Add verifier pass for finding GC relocation bugs

[anna]

Summary

Original Patch and summary by Philip Reames.

RewriteStatepointsForGC tries to rewrite a function in a manner where the optimizer can't end up using a pointer value after it might have been relocated by a safepoint. This pass checks the invariant that RSForGC is supposed to establish and that (if we constructed semantics correctly) later passes must preserve.

This has been a really useful diagnostic tool when initially developing the rewriting scheme and has found numerous bugs. Manuel recently pointed out that this had never gotten upstreamed. Given both Manuel and the Microsoft team are in the process of trying to ramp up both the amount of IR being fed through and the optimization passes run, it seems useful to have this available for them as well. Manuel in particular has already found and fixed a couple of relocation bugs the hard way.

In terms of placement and structure, I left this in the IR directory which is where we'd happened to drop it in our tree. I could see an argument that this should be in either Analysis or possibly Transform. I'm happy to move it if anyone has a preference.

[swaroop.sridhar]

Thanks for adding the IR checker.
My preference is for keeping it within the Analysis (rather than IR) tree.

[mjacob]

I'm fine if this lives in the IR directory, next to Verifier.

Please change the function names to start with a lowercase letter.

[mjacob]

Have you run clang-format on the source code? I saw some consecutive empty lines which should be removed by clang-format?

lib/IR/SafepointIRVerifier.cpp

77 ↗

