The classical common subexpression problem in program optimization is the detection of identical subexpressions. Suppose we have some extra information and are given pairs of expressions e. =e.. which must have the same value, and expressions fj1 ≠fj2 which must have different values. We ask if as a result, h1=h2, or h1≠h2. This has been called the uniform word problem for finitely presented algebras, and has application in theoremproving and code optimization. We show that such questions can be answered in O(nlogn) time, where n is the number of nodes in a graph representation of all relevant expressions. A linear time algorithm for detecting common subexpressions is derived. Algorithms which process equalities, inequalities and deductions on-line are discussed.
|Original language||English (US)|
|Number of pages||13|
|Journal||Conference Record of the Annual ACM Symposium on Principles of Programming Languages|
|State||Published - Jan 1 1978|
|Event||5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1978 - Tucson, United States|
Duration: Jan 23 1978 → Jan 25 1978
ASJC Scopus subject areas