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/common-operator.h" 6 #include "src/compiler/graph.h" 7 #include "src/compiler/loop-peeling.h" 8 #include "src/compiler/node.h" 9 #include "src/compiler/node-marker.h" 10 #include "src/compiler/node-properties.h" 11 #include "src/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 100 namespace v8 { 101 namespace internal { 102 namespace compiler { 103 104 struct 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()) inputs.push_back(map(input)); 130 Insert(node, graph->NewNode(node->op(), node->InputCount(), &inputs[0])); 131 } 132 133 // Fix remaining inputs of the copies. 134 for (Node* original : nodes) { 135 Node* copy = pairs->at(node_map.Get(original)); 136 for (int i = 0; i < copy->InputCount(); i++) { 137 copy->ReplaceInput(i, map(original->InputAt(i))); 138 } 139 } 140 } 141 142 bool Marked(Node* node) { return node_map.Get(node) > 0; } 143 }; 144 145 146 class PeeledIterationImpl : public PeeledIteration { 147 public: 148 NodeVector node_pairs_; 149 explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {} 150 }; 151 152 153 Node* PeeledIteration::map(Node* node) { 154 // TODO(turbofan): we use a simple linear search, since the peeled iteration 155 // is really only used in testing. 156 PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this); 157 for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) { 158 if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1]; 159 } 160 return node; 161 } 162 163 164 static void FindLoopExits(LoopTree* loop_tree, LoopTree::Loop* loop, 165 NodeVector& exits, NodeVector& rets) { 166 // Look for returns and if projections that are outside the loop but whose 167 // control input is inside the loop. 168 for (Node* node : loop_tree->LoopNodes(loop)) { 169 for (Node* use : node->uses()) { 170 if (!loop_tree->Contains(loop, use)) { 171 if (IrOpcode::IsIfProjectionOpcode(use->opcode())) { 172 // This is a branch from inside the loop to outside the loop. 173 exits.push_back(use); 174 } else if (use->opcode() == IrOpcode::kReturn && 175 loop_tree->Contains(loop, 176 NodeProperties::GetControlInput(use))) { 177 // This is a return from inside the loop. 178 rets.push_back(use); 179 } 180 } 181 } 182 } 183 } 184 185 186 bool LoopPeeler::CanPeel(LoopTree* loop_tree, LoopTree::Loop* loop) { 187 Zone zone; 188 NodeVector exits(&zone); 189 NodeVector rets(&zone); 190 FindLoopExits(loop_tree, loop, exits, rets); 191 return exits.size() <= 1u; 192 } 193 194 195 PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common, 196 LoopTree* loop_tree, LoopTree::Loop* loop, 197 Zone* tmp_zone) { 198 //============================================================================ 199 // Find the loop exit region to determine if this loop can be peeled. 200 //============================================================================ 201 NodeVector exits(tmp_zone); 202 NodeVector rets(tmp_zone); 203 FindLoopExits(loop_tree, loop, exits, rets); 204 205 if (exits.size() != 1) return nullptr; // not peelable currently. 206 207 //============================================================================ 208 // Construct the peeled iteration. 209 //============================================================================ 210 PeeledIterationImpl* iter = new (tmp_zone) PeeledIterationImpl(tmp_zone); 211 size_t estimated_peeled_size = 212 5 + (loop->TotalSize() + exits.size() + rets.size()) * 2; 213 Peeling peeling(graph, tmp_zone, estimated_peeled_size, &iter->node_pairs_); 214 215 Node* dead = graph->NewNode(common->Dead()); 216 217 // Map the loop header nodes to their entry values. 218 for (Node* node : loop_tree->HeaderNodes(loop)) { 219 peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex)); 220 } 221 222 // Copy all the nodes of loop body for the peeled iteration. 223 peeling.CopyNodes(graph, tmp_zone, dead, loop_tree->BodyNodes(loop)); 224 225 //============================================================================ 226 // Replace the entry to the loop with the output of the peeled iteration. 227 //============================================================================ 228 Node* loop_node = loop_tree->GetLoopControl(loop); 229 Node* new_entry; 230 int backedges = loop_node->InputCount() - 1; 231 if (backedges > 1) { 232 // Multiple backedges from original loop, therefore multiple output edges 233 // from the peeled iteration. 234 NodeVector inputs(tmp_zone); 235 for (int i = 1; i < loop_node->InputCount(); i++) { 236 inputs.push_back(peeling.map(loop_node->InputAt(i))); 237 } 238 Node* merge = 239 graph->NewNode(common->Merge(backedges), backedges, &inputs[0]); 240 241 // Merge values from the multiple output edges of the peeled iteration. 242 for (Node* node : loop_tree->HeaderNodes(loop)) { 243 if (node->opcode() == IrOpcode::kLoop) continue; // already done. 244 inputs.clear(); 245 for (int i = 0; i < backedges; i++) { 246 inputs.push_back(peeling.map(node->InputAt(1 + i))); 247 } 248 for (Node* input : inputs) { 249 if (input != inputs[0]) { // Non-redundant phi. 250 inputs.push_back(merge); 251 const Operator* op = common->ResizeMergeOrPhi(node->op(), backedges); 252 Node* phi = graph->NewNode(op, backedges + 1, &inputs[0]); 253 node->ReplaceInput(0, phi); 254 break; 255 } 256 } 257 } 258 new_entry = merge; 259 } else { 260 // Only one backedge, simply replace the input to loop with output of 261 // peeling. 262 for (Node* node : loop_tree->HeaderNodes(loop)) { 263 node->ReplaceInput(0, peeling.map(node->InputAt(0))); 264 } 265 new_entry = peeling.map(loop_node->InputAt(1)); 266 } 267 loop_node->ReplaceInput(0, new_entry); 268 269 //============================================================================ 270 // Duplicate the loop exit region and add a merge. 271 //============================================================================ 272 273 // Currently we are limited to peeling loops with a single exit. The exit is 274 // the postdominator of the loop (ignoring returns). 275 Node* postdom = exits[0]; 276 for (Node* node : rets) exits.push_back(node); 277 for (Node* use : postdom->uses()) { 278 if (NodeProperties::IsPhi(use)) exits.push_back(use); 279 } 280 281 NodeRange exit_range(&exits[0], &exits[0] + exits.size()); 282 peeling.CopyNodes(graph, tmp_zone, dead, exit_range); 283 284 Node* merge = graph->NewNode(common->Merge(2), postdom, peeling.map(postdom)); 285 postdom->ReplaceUses(merge); 286 merge->ReplaceInput(0, postdom); // input 0 overwritten by above line. 287 288 // Find and update all the edges into either the loop or exit region. 289 for (int i = 0; i < 2; i++) { 290 NodeRange range = i == 0 ? loop_tree->LoopNodes(loop) : exit_range; 291 ZoneVector<Edge> value_edges(tmp_zone); 292 ZoneVector<Edge> effect_edges(tmp_zone); 293 294 for (Node* node : range) { 295 // Gather value and effect edges from outside the region. 296 for (Edge edge : node->use_edges()) { 297 if (!peeling.Marked(edge.from())) { 298 // Edge from outside the loop into the region. 299 if (NodeProperties::IsValueEdge(edge) || 300 NodeProperties::IsContextEdge(edge)) { 301 value_edges.push_back(edge); 302 } else if (NodeProperties::IsEffectEdge(edge)) { 303 effect_edges.push_back(edge); 304 } else { 305 // don't do anything for control edges. 306 // TODO(titzer): should update control edges to peeled? 307 } 308 } 309 } 310 311 // Update all the value and effect edges at once. 312 if (!value_edges.empty()) { 313 // TODO(titzer): machine type is wrong here. 314 Node* phi = 315 graph->NewNode(common->Phi(MachineRepresentation::kTagged, 2), node, 316 peeling.map(node), merge); 317 for (Edge edge : value_edges) edge.UpdateTo(phi); 318 value_edges.clear(); 319 } 320 if (!effect_edges.empty()) { 321 Node* effect_phi = graph->NewNode(common->EffectPhi(2), node, 322 peeling.map(node), merge); 323 for (Edge edge : effect_edges) edge.UpdateTo(effect_phi); 324 effect_edges.clear(); 325 } 326 } 327 } 328 329 return iter; 330 } 331 332 } // namespace compiler 333 } // namespace internal 334 } // namespace v8 335