[unroll] Use value domain for symbolic execution based cost model

[reames]

Summary

The current full unroll cost model does a symbolic evaluation of the loop up to a fixed limit. That symbolic evaluation currently simplifies to constants, but we can generalize to arbitrary Values using the InstructionSimplify infrastructure at very low cost.

By itself, this enables some simplifications, but it's mainly useful when combined with the branch simplification over in D102928.

(FYI, current tests are a bit lacking. Planning to pre-commit some tests and rebase in the near future.)

[reames]

Rebase over landed tests

[nikic]

I think it would be good to split this into two parts: One that changes the infrastructure to map to Value rather than Constant, making use of the existing SimplifyBinOp fold. And another that replaces constant folding with InstSimplify calls in the places it's not used yet.

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

203

With the added SimplifyCmpInst, I'd expect that we no longer need this ConstantExpr::getCompare() block.

[nikic]

llvm/test/Transforms/LoopUnroll/unroll-cost-symbolic-execute.ll

23

Side note: Looks like we currently don't simplify peeled blocks at all.

[reames]

In D102934#2774854, @nikic wrote:

I think it would be good to split this into two parts: One that changes the infrastructure to map to Value rather than Constant, making use of the existing SimplifyBinOp fold. And another that replaces constant folding with InstSimplify calls in the places it's not used yet.

If you're happy with the direction, do you mind if I land them without separate review? i.e. Can I interpret this as an LGTM for the split patches?

I'd mildly prefer not splitting the patches, but I'll do whatever will minimize the review back-and-forth. :)

[nikic]

In D102934#2778255, @reames wrote:

If you're happy with the direction, do you mind if I land them without separate review? i.e. Can I interpret this as an LGTM for the split patches?

I'd mildly prefer not splitting the patches, but I'll do whatever will minimize the review back-and-forth. :)

Okay, I don't feel particularly strongly about this, so let's say this LGTM modulo the note about ConstantExpr::getCompare().

llvm/include/llvm/Analysis/LoopUnrollAnalyzer.h

class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
   friend class InstVisitor<UnrolledInstAnalyzer, bool>;
   struct SimplifiedAddress {
     Value *Base = nullptr;
     ConstantInt *Offset = nullptr;
   };
 
 public:
   UnrolledInstAnalyzer(unsigned Iteration,
-                       DenseMap<Value *, Constant *> &SimplifiedValues,
+                       DenseMap<Value *, Value *> &SimplifiedValues,
                        ScalarEvolution &SE, const Loop *L)
       : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
       IterationNumber = SE.getConstant(APInt(64, Iteration));
   }
 
   // Allow access to the initial visit method.
   using Base::visit;
 
 private:
   /// A cache of pointer bases and constant-folded offsets corresponding
   /// to GEP (or derived from GEP) instructions.
   ///
   /// In order to find the base pointer one needs to perform non-trivial
   /// traversal of the corresponding SCEV expression, so it's good to have the
   /// results saved.
   DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
 
   /// SCEV expression corresponding to number of currently simulated
   /// iteration.
   const SCEV *IterationNumber;
 
-  /// A Value->Constant map for keeping values that we managed to
-  /// constant-fold on the given iteration.
-  ///
   /// While we walk the loop instructions, we build up and maintain a mapping
   /// of simplified values specific to this iteration.  The idea is to propagate
   /// any special information we have about loads that can be replaced with
   /// constants after complete unrolling, and account for likely simplifications
   /// post-unrolling.
-  DenseMap<Value *, Constant *> &SimplifiedValues;
+  DenseMap<Value *, Value *> &SimplifiedValues;
 
   ScalarEvolution &SE;
   const Loop *L;
 
   bool simplifyInstWithSCEV(Instruction *I);
 
   bool visitInstruction(Instruction &I);
   bool visitBinaryOperator(BinaryOperator &I);
   bool visitLoad(LoadInst &I);
   bool visitCastInst(CastInst &I);
   bool visitCmpInst(CmpInst &I);
   bool visitPHINode(PHINode &PN);
 };
 }
 #endif

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp

 /// Try to simplify binary operator I.
 ///
 /// TODO: Probably it's worth to hoist the code for estimating the
 /// simplifications effects to a separate class, since we have a very similar
 /// code in InlineCost already.
 bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   if (!isa<Constant>(LHS))
-    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
+    if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
       LHS = SimpleLHS;
   if (!isa<Constant>(RHS))
