5 Jan 1998 22:57:32 -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: | cliffc <cliff.click@Eng.Sun.COM> |

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

--

Cliff Click Compiler Designer and Researcher

cliffc at acm.org 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.