load-elimination.h 12.4 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/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 17
namespace v8 {
namespace internal {
18 19 20 21

// Forward declarations.
class Factory;

22 23
namespace compiler {

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

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

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

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

 private:
42 43 44 45 46 47 48 49 50 51 52
  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();
      }
    }
53 54
    AbstractElements(Node* object, Node* index, Node* value,
                     MachineRepresentation representation, Zone* zone)
55
        : AbstractElements(zone) {
56
      elements_[next_index_++] = Element(object, index, value, representation);
57 58 59
    }

    AbstractElements const* Extend(Node* object, Node* index, Node* value,
60
                                   MachineRepresentation representation,
61
                                   Zone* zone) const {
62
      AbstractElements* that = zone->New<AbstractElements>(*this);
63 64
      that->elements_[that->next_index_] =
          Element(object, index, value, representation);
65 66 67
      that->next_index_ = (that->next_index_ + 1) % arraysize(elements_);
      return that;
    }
68 69
    Node* Lookup(Node* object, Node* index,
                 MachineRepresentation representation) const;
70 71 72 73 74
    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;

75 76
    void Print() const;

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

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

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

97 98 99 100 101
  // 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;

102 103
  struct FieldInfo {
    FieldInfo() = default;
104 105 106 107 108 109 110
    FieldInfo(Node* value, MachineRepresentation representation,
              MaybeHandle<Name> name = {},
              ConstFieldInfo const_field_info = ConstFieldInfo::None())
        : value(value),
          representation(representation),
          name(name),
          const_field_info(const_field_info) {}
111 112

    bool operator==(const FieldInfo& other) const {
113 114 115
      return value == other.value && representation == other.representation &&
             name.address() == other.name.address() &&
             const_field_info == other.const_field_info;
116
    }
117
    bool operator!=(const FieldInfo& other) const { return !(*this == other); }
118 119 120

    Node* value = nullptr;
    MachineRepresentation representation = MachineRepresentation::kNone;
121 122
    MaybeHandle<Name> name;
    ConstFieldInfo const_field_info;
123 124
  };

125 126 127 128 129
  // 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) {}
130
    AbstractField(Node* object, FieldInfo info, Zone* zone)
131
        : info_for_node_(zone) {
132
      info_for_node_.insert(std::make_pair(object, info));
133 134
    }

135 136
    AbstractField const* Extend(Node* object, FieldInfo info,
                                Zone* zone) const {
137
      AbstractField* that = zone->New<AbstractField>(zone);
138
      that->info_for_node_ = this->info_for_node_;
139
      that->info_for_node_[object] = info;
140 141
      return that;
    }
142
    FieldInfo const* Lookup(Node* object) const;
143
    AbstractField const* KillConst(Node* object, Zone* zone) const;
144 145
    AbstractField const* Kill(const AliasStateInfo& alias_info,
                              MaybeHandle<Name> name, Zone* zone) const;
146 147 148 149 150
    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;
151
      AbstractField* copy = zone->New<AbstractField>(zone);
152 153
      for (auto this_it : this->info_for_node_) {
        Node* this_object = this_it.first;
154
        FieldInfo this_second = this_it.second;
155
        if (this_object->IsDead()) continue;
156 157
        auto that_it = that->info_for_node_.find(this_object);
        if (that_it != that->info_for_node_.end() &&
158
            that_it->second == this_second) {
159 160 161 162 163 164
          copy->info_for_node_.insert(this_it);
        }
      }
      return copy;
    }

165 166
    void Print() const;

167
   private:
168
    ZoneMap<Node*, FieldInfo> info_for_node_;
169 170
  };

171
  static size_t const kMaxTrackedFields = 32;
172

173 174 175 176
  // Abstract state to approximate the current map of an object along the
  // effect paths through the graph.
  class AbstractMaps final : public ZoneObject {
   public:
177
    explicit AbstractMaps(Zone* zone);
178
    AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone);
179

180
    AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps,
181
                               Zone* zone) const;
182
    bool Lookup(Node* object, ZoneHandleSet<Map>* object_maps) const;
183 184
    AbstractMaps const* Kill(const AliasStateInfo& alias_info,
                             Zone* zone) const;
185 186 187
    bool Equals(AbstractMaps const* that) const {
      return this == that || this->info_for_node_ == that->info_for_node_;
    }
188
    AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const;
189 190 191 192

    void Print() const;

   private:
193
    ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_;
194 195
  };

196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
  class IndexRange {
   public:
    IndexRange(int begin, int size) : begin_(begin), end_(begin + size) {
      DCHECK_LE(0, begin);
      DCHECK_LE(1, size);
      if (end_ > static_cast<int>(kMaxTrackedFields)) {
        *this = IndexRange::Invalid();
      }
    }
    static IndexRange Invalid() { return IndexRange(); }

    bool operator==(const IndexRange& other) {
      return begin_ == other.begin_ && end_ == other.end_;
    }
    bool operator!=(const IndexRange& other) { return !(*this == other); }

    struct Iterator {
      int i;
      int operator*() { return i; }
      void operator++() { ++i; }
      bool operator!=(Iterator other) { return i != other.i; }
    };

    Iterator begin() { return {begin_}; }
    Iterator end() { return {end_}; }

   private:
    int begin_;
    int end_;

    IndexRange() : begin_(-1), end_(-1) {}
  };

