[LoopSimplify] Update loop-metadata ID after loop-simplify splitting out new outer loop

[Narutoworld]

Summary

This patch tries to fix bug-57603.

LoopSimplify creates nested loop to canonicalize those who have more than one latches.
However, the current code forgets to update the loop metadata ID for the newly created loop.
As a result, more than one loop shares the same loop ID.
This patch aims to resolve this issue.

BTW. If it looks good, please help me to commit it.

[uabelho]

Thanks for the patch!

It surely seems to make the output less weird in that the outer and inner loop doesn't use the same metadata ID anymore.
However, it still keeps the metadata for the inner loop, and I'm not sure it should?

At least in our original case, the metadata does not make sense anymore for the inner loop.
There the metadata was information about the known minimum iteration count of the loop, and that info is not valid for the inner loop after the rewrite LoopSimplify does.
Possibly it's not even valid for the outer loop, I'm not sure.

[bjope]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

I'm no expert on the Loop metadata handling. But in some sense I'd consider the outer loop as the original loop (so keeping the old metadata on that loop seem correct, e.g. if it has been vectorizer, or if user has forced vectorization of that original loop etc).

However, I'm not sure if the metadata should be kept for the inner loop here. That is a sub-loop, and not sure what an optimization report should say about that loop (that was created by the compiler). And if the user has requested unrolling of the original loop with a factor X, and this loop simplify pass is run before unrolling, we now indicate that we want both the outer and inner loop to be unrolled by a factor X. That seem wrong to me. So maybe it would be more correct to just drop all metadata for the inner loop (except for the loop id).

On the other hand, hypothetically, if the metadata already indicates that the loop has been vectorized/unrolled etc, then we probably want to mark the inner loop as already having been optimized to avoid that it is optimized again. Or is that irrelevant here?

llvm/test/Transforms/LoopSimplify/update_separate_loop_metadata.ll

1

typo: outer

1

"Test that loop-simplify ..." ?

4

I guess this kind of verification could be sufficient.
Another idea is to use -passes='loop-simplify,print<loops> -o /dev/null 2>&1' and then check that the loop info printed identify two nested loops.

But maybe we want to check that the metadata "survives" as well (if the goal is that both loops should have the same metadata but identify as different loop). Then we need to CHECK the actual metadata as well (to see that both loops are annotated with "llvm.loop.usefulinfo").

48

No newline at end of file

[Narutoworld]

Hi Mikael
Thanks for the comment.

I used to think the most conservative option is to always keep original metadata.
However, in this case, the most conservative choice seems to remove all metadata other than its loop ID.

I think it might be a better design to drop all metadata of a loop which is touched by loop-simplify, I'd appreciate it if you could let me know your thoughts.

BTW, do you have the C/C++ code snippet which generate the IRs ? It would be more reasonable that different latches should hold different metadata even if they belongs to the same loop.

In D136102#3867406, @uabelho wrote:

Thanks for the patch!

It surely seems to make the output less weird in that the outer and inner loop doesn't use the same metadata ID anymore.
However, it still keeps the metadata for the inner loop, and I'm not sure it should?

At least in our original case, the metadata does not make sense anymore for the inner loop.
There the metadata was information about the known minimum iteration count of the loop, and that info is not valid for the inner loop after the rewrite LoopSimplify does.
Possibly it's not even valid for the outer loop, I'm not sure.

[Narutoworld]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

Thanks for your comment.

For the given testcase, the outer loop needs the llvm.loop.usefulinfo metadata not the inner loop, which happens to have it only because they were a single loop.

However, I don't think we can generalize this. And in fact, the loop-simplify pass tries to create the outer loop and keeps the remaining loop as before. It might be better to drop all metadata if we cannot prove they are valid.

I think it should be the vectorizer's job to mark a loop that has already been optimized .

[uabelho]

In D136102#3872160, @Narutoworld wrote:

Hi Mikael
Thanks for the comment.

I used to think the most conservative option is to always keep original metadata.
However, in this case, the most conservative choice seems to remove all metadata other than its loop ID.

I think it might be a better design to drop all metadata of a loop which is touched by loop-simplify, I'd appreciate it if you could let me know your thoughts.

BTW, do you have the C/C++ code snippet which generate the IRs ? It would be more reasonable that different latches should hold different metadata even if they belongs to the same loop.

The original C code looked roughly like

void foo()
{
    int i = 0;
    int j = 0;

    _Pragma("loop minitercount(1)")
    while (i < 10 || j != 5)
    {
        i++;
        if (i == 12)
        {
            j = 5;
        }
    }

    assert(i == 12);
}

note that the "minitercount" pragma is something we've added downstream, that does not exist in a normal clang.
When we saw this error it was with a non-standard opt pipeline, but after a bit of debugging we thought it looked like
loop-simplify behaved strange and wrote https://github.com/llvm/llvm-project/issues/57603
But I don't know really what the solution is or how different passes should handle metadata in general.

[bjope]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

I think it should be the vectorizer's job to mark a loop that has already been optimized .

