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 if (node_checks_.Get(node)) return NoChange(); 20 switch (node->opcode()) { 21 case IrOpcode::kCheckBounds: 22 case IrOpcode::kCheckFloat64Hole: 23 case IrOpcode::kCheckHeapObject: 24 case IrOpcode::kCheckIf: 25 case IrOpcode::kCheckInternalizedString: 26 case IrOpcode::kCheckNumber: 27 case IrOpcode::kCheckReceiver: 28 case IrOpcode::kCheckSmi: 29 case IrOpcode::kCheckString: 30 case IrOpcode::kCheckTaggedHole: 31 case IrOpcode::kCheckedFloat64ToInt32: 32 case IrOpcode::kCheckedInt32Add: 33 case IrOpcode::kCheckedInt32Sub: 34 case IrOpcode::kCheckedInt32Div: 35 case IrOpcode::kCheckedInt32Mod: 36 case IrOpcode::kCheckedInt32Mul: 37 case IrOpcode::kCheckedTaggedToFloat64: 38 case IrOpcode::kCheckedTaggedSignedToInt32: 39 case IrOpcode::kCheckedTaggedToInt32: 40 case IrOpcode::kCheckedUint32ToInt32: 41 return ReduceCheckNode(node); 42 case IrOpcode::kSpeculativeNumberAdd: 43 case IrOpcode::kSpeculativeNumberSubtract: 44 // For increments and decrements by a constant, try to learn from the last 45 // bounds check. 46 return TryReuseBoundsCheckForFirstInput(node); 47 case IrOpcode::kEffectPhi: 48 return ReduceEffectPhi(node); 49 case IrOpcode::kDead: 50 break; 51 case IrOpcode::kStart: 52 return ReduceStart(node); 53 default: 54 return ReduceOtherNode(node); 55 } 56 return NoChange(); 57 } 58 59 // static 60 RedundancyElimination::EffectPathChecks* 61 RedundancyElimination::EffectPathChecks::Copy(Zone* zone, 62 EffectPathChecks const* checks) { 63 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks); 64 } 65 66 // static 67 RedundancyElimination::EffectPathChecks const* 68 RedundancyElimination::EffectPathChecks::Empty(Zone* zone) { 69 return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0); 70 } 71 72 bool RedundancyElimination::EffectPathChecks::Equals( 73 EffectPathChecks const* that) const { 74 if (this->size_ != that->size_) return false; 75 Check* this_head = this->head_; 76 Check* that_head = that->head_; 77 while (this_head != that_head) { 78 if (this_head->node != that_head->node) return false; 79 this_head = this_head->next; 80 that_head = that_head->next; 81 } 82 return true; 83 } 84 85 void RedundancyElimination::EffectPathChecks::Merge( 86 EffectPathChecks const* that) { 87 // Change the current check list to a longest common tail of this check 88 // list and the other list. 89 90 // First, we throw away the prefix of the longer list, so that 91 // we have lists of the same length. 92 Check* that_head = that->head_; 93 size_t that_size = that->size_; 94 while (that_size > size_) { 95 that_head = that_head->next; 96 that_size--; 97 } 98 while (size_ > that_size) { 99 head_ = head_->next; 100 size_--; 101 } 102 103 // Then we go through both lists in lock-step until we find 104 // the common tail. 105 while (head_ != that_head) { 106 DCHECK_LT(0u, size_); 107 DCHECK_NOT_NULL(head_); 108 size_--; 109 head_ = head_->next; 110 that_head = that_head->next; 111 } 112 } 113 114 RedundancyElimination::EffectPathChecks const* 115 RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone, 116 Node* node) const { 117 Check* head = new (zone->New(sizeof(Check))) Check(node, head_); 118 return new (zone->New(sizeof(EffectPathChecks))) 119 EffectPathChecks(head, size_ + 1); 120 } 121 122 namespace { 123 124 bool IsCompatibleCheck(Node const* a, Node const* b) { 125 if (a->op() != b->op()) { 126 if (a->opcode() == IrOpcode::kCheckInternalizedString && 127 b->opcode() == IrOpcode::kCheckString) { 128 // CheckInternalizedString(node) implies CheckString(node) 129 } else { 130 return false; 131 } 132 } 133 for (int i = a->op()->ValueInputCount(); --i >= 0;) { 134 if (a->InputAt(i) != b->InputAt(i)) return false; 135 } 136 return true; 137 } 138 139 } // namespace 140 141 Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const { 142 for (Check const* check = head_; check != nullptr; check = check->next) { 143 if (IsCompatibleCheck(check->node, node)) { 144 DCHECK(!check->node->IsDead()); 145 return check->node; 146 } 147 } 148 return nullptr; 149 } 150 151 Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor( 152 Node* node) const { 153 for (Check const* check = head_; check != nullptr; check = check->next) { 154 if (check->node->opcode() == IrOpcode::kCheckBounds && 155 check->node->InputAt(0) == node) { 156 return check->node; 157 } 158 } 159 return nullptr; 160 } 161 162 RedundancyElimination::EffectPathChecks const* 163 RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const { 164 size_t const id = node->id(); 165 if (id < info_for_node_.size()) return info_for_node_[id]; 166 return nullptr; 167 } 168 169 void RedundancyElimination::PathChecksForEffectNodes::Set( 170 Node* node, EffectPathChecks const* checks) { 171 size_t const id = node->id(); 172 if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr); 173 info_for_node_[id] = checks; 174 } 175 176 Reduction RedundancyElimination::ReduceCheckNode(Node* node) { 177 Node* const effect = NodeProperties::GetEffectInput(node); 178 EffectPathChecks const* checks = node_checks_.Get(effect); 179 // If we do not know anything about the predecessor, do not propagate just yet 180 // because we will have to recompute anyway once we compute the predecessor. 181 if (checks == nullptr) return NoChange(); 182 // See if we have another check that dominates us. 183 if (Node* check = checks->LookupCheck(node)) { 184 ReplaceWithValue(node, check); 185 return Replace(check); 186 } 187 188 // Learn from this check. 189 return UpdateChecks(node, checks->AddCheck(zone(), node)); 190 } 191 192 Reduction RedundancyElimination::TryReuseBoundsCheckForFirstInput(Node* node) { 193 DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd || 194 node->opcode() == IrOpcode::kSpeculativeNumberSubtract); 195 196 DCHECK_EQ(1, node->op()->EffectInputCount()); 197 DCHECK_EQ(1, node->op()->EffectOutputCount()); 198 199 Node* const effect = NodeProperties::GetEffectInput(node); 200 EffectPathChecks const* checks = node_checks_.Get(effect); 201 202 // If we do not know anything about the predecessor, do not propagate just yet 203 // because we will have to recompute anyway once we compute the predecessor. 204 if (checks == nullptr) return NoChange(); 205 206 Node* left = node->InputAt(0); 207 Node* right = node->InputAt(1); 208 // Only use bounds checks for increments/decrements by a constant. 209 if (right->opcode() == IrOpcode::kNumberConstant) { 210 if (Node* bounds_check = checks->LookupBoundsCheckFor(left)) { 211 // Only use the bounds checked type if it is better. 212 if (NodeProperties::GetType(bounds_check) 213 ->Is(NodeProperties::GetType(left))) { 214 node->ReplaceInput(0, bounds_check); 215 } 216 } 217 } 218 219 return UpdateChecks(node, checks); 220 } 221 222 Reduction RedundancyElimination::ReduceEffectPhi(Node* node) { 223 Node* const control = NodeProperties::GetControlInput(node); 224 if (control->opcode() == IrOpcode::kLoop) { 225 // Here we rely on having only reducible loops: 226 // The loop entry edge always dominates the header, so we can just use 227 // the information from the loop entry edge. 228 return TakeChecksFromFirstEffect(node); 229 } 230 DCHECK_EQ(IrOpcode::kMerge, control->opcode()); 231 232 // Shortcut for the case when we do not know anything about some input. 233 int const input_count = node->op()->EffectInputCount(); 234 for (int i = 0; i < input_count; ++i) { 235 Node* const effect = NodeProperties::GetEffectInput(node, i); 236 if (node_checks_.Get(effect) == nullptr) return NoChange(); 237 } 238 239 // Make a copy of the first input's checks and merge with the checks 240 // from other inputs. 241 EffectPathChecks* checks = EffectPathChecks::Copy( 242 zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0))); 243 for (int i = 1; i < input_count; ++i) { 244 Node* const input = NodeProperties::GetEffectInput(node, i); 245 checks->Merge(node_checks_.Get(input)); 246 } 247 return UpdateChecks(node, checks); 248 } 249 250 Reduction RedundancyElimination::ReduceStart(Node* node) { 251 return UpdateChecks(node, EffectPathChecks::Empty(zone())); 252 } 253 254 Reduction RedundancyElimination::ReduceOtherNode(Node* node) { 255 if (node->op()->EffectInputCount() == 1) { 256 if (node->op()->EffectOutputCount() == 1) { 257 return TakeChecksFromFirstEffect(node); 258 } else { 259 // Effect terminators should be handled specially. 260 return NoChange(); 261 } 262 } 263 DCHECK_EQ(0, node->op()->EffectInputCount()); 264 DCHECK_EQ(0, node->op()->EffectOutputCount()); 265 return NoChange(); 266 } 267 268 Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) { 269 DCHECK_EQ(1, node->op()->EffectOutputCount()); 270 Node* const effect = NodeProperties::GetEffectInput(node); 271 EffectPathChecks const* checks = node_checks_.Get(effect); 272 // If we do not know anything about the predecessor, do not propagate just yet 273 // because we will have to recompute anyway once we compute the predecessor. 274 if (checks == nullptr) return NoChange(); 275 // We just propagate the information from the effect input (ideally, 276 // we would only revisit effect uses if there is change). 277 return UpdateChecks(node, checks); 278 } 279 280 Reduction RedundancyElimination::UpdateChecks(Node* node, 281 EffectPathChecks const* checks) { 282 EffectPathChecks const* original = node_checks_.Get(node); 283 // Only signal that the {node} has Changed, if the information about {checks} 284 // has changed wrt. the {original}. 285 if (checks != original) { 286 if (original == nullptr || !checks->Equals(original)) { 287 node_checks_.Set(node, checks); 288 return Changed(node); 289 } 290 } 291 return NoChange(); 292 } 293 294 } // namespace compiler 295 } // namespace internal 296 } // namespace v8 297