[SCEV] Prove implications for SCEVUnknown Phis

[mkazantsev]

Summary

This patch teaches SCEV how to prove implications for SCEVUnknown nodes that are Phis.
If we need to prove Pred for LHS, RHS, and LHS is a Phi with possible incoming values
L1, L2, ..., LN, then if we prove Pred for (L1, RHS), (L2, RHS), ..., (LN, RHS) then we can also
prove it for (LHS, RHS). If both LHS and RHS are Phis from the same block, it is sufficient
to prove the predicate for values that come from the same predecessor block.

The typical case that it handles is that we sometimes need to prove that Phi(Len, Len - 1) >= 0
given that Len > 0. The new logic was added to isImpliedViaOperations and only uses it and
non-recursive reasoning to prove the facts we need, so it should not hurt compile time a lot.

[mkazantsev]

New asserts failed on internal testing, I will investigate and update the patch accordingly.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9585 ↗

(On Diff #136709)

This may fail if LHS is also a Phi from the same BB, but not a SCEVUnknown. It seems that it should be a check instead of assert.

[mkazantsev]

Replaced the overconfident assertion with a check. It is something to follow-up on, but let's not do it in frames of this patch. Added a corresponding test.

[anna]

Comments inline. There's 2 dominator checks (dominates and isReachableFromEntry) that's done per phi operand. That seems like a good amount of compile time usage. There's also a isReachableFromEntry check within the dominates function. I cannot see a way to reduce these checks in your patch though.

lib/Analysis/ScalarEvolution.cpp

9586 ↗

(On Diff #138498)

Pls separate out LPhi->getParent() into a var such as CommonParent and use here and below at line 9591.

9603 ↗

(On Diff #138498)

I think you can extract out the logic here into another lambda because there's a lot of code duplication.
Really all we want to check using logic below and it can be extracted into isImplied(PhiNode *Phi, const Scev *LHSOrRHS).

[mkazantsev]

Actually ignoring of unreachable predecessors was supposed to be an improvement, but we don't really need it. We can yield it for sake of compile time saving.

[anna]

In D44001#1050287, @mkazantsev wrote:

Actually ignoring of unreachable predecessors was supposed to be an improvement, but we don't really need it. We can yield it for sake of compile time saving.

Could you add a test case for unreachable predecessors? They are dominated by everything, so they would just pass through the checks below. I guess the expected improvement was to avoid cases where the unreachable blocks failed ProvedEasily check... A test case shows "unreachable blocks" go through the code, we just never handle them separately.

lib/Analysis/ScalarEvolution.cpp

9585 ↗

(On Diff #136709)

I don't get this comment. We already finished checking that LHS is a phi in the above 2 cases in if-else ladder.

[mkazantsev]

Will do.

lib/Analysis/ScalarEvolution.cpp

9585 ↗

(On Diff #136709)

This comment relates to old version of this patch and is no longer relevant. :)

[mkazantsev]

1. Removed separate logic for unreachable blocks. They will now be handled as usual blocks because identifying them is more expensive in terms of compile time than the profit we expect from it.
2. Removed redundant dominance check, limiting them to one essential check.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9603 ↗

(On Diff #138498)

Dominance check is only needed in one case, so I don't think it's a good idea to make such a lambda.

[mkazantsev]

Adding IRCE tests for new cases (2 phis).

[anna]

lib/Analysis/ScalarEvolution.cpp

9583 ↗

(On Diff #140392)

Could you pls give an idea of how these PendingMerges are used?

9615 ↗

(On Diff #140392)

Nit: LBB == RPhi->getParent()

9618 ↗

(On Diff #140392)

incoming

9633 ↗

(On Diff #140392)

Can we also add an assert that the num of Incoming Values for LPhi is exactly 2?

Really just seems like RAR is a special case of a SCEV Phi with 2 incoming values. We just don't have a Phi node, it's recorded as an RAR.

9643 ↗

(On Diff #140392)

Could you state here: LHS is phi and RHS is non-phi. It's obvious when looking at above code and the swapping, but easier when seeing this as a standalone third case.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9643 ↗

(On Diff #140392)

It is not utterly correct: RHS can be a Phi either SCEVUnknown or AddRec, but from different block than LPhi.

[mkazantsev]

Added comments and asserts, fixed typos.

[anna]

lib/Analysis/ScalarEvolution.cpp

9643 ↗

(On Diff #140392)

ah you're right. It can be a phi from a different block, just that at the point of LBB, it will be exactly one value.

[anna]

LGTM

[efriedma]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

9604

This assertion is triggering on the polly-AOSP buildbot: http://lab.llvm.org:8011/builders/aosp-O3-polly-before-vectorizer-unprofitable/builds/477 .

I can try to reduce a testcase if you need it, but the assertion is pretty obviously just wrong: in general, SCEV doesn't care care whether a loop has a preheader.

[mkazantsev]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

9604

Thanks Eli, you're right, we don't actually need preheader here. I think this one should fix that: https://reviews.llvm.org/rL329379

[efriedma]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

9604

Hmm...

That's an improvement, but ScalarEvolution::createAddRecFromPHI is still much more generous than your assertions: it handles loops with multiple predecessors and multiple latches, at least in some cases.

[mkazantsev]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

9604

I don't think that in such loop we can have SCEVAddRec *in practice*, but after giving it some thought I don't see a theoretical problem with that: we have proved that all incoming values from all incoming blocks are the same, and all increment values from all latches are also the same, this may be happening... I will follow-up on this. At least now the buildbot does not crash with SCEV: http://lab.llvm.org:8011/builders/aosp-O3-polly-before-vectorizer-unprofitable/builds/479

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

private:
   ValueExprMapType ValueExprMap;
 
   /// Mark predicate values currently being processed by isImpliedCond.
   SmallPtrSet<Value *, 6> PendingLoopPredicates;
 
   /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
   SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
 
+  // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
+  SmallPtrSet<const PHINode *, 6> PendingMerges;
+
   /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
   /// conditions dominating the backedge of a loop.
   bool WalkingBEDominatingConds = false;
 
   /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
   /// predicate by splitting it into a set of independent predicates.
   bool ProvingSplitPredicate = false;
 
private:
   ///
   /// This routine tries to rule out certain kinds of integer overflow, and
   /// then tries to reason about arithmetic properties of the predicates.
   bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
                                           const SCEV *LHS, const SCEV *RHS,
                                           const SCEV *FoundLHS,
                                           const SCEV *FoundRHS);
 
+  /// Test whether the condition described by Pred, LHS, and RHS is true
+  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
+  /// true.
+  ///
+  /// This routine tries to figure out predicate for Phis which are SCEVUnknown
+  /// if it is true for every possible incoming value from their respective
+  /// basic blocks.
+  bool isImpliedViaMerge(ICmpInst::Predicate Pred,
+                         const SCEV *LHS, const SCEV *RHS,
+                         const SCEV *FoundLHS, const SCEV *FoundRHS,
+                         unsigned Depth);
+
   /// If we know that the specified Phi is in the header of its containing
   /// loop, we know the loop executes a constant number of times, and the PHI
   /// node is just a recurrence involving constants, fold it.
   Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
                                               const Loop *L);
 
   /// Test if the given expression is known to satisfy the condition described
   /// by Pred and the known constant ranges of LHS and RHS.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
   }
 
   // Try to prove (1) or (2), as needed.
   return isAvailableAtLoopEntry(FoundRHS, L) &&
          isLoopEntryGuardedByCond(L, Pred, FoundRHS,
                                   getConstant(FoundRHSLimit));
 }
 
+bool ScalarEvolution::isImpliedViaMerge(ICmpInst::Predicate Pred,
+                                        const SCEV *LHS, const SCEV *RHS,
+                                        const SCEV *FoundLHS,
+                                        const SCEV *FoundRHS, unsigned Depth) {
+  const PHINode *LPhi = nullptr, *RPhi = nullptr;
+
+  auto ClearOnExit = make_scope_exit([&]() {
+    if (LPhi) {
+      bool Erased = PendingMerges.erase(LPhi);
+      assert(Erased && "Failed to erase LPhi!");
+      (void)Erased;
+    }
+    if (RPhi) {
+      bool Erased = PendingMerges.erase(RPhi);
+      assert(Erased && "Failed to erase RPhi!");
+      (void)Erased;
+    }
+  });
+
+  // Find respective Phis and check that they are not being pending.
+  if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS))
+    if (auto *Phi = dyn_cast<PHINode>(LU->getValue())) {
+      if (!PendingMerges.insert(Phi).second)
+        return false;
+      LPhi = Phi;
+    }
+  if (const SCEVUnknown *RU = dyn_cast<SCEVUnknown>(RHS))
+    if (auto *Phi = dyn_cast<PHINode>(RU->getValue())) {
+      // If we detect a loop of Phi nodes being processed by this method, for
+      // example:
+      //
+      //   %a = phi i32 [ %some1, %preheader ], [ %b, %latch ]
+      //   %b = phi i32 [ %some2, %preheader ], [ %a, %latch ]
+      //
+      // we don't want to deal with a case that complex, so return conservative
+      // answer false.
+      if (!PendingMerges.insert(Phi).second)
+        return false;
+      RPhi = Phi;
+    }
+
+  // If none of LHS, RHS is a Phi, nothing to do here.
+  if (!LPhi && !RPhi)
+    return false;
+
+  // If there is a SCEVUnknown Phi we are interested in, make it left.
+  if (!LPhi) {
+    std::swap(LHS, RHS);
+    std::swap(FoundLHS, FoundRHS);
+    std::swap(LPhi, RPhi);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  assert(LPhi && "LPhi should definitely be a SCEVUnknown Phi!");
+  const BasicBlock *LBB = LPhi->getParent();
+  const SCEVAddRecExpr *RAR = dyn_cast<SCEVAddRecExpr>(RHS);
+
+  auto ProvedEasily = [&](const SCEV *S1, const SCEV *S2) {
+    return isKnownViaNonRecursiveReasoning(Pred, S1, S2) ||
+           isImpliedCondOperandsViaRanges(Pred, S1, S2, FoundLHS, FoundRHS) ||
+           isImpliedViaOperations(Pred, S1, S2, FoundLHS, FoundRHS, Depth);
+  };
+
+  if (RPhi && RPhi->getParent() == LBB) {
+    // Case one: RHS is also a SCEVUnknown Phi from the same basic block.
+    // If we compare two Phis from the same block, and for each entry block
+    // the predicate is true for incoming values from this block, then the
+    // predicate is also true for the Phis.
+    for (const BasicBlock *IncBB : predecessors(LBB)) {
+      const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
+      const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB));
+      if (!ProvedEasily(L, R))
+        return false;
+    }
+  } else if (RAR && RAR->getLoop()->getHeader() == LBB) {
+    // Case two: RHS is also a Phi from the same basic block, and it is an
+    // AddRec. It means that there is a loop which has both AddRec and Unknown
+    // PHIs, for it we can compare incoming values of AddRec from preheader and
+    // latch with their respective incoming values of LPhi.
+    assert(LPhi->getNumIncomingValues() == 2 &&
+           "Phi node standing in loop header does not have exactly 2 inputs?");
+    auto *RLoop = RAR->getLoop();
+    auto *Preheader = RLoop->getLoopPreheader();
+    assert(Preheader && "Loop with AddRec with no preheader?");
+    const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Preheader));
+    if (!ProvedEasily(L1, RAR->getStart()))
+      return false;
+    auto *Latch = RLoop->getLoopLatch();
+    assert(Latch && "Loop with AddRec with no latch?");
+    const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch));
+    if (!ProvedEasily(L2, RAR->getPostIncExpr(*this)))
+      return false;
+  } else {
+    // In all other cases go over inputs of LHS and compare each of them to RHS,
+    // the predicate is true for (LHS, RHS) if it is true for all such pairs.
+    // At this point RHS is either a non-Phi, or it is a Phi from some block
+    // different from LBB.
+    for (const BasicBlock *IncBB : predecessors(LBB)) {
+      // Check that RHS is available in this block.
+      if (!dominates(RHS, IncBB))
+        return false;
+      const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB));
+      if (!ProvedEasily(L, RHS))
+        return false;
+    }
+  }
+  return true;
+}
+
 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
                                             const SCEV *LHS, const SCEV *RHS,
                                             const SCEV *FoundLHS,
                                             const SCEV *FoundRHS) {
   if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundLHS, FoundRHS))
     return true;
 
   if (isImpliedCondOperandsViaNoOverflow(Pred, LHS, RHS, FoundLHS, FoundRHS))
