load-elimination.h 10.2 KB
Newer Older
1
// Copyright 2016 the V8 project authors. All rights reserved.
2 3 4 5 6 7
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_LOAD_ELIMINATION_H_
#define V8_COMPILER_LOAD_ELIMINATION_H_

8
#include "src/base/compiler-specific.h"
9
#include "src/compiler/graph-reducer.h"
10
#include "src/globals.h"
11
#include "src/machine-type.h"
12
#include "src/maybe-handles.h"
13
#include "src/zone/zone-handle-set.h"
14

15 16
namespace v8 {
namespace internal {
17 18 19 20

// Forward declarations.
class Factory;

21 22
namespace compiler {

23
// Forward declarations.
24
class CommonOperatorBuilder;
25
struct FieldAccess;
26
class Graph;
27
class JSGraph;
28

29 30
class V8_EXPORT_PRIVATE LoadElimination final
    : public NON_EXPORTED_BASE(AdvancedReducer) {
31
 public:
32 33
  LoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
      : AdvancedReducer(editor), node_states_(zone), jsgraph_(jsgraph) {}
34
  ~LoadElimination() final = default;
35

36 37
  const char* reducer_name() const override { return "LoadElimination"; }

38
  Reduction Reduce(Node* node) final;
39 40

 private:
41 42 43 44 45 46 47 48 49 50 51
  static const size_t kMaxTrackedElements = 8;

  // Abstract state to approximate the current state of an element along the
  // effect paths through the graph.
  class AbstractElements final : public ZoneObject {
   public:
    explicit AbstractElements(Zone* zone) {
      for (size_t i = 0; i < arraysize(elements_); ++i) {
        elements_[i] = Element();
      }
    }
52 53
    AbstractElements(Node* object, Node* index, Node* value,
                     MachineRepresentation representation, Zone* zone)
54
        : AbstractElements(zone) {
55
      elements_[next_index_++] = Element(object, index, value, representation);
56 57 58
    }

    AbstractElements const* Extend(Node* object, Node* index, Node* value,
59
                                   MachineRepresentation representation,
60 61
                                   Zone* zone) const {
      AbstractElements* that = new (zone) AbstractElements(*this);
62 63
      that->elements_[that->next_index_] =
          Element(object, index, value, representation);
64 65 66
      that->next_index_ = (that->next_index_ + 1) % arraysize(elements_);
      return that;
    }
67 68
    Node* Lookup(Node* object, Node* index,
                 MachineRepresentation representation) const;
69 70 71 72 73
    AbstractElements const* Kill(Node* object, Node* index, Zone* zone) const;
    bool Equals(AbstractElements const* that) const;
    AbstractElements const* Merge(AbstractElements const* that,
                                  Zone* zone) const;

74 75
    void Print() const;

76 77
   private:
    struct Element {
78
      Element() = default;
79 80 81 82 83 84
      Element(Node* object, Node* index, Node* value,
              MachineRepresentation representation)
          : object(object),
            index(index),
            value(value),
            representation(representation) {}
85 86 87 88

      Node* object = nullptr;
      Node* index = nullptr;
      Node* value = nullptr;
89
      MachineRepresentation representation = MachineRepresentation::kNone;
90 91 92 93 94 95
    };

    Element elements_[kMaxTrackedElements];
    size_t next_index_ = 0;
  };

96 97 98 99 100
  // Information we use to resolve object aliasing. Currently, we consider
  // object not aliased if they have different maps or if the nodes may
  // not alias.
  class AliasStateInfo;

101 102 103 104 105
  // Abstract state to approximate the current state of a certain field along
  // the effect paths through the graph.
  class AbstractField final : public ZoneObject {
   public:
    explicit AbstractField(Zone* zone) : info_for_node_(zone) {}
106
    AbstractField(Node* object, Node* value, MaybeHandle<Name> name, Zone* zone)
107
        : info_for_node_(zone) {
108
      info_for_node_.insert(std::make_pair(object, Field(value, name)));
109 110
    }

111 112
    AbstractField const* Extend(Node* object, Node* value,
                                MaybeHandle<Name> name, Zone* zone) const {
113 114
      AbstractField* that = new (zone) AbstractField(zone);
      that->info_for_node_ = this->info_for_node_;
115
      that->info_for_node_.insert(std::make_pair(object, Field(value, name)));
116 117 118
      return that;
    }
    Node* Lookup(Node* object) const;
119 120
    AbstractField const* Kill(const AliasStateInfo& alias_info,
                              MaybeHandle<Name> name, Zone* zone) const;
121 122 123 124 125 126 127 128
    bool Equals(AbstractField const* that) const {
      return this == that || this->info_for_node_ == that->info_for_node_;
    }
    AbstractField const* Merge(AbstractField const* that, Zone* zone) const {
      if (this->Equals(that)) return this;
      AbstractField* copy = new (zone) AbstractField(zone);
      for (auto this_it : this->info_for_node_) {
        Node* this_object = this_it.first;
129
        Field this_second = this_it.second;
130
        if (this_object->IsDead()) continue;
131 132
        auto that_it = that->info_for_node_.find(this_object);
        if (that_it != that->info_for_node_.end() &&
133
            that_it->second == this_second) {
134 135 136 137 138 139
          copy->info_for_node_.insert(this_it);
        }
      }
      return copy;
    }

140 141
    void Print() const;

142
   private:
143
    struct Field {
144
      Field() = default;
145 146 147 148 149 150 151 152 153 154 155
      Field(Node* value, MaybeHandle<Name> name) : value(value), name(name) {}

      bool operator==(const Field& other) const {
        return value == other.value && name.address() == other.name.address();
      }

      Node* value = nullptr;
      MaybeHandle<Name> name;
    };

    ZoneMap<Node*, Field> info_for_node_;
156 157
  };

158
  static size_t const kMaxTrackedFields = 32;
159

160 161 162 163
  // Abstract state to approximate the current map of an object along the
  // effect paths through the graph.
  class AbstractMaps final : public ZoneObject {
   public:
164
    explicit AbstractMaps(Zone* zone);
165
    AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone);
166

167
    AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps,
168
                               Zone* zone) const;
169
    bool Lookup(Node* object, ZoneHandleSet<Map>* object_maps) const;
170 171
    AbstractMaps const* Kill(const AliasStateInfo& alias_info,
                             Zone* zone) const;
172 173 174
    bool Equals(AbstractMaps const* that) const {
      return this == that || this->info_for_node_ == that->info_for_node_;
    }
175
    AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const;
176 177 178 179

