[AssumeBundles] Adapt RecursivelyDeleteTriviallyDeadInstructions and depending passes.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

7990

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

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

210

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

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

221

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

8080

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

878

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

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

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

thanks for the heads up.

37

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

8080

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

 //===- Local.h - Functions to perform local transformations -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 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

 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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> 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);
+    for (Instruction *I : DeadInsts) {
+      AssumptionCache *AC =
+          InfoCache.AG.getAnalysis<AssumptionAnalysis>(*I->getFunction());
+      RecursivelyDeleteTriviallyDeadInstructions(I, 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);
       }
       // Actually we do not delete the blocks but squash them into a single

llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp

 //===- InstSimplifyPass.cpp -----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
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

 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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

 //===- NaryReassociate.cpp - Reassociate n-ary expressions ----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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/AssumeBundleBuilder.cpp

 //===- AssumeBundleBuilder.cpp - tools to preserve informations -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
void addAttribute(Attribute Attr, Value *WasOn) {
     AssumedKnowledgeSet.insert(
         {Name.data(), AttrArg, {WasOn, AssumedKnowledge::None}});
   }
 
   void addCall(const CallBase *Call) {
     auto addAttrList = [&](AttributeList AttrList) {
       for (unsigned Idx = AttributeList::FirstArgIndex;
            Idx < AttrList.getNumAttrSets(); Idx++)
-        for (Attribute Attr : AttrList.getAttributes(Idx))
+        for (Attribute Attr : AttrList.getAttributes(Idx)) {
+          if (!Call->getArgOperand(Idx - 1))
+            continue;
           addAttribute(Attr, Call->getArgOperand(Idx - 1));
+        }
       for (Attribute Attr : AttrList.getFnAttributes())
         addAttribute(Attr, nullptr);
     };
     addAttrList(Call->getAttributes());
     if (Function *Fn = Call->getCalledFunction())
       addAttrList(Fn->getAttributes());
   }
 
if (DerefSize != 0) {
       if (!NullPointerIsDefined(MemInst->getFunction(),
                                 Pointer->getType()->getPointerAddressSpace()))
         addAttr(Attribute::NonNull, Pointer);
     }
     if (MA.valueOrOne() > 1)
       addAttr(Attribute::Alignment, Pointer, MA.valueOrOne().value());
   }
 
+  bool instructionHasNullOperand(Instruction *I) {
+    for (Value *V : I->operand_values())
+      if (!V)
+        return true;
+    return false;
+  }
+
   void addInstruction(Instruction *I) {
     if (auto *Call = dyn_cast<CallBase>(I))
       return addCall(Call);
+    if (instructionHasNullOperand(I))
+      return;
     if (auto *Load = dyn_cast<LoadInst>(I))
       return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(),
                             Load->getAlign());
     if (auto *Store = dyn_cast<StoreInst>(I))
       return addAccessedPtr(I, Store->getPointerOperand(),
                             Store->getValueOperand()->getType(),
                             Store->getAlign());
     // TODO: Add support for the other Instructions.

llvm/lib/Transforms/Utils/Local.cpp

 //===- Local.cpp - Functions to perform local transformations -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #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

 //===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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

 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
class SimplifyCFGOpt {
   bool simplifyCommonResume(ResumeInst *RI);
   bool simplifyCleanupReturn(CleanupReturnInst *RI);
   bool simplifyUnreachable(UnreachableInst *UI);
   bool simplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
   bool simplifyIndirectBr(IndirectBrInst *IBI);
   bool simplifyBranch(BranchInst *Branch, IRBuilder<> &Builder);
   bool simplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
   bool simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
+  bool SimplifyCondBranchToTwoReturns(BranchInst *BI, IRBuilder<> &Builder);
 
   bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
                                              IRBuilder<> &Builder);
 
+  bool HoistThenElseCodeToIf(BranchInst *BI, const TargetTransformInfo &TTI);
+  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);
   bool simplifyOnce(BasicBlock *BB);
while (!DFT.empty()) {
       }
       // Failed to parse a proper sequence, abort now
       CompValue = nullptr;
       break;
     }
   }
 };
 
-} // end anonymous namespace
-
-static void EraseTerminatorAndDCECond(Instruction *TI,
-                                      MemorySSAUpdater *MSSAU = nullptr) {
+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, 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, 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.
 struct ConstantIntOrdering {
   bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const {
     return LHS->getValue().ult(RHS->getValue());
   }
 };
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, 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) {
static bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2,
   return true;
 }
 
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I);
 
 /// Given a conditional branch that goes to BB1 and BB2, hoist any common code
 /// in the two blocks up into the branch block. The caller of this function
 /// guarantees that BI's block dominates BB1 and BB2.
