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 "base/macros.h"
21 #include "nodes.h"
22 
23 namespace art HIDDEN {
24 
25 // Helper class for finding common dominators of two or more blocks in a graph.
26 // The domination information of a graph must not be modified while there is
27 // a CommonDominator object as it's internal state could become invalid.
28 class CommonDominator {
29  public:
30   // Convenience function to find the common dominator of 2 blocks.
ForPair(HBasicBlock * block1,HBasicBlock * block2)31   static HBasicBlock* ForPair(HBasicBlock* block1, HBasicBlock* block2) {
32     CommonDominator finder(block1);
33     finder.Update(block2);
34     return finder.Get();
35   }
36 
37   // Create a finder starting with a given block.
CommonDominator(HBasicBlock * block)38   explicit CommonDominator(HBasicBlock* block)
39       : dominator_(block), chain_length_(ChainLength(block)) {
40   }
41 
42   // Update the common dominator with another block.
Update(HBasicBlock * block)43   void Update(HBasicBlock* block) {
44     DCHECK(block != nullptr);
45     if (dominator_ == nullptr) {
46       dominator_ = block;
47       chain_length_ = ChainLength(block);
48       return;
49     }
50     HBasicBlock* block2 = dominator_;
51     DCHECK(block2 != nullptr);
52     if (block == block2) {
53       return;
54     }
55     size_t chain_length = ChainLength(block);
56     size_t chain_length2 = chain_length_;
57     // Equalize the chain lengths
58     for ( ; chain_length > chain_length2; --chain_length) {
59       block = block->GetDominator();
60       DCHECK(block != nullptr);
61     }
62     for ( ; chain_length2 > chain_length; --chain_length2) {
63       block2 = block2->GetDominator();
64       DCHECK(block2 != nullptr);
65     }
66     // Now run up the chain until we hit the common dominator.
67     while (block != block2) {
68       --chain_length;
69       block = block->GetDominator();
70       DCHECK(block != nullptr);
71       block2 = block2->GetDominator();
72       DCHECK(block2 != nullptr);
73     }
74     dominator_ = block;
75     chain_length_ = chain_length;
76   }
77 
Get()78   HBasicBlock* Get() const {
79     return dominator_;
80   }
81 
82  private:
ChainLength(HBasicBlock * block)83   static size_t ChainLength(HBasicBlock* block) {
84     size_t result = 0;
85     while (block != nullptr) {
86       ++result;
87       block = block->GetDominator();
88     }
89     return result;
90   }
91 
92   HBasicBlock* dominator_;
93   size_t chain_length_;
94 };
95 
96 }  // namespace art
97 
98 #endif  // ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_
99