loop-peeling.cc 14.7 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
#include "src/compiler/common-operator.h"
7
#include "src/compiler/compiler-source-position-table.h"
8 9
#include "src/compiler/graph.h"
#include "src/compiler/node-marker.h"
10
#include "src/compiler/node-origin-table.h"
11
#include "src/compiler/node-properties.h"
12 13
#include "src/compiler/node.h"
#include "src/zone/zone.h"
14 15 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

// 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 {

struct Peeling {
  // Maps a node to its index in the {pairs} vector.
  NodeMarker<size_t> node_map;
  // The vector which contains the mapped nodes.
  NodeVector* pairs;

112
  Peeling(Graph* graph, size_t max, NodeVector* p)
113 114 115 116 117 118 119 120 121 122 123 124 125
      : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {}

  Node* map(Node* node) {
    if (node_map.Get(node) == 0) return node;
    return pairs->at(node_map.Get(node));
  }

  void Insert(Node* original, Node* copy) {
    node_map.Set(original, 1 + pairs->size());
    pairs->push_back(original);
    pairs->push_back(copy);
  }

126
  void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead, NodeRange nodes,
127 128
                 SourcePositionTable* source_positions,
                 NodeOriginTable* node_origins) {
129
    NodeVector inputs(tmp_zone_);
130 131
    // Copy all the nodes first.
    for (Node* node : nodes) {
132 133
      SourcePositionTable::Scope position(
          source_positions, source_positions->GetSourcePosition(node));
134
      NodeOriginTable::Scope origin_scope(node_origins, "copy nodes", node);
135
      inputs.clear();
136 137 138 139 140 141 142 143
      for (Node* input : node->inputs()) {
        inputs.push_back(map(input));
      }
      Node* copy = graph->NewNode(node->op(), node->InputCount(), &inputs[0]);
      if (NodeProperties::IsTyped(node)) {
        NodeProperties::SetType(copy, NodeProperties::GetType(node));
      }
      Insert(node, copy);
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
    }

    // Fix remaining inputs of the copies.
    for (Node* original : nodes) {
      Node* copy = pairs->at(node_map.Get(original));
      for (int i = 0; i < copy->InputCount(); i++) {
        copy->ReplaceInput(i, map(original->InputAt(i)));
      }
    }
  }

  bool Marked(Node* node) { return node_map.Get(node) > 0; }
};


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;
}

176
bool LoopPeeler::CanPeel(LoopTree::Loop* loop) {
177 178
  // Look for returns and if projections that are outside the loop but whose
  // control input is inside the loop.
179 180
  Node* loop_node = loop_tree_->GetLoopControl(loop);
  for (Node* node : loop_tree_->LoopNodes(loop)) {
181
    for (Node* use : node->uses()) {
182
      if (!loop_tree_->Contains(loop, use)) {
183 184 185 186 187 188 189 190 191 192 193 194 195
        bool unmarked_exit;
        switch (node->opcode()) {
          case IrOpcode::kLoopExit:
            unmarked_exit = (node->InputAt(1) != loop_node);
            break;
          case IrOpcode::kLoopExitValue:
          case IrOpcode::kLoopExitEffect:
            unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node);
            break;
          default:
            unmarked_exit = (use->opcode() != IrOpcode::kTerminate);
        }
        if (unmarked_exit) {
196
          if (FLAG_trace_turbo_loop) {
197
            Node* loop_node = loop_tree_->GetLoopControl(loop);
198 199 200 201 202 203 204 205
            PrintF(
                "Cannot peel loop %i. Loop exit without explicit mark: Node %i "
                "(%s) is inside "
                "loop, but its use %i (%s) is outside.\n",
                loop_node->id(), node->id(), node->op()->mnemonic(), use->id(),
                use->op()->mnemonic());
          }
          return false;
206 207 208 209
        }
      }
    }
  }
210
  return true;
211 212
}

