Register liveness analysis for SIMD architectures
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/44
G06F-009/45
출원번호
US-0075590
(2011-03-30)
등록번호
US-9015687
(2015-04-21)
발명자
/ 주소
George, Biju
Lueh, Guei-Yuan
출원인 / 주소
Intel Corporation
대리인 / 주소
Jordan IP Law, LLC
인용정보
피인용 횟수 :
4인용 특허 :
12
초록▼
Systems and methods of allocating physical registers to variables may involve identifying a partial definition of a variable in an inter-procedural control flow graph. A determination can be made as to whether to terminate a live range of the variable based at least in part on the partial definition
Systems and methods of allocating physical registers to variables may involve identifying a partial definition of a variable in an inter-procedural control flow graph. A determination can be made as to whether to terminate a live range of the variable based at least in part on the partial definition. Additionally, a physical register may be allocated to the variable based at least in part on the live range.
대표청구항▼
1. A method comprising: conducting a context-sensitive traversal of an inter-procedural control flow graph corresponding to vector-based executable code;identifying a partial definition of a variable in the inter-procedural control flow graph, wherein the partial definition is associated with a sing
1. A method comprising: conducting a context-sensitive traversal of an inter-procedural control flow graph corresponding to vector-based executable code;identifying a partial definition of a variable in the inter-procedural control flow graph, wherein the partial definition is associated with a single instruction multiple data execution context;identifying a strongly connected component status of an inter-procedural control flow graph block containing the partial definition;determining whether to terminate a live range of the variable based at least in part on the strongly connected component status, and whether the strongly connected component contains multiple entry loops, and whether the partial definition is a definition that does not use indirect addressing of the variable; andallocating a physical register to the variable based at least in part on the live range. 2. The method of claim 1, further including terminating the live range of the variable if the partial definition does not use indirect addressing of the variable and the partial definition is not within a strongly connected component containing multiple entry loops, wherein terminating the live range includes marking the partial definition as a first definition of the variable. 3. The method of claim 1, further including filtering out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block. 4. The method of claim 1, wherein conducting the context-sensitive traversal includes: traversing the inter-procedural control flow graph to identify first definitions;identifying a call block in the inter-procedural control flow graph, wherein the call block calls a subprogram;terminating traversal of the subprogram at an exit node of the subprogram; andusing return link information stored in the call block to resume traversal at a return node of the call block. 5. A method comprising: identifying a partial definition of a variable in an inter-procedural control flow graph;determining whether to terminate a live range of the variable based at least in part on the partial definition wherein the partial definition does not use indirect addressing of the variable;allocating a physical register to the variable based at least in part on the live range;identifying a strongly connected component status of an inter-procedural control flow graph block containing the partial definition;determining whether to terminate the live range of the variable based at least in part on the strongly connected component status and whether the strongly connected component contains multiple entry loops; andterminating the live range of the variable if the partial definition is a definition that does not use indirect addressing of the variable and the partial definition is not within a strongly connected component having multiple entry loops. 6. The method of claim 5, wherein terminating the live range includes marking the partial definition as a first definition of the variable. 7. The method of claim 5, further including filtering out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block. 8. The method of claim 5, further including a context-sensitive traversal of the inter-procedural control flow graph to identify a first definition. 9. The method of claim 8, wherein conducting the context-sensitive traversal includes: traversing the inter-procedural control flow graph to identify first definitions;identifying a call block in the inter-procedural control flow graph, wherein the call block calls a subprogram;terminating traversal of the subprogram at an exit node of the subprogram; andusing return link information stored in the call block to resume traversal at a return node of the call block. 10. The method of claim 5, further including computing at least one of a set of variables that may be defined by a function and a set of variables that may be used indirectly in a block. 11. The method of claim 5, wherein the partial definition is associated with a single instruction multiple data execution context in vector-based executable code. 12. A non-transitory computer readable storage medium comprising a set of instructions which, if executed by a processor, cause a computer to: identify a partial definition of a variable in an inter-procedural control flow graph;determine whether to terminate a live range of the variable based at least in part on the partial definition wherein the partial definition does not use indirect addressing of the variable;allocate a physical register to the variable based at least in part on the live range;identify a strongly connected component status of an inter-procedural control flow graph block containing the partial definition;determine whether to terminate the live range of the variable based at least in part on the strongly connected component status and whether the strongly connected component contains multiple entry loops; andterminate the live range of the variable if the partial definition is a definition that does not use indirect addressing of the variable and the partial definition is not within a strongly connected component having multiple entry loops. 13. The medium of claim 12, wherein the instructions, if executed, cause a computer to mark the partial definition as a first definition of the variable. 14. The medium of claim 12, wherein the instructions, if executed, cause a computer to filter out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block. 15. The medium of claim 12, wherein the instructions, if executed, cause a computer to conduct a context-sensitive traversal of the inter-procedural control flow graph to identify a first definition. 16. The medium of claim 15, wherein the instructions, if executed, cause a computer to: traversing the inter-procedural control flow graph to identify first definitions;identify a call block in the inter-procedural control flow graph, wherein the call block is to call a subprogram;terminate traversal of the subprogram at an exit node of the subprogram; anduse return link information stored in the call block to resume traversal at a return node of the call block. 17. The medium of claim 12, wherein the instructions, if executed, cause a computer to compute at least one of a set of variables that may be defined by a function and a set of variables that may be used indirectly in a block. 18. The medium of claim 12, wherein the partial definition is to be associated with a single instruction multiple data execution context in vector-based executable code. 19. A system comprising: a main processor;a graphics processor coupled to the main processor; anda non-transitory computer readable storage medium including a set of instructions which, if executed by the graphics processor, cause the system to,identify a partial definition of a variable in an inter-procedural control flow graph, wherein the partial definition is to be associated with a single instruction multiple data execution context in vector-based executable code;determine whether to terminate a live range of the variable based at least in part on the partial definition wherein the partial definition does not use indirect addressing of the variable;allocate a physical register to the variable based at least in part on the live range;identify a strongly connected component status of an inter-procedural control flow graph block containing the partial definition;determine whether to terminate the live of the variable based at least in part on the strongly connected component status and whether the strongly connected component contains multiple entry loops; andterminate the live range of the variable if the partial definition is a definition that does not use indirect addressing of the variable and the partial definition is not within a strongly connected component having multiple entry loops. 20. The system of claim 19, wherein the instructions, if executed, cause the system to mark the partial definition as a first definition of the variable. 21. The system of claim 19, wherein the instructions, if executed, cause the system to filter out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block. 22. The system of claim 19, wherein the instructions, if executed, cause the system to conduct a context-sensitive traversal of the inter-procedural control flow graph to identify the partial definition. 23. The system of claim 22, wherein the instructions, if executed, cause the system to: traversing the inter-procedural control flow graph to identify first definitions;identify a call block in the inter-procedural control flow graph, wherein the call block is to call a subprogram,terminate traversal of the subprogram at an exit node of the subprogram, and use return link information stored in the call block to resume traversal at a return node of the call block. 24. The system of claim 19, wherein the instructions, if executed, cause the system to compute at least one of a set of variables that may be defined by a function and a set of variables that may be used indirectly in a block.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (12)
Zhang,Junchao; Ju,Dz ching (Roy); Lian,Ruiqi; Lueh,Guei Yuan; Zhang,Zhaoqing, Bank assignment for partitioned register banks.
Bergner, Peter Edward; Prosser, Edward Curtis, Method and apparatus for allocating registers during code compilation using different spill strategies to evaluate spill cost.
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.
Aizikowitz Nava Arela,ILX ; Bar-Haim Roy,ILX ; Prosser Edward Curtis ; Roediger Robert Ralph ; Schmidt William Jon, Register allocation method and apparatus for truncating runaway lifetimes of program variables in a computer system.
Mizrahi, Noam; Mandler, Alberto; Koren, Shay; Friedmann, Jonathan, Run-time parallelization of code execution based on an approximate register-access specification.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.