branch-elimination.cc 12.2 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/branch-elimination.h"

7
#include "src/base/small-vector.h"
8 9 10 11 12 13 14 15 16
#include "src/compiler/js-graph.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/simplified-operator.h"

namespace v8 {
namespace internal {
namespace compiler {

BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
17
                                     Zone* zone, Phase phase)
18
    : AdvancedReducer(editor),
19
      jsgraph_(js_graph),
20 21
      node_conditions_(js_graph->graph()->NodeCount(), zone),
      reduced_(js_graph->graph()->NodeCount(), zone),
22
      zone_(zone),
23 24
      dead_(js_graph->Dead()),
      phase_(phase) {}
25

26
BranchElimination::~BranchElimination() = default;
27 28 29 30 31

Reduction BranchElimination::Reduce(Node* node) {
  switch (node->opcode()) {
    case IrOpcode::kDead:
      return NoChange();
32 33 34
    case IrOpcode::kDeoptimizeIf:
    case IrOpcode::kDeoptimizeUnless:
      return ReduceDeoptimizeConditional(node);
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
    case IrOpcode::kMerge:
      return ReduceMerge(node);
    case IrOpcode::kLoop:
      return ReduceLoop(node);
    case IrOpcode::kBranch:
      return ReduceBranch(node);
    case IrOpcode::kIfFalse:
      return ReduceIf(node, false);
    case IrOpcode::kIfTrue:
      return ReduceIf(node, true);
    case IrOpcode::kStart:
      return ReduceStart(node);
    default:
      if (node->op()->ControlOutputCount() > 0) {
        return ReduceOtherControl(node);
      }
      break;
  }
  return NoChange();
}

56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
void BranchElimination::SimplifyBranchCondition(Node* branch) {
  // Try to use a phi as a branch condition if the control flow from the branch
  // is known from previous branches. For example, in the graph below, the
  // control flow of the second_branch is predictable because the first_branch
  // use the same branch condition. In such case, create a new phi with constant
  // inputs and let the second branch use the phi as its branch condition. From
  // this transformation, more branch folding opportunities would be exposed to
  // later passes through branch cloning in effect-control-linearizer.
  //
  // condition                             condition
  //    |   \                                   |
  //    |  first_branch                        first_branch
  //    |   /          \                       /          \
  //    |  /            \                     /            \
  //    |first_true  first_false           first_true  first_false
  //    |  \           /                      \           /
  //    |   \         /                        \         /
  //    |  first_merge           ==>          first_merge
  //    |       |                                   |
  //   second_branch                    1    0      |
  //    /          \                     \  /       |
  //   /            \                     phi       |
  // second_true  second_false              \       |
  //                                      second_branch
  //                                      /          \
  //                                     /            \
  //                                   second_true  second_false
  //

  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
  Node* merge = NodeProperties::GetControlInput(branch);
  if (merge->opcode() != IrOpcode::kMerge) return;

  Node* branch_condition = branch->InputAt(0);
  Node* previous_branch;
  bool condition_value;
  Graph* graph = jsgraph()->graph();
  base::SmallVector<Node*, 2> phi_inputs;

  Node::Inputs inputs = merge->inputs();
  int input_count = inputs.count();
  for (int i = 0; i != input_count; ++i) {
    Node* input = inputs[i];
    ControlPathConditions from_input = node_conditions_.Get(input);
    if (!from_input.LookupCondition(branch_condition, &previous_branch,
                                    &condition_value))
      return;

    if (phase_ == kEARLY) {
      phi_inputs.emplace_back(condition_value ? jsgraph()->TrueConstant()
                                              : jsgraph()->FalseConstant());
    } else {
      phi_inputs.emplace_back(
          condition_value
              ? graph->NewNode(jsgraph()->common()->Int32Constant(1))
              : graph->NewNode(jsgraph()->common()->Int32Constant(0)));
    }
  }
  phi_inputs.emplace_back(merge);
  Node* new_phi = graph->NewNode(
      common()->Phi(phase_ == kEARLY ? MachineRepresentation::kTagged
                                     : MachineRepresentation::kWord32,
                    input_count),
      input_count + 1, &phi_inputs.at(0));

  // Replace the branch condition with the new phi.
  NodeProperties::ReplaceValueInput(branch, new_phi, 0);
}
124 125 126 127

Reduction BranchElimination::ReduceBranch(Node* node) {
  Node* condition = node->InputAt(0);
  Node* control_input = NodeProperties::GetControlInput(node, 0);
128
  ControlPathConditions from_input = node_conditions_.Get(control_input);
129 130
  Node* branch;
  bool condition_value;
131
  // If we know the condition we can discard the branch.
132
  if (from_input.LookupCondition(condition, &branch, &condition_value)) {
133
    MarkAsSafetyCheckIfNeeded(branch, node);
134 135 136
    for (Node* const use : node->uses()) {
      switch (use->opcode()) {
        case IrOpcode::kIfTrue:
137
          Replace(use, condition_value ? control_input : dead());
138 139
          break;
        case IrOpcode::kIfFalse:
140
          Replace(use, condition_value ? dead() : control_input);
141 142 143
          break;
        default:
          UNREACHABLE();
144 145
      }
    }
146
    return Replace(dead());
147
  }
148
  SimplifyBranchCondition(node);
149 150 151 152 153
  // Trigger revisits of the IfTrue/IfFalse projections, since they depend on
  // the branch condition.
  for (Node* const use : node->uses()) {
    Revisit(use);
  }
154 155 156
  return TakeConditionsFromFirstControl(node);
}

157 158 159 160
Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
         node->opcode() == IrOpcode::kDeoptimizeUnless);
  bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
161
  DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
162 163 164 165 166 167 168
  Node* condition = NodeProperties::GetValueInput(node, 0);
  Node* frame_state = NodeProperties::GetValueInput(node, 1);
  Node* effect = NodeProperties::GetEffectInput(node);
  Node* control = NodeProperties::GetControlInput(node);
  // If we do not know anything about the predecessor, do not propagate just
  // yet because we will have to recompute anyway once we compute the
  // predecessor.
169 170
  if (!reduced_.Get(control)) {
    return NoChange();
171
  }
172 173

