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 DCHECK(block != nullptr); 40 } 41 42 // Update the common dominator with another block. Update(HBasicBlock * block)43 void Update(HBasicBlock* block) { 44 DCHECK(block != nullptr); 45 HBasicBlock* block2 = dominator_; 46 DCHECK(block2 != nullptr); 47 if (block == block2) { 48 return; 49 } 50 size_t chain_length = ChainLength(block); 51 size_t chain_length2 = chain_length_; 52 // Equalize the chain lengths 53 for ( ; chain_length > chain_length2; --chain_length) { 54 block = block->GetDominator(); 55 DCHECK(block != nullptr); 56 } 57 for ( ; chain_length2 > chain_length; --chain_length2) { 58 block2 = block2->GetDominator(); 59 DCHECK(block2 != nullptr); 60 } 61 // Now run up the chain until we hit the common dominator. 62 while (block != block2) { 63 --chain_length; 64 block = block->GetDominator(); 65 DCHECK(block != nullptr); 66 block2 = block2->GetDominator(); 67 DCHECK(block2 != nullptr); 68 } 69 dominator_ = block; 70 chain_length_ = chain_length; 71 } 72 Get()73 HBasicBlock* Get() const { 74 return dominator_; 75 } 76 77 private: ChainLength(HBasicBlock * block)78 static size_t ChainLength(HBasicBlock* block) { 79 size_t result = 0; 80 while (block != nullptr) { 81 ++result; 82 block = block->GetDominator(); 83 } 84 return result; 85 } 86 87 HBasicBlock* dominator_; 88 size_t chain_length_; 89 }; 90 91 } // namespace art 92 93 #endif // ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_ 94