Patent Description:
In order for program source code to be executed by a computer, the program source code undergoes a compiling process that translates the program source code into machine code that is recognizable by the computer. During the compiling process, various compiler optimizations may be performed on the program source code. For example, compiler optimizations may be implemented by applying a sequence of optimizing transformations to an input function/program to produce a semantically equivalent output program that uses fewer resources and/or executes faster. Such compiler optimizations may optimize one or more of a program's execution time, memory requirement, and/or power consumption as examples.

<CIT> describes techniques for live analysis-based rematerialization to reduce register pressures and enhance parallelism.

Examples are disclosed herein that relate to performing rematerialization operation(s) on program source code to reduce a register pressure at a boundary of a basic block of the program source code prior to performing instruction scheduling on the program source code. In one example, a method performed by a computer includes, prior to performing instruction scheduling on program source code, for each basic block of a plurality of basic blocks of the program source code, determining a register pressure at a boundary of the basic block, determining whether the register pressure at the boundary of the basic block is greater than a target register pressure, based on the register pressure at the boundary of the basic block being greater than the target register pressure, identifying one or more candidate instructions in the basic block suitable for rematerialization to reduce the register pressure at the boundary of the basic block, and performing a rematerialization operation on at least one of the one or more candidate instructions to reduce the register pressure at the boundary of the basic block to be less than the target register pressure.

The invention relates to a method and a computing system as set forth in the claims. It will be understood that aspects falling outside the scope of the claims may not be part of the invention but may be useful to understand the invention.

During the compiling process, various compiler optimizations may be performed on the program source code. For example, such compiler optimizations may optimize one or more of a program's execution time, memory requirement, and/or power consumption. However, such optimizations can create other issues. As one example, live ranges of variables (i.e., a time in which a variable is stored in a register) in the program can be increased as a result of performing compiler optimizations. As another example, such optimizations may create many new variables in the program that collectively increase register pressure (i.e., a number of live variables relative to a number of available registers to store the variables) and result in spills to memory during register allocation. Such spills to memory may reduce processing performance when the complied machine code is processed by a computing system. Additionally, local per-block instruction scheduling performed before register allocation may have a significant impact on register pressure. For example, in a case where the input code for instruction scheduling has unbalanced cross-block register pressure, instruction scheduling may generate scheduling results which cause additional spills to memory.

Accordingly, examples are disclosed herein that relate to, during a compiling process performed on program source code, performing rematerialization operations to balance cross-block register pressure prior to instruction scheduling. Such cross-block rematerialization may optimize the basic blocks of the source code prior to instruction scheduling such that instruction scheduling may be performed more efficiently (i.e., to produce fewer spills to memory). The resulting compiled code may be executed by a computing system with increased processing performance due to the reduced number of memory write operations as a result of the fewer spills to memory.

<FIG> shows an example computer <NUM> in simplified form. The computer <NUM> may include one or more graphics processing units (GPUs) <NUM> each having a highly parallel structure that allows for efficient processing of large blocks of data in parallel. In the illustrated example, the computer <NUM> is shown with a plurality of GPUs. The plurality of GPUs <NUM> may take any suitable form. For example, a GPU can be present on a video card or embedded on a motherboard (along with a central processing unit (CPU) in some cases). Each of the plurality of GPUs <NUM> may include a plurality of registers <NUM>. Each of the registers <NUM> may temporarily store values corresponding to different variable during execution of code by the plurality of GPUs <NUM>.

Each of the plurality of GPUs <NUM> may be configured to execute a plurality of shaders <NUM>. The plurality of shaders <NUM> may be arranged in a processing pipeline that is well suited for parallel processing. Each of the plurality of shaders <NUM> may be configured to perform a variety of specialized functions, such as applying transformations to a large set of elements at a time. For example, shaders may apply transformations to each pixel in an area of a display. As another example, shaders may apply transformations to vertices of a model. The plurality of shaders <NUM> may take any suitable form. Examples of different shaders that may be executed by the plurality of GPUs <NUM> include pixel shaders, vertex shaders, geometry shaders, and compute shaders.

The computer <NUM> is configured to execute a compiler <NUM> that is configured to compile source code <NUM> from a higher-level programing language into a lower-level language - e.g., into machine code <NUM> that is processable by the shaders <NUM> of the GPUs <NUM>. The source code <NUM> may take any suitable form, including any suitable programing language. For example, the source code <NUM> may be executed to instantiate software programs including individual or groups of executable files, data files, libraries, drivers, scripts, database records, or other suitable forms of code.

