LCOV - code coverage report
Current view: top level - lib/IR - SafepointIRVerifier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 183 192 95.3 %
Date: 2018-06-17 00:07:59 Functions: 25 29 86.2 %
Legend: Lines: hit not hit

          Line data    Source code
       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      101169 : static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
      60      101169 :                                cl::init(false));
      61             : 
      62             : static void Verify(const Function &F, const DominatorTree &DT);
      63             : 
      64             : namespace {
      65          16 : struct SafepointIRVerifier : public FunctionPass {
      66             :   static char ID; // Pass identification, replacement for typeid
      67             :   DominatorTree DT;
      68          16 :   SafepointIRVerifier() : FunctionPass(ID) {
      69           8 :     initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
      70           8 :   }
      71             : 
      72          34 :   bool runOnFunction(Function &F) override {
      73          34 :     DT.recalculate(F);
      74          34 :     Verify(F, DT);
      75          34 :     return false; // no modifications
      76             :   }
      77             : 
      78           8 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      79             :     AU.setPreservesAll();
      80           8 :   }
      81             : 
      82           0 :   StringRef getPassName() const override { return "safepoint verifier"; }
      83             : };
      84             : } // namespace
      85             : 
      86           0 : void llvm::verifySafepointIR(Function &F) {
      87           0 :   SafepointIRVerifier pass;
      88             :   pass.runOnFunction(F);
      89           0 : }
      90             : 
      91             : char SafepointIRVerifier::ID = 0;
      92             : 
      93           0 : FunctionPass *llvm::createSafepointIRVerifierPass() {
      94           0 :   return new SafepointIRVerifier();
      95             : }
      96             : 
      97       30563 : INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
      98             :                       "Safepoint IR Verifier", false, true)
      99      122268 : 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         663 :     return (1 == PT->getAddressSpace());
     108             :   return false;
     109             : }
     110             : 
     111        1560 : static bool containsGCPtrType(Type *Ty) {
     112         663 :   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           0 :     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         300 : 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         247 : static enum BaseType getBaseType(const Value *Val) {
     177             : 
     178             :   SmallVector<const Value *, 32> Worklist;
     179             :   DenseSet<const Value *> Visited;
     180             :   bool isExclusivelyDerivedFromNull = true;
     181         247 :   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         773 :   while(!Worklist.empty()) {
     186         454 :     const Value *V = Worklist.pop_back_val();
     187         454 :     if (!Visited.insert(V).second)
     188         265 :       continue;
     189             : 
     190         502 :     if (const auto *CI = dyn_cast<CastInst>(V)) {
     191          50 :       Worklist.push_back(CI->stripPointerCasts());
     192          50 :       continue;
     193             :     }
     194         105 :     if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
     195         105 :       Worklist.push_back(GEP->getPointerOperand());
     196         105 :       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         210 :       for (Value *InV: PN->incoming_values())
     202          84 :         Worklist.push_back(InV);
     203          42 :       continue;
     204             :     }
     205           2 :     if (const auto *SI = dyn_cast<SelectInst>(V)) {
     206             :       // Push in the true and false values
     207           2 :       Worklist.push_back(SI->getTrueValue());
     208           2 :       Worklist.push_back(SI->getFalseValue());
     209           2 :       continue;
     210             :     }
     211         315 :     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          62 :       if (V != Constant::getNullValue(V->getType()))
     215             :         isExclusivelyDerivedFromNull = false;
     216             :       // Continue processing the remaining values to make sure it's exclusively
     217             :       // constant.
     218          62 :       continue;
     219             :     }
     220             :     // At this point, we know that the base pointer is not exclusively
     221             :     // constant.
     222         191 :     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          56 :   return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
     227             :                                       : BaseType::ExclusivelySomeConstant;
     228             : }
     229             : 
     230             : static bool isNotExclusivelyConstantDerived(const Value *V) {
     231         209 :   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         102 : 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             :   /// Returns true for reachable blocks that are verified, the other blocks are
     322             :   /// ignored.
     323             :   bool isMapped(const BasicBlock *BB) const {
     324         139 :     return BlockMap.find(BB) != BlockMap.end();
     325             :   }
     326             : 
     327             : private:
     328             :   /// Returns true if the instruction may be safely skipped during verification.
     329             :   bool instructionMayBeSkipped(const Instruction *I) const;
     330             : 
     331             :   /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
     332             :   /// each of them until it converges.
     333             :   void recalculateBBsStates();
     334             : 
     335             :   /// Remove from Contribution all defs that legally produce unrelocated
     336             :   /// pointers and saves them to ValidUnrelocatedDefs.
     337             :   /// Though Contribution should belong to BBS it is passed separately with
     338             :   /// different const-modifier in order to emphasize (and guarantee) that only
     339             :   /// Contribution will be changed.
     340             :   /// Returns true if Contribution was changed otherwise false.
     341             :   bool removeValidUnrelocatedDefs(const BasicBlock *BB,
     342             :                                   const BasicBlockState *BBS,
     343             :                                   AvailableValueSet &Contribution);
     344             : 
     345             :   /// Gather all the definitions dominating the start of BB into Result. This is
     346             :   /// simply the defs introduced by every dominating basic block and the
     347             :   /// function arguments.
     348             :   void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
     349             :                             const DominatorTree &DT);
     350             : 
     351             :   /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
     352             :   /// which is the BasicBlockState for BB.
     353             :   /// ContributionChanged is set when the verifier runs for the first time
     354             :   /// (in this case Contribution was changed from 'empty' to its initial state)
     355             :   /// or when Contribution of this BB was changed since last computation.
     356             :   static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
     357             :                             bool ContributionChanged);
     358             : 
     359             :   /// Model the effect of an instruction on the set of available values.
     360             :   static void transferInstruction(const Instruction &I, bool &Cleared,
     361             :                                   AvailableValueSet &Available);
     362             : };
     363             : 
     364             : /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
     365             : /// instruction (which uses heap reference) is legal or not, given our safepoint
     366             : /// semantics.
     367             : class InstructionVerifier {
     368             :   bool AnyInvalidUses = false;
     369             : 
     370             : public:
     371             :   void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
     372             :                          const AvailableValueSet &AvailableSet);
     373             : 
     374          34 :   bool hasAnyInvalidUses() const { return AnyInvalidUses; }
     375             : 
     376             : private:
     377             :   void reportInvalidUse(const Value &V, const Instruction &I);
     378             : };
     379             : } // end anonymous namespace
     380             : 
     381          68 : GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT) : F(F) {
     382             :   // First, calculate Contribution of each BB.
     383         111 :   for (const BasicBlock &BB : F)
     384          77 :     if (DT.isReachableFromEntry(&BB)) {
     385          75 :       BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
     386         309 :       for (const auto &I : BB)
     387         234 :         transferInstruction(I, BBS->Cleared, BBS->Contribution);
     388         150 :       BlockMap[&BB] = BBS;
     389             :     }
     390             : 
     391             :   // Initialize AvailableIn/Out sets of each BB using only information about
     392             :   // dominating BBs.
     393         143 :   for (auto &BBI : BlockMap) {
     394          75 :     gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
     395          75 :     transferBlock(BBI.first, *BBI.second, true);
     396             :   }
     397             : 
     398             :   // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
     399             :   // sets of each BB until it converges. If any def is proved to be an
     400             :   // unrelocated pointer, it will be removed from all BBSs.
     401          34 :   recalculateBBsStates();
     402          34 : }
     403             : 
     404             : BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
     405          91 :   auto it = BlockMap.find(BB);
     406             :   assert(it != BlockMap.end() &&
     407             :          "No such BB in BlockMap! Probably BB from another function");
     408          91 :   return it->second;
     409             : }
     410             : 
     411             : const BasicBlockState *GCPtrTracker::getBasicBlockState(
     412             :     const BasicBlock *BB) const {
     413             :   return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
     414             : }
     415             : 
     416         234 : bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
     417             :   // Poisoned defs are skipped since they are always safe by itself by
     418             :   // definition (for details see comment to this class).
     419         234 :   return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
     420             : }
     421             : 
     422          34 : void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
     423             :                                   InstructionVerifier &Verifier) {
     424             :   // We need RPO here to a) report always the first error b) report errors in
     425             :   // same order from run to run.
     426          34 :   ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
     427         109 :   for (const BasicBlock *BB : RPOT) {
     428             :     BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
     429             :     // We destructively modify AvailableIn as we traverse the block instruction
     430             :     // by instruction.
     431          75 :     AvailableValueSet &AvailableSet = BBS->AvailableIn;
     432         309 :     for (const Instruction &I : *BB) {
     433         234 :       if (Tracker.instructionMayBeSkipped(&I))
     434          32 :         continue; // This instruction shouldn't be added to AvailableSet.
     435             : 
     436         202 :       Verifier.verifyInstruction(&Tracker, I, AvailableSet);
     437             : 
     438             :       // Model the effect of current instruction on AvailableSet to keep the set
     439             :       // relevant at each point of BB.
     440         202 :       bool Cleared = false;
     441         202 :       transferInstruction(I, Cleared, AvailableSet);
     442             :       (void)Cleared;
     443             :     }
     444             :   }
     445          34 : }
     446             : 
     447          34 : void GCPtrTracker::recalculateBBsStates() {
     448          34 :   SetVector<const BasicBlock *> Worklist;
     449             :   // TODO: This order is suboptimal, it's better to replace it with priority
     450             :   // queue where priority is RPO number of BB.
     451         143 :   for (auto &BBI : BlockMap)
     452          75 :     Worklist.insert(BBI.first);
     453             : 
     454             :   // This loop iterates the AvailableIn/Out sets until it converges.
     455             :   // The AvailableIn and AvailableOut sets decrease as we iterate.
     456         113 :   while (!Worklist.empty()) {
     457          79 :     const BasicBlock *BB = Worklist.pop_back_val();
     458          79 :     BasicBlockState *BBS = BlockMap[BB];
     459             : 
     460             :     size_t OldInCount = BBS->AvailableIn.size();
     461         359 :     for (const BasicBlock *PBB : predecessors(BB))
     462          61 :       if (isMapped(PBB))
     463          60 :         set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
     464             : 
     465             :     assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
     466             : 
     467             :     bool InputsChanged = OldInCount != BBS->AvailableIn.size();
     468             :     bool ContributionChanged =
     469          79 :         removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
     470          79 :     if (!InputsChanged && !ContributionChanged)
     471          57 :       continue;
     472             : 
     473             :     size_t OldOutCount = BBS->AvailableOut.size();
     474          22 :     transferBlock(BB, *BBS, ContributionChanged);
     475          22 :     if (OldOutCount != BBS->AvailableOut.size()) {
     476             :       assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
     477          40 :       Worklist.insert(succ_begin(BB), succ_end(BB));
     478             :     }
     479             :   }
     480          34 : }
     481             : 
     482          79 : bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
     483             :                                               const BasicBlockState *BBS,
     484             :                                               AvailableValueSet &Contribution) {
     485             :   assert(&BBS->Contribution == &Contribution &&
     486             :          "Passed Contribution should be from the passed BasicBlockState!");
     487             :   AvailableValueSet AvailableSet = BBS->AvailableIn;
     488             :   bool ContributionChanged = false;
     489             :   // For explanation why instructions are processed this way see
     490             :   // "Rules of deriving" in the comment to this class.
     491         334 :   for (const Instruction &I : *BB) {
     492             :     bool ValidUnrelocatedPointerDef = false;
     493             :     bool PoisonedPointerDef = false;
     494             :     // TODO: `select` instructions should be handled here too.
     495             :     if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
     496          27 :       if (containsGCPtrType(PN->getType())) {
     497             :         // If both is true, output is poisoned.
     498             :         bool HasRelocatedInputs = false;
     499             :         bool HasUnrelocatedInputs = false;
     500         131 :         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     501          54 :           const BasicBlock *InBB = PN->getIncomingBlock(i);
     502          54 :           if (!isMapped(InBB))
     503           1 :               continue;
     504             :           const Value *InValue = PN->getIncomingValue(i);
     505             : 
     506          53 :           if (isNotExclusivelyConstantDerived(InValue)) {
     507             :             if (isValuePoisoned(InValue)) {
     508             :               // If any of inputs is poisoned, output is always poisoned too.
     509             :               HasRelocatedInputs = true;
     510             :               HasUnrelocatedInputs = true;
     511           2 :               break;
     512             :             }
     513          42 :             if (BlockMap[InBB]->AvailableOut.count(InValue))
     514             :               HasRelocatedInputs = true;
     515             :             else
     516             :               HasUnrelocatedInputs = true;
     517             :           }
     518             :         }
     519          25 :         if (HasUnrelocatedInputs) {
     520          10 :           if (HasRelocatedInputs)
     521             :             PoisonedPointerDef = true;
     522             :           else
     523             :             ValidUnrelocatedPointerDef = true;
     524             :         }
     525             :       }
     526         284 :     } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
     527          56 :                containsGCPtrType(I.getType())) {
     528             :       // GEP/bitcast of unrelocated pointer is legal by itself but this def
     529             :       // shouldn't appear in any AvailableSet.
     530         236 :       for (const Value *V : I.operands())
     531         140 :         if (containsGCPtrType(V->getType()) &&
     532          84 :             isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
     533             :           if (isValuePoisoned(V))
     534             :             PoisonedPointerDef = true;
     535             :           else
     536             :             ValidUnrelocatedPointerDef = true;
     537             :           break;
     538             :         }
     539             :     }
     540             :     assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
     541             :            "Value cannot be both unrelocated and poisoned!");
     542             :     if (ValidUnrelocatedPointerDef) {
     543             :       // Remove def of unrelocated pointer from Contribution of this BB and
     544             :       // trigger update of all its successors.
     545          46 :       Contribution.erase(&I);
     546          46 :       PoisonedDefs.erase(&I);
     547          46 :       ValidUnrelocatedDefs.insert(&I);
     548             :       LLVM_DEBUG(dbgs() << "Removing urelocated " << I
     549             :                         << " from Contribution of " << BB->getName() << "\n");
     550             :       ContributionChanged = true;
     551         232 :     } else if (PoisonedPointerDef) {
     552             :       // Mark pointer as poisoned, remove its def from Contribution and trigger
     553             :       // update of all successors.
     554          18 :       Contribution.erase(&I);
     555          18 :       PoisonedDefs.insert(&I);
     556             :       LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
     557             :                         << BB->getName() << "\n");
     558             :       ContributionChanged = true;
     559             :     } else {
     560         223 :       bool Cleared = false;
     561         223 :       transferInstruction(I, Cleared, AvailableSet);
     562             :       (void)Cleared;
     563             :     }
     564             :   }
     565          79 :   return ContributionChanged;
     566             : }
     567             : 
     568          75 : void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
     569             :                                         AvailableValueSet &Result,
     570             :                                         const DominatorTree &DT) {
     571             :   DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
     572             : 
     573             :   assert(DTN && "Unreachable blocks are ignored");
     574         117 :   while (DTN->getIDom()) {
     575             :     DTN = DTN->getIDom();
     576          90 :     const auto &Defs = BlockMap[DTN->getBlock()]->Contribution;
     577          90 :     Result.insert(Defs.begin(), Defs.end());
     578             :     // If this block is 'Cleared', then nothing LiveIn to this block can be
     579             :     // available after this block completes.  Note: This turns out to be
     580             :     // really important for reducing memory consuption of the initial available
     581             :     // sets and thus peak memory usage by this verifier.
     582          90 :     if (BlockMap[DTN->getBlock()]->Cleared)
     583             :       return;
     584             :   }
     585             : 
     586         193 :   for (const Argument &A : BB->getParent()->args())
     587         121 :     if (containsGCPtrType(A.getType()))
     588         158 :       Result.insert(&A);
     589             : }
     590             : 
     591          97 : void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
     592             :                                  bool ContributionChanged) {
     593          97 :   const AvailableValueSet &AvailableIn = BBS.AvailableIn;
     594             :   AvailableValueSet &AvailableOut = BBS.AvailableOut;
     595             : 
     596          97 :   if (BBS.Cleared) {
     597             :     // AvailableOut will change only when Contribution changed.
     598          44 :     if (ContributionChanged)
     599             :       AvailableOut = BBS.Contribution;
     600             :   } else {
     601             :     // Otherwise, we need to reduce the AvailableOut set by things which are no
     602             :     // longer in our AvailableIn
     603             :     AvailableValueSet Temp = BBS.Contribution;
     604          53 :     set_union(Temp, AvailableIn);
     605             :     AvailableOut = std::move(Temp);
     606             :   }
     607             : 
     608             :   LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
     609             :              PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
     610             :              dbgs() << " to ";
     611             :              PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
     612             :              dbgs() << "\n";);
     613          97 : }
     614             : 
     615         659 : void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
     616             :                                        AvailableValueSet &Available) {
     617         659 :   if (isStatepoint(I)) {
     618         112 :     Cleared = true;
     619             :     Available.clear();
     620         547 :   } else if (containsGCPtrType(I.getType()))
     621         484 :     Available.insert(&I);
     622         659 : }
     623             : 
     624         202 : void InstructionVerifier::verifyInstruction(
     625             :     const GCPtrTracker *Tracker, const Instruction &I,
     626             :     const AvailableValueSet &AvailableSet) {
     627             :   if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
     628          12 :     if (containsGCPtrType(PN->getType()))
     629          60 :       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     630             :         const BasicBlock *InBB = PN->getIncomingBlock(i);
     631          24 :         if (!Tracker->isMapped(InBB))
     632           1 :             continue;
     633             :         const Value *InValue = PN->getIncomingValue(i);
     634             : 
     635          23 :         if (isNotExclusivelyConstantDerived(InValue) &&
     636             :             !Tracker->getBasicBlockState(InBB)->AvailableOut.count(InValue))
     637           0 :           reportInvalidUse(*InValue, *PN);
     638             :       }
     639          19 :   } else if (isa<CmpInst>(I) &&
     640          38 :              containsGCPtrType(I.getOperand(0)->getType())) {
     641          38 :     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
     642          19 :     enum BaseType baseTyLHS = getBaseType(LHS),
     643          19 :                   baseTyRHS = getBaseType(RHS);
     644             : 
     645             :     // Returns true if LHS and RHS are unrelocated pointers and they are
     646             :     // valid unrelocated uses.
     647             :     auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
     648          90 :                                    &LHS, &RHS] () {
     649             :         // A cmp instruction has valid unrelocated pointer operands only if
     650             :         // both operands are unrelocated pointers.
     651             :         // In the comparison between two pointers, if one is an unrelocated
     652             :         // use, the other *should be* an unrelocated use, for this
     653             :         // instruction to contain valid unrelocated uses. This unrelocated
     654             :         // use can be a null constant as well, or another unrelocated
     655             :         // pointer.
     656          37 :         if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
     657             :           return false;
     658             :         // Constant pointers (that are not exclusively null) may have
     659             :         // meaning in different VMs, so we cannot reorder the compare
     660             :         // against constant pointers before the safepoint. In other words,
     661             :         // comparison of an unrelocated use against a non-null constant
     662             :         // maybe invalid.
     663          28 :         if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
     664          27 :              baseTyRHS == BaseType::NonConstant) ||
     665          26 :             (baseTyLHS == BaseType::NonConstant &&
     666          13 :              baseTyRHS == BaseType::ExclusivelySomeConstant))
     667             :           return false;
     668             : 
     669             :         // If one of pointers is poisoned and other is not exclusively derived
     670             :         // from null it is an invalid expression: it produces poisoned result
     671             :         // and unless we want to track all defs (not only gc pointers) the only
     672             :         // option is to prohibit such instructions.
     673          15 :         if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||
     674          10 :             (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))
     675             :             return false;
     676             : 
     677             :         // All other cases are valid cases enumerated below:
     678             :         // 1. Comparison between an exclusively derived null pointer and a
     679             :         // constant base pointer.
     680             :         // 2. Comparison between an exclusively derived null pointer and a
     681             :         // non-constant unrelocated base pointer.
     682             :         // 3. Comparison between 2 unrelocated pointers.
     683             :         // 4. Comparison between a pointer exclusively derived from null and a
     684             :         // non-constant poisoned pointer.
     685             :         return true;
     686          19 :     };
     687          19 :     if (!hasValidUnrelocatedUse()) {
     688             :       // Print out all non-constant derived pointers that are unrelocated
     689             :       // uses, which are invalid.
     690           9 :       if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
     691           7 :         reportInvalidUse(*LHS, I);
     692           9 :       if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
     693           3 :         reportInvalidUse(*RHS, I);
     694             :     }
     695             :   } else {
     696        1730 :     for (const Value *V : I.operands())
     697         771 :       if (containsGCPtrType(V->getType()) &&
     698         694 :           isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
     699           8 :         reportInvalidUse(*V, I);
     700             :   }
     701         202 : }
     702             : 
     703          18 : void InstructionVerifier::reportInvalidUse(const Value &V,
     704             :                                            const Instruction &I) {
     705          18 :   errs() << "Illegal use of unrelocated value found!\n";
     706          36 :   errs() << "Def: " << V << "\n";
     707          36 :   errs() << "Use: " << I << "\n";
     708          18 :   if (!PrintOnly)
     709           0 :     abort();
     710          18 :   AnyInvalidUses = true;
     711          18 : }
     712             : 
     713          34 : static void Verify(const Function &F, const DominatorTree &DT) {
     714             :   LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()
     715             :                     << "\n");
     716          34 :   if (PrintOnly)
     717          34 :     dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
     718             : 
     719          68 :   GCPtrTracker Tracker(F, DT);
     720             : 
     721             :   // We now have all the information we need to decide if the use of a heap
     722             :   // reference is legal or not, given our safepoint semantics.
     723             : 
     724          34 :   InstructionVerifier Verifier;
     725          34 :   GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);
     726             : 
     727          68 :   if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
     728          18 :     dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
     729          18 :            << "\n";
     730             :   }
     731      303541 : }

Generated by: LCOV version 1.13