-static bool HoistThenElseCodeToIf(BranchInst *BI,
+bool SimplifyCFGOpt::HoistThenElseCodeToIf(BranchInst *BI,
                                            const TargetTransformInfo &TTI) {
   // This does very trivial matching, with limited scanning, to find identical
   // instructions in the two blocks.  In particular, we don't want to get into
   // O(M*N) situations here where M and N are the sizes of BB1 and BB2.  As
   // such, we currently just scan for obviously identical instructions in an
   // identical order.
   BasicBlock *BB1 = BI->getSuccessor(0); // The true destination.
   BasicBlock *BB2 = BI->getSuccessor(1); // The false destination
 
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, 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:

 ///   BB:
 ///     %cmp = icmp ult %x, %y
 ///     %sub = sub %x, %y
 ///     %cond = select i1 %cmp, 0, %sub
 ///     ...
 /// \endcode
 ///
 /// \returns true if the conditional block is removed.
-static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
+bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
                                             const TargetTransformInfo &TTI) {
   // Be conservative for now. FP select instruction can often be expensive.
   Value *BrCond = BI->getCondition();
   if (isa<FCmpInst>(BrCond))
     return false;
 
   BasicBlock *BB = BI->getParent();
   BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0);
 
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
   Builder.CreateBr(BB);
   OldTI->eraseFromParent();
   return true;
 }
 
 /// If we found a conditional branch that goes to two returning blocks,
 /// try to merge them together into one return,
 /// introducing a select if the return values disagree.
