[SCEV] Suppress hoisting insertion point of binops when unsafe

[wristow]

Summary

InsertBinop tries to move insertion-points out of loops for expressions that are loop-invariant. This patch adds a new parameter, IsSafeToHost (default true), to guard that hoisting. This allows callers to suppress that hoisting for unsafe situations, such as divisions that may have a zero denominator.

This fixes PR38697.

[wristow]

Since the callers of SCEVExpander::InsertBinop "know" whether the binop being inserted is safe to hoist, this proposed solution of having the caller pass a parameter to indicate whether it's safe seems clean. But a simpler approach is to special-case the opcode Instruction::UDiv in InsertBinop.

An even simpler approach is to simply never hoist the insertion-point in InsertBinop. In fact, in the cases I've examined, SCEVExpander::expand always did the desired hoisting when it was safe, anyway. So removing the loop that I'm guarding here with the new parameter IsSafeToHoist is equivalent for those test-cases (the check-all tests all passed on x86_64-linux if I simply removed the loop entirely). I'd be happy to go with this approach of removing the hoisting loop, but I don't know for certain whether the hoisting is always redundant with other optimizations.

To try to understand (and in particular, to try to find a test-case that depended on that hoisting being done), I looked through the history of that hosting loop. I see it was added more than 8 years ago (r97642):

Make SCEVExpander and LSR more aggressive about hoisting expressions out
of loops.

But that revision didn't include any test-cases. So I'm at a loss to demonstrate whether there are any cases where the code-gen is improved by the hoisting.

In investigating this history, I noticed a couple of other interesting points.

First, the patch here, along with the recently committed patch of:
https://reviews.llvm.org/rL347934

is equivalent to a patch that was committed about a year ago:
https://reviews.llvm.org/rL289412