The source code <NUM> may be organized according to a plurality of basic blocks <NUM>. Each basic block of the plurality of basic blocks <NUM> may include a sequence of instructions that may be executed without a conditional instruction, such as a jump, branch, or interrupt. In other words, an occurrence of a conditional instruction may create a boundary between different basic blocks.

The compiler <NUM> may be configured to perform a series of operations to compile the source code <NUM> into the machine code <NUM>. As part of the compiling process, the compiler <NUM> may be configured to verify syntax and semantics of the source code according to a specific source language. Such verification may include performing lexical analysis, syntax analysis, and/or semantic analysis.

The compiler <NUM> further may be configured to transform the source code <NUM> into an intermediate representation (IR) for further processing. The IR may be a lower-level representation of the program with respect to the source code. The compiler <NUM> may be configured to perform optimizations on the IR that are independent of the computer architecture being targeted. This source code/machine code independence may enable generic optimizations to be shared between versions of the compiler supporting different languages and target processors. Example optimizations may include removal of useless code (dead code elimination) or unreachable code (reachability analysis), discovery and propagation of constant values (constant propagation), relocation of computation to a less frequently executed place (e.g., out of a loop), or specialization of computation based on the context. The compiler <NUM> may be configured to perform optimization on the IR to produce an optimized IR. The compiler <NUM> may be configured to take the optimized IR and perform analysis, transformations and optimizations that are specific for the target computer architecture of the computer <NUM>. The compiler <NUM> further may be configured to perform instruction scheduling, which re-orders instructions to keep parallel execution units busy by filling delay slots in the processing pipeline. The compiler <NUM> may be configured to generate target-dependent assembly code, performing register allocation in the process. The compiler <NUM> may be configured to compile the assembly code into machine code and output the machine code <NUM> to the plurality of GPUs <NUM> for processing.

The compiler <NUM> may be configured to perform various optimizations through the compiling process of translating the source code <NUM> into the machine code <NUM>. For example, the compiler <NUM> may be configured to optimize one or more of a program's execution time, memory requirement, and/or power consumption. Compiler optimization may be implemented by applying a sequence of optimizing transformations to an input function/program to produce a semantically equivalent output program that uses fewer resources and/or executes faster. Such optimizations often focus on eliminating redundant computations. However, such optimizations can increase the live ranges of variables (i.e., a time in which a variable is stored in a register). Also, such optimizations may create many new variables that collectively increase register pressure and result in spills to memory during register allocation. Such spills to memory may reduce processing performance when the complied machine code <NUM> is processed by the shaders <NUM> of the plurality of GPUs <NUM>. Moreover, local per-block instruction scheduling performed before register allocation may have a significant impact on register pressure. For example, in a case where the input for instruction scheduling has unbalanced cross-block register pressure, instruction scheduling will generate scheduling results which cause additional spills to memory.

Thus, the compiler <NUM> may be configured to selectively perform rematerialization operations to balance cross-block register pressure prior to instruction scheduling. Such cross-block rematerialization may optimize the basic blocks of the source code prior to instruction scheduling such that instruction scheduling may be performed more efficiently (i.e., to produce fewer spills to memory) that increases shader performance. Rematerialization operations can decrease register pressure by increasing the amount of computations performed while reduce a number of registers being used in a particular basic block of code.

The compiler <NUM> may be configured to perform the rematerialization operations prior to instruction scheduling in order to provide basic blocks having reduced register pressure that allow for scheduling results to have reduced memory latency (e.g., due to fewer spills to memory). In this way, the compiled code may be processed by the GPUs <NUM> more efficiently.

Rematerialization may be tightly integrated with register allocation that is performed after instruction scheduling, where rematerialization is used as an alternative to spilling registers to memory. In scenarios where rematerialization is only performed at register allocation, instruction scheduling that is performed prior to register allocation may have inaccurate cross-block register pressures as well as inaccurate intra-block register pressures. By performing rematerialization before instruction scheduling (and also optionally after instruction scheduling), the input code provided for instruction scheduling may have balanced cross-block register pressure that helps the instruction scheduling process generate scheduling results with low register pressure. Moreover, performing cross-block rematerialization prior to instruction scheduling to help lower register pressure may have a lower processing cost as compared to performing global instruction scheduling.

