common-operator-reducer.cc 16.4 KB
Newer Older
1 2 3 4 5 6
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/common-operator-reducer.h"

7 8
#include <algorithm>

9
#include "src/compiler/common-operator.h"
10 11
#include "src/compiler/graph.h"
#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 16 17 18 19

namespace v8 {
namespace internal {
namespace compiler {

20 21 22 23 24 25 26 27 28
namespace {

Decision DecideCondition(Node* const cond) {
  switch (cond->opcode()) {
    case IrOpcode::kInt32Constant: {
      Int32Matcher mcond(cond);
      return mcond.Value() ? Decision::kTrue : Decision::kFalse;
    }
    case IrOpcode::kHeapConstant: {
29
      HeapObjectMatcher mcond(cond);
30
      return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
31 32 33 34 35 36 37 38
    }
    default:
      return Decision::kUnknown;
  }
}

}  // namespace

39 40 41 42 43 44 45
CommonOperatorReducer::CommonOperatorReducer(Editor* editor, Graph* graph,
                                             CommonOperatorBuilder* common,
                                             MachineOperatorBuilder* machine)
    : AdvancedReducer(editor),
      graph_(graph),
      common_(common),
      machine_(machine),
46 47 48
      dead_(graph->NewNode(common->Dead())) {
  NodeProperties::SetType(dead_, Type::None());
}
49

50 51
Reduction CommonOperatorReducer::Reduce(Node* node) {
  switch (node->opcode()) {
52 53
    case IrOpcode::kBranch:
      return ReduceBranch(node);
54 55 56
    case IrOpcode::kDeoptimizeIf:
    case IrOpcode::kDeoptimizeUnless:
      return ReduceDeoptimizeConditional(node);
57 58
    case IrOpcode::kMerge:
      return ReduceMerge(node);
59
    case IrOpcode::kEffectPhi:
60 61 62
      return ReduceEffectPhi(node);
    case IrOpcode::kPhi:
      return ReducePhi(node);
63 64
    case IrOpcode::kReturn:
      return ReduceReturn(node);
65 66 67
    case IrOpcode::kSelect:
      return ReduceSelect(node);
    default:
68
      break;
69 70 71 72 73
  }
  return NoChange();
}


74 75 76
Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  Node* const cond = node->InputAt(0);
77 78 79
  // Swap IfTrue/IfFalse on {branch} if {cond} is a BooleanNot and use the input
  // to BooleanNot as new condition for {branch}. Note we assume that {cond} was
  // already properly optimized before we get here (as guaranteed by the graph
80 81 82 83 84 85
  // reduction logic). The same applies if {cond} is a Select acting as boolean
  // not (i.e. true being returned in the false case and vice versa).
  if (cond->opcode() == IrOpcode::kBooleanNot ||
      (cond->opcode() == IrOpcode::kSelect &&
       DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
       DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
86 87 88
    for (Node* const use : node->uses()) {
      switch (use->opcode()) {
        case IrOpcode::kIfTrue:
89
          NodeProperties::ChangeOp(use, common()->IfFalse());
90 91
          break;
        case IrOpcode::kIfFalse:
92
          NodeProperties::ChangeOp(use, common()->IfTrue());
93 94 95 96 97 98 99 100 101
          break;
        default:
          UNREACHABLE();
      }
    }
    // Update the condition of {branch}. No need to mark the uses for revisit,
    // since we tell the graph reducer that the {branch} was changed and the
    // graph reduction logic will ensure that the uses are revisited properly.
    node->ReplaceInput(0, cond->InputAt(0));
102
    // Negate the hint for {branch}.
103 104
    NodeProperties::ChangeOp(
        node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
105 106
    return Changed(node);
  }
107 108 109 110 111 112
  Decision const decision = DecideCondition(cond);
  if (decision == Decision::kUnknown) return NoChange();
  Node* const control = node->InputAt(1);
  for (Node* const use : node->uses()) {
    switch (use->opcode()) {
      case IrOpcode::kIfTrue:
113
        Replace(use, (decision == Decision::kTrue) ? control : dead());
114 115
        break;
      case IrOpcode::kIfFalse:
116
        Replace(use, (decision == Decision::kFalse) ? control : dead());
117 118 119 120 121
        break;
      default:
        UNREACHABLE();
    }
  }
122
  return Replace(dead());
123 124
}

125 126 127 128
Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
         node->opcode() == IrOpcode::kDeoptimizeUnless);
  bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
129
  DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
130 131 132 133 134 135 136 137 138 139
  Node* condition = NodeProperties::GetValueInput(node, 0);
  Node* frame_state = NodeProperties::GetValueInput(node, 1);
  Node* effect = NodeProperties::GetEffectInput(node);
  Node* control = NodeProperties::GetControlInput(node);
  // Swap DeoptimizeIf/DeoptimizeUnless on {node} if {cond} is a BooleaNot
  // and use the input to BooleanNot as new condition for {node}.  Note we
  // assume that {cond} was already properly optimized before we get here
  // (as guaranteed by the graph reduction logic).
  if (condition->opcode() == IrOpcode::kBooleanNot) {
    NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0);
140
    NodeProperties::ChangeOp(
141 142 143 144
        node,
        condition_is_true
            ? common()->DeoptimizeIf(p.kind(), p.reason(), p.feedback())
            : common()->DeoptimizeUnless(p.kind(), p.reason(), p.feedback()));
145 146 147 148 149
    return Changed(node);
  }
  Decision const decision = DecideCondition(condition);
  if (decision == Decision::kUnknown) return NoChange();
  if (condition_is_true == (decision == Decision::kTrue)) {
150 151
    ReplaceWithValue(node, dead(), effect, control);
  } else {
152
    control = graph()->NewNode(
153 154
        common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
        effect, control);
155 156 157
    // TODO(bmeurer): This should be on the AdvancedReducer somehow.
    NodeProperties::MergeControlToEnd(graph(), common(), control);
    Revisit(graph()->end());
158 159 160
  }
  return Replace(dead());
}
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

Reduction CommonOperatorReducer::ReduceMerge(Node* node) {
  DCHECK_EQ(IrOpcode::kMerge, node->opcode());
  //
  // Check if this is a merge that belongs to an unused diamond, which means
  // that:
  //
  //  a) the {Merge} has no {Phi} or {EffectPhi} uses, and
  //  b) the {Merge} has two inputs, one {IfTrue} and one {IfFalse}, which are
  //     both owned by the Merge, and
  //  c) and the {IfTrue} and {IfFalse} nodes point to the same {Branch}.
  //
  if (node->InputCount() == 2) {
    for (Node* const use : node->uses()) {
      if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
    }
    Node* if_true = node->InputAt(0);
    Node* if_false = node->InputAt(1);
    if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
    if (if_true->opcode() == IrOpcode::kIfTrue &&
        if_false->opcode() == IrOpcode::kIfFalse &&
        if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
        if_false->OwnedBy(node)) {
      Node* const branch = if_true->InputAt(0);
      DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
      DCHECK(branch->OwnedBy(if_true, if_false));
      Node* const control = branch->InputAt(1);
      // Mark the {branch} as {Dead}.
      branch->TrimInputCount(0);
190
      NodeProperties::ChangeOp(branch, common()->Dead());
191 192 193 194 195 196 197
      return Replace(control);
    }
  }
  return NoChange();
}


198 199
Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
  DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
200 201 202 203
  Node::Inputs inputs = node->inputs();
  int const effect_input_count = inputs.count() - 1;
  DCHECK_LE(1, effect_input_count);
  Node* const merge = inputs[effect_input_count];
204
  DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
205 206
  DCHECK_EQ(effect_input_count, merge->InputCount());
  Node* const effect = inputs[0];
207
  DCHECK_NE(node, effect);
208 209
  for (int i = 1; i < effect_input_count; ++i) {
    Node* const input = inputs[i];
210 211 212 213
    if (input == node) {
      // Ignore redundant inputs.
      DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
      continue;
214
    }
215
    if (input != effect) return NoChange();
216
  }
217 218 219
  // We might now be able to further reduce the {merge} node.
  Revisit(merge);
  return Replace(effect);
220 221 222 223 224
}