-static bool SimplifyCondBranchToTwoReturns(BranchInst *BI,
+bool SimplifyCFGOpt::SimplifyCondBranchToTwoReturns(BranchInst *BI,
                                                     IRBuilder<> &Builder) {
   assert(BI->isConditional() && "Must be a conditional branch");
   BasicBlock *TrueSucc = BI->getSuccessor(0);
   BasicBlock *FalseSucc = BI->getSuccessor(1);
   ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator());
   ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator());
 
   // Check to ensure both blocks are empty (just a return) or optionally empty
   // with PHI nodes.  If there are other instructions, merging would cause extra
   // computation on one path or the other.
   if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator())
     return false;
   if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator())
     return false;
 
   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, 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, 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) {
     if (!SuccHasWeights)
       SuccTrueWeight = SuccFalseWeight = 1;
     return true;
   } else {
     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) {
-  BasicBlock *BB = BI->getParent();
-
-  const unsigned PredCount = pred_size(BB);
-
-  Instruction *Cond = nullptr;
-  if (BI->isConditional())
-    Cond = dyn_cast<Instruction>(BI->getCondition());
-  else {
-    // For unconditional branch, check for a simple CFG pattern, where
-    // BB has a single predecessor and BB's successor is also its predecessor's
-    // successor. If such pattern exists, check for CSE between BB and its
-    // predecessor.
-    if (BasicBlock *PB = BB->getSinglePredecessor())
-      if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
-        if (PBI->isConditional() &&
-            (BI->getSuccessor(0) == PBI->getSuccessor(0) ||
-             BI->getSuccessor(0) == PBI->getSuccessor(1))) {
-          for (auto I = BB->instructionsWithoutDebug().begin(),
-                    E = BB->instructionsWithoutDebug().end();
-               I != E;) {
-            Instruction *Curr = &*I++;
-            if (isa<CmpInst>(Curr)) {
-              Cond = Curr;
-              break;
-            }
-            // Quit if we can't remove this instruction.
-            if (!tryCSEWithPredecessor(Curr, PB))
-              return false;
-          }
-        }
-
-    if (!Cond)
-      return false;
-  }
-
-  if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
-      Cond->getParent() != BB || !Cond->hasOneUse())
-    return false;
-
-  // Make sure the instruction after the condition is the cond branch.
-  BasicBlock::iterator CondIt = ++Cond->getIterator();
-
-  // Ignore dbg intrinsics.
-  while (isa<DbgInfoIntrinsic>(CondIt))
-    ++CondIt;
-
-  if (&*CondIt != BI)
-    return false;
-
-  // Only allow this transformation if computing the condition doesn't involve
-  // too many instructions and these involved instructions can be executed
-  // unconditionally. We denote all involved instructions except the condition
-  // as "bonus instructions", and only allow this transformation when the
-  // number of the bonus instructions we'll need to create when cloning into
-  // each predecessor does not exceed a certain threshold.
-  unsigned NumBonusInsts = 0;
-  for (auto I = BB->begin(); Cond != &*I; ++I) {
-    // Ignore dbg intrinsics.
-    if (isa<DbgInfoIntrinsic>(I))
-      continue;
-    if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(&*I))
-      return false;
-    // I has only one use and can be executed unconditionally.
-    Instruction *User = dyn_cast<Instruction>(I->user_back());
-    if (User == nullptr || User->getParent() != BB)
-      return false;
-    // I is used in the same BB. Since BI uses Cond and doesn't have more slots
-    // to use any other instruction, User must be an instruction between next(I)
-    // and Cond.
-
-    // Account for the cost of duplicating this instruction into each
-    // predecessor.
-    NumBonusInsts += PredCount;
-    // Early exits once we reach the limit.
-    if (NumBonusInsts > BonusInstThreshold)
-      return false;
-  }
-
-  // Cond is known to be a compare or binary operator.  Check to make sure that
-  // neither operand is a potentially-trapping constant expression.
-  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
-    if (CE->canTrap())
-      return false;
-  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
-    if (CE->canTrap())
-      return false;
-
-  // Finally, don't infinitely unroll conditional loops.
-  BasicBlock *TrueDest = BI->getSuccessor(0);
-  BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr;
-  if (TrueDest == BB || FalseDest == BB)
-    return false;
-
-  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
-    BasicBlock *PredBlock = *PI;
-    BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
-
-    // Check that we have two conditional branches.  If there is a PHI node in
-    // the common successor, verify that the same value flows in from both
-    // blocks.
-    SmallVector<PHINode *, 4> PHIs;
-    if (!PBI || PBI->isUnconditional() ||
-        (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) ||
-        (!BI->isConditional() &&
-         !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
-      continue;
-
-    // Determine if the two branches share a common destination.
-    Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd;
-    bool InvertPredCond = false;
-
-    if (BI->isConditional()) {
-      if (PBI->getSuccessor(0) == TrueDest) {
-        Opc = Instruction::Or;
-      } else if (PBI->getSuccessor(1) == FalseDest) {
-        Opc = Instruction::And;
-      } else if (PBI->getSuccessor(0) == FalseDest) {
-        Opc = Instruction::And;
-        InvertPredCond = true;
-      } else if (PBI->getSuccessor(1) == TrueDest) {
-        Opc = Instruction::Or;
-        InvertPredCond = true;
-      } else {
-        continue;
-      }
-    } else {
-      if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
-        continue;
-    }
-
-    LLVM_DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
-    IRBuilder<> Builder(PBI);
-
-    // If we need to invert the condition in the pred block to match, do so now.
-    if (InvertPredCond) {
-      Value *NewCond = PBI->getCondition();
-
-      if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
-        CmpInst *CI = cast<CmpInst>(NewCond);
-        CI->setPredicate(CI->getInversePredicate());
-      } else {
-        NewCond =
-            Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not");
-      }
-
-      PBI->setCondition(NewCond);
-      PBI->swapSuccessors();
-    }
-
-    // If we have bonus instructions, clone them into the predecessor block.
-    // Note that there may be multiple predecessor blocks, so we cannot move
-    // bonus instructions to a predecessor block.
-    ValueToValueMapTy VMap; // maps original values to cloned values
-    // We already make sure Cond is the last instruction before BI. Therefore,
-    // all instructions before Cond other than DbgInfoIntrinsic are bonus
-    // instructions.
-    for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) {
-      if (isa<DbgInfoIntrinsic>(BonusInst))
-        continue;
-      Instruction *NewBonusInst = BonusInst->clone();
-      RemapInstruction(NewBonusInst, VMap,
-                       RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
-      VMap[&*BonusInst] = NewBonusInst;
-
-      // If we moved a load, we cannot any longer claim any knowledge about
-      // its potential value. The previous information might have been valid
-      // only given the branch precondition.
-      // For an analogous reason, we must also drop all the metadata whose
-      // semantics we don't understand.
-      NewBonusInst->dropUnknownNonDebugMetadata();
-
-      PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst);
-      NewBonusInst->takeName(&*BonusInst);
-      BonusInst->setName(BonusInst->getName() + ".old");
-    }
-
-    // Clone Cond into the predecessor basic block, and or/and the
-    // two conditions together.
-    Instruction *CondInPred = Cond->clone();
-    RemapInstruction(CondInPred, VMap,
-                     RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
-    PredBlock->getInstList().insert(PBI->getIterator(), CondInPred);
-    CondInPred->takeName(Cond);
-    Cond->setName(CondInPred->getName() + ".old");
-
-    if (BI->isConditional()) {
-      Instruction *NewCond = cast<Instruction>(
-          Builder.CreateBinOp(Opc, PBI->getCondition(), CondInPred, "or.cond"));
-      PBI->setCondition(NewCond);
-
-      uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
-      bool HasWeights =
-          extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight,
-                                 SuccTrueWeight, SuccFalseWeight);
-      SmallVector<uint64_t, 8> NewWeights;
-
-      if (PBI->getSuccessor(0) == BB) {
-        if (HasWeights) {
-          // PBI: br i1 %x, BB, FalseDest
-          // BI:  br i1 %y, TrueDest, FalseDest
-          // TrueWeight is TrueWeight for PBI * TrueWeight for BI.
-          NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
-          // FalseWeight is FalseWeight for PBI * TotalWeight for BI +
-          //               TrueWeight for PBI * FalseWeight for BI.
-          // We assume that total weights of a BranchInst can fit into 32 bits.
-          // Therefore, we will not have overflow using 64-bit arithmetic.
-          NewWeights.push_back(PredFalseWeight *
-                                   (SuccFalseWeight + SuccTrueWeight) +
-                               PredTrueWeight * SuccFalseWeight);
-        }
-        AddPredecessorToBlock(TrueDest, PredBlock, BB, MSSAU);
-        PBI->setSuccessor(0, TrueDest);
-      }
-      if (PBI->getSuccessor(1) == BB) {
-        if (HasWeights) {
-          // PBI: br i1 %x, TrueDest, BB
-          // BI:  br i1 %y, TrueDest, FalseDest
-          // TrueWeight is TrueWeight for PBI * TotalWeight for BI +
-          //              FalseWeight for PBI * TrueWeight for BI.
-          NewWeights.push_back(PredTrueWeight *
-                                   (SuccFalseWeight + SuccTrueWeight) +
-                               PredFalseWeight * SuccTrueWeight);
-          // FalseWeight is FalseWeight for PBI * FalseWeight for BI.
-          NewWeights.push_back(PredFalseWeight * SuccFalseWeight);
-        }
-        AddPredecessorToBlock(FalseDest, PredBlock, BB, MSSAU);
-        PBI->setSuccessor(1, FalseDest);
-      }
-      if (NewWeights.size() == 2) {
-        // Halve the weights if any of them cannot fit in an uint32_t
-        FitWeights(NewWeights);
-
-        SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),
-                                           NewWeights.end());
-        setBranchWeights(PBI, MDWeights[0], MDWeights[1]);
-      } else
-        PBI->setMetadata(LLVMContext::MD_prof, nullptr);
-    } else {
-      // Update PHI nodes in the common successors.
-      for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
-        ConstantInt *PBI_C = cast<ConstantInt>(
-            PHIs[i]->getIncomingValueForBlock(PBI->getParent()));
-        assert(PBI_C->getType()->isIntegerTy(1));
-        Instruction *MergedCond = nullptr;
-        if (PBI->getSuccessor(0) == TrueDest) {
-          // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value)
-          // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value)
-          //       is false: !PBI_Cond and BI_Value
-          Instruction *NotCond = cast<Instruction>(
-              Builder.CreateNot(PBI->getCondition(), "not.cond"));
-          MergedCond = cast<Instruction>(
-               Builder.CreateBinOp(Instruction::And, NotCond, CondInPred,
-                                   "and.cond"));
-          if (PBI_C->isOne())
-            MergedCond = cast<Instruction>(Builder.CreateBinOp(
-                Instruction::Or, PBI->getCondition(), MergedCond, "or.cond"));
-        } else {
-          // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C)
-          // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond)
-          //       is false: PBI_Cond and BI_Value
-          MergedCond = cast<Instruction>(Builder.CreateBinOp(
-              Instruction::And, PBI->getCondition(), CondInPred, "and.cond"));
-          if (PBI_C->isOne()) {
-            Instruction *NotCond = cast<Instruction>(
-                Builder.CreateNot(PBI->getCondition(), "not.cond"));
-            MergedCond = cast<Instruction>(Builder.CreateBinOp(
-                Instruction::Or, NotCond, MergedCond, "or.cond"));
-          }
-        }
-        // Update PHI Node.
-  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);
-      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);
-
-    // TODO: If BB is reachable from all paths through PredBlock, then we
-    // could replace PBI's branch probabilities with BI's.
-
-    // Copy any debug value intrinsics into the end of PredBlock.
-    for (Instruction &I : *BB)
-      if (isa<DbgInfoIntrinsic>(I))
-        I.clone()->insertBefore(PBI);
-
-    return true;
-  }
-  return false;
-}
-
 // If there is only one store in BB1 and BB2, return it, otherwise return
 // nullptr.
 static StoreInst *findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2) {
   StoreInst *S = nullptr;
   for (auto *BB : {BB1, BB2}) {
     if (!BB)
       continue;
     for (auto &I : *BB)
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())
static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
   return true;
 }
 
 // Simplifies a terminator by replacing it with a branch to TrueBB if Cond is
 // true or to FalseBB if Cond is false.
 // Takes care of updating the successors and removing the old terminator.
 // Also makes sure not to introduce new successors by assuming that edges to
 // non-successor TrueBBs and FalseBBs aren't reachable.
