[NFC] Refactor loop peeling code for calculating phi invariance.

[jamieschmeiser]

Summary

Refactor loop peeling code for calculating phi invariance.

Refactor loop peeling code by moving code for calculating phi invariance
into a separate class that does the calculation.  Redescribe and rework
the algorithm in preparation for adding increased functionality.  Add
test case that does not exhibit peeling that will be subsequently supported.

[mkazantsev]

General notion: if your claim is that the existing code isn't handling some case, then you need to demonstrate it in a test. Steps are the following:

• Create a test, run utils/update_test_checks.py on it with existing implementation, and commit it;
• With your change, run this script again and re-generate checks so that they clearly show the difference;

Without it, it's hard to say how much better it became.

Also think if it can be split into several patches, some being NFC (e.g. factor out this logic into a separate class), which I'm generally fine with, and semantically meaningful functionality changes.

llvm/test/Transforms/LoopUnroll/peel-loop-phi-analysis.ll

7

This is in the process of deprecation, pls only use new PM.

17

I would strongly prefer auto-generated full checks over anything else. Please use utils/update_test_checks.py.

[jamieschmeiser]

I have split out the refactoring of the code so there are no intended
functional changes. I have added the test case as requested, showing
the current, limited functionality. After this lands, I will post a
patch with the expanded functionality.

[mkazantsev]

I'm generally fine with this refactoring. Some style comments, the most important one being regarding using a constant to represent infinity instead of None.

For test -- LGTM, you can commit it separately, it doesn't require this NFC to go with it.

llvm/lib/Transforms/Utils/LoopPeel.cpp

107

"Deterministic" isn't the best word here, because Phi value is always determined by its incoming block. How about "loop-invariant"?

118

If it wasn't your intention, please change condition i > 10 here, otherwise we can say that it's (maybe) also profitable to peel off 10 iterations to get rid of this check (and it might be even more important than what are you describing).

167

Can it be const Loop * here and in other places? Looks like this thing isn't intended to modify the code.

169

"allowable maximum" -> "sufficient minimum"? We could off course peel more, just don't see a reason to.

175

Do we really need that, provided that there is L->getLatch()?

179

Can it return Infinity + 1 if MaxIterations > Infinity? Or, if it's impossible, please assert it here explicitly.

187

Doesn't really look like it's worth storing it separately, it's cheaply claimed from loop when needed.

191

Does this mean that this Phi provably never becomes invariant, or it can also mean that we haven't found this number (as it was in the original code)?

I think the original code was structured better here for 2 reasons:

• Having a constant to represent infinity is potentially error-prone. Who knows what kind of math people are going to do with it? Using None for it is just more clear.
• Old code used None for unknowns in fact, and this code claims to know it's infinity.

I'd suggest returning Optional<unsigned> as a safer structure for this.

197

Please use DenseMap unless there are strong reasons to choose a std:: container.

200

I don't think you ever expect nullptr loops to be a normal input. Change to const Loop &?

210

LP -> L, M -> MaxIterations?

[jamieschmeiser]

@mkazantsev, I have addressed your concerns.
Regarding your comments concerning the use of infinity (as an unsigned) vs Optional<unsigned>: perhaps it's just me, but I found the use of Optional<unsigned> confusing and it became more confusing when I incorporated the max iterations into the algorithm. It isn't clear from the code at this point, but when one expands the algorithm to include binary operators, one wants to avoid computing the number of peels unnecessarily when the first operand has already reached (or surpassed) the maximum allowable peels. This is why I simplified the code to use an unsigned and placed it all within protected members of the class, wrapping it with the Optional<unsigned> on coming out, to both clarify the algorithm (especially when considering max iterations) and also to prevent people monkeying with the unsigned value (as you pointed out as a possibility in your comments). Your criticism of the constant name Infinity is valid--it is misleading. In response, I have hidden the Optional<unsigned> behind a type called PeelCount, used a constant Unknown (which is None) rather than Infinity and kept the math in protected functions. I think this makes the code easier to understand and also addresses your preference for using Optional<unsigned>.

[jamieschmeiser]

llvm/lib/Transforms/Utils/LoopPeel.cpp

118

I have removed this as it isn't germane to the example. I think I originally had it in to avoid partial loop unrolling, which I think is attempted before peeling

[mkazantsev]

LG, thanks for addressing the comments!

