23 Dec 1997 22:53:27 -0500

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) |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.