[PredicateInfo] Generalize processing of conditions

[nikic]

Summary

Branch/assume conditions in PredicateInfo are currently handle in a rather ad-hoc manner, with some arbitrary limitations. For example, an and of two icmps will be handled, but an and of an icmp and some other condition will not. That also includes the case where more than two conditions and and'ed together.

This patch makes the handling more general by looking through an arbitrary number of ands/ors and considering all kinds of conditions (though operands will only be taken for cmps of course).

[nikic]

The thought that the current limitations are compile-time related crossed my mind, but that doesn't seem to be a concern: https://llvm-compile-time-tracker.com/compare.php?from=00f773cf424699d8eb31591fdc95e0ca18b2682c&to=10ec7c7960ea47e899003fcd7d1ba5c389ba1cae&stat=instructions

[nikic]

Ping!

[fhahn]

In D94447#2493177, @nikic wrote:

The thought that the current limitations are compile-time related crossed my mind, but that doesn't seem to be a concern: https://llvm-compile-time-tracker.com/compare.php?from=00f773cf424699d8eb31591fdc95e0ca18b2682c&to=10ec7c7960ea47e899003fcd7d1ba5c389ba1cae&stat=instructions

I believe compile-time is at least partly a motivation for some limitation here, but not in a way that is exposed by CTMark. I think here we mostly want to guard against the worst case (deeply nested AND/OR). Those kind of cases are not really covered by the tests in CTMark (or other parts in the test-suite), but are surprisingly common in practice (e.g. various code-generators that feed into Clang/LLVM). I think it would be desirable to have a limit on the number of items in the worklist to guard against that.

llvm/test/Transforms/SCCP/conditions-ranges.ll

1012

Perhaps I missed it, but do we have tests with a chain or Ors? If not, it would be good to add one, also independent of SCCP. The same also for assume And it would probably be also good to cover the case where and and or are mixed.

[nikic]

Rebase over more tests, prevent exponential renaming with reused operands.

[nikic]

In D94447#2505374, @fhahn wrote:

I believe compile-time is at least partly a motivation for some limitation here, but not in a way that is exposed by CTMark. I think here we mostly want to guard against the worst case (deeply nested AND/OR). Those kind of cases are not really covered by the tests in CTMark (or other parts in the test-suite), but are surprisingly common in practice (e.g. various code-generators that feed into Clang/LLVM). I think it would be desirable to have a limit on the number of items in the worklist to guard against that.

You make a good point here. I think it's worthwhile to distinguish two cases though: The first is where you have a simple chain of and's. I believe this is harmless. Even if you have 32 and's in a row, you would introduce 32 new variables, and that's linear in the input size. This is not a pathological case. The second case is where you have code like this:

%b = and i1 %a, %a
%c = and i1 %b, %b
%d = and i1 %c, %c
...

That is, where and operands get reused in a tree. In this case, my previous code introduced an exponential number of variables for %a, which is certainly not good. I have updated the implementation to add a Visited set, which will cut down the number of renames to linear. I've also added some test cases for deep chains and trees (as well as general tests for nesting).

Does this address this concern sufficiently, or do you want the linear case to be limited as well?

[fhahn]

In D94447#2505439, @nikic wrote:

In D94447#2505374, @fhahn wrote:

I believe compile-time is at least partly a motivation for some limitation here, but not in a way that is exposed by CTMark. I think here we mostly want to guard against the worst case (deeply nested AND/OR). Those kind of cases are not really covered by the tests in CTMark (or other parts in the test-suite), but are surprisingly common in practice (e.g. various code-generators that feed into Clang/LLVM). I think it would be desirable to have a limit on the number of items in the worklist to guard against that.

You make a good point here. I think it's worthwhile to distinguish two cases though: The first is where you have a simple chain of and's. I believe this is harmless. Even if you have 32 and's in a row, you would introduce 32 new variables, and that's linear in the input size. This is not a pathological case. The second case is where you have code like this:

%b = and i1 %a, %a
%c = and i1 %b, %b
%d = and i1 %c, %c
...

That is, where and operands get reused in a tree. In this case, my previous code introduced an exponential number of variables for %a, which is certainly not good. I have updated the implementation to add a Visited set, which will cut down the number of renames to linear. I've also added some test cases for deep chains and trees (as well as general tests for nesting).

Does this address this concern sufficiently, or do you want the linear case to be limited as well?

I think there is still a potentially problematic case: multiple branches could use the same deep chain/tree of and/ors (or different entries of the same tree), in which case the new approach would still have to traverse a lot of instructions in the worst case I think.

Granted, this is unlikely to happen often in practice, but the original goal of PredicateInfo is to be as fast as possible IIRC, so ensuring we only traverse and create a constant number of instructions per branch/assume would still be desirable I think.

[nikic]

Add a limit on the maximum number of conditions we handle for each branch/assume. Value for the limit was picked arbitrarily...

[fhahn]

LGTM, thanks

lib/Transforms/Utils/PredicateInfo.cpp

58 ↗

