[PM/AA] Remove the addEscapingUse update API that won't be easy to directly model in the new PM.

[chandlerc]

Summary

This also was an incredibly brittle and expensive update API that was
never fully utilized by all the passes that claimed to preserve AA, nor
could it reasonably have been extended to all of them. Any number of
places add uses of values. If we ever wanted to reliably instrument
this, we would want a callback hook much like we have with ValueHandles,
but doing this for every use addition seems *extremely* expensive in
terms of compile time.

The only user of this update mechanism is GlobalsModRef. The idea of
using this to keep it up to date doesn't really work anyways as its
analysis requires a symmetric analysis of two different memory
locations. It would be very hard to make updates be sufficiently
rigorous to *guarantee* symmetric analysis in this way, and it pretty
certainly isn't true today.

However, folks have been using GMR with this update for a long time and
seem to not be hitting the issues. The reported issue that the update
hook fixes isn't even a problem any more as other changes to
GetUnderlyingObject worked around it, and that issue stemmed from *many*
years ago. As a consequence, a prior patch provided a flag to control
the unsafe behavior of GMR, and this patch removes the update mechanism
that has questionable compile-time tradeoffs and is causing problems
with moving to the new pass manager. Note the lack of test updates --
not one test in tree actually requires this update, even for a contrived
case.

All of this was extensively discussed on the dev list, this patch will
just enact what that discussion decides on. I'm sending it for review in
part to show what I'm planning, and in part to show the *amazing* amount
of work this avoids. Every call to the AA here is something like three
to six indirect function calls, which in the non-LTO pipeline never do
any work! =[

Depends on D11213.

[pete]

Makes sense to remove this and get a new API in future. I think the discussion on llvmdev is extensive enough that not much more to say here than LGTM.

[Gerolf]

I don't know this code well enough for a quality review. Certainly agree with the notion that this is a very brittle interface that is hard to maintain. And I trust your judgement that the original intent it was invented for is now obsolete. LGTM with these constraints. Also, as a bit orthogonal issue, but since you argue with ease of migration to the new pass manager (NPM): do you have a list of (potentially) performance relevant passes that could run into integration issues down the road? I suspect more(similar) performance-stability trade-offs on the road to NPM. Thanks!

[chandlerc]

Thanks Pete and Gerolf for the review. Submitting shortly.

In D11214#205912, @Gerolf wrote:

I don't know this code well enough for a quality review. Certainly agree with the notion that this is a very brittle interface that is hard to maintain. And I trust your judgement that the original intent it was invented for is now obsolete. LGTM with these constraints. Also, as a bit orthogonal issue, but since you argue with ease of migration to the new pass manager (NPM): do you have a list of (potentially) performance relevant passes that could run into integration issues down the road? I suspect more(similar) performance-stability trade-offs on the road to NPM. Thanks!

I think I'm running out of things that will actually be substantially different between the two. AA was very near the bottom of the pile, and most of the others I've been able to fix without regressions.

The only other big one is one I already know is coming (but that will be super hard). The call graph used to drive the inliner will be different between the two pass managers. Specifically, the NPM will end up with a more precise call graph (LazyCallGraph, its already in the tree) and this may cause some significant differences with how functions are visited in the CGSCC walk. Sadly, fixing these to be the same is also *hard*. But I'm hopeful that while the difference is theoretically significant it won't in practice cause substantial performance differences.

llvm/trunk/include/llvm/Analysis/AliasAnalysis.h

public:
   ///
 
   /// deleteValue - This method should be called whenever an LLVM Value is
   /// deleted from the program, for example when an instruction is found to be
   /// redundant and is eliminated.
   ///
   virtual void deleteValue(Value *V);
 
-  /// addEscapingUse - This method should be used whenever an escaping use is
-  /// added to a pointer value.  Analysis implementations may either return
-  /// conservative responses for that value in the future, or may recompute
-  /// some or all internal state to continue providing precise responses.
-  ///
-  /// Escaping uses are considered by anything _except_ the following:
-  ///  - GEPs or bitcasts of the pointer
-  ///  - Loads through the pointer
-  ///  - Stores through (but not of) the pointer
-  virtual void addEscapingUse(Use &U);
-
   /// replaceWithNewValue - This method is the obvious combination of the two
   /// above, and it provided as a helper to simplify client code.
   ///
   void replaceWithNewValue(Value *Old, Value *New) {
     deleteValue(Old);
   }
 };
 

llvm/trunk/lib/Analysis/AliasAnalysis.cpp

AliasAnalysis::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
   return AA->getArgModRefInfo(CS, ArgIdx);
 }
 
 void AliasAnalysis::deleteValue(Value *V) {
   assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
   AA->deleteValue(V);
 }
 
-void AliasAnalysis::addEscapingUse(Use &U) {
-  assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!");
-  AA->addEscapingUse(U);
-}
-
 AliasAnalysis::ModRefResult
 AliasAnalysis::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
   // We may have two calls
   if (auto CS = ImmutableCallSite(I)) {
     // Check if the two calls modify the same memory
     return getModRefInfo(Call, CS);
   } else {
     // Otherwise, check if the call modifies or references the

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

if (const Function *F = CS.getCalledFunction())
         else if ((FR->FunctionEffect & Mod) == 0)
           Min = OnlyReadsMemory;
       }
 
     return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
   }
 
   void deleteValue(Value *V) override;
