Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
FPIIM-449
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/src/compiler/osr.cc b/src/compiler/osr.cc
new file mode 100644
index 0000000..55431c2
--- /dev/null
+++ b/src/compiler/osr.cc
@@ -0,0 +1,337 @@
+// Copyright 2014 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.
+
+#include "src/ast/scopes.h"
+#include "src/compiler.h"
+#include "src/compiler/all-nodes.h"
+#include "src/compiler/common-operator.h"
+#include "src/compiler/common-operator-reducer.h"
+#include "src/compiler/dead-code-elimination.h"
+#include "src/compiler/frame.h"
+#include "src/compiler/graph.h"
+#include "src/compiler/graph-reducer.h"
+#include "src/compiler/graph-trimmer.h"
+#include "src/compiler/graph-visualizer.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"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+OsrHelper::OsrHelper(CompilationInfo* info)
+ : parameter_count_(info->scope()->num_parameters()),
+ stack_slot_count_(info->scope()->num_stack_slots() +
+ info->osr_expr_stack_height()) {}
+
+
+#ifdef DEBUG
+#define TRACE_COND (FLAG_trace_turbo_graph && FLAG_trace_osr)
+#else
+#define TRACE_COND false
+#endif
+
+#define TRACE(...) \
+ do { \
+ if (TRACE_COND) PrintF(__VA_ARGS__); \
+ } while (false)
+
+
+// Peel outer loops and rewire the graph so that control reduction can
+// produce a properly formed graph.
+static void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
+ Zone* tmp_zone, Node* dead,
+ LoopTree* loop_tree, LoopTree::Loop* osr_loop,
+ Node* osr_normal_entry, Node* osr_loop_entry) {
+ const size_t original_count = graph->NodeCount();
+ AllNodes all(tmp_zone, graph);
+ NodeVector tmp_inputs(tmp_zone);
+ Node* sentinel = graph->NewNode(dead->op());
+
+ // Make a copy of the graph for each outer loop.
+ ZoneVector<NodeVector*> copies(tmp_zone);
+ for (LoopTree::Loop* loop = osr_loop->parent(); loop; loop = loop->parent()) {
+ void* stuff = tmp_zone->New(sizeof(NodeVector));
+ NodeVector* mapping =
+ new (stuff) NodeVector(original_count, sentinel, tmp_zone);
+ copies.push_back(mapping);
+ TRACE("OsrDuplication #%zu, depth %zu, header #%d:%s\n", copies.size(),
+ loop->depth(), loop_tree->HeaderNode(loop)->id(),
+ loop_tree->HeaderNode(loop)->op()->mnemonic());
+
+ // Prepare the mapping for OSR values and the OSR loop entry.
+ mapping->at(osr_normal_entry->id()) = dead;
+ mapping->at(osr_loop_entry->id()) = dead;
+
+ // The outer loops are dead in this copy.
+ for (LoopTree::Loop* outer = loop->parent(); outer;
+ outer = outer->parent()) {
+ for (Node* node : loop_tree->HeaderNodes(outer)) {
+ mapping->at(node->id()) = dead;
+ TRACE(" ---- #%d:%s -> dead (header)\n", node->id(),
+ node->op()->mnemonic());
+ }
+ }
+
+ // Copy all nodes.
+ for (size_t i = 0; i < all.live.size(); i++) {
+ Node* orig = all.live[i];
+ Node* copy = mapping->at(orig->id());
+ if (copy != sentinel) {
+ // Mapping already exists.
+ continue;
+ }
+ if (orig->InputCount() == 0 || orig->opcode() == IrOpcode::kParameter ||
+ orig->opcode() == IrOpcode::kOsrValue) {
+ // No need to copy leaf nodes or parameters.
+ mapping->at(orig->id()) = orig;
+ continue;
+ }
+
+ // Copy the node.
+ tmp_inputs.clear();
+ for (Node* input : orig->inputs()) {
+ tmp_inputs.push_back(mapping->at(input->id()));
+ }
+ copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]);
+ if (NodeProperties::IsTyped(orig)) {
+ NodeProperties::SetType(copy, NodeProperties::GetType(orig));
+ }
+ mapping->at(orig->id()) = copy;
+ TRACE(" copy #%d:%s -> #%d\n", orig->id(), orig->op()->mnemonic(),
+ copy->id());
+ }
+
+ // Fix missing inputs.
+ for (Node* orig : all.live) {
+ Node* copy = mapping->at(orig->id());
+ for (int j = 0; j < copy->InputCount(); j++) {
+ if (copy->InputAt(j) == sentinel) {
+ copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id()));
+ }
+ }
+ }
+
+ // Construct the entry into this loop from previous copies.
+
+ // Gather the live loop header nodes, {loop_header} first.
+ Node* loop_header = loop_tree->HeaderNode(loop);
+ NodeVector header_nodes(tmp_zone);
+ header_nodes.reserve(loop->HeaderSize());
+ header_nodes.push_back(loop_header); // put the loop header first.
+ for (Node* node : loop_tree->HeaderNodes(loop)) {
+ if (node != loop_header && all.IsLive(node)) {
+ header_nodes.push_back(node);
+ }
+ }
+
+ // Gather backedges from the previous copies of the inner loops of {loop}.
+ NodeVectorVector backedges(tmp_zone);
+ TRACE("Gathering backedges...\n");
+ for (int i = 1; i < loop_header->InputCount(); i++) {
+ if (TRACE_COND) {
+ Node* control = loop_header->InputAt(i);
+ size_t incoming_depth = 0;
+ for (int j = 0; j < control->op()->ControlInputCount(); j++) {
+ Node* k = NodeProperties::GetControlInput(control, j);
+ incoming_depth =
+ std::max(incoming_depth, loop_tree->ContainingLoop(k)->depth());
+ }
+
+ TRACE(" edge @%d #%d:%s, incoming depth %zu\n", i, control->id(),
+ control->op()->mnemonic(), incoming_depth);
+ }
+
+ for (int pos = static_cast<int>(copies.size()) - 1; pos >= 0; pos--) {
+ backedges.push_back(NodeVector(tmp_zone));
+ backedges.back().reserve(header_nodes.size());
+
+ NodeVector* previous_map = pos > 0 ? copies[pos - 1] : nullptr;
+
+ for (Node* node : header_nodes) {
+ Node* input = node->InputAt(i);
+ if (previous_map) input = previous_map->at(input->id());
+ backedges.back().push_back(input);
+ TRACE(" node #%d:%s(@%d) = #%d:%s\n", node->id(),
+ node->op()->mnemonic(), i, input->id(),
+ input->op()->mnemonic());
+ }
+ }
+ }
+
+ int backedge_count = static_cast<int>(backedges.size());
+ if (backedge_count == 1) {
+ // Simple case of single backedge, therefore a single entry.
+ int index = 0;
+ for (Node* node : header_nodes) {
+ Node* copy = mapping->at(node->id());
+ Node* input = backedges[0][index];
+ copy->ReplaceInput(0, input);
+ TRACE(" header #%d:%s(0) => #%d:%s\n", copy->id(),
+ copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
+ index++;
+ }
+ } else {
+ // Complex case of multiple backedges from previous copies requires
+ // merging the backedges to create the entry into the loop header.
+ Node* merge = nullptr;
+ int index = 0;
+ for (Node* node : header_nodes) {
+ // Gather edge inputs into {tmp_inputs}.
+ tmp_inputs.clear();
+ for (int edge = 0; edge < backedge_count; edge++) {
+ tmp_inputs.push_back(backedges[edge][index]);
+ }
+ Node* copy = mapping->at(node->id());
+ Node* input;
+ if (node == loop_header) {
+ // Create the merge for the entry into the loop header.
+ input = merge = graph->NewNode(common->Merge(backedge_count),
+ backedge_count, &tmp_inputs[0]);
+ copy->ReplaceInput(0, merge);
+ } else {
+ // Create a phi that merges values at entry into the loop header.
+ DCHECK_NOT_NULL(merge);
+ DCHECK(IrOpcode::IsPhiOpcode(node->opcode()));
+ tmp_inputs.push_back(merge);
+ Node* phi = input = graph->NewNode(
+ common->ResizeMergeOrPhi(node->op(), backedge_count),
+ backedge_count + 1, &tmp_inputs[0]);
+ copy->ReplaceInput(0, phi);
+ }
+
+ // Print the merge.
+ if (TRACE_COND) {
+ TRACE(" header #%d:%s(0) => #%d:%s(", copy->id(),
+ copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
+ for (size_t i = 0; i < tmp_inputs.size(); i++) {
+ if (i > 0) TRACE(", ");
+ Node* input = tmp_inputs[i];
+ TRACE("#%d:%s", input->id(), input->op()->mnemonic());
+ }
+ TRACE(")\n");
+ }
+
+ index++;
+ }
+ }
+ }
+
+ // Kill the outer loops in the original graph.
+ TRACE("Killing outer loop headers...\n");
+ for (LoopTree::Loop* outer = osr_loop->parent(); outer;
+ outer = outer->parent()) {
+ Node* loop_header = loop_tree->HeaderNode(outer);
+ loop_header->ReplaceUses(dead);
+ TRACE(" ---- #%d:%s\n", loop_header->id(), loop_header->op()->mnemonic());
+ }
+
+ // Merge the ends of the graph copies.
+ Node* const end = graph->end();
+ int const input_count = end->InputCount();
+ for (int i = 0; i < input_count; ++i) {
+ NodeId const id = end->InputAt(i)->id();
+ for (NodeVector* const copy : copies) {
+ end->AppendInput(graph->zone(), copy->at(id));
+ NodeProperties::ChangeOp(end, common->End(end->InputCount()));
+ }
+ }
+
+ if (FLAG_trace_turbo_graph) { // Simple textual RPO.
+ OFStream os(stdout);
+ os << "-- Graph after OSR duplication -- " << std::endl;
+ os << AsRPO(*graph);
+ }
+}
+
+
+void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common,
+ Zone* tmp_zone) {
+ Graph* graph = jsgraph->graph();
+ 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;
+ }
+ }
+
+ if (osr_loop_entry == nullptr) {
+ // No OSR entry found, do nothing.
+ CHECK(osr_normal_entry);
+ return;
+ }
+
+ for (Node* use : osr_loop_entry->uses()) {
+ if (use->opcode() == IrOpcode::kLoop) {
+ CHECK(!osr_loop); // should be only one OSR loop.
+ osr_loop = use; // found the OSR loop.
+ }
+ }
+
+ CHECK(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);
+
+ Node* dead = jsgraph->Dead();
+ LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop);
+ if (loop->depth() > 0) {
+ PeelOuterLoopsForOsr(graph, common, tmp_zone, dead, loop_tree, loop,
+ osr_normal_entry, osr_loop_entry);
+ }
+
+ // 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(dead);
+ osr_normal_entry->Kill();
+ osr_loop_entry->ReplaceUses(graph->start());
+ osr_loop_entry->Kill();
+
+ // Remove the first input to the {osr_loop}.
+ int const live_input_count = osr_loop->InputCount() - 1;
+ CHECK_NE(0, live_input_count);
+ for (Node* const use : osr_loop->uses()) {
+ if (NodeProperties::IsPhi(use)) {
+ use->RemoveInput(0);
+ NodeProperties::ChangeOp(
+ use, common->ResizeMergeOrPhi(use->op(), live_input_count));
+ }
+ }
+ osr_loop->RemoveInput(0);
+ NodeProperties::ChangeOp(
+ osr_loop, common->ResizeMergeOrPhi(osr_loop->op(), live_input_count));
+
+ // Run control reduction and graph trimming.
+ // TODO(bmeurer): The OSR deconstruction could be a regular reducer and play
+ // nice together with the rest, instead of having this custom stuff here.
+ GraphReducer graph_reducer(tmp_zone, graph);
+ DeadCodeElimination dce(&graph_reducer, graph, common);
+ CommonOperatorReducer cor(&graph_reducer, graph, common, jsgraph->machine());
+ graph_reducer.AddReducer(&dce);
+ graph_reducer.AddReducer(&cor);
+ graph_reducer.ReduceGraph();
+ GraphTrimmer trimmer(tmp_zone, graph);
+ NodeVector roots(tmp_zone);
+ jsgraph->GetCachedNodes(&roots);
+ trimmer.TrimGraph(roots.begin(), roots.end());
+}
+
+
+void OsrHelper::SetupFrame(Frame* frame) {
+ // The optimized frame will subsume the unoptimized frame. Do so by reserving
+ // the first spill slots.
+ frame->ReserveSpillSlots(UnoptimizedFrameSlots());
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8