(On Diff #44168)

This is already implied by AU.setPreservesAll();

190 ↗

(On Diff #44168)

Can you restate this comment, so it tells me what it is for instead of which funtion it calls?

223–224 ↗

(On Diff #44168)

I think this should be in a DEBUG(...) and not guarded by PrintOnly.

[mjacob]

ping

I have have patches which make the verifier accept the "non-constant GC pointer with constant base" case. Should I submit them for review after this patch here is committed?

[anna]

Taking this over from Philip. Will address the review comments.
Looks like there's conflicting opinion about where to place this - in the IR directory next to verifier, or in the analysis directory.
I prefer keeping it in the IR directory itself if no one has objections.

[anna]

lib/IR/SafepointIRVerifier.cpp

223–224 ↗

(On Diff #44168)

I've added a DEBUG as well as a separate statement. We need PrintOnly guard as part of testing.

llvm/trunk/include/llvm/IR/SafepointIRVerifier.h

+//===- SafepointIRVerifier.h - Checks for GC relocation problems *- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a verifier which is useful for enforcing the relocation
+// properties required by a relocating GC.  Specifically, it looks for uses of
+// the unrelocated value of pointer SSA values after a possible safepoint. It
+// attempts to report no false negatives, but may end up reporting false
+// positives in rare cases (see the note at the top of the corresponding cpp
+// file.)
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_SAFEPOINT_IR_VERIFIER
+#define LLVM_IR_SAFEPOINT_IR_VERIFIER
+
+namespace llvm {
+
+class Function;
+class FunctionPass;
+
+/// Run the safepoint verifier over a single function.  Crashes on failure.
+void verifySafepointIR(Function &F);
+
+/// Create an instance of the safepoint verifier pass which can be added to
+/// a pass pipeline to check for relocation bugs.
+FunctionPass *createSafepointIRVerifierPass();
+}
+
+#endif // LLVM_IR_SAFEPOINT_IR_VERIFIER

llvm/trunk/include/llvm/InitializePasses.h

 void initializeRegionPrinterPass(PassRegistry&);
 void initializeRegionViewerPass(PassRegistry&);
 void initializeRegisterCoalescerPass(PassRegistry&);
 void initializeRenameIndependentSubregsPass(PassRegistry&);
 void initializeResetMachineFunctionPass(PassRegistry&);
 void initializeReversePostOrderFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeRewriteStatepointsForGCPass(PassRegistry&);
 void initializeRewriteSymbolsLegacyPassPass(PassRegistry&);
+void initializeSafepointIRVerifierPass(PassRegistry&);
 void initializeSCCPLegacyPassPass(PassRegistry&);
 void initializeSCEVAAWrapperPassPass(PassRegistry&);
 void initializeSLPVectorizerPass(PassRegistry&);
 void initializeSROALegacyPassPass(PassRegistry&);
 void initializeSafeStackLegacyPassPass(PassRegistry&);
 void initializeSampleProfileLoaderLegacyPassPass(PassRegistry&);
 void initializeSanitizerCoverageModulePass(PassRegistry&);
 void initializeScalarEvolutionWrapperPassPass(PassRegistry&);

llvm/trunk/lib/IR/CMakeLists.txt

add_llvm_library(LLVMCore
   Metadata.cpp
   Module.cpp
   ModuleSummaryIndex.cpp
   Operator.cpp
   OptBisect.cpp
   Pass.cpp
   PassManager.cpp
   PassRegistry.cpp
+  SafepointIRVerifier.cpp
   ProfileSummary.cpp
   Statepoint.cpp
   Type.cpp
   TypeFinder.cpp
   Use.cpp
   User.cpp
   Value.cpp
   ValueSymbolTable.cpp

llvm/trunk/lib/IR/Core.cpp

 
 #define DEBUG_TYPE "ir"
 
 void llvm::initializeCore(PassRegistry &Registry) {
   initializeDominatorTreeWrapperPassPass(Registry);
   initializePrintModulePassWrapperPass(Registry);
   initializePrintFunctionPassWrapperPass(Registry);
   initializePrintBasicBlockPassPass(Registry);
+  initializeSafepointIRVerifierPass(Registry);
   initializeVerifierLegacyPassPass(Registry);
 }
 
 void LLVMInitializeCore(LLVMPassRegistryRef R) {
   initializeCore(*unwrap(R));
 }
 
 void LLVMShutdown() {

llvm/trunk/lib/IR/SafepointIRVerifier.cpp

+//===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Run a sanity check on the IR to ensure that Safepoints - if they've been
+// inserted - were inserted correctly.  In particular, look for use of
+// non-relocated values after a safepoint.  It's primary use is to check the
+// correctness of safepoint insertion immediately after insertion, but it can
+// also be used to verify that later transforms have not found a way to break
+// safepoint semenatics.
+//
+// In its current form, this verify checks a property which is sufficient, but
+// not neccessary for correctness.  There are some cases where an unrelocated
+// pointer can be used after the safepoint.  Consider this example:
+//
+//    a = ...
+//    b = ...
+//    (a',b') = safepoint(a,b)
+//    c = cmp eq a b
+//    br c, ..., ....
+//
+// Because it is valid to reorder 'c' above the safepoint, this is legal.  In
+// practice, this is a somewhat uncommon transform, but CodeGenPrep does create
+// idioms like this.  Today, the verifier would report a spurious failure on
+// this case.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SetOperations.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Value.h"
+#include "llvm/IR/SafepointIRVerifier.h"
+#include "llvm/IR/Statepoint.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/raw_ostream.h"
+
+#define DEBUG_TYPE "safepoint-ir-verifier"
+
+using namespace llvm;
+
+/// This option is used for writing test cases.  Instead of crashing the program
+/// when verification fails, report a message to the console (for FileCheck
+/// usage) and continue execution as if nothing happened.
+static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
+                               cl::init(false));
+
+static void Verify(const Function &F, const DominatorTree &DT);
+
+struct SafepointIRVerifier : public FunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+  DominatorTree DT;
+  SafepointIRVerifier() : FunctionPass(ID) {
+    initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    DT.recalculate(F);
+    Verify(F, DT);
+    return false; // no modifications
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+
+  StringRef getPassName() const override { return "safepoint verifier"; }
+};
+
+void llvm::verifySafepointIR(Function &F) {
+  SafepointIRVerifier pass;
+  pass.runOnFunction(F);
+}
+
+char SafepointIRVerifier::ID = 0;
+
+FunctionPass *llvm::createSafepointIRVerifierPass() {
+  return new SafepointIRVerifier();
+}
+
+INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
+                      "Safepoint IR Verifier", false, true)
+INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
+                    "Safepoint IR Verifier", false, true)
+
+static bool isGCPointerType(Type *T) {
+  if (auto *PT = dyn_cast<PointerType>(T))
+    // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
+    // GC managed heap.  We know that a pointer into this heap needs to be
+    // updated and that no other pointer does.
+    return (1 == PT->getAddressSpace());
+  return false;
+}
+
+static bool containsGCPtrType(Type *Ty) {
+  if (isGCPointerType(Ty))
+    return true;
+  if (VectorType *VT = dyn_cast<VectorType>(Ty))
+    return isGCPointerType(VT->getScalarType());
+  if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
+    return containsGCPtrType(AT->getElementType());
+  if (StructType *ST = dyn_cast<StructType>(Ty))
+    return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
+                       containsGCPtrType);
+  return false;
+}
+
+// Debugging aid -- prints a [Begin, End) range of values.
+template<typename IteratorTy>
+static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
+  OS << "[ ";
+  while (Begin != End) {
+    OS << **Begin << " ";
+    ++Begin;
+  }
+  OS << "]";
+}
+
+/// The verifier algorithm is phrased in terms of availability.  The set of
+/// values "available" at a given point in the control flow graph is the set of
+/// correctly relocated value at that point, and is a subset of the set of
+/// definitions dominating that point.
+
+/// State we compute and track per basic block.
+struct BasicBlockState {
+  // Set of values available coming in, before the phi nodes
+  DenseSet<const Value *> AvailableIn;
+
+  // Set of values available going out
+  DenseSet<const Value *> AvailableOut;
+
+  // AvailableOut minus AvailableIn.
+  // All elements are Instructions
+  DenseSet<const Value *> Contribution;
+
+  // True if this block contains a safepoint and thus AvailableIn does not
+  // contribute to AvailableOut.
+  bool Cleared = false;
+};
+
+
+/// Gather all the definitions dominating the start of BB into Result.  This is
+/// simply the Defs introduced by every dominating basic block and the function
+/// arguments.
+static void GatherDominatingDefs(const BasicBlock *BB,
+                                 DenseSet<const Value *> &Result,
+                                 const DominatorTree &DT,
+                    DenseMap<const BasicBlock *, BasicBlockState *> &BlockMap) {
+  DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
+
+  while (DTN->getIDom()) {
+    DTN = DTN->getIDom();
+    const auto &Defs = BlockMap[DTN->getBlock()]->Contribution;
+    Result.insert(Defs.begin(), Defs.end());
+    // If this block is 'Cleared', then nothing LiveIn to this block can be
+    // available after this block completes.  Note: This turns out to be 
+    // really important for reducing memory consuption of the initial available
+    // sets and thus peak memory usage by this verifier.
+    if (BlockMap[DTN->getBlock()]->Cleared)
+      return;
+  }
+
+  for (const Argument &A : BB->getParent()->args())
+    if (containsGCPtrType(A.getType()))
+      Result.insert(&A);
+}
+
+/// Model the effect of an instruction on the set of available values.
+static void TransferInstruction(const Instruction &I, bool &Cleared,
+                              DenseSet<const Value *> &Available) {
+  if (isStatepoint(I)) {
+    Cleared = true;
+    Available.clear();
+  } else if (containsGCPtrType(I.getType()))
+    Available.insert(&I);
+}
+
+/// Compute the AvailableOut set for BB, based on the
+/// BasicBlockState BBS, which is the BasicBlockState for BB. FirstPass is set
+/// when the verifier runs for the first time computing the AvailableOut set
+/// for BB.
+static void TransferBlock(const BasicBlock *BB,
+                          BasicBlockState &BBS, bool FirstPass) {
+
+  const DenseSet<const Value *> &AvailableIn = BBS.AvailableIn; 
+  DenseSet<const Value *> &AvailableOut  = BBS.AvailableOut;
+
+  if (BBS.Cleared) {
+    // AvailableOut does not change no matter how the input changes, just
+    // leave it be.  We need to force this calculation the first time so that
+    // we have a AvailableOut at all.
+    if (FirstPass) {
+      AvailableOut = BBS.Contribution;
+    }
+  } else {
+    // Otherwise, we need to reduce the AvailableOut set by things which are no
+    // longer in our AvailableIn
+    DenseSet<const Value *> Temp = BBS.Contribution;
+    set_union(Temp, AvailableIn);
+    AvailableOut = std::move(Temp);
+  }
+
+  DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
+        PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
+        dbgs() << " to ";
+        PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
+        dbgs() << "\n";);
+}
+
+/// Return true if V is exclusively derived off a constant base, i.e. all
+/// operands of non-unary operators (phi/select) are derived off a constant
+/// base.
+static bool
+isExclusivelyConstantDerivedRecursive(const Value *V,
+                                      DenseSet<const Value *> &Visited) {
+  if (!Visited.insert(V).second)
+    return true;
+
+  if (isa<Constant>(V))
+    return true;
+
+  if (const auto *CI = dyn_cast<CastInst>(V))
+    return isExclusivelyConstantDerivedRecursive(CI->stripPointerCasts(),
+                                                 Visited);
+
+  if (const auto *GEP = dyn_cast<GetElementPtrInst>(V))
+    return isExclusivelyConstantDerivedRecursive(GEP->getPointerOperand(),
+                                                 Visited);
+
+  // All operands of the phi and select nodes should be derived off a constant
+  // base.
+  if (const auto *PN = dyn_cast<PHINode>(V)) {
+    return all_of(PN->incoming_values(), [&](const Value *InV) {
+      return isExclusivelyConstantDerivedRecursive(InV, Visited);
+    });
+  }
+
+  if (const auto *SI = dyn_cast<SelectInst>(V))
+    return isExclusivelyConstantDerivedRecursive(SI->getTrueValue(), Visited) &&
+           isExclusivelyConstantDerivedRecursive(SI->getFalseValue(), Visited);
+
+  return false;
+}
+
+static bool isExclusivelyConstantDerived(const Value *V) {
+  DenseSet<const Value*> Visited;
+  return isExclusivelyConstantDerivedRecursive(V, Visited);
+}
+
+static void Verify(const Function &F, const DominatorTree &DT) {
+  SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
+  DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
+ 
+  DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n");
+  if (PrintOnly)
+    dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
+
+
+  for (const BasicBlock &BB : F) {
+    BasicBlockState *BBS = new(BSAllocator.Allocate()) BasicBlockState;
+    for (const auto &I : BB)
+      TransferInstruction(I, BBS->Cleared, BBS->Contribution);
+    BlockMap[&BB] = BBS;
+  }
+
+  for (auto &BBI : BlockMap) {
+    GatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT, BlockMap);
+    TransferBlock(BBI.first, *BBI.second, true);
+  }
+
+  SetVector<const BasicBlock *> Worklist;
+  for (auto &BBI : BlockMap)
+    Worklist.insert(BBI.first);
+
+  // This loop iterates the AvailableIn and AvailableOut sets to a fixed point.
+  // The AvailableIn and AvailableOut sets decrease as we iterate.
+  while (!Worklist.empty()) {
+    const BasicBlock *BB = Worklist.pop_back_val();
+    BasicBlockState *BBS = BlockMap[BB];
+
+    size_t OldInCount = BBS->AvailableIn.size();
+    for (const BasicBlock *PBB : predecessors(BB))
+      set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
+
+    if (OldInCount == BBS->AvailableIn.size())
+      continue;
+
+    assert(OldInCount > BBS->AvailableIn.size() && "invariant!");
+
+    size_t OldOutCount = BBS->AvailableOut.size();
+    TransferBlock(BB, *BBS, false);
+    if (OldOutCount != BBS->AvailableOut.size()) {
+      assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
+      Worklist.insert(succ_begin(BB), succ_end(BB));
+    }
+  }
+
+  // We now have all the information we need to decide if the use of a heap
+  // reference is legal or not, given our safepoint semantics.
+
+  bool AnyInvalidUses = false;
+
+  auto ReportInvalidUse = [&AnyInvalidUses](const Value &V,
+                                            const Instruction &I) {
+    errs() << "Illegal use of unrelocated value found!\n";
+    errs() << "Def: " << V << "\n";
+    errs() << "Use: " << I << "\n";
+    if (!PrintOnly)
+      abort();
+    AnyInvalidUses = true;
+  };
+
+  for (const BasicBlock &BB : F) {
+    // We destructively modify AvailableIn as we traverse the block instruction
+    // by instruction.
+    DenseSet<const Value *> &AvailableSet = BlockMap[&BB]->AvailableIn;
+    for (const Instruction &I : BB) {
+      if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
+        if (containsGCPtrType(PN->getType()))
+          for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+            const BasicBlock *InBB = PN->getIncomingBlock(i);
+            const Value *InValue = PN->getIncomingValue(i);
+
+            if (!isExclusivelyConstantDerived(InValue) &&
+                !BlockMap[InBB]->AvailableOut.count(InValue))
+              ReportInvalidUse(*InValue, *PN);
+          }
+      } else {
+        for (const Value *V : I.operands())
+          if (containsGCPtrType(V->getType()) &&
+              !isExclusivelyConstantDerived(V) && !AvailableSet.count(V))
+            ReportInvalidUse(*V, I);
+      }
+
+      bool Cleared = false;
+      TransferInstruction(I, Cleared, AvailableSet);
+      (void)Cleared;
+    }
+  }
+
+  if (PrintOnly && !AnyInvalidUses) {
+    dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
+           << "\n";
+  }
+}

