113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// Copyright 2016 the V8 project authors. All rights reserved. 213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// Use of this source code is governed by a BSD-style license that can be 313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// found in the LICENSE file. 413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 5f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#include <iterator> 6f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch#include "src/compiler/store-store-elimination.h" 813e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch#include "src/compiler/all-nodes.h" 1013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch#include "src/compiler/js-graph.h" 1113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch#include "src/compiler/node-properties.h" 1213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch#include "src/compiler/simplified-operator.h" 1313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 1413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdochnamespace v8 { 1513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdochnamespace internal { 1613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdochnamespace compiler { 1713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 18f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#define TRACE(fmt, ...) \ 19f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch do { \ 20f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (FLAG_trace_store_elimination) { \ 21f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch PrintF("RedundantStoreFinder: " fmt "\n", ##__VA_ARGS__); \ 22f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } \ 2313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } while (false) 2413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 25f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// CHECK_EXTRA is like CHECK, but has two or more arguments: a boolean 26f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// expression, a format string, and any number of extra arguments. The boolean 27f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// expression will be evaluated at runtime. If it evaluates to false, then an 28f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// error message will be shown containing the condition, as well as the extra 29f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// info formatted like with printf. 30f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#define CHECK_EXTRA(condition, fmt, ...) \ 31f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch do { \ 32f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (V8_UNLIKELY(!(condition))) { \ 33f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch V8_Fatal(__FILE__, __LINE__, "Check failed: %s. Extra info: " fmt, \ 34f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch #condition, ##__VA_ARGS__); \ 35f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } \ 36f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } while (0) 37f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 38f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#ifdef DEBUG 39f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#define DCHECK_EXTRA(condition, fmt, ...) \ 40f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch CHECK_EXTRA(condition, fmt, ##__VA_ARGS__) 41f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#else 42f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#define DCHECK_EXTRA(condition, fmt, ...) ((void)0) 43f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#endif 44f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 45f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Store-store elimination. 4613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 47f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// The aim of this optimization is to detect the following pattern in the 48f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// effect graph: 4913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 50f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// - StoreField[+24, kRepTagged](263, ...) 5113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 52f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// ... lots of nodes from which the field at offset 24 of the object 53f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// returned by node #263 cannot be observed ... 5413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 55f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// - StoreField[+24, kRepTagged](263, ...) 5613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 57f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// In such situations, the earlier StoreField cannot be observed, and can be 58f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// eliminated. This optimization should work for any offset and input node, of 59f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// course. 6013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 61f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// The optimization also works across splits. It currently does not work for 62f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// loops, because we tend to put a stack check in loops, and like deopts, 63f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// stack checks can observe anything. 64f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 65f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Assumption: every byte of a JS object is only ever accessed through one 66f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// offset. For instance, byte 15 of a given object may be accessed using a 67f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// two-byte read at offset 14, or a four-byte read at offset 12, but never 68f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// both in the same program. 6913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 70f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// This implementation needs all dead nodes removed from the graph, and the 71f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// graph should be trimmed. 72f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 73f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochnamespace { 74f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 75f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdochtypedef uint32_t StoreOffset; 76f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 77f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochstruct UnobservableStore { 78f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch NodeId id_; 79f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch StoreOffset offset_; 80f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 81f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool operator==(const UnobservableStore) const; 82f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool operator!=(const UnobservableStore) const; 83f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool operator<(const UnobservableStore) const; 84f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch}; 85f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 86f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} // namespace 87f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 88f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochnamespace { 89f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 90f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Instances of UnobservablesSet are immutable. They represent either a set of 91f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// UnobservableStores, or the "unvisited empty set". 9213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 93f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// We apply some sharing to save memory. The class UnobservablesSet is only a 94f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// pointer wide, and a copy does not use any heap (or temp_zone) memory. Most 95f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// changes to an UnobservablesSet might allocate in the temp_zone. 9613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch// 97f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// The size of an instance should be the size of a pointer, plus additional 98f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// space in the zone in the case of non-unvisited UnobservablesSets. Copying 99f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// an UnobservablesSet allocates no memory. 100f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochclass UnobservablesSet final { 101f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch public: 102f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch static UnobservablesSet Unvisited(); 103f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch static UnobservablesSet VisitedEmpty(Zone* zone); 104f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet(); // unvisited 105f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet(const UnobservablesSet& other) : set_(other.set_) {} 106f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 107f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet Intersect(UnobservablesSet other, Zone* zone) const; 108f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet Add(UnobservableStore obs, Zone* zone) const; 109f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const; 110f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 111f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch const ZoneSet<UnobservableStore>* set() const { return set_; } 112f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 113f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool IsUnvisited() const { return set_ == nullptr; } 114f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool IsEmpty() const { return set_ == nullptr || set_->empty(); } 115f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool Contains(UnobservableStore obs) const { 116f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return set_ != nullptr && (set_->find(obs) != set_->end()); 117f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 118f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 119f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool operator==(const UnobservablesSet&) const; 120f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool operator!=(const UnobservablesSet&) const; 121f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 122f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch private: 123f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch explicit UnobservablesSet(const ZoneSet<UnobservableStore>* set) 124f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch : set_(set) {} 125f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch const ZoneSet<UnobservableStore>* set_; 126f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch}; 127f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 128f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} // namespace 129f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 130f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochnamespace { 131f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 132f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochclass RedundantStoreFinder final { 133f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch public: 134f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch RedundantStoreFinder(JSGraph* js_graph, Zone* temp_zone); 135f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 136f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch void Find(); 137f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 138f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch const ZoneSet<Node*>& to_remove_const() { return to_remove_; } 139f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 140f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch void Visit(Node* node); 141f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 142f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch private: 143f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch static bool IsEffectful(Node* node); 144f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch void VisitEffectfulNode(Node* node); 145f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet RecomputeUseIntersection(Node* node); 146f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet RecomputeSet(Node* node, UnobservablesSet uses); 147f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch static bool CannotObserveStoreField(Node* node); 148f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 149f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch void MarkForRevisit(Node* node); 150f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool HasBeenVisited(Node* node); 151f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 152f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch JSGraph* jsgraph() const { return jsgraph_; } 153f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Zone* temp_zone() const { return temp_zone_; } 154f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneVector<UnobservablesSet>& unobservable() { return unobservable_; } 155f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet& unobservable_for_id(NodeId id) { 156f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK_LT(id, unobservable().size()); 157f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return unobservable()[id]; 158f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 159f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<Node*>& to_remove() { return to_remove_; } 160f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 161f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch JSGraph* const jsgraph_; 162f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Zone* const temp_zone_; 163f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 164f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneStack<Node*> revisit_; 165f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneVector<bool> in_revisit_; 166f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Maps node IDs to UnobservableNodeSets. 167f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneVector<UnobservablesSet> unobservable_; 168f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<Node*> to_remove_; 169f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch const UnobservablesSet unobservables_visited_empty_; 170f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch}; 171f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 172f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch// To safely cast an offset from a FieldAccess, which has a potentially wider 173f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch// range (namely int). 174f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochStoreOffset ToOffset(int offset) { 175f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch CHECK(0 <= offset); 176f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch return static_cast<StoreOffset>(offset); 177f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 178f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 179f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochStoreOffset ToOffset(const FieldAccess& access) { 180f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return ToOffset(access.offset); 181f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 182f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 183f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochunsigned int RepSizeOf(MachineRepresentation rep) { 184f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return 1u << ElementSizeLog2Of(rep); 185f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 186f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochunsigned int RepSizeOf(FieldAccess access) { 187f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return RepSizeOf(access.machine_type.representation()); 188f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 189f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 190f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool AtMostTagged(FieldAccess access) { 191f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return RepSizeOf(access) <= RepSizeOf(MachineRepresentation::kTagged); 192f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 193f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 194f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool AtLeastTagged(FieldAccess access) { 195f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return RepSizeOf(access) >= RepSizeOf(MachineRepresentation::kTagged); 196f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 197f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 198f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} // namespace 199f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 200f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochvoid RedundantStoreFinder::Find() { 201f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Visit(jsgraph()->graph()->end()); 202f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 203f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch while (!revisit_.empty()) { 204f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Node* next = revisit_.top(); 205f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch revisit_.pop(); 206f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK_LT(next->id(), in_revisit_.size()); 207f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch in_revisit_[next->id()] = false; 208f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Visit(next); 209f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 210f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 211f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#ifdef DEBUG 212f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Check that we visited all the StoreFields 21313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch AllNodes all(temp_zone(), jsgraph()->graph()); 214f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch for (Node* node : all.reachable) { 215f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (node->op()->opcode() == IrOpcode::kStoreField) { 216f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK_EXTRA(HasBeenVisited(node), "#%d:%s", node->id(), 217f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->op()->mnemonic()); 218f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 219f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 220f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch#endif 221f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 222f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 223f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochvoid RedundantStoreFinder::MarkForRevisit(Node* node) { 224f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK_LT(node->id(), in_revisit_.size()); 225f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (!in_revisit_[node->id()]) { 226f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch revisit_.push(node); 227f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch in_revisit_[node->id()] = true; 228f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 229f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 230f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 231f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool RedundantStoreFinder::HasBeenVisited(Node* node) { 232f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return !unobservable_for_id(node->id()).IsUnvisited(); 233f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 23413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 235f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochvoid StoreStoreElimination::Run(JSGraph* js_graph, Zone* temp_zone) { 236f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Find superfluous nodes 237f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch RedundantStoreFinder finder(js_graph, temp_zone); 238f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch finder.Find(); 239f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 240f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Remove superfluous nodes 241f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 242f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch for (Node* node : finder.to_remove_const()) { 243f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (FLAG_trace_store_elimination) { 244f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch PrintF("StoreStoreElimination::Run: Eliminating node #%d:%s\n", 245f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->id(), node->op()->mnemonic()); 24613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 247f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Node* previous_effect = NodeProperties::GetEffectInput(node); 248f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch NodeProperties::ReplaceUses(node, nullptr, previous_effect, nullptr, 249f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch nullptr); 250f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->Kill(); 25113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 252f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 253f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 254f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool RedundantStoreFinder::IsEffectful(Node* node) { 255f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return (node->op()->EffectInputCount() >= 1); 256f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 25713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 258f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Recompute unobservables-set for a node. Will also mark superfluous nodes 259f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// as to be removed. 260f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 261f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet RedundantStoreFinder::RecomputeSet(Node* node, 262f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet uses) { 263f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch switch (node->op()->opcode()) { 264f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch case IrOpcode::kStoreField: { 265f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Node* stored_to = node->InputAt(0); 266f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch FieldAccess access = OpParameter<FieldAccess>(node->op()); 267f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch StoreOffset offset = ToOffset(access); 268f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 269f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservableStore observation = {stored_to->id(), offset}; 270f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool isNotObservable = uses.Contains(observation); 271f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 272f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (isNotObservable && AtMostTagged(access)) { 273f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE(" #%d is StoreField[+%d,%s](#%d), unobservable", node->id(), 274f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch offset, MachineReprToString(access.machine_type.representation()), 275f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch stored_to->id()); 276f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch to_remove().insert(node); 277f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return uses; 278f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else if (isNotObservable && !AtMostTagged(access)) { 279f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE( 280f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch " #%d is StoreField[+%d,%s](#%d), repeated in future but too " 281f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch "big to optimize away", 282f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->id(), offset, 283f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch MachineReprToString(access.machine_type.representation()), 284f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch stored_to->id()); 285f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return uses; 286f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else if (!isNotObservable && AtLeastTagged(access)) { 287f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE(" #%d is StoreField[+%d,%s](#%d), observable, recording in set", 288f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->id(), offset, 289f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch MachineReprToString(access.machine_type.representation()), 290f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch stored_to->id()); 291f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return uses.Add(observation, temp_zone()); 292f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else if (!isNotObservable && !AtLeastTagged(access)) { 293f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE( 294f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch " #%d is StoreField[+%d,%s](#%d), observable but too small to " 295f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch "record", 296f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->id(), offset, 297f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch MachineReprToString(access.machine_type.representation()), 298f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch stored_to->id()); 299f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return uses; 300f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else { 301f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UNREACHABLE(); 302f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 303f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch break; 304f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 305f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch case IrOpcode::kLoadField: { 306f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Node* loaded_from = node->InputAt(0); 307f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch FieldAccess access = OpParameter<FieldAccess>(node->op()); 308f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch StoreOffset offset = ToOffset(access); 309f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 310f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE( 311f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch " #%d is LoadField[+%d,%s](#%d), removing all offsets [+%d] from " 312f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch "set", 313f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->id(), offset, 314f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch MachineReprToString(access.machine_type.representation()), 315f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch loaded_from->id(), offset); 316f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 317f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return uses.RemoveSameOffset(offset, temp_zone()); 318f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch break; 319f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 320f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch default: 321f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (CannotObserveStoreField(node)) { 322f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE(" #%d:%s can observe nothing, set stays unchanged", node->id(), 323f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->op()->mnemonic()); 324f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return uses; 325f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else { 326f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE(" #%d:%s might observe anything, recording empty set", 327f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->id(), node->op()->mnemonic()); 328f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return unobservables_visited_empty_; 329f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 33013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 331f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UNREACHABLE(); 332f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return UnobservablesSet::Unvisited(); 33313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 33413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 335f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool RedundantStoreFinder::CannotObserveStoreField(Node* node) { 336f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return node->opcode() == IrOpcode::kCheckedLoad || 337f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kLoadElement || 338f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kLoad || 339f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kStore || 340f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kEffectPhi || 341f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kStoreElement || 342f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kCheckedStore || 343f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kUnsafePointerAdd || 344f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch node->opcode() == IrOpcode::kRetain; 345f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 34613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 347f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Initialize unobservable_ with js_graph->graph->NodeCount() empty sets. 348f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochRedundantStoreFinder::RedundantStoreFinder(JSGraph* js_graph, Zone* temp_zone) 349f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch : jsgraph_(js_graph), 350f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch temp_zone_(temp_zone), 351f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch revisit_(temp_zone), 352f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch in_revisit_(js_graph->graph()->NodeCount(), temp_zone), 353f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch unobservable_(js_graph->graph()->NodeCount(), 354f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet::Unvisited(), temp_zone), 355f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch to_remove_(temp_zone), 356f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch unobservables_visited_empty_(UnobservablesSet::VisitedEmpty(temp_zone)) {} 357f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 358f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochvoid RedundantStoreFinder::Visit(Node* node) { 359f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // All effectful nodes should be reachable from End via a sequence of 360f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // control, then a sequence of effect edges. In VisitEffectfulNode we mark 361f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // all effect inputs for revisiting (if they might have stale state); here 362f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // we mark all control inputs at least once. 363f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 364f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (!HasBeenVisited(node)) { 365f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch for (int i = 0; i < node->op()->ControlInputCount(); i++) { 366f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Node* control_input = NodeProperties::GetControlInput(node, i); 367f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (!HasBeenVisited(control_input)) { 368f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch MarkForRevisit(control_input); 369f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 370f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 371f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 37213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 373f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool isEffectful = (node->op()->EffectInputCount() >= 1); 374f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (isEffectful) { 375f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch VisitEffectfulNode(node); 376f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK(HasBeenVisited(node)); 377f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 378f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 379f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (!HasBeenVisited(node)) { 380f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Mark as visited. 381f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch unobservable_for_id(node->id()) = unobservables_visited_empty_; 382f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 38313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 38413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 385f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochvoid RedundantStoreFinder::VisitEffectfulNode(Node* node) { 386f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (HasBeenVisited(node)) { 387f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE("- Revisiting: #%d:%s", node->id(), node->op()->mnemonic()); 388f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 389f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet after_set = RecomputeUseIntersection(node); 390f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet before_set = RecomputeSet(node, after_set); 391f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK(!before_set.IsUnvisited()); 392f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 393f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet stored_for_node = unobservable_for_id(node->id()); 394f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool cur_set_changed = 395f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch (stored_for_node.IsUnvisited() || stored_for_node != before_set); 396f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (!cur_set_changed) { 397f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // We will not be able to update the part of this chain above any more. 398f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Exit. 399f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch TRACE("+ No change: stabilized. Not visiting effect inputs."); 400f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else { 401f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch unobservable_for_id(node->id()) = before_set; 402f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 403f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Mark effect inputs for visiting. 404f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch for (int i = 0; i < node->op()->EffectInputCount(); i++) { 405f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Node* input = NodeProperties::GetEffectInput(node, i); 406f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch TRACE(" marking #%d:%s for revisit", input->id(), 407f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch input->op()->mnemonic()); 408f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch MarkForRevisit(input); 409f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 410f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 411f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 412f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 413f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Compute the intersection of the UnobservablesSets of all effect uses and 414f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// return it. This function only works if {node} has an effect use. 415f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// 416f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// The result UnobservablesSet will always be visited. 417f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet RedundantStoreFinder::RecomputeUseIntersection(Node* node) { 418f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // {first} == true indicates that we haven't looked at any elements yet. 419f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // {first} == false indicates that cur_set is the intersection of at least one 420f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // thing. 421f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 422f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool first = true; 423f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet cur_set = UnobservablesSet::Unvisited(); // irrelevant 42413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 42513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch for (Edge edge : node->use_edges()) { 426f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Skip non-effect edges 42713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch if (!NodeProperties::IsEffectEdge(edge)) { 42813e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch continue; 42913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 430f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 431f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Node* use = edge.from(); 432f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch UnobservablesSet new_set = unobservable_for_id(use->id()); 433f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Include new_set in the intersection. 434f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (first) { 435f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Intersection of a one-element set is that one element 436f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch first = false; 437f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch cur_set = new_set; 438f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else { 439f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Take the intersection of cur_set and new_set. 440f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch cur_set = cur_set.Intersect(new_set, temp_zone()); 44113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 44213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 443f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 444f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (first) { 445f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // There were no effect uses. 446f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch auto opcode = node->op()->opcode(); 447f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // List of opcodes that may end this effect chain. The opcodes are not 448f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // important to the soundness of this optimization; this serves as a 449f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // general sanity check. Add opcodes to this list as it suits you. 450f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // 451f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Everything is observable after these opcodes; return the empty set. 452f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK_EXTRA( 453f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate || 454f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow, 455f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch "for #%d:%s", node->id(), node->op()->mnemonic()); 456f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch USE(opcode); // silence warning about unused variable in release mode 457f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 458f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return unobservables_visited_empty_; 459f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else { 460f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (cur_set.IsUnvisited()) { 461f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch cur_set = unobservables_visited_empty_; 462f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 463f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 464f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return cur_set; 465f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 46613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 46713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 468f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet UnobservablesSet::Unvisited() { return UnobservablesSet(); } 469f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 470f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet::UnobservablesSet() : set_(nullptr) {} 471f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 472f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) { 473f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Create a new empty UnobservablesSet. This allocates in the zone, and 474f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // can probably be optimized to use a global singleton. 475f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>* empty_set = 476f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 477f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>(zone); 478f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return UnobservablesSet(empty_set); 47913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 48013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 481f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Computes the intersection of two UnobservablesSets. May return 482f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// UnobservablesSet::Unvisited() instead of an empty UnobservablesSet for 483f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// speed. 484f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet UnobservablesSet::Intersect(UnobservablesSet other, 485f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Zone* zone) const { 486f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (IsEmpty() || other.IsEmpty()) { 487f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return Unvisited(); 48813e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } else { 489f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>* intersection = 490f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 491f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>(zone); 492f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Put the intersection of set() and other.set() in intersection. 493f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch set_intersection(set()->begin(), set()->end(), other.set()->begin(), 494f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch other.set()->end(), 495f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch std::inserter(*intersection, intersection->end())); 496f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 497f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return UnobservablesSet(intersection); 49813e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch } 49913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 50013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 501f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet UnobservablesSet::Add(UnobservableStore obs, 502f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Zone* zone) const { 503f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool present = (set()->find(obs) != set()->end()); 504f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (present) { 505f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return *this; 506f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else { 507f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Make a new empty set. 508f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>* new_set = 509f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 510f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>(zone); 511f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Copy the old elements over. 512f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch *new_set = *set(); 513f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Add the new element. 514f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch bool inserted = new_set->insert(obs).second; 515f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch DCHECK(inserted); 516f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch USE(inserted); // silence warning about unused variable 517f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch 518f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return UnobservablesSet(new_set); 519f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 52013e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 52113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 522f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen MurdochUnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset, 523f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch Zone* zone) const { 524f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Make a new empty set. 525f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>* new_set = 526f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch new (zone->New(sizeof(ZoneSet<UnobservableStore>))) 527f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch ZoneSet<UnobservableStore>(zone); 528f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Copy all elements over that have a different offset. 529f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch for (auto obs : *set()) { 530f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (obs.offset_ != offset) { 531f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch new_set->insert(obs); 532f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 533f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 53413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 535f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return UnobservablesSet(new_set); 53613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 53713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 538f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch// Used for debugging. 539f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool UnobservablesSet::operator==(const UnobservablesSet& other) const { 540f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch if (IsUnvisited() || other.IsUnvisited()) { 541f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return IsEmpty() && other.IsEmpty(); 542f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } else { 543f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch // Both pointers guaranteed not to be nullptrs. 544f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return *set() == *other.set(); 545f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch } 546f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 54713e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 548f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool UnobservablesSet::operator!=(const UnobservablesSet& other) const { 549f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return !(*this == other); 550f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 55113e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 552f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool UnobservableStore::operator==(const UnobservableStore other) const { 553f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return (id_ == other.id_) && (offset_ == other.offset_); 554f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 55513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 556f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool UnobservableStore::operator!=(const UnobservableStore other) const { 557f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return !(*this == other); 558f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch} 55913e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 560f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdochbool UnobservableStore::operator<(const UnobservableStore other) const { 561f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch return (id_ < other.id_) || (id_ == other.id_ && offset_ < other.offset_); 56213e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} 56313e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch 56413e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} // namespace compiler 56513e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} // namespace internal 56613e2dadd00298019ed862f2b2fc5068bba730bcfBen Murdoch} // namespace v8 567