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 18 namespace v8 { 19 namespace internal { 20 21 namespace compiler { 22 23 // Forward declarations. 24 class CommonOperatorBuilder; 25 struct ObjectAccess; 26 class Graph; 27 class JSGraph; 28 29 class V8_EXPORT_PRIVATE CsaLoadElimination final 30 : public NON_EXPORTED_BASE(AdvancedReducer) { 31 public: CsaLoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)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; FieldInfov8::internal::compiler::final::FieldInfo49 FieldInfo(Node* value, MachineRepresentation representation) 50 : value(value), representation(representation) {} 51 operator ==v8::internal::compiler::final::FieldInfo52 bool operator==(const FieldInfo& other) const { 53 return value == other.value && representation == other.representation; 54 } 55 operator !=v8::internal::compiler::final::FieldInfo56 bool operator!=(const FieldInfo& other) const { return !(*this == other); } 57 IsEmptyv8::internal::compiler::final::FieldInfo58 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: HalfState(Zone* zone)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 Equals(HalfState const* that) const76 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> Update(OuterMap<OuterKey>& map, OuterKey outer_key, Node* inner_key, FieldInfo info)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 { AbstractStatev8::internal::compiler::final::AbstractState136 explicit AbstractState(Zone* zone) 137 : mutable_state(zone), immutable_state(zone) {} AbstractStatev8::internal::compiler::final::AbstractState138 explicit AbstractState(HalfState mutable_state, HalfState immutable_state) 139 : mutable_state(mutable_state), immutable_state(immutable_state) {} 140 Equalsv8::internal::compiler::final::AbstractState141 bool Equals(AbstractState const* that) const { 142 return this->immutable_state.Equals(&that->immutable_state) && 143 this->mutable_state.Equals(&that->mutable_state); 144 } IntersectWithv8::internal::compiler::final::AbstractState145 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; jsgraph() const173 JSGraph* jsgraph() const { return jsgraph_; } zone() const174 Zone* zone() const { return zone_; } empty_state() const175 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