1 // Copyright 2013 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/crankshaft/hydrogen-load-elimination.h" 6 7 #include "src/crankshaft/hydrogen-alias-analysis.h" 8 #include "src/crankshaft/hydrogen-flow-engine.h" 9 #include "src/crankshaft/hydrogen-instructions.h" 10 #include "src/objects-inl.h" 11 12 namespace v8 { 13 namespace internal { 14 15 #define GLOBAL true 16 #define TRACE(x) if (FLAG_trace_load_elimination) PrintF x 17 18 static const int kMaxTrackedFields = 16; 19 static const int kMaxTrackedObjects = 5; 20 21 // An element in the field approximation list. 22 class HFieldApproximation : public ZoneObject { 23 public: // Just a data blob. 24 HValue* object_; 25 HValue* last_value_; 26 HFieldApproximation* next_; 27 28 // Recursively copy the entire linked list of field approximations. 29 HFieldApproximation* Copy(Zone* zone) { 30 HFieldApproximation* copy = new(zone) HFieldApproximation(); 31 copy->object_ = this->object_; 32 copy->last_value_ = this->last_value_; 33 copy->next_ = this->next_ == NULL ? NULL : this->next_->Copy(zone); 34 return copy; 35 } 36 }; 37 38 39 // The main datastructure used during load/store elimination. Each in-object 40 // field is tracked separately. For each field, store a list of known field 41 // values for known objects. 42 class HLoadEliminationTable : public ZoneObject { 43 public: 44 HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing) 45 : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { } 46 47 // The main processing of instructions. 48 HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) { 49 switch (instr->opcode()) { 50 case HValue::kLoadNamedField: { 51 HLoadNamedField* l = HLoadNamedField::cast(instr); 52 TRACE((" process L%d field %d (o%d)\n", 53 instr->id(), 54 FieldOf(l->access()), 55 l->object()->ActualValue()->id())); 56 HValue* result = load(l); 57 if (result != instr && l->CanBeReplacedWith(result)) { 58 // The load can be replaced with a previous load or a value. 59 TRACE((" replace L%d -> v%d\n", instr->id(), result->id())); 60 instr->DeleteAndReplaceWith(result); 61 } 62 break; 63 } 64 case HValue::kStoreNamedField: { 65 HStoreNamedField* s = HStoreNamedField::cast(instr); 66 TRACE((" process S%d field %d (o%d) = v%d\n", 67 instr->id(), 68 FieldOf(s->access()), 69 s->object()->ActualValue()->id(), 70 s->value()->id())); 71 HValue* result = store(s); 72 if (result == NULL) { 73 // The store is redundant. Remove it. 74 TRACE((" remove S%d\n", instr->id())); 75 instr->DeleteAndReplaceWith(NULL); 76 } 77 break; 78 } 79 case HValue::kTransitionElementsKind: { 80 HTransitionElementsKind* t = HTransitionElementsKind::cast(instr); 81 HValue* object = t->object()->ActualValue(); 82 KillFieldInternal(object, FieldOf(JSArray::kElementsOffset), NULL); 83 KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL); 84 break; 85 } 86 default: { 87 if (instr->CheckChangesFlag(kInobjectFields)) { 88 TRACE((" kill-all i%d\n", instr->id())); 89 Kill(); 90 break; 91 } 92 if (instr->CheckChangesFlag(kMaps)) { 93 TRACE((" kill-maps i%d\n", instr->id())); 94 KillOffset(JSObject::kMapOffset); 95 } 96 if (instr->CheckChangesFlag(kElementsKind)) { 97 TRACE((" kill-elements-kind i%d\n", instr->id())); 98 KillOffset(JSObject::kMapOffset); 99 KillOffset(JSObject::kElementsOffset); 100 } 101 if (instr->CheckChangesFlag(kElementsPointer)) { 102 TRACE((" kill-elements i%d\n", instr->id())); 103 KillOffset(JSObject::kElementsOffset); 104 } 105 if (instr->CheckChangesFlag(kOsrEntries)) { 106 TRACE((" kill-osr i%d\n", instr->id())); 107 Kill(); 108 } 109 } 110 // Improvements possible: 111 // - learn from HCheckMaps for field 0 112 // - remove unobservable stores (write-after-write) 113 // - track cells 114 // - track globals 115 // - track roots 116 } 117 return this; 118 } 119 120 // Support for global analysis with HFlowEngine: Merge given state with 121 // the other incoming state. 122 static HLoadEliminationTable* Merge(HLoadEliminationTable* succ_state, 123 HBasicBlock* succ_block, 124 HLoadEliminationTable* pred_state, 125 HBasicBlock* pred_block, 126 Zone* zone) { 127 DCHECK(pred_state != NULL); 128 if (succ_state == NULL) { 129 return pred_state->Copy(succ_block, pred_block, zone); 130 } else { 131 return succ_state->Merge(succ_block, pred_state, pred_block, zone); 132 } 133 } 134 135 // Support for global analysis with HFlowEngine: Given state merged with all 136 // the other incoming states, prepare it for use. 137 static HLoadEliminationTable* Finish(HLoadEliminationTable* state, 138 HBasicBlock* block, 139 Zone* zone) { 140 DCHECK(state != NULL); 141 return state; 142 } 143 144 private: 145 // Copy state to successor block. 146 HLoadEliminationTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, 147 Zone* zone) { 148 HLoadEliminationTable* copy = 149 new(zone) HLoadEliminationTable(zone, aliasing_); 150 copy->EnsureFields(fields_.length()); 151 for (int i = 0; i < fields_.length(); i++) { 152 copy->fields_[i] = fields_[i] == NULL ? NULL : fields_[i]->Copy(zone); 153 } 154 if (FLAG_trace_load_elimination) { 155 TRACE((" copy-to B%d\n", succ->block_id())); 156 copy->Print(); 157 } 158 return copy; 159 } 160 161 // Merge this state with the other incoming state. 162 HLoadEliminationTable* Merge(HBasicBlock* succ, HLoadEliminationTable* that, 163 HBasicBlock* that_block, Zone* zone) { 164 if (that->fields_.length() < fields_.length()) { 165 // Drop fields not in the other table. 166 fields_.Rewind(that->fields_.length()); 167 } 168 for (int i = 0; i < fields_.length(); i++) { 169 // Merge the field approximations for like fields. 170 HFieldApproximation* approx = fields_[i]; 171 HFieldApproximation* prev = NULL; 172 while (approx != NULL) { 173 // TODO(titzer): Merging is O(N * M); sort? 174 HFieldApproximation* other = that->Find(approx->object_, i); 175 if (other == NULL || !Equal(approx->last_value_, other->last_value_)) { 176 // Kill an entry that doesn't agree with the other value. 177 if (prev != NULL) { 178 prev->next_ = approx->next_; 179 } else { 180 fields_[i] = approx->next_; 181 } 182 approx = approx->next_; 183 continue; 184 } 185 prev = approx; 186 approx = approx->next_; 187 } 188 } 189 if (FLAG_trace_load_elimination) { 190 TRACE((" merge-to B%d\n", succ->block_id())); 191 Print(); 192 } 193 return this; 194 } 195 196 friend class HLoadEliminationEffects; // Calls Kill() and others. 197 friend class HLoadEliminationPhase; 198 199 private: 200 // Process a load instruction, updating internal table state. If a previous 201 // load or store for this object and field exists, return the new value with 202 // which the load should be replaced. Otherwise, return {instr}. 203 HValue* load(HLoadNamedField* instr) { 204 // There must be no loads from non observable in-object properties. 205 DCHECK(!instr->access().IsInobject() || 206 instr->access().existing_inobject_property()); 207 208 int field = FieldOf(instr->access()); 209 if (field < 0) return instr; 210 211 HValue* object = instr->object()->ActualValue(); 212 HFieldApproximation* approx = FindOrCreate(object, field); 213 214 if (approx->last_value_ == NULL) { 215 // Load is not redundant. Fill out a new entry. 216 approx->last_value_ = instr; 217 return instr; 218 } else if (approx->last_value_->block()->EqualToOrDominates( 219 instr->block())) { 220 // Eliminate the load. Reuse previously stored value or load instruction. 221 return approx->last_value_; 222 } else { 223 return instr; 224 } 225 } 226 227 // Process a store instruction, updating internal table state. If a previous 228 // store to the same object and field makes this store redundant (e.g. because 229 // the stored values are the same), return NULL indicating that this store 230 // instruction is redundant. Otherwise, return {instr}. 231 HValue* store(HStoreNamedField* instr) { 232 if (instr->access().IsInobject() && 233 !instr->access().existing_inobject_property()) { 234 TRACE((" skipping non existing property initialization store\n")); 235 return instr; 236 } 237 238 int field = FieldOf(instr->access()); 239 if (field < 0) return KillIfMisaligned(instr); 240 241 HValue* object = instr->object()->ActualValue(); 242 HValue* value = instr->value(); 243 244 if (instr->has_transition()) { 245 // A transition introduces a new field and alters the map of the object. 246 // Since the field in the object is new, it cannot alias existing entries. 247 KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL); 248 } else { 249 // Kill non-equivalent may-alias entries. 250 KillFieldInternal(object, field, value); 251 } 252 HFieldApproximation* approx = FindOrCreate(object, field); 253 254 if (Equal(approx->last_value_, value)) { 255 // The store is redundant because the field already has this value. 256 return NULL; 257 } else { 258 // The store is not redundant. Update the entry. 259 approx->last_value_ = value; 260 return instr; 261 } 262 } 263 264 // Kill everything in this table. 265 void Kill() { 266 fields_.Rewind(0); 267 } 268 269 // Kill all entries matching the given offset. 270 void KillOffset(int offset) { 271 int field = FieldOf(offset); 272 if (field >= 0 && field < fields_.length()) { 273 fields_[field] = NULL; 274 } 275 } 276 277 // Kill all entries aliasing the given store. 278 void KillStore(HStoreNamedField* s) { 279 int field = FieldOf(s->access()); 280 if (field >= 0) { 281 KillFieldInternal(s->object()->ActualValue(), field, s->value()); 282 } else { 283 KillIfMisaligned(s); 284 } 285 } 286 287 // Kill multiple entries in the case of a misaligned store. 288 HValue* KillIfMisaligned(HStoreNamedField* instr) { 289 HObjectAccess access = instr->access(); 290 if (access.IsInobject()) { 291 int offset = access.offset(); 292 if ((offset % kPointerSize) != 0) { 293 // Kill the field containing the first word of the access. 294 HValue* object = instr->object()->ActualValue(); 295 int field = offset / kPointerSize; 296 KillFieldInternal(object, field, NULL); 297 298 // Kill the next field in case of overlap. 299 int size = access.representation().size(); 300 int next_field = (offset + size - 1) / kPointerSize; 301 if (next_field != field) KillFieldInternal(object, next_field, NULL); 302 } 303 } 304 return instr; 305 } 306 307 // Find an entry for the given object and field pair. 308 HFieldApproximation* Find(HValue* object, int field) { 309 // Search for a field approximation for this object. 310 HFieldApproximation* approx = fields_[field]; 311 while (approx != NULL) { 312 if (aliasing_->MustAlias(object, approx->object_)) return approx; 313 approx = approx->next_; 314 } 315 return NULL; 316 } 317 318 // Find or create an entry for the given object and field pair. 319 HFieldApproximation* FindOrCreate(HValue* object, int field) { 320 EnsureFields(field + 1); 321 322 // Search for a field approximation for this object. 323 HFieldApproximation* approx = fields_[field]; 324 int count = 0; 325 while (approx != NULL) { 326 if (aliasing_->MustAlias(object, approx->object_)) return approx; 327 count++; 328 approx = approx->next_; 329 } 330 331 if (count >= kMaxTrackedObjects) { 332 // Pull the last entry off the end and repurpose it for this object. 333 approx = ReuseLastApproximation(field); 334 } else { 335 // Allocate a new entry. 336 approx = new(zone_) HFieldApproximation(); 337 } 338 339 // Insert the entry at the head of the list. 340 approx->object_ = object; 341 approx->last_value_ = NULL; 342 approx->next_ = fields_[field]; 343 fields_[field] = approx; 344 345 return approx; 346 } 347 348 // Kill all entries for a given field that _may_ alias the given object 349 // and do _not_ have the given value. 350 void KillFieldInternal(HValue* object, int field, HValue* value) { 351 if (field >= fields_.length()) return; // Nothing to do. 352 353 HFieldApproximation* approx = fields_[field]; 354 HFieldApproximation* prev = NULL; 355 while (approx != NULL) { 356 if (aliasing_->MayAlias(object, approx->object_)) { 357 if (!Equal(approx->last_value_, value)) { 358 // Kill an aliasing entry that doesn't agree on the value. 359 if (prev != NULL) { 360 prev->next_ = approx->next_; 361 } else { 362 fields_[field] = approx->next_; 363 } 364 approx = approx->next_; 365 continue; 366 } 367 } 368 prev = approx; 369 approx = approx->next_; 370 } 371 } 372 373 bool Equal(HValue* a, HValue* b) { 374 if (a == b) return true; 375 if (a != NULL && b != NULL && a->CheckFlag(HValue::kUseGVN)) { 376 return a->Equals(b); 377 } 378 return false; 379 } 380 381 // Remove the last approximation for a field so that it can be reused. 382 // We reuse the last entry because it was the first inserted and is thus 383 // farthest away from the current instruction. 384 HFieldApproximation* ReuseLastApproximation(int field) { 385 HFieldApproximation* approx = fields_[field]; 386 DCHECK(approx != NULL); 387 388 HFieldApproximation* prev = NULL; 389 while (approx->next_ != NULL) { 390 prev = approx; 391 approx = approx->next_; 392 } 393 if (prev != NULL) prev->next_ = NULL; 394 return approx; 395 } 396 397 // Compute the field index for the given object access; -1 if not tracked. 398 int FieldOf(HObjectAccess access) { 399 return access.IsInobject() ? FieldOf(access.offset()) : -1; 400 } 401 402 // Compute the field index for the given in-object offset; -1 if not tracked. 403 int FieldOf(int offset) { 404 if (offset >= kMaxTrackedFields * kPointerSize) return -1; 405 if ((offset % kPointerSize) != 0) return -1; // Ignore misaligned accesses. 406 return offset / kPointerSize; 407 } 408 409 // Ensure internal storage for the given number of fields. 410 void EnsureFields(int num_fields) { 411 if (fields_.length() < num_fields) { 412 fields_.AddBlock(NULL, num_fields - fields_.length(), zone_); 413 } 414 } 415 416 // Print this table to stdout. 417 void Print() { 418 for (int i = 0; i < fields_.length(); i++) { 419 PrintF(" field %d: ", i); 420 for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) { 421 PrintF("[o%d =", a->object_->id()); 422 if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id()); 423 PrintF("] "); 424 } 425 PrintF("\n"); 426 } 427 } 428 429 Zone* zone_; 430 ZoneList<HFieldApproximation*> fields_; 431 HAliasAnalyzer* aliasing_; 432 }; 433 434 435 // Support for HFlowEngine: collect store effects within loops. 436 class HLoadEliminationEffects : public ZoneObject { 437 public: 438 explicit HLoadEliminationEffects(Zone* zone) 439 : zone_(zone), stores_(5, zone) { } 440 441 inline bool Disabled() { 442 return false; // Effects are _not_ disabled. 443 } 444 445 // Process a possibly side-effecting instruction. 446 void Process(HInstruction* instr, Zone* zone) { 447 if (instr->IsStoreNamedField()) { 448 stores_.Add(HStoreNamedField::cast(instr), zone_); 449 } else { 450 flags_.Add(instr->ChangesFlags()); 451 } 452 } 453 454 // Apply these effects to the given load elimination table. 455 void Apply(HLoadEliminationTable* table) { 456 // Loads must not be hoisted past the OSR entry, therefore we kill 457 // everything if we see an OSR entry. 458 if (flags_.Contains(kInobjectFields) || flags_.Contains(kOsrEntries)) { 459 table->Kill(); 460 return; 461 } 462 if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) { 463 table->KillOffset(JSObject::kMapOffset); 464 } 465 if (flags_.Contains(kElementsKind) || flags_.Contains(kElementsPointer)) { 466 table->KillOffset(JSObject::kElementsOffset); 467 } 468 469 // Kill non-agreeing fields for each store contained in these effects. 470 for (int i = 0; i < stores_.length(); i++) { 471 table->KillStore(stores_[i]); 472 } 473 } 474 475 // Union these effects with the other effects. 476 void Union(HLoadEliminationEffects* that, Zone* zone) { 477 flags_.Add(that->flags_); 478 for (int i = 0; i < that->stores_.length(); i++) { 479 stores_.Add(that->stores_[i], zone); 480 } 481 } 482 483 private: 484 Zone* zone_; 485 GVNFlagSet flags_; 486 ZoneList<HStoreNamedField*> stores_; 487 }; 488 489 490 // The main routine of the analysis phase. Use the HFlowEngine for either a 491 // local or a global analysis. 492 void HLoadEliminationPhase::Run() { 493 HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects> 494 engine(graph(), zone()); 495 HAliasAnalyzer aliasing; 496 HLoadEliminationTable* table = 497 new(zone()) HLoadEliminationTable(zone(), &aliasing); 498 499 if (GLOBAL) { 500 // Perform a global analysis. 501 engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table); 502 } else { 503 // Perform only local analysis. 504 for (int i = 0; i < graph()->blocks()->length(); i++) { 505 table->Kill(); 506 engine.AnalyzeOneBlock(graph()->blocks()->at(i), table); 507 } 508 } 509 } 510 511 } // namespace internal 512 } // namespace v8 513