-    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
+    if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
       RHS = SimpleRHS;
 
   Value *SimpleV = nullptr;
   const DataLayout &DL = I.getModule()->getDataLayout();
   if (auto FI = dyn_cast<FPMathOperator>(&I))
     SimpleV =
         SimplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
   else
     SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
 
-  if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
-    SimplifiedValues[&I] = C;
-
-  if (SimpleV)
+  if (SimpleV) {
+    SimplifiedValues[&I] = SimpleV;
     return true;
+  }
   return Base::visitBinaryOperator(I);
 }
 
 /// Try to fold load I.
 bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
   Value *AddrOp = I.getPointerOperand();
 
   auto AddressIt = SimplifiedAddresses.find(AddrOp);
bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
   assert(CV && "Constant expected.");
   SimplifiedValues[&I] = CV;
 
   return true;
 }
 
 /// Try to simplify cast instruction.
 bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
-  // Propagate constants through casts.
-  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
-  if (!COp)
-    COp = SimplifiedValues.lookup(I.getOperand(0));
+  Value *Op = I.getOperand(0);
+  if (Value *Simplified = SimplifiedValues.lookup(Op))
+    Op = Simplified;
 
-  // If we know a simplified value for this operand and cast is valid, save the
-  // result to SimplifiedValues.
   // The cast can be invalid, because SimplifiedValues contains results of SCEV
   // analysis, which operates on integers (and, e.g., might convert i8* null to
   // i32 0).
-  if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())) {
-    if (Constant *C =
-            ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
-      SimplifiedValues[&I] = C;
+  if (CastInst::castIsValid(I.getOpcode(), Op, I.getType())) {
+    const DataLayout &DL = I.getModule()->getDataLayout();
+    if (Value *V = SimplifyCastInst(I.getOpcode(), Op, I.getType(), DL)) {
+      SimplifiedValues[&I] = V;
       return true;
     }
   }
 
   return Base::visitCastInst(I);
 }
 
 /// Try to simplify cmp instruction.
 bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
   // First try to handle simplified comparisons.
   if (!isa<Constant>(LHS))
-    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
+    if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
       LHS = SimpleLHS;
   if (!isa<Constant>(RHS))
-    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
+    if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
       RHS = SimpleRHS;
 
   if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
     auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
     if (SimplifiedLHS != SimplifiedAddresses.end()) {
       auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
       if (SimplifiedRHS != SimplifiedAddresses.end()) {
         SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
     if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
       if (CLHS->getType() == CRHS->getType()) {
         if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
           SimplifiedValues[&I] = C;
           return true;
         }
       }
     }
   }
 
+  const DataLayout &DL = I.getModule()->getDataLayout();
+  if (Value *V = SimplifyCmpInst(I.getPredicate(), LHS, RHS, DL)) {
+    SimplifiedValues[&I] = V;
+    return true;
+  }
+
   return Base::visitCmpInst(I);
 }
 
 bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
   // Run base visitor first. This way we can gather some useful for later
   // analysis information.
   if (Base::visitPHINode(PN))
     return true;
 
   // The loop induction PHI nodes are definitionally free.
   return PN.getParent() == L->getHeader();
 }
 
 bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {
   return simplifyInstWithSCEV(&I);
 }

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

if (!L->isInnermost())
     return None;
 
   // Don't simulate loops with a big or unknown tripcount
   if (!TripCount || TripCount > MaxIterationsCountToAnalyze)
     return None;
 
   SmallSetVector<BasicBlock *, 16> BBWorklist;
   SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;
-  DenseMap<Value *, Constant *> SimplifiedValues;
-  SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues;
+  DenseMap<Value *, Value *> SimplifiedValues;
+  SmallVector<std::pair<Value *, Value *>, 4> SimplifiedInputValues;
 
   // The estimated cost of the unrolled form of the loop. We try to estimate
   // this by simplifying as much as we can while computing the estimate.
   InstructionCost UnrolledCost = 0;
 
   // We also track the estimated dynamic (that is, actually executed) cost in
   // the rolled form. This helps identify cases when the savings from unrolling
   // aren't just exposing dead control flows, but actual reduced dynamic