<FIG> shows different example modules of the compiler <NUM> that may be configured to perform different operations during the compiling process to produce optimized compiled code. The compiler <NUM> includes a register pressure determination module <NUM>, a rematerialization operation module <NUM>, an instruction scheduling module <NUM>, and a register allocation module <NUM>. Note that the compiler <NUM> may include additional modules (not shown) that perform other compiling operations.

The register pressure determination module <NUM> is configured to determine the register pressures at the boundaries of each of the plurality of basic blocks <NUM> of the source code <NUM> (or an optimized IR version of the source code) prior to instruction scheduling. The boundaries of a basic block include the first and last instruction of the basic block. The register pressure determination module <NUM> determines the register pressures at just the boundaries of the basic blocks, because the register pressures of other instructions in the middle of the basic blocks may be inaccurate since instruction scheduling has not yet been performed. The register pressure determination module <NUM> may determine the register pressures at the boundaries of the basic block in any suitable manner using any suitable algorithm. For example, the register pressure determination module <NUM> may determine the register pressures based on liveness parameters of variable used by the instructions at the boundaries of the basic blocks.

The rematerialization operation module <NUM> may be configured to identify basic blocks of the plurality of basic blocks <NUM> that have a register pressure at a boundary that is greater than a target register pressure. The rematerialization operation module <NUM> may be configured to, for each basic block having a register pressure at a boundary that is greater than the target register pressure, identify one or more candidate instructions in the basic block that are suitable for rematerialization to help reduce register pressure. The rematerialization operation module <NUM> may scan each instruction in a basic block to identify candidate instruction(s). The rematerialization operation module <NUM> may identify candidate instruction(s) in any suitable manner. For example, the rematerialization operation module <NUM> identify a candidate instruction based on the instruction having redundant variables that would potentially occupy additional registers. Additionally, the rematerialization operation module <NUM> may be configured to verify that an output of an instruction is not provided as input to another instruction in the basic block in order for that instruction to be considered as a candidate instruction. In other words, none of the candidate instructions in a basic block may comprise an output that is provided as an input to another instruction in the same basic block.

In some cases, no instructions in a particular basic block may qualify as candidates for rematerialization operations. In such cases, the rematerialization operation module <NUM> may not perform any rematerialization operations on the particular basic block, and instead may move to the next basic block in the code.

The rematerialization operation module <NUM> further may be configured to, for each basic block having candidate instruction(s), perform one or more rematerialization operations on one or more candidate instructions to help reduce register pressure of the basic block. In some examples, one or more rematerialization operations may be cross-block rematerialization operations where an instruction is moved from one basic block to another basic block. In some examples, the rematerialization operation module <NUM> may be configured to iteratively perform rematerialization operations on different instructions until the register pressure of the basic block is less than the target register pressure.

The rematerialization operation module <NUM> may be configured to perform any suitable rematerialization operation on a candidate instruction to reduce register pressure. Example rematerialization operations may include move operations and clone operations. An example rematerialization operation where a redundant variable is replaced is shown in the pseudo code below.

<IMG>
In this example, the variable c is equivalent to a+b. The rematerialization operation replaces the instances of the variable c with a+b in order to open a register that would otherwise hold the variable c. In this way, the rematerialization operation may reduce register pressure in the basic block.

An example rematerialization operation where a variable is moved is shown in the pseudo code below.

<IMG>
In this example, the value s is instantiated prior to the conditional if statement, such that s lives (i.e., occupies a register) across the if statement. The rematerialization operation moves the instruction that instantiates value s, such that the instruction is executed after the conditional if statement has concluded. The rematerialization operation makes a register available during the conditional if statement that would have otherwise been occupied by the value s. In this way, the rematerialization operation may reduce register pressure in the basic block.

The rematerialization operation module <NUM> may be configured to perform any suitable number of rematerialization operations on any suitable number of instructions in different basic block of the code to reduce register pressure.

The instruction scheduling module <NUM> may be configured to perform instruction scheduling by selectively rearranging the order in which instructions are executed in order to improve instruction-level parallelism, which may improve performance of the GPUs <NUM> when executing the compiled machine code <NUM>. For example, the instruction scheduling module <NUM> may be configured to rearrange the order of instructions to avoid pipeline stalls. As another example, the instruction scheduling module <NUM> may be configured to rearrange the order of instructions to avoid illegal or semantically ambiguous operations (e.g., relating to pipeline timing issues or non-interlocked resources). The instruction scheduling module <NUM> may be configured to perform instruction scheduling in any suitable manner. In the examples discussed herein, instruction scheduling is performed prior to register allocation. In other examples, instruction scheduling may be performed after register allocation or both before and after register allocation.

