[PM/AA] Replace the only use of the AliasAnalysis::deleteValue API (in GlobalsModRef) with CallbackVHs that trigger the same behavior.

[chandlerc]

Summary

This is technically more expensive, but in benchmarking some LTO runs,
it seems unlikely to even be above the noise floor. The only way I was
able to measure the performance of GMR at all was to run nothing else
but this one analysis on a linked clang bitcode file. The call graph
analysis still took 5x more time than GMR, and this change at most made
GMR 2% slower (this is well within the noise, so its hard for me to be
sure that this is an actual change). However, in a real LTO run over the
same bitcode, the GMR run takes so little time that the pass timers
don't measure it.

With this, I can remove the last update API from the AliasAnalysis
interface, but I'll actually remove the interface hook point in
a follow-up commit.

[kimgr]

llvm/trunk/lib/Analysis/IPA/GlobalsModRef.cpp

106–114

This doesn't compile on my FreeBSD 10.1 rig;

In file included from /home/kimgr/code/llvm-trunk/llvm/lib/Analysis/IPA/GlobalsModRef.cpp:32:
/usr/include/c++/v1/list:227:9: error: field has incomplete type '<anonymous>::GlobalsModRef::DeletionCallbackHandle'
    _Tp __value_;
        ^
/usr/include/c++/v1/type_traits:1994:27: note: in instantiation of template class 'std::__1::__list_node<<anonymous>::GlobalsModRef::DeletionCallbackHandle, void *>' requested here
                 decltype(__is_constructible_test(declval<_Tp>(), declval<_Args>()...))

$ clang --version
FreeBSD clang version 3.4.1 (tags/RELEASE_34/dot1-final 208032) 20140512
Target: x86_64-unknown-freebsd10.1
Thread model: posix

Not sure which libc++ version came with this system. I've confirmed that moving the full DeletionCallbackHandle definition up in place of the forward decl resolves the problem.

The Clang version is getting old, but this is FreeBSD's latest production release, so it would be nice if it could be supported.

Thanks!

llvm/trunk/lib/Analysis/IPA/GlobalsModRef.cpp

 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
+#include <list>
 #include <set>
 using namespace llvm;
 
 #define DEBUG_TYPE "globalsmodref-aa"
 
 STATISTIC(NumNonAddrTakenGlobalVars,
           "Number of global vars without address taken");
 STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
struct FunctionRecord {
   /// ANY memory.  If not, we can do a lot of aggressive analysis on it.
   unsigned FunctionEffect;
 
   FunctionRecord() : MayReadAnyGlobal(false), FunctionEffect(0) {}
 };
 
 /// GlobalsModRef - The actual analysis pass.
 class GlobalsModRef : public ModulePass, public AliasAnalysis {
-  /// NonAddressTakenGlobals - The globals that do not have their addresses
-  /// taken.
+  /// The globals that do not have their addresses taken.
   std::set<const GlobalValue *> NonAddressTakenGlobals;
 
   /// IndirectGlobals - The memory pointed to by this global is known to be
   /// 'owned' by the global.
   std::set<const GlobalValue *> IndirectGlobals;
 
   /// AllocsForIndirectGlobals - If an instruction allocates memory for an
   /// indirect global, this map indicates which one.
   std::map<const Value *, const GlobalValue *> AllocsForIndirectGlobals;
 
   /// FunctionInfo - For each function, keep track of what globals are
   /// modified or read.
   std::map<const Function *, FunctionRecord> FunctionInfo;
 
+  /// Handle to clear this analysis on deletion of values.
+  struct DeletionCallbackHandle;
+
+  /// List of callbacks for globals being tracked by this analysis. Note that
+  /// these objects are quite large, but we only anticipate having one per
+  /// global tracked by this analysis. There are numerous optimizations we
+  /// could perform to the memory utilization here if this becomes a problem.
+  std::list<DeletionCallbackHandle> Handles;
+
 public:
   static char ID;
   GlobalsModRef() : ModulePass(ID) {
     initializeGlobalsModRefPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnModule(Module &M) override {
     InitializeAliasAnalysis(this, &M.getDataLayout());
if (const Function *F = CS.getCalledFunction())
           Min = DoesNotAccessMemory;
         else if ((FR->FunctionEffect & Mod) == 0)
           Min = OnlyReadsMemory;
       }
 
     return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
   }
 
-  void deleteValue(Value *V) override;
-
   /// getAdjustedAnalysisPointer - This method is used when a pass implements
   /// an analysis interface through multiple inheritance.  If needed, it
   /// should override this to adjust the this pointer as needed for the
   /// specified pass info.
   void *getAdjustedAnalysisPointer(AnalysisID PI) override {
     if (PI == &AliasAnalysis::ID)
       return (AliasAnalysis *)this;
     return this;
INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
                          false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
                        "Simple mod/ref analysis for globals", false, true,
                        false)
 
 Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); }
 
