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/compiler/js-graph.h"
8#include "src/compiler/node-properties.h"
9#include "src/compiler/simplified-operator.h"
10
11namespace v8 {
12namespace internal {
13namespace compiler {
14
15BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
16                                     Zone* zone)
17    : AdvancedReducer(editor),
18      jsgraph_(js_graph),
19      node_conditions_(zone, js_graph->graph()->NodeCount()),
20      zone_(zone),
21      dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {}
22
23BranchElimination::~BranchElimination() {}
24
25
26Reduction BranchElimination::Reduce(Node* node) {
27  switch (node->opcode()) {
28    case IrOpcode::kDead:
29      return NoChange();
30    case IrOpcode::kDeoptimizeIf:
31    case IrOpcode::kDeoptimizeUnless:
32      return ReduceDeoptimizeConditional(node);
33    case IrOpcode::kMerge:
34      return ReduceMerge(node);
35    case IrOpcode::kLoop:
36      return ReduceLoop(node);
37    case IrOpcode::kBranch:
38      return ReduceBranch(node);
39    case IrOpcode::kIfFalse:
40      return ReduceIf(node, false);
41    case IrOpcode::kIfTrue:
42      return ReduceIf(node, true);
43    case IrOpcode::kStart:
44      return ReduceStart(node);
45    default:
46      if (node->op()->ControlOutputCount() > 0) {
47        return ReduceOtherControl(node);
48      }
49      break;
50  }
51  return NoChange();
52}
53
54
55Reduction BranchElimination::ReduceBranch(Node* node) {
56  Node* condition = node->InputAt(0);
57  Node* control_input = NodeProperties::GetControlInput(node, 0);
58  const ControlPathConditions* from_input = node_conditions_.Get(control_input);
59  if (from_input != nullptr) {
60    Maybe<bool> condition_value = from_input->LookupCondition(condition);
61    // If we know the condition we can discard the branch.
62    if (condition_value.IsJust()) {
63      bool known_value = condition_value.FromJust();
64      for (Node* const use : node->uses()) {
65        switch (use->opcode()) {
66          case IrOpcode::kIfTrue:
67            Replace(use, known_value ? control_input : dead());
68            break;
69          case IrOpcode::kIfFalse:
70            Replace(use, known_value ? dead() : control_input);
71            break;
72          default:
73            UNREACHABLE();
74        }
75      }
76      return Replace(dead());
77    }
78  }
79  return TakeConditionsFromFirstControl(node);
80}
81
82Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
83  DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
84         node->opcode() == IrOpcode::kDeoptimizeUnless);
85  bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
86  Node* condition = NodeProperties::GetValueInput(node, 0);
87  Node* frame_state = NodeProperties::GetValueInput(node, 1);
88  Node* effect = NodeProperties::GetEffectInput(node);
89  Node* control = NodeProperties::GetControlInput(node);
90  ControlPathConditions const* conditions = node_conditions_.Get(control);
91  // If we do not know anything about the predecessor, do not propagate just
92  // yet because we will have to recompute anyway once we compute the
93  // predecessor.
94  if (conditions == nullptr) {
95    DCHECK_NULL(node_conditions_.Get(node));
96    return NoChange();
97  }
98  Maybe<bool> condition_value = conditions->LookupCondition(condition);
99  if (condition_value.IsJust()) {
100    // If we know the condition we can discard the branch.
101    if (condition_is_true == condition_value.FromJust()) {
102      // We don't update the conditions here, because we're replacing {node}
103      // with the {control} node that already contains the right information.
104      ReplaceWithValue(node, dead(), effect, control);
105    } else {
106      control = graph()->NewNode(common()->Deoptimize(DeoptimizeKind::kEager),
107                                 frame_state, effect, control);
108      // TODO(bmeurer): This should be on the AdvancedReducer somehow.
109      NodeProperties::MergeControlToEnd(graph(), common(), control);
110      Revisit(graph()->end());
111    }
112    return Replace(dead());
113  }
114  return UpdateConditions(
115      node, conditions->AddCondition(zone_, condition, condition_is_true));
116}
117
118Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
119  // Add the condition to the list arriving from the input branch.
120  Node* branch = NodeProperties::GetControlInput(node, 0);
121  const ControlPathConditions* from_branch = node_conditions_.Get(branch);
122  // If we do not know anything about the predecessor, do not propagate just
123  // yet because we will have to recompute anyway once we compute the
124  // predecessor.
125  if (from_branch == nullptr) {
126    DCHECK(node_conditions_.Get(node) == nullptr);
127    return NoChange();
128  }
129  Node* condition = branch->InputAt(0);
130  return UpdateConditions(
131      node, from_branch->AddCondition(zone_, condition, is_true_branch));
132}
133
134
135Reduction BranchElimination::ReduceLoop(Node* node) {
136  // Here we rely on having only reducible loops:
137  // The loop entry edge always dominates the header, so we can just use
138  // the information from the loop entry edge.
139  return TakeConditionsFromFirstControl(node);
140}
141
142
143Reduction BranchElimination::ReduceMerge(Node* node) {
144  // Shortcut for the case when we do not know anything about some
145  // input.
146  for (int i = 0; i < node->InputCount(); i++) {
147    if (node_conditions_.Get(node->InputAt(i)) == nullptr) {
148      DCHECK(node_conditions_.Get(node) == nullptr);
149      return NoChange();
150    }
151  }
152
153  const ControlPathConditions* first = node_conditions_.Get(node->InputAt(0));
154  // Make a copy of the first input's conditions and merge with the conditions
155  // from other inputs.
156  ControlPathConditions* conditions =
157      new (zone_->New(sizeof(ControlPathConditions)))
158          ControlPathConditions(*first);
159  for (int i = 1; i < node->InputCount(); i++) {
160    conditions->Merge(*(node_conditions_.Get(node->InputAt(i))));
161  }
162
163  return UpdateConditions(node, conditions);
164}
165
166
167Reduction BranchElimination::ReduceStart(Node* node) {
168  return UpdateConditions(node, ControlPathConditions::Empty(zone_));
169}
170
171
172const BranchElimination::ControlPathConditions*
173BranchElimination::PathConditionsForControlNodes::Get(Node* node) {
174  if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
175    return info_for_node_[node->id()];
176  }
177  return nullptr;
178}
179
180
181void BranchElimination::PathConditionsForControlNodes::Set(
182    Node* node, const ControlPathConditions* conditions) {
183  size_t index = static_cast<size_t>(node->id());
184  if (index >= info_for_node_.size()) {
185    info_for_node_.resize(index + 1, nullptr);
186  }
187  info_for_node_[index] = conditions;
188}
189
190
191Reduction BranchElimination::ReduceOtherControl(Node* node) {
192  DCHECK_EQ(1, node->op()->ControlInputCount());
193  return TakeConditionsFromFirstControl(node);
194}
195
196
197Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
198  // We just propagate the information from the control input (ideally,
199  // we would only revisit control uses if there is change).
200  const ControlPathConditions* from_input =
201      node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
202  return UpdateConditions(node, from_input);
203}
204
205
206Reduction BranchElimination::UpdateConditions(
207    Node* node, const ControlPathConditions* conditions) {
208  const ControlPathConditions* original = node_conditions_.Get(node);
209  // Only signal that the node has Changed if the condition information has
210  // changed.
211  if (conditions != original) {
212    if (original == nullptr || *conditions != *original) {
213      node_conditions_.Set(node, conditions);
214      return Changed(node);
215    }
216  }
217  return NoChange();
218}
219
220
221// static
222const BranchElimination::ControlPathConditions*
223BranchElimination::ControlPathConditions::Empty(Zone* zone) {
224  return new (zone->New(sizeof(ControlPathConditions)))
225      ControlPathConditions(nullptr, 0);
226}
227
228
229void BranchElimination::ControlPathConditions::Merge(
230    const ControlPathConditions& other) {
231  // Change the current condition list to a longest common tail
232  // of this condition list and the other list. (The common tail
233  // should correspond to the list from the common dominator.)
234
235  // First, we throw away the prefix of the longer list, so that
236  // we have lists of the same length.
237  size_t other_size = other.condition_count_;
238  BranchCondition* other_condition = other.head_;
239  while (other_size > condition_count_) {
240    other_condition = other_condition->next;
241    other_size--;
242  }
243  while (condition_count_ > other_size) {
244    head_ = head_->next;
245    condition_count_--;
246  }
247
248  // Then we go through both lists in lock-step until we find
249  // the common tail.
250  while (head_ != other_condition) {
251    DCHECK(condition_count_ > 0);
252    condition_count_--;
253    other_condition = other_condition->next;
254    head_ = head_->next;
255  }
256}
257
258
259const BranchElimination::ControlPathConditions*
260BranchElimination::ControlPathConditions::AddCondition(Zone* zone,
261                                                       Node* condition,
262                                                       bool is_true) const {
263  DCHECK(LookupCondition(condition).IsNothing());
264
265  BranchCondition* new_head = new (zone->New(sizeof(BranchCondition)))
266      BranchCondition(condition, is_true, head_);
267
268  ControlPathConditions* conditions =
269      new (zone->New(sizeof(ControlPathConditions)))
270          ControlPathConditions(new_head, condition_count_ + 1);
271  return conditions;
272}
273
274
275Maybe<bool> BranchElimination::ControlPathConditions::LookupCondition(
276    Node* condition) const {
277  for (BranchCondition* current = head_; current != nullptr;
278       current = current->next) {
279    if (current->condition == condition) {
280      return Just<bool>(current->is_true);
281    }
282  }
283  return Nothing<bool>();
284}
285
286
287bool BranchElimination::ControlPathConditions::operator==(
288    const ControlPathConditions& other) const {
289  if (condition_count_ != other.condition_count_) return false;
290  BranchCondition* this_condition = head_;
291  BranchCondition* other_condition = other.head_;
292  while (true) {
293    if (this_condition == other_condition) return true;
294    if (this_condition->condition != other_condition->condition ||
295        this_condition->is_true != other_condition->is_true) {
296      return false;
297    }
298    this_condition = this_condition->next;
299    other_condition = other_condition->next;
300  }
301  UNREACHABLE();
302  return false;
303}
304
305Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
306
307CommonOperatorBuilder* BranchElimination::common() const {
308  return jsgraph()->common();
309}
310
311}  // namespace compiler
312}  // namespace internal
313}  // namespace v8
314