t
⁢

10
[

i
⁢
n
⁢
t
⁢

(

u
⁢
15

)

]

.
BgdMinCoc

=
16384.

;

Without the access vector metadata as in the first technique, the compiler would struggle to optimize this operation due to the dynamic nature of the index and the complex data structure.

In the second technique, by knowing the exact layout and size of the data structures involved, the compiler can effectively translate high-level code into optimized machine-level instructions that make better use of the GPU's registers. The oracle conditions generated from the access vector metadata may be as follows:

if (u15 == 0) {

*(Base_pointer + 8) = 16384.0; // First element

} else if (u15 == 1) {

*(Base_pointer + 8 + 24) = 16384.0; // Second element

} else if (u15 == 2) {

*(Base_pointer + 8 + 48) = 16384.0; // Third element

}

Here, Base_pointer represents the starting address of the array t10. The offset and stride values from the access vector are used to calculate the exact memory addresses for the BgdMinCoc field in each structure within the array.

Furthermore, this technique naturally extends to multi-dimensional arrays. Although the simplified example only demonstrates a one-dimensional array, the access vector metadata can be extended to support multiple dimensions by using an access vector list. Each dimension of the array would have its own access vector tuple, allowing the compiler to handle multi-dimensional arrays efficiently.

The introduction of access vector metadata in the compiler's intermediate representation enables more precise handling of arrays of structures and multi-dimensional arrays. By preserving the structure's type information, the compiler can generate more efficient code with fewer conditional statements, leading to improved performance and reduced redundancy in SIMT computing.

[[Non-Constant Stores and Loads]]

FIG. 4 shows code 420 that performs non-constant stores and loads. The first technique described supra for register promotion may require that each address is stored only once, and the values being stored must be constants or uniform values at compile time. Uniform values are those that remain the same across all threads in a shader program, even if they are not known at compile time.

However, the second technique described here may extends the capabilities of register promotion to support non-constant stores and loads. This means that the technique can handle cases where values are stored to and loaded from unknown addresses at compile time, and these values can be varying across threads (i.e., non-uniform).

In the code shown in FIG. 4(A), a value T is stored at an unknown index i in the array Temp, and later, a value is loaded from the same index i into T. Additionally, another value R is stored at the same unknown index i later in the program, and then a value is loaded from index i into T again.

The second technique can handle such cases by generating oracle codes around the stores and loads, and using a compiler algorithm to propagate the data flow of the values. The oracle codes are conditional statements that determine which register to use based on the value of the unknown address i.

FIG. 4(B) shows oracle code 440 generated for the store operation Temp[i]=T. FIG. 4(C) shows oracle code 460 generated for the load operation T=Temp[i].

To handle the data flow between these multiple non-constant stores and loads, the compiler may use a data flow propagation algorithm. This algorithm tracks the values stored in each register and propagates them to the appropriate load operations. By doing this, the correct values are loaded from the registers, even in the presence of multiple non-constant stores and loads.

The data flow propagation algorithm allows the compiler to handle complex cases where the values stored in registers may be overwritten by subsequent store operations. By tracking the data flow and propagating the values correctly, the compiler can generate efficient code that correctly handles multiple non-constant stores and loads.

The access vector metadata, as described supra, preserves the structure's type information and provides precise details about the offsets, lengths, and strides of the array elements, which further allows the compiler to generate efficient and accurate oracle codes for handling unknown addresses and non-constant values. As such, the second technique supports unknown accesses to the locations in Temp[ ], either by loads or stores.

[[Conditional Select Operations]]

FIG. 4(D) shows code 480 of conditional select operations. In addition to using conditional branches (e.g., if-else statements) for handling oracle conditions, the second technique may also supports the use of conditional select operations (e.g., csel instructions) when available in the target processor architecture. Conditional select operations provide an alternative way to implement oracle conditions without the need for explicit branching.

In the code of FIG. 4(D), the csel.eg instruction is used to conditionally select between the new value T and the existing value in the register (r0, r1, r2, or r3) based on the value of the index I. The “.eg” suffix indicates an “equal to” condition, meaning that the new value T is selected if I is equal to the specified constant (0, 1, 2, or 3), otherwise the existing value in the register is retained.

Using conditional select operations has several advantages over conditional branches such as reduced branching overhead, improved instruction-level parallelism, and simplified code generation.

The second technique supports both conditional branches and conditional select operations, providing flexibility to choose the most appropriate approach based on the specific requirements and characteristics of the code being optimized.

FIG. 5(A) shows code 520 for register promotion in the first technique. The code utilizes the struct in FIG. 3(A). The first technique described supra for handling stores to unknown locations in arrays of structures has limitations due to the loss of structure information during the compilation process. When the compiler operates on a flattened memory representation, it treats the array as a series of elementary values, disregarding the structure's type information. This leads to the generation of inefficient code with a large number of conditional statements to cover all possible byte offsets within the array.

In the code shown in FIG. 5(A), t10[int(u15)].BgdMinCoc=16384.0, where t10 is an array of structures and BgdMinCoc is a field within the structure. The first technique generates code that uses 18 float variables (e.g., R0 to R17) to handle all possible byte offsets for the index u15. This approach does not take advantage of the structure's type information and generates unnecessary conditional statements.

FIG. 5(B) shows code 540 for register promotion in the second technique. The code utilizes the struct in FIG. 3(A). The second technique uses access vector metadata to generate more efficient code. By preserving the structure's type information through the access vector metadata, the compiler can detect which field of the structure is accessed by each store or load operation. This allows the compiler to tune the conditions precisely, reducing the number of oracle conditions from 18 to just 3 for the given store operation.

