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/nodes.cc b/compiler/optimizing/nodes.cc
index 68fb0ac..cc549ff 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 @@
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 @@
}
}
-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);