LLVM  9.0.0svn
OrderedBasicBlock.cpp
Go to the documentation of this file.
1 //===- OrderedBasicBlock.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 //
9 // This file implements the OrderedBasicBlock class. OrderedBasicBlock
10 // maintains an interface where clients can query if one instruction comes
11 // before another in a BasicBlock. Since BasicBlock currently lacks a reliable
12 // way to query relative position between instructions one can use
13 // OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a
14 // source BasicBlock and maintains an internal Instruction -> Position map. A
15 // OrderedBasicBlock instance should be discarded whenever the source
16 // BasicBlock changes.
17 //
18 // It's currently used by the CaptureTracker in order to find relative
19 // positions of a pair of instructions inside a BasicBlock.
20 //
21 //===----------------------------------------------------------------------===//
22 
24 #include "llvm/IR/Instruction.h"
25 using namespace llvm;
26 
28  : NextInstPos(0), BB(BasicB) {
29  LastInstFound = BB->end();
30 }
31 
32 /// Given no cached results, find if \p A comes before \p B in \p BB.
33 /// Cache and number out instruction while walking \p BB.
34 bool OrderedBasicBlock::comesBefore(const Instruction *A,
35  const Instruction *B) {
36  const Instruction *Inst = nullptr;
37  assert(!(LastInstFound == BB->end() && NextInstPos != 0) &&
38  "Instruction supposed to be in NumberedInsts");
39  assert(A->getParent() == BB && "Instruction supposed to be in the block!");
40  assert(B->getParent() == BB && "Instruction supposed to be in the block!");
41 
42  // Start the search with the instruction found in the last lookup round.
43  auto II = BB->begin();
44  auto IE = BB->end();
45  if (LastInstFound != IE)
46  II = std::next(LastInstFound);
47 
48  // Number all instructions up to the point where we find 'A' or 'B'.
49  for (; II != IE; ++II) {
50  Inst = cast<Instruction>(II);
51  NumberedInsts[Inst] = NextInstPos++;
52  if (Inst == A || Inst == B)
53  break;
54  }
55 
56  assert(II != IE && "Instruction not found?");
57  assert((Inst == A || Inst == B) && "Should find A or B");
58  LastInstFound = II;
59  return Inst != B;
60 }
61 
62 /// Find out whether \p A dominates \p B, meaning whether \p A
63 /// comes before \p B in \p BB. This is a simplification that considers
64 /// cached instruction positions and ignores other basic blocks, being
65 /// only relevant to compare relative instructions positions inside \p BB.
67  assert(A->getParent() == B->getParent() &&
68  "Instructions must be in the same basic block!");
69  assert(A->getParent() == BB && "Instructions must be in the tracked block!");
70 
71  // First we lookup the instructions. If they don't exist, lookup will give us
72  // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA
73  // exists and NB doesn't, it means NA must come before NB because we would
74  // have numbered NB as well if it didn't. The same is true for NB. If it
75  // exists, but NA does not, NA must come after it. If neither exist, we need
76  // to number the block and cache the results (by calling comesBefore).
77  auto NAI = NumberedInsts.find(A);
78  auto NBI = NumberedInsts.find(B);
79  if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end())
80  return NAI->second < NBI->second;
81  if (NAI != NumberedInsts.end())
82  return true;
83  if (NBI != NumberedInsts.end())
84  return false;
85 
86  return comesBefore(A, B);
87 }
88 
90  if (LastInstFound != BB->end() && I == &*LastInstFound) {
91  if (LastInstFound == BB->begin()) {
92  LastInstFound = BB->end();
93  NextInstPos = 0;
94  } else
95  LastInstFound--;
96  }
97 
98  NumberedInsts.erase(I);
99 }
100 
102  const Instruction *New) {
103  auto OI = NumberedInsts.find(Old);
104  if (OI == NumberedInsts.end())
105  return;
106 
107  NumberedInsts.insert({New, OI->second});
108  if (LastInstFound != BB->end() && Old == &*LastInstFound)
109  LastInstFound = New->getIterator();
110  NumberedInsts.erase(Old);
111 }
void eraseInstruction(const Instruction *I)
Remove from the ordering, if it is present.
OrderedBasicBlock(const BasicBlock *BasicB)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool dominates(const Instruction *A, const Instruction *B)
Find out whether A dominates B, meaning whether A comes before B in BB.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
self_iterator getIterator()
Definition: ilist_node.h:81
iterator end()
Definition: BasicBlock.h:270
void replaceInstruction(const Instruction *Old, const Instruction *New)
Replace Old with New in the ordering.
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const BasicBlock * getParent() const
Definition: Instruction.h:66