Apparatus and method for optimizing scalar code executed on a SIMD engine by alignment of SIMD slots

Abstract

An apparatus and method for optimizing scalar code executed on a single instruction multiple data (SIMD) engine is provided that aligns the slots of SIMD registers. With the apparatus and method, a compiler is provided that parses source code and, for each statement in the program, generates an expression tree. The compiler inspects all storage inputs to scalar operations in the expression tree to determine their alignment in the SIMD registers. This alignment is propagated up the expression tree from the leaves. When the alignments of two operands in the expression tree are the same, the resulting alignment is the shared value. When the alignments of two operands in the expression tree are different, one operand is shifted. For shifted operands, a shift operation is inserted in the expression tree. The executable code is then generated for the expression tree and shifts are inserted where indicated.

1 . A method, in a data processing system, for performing a scalar operation, comprising: 
 identifying a scalar operation in source code;    generating an expression tree for the scalar operation, wherein the expression tree has leaf nodes corresponding to scalar operands of the scalar operation;    determining an alignment of the scalar operands in respective registers that store the scalar operands; and    generating executable code for the scalar operation based on the expression tree and the determined alignment of the scalar operands, wherein generating executable code for the scalar operation includes inserting shift instructions into the executable code based on the alignment of the scalar operands.    
   
   
       2 . The method of  claim 1 , further comprising: 
 propagating the alignment of the scalar operands up the expression tree; and    annotating the expression tree based on the propagation of the alignment of the scalar operands up the expression tree.    
   
   
       3 . The method of  claim 2 , wherein annotating the expression tree based on the propagation of the alignment comprises annotating selected nodes of the expression tree to identify shift operations to be performed with respect to the selected nodes.  
   
   
       4 . The method of  claim 3 , wherein the selected nodes are nodes where values associated with two or more child nodes in the expression tree are to be combined and the values have different alignments in their respective registers.  
   
   
       5 . The method of  claim 4 , wherein values of the selected nodes have alignments in their respective resultant registers corresponding to an alignment of the two or more child nodes after shifting is performed.  
   
   
       6 . The method of  claim 3 , wherein the shift operations are determined with reference to all other shift operations within a given region of the source code by means of an optimization process which attempts to find a minimum number of shift operations within the region of the source code.  
   
   
       7 . The method of  claim 6 , wherein the optimization process determines common sub-expressions of scalar operations and shift operations are selected such that for a number of instances of the common sub-expression a same shift operation is utilized.  
   
   
       8 . The method of  claim 3 , wherein at least one of the shift operations is a shuffle shift operation that propagates a scalar operand to all positions in a respective register such that the scalar operand may be used with more than one desired alignment.  
   
   
       9 . The method of  claim 1 , wherein the shift instructions that are inserted into the executable code are one of rotation shift instructions or shuffle shift instructions.  
   
   
       10 . A computer program product comprising a computer useable medium having a computer readable program, wherein the computer readable program, when executed on a computing device, causes the computing device to: 
 identify a scalar operation in source code;    generate an expression tree for the scalar operation, wherein the expression tree has leaf nodes corresponding to scalar operands of the scalar operation;    determine an alignment of the scalar operands in respective registers that store the scalar operands; and    generate executable code for the scalar operation based on the expression tree and the determined alignment of the scalar operands, wherein generating executable code for the scalar operation includes inserting shift instructions into the executable code based on the alignment of the scalar operands.    
   
   
       11 . The computer program product of  claim 10 , wherein the computer readable program further causes the computing device to: 
 propagate the alignment of the scalar operands up the expression tree; and    annotate the expression tree based on the propagation of the alignment of the scalar operands up the expression tree.    
   
   
       12 . The computer program product of  claim 11 , wherein the computer readable program causes the computing device to annotate the expression tree based on the propagation of the alignment by annotating selected nodes of the expression tree to identify shift operations to be performed with respect to the selected nodes.  
   
   
       13 . The computer program product of  claim 12 , wherein the selected nodes are nodes where values associated with two or more child nodes in the expression tree are to be combined and the values have different alignments in their respective registers.  
   
   
       14 . The computer program product of  claim 13 , wherein values of the selected nodes have alignments in their respective resultant registers corresponding to an alignment of the two or more child nodes after shifting is performed.  
   
   
       15 . The computer program product of  claim 12 , wherein the shift operations are determined with reference to all other shift operations within a given region of the source code by means of an optimization process which attempts to find a minimum number of shift operations within the region of the source code.  
   
   
       16 . The computer program product of  claim 15 , wherein the optimization process determines common sub-expressions of scalar operations and shift operations are selected such that for a number of instances of the common sub-expression a same shift operation is utilized.  
   
   
       17 . The computer program product of  claim 12 , wherein at least one of the shift operations is a shuffle shift operation that propagates a scalar operand to all positions in a respective register such that the scalar operand may be used with more than one desired alignment.  
   
   
       18 . The computer program product of  claim 10 , wherein the shift instructions that are inserted into the executable code are one of rotation shift instructions or shuffle shift instructions.  
   
   
       19 . An apparatus for performing a scalar operation, comprising: 
 a processor; and    a memory coupled to the processor, wherein the memory contains instructions which, when executed by the processor, cause the processor to:    identify a scalar operation in source code;    generate an expression tree for the scalar operation, wherein the expression tree has leaf nodes corresponding to scalar operands of the scalar operation;    determine an alignment of the scalar operands in respective registers that store the scalar operands; and    generate executable code for the scalar operation based on the expression tree and the determined alignment of the scalar operands, wherein generating executable code for the scalar operation includes inserting shift instructions into the executable code based on the alignment of the scalar operands.    
   
   
       20 . The computer program product of  claim 10 , wherein the instructions further cause the processor to: 
 propagate the alignment of the scalar operands up the expression tree; and    annotate the expression tree based on the propagation of the alignment of the scalar operands up the expression tree.