Patent Description:
<CIT> Al (Advanced Micro Devices, Inc. ) relates to combined world-space pipeline shader stages. Also acknowledged are a paper by <NPL> and "<NPL>.

Techniques for improving memory utilization for communication between pipeline stages of a graphics processing pipeline are disclosed. The techniques include identifying shader programs for analysis. Such shader programs are identified by at least two shader programs where one (a first shader program) outputs data used by another (a second shader program). A compiler analyzes the output instructions of the first shader program to determine whether any such output instructions output any data that is not input by the second shader program. If one or more of such instructions exist, the compiler identifies the data points that are output by the first shader program and input by the second shader program, and avoids generating memory writes that write data points that are output by the first shader program but not input by the second shader program. If memory writes for the first shader program would lead to "gaps," in the data that is output, then the compiler modifies the memory writes to remove such gaps by using a packed format. This gap removal reduces the memory footprint and also, by aggregating multiple originally separated memory writes or reads into fewer memory access instructions, reduces the number of memory access instructions that are executed. Overall, these modifications result in fewer memory accesses, a smaller memory footprint, and increased effective bandwidth.

One particular part of the graphics pipeline for which this analysis is useful is in the part of the pipeline that implements tessellation, which includes the hull shader stage and the domain shader stage. Specifically, the hull shader outputs data, such as control points and patch constants (such as tessellation factors) for use by the domain shader. This data is typically output to a general purpose memory which is used for things other than tessellation. The hull shader includes instructions that each outputs multiple items of data (e.g., multiple control points, multiple tessellation factors). Further, hull shaders are generalizable, with multiple domain shaders typically being written to be used with a single hull shader. Thus it is common for hull shaders to output data not used by some domain shaders. Hull shaders are also able to know whether a patch will be culled based on computed tessellation factor values at runtime, and hull shaders thus know whether data for whole patches are used by the domain shader. The techniques described herein would be helpful to reduce the memory footprint and memory accesses of the data transferred from the hull shader to the domain shader.

<FIG> is a block diagram of an example device <NUM> in which one or more aspects of the present disclosure are implemented. The device <NUM> includes, for example, a computer, a gaming device, a handheld device, a set-top box, a television, a mobile phone, or a tablet computer. The device <NUM> includes a processor <NUM>, a memory <NUM>, a storage device <NUM>, one or more input devices <NUM>, and one or more output devices <NUM>. The device <NUM> also optionally includes an input driver <NUM> and an output driver <NUM>. It is understood that the device <NUM> may include additional components not shown in <FIG>.

The processor <NUM> includes a central processing unit (CPU), a graphics processing unit (GPU), a CPU and GPU located on the same die, or one or more processor cores, wherein each processor core may be a CPU or a GPU. The memory <NUM> is located on the same die as the processor <NUM>, or may be located separately from the processor <NUM>. The memory <NUM> includes a volatile or non-volatile memory, for example, random access memory (RAM), dynamic RAM, or a cache.

The storage device <NUM> includes a fixed or removable storage, for example, a hard disk drive, a solid state drive, an optical disk, or a flash drive. The input devices <NUM> include a keyboard, a keypad, a touch screen, a touch pad, a detector, a microphone, an accelerometer, a gyroscope, a biometric scanner, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE <NUM> signals). The output devices <NUM> include a display, a speaker, a printer, a haptic feedback device, one or more lights, an antenna, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE <NUM> signals).

The input driver <NUM> communicates with the processor <NUM> and the input devices <NUM>, and permits the processor <NUM> to receive input from the input devices <NUM>. The output driver <NUM> communicates with the processor <NUM> and the output devices <NUM>, and permits the processor <NUM> to send output to the output devices <NUM>. The output driver <NUM> includes an accelerated processing device (APD) <NUM> which is coupled to a display device <NUM>. The APD is configured to accept compute commands and graphics rendering commands from processor <NUM>, to process those compute and graphics rendering commands, and to provide pixel output to display device <NUM> for display.

The APD <NUM> includes one or more parallel processing units configured to perform computations in accordance with a single-instruction-multiple-data ("SIMD") paradigm. However, functionality described as being performed by the APD <NUM> may also be performed by processing devices that do not process data in accordance with a SIMD paradigm.

<FIG> is a block diagram of the device <NUM>, illustrating additional details related to execution of processing tasks on the APD <NUM>. The processor <NUM> maintains, in system memory <NUM>, one or more control logic modules for execution by the processor <NUM>. The control logic modules include an operating system <NUM>, a driver <NUM>, and applications <NUM>, and may optionally include other modules not shown. These control logic modules control various aspects of the operation of the processor <NUM> and the APD <NUM>. For example, the operating system <NUM> directly communicates with hardware and provides an interface to the hardware for other software executing on the processor <NUM>. The driver <NUM> controls operation of the APD <NUM> by, for example, providing an application programming interface ("API") to software (e.g., applications <NUM>) executing on the processor <NUM> to access various functionality of the APD <NUM>. The driver <NUM> also includes a just-in-time compiler that compiles shader code into shader programs for execution by processing components (such as the SIMD units <NUM> discussed in further detail below) of the APD <NUM>.

