1// Copyright 2019 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_CSA_LOAD_ELIMINATION_H_
6#define V8_COMPILER_CSA_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/js-graph.h"
13#include "src/compiler/node-aux-data.h"
14#include "src/compiler/persistent-map.h"
15#include "src/handles/maybe-handles.h"
16#include "src/zone/zone-handle-set.h"
17
18namespace v8 {
19namespace internal {
20
21namespace compiler {
22
23// Forward declarations.
24class CommonOperatorBuilder;
25struct ObjectAccess;
26class Graph;
27class JSGraph;
28
29class V8_EXPORT_PRIVATE CsaLoadElimination final
30    : public NON_EXPORTED_BASE(AdvancedReducer) {
31 public:
32  CsaLoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
33      : AdvancedReducer(editor),
34        empty_state_(zone),
35        node_states_(jsgraph->graph()->NodeCount(), zone),
36        jsgraph_(jsgraph),
37        zone_(zone) {}
38  ~CsaLoadElimination() final = default;
39  CsaLoadElimination(const CsaLoadElimination&) = delete;
40  CsaLoadElimination& operator=(const CsaLoadElimination&) = delete;
41
42  const char* reducer_name() const override { return "CsaLoadElimination"; }
43
44  Reduction Reduce(Node* node) final;
45
46 private:
47  struct FieldInfo {
48    FieldInfo() = default;
49    FieldInfo(Node* value, MachineRepresentation representation)
50        : value(value), representation(representation) {}
51
52    bool operator==(const FieldInfo& other) const {
53      return value == other.value && representation == other.representation;
54    }
55
56    bool operator!=(const FieldInfo& other) const { return !(*this == other); }
57
58    bool IsEmpty() const { return value == nullptr; }
59
60    Node* value = nullptr;
61    MachineRepresentation representation = MachineRepresentation::kNone;
62  };
63
64  // Design doc: https://bit.ly/36MfD6Y
65  class HalfState final : public ZoneObject {
66   public:
67    explicit HalfState(Zone* zone)
68        : zone_(zone),
69          fresh_entries_(zone, InnerMap(zone)),
70          constant_entries_(zone, InnerMap(zone)),
71          arbitrary_entries_(zone, InnerMap(zone)),
72          fresh_unknown_entries_(zone, InnerMap(zone)),
73          constant_unknown_entries_(zone, InnerMap(zone)),
74          arbitrary_unknown_entries_(zone, InnerMap(zone)) {}
75
76    bool Equals(HalfState const* that) const {
77      return fresh_entries_ == that->fresh_entries_ &&
78             constant_entries_ == that->constant_entries_ &&
79             arbitrary_entries_ == that->arbitrary_entries_ &&
80             fresh_unknown_entries_ == that->fresh_unknown_entries_ &&
81             constant_unknown_entries_ == that->constant_unknown_entries_ &&
82             arbitrary_unknown_entries_ == that->arbitrary_unknown_entries_;
83    }
84    void IntersectWith(HalfState const* that);
85    HalfState const* KillField(Node* object, Node* offset,
86                               MachineRepresentation repr) const;
87    HalfState const* AddField(Node* object, Node* offset, Node* value,
88                              MachineRepresentation repr) const;
89    FieldInfo Lookup(Node* object, Node* offset) const;
90    void Print() const;
91
92   private:
93    using InnerMap = PersistentMap<Node*, FieldInfo>;
94    template <typename OuterKey>
95    using OuterMap = PersistentMap<OuterKey, InnerMap>;
96    // offset -> object -> info
97    using ConstantOffsetInfos = OuterMap<uint32_t>;
98    // object -> offset -> info
99    using UnknownOffsetInfos = OuterMap<Node*>;
100
101    // Update {map} so that {map.Get(outer_key).Get(inner_key)} returns {info}.
102    template <typename OuterKey>
103    static void Update(OuterMap<OuterKey>& map, OuterKey outer_key,
104                       Node* inner_key, FieldInfo info) {
105      InnerMap map_copy(map.Get(outer_key));
106      map_copy.Set(inner_key, info);
107      map.Set(outer_key, map_copy);
108    }
109
110    // Kill all elements in {infos} which may alias with offset.
111    static void KillOffset(ConstantOffsetInfos& infos, uint32_t offset,
112                           MachineRepresentation repr, Zone* zone);
113    void KillOffsetInFresh(Node* object, uint32_t offset,
114                           MachineRepresentation repr);
115    template <typename OuterKey>
116    static void IntersectWith(OuterMap<OuterKey>& to,
117                              const OuterMap<OuterKey>& from);
118    static void Print(const ConstantOffsetInfos& infos);
119    static void Print(const UnknownOffsetInfos& infos);
120
121    Zone* zone_;
122    ConstantOffsetInfos fresh_entries_;
123    ConstantOffsetInfos constant_entries_;
124    ConstantOffsetInfos arbitrary_entries_;
125    UnknownOffsetInfos fresh_unknown_entries_;
126    UnknownOffsetInfos constant_unknown_entries_;
127    UnknownOffsetInfos arbitrary_unknown_entries_;
128  };
129
130  // An {AbstractState} consists of two {HalfState}s, representing the mutable
131  // and immutable sets of known fields, respectively. These sets correspond to
132  // LoadFromObject/StoreToObject and LoadImmutableFromObject/
133  // InitializeImmutableInObject respectively. The two half-states should not
134  // overlap.
135  struct AbstractState : public ZoneObject {
136    explicit AbstractState(Zone* zone)
137        : mutable_state(zone), immutable_state(zone) {}
138    explicit AbstractState(HalfState mutable_state, HalfState immutable_state)
139        : mutable_state(mutable_state), immutable_state(immutable_state) {}
140
141    bool Equals(AbstractState const* that) const {
142      return this->immutable_state.Equals(&that->immutable_state) &&
143             this->mutable_state.Equals(&that->mutable_state);
144    }
145    void IntersectWith(AbstractState const* that) {
146      mutable_state.IntersectWith(&that->mutable_state);
147      immutable_state.IntersectWith(&that->immutable_state);
148    }
149
150    HalfState mutable_state;
151    HalfState immutable_state;
152  };
153
154  Reduction ReduceLoadFromObject(Node* node, ObjectAccess const& access);
155  Reduction ReduceStoreToObject(Node* node, ObjectAccess const& access);
156  Reduction ReduceEffectPhi(Node* node);
157  Reduction ReduceStart(Node* node);
158  Reduction ReduceCall(Node* node);
159  Reduction ReduceOtherNode(Node* node);
160
161  Reduction UpdateState(Node* node, AbstractState const* state);
162  Reduction PropagateInputState(Node* node);
163
164  AbstractState const* ComputeLoopState(Node* node,
165                                        AbstractState const* state) const;
166  Node* TruncateAndExtend(Node* node, MachineRepresentation from,
167                          MachineType to);
168
169  CommonOperatorBuilder* common() const;
170  MachineOperatorBuilder* machine() const;
171  Isolate* isolate() const;
172  Graph* graph() const;
173  JSGraph* jsgraph() const { return jsgraph_; }
174  Zone* zone() const { return zone_; }
175  AbstractState const* empty_state() const { return &empty_state_; }
176
177  AbstractState const empty_state_;
178  NodeAuxData<AbstractState const*> node_states_;
179  JSGraph* const jsgraph_;
180  Zone* zone_;
181};
182
183}  // namespace compiler
184}  // namespace internal
185}  // namespace v8
186
187#endif  // V8_COMPILER_CSA_LOAD_ELIMINATION_H_
188