Reduction CommonOperatorReducer::ReducePhi(Node* node) {
  DCHECK_EQ(IrOpcode::kPhi, node->opcode());
225 226 227 228
  Node::Inputs inputs = node->inputs();
  int const value_input_count = inputs.count() - 1;
  DCHECK_LE(1, value_input_count);
  Node* const merge = inputs[value_input_count];
229
  DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
230 231 232 233 234 235 236
  DCHECK_EQ(value_input_count, merge->InputCount());
  if (value_input_count == 2) {
    Node* vtrue = inputs[0];
    Node* vfalse = inputs[1];
    Node::Inputs merge_inputs = merge->inputs();
    Node* if_true = merge_inputs[0];
    Node* if_false = merge_inputs[1];
237 238 239 240 241 242 243 244
    if (if_true->opcode() != IrOpcode::kIfTrue) {
      std::swap(if_true, if_false);
      std::swap(vtrue, vfalse);
    }
    if (if_true->opcode() == IrOpcode::kIfTrue &&
        if_false->opcode() == IrOpcode::kIfFalse &&
        if_true->InputAt(0) == if_false->InputAt(0)) {
      Node* const branch = if_true->InputAt(0);
245 246
      // Check that the branch is not dead already.
      if (branch->opcode() != IrOpcode::kBranch) return NoChange();
247
      Node* const cond = branch->InputAt(0);
248 249 250
      if (cond->opcode() == IrOpcode::kFloat32LessThan) {
        Float32BinopMatcher mcond(cond);
        if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
251
            vfalse->opcode() == IrOpcode::kFloat32Sub) {
252 253
          Float32BinopMatcher mvfalse(vfalse);
          if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
254 255
            // We might now be able to further reduce the {merge} node.
            Revisit(merge);
256 257 258 259 260 261
            return Change(node, machine()->Float32Abs(), vtrue);
          }
        }
      } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
        Float64BinopMatcher mcond(cond);
        if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
262
            vfalse->opcode() == IrOpcode::kFloat64Sub) {
263 264
          Float64BinopMatcher mvfalse(vfalse);
          if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
265 266
            // We might now be able to further reduce the {merge} node.
            Revisit(merge);
267 268 269
            return Change(node, machine()->Float64Abs(), vtrue);
          }
        }
