Method and apparatus for generating data parallel select operations in a pervasively data parallel system

1. A method of compiling program code, the method comprising:

receiving, by a compiler, an instruction stream including a plurality of instructions that form the program code, the instructions being related to both scalar and vector data;

forming, by the compiler, hyperblocks from the instruction stream thus providing an instruction stream with hyperblocks;

injecting, by the compiler, data parallel select instructions into the instruction stream with hyperblocks to form a modified instruction stream wherein conditional test and branch instructions are replaced with data parallel select instructions;

revising, by the compiler, the modified instruction stream to enhance execution of the data parallel select instructions by performing select promotion operations on the modified instruction stream, thus providing a revised modified instruction stream;

wherein performing select promotion operations includes:

identifying a program sequence in the modified instruction stream wherein a select operation is associated with two selection sources corresponding to two operations of the same type, the two selection sources including input operands, the select operation yielding a result computation; and

replacing the result computation of the select operation with at least one other select operation corresponding to a selection of at least one of the input operands, the output of the at least one other select operation feeding another operation of the same type;

and generating, by the compiler, vectorized code from the revised modified instruction stream.

2. The method of claim 1 , wherein the generating vectorized code step comprises generating single instruction multiple data (SIMD) code from the revised modified instruction stream.

3. The method of claim 1 , wherein the revising the modified instruction stream step further comprises performing select predicate combining operations on the modified instruction stream.

4. The method of claim 3 , wherein performing select predicate combining operations comprises:

identifying a first program sequence in the modified instruction stream wherein a first select operation feeds into a second select operation, and wherein an input value of the first select operation is the same as an input value of the second select operation, thus providing a shared input value; and

replacing the second select operation with a new select operation having an input value corresponding to all conditions under which the shared input value can be selected.

5. The method of claim 1 , wherein the revising the modified instruction stream step further comprises performing conditional store conversion operations on the modified instruction stream.

6. The method of claim 5 , wherein the injecting of data parallel select instructions comprises:

identifying in the modified instruction stream a store operation that corresponds to one conditional path in a hyperblock in the modified instruction stream, thus providing an identified store operation; and

replacing the identified store operation with a program sequence including a select operation that selects a stored data value based on a condition of the conditional path and the identified store operation.

7. The method of claim 1 , wherein the revising the modified instruction stream step further comprises performing conditional mask expansion operations on the modified instruction stream.

8. The method of claim 7 , wherein the injecting step comprises:

identifying in the instruction stream an assignment to a field of a value which corresponds to a wide data word;

aligning the value to a position corresponding to a position in the wide data word for updating purposes;

generating a select mask for a data parallel select operation wherein the select mask selects a first operand corresponding to non-assigned fields in the wide data word and a second operand corresponding to assigned fields in the wide data word; and

generating a select operation that selects from the wide data word and the aligned value under control of the select mask.

9. The method of claim 1 , wherein the revising the modified instruction stream step further comprises performing vector culling operations on the modified instruction stream.

10. The method of claim 9 , wherein the revising the modified instruction stream step comprises:

identifying a conditional operation in the modified instruction stream upon which to perform a vector culling optimization;

computing a culling condition on vector elements in the modified instruction stream;

generating a branch in the modified instruction stream to an alternate basic block containing code corresponding to a vectorized path in which all elements correspond to the culling condition; and

generating the alternate basic block containing a vectorized computation wherein all elements correspond to the culling condition.

11. A method of compiling program code, the method comprising:

receiving, by a compiler, an instruction stream including a plurality of instructions that form the program code, the instructions being related to both scalar and vector data:

forming, by the compiler, hyperblocks from the instruction stream thus providing an instruction stream with hyperblocks;

injecting, by the compiler, data parallel select instructions into the instruction stream with hyperblocks to form a modified instruction stream wherein conditional test and branch instructions are replaced with data parallel select instructions;

revising, by the compiler, the modified instruction stream to enhance execution of the data parallel select instructions by performing select sinking operations on the modified instruction stream, thus providing a revised modified instruction stream; and

wherein performing select sinking operations includes:

identifying a first program sequence in the modified instruction stream wherein at least one select operation of the first program sequence selects from two values that feed another operation exhibiting a type, the another operation yielding a result computation; and

replacing the result computation of the another operation with a second program sequence in which a select operation selects from two computed values, each of the two computed values corresponding to an operation of the type of the another operation;

and generating, by the compiler, vectorized code from the revised modified instruction stream.

12. A method of compiling program code, the method comprising:

receiving, by a compiler, an instruction stream including a plurality of instructions that form the program code, the instructions being related to both scalar and vector data;

forming, by the compiler, hyperblocks from the instruction stream thus providing an instruction stream with hyperblocks;

injecting, by the compiler, data parallel select instructions into the instruction stream with hyperblocks to form a modified instruction stream wherein conditional test and branch instructions are replaced with data parallel select instructions;

revising, by the compiler, the modified instruction stream to enhance execution of the data parallel select instructions by performing select fusion operations on the modified instruction stream, thus providing a revised modified instruction stream; and

wherein performing select sinking operations includes:

identifying a program sequence in the modified instruction stream wherein a first select operation provides an input value into a second select operation, wherein predicates of the first and second select operations select a subset of input operands of the first select and second select operation input values; and

replacing the second select operation with a select operation that selects from the subset;

and generating, by the compiler, vectorized code from the revised modified instruction stream.