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

[Robison, Arch]

Julia and OpenMP 4.0 have features where the user can bless a loop as 
having no memory dependences that prevent vectorization, thus enabling
vectorization of loops not amenable to compile-time or run-time 
dependence analysis.  LLVM currently has no metadata to express such,
as explained further below.

I'd like to propose new metadata that enables front-ends to tell the 
vectorizer that "memory dependences are not a problem for vectorization
widths up to n".  I'd appreciate any comments before I spend time 
prototyping it.

BACKGROUND
----------

OpenMP 4.0 allows the programmer to write something such as:

    void foo( float* a, int n, int k ) {
    #pragma omp simd safelen(8)
        for( int i=0; i<n; ++i ) {
            a[i] = 2*a[i+k];
    }

The pragma tells the compiler that the loop is safe to vectorize with 
a width of 8 or less.  (I.e. it's up to the programmer to ensure that 
either k<=-8 or k>=0.)  If safelen is missing, the safe width is 
unbounded.  The example is a trivial one for exposition.  Real examples 
may involve complex subscripting patters or scatter/gather patterns 
well beyond what is practical to check with a run-time check.

Julia has an @simd annotation with a similar purpose, but without a 
safelen parameter.  It's documented as not allowing any dependences, 
but that's because of the LLVM shortcoming addressed by this proposal. 

WHY CURRENT METADATA DOES NOT SUFFICE
-------------------------------------

There are currently two pieces of metadata that come close, but miss the 
desired semantics.

* llvm.loop.vectorize.width - hints at what vectorization width to use
  *if* the loop is safe to vectorize.  It does not specify that the 
  loop is safe to vectorize.

* llvm.mem.parallel_loop_access - indicates that accesses do not
  have a loop-carried dependence between them.  That's too broad a 
  brush, as it precludes loops that do have dependences (e.g. "forward 
  lexical dependences") that are nonetheless vectorizable.

PROPOSAL
--------

Add new metadata "llvm.loop.vectorize.safelen" that has a parameter n 
of type i32.  The metadata tells the vectorizer that the loop is safe 
to vectorize with any vectorization width less or equal to n.  The loop 
vectorizer is free to choose any vectorization width within that 
constraint.

- Arch D. Robison
  Intel Corporation