The access vector metadata provides the necessary information about the field offsets, array length, and structure size, enabling the compiler to generate optimized code. In this example, the compiler uses only three float variables (R0, R1, and R2) to handle the store operation, corresponding to the three possible offsets for the BgdMinCoc field in the structure. The access vector metadata provides the necessary information about the field offset (8), array length (3), and structure stride (24) to generate these precise oracle conditions.

By using the access vector metadata, the proposed solution reduces the number of oracle conditions from 18 to 3 for this particular store operation, resulting in more efficient code generation. This approach demonstrates the benefits of preserving and utilizing the structure's type information during the compilation process, enabling more effective optimizations for complex data types like arrays of structures.

FIG. 6

The first technique for register promotion described supra has several limitations when it comes to handling arbitrary control flow and multiple stores to the same location. These limitations arise from the fact that the first technique assumes a simplified control flow structure and performs the transformation based on certain restrictions.

One of the main limitations is that the first technique expects stores to be done only once, while loads can be done multiple times. This assumption simplifies the condition-based scalar promotion process, as it eliminates the need to consider the control flow effects resulting from multiple writes to the same location. When the store address is known and the store operation is performed only once, the first technique can easily convert the store instruction to an oracle condition at a particular site in the code.

However, this limitation becomes problematic when dealing with more complex control flow structures and multiple stores to the same location. Consider the following code snippet:

t832[i388 + 1] = x; // variable x

while(...) {

if(...) {

t832[i388 + 1] += t382[i388];

}

}

In this example, the first technique struggles to handle the store operation t832 [1388+1]=x; because it involves storing a variable value (x) to a variable location (t832 [i388+1]). Additionally, there is a possibility of multiple stores to the same location within the loop, as evident from the statement t832 [1388+1]+=t382 [i388].

To handle such cases, the compiler needs to perform data flow analysis to determine how the value of x can propagate and which addresses it can be stored to. This analysis becomes more complex when considering multiple stores and different control flow paths. For example, there might be another variable y being stored to an unknown location, and the values of x and y could be stored in different orders depending on the control flow path taken.

The first technique does not perform this necessary data flow analysis, which limits its ability to handle arbitrary control flow and multiple stores to the same location. As a result, it can only handle simpler cases where stores are done once, and the control flow is limited to certain types of structures.

To overcome these limitations, a more advanced solution is needed that can handle arbitrary control flow and perform data flow analysis to determine the propagation of values across multiple stores and different control flow paths. Such a solution would enable more comprehensive register promotion optimizations, leading to improved performance and reduced memory access overhead in GPU workloads.

[[SSA Algorithm with Access Vector for Scalarization]]

The second technique introduces a Static Single Assignment (SSA) algorithm to support scalarization in the presence of arbitrary control flow. This algorithm leverages the access vector type information provided by the compiler's front-end to generate a precise number of oracle conditions, enabling efficient scalarization despite complex control flow structures.

SSA is an intermediate representation used in compilers, where each variable is assigned only once, and every variable is defined before it is used. This property makes SSA particularly suitable for various compiler optimizations, including scalarization. By using SSA form, the compiler can easily track the definitions and uses of variables, simplifying the process of converting memory accesses to register accesses.

The SSA-based scalarization algorithm utilizes the access vector metadata to generate precise oracle conditions. The access vector metadata, as described earlier, provides information about the field offsets, array lengths, and structure sizes, allowing the compiler to accurately determine the register locations accessed by each load and store operation.

The SSA-based scalarization algorithm has ability to handle arbitrary control flow while leveraging the access vector information. Traditional scalarization techniques often struggle with complex control flow structures, such as loops and conditional statements, due to the difficulty in tracking the flow of data across different paths. However, by combining the SSA form with the access vector metadata, the proposed algorithm can effectively handle scalarization in the presence of arbitrary control flow.

The algorithm works by first converting the program into SSA form, ensuring that each variable has a single definition. Then, it uses the access vector metadata to identify the register locations accessed by each load and store operation. With this information, the algorithm can generate precise oracle conditions for each memory access, taking into account the specific field offsets, array lengths, and structure sizes.

The oracle conditions are generated based on the SSA form and the access vector metadata. For each load or store operation, the algorithm creates a set of conditional statements that determine which register to use based on the value of the access vector. These conditions are precise because they take into account the exact register locations accessed by each operation, as determined by the access vector metadata.

Once the oracle conditions are generated, the algorithm performs data flow analysis to propagate the values across different control flow paths. This analysis takes into account the SSA form; the values are correctly tracked and propagated based on the single assignment property. The data flow analysis also considers the oracle conditions; the correct registers are used for each memory access based on the specific conditions determined by the access vector metadata.

By combining the SSA form, access vector metadata, and data flow analysis, the proposed algorithm can effectively handle scalarization in the presence of arbitrary control flow. This approach allows for more precise and efficient scalarization compared to traditional techniques, as it takes into account the specific register locations accessed by each operation and propagates the values correctly across different control flow paths.

In an example with an array of structures each containing multiple fields, the SSA and access vector metadata can be applied as follows:

Original Code Snippet

struct MyStruct {

float a;

float b;

float c;

};

MyStruct arr[10];

for (int i = 0; i < 10; ++i) {

arr[i].b = someFunction(i);

}

