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/Transforms/Utils/OrderedInstructions.h"
15 using namespace llvm;
16
localDominates(const Instruction * InstA,const Instruction * InstB) const17 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.
dominates(const Instruction * InstA,const Instruction * InstB) const32 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
dfsBefore(const Instruction * InstA,const Instruction * InstB) const41 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 }
52