LLVM  9.0.0svn
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"
23 
24 using namespace llvm;
25 
26 #ifndef NDEBUG
28  "ipt-expensive-asserts",
29  cl::desc("Perform expensive assert validation on every query to Instruction"
30  " Precedence Tracking"),
31  cl::init(false), cl::Hidden);
32 #endif
33 
35  const BasicBlock *BB) {
36 #ifndef NDEBUG
37  // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
38  // catch this situation as early as possible.
39  if (ExpensiveAsserts)
40  validateAll();
41  else
42  validate(BB);
43 #endif
44 
45  if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
46  fill(BB);
47  assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
48  }
49  return FirstSpecialInsts[BB];
50 }
51 
53  const BasicBlock *BB) {
54  return getFirstSpecialInstruction(BB) != nullptr;
55 }
56 
58  const Instruction *Insn) {
59  const Instruction *MaybeFirstSpecial =
61  return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
62 }
63 
64 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
65  FirstSpecialInsts.erase(BB);
66  for (auto &I : *BB)
67  if (isSpecialInstruction(&I)) {
68  FirstSpecialInsts[BB] = &I;
69  return;
70  }
71 
72  // Mark this block as having no special instructions.
73  FirstSpecialInsts[BB] = nullptr;
74 }
75 
76 #ifndef NDEBUG
78  auto It = FirstSpecialInsts.find(BB);
79  // Bail if we don't have anything cached for this block.
80  if (It == FirstSpecialInsts.end())
81  return;
82 
83  for (const Instruction &Insn : *BB)
84  if (isSpecialInstruction(&Insn)) {
85  assert(It->second == &Insn &&
86  "Cached first special instruction is wrong!");
87  return;
88  }
89 
90  assert(It->second == nullptr &&
91  "Block is marked as having special instructions but in fact it has "
92  "none!");
93 }
94 
95 void InstructionPrecedenceTracking::validateAll() const {
96  // Check that for every known block the cached value is correct.
97  for (auto &It : FirstSpecialInsts)
98  validate(It.first);
99 }
100 #endif
101 
103  const BasicBlock *BB) {
104  if (isSpecialInstruction(Inst))
105  FirstSpecialInsts.erase(BB);
106  OI.invalidateBlock(BB);
107 }
108 
110  if (isSpecialInstruction(Inst))
111  FirstSpecialInsts.erase(Inst->getParent());
112  OI.invalidateBlock(Inst->getParent());
113 }
114 
116  for (auto It : FirstSpecialInsts)
117  OI.invalidateBlock(It.first);
118  FirstSpecialInsts.clear();
119 #ifndef NDEBUG
120  // The map should be valid after clearing (at least empty).
121  validateAll();
122 #endif
123 }
124 
126  const Instruction *Insn) const {
127  // If a block's instruction doesn't always pass the control to its successor
128  // instruction, mark the block as having implicit control flow. We use them
129  // to avoid wrong assumptions of sort "if A is executed and B post-dominates
130  // A, then B is also executed". This is not true is there is an implicit
131  // control flow instruction (e.g. a guard) between them.
132  //
133  // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
134  // for volatile stores and loads because they can trap. The discussion on
135  // whether or not it is correct is still ongoing. We might want to get rid
136  // of this logic in the future. Anyways, trapping instructions shouldn't
137  // introduce implicit control flow, so we explicitly allow them here. This
138  // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
140  return false;
141  if (isa<LoadInst>(Insn)) {
142  assert(cast<LoadInst>(Insn)->isVolatile() &&
143  "Non-volatile load should transfer execution to successor!");
144  return false;
145  }
146  if (isa<StoreInst>(Insn)) {
147  assert(cast<StoreInst>(Insn)->isVolatile() &&
148  "Non-volatile store should transfer execution to successor!");
149  return false;
150  }
151  return true;
152 }
153 
155  const Instruction *Insn) const {
156  using namespace PatternMatch;
157  if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
158  return false;
159  return Insn->mayWriteToMemory();
160 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool dominates(const Instruction *, const Instruction *) const
Return true if first instruction dominates the second.
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
void clear()
Invalidates all information from this tracking.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
bool hasSpecialInstructions(const BasicBlock *BB)
Returns true iff at least one instruction from the basic block BB is special.
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)
virtual bool isSpecialInstruction(const Instruction *Insn) const
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
virtual bool isSpecialInstruction(const Instruction *Insn) const
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
void invalidateBlock(const BasicBlock *BB)
Invalidate the OrderedBasicBlock cache when its basic block changes.
const Instruction * getFirstSpecialInstruction(const BasicBlock *BB)
Returns the topmost special instruction from the block BB.
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...
#define I(x, y, z)
Definition: MD5.cpp:58
void removeInstruction(const Instruction *Inst)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
bool isPreceededBySpecialInstruction(const Instruction *Insn)
Returns true iff the first special instruction of Insn&#39;s block exists and dominates Insn...
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...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isVolatile(Instruction *Inst)
void validate(const Triple &TT, const FeatureBitset &FeatureBits)
const BasicBlock * getParent() const
Definition: Instruction.h:66