LCOV - code coverage report
Current view: top level - src/compiler - loop-variable-optimizer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 154 166 92.8 %
Date: 2017-04-26 Functions: 17 20 85.0 %

          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

Generated by: LCOV version 1.10