[IPT] Drop cache less eagerly in GVN and LoopSafetyInfo

[mkazantsev]

Summary

Current strategy of dropping InstructionPrecedenceTracking cache is to
invalidate the entire basic block whenever we change its contents. In fact,
InstructionPrecedenceTracking has 2 internal strictures: OrderedInstructions
that is needed to be invalidated whenever the contents changes, and the map
with first special instructions in block. This second map does not need an
update if we add/remove a non-special instuction because it cannot
affect the contents of this map.

This patch changes API of InstructionPrecedenceTracking so that it now
accounts for reasons under which we invalidate blocks. This should lead
to much less recalculations the map and should save us some compile time
because in practice we don't typically add/remove special instructions.

[mkazantsev]

Ping?

[efriedma]

LGTM

llvm/trunk/include/llvm/Analysis/InstructionPrecedenceTracking.h

protected:
   /// children classes allows to implement tracking of implicit control flow,
   /// memory writing instructions or any other kinds of instructions we might
   /// be interested in.
   virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
 
   virtual ~InstructionPrecedenceTracking() = default;
 
 public:
-  /// Clears cached information about this particular block.
-  void invalidateBlock(const BasicBlock *BB);
+  /// Notifies this tracking that we are going to insert a new instruction \p
+  /// Inst to the basic block \p BB. It makes all necessary updates to internal
+  /// caches to keep them consistent.
+  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
+
+  /// Notifies this tracking that we are going to remove the instruction \p Inst
+  /// It makes all necessary updates to internal caches to keep them consistent.
+  void removeInstruction(const Instruction *Inst);
 
   /// Invalidates all information from this tracking.
   void clear();
 };
 
 /// This class allows to keep track on instructions with implicit control flow.
 /// These are instructions that may not pass execution to their successors. For
 /// example, throwing calls and guards do not always do this. If we need to know

llvm/trunk/include/llvm/Analysis/MustExecute.h

bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
       const;
 
   /// Returns true if we could not execute a memory-modifying instruction before
   /// we execute \p I under assumption that \p CurLoop is entered.
   bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
       const;
 
   /// Inform the safety info that we are planning to insert a new instruction
-  /// into the basic block \p BB. It will make all cache updates to keep it
-  /// correct after this insertion.
-  void insertInstructionTo(const BasicBlock *BB);
+  /// \p Inst into the basic block \p BB. It will make all cache updates to keep
+  /// it correct after this insertion.
+  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
 
   /// Inform safety info that we are planning to remove the instruction \p Inst
   /// from its block. It will make all cache updates to keep it correct after
   /// this removal.
   void removeInstruction(const Instruction *Inst);
 
   ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
 
   virtual ~ICFLoopSafetyInfo() {};
 };
 
 }
 
 #endif

llvm/trunk/lib/Analysis/InstructionPrecedenceTracking.cpp

 
 void InstructionPrecedenceTracking::validateAll() const {
   // Check that for every known block the cached value is correct.
   for (auto &It : FirstSpecialInsts)
     validate(It.first);
 }
 #endif
 
-void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
-  OI.invalidateBlock(BB);
+void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
+                                                        const BasicBlock *BB) {
+  if (isSpecialInstruction(Inst))
     FirstSpecialInsts.erase(BB);
+  OI.invalidateBlock(BB);
+}
+
+void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
+  if (isSpecialInstruction(Inst))
+    FirstSpecialInsts.erase(Inst->getParent());
+  OI.invalidateBlock(Inst->getParent());
 }
 
 void InstructionPrecedenceTracking::clear() {
   for (auto It : FirstSpecialInsts)
     OI.invalidateBlock(It.first);
   FirstSpecialInsts.clear();
 #ifndef NDEBUG
   // The map should be valid after clearing (at least empty).

llvm/trunk/lib/Analysis/MustExecute.cpp

void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
   for (auto &BB : CurLoop->blocks())
     if (ICF.hasICF(&*BB)) {
       MayThrow = true;
       break;
     }
   computeBlockColors(CurLoop);
 }
 