229 230 231 232 233
  class AbstractState final : public ZoneObject {
   public:
    bool Equals(AbstractState const* that) const;
    void Merge(AbstractState const* that, Zone* zone);

234
    AbstractState const* SetMaps(Node* object, ZoneHandleSet<Map> maps,
235 236
                                 Zone* zone) const;
    AbstractState const* KillMaps(Node* object, Zone* zone) const;
237 238
    AbstractState const* KillMaps(const AliasStateInfo& alias_info,
                                  Zone* zone) const;
239 240
    bool LookupMaps(Node* object, ZoneHandleSet<Map>* object_maps) const;

241
    AbstractState const* AddField(Node* object, IndexRange index,
242
                                  FieldInfo info, Zone* zone) const;
243 244
    AbstractState const* KillConstField(Node* object, IndexRange index_range,
                                        Zone* zone) const;
245
    AbstractState const* KillField(const AliasStateInfo& alias_info,
246
                                   IndexRange index, MaybeHandle<Name> name,
247
                                   Zone* zone) const;
248
    AbstractState const* KillField(Node* object, IndexRange index,
249 250 251
                                   MaybeHandle<Name> name, Zone* zone) const;
    AbstractState const* KillFields(Node* object, MaybeHandle<Name> name,
                                    Zone* zone) const;
252
    AbstractState const* KillAll(Zone* zone) const;
253
    FieldInfo const* LookupField(Node* object, IndexRange index,
254
                                 ConstFieldInfo const_field_info) const;
255 256

    AbstractState const* AddElement(Node* object, Node* index, Node* value,
257
                                    MachineRepresentation representation,
258 259 260
                                    Zone* zone) const;
    AbstractState const* KillElement(Node* object, Node* index,
                                     Zone* zone) const;
261 262
    Node* LookupElement(Node* object, Node* index,
                        MachineRepresentation representation) const;
263

264 265
    void Print() const;

266 267
    static AbstractState const* empty_state() { return &empty_state_; }

268
   private:
269 270 271 272 273 274
    static AbstractState const empty_state_;

    using AbstractFields = std::array<AbstractField const*, kMaxTrackedFields>;

    bool FieldsEquals(AbstractFields const& this_fields,
                      AbstractFields const& that_fields) const;
275
    void FieldsMerge(AbstractFields* this_fields,
276 277
                     AbstractFields const& that_fields, Zone* zone);

278
    AbstractElements const* elements_ = nullptr;
279 280
    AbstractFields fields_{};
    AbstractFields const_fields_{};
281
    AbstractMaps const* maps_ = nullptr;
282 283 284 285 286 287 288 289 290 291 292 293 294 295
  };

  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_;
  };

296
  Reduction ReduceCheckMaps(Node* node);
297
  Reduction ReduceCompareMaps(Node* node);
298
  Reduction ReduceMapGuard(Node* node);
299
  Reduction ReduceEnsureWritableFastElements(Node* node);
300
  Reduction ReduceMaybeGrowFastElements(Node* node);
301
  Reduction ReduceTransitionElementsKind(Node* node);
302 303
  Reduction ReduceLoadField(Node* node, FieldAccess const& access);
  Reduction ReduceStoreField(Node* node, FieldAccess const& access);
304 305
  Reduction ReduceLoadElement(Node* node);
  Reduction ReduceStoreElement(Node* node);
306
  Reduction ReduceTransitionAndStoreElement(Node* node);
307
  Reduction ReduceStoreTypedElement(Node* node);
308 309 310 311 312 313 314 315
  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;
316 317 318
  AbstractState const* ComputeLoopStateForStoreField(
      Node* current, LoadElimination::AbstractState const* state,
      FieldAccess const& access) const;
319 320
  AbstractState const* UpdateStateForPhi(AbstractState const* state,
                                         Node* effect_phi, Node* phi);
321

322 323
  static IndexRange FieldIndexOf(int offset, int representation_size);
  static IndexRange FieldIndexOf(FieldAccess const& access);
324

325 326 327 328
  static AbstractState const* empty_state() {
    return AbstractState::empty_state();
  }

329
  CommonOperatorBuilder* common() const;
330
  Isolate* isolate() const;
331
  Factory* factory() const;
332
  Graph* graph() const;
333
  JSGraph* jsgraph() const { return jsgraph_; }
334 335 336
  Zone* zone() const { return node_states_.zone(); }

  AbstractStateForEffectNodes node_states_;
337
  JSGraph* const jsgraph_;
338

339
  DISALLOW_COPY_AND_ASSIGN(LoadElimination);
340 341 342 343 344 345 346
};

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

#endif  // V8_COMPILER_LOAD_ELIMINATION_H_