Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -2443,84 +2443,122 @@ while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) ++Idx; - // Scan over all recurrences, trying to fold loop invariants into them. - for (; Idx < Ops.size() && isa(Ops[Idx]); ++Idx) { - // Scan all of the other operands to this add and add them to the vector if - // they are loop invariant w.r.t. the recurrence. - SmallVector LIOps; - const SCEVAddRecExpr *AddRec = cast(Ops[Idx]); - const Loop *AddRecLoop = AddRec->getLoop(); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - if (isLoopInvariant(Ops[i], AddRecLoop)) { + if (Idx < Ops.size() && Ops[Idx]->getSCEVType() == scAddRecExpr) { + // We might have more than one recurrent operands from different loops at + // this point. As a first step, we should choose the right recurrence among + // them. Obviously, all operands should be visible from the place where we + // use them, what means that we need to find a point that is dominated by + // all these loop headers. So we look for the 'bottom-most' loop in terms of + // headers domination. + const SCEVAddRecExpr *BaseAddRec = cast(Ops[Idx]); + for (unsigned i = Idx + 1; + i < Ops.size() && isa(Ops[i]); ++i) { + const SCEVAddRecExpr *Candidate = cast(Ops[i]); + if (BaseAddRec->getLoop() != Candidate->getLoop() && + DT.dominates(BaseAddRec->getLoop()->getHeader(), + Candidate->getLoop()->getHeader())) { + Idx = i; + BaseAddRec = Candidate; + } else + assert(DT.dominates(Candidate->getLoop()->getHeader(), + BaseAddRec->getLoop()->getHeader()) && + "No domination relationships between two used AddRecs?"); + } + + // Now, we have found the 'bottom-most' recurrence. If we have more than one + // recurrence in this loop, we can combine them into one. If we have values + // that are invariant w.r.t. this loop, we can combine them with the + // recurrence. In order to do that, split all operands into three types: + // 1) Recurrencies from the same loop as base add rec (base loop); + // 2) Invariants in the loop of AddRec; + // 3) All others. + const Loop *BaseLoop = BaseAddRec->getLoop(); + SmallVector BaseLoopRecs; + SmallVector LIOps; + for (unsigned i = 0, e = Ops.size(); i != e;) { + if (isLoopInvariant(Ops[i], BaseLoop)) { LIOps.push_back(Ops[i]); - Ops.erase(Ops.begin()+i); - --i; --e; - } - - // If we found some loop invariants, fold them into the recurrence. + Ops.erase(Ops.begin() + i); + if (i < Idx) + --Idx; + --e; + } else if (isa(Ops[i]) && + cast(Ops[i])->getLoop() == BaseLoop) { + BaseLoopRecs.push_back(cast(Ops[i])); + if (i != Idx) { + // Keep the base AddRec in Ops so that we could later replace it with + // a new expression and, thus, preserve the order of operands. + Ops.erase(Ops.begin() + i); + --e; + } else + ++i; + } else + ++i; + } + + // By this moment, Ops contains non-invariant the values that cannot be + // optimized away and the BaseAddRec which will be replaced in future. + assert(!BaseLoopRecs.empty() && "No AddRecExpr's in the base loop?"); + assert(BaseLoopRecs[0] == BaseAddRec && "Base add rec was not the first?"); + assert(!Ops.empty() && "At least the BaseAddRec should be kept in Ops!"); + assert(Ops[Idx] == BaseAddRec && "Bad placement of BaseAddRec?"); + + // If we have invariants, combine them with the base add recurrence: + // Inv1 + Inv2 + {Start,+,Step} --> {Inv1 + Inv2 + Start,+,Step}. if (!LIOps.empty()) { - // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step} - LIOps.push_back(AddRec->getStart()); - - SmallVector AddRecOps(AddRec->op_begin(), - AddRec->op_end()); + LIOps.push_back(BaseAddRec->getStart()); + SmallVector NewAddRecOps(BaseAddRec->op_begin(), + BaseAddRec->op_end()); // This follows from the fact that the no-wrap flags on the outer add // expression are applicable on the 0th iteration, when the add recurrence // will be equal to its start value. - AddRecOps[0] = getAddExpr(LIOps, Flags, Depth + 1); - + NewAddRecOps[0] = getAddExpr(LIOps, Flags, Depth + 1); // Build the new addrec. Propagate the NUW and NSW flags if both the // outer add and the inner addrec are guaranteed to have no overflow. // Always propagate NW. - Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW)); - const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags); - - // If all of the other operands were loop invariant, we are done. - if (Ops.size() == 1) return NewRec; + Flags = BaseAddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW)); + // The result is guaranteed to be an AddRecExpr here because we don't + // change the step. + BaseLoopRecs[0] = BaseAddRec = + cast(getAddRecExpr(NewAddRecOps, BaseLoop, Flags)); + } + + // If we have more than one recurrence from the base loop, combine them: + // {A,+,B} + {C,+,D} + {E,+,F} --> {A + C + E,+,B + D + F}. + const SCEV *NewRec = BaseAddRec; + if (BaseLoopRecs.size() > 1) { + // We may have recs of different degree, so handle them carefully: + // {A,+,B} + {C,+,D,+,E} --> {A+C,+,B+D,+,E}. + size_t MaxArgs = 0; + for (auto It : BaseLoopRecs) + MaxArgs = std::max(MaxArgs, It->getNumOperands()); + + SmallVector NewAddRecOps; + // Add the operands of same degree together. + for (unsigned i = 0; i < MaxArgs; i++) { + SmallVector CurrentOps; + for (unsigned j = 0; j < BaseLoopRecs.size(); ++j) + if (BaseLoopRecs[j]->getNumOperands() > i) + CurrentOps.push_back(BaseLoopRecs[j]->getOperand(i)); + // If only one operand of this order has been found, take it. Otherwise + // sum the operands we have. + if (CurrentOps.size() == 1) + NewAddRecOps.push_back(CurrentOps[0]); + else + NewAddRecOps.push_back( + getAddExpr(CurrentOps, SCEV::FlagAnyWrap, Depth + 1)); + } - // Otherwise, add the folded AddRec by the non-invariant parts. - for (unsigned i = 0;; ++i) - if (Ops[i] == AddRec) { - Ops[i] = NewRec; - break; - } - return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); + // Step size has changed, so we cannot guarantee no self-wraparound. + NewRec = getAddRecExpr(NewAddRecOps, BaseLoop, SCEV::FlagAnyWrap); } - // Okay, if there weren't any loop invariants to be folded, check to see if - // there are multiple AddRec's with the same loop induction variable being - // added together. If so, we can fold them. - for (unsigned OtherIdx = Idx+1; - OtherIdx < Ops.size() && isa(Ops[OtherIdx]); - ++OtherIdx) - if (AddRecLoop == cast(Ops[OtherIdx])->getLoop()) { - // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} - SmallVector AddRecOps(AddRec->op_begin(), - AddRec->op_end()); - for (; OtherIdx != Ops.size() && isa(Ops[OtherIdx]); - ++OtherIdx) - if (const auto *OtherAddRec = dyn_cast(Ops[OtherIdx])) - if (OtherAddRec->getLoop() == AddRecLoop) { - for (unsigned i = 0, e = OtherAddRec->getNumOperands(); - i != e; ++i) { - if (i >= AddRecOps.size()) { - AddRecOps.append(OtherAddRec->op_begin()+i, - OtherAddRec->op_end()); - break; - } - SmallVector TwoOps = { - AddRecOps[i], OtherAddRec->getOperand(i)}; - AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); - } - Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; - } - // Step size has changed, so we cannot guarantee no self-wraparound. - Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap); - return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); - } - - // Otherwise couldn't fold anything into this recurrence. Move onto the - // next one. + // If we still have non-invariants that are not folded, we should + // proceed to the next step. Otherwise, we are done. + if (Ops.size() == 1) + return NewRec; + else + Ops[Idx] = NewRec; } // Okay, it looks like we really DO need an add expr. Check to see if we Index: test/Analysis/ScalarEvolution/different-loops-recs.ll =================================================================== --- test/Analysis/ScalarEvolution/different-loops-recs.ll +++ test/Analysis/ScalarEvolution/different-loops-recs.ll @@ -0,0 +1,350 @@ +; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s + +; This test set ensures that we can correctly operate with recurrencies from +; different loops. + +; Check that we can evaluate a sum of phis from two different loops in any +; order. + +define void @test_00() { + +; CHECK-LABEL: Classifying expressions for: @test_00 +; CHECK: %sum1 = add i32 %phi1, %phi2 +; CHECK-NEXT: --> {14,+,3}<%loop1> +; CHECK: %sum2 = add i32 %sum1, %phi3 +; CHECK-NEXT: --> {20,+,6}<%loop1> +; CHECK: %sum3 = add i32 %phi4, %phi5 +; CHECK-NEXT: --> {116,+,3}<%loop2> +; CHECK: %sum4 = add i32 %sum3, %phi6 +; CHECK-NEXT: --> {159,+,6}<%loop2> +; CHECK: %s1 = add i32 %phi1, %phi4 +; CHECK-NEXT: --> {{{{}}73,+,1}<%loop1>,+,1}<%loop2> +; CHECK: %s2 = add i32 %phi5, %phi2 +; CHECK-NEXT: --> {{{{}}57,+,2}<%loop1>,+,2}<%loop2> +; CHECK: %s3 = add i32 %sum1, %sum3 +; CHECK-NEXT: --> {{{{}}130,+,3}<%loop1>,+,3}<%loop2> +; CHECK: %s4 = add i32 %sum4, %sum2 +; CHECK-NEXT: --> {{{{}}179,+,6}<%loop1>,+,6}<%loop2> +; CHECK: %s5 = add i32 %phi3, %sum3 +; CHECK-NEXT: --> {{{{}}122,+,3}<%loop1>,+,3}<%loop2> +; CHECK: %s6 = add i32 %sum2, %phi6 +; CHECK-NEXT: --> {{{{}}63,+,6}<%loop1>,+,3}<%loop2> + +entry: + br label %loop1 + +loop1: + %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1 ] + %phi2 = phi i32 [ 4, %entry ], [ %phi2.inc, %loop1 ] + %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] + %phi1.inc = add i32 %phi1, 1 + %phi2.inc = add i32 %phi2, 2 + %phi3.inc = add i32 %phi3, 3 + %sum1 = add i32 %phi1, %phi2 + %sum2 = add i32 %sum1, %phi3 + %cond1 = icmp ult i32 %sum2, 1000 + br i1 %cond1, label %loop1, label %loop2 + +loop2: + %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ] + %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ] + %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] + %phi4.inc = add i32 %phi4, 1 + %phi5.inc = add i32 %phi5, 2 + %phi6.inc = add i32 %phi6, 3 + %sum3 = add i32 %phi4, %phi5 + %sum4 = add i32 %sum3, %phi6 + %cond2 = icmp ult i32 %sum4, 1000 + br i1 %cond2, label %loop2, label %exit + +exit: + %s1 = add i32 %phi1, %phi4 + %s2 = add i32 %phi5, %phi2 + %s3 = add i32 %sum1, %sum3 + %s4 = add i32 %sum4, %sum2 + %s5 = add i32 %phi3, %sum3 + %s6 = add i32 %sum2, %phi6 + ret void +} + +; Check that we can evaluate a sum of phis+invariants from two different loops +; in any order. + +define void @test_01(i32 %a, i32 %b) { + +; CHECK-LABEL: Classifying expressions for: @test_01 +; CHECK: %sum1 = add i32 %phi1, %phi2 +; CHECK-NEXT: --> {(%a + %b),+,3}<%loop1> +; CHECK: %sum2 = add i32 %sum1, %phi3 +; CHECK-NEXT: --> {(6 + %a + %b),+,6}<%loop1> +; CHECK: %is1 = add i32 %sum2, %a +; CHECK-NEXT: --> {(6 + (2 * %a) + %b),+,6}<%loop1> +; CHECK: %sum3 = add i32 %phi4, %phi5 +; CHECK-NEXT: --> {116,+,3}<%loop2> +; CHECK: %sum4 = add i32 %sum3, %phi6 +; CHECK-NEXT: --> {159,+,6}<%loop2> +; CHECK: %is2 = add i32 %sum4, %b +; CHECK-NEXT: --> {(159 + %b),+,6}<%loop2> +; CHECK: %ec2 = add i32 %is1, %is2 +; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> +; CHECK: %s1 = add i32 %phi1, %is1 +; CHECK-NEXT: --> {(6 + (3 * %a) + %b),+,7}<%loop1> +; CHECK: %s2 = add i32 %is2, %phi4 +; CHECK-NEXT: --> {(222 + %b),+,7}<%loop2> +; CHECK: %s3 = add i32 %is1, %phi5 +; CHECK-NEXT: --> {{{{}}(59 + (2 * %a) + %b),+,6}<%loop1>,+,2}<%loop2> +; CHECK: %s4 = add i32 %phi2, %is2 +; CHECK-NEXT: --> {{{{}}(159 + (2 * %b)),+,2}<%loop1>,+,6}<%loop2> +; CHECK: %s5 = add i32 %is1, %is2 +; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> +; CHECK: %s6 = add i32 %is2, %is1 +; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> + +entry: + br label %loop1 + +loop1: + %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] + %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ] + %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] + %phi1.inc = add i32 %phi1, 1 + %phi2.inc = add i32 %phi2, 2 + %phi3.inc = add i32 %phi3, 3 + %sum1 = add i32 %phi1, %phi2 + %sum2 = add i32 %sum1, %phi3 + %is1 = add i32 %sum2, %a + %cond1 = icmp ult i32 %is1, 1000 + br i1 %cond1, label %loop1, label %loop2 + +loop2: + %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ] + %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ] + %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] + %phi4.inc = add i32 %phi4, 1 + %phi5.inc = add i32 %phi5, 2 + %phi6.inc = add i32 %phi6, 3 + %sum3 = add i32 %phi4, %phi5 + %sum4 = add i32 %sum3, %phi6 + %is2 = add i32 %sum4, %b + %ec2 = add i32 %is1, %is2 + %cond2 = icmp ult i32 %ec2, 1000 + br i1 %cond2, label %loop2, label %exit + +exit: + %s1 = add i32 %phi1, %is1 + %s2 = add i32 %is2, %phi4 + %s3 = add i32 %is1, %phi5 + %s4 = add i32 %phi2, %is2 + %s5 = add i32 %is1, %is2 + %s6 = add i32 %is2, %is1 + ret void +} + +; Check that we can correctly evaluate a sum of phis+variants from two different +; loops in any order. + +define void @test_02(i32 %a, i32 %b, i32* %p) { + +; CHECK-LABEL: Classifying expressions for: @test_02 +; CHECK: %sum1 = add i32 %phi1, %phi2 +; CHECK-NEXT: --> {(%a + %b),+,3}<%loop1> +; CHECK: %sum2 = add i32 %sum1, %phi3 +; CHECK-NEXT: --> {(6 + %a + %b),+,6}<%loop1> +; CHECK: %is1 = add i32 %sum2, %v1 +; CHECK-NEXT: --> ({(6 + %a + %b),+,6}<%loop1> + %v1) +; CHECK: %sum3 = add i32 %phi4, %phi5 +; CHECK-NEXT: --> {(%a + %b),+,3}<%loop2> +; CHECK: %sum4 = add i32 %sum3, %phi6 +; CHECK-NEXT: --> {(43 + %a + %b),+,6}<%loop2> +; CHECK: %is2 = add i32 %sum4, %v2 +; CHECK-NEXT: --> ({(43 + %a + %b),+,6}<%loop2> + %v2) +; CHECK: %is3 = add i32 %v1, %sum2 +; CHECK-NEXT: --> ({(6 + %a + %b),+,6}<%loop1> + %v1) +; CHECK: %ec2 = add i32 %is1, %is3 +; CHECK-NEXT: --> (2 * ({(6 + %a + %b),+,6}<%loop1> + %v1)) +; CHECK: %s1 = add i32 %phi1, %is1 +; CHECK-NEXT: --> ({(6 + (2 * %a) + %b),+,7}<%loop1> + %v1) +; CHECK: %s2 = add i32 %is2, %phi4 +; CHECK-NEXT: --> ({(43 + (2 * %a) + %b),+,7}<%loop2> + %v2) +; CHECK: %s3 = add i32 %is1, %phi5 +; CHECK-NEXT: --> {({(6 + (2 * %b) + %a),+,6}<%loop1> + %v1),+,2}<%loop2> +; CHECK: %s4 = add i32 %phi2, %is2 +; CHECK-NEXT: --> ({{{{}}(43 + (2 * %b) + %a),+,2}<%loop1>,+,6}<%loop2> + %v2) +; CHECK: %s5 = add i32 %is1, %is2 +; CHECK-NEXT: --> ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2) +; CHECK: %s6 = add i32 %is2, %is1 +; CHECK-NEXT: --> ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2) + +entry: + br label %loop1 + +loop1: + %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] + %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ] + %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] + %phi1.inc = add i32 %phi1, 1 + %phi2.inc = add i32 %phi2, 2 + %phi3.inc = add i32 %phi3, 3 + %v1 = load i32, i32* %p + %sum1 = add i32 %phi1, %phi2 + %sum2 = add i32 %sum1, %phi3 + %is1 = add i32 %sum2, %v1 + %cond1 = icmp ult i32 %is1, 1000 + br i1 %cond1, label %loop1, label %loop2 + +loop2: + %phi4 = phi i32 [ %a, %loop1 ], [ %phi4.inc, %loop2 ] + %phi5 = phi i32 [ %b, %loop1 ], [ %phi5.inc, %loop2 ] + %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] + %phi4.inc = add i32 %phi4, 1 + %phi5.inc = add i32 %phi5, 2 + %phi6.inc = add i32 %phi6, 3 + %v2 = load i32, i32* %p + %sum3 = add i32 %phi4, %phi5 + %sum4 = add i32 %sum3, %phi6 + %is2 = add i32 %sum4, %v2 + %is3 = add i32 %v1, %sum2 + %ec2 = add i32 %is1, %is3 + %cond2 = icmp ult i32 %ec2, 1000 + br i1 %cond2, label %loop2, label %exit + +exit: + %s1 = add i32 %phi1, %is1 + %s2 = add i32 %is2, %phi4 + %s3 = add i32 %is1, %phi5 + %s4 = add i32 %phi2, %is2 + %s5 = add i32 %is1, %is2 + %s6 = add i32 %is2, %is1 + ret void +} + +; Mix of previous use cases that demonstrates %s3 can be incorrectly treated as +; a recurrence of loop1 because of operands order if we pick recurrencies in an +; incorrect order. + +define void @test_03(i32 %a, i32 %b, i32 %c, i32* %p) { + +; CHECK-LABEL: Classifying expressions for: @test_03 +; CHECK: %v1 = load i32, i32* %p +; CHECK-NEXT: --> %v1 +; CHECK: %s1 = add i32 %phi1, %v1 +; CHECK-NEXT: --> {(%a + %v1),+,1}<%loop1> +; CHECK: %s2 = add i32 %s1, %b +; CHECK-NEXT: --> {(%a + %b + %v1),+,1}<%loop1> +; CHECK: %s3 = add i32 %s2, %phi2 +; CHECK-NEXT: --> ({{{{}}((2 * %a) + %b),+,1}<%loop1>,+,2}<%loop2> + %v1) + +entry: + br label %loop1 + +loop1: + %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] + %phi1.inc = add i32 %phi1, 1 + %cond1 = icmp ult i32 %phi1, %c + br i1 %cond1, label %loop1, label %loop2 + +loop2: + %phi2 = phi i32 [ %a, %loop1 ], [ %phi2.inc, %loop2 ] + %phi2.inc = add i32 %phi2, 2 + %v1 = load i32, i32* %p + %s1 = add i32 %phi1, %v1 + %s2 = add i32 %s1, %b + %s3 = add i32 %s2, %phi2 + %cond2 = icmp ult i32 %s3, %c + br i1 %cond2, label %loop2, label %exit + +exit: + + ret void +} + +; Another mix of previous use cases that demonstrates that incorrect picking of +; a loop for a recurrence may cause a crash of SCEV analysis. +define void @test_04() { + +; CHECK-LABEL: Classifying expressions for: @test_04 +; CHECK: %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ] +; CHECK-NEXT: --> {2,+,1}<%loop1> +; CHECK: %tmp2 = trunc i64 %tmp to i32 +; CHECK-NEXT: --> {2,+,1}<%loop1> +; CHECK: %tmp4 = add nuw nsw i64 %tmp, 1 +; CHECK-NEXT: --> {3,+,1}<%loop1> +; CHECK: %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ] +; CHECK-NEXT: --> {2,+,1}<%loop2> +; CHECK: %tmp10 = sub i64 %tmp9, %tmp7 +; CHECK-NEXT: --> ((sext i8 %tmp8 to i64) + {-2,+,-1}<%loop2>) +; CHECK: %tmp11 = add i64 %tmp10, undef +; CHECK-NEXT: --> ((sext i8 %tmp8 to i64) + {(-2 + undef),+,-1}<%loop2>) +; CHECK: %tmp13 = trunc i64 %tmp11 to i32 +; CHECK-NEXT: --> ((sext i8 %tmp8 to i32) + {(trunc i64 (-2 + undef) to i32),+,-1}<%loop2>) +; CHECK: %tmp14 = sub i32 %tmp13, %tmp2 +; CHECK-NEXT: --> ((sext i8 %tmp8 to i32) + {{{{}}(-2 + (trunc i64 (-2 + undef) to i32)),+,-1}<%loop1>,+,-1}<%loop2>) +; CHECK: %tmp15 = add nuw nsw i64 %tmp7, 1 +; CHECK-NEXT: --> {3,+,1}<%loop2> + +bb: + br label %loop1 + +loop1: + %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ] + %tmp2 = trunc i64 %tmp to i32 + br i1 undef, label %loop2, label %bb3 + +bb3: + %tmp4 = add nuw nsw i64 %tmp, 1 + br label %loop1 + +bb5: + ret void + +loop2: + %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ] + %tmp8 = load i8, i8 addrspace(1)* undef, align 1 + %tmp9 = sext i8 %tmp8 to i64 + %tmp10 = sub i64 %tmp9, %tmp7 + %tmp11 = add i64 %tmp10, undef + %tmp13 = trunc i64 %tmp11 to i32 + %tmp14 = sub i32 %tmp13, %tmp2 + %tmp15 = add nuw nsw i64 %tmp7, 1 + %tmp16 = icmp slt i64 %tmp15, %tmp + br i1 %tmp16, label %loop2, label %bb5 +} + +@A = weak global [1000 x i32] zeroinitializer, align 32 + +; Demonstrate a situation when we can add two recs with different degrees from +; the same loop. +define void @test_05(i32 %N) { + +; CHECK-LABEL: Classifying expressions for: @test_05 +; CHECK: %SQ = mul i32 %i.0, %i.0 +; CHECK-NEXT: --> {4,+,5,+,2}<%bb3> +; CHECK: %tmp4 = mul i32 %i.0, 2 +; CHECK-NEXT: --> {4,+,2}<%bb3> +; CHECK: %tmp5 = sub i32 %SQ, %tmp4 +; CHECK-NEXT: --> {0,+,3,+,2}<%bb3> + +entry: + %"alloca point" = bitcast i32 0 to i32 ; [#uses=0] + br label %bb3 + +bb: ; preds = %bb3 + %tmp = getelementptr [1000 x i32], [1000 x i32]* @A, i32 0, i32 %i.0 ; [#uses=1] + store i32 123, i32* %tmp + %tmp2 = add i32 %i.0, 1 ; [#uses=1] + br label %bb3 + +bb3: ; preds = %bb, %entry + %i.0 = phi i32 [ 2, %entry ], [ %tmp2, %bb ] ; [#uses=3] + %SQ = mul i32 %i.0, %i.0 + %tmp4 = mul i32 %i.0, 2 + %tmp5 = sub i32 %SQ, %tmp4 + %tmp3 = icmp sle i32 %tmp5, 9999 ; [#uses=1] + br i1 %tmp3, label %bb, label %bb5 + +bb5: ; preds = %bb3 + br label %return + +return: ; preds = %bb5 + ret void +}