Index: llvm/trunk/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/trunk/lib/Analysis/ScalarEvolution.cpp +++ llvm/trunk/lib/Analysis/ScalarEvolution.cpp @@ -4443,7 +4443,7 @@ // varying inside the loop. if (!isLoopInvariant(Accum, L)) return None; - + // *** Part2: Create the predicates // Analysis was successful: we have a phi-with-cast pattern for which we @@ -4493,27 +4493,71 @@ // // By induction, the same applies to all iterations 1<=i(PHISCEV); + getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap); - SCEVWrapPredicate::IncrementWrapFlags AddedFlags = - Signed ? SCEVWrapPredicate::IncrementNSSW - : SCEVWrapPredicate::IncrementNUSW; - const SCEVPredicate *AddRecPred = getWrapPredicate(AR, AddedFlags); - Predicates.push_back(AddRecPred); + // PHISCEV can be either a SCEVConstant or a SCEVAddRecExpr. + // ex: If truncated Accum is 0 and StartVal is a constant, then PHISCEV + // will be constant. + // + // If PHISCEV is a constant, then P1 degenerates into P2 or P3, so we don't + // add P1. + if (const auto *AR = dyn_cast(PHISCEV)) { + SCEVWrapPredicate::IncrementWrapFlags AddedFlags = + Signed ? SCEVWrapPredicate::IncrementNSSW + : SCEVWrapPredicate::IncrementNUSW; + const SCEVPredicate *AddRecPred = getWrapPredicate(AR, AddedFlags); + Predicates.push_back(AddRecPred); + } else + assert(isa(PHISCEV) && "Expected constant SCEV"); // Create the Equal Predicates P2,P3: - auto AppendPredicate = [&](const SCEV *Expr) -> void { + + // It is possible that the predicates P2 and/or P3 are computable at + // compile time due to StartVal and/or Accum being constants. + // If either one is, then we can check that now and escape if either P2 + // or P3 is false. + + // Construct the extended SCEV: (Ext ix (Trunc iy (Expr) to ix) to iy) + // for each of StartVal and Accum + auto GetExtendedExpr = [&](const SCEV *Expr) -> const SCEV * { assert(isLoopInvariant(Expr, L) && "Expr is expected to be invariant"); const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy); const SCEV *ExtendedExpr = Signed ? getSignExtendExpr(TruncatedExpr, Expr->getType()) : getZeroExtendExpr(TruncatedExpr, Expr->getType()); + return ExtendedExpr; + }; + + // Given: + // ExtendedExpr = (Ext ix (Trunc iy (Expr) to ix) to iy + // = GetExtendedExpr(Expr) + // Determine whether the predicate P: Expr == ExtendedExpr + // is known to be false at compile time + auto PredIsKnownFalse = [&](const SCEV *Expr, + const SCEV *ExtendedExpr) -> bool { + return Expr != ExtendedExpr && + isKnownPredicate(ICmpInst::ICMP_NE, Expr, ExtendedExpr); + }; + + const SCEV *StartExtended = GetExtendedExpr(StartVal); + if (PredIsKnownFalse(StartVal, StartExtended)) { + DEBUG(dbgs() << "P2 is compile-time false\n";); + return None; + } + + const SCEV *AccumExtended = GetExtendedExpr(Accum); + if (PredIsKnownFalse(Accum, AccumExtended)) { + DEBUG(dbgs() << "P3 is compile-time false\n";); + return None; + } + + auto AppendPredicate = [&](const SCEV *Expr, + const SCEV *ExtendedExpr) -> void { if (Expr != ExtendedExpr && !isKnownPredicate(ICmpInst::ICMP_EQ, Expr, ExtendedExpr)) { const SCEVPredicate *Pred = getEqualPredicate(Expr, ExtendedExpr); @@ -4521,10 +4565,10 @@ Predicates.push_back(Pred); } }; - - AppendPredicate(StartVal); - AppendPredicate(Accum); - + + AppendPredicate(StartVal, StartExtended); + AppendPredicate(Accum, AccumExtended); + // *** Part3: Predicates are ready. Now go ahead and create the new addrec in // which the casts had been folded away. The caller can rewrite SymbolicPHI // into NewAR if it will also add the runtime overflow checks specified in Index: llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp +++ llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp @@ -1095,5 +1095,60 @@ EXPECT_EQ(cast(NewEC)->getAPInt().getLimitedValue(), 1999u); } +TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) { + // Reference: https://reviews.llvm.org/D37265 + // Make sure that SCEV does not blow up when constructing an AddRec + // with predicates for a phi with the update pattern: + // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum + // when either the initial value of the Phi or the InvariantAccum are + // constants that are too large to fit in an ix but are zero when truncated to + // ix. + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(Context), std::vector(), false); + Function *F = cast(M.getOrInsertFunction("addrecphitest", FTy)); + + /* + Create IR: + entry: + br label %loop + loop: + %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop] + %1 = shl i64 %0, 32 + %2 = ashr exact i64 %1, 32 + %3 = add i64 %2, -9223372036854775808 + br i1 undef, label %exit, label %loop + exit: + ret void + */ + BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); + BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); + BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); + + // entry: + BranchInst::Create(LoopBB, EntryBB); + // loop: + auto *MinInt64 = + ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true)); + auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32)); + auto *Br = BranchInst::Create( + LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB); + auto *Phi = PHINode::Create(Type::getInt64Ty(Context), 2, "", Br); + auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br); + auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br); + auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br); + Phi->addIncoming(MinInt64, EntryBB); + Phi->addIncoming(Add, LoopBB); + // exit: + ReturnInst::Create(Context, nullptr, ExitBB); + + // Make sure that SCEV doesn't blow up + ScalarEvolution SE = buildSE(*F); + SCEVUnionPredicate Preds; + const SCEV *Expr = SE.getSCEV(Phi); + EXPECT_NE(nullptr, Expr); + EXPECT_TRUE(isa(Expr)); + auto Result = SE.createAddRecFromPHIWithCasts(cast(Expr)); +} + } // end anonymous namespace } // end namespace llvm