[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

[Robison, Arch]

> Concatenation unrolling is an interesting case, we'll need to think about that.

I played with unrolling on paper.  With per-access order information, concatenation unrolling works fine as long as it copies the order information, in the sense that the resulting order information correctly indicates that the loop is no longer trivially vectorizable. 

For example, consider a loop body with two accesses per iteration:

    #pragma omp simd
    for(int i=0; i<4; ++i) {
        ...access Xi...
        ...access Yi...
     }

Preservation of forward lexical dependencies requires that for two iterations j and k with j<k, we have to guarantee that Xj happens before Xk.  Before unrolling, the accesses will be marked with positions A and B, with A<B.  Now partially unroll by a factor of 2.  We have (please pardon the informal notation):

    for(int i=0; i<4; i+=2 ) {
         ...access Xi...marked with A
         ...access Yi...marked with B
         ...access X(i+1)...marked with A
         ...access Y(i+1)...marked with B    }
    }

Now there is an out-of-order sequence in the middle of ABAB, so the vectorizer has to punt.  But that's good, because the sequence really is no longer trivially safe to vectorize since it would not preserve the constraint "X1 must happen before Y2" that was present in the original code.

- Arch D. Robison
  Intel Corporation