LLVM 20.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"
25
26using namespace llvm;
27
28#define DEBUG_TYPE "ipt"
29STATISTIC(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.
45 validateAll();
46 else
47 validate(BB);
48#endif
49
50 if (!FirstSpecialInsts.contains(BB)) {
51 fill(BB);
52 assert(FirstSpecialInsts.contains(BB) && "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
69void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
70 FirstSpecialInsts.erase(BB);
71 for (const 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
84void 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)
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
102void InstructionPrecedenceTracking::validateAll() const {
103 // Check that for every known block the cached value is correct.
104 for (const 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))
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}
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
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)
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
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...
void clear()
Invalidates all information from this tracking.
void removeUsersOf(const Instruction *Inst)
Notifies this tracking that we are going to replace all uses of Inst.
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.
void removeInstruction(const Instruction *Inst)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
const Instruction * getFirstSpecialInstruction(const BasicBlock *BB)
Returns the topmost special instruction from the block BB.
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...
bool hasSpecialInstructions(const BasicBlock *BB)
Returns true iff at least one instruction from the basic block BB is special.
bool isPreceededBySpecialInstruction(const Instruction *Insn)
Returns true iff the first special instruction of Insn's block exists and dominates Insn.
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
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...
iterator_range< user_iterator > users()
Definition: Value.h:421
const ParentTy * getParent() const
Definition: ilist_node.h:32
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...