The APD <NUM> executes commands and programs for selected functions, such as graphics operations and non-graphics operations, which may be suited for parallel processing. The APD <NUM> can be used for executing graphics pipeline operations such as pixel operations, geometric computations, and rendering an image to display device <NUM> based on commands received from the processor <NUM>. The APD <NUM> also executes compute processing operations that are not directly related to graphics operations, such as operations related to video, physics simulations, computational fluid dynamics, or other tasks, based on commands received from the processor <NUM> or that are not part of the "normal" information flow of a graphics processing pipeline.

The APD <NUM> includes shader engines <NUM> (which may collectively be referred to herein as "programmable processing units <NUM>") that include one or more SIMD units <NUM> that are configured to perform operations at the request of the processor <NUM> in a parallel manner according to a SIMD paradigm. The SIMD paradigm is one in which multiple processing elements share a single program control flow unit and program counter and thus execute the same program but are able to execute that program with different data. In one example, each SIMD unit <NUM> includes sixteen lanes, where each lane executes the same instruction at the same time as the other lanes in the SIMD unit <NUM> but can execute that instruction with different data. Lanes can be switched off with predication if not all lanes need to execute a given instruction. Predication can also be used to execute programs with divergent control flow. More specifically, for programs with conditional branches or other instructions where control flow is based on calculations performed by individual lanes, predication of lanes corresponding to control flow paths not currently being executed, and serial execution of different control flow paths, allows for arbitrary control flow to be followed.

The basic unit of execution in shader engines <NUM> is a work-item. Each work-item represents a single instantiation of a shader program that is to be executed in parallel in a particular lane. Work-items can be executed simultaneously as a "wavefront" on a single SIMD unit <NUM>. Multiple wavefronts may be included in a "work group," which includes a collection of work-items designated to execute the same program. A work group can be executed by executing each of the wavefronts that make up the work group. The wavefronts may be executed sequentially on a single SIMD unit <NUM> or partially or fully in parallel on different SIMD units <NUM>. Wavefronts can be thought of as instances of parallel execution of a shader program, where each wavefront includes multiple work-items that execute simultaneously on a single SIMD unit <NUM> in line with the SIMD paradigm (e.g., one instruction control unit executing the same stream of instructions with multiple data).

A local data store memory <NUM> in each shader engine <NUM> stores values for use by shader programs. The physical proximity of the local data store memory <NUM> provides improved latency as compared with other memories such as global memory <NUM> in the APD <NUM> that is not included within shader engines <NUM> or memory <NUM> that is not within the APD <NUM>. A scheduler <NUM> is configured to perform operations related to scheduling various wavefronts on different shader engines <NUM> and SIMD units <NUM>.

The parallelism afforded by the shader engines <NUM> is suitable for graphics related operations such as pixel value calculations, vertex transformations, tessellation, geometry shading operations, and other graphics operations. A graphics processing pipeline <NUM> which accepts graphics processing commands from the processor <NUM> thus provides computation tasks to the shader engines <NUM> for execution in parallel.

The shader engines <NUM> are also used to perform computation tasks not related to graphics or not performed as part of the "normal" operation of a graphics processing pipeline <NUM> (e.g., custom operations performed to supplement processing performed for operation of the graphics processing pipeline <NUM>). An application <NUM> or other software executing on the processor <NUM> transmits programs (often referred to as "compute shader programs," which may be compiled by the driver <NUM>) that define such computation tasks to the APD <NUM> for execution.

<FIG> is a block diagram showing additional details of the graphics processing pipeline <NUM> illustrated in <FIG>. The graphics processing pipeline <NUM> includes stages that each performs specific functionality. The stages represent subdivisions of functionality of the graphics processing pipeline <NUM>. Each stage is implemented partially or fully as shader programs executing in the programmable processing units <NUM>, or partially or fully as fixed-function, non-programmable hardware external to the programmable processing units <NUM>.

The input assembler stage <NUM> reads primitive data from user-filled buffers (e.g., buffers filled at the request of software executed by the processor <NUM>, such as an application <NUM>) and assembles the data into primitives for use by the remainder of the pipeline. The input assembler stage <NUM> can generate different types of primitives based on the primitive data included in the user-filled buffers. The input assembler stage <NUM> formats the assembled primitives for use by the rest of the pipeline.

The vertex shader stage <NUM> processes vertices of the primitives assembled by the input assembler stage <NUM>. The vertex shader stage <NUM> performs various per-vertex operations such as transformations, skinning, morphing, and per-vertex lighting. Transformation operations may include various operations to transform the coordinates of the vertices. These operations may include one or more of modeling transformations, viewing transformations, projection transformations, perspective division, and viewport transformations. Herein, such transforms are considered to modify the coordinates or "position" of the vertices on which the transforms are performed. Other operations of the vertex shader stage <NUM> that modify attributes other than the coordinates are considered to modify non-position attributes.