llvm/trunk/test/SafepointIRVerifier/basic-use-after-reloc.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+; This test checks that if a value is used immediately after a
+; safepoint without using the relocated value that the verifier
+; catches this.
+
+%jObject = type { [8 x i8] }
+
+; Function Attrs: nounwind
+define %jObject addrspace(1)* @test(%jObject addrspace(1)* %arg) gc "statepoint-example" {
+bci_0:
+  %safepoint_token3 = tail call token (i64, i32, double (double)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_f64f64f(i64 0, i32 0, double (double)* undef, i32 1, i32 0, double undef, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, %jObject addrspace(1)* %arg)
+  %arg2.relocated4 = call coldcc %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token %safepoint_token3, i32 13, i32 13)
+  ret %jObject addrspace(1)* %arg
+; CHECK: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def: %jObject addrspace(1)* %arg
+; CHECK-NEXT: Use:   ret %jObject addrspace(1)* %arg
+}
+
+; Function Attrs: nounwind
+declare %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token, i32, i32) #3
+
+declare token @llvm.experimental.gc.statepoint.p0f_f64f64f(i64, i32, double (double)*, i32, i32, ...)

llvm/trunk/test/SafepointIRVerifier/constant-bases.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+define i8 addrspace(1)* @test1(i64 %arg) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test1
+entry:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  ret i8 addrspace(1)* null
+}
+
+define i8 addrspace(1)* @test2(i64 %arg) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test2
+entry:
+  %load_addr = getelementptr i8, i8 addrspace(1)* inttoptr (i64 15 to i8 addrspace(1)*), i64 %arg
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  ret i8 addrspace(1)* %load_addr
+}
+
+define i8 addrspace(1)* @test3(i64 %arg) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test3
+entry:
+  %load_addr = getelementptr i32, i32 addrspace(1)* inttoptr (i64 15 to i32 addrspace(1)*), i64 %arg
+  %load_addr.cast = bitcast i32 addrspace(1)* %load_addr to i8 addrspace(1)*
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  ret i8 addrspace(1)* %load_addr.cast
+}
+
+define i8 addrspace(1)* @test4(i64 %arg, i1 %cond) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test4
+entry:
+  %load_addr.1 = getelementptr i8, i8 addrspace(1)* inttoptr (i64 15 to i8 addrspace(1)*), i64 %arg
+  br i1 %cond, label %split, label %join
+
+split:
+  %load_addr.2 = getelementptr i8, i8 addrspace(1)* inttoptr (i64 30 to i8 addrspace(1)*), i64 %arg
+  br label %join
+
+join:
+  %load_addr = phi i8 addrspace(1)* [%load_addr.1, %entry], [%load_addr.2, %split]
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  ret i8 addrspace(1)* %load_addr
+}
+
+define i8 addrspace(1)* @test5(i64 %arg, i1 %cond) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test5
+entry:
+  %load_addr.1 = getelementptr i8, i8 addrspace(1)* inttoptr (i64 15 to i8 addrspace(1)*), i64 %arg
+  %load_addr.2 = getelementptr i8, i8 addrspace(1)* inttoptr (i64 30 to i8 addrspace(1)*), i64 %arg
+  %load_addr = select i1 %cond, i8 addrspace(1)* %load_addr.1, i8 addrspace(1)* %load_addr.2
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  ret i8 addrspace(1)* %load_addr
+}
+
+define i8 addrspace(1)* @test6(i64 %arg, i1 %cond, i8 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test6
+; CHECK: Illegal use of unrelocated value found!
+entry:
+  %load_addr.1 = getelementptr i8, i8 addrspace(1)* %base, i64 %arg
+  br i1 %cond, label %split, label %join
+
+split:
+  %load_addr.2 = getelementptr i8, i8 addrspace(1)* inttoptr (i64 30 to i8 addrspace(1)*), i64 %arg
+  br label %join
+
+join:
+  %load_addr = phi i8 addrspace(1)* [%load_addr.1, %entry], [%load_addr.2, %split]
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  ret i8 addrspace(1)* %load_addr
+}
+
+declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)

