Re: non trivial constant folding

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

Return to the comp.compilers page.
Search the comp.compilers archives again.