Nesting of reducible and irreducible loops

ABSTRACT

Recognizing and transforming loops are essential steps in any attempt to improve the running time of a program. Aggressive restructuring techniques have been developed for single-entry (reducible) loops, but restructurers and the dataflow and dependence analysis they rely on often give up in the presence of multientry (irreducible) loops. Thus one irreducible loop can prevent the improvement of all loops in a procedure. This article give an algorithm to build a loop nesting tree for a procedure with arbitrary control flow. The algorithm uses definitions of reducible and irreducible loops which allow either kind of loop to be nested in the other. The tree construction algorithm, an extension of Tarjan's algorithm for testing reducibility, runs in almost linear time. In the presence of irreducible loops, the loop nesting tree can depend on the depth-first spanning tree used to build it. In particular, the header node representing a reducible loop in one version of the loop nesting tree can be the representative of an irreducible loop in another. We give a normalization method that maximizes the set of reducible loops discovered, independent of the depth-first spanning tree used. The normalization require the insertion of at most one node and one edge per reducible loop.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 3: Paul Howard Havlak , Ken Kennedy, Interprocedural symbolic analysis, 1995
• 4: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 5: SCHWARTZ, J. AND SHARIR, M. 1979. A design for optimizations of the bitvectoring class. Tech. rep., Courant Inst., New York Univ., New York. September.
• 6: SLOMAN, B., LAKE, T., AND WILLIAM, S. 1994. Identifying loops in flowgraphs. Tech. Rep. SEG/GN/94/1, Univ. of Reading, Reading, UK.
• 7: TARJAN, R. E. 1974. Testing flow graph reducibility. J. Comput. Syst. Sc{. 9, 355-365.
• 8: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Design, Languages

Keywords:
reducible loops, strongly-connected regions