1 // Copyright 2016 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/redundancy-elimination.h" 6 7 #include "src/compiler/node-properties.h" 8 9 namespace v8 { 10 namespace internal { 11 namespace compiler { 12 13 RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone) 14 : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {} 15 16 RedundancyElimination::~RedundancyElimination() {} 17 18 Reduction RedundancyElimination::Reduce(Node* node) { 19 switch (node->opcode()) { 20 case IrOpcode::kCheckFloat64Hole: 21 case IrOpcode::kCheckTaggedHole: 22 case IrOpcode::kCheckTaggedPointer: 23 case IrOpcode::kCheckTaggedSigned: 24 case IrOpcode::kCheckedFloat64ToInt32: 25 case IrOpcode::kCheckedInt32Add: 26 case IrOpcode::kCheckedInt32Sub: 27 case IrOpcode::kCheckedTaggedToFloat64: 28 case IrOpcode::kCheckedTaggedToInt32: 29 case IrOpcode::kCheckedUint32ToInt32: 30 return ReduceCheckNode(node); 31 case IrOpcode::kEffectPhi: 32 return ReduceEffectPhi(node); 33 case IrOpcode::kDead: 34 break; 35 case IrOpcode::kStart: 36 return ReduceStart(node); 37 default: 38 return ReduceOtherNode(node); 39 } 40 return NoChange(); 41 } 42 43 // static 44 RedundancyElimination::EffectPathChecks* 45 RedundancyElimination::EffectPathChecks::Copy(Zone* zone, 46 EffectPathChecks const* checks) { 47 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks); 48 } 49 50 // static 51 RedundancyElimination::EffectPathChecks const* 52 RedundancyElimination::EffectPathChecks::Empty(Zone* zone) { 53 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0); 54 } 55 56 void RedundancyElimination::EffectPathChecks::Merge( 57 EffectPathChecks const* that) { 58 // Change the current check list to a longest common tail of this check 59 // list and the other list. 60 61 // First, we throw away the prefix of the longer list, so that 62 // we have lists of the same length. 63 Check* that_head = that->head_; 64 size_t that_size = that->size_; 65 while (that_size > size_) { 66 that_head = that_head->next; 67 that_size--; 68 } 69 while (size_ > that_size) { 70 head_ = head_->next; 71 size_--; 72 } 73 74 // Then we go through both lists in lock-step until we find 75 // the common tail. 76 while (head_ != that_head) { 77 DCHECK_LT(0u, size_); 78 DCHECK_NOT_NULL(head_); 79 size_--; 80 head_ = head_->next; 81 that_head = that_head->next; 82 } 83 } 84 85 RedundancyElimination::EffectPathChecks const* 86 RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone, 87 Node* node) const { 88 Check* head = new (zone->New(sizeof(Check))) Check(node, head_); 89 return new (zone->New(sizeof(EffectPathChecks))) 90 EffectPathChecks(head, size_ + 1); 91 } 92 93 namespace { 94 95 bool IsCompatibleCheck(Node const* a, Node const* b) { 96 if (a->op() != b->op()) return false; 97 for (int i = a->op()->ValueInputCount(); --i >= 0;) { 98 if (a->InputAt(i) != b->InputAt(i)) return false; 99 } 100 return true; 101 } 102 103 } // namespace 104 105 Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const { 106 for (Check const* check = head_; check != nullptr; check = check->next) { 107 if (IsCompatibleCheck(check->node, node)) { 108 DCHECK(!check->node->IsDead()); 109 return check->node; 110 } 111 } 112 return nullptr; 113 } 114 115 RedundancyElimination::EffectPathChecks const* 116 RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const { 117 size_t const id = node->id(); 118 if (id < info_for_node_.size()) return info_for_node_[id]; 119 return nullptr; 120 } 121 122 void RedundancyElimination::PathChecksForEffectNodes::Set( 123 Node* node, EffectPathChecks const* checks) { 124 size_t const id = node->id(); 125 if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr); 126 info_for_node_[id] = checks; 127 } 128 129 Reduction RedundancyElimination::ReduceCheckNode(Node* node) { 130 Node* const effect = NodeProperties::GetEffectInput(node); 131 EffectPathChecks const* checks = node_checks_.Get(effect); 132 // If we do not know anything about the predecessor, do not propagate just yet 133 // because we will have to recompute anyway once we compute the predecessor. 134 if (checks == nullptr) return NoChange(); 135 // See if we have another check that dominates us. 136 if (Node* check = checks->LookupCheck(node)) { 137 ReplaceWithValue(node, check); 138 return Replace(check); 139 } 140 // Learn from this check. 141 return UpdateChecks(node, checks->AddCheck(zone(), node)); 142 } 143 144 Reduction RedundancyElimination::ReduceEffectPhi(Node* node) { 145 Node* const control = NodeProperties::GetControlInput(node); 146 if (control->opcode() == IrOpcode::kLoop) { 147 // Here we rely on having only reducible loops: 148 // The loop entry edge always dominates the header, so we can just use 149 // the information from the loop entry edge. 150 return TakeChecksFromFirstEffect(node); 151 } 152 DCHECK_EQ(IrOpcode::kMerge, control->opcode()); 153 154 // Shortcut for the case when we do not know anything about some input. 155 int const input_count = node->op()->EffectInputCount(); 156 for (int i = 0; i < input_count; ++i) { 157 Node* const effect = NodeProperties::GetEffectInput(node, i); 158 if (node_checks_.Get(effect) == nullptr) return NoChange(); 159 } 160 161 // Make a copy of the first input's checks and merge with the checks 162 // from other inputs. 163 EffectPathChecks* checks = EffectPathChecks::Copy( 164 zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0))); 165 for (int i = 1; i < input_count; ++i) { 166 Node* const input = NodeProperties::GetEffectInput(node, i); 167 checks->Merge(node_checks_.Get(input)); 168 } 169 return UpdateChecks(node, checks); 170 } 171 172 Reduction RedundancyElimination::ReduceStart(Node* node) { 173 return UpdateChecks(node, EffectPathChecks::Empty(zone())); 174 } 175 176 Reduction RedundancyElimination::ReduceOtherNode(Node* node) { 177 if (node->op()->EffectInputCount() == 1) { 178 if (node->op()->EffectOutputCount() == 1) { 179 return TakeChecksFromFirstEffect(node); 180 } else { 181 // Effect terminators should be handled specially. 182 return NoChange(); 183 } 184 } 185 DCHECK_EQ(0, node->op()->EffectInputCount()); 186 DCHECK_EQ(0, node->op()->EffectOutputCount()); 187 return NoChange(); 188 } 189 190 Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) { 191 DCHECK_EQ(1, node->op()->EffectOutputCount()); 192 Node* const effect = NodeProperties::GetEffectInput(node); 193 EffectPathChecks const* checks = node_checks_.Get(effect); 194 // If we do not know anything about the predecessor, do not propagate just yet 195 // because we will have to recompute anyway once we compute the predecessor. 196 if (checks == nullptr) return NoChange(); 197 // We just propagate the information from the effect input (ideally, 198 // we would only revisit effect uses if there is change). 199 return UpdateChecks(node, checks); 200 } 201 202 Reduction RedundancyElimination::UpdateChecks(Node* node, 203 EffectPathChecks const* checks) { 204 EffectPathChecks const* original = node_checks_.Get(node); 205 // Only signal that the {node} has Changed, if the information about {checks} 206 // has changed wrt. the {original}. 207 if (checks != original) { 208 node_checks_.Set(node, checks); 209 return Changed(node); 210 } 211 return NoChange(); 212 } 213 214 } // namespace compiler 215 } // namespace internal 216 } // namespace v8 217