Peng Tu
David Padua
ABSTRACT
In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at ø-nodes. The gating functions specify the control dependences for each reaching definition at a ø-node. We introduce a new concept of gating path, which is path in the control flow graph from the immediate dominator u of a node v to v, such that every node in the path is dominated by u. Previous algorithms start with ø-function placement, and then traverse the control flow graph to compute the gating functions. By formulating the problem into gating path construction, we are able to identify not only a ø-node, but also a gating path expression which defines a gating function for the ø-node.
- ASU86.A. V. Aho, R. Sethi, and I.D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986. Google Scholar
Digital Library
- AWZ88.B. Alpern, M. N. Wegman, and F. K. Zadeck. Detecting equality of variables in programs. In Proc. of the 15th A UM Symposium on Princzples of Programming Languages, pages 1-11, 1988. Google ScholarDigital Library
- BE94.William Blume and Rudolf Eigenmann. The range test: A dependence test for symbolic, non-linear expressions. In Proceedings of Super. computing '9~, November 1994. Google ScholarDigital Library
- BEF+94.Bill Bhme, Rudolf Eigenmann, Keith FMgin, John Grout, Jay Hoefiinger, David Padua, Paul Petersen, Bill Pottenger, Lawrence Rauchwerger, Peng Tu, and Stephen Weatherford. Polaris: The next generation in parallelizing compilers. In Proc. 7th Workshop on Programming Languages and Compilers for Parallel Computing, August 1994.Google Scholar
- BMO90.R. Ballance, A. Maccabe, and K. Ottenstein. The program dependence web: a representation supporting control-, data-, and demanddriven interpretation of imperative languages. In Proceedings of the SIGPLAN'90 Conference on Programming Language Design and Impleraentatzon, pages 257-271, June 1990. Google ScholarDigital Library
- CFR+91.Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991. Google ScholarDigital Library
- CKPK90.George Cybenko, Lyle Kipp, Lynn Pointer, and David Kuck. Supercomputer performance evaluation and the perfect benchmarks. In Proceedings of }US, Amsterdam, Netherlands, pages 162-174, March 1990.Google ScholarDigital Library
- Far77.R. Farrow. Efficient on-line evaluation of functions defined on paths in trees. Technical report, Rice University, Dept. Math. Sci., 1977.Google Scholar
- FOW87.J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependency graph and its uses in optimization. A CM Transactions on Programming Languages and Systems, 9(3):319- 349, June 1987. Google ScholarDigital Library
- Har85.P. Hard. A linear time algorithm for finding dominators in flowgraphs and related problems. In Proc. of the 17th A CM Symposium on Theory of Computing, May 1985. Google ScholarDigital Library
- Hav93.P~ul Ilavlak. Construction of thinned gated single-assignment form. In Proc. 6rd Workshop on Programmzng Languages and Compilers for Parallel Computing, August 1993. Google ScholarDigital Library
- JP93.R. Johnson and K. Pingali. Dependence-based program analysis. In Proc. the SIGPLAN '93 Conference on Program Language Design and Irapleraentat,on, June 1993. Google ScholarDigital Library
- JPP94.R. Johnson, D. Pearson, and K. Pingali. The program structure tree: Computing control regions in linear time. In Proc. the SIGPLAN '94 Conference on Program Language Design and Implementation, June 1994. Google ScholarDigital Library
- LT79.Thomas Lengauer and Robert Endre Tarjan. A fast algorithm for finding dominators in a flowgraph. A CM Transactions on Programming Languages and Systems, 1(1):121-141, July t979. Google ScholarDigital Library
- RWZ88.B.K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computation. In Proc. o/the 15th A UM Symposium on Principles of Programming Languages, pages 12-27, 1988. Google ScholarDigital Library
- SG94.V.C. Sreedhar and G.R. Gao. Computing ~- nodes in linear time using dj-graph. Technical Report Technical Report,ACAPS Technical Memo 75, McGill University, School of Computer Science, January 1994.Google Scholar
- Tar79.Robert Endre Tarjan. Applications of path compression on balanced trees. Journal o/A CM, 26(4):690-715, October 1979. Google ScholarDigital Library
- Tar81a.Robert Endre Tarjan. Fast algorithm for solving path problems. Journal of the A UM, 28(3):594- 614, July 1981. Google ScholarDigital Library
- Tar81b.Robert Endre Tarjan. A unified approach to path problems. Journal o/the A UM, 28(3):577- 593, July 1981. Google ScholarDigital Library
- TP93.Peng Tu and David Padua. Automatic array privatization. In Proc. 6rd Workshop on Programming Languages and Compilers/or Parallel Computing, August 1993. Google ScholarDigital Library
- TP95.Peng Tu and David Padua. GSA based demanddriven symbolic analysis for parallelizing compilers. In Proc. A CM 1995 International Conference on Supercomputing, July 1995. Google ScholarDigital Library
- Wol92.Michael Wolfe. Beyond induction variables. Proc. the S}GPLAN'92 Conference on Programming Language Design and }mplementation, June 1992. Google ScholarDigital Library
- WZ91.M.N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. A CM Transactions on Programming Languages and Systems, 13(2):181-210, April 1991. Google ScholarDigital Library
Recommendations
Efficient building and placing of gating functions
In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at ø-nodes. The gating functions specify the control dependences for each reaching definition at a ø-...
The program dependence graph and its use in optimization
In this paper we present an intermediate program representation, called the program dependence graph (PDG), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the ...
Comments