Peephole Optimizations

In article <373@artecon.artecon.UUCP> Kevin writes:
>I am looking for some source/suggestions/clues/etc... (whatever) for
>Peephole Optimizers. ...


One project I worked on was a Davidson Frazer style Peephole Optimizer.


This takes an incoming stream of instructions inside a basic block (using
an infinite register set),


1) expands them into a symbolic description of their effect
(register transfer lists)
2) keeps track of register values not killed, reusing them
where possible.
3) As a side effect of #2, constructs links from instructions
to instructions that they logically depend on (ie. because
the prior instruction computes a value the latter instruction
uses)
4) collapses pairs of logically related instructions by composition
of the register transfer list - if the result can be represented
by a valid instruction, replace pair with that.
5) assignment of virtual registers to real registers.


The original researches goal was retargetability; my experience was that
it was a little slow, but quite thorough, getting you the results of a
lot of ad-hoc fixups with a few solid techniques. Note that the original
work was done using a series of textual filters for 1-5. You can do a lot
better in terms of speed by using internal linked list representations
of register transfer lists.


The references to the original paper is:
TOPLAS, april '80 pg 191, Davidson, Frazer
'Implementation of a Retargetable Peephole Analyser'


Max
--

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