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