blob: b71bcd7e669fb80752193b4ebf064a8ff980337e [file] [log] [blame]
// 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 <iterator>
#include "src/compiler/store-store-elimination.h"
#include "src/codegen/tick-counter.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("RedundantStoreFinder: " fmt "\n", ##__VA_ARGS__); \
} \
} while (false)
// CHECK_EXTRA is like CHECK, but has two or more arguments: a boolean
// expression, a format string, and any number of extra arguments. The boolean
// expression will be evaluated at runtime. If it evaluates to false, then an
// error message will be shown containing the condition, as well as the extra
// info formatted like with printf.
#define CHECK_EXTRA(condition, fmt, ...) \
do { \
if (V8_UNLIKELY(!(condition))) { \
FATAL("Check failed: %s. Extra info: " fmt, #condition, ##__VA_ARGS__); \
} \
} while (false)
#ifdef DEBUG
#define DCHECK_EXTRA(condition, fmt, ...) \
CHECK_EXTRA(condition, fmt, ##__VA_ARGS__)
#else
#define DCHECK_EXTRA(condition, fmt, ...) ((void)0)
#endif
// Store-store elimination.
//
// The aim of this optimization is to detect the following pattern in the
// effect graph:
//
// - StoreField[+24, kRepTagged](263, ...)
//
// ... lots of nodes from which the field at offset 24 of the object
// returned by node #263 cannot be observed ...
//
// - StoreField[+24, kRepTagged](263, ...)
//
// In such situations, the earlier StoreField cannot be observed, and can be
// eliminated. This optimization should work for any offset and input node, of
// course.
//
// The optimization also works across splits. It currently does not work for
// loops, because we tend to put a stack check in loops, and like deopts,
// stack checks can observe anything.
// Assumption: every byte of a JS object is only ever accessed through one
// offset. For instance, byte 15 of a given object may be accessed using a
// two-byte read at offset 14, or a four-byte read at offset 12, but never
// both in the same program.
//
// This implementation needs all dead nodes removed from the graph, and the
// graph should be trimmed.
namespace {
using StoreOffset = uint32_t;
struct UnobservableStore {
NodeId id_;
StoreOffset offset_;
bool operator==(const UnobservableStore) const;
bool operator<(const UnobservableStore) const;
};
} // namespace
namespace {
// Instances of UnobservablesSet are immutable. They represent either a set of
// UnobservableStores, or the "unvisited empty set".
//
// We apply some sharing to save memory. The class UnobservablesSet is only a
// pointer wide, and a copy does not use any heap (or temp_zone) memory. Most
// changes to an UnobservablesSet might allocate in the temp_zone.
//
// The size of an instance should be the size of a pointer, plus additional
// space in the zone in the case of non-unvisited UnobservablesSets. Copying
// an UnobservablesSet allocates no memory.
class UnobservablesSet final {
public:
static UnobservablesSet Unvisited();
static UnobservablesSet VisitedEmpty(Zone* zone);
UnobservablesSet(); // unvisited
UnobservablesSet(const UnobservablesSet& other) V8_NOEXCEPT = default;
UnobservablesSet Intersect(const UnobservablesSet& other, Zone* zone) const;
UnobservablesSet Add(UnobservableStore obs, Zone* zone) const;
UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const;
const ZoneSet<UnobservableStore>* set() const { return set_; }
bool IsUnvisited() const { return set_ == nullptr; }
bool IsEmpty() const { return set_ == nullptr || set_->empty(); }
bool Contains(UnobservableStore obs) const {
return set_ != nullptr && (set_->find(obs) != set_->end());
}
bool operator==(const UnobservablesSet&) const;
bool operator!=(const UnobservablesSet&) const;
private:
explicit UnobservablesSet(const ZoneSet<UnobservableStore>* set)
: set_(set) {}
const ZoneSet<UnobservableStore>* set_;
};
} // namespace
namespace {
class RedundantStoreFinder final {
public:
RedundantStoreFinder(JSGraph* js_graph, TickCounter* tick_counter,
Zone* temp_zone);
void Find();
const ZoneSet<Node*>& to_remove_const() { return to_remove_; }
void Visit(Node* node);
private:
void VisitEffectfulNode(Node* node);
UnobservablesSet RecomputeUseIntersection(Node* node);
UnobservablesSet RecomputeSet(Node* node, const UnobservablesSet& uses);
static bool CannotObserveStoreField(Node* node);
void MarkForRevisit(Node* node);
bool HasBeenVisited(Node* node);
JSGraph* jsgraph() const { return jsgraph_; }
Isolate* isolate() { return jsgraph()->isolate(); }
Zone* temp_zone() const { return temp_zone_; }
ZoneVector<UnobservablesSet>& unobservable() { return unobservable_; }
UnobservablesSet& unobservable_for_id(NodeId id) {
DCHECK_LT(id, unobservable().size());
return unobservable()[id];
}
ZoneSet<Node*>& to_remove() { return to_remove_; }
JSGraph* const jsgraph_;
TickCounter* const tick_counter_;
Zone* const temp_zone_;
ZoneStack<Node*> revisit_;
ZoneVector<bool> in_revisit_;
// Maps node IDs to UnobservableNodeSets.
ZoneVector<UnobservablesSet> unobservable_;
ZoneSet<Node*> to_remove_;
const UnobservablesSet unobservables_visited_empty_;
};
// To safely cast an offset from a FieldAccess, which has a potentially wider
// range (namely int).
StoreOffset ToOffset(int offset) {
CHECK_LE(0, offset);
return static_cast<StoreOffset>(offset);
}
StoreOffset ToOffset(const FieldAccess& access) {
return ToOffset(access.offset);
}
unsigned int RepSizeOf(MachineRepresentation rep) {
return 1u << ElementSizeLog2Of(rep);
}
unsigned int RepSizeOf(FieldAccess access) {
return RepSizeOf(access.machine_type.representation());
}
bool AtMostTagged(FieldAccess access) {
return RepSizeOf(access) <= RepSizeOf(MachineRepresentation::kTagged);
}
bool AtLeastTagged(FieldAccess access) {
return RepSizeOf(access) >= RepSizeOf(MachineRepresentation::kTagged);
}
} // namespace
void RedundantStoreFinder::Find() {
Visit(jsgraph()->graph()->end());
while (!revisit_.empty()) {
tick_counter_->DoTick();
Node* next = revisit_.top();
revisit_.pop();
DCHECK_LT(next->id(), in_revisit_.size());
in_revisit_[next->id()] = false;
Visit(next);
}
#ifdef DEBUG
// Check that we visited all the StoreFields
AllNodes all(temp_zone(), jsgraph()->graph());
for (Node* node : all.reachable) {
if (node->op()->opcode() == IrOpcode::kStoreField) {
DCHECK_EXTRA(HasBeenVisited(node), "#%d:%s", node->id(),
node->op()->mnemonic());
}
}
#endif
}
void RedundantStoreFinder::MarkForRevisit(Node* node) {
DCHECK_LT(node->id(), in_revisit_.size());
if (!in_revisit_[node->id()]) {
revisit_.push(node);
in_revisit_[node->id()] = true;
}
}
bool RedundantStoreFinder::HasBeenVisited(Node* node) {
return !unobservable_for_id(node->id()).IsUnvisited();
}
void StoreStoreElimination::Run(JSGraph* js_graph, TickCounter* tick_counter,
Zone* temp_zone) {
// Find superfluous nodes
RedundantStoreFinder finder(js_graph, tick_counter, temp_zone);
finder.Find();
// Remove superfluous nodes
for (Node* node : finder.to_remove_const()) {
if (FLAG_trace_store_elimination) {
PrintF("StoreStoreElimination::Run: Eliminating node #%d:%s\n",
node->id(), node->op()->mnemonic());
}
Node* previous_effect = NodeProperties::GetEffectInput(node);
NodeProperties::ReplaceUses(node, nullptr, previous_effect, nullptr,
nullptr);
node->Kill();
}
}
// Recompute unobservables-set for a node. Will also mark superfluous nodes
// as to be removed.
UnobservablesSet RedundantStoreFinder::RecomputeSet(
Node* node, const UnobservablesSet& uses) {
switch (node->op()->opcode()) {
case IrOpcode::kStoreField: {
Node* stored_to = node->InputAt(0);
const FieldAccess& access = FieldAccessOf(node->op());
StoreOffset offset = ToOffset(access);
UnobservableStore observation = {stored_to->id(), offset};
bool isNotObservable = uses.Contains(observation);
if (isNotObservable && AtMostTagged(access)) {
TRACE(" #%d is StoreField[+%d,%s](#%d), unobservable", node->id(),
offset, MachineReprToString(access.machine_type.representation()),
stored_to->id());
to_remove().insert(node);
return uses;
} else if (isNotObservable && !AtMostTagged(access)) {
TRACE(
" #%d is StoreField[+%d,%s](#%d), repeated in future but too "
"big to optimize away",
node->id(), offset,
MachineReprToString(access.machine_type.representation()),
stored_to->id());
return uses;
} else if (!isNotObservable && AtLeastTagged(access)) {
TRACE(" #%d is StoreField[+%d,%s](#%d), observable, recording in set",
node->id(), offset,
MachineReprToString(access.machine_type.representation()),
stored_to->id());
return uses.Add(observation, temp_zone());
} else if (!isNotObservable && !AtLeastTagged(access)) {
TRACE(
" #%d is StoreField[+%d,%s](#%d), observable but too small to "
"record",
node->id(), offset,
MachineReprToString(access.machine_type.representation()),
stored_to->id());
return uses;
} else {
UNREACHABLE();
}
break;
}
case IrOpcode::kLoadField: {
Node* loaded_from = node->InputAt(0);
const FieldAccess& access = FieldAccessOf(node->op());
StoreOffset offset = ToOffset(access);
TRACE(
" #%d is LoadField[+%d,%s](#%d), removing all offsets [+%d] from "
"set",
node->id(), offset,
MachineReprToString(access.machine_type.representation()),
loaded_from->id(), offset);
return uses.RemoveSameOffset(offset, temp_zone());
break;
}
default:
if (CannotObserveStoreField(node)) {
TRACE(" #%d:%s can observe nothing, set stays unchanged", node->id(),
node->op()->mnemonic());
return uses;
} else {
TRACE(" #%d:%s might observe anything, recording empty set",
node->id(), node->op()->mnemonic());
return unobservables_visited_empty_;
}
}
UNREACHABLE();
}
bool RedundantStoreFinder::CannotObserveStoreField(Node* node) {
return node->opcode() == IrOpcode::kLoadElement ||
node->opcode() == IrOpcode::kLoad ||
node->opcode() == IrOpcode::kStore ||
node->opcode() == IrOpcode::kEffectPhi ||
node->opcode() == IrOpcode::kStoreElement ||
node->opcode() == IrOpcode::kUnsafePointerAdd ||
node->opcode() == IrOpcode::kRetain;
}
// Initialize unobservable_ with js_graph->graph->NodeCount() empty sets.
RedundantStoreFinder::RedundantStoreFinder(JSGraph* js_graph,
TickCounter* tick_counter,
Zone* temp_zone)
: jsgraph_(js_graph),
tick_counter_(tick_counter),
temp_zone_(temp_zone),
revisit_(temp_zone),
in_revisit_(js_graph->graph()->NodeCount(), temp_zone),
unobservable_(js_graph->graph()->NodeCount(),
UnobservablesSet::Unvisited(), temp_zone),
to_remove_(temp_zone),
unobservables_visited_empty_(UnobservablesSet::VisitedEmpty(temp_zone)) {}
void RedundantStoreFinder::Visit(Node* node) {
// All effectful nodes should be reachable from End via a sequence of
// control, then a sequence of effect edges. In VisitEffectfulNode we mark
// all effect inputs for revisiting (if they might have stale state); here
// we mark all control inputs at least once.
if (!HasBeenVisited(node)) {
for (int i = 0; i < node->op()->ControlInputCount(); i++) {
Node* control_input = NodeProperties::GetControlInput(node, i);
if (!HasBeenVisited(control_input)) {
MarkForRevisit(control_input);
}
}
}
bool isEffectful = (node->op()->EffectInputCount() >= 1);
if (isEffectful) {
VisitEffectfulNode(node);
DCHECK(HasBeenVisited(node));
}
if (!HasBeenVisited(node)) {
// Mark as visited.
unobservable_for_id(node->id()) = unobservables_visited_empty_;
}
}
void RedundantStoreFinder::VisitEffectfulNode(Node* node) {
if (HasBeenVisited(node)) {
TRACE("- Revisiting: #%d:%s", node->id(), node->op()->mnemonic());
}
UnobservablesSet after_set = RecomputeUseIntersection(node);
UnobservablesSet before_set = RecomputeSet(node, after_set);
DCHECK(!before_set.IsUnvisited());
UnobservablesSet stored_for_node = unobservable_for_id(node->id());
bool cur_set_changed =
(stored_for_node.IsUnvisited() || stored_for_node != before_set);
if (!cur_set_changed) {
// We will not be able to update the part of this chain above any more.
// Exit.
TRACE("+ No change: stabilized. Not visiting effect inputs.");
} else {
unobservable_for_id(node->id()) = before_set;
// Mark effect inputs for visiting.
for (int i = 0; i < node->op()->EffectInputCount(); i++) {
Node* input = NodeProperties::GetEffectInput(node, i);
TRACE(" marking #%d:%s for revisit", input->id(),
input->op()->mnemonic());
MarkForRevisit(input);
}
}
}
// Compute the intersection of the UnobservablesSets of all effect uses and
// return it. This function only works if {node} has an effect use.
//
// The result UnobservablesSet will always be visited.
UnobservablesSet RedundantStoreFinder::RecomputeUseIntersection(Node* node) {
// {first} == true indicates that we haven't looked at any elements yet.
// {first} == false indicates that cur_set is the intersection of at least one
// thing.
bool first = true;
UnobservablesSet cur_set = UnobservablesSet::Unvisited(); // irrelevant
for (Edge edge : node->use_edges()) {
// Skip non-effect edges
if (!NodeProperties::IsEffectEdge(edge)) {
continue;
}
Node* use = edge.from();
UnobservablesSet new_set = unobservable_for_id(use->id());
// Include new_set in the intersection.
if (first) {
// Intersection of a one-element set is that one element
first = false;
cur_set = new_set;
} else {
// Take the intersection of cur_set and new_set.
cur_set = cur_set.Intersect(new_set, temp_zone());
}
}
if (first) {
// There were no effect uses.
auto opcode = node->op()->opcode();
// List of opcodes that may end this effect chain. The opcodes are not
// important to the soundness of this optimization; this serves as a
// general sanity check. Add opcodes to this list as it suits you.
//
// Everything is observable after these opcodes; return the empty set.
DCHECK_EXTRA(
opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate ||
opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow,
"for #%d:%s", node->id(), node->op()->mnemonic());
USE(opcode); // silence warning about unused variable in release mode
return unobservables_visited_empty_;
} else {
if (cur_set.IsUnvisited()) {
cur_set = unobservables_visited_empty_;
}
return cur_set;
}
}
UnobservablesSet UnobservablesSet::Unvisited() { return UnobservablesSet(); }
UnobservablesSet::UnobservablesSet() : set_(nullptr) {}
UnobservablesSet UnobservablesSet::VisitedEmpty(Zone* zone) {
// Create a new empty UnobservablesSet. This allocates in the zone, and
// can probably be optimized to use a global singleton.
ZoneSet<UnobservableStore>* empty_set =
new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
ZoneSet<UnobservableStore>(zone);
return UnobservablesSet(empty_set);
}
// Computes the intersection of two UnobservablesSets. May return
// UnobservablesSet::Unvisited() instead of an empty UnobservablesSet for
// speed.
UnobservablesSet UnobservablesSet::Intersect(const UnobservablesSet& other,
Zone* zone) const {
if (IsEmpty() || other.IsEmpty()) {
return Unvisited();
} else {
ZoneSet<UnobservableStore>* intersection =
new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
ZoneSet<UnobservableStore>(zone);
// Put the intersection of set() and other.set() in intersection.
set_intersection(set()->begin(), set()->end(), other.set()->begin(),
other.set()->end(),
std::inserter(*intersection, intersection->end()));
return UnobservablesSet(intersection);
}
}
UnobservablesSet UnobservablesSet::Add(UnobservableStore obs,
Zone* zone) const {
bool present = (set()->find(obs) != set()->end());
if (present) {
return *this;
} else {
// Make a new empty set.
ZoneSet<UnobservableStore>* new_set =
new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
ZoneSet<UnobservableStore>(zone);
// Copy the old elements over.
*new_set = *set();
// Add the new element.
bool inserted = new_set->insert(obs).second;
DCHECK(inserted);
USE(inserted); // silence warning about unused variable
return UnobservablesSet(new_set);
}
}
UnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset,
Zone* zone) const {
// Make a new empty set.
ZoneSet<UnobservableStore>* new_set =
new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
ZoneSet<UnobservableStore>(zone);
// Copy all elements over that have a different offset.
for (auto obs : *set()) {
if (obs.offset_ != offset) {
new_set->insert(obs);
}
}
return UnobservablesSet(new_set);
}
// Used for debugging.
bool UnobservablesSet::operator==(const UnobservablesSet& other) const {
if (IsUnvisited() || other.IsUnvisited()) {
return IsEmpty() && other.IsEmpty();
} else {
// Both pointers guaranteed not to be nullptrs.
return *set() == *other.set();
}
}
bool UnobservablesSet::operator!=(const UnobservablesSet& other) const {
return !(*this == other);
}
bool UnobservableStore::operator==(const UnobservableStore other) const {
return (id_ == other.id_) && (offset_ == other.offset_);
}
bool UnobservableStore::operator<(const UnobservableStore other) const {
return (id_ < other.id_) || (id_ == other.id_ && offset_ < other.offset_);
}
#undef TRACE
#undef CHECK_EXTRA
#undef DCHECK_EXTRA
} // namespace compiler
} // namespace internal
} // namespace v8