In the second technique, the compiler determines the access vector for the field ‘b’ in the structure ‘MyStruct’. Assuming the offsets for ‘a’, ‘b’, and ‘c’ are 0, 4, and 8 respectively, and each float occupies 4 bytes, the access vector for ‘b’ would be (4, 10, 12) where 4 is the offset, 10 is the length (number of structures), and 12 is the stride (size of each structure).

In SSA form, the loop can be transformed such that each variable is assigned exactly once:

// SSA form with Access Vector Metadata

float* base_ptr = &arr[0].b; // Base pointer to the first ‘b’

for (int i = 0; i < 10; ++i) {

float* ptr = base_ptr + (i * 12); // Calculate pointer using stride

*ptr = someFunction(i); // Directly use the pointer for assignment

}

Here, the pointer calculation uses the stride from the access vector, and the assignment to each location is done exactly once per loop iteration, adhering to the SSA form. This transformation allows the compiler to optimize the memory access patterns more effectively by reducing the overhead of accessing individual fields through the structure and potentially enhancing the usage of registers.

[[Uniform vs. Varying Variables and Divergent Control Flow]]

In GPU programming using the SIMT (Single Instruction, Multiple Threads) model, a shader program is executed by multiple threads concurrently. Each thread may have different values for certain variables, leading to different execution paths and potentially divergent control flow.

Variables in a shader program can be classified as either uniform or varying. Uniform variables contain the same value across all threads executing the shader, even if the value is not known at compile time. On the other hand, varying variables may contain different values for different threads, leading to divergent behavior.

Branches in the shader code that depend on uniform variables are called uniform branches. In such cases, all threads will take the same execution path, either taking the branch or not. This allows for efficient execution, as all threads can execute in lockstep without any divergence.

However, branches that depend on varying variables are called divergent branches. In these cases, some threads may take the branch while others may not, leading to divergent control flow. Divergent control flow can impact performance, as threads that take different paths must be executed separately, potentially leading to underutilization of GPU resources.

An example is shown below:

float temp[4];

// temp[i] = T

If (I == 0)

r0 = T;

Else if (I == 1)

r1 = T;

Else if (I == 2)

r2 = T;

Else if (I == 3)

r3 = T;

Endif

In this code, if the index variable I is known to be uniform across all threads, the compiler can generate code using conditional branches. This is because all threads will take the same control flow path, and the branch predictor can efficiently predict the outcome of the branches. In this case, the generated code will be more efficient as it avoids executing unnecessary instructions.

If the variable I takes on different values (0, 1, 2, or 3) for different threads, it is considered a varying variable. Each thread may take a different branch based on its value of I, leading to divergent control flow. In such cases, the GPU must execute each branch separately, potentially leading to performance degradation.

To mitigate the impact of divergent control flow, the second technique uses conditional select statements instead of branches. Conditional select statements allow for executing all possible paths and selecting the appropriate result based on a condition.

An example is shown below:

float temp[4];

// temp[i] = T

r0 = csel.eg I, 0, T, r0;

r1 = csel.eg I, 1, T, r1;

r2 = csel.eg I, 2, T, r2;

r3 = csel.eg I, 3, T, r3;

In this code, the csel.eg instruction is used to conditionally select the value of T based on the value of I. If I is equal to the specified constant (0, 1, 2, or 3), the corresponding register (r0, r1, r2, or r3) is updated with the value of T. This approach avoids divergent control flow, as all threads execute the same instructions, and the appropriate result is selected based on the condition.

The process of converting control flow statements (e.g., if-else) to data flow statements (e.g., conditional selects) is known as if-conversion. If-conversion is a compiler transformation that helps in reducing the impact of divergent control flow in GPU programs.

By analyzing the nature of variables (uniform or varying) and the control flow structure, compilers can make informed decisions about code generation. For uniform branches, traditional branch instructions can be used efficiently. However, for divergent branches, techniques like if-conversion and the use of conditional select statements are preferred to minimize the impact of divergence and improve overall performance.

[[Divide and Conquer Strategy for Uniform Variables]]

In the second technique, the compiler can generate more efficient code by using a divide and conquer strategy when the index variable is known to be uniform across all threads. This strategy involves splitting the range of possible index values into smaller subranges and recursively checking each subrange to determine the appropriate register to use.

An example is shown below:

float temp[4];

// temp[i] = T

If (I == 0)

r0 = T;

Else if (I == 1)

r1 = T;

Else if (I == 2)

r2 = T;

Else if (I == 3)

r3 = T;

Endif

In this code, the index variable I is used to determine which register (r0, r1, r2, or r3) should be assigned the value of T. If I is known to be uniform across all threads, meaning that all threads will have the same value for I, the compiler can optimize the code using a divide and conquer approach.

The divide and conquer strategy works by splitting the range of possible index values into smaller subranges and recursively checking each subrange. For example, the compiler can generate the following code:

float temp[4];

// temp[i] = T

If (I < 2):

If I < 1:

r0 = T;

Else:

r1 = T;

Else:

if I < 3:

r2 = T;

else:

r3 = T

In this optimized code, the compiler first checks if I is less than 2. If it is, the code enters the first branch and further checks if I is less than 1. If I is less than 1, r0 is assigned the value of T; otherwise, r1 is assigned the value of T. If I is greater than or equal to 2, the code enters the second branch and checks if I is less than 3. If I is less than 3, r2 is assigned the value of T; otherwise, r3 is assigned the value of T.

The divide and conquer approach reduces the number of comparisons needed to determine the appropriate register. In the original code, if I is 3, the code needs to perform four comparisons (I=0, I=1, I=2, and I=3) before assigning the value of T to r3. In the optimized code, only two comparisons are needed (I<2 and I<3) to assign the value of T to r3.

