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

>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

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