llvm/trunk/test/SafepointIRVerifier/unrecorded-live-at-sp.ll

+; RUN: opt %s -safepoint-ir-verifier-print-only -verify-safepoint-ir -S 2>&1 | FileCheck %s
+
+; CHECK:      Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %base_phi3 = phi %jObject addrspace(1)* [ %obj609.relocated, %not_zero146 ], [ %base_phi2, %bci_37-aload ], !is_base_value !0
+; CHECK-NEXT: Use:   %base_phi2 = phi %jObject addrspace(1)* [ %base_phi3, %not_zero179 ], [ %cast5, %bci_0 ], !is_base_value !0
+
+%jObject = type { [8 x i8] }
+
+declare %jObject addrspace(1)* @generate_obj1() #1
+
+declare %jObject addrspace(1)* addrspace(1)* @generate_obj2() #1
+
+declare %jObject addrspace(1)* @generate_obj3() #1
+
+; Function Attrs: nounwind
+define  void @test(%jObject addrspace(1)*, %jObject addrspace(1)*, i32) #3 gc "statepoint-example" {
+bci_0:
+  %result608 = call %jObject addrspace(1)* @generate_obj3()
+  %obj609 = bitcast %jObject addrspace(1)* %result608 to %jObject addrspace(1)*
+  %cast = bitcast %jObject addrspace(1)* %result608 to %jObject addrspace(1)*
+  %cast5 = bitcast %jObject addrspace(1)* %result608 to %jObject addrspace(1)*
+  br label %bci_37-aload
+
+bci_37-aload:                                     ; preds = %not_zero179, %bci_0
+  %base_phi = phi %jObject addrspace(1)* [ %base_phi1.relocated, %not_zero179 ], [ %cast, %bci_0 ], !is_base_value !0
+  %base_phi2 = phi %jObject addrspace(1)* [ %base_phi3, %not_zero179 ], [ %cast5, %bci_0 ], !is_base_value !0
+  %relocated8 = phi %jObject addrspace(1)* [ %relocated7.relocated, %not_zero179 ], [ %obj609, %bci_0 ]
+  %tmp3 = getelementptr inbounds %jObject, %jObject addrspace(1)* %relocated8, i64 0, i32 0, i64 32
+  %addr98 = bitcast i8 addrspace(1)* %tmp3 to %jObject addrspace(1)* addrspace(1)*
+  %cast6 = bitcast %jObject addrspace(1)* %base_phi2 to %jObject addrspace(1)* addrspace(1)*
+  br i1 undef, label %not_zero179, label %not_zero146
+
+not_zero146:                                      ; preds = %bci_37-aload
+  %addr98.relocated = call %jObject addrspace(1)* addrspace(1)* @generate_obj2() #1
+  %obj609.relocated = call %jObject addrspace(1)* @generate_obj1() #1
+  br label %not_zero179
+
+not_zero179:                                      ; preds = %not_zero146, %bci_37-aload
+  %base_phi1 = phi %jObject addrspace(1)* [ %obj609.relocated, %not_zero146 ], [ %base_phi, %bci_37-aload ], !is_base_value !0
+  %base_phi3 = phi %jObject addrspace(1)* [ %obj609.relocated, %not_zero146 ], [ %base_phi2, %bci_37-aload ], !is_base_value !0
+  %relocated7 = phi %jObject addrspace(1)* [ %obj609.relocated, %not_zero146 ], [ %relocated8, %bci_37-aload ]
+  %base_phi4 = phi %jObject addrspace(1)* addrspace(1)* [ %addr98.relocated, %not_zero146 ], [ %cast6, %bci_37-aload ], !is_base_value !0
+  %relocated4 = phi %jObject addrspace(1)* addrspace(1)* [ %addr98.relocated, %not_zero146 ], [ %addr98, %bci_37-aload ]
+  %safepoint_token = tail call  token (i64, i32, i32 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32f(i64 0, i32 0, i32 ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 0, i32 0, i32 0, i32 0, %jObject addrspace(1)* %base_phi1, %jObject addrspace(1)* addrspace(1)* %base_phi4, %jObject addrspace(1)* addrspace(1)* %relocated4, %jObject addrspace(1)* %relocated7)
+  %tmp4 = call i32 @llvm.experimental.gc.result.i32(token %safepoint_token)
+  %base_phi1.relocated = call coldcc %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token %safepoint_token, i32 12, i32 12)
+  %base_phi4.relocated = call coldcc %jObject addrspace(1)* addrspace(1)* @llvm.experimental.gc.relocate.p1p1jObject(token %safepoint_token, i32 13, i32 13)
+  %relocated4.relocated = call coldcc %jObject addrspace(1)* addrspace(1)* @llvm.experimental.gc.relocate.p1p1jObject(token %safepoint_token, i32 13, i32 14)
+  %relocated7.relocated = call coldcc %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token %safepoint_token, i32 12, i32 15)
+  %addr636 = bitcast %jObject addrspace(1)* addrspace(1)* %relocated4.relocated to %jObject addrspace(1)* addrspace(1)*
+  br label %bci_37-aload
+}
+
+declare token @llvm.experimental.gc.statepoint.p0f_i32f(i64, i32, i32 ()*, i32, i32, ...)
+
+; Function Attrs: nounwind
+declare i32 @llvm.experimental.gc.result.i32(token) #4
+
+; Function Attrs: nounwind
+declare %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token, i32, i32) #4
+
+; Function Attrs: nounwind
+declare %jObject addrspace(1)* addrspace(1)* @llvm.experimental.gc.relocate.p1p1jObject(token, i32, i32) #4
+
+attributes #0 = { noinline nounwind "gc-leaf-function"="true" }
+attributes #1 = { "gc-leaf-function"="true" }
+attributes #2 = { nounwind readonly "gc-leaf-function"="true" }
+attributes #3 = { nounwind }
+attributes #4 = { nounwind }
+
+!0 = !{i32 1}

