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 3546844 : BranchElimination::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 4433556 : dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {
22 : NodeProperties::SetType(dead_, Type::None());
23 886712 : }
24 :
25 1773406 : BranchElimination::~BranchElimination() {}
26 :
27 :
28 100493885 : Reduction BranchElimination::Reduce(Node* node) {
29 100493885 : switch (node->opcode()) {
30 : case IrOpcode::kDead:
31 : return NoChange();
32 : case IrOpcode::kDeoptimizeIf:
33 : case IrOpcode::kDeoptimizeUnless:
34 381784 : return ReduceDeoptimizeConditional(node);
35 : case IrOpcode::kMerge:
36 2149507 : return ReduceMerge(node);
37 : case IrOpcode::kLoop:
38 : return ReduceLoop(node);
39 : case IrOpcode::kBranch:
40 2833004 : return ReduceBranch(node);
41 : case IrOpcode::kIfFalse:
42 2756159 : return ReduceIf(node, false);
43 : case IrOpcode::kIfTrue:
44 2766107 : return ReduceIf(node, true);
45 : case IrOpcode::kStart:
46 1773405 : return ReduceStart(node);
47 : default:
48 175234344 : if (node->op()->ControlOutputCount() > 0) {
49 : return ReduceOtherControl(node);
50 : }
51 : break;
52 : }
53 : return NoChange();
54 : }
55 :
56 :
57 2868375 : Reduction BranchElimination::ReduceBranch(Node* node) {
58 : Node* condition = node->InputAt(0);
59 2833021 : Node* control_input = NodeProperties::GetControlInput(node, 0);
60 : const ControlPathConditions* from_input = node_conditions_.Get(control_input);
61 2833016 : if (from_input != nullptr) {
62 : Maybe<bool> condition_value = from_input->LookupCondition(condition);
63 : // If we know the condition we can discard the branch.
64 2464282 : if (condition_value.IsJust()) {
65 : bool known_value = condition_value.FromJust();
66 88385 : for (Node* const use : node->uses()) {
67 35354 : switch (use->opcode()) {
68 : case IrOpcode::kIfTrue:
69 53031 : Replace(use, known_value ? control_input : dead());
70 : break;
71 : case IrOpcode::kIfFalse:
72 17677 : Replace(use, known_value ? dead() : control_input);
73 : break;
74 : default:
75 0 : UNREACHABLE();
76 : }
77 : }
78 : return Replace(dead());
79 : }
80 : }
81 2815339 : return TakeConditionsFromFirstControl(node);
82 : }
83 :
84 409245 : Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
85 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
86 : node->opcode() == IrOpcode::kDeoptimizeUnless);
87 381781 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
88 381781 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
89 381783 : Node* condition = NodeProperties::GetValueInput(node, 0);
90 381782 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
91 381781 : Node* effect = NodeProperties::GetEffectInput(node);
92 381781 : Node* control = NodeProperties::GetControlInput(node);
93 : ControlPathConditions const* conditions = node_conditions_.Get(control);
94 : // If we do not know anything about the predecessor, do not propagate just
95 : // yet because we will have to recompute anyway once we compute the
96 : // predecessor.
97 381783 : if (conditions == nullptr) {
98 62202 : return UpdateConditions(node, conditions);
99 : }
100 : Maybe<bool> condition_value = conditions->LookupCondition(condition);
101 319581 : if (condition_value.IsJust()) {
102 : // If we know the condition we can discard the branch.
103 13732 : if (condition_is_true == condition_value.FromJust()) {
104 : // We don't update the conditions here, because we're replacing {node}
105 : // with the {control} node that already contains the right information.
106 13732 : ReplaceWithValue(node, dead(), effect, control);
107 : } else {
108 : control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
109 0 : frame_state, effect, control);
110 : // TODO(bmeurer): This should be on the AdvancedReducer somehow.
111 0 : NodeProperties::MergeControlToEnd(graph(), common(), control);
112 0 : Revisit(graph()->end());
113 : }
114 : return Replace(dead());
115 : }
116 305849 : return UpdateConditions(node, conditions, condition, condition_is_true);
117 : }
118 :
119 5522183 : Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
120 : // Add the condition to the list arriving from the input branch.
121 5522183 : Node* branch = NodeProperties::GetControlInput(node, 0);
122 : const ControlPathConditions* from_branch = node_conditions_.Get(branch);
123 : // If we do not know anything about the predecessor, do not propagate just
124 : // yet because we will have to recompute anyway once we compute the
125 : // predecessor.
126 5522238 : if (from_branch == nullptr) {
127 709500 : return UpdateConditions(node, nullptr);
128 : }
129 : Node* condition = branch->InputAt(0);
130 4812738 : return UpdateConditions(node, from_branch, condition, is_true_branch);
131 : }
132 :
133 :
134 0 : Reduction BranchElimination::ReduceLoop(Node* node) {
135 : // Here we rely on having only reducible loops:
136 : // The loop entry edge always dominates the header, so we can just use
137 : // the information from the loop entry edge.
138 199869 : return TakeConditionsFromFirstControl(node);
139 : }
140 :
141 :
142 2149476 : Reduction BranchElimination::ReduceMerge(Node* node) {
143 : // Shortcut for the case when we do not know anything about some
144 : // input.
145 : Node::Inputs inputs = node->inputs();
146 7477094 : for (Node* input : inputs) {
147 5741717 : if (node_conditions_.Get(input) == nullptr) {
148 414099 : return UpdateConditions(node, nullptr);
149 : }
150 : }
151 :
152 : auto input_it = inputs.begin();
153 :
154 : DCHECK_GT(inputs.count(), 0);
155 :
156 : const ControlPathConditions* first = node_conditions_.Get(*input_it);
157 : ++input_it;
158 : // Make a copy of the first input's conditions and merge with the conditions
159 : // from other inputs.
160 : ControlPathConditions* conditions =
161 1735377 : new (zone_->New(sizeof(ControlPathConditions)))
162 1735377 : ControlPathConditions(*first);
163 : auto input_end = inputs.end();
164 4283100 : for (; input_it != input_end; ++input_it) {
165 2547722 : conditions->Merge(*(node_conditions_.Get(*input_it)));
166 : }
167 :
168 1735378 : return UpdateConditions(node, conditions);
169 : }
170 :
171 :
172 1773404 : Reduction BranchElimination::ReduceStart(Node* node) {
173 3546812 : return UpdateConditions(node, ControlPathConditions::Empty(zone_));
174 : }
175 :
176 : const BranchElimination::ControlPathConditions*
177 63435671 : BranchElimination::PathConditionsForControlNodes::Get(Node* node) const {
178 126871342 : if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
179 63331718 : return info_for_node_[node->id()];
180 : }
181 : return nullptr;
182 : }
183 :
184 :
185 17709665 : void BranchElimination::PathConditionsForControlNodes::Set(
186 17709665 : Node* node, const ControlPathConditions* conditions) {
187 17709665 : size_t index = static_cast<size_t>(node->id());
188 53128995 : if (index >= info_for_node_.size()) {
189 71087 : info_for_node_.resize(index + 1, nullptr);
190 : }
191 17709665 : info_for_node_[index] = conditions;
192 17709665 : }
193 :
194 :
195 0 : Reduction BranchElimination::ReduceOtherControl(Node* node) {
196 : DCHECK_EQ(1, node->op()->ControlInputCount());
197 14415238 : return TakeConditionsFromFirstControl(node);
198 : }
199 :
200 :
201 17430402 : Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
202 : // We just propagate the information from the control input (ideally,
203 : // we would only revisit control uses if there is change).
204 : const ControlPathConditions* from_input =
205 17430402 : node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
206 17430364 : return UpdateConditions(node, from_input);
207 : }
208 :
209 :
210 22124918 : Reduction BranchElimination::UpdateConditions(
211 : Node* node, const ControlPathConditions* conditions) {
212 : const ControlPathConditions* original = node_conditions_.Get(node);
213 : // Only signal that the node has Changed if the condition information has
214 : // changed.
215 22124918 : if (conditions != original) {
216 14471157 : if (conditions == nullptr || original == nullptr ||
217 : *conditions != *original) {
218 12591822 : node_conditions_.Set(node, conditions);
219 : return Changed(node);
220 : }
221 : }
222 : return NoChange();
223 : }
224 :
225 5118536 : Reduction BranchElimination::UpdateConditions(
226 : Node* node, const ControlPathConditions* prev_conditions,
227 : Node* current_condition, bool is_true_branch) {
228 : const ControlPathConditions* original = node_conditions_.Get(node);
229 : DCHECK(prev_conditions != nullptr && current_condition != nullptr);
230 : // The control path for the node is the path obtained by appending the
231 : // current_condition to the prev_conditions. Check if this new control path
232 : // would be the same as the already recorded path (original).
233 5118578 : if (original == nullptr || !prev_conditions->EqualsAfterAddingCondition(
234 42 : original, current_condition, is_true_branch)) {
235 : // If this is the first visit or if the control path is different from the
236 : // recorded path create the new control path and record it.
237 : const ControlPathConditions* new_condition =
238 5118536 : prev_conditions->AddCondition(zone_, current_condition, is_true_branch);
239 5118352 : node_conditions_.Set(node, new_condition);
240 : return Changed(node);
241 : }
242 : return NoChange();
243 : }
244 :
245 : // static
246 : const BranchElimination::ControlPathConditions*
247 0 : BranchElimination::ControlPathConditions::Empty(Zone* zone) {
248 : return new (zone->New(sizeof(ControlPathConditions)))
249 1773404 : ControlPathConditions(nullptr, 0);
250 : }
251 :
252 :
253 2547734 : void BranchElimination::ControlPathConditions::Merge(
254 : const ControlPathConditions& other) {
255 : // Change the current condition list to a longest common tail
256 : // of this condition list and the other list. (The common tail
257 : // should correspond to the list from the common dominator.)
258 :
259 : // First, we throw away the prefix of the longer list, so that
260 : // we have lists of the same length.
261 2547734 : size_t other_size = other.condition_count_;
262 2547734 : BranchCondition* other_condition = other.head_;
263 7915048 : while (other_size > condition_count_) {
264 2819580 : other_condition = other_condition->next;
265 2819580 : other_size--;
266 : }
267 2903735 : while (condition_count_ > other_size) {
268 356001 : head_ = head_->next;
269 356001 : condition_count_--;
270 : }
271 :
272 : // Then we go through both lists in lock-step until we find
273 : // the common tail.
274 4217929 : while (head_ != other_condition) {
275 : DCHECK_LT(0, condition_count_);
276 1670195 : condition_count_--;
277 1670195 : other_condition = other_condition->next;
278 1670195 : head_ = head_->next;
279 : }
280 2547734 : }
281 :
282 :
283 : const BranchElimination::ControlPathConditions*
284 5118535 : BranchElimination::ControlPathConditions::AddCondition(Zone* zone,
285 : Node* condition,
286 : bool is_true) const {
287 : DCHECK(LookupCondition(condition).IsNothing());
288 :
289 : BranchCondition* new_head = new (zone->New(sizeof(BranchCondition)))
290 5118535 : BranchCondition(condition, is_true, head_);
291 :
292 : ControlPathConditions* conditions =
293 : new (zone->New(sizeof(ControlPathConditions)))
294 5118512 : ControlPathConditions(new_head, condition_count_ + 1);
295 5118337 : return conditions;
296 : }
297 :
298 :
299 0 : Maybe<bool> BranchElimination::ControlPathConditions::LookupCondition(
300 : Node* condition) const {
301 16541633 : for (BranchCondition* current = head_; current != nullptr;
302 : current = current->next) {
303 13789182 : if (current->condition == condition) {
304 31412 : return Just<bool>(current->is_true);
305 : }
306 : }
307 : return Nothing<bool>();
308 : }
309 :
310 0 : bool BranchElimination::ControlPathConditions::IsSamePath(
311 : BranchCondition* this_condition, BranchCondition* other_condition) const {
312 : while (true) {
313 939644 : if (this_condition == other_condition) return true;
314 0 : if (this_condition->condition != other_condition->condition ||
315 0 : this_condition->is_true != other_condition->is_true) {
316 : return false;
317 : }
318 0 : this_condition = this_condition->next;
319 0 : other_condition = other_condition->next;
320 : }
321 : UNREACHABLE();
322 : }
323 :
324 939691 : bool BranchElimination::ControlPathConditions::operator==(
325 : const ControlPathConditions& other) const {
326 939691 : if (condition_count_ != other.condition_count_) return false;
327 1879288 : return IsSamePath(head_, other.head_);
328 : }
329 :
330 42 : bool BranchElimination::ControlPathConditions::EqualsAfterAddingCondition(
331 : const ControlPathConditions* other, const Node* new_condition,
332 : bool new_branch_direction) const {
333 : // When an extra condition is added to the current chain, the count of
334 : // the resulting chain would increase by 1. Quick check to see if counts
335 : // match.
336 42 : if (other->condition_count_ != condition_count_ + 1) return false;
337 :
338 : // Check if the head of the other chain is same as the new condition that
339 : // would be added.
340 0 : if (other->head_->condition != new_condition ||
341 0 : other->head_->is_true != new_branch_direction) {
342 : return false;
343 : }
344 :
345 : // Check if the rest of the path is the same as the prev_condition.
346 0 : return IsSamePath(other->head_->next, head_);
347 : }
348 :
349 0 : Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
350 :
351 0 : CommonOperatorBuilder* BranchElimination::common() const {
352 0 : return jsgraph()->common();
353 : }
354 :
355 : } // namespace compiler
356 : } // namespace internal
357 : } // namespace v8
|
