[GC] CodeGenPrep transform: simplify offsetable relocate

[artagnon]

Summary

The transform is somewhat involved, but the basic idea is simple: find
derived pointers that have been offset from the base pointer using gep
and replace the relocate of the derived pointer with a gep to the
relocated base pointer (with the same offset).

[sanjoy]

Small nits inline.

lib/CodeGen/CodeGenPrepare.cpp

570

This seems limiting, but correct; and a strict improvement over what we have. We could easily have a DenseMap<CallInst *, CallInst *> that we build in a first pass that maps derived gc relocates to base gc relocates; and write the rest of the algorithm in terms of that.

576

Don't use dyn_cast<> unless you want to check if the cast succeeded or not. I think a cast<> is more appropriate here. Same applies to some later calls to dyn_cast.

599

You've assumed that the gep index is a constant int here. Also, how about geps with multiple index operands? And vector geps?

602

This can be IRBuilder<> Builder(II) I think.

[reames]

Lots of cleanup (both style and correctness) needed, but I like the direction. Please revise.

lib/CodeGen/CodeGenPrepare.cpp

556

First, thank you for working on this!

Second, I'm not entirely sure this is the right place for this. It's possible that having this in InstCombine (alternatively or possible also) might open up IR level optimizations based on comparisons of relocated pointers. Thoughts? (Also, this is not a reason to hold your current patch.)

562

You can combine these two tests into one.

567

Add a comment about why 2 is the magic number.

570

Er, maybe I'm misreading Sanjoy's comment, but I think his first sentence is wrong. There is no guarantee that the first gc.relocate encountered is a base relocation,

576

Take a look at Statepoint.h for useful utility routines here.

585

Organizing this as visiting each of the uses of a statepoint, and then visiting each statepoint individually would make this strictly stronger. Also, vastly preferred from a readability perspective.

594

Not yet. But if you wanted to write an InstCombine, I'd be happy to review it...

[sanjoy]

lib/CodeGen/CodeGenPrepare.cpp

570

There is no guarantee that the first gc.relocate encountered is a base relocation,

I agree. What I meant was that if the first gc.relocate is not a base relocation, then the worst case scenario is that we will miss the optimization, because that fact is checked later.

[artagnon]

Thanks for the quick reviews, sanjoy and reames!

This is the second cut. It doesn't address all the problems, but I
thought it's enough progress to show. I'll defer issues like where to
put this functionality until the patch is in good shape.

Let me know if this is not moving in the right direction.

[artagnon]

Oh, oops: I just realized that a User of a statepoint may be a gc.result: I'll adjust that in the next iteration.

lib/CodeGen/CodeGenPrepare.cpp

570

Is DenseMap<InstrinsicInst *, SmallVector<User *, 2>> more like what we want?

[artagnon]

Revision 3. I implemented a generalized algorithm that doesn't
restrict base relocation being the first one. However, insertion is
now a challenge: the out-of-order test fails. Hopefully, I should have
revision 4 by afternoon tomorrow with everything working; we can then
discuss more high-level questions.

[artagnon]

(Hopefully) final revision. Feedback necessary to proceed.

The .insertAfter was a bit tricky, but I figured it out in the
end. Any number of gep arguments should work now, but is there a way
to call gc.relocate such that it returns a vector or struct?

[reames]

In D6883#107112, @artagnon wrote:

Any number of gep arguments should work now, but is there a way
to call gc.relocate such that it returns a vector or struct?

Not that's been tried or tested yet. Patches welcome and it looks like you already started working on that?

[reames]

Much improved and almost there. Lots of comments, one bug.

FYI, readability wise I had some trouble following the code. Once you break it up, I might spot more things.

lib/CodeGen/CodeGenPrepare.cpp

311

You've got a whitespace problem here. Please fix indentation.

Also, you may be invalidating the iterator you're using here. I'd strongly recommend collecting the statepoints into a SmallVector than processing them. (i.e. two pass)

314

These changes should change the dom tree? Why is this needed?

565

I'd suggest using whitespace (blank lines) to break up the logic junks. You might also want to split out a few static helpers.

589

