Line data Source code
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 123179540 : 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 5034375 : const ZoneSet<UnobservableStore>* set() const { return set_; }
112 :
113 78034783 : bool IsUnvisited() const { return set_ == nullptr; }
114 6660535 : bool IsEmpty() const { return set_ == nullptr || set_->empty(); }
115 1031336 : bool Contains(UnobservableStore obs) const {
116 2062673 : 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 3135409 : : 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 98259186 : 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 2791511 : CHECK(0 <= offset);
176 2791511 : 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 1035041 : return 1u << ElementSizeLog2Of(rep);
185 : }
186 : unsigned int RepSizeOf(FieldAccess access) {
187 : return RepSizeOf(access.machine_type.representation());
188 : }
189 :
190 51897 : bool AtMostTagged(FieldAccess access) {
191 103794 : return RepSizeOf(access) <= RepSizeOf(MachineRepresentation::kTagged);
192 : }
193 :
194 983144 : bool AtLeastTagged(FieldAccess access) {
195 1966289 : return RepSizeOf(access) >= RepSizeOf(MachineRepresentation::kTagged);
196 : }
197 :
198 : } // namespace
199 :
200 395297 : void RedundantStoreFinder::Find() {
201 395297 : Visit(jsgraph()->graph()->end());
202 :
203 19094798 : while (!revisit_.empty()) {
204 36608408 : Node* next = revisit_.top();
205 : revisit_.pop();
206 : DCHECK_LT(next->id(), in_revisit_.size());
207 18304207 : in_revisit_[next->id()] = false;
208 18304207 : 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 395301 : }
222 :
223 23824815 : void RedundantStoreFinder::MarkForRevisit(Node* node) {
224 : DCHECK_LT(node->id(), in_revisit_.size());
225 108082947 : if (!in_revisit_[node->id()]) {
226 : revisit_.push(node);
227 36608502 : in_revisit_[node->id()] = true;
228 : }
229 23824817 : }
230 :
231 66105994 : bool RedundantStoreFinder::HasBeenVisited(Node* node) {
232 : return !unobservable_for_id(node->id()).IsUnvisited();
233 : }
234 :
235 395300 : void StoreStoreElimination::Run(JSGraph* js_graph, Zone* temp_zone) {
236 : // Find superfluous nodes
237 395300 : RedundantStoreFinder finder(js_graph, temp_zone);
238 395297 : finder.Find();
239 :
240 : // Remove superfluous nodes
241 :
242 842497 : for (Node* node : finder.to_remove_const()) {
243 51897 : if (FLAG_trace_store_elimination) {
244 : PrintF("StoreStoreElimination::Run: Eliminating node #%d:%s\n",
245 0 : node->id(), node->op()->mnemonic());
246 : }
247 51897 : Node* previous_effect = NodeProperties::GetEffectInput(node);
248 : NodeProperties::ReplaceUses(node, nullptr, previous_effect, nullptr,
249 51897 : nullptr);
250 51897 : node->Kill();
251 : }
252 395299 : }
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 9942772 : UnobservablesSet RedundantStoreFinder::RecomputeSet(Node* node,
262 2735909 : UnobservablesSet uses) {
263 9942772 : switch (node->op()->opcode()) {
264 : case IrOpcode::kStoreField: {
265 1031337 : Node* stored_to = node->InputAt(0);
266 1031337 : FieldAccess access = OpParameter<FieldAccess>(node->op());
267 : StoreOffset offset = ToOffset(access);
268 :
269 1031337 : UnobservableStore observation = {stored_to->id(), offset};
270 1031337 : bool isNotObservable = uses.Contains(observation);
271 :
272 1031337 : if (isNotObservable && AtMostTagged(access)) {
273 51897 : 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 979440 : } else if (isNotObservable && !AtMostTagged(access)) {
279 0 : 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 979440 : } else if (!isNotObservable && AtLeastTagged(access)) {
287 975735 : 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 975735 : return uses.Add(observation, temp_zone());
292 3705 : } else if (!isNotObservable && !AtLeastTagged(access)) {
293 3705 : 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 0 : UNREACHABLE();
302 : }
303 : break;
304 : }
305 : case IrOpcode::kLoadField: {
306 0 : Node* loaded_from = node->InputAt(0);
307 1760174 : FieldAccess access = OpParameter<FieldAccess>(node->op());
308 : StoreOffset offset = ToOffset(access);
309 :
310 1760174 : 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 1760174 : return uses.RemoveSameOffset(offset, temp_zone());
318 : break;
319 : }
320 : default:
321 7151261 : if (CannotObserveStoreField(node)) {
322 2259174 : TRACE(" #%d:%s can observe nothing, set stays unchanged", node->id(),
323 : node->op()->mnemonic());
324 : return uses;
325 : } else {
326 4892119 : 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 7151261 : bool RedundantStoreFinder::CannotObserveStoreField(Node* node) {
336 7144344 : return node->opcode() == IrOpcode::kCheckedLoad ||
337 7105022 : node->opcode() == IrOpcode::kLoadElement ||
338 6522793 : node->opcode() == IrOpcode::kLoad ||
339 6522621 : node->opcode() == IrOpcode::kStore ||
340 5072750 : node->opcode() == IrOpcode::kEffectPhi ||
341 4906791 : node->opcode() == IrOpcode::kStoreElement ||
342 4902304 : node->opcode() == IrOpcode::kCheckedStore ||
343 12049894 : node->opcode() == IrOpcode::kUnsafePointerAdd ||
344 7151261 : node->opcode() == IrOpcode::kRetain;
345 : }
346 :
347 : // Initialize unobservable_ with js_graph->graph->NodeCount() empty sets.
348 1185900 : 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 1976504 : unobservables_visited_empty_(UnobservablesSet::VisitedEmpty(temp_zone)) {}
357 :
358 73235517 : 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 18699554 : if (!HasBeenVisited(node)) {
365 90436863 : for (int i = 0; i < node->op()->ControlInputCount(); i++) {
366 18764018 : Node* control_input = NodeProperties::GetControlInput(node, i);
367 18764054 : if (!HasBeenVisited(control_input)) {
368 13327690 : MarkForRevisit(control_input);
369 : }
370 : }
371 : }
372 :
373 18699527 : bool isEffectful = (node->op()->EffectInputCount() >= 1);
374 18699527 : if (isEffectful) {
375 9942727 : VisitEffectfulNode(node);
376 : DCHECK(HasBeenVisited(node));
377 : }
378 :
379 18699658 : if (!HasBeenVisited(node)) {
380 : // Mark as visited.
381 8444076 : unobservable_for_id(node->id()) = unobservables_visited_empty_;
382 : }
383 18699658 : }
384 :
385 57583961 : void RedundantStoreFinder::VisitEffectfulNode(Node* node) {
386 9942728 : if (HasBeenVisited(node)) {
387 1314325 : TRACE("- Revisiting: #%d:%s", node->id(), node->op()->mnemonic());
388 : }
389 9942728 : UnobservablesSet after_set = RecomputeUseIntersection(node);
390 9942738 : 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 11257101 : (stored_for_node.IsUnvisited() || stored_for_node != before_set);
396 9942773 : if (!cur_set_changed) {
397 : // We will not be able to update the part of this chain above any more.
398 : // Exit.
399 1313605 : TRACE("+ No change: stabilized. Not visiting effect inputs.");
400 : } else {
401 8629168 : unobservable_for_id(node->id()) = before_set;
402 :
403 : // Mark effect inputs for visiting.
404 57379680 : for (int i = 0; i < node->op()->EffectInputCount(); i++) {
405 10497400 : Node* input = NodeProperties::GetEffectInput(node, i);
406 10497395 : TRACE(" marking #%d:%s for revisit", input->id(),
407 : input->op()->mnemonic());
408 10497395 : MarkForRevisit(input);
409 : }
410 : }
411 9942765 : }
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 14223863 : 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 72492311 : for (Edge edge : node->use_edges()) {
426 : // Skip non-effect edges
427 31274782 : if (!NodeProperties::IsEffectEdge(edge)) {
428 : continue;
429 : }
430 :
431 13581247 : Node* use = edge.from();
432 : UnobservablesSet new_set = unobservable_for_id(use->id());
433 : // Include new_set in the intersection.
434 13581247 : if (first) {
435 : // Intersection of a one-element set is that one element
436 : first = false;
437 9300120 : cur_set = new_set;
438 : } else {
439 : // Take the intersection of cur_set and new_set.
440 4281127 : cur_set = cur_set.Intersect(new_set, temp_zone());
441 : }
442 : }
443 :
444 9942747 : 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 9300133 : if (cur_set.IsUnvisited()) {
461 2986775 : cur_set = unobservables_visited_empty_;
462 : }
463 :
464 : return cur_set;
465 : }
466 : }
467 :
468 : UnobservablesSet UnobservablesSet::Unvisited() { return UnobservablesSet(); }
469 :
470 14614959 : UnobservablesSet::UnobservablesSet() : set_(nullptr) {}
471 :
472 395298 : 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 395298 : ZoneSet<UnobservableStore>(zone);
478 395298 : 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 4281122 : UnobservablesSet UnobservablesSet::Intersect(UnobservablesSet other,
485 : Zone* zone) const {
486 4337717 : if (IsEmpty() || other.IsEmpty()) {
487 : return Unvisited();
488 : } else {
489 : ZoneSet<UnobservableStore>* intersection =
490 : new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
491 4200 : 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 4200 : std::inserter(*intersection, intersection->end()));
496 :
497 : return UnobservablesSet(intersection);
498 : }
499 : }
500 :
501 975736 : UnobservablesSet UnobservablesSet::Add(UnobservableStore obs,
502 : Zone* zone) const {
503 : bool present = (set()->find(obs) != set()->end());
504 975734 : 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 975734 : 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 1760175 : 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 1760175 : ZoneSet<UnobservableStore>(zone);
528 : // Copy all elements over that have a different offset.
529 3823826 : for (auto obs : *set()) {
530 303473 : if (obs.offset_ != offset) {
531 : new_set->insert(obs);
532 : }
533 : }
534 :
535 1760177 : return UnobservablesSet(new_set);
536 : }
537 :
538 : // Used for debugging.
539 1314328 : bool UnobservablesSet::operator==(const UnobservablesSet& other) const {
540 2628656 : if (IsUnvisited() || other.IsUnvisited()) {
541 0 : return IsEmpty() && other.IsEmpty();
542 : } else {
543 : // Both pointers guaranteed not to be nullptrs.
544 1314323 : return *set() == *other.set();
545 : }
546 : }
547 :
548 : bool UnobservablesSet::operator!=(const UnobservablesSet& other) const {
549 1314328 : return !(*this == other);
550 : }
551 :
552 : bool UnobservableStore::operator==(const UnobservableStore other) const {
553 30103 : 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 9915525 : return (id_ < other.id_) || (id_ == other.id_ && offset_ < other.offset_);
562 : }
563 :
564 : } // namespace compiler
565 : } // namespace internal
566 : } // namespace v8
|
