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#ifndef V8_COMPILER_LOAD_ELIMINATION_H_
6#define V8_COMPILER_LOAD_ELIMINATION_H_
7
8#include "src/base/compiler-specific.h"
9#include "src/codegen/machine-type.h"
10#include "src/common/globals.h"
11#include "src/compiler/graph-reducer.h"
12#include "src/compiler/simplified-operator.h"
13#include "src/handles/maybe-handles.h"
14#include "src/zone/zone-handle-set.h"
15
16namespace v8 {
17namespace internal {
18
19// Forward declarations.
20class Factory;
21
22namespace compiler {
23
24// Forward declarations.
25class CommonOperatorBuilder;
26struct FieldAccess;
27class Graph;
28class JSGraph;
29
30class V8_EXPORT_PRIVATE LoadElimination final
31    : public NON_EXPORTED_BASE(AdvancedReducer) {
32 public:
33  LoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
34      : AdvancedReducer(editor), node_states_(zone), jsgraph_(jsgraph) {}
35  ~LoadElimination() final = default;
36  LoadElimination(const LoadElimination&) = delete;
37  LoadElimination& operator=(const LoadElimination&) = delete;
38
39  const char* reducer_name() const override { return "LoadElimination"; }
40
41  Reduction Reduce(Node* node) final;
42
43 private:
44  static const size_t kMaxTrackedElements = 8;
45
46  // Abstract state to approximate the current state of an element along the
47  // effect paths through the graph.
48  class AbstractElements final : public ZoneObject {
49   public:
50    explicit AbstractElements(Zone* zone) {
51      for (size_t i = 0; i < arraysize(elements_); ++i) {
52        elements_[i] = Element();
53      }
54    }
55    AbstractElements(Node* object, Node* index, Node* value,
56                     MachineRepresentation representation, Zone* zone)
57        : AbstractElements(zone) {
58      elements_[next_index_++] = Element(object, index, value, representation);
59    }
60
61    AbstractElements const* Extend(Node* object, Node* index, Node* value,
62                                   MachineRepresentation representation,
63                                   Zone* zone) const {
64      AbstractElements* that = zone->New<AbstractElements>(*this);
65      that->elements_[that->next_index_] =
66          Element(object, index, value, representation);
67      that->next_index_ = (that->next_index_ + 1) % arraysize(elements_);
68      return that;
69    }
70    Node* Lookup(Node* object, Node* index,
71                 MachineRepresentation representation) const;
72    AbstractElements const* Kill(Node* object, Node* index, Zone* zone) const;
73    bool Equals(AbstractElements const* that) const;
74    AbstractElements const* Merge(AbstractElements const* that,
75                                  Zone* zone) const;
76
77    void Print() const;
78
79   private:
80    struct Element {
81      Element() = default;
82      Element(Node* object, Node* index, Node* value,
83              MachineRepresentation representation)
84          : object(object),
85            index(index),
86            value(value),
87            representation(representation) {}
88
89      Node* object = nullptr;
90      Node* index = nullptr;
91      Node* value = nullptr;
92      MachineRepresentation representation = MachineRepresentation::kNone;
93    };
94
95    Element elements_[kMaxTrackedElements];
96    size_t next_index_ = 0;
97  };
98
99  // Information we use to resolve object aliasing. Currently, we consider
100  // object not aliased if they have different maps or if the nodes may
101  // not alias.
102  class AliasStateInfo;
103
104  struct FieldInfo {
105    FieldInfo() = default;
106    FieldInfo(Node* value, MachineRepresentation representation,
107              MaybeHandle<Name> name = {},
108              ConstFieldInfo const_field_info = ConstFieldInfo::None())
109        : value(value),
110          representation(representation),
111          name(name),
112          const_field_info(const_field_info) {}
113
114    bool operator==(const FieldInfo& other) const {
115      return value == other.value && representation == other.representation &&
116             name.address() == other.name.address() &&
117             const_field_info == other.const_field_info;
118    }
119    bool operator!=(const FieldInfo& other) const { return !(*this == other); }
120
121    Node* value = nullptr;
122    MachineRepresentation representation = MachineRepresentation::kNone;
123    MaybeHandle<Name> name;
124    ConstFieldInfo const_field_info;
125  };
126
127  // Abstract state to approximate the current state of a certain field along
128  // the effect paths through the graph.
129  class AbstractField final : public ZoneObject {
130   public:
131    explicit AbstractField(Zone* zone) : info_for_node_(zone) {}
132    AbstractField(Node* object, FieldInfo info, Zone* zone)
133        : info_for_node_(zone) {
134      info_for_node_.insert(std::make_pair(object, info));
135    }
136
137    AbstractField const* Extend(Node* object, FieldInfo info,
138                                Zone* zone) const {
139      AbstractField* that = zone->New<AbstractField>(zone);
140      that->info_for_node_ = this->info_for_node_;
141      that->info_for_node_[object] = info;
142      return that;
143    }
144    FieldInfo const* Lookup(Node* object) const;
145    AbstractField const* KillConst(Node* object, Zone* zone) const;
146    AbstractField const* Kill(const AliasStateInfo& alias_info,
147                              MaybeHandle<Name> name, Zone* zone) const;
148    bool Equals(AbstractField const* that) const {
149      return this == that || this->info_for_node_ == that->info_for_node_;
150    }
151    AbstractField const* Merge(AbstractField const* that, Zone* zone) const {
152      if (this->Equals(that)) return this;
153      AbstractField* copy = zone->New<AbstractField>(zone);
154      for (auto this_it : this->info_for_node_) {
155        Node* this_object = this_it.first;
156        FieldInfo this_second = this_it.second;
157        if (this_object->IsDead()) continue;
158        auto that_it = that->info_for_node_.find(this_object);
159        if (that_it != that->info_for_node_.end() &&
160            that_it->second == this_second) {
161          copy->info_for_node_.insert(this_it);
162        }
163      }
164      return copy;
165    }
166
167    void Print() const;
168
169   private:
170    ZoneMap<Node*, FieldInfo> info_for_node_;
171  };
172
173  static size_t const kMaxTrackedFields = 32;
174
175  // Abstract state to approximate the current map of an object along the
176  // effect paths through the graph.
177  class AbstractMaps final : public ZoneObject {
178   public:
179    explicit AbstractMaps(Zone* zone);
180    AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone);
181
182    AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps,
183                               Zone* zone) const;
184    bool Lookup(Node* object, ZoneHandleSet<Map>* object_maps) const;
185    AbstractMaps const* Kill(const AliasStateInfo& alias_info,
186                             Zone* zone) const;
187    bool Equals(AbstractMaps const* that) const {
188      return this == that || this->info_for_node_ == that->info_for_node_;
189    }
190    AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const;
191
192    void Print() const;
193
194   private:
195    ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_;
196  };
197
198  class IndexRange {
199   public:
200    IndexRange(int begin, int size) : begin_(begin), end_(begin + size) {
201      DCHECK_LE(0, begin);
202      DCHECK_LE(1, size);
203      if (end_ > static_cast<int>(kMaxTrackedFields)) {
204        *this = IndexRange::Invalid();
205      }
206    }
207    static IndexRange Invalid() { return IndexRange(); }
208
209    bool operator==(const IndexRange& other) {
210      return begin_ == other.begin_ && end_ == other.end_;
211    }
212    bool operator!=(const IndexRange& other) { return !(*this == other); }
213
214    struct Iterator {
215      int i;
216      int operator*() { return i; }
217      void operator++() { ++i; }
218      bool operator!=(Iterator other) { return i != other.i; }
219    };
220
221    Iterator begin() { return {begin_}; }
222    Iterator end() { return {end_}; }
223
224   private:
225    int begin_;
226    int end_;
227
228    IndexRange() : begin_(-1), end_(-1) {}
229  };
230
231  class AbstractState final : public ZoneObject {
232   public:
233    bool Equals(AbstractState const* that) const;
234    void Merge(AbstractState const* that, Zone* zone);
235
236    AbstractState const* SetMaps(Node* object, ZoneHandleSet<Map> maps,
237                                 Zone* zone) const;
238    AbstractState const* KillMaps(Node* object, Zone* zone) const;
239    AbstractState const* KillMaps(const AliasStateInfo& alias_info,
240                                  Zone* zone) const;
241    bool LookupMaps(Node* object, ZoneHandleSet<Map>* object_maps) const;
242
243    AbstractState const* AddField(Node* object, IndexRange index,
244                                  FieldInfo info, Zone* zone) const;
245    AbstractState const* KillConstField(Node* object, IndexRange index_range,
246                                        Zone* zone) const;
247    AbstractState const* KillField(const AliasStateInfo& alias_info,
248                                   IndexRange index, MaybeHandle<Name> name,
249                                   Zone* zone) const;
250    AbstractState const* KillField(Node* object, IndexRange index,
251                                   MaybeHandle<Name> name, Zone* zone) const;
252    AbstractState const* KillFields(Node* object, MaybeHandle<Name> name,
253                                    Zone* zone) const;
254    AbstractState const* KillAll(Zone* zone) const;
255    FieldInfo const* LookupField(Node* object, IndexRange index,
256                                 ConstFieldInfo const_field_info) const;
257
258    AbstractState const* AddElement(Node* object, Node* index, Node* value,
259                                    MachineRepresentation representation,
260                                    Zone* zone) const;
261    AbstractState const* KillElement(Node* object, Node* index,
262                                     Zone* zone) const;
263    Node* LookupElement(Node* object, Node* index,
264                        MachineRepresentation representation) const;
265
266    void Print() const;
267
268    static AbstractState const* empty_state() { return &empty_state_; }
269
270   private:
271    static AbstractState const empty_state_;
272
273    using AbstractFields = std::array<AbstractField const*, kMaxTrackedFields>;
274
275    bool FieldsEquals(AbstractFields const& this_fields,
276                      AbstractFields const& that_fields) const;
277    void FieldsMerge(AbstractFields* this_fields,
278                     AbstractFields const& that_fields, Zone* zone);
279
280    AbstractElements const* elements_ = nullptr;
281    AbstractFields fields_{};
282    AbstractFields const_fields_{};
283    AbstractMaps const* maps_ = nullptr;
284  };
285
286  class AbstractStateForEffectNodes final : public ZoneObject {
287   public:
288    explicit AbstractStateForEffectNodes(Zone* zone) : info_for_node_(zone) {}
289    AbstractState const* Get(Node* node) const;
290    void Set(Node* node, AbstractState const* state);
291
292    Zone* zone() const { return info_for_node_.get_allocator().zone(); }
293
294   private:
295    ZoneVector<AbstractState const*> info_for_node_;
296  };
297
298  Reduction ReduceCheckMaps(Node* node);
299  Reduction ReduceCompareMaps(Node* node);
300  Reduction ReduceMapGuard(Node* node);
301  Reduction ReduceEnsureWritableFastElements(Node* node);
302  Reduction ReduceMaybeGrowFastElements(Node* node);
303  Reduction ReduceTransitionElementsKind(Node* node);
304  Reduction ReduceLoadField(Node* node, FieldAccess const& access);
305  Reduction ReduceStoreField(Node* node, FieldAccess const& access);
306  Reduction ReduceLoadElement(Node* node);
307  Reduction ReduceStoreElement(Node* node);
308  Reduction ReduceTransitionAndStoreElement(Node* node);
309  Reduction ReduceStoreTypedElement(Node* node);
310  Reduction ReduceEffectPhi(Node* node);
311  Reduction ReduceStart(Node* node);
312  Reduction ReduceOtherNode(Node* node);
313
314  Reduction UpdateState(Node* node, AbstractState const* state);
315
316  AbstractState const* ComputeLoopState(Node* node,
317                                        AbstractState const* state) const;
318  AbstractState const* ComputeLoopStateForStoreField(
319      Node* current, LoadElimination::AbstractState const* state,
320      FieldAccess const& access) const;
321  AbstractState const* UpdateStateForPhi(AbstractState const* state,
322                                         Node* effect_phi, Node* phi);
323
324  static IndexRange FieldIndexOf(int offset, int representation_size);
325  static IndexRange FieldIndexOf(FieldAccess const& access);
326
327  static AbstractState const* empty_state() {
328    return AbstractState::empty_state();
329  }
330
331  CommonOperatorBuilder* common() const;
332  Isolate* isolate() const;
333  Factory* factory() const;
334  Graph* graph() const;
335  JSGraph* jsgraph() const { return jsgraph_; }
336  Zone* zone() const { return node_states_.zone(); }
337
338  AbstractStateForEffectNodes node_states_;
339  JSGraph* const jsgraph_;
340};
341
342}  // namespace compiler
343}  // namespace internal
344}  // namespace v8
345
346#endif  // V8_COMPILER_LOAD_ELIMINATION_H_
347