-static bool SimplifyTerminatorOnSelect(Instruction *OldTerm, Value *Cond,
-                                       BasicBlock *TrueBB, BasicBlock *FalseBB,
+bool SimplifyCFGOpt::SimplifyTerminatorOnSelect(Instruction *OldTerm,
+                                                Value *Cond, BasicBlock *TrueBB,
+                                                BasicBlock *FalseBB,
                                                 uint32_t TrueWeight,
                                                 uint32_t FalseWeight) {
   // Remove any superfluous successor edges from the CFG.
   // First, figure out which successors to preserve.
   // If TrueBB and FalseBB are equal, only try to preserve one copy of that
   // successor.
   BasicBlock *KeepEdge1 = TrueBB;
   BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
 
   // Then remove the rest.
if (!KeepEdge1 && !KeepEdge2) {
     if (!KeepEdge1)
       // Only TrueBB was found.
       Builder.CreateBr(TrueBB);
     else
       // Only FalseBB was found.
       Builder.CreateBr(FalseBB);
   }
 
-  EraseTerminatorAndDCECond(OldTerm);
+  EraseTerminatorAndDCECond(OldTerm, 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.
-static bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) {
+bool SimplifyCFGOpt::SimplifySwitchOnSelect(SwitchInst *SI,
+                                            SelectInst *Select) {
   // Check for constant integer values in the select.
   ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue());
   ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue());
   if (!TrueVal || !FalseVal)
     return false;
 
   // Find the relevant condition and destinations.
   Value *Condition = Select->getCondition();
return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, TrueWeight,
                                     FalseWeight);
 }
 
 // Replaces
 //   (indirectbr (select cond, blockaddress(@fn, BlockA),
 //                             blockaddress(@fn, BlockB)))
 // with
 //   (br cond, BlockA, BlockB).
