1// Copyright 2015 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/branch-elimination.h"
6
7#include "src/base/small-vector.h"
8#include "src/compiler/compiler-source-position-table.h"
9#include "src/compiler/js-graph.h"
10#include "src/compiler/node-properties.h"
11#include "src/compiler/simplified-operator.h"
12
13namespace v8 {
14namespace internal {
15namespace compiler {
16
17BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
18                                     Zone* zone,
19                                     SourcePositionTable* source_positions,
20                                     Phase phase)
21    : AdvancedReducer(editor),
22      jsgraph_(js_graph),
23      node_conditions_(js_graph->graph()->NodeCount(), zone),
24      reduced_(js_graph->graph()->NodeCount(), zone),
25      zone_(zone),
26      source_positions_(source_positions),
27      dead_(js_graph->Dead()),
28      phase_(phase) {}
29
30BranchElimination::~BranchElimination() = default;
31
32Reduction BranchElimination::Reduce(Node* node) {
33  switch (node->opcode()) {
34    case IrOpcode::kDead:
35      return NoChange();
36    case IrOpcode::kDeoptimizeIf:
37    case IrOpcode::kDeoptimizeUnless:
38      return ReduceDeoptimizeConditional(node);
39    case IrOpcode::kMerge:
40      return ReduceMerge(node);
41    case IrOpcode::kLoop:
42      return ReduceLoop(node);
43    case IrOpcode::kBranch:
44      return ReduceBranch(node);
45    case IrOpcode::kIfFalse:
46      return ReduceIf(node, false);
47    case IrOpcode::kIfTrue:
48      return ReduceIf(node, true);
49    case IrOpcode::kTrapIf:
50    case IrOpcode::kTrapUnless:
51      return ReduceTrapConditional(node);
52    case IrOpcode::kStart:
53      return ReduceStart(node);
54    default:
55      if (node->op()->ControlOutputCount() > 0) {
56        return ReduceOtherControl(node);
57      }
58      break;
59  }
60  return NoChange();
61}
62
63void BranchElimination::SimplifyBranchCondition(Node* branch) {
64  // Try to use a phi as a branch condition if the control flow from the branch
65  // is known from previous branches. For example, in the graph below, the
66  // control flow of the second_branch is predictable because the first_branch
67  // use the same branch condition. In such case, create a new phi with constant
68  // inputs and let the second branch use the phi as its branch condition. From
69  // this transformation, more branch folding opportunities would be exposed to
70  // later passes through branch cloning in effect-control-linearizer.
71  //
72  // condition                             condition
73  //    |   \                                   |
74  //    |  first_branch                        first_branch
75  //    |   /          \                       /          \
76  //    |  /            \                     /            \
77  //    |first_true  first_false           first_true  first_false
78  //    |  \           /                      \           /
79  //    |   \         /                        \         /
80  //    |  first_merge           ==>          first_merge
81  //    |       |                              /    |
82  //   second_branch                    1  0  /     |
83  //    /          \                     \ | /      |
84  //   /            \                     phi       |
85  // second_true  second_false              \       |
86  //                                      second_branch
87  //                                      /          \
88  //                                     /            \
89  //                                   second_true  second_false
90  //
91
92  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
93  Node* merge = NodeProperties::GetControlInput(branch);
94  if (merge->opcode() != IrOpcode::kMerge) return;
95
96  Node* branch_condition = branch->InputAt(0);
97  Node* previous_branch;
98  bool condition_value;
99  Graph* graph = jsgraph()->graph();
100  base::SmallVector<Node*, 2> phi_inputs;
101
102  Node::Inputs inputs = merge->inputs();
103  int input_count = inputs.count();
104  for (int i = 0; i != input_count; ++i) {
105    Node* input = inputs[i];
106    ControlPathConditions from_input = node_conditions_.Get(input);
107    if (!from_input.LookupCondition(branch_condition, &previous_branch,
108                                    &condition_value)) {
109      return;
110    }
111
112    if (phase_ == kEARLY) {
113      phi_inputs.emplace_back(condition_value ? jsgraph()->TrueConstant()
114                                              : jsgraph()->FalseConstant());
115    } else {
116      phi_inputs.emplace_back(
117          condition_value
118              ? graph->NewNode(jsgraph()->common()->Int32Constant(1))
119              : graph->NewNode(jsgraph()->common()->Int32Constant(0)));
120    }
121  }
122  phi_inputs.emplace_back(merge);
123  Node* new_phi = graph->NewNode(
124      common()->Phi(phase_ == kEARLY ? MachineRepresentation::kTagged
125                                     : MachineRepresentation::kWord32,
126                    input_count),
127      input_count + 1, &phi_inputs.at(0));
128
129  // Replace the branch condition with the new phi.
130  NodeProperties::ReplaceValueInput(branch, new_phi, 0);
131}
132
133Reduction BranchElimination::ReduceBranch(Node* node) {
134  Node* condition = node->InputAt(0);
135  Node* control_input = NodeProperties::GetControlInput(node, 0);
136  if (!reduced_.Get(control_input)) return NoChange();
137  ControlPathConditions from_input = node_conditions_.Get(control_input);
138  Node* branch;
139  bool condition_value;
140  // If we know the condition we can discard the branch.
141  if (from_input.LookupCondition(condition, &branch, &condition_value)) {
142    for (Node* const use : node->uses()) {
143      switch (use->opcode()) {
144        case IrOpcode::kIfTrue:
145          Replace(use, condition_value ? control_input : dead());
146          break;
147        case IrOpcode::kIfFalse:
148          Replace(use, condition_value ? dead() : control_input);
149          break;
150        default:
151          UNREACHABLE();
152      }
153    }
154    return Replace(dead());
155  }
156  SimplifyBranchCondition(node);
157  // Trigger revisits of the IfTrue/IfFalse projections, since they depend on
158  // the branch condition.
159  for (Node* const use : node->uses()) {
160    Revisit(use);
161  }
162  return TakeConditionsFromFirstControl(node);
163}
164
165// Simplify a trap following a merge.
166// Assuming condition is in control1's path conditions, and !condition is in
167// control2's path condtions, the following transformation takes place:
168//
169//            control1 control2     condition  effect1
170//                  \   /                   \ /  |
171//                  Merge                    X   |   control1
172//                    |                     / \  |   /
173//   effect1  effect2 |                    |   TrapIf     control2
174//         \     |   /|         ==>        |         \    /
175//          EffectPhi |                    | effect2  Merge
176//              |    /                     |    |     /
177//   condition  |   /                       \   |    /
178//          \   |  /                        EffectPhi
179//           TrapIf
180// TODO(manoskouk): We require that the trap's effect input is the Merge's
181// EffectPhi, so we can ensure that the new traps' effect inputs are not
182// dominated by the Merge. Can we relax this?
183bool BranchElimination::TryPullTrapIntoMerge(Node* node) {
184  DCHECK(node->opcode() == IrOpcode::kTrapIf ||
185         node->opcode() == IrOpcode::kTrapUnless);
186  Node* merge = NodeProperties::GetControlInput(node);
187  DCHECK_EQ(merge->opcode(), IrOpcode::kMerge);
188  Node* condition = NodeProperties::GetValueInput(node, 0);
189  Node* effect_input = NodeProperties::GetEffectInput(node);
190  if (!(effect_input->opcode() == IrOpcode::kEffectPhi &&
191        NodeProperties::GetControlInput(effect_input) == merge)) {
192    return false;
193  }
194
195  bool trapping_condition = node->opcode() == IrOpcode::kTrapIf;
196  base::SmallVector<Node*, 8> new_merge_inputs;
197  for (Edge edge : merge->input_edges()) {
198    Node* input = edge.to();
199    ControlPathConditions from_input = node_conditions_.Get(input);
200    Node* previous_branch;
201    bool condition_value;
202    if (!from_input.LookupCondition(condition, &previous_branch,
203                                    &condition_value)) {
204      return false;
205    }
206    if (condition_value == trapping_condition) {
207      Node* inputs[] = {
208          condition, NodeProperties::GetEffectInput(effect_input, edge.index()),
209          input};
210      Node* trap_clone = graph()->NewNode(node->op(), 3, inputs);
211      if (source_positions_) {
212        source_positions_->SetSourcePosition(
213            trap_clone, source_positions_->GetSourcePosition(node));
214      }
215      new_merge_inputs.emplace_back(trap_clone);
216    } else {
217      new_merge_inputs.emplace_back(input);
218    }
219  }
220
221  for (int i = 0; i < merge->InputCount(); i++) {
222    merge->ReplaceInput(i, new_merge_inputs[i]);
223  }
224  ReplaceWithValue(node, dead(), dead(), merge);
225  node->Kill();
226  Revisit(merge);
227
228  return true;
229}
230
231Reduction BranchElimination::ReduceTrapConditional(Node* node) {
232  DCHECK(node->opcode() == IrOpcode::kTrapIf ||
233         node->opcode() == IrOpcode::kTrapUnless);
234  bool trapping_condition = node->opcode() == IrOpcode::kTrapIf;
235  Node* condition = node->InputAt(0);
236  Node* control_input = NodeProperties::GetControlInput(node, 0);
237  // If we do not know anything about the predecessor, do not propagate just
238  // yet because we will have to recompute anyway once we compute the
239  // predecessor.
240  if (!reduced_.Get(control_input)) return NoChange();
241
242  // If the trap comes directly after a merge, pull it into the merge. This will
243  // unlock other optimizations later.
244  if (control_input->opcode() == IrOpcode::kMerge &&
245      TryPullTrapIntoMerge(node)) {
246    return Replace(dead());
247  }
248
249  ControlPathConditions from_input = node_conditions_.Get(control_input);
250  Node* previous_branch;
251  bool condition_value;
252
253  if (from_input.LookupCondition(condition, &previous_branch,
254                                 &condition_value)) {
255    if (condition_value == trapping_condition) {
256      // Special case: Trap directly inside a branch without sibling nodes.
257      // Replace the branch with the trap.
258      //    condition  control              condition  control
259      //     |   \      /                        \      /
260      //     |    Branch                          TrapIf
261      //     |    /    \            ==>             |
262      //     |  IfTrue IfFalse                 <subgraph2>
263      //     |  /        |
264      //    TrapIf   <subraph2>            Dead
265      //      |                              |
266      //   <subgraph1>                     <subgraph1>
267      // (and symmetrically for TrapUnless.)
268      if (((trapping_condition &&
269            control_input->opcode() == IrOpcode::kIfTrue) ||
270           (!trapping_condition &&
271            control_input->opcode() == IrOpcode::kIfFalse)) &&
272          control_input->UseCount() == 1) {
273        Node* branch = NodeProperties::GetControlInput(control_input);
274        DCHECK_EQ(branch->opcode(), IrOpcode::kBranch);
275        if (condition == NodeProperties::GetValueInput(branch, 0)) {
276          Node* other_if_branch = nullptr;
277          for (Node* use : branch->uses()) {
278            if (use != control_input) other_if_branch = use;
279          }
280          DCHECK_NOT_NULL(other_if_branch);
281
282          node->ReplaceInput(NodeProperties::FirstControlIndex(node),
283                             NodeProperties::GetControlInput(branch));
284          ReplaceWithValue(node, dead(), dead(), dead());
285          ReplaceWithValue(other_if_branch, node, node, node);
286          other_if_branch->Kill();
287          control_input->Kill();
288          branch->Kill();
289          return Changed(node);
290        }
291      }
292
293      // General case: This will always trap. Mark its outputs as dead and
294      // connect it to graph()->end().
295      ReplaceWithValue(node, dead(), dead(), dead());
296      Node* effect = NodeProperties::GetEffectInput(node);
297      Node* control = graph()->NewNode(common()->Throw(), effect, node);
298      NodeProperties::MergeControlToEnd(graph(), common(), control);
299      Revisit(graph()->end());
300      return Changed(node);
301    } else {
302      // This will not trap, remove it.
303      return Replace(control_input);
304    }
305  }
306  return UpdateConditions(node, from_input, condition, node,
307                          !trapping_condition, false);
308}
309
310Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
311  DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
312         node->opcode() == IrOpcode::kDeoptimizeUnless);
313  bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
314  DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
315  Node* condition = NodeProperties::GetValueInput(node, 0);
316  Node* frame_state = NodeProperties::GetValueInput(node, 1);
317  Node* effect = NodeProperties::GetEffectInput(node);
318  Node* control = NodeProperties::GetControlInput(node);
319  // If we do not know anything about the predecessor, do not propagate just
320  // yet because we will have to recompute anyway once we compute the
321  // predecessor.
322  if (!reduced_.Get(control)) {
323    return NoChange();
324  }
325
326  ControlPathConditions conditions = node_conditions_.Get(control);
327  bool condition_value;
328  Node* branch;
329  // If we know the condition we can discard the branch.
330  if (conditions.LookupCondition(condition, &branch, &condition_value)) {
331    if (condition_is_true == condition_value) {
332      // We don't update the conditions here, because we're replacing {node}
333      // with the {control} node that already contains the right information.
334      ReplaceWithValue(node, dead(), effect, control);
335    } else {
336      control = graph()->NewNode(common()->Deoptimize(p.reason(), p.feedback()),
337                                 frame_state, effect, control);
338      // TODO(bmeurer): This should be on the AdvancedReducer somehow.
339      NodeProperties::MergeControlToEnd(graph(), common(), control);
340      Revisit(graph()->end());
341    }
342    return Replace(dead());
343  }
344  return UpdateConditions(node, conditions, condition, node, condition_is_true,
345                          false);
346}
347
348Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
349  // Add the condition to the list arriving from the input branch.
350  Node* branch = NodeProperties::GetControlInput(node, 0);
351  ControlPathConditions from_branch = node_conditions_.Get(branch);
352  // If we do not know anything about the predecessor, do not propagate just
353  // yet because we will have to recompute anyway once we compute the
354  // predecessor.
355  if (!reduced_.Get(branch)) {
356    return NoChange();
357  }
358  Node* condition = branch->InputAt(0);
359  return UpdateConditions(node, from_branch, condition, branch, is_true_branch,
360                          true);
361}
362
363Reduction BranchElimination::ReduceLoop(Node* node) {
364  // Here we rely on having only reducible loops:
365  // The loop entry edge always dominates the header, so we can just use
366  // the information from the loop entry edge.
367  return TakeConditionsFromFirstControl(node);
368}
369
370Reduction BranchElimination::ReduceMerge(Node* node) {
371  // Shortcut for the case when we do not know anything about some
372  // input.
373  Node::Inputs inputs = node->inputs();
374  for (Node* input : inputs) {
375    if (!reduced_.Get(input)) {
376      return NoChange();
377    }
378  }
379
380  auto input_it = inputs.begin();
381
382  DCHECK_GT(inputs.count(), 0);
383
384  ControlPathConditions conditions = node_conditions_.Get(*input_it);
385  ++input_it;
386  // Merge the first input's conditions with the conditions from the other
387  // inputs.
388  auto input_end = inputs.end();
389  for (; input_it != input_end; ++input_it) {
390    // Change the current condition block list to a longest common tail of this
391    // condition list and the other list. (The common tail should correspond to
392    // the list from the common dominator.)
393    conditions.ResetToCommonAncestor(node_conditions_.Get(*input_it));
394  }
395  return UpdateConditions(node, conditions);
396}
397
398Reduction BranchElimination::ReduceStart(Node* node) {
399  return UpdateConditions(node, ControlPathConditions(zone_));
400}
401
402Reduction BranchElimination::ReduceOtherControl(Node* node) {
403  DCHECK_EQ(1, node->op()->ControlInputCount());
404  return TakeConditionsFromFirstControl(node);
405}
406
407Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
408  // We just propagate the information from the control input (ideally,
409  // we would only revisit control uses if there is change).
410  Node* input = NodeProperties::GetControlInput(node, 0);
411  if (!reduced_.Get(input)) return NoChange();
412  return UpdateConditions(node, node_conditions_.Get(input));
413}
414
415Reduction BranchElimination::UpdateConditions(
416    Node* node, ControlPathConditions conditions) {
417  // Only signal that the node has Changed if the condition information has
418  // changed.
419  bool reduced_changed = reduced_.Set(node, true);
420  bool node_conditions_changed = node_conditions_.Set(node, conditions);
421  if (reduced_changed || node_conditions_changed) {
422    return Changed(node);
423  }
424  return NoChange();
425}
426
427Reduction BranchElimination::UpdateConditions(
428    Node* node, ControlPathConditions prev_conditions, Node* current_condition,
429    Node* current_branch, bool is_true_branch, bool in_new_block) {
430  // The control path for the node is the path obtained by appending the
431  // current_condition to the prev_conditions. Use the original control path as
432  // a hint to avoid allocations.
433  if (in_new_block || prev_conditions.blocks_.Size() == 0) {
434    prev_conditions.AddConditionInNewBlock(zone_, current_condition,
435                                           current_branch, is_true_branch);
436  } else {
437    ControlPathConditions original = node_conditions_.Get(node);
438    prev_conditions.AddCondition(zone_, current_condition, current_branch,
439                                 is_true_branch, original);
440  }
441  return UpdateConditions(node, prev_conditions);
442}
443
444void BranchElimination::ControlPathConditions::AddCondition(
445    Zone* zone, Node* condition, Node* branch, bool is_true,
446    ControlPathConditions hint) {
447  if (!LookupCondition(condition)) {
448    BranchCondition branch_condition(condition, branch, is_true);
449    FunctionalList<BranchCondition> prev_front = blocks_.Front();
450    if (hint.blocks_.Size() > 0) {
451      prev_front.PushFront(branch_condition, zone, hint.blocks_.Front());
452    } else {
453      prev_front.PushFront(branch_condition, zone);
454    }
455    blocks_.DropFront();
456    blocks_.PushFront(prev_front, zone);
457    conditions_.Set(condition, branch_condition);
458    SLOW_DCHECK(BlocksAndConditionsInvariant());
459  }
460}
461
462void BranchElimination::ControlPathConditions::AddConditionInNewBlock(
463    Zone* zone, Node* condition, Node* branch, bool is_true) {
464  FunctionalList<BranchCondition> new_block;
465  if (!LookupCondition(condition)) {
466    BranchCondition branch_condition(condition, branch, is_true);
467    new_block.PushFront(branch_condition, zone);
468    conditions_.Set(condition, branch_condition);
469  }
470  blocks_.PushFront(new_block, zone);
471  SLOW_DCHECK(BlocksAndConditionsInvariant());
472}
473
474bool BranchElimination::ControlPathConditions::LookupCondition(
475    Node* condition) const {
476  return conditions_.Get(condition).IsSet();
477}
478
479bool BranchElimination::ControlPathConditions::LookupCondition(
480    Node* condition, Node** branch, bool* is_true) const {
481  const BranchCondition& element = conditions_.Get(condition);
482  if (element.IsSet()) {
483    *is_true = element.is_true;
484    *branch = element.branch;
485    return true;
486  }
487  return false;
488}
489
490void BranchElimination::ControlPathConditions::ResetToCommonAncestor(
491    ControlPathConditions other) {
492  while (other.blocks_.Size() > blocks_.Size()) other.blocks_.DropFront();
493  while (blocks_.Size() > other.blocks_.Size()) {
494    for (BranchCondition branch_condition : blocks_.Front()) {
495      conditions_.Set(branch_condition.condition, {});
496    }
497    blocks_.DropFront();
498  }
499  while (blocks_ != other.blocks_) {
500    for (BranchCondition branch_condition : blocks_.Front()) {
501      conditions_.Set(branch_condition.condition, {});
502    }
503    blocks_.DropFront();
504    other.blocks_.DropFront();
505  }
506  SLOW_DCHECK(BlocksAndConditionsInvariant());
507}
508
509#if DEBUG
510bool BranchElimination::ControlPathConditions::BlocksAndConditionsInvariant() {
511  PersistentMap<Node*, BranchCondition> conditions_copy(conditions_);
512  for (auto block : blocks_) {
513    for (BranchCondition condition : block) {
514      // Every element of blocks_ has to be in conditions_.
515      if (conditions_copy.Get(condition.condition) != condition) return false;
516      conditions_copy.Set(condition.condition, {});
517    }
518  }
519  // Every element of {conditions_} has to be in {blocks_}. We removed all
520  // elements of blocks_ from condition_copy, so if it is not empty, the
521  // invariant fails.
522  return conditions_copy.begin() == conditions_copy.end();
523}
524#endif
525
526Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
527
528Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); }
529
530CommonOperatorBuilder* BranchElimination::common() const {
531  return jsgraph()->common();
532}
533
534}  // namespace compiler
535}  // namespace internal
536}  // namespace v8
537