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 886762 : 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 886763 : induction_vars_(zone) {}
33 :
34 1330144 : void LoopVariableOptimizer::Run() {
35 443382 : ZoneQueue<Node*> queue(zone());
36 886762 : queue.push(graph()->start());
37 : NodeMarker<bool> queued(graph(), 2);
38 7305492 : while (!queue.empty()) {
39 13724220 : 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 6862110 : : node->op()->ControlInputCount();
48 15490974 : for (int i = 0; i < inputs_end; i++) {
49 27158817 : if (limits_[NodeProperties::GetControlInput(node, i)->id()] == nullptr) {
50 : all_inputs_visited = false;
51 : break;
52 : }
53 : }
54 6862113 : if (!all_inputs_visited) continue;
55 :
56 6438036 : VisitNode(node);
57 : DCHECK_NOT_NULL(limits_[node->id()]);
58 :
59 : // Queue control outputs.
60 70854656 : for (Edge edge : node->use_edges()) {
61 45256053 : if (NodeProperties::IsControlEdge(edge) &&
62 13047743 : edge.from()->op()->ControlOutputCount() > 0) {
63 6577200 : Node* use = edge.from();
64 13239606 : if (use->opcode() == IrOpcode::kLoop &&
65 85206 : edge.index() != kAssumedLoopEntryIndex) {
66 42603 : VisitBackedge(node, use);
67 6534597 : } else if (!queued.Get(use)) {
68 : queue.push(use);
69 6418730 : queued.Set(use, true);
70 : }
71 : }
72 : }
73 : }
74 443382 : }
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 113480 : : 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 226960 : head_ = new (zone) Constraint(left, kind, right, head_);
108 113480 : limit_count_++;
109 : }
110 :
111 431211 : 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 431211 : size_t other_size = other->limit_count_;
119 472510 : const Constraint* other_limit = other->head_;
120 869789 : while (other_size > limit_count_) {
121 : other_limit = other_limit->next();
122 7367 : other_size--;
123 : }
124 431330 : while (limit_count_ > other_size) {
125 34051 : head_ = head_->next();
126 119 : limit_count_--;
127 : }
128 :
129 : // Then we go through both lists in lock-step until we find
130 : // the common tail.
131 465143 : while (head_ != other_limit) {
132 : DCHECK_LT(0, limit_count_);
133 33932 : limit_count_--;
134 : other_limit = other_limit->next();
135 33932 : head_ = head_->next();
136 : }
137 431211 : }
138 :
139 : const Constraint* head() const { return head_; }
140 :
141 : private:
142 443382 : VariableLimits() {}
143 : explicit VariableLimits(const VariableLimits* other)
144 1427504 : : head_(other->head_), limit_count_(other->limit_count_) {}
145 :
146 : const Constraint* head_ = nullptr;
147 : size_t limit_count_ = 0;
148 : };
149 :
150 22622 : void InductionVariable::AddUpperBound(Node* bound,
151 0 : InductionVariable::ConstraintKind kind) {
152 22622 : 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 45244 : upper_bounds_.push_back(Bound(bound, kind));
159 22622 : }
160 :
161 1082 : void InductionVariable::AddLowerBound(Node* bound,
162 0 : InductionVariable::ConstraintKind kind) {
163 1082 : 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 2164 : lower_bounds_.push_back(Bound(bound, kind));
169 1082 : }
170 :
171 85206 : void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
172 85206 : 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 85206 : const VariableLimits* limits = limits_[from->id()];
177 148862 : for (const Constraint* constraint = limits->head(); constraint != nullptr;
178 : constraint = constraint->next()) {
179 83836 : if (constraint->left()->opcode() == IrOpcode::kPhi &&
180 25370 : NodeProperties::GetControlInput(constraint->left()) == loop) {
181 67866 : auto var = induction_vars_.find(constraint->left()->id());
182 22622 : if (var != induction_vars_.end()) {
183 22622 : var->second->AddUpperBound(constraint->right(), constraint->kind());
184 : }
185 : }
186 63480 : if (constraint->right()->opcode() == IrOpcode::kPhi &&
187 5014 : NodeProperties::GetControlInput(constraint->right()) == loop) {
188 4401 : auto var = induction_vars_.find(constraint->right()->id());
189 1467 : if (var != induction_vars_.end()) {
190 1082 : var->second->AddLowerBound(constraint->left(), constraint->kind());
191 : }
192 : }
193 : }
194 : }
195 :
196 6438043 : void LoopVariableOptimizer::VisitNode(Node* node) {
197 6438043 : switch (node->opcode()) {
198 : case IrOpcode::kMerge:
199 273712 : return VisitMerge(node);
200 : case IrOpcode::kLoop:
201 : return VisitLoop(node);
202 : case IrOpcode::kIfFalse:
203 576896 : return VisitIf(node, false);
204 : case IrOpcode::kIfTrue:
205 576896 : return VisitIf(node, true);
206 : case IrOpcode::kStart:
207 443380 : return VisitStart(node);
208 : case IrOpcode::kLoopExit:
209 : return VisitLoopExit(node);
210 : default:
211 : return VisitOtherControl(node);
212 : }
213 : }
214 :
215 273712 : void LoopVariableOptimizer::VisitMerge(Node* node) {
216 : // Merge the limits of all incoming edges.
217 1526059 : VariableLimits* merged = limits_[node->InputAt(0)->id()]->Copy(zone());
218 1409846 : for (int i = 1; i < node->InputCount(); i++) {
219 1293633 : merged->Merge(limits_[node->InputAt(i)->id()]);
220 : }
221 547424 : limits_[node->id()] = merged;
222 273712 : }
223 :
224 0 : void LoopVariableOptimizer::VisitLoop(Node* node) {
225 42603 : DetectInductionVariables(node);
226 : // Conservatively take the limits from the loop entry here.
227 42603 : return TakeConditionsFromFirstControl(node);
228 : }
229 :
230 3461376 : void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
231 : Node* branch = node->InputAt(0);
232 1153792 : Node* cond = branch->InputAt(0);
233 3461376 : VariableLimits* limits = limits_[branch->id()]->Copy(zone());
234 : // Normalize to less than comparison.
235 1153792 : switch (cond->opcode()) {
236 : case IrOpcode::kJSLessThan:
237 : case IrOpcode::kSpeculativeNumberLessThan:
238 129070 : AddCmpToLimits(limits, cond, InductionVariable::kStrict, polarity);
239 129070 : break;
240 : case IrOpcode::kJSGreaterThan:
241 20460 : AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, !polarity);
242 20460 : break;
243 : case IrOpcode::kJSLessThanOrEqual:
244 : case IrOpcode::kSpeculativeNumberLessThanOrEqual:
245 6344 : AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, polarity);
246 6344 : break;
247 : case IrOpcode::kJSGreaterThanOrEqual:
248 4332 : AddCmpToLimits(limits, cond, InductionVariable::kStrict, !polarity);
249 4332 : break;
250 : default:
251 : break;
252 : }
253 2307584 : limits_[node->id()] = limits;
254 1153792 : }
255 :
256 160206 : void LoopVariableOptimizer::AddCmpToLimits(
257 : VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
258 113480 : bool polarity) {
259 : Node* left = node->InputAt(0);
260 : Node* right = node->InputAt(1);
261 160206 : if (FindInductionVariable(left) || FindInductionVariable(right)) {
262 113480 : if (polarity) {
263 : limits->Add(left, kind, right, zone());
264 : } else {
265 : kind = (kind == InductionVariable::kStrict)
266 : ? InductionVariable::kNonStrict
267 56740 : : InductionVariable::kStrict;
268 : limits->Add(right, kind, left, zone());
269 : }
270 : }
271 160206 : }
272 :
273 886762 : void LoopVariableOptimizer::VisitStart(Node* node) {
274 886763 : limits_[node->id()] = VariableLimits::Empty(zone());
275 443382 : }
276 :
277 0 : void LoopVariableOptimizer::VisitLoopExit(Node* node) {
278 108738 : return TakeConditionsFromFirstControl(node);
279 : }
280 :
281 0 : void LoopVariableOptimizer::VisitOtherControl(Node* node) {
282 : DCHECK_EQ(1, node->op()->ControlInputCount());
283 4415818 : return TakeConditionsFromFirstControl(node);
284 : }
285 :
286 9134319 : void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
287 : const VariableLimits* limits =
288 13701479 : limits_[NodeProperties::GetControlInput(node, 0)->id()];
289 : DCHECK_NOT_NULL(limits);
290 9134320 : limits_[node->id()] = limits;
291 4567160 : }
292 :
293 216650 : const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
294 216650 : Node* node) {
295 433300 : auto var = induction_vars_.find(node->id());
296 216650 : if (var != induction_vars_.end()) {
297 113480 : return var->second;
298 : }
299 : return nullptr;
300 : }
301 :
302 105268 : 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 73860 : Node* arith = phi->InputAt(1);
307 : InductionVariable::ArithmeticType arithmeticType;
308 145223 : if (arith->opcode() == IrOpcode::kJSAdd ||
309 144808 : arith->opcode() == IrOpcode::kSpeculativeNumberAdd ||
310 : arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) {
311 : arithmeticType = InductionVariable::ArithmeticType::kAddition;
312 120298 : } else if (arith->opcode() == IrOpcode::kJSSubtract ||
313 119999 : arith->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
314 : arith->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract) {
315 : arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
316 : } else {
317 : return nullptr;
318 : }
319 :
320 : // TODO(jarin) Support both sides.
321 33252 : if (arith->InputAt(0) != phi) {
322 14092 : if ((arith->InputAt(0)->opcode() != IrOpcode::kJSToNumber &&
323 12256 : arith->InputAt(0)->opcode() != IrOpcode::kSpeculativeToNumber) ||
324 : arith->InputAt(0)->InputAt(0) != phi) {
325 : return nullptr;
326 : }
327 : }
328 : Node* incr = arith->InputAt(1);
329 : return new (zone())
330 31408 : InductionVariable(phi, arith, incr, initial, zone(), arithmeticType);
331 : }
332 :
333 42603 : void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
334 85206 : if (loop->op()->ControlInputCount() != 2) return;
335 42603 : TRACE("Loop variables for loop %i:", loop->id());
336 809597 : for (Edge edge : loop->use_edges()) {
337 766994 : if (NodeProperties::IsControlEdge(edge) &&
338 383497 : edge.from()->opcode() == IrOpcode::kPhi) {
339 31408 : Node* phi = edge.from();
340 73860 : InductionVariable* induction_var = TryGetInductionVariable(phi);
341 73860 : if (induction_var) {
342 31408 : induction_vars_[phi->id()] = induction_var;
343 31408 : TRACE(" %i", induction_var->phi()->id());
344 : }
345 : }
346 : }
347 42603 : TRACE("\n");
348 : }
349 :
350 514098 : void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
351 918168 : for (auto entry : induction_vars_) {
352 : // It only make sense to analyze the induction variables if
353 : // there is a bound.
354 94225 : InductionVariable* induction_var = entry.second;
355 : DCHECK_EQ(MachineRepresentation::kTagged,
356 : PhiRepresentationOf(induction_var->phi()->op()));
357 71702 : if (induction_var->upper_bounds().size() == 0 &&
358 8886 : induction_var->lower_bounds().size() == 0) {
359 : continue;
360 : }
361 : // Insert the increment value to the value inputs.
362 : induction_var->phi()->InsertInput(graph()->zone(),
363 : induction_var->phi()->InputCount() - 1,
364 47014 : induction_var->increment());
365 : // Insert the bound inputs to the value inputs.
366 48096 : for (auto bound : induction_var->lower_bounds()) {
367 : induction_var->phi()->InsertInput(
368 2164 : graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
369 : }
370 69636 : for (auto bound : induction_var->upper_bounds()) {
371 : induction_var->phi()->InsertInput(
372 45244 : graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
373 : }
374 : NodeProperties::ChangeOp(
375 : induction_var->phi(),
376 70521 : common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
377 : }
378 443380 : }
379 :
380 486803 : void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
381 918170 : for (auto entry : induction_vars_) {
382 145350 : InductionVariable* induction_var = entry.second;
383 62816 : if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
384 : // Turn the induction variable phi back to normal phi.
385 : int value_count = 2;
386 23507 : Node* control = NodeProperties::GetControlInput(induction_var->phi());
387 : DCHECK_EQ(value_count, control->op()->ControlInputCount());
388 23507 : induction_var->phi()->TrimInputCount(value_count + 1);
389 23507 : induction_var->phi()->ReplaceInput(value_count, control);
390 : NodeProperties::ChangeOp(
391 : induction_var->phi(),
392 47014 : common()->Phi(MachineRepresentation::kTagged, value_count));
393 :
394 : // If the backedge is not a subtype of the phi's type, we insert a sigma
395 : // to get the typing right.
396 : Node* backedge_value = induction_var->phi()->InputAt(1);
397 : Type* backedge_type = NodeProperties::GetType(backedge_value);
398 : Type* phi_type = NodeProperties::GetType(induction_var->phi());
399 23507 : if (!backedge_type->Is(phi_type)) {
400 : Node* backedge_control =
401 9957 : NodeProperties::GetControlInput(induction_var->phi())->InputAt(1);
402 : Node* rename = graph()->NewNode(common()->TypeGuard(phi_type),
403 9957 : backedge_value, backedge_control);
404 9957 : induction_var->phi()->ReplaceInput(1, rename);
405 : }
406 : }
407 : }
408 443380 : }
409 :
410 : #undef TRACE
411 :
412 : } // namespace compiler
413 : } // namespace internal
414 : } // namespace v8
|
