[SCEV] Keep SCEVExpander insert points consistent.

[gberry]

Summary

Make sure that the SCEVExpander Builder insert point and any
saved/restored insert points are kept consistent (i.e. their Instruction
and BasicBlock match) when moving instructions in SCEVExpander.

This fixes an issue triggered by
http://reviews.llvm.org/D18001 [LSR] Create fewer redundant instructions.

[sanjoy]

include/llvm/Analysis/ScalarEvolutionExpander.h

97

Add a description here on why this assert shouldn't fail.

include/llvm/IR/IRBuilder.h

229

This new public interface looks like the kind of thing that will be inadvertently get misused later. How about duplicating the functionality of InsertPointGuard in SCEVInsertPointGuard and adding the getter and setter on just that class?

lib/Analysis/ScalarEvolutionExpander.cpp

917

Why not Builder.SetInsertPoint(&*NewInsertPt)?

[gberry]

Update to address Sanjoy's comments.

[gberry]

Hi Sanjoy,

Thanks for the review. I've made the changes you suggested. I'm not entirely pleased with the duplicating of InsertPointGuard, though I also wasn't pleased with changing the InsertPointGuard interface.

[sanjoy]

lgtm with nits, thanks!

I'm not entirely pleased with the duplicating of InsertPointGuard, though I also wasn't pleased with changing the InsertPointGuard interface.

Yes, but it seems to be the lesser of two evils. :)

include/llvm/Analysis/ScalarEvolutionExpander.h

121

Minor: add newline between declarations.

123

Assert that this is empty when destroying a SCEVExpander.

168

This should be a private function.

[gberry]

Thanks Sanjoy.

llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpander.h

367 ↗

(On Diff #59267)

FYI, I had to make this a private member function to make fixupInsertPoints private.

include/llvm/Analysis/ScalarEvolutionExpander.h

class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
     /// \brief When invoked from LSR, the expander is in "strength reduction"
     /// mode. The only difference is that phi's are only reused if they are
     /// already in "expanded" form.
     bool LSRMode;
 
     typedef IRBuilder<TargetFolder> BuilderType;
     BuilderType Builder;
 
+    /// Stack of pointers to saved insert points, used to keep insert points
+    /// consistent when instructions are moved.
+    SmallVector<BuilderType::InsertPointGuard *, 8> InsertPointGuards;
+    class SCEVInsertPointGuard {
+    public:
+      SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
+          : Guard(B), SE(SE) {
+        SE->InsertPointGuards.push_back(&Guard);
+      }
+
+      ~SCEVInsertPointGuard() {
+        assert(SE->InsertPointGuards.back() == &Guard);
+        SE->InsertPointGuards.pop_back();
+      }
+
+      BuilderType::InsertPointGuard Guard;
+      SCEVExpander *SE;
+    };
+
 #ifndef NDEBUG
     const char *DebugType;
 #endif
 
     friend struct SCEVVisitor<SCEVExpander, Value*>;
 
   public:
     /// \brief Construct a SCEVExpander in "canonical" mode.
     explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
                           const char *name)
         : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr),
           IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false),
           Builder(se.getContext(), TargetFolder(DL)) {
 #ifndef NDEBUG
       DebugType = "";
 #endif
     }
 
 #ifndef NDEBUG
     void setDebugType(const char* s) { DebugType = s; }
 #endif
 
     /// \brief Erase the contents of the InsertedExpressions map so that users
     /// trying to expand the same expression into multiple BasicBlocks or
     /// different places within the same BasicBlock can do so.
     void clear() {
       InsertedExpressions.clear();
#endif
     bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
 
     /// \brief replace congruent phis with their most canonical
     /// representative. Return the number of phis eliminated.
     unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
                                  SmallVectorImpl<WeakVH> &DeadInsts,
                                  const TargetTransformInfo *TTI = nullptr);
 
+    void fixupInsertPoints(Instruction *I);
+
     /// \brief Insert code to directly compute the specified SCEV expression
     /// into the program.  The inserted code is inserted into the specified
     /// block.
     Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);
 
     /// \brief Generates a code sequence that evaluates this predicate.
     /// The inserted instructions will be at position \p Loc.
     /// The result will be of type i1 and will have a value of 0 when the

include/llvm/IR/IRBuilder.h

public:
     InsertPointGuard(IRBuilderBase &B)
         : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
           DbgLoc(B.getCurrentDebugLocation()) {}
 
     ~InsertPointGuard() {
       Builder.restoreIP(InsertPoint(Block, Point));
       Builder.SetCurrentDebugLocation(DbgLoc);
     }
+
+    BasicBlock::iterator GetInsertPoint() const { return Point; }
+    void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
   };
 
   // \brief RAII object that stores the current fast math settings and restores
   // them when the object is destroyed.
   class FastMathFlagGuard {
     IRBuilderBase &Builder;
     FastMathFlags FMF;
     MDNode *FPMathTag;

lib/Analysis/ScalarEvolutionExpander.cpp

for (; ScanLimit; --IP, --ScanLimit) {
           IP->getOperand(1) == RHS)
         return &*IP;
       if (IP == BlockBegin) break;
     }
   }
 
   // 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())) {
     if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
     BasicBlock *Preheader = L->getLoopPreheader();
     if (!Preheader) break;
 
     // Ok, move up a level.
