LLVM  14.0.0git
InstructionPrecedenceTracking.cpp
Go to the documentation of this file.
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 
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/IR/PatternMatch.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
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 
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 
58  const BasicBlock *BB) {
59  return getFirstSpecialInstruction(BB) != nullptr;
60 }
61 
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 (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 (auto &It : FirstSpecialInsts)
105  validate(It.first);
106 }
107 #endif
108 
110  const BasicBlock *BB) {
111  if (isSpecialInstruction(Inst))
112  FirstSpecialInsts.erase(BB);
113 }
114 
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 
123  for (const auto *U : Inst->users()) {
124  if (const auto *UI = dyn_cast<Instruction>(U))
125  removeInstruction(UI);
126  }
127 }
128 
130  FirstSpecialInsts.clear();
131 #ifndef NDEBUG
132  // The map should be valid after clearing (at least empty).
133  validateAll();
134 #endif
135 }
136 
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.
145 }
146 
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 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
Statistic.h
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
ValueTracking.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::Instruction::comesBefore
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Definition: Instruction.cpp:111
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
CommandLine.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
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::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
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
PatternMatch.h
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::cl::opt< bool >
ExpensiveAsserts
static cl::opt< bool > ExpensiveAsserts("ipt-expensive-asserts", cl::desc("Perform expensive assert validation on every query to Instruction" " Precedence Tracking"), cl::init(false), cl::Hidden)
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
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
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
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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::InstructionPrecedenceTracking::clear
void clear()
Invalidates all information from this tracking.
Definition: InstructionPrecedenceTracking.cpp:129
Insn
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
Definition: AArch64MIPeepholeOpt.cpp:86
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5186
InstructionPrecedenceTracking.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
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
llvm::cl::desc
Definition: CommandLine.h:412
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421