The vertex shader stage <NUM> is implemented partially or fully as vertex shader programs to be executed on one or more shader engines <NUM>. The vertex shader programs are provided by the processor <NUM> as programs that are pre-written by a computer programmer. The driver <NUM> compiles such computer programs to generate the vertex shader programs having a format suitable for execution within the shader engines <NUM>.

The hull shader stage <NUM>, tessellator stage <NUM>, and domain shader stage <NUM> work together to implement tessellation, which converts patch primitives into a specified domain using subdivision. Examples of domain types include point, line, tri, and quad, and these domain types are capable of being rendered by the graphics processing pipeline <NUM>. Either or both of the hull shader stage <NUM> and the domain shader stage <NUM> can be implemented as shader programs to be executed on the programmable processing units <NUM>.

The hull shader stage <NUM> generates a patch for the tessellation based on an input primitive defined by a set of vertices and other information. More specifically, the hull shader stage <NUM> accepts input control points from the vertex shader stage <NUM>, where these input control points define a geometric primitive (e.g., a triangle) to be processed by the hull shader stage <NUM>. The input control points include position information that together define the shape and position of a patch. The hull shader stage <NUM> generates an output patch, along with patch constants, based on the input control points and the instructions of a programmable hull shader program. The output patch is defined at least in part by output control points that may or may not be the same as the input control points, based, again, on the instructions of the hull shader program. The output control points define the shape and position of a patch for processing by the tessellator stage <NUM>. The patch constants include at least tessellation factors, which define how the output patch is to be subdivided by the tessellator stage <NUM>. The tessellation factors include edge tessellation factors and may also include internal tessellation factors. The internal tessellation factors define the extent of subdivision of an internal portion of the output patch. The edge tessellation factors define the extent of subdivision of edge-adjacent portions of the output patch.

The tessellator stage <NUM> generates a set of domain points defined in coordinates of U and V or U, V, and W, each of which range between <NUM> and <NUM>. These domain points are subdivision vertices within the patch. A variety of patch division techniques are possible.

The domain shader <NUM> transforms unit space U, V, and W locations onto the 3D space domain of the patch. Once in 3D space (or "world space"), vertices are transformed into a homogenous (x, y, z, w) coordinate system referred to as clip space. This step is analogous to what a vertex shader would do after reading vertices from a vertex buffer, for example. The domain shader stage <NUM> generates the world-space positions based on the instructions of the corresponding domain shader program, based on the domain points output by the tessellator stage <NUM>, and based on the control points output by the hull shader stage <NUM>. The domain shader stage <NUM> may also use patch constants such as tessellation factors output by the hull shader stage <NUM> in generating the output vertices. The domain shader program is flexible in that the domain shader program is able to generate the output vertices having any definable relationship to the domain points output by the tessellator stage <NUM>. However, there are many known techniques. In a simple example, the domain shader stage <NUM> maps the U, V or U, V, W coordinates from the tessellator stage <NUM> to the world-space coordinates of the control points to generate intermediate output vertices having world-space positions. The domain shader stage <NUM> modifies the world-space positions of the intermediate output vertices by displacing such positions in a direction perpendicular to the plane of the patch (with no modification to the positions in the plane of the patch). The domain shader stage <NUM> may use the patch constants, such as tessellation factors from the hull shader stage <NUM>, to determine the positions of the output vertices. The domain shader stage <NUM> also optionally generates one or more vertex parameters for each output vertex in any technically feasible manner, such as by interpolating the corresponding parameters of the control points based on the positions of the domain points output by the tessellator stage <NUM> in relation to the control points.

The geometry shader stage <NUM> performs vertex operations on a primitive-by-primitive basis. Geometry shader programs typically accept whole primitives (e.g., a collection of vertices) as input and perform operations on those whole primitives as specified by the instructions of the geometry shader programs. A variety of different types of operations can be performed by the geometry shader stage <NUM>, including operations such as point sprite expansion, dynamic particle system operations, fur-fin generation, shadow volume generation, single pass render-to-cubemap, per-primitive material swapping, and per-primitive material setup. Operations for the geometry shader stage <NUM> may be performed by a shader program that executes on the programmable processing units <NUM>.

The rasterizer stage <NUM> accepts and rasterizes simple primitives generated upstream. Rasterization consists of determining which screen pixels (or sub-pixel samples) are covered by a particular primitive. Rasterization is performed by fixed function hardware or may be performed by shader programs executing in the programmable processing units <NUM>.

The pixel shader stage <NUM> calculates output values (e.g., color values) for screen pixels based on the primitives generated upstream and the results of rasterization. The pixel shader stage <NUM> may apply textures from texture memory. Operations for the pixel shader stage <NUM> are performed by a shader program that executes on the programmable processing units <NUM>.

