| 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<HeapObject> object = HeapObjectMatcher(cond).Value().handle(); | |
| 92 return object->BooleanValue() ? kTrue : kFalse; | |
| 93 } | |
| 94 default: | |
| 95 break; | |
| 96 } | |
| 97 return kUnknown; | |
| 98 } | |
| 99 | |
| 100 // Reduce branches. | |
| 101 Node* ReduceBranch(Node* branch) { | |
| 102 if (DecideCondition(branch->InputAt(0)) != kUnknown) { | |
| 103 for (Node* use : branch->uses()) Revisit(use); | |
| 104 } | |
| 105 return branch; | |
| 106 } | |
| 107 | |
| 108 // Reduce end by trimming away dead inputs. | |
| 109 Node* ReduceEnd(Node* node) { | |
| 110 // Count the number of live inputs. | |
| 111 int live = 0; | |
| 112 for (int index = 0; index < node->InputCount(); ++index) { | |
| 113 // Skip dead inputs. | |
| 114 if (node->InputAt(index)->opcode() == IrOpcode::kDeadControl) continue; | |
| 115 // Compact live inputs. | |
| 116 if (index != live) node->ReplaceInput(live, node->InputAt(index)); | |
| 117 ++live; | |
| 118 } | |
| 119 | |
| 120 TRACE("ReduceEnd: #%d:%s (%d of %d live)\n", node->id(), | |
| 121 node->op()->mnemonic(), live, node->InputCount()); | |
| 122 | |
| 123 if (live == 0) return dead(); // No remaining inputs. | |
| 124 | |
| 125 if (live < node->InputCount()) { | |
| 126 node->set_op(common()->End(live)); | |
| 127 node->TrimInputCount(live); | |
| 128 } | |
| 129 | |
| 130 return node; | |
| 131 } | |
| 132 | |
| 133 // Reduce merges by trimming away dead inputs from the merge and phis. | |
| 134 Node* ReduceMerge(Node* node) { | |
| 135 // Count the number of live inputs. | |
| 136 int live = 0; | |
| 137 int index = 0; | |
| 138 int live_index = 0; | |
| 139 for (Node* const input : node->inputs()) { | |
| 140 if (input->opcode() != IrOpcode::kDeadControl) { | |
| 141 live++; | |
| 142 live_index = index; | |
| 143 } | |
| 144 index++; | |
| 145 } | |
| 146 | |
| 147 TRACE("ReduceMerge: #%d:%s (%d of %d live)\n", node->id(), | |
| 148 node->op()->mnemonic(), live, index); | |
| 149 | |
| 150 if (live == 0) return dead(); // no remaining inputs. | |
| 151 | |
| 152 // Gather terminates, phis and effect phis to be edited. | |
| 153 NodeVector phis(zone_); | |
| 154 Node* terminate = nullptr; | |
| 155 for (Node* const use : node->uses()) { | |
| 156 if (NodeProperties::IsPhi(use)) { | |
| 157 phis.push_back(use); | |
| 158 } else if (use->opcode() == IrOpcode::kTerminate) { | |
| 159 DCHECK_NULL(terminate); | |
| 160 terminate = use; | |
| 161 } | |
| 162 } | |
| 163 | |
| 164 if (live == 1) { | |
| 165 // All phis are redundant. Replace them with their live input. | |
| 166 for (Node* const phi : phis) { | |
| 167 Replace(phi, phi->InputAt(live_index)); | |
| 168 } | |
| 169 // The terminate is not needed anymore. | |
| 170 if (terminate) Replace(terminate, dead()); | |
| 171 // The merge itself is redundant. | |
| 172 return node->InputAt(live_index); | |
| 173 } | |
| 174 | |
| 175 DCHECK_LE(2, live); | |
| 176 | |
| 177 if (live < node->InputCount()) { | |
| 178 // Edit phis in place, removing dead inputs and revisiting them. | |
| 179 for (Node* const phi : phis) { | |
| 180 TRACE(" PhiInMerge: #%d:%s (%d live)\n", phi->id(), | |
| 181 phi->op()->mnemonic(), live); | |
| 182 RemoveDeadInputs(node, phi); | |
| 183 Revisit(phi); | |
| 184 } | |
| 185 // Edit the merge in place, removing dead inputs. | |
| 186 RemoveDeadInputs(node, node); | |
| 187 } | |
| 188 | |
| 189 DCHECK_EQ(live, node->InputCount()); | |
| 190 | |
| 191 // Try to remove dead diamonds or introduce selects. | |
| 192 if (live == 2 && CheckPhisForSelect(phis)) { | |
| 193 DiamondMatcher matcher(node); | |
| 194 if (matcher.Matched() && matcher.IfProjectionsAreOwned()) { | |
| 195 // Dead diamond, i.e. neither the IfTrue nor the IfFalse nodes | |
| 196 // have uses except for the Merge. Remove the branch if there | |
| 197 // are no phis or replace phis with selects. | |
| 198 Node* control = NodeProperties::GetControlInput(matcher.Branch()); | |
| 199 if (phis.size() == 0) { | |
| 200 // No phis. Remove the branch altogether. | |
| 201 TRACE(" DeadDiamond: #%d:Branch #%d:IfTrue #%d:IfFalse\n", | |
| 202 matcher.Branch()->id(), matcher.IfTrue()->id(), | |
| 203 matcher.IfFalse()->id()); | |
| 204 return control; | |
| 205 } else { | |
| 206 // A small number of phis. Replace with selects. | |
| 207 Node* cond = matcher.Branch()->InputAt(0); | |
| 208 for (Node* phi : phis) { | |
| 209 Node* select = graph()->NewNode( | |
| 210 common()->Select(OpParameter<MachineType>(phi), | |
| 211 BranchHintOf(matcher.Branch()->op())), | |
| 212 cond, matcher.TrueInputOf(phi), matcher.FalseInputOf(phi)); | |
| 213 TRACE(" MatchSelect: #%d:Branch #%d:IfTrue #%d:IfFalse -> #%d\n", | |
| 214 matcher.Branch()->id(), matcher.IfTrue()->id(), | |
| 215 matcher.IfFalse()->id(), select->id()); | |
| 216 Replace(phi, select); | |
| 217 } | |
| 218 return control; | |
| 219 } | |
| 220 } | |
| 221 } | |
| 222 | |
| 223 return node; | |
| 224 } | |
| 225 | |
| 226 bool CheckPhisForSelect(const NodeVector& phis) { | |
| 227 if (phis.size() > static_cast<size_t>(max_phis_for_select_)) return false; | |
| 228 for (Node* phi : phis) { | |
| 229 if (phi->opcode() != IrOpcode::kPhi) return false; // no EffectPhis. | |
| 230 } | |
| 231 return true; | |
| 232 } | |
| 233 | |
| 234 // Reduce if projections if the branch has a constant input. | |
| 235 Node* ReduceIfProjection(Node* node, Decision decision) { | |
| 236 Node* branch = node->InputAt(0); | |
| 237 DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); | |
| 238 Decision result = DecideCondition(branch->InputAt(0)); | |
| 239 if (result == decision) { | |
| 240 // Fold a branch by replacing IfTrue/IfFalse with the branch control. | |
| 241 TRACE(" BranchReduce: #%d:%s => #%d:%s\n", branch->id(), | |
| 242 branch->op()->mnemonic(), node->id(), node->op()->mnemonic()); | |
| 243 return branch->InputAt(1); | |
| 244 } | |
| 245 return result == kUnknown ? node : dead(); | |
| 246 } | |
| 247 | |
| 248 // Remove inputs to {node} corresponding to the dead inputs to {merge} | |
| 249 // and compact the remaining inputs, updating the operator. | |
| 250 void RemoveDeadInputs(Node* merge, Node* node) { | |
| 251 int live = 0; | |
| 252 for (int i = 0; i < merge->InputCount(); i++) { | |
| 253 // skip dead inputs. | |
| 254 if (merge->InputAt(i)->opcode() == IrOpcode::kDeadControl) continue; | |
| 255 // compact live inputs. | |
| 256 if (live != i) node->ReplaceInput(live, node->InputAt(i)); | |
| 257 live++; | |
| 258 } | |
| 259 // compact remaining inputs. | |
| 260 int total = live; | |
| 261 for (int i = merge->InputCount(); i < node->InputCount(); i++) { | |
| 262 if (total != i) node->ReplaceInput(total, node->InputAt(i)); | |
| 263 total++; | |
| 264 } | |
| 265 DCHECK_EQ(total, live + node->InputCount() - merge->InputCount()); | |
| 266 DCHECK_NE(total, node->InputCount()); | |
| 267 node->TrimInputCount(total); | |
| 268 node->set_op(common()->ResizeMergeOrPhi(node->op(), live)); | |
| 269 } | |
| 270 }; | |
| 271 | |
| 272 | |
| 273 void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph, | |
| 274 int max_phis_for_select) { | |
| 275 GraphReducer graph_reducer(zone, jsgraph->graph()); | |
| 276 CommonOperatorReducer common(&graph_reducer, jsgraph->graph(), | |
| 277 jsgraph->common(), jsgraph->machine()); | |
| 278 ControlReducerImpl impl(&graph_reducer, zone, jsgraph); | |
| 279 impl.max_phis_for_select_ = max_phis_for_select; | |
| 280 graph_reducer.AddReducer(&impl); | |
| 281 graph_reducer.AddReducer(&common); | |
| 282 graph_reducer.ReduceGraph(); | |
| 283 } | |
| 284 | |
| 285 | |
| 286 namespace { | |
| 287 | |
| 288 class DummyEditor final : public AdvancedReducer::Editor { | |
| 289 public: | |
| 290 void Replace(Node* node, Node* replacement) final { | |
| 291 node->ReplaceUses(replacement); | |
| 292 } | |
| 293 void Revisit(Node* node) final {} | |
| 294 void ReplaceWithValue(Node* node, Node* value, Node* effect, | |
| 295 Node* control) final {} | |
| 296 }; | |
| 297 | |
| 298 } // namespace | |
| 299 | |
| 300 | |
| 301 Node* ControlReducer::ReduceMerge(JSGraph* jsgraph, Node* node, | |
| 302 int max_phis_for_select) { | |
| 303 Zone zone; | |
| 304 DummyEditor editor; | |
| 305 ControlReducerImpl impl(&editor, &zone, jsgraph); | |
| 306 impl.max_phis_for_select_ = max_phis_for_select; | |
| 307 return impl.ReduceMerge(node); | |
| 308 } | |
| 309 | |
| 310 | |
| 311 Node* ControlReducer::ReduceIfNodeForTesting(JSGraph* jsgraph, Node* node) { | |
| 312 Zone zone; | |
| 313 DummyEditor editor; | |
| 314 ControlReducerImpl impl(&editor, &zone, jsgraph); | |
| 315 switch (node->opcode()) { | |
| 316 case IrOpcode::kIfTrue: | |
| 317 return impl.ReduceIfProjection(node, kTrue); | |
| 318 case IrOpcode::kIfFalse: | |
| 319 return impl.ReduceIfProjection(node, kFalse); | |
| 320 default: | |
| 321 return node; | |
| 322 } | |
| 323 } | |
| 324 | |
| 325 } // namespace compiler | |
| 326 } // namespace internal | |
| 327 } // namespace v8 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1197793005:
[turbofan] Remove stale control-reducer.cc file. (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master