1//===-- InstructionPrecedenceTracking.h -------------------------*- 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#ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H 21#define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H 22 23#include "llvm/ADT/DenseMap.h" 24 25namespace llvm { 26 27class BasicBlock; 28class Instruction; 29 30class InstructionPrecedenceTracking { 31 // Maps a block to the topmost special instruction in it. If the value is 32 // nullptr, it means that it is known that this block does not contain any 33 // special instructions. 34 DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts; 35 36 // Fills information about the given block's special instructions. 37 void fill(const BasicBlock *BB); 38 39#ifndef NDEBUG 40 /// Asserts that the cached info for \p BB is up-to-date. This helps to catch 41 /// the usage error of accessing a block without properly invalidating after a 42 /// previous transform. 43 void validate(const BasicBlock *BB) const; 44 45 /// Asserts whether or not the contents of this tracking is up-to-date. This 46 /// helps to catch the usage error of accessing a block without properly 47 /// invalidating after a previous transform. 48 void validateAll() const; 49#endif 50 51protected: 52 /// Returns the topmost special instruction from the block \p BB. Returns 53 /// nullptr if there is no special instructions in the block. 54 const Instruction *getFirstSpecialInstruction(const BasicBlock *BB); 55 56 /// Returns true iff at least one instruction from the basic block \p BB is 57 /// special. 58 bool hasSpecialInstructions(const BasicBlock *BB); 59 60 /// Returns true iff the first special instruction of \p Insn's block exists 61 /// and dominates \p Insn. 62 bool isPreceededBySpecialInstruction(const Instruction *Insn); 63 64 /// A predicate that defines whether or not the instruction \p Insn is 65 /// considered special and needs to be tracked. Implementing this method in 66 /// children classes allows to implement tracking of implicit control flow, 67 /// memory writing instructions or any other kinds of instructions we might 68 /// be interested in. 69 virtual bool isSpecialInstruction(const Instruction *Insn) const = 0; 70 71 virtual ~InstructionPrecedenceTracking() = default; 72 73public: 74 /// Notifies this tracking that we are going to insert a new instruction \p 75 /// Inst to the basic block \p BB. It makes all necessary updates to internal 76 /// caches to keep them consistent. 77 void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB); 78 79 /// Notifies this tracking that we are going to remove the instruction \p Inst 80 /// It makes all necessary updates to internal caches to keep them consistent. 81 void removeInstruction(const Instruction *Inst); 82 83 /// Notifies this tracking that we are going to replace all uses of \p Inst. 84 /// It makes all necessary updates to internal caches to keep them consistent. 85 /// Should typically be called before a RAUW. 86 void removeUsersOf(const Instruction *Inst); 87 88 /// Invalidates all information from this tracking. 89 void clear(); 90}; 91 92/// This class allows to keep track on instructions with implicit control flow. 93/// These are instructions that may not pass execution to their successors. For 94/// example, throwing calls and guards do not always do this. If we need to know 95/// for sure that some instruction is guaranteed to execute if the given block 96/// is reached, then we need to make sure that there is no implicit control flow 97/// instruction (ICFI) preceding it. For example, this check is required if we 98/// perform PRE moving non-speculable instruction to other place. 99class ImplicitControlFlowTracking : public InstructionPrecedenceTracking { 100public: 101 /// Returns the topmost instruction with implicit control flow from the given 102 /// basic block. Returns nullptr if there is no such instructions in the block. 103 const Instruction *getFirstICFI(const BasicBlock *BB) { 104 return getFirstSpecialInstruction(BB); 105 } 106 107 /// Returns true if at least one instruction from the given basic block has 108 /// implicit control flow. 109 bool hasICF(const BasicBlock *BB) { 110 return hasSpecialInstructions(BB); 111 } 112 113 /// Returns true if the first ICFI of Insn's block exists and dominates Insn. 114 bool isDominatedByICFIFromSameBlock(const Instruction *Insn) { 115 return isPreceededBySpecialInstruction(Insn); 116 } 117 118 bool isSpecialInstruction(const Instruction *Insn) const override; 119}; 120 121class MemoryWriteTracking : public InstructionPrecedenceTracking { 122public: 123 /// Returns the topmost instruction that may write memory from the given 124 /// basic block. Returns nullptr if there is no such instructions in the block. 125 const Instruction *getFirstMemoryWrite(const BasicBlock *BB) { 126 return getFirstSpecialInstruction(BB); 127 } 128 129 /// Returns true if at least one instruction from the given basic block may 130 /// write memory. 131 bool mayWriteToMemory(const BasicBlock *BB) { 132 return hasSpecialInstructions(BB); 133 } 134 135 /// Returns true if the first memory writing instruction of Insn's block 136 /// exists and dominates Insn. 137 bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) { 138 return isPreceededBySpecialInstruction(Insn); 139 } 140 141 bool isSpecialInstruction(const Instruction *Insn) const override; 142}; 143 144} // llvm 145 146#endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H 147