Index: include/llvm/InitializePasses.h
===================================================================
--- include/llvm/InitializePasses.h
+++ include/llvm/InitializePasses.h
@@ -286,6 +286,7 @@
 void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializePostRAHazardRecognizerPass(PassRegistry&);
 void initializePostRASchedulerPass(PassRegistry&);
+void initializePredicateInfoPrinterLegacyPassPass(PassRegistry &);
 void initializePreISelIntrinsicLoweringLegacyPassPass(PassRegistry&);
 void initializePrintBasicBlockPassPass(PassRegistry&);
 void initializePrintFunctionPassWrapperPass(PassRegistry&);
Index: include/llvm/Transforms/Utils/PredicateInfo.h
===================================================================
--- /dev/null
+++ include/llvm/Transforms/Utils/PredicateInfo.h
@@ -0,0 +1,251 @@
+//===- PredicateInfo.h - Build PredicateInfo ----------------------*-C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// \file
+// \brief
+//
+// This file implements the PredicateInfo analysis, which creates an Extended
+// SSA form for operations used in branch comparisons and llvm.assume
+// comparisons.  Copies of these operations are inserted into the true/false
+// edge (and after assumes), and information attached to the copies.  All uses
+// of the original operation in blocks dominated by the true/false edge (and
+// assume), are replaced with uses of the copies.  This enables passes to easily
+// and sparsely propagate condition based info into the operations that may be
+// affected.
+//
+// Example:
+// %cmp = icmp eq i32 %x, 50
+// br i1 %cmp, label %true, label %false
+// true:
+// ret i32 %x
+// false:
+// ret i32 1
+//
+// will become
+//
+// %cmp = icmp eq i32, %x, 50
+// br i1 %cmp, label %true, label %false
+// true:
+// %x.0 = call @llvm.ssa_copy.i32(i32 %x)
+// ret i32 %x.0
+// false:
+// ret i32 1
+//
+// Using getPredicateInfoFor on x.0 will give you the comparison it is
+// dominated by (the icmp), and that you are located in the true edge of that
+// comparison, which tells you x.0 is 50.
+//
+// In order to reduce the number of copies inserted, predicateinfo is only
+// inserted where it would actually be live.  This means if there are no uses of
+// an operation dominated by the branch edges, or by an assume, the associated
+// predicate info is never inserted.
+//
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
+#define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/OperandTraits.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Pass.h"
+#include "llvm/PassAnalysisSupport.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <iterator>
+#include <memory>
+#include <utility>
+
+namespace llvm {
+
+class DominatorTree;
+class Function;
+class Instruction;
+class MemoryAccess;
+class LLVMContext;
+class raw_ostream;
+class OrderedBasicBlock;
+
+enum PredicateType { PT_Branch, PT_Assume };
+
+// Base class for all predicate information we provide.
+// All of our predicate information has at least a comparison.
+class PredicateBase : public ilist_node<PredicateBase> {
+public:
+  PredicateType Type;
+  Value *OriginalOp;
+  CmpInst *Comparison;
+  // The original operand before we renamed it.
+  // This can be use by passes, when destroying predicateinfo, to know
+  // whether they can just drop the intrinsic, or have to merge metadata.
+  PredicateBase(const PredicateBase &) = delete;
+  PredicateBase &operator=(const PredicateBase &) = delete;
+  PredicateBase() = delete;
+  static inline bool classof(const PredicateBase *) { return true; }
+
+protected:
+  PredicateBase(PredicateType PT, Value *Op, CmpInst *Comparison)
+      : Type(PT), OriginalOp(Op), Comparison(Comparison) {}
+};
+
+// Provides predicate information for assumes.  Since assumes are always true,
+// we simply provide the assume instruction, so you can tell your relative
+// position to it.
+class PredicateAssume : public PredicateBase {
+public:
+  IntrinsicInst *AssumeInst;
+  PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, CmpInst *Comparison)
+      : PredicateBase(PT_Assume, Op, Comparison), AssumeInst(AssumeInst) {}
+  PredicateAssume() = delete;
+  static inline bool classof(const PredicateAssume *) { return true; }
+  static inline bool classof(const PredicateBase *PB) {
+    return PB->Type == PT_Assume;
+  }
+};
+
+// Provides predicate information for branches.
+class PredicateBranch : public PredicateBase {
+public:
+  // This is the block that is conditional upon the comparison.
+  BasicBlock *BranchBB;
+  // This is one of the true/false successors of BranchBB.
+  BasicBlock *SplitBB;
+  // If true, SplitBB is the true successor, otherwise it's the false successor.
+  bool TrueEdge;
+  PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB,
+                  CmpInst *Comparison, bool TakenEdge)
+      : PredicateBase(PT_Branch, Op, Comparison), BranchBB(BranchBB),
+        SplitBB(SplitBB), TrueEdge(TakenEdge) {}
+  PredicateBranch() = delete;
+
+  static inline bool classof(const PredicateBranch *) { return true; }
+  static inline bool classof(const PredicateBase *PB) {
+    return PB->Type == PT_Branch;
+  }
+};
+
+// This name is used in a few places, so kick it into their own namespace
+namespace PredicateInfoClasses {
+struct ValueDFS;
+}
+
+/// \brief Encapsulates PredicateInfo, including all data associated with memory
+/// accesses.
+class PredicateInfo {
+private:
+  // Used to store information about each value we might rename.
+  struct ValueInfo {
+    // Information about each possible copy. During processing, this is each
+    // inserted info. After processing, we move the uninserted ones to the
+    // uninserted vector.
+    SmallVector<PredicateBase *, 4> Infos;
+    SmallVector<PredicateBase *, 4> UninsertedInfos;
+  };
+  // This owns the all the predicate infos in the function, placed or not.
+  iplist<PredicateBase> AllInfos;
+
+public:
+  PredicateInfo(Function &, DominatorTree &, AssumptionCache &);
+  ~PredicateInfo();
+
+  void verifyPredicateInfo() const;
+
+  void dump() const;
+  void print(raw_ostream &) const;
+
+  const PredicateBase *getPredicateInfoFor(const Value *V) const {
+    return PredicateMap.lookup(V);
+  }
+
+protected:
+  // Used by PredicateInfo annotater, dumpers, and wrapper pass.
+  friend class PredicateInfoAnnotatedWriter;
+  friend class PredicateInfoPrinterLegacyPass;
+
+private:
+  void buildPredicateInfo();
+  void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
+  void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
+  void renameUses(SmallPtrSetImpl<Value *> &);
+  using ValueDFS = PredicateInfoClasses::ValueDFS;
+  typedef SmallVectorImpl<ValueDFS> ValueDFSStack;
+  void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
+  Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);
+  bool stackIsInScope(const ValueDFSStack &, int DFSIn, int DFSOut) const;
+  void popStackUntilDFSScope(ValueDFSStack &, int DFSIn, int DFSOut);
+  ValueInfo &getOrCreateValueInfo(Value *);
+  const ValueInfo &getValueInfo(Value *) const;
+  Function &F;
+  DominatorTree &DT;
+  AssumptionCache &AC;
+  // This maps from copy operands to Predicate Info. Note that it does not own
+  // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos
+  // vector.
+  DenseMap<const Value *, const PredicateBase *> PredicateMap;
+  // This stores info about each operand or comparison result we make copies
+  // of.  The real ValueInfos start at index 1, index 0 is unused so that we can
+  // more easily detect invalid indexing.
+  SmallVector<ValueInfo, 32> ValueInfos;
+  // This gives the index into the ValueInfos array for a given Value.  Because
+  // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell
+  // whether it returned a valid result.
+  DenseMap<Value *, unsigned int> ValueInfoNums;
+  // OrderedBasicBlocks used during sorting uses
+  DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> OBBMap;
+};
+
+// This pass does eager building and then printing of PredicateInfo. It is used
+// by
+// the tests to be able to build, dump, and verify PredicateInfo.
+class PredicateInfoPrinterLegacyPass : public FunctionPass {
+public:
+  PredicateInfoPrinterLegacyPass();
+
+  static char ID;
+  bool runOnFunction(Function &) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+/// \brief Printer pass for \c PredicateInfo.
+class PredicateInfoPrinterPass
+    : public PassInfoMixin<PredicateInfoPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// \brief Verifier pass for \c PredicateInfo.
+struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
Index: lib/Passes/PassBuilder.cpp
===================================================================
--- lib/Passes/PassBuilder.cpp
+++ lib/Passes/PassBuilder.cpp
@@ -136,6 +136,7 @@
 #include "llvm/Transforms/Utils/Mem2Reg.h"
 #include "llvm/Transforms/Utils/MemorySSA.h"
 #include "llvm/Transforms/Utils/NameAnonGlobals.h"
+#include "llvm/Transforms/Utils/PredicateInfo.h"
 #include "llvm/Transforms/Utils/SimplifyInstructions.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include "llvm/Transforms/Vectorize/LoopVectorize.h"
Index: lib/Transforms/Utils/CMakeLists.txt
===================================================================
--- lib/Transforms/Utils/CMakeLists.txt
+++ lib/Transforms/Utils/CMakeLists.txt
@@ -38,6 +38,7 @@
   MetaRenamer.cpp
   ModuleUtils.cpp
   NameAnonGlobals.cpp
+  PredicateInfo.cpp
   PromoteMemoryToRegister.cpp
   StripGCRelocates.cpp
   SSAUpdater.cpp
Index: lib/Transforms/Utils/PredicateInfo.cpp
===================================================================
--- /dev/null
+++ lib/Transforms/Utils/PredicateInfo.cpp
@@ -0,0 +1,643 @@
+//===-- PredicateInfo.cpp - PredicateInfo Builder--------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------===//
+//
+// This file implements the PredicateInfo class.
+//
+//===----------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/PredicateInfo.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/IR/AssemblyAnnotationWriter.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
+#include "llvm/Transforms/Scalar.h"
+#include <algorithm>
+#define DEBUG_TYPE "predicateinfo"
+using namespace llvm;
+using namespace PatternMatch;
+using namespace llvm::PredicateInfoClasses;
+
+INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
+                      "PredicateInfo Printer", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
+                    "PredicateInfo Printer", false, false)
+static cl::opt<bool> VerifyPredicateInfo(
+    "verify-predicateinfo", cl::init(false), cl::Hidden,
+    cl::desc("Verify PredicateInfo in legacy printer pass."));
+namespace llvm {
+namespace PredicateInfoClasses {
+enum LocalNum {
+  // Operations that must appear first in the block.
+  LN_First,
+  // Operations that are somewhere in the middle of the block, and are sorted on
+  // demand.
+  LN_Middle,
+  // Operations that must appear last in a block, like successor phi node uses.
+  LN_Last
+};
+
+// Associate global and local DFS info with defs and uses, so we can sort them
+// into a global domination ordering.
+struct ValueDFS {
+  int DFSIn = 0;
+  int DFSOut = 0;
+  unsigned int LocalNum = LN_Middle;
+  PredicateBase *PInfo = nullptr;
+  // Only one of Def or Use will be set.
+  Value *Def = nullptr;
+  Use *Use = nullptr;
+};
+
+// This compares ValueDFS structures, creating OrderedBasicBlocks where
+// necessary to compare uses/defs in the same block.  Doing so allows us to walk
+// the minimum number of instructions necessary to compute our def/use ordering.
+struct ValueDFS_Compare {
+  DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &OBBMap;
+  ValueDFS_Compare(
+      DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> &OBBMap)
+      : OBBMap(OBBMap) {}
+  bool operator()(const ValueDFS &A, const ValueDFS &B) const {
+    if (&A == &B)
+      return false;
+    // The only case we can't directly compare them is when they in the same
+    // block, and both have localnum == middle.  In that case, we have to use
+    // comesbefore to see what the real ordering is, because they are in the
+    // same basic block.
+
+    bool SameBlock = std::tie(A.DFSIn, A.DFSOut) == std::tie(B.DFSIn, B.DFSOut);
+
+    if (!SameBlock || A.LocalNum != LN_Middle || B.LocalNum != LN_Middle)
+      return std::tie(A.DFSIn, A.DFSOut, A.LocalNum, A.Def, A.Use) <
+             std::tie(B.DFSIn, B.DFSOut, B.LocalNum, B.Def, B.Use);
+    return localComesBefore(A, B);
+  }
+
+  // This performs the necessary local basic block ordering checks to tell
+  // whether A comes before B, where both are in the same basic block.
+  bool localComesBefore(const ValueDFS &A, const ValueDFS &B) const {
+    auto *ADef = A.Def;
+    auto *BDef = B.Def;
+
+    // It's possible for the defs and uses to be null.  For branches, the local
+    // numbering will say the placed predicaeinfos should go first (IE
+    // LN_beginning), so we won't be in this function. For assumes, we will end
+    // up here, beause we need to order the def we will placerelative to the
+    // assume.  So for the purpose of this function, we pretend the def is the
+    // assume because that is where we will insert the info.
+    if (!ADef && !A.Use) {
+      assert(A.PInfo &&
+             "No def, no use, and no predicateinfo should not occur");
+      assert(isa<PredicateAssume>(A.PInfo) &&
+             "Middle of block should only occur for assumes");
+      ADef = cast<PredicateAssume>(A.PInfo)->AssumeInst;
+    }
+    if (!BDef && !B.Use) {
+      assert(B.PInfo &&
+             "No def, no use, and no predicateinfo should not occur");
+      assert(isa<PredicateAssume>(B.PInfo) &&
+             "Middle of block should only occur for assumes");
+      BDef = cast<PredicateAssume>(B.PInfo)->AssumeInst;
+    }
+
+    // See if we have real values or uses. If we have real values, we are
+    // guaranteed they are instructions or arguments. No matter what, we are
+    // guaranteed they are in the same block if they are instructions.
+    auto *ArgA = dyn_cast_or_null<Argument>(ADef);
+    auto *ArgB = dyn_cast_or_null<Argument>(BDef);
+
+    if (ArgA && !ArgB)
+      return true;
+    if (ArgB && !ArgA)
+      return false;
+    if (ArgA && ArgB)
+      return ArgA->getArgNo() < ArgB->getArgNo();
+
+    Instruction *AInst = nullptr;
+    Instruction *BInst = nullptr;
+    if (ADef) {
+      AInst = cast<Instruction>(ADef);
+    } else {
+      AInst = cast<Instruction>(A.Use->getUser());
+    }
+    if (BDef) {
+      BInst = cast<Instruction>(BDef);
+    } else {
+      BInst = cast<Instruction>(B.Use->getUser());
+    }
+    auto *BB = AInst->getParent();
+    auto LookupResult = OBBMap.find(BB);
+    if (LookupResult != OBBMap.end())
+      return LookupResult->second->dominates(AInst, BInst);
+    else {
+      //      auto *OBB = new OrderedBasicBlock(BB);
+      auto Result = OBBMap.insert({BB, make_unique<OrderedBasicBlock>(BB)});
+      return Result.first->second->dominates(AInst, BInst);
+    }
+    return std::tie(ADef, A.Use) < std::tie(BDef, B.Use);
+  }
+};
+
+} // namespace PredicateInfoClasses
+
+bool PredicateInfo::stackIsInScope(const ValueDFSStack &Stack, int DFSIn,
+                                   int DFSOut) const {
+  if (Stack.empty())
+    return false;
+  return DFSIn >= Stack.back().DFSIn && DFSOut <= Stack.back().DFSOut;
+}
+
+void PredicateInfo::popStackUntilDFSScope(ValueDFSStack &Stack, int DFSIn,
+                                          int DFSOut) {
+  while (!Stack.empty() && !stackIsInScope(Stack, DFSIn, DFSOut))
+    Stack.pop_back();
+}
+
+// Convert the uses of Op into a vector of uses, associating global and local
+// DFS info with each one.
+void PredicateInfo::convertUsesToDFSOrdered(
+    Value *Op, SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
+  for (auto &U : Op->uses()) {
+    if (auto *I = dyn_cast<Instruction>(U.getUser())) {
+      ValueDFS VD;
+      // Put the phi node uses in the incoming block.
+      BasicBlock *IBlock;
+      if (auto *PN = dyn_cast<PHINode>(I)) {
+        IBlock = PN->getIncomingBlock(U);
+        // Make phi node users appear last in the incoming block
+        // they are from.
+        VD.LocalNum = LN_Last;
+      } else {
+        // If it's not a phi node use, it is somewhere in the middle of the
+        // block.
+        IBlock = I->getParent();
+        VD.LocalNum = LN_Middle;
+      }
+      DomTreeNode *DomNode = DT.getNode(IBlock);
+      // It's possible our use is in an unreachable block. Skip it if so.
+      if (!DomNode)
+        continue;
+      VD.DFSIn = DomNode->getDFSNumIn();
+      VD.DFSOut = DomNode->getDFSNumOut();
+      VD.Use = &U;
+      DFSOrderedSet.push_back(VD);
+    }
+  }
+}
+
+// Collect relevant operations from Comparison that we may want to insert copies
+// for.
+void collectCmpOps(CmpInst *Comparison, SmallVectorImpl<Value *> &CmpOperands) {
+  auto *Op0 = Comparison->getOperand(0);
+  auto *Op1 = Comparison->getOperand(1);
+  if (Op0 == Op1)
+    return;
+  CmpOperands.push_back(Comparison);
+  // Only want real values, not constants.  Additionally, operands with one use
+  // are only being used in the comparison, which means they will not be useful
+  // for us to consider for predicateinfo.
+  //
+  // FIXME: LLVM crashes trying to create an intrinsic declaration of some
+  // pointer to function types that return structs, so we avoid them.
+  if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse() &&
+      !(Op0->getType()->isPointerTy() &&
+        Op0->getType()->getPointerElementType()->isFunctionTy()))
+    CmpOperands.push_back(Op0);
+  if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse() &&
+      !(Op1->getType()->isPointerTy() &&
+        Op1->getType()->getPointerElementType()->isFunctionTy()))
+    CmpOperands.push_back(Op1);
+}
+
+// Process an assume instruction and place relevant operations we want to rename
+// into OpsToRename.
+void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
+                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+  SmallVector<Value *, 8> CmpOperands;
+  // Second, see if we have a comparison we support
+  SmallVector<Value *, 2> ComparisonsToProcess;
+  CmpInst::Predicate Pred;
+  Value *Operand = II->getOperand(0);
+  if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()),
+              m_Cmp(Pred, m_Value(), m_Value()))
+          .match(II->getOperand(0))) {
+    ComparisonsToProcess.push_back(
+        cast<BinaryOperator>(Operand)->getOperand(0));
+    ComparisonsToProcess.push_back(
+        cast<BinaryOperator>(Operand)->getOperand(1));
+  } else {
+    ComparisonsToProcess.push_back(Operand);
+  }
+  for (auto Comparison : ComparisonsToProcess) {
+    if (auto *Cmp = dyn_cast<CmpInst>(Comparison)) {
+      collectCmpOps(Cmp, CmpOperands);
+      // Now add our copy infos for our operands
+      for (auto *Op : CmpOperands) {
+        OpsToRename.insert(Op);
+        auto &OperandInfo = getOrCreateValueInfo(Op);
+        PredicateBase *PB = new PredicateAssume(Op, II, Cmp);
+        AllInfos.push_back(PB);
+        OperandInfo.Infos.push_back(PB);
+      }
+      CmpOperands.clear();
+    }
+  }
+}
+
+// Process a block terminating branch, and place relevant operations to be
+// renamed into OpsToRename.
+void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
+                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+  SmallVector<Value *, 8> CmpOperands;
+  BasicBlock *FirstBB = BI->getSuccessor(0);
+  BasicBlock *SecondBB = BI->getSuccessor(1);
+  bool FirstSinglePred = FirstBB->getSinglePredecessor();
+  bool SecondSinglePred = SecondBB->getSinglePredecessor();
+  SmallVector<BasicBlock *, 2> SuccsToProcess;
+  bool isAnd = false;
+  bool isOr = false;
+  // First make sure we have single preds for these successors, as we can't
+  // usefully propagate true/false info to them if there are multiple paths to
+  // them.
+  if (FirstSinglePred)
+    SuccsToProcess.push_back(FirstBB);
+  if (SecondSinglePred)
+    SuccsToProcess.push_back(SecondBB);
+  if (SuccsToProcess.empty())
+    return;
+  // Second, see if we have a comparison we support
+  SmallVector<Value *, 2> ComparisonsToProcess;
+  CmpInst::Predicate Pred;
+
+  // Match combinations of conditions.
+  if (match(BI->getCondition(), m_And(m_Cmp(Pred, m_Value(), m_Value()),
+                                      m_Cmp(Pred, m_Value(), m_Value()))) ||
+      match(BI->getCondition(), m_Or(m_Cmp(Pred, m_Value(), m_Value()),
+                                     m_Cmp(Pred, m_Value(), m_Value())))) {
+    auto *BinOp = cast<BinaryOperator>(BI->getCondition());
+    if (BinOp->getOpcode() == Instruction::And)
+      isAnd = true;
+    else if (BinOp->getOpcode() == Instruction::Or)
+      isOr = true;
+    ComparisonsToProcess.push_back(BinOp->getOperand(0));
+    ComparisonsToProcess.push_back(BinOp->getOperand(1));
+  } else {
+    ComparisonsToProcess.push_back(BI->getCondition());
+  }
+  for (auto Comparison : ComparisonsToProcess) {
+    if (auto *Cmp = dyn_cast<CmpInst>(Comparison)) {
+      collectCmpOps(Cmp, CmpOperands);
+      // Now add our copy infos for our operands
+      for (auto *Op : CmpOperands) {
+        OpsToRename.insert(Op);
+        auto &OperandInfo = getOrCreateValueInfo(Op);
+        for (auto *Succ : SuccsToProcess) {
+          bool TakenEdge = (Succ == FirstBB);
+          // For and, only insert on the true edge
+          // For or, only insert on the false edge
+          if ((isAnd && !TakenEdge) || (isOr && TakenEdge))
+            continue;
+          PredicateBase *PB =
+              new PredicateBranch(Op, BranchBB, Succ, Cmp, TakenEdge);
+          AllInfos.push_back(PB);
+          OperandInfo.Infos.push_back(PB);
+        }
+      }
+      CmpOperands.clear();
+    }
+  }
+}
+
+// Build predicate info for our function
+void PredicateInfo::buildPredicateInfo() {
+  DT.updateDFSNumbers();
+  // Collect operands to rename from all conditional branch terminators, as well
+  // as assume statements.
+  SmallPtrSet<Value *, 8> OpsToRename;
+  for (auto DTN : depth_first(DT.getRootNode())) {
+    BasicBlock *BranchBB = DTN->getBlock();
+    if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
+      if (!BI->isConditional())
+        continue;
+      processBranch(BI, BranchBB, OpsToRename);
+    }
+  }
+  for (auto &Assume : AC.assumptions()) {
+    if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
+      processAssume(II, II->getParent(), OpsToRename);
+  }
+  // Now rename all our operations.
+  renameUses(OpsToRename);
+}
+Value *PredicateInfo::materializeStack(unsigned int &Counter,
+                                       ValueDFSStack &RenameStack,
+                                       Value *OrigOp) {
+  // Find the first thing we have to materialize
+  auto RevIter = RenameStack.rbegin();
+  for (; RevIter != RenameStack.rend(); ++RevIter)
+    if (RevIter->Def)
+      break;
+
+  size_t Start = RevIter - RenameStack.rbegin();
+  // The maximum number of things we should be trying to materialize at once
+  // right now is 4, depending on if we had an assume, a branch, and both used
+  // and of conditions.
+  for (auto RenameIter = RenameStack.end() - Start;
+       RenameIter != RenameStack.end(); ++RenameIter) {
+    auto *Op =
+        RenameIter == RenameStack.begin() ? OrigOp : (RenameIter - 1)->Def;
+    ValueDFS &Result = *RenameIter;
+    auto *ValInfo = Result.PInfo;
+    // For branches, we can just place the operand in the split block.  For
+    // assume, we have to place it right before the assume to ensure we dominate
+    // all of our uses.
+    if (isa<PredicateBranch>(ValInfo)) {
+      auto *PBranch = cast<PredicateBranch>(ValInfo);
+      // It's possible we are trying to insert multiple predicateinfos in the
+      // same block at the beginning of the block.  When we do this, we need to
+      // insert them one after the other, not one before the other. To see if we
+      // have already inserted predicateinfo into this block, we see if Op !=
+      // OrigOp && Op->getParent() == PBranch->SplitBB.  Op must be an
+      // instruction we inserted if it's not the original op.
+      BasicBlock::iterator InsertPt;
+      if (Op == OrigOp ||
+          cast<Instruction>(Op)->getParent() != PBranch->SplitBB) {
+        InsertPt = PBranch->SplitBB->begin();
+        // Insert after last phi node.
+        while (isa<PHINode>(InsertPt))
+          ++InsertPt;
+      } else {
+        // Insert after op.
+        InsertPt = ++(cast<Instruction>(Op)->getIterator());
+      }
+      IRBuilder<> B(PBranch->SplitBB, InsertPt);
+      Function *IF = Intrinsic::getDeclaration(
+          F.getParent(), Intrinsic::ssa_copy, Op->getType());
+      Value *PIC = B.CreateCall(IF, Op, Op->getName() + "." + Twine(Counter++));
+      PredicateMap.insert({PIC, ValInfo});
+      Result.Def = PIC;
+    } else {
+      auto *PAssume = dyn_cast<PredicateAssume>(ValInfo);
+      assert(PAssume &&
+             "Should not have gotten here without it being an assume");
+      // Unlike above, this should already insert in the right order when we
+      // insert multiple predicateinfos in the same block.  Because we are
+      // always inserting right before the assume (instead of the beginning of a
+      // block), newer insertions will end up after older ones.
+      IRBuilder<> B(PAssume->AssumeInst->getParent(),
+                    PAssume->AssumeInst->getIterator());
+      Function *IF = Intrinsic::getDeclaration(
+          F.getParent(), Intrinsic::ssa_copy, Op->getType());
+      Value *PIC = B.CreateCall(IF, Op);
+      PredicateMap.insert({PIC, ValInfo});
+      Result.Def = PIC;
+    }
+  }
+  return RenameStack.back().Def;
+}
+
+// Instead of the standard SSA renaming algorithm, which is O(Number of
+// instructions), and walks the entire dominator tree, we walk only the defs +
+// uses.  The standard SSA renaming algorithm does not really rely on the
+// dominator tree except to order the stack push/pops of the renaming stacks, so
+// that defs end up getting pushed before hitting the correct uses.  This does
+// not require the dominator tree, only the *order* of the dominator tree. The
+// complete and correct ordering of the defs and uses, in dominator tree is
+// contained in the DFS numbering of the dominator tree. So we sort the defs and
+// uses into the DFS ordering, and then just use the renaming stack as per
+// normal, pushing when we hit a def (which is a predicateinfo instruction),
+// popping when we are out of the dfs scope for that def, and replacing any uses
+// with top of stack if it exists.  In order to handle liveness without
+// propagating liveness info, we don't actually insert the predicateinfo
+// instruction def until we see a use that it would dominate.  Once we see such
+// a use, we materialize the predicateinfo instruction in the right place and
+// use it.
+//
+// TODO: Use this algorithm to perform fast single-variable renaming in
+// promotememtoreg and memoryssa.
+void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpsToRename) {
+  ValueDFS_Compare Compare(OBBMap);
+  // Compute liveness, and rename in O(uses) per Op.
+  for (auto *Op : OpsToRename) {
+    unsigned Counter = 0;
+    SmallVector<ValueDFS, 16> OrderedUses;
+    const auto &ValueInfo = getValueInfo(Op);
+    // Insert the possible copies into the def/use list.
+    // They will become real copies if we find a real use for them, and never
+    // created otherwise.
+    for (auto &PossibleCopy : ValueInfo.Infos) {
+      ValueDFS VD;
+      BasicBlock *CopyBB = nullptr;
+      // Determine where we are going to place the copy by the copy type.
+      // The predicate info for branches always come first, they will get
+      // materialized in the split block at the top of the block.
+      // The predicate info for assumes will be somewhere in the middle,
+      // it will get materialized in front of the assume.
+      if (const auto *PBranch = dyn_cast<PredicateBranch>(PossibleCopy)) {
+        CopyBB = PBranch->SplitBB;
+        VD.LocalNum = LN_First;
+      } else if (const auto *PAssume =
+                     dyn_cast<PredicateAssume>(PossibleCopy)) {
+        CopyBB = PAssume->AssumeInst->getParent();
+        VD.LocalNum = LN_Middle;
+      } else
+        llvm_unreachable("Unhandled predicate info type");
+      DomTreeNode *DomNode = DT.getNode(CopyBB);
+      if (!DomNode)
+        continue;
+      VD.DFSIn = DomNode->getDFSNumIn();
+      VD.DFSOut = DomNode->getDFSNumOut();
+      VD.PInfo = PossibleCopy;
+      OrderedUses.push_back(VD);
+    }
+
+    convertUsesToDFSOrdered(Op, OrderedUses);
+    std::sort(OrderedUses.begin(), OrderedUses.end(), Compare);
+    SmallVector<ValueDFS, 8> RenameStack;
+    // For each use, sorted into dfs order, push values and replaces uses with
+    // top of stack, which will represent the reaching def.
+    for (auto &VD : OrderedUses) {
+      // We currently do not materialize copy over copy, but we should decide if
+      // we want to.
+      bool PossibleCopy = VD.PInfo != nullptr;
+      if (RenameStack.empty()) {
+        DEBUG(dbgs() << "Rename Stack is empty\n");
+      } else {
+        DEBUG(dbgs() << "Rename Stack Top DFS numbers are ("
+                     << RenameStack.back().DFSIn << ","
+                     << RenameStack.back().DFSOut << ")\n");
+      }
+
+      DEBUG(dbgs() << "Current DFS numbers are (" << VD.DFSIn << ","
+                   << VD.DFSOut << ")\n");
+
+      bool ShouldPush = (VD.Def || PossibleCopy);
+      bool OutOfScope = !stackIsInScope(RenameStack, VD.DFSIn, VD.DFSOut);
+      if (OutOfScope || ShouldPush) {
+        // Sync to our current scope.
+        popStackUntilDFSScope(RenameStack, VD.DFSIn, VD.DFSOut);
+        ShouldPush |= (VD.Def || PossibleCopy);
+        if (ShouldPush) {
+          RenameStack.push_back(VD);
+        }
+      }
+      // If we get to this point, and the stack is empty we must have a use
+      // with no renaming needed, just skip it.
+      if (RenameStack.empty())
+        continue;
+      // Skip values, only want to rename the uses
+      if (VD.Def || PossibleCopy)
+        continue;
+      ValueDFS &Result = RenameStack.back();
+
+      // If the possible copy dominates something, materialize our stack up to
+      // this point. This ensures every comparison that affects our operation
+      // ends up with predicateinfo.
+      if (!Result.Def)
+        Result.Def = materializeStack(Counter, RenameStack, Op);
+
+      DEBUG(dbgs() << "Found replacement " << *Result.Def << " for "
+                   << *VD.Use->get() << " in " << *(VD.Use->getUser()) << "\n");
+      assert(DT.dominates(cast<Instruction>(Result.Def), *VD.Use) &&
+             "Predicateinfo def should have dominated this use");
+      VD.Use->set(Result.Def);
+    }
+  }
+}
+
+PredicateInfo::ValueInfo &PredicateInfo::getOrCreateValueInfo(Value *Operand) {
+  auto OIN = ValueInfoNums.find(Operand);
+  if (OIN == ValueInfoNums.end()) {
+    // This will grow it
+    ValueInfos.resize(ValueInfos.size() + 1);
+    // This will use the new size and give us a 0 based number of the info
+    auto InsertResult = ValueInfoNums.insert({Operand, ValueInfos.size() - 1});
+    assert(InsertResult.second && "Value info number already existed?");
+    return ValueInfos[InsertResult.first->second];
+  }
+  return ValueInfos[OIN->second];
+}
+
+const PredicateInfo::ValueInfo &
+PredicateInfo::getValueInfo(Value *Operand) const {
+  auto OINI = ValueInfoNums.lookup(Operand);
+  assert(OINI != 0 && "Operand was not really in the Value Info Numbers");
+  assert(OINI < ValueInfos.size() &&
+         "Value Info Number greater than size of Value Info Table");
+  return ValueInfos[OINI];
+}
+
+PredicateInfo::PredicateInfo(Function &F, DominatorTree &DT,
+                             AssumptionCache &AC)
+    : F(F), DT(DT), AC(AC) {
+  // Push an empty operand info so that we can detect 0 as not finding one
+  ValueInfos.resize(1);
+  buildPredicateInfo();
+}
+
+PredicateInfo::~PredicateInfo() {}
+
+void PredicateInfo::verifyPredicateInfo() const {}
+
+char PredicateInfoPrinterLegacyPass::ID = 0;
+
+PredicateInfoPrinterLegacyPass::PredicateInfoPrinterLegacyPass()
+    : FunctionPass(ID) {
+  initializePredicateInfoPrinterLegacyPassPass(
+      *PassRegistry::getPassRegistry());
+}
+
+void PredicateInfoPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
+  AU.addRequired<AssumptionCacheTracker>();
+}
+
+bool PredicateInfoPrinterLegacyPass::runOnFunction(Function &F) {
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+  auto PredInfo = make_unique<PredicateInfo>(F, DT, AC);
+  PredInfo->print(dbgs());
+  if (VerifyPredicateInfo)
+    PredInfo->verifyPredicateInfo();
+  return false;
+}
+
+PreservedAnalyses PredicateInfoPrinterPass::run(Function &F,
+                                                FunctionAnalysisManager &AM) {
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  OS << "PredicateInfo for function: " << F.getName() << "\n";
+  make_unique<PredicateInfo>(F, DT, AC)->print(OS);
+
+  return PreservedAnalyses::all();
+}
+
+/// \brief An assembly annotator class to print PredicateInfo information in
+/// comments.
+class PredicateInfoAnnotatedWriter : public AssemblyAnnotationWriter {
+  friend class PredicateInfo;
+  const PredicateInfo *PredInfo;
+
+public:
+  PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
+
+  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
+                                        formatted_raw_ostream &OS) {}
+
+  virtual void emitInstructionAnnot(const Instruction *I,
+                                    formatted_raw_ostream &OS) {
+    if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
+      OS << "; Has predicate info\n";
+      if (const auto *PB = dyn_cast<PredicateBranch>(PI))
+        OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
+           << " Comparison:" << *PB->Comparison << " }\n";
+      else if (const auto *PA = dyn_cast<PredicateAssume>(PI))
+        OS << "; assume predicate info {"
+           << " Comparison:" << *PA->Comparison << " }\n";
+    }
+  }
+};
+
+void PredicateInfo::print(raw_ostream &OS) const {
+  PredicateInfoAnnotatedWriter Writer(this);
+  F.print(OS, &Writer);
+}
+
+void PredicateInfo::dump() const {
+  PredicateInfoAnnotatedWriter Writer(this);
+  F.print(dbgs(), &Writer);
+}
+
+PreservedAnalyses PredicateInfoVerifierPass::run(Function &F,
+                                                 FunctionAnalysisManager &AM) {
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  make_unique<PredicateInfo>(F, DT, AC)->verifyPredicateInfo();
+
+  return PreservedAnalyses::all();
+}
+}
Index: lib/Transforms/Utils/Utils.cpp
===================================================================
--- lib/Transforms/Utils/Utils.cpp
+++ lib/Transforms/Utils/Utils.cpp
@@ -38,6 +38,7 @@
   initializeMemorySSAWrapperPassPass(Registry);
   initializeMemorySSAPrinterLegacyPassPass(Registry);
   initializeStripGCRelocatesPass(Registry);
