LCOV - code coverage report
Current view: top level - src/compiler - loop-peeling.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 118 124 95.2 %
Date: 2017-04-26 Functions: 10 10 100.0 %

          Line data    Source code
       1             : // Copyright 2015 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-peeling.h"
       6             : #include "src/compiler/common-operator.h"
       7             : #include "src/compiler/graph.h"
       8             : #include "src/compiler/node-marker.h"
       9             : #include "src/compiler/node-properties.h"
      10             : #include "src/compiler/node.h"
      11             : #include "src/zone/zone.h"
      12             : 
      13             : // Loop peeling is an optimization that copies the body of a loop, creating
      14             : // a new copy of the body called the "peeled iteration" that represents the
      15             : // first iteration. Beginning with a loop as follows:
      16             : 
      17             : //             E
      18             : //             |                 A
      19             : //             |                 |                     (backedges)
      20             : //             | +---------------|---------------------------------+
      21             : //             | | +-------------|-------------------------------+ |
      22             : //             | | |             | +--------+                    | |
      23             : //             | | |             | | +----+ |                    | |
      24             : //             | | |             | | |    | |                    | |
      25             : //           ( Loop )<-------- ( phiA )   | |                    | |
      26             : //              |                 |       | |                    | |
      27             : //      ((======P=================U=======|=|=====))             | |
      28             : //      ((                                | |     ))             | |
      29             : //      ((        X <---------------------+ |     ))             | |
      30             : //      ((                                  |     ))             | |
      31             : //      ((     body                         |     ))             | |
      32             : //      ((                                  |     ))             | |
      33             : //      ((        Y <-----------------------+     ))             | |
      34             : //      ((                                        ))             | |
      35             : //      ((===K====L====M==========================))             | |
      36             : //           |    |    |                                         | |
      37             : //           |    |    +-----------------------------------------+ |
      38             : //           |    +------------------------------------------------+
      39             : //           |
      40             : //          exit
      41             : 
      42             : // The body of the loop is duplicated so that all nodes considered "inside"
      43             : // the loop (e.g. {P, U, X, Y, K, L, M}) have a corresponding copies in the
      44             : // peeled iteration (e.g. {P', U', X', Y', K', L', M'}). What were considered
      45             : // backedges of the loop correspond to edges from the peeled iteration to
      46             : // the main loop body, with multiple backedges requiring a merge.
      47             : 
      48             : // Similarly, any exits from the loop body need to be merged with "exits"
      49             : // from the peeled iteration, resulting in the graph as follows:
      50             : 
      51             : //             E
      52             : //             |                 A
      53             : //             |                 |
      54             : //      ((=====P'================U'===============))
      55             : //      ((                                        ))
      56             : //      ((        X'<-------------+               ))
      57             : //      ((                        |               ))
      58             : //      ((   peeled iteration     |               ))
      59             : //      ((                        |               ))
      60             : //      ((        Y'<-----------+ |               ))
      61             : //      ((                      | |               ))
      62             : //      ((===K'===L'====M'======|=|===============))
      63             : //           |    |     |       | |
      64             : //  +--------+    +-+ +-+       | |
      65             : //  |               | |         | |
      66             : //  |              Merge <------phi
      67             : //  |                |           |
      68             : //  |          +-----+           |
      69             : //  |          |                 |                     (backedges)
      70             : //  |          | +---------------|---------------------------------+
      71             : //  |          | | +-------------|-------------------------------+ |
      72             : //  |          | | |             | +--------+                    | |
      73             : //  |          | | |             | | +----+ |                    | |
      74             : //  |          | | |             | | |    | |                    | |
      75             : //  |        ( Loop )<-------- ( phiA )   | |                    | |
      76             : //  |           |                 |       | |                    | |
      77             : //  |   ((======P=================U=======|=|=====))             | |
      78             : //  |   ((                                | |     ))             | |
      79             : //  |   ((        X <---------------------+ |     ))             | |
      80             : //  |   ((                                  |     ))             | |
      81             : //  |   ((     body                         |     ))             | |
      82             : //  |   ((                                  |     ))             | |
      83             : //  |   ((        Y <-----------------------+     ))             | |
      84             : //  |   ((                                        ))             | |
      85             : //  |   ((===K====L====M==========================))             | |
      86             : //  |        |    |    |                                         | |
      87             : //  |        |    |    +-----------------------------------------+ |
      88             : //  |        |    +------------------------------------------------+
      89             : //  |        |
      90             : //  |        |
      91             : //  +----+ +-+
      92             : //       | |
      93             : //      Merge
      94             : //        |
      95             : //      exit
      96             : 
      97             : // Note that the boxes ((===)) above are not explicitly represented in the
      98             : // graph, but are instead computed by the {LoopFinder}.
      99             : 
     100             : namespace v8 {
     101             : namespace internal {
     102             : namespace compiler {
     103             : 
     104             : struct Peeling {
     105             :   // Maps a node to its index in the {pairs} vector.
     106             :   NodeMarker<size_t> node_map;
     107             :   // The vector which contains the mapped nodes.
     108             :   NodeVector* pairs;
     109             : 
     110             :   Peeling(Graph* graph, Zone* tmp_zone, size_t max, NodeVector* p)
     111       66788 :       : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {}
     112             : 
     113    15465117 :   Node* map(Node* node) {
     114    15465117 :     if (node_map.Get(node) == 0) return node;
     115    12069592 :     return pairs->at(node_map.Get(node));
     116             :   }
     117             : 
     118     2205738 :   void Insert(Node* original, Node* copy) {
     119     4411476 :     node_map.Set(original, 1 + pairs->size());
     120     2205723 :     pairs->push_back(original);
     121     2205709 :     pairs->push_back(copy);
     122     2205637 :   }
     123             : 
     124       33399 :   void CopyNodes(Graph* graph, Zone* tmp_zone, Node* dead, NodeRange nodes) {
     125             :     NodeVector inputs(tmp_zone);
     126             :     // Copy all the nodes first.
     127     4178808 :     for (Node* node : nodes) {
     128             :       inputs.clear();
     129     9611417 :       for (Node* input : node->inputs()) {
     130    15077423 :         inputs.push_back(map(input));
     131             :       }
     132     4145342 :       Node* copy = graph->NewNode(node->op(), node->InputCount(), &inputs[0]);
     133     2072835 :       if (NodeProperties::IsTyped(node)) {
     134             :         NodeProperties::SetType(copy, NodeProperties::GetType(node));
     135             :       }
     136     2072835 :       Insert(node, copy);
     137             :     }
     138             : 
     139             :     // Fix remaining inputs of the copies.
     140     4145617 :     for (Node* original : nodes) {
     141     4145670 :       Node* copy = pairs->at(node_map.Get(original));
     142    19223198 :       for (int i = 0; i < copy->InputCount(); i++) {
     143     7538792 :         copy->ReplaceInput(i, map(original->InputAt(i)));
     144             :       }
     145             :     }
     146       33394 :   }
     147             : 
     148             :   bool Marked(Node* node) { return node_map.Get(node) > 0; }
     149             : };
     150             : 
     151             : 
     152             : class PeeledIterationImpl : public PeeledIteration {
     153             :  public:
     154             :   NodeVector node_pairs_;
     155             :   explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {}
     156             : };
     157             : 
     158             : 
     159          63 : Node* PeeledIteration::map(Node* node) {
     160             :   // TODO(turbofan): we use a simple linear search, since the peeled iteration
     161             :   // is really only used in testing.
     162             :   PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this);
     163         678 :   for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) {
     164         719 :     if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1];
     165             :   }
     166             :   return node;
     167             : }
     168             : 
     169       74360 : bool LoopPeeler::CanPeel(LoopTree* loop_tree, LoopTree::Loop* loop) {
     170             :   // Look for returns and if projections that are outside the loop but whose
     171             :   // control input is inside the loop.
     172       37180 :   Node* loop_node = loop_tree->GetLoopControl(loop);
     173     2944454 :   for (Node* node : loop_tree->LoopNodes(loop)) {
     174     8458967 :     for (Node* use : node->uses()) {
     175     5835509 :       if (!loop_tree->Contains(loop, use)) {
     176             :         bool unmarked_exit;
     177      358536 :         switch (node->opcode()) {
     178             :           case IrOpcode::kLoopExit:
     179      117619 :             unmarked_exit = (node->InputAt(1) != loop_node);
     180      117619 :             break;
     181             :           case IrOpcode::kLoopExitValue:
     182             :           case IrOpcode::kLoopExitEffect:
     183      166197 :             unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node);
     184      166197 :             break;
     185             :           default:
     186       74720 :             unmarked_exit = (use->opcode() != IrOpcode::kTerminate);
     187             :         }
     188      358536 :         if (unmarked_exit) {
     189        3770 :           if (FLAG_trace_turbo_loop) {
     190           0 :             Node* loop_node = loop_tree->GetLoopControl(loop);
     191             :             PrintF(
     192             :                 "Cannot peel loop %i. Loop exit without explicit mark: Node %i "
     193             :                 "(%s) is inside "
     194             :                 "loop, but its use %i (%s) is outside.\n",
     195             :                 loop_node->id(), node->id(), node->op()->mnemonic(), use->id(),
     196           0 :                 use->op()->mnemonic());
     197             :           }
     198             :           return false;
     199             :         }
     200             :       }
     201             :     }
     202             :   }
     203             :   return true;
     204             : }
     205             : 
     206             : 
     207      184943 : PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common,
     208      166970 :                                   LoopTree* loop_tree, LoopTree::Loop* loop,
     209             :                                   Zone* tmp_zone) {
     210       37163 :   if (!CanPeel(loop_tree, loop)) return nullptr;
     211             : 
     212             :   //============================================================================
     213             :   // Construct the peeled iteration.
     214             :   //============================================================================
     215             :   PeeledIterationImpl* iter = new (tmp_zone) PeeledIterationImpl(tmp_zone);
     216       33394 :   size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2;
     217       33394 :   Peeling peeling(graph, tmp_zone, estimated_peeled_size, &iter->node_pairs_);
     218             : 
     219       33394 :   Node* dead = graph->NewNode(common->Dead());
     220             : 
     221             :   // Map the loop header nodes to their entry values.
     222      166311 :   for (Node* node : loop_tree->HeaderNodes(loop)) {
     223      132917 :     peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
     224             :   }
     225             : 
     226             :   // Copy all the nodes of loop body for the peeled iteration.
     227       33394 :   peeling.CopyNodes(graph, tmp_zone, dead, loop_tree->BodyNodes(loop));
     228             : 
     229             :   //============================================================================
     230             :   // Replace the entry to the loop with the output of the peeled iteration.
     231             :   //============================================================================
     232       33394 :   Node* loop_node = loop_tree->GetLoopControl(loop);
     233             :   Node* new_entry;
     234       33394 :   int backedges = loop_node->InputCount() - 1;
     235       33394 :   if (backedges > 1) {
     236             :     // Multiple backedges from original loop, therefore multiple output edges
     237             :     // from the peeled iteration.
     238             :     NodeVector inputs(tmp_zone);
     239          18 :     for (int i = 1; i < loop_node->InputCount(); i++) {
     240          12 :       inputs.push_back(peeling.map(loop_node->InputAt(i)));
     241             :     }
     242             :     Node* merge =
     243           3 :         graph->NewNode(common->Merge(backedges), backedges, &inputs[0]);
     244             : 
     245             :     // Merge values from the multiple output edges of the peeled iteration.
     246          10 :     for (Node* node : loop_tree->HeaderNodes(loop)) {
     247           5 :       if (node->opcode() == IrOpcode::kLoop) continue;  // already done.
     248             :       inputs.clear();
     249           8 :       for (int i = 0; i < backedges; i++) {
     250          12 :         inputs.push_back(peeling.map(node->InputAt(1 + i)));
     251             :       }
     252           6 :       for (Node* input : inputs) {
     253           4 :         if (input != inputs[0]) {  // Non-redundant phi.
     254           2 :           inputs.push_back(merge);
     255           2 :           const Operator* op = common->ResizeMergeOrPhi(node->op(), backedges);
     256           2 :           Node* phi = graph->NewNode(op, backedges + 1, &inputs[0]);
     257           2 :           node->ReplaceInput(0, phi);
     258           2 :           break;
     259             :         }
     260             :       }
     261             :     }
     262           3 :     new_entry = merge;
     263             :   } else {
     264             :     // Only one backedge, simply replace the input to loop with output of
     265             :     // peeling.
     266      166303 :     for (Node* node : loop_tree->HeaderNodes(loop)) {
     267      132912 :       node->ReplaceInput(0, peeling.map(node->InputAt(1)));
     268             :     }
     269       33391 :     new_entry = peeling.map(loop_node->InputAt(1));
     270             :   }
     271       33394 :   loop_node->ReplaceInput(0, new_entry);
     272             : 
     273             :   //============================================================================
     274             :   // Change the exit and exit markers to merge/phi/effect-phi.
     275             :   //============================================================================
     276      256711 :   for (Node* exit : loop_tree->ExitNodes(loop)) {
     277      223317 :     switch (exit->opcode()) {
     278             :       case IrOpcode::kLoopExit:
     279             :         // Change the loop exit node to a merge node.
     280       75537 :         exit->ReplaceInput(1, peeling.map(exit->InputAt(0)));
     281       75537 :         NodeProperties::ChangeOp(exit, common->Merge(2));
     282       75537 :         break;
     283             :       case IrOpcode::kLoopExitValue:
     284             :         // Change exit marker to phi.
     285      144506 :         exit->InsertInput(graph->zone(), 1, peeling.map(exit->InputAt(0)));
     286             :         NodeProperties::ChangeOp(
     287       72253 :             exit, common->Phi(MachineRepresentation::kTagged, 2));
     288       72253 :         break;
     289             :       case IrOpcode::kLoopExitEffect:
     290             :         // Change effect exit marker to effect phi.
     291      151054 :         exit->InsertInput(graph->zone(), 1, peeling.map(exit->InputAt(0)));
     292       75527 :         NodeProperties::ChangeOp(exit, common->EffectPhi(2));
     293       75527 :         break;
     294             :       default:
     295             :         break;
     296             :     }
     297             :   }
     298             :   return iter;
     299             : }
     300             : 
     301             : namespace {
     302             : 
     303       44014 : void PeelInnerLoops(Graph* graph, CommonOperatorBuilder* common,
     304       37240 :                     LoopTree* loop_tree, LoopTree::Loop* loop,
     305             :                     Zone* temp_zone) {
     306             :   // If the loop has nested loops, peel inside those.
     307       44014 :   if (!loop->children().empty()) {
     308       22042 :     for (LoopTree::Loop* inner_loop : loop->children()) {
     309        7634 :       PeelInnerLoops(graph, common, loop_tree, inner_loop, temp_zone);
     310             :     }
     311             :     return;
     312             :   }
     313             :   // Only peel small-enough loops.
     314       37240 :   if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return;
     315       37154 :   if (FLAG_trace_turbo_loop) {
     316           0 :     PrintF("Peeling loop with header: ");
     317           0 :     for (Node* node : loop_tree->HeaderNodes(loop)) {
     318           0 :       PrintF("%i ", node->id());
     319             :     }
     320           0 :     PrintF("\n");
     321             :   }
     322             : 
     323       37154 :   LoopPeeler::Peel(graph, common, loop_tree, loop, temp_zone);
     324             : }
     325             : 
     326       66776 : void EliminateLoopExit(Node* node) {
     327             :   DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
     328             :   // The exit markers take the loop exit as input. We iterate over uses
     329             :   // and remove all the markers from the graph.
     330      513036 :   for (Edge edge : node->use_edges()) {
     331      223130 :     if (NodeProperties::IsControlEdge(edge)) {
     332      223130 :       Node* marker = edge.from();
     333      223130 :       if (marker->opcode() == IrOpcode::kLoopExitValue) {
     334       85190 :         NodeProperties::ReplaceUses(marker, marker->InputAt(0));
     335       85190 :         marker->Kill();
     336      137940 :       } else if (marker->opcode() == IrOpcode::kLoopExitEffect) {
     337             :         NodeProperties::ReplaceUses(marker, nullptr,
     338       66776 :                                     NodeProperties::GetEffectInput(marker));
     339       66776 :         marker->Kill();
     340             :       }
     341             :     }
     342             :   }
     343             :   NodeProperties::ReplaceUses(node, nullptr, nullptr,
     344       66776 :                               NodeProperties::GetControlInput(node, 0));
     345       66776 :   node->Kill();
     346       66776 : }
     347             : 
     348             : }  // namespace
     349             : 
     350             : // static
     351      388307 : void LoopPeeler::PeelInnerLoopsOfTree(Graph* graph,
     352             :                                       CommonOperatorBuilder* common,
     353             :                                       LoopTree* loop_tree, Zone* temp_zone) {
     354      812994 :   for (LoopTree::Loop* loop : loop_tree->outer_loops()) {
     355       36380 :     PeelInnerLoops(graph, common, loop_tree, loop, temp_zone);
     356             :   }
     357             : 
     358      388307 :   EliminateLoopExits(graph, temp_zone);
     359      388307 : }
     360             : 
     361             : // static
     362     1185909 : void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* temp_zone) {
     363      395303 :   ZoneQueue<Node*> queue(temp_zone);
     364             :   ZoneVector<bool> visited(graph->NodeCount(), false, temp_zone);
     365      790606 :   queue.push(graph->end());
     366     7914015 :   while (!queue.empty()) {
     367    28983240 :     Node* node = queue.front();
     368             :     queue.pop();
     369             : 
     370     7123409 :     if (node->opcode() == IrOpcode::kLoopExit) {
     371       66776 :       Node* control = NodeProperties::GetControlInput(node);
     372       66776 :       EliminateLoopExit(node);
     373      200328 :       if (!visited[control->id()]) {
     374             :         visited[control->id()] = true;
     375             :         queue.push(control);
     376             :       }
     377             :     } else {
     378    37152633 :       for (int i = 0; i < node->op()->ControlInputCount(); i++) {
     379     7679789 :         Node* control = NodeProperties::GetControlInput(node, i);
     380    23039367 :         if (!visited[control->id()]) {
     381             :           visited[control->id()] = true;
     382             :           queue.push(control);
     383             :         }
     384             :       }
     385             :     }
     386             :   }
     387      395303 : }
     388             : 
     389             : }  // namespace compiler
     390             : }  // namespace internal
     391             : }  // namespace v8

Generated by: LCOV version 1.10