[InstCombine] Look through PHIs, GEPs, IntToPtrs and PtrToInts to expose more constants when comparing GEPs

[sbaranga]

Summary

When comparing two GEP instructions which have the same base pointer
and one of them has a constant index, it is possible to only compare
indices, transforming it to a compare with a constant. This removes
one use for the GEP instruction with the constant index, can reduce
register pressure and can sometimes lead to removing the comparisson
entirely.

InstCombine was already doing this when comparing two GEPs if the
base pointers were the same. However, in the case where we have
complex pointer arithmetic (GEPs applied to GEPs, PHIs of GEPs,
conversions to or from integers, etc) the value of the original
base pointer will be hidden to the optimizer and this transformation
will be disabled.

This change detects when the two sides of the comparison can be
expressed as GEPs with the same base pointer, even if they don't
appear as such in the IR. The transformation will convert all the
pointer arithmetic to arithmetic done on indices and all the
relevant uses of GEPs to GEPs with a common base pointer. The
GEP comparison will be converted to a comparison done on indices.

[majnemer]

Please try to name your functions like transformToIndexedCompare instead of TransformToIndexedCompare.

lib/Transforms/InstCombine/InstCombineCompares.cpp

709

Please use auto * here.

836

If you are not using the result of dyn_cast, use isa instead.

862–864

The caller of GetAsConstantIndexedAddress passes in a GEPOperator but you are casting it to an Instruction. How have you ensured that the GEPOperator is an GetElementPtrInst instead of a ConstantExpr ?

Also, Value has a getContext member.

882

Please use auto *CI here.

882–895

Can you use isNoopCast here? Should simplify things.

889

Ditto.

904

Shouldn't this function be static ?

[sbaranga]

Address the review comments so far.

[sbaranga]

Thanks for the review! The new version should fix all the issues pointed out.

-Silviu

lib/Transforms/InstCombine/InstCombineCompares.cpp

862–864

Thanks for the catch, this was indeed an issue. Not doing the cast in the first place should fix this.

[jmolloy]

Hi Silviu,

I've reviewed the first half of the patch and have a bunch of comments.

Cheers,

James

lib/Transforms/InstCombine/InstCombineCompares.cpp

605

Do you really expect 100 items in the worklist?

615

Why aren't you inserting V into Explored here, and just incrementing a counter instead of checking Explored.size() above?

625

It looks like you're checking the *next item to be inserted into the worklist* here; I think it'd be easier to just always insert into the worklist and check each item as it's removed from the worklist up above, like GetUnderlyingObjects does.

631

This and the previous block can be merged together.

645

These ifs can be merged.

655

Don't understand this comment?

668

Can't we insert the GEP after the transformed instruction instead of before the PHI?

692

I can't parse this comment :(

702

This would be better written as

I = &*std::next(I->getIterator());

713

We should assert this.

732

ValueToValueMapTy might help here.

762

It seems a bit strange to do all this work again. You've already explored before; if you'd have just kept the explore order you'd be able to iterate over Explored here without creating it afresh.

[sbaranga]

Hi James,

Thanks for having a look. I've added some replies inline. I should have a new version of this patch that addresses your comments out soon.

Thanks,
Silviu

lib/Transforms/InstCombine/InstCombineCompares.cpp

605

Not frequently, but it is possible. Probably the limit wouldn't be ever reached in practice, but we still need to have it. In my experience if we can't do the transformation we usually bail out early, so it shouldn't be a very big problem.

I can do compile time measurements if you think this would be a problem.

625

My intention was to limit the memory usage of the work list to |V| (you would get |E| if you checked when removing from the worklist). However, it doesn't seem that bad either way.

762

Good idea, thanks! It would technically need to be the reverse order, but that shouldn't be a problem.

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

921

For the particular ICmpInst you've creating here, is this ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) or OFFSET1 cmp OFFSET2? Given that rewriteAsOffsetGEP returns a GEP that uses PtrBase as its base address, it looks like for former. I see no reason it should not be the latter, however.

I think this would be clearer if you used the same names in your comments as you did names for the local variables.

[sbaranga]

lib/Transforms/InstCombine/InstCombineCompares.cpp

668

Theoretically if you have

