loop-peeling.cc 11.8 KB
Newer Older
1 2 3 4
// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/compiler/loop-peeling.h"
6

7
#include "src/compiler/common-operator.h"
8
#include "src/compiler/compiler-source-position-table.h"
9
#include "src/compiler/graph.h"
10
#include "src/compiler/loop-analysis.h"
11
#include "src/compiler/node-marker.h"
12
#include "src/compiler/node-origin-table.h"
13
#include "src/compiler/node-properties.h"
14 15
#include "src/compiler/node.h"
#include "src/zone/zone.h"
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124

// Loop peeling is an optimization that copies the body of a loop, creating
// a new copy of the body called the "peeled iteration" that represents the
// first iteration. Beginning with a loop as follows:

//             E
//             |                 A
//             |                 |                     (backedges)
//             | +---------------|---------------------------------+
//             | | +-------------|-------------------------------+ |
//             | | |             | +--------+                    | |
//             | | |             | | +----+ |                    | |
//             | | |             | | |    | |                    | |
//           ( Loop )<-------- ( phiA )   | |                    | |
//              |                 |       | |                    | |
//      ((======P=================U=======|=|=====))             | |
//      ((                                | |     ))             | |
//      ((        X <---------------------+ |     ))             | |
//      ((                                  |     ))             | |
//      ((     body                         |     ))             | |
//      ((                                  |     ))             | |
//      ((        Y <-----------------------+     ))             | |
//      ((                                        ))             | |
//      ((===K====L====M==========================))             | |
//           |    |    |                                         | |
//           |    |    +-----------------------------------------+ |
//           |    +------------------------------------------------+
//           |
//          exit

// The body of the loop is duplicated so that all nodes considered "inside"
// the loop (e.g. {P, U, X, Y, K, L, M}) have a corresponding copies in the
// peeled iteration (e.g. {P', U', X', Y', K', L', M'}). What were considered
// backedges of the loop correspond to edges from the peeled iteration to
// the main loop body, with multiple backedges requiring a merge.

// Similarly, any exits from the loop body need to be merged with "exits"
// from the peeled iteration, resulting in the graph as follows:

//             E
//             |                 A
//             |                 |
//      ((=====P'================U'===============))
//      ((                                        ))
//      ((        X'<-------------+               ))
//      ((                        |               ))
//      ((   peeled iteration     |               ))
//      ((                        |               ))
//      ((        Y'<-----------+ |               ))
//      ((                      | |               ))
//      ((===K'===L'====M'======|=|===============))
//           |    |     |       | |
//  +--------+    +-+ +-+       | |
//  |               | |         | |
//  |              Merge <------phi
//  |                |           |
//  |          +-----+           |
//  |          |                 |                     (backedges)
//  |          | +---------------|---------------------------------+
//  |          | | +-------------|-------------------------------+ |
//  |          | | |             | +--------+                    | |
//  |          | | |             | | +----+ |                    | |
//  |          | | |             | | |    | |                    | |
//  |        ( Loop )<-------- ( phiA )   | |                    | |
//  |           |                 |       | |                    | |
//  |   ((======P=================U=======|=|=====))             | |
//  |   ((                                | |     ))             | |
//  |   ((        X <---------------------+ |     ))             | |
//  |   ((                                  |     ))             | |
//  |   ((     body                         |     ))             | |
//  |   ((                                  |     ))             | |
//  |   ((        Y <-----------------------+     ))             | |
//  |   ((                                        ))             | |
//  |   ((===K====L====M==========================))             | |
//  |        |    |    |                                         | |
//  |        |    |    +-----------------------------------------+ |
//  |        |    +------------------------------------------------+
//  |        |
//  |        |
//  +----+ +-+
//       | |
//      Merge
//        |
//      exit

// Note that the boxes ((===)) above are not explicitly represented in the
// graph, but are instead computed by the {LoopFinder}.

namespace v8 {
namespace internal {
namespace compiler {

class PeeledIterationImpl : public PeeledIteration {
 public:
  NodeVector node_pairs_;
  explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {}
};


Node* PeeledIteration::map(Node* node) {
  // TODO(turbofan): we use a simple linear search, since the peeled iteration
  // is really only used in testing.
  PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this);
  for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) {
    if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1];
  }
  return node;
}