auto GetOpFromSExt = [&](const SCEV *S) {
     if (auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
       return Ext->getOperand();
     // TODO: If S is a SCEVConstant then you can cheaply "strip" the sext off
     // the constant in some cases.
     return S;
   };
 
   // Acquire values from extensions.
+  auto *OrigLHS = LHS;
   auto *OrigFoundLHS = FoundLHS;
   LHS = GetOpFromSExt(LHS);
   FoundLHS = GetOpFromSExt(FoundLHS);
 
   // Is the SGT predicate can be proved trivially or using the found context.
   auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) {
     return isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_SGT, S1, S2) ||
            isImpliedViaOperations(ICmpInst::ICMP_SGT, S1, S2, OrigFoundLHS,
if (match(LHSUnknownExpr->getValue(), m_SDiv(m_Value(LL), m_Value(LR)))) {
       auto *MinusOne = getNegativeSCEV(getOne(WTy));
       auto *NegDenomMinusOne = getMinusSCEV(MinusOne, DenominatorExt);
       if (isKnownNegative(RHS) &&
           IsSGTViaContext(FoundRHSExt, NegDenomMinusOne))
         return true;
     }
   }
 
+  // If our expression contained SCEVUnknown Phis, and we split it down and now
+  // need to prove something for them, try to prove the predicate for every
+  // possible incoming values of those Phis.
+  if (isImpliedViaMerge(Pred, OrigLHS, RHS, OrigFoundLHS, FoundRHS, Depth + 1))
+    return true;
+
   return false;
 }
 
 bool
 ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
                                            const SCEV *LHS, const SCEV *RHS) {
   return isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
          IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||

 }
 
 ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
     : F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
       LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
       PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
       PendingPhiRanges(std::move(Arg.PendingPhiRanges)),
