number value method and LCSEquestions (George C. Lindauer)
23 Dec 1997 22:53:27 -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: (George C. Lindauer)
Newsgroups: comp.compilers
Date: 23 Dec 1997 22:53:27 -0500
Organization: University of Louisville
Keywords: optimize

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? I mean if one of these
instructions can be reused as-is then folding would get in
the way... anyone have a feel for whether I should even bother
with this?

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.

Post a followup to this message

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