control-flow-optimizer.cc 4.08 KB
Newer Older
1 2 3 4 5 6
// Copyright 2015 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/control-flow-optimizer.h"

7
#include "src/codegen/tick-counter.h"
8 9
#include "src/compiler/common-operator.h"
#include "src/compiler/graph.h"
10 11 12 13 14 15 16
#include "src/compiler/node-matchers.h"
#include "src/compiler/node-properties.h"

namespace v8 {
namespace internal {
namespace compiler {

17 18 19
ControlFlowOptimizer::ControlFlowOptimizer(Graph* graph,
                                           CommonOperatorBuilder* common,
                                           MachineOperatorBuilder* machine,
20
                                           TickCounter* tick_counter,
21 22 23 24
                                           Zone* zone)
    : graph_(graph),
      common_(common),
      machine_(machine),
25
      queue_(zone),
26
      queued_(graph, 2),
27 28
      zone_(zone),
      tick_counter_(tick_counter) {}
29 30 31 32

void ControlFlowOptimizer::Optimize() {
  Enqueue(graph()->start());
  while (!queue_.empty()) {
33
    tick_counter_->DoTick();
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
    Node* node = queue_.front();
    queue_.pop();
    if (node->IsDead()) continue;
    switch (node->opcode()) {
      case IrOpcode::kBranch:
        VisitBranch(node);
        break;
      default:
        VisitNode(node);
        break;
    }
  }
}


void ControlFlowOptimizer::Enqueue(Node* node) {
  DCHECK_NOT_NULL(node);
  if (node->IsDead() || queued_.Get(node)) return;
  queued_.Set(node, true);
  queue_.push(node);
}


void ControlFlowOptimizer::VisitNode(Node* node) {
58 59 60 61
  for (Edge edge : node->use_edges()) {
    if (NodeProperties::IsControlEdge(edge)) {
      Enqueue(edge.from());
    }
62 63 64 65 66 67
  }
}


void ControlFlowOptimizer::VisitBranch(Node* node) {
  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
68 69 70 71 72 73 74
  if (TryBuildSwitch(node)) return;
  VisitNode(node);
}


bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
75 76

  Node* branch = node;
77
  if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
78
  Node* cond = NodeProperties::GetValueInput(branch, 0);
79
  if (cond->opcode() != IrOpcode::kWord32Equal) return false;
80 81
  Int32BinopMatcher m(cond);
  Node* index = m.left().node();
82
  if (!m.right().HasValue()) return false;
83 84 85 86 87 88
  int32_t value = m.right().Value();
  ZoneSet<int32_t> values(zone());
  values.insert(value);

  Node* if_false;
  Node* if_true;
89
  int32_t order = 1;
90
  while (true) {
91 92 93 94 95
    BranchMatcher matcher(branch);
    DCHECK(matcher.Matched());

    if_true = matcher.IfTrue();
    if_false = matcher.IfFalse();
96

97
    auto it = if_false->uses().begin();
98 99 100
    if (it == if_false->uses().end()) break;
    Node* branch1 = *it++;
    if (branch1->opcode() != IrOpcode::kBranch) break;
101
    if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
102 103 104 105 106 107 108 109 110 111 112
    if (it != if_false->uses().end()) break;
    Node* cond1 = branch1->InputAt(0);
    if (cond1->opcode() != IrOpcode::kWord32Equal) break;
    Int32BinopMatcher m1(cond1);
    if (m1.left().node() != index) break;
    if (!m1.right().HasValue()) break;
    int32_t value1 = m1.right().Value();
    if (values.find(value1) != values.end()) break;
    DCHECK_NE(value, value1);

    if (branch != node) {
113
      branch->NullAllInputs();
114 115
      if_true->ReplaceInput(0, node);
    }
116
    NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
117
    if_false->NullAllInputs();
118 119 120 121 122 123 124 125 126 127 128
    Enqueue(if_true);

    branch = branch1;
    value = value1;
    values.insert(value);
  }

  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
  if (branch == node) {
    DCHECK_EQ(1u, values.size());
129
    return false;
130
  }
131 132
  DCHECK_LT(1u, values.size());
  node->ReplaceInput(0, index);
133
  NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
134
  if_true->ReplaceInput(0, node);
135
  NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
136 137
  Enqueue(if_true);
  if_false->ReplaceInput(0, node);
138
  NodeProperties::ChangeOp(if_false, common()->IfDefault());
139
  Enqueue(if_false);
140
  branch->NullAllInputs();
141
  return true;
142 143 144 145 146
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8