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

[Humphreys, Jonathan]

Well, having not understood the connection between lexical dependence and the openMP simd construct yesterday, I inquired in the openMP community.  If I understand the answer I got (from someone at Intel), the openMP simd construct is really asserting that no lexically backward dependences exist.  This is not at all obvious to me from reading the spec.

That answer seems to be in conflict with what you are saying below.

Thanks
Jon

-----Original Message-----
From: Robison, Arch [mailto:arch.robison at intel.com] 
Sent: Thursday, August 28, 2014 10:47 AM
To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

> Sorry for coming to the discussion so late.  I have a couple of questions/comments:

Actually, you're note is timely, because I'm planning to send out a patch (as soon as I update LangRef and rerun tests) that supports safelen but *not* lexical dependences.  I don't need the safelen for Julia, but having done the work and seeing that OpenMP needs it, feel that I should finish the work to contribute it.

Yes, safelen and lexical forward dependences are separable.  I was initially under the impression that to implement OpenMP 4.0 simd loops correctly, support for both safelen and lexical forward dependences were necessary.  Indeed, the Intel compiler supports forward lexical dependences in OpenMP 4.0 simd loops.  (Sophisticated vectorizers have to support them anyway for auto-vectorization.)  But upon closer reading, and discussion with the experts here, it became apparent that the OpenMP 4.0 spec talks about execution of SIMD instructions, but does not say much about how source code is mapped onto those instructions, so support for lexical dependences is not necessary for 4.0. 

Likewise, I'm dropping my experiment with supporting lexical forward dependences in Julia, though I'm mulling an alternative language-level solution.

> 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.  

Right.

> 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).

The parameter is best put on the loop instead of each access.  That way it can have different values for different loop levels.  I.e., each loop is marked with its relevant component of the minimum distance vector.

With respect to a more general mechanism, and perhaps more complete distance information, that seems worthwhile if there's real benefit to be obtained.  I'll leave that to others, though I'd be curious to see proposed designs.  I haven't explored the limits of LLVM's metadata format.  For instance, what's the best way to store a distance matrix as metadata?

- I agree with Hal's request that we don't use the name 'safelen'

I'm fine with the "minimum_dependence_distance" if everyone else is.

- Arch

-----Original Message-----
From: Humphreys, Jonathan [mailto:j-humphreys at ti.com] 
Sent: Wednesday, August 27, 2014 5:37 PM
To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

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