Implement irreducible loop support in optimizing.
So we don't fallback to the interpreter in the presence of
irreducible loops.
Implications:
- A loop pre-header does not necessarily dominate a loop header.
- Non-constant redundant phis will be kept in loop headers, to
satisfy our linear scan register allocation algorithm.
- while-graph optimizations, such as gvn, licm, lse, and dce
need to know when they are dealing with irreducible loops.
Change-Id: I2cea8934ce0b40162d215353497c7f77d6c9137e
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index c85e573..f5a7048 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -13,7 +13,6 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
#include "nodes.h"
#include "code_generator.h"
@@ -90,6 +89,7 @@
for (size_t i = 0; i < blocks_.size(); ++i) {
if (!visited.IsBitSet(i)) {
HBasicBlock* block = blocks_[i];
+ if (block == nullptr) continue;
DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
RemoveAsUser(it.Current());
@@ -102,6 +102,7 @@
for (size_t i = 0; i < blocks_.size(); ++i) {
if (!visited.IsBitSet(i)) {
HBasicBlock* block = blocks_[i];
+ if (block == nullptr) continue;
// We only need to update the successor, which might be live.
for (HBasicBlock* successor : block->GetSuccessors()) {
successor->RemovePredecessor(block);
@@ -113,7 +114,7 @@
}
}
-void HGraph::BuildDominatorTree() {
+GraphAnalysisResult HGraph::BuildDominatorTree() {
// (1) Simplify the CFG so that catch blocks have only exceptional incoming
// edges. This invariant simplifies building SSA form because Phis cannot
// collect both normal- and exceptional-flow values at the same time.
@@ -130,7 +131,7 @@
RemoveInstructionsAsUsersFromDeadBlocks(visited);
// (4) Remove blocks not visited during the initial DFS.
- // Step (4) requires dead blocks to be removed from the
+ // Step (5) requires dead blocks to be removed from the
// predecessors list of live blocks.
RemoveDeadBlocks(visited);
@@ -140,6 +141,20 @@
// (6) Compute the dominance information and the reverse post order.
ComputeDominanceInformation();
+
+ // (7) Analyze loops discover through back edge analysis, and
+ // set the loop information on each block.
+ GraphAnalysisResult result = AnalyzeLoops();
+ if (result != kAnalysisSuccess) {
+ return result;
+ }
+
+ // (8) Precompute per-block try membership before entering the SSA builder,
+ // which needs the information to build catch block phis from values of
+ // locals at throwing instructions inside try blocks.
+ ComputeTryBlockInformation();
+
+ return kAnalysisSuccess;
}
void HGraph::ClearDominanceInformation() {
@@ -149,6 +164,17 @@
reverse_post_order_.clear();
}
+void HGraph::ClearLoopInformation() {
+ SetHasIrreducibleLoops(false);
+ for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+ HBasicBlock* current = it.Current();
+ if (current->IsLoopHeader()) {
+ current->RemoveInstruction(current->GetLoopInformation()->GetSuspendCheck());
+ }
+ current->SetLoopInformation(nullptr);
+ }
+}
+
void HBasicBlock::ClearDominanceInformation() {
dominated_blocks_.clear();
dominator_ = nullptr;
@@ -190,31 +216,28 @@
// dominator of the block. We can then start visiting its successors.
if (++visits[successor->GetBlockId()] ==
successor->GetPredecessors().size() - successor->NumberOfBackEdges()) {
- successor->GetDominator()->AddDominatedBlock(successor);
reverse_post_order_.push_back(successor);
worklist.push_back(successor);
}
}
}
+
+ // Populate `dominated_blocks_` information after computing all dominators.
+ // The potential presence of irreducible loops require to do it after.
+ for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ if (!block->IsEntryBlock()) {
+ block->GetDominator()->AddDominatedBlock(block);
+ }
+ }
}
-BuildSsaResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
- BuildDominatorTree();
-
- // The SSA builder requires loops to all be natural. Specifically, the dead phi
- // elimination phase checks the consistency of the graph when doing a post-order
- // visit for eliminating dead phis: a dead phi can only have loop header phi
- // users remaining when being visited.
- BuildSsaResult result = AnalyzeNaturalLoops();
- if (result != kBuildSsaSuccess) {
+GraphAnalysisResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
+ GraphAnalysisResult result = BuildDominatorTree();
+ if (result != kAnalysisSuccess) {
return result;
}
- // Precompute per-block try membership before entering the SSA builder,
- // which needs the information to build catch block phis from values of
- // locals at throwing instructions inside try blocks.
- ComputeTryBlockInformation();
-
// Create the inexact Object reference type and store it in the HGraph.
ScopedObjectAccess soa(Thread::Current());
ClassLinker* linker = Runtime::Current()->GetClassLinker();
@@ -224,12 +247,12 @@
// Tranforms graph to SSA form.
result = SsaBuilder(this, handles).BuildSsa();
- if (result != kBuildSsaSuccess) {
+ if (result != kAnalysisSuccess) {
return result;
}
in_ssa_form_ = true;
- return kBuildSsaSuccess;
+ return kAnalysisSuccess;
}
HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
@@ -331,7 +354,7 @@
// can be invalidated. We remember the initial size to avoid iterating over the new blocks.
for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
HBasicBlock* catch_block = blocks_[block_id];
- if (!catch_block->IsCatchBlock()) {
+ if (catch_block == nullptr || !catch_block->IsCatchBlock()) {
continue;
}
@@ -438,7 +461,7 @@
}
}
-BuildSsaResult HGraph::AnalyzeNaturalLoops() const {
+GraphAnalysisResult HGraph::AnalyzeLoops() const {
// Order does not matter.
for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
@@ -446,16 +469,26 @@
if (block->IsCatchBlock()) {
// TODO: Dealing with exceptional back edges could be tricky because
// they only approximate the real control flow. Bail out for now.
- return kBuildSsaFailThrowCatchLoop;
+ return kAnalysisFailThrowCatchLoop;
}
- HLoopInformation* info = block->GetLoopInformation();
- if (!info->Populate()) {
- // Abort if the loop is non natural. We currently bailout in such cases.
- return kBuildSsaFailNonNaturalLoop;
- }
+ block->GetLoopInformation()->Populate();
}
}
- return kBuildSsaSuccess;
+ return kAnalysisSuccess;
+}
+
+void HLoopInformation::Dump(std::ostream& os) {
+ os << "header: " << header_->GetBlockId() << std::endl;
+ os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl;
+ for (HBasicBlock* block : back_edges_) {
+ os << "back edge: " << block->GetBlockId() << std::endl;
+ }
+ for (HBasicBlock* block : header_->GetPredecessors()) {
+ os << "predecessor: " << block->GetBlockId() << std::endl;
+ }
+ for (uint32_t idx : blocks_.Indexes()) {
+ os << " in loop: " << idx << std::endl;
+ }
}
void HGraph::InsertConstant(HConstant* constant) {
@@ -555,61 +588,65 @@
}
}
-bool HLoopInformation::Populate() {
+void HLoopInformation::PopulateIrreducibleRecursive(HBasicBlock* block) {
+ if (blocks_.IsBitSet(block->GetBlockId())) {
+ return;
+ }
+
+ if (block->IsLoopHeader()) {
+ // If we hit a loop header in an irreducible loop, we first check if the
+ // pre header of that loop belongs to the currently analyzed loop. If it does,
+ // then we visit the back edges.
+ // Note that we cannot use GetPreHeader, as the loop may have not been populated
+ // yet.
+ HBasicBlock* pre_header = block->GetPredecessors()[0];
+ PopulateIrreducibleRecursive(pre_header);
+ if (blocks_.IsBitSet(pre_header->GetBlockId())) {
+ blocks_.SetBit(block->GetBlockId());
+ block->SetInLoop(this);
+ HLoopInformation* info = block->GetLoopInformation();
+ for (HBasicBlock* back_edge : info->GetBackEdges()) {
+ PopulateIrreducibleRecursive(back_edge);
+ }
+ }
+ } else {
+ // Visit all predecessors. If one predecessor is part of the loop, this
+ // block is also part of this loop.
+ for (HBasicBlock* predecessor : block->GetPredecessors()) {
+ PopulateIrreducibleRecursive(predecessor);
+ if (blocks_.IsBitSet(predecessor->GetBlockId())) {
+ blocks_.SetBit(block->GetBlockId());
+ block->SetInLoop(this);
+ }
+ }
+ }
+}
+
+void HLoopInformation::Populate() {
DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
+ // Populate this loop: starting with the back edge, recursively add predecessors
+ // that are not already part of that loop. Set the header as part of the loop
+ // to end the recursion.
+ // This is a recursive implementation of the algorithm described in
+ // "Advanced Compiler Design & Implementation" (Muchnick) p192.
+ blocks_.SetBit(header_->GetBlockId());
+ header_->SetInLoop(this);
for (HBasicBlock* back_edge : GetBackEdges()) {
DCHECK(back_edge->GetDominator() != nullptr);
if (!header_->Dominates(back_edge)) {
- // This loop is not natural. Do not bother going further.
- return false;
+ irreducible_ = true;
+ header_->GetGraph()->SetHasIrreducibleLoops(true);
+ PopulateIrreducibleRecursive(back_edge);
+ } else {
+ PopulateRecursive(back_edge);
}
-
- // Populate this loop: starting with the back edge, recursively add predecessors
- // that are not already part of that loop. Set the header as part of the loop
- // to end the recursion.
- // This is a recursive implementation of the algorithm described in
- // "Advanced Compiler Design & Implementation" (Muchnick) p192.
- blocks_.SetBit(header_->GetBlockId());
- PopulateRecursive(back_edge);
- }
- return true;
-}
-
-void HLoopInformation::Update() {
- HGraph* graph = header_->GetGraph();
- for (uint32_t id : blocks_.Indexes()) {
- HBasicBlock* block = graph->GetBlocks()[id];
- // Reset loop information of non-header blocks inside the loop, except
- // members of inner nested loops because those should already have been
- // updated by their own LoopInformation.
- if (block->GetLoopInformation() == this && block != header_) {
- block->SetLoopInformation(nullptr);
- }
- }
- blocks_.ClearAllBits();
-
- if (back_edges_.empty()) {
- // The loop has been dismantled, delete its suspend check and remove info
- // from the header.
- DCHECK(HasSuspendCheck());
- header_->RemoveInstruction(suspend_check_);
- header_->SetLoopInformation(nullptr);
- header_ = nullptr;
- suspend_check_ = nullptr;
- } else {
- if (kIsDebugBuild) {
- for (HBasicBlock* back_edge : back_edges_) {
- DCHECK(header_->Dominates(back_edge));
- }
- }
- // This loop still has reachable back edges. Repopulate the list of blocks.
- bool populate_successful = Populate();
- DCHECK(populate_successful);
}
}
HBasicBlock* HLoopInformation::GetPreHeader() const {
- return header_->GetDominator();
+ HBasicBlock* block = header_->GetPredecessors()[0];
+ DCHECK(irreducible_ || (block == header_->GetDominator()));
+ return block;
}
bool HLoopInformation::Contains(const HBasicBlock& block) const {