[IndVars] Special case the problematic (gep inbounds p, iv == nullptr) problem (pr42357)

[reames]

Summary

LFTR and SCEV interact badly on the following test case:

%gep = getelementptr inbounds i8, i8* %base, i64 %iv
%cnd1 = icmp ne i8* null, %gep
br i1 %cnd1, label %latch, label %exit

SCEV will happily compute an exit count for this, but does so disregarding the inbounds annotation. As a result, we end up with a integer comparison of the following form:

%cnd1 = icmp ne i64 %iv, -1 * (ptrtoint(p))
br i1 %cnd1, label %latch, label %exit

Once we've done that, we delete the GEP, and loose the inbounds fact. At that point, we're stuck.

As somewhat of a hack, this patch implements a special case rule to discharge the null check before LFTR has a chance transform it. I don't really like this solution, but after a fair amount of thought, I can't come up with anything better which isn't either a) just as much of a special case, or b) a huge amount of complexity.

(For context, the reported compile time regression happens purely because we end with a loop which "more analyzeable" after LFTR (11 occurrences), and other transforms go to town. We never discharged the check at all - in either form -, and in the faster case just left the loops unoptimized. This special case appears to address the slowdown on this example.)

[grandinj]

lib/Transforms/Utils/SimplifyIndVar.cpp

195

looses->loses

198

loose->lose

[nikic]

lib/Transforms/Utils/SimplifyIndVar.cpp

206

GEP->getType()->isPointerTy() should always be true for a single-index GEP ... right?

220

I believe we also need to check for a pointer to a zero-sized type here, in which case we might have null + 0*Idx == null even if the index is non-zero.

[reames]

lib/Transforms/Utils/SimplifyIndVar.cpp

206

Nope. The following is valid:
%vec_gep = gep i8, i8* %scalar_base, <2 x i64> zeroinitializer