llvm/include/llvm/Transforms/Utils/LoopPeel.h

 
 #ifndef LLVM_TRANSFORMS_UTILS_LOOPPEEL_H
 #define LLVM_TRANSFORMS_UTILS_LOOPPEEL_H
 
 #include "llvm/Analysis/TargetTransformInfo.h"
 
 namespace llvm {
 
-bool canPeel(Loop *L);
+bool canPeel(const Loop *L);
 
 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
               DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA);
 
 TargetTransformInfo::PeelingPreferences
 gatherPeelingPreferences(Loop *L, ScalarEvolution &SE,
                          const TargetTransformInfo &TTI,
                          Optional<bool> UserAllowPeeling,

llvm/lib/Transforms/Utils/LoopPeel.cpp

 static cl::opt<bool> DisableAdvancedPeeling(
     "disable-advanced-peeling", cl::init(false), cl::Hidden,
     cl::desc(
         "Disable advance peeling. Issues for convergent targets (D134803)."));
 
 static const char *PeeledCountMetaData = "llvm.loop.peeled.count";
 
 // Check whether we are capable of peeling this loop.
-bool llvm::canPeel(Loop *L) {
+bool llvm::canPeel(const Loop *L) {
   // Make sure the loop is in simplified form
   if (!L->isLoopSimplifyForm())
     return false;
   if (!DisableAdvancedPeeling)
     return true;
 
   SmallVector<BasicBlock *, 4> Exits;
   L->getUniqueNonLatchExitBlocks(Exits);
   // The latch must either be the only exiting block or all non-latch exit
   // blocks have either a deopt or unreachable terminator or compose a chain of
   // blocks where the last one is either deopt or unreachable terminated. Both
   // deopt and unreachable terminators are a strong indication they are not
   // taken. Note that this is a profitability check, not a legality check. Also
   // note that LoopPeeling currently can only update the branch weights of latch
   // blocks and branch weights to blocks with deopt or unreachable do not need
   // updating.
   return llvm::all_of(Exits, IsBlockFollowedByDeoptOrUnreachable);
 }
 
-// This function calculates the number of iterations after which the given Phi
-// becomes an invariant. The pre-calculated values are memorized in the map. The
-// function (shortcut is I) is calculated according to the following definition:
+namespace {
+
+// As a loop is peeled, it may be the case that Phi nodes become
+// loop-invariant (ie, known because there is only one choice).
+// For example, consider the following function:
+//   void g(int);
+//   void binary() {
+//     int x = 0;
+//     int y = 0;
+//     int a = 0;
+//     for(int i = 0; i <100000; ++i) {
+//       g(x);
+//       x = y;
+//       g(a);
+//       y = a + 1;
+//       a = 5;
+//     }
+//   }
+// Peeling 3 iterations is beneficial because the values for x, y and a
+// become known.  The IR for this loop looks something like the following:
+//
+//   %i = phi i32 [ 0, %entry ], [ %inc, %if.end ]
+//   %a = phi i32 [ 0, %entry ], [ 5, %if.end ]
+//   %y = phi i32 [ 0, %entry ], [ %add, %if.end ]
+//   %x = phi i32 [ 0, %entry ], [ %y, %if.end ]
+//   ...
+//   tail call void @_Z1gi(i32 signext %x)
+//   tail call void @_Z1gi(i32 signext %a)
+//   %add = add nuw nsw i32 %a, 1
+//   %inc = add nuw nsw i32 %i, 1
+//   %exitcond = icmp eq i32 %inc, 100000
+//   br i1 %exitcond, label %for.cond.cleanup, label %for.body
+//
+// The arguments for the calls to g will become known after 3 iterations
+// of the loop, because the phi nodes values become known after 3 iterations
+// of the loop (ie, they are known on the 4th iteration, so peel 3 iterations).
+// The first iteration has g(0), g(0); the second has g(0), g(5); the
+// third has g(1), g(5) and the fourth (and all subsequent) have g(6), g(5).
+// Now consider the phi nodes:
+//   %a is a phi with constants so it is determined after iteration 1.
+//   %y is a phi based on a constant and %a so it is determined on
+//     the iteration after %a is determined, so iteration 2.
+//   %x is a phi based on a constant and %y so it is determined on
+//     the iteration after %y, so iteration 3.
+//   %i is based on itself (and is an induction variable) so it is
+//     never determined.
+// This means that peeling off 3 iterations will result in being able to
+// remove the phi nodes for %a, %y, and %x.  The arguments for the
+// corresponding calls to g are determined and the code for computing
+// x, y, and a can be removed.
+//
+// The PhiAnalyzer class calculates how many times a loop should be
+// peeled based on the above analysis of the phi nodes in the loop while
+// respecting the maximum specified.
+class PhiAnalyzer {
+public:
+  PhiAnalyzer(const Loop &L, unsigned MaxIterations);
+
+  // Calculate the sufficient minimum number of iterations of the loop to peel
+  // such that phi instructions become determined (subject to allowable limits)
+  Optional<unsigned> calculateIterationsToPeel();
+
+protected:
+  using PeelCounter = Optional<unsigned>;
+  const PeelCounter Unknown = None;
+
+  // Add 1 respecting Unknown and return Unknown if result over MaxIterations
+  PeelCounter addOne(PeelCounter PC) const {
+    if (PC == Unknown)
+      return Unknown;
+    return (*PC + 1 <= MaxIterations) ? PeelCounter{*PC + 1} : Unknown;
+  }
+
+  // Calculate the number of iterations after which the given value
+  // becomes an invariant.
+  PeelCounter calculate(const Value &);
+
+  const Loop &L;
+  const unsigned MaxIterations;
+
+  // Map of Values to number of iterations to invariance
+  SmallDenseMap<const Value *, PeelCounter> IterationsToInvariance;
+};
+
+PhiAnalyzer::PhiAnalyzer(const Loop &L, unsigned MaxIterations)
+    : L(L), MaxIterations(MaxIterations) {
+  assert(canPeel(&L) && "loop is not suitable for peeling");
+  assert(MaxIterations > 0 && "no peeling is allowed?");
+}
+
+// This function calculates the number of iterations after which the value
+// becomes an invariant. The pre-calculated values are memorized in a map.
+// N.B. This number will be Unknown or <= MaxIterations.
+// The function is calculated according to the following definition:
 // Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge].
-//   If %y is a loop invariant, then I(%x) = 1.
-//   If %y is a Phi from the loop header, I(%x) = I(%y) + 1.
-//   Otherwise, I(%x) is infinite.
-// TODO: Actually if %y is an expression that depends only on Phi %z and some
-//       loop invariants, we can estimate I(%x) = I(%z) + 1. The example
-//       looks like:
-//         %x = phi(0, %a),  <-- becomes invariant starting from 3rd iteration.
-//         %y = phi(0, 5),
-//         %a = %y + 1.
-static Optional<unsigned> calculateIterationsToInvariance(
-    PHINode *Phi, Loop *L, BasicBlock *BackEdge,
-    SmallDenseMap<PHINode *, Optional<unsigned> > &IterationsToInvariance) {
-  assert(Phi->getParent() == L->getHeader() &&
-         "Non-loop Phi should not be checked for turning into invariant.");
-  assert(BackEdge == L->getLoopLatch() && "Wrong latch?");
+//   F(%x) = G(%y) + 1 (N.B. [MaxIterations | Unknown] + 1 => Unknown)
+//   G(%y) = 0 if %y is a loop invariant
+//   G(%y) = G(%BackEdgeValue) if %y is a phi in the header block
+//   G(%y) = TODO: if %y is an expression based on phis and loop invariants
+//           The example looks like:
+//           %x = phi(0, %a) <-- becomes invariant starting from 3rd iteration.
+//           %y = phi(0, 5)
+//           %a = %y + 1
+//   G(%y) = Unknown otherwise (including phi not in header block)
+PhiAnalyzer::PeelCounter PhiAnalyzer::calculate(const Value &V) {
   // If we already know the answer, take it from the map.
-  auto I = IterationsToInvariance.find(Phi);
+  auto I = IterationsToInvariance.find(&V);
   if (I != IterationsToInvariance.end())
     return I->second;
 
-  // Otherwise we need to analyze the input from the back edge.
-  Value *Input = Phi->getIncomingValueForBlock(BackEdge);
-  // Place infinity to map to avoid infinite recursion for cycled Phis. Such
+  // Place Unknown to map to avoid infinite recursion. Such
   // cycles can never stop on an invariant.
-  IterationsToInvariance[Phi] = None;
-  Optional<unsigned> ToInvariance;
+  IterationsToInvariance[&V] = Unknown;
 
-  if (L->isLoopInvariant(Input))
-    ToInvariance = 1u;
-  else if (PHINode *IncPhi = dyn_cast<PHINode>(Input)) {
-    // Only consider Phis in header block.
-    if (IncPhi->getParent() != L->getHeader())
-      return None;
-    // If the input becomes an invariant after X iterations, then our Phi
-    // becomes an invariant after X + 1 iterations.
-    auto InputToInvariance = calculateIterationsToInvariance(
-        IncPhi, L, BackEdge, IterationsToInvariance);
-    if (InputToInvariance)
-      ToInvariance = *InputToInvariance + 1u;
-  }
-
-  // If we found that this Phi lies in an invariant chain, update the map.
-  if (ToInvariance)
-    IterationsToInvariance[Phi] = ToInvariance;
-  return ToInvariance;
+  if (L.isLoopInvariant(&V))
+    // Loop invariant so known at start.
+    return (IterationsToInvariance[&V] = 0);
+  if (const PHINode *Phi = dyn_cast<PHINode>(&V)) {
+    if (Phi->getParent() != L.getHeader()) {
+      // Phi is not in header block so Unknown.
+      assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved");
+      return Unknown;
+    }
+    // We need to analyze the input from the back edge and add 1.
+    Value *Input = Phi->getIncomingValueForBlock(L.getLoopLatch());
+    PeelCounter Iterations = calculate(*Input);
+    assert(IterationsToInvariance[Input] == Iterations &&
+           "unexpected value saved");
+    return (IterationsToInvariance[Phi] = addOne(Iterations));
+  }
+  // TODO: handle expressions
+
+  // Everything else is Unknown.
+  assert(IterationsToInvariance[&V] == Unknown && "unexpected value saved");
+  return Unknown;
+}
+
+Optional<unsigned> PhiAnalyzer::calculateIterationsToPeel() {
+  unsigned Iterations = 0;
+  for (auto &PHI : L.getHeader()->phis()) {
+    PeelCounter ToInvariance = calculate(PHI);
+    if (ToInvariance != Unknown) {
+      assert(*ToInvariance <= MaxIterations && "bad result in phi analysis");
+      Iterations = std::max(Iterations, *ToInvariance);
+      if (Iterations == MaxIterations)
+        break;
+    }
   }
+  assert((Iterations <= MaxIterations) && "bad result in phi analysis");
+  return Iterations ? Optional<unsigned>(Iterations) : None;
+}
+
+} // unnamed namespace
 
 // Try to find any invariant memory reads that will become dereferenceable in
 // the remainder loop after peeling. The load must also be used (transitively)
 // by an exit condition. Returns the number of iterations to peel off (at the
 // moment either 0 or 1).
 static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L,
                                                       DominatorTree &DT,
                                                       AssumptionCache *AC) {
void llvm::computePeelCount(Loop *L, unsigned LoopSize,
 
   unsigned AlreadyPeeled = 0;
   if (auto Peeled = getOptionalIntLoopAttribute(L, PeeledCountMetaData))
     AlreadyPeeled = *Peeled;
   // Stop if we already peeled off the maximum number of iterations.
   if (AlreadyPeeled >= UnrollPeelMaxCount)
     return;
 
+  // Pay respect to limitations implied by loop size and the max peel count.
+  unsigned MaxPeelCount = UnrollPeelMaxCount;
+  MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1);
+
+  // Start the max computation with the PP.PeelCount value set by the target
+  // in TTI.getPeelingPreferences or by the flag -unroll-peel-count.
+  unsigned DesiredPeelCount = TargetPeelCount;
+
   // Here we try to get rid of Phis which become invariants after 1, 2, ..., N
   // iterations of the loop. For this we compute the number for iterations after
   // which every Phi is guaranteed to become an invariant, and try to peel the
   // maximum number of iterations among these values, thus turning all those
   // Phis into invariants.
-
-  // Store the pre-calculated values here.
-  SmallDenseMap<PHINode *, Optional<unsigned>> IterationsToInvariance;
-  // Now go through all Phis to calculate their the number of iterations they
-  // need to become invariants.
-  // Start the max computation with the PP.PeelCount value set by the target
-  // in TTI.getPeelingPreferences or by the flag -unroll-peel-count.
-  unsigned DesiredPeelCount = TargetPeelCount;
-  BasicBlock *BackEdge = L->getLoopLatch();
-  assert(BackEdge && "Loop is not in simplified form?");
-  for (auto BI = L->getHeader()->begin(); isa<PHINode>(&*BI); ++BI) {
-    PHINode *Phi = cast<PHINode>(&*BI);
-    auto ToInvariance = calculateIterationsToInvariance(Phi, L, BackEdge,
-                                                        IterationsToInvariance);
-    if (ToInvariance)
-      DesiredPeelCount = std::max(DesiredPeelCount, *ToInvariance);
+  if (MaxPeelCount > DesiredPeelCount) {
+    // Check how many iterations are useful for resolving Phis
+    auto NumPeels = PhiAnalyzer(*L, MaxPeelCount).calculateIterationsToPeel();
+    if (NumPeels)
+      DesiredPeelCount = std::max(DesiredPeelCount, *NumPeels);
   }
 
-  // Pay respect to limitations implied by loop size and the max peel count.
-  unsigned MaxPeelCount = UnrollPeelMaxCount;
-  MaxPeelCount = std::min(MaxPeelCount, Threshold / LoopSize - 1);
-
   DesiredPeelCount = std::max(DesiredPeelCount,
                               countToEliminateCompares(*L, MaxPeelCount, SE));
 
   if (DesiredPeelCount == 0)
     DesiredPeelCount = peelToTurnInvariantLoadsDerefencebale(*L, DT, AC);
 
   if (DesiredPeelCount > 0) {
     DesiredPeelCount = std::min(DesiredPeelCount, MaxPeelCount);

llvm/test/Transforms/LoopUnroll/peel-loop-phi-analysis.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Check that phi analysis can determine the number of iterations of the
+; loop to peel such that the phi nodes (other than the iteration variable)
+; have their resulting values known and are thus removed by peeling the loop
+; at least that many times.
+
+; RUN: opt < %s -S -passes=loop-unroll | FileCheck %s
+; RUN: opt < %s -S -passes=loop-unroll-full | FileCheck %s
+
+; void f(float);
+; void g(int);
+declare void @_Z1ff(float)
+declare void @_Z1gi(i32 signext)
+
+; Check that phi analysis can handle a cast.
+define void @_Z8castTestv() {
+; The phis become invariant through the chain of phis, with a unary
+; instruction on a loop invariant.  Check that the phis for x, a, and y
+; are removed since x is based on a cast of y, which is based on a, which is
+; set on the backedge.
+; Consider the calls to g and f.
+; First iteration: g(0), x=0, f(0.0), y=0.0, a=5.0
+; Second iteration: g(0), x=0, f(0.0), y=5.0, a=5.0
+; Third iteration: g(0), x=5 (requires cast), f(5.0), a=5.0
+; Fourth iteration (and subsequent): g(5), x=5, f(5.0), a=5.0
+; Therefore, peeling 3 times removes the phi nodes, so check for 3 peels.
+; CURRENT LIMITATION: only peels twice because cannot handle cast
+;
+; void castTest() {
+;   int x = 0;
+;   float y = 0.0;
+;   float a = 0.0;
+;   for(int i = 0; i <100000; ++i) {
+;     g(x);
+;     x = y;
+;     f(y);
+;     y = a;
+;     a = 5.0;
+;   }
+; }
+;
+; CHECK-LABEL: @_Z8castTestv(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
+; CHECK:       for.body.peel.begin:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
+; CHECK:       for.body.peel:
+; CHECK-NEXT:    tail call void @_Z1gi(i32 noundef signext 0)
+; CHECK-NEXT:    [[CONV_PEEL:%.*]] = fptosi float 0.000000e+00 to i32
+; CHECK-NEXT:    tail call void @_Z1ff(float noundef 0.000000e+00)
+; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nuw nsw i32 0, 1
+; CHECK-NEXT:    [[EXITCOND_PEEL:%.*]] = icmp ne i32 [[INC_PEEL]], 100000
+; CHECK-NEXT:    br i1 [[EXITCOND_PEEL]], label [[FOR_BODY_PEEL_NEXT:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.body.peel.next:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL2:%.*]]
+; CHECK:       for.body.peel2:
+; CHECK-NEXT:    tail call void @_Z1gi(i32 noundef signext [[CONV_PEEL]])
+; CHECK-NEXT:    [[CONV_PEEL3:%.*]] = fptosi float 0.000000e+00 to i32
+; CHECK-NEXT:    tail call void @_Z1ff(float noundef 0.000000e+00)
+; CHECK-NEXT:    [[INC_PEEL4:%.*]] = add nuw nsw i32 [[INC_PEEL]], 1
+; CHECK-NEXT:    [[EXITCOND_PEEL5:%.*]] = icmp ne i32 [[INC_PEEL4]], 100000
+; CHECK-NEXT:    br i1 [[EXITCOND_PEEL5]], label [[FOR_BODY_PEEL_NEXT1:%.*]], label [[FOR_COND_CLEANUP]]
+; CHECK:       for.body.peel.next1:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT6:%.*]]
+; CHECK:       for.body.peel.next6:
+; CHECK-NEXT:    br label [[ENTRY_PEEL_NEWPH:%.*]]
+; CHECK:       entry.peel.newph:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup.loopexit:
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INC_PEEL4]], [[ENTRY_PEEL_NEWPH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[CONV_PEEL3]], [[ENTRY_PEEL_NEWPH]] ], [ 5, [[FOR_BODY]] ]
+; CHECK-NEXT:    tail call void @_Z1gi(i32 noundef signext [[X]])
+; CHECK-NEXT:    tail call void @_Z1ff(float noundef 5.000000e+00)
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[INC]], 100000
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %a = phi float [ 0.000000e+00, %entry ], [ 5.000000e+00, %for.body ]
+  %y = phi float [ 0.000000e+00, %entry ], [ %a, %for.body ]
+  %x = phi i32 [ 0, %entry ], [ %conv, %for.body ]
+  tail call void @_Z1gi(i32 noundef signext %x)
+  %conv = fptosi float %y to i32
+  tail call void @_Z1ff(float noundef %y)
+  %inc = add nuw nsw i32 %i, 1
+  %exitcond = icmp ne i32 %inc, 100000
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}
+
+; Check that phi analysis can handle a binary operator.
+define void @_Z6binaryv() {
+; The phis become invariant through the chain of phis, with a unary
+; instruction on a loop invariant.  Check that the phis for x, a, and y
+; are removed since x is based on y, which is based on a, which is based
+; on a binary add of a phi and a constant.
+; Consider the calls to g:
+; First iteration: g(0), x=0, g(0), y=1, a=5
+; Second iteration: g(0), x=1, g(5), y=6(binary operator), a=5
+; Third iteration: g(1), x=6, g(5), y=6, a=5
+; Fourth iteration (and subsequent): g(6), x=6, g(5), y=6, a=5
+; Therefore, peeling 3 times removes the phi nodes.
+; CURRENT_LIMITATION: only peels once because cannot handle binary operator
+;
+; void g(int);
+; void binary() {
+;   int x = 0;
+;   int y = 0;
+;   int a = 0;
+;   for(int i = 0; i <100000; ++i) {
+;     g(x);
+;     x = y;
+;     g(a);
+;     y = a + 1;
+;     a = 5;
+;   }
+; }
+;
+; CHECK-LABEL: @_Z6binaryv(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_BEGIN:%.*]]
+; CHECK:       for.body.peel.begin:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL:%.*]]
+; CHECK:       for.body.peel:
+; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 0)
+; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 0)
+; CHECK-NEXT:    [[ADD_PEEL:%.*]] = add nuw nsw i32 0, 1
+; CHECK-NEXT:    [[INC_PEEL:%.*]] = add nuw nsw i32 0, 1
+; CHECK-NEXT:    [[EXITCOND_PEEL:%.*]] = icmp eq i32 [[INC_PEEL]], 100000
+; CHECK-NEXT:    br i1 [[EXITCOND_PEEL]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY_PEEL_NEXT:%.*]]
+; CHECK:       for.body.peel.next:
+; CHECK-NEXT:    br label [[FOR_BODY_PEEL_NEXT1:%.*]]
+; CHECK:       for.body.peel.next1:
+; CHECK-NEXT:    br label [[ENTRY_PEEL_NEWPH:%.*]]
+; CHECK:       entry.peel.newph:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond.cleanup.loopexit:
+; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INC_PEEL]], [[ENTRY_PEEL_NEWPH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[ADD_PEEL]], [[ENTRY_PEEL_NEWPH]] ], [ 6, [[FOR_BODY]] ]
+; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 0, [[ENTRY_PEEL_NEWPH]] ], [ [[Y]], [[FOR_BODY]] ]
+; CHECK-NEXT:    tail call void @_Z1gi(i32 signext [[X]])
+; CHECK-NEXT:    tail call void @_Z1gi(i32 signext 5)
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 100000
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY]], !llvm.loop [[LOOP2:![0-9]+]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %a = phi i32 [ 0, %entry ], [ 5, %for.body ]
+  %y = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %x = phi i32 [ 0, %entry ], [ %y, %for.body ]
+  tail call void @_Z1gi(i32 signext %x)
+  tail call void @_Z1gi(i32 signext %a)
+  %add = add nuw nsw i32 %a, 1
+  %inc = add nuw nsw i32 %i, 1
+  %exitcond = icmp eq i32 %inc, 100000
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+