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 122652128 : 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 5087765 : const ZoneSet<UnobservableStore>* set() const { return set_; }
112 :
113 77109294 : bool IsUnvisited() const { return set_ == nullptr; }
114 5372677 : bool IsEmpty() const { return set_ == nullptr || set_->empty(); }
115 1238680 : bool Contains(UnobservableStore obs) const {
116 2477360 : 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 3341756 : : 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 98687872 : 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 2945302 : CHECK_LE(0, offset);
176 2945302 : 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 1241303 : return 1u << ElementSizeLog2Of(rep);
185 : }
186 : unsigned int RepSizeOf(FieldAccess access) {
187 : return RepSizeOf(access.machine_type.representation());
188 : }
189 :
190 51586 : bool AtMostTagged(FieldAccess access) {
191 51586 : return RepSizeOf(access) <= RepSizeOf(MachineRepresentation::kTagged);
192 : }
193 :
194 1189717 : bool AtLeastTagged(FieldAccess access) {
195 1189717 : return RepSizeOf(access) >= RepSizeOf(MachineRepresentation::kTagged);
196 : }
197 :
198 : } // namespace
199 :
200 443352 : void RedundantStoreFinder::Find() {
201 443352 : Visit(jsgraph()->graph()->end());
202 :
203 18867164 : while (!revisit_.empty()) {
204 35960909 : Node* next = revisit_.top();
205 : revisit_.pop();
206 : DCHECK_LT(next->id(), in_revisit_.size());
207 17980456 : in_revisit_[next->id()] = false;
208 17980456 : 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 443360 : }
222 :
223 23914927 : void RedundantStoreFinder::MarkForRevisit(Node* node) {
224 : DCHECK_LT(node->id(), in_revisit_.size());
225 107705763 : if (!in_revisit_[node->id()]) {
226 : revisit_.push(node);
227 35960982 : in_revisit_[node->id()] = true;
228 : }
229 23914937 : }
230 :
231 65214911 : bool RedundantStoreFinder::HasBeenVisited(Node* node) {
232 : return !unobservable_for_id(node->id()).IsUnvisited();
233 : }
234 :
235 443350 : void StoreStoreElimination::Run(JSGraph* js_graph, Zone* temp_zone) {
236 : // Find superfluous nodes
237 443350 : RedundantStoreFinder finder(js_graph, temp_zone);
238 443353 : finder.Find();
239 :
240 : // Remove superfluous nodes
241 :
242 938295 : for (Node* node : finder.to_remove_const()) {
243 51586 : if (FLAG_trace_store_elimination) {
244 : PrintF("StoreStoreElimination::Run: Eliminating node #%d:%s\n",
245 0 : node->id(), node->op()->mnemonic());
246 : }
247 51586 : Node* previous_effect = NodeProperties::GetEffectInput(node);
248 : NodeProperties::ReplaceUses(node, nullptr, previous_effect, nullptr,
249 51586 : nullptr);
250 51586 : node->Kill();
251 : }
252 443357 : }
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 10619282 : UnobservablesSet RedundantStoreFinder::RecomputeSet(Node* node,
262 2891093 : UnobservablesSet uses) {
263 10619282 : switch (node->op()->opcode()) {
264 : case IrOpcode::kStoreField: {
265 1238681 : Node* stored_to = node->InputAt(0);
266 1238681 : FieldAccess access = OpParameter<FieldAccess>(node->op());
267 : StoreOffset offset = ToOffset(access);
268 :
269 1238681 : UnobservableStore observation = {stored_to->id(), offset};
270 1238681 : bool isNotObservable = uses.Contains(observation);
271 :
272 1238680 : if (isNotObservable && AtMostTagged(access)) {
273 51586 : 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 1238680 : return uses;
278 1187094 : } 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 1187094 : } else if (!isNotObservable && AtLeastTagged(access)) {
287 1184472 : 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 1184472 : return uses.Add(observation, temp_zone());
292 2623 : } else if (!isNotObservable && !AtLeastTagged(access)) {
293 2623 : 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 1706621 : FieldAccess access = OpParameter<FieldAccess>(node->op());
308 : StoreOffset offset = ToOffset(access);
309 :
310 1706621 : 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 1706621 : return uses.RemoveSameOffset(offset, temp_zone());
318 : break;
319 : }
320 : default:
321 7673980 : if (CannotObserveStoreField(node)) {
322 2272271 : TRACE(" #%d:%s can observe nothing, set stays unchanged", node->id(),
323 : node->op()->mnemonic());
324 : return uses;
325 : } else {
326 5401723 : 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 : }
333 :
334 7673982 : bool RedundantStoreFinder::CannotObserveStoreField(Node* node) {
335 7673985 : return node->opcode() == IrOpcode::kCheckedLoad ||
336 7639956 : node->opcode() == IrOpcode::kLoadElement ||
337 6727635 : node->opcode() == IrOpcode::kLoad ||
338 6727163 : node->opcode() == IrOpcode::kStore ||
339 5468416 : node->opcode() == IrOpcode::kEffectPhi ||
340 5420502 : node->opcode() == IrOpcode::kStoreElement ||
341 5420502 : node->opcode() == IrOpcode::kCheckedStore ||
342 13087898 : node->opcode() == IrOpcode::kUnsafePointerAdd ||
343 7673982 : node->opcode() == IrOpcode::kRetain;
344 : }
345 :
346 : // Initialize unobservable_ with js_graph->graph->NodeCount() empty sets.
347 1330064 : RedundantStoreFinder::RedundantStoreFinder(JSGraph* js_graph, Zone* temp_zone)
348 : : jsgraph_(js_graph),
349 : temp_zone_(temp_zone),
350 : revisit_(temp_zone),
351 : in_revisit_(js_graph->graph()->NodeCount(), temp_zone),
352 : unobservable_(js_graph->graph()->NodeCount(),
353 : UnobservablesSet::Unvisited(), temp_zone),
354 : to_remove_(temp_zone),
355 2216784 : unobservables_visited_empty_(UnobservablesSet::VisitedEmpty(temp_zone)) {}
356 :
357 71639229 : void RedundantStoreFinder::Visit(Node* node) {
358 : // All effectful nodes should be reachable from End via a sequence of
359 : // control, then a sequence of effect edges. In VisitEffectfulNode we mark
360 : // all effect inputs for revisiting (if they might have stale state); here
361 : // we mark all control inputs at least once.
362 :
363 18423834 : if (!HasBeenVisited(node)) {
364 87331051 : for (int i = 0; i < node->op()->ControlInputCount(); i++) {
365 17747917 : Node* control_input = NodeProperties::GetControlInput(node, i);
366 17747928 : if (!HasBeenVisited(control_input)) {
367 12807869 : MarkForRevisit(control_input);
368 : }
369 : }
370 : }
371 :
372 18423822 : bool isEffectful = (node->op()->EffectInputCount() >= 1);
373 18423822 : if (isEffectful) {
374 10619296 : VisitEffectfulNode(node);
375 : DCHECK(HasBeenVisited(node));
376 : }
377 :
378 18423856 : if (!HasBeenVisited(node)) {
379 : // Mark as visited.
380 7421970 : unobservable_for_id(node->id()) = unobservables_visited_empty_;
381 : }
382 18423856 : }
383 :
384 62209042 : void RedundantStoreFinder::VisitEffectfulNode(Node* node) {
385 10619293 : if (HasBeenVisited(node)) {
386 997588 : TRACE("- Revisiting: #%d:%s", node->id(), node->op()->mnemonic());
387 : }
388 10619293 : UnobservablesSet after_set = RecomputeUseIntersection(node);
389 10619294 : UnobservablesSet before_set = RecomputeSet(node, after_set);
390 : DCHECK(!before_set.IsUnvisited());
391 :
392 : UnobservablesSet stored_for_node = unobservable_for_id(node->id());
393 : bool cur_set_changed =
394 11616874 : (stored_for_node.IsUnvisited() || stored_for_node != before_set);
395 10619285 : if (!cur_set_changed) {
396 : // We will not be able to update the part of this chain above any more.
397 : // Exit.
398 997261 : TRACE("+ No change: stabilized. Not visiting effect inputs.");
399 : } else {
400 9622024 : unobservable_for_id(node->id()) = before_set;
401 :
402 : // Mark effect inputs for visiting.
403 62187432 : for (int i = 0; i < node->op()->EffectInputCount(); i++) {
404 11107112 : Node* input = NodeProperties::GetEffectInput(node, i);
405 11107120 : TRACE(" marking #%d:%s for revisit", input->id(),
406 : input->op()->mnemonic());
407 11107120 : MarkForRevisit(input);
408 : }
409 : }
410 10619293 : }
411 :
412 : // Compute the intersection of the UnobservablesSets of all effect uses and
413 : // return it. This function only works if {node} has an effect use.
414 : //
415 : // The result UnobservablesSet will always be visited.
416 13951730 : UnobservablesSet RedundantStoreFinder::RecomputeUseIntersection(Node* node) {
417 : // {first} == true indicates that we haven't looked at any elements yet.
418 : // {first} == false indicates that cur_set is the intersection of at least one
419 : // thing.
420 :
421 : bool first = true;
422 : UnobservablesSet cur_set = UnobservablesSet::Unvisited(); // irrelevant
423 :
424 79336078 : for (Edge edge : node->use_edges()) {
425 : // Skip non-effect edges
426 34358395 : if (!NodeProperties::IsEffectEdge(edge)) {
427 : continue;
428 : }
429 :
430 13231649 : Node* use = edge.from();
431 : UnobservablesSet new_set = unobservable_for_id(use->id());
432 : // Include new_set in the intersection.
433 13231649 : if (first) {
434 : // Intersection of a one-element set is that one element
435 : first = false;
436 9899205 : cur_set = new_set;
437 : } else {
438 : // Take the intersection of cur_set and new_set.
439 3332444 : cur_set = cur_set.Intersect(new_set, temp_zone());
440 : }
441 : }
442 :
443 10619288 : if (first) {
444 : // There were no effect uses.
445 : auto opcode = node->op()->opcode();
446 : // List of opcodes that may end this effect chain. The opcodes are not
447 : // important to the soundness of this optimization; this serves as a
448 : // general sanity check. Add opcodes to this list as it suits you.
449 : //
450 : // Everything is observable after these opcodes; return the empty set.
451 : DCHECK_EXTRA(
452 : opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate ||
453 : opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow,
454 : "for #%d:%s", node->id(), node->op()->mnemonic());
455 : USE(opcode); // silence warning about unused variable in release mode
456 :
457 : return unobservables_visited_empty_;
458 : } else {
459 9899205 : if (cur_set.IsUnvisited()) {
460 2436352 : cur_set = unobservables_visited_empty_;
461 : }
462 :
463 : return cur_set;
464 : }
465 : }
466 :
467 : UnobservablesSet UnobservablesSet::Unvisited() { return UnobservablesSet(); }
468 :
469 14387779 : UnobservablesSet::UnobservablesSet() : set_(nullptr) {}
470 :
471 443355 : UnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) {
472 : // Create a new empty UnobservablesSet. This allocates in the zone, and
473 : // can probably be optimized to use a global singleton.
474 : ZoneSet<UnobservableStore>* empty_set =
475 : new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
476 443355 : ZoneSet<UnobservableStore>(zone);
477 443357 : return UnobservablesSet(empty_set);
478 : }
479 :
480 : // Computes the intersection of two UnobservablesSets. May return
481 : // UnobservablesSet::Unvisited() instead of an empty UnobservablesSet for
482 : // speed.
483 3332442 : UnobservablesSet UnobservablesSet::Intersect(UnobservablesSet other,
484 : Zone* zone) const {
485 3367092 : if (IsEmpty() || other.IsEmpty()) {
486 : return Unvisited();
487 : } else {
488 : ZoneSet<UnobservableStore>* intersection =
489 : new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
490 7305 : ZoneSet<UnobservableStore>(zone);
491 : // Put the intersection of set() and other.set() in intersection.
492 : set_intersection(set()->begin(), set()->end(), other.set()->begin(),
493 : other.set()->end(),
494 7305 : std::inserter(*intersection, intersection->end()));
495 :
496 : return UnobservablesSet(intersection);
497 : }
498 : }
499 :
500 1184471 : UnobservablesSet UnobservablesSet::Add(UnobservableStore obs,
501 : Zone* zone) const {
502 : bool present = (set()->find(obs) != set()->end());
503 1184471 : if (present) {
504 : return *this;
505 : } else {
506 : // Make a new empty set.
507 : ZoneSet<UnobservableStore>* new_set =
508 : new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
509 1184471 : ZoneSet<UnobservableStore>(zone);
510 : // Copy the old elements over.
511 : *new_set = *set();
512 : // Add the new element.
513 : bool inserted = new_set->insert(obs).second;
514 : DCHECK(inserted);
515 : USE(inserted); // silence warning about unused variable
516 :
517 : return UnobservablesSet(new_set);
518 : }
519 : }
520 :
521 1706622 : UnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset,
522 : Zone* zone) const {
523 : // Make a new empty set.
524 : ZoneSet<UnobservableStore>* new_set =
525 : new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
526 1706622 : ZoneSet<UnobservableStore>(zone);
527 : // Copy all elements over that have a different offset.
528 9596794 : for (auto obs : *set()) {
529 6183547 : if (obs.offset_ != offset) {
530 : new_set->insert(obs);
531 : }
532 : }
533 :
534 1706623 : return UnobservablesSet(new_set);
535 : }
536 :
537 : // Used for debugging.
538 997589 : bool UnobservablesSet::operator==(const UnobservablesSet& other) const {
539 1995178 : if (IsUnvisited() || other.IsUnvisited()) {
540 0 : return IsEmpty() && other.IsEmpty();
541 : } else {
542 : // Both pointers guaranteed not to be nullptrs.
543 997586 : return *set() == *other.set();
544 : }
545 : }
546 :
547 : bool UnobservablesSet::operator!=(const UnobservablesSet& other) const {
548 997589 : return !(*this == other);
549 : }
550 :
551 : bool UnobservableStore::operator==(const UnobservableStore other) const {
552 23597 : return (id_ == other.id_) && (offset_ == other.offset_);
553 : }
554 :
555 : bool UnobservableStore::operator!=(const UnobservableStore other) const {
556 : return !(*this == other);
557 : }
558 :
559 : bool UnobservableStore::operator<(const UnobservableStore other) const {
560 112780562 : return (id_ < other.id_) || (id_ == other.id_ && offset_ < other.offset_);
561 : }
562 :
563 : #undef TRACE
564 : #undef CHECK_EXTRA
565 : #undef DCHECK_EXTRA
566 :
567 : } // namespace compiler
568 : } // namespace internal
569 : } // namespace v8
|
