[RS4GC] Use "deopt" operand bundles

[sanjoy]

Summary

This is a step towards using operand bundles to carry deopt state till
RewriteStatepointsForGC. The change adds a flag to
RewriteStatepointsForGC that teaches it to pick up deopt state from a
"deopt" operand bundle attached to the call or invoke it is
wrapping.

The command line flag added, -rs4gc-use-deopt-bundles, will only exist
for a short while. Once we are able to pipe deopt bundle state through
the full optimization pipeline without problems, we will "constant fold"
-rs4gc-use-deopt-bundles to true.

[sanjoy]

Add test cases and do what it takes to get them to pass:

• The tests were ported automatically, so there may be some skew in the ; CHECK lines. I'll audit them before checking in, but please comment if you find some obvious goof-up.
• This change fixes a bug in the earlier version of this change: if the return value of a function being wrapped in gc.statepoint is itself live over some safepoint, we cannot just RAUW / erase that function call because we may have a raw pointer to it in some PartiallyConstructedSafepointRecord. This updated change fixes this issue by deferring the RAUW and erase from parent till after the live sets have been made explicit in the IR.

PS: while this update is not logically distinct from change it is
updating, I can separate out the update into a separate change if you
think that will make the review easier.

[reames]

There's enough changing in this diff that I can't really get a sense for what's going on. I'm going to need you to split this up a bit. There appear to be a couple of refactorings hidden within this patch. Please separate them and submit them.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

168 ↗

