| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2014 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/common-operator-reducer.h" | |
| 7 #include "src/compiler/control-reducer.h" | |
| 8 #include "src/compiler/graph.h" | |
| 9 #include "src/compiler/graph-reducer.h" | |
| 10 #include "src/compiler/js-graph.h" | |
| 11 #include "src/compiler/node-marker.h" | |
| 12 #include "src/compiler/node-matchers.h" | |
| 13 #include "src/compiler/node-properties.h" | |
| 14 #include "src/zone-containers.h" | |
| 15 | |
| 16 namespace v8 { | |
| 17 namespace internal { | |
| 18 namespace compiler { | |
| 19 | |
| 20 #define TRACE(...) \ | |
| 21 do { \ | |
| 22 if (FLAG_trace_turbo_reduction) PrintF(__VA_ARGS__); \ | |
| 23 } while (false) | |
| 24 | |
| 25 enum Decision { kFalse, kUnknown, kTrue }; | |
| 26 | |
| 27 class ControlReducerImpl final : public AdvancedReducer { | |
| 28 public: | |
| 29 Zone* zone_; | |
| 30 JSGraph* jsgraph_; | |
| 31 int max_phis_for_select_; | |
| 32 | |
| 33 ControlReducerImpl(Editor* editor, Zone* zone, JSGraph* jsgraph) | |
| 34 : AdvancedReducer(editor), | |
| 35 zone_(zone), | |
| 36 jsgraph_(jsgraph), | |
| 37 max_phis_for_select_(0) {} | |
| 38 | |
| 39 Graph* graph() { return jsgraph_->graph(); } | |
| 40 CommonOperatorBuilder* common() { return jsgraph_->common(); } | |
| 41 Node* dead() { return jsgraph_->DeadControl(); } | |
| 42 | |
| 43 //=========================================================================== | |
| 44 // Reducer implementation: perform reductions on a node. | |
| 45 //=========================================================================== | |
| 46 Reduction Reduce(Node* node) override { | |
| 47 if (node->op()->ControlInputCount() == 1 || | |
| 48 node->opcode() == IrOpcode::kLoop) { | |
| 49 // If a node has only one control input and it is dead, replace with dead. | |
| 50 Node* control = NodeProperties::GetControlInput(node); | |
| 51 if (control->opcode() == IrOpcode::kDeadControl) { | |
| 52 TRACE("ControlDead: #%d:%s\n", node->id(), node->op()->mnemonic()); | |
| 53 return Replace(control); | |
| 54 } | |
| 55 } | |
| 56 | |
| 57 Node* result = node; | |
| 58 // Reduce branches, phis, and merges. | |
| 59 switch (node->opcode()) { | |
| 60 case IrOpcode::kBranch: | |
| 61 result = ReduceBranch(node); | |
| 62 break; | |
| 63 case IrOpcode::kIfTrue: | |
| 64 result = ReduceIfProjection(node, kTrue); | |
| 65 break; | |
| 66 case IrOpcode::kIfFalse: | |
| 67 result = ReduceIfProjection(node, kFalse); | |
| 68 break; | |
| 69 case IrOpcode::kLoop: // fallthrough | |
| 70 case IrOpcode::kMerge: | |
| 71 result = ReduceMerge(node); | |
| 72 break; | |
| 73 case IrOpcode::kEnd: | |
| 74 result = ReduceEnd(node); | |
| 75 break; | |
| 76 default: | |
| 77 break; | |
| 78 } | |
| 79 | |
| 80 return result == node ? NoChange() : Replace(result); | |
| 81 } | |
| 82 | |
| 83 // Try to statically fold a condition. | |
| 84 Decision DecideCondition(Node* cond) { | |
| 85 switch (cond->opcode()) { | |
| 86 case IrOpcode::kInt32Constant: | |
| 87 return Int32Matcher(cond).Is(0) ? kFalse : kTrue; | |
| 88 case IrOpcode::kInt64Constant: | |
| 89 return Int64Matcher(cond).Is(0) ? kFalse : kTrue; | |
| 90 case IrOpcode::kHeapConstant: { | |
| 91 Handle<Object> object = | |
| 92 HeapObjectMatcher<Object>(cond).Value().handle(); | |
| 93 return object->BooleanValue() ? kTrue : kFalse; | |
| 94 } | |
| 95 default: | |
| 96 break; | |
| 97 } | |
| 98 return kUnknown; | |
| 99 } | |
| 100 | |
| 101 // Reduce branches. | |
| 102 Node* ReduceBranch(Node* branch) { | |
| 103 if (DecideCondition(branch->InputAt(0)) != kUnknown) { | |
| 104 for (Node* use : branch->uses()) Revisit(use); | |
| 105 } | |
| 106 return branch; | |
| 107 } | |
| 108 | |
| 109 // Reduce end by trimming away dead inputs. | |
| 110 Node* ReduceEnd(Node* node) { | |
| 111 // Count the number of live inputs. | |
| 112 int live = 0; | |
| 113 for (int index = 0; index < node->InputCount(); ++index) { | |
| 114 // Skip dead inputs. | |
| 115 if (node->InputAt(index)->opcode() == IrOpcode::kDeadControl) continue; | |
| 116 // Compact live inputs. | |
| 117 if (index != live) node->ReplaceInput(live, node->InputAt(index)); | |
| 118 ++live; | |
| 119 } | |
| 120 | |
| 121 TRACE("ReduceEnd: #%d:%s (%d of %d live)\n", node->id(), | |
| 122 node->op()->mnemonic(), live, node->InputCount()); | |
| 123 | |
| 124 if (live == 0) return dead(); // No remaining inputs. | |
| 125 | |
| 126 if (live < node->InputCount()) { | |
| 127 node->set_op(common()->End(live)); | |
| 128 node->TrimInputCount(live); | |
| 129 } | |
| 130 | |
| 131 return node; | |
| 132 } | |
| 133 | |
| 134 // Reduce merges by trimming away dead inputs from the merge and phis. | |
| 135 Node* ReduceMerge(Node* node) { | |
| 136 // Count the number of live inputs. | |
| 137 int live = 0; | |
| 138 int index = 0; | |
| 139 int live_index = 0; | |
| 140 for (Node* const input : node->inputs()) { | |
| 141 if (input->opcode() != IrOpcode::kDeadControl) { | |
| 142 live++; | |
| 143 live_index = index; | |
| 144 } | |
| 145 index++; | |
| 146 } | |
| 147 | |
| 148 TRACE("ReduceMerge: #%d:%s (%d of %d live)\n", node->id(), | |
| 149 node->op()->mnemonic(), live, index); | |
| 150 | |
| 151 if (live == 0) return dead(); // no remaining inputs. | |
| 152 | |
| 153 // Gather terminates, phis and effect phis to be edited. | |
| 154 NodeVector phis(zone_); | |
| 155 Node* terminate = nullptr; | |
| 156 for (Node* const use : node->uses()) { | |
| 157 if (NodeProperties::IsPhi(use)) { | |
| 158 phis.push_back(use); | |
| 159 } else if (use->opcode() == IrOpcode::kTerminate) { | |
| 160 DCHECK_NULL(terminate); | |
| 161 terminate = use; | |
| 162 } | |
| 163 } | |
| 164 | |
| 165 if (live == 1) { | |
| 166 // All phis are redundant. Replace them with their live input. | |
| 167 for (Node* const phi : phis) { | |
| 168 Replace(phi, phi->InputAt(live_index)); | |
| 169 } | |
| 170 // The terminate is not needed anymore. | |
| 171 if (terminate) Replace(terminate, dead()); | |
| 172 // The merge itself is redundant. | |
| 173 return node->InputAt(live_index); | |
| 174 } | |
| 175 | |
| 176 DCHECK_LE(2, live); | |
| 177 | |
| 178 if (live < node->InputCount()) { | |
| 179 // Edit phis in place, removing dead inputs and revisiting them. | |
| 180 for (Node* const phi : phis) { | |
| 181 TRACE(" PhiInMerge: #%d:%s (%d live)\n", phi->id(), | |
| 182 phi->op()->mnemonic(), live); | |
| 183 RemoveDeadInputs(node, phi); | |
| 184 Revisit(phi); | |
| 185 } | |
| 186 // Edit the merge in place, removing dead inputs. | |
| 187 RemoveDeadInputs(node, node); | |
| 188 } | |
| 189 | |
| 190 DCHECK_EQ(live, node->InputCount()); | |
| 191 | |
| 192 // Try to remove dead diamonds or introduce selects. | |
| 193 if (live == 2 && CheckPhisForSelect(phis)) { | |
| 194 DiamondMatcher matcher(node); | |
| 195 if (matcher.Matched() && matcher.IfProjectionsAreOwned()) { | |
| 196 // Dead diamond, i.e. neither the IfTrue nor the IfFalse nodes | |
| 197 // have uses except for the Merge. Remove the branch if there | |
| 198 // are no phis or replace phis with selects. | |
| 199 Node* control = NodeProperties::GetControlInput(matcher.Branch()); | |
| 200 if (phis.size() == 0) { | |
| 201 // No phis. Remove the branch altogether. | |
| 202 TRACE(" DeadDiamond: #%d:Branch #%d:IfTrue #%d:IfFalse\n", | |
| 203 matcher.Branch()->id(), matcher.IfTrue()->id(), | |
| 204 matcher.IfFalse()->id()); | |
| 205 return control; | |
| 206 } else { | |
| 207 // A small number of phis. Replace with selects. | |
| 208 Node* cond = matcher.Branch()->InputAt(0); | |
| 209 for (Node* phi : phis) { | |
| 210 Node* select = graph()->NewNode( | |
| 211 common()->Select(OpParameter<MachineType>(phi), | |
| 212 BranchHintOf(matcher.Branch()->op())), | |
| 213 cond, matcher.TrueInputOf(phi), matcher.FalseInputOf(phi)); | |
| 214 TRACE(" MatchSelect: #%d:Branch #%d:IfTrue #%d:IfFalse -> #%d\n", | |
| 215 matcher.Branch()->id(), matcher.IfTrue()->id(), | |
| 216 matcher.IfFalse()->id(), select->id()); | |
| 217 Replace(phi, select); | |
| 218 } | |
| 219 return control; | |
| 220 } | |
| 221 } | |
| 222 } | |
| 223 | |
| 224 return node; | |
| 225 } | |
| 226 | |
| 227 bool CheckPhisForSelect(const NodeVector& phis) { | |
| 228 if (phis.size() > static_cast<size_t>(max_phis_for_select_)) return false; | |
| 229 for (Node* phi : phis) { | |
| 230 if (phi->opcode() != IrOpcode::kPhi) return false; // no EffectPhis. | |
| 231 } | |
| 232 return true; | |
| 233 } | |
| 234 | |
| 235 // Reduce if projections if the branch has a constant input. | |
| 236 Node* ReduceIfProjection(Node* node, Decision decision) { | |
| 237 Node* branch = node->InputAt(0); | |
| 238 DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); | |
| 239 Decision result = DecideCondition(branch->InputAt(0)); | |
| 240 if (result == decision) { | |
| 241 // Fold a branch by replacing IfTrue/IfFalse with the branch control. | |
| 242 TRACE(" BranchReduce: #%d:%s => #%d:%s\n", branch->id(), | |
| 243 branch->op()->mnemonic(), node->id(), node->op()->mnemonic()); | |
| 244 return branch->InputAt(1); | |
| 245 } | |
| 246 return result == kUnknown ? node : dead(); | |
| 247 } | |
| 248 | |
| 249 // Remove inputs to {node} corresponding to the dead inputs to {merge} | |
| 250 // and compact the remaining inputs, updating the operator. | |
| 251 void RemoveDeadInputs(Node* merge, Node* node) { | |
| 252 int live = 0; | |
| 253 for (int i = 0; i < merge->InputCount(); i++) { | |
| 254 // skip dead inputs. | |
| 255 if (merge->InputAt(i)->opcode() == IrOpcode::kDeadControl) continue; | |
| 256 // compact live inputs. | |
| 257 if (live != i) node->ReplaceInput(live, node->InputAt(i)); | |
| 258 live++; | |
| 259 } | |
| 260 // compact remaining inputs. | |
| 261 int total = live; | |
| 262 for (int i = merge->InputCount(); i < node->InputCount(); i++) { | |
| 263 if (total != i) node->ReplaceInput(total, node->InputAt(i)); | |
| 264 total++; | |
| 265 } | |
| 266 DCHECK_EQ(total, live + node->InputCount() - merge->InputCount()); | |
| 267 DCHECK_NE(total, node->InputCount()); | |
| 268 node->TrimInputCount(total); | |
| 269 node->set_op(common()->ResizeMergeOrPhi(node->op(), live)); | |
| 270 } | |
| 271 }; | |
| 272 | |
| 273 | |
| 274 void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph, | |
| 275 int max_phis_for_select) { | |
| 276 GraphReducer graph_reducer(zone, jsgraph->graph()); | |
| 277 CommonOperatorReducer common(&graph_reducer, jsgraph->graph(), | |
| 278 jsgraph->common(), jsgraph->machine()); | |
| 279 ControlReducerImpl impl(&graph_reducer, zone, jsgraph); | |
| 280 impl.max_phis_for_select_ = max_phis_for_select; | |
| 281 graph_reducer.AddReducer(&impl); | |
| 282 graph_reducer.AddReducer(&common); | |
| 283 graph_reducer.ReduceGraph(); | |
| 284 } | |
| 285 | |
| 286 | |
| 287 namespace { | |
| 288 | |
| 289 class DummyEditor final : public AdvancedReducer::Editor { | |
| 290 public: | |
| 291 void Replace(Node* node, Node* replacement) final { | |
| 292 node->ReplaceUses(replacement); | |
| 293 } | |
| 294 void Revisit(Node* node) final {} | |
| 295 void ReplaceWithValue(Node* node, Node* value, Node* effect, | |
| 296 Node* control) final {} | |
| 297 }; | |
| 298 | |
| 299 } // namespace | |
| 300 | |
| 301 | |
| 302 Node* ControlReducer::ReduceMerge(JSGraph* jsgraph, Node* node, | |
| 303 int max_phis_for_select) { | |
| 304 Zone zone; | |
| 305 DummyEditor editor; | |
| 306 ControlReducerImpl impl(&editor, &zone, jsgraph); | |
| 307 impl.max_phis_for_select_ = max_phis_for_select; | |
| 308 return impl.ReduceMerge(node); | |
| 309 } | |
| 310 | |
| 311 | |
| 312 Node* ControlReducer::ReduceIfNodeForTesting(JSGraph* jsgraph, Node* node) { | |
| 313 Zone zone; | |
| 314 DummyEditor editor; | |
| 315 ControlReducerImpl impl(&editor, &zone, jsgraph); | |
| 316 switch (node->opcode()) { | |
| 317 case IrOpcode::kIfTrue: | |
| 318 return impl.ReduceIfProjection(node, kTrue); | |
| 319 case IrOpcode::kIfFalse: | |
| 320 return impl.ReduceIfProjection(node, kFalse); | |
| 321 default: | |
| 322 return node; | |
| 323 } | |
| 324 } | |
| 325 | |
| 326 } // namespace compiler | |
| 327 } // namespace internal | |
| 328 } // namespace v8 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1193833002:
[turbofan] Proper dead code elimination as regular reducer. (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master