That is true. But the question is how a pass like this should behave if in the input
a) a loop already is marked as having been vectorized/unrolled etc
b) a loop is marked as "force vectorize" or "force unroll X times" etc

In case (a) I think the metadata probably should be kept on the outer loop (and possibly added to the inner loops) The optimization has already been done and we do not want further vectorization/unrolling on any of the sub loops.

In case (b) I think the metadata probably should remain on the outer loop (which in this case is the full original loop?). But it should not be added to the inner loop (or else we might get unrolling by a factor X*X etc).

Anyway. I believe it would be correct to keep the original metadata on the outer loop.
Not quite sure about which metadata to put on the inner loop. Dropping all metadata (except the loop id) for the inner loop is perhaps good enough for this patch to just sort out the current issue that we get same loop id on both inner and outer loop, and I think adding the outer loops metadata to the inner loop could be worse than dropping the metadata on the inner loop.

So in other words, I think the patch should be updated to get this kind of semantics:

• replicate the original loops metadata to the new outer loop
• assign a new loop id to the inner loop

[Meinersbur]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

“LoopID” is a misnomer, the same LoopID can refer to the same loop. Otherwise every transformation that clones code (unroll, inline, LoopVersioning, LoopUnswitch, ...) whout have to specifically handle any llvm.loop that the cloned code contains. See LLVM Language Reference Manual.

