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

[Humphreys, Jonathan]

Sorry for coming to the discussion so late.  I have a couple of questions/comments:
 - I'm no openMP expert but I don't understand the relevance of lexically forward or backward dependence with respect to the safelen() metadata.  I would be surprised if the openMP spec based safelen() upon lexical ordering for the reasons that you are running up against.
 - I agree with Hal's request that we don't use the name 'safelen'.  I can think of many other 'safety' requirements for SIMD (such as alignment), and the proposed metadata is specifically addressing memory dependence.
 - what are the semantics for outer loop dependences in nested loops?  I believe that openMP restricts the usage of this clause to nested loops that are perfectly nested and collapsible.  We will be introducing this metadata in LLVM without such restrictions.
 - Assuming that lexical ordering is irrelevant to this discussion, it would be nice if we could build upon the llvm.mem.parallel_loop_access metadata rather than inventing more metadata.  I was thinking that you could add an additional parameter that specifies the minimum dependence distance.  It would be optional and if absent, would be infinite (which preserves existing semantics).
 - And having said that, I'm also wondering (but haven't thought any of it through) if instead of inventing metadata to address particular language features, we should instead invent a more general mechanism for expressing memory independence through metadata.  Then the expression of a language feature could be decomposed into basic dependence metadata.  There are many advantages to this.  It would be more precise (operation based vs loop based).  Being basic/lowlevel, passes that invalidate it (or enhance it) can do that at a fundamental level and not need to be aware of a specific language feature that might be implied in the name of the metadata.  And being more precise, it would be more robust because any pass that introduces memory operations would not have the metadata and so wouldn't inherit assertions that might not be true for it.

Jon

-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Robison, Arch
Sent: Thursday, August 21, 2014 2:17 PM
To: Hal Finkel; Renato Golin; Alexander Musman (alexander.musman at gmail.com)
Cc: LLVM Dev
Subject: Re: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Here's an attempt to nail down the annotation semantics with support for respecting forward lexical dependences. 

Each load, store, call, or invoke instruction can be labeled with !llvm.mem.vector_loop_access, which has two operands:
* The first operand is an integer denoting lexical position.  The positions need not be consecutive, and may contain duplicates.  
* The second operand is the same as the first operand to llvm.mem.parallel_loop_access.  It's second so that it can be omitted - see mention of inlining further below.
The LoopID can have "llvm.loop.safelen" metadata.

Here is an example with three accesses with positions {10, 15 17} and a safelen of 42.  

    define void @foo(float* %a, float* %b) {
    entry:
      br label %for.body

    for.body:                                         ; preds = %for.body, %entry
      ...
      %0 = load float* %arrayidx, !llvm.mem.vector_loop_access !{metadata i32 10, !0}
      ...
      %1 = load float* %arrayidx2, !llvm.mem.vector_loop_access !{metadata i32 15, !0}
      ...
      store float %add3, float* %arrayidx5, !llvm.mem.vector_loop_access !{metadata i32 17, !0}
      ...
      br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !0

    for.end:                                          ; preds = %for.body
      ret void
    }

    !0 = metadata !{metadata !0, metadata !1}
    !1 = metadata !{metadata !"llvm.loop.safelen", i32 42}

Let lex(x) denote the lexical position metadata for access x.  If two accesses A and B:
* Are marked with llvm.mem.vector_loop_access that reference a loop L AND
* lex(A)<lex(B) AND
* L has llvm.loop.safelen with value K
THEN for loop L, the dependence distance from B to A is at least K iterations.

When llvm.mem.vector_loop_access is used on a call/invoke instruction, any accesses therein inherit that lexical position.

Open issue: when inlining a callee with more than one memory access, the accesses will end up with the same lexical position, and thus lose the dependence distance clue.  I don't know how often this drawback would show up in practice.  A possibility is to allow the callee instructions to be annotated with a !llvm.mem.vector_loop_access that omits the LoopId operand, i.e. just has lexical position information.  Then inlining could be more clever.

- Arch Robison
  Intel Corporation

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev