Move easily derivable pointers optimization from CodeGenPrepare to RewriteStatepointPass

[igor-laevsky]

Summary

In CodeGen prepare we have optimization which re-creates some derived pointers instead of using gc.relocates for them. I.e if we had following code:

%derived = gep %base, 15
safepoint(base, derived)
%base.rel = gc.relocate(%base)
%derived.rel = gc.relocate(%derived)

It transforms it into:

%derived = gep %base, 15
safepoint(base, derived)
%base.rel = gc.relocate(%base)
%derived.rel = gep %base.rel, 15

This is profitable for pointers which are cheaply computed from their bases.

In this changeset I am moving this optimization from CodeGenPrepare into RewriteSafepointPass. Basic motivation here is that by doing it before gc.relocate insertion we can catch substantially more cases. For example if pointer is located inside a loop with statepoint.

Also I am extending it to happen not only on geps with small constant indices, but on all geps and noop casts.

[reames]

I haven't had a chance to review the newly added bits in RewriteStatepointsForGC, but I want to comment on the CGP parts first. I see no reason to remove this optimization. If a statepoint is generated through a means other than RSForGC, this optimization is valid and useful. Please update your patch to leave this code in CGP.

(If you chose to common the code in some way, that's fine. I don't mean to discourage that.)

[sanjoy]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1418 ↗

