1343171Sdim//===-- OrderedInstructions.cpp - Instruction dominance function ---------===// 2343171Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6343171Sdim// 7343171Sdim//===----------------------------------------------------------------------===// 8343171Sdim// 9343171Sdim// This file defines utility to check dominance relation of 2 instructions. 10343171Sdim// 11343171Sdim//===----------------------------------------------------------------------===// 12343171Sdim 13343171Sdim#include "llvm/Analysis/OrderedInstructions.h" 14343171Sdimusing namespace llvm; 15343171Sdim 16343171Sdimbool OrderedInstructions::localDominates(const Instruction *InstA, 17343171Sdim const Instruction *InstB) const { 18343171Sdim assert(InstA->getParent() == InstB->getParent() && 19343171Sdim "Instructions must be in the same basic block"); 20343171Sdim 21343171Sdim const BasicBlock *IBB = InstA->getParent(); 22343171Sdim auto OBB = OBBMap.find(IBB); 23343171Sdim if (OBB == OBBMap.end()) 24360784Sdim OBB = OBBMap.insert({IBB, std::make_unique<OrderedBasicBlock>(IBB)}).first; 25343171Sdim return OBB->second->dominates(InstA, InstB); 26343171Sdim} 27343171Sdim 28343171Sdim/// Given 2 instructions, use OrderedBasicBlock to check for dominance relation 29343171Sdim/// if the instructions are in the same basic block, Otherwise, use dominator 30343171Sdim/// tree. 31343171Sdimbool OrderedInstructions::dominates(const Instruction *InstA, 32343171Sdim const Instruction *InstB) const { 33343171Sdim // Use ordered basic block to do dominance check in case the 2 instructions 34343171Sdim // are in the same basic block. 35343171Sdim if (InstA->getParent() == InstB->getParent()) 36343171Sdim return localDominates(InstA, InstB); 37343171Sdim return DT->dominates(InstA->getParent(), InstB->getParent()); 38343171Sdim} 39343171Sdim 40343171Sdimbool OrderedInstructions::dfsBefore(const Instruction *InstA, 41343171Sdim const Instruction *InstB) const { 42343171Sdim // Use ordered basic block in case the 2 instructions are in the same basic 43343171Sdim // block. 44343171Sdim if (InstA->getParent() == InstB->getParent()) 45343171Sdim return localDominates(InstA, InstB); 46343171Sdim 47343171Sdim DomTreeNode *DA = DT->getNode(InstA->getParent()); 48343171Sdim DomTreeNode *DB = DT->getNode(InstB->getParent()); 49343171Sdim return DA->getDFSNumIn() < DB->getDFSNumIn(); 50343171Sdim} 51