From f5479ca675a54411d79458b82e6d6ae2bd99b832 Mon Sep 17 00:00:00 2001 From: titzer Date: Thu, 29 Jan 2015 01:46:24 -0800 Subject: [PATCH] [turbofan] Gracefully bail out if OSR encounters a loop too deeply nested. R=jarin@chromium.org BUG= Review URL: https://codereview.chromium.org/877553007 Cr-Commit-Position: refs/heads/master@{#26318} --- src/bailout-reason.h | 1 + src/compiler/osr.cc | 64 ++++++++++++++++++++++-------------- src/compiler/osr.h | 3 +- src/compiler/pipeline.cc | 13 ++++++-- test/mjsunit/compiler/osr-nested2.js | 24 ++++++++++++++ test/mjsunit/compiler/osr-nested3.js | 27 +++++++++++++++ 6 files changed, 103 insertions(+), 29 deletions(-) create mode 100644 test/mjsunit/compiler/osr-nested2.js create mode 100644 test/mjsunit/compiler/osr-nested3.js diff --git a/src/bailout-reason.h b/src/bailout-reason.h index 69f65be..d66dbc4 100644 --- a/src/bailout-reason.h +++ b/src/bailout-reason.h @@ -332,6 +332,7 @@ namespace internal { "Wrong address or value passed to RecordWrite") \ V(kShouldNotDirectlyEnterOsrFunction, \ "Should not directly enter OSR-compiled function") \ + V(kOsrCompileFailed, "OSR compilation failed") \ V(kYield, "Yield") diff --git a/src/compiler/osr.cc b/src/compiler/osr.cc index 3360a1a..6f30963 100644 --- a/src/compiler/osr.cc +++ b/src/compiler/osr.cc @@ -8,6 +8,7 @@ #include "src/compiler/frame.h" #include "src/compiler/graph.h" #include "src/compiler/js-graph.h" +#include "src/compiler/loop-analysis.h" #include "src/compiler/node.h" #include "src/compiler/node-marker.h" #include "src/compiler/osr.h" @@ -22,38 +23,51 @@ OsrHelper::OsrHelper(CompilationInfo* info) stack_slot_count_(info->scope()->num_stack_slots()) {} -void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common, +bool OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common, Zone* tmp_zone) { - NodeDeque queue(tmp_zone); Graph* graph = jsgraph->graph(); - NodeMarker marker(graph, 2); - queue.push_back(graph->end()); - marker.Set(graph->end(), true); - - while (!queue.empty()) { - Node* node = queue.front(); - queue.pop_front(); - - // Rewrite OSR-related nodes. - switch (node->opcode()) { - case IrOpcode::kOsrNormalEntry: - node->ReplaceUses(graph->NewNode(common->Dead())); - break; - case IrOpcode::kOsrLoopEntry: - node->ReplaceUses(graph->start()); - break; - default: - break; + Node* osr_normal_entry = nullptr; + Node* osr_loop_entry = nullptr; + Node* osr_loop = nullptr; + + for (Node* node : graph->start()->uses()) { + if (node->opcode() == IrOpcode::kOsrLoopEntry) { + osr_loop_entry = node; // found the OSR loop entry + } else if (node->opcode() == IrOpcode::kOsrNormalEntry) { + osr_normal_entry = node; } - for (Node* const input : node->inputs()) { - if (!marker.Get(input)) { - marker.Set(input, true); - queue.push_back(input); - } + } + + if (osr_loop_entry == nullptr) { + // No OSR entry found, do nothing. + CHECK_NE(nullptr, osr_normal_entry); + return true; + } + + for (Node* use : osr_loop_entry->uses()) { + if (use->opcode() == IrOpcode::kLoop) { + CHECK_EQ(nullptr, osr_loop); // should be only one OSR loop. + osr_loop = use; // found the OSR loop. } } + CHECK_NE(nullptr, osr_loop); // Should have found the OSR loop. + + // Analyze the graph to determine how deeply nested the OSR loop is. + LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone); + + LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop); + if (loop->depth() > 0) return false; // cannot OSR inner loops yet. + + // TODO(titzer): perform loop peeling or graph duplication. + + // Replace the normal entry with {Dead} and the loop entry with {Start} + // and run the control reducer to clean up the graph. + osr_normal_entry->ReplaceUses(graph->NewNode(common->Dead())); + osr_loop_entry->ReplaceUses(graph->start()); ControlReducer::ReduceGraph(tmp_zone, jsgraph, common); + + return true; } diff --git a/src/compiler/osr.h b/src/compiler/osr.h index 89773f0..549bb5f 100644 --- a/src/compiler/osr.h +++ b/src/compiler/osr.h @@ -99,7 +99,8 @@ class OsrHelper { // Deconstructs the artificial {OsrNormalEntry} and rewrites the graph so // that only the path corresponding to {OsrLoopEntry} remains. - void Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common, + // Return {false} if the OSR deconstruction failed somehow. + bool Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common, Zone* tmp_zone); // Prepares the frame w.r.t. OSR. diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index ef0144c..6e71215 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -414,7 +414,9 @@ struct OsrDeconstructionPhase { SourcePositionTable::Scope pos(data->source_positions(), SourcePosition::Unknown()); OsrHelper osr_helper(data->info()); - osr_helper.Deconstruct(data->jsgraph(), data->common(), temp_zone); + bool success = + osr_helper.Deconstruct(data->jsgraph(), data->common(), temp_zone); + if (!success) data->info()->RetryOptimization(kOsrCompileFailed); } }; @@ -774,8 +776,11 @@ void Pipeline::RunPrintAndVerify(const char* phase, bool untyped) { Handle Pipeline::GenerateCode() { - // TODO(turbofan): Make OSR work with inner loops and remove this bailout. - if (info()->is_osr() && !FLAG_turbo_osr) return Handle::null(); + if (info()->is_osr() && !FLAG_turbo_osr) { + // TODO(turbofan): remove this flag and always handle OSR + info()->RetryOptimization(kOsrCompileFailed); + return Handle::null(); + } // TODO(mstarzinger): This is just a temporary hack to make TurboFan work, // the correct solution is to restore the context register after invoking @@ -863,6 +868,7 @@ Handle Pipeline::GenerateCode() { if (info()->is_osr()) { Run(); + if (info()->bailout_reason() != kNoReason) return Handle::null(); RunPrintAndVerify("OSR deconstruction"); } @@ -880,6 +886,7 @@ Handle Pipeline::GenerateCode() { } else { if (info()->is_osr()) { Run(); + if (info()->bailout_reason() != kNoReason) return Handle::null(); RunPrintAndVerify("OSR deconstruction"); } } diff --git a/test/mjsunit/compiler/osr-nested2.js b/test/mjsunit/compiler/osr-nested2.js new file mode 100644 index 0000000..8fd12fd --- /dev/null +++ b/test/mjsunit/compiler/osr-nested2.js @@ -0,0 +1,24 @@ +// Copyright 2015 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Flags: --allow-natives-syntax --use-osr --turbo-osr + +function f() { + var sum = 0; + for (var i = 5; i < 6; i++) { + for (var j = 0; j < 1000000; j++) { + var x = i + 2; + var y = x + 5; + var z = y + 3; + sum += z; + } + if (true) break; + } + return sum; +} + + +assertEquals(15000000, f()); +assertEquals(15000000, f()); +assertEquals(15000000, f()); diff --git a/test/mjsunit/compiler/osr-nested3.js b/test/mjsunit/compiler/osr-nested3.js new file mode 100644 index 0000000..8ff4e98 --- /dev/null +++ b/test/mjsunit/compiler/osr-nested3.js @@ -0,0 +1,27 @@ +// Copyright 2015 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Flags: --allow-natives-syntax --use-osr --turbo-osr + +function f() { + var sum = 0; + for (var m = 99; m < 100; m++) { + for (var i = 5; i < 6; i++) { + for (var j = 0; j < 1000000; j++) { + var x = i + 2; + var y = x + 5; + var z = y + 3; + sum += z; + } + if (true) break; + } + if (true) break; + } + return sum; +} + + +assertEquals(15000000, f()); +assertEquals(15000000, f()); +assertEquals(15000000, f()); -- 2.7.4