(On Diff #317892)

can this be static or in an anonymous namespace?

[nikic]

lib/Transforms/Utils/PredicateInfo.cpp

58 ↗

(On Diff #317892)

Yeah, this should've been static. I'll fix this when landing.

llvm/lib/Transforms/Utils/PredicateInfo.cpp

 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."));
 DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
               "Controls which variables are renamed with predicateinfo");
 
+// Maximum number of conditions considered for renaming for each branch/assume.
+// This limits renaming of deep and/or chains.
+static const unsigned MaxCondsPerBranch = 8;
+
 namespace {
 // Given a predicate info that is a type of branching terminator, get the
 // branching block.
 const BasicBlock *getBranchBlock(const PredicateBase *PB) {
   assert(isa<PredicateWithEdge>(PB) &&
          "Only branches and switches should have PHIOnly defs that "
          "require branch blocks.");
   return cast<PredicateWithEdge>(PB)->From;
if (auto *I = dyn_cast<Instruction>(U.getUser())) {
       VD.DFSIn = DomNode->getDFSNumIn();
       VD.DFSOut = DomNode->getDFSNumOut();
       VD.U = &U;
       DFSOrderedSet.push_back(VD);
     }
   }
 }
 
+bool shouldRename(Value *V) {
+  // 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.
+  return (isa<Instruction>(V) || isa<Argument>(V)) && !V->hasOneUse();
+}
+
 // 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.
-  //
-  if ((isa<Instruction>(Op0) || isa<Argument>(Op0)) && !Op0->hasOneUse())
-    CmpOperands.push_back(Op0);
-  if ((isa<Instruction>(Op1) || isa<Argument>(Op1)) && !Op1->hasOneUse())
-    CmpOperands.push_back(Op1);
+
 }
 
 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
 void PredicateInfoBuilder::addInfoFor(SmallVectorImpl<Value *> &OpsToRename,
                                       Value *Op, PredicateBase *PB) {
   auto &OperandInfo = getOrCreateValueInfo(Op);
   if (OperandInfo.Infos.empty())
     OpsToRename.push_back(Op);
   PI.AllInfos.push_back(PB);
   OperandInfo.Infos.push_back(PB);
 }
 
 // Process an assume instruction and place relevant operations we want to rename
 // into OpsToRename.
 void PredicateInfoBuilder::processAssume(
     IntrinsicInst *II, BasicBlock *AssumeBB,
     SmallVectorImpl<Value *> &OpsToRename) {
-  // See if we have a comparison we support
-  SmallVector<Value *, 8> CmpOperands;
-  SmallVector<Value *, 2> ConditionsToProcess;
-  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))) {
-    ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(0));
-    ConditionsToProcess.push_back(cast<BinaryOperator>(Operand)->getOperand(1));
-    ConditionsToProcess.push_back(Operand);
-  } else if (isa<CmpInst>(Operand)) {
-
-    ConditionsToProcess.push_back(Operand);
+  SmallVector<Value *, 4> Worklist;
+  SmallPtrSet<Value *, 4> Visited;
+  Worklist.push_back(II->getOperand(0));
+  while (!Worklist.empty()) {
+    Value *Cond = Worklist.pop_back_val();
+    if (!Visited.insert(Cond).second)
+      continue;
+    if (Visited.size() > MaxCondsPerBranch)
+      break;
+
+    Value *Op0, *Op1;
+    if (match(Cond, m_And(m_Value(Op0), m_Value(Op1)))) {
+      Worklist.push_back(Op1);
+      Worklist.push_back(Op0);
     }
-  for (auto Cond : ConditionsToProcess) {
-    if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
-      collectCmpOps(Cmp, CmpOperands);
-      // Now add our copy infos for our operands
-      for (auto *Op : CmpOperands) {
-        auto *PA = new PredicateAssume(Op, II, Cmp);
-        addInfoFor(OpsToRename, Op, PA);
-      }
-      CmpOperands.clear();
-    } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
-      // Otherwise, it should be an AND.
-      assert(BinOp->getOpcode() == Instruction::And &&
-             "Should have been an AND");
-      auto *PA = new PredicateAssume(BinOp, II, BinOp);
-      addInfoFor(OpsToRename, BinOp, PA);
-    } else {
-      llvm_unreachable("Unknown type of condition");
+
+    SmallVector<Value *, 4> Values;
+    Values.push_back(Cond);
+    if (auto *Cmp = dyn_cast<CmpInst>(Cond))
+      collectCmpOps(Cmp, Values);
+
+    for (Value *V : Values) {
+      if (shouldRename(V)) {
+        auto *PA = new PredicateAssume(V, II, Cond);
+        addInfoFor(OpsToRename, V, PA);
+      }
     }
   }
 }
 
 // Process a block terminating branch, and place relevant operations to be
 // renamed into OpsToRename.
 void PredicateInfoBuilder::processBranch(
     BranchInst *BI, BasicBlock *BranchBB,
     SmallVectorImpl<Value *> &OpsToRename) {
   BasicBlock *FirstBB = BI->getSuccessor(0);
   BasicBlock *SecondBB = BI->getSuccessor(1);
-  SmallVector<BasicBlock *, 2> SuccsToProcess;
-  SuccsToProcess.push_back(FirstBB);
-  SuccsToProcess.push_back(SecondBB);
-  SmallVector<Value *, 2> ConditionsToProcess;
 
-  auto InsertHelper = [&](Value *Op, bool isAnd, bool isOr, Value *Cond) {
-    for (auto *Succ : SuccsToProcess) {
-      // Don't try to insert on a self-edge. This is mainly because we will
-      // eliminate during renaming anyway.
-      if (Succ == BranchBB)
-        continue;
-      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))
+  for (BasicBlock *Succ : {FirstBB, SecondBB}) {
+    bool TakenEdge = Succ == FirstBB;
+
+    SmallVector<Value *, 4> Worklist;
+    SmallPtrSet<Value *, 4> Visited;
+    Worklist.push_back(BI->getCondition());
+    while (!Worklist.empty()) {
+      Value *Cond = Worklist.pop_back_val();
+      if (!Visited.insert(Cond).second)
         continue;
+      if (Visited.size() > MaxCondsPerBranch)
+        break;
+
+      Value *Op0, *Op1;
+      if (TakenEdge ? match(Cond, m_And(m_Value(Op0), m_Value(Op1)))
+                    : match(Cond, m_Or(m_Value(Op0), m_Value(Op1)))) {
+        Worklist.push_back(Op1);
+        Worklist.push_back(Op0);
+      }
+
+      SmallVector<Value *, 4> Values;
+      Values.push_back(Cond);
+      if (auto *Cmp = dyn_cast<CmpInst>(Cond))
+        collectCmpOps(Cmp, Values);
+
+      for (Value *V : Values) {
+        if (shouldRename(V)) {
           PredicateBase *PB =
-          new PredicateBranch(Op, BranchBB, Succ, Cond, TakenEdge);
-      addInfoFor(OpsToRename, Op, PB);
+              new PredicateBranch(V, BranchBB, Succ, Cond, TakenEdge);
+          addInfoFor(OpsToRename, V, PB);
           if (!Succ->getSinglePredecessor())
             EdgeUsesOnly.insert({BranchBB, Succ});
         }
-  };
-
-  // Match combinations of conditions.
-  CmpInst::Predicate Pred;
-  bool isAnd = false;
-  bool isOr = false;
-  SmallVector<Value *, 8> CmpOperands;
-  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;
-    ConditionsToProcess.push_back(BinOp->getOperand(0));
-    ConditionsToProcess.push_back(BinOp->getOperand(1));
-    ConditionsToProcess.push_back(BI->getCondition());
-  } else if (isa<CmpInst>(BI->getCondition())) {
-    ConditionsToProcess.push_back(BI->getCondition());
-  }
-  for (auto Cond : ConditionsToProcess) {
-    if (auto *Cmp = dyn_cast<CmpInst>(Cond)) {
-      collectCmpOps(Cmp, CmpOperands);
-      // Now add our copy infos for our operands
-      for (auto *Op : CmpOperands)
-        InsertHelper(Op, isAnd, isOr, Cmp);
-    } else if (auto *BinOp = dyn_cast<BinaryOperator>(Cond)) {
-      // This must be an AND or an OR.
-      assert((BinOp->getOpcode() == Instruction::And ||
-              BinOp->getOpcode() == Instruction::Or) &&
-             "Should have been an AND or an OR");
-      // The actual value of the binop is not subject to the same restrictions
-      // as the comparison. It's either true or false on the true/false branch.
-      InsertHelper(BinOp, false, false, BinOp);
-    } else {
-      llvm_unreachable("Unknown type of condition");
       }
-    CmpOperands.clear();
+    }
   }
 }
 // Process a block terminating switch, and place relevant operations to be
 // renamed into OpsToRename.
 void PredicateInfoBuilder::processSwitch(
     SwitchInst *SI, BasicBlock *BranchBB,
     SmallVectorImpl<Value *> &OpsToRename) {
   Value *Op = SI->getCondition();

llvm/test/Transforms/NewGVN/assume-equal.ll

 ; This test checks if GVN can do the constant propagation correctly
 ; when there are multiple uses of the same assume value in the
 ; basic block that has a loop back-edge pointing to itself.
 define i32 @_Z1il(i32 %val, i1 %k) {
 ; CHECK-LABEL: @_Z1il(
 ; CHECK-NEXT:    br label [[NEXT:%.*]]
 ; CHECK:       next:
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[K:%.*]])
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[K]])
+; CHECK-NEXT:    tail call void @llvm.assume(i1 true)
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[VAL:%.*]], 50
 ; CHECK-NEXT:    br i1 [[CMP]], label [[NEXT]], label [[MEH:%.*]]
 ; CHECK:       meh:
 ; CHECK-NEXT:    ret i32 0
 ;
   br label %next
 
 next:

 ; This test checks if GVN can prevent the constant propagation correctly
 ; in the successor blocks that are not dominated by the basic block
 ; with the assume instruction.
 define i1 @_z1im(i32 %val, i1 %k, i1 %j) {
 ; CHECK-LABEL: @_z1im(
 ; CHECK-NEXT:    br i1 [[J:%.*]], label [[NEXT:%.*]], label [[MEH:%.*]]
 ; CHECK:       next:
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[K:%.*]])
-; CHECK-NEXT:    tail call void @llvm.assume(i1 [[K]])
+; CHECK-NEXT:    tail call void @llvm.assume(i1 true)
 ; CHECK-NEXT:    br label [[MEH]]
 ; CHECK:       meh:
 ; CHECK-NEXT:    ret i1 [[K]]
 ;
   br i1 %j, label %next, label %meh
 
 next:
   tail call void @llvm.assume(i1 %k)
   tail call void @llvm.assume(i1 %k)
   br label %meh
 
 meh:
   ret i1 %k
 }
 
 declare void @llvm.assume(i1)

