[AssumeBundles] Adapt RecursivelyDeleteTriviallyDeadInstructions and depending passes.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1102

This looks suspicious. Are we sure we don't invalidate an element in here and need the tracking behavior?

llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp

139 ↗

(On Diff #256026)

Could you explain this check? When would a call return a nullptr of an arg operand? isn't there an assertion against that?

210 ↗

(On Diff #256026)

This doesn't sound right. null operands will explode everywhere, how could they happen?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

220

I guess this is an NFC rewrite? We should split it into a separate commit though, only this file, creating the members.

[Tyker]

fixed

[Tyker]

Sorry i messed up will uploading the diff.
this diff should be fine.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1192

Are we sure the instruction could not have been deleted at this point? If not we need to check for null in the cast.

---

I think it is reasonable to assume all instructions are in the same function. We should query AC before the loop.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

879

Unsure if it helps but one could add comments to the nullptr here and elsewhere: /* MSSAU */

llvm/test/Transforms/Attributor/ArgumentPromotion/byval-2.ll

37 ↗

(On Diff #256055)

Note: We really have to teach the Attributor to prune these. I'll get to it or make it a task for one of the GSoC students.

[jdoerfert]

llvm/test/Transforms/Attributor/ArgumentPromotion/byval-2.ll

3 ↗

(On Diff #256055)

When you rebase you'll get a conflict. I recommend using the new file and adding --enable-knowledge-retention to some or all of the 4 run configurations. check lines are generated :)

[Tyker]

addressed comments.

Note: this patch depend on D77402 and D76149 that should be reviewed first.

[Tyker]

llvm/test/Transforms/Attributor/ArgumentPromotion/byval-2.ll

3 ↗

(On Diff #256055)

thanks for the heads up.

37 ↗

(On Diff #256055)

by prune you mean removing redundant knowledge ?

[Tyker]

rebased

[jdoerfert]

I think we need to run some of the affected passes with knowledge preservation to get more test coverage. Also two more comments below.

llvm/lib/Transforms/IPO/Attributor.cpp

1192

I'm unsure why I thought all dead instructions are in the same function. I somehow fear we need to sort them by function. Maybe we can go ahead with the patch without this change first?

llvm/unittests/Transforms/Utils/LocalTest.cpp

39

Commit this as test improvements.

[jdoerfert]

What is the status on this one? Are there other AssumeBundle patches pending or missing?

[Tyker]

In D77734#2117317, @jdoerfert wrote:

What is the status on this one? Are there other AssumeBundle patches pending or missing?

since the creation of the patch many patches on assume bundles have landed and I don't think this patch is needed any more

llvm/include/llvm/Transforms/Utils/Local.h

 bool wouldInstructionBeTriviallyDead(Instruction *I,
                                      const TargetLibraryInfo *TLI = nullptr);
 
 /// If the specified value is a trivially dead instruction, delete it.
 /// If that makes any of its operands trivially dead, delete them too,
 /// recursively. Return true if any instructions were deleted.
 bool RecursivelyDeleteTriviallyDeadInstructions(
     Value *V, const TargetLibraryInfo *TLI = nullptr,
-    MemorySSAUpdater *MSSAU = nullptr);
+    MemorySSAUpdater *MSSAU = nullptr, AssumptionCache *AC = nullptr);
 
 /// Delete all of the instructions in `DeadInsts`, and all other instructions
 /// that deleting these in turn causes to be trivially dead.
 ///
 /// The initial instructions in the provided vector must all have empty use
 /// lists and satisfy `isInstructionTriviallyDead`.
 ///
 /// `DeadInsts` will be used as scratch storage for this routine and will be
 /// empty afterward.
 void RecursivelyDeleteTriviallyDeadInstructions(
     SmallVectorImpl<WeakTrackingVH> &DeadInsts,
-    const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr);
+    const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr,
+    AssumptionCache *AC = nullptr);
 
 /// Same functionality as RecursivelyDeleteTriviallyDeadInstructions, but allow
 /// instructions that are not trivially dead. These will be ignored.
 /// Returns true if any changes were made, i.e. any instructions trivially dead
 /// were found and deleted.
 bool RecursivelyDeleteTriviallyDeadInstructionsPermissive(
     SmallVectorImpl<WeakTrackingVH> &DeadInsts,
-    const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr);
+    const TargetLibraryInfo *TLI = nullptr, MemorySSAUpdater *MSSAU = nullptr,
+    AssumptionCache *AC = nullptr);
 
 /// If the specified value is an effectively dead PHI node, due to being a
 /// def-use chain of single-use nodes that either forms a cycle or is terminated
 /// by a trivially dead instruction, delete it. If that makes any of its
 /// operands trivially dead, delete them too, recursively. Return true if a
 /// change was made.
 bool RecursivelyDeleteDeadPHINode(PHINode *PN,
                                   const TargetLibraryInfo *TLI = nullptr,

 /// and parallel-or mode to collapse if-conditions and merge if-regions with
 /// identical statements.
 bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr);
 
 /// If this basic block is ONLY a setcc and a branch, and if a predecessor
 /// branches to us and one of our successors, fold the setcc into the
 /// predecessor and use logical operations to pick the right destination.
 bool FoldBranchToCommonDest(BranchInst *BI, MemorySSAUpdater *MSSAU = nullptr,
-                            unsigned BonusInstThreshold = 1);
+                            unsigned BonusInstThreshold = 1,
+                            AssumptionCache *AC = nullptr);
 
 /// This function takes a virtual register computed by an Instruction and
 /// replaces it with a slot in the stack frame, allocated via alloca.
 /// This allows the CFG to be changed around without fear of invalidating the
 /// SSA information for the value. It returns the pointer to the alloca inserted
 /// to create a stack slot for X.
 AllocaInst *DemoteRegToStack(Instruction &X,
                              bool VolatileLoads = false,

llvm/lib/Transforms/IPO/Attributor.cpp

ChangeStatus Attributor::run() {
   // Delete stuff at the end to avoid invalid references and a nice order.
   {
     LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least "
                       << ToBeDeletedFunctions.size() << " functions and "
                       << ToBeDeletedBlocks.size() << " blocks and "
                       << ToBeDeletedInsts.size() << " instructions and "
                       << ToBeChangedUses.size() << " uses\n");
 
     SmallVector<WeakTrackingVH, 32> DeadInsts;
     SmallVector<Instruction *, 32> TerminatorsToFold;
 
     for (auto &It : ToBeChangedUses) {
       Use *U = It.first;
       Value *NewV = It.second;
       Value *OldV = U->get();
 
       // Do not replace uses in returns if the value is a must-tail call we will
for (auto &V : ToBeDeletedInsts) {
           I->replaceAllUsesWith(UndefValue::get(I->getType()));
         if (!isa<PHINode>(I) && isInstructionTriviallyDead(I))
           DeadInsts.push_back(I);
         else
           I->eraseFromParent();
       }
     }
 
-    RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
+    AssumptionCache *AC = nullptr;
+    for (auto &Inst : DeadInsts)
+      if (Inst.pointsToAliveValue()) {
+        AC = InfoCache.AG.getAnalysis<AssumptionAnalysis>(
+            *cast<Instruction>(Inst)->getFunction());
+        break;
+      }
+    RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, nullptr, nullptr, AC);
 
     if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
       SmallVector<BasicBlock *, 8> ToBeDeletedBBs;
       ToBeDeletedBBs.reserve(NumDeadBlocks);
       for (BasicBlock *BB : ToBeDeletedBlocks) {
         CGModifiedFunctions.insert(BB->getParent());
         ToBeDeletedBBs.push_back(BB);
       }

llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp

for (BasicBlock &BB : F) {
             ++NumSimplified;
             Changed = true;
             // A call can get simplified, but it may not be trivially dead.
             if (isInstructionTriviallyDead(&I))
               DeadInstsInBB.push_back(&I);
           }
         }
       }
-      RecursivelyDeleteTriviallyDeadInstructions(DeadInstsInBB, SQ.TLI);
+      RecursivelyDeleteTriviallyDeadInstructions(DeadInstsInBB, SQ.TLI, nullptr,
+                                                 SQ.AC);
     }
 
     // Place the list of instructions to simplify on the next loop iteration
     // into ToSimplify.
     std::swap(ToSimplify, Next);
     Next->clear();
   } while (!ToSimplify->empty());
 

