| // 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 |