Home | History | Annotate | Download | only in compiler 
      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/compiler/graph-reducer.h"
     10 #include "src/globals.h"
     11 #include "src/zone/zone-handle-set.h"
     12 
     13 namespace v8 {
     14 namespace internal {
     15 
     16 // Forward declarations.
     17 class Factory;
     18 
     19 namespace compiler {
     20 
     21 // Foward declarations.
     22 class CommonOperatorBuilder;
     23 struct FieldAccess;
     24 class Graph;
     25 class JSGraph;
     26 
     27 class V8_EXPORT_PRIVATE LoadElimination final
     28     : public NON_EXPORTED_BASE(AdvancedReducer) {
     29  public:
     30   LoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
     31       : AdvancedReducer(editor), node_states_(zone), jsgraph_(jsgraph) {}
     32   ~LoadElimination() final {}
     33 
     34   Reduction Reduce(Node* node) final;
     35 
     36  private:
     37   static const size_t kMaxTrackedChecks = 8;
     38 
     39   // Abstract state to approximate the current state of checks that are
     40   // only invalidated by calls, i.e. array buffer neutering checks, along
     41   // the effect paths through the graph.
     42   class AbstractChecks final : public ZoneObject {
     43    public:
     44     explicit AbstractChecks(Zone* zone) {
     45       for (size_t i = 0; i < arraysize(nodes_); ++i) {
     46         nodes_[i] = nullptr;
     47       }
     48     }
     49     AbstractChecks(Node* node, Zone* zone) : AbstractChecks(zone) {
     50       nodes_[next_index_++] = node;
     51     }
     52 
     53     AbstractChecks const* Extend(Node* node, Zone* zone) const {
     54       AbstractChecks* that = new (zone) AbstractChecks(*this);
     55       that->nodes_[that->next_index_] = node;
     56       that->next_index_ = (that->next_index_ + 1) % arraysize(nodes_);
     57       return that;
     58     }
     59     Node* Lookup(Node* node) const;
     60     bool Equals(AbstractChecks const* that) const;
     61     AbstractChecks const* Merge(AbstractChecks const* that, Zone* zone) const;
     62 
     63     void Print() const;
     64 
     65    private:
     66     Node* nodes_[kMaxTrackedChecks];
     67     size_t next_index_ = 0;
     68   };
     69 
     70   static const size_t kMaxTrackedElements = 8;
     71 
     72   // Abstract state to approximate the current state of an element along the
     73   // effect paths through the graph.
     74   class AbstractElements final : public ZoneObject {
     75    public:
     76     explicit AbstractElements(Zone* zone) {
     77       for (size_t i = 0; i < arraysize(elements_); ++i) {
     78         elements_[i] = Element();
     79       }
     80     }
     81     AbstractElements(Node* object, Node* index, Node* value, Zone* zone)
     82         : AbstractElements(zone) {
     83       elements_[next_index_++] = Element(object, index, value);
     84     }
     85 
     86     AbstractElements const* Extend(Node* object, Node* index, Node* value,
     87                                    Zone* zone) const {
     88       AbstractElements* that = new (zone) AbstractElements(*this);
     89       that->elements_[that->next_index_] = Element(object, index, value);
     90       that->next_index_ = (that->next_index_ + 1) % arraysize(elements_);
     91       return that;
     92     }
     93     Node* Lookup(Node* object, Node* index) const;
     94     AbstractElements const* Kill(Node* object, Node* index, Zone* zone) const;
     95     bool Equals(AbstractElements const* that) const;
     96     AbstractElements const* Merge(AbstractElements const* that,
     97                                   Zone* zone) const;
     98 
     99     void Print() const;
    100 
    101    private:
    102     struct Element {
    103       Element() {}
    104       Element(Node* object, Node* index, Node* value)
    105           : object(object), index(index), value(value) {}
    106 
    107       Node* object = nullptr;
    108       Node* index = nullptr;
    109       Node* value = nullptr;
    110     };
    111 
    112     Element elements_[kMaxTrackedElements];
    113     size_t next_index_ = 0;
    114   };
    115 
    116   // Abstract state to approximate the current state of a certain field along
    117   // the effect paths through the graph.
    118   class AbstractField final : public ZoneObject {
    119    public:
    120     explicit AbstractField(Zone* zone) : info_for_node_(zone) {}
    121     AbstractField(Node* object, Node* value, Zone* zone)
    122         : info_for_node_(zone) {
    123       info_for_node_.insert(std::make_pair(object, value));
    124     }
    125 
    126     AbstractField const* Extend(Node* object, Node* value, Zone* zone) const {
    127       AbstractField* that = new (zone) AbstractField(zone);
    128       that->info_for_node_ = this->info_for_node_;
    129       that->info_for_node_.insert(std::make_pair(object, value));
    130       return that;
    131     }
    132     Node* Lookup(Node* object) const;
    133     AbstractField const* Kill(Node* object, Zone* zone) const;
    134     bool Equals(AbstractField const* that) const {
    135       return this == that || this->info_for_node_ == that->info_for_node_;
    136     }
    137     AbstractField const* Merge(AbstractField const* that, Zone* zone) const {
    138       if (this->Equals(that)) return this;
    139       AbstractField* copy = new (zone) AbstractField(zone);
    140       for (auto this_it : this->info_for_node_) {
    141         Node* this_object = this_it.first;
    142         Node* this_value = this_it.second;
    143         auto that_it = that->info_for_node_.find(this_object);
    144         if (that_it != that->info_for_node_.end() &&
    145             that_it->second == this_value) {
    146           copy->info_for_node_.insert(this_it);
    147         }
    148       }
    149       return copy;
    150     }
    151 
    152     void Print() const;
    153 
    154    private:
    155     ZoneMap<Node*, Node*> info_for_node_;
    156   };
    157 
    158   static size_t const kMaxTrackedFields = 32;
    159 
    160   // Abstract state to approximate the current map of an object along the
    161   // effect paths through the graph.
    162   class AbstractMaps final : public ZoneObject {
    163    public:
    164     explicit AbstractMaps(Zone* zone) : info_for_node_(zone) {}
    165     AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone)
    166         : info_for_node_(zone) {
    167       info_for_node_.insert(std::make_pair(object, maps));
    168     }
    169 
    170     AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps,
    171                                Zone* zone) const {
    172       AbstractMaps* that = new (zone) AbstractMaps(zone);
    173       that->info_for_node_ = this->info_for_node_;
    174       that->info_for_node_.insert(std::make_pair(object, maps));
    175       return that;
    176     }
    177     bool Lookup(Node* object, ZoneHandleSet<Map>* object_maps) const;
    178     AbstractMaps const* Kill(Node* object, Zone* zone) const;
    179     bool Equals(AbstractMaps const* that) const {
    180       return this == that || this->info_for_node_ == that->info_for_node_;
    181     }
    182     AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const {
    183       if (this->Equals(that)) return this;
    184       AbstractMaps* copy = new (zone) AbstractMaps(zone);
    185       for (auto this_it : this->info_for_node_) {
    186         Node* this_object = this_it.first;
    187         ZoneHandleSet<Map> this_maps = this_it.second;
    188         auto that_it = that->info_for_node_.find(this_object);
    189         if (that_it != that->info_for_node_.end() &&
    190             that_it->second == this_maps) {
    191           copy->info_for_node_.insert(this_it);
    192         }
    193       }
    194       return copy;
    195     }
    196 
    197     void Print() const;
    198 
    199    private:
    200     ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_;
    201   };
    202 
    203   class AbstractState final : public ZoneObject {
    204    public:
    205     AbstractState() {
    206       for (size_t i = 0; i < arraysize(fields_); ++i) {
    207         fields_[i] = nullptr;
    208       }
    209     }
    210 
    211     bool Equals(AbstractState const* that) const;
    212     void Merge(AbstractState const* that, Zone* zone);
    213 
    214     AbstractState const* AddMaps(Node* object, ZoneHandleSet<Map> maps,
    215                                  Zone* zone) const;
    216     AbstractState const* KillMaps(Node* object, Zone* zone) const;
    217     bool LookupMaps(Node* object, ZoneHandleSet<Map>* object_maps) const;
    218 
    219     AbstractState const* AddField(Node* object, size_t index, Node* value,
    220                                   Zone* zone) const;
    221     AbstractState const* KillField(Node* object, size_t index,
    222                                    Zone* zone) const;
    223     AbstractState const* KillFields(Node* object, Zone* zone) const;
    224     Node* LookupField(Node* object, size_t index) const;
    225 
    226     AbstractState const* AddElement(Node* object, Node* index, Node* value,
    227                                     Zone* zone) const;
    228     AbstractState const* KillElement(Node* object, Node* index,
    229                                      Zone* zone) const;
    230     Node* LookupElement(Node* object, Node* index) const;
    231 
    232     AbstractState const* AddCheck(Node* node, Zone* zone) const;
    233     Node* LookupCheck(Node* node) const;
    234 
    235     void Print() const;
    236 
    237    private:
    238     AbstractChecks const* checks_ = nullptr;
    239     AbstractElements const* elements_ = nullptr;
    240     AbstractField const* fields_[kMaxTrackedFields];
    241     AbstractMaps const* maps_ = nullptr;
    242   };
    243 
    244   class AbstractStateForEffectNodes final : public ZoneObject {
    245    public:
    246     explicit AbstractStateForEffectNodes(Zone* zone) : info_for_node_(zone) {}
    247     AbstractState const* Get(Node* node) const;
    248     void Set(Node* node, AbstractState const* state);
    249 
    250     Zone* zone() const { return info_for_node_.get_allocator().zone(); }
    251 
    252    private:
    253     ZoneVector<AbstractState const*> info_for_node_;
    254   };
    255 
    256   Reduction ReduceArrayBufferWasNeutered(Node* node);
    257   Reduction ReduceCheckMaps(Node* node);
    258   Reduction ReduceEnsureWritableFastElements(Node* node);
    259   Reduction ReduceMaybeGrowFastElements(Node* node);
    260   Reduction ReduceTransitionElementsKind(Node* node);
    261   Reduction ReduceLoadField(Node* node);
    262   Reduction ReduceStoreField(Node* node);
    263   Reduction ReduceLoadElement(Node* node);
    264   Reduction ReduceStoreElement(Node* node);
    265   Reduction ReduceStoreTypedElement(Node* node);
    266   Reduction ReduceEffectPhi(Node* node);
    267   Reduction ReduceStart(Node* node);
    268   Reduction ReduceOtherNode(Node* node);
    269 
    270   Reduction UpdateState(Node* node, AbstractState const* state);
    271 
    272   AbstractState const* ComputeLoopState(Node* node,
    273                                         AbstractState const* state) const;
    274 
    275   static int FieldIndexOf(int offset);
    276   static int FieldIndexOf(FieldAccess const& access);
    277 
    278   CommonOperatorBuilder* common() const;
    279   AbstractState const* empty_state() const { return &empty_state_; }
    280   Factory* factory() const;
    281   Graph* graph() const;
    282   JSGraph* jsgraph() const { return jsgraph_; }
    283   Zone* zone() const { return node_states_.zone(); }
    284 
    285   AbstractState const empty_state_;
    286   AbstractStateForEffectNodes node_states_;
    287   JSGraph* const jsgraph_;
    288 
    289   DISALLOW_COPY_AND_ASSIGN(LoadElimination);
    290 };
    291 
    292 }  // namespace compiler
    293 }  // namespace internal
    294 }  // namespace v8
    295 
    296 #endif  // V8_COMPILER_LOAD_ELIMINATION_H_
    297