Line data Source code
1 : // Copyright 2016 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/loop-variable-optimizer.h"
6 :
7 : #include "src/compiler/common-operator.h"
8 : #include "src/compiler/graph.h"
9 : #include "src/compiler/node-marker.h"
10 : #include "src/compiler/node-properties.h"
11 : #include "src/compiler/node.h"
12 : #include "src/zone/zone-containers.h"
13 : #include "src/zone/zone.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 : namespace compiler {
18 :
19 : // Macro for outputting trace information from representation inference.
20 : #define TRACE(...) \
21 : do { \
22 : if (FLAG_trace_turbo_loop) PrintF(__VA_ARGS__); \
23 : } while (false)
24 :
25 790686 : LoopVariableOptimizer::LoopVariableOptimizer(Graph* graph,
26 : CommonOperatorBuilder* common,
27 : Zone* zone)
28 : : graph_(graph),
29 : common_(common),
30 : zone_(zone),
31 : limits_(graph->NodeCount(), zone),
32 790686 : induction_vars_(zone) {}
33 :
34 1186029 : void LoopVariableOptimizer::Run() {
35 395343 : ZoneQueue<Node*> queue(zone());
36 790686 : queue.push(graph()->start());
37 : NodeMarker<bool> queued(graph(), 2);
38 7889545 : while (!queue.empty()) {
39 14988405 : Node* node = queue.front();
40 : queue.pop();
41 : queued.Set(node, false);
42 :
43 : DCHECK_NULL(limits_[node->id()]);
44 : bool all_inputs_visited = true;
45 : int inputs_end = (node->opcode() == IrOpcode::kLoop)
46 : ? kFirstBackedge
47 7494203 : : node->op()->ControlInputCount();
48 18124456 : for (int i = 0; i < inputs_end; i++) {
49 34054810 : if (limits_[NodeProperties::GetControlInput(node, i)->id()] == nullptr) {
50 : all_inputs_visited = false;
51 : break;
52 : }
53 : }
54 7494202 : if (!all_inputs_visited) continue;
55 :
56 6772851 : VisitNode(node);
57 : DCHECK_NOT_NULL(limits_[node->id()]);
58 :
59 : // Queue control outputs.
60 63247079 : for (Edge edge : node->use_edges()) {
61 41414274 : if (NodeProperties::IsControlEdge(edge) &&
62 13177160 : edge.from()->op()->ControlOutputCount() > 0) {
63 7289153 : Node* use = edge.from();
64 14669620 : if (use->opcode() == IrOpcode::kLoop &&
65 91314 : edge.index() != kAssumedLoopEntryIndex) {
66 45657 : VisitBackedge(node, use);
67 7243496 : } else if (!queued.Get(use)) {
68 : queue.push(use);
69 7098858 : queued.Set(use, true);
70 : }
71 : }
72 : }
73 : }
74 395343 : }
75 :
76 : class LoopVariableOptimizer::Constraint : public ZoneObject {
77 : public:
78 : InductionVariable::ConstraintKind kind() const { return kind_; }
79 : Node* left() const { return left_; }
80 : Node* right() const { return right_; }
81 :
82 : const Constraint* next() const { return next_; }
83 :
84 : Constraint(Node* left, InductionVariable::ConstraintKind kind, Node* right,
85 : const Constraint* next)
86 104978 : : left_(left), right_(right), kind_(kind), next_(next) {}
87 :
88 : private:
89 : Node* left_;
90 : Node* right_;
91 : InductionVariable::ConstraintKind kind_;
92 : const Constraint* next_;
93 : };
94 :
95 : class LoopVariableOptimizer::VariableLimits : public ZoneObject {
96 : public:
97 : static VariableLimits* Empty(Zone* zone) {
98 : return new (zone) VariableLimits();
99 : }
100 :
101 : VariableLimits* Copy(Zone* zone) const {
102 : return new (zone) VariableLimits(this);
103 : }
104 :
105 : void Add(Node* left, InductionVariable::ConstraintKind kind, Node* right,
106 : Zone* zone) {
107 209956 : head_ = new (zone) Constraint(left, kind, right, head_);
108 104978 : limit_count_++;
109 : }
110 :
111 716683 : void Merge(const VariableLimits* other) {
112 : // Change the current condition list to a longest common tail
113 : // of this condition list and the other list. (The common tail
114 : // should correspond to the list from the common dominator.)
115 :
116 : // First, we throw away the prefix of the longer list, so that
117 : // we have lists of the same length.
118 716683 : size_t other_size = other->limit_count_;
119 754580 : const Constraint* other_limit = other->head_;
120 1440849 : while (other_size > limit_count_) {
121 : other_limit = other_limit->next();
122 7483 : other_size--;
123 : }
124 716889 : while (limit_count_ > other_size) {
125 30620 : head_ = head_->next();
126 206 : limit_count_--;
127 : }
128 :
129 : // Then we go through both lists in lock-step until we find
130 : // the common tail.
131 747097 : while (head_ != other_limit) {
132 : DCHECK(limit_count_ > 0);
133 30414 : limit_count_--;
134 : other_limit = other_limit->next();
135 30414 : head_ = head_->next();
136 : }
137 716683 : }
138 :
139 : const Constraint* head() const { return head_; }
140 :
141 : private:
142 395343 : VariableLimits() {}
143 : explicit VariableLimits(const VariableLimits* other)
144 1876061 : : head_(other->head_), limit_count_(other->limit_count_) {}
145 :
146 : const Constraint* head_ = nullptr;
147 : size_t limit_count_ = 0;
148 : };
149 :
150 21794 : void InductionVariable::AddUpperBound(Node* bound,
151 0 : InductionVariable::ConstraintKind kind) {
152 21794 : if (FLAG_trace_turbo_loop) {
153 0 : OFStream os(stdout);
154 0 : os << "New upper bound for " << phi()->id() << " (loop "
155 0 : << NodeProperties::GetControlInput(phi())->id() << "): " << *bound
156 0 : << std::endl;
157 : }
158 43588 : upper_bounds_.push_back(Bound(bound, kind));
159 21794 : }
160 :
161 1475 : void InductionVariable::AddLowerBound(Node* bound,
162 0 : InductionVariable::ConstraintKind kind) {
163 1475 : if (FLAG_trace_turbo_loop) {
164 0 : OFStream os(stdout);
165 0 : os << "New lower bound for " << phi()->id() << " (loop "
166 0 : << NodeProperties::GetControlInput(phi())->id() << "): " << *bound;
167 : }
168 2950 : lower_bounds_.push_back(Bound(bound, kind));
169 1475 : }
170 :
171 91314 : void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
172 91314 : if (loop->op()->ControlInputCount() != 2) return;
173 :
174 : // Go through the constraints, and update the induction variables in
175 : // this loop if they are involved in the constraint.
176 91314 : const VariableLimits* limits = limits_[from->id()];
177 151778 : for (const Constraint* constraint = limits->head(); constraint != nullptr;
178 : constraint = constraint->next()) {
179 84680 : if (constraint->left()->opcode() == IrOpcode::kPhi &&
180 25556 : NodeProperties::GetControlInput(constraint->left()) == loop) {
181 65382 : auto var = induction_vars_.find(constraint->left()->id());
182 21794 : if (var != induction_vars_.end()) {
183 21794 : var->second->AddUpperBound(constraint->right(), constraint->kind());
184 : }
185 : }
186 64593 : if (constraint->right()->opcode() == IrOpcode::kPhi &&
187 5469 : NodeProperties::GetControlInput(constraint->right()) == loop) {
188 5802 : auto var = induction_vars_.find(constraint->right()->id());
189 1934 : if (var != induction_vars_.end()) {
190 1475 : var->second->AddLowerBound(constraint->left(), constraint->kind());
191 : }
192 : }
193 : }
194 : }
195 :
196 6772851 : void LoopVariableOptimizer::VisitNode(Node* node) {
197 6772851 : switch (node->opcode()) {
198 : case IrOpcode::kMerge:
199 411815 : return VisitMerge(node);
200 : case IrOpcode::kLoop:
201 : return VisitLoop(node);
202 : case IrOpcode::kIfFalse:
203 732123 : return VisitIf(node, false);
204 : case IrOpcode::kIfTrue:
205 732123 : return VisitIf(node, true);
206 : case IrOpcode::kStart:
207 395343 : return VisitStart(node);
208 : case IrOpcode::kLoopExit:
209 : return VisitLoopExit(node);
210 : default:
211 : return VisitOtherControl(node);
212 : }
213 : }
214 :
215 411815 : void LoopVariableOptimizer::VisitMerge(Node* node) {
216 : // Merge the limits of all incoming edges.
217 2363943 : VariableLimits* merged = limits_[node->InputAt(0)->id()]->Copy(zone());
218 2256996 : for (int i = 1; i < node->InputCount(); i++) {
219 2150049 : merged->Merge(limits_[node->InputAt(i)->id()]);
220 : }
221 823630 : limits_[node->id()] = merged;
222 411815 : }
223 :
224 0 : void LoopVariableOptimizer::VisitLoop(Node* node) {
225 45657 : DetectInductionVariables(node);
226 : // Conservatively take the limits from the loop entry here.
227 45657 : return TakeConditionsFromFirstControl(node);
228 : }
229 :
230 4392738 : void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
231 : Node* branch = node->InputAt(0);
232 1464246 : Node* cond = branch->InputAt(0);
233 4392738 : VariableLimits* limits = limits_[branch->id()]->Copy(zone());
234 : // Normalize to less than comparison.
235 1464246 : switch (cond->opcode()) {
236 : case IrOpcode::kJSLessThan:
237 : case IrOpcode::kSpeculativeNumberLessThan:
238 129742 : AddCmpToLimits(limits, cond, InductionVariable::kStrict, polarity);
239 129742 : break;
240 : case IrOpcode::kJSGreaterThan:
241 13750 : AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, !polarity);
242 13750 : break;
243 : case IrOpcode::kJSLessThanOrEqual:
244 : case IrOpcode::kSpeculativeNumberLessThanOrEqual:
245 5908 : AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, polarity);
246 5908 : break;
247 : case IrOpcode::kJSGreaterThanOrEqual:
248 6024 : AddCmpToLimits(limits, cond, InductionVariable::kStrict, !polarity);
249 6024 : break;
250 : default:
251 : break;
252 : }
253 2928492 : limits_[node->id()] = limits;
254 1464246 : }
255 :
256 155424 : void LoopVariableOptimizer::AddCmpToLimits(
257 : VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
258 104978 : bool polarity) {
259 : Node* left = node->InputAt(0);
260 : Node* right = node->InputAt(1);
261 155424 : if (FindInductionVariable(left) || FindInductionVariable(right)) {
262 104978 : if (polarity) {
263 : limits->Add(left, kind, right, zone());
264 : } else {
265 : kind = (kind == InductionVariable::kStrict)
266 : ? InductionVariable::kNonStrict
267 52489 : : InductionVariable::kStrict;
268 : limits->Add(right, kind, left, zone());
269 : }
270 : }
271 155424 : }
272 :
273 790686 : void LoopVariableOptimizer::VisitStart(Node* node) {
274 790686 : limits_[node->id()] = VariableLimits::Empty(zone());
275 395343 : }
276 :
277 0 : void LoopVariableOptimizer::VisitLoopExit(Node* node) {
278 149306 : return TakeConditionsFromFirstControl(node);
279 : }
280 :
281 0 : void LoopVariableOptimizer::VisitOtherControl(Node* node) {
282 : DCHECK_EQ(1, node->op()->ControlInputCount());
283 4306484 : return TakeConditionsFromFirstControl(node);
284 : }
285 :
286 9002894 : void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
287 : const VariableLimits* limits =
288 13504341 : limits_[NodeProperties::GetControlInput(node, 0)->id()];
289 : DCHECK_NOT_NULL(limits);
290 9002894 : limits_[node->id()] = limits;
291 4501447 : }
292 :
293 207604 : const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
294 207604 : Node* node) {
295 415208 : auto var = induction_vars_.find(node->id());
296 207604 : if (var != induction_vars_.end()) {
297 104978 : return var->second;
298 : }
299 : return nullptr;
300 : }
301 :
302 124962 : InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
303 : DCHECK_EQ(2, phi->op()->ValueInputCount());
304 : DCHECK_EQ(IrOpcode::kLoop, NodeProperties::GetControlInput(phi)->opcode());
305 : Node* initial = phi->InputAt(0);
306 96206 : Node* arith = phi->InputAt(1);
307 : InductionVariable::ArithmeticType arithmeticType;
308 96206 : if (arith->opcode() == IrOpcode::kJSAdd ||
309 : arith->opcode() == IrOpcode::kSpeculativeNumberAdd) {
310 : arithmeticType = InductionVariable::ArithmeticType::kAddition;
311 88554 : } else if (arith->opcode() == IrOpcode::kJSSubtract ||
312 : arith->opcode() == IrOpcode::kSpeculativeNumberSubtract) {
313 : arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
314 : } else {
315 : return nullptr;
316 : }
317 :
318 : // TODO(jarin) Support both sides.
319 40114 : if (arith->InputAt(0) != phi) {
320 38655 : if ((arith->InputAt(0)->opcode() != IrOpcode::kJSToNumber &&
321 27297 : arith->InputAt(0)->opcode() != IrOpcode::kSpeculativeToNumber) ||
322 : arith->InputAt(0)->InputAt(0) != phi) {
323 : return nullptr;
324 : }
325 : }
326 : Node* incr = arith->InputAt(1);
327 : return new (zone())
328 28756 : InductionVariable(phi, arith, incr, initial, zone(), arithmeticType);
329 : }
330 :
331 45657 : void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
332 91314 : if (loop->op()->ControlInputCount() != 2) return;
333 45657 : TRACE("Loop variables for loop %i:", loop->id());
334 961645 : for (Edge edge : loop->use_edges()) {
335 915988 : if (NodeProperties::IsControlEdge(edge) &&
336 457994 : edge.from()->opcode() == IrOpcode::kPhi) {
337 28756 : Node* phi = edge.from();
338 96206 : InductionVariable* induction_var = TryGetInductionVariable(phi);
339 96206 : if (induction_var) {
340 28756 : induction_vars_[phi->id()] = induction_var;
341 28756 : TRACE(" %i", induction_var->phi()->id());
342 : }
343 : }
344 : }
345 45657 : TRACE("\n");
346 : }
347 :
348 464694 : void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
349 819442 : for (auto entry : induction_vars_) {
350 : // It only make sense to analyze the induction variables if
351 : // there is a bound.
352 92392 : InductionVariable* induction_var = entry.second;
353 : DCHECK_EQ(MachineRepresentation::kTagged,
354 : PhiRepresentationOf(induction_var->phi()->op()));
355 64552 : if (induction_var->upper_bounds().size() == 0 &&
356 7040 : induction_var->lower_bounds().size() == 0) {
357 : continue;
358 : }
359 : // Insert the increment value to the value inputs.
360 : induction_var->phi()->InsertInput(graph()->zone(),
361 : induction_var->phi()->InputCount() - 1,
362 46082 : induction_var->increment());
363 : // Insert the bound inputs to the value inputs.
364 47557 : for (auto bound : induction_var->lower_bounds()) {
365 : induction_var->phi()->InsertInput(
366 2950 : graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
367 : }
368 67876 : for (auto bound : induction_var->upper_bounds()) {
369 : induction_var->phi()->InsertInput(
370 43588 : graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
371 : }
372 : NodeProperties::ChangeOp(
373 : induction_var->phi(),
374 69123 : common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
375 : }
376 395343 : }
377 :
378 434582 : void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
379 819442 : for (auto entry : induction_vars_) {
380 137118 : InductionVariable* induction_var = entry.second;
381 57512 : if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
382 : // Turn the induction variable phi back to normal phi.
383 : int value_count = 2;
384 23041 : Node* control = NodeProperties::GetControlInput(induction_var->phi());
385 : DCHECK_EQ(value_count, control->op()->ControlInputCount());
386 23041 : induction_var->phi()->TrimInputCount(value_count + 1);
387 23041 : induction_var->phi()->ReplaceInput(value_count, control);
388 : NodeProperties::ChangeOp(
389 : induction_var->phi(),
390 46082 : common()->Phi(MachineRepresentation::kTagged, value_count));
391 :
392 : // If the backedge is not a subtype of the phi's type, we insert a sigma
393 : // to get the typing right.
394 : Node* backedge_value = induction_var->phi()->InputAt(1);
395 : Type* backedge_type = NodeProperties::GetType(backedge_value);
396 : Type* phi_type = NodeProperties::GetType(induction_var->phi());
397 23041 : if (!backedge_type->Is(phi_type)) {
398 : Node* backedge_control =
399 8099 : NodeProperties::GetControlInput(induction_var->phi())->InputAt(1);
400 : Node* rename = graph()->NewNode(common()->TypeGuard(phi_type),
401 8099 : backedge_value, backedge_control);
402 8099 : induction_var->phi()->ReplaceInput(1, rename);
403 : }
404 : }
405 : }
406 395343 : }
407 :
408 : } // namespace compiler
409 : } // namespace internal
410 : } // namespace v8
|
