|polynomial evaluation in GF(2) and common subexpression elimination firstname.lastname@example.org (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 email@example.com (drizzle) (2005-06-23)|
|Re: polynomial evaluation in GF(2) and common subexpression eliminatio firstname.lastname@example.org (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)|
|From:||"Amit Gupta" <email@example.com>|
|Date:||24 Jun 2005 14:12:31 -0400|
>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
Return to the
Search the comp.compilers archives again.