Revision: 13656
Author: [email protected]
Date: Wed Feb 13 06:16:15 2013
Log: Infrastructure classes for evaluating numeric relations between
values.
Review URL: https://codereview.chromium.org/12226112
http://code.google.com/p/v8/source/detail?r=13656
Modified:
/branches/bleeding_edge/src/arm/lithium-arm.cc
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/hydrogen.h
/branches/bleeding_edge/src/ia32/lithium-ia32.cc
/branches/bleeding_edge/src/mips/lithium-mips.cc
/branches/bleeding_edge/src/x64/lithium-x64.cc
=======================================
--- /branches/bleeding_edge/src/arm/lithium-arm.cc Tue Feb 12 03:44:08 2013
+++ /branches/bleeding_edge/src/arm/lithium-arm.cc Wed Feb 13 06:16:15 2013
@@ -1683,6 +1683,11 @@
new(zone()) LSeqStringSetChar(instr->encoding(), string, index,
value);
return DefineAsRegister(result);
}
+
+
+LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint*
instr) {
+ return NULL;
+}
LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) {
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Tue Feb 12
04:04:29 2013
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Wed Feb 13
06:16:15 2013
@@ -405,9 +405,10 @@
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);
}
}
@@ -522,6 +523,16 @@
default: return "";
}
}
+
+
+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) {
@@ -799,6 +810,37 @@
}
}
#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) {
@@ -822,10 +864,38 @@
}
+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]");
+ }
}
@@ -1480,6 +1550,38 @@
return HValue::InferRange(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) {
@@ -1941,6 +2043,16 @@
stream->Add(" ");
HControlInstruction::PrintDataTo(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) {
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Tue Feb 12 04:04:29
2013
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Wed Feb 13 06:16:15
2013
@@ -147,6 +147,7 @@
V(MathMinMax) \
V(Mod) \
V(Mul) \
+ V(NumericConstraint) \
V(ObjectLiteral) \
V(OsrEntry) \
V(OuterContext) \
@@ -550,6 +551,127 @@
#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<GVNFlag> GVNFlagSet;
@@ -712,6 +834,9 @@
void UpdateRedefinedUses() {
UpdateRedefinedUsesInner<Dominates>();
}
+
+ bool IsInteger32Constant();
+ int32_t GetInteger32Constant();
bool IsDefinedAfter(HBasicBlock* other) const;
@@ -838,6 +963,24 @@
#ifdef DEBUG
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
@@ -900,6 +1043,12 @@
}
}
}
+
+ // 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;
@@ -1125,6 +1274,50 @@
};
+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.
@@ -2676,6 +2869,8 @@
bool IsReceiver() { return merged_index_ == 0; }
int merged_index() const { return merged_index_; }
+
+ virtual void AddInformativeDefinitions();
virtual void PrintTo(StringStream* stream);
@@ -3153,6 +3348,9 @@
virtual Representation observed_input_representation(int index) {
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 @@
HValue* length() { return OperandAt(1); }
virtual int RedefinedOperandIndex() { return 0; }
+ virtual void AddInformativeDefinitions();
DECLARE_CONCRETE_INSTRUCTION(BoundsCheck)
@@ -3337,6 +3536,8 @@
}
virtual void PrintDataTo(StringStream* stream);
+ virtual void AddInformativeDefinitions();
+
DECLARE_CONCRETE_INSTRUCTION(CompareIDAndBranch)
private:
@@ -3741,6 +3942,23 @@
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 @@
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:
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Tue Feb 12 06:00:39 2013
+++ /branches/bleeding_edge/src/hydrogen.cc Wed Feb 13 06:16:15 2013
@@ -71,7 +71,8 @@
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 @@
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 @@
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 @@
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();
=======================================
--- /branches/bleeding_edge/src/hydrogen.h Tue Feb 12 03:44:08 2013
+++ /branches/bleeding_edge/src/hydrogen.h Wed Feb 13 06:16:15 2013
@@ -91,6 +91,8 @@
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 @@
bool is_inline_return_target_;
bool is_deoptimizing_;
bool dominates_loop_successors_;
+ bool is_osr_entry_;
};
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-ia32.cc Tue Feb 12 03:44:08
2013
+++ /branches/bleeding_edge/src/ia32/lithium-ia32.cc Wed Feb 13 06:16:15
2013
@@ -1710,6 +1710,11 @@
new(zone()) LSeqStringSetChar(instr->encoding(), string, index,
value);
return DefineSameAsFirst(result);
}
+
+
+LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint*
instr) {
+ return NULL;
+}
LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) {
=======================================
--- /branches/bleeding_edge/src/mips/lithium-mips.cc Wed Feb 13 06:01:22
2013
+++ /branches/bleeding_edge/src/mips/lithium-mips.cc Wed Feb 13 06:16:15
2013
@@ -1588,6 +1588,11 @@
new(zone()) LSeqStringSetChar(instr->encoding(), string, index,
value);
return DefineAsRegister(result);
}
+
+
+LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint*
instr) {
+ return NULL;
+}
LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) {
=======================================
--- /branches/bleeding_edge/src/x64/lithium-x64.cc Tue Feb 12 03:44:08 2013
+++ /branches/bleeding_edge/src/x64/lithium-x64.cc Wed Feb 13 06:16:15 2013
@@ -1634,6 +1634,11 @@
new(zone()) LSeqStringSetChar(instr->encoding(), string, index,
value);
return DefineSameAsFirst(result);
}
+
+
+LInstruction* LChunkBuilder::DoNumericConstraint(HNumericConstraint*
instr) {
+ return NULL;
+}
LInstruction* LChunkBuilder::DoBoundsCheck(HBoundsCheck* instr) {
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
