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/node-properties.h" 10 #include "src/compiler/operator-properties.h" 11 12 namespace v8 { 13 namespace internal { 14 namespace compiler { 15 16 DeadCodeElimination::DeadCodeElimination(Editor* editor, Graph* graph, 17 CommonOperatorBuilder* common) 18 : AdvancedReducer(editor), 19 graph_(graph), 20 common_(common), 21 dead_(graph->NewNode(common->Dead())) { 22 NodeProperties::SetType(dead_, Type::None()); 23 } 24 25 Reduction DeadCodeElimination::Reduce(Node* node) { 26 switch (node->opcode()) { 27 case IrOpcode::kEnd: 28 return ReduceEnd(node); 29 case IrOpcode::kLoop: 30 case IrOpcode::kMerge: 31 return ReduceLoopOrMerge(node); 32 case IrOpcode::kLoopExit: 33 return ReduceLoopExit(node); 34 default: 35 return ReduceNode(node); 36 } 37 UNREACHABLE(); 38 return NoChange(); 39 } 40 41 42 Reduction DeadCodeElimination::ReduceEnd(Node* node) { 43 DCHECK_EQ(IrOpcode::kEnd, node->opcode()); 44 Node::Inputs inputs = node->inputs(); 45 DCHECK_LE(1, inputs.count()); 46 int live_input_count = 0; 47 for (int i = 0; i < inputs.count(); ++i) { 48 Node* const input = inputs[i]; 49 // Skip dead inputs. 50 if (input->opcode() == IrOpcode::kDead) continue; 51 // Compact live inputs. 52 if (i != live_input_count) node->ReplaceInput(live_input_count, input); 53 ++live_input_count; 54 } 55 if (live_input_count == 0) { 56 return Replace(dead()); 57 } else if (live_input_count < inputs.count()) { 58 node->TrimInputCount(live_input_count); 59 NodeProperties::ChangeOp(node, common()->End(live_input_count)); 60 return Changed(node); 61 } 62 DCHECK_EQ(inputs.count(), live_input_count); 63 return NoChange(); 64 } 65 66 67 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) { 68 DCHECK(IrOpcode::IsMergeOpcode(node->opcode())); 69 Node::Inputs inputs = node->inputs(); 70 DCHECK_LE(1, inputs.count()); 71 // Count the number of live inputs to {node} and compact them on the fly, also 72 // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the 73 // same time. We consider {Loop}s dead even if only the first control input 74 // is dead. 75 int live_input_count = 0; 76 if (node->opcode() != IrOpcode::kLoop || 77 node->InputAt(0)->opcode() != IrOpcode::kDead) { 78 for (int i = 0; i < inputs.count(); ++i) { 79 Node* const input = inputs[i]; 80 // Skip dead inputs. 81 if (input->opcode() == IrOpcode::kDead) continue; 82 // Compact live inputs. 83 if (live_input_count != i) { 84 node->ReplaceInput(live_input_count, input); 85 for (Node* const use : node->uses()) { 86 if (NodeProperties::IsPhi(use)) { 87 DCHECK_EQ(inputs.count() + 1, use->InputCount()); 88 use->ReplaceInput(live_input_count, use->InputAt(i)); 89 } 90 } 91 } 92 ++live_input_count; 93 } 94 } 95 if (live_input_count == 0) { 96 return Replace(dead()); 97 } else if (live_input_count == 1) { 98 // Due to compaction above, the live input is at offset 0. 99 for (Node* const use : node->uses()) { 100 if (NodeProperties::IsPhi(use)) { 101 Replace(use, use->InputAt(0)); 102 } else if (use->opcode() == IrOpcode::kLoopExit && 103 use->InputAt(1) == node) { 104 RemoveLoopExit(use); 105 } else if (use->opcode() == IrOpcode::kTerminate) { 106 DCHECK_EQ(IrOpcode::kLoop, node->opcode()); 107 Replace(use, dead()); 108 } 109 } 110 return Replace(node->InputAt(0)); 111 } 112 DCHECK_LE(2, live_input_count); 113 DCHECK_LE(live_input_count, inputs.count()); 114 // Trim input count for the {Merge} or {Loop} node. 115 if (live_input_count < inputs.count()) { 116 // Trim input counts for all phi uses and revisit them. 117 for (Node* const use : node->uses()) { 118 if (NodeProperties::IsPhi(use)) { 119 use->ReplaceInput(live_input_count, node); 120 TrimMergeOrPhi(use, live_input_count); 121 Revisit(use); 122 } 123 } 124 TrimMergeOrPhi(node, live_input_count); 125 return Changed(node); 126 } 127 return NoChange(); 128 } 129 130 Reduction DeadCodeElimination::RemoveLoopExit(Node* node) { 131 DCHECK_EQ(IrOpcode::kLoopExit, node->opcode()); 132 for (Node* const use : node->uses()) { 133 if (use->opcode() == IrOpcode::kLoopExitValue || 134 use->opcode() == IrOpcode::kLoopExitEffect) { 135 Replace(use, use->InputAt(0)); 136 } 137 } 138 Node* control = NodeProperties::GetControlInput(node, 0); 139 Replace(node, control); 140 return Replace(control); 141 } 142 143 Reduction DeadCodeElimination::ReduceNode(Node* node) { 144 // If {node} has exactly one control input and this is {Dead}, 145 // replace {node} with {Dead}. 146 int const control_input_count = node->op()->ControlInputCount(); 147 if (control_input_count == 0) return NoChange(); 148 DCHECK_EQ(1, control_input_count); 149 Node* control = NodeProperties::GetControlInput(node); 150 if (control->opcode() == IrOpcode::kDead) return Replace(control); 151 return NoChange(); 152 } 153 154 Reduction DeadCodeElimination::ReduceLoopExit(Node* node) { 155 Node* control = NodeProperties::GetControlInput(node, 0); 156 Node* loop = NodeProperties::GetControlInput(node, 1); 157 if (control->opcode() == IrOpcode::kDead || 158 loop->opcode() == IrOpcode::kDead) { 159 return RemoveLoopExit(node); 160 } 161 return NoChange(); 162 } 163 164 void DeadCodeElimination::TrimMergeOrPhi(Node* node, int size) { 165 const Operator* const op = common()->ResizeMergeOrPhi(node->op(), size); 166 node->TrimInputCount(OperatorProperties::GetTotalInputCount(op)); 167 NodeProperties::ChangeOp(node, op); 168 } 169 170 } // namespace compiler 171 } // namespace internal 172 } // namespace v8 173
