From a5c6716cf5b06f14181ac94837992b8befe303f0 Mon Sep 17 00:00:00 2001 From: "mmassi@chromium.org" Date: Wed, 13 Feb 2013 14:16:15 +0000 Subject: [PATCH] Infrastructure classes for evaluating numeric relations between values. Review URL: https://codereview.chromium.org/12226112 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@13656 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/lithium-arm.cc | 5 + src/hydrogen-instructions.cc | 118 +++++++++++++++++++++- src/hydrogen-instructions.h | 229 +++++++++++++++++++++++++++++++++++++++++++ src/hydrogen.cc | 12 ++- src/hydrogen.h | 3 + src/ia32/lithium-ia32.cc | 5 + src/mips/lithium-mips.cc | 5 + src/x64/lithium-x64.cc | 5 + 8 files changed, 378 insertions(+), 4 deletions(-) diff --git a/src/arm/lithium-arm.cc b/src/arm/lithium-arm.cc index 990eb5f..208ca21 100644 --- a/src/arm/lithium-arm.cc +++ b/src/arm/lithium-arm.cc @@ -1685,6 +1685,11 @@ LInstruction* LChunkBuilder::DoSeqStringSetChar(HSeqStringSetChar* instr) { } +LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint* instr) { + return NULL; +} + + LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { LOperand* value = UseRegisterOrConstantAtStart(instr->index()); LOperand* length = UseRegister(instr->length()); diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index c8b16c2..2d4b82b 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -405,9 +405,10 @@ bool HValue::TestDominanceUsingProcessedFlag(HValue* dominator, if (dominator->block() != dominated->block()) { return dominator->block()->Dominates(dominated->block()); } else { - // If both arguments are in the same block we check if "dominator" has - // already been processed or if it is a phi: if yes it dominates the other. - return dominator->CheckFlag(kIDefsProcessingDone) || dominator->IsPhi(); + // If both arguments are in the same block we check if dominator is a phi + // or if dominated has not already been processed: in either case we know + // that dominator precedes dominated. + return dominator->IsPhi() || !dominated->CheckFlag(kIDefsProcessingDone); } } @@ -524,6 +525,16 @@ const char* HValue::Mnemonic() const { } +bool HValue::IsInteger32Constant() { + return IsConstant() && HConstant::cast(this)->HasInteger32Value(); +} + + +int32_t HValue::GetInteger32Constant() { + return HConstant::cast(this)->Integer32Value(); +} + + void HValue::SetOperandAt(int index, HValue* value) { RegisterUse(index, value); InternalSetOperandAt(index, value); @@ -801,6 +812,37 @@ void HInstruction::Verify() { #endif +HNumericConstraint* HNumericConstraint::AddToGraph( + HValue* constrained_value, + NumericRelation relation, + HValue* related_value, + HInstruction* insertion_point) { + if (insertion_point == NULL) { + if (constrained_value->IsInstruction()) { + insertion_point = HInstruction::cast(constrained_value); + } else if (constrained_value->IsPhi()) { + insertion_point = constrained_value->block()->first(); + } else { + UNREACHABLE(); + } + } + HNumericConstraint* result = + new(insertion_point->block()->zone()) HNumericConstraint( + constrained_value, relation, related_value); + result->InsertAfter(insertion_point); + return result; +} + + +void HNumericConstraint::PrintDataTo(StringStream* stream) { + stream->Add("("); + constrained_value()->PrintNameTo(stream); + stream->Add(" %s ", relation().Mnemonic()); + related_value()->PrintNameTo(stream); + stream->Add(")"); +} + + void HDummyUse::PrintDataTo(StringStream* stream) { value()->PrintNameTo(stream); } @@ -822,10 +864,38 @@ void HBinaryCall::PrintDataTo(StringStream* stream) { } +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); + } +} + + +bool HBoundsCheck::IsRelationTrueInternal(NumericRelation relation, + HValue* related_value) { + if (related_value == length()) { + // A HBoundsCheck is smaller than the length it compared against. + return NumericRelation::Lt().Implies(relation); + } else if (related_value == block()->graph()->GetConstant0()) { + // A HBoundsCheck is greater than or equal to zero. + return NumericRelation::Ge().Implies(relation); + } else { + return false; + } +} + + void HBoundsCheck::PrintDataTo(StringStream* stream) { index()->PrintNameTo(stream); stream->Add(" "); length()->PrintNameTo(stream); + if (skip_check()) { + stream->Add(" [DISABLED]"); + } } @@ -1482,6 +1552,38 @@ Range* HMod::InferRange(Zone* zone) { } +void HPhi::AddInformativeDefinitions() { + if (OperandCount() == 2) { + for (int operand_index = 0; operand_index < 2; operand_index++) { + int other_operand_index = (operand_index + 1) % 2; + + // Add an idef that "discards" the OSR entry block branch. + if (OperandAt(operand_index)->block()->is_osr_entry()) { + HNumericConstraint::AddToGraph( + this, NumericRelation::Eq(), OperandAt(other_operand_index)); + } + + static NumericRelation relations[] = { + NumericRelation::Ge(), + NumericRelation::Le() + }; + + // Check if this phi is an induction variable. If, e.g., we know that + // its first input is greater than the phi itself, then that must be + // the back edge, and the phi is always greater than its second input. + for (int relation_index = 0; relation_index < 2; relation_index++) { + if (OperandAt(operand_index)->IsRelationTrue(relations[relation_index], + this)) { + HNumericConstraint::AddToGraph(this, + relations[relation_index], + OperandAt(other_operand_index)); + } + } + } + } +} + + Range* HMathMinMax::InferRange(Zone* zone) { if (representation().IsInteger32()) { Range* a = left()->range(); @@ -1943,6 +2045,16 @@ void HStringCompareAndBranch::PrintDataTo(StringStream* stream) { } +void HCompareIDAndBranch::AddInformativeDefinitions() { + NumericRelation r = NumericRelation::FromToken(token()); + if (r.IsNone()) return; + + HNumericConstraint::AddToGraph(left(), r, right(), SuccessorAt(0)->first()); + HNumericConstraint::AddToGraph( + left(), r.Negated(), right(), SuccessorAt(1)->first()); +} + + void HCompareIDAndBranch::PrintDataTo(StringStream* stream) { stream->Add(Token::Name(token())); stream->Add(" "); diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h index 20e5b3b..2767560 100644 --- a/src/hydrogen-instructions.h +++ b/src/hydrogen-instructions.h @@ -147,6 +147,7 @@ class LChunkBuilder; V(MathMinMax) \ V(Mod) \ V(Mul) \ + V(NumericConstraint) \ V(ObjectLiteral) \ V(OsrEntry) \ V(OuterContext) \ @@ -550,6 +551,127 @@ enum GVNFlag { #undef COUNT_FLAG }; + +class NumericRelation { + public: + enum Kind { NONE, EQ, GT, GE, LT, LE, NE }; + static const char* MnemonicFromKind(Kind kind) { + switch (kind) { + case NONE: return "NONE"; + case EQ: return "EQ"; + case GT: return "GT"; + case GE: return "GE"; + case LT: return "LT"; + case LE: return "LE"; + case NE: return "NE"; + } + UNREACHABLE(); + return NULL; + } + const char* Mnemonic() const { return MnemonicFromKind(kind_); } + + static NumericRelation None() { return NumericRelation(NONE); } + static NumericRelation Eq() { return NumericRelation(EQ); } + static NumericRelation Gt() { return NumericRelation(GT); } + static NumericRelation Ge() { return NumericRelation(GE); } + static NumericRelation Lt() { return NumericRelation(LT); } + static NumericRelation Le() { return NumericRelation(LE); } + static NumericRelation Ne() { return NumericRelation(NE); } + + bool IsNone() { return kind_ == NONE; } + + static NumericRelation FromToken(Token::Value token) { + switch (token) { + case Token::EQ: return Eq(); + case Token::EQ_STRICT: return Eq(); + case Token::LT: return Lt(); + case Token::GT: return Gt(); + case Token::LTE: return Le(); + case Token::GTE: return Ge(); + case Token::NE: return Ne(); + case Token::NE_STRICT: return Ne(); + default: return None(); + } + } + + // The semantics of "Reversed" is that if "x rel y" is true then also + // "y rel.Reversed() x" is true, and that rel.Reversed().Reversed() == rel. + NumericRelation Reversed() { + switch (kind_) { + case NONE: return None(); + case EQ: return Eq(); + case GT: return Lt(); + case GE: return Le(); + case LT: return Gt(); + case LE: return Ge(); + case NE: return Ne(); + } + UNREACHABLE(); + return None(); + } + + // The semantics of "Negated" is that if "x rel y" is true then also + // "!(x rel.Negated() y)" is true. + NumericRelation Negated() { + switch (kind_) { + case NONE: return None(); + case EQ: return Ne(); + case GT: return Le(); + case GE: return Lt(); + case LT: return Ge(); + case LE: return Gt(); + case NE: return Eq(); + } + UNREACHABLE(); + return None(); + } + + // The semantics of "Implies" is that if "x rel y" is true + // then also "x other_relation y" is true. + bool Implies(NumericRelation other_relation) { + switch (kind_) { + case NONE: return false; + case EQ: return (other_relation.kind_ == EQ) + || (other_relation.kind_ == GE) + || (other_relation.kind_ == LE); + case GT: return (other_relation.kind_ == GT) + || (other_relation.kind_ == GE) + || (other_relation.kind_ == NE); + case LT: return (other_relation.kind_ == LT) + || (other_relation.kind_ == LE) + || (other_relation.kind_ == NE); + case GE: return (other_relation.kind_ == GE); + case LE: return (other_relation.kind_ == LE); + case NE: return (other_relation.kind_ == NE); + } + UNREACHABLE(); + return false; + } + + // The semantics of "IsExtendable" is that if + // "rel.IsExtendable(direction)" is true then + // "x rel y" implies "(x + direction) rel y" . + bool IsExtendable(int direction) { + switch (kind_) { + case NONE: return false; + case EQ: return false; + case GT: return (direction >= 0); + case GE: return (direction >= 0); + case LT: return (direction <= 0); + case LE: return (direction <= 0); + case NE: return false; + } + UNREACHABLE(); + return false; + } + + private: + explicit NumericRelation(Kind kind) : kind_(kind) {} + + Kind kind_; +}; + + typedef EnumSet GVNFlagSet; @@ -713,6 +835,9 @@ class HValue: public ZoneObject { UpdateRedefinedUsesInner(); } + bool IsInteger32Constant(); + int32_t GetInteger32Constant(); + bool IsDefinedAfter(HBasicBlock* other) const; // Operands. @@ -839,6 +964,24 @@ 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 result = IsRelationTrueInternal(relation, other) || + other->IsRelationTrueInternal(relation.Reversed(), this); + if (!result) { + HValue* redefined = RedefinedOperand(); + if (redefined != NULL) { + result = redefined->IsRelationTrue(relation, other); + } + } + return result; + } + protected: // This function must be overridden for instructions with flag kUseGVN, to // compare the non-Operand parts of the instruction. @@ -901,6 +1044,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) { + return false; + } + static GVNFlagSet AllDependsOnFlagSet() { GVNFlagSet result; // Create changes mask. @@ -1125,6 +1274,50 @@ class HDummyUse: public HTemplateInstruction<1> { }; +class HNumericConstraint : public HTemplateInstruction<2> { + public: + static HNumericConstraint* AddToGraph(HValue* constrained_value, + NumericRelation relation, + HValue* related_value, + HInstruction* insertion_point = NULL); + + HValue* constrained_value() { return OperandAt(0); } + HValue* related_value() { return OperandAt(1); } + NumericRelation relation() { return relation_; } + + virtual int RedefinedOperandIndex() { return 0; } + + virtual Representation RequiredInputRepresentation(int index) { + return representation(); + } + + virtual void PrintDataTo(StringStream* stream); + + virtual bool IsRelationTrueInternal(NumericRelation other_relation, + HValue* other_related_value) { + if (related_value() == other_related_value) { + return relation().Implies(other_relation); + } else { + return false; + } + } + + DECLARE_CONCRETE_INSTRUCTION(NumericConstraint) + + private: + HNumericConstraint(HValue* constrained_value, + NumericRelation relation, + HValue* related_value) + : relation_(relation) { + SetOperandAt(0, constrained_value); + SetOperandAt(1, related_value); + set_representation(constrained_value->representation()); + } + + NumericRelation relation_; +}; + + // We insert soft-deoptimize when we hit code with unknown typefeedback, // so that we get a chance of re-optimizing with useful typefeedback. // HSoftDeoptimize does not end a basic block as opposed to HDeoptimize. @@ -2677,6 +2870,8 @@ class HPhi: public HValue { int merged_index() const { return merged_index_; } + virtual void AddInformativeDefinitions(); + virtual void PrintTo(StringStream* stream); #ifdef DEBUG @@ -3154,6 +3349,9 @@ class HBoundsCheck: public HTemplateInstruction<2> { return Representation::Integer32(); } + virtual bool IsRelationTrueInternal(NumericRelation relation, + HValue* related_value); + virtual void PrintDataTo(StringStream* stream); virtual void InferRepresentation(HInferRepresentation* h_infer); @@ -3161,6 +3359,7 @@ class HBoundsCheck: public HTemplateInstruction<2> { HValue* length() { return OperandAt(1); } virtual int RedefinedOperandIndex() { return 0; } + virtual void AddInformativeDefinitions(); DECLARE_CONCRETE_INSTRUCTION(BoundsCheck) @@ -3337,6 +3536,8 @@ class HCompareIDAndBranch: public HTemplateControlInstruction<2, 2> { } virtual void PrintDataTo(StringStream* stream); + virtual void AddInformativeDefinitions(); + DECLARE_CONCRETE_INSTRUCTION(CompareIDAndBranch) private: @@ -3741,6 +3942,23 @@ class HAdd: public HArithmeticBinaryOperation { virtual HValue* Canonicalize(); + virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) { + HValue* base = NULL; + int32_t offset = 0; + if (left()->IsInteger32Constant()) { + base = right(); + offset = left()->GetInteger32Constant(); + } else if (right()->IsInteger32Constant()) { + base = left(); + offset = right()->GetInteger32Constant(); + } else { + return false; + } + + return relation.IsExtendable(offset) + ? base->IsRelationTrue(relation, other) : false; + } + DECLARE_CONCRETE_INSTRUCTION(Add) protected: @@ -3766,6 +3984,17 @@ class HSub: public HArithmeticBinaryOperation { HValue* left, HValue* right); + virtual bool IsRelationTrueInternal(NumericRelation relation, HValue* other) { + if (right()->IsInteger32Constant()) { + HValue* base = left(); + int32_t offset = right()->GetInteger32Constant(); + return relation.IsExtendable(-offset) + ? base->IsRelationTrue(relation, other) : false; + } else { + return false; + } + } + DECLARE_CONCRETE_INSTRUCTION(Sub) protected: diff --git a/src/hydrogen.cc b/src/hydrogen.cc index e1cf70a..b3710f4 100644 --- a/src/hydrogen.cc +++ b/src/hydrogen.cc @@ -71,7 +71,8 @@ HBasicBlock::HBasicBlock(HGraph* graph) parent_loop_header_(NULL), is_inline_return_target_(false), is_deoptimizing_(false), - dominates_loop_successors_(false) { } + dominates_loop_successors_(false), + is_osr_entry_(false) { } void HBasicBlock::AttachLoopInformation() { @@ -3794,6 +3795,12 @@ bool HGraph::Optimize(SmartArrayPointer* bailout_reason) { OrderBlocks(); AssignDominators(); + // We need to create a HConstant "zero" now so that GVN will fold every + // zero-valued constant in the graph together. + // The constant is needed to make idef-based bounds check work: the pass + // evaluates relations with "zero" and that zero cannot be created after GVN. + GetConstant0(); + #ifdef DEBUG // Do a full verify after building the graph and computing dominators. Verify(true); @@ -3871,12 +3878,14 @@ void HGraph::SetupInformativeDefinitionsInBlock(HBasicBlock* block) { for (int phi_index = 0; phi_index < block->phis()->length(); phi_index++) { HPhi* phi = block->phis()->at(phi_index); phi->AddInformativeDefinitions(); + phi->SetFlag(HValue::kIDefsProcessingDone); // We do not support phis that "redefine just one operand". ASSERT(!phi->IsInformativeDefinition()); } for (HInstruction* i = block->first(); i != NULL; i = i->next()) { i->AddInformativeDefinitions(); + i->SetFlag(HValue::kIDefsProcessingDone); i->UpdateRedefinedUsesWhileSettingUpInformativeDefinitions(); } } @@ -4897,6 +4906,7 @@ bool HOptimizedGraphBuilder::PreProcessOsrEntry(IterationStatement* statement) { non_osr_entry->Goto(loop_predecessor); set_current_block(osr_entry); + osr_entry->set_osr_entry(); BailoutId osr_entry_id = statement->OsrEntryId(); int first_expression_index = environment()->first_expression_index(); int length = environment()->length(); diff --git a/src/hydrogen.h b/src/hydrogen.h index 7c34bba..180882e 100644 --- a/src/hydrogen.h +++ b/src/hydrogen.h @@ -91,6 +91,8 @@ class HBasicBlock: public ZoneObject { void set_last_instruction_index(int index) { last_instruction_index_ = index; } + bool is_osr_entry() { return is_osr_entry_; } + void set_osr_entry() { is_osr_entry_ = true; } void AttachLoopInformation(); void DetachLoopInformation(); @@ -193,6 +195,7 @@ class HBasicBlock: public ZoneObject { bool is_inline_return_target_; bool is_deoptimizing_; bool dominates_loop_successors_; + bool is_osr_entry_; }; diff --git a/src/ia32/lithium-ia32.cc b/src/ia32/lithium-ia32.cc index e69d7f6..a25c154 100644 --- a/src/ia32/lithium-ia32.cc +++ b/src/ia32/lithium-ia32.cc @@ -1712,6 +1712,11 @@ LInstruction* LChunkBuilder::DoSeqStringSetChar(HSeqStringSetChar* instr) { } +LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint* instr) { + return NULL; +} + + LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { return AssignEnvironment(new(zone()) LBoundsCheck( UseRegisterOrConstantAtStart(instr->index()), diff --git a/src/mips/lithium-mips.cc b/src/mips/lithium-mips.cc index cdc340f..6c84bbb 100644 --- a/src/mips/lithium-mips.cc +++ b/src/mips/lithium-mips.cc @@ -1590,6 +1590,11 @@ LInstruction* LChunkBuilder::DoSeqStringSetChar(HSeqStringSetChar* instr) { } +LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint* instr) { + return NULL; +} + + LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { LOperand* value = UseRegisterOrConstantAtStart(instr->index()); LOperand* length = UseRegister(instr->length()); diff --git a/src/x64/lithium-x64.cc b/src/x64/lithium-x64.cc index 20fe5cf..4194ad6 100644 --- a/src/x64/lithium-x64.cc +++ b/src/x64/lithium-x64.cc @@ -1636,6 +1636,11 @@ LInstruction* LChunkBuilder::DoSeqStringSetChar(HSeqStringSetChar* instr) { } +LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint* instr) { + return NULL; +} + + LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) { LOperand* value = UseRegisterOrConstantAtStart(instr->index()); LOperand* length = Use(instr->length()); -- 2.7.4