llvm/lib/Transforms/Scalar/LoopInstSimplify.cpp

for (BasicBlock *BB : RPOT) {
         Changed = true;
       }
     }
 
     // Delete any dead instructions found thus far now that we've finished an
     // iteration over all instructions in all the loop blocks.
     if (!DeadInsts.empty()) {
       Changed = true;
-      RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
+      RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU, &AC);
     }
 
     if (MSSAU && VerifyMemorySSA)
       MSSA->verifyMemorySSA();
 
     // If we never found a PHI that needs to be simplified in the next
     // iteration, we're done.
     if (Next->empty())

llvm/lib/Transforms/Scalar/NaryReassociate.cpp

for (auto I = BB->begin(); I != BB->end(); ++I) {
         const SCEV *OldSCEV = SE->getSCEV(&*I);
         if (Instruction *NewI = tryReassociate(&*I)) {
           Changed = true;
           SE->forgetValue(&*I);
           I->replaceAllUsesWith(NewI);
           WeakVH NewIExist = NewI;
           // If SeenExprs/NewIExist contains I's WeakTrackingVH/WeakVH, that
           // entry will be replaced with nullptr if deleted.
-          RecursivelyDeleteTriviallyDeadInstructions(&*I, TLI);
+          RecursivelyDeleteTriviallyDeadInstructions(&*I, TLI, nullptr, AC);
           if (!NewIExist) {
             // Rare occation where the new instruction (NewI) have been removed,
             // probably due to parts of the input code was dead from the
             // beginning, reset the iterator and start over from the beginning
             I = BB->begin();
             continue;
           }
           I = NewI->getIterator();

llvm/lib/Transforms/Utils/Local.cpp

 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
+#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <iterator>
 #include <map>
 #include <utility>
 
bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
   return false;
 }
 
 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 /// trivially dead instruction, delete it.  If that makes any of its operands
 /// trivially dead, delete them too, recursively.  Return true if any
 /// instructions were deleted.
 bool llvm::RecursivelyDeleteTriviallyDeadInstructions(
-    Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU) {
+    Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU,
+    AssumptionCache *AC) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I || !isInstructionTriviallyDead(I, TLI))
     return false;
 
   SmallVector<WeakTrackingVH, 16> DeadInsts;
   DeadInsts.push_back(I);
