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
15namespace v8 {
16namespace internal {
17namespace 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
25LoopVariableOptimizer::LoopVariableOptimizer(Graph* graph,
26                                             CommonOperatorBuilder* common,
27                                             Zone* zone)
28    : graph_(graph),
29      common_(common),
30      zone_(zone),
31      limits_(graph->NodeCount(), zone),
32      induction_vars_(zone) {}
33
34void LoopVariableOptimizer::Run() {
35  ZoneQueue<Node*> queue(zone());
36  queue.push(graph()->start());
37  NodeMarker<bool> queued(graph(), 2);
38  while (!queue.empty()) {
39    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                         : node->op()->ControlInputCount();
48    for (int i = 0; i < inputs_end; i++) {
49      if (limits_[NodeProperties::GetControlInput(node, i)->id()] == nullptr) {
50        all_inputs_visited = false;
51        break;
52      }
53    }
54    if (!all_inputs_visited) continue;
55
56    VisitNode(node);
57    DCHECK_NOT_NULL(limits_[node->id()]);
58
59    // Queue control outputs.
60    for (Edge edge : node->use_edges()) {
61      if (NodeProperties::IsControlEdge(edge) &&
62          edge.from()->op()->ControlOutputCount() > 0) {
63        Node* use = edge.from();
64        if (use->opcode() == IrOpcode::kLoop &&
65            edge.index() != kAssumedLoopEntryIndex) {
66          VisitBackedge(node, use);
67        } else if (!queued.Get(use)) {
68          queue.push(use);
69          queued.Set(use, true);
70        }
71      }
72    }
73  }
74}
75
76class 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      : 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
95class 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    head_ = new (zone) Constraint(left, kind, right, head_);
108    limit_count_++;
109  }
110
111  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    size_t other_size = other->limit_count_;
119    const Constraint* other_limit = other->head_;
120    while (other_size > limit_count_) {
121      other_limit = other_limit->next();
122      other_size--;
123    }
124    while (limit_count_ > other_size) {
125      head_ = head_->next();
126      limit_count_--;
127    }
128
129    // Then we go through both lists in lock-step until we find
130    // the common tail.
131    while (head_ != other_limit) {
132      DCHECK(limit_count_ > 0);
133      limit_count_--;
134      other_limit = other_limit->next();
135      head_ = head_->next();
136    }
137  }
138
139  const Constraint* head() const { return head_; }
140
141 private:
142  VariableLimits() {}
143  explicit VariableLimits(const VariableLimits* other)
144      : head_(other->head_), limit_count_(other->limit_count_) {}
145
146  const Constraint* head_ = nullptr;
147  size_t limit_count_ = 0;
148};
149
150void InductionVariable::AddUpperBound(Node* bound,
151                                      InductionVariable::ConstraintKind kind) {
152  if (FLAG_trace_turbo_loop) {
153    OFStream os(stdout);
154    os << "New upper bound for " << phi()->id() << " (loop "
155       << NodeProperties::GetControlInput(phi())->id() << "): " << *bound
156       << std::endl;
157  }
158  upper_bounds_.push_back(Bound(bound, kind));
159}
160
161void InductionVariable::AddLowerBound(Node* bound,
162                                      InductionVariable::ConstraintKind kind) {
163  if (FLAG_trace_turbo_loop) {
164    OFStream os(stdout);
165    os << "New lower bound for " << phi()->id() << " (loop "
166       << NodeProperties::GetControlInput(phi())->id() << "): " << *bound;
167  }
168  lower_bounds_.push_back(Bound(bound, kind));
169}
170
171void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
172  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  const VariableLimits* limits = limits_[from->id()];
177  for (const Constraint* constraint = limits->head(); constraint != nullptr;
178       constraint = constraint->next()) {
179    if (constraint->left()->opcode() == IrOpcode::kPhi &&
180        NodeProperties::GetControlInput(constraint->left()) == loop) {
181      auto var = induction_vars_.find(constraint->left()->id());
182      if (var != induction_vars_.end()) {
183        var->second->AddUpperBound(constraint->right(), constraint->kind());
184      }
185    }
186    if (constraint->right()->opcode() == IrOpcode::kPhi &&
187        NodeProperties::GetControlInput(constraint->right()) == loop) {
188      auto var = induction_vars_.find(constraint->right()->id());
189      if (var != induction_vars_.end()) {
190        var->second->AddLowerBound(constraint->left(), constraint->kind());
191      }
192    }
193  }
194}
195
196void LoopVariableOptimizer::VisitNode(Node* node) {
197  switch (node->opcode()) {
198    case IrOpcode::kMerge:
199      return VisitMerge(node);
200    case IrOpcode::kLoop:
201      return VisitLoop(node);
202    case IrOpcode::kIfFalse:
203      return VisitIf(node, false);
204    case IrOpcode::kIfTrue:
205      return VisitIf(node, true);
206    case IrOpcode::kStart:
207      return VisitStart(node);
208    case IrOpcode::kLoopExit:
209      return VisitLoopExit(node);
210    default:
211      return VisitOtherControl(node);
212  }
213}
214
215void LoopVariableOptimizer::VisitMerge(Node* node) {
216  // Merge the limits of all incoming edges.
217  VariableLimits* merged = limits_[node->InputAt(0)->id()]->Copy(zone());
218  for (int i = 1; i < node->InputCount(); i++) {
219    merged->Merge(limits_[node->InputAt(i)->id()]);
220  }
221  limits_[node->id()] = merged;
222}
223
224void LoopVariableOptimizer::VisitLoop(Node* node) {
225  DetectInductionVariables(node);
226  // Conservatively take the limits from the loop entry here.
227  return TakeConditionsFromFirstControl(node);
228}
229
230void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
231  Node* branch = node->InputAt(0);
232  Node* cond = branch->InputAt(0);
233  VariableLimits* limits = limits_[branch->id()]->Copy(zone());
234  // Normalize to less than comparison.
235  switch (cond->opcode()) {
236    case IrOpcode::kJSLessThan:
237      AddCmpToLimits(limits, cond, InductionVariable::kStrict, polarity);
238      break;
239    case IrOpcode::kJSGreaterThan:
240      AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, !polarity);
241      break;
242    case IrOpcode::kJSLessThanOrEqual:
243      AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, polarity);
244      break;
245    case IrOpcode::kJSGreaterThanOrEqual:
246      AddCmpToLimits(limits, cond, InductionVariable::kStrict, !polarity);
247      break;
248    default:
249      break;
250  }
251  limits_[node->id()] = limits;
252}
253
254void LoopVariableOptimizer::AddCmpToLimits(
255    VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
256    bool polarity) {
257  Node* left = node->InputAt(0);
258  Node* right = node->InputAt(1);
259  if (FindInductionVariable(left) || FindInductionVariable(right)) {
260    if (polarity) {
261      limits->Add(left, kind, right, zone());
262    } else {
263      kind = (kind == InductionVariable::kStrict)
264                 ? InductionVariable::kNonStrict
265                 : InductionVariable::kStrict;
266      limits->Add(right, kind, left, zone());
267    }
268  }
269}
270
271void LoopVariableOptimizer::VisitStart(Node* node) {
272  limits_[node->id()] = VariableLimits::Empty(zone());
273}
274
275void LoopVariableOptimizer::VisitLoopExit(Node* node) {
276  return TakeConditionsFromFirstControl(node);
277}
278
279void LoopVariableOptimizer::VisitOtherControl(Node* node) {
280  DCHECK_EQ(1, node->op()->ControlInputCount());
281  return TakeConditionsFromFirstControl(node);
282}
283
284void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
285  const VariableLimits* limits =
286      limits_[NodeProperties::GetControlInput(node, 0)->id()];
287  DCHECK_NOT_NULL(limits);
288  limits_[node->id()] = limits;
289}
290
291const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
292    Node* node) {
293  auto var = induction_vars_.find(node->id());
294  if (var != induction_vars_.end()) {
295    return var->second;
296  }
297  return nullptr;
298}
299
300InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
301  DCHECK_EQ(2, phi->op()->ValueInputCount());
302  DCHECK_EQ(IrOpcode::kLoop, NodeProperties::GetControlInput(phi)->opcode());
303  Node* initial = phi->InputAt(0);
304  Node* arith = phi->InputAt(1);
305  InductionVariable::ArithmeticType arithmeticType;
306  if (arith->opcode() == IrOpcode::kJSAdd ||
307      arith->opcode() == IrOpcode::kSpeculativeNumberAdd) {
308    arithmeticType = InductionVariable::ArithmeticType::kAddition;
309  } else if (arith->opcode() == IrOpcode::kJSSubtract ||
310             arith->opcode() == IrOpcode::kSpeculativeNumberSubtract) {
311    arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
312  } else {
313    return nullptr;
314  }
315
316  // TODO(jarin) Support both sides.
317  if (arith->InputAt(0) != phi) {
318    if (arith->InputAt(0)->opcode() != IrOpcode::kJSToNumber ||
319        arith->InputAt(0)->InputAt(0) != phi) {
320      return nullptr;
321    }
322  }
323  Node* incr = arith->InputAt(1);
324  return new (zone())
325      InductionVariable(phi, arith, incr, initial, zone(), arithmeticType);
326}
327
328void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
329  if (loop->op()->ControlInputCount() != 2) return;
330  TRACE("Loop variables for loop %i:", loop->id());
331  for (Edge edge : loop->use_edges()) {
332    if (NodeProperties::IsControlEdge(edge) &&
333        edge.from()->opcode() == IrOpcode::kPhi) {
334      Node* phi = edge.from();
335      InductionVariable* induction_var = TryGetInductionVariable(phi);
336      if (induction_var) {
337        induction_vars_[phi->id()] = induction_var;
338        TRACE(" %i", induction_var->phi()->id());
339      }
340    }
341  }
342  TRACE("\n");
343}
344
345void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
346  for (auto entry : induction_vars_) {
347    // It only make sense to analyze the induction variables if
348    // there is a bound.
349    InductionVariable* induction_var = entry.second;
350    DCHECK_EQ(MachineRepresentation::kTagged,
351              PhiRepresentationOf(induction_var->phi()->op()));
352    if (induction_var->upper_bounds().size() == 0 &&
353        induction_var->lower_bounds().size() == 0) {
354      continue;
355    }
356    // Insert the increment value to the value inputs.
357    induction_var->phi()->InsertInput(graph()->zone(),
358                                      induction_var->phi()->InputCount() - 1,
359                                      induction_var->increment());
360    // Insert the bound inputs to the value inputs.
361    for (auto bound : induction_var->lower_bounds()) {
362      induction_var->phi()->InsertInput(
363          graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
364    }
365    for (auto bound : induction_var->upper_bounds()) {
366      induction_var->phi()->InsertInput(
367          graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
368    }
369    NodeProperties::ChangeOp(
370        induction_var->phi(),
371        common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
372  }
373}
374
375void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
376  for (auto entry : induction_vars_) {
377    InductionVariable* induction_var = entry.second;
378    if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
379      // Turn the induction variable phi back to normal phi.
380      int value_count = 2;
381      Node* control = NodeProperties::GetControlInput(induction_var->phi());
382      DCHECK_EQ(value_count, control->op()->ControlInputCount());
383      induction_var->phi()->TrimInputCount(value_count + 1);
384      induction_var->phi()->ReplaceInput(value_count, control);
385      NodeProperties::ChangeOp(
386          induction_var->phi(),
387          common()->Phi(MachineRepresentation::kTagged, value_count));
388
389      // If the backedge is not a subtype of the phi's type, we insert a sigma
390      // to get the typing right.
391      Node* backedge_value = induction_var->phi()->InputAt(1);
392      Type* backedge_type = NodeProperties::GetType(backedge_value);
393      Type* phi_type = NodeProperties::GetType(induction_var->phi());
394      if (!backedge_type->Is(phi_type)) {
395        Node* backedge_control =
396            NodeProperties::GetControlInput(induction_var->phi())->InputAt(1);
397        Node* rename = graph()->NewNode(common()->TypeGuard(phi_type),
398                                        backedge_value, backedge_control);
399        induction_var->phi()->ReplaceInput(1, rename);
400      }
401    }
402  }
403}
404
405}  // namespace compiler
406}  // namespace internal
407}  // namespace v8
408