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/common-operator-reducer.h"
6
7#include <algorithm>
8
9#include "src/compiler/common-operator.h"
10#include "src/compiler/graph.h"
11#include "src/compiler/machine-operator.h"
12#include "src/compiler/node.h"
13#include "src/compiler/node-matchers.h"
14#include "src/compiler/node-properties.h"
15
16namespace v8 {
17namespace internal {
18namespace compiler {
19
20namespace {
21
22enum class Decision { kUnknown, kTrue, kFalse };
23
24Decision DecideCondition(Node* const cond) {
25  switch (cond->opcode()) {
26    case IrOpcode::kInt32Constant: {
27      Int32Matcher mcond(cond);
28      return mcond.Value() ? Decision::kTrue : Decision::kFalse;
29    }
30    case IrOpcode::kInt64Constant: {
31      Int64Matcher mcond(cond);
32      return mcond.Value() ? Decision::kTrue : Decision::kFalse;
33    }
34    case IrOpcode::kHeapConstant: {
35      HeapObjectMatcher mcond(cond);
36      return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
37    }
38    default:
39      return Decision::kUnknown;
40  }
41}
42
43}  // namespace
44
45
46CommonOperatorReducer::CommonOperatorReducer(Editor* editor, Graph* graph,
47                                             CommonOperatorBuilder* common,
48                                             MachineOperatorBuilder* machine)
49    : AdvancedReducer(editor),
50      graph_(graph),
51      common_(common),
52      machine_(machine),
53      dead_(graph->NewNode(common->Dead())) {}
54
55
56Reduction CommonOperatorReducer::Reduce(Node* node) {
57  switch (node->opcode()) {
58    case IrOpcode::kBranch:
59      return ReduceBranch(node);
60    case IrOpcode::kMerge:
61      return ReduceMerge(node);
62    case IrOpcode::kEffectPhi:
63      return ReduceEffectPhi(node);
64    case IrOpcode::kPhi:
65      return ReducePhi(node);
66    case IrOpcode::kReturn:
67      return ReduceReturn(node);
68    case IrOpcode::kSelect:
69      return ReduceSelect(node);
70    case IrOpcode::kGuard:
71      return ReduceGuard(node);
72    default:
73      break;
74  }
75  return NoChange();
76}
77
78
79Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
80  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
81  Node* const cond = node->InputAt(0);
82  // Swap IfTrue/IfFalse on {branch} if {cond} is a BooleanNot and use the input
83  // to BooleanNot as new condition for {branch}. Note we assume that {cond} was
84  // already properly optimized before we get here (as guaranteed by the graph
85  // reduction logic).
86  if (cond->opcode() == IrOpcode::kBooleanNot) {
87    for (Node* const use : node->uses()) {
88      switch (use->opcode()) {
89        case IrOpcode::kIfTrue:
90          NodeProperties::ChangeOp(use, common()->IfFalse());
91          break;
92        case IrOpcode::kIfFalse:
93          NodeProperties::ChangeOp(use, common()->IfTrue());
94          break;
95        default:
96          UNREACHABLE();
97      }
98    }
99    // Update the condition of {branch}. No need to mark the uses for revisit,
100    // since we tell the graph reducer that the {branch} was changed and the
101    // graph reduction logic will ensure that the uses are revisited properly.
102    node->ReplaceInput(0, cond->InputAt(0));
103    // Negate the hint for {branch}.
104    NodeProperties::ChangeOp(
105        node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
106    return Changed(node);
107  }
108  Decision const decision = DecideCondition(cond);
109  if (decision == Decision::kUnknown) return NoChange();
110  Node* const control = node->InputAt(1);
111  for (Node* const use : node->uses()) {
112    switch (use->opcode()) {
113      case IrOpcode::kIfTrue:
114        Replace(use, (decision == Decision::kTrue) ? control : dead());
115        break;
116      case IrOpcode::kIfFalse:
117        Replace(use, (decision == Decision::kFalse) ? control : dead());
118        break;
119      default:
120        UNREACHABLE();
121    }
122  }
123  return Replace(dead());
124}
125
126
127Reduction CommonOperatorReducer::ReduceMerge(Node* node) {
128  DCHECK_EQ(IrOpcode::kMerge, node->opcode());
129  //
130  // Check if this is a merge that belongs to an unused diamond, which means
131  // that:
132  //
133  //  a) the {Merge} has no {Phi} or {EffectPhi} uses, and
134  //  b) the {Merge} has two inputs, one {IfTrue} and one {IfFalse}, which are
135  //     both owned by the Merge, and
136  //  c) and the {IfTrue} and {IfFalse} nodes point to the same {Branch}.
137  //
138  if (node->InputCount() == 2) {
139    for (Node* const use : node->uses()) {
140      if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
141    }
142    Node* if_true = node->InputAt(0);
143    Node* if_false = node->InputAt(1);
144    if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
145    if (if_true->opcode() == IrOpcode::kIfTrue &&
146        if_false->opcode() == IrOpcode::kIfFalse &&
147        if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
148        if_false->OwnedBy(node)) {
149      Node* const branch = if_true->InputAt(0);
150      DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
151      DCHECK(branch->OwnedBy(if_true, if_false));
152      Node* const control = branch->InputAt(1);
153      // Mark the {branch} as {Dead}.
154      branch->TrimInputCount(0);
155      NodeProperties::ChangeOp(branch, common()->Dead());
156      return Replace(control);
157    }
158  }
159  return NoChange();
160}
161
162
163Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
164  DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
165  int const input_count = node->InputCount() - 1;
166  DCHECK_LE(1, input_count);
167  Node* const merge = node->InputAt(input_count);
168  DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
169  DCHECK_EQ(input_count, merge->InputCount());
170  Node* const effect = node->InputAt(0);
171  DCHECK_NE(node, effect);
172  for (int i = 1; i < input_count; ++i) {
173    Node* const input = node->InputAt(i);
174    if (input == node) {
175      // Ignore redundant inputs.
176      DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
177      continue;
178    }
179    if (input != effect) return NoChange();
180  }
181  // We might now be able to further reduce the {merge} node.
182  Revisit(merge);
183  return Replace(effect);
184}
185
186
187Reduction CommonOperatorReducer::ReducePhi(Node* node) {
188  DCHECK_EQ(IrOpcode::kPhi, node->opcode());
189  int const input_count = node->InputCount() - 1;
190  DCHECK_LE(1, input_count);
191  Node* const merge = node->InputAt(input_count);
192  DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
193  DCHECK_EQ(input_count, merge->InputCount());
194  if (input_count == 2) {
195    Node* vtrue = node->InputAt(0);
196    Node* vfalse = node->InputAt(1);
197    Node* if_true = merge->InputAt(0);
198    Node* if_false = merge->InputAt(1);
199    if (if_true->opcode() != IrOpcode::kIfTrue) {
200      std::swap(if_true, if_false);
201      std::swap(vtrue, vfalse);
202    }
203    if (if_true->opcode() == IrOpcode::kIfTrue &&
204        if_false->opcode() == IrOpcode::kIfFalse &&
205        if_true->InputAt(0) == if_false->InputAt(0)) {
206      Node* const branch = if_true->InputAt(0);
207      // Check that the branch is not dead already.
208      if (branch->opcode() != IrOpcode::kBranch) return NoChange();
209      Node* const cond = branch->InputAt(0);
210      if (cond->opcode() == IrOpcode::kFloat32LessThan) {
211        Float32BinopMatcher mcond(cond);
212        if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
213            vfalse->opcode() == IrOpcode::kFloat32Sub) {
214          Float32BinopMatcher mvfalse(vfalse);
215          if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
216            // We might now be able to further reduce the {merge} node.
217            Revisit(merge);
218            return Change(node, machine()->Float32Abs(), vtrue);
219          }
220        }
221        if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
222            machine()->Float32Min().IsSupported()) {
223          // We might now be able to further reduce the {merge} node.
224          Revisit(merge);
225          return Change(node, machine()->Float32Min().op(), vtrue, vfalse);
226        } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
227                   machine()->Float32Max().IsSupported()) {
228          // We might now be able to further reduce the {merge} node.
229          Revisit(merge);
230          return Change(node, machine()->Float32Max().op(), vtrue, vfalse);
231        }
232      } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
233        Float64BinopMatcher mcond(cond);
234        if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
235            vfalse->opcode() == IrOpcode::kFloat64Sub) {
236          Float64BinopMatcher mvfalse(vfalse);
237          if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
238            // We might now be able to further reduce the {merge} node.
239            Revisit(merge);
240            return Change(node, machine()->Float64Abs(), vtrue);
241          }
242        }
243        if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
244            machine()->Float64Min().IsSupported()) {
245          // We might now be able to further reduce the {merge} node.
246          Revisit(merge);
247          return Change(node, machine()->Float64Min().op(), vtrue, vfalse);
248        } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
249                   machine()->Float64Max().IsSupported()) {
250          // We might now be able to further reduce the {merge} node.
251          Revisit(merge);
252          return Change(node, machine()->Float64Max().op(), vtrue, vfalse);
253        }
254      }
255    }
256  }
257  Node* const value = node->InputAt(0);
258  DCHECK_NE(node, value);
259  for (int i = 1; i < input_count; ++i) {
260    Node* const input = node->InputAt(i);
261    if (input == node) {
262      // Ignore redundant inputs.
263      DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
264      continue;
265    }
266    if (input != value) return NoChange();
267  }
268  // We might now be able to further reduce the {merge} node.
269  Revisit(merge);
270  return Replace(value);
271}
272
273
274Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
275  DCHECK_EQ(IrOpcode::kReturn, node->opcode());
276  Node* const value = node->InputAt(0);
277  Node* const effect = node->InputAt(1);
278  Node* const control = node->InputAt(2);
279  if (value->opcode() == IrOpcode::kPhi &&
280      NodeProperties::GetControlInput(value) == control &&
281      effect->opcode() == IrOpcode::kEffectPhi &&
282      NodeProperties::GetControlInput(effect) == control &&
283      control->opcode() == IrOpcode::kMerge) {
284    int const control_input_count = control->InputCount();
285    DCHECK_NE(0, control_input_count);
286    DCHECK_EQ(control_input_count, value->InputCount() - 1);
287    DCHECK_EQ(control_input_count, effect->InputCount() - 1);
288    DCHECK_EQ(IrOpcode::kEnd, graph()->end()->opcode());
289    DCHECK_NE(0, graph()->end()->InputCount());
290    for (int i = 0; i < control_input_count; ++i) {
291      // Create a new {Return} and connect it to {end}. We don't need to mark
292      // {end} as revisit, because we mark {node} as {Dead} below, which was
293      // previously connected to {end}, so we know for sure that at some point
294      // the reducer logic will visit {end} again.
295      Node* ret = graph()->NewNode(common()->Return(), value->InputAt(i),
296                                   effect->InputAt(i), control->InputAt(i));
297      NodeProperties::MergeControlToEnd(graph(), common(), ret);
298    }
299    // Mark the merge {control} and return {node} as {dead}.
300    Replace(control, dead());
301    return Replace(dead());
302  }
303  return NoChange();
304}
305
306
307Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
308  DCHECK_EQ(IrOpcode::kSelect, node->opcode());
309  Node* const cond = node->InputAt(0);
310  Node* const vtrue = node->InputAt(1);
311  Node* const vfalse = node->InputAt(2);
312  if (vtrue == vfalse) return Replace(vtrue);
313  switch (DecideCondition(cond)) {
314    case Decision::kTrue:
315      return Replace(vtrue);
316    case Decision::kFalse:
317      return Replace(vfalse);
318    case Decision::kUnknown:
319      break;
320  }
321  switch (cond->opcode()) {
322    case IrOpcode::kFloat32LessThan: {
323      Float32BinopMatcher mcond(cond);
324      if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
325          vfalse->opcode() == IrOpcode::kFloat32Sub) {
326        Float32BinopMatcher mvfalse(vfalse);
327        if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
328          return Change(node, machine()->Float32Abs(), vtrue);
329        }
330      }
331      if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
332          machine()->Float32Min().IsSupported()) {
333        return Change(node, machine()->Float32Min().op(), vtrue, vfalse);
334      } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
335                 machine()->Float32Max().IsSupported()) {
336        return Change(node, machine()->Float32Max().op(), vtrue, vfalse);
337      }
338      break;
339    }
340    case IrOpcode::kFloat64LessThan: {
341      Float64BinopMatcher mcond(cond);
342      if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
343          vfalse->opcode() == IrOpcode::kFloat64Sub) {
344        Float64BinopMatcher mvfalse(vfalse);
345        if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
346          return Change(node, machine()->Float64Abs(), vtrue);
347        }
348      }
349      if (mcond.left().Equals(vtrue) && mcond.right().Equals(vfalse) &&
350          machine()->Float64Min().IsSupported()) {
351        return Change(node, machine()->Float64Min().op(), vtrue, vfalse);
352      } else if (mcond.left().Equals(vfalse) && mcond.right().Equals(vtrue) &&
353                 machine()->Float64Max().IsSupported()) {
354        return Change(node, machine()->Float64Max().op(), vtrue, vfalse);
355      }
356      break;
357    }
358    default:
359      break;
360  }
361  return NoChange();
362}
363
364
365Reduction CommonOperatorReducer::ReduceGuard(Node* node) {
366  DCHECK_EQ(IrOpcode::kGuard, node->opcode());
367  Node* const input = NodeProperties::GetValueInput(node, 0);
368  Type* const input_type = NodeProperties::GetTypeOrAny(input);
369  Type* const guard_type = OpParameter<Type*>(node);
370  if (input_type->Is(guard_type)) return Replace(input);
371  return NoChange();
372}
373
374
375Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
376                                        Node* a) {
377  node->ReplaceInput(0, a);
378  node->TrimInputCount(1);
379  NodeProperties::ChangeOp(node, op);
380  return Changed(node);
381}
382
383
384Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
385                                        Node* b) {
386  node->ReplaceInput(0, a);
387  node->ReplaceInput(1, b);
388  node->TrimInputCount(2);
389  NodeProperties::ChangeOp(node, op);
390  return Changed(node);
391}
392
393}  // namespace compiler
394}  // namespace internal
395}  // namespace v8
396