Handle llvm.loop metadata in SplitCriticalEdges.

[jdoerfert]

Summary

Loop ID metadata (llvm.loop) might get falsified if we split critical
backedges. This patch ensures that only a valid annotation survives
and is attached to the correct branch instruction which can be the old
or the new one.

Four of the five test cases check for all different situations which
can arise when we split an edge annotated with llvm.loop metadata and
when LoopInfo is present. The fifth checks that we remove such metadata
in case LoopInfo is not present as everything else might invalidate the
annotation.

[jdoerfert]

Added test cases and implemented all possible cases an edge with annotations could be splitted.

[grosser]

Is this patch still relevant? I remember there was a discussion with Hal and Andrew on llvm-commits. What was the result?

[grosser]

I am just going through my open patches. I already asked earlier. Johannes, is this patch still relevant?

[jdoerfert]

Seems not relevant to ppl.

lib/Transforms/Utils/BreakCriticalEdges.cpp

BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
 
   // Create a new basic block, linking it into the CFG.
   BasicBlock *NewBB = BasicBlock::Create(TI->getContext(),
                       TIBB->getName() + "." + DestBB->getName() + "_crit_edge");
   // Create our unconditional branch.
   BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
   NewBI->setDebugLoc(TI->getDebugLoc());
 
+  // Reset the llvm.loop metadata (if present) and adjust it later if LoopInfo
+  // is available. This ensures that neither branch carries falsified
+  // llvm.loop metadata.
+  MDNode *LoopMD = TI->getMetadata("llvm.loop");
+  if (LoopMD)
+    TI->setMetadata("llvm.loop", nullptr);
+
   // Branch to the new block, breaking the edge.
   TI->setSuccessor(SuccNum, NewBB);
 
   // Insert the block into the function... right after the block TI lives in.
   Function &F = *TIBB->getParent();
   Function::iterator FBBI = TIBB;
   F.getBasicBlockList().insert(++FBBI, NewBB);
 
if (Loop *TIL = LI->getLoopFor(TIBB)) {
       // LCSSA form was updated above for the case where LoopSimplify is
       // available, which means that all predecessors of loop exit blocks
       // are within the loop. Without LoopSimplify form, it would be
       // necessary to insert a new phi.
       assert((!P->mustPreserveAnalysisID(LCSSAID) ||
               P->mustPreserveAnalysisID(LoopSimplifyID)) &&
              "SplitCriticalEdge doesn't know how to update LCCSA form "
              "without LoopSimplify!");
+
+      // We removed llvm.loop metadata earlier as we do not know if it is still
+      // valid for the old and new branch respectively. If it was present at the
+      // original (old) branch we check if the new branch should carry it from
+      // now on or if we should reattach it to the old branch. In either case we
+      // will check if any remaining successor of the old branch is a loop
+      // loop header. Afterwards, we check if the new branch destination block
+      // is a loop header. Possible outcomes:
+      //  1) The old branch but not the new branch may jump to a loop header.
+      //     ==> We reattach the loop ID to the old branch.
+      //  2) The new branch but not the old branch may jump to a loop header.
+      //     ==> We attach the loop ID to the new branch.
+      //  3) Both branches (new and old) may jump to a loop header.
+      //     ==> We won't attach the loop ID to either one as we cannot
+      //         guarantee which one it was for. Other annotations (e.g.,
+      //         llvm.mem.parallel_loop_access) could be invalid if we choose
+      //         the wrong one.
+      //  4) Neither branch may jump to a loop header.
+      //     ==> We won't attach the loop ID since it was invalid before.
+      if (LoopMD) {
+        bool NewBrJumpsToHeader = LI->isLoopHeader(DestBB);
+        bool OldBrJumpsToHeader = false;
+        for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
+          BasicBlock *SuccBB = TI->getSuccessor(i);
+          if (SuccBB == DestBB || !LI->isLoopHeader(SuccBB))
+            continue;
+          OldBrJumpsToHeader = true;
+          break;
+        }
+
+        // Case 1)
+        if (OldBrJumpsToHeader && !NewBrJumpsToHeader)
+          TI->setMetadata("llvm.loop", LoopMD);
+        // Case 2)
+        if (NewBrJumpsToHeader && !OldBrJumpsToHeader)
+          NewBI->setMetadata("llvm.loop", LoopMD);
+        // Case 3) and 4) are noops.
+      }
     }
   }
 
   return NewBB;
 }

