Finding Regions Fast: Single Entry Single Exit and Control Regions in Linear Time

Abstract

Many compilation problems require computing the control dependence equivalence relation which divides nodes in a control flow graph into equivalence classes such that nodes are in the same class if and only if they have the same set of control dependences. In this paper, we show that this relation can be computed in $O(E)$ time by reducing it to a naturally stated graph problem: in a strongly connected component, divide nodes into equivalence classes such that every cycle passes through all or none of the nodes in an equivalence class. Our algorithm does not require the computation of the control dependence relation or of the postdominator relation - in fact, it runs faster in practice than the best algorithms for either of these problems. We also show that our algorithm can be used to determine the single entry single exit regions of a control flow graph in $O(E)$ time.