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 1370088 : 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 : reduced_(graph->NodeCount(), zone),
33 913393 : induction_vars_(zone) {}
34 :
35 1370090 : void LoopVariableOptimizer::Run() {
36 456696 : ZoneQueue<Node*> queue(zone());
37 913394 : queue.push(graph()->start());
38 : NodeMarker<bool> queued(graph(), 2);
39 8268457 : while (!queue.empty()) {
40 15623520 : Node* node = queue.front();
41 : queue.pop();
42 : queued.Set(node, false);
43 :
44 : DCHECK(!reduced_.Get(node));
45 : bool all_inputs_visited = true;
46 : int inputs_end = (node->opcode() == IrOpcode::kLoop)
47 : ? kFirstBackedge
48 7811760 : : node->op()->ControlInputCount();
49 18356759 : for (int i = 0; i < inputs_end; i++) {
50 11036440 : if (!reduced_.Get(NodeProperties::GetControlInput(node, i))) {
51 : all_inputs_visited = false;
52 : break;
53 : }
54 : }
55 7811761 : if (!all_inputs_visited) continue;
56 :
57 7320317 : VisitNode(node);
58 7320311 : reduced_.Set(node, true);
59 :
60 : // Queue control outputs.
61 89864959 : for (Edge edge : node->use_edges()) {
62 53828897 : if (NodeProperties::IsControlEdge(edge) &&
63 16216738 : edge.from()->op()->ControlOutputCount() > 0) {
64 7555609 : Node* use = edge.from();
65 15197578 : if (use->opcode() == IrOpcode::kLoop &&
66 86360 : edge.index() != kAssumedLoopEntryIndex) {
67 43180 : VisitBackedge(node, use);
68 7512425 : } else if (!queued.Get(use)) {
69 : queue.push(use);
70 7355060 : queued.Set(use, true);
71 : }
72 : }
73 : }
74 : }
75 456697 : }
76 :
77 12240 : void InductionVariable::AddUpperBound(Node* bound,
78 0 : InductionVariable::ConstraintKind kind) {
79 12240 : if (FLAG_trace_turbo_loop) {
80 0 : StdoutStream{} << "New upper bound for " << phi()->id() << " (loop "
81 0 : << NodeProperties::GetControlInput(phi())->id()
82 0 : << "): " << *bound << std::endl;
83 : }
84 24480 : upper_bounds_.push_back(Bound(bound, kind));
85 12240 : }
86 :
87 528 : void InductionVariable::AddLowerBound(Node* bound,
88 0 : InductionVariable::ConstraintKind kind) {
89 528 : if (FLAG_trace_turbo_loop) {
90 0 : StdoutStream{} << "New lower bound for " << phi()->id() << " (loop "
91 0 : << NodeProperties::GetControlInput(phi())->id()
92 0 : << "): " << *bound;
93 : }
94 1056 : lower_bounds_.push_back(Bound(bound, kind));
95 528 : }
96 :
97 43180 : void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
98 86360 : if (loop->op()->ControlInputCount() != 2) return;
99 :
100 : // Go through the constraints, and update the induction variables in
101 : // this loop if they are involved in the constraint.
102 104089 : for (Constraint constraint : limits_.Get(from)) {
103 50894 : if (constraint.left->opcode() == IrOpcode::kPhi &&
104 15436 : NodeProperties::GetControlInput(constraint.left) == loop) {
105 24480 : auto var = induction_vars_.find(constraint.left->id());
106 12240 : if (var != induction_vars_.end()) {
107 12768 : var->second->AddUpperBound(constraint.right, constraint.kind);
108 : }
109 : }
110 20266 : if (constraint.right->opcode() == IrOpcode::kPhi &&
111 2537 : NodeProperties::GetControlInput(constraint.right) == loop) {
112 1056 : auto var = induction_vars_.find(constraint.right->id());
113 528 : if (var != induction_vars_.end()) {
114 528 : var->second->AddLowerBound(constraint.left, constraint.kind);
115 : }
116 : }
117 : }
118 : }
119 :
120 7320336 : void LoopVariableOptimizer::VisitNode(Node* node) {
121 7320336 : switch (node->opcode()) {
122 : case IrOpcode::kMerge:
123 263675 : return VisitMerge(node);
124 : case IrOpcode::kLoop:
125 : return VisitLoop(node);
126 : case IrOpcode::kIfFalse:
127 616230 : return VisitIf(node, false);
128 : case IrOpcode::kIfTrue:
129 616231 : return VisitIf(node, true);
130 : case IrOpcode::kStart:
131 : return VisitStart(node);
132 : case IrOpcode::kLoopExit:
133 : return VisitLoopExit(node);
134 : default:
135 : return VisitOtherControl(node);
136 : }
137 : }
138 :
139 263674 : void LoopVariableOptimizer::VisitMerge(Node* node) {
140 : // Merge the limits of all incoming edges.
141 263674 : VariableLimits merged = limits_.Get(node->InputAt(0));
142 1494028 : for (int i = 1; i < node->InputCount(); i++) {
143 483340 : merged.ResetToCommonAncestor(limits_.Get(node->InputAt(i)));
144 : }
145 263674 : limits_.Set(node, merged);
146 263674 : }
147 :
148 0 : void LoopVariableOptimizer::VisitLoop(Node* node) {
149 43180 : DetectInductionVariables(node);
150 : // Conservatively take the limits from the loop entry here.
151 43180 : return TakeConditionsFromFirstControl(node);
152 : }
153 :
154 1232458 : void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
155 : Node* branch = node->InputAt(0);
156 1232458 : Node* cond = branch->InputAt(0);
157 1232458 : VariableLimits limits = limits_.Get(branch);
158 : // Normalize to less than comparison.
159 1232458 : switch (cond->opcode()) {
160 : case IrOpcode::kJSLessThan:
161 : case IrOpcode::kNumberLessThan:
162 : case IrOpcode::kSpeculativeNumberLessThan:
163 126337 : AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity);
164 126336 : break;
165 : case IrOpcode::kJSGreaterThan:
166 23436 : AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity);
167 23436 : break;
168 : case IrOpcode::kJSLessThanOrEqual:
169 : case IrOpcode::kNumberLessThanOrEqual:
170 : case IrOpcode::kSpeculativeNumberLessThanOrEqual:
171 5388 : AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, polarity);
172 5388 : break;
173 : case IrOpcode::kJSGreaterThanOrEqual:
174 2368 : AddCmpToLimits(&limits, cond, InductionVariable::kStrict, !polarity);
175 2368 : break;
176 : default:
177 : break;
178 : }
179 1232457 : limits_.Set(node, limits);
180 1232457 : }
181 :
182 157529 : void LoopVariableOptimizer::AddCmpToLimits(
183 : VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
184 83218 : bool polarity) {
185 : Node* left = node->InputAt(0);
186 : Node* right = node->InputAt(1);
187 157529 : if (FindInductionVariable(left) || FindInductionVariable(right)) {
188 83218 : if (polarity) {
189 41609 : limits->PushFront(Constraint{left, kind, right}, zone());
190 : } else {
191 : kind = (kind == InductionVariable::kStrict)
192 : ? InductionVariable::kNonStrict
193 41609 : : InductionVariable::kStrict;
194 41609 : limits->PushFront(Constraint{right, kind, left}, zone());
195 : }
196 : }
197 157528 : }
198 :
199 456697 : void LoopVariableOptimizer::VisitStart(Node* node) { limits_.Set(node, {}); }
200 :
201 0 : void LoopVariableOptimizer::VisitLoopExit(Node* node) {
202 165480 : return TakeConditionsFromFirstControl(node);
203 : }
204 :
205 0 : void LoopVariableOptimizer::VisitOtherControl(Node* node) {
206 : DCHECK_EQ(1, node->op()->ControlInputCount());
207 5158843 : return TakeConditionsFromFirstControl(node);
208 : }
209 :
210 5367501 : void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
211 10735003 : limits_.Set(node, limits_.Get(NodeProperties::GetControlInput(node, 0)));
212 5367502 : }
213 :
214 233083 : const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
215 233083 : Node* node) {
216 466165 : auto var = induction_vars_.find(node->id());
217 233082 : if (var != induction_vars_.end()) {
218 83214 : return var->second;
219 : }
220 : return nullptr;
221 : }
222 :
223 86221 : InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
224 : DCHECK_EQ(2, phi->op()->ValueInputCount());
225 68028 : Node* loop = NodeProperties::GetControlInput(phi);
226 : DCHECK_EQ(IrOpcode::kLoop, loop->opcode());
227 : Node* initial = phi->InputAt(0);
228 68028 : Node* arith = phi->InputAt(1);
229 : InductionVariable::ArithmeticType arithmeticType;
230 134144 : if (arith->opcode() == IrOpcode::kJSAdd ||
231 64146 : arith->opcode() == IrOpcode::kNumberAdd ||
232 131588 : arith->opcode() == IrOpcode::kSpeculativeNumberAdd ||
233 : arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) {
234 : arithmeticType = InductionVariable::ArithmeticType::kAddition;
235 96864 : } else if (arith->opcode() == IrOpcode::kJSSubtract ||
236 48121 : arith->opcode() == IrOpcode::kNumberSubtract ||
237 96568 : arith->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
238 : arith->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract) {
239 : arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
240 : } else {
241 : return nullptr;
242 : }
243 :
244 : // TODO(jarin) Support both sides.
245 21408 : Node* input = arith->InputAt(0);
246 41402 : if (input->opcode() == IrOpcode::kSpeculativeToNumber ||
247 41402 : input->opcode() == IrOpcode::kJSToNumber ||
248 : input->opcode() == IrOpcode::kJSToNumberConvertBigInt) {
249 : input = input->InputAt(0);
250 : }
251 21408 : if (input != phi) return nullptr;
252 :
253 : Node* effect_phi = nullptr;
254 373950 : for (Node* use : loop->uses()) {
255 168782 : if (use->opcode() == IrOpcode::kEffectPhi) {
256 : DCHECK_NULL(effect_phi);
257 : effect_phi = use;
258 : }
259 : }
260 18193 : if (!effect_phi) return nullptr;
261 :
262 : Node* incr = arith->InputAt(1);
263 : return new (zone()) InductionVariable(phi, effect_phi, arith, incr, initial,
264 18193 : zone(), arithmeticType);
265 : }
266 :
267 43180 : void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
268 86360 : if (loop->op()->ControlInputCount() != 2) return;
269 43180 : TRACE("Loop variables for loop %i:", loop->id());
270 964210 : for (Edge edge : loop->use_edges()) {
271 877850 : if (NodeProperties::IsControlEdge(edge) &&
272 438925 : edge.from()->opcode() == IrOpcode::kPhi) {
273 18193 : Node* phi = edge.from();
274 68028 : InductionVariable* induction_var = TryGetInductionVariable(phi);
275 68028 : if (induction_var) {
276 18193 : induction_vars_[phi->id()] = induction_var;
277 18193 : TRACE(" %i", induction_var->phi()->id());
278 : }
279 : }
280 : }
281 43180 : TRACE("\n");
282 : }
283 :
284 494699 : void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
285 931583 : for (auto entry : induction_vars_) {
286 : // It only make sense to analyze the induction variables if
287 : // there is a bound.
288 50622 : InductionVariable* induction_var = entry.second;
289 : DCHECK_EQ(MachineRepresentation::kTagged,
290 : PhiRepresentationOf(induction_var->phi()->op()));
291 42409 : if (induction_var->upper_bounds().size() == 0 &&
292 6023 : induction_var->lower_bounds().size() == 0) {
293 : continue;
294 : }
295 : // Insert the increment value to the value inputs.
296 : induction_var->phi()->InsertInput(graph()->zone(),
297 : induction_var->phi()->InputCount() - 1,
298 25236 : induction_var->increment());
299 : // Insert the bound inputs to the value inputs.
300 25764 : for (auto bound : induction_var->lower_bounds()) {
301 : induction_var->phi()->InsertInput(
302 1056 : graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
303 : }
304 37476 : for (auto bound : induction_var->upper_bounds()) {
305 : induction_var->phi()->InsertInput(
306 24480 : graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
307 : }
308 : NodeProperties::ChangeOp(
309 : induction_var->phi(),
310 37854 : common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
311 : }
312 456695 : }
313 :
314 485088 : void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
315 931580 : for (auto entry : induction_vars_) {
316 112835 : InductionVariable* induction_var = entry.second;
317 36386 : if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
318 : // Turn the induction variable phi back to normal phi.
319 : int value_count = 2;
320 12618 : Node* control = NodeProperties::GetControlInput(induction_var->phi());
321 : DCHECK_EQ(value_count, control->op()->ControlInputCount());
322 12618 : induction_var->phi()->TrimInputCount(value_count + 1);
323 12618 : induction_var->phi()->ReplaceInput(value_count, control);
324 : NodeProperties::ChangeOp(
325 : induction_var->phi(),
326 25236 : common()->Phi(MachineRepresentation::kTagged, value_count));
327 :
328 : // If the backedge is not a subtype of the phi's type, we insert a sigma
329 : // to get the typing right.
330 : Node* backedge_value = induction_var->phi()->InputAt(1);
331 12618 : Type backedge_type = NodeProperties::GetType(backedge_value);
332 : Type phi_type = NodeProperties::GetType(induction_var->phi());
333 12618 : if (!backedge_type.Is(phi_type)) {
334 7888 : Node* loop = NodeProperties::GetControlInput(induction_var->phi());
335 : Node* backedge_control = loop->InputAt(1);
336 : Node* backedge_effect =
337 7888 : NodeProperties::GetEffectInput(induction_var->effect_phi(), 1);
338 : Node* rename =
339 : graph()->NewNode(common()->TypeGuard(phi_type), backedge_value,
340 7888 : backedge_effect, backedge_control);
341 7888 : induction_var->effect_phi()->ReplaceInput(1, rename);
342 7888 : induction_var->phi()->ReplaceInput(1, rename);
343 : }
344 : }
345 : }
346 456693 : }
347 :
348 : #undef TRACE
349 :
350 : } // namespace compiler
351 : } // namespace internal
352 178779 : } // namespace v8
|
