lib/IR/SafepointIRVerifier.cpp

   1 //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Run a sanity check on the IR to ensure that Safepoints - if they've been
  11 // inserted - were inserted correctly.  In particular, look for use of
  12 // non-relocated values after a safepoint.  It's primary use is to check the
  13 // correctness of safepoint insertion immediately after insertion, but it can
  14 // also be used to verify that later transforms have not found a way to break
  15 // safepoint semenatics.
  16 //
  17 // In its current form, this verify checks a property which is sufficient, but
  18 // not neccessary for correctness.  There are some cases where an unrelocated
  19 // pointer can be used after the safepoint.  Consider this example:
  20 //
  21 //    a = ...
  22 //    b = ...
  23 //    (a',b') = safepoint(a,b)
  24 //    c = cmp eq a b
  25 //    br c, ..., ....
  26 //
  27 // Because it is valid to reorder 'c' above the safepoint, this is legal.  In
  28 // practice, this is a somewhat uncommon transform, but CodeGenPrep does create
  29 // idioms like this.  The verifier knows about these cases and avoids reporting
  30 // false positives.
  31 //
  32 //===----------------------------------------------------------------------===//
  33
  34 #include "llvm/ADT/DenseSet.h"
  35 #include "llvm/ADT/PostOrderIterator.h"
  36 #include "llvm/ADT/SetOperations.h"
  37 #include "llvm/ADT/SetVector.h"
  38 #include "llvm/IR/BasicBlock.h"
  39 #include "llvm/IR/Dominators.h"
  40 #include "llvm/IR/Function.h"
  41 #include "llvm/IR/Instructions.h"
  42 #include "llvm/IR/Intrinsics.h"
  43 #include "llvm/IR/IntrinsicInst.h"
  44 #include "llvm/IR/Module.h"
  45 #include "llvm/IR/Value.h"
  46 #include "llvm/IR/SafepointIRVerifier.h"
  47 #include "llvm/IR/Statepoint.h"
  48 #include "llvm/Support/Debug.h"
  49 #include "llvm/Support/CommandLine.h"
  50 #include "llvm/Support/raw_ostream.h"
  51
  52 #define DEBUG_TYPE "safepoint-ir-verifier"
  53
  54 using namespace llvm;
  55
  56 /// This option is used for writing test cases.  Instead of crashing the program
  57 /// when verification fails, report a message to the console (for FileCheck
  58 /// usage) and continue execution as if nothing happened.
  59 static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
  60                                cl::init(false));
  61
  62 static void Verify(const Function &F, const DominatorTree &DT);
  63
  64 namespace {
  65 struct SafepointIRVerifier : public FunctionPass {
  66   static char ID; // Pass identification, replacement for typeid
  67   DominatorTree DT;
  68   SafepointIRVerifier() : FunctionPass(ID) {
  69     initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
  70   }
  71
  72   bool runOnFunction(Function &F) override {
  73     DT.recalculate(F);
  74     Verify(F, DT);
  75     return false; // no modifications
  76   }
  77
  78   void getAnalysisUsage(AnalysisUsage &AU) const override {
  79     AU.setPreservesAll();
  80   }
  81
  82   StringRef getPassName() const override { return "safepoint verifier"; }
  83 };
  84 } // namespace
  85
  86 void llvm::verifySafepointIR(Function &F) {
  87   SafepointIRVerifier pass;
  88   pass.runOnFunction(F);
  89 }
  90
  91 char SafepointIRVerifier::ID = 0;
  92
  93 FunctionPass *llvm::createSafepointIRVerifierPass() {
  94   return new SafepointIRVerifier();
  95 }
  96
  97 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
  98                       "Safepoint IR Verifier", false, true)
  99 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
 100                     "Safepoint IR Verifier", false, true)
 101
 102 static bool isGCPointerType(Type *T) {
 103   if (auto *PT = dyn_cast<PointerType>(T))
 104     // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
 105     // GC managed heap.  We know that a pointer into this heap needs to be
 106     // updated and that no other pointer does.
 107     return (1 == PT->getAddressSpace());
 108   return false;
 109 }
 110
 111 static bool containsGCPtrType(Type *Ty) {
 112   if (isGCPointerType(Ty))
 113     return true;
 114   if (VectorType *VT = dyn_cast<VectorType>(Ty))
 115     return isGCPointerType(VT->getScalarType());
 116   if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
 117     return containsGCPtrType(AT->getElementType());
 118   if (StructType *ST = dyn_cast<StructType>(Ty))
 119     return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
 120                        containsGCPtrType);
 121   return false;
 122 }
 123
 124 // Debugging aid -- prints a [Begin, End) range of values.
 125 template<typename IteratorTy>
 126 static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
 127   OS << "[ ";
 128   while (Begin != End) {
 129     OS << **Begin << " ";
 130     ++Begin;
 131   }
 132   OS << "]";
 133 }
 134
 135 /// The verifier algorithm is phrased in terms of availability.  The set of
 136 /// values "available" at a given point in the control flow graph is the set of
 137 /// correctly relocated value at that point, and is a subset of the set of
 138 /// definitions dominating that point.
 139
 140 using AvailableValueSet = DenseSet<const Value *>;
 141
 142 /// State we compute and track per basic block.
 143 struct BasicBlockState {
 144   // Set of values available coming in, before the phi nodes
 145   AvailableValueSet AvailableIn;
 146
 147   // Set of values available going out
 148   AvailableValueSet AvailableOut;
 149
 150   // AvailableOut minus AvailableIn.
 151   // All elements are Instructions
 152   AvailableValueSet Contribution;
 153
 154   // True if this block contains a safepoint and thus AvailableIn does not
 155   // contribute to AvailableOut.
 156   bool Cleared = false;
 157 };
 158
 159 /// A given derived pointer can have multiple base pointers through phi/selects.
 160 /// This type indicates when the base pointer is exclusively constant
 161 /// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
 162 /// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
 163 /// NonConstant.
 164 enum BaseType {
 165   NonConstant = 1, // Base pointers is not exclusively constant.
 166   ExclusivelyNull,
 167   ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
 168                           // set of constants, but they are not exclusively
 169                           // null.
 170 };
 171
 172 /// Return the baseType for Val which states whether Val is exclusively
 173 /// derived from constant/null, or not exclusively derived from constant.
 174 /// Val is exclusively derived off a constant base when all operands of phi and
 175 /// selects are derived off a constant base.
 176 static enum BaseType getBaseType(const Value *Val) {
 177
 178   SmallVector<const Value *, 32> Worklist;
 179   DenseSet<const Value *> Visited;
 180   bool isExclusivelyDerivedFromNull = true;
 181   Worklist.push_back(Val);
 182   // Strip through all the bitcasts and geps to get base pointer. Also check for
 183   // the exclusive value when there can be multiple base pointers (through phis
 184   // or selects).
 185   while(!Worklist.empty()) {
 186     const Value *V = Worklist.pop_back_val();
 187     if (!Visited.insert(V).second)
 188       continue;
 189
 190     if (const auto *CI = dyn_cast<CastInst>(V)) {
 191       Worklist.push_back(CI->stripPointerCasts());
 192       continue;
 193     }
 194     if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
 195       Worklist.push_back(GEP->getPointerOperand());
 196       continue;
 197     }
 198     // Push all the incoming values of phi node into the worklist for
 199     // processing.
 200     if (const auto *PN = dyn_cast<PHINode>(V)) {
 201       for (Value *InV: PN->incoming_values())
 202         Worklist.push_back(InV);
 203       continue;
 204     }
 205     if (const auto *SI = dyn_cast<SelectInst>(V)) {
 206       // Push in the true and false values
 207       Worklist.push_back(SI->getTrueValue());
 208       Worklist.push_back(SI->getFalseValue());
 209       continue;
 210     }
 211     if (isa<Constant>(V)) {
 212       // We found at least one base pointer which is non-null, so this derived
 213       // pointer is not exclusively derived from null.
 214       if (V != Constant::getNullValue(V->getType()))
 215         isExclusivelyDerivedFromNull = false;
 216       // Continue processing the remaining values to make sure it's exclusively
 217       // constant.
 218       continue;
 219     }
 220     // At this point, we know that the base pointer is not exclusively
 221     // constant.
 222     return BaseType::NonConstant;
 223   }
 224   // Now, we know that the base pointer is exclusively constant, but we need to
 225   // differentiate between exclusive null constant and non-null constant.
 226   return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
 227                                       : BaseType::ExclusivelySomeConstant;
 228 }
 229
 230 static bool isNotExclusivelyConstantDerived(const Value *V) {
 231   return getBaseType(V) == BaseType::NonConstant;
 232 }
 233
 234 namespace {
 235 class InstructionVerifier;
 236
 237 /// Builds BasicBlockState for each BB of the function.
 238 /// It can traverse function for verification and provides all required
 239 /// information.
 240 ///
 241 /// GC pointer may be in one of three states: relocated, unrelocated and
 242 /// poisoned.
 243 /// Relocated pointer may be used without any restrictions.
 244 /// Unrelocated pointer cannot be dereferenced, passed as argument to any call
 245 /// or returned. Unrelocated pointer may be safely compared against another
 246 /// unrelocated pointer or against a pointer exclusively derived from null.
 247 /// Poisoned pointers are produced when we somehow derive pointer from relocated
 248 /// and unrelocated pointers (e.g. phi, select). This pointers may be safely
 249 /// used in a very limited number of situations. Currently the only way to use
 250 /// it is comparison against constant exclusively derived from null. All
 251 /// limitations arise due to their undefined state: this pointers should be
 252 /// treated as relocated and unrelocated simultaneously.
 253 /// Rules of deriving:
 254 /// R + U = P - that's where the poisoned pointers come from
 255 /// P + X = P
 256 /// U + U = U
 257 /// R + R = R
 258 /// X + C = X
 259 /// Where "+" - any operation that somehow derive pointer, U - unrelocated,
 260 /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or
 261 /// nothing (in case when "+" is unary operation).
 262 /// Deriving of pointers by itself is always safe.
 263 /// NOTE: when we are making decision on the status of instruction's result:
 264 /// a) for phi we need to check status of each input *at the end of
 265 ///    corresponding predecessor BB*.
 266 /// b) for other instructions we need to check status of each input *at the
 267 ///    current point*.
 268 ///
 269 /// FIXME: This works fairly well except one case
 270 ///     bb1:
 271 ///     p = *some GC-ptr def*
 272 ///     p1 = gep p, offset
 273 ///         /     |
 274 ///        /      |
 275 ///    bb2:       |
 276 ///    safepoint  |
 277 ///        \      |
 278 ///         \     |
 279 ///      bb3:
 280 ///      p2 = phi [p, bb2] [p1, bb1]
 281 ///      p3 = phi [p, bb2] [p, bb1]
 282 ///      here p and p1 is unrelocated
 283 ///           p2 and p3 is poisoned (though they shouldn't be)
 284 ///
 285 /// This leads to some weird results:
 286 ///      cmp eq p, p2 - illegal instruction (false-positive)
 287 ///      cmp eq p1, p2 - illegal instruction (false-positive)
 288 ///      cmp eq p, p3 - illegal instruction (false-positive)
 289 ///      cmp eq p, p1 - ok
 290 /// To fix this we need to introduce conception of generations and be able to
 291 /// check if two values belong to one generation or not. This way p2 will be
 292 /// considered to be unrelocated and no false alarm will happen.
 293 class GCPtrTracker {
 294   const Function &F;
 295   SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
 296   DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
 297   // This set contains defs of unrelocated pointers that are proved to be legal
 298   // and don't need verification.
 299   DenseSet<const Instruction *> ValidUnrelocatedDefs;
 300   // This set contains poisoned defs. They can be safely ignored during
 301   // verification too.
 302   DenseSet<const Value *> PoisonedDefs;
 303
 304 public:
 305   GCPtrTracker(const Function &F, const DominatorTree &DT);
 306
 307   BasicBlockState *getBasicBlockState(const BasicBlock *BB);
 308   const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
 309
 310   bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
 311
 312   /// Traverse each BB of the function and call
 313   /// InstructionVerifier::verifyInstruction for each possibly invalid
 314   /// instruction.
 315   /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
 316   /// in order to prohibit further usages of GCPtrTracker as it'll be in
 317   /// inconsistent state.
 318   static void verifyFunction(GCPtrTracker &&Tracker,
 319                              InstructionVerifier &Verifier);
 320
 321 private:
 322   /// Returns true if the instruction may be safely skipped during verification.
 323   bool instructionMayBeSkipped(const Instruction *I) const;
 324
 325   /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
 326   /// each of them until it converges.
 327   void recalculateBBsStates();
 328
 329   /// Remove from Contribution all defs that legally produce unrelocated
 330   /// pointers and saves them to ValidUnrelocatedDefs.
 331   /// Though Contribution should belong to BBS it is passed separately with
 332   /// different const-modifier in order to emphasize (and guarantee) that only
 333   /// Contribution will be changed.
 334   /// Returns true if Contribution was changed otherwise false.
 335   bool removeValidUnrelocatedDefs(const BasicBlock *BB,
 336                                   const BasicBlockState *BBS,
 337                                   AvailableValueSet &Contribution);
 338
 339   /// Gather all the definitions dominating the start of BB into Result. This is
 340   /// simply the defs introduced by every dominating basic block and the
 341   /// function arguments.
 342   void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
 343                             const DominatorTree &DT);
 344
 345   /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
 346   /// which is the BasicBlockState for BB.
 347   /// ContributionChanged is set when the verifier runs for the first time
 348   /// (in this case Contribution was changed from 'empty' to its initial state)
 349   /// or when Contribution of this BB was changed since last computation.
 350   static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
 351                             bool ContributionChanged);
 352
 353   /// Model the effect of an instruction on the set of available values.
 354   static void transferInstruction(const Instruction &I, bool &Cleared,
 355                                   AvailableValueSet &Available);
 356 };
 357
 358 /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
 359 /// instruction (which uses heap reference) is legal or not, given our safepoint
 360 /// semantics.
 361 class InstructionVerifier {
 362   bool AnyInvalidUses = false;
 363
 364 public:
 365   void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
 366                          const AvailableValueSet &AvailableSet);
 367
 368   bool hasAnyInvalidUses() const { return AnyInvalidUses; }
 369
 370 private:
 371   void reportInvalidUse(const Value &V, const Instruction &I);
 372 };
 373 } // end anonymous namespace
 374
 375 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT) : F(F) {
 376   // First, calculate Contribution of each BB.
 377   for (const BasicBlock &BB : F) {
 378     BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
 379     for (const auto &I : BB)
 380       transferInstruction(I, BBS->Cleared, BBS->Contribution);
 381     BlockMap[&BB] = BBS;
 382   }
 383
 384   // Initialize AvailableIn/Out sets of each BB using only information about
 385   // dominating BBs.
 386   for (auto &BBI : BlockMap) {
 387     gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
 388     transferBlock(BBI.first, *BBI.second, true);
 389   }
 390
 391   // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
 392   // sets of each BB until it converges. If any def is proved to be an
 393   // unrelocated pointer, it will be removed from all BBSs.
 394   recalculateBBsStates();
 395 }
 396
 397 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
 398   auto it = BlockMap.find(BB);
 399   assert(it != BlockMap.end() &&
 400          "No such BB in BlockMap! Probably BB from another function");
 401   return it->second;
 402 }
 403
 404 const BasicBlockState *GCPtrTracker::getBasicBlockState(
 405     const BasicBlock *BB) const {
 406   return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
 407 }
 408
 409 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
 410   // Poisoned defs are skipped since they are always safe by itself by
 411   // definition (for details see comment to this class).
 412   return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
 413 }
 414
 415 void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
 416                                   InstructionVerifier &Verifier) {
 417   // We need RPO here to a) report always the first error b) report errors in
 418   // same order from run to run.
 419   ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
 420   for (const BasicBlock *BB : RPOT) {
 421     BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
 422     // We destructively modify AvailableIn as we traverse the block instruction
 423     // by instruction.
 424     AvailableValueSet &AvailableSet = BBS->AvailableIn;
 425     for (const Instruction &I : *BB) {
 426       if (Tracker.instructionMayBeSkipped(&I))
 427         continue; // This instruction shouldn't be added to AvailableSet.
 428
 429       Verifier.verifyInstruction(&Tracker, I, AvailableSet);
 430
 431       // Model the effect of current instruction on AvailableSet to keep the set
 432       // relevant at each point of BB.
 433       bool Cleared = false;
 434       transferInstruction(I, Cleared, AvailableSet);
 435       (void)Cleared;
 436     }
 437   }
 438 }
 439
 440 void GCPtrTracker::recalculateBBsStates() {
 441   SetVector<const BasicBlock *> Worklist;
 442   // TODO: This order is suboptimal, it's better to replace it with priority
 443   // queue where priority is RPO number of BB.
 444   for (auto &BBI : BlockMap)
 445     Worklist.insert(BBI.first);
 446
 447   // This loop iterates the AvailableIn/Out sets until it converges.
 448   // The AvailableIn and AvailableOut sets decrease as we iterate.
 449   while (!Worklist.empty()) {
 450     const BasicBlock *BB = Worklist.pop_back_val();
 451     BasicBlockState *BBS = BlockMap[BB];
 452
 453     size_t OldInCount = BBS->AvailableIn.size();
 454     for (const BasicBlock *PBB : predecessors(BB))
 455       set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
 456
 457     assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
 458
 459     bool InputsChanged = OldInCount != BBS->AvailableIn.size();
 460     bool ContributionChanged =
 461         removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
 462     if (!InputsChanged && !ContributionChanged)
 463       continue;
 464
 465     size_t OldOutCount = BBS->AvailableOut.size();
 466     transferBlock(BB, *BBS, ContributionChanged);
 467     if (OldOutCount != BBS->AvailableOut.size()) {
 468       assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
 469       Worklist.insert(succ_begin(BB), succ_end(BB));
 470     }
 471   }
 472 }
 473
 474 bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
 475                                               const BasicBlockState *BBS,
 476                                               AvailableValueSet &Contribution) {
 477   assert(&BBS->Contribution == &Contribution &&
 478          "Passed Contribution should be from the passed BasicBlockState!");
 479   AvailableValueSet AvailableSet = BBS->AvailableIn;
 480   bool ContributionChanged = false;
 481   // For explanation why instructions are processed this way see
 482   // "Rules of deriving" in the comment to this class.
 483   for (const Instruction &I : *BB) {
 484     bool ValidUnrelocatedPointerDef = false;
 485     bool PoisonedPointerDef = false;
 486     // TODO: `select` instructions should be handled here too.
 487     if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
 488       if (containsGCPtrType(PN->getType())) {
 489         // If both is true, output is poisoned.
 490         bool HasRelocatedInputs = false;
 491         bool HasUnrelocatedInputs = false;
 492         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 493           const BasicBlock *InBB = PN->getIncomingBlock(i);
 494           const Value *InValue = PN->getIncomingValue(i);
 495
 496           if (isNotExclusivelyConstantDerived(InValue)) {
 497             if (isValuePoisoned(InValue)) {
 498               // If any of inputs is poisoned, output is always poisoned too.
 499               HasRelocatedInputs = true;
 500               HasUnrelocatedInputs = true;
 501               break;
 502             }
 503             if (BlockMap[InBB]->AvailableOut.count(InValue))
 504               HasRelocatedInputs = true;
 505             else
 506               HasUnrelocatedInputs = true;
 507           }
 508         }
 509         if (HasUnrelocatedInputs) {
 510           if (HasRelocatedInputs)
 511             PoisonedPointerDef = true;
 512           else
 513             ValidUnrelocatedPointerDef = true;
 514         }
 515       }
 516     } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
 517                containsGCPtrType(I.getType())) {
 518       // GEP/bitcast of unrelocated pointer is legal by itself but this def
 519       // shouldn't appear in any AvailableSet.
 520       for (const Value *V : I.operands())
 521         if (containsGCPtrType(V->getType()) &&
 522             isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
 523           if (isValuePoisoned(V))
 524             PoisonedPointerDef = true;
 525           else
 526             ValidUnrelocatedPointerDef = true;
 527           break;
 528         }
 529     }
 530     assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
 531            "Value cannot be both unrelocated and poisoned!");
 532     if (ValidUnrelocatedPointerDef) {
 533       // Remove def of unrelocated pointer from Contribution of this BB and
 534       // trigger update of all its successors.
 535       Contribution.erase(&I);
 536       PoisonedDefs.erase(&I);
 537       ValidUnrelocatedDefs.insert(&I);
 538       DEBUG(dbgs() << "Removing urelocated " << I << " from Contribution of "
 539                    << BB->getName() << "\n");
 540       ContributionChanged = true;
 541     } else if (PoisonedPointerDef) {
 542       // Mark pointer as poisoned, remove its def from Contribution and trigger
 543       // update of all successors.
 544       Contribution.erase(&I);
 545       PoisonedDefs.insert(&I);
 546       DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
 547                    << BB->getName() << "\n");
 548       ContributionChanged = true;
 549     } else {
 550       bool Cleared = false;
 551       transferInstruction(I, Cleared, AvailableSet);
 552       (void)Cleared;
 553     }
 554   }
 555   return ContributionChanged;
 556 }
 557
 558 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
 559                                         AvailableValueSet &Result,
 560                                         const DominatorTree &DT) {
 561   DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
 562
 563   while (DTN->getIDom()) {
 564     DTN = DTN->getIDom();
 565     const auto &Defs = BlockMap[DTN->getBlock()]->Contribution;
 566     Result.insert(Defs.begin(), Defs.end());
 567     // If this block is 'Cleared', then nothing LiveIn to this block can be
 568     // available after this block completes.  Note: This turns out to be
 569     // really important for reducing memory consuption of the initial available
 570     // sets and thus peak memory usage by this verifier.
 571     if (BlockMap[DTN->getBlock()]->Cleared)
 572       return;
 573   }
 574
 575   for (const Argument &A : BB->getParent()->args())
 576     if (containsGCPtrType(A.getType()))
 577       Result.insert(&A);
 578 }
 579
 580 void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
 581                                  bool ContributionChanged) {
 582   const AvailableValueSet &AvailableIn = BBS.AvailableIn;
 583   AvailableValueSet &AvailableOut = BBS.AvailableOut;
 584
 585   if (BBS.Cleared) {
 586     // AvailableOut will change only when Contribution changed.
 587     if (ContributionChanged)
 588       AvailableOut = BBS.Contribution;
 589   } else {
 590     // Otherwise, we need to reduce the AvailableOut set by things which are no
 591     // longer in our AvailableIn
 592     AvailableValueSet Temp = BBS.Contribution;
 593     set_union(Temp, AvailableIn);
 594     AvailableOut = std::move(Temp);
 595   }
 596
 597   DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
 598         PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
 599         dbgs() << " to ";
 600         PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
 601         dbgs() << "\n";);
 602 }
 603
 604 void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
 605                                        AvailableValueSet &Available) {
 606   if (isStatepoint(I)) {
 607     Cleared = true;
 608     Available.clear();
 609   } else if (containsGCPtrType(I.getType()))
 610     Available.insert(&I);
 611 }
 612
 613 void InstructionVerifier::verifyInstruction(
 614     const GCPtrTracker *Tracker, const Instruction &I,
 615     const AvailableValueSet &AvailableSet) {
 616   if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
 617     if (containsGCPtrType(PN->getType()))
 618       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 619         const BasicBlock *InBB = PN->getIncomingBlock(i);
 620         const Value *InValue = PN->getIncomingValue(i);
 621
 622         if (isNotExclusivelyConstantDerived(InValue) &&
 623             !Tracker->getBasicBlockState(InBB)->AvailableOut.count(InValue))
 624           reportInvalidUse(*InValue, *PN);
 625       }
 626   } else if (isa<CmpInst>(I) &&
 627              containsGCPtrType(I.getOperand(0)->getType())) {
 628     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 629     enum BaseType baseTyLHS = getBaseType(LHS),
 630                   baseTyRHS = getBaseType(RHS);
 631
 632     // Returns true if LHS and RHS are unrelocated pointers and they are
 633     // valid unrelocated uses.
 634     auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
 635                                    &LHS, &RHS] () {
 636         // A cmp instruction has valid unrelocated pointer operands only if
 637         // both operands are unrelocated pointers.
 638         // In the comparison between two pointers, if one is an unrelocated
 639         // use, the other *should be* an unrelocated use, for this
 640         // instruction to contain valid unrelocated uses. This unrelocated
 641         // use can be a null constant as well, or another unrelocated
 642         // pointer.
 643         if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
 644           return false;
 645         // Constant pointers (that are not exclusively null) may have
 646         // meaning in different VMs, so we cannot reorder the compare
 647         // against constant pointers before the safepoint. In other words,
 648         // comparison of an unrelocated use against a non-null constant
 649         // maybe invalid.
 650         if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
 651              baseTyRHS == BaseType::NonConstant) ||
 652             (baseTyLHS == BaseType::NonConstant &&
 653              baseTyRHS == BaseType::ExclusivelySomeConstant))
 654           return false;
 655
 656         // If one of pointers is poisoned and other is not exclusively derived
 657         // from null it is an invalid expression: it produces poisoned result
 658         // and unless we want to track all defs (not only gc pointers) the only
 659         // option is to prohibit such instructions.
 660         if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||
 661             (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))
 662             return false;
 663
 664         // All other cases are valid cases enumerated below:
 665         // 1. Comparison between an exclusively derived null pointer and a
 666         // constant base pointer.
 667         // 2. Comparison between an exclusively derived null pointer and a
 668         // non-constant unrelocated base pointer.
 669         // 3. Comparison between 2 unrelocated pointers.
 670         // 4. Comparison between a pointer exclusively derived from null and a
 671         // non-constant poisoned pointer.
 672         return true;
 673     };
 674     if (!hasValidUnrelocatedUse()) {
 675       // Print out all non-constant derived pointers that are unrelocated
 676       // uses, which are invalid.
 677       if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
 678         reportInvalidUse(*LHS, I);
 679       if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
 680         reportInvalidUse(*RHS, I);
 681     }
 682   } else {
 683     for (const Value *V : I.operands())
 684       if (containsGCPtrType(V->getType()) &&
 685           isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
 686         reportInvalidUse(*V, I);
 687   }
 688 }
 689
 690 void InstructionVerifier::reportInvalidUse(const Value &V,
 691                                            const Instruction &I) {
 692   errs() << "Illegal use of unrelocated value found!\n";
 693   errs() << "Def: " << V << "\n";
 694   errs() << "Use: " << I << "\n";
 695   if (!PrintOnly)
 696     abort();
 697   AnyInvalidUses = true;
 698 }
 699
 700 static void Verify(const Function &F, const DominatorTree &DT) {
 701   DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n");
 702   if (PrintOnly)
 703     dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
 704
 705   GCPtrTracker Tracker(F, DT);
 706
 707   // We now have all the information we need to decide if the use of a heap
 708   // reference is legal or not, given our safepoint semantics.
 709
 710   InstructionVerifier Verifier;
 711   GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);
 712
 713   if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
 714     dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
 715            << "\n";
 716   }
 717 }