The divide and conquer strategy is beneficial when the index variable is known to be uniform across all threads. If the index variable is varying, meaning that different threads may have different values for the index variable, the divide and conquer approach may not provide any performance benefit. In such cases, the compiler may generate code that executes all branches, and threads with different index values may take different paths, leading to divergent control flow and potential performance degradation.

Therefore, the second technique determines whether the index variable is uniform or varying to make informed decisions about code generation. When the index variable is uniform, the divide and conquer strategy can be used to optimize the code and reduce the number of comparisons needed. However, when the index variable is varying, the compiler may choose to generate code that executes all branches to handle the divergent control flow.

[[Divide and Conquer Strategy for Multi-Dimensional Arrays]]

The second technique can be extended to handle multi-dimensional arrays efficiently by leveraging the divide and conquer strategy along with the analysis of uniform and varying variables. This approach is particularly useful when dealing with expensive memory accesses, such as in low-power GPUs where cache memory is limited, and each load operation may take a significant number of cycles.

FIG. 6(A) shows exemplary code 620 of a two-dimensional array. In this code, temp is a two-dimensional array, and the values of I and J are used to access an element of the array. If the analysis shows that I is a varying variable and J is a uniform variable, the second technique can generate efficient code using a combination of the divide and conquer strategy and conditional select (CSEL) instructions.

FIG. 6(B) shows exemplary generated code 640. In the generated code, V, W, U, and X represent the elements at temp[0][0], temp[1][0], temp[2][0], and temp[3][0], respectively.

The divide and conquer strategy is applied to the uniform variable J, recursively dividing the range of possible values and generating nested conditional statements. This approach reduces the number of comparisons needed to determine the appropriate row of the two-dimensional array.

For the varying variable I, conditional select (CSEL) instructions are used to handle the divergent control flow. The CSEL instructions select the appropriate element (V, W, U, or X) based on the value of I for each thread. This avoids the need for explicit branching and minimizes the impact of divergent control flow on performance.

To generate this efficient code, the second technique relies on several components:

- 1. Front-end metadata derived from types: The compiler's front-end provides metadata about the types and dimensions of the arrays, which is used to guide the code generation process.
- 2. Uniform variable analysis: The technique uses uniform variable analysis algorithms, such as those available in the LLVM compiler infrastructure, to determine which variables are uniform across all threads.
- 3. Induction variable analysis and scalar evolution analysis: These analyses help in identifying and optimizing loop-related variables and expressions, enabling more precise code generation.

By combining these components, the second technique can generate efficient code that minimizes the cost of each scalarized operation (load or store) by using the divide and conquer strategy for uniform variables and conditional select instructions for varying variables.

This technique is particularly beneficial for multi-dimensional arrays, where one dynamic index is uniform across threads, and the other is divergent. The divide and conquer strategy can be applied to the uniform index, while the divergent index is handled using conditional select instructions.

Furthermore, this technique is highly applicable in scenarios where memory accesses are expensive, such as in low-power GPUs with limited cache memory. In such cases, a nest of branches generated by the divide and conquer strategy may be cheaper than accessing the stack memory directly, leading to improved performance and reduced energy consumption.

[[Summary]]

As described supra, certain features of the second technique are:

- 1. Efficient support for different kinds of aggregates, such as arrays of structures and multidimensional arrays in stack memory and internal constant buffers. The second technique uses “access vector metadata,” which preserves the structure's type information in the compiler's intermediate representation. This metadata consists of a three-tuple per dimension of an array: (Offset, Length, Stride). By maintaining this information, the compiler can generate precise conditions for advanced data types, resulting in more efficient code.
- 2. Precise handling of nested aggregate data types. The access vector metadata allow the compiler to handle nested data structures effectively, as it retains the necessary information about field offsets, array lengths, and structure sizes. This enables the compiler to generate optimized code for complex data types, reducing the number of unnecessary conditional statements.
- 3. Support for multiple stores and loads. The second technique uses an SSA-based algorithm that supports any control flow. The SSA algorithm, combined with the access vector metadata, enables the compiler to handle multiple stores and loads efficiently. It performs data flow analysis to propagate the values correctly across different control flow paths.
- 4. Support for multi-dimensional arrays and utilization of uniformity behavior. The second technique extends the access vector metadata to handle multi-dimensional arrays naturally. It also leverages the analysis of uniform and varying variables in GPU workloads to generate efficient code. When the index variable is known to be uniform across all threads, the compiler can apply a divide-and-conquer strategy to reduce the number of comparisons needed. For varying variables, the compiler generates code using conditional select instructions to minimize the impact of divergent control flow.
- 5. Shader, hardware, and graphics API agnostic solution. The second technique are generic and applicable to various GPU workloads, regardless of the specific shader type (compute, vertex, fragment), hardware architecture (as long as it supports conditional select instructions), or graphics API (OpenGL, DirectX, Vulkan, Metal).

[[Two-Stage]]

The second technique may include two main stages:

- Stage 1: Metadata insertion procedure in the compiler's front-end
- Stage 2: Generation of oracle conditions on the compiler's middle-end intermediate representation

In the first stage, the metadata are inserted into the compiler's front-end. This metadata insertion procedure may be performed on the Abstract Syntax Tree (AST) or an equivalent high-level Intermediate Representation (IR). One example of such an IR is the SPIR-V intermediate representation, which is commonly used for representing Vulkan shaders in the compiler.

