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
localDominates(const Instruction * InstA,const Instruction * InstB) const16 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.
dominates(const Instruction * InstA,const Instruction * InstB) const31 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
dfsBefore(const Instruction * InstA,const Instruction * InstB) const40 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 }
51