Home | History | Annotate | Download | only in compiler 
      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 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 
     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 
     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 
     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 
     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 
    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 
    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 
    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 
    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::kSpeculativeNumberLessThan:
    162       AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity);
    163       break;
    164     case IrOpcode::kJSGreaterThan:
    165       AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity);
    166       break;
    167     case IrOpcode::kJSLessThanOrEqual:
    168     case IrOpcode::kSpeculativeNumberLessThanOrEqual:
    169       AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, polarity);
    170       break;
    171     case IrOpcode::kJSGreaterThanOrEqual:
    172       AddCmpToLimits(&limits, cond, InductionVariable::kStrict, !polarity);
    173       break;
    174     default:
    175       break;
    176   }
    177   limits_.Set(node, limits);
    178 }
    179 
    180 void LoopVariableOptimizer::AddCmpToLimits(
    181     VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
    182     bool polarity) {
    183   Node* left = node->InputAt(0);
    184   Node* right = node->InputAt(1);
    185   if (FindInductionVariable(left) || FindInductionVariable(right)) {
    186     if (polarity) {
    187       limits->PushFront(Constraint{left, kind, right}, zone());
    188     } else {
    189       kind = (kind == InductionVariable::kStrict)
    190                  ? InductionVariable::kNonStrict
    191                  : InductionVariable::kStrict;
    192       limits->PushFront(Constraint{right, kind, left}, zone());
    193     }
    194   }
    195 }
    196 
    197 void LoopVariableOptimizer::VisitStart(Node* node) { limits_.Set(node, {}); }
    198 
    199 void LoopVariableOptimizer::VisitLoopExit(Node* node) {
    200   return TakeConditionsFromFirstControl(node);
    201 }
    202 
    203 void LoopVariableOptimizer::VisitOtherControl(Node* node) {
    204   DCHECK_EQ(1, node->op()->ControlInputCount());
    205   return TakeConditionsFromFirstControl(node);
    206 }
    207 
    208 void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
    209   limits_.Set(node, limits_.Get(NodeProperties::GetControlInput(node, 0)));
    210 }
    211 
    212 const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
    213     Node* node) {
    214   auto var = induction_vars_.find(node->id());
    215   if (var != induction_vars_.end()) {
    216     return var->second;
    217   }
    218   return nullptr;
    219 }
    220 
    221 InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
    222   DCHECK_EQ(2, phi->op()->ValueInputCount());
    223   Node* loop = NodeProperties::GetControlInput(phi);
    224   DCHECK_EQ(IrOpcode::kLoop, loop->opcode());
    225   Node* initial = phi->InputAt(0);
    226   Node* arith = phi->InputAt(1);
    227   InductionVariable::ArithmeticType arithmeticType;
    228   if (arith->opcode() == IrOpcode::kJSAdd ||
    229       arith->opcode() == IrOpcode::kSpeculativeNumberAdd ||
    230       arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) {
    231     arithmeticType = InductionVariable::ArithmeticType::kAddition;
    232   } else if (arith->opcode() == IrOpcode::kJSSubtract ||
    233              arith->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
    234              arith->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract) {
    235     arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
    236   } else {
    237     return nullptr;
    238   }
    239 
    240   // TODO(jarin) Support both sides.
    241   Node* input = arith->InputAt(0);
    242   if (input->opcode() == IrOpcode::kSpeculativeToNumber ||
    243       input->opcode() == IrOpcode::kJSToNumber ||
    244       input->opcode() == IrOpcode::kJSToNumberConvertBigInt) {
    245     input = input->InputAt(0);
    246   }
    247   if (input != phi) return nullptr;
    248 
    249   Node* effect_phi = nullptr;
    250   for (Node* use : loop->uses()) {
    251     if (use->opcode() == IrOpcode::kEffectPhi) {
    252       DCHECK_NULL(effect_phi);
    253       effect_phi = use;
    254     }
    255   }
    256   if (!effect_phi) return nullptr;
    257 
    258   Node* incr = arith->InputAt(1);
    259   return new (zone()) InductionVariable(phi, effect_phi, arith, incr, initial,
    260                                         zone(), arithmeticType);
    261 }
    262 
    263 void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
    264   if (loop->op()->ControlInputCount() != 2) return;
    265   TRACE("Loop variables for loop %i:", loop->id());
    266   for (Edge edge : loop->use_edges()) {
    267     if (NodeProperties::IsControlEdge(edge) &&
    268         edge.from()->opcode() == IrOpcode::kPhi) {
    269       Node* phi = edge.from();
    270       InductionVariable* induction_var = TryGetInductionVariable(phi);
    271       if (induction_var) {
    272         induction_vars_[phi->id()] = induction_var;
    273         TRACE(" %i", induction_var->phi()->id());
    274       }
    275     }
    276   }
    277   TRACE("\n");
    278 }
    279 
    280 void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
    281   for (auto entry : induction_vars_) {
    282     // It only make sense to analyze the induction variables if
    283     // there is a bound.
    284     InductionVariable* induction_var = entry.second;
    285     DCHECK_EQ(MachineRepresentation::kTagged,
    286               PhiRepresentationOf(induction_var->phi()->op()));
    287     if (induction_var->upper_bounds().size() == 0 &&
    288         induction_var->lower_bounds().size() == 0) {
    289       continue;
    290     }
    291     // Insert the increment value to the value inputs.
    292     induction_var->phi()->InsertInput(graph()->zone(),
    293                                       induction_var->phi()->InputCount() - 1,
    294                                       induction_var->increment());
    295     // Insert the bound inputs to the value inputs.
    296     for (auto bound : induction_var->lower_bounds()) {
    297       induction_var->phi()->InsertInput(
    298           graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
    299     }
    300     for (auto bound : induction_var->upper_bounds()) {
    301       induction_var->phi()->InsertInput(
    302           graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
    303     }
    304     NodeProperties::ChangeOp(
    305         induction_var->phi(),
    306         common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
    307   }
    308 }
    309 
    310 void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
    311   for (auto entry : induction_vars_) {
    312     InductionVariable* induction_var = entry.second;
    313     if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
    314       // Turn the induction variable phi back to normal phi.
    315       int value_count = 2;
    316       Node* control = NodeProperties::GetControlInput(induction_var->phi());
    317       DCHECK_EQ(value_count, control->op()->ControlInputCount());
    318       induction_var->phi()->TrimInputCount(value_count + 1);
    319       induction_var->phi()->ReplaceInput(value_count, control);
    320       NodeProperties::ChangeOp(
    321           induction_var->phi(),
    322           common()->Phi(MachineRepresentation::kTagged, value_count));
    323 
    324       // If the backedge is not a subtype of the phi's type, we insert a sigma
    325       // to get the typing right.
    326       Node* backedge_value = induction_var->phi()->InputAt(1);
    327       Type backedge_type = NodeProperties::GetType(backedge_value);
    328       Type phi_type = NodeProperties::GetType(induction_var->phi());
    329       if (!backedge_type.Is(phi_type)) {
    330         Node* loop = NodeProperties::GetControlInput(induction_var->phi());
    331         Node* backedge_control = loop->InputAt(1);
    332         Node* backedge_effect =
    333             NodeProperties::GetEffectInput(induction_var->effect_phi(), 1);
    334         Node* rename =
    335             graph()->NewNode(common()->TypeGuard(phi_type), backedge_value,
    336                              backedge_effect, backedge_control);
    337         induction_var->effect_phi()->ReplaceInput(1, rename);
    338         induction_var->phi()->ReplaceInput(1, rename);
    339       }
    340     }
    341   }
    342 }
    343 
    344 #undef TRACE
    345 
    346 }  // namespace compiler
    347 }  // namespace internal
    348 }  // namespace v8
    349