llvm/test/Transforms/SCCP/conditions-ranges.ll

;       %a should be in in [100, 21)
   ; Conditions below cannot be simplified.
   %c.4 = icmp eq i32 %a, 10
   call void @use(i1 %c.4)
   %c.5 = icmp eq i32 %b, 100
   call void @use(i1 %c.5)
   ret void
 }
 
-; TODO: Currently only the information of the AND used as branch condition is
-; used.
 define void @f18_conditions_chained_and(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f18_conditions_chained_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LT:%.*]] = icmp ult i32 [[A:%.*]], 100
 ; CHECK-NEXT:    [[GT:%.*]] = icmp ugt i32 [[A]], 20
 ; CHECK-NEXT:    [[BC:%.*]] = and i1 [[LT]], [[GT]]
 ; CHECK-NEXT:    [[B_LT:%.*]] = icmp ult i32 [[B:%.*]], 50
 ; CHECK-NEXT:    [[BC_2:%.*]] = and i1 [[BC]], [[B_LT]]
 ; CHECK-NEXT:    br i1 [[BC_2]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[A]], 0
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i32 [[A]], 20
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
-; CHECK-NEXT:    [[F_3:%.*]] = icmp ugt i32 [[A]], 100
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
-; CHECK-NEXT:    [[F_4:%.*]] = icmp ugt i32 [[B]], 100
-; CHECK-NEXT:    call void @use(i1 [[F_4]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ult i32 [[A]], 100
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ne i32 [[A]], 20
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[A]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[A]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[A]], 50
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i32 [[B]], 0
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])

 ; CHECK-NEXT:    call void @use(i1 [[C_7]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %lt = icmp ult i32 %a, 100
   %gt = icmp ugt i32 %a, 20
   %bc = and i1 %lt, %gt
   %b.lt = icmp ult i32 %b, 50
   %bc.2 = and i1 %bc, %b.lt
   br i1 %bc.2, label %true, label %false
 
 true: ; %a in [21, 100)
   ; Conditions below are false.
   %f.1 = icmp eq i32 %a, 0
   call void @use(i1 %f.1)
   %f.2 = icmp eq i32 %a, 20
   call void @use(i1 %f.2)

llvm/test/Transforms/Util/PredicateInfo/condprop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -print-predicateinfo < %s 2>&1 | FileCheck %s
+; RUN: opt -print-predicateinfo -disable-output < %s 2>&1 | 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

 declare void @foo(i1)
 declare void @bar(i32)
 
 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:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[XZ]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
 ; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[YZ]])
 ; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[Y]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK-NEXT:    br i1 [[Z]], label [[BOTH_ZERO:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both_zero:
 ; 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-LABEL: @test4(
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[SW:%.*]], label [[CASE3:%.*]]
 ; CHECK:       sw:
 ; CHECK:         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:    ] Edge: [label [[SW]],label %case1]
-; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X:%.*]])
+; CHECK-NEXT:    ] Edge: [label [[SW]],label %case1], RenamedOp: [[X:%.*]] }
+; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
 ; 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:

llvm/test/Transforms/Util/PredicateInfo/testandor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -print-predicateinfo -disable-output < %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:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[XZ]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
 ; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[YZ]])
 ; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[Y]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; 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:
neither:
   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:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[XZ]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
 ; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[YZ]])
 ; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[Y]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both:
 ; 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:
;; Should not insert on the false edge for and
   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:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK:         [[XGT_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[XGT]])
 ; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
 ; CHECK:         [[X_0_1:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X_0]])
 ; CHECK:         [[XLT_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[XLT]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both:
 ; 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]])

 }
 
 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-NEXT:    call void @llvm.assume(i1 [[Z]])
