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 3148166 : 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 3935204 : dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {
22 : NodeProperties::SetType(dead_, Type::None());
23 787044 : }
24 :
25 1574076 : BranchElimination::~BranchElimination() {}
26 :
27 :
28 99611035 : Reduction BranchElimination::Reduce(Node* node) {
29 99611035 : switch (node->opcode()) {
30 : case IrOpcode::kDead:
31 : return NoChange();
32 : case IrOpcode::kDeoptimizeIf:
33 : case IrOpcode::kDeoptimizeUnless:
34 341823 : return ReduceDeoptimizeConditional(node);
35 : case IrOpcode::kMerge:
36 2790697 : return ReduceMerge(node);
37 : case IrOpcode::kLoop:
38 : return ReduceLoop(node);
39 : case IrOpcode::kBranch:
40 3346872 : return ReduceBranch(node);
41 : case IrOpcode::kIfFalse:
42 3217132 : return ReduceIf(node, false);
43 : case IrOpcode::kIfTrue:
44 3226648 : return ReduceIf(node, true);
45 : case IrOpcode::kStart:
46 1571933 : return ReduceStart(node);
47 : default:
48 169761822 : if (node->op()->ControlOutputCount() > 0) {
49 : return ReduceOtherControl(node);
50 : }
51 : break;
52 : }
53 : return NoChange();
54 : }
55 :
56 :
57 3387657 : Reduction BranchElimination::ReduceBranch(Node* node) {
58 : Node* condition = node->InputAt(0);
59 3346869 : Node* control_input = NodeProperties::GetControlInput(node, 0);
60 : const ControlPathConditions* from_input = node_conditions_.Get(control_input);
61 3346877 : 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 2839777 : if (condition_value.IsJust()) {
65 : bool known_value = condition_value.FromJust();
66 101970 : for (Node* const use : node->uses()) {
67 40788 : switch (use->opcode()) {
68 : case IrOpcode::kIfTrue:
69 61182 : Replace(use, known_value ? control_input : dead());
70 : break;
71 : case IrOpcode::kIfFalse:
72 20394 : Replace(use, known_value ? dead() : control_input);
73 : break;
74 : default:
75 0 : UNREACHABLE();
76 : }
77 : }
78 : return Replace(dead());
79 : }
80 : }
81 3326483 : return TakeConditionsFromFirstControl(node);
82 : }
83 :
84 374884 : Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
85 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
86 : node->opcode() == IrOpcode::kDeoptimizeUnless);
87 341822 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
88 341822 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
89 341822 : Node* condition = NodeProperties::GetValueInput(node, 0);
90 341822 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
91 341821 : Node* effect = NodeProperties::GetEffectInput(node);
92 341820 : 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 341820 : if (conditions == nullptr) {
98 54970 : return UpdateConditions(node, conditions);
99 : }
100 : Maybe<bool> condition_value = conditions->LookupCondition(condition);
101 286850 : if (condition_value.IsJust()) {
102 : // If we know the condition we can discard the branch.
103 16531 : 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 16531 : 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 270319 : node, conditions->AddCondition(zone_, condition, condition_is_true));
118 : }
119 :
120 6443682 : Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
121 : // Add the condition to the list arriving from the input branch.
122 6443682 : 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 6443770 : if (from_branch == nullptr) {
128 886360 : return UpdateConditions(node, nullptr);
129 : }
130 : Node* condition = branch->InputAt(0);
131 : return UpdateConditions(
132 5557410 : 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 215815 : return TakeConditionsFromFirstControl(node);
141 : }
142 :
143 :
144 2790721 : 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 11728637 : for (Node* input : inputs) {
149 9661122 : if (node_conditions_.Get(input) == nullptr) {
150 723206 : 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 2067515 : new (zone_->New(sizeof(ControlPathConditions)))
164 2067515 : ControlPathConditions(*first);
165 : auto input_end = inputs.end();
166 5894092 : for (; input_it != input_end; ++input_it) {
167 3826570 : conditions->Merge(*(node_conditions_.Get(*input_it)));
168 : }
169 :
170 2067522 : return UpdateConditions(node, conditions);
171 : }
172 :
173 :
174 1571933 : Reduction BranchElimination::ReduceStart(Node* node) {
175 3143867 : return UpdateConditions(node, ControlPathConditions::Empty(zone_));
176 : }
177 :
178 : const BranchElimination::ControlPathConditions*
179 71590288 : BranchElimination::PathConditionsForControlNodes::Get(Node* node) const {
180 143180576 : if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
181 71486272 : return info_for_node_[node->id()];
182 : }
183 : return nullptr;
184 : }
185 :
186 :
187 18532045 : void BranchElimination::PathConditionsForControlNodes::Set(
188 18532045 : Node* node, const ControlPathConditions* conditions) {
189 18532045 : size_t index = static_cast<size_t>(node->id());
190 55596135 : if (index >= info_for_node_.size()) {
191 58515 : info_for_node_.resize(index + 1, nullptr);
192 : }
193 18532045 : info_for_node_[index] = conditions;
194 18532045 : }
195 :
196 :
197 0 : Reduction BranchElimination::ReduceOtherControl(Node* node) {
198 : DCHECK_EQ(1, node->op()->ControlInputCount());
199 13843611 : return TakeConditionsFromFirstControl(node);
200 : }
201 :
202 :
203 17385787 : 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 17385787 : node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
208 17385769 : return UpdateConditions(node, from_input);
209 : }
210 :
211 :
212 28516845 : 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 28516845 : if (conditions != original) {
218 20256203 : if (conditions == nullptr || original == nullptr ||
219 : *conditions != *original) {
220 18532016 : 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 1571933 : ControlPathConditions(nullptr, 0);
233 : }
234 :
235 :
236 3826566 : 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 3826566 : size_t other_size = other.condition_count_;
245 3826566 : BranchCondition* other_condition = other.head_;
246 13011570 : while (other_size > condition_count_) {
247 5358438 : other_condition = other_condition->next;
248 5358438 : other_size--;
249 : }
250 4332561 : while (condition_count_ > other_size) {
251 505995 : head_ = head_->next;
252 505995 : condition_count_--;
253 : }
254 :
255 : // Then we go through both lists in lock-step until we find
256 : // the common tail.
257 5805959 : while (head_ != other_condition) {
258 : DCHECK(condition_count_ > 0);
259 1979393 : condition_count_--;
260 1979393 : other_condition = other_condition->next;
261 1979393 : head_ = head_->next;
262 : }
263 3826566 : }
264 :
265 :
266 : const BranchElimination::ControlPathConditions*
267 5827618 : 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 5827618 : BranchCondition(condition, is_true, head_);
274 :
275 : ControlPathConditions* conditions =
276 : new (zone->New(sizeof(ControlPathConditions)))
277 5827606 : ControlPathConditions(new_head, condition_count_ + 1);
278 5827613 : return conditions;
279 : }
280 :
281 :
282 0 : Maybe<bool> BranchElimination::ControlPathConditions::LookupCondition(
283 : Node* condition) const {
284 17863050 : for (BranchCondition* current = head_; current != nullptr;
285 : current = current->next) {
286 14773358 : if (current->condition == condition) {
287 36935 : return Just<bool>(current->is_true);
288 : }
289 : }
290 : return Nothing<bool>();
291 : }
292 :
293 :
294 862114 : bool BranchElimination::ControlPathConditions::operator==(
295 : const ControlPathConditions& other) const {
296 862114 : if (condition_count_ != other.condition_count_) return false;
297 862104 : BranchCondition* this_condition = head_;
298 862104 : BranchCondition* other_condition = other.head_;
299 : while (true) {
300 862104 : 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
|
