[JumpThreading] Fix handling of aliasing metadata.

[eli.friedman]

Summary

The correctness fix here is that when we CSE a load with another load,
we need to combine the metadata on the two loads. This matches the
behavior of other passes, like instcombine and GVN.

There's also a minor optimization improvement here: for load PRE, the
aliasing metadata on the inserted load should be the same as the
metadata on the original load. Not sure why the old code was throwing
it away.

Issue found by inspection.

[hiraditya]

lib/Transforms/Scalar/JumpThreading.cpp

965

The declaration of KnownIDs seem to be repeated at other places e.g., line 827. Is there a way to merge them, possibly put them all in a separate function.

[eli.friedman]

It should be possible to merge it together... actually, that's probably a good idea considering the number of different versions we have of essentially the same code. GVN has a version (and is missing checks in a couple places), Instcombine has two versions, EarlyCSE has a version (and is missing checks in a couple of places), BBVectorize has a version. Basically, it's a mess. We probably want a general "CSE-metadata" utility. (There's probably also room for a "hoist-metadata" utility.)

That said, I'm not sure it makes sense to do that in this patch.

[eli.friedman]

Ping.

[hfinkel]

lib/Transforms/Scalar/JumpThreading.cpp

965

I agree; we'll now have this list of 'metadata which is safe to merge on memory-access CSE'. Let's put this list somewhere common.

975

Is AATags now dead?

[eli.friedman]

lib/Transforms/Scalar/JumpThreading.cpp

965

Okay; should I add a new utility method called "combineMetadataForMemoryCSE", or do you have some other suggestion?

975

Not quite; it's used for inserting a new load instruction. See "if (UnavailablePred)..." around line 1073.

[hfinkel]

lib/Transforms/Scalar/JumpThreading.cpp

965

SGTM; and with that, this LGTM.

include/llvm/Analysis/Loads.h

 ///
 /// If AATags is non-null and a load or store is found, the AA tags from the
 /// load or store are recorded there.  If there are no AA tags or if no access
 /// is found, it is left unmodified.
 Value *FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB,
                                 BasicBlock::iterator &ScanFrom,
                                 unsigned MaxInstsToScan = DefMaxInstsToScan,
                                 AliasAnalysis *AA = nullptr,
-                                AAMDNodes *AATags = nullptr,
                                 bool *IsLoadCSE = nullptr);
 
 }
 
 #endif

lib/Analysis/Loads.cpp

 /// makes this more precise.
 ///
 /// If \c AATags is non-null and a load or store is found, the AA tags from the
 /// load or store are recorded there. If there are no AA tags or if no access is
 /// found, it is left unmodified.
 Value *llvm::FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB,
                                       BasicBlock::iterator &ScanFrom,
                                       unsigned MaxInstsToScan,
