[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 ↗

(On Diff #58700)

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

include/llvm/IR/IRBuilder.h

229 ↗

(On Diff #58700)

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 ↗

(On Diff #58700)

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 ↗

(On Diff #59090)

Minor: add newline between declarations.

123 ↗

(On Diff #59090)

Assert that this is empty when destroying a SCEVExpander.

188 ↗

(On Diff #59090)

This should be a private function.

[gberry]

Thanks Sanjoy.

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

367

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

llvm/trunk/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;
 
+    // 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<BasicBlock> 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<SCEVInsertPointGuard *, 8> InsertPointGuards;
+
 #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
     }
 
+    ~SCEVExpander() {
+      // Make sure the insert point guard stack is consistent.
+      assert(InsertPointGuards.empty());
+    }
+
 #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() {
private:
     PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
                                        const Loop *L,
                                        Type *ExpandTy,
                                        Type *IntTy,
                                        Type *&TruncTy,
                                        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);
   };
 }
 
 #endif

llvm/trunk/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(&*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
IncV = useSubtract ?
       Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
     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,
+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<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.
if (AddRecPhiMatch) {
       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