| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/PassAnalysisSupport.h |
| Warning: | line 242, column 22 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 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" "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")((void)0); | |||
| 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")((void)0); | |||
| 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() &&((void)0) | |||
| 108 | "edge must be operand of terminator")((void)0); | |||
| 109 | assert(cast_or_null<BasicBlock>(U->get()) &&((void)0) | |||
| 110 | "edge must refer to basic block")((void)0); | |||
| 111 | assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) &&((void)0) | |||
| 112 | "isDeadEdge() must be applied to edge from live block")((void)0); | |||
| 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")((void)0); | |||
| 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",static void *initializeSafepointIRVerifierPassOnce(PassRegistry &Registry) { | |||
| 250 | "Safepoint IR Verifier", false, false)static void *initializeSafepointIRVerifierPassOnce(PassRegistry &Registry) { | |||
| 251 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
| 252 | INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",PassInfo *PI = new PassInfo( "Safepoint IR Verifier", "verify-safepoint-ir" , &SafepointIRVerifier::ID, PassInfo::NormalCtor_t(callDefaultCtor <SafepointIRVerifier>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeSafepointIRVerifierPassFlag ; void llvm::initializeSafepointIRVerifierPass(PassRegistry & Registry) { llvm::call_once(InitializeSafepointIRVerifierPassFlag , initializeSafepointIRVerifierPassOnce, std::ref(Registry)); } | |||
| 253 | "Safepoint IR Verifier", false, false)PassInfo *PI = new PassInfo( "Safepoint IR Verifier", "verify-safepoint-ir" , &SafepointIRVerifier::ID, PassInfo::NormalCtor_t(callDefaultCtor <SafepointIRVerifier>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeSafepointIRVerifierPassFlag ; void llvm::initializeSafepointIRVerifierPass(PassRegistry & Registry) { llvm::call_once(InitializeSafepointIRVerifierPassFlag , initializeSafepointIRVerifierPassOnce, std::ref(Registry)); } | |||
| 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 | append_range(Worklist, PN->incoming_values()); | |||
| 354 | continue; | |||
| 355 | } | |||
| 356 | if (const auto *SI = dyn_cast<SelectInst>(V)) { | |||
| 357 | // Push in the true and false values | |||
| 358 | Worklist.push_back(SI->getTrueValue()); | |||
| 359 | Worklist.push_back(SI->getFalseValue()); | |||
| 360 | continue; | |||
| 361 | } | |||
| 362 | if (isa<Constant>(V)) { | |||
| 363 | // We found at least one base pointer which is non-null, so this derived | |||
| 364 | // pointer is not exclusively derived from null. | |||
| 365 | if (V != Constant::getNullValue(V->getType())) | |||
| 366 | isExclusivelyDerivedFromNull = false; | |||
| 367 | // Continue processing the remaining values to make sure it's exclusively | |||
| 368 | // constant. | |||
| 369 | continue; | |||
| 370 | } | |||
| 371 | // At this point, we know that the base pointer is not exclusively | |||
| 372 | // constant. | |||
| 373 | return BaseType::NonConstant; | |||
| 374 | } | |||
| 375 | // Now, we know that the base pointer is exclusively constant, but we need to | |||
| 376 | // differentiate between exclusive null constant and non-null constant. | |||
| 377 | return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull | |||
| 378 | : BaseType::ExclusivelySomeConstant; | |||
| 379 | } | |||
| 380 | ||||
| 381 | static bool isNotExclusivelyConstantDerived(const Value *V) { | |||
| 382 | return getBaseType(V) == BaseType::NonConstant; | |||
| 383 | } | |||
| 384 | ||||
| 385 | namespace { | |||
| 386 | class InstructionVerifier; | |||
| 387 | ||||
| 388 | /// Builds BasicBlockState for each BB of the function. | |||
| 389 | /// It can traverse function for verification and provides all required | |||
| 390 | /// information. | |||
| 391 | /// | |||
| 392 | /// GC pointer may be in one of three states: relocated, unrelocated and | |||
| 393 | /// poisoned. | |||
| 394 | /// Relocated pointer may be used without any restrictions. | |||
| 395 | /// Unrelocated pointer cannot be dereferenced, passed as argument to any call | |||
| 396 | /// or returned. Unrelocated pointer may be safely compared against another | |||
| 397 | /// unrelocated pointer or against a pointer exclusively derived from null. | |||
| 398 | /// Poisoned pointers are produced when we somehow derive pointer from relocated | |||
| 399 | /// and unrelocated pointers (e.g. phi, select). This pointers may be safely | |||
| 400 | /// used in a very limited number of situations. Currently the only way to use | |||
| 401 | /// it is comparison against constant exclusively derived from null. All | |||
| 402 | /// limitations arise due to their undefined state: this pointers should be | |||
| 403 | /// treated as relocated and unrelocated simultaneously. | |||
| 404 | /// Rules of deriving: | |||
| 405 | /// R + U = P - that's where the poisoned pointers come from | |||
| 406 | /// P + X = P | |||
| 407 | /// U + U = U | |||
| 408 | /// R + R = R | |||
| 409 | /// X + C = X | |||
| 410 | /// Where "+" - any operation that somehow derive pointer, U - unrelocated, | |||
| 411 | /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or | |||
| 412 | /// nothing (in case when "+" is unary operation). | |||
| 413 | /// Deriving of pointers by itself is always safe. | |||
| 414 | /// NOTE: when we are making decision on the status of instruction's result: | |||
| 415 | /// a) for phi we need to check status of each input *at the end of | |||
| 416 | /// corresponding predecessor BB*. | |||
| 417 | /// b) for other instructions we need to check status of each input *at the | |||
| 418 | /// current point*. | |||
| 419 | /// | |||
| 420 | /// FIXME: This works fairly well except one case | |||
| 421 | /// bb1: | |||
| 422 | /// p = *some GC-ptr def* | |||
| 423 | /// p1 = gep p, offset | |||
| 424 | /// / | | |||
| 425 | /// / | | |||
| 426 | /// bb2: | | |||
| 427 | /// safepoint | | |||
| 428 | /// \ | | |||
| 429 | /// \ | | |||
| 430 | /// bb3: | |||
| 431 | /// p2 = phi [p, bb2] [p1, bb1] | |||
| 432 | /// p3 = phi [p, bb2] [p, bb1] | |||
| 433 | /// here p and p1 is unrelocated | |||
| 434 | /// p2 and p3 is poisoned (though they shouldn't be) | |||
| 435 | /// | |||
| 436 | /// This leads to some weird results: | |||
| 437 | /// cmp eq p, p2 - illegal instruction (false-positive) | |||
| 438 | /// cmp eq p1, p2 - illegal instruction (false-positive) | |||
| 439 | /// cmp eq p, p3 - illegal instruction (false-positive) | |||
| 440 | /// cmp eq p, p1 - ok | |||
| 441 | /// To fix this we need to introduce conception of generations and be able to | |||
| 442 | /// check if two values belong to one generation or not. This way p2 will be | |||
| 443 | /// considered to be unrelocated and no false alarm will happen. | |||
| 444 | class GCPtrTracker { | |||
| 445 | const Function &F; | |||
| 446 | const CFGDeadness &CD; | |||
| 447 | SpecificBumpPtrAllocator<BasicBlockState> BSAllocator; | |||
| 448 | DenseMap<const BasicBlock *, BasicBlockState *> BlockMap; | |||
| 449 | // This set contains defs of unrelocated pointers that are proved to be legal | |||
| 450 | // and don't need verification. | |||
| 451 | DenseSet<const Instruction *> ValidUnrelocatedDefs; | |||
| 452 | // This set contains poisoned defs. They can be safely ignored during | |||
| 453 | // verification too. | |||
| 454 | DenseSet<const Value *> PoisonedDefs; | |||
| 455 | ||||
| 456 | public: | |||
| 457 | GCPtrTracker(const Function &F, const DominatorTree &DT, | |||
| 458 | const CFGDeadness &CD); | |||
| 459 | ||||
| 460 | bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const { | |||
| 461 | return CD.hasLiveIncomingEdge(PN, InBB); | |||
| 462 | } | |||
| 463 | ||||
| 464 | BasicBlockState *getBasicBlockState(const BasicBlock *BB); | |||
| 465 | const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const; | |||
| 466 | ||||
| 467 | bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); } | |||
| 468 | ||||
| 469 | /// Traverse each BB of the function and call | |||
| 470 | /// InstructionVerifier::verifyInstruction for each possibly invalid | |||
| 471 | /// instruction. | |||
| 472 | /// It destructively modifies GCPtrTracker so it's passed via rvalue reference | |||
| 473 | /// in order to prohibit further usages of GCPtrTracker as it'll be in | |||
| 474 | /// inconsistent state. | |||
| 475 | static void verifyFunction(GCPtrTracker &&Tracker, | |||
| 476 | InstructionVerifier &Verifier); | |||
| 477 | ||||
| 478 | /// Returns true for reachable and live blocks. | |||
| 479 | bool isMapped(const BasicBlock *BB) const { | |||
| 480 | return BlockMap.find(BB) != BlockMap.end(); | |||
| 481 | } | |||
| 482 | ||||
| 483 | private: | |||
| 484 | /// Returns true if the instruction may be safely skipped during verification. | |||
| 485 | bool instructionMayBeSkipped(const Instruction *I) const; | |||
| 486 | ||||
| 487 | /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for | |||
| 488 | /// each of them until it converges. | |||
| 489 | void recalculateBBsStates(); | |||
| 490 | ||||
| 491 | /// Remove from Contribution all defs that legally produce unrelocated | |||
| 492 | /// pointers and saves them to ValidUnrelocatedDefs. | |||
| 493 | /// Though Contribution should belong to BBS it is passed separately with | |||
| 494 | /// different const-modifier in order to emphasize (and guarantee) that only | |||
| 495 | /// Contribution will be changed. | |||
| 496 | /// Returns true if Contribution was changed otherwise false. | |||
| 497 | bool removeValidUnrelocatedDefs(const BasicBlock *BB, | |||
| 498 | const BasicBlockState *BBS, | |||
| 499 | AvailableValueSet &Contribution); | |||
| 500 | ||||
| 501 | /// Gather all the definitions dominating the start of BB into Result. This is | |||
| 502 | /// simply the defs introduced by every dominating basic block and the | |||
| 503 | /// function arguments. | |||
| 504 | void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result, | |||
| 505 | const DominatorTree &DT); | |||
| 506 | ||||
| 507 | /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS, | |||
| 508 | /// which is the BasicBlockState for BB. | |||
| 509 | /// ContributionChanged is set when the verifier runs for the first time | |||
| 510 | /// (in this case Contribution was changed from 'empty' to its initial state) | |||
| 511 | /// or when Contribution of this BB was changed since last computation. | |||
| 512 | static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS, | |||
| 513 | bool ContributionChanged); | |||
| 514 | ||||
| 515 | /// Model the effect of an instruction on the set of available values. | |||
| 516 | static void transferInstruction(const Instruction &I, bool &Cleared, | |||
| 517 | AvailableValueSet &Available); | |||
| 518 | }; | |||
| 519 | ||||
| 520 | /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the | |||
| 521 | /// instruction (which uses heap reference) is legal or not, given our safepoint | |||
| 522 | /// semantics. | |||
| 523 | class InstructionVerifier { | |||
| 524 | bool AnyInvalidUses = false; | |||
| 525 | ||||
| 526 | public: | |||
| 527 | void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I, | |||
| 528 | const AvailableValueSet &AvailableSet); | |||
| 529 | ||||
| 530 | bool hasAnyInvalidUses() const { return AnyInvalidUses; } | |||
| 531 | ||||
| 532 | private: | |||
| 533 | void reportInvalidUse(const Value &V, const Instruction &I); | |||
| 534 | }; | |||
| 535 | } // end anonymous namespace | |||
| 536 | ||||
| 537 | GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT, | |||
| 538 | const CFGDeadness &CD) : F(F), CD(CD) { | |||
| 539 | // Calculate Contribution of each live BB. | |||
| 540 | // Allocate BB states for live blocks. | |||
| 541 | for (const BasicBlock &BB : F) | |||
| 542 | if (!CD.isDeadBlock(&BB)) { | |||
| 543 | BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState; | |||
| 544 | for (const auto &I : BB) | |||
| 545 | transferInstruction(I, BBS->Cleared, BBS->Contribution); | |||
| 546 | BlockMap[&BB] = BBS; | |||
| 547 | } | |||
| 548 | ||||
| 549 | // Initialize AvailableIn/Out sets of each BB using only information about | |||
| 550 | // dominating BBs. | |||
| 551 | for (auto &BBI : BlockMap) { | |||
| 552 | gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT); | |||
| 553 | transferBlock(BBI.first, *BBI.second, true); | |||
| 554 | } | |||
| 555 | ||||
| 556 | // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out | |||
| 557 | // sets of each BB until it converges. If any def is proved to be an | |||
| 558 | // unrelocated pointer, it will be removed from all BBSs. | |||
| 559 | recalculateBBsStates(); | |||
| 560 | } | |||
| 561 | ||||
| 562 | BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) { | |||
| 563 | return BlockMap.lookup(BB); | |||
| 564 | } | |||
| 565 | ||||
| 566 | const BasicBlockState *GCPtrTracker::getBasicBlockState( | |||
| 567 | const BasicBlock *BB) const { | |||
| 568 | return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB); | |||
| 569 | } | |||
| 570 | ||||
| 571 | bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const { | |||
| 572 | // Poisoned defs are skipped since they are always safe by itself by | |||
| 573 | // definition (for details see comment to this class). | |||
| 574 | return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I); | |||
| 575 | } | |||
| 576 | ||||
| 577 | void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker, | |||
| 578 | InstructionVerifier &Verifier) { | |||
| 579 | // We need RPO here to a) report always the first error b) report errors in | |||
| 580 | // same order from run to run. | |||
| 581 | ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F); | |||
| 582 | for (const BasicBlock *BB : RPOT) { | |||
| 583 | BasicBlockState *BBS = Tracker.getBasicBlockState(BB); | |||
| 584 | if (!BBS) | |||
| 585 | continue; | |||
| 586 | ||||
| 587 | // We destructively modify AvailableIn as we traverse the block instruction | |||
| 588 | // by instruction. | |||
| 589 | AvailableValueSet &AvailableSet = BBS->AvailableIn; | |||
| 590 | for (const Instruction &I : *BB) { | |||
| 591 | if (Tracker.instructionMayBeSkipped(&I)) | |||
| 592 | continue; // This instruction shouldn't be added to AvailableSet. | |||
| 593 | ||||
| 594 | Verifier.verifyInstruction(&Tracker, I, AvailableSet); | |||
| 595 | ||||
| 596 | // Model the effect of current instruction on AvailableSet to keep the set | |||
| 597 | // relevant at each point of BB. | |||
| 598 | bool Cleared = false; | |||
| 599 | transferInstruction(I, Cleared, AvailableSet); | |||
| 600 | (void)Cleared; | |||
| 601 | } | |||
| 602 | } | |||
| 603 | } | |||
| 604 | ||||
| 605 | void GCPtrTracker::recalculateBBsStates() { | |||
| 606 | SetVector<const BasicBlock *> Worklist; | |||
| 607 | // TODO: This order is suboptimal, it's better to replace it with priority | |||
| 608 | // queue where priority is RPO number of BB. | |||
| 609 | for (auto &BBI : BlockMap) | |||
| 610 | Worklist.insert(BBI.first); | |||
| 611 | ||||
| 612 | // This loop iterates the AvailableIn/Out sets until it converges. | |||
| 613 | // The AvailableIn and AvailableOut sets decrease as we iterate. | |||
| 614 | while (!Worklist.empty()) { | |||
| 615 | const BasicBlock *BB = Worklist.pop_back_val(); | |||
| 616 | BasicBlockState *BBS = getBasicBlockState(BB); | |||
| 617 | if (!BBS) | |||
| 618 | continue; // Ignore dead successors. | |||
| 619 | ||||
| 620 | size_t OldInCount = BBS->AvailableIn.size(); | |||
| 621 | for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { | |||
| 622 | const BasicBlock *PBB = *PredIt; | |||
| 623 | BasicBlockState *PBBS = getBasicBlockState(PBB); | |||
| 624 | if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt))) | |||
| 625 | set_intersect(BBS->AvailableIn, PBBS->AvailableOut); | |||
| 626 | } | |||
| 627 | ||||
| 628 | assert(OldInCount >= BBS->AvailableIn.size() && "invariant!")((void)0); | |||
| 629 | ||||
| 630 | bool InputsChanged = OldInCount != BBS->AvailableIn.size(); | |||
| 631 | bool ContributionChanged = | |||
| 632 | removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution); | |||
| 633 | if (!InputsChanged && !ContributionChanged) | |||
| 634 | continue; | |||
| 635 | ||||
| 636 | size_t OldOutCount = BBS->AvailableOut.size(); | |||
| 637 | transferBlock(BB, *BBS, ContributionChanged); | |||
| 638 | if (OldOutCount != BBS->AvailableOut.size()) { | |||
| 639 | assert(OldOutCount > BBS->AvailableOut.size() && "invariant!")((void)0); | |||
| 640 | Worklist.insert(succ_begin(BB), succ_end(BB)); | |||
| 641 | } | |||
| 642 | } | |||
| 643 | } | |||
| 644 | ||||
| 645 | bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB, | |||
| 646 | const BasicBlockState *BBS, | |||
| 647 | AvailableValueSet &Contribution) { | |||
| 648 | assert(&BBS->Contribution == &Contribution &&((void)0) | |||
| 649 | "Passed Contribution should be from the passed BasicBlockState!")((void)0); | |||
| 650 | AvailableValueSet AvailableSet = BBS->AvailableIn; | |||
| 651 | bool ContributionChanged = false; | |||
| 652 | // For explanation why instructions are processed this way see | |||
| 653 | // "Rules of deriving" in the comment to this class. | |||
| 654 | for (const Instruction &I : *BB) { | |||
| 655 | bool ValidUnrelocatedPointerDef = false; | |||
| 656 | bool PoisonedPointerDef = false; | |||
| 657 | // TODO: `select` instructions should be handled here too. | |||
| 658 | if (const PHINode *PN = dyn_cast<PHINode>(&I)) { | |||
| 659 | if (containsGCPtrType(PN->getType())) { | |||
| 660 | // If both is true, output is poisoned. | |||
| 661 | bool HasRelocatedInputs = false; | |||
| 662 | bool HasUnrelocatedInputs = false; | |||
| 663 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
| 664 | const BasicBlock *InBB = PN->getIncomingBlock(i); | |||
| 665 | if (!isMapped(InBB) || | |||
| 666 | !CD.hasLiveIncomingEdge(PN, InBB)) | |||
| 667 | continue; // Skip dead block or dead edge. | |||
| 668 | ||||
| 669 | const Value *InValue = PN->getIncomingValue(i); | |||
| 670 | ||||
| 671 | if (isNotExclusivelyConstantDerived(InValue)) { | |||
| 672 | if (isValuePoisoned(InValue)) { | |||
| 673 | // If any of inputs is poisoned, output is always poisoned too. | |||
| 674 | HasRelocatedInputs = true; | |||
| 675 | HasUnrelocatedInputs = true; | |||
| 676 | break; | |||
| 677 | } | |||
| 678 | if (BlockMap[InBB]->AvailableOut.count(InValue)) | |||
| 679 | HasRelocatedInputs = true; | |||
| 680 | else | |||
| 681 | HasUnrelocatedInputs = true; | |||
| 682 | } | |||
| 683 | } | |||
| 684 | if (HasUnrelocatedInputs) { | |||
| 685 | if (HasRelocatedInputs) | |||
| 686 | PoisonedPointerDef = true; | |||
| 687 | else | |||
| 688 | ValidUnrelocatedPointerDef = true; | |||
| 689 | } | |||
| 690 | } | |||
| 691 | } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) && | |||
| 692 | containsGCPtrType(I.getType())) { | |||
| 693 | // GEP/bitcast of unrelocated pointer is legal by itself but this def | |||
| 694 | // shouldn't appear in any AvailableSet. | |||
| 695 | for (const Value *V : I.operands()) | |||
| 696 | if (containsGCPtrType(V->getType()) && | |||
| 697 | isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) { | |||
| 698 | if (isValuePoisoned(V)) | |||
| 699 | PoisonedPointerDef = true; | |||
| 700 | else | |||
| 701 | ValidUnrelocatedPointerDef = true; | |||
| 702 | break; | |||
| 703 | } | |||
| 704 | } | |||
| 705 | assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&((void)0) | |||
| 706 | "Value cannot be both unrelocated and poisoned!")((void)0); | |||
| 707 | if (ValidUnrelocatedPointerDef) { | |||
| 708 | // Remove def of unrelocated pointer from Contribution of this BB and | |||
| 709 | // trigger update of all its successors. | |||
| 710 | Contribution.erase(&I); | |||
| 711 | PoisonedDefs.erase(&I); | |||
| 712 | ValidUnrelocatedDefs.insert(&I); | |||
| 713 | LLVM_DEBUG(dbgs() << "Removing urelocated " << Ido { } while (false) | |||
| 714 | << " from Contribution of " << BB->getName() << "\n")do { } while (false); | |||
| 715 | ContributionChanged = true; | |||
| 716 | } else if (PoisonedPointerDef) { | |||
| 717 | // Mark pointer as poisoned, remove its def from Contribution and trigger | |||
| 718 | // update of all successors. | |||
| 719 | Contribution.erase(&I); | |||
| 720 | PoisonedDefs.insert(&I); | |||
| 721 | LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "do { } while (false) | |||
| 722 | << BB->getName() << "\n")do { } while (false); | |||
| 723 | ContributionChanged = true; | |||
| 724 | } else { | |||
| 725 | bool Cleared = false; | |||
| 726 | transferInstruction(I, Cleared, AvailableSet); | |||
| 727 | (void)Cleared; | |||
| 728 | } | |||
| 729 | } | |||
| 730 | return ContributionChanged; | |||
| 731 | } | |||
| 732 | ||||
| 733 | void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB, | |||
| 734 | AvailableValueSet &Result, | |||
| 735 | const DominatorTree &DT) { | |||
| 736 | DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)]; | |||
| 737 | ||||
| 738 | assert(DTN && "Unreachable blocks are ignored")((void)0); | |||
| 739 | while (DTN->getIDom()) { | |||
| 740 | DTN = DTN->getIDom(); | |||
| 741 | auto BBS = getBasicBlockState(DTN->getBlock()); | |||
| 742 | assert(BBS && "immediate dominator cannot be dead for a live block")((void)0); | |||
| 743 | const auto &Defs = BBS->Contribution; | |||
| 744 | Result.insert(Defs.begin(), Defs.end()); | |||
| 745 | // If this block is 'Cleared', then nothing LiveIn to this block can be | |||
| 746 | // available after this block completes. Note: This turns out to be | |||
| 747 | // really important for reducing memory consuption of the initial available | |||
| 748 | // sets and thus peak memory usage by this verifier. | |||
| 749 | if (BBS->Cleared) | |||
| 750 | return; | |||
| 751 | } | |||
| 752 | ||||
| 753 | for (const Argument &A : BB->getParent()->args()) | |||
| 754 | if (containsGCPtrType(A.getType())) | |||
| 755 | Result.insert(&A); | |||
| 756 | } | |||
| 757 | ||||
| 758 | void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS, | |||
| 759 | bool ContributionChanged) { | |||
| 760 | const AvailableValueSet &AvailableIn = BBS.AvailableIn; | |||
| 761 | AvailableValueSet &AvailableOut = BBS.AvailableOut; | |||
| 762 | ||||
| 763 | if (BBS.Cleared) { | |||
| 764 | // AvailableOut will change only when Contribution changed. | |||
| 765 | if (ContributionChanged) | |||
| 766 | AvailableOut = BBS.Contribution; | |||
| 767 | } else { | |||
| 768 | // Otherwise, we need to reduce the AvailableOut set by things which are no | |||
| 769 | // longer in our AvailableIn | |||
| 770 | AvailableValueSet Temp = BBS.Contribution; | |||
| 771 | set_union(Temp, AvailableIn); | |||
| 772 | AvailableOut = std::move(Temp); | |||
| 773 | } | |||
| 774 | ||||
| 775 | LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";do { } while (false) | |||
| 776 | PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());do { } while (false) | |||
| 777 | dbgs() << " to ";do { } while (false) | |||
| 778 | PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());do { } while (false) | |||
| 779 | dbgs() << "\n";)do { } while (false); | |||
| 780 | } | |||
| 781 | ||||
| 782 | void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared, | |||
| 783 | AvailableValueSet &Available) { | |||
| 784 | if (isa<GCStatepointInst>(I)) { | |||
| 785 | Cleared = true; | |||
| 786 | Available.clear(); | |||
| 787 | } else if (containsGCPtrType(I.getType())) | |||
| 788 | Available.insert(&I); | |||
| 789 | } | |||
| 790 | ||||
| 791 | void InstructionVerifier::verifyInstruction( | |||
| 792 | const GCPtrTracker *Tracker, const Instruction &I, | |||
| 793 | const AvailableValueSet &AvailableSet) { | |||
| 794 | if (const PHINode *PN = dyn_cast<PHINode>(&I)) { | |||
| 795 | if (containsGCPtrType(PN->getType())) | |||
| 796 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
| 797 | const BasicBlock *InBB = PN->getIncomingBlock(i); | |||
| 798 | const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB); | |||
| 799 | if (!InBBS || | |||
| 800 | !Tracker->hasLiveIncomingEdge(PN, InBB)) | |||
| 801 | continue; // Skip dead block or dead edge. | |||
| 802 | ||||
| 803 | const Value *InValue = PN->getIncomingValue(i); | |||
| 804 | ||||
| 805 | if (isNotExclusivelyConstantDerived(InValue) && | |||
| 806 | !InBBS->AvailableOut.count(InValue)) | |||
| 807 | reportInvalidUse(*InValue, *PN); | |||
| 808 | } | |||
| 809 | } else if (isa<CmpInst>(I) && | |||
| 810 | containsGCPtrType(I.getOperand(0)->getType())) { | |||
| 811 | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); | |||
| 812 | enum BaseType baseTyLHS = getBaseType(LHS), | |||
| 813 | baseTyRHS = getBaseType(RHS); | |||
| 814 | ||||
| 815 | // Returns true if LHS and RHS are unrelocated pointers and they are | |||
| 816 | // valid unrelocated uses. | |||
| 817 | auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS, | |||
| 818 | &LHS, &RHS] () { | |||
| 819 | // A cmp instruction has valid unrelocated pointer operands only if | |||
| 820 | // both operands are unrelocated pointers. | |||
| 821 | // In the comparison between two pointers, if one is an unrelocated | |||
| 822 | // use, the other *should be* an unrelocated use, for this | |||
| 823 | // instruction to contain valid unrelocated uses. This unrelocated | |||
| 824 | // use can be a null constant as well, or another unrelocated | |||
| 825 | // pointer. | |||
| 826 | if (AvailableSet.count(LHS) || AvailableSet.count(RHS)) | |||
| 827 | return false; | |||
| 828 | // Constant pointers (that are not exclusively null) may have | |||
| 829 | // meaning in different VMs, so we cannot reorder the compare | |||
| 830 | // against constant pointers before the safepoint. In other words, | |||
| 831 | // comparison of an unrelocated use against a non-null constant | |||
| 832 | // maybe invalid. | |||
| 833 | if ((baseTyLHS == BaseType::ExclusivelySomeConstant && | |||
| 834 | baseTyRHS == BaseType::NonConstant) || | |||
| 835 | (baseTyLHS == BaseType::NonConstant && | |||
| 836 | baseTyRHS == BaseType::ExclusivelySomeConstant)) | |||
| 837 | return false; | |||
| 838 | ||||
| 839 | // If one of pointers is poisoned and other is not exclusively derived | |||
| 840 | // from null it is an invalid expression: it produces poisoned result | |||
| 841 | // and unless we want to track all defs (not only gc pointers) the only | |||
| 842 | // option is to prohibit such instructions. | |||
| 843 | if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) || | |||
| 844 | (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull)) | |||
| 845 | return false; | |||
| 846 | ||||
| 847 | // All other cases are valid cases enumerated below: | |||
| 848 | // 1. Comparison between an exclusively derived null pointer and a | |||
| 849 | // constant base pointer. | |||
| 850 | // 2. Comparison between an exclusively derived null pointer and a | |||
| 851 | // non-constant unrelocated base pointer. | |||
| 852 | // 3. Comparison between 2 unrelocated pointers. | |||
| 853 | // 4. Comparison between a pointer exclusively derived from null and a | |||
| 854 | // non-constant poisoned pointer. | |||
| 855 | return true; | |||
| 856 | }; | |||
| 857 | if (!hasValidUnrelocatedUse()) { | |||
| 858 | // Print out all non-constant derived pointers that are unrelocated | |||
| 859 | // uses, which are invalid. | |||
| 860 | if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS)) | |||
| 861 | reportInvalidUse(*LHS, I); | |||
| 862 | if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS)) | |||
| 863 | reportInvalidUse(*RHS, I); | |||
| 864 | } | |||
| 865 | } else { | |||
| 866 | for (const Value *V : I.operands()) | |||
| 867 | if (containsGCPtrType(V->getType()) && | |||
| 868 | isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) | |||
| 869 | reportInvalidUse(*V, I); | |||
| 870 | } | |||
| 871 | } | |||
| 872 | ||||
| 873 | void InstructionVerifier::reportInvalidUse(const Value &V, | |||
| 874 | const Instruction &I) { | |||
| 875 | errs() << "Illegal use of unrelocated value found!\n"; | |||
| 876 | errs() << "Def: " << V << "\n"; | |||
| 877 | errs() << "Use: " << I << "\n"; | |||
| 878 | if (!PrintOnly) | |||
| 879 | abort(); | |||
| 880 | AnyInvalidUses = true; | |||
| 881 | } | |||
| 882 | ||||
| 883 | static void Verify(const Function &F, const DominatorTree &DT, | |||
| 884 | const CFGDeadness &CD) { | |||
| 885 | LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()do { } while (false) | |||
| 886 | << "\n")do { } while (false); | |||
| 887 | if (PrintOnly) | |||
| 888 | dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n"; | |||
| 889 | ||||
| 890 | GCPtrTracker Tracker(F, DT, CD); | |||
| 891 | ||||
| 892 | // We now have all the information we need to decide if the use of a heap | |||
| 893 | // reference is legal or not, given our safepoint semantics. | |||
| 894 | ||||
| 895 | InstructionVerifier Verifier; | |||
| 896 | GCPtrTracker::verifyFunction(std::move(Tracker), Verifier); | |||
| 897 | ||||
| 898 | if (PrintOnly && !Verifier.hasAnyInvalidUses()) { | |||
| 899 | dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName() | |||
| 900 | << "\n"; | |||
| 901 | } | |||
| 902 | } |
| 1 | //===- llvm/Pass.h - Base class for Passes ----------------------*- C++ -*-===// |
| 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 | // This file defines a base class that indicates that a specified class is a |
| 10 | // transformation pass implementation. |
| 11 | // |
| 12 | // Passes are designed this way so that it is possible to run passes in a cache |
| 13 | // and organizationally optimal order without having to specify it at the front |
| 14 | // end. This allows arbitrary passes to be strung together and have them |
| 15 | // executed as efficiently as possible. |
| 16 | // |
| 17 | // Passes should extend one of the classes below, depending on the guarantees |
| 18 | // that it can make about what will be modified as it is run. For example, most |
| 19 | // global optimizations should derive from FunctionPass, because they do not add |
| 20 | // or delete functions, they operate on the internals of the function. |
| 21 | // |
| 22 | // Note that this file #includes PassSupport.h and PassAnalysisSupport.h (at the |
| 23 | // bottom), so the APIs exposed by these files are also automatically available |
| 24 | // to all users of this file. |
| 25 | // |
| 26 | //===----------------------------------------------------------------------===// |
| 27 | |
| 28 | #ifndef LLVM_PASS_H |
| 29 | #define LLVM_PASS_H |
| 30 | |
| 31 | #include <string> |
| 32 | |
| 33 | namespace llvm { |
| 34 | |
| 35 | class AnalysisResolver; |
| 36 | class AnalysisUsage; |
| 37 | class Function; |
| 38 | class ImmutablePass; |
| 39 | class Module; |
| 40 | class PassInfo; |
| 41 | class PMDataManager; |
| 42 | class PMStack; |
| 43 | class raw_ostream; |
| 44 | class StringRef; |
| 45 | |
| 46 | // AnalysisID - Use the PassInfo to identify a pass... |
| 47 | using AnalysisID = const void *; |
| 48 | |
| 49 | /// Different types of internal pass managers. External pass managers |
| 50 | /// (PassManager and FunctionPassManager) are not represented here. |
| 51 | /// Ordering of pass manager types is important here. |
| 52 | enum PassManagerType { |
| 53 | PMT_Unknown = 0, |
| 54 | PMT_ModulePassManager = 1, ///< MPPassManager |
| 55 | PMT_CallGraphPassManager, ///< CGPassManager |
| 56 | PMT_FunctionPassManager, ///< FPPassManager |
| 57 | PMT_LoopPassManager, ///< LPPassManager |
| 58 | PMT_RegionPassManager, ///< RGPassManager |
| 59 | PMT_Last |
| 60 | }; |
| 61 | |
| 62 | // Different types of passes. |
| 63 | enum PassKind { |
| 64 | PT_Region, |
| 65 | PT_Loop, |
| 66 | PT_Function, |
| 67 | PT_CallGraphSCC, |
| 68 | PT_Module, |
| 69 | PT_PassManager |
| 70 | }; |
| 71 | |
| 72 | /// This enumerates the LLVM full LTO or ThinLTO optimization phases. |
| 73 | enum class ThinOrFullLTOPhase { |
| 74 | /// No LTO/ThinLTO behavior needed. |
| 75 | None, |
| 76 | /// ThinLTO prelink (summary) phase. |
| 77 | ThinLTOPreLink, |
| 78 | /// ThinLTO postlink (backend compile) phase. |
| 79 | ThinLTOPostLink, |
| 80 | /// Full LTO prelink phase. |
| 81 | FullLTOPreLink, |
| 82 | /// Full LTO postlink (backend compile) phase. |
| 83 | FullLTOPostLink |
| 84 | }; |
| 85 | |
| 86 | //===----------------------------------------------------------------------===// |
| 87 | /// Pass interface - Implemented by all 'passes'. Subclass this if you are an |
| 88 | /// interprocedural optimization or you do not fit into any of the more |
| 89 | /// constrained passes described below. |
| 90 | /// |
| 91 | class Pass { |
| 92 | AnalysisResolver *Resolver = nullptr; // Used to resolve analysis |
| 93 | const void *PassID; |
| 94 | PassKind Kind; |
| 95 | |
| 96 | public: |
| 97 | explicit Pass(PassKind K, char &pid) : PassID(&pid), Kind(K) {} |
| 98 | Pass(const Pass &) = delete; |
| 99 | Pass &operator=(const Pass &) = delete; |
| 100 | virtual ~Pass(); |
| 101 | |
| 102 | PassKind getPassKind() const { return Kind; } |
| 103 | |
| 104 | /// getPassName - Return a nice clean name for a pass. This usually |
| 105 | /// implemented in terms of the name that is registered by one of the |
| 106 | /// Registration templates, but can be overloaded directly. |
| 107 | virtual StringRef getPassName() const; |
| 108 | |
| 109 | /// getPassID - Return the PassID number that corresponds to this pass. |
| 110 | AnalysisID getPassID() const { |
| 111 | return PassID; |
| 112 | } |
| 113 | |
| 114 | /// doInitialization - Virtual method overridden by subclasses to do |
| 115 | /// any necessary initialization before any pass is run. |
| 116 | virtual bool doInitialization(Module &) { return false; } |
| 117 | |
| 118 | /// doFinalization - Virtual method overriden by subclasses to do any |
| 119 | /// necessary clean up after all passes have run. |
| 120 | virtual bool doFinalization(Module &) { return false; } |
| 121 | |
| 122 | /// print - Print out the internal state of the pass. This is called by |
| 123 | /// Analyze to print out the contents of an analysis. Otherwise it is not |
| 124 | /// necessary to implement this method. Beware that the module pointer MAY be |
| 125 | /// null. This automatically forwards to a virtual function that does not |
| 126 | /// provide the Module* in case the analysis doesn't need it it can just be |
| 127 | /// ignored. |
| 128 | virtual void print(raw_ostream &OS, const Module *M) const; |
| 129 | |
| 130 | void dump() const; // dump - Print to stderr. |
| 131 | |
| 132 | /// createPrinterPass - Get a Pass appropriate to print the IR this |
| 133 | /// pass operates on (Module, Function or MachineFunction). |
| 134 | virtual Pass *createPrinterPass(raw_ostream &OS, |
| 135 | const std::string &Banner) const = 0; |
| 136 | |
| 137 | /// Each pass is responsible for assigning a pass manager to itself. |
| 138 | /// PMS is the stack of available pass manager. |
| 139 | virtual void assignPassManager(PMStack &, |
| 140 | PassManagerType) {} |
| 141 | |
| 142 | /// Check if available pass managers are suitable for this pass or not. |
| 143 | virtual void preparePassManager(PMStack &); |
| 144 | |
| 145 | /// Return what kind of Pass Manager can manage this pass. |
| 146 | virtual PassManagerType getPotentialPassManagerType() const; |
| 147 | |
| 148 | // Access AnalysisResolver |
| 149 | void setResolver(AnalysisResolver *AR); |
| 150 | AnalysisResolver *getResolver() const { return Resolver; } |
| 151 | |
| 152 | /// getAnalysisUsage - This function should be overriden by passes that need |
| 153 | /// analysis information to do their job. If a pass specifies that it uses a |
| 154 | /// particular analysis result to this function, it can then use the |
| 155 | /// getAnalysis<AnalysisType>() function, below. |
| 156 | virtual void getAnalysisUsage(AnalysisUsage &) const; |
| 157 | |
| 158 | /// releaseMemory() - This member can be implemented by a pass if it wants to |
| 159 | /// be able to release its memory when it is no longer needed. The default |
| 160 | /// behavior of passes is to hold onto memory for the entire duration of their |
| 161 | /// lifetime (which is the entire compile time). For pipelined passes, this |
| 162 | /// is not a big deal because that memory gets recycled every time the pass is |
| 163 | /// invoked on another program unit. For IP passes, it is more important to |
| 164 | /// free memory when it is unused. |
| 165 | /// |
| 166 | /// Optionally implement this function to release pass memory when it is no |
| 167 | /// longer used. |
| 168 | virtual void releaseMemory(); |
| 169 | |
| 170 | /// getAdjustedAnalysisPointer - This method is used when a pass implements |
| 171 | /// an analysis interface through multiple inheritance. If needed, it should |
| 172 | /// override this to adjust the this pointer as needed for the specified pass |
| 173 | /// info. |
| 174 | virtual void *getAdjustedAnalysisPointer(AnalysisID ID); |
| 175 | virtual ImmutablePass *getAsImmutablePass(); |
| 176 | virtual PMDataManager *getAsPMDataManager(); |
| 177 | |
| 178 | /// verifyAnalysis() - This member can be implemented by a analysis pass to |
| 179 | /// check state of analysis information. |
| 180 | virtual void verifyAnalysis() const; |
| 181 | |
| 182 | // dumpPassStructure - Implement the -debug-passes=PassStructure option |
| 183 | virtual void dumpPassStructure(unsigned Offset = 0); |
| 184 | |
| 185 | // lookupPassInfo - Return the pass info object for the specified pass class, |
| 186 | // or null if it is not known. |
| 187 | static const PassInfo *lookupPassInfo(const void *TI); |
| 188 | |
| 189 | // lookupPassInfo - Return the pass info object for the pass with the given |
| 190 | // argument string, or null if it is not known. |
| 191 | static const PassInfo *lookupPassInfo(StringRef Arg); |
| 192 | |
| 193 | // createPass - Create a object for the specified pass class, |
| 194 | // or null if it is not known. |
| 195 | static Pass *createPass(AnalysisID ID); |
| 196 | |
| 197 | /// getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to |
| 198 | /// get analysis information that might be around, for example to update it. |
| 199 | /// This is different than getAnalysis in that it can fail (if the analysis |
| 200 | /// results haven't been computed), so should only be used if you can handle |
| 201 | /// the case when the analysis is not available. This method is often used by |
| 202 | /// transformation APIs to update analysis results for a pass automatically as |
| 203 | /// the transform is performed. |
| 204 | template<typename AnalysisType> AnalysisType * |
| 205 | getAnalysisIfAvailable() const; // Defined in PassAnalysisSupport.h |
| 206 | |
| 207 | /// mustPreserveAnalysisID - This method serves the same function as |
| 208 | /// getAnalysisIfAvailable, but works if you just have an AnalysisID. This |
| 209 | /// obviously cannot give you a properly typed instance of the class if you |
| 210 | /// don't have the class name available (use getAnalysisIfAvailable if you |
| 211 | /// do), but it can tell you if you need to preserve the pass at least. |
| 212 | bool mustPreserveAnalysisID(char &AID) const; |
| 213 | |
| 214 | /// getAnalysis<AnalysisType>() - This function is used by subclasses to get |
| 215 | /// to the analysis information that they claim to use by overriding the |
| 216 | /// getAnalysisUsage function. |
| 217 | template<typename AnalysisType> |
| 218 | AnalysisType &getAnalysis() const; // Defined in PassAnalysisSupport.h |
| 219 | |
| 220 | template <typename AnalysisType> |
| 221 | AnalysisType & |
| 222 | getAnalysis(Function &F, |
| 223 | bool *Changed = nullptr); // Defined in PassAnalysisSupport.h |
| 224 | |
| 225 | template<typename AnalysisType> |
| 226 | AnalysisType &getAnalysisID(AnalysisID PI) const; |
| 227 | |
| 228 | template <typename AnalysisType> |
| 229 | AnalysisType &getAnalysisID(AnalysisID PI, Function &F, |
| 230 | bool *Changed = nullptr); |
| 231 | }; |
| 232 | |
| 233 | //===----------------------------------------------------------------------===// |
| 234 | /// ModulePass class - This class is used to implement unstructured |
| 235 | /// interprocedural optimizations and analyses. ModulePasses may do anything |
| 236 | /// they want to the program. |
| 237 | /// |
| 238 | class ModulePass : public Pass { |
| 239 | public: |
| 240 | explicit ModulePass(char &pid) : Pass(PT_Module, pid) {} |
| 241 | |
| 242 | // Force out-of-line virtual method. |
| 243 | ~ModulePass() override; |
| 244 | |
| 245 | /// createPrinterPass - Get a module printer pass. |
| 246 | Pass *createPrinterPass(raw_ostream &OS, |
| 247 | const std::string &Banner) const override; |
| 248 | |
| 249 | /// runOnModule - Virtual method overriden by subclasses to process the module |
| 250 | /// being operated on. |
| 251 | virtual bool runOnModule(Module &M) = 0; |
| 252 | |
| 253 | void assignPassManager(PMStack &PMS, PassManagerType T) override; |
| 254 | |
| 255 | /// Return what kind of Pass Manager can manage this pass. |
| 256 | PassManagerType getPotentialPassManagerType() const override; |
| 257 | |
| 258 | protected: |
| 259 | /// Optional passes call this function to check whether the pass should be |
| 260 | /// skipped. This is the case when optimization bisect is over the limit. |
| 261 | bool skipModule(Module &M) const; |
| 262 | }; |
| 263 | |
| 264 | //===----------------------------------------------------------------------===// |
| 265 | /// ImmutablePass class - This class is used to provide information that does |
| 266 | /// not need to be run. This is useful for things like target information and |
| 267 | /// "basic" versions of AnalysisGroups. |
| 268 | /// |
| 269 | class ImmutablePass : public ModulePass { |
| 270 | public: |
| 271 | explicit ImmutablePass(char &pid) : ModulePass(pid) {} |
| 272 | |
| 273 | // Force out-of-line virtual method. |
| 274 | ~ImmutablePass() override; |
| 275 | |
| 276 | /// initializePass - This method may be overriden by immutable passes to allow |
| 277 | /// them to perform various initialization actions they require. This is |
| 278 | /// primarily because an ImmutablePass can "require" another ImmutablePass, |
| 279 | /// and if it does, the overloaded version of initializePass may get access to |
| 280 | /// these passes with getAnalysis<>. |
| 281 | virtual void initializePass(); |
| 282 | |
| 283 | ImmutablePass *getAsImmutablePass() override { return this; } |
| 284 | |
| 285 | /// ImmutablePasses are never run. |
| 286 | bool runOnModule(Module &) override { return false; } |
| 287 | }; |
| 288 | |
| 289 | //===----------------------------------------------------------------------===// |
| 290 | /// FunctionPass class - This class is used to implement most global |
| 291 | /// optimizations. Optimizations should subclass this class if they meet the |
| 292 | /// following constraints: |
| 293 | /// |
| 294 | /// 1. Optimizations are organized globally, i.e., a function at a time |
| 295 | /// 2. Optimizing a function does not cause the addition or removal of any |
| 296 | /// functions in the module |
| 297 | /// |
| 298 | class FunctionPass : public Pass { |
| 299 | public: |
| 300 | explicit FunctionPass(char &pid) : Pass(PT_Function, pid) {} |
| 301 | |
| 302 | /// createPrinterPass - Get a function printer pass. |
| 303 | Pass *createPrinterPass(raw_ostream &OS, |
| 304 | const std::string &Banner) const override; |
| 305 | |
| 306 | /// runOnFunction - Virtual method overriden by subclasses to do the |
| 307 | /// per-function processing of the pass. |
| 308 | virtual bool runOnFunction(Function &F) = 0; |
| 309 | |
| 310 | void assignPassManager(PMStack &PMS, PassManagerType T) override; |
| 311 | |
| 312 | /// Return what kind of Pass Manager can manage this pass. |
| 313 | PassManagerType getPotentialPassManagerType() const override; |
| 314 | |
| 315 | protected: |
| 316 | /// Optional passes call this function to check whether the pass should be |
| 317 | /// skipped. This is the case when Attribute::OptimizeNone is set or when |
| 318 | /// optimization bisect is over the limit. |
| 319 | bool skipFunction(const Function &F) const; |
| 320 | }; |
| 321 | |
| 322 | /// If the user specifies the -time-passes argument on an LLVM tool command line |
| 323 | /// then the value of this boolean will be true, otherwise false. |
| 324 | /// This is the storage for the -time-passes option. |
| 325 | extern bool TimePassesIsEnabled; |
| 326 | /// If TimePassesPerRun is true, there would be one line of report for |
| 327 | /// each pass invocation. |
| 328 | /// If TimePassesPerRun is false, there would be only one line of |
| 329 | /// report for each pass (even there are more than one pass objects). |
| 330 | /// (For new pass manager only) |
| 331 | extern bool TimePassesPerRun; |
| 332 | |
| 333 | } // end namespace llvm |
| 334 | |
| 335 | // Include support files that contain important APIs commonly used by Passes, |
| 336 | // but that we want to separate out to make it easier to read the header files. |
| 337 | #include "llvm/PassAnalysisSupport.h" |
| 338 | #include "llvm/PassSupport.h" |
| 339 | |
| 340 | #endif // LLVM_PASS_H |
| 1 | //===- llvm/PassAnalysisSupport.h - Analysis Pass Support code --*- C++ -*-===// | |||
| 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 | // This file defines stuff that is used to define and "use" Analysis Passes. | |||
| 10 | // This file is automatically #included by Pass.h, so: | |||
| 11 | // | |||
| 12 | // NO .CPP FILES SHOULD INCLUDE THIS FILE DIRECTLY | |||
| 13 | // | |||
| 14 | // Instead, #include Pass.h | |||
| 15 | // | |||
| 16 | //===----------------------------------------------------------------------===// | |||
| 17 | ||||
| 18 | #if !defined(LLVM_PASS_H) || defined(LLVM_PASSANALYSISSUPPORT_H) | |||
| 19 | #error "Do not include <PassAnalysisSupport.h>; include <Pass.h> instead" | |||
| 20 | #endif | |||
| 21 | ||||
| 22 | #ifndef LLVM_PASSANALYSISSUPPORT_H | |||
| 23 | #define LLVM_PASSANALYSISSUPPORT_H | |||
| 24 | ||||
| 25 | #include "llvm/ADT/STLExtras.h" | |||
| 26 | #include "llvm/ADT/SmallVector.h" | |||
| 27 | #include <cassert> | |||
| 28 | #include <tuple> | |||
| 29 | #include <utility> | |||
| 30 | #include <vector> | |||
| 31 | ||||
| 32 | namespace llvm { | |||
| 33 | ||||
| 34 | class Function; | |||
| 35 | class Pass; | |||
| 36 | class PMDataManager; | |||
| 37 | class StringRef; | |||
| 38 | ||||
| 39 | //===----------------------------------------------------------------------===// | |||
| 40 | /// Represent the analysis usage information of a pass. This tracks analyses | |||
| 41 | /// that the pass REQUIRES (must be available when the pass runs), REQUIRES | |||
| 42 | /// TRANSITIVE (must be available throughout the lifetime of the pass), and | |||
| 43 | /// analyses that the pass PRESERVES (the pass does not invalidate the results | |||
| 44 | /// of these analyses). This information is provided by a pass to the Pass | |||
| 45 | /// infrastructure through the getAnalysisUsage virtual function. | |||
| 46 | /// | |||
| 47 | class AnalysisUsage { | |||
| 48 | public: | |||
| 49 | using VectorType = SmallVectorImpl<AnalysisID>; | |||
| 50 | ||||
| 51 | private: | |||
| 52 | /// Sets of analyses required and preserved by a pass | |||
| 53 | // TODO: It's not clear that SmallVector is an appropriate data structure for | |||
| 54 | // this usecase. The sizes were picked to minimize wasted space, but are | |||
| 55 | // otherwise fairly meaningless. | |||
| 56 | SmallVector<AnalysisID, 8> Required; | |||
| 57 | SmallVector<AnalysisID, 2> RequiredTransitive; | |||
| 58 | SmallVector<AnalysisID, 2> Preserved; | |||
| 59 | SmallVector<AnalysisID, 0> Used; | |||
| 60 | bool PreservesAll = false; | |||
| 61 | ||||
| 62 | void pushUnique(VectorType &Set, AnalysisID ID) { | |||
| 63 | if (!llvm::is_contained(Set, ID)) | |||
| 64 | Set.push_back(ID); | |||
| 65 | } | |||
| 66 | ||||
| 67 | public: | |||
| 68 | AnalysisUsage() = default; | |||
| 69 | ||||
| 70 | ///@{ | |||
| 71 | /// Add the specified ID to the required set of the usage info for a pass. | |||
| 72 | AnalysisUsage &addRequiredID(const void *ID); | |||
| 73 | AnalysisUsage &addRequiredID(char &ID); | |||
| 74 | template<class PassClass> | |||
| 75 | AnalysisUsage &addRequired() { | |||
| 76 | return addRequiredID(PassClass::ID); | |||
| 77 | } | |||
| 78 | ||||
| 79 | AnalysisUsage &addRequiredTransitiveID(char &ID); | |||
| 80 | template<class PassClass> | |||
| 81 | AnalysisUsage &addRequiredTransitive() { | |||
| 82 | return addRequiredTransitiveID(PassClass::ID); | |||
| 83 | } | |||
| 84 | ///@} | |||
| 85 | ||||
| 86 | ///@{ | |||
| 87 | /// Add the specified ID to the set of analyses preserved by this pass. | |||
| 88 | AnalysisUsage &addPreservedID(const void *ID) { | |||
| 89 | pushUnique(Preserved, ID); | |||
| 90 | return *this; | |||
| 91 | } | |||
| 92 | AnalysisUsage &addPreservedID(char &ID) { | |||
| 93 | pushUnique(Preserved, &ID); | |||
| 94 | return *this; | |||
| 95 | } | |||
| 96 | /// Add the specified Pass class to the set of analyses preserved by this pass. | |||
| 97 | template<class PassClass> | |||
| 98 | AnalysisUsage &addPreserved() { | |||
| 99 | pushUnique(Preserved, &PassClass::ID); | |||
| 100 | return *this; | |||
| 101 | } | |||
| 102 | ///@} | |||
| 103 | ||||
| 104 | ///@{ | |||
| 105 | /// Add the specified ID to the set of analyses used by this pass if they are | |||
| 106 | /// available.. | |||
| 107 | AnalysisUsage &addUsedIfAvailableID(const void *ID) { | |||
| 108 | pushUnique(Used, ID); | |||
| 109 | return *this; | |||
| 110 | } | |||
| 111 | AnalysisUsage &addUsedIfAvailableID(char &ID) { | |||
| 112 | pushUnique(Used, &ID); | |||
| 113 | return *this; | |||
| 114 | } | |||
| 115 | /// Add the specified Pass class to the set of analyses used by this pass. | |||
| 116 | template<class PassClass> | |||
| 117 | AnalysisUsage &addUsedIfAvailable() { | |||
| 118 | pushUnique(Used, &PassClass::ID); | |||
| 119 | return *this; | |||
| 120 | } | |||
| 121 | ///@} | |||
| 122 | ||||
| 123 | /// Add the Pass with the specified argument string to the set of analyses | |||
| 124 | /// preserved by this pass. If no such Pass exists, do nothing. This can be | |||
| 125 | /// useful when a pass is trivially preserved, but may not be linked in. Be | |||
| 126 | /// careful about spelling! | |||
| 127 | AnalysisUsage &addPreserved(StringRef Arg); | |||
| 128 | ||||
| 129 | /// Set by analyses that do not transform their input at all | |||
| 130 | void setPreservesAll() { PreservesAll = true; } | |||
| 131 | ||||
| 132 | /// Determine whether a pass said it does not transform its input at all | |||
| 133 | bool getPreservesAll() const { return PreservesAll; } | |||
| 134 | ||||
| 135 | /// This function should be called by the pass, iff they do not: | |||
| 136 | /// | |||
| 137 | /// 1. Add or remove basic blocks from the function | |||
| 138 | /// 2. Modify terminator instructions in any way. | |||
| 139 | /// | |||
| 140 | /// This function annotates the AnalysisUsage info object to say that analyses | |||
| 141 | /// that only depend on the CFG are preserved by this pass. | |||
| 142 | void setPreservesCFG(); | |||
| 143 | ||||
| 144 | const VectorType &getRequiredSet() const { return Required; } | |||
| 145 | const VectorType &getRequiredTransitiveSet() const { | |||
| 146 | return RequiredTransitive; | |||
| 147 | } | |||
| 148 | const VectorType &getPreservedSet() const { return Preserved; } | |||
| 149 | const VectorType &getUsedSet() const { return Used; } | |||
| 150 | }; | |||
| 151 | ||||
| 152 | //===----------------------------------------------------------------------===// | |||
| 153 | /// AnalysisResolver - Simple interface used by Pass objects to pull all | |||
| 154 | /// analysis information out of pass manager that is responsible to manage | |||
| 155 | /// the pass. | |||
| 156 | /// | |||
| 157 | class AnalysisResolver { | |||
| 158 | public: | |||
| 159 | AnalysisResolver() = delete; | |||
| 160 | explicit AnalysisResolver(PMDataManager &P) : PM(P) {} | |||
| 161 | ||||
| 162 | PMDataManager &getPMDataManager() { return PM; } | |||
| 163 | ||||
| 164 | /// Find pass that is implementing PI. | |||
| 165 | Pass *findImplPass(AnalysisID PI) { | |||
| 166 | Pass *ResultPass = nullptr; | |||
| 167 | for (const auto &AnalysisImpl : AnalysisImpls) { | |||
| 168 | if (AnalysisImpl.first == PI) { | |||
| 169 | ResultPass = AnalysisImpl.second; | |||
| 170 | break; | |||
| 171 | } | |||
| 172 | } | |||
| 173 | return ResultPass; | |||
| 174 | } | |||
| 175 | ||||
| 176 | /// Find pass that is implementing PI. Initialize pass for Function F. | |||
| 177 | std::tuple<Pass *, bool> findImplPass(Pass *P, AnalysisID PI, Function &F); | |||
| 178 | ||||
| 179 | void addAnalysisImplsPair(AnalysisID PI, Pass *P) { | |||
| 180 | if (findImplPass(PI) == P) | |||
| 181 | return; | |||
| 182 | std::pair<AnalysisID, Pass*> pir = std::make_pair(PI,P); | |||
| 183 | AnalysisImpls.push_back(pir); | |||
| 184 | } | |||
| 185 | ||||
| 186 | /// Clear cache that is used to connect a pass to the analysis (PassInfo). | |||
| 187 | void clearAnalysisImpls() { | |||
| 188 | AnalysisImpls.clear(); | |||
| 189 | } | |||
| 190 | ||||
| 191 | /// Return analysis result or null if it doesn't exist. | |||
| 192 | Pass *getAnalysisIfAvailable(AnalysisID ID) const; | |||
| 193 | ||||
| 194 | private: | |||
| 195 | /// This keeps track of which passes implements the interfaces that are | |||
| 196 | /// required by the current pass (to implement getAnalysis()). | |||
| 197 | std::vector<std::pair<AnalysisID, Pass *>> AnalysisImpls; | |||
| 198 | ||||
| 199 | /// PassManager that is used to resolve analysis info | |||
| 200 | PMDataManager &PM; | |||
| 201 | }; | |||
| 202 | ||||
| 203 | /// getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to | |||
| 204 | /// get analysis information that might be around, for example to update it. | |||
| 205 | /// This is different than getAnalysis in that it can fail (if the analysis | |||
| 206 | /// results haven't been computed), so should only be used if you can handle | |||
| 207 | /// the case when the analysis is not available. This method is often used by | |||
| 208 | /// transformation APIs to update analysis results for a pass automatically as | |||
| 209 | /// the transform is performed. | |||
| 210 | template<typename AnalysisType> | |||
| 211 | AnalysisType *Pass::getAnalysisIfAvailable() const { | |||
| 212 | assert(Resolver && "Pass not resident in a PassManager object!")((void)0); | |||
| 213 | ||||
| 214 | const void *PI = &AnalysisType::ID; | |||
| 215 | ||||
| 216 | Pass *ResultPass = Resolver->getAnalysisIfAvailable(PI); | |||
| 217 | if (!ResultPass) return nullptr; | |||
| 218 | ||||
| 219 | // Because the AnalysisType may not be a subclass of pass (for | |||
| 220 | // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially | |||
| 221 | // adjust the return pointer (because the class may multiply inherit, once | |||
| 222 | // from pass, once from AnalysisType). | |||
| 223 | return (AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); | |||
| 224 | } | |||
| 225 | ||||
| 226 | /// getAnalysis<AnalysisType>() - This function is used by subclasses to get | |||
| 227 | /// to the analysis information that they claim to use by overriding the | |||
| 228 | /// getAnalysisUsage function. | |||
| 229 | template<typename AnalysisType> | |||
| 230 | AnalysisType &Pass::getAnalysis() const { | |||
| 231 | assert(Resolver && "Pass has not been inserted into a PassManager object!")((void)0); | |||
| 232 | return getAnalysisID<AnalysisType>(&AnalysisType::ID); | |||
| 233 | } | |||
| 234 | ||||
| 235 | template<typename AnalysisType> | |||
| 236 | AnalysisType &Pass::getAnalysisID(AnalysisID PI) const { | |||
| 237 | assert(PI && "getAnalysis for unregistered pass!")((void)0); | |||
| 238 | assert(Resolver&&"Pass has not been inserted into a PassManager object!")((void)0); | |||
| 239 | // PI *must* appear in AnalysisImpls. Because the number of passes used | |||
| 240 | // should be a small number, we just do a linear search over a (dense) | |||
| 241 | // vector. | |||
| 242 | Pass *ResultPass = Resolver->findImplPass(PI); | |||
| ||||
| 243 | assert(ResultPass &&((void)0) | |||
| 244 | "getAnalysis*() called on an analysis that was not "((void)0) | |||
| 245 | "'required' by pass!")((void)0); | |||
| 246 | ||||
| 247 | // Because the AnalysisType may not be a subclass of pass (for | |||
| 248 | // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially | |||
| 249 | // adjust the return pointer (because the class may multiply inherit, once | |||
| 250 | // from pass, once from AnalysisType). | |||
| 251 | return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); | |||
| 252 | } | |||
| 253 | ||||
| 254 | /// getAnalysis<AnalysisType>() - This function is used by subclasses to get | |||
| 255 | /// to the analysis information that they claim to use by overriding the | |||
| 256 | /// getAnalysisUsage function. If as part of the dependencies, an IR | |||
| 257 | /// transformation is triggered (e.g. because the analysis requires | |||
| 258 | /// BreakCriticalEdges), and Changed is non null, *Changed is updated. | |||
| 259 | template <typename AnalysisType> | |||
| 260 | AnalysisType &Pass::getAnalysis(Function &F, bool *Changed) { | |||
| 261 | assert(Resolver &&"Pass has not been inserted into a PassManager object!")((void)0); | |||
| 262 | ||||
| 263 | return getAnalysisID<AnalysisType>(&AnalysisType::ID, F, Changed); | |||
| 264 | } | |||
| 265 | ||||
| 266 | template <typename AnalysisType> | |||
| 267 | AnalysisType &Pass::getAnalysisID(AnalysisID PI, Function &F, bool *Changed) { | |||
| 268 | assert(PI && "getAnalysis for unregistered pass!")((void)0); | |||
| 269 | assert(Resolver && "Pass has not been inserted into a PassManager object!")((void)0); | |||
| 270 | // PI *must* appear in AnalysisImpls. Because the number of passes used | |||
| 271 | // should be a small number, we just do a linear search over a (dense) | |||
| 272 | // vector. | |||
| 273 | Pass *ResultPass; | |||
| 274 | bool LocalChanged; | |||
| 275 | std::tie(ResultPass, LocalChanged) = Resolver->findImplPass(this, PI, F); | |||
| 276 | ||||
| 277 | assert(ResultPass && "Unable to find requested analysis info")((void)0); | |||
| 278 | if (Changed) | |||
| 279 | *Changed |= LocalChanged; | |||
| 280 | else | |||
| 281 | assert(!LocalChanged &&((void)0) | |||
| 282 | "A pass trigged a code update but the update status is lost")((void)0); | |||
| 283 | ||||
| 284 | // Because the AnalysisType may not be a subclass of pass (for | |||
| 285 | // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially | |||
| 286 | // adjust the return pointer (because the class may multiply inherit, once | |||
| 287 | // from pass, once from AnalysisType). | |||
| 288 | return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); | |||
| 289 | } | |||
| 290 | ||||
| 291 | } // end namespace llvm | |||
| 292 | ||||
| 293 | #endif // LLVM_PASSANALYSISSUPPORT_H |