-  void addEscapingUse(Use &U) 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;
void GlobalsModRef::deleteValue(Value *V) {
   }
 
   // Otherwise, if this is an allocation related to an indirect global, remove
   // it.
   AllocsForIndirectGlobals.erase(V);
 
   AliasAnalysis::deleteValue(V);
 }
-
-void GlobalsModRef::addEscapingUse(Use &U) {
-  // For the purposes of this analysis, it is conservatively correct to treat
-  // a newly escaping value equivalently to a deleted one.  We could perhaps
-  // be more precise by processing the new use and attempting to update our
-  // saved analysis results to accommodate it.
-  deleteValue(U);
-
-  AliasAnalysis::addEscapingUse(U);
-}

llvm/trunk/lib/Analysis/NoAliasAnalysis.cpp

ModRefResult getModRefInfo(ImmutableCallSite CS,
       return ModRef;
     }
     ModRefResult getModRefInfo(ImmutableCallSite CS1,
                                ImmutableCallSite CS2) override {
       return ModRef;
     }
 
     void deleteValue(Value *V) override {}
-    void addEscapingUse(Use &U) 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(const void *ID) override {
       if (ID == &AliasAnalysis::ID)
         return (AliasAnalysis*)this;

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) {
 
     if (SSAUpdate.HasValueForBlock(BB))
       continue;
 
     SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(LI, gvn));
   }
 
   // Perform PHI construction.
-  Value *V = SSAUpdate.GetValueInMiddleOfBlock(LI->getParent());
-
-  // If new PHI nodes were created, notify alias analysis.
-  if (V->getType()->getScalarType()->isPointerTy()) {
-    AliasAnalysis *AA = gvn.getAliasAnalysis();
-
-    // Scan the new PHIs and inform alias analysis that we've added potentially
-    // escaping uses to any values that are operands to these PHIs.
-    for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) {
-      PHINode *P = NewPHIs[i];
-      for (unsigned ii = 0, ee = P->getNumIncomingValues(); ii != ee; ++ii) {
-        unsigned jj = PHINode::getOperandNumForIncomingValue(ii);
-        AA->addEscapingUse(P->getOperandUse(jj));
-      }
-    }
-  }
-
-  return V;
+  return SSAUpdate.GetValueInMiddleOfBlock(LI->getParent());
 }
 
 Value *AvailableValueInBlock::MaterializeAdjustedValue(LoadInst *LI,
                                                        GVN &gvn) const {
   Value *Res;
   Type *LoadTy = LI->getType();
   const DataLayout &DL = LI->getModule()->getDataLayout();
   if (isSimpleValue()) {
for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
     else
       Phi->addIncoming(PREInstr, PREPred);
   }
 
   VN.add(Phi, ValNo);
   addToLeaderTable(ValNo, Phi, CurrentBlock);
   Phi->setDebugLoc(CurInst->getDebugLoc());
   CurInst->replaceAllUsesWith(Phi);
-  if (Phi->getType()->getScalarType()->isPointerTy()) {
-    // Because we have added a PHI-use of the pointer value, it has now
-    // "escaped" from alias analysis' perspective.  We need to inform
-    // AA of this.
-    for (unsigned ii = 0, ee = Phi->getNumIncomingValues(); ii != ee; ++ii) {
-      unsigned jj = PHINode::getOperandNumForIncomingValue(ii);
-      VN.getAliasAnalysis()->addEscapingUse(Phi->getOperandUse(jj));
-    }
-
-    if (MD)
-      MD->invalidateCachedPointerInfo(Phi);
-  }
+  if (MD && Phi->getType()->getScalarType()->isPointerTy())
   VN.erase(CurInst);
   removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
 
   DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
   if (MD)
     MD->removeInstruction(CurInst);
   DEBUG(verifyRemoved(CurInst));
   CurInst->eraseFromParent();

llvm/trunk/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

PHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0,
   PHINode *NewPN = 0;
   Value *Opd1 = S0->getValueOperand();
   Value *Opd2 = S1->getValueOperand();
   if (Opd1 != Opd2) {
     NewPN = PHINode::Create(Opd1->getType(), 2, Opd2->getName() + ".sink",
                             BB->begin());
     NewPN->addIncoming(Opd1, S0->getParent());
     NewPN->addIncoming(Opd2, S1->getParent());
-    if (NewPN->getType()->getScalarType()->isPointerTy()) {
-      // AA needs to be informed when a PHI-use of the pointer value is added
-      for (unsigned I = 0, E = NewPN->getNumIncomingValues(); I != E; ++I) {
-        unsigned J = PHINode::getOperandNumForIncomingValue(I);
-        AA->addEscapingUse(NewPN->getOperandUse(J));
-      }
-      if (MD)
-        MD->invalidateCachedPointerInfo(NewPN);
-    }
-  }
+    if (MD && NewPN->getType()->getScalarType()->isPointerTy())
   return NewPN;
 }
 
 ///
 /// \brief Merge two stores to same address and sink into \p BB
 ///
 /// Also sinks GEP instruction computing the store address
 ///