1958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Copyright 2014 the V8 project authors. All rights reserved. 2958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Use of this source code is governed by a BSD-style license that can be 3958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// found in the LICENSE file. 4958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 5958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/compiler/select-lowering.h" 6958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 7958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/compiler/common-operator.h" 8958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/compiler/diamond.h" 9958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/compiler/graph.h" 10958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include "src/compiler/node.h" 11014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/compiler/node-properties.h" 12958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 13958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace v8 { 14958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace internal { 15958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniernamespace compiler { 16958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 17958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierSelectLowering::SelectLowering(Graph* graph, CommonOperatorBuilder* common) 18958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : common_(common), 19958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier graph_(graph), 20958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier merges_(Merges::key_compare(), Merges::allocator_type(graph->zone())) {} 21958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 22958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 23958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierSelectLowering::~SelectLowering() {} 24958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 25958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 26958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierReduction SelectLowering::Reduce(Node* node) { 27958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (node->opcode() != IrOpcode::kSelect) return NoChange(); 28958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SelectParameters const p = SelectParametersOf(node->op()); 29958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 30958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* cond = node->InputAt(0); 31958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* vthen = node->InputAt(1); 32958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* velse = node->InputAt(2); 33958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* merge = nullptr; 34958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 35958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Check if we already have a diamond for this condition. 36958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier auto range = merges_.equal_range(cond); 37958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier for (auto i = range.first;; ++i) { 38958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (i == range.second) { 39958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Create a new diamond for this condition and remember its merge node. 40958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Diamond d(graph(), common(), cond, p.hint()); 41958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier merges_.insert(std::make_pair(cond, d.merge)); 42958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier merge = d.merge; 43958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier break; 44958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 45958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 46958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // If the diamond is reachable from the Select, merging them would result in 47958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // an unschedulable graph, so we cannot reuse the diamond in that case. 48958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier merge = i->second; 49958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (!ReachableFrom(merge, node)) { 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier break; 51958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 52958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 53958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 54958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Create a Phi hanging off the previously determined merge. 55958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier node->ReplaceInput(0, vthen); 56958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier node->ReplaceInput(1, velse); 57958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier node->ReplaceInput(2, merge); 58014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch NodeProperties::ChangeOp(node, common()->Phi(p.representation(), 2)); 59958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return Changed(node); 60958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 61958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 62958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 63958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierbool SelectLowering::ReachableFrom(Node* const sink, Node* const source) { 64958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // TODO(turbofan): This is probably horribly expensive, and it should be moved 65958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // into node.h or somewhere else?! 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 67958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier std::queue<Node*, NodeDeque> queue((NodeDeque(&zone))); 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BoolVector visited(graph()->NodeCount(), false, &zone); 69958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier queue.push(source); 70958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier visited[source->id()] = true; 71958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier while (!queue.empty()) { 72958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* current = queue.front(); 73958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (current == sink) return true; 74958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier queue.pop(); 75958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier for (auto input : current->inputs()) { 76958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (!visited[input->id()]) { 77958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier queue.push(input); 78958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier visited[input->id()] = true; 79958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 80958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 81958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 82958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return false; 83958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 84958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 85958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace compiler 86958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace internal 87958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace v8 88