(On Diff #36574)

Changing to an AssertVH is a refactoring, please separate.

193 ↗

(On Diff #36574)

This is the same as isGCLeafFunction in PlaceSafepoints. Pull into a common utility file. /Utils/Local.h?

212 ↗

(On Diff #36574)

This feels like a missing function on CallSite. getOperandBundle(Name)?

1370 ↗

(On Diff #36574)

This bit really confused me. Refactoring? Or something subtle that's not documented/explained?

1446 ↗

(On Diff #36574)

This section is a refactoring, please separate.

[sanjoy]

• extract out most of the non-semantic refactoring to make this change simpler

[sanjoy]

• add a comment

[reames]

Mostly minor comments. Question about transition args is potentially not minor.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1354 ↗

(On Diff #36693)

This comment could be far clearer. I shouldn't have to go look at what perform does to understand the purpose of the class.

1362 ↗

(On Diff #36693)

add assert Old != New.

1364 ↗

(On Diff #36693)

minor: The common name for this would be something like "do".

1414 ↗

(On Diff #36693)

Does this mean that to support the MSFT guys, we're going to need both code paths for a while to come? I think it does.

1530 ↗

(On Diff #36693)

Sinking these asserts into the else clause would be far more clear.

1543 ↗

(On Diff #36693)

We've already taken the name for the token above. This needs adjusted for the new location.

1555 ↗

(On Diff #36693)

Wait, what? Oh, your replacements also does deletion. Got it. Slightly confusing.

1561 ↗

(On Diff #36693)

I believe both schemes could use the deferred update safely for the record. Less divergent code.

2415 ↗

(On Diff #36693)

You need a comment here about what this is and why it's needed.

2429 ↗

(On Diff #36693)

Followed by: clear replacements

2436 ↗

(On Diff #36693)

Any reason this can't be done immediate after inserting the statepoint? Having it in the next loop after the replacements makes me think there's a reason for that?

test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-1.ll

1 ↗

(On Diff #36693)

I am really buged by the fact that you need to duplicate all the test cases like this. I don't have a good alternative other than what we've already discussed, but I'm worried this is a sign of poor factoring in the code.

[sanjoy]

• address review. Note that some names have changed because I changed how I named Token when using deopt bundles.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1354 ↗

(On Diff #36692)

There's a comment on why this is needed before the Replacements.emplace_back(CS.getInstruction(), GCResult); bit.

1364 ↗

(On Diff #36693)

Renamed to doReplacement.

1414 ↗

(On Diff #36693)

We need to have a discussion about this (I'll send out an email shortly); but yes, we'll have to keep both paths till LLILC is able to generate "gc-transition" operand bundles. I think the changes to LLILC should be fairly minimal (and will probably actually reduce complexity in LLILC), but this is really gated on us bringing operand bundles to an adequate level of stability.

1555 ↗

(On Diff #36693)

Mentioned that in the comment.

1561 ↗

(On Diff #36693)

I agree that it would be correct to have both schemes to use DeferredReplacement; but I suspect that will be more confusing to read since in one case we'd replace one token with another, whereas in the other case we'd replace a normal return value with gc_result (so there will be some divergent code anyway).

[reames]

LGTM w/minor comments. My concern about test duplication still stands, but given this is a temporary step, I'm okay with it for a short period.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

79 ↗

(On Diff #37434)

I think this needs to default to true.

1416 ↗

(On Diff #37434)

Add a TODO please.

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

 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);
 
+static cl::opt<bool> UseDeoptBundles("rs4gc-use-deopt-bundles", cl::Hidden,
+                                     cl::init(false));
+static cl::opt<bool>
+    AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",
+                                   cl::Hidden, cl::init(true));
+
 namespace {
 struct RewriteStatepointsForGC : public ModulePass {
   static char ID; // Pass identification, replacement for typeid
 
   RewriteStatepointsForGC() : ModulePass(ID) {
     initializeRewriteStatepointsForGCPass(*PassRegistry::getPassRegistry());
   }
   bool runOnFunction(Function &F);
struct PartiallyConstructedSafepointRecord {
 
   /// 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;
 };
 }
 
+static ArrayRef<Use> GetDeoptBundleOperands(ImmutableCallSite CS) {
+  assert(UseDeoptBundles && "Should not be called otherwise!");
+
+  Optional<OperandBundleUse> DeoptBundle = CS.getOperandBundle("deopt");
+
+  if (!DeoptBundle.hasValue()) {
+    assert(AllowStatepointWithNoDeoptInfo &&
+           "Found non-leaf call without deopt info!");
+    return None;
+  }
+
+  return DeoptBundle.getValue().Inputs;
+}
+
 /// 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
 /// Values at a particular instruction.
 static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
                               StatepointLiveSetTy &out);
CallInst *Reloc = Builder.CreateCall(
         GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
         suffixed_name_or(LiveVariables[i], ".relocated", ""));
     // Trick CodeGen into thinking there are lots of free registers at this
     // fake call.
     Reloc->setCallingConv(CallingConv::Cold);
   }
 }
 
+namespace {
+
+/// This struct is used to defer RAUWs and `eraseFromParent` s.  Using this
+/// avoids having to worry about keeping around dangling pointers to Values.
+class DeferredReplacement {
+  AssertingVH<Instruction> Old;
+  AssertingVH<Instruction> New;
+
+public:
+  explicit DeferredReplacement(Instruction *Old, Instruction *New) :
+    Old(Old), New(New) {
+    assert(Old != New && "Not allowed!");
+  }
+
+  /// Does the task represented by this instance.
+  void doReplacement() {
+    Instruction *OldI = Old;
+    Instruction *NewI = New;
+
+    assert(OldI != NewI && "Disallowed at construction?!");
+
+    Old = nullptr;
+    New = nullptr;
+
+    if (NewI)
+      OldI->replaceAllUsesWith(NewI);
+    OldI->eraseFromParent();
+  }
+};
+}
+
 static void
 makeStatepointExplicitImpl(const CallSite CS, /* to replace */
                            const SmallVectorImpl<Value *> &BasePtrs,
                            const SmallVectorImpl<Value *> &LiveVariables,
-                           PartiallyConstructedSafepointRecord &Result) {
+                           PartiallyConstructedSafepointRecord &Result,
+                           std::vector<DeferredReplacement> &Replacements) {
   assert(BasePtrs.size() == LiveVariables.size());
-  assert(isStatepoint(CS) &&
+  assert((UseDeoptBundles || isStatepoint(CS)) &&
          "This method expects to be rewriting a statepoint");
 
   // Then go ahead and use the builder do actually do the inserts.  We insert
   // immediately before the previous instruction under the assumption that all
   // arguments will be available here.  We can't insert afterwards since we may
   // be replacing a terminator.
   Instruction *InsertBefore = CS.getInstruction();
   IRBuilder<> Builder(InsertBefore);
 
-  Statepoint OldSP(CS);
-
   ArrayRef<Value *> GCArgs(LiveVariables);
-  uint64_t StatepointID = OldSP.getID();
-  uint32_t NumPatchBytes = OldSP.getNumPatchBytes();
-  uint32_t Flags = OldSP.getFlags();
-
-  ArrayRef<Use> CallArgs(OldSP.arg_begin(), OldSP.arg_end());
-  ArrayRef<Use> DeoptArgs(OldSP.vm_state_begin(), OldSP.vm_state_end());
-  ArrayRef<Use> TransitionArgs(OldSP.gc_transition_args_begin(),
-                               OldSP.gc_transition_args_end());
-  Value *CallTarget = OldSP.getCalledValue();
+  uint64_t StatepointID = 0xABCDEF00;
+  uint32_t NumPatchBytes = 0;
+  uint32_t Flags = uint32_t(StatepointFlags::None);
+
+  ArrayRef<Use> CallArgs;
+  ArrayRef<Use> DeoptArgs;
+  ArrayRef<Use> TransitionArgs;
+
+  Value *CallTarget = nullptr;
+
+  if (UseDeoptBundles) {
+    CallArgs = {CS.arg_begin(), CS.arg_end()};
+    DeoptArgs = GetDeoptBundleOperands(CS);
+    // TODO: we don't fill in TransitionArgs or Flags in this branch, but we
+    // could have an operand bundle for that too.
+    AttributeSet OriginalAttrs = CS.getAttributes();
+
+    Attribute AttrID = OriginalAttrs.getAttribute(AttributeSet::FunctionIndex,
+                                                  "statepoint-id");
+    if (AttrID.isStringAttribute())
+      AttrID.getValueAsString().getAsInteger(10, StatepointID);
+
+    Attribute AttrNumPatchBytes = OriginalAttrs.getAttribute(
+        AttributeSet::FunctionIndex, "statepoint-num-patch-bytes");
+    if (AttrNumPatchBytes.isStringAttribute())
+      AttrNumPatchBytes.getValueAsString().getAsInteger(10, NumPatchBytes);
+
+    CallTarget = CS.getCalledValue();
+  } else {
+    // This branch will be gone soon, and we will soon only support the
+    // UseDeoptBundles == true configuration.
+    Statepoint OldSP(CS);
+    StatepointID = OldSP.getID();
+    NumPatchBytes = OldSP.getNumPatchBytes();
+    Flags = OldSP.getFlags();
+
+    CallArgs = {OldSP.arg_begin(), OldSP.arg_end()};
+    DeoptArgs = {OldSP.vm_state_begin(), OldSP.vm_state_end()};
+    TransitionArgs = {OldSP.gc_transition_args_begin(),
+                      OldSP.gc_transition_args_end()};
+    CallTarget = OldSP.getCalledValue();
+  }
 
   // Create the statepoint given all the arguments
   Instruction *Token = nullptr;
   AttributeSet ReturnAttrs;
   if (CS.isCall()) {
     CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
     CallInst *Call = Builder.CreateGCStatepointCall(
         StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
if (CS.isCall()) {
 
     Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
 
     // gc relocates will be generated later as if it were regular call
     // statepoint
   }
   assert(Token && "Should be set in one of the above branches!");
 
-  // Take the name of the original value call if it had one.
-  Token->takeName(CS.getInstruction());
-
-// The GCResult is already inserted, we just need to find it
-#ifndef NDEBUG
-  Instruction *ToReplace = CS.getInstruction();
-  assert(!ToReplace->hasNUsesOrMore(2) &&
+  if (UseDeoptBundles) {
+    Token->setName("statepoint_token");
+    if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
+      StringRef Name =
+          CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
+      CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), Name);
+      GCResult->setAttributes(CS.getAttributes().getRetAttributes());
+
+      // We cannot RAUW or delete CS.getInstruction() because it could be in the
+      // live set of some other safepoint, in which case that safepoint's
+      // PartiallyConstructedSafepointRecord will hold a raw pointer to this
+      // llvm::Instruction.  Instead, we defer the replacement and deletion to
+      // after the live sets have been made explicit in the IR, and we no longer
+      // have raw pointers to worry about.
+      Replacements.emplace_back(CS.getInstruction(), GCResult);
+    } else {
+      Replacements.emplace_back(CS.getInstruction(), nullptr);
+    }
+  } else {
+    assert(!CS.getInstruction()->hasNUsesOrMore(2) &&
            "only valid use before rewrite is gc.result");
-  assert(!ToReplace->hasOneUse() ||
-         isGCResult(cast<Instruction>(*ToReplace->user_begin())));
-#endif
+    assert(!CS.getInstruction()->hasOneUse() ||
+           isGCResult(cast<Instruction>(*CS.getInstruction()->user_begin())));
+
+    // Take the name of the original statepoint token if there was one.
+    Token->takeName(CS.getInstruction());
 
     // Update the gc.result of the original statepoint (if any) to use the newly
     // inserted statepoint.  This is safe to do here since the token can't be
     // considered a live reference.
     CS.getInstruction()->replaceAllUsesWith(Token);
+    CS.getInstruction()->eraseFromParent();
+  }
 
   Result.StatepointToken = Token;
 
   // Second, create a gc.relocate for every live variable
   const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx();
   CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder);
 }
 

 
 // Replace an existing gc.statepoint with a new one and a set of gc.relocates
 // which make the relocations happening at this safepoint explicit.
 //
 // WARNING: Does not do any fixup to adjust users of the original live
 // values.  That's the callers responsibility.
 static void
 makeStatepointExplicit(DominatorTree &DT, const CallSite &CS,
-                       PartiallyConstructedSafepointRecord &Result) {
+                       PartiallyConstructedSafepointRecord &Result,
+                       std::vector<DeferredReplacement> &Replacements) {
   const auto &LiveSet = Result.LiveSet;
   const auto &PointerToBase = Result.PointerToBase;
 
   // Convert to vector for efficient cross referencing.
   SmallVector<Value *, 64> BaseVec, LiveVec;
   LiveVec.reserve(LiveSet.size());
   BaseVec.reserve(LiveSet.size());
   for (Value *L : LiveSet) {
     LiveVec.push_back(L);
     assert(PointerToBase.count(L));
     Value *Base = PointerToBase.find(L)->second;
     BaseVec.push_back(Base);
   }
   assert(LiveVec.size() == BaseVec.size());
 
   // To make the output IR slightly more stable (for use in diffs), ensure a
   // fixed order of the values in the safepoint (by sorting the value name).
   // The order is otherwise meaningless.
   StabilizeOrder(BaseVec, LiveVec);
 
   // Do the actual rewriting and delete the old statepoint
-  makeStatepointExplicitImpl(CS, BaseVec, LiveVec, Result);
-  CS.getInstruction()->eraseFromParent();
+  makeStatepointExplicitImpl(CS, BaseVec, LiveVec, Result, Replacements);
 }
 
 // Helper function for the relocationViaAlloca.
 //
 // It receives iterator to the statepoint gc relocates and emits a store to the
 // assigned location (via allocaMap) for the each one of them.  It adds the
 // visited values into the visitedLiveValues set, which we will later use them
 // for sanity checking.

 #ifndef NDEBUG
   // sanity check the input
   std::set<CallSite> Uniqued;
   Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
   assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
 
   for (CallSite CS : ToUpdate) {
     assert(CS.getInstruction()->getParent()->getParent() == &F);
-    assert(isStatepoint(CS) && "expected to already be a deopt statepoint");
+    assert((UseDeoptBundles || isStatepoint(CS)) &&
+           "expected to already be a deopt statepoint");
   }
 #endif
 
   // When inserting gc.relocates for invokes, we need to be able to insert at
   // the top of the successor blocks.  See the comment on
   // normalForInvokeSafepoint on exactly what is needed.  Note that this step
   // may restructure the CFG.
   for (CallSite CS : ToUpdate) {
     if (!CS.isInvoke())
       continue;
     auto *II = cast<InvokeInst>(CS.getInstruction());
     normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);
     normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);
   }
 
   // A list of dummy calls added to the IR to keep various values obviously
   // live in the IR.  We'll remove all of these when done.
   SmallVector<CallInst *, 64> Holders;
 
   // Insert a dummy call with all of the arguments to the vm_state we'll need
   // for the actual safepoint insertion.  This ensures reference arguments in
   // the deopt argument list are considered live through the safepoint (and
   // thus makes sure they get relocated.)
   for (CallSite CS : ToUpdate) {
-    Statepoint StatepointCS(CS);
-
     SmallVector<Value *, 64> DeoptValues;
-    for (Use &U : StatepointCS.vm_state_args()) {
-      Value *Arg = cast<Value>(&U);
+
+    iterator_range<const Use *> DeoptStateRange =
+        UseDeoptBundles
+            ? iterator_range<const Use *>(GetDeoptBundleOperands(CS))
+            : iterator_range<const Use *>(Statepoint(CS).vm_state_args());
+
+    for (Value *Arg : DeoptStateRange) {
       assert(!isUnhandledGCPointerType(Arg->getType()) &&
              "support for FCA unimplemented");
       if (isHandledGCPointerType(Arg->getType()))
         DeoptValues.push_back(Arg);
     }
+
     insertUseHolderAfter(CS, DeoptValues, Holders);
   }
 
   SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size());
 
   // A) Identify all gc pointers which are statically live at the given call
   // site.
   findLiveReferences(F, DT, P, ToUpdate, Records);
#endif
   // some values instead of relocating them. This is purely an optimization and
   // does not influence correctness.
   TargetTransformInfo &TTI =
     P->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
   for (size_t i = 0; i < Records.size(); i++)
     rematerializeLiveValues(ToUpdate[i], Records[i], TTI);
 
+  // We need this to safely RAUW and delete call or invoke return values that
+  // may themselves be live over a statepoint.  For details, please see usage in
+  // makeStatepointExplicitImpl.
+  std::vector<DeferredReplacement> Replacements;
+
   // 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++)
-    makeStatepointExplicit(DT, ToUpdate[i], Records[i]);
+    makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements);
 
   ToUpdate.clear(); // prevent accident use of invalid CallSites
 
+  for (auto &PR : Replacements)
+    PR.doReplacement();
+
+  Replacements.clear();
+
+  for (auto &Info : Records) {
+    // These live sets may contain state Value pointers, since we replaced calls
+    // with operand bundles with calls wrapped in gc.statepoint, and some of
+    // those calls may have been def'ing live gc pointers.  Clear these out to
+    // avoid accidentally using them.
+    //
+    // TODO: We should create a separate data structure that does not contain
+    // these live sets, and migrate to using that data structure from this point
+    // onward.
+    Info.LiveSet.clear();
+    Info.PointerToBase.clear();
+  }
+
   // Do all the fixups of the original live variables to their relocated selves
   SmallVector<Value *, 128> Live;
   for (size_t i = 0; i < Records.size(); i++) {
     PartiallyConstructedSafepointRecord &Info = Records[i];
+
     // We can't simply save the live set from the original insertion.  One of
     // the live values might be the result of a call which needs a safepoint.
     // That Value* no longer exists and we need to use the new gc_result.
     // Thankfully, the live set is embedded in the statepoint (and updated), so
     // we just grab that.
     Statepoint Statepoint(Info.StatepointToken);
     Live.insert(Live.end(), Statepoint.gc_args_begin(),
                 Statepoint.gc_args_end());
bool RewriteStatepointsForGC::runOnFunction(Function &F) {
 
   // Policy choice says not to rewrite - the most common reason is that we're
   // compiling code without a GCStrategy.
   if (!shouldRewriteStatepointsIn(F))
     return false;
 
   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 
+  auto NeedsRewrite = [](Instruction &I) {
+    if (UseDeoptBundles) {
+      if (ImmutableCallSite CS = ImmutableCallSite(&I))
+        return !callsGCLeafFunction(CS);
+      return false;
+    }
+
+    return isStatepoint(I);
+  };
+
   // Gather all the statepoints which need rewritten.  Be careful to only
   // consider those in reachable code since we need to ask dominance queries
   // when rewriting.  We'll delete the unreachable ones in a moment.
   SmallVector<CallSite, 64> ParsePointNeeded;
   bool HasUnreachableStatepoint = false;
   for (Instruction &I : instructions(F)) {
     // TODO: only the ones with the flag set!
-    if (isStatepoint(I)) {
+    if (NeedsRewrite(I)) {
       if (DT.isReachableFromEntry(I.getParent()))
         ParsePointNeeded.push_back(CallSite(&I));
       else
         HasUnreachableStatepoint = true;
     }
   }
 
   bool MadeChange = false;

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-1.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %merged_value base %merged_value.base
+
+declare void @site_for_call_safpeoint()
+
+define i64 addrspace(1)* @test(i64 addrspace(1)* %base_obj_x, i64 addrspace(1)* %base_obj_y, i1 %runtime_condition) gc "statepoint-example" {
+entry:
+  br i1 %runtime_condition, label %here, label %there
+
+here:                                             ; preds = %entry
+  %x = getelementptr i64, i64 addrspace(1)* %base_obj_x, i32 1
+  br label %merge
+
+there:                                            ; preds = %entry
+  %y = getelementptr i64, i64 addrspace(1)* %base_obj_y, i32 1
+  br label %merge
+
+merge:                                            ; preds = %there, %here
+; CHECK-LABEL: merge:
+; CHECK:   %merged_value.base = phi i64 addrspace(1)* [ %base_obj_x, %here ], [ %base_obj_y, %there ]
+  %merged_value = phi i64 addrspace(1)* [ %x, %here ], [ %y, %there ]
+  call void @site_for_call_safpeoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %merged_value
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-10.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+
+declare i1 @runtime_value() "gc-leaf-function"
+
+declare void @do_safepoint()
+
+define void @select_of_phi(i64 addrspace(1)* %base_obj_x, i64 addrspace(1)* %base_obj_y) gc "statepoint-example" {
+entry:
+  br label %loop
+
+loop:                                             ; preds = %merge, %entry
+  %current_x = phi i64 addrspace(1)* [ %base_obj_x, %entry ], [ %next_x, %merge ]
+  %current_y = phi i64 addrspace(1)* [ %base_obj_y, %entry ], [ %next_y, %merge ]
+  %current = phi i64 addrspace(1)* [ null, %entry ], [ %next, %merge ]
+  %condition = call i1 @runtime_value()
+  %next_x = getelementptr i64, i64 addrspace(1)* %current_x, i32 1
+  %next_y = getelementptr i64, i64 addrspace(1)* %current_y, i32 1
+  br i1 %condition, label %true, label %false
+
+true:                                             ; preds = %loop
+  br label %merge
+
+false:                                            ; preds = %loop
+  br label %merge
+
+merge:                                            ; preds = %false, %true
+  %next = phi i64 addrspace(1)* [ %next_x, %true ], [ %next_y, %false ]
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop
+}
+; CHECK: Base Pairs (w/o Relocation):
+; CHECK-DAG: derived %next base %next.base
+; CHECK-DAG: derived %next_x base %base_obj_x
+; CHECK-DAG: derived %next_y base %base_obj_y

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-11.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers  -S 2>&1 | FileCheck %s
+
+; CHECK: derived %next base %base_obj
+
+declare void @do_safepoint()
+
+define void @test(i64 addrspace(1)* %base_obj) gc "statepoint-example" {
+entry:
+  %obj = getelementptr i64, i64 addrspace(1)* %base_obj, i32 1
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+; CHECK-LABEL: loop:
+; CHECK: phi i64 addrspace(1)*
+; CHECK-DAG:  [ %base_obj.relocated.casted, %loop ] 
+; CHECK-DAG:  [ %base_obj, %entry ]
+; CHECK:  %current = phi i64 addrspace(1)* 
+; CHECK-DAG:  [ %obj, %entry ]
+; CHECK-DAG:  [ %next.relocated.casted, %loop ]
+  %current = phi i64 addrspace(1)* [ %obj, %entry ], [ %next, %loop ]
+  %next = getelementptr i64, i64 addrspace(1)* %current, i32 1
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-2.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %merged_value base %base_obj
+
+define i64 addrspace(1)* @test(i64 addrspace(1)* %base_obj, i1 %runtime_condition) gc "statepoint-example" {
+entry:
+  br i1 %runtime_condition, label %merge, label %there
+
+there:                                            ; preds = %entry
+  %derived_obj = getelementptr i64, i64 addrspace(1)* %base_obj, i32 1
+  br label %merge
+
+merge:                                            ; preds = %there, %entry
+  %merged_value = phi i64 addrspace(1)* [ %base_obj, %entry ], [ %derived_obj, %there ]
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %merged_value
+}
+
+declare void @foo()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-3.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %next.i64 base %base_obj
+
+define void @test(i64 addrspace(1)* %base_obj) gc "statepoint-example" {
+entry:
+  %obj = getelementptr i64, i64 addrspace(1)* %base_obj, i32 1
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %current = phi i64 addrspace(1)* [ %obj, %entry ], [ %next.i64, %loop ]
+  %current.i32 = bitcast i64 addrspace(1)* %current to i32 addrspace(1)*
+  %next.i32 = getelementptr i32, i32 addrspace(1)* %current.i32, i32 1
+  %next.i64 = bitcast i32 addrspace(1)* %next.i32 to i64 addrspace(1)*
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop
+}
+
+declare void @do_safepoint()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-4.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %obj_to_consume base %obj_to_consume
+
+declare void @foo()
+
+declare i64 addrspace(1)* @generate_obj()
+
+declare void @consume_obj(i64 addrspace(1)*)
+
+define void @test(i32 %condition) gc "statepoint-example" {
+entry:
+  br label %loop
+
+loop:                                             ; preds = %merge.split, %entry
+; CHECK: loop:
+; CHECK:  [[TOKEN_0:%[^ ]+]] = call i32 (i64, i32, i64 addrspace(1)* ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_p1i64f(i64 2882400000, i32 0, i64 addrspace(1)* ()* @generate_obj, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i3
+; CHECK-NEXT:  [[RESULT_0:%[^ ]+]] = call i64 addrspace(1)* @llvm.experimental.gc.result
+  %0 = call i64 addrspace(1)* @generate_obj() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  switch i32 %condition, label %dest_a [
+    i32 0, label %dest_b
+    i32 1, label %dest_c
+  ]
+
+dest_a:                                           ; preds = %loop
+  br label %merge
+
+dest_b:                                           ; preds = %loop
+  br label %merge
+
+dest_c:                                           ; preds = %loop
+  br label %merge
+
+merge:                                            ; preds = %dest_c, %dest_b, %dest_a
+; CHECK: merge:
+; CHECK:  %obj_to_consume = phi i64 addrspace(1)* [ [[RESULT_0]], %dest_a ], [ null, %dest_b ], [ null, %dest_c ]
+  %obj_to_consume = phi i64 addrspace(1)* [ %0, %dest_a ], [ null, %dest_b ], [ null, %dest_c ]
+  call void @consume_obj(i64 addrspace(1)* %obj_to_consume) [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %merge.split
+
+merge.split:                                      ; preds = %merge
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-5.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %merged_value base %merged_value.base
+
+declare void @foo()
+
+define i64 addrspace(1)* @test(i64 addrspace(1)* %base_obj_x, i64 addrspace(1)* %base_obj_y, i1 %runtime_condition) gc "statepoint-example" {
+entry:
+  br i1 %runtime_condition, label %here, label %there
+
+here:                                             ; preds = %entry
+  br label %bump
+
+bump:                                             ; preds = %here
+  br label %merge
+
+there:                                            ; preds = %entry
+  %y = getelementptr i64, i64 addrspace(1)* %base_obj_y, i32 1
+  br label %merge
+
+merge:                                            ; preds = %there, %bump
+; CHECK: merge:
+; CHECK:  %merged_value.base = phi i64 addrspace(1)* [ %base_obj_x, %bump ], [ %base_obj_y, %there ]
+; CHECK-NEXT:  %merged_value = phi i64 addrspace(1)* [ %base_obj_x, %bump ], [ %y, %there ]  
+  %merged_value = phi i64 addrspace(1)* [ %base_obj_x, %bump ], [ %y, %there ]
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %merged_value
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-6.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %merged_value base %merged_value.base
+
+declare void @site_for_call_safpeoint()
+
+define i64 addrspace(1)* @test(i64 addrspace(1)* %base_obj_x, i64 addrspace(1)* %base_obj_y, i1 %runtime_condition_x, i1 %runtime_condition_y) gc "statepoint-example" {
+entry:
+  br i1 %runtime_condition_x, label %here, label %there
+
+here:                                             ; preds = %entry
+  br i1 %runtime_condition_y, label %bump_here_a, label %bump_here_b
+
+bump_here_a:                                      ; preds = %here
+  %x_a = getelementptr i64, i64 addrspace(1)* %base_obj_x, i32 1
+  br label %merge_here
+
+bump_here_b:                                      ; preds = %here
+  %x_b = getelementptr i64, i64 addrspace(1)* %base_obj_x, i32 2
+  br label %merge_here
+
+merge_here:                                       ; preds = %bump_here_b, %bump_here_a
+  %x = phi i64 addrspace(1)* [ %x_a, %bump_here_a ], [ %x_b, %bump_here_b ]
+  br label %merge
+
+there:                                            ; preds = %entry
+  %y = getelementptr i64, i64 addrspace(1)* %base_obj_y, i32 1
+  br label %merge
+
+merge:                                            ; preds = %there, %merge_here
+; CHECK: merge:
+; CHECK:  %merged_value.base = phi i64 addrspace(1)* [ %base_obj_x, %merge_here ], [ %base_obj_y, %there ]
+; CHECK-NEXT:  %merged_value = phi i64 addrspace(1)* [ %x, %merge_here ], [ %y, %there ]  
+  %merged_value = phi i64 addrspace(1)* [ %x, %merge_here ], [ %y, %there ]
+  call void @site_for_call_safpeoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %merged_value
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-7.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %merged_value base %merged_value.base
+
+declare void @site_for_call_safpeoint()
+
+define i64 addrspace(1)* @test(i64 addrspace(1)* %base_obj_x, i64 addrspace(1)* %base_obj_y, i1 %runtime_condition_x, i1 %runtime_condition_y) gc "statepoint-example" {
+entry:
+  br i1 %runtime_condition_x, label %here, label %there
+
+here:                                             ; preds = %entry
+  br i1 %runtime_condition_y, label %bump_here_a, label %bump_here_b
+
+bump_here_a:                                      ; preds = %here
+  %x_a = getelementptr i64, i64 addrspace(1)* %base_obj_x, i32 1
+  br label %merge_here
+
+bump_here_b:                                      ; preds = %here
+  %x_b = getelementptr i64, i64 addrspace(1)* %base_obj_y, i32 2
+  br label %merge_here
+
+merge_here:                                       ; preds = %bump_here_b, %bump_here_a
+; CHECK: merge_here:
+; CHECK-DAG: %x.base
+; CHECK-DAG: phi i64 addrspace(1)*
+; CHECK-DAG: [ %base_obj_x, %bump_here_a ]
+; CHECK-DAG: [ %base_obj_y, %bump_here_b ]
+  %x = phi i64 addrspace(1)* [ %x_a, %bump_here_a ], [ %x_b, %bump_here_b ]
+  br label %merge
+
+there:                                            ; preds = %entry
+  %y = getelementptr i64, i64 addrspace(1)* %base_obj_y, i32 1
+  br label %merge
+
+merge:                                            ; preds = %there, %merge_here
+; CHECK: merge:
+; CHECK-DAG:  %merged_value.base
+; CHECK-DAG: phi i64 addrspace(1)*
+; CHECK-DAG: %merge_here
+; CHECK-DAG: [ %base_obj_y, %there ]
+; CHECK:  %merged_value = phi i64 addrspace(1)* [ %x, %merge_here ], [ %y, %there ]  
+  %merged_value = phi i64 addrspace(1)* [ %x, %merge_here ], [ %y, %there ]
+  call void @site_for_call_safpeoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %merged_value
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-8.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S 2>&1 | FileCheck %s
+
+; CHECK: derived %next_element_ptr base %array_obj
+
+define i32 @null_in_array(i64 addrspace(1)* %array_obj) gc "statepoint-example" {
+entry:
+  %array_len_pointer.i64 = getelementptr i64, i64 addrspace(1)* %array_obj, i32 1
+  %array_len_pointer.i32 = bitcast i64 addrspace(1)* %array_len_pointer.i64 to i32 addrspace(1)*
+  %array_len = load i32, i32 addrspace(1)* %array_len_pointer.i32
+  %array_elems = bitcast i32 addrspace(1)* %array_len_pointer.i32 to i64 addrspace(1)* addrspace(1)*
+  br label %loop_check
+
+loop_check:                                       ; preds = %loop_back, %entry
+  %index = phi i32 [ 0, %entry ], [ %next_index, %loop_back ]
+  %current_element_ptr = phi i64 addrspace(1)* addrspace(1)* [ %array_elems, %entry ], [ %next_element_ptr, %loop_back ]
+  %index_lt = icmp ult i32 %index, %array_len
+  br i1 %index_lt, label %check_for_null, label %not_found
+
+check_for_null:                                   ; preds = %loop_check
+  %current_element = load i64 addrspace(1)*, i64 addrspace(1)* addrspace(1)* %current_element_ptr
+  %is_null = icmp eq i64 addrspace(1)* %current_element, null
+  br i1 %is_null, label %found, label %loop_back
+
+loop_back:                                        ; preds = %check_for_null
+  %next_element_ptr = getelementptr i64 addrspace(1)*, i64 addrspace(1)* addrspace(1)* %current_element_ptr, i32 1
+  %next_index = add i32 %index, 1
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop_check
+
+not_found:                                        ; preds = %loop_check
+  ret i32 -1
+
+found:                                            ; preds = %check_for_null
+  ret i32 %index
+}
+
+declare void @do_safepoint()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers-9.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-print-base-pointers -S  2>&1 | FileCheck %s
+
+; CHECK: derived %next base %base_obj
+
+declare i1 @runtime_value() "gc-leaf-function"
+
+define void @maybe_GEP(i64 addrspace(1)* %base_obj) gc "statepoint-example" {
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %current = phi i64 addrspace(1)* [ %base_obj, %entry ], [ %next, %loop ]
+  %condition = call i1 @runtime_value()
+  %maybe_next = getelementptr i64, i64 addrspace(1)* %current, i32 1
+  %next = select i1 %condition, i64 addrspace(1)* %maybe_next, i64 addrspace(1)* %current
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop
+}
+
+declare void @do_safepoint()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-pointers.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -S 2>&1 | FileCheck %s
+
+; The rewriting needs to make %obj loop variant by inserting a phi 
+; of the original value and it's relocation.
+
+declare i64 addrspace(1)* @generate_obj() "gc-leaf-function"
+
+declare void @use_obj(i64 addrspace(1)*) "gc-leaf-function"
+
+define void @def_use_safepoint() gc "statepoint-example" {
+; CHECK-LABEL: def_use_safepoint
+; CHECK: phi i64 addrspace(1)* 
+; CHECK-DAG: [ %obj.relocated.casted, %loop ]
+; CHECK-DAG: [ %obj, %entry ]
+entry:
+  %obj = call i64 addrspace(1)* @generate_obj()
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  call void @use_obj(i64 addrspace(1)* %obj)
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop
+}
+
+declare void @do_safepoint()
+
+declare void @parse_point(i64 addrspace(1)*)
+
+define i64 addrspace(1)* @test1(i32 %caller, i8 addrspace(1)* %a, i8 addrspace(1)* %b, i32 %unknown) gc "statepoint-example" {
+; CHECK-LABEL: test1
+entry:
+  br i1 undef, label %left, label %right
+
+left:                                             ; preds = %entry
+; CHECK: left:
+; CHECK-NEXT: %a.cast = bitcast i8 addrspace(1)* %a to i64 addrspace(1)*
+; CHECK-NEXT: [[CAST_L:%.*]] = bitcast i8 addrspace(1)* %a to i64 addrspace(1)*
+; Our safepoint placement pass calls removeUnreachableBlocks, which does a bunch
+; of simplifications to branch instructions.  This bug is visible only when
+; there are multiple branches into the same block from the same predecessor, and
+; the following ceremony is to make that artefact survive a call to 
+; removeUnreachableBlocks.  As an example, "br i1 undef, label %merge, label %merge"
+; will get simplified to "br label %merge" by removeUnreachableBlocks.
+  %a.cast = bitcast i8 addrspace(1)* %a to i64 addrspace(1)*
+  switch i32 %unknown, label %right [
+    i32 0, label %merge
+    i32 1, label %merge
+    i32 5, label %merge
+    i32 3, label %right
+  ]
+
+right:                                            ; preds = %left, %left, %entry
+; CHECK: right:
+; CHECK-NEXT: %b.cast = bitcast i8 addrspace(1)* %b to i64 addrspace(1)*
+; CHECK-NEXT: [[CAST_R:%.*]] = bitcast i8 addrspace(1)* %b to i64 addrspace(1)*
+  %b.cast = bitcast i8 addrspace(1)* %b to i64 addrspace(1)*
+  br label %merge
+
+merge:                                            ; preds = %right, %left, %left, %left
+; CHECK: merge:
+; CHECK-NEXT: %value.base = phi i64 addrspace(1)* [ [[CAST_L]], %left ], [ [[CAST_L]], %left ], [ [[CAST_L]], %left ], [ [[CAST_R]], %right ], !is_base_value !0
+  %value = phi i64 addrspace(1)* [ %a.cast, %left ], [ %a.cast, %left ], [ %a.cast, %left ], [ %b.cast, %right ]
+  call void @parse_point(i64 addrspace(1)* %value) [ "deopt"(i32 0, i32 0, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %value
+}
+
+;; The purpose of this test is to ensure that when two live values share a
+;;  base defining value with inherent conflicts, we end up with a *single*
+;;  base phi/select per such node.  This is testing an optimization, not a
+;;  fundemental correctness criteria
+define void @test2(i1 %cnd, i64 addrspace(1)* %base_obj, i64 addrspace(1)* %base_arg2) gc "statepoint-example" {
+; CHECK-LABEL: @test2
+entry:
+  %obj = getelementptr i64, i64 addrspace(1)* %base_obj, i32 1
+  br label %loop
+; CHECK-LABEL: loop
+; CHECK:   %current.base = phi i64 addrspace(1)*
+; CHECK-DAG: [ %base_obj, %entry ]
+
+; Given the two selects are equivelent, so are their base phis - ideally,
+; we'd have commoned these, but that's a missed optimization, not correctness.
+; CHECK-DAG: [ [[DISCARD:%.*.base.relocated.casted]], %loop ]
+; CHECK-NOT: extra.base
+; CHECK: next = select
+; CHECK: extra2.base = select
+; CHECK: extra2 = select
+; CHECK: statepoint
+;; Both 'next' and 'extra2' are live across the backedge safepoint...
+
+loop:                                             ; preds = %loop, %entry
+  %current = phi i64 addrspace(1)* [ %obj, %entry ], [ %next, %loop ]
+  %extra = phi i64 addrspace(1)* [ %obj, %entry ], [ %extra2, %loop ]
+  %nexta = getelementptr i64, i64 addrspace(1)* %current, i32 1
+  %next = select i1 %cnd, i64 addrspace(1)* %nexta, i64 addrspace(1)* %base_arg2
+  %extra2 = select i1 %cnd, i64 addrspace(1)* %nexta, i64 addrspace(1)* %base_arg2
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %loop
+}
+
+define i64 addrspace(1)* @test3(i1 %cnd, i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2) gc "statepoint-example" {
+; CHECK-LABEL: @test3
+entry:
+  br i1 %cnd, label %merge, label %taken
+
+taken:                                            ; preds = %entry
+  br label %merge
+
+merge:                                            ; preds = %taken, %entry
+; CHECK-LABEL: merge:
+; CHECK-NEXT: %bdv = phi
+; CHECK-NEXT: gc.statepoint
+  %bdv = phi i64 addrspace(1)* [ %obj, %entry ], [ %obj2, %taken ]
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %bdv
+}
+
+define i64 addrspace(1)* @test4(i1 %cnd, i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2) gc "statepoint-example" {
+; CHECK-LABEL: @test4
+entry:
+  br i1 %cnd, label %merge, label %taken
+
+taken:                                            ; preds = %entry
+  br label %merge
+
+merge:                                            ; preds = %taken, %entry
+; CHECK-LABEL: merge:
+; CHECK-NEXT: %bdv = phi
+; CHECK-NEXT: gc.statepoint
+  %bdv = phi i64 addrspace(1)* [ %obj, %entry ], [ %obj, %taken ]
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %bdv
+}
+
+define i64 addrspace(1)* @test5(i1 %cnd, i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2) gc "statepoint-example" {
+; CHECK-LABEL: @test5
+entry:
+  br label %merge
+
+merge:                                            ; preds = %merge, %entry
+; CHECK-LABEL: merge:
+; CHECK-NEXT: %bdv = phi
+; CHECK-NEXT: br i1
+  %bdv = phi i64 addrspace(1)* [ %obj, %entry ], [ %obj2, %merge ]
+  br i1 %cnd, label %merge, label %next
+
+next:                                             ; preds = %merge
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %bdv
+}
+
+declare void @foo()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/base-vector.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -S | FileCheck  %s
+
+
+define i64 addrspace(1)* @test(<2 x i64 addrspace(1)*> %vec, i32 %idx) gc "statepoint-example" {
+; CHECK-LABEL: @test
+; CHECK: extractelement
+; CHECK: extractelement
+; CHECK: statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: ; (%base_ee, %base_ee)
+; CHECK: gc.relocate
+; CHECK-DAG: ; (%base_ee, %obj)
+; Note that the second extractelement is actually redundant here.  A correct output would
+; be to reuse the existing obj as a base since it is actually a base pointer.
+entry:
+  %obj = extractelement <2 x i64 addrspace(1)*> %vec, i32 %idx
+  call void @do_safepoint() [ "deopt"() ]
+  ret i64 addrspace(1)* %obj
+}
+
+define i64 addrspace(1)* @test2(<2 x i64 addrspace(1)*>* %ptr, i1 %cnd, i32 %idx1, i32 %idx2) gc "statepoint-example" {
+; CHECK-LABEL: test2
+entry:
+  br i1 %cnd, label %taken, label %untaken
+
+taken:                                            ; preds = %entry
+  %obja = load <2 x i64 addrspace(1)*>, <2 x i64 addrspace(1)*>* %ptr
+  br label %merge
+
+untaken:                                          ; preds = %entry
+  %objb = load <2 x i64 addrspace(1)*>, <2 x i64 addrspace(1)*>* %ptr
+  br label %merge
+
+merge:                                            ; preds = %untaken, %taken
+  %vec = phi <2 x i64 addrspace(1)*> [ %obja, %taken ], [ %objb, %untaken ]
+  br i1 %cnd, label %taken2, label %untaken2
+
+taken2:                                           ; preds = %merge
+  %obj0 = extractelement <2 x i64 addrspace(1)*> %vec, i32 %idx1
+  br label %merge2
+
+untaken2:                                         ; preds = %merge
+  %obj1 = extractelement <2 x i64 addrspace(1)*> %vec, i32 %idx2
+  br label %merge2
+
+merge2:                                           ; preds = %untaken2, %taken2
+; CHECK-LABEL: merge2:
+; CHECK-NEXT: %obj = phi i64 addrspace(1)*
+; CHECK-NEXT: statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: ; (%obj, %obj)
+  %obj = phi i64 addrspace(1)* [ %obj0, %taken2 ], [ %obj1, %untaken2 ]
+  call void @do_safepoint() [ "deopt"() ]
+  ret i64 addrspace(1)* %obj
+}
+
+define i64 addrspace(1)* @test3(i64 addrspace(1)* %ptr) gc "statepoint-example" {
+; CHECK-LABEL: test3
+; CHECK: insertelement
+; CHECK: extractelement
+; CHECK: statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: (%obj, %obj)
+entry:
+  %vec = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %ptr, i32 0
+  %obj = extractelement <2 x i64 addrspace(1)*> %vec, i32 0
+  call void @do_safepoint() [ "deopt"() ]
+  ret i64 addrspace(1)* %obj
+}
+
+define i64 addrspace(1)* @test4(i64 addrspace(1)* %ptr) gc "statepoint-example" {
+; CHECK-LABEL: test4
+; CHECK: statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: ; (%ptr, %obj)
+; CHECK: gc.relocate
+; CHECK-DAG: ; (%ptr, %ptr)
+; When we can optimize an extractelement from a known
+; index and avoid introducing new base pointer instructions
+entry:
+  %derived = getelementptr i64, i64 addrspace(1)* %ptr, i64 16
+  %veca = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %derived, i32 0
+  %vec = insertelement <2 x i64 addrspace(1)*> %veca, i64 addrspace(1)* %ptr, i32 1
+  %obj = extractelement <2 x i64 addrspace(1)*> %vec, i32 0
+  call void @do_safepoint() [ "deopt"() ]
+  ret i64 addrspace(1)* %obj
+}
+
+declare void @use(i64 addrspace(1)*) "gc-leaf-function"
+
+define void @test5(i1 %cnd, i64 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test5
+; CHECK: gc.relocate
+; CHECK-DAG: (%obj, %bdv)
+; When we fundementally have to duplicate
+entry:
+  %gep = getelementptr i64, i64 addrspace(1)* %obj, i64 1
+  %vec = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep, i32 0
+  %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i32 0
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  call void @use(i64 addrspace(1)* %bdv)
+  ret void
+}
+
+define void @test6(i1 %cnd, i64 addrspace(1)* %obj, i64 %idx) gc "statepoint-example" {
+; CHECK-LABEL: @test6
+; CHECK: %gep = getelementptr i64, i64 addrspace(1)* %obj, i64 1
+; CHECK: %vec.base = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %obj, i32 0, !is_base_value !0
+; CHECK: %vec = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep, i32 0
+; CHECK: %bdv.base = extractelement <2 x i64 addrspace(1)*> %vec.base, i64 %idx, !is_base_value !0
+; CHECK:  %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i64 %idx
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: (%bdv.base, %bdv)
+; A more complicated example involving vector and scalar bases.
+; This is derived from a failing test case when we didn't have correct
+; insertelement handling.
+entry:
+  %gep = getelementptr i64, i64 addrspace(1)* %obj, i64 1
+  %vec = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep, i32 0
+  %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i64 %idx
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  call void @use(i64 addrspace(1)* %bdv)
+  ret void
+}
+
+define i64 addrspace(1)* @test7(i1 %cnd, i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2) gc "statepoint-example" {
+; CHECK-LABEL: @test7
+entry:
+  %vec = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %obj2, i32 0
+  br label %merge1
+
+merge1:                                           ; preds = %merge1, %entry
+; CHECK-LABEL: merge1:
+; CHECK: vec2.base
+; CHECK: vec2
+; CHECK: gep
+; CHECK: vec3.base
+; CHECK: vec3
+  %vec2 = phi <2 x i64 addrspace(1)*> [ %vec, %entry ], [ %vec3, %merge1 ]
+  %gep = getelementptr i64, i64 addrspace(1)* %obj2, i64 1
+  %vec3 = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep, i32 0
+  br i1 %cnd, label %merge1, label %next1
+
+next1:                                            ; preds = %merge1
+; CHECK-LABEL: next1:
+; CHECK: bdv.base = 
+; CHECK: bdv = 
+  %bdv = extractelement <2 x i64 addrspace(1)*> %vec2, i32 0
+  br label %merge
+
+merge:                                            ; preds = %merge, %next1
+; CHECK-LABEL: merge:
+; CHECK: %objb.base
+; CHECK: %objb
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: (%objb.base, %objb)
+  %objb = phi i64 addrspace(1)* [ %obj, %next1 ], [ %bdv, %merge ]
+  br i1 %cnd, label %merge, label %next
+
+next:                                             ; preds = %merge
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %objb
+}
+
+declare void @do_safepoint()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/basic.ll

+; RUN: opt -S -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles < %s | FileCheck %s
+
+declare void @g()
+declare i32 @h()
+
+define i32 addrspace(1)* @f0(i32 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: @f0(
+ entry:
+; CHECK: [[TOKEN_0:%[^ ]+]] = call i32 {{[^@]*}} @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @g, i32 0, i32 0, i32 0, i32 1, i32 100, i32 addrspace(1)* %arg)
+  call void @g() [ "deopt"(i32 100) ]
+
+; CHECK: %arg.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 [[TOKEN_0]], i32 8, i32 8)
+  ret i32 addrspace(1)* %arg
+}
+
+define i32 addrspace(1)* @f1(i32 addrspace(1)* %arg) gc "statepoint-example"  personality i32 8  {
+; CHECK-LABEL: @f1(
+ entry:
+; CHECK: [[TOKEN_1:%[^ ]+]] = invoke i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @g, i32 0, i32 0, i32 0, i32 1, i32 100, i32 addrspace(1)* %arg)
+  invoke void @g() [ "deopt"(i32 100) ] to label %normal_dest unwind label %unwind_dest
+
+ normal_dest:
+; CHECK: %arg.relocated1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 [[TOKEN_1]], i32 8, i32 8)
+  ret i32 addrspace(1)* %arg
+
+ unwind_dest: 
+  %lpad = landingpad { i8*, i32 } cleanup
+  resume { i8*, i32 } undef
+}
+
+define i32 addrspace(1)* @f2(i32 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: @f2(
+ entry:
+; CHECK: [[TOKEN_2:%[^ ]+]] = call i32 (i64, i32, i32 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32f(i64 2882400000, i32 0, i32 ()* @h, i32 0, i32 0, i32 0, i32 1, i32 100, i32 addrspace(1)* %arg)
+  %val = call i32 @h() [ "deopt"(i32 100) ]
+
+; CHECK: [[RESULT_F2:%[^ ]+]] = call i32 @llvm.experimental.gc.result.i32(i32 [[TOKEN_2]])
+; CHECK: %arg.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 [[TOKEN_2]], i32 8, i32 8)
+; CHECK: %arg.relocated.casted = bitcast i8 addrspace(1)* %arg.relocated to i32 addrspace(1)*
+
+  store i32 %val, i32 addrspace(1)* %arg
+; CHECK: store i32 [[RESULT_F2]], i32 addrspace(1)* %arg.relocated.casted
+  ret i32 addrspace(1)* %arg
+}
+
+define i32 addrspace(1)* @f3(i32 addrspace(1)* %arg) gc "statepoint-example"  personality i32 8  {
+; CHECK-LABEL: @f3(
+ entry:
+; CHECK: [[TOKEN_3:%[^ ]+]] = invoke i32 (i64, i32, i32 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32f(i64 2882400000, i32 0, i32 ()* @h, i32 0, i32 0, i32 0, i32 1, i32 100, i32 addrspace(1)* %arg)
+  %val = invoke i32 @h() [ "deopt"(i32 100) ] to label %normal_dest unwind label %unwind_dest
+
+ normal_dest:
+; CHECK: [[RESULT_F3:%[^ ]+]] = call i32 @llvm.experimental.gc.result.i32(i32 [[TOKEN_3]])
+; CHECK: [[ARG_RELOCATED:%[^ ]+]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 [[TOKEN_3]], i32 8, i32 8)
+; CHECK: [[ARG_RELOCATED_CASTED:%[^ ]+]] = bitcast i8 addrspace(1)* [[ARG_RELOCATED]] to i32 addrspace(1)*
+
+  store i32 %val, i32 addrspace(1)* %arg
+
+; CHECK: store i32 [[RESULT_F3]], i32 addrspace(1)* [[ARG_RELOCATED_CASTED]]
+  ret i32 addrspace(1)* %arg
+
+ unwind_dest: 
+  %lpad = landingpad { i8*, i32 } cleanup
+  resume { i8*, i32 } undef
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/basics.ll

+; This is a collection of really basic tests for gc.statepoint rewriting.
+; RUN:  opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-rematerialization-threshold=0 -S | FileCheck %s
+
+; Trivial relocation over a single call
+
+declare void @foo()
+
+define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test1
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+; Two safepoints in a row (i.e. consistent liveness)
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %obj
+}
+
+define i8 addrspace(1)* @test2(i8 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test2
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated2 = call coldcc i8 addrspace(1)*
+; A simple derived pointer
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %obj
+}
+
+define i8 @test3(i8 addrspace(1)* %obj) gc "statepoint-example" {
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: getelementptr
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %derived.relocated = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: load i8, i8 addrspace(1)* %derived.relocated
+; CHECK-NEXT: load i8, i8 addrspace(1)* %obj.relocated
+; Tests to make sure we visit both the taken and untaken predeccessor 
+; of merge.  This was a bug in the dataflow liveness at one point.
+  %derived = getelementptr i8, i8 addrspace(1)* %obj, i64 10
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  %a = load i8, i8 addrspace(1)* %derived
+  %b = load i8, i8 addrspace(1)* %obj
+  %c = sub i8 %a, %b
+  ret i8 %c
+}
+
+define i8 addrspace(1)* @test4(i1 %cmp, i8 addrspace(1)* %obj) gc "statepoint-example" {
+entry:
+  br i1 %cmp, label %taken, label %untaken
+
+taken:                                            ; preds = %entry
+; CHECK-LABEL: taken:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %merge
+
+untaken:                                          ; preds = %entry
+; CHECK-LABEL: untaken:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated2 = call coldcc i8 addrspace(1)*
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %merge
+
+merge:                                            ; preds = %untaken, %taken
+; CHECK-LABEL: merge:
+; CHECK-NEXT: %.0 = phi i8 addrspace(1)* [ %obj.relocated, %taken ], [ %obj.relocated2, %untaken ]
+; CHECK-NEXT: ret i8 addrspace(1)* %.0
+; When run over a function which doesn't opt in, should do nothing!
+  ret i8 addrspace(1)* %obj
+}
+
+define i8 addrspace(1)* @test5(i8 addrspace(1)* %obj) gc "ocaml" {
+; CHECK-LABEL: @test5
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NOT: %obj.relocated = call coldcc i8 addrspace(1)*
+  %0 = 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, ...)

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/codegen-cond.ll

+; RUN: opt -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -S < %s | FileCheck %s
+
+; A null test of a single value
+
+define i1 @test(i8 addrspace(1)* %p, i1 %rare) gc "statepoint-example" {
+; CHECK-LABEL: @test
+entry:
+  %cond = icmp eq i8 addrspace(1)* %p, null
+  br i1 %rare, label %safepoint, label %continue, !prof !0
+
+safepoint:                                        ; preds = %entry
+  call void @safepoint() [ "deopt"() ]
+  br label %continue
+
+continue:                                         ; preds = %safepoint, %entry
+; CHECK-LABEL: continue:
+; CHECK: phi
+; CHECK-DAG: [ %p.relocated, %safepoint ]
+; CHECK-DAG: [ %p, %entry ]
+; CHECK: %cond = icmp
+; CHECK: br i1 %cond
+; Comparing two pointers
+  br i1 %cond, label %taken, label %untaken
+
+taken:                                            ; preds = %continue
+  ret i1 true
+
+untaken:                                          ; preds = %continue
+  ret i1 false
+}
+
+define i1 @test2(i8 addrspace(1)* %p, i8 addrspace(1)* %q, i1 %rare) gc "statepoint-example" {
+; CHECK-LABEL: @test2
+entry:
+  %cond = icmp eq i8 addrspace(1)* %p, %q
+  br i1 %rare, label %safepoint, label %continue, !prof !0
+
+safepoint:                                        ; preds = %entry
+  call void @safepoint() [ "deopt"() ]
+  br label %continue
+
+continue:                                         ; preds = %safepoint, %entry
+; CHECK-LABEL: continue:
+; CHECK: phi
+; CHECK-DAG: [ %q.relocated, %safepoint ]
+; CHECK-DAG: [ %q, %entry ]
+; CHECK: phi
+; CHECK-DAG: [ %p.relocated, %safepoint ]
+; CHECK-DAG: [ %p, %entry ]
+; CHECK: %cond = icmp
+; CHECK: br i1 %cond
+; Sanity check that nothing bad happens if already last instruction
+; before terminator
+  br i1 %cond, label %taken, label %untaken
+
+taken:                                            ; preds = %continue
+  ret i1 true
+
+untaken:                                          ; preds = %continue
+  ret i1 false
+}
+
+define i1 @test3(i8 addrspace(1)* %p, i8 addrspace(1)* %q, i1 %rare) gc "statepoint-example" {
+; CHECK-LABEL: @test3
+; CHECK: gc.statepoint
+; CHECK: %cond = icmp
+; CHECK: br i1 %cond
+entry:
+  call void @safepoint() [ "deopt"() ]
+  %cond = icmp eq i8 addrspace(1)* %p, %q
+  br i1 %cond, label %taken, label %untaken
+
+taken:                                            ; preds = %entry
+  ret i1 true
+
+untaken:                                          ; preds = %entry
+  ret i1 false
+}
+
+declare void @safepoint()
+!0 = !{!"branch_weights", i32 1, i32 10000}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/constants.ll

+; RUN: opt -S -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles %s | FileCheck %s
+
+; constants don't get relocated.
+@G = addrspace(1) global i8 5
+
+declare void @foo()
+
+define i8 @test() gc "statepoint-example" {
+; CHECK-LABEL: @test
+; CHECK: gc.statepoint
+; CHECK-NEXT: load i8, i8 addrspace(1)* inttoptr (i64 15 to i8 addrspace(1)*)
+; Mostly just here to show reasonable code test can come from.  
+entry:
+  call void @foo() [ "deopt"() ]
+  %res = load i8, i8 addrspace(1)* inttoptr (i64 15 to i8 addrspace(1)*)
+  ret i8 %res
+}
+
+define i8 @test2(i8 addrspace(1)* %p) gc "statepoint-example" {
+; CHECK-LABEL: @test2
+; CHECK: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: icmp
+; Globals don't move and thus don't get relocated
+entry:
+  call void @foo() [ "deopt"() ]
+  %cmp = icmp eq i8 addrspace(1)* %p, null
+  br i1 %cmp, label %taken, label %not_taken
+
+taken:                                            ; preds = %not_taken, %entry
+  ret i8 0
+
+not_taken:                                        ; preds = %entry
+  %cmp2 = icmp ne i8 addrspace(1)* %p, null
+  br i1 %cmp2, label %taken, label %dead
+
+dead:                                             ; preds = %not_taken
+  %addr = getelementptr i8, i8 addrspace(1)* %p, i32 15
+  %res = load i8, i8 addrspace(1)* %addr
+  ret i8 %res
+}
+
+define i8 @test3(i1 %always_true) gc "statepoint-example" {
+; CHECK-LABEL: @test3
+; CHECK: gc.statepoint
+; CHECK-NEXT: load i8, i8 addrspace(1)* @G
+entry:
+  call void @foo() [ "deopt"() ]
+  %res = load i8, i8 addrspace(1)* @G, align 1
+  ret i8 %res
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/deref-pointers.ll

+; RUN: opt -S -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles < %s | FileCheck %s
+
+; CHECK: declare i8 addrspace(1)* @some_function_ret_deref()
+; CHECK: define i8 addrspace(1)* @test_deref_arg(i8 addrspace(1)* %a)
+; CHECK: define i8 addrspace(1)* @test_deref_or_null_arg(i8 addrspace(1)* %a)
+
+declare void @foo()
+
+declare i8 addrspace(1)* @some_function() "gc-leaf-function"
+
+declare void @some_function_consumer(i8 addrspace(1)*) "gc-leaf-function"
+
+declare dereferenceable(4) i8 addrspace(1)* @some_function_ret_deref() "gc-leaf-function"
+
+define i8 addrspace(1)* @test_deref_arg(i8 addrspace(1)* dereferenceable(4) %a) gc "statepoint-example" {
+entry:
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %a
+}
+
+define i8 addrspace(1)* @test_deref_or_null_arg(i8 addrspace(1)* dereferenceable_or_null(4) %a) gc "statepoint-example" {
+entry:
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %a
+}
+
+define i8 addrspace(1)* @test_deref_retval() gc "statepoint-example" {
+; CHECK-LABEL: @test_deref_retval(
+; CHECK: %a = call i8 addrspace(1)* @some_function()
+entry:
+  %a = call dereferenceable(4) i8 addrspace(1)* @some_function()
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %a
+}
+
+define i8 addrspace(1)* @test_deref_or_null_retval() gc "statepoint-example" {
+; CHECK-LABEL: @test_deref_or_null_retval(
+; CHECK: %a = call i8 addrspace(1)* @some_function()
+entry:
+  %a = call dereferenceable_or_null(4) i8 addrspace(1)* @some_function()
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %a
+}
+
+define i8 @test_md(i8 addrspace(1)* %ptr) gc "statepoint-example" {
+; CHECK-LABEL: @test_md(
+; CHECK: %tmp = load i8, i8 addrspace(1)* %ptr, !tbaa !0
+entry:
+  %tmp = load i8, i8 addrspace(1)* %ptr, !tbaa !0
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 %tmp
+}
+
+define i8 addrspace(1)* @test_decl_only_attribute(i8 addrspace(1)* %ptr) gc "statepoint-example" {
+; CHECK-LABEL: @test_decl_only_attribute(
+; No change here, but the prototype of some_function_ret_deref should have changed.
+; CHECK: call i8 addrspace(1)* @some_function_ret_deref()
+entry:
+  %a = call i8 addrspace(1)* @some_function_ret_deref()
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %a
+}
+
+define i8 addrspace(1)* @test_callsite_arg_attribute(i8 addrspace(1)* %ptr) gc "statepoint-example" {
+; CHECK-LABEL: @test_callsite_arg_attribute(
+; CHECK: call void @some_function_consumer(i8 addrspace(1)* %ptr)
+; CHECK: !0 = !{!1, !1, i64 0}
+; CHECK: !1 = !{!"red", !2}
+; CHECK: !2 = !{!"blue"}
+entry:
+  call void @some_function_consumer(i8 addrspace(1)* dereferenceable(4) %ptr)
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i8 addrspace(1)* %ptr
+}
+!0 = !{!1, !1, i64 0, i64 1}
+!1 = !{!"red", !2}
+!2 = !{!"blue"}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/gc-relocate-creation.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -S 2>&1 | FileCheck %s
+
+; This test is to verify gc.relocate can handle pointer to vector of
+; pointers (<2 x i32 addrspace(1)*> addrspace(1)* in this case).
+; The old scheme to create a gc.relocate of <2 x i32 addrspace(1)*> addrspace(1)*
+; type will fail because llvm does not support mangling vector of pointers.
+; The new scheme will create all gc.relocate to i8 addrspace(1)* type and
+; then bitcast to the correct type.
+
+declare void @foo()
+
+declare void @use(...) "gc-leaf-function"
+
+define void @test1(<2 x i32 addrspace(1)*> addrspace(1)* %obj) gc "statepoint-example" {
+entry:
+; CHECK: %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(i32 %statepoint_token, i32 7, i32 7)
+; CHECK-NEXT:  %obj.relocated.casted = bitcast i8 addrspace(1)* %obj.relocated to <2 x i32 addrspace(1)*> addrspace(1)*
+
+  call void @foo() [ "deopt"() ]
+  call void (...) @use(<2 x i32 addrspace(1)*> addrspace(1)* %obj)
+  ret void
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/live-vector.ll

+; Test that we can correctly handle vectors of pointers in statepoint 
+; rewriting.  Currently, we scalarize, but that's an implementation detail.
+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -S | FileCheck  %s
+
+; A non-vector relocation for comparison
+
+define i64 addrspace(1)* @test(i64 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: test
+; CHECK: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: ret i64 addrspace(1)* %obj.relocated.casted
+; A base vector from a argument
+entry:
+  call void @do_safepoint() [ "deopt"() ]
+  ret i64 addrspace(1)* %obj
+}
+
+define <2 x i64 addrspace(1)*> @test2(<2 x i64 addrspace(1)*> %obj) gc "statepoint-example" {
+; CHECK-LABEL: test2
+; CHECK: extractelement
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: ret <2 x i64 addrspace(1)*> %7
+; A base vector from a load
+entry:
+  call void @do_safepoint() [ "deopt"() ]
+  ret <2 x i64 addrspace(1)*> %obj
+}
+
+define <2 x i64 addrspace(1)*> @test3(<2 x i64 addrspace(1)*>* %ptr) gc "statepoint-example" {
+; CHECK-LABEL: test3
+; CHECK: load
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: ret <2 x i64 addrspace(1)*> %7
+; When a statepoint is an invoke rather than a call
+entry:
+  %obj = load <2 x i64 addrspace(1)*>, <2 x i64 addrspace(1)*>* %ptr
+  call void @do_safepoint() [ "deopt"() ]
+  ret <2 x i64 addrspace(1)*> %obj
+}
+
+declare i32 @fake_personality_function()
+
+define <2 x i64 addrspace(1)*> @test4(<2 x i64 addrspace(1)*>* %ptr) gc "statepoint-example" personality i32 ()* @fake_personality_function {
+; CHECK-LABEL: test4
+; CHECK: load
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: gc.statepoint
+entry:
+  %obj = load <2 x i64 addrspace(1)*>, <2 x i64 addrspace(1)*>* %ptr
+  invoke void @do_safepoint() [ "deopt"() ]
+          to label %normal_return unwind label %exceptional_return
+
+normal_return:                                    ; preds = %entry
+; CHECK-LABEL: normal_return:
+; CHECK: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: ret <2 x i64 addrspace(1)*> %7
+  ret <2 x i64 addrspace(1)*> %obj
+
+exceptional_return:                               ; preds = %entry
+; CHECK-LABEL: exceptional_return:
+; CHECK: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: ret <2 x i64 addrspace(1)*> %13
+; Can we handle an insert element with a constant offset?  This effectively
+; tests both the equal and inequal case since we have to relocate both indices
+; in the vector.
+  %landing_pad4 = landingpad { i8*, i32 }
+          cleanup
+  ret <2 x i64 addrspace(1)*> %obj
+}
+
+define <2 x i64 addrspace(1)*> @test5(i64 addrspace(1)* %p) gc "statepoint-example" {
+; CHECK-LABEL: test5
+; CHECK: insertelement
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: ret <2 x i64 addrspace(1)*> %7
+; A base vector from a load
+entry:
+  %vec = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %p, i32 0
+  call void @do_safepoint() [ "deopt"() ]
+  ret <2 x i64 addrspace(1)*> %vec
+}
+
+define <2 x i64 addrspace(1)*> @test6(i1 %cnd, <2 x i64 addrspace(1)*>* %ptr) gc "statepoint-example" {
+; CHECK-LABEL: test6
+entry:
+  br i1 %cnd, label %taken, label %untaken
+
+taken:                                            ; preds = %entry
+  %obja = load <2 x i64 addrspace(1)*>, <2 x i64 addrspace(1)*>* %ptr
+  br label %merge
+
+untaken:                                          ; preds = %entry
+  %objb = load <2 x i64 addrspace(1)*>, <2 x i64 addrspace(1)*>* %ptr
+  br label %merge
+
+merge:                                            ; preds = %untaken, %taken
+; CHECK-LABEL: merge:
+; CHECK-NEXT: = phi
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: extractelement
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: insertelement
+; CHECK-NEXT: ret <2 x i64 addrspace(1)*>
+  %obj = phi <2 x i64 addrspace(1)*> [ %obja, %taken ], [ %objb, %untaken ]
+  call void @do_safepoint() [ "deopt"() ]
+  ret <2 x i64 addrspace(1)*> %obj
+}
+
+declare void @do_safepoint()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/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 -rs4gc-use-deopt-bundles -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
+
+taken:                                            ; preds = %entry
+; CHECK-LABEL: taken:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: br label %merge
+  call void @foo() [ "deopt"() ]
+  br label %merge
+
+untaken:                                          ; preds = %entry
+; CHECK-LABEL: untaken:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated2 = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: br label %merge
+  call void @foo() [ "deopt"() ]
+  br label %merge
+
+merge:                                            ; preds = %untaken, %taken
+; CHECK-LABEL: merge:
+; CHECK-NEXT: %.0 = phi i64 addrspace(1)* [ %obj.relocated.casted, %taken ], [ %obj.relocated2.casted, %untaken ]
+; CHECK-NEXT: ret i64 addrspace(1)* %.0
+; A local kill should not effect liveness in predecessor block
+  ret i64 addrspace(1)* %obj
+}
+
+define i64 addrspace(1)* @test2(i1 %cmp, i64 addrspace(1)** %loc) gc "statepoint-example" {
+; CHECK-LABEL: @test2
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT:  gc.statepoint
+; CHECK-NEXT:  br
+  call void @foo() [ "deopt"() ]
+  br i1 %cmp, label %taken, label %untaken
+
+taken:                                            ; preds = %entry
+; CHECK-LABEL: taken:
+; CHECK-NEXT:  %obj = load
+; CHECK-NEXT:  gc.statepoint
+; CHECK-NEXT:  gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT:  ret i64 addrspace(1)* %obj.relocated.casted
+; A local kill should effect values live from a successor phi.  Also, we
+; should only propagate liveness from a phi to the appropriate predecessors.
+  %obj = load i64 addrspace(1)*, i64 addrspace(1)** %loc
+  call void @foo() [ "deopt"() ]
+  ret i64 addrspace(1)* %obj
+
+untaken:                                          ; preds = %entry
+  ret i64 addrspace(1)* null
+}
+
+define i64 addrspace(1)* @test3(i1 %cmp, i64 addrspace(1)** %loc) gc "statepoint-example" {
+; CHECK-LABEL: @test3
+entry:
+  br i1 %cmp, label %taken, label %untaken
+
+taken:                                            ; preds = %entry
+; CHECK-LABEL: taken:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj = load
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: br label %merge
+  call void @foo() [ "deopt"() ]
+  %obj = load i64 addrspace(1)*, i64 addrspace(1)** %loc
+  call void @foo() [ "deopt"() ]
+  br label %merge
+
+untaken:                                          ; preds = %entry
+; CHECK-LABEL: taken:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: br label %merge
+; A base pointer must be live if it is needed at a later statepoint,
+; even if the base pointer is otherwise unused.
+  call void @foo() [ "deopt"() ]
+  br label %merge
+
+merge:                                            ; preds = %untaken, %taken
+  %phi = phi i64 addrspace(1)* [ %obj, %taken ], [ null, %untaken ]
+  ret i64 addrspace(1)* %phi
+}
+
+define i64 addrspace(1)* @test4(i1 %cmp, i64 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test4
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT:  %derived = getelementptr
+; CHECK-NEXT:  gc.statepoint
+; CHECK-NEXT:  %derived.relocated =
+; CHECK-NEXT:  bitcast 
+; CHECK-NEXT:  %obj.relocated =
+; CHECK-NEXT:  bitcast
+; CHECK-NEXT:  gc.statepoint
+; CHECK-NEXT:  %derived.relocated2 =
+; CHECK-NEXT:  bitcast 
+
+; Note: It's legal to relocate obj again, but not strictly needed
+; CHECK-NEXT:  %obj.relocated3 =
+; CHECK-NEXT:  bitcast
+; CHECK-NEXT:  ret i64 addrspace(1)* %derived.relocated2.casted
+; 
+; Make sure that a phi def visited during iteration is considered a kill.
+; Also, liveness after base pointer analysis can change based on new uses,
+; not just new defs.
+  %derived = getelementptr i64, i64 addrspace(1)* %obj, i64 8
+  call void @foo() [ "deopt"() ]
+  call void @foo() [ "deopt"() ]
+  ret i64 addrspace(1)* %derived
+}
+
+declare void @consume(...) readonly "gc-leaf-function"
+
+define i64 addrspace(1)* @test5(i1 %cmp, i64 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test5
+entry:
+  br i1 %cmp, label %taken, label %untaken
+
+taken:                                            ; preds = %entry
+; CHECK-LABEL: taken:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: br label %merge
+  call void @foo() [ "deopt"() ]
+  br label %merge
+
+untaken:                                          ; preds = %entry
+; CHECK-LABEL: untaken:
+; CHECK-NEXT: br label %merge
+  br label %merge
+
+merge:                                            ; preds = %untaken, %taken
+; CHECK-LABEL: merge:
+; CHECK-NEXT: %.0 = phi i64 addrspace(1)*
+; CHECK-NEXT: %obj2a = phi
+; CHECK-NEXT: @consume
+; CHECK-NEXT: br label %final
+  %obj2a = phi i64 addrspace(1)* [ %obj, %taken ], [ null, %untaken ]
+  call void (...) @consume(i64 addrspace(1)* %obj2a)
+  br label %final
+
+final:                                            ; preds = %merge
+; CHECK-LABEL: final:
+; CHECK-NEXT: @consume
+; CHECK-NEXT: ret i64 addrspace(1)* %.0
+  call void (...) @consume(i64 addrspace(1)* %obj2a)
+  ret i64 addrspace(1)* %obj
+}
+
+declare void @foo()
+

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/preprocess.ll

+; RUN: opt -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -S < %s | FileCheck %s
+
+; Test to make sure we destroy LCSSA's single entry phi nodes before
+; running liveness
+
+declare void @consume(...) "gc-leaf-function"
+
+define void @test6(i64 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test6
+entry:
+  br label %next
+
+next:                                             ; preds = %entry
+; CHECK-LABEL: next:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: @consume(i64 addrspace(1)* %obj.relocated.casted)
+; CHECK-NEXT: @consume(i64 addrspace(1)* %obj.relocated.casted)
+; Need to delete unreachable gc.statepoint call
+  %obj2 = phi i64 addrspace(1)* [ %obj, %entry ]
+  call void @foo() [ "deopt"() ]
+  call void (...) @consume(i64 addrspace(1)* %obj2)
+  call void (...) @consume(i64 addrspace(1)* %obj)
+  ret void
+}
+
+define void @test7() gc "statepoint-example" {
+; CHECK-LABEL: test7
+; CHECK-NOT: gc.statepoint
+; Need to delete unreachable gc.statepoint invoke - tested seperately given
+; a correct implementation could only remove the instructions, not the block
+  ret void
+
+unreached:                                        ; preds = %unreached
+  %obj = phi i64 addrspace(1)* [ null, %unreached ]
+  call void @foo() [ "deopt"() ]
+  call void (...) @consume(i64 addrspace(1)* %obj)
+  br label %unreached
+}
+
+define void @test8() gc "statepoint-example" personality i32 ()* undef {
+; CHECK-LABEL: test8
+; CHECK-NOT: gc.statepoint
+; Bound the last check-not
+  ret void
+
+unreached:                                        ; No predecessors!
+  invoke void @foo() [ "deopt"() ]
+; CHECK-LABEL: @foo
+          to label %normal_return unwind label %exceptional_return
+
+normal_return:                                    ; preds = %unreached
+  ret void
+
+exceptional_return:                               ; preds = %unreached
+  %landing_pad4 = landingpad { i8*, i32 }
+          cleanup
+  ret void
+}
+
+declare void @foo()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/relocate-invoke-result.ll

+
+;; RUN: opt -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -verify -S < %s | FileCheck %s
+;; This test is to verify that RewriteStatepointsForGC correctly relocates values
+;; defined by invoke instruction results. 
+
+declare i64* addrspace(1)* @non_gc_call() "gc-leaf-function"
+
+declare void @gc_call()
+
+declare i32* @fake_personality_function()
+
+define i64* addrspace(1)* @test() gc "statepoint-example" personality i32* ()* @fake_personality_function {
+; CHECK-LABEL: @test(
+
+entry:
+  %obj = invoke i64* addrspace(1)* @non_gc_call()
+          to label %normal_dest unwind label %unwind_dest
+
+unwind_dest:                                      ; preds = %entry
+  %lpad = landingpad { i8*, i32 }
+          cleanup
+  resume { i8*, i32 } undef
+
+normal_dest:                                      ; preds = %entry
+; CHECK: normal_dest:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: %obj.relocated = call coldcc i8 addrspace(1)*
+; CHECK-NEXT: bitcast
+
+  call void @gc_call() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64* addrspace(1)* %obj
+}

llvm/trunk/test/Transforms/RewriteStatepointsForGC/deopt-bundles/relocation.ll

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -spp-rematerialization-threshold=0 -S 2>&1 | FileCheck %s
+
+
+declare void @foo()
+
+declare void @use(...) "gc-leaf-function"
+
+define i64 addrspace(1)* @test1(i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2, i1 %condition) gc "statepoint-example" {
+; CHECK-LABEL: @test1
+; CHECK-DAG: %obj.relocated
+; CHECK-DAG: %obj2.relocated
+entry:
+  call void @foo() [ "deopt"() ]
+  br label %joint
+
+joint:                                            ; preds = %joint2, %entry
+; CHECK-LABEL: joint:
+; CHECK: %phi1 = phi i64 addrspace(1)* [ %obj.relocated.casted, %entry ], [ %obj3, %joint2 ]
+  %phi1 = phi i64 addrspace(1)* [ %obj, %entry ], [ %obj3, %joint2 ]
+  br i1 %condition, label %use, label %joint2
+
+use:                                              ; preds = %joint
+  br label %joint2
+
+joint2:                                           ; preds = %use, %joint
+; CHECK-LABEL: joint2:
+; CHECK: %phi2 = phi i64 addrspace(1)* [ %obj.relocated.casted, %use ], [ %obj2.relocated.casted, %joint ]
+; CHECK: %obj3 = getelementptr i64, i64 addrspace(1)* %obj2.relocated.casted, i32 1
+  %phi2 = phi i64 addrspace(1)* [ %obj, %use ], [ %obj2, %joint ]
+  %obj3 = getelementptr i64, i64 addrspace(1)* %obj2, i32 1
+  br label %joint
+}
+
+declare i64 addrspace(1)* @generate_obj() "gc-leaf-function"
+
+declare void @consume_obj(i64 addrspace(1)*) "gc-leaf-function"
+
+declare i1 @rt() "gc-leaf-function"
+
+define void @test2() gc "statepoint-example" {
+; CHECK-LABEL: @test2
+entry:
+  %obj_init = call i64 addrspace(1)* @generate_obj()
+  %obj = getelementptr i64, i64 addrspace(1)* %obj_init, i32 42
+  br label %loop
+
+loop:                                             ; preds = %loop.backedge, %entry
+; CHECK: loop:
+; CHECK-DAG: [ %obj_init.relocated.casted, %loop.backedge ]
+; CHECK-DAG: [ %obj_init, %entry ]
+; CHECK-DAG: [ %obj.relocated.casted, %loop.backedge ]
+; CHECK-DAG: [ %obj, %entry ]
+; CHECK-NOT: %location = getelementptr i64, i64 addrspace(1)* %obj, i32 %index
+  %index = phi i32 [ 0, %entry ], [ %index.inc, %loop.backedge ]
+  %location = getelementptr i64, i64 addrspace(1)* %obj, i32 %index
+  call void @consume_obj(i64 addrspace(1)* %location)
+  %index.inc = add i32 %index, 1
+  %condition = call i1 @rt()
+  br i1 %condition, label %loop_x, label %loop_y
+
+loop_x:                                           ; preds = %loop
+  br label %loop.backedge
+
+loop.backedge:                                    ; preds = %loop_y, %loop_x
+  call void @do_safepoint() [ "deopt"() ]
+  br label %loop
+
+loop_y:                                           ; preds = %loop
+  br label %loop.backedge
+}
+
+declare void @some_call(i8 addrspace(1)*) "gc-leaf-function"
+
+define void @relocate_merge(i1 %cnd, i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: @relocate_merge
+
+bci_0:
+  br i1 %cnd, label %if_branch, label %else_branch
+
+if_branch:                                        ; preds = %bci_0
+; CHECK-LABEL: if_branch:
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+  call void @foo() [ "deopt"() ]
+  br label %join
+
+else_branch:                                      ; preds = %bci_0
+; CHECK-LABEL: else_branch:
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+; We need to end up with a single relocation phi updated from both paths 
+  call void @foo() [ "deopt"() ]
+  br label %join
+
+join:                                             ; preds = %else_branch, %if_branch
+; CHECK-LABEL: join:
+; CHECK: phi i8 addrspace(1)*
+; CHECK-DAG: [ %arg.relocated, %if_branch ]
+; CHECK-DAG: [ %arg.relocated2, %else_branch ]
+; CHECK-NOT: phi
+  call void @some_call(i8 addrspace(1)* %arg)
+  ret void
+}
+
+; Make sure a use in a statepoint gets properly relocated at a previous one.  
+; This is basically just making sure that statepoints aren't accidentally 
+; treated specially.
+define void @test3(i64 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test3
+; CHECK: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: bitcast
+; CHECK-NEXT: gc.statepoint
+entry:
+  call void undef(i64 undef) [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  %0 = call i32 undef(i64 addrspace(1)* %obj) [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret void
+}
+
+; Check specifically for the case where the result of a statepoint needs to 
+; be relocated itself
+define void @test4() gc "statepoint-example" {
+; CHECK-LABEL: @test4
+; CHECK: gc.statepoint
+; CHECK: gc.result
+; CHECK: gc.statepoint
+; CHECK: [[RELOCATED:%[^ ]+]] = call {{.*}}gc.relocate
+; CHECK: @use(i8 addrspace(1)* [[RELOCATED]])
+  %1 = call i8 addrspace(1)* undef() [ "deopt"() ]
+  %2 = call i8 addrspace(1)* undef() [ "deopt"() ]
+  call void (...) @use(i8 addrspace(1)* %1)
+  unreachable
+}
+
+; Test updating a phi where not all inputs are live to begin with
+define void @test5(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: test5
+entry:
+  %0 = call i8 addrspace(1)* undef() [ "deopt"() ]
+  switch i32 undef, label %kill [
+    i32 10, label %merge
+    i32 13, label %merge
+  ]
+
+kill:                                             ; preds = %entry
+  br label %merge
+
+merge:                                            ; preds = %kill, %entry, %entry
+; CHECK: merge:
+; CHECK: %test = phi i8 addrspace(1)
+; CHECK-DAG: [ null, %kill ]
+; CHECK-DAG: [ %arg.relocated, %entry ]
+; CHECK-DAG: [ %arg.relocated, %entry ]
+  %test = phi i8 addrspace(1)* [ null, %kill ], [ %arg, %entry ], [ %arg, %entry ]
+  call void (...) @use(i8 addrspace(1)* %test)
+  unreachable
+}
+
+; Check to make sure we handle values live over an entry statepoint
+define void @test6(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2, i8 addrspace(1)* %arg3) gc "statepoint-example" {
+; CHECK-LABEL: @test6
+entry:
+  br i1 undef, label %gc.safepoint_poll.exit2, label %do_safepoint
+
+do_safepoint:                                     ; preds = %entry
+; CHECK-LABEL: do_safepoint:
+; CHECK: gc.statepoint
+; CHECK: arg1.relocated = 
+; CHECK: arg2.relocated = 
+; CHECK: arg3.relocated = 
+  call void @foo() [ "deopt"(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2, i8 addrspace(1)* %arg3) ]
+  br label %gc.safepoint_poll.exit2
+
+gc.safepoint_poll.exit2:                          ; preds = %do_safepoint, %entry
+; CHECK-LABEL: gc.safepoint_poll.exit2:
+; CHECK: phi i8 addrspace(1)*
+; CHECK-DAG: [ %arg3, %entry ]
+; CHECK-DAG: [ %arg3.relocated, %do_safepoint ]
+; CHECK: phi i8 addrspace(1)*
+; CHECK-DAG: [ %arg2, %entry ]
+; CHECK-DAG: [ %arg2.relocated, %do_safepoint ]
+; CHECK: phi i8 addrspace(1)*
+; CHECK-DAG: [ %arg1, %entry ]
+; CHECK-DAG:  [ %arg1.relocated, %do_safepoint ]
+  call void (...) @use(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2, i8 addrspace(1)* %arg3)
+  ret void
+}
+
+; Check relocation in a loop nest where a relocation happens in the outer
+; but not the inner loop
+define void @test_outer_loop(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2, i1 %cmp) gc "statepoint-example" {
+; CHECK-LABEL: @test_outer_loop
+
+bci_0:
+  br label %outer-loop
+
+outer-loop:                                       ; preds = %outer-inc, %bci_0
+; CHECK-LABEL: outer-loop:
+; CHECK: phi i8 addrspace(1)* [ %arg2, %bci_0 ], [ %arg2.relocated, %outer-inc ]
+; CHECK: phi i8 addrspace(1)* [ %arg1, %bci_0 ], [ %arg1.relocated, %outer-inc ]
+  br label %inner-loop
+
+inner-loop:                                       ; preds = %inner-loop, %outer-loop
+  br i1 %cmp, label %inner-loop, label %outer-inc
+
+outer-inc:                                        ; preds = %inner-loop
+; CHECK-LABEL: outer-inc:
+; CHECK: %arg1.relocated
+; CHECK: %arg2.relocated
+  call void @foo() [ "deopt"(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2) ]
+  br label %outer-loop
+}
+
+; Check that both inner and outer loops get phis when relocation is in
+;  inner loop
+define void @test_inner_loop(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2, i1 %cmp) gc "statepoint-example" {
+; CHECK-LABEL: @test_inner_loop
+
+bci_0:
+  br label %outer-loop
+
+outer-loop:                                       ; preds = %outer-inc, %bci_0
+; CHECK-LABEL: outer-loop:
+; CHECK: phi i8 addrspace(1)* [ %arg2, %bci_0 ], [ %arg2.relocated, %outer-inc ]
+; CHECK: phi i8 addrspace(1)* [ %arg1, %bci_0 ], [ %arg1.relocated, %outer-inc ]
+  br label %inner-loop
+; CHECK-LABEL: inner-loop
+; CHECK: phi i8 addrspace(1)* 
+; CHECK-DAG: %outer-loop ]
+; CHECK-DAG: [ %arg2.relocated, %inner-loop ]
+; CHECK: phi i8 addrspace(1)* 
+; CHECK-DAG: %outer-loop ]
+; CHECK-DAG: [ %arg1.relocated, %inner-loop ]
+; CHECK: gc.statepoint
+; CHECK: %arg1.relocated
+; CHECK: %arg2.relocated
+
+inner-loop:                                       ; preds = %inner-loop, %outer-loop
+  call void @foo() [ "deopt"(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2) ]
+  br i1 %cmp, label %inner-loop, label %outer-inc
+
+outer-inc:                                        ; preds = %inner-loop
+; CHECK-LABEL: outer-inc:
+; This test shows why updating just those uses of the original value being
+; relocated dominated by the inserted relocation is not always sufficient.
+  br label %outer-loop
+}
+
+define i64 addrspace(1)* @test7(i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2, i1 %condition) gc "statepoint-example" {
+; CHECK-LABEL: @test7
+entry:
+  br i1 %condition, label %branch2, label %join
+
+branch2:                                          ; preds = %entry
+  br i1 %condition, label %callbb, label %join2
+
+callbb:                                           ; preds = %branch2
+  call void @foo() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  br label %join
+
+join:                                             ; preds = %callbb, %entry
+; CHECK-LABEL: join:
+; CHECK: phi i64 addrspace(1)* [ %obj.relocated.casted, %callbb ], [ %obj, %entry ]
+; CHECK: phi i64 addrspace(1)* 
+; CHECK-DAG: [ %obj, %entry ]
+; CHECK-DAG: [ %obj2.relocated.casted, %callbb ]
+  %phi1 = phi i64 addrspace(1)* [ %obj, %entry ], [ %obj2, %callbb ]
+  br label %join2
+
+join2:                                            ; preds = %join, %branch2
+; CHECK-LABEL: join2:
+; CHECK: phi2 = phi i64 addrspace(1)* 
+; CHECK-DAG: %join ] 
+; CHECK-DAG:  [ %obj2, %branch2 ]
+  %phi2 = phi i64 addrspace(1)* [ %obj, %join ], [ %obj2, %branch2 ]
+  ret i64 addrspace(1)* %phi2
+}
+
+declare void @do_safepoint()

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

+; RUN: opt %s -rewrite-statepoints-for-gc -rs4gc-use-deopt-bundles -S 2>&1 | FileCheck %s
+
+
+declare void @use_obj16(i16 addrspace(1)*) "gc-leaf-function"
+declare void @use_obj32(i32 addrspace(1)*) "gc-leaf-function"
+declare void @use_obj64(i64 addrspace(1)*) "gc-leaf-function"
+
+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
+  call void @do_safepoint() [ "deopt"() ]
+  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
+  call void @do_safepoint() [ "deopt"() ]
+  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)*
+  call void @do_safepoint() [ "deopt"() ]
+  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
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep to i64 addrspace(1)*
+  call void @do_safepoint() [ "deopt"() ]
+  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
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep to i64 addrspace(1)*
+  %ptr.cast2 = bitcast i32 addrspace(1)* %ptr.gep to i16 addrspace(1)*
+  call void @do_safepoint() [ "deopt"() ]
+  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
+  %ptr.gep2 = getelementptr i32, i32 addrspace(1)* %ptr.gep, i32 %idx1
+  %ptr.gep3 = getelementptr i32, i32 addrspace(1)* %ptr.gep2, i32 %idx2
+  %ptr.gep4 = getelementptr i32, i32 addrspace(1)* %ptr.gep3, i32 %idx3
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep4 to i64 addrspace(1)*
+  call void @do_safepoint() [ "deopt"() ]
+  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
+  call void @do_safepoint() [ "deopt"() ]
+  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
+  call void @do_safepoint() [ "deopt"() ]
+  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" personality i32 ()* @fake_personality_function {
+; CHECK-LABEL: test_invoke
+entry:
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep to i64 addrspace(1)*
+  %ptr.cast2 = bitcast i32 addrspace(1)* %ptr.gep to i16 addrspace(1)*
+  invoke void @do_safepoint() [ "deopt"() ]
+          to label %normal unwind label %exception
+
+normal:                                           ; preds = %entry
+  call void @use_obj64(i64 addrspace(1)* %ptr.cast)
+  call void @use_obj16(i16 addrspace(1)* %ptr.cast2)
+  ret void
+
+exception:                                        ; preds = %entry
+  %landing_pad4 = landingpad { i8*, i32 }
+          cleanup
+  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
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  call void @use_obj32(i32 addrspace(1)* %ptr.gep)
+  call void @do_safepoint() [ "deopt"() ]
+  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
+  call void @do_safepoint() [ "deopt"() ]
+  call void @use_obj32(i32 addrspace(1)* %ptr.gep11)
+  ret void
+}