test/Transforms/Util/break-critical-edges-loop-metadata.ll

+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Check that the new loop backedge (after we split critical edges)
+; will carry the same llvm.loop annotation as the old (critical) backedge.
+
+define void @jd(i1 %b, i32* nocapture %A) {
+entry:
+  br i1 %b, label %loop.exit, label %loop.header
+
+loop.header:                             ; preds = %loop.header, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop.header ]
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvar
+  %tmp = trunc i64 %indvar to i32
+  store i32 %tmp, i32* %arrayidx, align 4
+  %indvar.next = add nsw i64 %indvar, 1
+  %exitcond = icmp eq i64 %indvar.next, 512
+
+; This is a critical edge for both destination blocks, thus critical edge
+; splitting will create two new blocks one to jump to %inner.loop.header
+; and one to jump to %loop.exit. We verify only the former keeps the
+; loop ID annotation.
+
+  br i1 %exitcond, label %loop.exit, label %loop.header, !llvm.loop !0
+; CHECK:     br label %loop.header, !llvm.loop !0
+; CHECK-NOT: br label %loop.exit, !llvm.loop
+
+loop.exit:                                  ; preds = %loop.header
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}

test/Transforms/Util/break-critical-edges-loops-metadata.ll

+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Check that the new loop backedges (after we split critical edges)
+; will carry the same llvm.loop annotation as the old (critical) backedges.
+
+define void @jd(i32* nocapture %A) {
+entry:
+  br label %outer.loop.header
+
+outer.loop.header:                            ; preds = %loop_exit3, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar_next, %loop_exit3 ]
+  %p_tmp7 = shl i64 %indvar, 9
+  br label %inner.loop.header
+
+inner.loop.header:                             ; preds = %inner.loop.header, %outer.loop.header
+  %indvar4 = phi i64 [ 0, %outer.loop.header ], [ %indvar_next5, %inner.loop.header ]
+  %p_tmp = add nsw i64 %indvar4, %indvar
+  %p_tmp8 = add nsw i64 %indvar4, %p_tmp7
+  %p_arrayidx = getelementptr inbounds i32* %A, i64 %p_tmp8
+  %p_tmp9 = trunc i64 %p_tmp to i32
+  store i32 %p_tmp9, i32* %p_arrayidx, align 4
+  %indvar_next5 = add nsw i64 %indvar4, 1
+  %exitcond = icmp eq i64 %indvar_next5, 512
+; This is a critical edge.
+  br i1 %exitcond, label %loop_exit3, label %inner.loop.header, !llvm.loop !0
+; CHECK: br label %inner.loop.header, !llvm.loop !0
+
+loop_exit3:                                 ; preds = %inner.loop.header
+  %indvar_next = add nsw i64 %indvar, 1
+  %exitcond1 = icmp eq i64 %indvar_next, 1024
+; This is a critical edge.
+  br i1 %exitcond1, label %loop_exit, label %outer.loop.header, !llvm.loop !1
+; CHECK: br label %outer.loop.header, !llvm.loop !1
+
+loop_exit:                                  ; preds = %loop_exit3
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}
+!1 = metadata !{metadata !1}

test/Transforms/Util/break-critical-edges-loops-same-latch-metadata.ll