llvm/trunk/test/SafepointIRVerifier/uses-in-phi-nodes.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+define i8 addrspace(1)* @test.not.ok.0(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.not.ok.0
+ bci_0:
+  br i1 undef, label %left, label %right
+
+ left:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+; CHECK: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def: i8 addrspace(1)* %arg
+; CHECK-NEXT: Use:   %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right ]
+  %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right]
+  ret i8 addrspace(1)* %val
+}
+
+define i8 addrspace(1)* @test.not.ok.1(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.not.ok.1
+ bci_0:
+  br i1 undef, label %left, label %right
+
+ left:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+; CHECK: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def: i8 addrspace(1)* %arg
+; CHECK-NEXT: Use:   %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ]
+  %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right]
+  ret i8 addrspace(1)* %val
+}
+
+define i8 addrspace(1)* @test.ok.0(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test.ok.0
+ bci_0:
+  br i1 undef, label %left, label %right
+
+ left:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+  %val = phi i8 addrspace(1)* [ null, %left ], [ null, %right]
+  ret i8 addrspace(1)* %val
+}
+
+define i8 addrspace(1)* @test.ok.1(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test.ok.1
+ bci_0:
+  br i1 undef, label %left, label %right
+
+ left:
+  call void @not_statepoint()
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+  %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right]
+  ret i8 addrspace(1)* %val
+}
+
+declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
+declare void @not_statepoint()