Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Finding Regions Fast: Single Entry Single Exit and Control Regions in Linear Time
Authors: Johnson, Richard C.
Pearson, David
Pingali, Keshav
Keywords: computer science
technical report
Issue Date: Jul-1993
Publisher: Cornell University
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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
93-1365.pdf1.95 MBAdobe PDFView/Open
93-1365.ps484.96 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us