# number value method and LCSEquestions

## gclind01@spd.louisville.edu (George C. Lindauer)23 Dec 1997 22:53:27 -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: gclind01@spd.louisville.edu (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

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.
}
--

Post a followup to this message