The metadata inserted in this stage provides information about the structure and layout of the data types, such as arrays of structures and multi-dimensional arrays. This metadata, referred to as “access vector metadata,” may include a three-tuple per dimension of an array: (Offset, Length, Stride). The access vector metadata preserves the structure's type information in the compiler's intermediate representation. By maintaining this information, the compiler can generate precise conditions for advanced data types in the later stages of the invention.

[[Stage 2: Generation of Oracle Conditions]]

The second stage of the second technique involves generating oracle conditions on the compiler's middle-end intermediate representation. This stage utilizes the metadata inserted in Stage 1 to generate efficient and precise oracle conditions for handling multiple stores and loads.

The oracle conditions may be generated using an SSA-based algorithm that supports arbitrary control flow. By combining the SSA form with the access vector metadata, the algorithm can effectively handle scalarization in the presence of complex control flow structures.

The SSA-based algorithm performs data flow analysis to propagate the values correctly across different control flow paths. It takes into account the access vector metadata to generate precise oracle conditions for each memory access. These oracle conditions determine which register to use based on the specific register location being accessed, as determined by the access vector metadata.

The generation of oracle conditions in Stage 2 is performed on the compiler's middle-end intermediate representation, such as LLVM IR. LLVM is a widely used compiler infrastructure that provides a powerful and flexible intermediate representation for optimization and code generation.