Your comment here confuses me. I think you mean that you'd have to insert the base relocate and then gep off that?

595

Can't this become:
RelocateMasterMap[Base].push_back()

609

Shouldn't the first part of this be impossible and thus an assert?

616

Indentation! Are you using tabs?

616

Early continue please, or if (auto Derived = ...) at least.

You need to break up this function for readability. If you want specific suggestions, ask, but any reasonable division should do.

619

I'm not sure doing this for *any* gep is a good idea. I'd suggest starting with a small constant offsets only.

623

InBounds is wrong. out of bounds geps for relocates are explicitly legal.

625

p.s. By this point in the code, I've completely lost track of what Target and Repl refer to. You need better variable names and to break this function up.

[artagnon]

Thanks for the detailed review! Expect the next iteration shortly.

lib/CodeGen/CodeGenPrepare.cpp

311

Whitespace: Nobody is maintaining the Emacs modes in-tree, so I'm using my own. I forgot about indent-tabs-mode.

SmallVector done. Why will the iterator get invalidated though? I'm not modifying the instruction in SimplifyOffsetableRelocate, am I?

314

Removed.

I thought I needed this because the dominator tree is changing (when we reorder the base relocate to come before the derived relocate)?

589

That's a TODO then: spitting out a base relocate and gep'ing off that when there are enough derived relocate calls.

595

Um, yeah.

609

Cruft left from my previous iterations. Converted into assert now.

616

Not sure what you mean: you want a if (!Derived) continue; so the user doesn't have to read till the end of the block to figure out that it's continuing?

619

I've defined "small" as 20: so if there ConstantInt offsets, all less than 20, then gep.

623

Okay, fixed.

625

If my variable names are too long, I hit the 80-column limit; If they're too short, they aren't descriptive enough :|

I'll figure something out.

[artagnon]

In response to reames's review. Looks much better with body split up
into functions. Everything seems to work as expected.

[reames]

Response to comments, not yet looking at new version.

lib/CodeGen/CodeGenPrepare.cpp

311

I did say *may*. After reading through your code, it was actually fine, but for clarity, I might do the two pass anyways. Your choice.

314

Replacing instructions does not modify the cached dominator tree analysis.

616

Less "read till the end" and more "not have to keep track of another nesting level"

625

That is the constant tension. :)

[reames]

lib/CodeGen/CodeGenPrepare.cpp

311

Whitespace again.

Do us both a favor and run this diff through clang-format.

542

llvm style is computeBase...

Make the param SmallVectorImpl so that it's size independent.

554

This should be a cast since it's never expected to fail.

595

I think GEPBase might be more clearly named "RelocatedBase".

Also, "affect" is a slightly odd verb. Possibly: SimplifyOneRelocate?

597

Please make MadeChange a normal return value rather than return by reference.

615

I might write this as:
if (!Derived || Derived->getPointerOperand() != Base)

continue;

But this is minor. I'll defer to your preference.

617

To more clearly seperate the legality and profitability, I might write this as:
get gep indices
visit gep indices, checking for constants

Your current version might be slightly faster, but it's IMO less clear.

Minor. I'll defer to your preference.

624

I'd suggest casting once on the previous line.

625

I'm confused by the insertion placement games. Why isn't inserting the new GEP right after the relocation you're replacing okay?

675

Giving names to Item.first and Item.second would make this code more clear. Temporary variables could be used. Creating a helper struct rather than a pair would also be fine.

[artagnon]

Expect a new iteration immediately.

lib/CodeGen/CodeGenPrepare.cpp

542

I see static bool SinkCast, static bool OptimizeNoopCopyExpression, static bool OptimizeCmpExpression, but I suppose it's good to follow the documented convention when writing new functions? simplifyOffsetableRelocate it is.

Note: I can't do SmallVectorImpl inside the DenseMap.

595

SimplifyOneRelocate is misleading because we're simplifying multiple derived-pointer relocates corresponding to the same base-pointer relocate. Perhaps SimplifyRelocatesOffABase?

617

Get - GEP - Small - ConstantInteger - OffsetVector. I thought the name was clever and clear; my preference is not to change it.