The register allocation module <NUM> may be configured to assign target variables of the code onto the registers <NUM> of the GPUs <NUM>. For example, the register allocation module <NUM> may be configured to perform register allocation over a basic block (i.e., local register allocation), over a whole function/procedure (i.e., global register allocation), or across function boundaries. The compiler <NUM> may be configured to generate target-dependent assembly code, performing register allocation in the process via the register allocation module <NUM>. Further, the compiler <NUM> may be configured to compile the assembly code into machine code and output the machine code <NUM> to the plurality of GPUs <NUM> for processing.

<FIG> is a flowchart of an example method <NUM> for performing rematerialization prior to instruction scheduling to help reduce register pressure. For example, the method <NUM> may be performed by the compiler <NUM> shown in <FIG> and <FIG>.

At <NUM>, prior to performing instruction scheduling on the program source code, for each basic block of a plurality of basic blocks of the program source code, register pressures are determined at the boundaries of the basic block. For example, the register pressures may be determined by the register pressure determination module <NUM> of the compiler <NUM> shown in <FIG>.

Next, at <NUM>, method <NUM> moves to a next basic block to be analyzed of the plurality of basic blocks of the program source code. At <NUM>, it is determined whether a register pressure at a boundary of the basic block is greater than a target register pressure. For example, the register pressures analysis may be performed by the rematerialization operation module <NUM> of the compiler <NUM> shown in <FIG>. If a register pressure at a boundary of the basic block is greater than the target register pressure, then the method <NUM> moves to <NUM>. Otherwise, the method <NUM> moves to <NUM> to determine whether rematerialization analysis has been performed on all basic blocks of the program source code.

At <NUM>, it is determined whether one or more candidate instructions in the basic block suitable for rematerialization to reduce register pressure can be identified. In some implementations, at <NUM>, such identifying may include verifying that an instruction does not have any intra-block dependencies where an output of the instruction is provided as input to another instruction in the basic block.

If one or more candidate instructions are identified, then at <NUM>, the one or more rematerialization operations that may be performed on the one or more corresponding candidate instructions are saved. In some examples, at <NUM>, the rematerialization operation(s) optionally may include a move operation. Further, in some examples, at <NUM>, the rematerialization operation(s) optionally may include a clone operation. For example, the rematerialization operation(s) may be saved by the rematerialization operation module <NUM> of the compiler <NUM> shown in <FIG>. In some examples, where multiple candidate instructions are identified, one or more rematerialization operations that are identified to have a relatively larger beneficial effect on register pressure may be saved preferentially over one or more rematerialization operations that are identified to have a relatively smaller beneficial effect on register pressure.

If no candidate instructions are identified that can reduce the register pressure to less than the target register pressure, then the method <NUM> moves to <NUM>, and instruction scheduling is performed without performing any rematerialization operations prior to performing instruction scheduling.

At <NUM>, updated register pressures at the boundaries of the basic block may be determined based on the saved rematerialization operation(s) theoretically being performed on the corresponding candidate instruction(s). Further, at <NUM>, it is determined whether rematerialization analysis has been performed on all basic blocks of the plurality of basic blocks of the program source code. If all basic block have been analyzed, then the method <NUM> moves to <NUM>. Otherwise, the method <NUM> returns to <NUM> and rematerialization analysis is performed on a next basic block of the plurality of basic blocks of the program source code. At <NUM>, rematerialization operations are performed on any identified candidate instructions in the plurality of basic blocks to help reduce register pressure. In some examples, at <NUM>, the rematerialization operation(s) optionally may include a move operation. Further, in some examples, at <NUM>, the rematerialization operation(s) optionally may include a clone operation. For example, the rematerialization operation(s) may be performed by the rematerialization operation module <NUM> of the compiler <NUM> shown in <FIG>.

In some examples, multiple rematerialization operations may be performed on candidate instructions to collectively reduce register pressure at the boundary of the basic block to be less than the target register pressure. In some examples, rematerialization operations that are identified to have a relatively larger beneficial effect on register pressure may be performed preferentially over one or more rematerialization operations that are identified to have a relatively smaller beneficial effect on register pressure. Generally, rematerialization operations may be selected such that a minimum number of rematerialization operations are performed to reduce register pressure at the boundary of the basic block to be less than the target register pressure.