+struct final GlobalsModRef::DeletionCallbackHandle : CallbackVH {
+  GlobalsModRef &GMR;
+  std::list<DeletionCallbackHandle>::iterator I;
+
+  DeletionCallbackHandle(GlobalsModRef &GMR, Value *V)
+      : CallbackVH(V), GMR(GMR) {}
+
+  void deleted() override {
+    Value *V = getValPtr();
+    if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
+      if (GMR.NonAddressTakenGlobals.erase(GV)) {
+        // This global might be an indirect global.  If so, remove it and remove
+        // any AllocRelatedValues for it.
+        if (GMR.IndirectGlobals.erase(GV)) {
+          // Remove any entries in AllocsForIndirectGlobals for this global.
+          for (std::map<const Value *, const GlobalValue *>::iterator
+                   I = GMR.AllocsForIndirectGlobals.begin(),
+                   E = GMR.AllocsForIndirectGlobals.end();
+               I != E;) {
+            if (I->second == GV) {
+              GMR.AllocsForIndirectGlobals.erase(I++);
+            } else {
+              ++I;
+            }
+          }
+        }
+      }
+    }
+
+    // If this is an allocation related to an indirect global, remove it.
+    GMR.AllocsForIndirectGlobals.erase(V);
+
+    // And clear out the handle.
+    setValPtr(nullptr);
+    GMR.Handles.erase(I);
+    // This object is now destroyed!
+  }
+};
+
 /// AnalyzeGlobals - Scan through the users of all of the internal
 /// GlobalValue's in the program.  If none of them have their "address taken"
 /// (really, their address passed to something nontrivial), record this fact,
 /// and record the functions that they are used directly in.
 void GlobalsModRef::AnalyzeGlobals(Module &M) {
   std::vector<Function *> Readers, Writers;
   for (Function &F : M)
     if (F.hasLocalLinkage()) {
       if (!AnalyzeUsesOfPointer(&F, Readers, Writers)) {
         // Remember that we are tracking this global.
         NonAddressTakenGlobals.insert(&F);
+        Handles.emplace_front(*this, &F);
+        Handles.front().I = Handles.begin();
         ++NumNonAddrTakenFunctions;
       }
       Readers.clear();
       Writers.clear();
     }
 
   for (GlobalVariable &GV : M.globals())
     if (GV.hasLocalLinkage()) {
       if (!AnalyzeUsesOfPointer(&GV, Readers, Writers)) {
         // Remember that we are tracking this global, and the mod/ref fns
         NonAddressTakenGlobals.insert(&GV);
+        Handles.emplace_front(*this, &GV);
+        Handles.front().I = Handles.begin();
 
         for (Function *Reader : Readers)
           FunctionInfo[Reader].GlobalInfo[&GV] |= Ref;
 
         if (!GV.isConstant()) // No need to keep track of writers to constants
           for (Function *Writer : Writers)
             FunctionInfo[Writer].GlobalInfo[&GV] |= Mod;
         ++NumNonAddrTakenGlobalVars;
if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
       return false;
     }
   }
 
   // Okay, this is an indirect global.  Remember all of the allocations for
   // this global in AllocsForIndirectGlobals.
   while (!AllocRelatedValues.empty()) {
     AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
+    Handles.emplace_front(*this, AllocRelatedValues.back());
+    Handles.front().I = Handles.begin();
     AllocRelatedValues.pop_back();
   }
   IndirectGlobals.insert(GV);
+  Handles.emplace_front(*this, GV);
+  Handles.front().I = Handles.begin();
   return true;
 }
 
 /// AnalyzeCallGraph - At this point, we know the functions where globals are
 /// immediately stored to and read from.  Propagate this information up the call
 /// graph to all callers and compute the mod/ref info for all memory for each
 /// function.
 void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
if (GV->hasLocalLinkage())
         if (NonAddressTakenGlobals.count(GV))
           if (const FunctionRecord *FR = getFunctionInfo(F))
             Known = FR->getInfoForGlobal(GV);
 
   if (Known == NoModRef)
     return NoModRef; // No need to query other mod/ref analyses
   return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, Loc));
 }
-
-//===----------------------------------------------------------------------===//
-// Methods to update the analysis as a result of the client transformation.
-//
-void GlobalsModRef::deleteValue(Value *V) {
-  if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
-    if (NonAddressTakenGlobals.erase(GV)) {
-      // This global might be an indirect global.  If so, remove it and remove
-      // any AllocRelatedValues for it.
-      if (IndirectGlobals.erase(GV)) {
-        // Remove any entries in AllocsForIndirectGlobals for this global.
-        for (std::map<const Value *, const GlobalValue *>::iterator
-                 I = AllocsForIndirectGlobals.begin(),
-                 E = AllocsForIndirectGlobals.end();
-             I != E;) {
-          if (I->second == GV) {
-            AllocsForIndirectGlobals.erase(I++);
-          } else {
-            ++I;
-          }
-        }
-      }
-    }
-  }
-
-  // Otherwise, if this is an allocation related to an indirect global, remove
-  // it.
-  AllocsForIndirectGlobals.erase(V);
-
-  AliasAnalysis::deleteValue(V);
-}