lib/Analysis/OrderedInstructions.cpp

   1 //===-- OrderedInstructions.cpp - Instruction dominance function ---------===//
   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 defines utility to check dominance relation of 2 instructions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/OrderedInstructions.h"
  15 using namespace llvm;
  16
  17 bool OrderedInstructions::localDominates(const Instruction *InstA,
  18                                          const Instruction *InstB) const {
  19   assert(InstA->getParent() == InstB->getParent() &&
  20          "Instructions must be in the same basic block");
  21
  22   const BasicBlock *IBB = InstA->getParent();
  23   auto OBB = OBBMap.find(IBB);
  24   if (OBB == OBBMap.end())
  25     OBB = OBBMap.insert({IBB, make_unique<OrderedBasicBlock>(IBB)}).first;
  26   return OBB->second->dominates(InstA, InstB);
  27 }
  28
  29 /// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
  30 /// if the instructions are in the same basic block, Otherwise, use dominator
  31 /// tree.
  32 bool OrderedInstructions::dominates(const Instruction *InstA,
  33                                     const Instruction *InstB) const {
  34   // Use ordered basic block to do dominance check in case the 2 instructions
  35   // are in the same basic block.
  36   if (InstA->getParent() == InstB->getParent())
  37     return localDominates(InstA, InstB);
  38   return DT->dominates(InstA->getParent(), InstB->getParent());
  39 }
  40
  41 bool OrderedInstructions::dfsBefore(const Instruction *InstA,
  42                                     const Instruction *InstB) const {
  43   // Use ordered basic block in case the 2 instructions are in the same basic
  44   // block.
  45   if (InstA->getParent() == InstB->getParent())
  46     return localDominates(InstA, InstB);
  47
  48   DomTreeNode *DA = DT->getNode(InstA->getParent());
  49   DomTreeNode *DB = DT->getNode(InstB->getParent());
  50   return DA->getDFSNumIn() < DB->getDFSNumIn();
  51 }