The output merger stage <NUM> accepts output from the pixel shader stage <NUM> and merges those outputs, performing operations such as z-testing and alpha blending to determine the final color for a screen pixel, which are written to a frame buffer for output to the display device <NUM>.

As described above, many of the stages illustrated in <FIG> and described as being included within the graphics processing pipeline <NUM> can be implemented as shader programs executing within the shader engines <NUM> illustrated in <FIG>. Various operations occur in the driver <NUM> and within the APD <NUM> to facilitate executing shader programs in the shader engines <NUM>.

As described elsewhere herein, shader programs are often specified in code by an application programmer and are compiled for use by the application program by a compiler. Typically, this compilation occurs by the driver <NUM> during application startup, as opposed to at draw time (i.e., after startup, when the application is actually requesting objects to be rendered). However, it is possible for the driver <NUM> to perform a just-in-time compilation of shader programs at draw time should the need arise.

The application defines the specific configuration of the graphics processing pipeline <NUM>. This "graphics pipeline configuration" defines various aspects of the graphics processing pipeline <NUM>, including which optional shader stages are used (for example, whether the geometry shader stage <NUM> is used, and/or whether tessellation, which uses the hull shader stage <NUM>, tessellator stage <NUM>, and domain shader stage <NUM>, is used). The graphics pipeline configuration information also defines other aspects of the graphics processing pipeline <NUM>, such as, without limitation, the specific shader programs to be used for the shader stages that are enabled and that execute shader programs (e.g., the vertex shader stage <NUM>, pixel shader stage <NUM>, and the hull shader stage <NUM>, domain shader stage <NUM>, and geometry shader stage <NUM> if enabled), aspects of the rasterizer stage <NUM> (such as which face of a triangle is the front face, how to apply depth values to pixels, how culling is to be performed, how triangles are to be filled, and other aspects), aspects of how blending and other processing occurs in the output merger stage <NUM>, aspects of how inputs to the graphics processing pipeline <NUM> (e.g., input vertices) are to be interpreted, and other aspects. One example of a programming construct that defines graphics pipeline configuration is the Direct 3D version <NUM> Graphics Pipeline State structure (D3D12_GRAPHICS_PIPELINE_STATE_DESC structure) of the Direct 3D <NUM> application programming interface provided by Microsoft Corporation of Redmond, Washington, U. In some situations (such as in a hardware and software configuration in which Microsoft Direct X <NUM> is used), various pre-defined graphics pipeline configurations are communicated by the application to the driver <NUM> at application startup time. At draw time, the application is able to switch between different pre-defined graphics pipeline configurations by issuing requests to the driver <NUM> to switch to particular pre-defined graphics pipeline configuration. In other situations (such as in a hardware and software configuration in which Microsoft Direct X <NUM> is used), the application does not specify graphics pipeline configurations at runtime to the driver <NUM>. Instead, the application modifies the graphics pipeline configuration, including which pipeline stages are to participate in rendering and which shader programs are to be used for the various pipeline stages, at draw time by issuing state change commands.

Shader programs have inputs and outputs that indicate how data is communicated between shader stages. These inputs and outputs represent what data is to be provided to the shader programs by previous stages of the graphics processing pipeline <NUM> and also what data is to be output by the shader programs to be provided to subsequent stages of the graphics processing pipeline <NUM>. Some shader programs utilize memory load and/or store instructions to read their inputs from memory and to store their outputs to memory (such as to/from a local data store memory <NUM> or global memory <NUM>). Other shader programs use other types of instructions, such as direct declarations of inputs and outputs that, when interpreted by the hardware, cause the hardware to import specific values from previous stages and place those values into local memory and/or registers for the shader program, and/or to export specific values from registers and/or local memory for the shader to locations for use by a subsequent shader stage. The transfer between stages may occur via a general-use memory (such as local data store memory <NUM> or global memory <NUM>) or via more specific storage areas devoted to particular data types.

It is possible for certain shader programs to output data that is not used by any subsequent portion of a pipeline. If such output data is stored in storage such as local data store memory <NUM> or global memory <NUM>, then graphics rendering is less efficient due to memory storing unused data and gaps in memory between used data. One example situation in which such inefficiencies occur is with the pair of shader programs including the hull shader and the domain shader. In this example situation, it is possible (and in fact occurs often) that an application programmer creates a single version, or limited number of versions of a particular hull shader program, and creates more version of domain shader programs. In such a situation, one or more hull shader programs are each designed to work with multiple different domain shader programs. Thus, the one or more hull shader programs would need to output all possible outputs that could be used by the various domain shaders that could work with each such hull shader. Therefore, in any particular hull shader/domain shader combination, some of the data output by the hull shader would not be used by that domain shader, and at least some of the storage space for the hull shader would be wasted. In addition, gaps in memory may exist between data that is used due to the manner in which the compiler is implemented. Reorganizing data in memory in a packed format reduces the memory footprint and increases the effective memory bandwidth. In some scenarios, the compiler <NUM> is not able to identify whether particular data points output by the hull shader would be used by subsequent stages of the graphics processing pipeline <NUM>. In such situations, the compiler could use conservative estimation or runtime checking. In one example, a patch has an edge tessellation factor that is less than or equal to <NUM> or not a number. In such scenarios, the compiler generates additional instructions in the hull shader to check the tessellation factors at runtime.

