Merge "Optimizing: Rewrite search for common dominators."

3 files changed, 98 insertions, 21 deletions

diff --git a/compiler/optimizing/common_dominator.h b/compiler/optimizing/common_dominator.h
new file mode 100644
index 0000000000..b459d24d7c
--- /dev/null
+++ b/compiler/optimizing/common_dominator.h
@@ -0,0 +1,93 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_
+#define ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_
+
+#include "nodes.h"
+
+namespace art {
+
+// Helper class for finding common dominators of two or more blocks in a graph.
+// The domination information of a graph must not be modified while there is
+// a CommonDominator object as it's internal state could become invalid.
+class CommonDominator {
+ public:
+  // Convenience function to find the common dominator of 2 blocks.
+  static HBasicBlock* ForPair(HBasicBlock* block1, HBasicBlock* block2) {
+    CommonDominator finder(block1);
+    finder.Update(block2);
+    return finder.Get();
+  }
+
+  // Create a finder starting with a given block.
+  explicit CommonDominator(HBasicBlock* block)
+      : dominator_(block), chain_length_(ChainLength(block)) {
+    DCHECK(block != nullptr);
+  }
+
+  // Update the common dominator with another block.
+  void Update(HBasicBlock* block) {
+    DCHECK(block != nullptr);
+    HBasicBlock* block2 = dominator_;
+    DCHECK(block2 != nullptr);
+    if (block == block2) {
+      return;
+    }
+    size_t chain_length = ChainLength(block);
+    size_t chain_length2 = chain_length_;
+    // Equalize the chain lengths
+    for ( ; chain_length > chain_length2; --chain_length) {
+      block = block->GetDominator();
+      DCHECK(block != nullptr);
+    }
+    for ( ; chain_length2 > chain_length; --chain_length2) {
+      block2 = block2->GetDominator();
+      DCHECK(block2 != nullptr);
+    }
+    // Now run up the chain until we hit the common dominator.
+    while (block != block2) {
+      --chain_length;
+      block = block->GetDominator();
+      DCHECK(block != nullptr);
+      block2 = block2->GetDominator();
+      DCHECK(block2 != nullptr);
+    }
+    dominator_ = block;
+    chain_length_ = chain_length;
+  }
+
+  HBasicBlock* Get() const {
+    return dominator_;
+  }
+
+ private:
+  static size_t ChainLength(HBasicBlock* block) {
+    size_t result = 0;
+    while (block != nullptr) {
+      ++result;
+      block = block->GetDominator();
+    }
+    return result;
+  }
+
+  HBasicBlock* dominator_;
+  size_t chain_length_;
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_OPTIMIZING_COMMON_DOMINATOR_H_
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 7a8b463d13..de3f2668b6 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -17,6 +17,7 @@
 #include "nodes.h"
 
 #include "code_generator.h"
+#include "common_dominator.h"
 #include "ssa_builder.h"
 #include "base/bit_vector-inl.h"
 #include "base/bit_utils.h"
@@ -179,7 +180,10 @@ void HGraph::ComputeDominanceInformation() {
       if (successor->GetDominator() == nullptr) {
         successor->SetDominator(current);
       } else {
-        successor->SetDominator(FindCommonDominator(successor->GetDominator(), current));
+        // The CommonDominator can work for multiple blocks as long as the
+        // domination information doesn't change. However, since we're changing
+        // that information here, we can use the finder only for pairs of blocks.
+        successor->SetDominator(CommonDominator::ForPair(successor->GetDominator(), current));
       }
 
       // Once all the forward edges have been visited, we know the immediate
@@ -194,24 +198,6 @@ void HGraph::ComputeDominanceInformation() {
   }
 }
 
-HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const {
-  ArenaBitVector visited(arena_, blocks_.size(), false);
-  // Walk the dominator tree of the first block and mark the visited blocks.
-  while (first != nullptr) {
-    visited.SetBit(first->GetBlockId());
-    first = first->GetDominator();
-  }
-  // Walk the dominator tree of the second block until a marked block is found.
-  while (second != nullptr) {
-    if (visited.IsBitSet(second->GetBlockId())) {
-      return second;
-    }
-    second = second->GetDominator();
-  }
-  LOG(ERROR) << "Could not find common dominator";
-  return nullptr;
-}
-
 void HGraph::TransformToSsa() {
   DCHECK(!reverse_post_order_.empty());
   SsaBuilder ssa_builder(this);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 4e8124894a..ab53e63300 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -350,8 +350,6 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
 
   HCurrentMethod* GetCurrentMethod();
 
-  HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
-
   const DexFile& GetDexFile() const {
     return dex_file_;
   }