125 126
PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) {
  if (!CanPeel(loop)) return nullptr;
127 128 129 130

  //============================================================================
  // Construct the peeled iteration.
  //============================================================================
131
  PeeledIterationImpl* iter = tmp_zone_->New<PeeledIterationImpl>(tmp_zone_);
132 133
  uint32_t estimated_peeled_size = 5 + loop->TotalSize() * 2;
  NodeCopier copier(graph_, estimated_peeled_size, &iter->node_pairs_, 1);
134

135
  Node* dead = graph_->NewNode(common_->Dead());
136 137

  // Map the loop header nodes to their entry values.
138
  for (Node* node : loop_tree_->HeaderNodes(loop)) {
139
    copier.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
140 141 142
  }

  // Copy all the nodes of loop body for the peeled iteration.
143 144
  copier.CopyNodes(graph_, tmp_zone_, dead, loop_tree_->BodyNodes(loop),
                   source_positions_, node_origins_);
145 146 147 148

  //============================================================================
  // Replace the entry to the loop with the output of the peeled iteration.
  //============================================================================
149
  Node* loop_node = loop_tree_->GetLoopControl(loop);
150 151 152 153 154
  Node* new_entry;
  int backedges = loop_node->InputCount() - 1;
  if (backedges > 1) {
    // Multiple backedges from original loop, therefore multiple output edges
    // from the peeled iteration.
155
    NodeVector inputs(tmp_zone_);
156
    for (int i = 1; i < loop_node->InputCount(); i++) {
157
      inputs.push_back(copier.map(loop_node->InputAt(i)));
158 159
    }
    Node* merge =
160
        graph_->NewNode(common_->Merge(backedges), backedges, &inputs[0]);
161 162

    // Merge values from the multiple output edges of the peeled iteration.
163
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
164 165 166
      if (node->opcode() == IrOpcode::kLoop) continue;  // already done.
      inputs.clear();
      for (int i = 0; i < backedges; i++) {
167
        inputs.push_back(copier.map(node->InputAt(1 + i)));
168 169 170 171
      }
      for (Node* input : inputs) {
        if (input != inputs[0]) {  // Non-redundant phi.
          inputs.push_back(merge);
172 173
          const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges);
          Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]);
174 175 176 177 178 179 180 181 182
          node->ReplaceInput(0, phi);
          break;
        }
      }
    }
    new_entry = merge;
  } else {
    // Only one backedge, simply replace the input to loop with output of
    // peeling.
183
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
184
      node->ReplaceInput(0, copier.map(node->InputAt(1)));
185
    }
186
    new_entry = copier.map(loop_node->InputAt(1));
187 188 189 190
  }
  loop_node->ReplaceInput(0, new_entry);

  //============================================================================
191
  // Change the exit and exit markers to merge/phi/effect-phi.
192
  //============================================================================
193
  for (Node* exit : loop_tree_->ExitNodes(loop)) {
194 195 196
    switch (exit->opcode()) {
      case IrOpcode::kLoopExit:
        // Change the loop exit node to a merge node.
197
        exit->ReplaceInput(1, copier.map(exit->InputAt(0)));
198
        NodeProperties::ChangeOp(exit, common_->Merge(2));
199 200 201
        break;
      case IrOpcode::kLoopExitValue:
        // Change exit marker to phi.
202
        exit->InsertInput(graph_->zone(), 1, copier.map(exit->InputAt(0)));
203
        NodeProperties::ChangeOp(
204
            exit, common_->Phi(LoopExitValueRepresentationOf(exit->op()), 2));
205 206 207
        break;
      case IrOpcode::kLoopExitEffect:
        // Change effect exit marker to effect phi.
208
        exit->InsertInput(graph_->zone(), 1, copier.map(exit->InputAt(0)));
209
        NodeProperties::ChangeOp(exit, common_->EffectPhi(2));
210 211 212 213
        break;
      default:
        break;
    }
214
  }
215 216
  return iter;
}
217

218
void LoopPeeler::PeelInnerLoops(LoopTree::Loop* loop) {
219 220 221
  // If the loop has nested loops, peel inside those.
  if (!loop->children().empty()) {
    for (LoopTree::Loop* inner_loop : loop->children()) {
222
      PeelInnerLoops(inner_loop);
223 224 225 226 227
    }
    return;
  }
  // Only peel small-enough loops.
  if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return;
228
  if (FLAG_trace_turbo_loop) {
229
    PrintF("Peeling loop with header: ");
230
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
231
      PrintF("%i ", node->id());
232
    }
233
    PrintF("\n");
234 235
  }

236
  Peel(loop);
237 238
}

239
void LoopPeeler::EliminateLoopExit(Node* node) {
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
  DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
  // The exit markers take the loop exit as input. We iterate over uses
  // and remove all the markers from the graph.
  for (Edge edge : node->use_edges()) {
    if (NodeProperties::IsControlEdge(edge)) {
      Node* marker = edge.from();
      if (marker->opcode() == IrOpcode::kLoopExitValue) {
        NodeProperties::ReplaceUses(marker, marker->InputAt(0));
        marker->Kill();
      } else if (marker->opcode() == IrOpcode::kLoopExitEffect) {
        NodeProperties::ReplaceUses(marker, nullptr,
                                    NodeProperties::GetEffectInput(marker));
        marker->Kill();
      }
    }
  }
  NodeProperties::ReplaceUses(node, nullptr, nullptr,
                              NodeProperties::GetControlInput(node, 0));
  node->Kill();
}

261 262 263
void LoopPeeler::PeelInnerLoopsOfTree() {
  for (LoopTree::Loop* loop : loop_tree_->outer_loops()) {
    PeelInnerLoops(loop);
264 265
  }

266
  EliminateLoopExits(graph_, tmp_zone_);
267 268
}

269
// static
270 271 272
void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* tmp_zone) {
  ZoneQueue<Node*> queue(tmp_zone);
  ZoneVector<bool> visited(graph->NodeCount(), false, tmp_zone);
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
  queue.push(graph->end());
  while (!queue.empty()) {
    Node* node = queue.front();
    queue.pop();

    if (node->opcode() == IrOpcode::kLoopExit) {
      Node* control = NodeProperties::GetControlInput(node);
      EliminateLoopExit(node);
      if (!visited[control->id()]) {
        visited[control->id()] = true;
        queue.push(control);
      }
    } else {
      for (int i = 0; i < node->op()->ControlInputCount(); i++) {
        Node* control = NodeProperties::GetControlInput(node, i);
        if (!visited[control->id()]) {
          visited[control->id()] = true;
          queue.push(control);
        }
      }
    }
  }
}

297 298 299
}  // namespace compiler
}  // namespace internal
}  // namespace v8