<FIG> illustrates a technique for improving memory usage for inter-shader communication of data, according to an example. Generally, the technique involves modifying a shader program that outputs data based on knowledge of how one or more other shader programs uses that data, as well as modifying the one or more other shader programs that uses the data. A compiler <NUM> is illustrated as being a part of the driver <NUM>. The compiler <NUM> accepts code specified in an application program and compiles that code to generate compiled shader programs for use in various stages of the graphics processing pipeline <NUM>. The driver <NUM> transmits the compiled shader programs to the graphics processing pipeline <NUM> for execution. Although the compiler <NUM> is illustrated as part of the driver <NUM>, those of skill in the art will understand that the compiler <NUM> could alternatively be independent or part of another software module.

As described elsewhere herein, the application specifies graphics pipeline configuration information that specifies the optional shader stages that are enabled and the specific shader programs to be used for the various stages of the graphics processing pipeline <NUM>. This graphics pipeline configuration information is represented in <FIG> as graphics pipeline state <NUM>.

The driver <NUM> examines the graphics pipeline state <NUM> to determine which shader stages are enabled, as well as which specific shader programs are used for those stages. The driver <NUM> determines that the first shader program <NUM> is used for one of the pipeline stages and that one or more second shader programs <NUM> are used for a subsequent pipeline stage and passes that determined information to the compiler <NUM>. The compiler <NUM> analyzes the instructions of the first shader program <NUM> and, in some situations, the instructions of the second shader program(s) <NUM> to determine whether the first shader program <NUM> outputs data that is not used by any of the second shader program(s) <NUM> (this analysis is referred to elsewhere herein as "output use analysis").

In some implementations, the compiler <NUM> knows that certain outputs from certain shader programs can only be used by certain other shader programs. In such situations, for any particular analyzed first shader program <NUM>, the compiler <NUM> limits the second shader program(s) analyzed <NUM> for the output use analysis to those shader programs that could possibly use the data output from the first shader program <NUM> (for example, it is known that hull shaders output data only used by domain shaders, so the compiler <NUM> would limit at least one instance of the output use analysis in which the hull shader program is the first shader program <NUM> such that only a domain shader program is analyzed as the second shader program <NUM>). In other implementations, the compiler analyzes each shader program that executes after the shader program that outputs data to determine whether the data output is used by any other shader program. If, in response to performing the output use analysis, the compiler <NUM> determines that some of the data output by the first shader program <NUM> is not used by any of the second shader programs <NUM>, then the compiler <NUM> modifies one or more of the first shader program <NUM> and the second shader programs <NUM> based on the output use analysis.

The output use analysis performed by the compiler <NUM> includes identifying the data output by the first shader program <NUM>. More specifically, the compiler <NUM> examines the output instructions <NUM> to identify data that is output by the first shader program <NUM>. In some situations, each particular data that is output by the first shader program <NUM>, the compiler <NUM> examines the second shader programs <NUM> to determine if there is any data output by the first shader program <NUM> that is not used by any of the second shader programs <NUM>.

To determine whether there is any data output by the first shader program <NUM> that is not used by any of the second shader programs <NUM>, the compiler <NUM> examines the input instructions <NUM> of each of the second shader programs <NUM> to determine if the input instructions <NUM> input all of the data that is output by the output instructions <NUM> of the first shader program <NUM>. If there is any data output by the output instructions <NUM> of the first shader program <NUM> that is not input by the input instructions <NUM> of any of the second shader programs <NUM>, then the compiler <NUM> determines that such data is not used by any of the second shader programs <NUM>. In some situations, checks regarding whether data is used by a second shader program <NUM> cannot be performed at compile time. In those situations, the compiler <NUM> inserts instructions to perform runtime checking to detect whether data output from the first shader program <NUM> will be used by subsequent shader programs (one example of this is a hull shader that determines whether patches are to be culled based on a tessellation factor being less than or equal to zero).

If the compiler <NUM> determines that there is no data that is unused by the second shader programs <NUM> and that no gaps would exist between data passed from the first shader program to a second shader program in memory, then the compiler <NUM> does not modify the first shader program <NUM> or the second shader program <NUM> according to the techniques described herein. If gaps would exist between used data in memory, then the compiler <NUM> applies data packing to the data. The compiler modifies both output instructions in the first shader program and input instructions in the second shader program to access memory according to a packed format. If the compiler <NUM> determines that there is data that is not used by any of the second shader programs <NUM>, then the compiler <NUM> does not generate memory writes or stores for the unused data of the first shader program. In the situation that data packing is performed after identifying the unused data, the compiler <NUM> generates output instructions in the first shader program and input instructions in the second shader program in a form that accesses the memory data in the packed format. In some situations, the compiler <NUM> inserts instructions to perform runtime checking for unused data (such as to check whether the tessellation factors number is less than <NUM>).

