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 
16 namespace v8 {
17 namespace internal {
18 
19 // Forward declarations.
20 class Factory;
21 
22 namespace compiler {
23 
24 // Forward declarations.
25 class CommonOperatorBuilder;
26 struct FieldAccess;
27 class Graph;
28 class JSGraph;
29 
30 class V8_EXPORT_PRIVATE LoadElimination final
NON_EXPORTED_BASE(AdvancedReducer)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