1 //===-- InstructionPrecedenceTracking.cpp -----------------------*- C++ -*-===// 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 // Implements a class that is able to define some instructions as "special" 10 // (e.g. as having implicit control flow, or writing memory, or having another 11 // interesting property) and then efficiently answers queries of the types: 12 // 1. Are there any special instructions in the block of interest? 13 // 2. Return first of the special instructions in the given block; 14 // 3. Check if the given instruction is preceeded by the first special 15 // instruction in the same block. 16 // The class provides caching that allows to answer these queries quickly. The 17 // user must make sure that the cached data is invalidated properly whenever 18 // a content of some tracked block is changed. 19 //===----------------------------------------------------------------------===// 20 21 #include "llvm/Analysis/InstructionPrecedenceTracking.h" 22 #include "llvm/Analysis/ValueTracking.h" 23 24 using namespace llvm; 25 26 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction( 27 const BasicBlock *BB) { 28 if (!KnownBlocks.count(BB)) 29 fill(BB); 30 auto *FirstICF = FirstSpecialInsts.lookup(BB); 31 assert((!FirstICF || FirstICF->getParent() == BB) && "Inconsistent cache!"); 32 return FirstICF; 33 } 34 35 bool InstructionPrecedenceTracking::hasSpecialInstructions( 36 const BasicBlock *BB) { 37 return getFirstSpecialInstruction(BB) != nullptr; 38 } 39 40 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction( 41 const Instruction *Insn) { 42 const Instruction *MaybeFirstICF = 43 getFirstSpecialInstruction(Insn->getParent()); 44 return MaybeFirstICF && OI.dominates(MaybeFirstICF, Insn); 45 } 46 47 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) { 48 FirstSpecialInsts.erase(BB); 49 for (auto &I : *BB) 50 if (isSpecialInstruction(&I)) { 51 FirstSpecialInsts[BB] = &I; 52 break; 53 } 54 55 // Mark this block as having a known result. 56 KnownBlocks.insert(BB); 57 } 58 59 void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) { 60 OI.invalidateBlock(BB); 61 FirstSpecialInsts.erase(BB); 62 KnownBlocks.erase(BB); 63 } 64 65 void InstructionPrecedenceTracking::clear() { 66 for (auto It : FirstSpecialInsts) 67 OI.invalidateBlock(It.first); 68 FirstSpecialInsts.clear(); 69 KnownBlocks.clear(); 70 } 71 72 bool ImplicitControlFlowTracking::isSpecialInstruction( 73 const Instruction *Insn) const { 74 // If a block's instruction doesn't always pass the control to its successor 75 // instruction, mark the block as having implicit control flow. We use them 76 // to avoid wrong assumptions of sort "if A is executed and B post-dominates 77 // A, then B is also executed". This is not true is there is an implicit 78 // control flow instruction (e.g. a guard) between them. 79 // 80 // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false 81 // for volatile stores and loads because they can trap. The discussion on 82 // whether or not it is correct is still ongoing. We might want to get rid 83 // of this logic in the future. Anyways, trapping instructions shouldn't 84 // introduce implicit control flow, so we explicitly allow them here. This 85 // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed. 86 if (isGuaranteedToTransferExecutionToSuccessor(Insn)) 87 return false; 88 if (isa<LoadInst>(Insn)) { 89 assert(cast<LoadInst>(Insn)->isVolatile() && 90 "Non-volatile load should transfer execution to successor!"); 91 return false; 92 } 93 if (isa<StoreInst>(Insn)) { 94 assert(cast<StoreInst>(Insn)->isVolatile() && 95 "Non-volatile store should transfer execution to successor!"); 96 return false; 97 } 98 return true; 99 } 100