loop-peeling.cc 14.5 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-properties.h"
11 12
#include "src/compiler/node.h"
#include "src/zone/zone.h"
13 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

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

111
  Peeling(Graph* graph, size_t max, NodeVector* p)
112 113 114 115 116 117 118 119 120 121 122 123 124
      : 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);
  }

125 126 127
  void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead, NodeRange nodes,
                 SourcePositionTable* source_positions) {
    NodeVector inputs(tmp_zone_);
128 129
    // Copy all the nodes first.
    for (Node* node : nodes) {
130 131
      SourcePositionTable::Scope position(
          source_positions, source_positions->GetSourcePosition(node));
132
      inputs.clear();
133 134 135 136 137 138 139 140
      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);
141 142 143 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
    }

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

173
bool LoopPeeler::CanPeel(LoopTree::Loop* loop) {
174 175
  // Look for returns and if projections that are outside the loop but whose
  // control input is inside the loop.
176 177
  Node* loop_node = loop_tree_->GetLoopControl(loop);
  for (Node* node : loop_tree_->LoopNodes(loop)) {
178
    for (Node* use : node->uses()) {
179
      if (!loop_tree_->Contains(loop, use)) {
180 181 182 183 184 185 186 187 188 189 190 191 192
        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) {
193
          if (FLAG_trace_turbo_loop) {
194
            Node* loop_node = loop_tree_->GetLoopControl(loop);
195 196 197 198 199 200 201 202
            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;
203 204 205 206
        }
      }
    }
  }
207
  return true;
208 209
}

210 211
PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) {
  if (!CanPeel(loop)) return nullptr;
212 213 214 215

  //============================================================================
  // Construct the peeled iteration.
  //============================================================================
216
  PeeledIterationImpl* iter = new (tmp_zone_) PeeledIterationImpl(tmp_zone_);
217
  size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2;
218
  Peeling peeling(graph_, estimated_peeled_size, &iter->node_pairs_);
219

220
  Node* dead = graph_->NewNode(common_->Dead());
221 222

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

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

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

    // Merge values from the multiple output edges of the peeled iteration.
248
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
249 250 251 252 253 254 255 256
      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);
257 258
          const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges);
          Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]);
259 260 261 262 263 264 265 266 267
          node->ReplaceInput(0, phi);
          break;
        }
      }
    }
    new_entry = merge;
  } else {
    // Only one backedge, simply replace the input to loop with output of
    // peeling.
268
    for (Node* node : loop_tree_->HeaderNodes(loop)) {
269
      node->ReplaceInput(0, peeling.map(node->InputAt(1)));
270 271 272 273 274 275
    }
    new_entry = peeling.map(loop_node->InputAt(1));
  }
  loop_node->ReplaceInput(0, new_entry);

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

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

321
  Peel(loop);
322 323
}

324 325
namespace {

326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349
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

350 351 352
void LoopPeeler::PeelInnerLoopsOfTree() {
  for (LoopTree::Loop* loop : loop_tree_->outer_loops()) {
    PeelInnerLoops(loop);
353 354
  }

355
  EliminateLoopExits(graph_, tmp_zone_);
356 357
}

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

386 387 388
}  // namespace compiler
}  // namespace internal
}  // namespace v8