if (IP != BlockBegin) {
         if (IP->getOpcode() == Instruction::GetElementPtr &&
             IP->getOperand(0) == V && IP->getOperand(1) == Idx)
           return &*IP;
         if (IP == BlockBegin) break;
       }
     }
 
     // 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())) {
       if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
       BasicBlock *Preheader = L->getLoopPreheader();
       if (!Preheader) break;
 
       // Ok, move up a level.
       Builder.SetInsertPoint(Preheader->getTerminator());
     }
 
     // Emit a GEP.
     Value *GEP = Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
     rememberInstruction(GEP);
 
     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;
 
       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;
 
       // Ok, move up a level.
       Builder.SetInsertPoint(Preheader->getTerminator());
     }
 
     // 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);
-
-  // Restore the original insert point.
-  Builder.restoreIP(SaveInsertPt);
+  }
 
   return expand(SE.getAddExpr(Ops));
 }
 
 /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
 /// SCEV expansion. If they are nested, this is the most nested. If they are
 /// neighboring, pick the later.
 static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) {
           && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
         return nullptr;
       break;
     }
     return dyn_cast<Instruction>(IncV->getOperand(0));
   }
 }
 
+/// 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(Builder.GetInsertBlock(), 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.
 bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
   if (SE.DT.dominates(IncV, InsertPos))
       return true;
 
   // InsertPos must itself dominate IncV so that IncV's new position satisfies
if (!Oper)
       return false;
     // IncV is safe to hoist.
     IVIncs.push_back(IncV);
     IncV = Oper;
     if (SE.DT.dominates(IncV, InsertPos))
       break;
   }
   for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
+    fixupInsertPoints(*I);
     (*I)->moveBefore(InsertPos);
   }
   return true;
 }
 
 /// Determine if this cyclic phi is in a form that would have been generated by
 /// LSR. We don't care if the phi was actually expanded in this pass, as long
 /// as it is in a low-cost form, for example, no implied multiplication. This
if (ExpandTy->isPointerTy()) {
     rememberInstruction(IncV);
   }
   return IncV;
 }
 
 /// \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) {
+                           Instruction *Pos, PHINode *LoopPhi,
+                           SCEVExpander *SE) {
   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.
+    SE->fixupInsertPoints(InstToHoist);
     InstToHoist->moveBefore(Pos);
     Pos = InstToHoist;
     InstToHoist = cast<Instruction>(InstToHoist->getOperand(0));
   } while (InstToHoist != LoopPhi);
 }
 
 /// \brief Check whether we can cheaply express the requested SCEV in terms of
 /// the available PHI SCEV by truncation and/or inversion of the step.
for (auto &I : *L->getHeader()) {
         TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
       }
     }
 
     if (AddRecPhiMatch) {
       // Potentially, move the increment. We have made sure in
       // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
       if (L == IVIncInsertLoop)
-        hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
+        hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch, this);
 
       // Ok, the add recurrence looks usable.
       // Remember this PHI, even in post-inc mode.
       InsertedValues.insert(AddRecPhiMatch);
       // Remember the increment.
       rememberInstruction(IncV);
       return AddRecPhiMatch;
     }
   }
 
   // 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
   // loop. Remove this loop from the PostIncLoops set before expanding such
   // AddRecs. Otherwise, we cannot find a valid position for the step
   // (i.e. StepV can never dominate its loop header).  Ideally, we could do
   // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
   // so it's not worth implementing SmallPtrSet::swap.
if (isa<Instruction>(Result) &&
       // but hopefully expandCodeFor handles that.
       bool useSubtract =
         !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
       if (useSubtract)
         Step = SE.getNegativeSCEV(Step);
       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);
     }
   }
 
   // We have decided to reuse an induction variable of a dominating loop. Apply
   // truncation and/or invertion of the step.
if (SE.isLoopInvariant(S, L)) {
       break;
     }
 
   // Check to see if we already expanded this here.
   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
   if (I != InsertedExpressions.end())
     return I->second;
 
-  BuilderType::InsertPointGuard Guard(Builder);
+  SCEVInsertPointGuard Guard(Builder, this);
   Builder.SetInsertPoint(InsertPt);
 
   // Expand the expression into instructions.
   Value *V = FindValueInExprValueMap(S, InsertPt);
 
   if (!V)
     V = visit(S);
 
SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
   assert(Ty->isIntegerTy() && "Can only insert integer induction variables!");
 
   // Build a SCEV for {0,+,1}<L>.
   // Conservatively use FlagAnyWrap for now.
   const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0),
                                    SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap);
 
   // Emit code for it.
-  BuilderType::InsertPointGuard Guard(Builder);
+  SCEVInsertPointGuard Guard(Builder, this);
   PHINode *V =
       cast<PHINode>(expandCodeFor(H, nullptr, &L->getHeader()->front()));
 
   return V;
 }
 
 /// replaceCongruentIVs - Check for congruent phis in this loop header and
 /// replace them with their most canonical representative. Return the number of