-  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU);
+  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU, AC);
 
   return true;
 }
 
 bool llvm::RecursivelyDeleteTriviallyDeadInstructionsPermissive(
     SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
-    MemorySSAUpdater *MSSAU) {
+    MemorySSAUpdater *MSSAU, AssumptionCache *AC) {
   unsigned S = 0, E = DeadInsts.size(), Alive = 0;
   for (; S != E; ++S) {
     auto *I = cast<Instruction>(DeadInsts[S]);
     if (!isInstructionTriviallyDead(I)) {
       DeadInsts[S] = nullptr;
       ++Alive;
     }
   }
   if (Alive == E)
     return false;
-  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU);
+  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU, AC);
   return true;
 }
 
 void llvm::RecursivelyDeleteTriviallyDeadInstructions(
     SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
-    MemorySSAUpdater *MSSAU) {
+    MemorySSAUpdater *MSSAU, AssumptionCache *AC) {
   // Process the dead instruction list until empty.
   while (!DeadInsts.empty()) {
     Value *V = DeadInsts.pop_back_val();
     Instruction *I = cast_or_null<Instruction>(V);
     if (!I)
       continue;
     assert(isInstructionTriviallyDead(I, TLI) &&
            "Live instruction found in dead worklist!");
     assert(I->use_empty() && "Instructions with uses are not dead.");
 
     // Don't lose the debug info while deleting the instructions.
     salvageDebugInfo(*I);
+    salvageKnowledge(I, AC);
 
     // Null out all of the instruction's operands to see if any operand becomes
     // dead as we go.
     for (Use &OpU : I->operands()) {
       Value *OpV = OpU.get();
       OpU.set(nullptr);
 
       if (!OpV->use_empty())

 
 static bool
 simplifyAndDCEInstruction(Instruction *I,
                           SmallSetVector<Instruction *, 16> &WorkList,
                           const DataLayout &DL,
                           const TargetLibraryInfo *TLI) {
   if (isInstructionTriviallyDead(I, TLI)) {
     salvageDebugInfo(*I);
+    salvageKnowledge(I);
 
     // Null out all of the instruction's operands to see if any operand becomes
     // dead as we go.
     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
       Value *OpV = I->getOperand(i);
       I->setOperand(i, nullptr);
 
       if (!OpV->use_empty() || I == OpV)

llvm/lib/Transforms/Utils/LoopUnroll.cpp

if (SE && SimplifyIVs) {
     SmallVector<WeakTrackingVH, 16> DeadInsts;
     simplifyLoopIVs(L, SE, DT, LI, TTI, DeadInsts);
 
     // Aggressively clean up dead instructions that simplifyLoopIVs already
     // identified. Any remaining should be cleaned up below.
     while (!DeadInsts.empty()) {
       Value *V = DeadInsts.pop_back_val();
       if (Instruction *Inst = dyn_cast_or_null<Instruction>(V))
-        RecursivelyDeleteTriviallyDeadInstructions(Inst);
+        RecursivelyDeleteTriviallyDeadInstructions(Inst, nullptr, nullptr, AC);
     }
   }
 
   // At this point, the code is well formed.  We now do a quick sweep over the
   // inserted code, doing constant propagation and dead code elimination as we
   // go.
   const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
   for (BasicBlock *BB : L->getBlocks()) {

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
                               const TargetTransformInfo &TTI);
   bool SimplifyTerminatorOnSelect(Instruction *OldTerm, Value *Cond,
                                   BasicBlock *TrueBB, BasicBlock *FalseBB,
                                   uint32_t TrueWeight, uint32_t FalseWeight);
   bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
                                  const DataLayout &DL);
   bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select);
   bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI);
   bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder);
 
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
                  SmallPtrSetImpl<BasicBlock *> *LoopHeaders,
                  const SimplifyCFGOptions &Opts)
       : TTI(TTI), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {}
 
   bool run(BasicBlock *BB);