(On Diff #25854)

Nit: change this to assert(AllocaMap.count() && "why this should be true!").

1422 ↗

(On Diff #25854)

Unless you have a reason to prefer otherwise, I'd push this invariant of RematerializedValue being an Instruction earlier and

typedef DenseMap<Value *, Instruction *> RematerializedValueMapTy;

1456 ↗

(On Diff #25854)

Variable naming in this function is somewhat haphazard. Do you mind bringing the variable names up to LLVM's coding standards for the functions you touched in a later separate NFC change, (once this change is in)?

1471 ↗

(On Diff #25854)

Most of LLVM consistently avoids bracing small if bodies like these, can you change this to

if (...)
  continue;

here and elsewhere?

1801 ↗

(On Diff #25854)

Nit: should be "successfully"

1842 ↗

(On Diff #25854)

If TTI is non-null, then take a reference instead of a pointer.

1847 ↗

(On Diff #25854)

I'd structure this as:

if (CastInst *CI = ...) {
} else if (GEPInst *GEP = ...) {
} else
  llvm_unreachable("message");

Currently the continue statements are redundant and they make it look like that there is some fallthrough logic that you're trying to avoid, but there isn't.

1850 ↗

(On Diff #25854)

Add a string to the assert on why the condition should be true.

1873 ↗

(On Diff #25854)

What is a situation where this guard will help?

1887 ↗

(On Diff #25854)

If TTI is never null then take TargetTransformInfo & instead.

1893 ↗

(On Diff #25854)

I'd rather you not do this, but instead accumulate the values you're supposed to delete into a SmallVector and batch-delete them after the loop.

If you wish to keep this as it is, please use the SmallVector constructor that takes a begin and end iterator.

1914 ↗

(On Diff #25854)

No need to fix this now, but add a TODO for adjusting the cost when recomputing the derived pointer will let you remove the computation of the unrelocated derived pointer in cases where the only use of the derived pointer was the statepoint.

1934 ↗

(On Diff #25854)

But you may still semantically "promote" a live value that was solely the base pointer for another derived pointer (and had no direct uses after the safepoint) to a pointer that is fundamentally live over the safepoint (has a direct use after the safepoint), right? Will that always work correctly?

1945 ↗

(On Diff #25854)

In debug mode assert that ClonedValue does not use any of the values in ChainToBase except LastValue.

1966 ↗

(On Diff #25854)

Please common out the cast<InvokeInst>(CS.getInstruction()). That way the assert(CS.isInvoke()) also becomes redundant.

[igor-laevsky]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1456 ↗

(On Diff #25854)

Sure

1873 ↗

(On Diff #25854)

In theory TTI functions can return zero cost. In that case it is possible to have very long instruction chain with estimated cost of zero. It does not seems very right. This is purely hypothetical and I don't think it is very likely to happen on practice.

1914 ↗

(On Diff #25854)

Not sure if I am following.

Are you saying about cases when we will be able to remove instruction chain (or part of it) later? I.e it also can happen if there was several intersecting instruction chains we have rematerialized.

1934 ↗

(On Diff #25854)

Yes, it should work. Nowhere in this pass we distinguish pointers which are live "for real" and base pointer which are required to be live because of the derived pointer, but does not have uses of their own.

[sanjoy]

LGTM with comments addressed.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1860 ↗

(On Diff #25854)

I'm not sure that this is the right meaning of IsComplex. Even with variable indices x86 can usually merge the GEP into the load/store. I think IsComplex should be "has more than one non-constant operand".

1873 ↗

(On Diff #25854)

But I'd say in those cases it should be perfectly okay to have a large chain. Otherwise TTI is wrong. :)

Actually, I don't have strong objections to this part, but I think it is more sensible to have this as an optimization to reduce compile time -- in the caller, check if Chain.size() is higher than some threshold (10 is good) and if so bail out of rewriting anything for the given Chain.

In either case, please add a test case that exercises this path.

1914 ↗

(On Diff #25854)

I'm talking about the case where we go from:

%D = GEP %B, 4
; No use of %D before statepoint
(%D2, %B2) = statepoint_and_relocate(%D, %B)

to

%B2 = statepoint_and_relocatt(%B)
%D2 = GEP %B2, 4

Here we have only moved the GEP, but did not copy it, so we did not add any cost to the computation overall.

1934 ↗

(On Diff #25854)

Great! Please add one or two lines explaining this. If you can figure out a way to assert on this then even better.

test/Transforms/RewriteStatepointsForGC/basics.ll

2 ↗

(On Diff #25854)

Very minor: I'd use -spp-rematerialization-threshold=-1 here to make it obvious that you're preventing any rewriting, even zero-cost ones.

test/Transforms/RewriteStatepointsForGC/rematerialize-derived-pointers.ll

12 ↗

(On Diff #25854)

Please add some (2-3) more detailed test cases that check that you've generated the correct GEPs and cast instructions.

[igor-laevsky]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1873 ↗

(On Diff #25854)

I think it's ok for TTI function to return zero - they estimate only runtime cost. But since we are cloning instructions we also need to account compile time for them.

I agree, this threshold fits for the caller better.

llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 //===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Rewrite an existing set of gc.statepoints such that they make potential
 // relocations performed by the garbage collector explicit in the IR.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Pass.h"
 #include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"

 static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden,
                                   cl::init(false));
 static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden,
                                       cl::init(false));
 // Print out the base pointers for debugging
 static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden,
                                        cl::init(false));
 
+// Cost threshold measuring when it is profitable to rematerialize value instead
+// of relocating it
+static cl::opt<unsigned>
+RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden,
+                           cl::init(6));
+
 #ifdef XDEBUG
 static bool ClobberNonLive = true;
 #else
 static bool ClobberNonLive = false;
 #endif
 static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
                                                   cl::location(ClobberNonLive),
                                                   cl::Hidden);
 
 namespace {
 struct RewriteStatepointsForGC : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
 
   RewriteStatepointsForGC() : FunctionPass(ID) {
     initializeRewriteStatepointsForGCPass(*PassRegistry::getPassRegistry());
   }
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     // We add and rewrite a bunch of instructions, but don't really do much
     // else.  We could in theory preserve a lot more analyses here.
     AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<TargetTransformInfoWrapperPass>();
   }
 };
 } // namespace
 
 char RewriteStatepointsForGC::ID = 0;
 
 FunctionPass *llvm::createRewriteStatepointsForGCPass() {
   return new RewriteStatepointsForGC();

 // In the actual implementation this caches two relations:
 // - The base relation itself (i.e. this pointer is based on that one)
 // - The base defining value relation (i.e. before base_phi insertion)
 // Generally, after the execution of a full findBasePointer call, only the
 // base relation will remain.  Internally, we add a mixture of the two
 // types, then update all the second type to the first type
 typedef DenseMap<Value *, Value *> DefiningValueMapTy;
 typedef DenseSet<llvm::Value *> StatepointLiveSetTy;
+typedef DenseMap<Instruction *, Value *> RematerializedValueMapTy;
 
 struct PartiallyConstructedSafepointRecord {
   /// The set of values known to be live accross this safepoint
   StatepointLiveSetTy liveset;
 
   /// Mapping from live pointers to a base-defining-value
   DenseMap<llvm::Value *, llvm::Value *> PointerToBase;
 
   /// The *new* gc.statepoint instruction itself.  This produces the token
   /// that normal path gc.relocates and the gc.result are tied to.
   Instruction *StatepointToken;
 
   /// Instruction to which exceptional gc relocates are attached
   /// Makes it easier to iterate through them during relocationViaAlloca.
   Instruction *UnwindToken;
+
+  /// Record live values we are rematerialized instead of relocating.
+  /// They are not included into 'liveset' field.
+  /// Maps rematerialized copy to it's original value.
+  RematerializedValueMapTy RematerializedValues;
 };
 }
 
 /// Compute the live-in set for every basic block in the function
 static void computeLiveInValues(DominatorTree &DT, Function &F,
                                 GCPtrLivenessData &Data);
 
 /// Given results from the dataflow liveness computation, find the set of live
for (User *U : GCRelocs) {
     Store->insertAfter(cast<Instruction>(CastedRelocatedValue));
 
 #ifndef NDEBUG
     VisitedLiveValues.insert(OriginalValue);
 #endif
   }
 }
 
+// Helper function for the "relocationViaAlloca". Similar to the
+// "insertRelocationStores" but works for rematerialized values.
+static void
+insertRematerializationStores(
+  RematerializedValueMapTy RematerializedValues,
+  DenseMap<Value *, Value *> &AllocaMap,
+  DenseSet<Value *> &VisitedLiveValues) {
+
+  for (auto RematerializedValuePair: RematerializedValues) {
+    Instruction *RematerializedValue = RematerializedValuePair.first;
+    Value *OriginalValue = RematerializedValuePair.second;
+
+    assert(AllocaMap.count(OriginalValue) &&
+           "Can not find alloca for rematerialized value");
+    Value *Alloca = AllocaMap[OriginalValue];
+
+    StoreInst *Store = new StoreInst(RematerializedValue, Alloca);
+    Store->insertAfter(RematerializedValue);
+
+#ifndef NDEBUG
+    VisitedLiveValues.insert(OriginalValue);
+#endif
+  }
+}
+
 /// do all the relocation update via allocas and mem2reg
 static void relocationViaAlloca(
     Function &F, DominatorTree &DT, ArrayRef<Value *> live,
     ArrayRef<struct PartiallyConstructedSafepointRecord> records) {
 #ifndef NDEBUG
   // record initial number of (static) allocas; we'll check we have the same
   // number when we get done.
   int InitialAllocaNum = 0;
   for (auto I = F.getEntryBlock().begin(), E = F.getEntryBlock().end(); I != E;
        I++)
     if (isa<AllocaInst>(*I))
       InitialAllocaNum++;
 #endif
 
   // TODO-PERF: change data structures, reserve
   DenseMap<Value *, Value *> allocaMap;
   SmallVector<AllocaInst *, 200> PromotableAllocas;
+  // Used later to chack that we have enough allocas to store all values
+  std::size_t NumRematerializedValues = 0;
   PromotableAllocas.reserve(live.size());
 
+  // Emit alloca for "LiveValue" and record it in "allocaMap" and
+  // "PromotableAllocas"
+  auto emitAllocaFor = [&](Value *LiveValue) {
+    AllocaInst *Alloca = new AllocaInst(LiveValue->getType(), "",
+                                        F.getEntryBlock().getFirstNonPHI());
+    allocaMap[LiveValue] = Alloca;
+    PromotableAllocas.push_back(Alloca);
+  };
+
   // emit alloca for each live gc pointer
   for (unsigned i = 0; i < live.size(); i++) {
-    Value *liveValue = live[i];
-    AllocaInst *alloca = new AllocaInst(liveValue->getType(), "",
-                                        F.getEntryBlock().getFirstNonPHI());
-    allocaMap[liveValue] = alloca;
-    PromotableAllocas.push_back(alloca);
+    emitAllocaFor(live[i]);
+  }
+
+  // emit allocas for rematerialized values
+  for (size_t i = 0; i < records.size(); i++) {
+    const struct PartiallyConstructedSafepointRecord &Info = records[i];
+
+    for (auto RematerializedValuePair: Info.RematerializedValues) {
+      Value *OriginalValue = RematerializedValuePair.second;
+      if (allocaMap.count(OriginalValue) != 0)
+        continue;
+
+      emitAllocaFor(OriginalValue);
+      ++NumRematerializedValues;
+    }
   }
   
   // The next two loops are part of the same conceptual operation.  We need to
   // insert a store to the alloca after the original def and at each
   // redefinition.  We need to insert a load before each use.  These are split
   // into distinct loops for performance reasons.
 
   // update gc pointer after each statepoint
   // either store a relocated value or null (if no relocated value found for
   // this gc pointer and it is not a gc_result)
for (size_t i = 0; i < records.size(); i++) {
 
     // In case if it was invoke statepoint
     // we will insert stores for exceptional path gc relocates.
     if (isa<InvokeInst>(Statepoint)) {
       insertRelocationStores(info.UnwindToken->users(), allocaMap,
                              visitedLiveValues);
     }
 
+    // Do similar thing with rematerialized values
+    insertRematerializationStores(info.RematerializedValues, allocaMap,
+                                  visitedLiveValues);
+
     if (ClobberNonLive) {
       // As a debuging aid, pretend that an unrelocated pointer becomes null at
       // the gc.statepoint.  This will turn some subtle GC problems into
       // slightly easier to debug SEGVs.  Note that on large IR files with
       // lots of gc.statepoints this is extremely costly both memory and time
       // wise.
       SmallVector<AllocaInst *, 64> ToClobber;
       for (auto Pair : allocaMap) {
if (Instruction *inst = dyn_cast<Instruction>(def)) {
         store->insertAfter(inst);
       }
     } else {
       assert(isa<Argument>(def));
       store->insertAfter(cast<Instruction>(alloca));
     }
   }
 
-  assert(PromotableAllocas.size() == live.size() &&
+  assert(PromotableAllocas.size() == live.size() + NumRematerializedValues &&
          "we must have the same allocas with lives");
   if (!PromotableAllocas.empty()) {
     // apply mem2reg to promote alloca to SSA
     PromoteMemToReg(PromotableAllocas, DT);
   }
 
 #ifndef NDEBUG
   for (auto I = F.getEntryBlock().begin(), E = F.getEntryBlock().end(); I != E;
static void splitVectorValues(Instruction *StatepointInst,
 
   // apply mem2reg to promote alloca to SSA
   SmallVector<AllocaInst *, 16> Allocas;
   for (Value *V : ToSplit)
     Allocas.push_back(AllocaMap[V]);
   PromoteMemToReg(Allocas, DT);
 }
 
+// Helper function for the "rematerializeLiveValues". It walks use chain
+// starting from the "CurrentValue" until it meets "BaseValue". Only "simple"
+// values are visited (currently it is GEP's and casts). Returns true if it
+// sucessfully reached "BaseValue" and false otherwise.
+// Fills "ChainToBase" array with all visited values. "BaseValue" is not
+// recorded.
+static bool findRematerializableChainToBasePointer(
+  SmallVectorImpl<Instruction*> &ChainToBase,
+  Value *CurrentValue, Value *BaseValue) {
+
+  // We have found a base value
+  if (CurrentValue == BaseValue) {
+    return true;
+  }
+
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
+    ChainToBase.push_back(GEP);
+    return findRematerializableChainToBasePointer(ChainToBase,
+                                                  GEP->getPointerOperand(),
+                                                  BaseValue);
+  }
+
+  if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
+    Value *Def = CI->stripPointerCasts();
+
+    // This two checks are basically similar. First one is here for the
+    // consistency with findBasePointers logic.
+    assert(!isa<CastInst>(Def) && "not a pointer cast found");
+    if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
+      return false;
+
+    ChainToBase.push_back(CI);
+    return findRematerializableChainToBasePointer(ChainToBase, Def, BaseValue);
+  }
+
+  // Not supported instruction in the chain
+  return false;
+}
+
+// Helper function for the "rematerializeLiveValues". Compute cost of the use
+// chain we are going to rematerialize.
+static unsigned
+chainToBasePointerCost(SmallVectorImpl<Instruction*> &Chain,
+                       TargetTransformInfo &TTI) {
+  unsigned Cost = 0;
+
+  for (Instruction *Instr : Chain) {
+    if (CastInst *CI = dyn_cast<CastInst>(Instr)) {
+      assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
+             "non noop cast is found during rematerialization");
+
+      Type *SrcTy = CI->getOperand(0)->getType();
+      Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy);
+
+    } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) {
+      // Cost of the address calculation
+      Type *ValTy = GEP->getPointerOperandType()->getPointerElementType();
+      Cost += TTI.getAddressComputationCost(ValTy);
+
+      // And cost of the GEP itself
+      // TODO: Use TTI->getGEPCost here (it exists, but appears to be not
+      //       allowed for the external usage)
+      if (!GEP->hasAllConstantIndices())
+        Cost += 2;
+
+    } else {
+      llvm_unreachable("unsupported instruciton type during rematerialization");
+    }
+  }
+
+  return Cost;
+}
+
+// From the statepoint liveset pick values that are cheaper to recompute then to
+// relocate. Remove this values from the liveset, rematerialize them after
+// statepoint and record them in "Info" structure. Note that similar to
+// relocated values we don't do any user adjustments here.
+static void rematerializeLiveValues(CallSite CS,
+                                    PartiallyConstructedSafepointRecord &Info,
+                                    TargetTransformInfo &TTI) {
+  const int ChainLengthThreshold = 10;
+  
+  // Record values we are going to delete from this statepoint live set.
+  // We can not di this in following loop due to iterator invalidation.
+  SmallVector<Value *, 32> LiveValuesToBeDeleted;
+
+  for (Value *LiveValue: Info.liveset) {
+    // For each live pointer find it's defining chain
+    SmallVector<Instruction *, 3> ChainToBase;
+    assert(Info.PointerToBase.find(LiveValue) != Info.PointerToBase.end());
+    bool FoundChain =
+      findRematerializableChainToBasePointer(ChainToBase,
+                                             LiveValue,
+                                             Info.PointerToBase[LiveValue]);
+    // Nothing to do, or chain is too long
+    if (!FoundChain ||
+        ChainToBase.size() == 0 ||
+        ChainToBase.size() > ChainLengthThreshold)
+      continue;
+
+    // Compute cost of this chain
+    unsigned Cost = chainToBasePointerCost(ChainToBase, TTI);
+    // TODO: We can also account for cases when we will be able to remove some
+    //       of the rematerialized values by later optimization passes. I.e if
+    //       we rematerialized several intersecting chains. Or if original values
+    //       don't have any uses besides this statepoint.
+
+    // For invokes we need to rematerialize each chain twice - for normal and
+    // for unwind basic blocks. Model this by multiplying cost by two.
+    if (CS.isInvoke()) {
+      Cost *= 2;
+    }
+    // If it's too expensive - skip it
+    if (Cost >= RematerializationThreshold)
+      continue;
+
+    // Remove value from the live set
+    LiveValuesToBeDeleted.push_back(LiveValue);
+
+    // Clone instructions and record them inside "Info" structure
+
+    // Walk backwards to visit top-most instructions first
+    std::reverse(ChainToBase.begin(), ChainToBase.end());
+
+    // Utility function which clones all instructions from "ChainToBase"
+    // and inserts them before "InsertBefore". Returns rematerialized value
+    // which should be used after statepoint.
+    auto rematerializeChain = [&ChainToBase](Instruction *InsertBefore) {
+      Instruction *LastClonedValue = nullptr;
+      Instruction *LastValue = nullptr;
+      for (Instruction *Instr: ChainToBase) {
+        // Only GEP's and casts are suported as we need to be careful to not
+        // introduce any new uses of pointers not in the liveset.
+        // Note that it's fine to introduce new uses of pointers which were
+        // otherwise not used after this statepoint.
+        assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
+
+        Instruction *ClonedValue = Instr->clone();
+        ClonedValue->insertBefore(InsertBefore);
+        ClonedValue->setName(Instr->getName() + ".remat");
+
+        // If it is not first instruction in the chain then it uses previously
+        // cloned value. We should update it to use cloned value.
+        if (LastClonedValue) {
+          assert(LastValue);
+          ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);
+#ifndef NDEBUG
+          // Assert that cloned instruction does not use any instructions
+          // other than LastClonedValue
+          for (auto OpValue: ClonedValue->operand_values()) {
+            if (isa<Instruction>(OpValue))
+              assert(OpValue == LastClonedValue &&
+                     "unexpected use found in rematerialized value");
+          }
+#endif
+        }
+
+        LastClonedValue = ClonedValue;
+        LastValue = Instr;
+      }
+      assert(LastClonedValue);
+      return LastClonedValue;
+    };
+
+    // Different cases for calls and invokes. For invokes we need to clone
+    // instructions both on normal and unwind path.
+    if (CS.isCall()) {
+      Instruction *InsertBefore = CS.getInstruction()->getNextNode();
+      assert(InsertBefore);
+      Instruction *RematerializedValue = rematerializeChain(InsertBefore);
+      Info.RematerializedValues[RematerializedValue] = LiveValue;
+    } else {
+      InvokeInst *Invoke = cast<InvokeInst>(CS.getInstruction());
+
+      Instruction *NormalInsertBefore =
+          Invoke->getNormalDest()->getFirstInsertionPt();
+      Instruction *UnwindInsertBefore =
+          Invoke->getUnwindDest()->getFirstInsertionPt();
+
+      Instruction *NormalRematerializedValue =
+          rematerializeChain(NormalInsertBefore);
+      Instruction *UnwindRematerializedValue =
+          rematerializeChain(UnwindInsertBefore);
+
+      Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
+      Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
+    }
+  }
+
+  // Remove rematerializaed values from the live set
+  for (auto LiveValue: LiveValuesToBeDeleted) {
+    Info.liveset.erase(LiveValue);
+  }
+}
+
 static bool insertParsePoints(Function &F, DominatorTree &DT, Pass *P,
                               SmallVectorImpl<CallSite> &toUpdate) {
 #ifndef NDEBUG
   // sanity check the input
   std::set<CallSite> uniqued;
   uniqued.insert(toUpdate.begin(), toUpdate.end());
   assert(uniqued.size() == toUpdate.size() && "no duplicates please!");
 
if (PrintBasePointers) {
     }
   }
   for (size_t i = 0; i < holders.size(); i++) {
     holders[i]->eraseFromParent();
     holders[i] = nullptr;
   }
   holders.clear();
 
+  // In order to reduce live set of statepoint we might choose to rematerialize
+  // some values instead of relocating them. This is purelly an optimization and
+  // does not influence correctness.
+  TargetTransformInfo &TTI =
+    P->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+
+  for (size_t i = 0; i < records.size(); i++) { 
+    struct PartiallyConstructedSafepointRecord &info = records[i];
+    CallSite &CS = toUpdate[i];
+
+    rematerializeLiveValues(CS, info, TTI);
+  }
+
   // Now run through and replace the existing statepoints with new ones with
   // the live variables listed.  We do not yet update uses of the values being
   // relocated. We have references to live variables that need to
   // survive to the last iteration of this loop.  (By construction, the
   // previous statepoint can not be a live variable, thus we can and remove
   // the old statepoint calls as we go.)
   for (size_t i = 0; i < records.size(); i++) {
     struct PartiallyConstructedSafepointRecord &info = records[i];

llvm/trunk/test/Transforms/RewriteStatepointsForGC/basics.ll

 ; This is a collection of really basic tests for gc.statepoint rewriting.
-; RUN:  opt %s -rewrite-statepoints-for-gc -S | FileCheck %s
+; RUN:  opt %s -rewrite-statepoints-for-gc -spp-rematerialization-threshold=0 -S | FileCheck %s
 
 declare void @foo()
 
 ; Trivial relocation over a single call
 define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) gc "statepoint-example" {
 ; CHECK-LABEL: @test1
 ; CHECK-LABEL: entry:
 ; CHECK-NEXT: gc.statepoint

 ; CHECK-NEXT: gc.statepoint
 ; CHECK-NOT: %obj.relocated = call coldcc i8 addrspace(1)*
 entry:
   call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @foo, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
   ret i8 addrspace(1)* %obj
 }
 
 declare i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
 No newline at end of file

llvm/trunk/test/Transforms/RewriteStatepointsForGC/liveness-basics.ll

 ; A collection of liveness test cases to ensure we're reporting the
 ; correct live values at statepoints
-; RUN: opt -rewrite-statepoints-for-gc -S < %s | FileCheck %s
+; RUN: opt -rewrite-statepoints-for-gc -spp-rematerialization-threshold=0 -S < %s | FileCheck %s
 
 
 ; Tests to make sure we consider %obj live in both the taken and untaken 
 ; predeccessor of merge.
 define i64 addrspace(1)* @test1(i1 %cmp, i64 addrspace(1)* %obj) gc "statepoint-example" {
 ; CHECK-LABEL: @test1
 entry:
   br i1 %cmp, label %taken, label %untaken

llvm/trunk/test/Transforms/RewriteStatepointsForGC/relocation.ll

-; RUN: opt %s -rewrite-statepoints-for-gc -S 2>&1 | FileCheck %s
+; RUN: opt %s -rewrite-statepoints-for-gc -spp-rematerialization-threshold=0 -S 2>&1 | FileCheck %s
 
 
 declare void @foo()
 declare void @use(...)
 
 define i64 addrspace(1)* @test1(i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2, i1 %condition) gc "statepoint-example" {
 entry:
 ; CHECK-LABEL: @test1

llvm/trunk/test/Transforms/RewriteStatepointsForGC/rematerialize-derived-pointers.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -S 2>&1 | FileCheck %s
+
+declare void @use_obj16(i16 addrspace(1)*)
+declare void @use_obj32(i32 addrspace(1)*)
+declare void @use_obj64(i64 addrspace(1)*)
+declare void @do_safepoint()
+
+define void @"test_gep_const"(i32 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_gep_const
+entry:
+  %ptr = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  ; CHECK: getelementptr i32, i32 addrspace(1)* %base, i32 15
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: %base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %sp, i32 7, i32 7)
+  ; CHECK: bitcast i8 addrspace(1)* %base.relocated to i32 addrspace(1)*
+  ; CHECK: getelementptr i32, i32 addrspace(1)* %base.relocated.casted, i32 15
+  call void @use_obj32(i32 addrspace(1)* %base)
+  call void @use_obj32(i32 addrspace(1)* %ptr)
+  ret void
+}
+
+define void @"test_gep_idx"(i32 addrspace(1)* %base, i32 %idx) gc "statepoint-example" {
+; CHECK-LABEL: test_gep_idx
+entry:
+  %ptr = getelementptr i32, i32 addrspace(1)* %base, i32 %idx
+  ; CHECK: getelementptr
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: %base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %sp, i32 7, i32 7)
+  ; CHECK: %base.relocated.casted = bitcast i8 addrspace(1)* %base.relocated to i32 addrspace(1)*
+  ; CHECK: getelementptr i32, i32 addrspace(1)* %base.relocated.casted, i32 %idx
+  call void @use_obj32(i32 addrspace(1)* %base)
+  call void @use_obj32(i32 addrspace(1)* %ptr)
+  ret void
+}
+
+define void @"test_bitcast"(i32 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_bitcast
+entry:
+  %ptr = bitcast i32 addrspace(1)* %base to i64 addrspace(1)*
+  ; CHECK: bitcast i32 addrspace(1)* %base to i64 addrspace(1)*
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: %base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %sp, i32 7, i32 7)
+  ; CHECK: %base.relocated.casted = bitcast i8 addrspace(1)* %base.relocated to i32 addrspace(1)*
+  ; CHECK: bitcast i32 addrspace(1)* %base.relocated.casted to i64 addrspace(1)*
+  call void @use_obj32(i32 addrspace(1)* %base)
+  call void @use_obj64(i64 addrspace(1)* %ptr)
+  ret void
+}
+
+define void @"test_bitcast_gep"(i32 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_bitcast_gep
+entry:
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  ; CHECK: getelementptr
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep to i64 addrspace(1)*
+  ; CHECK: bitcast
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  ; CHECK: bitcast
+  call void @use_obj32(i32 addrspace(1)* %base)
+  call void @use_obj64(i64 addrspace(1)* %ptr.cast)
+  ret void
+}
+
+define void @"test_intersecting_chains"(i32 addrspace(1)* %base, i32 %idx) gc "statepoint-example" {
+; CHECK-LABEL: test_intersecting_chains
+entry:
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  ; CHECK: getelementptr
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep to i64 addrspace(1)*
+  ; CHECK: bitcast
+  %ptr.cast2 = bitcast i32 addrspace(1)* %ptr.gep to i16 addrspace(1)*
+  ; CHECK: bitcast
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: getelementptr
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  ; CHECK: bitcast
+  call void @use_obj64(i64 addrspace(1)* %ptr.cast)
+  call void @use_obj16(i16 addrspace(1)* %ptr.cast2)
+  ret void
+}
+
+define void @"test_cost_threshold"(i32 addrspace(1)* %base, i32 %idx1, i32 %idx2, i32 %idx3) gc "statepoint-example" {
+; CHECK-LABEL: test_cost_threshold
+entry:
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  ; CHECK: getelementptr
+  %ptr.gep2 = getelementptr i32, i32 addrspace(1)* %ptr.gep, i32 %idx1
+  ; CHECK: getelementptr
+  %ptr.gep3 = getelementptr i32, i32 addrspace(1)* %ptr.gep2, i32 %idx2
+  ; CHECK: getelementptr
+  %ptr.gep4 = getelementptr i32, i32 addrspace(1)* %ptr.gep3, i32 %idx3
+  ; CHECK: getelementptr
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep4 to i64 addrspace(1)*
+  ; CHECK: bitcast
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  call void @use_obj64(i64 addrspace(1)* %ptr.cast)
+  ret void
+}
+
+define void @"test_two_derived"(i32 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_two_derived
+entry:
+  %ptr = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  %ptr2 = getelementptr i32, i32 addrspace(1)* %base, i32 12
+  ; CHECK: getelementptr
+  ; CHECK: getelementptr
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  ; CHECK: getelementptr
+  call void @use_obj32(i32 addrspace(1)* %ptr)
+  call void @use_obj32(i32 addrspace(1)* %ptr2)
+  ret void
+}
+
+define void @"test_gep_smallint_array"([3 x i32] addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_gep_smallint_array
+entry:
+  %ptr = getelementptr [3 x i32], [3 x i32] addrspace(1)* %base, i32 0, i32 2
+  ; CHECK: getelementptr
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  call void @use_obj32(i32 addrspace(1)* %ptr)
+  ret void
+}
+
+declare i32 @fake_personality_function()
+
+define void @"test_invoke"(i32 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_invoke
+entry:
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  ; CHECK: getelementptr
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep to i64 addrspace(1)*
+  ; CHECK: bitcast
+  %ptr.cast2 = bitcast i32 addrspace(1)* %ptr.gep to i16 addrspace(1)*
+  ; CHECK: bitcast
+  %sp = invoke i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+                to label %normal unwind label %exception
+
+normal:
+  ; CHECK-LABEL: normal:
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  ; CHECK: bitcast
+  call void @use_obj64(i64 addrspace(1)* %ptr.cast)
+  call void @use_obj16(i16 addrspace(1)* %ptr.cast2)
+  ret void
+
+exception:
+  ; CHECK-LABEL: exception:
+  %landing_pad4 = landingpad { i8*, i32 } personality i32 ()* @fake_personality_function
+          cleanup
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  ; CHECK: bitcast
+  call void @use_obj64(i64 addrspace(1)* %ptr.cast)
+  call void @use_obj16(i16 addrspace(1)* %ptr.cast2)
+  ret void
+}
+
+define void @"test_loop"(i32 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_loop
+entry:
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  ; CHECK: getelementptr
+  br label %loop
+
+loop:
+  ; CHECK: phi i32 addrspace(1)* [ %ptr.gep, %entry ], [ %ptr.gep.remat, %loop ]
+  ; CHECK: phi i32 addrspace(1)* [ %base, %entry ], [ %base.relocated.casted, %loop ]
+  call void @use_obj32(i32 addrspace(1)* %ptr.gep)
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: getelementptr
+  br label %loop
+}
+
+define void @"test_too_long"(i32 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: test_too_long
+entry:
+  %ptr.gep   = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  %ptr.gep1  = getelementptr i32, i32 addrspace(1)* %ptr.gep, i32 15
+  %ptr.gep2  = getelementptr i32, i32 addrspace(1)* %ptr.gep1, i32 15
+  %ptr.gep3  = getelementptr i32, i32 addrspace(1)* %ptr.gep2, i32 15
+  %ptr.gep4  = getelementptr i32, i32 addrspace(1)* %ptr.gep3, i32 15
+  %ptr.gep5  = getelementptr i32, i32 addrspace(1)* %ptr.gep4, i32 15
+  %ptr.gep6  = getelementptr i32, i32 addrspace(1)* %ptr.gep5, i32 15
+  %ptr.gep7  = getelementptr i32, i32 addrspace(1)* %ptr.gep6, i32 15
+  %ptr.gep8  = getelementptr i32, i32 addrspace(1)* %ptr.gep7, i32 15
+  %ptr.gep9  = getelementptr i32, i32 addrspace(1)* %ptr.gep8, i32 15
+  %ptr.gep10 = getelementptr i32, i32 addrspace(1)* %ptr.gep9, i32 15
+  %ptr.gep11 = getelementptr i32, i32 addrspace(1)* %ptr.gep10, i32 15
+  %sp = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  ; CHECK: gc.relocate
+  ; CHECK: bitcast
+  call void @use_obj32(i32 addrspace(1)* %ptr.gep11)
+  ret void
+}
+
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)