1//===- OrderedBasicBlock.cpp --------------------------------- -*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the OrderedBasicBlock class. OrderedBasicBlock 11// maintains an interface where clients can query if one instruction comes 12// before another in a BasicBlock. Since BasicBlock currently lacks a reliable 13// way to query relative position between instructions one can use 14// OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a 15// source BasicBlock and maintains an internal Instruction -> Position map. A 16// OrderedBasicBlock instance should be discarded whenever the source 17// BasicBlock changes. 18// 19// It's currently used by the CaptureTracker in order to find relative 20// positions of a pair of instructions inside a BasicBlock. 21// 22//===----------------------------------------------------------------------===// 23 24#include "llvm/Analysis/OrderedBasicBlock.h" 25#include "llvm/IR/Instruction.h" 26using namespace llvm; 27 28OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB) 29 : NextInstPos(0), BB(BasicB) { 30 LastInstFound = BB->end(); 31} 32 33/// \brief Given no cached results, find if \p A comes before \p B in \p BB. 34/// Cache and number out instruction while walking \p BB. 35bool OrderedBasicBlock::comesBefore(const Instruction *A, 36 const Instruction *B) { 37 const Instruction *Inst = nullptr; 38 assert(!(LastInstFound == BB->end() && NextInstPos != 0) && 39 "Instruction supposed to be in NumberedInsts"); 40 41 // Start the search with the instruction found in the last lookup round. 42 auto II = BB->begin(); 43 auto IE = BB->end(); 44 if (LastInstFound != IE) 45 II = std::next(LastInstFound); 46 47 // Number all instructions up to the point where we find 'A' or 'B'. 48 for (; II != IE; ++II) { 49 Inst = cast<Instruction>(II); 50 NumberedInsts[Inst] = NextInstPos++; 51 if (Inst == A || Inst == B) 52 break; 53 } 54 55 assert(II != IE && "Instruction not found?"); 56 assert((Inst == A || Inst == B) && "Should find A or B"); 57 LastInstFound = II; 58 return Inst == A; 59} 60 61/// \brief Find out whether \p A dominates \p B, meaning whether \p A 62/// comes before \p B in \p BB. This is a simplification that considers 63/// cached instruction positions and ignores other basic blocks, being 64/// only relevant to compare relative instructions positions inside \p BB. 65bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) { 66 assert(A->getParent() == B->getParent() && 67 "Instructions must be in the same basic block!"); 68 69 // First we lookup the instructions. If they don't exist, lookup will give us 70 // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA 71 // exists and NB doesn't, it means NA must come before NB because we would 72 // have numbered NB as well if it didn't. The same is true for NB. If it 73 // exists, but NA does not, NA must come after it. If neither exist, we need 74 // to number the block and cache the results (by calling comesBefore). 75 auto NAI = NumberedInsts.find(A); 76 auto NBI = NumberedInsts.find(B); 77 if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end()) 78 return NAI->second < NBI->second; 79 if (NAI != NumberedInsts.end()) 80 return true; 81 if (NBI != NumberedInsts.end()) 82 return false; 83 84 return comesBefore(A, B); 85} 86