+      PendingMerges(std::move(Arg.PendingMerges)),
       MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
       ConstantEvolutionLoopExitValue(
           std::move(Arg.ConstantEvolutionLoopExitValue)),
       ValuesAtScopes(std::move(Arg.ValuesAtScopes)),
       LoopDispositions(std::move(Arg.LoopDispositions)),
ScalarEvolution::~ScalarEvolution() {
   // that a loop had multiple computable exits.
   for (auto &BTCI : BackedgeTakenCounts)
     BTCI.second.clear();
   for (auto &BTCI : PredicatedBackedgeTakenCounts)
     BTCI.second.clear();
 
   assert(PendingLoopPredicates.empty() && "isImpliedCond garbage");
   assert(PendingPhiRanges.empty() && "getRangeRef garbage");
+  assert(PendingMerges.empty() && "isImpliedViaMerge garbage");
   assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!");
   assert(!ProvingSplitPredicate && "ProvingSplitPredicate garbage!");
 }
 
 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
   return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
 }
 

llvm/trunk/test/Transforms/IRCE/decrementing-loop.ll

 
  out.of.bounds:
   ret void
 
  exit:
   ret void
 }
 
+; Check that we can figure out that IV is non-negative via implication through
+; Phi node.
+define void @test_03(i32* %a, i32* %a_len_ptr, i1 %cond) {
+
+; CHECK-LABEL: test_03
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.minus.one = sub nsw i32 %len.a, 1
+  %len.minus.two = sub nsw i32 %len.a, 2
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
+  %first.itr.check = icmp sgt i32 %len.a, 3
+  br i1 %first.itr.check, label %loop, label %exit
+
+loop:
+  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rc = icmp ult i32 %idx.next, %len.a
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %v = load i32, i32* %el.a
+  %loop.cond = icmp slt i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+; Check that we can figure out that IV is non-negative via implication through
+; two Phi nodes.
+define void @test_04(i32* %a, i32* %a_len_ptr, i1 %cond) {
+
+; CHECK-LABEL: test_04
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.minus.one = sub nsw i32 %len.a, 1
+  %len.plus.one = add nsw i32 %len.a, 1
+  %len.minus.two = sub nsw i32 %len.a, 2
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
+  %len.phi = phi i32 [ %len.a, %if.true ], [ %len.plus.one, %if.false ]
+  %first.itr.check = icmp sgt i32 %len.a, 3
+  br i1 %first.itr.check, label %loop, label %exit
+
+loop:
+  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rc = icmp ult i32 %idx.next, %len.phi
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %v = load i32, i32* %el.a
+  %loop.cond = icmp slt i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+; Check that we can figure out that IV is non-negative via implication through
+; two Phi nodes, one being AddRec.
+define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) {
+
+; CHECK-LABEL: test_05
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.minus.one = sub nsw i32 %len.a, 1
+  %len.plus.one = add nsw i32 %len.a, 1
+  %len.minus.two = sub nsw i32 %len.a, 2
+  br label %merge
+
+merge:
+  %starting.value = phi i32 [ %len.minus.two, %entry ], [ %len.minus.one, %merge ]
+  %len.phi = phi i32 [ %len.a, %entry ], [ %len.phi.next, %merge ]
+  %len.phi.next = add nsw i32 %len.phi, 1
+  br i1 true, label %first.iter.check, label %merge
+
+first.iter.check:
+  %first.itr.check = icmp sgt i32 %len.a, 3
+  br i1 %first.itr.check, label %loop, label %exit
+
+loop:
+  %idx = phi i32 [ %starting.value, %first.iter.check ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rc = icmp ult i32 %idx.next, %len.phi
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %v = load i32, i32* %el.a
+  %loop.cond = icmp slt i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
 !0 = !{i32 0, i32 2147483647}
 !1 = !{!"branch_weights", i32 64, i32 4}

llvm/trunk/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll

loop:
   %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
   store atomic i32 0, i32* %el unordered, align 4
   %iv.next = add nsw i32 %iv, -1
   ; CHECK: %loopcond = icmp slt i64 %indvars.iv, 1
   %loopcond = icmp slt i32 %iv, 1
   br i1 %loopcond, label %loopexit, label %loop
 }
 
+define void @promote_latch_condition_decrementing_loop_04(i32* %p, i32* %a, i1 %cond) {
+
+; CHECK-LABEL: @promote_latch_condition_decrementing_loop_04(
+; CHECK-NOT:     trunc
+
+entry:
+  %len = load i32, i32* %p, align 4, !range !0
+  %len.minus.1 = add nsw i32 %len, -1
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %iv_start = phi i32 [ %len, %if.true ], [%len.minus.1, %if.false ]
+  %zero_check = icmp eq i32 %len, 0
+  br i1 %zero_check, label %loopexit, label %preheader
+
+preheader:
+  br label %loop
+
+loopexit:
+  ret void
+
+loop:
+  %iv = phi i32 [ %iv.next, %loop ], [ %iv_start, %preheader ]
+  ; CHECK: %indvars.iv = phi i64
+  %iv.wide = zext i32 %iv to i64
+  %el = getelementptr inbounds i32, i32* %a, i64 %iv.wide
+  store atomic i32 0, i32* %el unordered, align 4
+  %iv.next = add nsw i32 %iv, -1
+  ; CHECK: %loopcond = icmp slt i64 %indvars.iv, 1
+  %loopcond = icmp slt i32 %iv, 1
+  br i1 %loopcond, label %loopexit, label %loop
+}
 
 !0 = !{i32 0, i32 2147483647}