for (Instruction &I : *L->getHeader()) {
       // The loop header PHI nodes must have exactly two input: one from the
       // loop preheader and one from the loop latch.
       assert(
           PHI->getNumIncomingValues() == 2 &&
           "Must have an incoming value only for the preheader and the latch.");
 
       Value *V = PHI->getIncomingValueForBlock(
           Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
-      Constant *C = dyn_cast<Constant>(V);
-      if (Iteration != 0 && !C)
-        C = SimplifiedValues.lookup(V);
-      if (C)
-        SimplifiedInputValues.push_back({PHI, C});
+      if (Iteration != 0 && SimplifiedValues.count(V))
+        V = SimplifiedValues.lookup(V);
+      SimplifiedInputValues.push_back({PHI, V});
     }
 
     // Now clear and re-populate the map for the next iteration.
     SimplifiedValues.clear();
     while (!SimplifiedInputValues.empty())
       SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
 
     UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE, L);
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
                             << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize
                             << "\n");
           return None;
         }
       }
 
       Instruction *TI = BB->getTerminator();
 
+      auto getSimplifiedConstant = [&](Value *V) -> Constant * {
+        if (SimplifiedValues.count(V))
+          V = SimplifiedValues.lookup(V);
+        return dyn_cast<Constant>(V);
+      };
+
       // Add in the live successors by first checking whether we have terminator
       // that may be simplified based on the values simplified by this call.
       BasicBlock *KnownSucc = nullptr;
       if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
         if (BI->isConditional()) {
-          if (Constant *SimpleCond =
-                  SimplifiedValues.lookup(BI->getCondition())) {
+          if (auto *SimpleCond = getSimplifiedConstant(BI->getCondition())) {
             // Just take the first successor if condition is undef
             if (isa<UndefValue>(SimpleCond))
               KnownSucc = BI->getSuccessor(0);
             else if (ConstantInt *SimpleCondVal =
                          dyn_cast<ConstantInt>(SimpleCond))
               KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
           }
         }
       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
-        if (Constant *SimpleCond =
-                SimplifiedValues.lookup(SI->getCondition())) {
+        if (auto *SimpleCond = getSimplifiedConstant(SI->getCondition())) {
           // Just take the first successor if condition is undef
           if (isa<UndefValue>(SimpleCond))
             KnownSucc = SI->getSuccessor(0);
           else if (ConstantInt *SimpleCondVal =
                        dyn_cast<ConstantInt>(SimpleCond))
             KnownSucc = SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
         }
       }

llvm/test/Transforms/LoopUnroll/unroll-cost-symbolic-execute.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -loop-unroll -S -unroll-threshold=120 < %s | FileCheck %s
+
+define i32 @test_both(i32 %limit) {
+; CHECK-LABEL: @test_both(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sge i32 [[LIMIT:%.*]], 0
+; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[LIMIT]], [[SUM]]
+; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sge i32 [[SUB]], 0
+; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[SUB]]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 8
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK:       done:
+; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
+; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
+; CHECK:       failure:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  %loop_guard = icmp sge i32 %limit, 0
+  br i1 %loop_guard, label %loop, label %failure
+
+loop:                                             ; preds = %backedge, %entry
+  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %sub = sub i32 %limit, %sum
+  %is.positive = icmp sge i32 %sub, 0
+  br i1 %is.positive, label %backedge, label %if.false
+
+if.false:                                         ; preds = %loop
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  br label %backedge
+
+backedge:                                         ; preds = %if.false, %loop
+  %sum.next = add i32 %sum, %sub
+  %iv.next = add i32 %iv, 1
+  %loop.cond = icmp ne i32 %iv, 8
+  br i1 %loop.cond, label %loop, label %done
+
+done:                                             ; preds = %backedge
+  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
+  ret i32 %sum.next.lcssa
+
+failure:
+  unreachable
+}
+
+define i32 @test_dom_condition(i32 %limit) {
+; CHECK-LABEL: @test_dom_condition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sge i32 [[LIMIT:%.*]], 0
+; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[SUM]]
+; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sle i32 [[SUB]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[SUB]]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 8
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK:       done:
+; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
+; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
+; CHECK:       failure:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  %loop_guard = icmp sge i32 %limit, 0
+  br i1 %loop_guard, label %loop, label %failure
+
+loop:                                             ; preds = %backedge, %entry
+  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %sub = sub i32 0, %sum
+  %is.positive = icmp sle i32 %sub, %limit
+  br i1 %is.positive, label %backedge, label %if.false
+
+if.false:                                         ; preds = %loop
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  br label %backedge
+
+backedge:                                         ; preds = %if.false, %loop
+  %sum.next = add i32 %sum, %sub
+  %iv.next = add i32 %iv, 1
+  %loop.cond = icmp ne i32 %iv, 8
+  br i1 %loop.cond, label %loop, label %done
+
+done:                                             ; preds = %backedge
+  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
+  ret i32 %sum.next.lcssa
+
+failure:
+  unreachable
+}
+
+
+define i32 @test_symbolic_only(i32 %limit) {
+; CHECK-LABEL: @test_symbolic_only(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LOOP_GUARD:%.*]] = icmp sge i32 [[LIMIT:%.*]], 0
+; CHECK-NEXT:    br i1 [[LOOP_GUARD]], label [[LOOP_PREHEADER:%.*]], label [[FAILURE:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_1:%.*]], label [[IF_FALSE_1:%.*]]
+; CHECK:       failure:
+; CHECK-NEXT:    unreachable
+; CHECK:       if.false.1:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_1]]
+; CHECK:       backedge.1:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_2:%.*]], label [[IF_FALSE_2:%.*]]
+; CHECK:       if.false.2:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_2]]
+; CHECK:       backedge.2:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_3:%.*]], label [[IF_FALSE_3:%.*]]
+; CHECK:       if.false.3:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_3]]
+; CHECK:       backedge.3:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_4:%.*]], label [[IF_FALSE_4:%.*]]
+; CHECK:       if.false.4:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_4]]
+; CHECK:       backedge.4:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_5:%.*]], label [[IF_FALSE_5:%.*]]
+; CHECK:       if.false.5:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_5]]
+; CHECK:       backedge.5:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_6:%.*]], label [[IF_FALSE_6:%.*]]
+; CHECK:       if.false.6:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_6]]
+; CHECK:       backedge.6:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_7:%.*]], label [[IF_FALSE_7:%.*]]
+; CHECK:       if.false.7:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_7]]
+; CHECK:       backedge.7:
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE_8:%.*]], label [[IF_FALSE_8:%.*]]
+; CHECK:       if.false.8:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    br label [[BACKEDGE_8]]
+; CHECK:       backedge.8:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %loop_guard = icmp sge i32 %limit, 0
+  br i1 %loop_guard, label %loop, label %failure
+
+loop:                                             ; preds = %backedge, %entry
+  %sum = phi i32 [ 0, %entry ], [ %sum.next, %backedge ]
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %sub = sub i32 %limit, %sum
+  %is.positive = icmp eq i32 %sub, %limit
+  br i1 %is.positive, label %backedge, label %if.false
+
+if.false:                                         ; preds = %loop
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  call void @foo()
+  br label %backedge
+
+backedge:                                         ; preds = %if.false, %loop
+  %hidden_zero = sub i32 %limit, %sub
+  %sum.next = add i32 %sum, %hidden_zero
+  %iv.next = add i32 %iv, 1
+  %loop.cond = icmp ne i32 %iv, 8
+  br i1 %loop.cond, label %loop, label %done
+
+done:                                             ; preds = %backedge
+  %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
+  ret i32 %sum.next.lcssa
+
+failure:
+  unreachable
+}
+
+declare void @foo()

