LLVM  14.0.0git
InstructionPrecedenceTracking.h
Go to the documentation of this file.
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 
25 namespace llvm {
26 
27 class BasicBlock;
28 class Instruction;
29 
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.
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 
51 protected:
52  /// Returns the topmost special instruction from the block \p BB. Returns
53  /// nullptr if there is no special instructions in the block.
55 
56  /// Returns true iff at least one instruction from the basic block \p BB is
57  /// special.
59 
60  /// Returns true iff the first special instruction of \p Insn's block exists
61  /// and dominates \p 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 
73 public:
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.
100 public:
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.
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.
116  }
117 
118  bool isSpecialInstruction(const Instruction *Insn) const override;
119 };
120 
122 public:
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.
127  }
128 
129  /// Returns true if at least one instruction from the given basic block may
130  /// write memory.
132  return hasSpecialInstructions(BB);
133  }
134 
135  /// Returns true if the first memory writing instruction of Insn's block
136  /// exists and dominates Insn.
139  }
140 
141  bool isSpecialInstruction(const Instruction *Insn) const override;
142 };
143 
144 } // llvm
145 
146 #endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
llvm::ImplicitControlFlowTracking
This class allows to keep track on instructions with implicit control flow.
Definition: InstructionPrecedenceTracking.h:99
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::ImplicitControlFlowTracking::getFirstICFI
const Instruction * getFirstICFI(const BasicBlock *BB)
Returns the topmost instruction with implicit control flow from the given basic block.
Definition: InstructionPrecedenceTracking.h:103
llvm::MemoryWriteTracking::getFirstMemoryWrite
const Instruction * getFirstMemoryWrite(const BasicBlock *BB)
Returns the topmost instruction that may write memory from the given basic block.
Definition: InstructionPrecedenceTracking.h:125
llvm::InstructionPrecedenceTracking::getFirstSpecialInstruction
const Instruction * getFirstSpecialInstruction(const BasicBlock *BB)
Returns the topmost special instruction from the block BB.
Definition: InstructionPrecedenceTracking.cpp:39
llvm::InstructionPrecedenceTracking::insertInstructionTo
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Notifies this tracking that we are going to insert a new instruction Inst to the basic block BB.
Definition: InstructionPrecedenceTracking.cpp:109
DenseMap.h
llvm::InstructionPrecedenceTracking::~InstructionPrecedenceTracking
virtual ~InstructionPrecedenceTracking()=default
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::InstructionPrecedenceTracking::isSpecialInstruction
virtual bool isSpecialInstruction(const Instruction *Insn) const =0
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
llvm::Instruction
Definition: Instruction.h:45
llvm::MemoryWriteTracking::mayWriteToMemory
bool mayWriteToMemory(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block may write memory.
Definition: InstructionPrecedenceTracking.h:131
llvm::InstructionPrecedenceTracking::isPreceededBySpecialInstruction
bool isPreceededBySpecialInstruction(const Instruction *Insn)
Returns true iff the first special instruction of Insn's block exists and dominates Insn.
Definition: InstructionPrecedenceTracking.cpp:62
llvm::MemoryWriteTracking
Definition: InstructionPrecedenceTracking.h:121
llvm::ImplicitControlFlowTracking::isSpecialInstruction
bool isSpecialInstruction(const Instruction *Insn) const override
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
Definition: InstructionPrecedenceTracking.cpp:137
llvm::MemoryWriteTracking::isSpecialInstruction
bool isSpecialInstruction(const Instruction *Insn) const override
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
Definition: InstructionPrecedenceTracking.cpp:147
llvm::MemoryWriteTracking::isDominatedByMemoryWriteFromSameBlock
bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn)
Returns true if the first memory writing instruction of Insn's block exists and dominates Insn.
Definition: InstructionPrecedenceTracking.h:137
llvm::InstructionPrecedenceTracking
Definition: InstructionPrecedenceTracking.h:30
llvm::DenseMap
Definition: DenseMap.h:714
llvm::InstructionPrecedenceTracking::removeUsersOf
void removeUsersOf(const Instruction *Inst)
Notifies this tracking that we are going to replace all uses of Inst.
Definition: InstructionPrecedenceTracking.cpp:122
llvm::InstructionPrecedenceTracking::removeInstruction
void removeInstruction(const Instruction *Inst)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
Definition: InstructionPrecedenceTracking.cpp:115
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::InstructionPrecedenceTracking::hasSpecialInstructions
bool hasSpecialInstructions(const BasicBlock *BB)
Returns true iff at least one instruction from the basic block BB is special.
Definition: InstructionPrecedenceTracking.cpp:57
llvm::ImplicitControlFlowTracking::isDominatedByICFIFromSameBlock
bool isDominatedByICFIFromSameBlock(const Instruction *Insn)
Returns true if the first ICFI of Insn's block exists and dominates Insn.
Definition: InstructionPrecedenceTracking.h:114
llvm::InstructionPrecedenceTracking::clear
void clear()
Invalidates all information from this tracking.
Definition: InstructionPrecedenceTracking.cpp:129
Insn
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
Definition: AArch64MIPeepholeOpt.cpp:74
llvm::ImplicitControlFlowTracking::hasICF
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
Definition: InstructionPrecedenceTracking.h:109
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39