deps/v8/src/compiler/osr.cc

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