[SCEV] Update interface to handle SCEVExpander insert point motion.

[gberry]

Summary

This is an extension of the fix in r271424. That fix dealt with builder
insert points being moved by SCEV expansion, but only for the lifetime
of the expand call. This change modifies the interface so that LSR can
safely call expand multiple times at the same insert point and do the
right thing if one of the expansions decides to move the original insert
point.

[hans]

+Sanjoy and Hal, perhaps you could take a look?

This is for PR28719 which is a 3.9 blocker.

[sanjoy]

lgtm, but at this point I'm wondering if there is something we can do to rule out this class of bugs. Any ideas @gberry? Or is the solution here just "be careful when using SCEVExpander".

test/Transforms/LoopStrengthReduce/X86/pr28719.ll

10 ↗

(On Diff #67454)

Can you still please add a CHECK for something obvious, like CHECK-LABEL: @main( ?

[gberry]

The only other solution that comes to mind is instead of fixing up the insert points, avoid moving them in the first place in SCEVExpander. I'm not familiar enough with that code to say whether that makes sense or would cause performance regressions. It's also probably a riskier fix for the release.

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

unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
                                  SmallVectorImpl<WeakVH> &DeadInsts,
                                  const TargetTransformInfo *TTI = nullptr);
 
     /// \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 Insert code to directly compute the specified SCEV expression
+    /// into the program.  The inserted code is inserted into the SCEVExpander's
+    /// current insertion point. If a type is specified, the result will be
+    /// expanded to have that type, with a cast if necessary.
+    Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
+
+
     /// \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
     /// predicate is false and 1 otherwise.
     Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc);
 
     /// \brief A specialized variant of expandCodeForPredicate, handling the
     /// case when we are expanding code for a SCEVEqualPredicate.
#endif
 
     /// \brief Disable the behavior of expanding expressions in canonical form
     /// rather than in a more literal form. Non-canonical mode is useful for
     /// late optimization passes.
     void disableCanonicalMode() { CanonicalMode = false; }
 
     void enableLSRMode() { LSRMode = true; }
 
+    /// \brief Set the current insertion point. This is useful if multiple calls
+    /// to expandCodeFor() are going to be made with the same insert point and
+    /// the insert point may be moved during one of the expansions (e.g. if the
+    /// insert point is not a block terminator).
+    void setInsertPoint(Instruction *IP) {
+      assert(IP);
+      Builder.SetInsertPoint(IP);
+    }
+
     /// \brief Clear the current insertion point. This is useful if the
     /// instruction that had been serving as the insertion point may have been
     /// deleted.
     void clearInsertPoint() {
       Builder.ClearInsertionPoint();
     }
 
     /// \brief Return true if the specified instruction was inserted by the code
Value *expandAddToGEP(const SCEV *const *op_begin,
                           PointerType *PTy, Type *Ty, Value *V);
 
     /// \brief Find a previous Value in ExprValueMap for expand.
     ScalarEvolution::ValueOffsetPair
     FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
 
     Value *expand(const SCEV *S);
 
-    /// \brief Insert code to directly compute the specified SCEV expression
-    /// into the program.  The inserted code is inserted into the SCEVExpander's
-    /// current insertion point. If a type is specified, the result will be
-    /// expanded to have that type, with a cast if necessary.
-    Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
-
     /// \brief Determine the most "relevant" loop for the given SCEV.
     const Loop *getRelevantLoop(const SCEV *);
 
     Value *visitConstant(const SCEVConstant *S) {
       return S->getValue();
     }
 
     Value *visitTruncateExpr(const SCEVTruncateExpr *S);

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,
                                    Instruction *IP) {
-  assert(IP);
-  Builder.SetInsertPoint(IP);
+  setInsertPoint(IP);
   return expandCodeFor(SH, Ty);
 }
 
 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
   // Expand the code for this SCEV.
   Value *V = expand(SH);
   if (Ty) {
     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&

llvm/trunk/lib/Transforms/Scalar/LoopStrengthReduce.cpp

Value *LSRInstance::Expand(const LSRFixup &LF,
                            SmallVectorImpl<WeakVH> &DeadInsts) const {
   const LSRUse &LU = Uses[LF.LUIdx];
   if (LU.RigidFormula)
     return LF.OperandValToReplace;
 
   // Determine an input position which will be dominated by the operands and
   // which will dominate the result.
   IP = AdjustInsertPositionForExpand(IP, LF, LU, Rewriter);
+  Rewriter.setInsertPoint(&*IP);
 
   // Inform the Rewriter if we have a post-increment use, so that it can
   // perform an advantageous expansion.
   Rewriter.setPostInc(LF.PostIncLoops);
 
   // This is the type that the user actually needs.
   Type *OpTy = LF.OperandValToReplace->getType();
   // This will be the type that we'll initially expand to.
for (const SCEV *Reg : F.BaseRegs) {
     assert(!Reg->isZero() && "Zero allocated in a base register!");
 
     // If we're expanding for a post-inc user, make the post-inc adjustment.
     PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops);
     Reg = TransformForPostIncUse(Denormalize, Reg,
                                  LF.UserInst, LF.OperandValToReplace,
                                  Loops, SE, DT);
 
-    Ops.push_back(SE.getUnknown(Rewriter.expandCodeFor(Reg, nullptr, &*IP)));
+    Ops.push_back(SE.getUnknown(Rewriter.expandCodeFor(Reg, nullptr)));
   }
 
   // Expand the ScaledReg portion.
   Value *ICmpScaledV = nullptr;
   if (F.Scale != 0) {
     const SCEV *ScaledS = F.ScaledReg;
 
     // If we're expanding for a post-inc user, make the post-inc adjustment.
     PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops);
     ScaledS = TransformForPostIncUse(Denormalize, ScaledS,
                                      LF.UserInst, LF.OperandValToReplace,
                                      Loops, SE, DT);
 
     if (LU.Kind == LSRUse::ICmpZero) {
       // Expand ScaleReg as if it was part of the base regs.
       if (F.Scale == 1)
         Ops.push_back(
-            SE.getUnknown(Rewriter.expandCodeFor(ScaledS, nullptr, &*IP)));
+            SE.getUnknown(Rewriter.expandCodeFor(ScaledS, nullptr)));
       else {
         // An interesting way of "folding" with an icmp is to use a negated
         // scale, which we'll implement by inserting it into the other operand
         // of the icmp.
         assert(F.Scale == -1 &&
                "The only scale supported by ICmpZero uses is -1!");
-        ICmpScaledV = Rewriter.expandCodeFor(ScaledS, nullptr, &*IP);
+        ICmpScaledV = Rewriter.expandCodeFor(ScaledS, nullptr);
       }
     } else {
       // Otherwise just expand the scaled register and an explicit scale,
       // which is expected to be matched as part of the address.
 
       // Flush the operand list to suppress SCEVExpander hoisting address modes.
       // Unless the addressing mode will not be folded.
       if (!Ops.empty() && LU.Kind == LSRUse::Address &&
           isAMCompletelyFolded(TTI, LU, F)) {
-        Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, &*IP);
+        Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty);
         Ops.clear();
         Ops.push_back(SE.getUnknown(FullV));
       }