-; CHECK:         [[TMP1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
-; CHECK:         [[TMP2:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[Y]])
-; CHECK:         [[TMP3:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[YZ]])
-; CHECK:         [[TMP4:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
-; CHECK:         [[TMP5:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[XZ]])
+; CHECK:         [[TMP1:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[Y]])
+; CHECK:         [[TMP2:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[YZ]])
+; CHECK:         [[TMP3:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
+; CHECK:         [[TMP4:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[XZ]])
+; CHECK:         [[TMP5:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
 ; CHECK:         [[DOT0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[TMP5]])
-; CHECK:         [[DOT01:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[TMP4]])
-; CHECK:         [[DOT02:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[TMP3]])
-; CHECK:         [[DOT03:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[TMP2]])
-; CHECK:         [[DOT04:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[TMP1]])
-; CHECK-NEXT:    br i1 [[TMP1]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:         [[DOT01:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[TMP4]])
+; CHECK:         [[DOT02:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[TMP3]])
+; CHECK:         [[DOT03:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[TMP2]])
+; CHECK:         [[DOT04:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[TMP1]])
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BOTH:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both:
-; 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:    call void @foo(i1 [[DOT01]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT03]])
+; CHECK-NEXT:    call void @bar(i32 [[DOT02]])
+; CHECK-NEXT:    call void @bar(i32 [[DOT04]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       nope:
-; CHECK-NEXT:    call void @foo(i1 [[DOT04]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT0]])
 ; 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:

 ;; 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:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
-; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
+; CHECK:         [[TMP1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[Z]])
+; CHECK:         [[DOT0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[TMP1]])
+; CHECK-NEXT:    br i1 [[TMP1]], 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_0]])
+; CHECK-NEXT:    call void @foo(i1 [[DOT0]])
 ; 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
 }
 
 define void @test_and_one_unknown_cond(i32 %x, i1 %c1) {
 ; CHECK-LABEL: @test_and_one_unknown_cond(
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[A:%.*]] = and i1 [[C1:%.*]], [[C2]]
+; CHECK:         [[A_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A]])
+; CHECK:         [[A_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A]])
+; CHECK:         [[C1_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C1]])
+; CHECK:         [[C2_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C2]])
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
 ; CHECK-NEXT:    br i1 [[A]], label [[BOTH:%.*]], label [[NOPE:%.*]]
 ; CHECK:       both:
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    call void @foo(i1 [[C1]])
-; CHECK-NEXT:    call void @foo(i1 [[C2]])
-; CHECK-NEXT:    call void @foo(i1 [[A]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
+; CHECK-NEXT:    call void @foo(i1 [[C1_0]])
+; CHECK-NEXT:    call void @foo(i1 [[C2_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       nope:
 ; CHECK-NEXT:    call void @bar(i32 [[X]])
 ; CHECK-NEXT:    call void @foo(i1 [[C1]])
 ; CHECK-NEXT:    call void @foo(i1 [[C2]])
-; CHECK-NEXT:    call void @foo(i1 [[A]])
+; CHECK-NEXT:    call void @foo(i1 [[A_1]])
 ; CHECK-NEXT:    ret void
 ;
   %c2 = icmp eq i32 %x, 0
   %a = and i1 %c1, %c2
   br i1 %a, label %both, label %nope
 
 both:
   call void @bar(i32 %x)
nope:
   call void @foo(i1 %a)
   ret void
 }
 
 define void @test_or_one_unknown_cond(i32 %x, i1 %c1) {
 ; CHECK-LABEL: @test_or_one_unknown_cond(
 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[A:%.*]] = or i1 [[C1:%.*]], [[C2]]
+; CHECK:         [[A_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A]])
+; CHECK:         [[A_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A]])
+; CHECK:         [[C1_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C1]])
+; CHECK:         [[C2_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C2]])
+; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.{{.+}}(i32 [[X]])
 ; CHECK-NEXT:    br i1 [[A]], label [[NOPE:%.*]], label [[BOTH_INVERTED:%.*]]
 ; CHECK:       both_inverted:
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    call void @foo(i1 [[C1]])
-; CHECK-NEXT:    call void @foo(i1 [[C2]])
-; CHECK-NEXT:    call void @foo(i1 [[A]])
+; CHECK-NEXT:    call void @bar(i32 [[X_0]])
+; CHECK-NEXT:    call void @foo(i1 [[C1_0]])
+; CHECK-NEXT:    call void @foo(i1 [[C2_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A_1]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       nope:
 ; CHECK-NEXT:    call void @bar(i32 [[X]])
 ; CHECK-NEXT:    call void @foo(i1 [[C1]])
 ; CHECK-NEXT:    call void @foo(i1 [[C2]])
-; CHECK-NEXT:    call void @foo(i1 [[A]])
+; CHECK-NEXT:    call void @foo(i1 [[A_0]])
 ; CHECK-NEXT:    ret void
 ;
   %c2 = icmp eq i32 %x, 0
   %a = or i1 %c1, %c2
   br i1 %a, label %nope, label %both_inverted
 
 both_inverted:
   call void @bar(i32 %x)
nope:
   call void @foo(i1 %a)
   ret void
 }
 
 define void @test_and_chain(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test_and_chain(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[AND1]], [[C:%.*]]
+; CHECK:         [[AND2_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[AND2]])
+; CHECK:         [[AND2_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[AND2]])
+; CHECK:         [[AND1_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[AND1]])
+; CHECK:         [[A_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A]])
+; CHECK:         [[B_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[B]])
+; CHECK:         [[C_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C]])
 ; CHECK-NEXT:    br i1 [[AND2]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    call void @foo(i1 [[A]])
-; CHECK-NEXT:    call void @foo(i1 [[B]])
-; CHECK-NEXT:    call void @foo(i1 [[C]])
-; CHECK-NEXT:    call void @foo(i1 [[AND1]])
-; CHECK-NEXT:    call void @foo(i1 [[AND2]])
+; CHECK-NEXT:    call void @foo(i1 [[A_0]])
+; CHECK-NEXT:    call void @foo(i1 [[B_0]])
+; CHECK-NEXT:    call void @foo(i1 [[C_0]])
+; CHECK-NEXT:    call void @foo(i1 [[AND1_0]])
+; CHECK-NEXT:    call void @foo(i1 [[AND2_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @foo(i1 [[A]])
 ; CHECK-NEXT:    call void @foo(i1 [[B]])
 ; CHECK-NEXT:    call void @foo(i1 [[C]])
 ; CHECK-NEXT:    call void @foo(i1 [[AND1]])
-; CHECK-NEXT:    call void @foo(i1 [[AND2]])
+; CHECK-NEXT:    call void @foo(i1 [[AND2_1]])
 ; CHECK-NEXT:    ret void
 ;
   %and1 = and i1 %a, %b
   %and2 = and i1 %and1, %c
   br i1 %and2, label %if, label %else
 
 if:
   call void @foo(i1 %a)
else:
   call void @foo(i1 %and2)
   ret void
 }
 
 define void @test_or_chain(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test_or_chain(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i1 [[OR1]], [[C:%.*]]
+; CHECK:         [[OR2_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[OR2]])
+; CHECK:         [[OR2_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[OR2]])
+; CHECK:         [[OR1_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[OR1]])
+; CHECK:         [[A_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A]])
+; CHECK:         [[B_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[B]])
+; CHECK:         [[C_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C]])
 ; CHECK-NEXT:    br i1 [[OR2]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo(i1 [[A]])
 ; CHECK-NEXT:    call void @foo(i1 [[B]])
 ; CHECK-NEXT:    call void @foo(i1 [[C]])
 ; CHECK-NEXT:    call void @foo(i1 [[OR1]])
-; CHECK-NEXT:    call void @foo(i1 [[OR2]])
+; CHECK-NEXT:    call void @foo(i1 [[OR2_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
-; CHECK-NEXT:    call void @foo(i1 [[A]])
-; CHECK-NEXT:    call void @foo(i1 [[B]])
-; CHECK-NEXT:    call void @foo(i1 [[C]])
-; CHECK-NEXT:    call void @foo(i1 [[OR1]])
-; CHECK-NEXT:    call void @foo(i1 [[OR2]])
+; CHECK-NEXT:    call void @foo(i1 [[A_0]])
+; CHECK-NEXT:    call void @foo(i1 [[B_0]])
+; CHECK-NEXT:    call void @foo(i1 [[C_0]])
+; CHECK-NEXT:    call void @foo(i1 [[OR1_0]])
+; CHECK-NEXT:    call void @foo(i1 [[OR2_1]])
 ; CHECK-NEXT:    ret void
 ;
   %or1 = or i1 %a, %b
   %or2 = or i1 %or1, %c
   br i1 %or2, label %if, label %else
 
 if:
   call void @foo(i1 %a)
else:
   call void @foo(i1 %or2)
   ret void
 }
 
 define void @test_and_or_mixed(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test_and_or_mixed(
 ; CHECK-NEXT:    [[OR:%.*]] = or i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[OR]], [[C:%.*]]
+; CHECK:         [[AND_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[AND]])
+; CHECK:         [[AND_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[AND]])
+; CHECK:         [[OR_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[OR]])
+; CHECK:         [[C_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C]])
 ; CHECK-NEXT:    br i1 [[AND]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo(i1 [[A]])
 ; CHECK-NEXT:    call void @foo(i1 [[B]])
-; CHECK-NEXT:    call void @foo(i1 [[C]])
-; CHECK-NEXT:    call void @foo(i1 [[OR]])
-; CHECK-NEXT:    call void @foo(i1 [[AND]])
+; CHECK-NEXT:    call void @foo(i1 [[C_0]])
+; CHECK-NEXT:    call void @foo(i1 [[OR_0]])
+; CHECK-NEXT:    call void @foo(i1 [[AND_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @foo(i1 [[A]])
 ; CHECK-NEXT:    call void @foo(i1 [[B]])
 ; CHECK-NEXT:    call void @foo(i1 [[C]])
 ; CHECK-NEXT:    call void @foo(i1 [[OR]])
-; CHECK-NEXT:    call void @foo(i1 [[AND]])
+; CHECK-NEXT:    call void @foo(i1 [[AND_1]])
 ; CHECK-NEXT:    ret void
 ;
   %or = or i1 %a, %b
   %and = and i1 %or, %c
   br i1 %and, label %if, label %else
 
 if:
   call void @foo(i1 %a)

 ; CHECK-NEXT:    [[A8:%.*]] = and i1 [[A7]], true
 ; CHECK-NEXT:    [[A9:%.*]] = and i1 [[A8]], true
 ; CHECK-NEXT:    [[A10:%.*]] = and i1 [[A9]], true
 ; CHECK-NEXT:    [[A11:%.*]] = and i1 [[A10]], true
 ; CHECK-NEXT:    [[A12:%.*]] = and i1 [[A11]], true
 ; CHECK-NEXT:    [[A13:%.*]] = and i1 [[A12]], true
 ; CHECK-NEXT:    [[A14:%.*]] = and i1 [[A13]], true
 ; CHECK-NEXT:    [[A15:%.*]] = and i1 [[A14]], true
+; CHECK:         [[A15_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A15]])
+; CHECK:         [[A15_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A15]])
+; CHECK:         [[A14_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A14]])
+; CHECK:         [[A13_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A13]])
+; CHECK:         [[A12_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A12]])
+; CHECK:         [[A11_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A11]])
+; CHECK:         [[A10_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A10]])
+; CHECK:         [[A9_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A9]])
+; CHECK:         [[A8_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A8]])
 ; CHECK-NEXT:    br i1 [[A15]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo(i1 [[A1]])
 ; CHECK-NEXT:    call void @foo(i1 [[A2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A3]])
 ; CHECK-NEXT:    call void @foo(i1 [[A4]])
-; CHECK-NEXT:    call void @foo(i1 [[A4]])
 ; CHECK-NEXT:    call void @foo(i1 [[A5]])
 ; CHECK-NEXT:    call void @foo(i1 [[A6]])
 ; CHECK-NEXT:    call void @foo(i1 [[A7]])
-; CHECK-NEXT:    call void @foo(i1 [[A8]])
-; CHECK-NEXT:    call void @foo(i1 [[A9]])
-; CHECK-NEXT:    call void @foo(i1 [[A10]])
-; CHECK-NEXT:    call void @foo(i1 [[A11]])
-; CHECK-NEXT:    call void @foo(i1 [[A12]])
-; CHECK-NEXT:    call void @foo(i1 [[A13]])
-; CHECK-NEXT:    call void @foo(i1 [[A14]])
-; CHECK-NEXT:    call void @foo(i1 [[A15]])
+; CHECK-NEXT:    call void @foo(i1 [[A8_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A9_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A10_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A11_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A12_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A13_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A14_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A15_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @foo(i1 [[A1]])
 ; CHECK-NEXT:    call void @foo(i1 [[A2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A3]])
 ; CHECK-NEXT:    call void @foo(i1 [[A4]])
-; CHECK-NEXT:    call void @foo(i1 [[A4]])
 ; CHECK-NEXT:    call void @foo(i1 [[A5]])
 ; CHECK-NEXT:    call void @foo(i1 [[A6]])
 ; CHECK-NEXT:    call void @foo(i1 [[A7]])
 ; CHECK-NEXT:    call void @foo(i1 [[A8]])
 ; CHECK-NEXT:    call void @foo(i1 [[A9]])
 ; CHECK-NEXT:    call void @foo(i1 [[A10]])
 ; CHECK-NEXT:    call void @foo(i1 [[A11]])
 ; CHECK-NEXT:    call void @foo(i1 [[A12]])
 ; CHECK-NEXT:    call void @foo(i1 [[A13]])
 ; CHECK-NEXT:    call void @foo(i1 [[A14]])
-; CHECK-NEXT:    call void @foo(i1 [[A15]])
+; CHECK-NEXT:    call void @foo(i1 [[A15_1]])
 ; CHECK-NEXT:    ret void
 ;
   %a2 = and i1 %a1, true
   %a3 = and i1 %a2, true
   %a4 = and i1 %a3, true
   %a5 = and i1 %a4, true
   %a6 = and i1 %a5, true
   %a7 = and i1 %a6, true
   %a8 = and i1 %a7, true
   %a9 = and i1 %a8, true
   %a10 = and i1 %a9, true
   %a11 = and i1 %a10, true
   %a12 = and i1 %a11, true
   %a13 = and i1 %a12, true
   %a14 = and i1 %a13, true
   %a15 = and i1 %a14, true
   br i1 %a15, label %if, label %else
 
 if:
   call void @foo(i1 %a1)
   call void @foo(i1 %a2)
   call void @foo(i1 %a3)
   call void @foo(i1 %a4)
-  call void @foo(i1 %a4)
   call void @foo(i1 %a5)
   call void @foo(i1 %a6)
   call void @foo(i1 %a7)
   call void @foo(i1 %a8)
   call void @foo(i1 %a9)
   call void @foo(i1 %a10)
   call void @foo(i1 %a11)
   call void @foo(i1 %a12)
   call void @foo(i1 %a13)
   call void @foo(i1 %a14)
   call void @foo(i1 %a15)
   ret void
 
 else:
   call void @foo(i1 %a1)
   call void @foo(i1 %a2)
   call void @foo(i1 %a3)
   call void @foo(i1 %a4)
-  call void @foo(i1 %a4)
   call void @foo(i1 %a5)
   call void @foo(i1 %a6)
   call void @foo(i1 %a7)
   call void @foo(i1 %a8)
   call void @foo(i1 %a9)
   call void @foo(i1 %a10)
   call void @foo(i1 %a11)
   call void @foo(i1 %a12)

 ; CHECK-NEXT:    [[A8:%.*]] = and i1 [[A7]], [[A7]]
 ; CHECK-NEXT:    [[A9:%.*]] = and i1 [[A8]], [[A8]]
 ; CHECK-NEXT:    [[A10:%.*]] = and i1 [[A9]], [[A9]]
 ; CHECK-NEXT:    [[A11:%.*]] = and i1 [[A10]], [[A10]]
 ; CHECK-NEXT:    [[A12:%.*]] = and i1 [[A11]], [[A11]]
 ; CHECK-NEXT:    [[A13:%.*]] = and i1 [[A12]], [[A12]]
 ; CHECK-NEXT:    [[A14:%.*]] = and i1 [[A13]], [[A13]]
 ; CHECK-NEXT:    [[A15:%.*]] = and i1 [[A14]], [[A14]]
+; CHECK:         [[A15_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A15]])
+; CHECK:         [[A15_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A15]])
+; CHECK:         [[A14_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A14]])
+; CHECK:         [[A13_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A13]])
+; CHECK:         [[A12_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A12]])
+; CHECK:         [[A11_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A11]])
+; CHECK:         [[A10_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A10]])
+; CHECK:         [[A9_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A9]])
+; CHECK:         [[A8_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A8]])
 ; CHECK-NEXT:    br i1 [[A15]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo(i1 [[A1]])
 ; CHECK-NEXT:    call void @foo(i1 [[A2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A3]])
 ; CHECK-NEXT:    call void @foo(i1 [[A4]])
-; CHECK-NEXT:    call void @foo(i1 [[A4]])
 ; CHECK-NEXT:    call void @foo(i1 [[A5]])
 ; CHECK-NEXT:    call void @foo(i1 [[A6]])
 ; CHECK-NEXT:    call void @foo(i1 [[A7]])
-; CHECK-NEXT:    call void @foo(i1 [[A8]])
-; CHECK-NEXT:    call void @foo(i1 [[A9]])
-; CHECK-NEXT:    call void @foo(i1 [[A10]])
-; CHECK-NEXT:    call void @foo(i1 [[A11]])
-; CHECK-NEXT:    call void @foo(i1 [[A12]])
-; CHECK-NEXT:    call void @foo(i1 [[A13]])
-; CHECK-NEXT:    call void @foo(i1 [[A14]])
-; CHECK-NEXT:    call void @foo(i1 [[A15]])
+; CHECK-NEXT:    call void @foo(i1 [[A8_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A9_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A10_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A11_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A12_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A13_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A14_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A15_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @foo(i1 [[A1]])
 ; CHECK-NEXT:    call void @foo(i1 [[A2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A3]])
 ; CHECK-NEXT:    call void @foo(i1 [[A4]])
-; CHECK-NEXT:    call void @foo(i1 [[A4]])
 ; CHECK-NEXT:    call void @foo(i1 [[A5]])
 ; CHECK-NEXT:    call void @foo(i1 [[A6]])
 ; CHECK-NEXT:    call void @foo(i1 [[A7]])
 ; CHECK-NEXT:    call void @foo(i1 [[A8]])
 ; CHECK-NEXT:    call void @foo(i1 [[A9]])
 ; CHECK-NEXT:    call void @foo(i1 [[A10]])
 ; CHECK-NEXT:    call void @foo(i1 [[A11]])
 ; CHECK-NEXT:    call void @foo(i1 [[A12]])
 ; CHECK-NEXT:    call void @foo(i1 [[A13]])
 ; CHECK-NEXT:    call void @foo(i1 [[A14]])
-; CHECK-NEXT:    call void @foo(i1 [[A15]])
+; CHECK-NEXT:    call void @foo(i1 [[A15_1]])
 ; CHECK-NEXT:    ret void
 ;
   %a2 = and i1 %a1, %a1
   %a3 = and i1 %a2, %a2
   %a4 = and i1 %a3, %a3
   %a5 = and i1 %a4, %a4
   %a6 = and i1 %a5, %a5
   %a7 = and i1 %a6, %a6
   %a8 = and i1 %a7, %a7
   %a9 = and i1 %a8, %a8
   %a10 = and i1 %a9, %a9
   %a11 = and i1 %a10, %a10
   %a12 = and i1 %a11, %a11
   %a13 = and i1 %a12, %a12
   %a14 = and i1 %a13, %a13
   %a15 = and i1 %a14, %a14
   br i1 %a15, label %if, label %else
 
 if:
   call void @foo(i1 %a1)
   call void @foo(i1 %a2)
   call void @foo(i1 %a3)
   call void @foo(i1 %a4)
-  call void @foo(i1 %a4)
   call void @foo(i1 %a5)
   call void @foo(i1 %a6)
   call void @foo(i1 %a7)
   call void @foo(i1 %a8)
   call void @foo(i1 %a9)
   call void @foo(i1 %a10)
   call void @foo(i1 %a11)
   call void @foo(i1 %a12)
   call void @foo(i1 %a13)
   call void @foo(i1 %a14)
   call void @foo(i1 %a15)
   ret void
 
 else:
   call void @foo(i1 %a1)
   call void @foo(i1 %a2)
   call void @foo(i1 %a3)
   call void @foo(i1 %a4)
-  call void @foo(i1 %a4)
   call void @foo(i1 %a5)
   call void @foo(i1 %a6)
   call void @foo(i1 %a7)
   call void @foo(i1 %a8)
   call void @foo(i1 %a9)
   call void @foo(i1 %a10)
   call void @foo(i1 %a11)
   call void @foo(i1 %a12)

 ; CHECK-NEXT:    [[A8:%.*]] = or i1 [[A7]], [[A7]]
 ; CHECK-NEXT:    [[A9:%.*]] = or i1 [[A8]], [[A8]]
 ; CHECK-NEXT:    [[A10:%.*]] = or i1 [[A9]], [[A9]]
 ; CHECK-NEXT:    [[A11:%.*]] = or i1 [[A10]], [[A10]]
 ; CHECK-NEXT:    [[A12:%.*]] = or i1 [[A11]], [[A11]]
 ; CHECK-NEXT:    [[A13:%.*]] = or i1 [[A12]], [[A12]]
 ; CHECK-NEXT:    [[A14:%.*]] = or i1 [[A13]], [[A13]]
 ; CHECK-NEXT:    [[A15:%.*]] = or i1 [[A14]], [[A14]]
+; CHECK:         [[A15_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A15]])
+; CHECK:         [[A15_1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A15]])
+; CHECK:         [[A14_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A14]])
+; CHECK:         [[A13_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A13]])
+; CHECK:         [[A12_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A12]])
+; CHECK:         [[A11_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A11]])
+; CHECK:         [[A10_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A10]])
+; CHECK:         [[A9_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A9]])
+; CHECK:         [[A8_0:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A8]])
 ; CHECK-NEXT:    br i1 [[A15]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo(i1 [[A1]])
 ; CHECK-NEXT:    call void @foo(i1 [[A2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A3]])
 ; CHECK-NEXT:    call void @foo(i1 [[A4]])
-; CHECK-NEXT:    call void @foo(i1 [[A4]])
 ; CHECK-NEXT:    call void @foo(i1 [[A5]])
 ; CHECK-NEXT:    call void @foo(i1 [[A6]])
 ; CHECK-NEXT:    call void @foo(i1 [[A7]])
 ; CHECK-NEXT:    call void @foo(i1 [[A8]])
 ; CHECK-NEXT:    call void @foo(i1 [[A9]])
 ; CHECK-NEXT:    call void @foo(i1 [[A10]])
 ; CHECK-NEXT:    call void @foo(i1 [[A11]])
 ; CHECK-NEXT:    call void @foo(i1 [[A12]])
 ; CHECK-NEXT:    call void @foo(i1 [[A13]])
 ; CHECK-NEXT:    call void @foo(i1 [[A14]])
-; CHECK-NEXT:    call void @foo(i1 [[A15]])
+; CHECK-NEXT:    call void @foo(i1 [[A15_0]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
 ; CHECK-NEXT:    call void @foo(i1 [[A1]])
 ; CHECK-NEXT:    call void @foo(i1 [[A2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A3]])
 ; CHECK-NEXT:    call void @foo(i1 [[A4]])
-; CHECK-NEXT:    call void @foo(i1 [[A4]])
 ; CHECK-NEXT:    call void @foo(i1 [[A5]])
 ; CHECK-NEXT:    call void @foo(i1 [[A6]])
 ; CHECK-NEXT:    call void @foo(i1 [[A7]])
-; CHECK-NEXT:    call void @foo(i1 [[A8]])
-; CHECK-NEXT:    call void @foo(i1 [[A9]])
-; CHECK-NEXT:    call void @foo(i1 [[A10]])
-; CHECK-NEXT:    call void @foo(i1 [[A11]])
-; CHECK-NEXT:    call void @foo(i1 [[A12]])
-; CHECK-NEXT:    call void @foo(i1 [[A13]])
-; CHECK-NEXT:    call void @foo(i1 [[A14]])
-; CHECK-NEXT:    call void @foo(i1 [[A15]])
+; CHECK-NEXT:    call void @foo(i1 [[A8_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A9_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A10_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A11_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A12_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A13_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A14_0]])
+; CHECK-NEXT:    call void @foo(i1 [[A15_1]])
 ; CHECK-NEXT:    ret void
 ;
   %a2 = or i1 %a1, %a1
   %a3 = or i1 %a2, %a2
   %a4 = or i1 %a3, %a3
   %a5 = or i1 %a4, %a4
   %a6 = or i1 %a5, %a5
   %a7 = or i1 %a6, %a6
   %a8 = or i1 %a7, %a7
   %a9 = or i1 %a8, %a8
   %a10 = or i1 %a9, %a9
   %a11 = or i1 %a10, %a10
   %a12 = or i1 %a11, %a11
   %a13 = or i1 %a12, %a12
   %a14 = or i1 %a13, %a13
   %a15 = or i1 %a14, %a14
   br i1 %a15, label %if, label %else
 
 if:
   call void @foo(i1 %a1)
   call void @foo(i1 %a2)
   call void @foo(i1 %a3)
   call void @foo(i1 %a4)
-  call void @foo(i1 %a4)
   call void @foo(i1 %a5)
   call void @foo(i1 %a6)
   call void @foo(i1 %a7)
   call void @foo(i1 %a8)
   call void @foo(i1 %a9)
   call void @foo(i1 %a10)
   call void @foo(i1 %a11)
   call void @foo(i1 %a12)
   call void @foo(i1 %a13)
   call void @foo(i1 %a14)
   call void @foo(i1 %a15)
   ret void
 
 else:
   call void @foo(i1 %a1)
   call void @foo(i1 %a2)
   call void @foo(i1 %a3)
   call void @foo(i1 %a4)
-  call void @foo(i1 %a4)
   call void @foo(i1 %a5)
   call void @foo(i1 %a6)
   call void @foo(i1 %a7)
   call void @foo(i1 %a8)
   call void @foo(i1 %a9)
   call void @foo(i1 %a10)
   call void @foo(i1 %a11)
   call void @foo(i1 %a12)
   call void @foo(i1 %a13)
   call void @foo(i1 %a14)
   call void @foo(i1 %a15)
   ret void
 }
 
 define void @test_assume_and_chain(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test_assume_and_chain(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[AND1]], [[C:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[AND2]])
-; CHECK-NEXT:    call void @foo(i1 [[A]])
-; CHECK-NEXT:    call void @foo(i1 [[B]])
-; CHECK-NEXT:    call void @foo(i1 [[C]])
-; CHECK-NEXT:    call void @foo(i1 [[AND1]])
-; CHECK-NEXT:    call void @foo(i1 [[AND2]])
+; CHECK:         [[TMP1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[C]])
+; CHECK:         [[TMP2:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[B]])
+; CHECK:         [[TMP3:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A]])
+; CHECK:         [[TMP4:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[AND1]])
+; CHECK:         [[TMP5:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[AND2]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP3]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP2]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP1]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP4]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP5]])
 ; CHECK-NEXT:    ret void
 ;
   %and1 = and i1 %a, %b
   %and2 = and i1 %and1, %c
   call void @llvm.assume(i1 %and2)
   call void @foo(i1 %a)
   call void @foo(i1 %b)
   call void @foo(i1 %c)
   call void @foo(i1 %and1)
   call void @foo(i1 %and2)
   ret void
 }
 
 define void @test_assume_or_chain(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test_assume_or_chain(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i1 [[OR1]], [[C:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[OR2]])
+; CHECK:         [[TMP1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[OR2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A]])
 ; CHECK-NEXT:    call void @foo(i1 [[B]])
 ; CHECK-NEXT:    call void @foo(i1 [[C]])
 ; CHECK-NEXT:    call void @foo(i1 [[OR1]])
-; CHECK-NEXT:    call void @foo(i1 [[OR2]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP1]])
 ; CHECK-NEXT:    ret void
 ;
   %or1 = or i1 %a, %b
   %or2 = or i1 %or1, %c
   call void @llvm.assume(i1 %or2)
   call void @foo(i1 %a)
   call void @foo(i1 %b)
   call void @foo(i1 %c)

 ; CHECK-NEXT:    [[A9:%.*]] = and i1 [[A8]], [[A8]]
 ; CHECK-NEXT:    [[A10:%.*]] = and i1 [[A9]], [[A9]]
 ; CHECK-NEXT:    [[A11:%.*]] = and i1 [[A10]], [[A10]]
 ; CHECK-NEXT:    [[A12:%.*]] = and i1 [[A11]], [[A11]]
 ; CHECK-NEXT:    [[A13:%.*]] = and i1 [[A12]], [[A12]]
 ; CHECK-NEXT:    [[A14:%.*]] = and i1 [[A13]], [[A13]]
 ; CHECK-NEXT:    [[A15:%.*]] = and i1 [[A14]], [[A14]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[A15]])