The concept of packing data is now described in more detail. Some output instructions <NUM> that output data that is not used by any of the second shader programs <NUM> output multiple items of data. In an example, an output instruction of a hull shader program outputs multiple control point data points for consumption by a domain shader program, but at least some of those control point data points are not used by the domain shader program. For an output instruction that outputs multiple items of data, the compiler <NUM> determines which of those items of data are not used by any of the second shader programs <NUM>. The compiler <NUM> deletes the memory write or store instructions if all of those items of data are not used, or generates instructions only writing or storing the data that are used. If gaps between data would exist in memory according to the original output instructions or after output use analysis, then the compiler <NUM> performs data packing. This data packing includes identifying the memory locations of the data that is used by the second shader programs. The compiler <NUM> uses this information to generate the modified output instructions <NUM> for the packed data in the first shader program <NUM> and the modified input instructions <NUM> that use those packed data in the second shader program <NUM>. Data packing also allows the compiler <NUM> to aggregate output and input instructions of small size such that fewer instructions operating on larger chunks of data are executed.

Packing data items reduces the total memory space allocated for the data items and enables the compiler <NUM> to aggregate multiple memory access instructions. Identifying unused data by output use analysis helps data packing to pack only those data that are used. In an example, a first output instruction outputs four data items, but only one is used by a second shader program <NUM>, and a second output instruction outputs a different four data items, but only three are used by a second shader program <NUM>. Packing these data items allows the compiler <NUM> to generate one output instruction that outputs the four items that are used (one data item plus three data items). Note, it is possible for the packing to be imperfect such that the generated output instructions <NUM> include at least some output instructions that output some unused data. In a modification to the example above, if the first output instruction and the second output instruction both output one data item, then an output instruction that results may output four items of data, with only two of those items used. However, this result would be better than two output instructions that only output one item of data each, since in that scenario, less memory is used, with memory for four data items instead of eight data items being used, and fewer memory instructions are issued, with one output instruction instead of two output instructions being issued.

In addition to generating the modified output instructions <NUM>, the compiler <NUM> also generates modified input instructions <NUM> based on the input instructions <NUM> of the second shader programs <NUM>. More specifically, in a second shader program <NUM>, the input instructions <NUM> input data of the same format as the data output by the output instructions <NUM>. When data are packed in memory, the compiler <NUM> generates modified input instructions <NUM> in the second shader program <NUM> to input the data having the packed format. Using the above example, the compiler <NUM> generates one input instruction to input the data items that are used in the body <NUM> of the second shader program <NUM>, or in a less ideally packed format (four data items), generates an input instruction to input four data items in which two of them are used in the body <NUM>. Input data are usually read from memory to registers or local memory such as the local data store memory <NUM> before being used in the rest of the shader program.

As described above, the output use analysis, in which the compiler <NUM> determines which data items output by the first shader program <NUM> are used by no other second shader programs <NUM>, can be limited to certain shader stages (and thus certain programs defined by the particular graphics pipeline state <NUM>). One example of a situation in which the compiler <NUM> limits the analysis to certain shader programs involves the hull shader stage <NUM> and the domain shader stage <NUM>, which together with the fixed-function tessellator stage <NUM>, implement tessellation. In this example, a hull shader program outputs patch control points and patch constants that include tessellation factors and a domain shader program inputs control points output from the hull shader, the domain points output from the tessellation stage <NUM>, and the patch constants from the hull shader program. In this situation, the compiler <NUM> analyzes the output instructions of the hull shader program and the input instructions of the domain shader program to determine whether there is data output by the hull shader program (e.g., patch control points or patch constants) that is not input by the domain shader program. Upon determining that such data exists, the compiler <NUM> modifies the hull shader program and/or the domain shader program in accordance with the techniques described herein. The compiler <NUM> does not analyze any other shader program (such as the geometry shader program or the pixel shader program) to determine whether the outputs of the hull shader program is used by any of those other shader programs.

Note that for different graphics pipeline states <NUM>, it is possible for different versions of the shader programs to be used. The compiler <NUM> performs the analysis described herein for various graphics pipeline states. Thus it is possible for the compiler <NUM> to modify different first shader programs differently or even to modify one shader program, used in one graphics pipeline state, differently than the same shader program used in a different graphics pipeline state. For example, it is possible for one first shader program to be used in conjunction with a second shader program in a first graphics pipeline state but for the same first shader program to be used in conjunction with a different second shader program in a second graphics pipeline state. In this situation, the compiler <NUM> performs the analysis and modification of shader programs described herein for each graphics pipeline state, which may thus result in different modified version of the same first shader program for different graphics pipeline states.

