Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 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 | #include "src/compiler/store-store-elimination.h" |
| 6 | |
| 7 | #include "src/compiler/all-nodes.h" |
| 8 | #include "src/compiler/js-graph.h" |
| 9 | #include "src/compiler/node-properties.h" |
| 10 | #include "src/compiler/simplified-operator.h" |
| 11 | |
| 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | namespace compiler { |
| 15 | |
| 16 | #define TRACE(fmt, ...) \ |
| 17 | do { \ |
| 18 | if (FLAG_trace_store_elimination) { \ |
| 19 | PrintF("StoreStoreElimination::ReduceEligibleNode: " fmt "\n", \ |
| 20 | ##__VA_ARGS__); \ |
| 21 | } \ |
| 22 | } while (false) |
| 23 | |
| 24 | // A simple store-store elimination. When the effect chain contains the |
| 25 | // following sequence, |
| 26 | // |
| 27 | // - StoreField[[+off_1]](x1, y1) |
| 28 | // - StoreField[[+off_2]](x2, y2) |
| 29 | // - StoreField[[+off_3]](x3, y3) |
| 30 | // ... |
| 31 | // - StoreField[[+off_n]](xn, yn) |
| 32 | // |
| 33 | // where the xes are the objects and the ys are the values to be stored, then |
| 34 | // we are going to say that a store is superfluous if the same offset of the |
| 35 | // same object will be stored to in the future. If off_i == off_j and xi == xj |
| 36 | // and i < j, then we optimize the i'th StoreField away. |
| 37 | // |
| 38 | // This optimization should be initiated on the last StoreField in such a |
| 39 | // sequence. |
| 40 | // |
| 41 | // The algorithm works by walking the effect chain from the last StoreField |
| 42 | // upwards. While walking, we maintain a map {futureStore} from offsets to |
| 43 | // nodes; initially it is empty. As we walk the effect chain upwards, if |
| 44 | // futureStore[off] = n, then any store to node {n} with offset {off} is |
| 45 | // guaranteed to be useless because we do a full-width[1] store to that offset |
| 46 | // of that object in the near future anyway. For example, for this effect |
| 47 | // chain |
| 48 | // |
| 49 | // 71: StoreField(60, 0) |
| 50 | // 72: StoreField(65, 8) |
| 51 | // 73: StoreField(63, 8) |
| 52 | // 74: StoreField(65, 16) |
| 53 | // 75: StoreField(62, 8) |
| 54 | // |
| 55 | // just before we get to 72, we will have futureStore = {8: 63, 16: 65}. |
| 56 | // |
| 57 | // Here is the complete process. |
| 58 | // |
| 59 | // - We are at the end of a sequence of consecutive StoreFields. |
| 60 | // - We start out with futureStore = empty. |
| 61 | // - We then walk the effect chain upwards to find the next StoreField [2]. |
| 62 | // |
| 63 | // 1. If the offset is not a key of {futureStore} yet, we put it in. |
| 64 | // 2. If the offset is a key of {futureStore}, but futureStore[offset] is a |
| 65 | // different node, we overwrite futureStore[offset] with the current node. |
| 66 | // 3. If the offset is a key of {futureStore} and futureStore[offset] equals |
| 67 | // this node, we eliminate this StoreField. |
| 68 | // |
| 69 | // As long as the current effect input points to a node with a single effect |
| 70 | // output, and as long as its opcode is StoreField, we keep traversing |
| 71 | // upwards. |
| 72 | // |
| 73 | // [1] This optimization is unsound if we optimize away a store to an offset |
| 74 | // because we store to the same offset in the future, even though the future |
| 75 | // store is narrower than the store we optimize away. Therefore, in case (1) |
| 76 | // and (2) we only add/overwrite to the dictionary when the field access has |
| 77 | // maximal size. For simplicity of implementation, we do not try to detect |
| 78 | // case (3). |
| 79 | // |
| 80 | // [2] We make sure that we only traverse the linear part, that is, the part |
| 81 | // where every node has exactly one incoming and one outgoing effect edge. |
| 82 | // Also, we only keep walking upwards as long as we keep finding consecutive |
| 83 | // StoreFields on the same node. |
| 84 | |
| 85 | StoreStoreElimination::StoreStoreElimination(JSGraph* js_graph, Zone* temp_zone) |
| 86 | : jsgraph_(js_graph), temp_zone_(temp_zone) {} |
| 87 | |
| 88 | StoreStoreElimination::~StoreStoreElimination() {} |
| 89 | |
| 90 | void StoreStoreElimination::Run() { |
| 91 | // The store-store elimination performs work on chains of certain types of |
| 92 | // nodes. The elimination must be invoked on the lowest node in such a |
| 93 | // chain; we have a helper function IsEligibleNode that returns true |
| 94 | // precisely on the lowest node in such a chain. |
| 95 | // |
| 96 | // Because the elimination removes nodes from the graph, even remove nodes |
| 97 | // that the elimination was not invoked on, we cannot use a normal |
| 98 | // AdvancedReducer but we manually find which nodes to invoke the |
| 99 | // elimination on. Then in a next step, we invoke the elimination for each |
| 100 | // node that was eligible. |
| 101 | |
| 102 | NodeVector eligible(temp_zone()); // loops over all nodes |
| 103 | AllNodes all(temp_zone(), jsgraph()->graph()); |
| 104 | |
| 105 | for (Node* node : all.live) { |
| 106 | if (IsEligibleNode(node)) { |
| 107 | eligible.push_back(node); |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | for (Node* node : eligible) { |
| 112 | ReduceEligibleNode(node); |
| 113 | } |
| 114 | } |
| 115 | |
| 116 | namespace { |
| 117 | |
| 118 | // 16 bits was chosen fairly arbitrarily; it seems enough now. 8 bits is too |
| 119 | // few. |
| 120 | typedef uint16_t Offset; |
| 121 | |
| 122 | // To safely cast an offset from a FieldAccess, which has a wider range |
| 123 | // (namely int). |
| 124 | Offset ToOffset(int offset) { |
| 125 | CHECK(0 <= offset && offset < (1 << 8 * sizeof(Offset))); |
| 126 | return (Offset)offset; |
| 127 | } |
| 128 | |
| 129 | Offset ToOffset(const FieldAccess& access) { return ToOffset(access.offset); } |
| 130 | |
| 131 | // If node has a single effect use, return that node. If node has no or |
| 132 | // multiple effect uses, return nullptr. |
| 133 | Node* SingleEffectUse(Node* node) { |
| 134 | Node* last_use = nullptr; |
| 135 | for (Edge edge : node->use_edges()) { |
| 136 | if (!NodeProperties::IsEffectEdge(edge)) { |
| 137 | continue; |
| 138 | } |
| 139 | if (last_use != nullptr) { |
| 140 | // more than one |
| 141 | return nullptr; |
| 142 | } |
| 143 | last_use = edge.from(); |
| 144 | DCHECK_NOT_NULL(last_use); |
| 145 | } |
| 146 | return last_use; |
| 147 | } |
| 148 | |
| 149 | // Return true if node is the last consecutive StoreField node in a linear |
| 150 | // part of the effect chain. |
| 151 | bool IsEndOfStoreFieldChain(Node* node) { |
| 152 | Node* next_on_chain = SingleEffectUse(node); |
| 153 | return (next_on_chain == nullptr || |
| 154 | next_on_chain->op()->opcode() != IrOpcode::kStoreField); |
| 155 | } |
| 156 | |
| 157 | // The argument must be a StoreField node. If there is a node before it in the |
| 158 | // effect chain, and if this part of the effect chain is linear (no other |
| 159 | // effect uses of that previous node), then return that previous node. |
| 160 | // Otherwise, return nullptr. |
| 161 | // |
| 162 | // The returned node need not be a StoreField. |
| 163 | Node* PreviousEffectBeforeStoreField(Node* node) { |
| 164 | DCHECK_EQ(node->op()->opcode(), IrOpcode::kStoreField); |
| 165 | DCHECK_EQ(node->op()->EffectInputCount(), 1); |
| 166 | |
| 167 | Node* previous = NodeProperties::GetEffectInput(node); |
| 168 | if (previous != nullptr && node == SingleEffectUse(previous)) { |
| 169 | return previous; |
| 170 | } else { |
| 171 | return nullptr; |
| 172 | } |
| 173 | } |
| 174 | |
| 175 | size_t rep_size_of(MachineRepresentation rep) { |
| 176 | return ((size_t)1) << ElementSizeLog2Of(rep); |
| 177 | } |
| 178 | size_t rep_size_of(FieldAccess access) { |
| 179 | return rep_size_of(access.machine_type.representation()); |
| 180 | } |
| 181 | |
| 182 | } // namespace |
| 183 | |
| 184 | bool StoreStoreElimination::IsEligibleNode(Node* node) { |
| 185 | return (node->op()->opcode() == IrOpcode::kStoreField) && |
| 186 | IsEndOfStoreFieldChain(node); |
| 187 | } |
| 188 | |
| 189 | void StoreStoreElimination::ReduceEligibleNode(Node* node) { |
| 190 | DCHECK(IsEligibleNode(node)); |
| 191 | |
| 192 | // if (FLAG_trace_store_elimination) { |
| 193 | // PrintF("** StoreStoreElimination::ReduceEligibleNode: activated: |
| 194 | // #%d\n", |
| 195 | // node->id()); |
| 196 | // } |
| 197 | |
| 198 | TRACE("activated: #%d", node->id()); |
| 199 | |
| 200 | // Initialize empty futureStore. |
| 201 | ZoneMap<Offset, Node*> futureStore(temp_zone()); |
| 202 | |
| 203 | Node* current_node = node; |
| 204 | |
| 205 | do { |
| 206 | FieldAccess access = OpParameter<FieldAccess>(current_node->op()); |
| 207 | Offset offset = ToOffset(access); |
| 208 | Node* object_input = current_node->InputAt(0); |
| 209 | |
| 210 | Node* previous = PreviousEffectBeforeStoreField(current_node); |
| 211 | |
| 212 | CHECK(rep_size_of(access) <= rep_size_of(MachineRepresentation::kTagged)); |
| 213 | if (rep_size_of(access) == rep_size_of(MachineRepresentation::kTagged)) { |
| 214 | // Try to insert. If it was present, this will preserve the original |
| 215 | // value. |
| 216 | auto insert_result = |
| 217 | futureStore.insert(std::make_pair(offset, object_input)); |
| 218 | if (insert_result.second) { |
| 219 | // Key was not present. This means that there is no matching |
| 220 | // StoreField to this offset in the future, so we cannot optimize |
| 221 | // current_node away. However, we will record the current StoreField |
| 222 | // in futureStore, and continue ascending up the chain. |
| 223 | TRACE("#%d[[+%d]] -- wide, key not present", current_node->id(), |
| 224 | offset); |
| 225 | } else if (insert_result.first->second != object_input) { |
| 226 | // Key was present, and the value did not equal object_input. This |
| 227 | // means |
| 228 | // that there is a StoreField to this offset in the future, but the |
| 229 | // object instance comes from a different Node. We pessimistically |
| 230 | // assume that we cannot optimize current_node away. However, we will |
| 231 | // record the current StoreField in futureStore, and continue |
| 232 | // ascending up the chain. |
| 233 | insert_result.first->second = object_input; |
| 234 | TRACE("#%d[[+%d]] -- wide, diff object", current_node->id(), offset); |
| 235 | } else { |
| 236 | // Key was present, and the value equalled object_input. This means |
| 237 | // that soon after in the effect chain, we will do a StoreField to the |
| 238 | // same object with the same offset, therefore current_node can be |
| 239 | // optimized away. We don't need to update futureStore. |
| 240 | |
| 241 | Node* previous_effect = NodeProperties::GetEffectInput(current_node); |
| 242 | |
| 243 | NodeProperties::ReplaceUses(current_node, nullptr, previous_effect, |
| 244 | nullptr, nullptr); |
| 245 | current_node->Kill(); |
| 246 | TRACE("#%d[[+%d]] -- wide, eliminated", current_node->id(), offset); |
| 247 | } |
| 248 | } else { |
| 249 | TRACE("#%d[[+%d]] -- narrow, not eliminated", current_node->id(), offset); |
| 250 | } |
| 251 | |
| 252 | // Regardless of whether we eliminated node {current}, we want to |
| 253 | // continue walking up the effect chain. |
| 254 | |
| 255 | current_node = previous; |
| 256 | } while (current_node != nullptr && |
| 257 | current_node->op()->opcode() == IrOpcode::kStoreField); |
| 258 | |
| 259 | TRACE("finished"); |
| 260 | } |
| 261 | |
| 262 | } // namespace compiler |
| 263 | } // namespace internal |
| 264 | } // namespace v8 |