270 271
      }
    }
272
  }
273
  Node* const value = inputs[0];
274
  DCHECK_NE(node, value);
275 276
  for (int i = 1; i < value_input_count; ++i) {
    Node* const input = inputs[i];
277 278 279 280
    if (input == node) {
      // Ignore redundant inputs.
      DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
      continue;
281
    }
282
    if (input != value) return NoChange();
283
  }
284 285 286
  // We might now be able to further reduce the {merge} node.
  Revisit(merge);
  return Replace(value);
287 288
}

289 290
Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
  DCHECK_EQ(IrOpcode::kReturn, node->opcode());
291 292 293 294 295 296
  Node* effect = NodeProperties::GetEffectInput(node);
  if (effect->opcode() == IrOpcode::kCheckpoint) {
    // Any {Return} node can never be used to insert a deoptimization point,
    // hence checkpoints can be cut out of the effect chain flowing into it.
    effect = NodeProperties::GetEffectInput(effect);
    NodeProperties::ReplaceEffectInput(node, effect);
297 298
    Reduction const reduction = ReduceReturn(node);
    return reduction.Changed() ? reduction : Changed(node);
299
  }
300 301 302 303
  // TODO(ahaas): Extend the reduction below to multiple return values.
  if (ValueInputCountOfReturn(node->op()) != 1) {
    return NoChange();
  }
304 305 306
  Node* pop_count = NodeProperties::GetValueInput(node, 0);
  Node* value = NodeProperties::GetValueInput(node, 1);
  Node* control = NodeProperties::GetControlInput(node);
