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

Your problem is not a case for common subexpression elimination but
rather it is similar to the problem of instruction selection. A simple
adaptation of that might be useful in your case. If you refer to any
compiler textbook say for example Andrew Appel, 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)

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