Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -5359,6 +5359,13 @@ } const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { + // If the PHI is in the midst of being constructed, it does not make sense to + // compute a SCEV for it. Here we assume that for every predecessor block + // there is a corresponding incoming value in the PHI. + unsigned NumIncoming = PN->getNumIncomingValues(); + if (!PN->getParent()->hasNPredecessors(NumIncoming)) + return getUnknown(PN); + if (const SCEV *S = createAddRecFromPHI(PN)) return S; Index: llvm/unittests/Analysis/ScalarEvolutionTest.cpp =================================================================== --- llvm/unittests/Analysis/ScalarEvolutionTest.cpp +++ llvm/unittests/Analysis/ScalarEvolutionTest.cpp @@ -65,6 +65,13 @@ } }; +static Argument *getArgumentByName(Function &F, StringRef Name) { + for (auto &A : F.args()) + if (A.getName() == Name) + return &A; + llvm_unreachable("Expected to find an argument!"); +} + TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) { FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), std::vector(), false); @@ -1773,6 +1780,104 @@ }); } +TEST_F(ScalarEvolutionsTest, TestRecursiveGetAddRecExprPHILiterally) { + // Reference: https://reviews.llvm.org/D77560 + // getAddRecExprPHILiterally might call itself recursively (when calling + // expandIVInc), and in the process attempts to create a SCEV for the PHINode + // it is constructing. The resulting SCEV, which gets cached in in + // ValueExprMap is invalid, so for now make it return SCEVUnknown. + // A better fix to this problem would yield a correct symbolic representation + // of the PHINode, but that's left for a future improvement. + // + LLVMContext C; + SMDiagnostic Err; + std::unique_ptr M = parseAssemblyString( + " target datalayout = \"e-m:e-i64:64-n32:64\" " + " define dso_local void @foo(i64* %.n, i8* %ar) local_unnamed_addr {" + " entry: " + " %n = load i64, i64* %.n, align 4 " + " br label %outer " + " outer: " + " %phi1 = phi i64 [ 0, %entry ], [ %add1, %outer.end ] " + " %phi2 = phi i64 [ 0, %entry ], [ %add5, %outer.end ] " + " %add1 = add i64 %phi1, %n " + " %shl1 = shl i64 %add1, 1 " + " %sub1 = sub i64 %phi2, undef " + " %add5 = add i64 %sub1, %shl1 " + " br i1 true, label %outer.end, label %inner.preheader " + " inner.preheader: " + " br label %inner " + " inner: " + " %phi3 = phi i64 [ %ad3, %inner ], [ 0, %inner.preheader ] " + " %ad2 = add i64 %phi3, %add5 " + " %sh2 = shl i64 %ad2, 2 " + " %gep2 = getelementptr i8, i8* %ar, i64 %sh2 " + " %ad4 = add i64 %phi3, %phi2 " + " %0 = shl i64 %ad4, 2 " + " %gep3 = getelementptr i8, i8* %ar, i64 %0 " + " call void @bar(i8* %gep3, i8* %gep2) " + " %ad3 = add i64 %phi3, 4 " + " br i1 false, label %inner, label %inner.end " + " inner.end: " + " br label %outer.end " + " outer.end: " + " %cmp = icmp ult i64 %phi2, 10 " + " br i1 %cmp, label %outer, label %ret " + " ret: " + " ret void " + " } " + " declare void @bar(i8*,i8*) local_unnamed_addr ", + Err, C); + + ASSERT_TRUE(M && "Could not parse module?"); + ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); + + runWithSE(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + auto GetAddRec = [&SE](const Loop *L, + std::initializer_list Ops) { + SmallVector OpsCopy(Ops); + return SE.getAddRecExpr(OpsCopy, L, SCEV::FlagAnyWrap); + }; + + Loop *outerLoop = *LI.begin(); + Loop *innerLoop = outerLoop->getSubLoops()[0]; + + Type *commonTy = getInstructionByName(F, "n")->getType(); + const SCEV *Scev_n = SE.getSCEV(getInstructionByName(F, "n")); + const SCEV *Scev_ar = SE.getSCEV(getArgumentByName(F, "ar")); + const SCEV *Scev_undef = SE.getSCEV(UndefValue::get(commonTy)); + const SCEV *Const8 = SE.getConstant(commonTy, 8); + const SCEV *Const4 = SE.getConstant(commonTy, 4); + const SCEV *Const16 = SE.getConstant(commonTy, 16); + const SCEV *Scev_8_times_n = SE.getMulExpr(Const8, Scev_n); + const SCEV *Scev_4_times_undef = + SE.getMulExpr(Const4, Scev_undef); + const SCEV *Scev_Aggregate = + SE.getAddExpr(Scev_8_times_n, Scev_4_times_undef); + + // create {%ar,+,((8 * %n) + (4 * undef)),+,(8 * %n)}<%outer> + const SCEV *OuterSCEV = + GetAddRec(outerLoop, {Scev_ar, Scev_Aggregate, Scev_8_times_n}); + + // create {{%ar,+,((8 * %n) + (4 * undef)),+,(8* %n)}<%outer>,+,16}<%inner> + const SCEV *Input = GetAddRec(innerLoop, {OuterSCEV, Const16}); + + // perform the expansion that leads to + // SCEVExpander::getAddRecExprPHILiterally calling getSCEV on an incomplete + // PHI + SCEVExpander Exp(SE, M->getDataLayout(), "expander"); + Exp.disableCanonicalMode(); + auto *InsertAt = getInstructionByName(F, "gep3")->getNextNode(); + Exp.expandCodeFor(Input, nullptr, InsertAt); + + // now confirm that the SCEV for the phi created during the expansion is + // correct. + Instruction *iv1 = getInstructionByName(F, "expander.iv1"); + const SCEV *Result = SE.getSCEV(iv1); + EXPECT_EQ(SE.getUnknown(iv1), Result); + }); +} + // Test expansion of nested addrecs in CanonicalMode. // Expanding nested addrecs in canonical mode requiers a canonical IV of a // type wider than the type of the addrec itself. Currently, SCEVExpander