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