JavaScript is disabled for your browser. Some features of this site may not work without it.
Finding Regions Fast: Single Entry Single Exit and Control Regions in Linear Time

Author
Johnson, Richard C.; Pearson, David; Pingali, Keshav
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.
Date Issued
1993-07Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1365
Type
technical report