From 73e83b0b0f10f76c6473ba69f10f0ff9dd3bc9fc Mon Sep 17 00:00:00 2001 From: "mmassi@chromium.org" Date: Mon, 18 Mar 2013 08:06:00 +0000 Subject: [PATCH] Handling expression decomposition and array bounds check hoisting: working code with lots of debugging PrintFs, postdominance check still missing. Review URL: https://codereview.chromium.org/12377072 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@13961 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/lithium-arm.cc | 7 + src/hydrogen-instructions.cc | 257 ++++++++++++++++++++++- src/hydrogen-instructions.h | 316 +++++++++++++++++++++++++---- src/hydrogen.cc | 12 ++ src/hydrogen.h | 2 + src/ia32/lithium-ia32.cc | 7 + src/mips/lithium-mips.cc | 7 + src/x64/lithium-x64.cc | 7 + test/mjsunit/array-bounds-check-removal.js | 28 +++ 9 files changed, 595 insertions(+), 48 deletions(-) diff --git a/src/arm/lithium-arm.cc b/src/arm/lithium-arm.cc index 7272f54..38884ce 100644 --- a/src/arm/lithium-arm.cc +++ b/src/arm/lithium-arm.cc @@ -1779,6 +1779,13 @@ LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { } +LInstruction* LChunkBuilder::DoBoundsCheckBaseIndexInformation( + HBoundsCheckBaseIndexInformation* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoAbnormalExit(HAbnormalExit* instr) { // The control instruction marking the end of a block that completed // abruptly (e.g., threw an exception). There is nothing specific to do. diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index 20e41bc..2aab369 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -167,6 +167,116 @@ void HValue::AddDependantsToWorklist(HInferRepresentation* h_infer) { } +// This method is recursive but it is guaranteed to terminate because +// RedefinedOperand() always dominates "this". +bool HValue::IsRelationTrue(NumericRelation relation, + HValue* other, + int offset, + int scale) { + if (this == other) { + return NumericRelation::Eq().Implies(relation); + } + + // Test the direct relation. + if (IsRelationTrueInternal(relation, other, offset, scale)) return true; + + // If scale is 0 try the reversed relation. + if (scale == 0 && + // TODO(mmassi): do we need the full, recursive IsRelationTrue? + other->IsRelationTrueInternal(relation.Reversed(), this, -offset)) { + return true; + } + + // Try decomposition (but do not accept scaled compounds). + DecompositionResult decomposition; + if (TryDecompose(&decomposition) && + decomposition.scale() == 0 && + decomposition.base()->IsRelationTrue(relation, other, + offset + decomposition.offset(), + scale)) { + return true; + } + + // Pass the request to the redefined value. + HValue* redefined = RedefinedOperand(); + return redefined != NULL && redefined->IsRelationTrue(relation, other, + offset, scale); +} + + +bool HValue::TryGuaranteeRange(HValue* upper_bound) { + RangeEvaluationContext context = RangeEvaluationContext(this, upper_bound); + TryGuaranteeRangeRecursive(&context); + bool result = context.is_range_satisfied(); + if (result) { + context.lower_bound_guarantee()->SetResponsibilityForRange(DIRECTION_LOWER); + context.upper_bound_guarantee()->SetResponsibilityForRange(DIRECTION_UPPER); + } + return result; +} + + +void HValue::TryGuaranteeRangeRecursive(RangeEvaluationContext* context) { + // Check if we already know that this value satisfies the lower bound. + if (context->lower_bound_guarantee() == NULL) { + if (IsRelationTrueInternal(NumericRelation::Ge(), context->lower_bound(), + context->offset(), context->scale())) { + context->set_lower_bound_guarantee(this); + } + } + + // Check if we already know that this value satisfies the upper bound. + if (context->upper_bound_guarantee() == NULL) { + if (IsRelationTrueInternal(NumericRelation::Lt(), context->upper_bound(), + context->offset(), context->scale()) || + (context->scale() == 0 && + context->upper_bound()->IsRelationTrue(NumericRelation::Gt(), + this, -context->offset()))) { + context->set_upper_bound_guarantee(this); + } + } + + if (context->is_range_satisfied()) return; + + // See if our RedefinedOperand() satisfies the constraints. + if (RedefinedOperand() != NULL) { + RedefinedOperand()->TryGuaranteeRangeRecursive(context); + } + if (context->is_range_satisfied()) return; + + // See if the constraints can be satisfied by decomposition. + DecompositionResult decomposition; + if (TryDecompose(&decomposition)) { + context->swap_candidate(&decomposition); + context->candidate()->TryGuaranteeRangeRecursive(context); + context->swap_candidate(&decomposition); + } + if (context->is_range_satisfied()) return; + + // Try to modify this to satisfy the constraint. + + TryGuaranteeRangeChanging(context); +} + + +RangeEvaluationContext::RangeEvaluationContext(HValue* value, HValue* upper) + : lower_bound_(upper->block()->graph()->GetConstant0()), + lower_bound_guarantee_(NULL), + candidate_(value), + upper_bound_(upper), + upper_bound_guarantee_(NULL), + offset_(0), + scale_(0) { +} + + +HValue* RangeEvaluationContext::ConvertGuarantee(HValue* guarantee) { + return guarantee->IsBoundsCheckBaseIndexInformation() + ? HBoundsCheckBaseIndexInformation::cast(guarantee)->bounds_check() + : guarantee; +} + + static int32_t ConvertAndSetOverflow(int64_t result, bool* overflow) { if (result > kMaxInt) { *overflow = true; @@ -888,25 +998,115 @@ void HBinaryCall::PrintDataTo(StringStream* stream) { } +void HBoundsCheck::TryGuaranteeRangeChanging(RangeEvaluationContext* context) { + if (context->candidate()->ActualValue() != base()->ActualValue() || + context->scale() < scale()) { + return; + } + + // TODO(mmassi) + // Instead of checking for "same basic block" we should check for + // "dominates and postdominates". + if (context->upper_bound() == length() && + context->lower_bound_guarantee() != NULL && + context->lower_bound_guarantee() != this && + context->lower_bound_guarantee()->block() != block() && + offset() < context->offset() && + index_can_increase() && + context->upper_bound_guarantee() == NULL) { + offset_ = context->offset(); + SetResponsibilityForRange(DIRECTION_UPPER); + context->set_upper_bound_guarantee(this); + } else if (context->upper_bound_guarantee() != NULL && + context->upper_bound_guarantee() != this && + context->upper_bound_guarantee()->block() != block() && + offset() > context->offset() && + index_can_decrease() && + context->lower_bound_guarantee() == NULL) { + offset_ = context->offset(); + SetResponsibilityForRange(DIRECTION_LOWER); + context->set_lower_bound_guarantee(this); + } +} + + +void HBoundsCheck::ApplyIndexChange() { + if (skip_check()) return; + + DecompositionResult decomposition; + bool index_is_decomposable = index()->TryDecompose(&decomposition); + if (index_is_decomposable) { + ASSERT(decomposition.base() == base()); + if (decomposition.offset() == offset() && + decomposition.scale() == scale()) return; + } else { + return; + } + + ReplaceAllUsesWith(index()); + + HValue* current_index = decomposition.base(); + int actual_offset = decomposition.offset() + offset(); + int actual_scale = decomposition.scale() + scale(); + + if (actual_offset != 0) { + HConstant* add_offset = new(block()->graph()->zone()) HConstant( + actual_offset, index()->representation()); + add_offset->InsertBefore(this); + HInstruction* add = HAdd::New(block()->graph()->zone(), + block()->graph()->GetInvalidContext(), current_index, add_offset); + add->InsertBefore(this); + add->AssumeRepresentation(index()->representation()); + current_index = add; + } + + if (actual_scale != 0) { + HConstant* sar_scale = new(block()->graph()->zone()) HConstant( + actual_scale, index()->representation()); + sar_scale->InsertBefore(this); + HInstruction* sar = HSar::New(block()->graph()->zone(), + block()->graph()->GetInvalidContext(), current_index, sar_scale); + sar->InsertBefore(this); + sar->AssumeRepresentation(index()->representation()); + current_index = sar; + } + + SetOperandAt(0, current_index); + + base_ = NULL; + offset_ = 0; + scale_ = 0; + responsibility_direction_ = DIRECTION_NONE; +} + + void HBoundsCheck::AddInformativeDefinitions() { // TODO(mmassi): Executing this code during AddInformativeDefinitions // is a hack. Move it to some other HPhase. - if (index()->IsRelationTrue(NumericRelation::Ge(), - block()->graph()->GetConstant0()) && - index()->IsRelationTrue(NumericRelation::Lt(), length())) { - set_skip_check(true); + if (FLAG_array_bounds_checks_elimination) { + if (index()->TryGuaranteeRange(length())) { + set_skip_check(true); + } + if (DetectCompoundIndex()) { + HBoundsCheckBaseIndexInformation* base_index_info = + new(block()->graph()->zone()) + HBoundsCheckBaseIndexInformation(this); + base_index_info->InsertAfter(this); + } } } bool HBoundsCheck::IsRelationTrueInternal(NumericRelation relation, - HValue* related_value) { + HValue* related_value, + int offset, + int scale) { if (related_value == length()) { // A HBoundsCheck is smaller than the length it compared against. - return NumericRelation::Lt().Implies(relation); + return NumericRelation::Lt().CompoundImplies(relation, 0, 0, offset, scale); } else if (related_value == block()->graph()->GetConstant0()) { // A HBoundsCheck is greater than or equal to zero. - return NumericRelation::Ge().Implies(relation); + return NumericRelation::Ge().CompoundImplies(relation, 0, 0, offset, scale); } else { return false; } @@ -917,6 +1117,15 @@ void HBoundsCheck::PrintDataTo(StringStream* stream) { index()->PrintNameTo(stream); stream->Add(" "); length()->PrintNameTo(stream); + if (base() != NULL && (offset() != 0 || scale() != 0)) { + stream->Add(" base: (("); + if (base() != index()) { + index()->PrintNameTo(stream); + } else { + stream->Add("index"); + } + stream->Add(" + %d) >> %d)", offset(), scale()); + } if (skip_check()) { stream->Add(" [DISABLED]"); } @@ -946,6 +1155,33 @@ void HBoundsCheck::InferRepresentation(HInferRepresentation* h_infer) { } +bool HBoundsCheckBaseIndexInformation::IsRelationTrueInternal( + NumericRelation relation, + HValue* related_value, + int offset, + int scale) { + if (related_value == bounds_check()->length()) { + return NumericRelation::Lt().CompoundImplies( + relation, + bounds_check()->offset(), bounds_check()->scale(), offset, scale); + } else if (related_value == block()->graph()->GetConstant0()) { + return NumericRelation::Ge().CompoundImplies( + relation, + bounds_check()->offset(), bounds_check()->scale(), offset, scale); + } else { + return false; + } +} + + +void HBoundsCheckBaseIndexInformation::PrintDataTo(StringStream* stream) { + stream->Add("base: "); + base_index()->PrintNameTo(stream); + stream->Add(", check: "); + base_index()->PrintNameTo(stream); +} + + void HCallConstantFunction::PrintDataTo(StringStream* stream) { if (IsApplyFunction()) { stream->Add("optimized apply "); @@ -1611,7 +1847,10 @@ void HPhi::AddInformativeDefinitions() { } -bool HPhi::IsRelationTrueInternal(NumericRelation relation, HValue* other) { +bool HPhi::IsRelationTrueInternal(NumericRelation relation, + HValue* other, + int offset, + int scale) { if (CheckFlag(kNumericConstraintEvaluationInProgress)) return false; SetFlag(kNumericConstraintEvaluationInProgress); @@ -1620,7 +1859,7 @@ bool HPhi::IsRelationTrueInternal(NumericRelation relation, HValue* other) { // Skip OSR entry blocks if (OperandAt(i)->block()->is_osr_entry()) continue; - if (!OperandAt(i)->IsRelationTrue(relation, other)) { + if (!OperandAt(i)->IsRelationTrue(relation, other, offset, scale)) { result = false; break; } diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index 29e8c29..f741f29 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -75,6 +75,7 @@ class LChunkBuilder; V(BitNot) \ V(BlockEntry) \ V(BoundsCheck) \ + V(BoundsCheckBaseIndexInformation) \ V(Branch) \ V(CallConstantFunction) \ V(CallFunction) \ @@ -667,13 +668,130 @@ class NumericRelation { return false; } + // CompoundImplies returns true when + // "((x + my_offset) >> my_scale) rel y" implies + // "((x + other_offset) >> other_scale) other_relation y". + bool CompoundImplies(NumericRelation other_relation, + int my_offset, + int my_scale, + int other_offset = 0, + int other_scale = 0) { + return Implies(other_relation) && ComponentsImply( + my_offset, my_scale, other_offset, other_scale); + } + private: + // ComponentsImply returns true when + // "((x + my_offset) >> my_scale) rel y" implies + // "((x + other_offset) >> other_scale) rel y". + bool ComponentsImply(int my_offset, + int my_scale, + int other_offset, + int other_scale) { + switch (kind_) { + case NONE: break; // Fall through to UNREACHABLE(). + case EQ: + case NE: return my_offset == other_offset && my_scale == other_scale; + case GT: + case GE: return my_offset <= other_offset && my_scale >= other_scale; + case LT: + case LE: return my_offset >= other_offset && my_scale <= other_scale; + } + UNREACHABLE(); + return false; + } + explicit NumericRelation(Kind kind) : kind_(kind) {} Kind kind_; }; +class DecompositionResult BASE_EMBEDDED { + public: + DecompositionResult() : base_(NULL), offset_(0), scale_(0) {} + + HValue* base() { return base_; } + int offset() { return offset_; } + int scale() { return scale_; } + + bool Apply(HValue* other_base, int other_offset, int other_scale = 0) { + if (base_ == NULL) { + base_ = other_base; + offset_ = other_offset; + scale_ = other_scale; + return true; + } else { + if (scale_ == 0) { + base_ = other_base; + offset_ += other_offset; + scale_ = other_scale; + return true; + } else { + return false; + } + } + } + + void SwapValues(HValue** other_base, int* other_offset, int* other_scale) { + swap(&base_, other_base); + swap(&offset_, other_offset); + swap(&scale_, other_scale); + } + + private: + template void swap(T* a, T* b) { + T c(*a); + *a = *b; + *b = c; + } + + HValue* base_; + int offset_; + int scale_; +}; + + +class RangeEvaluationContext BASE_EMBEDDED { + public: + RangeEvaluationContext(HValue* value, HValue* upper); + + HValue* lower_bound() { return lower_bound_; } + HValue* lower_bound_guarantee() { return lower_bound_guarantee_; } + HValue* candidate() { return candidate_; } + HValue* upper_bound() { return upper_bound_; } + HValue* upper_bound_guarantee() { return upper_bound_guarantee_; } + int offset() { return offset_; } + int scale() { return scale_; } + + bool is_range_satisfied() { + return lower_bound_guarantee() != NULL && upper_bound_guarantee() != NULL; + } + + void set_lower_bound_guarantee(HValue* guarantee) { + lower_bound_guarantee_ = ConvertGuarantee(guarantee); + } + void set_upper_bound_guarantee(HValue* guarantee) { + upper_bound_guarantee_ = ConvertGuarantee(guarantee); + } + + void swap_candidate(DecompositionResult* other_candicate) { + other_candicate->SwapValues(&candidate_, &offset_, &scale_); + } + + private: + HValue* ConvertGuarantee(HValue* guarantee); + + HValue* lower_bound_; + HValue* lower_bound_guarantee_; + HValue* candidate_; + HValue* upper_bound_; + HValue* upper_bound_guarantee_; + int offset_; + int scale_; +}; + + typedef EnumSet GVNFlagSet; @@ -977,25 +1095,32 @@ class HValue: public ZoneObject { virtual void Verify() = 0; #endif - // This method is recursive but it is guaranteed to terminate because - // RedefinedOperand() always dominates "this". - bool IsRelationTrue(NumericRelation relation, HValue* other) { - if (this == other) { - return NumericRelation::Eq().Implies(relation); - } + bool IsRelationTrue(NumericRelation relation, + HValue* other, + int offset = 0, + int scale = 0); - bool result = IsRelationTrueInternal(relation, other) || - other->IsRelationTrueInternal(relation.Reversed(), this); - if (!result) { - HValue* redefined = RedefinedOperand(); - if (redefined != NULL) { - result = redefined->IsRelationTrue(relation, other); - } + bool TryGuaranteeRange(HValue* upper_bound); + virtual bool TryDecompose(DecompositionResult* decomposition) { + if (RedefinedOperand() != NULL) { + return RedefinedOperand()->TryDecompose(decomposition); + } else { + return false; } - return result; } protected: + void TryGuaranteeRangeRecursive(RangeEvaluationContext* context); + + enum RangeGuaranteeDirection { + DIRECTION_NONE = 0, + DIRECTION_UPPER = 1, + DIRECTION_LOWER = 2, + DIRECTION_BOTH = DIRECTION_UPPER | DIRECTION_LOWER + }; + virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) {} + virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context) {} + // This function must be overridden for instructions with flag kUseGVN, to // compare the non-Operand parts of the instruction. virtual bool DataEquals(HValue* other) { @@ -1059,7 +1184,12 @@ class HValue: public ZoneObject { // Informative definitions can override this method to state any numeric // relation they provide on the redefined value. - virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) { + // Returns true if it is guaranteed that: + // ((this + offset) >> scale) relation other + virtual bool IsRelationTrueInternal(NumericRelation relation, + HValue* other, + int offset = 0, + int scale = 0) { return false; } @@ -1308,9 +1438,11 @@ class HNumericConstraint : public HTemplateInstruction<2> { virtual void PrintDataTo(StringStream* stream); virtual bool IsRelationTrueInternal(NumericRelation other_relation, - HValue* other_related_value) { + HValue* other_related_value, + int offset = 0, + int scale = 0) { if (related_value() == other_related_value) { - return relation().Implies(other_relation); + return relation().CompoundImplies(other_relation, offset, scale); } else { return false; } @@ -1325,7 +1457,6 @@ class HNumericConstraint : public HTemplateInstruction<2> { : relation_(relation) { SetOperandAt(0, constrained_value); SetOperandAt(1, related_value); - set_representation(constrained_value->representation()); } NumericRelation relation_; @@ -2992,7 +3123,10 @@ class HPhi: public HValue { inputs_[index] = value; } - virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other); + virtual bool IsRelationTrueInternal(NumericRelation relation, + HValue* other, + int offset = 0, + int scale = 0); private: ZoneList inputs_; @@ -3024,9 +3158,11 @@ class HInductionVariableAnnotation : public HUnaryOperation { virtual void PrintDataTo(StringStream* stream); virtual bool IsRelationTrueInternal(NumericRelation other_relation, - HValue* other_related_value) { + HValue* other_related_value, + int offset = 0, + int scale = 0) { if (induction_base() == other_related_value) { - return relation().Implies(other_relation); + return relation().CompoundImplies(other_relation, offset, scale); } else { return false; } @@ -3040,7 +3176,6 @@ class HInductionVariableAnnotation : public HUnaryOperation { int operand_index) : HUnaryOperation(phi), phi_(phi), relation_(relation), operand_index_(operand_index) { - set_representation(phi->representation()); } // We need to store the phi both here and in the instruction operand because @@ -3445,6 +3580,9 @@ enum BoundsCheckKeyMode { }; +class HBoundsCheckBaseIndexInformation; + + class HBoundsCheck: public HTemplateInstruction<2> { public: // Normally HBoundsCheck should be created using the @@ -3456,7 +3594,9 @@ class HBoundsCheck: public HTemplateInstruction<2> { HValue* length, BoundsCheckKeyMode key_mode = DONT_ALLOW_SMI_KEY, Representation r = Representation::None()) - : key_mode_(key_mode), skip_check_(false) { + : key_mode_(key_mode), skip_check_(false), + base_(NULL), offset_(0), scale_(0), + responsibility_direction_(DIRECTION_NONE) { SetOperandAt(0, index); SetOperandAt(1, length); if (r.IsNone()) { @@ -3473,6 +3613,33 @@ class HBoundsCheck: public HTemplateInstruction<2> { bool skip_check() { return skip_check_; } void set_skip_check(bool skip_check) { skip_check_ = skip_check; } + HValue* base() { return base_; } + int offset() { return offset_; } + int scale() { return scale_; } + bool index_can_increase() { + return (responsibility_direction_ & DIRECTION_LOWER) == 0; + } + bool index_can_decrease() { + return (responsibility_direction_ & DIRECTION_UPPER) == 0; + } + + void ApplyIndexChange(); + bool DetectCompoundIndex() { + ASSERT(base() == NULL); + + DecompositionResult decomposition; + if (index()->TryDecompose(&decomposition)) { + base_ = decomposition.base(); + offset_ = decomposition.offset(); + scale_ = decomposition.scale(); + return true; + } else { + base_ = index(); + offset_ = 0; + scale_ = 0; + return false; + } + } virtual Representation RequiredInputRepresentation(int arg_index) { return representation(); @@ -3482,7 +3649,9 @@ class HBoundsCheck: public HTemplateInstruction<2> { } virtual bool IsRelationTrueInternal(NumericRelation relation, - HValue* related_value); + HValue* related_value, + int offset = 0, + int scale = 0); virtual void PrintDataTo(StringStream* stream); virtual void InferRepresentation(HInferRepresentation* h_infer); @@ -3497,9 +3666,61 @@ class HBoundsCheck: public HTemplateInstruction<2> { DECLARE_CONCRETE_INSTRUCTION(BoundsCheck) protected: + friend class HBoundsCheckBaseIndexInformation; + + virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) { + responsibility_direction_ = static_cast( + responsibility_direction_ | direction); + } + virtual bool DataEquals(HValue* other) { return true; } + virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context); BoundsCheckKeyMode key_mode_; bool skip_check_; + HValue* base_; + int offset_; + int scale_; + RangeGuaranteeDirection responsibility_direction_; +}; + + +class HBoundsCheckBaseIndexInformation: public HTemplateInstruction<2> { + public: + explicit HBoundsCheckBaseIndexInformation(HBoundsCheck* check) { + DecompositionResult decomposition; + if (check->index()->TryDecompose(&decomposition)) { + SetOperandAt(0, decomposition.base()); + SetOperandAt(1, check); + } else { + UNREACHABLE(); + } + } + + HValue* base_index() { return OperandAt(0); } + HBoundsCheck* bounds_check() { return HBoundsCheck::cast(OperandAt(1)); } + + DECLARE_CONCRETE_INSTRUCTION(BoundsCheckBaseIndexInformation) + + virtual Representation RequiredInputRepresentation(int arg_index) { + return representation(); + } + + virtual bool IsRelationTrueInternal(NumericRelation relation, + HValue* related_value, + int offset = 0, + int scale = 0); + virtual void PrintDataTo(StringStream* stream); + + virtual int RedefinedOperandIndex() { return 0; } + virtual bool IsPurelyInformativeDefinition() { return true; } + + protected: + virtual void SetResponsibilityForRange(RangeGuaranteeDirection direction) { + bounds_check()->SetResponsibilityForRange(direction); + } + virtual void TryGuaranteeRangeChanging(RangeEvaluationContext* context) { + bounds_check()->TryGuaranteeRangeChanging(context); + } }; @@ -4092,21 +4313,16 @@ class HAdd: public HArithmeticBinaryOperation { virtual HValue* Canonicalize(); - virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) { - HValue* base = NULL; - int32_t offset = 0; + virtual bool TryDecompose(DecompositionResult* decomposition) { if (left()->IsInteger32Constant()) { - base = right(); - offset = left()->GetInteger32Constant(); + decomposition->Apply(right(), left()->GetInteger32Constant()); + return true; } else if (right()->IsInteger32Constant()) { - base = left(); - offset = right()->GetInteger32Constant(); + decomposition->Apply(left(), right()->GetInteger32Constant()); + return true; } else { return false; } - - return relation.IsExtendable(offset) - ? base->IsRelationTrue(relation, other) : false; } DECLARE_CONCRETE_INSTRUCTION(Add) @@ -4135,12 +4351,10 @@ class HSub: public HArithmeticBinaryOperation { virtual HValue* Canonicalize(); - virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) { + virtual bool TryDecompose(DecompositionResult* decomposition) { if (right()->IsInteger32Constant()) { - HValue* base = left(); - int32_t offset = right()->GetInteger32Constant(); - return relation.IsExtendable(-offset) - ? base->IsRelationTrue(relation, other) : false; + decomposition->Apply(left(), -right()->GetInteger32Constant()); + return true; } else { return false; } @@ -4375,6 +4589,18 @@ class HShr: public HBitwiseBinaryOperation { HValue* left, HValue* right); + virtual bool TryDecompose(DecompositionResult* decomposition) { + if (right()->IsInteger32Constant()) { + if (decomposition->Apply(left(), 0, right()->GetInteger32Constant())) { + // This is intended to look for HAdd and HSub, to handle compounds + // like ((base + offset) >> scale) with one single decomposition. + left()->TryDecompose(decomposition); + return true; + } + } + return false; + } + virtual Range* InferRange(Zone* zone); DECLARE_CONCRETE_INSTRUCTION(Shr) @@ -4395,6 +4621,18 @@ class HSar: public HBitwiseBinaryOperation { HValue* left, HValue* right); + virtual bool TryDecompose(DecompositionResult* decomposition) { + if (right()->IsInteger32Constant()) { + if (decomposition->Apply(left(), 0, right()->GetInteger32Constant())) { + // This is intended to look for HAdd and HSub, to handle compounds + // like ((base + offset) >> scale) with one single decomposition. + left()->TryDecompose(decomposition); + return true; + } + } + return false; + } + virtual Range* InferRange(Zone* zone); DECLARE_CONCRETE_INSTRUCTION(Sar) diff --git a/src/hydrogen.cc b/src/hydrogen.cc index 9f63c17..ae97d5e 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -687,6 +687,11 @@ void HGraphBuilder::CheckBuilder::End() { } +HConstant* HGraph::GetInvalidContext() { + return GetConstantInt32(&constant_invalid_context_, 0xFFFFC0C7); +} + + HGraphBuilder::IfBuilder::IfBuilder(HGraphBuilder* builder, BailoutId id) : builder_(builder), finished_(false), @@ -4007,6 +4012,13 @@ void HGraph::SetupInformativeDefinitionsRecursively(HBasicBlock* block) { for (int i = 0; i < block->dominated_blocks()->length(); ++i) { SetupInformativeDefinitionsRecursively(block->dominated_blocks()->at(i)); } + + for (HInstruction* i = block->first(); i != NULL; i = i->next()) { + if (i->IsBoundsCheck()) { + HBoundsCheck* check = HBoundsCheck::cast(i); + check->ApplyIndexChange(); + } + } } diff --git a/src/hydrogen.h b/src/hydrogen.h index a35d9a6..7f5326b 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -302,6 +302,7 @@ class HGraph: public ZoneObject { HConstant* GetConstantTrue(); HConstant* GetConstantFalse(); HConstant* GetConstantHole(); + HConstant* GetInvalidContext(); HBasicBlock* CreateBasicBlock(); HArgumentsObject* GetArgumentsObject() const { @@ -421,6 +422,7 @@ class HGraph: public ZoneObject { SetOncePointer constant_true_; SetOncePointer constant_false_; SetOncePointer constant_the_hole_; + SetOncePointer constant_invalid_context_; SetOncePointer arguments_object_; SetOncePointer osr_loop_entry_; diff --git a/src/ia32/lithium-ia32.cc b/src/ia32/lithium-ia32.cc index 4a380ef..f2aec99 100644 --- a/src/ia32/lithium-ia32.cc +++ b/src/ia32/lithium-ia32.cc @@ -1785,6 +1785,13 @@ LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { } +LInstruction* LChunkBuilder::DoBoundsCheckBaseIndexInformation( + HBoundsCheckBaseIndexInformation* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoAbnormalExit(HAbnormalExit* instr) { // The control instruction marking the end of a block that completed // abruptly (e.g., threw an exception). There is nothing specific to do. diff --git a/src/mips/lithium-mips.cc b/src/mips/lithium-mips.cc index f04a462..31d1067 100644 --- a/src/mips/lithium-mips.cc +++ b/src/mips/lithium-mips.cc @@ -1637,6 +1637,13 @@ LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { } +LInstruction* LChunkBuilder::DoBoundsCheckBaseIndexInformation( + HBoundsCheckBaseIndexInformation* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoAbnormalExit(HAbnormalExit* instr) { // The control instruction marking the end of a block that completed // abruptly (e.g., threw an exception). There is nothing specific to do. diff --git a/src/x64/lithium-x64.cc b/src/x64/lithium-x64.cc index d9c2f95..16248ee 100644 --- a/src/x64/lithium-x64.cc +++ b/src/x64/lithium-x64.cc @@ -1700,6 +1700,13 @@ LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { } +LInstruction* LChunkBuilder::DoBoundsCheckBaseIndexInformation( + HBoundsCheckBaseIndexInformation* instr) { + UNREACHABLE(); + return NULL; +} + + LInstruction* LChunkBuilder::DoAbnormalExit(HAbnormalExit* instr) { // The control instruction marking the end of a block that completed // abruptly (e.g., threw an exception). There is nothing specific to do. diff --git a/test/mjsunit/array-bounds-check-removal.js b/test/mjsunit/array-bounds-check-removal.js index 10e11f0..8ed7901 100644 --- a/test/mjsunit/array-bounds-check-removal.js +++ b/test/mjsunit/array-bounds-check-removal.js @@ -200,4 +200,32 @@ result_phi = test_phi(data_phi, 3, true); assertEquals(12, result_phi); +// A test for recursive decomposition +var data_composition_long = [0, 1, 2, 3, 4, 5, 6, 7, 8]; +var data_composition_short = [0, 1, 2, 3, 4]; +function test_composition(a, base0, check) { + var base1 = ((base0 + 2)); + var base2 = ((base1 + 8) >> 2); + var base3 = ((base2 + 6) >> 1); + var base4 = ((base3 + 8) >> 1); + + var result = 0; + result += a[base0]; + result += a[base1]; + result += a[base2]; + result += a[base3]; + result += a[base4]; + + return result; +} +var result_composition = 0; +result_composition = test_composition(data_composition_long, 2); +assertEquals(19, result_composition); +result_composition = test_composition(data_composition_long, 2); +assertEquals(19, result_composition); +%OptimizeFunctionOnNextCall(test_composition); +result_composition = test_composition(data_composition_short, 2); +assertEquals(NaN, result_composition); + + gc(); -- 2.7.4