blob: 9b401bcf43f7861ac2b2c9d6ed5661f8fe7c7b86 [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 "src/compiler/redundancy-elimination.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/simplified-operator.h"
namespace v8 {
namespace internal {
namespace compiler {
RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
: AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
RedundancyElimination::~RedundancyElimination() = default;
Reduction RedundancyElimination::Reduce(Node* node) {
if (node_checks_.Get(node)) return NoChange();
switch (node->opcode()) {
case IrOpcode::kCheckBigInt:
case IrOpcode::kCheckBounds:
case IrOpcode::kCheckEqualsInternalizedString:
case IrOpcode::kCheckEqualsSymbol:
case IrOpcode::kCheckFloat64Hole:
case IrOpcode::kCheckHeapObject:
case IrOpcode::kCheckIf:
case IrOpcode::kCheckInternalizedString:
case IrOpcode::kCheckNotTaggedHole:
case IrOpcode::kCheckNumber:
case IrOpcode::kCheckReceiver:
case IrOpcode::kCheckReceiverOrNullOrUndefined:
case IrOpcode::kCheckSmi:
case IrOpcode::kCheckString:
case IrOpcode::kCheckSymbol:
#define SIMPLIFIED_CHECKED_OP(Opcode) case IrOpcode::k##Opcode:
SIMPLIFIED_CHECKED_OP_LIST(SIMPLIFIED_CHECKED_OP)
#undef SIMPLIFIED_CHECKED_OP
return ReduceCheckNode(node);
case IrOpcode::kSpeculativeNumberEqual:
case IrOpcode::kSpeculativeNumberLessThan:
case IrOpcode::kSpeculativeNumberLessThanOrEqual:
return ReduceSpeculativeNumberComparison(node);
case IrOpcode::kSpeculativeNumberAdd:
case IrOpcode::kSpeculativeNumberSubtract:
case IrOpcode::kSpeculativeSafeIntegerAdd:
case IrOpcode::kSpeculativeSafeIntegerSubtract:
case IrOpcode::kSpeculativeToNumber:
return ReduceSpeculativeNumberOperation(node);
case IrOpcode::kEffectPhi:
return ReduceEffectPhi(node);
case IrOpcode::kDead:
break;
case IrOpcode::kStart:
return ReduceStart(node);
default:
return ReduceOtherNode(node);
}
return NoChange();
}
// static
RedundancyElimination::EffectPathChecks*
RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
EffectPathChecks const* checks) {
return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
}
// static
RedundancyElimination::EffectPathChecks const*
RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
}
bool RedundancyElimination::EffectPathChecks::Equals(
EffectPathChecks const* that) const {
if (this->size_ != that->size_) return false;
Check* this_head = this->head_;
Check* that_head = that->head_;
while (this_head != that_head) {
if (this_head->node != that_head->node) return false;
this_head = this_head->next;
that_head = that_head->next;
}
return true;
}
void RedundancyElimination::EffectPathChecks::Merge(
EffectPathChecks const* that) {
// Change the current check list to a longest common tail of this check
// list and the other list.
// First, we throw away the prefix of the longer list, so that
// we have lists of the same length.
Check* that_head = that->head_;
size_t that_size = that->size_;
while (that_size > size_) {
that_head = that_head->next;
that_size--;
}
while (size_ > that_size) {
head_ = head_->next;
size_--;
}
// Then we go through both lists in lock-step until we find
// the common tail.
while (head_ != that_head) {
DCHECK_LT(0u, size_);
DCHECK_NOT_NULL(head_);
size_--;
head_ = head_->next;
that_head = that_head->next;
}
}
RedundancyElimination::EffectPathChecks const*
RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
Node* node) const {
Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
return new (zone->New(sizeof(EffectPathChecks)))
EffectPathChecks(head, size_ + 1);
}
namespace {
// Does check {a} subsume check {b}?
bool CheckSubsumes(Node const* a, Node const* b) {
if (a->op() != b->op()) {
if (a->opcode() == IrOpcode::kCheckInternalizedString &&
b->opcode() == IrOpcode::kCheckString) {
// CheckInternalizedString(node) implies CheckString(node)
} else if (a->opcode() == IrOpcode::kCheckSmi &&
b->opcode() == IrOpcode::kCheckNumber) {
// CheckSmi(node) implies CheckNumber(node)
} else if (a->opcode() == IrOpcode::kCheckedTaggedSignedToInt32 &&
b->opcode() == IrOpcode::kCheckedTaggedToInt32) {
// CheckedTaggedSignedToInt32(node) implies CheckedTaggedToInt32(node)
} else if (a->opcode() == IrOpcode::kCheckReceiver &&
b->opcode() == IrOpcode::kCheckReceiverOrNullOrUndefined) {
// CheckReceiver(node) implies CheckReceiverOrNullOrUndefined(node)
} else if (a->opcode() != b->opcode()) {
return false;
} else {
switch (a->opcode()) {
case IrOpcode::kCheckBounds:
case IrOpcode::kCheckSmi:
case IrOpcode::kCheckString:
case IrOpcode::kCheckNumber:
case IrOpcode::kCheckBigInt:
break;
case IrOpcode::kCheckedInt32ToCompressedSigned:
case IrOpcode::kCheckedInt32ToTaggedSigned:
case IrOpcode::kCheckedInt64ToInt32:
case IrOpcode::kCheckedInt64ToTaggedSigned:
case IrOpcode::kCheckedTaggedSignedToInt32:
case IrOpcode::kCheckedTaggedToTaggedPointer:
case IrOpcode::kCheckedTaggedToTaggedSigned:
case IrOpcode::kCheckedCompressedToTaggedPointer:
case IrOpcode::kCheckedCompressedToTaggedSigned:
case IrOpcode::kCheckedTaggedToCompressedPointer:
case IrOpcode::kCheckedTaggedToCompressedSigned:
case IrOpcode::kCheckedUint32Bounds:
case IrOpcode::kCheckedUint32ToInt32:
case IrOpcode::kCheckedUint32ToTaggedSigned:
case IrOpcode::kCheckedUint64Bounds:
case IrOpcode::kCheckedUint64ToInt32:
case IrOpcode::kCheckedUint64ToTaggedSigned:
break;
case IrOpcode::kCheckedFloat64ToInt32:
case IrOpcode::kCheckedFloat64ToInt64:
case IrOpcode::kCheckedTaggedToInt32:
case IrOpcode::kCheckedTaggedToInt64: {
const CheckMinusZeroParameters& ap =
CheckMinusZeroParametersOf(a->op());
const CheckMinusZeroParameters& bp =
CheckMinusZeroParametersOf(b->op());
if (ap.mode() != bp.mode()) {
return false;
}
break;
}
case IrOpcode::kCheckedTaggedToFloat64:
case IrOpcode::kCheckedTruncateTaggedToWord32: {
CheckTaggedInputParameters const& ap =
CheckTaggedInputParametersOf(a->op());
CheckTaggedInputParameters const& bp =
CheckTaggedInputParametersOf(b->op());
// {a} subsumes {b} if the modes are either the same, or {a} checks
// for Number, in which case {b} will be subsumed no matter what.
if (ap.mode() != bp.mode() &&
ap.mode() != CheckTaggedInputMode::kNumber) {
return false;
}
break;
}
default:
DCHECK(!IsCheckedWithFeedback(a->op()));
return false;
}
}
}
for (int i = a->op()->ValueInputCount(); --i >= 0;) {
if (a->InputAt(i) != b->InputAt(i)) return false;
}
return true;
}
bool TypeSubsumes(Node* node, Node* replacement) {
if (!NodeProperties::IsTyped(node) || !NodeProperties::IsTyped(replacement)) {
// If either node is untyped, we are running during an untyped optimization
// phase, and replacement is OK.
return true;
}
Type node_type = NodeProperties::GetType(node);
Type replacement_type = NodeProperties::GetType(replacement);
return replacement_type.Is(node_type);
}
} // namespace
Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
for (Check const* check = head_; check != nullptr; check = check->next) {
if (CheckSubsumes(check->node, node) && TypeSubsumes(node, check->node)) {
DCHECK(!check->node->IsDead());
return check->node;
}
}
return nullptr;
}
Node* RedundancyElimination::EffectPathChecks::LookupBoundsCheckFor(
Node* node) const {
for (Check const* check = head_; check != nullptr; check = check->next) {
if (check->node->opcode() == IrOpcode::kCheckBounds &&
check->node->InputAt(0) == node) {
return check->node;
}
}
return nullptr;
}
RedundancyElimination::EffectPathChecks const*
RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
size_t const id = node->id();
if (id < info_for_node_.size()) return info_for_node_[id];
return nullptr;
}
void RedundancyElimination::PathChecksForEffectNodes::Set(
Node* node, EffectPathChecks const* checks) {
size_t const id = node->id();
if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
info_for_node_[id] = checks;
}
Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
Node* const effect = NodeProperties::GetEffectInput(node);
EffectPathChecks const* checks = node_checks_.Get(effect);
// If we do not know anything about the predecessor, do not propagate just yet
// because we will have to recompute anyway once we compute the predecessor.
if (checks == nullptr) return NoChange();
// See if we have another check that dominates us.
if (Node* check = checks->LookupCheck(node)) {
ReplaceWithValue(node, check);
return Replace(check);
}
// Learn from this check.
return UpdateChecks(node, checks->AddCheck(zone(), node));
}
Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
Node* const control = NodeProperties::GetControlInput(node);
if (control->opcode() == IrOpcode::kLoop) {
// Here we rely on having only reducible loops:
// The loop entry edge always dominates the header, so we can just use
// the information from the loop entry edge.
return TakeChecksFromFirstEffect(node);
}
DCHECK_EQ(IrOpcode::kMerge, control->opcode());
// Shortcut for the case when we do not know anything about some input.
int const input_count = node->op()->EffectInputCount();
for (int i = 0; i < input_count; ++i) {
Node* const effect = NodeProperties::GetEffectInput(node, i);
if (node_checks_.Get(effect) == nullptr) return NoChange();
}
// Make a copy of the first input's checks and merge with the checks
// from other inputs.
EffectPathChecks* checks = EffectPathChecks::Copy(
zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
for (int i = 1; i < input_count; ++i) {
Node* const input = NodeProperties::GetEffectInput(node, i);
checks->Merge(node_checks_.Get(input));
}
return UpdateChecks(node, checks);
}
Reduction RedundancyElimination::ReduceSpeculativeNumberComparison(Node* node) {
NumberOperationHint const hint = NumberOperationHintOf(node->op());
Node* const first = NodeProperties::GetValueInput(node, 0);
Type const first_type = NodeProperties::GetType(first);
Node* const second = NodeProperties::GetValueInput(node, 1);
Type const second_type = NodeProperties::GetType(second);
Node* const effect = NodeProperties::GetEffectInput(node);
EffectPathChecks const* checks = node_checks_.Get(effect);
// If we do not know anything about the predecessor, do not propagate just yet
// because we will have to recompute anyway once we compute the predecessor.
if (checks == nullptr) return NoChange();
// Avoid the potentially expensive lookups below if the {node}
// has seen non-Smi inputs in the past, which is a clear signal
// that the comparison is probably not performed on a value that
// already passed an array bounds check.
if (hint == NumberOperationHint::kSignedSmall) {
// Don't bother trying to find a CheckBounds for the {first} input
// if it's type is already in UnsignedSmall range, since the bounds
// check is only going to narrow that range further, but the result
// is not going to make the representation selection any better.
if (!first_type.Is(Type::UnsignedSmall())) {
if (Node* check = checks->LookupBoundsCheckFor(first)) {
if (!first_type.Is(NodeProperties::GetType(check))) {
// Replace the {first} input with the {check}. This is safe,
// despite the fact that {check} can truncate -0 to 0, because
// the regular Number comparisons in JavaScript also identify
// 0 and -0 (unlike special comparisons as Object.is).
NodeProperties::ReplaceValueInput(node, check, 0);
Reduction const reduction = ReduceSpeculativeNumberComparison(node);
return reduction.Changed() ? reduction : Changed(node);
}
}
}
// Don't bother trying to find a CheckBounds for the {second} input
// if it's type is already in UnsignedSmall range, since the bounds
// check is only going to narrow that range further, but the result
// is not going to make the representation selection any better.
if (!second_type.Is(Type::UnsignedSmall())) {
if (Node* check = checks->LookupBoundsCheckFor(second)) {
if (!second_type.Is(NodeProperties::GetType(check))) {
// Replace the {second} input with the {check}. This is safe,
// despite the fact that {check} can truncate -0 to 0, because
// the regular Number comparisons in JavaScript also identify
// 0 and -0 (unlike special comparisons as Object.is).
NodeProperties::ReplaceValueInput(node, check, 1);
Reduction const reduction = ReduceSpeculativeNumberComparison(node);
return reduction.Changed() ? reduction : Changed(node);
}
}
}
}
return UpdateChecks(node, checks);
}
Reduction RedundancyElimination::ReduceSpeculativeNumberOperation(Node* node) {
DCHECK(node->opcode() == IrOpcode::kSpeculativeNumberAdd ||
node->opcode() == IrOpcode::kSpeculativeNumberSubtract ||
node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd ||
node->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract ||
node->opcode() == IrOpcode::kSpeculativeToNumber);
DCHECK_EQ(1, node->op()->EffectInputCount());
DCHECK_EQ(1, node->op()->EffectOutputCount());
Node* const first = NodeProperties::GetValueInput(node, 0);
Node* const effect = NodeProperties::GetEffectInput(node);
EffectPathChecks const* checks = node_checks_.Get(effect);
// If we do not know anything about the predecessor, do not propagate just yet
// because we will have to recompute anyway once we compute the predecessor.
if (checks == nullptr) return NoChange();
// Check if there's a CheckBounds operation on {first}
// in the graph already, which we might be able to
// reuse here to improve the representation selection
// for the {node} later on.
if (Node* check = checks->LookupBoundsCheckFor(first)) {
// Only use the bounds {check} if its type is better
// than the type of the {first} node, otherwise we
// would end up replacing NumberConstant inputs with
// CheckBounds operations, which is kind of pointless.
if (!NodeProperties::GetType(first).Is(NodeProperties::GetType(check))) {
NodeProperties::ReplaceValueInput(node, check, 0);
}
}
return UpdateChecks(node, checks);
}
Reduction RedundancyElimination::ReduceStart(Node* node) {
return UpdateChecks(node, EffectPathChecks::Empty(zone()));
}
Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
if (node->op()->EffectInputCount() == 1) {
if (node->op()->EffectOutputCount() == 1) {
return TakeChecksFromFirstEffect(node);
} else {
// Effect terminators should be handled specially.
return NoChange();
}
}
DCHECK_EQ(0, node->op()->EffectInputCount());
DCHECK_EQ(0, node->op()->EffectOutputCount());
return NoChange();
}
Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
DCHECK_EQ(1, node->op()->EffectOutputCount());
Node* const effect = NodeProperties::GetEffectInput(node);
EffectPathChecks const* checks = node_checks_.Get(effect);
// If we do not know anything about the predecessor, do not propagate just yet
// because we will have to recompute anyway once we compute the predecessor.
if (checks == nullptr) return NoChange();
// We just propagate the information from the effect input (ideally,
// we would only revisit effect uses if there is change).
return UpdateChecks(node, checks);
}
Reduction RedundancyElimination::UpdateChecks(Node* node,
EffectPathChecks const* checks) {
EffectPathChecks const* original = node_checks_.Get(node);
// Only signal that the {node} has Changed, if the information about {checks}
// has changed wrt. the {original}.
if (checks != original) {
if (original == nullptr || !checks->Equals(original)) {
node_checks_.Set(node, checks);
return Changed(node);
}
}
return NoChange();
}
} // namespace compiler
} // namespace internal
} // namespace v8