p0 = phi(x0, x1, ..)
p1 = phi(p0, ..)

you could insert GEPs before x0, x1, etc, and get:
BB1:

y0 = gep(base, x0)

BB2:

y1 = gep(base x1)

BB3:

p0 = phi(y0, y1)
p1 = phi(p0, ..)

However you end up inserting a lot of geps using this strategy. It's not clear to me that this is a good thing.
So we could also handle this case, but I don't think it's worth it.

732

I could use it, but I'm not sure how it would help.

921

Hi Hal,

Should be the latter (in rewriteAsOffsetGEP NewInsts maps the geps to offsets). Maybe rewriteGEPAsOffset would be a better name for that function.

Thanks,
Silviu

[sbaranga]

Merged the traversal algorithms for the from canRewriteAsOffsetGEP and rewriteAsOffsetGEP.
Now the order in recorded in rewriteAsOffsetGEP.

Performed several other small changes requested during review.

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

905

Still don't find this clear. It seems to me that:

std::tie(PtrBase, Index) = GetAsConstantIndexedAddress(GEPLHS, DL);

returns PtrBase and Index such that GEP(PtrBase, Index) == GEPLHS. And then:

RewriteGEPAsOffset(RHS, PtrBase)

returns GEP(PtrBase, Something) == RHS. And then we compare:

Index icmp GEP(PtrBase, Something)

which must be wrong. What am I missing?

[sbaranga]

lib/Transforms/InstCombine/InstCombineCompares.cpp

905

RewriteGEPAsOffset returns the offset, not the GEP.

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

905

Ah, I understand now. The GEP it builds is not returned, but is for use by other users of the original GEP being replaced.

[sbaranga]

lib/Transforms/InstCombine/InstCombineCompares.cpp

905

Yes, that is correct. Would there be any better way to express this?

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

905

Probably not. The code in RewriteGEPAsOffset does say that the GEP is being generated for external users. I did not read it with sufficient care.

I think however, it is worth nothing in a comment here that RHS is being replaced by a rewritten GEP and the GEP's Index operand it being returned. Otherwise, the fact that RHS is no longer valid after the function call is not obvious.

[jmolloy]

Please try to name your functions like transformToIndexedCompare instead of TransformToIndexedCompare.

Please do update your function names to begin with a lower case letter as David asked.

lib/Transforms/InstCombine/InstCombineCompares.cpp

605

OK, but the smallvector value should be optimized for the frequent case. Something like 16 would be more appropriate?

631

You should move the comment inside of the if, so it makes sense.

679

for (auto &Use : Val->uses())  ?

805

Isn't this a ptrtoint?

851

possibility

[sbaranga]

lib/Transforms/InstCombine/InstCombineCompares.cpp

679

This is strange, Value seems to not have a uses() method.

805

The implementation creates a ptrtoint or inttoptr depending on the second argument (Start-getType() here). We know that Start is a pointer since it is produced by a GEP, so this will create a inttoptr.

905

Thanks, I'll add a comment.

[sbaranga]

Change the names of the functions (back) to lower case.
Use a smaller default size for the traversal SmallVector (changed to 16).

[jmolloy]

lib/Transforms/InstCombine/InstCombineCompares.cpp

679

It does! :)

805

Ah OK, My bad misreading this.

[sbaranga]

Changed loops to use the range for syntax.

[sbaranga]

lib/Transforms/InstCombine/InstCombineCompares.cpp

679

Yes, it does, I don't know how I missed it.

[jmolloy]

Hi Silviu,

This now LGTM. Please wait for Hal to give the OK too.

Cheers,

James

[jmolloy]

Optimistic Christmas Season Ping: Hal, did you have any more comments on this or were you happy?

[jmolloy]

Hi,

Actually, I think this looks good enough to me that I can approve.

James

[sbaranga]

Thanks, committed in r257064.

-Silviu

lib/Transforms/InstCombine/InstCombineCompares.cpp

 //===- InstCombineCompares.cpp --------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitICmp and visitFCmp functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/APSInt.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