while (!DFT.empty()) {
       CompValue = nullptr;
       break;
     }
   }
 };
 
 } // end anonymous namespace
 
-static void EraseTerminatorAndDCECond(Instruction *TI,
-                                      MemorySSAUpdater *MSSAU = nullptr) {
+static void EraseTerminatorAndDCECond(Instruction *TI, MemorySSAUpdater *MSSAU,
+                                      AssumptionCache *AC) {
   Instruction *Cond = nullptr;
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
     Cond = dyn_cast<Instruction>(SI->getCondition());
   } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
     if (BI->isConditional())
       Cond = dyn_cast<Instruction>(BI->getCondition());
   } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) {
     Cond = dyn_cast<Instruction>(IBI->getAddress());
if (isa<BranchInst>(TI)) {
 
       // Remove PHI node entries for the dead edge.
       ThisCases[0].Dest->removePredecessor(TI->getParent());
 
       LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
                         << "Through successor TI: " << *TI << "Leaving: " << *NI
                         << "\n");
 
-      EraseTerminatorAndDCECond(TI);
+      EraseTerminatorAndDCECond(TI, /*MSSAU*/ nullptr, Options.AC);
       return true;
     }
 
     SwitchInstProfUpdateWrapper SI = *cast<SwitchInst>(TI);
     // Okay, TI has cases that are statically dead, prune them away.
     SmallPtrSet<Constant *, 16> DeadCases;
     for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
       DeadCases.insert(PredCases[i].Value);
bool SimplifyCFGOpt::SimplifyEqualityComparisonWithOnlyPredecessor(
   // Insert the new branch.
   Instruction *NI = Builder.CreateBr(TheRealDest);
   (void)NI;
 
   LLVM_DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
                     << "Through successor TI: " << *TI << "Leaving: " << *NI
                     << "\n");
 
-  EraseTerminatorAndDCECond(TI);
+  EraseTerminatorAndDCECond(TI, /*MSSAU*/ nullptr, Options.AC);
   return true;
 }
 
 namespace {
 
 /// This class implements a stable ordering of constant
 /// integers that does not depend on their address.  This is important for
 /// applications that sort ConstantInt's to ensure uniqueness.
if (PCV == CV && TI != PTI) {
         // Halve the weights if any of them cannot fit in an uint32_t
         FitWeights(Weights);
 
         SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end());
 
         setBranchWeights(NewSI, MDWeights);
       }
 
-      EraseTerminatorAndDCECond(PTI);
+      EraseTerminatorAndDCECond(PTI, /*MSSAU*/ nullptr, Options.AC);
 
       // Okay, last check.  If BB is still a successor of PSI, then we must
       // have an infinite loop case.  If so, add an infinitely looping block
       // to handle the case to preserve the behavior of the code.
       BasicBlock *InfLoopBlock = nullptr;
       for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i)
         if (NewSI->getSuccessor(i) == BB) {
           if (!InfLoopBlock) {
for (PHINode &PN : Succ->phis()) {
           PN.setIncomingValue(i, SI);
     }
   }
 
   // Update any PHI nodes in our new successors.
   for (BasicBlock *Succ : successors(BB1))
     AddPredecessorToBlock(Succ, BIParent, BB1);
 
-  EraseTerminatorAndDCECond(BI);
+  EraseTerminatorAndDCECond(BI, /*MSSAU*/ nullptr, Options.AC);
   return true;
 }
 
 // Check lifetime markers.
 static bool isLifeTimeMarker(const Instruction *I) {
   if (auto II = dyn_cast<IntrinsicInst>(I)) {
     switch (II->getIntrinsicID()) {
     default:
bool SimplifyCFGOpt::SimplifyCondBranchToTwoReturns(BranchInst *BI,
   Builder.SetInsertPoint(BI);
   // Okay, we found a branch that is going to two return nodes.  If
   // there is no return value for this function, just change the
   // branch into a return.
   if (FalseRet->getNumOperands() == 0) {
     TrueSucc->removePredecessor(BI->getParent());
     FalseSucc->removePredecessor(BI->getParent());
     Builder.CreateRetVoid();
-    EraseTerminatorAndDCECond(BI);
+    EraseTerminatorAndDCECond(BI, /*MSSAU*/ nullptr, Options.AC);
     return true;
   }
 
   // Otherwise, figure out what the true and false return values are
   // so we can insert a new select instruction.
   Value *TrueValue = TrueRet->getReturnValue();
   Value *FalseValue = FalseRet->getReturnValue();
 
Value *RI =
       !TrueValue ? Builder.CreateRetVoid() : Builder.CreateRet(TrueValue);
 
   (void)RI;
 
   LLVM_DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:"
                     << "\n  " << *BI << "\nNewRet = " << *RI << "\nTRUEBLOCK: "
                     << *TrueSucc << "\nFALSEBLOCK: " << *FalseSucc);
 
-  EraseTerminatorAndDCECond(BI);
+  EraseTerminatorAndDCECond(BI, /*MSSAU*/ nullptr, Options.AC);
 
   return true;
 }
 
 /// Return true if the given instruction is available
 /// in its predecessor block. If yes, the instruction will be removed.
 static bool tryCSEWithPredecessor(Instruction *Inst, BasicBlock *PB) {
   if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst))
if (PredHasWeights || SuccHasWeights) {
     return false;
   }
 }
 
 /// If this basic block is simple enough, and if a predecessor branches to us
 /// and one of our successors, fold the block into the predecessor and use
 /// logical operations to pick the right destination.
 bool llvm::FoldBranchToCommonDest(BranchInst *BI, MemorySSAUpdater *MSSAU,
-                                  unsigned BonusInstThreshold) {
+                                  unsigned BonusInstThreshold,
+                                  AssumptionCache *AC) {
   BasicBlock *BB = BI->getParent();
 
   const unsigned PredCount = pred_size(BB);
 
   Instruction *Cond = nullptr;
   if (BI->isConditional())
     Cond = dyn_cast<Instruction>(BI->getCondition());
   else {
PHIs[i]->setIncomingValueForBlock(PBI->getParent(), MergedCond);
 
       // PBI is changed to branch to TrueDest below. Remove itself from
       // potential phis from all other successors.
       if (MSSAU)
         MSSAU->changeCondBranchToUnconditionalTo(PBI, TrueDest);
 
       // Change PBI from Conditional to Unconditional.
       BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI);
-      EraseTerminatorAndDCECond(PBI, MSSAU);
+      EraseTerminatorAndDCECond(PBI, MSSAU, AC);
       PBI = New_PBI;
     }
 
     // If BI was a loop latch, it may have had associated loop metadata.
     // We need to copy it to the new latch, that is, PBI.
     if (MDNode *LoopMD = BI->getMetadata(LLVMContext::MD_loop))
       PBI->setMetadata(LLVMContext::MD_loop, LoopMD);
 