-void ICFLoopSafetyInfo::insertInstructionTo(const BasicBlock *BB) {
-  ICF.invalidateBlock(BB);
-  MW.invalidateBlock(BB);
+void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
+                                            const BasicBlock *BB) {
+  ICF.insertInstructionTo(Inst, BB);
+  MW.insertInstructionTo(Inst, BB);
 }
 
 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
-  // TODO: So far we just conservatively drop cache, but maybe we can not do it
-  // when Inst is not an ICF instruction. Follow-up on that.
-  ICF.invalidateBlock(Inst->getParent());
-  MW.invalidateBlock(Inst->getParent());
+  ICF.removeInstruction(Inst);
+  MW.removeInstruction(Inst);
 }
 
 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
   // Compute funclet colors if we might sink/hoist in a function with a funclet
   // personality routine.
   Function *Fn = CurLoop->getHeader()->getParent();
   if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())

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

if (!AtStart)
       --BI;
 
     for (auto *I : InstrsToErase) {
       assert(I->getParent() == BB && "Removing instruction from wrong block?");
       LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
       salvageDebugInfo(*I);
       if (MD) MD->removeInstruction(I);
       LLVM_DEBUG(verifyRemoved(I));
+      ICF->removeInstruction(I);
       I->eraseFromParent();
     }
-
-    ICF->invalidateBlock(BB);
     InstrsToErase.clear();
 
     if (AtStart)
       BI = BB->begin();
     else
       ++BI;
   }
 
bool GVN::performScalarPRE(Instruction *CurInst) {
   removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
 
   LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
   if (MD)
     MD->removeInstruction(CurInst);
   LLVM_DEBUG(verifyRemoved(CurInst));
   // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
   // some assertion failures.
-  ICF->invalidateBlock(CurrentBlock);
+  ICF->removeInstruction(CurInst);
   CurInst->eraseFromParent();
   ++NumGVNInstr;
 
   return true;
 }
 
 /// Perform a purely local form of PRE that looks for diamond
 /// control flow patterns and attempts to perform simple PRE at the join point.

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

for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       // converting it to a reciprocal multiplication.
       if (I.getOpcode() == Instruction::FDiv &&
           CurLoop->isLoopInvariant(I.getOperand(1)) &&
           I.hasAllowReciprocal()) {
         auto Divisor = I.getOperand(1);
         auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
         auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
         ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
-        SafetyInfo->insertInstructionTo(I.getParent());
+        SafetyInfo->insertInstructionTo(ReciprocalDivisor, I.getParent());
         ReciprocalDivisor->insertBefore(&I);
 
         auto Product =
             BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
         Product->setFastMathFlags(I.getFastMathFlags());
-        SafetyInfo->insertInstructionTo(I.getParent());
+        SafetyInfo->insertInstructionTo(Product, I.getParent());
         Product->insertAfter(&I);
         I.replaceAllUsesWith(Product);
         eraseInstruction(I, *SafetyInfo, CurAST);
 
         hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
               SafetyInfo, ORE);
         HoistedInstructions.push_back(ReciprocalDivisor);
         Changed = true;
if (AST)
     AST->deleteValue(&I);
   SafetyInfo.removeInstruction(&I);
   I.eraseFromParent();
 }
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
                                   ICFLoopSafetyInfo &SafetyInfo) {
   SafetyInfo.removeInstruction(&I);
-  SafetyInfo.insertInstructionTo(Dest.getParent());
+  SafetyInfo.insertInstructionTo(&I, Dest.getParent());
   I.moveBefore(&Dest);
 }
 
 static Instruction *sinkThroughTriviallyReplaceablePHI(
     PHINode *TPN, Instruction *I, LoopInfo *LI,
     SmallDenseMap<BasicBlock *, Instruction *, 32> &SunkCopies,
     const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop) {
   assert(isTriviallyReplaceablePHI(*TPN, *I) &&