At <NUM>, once rematerialization operations have been performed on identified candidate instructions in applicable basic blocks of the program source code to help reduce register pressure or no candidate instructions are identified, instruction scheduling is performed on the program source code. For example, instruction scheduling may be performed on the program source code by the instruction scheduling module <NUM> of the compiler <NUM> shown in <FIG>.

The above described method may be performed to optimize the basic blocks of the source code prior to instruction scheduling such that instruction scheduling may be performed more efficiently (i.e., to produce fewer spills to memory). The resulting compiled code may be executed by a computing system with increased processing performance due to the reduced number of memory write operations as a result of the fewer spills to memory.

In some implementations, the methods and processes described herein may be tied to a computing system of one or more computing devices.

<FIG> schematically shows a simplified representation of a computing system <NUM> configured to provide any to all of the compute functionality described herein. Computing system <NUM> may take the form of one or more of personal computers, network-accessible server computers, tablet computers, home-entertainment computers, gaming devices, mobile computing devices, mobile communication devices (e.g., smart phone), virtual/augmented/mixed reality computing devices, wearable computing devices, Internet of Things (IoT) devices, embedded computing devices, and/or other computing devices. As one example, the computing system <NUM> may take the form of the computer <NUM> shown in <FIG>.

Computing system <NUM> includes a logic subsystem <NUM> and a storage subsystem <NUM>. Computing system <NUM> may optionally include a display subsystem <NUM>, input subsystem <NUM>, communication subsystem <NUM>, and/or other subsystems not shown in <FIG>.

Logic subsystem <NUM> includes one or more physical devices configured to execute instructions. For example, the logic subsystem <NUM> may be configured to execute instructions that are part of one or more applications, services, or other logical constructs. The logic subsystem <NUM> may include one or more hardware processors configured to execute software instructions. Additionally or alternatively, the logic subsystem <NUM> may include one or more hardware or firmware devices configured to execute hardware or firmware instructions. Processors of the logic subsystem <NUM> may be single-core or multi-core, and the instructions executed thereon may be configured for sequential, parallel, and/or distributed processing. Individual components of the logic subsystem <NUM> optionally may be distributed among two or more separate devices, which may be remotely located and/or configured for coordinated processing. Aspects of the logic subsystem <NUM> may be virtualized and executed by remotely accessible, networked computing devices configured in a cloud-computing configuration.

Storage subsystem <NUM> includes one or more physical devices configured to temporarily and/or permanently hold computer information such as data and instructions executable by the logic subsystem <NUM>. When the storage subsystem <NUM> includes two or more devices, the devices may be collocated and/or remotely located. Storage subsystem <NUM> may include volatile, nonvolatile, dynamic, static, read/write, read-only, random-access, sequential-access, location-addressable, file-addressable, and/or content-addressable devices. Storage subsystem <NUM> may include removable and/or built-in devices. When the logic subsystem <NUM> executes instructions, the state of storage subsystem <NUM> may be transformed - e.g., to hold different data.

The logic subsystem <NUM> and the storage subsystem <NUM> may cooperate to instantiate one or more logic machines. As used herein, the term "machine" is used to collectively refer to the combination of hardware, firmware, software, instructions, and/or any other components cooperating to provide computer functionality. In other words, "machines" are never abstract ideas and always have a tangible form. A machine may be instantiated by a single computing device, or a machine may include two or more sub-components instantiated by two or more different computing devices. In some implementations a machine includes a local component (e.g., software application executed by a computer processor) cooperating with a remote component (e.g., cloud computing service provided by a network of server computers). The software and/or other instructions that give a particular machine its functionality may optionally be saved as one or more unexecuted modules on one or more suitable storage devices.

Claim 1:
A method performed by a computer, the method comprising:
prior to performing instruction scheduling on program source code, for each basic block of a plurality of basic blocks of the program source code,
determining (<NUM>) a register pressure at a boundary of the basic block; determining (<NUM>) whether the register pressure at the boundary of the basic block is greater than a target register pressure;
based on the register pressure at the boundary of the basic block being greater than the target register pressure, performing (<NUM>) analysis to identify one or more candidate instructions in the basic block suitable for rematerialization to reduce the register pressure at the boundary of the basic block; and
performing (<NUM>) a rematerialization operation on at least one of the one or more candidate instructions to reduce the register pressure at the boundary of the basic block to be less than the target register pressure.