[[Stage 1: Metadata Insertion in the Compiler's Front-End]]

Stage 1 of the second technique involves inserting metadata into the compiler's front-end. This metadata insertion procedure is performed on the Abstract Syntax Tree (AST) or an equivalent high-level Intermediate Representation (IR). One example of such an IR is the SPIR-V intermediate representation, which is commonly used for representing Vulkan shaders in the compiler.

One example using OpenGL and SPIR-V is shown below:

OpenGL code for a store operation:

t10[int(u12)].BgdMinCoc = 16384.0;

SPIR-V intermediate form for this store operation in the front-end:

%77 = OpLoad %uint %u12

%78 = OpBitcast %int %77

%80 = OpAccessChain %_ptr_Function_float %t10 %78 %int_2

OpStore %80 %float_16384

In the SPIR-V representation, the array access is represented using the OpAccessChain operation (%80 in the example). The data type is %_ptr_Function_float, the constant offset is % int_2 (just the number 2), and the array index is dynamic and held in %78, which corresponds to u12 in the OpenGL code.

From the data type held in the compiler's symbol table and the constant offset, the compiler can fully obtain the access vector metadata (offset, stride, and array length). The result of Stage 1 is an intermediate form instruction with access vector metadata:

- %106=store align (4)<1×f32> %105, %102, access_vector(8, 3, 24)

In this example, 8 is the offset, 3 is the length, and 24 is the stride. The value %105 is stored at address %102. The sequence of addresses that correspond to an access vector metadata is calculated as:

Array_Base
⁢
_Pointer

+
Offset
+

l
×
Stride

,

by
⁢

taking
⁢

l
⁢

from

[

0
,

Length

)

For the above example, the integers being added to the array's pointer are:

8
+

0
×
2
⁢
4

,

8
+

1
×
2
⁢
4

,

8
+

2
×
2
⁢
4

These correspond to the following legal addresses possible for the store operation:

- 8+Base, 32+Base, 56
- +Base, where Base is the starting address of the array

As such, from every load/store operation with access vector metadata, the compiler can obtain the complete set of addresses that are possible at runtime during compile time.

The process of obtaining the access vector metadata involves walking the values in the OpAccessChain instruction to find the structure and extracting the necessary information. The SPIR-V representation provides the structure type information, the dynamic index, and the constant offset directly. By examining these values, the compiler can compute the access vector(e.g., access_vector(8, 3, 24)) based on the data type of t10 (which gives the length), the dynamic index %78 (indicating a dynamic access), and the constant offset % int_2 (specifying the field offset).

By attaching the metadata to the instructions themselves, the necessary information is readily available for subsequent stages of the compilation process, enabling more efficient and precise code generation.

While the example shown here uses the SPIR-V intermediate representation, the same idea applies to other front-end representations, such as abstract syntax trees used in compilers like Clang or ARM. The specific method for calculating the access vector may vary depending on the format of the intermediate representation, but the overall concept remains the same: examining the data types, offsets, and constants to determine the access vector metadata.

[[Symbol Table and Access Vector Metadata]]

The symbol table in a compiler is a data structure that stores information about the identifiers used in a program, such as variable names, function names, and data types. In one example, the below code defines a structure named ‘myStruct’ with two float fields, ‘Max’ and ‘Min’. An array named ‘t10’ has three elements of type ‘myStruct’.

struct myStruct {

float Max;

float Min;

} t10[3];

Table 1 is a symbol table containing information about the myStruct data type and the t10 array.

TABLE 1

Symbol table representation of the t10 array

Array-access

Location in

and field
Array-
Field-
bytes from

name
index
offset
start of array

t10[0].Max
0
0
0

t10[0].Min
0
1
4

t10[1].Max
1
0
8

t10[1].Min
1
1
12

t10[2].Max
2
0
16

t10[2].Min
2
1
20

Each row in the table represents a specific element of the t10 array, identified by its array index and field name. The field offset indicates the position of the field within the myStruct data type, and the location in bytes from the start of the array shows the actual memory address of the element relative to the beginning of the array.

To access a field of any array element at index x, the following formula can be used:

x
*

sizeof
⁡
(
myStruct
)

+

field_offset
⁢
_in
⁢
_bytes

For example, to access t10[2].Max, the formula would be:

2
*
8

+
4

Here, sizeof (myStruct) is 8 bytes (assuming 4 bytes for each float), and the field_offset_in_bytes for Max is 4.

The access vector metadata, as described supra, is added by the compiler's front-end to each load and store operation. It contains three components: Offset, Stride, and Length. Offset corresponds to the field_offset within the struct. Stride corresponds to the sizeof (myStruct). Length is the total length of the array.

This access vector metadata is not limited to one-dimensional arrays; it also extends to multidimensional arrays. By providing this metadata, the compiler can generate more efficient code for accessing array elements and perform optimizations such as register promotion, even in the presence of complex data structures like arrays of structs.

[[Oracle Insertion Phase]]

FIGS. 7(A) and (B) show exemplary code of an oracle insertion phase of the second technique. The oracle insertion phase in the second technique consists of two main algorithms that are applied sequentially: Algorithm-1 and Algorithm-2. These algorithms work together to collect load and store operations for each array and assign scalars to each address accessed using the access vector metadata.

Algorithm-1: Collect Load and Stores of Each Array

Algorithm-1 is responsible for collecting load and store operations that refer to each array under test. It takes the base address of an array (which is an offset to the stack pointer) as input and uses a def-use chain walker to find all the loads and stores that access the array.

FIG. 7(A) shows exemplary code 720 illustrating Algorithm-1. The algorithm maintains a worklist and a visited set, both initially empty. It starts by appending the base pointer of the array (A) to the worklist and adding it to the visited set. Then, it enters a loop that continues until the worklist is empty.

In each iteration, the algorithm pops an element (elt) from the worklist. If the element is a load or store operation, it checks if the operation has metadata associated with it. If the metadata is present, the load or store operation is added to the set of collected operations (ld_st). If the metadata is missing, the algorithm returns an empty set, indicating that the optimization cannot be performed for this array.

If the element is not a load or store operation, the algorithm iterates over each user (U) of the element. For each user that is not already in the visited set, the algorithm appends it to the worklist and adds it to the visited set.

Finally, the algorithm returns the set of collected load and store operations (ld_st) for the given array.

Algorithm-2: Create Scalars for Each Load/Store Slot in the Array

Algorithm-2 is executed immediately after Algorithm-1. Its purpose is to assign scalars to each address that is potentially accessed by the load and store operations collected in Algorithm-1. It uses the access vector metadata to determine the number of scalars needed and their corresponding addresses.

FIG. 7(B) shows exemplary code 740 illustrating Algorithm-2. The algorithm takes the base pointer of the array (A) and the set of collected load and store operations (ldst_set) as input. It returns two maps: Slot_map and Choices_map. A “slot” refers to a specific register location within the array that corresponds to a particular field of the structure at a given index. Each slot is identified by its offset from the start of the array and is assigned a unique scalar name (e.g., A1, A2, etc.).

For each load or store operation (ld_st) in the last_set, the algorithm extracts the offset, stride, and length from the operation's metadata. It then initializes an empty list called choices.

The algorithm iterates over the range [0, len), where len is the length obtained from the metadata. For each index I in this range, it calculates the slot by adding the offset to the product of stride and I. If the slot is not already present in the Slot_map, the algorithm generates a new name for the scalar using the generate_new_name( ) function and adds it to the Slot_map with the slot as the key.

The newly generated scalar name is appended to the choices list for the current load or store operation. After processing all the indices, the choices list is added to the Choices_map with the load or store operation (ld_st) as the key.

Finally, the algorithm returns the Slot_map and Choices_map. The Slot_map contains the mapping between each slot and its corresponding scalar name, while the Choices_map contains the list of scalar names that each load or store operation can potentially access.

These two algorithms work together to collect the necessary information for performing oracle insertion. Algorithm-1 identifies the relevant load and store operations for each array, while Algorithm-2 determines the scalars needed for each address accessed by those operations. This information is then used in subsequent steps of the oracle insertion process to generate efficient code for handling arrays of structures and other complex data types.

[[Example of Assigning Scalars to Array Elements]]

To illustrate how the second technique assigns scalars to each “slot” in the array based on the access vector metadata, consider the following example:

struct myStruct {

float Max;

float Min;

} t10[3];

In this example, myStruct is a structure containing two float fields, Max and Min, and t10 is an array of three elements of type myStruct.

Further, the structure in a particular array of structures used to store t[10] may have a different size from the size of myStruct. For example, the structure in the particular array may have a size of 12 bytes and contains 3 slots or scalars. The length of the particular array is 2.

Table 2 shows the assigned scalar names, corresponding array elements, and their locations in bytes from the start of the array.

Assigned scalar names and their corresponding array elements

Scalar name
Array element
Location in bytes from start of array

A1 (group 1)
t10[0].Max
0

A2 (group 2)
t10[0].Min
4

A3 (group 3)
t10[1].Max
8

A4 (group 1)
t10[1].Min
12

A5 (group 2)
t10[2].Max
16

A6 (group 3)
t10[2].Min
20

The scalar names A1 to A6 are assigned based on the access vector metadata for each load or store operation. The groups (group 1, group 2, group 3) represent different sets of oracle choices corresponding to specific offset, stride, and length values:

- group 1: Offset=0, Stride=12, Length=2
- group 2: Offset=4, Stride=12, Length=2
- group 3: Offset=8, Stride=12, Length=2

By applying the formula derived from the access vector metadata, the second technique determines the number of scalars required for the oracle-check for each load or store operation and the addresses they correspond to. This process filters the choices and reduces the set of elements to specific fields offset by a stride of 12, rather than considering all elements in the array.

The access vector metadata allows the compiler to generate more efficient code by focusing on the relevant fields and offsets, thereby reducing the number of oracle conditions needed for each load or store operation. This approach leads to more precise and optimized code generation for arrays of structures and other complex data types.

[[Oracle Insertion Algorithm for Stores]]

FIG. 8 shows exemplary code 820 of an oracle insertion algorithm for stores. The algorithm is responsible for generating the necessary oracle conditions and creating new SSA definitions for each store operation. This algorithm assists the second technique to optimize the handling of arrays of structures and other complex data types.

The algorithm takes four inputs:

- A: The base pointer of the array being processed.
- ldst_set: The set of load and store operations collected by Algorithm-1.
- Choices_map: A map that associates each load or store operation with its possible choices (i.e., the scalar names corresponding to the addresses it may access).
- Slot_map: A map that associates each slot (i.e., a specific register location within the array) with its corresponding scalar name.

The algorithm returns a map called New_definitions, which contains the new SSA definitions created for each store operation.

The algorithm iterates over each load or store operation (ld_st) in the ldst_set. If the operation is a load, it is skipped, as this algorithm focuses on handling stores. For each store operation, the algorithm retrieves the list of slots (slots) associated with that store from the Choices_map.

Next, the algorithm calculates the pointer difference (PtrDiff) between the store's pointer operand (ld_st.PointerOperand) and the base pointer of the array (A). This pointer difference represents the offset of the store operation from the start of the array. The InsertIRInst function is used to insert a new IR (Intermediate Representation) instruction of type POINTERDIFF, which calculates this offset.

The algorithm then initializes a SelectInst variable with a constant value of zero. This variable will be used to build the oracle condition for the store operation.

For each slot in the slots list, the algorithm performs the following steps:

- 1) It inserts a new IR instruction of type COMPARE to compare the current slot with the PtrDiff. This comparison determines whether the store operation is accessing the register location corresponding to the current slot.
- 2) It inserts a new IR instruction of type SELECT, which conditionally selects between the value being stored (ld_st.stored_value) and the current value of SelectInst, based on the result of the comparison. This step builds the oracle condition for the store operation.
- 3) It updates the SelectInst variable with the newly created SELECT instruction, effectively chaining the oracle conditions for each slot.
- 4) It adds a new entry to the New_definitions map, associating the scalar name corresponding to the current slot (Slot_map [slot]) with the updated SelectInst. This step creates a new SSA definition for the stored value at each relevant register location.

