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 namespace {
  63
  64 /// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set
  65 /// of blocks unreachable from entry then propagates deadness using foldable
  66 /// conditional branches without modifying CFG. So GVN does but it changes CFG
  67 /// by splitting critical edges. In most cases passes rely on SimplifyCFG to
  68 /// clean up dead blocks, but in some cases, like verification or loop passes
  69 /// it's not possible.
  70 class CFGDeadness {
  71   const DominatorTree *DT = nullptr;
  72   SetVector<const BasicBlock *> DeadBlocks;
  73   SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks.
  74
  75 public:
  76   /// Return the edge that coresponds to the predecessor.
  77   static const Use& getEdge(const_pred_iterator &PredIt) {
  78     auto &PU = PredIt.getUse();
  79     return PU.getUser()->getOperandUse(PU.getOperandNo());
  80   }
  81
  82   /// Return true if there is at least one live edge that corresponds to the
  83   /// basic block InBB listed in the phi node.
  84   bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
  85     assert(!isDeadBlock(InBB) && "block must be live");
  86     const BasicBlock* BB = PN->getParent();
  87     bool Listed = false;
  88     for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
  89       if (InBB == *PredIt) {
  90         if (!isDeadEdge(&getEdge(PredIt)))
  91           return true;
  92         Listed = true;
  93       }
  94     }
  95     assert(Listed && "basic block is not found among incoming blocks");
  96     return false;
  97   }
  98
  99
 100   bool isDeadBlock(const BasicBlock *BB) const {
 101     return DeadBlocks.count(BB);
 102   }
 103
 104   bool isDeadEdge(const Use *U) const {
 105     assert(dyn_cast<Instruction>(U->getUser())->isTerminator() &&
 106            "edge must be operand of terminator");
 107     assert(cast_or_null<BasicBlock>(U->get()) &&
 108            "edge must refer to basic block");
 109     assert(!isDeadBlock(dyn_cast<Instruction>(U->getUser())->getParent()) &&
 110            "isDeadEdge() must be applied to edge from live block");
 111     return DeadEdges.count(U);
 112   }
 113
 114   bool hasLiveIncomingEdges(const BasicBlock *BB) const {
 115     // Check if all incoming edges are dead.
 116     for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
 117       auto &PU = PredIt.getUse();
 118       const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());
 119       if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
 120         return true; // Found a live edge.
 121     }
 122     return false;
 123   }
 124
 125   void processFunction(const Function &F, const DominatorTree &DT) {
 126     this->DT = &DT;
 127
 128     // Start with all blocks unreachable from entry.
 129     for (const BasicBlock &BB : F)
 130       if (!DT.isReachableFromEntry(&BB))
 131         DeadBlocks.insert(&BB);
 132
 133     // Top-down walk of the dominator tree
 134     ReversePostOrderTraversal<const Function *> RPOT(&F);
 135     for (const BasicBlock *BB : RPOT) {
 136       const TerminatorInst *TI = BB->getTerminator();
 137       assert(TI && "blocks must be well formed");
 138
 139       // For conditional branches, we can perform simple conditional propagation on
 140       // the condition value itself.
 141       const BranchInst *BI = dyn_cast<BranchInst>(TI);
 142       if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
 143         continue;
 144
 145       // If a branch has two identical successors, we cannot declare either dead.
 146       if (BI->getSuccessor(0) == BI->getSuccessor(1))
 147         continue;
 148
 149       ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
 150       if (!Cond)
 151         continue;
 152
 153       addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
 154     }
 155   }
 156
 157 protected:
 158   void addDeadBlock(const BasicBlock *BB) {
 159     SmallVector<const BasicBlock *, 4> NewDead;
 160     SmallSetVector<const BasicBlock *, 4> DF;
 161
 162     NewDead.push_back(BB);
 163     while (!NewDead.empty()) {
 164       const BasicBlock *D = NewDead.pop_back_val();
 165       if (isDeadBlock(D))
 166         continue;
 167
 168       // All blocks dominated by D are dead.
 169       SmallVector<BasicBlock *, 8> Dom;
 170       DT->getDescendants(const_cast<BasicBlock*>(D), Dom);
 171       // Do not need to mark all in and out edges dead
 172       // because BB is marked dead and this is enough
 173       // to run further.
 174       DeadBlocks.insert(Dom.begin(), Dom.end());
 175
 176       // Figure out the dominance-frontier(D).
 177       for (BasicBlock *B : Dom)
 178         for (BasicBlock *S : successors(B))
 179           if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))
 180             NewDead.push_back(S);
 181     }
 182   }
 183
 184   void addDeadEdge(const Use &DeadEdge) {
 185     if (!DeadEdges.insert(&DeadEdge))
 186       return;
 187
 188     BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get());
 189     if (hasLiveIncomingEdges(BB))
 190       return;
 191
 192     addDeadBlock(BB);
 193   }
 194 };
 195 } // namespace
 196
 197 static void Verify(const Function &F, const DominatorTree &DT,
 198                    const CFGDeadness &CD);
 199
 200 namespace {
 201
 202 struct SafepointIRVerifier : public FunctionPass {
 203   static char ID; // Pass identification, replacement for typeid
 204   SafepointIRVerifier() : FunctionPass(ID) {
 205     initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
 206   }
 207
 208   bool runOnFunction(Function &F) override {
 209     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 210     CFGDeadness CD;
 211     CD.processFunction(F, DT);
 212     Verify(F, DT, CD);
 213     return false; // no modifications
 214   }
 215
 216   void getAnalysisUsage(AnalysisUsage &AU) const override {
 217     AU.addRequiredID(DominatorTreeWrapperPass::ID);
 218     AU.setPreservesAll();
 219   }
 220
 221   StringRef getPassName() const override { return "safepoint verifier"; }
 222 };
 223 } // namespace
 224
 225 void llvm::verifySafepointIR(Function &F) {
 226   SafepointIRVerifier pass;
 227   pass.runOnFunction(F);
 228 }
 229
 230 char SafepointIRVerifier::ID = 0;
 231
 232 FunctionPass *llvm::createSafepointIRVerifierPass() {
 233   return new SafepointIRVerifier();
 234 }
 235
 236 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
 237                       "Safepoint IR Verifier", false, false)
 238 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 239 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
 240                     "Safepoint IR Verifier", false, false)
 241
 242 static bool isGCPointerType(Type *T) {
 243   if (auto *PT = dyn_cast<PointerType>(T))
 244     // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
 245     // GC managed heap.  We know that a pointer into this heap needs to be
 246     // updated and that no other pointer does.
 247     return (1 == PT->getAddressSpace());
 248   return false;
 249 }
 250
 251 static bool containsGCPtrType(Type *Ty) {
 252   if (isGCPointerType(Ty))
 253     return true;
 254   if (VectorType *VT = dyn_cast<VectorType>(Ty))
 255     return isGCPointerType(VT->getScalarType());
 256   if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
 257     return containsGCPtrType(AT->getElementType());
 258   if (StructType *ST = dyn_cast<StructType>(Ty))
 259     return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
 260                        containsGCPtrType);
 261   return false;
 262 }
 263
 264 // Debugging aid -- prints a [Begin, End) range of values.
 265 template<typename IteratorTy>
 266 static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
 267   OS << "[ ";
 268   while (Begin != End) {
 269     OS << **Begin << " ";
 270     ++Begin;
 271   }
 272   OS << "]";
 273 }
 274
 275 /// The verifier algorithm is phrased in terms of availability.  The set of
 276 /// values "available" at a given point in the control flow graph is the set of
 277 /// correctly relocated value at that point, and is a subset of the set of
 278 /// definitions dominating that point.
 279
 280 using AvailableValueSet = DenseSet<const Value *>;
 281
 282 /// State we compute and track per basic block.
 283 struct BasicBlockState {
 284   // Set of values available coming in, before the phi nodes
 285   AvailableValueSet AvailableIn;
 286
 287   // Set of values available going out
 288   AvailableValueSet AvailableOut;
 289
 290   // AvailableOut minus AvailableIn.
 291   // All elements are Instructions
 292   AvailableValueSet Contribution;
 293
 294   // True if this block contains a safepoint and thus AvailableIn does not
 295   // contribute to AvailableOut.
 296   bool Cleared = false;
 297 };
 298
 299 /// A given derived pointer can have multiple base pointers through phi/selects.
 300 /// This type indicates when the base pointer is exclusively constant
 301 /// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
 302 /// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
 303 /// NonConstant.
 304 enum BaseType {
 305   NonConstant = 1, // Base pointers is not exclusively constant.
 306   ExclusivelyNull,
 307   ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
 308                           // set of constants, but they are not exclusively
 309                           // null.
 310 };
 311
 312 /// Return the baseType for Val which states whether Val is exclusively
 313 /// derived from constant/null, or not exclusively derived from constant.
 314 /// Val is exclusively derived off a constant base when all operands of phi and
 315 /// selects are derived off a constant base.
 316 static enum BaseType getBaseType(const Value *Val) {
 317
 318   SmallVector<const Value *, 32> Worklist;
 319   DenseSet<const Value *> Visited;
 320   bool isExclusivelyDerivedFromNull = true;
 321   Worklist.push_back(Val);
 322   // Strip through all the bitcasts and geps to get base pointer. Also check for
 323   // the exclusive value when there can be multiple base pointers (through phis
 324   // or selects).
 325   while(!Worklist.empty()) {
 326     const Value *V = Worklist.pop_back_val();
 327     if (!Visited.insert(V).second)
 328       continue;
 329
 330     if (const auto *CI = dyn_cast<CastInst>(V)) {
 331       Worklist.push_back(CI->stripPointerCasts());
 332       continue;
 333     }
 334     if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
 335       Worklist.push_back(GEP->getPointerOperand());
 336       continue;
 337     }
 338     // Push all the incoming values of phi node into the worklist for
 339     // processing.
 340     if (const auto *PN = dyn_cast<PHINode>(V)) {
 341       for (Value *InV: PN->incoming_values())
 342         Worklist.push_back(InV);
 343       continue;
 344     }
 345     if (const auto *SI = dyn_cast<SelectInst>(V)) {
 346       // Push in the true and false values
 347       Worklist.push_back(SI->getTrueValue());
 348       Worklist.push_back(SI->getFalseValue());
 349       continue;
 350     }
 351     if (isa<Constant>(V)) {
 352       // We found at least one base pointer which is non-null, so this derived
 353       // pointer is not exclusively derived from null.
 354       if (V != Constant::getNullValue(V->getType()))
 355         isExclusivelyDerivedFromNull = false;
 356       // Continue processing the remaining values to make sure it's exclusively
 357       // constant.
 358       continue;
 359     }
 360     // At this point, we know that the base pointer is not exclusively
 361     // constant.
 362     return BaseType::NonConstant;
 363   }
 364   // Now, we know that the base pointer is exclusively constant, but we need to
 365   // differentiate between exclusive null constant and non-null constant.
 366   return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
 367                                       : BaseType::ExclusivelySomeConstant;
 368 }
 369
 370 static bool isNotExclusivelyConstantDerived(const Value *V) {
 371   return getBaseType(V) == BaseType::NonConstant;
 372 }
 373
 374 namespace {
 375 class InstructionVerifier;
 376
 377 /// Builds BasicBlockState for each BB of the function.
 378 /// It can traverse function for verification and provides all required
 379 /// information.
 380 ///
 381 /// GC pointer may be in one of three states: relocated, unrelocated and
 382 /// poisoned.
 383 /// Relocated pointer may be used without any restrictions.
 384 /// Unrelocated pointer cannot be dereferenced, passed as argument to any call
 385 /// or returned. Unrelocated pointer may be safely compared against another
 386 /// unrelocated pointer or against a pointer exclusively derived from null.
 387 /// Poisoned pointers are produced when we somehow derive pointer from relocated
 388 /// and unrelocated pointers (e.g. phi, select). This pointers may be safely
 389 /// used in a very limited number of situations. Currently the only way to use
 390 /// it is comparison against constant exclusively derived from null. All
 391 /// limitations arise due to their undefined state: this pointers should be
 392 /// treated as relocated and unrelocated simultaneously.
 393 /// Rules of deriving:
 394 /// R + U = P - that's where the poisoned pointers come from
 395 /// P + X = P
 396 /// U + U = U
 397 /// R + R = R
 398 /// X + C = X
 399 /// Where "+" - any operation that somehow derive pointer, U - unrelocated,
 400 /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or
 401 /// nothing (in case when "+" is unary operation).
 402 /// Deriving of pointers by itself is always safe.
 403 /// NOTE: when we are making decision on the status of instruction's result:
 404 /// a) for phi we need to check status of each input *at the end of
 405 ///    corresponding predecessor BB*.
 406 /// b) for other instructions we need to check status of each input *at the
 407 ///    current point*.
 408 ///
 409 /// FIXME: This works fairly well except one case
 410 ///     bb1:
 411 ///     p = *some GC-ptr def*
 412 ///     p1 = gep p, offset
 413 ///         /     |
 414 ///        /      |
 415 ///    bb2:       |
 416 ///    safepoint  |
 417 ///        \      |
 418 ///         \     |
 419 ///      bb3:
 420 ///      p2 = phi [p, bb2] [p1, bb1]
 421 ///      p3 = phi [p, bb2] [p, bb1]
 422 ///      here p and p1 is unrelocated
 423 ///           p2 and p3 is poisoned (though they shouldn't be)
 424 ///
 425 /// This leads to some weird results:
 426 ///      cmp eq p, p2 - illegal instruction (false-positive)
 427 ///      cmp eq p1, p2 - illegal instruction (false-positive)
 428 ///      cmp eq p, p3 - illegal instruction (false-positive)
 429 ///      cmp eq p, p1 - ok
 430 /// To fix this we need to introduce conception of generations and be able to
 431 /// check if two values belong to one generation or not. This way p2 will be
 432 /// considered to be unrelocated and no false alarm will happen.
 433 class GCPtrTracker {
 434   const Function &F;
 435   const CFGDeadness &CD;
 436   SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
 437   DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
 438   // This set contains defs of unrelocated pointers that are proved to be legal
 439   // and don't need verification.
 440   DenseSet<const Instruction *> ValidUnrelocatedDefs;
 441   // This set contains poisoned defs. They can be safely ignored during
 442   // verification too.
 443   DenseSet<const Value *> PoisonedDefs;
 444
 445 public:
 446   GCPtrTracker(const Function &F, const DominatorTree &DT,
 447                const CFGDeadness &CD);
 448
 449   bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
 450     return CD.hasLiveIncomingEdge(PN, InBB);
 451   }
 452
 453   BasicBlockState *getBasicBlockState(const BasicBlock *BB);
 454   const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
 455
 456   bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
 457
 458   /// Traverse each BB of the function and call
 459   /// InstructionVerifier::verifyInstruction for each possibly invalid
 460   /// instruction.
 461   /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
 462   /// in order to prohibit further usages of GCPtrTracker as it'll be in
 463   /// inconsistent state.
 464   static void verifyFunction(GCPtrTracker &&Tracker,
 465                              InstructionVerifier &Verifier);
 466
 467   /// Returns true for reachable and live blocks.
 468   bool isMapped(const BasicBlock *BB) const {
 469     return BlockMap.find(BB) != BlockMap.end();
 470   }
 471
 472 private:
 473   /// Returns true if the instruction may be safely skipped during verification.
 474   bool instructionMayBeSkipped(const Instruction *I) const;
 475
 476   /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
 477   /// each of them until it converges.
 478   void recalculateBBsStates();
 479
 480   /// Remove from Contribution all defs that legally produce unrelocated
 481   /// pointers and saves them to ValidUnrelocatedDefs.
 482   /// Though Contribution should belong to BBS it is passed separately with
 483   /// different const-modifier in order to emphasize (and guarantee) that only
 484   /// Contribution will be changed.
 485   /// Returns true if Contribution was changed otherwise false.
 486   bool removeValidUnrelocatedDefs(const BasicBlock *BB,
 487                                   const BasicBlockState *BBS,
 488                                   AvailableValueSet &Contribution);
 489
 490   /// Gather all the definitions dominating the start of BB into Result. This is
 491   /// simply the defs introduced by every dominating basic block and the
 492   /// function arguments.
 493   void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
 494                             const DominatorTree &DT);
 495
 496   /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
 497   /// which is the BasicBlockState for BB.
 498   /// ContributionChanged is set when the verifier runs for the first time
 499   /// (in this case Contribution was changed from 'empty' to its initial state)
 500   /// or when Contribution of this BB was changed since last computation.
 501   static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
 502                             bool ContributionChanged);
 503
 504   /// Model the effect of an instruction on the set of available values.
 505   static void transferInstruction(const Instruction &I, bool &Cleared,
 506                                   AvailableValueSet &Available);
 507 };
 508
 509 /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
 510 /// instruction (which uses heap reference) is legal or not, given our safepoint
 511 /// semantics.
 512 class InstructionVerifier {
 513   bool AnyInvalidUses = false;
 514
 515 public:
 516   void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
 517                          const AvailableValueSet &AvailableSet);
 518
 519   bool hasAnyInvalidUses() const { return AnyInvalidUses; }
 520
 521 private:
 522   void reportInvalidUse(const Value &V, const Instruction &I);
 523 };
 524 } // end anonymous namespace
 525
 526 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,
 527                            const CFGDeadness &CD) : F(F), CD(CD) {
 528   // Calculate Contribution of each live BB.
 529   // Allocate BB states for live blocks.
 530   for (const BasicBlock &BB : F)
 531     if (!CD.isDeadBlock(&BB)) {
 532       BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
 533       for (const auto &I : BB)
 534         transferInstruction(I, BBS->Cleared, BBS->Contribution);
 535       BlockMap[&BB] = BBS;
 536     }
 537
 538   // Initialize AvailableIn/Out sets of each BB using only information about
 539   // dominating BBs.
 540   for (auto &BBI : BlockMap) {
 541     gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
 542     transferBlock(BBI.first, *BBI.second, true);
 543   }
 544
 545   // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
 546   // sets of each BB until it converges. If any def is proved to be an
 547   // unrelocated pointer, it will be removed from all BBSs.
 548   recalculateBBsStates();
 549 }
 550
 551 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
 552   auto it = BlockMap.find(BB);
 553   return it != BlockMap.end() ? it->second : nullptr;
 554 }
 555
 556 const BasicBlockState *GCPtrTracker::getBasicBlockState(
 557     const BasicBlock *BB) const {
 558   return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
 559 }
 560
 561 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
 562   // Poisoned defs are skipped since they are always safe by itself by
 563   // definition (for details see comment to this class).
 564   return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
 565 }
 566
 567 void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
 568                                   InstructionVerifier &Verifier) {
 569   // We need RPO here to a) report always the first error b) report errors in
 570   // same order from run to run.
 571   ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
 572   for (const BasicBlock *BB : RPOT) {
 573     BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
 574     if (!BBS)
 575       continue;
 576
 577     // We destructively modify AvailableIn as we traverse the block instruction
 578     // by instruction.
 579     AvailableValueSet &AvailableSet = BBS->AvailableIn;
 580     for (const Instruction &I : *BB) {
 581       if (Tracker.instructionMayBeSkipped(&I))
 582         continue; // This instruction shouldn't be added to AvailableSet.
 583
 584       Verifier.verifyInstruction(&Tracker, I, AvailableSet);
 585
 586       // Model the effect of current instruction on AvailableSet to keep the set
 587       // relevant at each point of BB.
 588       bool Cleared = false;
 589       transferInstruction(I, Cleared, AvailableSet);
 590       (void)Cleared;
 591     }
 592   }
 593 }
 594
 595 void GCPtrTracker::recalculateBBsStates() {
 596   SetVector<const BasicBlock *> Worklist;
 597   // TODO: This order is suboptimal, it's better to replace it with priority
 598   // queue where priority is RPO number of BB.
 599   for (auto &BBI : BlockMap)
 600     Worklist.insert(BBI.first);
 601
 602   // This loop iterates the AvailableIn/Out sets until it converges.
 603   // The AvailableIn and AvailableOut sets decrease as we iterate.
 604   while (!Worklist.empty()) {
 605     const BasicBlock *BB = Worklist.pop_back_val();
 606     BasicBlockState *BBS = getBasicBlockState(BB);
 607     if (!BBS)
 608       continue; // Ignore dead successors.
 609
 610     size_t OldInCount = BBS->AvailableIn.size();
 611     for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
 612       const BasicBlock *PBB = *PredIt;
 613       BasicBlockState *PBBS = getBasicBlockState(PBB);
 614       if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
 615         set_intersect(BBS->AvailableIn, PBBS->AvailableOut);
 616     }
 617
 618     assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
 619
 620     bool InputsChanged = OldInCount != BBS->AvailableIn.size();
 621     bool ContributionChanged =
 622         removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
 623     if (!InputsChanged && !ContributionChanged)
 624       continue;
 625
 626     size_t OldOutCount = BBS->AvailableOut.size();
 627     transferBlock(BB, *BBS, ContributionChanged);
 628     if (OldOutCount != BBS->AvailableOut.size()) {
 629       assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
 630       Worklist.insert(succ_begin(BB), succ_end(BB));
 631     }
 632   }
 633 }
 634
 635 bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
 636                                               const BasicBlockState *BBS,
 637                                               AvailableValueSet &Contribution) {
 638   assert(&BBS->Contribution == &Contribution &&
 639          "Passed Contribution should be from the passed BasicBlockState!");
 640   AvailableValueSet AvailableSet = BBS->AvailableIn;
 641   bool ContributionChanged = false;
 642   // For explanation why instructions are processed this way see
 643   // "Rules of deriving" in the comment to this class.
 644   for (const Instruction &I : *BB) {
 645     bool ValidUnrelocatedPointerDef = false;
 646     bool PoisonedPointerDef = false;
 647     // TODO: `select` instructions should be handled here too.
 648     if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
 649       if (containsGCPtrType(PN->getType())) {
 650         // If both is true, output is poisoned.
 651         bool HasRelocatedInputs = false;
 652         bool HasUnrelocatedInputs = false;
 653         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 654           const BasicBlock *InBB = PN->getIncomingBlock(i);
 655           if (!isMapped(InBB) ||
 656               !CD.hasLiveIncomingEdge(PN, InBB))
 657             continue; // Skip dead block or dead edge.
 658
 659           const Value *InValue = PN->getIncomingValue(i);
 660
 661           if (isNotExclusivelyConstantDerived(InValue)) {
 662             if (isValuePoisoned(InValue)) {
 663               // If any of inputs is poisoned, output is always poisoned too.
 664               HasRelocatedInputs = true;
 665               HasUnrelocatedInputs = true;
 666               break;
 667             }
 668             if (BlockMap[InBB]->AvailableOut.count(InValue))
 669               HasRelocatedInputs = true;
 670             else
 671               HasUnrelocatedInputs = true;
 672           }
 673         }
 674         if (HasUnrelocatedInputs) {
 675           if (HasRelocatedInputs)
 676             PoisonedPointerDef = true;
 677           else
 678             ValidUnrelocatedPointerDef = true;
 679         }
 680       }
 681     } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
 682                containsGCPtrType(I.getType())) {
 683       // GEP/bitcast of unrelocated pointer is legal by itself but this def
 684       // shouldn't appear in any AvailableSet.
 685       for (const Value *V : I.operands())
 686         if (containsGCPtrType(V->getType()) &&
 687             isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
 688           if (isValuePoisoned(V))
 689             PoisonedPointerDef = true;
 690           else
 691             ValidUnrelocatedPointerDef = true;
 692           break;
 693         }
 694     }
 695     assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
 696            "Value cannot be both unrelocated and poisoned!");
 697     if (ValidUnrelocatedPointerDef) {
 698       // Remove def of unrelocated pointer from Contribution of this BB and
 699       // trigger update of all its successors.
 700       Contribution.erase(&I);
 701       PoisonedDefs.erase(&I);
 702       ValidUnrelocatedDefs.insert(&I);
 703       LLVM_DEBUG(dbgs() << "Removing urelocated " << I
 704                         << " from Contribution of " << BB->getName() << "\n");
 705       ContributionChanged = true;
 706     } else if (PoisonedPointerDef) {
 707       // Mark pointer as poisoned, remove its def from Contribution and trigger
 708       // update of all successors.
 709       Contribution.erase(&I);
 710       PoisonedDefs.insert(&I);
 711       LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
 712                         << BB->getName() << "\n");
 713       ContributionChanged = true;
 714     } else {
 715       bool Cleared = false;
 716       transferInstruction(I, Cleared, AvailableSet);
 717       (void)Cleared;
 718     }
 719   }
 720   return ContributionChanged;
 721 }
 722
 723 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
 724                                         AvailableValueSet &Result,
 725                                         const DominatorTree &DT) {
 726   DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
 727
 728   assert(DTN && "Unreachable blocks are ignored");
 729   while (DTN->getIDom()) {
 730     DTN = DTN->getIDom();
 731     auto BBS = getBasicBlockState(DTN->getBlock());
 732     assert(BBS && "immediate dominator cannot be dead for a live block");
 733     const auto &Defs = BBS->Contribution;
 734     Result.insert(Defs.begin(), Defs.end());
 735     // If this block is 'Cleared', then nothing LiveIn to this block can be
 736     // available after this block completes.  Note: This turns out to be
 737     // really important for reducing memory consuption of the initial available
 738     // sets and thus peak memory usage by this verifier.
 739     if (BBS->Cleared)
 740       return;
 741   }
 742
 743   for (const Argument &A : BB->getParent()->args())
 744     if (containsGCPtrType(A.getType()))
 745       Result.insert(&A);
 746 }
 747
 748 void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
 749                                  bool ContributionChanged) {
 750   const AvailableValueSet &AvailableIn = BBS.AvailableIn;
 751   AvailableValueSet &AvailableOut = BBS.AvailableOut;
 752
 753   if (BBS.Cleared) {
 754     // AvailableOut will change only when Contribution changed.
 755     if (ContributionChanged)
 756       AvailableOut = BBS.Contribution;
 757   } else {
 758     // Otherwise, we need to reduce the AvailableOut set by things which are no
 759     // longer in our AvailableIn
 760     AvailableValueSet Temp = BBS.Contribution;
 761     set_union(Temp, AvailableIn);
 762     AvailableOut = std::move(Temp);
 763   }
 764
 765   LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
 766              PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
 767              dbgs() << " to ";
 768              PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
 769              dbgs() << "\n";);
 770 }
 771
 772 void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
 773                                        AvailableValueSet &Available) {
 774   if (isStatepoint(I)) {
 775     Cleared = true;
 776     Available.clear();
 777   } else if (containsGCPtrType(I.getType()))
 778     Available.insert(&I);
 779 }
 780
 781 void InstructionVerifier::verifyInstruction(
 782     const GCPtrTracker *Tracker, const Instruction &I,
 783     const AvailableValueSet &AvailableSet) {
 784   if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
 785     if (containsGCPtrType(PN->getType()))
 786       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 787         const BasicBlock *InBB = PN->getIncomingBlock(i);
 788         const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);
 789         if (!InBBS ||
 790             !Tracker->hasLiveIncomingEdge(PN, InBB))
 791           continue; // Skip dead block or dead edge.
 792
 793         const Value *InValue = PN->getIncomingValue(i);
 794
 795         if (isNotExclusivelyConstantDerived(InValue) &&
 796             !InBBS->AvailableOut.count(InValue))
 797           reportInvalidUse(*InValue, *PN);
 798       }
 799   } else if (isa<CmpInst>(I) &&
 800              containsGCPtrType(I.getOperand(0)->getType())) {
 801     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 802     enum BaseType baseTyLHS = getBaseType(LHS),
 803                   baseTyRHS = getBaseType(RHS);
 804
 805     // Returns true if LHS and RHS are unrelocated pointers and they are
 806     // valid unrelocated uses.
 807     auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
 808                                    &LHS, &RHS] () {
 809         // A cmp instruction has valid unrelocated pointer operands only if
 810         // both operands are unrelocated pointers.
 811         // In the comparison between two pointers, if one is an unrelocated
 812         // use, the other *should be* an unrelocated use, for this
 813         // instruction to contain valid unrelocated uses. This unrelocated
 814         // use can be a null constant as well, or another unrelocated
 815         // pointer.
 816         if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
 817           return false;
 818         // Constant pointers (that are not exclusively null) may have
 819         // meaning in different VMs, so we cannot reorder the compare
 820         // against constant pointers before the safepoint. In other words,
 821         // comparison of an unrelocated use against a non-null constant
 822         // maybe invalid.
 823         if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
 824              baseTyRHS == BaseType::NonConstant) ||
 825             (baseTyLHS == BaseType::NonConstant &&
 826              baseTyRHS == BaseType::ExclusivelySomeConstant))
 827           return false;
 828
 829         // If one of pointers is poisoned and other is not exclusively derived
 830         // from null it is an invalid expression: it produces poisoned result
 831         // and unless we want to track all defs (not only gc pointers) the only
 832         // option is to prohibit such instructions.
 833         if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||
 834             (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))
 835             return false;
 836
 837         // All other cases are valid cases enumerated below:
 838         // 1. Comparison between an exclusively derived null pointer and a
 839         // constant base pointer.
 840         // 2. Comparison between an exclusively derived null pointer and a
 841         // non-constant unrelocated base pointer.
 842         // 3. Comparison between 2 unrelocated pointers.
 843         // 4. Comparison between a pointer exclusively derived from null and a
 844         // non-constant poisoned pointer.
 845         return true;
 846     };
 847     if (!hasValidUnrelocatedUse()) {
 848       // Print out all non-constant derived pointers that are unrelocated
 849       // uses, which are invalid.
 850       if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
 851         reportInvalidUse(*LHS, I);
 852       if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
 853         reportInvalidUse(*RHS, I);
 854     }
 855   } else {
 856     for (const Value *V : I.operands())
 857       if (containsGCPtrType(V->getType()) &&
 858           isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
 859         reportInvalidUse(*V, I);
 860   }
 861 }
 862
 863 void InstructionVerifier::reportInvalidUse(const Value &V,
 864                                            const Instruction &I) {
 865   errs() << "Illegal use of unrelocated value found!\n";
 866   errs() << "Def: " << V << "\n";
 867   errs() << "Use: " << I << "\n";
 868   if (!PrintOnly)
 869     abort();
 870   AnyInvalidUses = true;
 871 }
 872
 873 static void Verify(const Function &F, const DominatorTree &DT,
 874                    const CFGDeadness &CD) {
 875   LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()
 876                     << "\n");
 877   if (PrintOnly)
 878     dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
 879
 880   GCPtrTracker Tracker(F, DT, CD);
 881
 882   // We now have all the information we need to decide if the use of a heap
 883   // reference is legal or not, given our safepoint semantics.
 884
 885   InstructionVerifier Verifier;
 886   GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);
 887
 888   if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
 889     dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
 890            << "\n";
 891   }
 892 }