Optimizing: Rewrite search for common dominators.
Provide a utility class that can be used to quickly search
for common dominators of two or more blocks. Change the
algorithm to avoid memory allocations.
Change-Id: Id72c975fc42377cb7622902f87c4262ea7b3cc38
diff --git a/compiler/optimizing/common_dominator.h b/compiler/optimizing/common_dominator.h
new file mode 100644
index 0000000..b459d24
--- /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_