Re: renaming question

Xinan TANG <tang@binkley.cs.mcgill.ca> writes:
> The question is that given a C program, is it possible to do some
>renaming to either expose parallelism or facilitate register allocation to
>increase speed.
>
> At the first step, it might be easy if only SCALAR variable is
>considered. Is there any efficient algorithm to do this sort of thing?
>
> When talking about renaming, I mean to do source to source
>transformation and want to keep the original semantics of the program.
>Please don't point me some thing like SSA beacuse that's not I want.


Mostly, parallelizers and register allocators don't care what names you
use in your source; they're going to choose convenient names for
themselves. Furthermore, there won't be any sort of one-to-one mapping
between source-level names and internal names; instead, each source-level
variable will typically be split into several pieces, with each piece (I
usually think of each "value" getting a name).


I use SSA (sorry, but that's the way it is) to find all the values and
name them all uniquely. To determine unique names for all the connected
values (sometimes called "web analysis" or "finding the right number of
names"), I walk over the SSA form unioning names connected by phi
functions, using the classical fast disjoint set union algorithm. Then
rewrite all the code using the disjoint set find, with path compression.


How about an example to clear up all the terminology?
Here's some source


i = 1
j = 2;
if (p) {
j = f(i)
i = j + 1;
}
else
j = j + f(j);
return i + j;


Now convert to pruned SSA (most algorithms give "minimal SSA" --
"pruned SSA" is minimal SSA with dead phi functions removed), giving


i0 = 1
j0 = 2;
if (p) {
j1 = f(i0)
i1 = j1 + 1;
}
else
j2 = j0 + f(j0);
i2 = phi(i1, i0)
j3 = phi(j1, j2)
return i2 + j3;


In this form, variables have disappeared completely (well, ok, I use the
form i0, i1, i3, so you can see what used to be "i", but I could just as
well have named everything a, b, c, ...) and every _value_ has a distinct
name. We like this for optimization because we like to find out facts
about values -- whether they are live, constant, etc. If we try do do
similar analysis with variables, we find many less facts (for example, i0
and j0 are clearly constant, but i and j are not).


This code isn't executable because of the phi functions. To get rid
of the phi functions, I can union together all the names connected by
phi functions. The result is


i012 = 1
j0 = 2;
if (p) {
j123 = f(i012)
i012 = j123 + 1;
}
else
j123 = j0 + f(j0);
return i012 + j123;


and now we back to an executable form, but with names suitable for
register allocator or scheduling (no artificial anti dependences
introduced by the programmer's arbitrary selection of names). For
register allocation, we see three live ranges: i012, j0, and j123.
Coloring, we find that j0 and j123 can be given the same color. Of
course, this should be no surprise since the original code was written
with only 2 variables. But this is only a simple example -- real code has
plenty of variables and plenty of temporary names introduced by the
compiler and optimizer. Throw them all into the same pot, as above, and
they can all be handled efficiently and uniformly.


Some register allocation references that talk about all this, in more or
less detail:


    title="Register Allocation and Spilling via Graph Coloring",
    author="Gregory J. Chaitin",
    journal=sigplan,
    year=1982,
    month=jun,
    volume=17,
    number=6,
    note=pldi82,
    pages="98--105"


    title="Effectiveness of a Machine-Level Global Optimizer",
    author="Mark Scott Johnson and Terrence C. Miller",
    journal=sigplan,
    year=1986,
    month=jul,
    volume=21,
    number=7,
    note=pldi86,
    pages="99--108"


    author="Preston Briggs",
    title="Register Allocation via Graph Coloring",
    school="Rice University",
    year=1992,
    month=apr,


The first two are in old PLDI proceedings. The last you can get via
anonymous ftp from cs.rice.edu, in the directory public/preston


So, going back to original question... Renaming scalars at the source
level is going to change anything at all. Arrays may be another matter,
as you can confuse matters arbitrarily by clever (perverse) aliasing.


Preston Briggs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.