1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_ 18 #define ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_ 19 20 #include "nodes.h" 21 22 namespace art { 23 24 // Helper class for finding common dominators of two or more blocks in a graph. 25 // The domination information of a graph must not be modified while there is 26 // a CommonDominator object as it's internal state could become invalid. 27 class CommonDominator { 28 public: 29 // Convenience function to find the common dominator of 2 blocks. ForPair(HBasicBlock * block1,HBasicBlock * block2)30 static HBasicBlock* ForPair(HBasicBlock* block1, HBasicBlock* block2) { 31 CommonDominator finder(block1); 32 finder.Update(block2); 33 return finder.Get(); 34 } 35 36 // Create a finder starting with a given block. CommonDominator(HBasicBlock * block)37 explicit CommonDominator(HBasicBlock* block) 38 : dominator_(block), chain_length_(ChainLength(block)) { 39 } 40 41 // Update the common dominator with another block. Update(HBasicBlock * block)42 void Update(HBasicBlock* block) { 43 DCHECK(block != nullptr); 44 if (dominator_ == nullptr) { 45 dominator_ = block; 46 chain_length_ = ChainLength(block); 47 return; 48 } 49 HBasicBlock* block2 = dominator_; 50 DCHECK(block2 != nullptr); 51 if (block == block2) { 52 return; 53 } 54 size_t chain_length = ChainLength(block); 55 size_t chain_length2 = chain_length_; 56 // Equalize the chain lengths 57 for ( ; chain_length > chain_length2; --chain_length) { 58 block = block->GetDominator(); 59 DCHECK(block != nullptr); 60 } 61 for ( ; chain_length2 > chain_length; --chain_length2) { 62 block2 = block2->GetDominator(); 63 DCHECK(block2 != nullptr); 64 } 65 // Now run up the chain until we hit the common dominator. 66 while (block != block2) { 67 --chain_length; 68 block = block->GetDominator(); 69 DCHECK(block != nullptr); 70 block2 = block2->GetDominator(); 71 DCHECK(block2 != nullptr); 72 } 73 dominator_ = block; 74 chain_length_ = chain_length; 75 } 76 Get()77 HBasicBlock* Get() const { 78 return dominator_; 79 } 80 81 private: ChainLength(HBasicBlock * block)82 static size_t ChainLength(HBasicBlock* block) { 83 size_t result = 0; 84 while (block != nullptr) { 85 ++result; 86 block = block->GetDominator(); 87 } 88 return result; 89 } 90 91 HBasicBlock* dominator_; 92 size_t chain_length_; 93 }; 94 95 } // namespace art 96 97 #endif // ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_ 98