LCOV - code coverage report
Current view: top level - src/compiler - loop-variable-optimizer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 141 151 93.4 %
Date: 2019-04-17 Functions: 15 20 75.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      464083 : 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      928166 :       induction_vars_(zone) {}
      34             : 
      35      464080 : void LoopVariableOptimizer::Run() {
      36      464080 :   ZoneQueue<Node*> queue(zone());
      37      928165 :   queue.push(graph()->start());
      38             :   NodeMarker<bool> queued(graph(), 2);
      39     8138777 :   while (!queue.empty()) {
      40     7674695 :     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     7674707 :                          : node->op()->ControlInputCount();
      49    28752569 :     for (int i = 0; i < inputs_end; i++) {
      50    22091385 :       if (!reduced_.Get(NodeProperties::GetControlInput(node, i))) {
      51             :         all_inputs_visited = false;
      52             :         break;
      53             :       }
      54             :     }
      55     7674698 :     if (!all_inputs_visited) continue;
      56             : 
      57     7167932 :     VisitNode(node);
      58     7167961 :     reduced_.Set(node, true);
      59             : 
      60             :     // Queue control outputs.
      61    80857248 :     for (Edge edge : node->use_edges()) {
      62    52675803 :       if (NodeProperties::IsControlEdge(edge) &&
      63             :           edge.from()->op()->ControlOutputCount() > 0) {
      64     7411076 :         Node* use = edge.from();
      65     7495928 :         if (use->opcode() == IrOpcode::kLoop &&
      66       84852 :             edge.index() != kAssumedLoopEntryIndex) {
      67       42426 :           VisitBackedge(node, use);
      68     7368650 :         } else if (!queued.Get(use)) {
      69             :           queue.push(use);
      70     7210642 :           queued.Set(use, true);
      71             :         }
      72             :       }
      73             :     }
      74             :   }
      75      464081 : }
      76             : 
      77       11837 : void InductionVariable::AddUpperBound(Node* bound,
      78             :                                       InductionVariable::ConstraintKind kind) {
      79       11837 :   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       23674 :   upper_bounds_.push_back(Bound(bound, kind));
      85       11837 : }
      86             : 
      87         530 : void InductionVariable::AddLowerBound(Node* bound,
      88             :                                       InductionVariable::ConstraintKind kind) {
      89         530 :   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        1060 :   lower_bounds_.push_back(Bound(bound, kind));
      95         530 : }
      96             : 
      97       42426 : void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
      98       42426 :   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       59510 :   for (Constraint constraint : limits_.Get(from)) {
     103       32106 :     if (constraint.left->opcode() == IrOpcode::kPhi &&
     104       15022 :         NodeProperties::GetControlInput(constraint.left) == loop) {
     105       11837 :       auto var = induction_vars_.find(constraint.left->id());
     106       11837 :       if (var != induction_vars_.end()) {
     107       11837 :         var->second->AddUpperBound(constraint.right, constraint.kind);
     108             :       }
     109             :     }
     110       19234 :     if (constraint.right->opcode() == IrOpcode::kPhi &&
     111        2150 :         NodeProperties::GetControlInput(constraint.right) == loop) {
     112         530 :       auto var = induction_vars_.find(constraint.right->id());
     113         530 :       if (var != induction_vars_.end()) {
     114         530 :         var->second->AddLowerBound(constraint.left, constraint.kind);
     115             :       }
     116             :     }
     117             :   }
     118             : }
     119             : 
     120     7167987 : void LoopVariableOptimizer::VisitNode(Node* node) {
     121     7167987 :   switch (node->opcode()) {
     122             :     case IrOpcode::kMerge:
     123      266093 :       return VisitMerge(node);
     124             :     case IrOpcode::kLoop:
     125             :       return VisitLoop(node);
     126             :     case IrOpcode::kIfFalse:
     127      622808 :       return VisitIf(node, false);
     128             :     case IrOpcode::kIfTrue:
     129      622807 :       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      266094 : void LoopVariableOptimizer::VisitMerge(Node* node) {
     140             :   // Merge the limits of all incoming edges.
     141      266094 :   VariableLimits merged = limits_.Get(node->InputAt(0));
     142     1252630 :   for (int i = 1; i < node->InputCount(); i++) {
     143      493268 :     merged.ResetToCommonAncestor(limits_.Get(node->InputAt(i)));
     144             :   }
     145      266094 :   limits_.Set(node, merged);
     146      266094 : }
     147             : 
     148           0 : void LoopVariableOptimizer::VisitLoop(Node* node) {
     149       42426 :   DetectInductionVariables(node);
     150             :   // Conservatively take the limits from the loop entry here.
     151       42426 :   return TakeConditionsFromFirstControl(node);
     152             : }
     153             : 
     154     1245610 : void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
     155             :   Node* branch = node->InputAt(0);
     156             :   Node* cond = branch->InputAt(0);
     157     1245610 :   VariableLimits limits = limits_.Get(branch);
     158             :   // Normalize to less than comparison.
     159     1245610 :   switch (cond->opcode()) {
     160             :     case IrOpcode::kJSLessThan:
     161             :     case IrOpcode::kNumberLessThan:
     162             :     case IrOpcode::kSpeculativeNumberLessThan:
     163      124929 :       AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity);
     164      124931 :       break;
     165             :     case IrOpcode::kJSGreaterThan:
     166       25250 :       AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity);
     167       25250 :       break;
     168             :     case IrOpcode::kJSLessThanOrEqual:
     169             :     case IrOpcode::kNumberLessThanOrEqual:
     170             :     case IrOpcode::kSpeculativeNumberLessThanOrEqual:
     171        5490 :       AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, polarity);
     172        5490 :       break;
     173             :     case IrOpcode::kJSGreaterThanOrEqual:
     174        2958 :       AddCmpToLimits(&limits, cond, InductionVariable::kStrict, !polarity);
     175        2958 :       break;
     176             :     default:
     177             :       break;
     178             :   }
     179     1245612 :   limits_.Set(node, limits);
     180     1245613 : }
     181             : 
     182      158630 : 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      236856 :   if (FindInductionVariable(left) || FindInductionVariable(right)) {
     188       81678 :     if (polarity) {
     189       40838 :       limits->PushFront(Constraint{left, kind, right}, zone());
     190             :     } else {
     191             :       kind = (kind == InductionVariable::kStrict)
     192             :                  ? InductionVariable::kNonStrict
     193       40840 :                  : InductionVariable::kStrict;
     194       40840 :       limits->PushFront(Constraint{right, kind, left}, zone());
     195             :     }
     196             :   }
     197      158629 : }
     198             : 
     199      464080 : void LoopVariableOptimizer::VisitStart(Node* node) { limits_.Set(node, {}); }
     200             : 
     201           0 : void LoopVariableOptimizer::VisitLoopExit(Node* node) {
     202      171521 :   return TakeConditionsFromFirstControl(node);
     203             : }
     204             : 
     205           0 : void LoopVariableOptimizer::VisitOtherControl(Node* node) {
     206             :   DCHECK_EQ(1, node->op()->ControlInputCount());
     207     4978252 :   return TakeConditionsFromFirstControl(node);
     208             : }
     209             : 
     210     5192199 : void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
     211    10384402 :   limits_.Set(node, limits_.Get(NodeProperties::GetControlInput(node, 0)));
     212     5192198 : }
     213             : 
     214           0 : const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
     215             :     Node* node) {
     216      236856 :   auto var = induction_vars_.find(node->id());
     217      236856 :   if (var != induction_vars_.end()) {
     218       81675 :     return var->second;
     219             :   }
     220             :   return nullptr;
     221             : }
     222             : 
     223       67849 : InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
     224             :   DCHECK_EQ(2, phi->op()->ValueInputCount());
     225       67849 :   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      133722 :   if (arith->opcode() == IrOpcode::kJSAdd ||
     231       63823 :       arith->opcode() == IrOpcode::kNumberAdd ||
     232      131091 :       arith->opcode() == IrOpcode::kSpeculativeNumberAdd ||
     233             :       arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) {
     234             :     arithmeticType = InductionVariable::ArithmeticType::kAddition;
     235       97010 :   } else if (arith->opcode() == IrOpcode::kJSSubtract ||
     236       48174 :              arith->opcode() == IrOpcode::kNumberSubtract ||
     237       96694 :              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       40948 :   if (input->opcode() == IrOpcode::kSpeculativeToNumber ||
     247       40948 :       input->opcode() == IrOpcode::kJSToNumber ||
     248             :       input->opcode() == IrOpcode::kJSToNumberConvertBigInt) {
     249             :     input = input->InputAt(0);
     250             :   }
     251       21185 :   if (input != phi) return nullptr;
     252             : 
     253             :   Node* effect_phi = nullptr;
     254      183023 :   for (Node* use : loop->uses()) {
     255      165177 :     if (use->opcode() == IrOpcode::kEffectPhi) {
     256             :       DCHECK_NULL(effect_phi);
     257             :       effect_phi = use;
     258             :     }
     259             :   }
     260       17846 :   if (!effect_phi) return nullptr;
     261             : 
     262             :   Node* incr = arith->InputAt(1);
     263             :   return new (zone()) InductionVariable(phi, effect_phi, arith, incr, initial,
     264       17846 :                                         zone(), arithmeticType);
     265             : }
     266             : 
     267       42426 : void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
     268       42426 :   if (loop->op()->ControlInputCount() != 2) return;
     269       42426 :   TRACE("Loop variables for loop %i:", loop->id());
     270      920182 :   for (Edge edge : loop->use_edges()) {
     271      877756 :     if (NodeProperties::IsControlEdge(edge) &&
     272             :         edge.from()->opcode() == IrOpcode::kPhi) {
     273             :       Node* phi = edge.from();
     274       67849 :       InductionVariable* induction_var = TryGetInductionVariable(phi);
     275       67849 :       if (induction_var) {
     276       17846 :         induction_vars_[phi->id()] = induction_var;
     277       17846 :         TRACE(" %i", induction_var->phi()->id());
     278             :       }
     279             :     }
     280             :   }
     281       42426 :   TRACE("\n");
     282             : }
     283             : 
     284      464077 : void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
     285      481924 :   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       23922 :     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       12220 :     induction_var->phi()->InsertInput(graph()->zone(),
     297             :                                       induction_var->phi()->InputCount() - 1,
     298       12220 :                                       induction_var->increment());
     299             :     // Insert the bound inputs to the value inputs.
     300       12750 :     for (auto bound : induction_var->lower_bounds()) {
     301         530 :       induction_var->phi()->InsertInput(
     302         530 :           graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
     303             :     }
     304       24057 :     for (auto bound : induction_var->upper_bounds()) {
     305       11837 :       induction_var->phi()->InsertInput(
     306       11837 :           graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
     307             :     }
     308       12220 :     NodeProperties::ChangeOp(
     309             :         induction_var->phi(),
     310       12220 :         common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
     311             :   }
     312      464078 : }
     313             : 
     314      464080 : void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
     315      481925 :   for (auto entry : induction_vars_) {
     316             :     InductionVariable* induction_var = entry.second;
     317       17846 :     if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
     318             :       // Turn the induction variable phi back to normal phi.
     319             :       int value_count = 2;
     320       12220 :       Node* control = NodeProperties::GetControlInput(induction_var->phi());
     321             :       DCHECK_EQ(value_count, control->op()->ControlInputCount());
     322       12220 :       induction_var->phi()->TrimInputCount(value_count + 1);
     323       12220 :       induction_var->phi()->ReplaceInput(value_count, control);
     324       12220 :       NodeProperties::ChangeOp(
     325             :           induction_var->phi(),
     326       12220 :           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       12220 :       Type backedge_type = NodeProperties::GetType(backedge_value);
     332             :       Type phi_type = NodeProperties::GetType(induction_var->phi());
     333       12220 :       if (!backedge_type.Is(phi_type)) {
     334        7712 :         Node* loop = NodeProperties::GetControlInput(induction_var->phi());
     335             :         Node* backedge_control = loop->InputAt(1);
     336             :         Node* backedge_effect =
     337        7712 :             NodeProperties::GetEffectInput(induction_var->effect_phi(), 1);
     338             :         Node* rename =
     339        7712 :             graph()->NewNode(common()->TypeGuard(phi_type), backedge_value,
     340             :                              backedge_effect, backedge_control);
     341        7712 :         induction_var->effect_phi()->ReplaceInput(1, rename);
     342        7712 :         induction_var->phi()->ReplaceInput(1, rename);
     343             :       }
     344             :     }
     345             :   }
     346      464079 : }
     347             : 
     348             : #undef TRACE
     349             : 
     350             : }  // namespace compiler
     351             : }  // namespace internal
     352      121996 : }  // namespace v8

Generated by: LCOV version 1.10