LLVM  13.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/IR/PatternMatch.h"
24 
25 using namespace llvm;
26 
27 #ifndef NDEBUG
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 
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 
54  const BasicBlock *BB) {
55  return getFirstSpecialInstruction(BB) != nullptr;
56 }
57 
59  const Instruction *Insn) {
60  const Instruction *MaybeFirstSpecial =
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 
104  const BasicBlock *BB) {
105  if (isSpecialInstruction(Inst))
106  FirstSpecialInsts.erase(BB);
107 }
108 
110  if (isSpecialInstruction(Inst))
111  FirstSpecialInsts.erase(Inst->getParent());
112 }
113 
115  for (const auto *U : Inst->users()) {
116  if (const auto *UI = dyn_cast<Instruction>(U))
117  removeInstruction(UI);
118  }
119 }
120 
122  FirstSpecialInsts.clear();
123 #ifndef NDEBUG
124  // The map should be valid after clearing (at least empty).
125  validateAll();
126 #endif
127 }
128 
130  const Instruction *Insn) const {
131  // If a block's instruction doesn't always pass the control to its successor
132  // instruction, mark the block as having implicit control flow. We use them
133  // to avoid wrong assumptions of sort "if A is executed and B post-dominates
134  // A, then B is also executed". This is not true is there is an implicit
135  // control flow instruction (e.g. a guard) between them.
137 }
138 
140  const Instruction *Insn) const {
141  using namespace PatternMatch;
142  if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
143  return false;
144  return Insn->mayWriteToMemory();
145 }
llvm
Definition: AllocatorList.h:23
llvm::InstructionPrecedenceTracking::getFirstSpecialInstruction
const Instruction * getFirstSpecialInstruction(const BasicBlock *BB)
Returns the topmost special instruction from the block BB.
Definition: InstructionPrecedenceTracking.cpp:35
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:103
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::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:58
PatternMatch.h
llvm::Instruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: Instruction.cpp:567
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:129
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:139
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:114
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
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:109
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:53
llvm::InstructionPrecedenceTracking::clear
void clear()
Invalidates all information from this tracking.
Definition: InstructionPrecedenceTracking.cpp:121
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:5224
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:414
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422