A system for optimizing computer code generation by carrying out interprocedural dead store elimination. The system carries out a top down traversal of a call graph in an intermediate representation of the code being compiled. Live on exit (LOE) sets are defined for variables at call points for func
A system for optimizing computer code generation by carrying out interprocedural dead store elimination. The system carries out a top down traversal of a call graph in an intermediate representation of the code being compiled. Live on exit (LOE) sets are defined for variables at call points for functions in the code being compiled. Bit vectors representing the LOE sets for call points for functions are stored in an LOE table indexed or hashed by call graph edges. For each function definition reached in the call graph traversal, a LOE set for the function itself is generated by taking the union of the LOE call point sets. The entries in the LOE table for the LOE call point sets are then removed. The LOE set for each function is used to determine if variables that are the subject of a store operation in a function may be subject to a dead store elimination optimization.
대표청구항▼
The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows: 1. A method for determining the correctness of a potential interprocedural dead store optimization for an optimizing compiler, the optimizing compiler generating an intermediate represent
The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows: 1. A method for determining the correctness of a potential interprocedural dead store optimization for an optimizing compiler, the optimizing compiler generating an intermediate representation of code to be compiled, including a call graph, the method comprising a top-down traversal of the call graph, and, for each procedure definition reached in the call graph traversal, further comprising: determining a live on exit set of interprocedural global variables for the reached procedure definition; determining a live on exit set of interprocedural global variables for each procedure call point within the reached procedure definition; storing the determined live on exit set of interprocedural global variables for each procedure call point in a live on exit data structure; and using the determined live on exit set of interprocedural global variables for the reached procedure definition to determine interprocedural global variables that are ineligible for interprocedural dead store elimination in the reached procedure definition. 2. The method of claim 1 in which the live on exit set of interprocedural global variables for the reached procedure definition is determined by taking the union of all stored entries in the live on exit data structure corresponding to call points for the reached procedure. 3. The method of claim 2 in which determining the live on exit set of interprocedural global variables for each procedure call point within the reached procedure definition comprises: determining a basic block live set for each block of computer code in a control flow graph for the reached procedure definition, the basic block live set comprising the variables used in the block of computer code and the variables used in any procedure called within the block of computer code; and determining the live on exit set of interprocedural global variables for each procedure call point by taking the union of the basic block live sets for all successor blocks to the block in the control flow graph containing the procedure call point, and adjusting the union to include uses of variables in the code between the call point for the procedure and the end of the block containing the call point. 4. The method of claim 1 in which determining the live on exit set for each procedure call point in the reached procedure definition comprises: determining a basic block live set for each block of computer code in a control flow graph for the reached procedure definition, the basic block live set comprising the variables used in the block of computer code and the variables used in any procedure called within the block of computer code; and determining the live on exit set for each procedure call point by taking the union of the basic block live sets for all successor blocks to the block in the control flow graph containing the procedure call point, and adjusting the union to include uses of variables in the code between the call point for the procedure and the end of the block containing the call point. 5. The method of claim 2, further comprising, after determining the live on exit set of interprocedural global variables for the reached procedure definition, removing all entries in the live on exit data structure corresponding to call points for the reached procedure. 6. The method of claim 3, in which the variables used in a procedure called within a block of computer code are determined by accessing the mod/use set for the procedure associated with the procedure definition node in the call graph. 7. The method of claim 1 in which using the live on exit set of interprocedural global variables for the reached procedure definition to determine the variables that are ineligible for interprocedural dead store elimination in the reached procedure definition comprises generating pseudo uses of the members of the live on exit set of interprocedural global variables for the reached procedure definition in the data flow graph for the reached procedure definition. 8. The method of claim 1 in which the live on exit data structure comprises bit vector entries and is indexed by call graph edges. 9. The method of claim 2 further comprising using the live on exit set of interprocedural global variables for the reached procedure definition to determine whether the reached procedure definition may be cloned by the optimizing compiler. 10. A method for determining the correctness of a potential interprocedural dead store optimization for an optimizing compiler, the optimizing compiler generating an intermediate representation of code to be compiled, including a call graph, the method comprising a top-down traversal of the call graph, and, for each procedure definition reached in the call graph traversal, further comprising: determining a live on exit set of interprocedural global variables for each procedure call point within the reached procedure definition by: determining a basic block live set for each block of computer code in a control flow graph for the reached procedure definition, the basic block live set comprising the interprocedural global variables used in the block of computer code and the interprocedural global variables used in any procedure called within the block of computer code; and determining the live on exit set of global variables for each procedure call point by taking the union of the basic block live sets for all successor blocks to the block in the control flow graph containing the procedure call point, and adjusting the union to include uses of interprocedural global variables in the code between the call point for the procedure and the end of the block containing the call point; storing the determined live on exit set of interprocedural global variables for each procedure call point in a live on exit data structure comprising a bit vector indexed by a call graph edge; determining a live on exit set of interprocedural global variables for the reached procedure definition by taking the union of all stored entries in the live on exit data structure corresponding to call points for the reached procedure; removing all entries in the live on exit data structure corresponding to call points for the reached procedure; and using the live on exit set of interprocedural global variables for the reached procedure definition to determine interprocedural global variables that are ineligible for interprocedural dead store elimination in the reached procedure definition. 11. A computer program product for the compilation of computer code, the computer program product comprising a computer usable medium having computer readable code means embodied in said medium, comprising computer readable program code means to carry out the method of claim 1. 12. An optimizing compiler comprising: means for generating an intermediate representation of computer code, the intermediate representation comprising a call graph; means for traversing the call graph in top down order; means for storing a live on exit data structure; means far generating a record in the live on exit data structure for each procedure call encountered in the traversal of the call graph, the record comprising data representing interprocedural global variables that are live at the point of the procedure call; and means for calculating the live on exit set for a procedure definition reached in traversing the call graph, wherein the means for calculating the live on exit set comprises means for retrieving records from the live on exit data structure corresponding to the reached procedure definition, means for performing a union of the records to determine the live on exit set for the reached procedure definition, and means for signaling the availability of a dead store elimination optimization for a store operation contained in the reached procedure definition based on the live on exit set calculated for the procedure definition. 13. The optimizing compiler of claim 12, further comprising means for removing records associated wit the reached procedure definition from the live on exit data structure following calculation of the live on exit set for the reached procedure definition. 14. A component for determining the correctness of a potential interprocedural dead store optimization for an optimizing compiler, the optimizing compiler generating an intermediate representation of code to be compiled, including a call graph, the component comprising: means to traverse the call graph in top-down order, means for determining a live on exit set of interprocedural global variables for each procedure call point within a reached procedure definition during the call graph traversal by: determining a basic block live set for each block of computer code in a control flow graph for the reached procedure definition, the basic block live set comprising the interprocedural global variables used in the block of computer code and the interprocedural global variables used in any procedure called within the block of computer code, and determining the live on exit set for each procedure call by taking the union of the basic block live sets for all successor blocks to the block in the control flow graph containing the procedure call point and by adjusting the union to include uses of interprocedural global variables in the code between the call point for the procedure and the end of the block containing the call point, means for storing the live on exit set of interprocedural global variables for each procedure call point in an entry in a live on exit data structure comprising a bit vector indexed by a call graph edge, means for determining a live on exit set of interprocedural global variables for the reached procedure determination by talking the union of all stored entries in the live on exit data structure corresponding to call points for the reached procedure, means for removing all entries in the live on exit data structure corresponding to call points for the reached procedure following determination of the live on exit set of interprocedural global variables for the reached procedure definition, and means for determining the interprocedural global variables that are ineligible for interprocedural dead store elimination in the reached procedure definition, using the live on exit set of interprocedural global variables for the reached procedure definition. 15. The method of claim 1, further comprising determining variables, other than variables determined to be ineligible for interprocedural dead store elimination, to be eligible for interprocedural dead store elimination. 16. The method of claim 15, further comprising eliminating the variables determined to be eligible for interprocedural dead store elimination. 17. The method of claim 10, further comprising determining variables, other than variables determined to be ineligible for interprocedural dead store elimination, to be eligible for interprocedural dead store elimination. 18. The meted of claim 17, further comprising eliminating the variables determined to be eligible for interprocedural dead store elimination.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (15)
Van Dyke Don A. (Pleasanton CA) Cramer Timothy J. (Pleasanton CA) Rasbold James C. (Livermore CA) O\Hair Kelly T. (Livermore CA) Cox David M. (Livermore CA) Seberger David A. (Livermore CA) O\Gara Li, Computer with integrated hierarchical representation (IHR) of program wherein IHR file is available for debugging and op.
Odnert Daryl (Boulder Creek CA) Santhanam Vatsa (Sunnyvale CA), Method and apparatus for compiling computer programs with interprocedural register allocation.
Odnert Daryl (Boulder Creek CA) Santhanam Vatsa (Sunnyvale CA), Method and apparatus for compiling computer programs with interproceduural register allocation.
Sreedhar Vugranam C. ; Ju Dz-ching ; Gillies David Mitford ; Santhanam Vatsa, Method and system for eliminating phi instruction resource interferences and redundant copy instructions from static-single-assignment-form computer code.
Jong-Deok Choi ; Manish Gupta ; Mauricio J. Serrano ; Vugranam C. Sreedhar ; Samuel Pratt Midkiff, Method for optimizing creation and destruction of objects in computer programs.
Bradley Alan C. (Portland OR) Vegdahl Steven R. (Beaverton OR) Adams Norman I. (Portland OR), Method for reducing memory allocations and data copying operations during program calling sequences.
Spix George A. (Eau Claire WI) Wengelski Diane M. (Eau Claire WI) Hawkinson Stuart W. (Eau Claire WI) Johnson Mark D. (Eau Claire WI) Burke Jeremiah D. (Eau Claire WI) Thompson Keith J. (Eau Claire W, System and method for controlling a highly parallel multiprocessor using an anarchy based scheduler for parallel executi.
Burke Michael G. (Yonkers NY) Carini Paul R. (Sherman CT) Choi Jong-Deok (Mount Kisco NY), Using program call graphs to determine the maximum fixed point solution of interprocedural bidirectional data flow probl.
Poznanovic, Daniel; Hammes, Jeffrey; Krause, Lisa; Steidel, Jon; Barker, David; Brooks, Jeffrey Paul, Process for converting programs in high-level programming languages to a unified executable for hybrid computing platforms.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.