blob: e0f4eb7fe218a40b5fc20cda003965da292da7ac [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.
#ifndef V8_COMPILER_LOAD_ELIMINATION_H_
#define V8_COMPILER_LOAD_ELIMINATION_H_
#include "src/base/compiler-specific.h"
#include "src/codegen/machine-type.h"
#include "src/common/globals.h"
#include "src/compiler/graph-reducer.h"
#include "src/compiler/simplified-operator.h"
#include "src/handles/maybe-handles.h"
#include "src/zone/zone-handle-set.h"
namespace v8 {
namespace internal {
// Forward declarations.
class Factory;
namespace compiler {
// Forward declarations.
class CommonOperatorBuilder;
struct FieldAccess;
class Graph;
class JSGraph;
class V8_EXPORT_PRIVATE LoadElimination final
: public NON_EXPORTED_BASE(AdvancedReducer) {
public:
LoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
: AdvancedReducer(editor), node_states_(zone), jsgraph_(jsgraph) {}
~LoadElimination() final = default;
LoadElimination(const LoadElimination&) = delete;
LoadElimination& operator=(const LoadElimination&) = delete;
const char* reducer_name() const override { return "LoadElimination"; }
Reduction Reduce(Node* node) final;
private:
static const size_t kMaxTrackedElements = 8;
// Abstract state to approximate the current state of an element along the
// effect paths through the graph.
class AbstractElements final : public ZoneObject {
public:
explicit AbstractElements(Zone* zone) {
for (size_t i = 0; i < arraysize(elements_); ++i) {
elements_[i] = Element();
}
}
AbstractElements(Node* object, Node* index, Node* value,
MachineRepresentation representation, Zone* zone)
: AbstractElements(zone) {
elements_[next_index_++] = Element(object, index, value, representation);
}
AbstractElements const* Extend(Node* object, Node* index, Node* value,
MachineRepresentation representation,
Zone* zone) const {
AbstractElements* that = zone->New<AbstractElements>(*this);
that->elements_[that->next_index_] =
Element(object, index, value, representation);
that->next_index_ = (that->next_index_ + 1) % arraysize(elements_);
return that;
}
Node* Lookup(Node* object, Node* index,
MachineRepresentation representation) const;
AbstractElements const* Kill(Node* object, Node* index, Zone* zone) const;
bool Equals(AbstractElements const* that) const;
AbstractElements const* Merge(AbstractElements const* that,
Zone* zone) const;
void Print() const;
private:
struct Element {
Element() = default;
Element(Node* object, Node* index, Node* value,
MachineRepresentation representation)
: object(object),
index(index),
value(value),
representation(representation) {}
Node* object = nullptr;
Node* index = nullptr;
Node* value = nullptr;
MachineRepresentation representation = MachineRepresentation::kNone;
};
Element elements_[kMaxTrackedElements];
size_t next_index_ = 0;
};
// Information we use to resolve object aliasing. Currently, we consider
// object not aliased if they have different maps or if the nodes may
// not alias.
class AliasStateInfo;
struct FieldInfo {
FieldInfo() = default;
FieldInfo(Node* value, MachineRepresentation representation,
MaybeHandle<Name> name = {},
ConstFieldInfo const_field_info = ConstFieldInfo::None())
: value(value),
representation(representation),
name(name),
const_field_info(const_field_info) {}
bool operator==(const FieldInfo& other) const {
return value == other.value && representation == other.representation &&
name.address() == other.name.address() &&
const_field_info == other.const_field_info;
}
bool operator!=(const FieldInfo& other) const { return !(*this == other); }
Node* value = nullptr;
MachineRepresentation representation = MachineRepresentation::kNone;
MaybeHandle<Name> name;
ConstFieldInfo const_field_info;
};
// Abstract state to approximate the current state of a certain field along
// the effect paths through the graph.
class AbstractField final : public ZoneObject {
public:
explicit AbstractField(Zone* zone) : info_for_node_(zone) {}
AbstractField(Node* object, FieldInfo info, Zone* zone)
: info_for_node_(zone) {
info_for_node_.insert(std::make_pair(object, info));
}
AbstractField const* Extend(Node* object, FieldInfo info,
Zone* zone) const {
AbstractField* that = zone->New<AbstractField>(zone);
that->info_for_node_ = this->info_for_node_;
that->info_for_node_[object] = info;
return that;
}
FieldInfo const* Lookup(Node* object) const;
AbstractField const* KillConst(Node* object, Zone* zone) const;
AbstractField const* Kill(const AliasStateInfo& alias_info,
MaybeHandle<Name> name, Zone* zone) const;
bool Equals(AbstractField const* that) const {
return this == that || this->info_for_node_ == that->info_for_node_;
}
AbstractField const* Merge(AbstractField const* that, Zone* zone) const {
if (this->Equals(that)) return this;
AbstractField* copy = zone->New<AbstractField>(zone);
for (auto this_it : this->info_for_node_) {
Node* this_object = this_it.first;
FieldInfo this_second = this_it.second;
if (this_object->IsDead()) continue;
auto that_it = that->info_for_node_.find(this_object);
if (that_it != that->info_for_node_.end() &&
that_it->second == this_second) {
copy->info_for_node_.insert(this_it);
}
}
return copy;
}
void Print() const;
private:
ZoneMap<Node*, FieldInfo> info_for_node_;
};
static size_t const kMaxTrackedFields = 32;
// Abstract state to approximate the current map of an object along the
// effect paths through the graph.
class AbstractMaps final : public ZoneObject {
public:
explicit AbstractMaps(Zone* zone);
AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone);
AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps,
Zone* zone) const;
bool Lookup(Node* object, ZoneHandleSet<Map>* object_maps) const;
AbstractMaps const* Kill(const AliasStateInfo& alias_info,
Zone* zone) const;
bool Equals(AbstractMaps const* that) const {
return this == that || this->info_for_node_ == that->info_for_node_;
}
AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const;
void Print() const;
private:
ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_;
};
class IndexRange {
public:
IndexRange(int begin, int size) : begin_(begin), end_(begin + size) {
DCHECK_LE(0, begin);
DCHECK_LE(1, size);
if (end_ > static_cast<int>(kMaxTrackedFields)) {
*this = IndexRange::Invalid();
}
}
static IndexRange Invalid() { return IndexRange(); }
bool operator==(const IndexRange& other) {
return begin_ == other.begin_ && end_ == other.end_;
}
bool operator!=(const IndexRange& other) { return !(*this == other); }
struct Iterator {
int i;
int operator*() { return i; }
void operator++() { ++i; }
bool operator!=(Iterator other) { return i != other.i; }
};
Iterator begin() { return {begin_}; }
Iterator end() { return {end_}; }
private:
int begin_;
int end_;
IndexRange() : begin_(-1), end_(-1) {}
};
class AbstractState final : public ZoneObject {
public:
bool Equals(AbstractState const* that) const;
void Merge(AbstractState const* that, Zone* zone);
AbstractState const* SetMaps(Node* object, ZoneHandleSet<Map> maps,
Zone* zone) const;
AbstractState const* KillMaps(Node* object, Zone* zone) const;
AbstractState const* KillMaps(const AliasStateInfo& alias_info,
Zone* zone) const;
bool LookupMaps(Node* object, ZoneHandleSet<Map>* object_maps) const;
AbstractState const* AddField(Node* object, IndexRange index,
FieldInfo info, Zone* zone) const;
AbstractState const* KillConstField(Node* object, IndexRange index_range,
Zone* zone) const;
AbstractState const* KillField(const AliasStateInfo& alias_info,
IndexRange index, MaybeHandle<Name> name,
Zone* zone) const;
AbstractState const* KillField(Node* object, IndexRange index,
MaybeHandle<Name> name, Zone* zone) const;
AbstractState const* KillFields(Node* object, MaybeHandle<Name> name,
Zone* zone) const;
AbstractState const* KillAll(Zone* zone) const;
FieldInfo const* LookupField(Node* object, IndexRange index,
ConstFieldInfo const_field_info) const;
AbstractState const* AddElement(Node* object, Node* index, Node* value,
MachineRepresentation representation,
Zone* zone) const;
AbstractState const* KillElement(Node* object, Node* index,
Zone* zone) const;
Node* LookupElement(Node* object, Node* index,
MachineRepresentation representation) const;
void Print() const;
static AbstractState const* empty_state() { return &empty_state_; }
private:
static AbstractState const empty_state_;
using AbstractFields = std::array<AbstractField const*, kMaxTrackedFields>;
bool FieldsEquals(AbstractFields const& this_fields,
AbstractFields const& that_fields) const;
void FieldsMerge(AbstractFields* this_fields,
AbstractFields const& that_fields, Zone* zone);
AbstractElements const* elements_ = nullptr;
AbstractFields fields_{};
AbstractFields const_fields_{};
AbstractMaps const* maps_ = nullptr;
};
class AbstractStateForEffectNodes final : public ZoneObject {
public:
explicit AbstractStateForEffectNodes(Zone* zone) : info_for_node_(zone) {}
AbstractState const* Get(Node* node) const;
void Set(Node* node, AbstractState const* state);
Zone* zone() const { return info_for_node_.get_allocator().zone(); }
private:
ZoneVector<AbstractState const*> info_for_node_;
};
Reduction ReduceCheckMaps(Node* node);
Reduction ReduceCompareMaps(Node* node);
Reduction ReduceMapGuard(Node* node);
Reduction ReduceEnsureWritableFastElements(Node* node);
Reduction ReduceMaybeGrowFastElements(Node* node);
Reduction ReduceTransitionElementsKind(Node* node);
Reduction ReduceLoadField(Node* node, FieldAccess const& access);
Reduction ReduceStoreField(Node* node, FieldAccess const& access);
Reduction ReduceLoadElement(Node* node);
Reduction ReduceStoreElement(Node* node);
Reduction ReduceTransitionAndStoreElement(Node* node);
Reduction ReduceStoreTypedElement(Node* node);
Reduction ReduceEffectPhi(Node* node);
Reduction ReduceStart(Node* node);
Reduction ReduceOtherNode(Node* node);
Reduction UpdateState(Node* node, AbstractState const* state);
AbstractState const* ComputeLoopState(Node* node,
AbstractState const* state) const;
AbstractState const* ComputeLoopStateForStoreField(
Node* current, LoadElimination::AbstractState const* state,
FieldAccess const& access) const;
AbstractState const* UpdateStateForPhi(AbstractState const* state,
Node* effect_phi, Node* phi);
static IndexRange FieldIndexOf(int offset, int representation_size);
static IndexRange FieldIndexOf(FieldAccess const& access);
static AbstractState const* empty_state() {
return AbstractState::empty_state();
}
CommonOperatorBuilder* common() const;
Isolate* isolate() const;
Factory* factory() const;
Graph* graph() const;
JSGraph* jsgraph() const { return jsgraph_; }
Zone* zone() const { return node_states_.zone(); }
AbstractStateForEffectNodes node_states_;
JSGraph* const jsgraph_;
};
} // namespace compiler
} // namespace internal
} // namespace v8
#endif // V8_COMPILER_LOAD_ELIMINATION_H_