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/dead-code-elimination.h" 6 7 #include "src/compiler/common-operator.h" 8 #include "src/compiler/graph.h" 9 #include "src/compiler/js-operator.h" 10 #include "src/compiler/node-properties.h" 11 #include "src/compiler/operator-properties.h" 12 13 namespace v8 { 14 namespace internal { 15 namespace compiler { 16 17 DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph, 18 CommonOperatorBuilder* common, 19 Zone* temp_zone) 20 : AdvancedReducer(editor), 21 graph_(graph), 22 common_(common), 23 dead_(graph->NewNode(common->Dead())), 24 zone_(temp_zone) { 25 NodeProperties::SetType(dead_, Type::None()); 26 } 27 28 namespace { 29 30 // True if we can guarantee that {node} will never actually produce a value or 31 // effect. 32 bool NoReturn(Node* node) { 33 return node->opcode() == IrOpcode::kDead || 34 node->opcode() == IrOpcode::kUnreachable || 35 node->opcode() == IrOpcode::kDeadValue || 36 NodeProperties::GetTypeOrAny(node).IsNone(); 37 } 38 39 Node* FindDeadInput(Node* node) { 40 for (Node* input : node->inputs()) { 41 if (NoReturn(input)) return input; 42 } 43 return nullptr; 44 } 45 46 } // namespace 47 48 Reduction DeadCodeElimination::Reduce(Node* node) { 49 DisallowHeapAccess no_heap_access; 50 switch (node->opcode()) { 51 case IrOpcode::kEnd: 52 return ReduceEnd(node); 53 case IrOpcode::kLoop: 54 case IrOpcode::kMerge: 55 return ReduceLoopOrMerge(node); 56 case IrOpcode::kLoopExit: 57 return ReduceLoopExit(node); 58 case IrOpcode::kUnreachable: 59 case IrOpcode::kIfException: 60 return ReduceUnreachableOrIfException(node); 61 case IrOpcode::kPhi: 62 return ReducePhi(node); 63 case IrOpcode::kEffectPhi: 64 return PropagateDeadControl(node); 65 case IrOpcode::kDeoptimize: 66 case IrOpcode::kReturn: 67 case IrOpcode::kTerminate: 68 return ReduceDeoptimizeOrReturnOrTerminate(node); 69 case IrOpcode::kThrow: 70 return PropagateDeadControl(node); 71 case IrOpcode::kBranch: 72 case IrOpcode::kSwitch: 73 return ReduceBranchOrSwitch(node); 74 default: 75 return ReduceNode(node); 76 } 77 UNREACHABLE(); 78 } 79 80 Reduction DeadCodeElimination::PropagateDeadControl(Node* node) { 81 DCHECK_EQ(1, node->op()->ControlInputCount()); 82 Node* control = NodeProperties::GetControlInput(node); 83 if (control->opcode() == IrOpcode::kDead) return Replace(control); 84 return NoChange(); 85 } 86 87 Reduction DeadCodeElimination::ReduceEnd(Node* node) { 88 DCHECK_EQ(IrOpcode::kEnd, node->opcode()); 89 Node::Inputs inputs = node->inputs(); 90 DCHECK_LE(1, inputs.count()); 91 int live_input_count = 0; 92 for (int i = 0; i < inputs.count(); ++i) { 93 Node* const input = inputs[i]; 94 // Skip dead inputs. 95 if (input->opcode() == IrOpcode::kDead) continue; 96 // Compact live inputs. 97 if (i != live_input_count) node->ReplaceInput(live_input_count, input); 98 ++live_input_count; 99 } 100 if (live_input_count == 0) { 101 return Replace(dead()); 102 } else if (live_input_count < inputs.count()) { 103 node->TrimInputCount(live_input_count); 104 NodeProperties::ChangeOp(node, common()->End(live_input_count)); 105 return Changed(node); 106 } 107 DCHECK_EQ(inputs.count(), live_input_count); 108 return NoChange(); 109 } 110 111 112 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) { 113 DCHECK(IrOpcode::IsMergeOpcode(node->opcode())); 114 Node::Inputs inputs = node->inputs(); 115 DCHECK_LE(1, inputs.count()); 116 // Count the number of live inputs to {node} and compact them on the fly, also 117 // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the 118 // same time. We consider {Loop}s dead even if only the first control input 119 // is dead. 120 int live_input_count = 0; 121 if (node->opcode() != IrOpcode::kLoop || 122 node->InputAt(0)->opcode() != IrOpcode::kDead) { 123 for (int i = 0; i < inputs.count(); ++i) { 124 Node* const input = inputs[i]; 125 // Skip dead inputs. 126 if (input->opcode() == IrOpcode::kDead) continue; 127 // Compact live inputs. 128 if (live_input_count != i) { 129 node->ReplaceInput(live_input_count, input); 130 for (Node* const use : node->uses()) { 131 if (NodeProperties::IsPhi(use)) { 132 DCHECK_EQ(inputs.count() + 1, use->InputCount()); 133 use->ReplaceInput(live_input_count, use->InputAt(i)); 134 } 135 } 136 } 137 ++live_input_count; 138 } 139 } 140 if (live_input_count == 0) { 141 return Replace(dead()); 142 } else if (live_input_count == 1) { 143 NodeVector loop_exits(zone_); 144 // Due to compaction above, the live input is at offset 0. 145 for (Node* const use : node->uses()) { 146 if (NodeProperties::IsPhi(use)) { 147 Replace(use, use->InputAt(0)); 148 } else if (use->opcode() == IrOpcode::kLoopExit && 149 use->InputAt(1) == node) { 150 // Remember the loop exits so that we can mark their loop input dead. 151 // This has to be done after the use list iteration so that we do 152 // not mutate the use list while it is being iterated. 153 loop_exits.push_back(use); 154 } else if (use->opcode() == IrOpcode::kTerminate) { 155 DCHECK_EQ(IrOpcode::kLoop, node->opcode()); 156 Replace(use, dead()); 157 } 158 } 159 for (Node* loop_exit : loop_exits) { 160 loop_exit->ReplaceInput(1, dead()); 161 Revisit(loop_exit); 162 } 163 return Replace(node->InputAt(0)); 164 } 165 DCHECK_LE(2, live_input_count); 166 DCHECK_LE(live_input_count, inputs.count()); 167 // Trim input count for the {Merge} or {Loop} node. 168 if (live_input_count < inputs.count()) { 169 // Trim input counts for all phi uses and revisit them. 170 for (Node* const use : node->uses()) { 171 if (NodeProperties::IsPhi(use)) { 172 use->ReplaceInput(live_input_count, node); 173 TrimMergeOrPhi(use, live_input_count); 174 Revisit(use); 175 } 176 } 177 TrimMergeOrPhi(node, live_input_count); 178 return Changed(node); 179 } 180 return NoChange(); 181 } 182 183 Reduction DeadCodeElimination::RemoveLoopExit(Node* node) { 184 DCHECK_EQ(IrOpcode::kLoopExit, node->opcode()); 185 for (Node* const use : node->uses()) { 186 if (use->opcode() == IrOpcode::kLoopExitValue || 187 use->opcode() == IrOpcode::kLoopExitEffect) { 188 Replace(use, use->InputAt(0)); 189 } 190 } 191 Node* control = NodeProperties::GetControlInput(node, 0); 192 Replace(node, control); 193 return Replace(control); 194 } 195 196 Reduction DeadCodeElimination::ReduceNode(Node* node) { 197 DCHECK(!IrOpcode::IsGraphTerminator(node->opcode())); 198 int const effect_input_count = node->op()->EffectInputCount(); 199 int const control_input_count = node->op()->ControlInputCount(); 200 DCHECK_LE(control_input_count, 1); 201 if (control_input_count == 1) { 202 Reduction reduction = PropagateDeadControl(node); 203 if (reduction.Changed()) return reduction; 204 } 205 if (effect_input_count == 0 && 206 (control_input_count == 0 || node->op()->ControlOutputCount() == 0)) { 207 return ReducePureNode(node); 208 } 209 if (effect_input_count > 0) { 210 return ReduceEffectNode(node); 211 } 212 return NoChange(); 213 } 214 215 Reduction DeadCodeElimination::ReducePhi(Node* node) { 216 DCHECK_EQ(IrOpcode::kPhi, node->opcode()); 217 Reduction reduction = PropagateDeadControl(node); 218 if (reduction.Changed()) return reduction; 219 MachineRepresentation rep = PhiRepresentationOf(node->op()); 220 if (rep == MachineRepresentation::kNone || 221 NodeProperties::GetTypeOrAny(node).IsNone()) { 222 return Replace(DeadValue(node, rep)); 223 } 224 int input_count = node->op()->ValueInputCount(); 225 for (int i = 0; i < input_count; ++i) { 226 Node* input = NodeProperties::GetValueInput(node, i); 227 if (input->opcode() == IrOpcode::kDeadValue && 228 DeadValueRepresentationOf(input->op()) != rep) { 229 NodeProperties::ReplaceValueInput(node, DeadValue(input, rep), i); 230 } 231 } 232 return NoChange(); 233 } 234 235 Reduction DeadCodeElimination::ReducePureNode(Node* node) { 236 DCHECK_EQ(0, node->op()->EffectInputCount()); 237 if (node->opcode() == IrOpcode::kDeadValue) return NoChange(); 238 if (Node* input = FindDeadInput(node)) { 239 return Replace(DeadValue(input)); 240 } 241 return NoChange(); 242 } 243 244 Reduction DeadCodeElimination::ReduceUnreachableOrIfException(Node* node) { 245 DCHECK(node->opcode() == IrOpcode::kUnreachable || 246 node->opcode() == IrOpcode::kIfException); 247 Reduction reduction = PropagateDeadControl(node); 248 if (reduction.Changed()) return reduction; 249 Node* effect = NodeProperties::GetEffectInput(node, 0); 250 if (effect->opcode() == IrOpcode::kDead) { 251 return Replace(effect); 252 } 253 if (effect->opcode() == IrOpcode::kUnreachable) { 254 return Replace(effect); 255 } 256 return NoChange(); 257 } 258 259 Reduction DeadCodeElimination::ReduceEffectNode(Node* node) { 260 DCHECK_EQ(1, node->op()->EffectInputCount()); 261 Node* effect = NodeProperties::GetEffectInput(node, 0); 262 if (effect->opcode() == IrOpcode::kDead) { 263 return Replace(effect); 264 } 265 if (Node* input = FindDeadInput(node)) { 266 if (effect->opcode() == IrOpcode::kUnreachable) { 267 RelaxEffectsAndControls(node); 268 return Replace(DeadValue(input)); 269 } 270 271 Node* control = node->op()->ControlInputCount() == 1 272 ? NodeProperties::GetControlInput(node, 0) 273 : graph()->start(); 274 Node* unreachable = 275 graph()->NewNode(common()->Unreachable(), effect, control); 276 NodeProperties::SetType(unreachable, Type::None()); 277 ReplaceWithValue(node, DeadValue(input), node, control); 278 return Replace(unreachable); 279 } 280 281 return NoChange(); 282 } 283 284 Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminate(Node* node) { 285 DCHECK(node->opcode() == IrOpcode::kDeoptimize || 286 node->opcode() == IrOpcode::kReturn || 287 node->opcode() == IrOpcode::kTerminate); 288 Reduction reduction = PropagateDeadControl(node); 289 if (reduction.Changed()) return reduction; 290 if (FindDeadInput(node) != nullptr) { 291 Node* effect = NodeProperties::GetEffectInput(node, 0); 292 Node* control = NodeProperties::GetControlInput(node, 0); 293 if (effect->opcode() != IrOpcode::kUnreachable) { 294 effect = graph()->NewNode(common()->Unreachable(), effect, control); 295 NodeProperties::SetType(effect, Type::None()); 296 } 297 node->TrimInputCount(2); 298 node->ReplaceInput(0, effect); 299 node->ReplaceInput(1, control); 300 NodeProperties::ChangeOp(node, common()->Throw()); 301 return Changed(node); 302 } 303 return NoChange(); 304 } 305 306 Reduction DeadCodeElimination::ReduceLoopExit(Node* node) { 307 Node* control = NodeProperties::GetControlInput(node, 0); 308 Node* loop = NodeProperties::GetControlInput(node, 1); 309 if (control->opcode() == IrOpcode::kDead || 310 loop->opcode() == IrOpcode::kDead) { 311 return RemoveLoopExit(node); 312 } 313 return NoChange(); 314 } 315 316 Reduction DeadCodeElimination::ReduceBranchOrSwitch(Node* node) { 317 DCHECK(node->opcode() == IrOpcode::kBranch || 318 node->opcode() == IrOpcode::kSwitch); 319 Reduction reduction = PropagateDeadControl(node); 320 if (reduction.Changed()) return reduction; 321 Node* condition = NodeProperties::GetValueInput(node, 0); 322 if (condition->opcode() == IrOpcode::kDeadValue) { 323 // Branches or switches on {DeadValue} must originate from unreachable code 324 // and cannot matter. Due to schedule freedom between the effect and the 325 // control chain, they might still appear in reachable code. Remove them by 326 // always choosing the first projection. 327 size_t const projection_cnt = node->op()->ControlOutputCount(); 328 Node** projections = zone_->NewArray<Node*>(projection_cnt); 329 NodeProperties::CollectControlProjections(node, projections, 330 projection_cnt); 331 Replace(projections[0], NodeProperties::GetControlInput(node)); 332 return Replace(dead()); 333 } 334 return NoChange(); 335 } 336 337 void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) { 338 const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size); 339 node->TrimInputCount(OperatorProperties::GetTotalInputCount(op)); 340 NodeProperties::ChangeOp(node, op); 341 } 342 343 Node* DeadCodeElimination::DeadValue(Node* node, MachineRepresentation rep) { 344 if (node->opcode() == IrOpcode::kDeadValue) { 345 if (rep == DeadValueRepresentationOf(node->op())) return node; 346 node = NodeProperties::GetValueInput(node, 0); 347 } 348 Node* dead_value = graph()->NewNode(common()->DeadValue(rep), node); 349 NodeProperties::SetType(dead_value, Type::None()); 350 return dead_value; 351 } 352 353 } // namespace compiler 354 } // namespace internal 355 } // namespace v8 356