contrib/llvm-project/llvm/lib/Analysis/OrderedInstructions.cpp

   1 //===-- OrderedInstructions.cpp - Instruction dominance function ---------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines utility to check dominance relation of 2 instructions.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Analysis/OrderedInstructions.h"
  14 using namespace llvm;
  15
  16 bool OrderedInstructions::localDominates(const Instruction *InstA,
  17                                          const Instruction *InstB) const {
  18   assert(InstA->getParent() == InstB->getParent() &&
  19          "Instructions must be in the same basic block");
  20
  21   const BasicBlock *IBB = InstA->getParent();
  22   auto OBB = OBBMap.find(IBB);
  23   if (OBB == OBBMap.end())
  24     OBB = OBBMap.insert({IBB, std::make_unique<OrderedBasicBlock>(IBB)}).first;
  25   return OBB->second->dominates(InstA, InstB);
  26 }
  27
  28 /// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
  29 /// if the instructions are in the same basic block, Otherwise, use dominator
  30 /// tree.
  31 bool OrderedInstructions::dominates(const Instruction *InstA,
  32                                     const Instruction *InstB) const {
  33   // Use ordered basic block to do dominance check in case the 2 instructions
  34   // are in the same basic block.
  35   if (InstA->getParent() == InstB->getParent())
  36     return localDominates(InstA, InstB);
  37   return DT->dominates(InstA->getParent(), InstB->getParent());
  38 }
  39
  40 bool OrderedInstructions::dfsBefore(const Instruction *InstA,
  41                                     const Instruction *InstB) const {
  42   // Use ordered basic block in case the 2 instructions are in the same basic
  43   // block.
  44   if (InstA->getParent() == InstB->getParent())
  45     return localDominates(InstA, InstB);
  46
  47   DomTreeNode *DA = DT->getNode(InstA->getParent());
  48   DomTreeNode *DB = DT->getNode(InstB->getParent());
  49   return DA->getDFSNumIn() < DB->getDFSNumIn();
  50 }