After processing all the slots for the current store operation, the algorithm moves on to the next store operation in the ldst_set.

Finally, the algorithm returns the New_definitions map, which contains the new SSA definitions created for each store operation. These new definitions represent the oracle conditions that determine which register locations are updated by each store, based on the pointer difference and the associated slots.

The oracle conditions generated by this algorithm are essentially conditional select instructions that choose between the new value being stored and the existing value at each relevant register location. By creating these oracle conditions and new SSA definitions, the algorithm enables the compiler to generate optimized code that efficiently handles stores to arrays of structures and other complex data types, even in the presence of unknown or dynamic access patterns.

The New_definitions map returned by this algorithm will be used in the subsequent step of handling load operations, where the appropriate SSA definitions will be selected based on the load's pointer operand and the associated slots. The correct values are read from memory, taking into account the updates made by the store operations.

As such, the oracle insertion algorithm for stores enables efficient and precise handling of complex data structures in the presence of unknown or dynamic access patterns.

[[Oracle Insertion Algorithm for Loads]]

FIG. 9 shows exemplary code 820 of an oracle insertion algorithm for loads. This algorithm is responsible for generating the necessary oracle conditions to select the appropriate values for each load operation based on the SSA definitions created by the store algorithm. This algorithm enables efficient and precise handling of load operations in the presence of complex data structures and unknown or dynamic access patterns.

The algorithm takes five inputs:

- A: The base pointer of the array being processed.
- New_definitions: A map containing the new SSA definitions created by the store algorithm for each relevant register location.
- Idst_set: The set of load and store operations collected by Algorithm-1.
- Choices_map: A map that associates each load or store operation with its possible choices (i.e., the scalar names corresponding to the addresses it may access).
- Slot_map: A map that associates each slot (i.e., a specific register location within the array) with its corresponding scalar name.

The algorithm iterates over each load or store operation (ld_st) in the last_set. If the operation is a store, it is skipped, as this algorithm focuses on handling loads. For each load operation, the algorithm retrieves the list of slots (slots) associated with that load from the Choices_map.

Next, the algorithm calculates the pointer difference (PtrDiff) between the load's pointer operand (ld_st.PointerOperand) and the base pointer of the array (A). This pointer difference represents the offset of the load operation from the start of the array. The InsertIRInst function is used to insert a new IR (Intermediate Representation) instruction of type POINTERDIFF, which calculates this offset.

The algorithm then initializes a SelectInst variable with a constant value of zero. This variable will be used to build the oracle condition for the load operation.

For each slot in the slots list, the algorithm performs the following steps:

- 1) It inserts a new IR instruction of type COMPARE to compare the current slot with the PtrDiff. This comparison determines whether the load operation is accessing the register location corresponding to the current slot.
- 2) It inserts a new IR instruction of type SELECT, which conditionally selects between the reaching definition of the current slot (SSAUpdater.get (Slot_map[slot], New_definitions[Slot_map[slot]])) and the current value of SelectInst, based on the result of the comparison. This step builds the oracle condition for the load operation.
- 3) It updates the SelectInst variable with the newly created SELECT instruction, effectively chaining the oracle conditions for each slot.

