Line data    Source code

       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       12435 : 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       12435 :   const BasicBlock *IBB = InstA->getParent();
      23       12435 :   auto OBB = OBBMap.find(IBB);
      24       12435 :   if (OBB == OBBMap.end())
      25        8959 :     OBB = OBBMap.insert({IBB, make_unique<OrderedBasicBlock>(IBB)}).first;
      26       12435 :   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         690 : 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         690 :   if (InstA->getParent() == InstB->getParent())
      37         689 :     return localDominates(InstA, InstB);
      38           1 :   return DT->dominates(InstA->getParent(), InstB->getParent());
      39             : }
      40             : 
      41       77771 : 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       77771 :   if (InstA->getParent() == InstB->getParent())
      46       11746 :     return localDominates(InstA, InstB);
      47             : 
      48       66025 :   DomTreeNode *DA = DT->getNode(InstA->getParent());
      49       66025 :   DomTreeNode *DB = DT->getNode(InstB->getParent());
      50       66025 :   return DA->getDFSNumIn() < DB->getDFSNumIn();
      51             : }