Patent
1997-06-13
2000-02-15
Hafiz, Tariq R.
395707, 395708, G06F 945
Patent
active
060262419
ABSTRACT:
Partial redundancy elimination of a computer program is described that operates using a static single assignment (SSA) representation of a computer program. The SSA representation of the computer program is processed to eliminate partially redundant expressions in the computer program. This processing involves inserting .PHI. functions for expressions where different values of the expressions reach common points in the computer program. A result of each of the .PHI. functions is stored in a hypothetical variable h. The processing also involves a renaming step where SSA versions are assigned to hypothetical variables h in the computer program, a down safety step of determining whether each .PHI. function in the computer program is down safe, and a will be available step of determining whether each expression in the computer program will be available at each .PHI. function following eventual insertion of code into the computer program for purposes of partial redundancy elimination. The processing also includes a finalize step of transforming the SSA representation of the computer program having hypothetical variables h to a SSA graph that includes some insertion information reflecting eventual insertions of code into the computer program for purposes of partial redundancy elimination, and a code motion step of updating the SSA graph based on the insertion information to introduce real temporary variables t for the hypothetical variables h.
REFERENCES:
patent: 5274818 (1993-12-01), Vasilevsky et al.
patent: 5293631 (1994-03-01), Rau et al.
patent: 5327561 (1994-07-01), Choi et al.
patent: 5448737 (1995-09-01), Burke et al.
patent: 5659754 (1997-08-01), Grove et al.
patent: 5768596 (1998-06-01), Chow et al.
patent: 5842017 (1998-11-01), Hookway et al.
Rosen et al., " Global Value Numbers and Redundant Computations" , Conference Record of the 15.sup.th ACM Symposium on the Principles of Programming Languages, Jan. 1988, pp. 12-27.
Briggs et al., " An Efficient Representation of Sparse Sets" , ACM Letters on Programming Languages and Systems, vol. 2, nos. 1-4, Mar.-Dec. 1993, pp. 59-69.
Chakrabarti et al., " Global Communication Analysis and Optimization" , ACM, 1996, pp. 68-78.
Alpern et al., "Detecting Equality of Variables in Programs," Conference Record of the 15th ACM Symposium on the Principles of Programming Languages, Jan., 1988, pp. 1-11.
Chase et al., "Analysis of Pointers and Structures," Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, Jun., 1990, pp. 296-310.
Choi et al., "Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects," Conference Record of the 20th ACM Symposium on the Principles of Programming Languages, Jan., 1993, 232-245.
Chow et al., "Effective Representation of Aliases and Indirect Memory Operations in SSA Form," Compiler Construction, 6th International Conference, Apr., 1996, pp. 253-267.
Chow, F., "A Portable Machine-independent Global Optimizer--Design and Measurements," Ph.D. Thesis and Technical Report 83-254. Computer System Lab. Stanford University, Dec., 1983, pp. 1-172.
Click, C., "Global Code Motion Global Value Numbering," Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation, Jun., 1995, pp. 246-257.
Cocke et al., Programming Languages and Their Compilers, Courant Institute of Mathematical Sciences, New York University, Apr., 1970, pp. 320-334.
Cytron et al., "Efficient Accommodation of May-alias Information in SSA Form," Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, Jun., 1993, pp. 36-45.
Rosen et al., "Global Value Numbers and Redundant Computation," Conference Record of the 15th ACM Symposium on the Principles of Programming Languages, Jan., 1988, pp. 12-27.
Ruf, "Context-Insensitive Alias Analysis Reconsidered," Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation, Jun., 1995, pp. 13-22.
Steensgaard, "Sparse Functional Stores for Imperative Programs," Proceedings of the SIGPLAN '95 Workshop on Intermediate Representations, Jan., 1995, pp. 62-70.
Wegman et al., "Constant Propagation with Conditional Branches," ACM Transactions on Programming Languages and Systems, vol. 13, No. 2, Apr., 1991, pp. 181-210.
Wilson et al., "Efficient Context Sensitive Pointer Analysis for C Programs," Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation, Jun., 1995, pp. 1-12.
Wolfe, "Beyond Induction Variables," Proceedings of the SIGPLAN '92 Conference on Programming Language Design and Implementation, Jun., 1992, pp. 162-174.
Choi et al., "On the Efficient Engineering of Ambitious Program Analysis," IEEE Transactions on Software Engineering, vol. 20, No. 2, Feb., 1994, pp. 105-114.
Cytron et al., "Efficiently Computing Static Single Asignment Form and the Control Dependence Graph," ACM Transactions on Programming Languages and Systems, vol. 13, No. 4, Oct., 1991, pp. 451-490.
Stoltz et al., "Extended SSA with Factored Use-Def Chains to Support Optimization and Parallelism," Proceedings of the 27th Annual Hawaii International Conference on System Sciences, 1994, pp. 43-52.
P. Briggs and K. Cooper, "Effective Partial Redundancy Elimination", Proceedings of the ACM SIGPLAN '94 Conference on Programming language Design and Implementation, pp. 159-170, Jun. 1994.
J. Choi, R. Cytron, and J. Ferrante, "Automatic Construction of Sparse Data Flow Evaluation Graphs", Conference Record of the Eighteenth ACM Symposium on Principles of Programming Languages, pp. 55-66, Jan. 1991.
F. Chow et al., "Engineering a RISC Compiler System", Proceedings of IEEE COMPCON, pp. 132-137, Mar. 1986.
F. Chow, "Minimizing Register Usage Penalty At Procedure Calls", Proceedings of the ACM SIGPLAN '88 Conference on Programming Language Design and Implementation, pp. 85-94, Jun. 1988.
K. Cooper and T. Simpson, "Scc-Based Value Numbering", Technical Report CRPC-TR95636-S, Dept. of Computer Science, Rice University, Oct. 1995.
K. Cooper and T. Simpson, "Value-driven Code Motion", Technical Report CRPC-TR95637-S, Dept. of Computer Science, Rice University, Oct. 1995.
Choi, J. et al., "Incremental Computation of Static Single Assignment Form", Proceedings of the Sixth International Conference on Compiler Construction, pp. 223-237, Apr. 1996.
Dhamdhere, D. et al., "A New Algorithm for Composite Hoisting and Strength Reduction Optimization (+ corrigendum)", Journal of Computer Mathematics, 27:1-14(+ 31-32), 1989.
Dhamdhere, D. et al., "How to Analyze Large Programs Efficiently and Informatively", Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 212-223, Jun. 1992.
K. Dreschler and M. Stadel, "A Variation of Knoop, Ruthing and Steffen's Lazy Code Motion", SIGPLAN Notices, 28(5):29-38, May 1993.
Gerlek, M. et al., "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form", ACM Trans. On Programming Language and Systems, 17(1):85-122, Jan. 1995.
Gerlek, M. et al., "A Reference Chain Approach for Live Variables", Technical Report CSE 94-029, Oregon Graduate Institute, Apr. 1994.
Johnson, R., "Efficient Program Analysis Using Dependence Flow Graphs", Technical Report (PhD Thesis), Dept. of Computer Science, Cornell University, Aug. 1994.
Johnson, r. et al., "The Program Structure Tree: Computing Control Regions in Linear Time", Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pp. 171-185, Jun. 1994.
Knoop, J. et al., "Lazy Code Motion", Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 224-234, Jun. 1992.
Knoop, J. et al., "Lazy Strength Reduction", Journal of Programming Languages, 1(1):71-91, Mar. 1993.
Knoop, J. et al., "Optimal Code Motion: Theory and Practice", ACM Trans. on Programming Languages and Systems, 16(4):1117-1155, Oct. 1994.
Knoop, J. et al., "Partial Dead Code Elimination", Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and
Chan Sun
Chow Frederick
Kennedy Robert
Liu Shin-Ming
Lo Raymond
Chaki Kakali
Hafiz Tariq R.
Silicon Graphics Inc.
LandOfFree
System, method, and computer program product for partial redunda does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method, and computer program product for partial redunda, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method, and computer program product for partial redunda will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1912891