Line data Source code
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 979107 : 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 2937388 : dead_(js_graph->Dead()) {}
23 :
24 : BranchElimination::~BranchElimination() = default;
25 :
26 :
27 125538467 : Reduction BranchElimination::Reduce(Node* node) {
28 125538467 : switch (node->opcode()) {
29 : case IrOpcode::kDead:
30 : return NoChange();
31 : case IrOpcode::kDeoptimizeIf:
32 : case IrOpcode::kDeoptimizeUnless:
33 412619 : return ReduceDeoptimizeConditional(node);
34 : case IrOpcode::kMerge:
35 3362915 : return ReduceMerge(node);
36 : case IrOpcode::kLoop:
37 : return ReduceLoop(node);
38 : case IrOpcode::kBranch:
39 4890204 : return ReduceBranch(node);
40 : case IrOpcode::kIfFalse:
41 4768494 : return ReduceIf(node, false);
42 : case IrOpcode::kIfTrue:
43 4807463 : return ReduceIf(node, true);
44 : case IrOpcode::kStart:
45 : return ReduceStart(node);
46 : default:
47 209893594 : if (node->op()->ControlOutputCount() > 0) {
48 : return ReduceOtherControl(node);
49 : }
50 : break;
51 : }
52 : return NoChange();
53 : }
54 :
55 :
56 4951959 : Reduction BranchElimination::ReduceBranch(Node* node) {
57 : Node* condition = node->InputAt(0);
58 4890192 : 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 4890256 : 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 24246 : if (!branch->IsDead()) {
67 20589 : IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
68 : IsSafetyCheck combined_safety =
69 20589 : CombineSafetyChecks(branch_safety, IsSafetyCheckOf(node->op()));
70 20589 : if (branch_safety != combined_safety) {
71 : NodeProperties::ChangeOp(
72 3657 : branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
73 : }
74 : }
75 :
76 123534 : for (Node* const use : node->uses()) {
77 41178 : switch (use->opcode()) {
78 : case IrOpcode::kIfTrue:
79 61767 : Replace(use, condition_value ? control_input : dead());
80 : break;
81 : case IrOpcode::kIfFalse:
82 20589 : Replace(use, condition_value ? dead() : control_input);
83 : break;
84 : default:
85 0 : UNREACHABLE();
86 : }
87 : }
88 : return Replace(dead());
89 : }
90 4869667 : return TakeConditionsFromFirstControl(node);
91 : }
92 :
93 430614 : Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
94 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
95 : node->opcode() == IrOpcode::kDeoptimizeUnless);
96 412618 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
97 412618 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
98 412620 : Node* condition = NodeProperties::GetValueInput(node, 0);
99 412620 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
100 412621 : Node* effect = NodeProperties::GetEffectInput(node);
101 412618 : 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 412621 : if (!reduced_.Get(control)) {
106 : return NoChange();
107 : }
108 :
109 : ControlPathConditions conditions = node_conditions_.Get(control);
110 : bool condition_value;
111 : Node* branch;
112 352749 : if (conditions.LookupCondition(condition, &branch, &condition_value)) {
113 : // Mark the branch as a safety check.
114 12918 : IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
115 : IsSafetyCheck combined_safety =
116 8998 : CombineSafetyChecks(branch_safety, p.is_safety_check());
117 8998 : if (branch_safety != combined_safety) {
118 : NodeProperties::ChangeOp(
119 3920 : branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
120 : }
121 :
122 : // If we know the condition we can discard the branch.
123 8998 : 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 8998 : ReplaceWithValue(node, dead(), effect, control);
127 : } else {
128 : control = graph()->NewNode(
129 : common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
130 0 : effect, control);
131 : // TODO(bmeurer): This should be on the AdvancedReducer somehow.
132 0 : NodeProperties::MergeControlToEnd(graph(), common(), control);
133 0 : Revisit(graph()->end());
134 : }
135 : return Replace(dead());
136 : }
137 343751 : return UpdateConditions(node, conditions, condition, node, condition_is_true);
138 : }
139 :
140 9575702 : Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
141 : // Add the condition to the list arriving from the input branch.
142 9575702 : Node* branch = NodeProperties::GetControlInput(node, 0);
143 9575642 : 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 9575642 : if (!reduced_.Get(branch)) {
148 : return NoChange();
149 : }
150 : Node* condition = branch->InputAt(0);
151 7681473 : return UpdateConditions(node, from_branch, condition, branch, is_true_branch);
152 : }
153 :
154 :
155 0 : 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 426536 : return TakeConditionsFromFirstControl(node);
160 : }
161 :
162 :
163 3362810 : 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 15922160 : for (Node* input : inputs) {
168 10151405 : 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 2407945 : 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 8824977 : 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 4009061 : conditions.ResetToCommonAncestor(node_conditions_.Get(*input_it));
187 : }
188 2407971 : return UpdateConditions(node, conditions);
189 : }
190 :
191 :
192 0 : Reduction BranchElimination::ReduceStart(Node* node) {
193 1891307 : return UpdateConditions(node, {});
194 : }
195 :
196 :
197 0 : Reduction BranchElimination::ReduceOtherControl(Node* node) {
198 : DCHECK_EQ(1, node->op()->ControlInputCount());
199 15477799 : return TakeConditionsFromFirstControl(node);
200 : }
201 :
202 :
203 20773910 : 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 20773910 : Node* input = NodeProperties::GetControlInput(node, 0);
207 20773861 : if (!reduced_.Get(input)) return NoChange();
208 18485646 : return UpdateConditions(node, node_conditions_.Get(input));
209 : }
210 :
211 30809409 : Reduction BranchElimination::UpdateConditions(
212 : Node* node, ControlPathConditions conditions) {
213 : // Only signal that the node has Changed if the condition information has
214 : // changed.
215 30809409 : if (reduced_.Set(node, true) | node_conditions_.Set(node, conditions)) {
216 : return Changed(node);
217 : }
218 : return NoChange();
219 : }
220 :
221 8025163 : 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 8025163 : is_true_branch, original);
230 8025149 : return UpdateConditions(node, prev_conditions);
231 : }
232 :
233 0 : 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 8025163 : PushFront({condition, branch, is_true}, zone, hint);
238 0 : }
239 :
240 0 : bool BranchElimination::ControlPathConditions::LookupCondition(
241 : Node* condition, Node** branch, bool* is_true) const {
242 56818173 : for (BranchCondition element : *this) {
243 25802383 : if (element.condition == condition) {
244 29598 : *is_true = element.is_true;
245 0 : *branch = element.branch;
246 : return true;
247 : }
248 : }
249 0 : return false;
250 : }
251 :
252 0 : Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
253 :
254 0 : Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); }
255 :
256 7577 : CommonOperatorBuilder* BranchElimination::common() const {
257 7577 : return jsgraph()->common();
258 : }
259 :
260 : } // namespace compiler
261 : } // namespace internal
262 183867 : } // namespace v8
|
