[unified-autovect:,1b/N] Instruction tile and grammar creation.

Hi Richard,

This is regarding the implementation of auto-vectorization based on my talk titled "Improving the effectiveness and generality of GCC auto-vectorization" in GNU Tools Cauldron 2015.

I have applied previous patches in branch 'unified-autovect' which generates primitive reorder tree (PRT) for load/store operations, and performs few optimizations to ensure optimal PRT is available for pattern matching. The options to enable unified auto-vectorization are '-ftree-vectorize -fopt-info-vec-all=file.txt -O2 -ftree-loop-vectorize-unified'. 

Now I am working on pattern matcher for PRT using bottom up rewrite parsing system (BURS) as described in "BURS Automata Generation" by Todd Proebsting. The paper describes an algorithm to generate BURS transition tables for cost effective pattern matching of complex target instructions. It takes target instructions represented in context free grammar in normal form as input, and generates transition table at build time of the compiler.

We have divided this problem into 3 parts:
1. Grammar creation for permute instructions of desired target at build time.
2. Transition table generation, and compile time executable code generation at build time.
3. Pattern matching code at compile time.

The patch I have attached addresses 1st part.

As number of states in automata increase exponentially for operators to be supported, I wanted to restrict the operators under consideration for BURS automata to be generated. As scalar to vector translator for arithmetic and logical instructions is already in place in GCC, and those operands do not play any role in permute order creation, the BURS is generated only for permute operators. For all other operators, GCC's current framework is to be used for code generation.

Hence, the only operators that are supported by the automata are
 ILV_2 : Interleave contents of 2 registers of size x and generate register of size 2x.
 EXTR_2,0   : Extract even elements from register of size x and generate register of size x/2
 EXTR_2,1  : Extract odd elements from register of size x and generate register of size x/2

Also, the number of states also depend upon the leaves in grammar. Hence, we are restricting the grammar to have 3 leaves namely REG, MEM and CONST.

We have defined new macro TARGET_VEC_PERM_CONST_ORDER which takes target supported permute orders as input in struct vec_perm_order_spec.

Current patch constructs instruction tiles for the target from this macro and optimizes those tiles using k-arity promotion reduction and redundancy elimination to have optimal PRT per instruction. It then generates context free grammar in normal form which can then be accepted by BURS algorithm to construct transition table.

There are multiple issues that need to be handled to support permute instructions across all architectures:
1. Constraints on input/output operands : We allow permutations on memory as well as registers to allow strided load/store and register permutes.
2. Different vector sizes supported : Each vector size needs to be enlisted in the macro in order to add support for that vector type.
3. Conditions under which the instruction is available : Like the condition field in RTL in md patterns.
4. Arity of permute operation : Multiple input single output model is supported.
5. Default rules to be generated for grammar to be complete : We need to identify default rules that are to be generated for pattern matcher so that the grammar will be complete. We have added
     goal --> reg              
     goal --> mem           
     reg --> mem            
     reg --> const           
     mem --> reg   
     mem --> const
       :
       :
     reg_32 --> REG  
     reg_16 --> REG  
     reg_8 --> REG    
     reg_4 --> REG    
     reg_2 --> REG     
     reg -> reg_2    
     reg -> reg_4            
     reg -> reg_8       
     reg -> reg_16         
     reg -> reg_32          
       :
       :
     mem --> MEM             
     const --> CONST           
     reg --> EXTR_2,0 (reg)    
     reg --> EXTR_2,1 (reg)    
     reg --> ILV (reg, reg)    

As we create 1 instruction tile per permute order in TARGET_VEC_PERM_CONST_ORDER, more detailed the macro,  more accurate the pattern matcher becomes.

Interestingly, even though different entries are created for different vector sizes, as and when possible, single tile is created for all vector sizes.
eg: In generated file insn-vect-inst-tiles.h which I have attached as sample, tile for permute order
permute order -  0  16  2  18  4  20  6  22  8  24  10  26  12  28  14  30 
ILV_2 (
  EXTR_2,0 (PHR:0) , 
  EXTR_2,0 (PHR:1))

is same as that for
permute order -  0  8  2  10  4  12  6  14 
ILV_2 (
  EXTR_2,0 (PHR:0) , 
  EXTR_2,0 (PHR:1))

This can be useful for SVE like extensions where vector size can be dynamic.

Richard, can you please see if this looks correct, or do I need additional information to successfully generate pattern matcher automatically?

Also, can you please comment on usability or scalability of this approach across all the architectures or point me to appropriate people in the group with whom I can discuss target specific vectorization issues?

- Thanks and regards,
  Sameera D.

[unified-autovect:,1b/N] Instruction tile and grammar creation.

Commit Message

Patch