Keshav Pingali
Gianfranco Bilardi
ABSTRACT
The control dependence relation is used extensively in restructuring compilers. This relation is usually represented using the control dependence graph; unfortunately, the size of this data structure can be quadratic in the size of the program, even for some structured programs. In this paper, we introduce a data structure called the augmented post-dominator tree (APT) which is constructed in space and time proportional to the size of the program, and which can answer control dependence queries in time proportional to the size of the output. Therefore, APT is an optimal representation of control dependence. We also show that using APT, we can compute SSA graphs, as well as sparse dataflow evaluator graphs, in time proportional to the size of the program. Finally, we put APT in perspective by showing that it can be viewed as a factored representation of control dependence graph in which filtered search is used to answer queries.
- ABC+88.Frances Allen, Michael Burke, Ron Cytron, Jeanne Ferrante, Wilson Hsieh, and Vivek Sarkar. A framework for determining useful parallelism. In Proceedings of the 1988 International Conference on Supercomputing, pages 207-215, St. Malo, France, July 4-8, 1988. Google Scholar
Digital Library
- Bal93.Thomas Ball. What's in a region? or computing control dependence regions in near-linear time for reducible control flow ACM Letters on Programming Languages and Systems, 2(t--4): 1-16, March- December 1993. Google ScholarDigital Library
- BR91.David Bernstein and Michael Rodeh. Global instruction scheduling for superscalar machines In Proceedings of the SIGPLAN '9I Conference on Programming Language Design and Implementation, pages 241-255, Toronto, Ontario, June 26-28, 1991. Google ScholarDigital Library
- CF93.Ron Cytron and Jeanne Ferrante. Efficiently computing qS-nodes on-the-fly. In Proceedings of the Sixth Workshop on Languages and Compilers for Parallel Computing, pages 461-476, August 1993. Published as Lecture Notes in Computer Science, number 768. Google ScholarDigital Library
- CFR+91.R, Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. 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
- CFS90.Ron Cytron, Jeanne Ferrante, and Vivek Sarkar. Compact representations for control dependence In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 337-351, White Plains, New York, June 20- 22, 1990. Google ScholarDigital Library
- Cha86.Bernard Chazelle. Filtering search: A new approach to query answering. SIAM Journal of Computing, 15:703-724, 1986. Google ScholarDigital Library
- CicBC.Marcus Tullius Cicero. Pro L. Cornelio Balbo Oratio 39. Published by Senate of Rome, Rome, 56 BC.Google Scholar
- CLR92.Thomas Cormen, Charles Leiserson, and Ronald Rivest. Introduction to Algorithms. The MIT Press, Cambridge, MA, 1992. Google ScholarDigital Library
- Fis81.Josh Fisher. Trace scheduling: a technique for global microcode compaction, iEEE Transactions on Computers, 7(3):478-490, 1981.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 Programmmg Languages and Systems, 9(3):319-349, June 1987. Google ScholarDigital Library
- GPS90.Rajiv Gupta, Lori Pollock, and Mary Lou Sofia. Parallelizing data flow analysis, in Proceedings of the Workshop on Parallel Compilation, Kingston, Ontario, May 6-8, 1990. Queen's University.Google Scholar
- GS87.Rajiv Gupta and Mary Lou Sofia Region scheduling. in 2nd International Conference on Supercomptcting, pages 141-148, 1987.Google Scholar
- Har85.D. Harel. A linear time algorithm for finding dominators in flowgraphs and related problems. In Proceedings of the 17th ACM Symposium on Theory of Computing, pages 185-194, Providence, Rhode Island, May 6-8, I985. Google ScholarDigital Library
- HPR87.Susan Horowitz, Jan Prins, and Thomas Reps. Integrating non-interfering versions of programs. In Conference Record of the 14th Annual ACM Symvosium on Principles of Programming Languages, pages 133-145, Munich, West Germany, January 21-23, 1987. Google ScholarDigital Library
- Joh94.Richard Johnson. Efficient Program Analysis using Dependence Flow Graphs. PhD thesis, CorneU Umversity, August 1994. Google ScholarDigital Library
- JP93.Richard Johnson and Keshav Pingali Dependencebased program analysis. In Proceedings of the SIG- PLAN '93 Conference on Programming Language Design and ImpIementatton, pages 78-89, Albuquerque, New Mexico, June 23-25, 1993. Google ScholarDigital Library
- JPP94.Richard Johnson, David Pearson, and Keshav Pingali. The program structure tree: Computing control regions in linear time. In Proceedings of the SIG- PLAN '94 Conference on Programming Language Design and Implementation, pages 171-185, Orlando, Florida, June 20-24, 1994. Google ScholarDigital Library
- LT79.Thomas Lengauer and Robert Endre Tarj an. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, l(1):121-141,July 1979. Google ScholarDigital Library
- Mic68.D. Michie. 'Memo' functions and machine learning. Nature, 2 t 8: t 9-22, April 1968.Google Scholar
- PBJ+91.Keshav Pingali, Micah Beck, Richard Johnson, Mayan MoudgiI1, and Paul StodghiI1. Dependence Flow Graphs: An algebraic approach to program dependencies. In Conference Record of the 18th Annual A CM Symposium on Principles of Programming Languages, pages 67-78, January 1991. Google ScholarDigital Library
- Pod93.Andy Podgurski. Reordering-transformations that preserve control dependence. Technical Report CES- 93-16, Case Western Reserve University, July 1993.Google Scholar
- SG95.Vugranam C. Sreedhar and Guang R. Gao. A linear time algorithm for placing (3-nodes. In Conference Record of POPL '95: 22nd ACM SIGPLAN- SIGACT Symposium on Principles of Programming Languages, pages 62-73, San Francisco, California, January 1995. Google ScholarDigital Library
- SGL94.Vugranam C. Sreedhar, Guang R. Gao, and Yongfong Lee. DJ-graphs and their applications to flowgraph analyses. Technical Report ACAPS Memo 70, McGill University, May 1994.Google Scholar
- SS70.R, M. Shapiro and H. Saint. The representation of algorithms. Technical Report CA-7002-1432, Massachusetts Computer Associates, February 1970.Google Scholar
- SS93.A. Segre and D. Scharstein. Bounded-overhead caching for definite-clause theorem proving. Journal of Automated Reasoning, 11:83-113, August 1993.Google ScholarCross Ref
- VEBKZ77.P. Van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathemetical Systems Theory, 10:99-127, 1977.Google ScholarCross Ref
Index Terms
- APT: a data structure for optimal control dependence computation
Recommendations
APT: a data structure for optimal control dependence computation
The control dependence relation is used extensively in restructuring compilers. This relation is usually represented using the control dependence graph; unfortunately, the size of this data structure can be quadratic in the size of the program, even for ...
APT Detector: Detect and Identify APT Malware Based on Deep Learning Framework
ICCAI '23: Proceedings of the 2023 9th International Conference on Computing and Artificial IntelligenceAdvanced persistent threat (APT) attacks use sophisticated attack techniques and covert command and control (C&C) channels to conduct long-term sustained cyber attacks on specific targets as unobtrusively as possible. Over the past ten years, APT ...
HTTP-Based APT Malware Infection Detection Using URL Correlation Analysis
APT malware exploits HTTP to establish communication with a C & C server to hide their malicious activities. Thus, HTTP-based APT malware infection can be discovered by analyzing HTTP traffic. Recent methods have been dependent on the extraction of ...
Comments