Home | History | Annotate | Download | only in optimizing 
      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.
     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.
     37   explicit CommonDominator(HBasicBlock* block)
     38       : dominator_(block), chain_length_(ChainLength(block)) {
     39   }
     40 
     41   // Update the common dominator with another 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 
     77   HBasicBlock* Get() const {
     78     return dominator_;
     79   }
     80 
     81  private:
     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