Use a WeakVH for UnknownInstructions in AliasSetTracker

[sanjoy]

Summary

This change solves the same problem as D30726, except that this only
throws out the bathwater.

AST was not correctly tracking and deleting UnknownInstructions via
handles. The existing code only tracks "pointers" in its
ASTCallbackVH, so an UnknownInstruction (that isn't also def'ing a
pointer used by another memory instruction) never gets a
ASTCallbackVH.

There are two other ways to solve this problem:

• Use the PointerRec scheme for both known and unknown instructions.
• Use a CallbackVH that erases the offending Instruction from the UnknownInstruction list.

Both of the above changes seemed to be significantly (and unnecessarily
IMO) more complex than this.

[chandlerc]

Nice, I like it.

[• dberlin]

+1
nice work ;)

llvm/trunk/include/llvm/Analysis/AliasSetTracker.h

class AliasSet : public ilist_node<AliasSet> {
   };
 
   // Doubly linked list of nodes.
   PointerRec *PtrList, **PtrListEnd;
   // Forwarding pointer.
   AliasSet *Forward;
 
   /// All instructions without a specific address in this alias set.
-  std::vector<AssertingVH<Instruction> > UnknownInsts;
+  /// In rare cases this vector can have a null'ed out WeakVH
+  /// instances (can happen if some other loop pass deletes an
+  /// instruction in this list).
+  std::vector<WeakVH> UnknownInsts;
 
   /// Number of nodes pointing to this AliasSet plus the number of AliasSets
   /// forwarding to it.
   unsigned RefCount : 27;
 
   // Signifies that this set should be considered to alias any pointer.
   // Use when the tracker holding this set is saturated.
   unsigned AliasAny : 1;
class AliasSet : public ilist_node<AliasSet> {
   void dropRef(AliasSetTracker &AST) {
     assert(RefCount >= 1 && "Invalid reference count detected!");
     if (--RefCount == 0)
       removeFromTracker(AST);
   }
 
   Instruction *getUnknownInst(unsigned i) const {
     assert(i < UnknownInsts.size());
-    return UnknownInsts[i];
+    return cast_or_null<Instruction>(UnknownInsts[i]);
   }
 
 public:
   /// Accessors...
   bool isRef() const { return Access & RefAccess; }
   bool isMod() const { return Access & ModAccess; }
   bool isMustAlias() const { return Alias == SetMustAlias; }
   bool isMayAlias()  const { return Alias == SetMayAlias; }

llvm/trunk/lib/Analysis/AliasSetTracker.cpp

bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
   for (iterator I = begin(), E = end(); I != E; ++I)
     if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
                  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
       return true;
 
   // Check the unknown instructions...
   if (!UnknownInsts.empty()) {
     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
-      if (AA.getModRefInfo(UnknownInsts[i],
-                           MemoryLocation(Ptr, Size, AAInfo)) != MRI_NoModRef)
+      if (auto *Inst = getUnknownInst(i))
+        if (AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo)) !=
+            MRI_NoModRef)
           return true;
   }
 
   return false;
 }
 
 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
                                   AliasAnalysis &AA) const {
 
   if (AliasAny)
     return true;
 
   if (!Inst->mayReadOrWriteMemory())
     return false;
 
   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
-    ImmutableCallSite C1(getUnknownInst(i)), C2(Inst);
+    if (auto *Inst = getUnknownInst(i)) {
+      ImmutableCallSite C1(Inst), C2(Inst);
       if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef ||
           AA.getModRefInfo(C2, C1) != MRI_NoModRef)
         return true;
     }
+  }
 
   for (iterator I = begin(), E = end(); I != E; ++I)
     if (AA.getModRefInfo(Inst, MemoryLocation(I.getPointer(), I.getSize(),
                                               I.getAAInfo())) != MRI_NoModRef)
       return true;
 
   return false;
 }
void AliasSetTracker::add(const AliasSetTracker &AST) {
   // therein into the current alias sets.  This can cause alias sets to be
   // merged together in the current AST.
   for (const AliasSet &AS : AST) {
     if (AS.Forward)
       continue; // Ignore forwarding alias sets
 
     // If there are any call sites in the alias set, add them to this AST.
     for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
-      add(AS.UnknownInsts[i]);
+      if (auto *Inst = AS.getUnknownInst(i))
+        add(Inst);
 
     // Loop over all of the pointers in this alias set.
     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
       AliasSet &NewAS =
           addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
                      (AliasSet::AccessLattice)AS.Access);
       if (AS.isVolatile()) NewAS.setVolatile();
     }
   }
 }
 
 // deleteValue method - This method is used to remove a pointer value from the
 // AliasSetTracker entirely.  It should be used when an instruction is deleted
 // from the program to update the AST.  If you don't use this, you would have
 // dangling pointers to deleted instructions.
 //
 void AliasSetTracker::deleteValue(Value *PtrVal) {
-  // If this is a call instruction, remove the callsite from the appropriate
-  // AliasSet (if present).
-  if (Instruction *Inst = dyn_cast<Instruction>(PtrVal)) {
-    if (Inst->mayReadOrWriteMemory()) {
-      // Scan all the alias sets to see if this call site is contained.
-      for (iterator I = begin(), E = end(); I != E;) {
-        iterator Cur = I++;
-        if (!Cur->Forward)
-          Cur->removeUnknownInst(*this, Inst);
-      }
-    }
-  }
-
   // First, look up the PointerRec for this pointer.
   PointerMapType::iterator I = PointerMap.find_as(PtrVal);
   if (I == PointerMap.end()) return;  // Noop
 
   // If we found one, remove the pointer from the alias set it is in.
   AliasSet::PointerRec *PtrValEnt = I->second;
   AliasSet *AS = PtrValEnt->getAliasSet(*this);
 
for (iterator I = begin(), E = end(); I != E; ++I) {
       I.getPointer()->printAsOperand(OS << "(");
       OS << ", " << I.getSize() << ")";
     }
   }
   if (!UnknownInsts.empty()) {
     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
       if (i) OS << ", ";
-      UnknownInsts[i]->printAsOperand(OS);
+      if (auto *I = getUnknownInst(i))
+        I->printAsOperand(OS);
     }
   }
   OS << "\n";
 }
 
 void AliasSetTracker::print(raw_ostream &OS) const {
   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
      << PointerMap.size() << " pointer values.\n";

llvm/trunk/test/Transforms/LICM/pr32129.ll

+; RUN: opt -S -licm -loop-unswitch -licm < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NOT: guard
+entry:
+  br label %header
+
+header:
+  br label %loop
+
+loop:
+  %0 = icmp ult i32 0, 400
+  call void (i1, ...) @llvm.experimental.guard(i1 %0, i32 9) [ "deopt"() ]
+  br i1 undef, label %header, label %loop
+}