Loading...
Please wait, while we are loading the content...
Similar Documents
Identifying loops using dj graphs (1995).
| Content Provider | CiteSeerX |
|---|---|
| Author | Sreedhar, Vugranam C. Gao, Guang R. Lee, Yong-Fong Leey, Yong-Fong |
| Abstract | Loop identification is a necessary step in loop transformations for high-performance architectures. The Tarjan intervals are single-entry, strongly connected subgraphs, so they closely reflect the loop structure of a program [Tar74]. They have been used for loop identification. In this paper we give a simple algorithm for identifying both reducible and irreducible loops using DJ graphs. Our method can be considered as a generalization of Tarjan's interval-finding algorithm, since we can identify nested intervals (or loops) even in the presence of irreducibility. i Contents 1 Introduction 1 2 Background and Notation 1 3 Reducible and Irreducible Loops 3 4 Our Algorithm 6 5 Conclusion and Related Work 10 List of Figures 1 An example of a flowgraph and its DJ graph : : : : : : : : : : : : : : : : : : : : 2 2 Examples of reducible and irreducible flowgraphs : : : : : : : : : : : : : : : : : : 4 3 An irreducible flowgraph with two irreducible loops : : : : : : : : : : : : : : : : : 6 4 ... |
| File Format | |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dj Graph Irreducible Loop Loop Identification Irreducible Flowgraphs Tarjan Interval Nested Interval Interval-finding Algorithm Loop Structure Related Work Loop Transformation High-performance Architecture Program Tar74 Irreducible Flowgraph Simple Algorithm Necessary Step |
| Content Type | Text |
| Resource Type | Article |