<FIG> is a block diagram illustrating analysis of a hull shader program and domain shader program pair, according to an example. The graphics pipeline state <NUM> is similar to the graphics pipeline state <NUM> of <FIG>, with the specific feature that graphics pipeline state <NUM> specifies that tessellation is enabled, and further specifies that the hull shader program <NUM> and the domain shader program <NUM> are to be used for the hull shader stage <NUM> and domain shader stage <NUM>, respectively.

The input hull shader program <NUM> and the input domain shader program <NUM> are pre-compilation programs, for example, as specified by an application. The compiler <NUM> converts these shader programs to a compiled hull shader program <NUM> and a compiled domain shader program <NUM>, respectively. The input hull shader program <NUM>, as specified by the application, includes input instructions <NUM>, a body <NUM>, and output instructions <NUM>. The input instructions <NUM> cause hull shader input data such as patch control points to be input (e.g., from a location written to by the vertex shader stage <NUM>) to a location available to instructions in the body <NUM>. The body <NUM> includes instructions for performing the work of the hull shader, such as processing or modifying inputs and generating one or more of patch control points and patch constants data based at least in part on the input hull shader input data. The output instructions <NUM> cause data, such as the generated one or more patch control points or patch constants, to be written to an output location that is available for input by the domain shader program <NUM> (as well as the tessellator stage <NUM>). In some implementations, this output location is a memory, such as local data store memory <NUM> or global memory <NUM>.

The domain shader program <NUM>, as specified by the application, includes input instructions <NUM>, a body <NUM>, and output instructions <NUM>. The input instructions <NUM> cause domain shader input data such as control points output from the hull shader program <NUM>, the domain points generated by the tessellator stage <NUM>, and the patch constants output by the hull shader program <NUM>, to be read in and placed in locations available to the instructions of the body <NUM> (such as within registers or a local data store memory <NUM>). The body <NUM> includes instructions that generate output vertices based on the input data, and the output instructions <NUM> output the output vertices to a location (such as specialized memory, local data store memory <NUM>, or global memory <NUM>) for use by subsequent stages.

In operation, the compiler <NUM> examines the graphics pipeline state <NUM> and determines that the pipeline to be used for rendering subsequent geometry has tessellation enabled and that the hull shader program and domain shader program are the hull shader program <NUM> and domain shader program <NUM> illustrated in <FIG>. The compiler <NUM> analyzes the output instructions <NUM> of the hull shader program <NUM> and the input instructions <NUM> of the domain shader program <NUM>. The compiler <NUM> determines that at least some instructions of the output instructions <NUM> output at least some control points or patch constants that are not input by the input instructions <NUM>. In response to this determination, the compiler <NUM> generates modified output instructions <NUM> from output instructions <NUM> in the input hull shader program <NUM> and modified input instructions <NUM> from input instructions <NUM> in the input domain shader program <NUM> if the data layout in memory is changed by the data packing. The term "modified" means that the compiled instructions are different than if the techniques disclosed herein were not applied. The compiler does not generate output instructions that output control points or patch constants that are not used by input instructions <NUM> of the domain shader <NUM>. When gaps exist in memory between used data including control points and patch constants, the compiler <NUM> configures the instructions to perform data packing. Specifically, the compiler <NUM> keeps track of the memory location of the packed control point and patch constant data. The compiler <NUM> uses the information to transform output instructions <NUM> in the input hull shader program <NUM> into modified output instructions <NUM> in the modified hull shader program <NUM> to output control points and patch constants to memory in a packed format. The compiler <NUM> also uses this information to transform input instructions <NUM> in the input domain shader program <NUM> into modified input instructions <NUM> in the generated domain shader program <NUM> to input control points and patch constants from memory in a packed format. Multiple output instructions from the input hull shader program <NUM> are "aggregated" in the modified output instructions <NUM> if their output data are consecutive in memory and the combined data size fits in a memory output instruction. Similarly, multiple input instructions <NUM> of the input domain shader program <NUM> are aggregated in the modified input instructions <NUM> if their input data are consecutive in memory and the combined data size fits in a memory input instruction. Data input by modified input instructions <NUM> are loaded into registers or local memory such as local data store memory <NUM> before the data are used by the rest of the body <NUM>. There are cases where runtime checking is used to identify data output by the hull shader that is not used by the domain shader. Such cases include data for patches that will be culled based on the computed tessellation factors (e.g., a tessellation factor is <NUM>, less than <NUM>, or not-a-number). The compiler <NUM> generates additional instructions to check the values of the tessellation factors to determine whether the patch is to be culled and does not generate output instructions in modified output instructions <NUM> for the data of those culled patches.

A specific example of data packing and generating output instructions for a hull shader with data packing is also illustrated. Data layout <NUM> in memory for output instructions in a hull shader program that are generated without data packing are shown. Additionally, data layout <NUM> in memory according to output instructions in the hull shader generated with data packing are shown. The hull shader output without data packing <NUM> includes <NUM> output instructions. Instructions <NUM> through <NUM> each output one control point or patch constant data element input by a corresponding domain shader. Instruction <NUM> outputs no control points or patch constant data elements used by the corresponding domain shader. All of the control points or patch constant data elements output by instruction <NUM> are used by the corresponding domain shader. The control points or patch constant data elements are provided arbitrary numbering from <NUM> to <NUM> for clarity. Control points or patch constant data elements in memory that are not input by the domain shader are marked with an "X.