-static bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) {
+bool SimplifyCFGOpt::SimplifyIndirectBrOnSelect(IndirectBrInst *IBI,
+                                                SelectInst *SI) {
   // Check that both operands of the select are block addresses.
   BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue());
   BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue());
   if (!TBA || !FBA)
     return false;
 
   // Extract the actual blocks.
   BasicBlock *TrueBB = TBA->getBasicBlock();
bool SimplifyCFGOpt::tryToSimplifyUncondBranchWithICmpInIt(
   Builder.CreateBr(SuccBlock);
   PHIUse->addIncoming(NewCst, NewBB);
   return true;
 }
 
 /// The specified branch is a conditional branch.
 /// Check to see if it is branching on an or/and chain of icmp instructions, and
 /// fold it into a switch instruction if so.
-static bool SimplifyBranchOnICmpChain(BranchInst *BI, IRBuilder<> &Builder,
+bool SimplifyCFGOpt::SimplifyBranchOnICmpChain(BranchInst *BI,
+                                               IRBuilder<> &Builder,
                                                const DataLayout &DL) {
   Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
   if (!Cond)
     return false;
 
   // Change br (X == 0 | X == 1), T, F into a switch instruction.
   // If this is a bunch of seteq's or'd together, or if it's a bunch of
   // 'setne's and'ed together, collect them.
 
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, 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, 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, nullptr, AC);
 }
 
 /// Turn a switch with two reachable destinations into an integer range
 /// comparison and branch.
-static bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) {
+bool SimplifyCFGOpt::TurnSwitchRangeIntoICmp(SwitchInst *SI,
+                                             IRBuilder<> &Builder) {
   assert(SI->getNumCases() > 1 && "Degenerate switch?");
 
   bool HasDefault =
       !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
 
   // Partition the cases into two sets with different destinations.
   BasicBlock *DestA = HasDefault ? SI->getDefaultDest() : nullptr;
   BasicBlock *DestB = nullptr;
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, 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, nullptr, Options.AC);
     return true;
   }
 
   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
     if (SimplifyIndirectBrOnSelect(IBI, SI))
       return requestResimplify();
   }
   return Changed;
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))
     return requestResimplify();
do {
     // Perform one round of simplifcation. Resimplify flag will be set if
     // another iteration is requested.
     Changed |= simplifyOnce(BB);
   } while (Resimplify);
 
   return Changed;
 }
 
