[llvm-dev] RFC: LoopIDs are not identifiers (and better loop-parallel metadata)

[Finkel, Hal J. via llvm-dev]

On 12/4/18 6:50 PM, Michael Kruse wrote:
> Dear LLVM community,
>
> LLVM IR has a concept of 'LoopID' [1] which is a misnomer:
>
> (a) LoopIDs are not unique: Any pass that duplicates IR will do it
> including its metadata (e.g. LoopVersioning) such that thereafter
> multiple loops are linked with the same LoopID. There is even a test
> case (Transforms/LoopUnroll/unroll-pragmas-disabled.ll) for multiple
> loops with the same LoopID.
>
> (b) LoopIDs are not persistent: Adding or removing an item from a
> LoopID can only be done by creating a new MDNode and assigning it to
> the loop's branch(es). Passes such as LoopUnroll
> (llvm.loop.unroll.disable) and LoopVectorize (llvm.loop.isvectorized)
> use this to mark loops to be not transformed multiple times or to
> avoid that a LoopVersioning original loop is transformed.
>
> The only mechanism in LLVM that uses LoopIDs as identifiers is
> llvm.mem.parallel_loop_access [2]. It is added to memory-accessing
> instructions and points to one or multiple LoopIDs it is parallel to.
> Because of (b), transformation passes can change a loop's llvm.loop
> metadata such that llvm.mem.parallel_loop_access may point to an
> orphaned LoopID.
>
> Patch [3] fixes this issue. Instead of instructions referencing the
> loops they are parallel to, it adds a new loop attribute
> "llvm.loop.parallel_accesses" that references the instructions. Any
> loop transformation that changes the loop metadata will by default
> carry-over the llvm.loop.parallel_accesses property and the
> information retained.
>
> Since global metadata cannot reference instructions, [3] also
> introduces a new distinct metadata type that represents a group of
> instructions. An instruction will reference the a group using the
> llvm.access.group metadata, and llvm.loop.parallel_accesses uses the
> access group MDNode to reference to the instructions.
>
> Currently, the metadata for parallel memory accesses looks like:
>
> loop:
>   load ... !llvm.mem.parallel_loop_access !0
>   br label %loop, !llvm.loop !0
>
> !0 = distinct !{!0}                                      ; 'LoopID'
>
> My suggestion uses this pattern instead:
>
> loop:
>   load ... !llvm.access.group !2
>   br label %loop, !llvm.loop !0
>
> !0 = distinct !{!0, !1}                                  ; 'LoopID'
> !1 = !{!"llvm.loop.parallel_accesses", !2}
> !2 = distinct !{}                                        ; access group
>
> Patch [4] modifies Clang to generate this kind of metadata. Accesses
> in the same loop nest level are assigned to the same access group.

I think that we should move forward with this solution. It will make
LLVM both more robust and most consistent in this regard:

 1. Robust: It will become less likely that we'll lose track of loops
marked as parallel because of an update to the loop ID. Given that any
change to the loop's properties (which happens, for example, when
user-requested transformations are performed) changes the metadata
identify of the loop id, this is not uncommon. As a result, we really
need the loop id to, in effect, point to the parallel access groupings
instead of the other-way around.

 2. Consistent: The only reason we need, AFAIK, the loop ids to be
distinct, semantically, is for parallel loop annotations in loop nests.
If I have loop-parallel annotations point at the loop ids, and loop ids
are not distinct, then there might be no way to distinguish an inner and
outer loop (and, thus, no way to make with respect to which level in a
loop nest a loop has been annotated as parallel). This new scheme
removes that requirement, and thus, the requirement that all loop ids
must be marked distinct.

>
>
> Fixing (a) and (b) instead would require much more work. For (a), any
> code that copies entire basic blocks (this includes the inliner since
> the same function can be inlined multiple times) would need to make a
> copy of the LoopID and update any llvm.mem.parallel_loop_access in the
> copy. For (b), in addition to MDNode::setOperand, we need a method to
> change the MDNode's size without changing its address. Currently,
> MDNode is optimized for an unchangeable number of operands.
>
> I suggest to stop seeing 'LoopID' as an identifier entirely, but to
> use it as a bag of loop attributes. Patch [5] updates the reference
> manual. We may also think about renaming LoopID in the source code,
> and dropping the 'distinct' and 'first item is self-reference'. The
> latter two were intended to avoid separate LoopIDs into into one
> because their content is identical, i.e. uphold (a). As we have seen,
> there are other reasons for loops to have identical LoopIDs. With
> patches [3,4], llvm.loop metadata can be collapsed (unlike access
> groups), thus the 'distinct' is not necessary anymore. Unfortunately,
> there is code in LLVM (and maybe elsewhere) that depends on LoopIDs'
> first item, i.e. we cannot get rid of it that easily.

I don't think it's worth changing this first element, unless we have
some other reason to do so.

 -Hal

>
>
> Regards,
> Michael
>
>
> [1] https://llvm.org/docs/LangRef.html#llvm-loop
> [2] https://llvm.org/docs/LangRef.html#llvm-mem-parallel-loop-access-metadata
> [3] https://reviews.llvm.org/D52116
> [4] https://reviews.llvm.org/D52117
> [5] https://reviews.llvm.org/D55290

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory