Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame^] | 187 | Zone zone(loop_tree->zone()->allocator()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 |