| Common-subexpression Elimination of Conditional Expressions (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Consider a side-eect-free expression | possibly containing conditionals | represented as a directed acyclic graph. Such an expression can be linearised into a tree by introducing let-abstractions for common subexpressions (viz. shared subgraphs). Let the number of vertices in the graph be n, let the number of edges be m and the number of shared vertices be k. We present a simple O(m + k maxfn; m = log mg) algorithm for optimal placement of let-abstractions. Key words: directed acyclic graph, common-subexpression elimination 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||