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
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14
BranchElimination(Editor * editor,JSGraph * js_graph,Zone * zone)15 BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
16 Zone* zone)
17 : AdvancedReducer(editor),
18 jsgraph_(js_graph),
19 node_conditions_(js_graph->graph()->NodeCount(), zone),
20 reduced_(js_graph->graph()->NodeCount(), zone),
21 zone_(zone),
22 dead_(js_graph->Dead()) {}
23
~BranchElimination()24 BranchElimination::~BranchElimination() {}
25
26
Reduce(Node * node)27 Reduction BranchElimination::Reduce(Node* node) {
28 switch (node->opcode()) {
29 case IrOpcode::kDead:
30 return NoChange();
31 case IrOpcode::kDeoptimizeIf:
32 case IrOpcode::kDeoptimizeUnless:
33 return ReduceDeoptimizeConditional(node);
34 case IrOpcode::kMerge:
35 return ReduceMerge(node);
36 case IrOpcode::kLoop:
37 return ReduceLoop(node);
38 case IrOpcode::kBranch:
39 return ReduceBranch(node);
40 case IrOpcode::kIfFalse:
41 return ReduceIf(node, false);
42 case IrOpcode::kIfTrue:
43 return ReduceIf(node, true);
44 case IrOpcode::kStart:
45 return ReduceStart(node);
46 default:
47 if (node->op()->ControlOutputCount() > 0) {
48 return ReduceOtherControl(node);
49 }
50 break;
51 }
52 return NoChange();
53 }
54
55
ReduceBranch(Node * node)56 Reduction BranchElimination::ReduceBranch(Node* node) {
57 Node* condition = node->InputAt(0);
58 Node* control_input = NodeProperties::GetControlInput(node, 0);
59 ControlPathConditions from_input = node_conditions_.Get(control_input);
60 Node* branch;
61 bool condition_value;
62 // If we know the condition we can discard the branch.
63 if (from_input.LookupCondition(condition, &branch, &condition_value)) {
64 // Mark the branch as a safety check if necessary.
65 // Check if {branch} is dead because we might have a stale side-table entry.
66 if (!branch->IsDead()) {
67 IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
68 IsSafetyCheck combined_safety =
69 CombineSafetyChecks(branch_safety, IsSafetyCheckOf(node->op()));
70 if (branch_safety != combined_safety) {
71 NodeProperties::ChangeOp(
72 branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
73 }
74 }
75
76 for (Node* const use : node->uses()) {
77 switch (use->opcode()) {
78 case IrOpcode::kIfTrue:
79 Replace(use, condition_value ? control_input : dead());
80 break;
81 case IrOpcode::kIfFalse:
82 Replace(use, condition_value ? dead() : control_input);
83 break;
84 default:
85 UNREACHABLE();
86 }
87 }
88 return Replace(dead());
89 }
90 return TakeConditionsFromFirstControl(node);
91 }
92
ReduceDeoptimizeConditional(Node * node)93 Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
94 DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
95 node->opcode() == IrOpcode::kDeoptimizeUnless);
96 bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
97 DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
98 Node* condition = NodeProperties::GetValueInput(node, 0);
99 Node* frame_state = NodeProperties::GetValueInput(node, 1);
100 Node* effect = NodeProperties::GetEffectInput(node);
101 Node* control = NodeProperties::GetControlInput(node);
102 // If we do not know anything about the predecessor, do not propagate just
103 // yet because we will have to recompute anyway once we compute the
104 // predecessor.
105 if (!reduced_.Get(control)) {
106 return NoChange();
107 }
108
109 ControlPathConditions conditions = node_conditions_.Get(control);
110 bool condition_value;
111 Node* branch;
112 if (conditions.LookupCondition(condition, &branch, &condition_value)) {
113 // Mark the branch as a safety check.
114 IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
115 IsSafetyCheck combined_safety =
116 CombineSafetyChecks(branch_safety, p.is_safety_check());
117 if (branch_safety != combined_safety) {
118 NodeProperties::ChangeOp(
119 branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
120 }
121
122 // If we know the condition we can discard the branch.
123 if (condition_is_true == condition_value) {
124 // We don't update the conditions here, because we're replacing {node}
125 // with the {control} node that already contains the right information.
126 ReplaceWithValue(node, dead(), effect, control);
127 } else {
128 control = graph()->NewNode(
129 common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
130 effect, control);
131 // TODO(bmeurer): This should be on the AdvancedReducer somehow.
132 NodeProperties::MergeControlToEnd(graph(), common(), control);
133 Revisit(graph()->end());
134 }
135 return Replace(dead());
136 }
137 return UpdateConditions(node, conditions, condition, node, condition_is_true);
138 }
139
ReduceIf(Node * node,bool is_true_branch)140 Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
141 // Add the condition to the list arriving from the input branch.
142 Node* branch = NodeProperties::GetControlInput(node, 0);
143 ControlPathConditions from_branch = node_conditions_.Get(branch);
144 // If we do not know anything about the predecessor, do not propagate just
145 // yet because we will have to recompute anyway once we compute the
146 // predecessor.
147 if (!reduced_.Get(branch)) {
148 return NoChange();
149 }
150 Node* condition = branch->InputAt(0);
151 return UpdateConditions(node, from_branch, condition, branch, is_true_branch);
152 }
153
154
ReduceLoop(Node * node)155 Reduction BranchElimination::ReduceLoop(Node* node) {
156 // Here we rely on having only reducible loops:
157 // The loop entry edge always dominates the header, so we can just use
158 // the information from the loop entry edge.
159 return TakeConditionsFromFirstControl(node);
160 }
161
162
ReduceMerge(Node * node)163 Reduction BranchElimination::ReduceMerge(Node* node) {
164 // Shortcut for the case when we do not know anything about some
165 // input.
166 Node::Inputs inputs = node->inputs();
167 for (Node* input : inputs) {
168 if (!reduced_.Get(input)) {
169 return NoChange();
170 }
171 }
172
173 auto input_it = inputs.begin();
174
175 DCHECK_GT(inputs.count(), 0);
176
177 ControlPathConditions conditions = node_conditions_.Get(*input_it);
178 ++input_it;
179 // Merge the first input's conditions with the conditions from the other
180 // inputs.
181 auto input_end = inputs.end();
182 for (; input_it != input_end; ++input_it) {
183 // Change the current condition list to a longest common tail
184 // of this condition list and the other list. (The common tail
185 // should correspond to the list from the common dominator.)
186 conditions.ResetToCommonAncestor(node_conditions_.Get(*input_it));
187 }
188 return UpdateConditions(node, conditions);
189 }
190
191
ReduceStart(Node * node)192 Reduction BranchElimination::ReduceStart(Node* node) {
193 return UpdateConditions(node, {});
194 }
195
196
ReduceOtherControl(Node * node)197 Reduction BranchElimination::ReduceOtherControl(Node* node) {
198 DCHECK_EQ(1, node->op()->ControlInputCount());
199 return TakeConditionsFromFirstControl(node);
200 }
201
202
TakeConditionsFromFirstControl(Node * node)203 Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
204 // We just propagate the information from the control input (ideally,
205 // we would only revisit control uses if there is change).
206 Node* input = NodeProperties::GetControlInput(node, 0);
207 if (!reduced_.Get(input)) return NoChange();
208 return UpdateConditions(node, node_conditions_.Get(input));
209 }
210
UpdateConditions(Node * node,ControlPathConditions conditions)211 Reduction BranchElimination::UpdateConditions(
212 Node* node, ControlPathConditions conditions) {
213 // Only signal that the node has Changed if the condition information has
214 // changed.
215 if (reduced_.Set(node, true) | node_conditions_.Set(node, conditions)) {
216 return Changed(node);
217 }
218 return NoChange();
219 }
220
UpdateConditions(Node * node,ControlPathConditions prev_conditions,Node * current_condition,Node * current_branch,bool is_true_branch)221 Reduction BranchElimination::UpdateConditions(
222 Node* node, ControlPathConditions prev_conditions, Node* current_condition,
223 Node* current_branch, bool is_true_branch) {
224 ControlPathConditions original = node_conditions_.Get(node);
225 // The control path for the node is the path obtained by appending the
226 // current_condition to the prev_conditions. Use the original control path as
227 // a hint to avoid allocations.
228 prev_conditions.AddCondition(zone_, current_condition, current_branch,
229 is_true_branch, original);
230 return UpdateConditions(node, prev_conditions);
231 }
232
AddCondition(Zone * zone,Node * condition,Node * branch,bool is_true,ControlPathConditions hint)233 void BranchElimination::ControlPathConditions::AddCondition(
234 Zone* zone, Node* condition, Node* branch, bool is_true,
235 ControlPathConditions hint) {
236 DCHECK_EQ(false, LookupCondition(condition, nullptr, nullptr));
237 PushFront({condition, branch, is_true}, zone, hint);
238 }
239
LookupCondition(Node * condition,Node ** branch,bool * is_true) const240 bool BranchElimination::ControlPathConditions::LookupCondition(
241 Node* condition, Node** branch, bool* is_true) const {
242 for (BranchCondition element : *this) {
243 if (element.condition == condition) {
244 *is_true = element.is_true;
245 *branch = element.branch;
246 return true;
247 }
248 }
249 return false;
250 }
251
graph() const252 Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
253
isolate() const254 Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); }
255
common() const256 CommonOperatorBuilder* BranchElimination::common() const {
257 return jsgraph()->common();
258 }
259
260 } // namespace compiler
261 } // namespace internal
262 } // namespace v8
263