I think the default behavior is just applying the same LoopID to both loops such as analytical information is preserved (e.g. isvectorized, parallel_accesses, ...). It may be argued this is not safe for all metadata since neither loops is quite the original and need to have a list of known loop metadata with the info whether is should apply to the inner loop (llvm.loop.unroll.enable, ..), the outer loop (?, can't think of one where this makes most sense), or both loops (isvectorized, parallel_accesses, llvm.loop.licm.disable, all the disable metadata, ...). and discard all unknown.

Some metadata definitely have different semantics when applied the outer loop (only). For instance, when (partial) unrolling an outer loop, it would give multiple copies of the inner loop (which makes the code more inefficient as it would most likely exceed the L1i cache), but not jam like llvm.loop.unroll_and_jam might do. llvm.loop.unroll.disable would still allow unrolling the inner loop, which is what the heuristic would most likely unroll.

[bjope]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

Alright, so the LoopID is not used as some sort of key in LoopInfo to identify a single loop. It just identifies the metadata associated with the loop (and several different loops could have identical metadata and share the same LoopID.

In practice I think that LoopVersioning, LoopUnswitch etc (almost?) always update the loop metadata in some way when versioning a loop (either using setLoopID directly, or using some helper such as addStringMetadataToLoop(), setLoopAlreadyUnrolled()). But given that text in the reference manual about llvm.loop not being unique to a single loop I guess that there are no guarantees for that (nor that it is enforced).

This reminds me of an old problem when stale llvm.loop was put on a non-latch branch after some transformation (or not applied to all latches). Then suddenly after some other transformations that llvm.loop accidentally happened to end up on a latch for a totally different loop. I think we wanted to add some protection in the verifier to detect misplaced llvm.loop metadata. but if I remember correctly that was complicated (maybe due to llvm.loop not being unique to a single loop so the we can't really say that it is misplaced unless it is in a non-latch block, or maybe it was just complicated to verify for other reasons).

[bjope]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

But then maybe https://github.com/llvm/llvm-project/issues/57603 isn't a bug then. If having the same llvm.loop id on both loops is OK, and even expected for this particular transform.

Downstream metadata such as "llvm.loop.usefulinfo" can of course not be updated by the upstream. So if that only apply to one or none of the loops after this transform the downstream maintainer need to find out where to hack into the code and add/remove metadata every time a loop is versioned/transformed. Usually we can look for places when setLoopID/addStringMetadataToLoop/setLoopAlreadyUnrolled/makePostTransformationMetadata etc are used to find such places.
But given the information that it is allowed to reuse the old loopID for new loops even when the loop shape is changed (such as number of iterations) there could also be a number of "hidden" scenarios when a new loop just get the same loopID as an existing loop even if it is a child-loop etc. Those will be much harder to find.
At least we know where we need to add a piece of code downstream for this particular case, to make a post transform metadata update for the loops involved related to "llvm.loop.usefulinfo".

[Narutoworld]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

Thanks @Meinersbur @bjope for your comment.

I think we agree on two points.

1. Since the loopID is not guaranteed to identify a unique loop. In this case, both loops can share the same loopID. There is no need to update LoopID metadata
2. To handle downstream feature such as "llvm.loop.usefulinfo", downstream code needs to handle it whenever a loop is transformed by passes such as loopVersioning, unroll or etc.

Since https://github.com/llvm/llvm-project/issues/57603 isn't a bug, I will close this patch.

[Meinersbur]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

336

In practice I think that LoopVersioning, LoopUnswitch etc (almost?) always update the loop metadata in some way when versioning a loop (either using setLoopID directly, or using some helper such as addStringMetadataToLoop(), setLoopAlreadyUnrolled()). But given that text in the reference manual about llvm.loop not being unique to a single loop I guess that there are no guarantees for that (nor that it is enforced).

They do it for the loops they are touching, but not the ones nested inside them. LoopUnroll even has test cases to ensure that the same LoopID is applied to cloned loops.

An even harder cases is inlining: The same function containing a loop might be inlined twice into another loop. The inliner is not supposed to depend on LoopInfo to update loop metadata (although it needs to update aliasing metadata).

This reminds me of an old problem when stale llvm.loop was put on a non-latch branch after some transformation (or not applied to all latches).

As not all passes are loop-aware, they may change the CFG such that a latch is not a latch anymore, then possibly merge with another BB that is the latch of another loop. We tried to fix some some of those instances, but it is difficult when you even don't know whether a BB is a latch because you don't want to depend on LoopInfo.

We actually discussed better designs, such as attaching the loop metadata to the header instead which is much more stable. However, at the moment metadata cannot be attached to basic blocks. I would be happy to review such patches if someone wants to put some work into it.

As @Narutoworld pointed out in https://discourse.llvm.org/t/how-to-preserve-loops-metadata-after-loopsimplify-transformation/66190, the best way might be to design the metadata to still work correctly after all the changes to the loop that might occur until reaching the pass that consumes it.

llvm/lib/Transforms/Utils/LoopSimplify.cpp

if (!BlocksInL.count(BB)) {
       --i;
     }
   }
 
   // Split edges to exit blocks from the inner loop, if they emerged in the
   // process of separating the outer one.
   formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA);
 
+  // Create new metadata ID for NewOuter loop
+  // keep other metadata attched before
+  BasicBlock *LatchBlock = NewOuter->getLoopLatch();
+  if (LatchBlock) {
+    unsigned LoopMDKind = LatchBlock->getContext().getMDKindID("llvm.loop");
+    Instruction *TI = LatchBlock->getTerminator();
+    if (TI) {
+      MDNode *LoopMD = TI->getMetadata(LoopMDKind);
+      if (LoopMD) {
+        // Save space for the self-referential LoopID.
+        SmallVector<Metadata *, 4> MDs = {nullptr};
+        for (unsigned i = 1; i < LoopMD->getNumOperands(); ++i)
+          MDs.push_back(LoopMD->getOperand(i));
+        MDNode *NewLoopID = MDNode::getDistinct(LoopMD->getContext(), MDs);
+        NewLoopID->replaceOperandWith(0, NewLoopID);
+        TI->setMetadata(LoopMDKind, NewLoopID);
+      }
+    }
+  }
+
   if (PreserveLCSSA) {
     // Fix LCSSA form for L. Some values, which previously were only used inside
     // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
     // in corresponding exit blocks.
     // We don't need to form LCSSA recursively, because there cannot be uses
     // inside a newly created loop of defs from inner loops as those would
     // already be a use of an LCSSA phi node.
     formLCSSA(*L, *DT, LI, SE);

llvm/test/Transforms/LoopSimplify/update_separate_loop_metadata.ll

+; Tests loop-simplify updates the newly created outter loop metadata with
+; a new loop id and keeps other MDNode as before.
+
+; RUN: opt < %s -passes=loop-simplify -S | FileCheck %s
+; CHECK-LABEL: while.body.thread:
+; CHECK: br label %while.cond, !llvm.loop !5
+; CHECK-LABEL: while.body:
+; CHECK: br label %while.cond.outer, !llvm.loop !7
+
+define i16 @foo() {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body.thread, %while.body, %entry
+  %i.0 = phi i16 [ 0, %entry ], [ %inc4, %while.body.thread ], [ %inc, %while.body ]
+  %j.0 = phi i16 [ 0, %entry ], [ %j.0, %while.body.thread ], [ %spec.select7, %while.body ]
+  %cmp = icmp slt i16 %i.0, 10
+  br i1 %cmp, label %while.body.thread, label %lor.end
+
+while.body.thread:                                ; preds = %while.cond
+  %inc4 = add nsw i16 %i.0, 1
+  br label %while.cond, !llvm.loop !5
+
+lor.end:                                          ; preds = %while.cond
+  %cmp1.not = icmp eq i16 %j.0, 5
+  br i1 %cmp1.not, label %while.end, label %while.body
+
+while.body:                                       ; preds = %lor.end
+  %inc = add nuw nsw i16 %i.0, 1
+  %cmp2 = icmp eq i16 %inc, 12
+  %spec.select7 = select i1 %cmp2, i16 5, i16 %j.0
+  br label %while.cond, !llvm.loop !5
+
+while.end:                                        ; preds = %lor.end
+  ret i16 %i.0
+}
+
+!llvm.module.flags = !{!0, !1, !2, !3}
+!llvm.ident = !{!4}
+
+!0 = !{i32 7, !"Dwarf Version", i32 4}
+!1 = !{i32 2, !"Debug Info Version", i32 3}
+!2 = !{i32 1, !"wchar_size", i32 1}
+!3 = !{i32 7, !"frame-pointer", i32 2}
+!4 = !{!"clang version 16.0.0.prerel"}
+!5 = distinct !{!5, !6}
+!6 = !{!"llvm.loop.usefulinfo"}                   ; MDString used to represent any metadata
 No newline at end of file