# US 9,436,447 B2 · Technique for live analysis-based rematerialization to reduce register pressures and enhance parallelism > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,436,447 B2 - Document ID: US9436447B2 - Status: Granted - Kind: B2 - Application number: 13/669,401 - Filed: 2012-11-05 - Published: 2013-05-09 - Granted: 2016-09-06 - Earliest claimed: 2011-11-07 - Assignees: NVIDIA Corporation - Applicants: NVIDIA Corporation - Inventors: Xiangyun Kong; Jian-Zhong Wang; Yuan Lin; Vinod Grover - Web page: https://patentgrep.com/patent/US9436447B2 ## CPC - G06F 8/443: {Optimisation} - G06F 8/41: Compilation - G06F 8/433: {Dependency analysis; Data or control flow analysis} - G06F 8/45: {Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions} - G06F 8/456: {Parallelism detection} - G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)} - G06F 8/4442: {Reducing the number of cache misses; Data prefetching (cache prefetching G06F12/0862)} - G06F 8/445: {Exploiting fine grain parallelism, i.e. parallelism at instruction level (run-time instruction scheduling G06F9/3836)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A device compiler and linker within a parallel processing unit (PPU) is configured to optimize program code of a co-processor enabled application by rematerializing a subset of live-in variables for a particular block in a control flow graph generated for that program code. The device compiler and linker identifies the block of the control flow graph that has the greatest number of live-in variables, then selects a subset of the live-in variables associated with the identified block for which rematerializing confers the greatest estimated profitability. The profitability of rematerializing a given subset of live-in variables is determined based on the number of live-in variables reduced, the cost of rematerialization, and the potential risk of rematerialization. ## Claims ### Claim 1 A computer-implemented method for optimizing program code that is capable of being compiled for execution on a parallel processing unit (PPU), the method comprising: generating a control flow graph for the program code; identifying a first block in the control flow graph with the greatest number of live-in variables compared to other blocks in the control flow graph; estimating a profitability value for each of different subsets of live-in variables associated with the first block by performing a profitability analysis on each of the different subsets; selecting a first subset of live-in variables based on the first subset of live-in variables having the greatest profitability value compared to the profitability values associated with the other different subsets of live-in variables; and optimizing the program code by rematerializing the first subset of live-in variables into a second block in the control flow graph that is subsequent to the first block in the control flow graph, wherein the optimized program code is to be executed on the PPU. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the profitability analysis for a given subset of live-in variables is generated based on the number of live-in variables reduced by rematerializing the given subset of live-in variables into the second block in the control flow graph. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, wherein the profitability analysis for the given subset of live-in variables is further generated based on the number of instructions pulled into the second block of the control flow graph when rematerializing the given subset of live-in variables into the second block. ### Claim 4 (depends on 3) The computer-implemented method of claim 3, wherein the profitability analysis for the given subset of live-in variables is further generated based on the number of use-sites associated with rematerializing the given subset of live-in variables into the second block of the control flow graph. ### Claim 5 (depends on 4) The computer-implemented method of claim 4, wherein the profitability analysis for the given subset of live-in variables is further generated based on at least one of the cost of transferring the given subset of live-in variables from register memory to system memory and the cost of accessing the given subset of live-in variables within system memory. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, further comprising performing a data flow analysis on the program code to generate the control flow graph. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, further comprising iteratively optimizing the program code and estimating an amount of register pressure caused by executing the optimized program code within the PPU until the amount of register pressure caused by executing the program code within the PPU falls below a threshold value. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, further comprising: determining that rematerializing the first set of live-in variables makes available a set of registers in register memory; and allocating the set of registers to one or more threads configured to execute on the PPU. ### Claim 9 A non-transitory computer-readable medium storing program instructions that, when executed by a processing unit, cause the processing unit to optimize program code that is capable of being compiled for execution on a parallel processing unit (PPU) by performing the steps of: generating a control flow graph for the program code; identifying a first block in the control flow graph with the greatest number of live-in variables compared to other blocks in the control flow graph; estimating a profitability value for each of different subsets of live-in variables associated with the first block by performing a profitability analysis on each of the different subsets; selecting a first subset of live-in variables based on the first subset of live-in variables having the greatest profitability value compared to the profitability values associated with the other different subsets of live-in variables; and optimizing the program code by rematerializing the first subset of live-in variables into a second block in the control flow graph that is subsequent to the first block in the control flow graph, wherein the optimized program code is to be executed on the PPU. ### Claim 10 (depends on 9) The non-transitory computer-readable medium of claim 9, wherein the profitability analysis for a given subset of live-in variables is generated based on the number of live-in variables reduced by rematerializing the given subset of live-in variables into the second block in the control flow graph. ### Claim 11 (depends on 10) The non-transitory computer-readable medium of claim 10, wherein the profitability analysis for the given subset of live-in variables is further generated based on the number of instructions pulled into the second block of the control flow graph when rematerializing the given subset of live-in variables into the second block. ### Claim 12 (depends on 11) The non-transitory computer-readable medium of claim 11, wherein the profitability analysis for the given subset of live-in variables is further generated based on the number of use-sites associated with rematerializing the given subset of live-in variables into the second block of the control flow graph. ### Claim 13 (depends on 12) The non-transitory computer-readable medium of claim 12, wherein the profitability analysis for the given subset of live-in variables is further generated based on at least one of the cost of transferring the given subset of live-in variables from register memory to system memory and the cost of accessing the given subset of live-in variables within system memory. ### Claim 14 (depends on 9) The non-transitory computer-readable medium of claim 9, further comprising the step of performing a data flow analysis on the program code to generate the control flow graph. ### Claim 15 (depends on 9) The non-transitory computer-readable medium of claim 9, further comprising iteratively optimizing the program code and estimating an amount of register pressure caused by executing the optimized program code within the PPU until the amount of register pressure caused by executing the program code within the PPU falls below a threshold value. ### Claim 16 (depends on 9) The non-transitory computer-readable medium of claim 9, further comprising the steps of: determining that rematerializing the first set of live-in variables makes available a set of registers in register memory; and allocating the set of registers to one or more threads configured to execute on the PPU. ### Claim 17 A computing device configured to optimize program code that is capable of being compiled for execution on a parallel processing unit (PPU), including: a processing unit configured to: generate a control flow graph for the program code; identify a first block in the control flow graph with the greatest number of live-in variables compared to other blocks in the control flow graph; estimate a profitability value for each of different subsets of live-in variables associated with the first block by performing a profitability analysis on each of the different subsets; select a first subset of live-in variables based on the first subset of live-in variables having the greatest profitability value compared to the profitability values associated with the other different subsets of live-in variables; and optimize the program code by rematerializing the first subset of live-in variables into a second block in the control flow graph that is subsequent to the first block in the control flow graph, wherein the optimized program code is to be executed on the PPU. ### Claim 18 (depends on 17) The computing device of claim 17, further including: a memory unit coupled to the processing unit and storing program instructions that, when executed by the processing unit, cause the processing unit to: generate the control flow graph; identify the first block in the control flow graph; select the first subset of live-in variables; and optimize the program code by rematerializing the first subset of live-in variables into the second block in the control flow graph.