From 391d01f3e8dedf3af3727bdf5d5b76ab35d52795 Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Fri, 6 Nov 2015 11:02:08 +0000 Subject: 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 --- compiler/optimizing/nodes.cc | 24 +++++------------------- 1 file changed, 5 insertions(+), 19 deletions(-) (limited to 'compiler/optimizing/nodes.cc') diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 68fb0acf7f..cc549ff2ff 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); -- cgit v1.2.3-59-g8ed1b