Data processing: software development – installation – and managem – Software program development tool – Translation of code
Patent
1997-11-26
2000-10-10
Chaki, Kakali
Data processing: software development, installation, and managem
Software program development tool
Translation of code
717 5, 717 8, G06F 945
Patent
active
061311898
ABSTRACT:
A system and method for an optimizer of a compilation suite for representing aliases and indirect memory operations in static single assignment (SSA) during compilation of a program having one or more basic blocks of source code. The optimizer converts all scalar variables of said program to SSA form, wherein said SSA form includes a plurality of variable versions, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the variable versions. The optimizer also determines whether a variable version can be renamed to a zero version, and upon such a determination, the optimizer renames the variable version to a zero version. The optimizer further converts all indirect variables of a program to SSA form, wherein the SSA form includes a plurality of virtual variable versions such that a virtual variable is assigned to an indirect variable, zero or more occurrences of a .chi. function, zero or more occurences of a .phi. function, and zero or more occurrences of a .mu. function. The .chi. function, .phi. function, and .mu. function are inserted for the virtual variables. The optimizer hashes a unique value number and creates a corresponding hash table entry for each variable version and each virtual variable remaining after renaming all zero versions. The optimizer also applies global value numbering to each basic block of the program.
REFERENCES:
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.
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., "Eficient 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 on 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., 1992, 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, Feb., 1994, pp. 105-114.
Cytron et al., "Efficiently Computing Static Single Assignment 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.
Chan Sun
Chow Frederick
Liu Shin-Ming
Lo Raymond
Streich Mark
Chaki Kakali
Silicon Graphics Inc.
LandOfFree
System and method to efficiently represent aliases and indirect 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 and method to efficiently represent aliases and indirect , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method to efficiently represent aliases and indirect will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2264040