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 <iterator> 6 7 #include "src/compiler/store-store-elimination.h" 8 9 #include "src/compiler/all-nodes.h" 10 #include "src/compiler/js-graph.h" 11 #include "src/compiler/node-properties.h" 12 #include "src/compiler/simplified-operator.h" 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 #define TRACE(fmt, ...) \ 19 do { \ 20 if (FLAG_trace_store_elimination) { \ 21 PrintF("RedundantStoreFinder: " fmt "\n", ##__VA_ARGS__); \ 22 } \ 23 } while (false) 24 25 // CHECK_EXTRA is like CHECK, but has two or more arguments: a boolean 26 // expression, a format string, and any number of extra arguments. The boolean 27 // expression will be evaluated at runtime. If it evaluates to false, then an 28 // error message will be shown containing the condition, as well as the extra 29 // info formatted like with printf. 30 #define CHECK_EXTRA(condition, fmt, ...) \ 31 do { \ 32 if (V8_UNLIKELY(!(condition))) { \ 33 V8_Fatal(__FILE__, __LINE__, "Check failed: %s. Extra info: " fmt, \ 34 #condition, ##__VA_ARGS__); \ 35 } \ 36 } while (0) 37 38 #ifdef DEBUG 39 #define DCHECK_EXTRA(condition, fmt, ...) \ 40 CHECK_EXTRA(condition, fmt, ##__VA_ARGS__) 41 #else 42 #define DCHECK_EXTRA(condition, fmt, ...) ((void)0) 43 #endif 44 45 // Store-store elimination. 46 // 47 // The aim of this optimization is to detect the following pattern in the 48 // effect graph: 49 // 50 // - StoreField[+24, kRepTagged](263, ...) 51 // 52 // ... lots of nodes from which the field at offset 24 of the object 53 // returned by node #263 cannot be observed ... 54 // 55 // - StoreField[+24, kRepTagged](263, ...) 56 // 57 // In such situations, the earlier StoreField cannot be observed, and can be 58 // eliminated. This optimization should work for any offset and input node, of 59 // course. 60 // 61 // The optimization also works across splits. It currently does not work for 62 // loops, because we tend to put a stack check in loops, and like deopts, 63 // stack checks can observe anything. 64 65 // Assumption: every byte of a JS object is only ever accessed through one 66 // offset. For instance, byte 15 of a given object may be accessed using a 67 // two-byte read at offset 14, or a four-byte read at offset 12, but never 68 // both in the same program. 69 // 70 // This implementation needs all dead nodes removed from the graph, and the 71 // graph should be trimmed. 72 73 namespace { 74 75 typedef uint32_t StoreOffset; 76 77 struct UnobservableStore { 78 NodeId id_; 79 StoreOffset offset_; 80 81 bool operator==(const UnobservableStore) const; 82 bool operator!=(const UnobservableStore) const; 83 bool operator<(const UnobservableStore) const; 84 }; 85 86 } // namespace 87 88 namespace { 89 90 // Instances of UnobservablesSet are immutable. They represent either a set of 91 // UnobservableStores, or the "unvisited empty set". 92 // 93 // We apply some sharing to save memory. The class UnobservablesSet is only a 94 // pointer wide, and a copy does not use any heap (or temp_zone) memory. Most 95 // changes to an UnobservablesSet might allocate in the temp_zone. 96 // 97 // The size of an instance should be the size of a pointer, plus additional 98 // space in the zone in the case of non-unvisited UnobservablesSets. Copying 99 // an UnobservablesSet allocates no memory. 100 class UnobservablesSet final { 101 public: 102 static UnobservablesSet Unvisited(); 103 static UnobservablesSet VisitedEmpty(Zone* zone); 104 UnobservablesSet(); // unvisited 105 UnobservablesSet(const UnobservablesSet& other) : set_(other.set_) {} 106 107 UnobservablesSet Intersect(UnobservablesSet other, Zone* zone) const; 108 UnobservablesSet Add(UnobservableStore obs, Zone* zone) const; 109 UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const; 110 111 const ZoneSet<UnobservableStore>* set() const { return set_; } 112 113 bool IsUnvisited() const { return set_ == nullptr; } 114 bool IsEmpty() const { return set_ == nullptr || set_->empty(); } 115 bool Contains(UnobservableStore obs) const { 116 return set_ != nullptr && (set_->find(obs) != set_->end()); 117 } 118 119 bool operator==(const UnobservablesSet&) const; 120 bool operator!=(const UnobservablesSet&) const; 121 122 private: 123 explicit UnobservablesSet(const ZoneSet<UnobservableStore>* set) 124 : set_(set) {} 125 const ZoneSet<UnobservableStore>* set_; 126 }; 127 128 } // namespace 129 130 namespace { 131 132 class RedundantStoreFinder final { 133 public: 134 RedundantStoreFinder(JSGraph* js_graph, Zone* temp_zone); 135 136 void Find(); 137 138 const ZoneSet<Node*>& to_remove_const() { return to_remove_; } 139 140 void Visit(Node* node); 141 142 private: 143 static bool IsEffectful(Node* node); 144 void VisitEffectfulNode(Node* node); 145 UnobservablesSet RecomputeUseIntersection(Node* node); 146 UnobservablesSet RecomputeSet(Node* node, UnobservablesSet uses); 147 static bool CannotObserveStoreField(Node* node); 148 149 void MarkForRevisit(Node* node); 150 bool HasBeenVisited(Node* node); 151 152 JSGraph* jsgraph() const { return jsgraph_; } 153 Zone* temp_zone() const { return temp_zone_; } 154 ZoneVector<UnobservablesSet>& unobservable() { return unobservable_; } 155 UnobservablesSet& unobservable_for_id(NodeId id) { 156 DCHECK_LT(id, unobservable().size()); 157 return unobservable()[id]; 158 } 159 ZoneSet<Node*>& to_remove() { return to_remove_; } 160 161 JSGraph* const jsgraph_; 162 Zone* const temp_zone_; 163 164 ZoneStack<Node*> revisit_; 165 ZoneVector<bool> in_revisit_; 166 // Maps node IDs to UnobservableNodeSets. 167 ZoneVector<UnobservablesSet> unobservable_; 168 ZoneSet<Node*> to_remove_; 169 const UnobservablesSet unobservables_visited_empty_; 170 }; 171 172 // To safely cast an offset from a FieldAccess, which has a potentially wider 173 // range (namely int). 174 StoreOffset ToOffset(int offset) { 175 CHECK(0 <= offset); 176 return static_cast<StoreOffset>(offset); 177 } 178 179 StoreOffset ToOffset(const FieldAccess& access) { 180 return ToOffset(access.offset); 181 } 182 183 unsigned int RepSizeOf(MachineRepresentation rep) { 184 return 1u << ElementSizeLog2Of(rep); 185 } 186 unsigned int RepSizeOf(FieldAccess access) { 187 return RepSizeOf(access.machine_type.representation()); 188 } 189 190 bool AtMostTagged(FieldAccess access) { 191 return RepSizeOf(access) <= RepSizeOf(MachineRepresentation::kTagged); 192 } 193 194 bool AtLeastTagged(FieldAccess access) { 195 return RepSizeOf(access) >= RepSizeOf(MachineRepresentation::kTagged); 196 } 197 198 } // namespace 199 200 void RedundantStoreFinder::Find() { 201 Visit(jsgraph()->graph()->end()); 202 203 while (!revisit_.empty()) { 204 Node* next = revisit_.top(); 205 revisit_.pop(); 206 DCHECK_LT(next->id(), in_revisit_.size()); 207 in_revisit_[next->id()] = false; 208 Visit(next); 209 } 210 211 #ifdef DEBUG 212 // Check that we visited all the StoreFields 213 AllNodes all(temp_zone(), jsgraph()->graph()); 214 for (Node* node : all.reachable) { 215 if (node->op()->opcode() == IrOpcode::kStoreField) { 216 DCHECK_EXTRA(HasBeenVisited(node), "#%d:%s", node->id(), 217 node->op()->mnemonic()); 218 } 219 } 220 #endif 221 } 222 223 void RedundantStoreFinder::MarkForRevisit(Node* node) { 224 DCHECK_LT(node->id(), in_revisit_.size()); 225 if (!in_revisit_[node->id()]) { 226 revisit_.push(node); 227 in_revisit_[node->id()] = true; 228 } 229 } 230 231 bool RedundantStoreFinder::HasBeenVisited(Node* node) { 232 return !unobservable_for_id(node->id()).IsUnvisited(); 233 } 234 235 void StoreStoreElimination::Run(JSGraph* js_graph, Zone* temp_zone) { 236 // Find superfluous nodes 237 RedundantStoreFinder finder(js_graph, temp_zone); 238 finder.Find(); 239 240 // Remove superfluous nodes 241 242 for (Node* node : finder.to_remove_const()) { 243 if (FLAG_trace_store_elimination) { 244 PrintF("StoreStoreElimination::Run: Eliminating node #%d:%s\n", 245 node->id(), node->op()->mnemonic()); 246 } 247 Node* previous_effect = NodeProperties::GetEffectInput(node); 248 NodeProperties::ReplaceUses(node, nullptr, previous_effect, nullptr, 249 nullptr); 250 node->Kill(); 251 } 252 } 253 254 bool RedundantStoreFinder::IsEffectful(Node* node) { 255 return (node->op()->EffectInputCount() >= 1); 256 } 257 258 // Recompute unobservables-set for a node. Will also mark superfluous nodes 259 // as to be removed. 260 261 UnobservablesSet RedundantStoreFinder::RecomputeSet(Node* node, 262 UnobservablesSet uses) { 263 switch (node->op()->opcode()) { 264 case IrOpcode::kStoreField: { 265 Node* stored_to = node->InputAt(0); 266 FieldAccess access = OpParameter<FieldAccess>(node->op()); 267 StoreOffset offset = ToOffset(access); 268 269 UnobservableStore observation = {stored_to->id(), offset}; 270 bool isNotObservable = uses.Contains(observation); 271 272 if (isNotObservable && AtMostTagged(access)) { 273 TRACE(" #%d is StoreField[+%d,%s](#%d), unobservable", node->id(), 274 offset, MachineReprToString(access.machine_type.representation()), 275 stored_to->id()); 276 to_remove().insert(node); 277 return uses; 278 } else if (isNotObservable && !AtMostTagged(access)) { 279 TRACE( 280 " #%d is StoreField[+%d,%s](#%d), repeated in future but too " 281 "big to optimize away", 282 node->id(), offset, 283 MachineReprToString(access.machine_type.representation()), 284 stored_to->id()); 285 return uses; 286 } else if (!isNotObservable && AtLeastTagged(access)) { 287 TRACE(" #%d is StoreField[+%d,%s](#%d), observable, recording in set", 288 node->id(), offset, 289 MachineReprToString(access.machine_type.representation()), 290 stored_to->id()); 291 return uses.Add(observation, temp_zone()); 292 } else if (!isNotObservable && !AtLeastTagged(access)) { 293 TRACE( 294 " #%d is StoreField[+%d,%s](#%d), observable but too small to " 295 "record", 296 node->id(), offset, 297 MachineReprToString(access.machine_type.representation()), 298 stored_to->id()); 299 return uses; 300 } else { 301 UNREACHABLE(); 302 } 303 break; 304 } 305 case IrOpcode::kLoadField: { 306 Node* loaded_from = node->InputAt(0); 307 FieldAccess access = OpParameter<FieldAccess>(node->op()); 308 StoreOffset offset = ToOffset(access); 309 310 TRACE( 311 " #%d is LoadField[+%d,%s](#%d), removing all offsets [+%d] from " 312 "set", 313 node->id(), offset, 314 MachineReprToString(access.machine_type.representation()), 315 loaded_from->id(), offset); 316 317 return uses.RemoveSameOffset(offset, temp_zone()); 318 break; 319 } 320 default: 321 if (CannotObserveStoreField(node)) { 322 TRACE(" #%d:%s can observe nothing, set stays unchanged", node->id(), 323 node->op()->mnemonic()); 324 return uses; 325 } else { 326 TRACE(" #%d:%s might observe anything, recording empty set", 327 node->id(), node->op()->mnemonic()); 328 return unobservables_visited_empty_; 329 } 330 } 331 UNREACHABLE(); 332 return UnobservablesSet::Unvisited(); 333 } 334 335 bool RedundantStoreFinder::CannotObserveStoreField(Node* node) { 336 return node->opcode() == IrOpcode::kCheckedLoad || 337 node->opcode() == IrOpcode::kLoadElement || 338 node->opcode() == IrOpcode::kLoad || 339 node->opcode() == IrOpcode::kStore || 340 node->opcode() == IrOpcode::kEffectPhi || 341 node->opcode() == IrOpcode::kStoreElement || 342 node->opcode() == IrOpcode::kCheckedStore || 343 node->opcode() == IrOpcode::kUnsafePointerAdd || 344 node->opcode() == IrOpcode::kRetain; 345 } 346 347 // Initialize unobservable_ with js_graph->graph->NodeCount() empty sets. 348 RedundantStoreFinder::RedundantStoreFinder(JSGraph* js_graph, Zone* temp_zone) 349 : jsgraph_(js_graph), 350 temp_zone_(temp_zone), 351 revisit_(temp_zone), 352 in_revisit_(js_graph->graph()->NodeCount(), temp_zone), 353 unobservable_(js_graph->graph()->NodeCount(), 354 UnobservablesSet::Unvisited(), temp_zone), 355 to_remove_(temp_zone), 356 unobservables_visited_empty_(UnobservablesSet::VisitedEmpty(temp_zone)) {} 357 358 void RedundantStoreFinder::Visit(Node* node) { 359 // All effectful nodes should be reachable from End via a sequence of 360 // control, then a sequence of effect edges. In VisitEffectfulNode we mark 361 // all effect inputs for revisiting (if they might have stale state); here 362 // we mark all control inputs at least once. 363 364 if (!HasBeenVisited(node)) { 365 for (int i = 0; i < node->op()->ControlInputCount(); i++) { 366 Node* control_input = NodeProperties::GetControlInput(node, i); 367 if (!HasBeenVisited(control_input)) { 368 MarkForRevisit(control_input); 369 } 370 } 371 } 372 373 bool isEffectful = (node->op()->EffectInputCount() >= 1); 374 if (isEffectful) { 375 VisitEffectfulNode(node); 376 DCHECK(HasBeenVisited(node)); 377 } 378 379 if (!HasBeenVisited(node)) { 380 // Mark as visited. 381 unobservable_for_id(node->id()) = unobservables_visited_empty_; 382 } 383 } 384 385 void RedundantStoreFinder::VisitEffectfulNode(Node* node) { 386 if (HasBeenVisited(node)) { 387 TRACE("- Revisiting: #%d:%s", node->id(), node->op()->mnemonic()); 388 } 389 UnobservablesSet after_set = RecomputeUseIntersection(node); 390 UnobservablesSet before_set = RecomputeSet(node, after_set); 391 DCHECK(!before_set.IsUnvisited()); 392 393 UnobservablesSet stored_for_node = unobservable_for_id(node->id()); 394 bool cur_set_changed = 395 (stored_for_node.IsUnvisited() || stored_for_node != before_set); 396 if (!cur_set_changed) { 397 // We will not be able to update the part of this chain above any more. 398 // Exit. 399 TRACE("+ No change: stabilized. Not visiting effect inputs."); 400 } else { 401 unobservable_for_id(node->id()) = before_set; 402 403 // Mark effect inputs for visiting. 404 for (int i = 0; i < node->op()->EffectInputCount(); i++) { 405 Node* input = NodeProperties::GetEffectInput(node, i); 406 TRACE(" marking #%d:%s for revisit", input->id(), 407 input->op()->mnemonic()); 408 MarkForRevisit(input); 409 } 410 } 411 } 412 413 // Compute the intersection of the UnobservablesSets of all effect uses and 414 // return it. This function only works if {node} has an effect use. 415 // 416 // The result UnobservablesSet will always be visited. 417 UnobservablesSet RedundantStoreFinder::RecomputeUseIntersection(Node* node) { 418 // {first} == true indicates that we haven't looked at any elements yet. 419 // {first} == false indicates that cur_set is the intersection of at least one 420 // thing. 421 422 bool first = true; 423 UnobservablesSet cur_set = UnobservablesSet::Unvisited(); // irrelevant 424 425 for (Edge edge : node->use_edges()) { 426 // Skip non-effect edges 427 if (!NodeProperties::IsEffectEdge(edge)) { 428 continue; 429 } 430 431 Node* use = edge.from(); 432 UnobservablesSet new_set = unobservable_for_id(use->id()); 433 // Include new_set in the intersection. 434 if (first) { 435 // Intersection of a one-element set is that one element 436 first = false; 437 cur_set = new_set; 438 } else { 439 // Take the intersection of cur_set and new_set. 440 cur_set = cur_set.Intersect(new_set, temp_zone()); 441 } 442 } 443 444 if (first) { 445 // There were no effect uses. 446 auto opcode = node->op()->opcode(); 447 // List of opcodes that may end this effect chain. The opcodes are not 448 // important to the soundness of this optimization; this serves as a 449 // general sanity check. Add opcodes to this list as it suits you. 450 // 451 // Everything is observable after these opcodes; return the empty set. 452 DCHECK_EXTRA( 453 opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate || 454 opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow, 455 "for #%d:%s", node->id(), node->op()->mnemonic()); 456 USE(opcode); // silence warning about unused variable in release mode 457 458 return unobservables_visited_empty_; 459 } else { 460 if (cur_set.IsUnvisited()) { 461 cur_set = unobservables_visited_empty_; 462 } 463 464 return cur_set; 465 } 466 } 467 468 UnobservablesSet UnobservablesSet::Unvisited() { return UnobservablesSet(); } 469 470 UnobservablesSet::UnobservablesSet() : set_(nullptr) {} 471 472 UnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) { 473 // Create a new empty UnobservablesSet. This allocates in the zone, and 474 // can probably be optimized to use a global singleton. 475 ZoneSet<UnobservableStore>* empty_set = 476 new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 477 ZoneSet<UnobservableStore>(zone); 478 return UnobservablesSet(empty_set); 479 } 480 481 // Computes the intersection of two UnobservablesSets. May return 482 // UnobservablesSet::Unvisited() instead of an empty UnobservablesSet for 483 // speed. 484 UnobservablesSet UnobservablesSet::Intersect(UnobservablesSet other, 485 Zone* zone) const { 486 if (IsEmpty() || other.IsEmpty()) { 487 return Unvisited(); 488 } else { 489 ZoneSet<UnobservableStore>* intersection = 490 new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 491 ZoneSet<UnobservableStore>(zone); 492 // Put the intersection of set() and other.set() in intersection. 493 set_intersection(set()->begin(), set()->end(), other.set()->begin(), 494 other.set()->end(), 495 std::inserter(*intersection, intersection->end())); 496 497 return UnobservablesSet(intersection); 498 } 499 } 500 501 UnobservablesSet UnobservablesSet::Add(UnobservableStore obs, 502 Zone* zone) const { 503 bool present = (set()->find(obs) != set()->end()); 504 if (present) { 505 return *this; 506 } else { 507 // Make a new empty set. 508 ZoneSet<UnobservableStore>* new_set = 509 new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 510 ZoneSet<UnobservableStore>(zone); 511 // Copy the old elements over. 512 *new_set = *set(); 513 // Add the new element. 514 bool inserted = new_set->insert(obs).second; 515 DCHECK(inserted); 516 USE(inserted); // silence warning about unused variable 517 518 return UnobservablesSet(new_set); 519 } 520 } 521 522 UnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset, 523 Zone* zone) const { 524 // Make a new empty set. 525 ZoneSet<UnobservableStore>* new_set = 526 new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 527 ZoneSet<UnobservableStore>(zone); 528 // Copy all elements over that have a different offset. 529 for (auto obs : *set()) { 530 if (obs.offset_ != offset) { 531 new_set->insert(obs); 532 } 533 } 534 535 return UnobservablesSet(new_set); 536 } 537 538 // Used for debugging. 539 bool UnobservablesSet::operator==(const UnobservablesSet& other) const { 540 if (IsUnvisited() || other.IsUnvisited()) { 541 return IsEmpty() && other.IsEmpty(); 542 } else { 543 // Both pointers guaranteed not to be nullptrs. 544 return *set() == *other.set(); 545 } 546 } 547 548 bool UnobservablesSet::operator!=(const UnobservablesSet& other) const { 549 return !(*this == other); 550 } 551 552 bool UnobservableStore::operator==(const UnobservableStore other) const { 553 return (id_ == other.id_) && (offset_ == other.offset_); 554 } 555 556 bool UnobservableStore::operator!=(const UnobservableStore other) const { 557 return !(*this == other); 558 } 559 560 bool UnobservableStore::operator<(const UnobservableStore other) const { 561 return (id_ < other.id_) || (id_ == other.id_ && offset_ < other.offset_); 562 } 563 564 } // namespace compiler 565 } // namespace internal 566 } // namespace v8 567