static bool mergeConditionalStoreToAddress(BasicBlock *PTB, BasicBlock *PFB,
   // If PostBB has more than two predecessors, we need to split it so we can
   // sink the store.
   if (std::next(pred_begin(PostBB), 2) != pred_end(PostBB)) {
     // We know that QFB's only successor is PostBB. And QFB has a single
     // predecessor. If QTB exists, then its only successor is also PostBB.
     // If QTB does not exist, then QFB's only predecessor has a conditional
     // branch to QFB and PostBB.
     BasicBlock *TruePred = QTB ? QTB : QFB->getSinglePredecessor();
-    BasicBlock *NewBB = SplitBlockPredecessors(PostBB, { QFB, TruePred},
-                                               "condstore.split");
+    BasicBlock *NewBB =
+        SplitBlockPredecessors(PostBB, {QFB, TruePred}, "condstore.split");
     if (!NewBB)
       return false;
     PostBB = NewBB;
   }
 
   // OK, we're going to sink the stores to PostBB. The store has to be
   // conditional though, so first create the predicate.
   Value *PCond = cast<BranchInst>(PFB->getSinglePredecessor()->getTerminator())
if (!KeepEdge1 && !KeepEdge2) {
     if (!KeepEdge1)
       // Only TrueBB was found.
       Builder.CreateBr(TrueBB);
     else
       // Only FalseBB was found.
       Builder.CreateBr(FalseBB);
   }
 
-  EraseTerminatorAndDCECond(OldTerm);
+  EraseTerminatorAndDCECond(OldTerm, /*MSSAU*/ nullptr, Options.AC);
   return true;
 }
 
 // Replaces
 //   (switch (select cond, X, Y)) on constant X, Y
 // with a branch - conditional if X and Y lead to distinct BBs,
 // unconditional otherwise.
 bool SimplifyCFGOpt::SimplifySwitchOnSelect(SwitchInst *SI,
bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(BranchInst *BI,
   for (BasicBlock::iterator BBI = EdgeBB->begin(); isa<PHINode>(BBI); ++BBI) {
     PHINode *PN = cast<PHINode>(BBI);
     Value *InVal = PN->getIncomingValueForBlock(BB);
     for (unsigned i = 0, e = Values.size() - 1; i != e; ++i)
       PN->addIncoming(InVal, BB);
   }
 
   // Erase the old branch instruction.
-  EraseTerminatorAndDCECond(BI);
+  EraseTerminatorAndDCECond(BI, /*MSSAU*/ nullptr, Options.AC);
 
   LLVM_DEBUG(dbgs() << "  ** 'icmp' chain result is:\n" << *BB << '\n');
   return true;
 }
 
 bool SimplifyCFGOpt::simplifyResume(ResumeInst *RI, IRBuilder<> &Builder) {
   if (isa<PHINode>(RI->getValue()))
     return simplifyCommonResume(RI);
if (auto *BI = dyn_cast<BranchInst>(TI)) {
         if (BI->getSuccessor(0) == BB) {
           Builder.CreateAssumption(Builder.CreateNot(Cond));
           Builder.CreateBr(BI->getSuccessor(1));
         } else {
           assert(BI->getSuccessor(1) == BB && "Incorrect CFG");
           Builder.CreateAssumption(Cond);
           Builder.CreateBr(BI->getSuccessor(0));
         }
-        EraseTerminatorAndDCECond(BI);
+        EraseTerminatorAndDCECond(BI, /*MSSAU*/ nullptr, Options.AC);
         Changed = true;
       }
     } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       SwitchInstProfUpdateWrapper SU(*SI);
       for (auto i = SU->case_begin(), e = SU->case_end(); i != e;) {
         if (i->getCaseSuccessor() != BB) {
           ++i;
           continue;
static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) {
   array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate);
   for (size_t I = 1, E = Cases.size(); I != E; ++I) {
     if (Cases[I - 1]->getValue() != Cases[I]->getValue() + 1)
       return false;
   }
   return true;
 }
 
-static void createUnreachableSwitchDefault(SwitchInst *Switch) {
+void createUnreachableSwitchDefault(SwitchInst *Switch, AssumptionCache *AC) {
   LLVM_DEBUG(dbgs() << "SimplifyCFG: switch default is dead.\n");
   BasicBlock *NewDefaultBlock =
      SplitBlockPredecessors(Switch->getDefaultDest(), Switch->getParent(), "");
   Switch->setDefaultDest(&*NewDefaultBlock);
   SplitBlock(&*NewDefaultBlock, &NewDefaultBlock->front());
   auto *NewTerminator = NewDefaultBlock->getTerminator();
   new UnreachableInst(Switch->getContext(), NewTerminator);
-  EraseTerminatorAndDCECond(NewTerminator);
+  EraseTerminatorAndDCECond(NewTerminator, /*MSSAU*/ nullptr, AC);
 }
 
 /// Turn a switch with two reachable destinations into an integer range
 /// comparison and branch.
 bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(SwitchInst *SI,
                                              IRBuilder<> &Builder) {
   assert(SI->getNumCases() > 1 && "Degenerate switch?");
 
if (OtherDest == SI->getDefaultDest())
       ++PreviousEdges;
     for (unsigned I = 0, E = PreviousEdges - 1; I != E; ++I)
       cast<PHINode>(BBI)->removeIncomingValue(SI->getParent());
   }
 
   // Clean up the default block - it may have phis or other instructions before
   // the unreachable terminator.
   if (!HasDefault)
-    createUnreachableSwitchDefault(SI);
+    createUnreachableSwitchDefault(SI, Options.AC);
 
   // Drop the switch.
   SI->eraseFromParent();
 
   return true;
 }
 
 /// Compute masked bits for the condition of a switch
static bool eliminateDeadSwitchCases(SwitchInst *SI, AssumptionCache *AC,
   bool HasDefault =
       !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
   const unsigned NumUnknownBits =
       Bits - (Known.Zero | Known.One).countPopulation();
   assert(NumUnknownBits <= Bits);
   if (HasDefault && DeadCases.empty() &&
       NumUnknownBits < 64 /* avoid overflow */ &&
       SI->getNumCases() == (1ULL << NumUnknownBits)) {
-    createUnreachableSwitchDefault(SI);
+    createUnreachableSwitchDefault(SI, AC);
     return true;
   }
 
   if (DeadCases.empty())
     return false;
 
   SwitchInstProfUpdateWrapper SIW(*SI);
   for (ConstantInt *DeadCase : DeadCases) {
if (!Dest->hasAddressTaken() || !Succs.insert(Dest).second) {
       --e;
       Changed = true;
     }
   }
 
   if (IBI->getNumDestinations() == 0) {
     // If the indirectbr has no successors, change it to unreachable.
     new UnreachableInst(IBI->getContext(), IBI);
-    EraseTerminatorAndDCECond(IBI);
+    EraseTerminatorAndDCECond(IBI, /*MSSAU*/ nullptr, Options.AC);
     return true;
   }
 
   if (IBI->getNumDestinations() == 1) {
     // If the indirectbr has one successor, change it to a direct branch.
     BranchInst::Create(IBI->getDestination(0), IBI);
-    EraseTerminatorAndDCECond(IBI);
+    EraseTerminatorAndDCECond(IBI, /*MSSAU*/ nullptr, Options.AC);
     return true;
   }
 
   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
     if (SimplifyIndirectBrOnSelect(IBI, SI))
       return requestResimplify();
   }
   return Changed;
if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) {
     if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB))
       return true;
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and our successor, fold the comparison into the
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
-  if (FoldBranchToCommonDest(BI, nullptr, Options.BonusInstThreshold))
+  if (FoldBranchToCommonDest(BI, nullptr, Options.BonusInstThreshold,
+                             Options.AC))
     return requestResimplify();
   return false;
 }
 
 static BasicBlock *allPredecessorsComeFromSameSource(BasicBlock *BB) {
   BasicBlock *PredPred = nullptr;
   for (auto *P : predecessors(BB)) {
     BasicBlock *PPred = P->getSinglePredecessor();
bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   // blocks' conditions imply BI's condition, we know the direction of BI.
   Optional<bool> Imp = isImpliedByDomCondition(BI->getCondition(), BI, DL);
   if (Imp) {
     // Turn this into a branch on constant.
     auto *OldCond = BI->getCondition();
     ConstantInt *TorF = *Imp ? ConstantInt::getTrue(BB->getContext())
                              : ConstantInt::getFalse(BB->getContext());
     BI->setCondition(TorF);
-    RecursivelyDeleteTriviallyDeadInstructions(OldCond);
+    RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr, nullptr,
+                                               Options.AC);
     return requestResimplify();
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
-  if (FoldBranchToCommonDest(BI, nullptr, Options.BonusInstThreshold))
+  if (FoldBranchToCommonDest(BI, nullptr, Options.BonusInstThreshold,
+                             Options.AC))
     return requestResimplify();
 
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {

llvm/test/Transforms/Attributor/ArgumentPromotion/byval-2-preservation.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=attributor --enable-knowledge-retention -aa-pipeline='basic-aa' -attributor-max-iterations-verify -attributor-max-iterations=3 < %s | FileCheck %s
+
+%struct.ss = type { i32, i64 }
+
+define internal void @f(%struct.ss* byval  %b, i32* byval %X) nounwind  {
+entry:
+  %tmp = getelementptr %struct.ss, %struct.ss* %b, i32 0, i32 0
+  %tmp1 = load i32, i32* %tmp, align 4
+  %tmp2 = add i32 %tmp1, 1
+  store i32 %tmp2, i32* %tmp, align 4
+
+  store i32 0, i32* %X
+  ret void
+}
+
+define i32 @test(i32* %X) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[S:%.*]] = alloca [[STRUCT_SS:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr [[STRUCT_SS]], %struct.ss* [[S]], i32 0, i32 0
+; CHECK-NEXT:    store i32 1, i32* [[TMP1]], align 8
+; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr [[STRUCT_SS]], %struct.ss* [[S]], i32 0, i32 1
+; CHECK-NEXT:    store i64 2, i64* [[TMP4]], align 4
+; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "align"(i32* [[X:%.*]], i64 4), "align"(%struct.ss* [[S]], i64 8), "dereferenceable"(i32* [[X]], i64 4), "dereferenceable"(%struct.ss* [[S]], i64 12), "nonnull"(%struct.ss* [[S]]), "nonnull"(i32* [[X]]) ]
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %S = alloca %struct.ss
+  %tmp1 = getelementptr %struct.ss, %struct.ss* %S, i32 0, i32 0
+  store i32 1, i32* %tmp1, align 8
+  %tmp4 = getelementptr %struct.ss, %struct.ss* %S, i32 0, i32 1
+  store i64 2, i64* %tmp4, align 4
+  call void @f( %struct.ss* byval %S, i32* byval %X)
+  ret i32 0
+}

llvm/test/Transforms/InstSimplify/load.ll

-; NOTE: Assertions have been autogenerated by update_test_checks.py
-; RUN: opt < %s -instsimplify -S | FileCheck %s
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s  --check-prefixes=CHECK,NO_ASSUME
+; RUN: opt < %s -instsimplify --enable-knowledge-retention -S | FileCheck %s  --check-prefixes=CHECK,USE_ASSUME
 
 @zeroinit = constant {} zeroinitializer
 @undef = constant {} undef
 
 define i32 @crash_on_zeroinit() {
-; CHECK-LABEL: @crash_on_zeroinit(
-; CHECK:         ret i32 0
+; NO_ASSUME-LABEL: @crash_on_zeroinit(
+; NO_ASSUME-NEXT:    ret i32 0
+;
+; USE_ASSUME-LABEL: @crash_on_zeroinit(
+; USE_ASSUME-NEXT:    call void @llvm.assume(i1 true) [ "dereferenceable"(i32* bitcast ({}* @zeroinit to i32*), i64 4), "nonnull"(i32* bitcast ({}* @zeroinit to i32*)) ]
+; USE_ASSUME-NEXT:    ret i32 0
 ;
   %load = load i32, i32* bitcast ({}* @zeroinit to i32*)
   ret i32 %load
 }
 
 define i32 @crash_on_undef() {
-; CHECK-LABEL: @crash_on_undef(
-; CHECK:         ret i32 undef
+; NO_ASSUME-LABEL: @crash_on_undef(
+; NO_ASSUME-NEXT:    ret i32 undef
+;
+; USE_ASSUME-LABEL: @crash_on_undef(
+; USE_ASSUME-NEXT:    call void @llvm.assume(i1 true) [ "dereferenceable"(i32* bitcast ({}* @undef to i32*), i64 4), "nonnull"(i32* bitcast ({}* @undef to i32*)) ]
+; USE_ASSUME-NEXT:    ret i32 undef
 ;
   %load = load i32, i32* bitcast ({}* @undef to i32*)
   ret i32 %load
 }
 
 @GV = private constant [8 x i32] [i32 42, i32 43, i32 44, i32 45, i32 46, i32 47, i32 48, i32 49]
 
 define <8 x i32> @partial_load() {
-; CHECK-LABEL: @partial_load(
-; CHECK:         ret <8 x i32> <i32 0, i32 42, i32 43, i32 44, i32 45, i32 46, i32 47, i32 48>
+; NO_ASSUME-LABEL: @partial_load(
+; NO_ASSUME-NEXT:    ret <8 x i32> <i32 0, i32 42, i32 43, i32 44, i32 45, i32 46, i32 47, i32 48>
+;
+; USE_ASSUME-LABEL: @partial_load(
+; USE_ASSUME-NEXT:    call void @llvm.assume(i1 true) [ "dereferenceable"(<8 x i32>* bitcast (i32* getelementptr ([8 x i32], [8 x i32]* @GV, i64 0, i64 -1) to <8 x i32>*), i64 32), "nonnull"(<8 x i32>* bitcast (i32* getelementptr ([8 x i32], [8 x i32]* @GV, i64 0, i64 -1) to <8 x i32>*)) ]
+; USE_ASSUME-NEXT:    ret <8 x i32> <i32 0, i32 42, i32 43, i32 44, i32 45, i32 46, i32 47, i32 48>
+;
   %load = load <8 x i32>, <8 x i32>* bitcast (i32* getelementptr ([8 x i32], [8 x i32]* @GV, i64 0, i64 -1) to <8 x i32>*)
   ret <8 x i32> %load
 }
 
 @constvec = internal constant <3 x float> <float 0xBFDA20BC40000000, float 0xBFE6A09EE0000000, float 0x3FE279A760000000>
 
 ; This does an out of bounds load from the global constant
 define <3 x float> @load_vec3() {
-; CHECK-LABEL: @load_vec3(
-; CHECK-NEXT:    ret <3 x float> undef
+; NO_ASSUME-LABEL: @load_vec3(
+; NO_ASSUME-NEXT:    ret <3 x float> undef
+;
+; USE_ASSUME-LABEL: @load_vec3(
+; USE_ASSUME-NEXT:    call void @llvm.assume(i1 true) [ "dereferenceable"(<3 x float>* getelementptr inbounds (<3 x float>, <3 x float>* @constvec, i64 1), i64 12), "nonnull"(<3 x float>* getelementptr inbounds (<3 x float>, <3 x float>* @constvec, i64 1)) ]
+; USE_ASSUME-NEXT:    ret <3 x float> undef
+;
   %1 = load <3 x float>, <3 x float>* getelementptr inbounds (<3 x float>, <3 x float>* @constvec, i64 1)
   ret <3 x float> %1
 }

llvm/unittests/Transforms/Utils/LocalTest.cpp

 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 TEST(Local, RecursivelyDeleteDeadPHINodes) {
   LLVMContext C;
+  auto M = std::make_unique<Module>("test", C);
 
   IRBuilder<> builder(C);
 
+  Function *F = Function::Create(FunctionType::get(Type::getVoidTy(C), false),
+                                 GlobalValue::ExternalLinkage, "", &*M);
+
   // Make blocks
   BasicBlock *bb0 = BasicBlock::Create(C);
   BasicBlock *bb1 = BasicBlock::Create(C);
+  bb0->insertInto(F);
+  bb1->insertInto(F);
 
   builder.SetInsertPoint(bb0);
   PHINode    *phi = builder.CreatePHI(Type::getInt32Ty(C), 2);
   BranchInst *br0 = builder.CreateCondBr(builder.getTrue(), bb0, bb1);
 
   builder.SetInsertPoint(bb1);
   BranchInst *br1 = builder.CreateBr(bb0);
 
TEST(Local, RecursivelyDeleteDeadPHINodes) {
 
   EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
 
   builder.SetInsertPoint(bb0);
   phi = builder.CreatePHI(Type::getInt32Ty(C), 0);
   builder.CreateAdd(phi, phi);
 
   EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi));
-
-  bb0->dropAllReferences();
-  bb1->dropAllReferences();
-  delete bb0;
-  delete bb1;
 }
 
 TEST(Local, RemoveDuplicatePHINodes) {
   LLVMContext C;
   IRBuilder<> B(C);
 
   std::unique_ptr<Function> F(
       Function::Create(FunctionType::get(B.getVoidTy(), false),