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/compiler-source-position-table.h" 8 #include "src/compiler/graph.h" 9 #include "src/compiler/node-marker.h" 10 #include "src/compiler/node-origin-table.h" 11 #include "src/compiler/node-properties.h" 12 #include "src/compiler/node.h" 13 #include "src/zone/zone.h" 14 15 // Loop peeling is an optimization that copies the body of a loop, creating 16 // a new copy of the body called the "peeled iteration" that represents the 17 // first iteration. Beginning with a loop as follows: 18 19 // E 20 // | A 21 // | | (backedges) 22 // | +---------------|---------------------------------+ 23 // | | +-------------|-------------------------------+ | 24 // | | | | +--------+ | | 25 // | | | | | +----+ | | | 26 // | | | | | | | | | | 27 // ( Loop )<-------- ( phiA ) | | | | 28 // | | | | | | 29 // ((======P=================U=======|=|=====)) | | 30 // (( | | )) | | 31 // (( X <---------------------+ | )) | | 32 // (( | )) | | 33 // (( body | )) | | 34 // (( | )) | | 35 // (( Y <-----------------------+ )) | | 36 // (( )) | | 37 // ((===K====L====M==========================)) | | 38 // | | | | | 39 // | | +-----------------------------------------+ | 40 // | +------------------------------------------------+ 41 // | 42 // exit 43 44 // The body of the loop is duplicated so that all nodes considered "inside" 45 // the loop (e.g. {P, U, X, Y, K, L, M}) have a corresponding copies in the 46 // peeled iteration (e.g. {P', U', X', Y', K', L', M'}). What were considered 47 // backedges of the loop correspond to edges from the peeled iteration to 48 // the main loop body, with multiple backedges requiring a merge. 49 50 // Similarly, any exits from the loop body need to be merged with "exits" 51 // from the peeled iteration, resulting in the graph as follows: 52 53 // E 54 // | A 55 // | | 56 // ((=====P'================U'===============)) 57 // (( )) 58 // (( X'<-------------+ )) 59 // (( | )) 60 // (( peeled iteration | )) 61 // (( | )) 62 // (( Y'<-----------+ | )) 63 // (( | | )) 64 // ((===K'===L'====M'======|=|===============)) 65 // | | | | | 66 // +--------+ +-+ +-+ | | 67 // | | | | | 68 // | Merge <------phi 69 // | | | 70 // | +-----+ | 71 // | | | (backedges) 72 // | | +---------------|---------------------------------+ 73 // | | | +-------------|-------------------------------+ | 74 // | | | | | +--------+ | | 75 // | | | | | | +----+ | | | 76 // | | | | | | | | | | | 77 // | ( Loop )<-------- ( phiA ) | | | | 78 // | | | | | | | 79 // | ((======P=================U=======|=|=====)) | | 80 // | (( | | )) | | 81 // | (( X <---------------------+ | )) | | 82 // | (( | )) | | 83 // | (( body | )) | | 84 // | (( | )) | | 85 // | (( Y <-----------------------+ )) | | 86 // | (( )) | | 87 // | ((===K====L====M==========================)) | | 88 // | | | | | | 89 // | | | +-----------------------------------------+ | 90 // | | +------------------------------------------------+ 91 // | | 92 // | | 93 // +----+ +-+ 94 // | | 95 // Merge 96 // | 97 // exit 98 99 // Note that the boxes ((===)) above are not explicitly represented in the 100 // graph, but are instead computed by the {LoopFinder}. 101 102 namespace v8 { 103 namespace internal { 104 namespace compiler { 105 106 struct Peeling { 107 // Maps a node to its index in the {pairs} vector. 108 NodeMarker<size_t> node_map; 109 // The vector which contains the mapped nodes. 110 NodeVector* pairs; 111 112 Peeling(Graph* graph, size_t max, NodeVector* p) 113 : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {} 114 115 Node* map(Node* node) { 116 if (node_map.Get(node) == 0) return node; 117 return pairs->at(node_map.Get(node)); 118 } 119 120 void Insert(Node* original, Node* copy) { 121 node_map.Set(original, 1 + pairs->size()); 122 pairs->push_back(original); 123 pairs->push_back(copy); 124 } 125 126 void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead, NodeRange nodes, 127 SourcePositionTable* source_positions, 128 NodeOriginTable* node_origins) { 129 NodeVector inputs(tmp_zone_); 130 // Copy all the nodes first. 131 for (Node* node : nodes) { 132 SourcePositionTable::Scope position( 133 source_positions, source_positions->GetSourcePosition(node)); 134 NodeOriginTable::Scope origin_scope(node_origins, "copy nodes", node); 135 inputs.clear(); 136 for (Node* input : node->inputs()) { 137 inputs.push_back(map(input)); 138 } 139 Node* copy = graph->NewNode(node->op(), node->InputCount(), &inputs[0]); 140 if (NodeProperties::IsTyped(node)) { 141 NodeProperties::SetType(copy, NodeProperties::GetType(node)); 142 } 143 Insert(node, copy); 144 } 145 146 // Fix remaining inputs of the copies. 147 for (Node* original : nodes) { 148 Node* copy = pairs->at(node_map.Get(original)); 149 for (int i = 0; i < copy->InputCount(); i++) { 150 copy->ReplaceInput(i, map(original->InputAt(i))); 151 } 152 } 153 } 154 155 bool Marked(Node* node) { return node_map.Get(node) > 0; } 156 }; 157 158 159 class PeeledIterationImpl : public PeeledIteration { 160 public: 161 NodeVector node_pairs_; 162 explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {} 163 }; 164 165 166 Node* PeeledIteration::map(Node* node) { 167 // TODO(turbofan): we use a simple linear search, since the peeled iteration 168 // is really only used in testing. 169 PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this); 170 for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) { 171 if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1]; 172 } 173 return node; 174 } 175 176 bool LoopPeeler::CanPeel(LoopTree::Loop* loop) { 177 // Look for returns and if projections that are outside the loop but whose 178 // control input is inside the loop. 179 Node* loop_node = loop_tree_->GetLoopControl(loop); 180 for (Node* node : loop_tree_->LoopNodes(loop)) { 181 for (Node* use : node->uses()) { 182 if (!loop_tree_->Contains(loop, use)) { 183 bool unmarked_exit; 184 switch (node->opcode()) { 185 case IrOpcode::kLoopExit: 186 unmarked_exit = (node->InputAt(1) != loop_node); 187 break; 188 case IrOpcode::kLoopExitValue: 189 case IrOpcode::kLoopExitEffect: 190 unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node); 191 break; 192 default: 193 unmarked_exit = (use->opcode() != IrOpcode::kTerminate); 194 } 195 if (unmarked_exit) { 196 if (FLAG_trace_turbo_loop) { 197 Node* loop_node = loop_tree_->GetLoopControl(loop); 198 PrintF( 199 "Cannot peel loop %i. Loop exit without explicit mark: Node %i " 200 "(%s) is inside " 201 "loop, but its use %i (%s) is outside.\n", 202 loop_node->id(), node->id(), node->op()->mnemonic(), use->id(), 203 use->op()->mnemonic()); 204 } 205 return false; 206 } 207 } 208 } 209 } 210 return true; 211 } 212 213 PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) { 214 if (!CanPeel(loop)) return nullptr; 215 216 //============================================================================ 217 // Construct the peeled iteration. 218 //============================================================================ 219 PeeledIterationImpl* iter = new (tmp_zone_) 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 // Replace the entry to the loop with the output of the peeled iteration. 236 //============================================================================ 237 Node* loop_node = loop_tree_->GetLoopControl(loop); 238 Node* new_entry; 239 int backedges = loop_node->InputCount() - 1; 240 if (backedges > 1) { 241 // Multiple backedges from original loop, therefore multiple output edges 242 // from the peeled iteration. 243 NodeVector inputs(tmp_zone_); 244 for (int i = 1; i < loop_node->InputCount(); i++) { 245 inputs.push_back(peeling.map(loop_node->InputAt(i))); 246 } 247 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 if (node->opcode() == IrOpcode::kLoop) continue; // already done. 253 inputs.clear(); 254 for (int i = 0; i < backedges; i++) { 255 inputs.push_back(peeling.map(node->InputAt(1 + i))); 256 } 257 for (Node* input : inputs) { 258 if (input != inputs[0]) { // Non-redundant phi. 259 inputs.push_back(merge); 260 const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges); 261 Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]); 262 node->ReplaceInput(0, phi); 263 break; 264 } 265 } 266 } 267 new_entry = merge; 268 } else { 269 // Only one backedge, simply replace the input to loop with output of 270 // peeling. 271 for (Node* node : loop_tree_->HeaderNodes(loop)) { 272 node->ReplaceInput(0, peeling.map(node->InputAt(1))); 273 } 274 new_entry = peeling.map(loop_node->InputAt(1)); 275 } 276 loop_node->ReplaceInput(0, new_entry); 277 278 //============================================================================ 279 // Change the exit and exit markers to merge/phi/effect-phi. 280 //============================================================================ 281 for (Node* exit : loop_tree_->ExitNodes(loop)) { 282 switch (exit->opcode()) { 283 case IrOpcode::kLoopExit: 284 // Change the loop exit node to a merge node. 285 exit->ReplaceInput(1, peeling.map(exit->InputAt(0))); 286 NodeProperties::ChangeOp(exit, common_->Merge(2)); 287 break; 288 case IrOpcode::kLoopExitValue: 289 // Change exit marker to phi. 290 exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0))); 291 NodeProperties::ChangeOp( 292 exit, common_->Phi(MachineRepresentation::kTagged, 2)); 293 break; 294 case IrOpcode::kLoopExitEffect: 295 // Change effect exit marker to effect phi. 296 exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0))); 297 NodeProperties::ChangeOp(exit, common_->EffectPhi(2)); 298 break; 299 default: 300 break; 301 } 302 } 303 return iter; 304 } 305 306 void LoopPeeler::PeelInnerLoops(LoopTree::Loop* loop) { 307 // If the loop has nested loops, peel inside those. 308 if (!loop->children().empty()) { 309 for (LoopTree::Loop* inner_loop : loop->children()) { 310 PeelInnerLoops(inner_loop); 311 } 312 return; 313 } 314 // Only peel small-enough loops. 315 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 namespace { 328 329 void EliminateLoopExit(Node* node) { 330 DCHECK_EQ(IrOpcode::kLoopExit, node->opcode()); 331 // The exit markers take the loop exit as input. We iterate over uses 332 // and remove all the markers from the graph. 333 for (Edge edge : node->use_edges()) { 334 if (NodeProperties::IsControlEdge(edge)) { 335 Node* marker = edge.from(); 336 if (marker->opcode() == IrOpcode::kLoopExitValue) { 337 NodeProperties::ReplaceUses(marker, marker->InputAt(0)); 338 marker->Kill(); 339 } else if (marker->opcode() == IrOpcode::kLoopExitEffect) { 340 NodeProperties::ReplaceUses(marker, nullptr, 341 NodeProperties::GetEffectInput(marker)); 342 marker->Kill(); 343 } 344 } 345 } 346 NodeProperties::ReplaceUses(node, nullptr, nullptr, 347 NodeProperties::GetControlInput(node, 0)); 348 node->Kill(); 349 } 350 351 } // namespace 352 353 void LoopPeeler::PeelInnerLoopsOfTree() { 354 for (LoopTree::Loop* loop : loop_tree_->outer_loops()) { 355 PeelInnerLoops(loop); 356 } 357 358 EliminateLoopExits(graph_, tmp_zone_); 359 } 360 361 // static 362 void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* tmp_zone) { 363 ZoneQueue<Node*> queue(tmp_zone); 364 ZoneVector<bool> visited(graph->NodeCount(), false, tmp_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