csa-load-elimination.h 6.96 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
// Copyright 2019 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_CSA_LOAD_ELIMINATION_H_
#define V8_COMPILER_CSA_LOAD_ELIMINATION_H_

#include "src/base/compiler-specific.h"
#include "src/codegen/machine-type.h"
#include "src/common/globals.h"
#include "src/compiler/graph-reducer.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/node-aux-data.h"
#include "src/compiler/persistent-map.h"
#include "src/handles/maybe-handles.h"
#include "src/zone/zone-handle-set.h"

namespace v8 {
namespace internal {

namespace compiler {

// Forward declarations.
class CommonOperatorBuilder;
struct ObjectAccess;
class Graph;
class JSGraph;

class V8_EXPORT_PRIVATE CsaLoadElimination final
    : public NON_EXPORTED_BASE(AdvancedReducer) {
 public:
  CsaLoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
      : AdvancedReducer(editor),
        empty_state_(zone),
        node_states_(jsgraph->graph()->NodeCount(), zone),
        jsgraph_(jsgraph),
        zone_(zone) {}
  ~CsaLoadElimination() final = default;
39 40
  CsaLoadElimination(const CsaLoadElimination&) = delete;
  CsaLoadElimination& operator=(const CsaLoadElimination&) = delete;
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

  const char* reducer_name() const override { return "CsaLoadElimination"; }

  Reduction Reduce(Node* node) final;

 private:
  struct FieldInfo {
    FieldInfo() = default;
    FieldInfo(Node* value, MachineRepresentation representation)
        : value(value), representation(representation) {}

    bool operator==(const FieldInfo& other) const {
      return value == other.value && representation == other.representation;
    }

    bool operator!=(const FieldInfo& other) const { return !(*this == other); }

    bool IsEmpty() const { return value == nullptr; }

    Node* value = nullptr;
    MachineRepresentation representation = MachineRepresentation::kNone;
  };

64
  // Design doc: https://bit.ly/36MfD6Y
65
  class HalfState final : public ZoneObject {
66
   public:
67
    explicit HalfState(Zone* zone)
68 69 70 71 72 73 74
        : zone_(zone),
          fresh_entries_(zone, InnerMap(zone)),
          constant_entries_(zone, InnerMap(zone)),
          arbitrary_entries_(zone, InnerMap(zone)),
          fresh_unknown_entries_(zone, InnerMap(zone)),
          constant_unknown_entries_(zone, InnerMap(zone)),
          arbitrary_unknown_entries_(zone, InnerMap(zone)) {}
75

76
    bool Equals(HalfState const* that) const {
77 78 79 80 81 82
      return fresh_entries_ == that->fresh_entries_ &&
             constant_entries_ == that->constant_entries_ &&
             arbitrary_entries_ == that->arbitrary_entries_ &&
             fresh_unknown_entries_ == that->fresh_unknown_entries_ &&
             constant_unknown_entries_ == that->constant_unknown_entries_ &&
             arbitrary_unknown_entries_ == that->arbitrary_unknown_entries_;
83
    }
84 85 86 87 88
    void IntersectWith(HalfState const* that);
    HalfState const* KillField(Node* object, Node* offset,
                               MachineRepresentation repr) const;
    HalfState const* AddField(Node* object, Node* offset, Node* value,
                              MachineRepresentation repr) const;
89
    FieldInfo Lookup(Node* object, Node* offset) const;
90 91 92
    void Print() const;

   private:
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
    using InnerMap = PersistentMap<Node*, FieldInfo>;
    template <typename OuterKey>
    using OuterMap = PersistentMap<OuterKey, InnerMap>;
    // offset -> object -> info
    using ConstantOffsetInfos = OuterMap<uint32_t>;
    // object -> offset -> info
    using UnknownOffsetInfos = OuterMap<Node*>;

    // Update {map} so that {map.Get(outer_key).Get(inner_key)} returns {info}.
    template <typename OuterKey>
    static void Update(OuterMap<OuterKey>& map, OuterKey outer_key,
                       Node* inner_key, FieldInfo info) {
      InnerMap map_copy(map.Get(outer_key));
      map_copy.Set(inner_key, info);
      map.Set(outer_key, map_copy);
    }

    // Kill all elements in {infos} which may alias with offset.
    static void KillOffset(ConstantOffsetInfos& infos, uint32_t offset,
                           MachineRepresentation repr, Zone* zone);
    void KillOffsetInFresh(Node* object, uint32_t offset,
                           MachineRepresentation repr);
    template <typename OuterKey>
    static void IntersectWith(OuterMap<OuterKey>& to,
                              const OuterMap<OuterKey>& from);
    static void Print(const ConstantOffsetInfos& infos);
    static void Print(const UnknownOffsetInfos& infos);
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151

    Zone* zone_;
    ConstantOffsetInfos fresh_entries_;
    ConstantOffsetInfos constant_entries_;
    ConstantOffsetInfos arbitrary_entries_;
    UnknownOffsetInfos fresh_unknown_entries_;
    UnknownOffsetInfos constant_unknown_entries_;
    UnknownOffsetInfos arbitrary_unknown_entries_;
  };

  // An {AbstractState} consists of two {HalfState}s, representing the mutable
  // and immutable sets of known fields, respectively. These sets correspond to
  // LoadFromObject/StoreToObject and LoadImmutableFromObject/
  // InitializeImmutableInObject respectively. The two half-states should not
  // overlap.
  struct AbstractState : public ZoneObject {
    explicit AbstractState(Zone* zone)
        : mutable_state(zone), immutable_state(zone) {}
    explicit AbstractState(HalfState mutable_state, HalfState immutable_state)
        : mutable_state(mutable_state), immutable_state(immutable_state) {}

    bool Equals(AbstractState const* that) const {
      return this->immutable_state.Equals(&that->immutable_state) &&
             this->mutable_state.Equals(&that->mutable_state);
    }
    void IntersectWith(AbstractState const* that) {
      mutable_state.IntersectWith(&that->mutable_state);
      immutable_state.IntersectWith(&that->immutable_state);
    }

    HalfState mutable_state;
    HalfState immutable_state;
152 153 154
  };

  Reduction ReduceLoadFromObject(Node* node, ObjectAccess const& access);
155
  Reduction ReduceStoreToObject(Node* node, ObjectAccess const& access);
156 157 158 159 160 161 162 163 164 165
  Reduction ReduceEffectPhi(Node* node);
  Reduction ReduceStart(Node* node);
  Reduction ReduceCall(Node* node);
  Reduction ReduceOtherNode(Node* node);

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

  AbstractState const* ComputeLoopState(Node* node,
                                        AbstractState const* state) const;
166 167
  Node* TruncateAndExtend(Node* node, MachineRepresentation from,
                          MachineType to);
168
  Reduction AssertUnreachable(Node* node);
169 170

  CommonOperatorBuilder* common() const;
171
  MachineOperatorBuilder* machine() const;
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188
  Isolate* isolate() const;
  Graph* graph() const;
  JSGraph* jsgraph() const { return jsgraph_; }
  Zone* zone() const { return zone_; }
  AbstractState const* empty_state() const { return &empty_state_; }

  AbstractState const empty_state_;
  NodeAuxData<AbstractState const*> node_states_;
  JSGraph* const jsgraph_;
  Zone* zone_;
};

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

#endif  // V8_COMPILER_CSA_LOAD_ELIMINATION_H_