+/// 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,
+                                  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 {
+    // For unconditional branch, check for a simple CFG pattern, where
+    // BB has a single predecessor and BB's successor is also its predecessor's
+    // successor. If such pattern exists, check for CSE between BB and its
+    // predecessor.
+    if (BasicBlock *PB = BB->getSinglePredecessor())
+      if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator()))
+        if (PBI->isConditional() &&
+            (BI->getSuccessor(0) == PBI->getSuccessor(0) ||
+             BI->getSuccessor(0) == PBI->getSuccessor(1))) {
+          for (auto I = BB->instructionsWithoutDebug().begin(),
+                    E = BB->instructionsWithoutDebug().end();
+               I != E;) {
+            Instruction *Curr = &*I++;
+            if (isa<CmpInst>(Curr)) {
+              Cond = Curr;
+              break;
+            }
+            // Quit if we can't remove this instruction.
+            if (!tryCSEWithPredecessor(Curr, PB))
+              return false;
+          }
+        }
+
+    if (!Cond)
+      return false;
+  }
+
+  if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
+      Cond->getParent() != BB || !Cond->hasOneUse())
+    return false;
+
+  // Make sure the instruction after the condition is the cond branch.
+  BasicBlock::iterator CondIt = ++Cond->getIterator();
+
+  // Ignore dbg intrinsics.
+  while (isa<DbgInfoIntrinsic>(CondIt))
+    ++CondIt;
+
+  if (&*CondIt != BI)
+    return false;
+
+  // Only allow this transformation if computing the condition doesn't involve
+  // too many instructions and these involved instructions can be executed
+  // unconditionally. We denote all involved instructions except the condition
+  // as "bonus instructions", and only allow this transformation when the
+  // number of the bonus instructions we'll need to create when cloning into
+  // each predecessor does not exceed a certain threshold.
+  unsigned NumBonusInsts = 0;
+  for (auto I = BB->begin(); Cond != &*I; ++I) {
+    // Ignore dbg intrinsics.
+    if (isa<DbgInfoIntrinsic>(I))
+      continue;
+    if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(&*I))
+      return false;
+    // I has only one use and can be executed unconditionally.
+    Instruction *User = dyn_cast<Instruction>(I->user_back());
+    if (User == nullptr || User->getParent() != BB)
+      return false;
+    // I is used in the same BB. Since BI uses Cond and doesn't have more slots
+    // to use any other instruction, User must be an instruction between next(I)
+    // and Cond.
+
+    // Account for the cost of duplicating this instruction into each
+    // predecessor.
+    NumBonusInsts += PredCount;
+    // Early exits once we reach the limit.
+    if (NumBonusInsts > BonusInstThreshold)
+      return false;
+  }
+
+  // Cond is known to be a compare or binary operator.  Check to make sure that
+  // neither operand is a potentially-trapping constant expression.
+  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
+    if (CE->canTrap())
+      return false;
+  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
+    if (CE->canTrap())
+      return false;
+
+  // Finally, don't infinitely unroll conditional loops.
+  BasicBlock *TrueDest = BI->getSuccessor(0);
+  BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr;
+  if (TrueDest == BB || FalseDest == BB)
+    return false;
+
+  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+    BasicBlock *PredBlock = *PI;
+    BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
+
+    // Check that we have two conditional branches.  If there is a PHI node in
+    // the common successor, verify that the same value flows in from both
+    // blocks.
+    SmallVector<PHINode *, 4> PHIs;
+    if (!PBI || PBI->isUnconditional() ||
+        (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) ||
+        (!BI->isConditional() &&
+         !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
+      continue;
+
+    // Determine if the two branches share a common destination.
+    Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd;
+    bool InvertPredCond = false;
+
+    if (BI->isConditional()) {
+      if (PBI->getSuccessor(0) == TrueDest) {
+        Opc = Instruction::Or;
+      } else if (PBI->getSuccessor(1) == FalseDest) {
+        Opc = Instruction::And;
+      } else if (PBI->getSuccessor(0) == FalseDest) {
+        Opc = Instruction::And;
+        InvertPredCond = true;
+      } else if (PBI->getSuccessor(1) == TrueDest) {
+        Opc = Instruction::Or;
+        InvertPredCond = true;
+      } else {
+        continue;
+      }
+    } else {
+      if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
+        continue;
+    }
+
+    LLVM_DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
+    IRBuilder<> Builder(PBI);
+
+    // If we need to invert the condition in the pred block to match, do so now.
+    if (InvertPredCond) {
+      Value *NewCond = PBI->getCondition();
+
+      if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {
+        CmpInst *CI = cast<CmpInst>(NewCond);
+        CI->setPredicate(CI->getInversePredicate());
+      } else {
+        NewCond =
+            Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not");
+      }
+
+      PBI->setCondition(NewCond);
+      PBI->swapSuccessors();
+    }
+
+    // If we have bonus instructions, clone them into the predecessor block.
+    // Note that there may be multiple predecessor blocks, so we cannot move
+    // bonus instructions to a predecessor block.
+    ValueToValueMapTy VMap; // maps original values to cloned values
+    // We already make sure Cond is the last instruction before BI. Therefore,
+    // all instructions before Cond other than DbgInfoIntrinsic are bonus
+    // instructions.
+    for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) {
+      if (isa<DbgInfoIntrinsic>(BonusInst))
+        continue;
+      Instruction *NewBonusInst = BonusInst->clone();
+      RemapInstruction(NewBonusInst, VMap,
+                       RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
+      VMap[&*BonusInst] = NewBonusInst;
+
+      // If we moved a load, we cannot any longer claim any knowledge about
+      // its potential value. The previous information might have been valid
+      // only given the branch precondition.
+      // For an analogous reason, we must also drop all the metadata whose
+      // semantics we don't understand.
+      NewBonusInst->dropUnknownNonDebugMetadata();
+
+      PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst);
+      NewBonusInst->takeName(&*BonusInst);
+      BonusInst->setName(BonusInst->getName() + ".old");
+    }
+
+    // Clone Cond into the predecessor basic block, and or/and the
+    // two conditions together.
+    Instruction *CondInPred = Cond->clone();
+    RemapInstruction(CondInPred, VMap,
+                     RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
+    PredBlock->getInstList().insert(PBI->getIterator(), CondInPred);
+    CondInPred->takeName(Cond);
+    Cond->setName(CondInPred->getName() + ".old");
+
+    if (BI->isConditional()) {
+      Instruction *NewCond = cast<Instruction>(
+          Builder.CreateBinOp(Opc, PBI->getCondition(), CondInPred, "or.cond"));
+      PBI->setCondition(NewCond);
+
+      uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
+      bool HasWeights =
+          extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight,
+                                 SuccTrueWeight, SuccFalseWeight);
+      SmallVector<uint64_t, 8> NewWeights;
+
+      if (PBI->getSuccessor(0) == BB) {
+        if (HasWeights) {
+          // PBI: br i1 %x, BB, FalseDest
+          // BI:  br i1 %y, TrueDest, FalseDest
+          // TrueWeight is TrueWeight for PBI * TrueWeight for BI.
+          NewWeights.push_back(PredTrueWeight * SuccTrueWeight);
+          // FalseWeight is FalseWeight for PBI * TotalWeight for BI +
+          //               TrueWeight for PBI * FalseWeight for BI.
+          // We assume that total weights of a BranchInst can fit into 32 bits.
+          // Therefore, we will not have overflow using 64-bit arithmetic.
+          NewWeights.push_back(PredFalseWeight *
+                                   (SuccFalseWeight + SuccTrueWeight) +
+                               PredTrueWeight * SuccFalseWeight);
+        }
+        AddPredecessorToBlock(TrueDest, PredBlock, BB, MSSAU);
+        PBI->setSuccessor(0, TrueDest);
+      }
+      if (PBI->getSuccessor(1) == BB) {
+        if (HasWeights) {
+          // PBI: br i1 %x, TrueDest, BB
+          // BI:  br i1 %y, TrueDest, FalseDest
+          // TrueWeight is TrueWeight for PBI * TotalWeight for BI +
+          //              FalseWeight for PBI * TrueWeight for BI.
+          NewWeights.push_back(PredTrueWeight *
+                                   (SuccFalseWeight + SuccTrueWeight) +
+                               PredFalseWeight * SuccTrueWeight);
+          // FalseWeight is FalseWeight for PBI * FalseWeight for BI.
+          NewWeights.push_back(PredFalseWeight * SuccFalseWeight);
+        }
+        AddPredecessorToBlock(FalseDest, PredBlock, BB, MSSAU);
+        PBI->setSuccessor(1, FalseDest);
+      }
+      if (NewWeights.size() == 2) {
+        // Halve the weights if any of them cannot fit in an uint32_t
+        FitWeights(NewWeights);
+
+        SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),
+                                           NewWeights.end());
+        setBranchWeights(PBI, MDWeights[0], MDWeights[1]);
+      } else
+        PBI->setMetadata(LLVMContext::MD_prof, nullptr);
+    } else {
+      // Update PHI nodes in the common successors.
+      for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
+        ConstantInt *PBI_C = cast<ConstantInt>(
+            PHIs[i]->getIncomingValueForBlock(PBI->getParent()));
+        assert(PBI_C->getType()->isIntegerTy(1));
+        Instruction *MergedCond = nullptr;
+        if (PBI->getSuccessor(0) == TrueDest) {
+          // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value)
+          // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value)
+          //       is false: !PBI_Cond and BI_Value
+          Instruction *NotCond = cast<Instruction>(
+              Builder.CreateNot(PBI->getCondition(), "not.cond"));
+          MergedCond = cast<Instruction>(Builder.CreateBinOp(
+              Instruction::And, NotCond, CondInPred, "and.cond"));
+          if (PBI_C->isOne())
+            MergedCond = cast<Instruction>(Builder.CreateBinOp(
+                Instruction::Or, PBI->getCondition(), MergedCond, "or.cond"));
+        } else {
+          // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C)
+          // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond)
+          //       is false: PBI_Cond and BI_Value
+          MergedCond = cast<Instruction>(Builder.CreateBinOp(
+              Instruction::And, PBI->getCondition(), CondInPred, "and.cond"));
+          if (PBI_C->isOne()) {
+            Instruction *NotCond = cast<Instruction>(
+                Builder.CreateNot(PBI->getCondition(), "not.cond"));
+            MergedCond = cast<Instruction>(Builder.CreateBinOp(
+                Instruction::Or, NotCond, MergedCond, "or.cond"));
+          }
+        }
+        // Update PHI Node.
+        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, 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);
+
+    // TODO: If BB is reachable from all paths through PredBlock, then we
+    // could replace PBI's branch probabilities with BI's.
+
+    // Copy any debug value intrinsics into the end of PredBlock.
+    for (Instruction &I : *BB)
+      if (isa<DbgInfoIntrinsic>(I))
+        I.clone()->insertBefore(PBI);
+
+    return true;
+  }
+  return false;
+}
+
 bool llvm::simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
                        const SimplifyCFGOptions &Options,
                        SmallPtrSetImpl<BasicBlock *> *LoopHeaders) {
   return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), LoopHeaders,
                         Options)
       .run(BB);
 }

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 < %s | FileCheck %s --check-prefixes=CHECK,NO_ASSUME
+; RUN: opt -S -passes=attributor --enable-knowledge-retention -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 < %s | FileCheck %s --check-prefixes=CHECK,USE_ASSUME
 
 %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: define {{[^@]+}}@test