  ControlPathConditions conditions = node_conditions_.Get(control);
174 175
  bool condition_value;
  Node* branch;
176
  // If we know the condition we can discard the branch.
177
  if (conditions.LookupCondition(condition, &branch, &condition_value)) {
178
    MarkAsSafetyCheckIfNeeded(branch, node);
179
    if (condition_is_true == condition_value) {
180 181 182
      // We don't update the conditions here, because we're replacing {node}
      // with the {control} node that already contains the right information.
      ReplaceWithValue(node, dead(), effect, control);
183
    } else {
184
      control = graph()->NewNode(
185 186
          common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
          effect, control);
187 188 189 190
      // TODO(bmeurer): This should be on the AdvancedReducer somehow.
      NodeProperties::MergeControlToEnd(graph(), common(), control);
      Revisit(graph()->end());
    }
191
    return Replace(dead());
192
  }
193
  return UpdateConditions(node, conditions, condition, node, condition_is_true);
194
}
195 196 197 198

Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
  // Add the condition to the list arriving from the input branch.
  Node* branch = NodeProperties::GetControlInput(node, 0);
199
  ControlPathConditions from_branch = node_conditions_.Get(branch);
200 201 202
  // If we do not know anything about the predecessor, do not propagate just
  // yet because we will have to recompute anyway once we compute the
  // predecessor.
203 204
  if (!reduced_.Get(branch)) {
    return NoChange();
205 206
  }
  Node* condition = branch->InputAt(0);
207
  return UpdateConditions(node, from_branch, condition, branch, is_true_branch);
208 209 210 211 212 213 214 215 216 217 218 219
}

Reduction BranchElimination::ReduceLoop(Node* node) {
  // Here we rely on having only reducible loops:
  // The loop entry edge always dominates the header, so we can just use
  // the information from the loop entry edge.
  return TakeConditionsFromFirstControl(node);
}