(As an aside, that year-old commit uses the simpler approach of special-casing the opcode Instruction::UDiv in InsertBinop to guard the loop, rather than having the caller pass an extra parameter to indicate when it's unsafe to hoist.)

Second, the reason this patch and the recently committed r347934 are needed (even though this was fixed a year ago by r289412), is because that year-old fix was reverted at r289453:

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

@rnk: I wanted to give you a heads up that that problem may re-apear once this patch is reviewed and committed.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

852

Limiting to constants looks super-conservative. How about getting SCEV for RHS and then asking SE isKnownPredicate(ICMP_NE, RHS, 0)?

[wristow]

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

852

Sounds good.

That said, I've put this work on the back-burner for the moment, because the effectiveness of this patch depends on the change of rL347934 being in place, and that commit was reverted today (at rL348426), due to SEGVs happening in PHINode Simplification in Instcombine. That may be the same underlying problem that motivated the revert I previously mentioned that was done about a year ago:

Reverts r289412. It caused an OOB PHI operand access in instcombine when
ASan is enabled. Reduction in progress.

In any case, until the fix that was done as rL347934 is re-instated in some form, I'll hold off on making the fix discussed here.

[wristow]

Limiting to constants looks super-conservative. How about getting SCEV for RHS and then asking SE isKnownPredicate(ICMP_NE, RHS, 0)?

Sounds good. ... In any case, until the fix that was done as rL347934 is re-instated in some form, I'll hold off on making the fix discussed here.

That fix has been reinstated at r356392 (D57428) so I'm now addressing this issue.

Taking the suggestion of isKnownPredicate(ICMP_NE, RHS, 0) from @mkazantsev, I see that for this situation, SE.isKnownNonZero(S->getRHS()) can be used. The resulting patch is then simpler than my original patch proposed here, and it adds the more aggressive analysis Max suggested. I've added additional tests in this update, which includes testing for that more aggressive behavior of the hoisting of a non-constant divisor that can be proven to be non-zero.

[wristow]

ping

[wristow]

ping

[wristow]

ping x 3

[sanjoy]

Only minor nitpicky comments, will LGTM once these are fixed.

Normally I'd ask you to wait for Max, but looks like he is no longer at Azul and thus is not getting phabricator emails.

include/llvm/Analysis/ScalarEvolutionExpander.h

321 ↗

(On Diff #192943)

I'd slightly prefer to not default this to anything, is that feasible?

test/Transforms/LoopVectorize/pr38697.ll

202 ↗

(On Diff #192943)

We should give these instructions names so that updating the tests remains easy (use opt -instnamer).

228 ↗

(On Diff #192943)

Can you please make these CHECK lines a bit more specific? Maybe using update_test_checks.py?

[wristow]

Thanks for the review @sanjoy!

I've removed the default setting of the IsSafeToHoist argument, and I've used opt -instnamer to give the instructions names.

I also ran update_test_checks.py, but I felt compelled to edit the result down significantly (because there were so many instructions that were not related to the optimization, and I was worried it would make the resulting test too sensitive to unrelated changes in llvm). After editing it down to what I felt were the relevant instructions, I then also wanted to add some checks to verify that a division did not appear in places where it shouldn't be hoisted to. With that, I decided it was so different from the results of update_test_checks.py that I decided to remove the comment Assertions have been autogenerated by utils/update_test_checks.py. Bottom line: There are more explicit checks than I had originally, but not anywhere near the full set that would appear from that script. If you'd prefer that I leave the more substantial set of checks in place, let me know, and it will be easy for me to "un-do" much of the editing-down I did.

[wristow]

test/Transforms/LoopVectorize/pr38697.ll

228 ↗

(On Diff #192943)

I've addressed this to some extent, but edited it down significantly. Let me know if you'd prefer the larger set of tests.

[sanjoy]

lgtm

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

833

Can you please add /*IsSafeToHoist*/ on these arguments?

[wristow]

In D55232#1494448, @sanjoy wrote:

lgtm

Thanks for the review!

llvm/include/llvm/Analysis/ScalarEvolutionExpander.h

private:
     LLVMContext &getContext() const { return SE.getContext(); }
 
     /// Recursive helper function for isHighCostExpansion.
     bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
                                    const Instruction *At,
                                    SmallPtrSetImpl<const SCEV *> &Processed);
 
     /// Insert the specified binary operator, doing a small amount of work to
-    /// avoid inserting an obviously redundant operation.
-    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
+    /// avoid inserting an obviously redundant operation, and hoisting to an
+    /// outer loop when the opportunity is there and it is safe.
+    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
+                       bool IsSafeToHoist = true);
 
     /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
     /// cast if a suitable one exists, moving an existing cast if a suitable one
     /// exists but isn't in the right place, or creating a new one.
     Value *ReuseOrCreateCast(Value *V, Type *Ty,
                              Instruction::CastOps Op,
                              BasicBlock::iterator IP);
 

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
 
   // Cast the instruction immediately after the instruction.
   Instruction *I = cast<Instruction>(V);
   BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
   return ReuseOrCreateCast(I, Ty, Op, IP);
 }
 
 /// InsertBinop - Insert the specified binary operator, doing a small amount
-/// of work to avoid inserting an obviously redundant operation.
+/// of work to avoid inserting an obviously redundant operation, and hoisting
+/// to an outer loop when the opportunity is there and it is safe.
 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
-                                 Value *LHS, Value *RHS) {
+                                 Value *LHS, Value *RHS, bool IsSafeToHoist) {
   // Fold a binop with constant operands.
   if (Constant *CLHS = dyn_cast<Constant>(LHS))
     if (Constant *CRHS = dyn_cast<Constant>(RHS))
       return ConstantExpr::get(Opcode, CLHS, CRHS);
 
   // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
   unsigned ScanLimit = 6;
   BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
for (; ScanLimit; --IP, --ScanLimit) {
       if (IP == BlockBegin) break;
     }
   }
 
   // Save the original insertion point so we can restore it when we're done.
   DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
   SCEVInsertPointGuard Guard(Builder, this);
 
+  if (IsSafeToHoist) {
     // 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.
   Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
   BO->setDebugLoc(Loc);
   rememberInstruction(BO);
 
   return BO;
 }
if (!Prod) {
       if (isa<Constant>(Prod)) std::swap(Prod, W);
       const APInt *RHS;
       if (match(W, m_Power2(RHS))) {
         // Canonicalize Prod*(1<<C) to Prod<<C.
         assert(!Ty->isVectorTy() && "vector types are not SCEVable");
         Prod = InsertBinop(Instruction::Shl, Prod,
                            ConstantInt::get(Ty, RHS->logBase2()));
       } else {
         Prod = InsertBinop(Instruction::Mul, Prod, W);
       }
     }
   }
 
   return Prod;
 }
 
 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
 
   Value *LHS = expandCodeFor(S->getLHS(), Ty);
