| // Copyright 2016 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. |
| |
| #include "src/compiler/store-store-elimination.h" |
| |
| #include "src/compiler/all-nodes.h" |
| #include "src/compiler/js-graph.h" |
| #include "src/compiler/node-properties.h" |
| #include "src/compiler/simplified-operator.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| #define TRACE(fmt, ...) \ |
| do { \ |
| if (FLAG_trace_store_elimination) { \ |
| PrintF("StoreStoreElimination::ReduceEligibleNode: " fmt "\n", \ |
| ##__VA_ARGS__); \ |
| } \ |
| } while (false) |
| |
| // A simple store-store elimination. When the effect chain contains the |
| // following sequence, |
| // |
| // - StoreField[[+off_1]](x1, y1) |
| // - StoreField[[+off_2]](x2, y2) |
| // - StoreField[[+off_3]](x3, y3) |
| // ... |
| // - StoreField[[+off_n]](xn, yn) |
| // |
| // where the xes are the objects and the ys are the values to be stored, then |
| // we are going to say that a store is superfluous if the same offset of the |
| // same object will be stored to in the future. If off_i == off_j and xi == xj |
| // and i < j, then we optimize the i'th StoreField away. |
| // |
| // This optimization should be initiated on the last StoreField in such a |
| // sequence. |
| // |
| // The algorithm works by walking the effect chain from the last StoreField |
| // upwards. While walking, we maintain a map {futureStore} from offsets to |
| // nodes; initially it is empty. As we walk the effect chain upwards, if |
| // futureStore[off] = n, then any store to node {n} with offset {off} is |
| // guaranteed to be useless because we do a full-width[1] store to that offset |
| // of that object in the near future anyway. For example, for this effect |
| // chain |
| // |
| // 71: StoreField(60, 0) |
| // 72: StoreField(65, 8) |
| // 73: StoreField(63, 8) |
| // 74: StoreField(65, 16) |
| // 75: StoreField(62, 8) |
| // |
| // just before we get to 72, we will have futureStore = {8: 63, 16: 65}. |
| // |
| // Here is the complete process. |
| // |
| // - We are at the end of a sequence of consecutive StoreFields. |
| // - We start out with futureStore = empty. |
| // - We then walk the effect chain upwards to find the next StoreField [2]. |
| // |
| // 1. If the offset is not a key of {futureStore} yet, we put it in. |
| // 2. If the offset is a key of {futureStore}, but futureStore[offset] is a |
| // different node, we overwrite futureStore[offset] with the current node. |
| // 3. If the offset is a key of {futureStore} and futureStore[offset] equals |
| // this node, we eliminate this StoreField. |
| // |
| // As long as the current effect input points to a node with a single effect |
| // output, and as long as its opcode is StoreField, we keep traversing |
| // upwards. |
| // |
| // [1] This optimization is unsound if we optimize away a store to an offset |
| // because we store to the same offset in the future, even though the future |
| // store is narrower than the store we optimize away. Therefore, in case (1) |
| // and (2) we only add/overwrite to the dictionary when the field access has |
| // maximal size. For simplicity of implementation, we do not try to detect |
| // case (3). |
| // |
| // [2] We make sure that we only traverse the linear part, that is, the part |
| // where every node has exactly one incoming and one outgoing effect edge. |
| // Also, we only keep walking upwards as long as we keep finding consecutive |
| // StoreFields on the same node. |
| |
| StoreStoreElimination::StoreStoreElimination(JSGraph* js_graph, Zone* temp_zone) |
| : jsgraph_(js_graph), temp_zone_(temp_zone) {} |
| |
| StoreStoreElimination::~StoreStoreElimination() {} |
| |
| void StoreStoreElimination::Run() { |
| // The store-store elimination performs work on chains of certain types of |
| // nodes. The elimination must be invoked on the lowest node in such a |
| // chain; we have a helper function IsEligibleNode that returns true |
| // precisely on the lowest node in such a chain. |
| // |
| // Because the elimination removes nodes from the graph, even remove nodes |
| // that the elimination was not invoked on, we cannot use a normal |
| // AdvancedReducer but we manually find which nodes to invoke the |
| // elimination on. Then in a next step, we invoke the elimination for each |
| // node that was eligible. |
| |
| NodeVector eligible(temp_zone()); // loops over all nodes |
| AllNodes all(temp_zone(), jsgraph()->graph()); |
| |
| for (Node* node : all.live) { |
| if (IsEligibleNode(node)) { |
| eligible.push_back(node); |
| } |
| } |
| |
| for (Node* node : eligible) { |
| ReduceEligibleNode(node); |
| } |
| } |
| |
| namespace { |
| |
| // 16 bits was chosen fairly arbitrarily; it seems enough now. 8 bits is too |
| // few. |
| typedef uint16_t Offset; |
| |
| // To safely cast an offset from a FieldAccess, which has a wider range |
| // (namely int). |
| Offset ToOffset(int offset) { |
| CHECK(0 <= offset && offset < (1 << 8 * sizeof(Offset))); |
| return (Offset)offset; |
| } |
| |
| Offset ToOffset(const FieldAccess& access) { return ToOffset(access.offset); } |
| |
| // If node has a single effect use, return that node. If node has no or |
| // multiple effect uses, return nullptr. |
| Node* SingleEffectUse(Node* node) { |
| Node* last_use = nullptr; |
| for (Edge edge : node->use_edges()) { |
| if (!NodeProperties::IsEffectEdge(edge)) { |
| continue; |
| } |
| if (last_use != nullptr) { |
| // more than one |
| return nullptr; |
| } |
| last_use = edge.from(); |
| DCHECK_NOT_NULL(last_use); |
| } |
| return last_use; |
| } |
| |
| // Return true if node is the last consecutive StoreField node in a linear |
| // part of the effect chain. |
| bool IsEndOfStoreFieldChain(Node* node) { |
| Node* next_on_chain = SingleEffectUse(node); |
| return (next_on_chain == nullptr || |
| next_on_chain->op()->opcode() != IrOpcode::kStoreField); |
| } |
| |
| // The argument must be a StoreField node. If there is a node before it in the |
| // effect chain, and if this part of the effect chain is linear (no other |
| // effect uses of that previous node), then return that previous node. |
| // Otherwise, return nullptr. |
| // |
| // The returned node need not be a StoreField. |
| Node* PreviousEffectBeforeStoreField(Node* node) { |
| DCHECK_EQ(node->op()->opcode(), IrOpcode::kStoreField); |
| DCHECK_EQ(node->op()->EffectInputCount(), 1); |
| |
| Node* previous = NodeProperties::GetEffectInput(node); |
| if (previous != nullptr && node == SingleEffectUse(previous)) { |
| return previous; |
| } else { |
| return nullptr; |
| } |
| } |
| |
| size_t rep_size_of(MachineRepresentation rep) { |
| return ((size_t)1) << ElementSizeLog2Of(rep); |
| } |
| size_t rep_size_of(FieldAccess access) { |
| return rep_size_of(access.machine_type.representation()); |
| } |
| |
| } // namespace |
| |
| bool StoreStoreElimination::IsEligibleNode(Node* node) { |
| return (node->op()->opcode() == IrOpcode::kStoreField) && |
| IsEndOfStoreFieldChain(node); |
| } |
| |
| void StoreStoreElimination::ReduceEligibleNode(Node* node) { |
| DCHECK(IsEligibleNode(node)); |
| |
| // if (FLAG_trace_store_elimination) { |
| // PrintF("** StoreStoreElimination::ReduceEligibleNode: activated: |
| // #%d\n", |
| // node->id()); |
| // } |
| |
| TRACE("activated: #%d", node->id()); |
| |
| // Initialize empty futureStore. |
| ZoneMap<Offset, Node*> futureStore(temp_zone()); |
| |
| Node* current_node = node; |
| |
| do { |
| FieldAccess access = OpParameter<FieldAccess>(current_node->op()); |
| Offset offset = ToOffset(access); |
| Node* object_input = current_node->InputAt(0); |
| |
| Node* previous = PreviousEffectBeforeStoreField(current_node); |
| |
| CHECK(rep_size_of(access) <= rep_size_of(MachineRepresentation::kTagged)); |
| if (rep_size_of(access) == rep_size_of(MachineRepresentation::kTagged)) { |
| // Try to insert. If it was present, this will preserve the original |
| // value. |
| auto insert_result = |
| futureStore.insert(std::make_pair(offset, object_input)); |
| if (insert_result.second) { |
| // Key was not present. This means that there is no matching |
| // StoreField to this offset in the future, so we cannot optimize |
| // current_node away. However, we will record the current StoreField |
| // in futureStore, and continue ascending up the chain. |
| TRACE("#%d[[+%d]] -- wide, key not present", current_node->id(), |
| offset); |
| } else if (insert_result.first->second != object_input) { |
| // Key was present, and the value did not equal object_input. This |
| // means |
| // that there is a StoreField to this offset in the future, but the |
| // object instance comes from a different Node. We pessimistically |
| // assume that we cannot optimize current_node away. However, we will |
| // record the current StoreField in futureStore, and continue |
| // ascending up the chain. |
| insert_result.first->second = object_input; |
| TRACE("#%d[[+%d]] -- wide, diff object", current_node->id(), offset); |
| } else { |
| // Key was present, and the value equalled object_input. This means |
| // that soon after in the effect chain, we will do a StoreField to the |
| // same object with the same offset, therefore current_node can be |
| // optimized away. We don't need to update futureStore. |
| |
| Node* previous_effect = NodeProperties::GetEffectInput(current_node); |
| |
| NodeProperties::ReplaceUses(current_node, nullptr, previous_effect, |
| nullptr, nullptr); |
| current_node->Kill(); |
| TRACE("#%d[[+%d]] -- wide, eliminated", current_node->id(), offset); |
| } |
| } else { |
| TRACE("#%d[[+%d]] -- narrow, not eliminated", current_node->id(), offset); |
| } |
| |
| // Regardless of whether we eliminated node {current}, we want to |
| // continue walking up the effect chain. |
| |
| current_node = previous; |
| } while (current_node != nullptr && |
| current_node->op()->opcode() == IrOpcode::kStoreField); |
| |
| TRACE("finished"); |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |