LCOV - code coverage report
Current view: top level - src/compiler - osr.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 130 133 97.7 %
Date: 2017-04-26 Functions: 5 5 100.0 %

          Line data    Source code
       1             : // Copyright 2014 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/compiler/osr.h"
       6             : #include "src/ast/scopes.h"
       7             : #include "src/compilation-info.h"
       8             : #include "src/compiler/all-nodes.h"
       9             : #include "src/compiler/common-operator-reducer.h"
      10             : #include "src/compiler/common-operator.h"
      11             : #include "src/compiler/dead-code-elimination.h"
      12             : #include "src/compiler/frame.h"
      13             : #include "src/compiler/graph-reducer.h"
      14             : #include "src/compiler/graph-trimmer.h"
      15             : #include "src/compiler/graph-visualizer.h"
      16             : #include "src/compiler/graph.h"
      17             : #include "src/compiler/js-graph.h"
      18             : #include "src/compiler/loop-analysis.h"
      19             : #include "src/compiler/node-marker.h"
      20             : #include "src/compiler/node.h"
      21             : #include "src/objects-inl.h"
      22             : 
      23             : namespace v8 {
      24             : namespace internal {
      25             : namespace compiler {
      26             : 
      27       17643 : OsrHelper::OsrHelper(CompilationInfo* info)
      28             :     : parameter_count_(
      29             :           info->is_optimizing_from_bytecode()
      30       51909 :               ? info->shared_info()->bytecode_array()->parameter_count()
      31         204 :               : info->scope()->num_parameters()),
      32             :       stack_slot_count_(
      33             :           info->is_optimizing_from_bytecode()
      34       69144 :               ? info->shared_info()->bytecode_array()->register_count() +
      35             :                     InterpreterFrameConstants::kExtraSlotCount
      36         408 :               : info->scope()->num_stack_slots() +
      37       87603 :                     info->osr_expr_stack_height()) {}
      38             : 
      39             : #ifdef DEBUG
      40             : #define TRACE_COND (FLAG_trace_turbo_graph && FLAG_trace_osr)
      41             : #else
      42             : #define TRACE_COND false
      43             : #endif
      44             : 
      45             : #define TRACE(...)                       \
      46             :   do {                                   \
      47             :     if (TRACE_COND) PrintF(__VA_ARGS__); \
      48             :   } while (false)
      49             : 
      50             : namespace {
      51             : 
      52             : // Peel outer loops and rewire the graph so that control reduction can
      53             : // produce a properly formed graph.
      54        9889 : void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
      55         920 :                           Zone* tmp_zone, Node* dead, LoopTree* loop_tree,
      56        3166 :                           LoopTree::Loop* osr_loop, Node* osr_normal_entry,
      57        1326 :                           Node* osr_loop_entry) {
      58             :   const size_t original_count = graph->NodeCount();
      59         920 :   AllNodes all(tmp_zone, graph);
      60             :   NodeVector tmp_inputs(tmp_zone);
      61             :   Node* sentinel = graph->NewNode(dead->op());
      62             : 
      63             :   // Make a copy of the graph for each outer loop.
      64             :   ZoneVector<NodeVector*> copies(tmp_zone);
      65        6224 :   for (LoopTree::Loop* loop = osr_loop->parent(); loop; loop = loop->parent()) {
      66        1326 :     void* stuff = tmp_zone->New(sizeof(NodeVector));
      67             :     NodeVector* mapping =
      68        2652 :         new (stuff) NodeVector(original_count, sentinel, tmp_zone);
      69        1326 :     copies.push_back(mapping);
      70             :     TRACE("OsrDuplication #%zu, depth %zu, header #%d:%s\n", copies.size(),
      71             :           loop->depth(), loop_tree->HeaderNode(loop)->id(),
      72             :           loop_tree->HeaderNode(loop)->op()->mnemonic());
      73             : 
      74             :     // Prepare the mapping for OSR values and the OSR loop entry.
      75        2652 :     mapping->at(osr_normal_entry->id()) = dead;
      76        2652 :     mapping->at(osr_loop_entry->id()) = dead;
      77             : 
      78             :     // The outer loops are dead in this copy.
      79        1756 :     for (LoopTree::Loop* outer = loop->parent(); outer;
      80             :          outer = outer->parent()) {
      81        3418 :       for (Node* node : loop_tree->HeaderNodes(outer)) {
      82        5976 :         mapping->at(node->id()) = dead;
      83             :         TRACE(" ---- #%d:%s -> dead (header)\n", node->id(),
      84             :               node->op()->mnemonic());
      85             :       }
      86             :     }
      87             : 
      88             :     // Copy all nodes.
      89      691356 :     for (size_t i = 0; i < all.reachable.size(); i++) {
      90     1254483 :       Node* orig = all.reachable[i];
      91      690030 :       Node* copy = mapping->at(orig->id());
      92      345015 :       if (copy != sentinel) {
      93             :         // Mapping already exists.
      94             :         continue;
      95             :       }
      96      662823 :       if (orig->InputCount() == 0 || orig->opcode() == IrOpcode::kParameter ||
      97      645250 :           orig->opcode() == IrOpcode::kOsrValue ||
      98             :           orig->opcode() == IrOpcode::kOsrGuard) {
      99             :         // No need to copy leaf nodes or parameters.
     100       46365 :         mapping->at(orig->id()) = orig;
     101       46365 :         continue;
     102             :       }
     103             : 
     104             :       // Copy the node.
     105             :       tmp_inputs.clear();
     106     2214240 :       for (Node* input : orig->inputs()) {
     107     1921230 :         tmp_inputs.push_back(mapping->at(input->id()));
     108             :       }
     109      586020 :       copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]);
     110      586020 :       mapping->at(orig->id()) = copy;
     111             :       TRACE(" copy #%d:%s -> #%d\n", orig->id(), orig->op()->mnemonic(),
     112             :             copy->id());
     113             :     }
     114             : 
     115             :     // Fix missing inputs.
     116      691356 :     for (Node* orig : all.reachable) {
     117      690030 :       Node* copy = mapping->at(orig->id());
     118     2723596 :       for (int j = 0; j < copy->InputCount(); j++) {
     119     1016783 :         if (copy->InputAt(j) == sentinel) {
     120     1339866 :           copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id()));
     121             :         }
     122             :       }
     123             :     }
     124             : 
     125             :     // Construct the entry into this loop from previous copies.
     126             : 
     127             :     // Gather the live loop header nodes, {loop_header} first.
     128        1326 :     Node* loop_header = loop_tree->HeaderNode(loop);
     129             :     NodeVector header_nodes(tmp_zone);
     130        1326 :     header_nodes.reserve(loop->HeaderSize());
     131        1326 :     header_nodes.push_back(loop_header);  // put the loop header first.
     132       11214 :     for (Node* node : loop_tree->HeaderNodes(loop)) {
     133        9888 :       if (node != loop_header && all.IsLive(node)) {
     134        8562 :         header_nodes.push_back(node);
     135             :       }
     136             :     }
     137             : 
     138             :     // Gather backedges from the previous copies of the inner loops of {loop}.
     139             :     NodeVectorVector backedges(tmp_zone);
     140             :     TRACE("Gathering backedges...\n");
     141        5304 :     for (int i = 1; i < loop_header->InputCount(); i++) {
     142             :       if (TRACE_COND) {
     143             :         Node* control = loop_header->InputAt(i);
     144             :         size_t incoming_depth = 0;
     145             :         for (int j = 0; j < control->op()->ControlInputCount(); j++) {
     146             :           Node* k = NodeProperties::GetControlInput(control, j);
     147             :           incoming_depth =
     148             :               std::max(incoming_depth, loop_tree->ContainingLoop(k)->depth());
     149             :         }
     150             : 
     151             :         TRACE(" edge @%d #%d:%s, incoming depth %zu\n", i, control->id(),
     152             :               control->op()->mnemonic(), incoming_depth);
     153             :       }
     154             : 
     155        4408 :       for (int pos = static_cast<int>(copies.size()) - 1; pos >= 0; pos--) {
     156        1756 :         backedges.push_back(NodeVector(tmp_zone));
     157        3512 :         backedges.back().reserve(header_nodes.size());
     158             : 
     159        2186 :         NodeVector* previous_map = pos > 0 ? copies[pos - 1] : nullptr;
     160             : 
     161       16388 :         for (Node* node : header_nodes) {
     162       12876 :           Node* input = node->InputAt(i);
     163       18852 :           if (previous_map) input = previous_map->at(input->id());
     164       12876 :           backedges.back().push_back(input);
     165             :           TRACE("   node #%d:%s(@%d) = #%d:%s\n", node->id(),
     166             :                 node->op()->mnemonic(), i, input->id(),
     167             :                 input->op()->mnemonic());
     168             :         }
     169             :       }
     170             :     }
     171             : 
     172        2652 :     int backedge_count = static_cast<int>(backedges.size());
     173        1326 :     if (backedge_count == 1) {
     174             :       // Simple case of single backedge, therefore a single entry.
     175             :       int index = 0;
     176        8884 :       for (Node* node : header_nodes) {
     177       14088 :         Node* copy = mapping->at(node->id());
     178       14088 :         Node* input = backedges[0][index];
     179        7044 :         copy->ReplaceInput(0, input);
     180             :         TRACE(" header #%d:%s(0) => #%d:%s\n", copy->id(),
     181             :               copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
     182        7044 :         index++;
     183             :       }
     184             :     } else {
     185             :       // Complex case of multiple backedges from previous copies requires
     186             :       // merging the backedges to create the entry into the loop header.
     187         406 :       Node* merge = nullptr;
     188             :       int index = 0;
     189        8938 :       for (Node* node : header_nodes) {
     190             :         // Gather edge inputs into {tmp_inputs}.
     191             :         tmp_inputs.clear();
     192        8676 :         for (int edge = 0; edge < backedge_count; edge++) {
     193       17496 :           tmp_inputs.push_back(backedges[edge][index]);
     194             :         }
     195        5688 :         Node* copy = mapping->at(node->id());
     196             :         Node* input;
     197        2844 :         if (node == loop_header) {
     198             :           // Create the merge for the entry into the loop header.
     199             :           input = merge = graph->NewNode(common->Merge(backedge_count),
     200         406 :                                          backedge_count, &tmp_inputs[0]);
     201         406 :           copy->ReplaceInput(0, merge);
     202             :         } else {
     203             :           // Create a phi that merges values at entry into the loop header.
     204             :           DCHECK_NOT_NULL(merge);
     205             :           DCHECK(IrOpcode::IsPhiOpcode(node->opcode()));
     206        2438 :           tmp_inputs.push_back(merge);
     207             :           Node* phi = input = graph->NewNode(
     208             :               common->ResizeMergeOrPhi(node->op(), backedge_count),
     209        4876 :               backedge_count + 1, &tmp_inputs[0]);
     210        2438 :           copy->ReplaceInput(0, phi);
     211             :         }
     212             : 
     213             :         // Print the merge.
     214             :         if (TRACE_COND) {
     215             :           TRACE(" header #%d:%s(0) => #%d:%s(", copy->id(),
     216             :                 copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
     217             :           for (size_t i = 0; i < tmp_inputs.size(); i++) {
     218             :             if (i > 0) TRACE(", ");
     219             :             Node* input = tmp_inputs[i];
     220             :             TRACE("#%d:%s", input->id(), input->op()->mnemonic());
     221             :           }
     222             :           TRACE(")\n");
     223             :         }
     224             : 
     225        2844 :         index++;
     226             :       }
     227             :     }
     228             :   }
     229             : 
     230             :   // Kill the outer loops in the original graph.
     231             :   TRACE("Killing outer loop headers...\n");
     232        2246 :   for (LoopTree::Loop* outer = osr_loop->parent(); outer;
     233             :        outer = outer->parent()) {
     234        1326 :     Node* loop_header = loop_tree->HeaderNode(outer);
     235        1326 :     loop_header->ReplaceUses(dead);
     236             :     TRACE(" ---- #%d:%s\n", loop_header->id(), loop_header->op()->mnemonic());
     237             :   }
     238             : 
     239             :   // Merge the ends of the graph copies.
     240             :   Node* const end = graph->end();
     241             :   int const input_count = end->InputCount();
     242        6026 :   for (int i = 0; i < input_count; ++i) {
     243        5106 :     NodeId const id = end->InputAt(i)->id();
     244       18261 :     for (NodeVector* const copy : copies) {
     245       24147 :       end->AppendInput(graph->zone(), copy->at(id));
     246        8049 :       NodeProperties::ChangeOp(end, common->End(end->InputCount()));
     247             :     }
     248             :   }
     249             : 
     250         920 :   if (FLAG_trace_turbo_graph) {  // Simple textual RPO.
     251           0 :     OFStream os(stdout);
     252           0 :     os << "-- Graph after OSR duplication -- " << std::endl;
     253           0 :     os << AsRPO(*graph);
     254             :   }
     255         920 : }
     256             : 
     257       54757 : void SetTypeForOsrValue(Node* osr_value, Node* loop,
     258             :                         CommonOperatorBuilder* common) {
     259             :   Node* osr_guard = nullptr;
     260      109514 :   for (Node* use : osr_value->uses()) {
     261       54757 :     if (use->opcode() == IrOpcode::kOsrGuard) {
     262             :       DCHECK_EQ(use->InputAt(0), osr_value);
     263             :       osr_guard = use;
     264             :       break;
     265             :     }
     266             :   }
     267             : 
     268       54757 :   NodeProperties::ChangeOp(osr_guard, common->OsrGuard(OsrGuardType::kAny));
     269       54757 : }
     270             : 
     271             : }  // namespace
     272             : 
     273       11626 : void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common,
     274             :                             Zone* tmp_zone) {
     275       11626 :   Graph* graph = jsgraph->graph();
     276             :   Node* osr_normal_entry = nullptr;
     277             :   Node* osr_loop_entry = nullptr;
     278        5813 :   Node* osr_loop = nullptr;
     279             : 
     280      435731 :   for (Node* node : graph->start()->uses()) {
     281      214959 :     if (node->opcode() == IrOpcode::kOsrLoopEntry) {
     282             :       osr_loop_entry = node;  // found the OSR loop entry
     283      203333 :     } else if (node->opcode() == IrOpcode::kOsrNormalEntry) {
     284             :       osr_normal_entry = node;
     285             :     }
     286             :   }
     287             : 
     288        5813 :   CHECK_NOT_NULL(osr_normal_entry);  // Should have found the OSR normal entry.
     289        5813 :   CHECK_NOT_NULL(osr_loop_entry);    // Should have found the OSR loop entry.
     290             : 
     291      259719 :   for (Node* use : osr_loop_entry->uses()) {
     292      126953 :     if (use->opcode() == IrOpcode::kLoop) {
     293        5813 :       CHECK(!osr_loop);             // should be only one OSR loop.
     294             :       osr_loop = use;               // found the OSR loop.
     295             :     }
     296             :   }
     297             : 
     298        5813 :   CHECK(osr_loop);  // Should have found the OSR loop.
     299             : 
     300      314476 :   for (Node* use : osr_loop_entry->uses()) {
     301      126953 :     if (use->opcode() == IrOpcode::kOsrValue) {
     302       54757 :       SetTypeForOsrValue(use, osr_loop, common);
     303             :     }
     304             :   }
     305             : 
     306             :   // Analyze the graph to determine how deeply nested the OSR loop is.
     307        5813 :   LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone);
     308             : 
     309        5813 :   Node* dead = jsgraph->Dead();
     310        5813 :   LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop);
     311        5813 :   if (loop->depth() > 0) {
     312             :     PeelOuterLoopsForOsr(graph, common, tmp_zone, dead, loop_tree, loop,
     313         920 :                          osr_normal_entry, osr_loop_entry);
     314             :   }
     315             : 
     316             :   // Replace the normal entry with {Dead} and the loop entry with {Start}
     317             :   // and run the control reducer to clean up the graph.
     318        5813 :   osr_normal_entry->ReplaceUses(dead);
     319        5813 :   osr_normal_entry->Kill();
     320        5813 :   osr_loop_entry->ReplaceUses(graph->start());
     321        5813 :   osr_loop_entry->Kill();
     322             : 
     323             :   // Remove the first input to the {osr_loop}.
     324        5813 :   int const live_input_count = osr_loop->InputCount() - 1;
     325        5813 :   CHECK_NE(0, live_input_count);
     326      102869 :   for (Node* const use : osr_loop->uses()) {
     327       63176 :     if (NodeProperties::IsPhi(use)) {
     328       33880 :       use->RemoveInput(0);
     329             :       NodeProperties::ChangeOp(
     330       33880 :           use, common->ResizeMergeOrPhi(use->op(), live_input_count));
     331             :     }
     332             :   }
     333        5813 :   osr_loop->RemoveInput(0);
     334             :   NodeProperties::ChangeOp(
     335        5813 :       osr_loop, common->ResizeMergeOrPhi(osr_loop->op(), live_input_count));
     336             : 
     337             :   // Run control reduction and graph trimming.
     338             :   // TODO(bmeurer): The OSR deconstruction could be a regular reducer and play
     339             :   // nice together with the rest, instead of having this custom stuff here.
     340        5813 :   GraphReducer graph_reducer(tmp_zone, graph);
     341        5813 :   DeadCodeElimination dce(&graph_reducer, graph, common);
     342        5813 :   CommonOperatorReducer cor(&graph_reducer, graph, common, jsgraph->machine());
     343        5813 :   graph_reducer.AddReducer(&dce);
     344        5813 :   graph_reducer.AddReducer(&cor);
     345        5813 :   graph_reducer.ReduceGraph();
     346       11626 :   GraphTrimmer trimmer(tmp_zone, graph);
     347             :   NodeVector roots(tmp_zone);
     348        5813 :   jsgraph->GetCachedNodes(&roots);
     349       11626 :   trimmer.TrimGraph(roots.begin(), roots.end());
     350        5813 : }
     351             : 
     352             : 
     353        5813 : void OsrHelper::SetupFrame(Frame* frame) {
     354             :   // The optimized frame will subsume the unoptimized frame. Do so by reserving
     355             :   // the first spill slots.
     356             :   frame->ReserveSpillSlots(UnoptimizedFrameSlots());
     357        5813 : }
     358             : 
     359             : }  // namespace compiler
     360             : }  // namespace internal
     361             : }  // namespace v8

Generated by: LCOV version 1.10