213 214
PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) {
  if (!CanPeel(loop)) return nullptr;
215 216 217 218

  //============================================================================
  // Construct the peeled iteration.
  //============================================================================
219
  PeeledIterationImpl* iter = tmp_zone_->New<PeeledIterationImpl>(tmp_zone_);
220
  size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2;
221
  Peeling peeling(graph_, estimated_peeled_size, &iter->node_pairs_);
222

223
  Node* dead = graph_->NewNode(common_->Dead());
224 225

  // Map the loop header nodes to their entry values.
226
  for (Node* node : loop_tree_->HeaderNodes(loop)) {
227
    peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
228 229 230
  }

  // Copy all the nodes of loop body for the peeled iteration.
231
  peeling.CopyNodes(graph_, tmp_zone_, dead, loop_tree_->BodyNodes(loop),
232
                    source_positions_, node_origins_);
233 234 235 236

  //============================================================================
  // Replace the entry to the loop with the output of the peeled iteration.
  //============================================================================
237
  Node* loop_node = loop_tree_->GetLoopControl(loop);
238 239 240 241 242
  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.
243
    NodeVector inputs(tmp_zone_);
244 245 246 247
    for (int i = 1; i < loop_node->InputCount(); i++) {
      inputs.push_back(peeling.map(loop_node->InputAt(i)));
    }
    Node* merge =
248
        graph_->NewNode(common_->Merge(backedges), backedges, &inputs[0]);
249 250

    // Merge values from the multiple output edges of the peeled iteration.
251
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
252 253 254 255 256 257 258 259
      if (node->opcode() == IrOpcode::kLoop) continue;  // already done.
      inputs.clear();
      for (int i = 0; i < backedges; i++) {
        inputs.push_back(peeling.map(node->InputAt(1 + i)));
      }
      for (Node* input : inputs) {
        if (input != inputs[0]) {  // Non-redundant phi.
          inputs.push_back(merge);
260 261
          const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges);
          Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]);
262 263 264 265 266 267 268 269 270
          node->ReplaceInput(0, phi);
          break;
        }
      }
    }
    new_entry = merge;
  } else {
    // Only one backedge, simply replace the input to loop with output of
    // peeling.
271
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
272
      node->ReplaceInput(0, peeling.map(node->InputAt(1)));
273 274 275 276 277 278
    }
    new_entry = peeling.map(loop_node->InputAt(1));
  }
  loop_node->ReplaceInput(0, new_entry);

  //============================================================================
279
  // Change the exit and exit markers to merge/phi/effect-phi.
280
  //============================================================================
281
  for (Node* exit : loop_tree_->ExitNodes(loop)) {
282 283 284 285
    switch (exit->opcode()) {
      case IrOpcode::kLoopExit:
        // Change the loop exit node to a merge node.
        exit->ReplaceInput(1, peeling.map(exit->InputAt(0)));
286
        NodeProperties::ChangeOp(exit, common_->Merge(2));
287 288 289
        break;
      case IrOpcode::kLoopExitValue:
        // Change exit marker to phi.
290
        exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0)));
291
        NodeProperties::ChangeOp(
292
            exit, common_->Phi(LoopExitValueRepresentationOf(exit->op()), 2));
293 294 295
        break;
      case IrOpcode::kLoopExitEffect:
        // Change effect exit marker to effect phi.
296 297
        exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0)));
        NodeProperties::ChangeOp(exit, common_->EffectPhi(2));
298 299 300 301
        break;
      default:
        break;
    }
302
  }
303 304
  return iter;
}
305

306
void LoopPeeler::PeelInnerLoops(LoopTree::Loop* loop) {
307 308 309
  // If the loop has nested loops, peel inside those.
  if (!loop->children().empty()) {
    for (LoopTree::Loop* inner_loop : loop->children()) {
310
      PeelInnerLoops(inner_loop);
311 312 313 314 315
    }
    return;
  }
  // Only peel small-enough loops.
  if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return;
316
  if (FLAG_trace_turbo_loop) {
317
    PrintF("Peeling loop with header: ");
318
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
319
      PrintF("%i ", node->id());
320
    }
321
    PrintF("\n");
322 323
  }

324
  Peel(loop);
325 326
}

327 328
namespace {

329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352
void EliminateLoopExit(Node* node) {
  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();
}

}  // namespace

353 354 355
void LoopPeeler::PeelInnerLoopsOfTree() {
  for (LoopTree::Loop* loop : loop_tree_->outer_loops()) {
    PeelInnerLoops(loop);
356 357
  }

358
  EliminateLoopExits(graph_, tmp_zone_);
359 360
}

361
// static
362 363 364
void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* tmp_zone) {
  ZoneQueue<Node*> queue(tmp_zone);
  ZoneVector<bool> visited(graph->NodeCount(), false, tmp_zone);
365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
  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);
        }
      }
    }
  }
}

389 390 391
}  // namespace compiler
}  // namespace internal
}  // namespace v8