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 | |
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 | |
24 | BranchElimination::~BranchElimination() = default; |
25 | |
26 | |
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 | |
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() && branch->opcode() != IrOpcode::kDead) { |
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 | |
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 | |
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 | |
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 | |
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 | |
192 | Reduction BranchElimination::ReduceStart(Node* node) { |
193 | return UpdateConditions(node, {}); |
194 | } |
195 | |
196 | |
197 | Reduction BranchElimination::ReduceOtherControl(Node* node) { |
198 | DCHECK_EQ(1, node->op()->ControlInputCount()); |
199 | return TakeConditionsFromFirstControl(node); |
200 | } |
201 | |
202 | |
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 | |
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 | |
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 | |
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 | |
240 | 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 | |
252 | Graph* BranchElimination::graph() const { return jsgraph()->graph(); } |
253 | |
254 | Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); } |
255 | |
256 | CommonOperatorBuilder* BranchElimination::common() const { |
257 | return jsgraph()->common(); |
258 | } |
259 | |
260 | } // namespace compiler |
261 | } // namespace internal |
262 | } // namespace v8 |
263 | |