Reduction BranchElimination::ReduceMerge(Node* node) {
  // Shortcut for the case when we do not know anything about some
  // input.
220 221
  Node::Inputs inputs = node->inputs();
  for (Node* input : inputs) {
222 223
    if (!reduced_.Get(input)) {
      return NoChange();
224 225 226
    }
  }

227 228 229 230
  auto input_it = inputs.begin();

  DCHECK_GT(inputs.count(), 0);

231
  ControlPathConditions conditions = node_conditions_.Get(*input_it);
232
  ++input_it;
233 234
  // Merge the first input's conditions with the conditions from the other
  // inputs.
235 236
  auto input_end = inputs.end();
  for (; input_it != input_end; ++input_it) {
237 238 239 240
    // Change the current condition list to a longest common tail
    // of this condition list and the other list. (The common tail
    // should correspond to the list from the common dominator.)
    conditions.ResetToCommonAncestor(node_conditions_.Get(*input_it));
241 242 243 244 245
  }
  return UpdateConditions(node, conditions);
}

Reduction BranchElimination::ReduceStart(Node* node) {
246
  return UpdateConditions(node, {});
247 248 249 250 251 252 253 254 255 256
}

Reduction BranchElimination::ReduceOtherControl(Node* node) {
  DCHECK_EQ(1, node->op()->ControlInputCount());
  return TakeConditionsFromFirstControl(node);
}

Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
  // We just propagate the information from the control input (ideally,
  // we would only revisit control uses if there is change).
257 258 259
  Node* input = NodeProperties::GetControlInput(node, 0);
  if (!reduced_.Get(input)) return NoChange();
  return UpdateConditions(node, node_conditions_.Get(input));
260 261 262
}

Reduction BranchElimination::UpdateConditions(
263
    Node* node, ControlPathConditions conditions) {
264 265
  // Only signal that the node has Changed if the condition information has
  // changed.
266 267
  if (reduced_.Set(node, true) | node_conditions_.Set(node, conditions)) {
    return Changed(node);
268 269 270 271
  }
  return NoChange();
}

272
Reduction BranchElimination::UpdateConditions(
273
    Node* node, ControlPathConditions prev_conditions, Node* current_condition,
274
    Node* current_branch, bool is_true_branch) {
275
  ControlPathConditions original = node_conditions_.Get(node);
276
  // The control path for the node is the path obtained by appending the
277 278
  // current_condition to the prev_conditions. Use the original control path as
  // a hint to avoid allocations.
279 280
  prev_conditions.AddCondition(zone_, current_condition, current_branch,
                               is_true_branch, original);
281
  return UpdateConditions(node, prev_conditions);
282
}
283

284
void BranchElimination::ControlPathConditions::AddCondition(
285 286
    Zone* zone, Node* condition, Node* branch, bool is_true,
    ControlPathConditions hint) {
287
  DCHECK(!LookupCondition(condition, nullptr, nullptr));
288
  PushFront({condition, branch, is_true}, zone, hint);
289 290
}

291 292
bool BranchElimination::ControlPathConditions::LookupCondition(
    Node* condition, Node** branch, bool* is_true) const {
293
  for (BranchCondition element : *this) {
294 295 296 297 298 299 300
    if (element.condition == condition) {
      *is_true = element.is_true;
      *branch = element.branch;
      return true;
    }
  }
  return false;
301
}
302

303 304 305 306 307 308 309 310 311 312 313 314 315
void BranchElimination::MarkAsSafetyCheckIfNeeded(Node* branch, Node* node) {
  // Check if {branch} is dead because we might have a stale side-table entry.
  if (!branch->IsDead() && branch->opcode() != IrOpcode::kDead) {
    IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
    IsSafetyCheck combined_safety =
        CombineSafetyChecks(branch_safety, IsSafetyCheckOf(node->op()));
    if (branch_safety != combined_safety) {
      NodeProperties::ChangeOp(
          branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
    }
  }
}

316
Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
317

318 319 320 321 322
Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); }

CommonOperatorBuilder* BranchElimination::common() const {
  return jsgraph()->common();
}
323

324 325 326
}  // namespace compiler
}  // namespace internal
}  // namespace v8