+  initializePredicateInfoPrinterLegacyPassPass(Registry);
 }
 
 /// LLVMInitializeTransformUtils - C binding for initializeTransformUtilsPasses.
Index: test/Transforms/Util/PredicateInfo/condprop.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/PredicateInfo/condprop.ll
@@ -0,0 +1,478 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -print-predicateinfo -S | FileCheck %s
+
+@a = external global i32		; <i32*> [#uses=7]
+
+define i32 @test1() nounwind {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[BB:%.*]], label [[BB1:%.*]]
+; CHECK:       bb:
+; CHECK-NEXT:    br label [[BB8:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 5
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB2:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 4
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], 5
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 5
+; CHECK-NEXT:    br i1 [[TMP9]], label [[BB6:%.*]], label [[BB7:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP10:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[TMP10]], 4
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP12:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb8:
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ [[TMP12]], [[BB7]] ], [ [[TMP11]], [[BB6]] ], [ [[TMP7]], [[BB4]] ], [ 4, [[BB2]] ], [ 5, [[BB]] ]
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 [[DOT0]]
+;
+entry:
+  %0 = load i32, i32* @a, align 4
+  %1 = icmp eq i32 %0, 4
+  br i1 %1, label %bb, label %bb1
+
+bb:		; preds = %entry
+  br label %bb8
+
+bb1:		; preds = %entry
+  %2 = load i32, i32* @a, align 4
+  %3 = icmp eq i32 %2, 5
+  br i1 %3, label %bb2, label %bb3
+
+bb2:		; preds = %bb1
+  br label %bb8
+
+bb3:		; preds = %bb1
+  %4 = load i32, i32* @a, align 4
+  %5 = icmp eq i32 %4, 4
+  br i1 %5, label %bb4, label %bb5
+
+bb4:		; preds = %bb3
+  %6 = load i32, i32* @a, align 4
+  %7 = add i32 %6, 5
+  br label %bb8
+
+bb5:		; preds = %bb3
+  %8 = load i32, i32* @a, align 4
+  %9 = icmp eq i32 %8, 5
+  br i1 %9, label %bb6, label %bb7
+
+bb6:		; preds = %bb5
+  %10 = load i32, i32* @a, align 4
+  %11 = add i32 %10, 4
+  br label %bb8
+
+bb7:		; preds = %bb5
+  %12 = load i32, i32* @a, align 4
+  br label %bb8
+
+bb8:		; preds = %bb7, %bb6, %bb4, %bb2, %bb
+  %.0 = phi i32 [ %12, %bb7 ], [ %11, %bb6 ], [ %7, %bb4 ], [ 4, %bb2 ], [ 5, %bb ]
+  br label %return
+
+return:		; preds = %bb8
+  ret i32 %.0
+}
+
+declare void @foo(i1)
+declare void @bar(i32)
+
+; CHECK-LABEL: @test3(
+define void @test3(i32 %x, i32 %y) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH_ZERO:%.*]], label [[NOPE:%.*]]
+; CHECK:       both_zero:
+; CHECK-NEXT:    [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK-NEXT:    [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK-NEXT:    [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
+; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xz = icmp eq i32 %x, 0
+  %yz = icmp eq i32 %y, 0
+  %z = and i1 %xz, %yz
+  br i1 %z, label %both_zero, label %nope
+both_zero:
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+nope:
+  call void @foo(i1 %z)
+  ret void
+}
+
+; CHECK-LABEL: @test4(
+define void @test4(i1 %b, i32 %x) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    br i1 [[B:%.*]], label [[SW:%.*]], label [[CASE3:%.*]]
+; CHECK:       sw:
+; CHECK-NEXT:    switch i32 [[X:%.*]], label [[DEFAULT:%.*]] [
+; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
+; CHECK-NEXT:    i32 1, label [[CASE1:%.*]]
+; CHECK-NEXT:    i32 2, label [[CASE0]]
+; CHECK-NEXT:    i32 3, label [[CASE3]]
+; CHECK-NEXT:    i32 4, label [[DEFAULT]]
+; CHECK-NEXT:    ]
+; CHECK:       default:
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    ret void
+; CHECK:       case0:
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    ret void
+; CHECK:       case1:
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    ret void
+; CHECK:       case3:
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    ret void
+;
+  br i1 %b, label %sw, label %case3
+sw:
+  switch i32 %x, label %default [
+  i32 0, label %case0
+  i32 1, label %case1
+  i32 2, label %case0
+  i32 3, label %case3
+  i32 4, label %default
+  ]
+default:
+  call void @bar(i32 %x)
+  ret void
+case0:
+  call void @bar(i32 %x)
+  ret void
+case1:
+  call void @bar(i32 %x)
+  ret void
+case3:
+  call void @bar(i32 %x)
+  ret void
+}
+
+; CHECK-LABEL: @test5(
+define i1 @test5(i32 %x, i32 %y) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[X_0]], [[Y_0]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i32 [[X_1]], [[Y_1]]
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  %cmp2 = icmp ne i32 %x, %y
+  ret i1 %cmp2
+
+different:
+  %cmp3 = icmp eq i32 %x, %y
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test6(
+define i1 @test6(i32 %x, i32 %y) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i32 [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = icmp ne i32 %x, %y
+  %cmp = icmp eq i32 %x, %y
+  %cmp3 = icmp eq i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test6_fp(
+define i1 @test6_fp(float %x, float %y) {
+; CHECK-LABEL: @test6_fp(
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp une float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp oeq float [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = fcmp oeq float [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = fcmp une float %x, %y
+  %cmp = fcmp oeq float %x, %y
+  %cmp3 = fcmp oeq float  %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test7(
+define i1 @test7(i32 %x, i32 %y) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X_0]], [[Y_0]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK-NEXT:    [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp sgt i32 [[X_1]], [[Y_1]]
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp = icmp sgt i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  %cmp2 = icmp sle i32 %x, %y
+  ret i1 %cmp2
+
+different:
+  %cmp3 = icmp sgt i32 %x, %y
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test7_fp(
+define i1 @test7_fp(float %x, float %y) {
+; CHECK-LABEL: @test7_fp(
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    [[Y_0:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]])
+; CHECK-NEXT:    [[X_0:%.*]] = call float @llvm.ssa.copy.f32(float [[X]])
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ule float [[X_0]], [[Y_0]]
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    [[Y_1:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]])
+; CHECK-NEXT:    [[X_1:%.*]] = call float @llvm.ssa.copy.f32(float [[X]])
+; CHECK-NEXT:    [[CMP3:%.*]] = fcmp ogt float [[X_1]], [[Y_1]]
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp = fcmp ogt float %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  %cmp2 = fcmp ule float %x, %y
+  ret i1 %cmp2
+
+different:
+  %cmp3 = fcmp ogt float %x, %y
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test8(
+define i1 @test8(i32 %x, i32 %y) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp sgt i32 [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = icmp sle i32 %x, %y
+  %cmp = icmp sgt i32 %x, %y
+  %cmp3 = icmp sgt i32 %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  ret i1 %cmp3
+}
+
+; CHECK-LABEL: @test8_fp(
+define i1 @test8_fp(float %x, float %y) {
+; CHECK-LABEL: @test8_fp(
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ule float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[X]], [[Y]]
+; CHECK-NEXT:    [[CMP3:%.*]] = fcmp ogt float [[X]], [[Y]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
+; CHECK:       same:
+; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK:       different:
+; CHECK-NEXT:    ret i1 [[CMP3]]
+;
+  %cmp2 = fcmp ule float %x, %y
+  %cmp = fcmp ogt float %x, %y
+  %cmp3 = fcmp ogt float %x, %y
+  br i1 %cmp, label %same, label %different
+
+same:
+  ret i1 %cmp2
+
+different:
+  ret i1 %cmp3
+}
+
+; PR1768
+; CHECK-LABEL: @test9(
+define i32 @test9(i32 %i, i32 %j) {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]])
+; CHECK-NEXT:    [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]])
+; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]]
+; CHECK-NEXT:    ret i32 [[DIFF]]
+; CHECK:       ret:
+; CHECK-NEXT:    ret i32 5
+;
+  %cmp = icmp eq i32 %i, %j
+  br i1 %cmp, label %cond_true, label %ret
+
+cond_true:
+  %diff = sub i32 %i, %j
+  ret i32 %diff
+
+ret:
+  ret i32 5
+}
+
+; PR1768
+; CHECK-LABEL: @test10(
+define i32 @test10(i32 %j, i32 %i) {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]])
+; CHECK-NEXT:    [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]])
+; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]]
+; CHECK-NEXT:    ret i32 [[DIFF]]
+; CHECK:       ret:
+; CHECK-NEXT:    ret i32 5
+;
+  %cmp = icmp eq i32 %i, %j
+  br i1 %cmp, label %cond_true, label %ret
+
+cond_true:
+  %diff = sub i32 %i, %j
+  ret i32 %diff
+
+ret:
+  ret i32 5
+}
+
+declare i32 @yogibar()
+
+; CHECK-LABEL: @test11(
+define i32 @test11(i32 %x) {
+; CHECK-LABEL: @test11(
+; CHECK-NEXT:    [[V0:%.*]] = call i32 @yogibar()
+; CHECK-NEXT:    [[V1:%.*]] = call i32 @yogibar()
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[V0]], [[V1]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[NEXT:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    [[V1_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V1]])
+; CHECK-NEXT:    ret i32 [[V1_0]]
+; CHECK:       next:
+; CHECK-NEXT:    [[V0_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0]])
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X:%.*]], [[V0_0]]
+; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_TRUE2:%.*]], label [[NEXT2:%.*]]
+; CHECK:       cond_true2:
+; CHECK-NEXT:    [[V0_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0_0]])
+; CHECK-NEXT:    ret i32 [[V0_0_1]]
+; CHECK:       next2:
+; CHECK-NEXT:    ret i32 0
+;
+  %v0 = call i32 @yogibar()
+  %v1 = call i32 @yogibar()
+  %cmp = icmp eq i32 %v0, %v1
+  br i1 %cmp, label %cond_true, label %next
+
+cond_true:
+  ret i32 %v1
+
+next:
+  %cmp2 = icmp eq i32 %x, %v0
+  br i1 %cmp2, label %cond_true2, label %next2
+
+cond_true2:
+  ret i32 %v0
+
+next2:
+  ret i32 0
+}
+
+; CHECK-LABEL: @test12(
+define i32 @test12(i32 %x) {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]
+; CHECK:       cond_true:
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK-NEXT:    br label [[RET:%.*]]
+; CHECK:       cond_false:
+; CHECK-NEXT:    [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK-NEXT:    br label [[RET]]
+; CHECK:       ret:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[X_0]], [[COND_TRUE]] ], [ [[X_1]], [[COND_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %cmp = icmp eq i32 %x, 0
+  br i1 %cmp, label %cond_true, label %cond_false
+
+cond_true:
+  br label %ret
+
+cond_false:
+  br label %ret
+
+ret:
+  %res = phi i32 [ %x, %cond_true ], [ %x, %cond_false ]
+  ret i32 %res
+}
Index: test/Transforms/Util/PredicateInfo/testandor.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/PredicateInfo/testandor.ll
@@ -0,0 +1,205 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -print-predicateinfo -analyze < %s 2>&1 | FileCheck %s
+
+declare void @foo(i1)
+declare void @bar(i32)
+declare void @llvm.assume(i1)
+
+define void @testor(i32 %x, i32 %y) {
+; CHECK-LABEL: @testor(
+; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[Z:%.*]] = or i1 [[XZ]], [[YZ]]
+; CHECK-NEXT:    br i1 [[Z]], label [[ONEOF:%.*]], label [[NEITHER:%.*]]
+; CHECK:       oneof:
+; CHECK-NEXT:    call void @foo(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ]])
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    call void @bar(i32 [[Y]])
+; CHECK-NEXT:    ret void
+; CHECK:       neither:
+; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
+; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xz = icmp eq i32 %x, 0
+  %yz = icmp eq i32 %y, 0
+  %z = or i1 %xz, %yz
+  br i1 %z, label %oneof, label %neither
+oneof:
+;; Should not insert on the true edge for or
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+neither:
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  call void @foo(i1 %z)
+  ret void
+}
+define void @testand(i32 %x, i32 %y) {
+; CHECK-LABEL: @testand(
+; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:       both:
+; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
+; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ]])
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    call void @bar(i32 [[Y]])
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xz = icmp eq i32 %x, 0
+  %yz = icmp eq i32 %y, 0
+  %z = and i1 %xz, %yz
+  br i1 %z, label %both, label %nope
+both:
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+nope:
+;; Should not insert on the false edge for and
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  call void @foo(i1 %z)
+  ret void
+}
+define void @testandsame(i32 %x, i32 %y) {
+; CHECK-LABEL: @testandsame(
+; CHECK-NEXT:    [[XGT:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[XLT:%.*]] = icmp slt i32 [[X]], 100
+; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XGT]], [[XLT]]
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:       both:
+; CHECK:         [[XLT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XLT]])
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK:         [[X_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X_0]])
+; CHECK:         [[XGT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XGT]])
+; CHECK-NEXT:    call void @foo(i1 [[XGT_0]])
+; CHECK-NEXT:    call void @foo(i1 [[XLT_0]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0_1]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[XGT]])
+; CHECK-NEXT:    call void @foo(i1 [[XLT]])
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xgt = icmp sgt i32 %x, 0
+  %xlt = icmp slt i32 %x, 100
+  %z = and i1 %xgt, %xlt
+  br i1 %z, label %both, label %nope
+both:
+  call void @foo(i1 %xgt)
+  call void @foo(i1 %xlt)
+  call void @bar(i32 %x)
+  ret void
+nope:
+  call void @foo(i1 %xgt)
+  call void @foo(i1 %xlt)
+  call void @foo(i1 %z)
+  ret void
+}
+
+define void @testandassume(i32 %x, i32 %y) {
+; CHECK-LABEL: @testandassume(
+; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
+; CHECK:         [[TMP1:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
+; CHECK:         [[TMP2:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
+; CHECK:         [[TMP3:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
+; CHECK:         [[TMP4:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
+; CHECK-NEXT:    call void @llvm.assume(i1 [[Z]])
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:       both:
+; CHECK:         [[DOT03:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP4]])
+; CHECK:         [[DOT02:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP3]])
+; CHECK:         [[DOT01:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP2]])
+; CHECK:         [[DOT0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP1]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT0]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT02]])
+; CHECK-NEXT:    call void @bar(i32 [[DOT01]])
+; CHECK-NEXT:    call void @bar(i32 [[DOT03]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xz = icmp eq i32 %x, 0
+  %yz = icmp eq i32 %y, 0
+  %z = and i1 %xz, %yz
+  call void @llvm.assume(i1 %z)
+  br i1 %z, label %both, label %nope
+both:
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+nope:
+  call void @foo(i1 %z)
+  ret void
+}
+
+;; Unlike and/or for branches, assume is *always* true, so we only match and for it
+define void @testorassume(i32 %x, i32 %y) {
+;
+; CHECK-LABEL: @testorassume(
+; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[Z:%.*]] = or i1 [[XZ]], [[YZ]]
+; CHECK-NEXT:    call void @llvm.assume(i1 [[Z]])
+; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:       both:
+; CHECK-NEXT:    call void @foo(i1 [[XZ]])
+; CHECK-NEXT:    call void @foo(i1 [[YZ]])
+; CHECK-NEXT:    call void @bar(i32 [[X]])
+; CHECK-NEXT:    call void @bar(i32 [[Y]])
+; CHECK-NEXT:    ret void
+; CHECK:       nope:
+; CHECK-NEXT:    call void @foo(i1 [[Z]])
+; CHECK-NEXT:    ret void
+;
+  %xz = icmp eq i32 %x, 0
+  %yz = icmp eq i32 %y, 0
+  %z = or i1 %xz, %yz
+  call void @llvm.assume(i1 %z)
+  br i1 %z, label %both, label %nope
+both:
+  call void @foo(i1 %xz)
+  call void @foo(i1 %yz)
+  call void @bar(i32 %x)
+  call void @bar(i32 %y)
+  ret void
+nope:
+  call void @foo(i1 %z)
+  ret void
+}