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" <emailamit@gmail.com>
Newsgroups: comp.compilers
Date: 24 Jun 2005 14:12:31 -0400
Organization: http://groups.google.com
References: 05-06-10105-06-113
Keywords: code

>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

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