static Value *EvaluateGEPOffsetExpression(User *GEP, InstCombiner &IC,
   // Okay, we can do this evaluation.  Start by converting the index to intptr.
   if (VariableIdx->getType() != IntPtrTy)
     VariableIdx = IC.Builder->CreateIntCast(VariableIdx, IntPtrTy,
                                             true /*Signed*/);
   Constant *OffsetVal = ConstantInt::get(IntPtrTy, NewOffs);
   return IC.Builder->CreateAdd(VariableIdx, OffsetVal, "offset");
 }
 
+/// Returns true if we can rewrite Start as a GEP with pointer Base
+/// and some integer offset. The nodes that need to be re-written
+/// for this transformation will be added to Explored.
+static bool CanRewriteGEPAsOffset(Value *Start, Value *Base,
+                                  const DataLayout &DL,
+                                  SetVector<Value *> &Explored) {
+  SmallVector<Value *, 100> WorkList(1, Start);
+  Explored.insert(Base);
+
+  // The following traversal gives us an order which can be used
+  // when doing the final transformation. Since in the final
+  // transformation we create the PHI replacement instructions first,
+  // we don't have to get them in any particular order.
+  //
+  // However, for other instructions we will have to traverse the
+  // operands of an instruction first, which means that we have to
+  // do a post-order traversal.
+  while (!WorkList.empty()) {
+    SetVector<PHINode *> PHIs;
+
+    while (!WorkList.empty()) {
+      if (Explored.size() >= 100)
+        return false;
+
+      Value *V = WorkList.back();
+
+      if (Explored.count(V) != 0) {
+        WorkList.pop_back();
+        continue;
+      }
+
+      // We've found some value that we can't explore which is different from
+      // the base. Therefore we can't do this transformation.
+      if (!isa<IntToPtrInst>(V) && !isa<PtrToIntInst>(V) &&
+          !isa<GEPOperator>(V) && !isa<PHINode>(V))
+        return false;
+
+      if (isa<IntToPtrInst>(V) || isa<PtrToIntInst>(V)) {
+        auto *CI = dyn_cast<CastInst>(V);
+        if (!CI->isNoopCast(DL))
+          return nullptr;
+
+        if (Explored.count(CI->getOperand(0)) == 0)
+          WorkList.push_back(CI->getOperand(0));
+      }
+
+      if (auto *GEP = dyn_cast<GEPOperator>(V)) {
+        // We're limiting the GEP to having one index. This will preserve
+        // the original pointer type. We could handle more cases in the
+        // future.
+        if (GEP->getNumIndices() != 1 || !GEP->isInBounds())
+          return nullptr;
+
+        if (Explored.count(GEP->getOperand(0)) == 0)
+          WorkList.push_back(GEP->getOperand(0));
+      }
+
+      if (WorkList.back() == V) {
+        WorkList.pop_back();
+        // We've finished visiting this node, mark it as such.
+        Explored.insert(V);
+      }
+
+      if (auto *PN = dyn_cast<PHINode>(V)) {
+        Explored.insert(PN);
+        PHIs.insert(PN);
+      }
+    }
+
+    // Explore the PHI nodes further.
+    for (auto *PN : PHIs)
+      for (Value *Op : PN->incoming_values())
+        if (Explored.count(Op) == 0)
+        WorkList.push_back(Op);
+  }
+
+  // Make sure that we can do this. Since we can't insert GEPs in a basic
+  // block before a PHI node, we can't easily do this transformation if
+  // we have PHI node users of transformed instructions.
+  for (Value *Val : Explored) {
+    for (auto Use = Val->use_begin(); Use != Val->use_end(); ++Use) {
+
+      auto *PHI = dyn_cast<PHINode>(*Use);
+      auto *Inst = dyn_cast<Instruction>(Val);
+
+      if (Inst == Base || Inst == PHI || !Inst || !PHI ||
+          Explored.count(PHI) == 0)
+        continue;
+
+      if (PHI->getParent() == Inst->getParent())
+        return false;
+    }
+  }
+  return true;
+}
+
+// Sets the appropriate insert point on Builder where we can add
+// a replacement Instruction for V (if that is possible).
+static void SetInsertionPoint(IRBuilder<> &Builder, Value *V,
+                              bool Before = true) {
+  if (auto *PHI = dyn_cast<PHINode>(V)) {
+    Builder.SetInsertPoint(&*PHI->getParent()->getFirstInsertionPt());
+    return;
+  }
+  if (auto *I = dyn_cast<Instruction>(V)) {
+    if (!Before)
+      I = &*std::next(I->getIterator());
+    Builder.SetInsertPoint(I);
+    return;
+  }
+  if (auto *A = dyn_cast<Argument>(V)) {
+    // Set the insertion point in the entry block.
+    BasicBlock &Entry = A->getParent()->getEntryBlock();
+    Builder.SetInsertPoint(&*Entry.getFirstInsertionPt());
+    return;
+  }
+  // Otherwise, this is a constant and we don't need to set a new
+  // insertion point.
+  assert(isa<ConstantExpr>(V) && "Setting insertion point for unknown value!");
+}
+
+/// Returns a re-written value of Start as an indexed GEP using Base as a
+/// pointer.
+static Value *RewriteGEPAsOffset(Value *Start, Value *Base,
+                                 const DataLayout &DL,
+                                 SetVector<Value *> &Explored) {
+  // Perform all the substitutions. This is a bit tricky because we can
+  // have cycles in our use-def chains.
+  // 1. Create the PHI nodes without any incoming values.
+  // 2. Create all the other values.
+  // 3. Add the edges for the PHI nodes.
+  // 4. Emit GEPs to get the original pointers.
+  // 5. Remove the original instructions.
+  Type *IndexType = IntegerType::get(
+      Base->getContext(), DL.getPointerTypeSizeInBits(Start->getType()));
+
+  DenseMap<Value *, Value *> NewInsts;
+  NewInsts[Base] = ConstantInt::getNullValue(IndexType);
+
+  // Create the new PHI nodes, without adding any incoming values.
+  for (Value *Val : Explored) {
+    if (Val == Base)
+      continue;
+    // Create empty phi nodes. This avoids cyclic dependencies when creating
+    // the remaining instructions.
+    if (auto *PHI = dyn_cast<PHINode>(Val))
+      NewInsts[PHI] = PHINode::Create(IndexType, PHI->getNumIncomingValues(),
+                                      PHI->getName() + ".idx", PHI);
+  }
+  IRBuilder<> Builder(Base->getContext());
+
+  // Create all the other instructions.
+  for (auto II = Explored.begin(), EE = Explored.end(); II != EE; ++II) {
+    Value *Val = *II;
+
+    if (NewInsts.find(Val) != NewInsts.end())
+      continue;
+
+    if (auto *CI = dyn_cast<CastInst>(Val)) {
+      NewInsts[CI] = NewInsts[CI->getOperand(0)];
+      continue;
+    }
+    if (auto *GEP = dyn_cast<GEPOperator>(Val)) {
+      Value *Index = NewInsts[GEP->getOperand(1)]
+                         ? NewInsts[GEP->getOperand(1)]
+                         : GEP->getOperand(1);
+      SetInsertionPoint(Builder, GEP);
+      // Indices might need to be sign extended. GEPs will magically do
+      // this, but we need to do it ourselves here.
+      if (Index->getType()->getScalarSizeInBits() !=
+          NewInsts[GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
+        Index = Builder.CreateSExtOrTrunc(
+            Index, NewInsts[GEP->getOperand(0)]->getType(),
+            GEP->getOperand(0)->getName() + ".sext");
+      }
+      NewInsts[GEP] =
+          Builder.CreateAdd(NewInsts[GEP->getOperand(0)], Index,
+                            GEP->getOperand(0)->getName() + ".add");
+      continue;
+
+    }
+    if (isa<PHINode>(Val))
+      continue;
+
+    llvm_unreachable("Unexpected instruction type");
+  }
+
+  // Add the incoming values to the PHI nodes.
+  for (Value *Val : Explored) {
+    if (Val == Base)
+      continue;
+    // All the instructions have been created, we can now add edges to the
+    // phi nodes.
+    if (auto *PHI = dyn_cast<PHINode>(Val)) {
+      PHINode *NewPhi = static_cast<PHINode *>(NewInsts[PHI]);
+      for (unsigned I = 0, E = PHI->getNumIncomingValues(); I < E; ++I) {
+        Value *NewIncoming = PHI->getIncomingValue(I);
+
+        if (NewInsts.find(NewIncoming) != NewInsts.end())
+          NewIncoming = NewInsts[NewIncoming];
+
+        NewPhi->addIncoming(NewIncoming, PHI->getIncomingBlock(I));
+      }
+    }
+  }
+
+  // If required, create a inttoptr instruction.
+  Value *NewBase = Base;
+  SetInsertionPoint(Builder, Base, false);
+  if (!Base->getType()->isPointerTy())
+    NewBase = Builder.CreateBitOrPointerCast(Base, Start->getType(),
+                      Start->getName() +  "to.ptr");
+
+  for (Value *Val : Explored) {
+    if (Val == Base)
+      continue;
+
+    // Depending on the type, for external users we have to emit
+    // a GEP or a GEP + ptrtoint.
+    if (isa<Instruction>(NewInsts[Val]))
+      SetInsertionPoint(Builder, NewInsts[Val], false);
+    else
+      SetInsertionPoint(Builder, NewBase, false);
+
+    Value *GEP =
+        Builder.CreateInBoundsGEP(Start->getType()->getPointerElementType(),
+                                  NewBase, {NewInsts[Val]},
+                                  Val->getName() + ".ptr");
+
+    if (!Val->getType()->isPointerTy()) {
+      Value *Cast = Builder.CreatePointerCast(GEP, Val->getType(),
+                                              Val->getName() + ".conv");
+      GEP = Cast;
+    }
+    Val->replaceAllUsesWith(GEP);
+  }
+
+  return NewInsts[Start];
+}
+
+/// Looks through GEPs, IntToPtrInsts and PtrToIntInsts in order to express
+/// the input Value as a GEP constant indexed GEP. Returns a pair containing
+/// the GEPs Pointer and Index.
+static std::pair<Value *, Value *>
+GetAsConstantIndexedAddress(Value *V, const DataLayout &DL) {
+  Type *IndexType =
+      IntegerType::get(V->getContext(),
+                       DL.getPointerTypeSizeInBits(V->getType()));
+
+  Constant *Index = ConstantInt::getNullValue(IndexType);
+  while (true) {
+    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
+      // We accept only inbouds GEPs here to exclude the possibily of
+      // overflow.
+      if (!GEP->isInBounds())
+        break;
+      if (GEP->hasAllConstantIndices() && GEP->getNumIndices() == 1) {
+        V = GEP->getOperand(0);
+        Constant *GEPIndex = static_cast<Constant *>(GEP->getOperand(1));
+        Index = ConstantExpr::getAdd(
+            Index, ConstantExpr::getSExtOrBitCast(GEPIndex, IndexType));
+        continue;
+      }
+      break;
+    }
+    if (auto *CI = dyn_cast<IntToPtrInst>(V)) {
+      if (!CI->isNoopCast(DL))
+        break;
+      V = CI->getOperand(0);
+      continue;
+    }
+    if (auto *CI = dyn_cast<PtrToIntInst>(V)) {
+      if (!CI->isNoopCast(DL))
+        break;
+      V = CI->getOperand(0);
+      continue;
+    }
+    break;
+  }
+  return {V, Index};
+}
+
+// Converts (CMP GEPLHS, RHS) if this change would make RHS a constant.
+// We can look through PHIs, GEPs and casts in order to determine a
+// common base between GEPLHS and RHS.
+static Instruction *TransformToIndexedCompare(GEPOperator *GEPLHS, Value *RHS,
+                                              ICmpInst::Predicate Cond,
+                                              const DataLayout &DL) {
+  if (!GEPLHS->hasAllConstantIndices())
+    return nullptr;
+
+  Value *PtrBase, *Index;
+  std::tie(PtrBase, Index) = GetAsConstantIndexedAddress(GEPLHS, DL);
+
+  // The set of nodes that will take part in this transformation.
+  SetVector<Value *> Nodes;
+
+  if (!CanRewriteGEPAsOffset(RHS, PtrBase, DL, Nodes))
+    return nullptr;
+
+  // We know we can re-write this as
+  //  ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)
+  // Since we've only looked through inbouds GEPs we know that we
+  // can't have overflow on either side. We can therefore re-write
+  // this as:
+  //   OFFSET1 cmp OFFSET2
+  Value *NewRHS = RewriteGEPAsOffset(RHS, PtrBase, DL, Nodes);
+  return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Index, NewRHS);
+}
+
 /// FoldGEPICmp - Fold comparisons between a GEP instruction and something
 /// else.  At this point we know that the GEP is on the LHS of the comparison.
 Instruction *InstCombiner::FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
                                        ICmpInst::Predicate Cond,
                                        Instruction &I) {
   // Don't transform signed compares of GEPs into index compares. Even if the
   // GEP is inbounds, the final add of the base pointer can have signed overflow
   // and would change the result of the icmp.
   // e.g. "&foo[0] <s &foo[1]" can't be folded to "true" because "foo" could be
   // the maximum signed value for the pointer type.
   if (ICmpInst::isSigned(Cond))
     return nullptr;
 
   // Look through bitcasts and addrspacecasts. We do not however want to remove
   // 0 GEPs.
   if (!isa<GetElementPtrInst>(RHS))
     RHS = RHS->stripPointerCasts();
 
   Value *PtrBase = GEPLHS->getOperand(0);
   if (PtrBase == RHS && GEPLHS->isInBounds()) {
     // ((gep Ptr, OFFSET) cmp Ptr)   ---> (OFFSET cmp 0).
if (PtrBase != GEPRHS->getOperand(0)) {
         }
 
         Value *Cmp = Builder->CreateICmp(ICmpInst::getSignedPredicate(Cond),
                                          LOffset, ROffset);
         return ReplaceInstUsesWith(I, Cmp);
       }
 
       // Otherwise, the base pointers are different and the indices are
-      // different, bail out.
-      return nullptr;
+      // different. Try convert this to an indexed compare by looking through
+      // PHIs/casts.
+      return TransformToIndexedCompare(GEPLHS, RHS, Cond, DL);
     }
 
     // If one of the GEPs has all zero indices, recurse.
     if (GEPLHS->hasAllZeroIndices())
       return FoldGEPICmp(GEPRHS, GEPLHS->getOperand(0),
                          ICmpInst::getSwappedPredicate(Cond), I);
 
     // If the other GEP has all zero indices, recurse.
