Copy propagation without lookahead

Hi,


I have a code generator (softwire.sourceforge.net) which does not
create a dataflow graph (*), but generates every instruction
instantly. Therefore I have no 'lookahead' and transformations are not
directly possible. However, I did manage to implement a quite
efficient register allocator using the linear scan algorithm.


Now I would like to add the copy propagation optimization. My newest
project (sw-shader.sourceforge.net) uses SoftWire to generate
processing pipelines. This works very well, but the code is full of
redundant mov instructions so performance is not yet optimal.


I had an idea how to implement it but it doesn't work: For every copy
from register to register, I can tag that instruction so it does not
get written in the final buffer (yet). For the registers I can then
store which is an alias of the other, and also store a reference to
the mov instruction (so it can be untagged). At every register free
operation, I just clear the alias and instruction field so nothing
happened (i.e. there is copy propagation and the mov instruction never
gets written). If a register is used, it can be either an alias or be
aliased by another register. In the former case I would just use the
alias register. In the latter case, it means the register cannot be
copy propagated and the mov instruction it untagged.


This creates a problem in a situation like this:


x := y
x *= z
y += w


The above algorithm would convert it into:


x := y (got untagged by third instruction)
y *= z (unaware that y needs to be preserved for third instruction)
y += w


So, I hope my explanation was clear. I'm just a student with an
interest in assembly but I've never had any compiler courses so I
don't know how to solve this optimally.


Also, I can do some trivial peephole optimizations on single
instructions or instructions in a direct sequence, but nothing
advanced. This problem isn't as big as the copy propagation though,
because my processing pipelines are generated from hand-optimized
assembly instruction sequences anyway.


So, any suggestions would be highly appreciated!


Kind regards,


Nicolas Capens


(*) It is not possible to create a dataflow graph for SoftWire since
it does not work with quadruples (or triples) but directly with the
actual x86 assembly instructions. There are more than 5000 variants
with all kinds of side-effects so it's really not feasible...

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