Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

What's in a region?: or computing control dependence regions in near-linear time for reducible control flow

What's in a region?: or computing control dependence regions in near-linear time for reducible... What ™s In a Region? Or Computing Control Dependence Regions In Near-Linear Time for Reducible Control Flow THOMAS BALL Madison University of Wisconsin, Regions of control dependence identify the instructions in a program that execute under the same control conditions. They have a variety of applications in parallelizing and optimizing compilers. Two vertices in a control-flow graph (which may represent instructions or basic blocks in a program) are in the same region if they have the same set of control dependence predecessors. The common algorithm for computing regions examines each control dependence at least once. As there maybe O(V X E) control dependence in the worst case, where V and E are the number of vertices and edges in the control-flow graph, this algorithm has a worst-case for finding regions in reducible control-flow running time of O(V x E). We present algorithms graphs in near-linear time, without using control dependence. These algorithms are based on alternative definitions of regions, which are easier to reason with than the definitions based on control dependence. Engineering]: Categories and Subject Descriptors: D.2.2 [Software Languages]: Processors ”compilers; optimization D.3.4 [Programming General Additional Terms: Algorithms, Languages Control dependence, control-flow Tools and Techniques; Key Words http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Letters on Programming Languages and Systems (LOPLAS) Association for Computing Machinery

What's in a region?: or computing control dependence regions in near-linear time for reducible control flow

Download PDF
16 pages

Loading next page...
 
/lp/association-for-computing-machinery/what-s-in-a-region-or-computing-control-dependence-regions-in-near-jfVZTUg01D
Publisher
Association for Computing Machinery
Copyright
Copyright © 1993 by ACM Inc.
ISSN
1057-4514
DOI
10.1145/176454.176456
Publisher site
See Article on Publisher Site

Abstract

What ™s In a Region? Or Computing Control Dependence Regions In Near-Linear Time for Reducible Control Flow THOMAS BALL Madison University of Wisconsin, Regions of control dependence identify the instructions in a program that execute under the same control conditions. They have a variety of applications in parallelizing and optimizing compilers. Two vertices in a control-flow graph (which may represent instructions or basic blocks in a program) are in the same region if they have the same set of control dependence predecessors. The common algorithm for computing regions examines each control dependence at least once. As there maybe O(V X E) control dependence in the worst case, where V and E are the number of vertices and edges in the control-flow graph, this algorithm has a worst-case for finding regions in reducible control-flow running time of O(V x E). We present algorithms graphs in near-linear time, without using control dependence. These algorithms are based on alternative definitions of regions, which are easier to reason with than the definitions based on control dependence. Engineering]: Categories and Subject Descriptors: D.2.2 [Software Languages]: Processors ”compilers; optimization D.3.4 [Programming General Additional Terms: Algorithms, Languages Control dependence, control-flow Tools and Techniques; Key Words

Journal

ACM Letters on Programming Languages and Systems (LOPLAS) – Association for Computing Machinery

Published: Mar 1, 1993

There are no references for this article.