-                                      AliasAnalysis *AA, AAMDNodes *AATags,
-                                      bool *IsLoadCSE) {
+                                      AliasAnalysis *AA, bool *IsLoadCSE) {
   if (MaxInstsToScan == 0)
     MaxInstsToScan = ~0U;
 
+  if (IsLoadCSE)
+    *IsLoadCSE = false;
+
   Value *Ptr = Load->getPointerOperand();
   Type *AccessTy = Load->getType();
 
   // We can never remove a volatile load
   if (Load->isVolatile())
     return nullptr;
 
   // Anything stronger than unordered is currently unimplemented.
if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
               LI->getPointerOperand()->stripPointerCasts(), StrippedPtr) &&
           CastInst::isBitOrNoopPointerCastable(LI->getType(), AccessTy, DL)) {
 
         // We can value forward from an atomic to a non-atomic, but not the
         // other way around.
         if (LI->isAtomic() < Load->isAtomic())
           return nullptr;
 
-        if (AATags)
-          LI->getAAMetadata(*AATags);
         if (IsLoadCSE)
             *IsLoadCSE = true;
         return LI;
       }
 
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       Value *StorePtr = SI->getPointerOperand()->stripPointerCasts();
       // If this is a store through Ptr, the value is available!
       // (This is true even if the store is volatile or atomic, although
       // those cases are unlikely.)
       if (AreEquivalentAddressValues(StorePtr, StrippedPtr) &&
           CastInst::isBitOrNoopPointerCastable(SI->getValueOperand()->getType(),
                                                AccessTy, DL)) {
 
         // We can value forward from an atomic to a non-atomic, but not the
         // other way around.
         if (SI->isAtomic() < Load->isAtomic())
           return nullptr;
 
-        if (AATags)
-          SI->getAAMetadata(*AATags);
         return SI->getOperand(0);
       }
 
       // If both StrippedPtr and StorePtr reach all the way to an alloca or
       // global and they are different, ignore the store. This is a trivial form
       // of alias analysis that is important for reg2mem'd code.
       if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
           (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
 
   if (Instruction *Res = unpackLoadToAggregate(*this, LI))
     return Res;
 
   // Do really simple store-to-load forwarding and load CSE, to catch cases
   // where there are several consecutive memory accesses to the same location,
   // separated by a few arithmetic operations.
   BasicBlock::iterator BBI(LI);
-  AAMDNodes AATags;
   bool IsLoadCSE = false;
   if (Value *AvailableVal =
       FindAvailableLoadedValue(&LI, LI.getParent(), BBI,
-                               DefMaxInstsToScan, AA, &AATags, &IsLoadCSE)) {
+                               DefMaxInstsToScan, AA, &IsLoadCSE)) {
     if (IsLoadCSE) {
       LoadInst *NLI = cast<LoadInst>(AvailableVal);
       unsigned KnownIDs[] = {
           LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
           LLVMContext::MD_noalias,         LLVMContext::MD_range,
           LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
           LLVMContext::MD_invariant_group, LLVMContext::MD_align,
           LLVMContext::MD_dereferenceable,

lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
   // TODO: Could do simple PHI translation, that would be fun :)
   if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
     if (PtrOp->getParent() == LoadBB)
       return false;
 
   // Scan a few instructions up from the load, to see if it is obviously live at
   // the entry to its block.
   BasicBlock::iterator BBIt(LI);
-
+  bool IsLoadCSE;
   if (Value *AvailableVal =
-        FindAvailableLoadedValue(LI, LoadBB, BBIt, DefMaxInstsToScan)) {
+        FindAvailableLoadedValue(LI, LoadBB, BBIt, DefMaxInstsToScan, nullptr, &IsLoadCSE)) {
     // If the value of the load is locally available within the block, just use
     // it.  This frequently occurs for reg2mem'd allocas.
     //cerr << "LOAD ELIMINATED:\n" << *BBIt << *LI << "\n";
 
+    if (IsLoadCSE) {
+      LoadInst *NLI = cast<LoadInst>(AvailableVal);
+      unsigned KnownIDs[] = {
+          LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
+          LLVMContext::MD_noalias,         LLVMContext::MD_range,
+          LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
+          LLVMContext::MD_invariant_group, LLVMContext::MD_align,
+          LLVMContext::MD_dereferenceable,
+          LLVMContext::MD_dereferenceable_or_null};
+      combineMetadata(NLI, LI, KnownIDs);
+    };
+
     // If the returned value is the load itself, replace with an undef. This can
     // only happen in dead loops.
     if (AvailableVal == LI) AvailableVal = UndefValue::get(LI->getType());
     if (AvailableVal->getType() != LI->getType())
       AvailableVal =
           CastInst::CreateBitOrPointerCast(AvailableVal, LI->getType(), "", LI);
     LI->replaceAllUsesWith(AvailableVal);
     LI->eraseFromParent();
     return true;
   }
 
   // Otherwise, if we scanned the whole block and got to the top of the block,
   // we know the block is locally transparent to the load.  If not, something
   // might clobber its value.
   if (BBIt != LoadBB->begin())
     return false;
 
   // If all of the loads and stores that feed the value have the same AA tags,
   // then we can propagate them onto any newly inserted loads.
   AAMDNodes AATags;
   LI->getAAMetadata(AATags);
 
   SmallPtrSet<BasicBlock*, 8> PredsScanned;
   typedef SmallVector<std::pair<BasicBlock*, Value*>, 8> AvailablePredsTy;
   AvailablePredsTy AvailablePreds;
   BasicBlock *OneUnavailablePred = nullptr;
+  SmallVector<LoadInst*, 8> CSELoads;
 
   // If we got here, the loaded value is transparent through to the start of the
   // block.  Check to see if it is available in any of the predecessor blocks.
   for (BasicBlock *PredBB : predecessors(LoadBB)) {
     // If we already scanned this predecessor, skip it.
     if (!PredsScanned.insert(PredBB).second)
       continue;
 
     // Scan the predecessor to see if the value is available in the pred.
     BBIt = PredBB->end();
-    AAMDNodes ThisAATags;
     Value *PredAvailable = FindAvailableLoadedValue(LI, PredBB, BBIt,
                                                     DefMaxInstsToScan,
-                                                    nullptr, &ThisAATags);
+                                                    nullptr,
+                                                    &IsLoadCSE);
     if (!PredAvailable) {
       OneUnavailablePred = PredBB;
       continue;
     }
 
-    // If AA tags disagree or are not present, forget about them.
-    if (AATags != ThisAATags) AATags = AAMDNodes();
+    if (IsLoadCSE)
+      CSELoads.push_back(cast<LoadInst>(PredAvailable));
 
     // If so, this load is partially redundant.  Remember this info so that we
     // can create a PHI node.
     AvailablePreds.push_back(std::make_pair(PredBB, PredAvailable));
   }
 
   // If the loaded value isn't available in any predecessor, it isn't partially
   // redundant.
for (pred_iterator PI = PB; PI != PE; ++PI) {
     Value *&PredV = I->second;
     if (PredV->getType() != LI->getType())
       PredV = CastInst::CreateBitOrPointerCast(PredV, LI->getType(), "",
                                                P->getTerminator());
 
     PN->addIncoming(PredV, I->first);
   }
 
+  for (LoadInst *PredLI : CSELoads) {
+      unsigned KnownIDs[] = {
+          LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
+          LLVMContext::MD_noalias,         LLVMContext::MD_range,
+          LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
+          LLVMContext::MD_invariant_group, LLVMContext::MD_align,
+          LLVMContext::MD_dereferenceable,
+          LLVMContext::MD_dereferenceable_or_null};
+      combineMetadata(PredLI, LI, KnownIDs);
+  }
+
   //cerr << "PRE: " << *LI << *PN << "\n";
 
   LI->replaceAllUsesWith(PN);
   LI->eraseFromParent();
 
   return true;
 }
 

test/Transforms/JumpThreading/thread-loads.ll

 
 if.then60:
   ret i32 42
 
 return:
   ret i32 13
 }
 