-      ScaledS = SE.getUnknown(Rewriter.expandCodeFor(ScaledS, nullptr, &*IP));
+      ScaledS = SE.getUnknown(Rewriter.expandCodeFor(ScaledS, nullptr));
       if (F.Scale != 1)
         ScaledS =
             SE.getMulExpr(ScaledS, SE.getConstant(ScaledS->getType(), F.Scale));
       Ops.push_back(ScaledS);
     }
   }
 
   // Expand the GV portion.
   if (F.BaseGV) {
     // Flush the operand list to suppress SCEVExpander hoisting.
     if (!Ops.empty()) {
-      Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, &*IP);
+      Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty);
       Ops.clear();
       Ops.push_back(SE.getUnknown(FullV));
     }
     Ops.push_back(SE.getUnknown(F.BaseGV));
   }
 
   // Flush the operand list to suppress SCEVExpander hoisting of both folded and
   // unfolded offsets. LSR assumes they both live next to their uses.
   if (!Ops.empty()) {
-    Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, &*IP);
+    Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty);
     Ops.clear();
     Ops.push_back(SE.getUnknown(FullV));
   }
 
   // Expand the immediate portion.
   int64_t Offset = (uint64_t)F.BaseOffset + LF.Offset;
   if (Offset != 0) {
     if (LU.Kind == LSRUse::ICmpZero) {
if (UnfoldedOffset != 0) {
     Ops.push_back(SE.getUnknown(ConstantInt::getSigned(IntTy,
                                                        UnfoldedOffset)));
   }
 
   // Emit instructions summing all the operands.
   const SCEV *FullS = Ops.empty() ?
                       SE.getConstant(IntTy, 0) :
                       SE.getAddExpr(Ops);
-  Value *FullV = Rewriter.expandCodeFor(FullS, Ty, &*IP);
+  Value *FullV = Rewriter.expandCodeFor(FullS, Ty);
 
   // We're done expanding now, so reset the rewriter.
   Rewriter.clearPostInc();
 
   // An ICmpZero Formula represents an ICmp which we're handling as a
   // comparison against zero. Now that we've expanded an expression for that
   // form, update the ICmp's other operand.
   if (LU.Kind == LSRUse::ICmpZero) {

llvm/trunk/test/Transforms/LoopStrengthReduce/X86/pr28719.ll

+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@a = global i32 0, align 4
+@b = global i8 0, align 1
+@c = global [4 x i8] zeroinitializer, align 1
+
+; Just make sure we don't generate code with uses not dominated by defs.
+; CHECK-LABEL: @main(
+define i32 @main() {
+entry:
+  %a0 = load i32, i32* @a, align 4
+  %cmpa = icmp slt i32 %a0, 4
+  br i1 %cmpa, label %preheader, label %for.end
+
+preheader:
+  %b0 = load i8, i8* @b, align 1
+  %b0sext = sext i8 %b0 to i64
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ 0, %preheader ], [ %iv.next, %lor.false ]
+  %mul = mul nsw i64 %b0sext, %iv
+  %multrunc = trunc i64 %mul to i32
+  %cmp = icmp eq i32 %multrunc, 0
+  br i1 %cmp, label %lor.false, label %if.then
+
+lor.false:
+  %cgep = getelementptr inbounds [4 x i8], [4 x i8]* @c, i64 0, i64 %iv
+  %ci = load i8, i8* %cgep, align 1
+  %cisext = sext i8 %ci to i32
+  %ivtrunc = trunc i64 %iv to i32
+  %cmp2 = icmp eq i32 %cisext, %ivtrunc
+  %iv.next = add i64 %iv, 1
+  br i1 %cmp2, label %for.body, label %if.then
+
+if.then:
+  tail call void @abort()
+  unreachable
+
+for.end:
+  ret i32 0
+}
+
+declare void @abort()