(That's equivalent to a broadcast.)

220

Just to make sure I'm following you, you concern is a zero-sized *index type* right? If so, no, that's disallowed by the verifier.

[nikic]

lib/Transforms/Utils/SimplifyIndVar.cpp

206

Oh right, thanks.

220

I'm not sure what the right terminology is, but I mean something like getelementptr {}, {}* %p, i32 %idx, which is legal and evaluates to {}* %p.

[jdoerfert]

I somehow have a bad feeling about this pattern matching "hack".

After looking at some of the test cases only, couldn't we rewrite null comparisons against a gep inbounds altogether in a more generic way?

I mean something like this, assuming null is not a valid pointer:

%c = icmp eq, null, gep inbounds %p %idx
%d = icmp ne, null, gep inbounds %p %idx

will become

%c0 = icmp eq, ptrtoint(%p), 0
%c1 = icmp eq,         %idx, 0
%c = and %c0, %c1
%d = xor %c, 1

Now, %c0 is loop invariant and %c1 is false for all but one iteration (in the common case of a counting loops).
In addition, if we can show %p != null we know %c0 is false which makes %c false as well and %d true.

Maybe I made a mistake but if the above logic holds, I would prefer a solution like that in one or two steps, that is perform the transformation either way and then check if %p is nonnull or only do it if we know %p is nonnull (maybe in inst-combine)?

lib/Transforms/Utils/SimplifyIndVar.cpp

219

I am confused by this comment, especially the negative part.

Without thinking about it too much I would have said somehting like this:

// With inbounds, 'g = p + NonZero' implies both g and p are valid pointers. Assuming null is not a valid pointer in this function, see NullPointerIsDefined above, we know g and p are both non-null. Note, this does not hold if the offset is zero.

220

assuming you meant the inbounds case and this is legal, which I can imagine it is, we might have missed this special case in other places as well.

[reames]

Just indicating in the review state that the next action item here is mine. Probably not going to get back to this for a bit, so want that to be clear to reviewers.

[reames]

See https://reviews.llvm.org/D66608 for an alternate approach in InstCombine as suggested in review here.

[jdoerfert]

In D64533#1641523, @reames wrote:

See https://reviews.llvm.org/D66608 for an alternate approach in InstCombine as suggested in review here.

FWIW, I like the D66608 approach way better.

[reames]

Alternate change landed, so patch abandoned.

In D64533#1641871, @jdoerfert wrote:

FWIW, I like the D66608 approach way better.

For the record, it was the discussion on the PoisonChecking review which made me realize the alternate approach was possible. Particularly the comments about the out of bounds base immediately triggering poison for an inbounds GEP. Without that, the alternate approach didn't seem feasible. So thanks!

lib/Transforms/Utils/SimplifyIndVar.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,
   ICmpInst::Predicate Pred = ICmp->getPredicate();
   if (IVOperand != ICmp->getOperand(0)) {
     // Swapped
     assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
     IVOperIdx = 1;
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
 
+  Value* Other = ICmp->getOperand(1 - IVOperIdx);
+  
+  // Pattern match the form
+  //  loop_exit_br (icmp ne/eq (gep inbounds p, (0,+,Stride)) nullptr)
+  // and convert it into a loop invariant null check on 'p' since we know the
+  //  address can't wrap and the allocation is of size==0 (i.e. p can't validly
+  //  be beyond null to start with if it's ever inbounds at null).
+  // 
+  // Note: We handle this explicitly in terms of values as SCEV looses the
+  //  inbounds facts on the GEP when forming the SCEV expressions.  If we don't
+  //  special case this here, we'll LFTR the expression into a form where due
+  //  to the lost inbounds, we'll loose the ability to discharge the check.
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(IVOperand))
+    if (ICmpInst::isEquality(Pred) &&
+        isa<Constant>(Other) && cast<Constant>(Other)->isNullValue() &&
+        !NullPointerIsDefined(ICmp->getFunction(),
+                              Other->getType()->getPointerAddressSpace()) &&
+        GEP->isInBounds() && GEP->getNumOperands() == 2 &&
+        L->isLoopInvariant(GEP->getPointerOperand()) &&
+        GEP->getType()->isPointerTy()) {
+      IRBuilder<> B(ICmp);
+
+      // TODO: factor our GEP expression generation logic (i.e. split
+      // getGEPExpr into indexing and base addition portions)
+      auto &DL = ICmp->getModule()->getDataLayout();
+      auto *ImplicitType =
+        B.getIntNTy(DL.getPointerSizeInBits(GEP->getPointerAddressSpace()));
+      const SCEV *Idx =
+        SE->getTruncateOrSignExtend(SE->getSCEV(GEP->getOperand(1)),
+                                    ImplicitType);
+      
+      // With inbounds, p + PosNum != nullptr;
+      // whereas p + NegNum == nullptr would imply p is out of bounds
+      if (SE->isKnownNonZero(Idx)) {
+        if (Pred == ICmpInst::ICMP_NE)
+          ICmp->replaceAllUsesWith(B.getTrue());
+        else
+          ICmp->replaceAllUsesWith(B.getFalse());
+        DeadInsts.emplace_back(ICmp);
+        return true;
+      }
+      
+
+      // If this condition controls an exiting branch which dominates the
+      // latch, return it.  Else, return null.
+      auto getControlledExitBr = [this](Loop *L, Value *Cond) -> BranchInst* {
+        if (Cond->user_begin() == Cond->user_end())
+          return nullptr;
+        auto I = Cond->user_begin();
+        if (std::next(I) != Cond->user_end())
+          return nullptr;
+        if (BasicBlock *Latch = L->getLoopLatch())
+          if (BranchInst *BI = dyn_cast<BranchInst>(*I))
+            if (DT->dominates(BI->getParent(), Latch)) {
+              unsigned ContainedCount = 0;
+              for (BasicBlock *BB : successors(BI->getParent()))
+                if (L->contains(BB))
+                  ContainedCount++;
+              if (ContainedCount == 1)
+                return BI;
+            }
+        return nullptr;
+      };
+
+      if (isa<SCEVAddRecExpr>(Idx) &&
+          cast<SCEVAddRecExpr>(Idx)->getStart()->isZero())
+        if (getControlledExitBr(L, ICmp)) {
+          Value *Base = GEP->getPointerOperand();
+          Value *Null =
+            ConstantPointerNull::get(cast<PointerType>(Base->getType()));
+          ICmp->replaceAllUsesWith(B.CreateICmp(Pred, Base, Null));
+          DeadInsts.emplace_back(ICmp);
+          return true;
+        }
+
+      // We could emit two conditions (one loop invariant null check, one
+      // loop varying check on Idx) if desired, but choose not since
+      // profitability is non-obvious.
+    }
+
+
   // Get the SCEVs for the ICmp operands (in the specific context of the
   // current loop)
   const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
-  const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
-  const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
+  const SCEV *S = SE->getSCEVAtScope(IVOperand, ICmpLoop);
+  const SCEV *X = SE->getSCEVAtScope(Other, ICmpLoop);
 
   ICmpInst::Predicate InvariantPredicate;
   const SCEV *InvariantLHS, *InvariantRHS;
 
   auto *PN = dyn_cast<PHINode>(IVOperand);
   if (!PN)
     return false;
   if (!SE->isLoopInvariantPredicate(Pred, S, X, L, InvariantPredicate,

test/Transforms/IndVarSimplify/inbounds-gep-null.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S < %s -indvars | FileCheck %s
+
+@G = external global i32
+
+define void @test_ne(i8* %base) {
+; CHECK-LABEL: @test_ne(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ne i8* [[BASE:%.*]], null
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LATCH]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store volatile i32 0, i32* @G
+; CHECK-NEXT:    [[CND2:%.*]] = icmp ult i64 [[IV]], 200
+; CHECK-NEXT:    br i1 [[CND2]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [0, %entry], [%iv.next, %latch]
+  %iv.next = add nsw nuw i64 %iv, 1
+  %gep = getelementptr inbounds i8, i8* %base, i64 %iv
+  %cnd1 = icmp ne i8* %gep, null
+  br i1 %cnd1, label %latch, label %exit
+latch:
+  store volatile i32 0, i32* @G
+  %cnd2 = icmp ult i64 %iv, 200
+  br i1 %cnd2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_ne_non_zero_idx(i8* %base) {
+; CHECK-LABEL: @test_ne_non_zero_idx(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    br i1 true, label [[LATCH]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store volatile i32 0, i32* @G
+; CHECK-NEXT:    [[CND2:%.*]] = icmp ult i64 [[IV]], 200
+; CHECK-NEXT:    br i1 [[CND2]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [1, %entry], [%iv.next, %latch]
+  %iv.next = add nsw nuw i64 %iv, 1
+  %gep = getelementptr inbounds i8, i8* %base, i64 %iv
+  %cnd1 = icmp ne i8* %gep, null
+  br i1 %cnd1, label %latch, label %exit
+latch:
+  store volatile i32 0, i32* @G
+  %cnd2 = icmp ult i64 %iv, 200
+  br i1 %cnd2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_ne_unknown_start(i8* %base, i64 %start) {
+; CHECK-LABEL: @test_ne_unknown_start(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[CND1:%.*]] = icmp ne i8* [[GEP]], null
+; CHECK-NEXT:    br i1 [[CND1]], label [[LATCH]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store volatile i32 0, i32* @G
+; CHECK-NEXT:    [[CND2:%.*]] = icmp ult i64 [[IV]], 200
+; CHECK-NEXT:    br i1 [[CND2]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [%start, %entry], [%iv.next, %latch]
+  %iv.next = add nsw nuw i64 %iv, 1
+  %gep = getelementptr inbounds i8, i8* %base, i64 %iv
+  %cnd1 = icmp ne i8* %gep, null
+  br i1 %cnd1, label %latch, label %exit
+latch:
+  store volatile i32 0, i32* @G
+  %cnd2 = icmp ult i64 %iv, 200
+  br i1 %cnd2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_eq(i8* %base) {
+; CHECK-LABEL: @test_eq(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i8* [[BASE:%.*]], null
+; CHECK-NEXT:    br i1 [[TMP0]], label [[EXIT:%.*]], label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    store volatile i32 0, i32* @G
+; CHECK-NEXT:    [[CND2:%.*]] = icmp ult i64 [[IV]], 200
+; CHECK-NEXT:    br i1 [[CND2]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [0, %entry], [%iv.next, %latch]
+  %iv.next = add nsw nuw i64 %iv, 1
+  %gep = getelementptr inbounds i8, i8* %base, i64 %iv
+  %cnd1 = icmp eq i8* %gep, null
+  br i1 %cnd1, label %exit, label %latch
+latch:
+  store volatile i32 0, i32* @G
+  %cnd2 = icmp ult i64 %iv, 200
+  br i1 %cnd2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_eq_noloop(i8* %base) {
+; CHECK-LABEL: @test_eq_noloop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i8* [[BASE:%.*]], null
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LATCH]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store volatile i32 0, i32* @G
+; CHECK-NEXT:    [[CND2:%.*]] = icmp ult i64 [[IV]], 200
+; CHECK-NEXT:    br i1 [[CND2]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [0, %entry], [%iv.next, %latch]
+  %iv.next = add nsw nuw i64 %iv, 1
+  %gep = getelementptr inbounds i8, i8* %base, i64 %iv
+  %cnd1 = icmp eq i8* %gep, null
+  br i1 %cnd1, label %latch, label %exit
+latch:
+  store volatile i32 0, i32* @G
+  %cnd2 = icmp ult i64 %iv, 200
+  br i1 %cnd2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+
+define void @test_ne_swapped_cmp_operands(i8* %base) {
+; CHECK-LABEL: @test_ne_swapped_cmp_operands(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ne i8* [[BASE:%.*]], null
+; CHECK-NEXT:    br i1 [[TMP0]], label [[LATCH]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store volatile i32 0, i32* @G
+; CHECK-NEXT:    [[CND2:%.*]] = icmp ult i64 [[IV]], 200
+; CHECK-NEXT:    br i1 [[CND2]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %iv = phi i64 [0, %entry], [%iv.next, %latch]
+  %iv.next = add nsw nuw i64 %iv, 1
+  %gep = getelementptr inbounds i8, i8* %base, i64 %iv
+  %cnd1 = icmp ne i8* null, %gep
+  br i1 %cnd1, label %latch, label %exit
+latch:
+  store volatile i32 0, i32* @G
+  %cnd2 = icmp ult i64 %iv, 200
+  br i1 %cnd2, label %loop, label %exit
+
+exit:
+  ret void
+}