1 // Copyright (c) 2018 Google LLC 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "source/opt/dominator_analysis.h" 16 17 #include <unordered_set> 18 19 #include "source/opt/ir_context.h" 20 21 namespace spvtools { 22 namespace opt { 23 CommonDominator(BasicBlock * b1,BasicBlock * b2) const24BasicBlock* DominatorAnalysisBase::CommonDominator(BasicBlock* b1, 25 BasicBlock* b2) const { 26 if (!b1 || !b2) return nullptr; 27 28 std::unordered_set<BasicBlock*> seen; 29 BasicBlock* block = b1; 30 while (block && seen.insert(block).second) { 31 block = ImmediateDominator(block); 32 } 33 34 block = b2; 35 while (block && !seen.count(block)) { 36 block = ImmediateDominator(block); 37 } 38 39 return block; 40 } 41 Dominates(Instruction * a,Instruction * b) const42bool DominatorAnalysisBase::Dominates(Instruction* a, Instruction* b) const { 43 if (!a || !b) { 44 return false; 45 } 46 47 if (a == b) { 48 return true; 49 } 50 51 BasicBlock* bb_a = a->context()->get_instr_block(a); 52 BasicBlock* bb_b = b->context()->get_instr_block(b); 53 54 if (bb_a != bb_b) { 55 return tree_.Dominates(bb_a, bb_b); 56 } 57 58 Instruction* current_inst = a; 59 while ((current_inst = current_inst->NextNode())) { 60 if (current_inst == b) { 61 return true; 62 } 63 } 64 return false; 65 } 66 67 } // namespace opt 68 } // namespace spvtools 69