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/select-lowering.h"
      6 
      7 #include "src/compiler/common-operator.h"
      8 #include "src/compiler/diamond.h"
      9 #include "src/compiler/graph.h"
     10 #include "src/compiler/node.h"
     11 #include "src/compiler/node-properties.h"
     12 
     13 namespace v8 {
     14 namespace internal {
     15 namespace compiler {
     16 
     17 SelectLowering::SelectLowering(Graph* graph, CommonOperatorBuilder* common)
     18     : common_(common),
     19       graph_(graph),
     20       merges_(Merges::key_compare(), Merges::allocator_type(graph->zone())) {}
     21 
     22 
     23 SelectLowering::~SelectLowering() {}
     24 
     25 
     26 Reduction SelectLowering::Reduce(Node* node) {
     27   if (node->opcode() != IrOpcode::kSelect) return NoChange();
     28   SelectParameters const p = SelectParametersOf(node->op());
     29 
     30   Node* cond = node->InputAt(0);
     31   Node* vthen = node->InputAt(1);
     32   Node* velse = node->InputAt(2);
     33   Node* merge = nullptr;
     34 
     35   // Check if we already have a diamond for this condition.
     36   auto range = merges_.equal_range(cond);
     37   for (auto i = range.first;; ++i) {
     38     if (i == range.second) {
     39       // Create a new diamond for this condition and remember its merge node.
     40       Diamond d(graph(), common(), cond, p.hint());
     41       merges_.insert(std::make_pair(cond, d.merge));
     42       merge = d.merge;
     43       break;
     44     }
     45 
     46     // If the diamond is reachable from the Select, merging them would result in
     47     // an unschedulable graph, so we cannot reuse the diamond in that case.
     48     merge = i->second;
     49     if (!ReachableFrom(merge, node)) {
     50       break;
     51     }
     52   }
     53 
     54   // Create a Phi hanging off the previously determined merge.
     55   node->ReplaceInput(0, vthen);
     56   node->ReplaceInput(1, velse);
     57   node->ReplaceInput(2, merge);
     58   NodeProperties::ChangeOp(node, common()->Phi(p.representation(), 2));
     59   return Changed(node);
     60 }
     61 
     62 
     63 bool SelectLowering::ReachableFrom(Node* const sink, Node* const source) {
     64   // TODO(turbofan): This is probably horribly expensive, and it should be moved
     65   // into node.h or somewhere else?!
     66   Zone zone;
     67   std::queue<Node*, NodeDeque> queue((NodeDeque(&zone)));
     68   BoolVector visited(graph()->NodeCount(), false, &zone);
     69   queue.push(source);
     70   visited[source->id()] = true;
     71   while (!queue.empty()) {
     72     Node* current = queue.front();
     73     if (current == sink) return true;
     74     queue.pop();
     75     for (auto input : current->inputs()) {
     76       if (!visited[input->id()]) {
     77         queue.push(input);
     78         visited[input->id()] = true;
     79       }
     80     }
     81   }
     82   return false;
     83 }
     84 
     85 }  // namespace compiler
     86 }  // namespace internal
     87 }  // namespace v8
     88