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  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
53bool InstructionPrecedenceTracking::hasSpecialInstructions(
54    const BasicBlock *BB) {
55  return getFirstSpecialInstruction(BB) != nullptr;
56}
57
58bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
59    const Instruction *Insn) {
60  const Instruction *MaybeFirstSpecial =
61      getFirstSpecialInstruction(Insn->getParent());
62  return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
63}
64
65void 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
78void 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
96void 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
103void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
104                                                        const BasicBlock *BB) {
105  if (isSpecialInstruction(Inst))
106    FirstSpecialInsts.erase(BB);
107  OI.invalidateBlock(BB);
108}
109
110void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
111  if (isSpecialInstruction(Inst))
112    FirstSpecialInsts.erase(Inst->getParent());
113  OI.invalidateBlock(Inst->getParent());
114}
115
116void InstructionPrecedenceTracking::clear() {
117  for (auto It : FirstSpecialInsts)
118    OI.invalidateBlock(It.first);
119  FirstSpecialInsts.clear();
120#ifndef NDEBUG
121  // The map should be valid after clearing (at least empty).
122  validateAll();
123#endif
124}
125
126bool ImplicitControlFlowTracking::isSpecialInstruction(
127    const Instruction *Insn) const {
128  // If a block's instruction doesn't always pass the control to its successor
129  // instruction, mark the block as having implicit control flow. We use them
130  // to avoid wrong assumptions of sort "if A is executed and B post-dominates
131  // A, then B is also executed". This is not true is there is an implicit
132  // control flow instruction (e.g. a guard) between them.
133  //
134  // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
135  // for volatile stores and loads because they can trap. The discussion on
136  // whether or not it is correct is still ongoing. We might want to get rid
137  // of this logic in the future. Anyways, trapping instructions shouldn't
138  // introduce implicit control flow, so we explicitly allow them here. This
139  // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
140  if (isGuaranteedToTransferExecutionToSuccessor(Insn))
141    return false;
142  if (isa<LoadInst>(Insn)) {
143    assert(cast<LoadInst>(Insn)->isVolatile() &&
144           "Non-volatile load should transfer execution to successor!");
145    return false;
146  }
147  if (isa<StoreInst>(Insn)) {
148    assert(cast<StoreInst>(Insn)->isVolatile() &&
149           "Non-volatile store should transfer execution to successor!");
150    return false;
151  }
152  return true;
153}
154
155bool MemoryWriteTracking::isSpecialInstruction(
156    const Instruction *Insn) const {
157  using namespace PatternMatch;
158  if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
159    return false;
160  return Insn->mayWriteToMemory();
161}
162