1 //===-- InstructionPrecedenceTracking.cpp -----------------------*- 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 // Implements a class that is able to define some instructions as "special" 9 // (e.g. as having implicit control flow, or writing memory, or having another 10 // interesting property) and then efficiently answers queries of the types: 11 // 1. Are there any special instructions in the block of interest? 12 // 2. Return first of the special instructions in the given block; 13 // 3. Check if the given instruction is preceeded by the first special 14 // instruction in the same block. 15 // The class provides caching that allows to answer these queries quickly. The 16 // user must make sure that the cached data is invalidated properly whenever 17 // a content of some tracked block is changed. 18 //===----------------------------------------------------------------------===// 19 20 #include "llvm/Analysis/InstructionPrecedenceTracking.h" 21 #include "llvm/Analysis/ValueTracking.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/IR/PatternMatch.h" 24 #include "llvm/Support/CommandLine.h" 25 26 using namespace llvm; 27 28 #define DEBUG_TYPE "ipt" 29 STATISTIC(NumInstScanned, "Number of insts scanned while updating ibt"); 30 31 #ifndef NDEBUG 32 static cl::opt<bool> ExpensiveAsserts( 33 "ipt-expensive-asserts", 34 cl::desc("Perform expensive assert validation on every query to Instruction" 35 " Precedence Tracking"), 36 cl::init(false), cl::Hidden); 37 #endif 38 39 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction( 40 const BasicBlock *BB) { 41 #ifndef NDEBUG 42 // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to 43 // catch this situation as early as possible. 44 if (ExpensiveAsserts) 45 validateAll(); 46 else 47 validate(BB); 48 #endif 49 50 if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) { 51 fill(BB); 52 assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!"); 53 } 54 return FirstSpecialInsts[BB]; 55 } 56 57 bool InstructionPrecedenceTracking::hasSpecialInstructions( 58 const BasicBlock *BB) { 59 return getFirstSpecialInstruction(BB) != nullptr; 60 } 61 62 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction( 63 const Instruction *Insn) { 64 const Instruction *MaybeFirstSpecial = 65 getFirstSpecialInstruction(Insn->getParent()); 66 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn); 67 } 68 69 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) { 70 FirstSpecialInsts.erase(BB); 71 for (const auto &I : *BB) { 72 NumInstScanned++; 73 if (isSpecialInstruction(&I)) { 74 FirstSpecialInsts[BB] = &I; 75 return; 76 } 77 } 78 79 // Mark this block as having no special instructions. 80 FirstSpecialInsts[BB] = nullptr; 81 } 82 83 #ifndef NDEBUG 84 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const { 85 auto It = FirstSpecialInsts.find(BB); 86 // Bail if we don't have anything cached for this block. 87 if (It == FirstSpecialInsts.end()) 88 return; 89 90 for (const Instruction &Insn : *BB) 91 if (isSpecialInstruction(&Insn)) { 92 assert(It->second == &Insn && 93 "Cached first special instruction is wrong!"); 94 return; 95 } 96 97 assert(It->second == nullptr && 98 "Block is marked as having special instructions but in fact it has " 99 "none!"); 100 } 101 102 void InstructionPrecedenceTracking::validateAll() const { 103 // Check that for every known block the cached value is correct. 104 for (const auto &It : FirstSpecialInsts) 105 validate(It.first); 106 } 107 #endif 108 109 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst, 110 const BasicBlock *BB) { 111 if (isSpecialInstruction(Inst)) 112 FirstSpecialInsts.erase(BB); 113 } 114 115 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) { 116 auto *BB = Inst->getParent(); 117 assert(BB && "must be called before instruction is actually removed"); 118 if (FirstSpecialInsts.count(BB) && FirstSpecialInsts[BB] == Inst) 119 FirstSpecialInsts.erase(BB); 120 } 121 122 void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) { 123 for (const auto *U : Inst->users()) { 124 if (const auto *UI = dyn_cast<Instruction>(U)) 125 removeInstruction(UI); 126 } 127 } 128 129 void InstructionPrecedenceTracking::clear() { 130 FirstSpecialInsts.clear(); 131 #ifndef NDEBUG 132 // The map should be valid after clearing (at least empty). 133 validateAll(); 134 #endif 135 } 136 137 bool ImplicitControlFlowTracking::isSpecialInstruction( 138 const Instruction *Insn) const { 139 // If a block's instruction doesn't always pass the control to its successor 140 // instruction, mark the block as having implicit control flow. We use them 141 // to avoid wrong assumptions of sort "if A is executed and B post-dominates 142 // A, then B is also executed". This is not true is there is an implicit 143 // control flow instruction (e.g. a guard) between them. 144 return !isGuaranteedToTransferExecutionToSuccessor(Insn); 145 } 146 147 bool MemoryWriteTracking::isSpecialInstruction( 148 const Instruction *Insn) const { 149 using namespace PatternMatch; 150 if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) 151 return false; 152 return Insn->mayWriteToMemory(); 153 } 154