24 Jun 2005 14:12:31 -0400

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) |

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.