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 3153926 : 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 3942408 : dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {
22 : NodeProperties::SetType(dead_, Type::None());
23 788482 : }
24 :
25 1576950 : BranchElimination::~BranchElimination() {}
26 :
27 :
28 99596858 : Reduction BranchElimination::Reduce(Node* node) {
29 99596858 : switch (node->opcode()) {
30 : case IrOpcode::kDead:
31 : return NoChange();
32 : case IrOpcode::kDeoptimizeIf:
33 : case IrOpcode::kDeoptimizeUnless:
34 342658 : return ReduceDeoptimizeConditional(node);
35 : case IrOpcode::kMerge:
36 2788252 : return ReduceMerge(node);
37 : case IrOpcode::kLoop:
38 : return ReduceLoop(node);
39 : case IrOpcode::kBranch:
40 3344977 : return ReduceBranch(node);
41 : case IrOpcode::kIfFalse:
42 3215802 : return ReduceIf(node, false);
43 : case IrOpcode::kIfTrue:
44 3225447 : return ReduceIf(node, true);
45 : case IrOpcode::kStart:
46 1574828 : return ReduceStart(node);
47 : default:
48 169740920 : if (node->op()->ControlOutputCount() > 0) {
49 : return ReduceOtherControl(node);
50 : }
51 : break;
52 : }
53 : return NoChange();
54 : }
55 :
56 :
57 3385341 : Reduction BranchElimination::ReduceBranch(Node* node) {
58 : Node* condition = node->InputAt(0);
59 3344971 : Node* control_input = NodeProperties::GetControlInput(node, 0);
60 : const ControlPathConditions* from_input = node_conditions_.Get(control_input);
61 3344982 : 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 2839786 : if (condition_value.IsJust()) {
65 : bool known_value = condition_value.FromJust();
66 100925 : for (Node* const use : node->uses()) {
67 40370 : switch (use->opcode()) {
68 : case IrOpcode::kIfTrue:
69 60555 : Replace(use, known_value ? control_input : dead());
70 : break;
71 : case IrOpcode::kIfFalse:
72 20185 : Replace(use, known_value ? dead() : control_input);
73 : break;
74 : default:
75 0 : UNREACHABLE();
76 : }
77 : }
78 : return Replace(dead());
79 : }
80 : }
81 3324797 : return TakeConditionsFromFirstControl(node);
82 : }
83 :
84 375469 : Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
85 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
86 : node->opcode() == IrOpcode::kDeoptimizeUnless);
87 342657 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
88 342657 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
89 342658 : Node* condition = NodeProperties::GetValueInput(node, 0);
90 342658 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
91 342658 : Node* effect = NodeProperties::GetEffectInput(node);
92 342658 : 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 342658 : if (conditions == nullptr) {
98 55044 : return UpdateConditions(node, conditions);
99 : }
100 : Maybe<bool> condition_value = conditions->LookupCondition(condition);
101 287614 : if (condition_value.IsJust()) {
102 : // If we know the condition we can discard the branch.
103 16406 : 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 16406 : 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 : return UpdateConditions(
117 271208 : node, conditions->AddCondition(zone_, condition, condition_is_true));
118 : }
119 :
120 6441162 : Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
121 : // Add the condition to the list arriving from the input branch.
122 6441162 : Node* branch = NodeProperties::GetControlInput(node, 0);
123 : const ControlPathConditions* from_branch = node_conditions_.Get(branch);
124 : // If we do not know anything about the predecessor, do not propagate just
125 : // yet because we will have to recompute anyway once we compute the
126 : // predecessor.
127 6441223 : if (from_branch == nullptr) {
128 882710 : return UpdateConditions(node, nullptr);
129 : }
130 : Node* condition = branch->InputAt(0);
131 : return UpdateConditions(
132 5558513 : node, from_branch->AddCondition(zone_, condition, is_true_branch));
133 : }
134 :
135 :
136 0 : Reduction BranchElimination::ReduceLoop(Node* node) {
137 : // Here we rely on having only reducible loops:
138 : // The loop entry edge always dominates the header, so we can just use
139 : // the information from the loop entry edge.
140 215305 : return TakeConditionsFromFirstControl(node);
141 : }
142 :
143 :
144 2788264 : Reduction BranchElimination::ReduceMerge(Node* node) {
145 : // Shortcut for the case when we do not know anything about some
146 : // input.
147 : Node::Inputs inputs = node->inputs();
148 11721613 : for (Node* input : inputs) {
149 9653712 : if (node_conditions_.Get(input) == nullptr) {
150 720363 : return UpdateConditions(node, nullptr);
151 : }
152 : }
153 :
154 : auto input_it = inputs.begin();
155 :
156 : DCHECK_GT(inputs.count(), 0);
157 :
158 : const ControlPathConditions* first = node_conditions_.Get(*input_it);
159 : ++input_it;
160 : // Make a copy of the first input's conditions and merge with the conditions
161 : // from other inputs.
162 : ControlPathConditions* conditions =
163 2067901 : new (zone_->New(sizeof(ControlPathConditions)))
164 2067901 : ControlPathConditions(*first);
165 : auto input_end = inputs.end();
166 5894656 : for (; input_it != input_end; ++input_it) {
167 3826755 : conditions->Merge(*(node_conditions_.Get(*input_it)));
168 : }
169 :
170 2067901 : return UpdateConditions(node, conditions);
171 : }
172 :
173 :
174 1574827 : Reduction BranchElimination::ReduceStart(Node* node) {
175 3149655 : return UpdateConditions(node, ControlPathConditions::Empty(zone_));
176 : }
177 :
178 : const BranchElimination::ControlPathConditions*
179 71576199 : BranchElimination::PathConditionsForControlNodes::Get(Node* node) const {
180 143152398 : if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
181 71472189 : return info_for_node_[node->id()];
182 : }
183 : return nullptr;
184 : }
185 :
186 :
187 18537649 : void BranchElimination::PathConditionsForControlNodes::Set(
188 18537649 : Node* node, const ControlPathConditions* conditions) {
189 18537649 : size_t index = static_cast<size_t>(node->id());
190 55612947 : if (index >= info_for_node_.size()) {
191 58339 : info_for_node_.resize(index + 1, nullptr);
192 : }
193 18537649 : info_for_node_[index] = conditions;
194 18537649 : }
195 :
196 :
197 0 : Reduction BranchElimination::ReduceOtherControl(Node* node) {
198 : DCHECK_EQ(1, node->op()->ControlInputCount());
199 13844618 : return TakeConditionsFromFirstControl(node);
200 : }
201 :
202 :
203 17384598 : 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 : const ControlPathConditions* from_input =
207 17384598 : node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
208 17384549 : return UpdateConditions(node, from_input);
209 : }
210 :
211 :
212 28514419 : Reduction BranchElimination::UpdateConditions(
213 : Node* node, const ControlPathConditions* conditions) {
214 : const ControlPathConditions* original = node_conditions_.Get(node);
215 : // Only signal that the node has Changed if the condition information has
216 : // changed.
217 28514419 : if (conditions != original) {
218 20264704 : if (conditions == nullptr || original == nullptr ||
219 : *conditions != *original) {
220 18537637 : node_conditions_.Set(node, conditions);
221 : return Changed(node);
222 : }
223 : }
224 : return NoChange();
225 : }
226 :
227 :
228 : // static
229 : const BranchElimination::ControlPathConditions*
230 0 : BranchElimination::ControlPathConditions::Empty(Zone* zone) {
231 : return new (zone->New(sizeof(ControlPathConditions)))
232 1574827 : ControlPathConditions(nullptr, 0);
233 : }
234 :
235 :
236 3826753 : void BranchElimination::ControlPathConditions::Merge(
237 : const ControlPathConditions& other) {
238 : // Change the current condition list to a longest common tail
239 : // of this condition list and the other list. (The common tail
240 : // should correspond to the list from the common dominator.)
241 :
242 : // First, we throw away the prefix of the longer list, so that
243 : // we have lists of the same length.
244 3826753 : size_t other_size = other.condition_count_;
245 3826753 : BranchCondition* other_condition = other.head_;
246 13011059 : while (other_size > condition_count_) {
247 5357553 : other_condition = other_condition->next;
248 5357553 : other_size--;
249 : }
250 4333097 : while (condition_count_ > other_size) {
251 506344 : head_ = head_->next;
252 506344 : condition_count_--;
253 : }
254 :
255 : // Then we go through both lists in lock-step until we find
256 : // the common tail.
257 5806822 : while (head_ != other_condition) {
258 : DCHECK(condition_count_ > 0);
259 1980069 : condition_count_--;
260 1980069 : other_condition = other_condition->next;
261 1980069 : head_ = head_->next;
262 : }
263 3826753 : }
264 :
265 :
266 : const BranchElimination::ControlPathConditions*
267 5829631 : BranchElimination::ControlPathConditions::AddCondition(Zone* zone,
268 : Node* condition,
269 : bool is_true) const {
270 : DCHECK(LookupCondition(condition).IsNothing());
271 :
272 : BranchCondition* new_head = new (zone->New(sizeof(BranchCondition)))
273 5829631 : BranchCondition(condition, is_true, head_);
274 :
275 : ControlPathConditions* conditions =
276 : new (zone->New(sizeof(ControlPathConditions)))
277 5829639 : ControlPathConditions(new_head, condition_count_ + 1);
278 5829560 : return conditions;
279 : }
280 :
281 :
282 0 : Maybe<bool> BranchElimination::ControlPathConditions::LookupCondition(
283 : Node* condition) const {
284 17836868 : for (BranchCondition* current = head_; current != nullptr;
285 : current = current->next) {
286 14746063 : if (current->condition == condition) {
287 36595 : return Just<bool>(current->is_true);
288 : }
289 : }
290 : return Nothing<bool>();
291 : }
292 :
293 :
294 863553 : bool BranchElimination::ControlPathConditions::operator==(
295 : const ControlPathConditions& other) const {
296 863553 : if (condition_count_ != other.condition_count_) return false;
297 863542 : BranchCondition* this_condition = head_;
298 863542 : BranchCondition* other_condition = other.head_;
299 : while (true) {
300 863542 : if (this_condition == other_condition) return true;
301 0 : if (this_condition->condition != other_condition->condition ||
302 0 : this_condition->is_true != other_condition->is_true) {
303 : return false;
304 : }
305 0 : this_condition = this_condition->next;
306 0 : other_condition = other_condition->next;
307 : }
308 : UNREACHABLE();
309 0 : return false;
310 : }
311 :
312 0 : Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
313 :
314 0 : CommonOperatorBuilder* BranchElimination::common() const {
315 0 : return jsgraph()->common();
316 : }
317 :
318 : } // namespace compiler
319 : } // namespace internal
320 : } // namespace v8
|
