Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(144)

Unified Diff: src/compiler/loop-peeling.cc

Issue 1052753004: [turbofan] Rework handling of loop exits in loop peeling. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/loop-peeling.h ('k') | test/unittests/compiler/loop-peeling-unittest.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/loop-peeling.cc
diff --git a/src/compiler/loop-peeling.cc b/src/compiler/loop-peeling.cc
index 39f487f85461e2dee18dc8a5b58f2d0eb7fd3ac1..8c980aa125e58ec1badefac9f224f35268106b2f 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++) {
« no previous file with comments | « src/compiler/loop-peeling.h ('k') | test/unittests/compiler/loop-peeling-unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698