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" 26 using namespace llvm; 27 28 OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB) 29 : NextInstPos(0), BB(BasicB) { 30 LastInstFound = BB->end(); 31 } 32 33 /// 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. 35 bool 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 != B; 59 } 60 61 /// 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. 65 bool 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