-; CHECK-SAME: (i32* nocapture nofree readonly align 4 [[X:%.*]])
-; 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:    ret i32 0
+; NO_ASSUME-LABEL: define {{[^@]+}}@test
+; NO_ASSUME-SAME: (i32* nocapture nofree readonly align 4 [[X:%.*]])
+; NO_ASSUME-NEXT:  entry:
+; NO_ASSUME-NEXT:    [[S:%.*]] = alloca [[STRUCT_SS:%.*]]
+; NO_ASSUME-NEXT:    [[TMP1:%.*]] = getelementptr [[STRUCT_SS]], %struct.ss* [[S]], i32 0, i32 0
+; NO_ASSUME-NEXT:    store i32 1, i32* [[TMP1]], align 8
+; NO_ASSUME-NEXT:    [[TMP4:%.*]] = getelementptr [[STRUCT_SS]], %struct.ss* [[S]], i32 0, i32 1
+; NO_ASSUME-NEXT:    store i64 2, i64* [[TMP4]], align 4
+; NO_ASSUME-NEXT:    ret i32 0
+;
+; USE_ASSUME-LABEL: define {{[^@]+}}@test
+; USE_ASSUME-SAME: (i32* nocapture nofree readonly align 4 [[X:%.*]])
+; USE_ASSUME-NEXT:  entry:
+; USE_ASSUME-NEXT:    [[S:%.*]] = alloca [[STRUCT_SS:%.*]]
+; USE_ASSUME-NEXT:    [[TMP1:%.*]] = getelementptr [[STRUCT_SS]], %struct.ss* [[S]], i32 0, i32 0
+; USE_ASSUME-NEXT:    store i32 1, i32* [[TMP1]], align 8
+; USE_ASSUME-NEXT:    [[TMP4:%.*]] = getelementptr [[STRUCT_SS]], %struct.ss* [[S]], i32 0, i32 1
+; USE_ASSUME-NEXT:    store i64 2, i64* [[TMP4]], align 4
+; USE_ASSUME-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]]) ]
+; USE_ASSUME-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

 //===- Local.cpp - Unit tests for Local -----------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 #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),