[LoopPeel] Use llvm.experimental.noalias.scope.decl for duplicating noalias metadata as needed.

[jeroen.dobbelaere]

Summary

The reduction of a sanitizer build failure when enabling the dominance check (D95335) showed that loop peeling also needs to take care of scope duplication, just like loop unrolling (D92887).

[nikic]

llvm/lib/Transforms/Utils/LoopPeel.cpp

525

Might make sense to do this once and pass into cloneLoopBlocks?

llvm/test/Transforms/LoopUnroll/peel-loop-noalias-scope-decl.ll

3

I don't think these --verify are needed. opt verifies before and after by default.

[jeroen.dobbelaere]

llvm/lib/Transforms/Utils/LoopPeel.cpp

525

Yes, that definitely makes sense !

[jeroen.dobbelaere]

Adapted to comments.

[nikic]

LGTM

llvm/lib/Transforms/Utils/LoopPeel.cpp

552

nit: ext -> Ext

[nikic]

@jeroen.dobbelaere Can you please also re-enable the verifier flag (assuming you're not aware of further issues right now)?

[jeroen.dobbelaere]

In D95544#2533355, @nikic wrote:

@jeroen.dobbelaere Can you please also re-enable the verifier flag (assuming you're not aware of further issues right now)?

That's the plan ;) Just leaving some time for the bots.

llvm/lib/Transforms/Utils/LoopPeel.cpp

 /// \param LoopBlocks A helper for DFS-traversal of the loop.
 /// \param LVMap A value-map that maps instructions from the original loop to
 /// instructions in the last peeled-off iteration.
 static void cloneLoopBlocks(
     Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot,
     SmallVectorImpl<std::pair<BasicBlock *, BasicBlock *>> &ExitEdges,
     SmallVectorImpl<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
     ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT,
-    LoopInfo *LI) {
+    LoopInfo *LI, ArrayRef<MDNode *> LoopLocalNoAliasDeclScopes) {
   BasicBlock *Header = L->getHeader();
   BasicBlock *Latch = L->getLoopLatch();
   BasicBlock *PreHeader = L->getLoopPreheader();
 
   Function *F = Header->getParent();
   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
   Loop *ParentLoop = L->getParentLoop();
 
   // For each block in the original loop, create a new copy,
   // and update the value map with the newly created values.
   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
     NewBlocks.push_back(NewBB);
 
     // If an original block is an immediate child of the loop L, its copy
     // is a child of a ParentLoop after peeling. If a block is a child of
     // a nested loop, it is handled in the cloneLoop() call below.
     if (ParentLoop && LI->getLoopFor(*BB) == L)
       ParentLoop->addBasicBlockToLoop(NewBB, *LI);
 
     VMap[*BB] = NewBB;
 
     // If dominator tree is available, insert nodes to represent cloned blocks.
     if (DT) {
       if (Header == *BB)
         DT->addNewBlock(NewBB, InsertTop);
       else {
         DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
         // VMap must contain entry for IDom, as the iteration order is RPO.
         DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDom->getBlock()]));
       }
     }
   }
 
+  {
+    // Identify what other metadata depends on the cloned version. After
+    // cloning, replace the metadata with the corrected version for both
+    // memory instructions and noalias intrinsics.
+    std::string Ext = (Twine("Peel") + Twine(IterNumber)).str();
+    cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,
+                               Header->getContext(), Ext);
+  }
+
   // Recursively create the new Loop objects for nested loops, if any,
   // to preserve LoopInfo.
   for (Loop *ChildLoop : *L) {
     cloneLoop(ChildLoop, ParentLoop, VMap, LI, nullptr);
   }
 
   // Hook-up the control flow for the newly inserted blocks.
   // The new header is hooked up directly to the "top", which is either
bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
 
   // If we have branch weight information, we'll want to update it for the
   // newly created branches.
   BranchInst *LatchBR =
       cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
   uint64_t ExitWeight = 0, FallThroughWeight = 0;
   initBranchWeights(Header, LatchBR, ExitWeight, FallThroughWeight);
 