307 308 309
  if (value->opcode() == IrOpcode::kPhi &&
      NodeProperties::GetControlInput(value) == control &&
      control->opcode() == IrOpcode::kMerge) {
310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333
    // This optimization pushes {Return} nodes through merges. It checks that
    // the return value is actually a {Phi} and the return control dependency
    // is the {Merge} to which the {Phi} belongs.

    // Value1 ... ValueN Control1 ... ControlN
    //   ^          ^       ^            ^
    //   |          |       |            |
    //   +----+-----+       +------+-----+
    //        |                    |
    //       Phi --------------> Merge
    //        ^                    ^
    //        |                    |
    //        |  +-----------------+
    //        |  |
    //       Return -----> Effect
    //         ^
    //         |
    //        End

    // Now the effect input to the {Return} node can be either an {EffectPhi}
    // hanging off the same {Merge}, or the {Merge} node is only connected to
    // the {Return} and the {Phi}, in which case we know that the effect input
    // must somehow dominate all merged branches.

334 335 336 337
    Node::Inputs control_inputs = control->inputs();
    Node::Inputs value_inputs = value->inputs();
    DCHECK_NE(0, control_inputs.count());
    DCHECK_EQ(control_inputs.count(), value_inputs.count() - 1);
338 339
    DCHECK_EQ(IrOpcode::kEnd, graph()->end()->opcode());
    DCHECK_NE(0, graph()->end()->InputCount());
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368
    if (control->OwnedBy(node, value)) {
      for (int i = 0; i < control_inputs.count(); ++i) {
        // Create a new {Return} and connect it to {end}. We don't need to mark
        // {end} as revisit, because we mark {node} as {Dead} below, which was
        // previously connected to {end}, so we know for sure that at some point
        // the reducer logic will visit {end} again.
        Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i],
                                     effect, control_inputs[i]);
        NodeProperties::MergeControlToEnd(graph(), common(), ret);
      }
      // Mark the Merge {control} and Return {node} as {dead}.
      Replace(control, dead());
      return Replace(dead());
    } else if (effect->opcode() == IrOpcode::kEffectPhi &&
               NodeProperties::GetControlInput(effect) == control) {
      Node::Inputs effect_inputs = effect->inputs();
      DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
      for (int i = 0; i < control_inputs.count(); ++i) {
        // Create a new {Return} and connect it to {end}. We don't need to mark
        // {end} as revisit, because we mark {node} as {Dead} below, which was
        // previously connected to {end}, so we know for sure that at some point
        // the reducer logic will visit {end} again.
        Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i],
                                     effect_inputs[i], control_inputs[i]);
        NodeProperties::MergeControlToEnd(graph(), common(), ret);
      }
      // Mark the Merge {control} and Return {node} as {dead}.
      Replace(control, dead());
      return Replace(dead());
369 370
    }
  }
371
  return NoChange();
372 373
}

374 375
Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
  DCHECK_EQ(IrOpcode::kSelect, node->opcode());
376 377 378
  Node* const cond = node->InputAt(0);
  Node* const vtrue = node->InputAt(1);
  Node* const vfalse = node->InputAt(2);
379
  if (vtrue == vfalse) return Replace(vtrue);
380 381 382 383 384 385 386 387
  switch (DecideCondition(cond)) {
    case Decision::kTrue:
      return Replace(vtrue);
    case Decision::kFalse:
      return Replace(vfalse);
    case Decision::kUnknown:
      break;
  }
388 389 390 391
  switch (cond->opcode()) {
    case IrOpcode::kFloat32LessThan: {
      Float32BinopMatcher mcond(cond);
      if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
392
          vfalse->opcode() == IrOpcode::kFloat32Sub) {
393 394 395 396
        Float32BinopMatcher mvfalse(vfalse);
        if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
          return Change(node, machine()->Float32Abs(), vtrue);
        }
397
      }
398
      break;
399
    }
400 401 402
    case IrOpcode::kFloat64LessThan: {
      Float64BinopMatcher mcond(cond);
      if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
403
          vfalse->opcode() == IrOpcode::kFloat64Sub) {
404 405 406 407 408 409
        Float64BinopMatcher mvfalse(vfalse);
        if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
          return Change(node, machine()->Float64Abs(), vtrue);
        }
      }
      break;
410
    }
411 412
    default:
      break;
413 414 415 416
  }
  return NoChange();
}

417

418 419 420 421
Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
                                        Node* a) {
  node->ReplaceInput(0, a);
  node->TrimInputCount(1);
422
  NodeProperties::ChangeOp(node, op);
423 424 425 426 427 428 429 430 431
  return Changed(node);
}


Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
                                        Node* b) {
  node->ReplaceInput(0, a);
  node->ReplaceInput(1, b);
  node->TrimInputCount(2);
432
  NodeProperties::ChangeOp(node, op);
433 434 435
  return Changed(node);
}

436 437 438
}  // namespace compiler
}  // namespace internal
}  // namespace v8