+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Here the critical backedge is the backedge of two nested loops. We ensure at
+; none will keep the loop ID annotation as it might be invalid for either one
+; of them.
+
+define void @jd(i32* nocapture %A) {
+entry:
+  br label %outer.loop.header
+
+outer.loop.header:                            ; preds = %inner.loop.header, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar_next, %inner.loop.header ]
+  %p_tmp7 = shl i64 %indvar, 9
+  %indvar_next = add nsw i64 %indvar, 1
+  %exitcond1 = icmp eq i64 %indvar_next, 1024
+  br i1 %exitcond1, label %loop_exit, label %inner.loop.header
+
+inner.loop.header:                             ; preds = %inner.loop.header, %outer.loop.header
+  %indvar4 = phi i64 [ 0, %outer.loop.header ], [ %indvar_next5, %inner.loop.header ]
+  %p_tmp = add nsw i64 %indvar4, %indvar
+  %p_tmp8 = add nsw i64 %indvar4, %p_tmp7
+  %p_arrayidx = getelementptr inbounds i32* %A, i64 %p_tmp8
+  %p_tmp9 = trunc i64 %p_tmp to i32
+  store i32 %p_tmp9, i32* %p_arrayidx, align 4
+  %indvar_next5 = add nsw i64 %indvar4, 1
+  %exitcond = icmp eq i64 %indvar_next5, 512
+
+; This is a critical edge and a backedge for both the inner as well as the
+; outer loop. As we cannot know for which it was initialy placed we remove
+; it and ensure other annotations (e.g., llvm.mem.parallel_loop_access) are
+; not invalidated by the splitting.
+
+; CHECK-NOT: !llvm.loop
+  br i1 %exitcond, label %outer.loop.header, label %inner.loop.header, !llvm.loop !0
+
+loop_exit:                                  ; preds = %loop_exit3
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}

test/Transforms/Util/break-critical-edges-no-loop-info-but-loop-id-metadata.ll

+; Run only BreakCriticalEdges without LoopInfo.
+; RUN: opt < %s -break-crit-edges -S | FileCheck %s
+
+; Check that the new loop backedge (after we split critical edges)
+; won't carry llvm.loop annotation as the old (critical) backedge.
+; This is a safety meassure since we cannot know (without LoopInfo)
+; which branch, the new one inserted by splitting the edge, or the
+; old one is a loop backedge now.
+
+define void @jd(i1 %b, i32* nocapture %A) {
+entry:
+  br i1 %b, label %loop_exit, label %loop.header
+
+loop.header:                             ; preds = %loop.header, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar_next, %loop.header ]
+  %p_arrayidx = getelementptr inbounds i32* %A, i64 %indvar
+  %p_tmp9 = trunc i64 %indvar to i32
+  store i32 %p_tmp9, i32* %p_arrayidx, align 4
+  %indvar_next = add nsw i64 %indvar, 1
+  %exitcond = icmp eq i64 %indvar_next, 512
+; This is a critical edge.
+  br i1 %exitcond, label %loop_exit, label %loop.header, !llvm.loop !0
+; CHECK-NOT:!llvm.loop
+
+loop_exit:                                  ; preds = %loop.header
+  ret void
+
+}
+
+!0 = metadata !{metadata !0}

test/Transforms/Util/break-critical-edges-non-loop-backedge-but-llvm-loop-metadata.ll

+; Run LoopInfo before BreakCriticalEdges and use LoopSimplify as a real user of
+; LoopInfo to ensure the pass survives.
+; RUN: opt < %s -loops -break-crit-edges -loop-simplify -S | FileCheck %s
+
+; Here the llvm.loop annotation is invalid in the beginning as the branch is
+; not a backedge of any loop.
+
+define void @jd(i1 %b0, i1 %b1, i32* nocapture %A) {
+block1:
+; This edge is critical but not a loop backedge.
+  br i1 %b0, label %exit1, label %block2
+
+block2:                             ; preds = %block1
+; This edge is critical but not a loop backedge. The annotation is already
+; invalid and BreakCriticalEdges should therefor remove it.
+  br i1 %b1, label %exit1, label %exit2, !llvm.loop !0
+
+exit1:                                  ; preds = %block1, %block2
+  ret void
+
+exit2:                                  ; preds = %block2
+  ret void
+}
+
+!0 = metadata !{metadata !0}
+
+; CHECK-NOT: !llvm.loop