6 Jan 2001 22:12:32 -0500

Related articles |
---|

non trivial constant folding mpointie@eden-studios.fr (MickaĆ«l Pointier) (2001-01-05) |

Re: non trivial constant folding broeker@physik.rwth-aachen.de (Hans-Bernhard Broeker) (2001-01-05) |

Re: non trivial constant folding mihai@cs.wisc.edu (Mihai Christodorescu) (2001-01-06) |

Re: non trivial constant folding pat@jantar.org (Patryk Zadarnowski) (2001-01-06) |

Re: non trivial constant folding bonzini@gnu.org (2001-01-06) |

Re: non trivial constant folding idbaxter@semdesigns.com (Ira D. Baxter) (2001-01-06) |

Re: non trivial constant folding cfc@world.std.com (Chris F Clark) (2001-01-06) |

Re: non trivial constant folding anton@mips.complang.tuwien.ac.at (2001-01-09) |

Re: non trivial constant folding anton@mips.complang.tuwien.ac.at (2001-01-09) |

Re: non trivial constant folding metzger@rsn.hp.com (Robert Metzger) (2001-01-09) |

Re: non trivial constant folding sjmeyer@www.tdl.com (2001-01-09) |

Re: non trivial constant folding henry@spsystems.net (2001-01-09) |

[11 later articles] |

From: | "Ira D. Baxter" <idbaxter@semdesigns.com> |

Newsgroups: | comp.compilers |

Date: | 6 Jan 2001 22:12:32 -0500 |

Organization: | Posted via Supernews, http://www.supernews.com |

References: | 01-01-015 |

Keywords: | optimize |

Posted-Date: | 06 Jan 2001 22:12:32 EST |

Simple tree walkers can do "local" constant folding.

To fold constants further apart in expressions, you

need mechanisms based on the theory on associative

and associative/commutative ("AC") rewriting,

which in essence allows one to detect such operands "far apart" in

expressions.

You can find this in what is generically called the rewriting literature.

The Handbook of Theoretical Computer Science treats this pretty well.

Our DMS Reengineering Toolkit has transformational matching/rewriting

based on AC rewriting. If you declarare a binary operators such as "+"

as AC (and you have to careful about when you can do

this for real programming languages as other respondents

have pointed out), then your example can be accomplished

in DMS by simply saying:

rule fold_additive_constants(n1:NUMBER,n2:NUMBER): SUM -> SUM

= " n1+n2" -> add_constants(n1,n2);

DMS automatically finds matches for n1 and n2 in an expression tree

(SUM literal:72 (SUM variable:"X" literal 17))

and replaces it by the tree

(SUM literal:89 variable:"X")

This kind of matching is also useful for algebraic simplifications, such as

rule eliminate-additive-inverse(e1:product): SUM -> SUM

= " e1-e1" -> "0";

where the tree might look like

(SUM (POWER variable:"X" literal:2) (SUM literal:19 (MINUS (POWER

variable:"X" literal:2))))

Note that the interesting elements of the pattern match are "far apart" in

the expression.

The basic process for doing this is pattern tree matching, but the

sets of possible operands are first pre-computed based on algebraic

properties of the operators. This is a much more complex mechanism

than simple tree matching.

--

Ira D. Baxter, Ph.D.,CTO email: idbaxter@semdesigns.com

Semantic Designs, Inc. web: http://www.semdesigns.com

12636 Research Blvd. C-214 voice: (512) 250-1018 x140

Austin, TX 78759-2200 fax: (512) 250-1191

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.