blob: 34f53b5e475b0e347812aab81f3b897316c61ad3 [file] [log] [blame]
// 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.
#include "src/compiler/loop-peeling.h"
#include "src/compiler/common-operator.h"
#include "src/compiler/compiler-source-position-table.h"
#include "src/compiler/graph.h"
#include "src/compiler/node-marker.h"
#include "src/compiler/node-origin-table.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/zone/zone.h"
// 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;
Peeling(Graph* graph, size_t max, NodeVector* p)
: 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);
}
void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead, NodeRange nodes,
SourcePositionTable* source_positions,
NodeOriginTable* node_origins) {
NodeVector inputs(tmp_zone_);
// Copy all the nodes first.
for (Node* node : nodes) {
SourcePositionTable::Scope position(
source_positions, source_positions->GetSourcePosition(node));
NodeOriginTable::Scope origin_scope(node_origins, "copy nodes", node);
inputs.clear();
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);
}
// 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;
}
bool LoopPeeler::CanPeel(LoopTree::Loop* loop) {
// Look for returns and if projections that are outside the loop but whose
// control input is inside the loop.
Node* loop_node = loop_tree_->GetLoopControl(loop);
for (Node* node : loop_tree_->LoopNodes(loop)) {
for (Node* use : node->uses()) {
if (!loop_tree_->Contains(loop, use)) {
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) {
if (FLAG_trace_turbo_loop) {
Node* loop_node = loop_tree_->GetLoopControl(loop);
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;
}
}
}
}
return true;
}
PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) {
if (!CanPeel(loop)) return nullptr;
//============================================================================
// Construct the peeled iteration.
//============================================================================
PeeledIterationImpl* iter = tmp_zone_->New<PeeledIterationImpl>(tmp_zone_);
size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2;
Peeling peeling(graph_, estimated_peeled_size, &iter->node_pairs_);
Node* dead = graph_->NewNode(common_->Dead());
// Map the loop header nodes to their entry values.
for (Node* node : loop_tree_->HeaderNodes(loop)) {
peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
}
// Copy all the nodes of loop body for the peeled iteration.
peeling.CopyNodes(graph_, tmp_zone_, dead, loop_tree_->BodyNodes(loop),
source_positions_, node_origins_);
//============================================================================
// Replace the entry to the loop with the output of the peeled iteration.
//============================================================================
Node* loop_node = loop_tree_->GetLoopControl(loop);
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.
NodeVector inputs(tmp_zone_);
for (int i = 1; i < loop_node->InputCount(); i++) {
inputs.push_back(peeling.map(loop_node->InputAt(i)));
}
Node* merge =
graph_->NewNode(common_->Merge(backedges), backedges, &inputs[0]);
// Merge values from the multiple output edges of the peeled iteration.
for (Node* node : loop_tree_->HeaderNodes(loop)) {
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);
const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges);
Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]);
node->ReplaceInput(0, phi);
break;
}
}
}
new_entry = merge;
} else {
// Only one backedge, simply replace the input to loop with output of
// peeling.
for (Node* node : loop_tree_->HeaderNodes(loop)) {
node->ReplaceInput(0, peeling.map(node->InputAt(1)));
}
new_entry = peeling.map(loop_node->InputAt(1));
}
loop_node->ReplaceInput(0, new_entry);
//============================================================================
// Change the exit and exit markers to merge/phi/effect-phi.
//============================================================================
for (Node* exit : loop_tree_->ExitNodes(loop)) {
switch (exit->opcode()) {
case IrOpcode::kLoopExit:
// Change the loop exit node to a merge node.
exit->ReplaceInput(1, peeling.map(exit->InputAt(0)));
NodeProperties::ChangeOp(exit, common_->Merge(2));
break;
case IrOpcode::kLoopExitValue:
// Change exit marker to phi.
exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0)));
NodeProperties::ChangeOp(
exit, common_->Phi(MachineRepresentation::kTagged, 2));
break;
case IrOpcode::kLoopExitEffect:
// Change effect exit marker to effect phi.
exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0)));
NodeProperties::ChangeOp(exit, common_->EffectPhi(2));
break;
default:
break;
}
}
return iter;
}
void LoopPeeler::PeelInnerLoops(LoopTree::Loop* loop) {
// If the loop has nested loops, peel inside those.
if (!loop->children().empty()) {
for (LoopTree::Loop* inner_loop : loop->children()) {
PeelInnerLoops(inner_loop);
}
return;
}
// Only peel small-enough loops.
if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return;
if (FLAG_trace_turbo_loop) {
PrintF("Peeling loop with header: ");
for (Node* node : loop_tree_->HeaderNodes(loop)) {
PrintF("%i ", node->id());
}
PrintF("\n");
}
Peel(loop);
}
namespace {
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
void LoopPeeler::PeelInnerLoopsOfTree() {
for (LoopTree::Loop* loop : loop_tree_->outer_loops()) {
PeelInnerLoops(loop);
}
EliminateLoopExits(graph_, tmp_zone_);
}
// static
void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* tmp_zone) {
ZoneQueue<Node*> queue(tmp_zone);
ZoneVector<bool> visited(graph->NodeCount(), false, tmp_zone);
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);
}
}
}
}
}
} // namespace compiler
} // namespace internal
} // namespace v8