The reaching definition for each slot is obtained using the SSAUpdater.get function, which takes the scalar name of the slot (Slot_map [slot]) and the corresponding new definition from the New_definitions map. This function is typically provided by the compiler's SSA updating API, such as the SSAUpdater in LLVM.

By using the SSAUpdater.get function, the correct value is selected for each load operation based on the most recent definition of the corresponding register location. This maintains the correctness of the program in the presence of multiple stores and complex control flow.

After processing all the slots for the current load operation, the algorithm moves on to the next load operation in the ldst_set.

The oracle conditions generated by this algorithm are essentially conditional select instructions that choose between the reaching definitions of the relevant register locations based on the pointer difference and the associated slots. As such, the correct values are loaded from memory, taking into account the updates made by the store operations.

By utilizing the SSA form and the access vector metadata, the algorithm can generate efficient and precise code for load operations, even in the presence of unknown or dynamic access patterns. The oracle insertion algorithm for loads, in combination with the store algorithm and the access vector metadata, enables the second technique to effectively optimize code involving arrays of structures and other complex data types.

FIG. 10 is a flow chart 1000 illustrating the oracle insertion phase of the second technique. The oracle insertion phase consists of two main stages: collecting load and store operations for each array (Algorithm-1) and assigning scalars to each address accessed using the access vector metadata (Algorithm-2).

The flow chart begins with the compiler driver checking if there is a function to process (operation 1010). If there is a function to process, the driver checks if there is an array to process in the function (operation 1020).

If an array is found, the compiler applies Algorithm-1 (Find_Loads_Stores) to the array (operation 1030). Algorithm-1 walks through the def-use chain of the array pointer to locate all the loads and stores associated with the array. It returns a set of load and store operations (ldst_set) that access the array.

Next, the compiler applies Algorithm-2 (Assign_Scalars) to the array using the ldst_set obtained from Algorithm-1 (operation 1040). Algorithm-2 utilizes the access vector metadata to determine the number of scalars (slots) in the array and their corresponding addresses. It returns two maps: Slot_map, which maps each slot to its corresponding scalar name, and Choices_map, which maps each load or store operation to its possible choices (i.e., the scalar names corresponding to the addresses it may access).

After obtaining the Slot_map and Choices_map, the compiler performs oracle insertion for store operations using Algorithm-3 (Oracle_Insertion_Stores) (operation 1050). This algorithm generates the necessary oracle conditions and creates new SSA definitions for each store operation based on the ldst_set, Slot_map, and Choices_map. It returns a map called New_definitions, which contains the new SSA definitions created for each store operation.

Finally, the compiler performs oracle insertion for load operations using Algorithm-4 (Oracle_Insertion_Loads) (operation 1060). This algorithm generates the necessary oracle conditions to select the appropriate values for each load operation based on the New_definitions map, ldst_set, Slot_map, and Choices_map. It utilizes the SSA updating compiler APIs to obtain the reaching definitions for each load operation.

The oracle insertion phase enables efficient and precise handling of complex data structures, such as arrays of structures, in the presence of unknown or dynamic access patterns. By collecting load and store operations, assigning scalars to each accessed address, and generating oracle conditions, the second technique can optimize code involving these data structures and improve overall performance.

[[Pseudo Code for Oracle Insertion]]

The exemplary code snippets below demonstrate the pseudo code generated by the second technique for oracle insertion in the case of store and load operations. These code snippets illustrate how the access vector metadata is utilized to generate efficient and precise oracle conditions for handling complex data structures, such as arrays of structures.

More specifically, a set of load and store operations has a base array pointer % Base:

{

store align(4) <1 x f32> %105, %102, access_vector (8, 3, 24);

%106 = load align(4) %103, access_vector (8, 3, 24)

}

The access vector metadata for both the store and load operations is (8, 3, 24), where 8 represents the offset, 3 represents the length of the array, and 24 represents the stride (size of each array element).

For the store operation, the pseudo code with oracle conditions using the access vector metadata is as follows:

if %102 == %Base + 8 + (0 * 24):

v_0 = %105

else if %102 == %Base + 8 + (1 * 24):

v_1 = %105

else if %102 == %Base + 8 + (2 * 24):

v_2 = %105

In this code, the oracle conditions check the value of the pointer operand %102 against the calculated addresses based on the access vector metadata. The base address % Base is added to the offset (8) and the product of the array index (0, 1, or 2) and the stride (24). If the pointer operand matches one of these calculated addresses, the corresponding scalar variable (v_0, v_1, or v_2) is assigned the value being stored (%105).

Similarly, for the load operation, the pseudo code with oracle conditions is as follows:

if %103 == %Base + 8 + (0 * 24):

%106 = v_0

else if %103 == %Base + 8 + (1 * 24):

%106 = v_1

else if %102 == %Base + 8 + (2 * 24):

%106 = v_2

In this code, the oracle conditions check the value of the pointer operand %103 against the calculated addresses based on the access vector metadata, similar to the store operation. If the pointer operand matches one of these calculated addresses, the corresponding scalar variable (v_0, v_1, or v_2) is assigned to the destination operand %106.

[[Divide and Conquer Strategy with Conditional Selects]]

The second technique supports a divide and conquer strategy for generating efficient code when the index variable is known to be uniform across all threads. This strategy involves recursively dividing the range of possible index values into smaller subranges and generating nested conditional statements to determine the appropriate register to use.