Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!ima!johnl
From: johnl@ima.UUCP
Newsgroups: mod.compilers
Subject: Peephole Optimizations
Message-ID: <512@ima.UUCP>
Date: Thu, 12-Mar-87 19:54:21 EST
Article-I.D.: ima.512
Posted: Thu Mar 12 19:54:21 1987
Date-Received: Sat, 14-Mar-87 09:07:57 EST
Sender: johnl@ima.UUCP
Lines: 39
Approved: compilers@ima.UUCP

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
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request