llvm/unittests/Analysis/UnrollAnalyzerTest.cpp

 #include "llvm/InitializePasses.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 namespace llvm {
 void initializeUnrollAnalyzerTestPass(PassRegistry &);
 
-static SmallVector<DenseMap<Value *, Constant *>, 16> SimplifiedValuesVector;
+static SmallVector<DenseMap<Value *, Value *>, 16> SimplifiedValuesVector;
 static unsigned TripCount = 0;
 
 namespace {
 struct UnrollAnalyzerTest : public FunctionPass {
   static char ID;
   bool runOnFunction(Function &F) override {
     LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 
     Function::iterator FI = F.begin();
     FI++; // First basic block is entry - skip it.
     BasicBlock *Header = &*FI++;
     Loop *L = LI->getLoopFor(Header);
     BasicBlock *Exiting = L->getExitingBlock();
 
     SimplifiedValuesVector.clear();
     TripCount = SE->getSmallConstantTripCount(L, Exiting);
     for (unsigned Iteration = 0; Iteration < TripCount; Iteration++) {
-      DenseMap<Value *, Constant *> SimplifiedValues;
+      DenseMap<Value *, Value *> SimplifiedValues;
       UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L);
       for (auto *BB : L->getBlocks())
         for (Instruction &I : *BB)
           Analyzer.visit(I);
       SimplifiedValuesVector.push_back(SimplifiedValues);
     }
     return false;
   }