Also, I found a bug: it shouldn't return if it couldn't find a small constant-integer offset-vector; it should continue, so that other derived pointer relocations get a chance.

625

Ha, this is fun. Consider:

%ptr = getelementptr i32* %base, i32 15
%tok = call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, i32* %base, i32* %ptr)
%ptr-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
%base-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 4)
%ret = load i32* %ptr-new

Here, if I replace the %ptr-new line with a gep, against whom am I gep'ing? %base-new ofcourse, but that's on the next line! The problem is therefore to reorder instructions so that the new instruction comes after %base-new, no matter what the case.

Makes sense?

675

Hm? It's a pair because that's what you get when iterating over a DenseMap. I don't want to create new variables, so I've written comments about what Item.first and Item.second are, as a compromise.

[artagnon]

Address reames review. Most visible changes:

1. Start function names with a lowercase letter.
2. Use SmallVectorImpl in arguments, where possible.
3. Run the thing through git-clang-format!
4. Change some function and variable names.

[reames]

LGTM. I assume you want me to commit on your behalf?

lib/CodeGen/CodeGenPrepare.cpp

616

What's here is functional, and LGTM for submission.

As a *separate* change, you could clarify the insertion logic slightly if you wanted to. I'd suggest either:
BasicBlock::iterator next(BaseRelocate);
while( isGCRelocate(*next)) next++;
IRBuilder<> Builder(&*next);

OR

find the last relocate in the statepoint sequence once, then pass that in as the insert point for all relocates you visit.

Either makes it lot more clear what's going on.

test/Transforms/CodeGenPrepare/statepoint-relocate.ll

23

You might want to add a CHECK: gc.statepoint in between to make the grouping of GEPs more clear. Entirely optional.

[artagnon]

Thanks; I pushed it immediately because I had branches dependent on this. I'll get back to improving this soon'ish.

include/llvm/IR/Statepoint.h

public:
 
   /// The statepoint with which this gc.relocate is associated.
   const Instruction *statepoint() {
     return cast<Instruction>(RelocateCS.getArgument(0));
   }
   /// The index into the associate statepoint's argument list
   /// which contains the base pointer of the pointer whose
   /// relocation this gc.relocate describes.
-  int basePtrIndex() {
+  unsigned basePtrIndex() {
     return cast<ConstantInt>(RelocateCS.getArgument(1))->getZExtValue();
   }
   /// The index into the associate statepoint's argument list which
   /// contains the pointer whose relocation this gc.relocate describes.
-  int derivedPtrIndex() {
+  unsigned derivedPtrIndex() {
     return cast<ConstantInt>(RelocateCS.getArgument(2))->getZExtValue();
   }
   Value *basePtr() {
     ImmutableCallSite CS(statepoint());
     return *(CS.arg_begin() + basePtrIndex());
   }
   Value *derivedPtr() {
     ImmutableCallSite CS(statepoint());
     return *(CS.arg_begin() + derivedPtrIndex());
   }
 };
 }
 #endif

lib/CodeGen/CodeGenPrepare.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Statepoint.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetLibraryInfo.h"
 #include "llvm/Target/TargetLowering.h"

 STATISTIC(NumSelectsExpanded, "Number of selects turned into branches");
 STATISTIC(NumAndCmpsMoved, "Number of and/cmp's pushed into branches");
 STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed");
 
 static cl::opt<bool> DisableBranchOpts(
   "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
   cl::desc("Disable branch optimizations in CodeGenPrepare"));
 
+static cl::opt<bool>
+    DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false),
+                  cl::desc("Disable GC optimizations in CodeGenPrepare"));
+
 static cl::opt<bool> DisableSelectToBranch(
   "disable-cgp-select2branch", cl::Hidden, cl::init(false),
   cl::desc("Disable select to branch conversion."));
 
 static cl::opt<bool> AddrSinkUsingGEPs(
   "addr-sink-using-gep", cl::Hidden, cl::init(false),
   cl::desc("Address sinking in CGP using GEPs."));
 
