GCC Internals of Auto-Vectorization Print
Written by Chandra Kumar R   


Auto-vectorization does a set of analysis on loops and performs the transformation of scalar to vector. There are two phases in auto-vectorization. They are

  1. Analysis phase
  2. Transformation phase


1. Analysis phase

During the analysis phase, information on each statement in a loop is collected and stored. I.e. Each statement would have the data structure (stmt_vec_info) associated with it, that would hold the information collected during the analysis phase.

Also the overall information of the loop is collected during this phase and it would be stored in the data structure (loop_vec_info).

Hence in the analysis phase of the auto-vectorization, the information pertaining to loops and each statements inside the loops are collected and stored in following two data structures:

  • stmt_vec_info
  • loop_vec_info


2. Transformation phase

This phase does the vectorization using the information collected during the analysis phase.

This phase generates the vector statements for each scalar statements. Thus generated vector statements are inserted just before corresponding scalar statements.

Also a pointer to the newly generated vector statement is stored in the data structure 'stmt_vec_info' corresponding to the scalar instruction (for which the vector statement is generated). Thus stored pointer information is required for the transformation of next scalar instruction (that may use the operand defined by the previous instruction).

For example, consider the following sequence of scalar statement:

SSTMT1: b = arrayA [i]
SSTMT2: arrayC [i] =  b 


Note:
SSTMT -> Scalar Statement
VSTMT -> Vector Statement



Lets see the steps that happens in transformation phase (assuming we have passed the analysis phase):

Step1:

Generate the vector statement for first scalar statement 'SSTMT1'. And insert it before 'SSTMT1'.

VSTMT1: Vb = VarrayA [i]
SSTMT1: b  = arrayA [i]
SSTMT2: arrayC [i] =  b 
Step2:

Store the pointer to VSTMT1 in the data structure 'stmt_vec_info' of 'SSTMT1'.

Step3:

Generate the vector statement for next scalar statement 'SSTMT2'. 'SSTMT2' uses the operand defined by previous instruction 'SSTMT1'. And hence during vectorization of 'SSTMT2', the transformation phase needs the operand information from previous vector statement 'VSTMT1'. So for that it uses the information stored at 'Step2'.

VSTMT1: Vb = VarrayA [i]
SSTMT1: b  = arrayA [i]
VSTMT2: VarrayC [i] =  Vb 
SSTMT2: arrayC [i]  =  b 
Step4:

Similarly after all the scalar statements are successfully transformed into vector statements, the scalar statements would become dead code which would be eliminated in the subsequent optimization passes.

VSTMT1: Vb = VarrayA [i]
VSTMT2: VarrayC [i] =  Vb