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 NON_EXPORTED_BASE(AdvancedReducer)30 : public NON_EXPORTED_BASE(AdvancedReducer) { 31 public: 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; 49 FieldInfo(Node* value, MachineRepresentation representation) 50 : value(value), representation(representation) {} 51 52 bool operator==(const FieldInfo& other) const { 53 return value == other.value && representation == other.representation; 54 } 55 56 bool operator!=(const FieldInfo& other) const { return !(*this == other); } 57 58 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 AbstractState final : public ZoneObject { 66 public: 67 explicit AbstractState(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 76 bool Equals(AbstractState 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(AbstractState const* that); 85 86 AbstractState const* KillField(Node* object, Node* offset, 87 MachineRepresentation repr) const; 88 AbstractState const* AddField(Node* object, Node* offset, Node* value, 89 MachineRepresentation repr) const; 90 FieldInfo Lookup(Node* object, Node* offset) const; 91 92 void Print() const; 93 94 private: 95 Zone* zone_; 96 using InnerMap = PersistentMap<Node*, FieldInfo>; 97 template <typename OuterKey> 98 using OuterMap = PersistentMap<OuterKey, InnerMap>; 99 100 // offset -> object -> info 101 using ConstantOffsetInfos = OuterMap<uint32_t>; 102 ConstantOffsetInfos fresh_entries_; 103 ConstantOffsetInfos constant_entries_; 104 ConstantOffsetInfos arbitrary_entries_; 105 106 // object -> offset -> info 107 using UnknownOffsetInfos = OuterMap<Node*>; 108 UnknownOffsetInfos fresh_unknown_entries_; 109 UnknownOffsetInfos constant_unknown_entries_; 110 UnknownOffsetInfos arbitrary_unknown_entries_; 111 112 // Update {map} so that {map.Get(outer_key).Get(inner_key)} returns {info}. 113 template <typename OuterKey> 114 static void Update(OuterMap<OuterKey>& map, OuterKey outer_key, 115 Node* inner_key, FieldInfo info) { 116 InnerMap map_copy(map.Get(outer_key)); 117 map_copy.Set(inner_key, info); 118 map.Set(outer_key, map_copy); 119 } 120 121 // Kill all elements in {infos} which may alias with offset. 122 static void KillOffset(ConstantOffsetInfos& infos, uint32_t offset, 123 MachineRepresentation repr, Zone* zone); 124 void KillOffsetInFresh(Node* object, uint32_t offset, 125 MachineRepresentation repr); 126 127 template <typename OuterKey> 128 static void IntersectWith(OuterMap<OuterKey>& to, 129 const OuterMap<OuterKey>& from); 130 static void Print(const ConstantOffsetInfos& infos); 131 static void Print(const UnknownOffsetInfos& infos); 132 }; 133 134 Reduction ReduceLoadFromObject(Node* node, ObjectAccess const& access); 135 Reduction ReduceStoreToObject(Node* node, ObjectAccess const& access); 136 Reduction ReduceEffectPhi(Node* node); 137 Reduction ReduceStart(Node* node); 138 Reduction ReduceCall(Node* node); 139 Reduction ReduceOtherNode(Node* node); 140 141 Reduction UpdateState(Node* node, AbstractState const* state); 142 Reduction PropagateInputState(Node* node); 143 144 AbstractState const* ComputeLoopState(Node* node, 145 AbstractState const* state) const; 146 Node* TruncateAndExtend(Node* node, MachineRepresentation from, 147 MachineType to); 148 149 CommonOperatorBuilder* common() const; 150 MachineOperatorBuilder* machine() const; 151 Isolate* isolate() const; 152 Graph* graph() const; 153 JSGraph* jsgraph() const { return jsgraph_; } 154 Zone* zone() const { return zone_; } 155 AbstractState const* empty_state() const { return &empty_state_; } 156 157 AbstractState const empty_state_; 158 NodeAuxData<AbstractState const*> node_states_; 159 JSGraph* const jsgraph_; 160 Zone* zone_; 161 }; 162 163 } // namespace compiler 164 } // namespace internal 165 } // namespace v8 166 167 #endif // V8_COMPILER_CSA_LOAD_ELIMINATION_H_ 168