private:
     bool DupRetToEnableTailCallOpts(BasicBlock *BB);
     bool PlaceDbgValues(Function &F);
     bool sinkAndCmp(Function &F);
     bool ExtLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI,
                         Instruction *&Inst,
                         const SmallVectorImpl<Instruction *> &Exts,
                         unsigned CreatedInst);
     bool splitBranchCondition(Function &F);
+    bool simplifyOffsetableRelocate(Instruction &I);
   };
 }
 
 char CodeGenPrepare::ID = 0;
 INITIALIZE_TM_PASS(CodeGenPrepare, "codegenprepare",
                    "Optimize for code generation", false, false)
 
 FunctionPass *llvm::createCodeGenPreparePass(const TargetMachine *TM) {
bool CodeGenPrepare::runOnFunction(Function &F) {
 
   bool MadeChange = true;
   while (MadeChange) {
     MadeChange = false;
     for (Function::iterator I = F.begin(); I != F.end(); ) {
       BasicBlock *BB = I++;
       bool ModifiedDTOnIteration = false;
       MadeChange |= OptimizeBlock(*BB, ModifiedDTOnIteration);
-      
       // Restart BB iteration if the dominator tree of the Function was changed
       ModifiedDT |= ModifiedDTOnIteration;
       if (ModifiedDTOnIteration)
         break;
     }
     EverMadeChange |= MadeChange;
   }
 
if (!DisableBranchOpts) {
     if (EverMadeChange || MadeChange)
       MadeChange |= EliminateFallThrough(F);
 
     if (MadeChange)
       ModifiedDT = true;
     EverMadeChange |= MadeChange;
   }
 
+  if (!DisableGCOpts) {
+    SmallVector<Instruction *, 2> Statepoints;
+    for (BasicBlock &BB : F)
+      for (Instruction &I : BB)
+        if (isStatepoint(I))
+          Statepoints.push_back(&I);
+    for (auto &I : Statepoints)
+      EverMadeChange |= simplifyOffsetableRelocate(*I);
+  }
+
   if (ModifiedDT && DT)
     DT->recalculate(F);
 
   return EverMadeChange;
 }
 
 /// EliminateFallThrough - Merge basic blocks which are connected
 /// by a single edge, where one of the basic blocks has a single successor
if (DT && !ModifiedDT) {
     DT->eraseNode(BB);
   }
   BB->eraseFromParent();
   ++NumBlocksElim;
 
   DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
 }
 
