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
14namespace v8 {
15namespace internal {
16namespace 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
73namespace {
74
75typedef uint32_t StoreOffset;
76
77struct 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
88namespace {
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.
100class 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
130namespace {
131
132class 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).
174StoreOffset ToOffset(int offset) {
175  CHECK(0 <= offset);
176  return static_cast<StoreOffset>(offset);
177}
178
179StoreOffset ToOffset(const FieldAccess& access) {
180  return ToOffset(access.offset);
181}
182
183unsigned int RepSizeOf(MachineRepresentation rep) {
184  return 1u << ElementSizeLog2Of(rep);
185}
186unsigned int RepSizeOf(FieldAccess access) {
187  return RepSizeOf(access.machine_type.representation());
188}
189
190bool AtMostTagged(FieldAccess access) {
191  return RepSizeOf(access) <= RepSizeOf(MachineRepresentation::kTagged);
192}
193
194bool AtLeastTagged(FieldAccess access) {
195  return RepSizeOf(access) >= RepSizeOf(MachineRepresentation::kTagged);
196}
197
198}  // namespace
199
200void 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
223void 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
231bool RedundantStoreFinder::HasBeenVisited(Node* node) {
232  return !unobservable_for_id(node->id()).IsUnvisited();
233}
234
235void 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
254bool 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
261UnobservablesSet 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
335bool 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.
348RedundantStoreFinder::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
358void 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
385void 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.
417UnobservablesSet 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
468UnobservablesSet UnobservablesSet::Unvisited() { return UnobservablesSet(); }
469
470UnobservablesSet::UnobservablesSet() : set_(nullptr) {}
471
472UnobservablesSet 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.
484UnobservablesSet 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
501UnobservablesSet 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
522UnobservablesSet 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.
539bool 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
548bool UnobservablesSet::operator!=(const UnobservablesSet& other) const {
549  return !(*this == other);
550}
551
552bool UnobservableStore::operator==(const UnobservableStore other) const {
553  return (id_ == other.id_) && (offset_ == other.offset_);
554}
555
556bool UnobservableStore::operator!=(const UnobservableStore other) const {
557  return !(*this == other);
558}
559
560bool 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