[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

708

Please use auto * here.

835

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

861–863

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.

881

Please use auto *CI here.

881–894

Can you use isNoopCast here? Should simplify things.

888

Ditto.

903

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

861–863

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

604

Do you really expect 100 items in the worklist?

614

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

624

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.

630

This and the previous block can be merged together.

644

These ifs can be merged.

654

Don't understand this comment?

667

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

691

I can't parse this comment :(

701

This would be better written as

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

712

We should assert this.

731

ValueToValueMapTy might help here.

761

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

604

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.

624

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.

761

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

920

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

667

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.

731

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

920

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

904

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

904

RewriteGEPAsOffset returns the offset, not the GEP.

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

904

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

904

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

[hfinkel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

904

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

604

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

630

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

678

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

804

Isn't this a ptrtoint?

850

possibility

[sbaranga]

lib/Transforms/InstCombine/InstCombineCompares.cpp

678

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

804

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.

904

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

678

It does! :)

804

Ah OK, My bad misreading this.

[sbaranga]

Changed loops to use the range for syntax.

[sbaranga]

lib/Transforms/InstCombine/InstCombineCompares.cpp

678

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

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 CanRewriteAsOffsetGEP(Value *Start, Value *Base,
+                                  const DataLayout &DL,
+                                  SmallPtrSetImpl<Value *> &Explored) {
+  SmallVector<Value *, 100> WorkList(1, Start);
+
+  Explored.insert(Base);
+  Explored.insert(Start);
+
+  // DFS traversal.
+  while (!WorkList.empty()) {
+    if (Explored.size() >= 100)
+      return false;
+
+    Value *V = WorkList.pop_back_val();
+
+    if (V == Base)
+      continue;
+
+    if (IntToPtrInst *CI = dyn_cast<IntToPtrInst>(V)) {
+      // Make sure this operation doesn't have an implicit zext/sext/trunc.
+      if (DL.getPointerTypeSizeInBits(CI->getType()) !=
+          CI->getOperand(0)->getType()->getScalarSizeInBits())
+        return nullptr;
+
+      if (Explored.insert(CI->getOperand(0)).second) {
+        WorkList.push_back(CI->getOperand(0));
+      }
+      continue;
+    }
+
+    if (PtrToIntInst *CI = dyn_cast<PtrToIntInst>(V)) {
+      // Make sure this operation doesn't have an implicit zext/sext/trunc.
+      if (CI->getType()->getScalarSizeInBits() !=
+          DL.getPointerTypeSizeInBits(CI->getOperand(0)->getType()))
+        return nullptr;
+
+      if (Explored.insert(CI->getOperand(0)).second)
+        WorkList.push_back(CI->getOperand(0));
+      continue;
+    }
+
+    if (GEPOperator *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)
+        return nullptr;
+      if (!GEP->isInBounds())
+        return nullptr;
+
+      if (Explored.insert(GEP->getOperand(0)).second)
+        WorkList.push_back(GEP->getOperand(0));
+      continue;
+    }
+
+    // Scan the operands to see if they are either phi nodes or are equal to
+    // the value.
+    if (PHINode *PN = dyn_cast<PHINode>(V)) {
+      for (Value *Op : PN->incoming_values())
+        if (Explored.insert(Op).second)
+          WorkList.push_back(Op);
+      continue;
+    }
+    // We've found some value that we can't explore which is different from
+    // the base. Therefore we can't do this transformation.
+    return false;
+  }
+
+  // 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);
+
+      // Don't change Base.
+      if (Inst == Base)
+        continue;
+
+      if ((Inst == PHI) || (!Inst) || (!PHI) || (Explored.count(PHI) == 0))
+        continue;
+
+      if (PHI->getParent() == Inst->getParent()) {
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+/// Sets the insertion point of the builder depending on the type of value that
+/// that will constitute an input for the instructions/values that we're going
+/// to emit.
+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 = &*(++BasicBlock::iterator(I));
+    Builder.SetInsertPoint(I);
+    return;
+  }
+  if (Argument *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.
+}
+
+/// Returns a re-written value of Start as an indexed GEP using Base as a
+/// pointer.
+static Value *RewriteAsOffsetGEP(Value *Start, Value *Base,
+                                 const DataLayout &DL,
+                                 SmallPtrSetImpl<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 (Value *Val : Explored) {
+    if (NewInsts.find(Val) != NewInsts.end())
+      continue;
+
+    SmallVector<Value *, 100> RList(1, Val);
+
+    while (!RList.empty()) {
+      Value *R = RList.pop_back_val();
+      if (NewInsts.find(R) != NewInsts.end())
+        continue;
+
+      if (R == Base)
+        continue;
+
+      // Create a new instruction for R.
+      if (auto *CI = dyn_cast<CastInst>(R)) {
+        if (NewInsts.find(CI->getOperand(0)) == NewInsts.end()) {
+          RList.push_back(R);
+          RList.push_back(CI->getOperand(0));
+          continue;
+        }
+        // This was a noop, so we don't need to create a new instruction.
+        NewInsts[CI] = NewInsts[CI->getOperand(0)];
+        continue;
+      }
+      if (auto *GEP = dyn_cast<GEPOperator>(R)) {
+        if (NewInsts.find(GEP->getOperand(0)) == NewInsts.end()) {
+          RList.push_back(R);
+          RList.push_back(GEP->getOperand(0));
+          continue;
+        }
+        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;
+      }
+      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 (dyn_cast<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.
+std::pair<Value *, Value *> GetAsConstantIndexedAddress(Value *V,
+                                                        const DataLayout &DL) {
+  Type *IndexType =
+      IntegerType::get((static_cast<Instruction *>(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 (IntToPtrInst *CI = dyn_cast<IntToPtrInst>(V)) {
+      if (DL.getPointerTypeSizeInBits(CI->getType()) !=
+          CI->getOperand(0)->getType()->getScalarSizeInBits())
+        break;
+      V = CI->getOperand(0);
+      continue;
+    }
+    if (PtrToIntInst *CI = dyn_cast<PtrToIntInst>(V)) {
+      if (CI->getType()->getScalarSizeInBits() !=
+          DL.getPointerTypeSizeInBits(CI->getOperand(0)->getType()))
+        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.
+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.
+  SmallPtrSet<Value *, 100> Nodes;
+
+  if (!CanRewriteAsOffsetGEP(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 = RewriteAsOffsetGEP(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.
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
+}
+