+; Make sure we merge the aliasing metadata. (If we don't, we have a load
+; with the wrong metadata, so the branch gets incorrectly eliminated.)
+define void @test4(i32*, i32*, i32*) {
+; CHECK-LABEL: @test4(
+; CHECK: %a = load i32, i32* %0, !range !4
+; CHECK-NEXT: store i32 %a
+; CHECK: br i1 %c
+  %a = load i32, i32* %0, !tbaa !0, !range !4, !alias.scope !9, !noalias !10
+  %b = load i32, i32* %0, !range !5
+  store i32 %a, i32* %1
+  %c = icmp eq i32 %b, 8
+  br i1 %c, label %ret1, label %ret2
+
+ret1:
+  ret void
+
+ret2:
+  %xxx = tail call i32 (...) @f1() nounwind
+  ret void
+}
+
+; Make sure we merge/PRE aliasing metadata correctly.  That means that
+; we need to remove metadata from the existing load, and add appropriate
+; metadata to the newly inserted load.
+define void @test5(i32*, i32*, i32*, i1 %c) {
+; CHECK-LABEL: @test5(
+  br i1 %c, label %d1, label %d2
+
+; CHECK: d1:
+; CHECK-NEXT: %a = load i32, i32* %0{{$}}
+d1:
+  %a = load i32, i32* %0, !range !4, !alias.scope !9, !noalias !10
+  br label %d3
+
+; CHECK: d2:
+; CHECK-NEXT: %xxxx = tail call i32 (...) @f1()
+; CHECK-NEXT: %b.pr = load i32, i32* %0, !tbaa !0{{$}}
+d2:
+  %xxxx = tail call i32 (...) @f1() nounwind
+  br label %d3
+
+d3:
+  %p = phi i32 [ 1, %d2 ], [ %a, %d1 ]
+  %b = load i32, i32* %0, !tbaa !0
+  store i32 %p, i32* %1
+  %c2 = icmp eq i32 %b, 8
+  br i1 %c2, label %ret1, label %ret2
+
+ret1:
+  ret void
+
+ret2:
+  %xxx = tail call i32 (...) @f1() nounwind
+  ret void
+}
+
 !0 = !{!3, !3, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA", null}
 !3 = !{!"int", !1}
+!4 = !{ i32 0, i32 1 }
+!5 = !{ i32 8, i32 10 }
+!6 = !{!6}
+!7 = !{!7, !6}
+!8 = !{!8, !6}
+!9 = !{!7}
+!10 = !{!8}