Index: llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpander.h =================================================================== --- llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpander.h +++ llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -83,6 +83,46 @@ typedef IRBuilder BuilderType; BuilderType Builder; + // RAII object that stores the current insertion point and restores it when + // the object is destroyed. This includes the debug location. Duplicated + // from InsertPointGuard to add SetInsertPoint() which is used to updated + // InsertPointGuards stack when insert points are moved during SCEV + // expansion. + class SCEVInsertPointGuard { + IRBuilderBase &Builder; + AssertingVH Block; + BasicBlock::iterator Point; + DebugLoc DbgLoc; + SCEVExpander *SE; + + SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete; + SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete; + + public: + SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE) + : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()), + DbgLoc(B.getCurrentDebugLocation()), SE(SE) { + SE->InsertPointGuards.push_back(this); + } + + ~SCEVInsertPointGuard() { + // These guards should always created/destroyed in FIFO order since they + // are used to guard lexically scoped blocks of code in + // ScalarEvolutionExpander. + assert(SE->InsertPointGuards.back() == this); + SE->InsertPointGuards.pop_back(); + Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point)); + Builder.SetCurrentDebugLocation(DbgLoc); + } + + BasicBlock::iterator GetInsertPoint() const { return Point; } + void SetInsertPoint(BasicBlock::iterator I) { Point = I; } + }; + + /// Stack of pointers to saved insert points, used to keep insert points + /// consistent when instructions are moved. + SmallVector InsertPointGuards; + #ifndef NDEBUG const char *DebugType; #endif @@ -101,6 +141,11 @@ #endif } + ~SCEVExpander() { + // Make sure the insert point guard stack is consistent. + assert(InsertPointGuards.empty()); + } + #ifndef NDEBUG void setDebugType(const char* s) { DebugType = s; } #endif @@ -318,6 +363,11 @@ bool &InvertStep); Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy, Type *IntTy, bool useSubtract); + + void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, + Instruction *Pos, PHINode *LoopPhi); + + void fixupInsertPoints(Instruction *I); }; } Index: llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp =================================================================== --- llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp +++ llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp @@ -196,7 +196,7 @@ // Save the original insertion point so we can restore it when we're done. DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc(); - BuilderType::InsertPointGuard Guard(Builder); + 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())) { @@ -523,7 +523,7 @@ } // Save the original insertion point so we can restore it when we're done. - BuilderType::InsertPointGuard Guard(Builder); + 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())) { @@ -542,39 +542,37 @@ return GEP; } - // Save the original insertion point so we can restore it when we're done. - BuilderType::InsertPoint SaveInsertPt = Builder.saveIP(); + { + 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(V)) break; + // Move the insertion point out of as many loops as we can. + while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) { + if (!L->isLoopInvariant(V)) break; - bool AnyIndexNotLoopInvariant = - std::any_of(GepIndices.begin(), GepIndices.end(), - [L](Value *Op) { return !L->isLoopInvariant(Op); }); + bool AnyIndexNotLoopInvariant = + std::any_of(GepIndices.begin(), GepIndices.end(), + [L](Value *Op) { return !L->isLoopInvariant(Op); }); - if (AnyIndexNotLoopInvariant) - break; - - BasicBlock *Preheader = L->getLoopPreheader(); - if (!Preheader) break; + if (AnyIndexNotLoopInvariant) + break; - // Ok, move up a level. - Builder.SetInsertPoint(Preheader->getTerminator()); - } + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) break; - // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, - // because ScalarEvolution may have changed the address arithmetic to - // compute a value which is beyond the end of the allocated object. - Value *Casted = V; - if (V->getType() != PTy) - Casted = InsertNoopCastOfTo(Casted, PTy); - Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep"); - Ops.push_back(SE.getUnknown(GEP)); - rememberInstruction(GEP); + // Ok, move up a level. + Builder.SetInsertPoint(Preheader->getTerminator()); + } - // Restore the original insert point. - Builder.restoreIP(SaveInsertPt); + // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, + // because ScalarEvolution may have changed the address arithmetic to + // compute a value which is beyond the end of the allocated object. + Value *Casted = V; + if (V->getType() != PTy) + Casted = InsertNoopCastOfTo(Casted, PTy); + Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep"); + Ops.push_back(SE.getUnknown(GEP)); + rememberInstruction(GEP); + } return expand(SE.getAddExpr(Ops)); } @@ -905,6 +903,23 @@ } } +/// If the insert point of the current builder or any of the builders on the +/// stack of saved builders has 'I' as its insert point, update it to point to +/// the instruction after 'I'. This is intended to be used when the instruction +/// 'I' is being moved. If this fixup is not done and 'I' is moved to a +/// different block, the inconsistent insert point (with a mismatched +/// Instruction and Block) can lead to an instruction being inserted in a block +/// other than its parent. +void SCEVExpander::fixupInsertPoints(Instruction *I) { + BasicBlock::iterator It(*I); + BasicBlock::iterator NewInsertPt = std::next(It); + if (Builder.GetInsertPoint() == It) + Builder.SetInsertPoint(&*NewInsertPt); + for (auto *InsertPtGuard : InsertPointGuards) + if (InsertPtGuard->GetInsertPoint() == It) + InsertPtGuard->SetInsertPoint(NewInsertPt); +} + /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make /// it available to other uses in this loop. Recursively hoist any operands, /// until we reach a value that dominates InsertPos. @@ -934,6 +949,7 @@ break; } for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) { + fixupInsertPoints(*I); (*I)->moveBefore(InsertPos); } return true; @@ -987,13 +1003,14 @@ /// \brief Hoist the addrec instruction chain rooted in the loop phi above the /// position. This routine assumes that this is possible (has been checked). -static void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, - Instruction *Pos, PHINode *LoopPhi) { +void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist, + Instruction *Pos, PHINode *LoopPhi) { do { if (DT->dominates(InstToHoist, Pos)) break; // Make sure the increment is where we want it. But don't move it // down past a potential existing post-inc user. + fixupInsertPoints(InstToHoist); InstToHoist->moveBefore(Pos); Pos = InstToHoist; InstToHoist = cast(InstToHoist->getOperand(0)); @@ -1154,7 +1171,7 @@ } // Save the original insertion point so we can restore it when we're done. - BuilderType::InsertPointGuard Guard(Builder); + SCEVInsertPointGuard Guard(Builder, this); // Another AddRec may need to be recursively expanded below. For example, if // this AddRec is quadratic, the StepV may itself be an AddRec in this @@ -1319,7 +1336,7 @@ Value *StepV; { // Expand the step somewhere that dominates the loop header. - BuilderType::InsertPointGuard Guard(Builder); + SCEVInsertPointGuard Guard(Builder, this); StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front()); } Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract); @@ -1667,7 +1684,7 @@ if (I != InsertedExpressions.end()) return I->second; - BuilderType::InsertPointGuard Guard(Builder); + SCEVInsertPointGuard Guard(Builder, this); Builder.SetInsertPoint(InsertPt); // Expand the expression into instructions. @@ -1708,7 +1725,7 @@ SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap); // Emit code for it. - BuilderType::InsertPointGuard Guard(Builder); + SCEVInsertPointGuard Guard(Builder, this); PHINode *V = cast(expandCodeFor(H, nullptr, &L->getHeader()->front()));