Re: number value method and LCSEquestions

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
>
> for_all_instructions()
> {
> replace_ops_with_nodes();
> //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.
>
> simple_constant_fold();
> //handle instructions with only constant opcodes
> special_algebra();
> //handle adds of 0, multiplies by 1, multiplies by
> //powers of two, etc...
>
> replace_inst_with_node();
> //look in instructions hash table and return any
> //matching node if it exists. Else put instruction
> //in hash table
>
> make_name_for_inst();
> //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
back out.


Cliff


--
Cliff Click Compiler Designer and Researcher
cliffc at acm.org JavaSoft
(408) 863-3266 MS UCUP02-302
--

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