Index: llvm/lib/Transforms/Utils/LoopPeel.cpp =================================================================== --- llvm/lib/Transforms/Utils/LoopPeel.cpp +++ llvm/lib/Transforms/Utils/LoopPeel.cpp @@ -79,6 +79,196 @@ static const char *PeeledCountMetaData = "llvm.loop.peeled.count"; +namespace { + +// As a loop is peeled, it may be the case that Phi nodes become +// deterministic (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) { +// if (i > 10) +// g(1); +// else +// g(2); +// g(x); +// x = y; +// g(a); +// y = a + 1; +// a = 5; +// } +// } +// This is not a typical loop for peeling because the conditional does not +// vary in the initial iterations. However, 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 +// +// Ignoring the calls to g in the conditional, the parameters for the +// other 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 parameters 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(Loop *L, unsigned MaxIterations); + + // Calculate the allowable maximum number of iterations of the loop to peel + // such that phi instructions become determined + Optional calculateIterationsToPeel(); + +protected: + static Loop &checkLoop(Loop *); + static BasicBlock &getBackEdge(Loop *); + + // Add 1 respecting Infinity and return Infinity if result over MaxIterations + unsigned addOne(unsigned N) const { + return N >= MaxIterations ? Infinity : N + 1; + } + + // Calculate the number of iterations after which the given value + // becomes an invariant. + unsigned calculate(const Value *); + + Loop &L; + BasicBlock &BackEdge; + + const unsigned MaxIterations; + + // Designates that a Phi is estimated to become invariant after an + // "infinite" number of loop iterations (i.e. only may become an + // invariant if the loop is fully unrolled). + const unsigned Infinity; + + // Map of Values to number of iterations to invariance + std::map IterationsToInvariance; +}; + +inline Loop &PhiAnalyzer::checkLoop(Loop *L) { + assert(L && canPeel(L) && "Loop is not suitable for peeling."); + return *L; +} + +inline BasicBlock &PhiAnalyzer::getBackEdge(Loop *L) { + assert(L && L->getLoopLatch() && "Loop does not have latch."); + return *L->getLoopLatch(); +} + +inline PhiAnalyzer::PhiAnalyzer(Loop *LP, unsigned M) + : L(checkLoop(LP)), BackEdge(getBackEdge(LP)), MaxIterations(M), + Infinity(MaxIterations + 1) { + 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 <= MaxIterations or Infinity. +// The function is calculated according to the following definition: +// Given %x = phi , ..., [%y, %back.edge]. +// F(%x) = G(%y) + 1 (N.B. [MaxIterations | Infinity] + 1 => Infinity) +// G(%y) = 0 if %y is a loop invariant +// G(%y) = G(%BackEdgeValue) if %y is a phi in the header block +// G(%y) = G(), if %y is a cast +// G(%y) = max(G(),G()), if %y is a binary op +// G(%y) = Infinity otherwise (including phi not in header block) +unsigned PhiAnalyzer::calculate(const Value *V) { + assert(V && "expected value to be non-null"); + + // If we already know the answer, take it from the map. + auto I = IterationsToInvariance.find(V); + if (I != IterationsToInvariance.end()) + return I->second; + + // Place Infinity to map to avoid infinite recursion. Such + // cycles can never stop on an invariant. + IterationsToInvariance[V] = Infinity; + + if (const PHINode *Phi = dyn_cast(V)) { + if (Phi->getParent() != L.getHeader()) { + // Phi is not in header block so Infinity. + assert(IterationsToInvariance[V] == Infinity && "unexpected value saved"); + return Infinity; + } + // We need to analyze the input from the back edge and add 1. + Value *Input = Phi->getIncomingValueForBlock(&BackEdge); + unsigned Iterations = calculate(Input); + assert(IterationsToInvariance[Input] == Iterations && + "unexpected value saved"); + return (IterationsToInvariance[Phi] = addOne(Iterations)); + } + if (const Instruction *I = dyn_cast(V)) { + if (isa(I) || I->isBinaryOp()) { + // Binary instructions get the max of the operands. + assert(I->getOperand(0) && I->getOperand(1) && "bad binary op"); + + unsigned LHS = calculate(I->getOperand(0)); + return (IterationsToInvariance[I] = + (LHS == Infinity) + ? Infinity + : std::max(LHS, calculate(I->getOperand(1)))); + } + if (I->isCast()) { + // Cast instructions get the value of the operand. + assert(I->getOperand(0) && "bad cast op"); + + return (IterationsToInvariance[I] = calculate(I->getOperand(0))); + } + } + if (L.isLoopInvariant(V)) { + // Loop invariant so known at start. + return (IterationsToInvariance[V] = 0); + } + // Everything else gets Infinity. + assert(IterationsToInvariance[V] == Infinity && "unexpected value saved"); + return Infinity; +} + +Optional PhiAnalyzer::calculateIterationsToPeel() { + unsigned Iterations = 0; + for (auto I = L.getHeader()->begin(); isa(&*I); ++I) { + unsigned ToInvariance = calculate(&*I); + if (ToInvariance != Infinity) { + assert(ToInvariance <= MaxIterations && "bad result in phi analysis"); + Iterations = std::max(Iterations, ToInvariance); + } + } + assert(Iterations <= MaxIterations && "bad result in phi analysis"); + return Iterations ? Optional(Iterations) : None; +} + +} // unnamed namespace + // Check whether we are capable of peeling this loop. bool llvm::canPeel(Loop *L) { // Make sure the loop is in simplified form @@ -100,57 +290,6 @@ 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: -// Given %x = phi , ..., [%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 calculateIterationsToInvariance( - PHINode *Phi, Loop *L, BasicBlock *BackEdge, - SmallDenseMap > &IterationsToInvariance) { - assert(Phi->getParent() == L->getHeader() && - "Non-loop Phi should not be checked for turning into invariant."); - assert(BackEdge == L->getLoopLatch() && "Wrong latch?"); - // If we already know the answer, take it from the map. - auto I = IterationsToInvariance.find(Phi); - 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 - // cycles can never stop on an invariant. - IterationsToInvariance[Phi] = None; - Optional ToInvariance; - - if (L->isLoopInvariant(Input)) - ToInvariance = 1u; - else if (PHINode *IncPhi = dyn_cast(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; -} - // 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 @@ -395,33 +534,26 @@ 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> 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(&*BI); ++BI) { - PHINode *Phi = cast(&*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)); Index: llvm/test/Transforms/LoopUnroll/peel-loop-phi-analysis.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopUnroll/peel-loop-phi-analysis.ll @@ -0,0 +1,153 @@ +; 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 -loop-unroll | FileCheck %s +; 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. +; +; 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; +; } +; } + +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-LABEL: @_Z8castTestv +; CHECK-LABEL: for.body.peel: +; CHECK-NOT: %{{.*}} = phi +; CHECK-NOT: br +; CHECK: tail call void @_Z1gi(i32 noundef signext 0) +; CHECK: [[CONV_PEEL_1:%.*]] = fptosi float 0.000000e+00 to i32 +; CHECK: tail call void @_Z1ff(float noundef 0.000000e+00) +; CHECK-LABEL: {{for\.body\.peel[0-9]*}}: +; CHECK-NOT: %{{.*}} = phi +; CHECK-NOT: br +; CHECK: tail call void @_Z1gi(i32 noundef signext [[CONV_PEEL_1]]) +; CHECK: [[CONV_PEEL_2:%.*]] = fptosi float 0.000000e+00 to i32 +; CHECK: tail call void @_Z1ff(float noundef 0.000000e+00) +; CHECK-LABEL: {{for\.body\.peel[0-9]*}}: +; CHECK: tail call void @_Z1gi(i32 noundef signext [[CONV_PEEL_2]]) +; CHECK: [[CONV_PEEL_3:%.*]] = fptosi float 5.000000e+00 to i32 +; CHECK: tail call void @_Z1ff(float noundef 5.000000e+00) +; CHECK-LABEL-NOT: {{for\.body\.peel[0-9]*}}: +; CHECK-LABEL: for.body: +; CHECK: [[PHI:%.*]] = phi i32 [ [[CONV_PEEL_3]], %entry.peel.newph ], [ 5, %for.body ] +; CHECK: tail call void @_Z1gi(i32 noundef signext [[PHI]]) +; CHECK: tail call void @_Z1ff(float noundef 5.000000e+00) + +; 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. +; +; 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; +; } +; } + +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 +} + +; CHECK-LABEL: @_Z6binaryv +; CHECK-LABEL: for.body.peel: +; CHECK-NOT: %{{.*}} = phi +; CHECK-NOT: br +; CHECK: tail call void @_Z1gi(i32 signext 0) +; CHECK: tail call void @_Z1gi(i32 signext 0) +; CHECK: [[ADD:%.*]] = add nuw nsw i32 0, 1 +; CHECK-LABEL: {{for\.body\.peel[0-9]*}}: +; CHECK-NOT: %{{.*}} = phi +; CHECK-NOT: br +; CHECK: tail call void @_Z1gi(i32 signext 0) +; CHECK: tail call void @_Z1gi(i32 signext 5) +; CHECK-LABEL: {{for\.body\.peel[0-9]*}}: +; CHECK-NOT: %{{.*}} = phi +; CHECK-NOT: br +; CHECK: tail call void @_Z1gi(i32 signext [[ADD]]) +; CHECK: tail call void @_Z1gi(i32 signext 5) +; CHECK-LABEL-NOT: {{for\.body\.peel[0-9]*}}: +; CHECK-LABEL: for.body: +; CHECK-NOT: br +; CHECK: [[I_IN:%.*]] = phi i32 [ {{.*}}, {{.*}} ], [ [[INC:%.*]], %for.body ] +; CHECK: tail call void @_Z1gi(i32 signext 6) +; CHECK: tail call void @_Z1gi(i32 signext 5) +; CHECK: [[INC]] = add nuw nsw i32 [[I_IN]], 1 +