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
LoopVariableOptimizer(Graph * graph,CommonOperatorBuilder * common,Zone * zone)25 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 induction_vars_(zone) {}
34
Run()35 void LoopVariableOptimizer::Run() {
36 ZoneQueue<Node*> queue(zone());
37 queue.push(graph()->start());
38 NodeMarker<bool> queued(graph(), 2);
39 while (!queue.empty()) {
40 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 : node->op()->ControlInputCount();
49 for (int i = 0; i < inputs_end; i++) {
50 if (!reduced_.Get(NodeProperties::GetControlInput(node, i))) {
51 all_inputs_visited = false;
52 break;
53 }
54 }
55 if (!all_inputs_visited) continue;
56
57 VisitNode(node);
58 reduced_.Set(node, true);
59
60 // Queue control outputs.
61 for (Edge edge : node->use_edges()) {
62 if (NodeProperties::IsControlEdge(edge) &&
63 edge.from()->op()->ControlOutputCount() > 0) {
64 Node* use = edge.from();
65 if (use->opcode() == IrOpcode::kLoop &&
66 edge.index() != kAssumedLoopEntryIndex) {
67 VisitBackedge(node, use);
68 } else if (!queued.Get(use)) {
69 queue.push(use);
70 queued.Set(use, true);
71 }
72 }
73 }
74 }
75 }
76
AddUpperBound(Node * bound,InductionVariable::ConstraintKind kind)77 void InductionVariable::AddUpperBound(Node* bound,
78 InductionVariable::ConstraintKind kind) {
79 if (FLAG_trace_turbo_loop) {
80 StdoutStream{} << "New upper bound for " << phi()->id() << " (loop "
81 << NodeProperties::GetControlInput(phi())->id()
82 << "): " << *bound << std::endl;
83 }
84 upper_bounds_.push_back(Bound(bound, kind));
85 }
86
AddLowerBound(Node * bound,InductionVariable::ConstraintKind kind)87 void InductionVariable::AddLowerBound(Node* bound,
88 InductionVariable::ConstraintKind kind) {
89 if (FLAG_trace_turbo_loop) {
90 StdoutStream{} << "New lower bound for " << phi()->id() << " (loop "
91 << NodeProperties::GetControlInput(phi())->id()
92 << "): " << *bound;
93 }
94 lower_bounds_.push_back(Bound(bound, kind));
95 }
96
VisitBackedge(Node * from,Node * loop)97 void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
98 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 for (Constraint constraint : limits_.Get(from)) {
103 if (constraint.left->opcode() == IrOpcode::kPhi &&
104 NodeProperties::GetControlInput(constraint.left) == loop) {
105 auto var = induction_vars_.find(constraint.left->id());
106 if (var != induction_vars_.end()) {
107 var->second->AddUpperBound(constraint.right, constraint.kind);
108 }
109 }
110 if (constraint.right->opcode() == IrOpcode::kPhi &&
111 NodeProperties::GetControlInput(constraint.right) == loop) {
112 auto var = induction_vars_.find(constraint.right->id());
113 if (var != induction_vars_.end()) {
114 var->second->AddLowerBound(constraint.left, constraint.kind);
115 }
116 }
117 }
118 }
119
VisitNode(Node * node)120 void LoopVariableOptimizer::VisitNode(Node* node) {
121 switch (node->opcode()) {
122 case IrOpcode::kMerge:
123 return VisitMerge(node);
124 case IrOpcode::kLoop:
125 return VisitLoop(node);
126 case IrOpcode::kIfFalse:
127 return VisitIf(node, false);
128 case IrOpcode::kIfTrue:
129 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
VisitMerge(Node * node)139 void LoopVariableOptimizer::VisitMerge(Node* node) {
140 // Merge the limits of all incoming edges.
141 VariableLimits merged = limits_.Get(node->InputAt(0));
142 for (int i = 1; i < node->InputCount(); i++) {
143 merged.ResetToCommonAncestor(limits_.Get(node->InputAt(i)));
144 }
145 limits_.Set(node, merged);
146 }
147
VisitLoop(Node * node)148 void LoopVariableOptimizer::VisitLoop(Node* node) {
149 DetectInductionVariables(node);
150 // Conservatively take the limits from the loop entry here.
151 return TakeConditionsFromFirstControl(node);
152 }
153
VisitIf(Node * node,bool polarity)154 void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
155 Node* branch = node->InputAt(0);
156 Node* cond = branch->InputAt(0);
157 VariableLimits limits = limits_.Get(branch);
158 // Normalize to less than comparison.
159 switch (cond->opcode()) {
160 case IrOpcode::kJSLessThan:
161 case IrOpcode::kNumberLessThan:
162 case IrOpcode::kSpeculativeNumberLessThan:
163 AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity);
164 break;
165 case IrOpcode::kJSGreaterThan:
166 AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity);
167 break;
168 case IrOpcode::kJSLessThanOrEqual:
169 case IrOpcode::kNumberLessThanOrEqual:
170 case IrOpcode::kSpeculativeNumberLessThanOrEqual:
171 AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, polarity);
172 break;
173 case IrOpcode::kJSGreaterThanOrEqual:
174 AddCmpToLimits(&limits, cond, InductionVariable::kStrict, !polarity);
175 break;
176 default:
177 break;
178 }
179 limits_.Set(node, limits);
180 }
181
AddCmpToLimits(VariableLimits * limits,Node * node,InductionVariable::ConstraintKind kind,bool polarity)182 void LoopVariableOptimizer::AddCmpToLimits(
183 VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
184 bool polarity) {
185 Node* left = node->InputAt(0);
186 Node* right = node->InputAt(1);
187 if (FindInductionVariable(left) || FindInductionVariable(right)) {
188 if (polarity) {
189 limits->PushFront(Constraint{left, kind, right}, zone());
190 } else {
191 kind = (kind == InductionVariable::kStrict)
192 ? InductionVariable::kNonStrict
193 : InductionVariable::kStrict;
194 limits->PushFront(Constraint{right, kind, left}, zone());
195 }
196 }
197 }
198
VisitStart(Node * node)199 void LoopVariableOptimizer::VisitStart(Node* node) { limits_.Set(node, {}); }
200
VisitLoopExit(Node * node)201 void LoopVariableOptimizer::VisitLoopExit(Node* node) {
202 return TakeConditionsFromFirstControl(node);
203 }
204
VisitOtherControl(Node * node)205 void LoopVariableOptimizer::VisitOtherControl(Node* node) {
206 DCHECK_EQ(1, node->op()->ControlInputCount());
207 return TakeConditionsFromFirstControl(node);
208 }
209
TakeConditionsFromFirstControl(Node * node)210 void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
211 limits_.Set(node, limits_.Get(NodeProperties::GetControlInput(node, 0)));
212 }
213
FindInductionVariable(Node * node)214 const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
215 Node* node) {
216 auto var = induction_vars_.find(node->id());
217 if (var != induction_vars_.end()) {
218 return var->second;
219 }
220 return nullptr;
221 }
222
TryGetInductionVariable(Node * phi)223 InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
224 DCHECK_EQ(2, phi->op()->ValueInputCount());
225 Node* loop = NodeProperties::GetControlInput(phi);
226 DCHECK_EQ(IrOpcode::kLoop, loop->opcode());
227 Node* initial = phi->InputAt(0);
228 Node* arith = phi->InputAt(1);
229 InductionVariable::ArithmeticType arithmeticType;
230 if (arith->opcode() == IrOpcode::kJSAdd ||
231 arith->opcode() == IrOpcode::kNumberAdd ||
232 arith->opcode() == IrOpcode::kSpeculativeNumberAdd ||
233 arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) {
234 arithmeticType = InductionVariable::ArithmeticType::kAddition;
235 } else if (arith->opcode() == IrOpcode::kJSSubtract ||
236 arith->opcode() == IrOpcode::kNumberSubtract ||
237 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 Node* input = arith->InputAt(0);
246 if (input->opcode() == IrOpcode::kSpeculativeToNumber ||
247 input->opcode() == IrOpcode::kJSToNumber ||
248 input->opcode() == IrOpcode::kJSToNumberConvertBigInt) {
249 input = input->InputAt(0);
250 }
251 if (input != phi) return nullptr;
252
253 Node* effect_phi = nullptr;
254 for (Node* use : loop->uses()) {
255 if (use->opcode() == IrOpcode::kEffectPhi) {
256 DCHECK_NULL(effect_phi);
257 effect_phi = use;
258 }
259 }
260 if (!effect_phi) return nullptr;
261
262 Node* incr = arith->InputAt(1);
263 return zone()->New<InductionVariable>(phi, effect_phi, arith, incr, initial,
264 zone(), arithmeticType);
265 }
266
DetectInductionVariables(Node * loop)267 void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
268 if (loop->op()->ControlInputCount() != 2) return;
269 TRACE("Loop variables for loop %i:", loop->id());
270 for (Edge edge : loop->use_edges()) {
271 if (NodeProperties::IsControlEdge(edge) &&
272 edge.from()->opcode() == IrOpcode::kPhi) {
273 Node* phi = edge.from();
274 InductionVariable* induction_var = TryGetInductionVariable(phi);
275 if (induction_var) {
276 induction_vars_[phi->id()] = induction_var;
277 TRACE(" %i", induction_var->phi()->id());
278 }
279 }
280 }
281 TRACE("\n");
282 }
283
ChangeToInductionVariablePhis()284 void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
285 for (auto entry : induction_vars_) {
286 // It only make sense to analyze the induction variables if
287 // there is a bound.
288 InductionVariable* induction_var = entry.second;
289 DCHECK_EQ(MachineRepresentation::kTagged,
290 PhiRepresentationOf(induction_var->phi()->op()));
291 if (induction_var->upper_bounds().size() == 0 &&
292 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 induction_var->increment());
299 // Insert the bound inputs to the value inputs.
300 for (auto bound : induction_var->lower_bounds()) {
301 induction_var->phi()->InsertInput(
302 graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
303 }
304 for (auto bound : induction_var->upper_bounds()) {
305 induction_var->phi()->InsertInput(
306 graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
307 }
308 NodeProperties::ChangeOp(
309 induction_var->phi(),
310 common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
311 }
312 }
313
ChangeToPhisAndInsertGuards()314 void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
315 for (auto entry : induction_vars_) {
316 InductionVariable* induction_var = entry.second;
317 if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
318 // Turn the induction variable phi back to normal phi.
319 int value_count = 2;
320 Node* control = NodeProperties::GetControlInput(induction_var->phi());
321 DCHECK_EQ(value_count, control->op()->ControlInputCount());
322 induction_var->phi()->TrimInputCount(value_count + 1);
323 induction_var->phi()->ReplaceInput(value_count, control);
324 NodeProperties::ChangeOp(
325 induction_var->phi(),
326 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 Type backedge_type = NodeProperties::GetType(backedge_value);
332 Type phi_type = NodeProperties::GetType(induction_var->phi());
333 if (!backedge_type.Is(phi_type)) {
334 Node* loop = NodeProperties::GetControlInput(induction_var->phi());
335 Node* backedge_control = loop->InputAt(1);
336 Node* backedge_effect =
337 NodeProperties::GetEffectInput(induction_var->effect_phi(), 1);
338 Node* rename =
339 graph()->NewNode(common()->TypeGuard(phi_type), backedge_value,
340 backedge_effect, backedge_control);
341 induction_var->effect_phi()->ReplaceInput(1, rename);
342 induction_var->phi()->ReplaceInput(1, rename);
343 }
344 }
345 }
346 }
347
348 #undef TRACE
349
350 } // namespace compiler
351 } // namespace internal
352 } // namespace v8
353