|number value method and LCSEquestions email@example.com (1997-12-23)|
|Re: number value method and LCSEquestions cliff.click@Eng.Sun.COM (cliffc) (1998-01-05)|
|Date:||5 Jan 1998 22:57:32 -0500|
George C. Lindauer wrote:
> Last year Mr. Cliff Click gave me approximately the following
> algorithm for LCSE determination through the value-number
> approach. It relies on two hash tables, one that maps names
> to CSEs and one that is used to look up registered
> CSEs. I have been too busy to do much with it but now I have a
> couple of questions about what to do with it:
> 1) first, I understand this concept, but I am a little foggy
> on how to convert the resulting hash tables back to
> code in the correct order.
> 2) What is the best way to deal with pointer aliasing at
> this stage? Just assume a pointer can point to everything
> and invalidate all nodes?
> 3) if I want to do advanced constant folding on tripled
> intermediate code, e.g.:
> t1 = t0 + 4;
> t3 = t2 + 6;
> t4 = t1 + t3;
> where the 4 and 6 can be combined...
> I'm wondering if this is worthwhile? ...
Sure! Easy to do as well.
At your "special_algebra" point below, just reassociate ADDs
to fold constants:
(con + X) becomes (X + con) AND
((Y + con0) + con1) becomes (Y + (con0+con1))
> Here's the algorithm he gave me, restated in my own words
> //look in names hash table and replace any operands
> //with its corresponding node. In the case an operand
> //is not in the table make a live-in node for it.
> //handle instructions with only constant opcodes
> //handle adds of 0, multiplies by 1, multiplies by
> //powers of two, etc...
> //look in instructions hash table and return any
> //matching node if it exists. Else put instruction
> //in hash table
> //put name and node in names hash table.
At the end of the block, assume all the named values are live-out.
Make all the name/nodes in the hash table roots of a DAG, and
walk the DAG in topological order to get the optimized instructions
Cliff Click Compiler Designer and Researcher
cliffc at acm.org JavaSoft
(408) 863-3266 MS UCUP02-302
Return to the
Search the comp.compilers archives again.