+; CHECK:         [[TMP1:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A8]])
+; CHECK:         [[TMP2:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A9]])
+; CHECK:         [[TMP3:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A10]])
+; CHECK:         [[TMP4:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A11]])
+; CHECK:         [[TMP5:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A12]])
+; CHECK:         [[TMP6:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A13]])
+; CHECK:         [[TMP7:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A14]])
+; CHECK:         [[TMP8:%.*]] = call i1 @llvm.ssa.copy.{{.+}}(i1 [[A15]])
 ; CHECK-NEXT:    call void @foo(i1 [[A1]])
 ; CHECK-NEXT:    call void @foo(i1 [[A2]])
 ; CHECK-NEXT:    call void @foo(i1 [[A3]])
 ; CHECK-NEXT:    call void @foo(i1 [[A4]])
-; CHECK-NEXT:    call void @foo(i1 [[A4]])
 ; CHECK-NEXT:    call void @foo(i1 [[A5]])
 ; CHECK-NEXT:    call void @foo(i1 [[A6]])
 ; CHECK-NEXT:    call void @foo(i1 [[A7]])
-; CHECK-NEXT:    call void @foo(i1 [[A8]])
-; CHECK-NEXT:    call void @foo(i1 [[A9]])
-; CHECK-NEXT:    call void @foo(i1 [[A10]])
-; CHECK-NEXT:    call void @foo(i1 [[A11]])
-; CHECK-NEXT:    call void @foo(i1 [[A12]])
-; CHECK-NEXT:    call void @foo(i1 [[A13]])
-; CHECK-NEXT:    call void @foo(i1 [[A14]])
-; CHECK-NEXT:    call void @foo(i1 [[A15]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP1]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP2]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP3]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP4]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP5]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP6]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP7]])
+; CHECK-NEXT:    call void @foo(i1 [[TMP8]])
 ; CHECK-NEXT:    ret void
 ;
   %a2 = and i1 %a1, %a1
   %a3 = and i1 %a2, %a2
   %a4 = and i1 %a3, %a3
   %a5 = and i1 %a4, %a4
   %a6 = and i1 %a5, %a5
   %a7 = and i1 %a6, %a6
   %a8 = and i1 %a7, %a7
   %a9 = and i1 %a8, %a8
   %a10 = and i1 %a9, %a9
   %a11 = and i1 %a10, %a10
   %a12 = and i1 %a11, %a11
   %a13 = and i1 %a12, %a12
   %a14 = and i1 %a13, %a13
   %a15 = and i1 %a14, %a14
   call void @llvm.assume(i1 %a15)
   call void @foo(i1 %a1)
   call void @foo(i1 %a2)
   call void @foo(i1 %a3)
   call void @foo(i1 %a4)
-  call void @foo(i1 %a4)
   call void @foo(i1 %a5)
   call void @foo(i1 %a6)
   call void @foo(i1 %a7)
   call void @foo(i1 %a8)
   call void @foo(i1 %a9)
   call void @foo(i1 %a10)
   call void @foo(i1 %a11)
   call void @foo(i1 %a12)
   call void @foo(i1 %a13)
   call void @foo(i1 %a14)
   call void @foo(i1 %a15)
   ret void
 }