+  bool IsSafeToHoist = false;  // Most divisions are assumed not safe to hoist.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
     const APInt &RHS = SC->getAPInt();
     if (RHS.isPowerOf2())
       return InsertBinop(Instruction::LShr, LHS,
                          ConstantInt::get(Ty, RHS.logBase2()));
+    // Division by non-zero constants are safe to hoist.
+    IsSafeToHoist = !SC->getValue()->isZero();
   }
 
   Value *RHS = expandCodeFor(S->getRHS(), Ty);
-  return InsertBinop(Instruction::UDiv, LHS, RHS);
+  return InsertBinop(Instruction::UDiv, LHS, RHS, IsSafeToHoist);
 }
 
 /// Move parts of Base into Rest to leave Base with the minimal
 /// expression that provides a pointer operand suitable for a
 /// GEP expansion.
 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
                               ScalarEvolution &SE) {
   while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {

llvm/test/Transforms/LoopVectorize/pr38697.ll

+; RUN: opt -loop-vectorize -force-vector-width=2 -S < %s 2>&1 | FileCheck %s
+
+; Produced from test-case:
+;
+; void testCountIncrLoop(unsigned char *ptr, int lim, int count, int val)
+; {
+;   int inx = 0;
+;   for (int outer_i = 0; outer_i < lim; ++outer_i) {
+;     if (count > 0) { // At runtime, 'count' is 0, so the following code is dead.
+;       int result = val;
+;       int tmp = count;
+;
+;       while (tmp < 8) {
+;         result += val >> tmp;
+;         tmp += count;
+;       }
+;
+;       ptr[inx++] = (unsigned char) result;
+;     }
+;   }
+; }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @testCountIncrLoop(i8* %ptr, i32 %lim, i32 %count, i32 %val) {
+entry:
+  %cmp1 = icmp sgt i32 %lim, 0
+  br i1 %cmp1, label %loop1.preheader, label %exit
+
+; Verify that a 'udiv' does not appear between the 'loop1.preheader' label, and
+; the 'while.cond.preheader' label.  And verify that a 'udiv' does appear at
+; some point after the 'while.cond.preheader' label.
+; CHECK: loop1.preheader:
+; CHECK-NOT: udiv
+; CHECK: while.cond.preheader:
+; CHECK: udiv
+
+loop1.preheader:
+  %cmp2 = icmp sgt i32 %count, 0
+  %cmp4 = icmp slt i32 %count, 8
+  br label %loop1.body
+
+loop1.body:
+  %outer_i = phi i32 [ 0, %loop1.preheader ], [ %outer_i.1, %loop1.inc ]
+  %inx.1 = phi i32 [ 0, %loop1.preheader ], [ %inx.2, %loop1.inc ]
+  br i1 %cmp2, label %while.cond.preheader, label %loop1.inc
+
+while.cond.preheader:
+  br i1 %cmp4, label %while.body, label %while.end
+
+while.body:
+  %tmp = phi i32 [ %add3, %while.body ], [ %count, %while.cond.preheader ]
+  %result.1 = phi i32 [ %add, %while.body ], [ %val, %while.cond.preheader ]
+  %shr = ashr i32 %val, %tmp
+  %add = add nsw i32 %shr, %result.1
+  %add3 = add nsw i32 %tmp, %count
+  %cmp3 = icmp slt i32 %add3, 8
+  br i1 %cmp3, label %while.body, label %while.end
+
+while.end:
+  %result.0.lcssa = phi i32 [ %val, %while.cond.preheader ], [ %add, %while.body ]
+  %conv = trunc i32 %result.0.lcssa to i8
+  %inc = add nsw i32 %inx.1, 1
+  %idxprom = sext i32 %inx.1 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %ptr, i64 %idxprom
+  store i8 %conv, i8* %arrayidx, align 1
+  br label %loop1.inc
+
+loop1.inc:
+  %inx.2 = phi i32 [ %inc, %while.end ], [ %inx.1, %loop1.body ]
+  %outer_i.1 = add nuw nsw i32 %outer_i, 1
+  %exitcond = icmp eq i32 %outer_i.1, %lim
+  br i1 %exitcond, label %exit, label %loop1.body
+
+exit:
+  ret void
+}