# Re: number value method and LCSEquestions

## cliffc <cliff.click@Eng.Sun.COM>5 Jan 1998 22:57:32 -0500

From comp.compilers

Related articles
number value method and LCSEquestions gclind01@spd.louisville.edu (1997-12-23)
Re: number value method and LCSEquestions cliff.click@Eng.Sun.COM (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.
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
--

Post a followup to this message