Webizer

Modern register allocation algorithms are usually not based on pseudo registers, like the GCC one, since pseudo registers representing variables may be reused for no real purpose. For instance many programmers are using i in the single function as index counter in many different loops. It is stupid to constraint register allocator to allocate single hardware register for all occurrences of variable i.

Solution to this problem is to split each pseudo register into one or more webs. The name web comes from DU data-flow representation. In this form, each definition of register has an attached linked list pointing to all instructions possibly using the value (Definition Use chains). The webs can be constructed by unifying all definitions having the same uses (as when instruction uses value from multiple possible definitions, all definitions must come to the same register).

We have implemented simple pass that constructs DU chains, computes webs and when single pseudo has attached multiple webs, it creates new pseudo register, so at the end there is $1-1$ correspondence between pseudo registers and webs.

This allows register allocation to be stronger without additional modifications. In addition this makes some other optimization passes stronger. For instance the following piece of code

after webizing looks like:

and GCC Common Subexpression Elimination pass converts it into:

when offsetted addressing is available. We run Webizer twice -- once in early compilation stages and once after tracing and loop unrolling, so we do not need to implement special purpose pass to split induction variables.