Comparisons return a 1-bit value, in theory
we could add a Wu1 width for them but I did
not bother and just used Wub. This simply
means that if a frontend generates an extsb
of a comparison result (silly), we will not
generate good code.
Crashing loads of uninitialized memory
proved to be a problem when implementing
unions using qbe. This patch introduces
a new UNDEF Ref to represent data that is
known to be uninitialized. Optimization
passes can make use of it to eliminate
some code. In the last compilation stages,
UNDEF is treated as the constant 0xdeaddead.
Previously, we would skip ssa construction when
a temporary has a single definition. This is
only part of the ssa invariant: we must also
check that all uses are dominated by the single
definition. The new code does this.
In fact, qbe does not store all the dominators
for a block, so instead of walking the idom
linked list we use a rough heuristic and declare
conservatively that B0 dominates B1 when one of
the two conditions is true:
a. B0 is the start block
b. B0 is B1
Some measurements on a big file from Michael
Forney show that the code is still as fast as
before this patch.
If a temporary is assigned exactly
once (most are), there is no need
to do any work to put it in ssa
form.
On an input file of ~35k loc, this
makes the processing time go from
2.9 secs to 1.2 secs.
Before this commit, I tried to make sure that
two interfering temporaries never ended up in
the same phi class.
This was to make sure that their register hints
were not counterproductively stepping on each
other's toes. The idea is fine, but:
* the implementation is clumsy because it
mixes the orthogonal concepts of
(i) interference and (ii) phi classes;
* the hinting process in the register
allocator is hard to understand because
the disjoint-set data structure used for
phi classes is cut in arbitrary places.
After this commit, the phi classes *really* are
phi classes represented with a proper disjoint-set
data structure.
