[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

571

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.

577

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.

600

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

603

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

557

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.)

563

You can combine these two tests into one.

568

Add a comment about why 2 is the magic number.

571

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,

577

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

586

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.

595

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

[sanjoy]

lib/CodeGen/CodeGenPrepare.cpp

571

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

571

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

310

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)

313

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

566

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

590

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

596

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

610

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

617

Indentation! Are you using tabs?

617

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.

620

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

624

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

626

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

310

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?

313

Removed.

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

590

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

596

Um, yeah.

610

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

617

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?

620

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

624

Okay, fixed.

626

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

310

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.

313

Replacing instructions does not modify the cached dominator tree analysis.

617

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

626

That is the constant tension. :)

[reames]

lib/CodeGen/CodeGenPrepare.cpp

310

Whitespace again.

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

543

llvm style is computeBase...

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

555

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

596

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

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

598

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

616

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

continue;

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

618

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.

625

I'd suggest casting once on the previous line.

626

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

676

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

543

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.

596

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

618

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.

626

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?

676

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

617

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

24

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:
   CallSiteTy getCallSite() {
     return StatepointCS;
   }
 
   /// Return the value actually being called or invoked.
   ValueTy *actualCallee() {
     return StatepointCS.getArgument(0);
   }
+  /// Return the value actually being called or invoked.
+  Value *getArgOperand(int N) {
+    return StatepointCS.getArgument(N);
+  }
+
   /// Number of arguments to be passed to the actual callee.
   int numCallArgs() {
     return cast<ConstantInt>(StatepointCS.getArgument(1))->getZExtValue();
   }
   /// Number of additional arguments excluding those intended
   /// for garbage collection.
   int numTotalVMSArgs() {
     return cast<ConstantInt>(StatepointCS.getArgument(3 + numCallArgs()))->getZExtValue();
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."));
 
void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<TargetTransformInfo>();
     }
 
   private:
     bool EliminateFallThrough(Function &F);
     bool EliminateMostlyEmptyBlocks(Function &F);
     bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
     void EliminateMostlyEmptyBlock(BasicBlock *BB);
+    bool SimplifyOffsetableRelocate(Instruction &I);
     bool OptimizeBlock(BasicBlock &BB, bool& ModifiedDT);
     bool OptimizeInst(Instruction *I, bool& ModifiedDT);
     bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy);
     bool OptimizeInlineAsmInst(CallInst *CS);
     bool OptimizeCallInst(CallInst *CI, bool& ModifiedDT);
     bool MoveExtToFormExtLoad(Instruction *&I);
     bool OptimizeExtUses(Instruction *I);
     bool OptimizeSelectInst(SelectInst *SI);
if (!DisableBranchOpts) {
     if (EverMadeChange || MadeChange)
       MadeChange |= EliminateFallThrough(F);
 
     if (MadeChange)
       ModifiedDT = true;
     EverMadeChange |= MadeChange;
   }
 
+  if (!DisableGCOpts) {
+    bool MadeChange = false;
+    for (BasicBlock &BB : F)
+      for (Instruction &I : BB)
+  if (isStatepoint(I))
+    MadeChange |= SimplifyOffsetableRelocate(I);
+
+    if (MadeChange)
+      ModifiedDT = true;
+    EverMadeChange |= MadeChange;
+  }
+
   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");
 }
 
+// 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;
+  // 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 *> RelocateMap;
+  DenseMap<IntrinsicInst *, SmallVector<IntrinsicInst *, 2>> RelocateMasterMap;
+  for (auto &U : AllRelocateCalls) {
+    GCRelocateOperands ThisRelocate(U);
+    IntrinsicInst *I = dyn_cast<IntrinsicInst>(U);
+    auto K = std::make_pair(ThisRelocate.basePtrIndex(),
+          ThisRelocate.derivedPtrIndex());
+    RelocateMap.insert(std::make_pair(K, I));
+  }
+  for (auto &Item: RelocateMap) {
+    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 = RelocateMap[BaseKey];
+    if (!Base)
+      // No Base relocation we can offset from
+      continue;
+    auto NewVal = RelocateMasterMap[Base];
+    RelocateMasterMap.erase(Base);
+    NewVal.insert(NewVal.end(), I);
+    RelocateMasterMap.insert(std::make_pair(Base, NewVal));
+  }
+
+  if (RelocateMasterMap.empty())
+    // The master call is not relocating the base object: if we don't have a
+    // handle on the relocated base object, how can we gep to get the relocated
+    // derived object? We could probably do some computation of offsets between
+    // derived objects, but that's out of scope for now.
+    return false;
+  for (auto &Item : RelocateMasterMap) {
+    IntrinsicInst *GEPBase = Item.first;
+    GCRelocateOperands MasterRelocate(GEPBase);
+    for (auto &Target : Item.second) {
+      GCRelocateOperands ThisRelocate(Target);
+      if (ThisRelocate.basePtrIndex() != MasterRelocate.basePtrIndex() ||
+    ThisRelocate.basePtrIndex() == ThisRelocate.derivedPtrIndex()) {
+  // Not relocating a derived object with the original base object OR a
+  // duplicate relocate call. TODO: coalesce duplicates.
+  continue;
+      }
+      Value *Base = ThisRelocate.basePtr();
+      Instruction *Derived = dyn_cast<Instruction>(ThisRelocate.derivedPtr());
+      if (Derived && Derived->getOpcode() == Instruction::GetElementPtr &&
+    Derived->getOperand(0) == Base) {
+  // TODO: what if the offset is a vector?
+  const int Offset = dyn_cast<ConstantInt>(Derived->getOperand(1))->getSExtValue();
+
+  // Create a Builder and replace the target callsite with a gep
+  IRBuilder<> Builder(Target);
+  Builder.SetCurrentDebugLocation(Target->getDebugLoc());
+  Value *Repl = Builder.CreateInBoundsGEP(GEPBase, Builder.getInt32(Offset));
+  Repl->takeName(Target);
+  Target->replaceAllUsesWith(Repl);
+  Target->eraseFromParent();
+
+  MadeChange = true;
+      }
+    }
+  }
+  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;
if (!InsertedCast) {
       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
       InsertedCast =
         CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
                          InsertPt);
       MadeChange = true;
     }
 
     // Replace a use of the cast with a use of the new cast.
     TheUse = InsertedCast;
     ++NumCastUses;
   }
 
   // If we removed all uses, nuke the cast.
   if (CI->use_empty()) {
     CI->eraseFromParent();
     MadeChange = true;
   }

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 inbounds i32* %base, i32 15
+; CHECK: getelementptr inbounds i32* %base-new, i32 15
+entry:
+       %ptr = getelementptr inbounds 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 inbounds i32* %base, i32 15
+; CHECK: getelementptr inbounds i32* %base, i32 12
+; CHECK: getelementptr inbounds i32* %base-new, i32 15
+; CHECK: getelementptr inbounds i32* %base-new, i32 12
+entry:
+       %ptr = getelementptr inbounds i32* %base, i32 15
+       %ptr2 = getelementptr inbounds 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 inbounds i32* %base, i32 15
+; CHECK: getelementptr inbounds i32* %base-new, i32 15
+entry:
+       %ptr = getelementptr inbounds 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
+}
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_i1f(i1 ()*, i32, i32, ...)
+declare i32* @llvm.experimental.gc.relocate.p0i32(i32, i32, i32)