Re: number value method and LCSEquestions

cliffc <>
5 Jan 1998 22:57:32 -0500

          From comp.compilers

Related articles
number value method and LCSEquestions (1997-12-23)
Re: number value method and LCSEquestions (cliffc) (1998-01-05)
| List of all articles for this month |

From: cliffc <>
Newsgroups: comp.compilers
Date: 5 Jan 1998 22:57:32 -0500
Organization: Sun Microsystems
References: 97-12-156
Keywords: analysis

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 Click Compiler Designer and Researcher
cliffc at JavaSoft
(408) 863-3266 MS UCUP02-302

Post a followup to this message

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