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 "AnalysisOptions.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/PatternMatch.h"
24
25using namespace llvm;
26
27const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
28 const BasicBlock *BB) {
29#ifndef NDEBUG
30 // If there is a bug connected to invalid cache, turn on
31 // -ipt-expensive-asserts to catch this situation as early as possible.
32 if (getAnalysisOptions(BB->getContext()).ipt_expensive_asserts)
33 validateAll();
34 else
35 validate(BB);
36#endif
37
38 auto [It, Inserted] = FirstSpecialInsts.try_emplace(Key: BB);
39 if (Inserted) {
40 for (const auto &I : *BB) {
41 if (isSpecialInstruction(Insn: &I)) {
42 It->second = &I;
43 break;
44 }
45 }
46 }
47 return It->second;
48}
49
50bool InstructionPrecedenceTracking::hasSpecialInstructions(
51 const BasicBlock *BB) {
52 return getFirstSpecialInstruction(BB) != nullptr;
53}
54
55bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
56 const Instruction *Insn) {
57 const Instruction *MaybeFirstSpecial =
58 getFirstSpecialInstruction(BB: Insn->getParent());
59 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Other: Insn);
60}
61
62#ifndef NDEBUG
63void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
64 auto It = FirstSpecialInsts.find(BB);
65 // Bail if we don't have anything cached for this block.
66 if (It == FirstSpecialInsts.end())
67 return;
68
69 for (const Instruction &Insn : *BB)
70 if (isSpecialInstruction(&Insn)) {
71 assert(It->second == &Insn &&
72 "Cached first special instruction is wrong!");
73 return;
74 }
75
76 assert(It->second == nullptr &&
77 "Block is marked as having special instructions but in fact it has "
78 "none!");
79}
80
81void InstructionPrecedenceTracking::validateAll() const {
82 // Check that for every known block the cached value is correct.
83 for (const auto &It : FirstSpecialInsts)
84 validate(It.first);
85}
86#endif
87
88void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
89 const BasicBlock *BB) {
90 if (isSpecialInstruction(Insn: Inst))
91 FirstSpecialInsts.erase(Val: BB);
92}
93
94void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
95 auto *BB = Inst->getParent();
96 assert(BB && "must be called before instruction is actually removed");
97 auto It = FirstSpecialInsts.find(Val: BB);
98 if (It != FirstSpecialInsts.end() && It->second == Inst)
99 FirstSpecialInsts.erase(I: It);
100}
101
102void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
103 for (const auto *U : Inst->users()) {
104 if (const auto *UI = dyn_cast<Instruction>(Val: U))
105 removeInstruction(Inst: UI);
106 }
107}
108
109void InstructionPrecedenceTracking::clear() {
110 FirstSpecialInsts.clear();
111#ifndef NDEBUG
112 // The map should be valid after clearing (at least empty).
113 validateAll();
114#endif
115}
116
117bool ImplicitControlFlowTracking::isSpecialInstruction(
118 const Instruction *Insn) const {
119 // If a block's instruction doesn't always pass the control to its successor
120 // instruction, mark the block as having implicit control flow. We use them
121 // to avoid wrong assumptions of sort "if A is executed and B post-dominates
122 // A, then B is also executed". This is not true is there is an implicit
123 // control flow instruction (e.g. a guard) between them.
124 return !isGuaranteedToTransferExecutionToSuccessor(I: Insn);
125}
126
127bool MemoryWriteTracking::isSpecialInstruction(
128 const Instruction *Insn) const {
129 using namespace PatternMatch;
130 if (match(V: Insn, P: m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
131 return false;
132 return Insn->mayWriteToMemory();
133}
134