contrib/llvm-project/llvm/lib/IR/SafepointIRVerifier.cpp

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