Re: Coalescing register allocators

Bjarne 'Rusa' Steensgaard writes:
>The statement
> if (P) then a = X; else a = Y;
>will be represented by the following graph:
> _ _ _
> / \ / \ / \
> | P | | X | | Y |
> \_/ \_/ \_/
> | \ /
> | _|_|_
> | / \
> |_____| gamma |
> \_____/
> |
> |
>The gamma node is selecting between the 4 and the 5 node depending on the
>value computed by the P node.


But that's the wrong representation! It corresponds to the statement


a := if P then X else Y fi


which is very different. As you point out, this change complicates
register allocation. Indeed, it leads to sub-optimal allocation,
because it forces the assumption that 'a' must have the same binding
on both paths, which in the more global context might not be true.


More important, however, is that it forces the values of X and Y to
a common subtype, before the assignment to a. This could well cause
major problems in optimising constraint checks, for instance. To
see this, suppose we have


a : integer range 0..10
X : integer range 0..10
Y : integer range 0..20


Clearly, in the original formulation, no check is needed on the assignmenrt
of X to a. But after merging the values in the "gamma" node, the subtype
of the merged value will be 0..20, and it will seem that a constraint
check is always required.


I respectfully suggest that the problems you are encountering are symptoms
of a design error in the internal representatiom, and the solution is to
fix the error.
[I tend to agree. It looks like you're assigning values to registers much
too early. See the next message for the classic references on register
allocation. -John]
--

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