    void Print() const;

   private:
180
    ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_;
181 182
  };

183 184
  class AbstractState final : public ZoneObject {
   public:
185 186 187 188 189 190
    AbstractState() {
      for (size_t i = 0; i < arraysize(fields_); ++i) {
        fields_[i] = nullptr;
      }
    }

191 192 193
    bool Equals(AbstractState const* that) const;
    void Merge(AbstractState const* that, Zone* zone);

194
    AbstractState const* SetMaps(Node* object, ZoneHandleSet<Map> maps,
195 196
                                 Zone* zone) const;
    AbstractState const* KillMaps(Node* object, Zone* zone) const;
197 198
    AbstractState const* KillMaps(const AliasStateInfo& alias_info,
                                  Zone* zone) const;
199 200
    bool LookupMaps(Node* object, ZoneHandleSet<Map>* object_maps) const;

201
    AbstractState const* AddField(Node* object, size_t index, Node* value,
202
                                  MaybeHandle<Name> name, Zone* zone) const;
203 204 205
    AbstractState const* KillField(const AliasStateInfo& alias_info,
                                   size_t index, MaybeHandle<Name> name,
                                   Zone* zone) const;
206
    AbstractState const* KillField(Node* object, size_t index,
207 208 209
                                   MaybeHandle<Name> name, Zone* zone) const;
    AbstractState const* KillFields(Node* object, MaybeHandle<Name> name,
                                    Zone* zone) const;
210 211 212
    Node* LookupField(Node* object, size_t index) const;

    AbstractState const* AddElement(Node* object, Node* index, Node* value,
213
                                    MachineRepresentation representation,
214 215 216
                                    Zone* zone) const;
    AbstractState const* KillElement(Node* object, Node* index,
                                     Zone* zone) const;
217 218
    Node* LookupElement(Node* object, Node* index,
                        MachineRepresentation representation) const;
219

220 221
    void Print() const;

222 223 224
   private:
    AbstractElements const* elements_ = nullptr;
    AbstractField const* fields_[kMaxTrackedFields];
225
    AbstractMaps const* maps_ = nullptr;
226 227 228 229 230 231 232 233 234 235 236 237 238 239
  };

  class AbstractStateForEffectNodes final : public ZoneObject {
   public:
    explicit AbstractStateForEffectNodes(Zone* zone) : info_for_node_(zone) {}
    AbstractState const* Get(Node* node) const;
    void Set(Node* node, AbstractState const* state);

    Zone* zone() const { return info_for_node_.get_allocator().zone(); }

   private:
    ZoneVector<AbstractState const*> info_for_node_;
  };

240
  Reduction ReduceCheckMaps(Node* node);
241
  Reduction ReduceCompareMaps(Node* node);
242
  Reduction ReduceMapGuard(Node* node);
243
  Reduction ReduceEnsureWritableFastElements(Node* node);
244
  Reduction ReduceMaybeGrowFastElements(Node* node);
245
  Reduction ReduceTransitionElementsKind(Node* node);
246 247 248 249
  Reduction ReduceLoadField(Node* node);
  Reduction ReduceStoreField(Node* node);
  Reduction ReduceLoadElement(Node* node);
  Reduction ReduceStoreElement(Node* node);
250
  Reduction ReduceTransitionAndStoreElement(Node* node);
251
  Reduction ReduceStoreTypedElement(Node* node);
252 253 254 255 256 257 258 259
  Reduction ReduceEffectPhi(Node* node);
  Reduction ReduceStart(Node* node);
  Reduction ReduceOtherNode(Node* node);

  Reduction UpdateState(Node* node, AbstractState const* state);

  AbstractState const* ComputeLoopState(Node* node,
                                        AbstractState const* state) const;
260 261
  AbstractState const* UpdateStateForPhi(AbstractState const* state,
                                         Node* effect_phi, Node* phi);
262

263
  static int FieldIndexOf(int offset);
264 265
  static int FieldIndexOf(FieldAccess const& access);

266
  CommonOperatorBuilder* common() const;
267
  AbstractState const* empty_state() const { return &empty_state_; }
268
  Isolate* isolate() const;
269
  Factory* factory() const;
270
  Graph* graph() const;
271
  JSGraph* jsgraph() const { return jsgraph_; }
272 273 274 275
  Zone* zone() const { return node_states_.zone(); }

  AbstractState const empty_state_;
  AbstractStateForEffectNodes node_states_;
276
  JSGraph* const jsgraph_;
277

278
  DISALLOW_COPY_AND_ASSIGN(LoadElimination);
279 280 281 282 283 284 285
};

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_LOAD_ELIMINATION_H_