# Re: polynomial evaluation in GF(2) and common subexpression elimination

## "Amit Gupta" <emailamit@gmail.com>24 Jun 2005 14:12:31 -0400

From comp.compilers

Related articles
polynomial evaluation in GF(2) and common subexpression elimination panneton@hotmail.com (rng) (2005-06-21)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-06-23)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio drizzle76@gmail.com (drizzle) (2005-06-23)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio emailamit@gmail.com (Amit Gupta) (2005-06-24)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-26)
| List of all articles for this month |

 From: "Amit Gupta" Newsgroups: comp.compilers Date: 24 Jun 2005 14:12:31 -0400 Organization: http://groups.google.com References: 05-06-10105-06-113 Keywords: code Posted-Date: 24 Jun 2005 14:12:31 EDT

>you will find that instruction selection is about finding minimum
>cost cover for a tree. In other words, represent your input as a
>tree of simplest units and then find instructions to cover single or
>multiple nodes belonging to the tree. In case you are more familiar
>with logic circuits, the same technique (tree matching) is used to
>find a minimal cost cover using components from a library for a
>digital circuit represented using simplest gates. ( refer Hatchel and
>Somenzi or any good digital design book)

I like the above formulation of the problem. But you are left with the
problem of finding different decompositions of the function and then
apply minimum-cost cover based on some available library of
operator. The question is how to find "that" best decomposition.
Virtex-cover does not try to find an alternate decomposition.

In this case, since "+" is costliest operator, a rule based
decomposition could be to convert a parse-tree of type
"a*a + a = a(a+1)", if (a+1) is already somewhere in the expression.
In general you would want to search for the costliest divisor
(a+1 in this case) in the parse tree, which contains the operator
(say, +) you want to optimize, and then try that divisor on the
complete expression to see if you get a feasible and less'er cost
solution.

-Amit

Post a followup to this message