Data processing: software development – installation – and managem – Software program development tool – Translation of code
Patent
1998-06-16
2000-10-03
Hafiz, Tariq R.
Data processing: software development, installation, and managem
Software program development tool
Translation of code
G06F 945
Patent
active
06128775&
ABSTRACT:
A method, system, and computer program product for performing register promotion, that optimizes placement of load and store operations of a computer program within a compiler. Based on the observation that the circumstances for promoting a memory location's value to register coincide with situations where the program exhibits partial redundancy between accesses to the memory location, the system is an approach to register promotion that models the optimization as two separate problems: (1) the partial redundancy elimination (PRE) of loads and (2) the PRE of stores. Both of these problems are solved through a sparse approach to PRE. The static single assignment PRE (SSAPRE) method for eliminating partial redundancy using a sparse SSA representation representations the foundation in eliminating redundancy among memory accesses, enabling the achievement of both computational and live range optimality in register promotion results. A static single use (SSU) representation is defined allowing the dual of the SSAPRE algorithm, called SSUPRE, to perform the partial redundancy elimination of stores. SSUPRE is performed after the PRE of loads, taking advantage of the loads' having been converted into pseudo-register references so that there are fewer barriers to the movement of stores. Consequently, the compiler produces more efficient, register-promoted executable program code from the SSA representation.
REFERENCES:
patent: 5327561 (1994-07-01), Choi et al.
patent: 5659754 (1997-08-01), Grove et al.
patent: 5768596 (1998-06-01), Chow et al.
Rosen et al. Global Value Numbers and Redundant Computations. ACM. pp. 12-27, Jan. 1988.
Gupta. Code Optimization as a Side Effect of Instruction Scheduling. High Performance Computing, Dec. 1997. Proceedings. Fourth International Conference. pp. 370-377.
Chow et al., "A New Algorithm for Partial Redundancy Elimination based on SSA Form", Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation, pp. 273-286, Jun. 1997.
Chow et al., "Effective Representation of Aliases and Indirect Memory Operations in SSA Form", Proceedings of the Sixth International Conference on Compiler Construction, pp. 253-267, Apr. 1996.
Chow, F. and J. Hennessy, "The Priority-Based Coloring Approach to Register Allocation", ACM Transactions on Programming Language and Systems, vol. 12, No. 4, pp. 501-536, Oct. 1990.
Cooper, K. and J. Lu, "Register Promotion in C Programs", Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation, pp. 308-319, Jun. 1997.
Dhamdhere, D., "Register Assignment Using Code Placement Techniques", Journal of Computer Languages, vol. 13, No. 2, pp. 75-93, 1988.
Dhamdhere, D., "A Usually Linear Algorithm For Register Assignment Using Edge Placement of Load and Store Instructions", Journal of Computer Languages, vol. 15, No. 2, pp. 83-94, 1990.
Knoop et al., "Partial Dead Code Elimination", Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pp. 147-158, Jun. 1994.
Chan Sun C.
Chow Frederick
Kennedy Robert
Liu Shin-Ming
Lo Raymond
Hafiz Tariq R.
Silicon Graphics Incorporated
Zhen Wei
LandOfFree
Method, system, and computer program product for performing regi does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, and computer program product for performing regi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and computer program product for performing regi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-206158