+  // Identify what noalias metadata is inside the loop: if it is inside the
+  // loop, the associated metadata must be cloned for each iteration.
+  SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
+  identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
+
   // For each peeled-off iteration, make a copy of the loop.
   for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
     SmallVector<BasicBlock *, 8> NewBlocks;
     ValueToValueMapTy VMap;
 
     cloneLoopBlocks(L, Iter, InsertTop, InsertBot, ExitEdges, NewBlocks,
-                    LoopBlocks, VMap, LVMap, DT, LI);
+                    LoopBlocks, VMap, LVMap, DT, LI,
+                    LoopLocalNoAliasDeclScopes);
 
     // Remap to use values from the current iteration instead of the
     // previous one.
     remapInstructionsInBlocks(NewBlocks, VMap);
 
     if (DT) {
       // Latches of the cloned loops dominate over the loop exit, so idom of the
       // latter is the first cloned loop body, as original PreHeader dominates

llvm/test/Transforms/LoopUnroll/peel-loop-noalias-scope-decl.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -loop-unroll -unroll-force-peel-count=1 | FileCheck %s
+; RUN: opt < %s -S -passes='loop-unroll<peeling;no-runtime>' -unroll-force-peel-count=1 | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Loop peeling must result in valid scope declartions
+
+define internal fastcc void @test01(i8* %p0, i8* %p1, i8* %p2) unnamed_addr align 2 {
+; CHECK-LABEL: @test01(
+; CHECK-NEXT:  for.body47.lr.ph:
+; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata !0)
+; CHECK-NEXT:    br label [[FOR_BODY47_PEEL_BEGIN:%.*]]
+; CHECK:       for.body47.peel.begin:
+; CHECK-NEXT:    br label [[FOR_BODY47_PEEL:%.*]]
+; CHECK:       for.body47.peel:
+; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata !3)
+; CHECK-NEXT:    store i8 42, i8* [[P0:%.*]], align 1, !alias.scope !3
+; CHECK-NEXT:    store i8 43, i8* [[P1:%.*]], align 1, !alias.scope !0
+; CHECK-NEXT:    store i8 44, i8* [[P2:%.*]], align 1, !alias.scope !5
+; CHECK-NEXT:    store i8 42, i8* [[P0]], align 1, !noalias !3
+; CHECK-NEXT:    store i8 43, i8* [[P1]], align 1, !noalias !0
+; CHECK-NEXT:    store i8 44, i8* [[P2]], align 1, !noalias !5
+; CHECK-NEXT:    [[CMP52_PEEL:%.*]] = icmp eq i32 0, 0
+; CHECK-NEXT:    br i1 [[CMP52_PEEL]], label [[COND_TRUE_PEEL:%.*]], label [[COND_END_PEEL:%.*]]
+; CHECK:       cond.true.peel:
+; CHECK-NEXT:    store i8 52, i8* [[P0]], align 1, !alias.scope !3
+; CHECK-NEXT:    store i8 53, i8* [[P1]], align 1, !alias.scope !0
+; CHECK-NEXT:    store i8 54, i8* [[P2]], align 1, !alias.scope !5
+; CHECK-NEXT:    store i8 52, i8* [[P0]], align 1, !noalias !3
+; CHECK-NEXT:    store i8 53, i8* [[P1]], align 1, !noalias !0
+; CHECK-NEXT:    store i8 54, i8* [[P2]], align 1, !noalias !5
+; CHECK-NEXT:    br label [[COND_END_PEEL]]
+; CHECK:       cond.end.peel:
+; CHECK-NEXT:    store i8 62, i8* [[P0]], align 1, !alias.scope !3
+; CHECK-NEXT:    store i8 63, i8* [[P1]], align 1, !alias.scope !0
+; CHECK-NEXT:    store i8 64, i8* [[P2]], align 1, !alias.scope !5
+; CHECK-NEXT:    store i8 62, i8* [[P0]], align 1, !noalias !3
+; CHECK-NEXT:    store i8 63, i8* [[P1]], align 1, !noalias !0
+; CHECK-NEXT:    store i8 64, i8* [[P2]], align 1, !noalias !5
+; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nuw i32 0, 1
+; CHECK-NEXT:    [[EXITCOND_NOT_PEEL:%.*]] = icmp eq i32 [[INC_PEEL]], undef
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT_PEEL]], label [[FOR_COND_CLEANUP46:%.*]], label [[FOR_BODY47_PEEL_NEXT:%.*]]
+; CHECK:       for.body47.peel.next:
+; CHECK-NEXT:    br label [[FOR_BODY47_PEEL_NEXT1:%.*]]
+; CHECK:       for.body47.peel.next1:
+; CHECK-NEXT:    br label [[FOR_BODY47_LR_PH_PEEL_NEWPH:%.*]]
+; CHECK:       for.body47.lr.ph.peel.newph:
+; CHECK-NEXT:    br label [[FOR_BODY47:%.*]]
+; CHECK:       for.cond.cleanup46.loopexit:
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP46]]
+; CHECK:       for.cond.cleanup46:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body47:
+; CHECK-NEXT:    [[J_02:%.*]] = phi i32 [ [[INC_PEEL]], [[FOR_BODY47_LR_PH_PEEL_NEWPH]] ], [ [[INC:%.*]], [[COND_END:%.*]] ]
+; CHECK-NEXT:    call void @llvm.experimental.noalias.scope.decl(metadata !6)
+; CHECK-NEXT:    store i8 42, i8* [[P0]], align 1, !alias.scope !6
+; CHECK-NEXT:    store i8 43, i8* [[P1]], align 1, !alias.scope !0
+; CHECK-NEXT:    store i8 44, i8* [[P2]], align 1, !alias.scope !8
+; CHECK-NEXT:    store i8 42, i8* [[P0]], align 1, !noalias !6
+; CHECK-NEXT:    store i8 43, i8* [[P1]], align 1, !noalias !0
+; CHECK-NEXT:    store i8 44, i8* [[P2]], align 1, !noalias !8
+; CHECK-NEXT:    br i1 false, label [[COND_TRUE:%.*]], label [[COND_END]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    store i8 52, i8* [[P0]], align 1, !alias.scope !6
+; CHECK-NEXT:    store i8 53, i8* [[P1]], align 1, !alias.scope !0
+; CHECK-NEXT:    store i8 54, i8* [[P2]], align 1, !alias.scope !8
+; CHECK-NEXT:    store i8 52, i8* [[P0]], align 1, !noalias !6
+; CHECK-NEXT:    store i8 53, i8* [[P1]], align 1, !noalias !0
+; CHECK-NEXT:    store i8 54, i8* [[P2]], align 1, !noalias !8
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    store i8 62, i8* [[P0]], align 1, !alias.scope !6
+; CHECK-NEXT:    store i8 63, i8* [[P1]], align 1, !alias.scope !0
+; CHECK-NEXT:    store i8 64, i8* [[P2]], align 1, !alias.scope !8
+; CHECK-NEXT:    store i8 62, i8* [[P0]], align 1, !noalias !6
+; CHECK-NEXT:    store i8 63, i8* [[P1]], align 1, !noalias !0
+; CHECK-NEXT:    store i8 64, i8* [[P2]], align 1, !noalias !8
+; CHECK-NEXT:    [[INC]] = add nuw i32 [[J_02]], 1
+; CHECK-NEXT:    br i1 undef, label [[FOR_COND_CLEANUP46_LOOPEXIT:%.*]], label [[FOR_BODY47]], [[LOOP9:!llvm.loop !.*]]
+;
+for.body47.lr.ph:
+  call void @llvm.experimental.noalias.scope.decl(metadata !5)
+  br label %for.body47
+
+for.cond.cleanup46:                               ; preds = %cond.end
+  ret void
+
+for.body47:                                       ; preds = %cond.end, %for.body47.lr.ph
+  %j.02 = phi i32 [ 0, %for.body47.lr.ph ], [ %inc, %cond.end ]
+  call void @llvm.experimental.noalias.scope.decl(metadata !0)
+  store i8 42, i8* %p0, !alias.scope !0
+  store i8 43, i8* %p1, !alias.scope !5
+  store i8 44, i8* %p2, !alias.scope !7
+  store i8 42, i8* %p0, !noalias !0
+  store i8 43, i8* %p1, !noalias !5
+  store i8 44, i8* %p2, !noalias !7
+  %cmp52 = icmp eq i32 %j.02, 0
+  br i1 %cmp52, label %cond.true, label %cond.end
+
+cond.true:                                        ; preds = %for.body47
+  store i8 52, i8* %p0, !alias.scope !0
+  store i8 53, i8* %p1, !alias.scope !5
+  store i8 54, i8* %p2, !alias.scope !7
+  store i8 52, i8* %p0, !noalias !0
+  store i8 53, i8* %p1, !noalias !5
+  store i8 54, i8* %p2, !noalias !7
+  br label %cond.end
+
+cond.end:                                         ; preds = %cond.true, %for.body47
+  store i8 62, i8* %p0, !alias.scope !0
+  store i8 63, i8* %p1, !alias.scope !5
+  store i8 64, i8* %p2, !alias.scope !7
+  store i8 62, i8* %p0, !noalias !0
+  store i8 63, i8* %p1, !noalias !5
+  store i8 64, i8* %p2, !noalias !7
+  %inc = add nuw i32 %j.02, 1
+  %exitcond.not = icmp eq i32 %inc, undef
+  br i1 %exitcond.not, label %for.cond.cleanup46, label %for.body47, !llvm.loop !3
+}
+
+; Function Attrs: inaccessiblememonly nofree nosync nounwind willreturn
+declare void @llvm.experimental.noalias.scope.decl(metadata) #0
+
+attributes #0 = { inaccessiblememonly nofree nosync nounwind willreturn }
+
+!0 = !{!1}
+!1 = distinct !{!1, !2, !"foo: %inner.result"}
+!2 = distinct !{!2, !"foo"}
+!3 = distinct !{!3, !4}
+!4 = !{!"llvm.loop.mustprogress"}
+!5 = !{!6}
+!6 = distinct !{!6, !2, !"foo: %outer.result"}
+!7 = !{!1, !6}
+
+; CHECK: !0 = !{!1}
+; CHECK: !1 = distinct !{!1, !2, !"foo: %outer.result"}
+; CHECK: !2 = distinct !{!2, !"foo"}
+; CHECK: !3 = !{!4}
+; CHECK: !4 = distinct !{!4, !2, !"foo: %inner.result:Peel0"}
+; CHECK: !5 = !{!4, !1}
+; CHECK: !6 = !{!7}
+; CHECK: !7 = distinct !{!7, !2, !"foo: %inner.result"}
+; CHECK: !8 = !{!7, !1}
+; CHECK: !9 = distinct !{!9, !10, !11, !12}
+; CHECK: !10 = !{!"llvm.loop.mustprogress"}
+; CHECK: !11 = !{!"llvm.loop.peeled.count", i32 1}
+; CHECK: !12 = !{!"llvm.loop.unroll.disable"}