Compilers - Eliminating SSA variables

Author

Eliminating SSA variables

Richard M.

2005-07-28, 4:02 am

Given a source program fragment like this:
int i;
for (i = 0; i < 10; i++)
;

After SSA transformation and back, we have

i = 0;
i1 = i;
top:
i2 = i1+1;
i1 = i2;
if (i2 < 10) goto top;
....

The problem now is that there are 2 variables inside the loop, i1 and i2
with overlapping lifetimes, thus using more registers and causing extra
register moves at code generation time. Is there something we can do to
address this problem?

Thanks for any hints and pointers!

--
// richard
http://www.imagecraft.com

Jeremy Singer

2005-07-31, 4:01 am

> The problem now is that there are 2 variables inside the loop, i1 and i2
> with overlapping lifetimes, thus using more registers and causing extra
> register moves at code generation time. Is there something we can do to
> address this problem?

A register coalescing phase should combine i1 and i2 into the same
register. In this case, extra register moves are not necessary. SSA
\phi-functions can provide hints to the coalescing algorithm. The recent
paper "Optimizing Translation out of SSA Using Renaming Constraints" by
Rastello et al, CGO 2004, gives more details.

It may also be worth checking out Sebastian Hack's work on "Interference
Graphs of Programs in SSA-form" -
http://www.info.uni-karlsruhe.de/pu...ions.php/id=382
He advocates performing register allocation directly from SSA, rather
than undoing the SSA renaming.

Cheers,
Jeremy

2005-07-31, 4:01 am

Register Allocation has coalescing phase which will remove these
redundant moves. So the same register will be used. But in general my
guess is SSA code should go through some of the basic optimizations
again

Ali Al-Shabibi

2005-07-31, 4:01 am

Hi,

Basically, what you want to do is avoid the copy of i2 to i1 on the last
iteration, to do this you must identify the critical edge and split it.
In your case the critiacal edge is the your goto top. So in your SSA
form you will move the assignment of i2 to i1 into another node and only
jump to that node in the case where the if (i2 < 10) is true.

Hope this is clear enough. This problem is called the lost-copy problem
and you can find very good resources about this on the web.

Enjoy,

--
-- Ali Al-Shabibi (Aka Al-Hacker)

Richard M. wrote:
> Given a source program fragment like this:
> int i;
> for (i = 0; i < 10; i++)
> ;
>
> After SSA transformation and back, we have
>
> i = 0;
> i1 = i;
> top:
> i2 = i1+1;
> i1 = i2;
> if (i2 < 10) goto top;
> ...
>
> The problem now is that there are 2 variables inside the loop, i1 and i2
> with overlapping lifetimes, thus using more registers and causing extra
> register moves at code generation time. Is there something we can do to
> address this problem?

Sponsored Links