+// Computes a map of base pointer relocation instructions to corresponding
+// derived pointer relocation instructions given a vector of all relocate calls
+static void computeBaseDerivedRelocateMap(
+    const SmallVectorImpl<User *> &AllRelocateCalls,
+    DenseMap<IntrinsicInst *, SmallVector<IntrinsicInst *, 2>> &
+        RelocateInstMap) {
+  // Collect information in two maps: one primarily for locating the base object
+  // while filling the second map; the second map is the final structure holding
+  // a mapping between Base and corresponding Derived relocate calls
+  DenseMap<std::pair<unsigned, unsigned>, IntrinsicInst *> RelocateIdxMap;
+  for (auto &U : AllRelocateCalls) {
+    GCRelocateOperands ThisRelocate(U);
+    IntrinsicInst *I = cast<IntrinsicInst>(U);
+    auto K = std::make_pair(ThisRelocate.basePtrIndex(),
+                            ThisRelocate.derivedPtrIndex());
+    RelocateIdxMap.insert(std::make_pair(K, I));
+  }
+  for (auto &Item : RelocateIdxMap) {
+    std::pair<unsigned, unsigned> Key = Item.first;
+    if (Key.first == Key.second)
+      // Base relocation: nothing to insert
+      continue;
+
+    IntrinsicInst *I = Item.second;
+    auto BaseKey = std::make_pair(Key.first, Key.first);
+    IntrinsicInst *Base = RelocateIdxMap[BaseKey];
+    if (!Base)
+      // TODO: We might want to insert a new base object relocate and gep off
+      // that, if there are enough derived object relocates.
+      continue;
+    RelocateInstMap[Base].push_back(I);
+  }
+}
+
+// Accepts a GEP and extracts the operands into a vector provided they're all
+// small integer constants
+static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP,
+                                          SmallVectorImpl<Value *> &OffsetV) {
+  for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
+    // Only accept small constant integer operands
+    auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
+    if (!Op || Op->getZExtValue() > 20)
+      return false;
+  }
+
+  for (unsigned i = 1; i < GEP->getNumOperands(); i++)
+    OffsetV.push_back(GEP->getOperand(i));
+  return true;
+}
+
+// Takes a RelocatedBase (base pointer relocation instruction) and Targets to
+// replace, computes a replacement, and affects it.
+static bool
+simplifyRelocatesOffABase(IntrinsicInst *RelocatedBase,
+                          const SmallVectorImpl<IntrinsicInst *> &Targets) {
+  bool MadeChange = false;
+  for (auto &ToReplace : Targets) {
+    GCRelocateOperands MasterRelocate(RelocatedBase);
+    GCRelocateOperands ThisRelocate(ToReplace);
+
+    assert(ThisRelocate.basePtrIndex() == MasterRelocate.basePtrIndex() &&
+           "Not relocating a derived object of the original base object");
+    if (ThisRelocate.basePtrIndex() == ThisRelocate.derivedPtrIndex()) {
+      // A duplicate relocate call. TODO: coalesce duplicates.
+      continue;
+    }
+
+    Value *Base = ThisRelocate.basePtr();
+    auto Derived = dyn_cast<GetElementPtrInst>(ThisRelocate.derivedPtr());
+    if (!Derived || Derived->getPointerOperand() != Base)
+      continue;
+
+    SmallVector<Value *, 2> OffsetV;
+    if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV))
+      continue;
+
+    // Create a Builder and replace the target callsite with a gep
+    IRBuilder<> Builder(ToReplace);
+    Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
+    Value *Replacement =
+        Builder.CreateGEP(RelocatedBase, makeArrayRef(OffsetV));
+    Instruction *ReplacementInst = cast<Instruction>(Replacement);
+    ReplacementInst->removeFromParent();
+    ReplacementInst->insertAfter(RelocatedBase);
+    Replacement->takeName(ToReplace);
+    ToReplace->replaceAllUsesWith(Replacement);
+    ToReplace->eraseFromParent();
+
+    MadeChange = true;
+  }
+  return MadeChange;
+}
+
+// Turns this:
+//
+// %base = ...
+// %ptr = gep %base + 15
+// %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
+// %base' = relocate(%tok, i32 4, i32 4)
+// %ptr' = relocate(%tok, i32 4, i32 5)
+// %val = load %ptr'
+//
+// into this:
+//
+// %base = ...
+// %ptr = gep %base + 15
+// %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
+// %base' = gc.relocate(%tok, i32 4, i32 4)
+// %ptr' = gep %base' + 15
+// %val = load %ptr'
+bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) {
+  bool MadeChange = false;
+  SmallVector<User *, 2> AllRelocateCalls;
+
+  for (auto *U : I.users())
+    if (isGCRelocate(dyn_cast<Instruction>(U)))
+      // Collect all the relocate calls associated with a statepoint
+      AllRelocateCalls.push_back(U);
+
+  // We need atleast one base pointer relocation + one derived pointer
+  // relocation to mangle
+  if (AllRelocateCalls.size() < 2)
+    return false;
+
+  // RelocateInstMap is a mapping from the base relocate instruction to the
+  // corresponding derived relocate instructions
+  DenseMap<IntrinsicInst *, SmallVector<IntrinsicInst *, 2>> RelocateInstMap;
+  computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap);
+  if (RelocateInstMap.empty())
+    return false;
+
+  for (auto &Item : RelocateInstMap)
+    // Item.first is the RelocatedBase to offset against
+    // Item.second is the vector of Targets to replace
+    MadeChange = simplifyRelocatesOffABase(Item.first, Item.second);
+  return MadeChange;
+}
+
 /// SinkCast - Sink the specified cast instruction into its user blocks
 static bool SinkCast(CastInst *CI) {
   BasicBlock *DefBB = CI->getParent();
 
   /// InsertedCasts - Only insert a cast in each block once.
   DenseMap<BasicBlock*, CastInst*> InsertedCasts;
 
   bool MadeChange = false;

test/Transforms/CodeGenPrepare/statepoint-relocate.ll

+; RUN: opt -codegenprepare -S < %s | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+declare zeroext i1 @return_i1()
+
+define i32 @test_sor_basic(i32* %base) {
+; CHECK: getelementptr i32* %base, i32 15
+; CHECK: getelementptr i32* %base-new, i32 15
+entry:
+       %ptr = getelementptr i32* %base, i32 15
+       %tok = call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, i32* %base, i32* %ptr)
+       %base-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 4)
+       %ptr-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
+       %ret = load i32* %ptr-new
+       ret i32 %ret
+}
+
+define i32 @test_sor_two_derived(i32* %base) {
+; CHECK: getelementptr i32* %base, i32 15
+; CHECK: getelementptr i32* %base, i32 12
+; CHECK: getelementptr i32* %base-new, i32 15
+; CHECK: getelementptr i32* %base-new, i32 12
+entry:
+       %ptr = getelementptr i32* %base, i32 15
+       %ptr2 = getelementptr i32* %base, i32 12
+       %tok = call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, i32* %base, i32* %ptr, i32* %ptr2)
+       %base-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 4)
+       %ptr-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
+       %ptr2-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 6)
+       %ret = load i32* %ptr-new
+       ret i32 %ret
+}
+
+define i32 @test_sor_ooo(i32* %base) {
+; CHECK: getelementptr i32* %base, i32 15
+; CHECK: getelementptr i32* %base-new, i32 15
+entry:
+       %ptr = getelementptr i32* %base, i32 15
+       %tok = call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, i32* %base, i32* %ptr)
+       %ptr-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
+       %base-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 4)
+       %ret = load i32* %ptr-new
+       ret i32 %ret
+}
+
+define i32 @test_sor_gep_smallint([3 x i32]* %base) {
+; CHECK: getelementptr [3 x i32]* %base, i32 0, i32 2
+; CHECK: getelementptr [3 x i32]* %base-new, i32 0, i32 2
+entry:
+       %ptr = getelementptr [3 x i32]* %base, i32 0, i32 2
+       %tok = call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, [3 x i32]* %base, i32* %ptr)
+       %base-new = call [3 x i32]* @llvm.experimental.gc.relocate.p0a3i32(i32 %tok, i32 4, i32 4)
+       %ptr-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
+       %ret = load i32* %ptr-new
+       ret i32 %ret
+}
+
+define i32 @test_sor_gep_largeint([3 x i32]* %base) {
+; CHECK: getelementptr [3 x i32]* %base, i32 0, i32 21
+; CHECK-NOT: getelementptr [3 x i32]* %base-new, i32 0, i32 21
+entry:
+       %ptr = getelementptr [3 x i32]* %base, i32 0, i32 21
+       %tok = call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, [3 x i32]* %base, i32* %ptr)
+       %base-new = call [3 x i32]* @llvm.experimental.gc.relocate.p0a3i32(i32 %tok, i32 4, i32 4)
+       %ptr-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
+       %ret = load i32* %ptr-new
+       ret i32 %ret
+}
+
+define i32 @test_sor_noop(i32* %base) {
+; CHECK: getelementptr i32* %base, i32 15
+; CHECK: call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
+; CHECK: call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 6)
+entry:
+       %ptr = getelementptr i32* %base, i32 15
+       %ptr2 = getelementptr i32* %base, i32 12
+       %tok = call i32 (i1 ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()* @return_i1, i32 0, i32 0, i32 0, i32* %base, i32* %ptr, i32* %ptr2)
+       %ptr-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 5)
+       %ptr2-new = call i32* @llvm.experimental.gc.relocate.p0i32(i32 %tok, i32 4, i32 6)
+       %ret = load i32* %ptr-new
+       ret i32 %ret
+}
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()*, i32, i32, ...)
+declare i32* @llvm.experimental.gc.relocate.p0i32(i32, i32, i32)
+declare [3 x i32]* @llvm.experimental.gc.relocate.p0a3i32(i32, i32, i32)