if (PtrBase == RHS && GEPLHS->isInBounds()) {
     if (GEPsInBounds && (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
         (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
       // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)  --->  (OFFSET1 cmp OFFSET2)
       Value *L = EmitGEPOffset(GEPLHS);
       Value *R = EmitGEPOffset(GEPRHS);
       return new ICmpInst(ICmpInst::getSignedPredicate(Cond), L, R);
     }
   }
-  return nullptr;
+
+  // Try convert this to an indexed compare by looking through PHIs/casts as a
+  // last resort.
+  return TransformToIndexedCompare(GEPLHS, RHS, Cond, DL);
 }
 
 Instruction *InstCombiner::FoldAllocaCmp(ICmpInst &ICI, AllocaInst *Alloca,
                                          Value *Other) {
   assert(ICI.isEquality() && "Cannot fold non-equality comparison.");
 
   // It would be tempting to fold away comparisons between allocas and any
   // pointer not based on that alloca (e.g. an argument). However, even

test/Transforms/InstCombine/indexed-gep-compares.ll

+; RUN: opt -instcombine -S  < %s | FileCheck %s
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:64"
+
+define i32 *@test1(i32* %A, i32 %Offset) {
+entry:
+  %tmp = getelementptr inbounds i32, i32* %A, i32 %Offset
+  br label %bb
+
+bb:
+  %RHS = phi i32* [ %RHS.next, %bb ], [ %tmp, %entry ]
+  %LHS = getelementptr inbounds i32, i32* %A, i32 100
+  %RHS.next = getelementptr inbounds i32, i32* %RHS, i64 1
+  %cond = icmp ult i32 * %LHS, %RHS
+  br i1 %cond, label %bb2, label %bb
+
+bb2:
+  ret i32* %RHS
+
+; CHECK-LABEL: @test1(
+; CHECK:  %[[INDEX:[0-9A-Za-z.]+]] = phi i32 [ %[[ADD:[0-9A-Za-z.]+]], %bb ], [ %Offset, %entry ]
+; CHECK:  %[[ADD]] = add i32 %[[INDEX]], 1
+; CHECK:  %cond = icmp sgt i32 %[[INDEX]], 100
+; CHECK:  br i1 %cond, label %bb2, label %bb
+; CHECK:  %[[PTR:[0-9A-Za-z.]+]] = getelementptr inbounds i32, i32* %A, i32 %[[INDEX]]
+; CHECK:  ret i32* %[[PTR]]
+}
+
+define i32 *@test2(i32 %A, i32 %Offset) {
+entry:
+  %A.ptr = inttoptr i32 %A to i32*
+  %tmp = getelementptr inbounds i32, i32* %A.ptr, i32 %Offset
+  br label %bb
+
+bb:
+  %RHS = phi i32* [ %RHS.next, %bb ], [ %tmp, %entry ]
+  %LHS = getelementptr inbounds i32, i32* %A.ptr, i32 100
+  %RHS.next = getelementptr inbounds i32, i32* %RHS, i64 1
+  %cmp0 = ptrtoint i32 *%LHS to i32
+  %cmp1 = ptrtoint i32 *%RHS to i32
+  %cond = icmp ult i32 %cmp0, %cmp1
+  br i1 %cond, label %bb2, label %bb
+
+bb2:
+  ret i32* %RHS
+
+; CHECK-LABEL: @test2(
+; CHECK:  %[[TOPTR:[0-9A-Za-z.]+]] = inttoptr i32 %[[ADD:[0-9A-Za-z.]+]] to i32*
+; CHECK:  %[[INDEX:[0-9A-Za-z.]+]] = phi i32 [ %[[ADD:[0-9A-Za-z.]+]], %bb ], [ %Offset, %entry ]
+; CHECK:  %[[ADD]] = add i32 %[[INDEX]], 1
+; CHECK:  %cond = icmp sgt i32 %[[INDEX]], 100
+; CHECK:  br i1 %cond, label %bb2, label %bb
+; CHECK:  %[[PTR:[0-9A-Za-z.]+]] = getelementptr inbounds i32, i32* %[[TOPTR]], i32 %[[INDEX]]
+; CHECK:  ret i32* %[[PTR]]
+}
+
+; Perform the transformation only if we know that the GEPs used are inbounds.
+define i32 *@test3(i32* %A, i32 %Offset) {
+entry:
+  %tmp = getelementptr i32, i32* %A, i32 %Offset
+  br label %bb
+
+bb:
+  %RHS = phi i32* [ %RHS.next, %bb ], [ %tmp, %entry ]
+  %LHS = getelementptr i32, i32* %A, i32 100
+  %RHS.next = getelementptr i32, i32* %RHS, i64 1
+  %cond = icmp ult i32 * %LHS, %RHS
+  br i1 %cond, label %bb2, label %bb
+
+bb2:
+  ret i32* %RHS
+
+; CHECK-LABEL: @test3(
+; CHECK-NOT:  %cond = icmp sgt i32 %{{[0-9A-Za-z.]+}}, 100
+}
+
+; An inttoptr that requires an extension or truncation will be opaque when determining
+; the base pointer. In this case we can still perform the transformation by considering
+; A.ptr as being the base pointer.
+define i32 *@test4(i16 %A, i32 %Offset) {
+entry:
+  %A.ptr = inttoptr i16 %A to i32*
+  %tmp = getelementptr inbounds i32, i32* %A.ptr, i32 %Offset
+  br label %bb
+
+bb:
+  %RHS = phi i32* [ %RHS.next, %bb ], [ %tmp, %entry ]
+  %LHS = getelementptr inbounds i32, i32* %A.ptr, i32 100
+  %RHS.next = getelementptr inbounds i32, i32* %RHS, i64 1
+  %cmp0 = ptrtoint i32 *%LHS to i32
+  %cmp1 = ptrtoint i32 *%RHS to i32
+  %cond = icmp ult i32 %cmp0, %cmp1
+  br i1 %cond, label %bb2, label %bb
+
+bb2:
+  ret i32* %RHS
+
+; CHECK-LABEL: @test4(
+; CHECK:  %cond = icmp sgt i32 %{{[0-9A-Za-z.]+}}, 100
+}