From 0b4dfc231263fbe5016f5c2c9e2d2e2fa1c154a1 Mon Sep 17 00:00:00 2001 From: titzer Date: Tue, 7 Apr 2015 04:00:40 -0700 Subject: [PATCH] [turbofan] Rework handling of loop exits in loop peeling. This CL primarily makes the loop peeling algorithm more robust; it no longer damages the graph if the loops are improperly closed. R=bmeurer@chromium.org BUG= Review URL: https://codereview.chromium.org/1052753004 Cr-Commit-Position: refs/heads/master@{#27620} --- src/compiler/loop-analysis.cc | 4 - src/compiler/loop-analysis.h | 4 +- src/compiler/loop-peeling.cc | 116 +++++++++++------------ src/compiler/loop-peeling.h | 1 + test/unittests/compiler/loop-peeling-unittest.cc | 48 +++++++++- 5 files changed, 106 insertions(+), 67 deletions(-) diff --git a/src/compiler/loop-analysis.cc b/src/compiler/loop-analysis.cc index 17e4fd4..d52c7c7 100644 --- a/src/compiler/loop-analysis.cc +++ b/src/compiler/loop-analysis.cc @@ -18,10 +18,6 @@ namespace compiler { #define BIT(x) (1u << OFFSET(x)) #define INDEX(x) ((x) >> 5) -// TODO(titzer): don't assume entry edges have a particular index. -static const int kAssumedLoopEntryIndex = 0; // assume loops are entered here. - - // Temporary information for each node during marking. struct NodeInfo { Node* node; diff --git a/src/compiler/loop-analysis.h b/src/compiler/loop-analysis.h index 71f9461..77c2a95 100644 --- a/src/compiler/loop-analysis.h +++ b/src/compiler/loop-analysis.h @@ -14,6 +14,9 @@ namespace v8 { namespace internal { namespace compiler { +// TODO(titzer): don't assume entry edges have a particular index. +static const int kAssumedLoopEntryIndex = 0; // assume loops are entered here. + class LoopFinderImpl; typedef base::iterator_range NodeRange; @@ -140,7 +143,6 @@ class LoopTree : public ZoneObject { ZoneVector loop_nodes_; }; - class LoopFinder { public: // Build a loop tree for the entire graph. diff --git a/src/compiler/loop-peeling.cc b/src/compiler/loop-peeling.cc index 39f487f..8c980aa 100644 --- a/src/compiler/loop-peeling.cc +++ b/src/compiler/loop-peeling.cc @@ -161,22 +161,62 @@ Node* PeeledIteration::map(Node* node) { } +static void FindLoopExits(LoopTree* loop_tree, LoopTree::Loop* loop, + NodeVector& exits, NodeVector& rets) { + // Look for returns and if projections that are outside the loop but whose + // control input is inside the loop. + for (Node* node : loop_tree->LoopNodes(loop)) { + for (Node* use : node->uses()) { + if (!loop_tree->Contains(loop, use)) { + if (IrOpcode::IsIfProjectionOpcode(use->opcode())) { + // This is a branch from inside the loop to outside the loop. + exits.push_back(use); + } else if (use->opcode() == IrOpcode::kReturn && + loop_tree->Contains(loop, + NodeProperties::GetControlInput(use))) { + // This is a return from inside the loop. + rets.push_back(use); + } + } + } + } +} + + +bool LoopPeeler::CanPeel(LoopTree* loop_tree, LoopTree::Loop* loop) { + Zone zone; + NodeVector exits(&zone); + NodeVector rets(&zone); + FindLoopExits(loop_tree, loop, exits, rets); + return exits.size() <= 1u; +} + + PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common, LoopTree* loop_tree, LoopTree::Loop* loop, Zone* tmp_zone) { - PeeledIterationImpl* iter = new (tmp_zone) PeeledIterationImpl(tmp_zone); - Peeling peeling(graph, tmp_zone, loop->TotalSize() * 2 + 2, - &iter->node_pairs_); + //============================================================================ + // Find the loop exit region to determine if this loop can be peeled. + //============================================================================ + NodeVector exits(tmp_zone); + NodeVector rets(tmp_zone); + FindLoopExits(loop_tree, loop, exits, rets); + + if (exits.size() != 1) return nullptr; // not peelable currently. //============================================================================ // Construct the peeled iteration. //============================================================================ + PeeledIterationImpl* iter = new (tmp_zone) PeeledIterationImpl(tmp_zone); + size_t estimated_peeled_size = + 5 + (loop->TotalSize() + exits.size() + rets.size()) * 2; + Peeling peeling(graph, tmp_zone, estimated_peeled_size, &iter->node_pairs_); + Node* dead = graph->NewNode(common->Dead()); // Map the loop header nodes to their entry values. for (Node* node : loop_tree->HeaderNodes(loop)) { - // TODO(titzer): assuming loop entry at index 0. - peeling.Insert(node, node->InputAt(0)); + peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex)); } // Copy all the nodes of loop body for the peeled iteration. @@ -227,69 +267,23 @@ PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common, loop_node->ReplaceInput(0, new_entry); //============================================================================ - // Find the loop exit region. + // Duplicate the loop exit region and add a merge. //============================================================================ - NodeVector exits(tmp_zone); - Node* end = NULL; - for (Node* node : loop_tree->LoopNodes(loop)) { - for (Node* use : node->uses()) { - if (!loop_tree->Contains(loop, use)) { - if (node->opcode() == IrOpcode::kBranch && - (use->opcode() == IrOpcode::kIfTrue || - use->opcode() == IrOpcode::kIfFalse)) { - // This is a branch from inside the loop to outside the loop. - exits.push_back(use); - } - } - } - } - - if (exits.size() == 0) return iter; // no exits => NTL - if (exits.size() == 1) { - // Only one exit, so {end} is that exit. - end = exits[0]; - } else { - // {end} should be the common merge from the exits. - NodeVector rets(tmp_zone); - for (Node* exit : exits) { - Node* found = NULL; - for (Node* use : exit->uses()) { - if (use->opcode() == IrOpcode::kMerge) { - found = use; - if (end == NULL) { - end = found; - } else { - CHECK_EQ(end, found); // it should be unique! - } - } else if (use->opcode() == IrOpcode::kReturn) { - found = use; - rets.push_back(found); - } - } - // There should be a merge or a return for each exit. - CHECK(found); - } - // Return nodes, the end merge, and the phis associated with the end merge - // must be duplicated as well. - for (Node* node : rets) exits.push_back(node); - if (end != NULL) { - exits.push_back(end); - for (Node* use : end->uses()) { - if (NodeProperties::IsPhi(use)) exits.push_back(use); - } - } + // Currently we are limited to peeling loops with a single exit. The exit is + // the postdominator of the loop (ignoring returns). + Node* postdom = exits[0]; + for (Node* node : rets) exits.push_back(node); + for (Node* use : postdom->uses()) { + if (NodeProperties::IsPhi(use)) exits.push_back(use); } - //============================================================================ - // Duplicate the loop exit region and add a merge. - //============================================================================ NodeRange exit_range(&exits[0], &exits[0] + exits.size()); peeling.CopyNodes(graph, tmp_zone, dead, exit_range); - Node* merge = graph->NewNode(common->Merge(2), end, peeling.map(end)); - end->ReplaceUses(merge); - merge->ReplaceInput(0, end); // HULK SMASH!! + Node* merge = graph->NewNode(common->Merge(2), postdom, peeling.map(postdom)); + postdom->ReplaceUses(merge); + merge->ReplaceInput(0, postdom); // input 0 overwritten by above line. // Find and update all the edges into either the loop or exit region. for (int i = 0; i < 2; i++) { diff --git a/src/compiler/loop-peeling.h b/src/compiler/loop-peeling.h index 3cbca78..ea963b0 100644 --- a/src/compiler/loop-peeling.h +++ b/src/compiler/loop-peeling.h @@ -29,6 +29,7 @@ class CommonOperatorBuilder; // Implements loop peeling. class LoopPeeler { public: + static bool CanPeel(LoopTree* loop_tree, LoopTree::Loop* loop); static PeeledIteration* Peel(Graph* graph, CommonOperatorBuilder* common, LoopTree* loop_tree, LoopTree::Loop* loop, Zone* tmp_zone); diff --git a/test/unittests/compiler/loop-peeling-unittest.cc b/test/unittests/compiler/loop-peeling-unittest.cc index dd0c46c..61b527c 100644 --- a/test/unittests/compiler/loop-peeling-unittest.cc +++ b/test/unittests/compiler/loop-peeling-unittest.cc @@ -71,10 +71,13 @@ class LoopPeelingTest : public GraphTest { PeeledIteration* PeelOne() { LoopTree* loop_tree = GetLoopTree(); - return Peel(loop_tree, loop_tree->outer_loops()[0]); + LoopTree::Loop* loop = loop_tree->outer_loops()[0]; + EXPECT_TRUE(LoopPeeler::CanPeel(loop_tree, loop)); + return Peel(loop_tree, loop); } PeeledIteration* Peel(LoopTree* loop_tree, LoopTree::Loop* loop) { + EXPECT_TRUE(LoopPeeler::CanPeel(loop_tree, loop)); PeeledIteration* peeled = LoopPeeler::Peel(graph(), common(), loop_tree, loop, zone()); if (FLAG_trace_turbo_graph) { @@ -446,6 +449,49 @@ TEST_F(LoopPeelingTest, TwoBackedgeLoopWithCounter) { } +TEST_F(LoopPeelingTest, TwoExitLoop_nope) { + Node* p0 = Parameter(0); + Node* loop = graph()->NewNode(common()->Loop(2), start(), start()); + Branch b1 = NewBranch(p0, loop); + Branch b2 = NewBranch(p0, b1.if_true); + + loop->ReplaceInput(1, b2.if_true); + Node* merge = graph()->NewNode(common()->Merge(2), b1.if_false, b2.if_false); + InsertReturn(p0, start(), merge); + + { + LoopTree* loop_tree = GetLoopTree(); + LoopTree::Loop* loop = loop_tree->outer_loops()[0]; + EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop)); + } +} + + +const Operator kMockCall(IrOpcode::kCall, Operator::kNoProperties, "MockCall", + 0, 0, 1, 1, 0, 2); + + +TEST_F(LoopPeelingTest, TwoExitLoopWithCall_nope) { + Node* p0 = Parameter(0); + Node* loop = graph()->NewNode(common()->Loop(2), start(), start()); + Branch b1 = NewBranch(p0, loop); + + Node* call = graph()->NewNode(&kMockCall, b1.if_true); + Node* if_success = graph()->NewNode(common()->IfSuccess(), call); + Node* if_exception = graph()->NewNode(common()->IfException(), call); + + loop->ReplaceInput(1, if_success); + Node* merge = graph()->NewNode(common()->Merge(2), b1.if_false, if_exception); + InsertReturn(p0, start(), merge); + + { + LoopTree* loop_tree = GetLoopTree(); + LoopTree::Loop* loop = loop_tree->outer_loops()[0]; + EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop)); + } +} + + } // namespace compiler } // namespace internal } // namespace v8 -- 2.7.4