Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -1553,6 +1553,13 @@ getExtendAddRecStart(AR, Ty, this), getZeroExtendExpr(Step, Ty), L, AR->getNoWrapFlags()); + // If we have special knowledge that this addrec won't self-overflow, + // we don't need to do any further analysis. + if (AR->hasNoSelfWrap()) + return getAddRecExpr( + getExtendAddRecStart(AR, Ty, this), + getSignExtendExpr(Step, Ty), L, AR->getNoWrapFlags()); + // Check whether the backedge-taken count is SCEVCouldNotCompute. // Note that this serves two purposes: It filters out loops that are // simply not analyzable, and it covers the case where this code is @@ -1780,6 +1787,13 @@ getExtendAddRecStart(AR, Ty, this), getSignExtendExpr(Step, Ty), L, SCEV::FlagNSW); + // If we have special knowledge that this addrec won't self-overflow, + // we don't need to do any further analysis. + if (AR->hasNoSelfWrap()) + return getAddRecExpr( + getExtendAddRecStart(AR, Ty, this), + getZeroExtendExpr(Step, Ty), L, AR->getNoWrapFlags()); + // Check whether the backedge-taken count is SCEVCouldNotCompute. // Note that this serves two purposes: It filters out loops that are // simply not analyzable, and it covers the case where this code is Index: unittests/Analysis/ScalarEvolutionTest.cpp =================================================================== --- unittests/Analysis/ScalarEvolutionTest.cpp +++ unittests/Analysis/ScalarEvolutionTest.cpp @@ -600,5 +600,236 @@ EXPECT_NE(nullptr, SE.getSCEV(Mul1)); } +// Expect the call of getZeroExtendExpr will not cost exponential time. +TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExpr) { + LLVMContext C; + SMDiagnostic Err; + std::unique_ptr M = parseAssemblyString( + "target datalayout = \"e-m:e-i64:64-f80:128-n8:16:32:64-S128\"\n" + "target triple = \"x86_64-unknown-linux-gnu\"\n" + "\n" + "define void @foo(i64 %ptr) {\n" + "entry:\n" + " br label %for.cond\n" + "\n" + "for.cond:\n" + " %i1.0 = phi i64 [ 100, %entry ], [ %inc, %for.inc ]\n" + " %cmp = icmp sgt i64 %i1.0, 90\n" + " br i1 %cmp, label %for.inc, label %for.cond1\n" + "\n" + "for.inc:\n" + " %inc = add nsw i64 %i1.0, -1\n" + " br label %for.cond\n" + "\n" + "for.cond1:\n" + " %i2.0 = phi i64 [ %inc5, %for.inc4 ], [ 100, %for.cond ]\n" + " %cmp2 = icmp sgt i64 %i2.0, 90\n" + " br i1 %cmp2, label %for.inc4, label %for.cond7\n" + "\n" + "for.inc4:\n" + " %inc5 = add nsw i64 %i2.0, -1\n" + " br label %for.cond1\n" + "\n" + "for.cond7:\n" + " %i3.0 = phi i64 [ %inc11, %for.inc10 ], [ 100, %for.cond1 ]\n" + " %cmp8 = icmp sgt i64 %i3.0, 90\n" + " br i1 %cmp8, label %for.inc10, label %for.cond13\n" + "\n" + "for.inc10:\n" + " %inc11 = add nsw i64 %i3.0, -1\n" + " br label %for.cond7\n" + "\n" + "for.cond13:\n" + " %i4.0 = phi i64 [ %inc17, %for.inc16 ], [ 100, %for.cond7 ]\n" + " %cmp14 = icmp sgt i64 %i4.0, 90\n" + " br i1 %cmp14, label %for.inc16, label %for.cond19\n" + "\n" + "for.inc16:\n" + " %inc17 = add nsw i64 %i4.0, -1\n" + " br label %for.cond13\n" + "\n" + "for.cond19:\n" + " %i5.0 = phi i64 [ %inc23, %for.inc22 ], [ 100, %for.cond13 ]\n" + " %cmp20 = icmp sgt i64 %i5.0, 90\n" + " br i1 %cmp20, label %for.inc22, label %for.cond25\n" + "\n" + "for.inc22:\n" + " %inc23 = add nsw i64 %i5.0, -1\n" + " br label %for.cond19\n" + "\n" + "for.cond25:\n" + " %i6.0 = phi i64 [ %inc29, %for.inc28 ], [ 100, %for.cond19 ]\n" + " %cmp26 = icmp sgt i64 %i6.0, 90\n" + " br i1 %cmp26, label %for.inc28, label %for.cond31\n" + "\n" + "for.inc28:\n" + " %inc29 = add nsw i64 %i6.0, -1\n" + " br label %for.cond25\n" + "\n" + "for.cond31:\n" + " %i7.0 = phi i64 [ %inc35, %for.inc34 ], [ 100, %for.cond25 ]\n" + " %cmp32 = icmp sgt i64 %i7.0, 90\n" + " br i1 %cmp32, label %for.inc34, label %for.cond37\n" + "\n" + "for.inc34:\n" + " %inc35 = add nsw i64 %i7.0, -1\n" + " br label %for.cond31\n" + "\n" + "for.cond37:\n" + " %i8.0 = phi i64 [ %inc41, %for.inc40 ], [ 100, %for.cond31 ]\n" + " %cmp38 = icmp sgt i64 %i8.0, 90\n" + " br i1 %cmp38, label %for.inc40, label %for.cond43\n" + "\n" + "for.inc40:\n" + " %inc41 = add nsw i64 %i8.0, -1\n" + " br label %for.cond37\n" + "\n" + "for.cond43:\n" + " %i9.0 = phi i64 [ %inc47, %for.inc46 ], [ 100, %for.cond37 ]\n" + " %cmp44 = icmp sgt i64 %i9.0, 90\n" + " br i1 %cmp44, label %for.inc46, label %for.cond49\n" + "\n" + "for.inc46:\n" + " %inc47 = add nsw i64 %i9.0, -1\n" + " br label %for.cond43\n" + "\n" + "for.cond49:\n" + " %i10.0 = phi i64 [ %inc53, %for.inc52 ], [ 100, %for.cond43 ]\n" + " %cmp50 = icmp sgt i64 %i10.0, 90\n" + " br i1 %cmp50, label %for.inc52, label %for.cond50\n" + "\n" + "for.inc52:\n" + " %inc53 = add nsw i64 %i10.0, -1\n" + " br label %for.cond49\n" + "\n" + "for.cond50:\n" + " %i11.0 = phi i64 [ %inc54, %for.inc53 ], [ 100, %for.cond49 ]\n" + " %cmp51 = icmp sgt i64 %i11.0, 90\n" + " br i1 %cmp51, label %for.inc53, label %for.cond51\n" + "\n" + "for.inc53:\n" + " %inc54 = add nsw i64 %i11.0, -1\n" + " br label %for.cond50\n" + "\n" + "for.cond51:\n" + " %i12.0 = phi i64 [ %inc55, %for.inc54 ], [ 100, %for.cond50 ]\n" + " %cmp52 = icmp sgt i64 %i12.0, 90\n" + " br i1 %cmp52, label %for.inc54, label %for.cond52\n" + "\n" + "for.inc54:\n" + " %inc55 = add nsw i64 %i12.0, -1\n" + " br label %for.cond51\n" + "\n" + "for.cond52:\n" + " %i13.0 = phi i64 [ %inc56, %for.inc55 ], [ 100, %for.cond51 ]\n" + " %cmp53 = icmp sgt i64 %i13.0, 90\n" + " br i1 %cmp53, label %for.inc55, label %for.cond53\n" + "\n" + "for.inc55:\n" + " %inc56 = add nsw i64 %i13.0, -1\n" + " br label %for.cond52\n" + "\n" + "for.cond53:\n" + " %i14.0 = phi i64 [ %inc57, %for.inc56 ], [ 100, %for.cond52 ]\n" + " %cmp54 = icmp sgt i64 %i14.0, 90\n" + " br i1 %cmp54, label %for.inc56, label %for.cond54\n" + "\n" + "for.inc56:\n" + " %inc57 = add nsw i64 %i14.0, -1\n" + " br label %for.cond53\n" + "\n" + "for.cond54:\n" + " %i15.0 = phi i64 [ %inc58, %for.inc57 ], [ 100, %for.cond53 ]\n" + " %cmp55 = icmp sgt i64 %i15.0, 90\n" + " br i1 %cmp55, label %for.inc57, label %for.cond55\n" + "\n" + "for.inc57:\n" + " %inc58 = add nsw i64 %i15.0, -1\n" + " br label %for.cond54\n" + "\n" + "for.cond55:\n" + " %i16.0 = phi i64 [ %inc59, %for.inc58 ], [ 100, %for.cond54 ]\n" + " %cmp56 = icmp sgt i64 %i16.0, 90\n" + " br i1 %cmp56, label %for.inc58, label %for.cond56\n" + "\n" + "for.inc58:\n" + " %inc59 = add nsw i64 %i16.0, -1\n" + " br label %for.cond55\n" + "\n" + "for.cond56:\n" + " %i17.0 = phi i64 [ %inc60, %for.inc59 ], [ 100, %for.cond55 ]\n" + " %cmp57 = icmp sgt i64 %i17.0, 90\n" + " br i1 %cmp57, label %for.inc59, label %for.cond57\n" + "\n" + "for.inc59:\n" + " %inc60 = add nsw i64 %i17.0, -1\n" + " br label %for.cond56\n" + "\n" + "for.cond57:\n" + " %i18.0 = phi i64 [ %inc61, %for.inc60 ], [ 100, %for.cond56 ]\n" + " %cmp58 = icmp sgt i64 %i18.0, 90\n" + " br i1 %cmp58, label %for.inc60, label %for.cond58\n" + "\n" + "for.inc60:\n" + " %inc61 = add nsw i64 %i18.0, -1\n" + " br label %for.cond57\n" + "\n" + "for.cond58:\n" + " %i19.0 = phi i64 [ %inc62, %for.inc61 ], [ 100, %for.cond57 ]\n" + " %cmp59 = icmp sgt i64 %i19.0, 90\n" + " br i1 %cmp59, label %for.inc61, label %for.cond59\n" + "\n" + "for.inc61:\n" + " %inc62 = add nsw i64 %i19.0, -1\n" + " br label %for.cond58\n" + "\n" + "for.cond59:\n" + " %i20.0 = phi i64 [ %inc63, %for.inc62 ], [ 100, %for.cond58 ]\n" + " %cmp60 = icmp sgt i64 %i20.0, 90\n" + " br i1 %cmp60, label %for.inc62, label %for.end\n" + "\n" + "for.inc62:\n" + " %inc63 = add nsw i64 %i20.0, -1\n" + " br label %for.cond59\n" + "\n" + "for.end:\n" + " %add1 = getelementptr inbounds i8, i8* null, i64 %i1.0\n" + " %add2 = getelementptr inbounds i8, i8* %add1, i64 %i2.0\n" + " %add3 = getelementptr inbounds i8, i8* %add2, i64 %i3.0\n" + " %add4 = getelementptr inbounds i8, i8* %add3, i64 %i4.0\n" + " %add5 = getelementptr inbounds i8, i8* %add4, i64 %i5.0\n" + " %add6 = getelementptr inbounds i8, i8* %add5, i64 %i6.0\n" + " %add7 = getelementptr inbounds i8, i8* %add6, i64 %i7.0\n" + " %add8 = getelementptr inbounds i8, i8* %add7, i64 %i8.0\n" + " %add9 = getelementptr inbounds i8, i8* %add8, i64 %i9.0\n" + " %add10 = getelementptr inbounds i8, i8* %add9, i64 %i10.0\n" + " %add11 = getelementptr inbounds i8, i8* %add10, i64 %i11.0\n" + " %add12 = getelementptr inbounds i8, i8* %add11, i64 %i12.0\n" + " %add13 = getelementptr inbounds i8, i8* %add12, i64 %i13.0\n" + " %add14 = getelementptr inbounds i8, i8* %add13, i64 %i14.0\n" + " %add15 = getelementptr inbounds i8, i8* %add14, i64 %i15.0\n" + " %add16 = getelementptr inbounds i8, i8* %add15, i64 %i16.0\n" + " %add17 = getelementptr inbounds i8, i8* %add16, i64 %i17.0\n" + " %add18 = getelementptr inbounds i8, i8* %add17, i64 %i18.0\n" + " %add19 = getelementptr inbounds i8, i8* %add18, i64 %i19.0\n" + " %add20 = getelementptr inbounds i8, i8* %add19, i64 %i20.0\n" + " %tmp80 = ptrtoint i8* %add20 to i64\n" + " %tmp90 = zext i64 %tmp80 to i128\n" + " %tmp91 = trunc i128 %tmp90 to i64\n" + " ret void\n" + "}\n", + Err, C); + assert(M && "Could not parse module?"); + assert(!verifyModule(*M) && "Must have been well formed!"); + Function *F = M->getFunction("foo"); + ScalarEvolution SE = buildSE(*F); + Function::iterator FI = F->begin(); + std::advance(FI, 41); + BasicBlock::iterator BI = FI->begin(); + std::advance(BI, 19); + const SCEV *S = SE.getSCEV(&*BI); + Type *Ty = Type::getInt128Ty(Context); + SE.getZeroExtendExpr(S, Ty); +} } // end anonymous namespace } // end namespace llvm