From e30a2814490d1e0f1d338a5eebd871e3defd37e4 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Thu, 10 Nov 2016 07:56:09 +0000 Subject: [PATCH] [SCEVExpander] Don't hoist divisions Fixes PR30942. llvm-svn: 286437 --- llvm/lib/Analysis/ScalarEvolutionExpander.cpp | 74 +++++++++++++----------- llvm/unittests/Analysis/ScalarEvolutionTest.cpp | 76 +++++++++++++++++++++++++ 2 files changed, 118 insertions(+), 32 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp index 6ad766b..d94782a 100644 --- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp @@ -198,14 +198,21 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc(); SCEVInsertPointGuard Guard(Builder, this); - // Move the insertion point out of as many loops as we can. - while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { - if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break; - BasicBlock *Preheader = L->getLoopPreheader(); - if (!Preheader) break; - - // Ok, move up a level. - Builder.SetInsertPoint(Preheader->getTerminator()); + if (Opcode != Instruction::UDiv) { + // FIXME: There is alredy similar logic in expandCodeFor, we should see if + // this is actually needed here. + + // Move the insertion point out of as many loops as we can. + while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { + if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) + break; + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) + break; + + // Ok, move up a level. + Builder.SetInsertPoint(Preheader->getTerminator()); + } } // If we haven't found this binop, insert it. @@ -1663,31 +1670,34 @@ Value *SCEVExpander::expand(const SCEV *S) { // Compute an insertion point for this SCEV object. Hoist the instructions // as far out in the loop nest as possible. Instruction *InsertPt = &*Builder.GetInsertPoint(); - for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());; - L = L->getParentLoop()) - if (SE.isLoopInvariant(S, L)) { - if (!L) break; - if (BasicBlock *Preheader = L->getLoopPreheader()) - InsertPt = Preheader->getTerminator(); - else { - // LSR sets the insertion point for AddRec start/step values to the - // block start to simplify value reuse, even though it's an invalid - // position. SCEVExpander must correct for this in all cases. - InsertPt = &*L->getHeader()->getFirstInsertionPt(); - } - } else { - // If the SCEV is computable at this level, insert it into the header - // after the PHIs (and after any other instructions that we've inserted - // there) so that it is guaranteed to dominate any user inside the loop. - if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L)) - InsertPt = &*L->getHeader()->getFirstInsertionPt(); - while (InsertPt->getIterator() != Builder.GetInsertPoint() && - (isInsertedInstruction(InsertPt) || - isa(InsertPt))) { - InsertPt = &*std::next(InsertPt->getIterator()); + if (!isa(S)) { + for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());; + L = L->getParentLoop()) + if (SE.isLoopInvariant(S, L)) { + if (!L) + break; + if (BasicBlock *Preheader = L->getLoopPreheader()) + InsertPt = Preheader->getTerminator(); + else { + // LSR sets the insertion point for AddRec start/step values to the + // block start to simplify value reuse, even though it's an invalid + // position. SCEVExpander must correct for this in all cases. + InsertPt = &*L->getHeader()->getFirstInsertionPt(); + } + } else { + // If the SCEV is computable at this level, insert it into the header + // after the PHIs (and after any other instructions that we've inserted + // there) so that it is guaranteed to dominate any user inside the loop. + if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L)) + InsertPt = &*L->getHeader()->getFirstInsertionPt(); + while (InsertPt->getIterator() != Builder.GetInsertPoint() && + (isInsertedInstruction(InsertPt) || + isa(InsertPt))) { + InsertPt = &*std::next(InsertPt->getIterator()); + } + break; } - break; - } + } // Check to see if we already expanded this here. auto I = InsertedExpressions.find(std::make_pair(S, InsertPt)); diff --git a/llvm/unittests/Analysis/ScalarEvolutionTest.cpp b/llvm/unittests/Analysis/ScalarEvolutionTest.cpp index 6dcb18f..f928925 100644 --- a/llvm/unittests/Analysis/ScalarEvolutionTest.cpp +++ b/llvm/unittests/Analysis/ScalarEvolutionTest.cpp @@ -349,6 +349,13 @@ static Instruction *getInstructionByName(Function &F, StringRef Name) { llvm_unreachable("Expected to find instruction!"); } +static Argument *getArgByName(Function &F, StringRef Name) { + for (auto &A : F.args()) + if (A.getName() == Name) + return &A; + llvm_unreachable("Expected to find argument!"); +} + TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) { LLVMContext C; SMDiagnostic Err; @@ -465,5 +472,74 @@ TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) { }); } +TEST_F(ScalarEvolutionsTest, BadHoistingSCEVExpander_PR30942) { + LLVMContext C; + SMDiagnostic Err; + std::unique_ptr M = parseAssemblyString( + "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" " + " " + "define void @f_1(i32 %x, i32 %y, i32 %n, i1* %cond_buf) " + " local_unnamed_addr { " + "entry: " + " %entrycond = icmp sgt i32 %n, 0 " + " br i1 %entrycond, label %loop.ph, label %for.end " + " " + "loop.ph: " + " br label %loop " + " " + "loop: " + " %iv1 = phi i32 [ %iv1.inc, %right ], [ 0, %loop.ph ] " + " %iv1.inc = add nuw nsw i32 %iv1, 1 " + " %cond = load volatile i1, i1* %cond_buf " + " br i1 %cond, label %left, label %right " + " " + "left: " + " %div = udiv i32 %x, %y " + " br label %right " + " " + "right: " + " %exitcond = icmp eq i32 %iv1.inc, %n " + " br i1 %exitcond, label %for.end.loopexit, label %loop " + " " + "for.end.loopexit: " + " br label %for.end " + " " + "for.end: " + " ret void " + "} ", + Err, C); + + assert(M && "Could not parse module?"); + assert(!verifyModule(*M) && "Must have been well formed!"); + + runWithFunctionAndSE(*M, "f_1", [&](Function &F, ScalarEvolution &SE) { + SCEVExpander Expander(SE, M->getDataLayout(), "unittests"); + auto *DivInst = getInstructionByName(F, "div"); + + { + auto *DivSCEV = SE.getSCEV(DivInst); + auto *DivExpansion = Expander.expandCodeFor( + DivSCEV, DivSCEV->getType(), DivInst->getParent()->getTerminator()); + auto *DivExpansionInst = dyn_cast(DivExpansion); + ASSERT_NE(DivExpansionInst, nullptr); + EXPECT_EQ(DivInst->getParent(), DivExpansionInst->getParent()); + } + + { + auto *ArgY = getArgByName(F, "y"); + auto *DivFromScratchSCEV = + SE.getUDivExpr(SE.getOne(ArgY->getType()), SE.getSCEV(ArgY)); + + auto *DivFromScratchExpansion = Expander.expandCodeFor( + DivFromScratchSCEV, DivFromScratchSCEV->getType(), + DivInst->getParent()->getTerminator()); + auto *DivFromScratchExpansionInst = + dyn_cast(DivFromScratchExpansion); + ASSERT_NE(DivFromScratchExpansionInst, nullptr); + EXPECT_EQ(DivInst->getParent(), DivFromScratchExpansionInst->getParent()); + } + }); +} + } // end anonymous namespace } // end namespace llvm -- 2.7.4