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/IR/PatternMatch.h" 23 #include "llvm/Support/CommandLine.h" 24 25 using namespace llvm; 26 27 #ifndef NDEBUG 28 static cl::opt<bool> ExpensiveAsserts( 29 "ipt-expensive-asserts", 30 cl::desc("Perform expensive assert validation on every query to Instruction" 31 " Precedence Tracking"), 32 cl::init(false), cl::Hidden); 33 #endif 34 35 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction( 36 const BasicBlock *BB) { 37 #ifndef NDEBUG 38 // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to 39 // catch this situation as early as possible. 40 if (ExpensiveAsserts) 41 validateAll(); 42 else 43 validate(BB); 44 #endif 45 46 if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) { 47 fill(BB); 48 assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!"); 49 } 50 return FirstSpecialInsts[BB]; 51 } 52 53 bool InstructionPrecedenceTracking::hasSpecialInstructions( 54 const BasicBlock *BB) { 55 return getFirstSpecialInstruction(BB) != nullptr; 56 } 57 58 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction( 59 const Instruction *Insn) { 60 const Instruction *MaybeFirstSpecial = 61 getFirstSpecialInstruction(Insn->getParent()); 62 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn); 63 } 64 65 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) { 66 FirstSpecialInsts.erase(BB); 67 for (auto &I : *BB) 68 if (isSpecialInstruction(&I)) { 69 FirstSpecialInsts[BB] = &I; 70 return; 71 } 72 73 // Mark this block as having no special instructions. 74 FirstSpecialInsts[BB] = nullptr; 75 } 76 77 #ifndef NDEBUG 78 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const { 79 auto It = FirstSpecialInsts.find(BB); 80 // Bail if we don't have anything cached for this block. 81 if (It == FirstSpecialInsts.end()) 82 return; 83 84 for (const Instruction &Insn : *BB) 85 if (isSpecialInstruction(&Insn)) { 86 assert(It->second == &Insn && 87 "Cached first special instruction is wrong!"); 88 return; 89 } 90 91 assert(It->second == nullptr && 92 "Block is marked as having special instructions but in fact it has " 93 "none!"); 94 } 95 96 void InstructionPrecedenceTracking::validateAll() const { 97 // Check that for every known block the cached value is correct. 98 for (auto &It : FirstSpecialInsts) 99 validate(It.first); 100 } 101 #endif 102 103 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst, 104 const BasicBlock *BB) { 105 if (isSpecialInstruction(Inst)) 106 FirstSpecialInsts.erase(BB); 107 } 108 109 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) { 110 if (isSpecialInstruction(Inst)) 111 FirstSpecialInsts.erase(Inst->getParent()); 112 } 113 114 void InstructionPrecedenceTracking::clear() { 115 FirstSpecialInsts.clear(); 116 #ifndef NDEBUG 117 // The map should be valid after clearing (at least empty). 118 validateAll(); 119 #endif 120 } 121 122 bool ImplicitControlFlowTracking::isSpecialInstruction( 123 const Instruction *Insn) const { 124 // If a block's instruction doesn't always pass the control to its successor 125 // instruction, mark the block as having implicit control flow. We use them 126 // to avoid wrong assumptions of sort "if A is executed and B post-dominates 127 // A, then B is also executed". This is not true is there is an implicit 128 // control flow instruction (e.g. a guard) between them. 129 return !isGuaranteedToTransferExecutionToSuccessor(Insn); 130 } 131 132 bool MemoryWriteTracking::isSpecialInstruction( 133 const Instruction *Insn) const { 134 using namespace PatternMatch; 135 if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) 136 return false; 137 return Insn->mayWriteToMemory(); 138 } 139