branch-elimination.cc 14 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
    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);
45 46 47
    case IrOpcode::kTrapIf:
    case IrOpcode::kTrapUnless:
      return ReduceTrapConditional(node);
48 49 50 51 52 53 54 55 56 57 58
    case IrOpcode::kStart:
      return ReduceStart(node);
    default:
      if (node->op()->ControlOutputCount() > 0) {
        return ReduceOtherControl(node);
      }
      break;
  }
  return NoChange();
}

59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
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
77 78 79
  //    |       |                              /    |
  //   second_branch                    1  0  /     |
  //    /          \                     \ | /      |
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 124 125 126
  //   /            \                     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);
}
127 128 129 130

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

160 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 190 191 192 193 194 195
Reduction BranchElimination::ReduceTrapConditional(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kTrapIf ||
         node->opcode() == IrOpcode::kTrapUnless);
  bool trapping_condition = node->opcode() == IrOpcode::kTrapIf;
  Node* condition = node->InputAt(0);
  Node* control_input = NodeProperties::GetControlInput(node, 0);
  // 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.
  if (!reduced_.Get(control_input)) {
    return NoChange();
  }
  ControlPathConditions from_input = node_conditions_.Get(control_input);

  Node* branch;
  bool condition_value;

  if (from_input.LookupCondition(condition, &branch, &condition_value)) {
    if (condition_value == trapping_condition) {
      // This will always trap. Mark its outputs as dead and connect it to
      // graph()->end().
      ReplaceWithValue(node, dead(), dead(), dead());
      Node* effect = NodeProperties::GetEffectInput(node);
      Node* control = graph()->NewNode(common()->Throw(), effect, node);
      NodeProperties::MergeControlToEnd(graph(), common(), control);
      Revisit(graph()->end());
      return Changed(node);
    } else {
      // This will not trap, remove it.
      return Replace(control_input);
    }
  }
  return UpdateConditions(node, from_input, condition, node,
                          !trapping_condition);
}

196 197 198 199
Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
         node->opcode() == IrOpcode::kDeoptimizeUnless);
  bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
200
  DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
201 202 203 204 205 206 207
  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.
208 209
  if (!reduced_.Get(control)) {
    return NoChange();
210
  }
211 212

  ControlPathConditions conditions = node_conditions_.Get(control);
213 214
  bool condition_value;
  Node* branch;
215
  // If we know the condition we can discard the branch.
216
  if (conditions.LookupCondition(condition, &branch, &condition_value)) {
217
    MarkAsSafetyCheckIfNeeded(branch, node);
218
    if (condition_is_true == condition_value) {
219 220 221
      // 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);
222
    } else {
223
      control = graph()->NewNode(
224 225
          common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
          effect, control);
226 227 228 229
      // TODO(bmeurer): This should be on the AdvancedReducer somehow.
      NodeProperties::MergeControlToEnd(graph(), common(), control);
      Revisit(graph()->end());
    }
230
    return Replace(dead());
231
  }
232
  return UpdateConditions(node, conditions, condition, node, condition_is_true);
233
}
234 235 236 237

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);
238
  ControlPathConditions from_branch = node_conditions_.Get(branch);
239 240 241
  // 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.
242 243
  if (!reduced_.Get(branch)) {
    return NoChange();
244 245
  }
  Node* condition = branch->InputAt(0);
246
  return UpdateConditions(node, from_branch, condition, branch, is_true_branch);
247 248 249 250 251 252 253 254 255 256 257 258
}

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.
259 260
  Node::Inputs inputs = node->inputs();
  for (Node* input : inputs) {
261 262
    if (!reduced_.Get(input)) {
      return NoChange();
263 264 265
    }
  }

266 267 268 269
  auto input_it = inputs.begin();

  DCHECK_GT(inputs.count(), 0);

270
  ControlPathConditions conditions = node_conditions_.Get(*input_it);
271
  ++input_it;
272 273
  // Merge the first input's conditions with the conditions from the other
  // inputs.
274 275
  auto input_end = inputs.end();
  for (; input_it != input_end; ++input_it) {
276 277 278 279
    // 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));
280 281 282 283 284
  }
  return UpdateConditions(node, conditions);
}

Reduction BranchElimination::ReduceStart(Node* node) {
285
  return UpdateConditions(node, {});
286 287 288 289 290 291 292 293 294 295
}

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).
296 297 298
  Node* input = NodeProperties::GetControlInput(node, 0);
  if (!reduced_.Get(input)) return NoChange();
  return UpdateConditions(node, node_conditions_.Get(input));
299 300 301
}

Reduction BranchElimination::UpdateConditions(
302
    Node* node, ControlPathConditions conditions) {
303 304
  // Only signal that the node has Changed if the condition information has
  // changed.
305 306
  if (reduced_.Set(node, true) | node_conditions_.Set(node, conditions)) {
    return Changed(node);
307 308 309 310
  }
  return NoChange();
}

311
Reduction BranchElimination::UpdateConditions(
312
    Node* node, ControlPathConditions prev_conditions, Node* current_condition,
313
    Node* current_branch, bool is_true_branch) {
314
  ControlPathConditions original = node_conditions_.Get(node);
315
  // The control path for the node is the path obtained by appending the
316 317
  // current_condition to the prev_conditions. Use the original control path as
  // a hint to avoid allocations.
318 319
  prev_conditions.AddCondition(zone_, current_condition, current_branch,
                               is_true_branch, original);
320
  return UpdateConditions(node, prev_conditions);
321
}
322

323
void BranchElimination::ControlPathConditions::AddCondition(
324 325
    Zone* zone, Node* condition, Node* branch, bool is_true,
    ControlPathConditions hint) {
326 327 328 329 330 331 332 333 334 335 336
  if (!LookupCondition(condition)) {
    PushFront({condition, branch, is_true}, zone, hint);
  }
}

bool BranchElimination::ControlPathConditions::LookupCondition(
    Node* condition) const {
  for (BranchCondition element : *this) {
    if (element.condition == condition) return true;
  }
  return false;
337 338
}

339 340
bool BranchElimination::ControlPathConditions::LookupCondition(
    Node* condition, Node** branch, bool* is_true) const {
341
  for (BranchCondition element : *this) {
342 343 344 345 346 347 348
    if (element.condition == condition) {
      *is_true = element.is_true;
      *branch = element.branch;
      return true;
    }
  }
  return false;
349
}
350

351 352
void BranchElimination::MarkAsSafetyCheckIfNeeded(Node* branch, Node* node) {
  // Check if {branch} is dead because we might have a stale side-table entry.
353 354 355
  if (!branch->IsDead() && branch->opcode() != IrOpcode::kDead &&
      branch->opcode() != IrOpcode::kTrapIf &&
      branch->opcode() != IrOpcode::kTrapUnless) {
356 357 358 359 360 361 362 363 364 365
    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));
    }
  }
}

366
Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
367

368 369 370 371 372
Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); }

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

374 375 376
}  // namespace compiler
}  // namespace internal
}  // namespace v8