A fast algorithm for the elimination of common subexpressions

Abstract

There is a class of flow charts called "reducible" for which many global code optimization algorithms have been recently written. As a practical matter, one may expect the flow chart of a program appearing "in nature" to be reducible with a probability over 90% [3], and those that are not can be made reducible by "node splitting" [10]. Unfortunately, the algorithms written for reducible graphs do not really take advantage of reducibility, since they require O(n2) bit vecter steps in worst case, the same as for the obvious general algorithms of these types. In this paper we give an O(n log n) bit vecter step algorithm to determine "available expressions," [7]. This information is essential for global elimination of common subexpressions. However, the ideas discussed here carry over to other global code optimization problems such as "reaching definitions" [1], "live variables" [9] and "very busy variables" [6].