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
20#include "llvm/Analysis/InstructionPrecedenceTracking.h"
21#include "llvm/Analysis/ValueTracking.h"
22#include "llvm/IR/PatternMatch.h"
23#include "llvm/Support/CommandLine.h"
24
25using namespace llvm;
26
27#ifndef NDEBUG
28static cl::opt<bool> ExpensiveAsserts(
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
35const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
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 auto [It, Inserted] = FirstSpecialInsts.try_emplace(Key: BB);
47 if (Inserted) {
48 for (const auto &I : *BB) {
49 if (isSpecialInstruction(Insn: &I)) {
50 It->second = &I;
51 break;
52 }
53 }
54 }
55 return It->second;
56}
57
58bool InstructionPrecedenceTracking::hasSpecialInstructions(
59 const BasicBlock *BB) {
60 return getFirstSpecialInstruction(BB) != nullptr;
61}
62
63bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
64 const Instruction *Insn) {
65 const Instruction *MaybeFirstSpecial =
66 getFirstSpecialInstruction(BB: Insn->getParent());
67 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Other: Insn);
68}
69
70#ifndef NDEBUG
71void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
72 auto It = FirstSpecialInsts.find(BB);
73 // Bail if we don't have anything cached for this block.
74 if (It == FirstSpecialInsts.end())
75 return;
76
77 for (const Instruction &Insn : *BB)
78 if (isSpecialInstruction(&Insn)) {
79 assert(It->second == &Insn &&
80 "Cached first special instruction is wrong!");
81 return;
82 }
83
84 assert(It->second == nullptr &&
85 "Block is marked as having special instructions but in fact it has "
86 "none!");
87}
88
89void InstructionPrecedenceTracking::validateAll() const {
90 // Check that for every known block the cached value is correct.
91 for (const auto &It : FirstSpecialInsts)
92 validate(It.first);
93}
94#endif
95
96void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
97 const BasicBlock *BB) {
98 if (isSpecialInstruction(Insn: Inst))
99 FirstSpecialInsts.erase(Val: BB);
100}
101
102void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
103 auto *BB = Inst->getParent();
104 assert(BB && "must be called before instruction is actually removed");
105 auto It = FirstSpecialInsts.find(Val: BB);
106 if (It != FirstSpecialInsts.end() && It->second == Inst)
107 FirstSpecialInsts.erase(I: It);
108}
109
110void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
111 for (const auto *U : Inst->users()) {
112 if (const auto *UI = dyn_cast<Instruction>(Val: U))
113 removeInstruction(Inst: UI);
114 }
115}
116
117void InstructionPrecedenceTracking::clear() {
118 FirstSpecialInsts.clear();
119#ifndef NDEBUG
120 // The map should be valid after clearing (at least empty).
121 validateAll();
122#endif
123}
124
125bool ImplicitControlFlowTracking::isSpecialInstruction(
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 return !isGuaranteedToTransferExecutionToSuccessor(I: Insn);
133}
134
135bool MemoryWriteTracking::isSpecialInstruction(
136 const Instruction *Insn) const {
137 using namespace PatternMatch;
138 if (match(V: Insn, P: m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
139 return false;
140 return Insn->mayWriteToMemory();
141}
142