Home | History | Annotate | Download | only in compiler 
      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 OsrHelper::OsrHelper(CompilationInfo* info)
     28     : parameter_count_(
     29           info->is_optimizing_from_bytecode()
     30               ? info->shared_info()->bytecode_array()->parameter_count()
     31               : info->scope()->num_parameters()),
     32       stack_slot_count_(
     33           info->is_optimizing_from_bytecode()
     34               ? info->shared_info()->bytecode_array()->register_count() +
     35                     InterpreterFrameConstants::kExtraSlotCount
     36               : info->scope()->num_stack_slots() +
     37                     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 void PeelOuterLoopsForOsr(Graph* graph, CommonOperatorBuilder* common,
     55                           Zone* tmp_zone, Node* dead, LoopTree* loop_tree,
     56                           LoopTree::Loop* osr_loop, Node* osr_normal_entry,
     57                           Node* osr_loop_entry) {
     58   const size_t original_count = graph->NodeCount();
     59   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   for (LoopTree::Loop* loop = osr_loop->parent(); loop; loop = loop->parent()) {
     66     void* stuff = tmp_zone->New(sizeof(NodeVector));
     67     NodeVector* mapping =
     68         new (stuff) NodeVector(original_count, sentinel, tmp_zone);
     69     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     mapping->at(osr_normal_entry->id()) = dead;
     76     mapping->at(osr_loop_entry->id()) = dead;
     77 
     78     // The outer loops are dead in this copy.
     79     for (LoopTree::Loop* outer = loop->parent(); outer;
     80          outer = outer->parent()) {
     81       for (Node* node : loop_tree->HeaderNodes(outer)) {
     82         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     for (size_t i = 0; i < all.reachable.size(); i++) {
     90       Node* orig = all.reachable[i];
     91       Node* copy = mapping->at(orig->id());
     92       if (copy != sentinel) {
     93         // Mapping already exists.
     94         continue;
     95       }
     96       if (orig->InputCount() == 0 || orig->opcode() == IrOpcode::kParameter ||
     97           orig->opcode() == IrOpcode::kOsrValue ||
     98           orig->opcode() == IrOpcode::kOsrGuard) {
     99         // No need to copy leaf nodes or parameters.
    100         mapping->at(orig->id()) = orig;
    101         continue;
    102       }
    103 
    104       // Copy the node.
    105       tmp_inputs.clear();
    106       for (Node* input : orig->inputs()) {
    107         tmp_inputs.push_back(mapping->at(input->id()));
    108       }
    109       copy = graph->NewNode(orig->op(), orig->InputCount(), &tmp_inputs[0]);
    110       if (NodeProperties::IsTyped(orig)) {
    111         NodeProperties::SetType(copy, NodeProperties::GetType(orig));
    112       }
    113       mapping->at(orig->id()) = copy;
    114       TRACE(" copy #%d:%s -> #%d\n", orig->id(), orig->op()->mnemonic(),
    115             copy->id());
    116     }
    117 
    118     // Fix missing inputs.
    119     for (Node* orig : all.reachable) {
    120       Node* copy = mapping->at(orig->id());
    121       for (int j = 0; j < copy->InputCount(); j++) {
    122         if (copy->InputAt(j) == sentinel) {
    123           copy->ReplaceInput(j, mapping->at(orig->InputAt(j)->id()));
    124         }
    125       }
    126     }
    127 
    128     // Construct the entry into this loop from previous copies.
    129 
    130     // Gather the live loop header nodes, {loop_header} first.
    131     Node* loop_header = loop_tree->HeaderNode(loop);
    132     NodeVector header_nodes(tmp_zone);
    133     header_nodes.reserve(loop->HeaderSize());
    134     header_nodes.push_back(loop_header);  // put the loop header first.
    135     for (Node* node : loop_tree->HeaderNodes(loop)) {
    136       if (node != loop_header && all.IsLive(node)) {
    137         header_nodes.push_back(node);
    138       }
    139     }
    140 
    141     // Gather backedges from the previous copies of the inner loops of {loop}.
    142     NodeVectorVector backedges(tmp_zone);
    143     TRACE("Gathering backedges...\n");
    144     for (int i = 1; i < loop_header->InputCount(); i++) {
    145       if (TRACE_COND) {
    146         Node* control = loop_header->InputAt(i);
    147         size_t incoming_depth = 0;
    148         for (int j = 0; j < control->op()->ControlInputCount(); j++) {
    149           Node* k = NodeProperties::GetControlInput(control, j);
    150           incoming_depth =
    151               std::max(incoming_depth, loop_tree->ContainingLoop(k)->depth());
    152         }
    153 
    154         TRACE(" edge @%d #%d:%s, incoming depth %zu\n", i, control->id(),
    155               control->op()->mnemonic(), incoming_depth);
    156       }
    157 
    158       for (int pos = static_cast<int>(copies.size()) - 1; pos >= 0; pos--) {
    159         backedges.push_back(NodeVector(tmp_zone));
    160         backedges.back().reserve(header_nodes.size());
    161 
    162         NodeVector* previous_map = pos > 0 ? copies[pos - 1] : nullptr;
    163 
    164         for (Node* node : header_nodes) {
    165           Node* input = node->InputAt(i);
    166           if (previous_map) input = previous_map->at(input->id());
    167           backedges.back().push_back(input);
    168           TRACE("   node #%d:%s(@%d) = #%d:%s\n", node->id(),
    169                 node->op()->mnemonic(), i, input->id(),
    170                 input->op()->mnemonic());
    171         }
    172       }
    173     }
    174 
    175     int backedge_count = static_cast<int>(backedges.size());
    176     if (backedge_count == 1) {
    177       // Simple case of single backedge, therefore a single entry.
    178       int index = 0;
    179       for (Node* node : header_nodes) {
    180         Node* copy = mapping->at(node->id());
    181         Node* input = backedges[0][index];
    182         copy->ReplaceInput(0, input);
    183         TRACE(" header #%d:%s(0) => #%d:%s\n", copy->id(),
    184               copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
    185         index++;
    186       }
    187     } else {
    188       // Complex case of multiple backedges from previous copies requires
    189       // merging the backedges to create the entry into the loop header.
    190       Node* merge = nullptr;
    191       int index = 0;
    192       for (Node* node : header_nodes) {
    193         // Gather edge inputs into {tmp_inputs}.
    194         tmp_inputs.clear();
    195         for (int edge = 0; edge < backedge_count; edge++) {
    196           tmp_inputs.push_back(backedges[edge][index]);
    197         }
    198         Node* copy = mapping->at(node->id());
    199         Node* input;
    200         if (node == loop_header) {
    201           // Create the merge for the entry into the loop header.
    202           input = merge = graph->NewNode(common->Merge(backedge_count),
    203                                          backedge_count, &tmp_inputs[0]);
    204           copy->ReplaceInput(0, merge);
    205         } else {
    206           // Create a phi that merges values at entry into the loop header.
    207           DCHECK_NOT_NULL(merge);
    208           DCHECK(IrOpcode::IsPhiOpcode(node->opcode()));
    209           tmp_inputs.push_back(merge);
    210           Node* phi = input = graph->NewNode(
    211               common->ResizeMergeOrPhi(node->op(), backedge_count),
    212               backedge_count + 1, &tmp_inputs[0]);
    213           copy->ReplaceInput(0, phi);
    214         }
    215 
    216         // Print the merge.
    217         if (TRACE_COND) {
    218           TRACE(" header #%d:%s(0) => #%d:%s(", copy->id(),
    219                 copy->op()->mnemonic(), input->id(), input->op()->mnemonic());
    220           for (size_t i = 0; i < tmp_inputs.size(); i++) {
    221             if (i > 0) TRACE(", ");
    222             Node* input = tmp_inputs[i];
    223             TRACE("#%d:%s", input->id(), input->op()->mnemonic());
    224           }
    225           TRACE(")\n");
    226         }
    227 
    228         index++;
    229       }
    230     }
    231   }
    232 
    233   // Kill the outer loops in the original graph.
    234   TRACE("Killing outer loop headers...\n");
    235   for (LoopTree::Loop* outer = osr_loop->parent(); outer;
    236        outer = outer->parent()) {
    237     Node* loop_header = loop_tree->HeaderNode(outer);
    238     loop_header->ReplaceUses(dead);
    239     TRACE(" ---- #%d:%s\n", loop_header->id(), loop_header->op()->mnemonic());
    240   }
    241 
    242   // Merge the ends of the graph copies.
    243   Node* const end = graph->end();
    244   int const input_count = end->InputCount();
    245   for (int i = 0; i < input_count; ++i) {
    246     NodeId const id = end->InputAt(i)->id();
    247     for (NodeVector* const copy : copies) {
    248       end->AppendInput(graph->zone(), copy->at(id));
    249       NodeProperties::ChangeOp(end, common->End(end->InputCount()));
    250     }
    251   }
    252 
    253   if (FLAG_trace_turbo_graph) {  // Simple textual RPO.
    254     OFStream os(stdout);
    255     os << "-- Graph after OSR duplication -- " << std::endl;
    256     os << AsRPO(*graph);
    257   }
    258 }
    259 
    260 void SetTypeForOsrValue(Node* osr_value, Node* loop,
    261                         CommonOperatorBuilder* common) {
    262   Node* osr_guard = nullptr;
    263   for (Node* use : osr_value->uses()) {
    264     if (use->opcode() == IrOpcode::kOsrGuard) {
    265       DCHECK_EQ(use->InputAt(0), osr_value);
    266       osr_guard = use;
    267       break;
    268     }
    269   }
    270 
    271   NodeProperties::ChangeOp(osr_guard, common->OsrGuard(OsrGuardType::kAny));
    272 }
    273 
    274 }  // namespace
    275 
    276 void OsrHelper::Deconstruct(JSGraph* jsgraph, CommonOperatorBuilder* common,
    277                             Zone* tmp_zone) {
    278   Graph* graph = jsgraph->graph();
    279   Node* osr_normal_entry = nullptr;
    280   Node* osr_loop_entry = nullptr;
    281   Node* osr_loop = nullptr;
    282 
    283   for (Node* node : graph->start()->uses()) {
    284     if (node->opcode() == IrOpcode::kOsrLoopEntry) {
    285       osr_loop_entry = node;  // found the OSR loop entry
    286     } else if (node->opcode() == IrOpcode::kOsrNormalEntry) {
    287       osr_normal_entry = node;
    288     }
    289   }
    290 
    291   CHECK_NOT_NULL(osr_normal_entry);  // Should have found the OSR normal entry.
    292   CHECK_NOT_NULL(osr_loop_entry);    // Should have found the OSR loop entry.
    293 
    294   for (Node* use : osr_loop_entry->uses()) {
    295     if (use->opcode() == IrOpcode::kLoop) {
    296       CHECK(!osr_loop);             // should be only one OSR loop.
    297       osr_loop = use;               // found the OSR loop.
    298     }
    299   }
    300 
    301   CHECK(osr_loop);  // Should have found the OSR loop.
    302 
    303   for (Node* use : osr_loop_entry->uses()) {
    304     if (use->opcode() == IrOpcode::kOsrValue) {
    305       SetTypeForOsrValue(use, osr_loop, common);
    306     }
    307   }
    308 
    309   // Analyze the graph to determine how deeply nested the OSR loop is.
    310   LoopTree* loop_tree = LoopFinder::BuildLoopTree(graph, tmp_zone);
    311 
    312   Node* dead = jsgraph->Dead();
    313   LoopTree::Loop* loop = loop_tree->ContainingLoop(osr_loop);
    314   if (loop->depth() > 0) {
    315     PeelOuterLoopsForOsr(graph, common, tmp_zone, dead, loop_tree, loop,
    316                          osr_normal_entry, osr_loop_entry);
    317   }
    318 
    319   // Replace the normal entry with {Dead} and the loop entry with {Start}
    320   // and run the control reducer to clean up the graph.
    321   osr_normal_entry->ReplaceUses(dead);
    322   osr_normal_entry->Kill();
    323   osr_loop_entry->ReplaceUses(graph->start());
    324   osr_loop_entry->Kill();
    325 
    326   // Remove the first input to the {osr_loop}.
    327   int const live_input_count = osr_loop->InputCount() - 1;
    328   CHECK_NE(0, live_input_count);
    329   for (Node* const use : osr_loop->uses()) {
    330     if (NodeProperties::IsPhi(use)) {
    331       use->RemoveInput(0);
    332       NodeProperties::ChangeOp(
    333           use, common->ResizeMergeOrPhi(use->op(), live_input_count));
    334     }
    335   }
    336   osr_loop->RemoveInput(0);
    337   NodeProperties::ChangeOp(
    338       osr_loop, common->ResizeMergeOrPhi(osr_loop->op(), live_input_count));
    339 
    340   // Run control reduction and graph trimming.
    341   // TODO(bmeurer): The OSR deconstruction could be a regular reducer and play
    342   // nice together with the rest, instead of having this custom stuff here.
    343   GraphReducer graph_reducer(tmp_zone, graph);
    344   DeadCodeElimination dce(&graph_reducer, graph, common);
    345   CommonOperatorReducer cor(&graph_reducer, graph, common, jsgraph->machine());
    346   graph_reducer.AddReducer(&dce);
    347   graph_reducer.AddReducer(&cor);
    348   graph_reducer.ReduceGraph();
    349   GraphTrimmer trimmer(tmp_zone, graph);
    350   NodeVector roots(tmp_zone);
    351   jsgraph->GetCachedNodes(&roots);
    352   trimmer.TrimGraph(roots.begin(), roots.end());
    353 }
    354 
    355 
    356 void OsrHelper::SetupFrame(Frame* frame) {
    357   // The optimized frame will subsume the unoptimized frame. Do so by reserving
    358   // the first spill slots.
    359   frame->ReserveSpillSlots(UnoptimizedFrameSlots());
    360 }
    361 
    362 }  // namespace compiler
    363 }  // namespace internal
    364 }  // namespace v8
    365