Menu
I am looking into implementing common subexpression elimination (CSE) for expression graphs corresponding to large mathematical expressions (millions of nodes).
What algorithms are suitable for performing this? I was searching the internet for an easy-to-implement algorithm but I could not find anything. If possible the algorithm should have a linear complexity in the number of nodes of the complete expression graph.
209
(D) x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination.
The expression or sub-expression that has been appeared and computed before and appears again during the computation of the code is the common sub-expression. Elimination of that sub-expression is known as Common sub-expression elimination.
While constructing a DAG, A check is made to find if there exists any node with the same value. A new node is created only when there does not exist any node with the same value. This action helps in detecting the common sub-expressions and avoiding the re-computation of the same.
Common Subexpression Elimination is an optimization that searches for instances of identical expressions, and replaces them with a single variable holding the computed value.
These are expressions with no side effects? Then the easiest thing to do is to hash the trees for each sub-expression into buckets to determine candidates for sub-expression elimination. This is a special case of CSE where all the expressions are in a single (huge) "basic block". (I use this idea as the basis for detecting duplicate code.)
If the expressions have order and side effects, you may want to consider Value Numbering.
136
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