In response to identifying that the control points or patch constant data elements <NUM> to <NUM> are input by the domain shader and that the other control points or patch constant data elements are not input by the domain shader, the compiler generates the modified hull shader output instructions <NUM>. More specifically, the compiler <NUM> determines that all <NUM> data elements can be packed in memory as shown in the hull shader output with data packing <NUM>. The compiler <NUM> also determines that the first four data elements can be output by a single instruction - modified HS output instruction <NUM> and that the second four data elements can be output by another single instruction - modified HS output instruction <NUM>. This packing reduces the memory footprint from the size of <NUM> data element to the size of <NUM> data elements and also reduces the number of memory access instructions from <NUM> to <NUM>. In addition, the compiler <NUM> generates corresponding input instructions for the domain shader program, which are configured to input the data in the packed format. These packed-format input instructions for the domain shader program result in a reduction in the number of instructions used, as the instructions that would input unpacked data are aggregated into fewer instructions.

In some circumstances, the compiler <NUM> inserts additional instructions to check at runtime whether data output by a shader stage is to be used by any subsequent shader stage. Specifically, for the hull shader and domain shader combination, a patch that has an edge tessellation factor of less than or equal to zero or not-a-number will be culled and data for this patch will not be used in the domain shader. The compiler <NUM> thus inserts instructions to check the value of the tessellation factors once computed and to prevent outputting data for a culled patch.

It is possible for one graphics pipeline state <NUM> to specify that a hull shader is to be used with a particular domain shader and for a second graphics pipeline state <NUM> to specify that the same hull shader is to be used with a different domain shader. In this instance, the compiler <NUM> would generate two different versions of the hull shader, one for use with each domain shader (assuming the domain shaders use the data output by the hull shader differently, of course).

<FIG> is a flow diagram of a method <NUM> for modifying shader programs to reduce the number of memory accesses and the memory footprint of data transmitted between the shader programs, according to an example. Although described with respect to the system shown and described with respect to <FIG>, it should be understood that any system configured to perform the method, in any technically feasible order, falls within the scope of the present disclosure.

The method <NUM> begins at step <NUM>, where a compiler <NUM> identifies shader programs to analyze based on the graphics pipeline configuration (e.g., included within graphics pipeline state <NUM> or graphics pipeline state <NUM>). The graphics pipeline configuration may be pre-defined at application startup time (as is the case with, for example, Direct3D <NUM>) or may be modified at draw-time. If pre-defined at application startup time, the compiler <NUM> is able to perform the method <NUM> to reduce memory footprint of data transmitted between shader programs also at application startup time in shader compilation. If modified at draw-time, the compiler <NUM> is capable of performing the method <NUM> also at draw time, during a just-in-time compilation of the shader programs analyzed.

The graphics pipeline configuration defines the specific shader stages that are to be used as well as the specific shader programs used at the stages that support programmable shader stages. The compiler <NUM> identifies a first shader program to analyze and identifies one or more second shader programs to analyze based on the identified first shader program. The first shader program may be any shader program specified by the graphics pipeline configuration. The second shader programs are shader programs that are known to use data output by the first shader program. In one example, a hull shader outputs data such as control points and patch constants and a domain shader inputs those control points and patch constants.

At step <NUM>, the compiler <NUM> identifies data output by the first shader program but not used by any second shader program. At step <NUM>, the compiler <NUM> determines data for which usage in the second shader program cannot be known at compile time, and adds instructions for runtime checking and removal of data if such data is not used. At step <NUM>, for used data that, when written to memory, has gaps, the compiler <NUM> determines whether and how data packing should be used. At step <NUM>, the compiler <NUM> applies data packing, generating output instructions for the first shader and input instructions for the second shader that write and read data in a packed format.

The methods provided may be implemented in a general purpose computer, a processor, or a processor core. Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine. Such processors may be manufactured by configuring a manufacturing process using the results of processed hardware description language (HDL) instructions and other intermediary data including netlists (such instructions capable of being stored on a computer readable media). The results of such processing may be maskworks that are then used in a semiconductor manufacturing process to manufacture a processor which implements aspects of the embodiments.

Claim 1:
A computer-implemented method for modifying at least one shader program of one or more shader programs to improve memory performance for data transmitted between the shader programs, the method comprising:
identifying a first shader program and a second shader program for analysis based on graphics pipeline (<NUM>) state;
first determining, including determining whether there are data points output by the first shader program that are not input to the second shader program;
second determining, including determining whether identification of data points output by the first shader program but not input to the second shader program cannot be performed at compile time and can be performed at runtime;
modifying the first shader program based on the first determining and the second determining to generate a compiled first shader program; and
outputting the compiled first shader program for execution in the graphics processing pipeline (<NUM>).