Re: non trivial constant folding

"Ira D. Baxter" <idbaxter@semdesigns.com>
6 Jan 2001 22:12:32 -0500

          From comp.compilers

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]
| List of all articles for this month |

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.