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 100namespace v8 { 101namespace internal { 102namespace compiler { 103 104struct 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 : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {} 112 113 Node* map(Node* node) { 114 if (node_map.Get(node) == 0) return node; 115 return pairs->at(node_map.Get(node)); 116 } 117 118 void Insert(Node* original, Node* copy) { 119 node_map.Set(original, 1 + pairs->size()); 120 pairs->push_back(original); 121 pairs->push_back(copy); 122 } 123 124 void CopyNodes(Graph* graph, Zone* tmp_zone, Node* dead, NodeRange nodes) { 125 NodeVector inputs(tmp_zone); 126 // Copy all the nodes first. 127 for (Node* node : nodes) { 128 inputs.clear(); 129 for (Node* input : node->inputs()) { 130 inputs.push_back(map(input)); 131 } 132 Node* copy = graph->NewNode(node->op(), node->InputCount(), &inputs[0]); 133 if (NodeProperties::IsTyped(node)) { 134 NodeProperties::SetType(copy, NodeProperties::GetType(node)); 135 } 136 Insert(node, copy); 137 } 138 139 // Fix remaining inputs of the copies. 140 for (Node* original : nodes) { 141 Node* copy = pairs->at(node_map.Get(original)); 142 for (int i = 0; i < copy->InputCount(); i++) { 143 copy->ReplaceInput(i, map(original->InputAt(i))); 144 } 145 } 146 } 147 148 bool Marked(Node* node) { return node_map.Get(node) > 0; } 149}; 150 151 152class PeeledIterationImpl : public PeeledIteration { 153 public: 154 NodeVector node_pairs_; 155 explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {} 156}; 157 158 159Node* 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 for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) { 164 if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1]; 165 } 166 return node; 167} 168 169bool 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 Node* loop_node = loop_tree->GetLoopControl(loop); 173 for (Node* node : loop_tree->LoopNodes(loop)) { 174 for (Node* use : node->uses()) { 175 if (!loop_tree->Contains(loop, use)) { 176 bool unmarked_exit; 177 switch (node->opcode()) { 178 case IrOpcode::kLoopExit: 179 unmarked_exit = (node->InputAt(1) != loop_node); 180 break; 181 case IrOpcode::kLoopExitValue: 182 case IrOpcode::kLoopExitEffect: 183 unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node); 184 break; 185 default: 186 unmarked_exit = (use->opcode() != IrOpcode::kTerminate); 187 } 188 if (unmarked_exit) { 189 if (FLAG_trace_turbo_loop) { 190 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 use->op()->mnemonic()); 197 } 198 return false; 199 } 200 } 201 } 202 } 203 return true; 204} 205 206 207PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common, 208 LoopTree* loop_tree, LoopTree::Loop* loop, 209 Zone* tmp_zone) { 210 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 size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2; 217 Peeling peeling(graph, tmp_zone, estimated_peeled_size, &iter->node_pairs_); 218 219 Node* dead = graph->NewNode(common->Dead()); 220 221 // Map the loop header nodes to their entry values. 222 for (Node* node : loop_tree->HeaderNodes(loop)) { 223 peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex)); 224 } 225 226 // Copy all the nodes of loop body for the peeled iteration. 227 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 Node* loop_node = loop_tree->GetLoopControl(loop); 233 Node* new_entry; 234 int backedges = loop_node->InputCount() - 1; 235 if (backedges > 1) { 236 // Multiple backedges from original loop, therefore multiple output edges 237 // from the peeled iteration. 238 NodeVector inputs(tmp_zone); 239 for (int i = 1; i < loop_node->InputCount(); i++) { 240 inputs.push_back(peeling.map(loop_node->InputAt(i))); 241 } 242 Node* merge = 243 graph->NewNode(common->Merge(backedges), backedges, &inputs[0]); 244 245 // Merge values from the multiple output edges of the peeled iteration. 246 for (Node* node : loop_tree->HeaderNodes(loop)) { 247 if (node->opcode() == IrOpcode::kLoop) continue; // already done. 248 inputs.clear(); 249 for (int i = 0; i < backedges; i++) { 250 inputs.push_back(peeling.map(node->InputAt(1 + i))); 251 } 252 for (Node* input : inputs) { 253 if (input != inputs[0]) { // Non-redundant phi. 254 inputs.push_back(merge); 255 const Operator* op = common->ResizeMergeOrPhi(node->op(), backedges); 256 Node* phi = graph->NewNode(op, backedges + 1, &inputs[0]); 257 node->ReplaceInput(0, phi); 258 break; 259 } 260 } 261 } 262 new_entry = merge; 263 } else { 264 // Only one backedge, simply replace the input to loop with output of 265 // peeling. 266 for (Node* node : loop_tree->HeaderNodes(loop)) { 267 node->ReplaceInput(0, peeling.map(node->InputAt(1))); 268 } 269 new_entry = peeling.map(loop_node->InputAt(1)); 270 } 271 loop_node->ReplaceInput(0, new_entry); 272 273 //============================================================================ 274 // Change the exit and exit markers to merge/phi/effect-phi. 275 //============================================================================ 276 for (Node* exit : loop_tree->ExitNodes(loop)) { 277 switch (exit->opcode()) { 278 case IrOpcode::kLoopExit: 279 // Change the loop exit node to a merge node. 280 exit->ReplaceInput(1, peeling.map(exit->InputAt(0))); 281 NodeProperties::ChangeOp(exit, common->Merge(2)); 282 break; 283 case IrOpcode::kLoopExitValue: 284 // Change exit marker to phi. 285 exit->InsertInput(graph->zone(), 1, peeling.map(exit->InputAt(0))); 286 NodeProperties::ChangeOp( 287 exit, common->Phi(MachineRepresentation::kTagged, 2)); 288 break; 289 case IrOpcode::kLoopExitEffect: 290 // Change effect exit marker to effect phi. 291 exit->InsertInput(graph->zone(), 1, peeling.map(exit->InputAt(0))); 292 NodeProperties::ChangeOp(exit, common->EffectPhi(2)); 293 break; 294 default: 295 break; 296 } 297 } 298 return iter; 299} 300 301namespace { 302 303void PeelInnerLoops(Graph* graph, CommonOperatorBuilder* common, 304 LoopTree* loop_tree, LoopTree::Loop* loop, 305 Zone* temp_zone) { 306 // If the loop has nested loops, peel inside those. 307 if (!loop->children().empty()) { 308 for (LoopTree::Loop* inner_loop : loop->children()) { 309 PeelInnerLoops(graph, common, loop_tree, inner_loop, temp_zone); 310 } 311 return; 312 } 313 // Only peel small-enough loops. 314 if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return; 315 if (FLAG_trace_turbo_loop) { 316 PrintF("Peeling loop with header: "); 317 for (Node* node : loop_tree->HeaderNodes(loop)) { 318 PrintF("%i ", node->id()); 319 } 320 PrintF("\n"); 321 } 322 323 LoopPeeler::Peel(graph, common, loop_tree, loop, temp_zone); 324} 325 326void 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 for (Edge edge : node->use_edges()) { 331 if (NodeProperties::IsControlEdge(edge)) { 332 Node* marker = edge.from(); 333 if (marker->opcode() == IrOpcode::kLoopExitValue) { 334 NodeProperties::ReplaceUses(marker, marker->InputAt(0)); 335 marker->Kill(); 336 } else if (marker->opcode() == IrOpcode::kLoopExitEffect) { 337 NodeProperties::ReplaceUses(marker, nullptr, 338 NodeProperties::GetEffectInput(marker)); 339 marker->Kill(); 340 } 341 } 342 } 343 NodeProperties::ReplaceUses(node, nullptr, nullptr, 344 NodeProperties::GetControlInput(node, 0)); 345 node->Kill(); 346} 347 348} // namespace 349 350// static 351void LoopPeeler::PeelInnerLoopsOfTree(Graph* graph, 352 CommonOperatorBuilder* common, 353 LoopTree* loop_tree, Zone* temp_zone) { 354 for (LoopTree::Loop* loop : loop_tree->outer_loops()) { 355 PeelInnerLoops(graph, common, loop_tree, loop, temp_zone); 356 } 357 358 EliminateLoopExits(graph, temp_zone); 359} 360 361// static 362void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* temp_zone) { 363 ZoneQueue<Node*> queue(temp_zone); 364 ZoneVector<bool> visited(graph->NodeCount(), false, temp_zone); 365 queue.push(graph->end()); 366 while (!queue.empty()) { 367 Node* node = queue.front(); 368 queue.pop(); 369 370 if (node->opcode() == IrOpcode::kLoopExit) { 371 Node* control = NodeProperties::GetControlInput(node); 372 EliminateLoopExit(node); 373 if (!visited[control->id()]) { 374 visited[control->id()] = true; 375 queue.push(control); 376 } 377 } else { 378 for (int i = 0; i < node->op()->ControlInputCount(); i++) { 379 Node* control = NodeProperties::GetControlInput(node, i); 380 if (!visited[control->id()]) { 381 visited[control->id()] = true; 382 queue.push(control); 383 } 384 } 385 } 386 } 387} 388 389} // namespace compiler 390} // namespace internal 391} // namespace v8 392