[PATCH 21/27] [noalias] LICM: learn about noalias intrinsics and ptr_provenance

[jeroen.dobbelaere]

Summary

This is part of the series started by D68484.

Besides learning about propagating the ptr_provenance path, I also marked places
where it could be interesting to do, but where it might not always be safe to do.

Note: this is a stable point and tests should run fine with the patches applied up to this point.

[jeroen.dobbelaere]

Rebased

[jeroen.dobbelaere]

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

[jeroen.dobbelaere]

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.

llvm/lib/Transforms/Scalar/LICM.cpp

for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
       Instruction *InsertPos = LoopInsertPts[i];
       StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
       if (UnorderedAtomic)
         NewSI->setOrdering(AtomicOrdering::Unordered);
       NewSI->setAlignment(Align(Alignment));
       NewSI->setDebugLoc(DL);
       if (AATags)
         NewSI->setAAMetadata(AATags);
+      // FIXME: not sure if ptr_provenance propagation should be allowed
+      // here: dependend provenances should also migrate first !
 
       if (MSSAU) {
         MemoryAccess *MSSAInsertPoint = MSSAInsertPts[i];
         MemoryAccess *NewMemAcc;
         if (!MSSAInsertPoint) {
           NewMemAcc = MSSAU->createMemoryAccessInBB(
               NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
         } else {
bool llvm::promoteLoopAccessesToScalars(
   // different sizes.  While we are at it, collect alignment and AA info.
   for (Value *ASIV : PointerMustAliases) {
     // Check that all of the pointers in the alias set have the same type.  We
     // cannot (yet) promote a memory location that is loaded and stored in
     // different sizes.
     if (SomePtr->getType() != ASIV->getType())
       return false;
 
-    for (User *U : ASIV->users()) {
+    for (auto U_it = ASIV->user_begin(), U_it_end = ASIV->user_end();
+         U_it != U_it_end; ++U_it) {
+      User *U = *U_it;
       // Ignore instructions that are outside the loop.
       Instruction *UI = dyn_cast<Instruction>(U);
       if (!UI || !CurLoop->contains(UI))
         continue;
 
       // If there is an non-load/store instruction in the loop, we can't promote
       // it.
       if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
+        if (U_it.getUse().getOperandNo() ==
+            Load->getNoaliasProvenanceOperandIndex())
+          continue;
         if (!Load->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Load->isAtomic();
         SawNotAtomic |= !Load->isAtomic();
 
         Align InstAlignment = Load->getAlign();
 
         // Note that proving a load safe to speculate requires proving
         // sufficient alignment at the target location.  Proving it guaranteed
         // to execute does as well.  Thus we can increase our guaranteed
         // alignment as well. 
         if (!DereferenceableInPH || (InstAlignment > Alignment))
           if (isSafeToExecuteUnconditionally(*Load, DT, CurLoop, SafetyInfo,
                                              ORE, Preheader->getTerminator())) {
             DereferenceableInPH = true;
             Alignment = std::max(Alignment, InstAlignment);
           }
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
+        if (U_it.getUse().getOperandNo() ==
+            Store->getNoaliasProvenanceOperandIndex())
+          continue;
+
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
         if (!Store->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Store->isAtomic();
for (auto U_it = ASIV->user_begin(), U_it_end = ASIV->user_end();
 
         // If the store is not guaranteed to execute, we may still get
         // deref info through it.
         if (!DereferenceableInPH) {
           DereferenceableInPH = isDereferenceableAndAlignedPointer(
               Store->getPointerOperand(), Store->getValueOperand()->getType(),
               Store->getAlign(), MDL, Preheader->getTerminator(), DT);
         }
-      } else
-        return false; // Not a load or store.
+      } else {
+        // Not a load or store.
+        if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(UI)) {
+          if (II->getIntrinsicID() == Intrinsic::provenance_noalias ||
+              II->getIntrinsicID() == Intrinsic::noalias_arg_guard ||
+              II->getIntrinsicID() == Intrinsic::noalias_copy_guard) {
+            // those must not block promotion.
+            continue;
+          }
+        }
+        return false;
+      }
 
       // Merge the AA tags.
       if (LoopUses.empty()) {
         // On the first load/store, just take its AA tags.
         UI->getAAMetadata(AATags);
       } else if (AATags) {
         UI->getAAMetadata(AATags, /* Merge = */ true);
       }
LoadInst *PreheaderLoad = new LoadInst(
       SomePtr->getType()->getPointerElementType(), SomePtr,
       SomePtr->getName() + ".promoted", Preheader->getTerminator());
   if (SawUnorderedAtomic)
     PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
   PreheaderLoad->setAlignment(Alignment);
   PreheaderLoad->setDebugLoc(DebugLoc());
   if (AATags)
     PreheaderLoad->setAAMetadata(AATags);
+  // FIXME: not sure if ptr_provenance propagation should be allowed
+  // here: dependend provenances should also migrate first !
   SSA.AddAvailableValue(Preheader, PreheaderLoad);
 
   if (MSSAU) {
     MemoryAccess *PreheaderLoadMemoryAccess = MSSAU->createMemoryAccessInBB(
         PreheaderLoad, nullptr, PreheaderLoad->getParent(), MemorySSA::End);
     MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
     MSSAU->insertUse(NewMemUse, /*RenameUses=*/true);
   }

llvm/test/Transforms/LICM/noalias.ll

+; RUN: opt -S -basic-aa -licm -enable-mssa-loop-dependency=false %s | FileCheck -check-prefixes=CHECK,AST %s
+; RUN: opt -S -basic-aa -licm -enable-mssa-loop-dependency=true %s | FileCheck  -check-prefixes=CHECK,MSSA %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck -check-prefixes=CHECK,AST %s
+
+
+; Function Attrs: nounwind
+define dso_local void @test01(i32* %_p, i32 %n) #0 {
+entry:
+  %0 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  %n.addr.0 = phi i32 [ %n, %entry ], [ %dec, %do.body ]
+  %1 = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_p, i8* %0, i32** null, i32** undef, i32 0, metadata !2), !tbaa !5, !noalias !2
+  store i32 42, i32* %_p, ptr_provenance i32* %1, align 4, !tbaa !9, !noalias !2
+  %dec = add nsw i32 %n.addr.0, -1
+  %cmp = icmp ne i32 %dec, 0
+  br i1 %cmp, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  ret void
+}
+
+; CHECK-LABEL: @test01(
+; CHECK-LABEL: entry:
+; CHECK:  %0 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+; CHECK:  %1 = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_p, i8* %0, i32** null, i32** undef, i32 0, metadata !2), !tbaa !5, !noalias !2
+; MSSA: store i32 42, i32* %_p, ptr_provenance i32* %1, align 4, !tbaa !9, !noalias !2
+; CHECK-LABEL: do.body:
+; CHECK-LABEL: do.end:
+; AST: store i32 42, i32* %_p, align 4, !tbaa !9
+; CHECK: ret void
+
+; Function Attrs: nounwind
+define dso_local void @test02(i32* %_p, i32 %n) #0 {
+entry:
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  %n.addr.0 = phi i32 [ %n, %entry ], [ %dec, %do.body ]
+  %0 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !11)
+  %1 = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_p, i8* %0, i32** null, i32** undef, i32 0, metadata !11), !tbaa !5, !noalias !11
+  store i32 42, i32* %_p, ptr_provenance i32* %1, align 4, !tbaa !9, !noalias !11
+  %dec = add nsw i32 %n.addr.0, -1
+  %cmp = icmp ne i32 %dec, 0
+  br i1 %cmp, label %do.body, label %do.end
+
+do.end:                                           ; preds = %do.body
+  ret void
+}
+
+; CHECK-LABEL: @test02(
+; CHECK-LABEL: entry:
+; CHECK-LABEL: do.body:
+; CHECK:  %0 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !11)
+; CHECK:  %1 = call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_p, i8* %0, i32** null, i32** undef, i32 0, metadata !11), !tbaa !5, !noalias !11
+; CHECK-LABEL: do.end:
+; CHECK: store i32 42, i32* %_p, align 4, !tbaa !9
+; CHECK: ret void
+
+; Function Attrs: argmemonly nounwind
+declare i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32**, i32, metadata) #1
+
+; Function Attrs: nounwind readnone speculatable
+declare i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32*, i8*, i32**, i32**, i32, metadata) #2
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { nounwind readnone speculatable }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang"}
+!2 = !{!3}
+!3 = distinct !{!3, !4, !"test01: rp"}
+!4 = distinct !{!4, !"test01"}
+!5 = !{!6, !6, i64 0, i64 4}
+!6 = !{!7, i64 4, !"any pointer"}
+!7 = !{!8, i64 1, !"omnipotent char"}
+!8 = !{!"Simple C/C++ TBAA"}
+!9 = !{!10, !10, i64 0, i64 4}
+!10 = !{!7, i64 4, !"int"}
+!11 = !{!12}
+!12 = distinct !{!12, !13, !"test02: rp"}
+!13 = distinct !{!13, !"test02"}