Revision: 19737
Author: [email protected]
Date: Mon Mar 10 05:52:03 2014 UTC
Log: Replace the recursion in PropagateMinusZeroChecks() with a loop
and a worklist.
Also refactor the related code in preparation for fixing the
range analysis.
BUG=v8:3204
LOG=y
[email protected]
Review URL: https://codereview.chromium.org/190713002
http://code.google.com/p/v8/source/detail?r=19737
Modified:
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen-minus-zero.cc
/branches/bleeding_edge/src/hydrogen-minus-zero.h
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Fri Mar 7
09:29:07 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Mar 10
05:52:03 2014 UTC
@@ -3701,99 +3701,6 @@
if (MustPrefillWithFiller()) stream->Add("F");
stream->Add(")");
}
-
-
-HValue* HUnaryMathOperation::EnsureAndPropagateNotMinusZero(
- BitVector* visited) {
- visited->Add(id());
- if (representation().IsSmiOrInteger32() &&
- !value()->representation().Equals(representation())) {
- if (value()->range() == NULL || value()->range()->CanBeMinusZero()) {
- SetFlag(kBailoutOnMinusZero);
- }
- }
- if (RequiredInputRepresentation(0).IsSmiOrInteger32() &&
- representation().Equals(RequiredInputRepresentation(0))) {
- return value();
- }
- return NULL;
-}
-
-
-HValue* HChange::EnsureAndPropagateNotMinusZero(BitVector* visited) {
- visited->Add(id());
- if (from().IsSmiOrInteger32()) return NULL;
- if (CanTruncateToInt32()) return NULL;
- if (value()->range() == NULL || value()->range()->CanBeMinusZero()) {
- SetFlag(kBailoutOnMinusZero);
- }
- ASSERT(!from().IsSmiOrInteger32() || !to().IsSmiOrInteger32());
- return NULL;
-}
-
-
-HValue* HForceRepresentation::EnsureAndPropagateNotMinusZero(
- BitVector* visited) {
- visited->Add(id());
- return value();
-}
-
-
-HValue* HMod::EnsureAndPropagateNotMinusZero(BitVector* visited) {
- visited->Add(id());
- if (range() == NULL || range()->CanBeMinusZero()) {
- SetFlag(kBailoutOnMinusZero);
- return left();
- }
- return NULL;
-}
-
-
-HValue* HDiv::EnsureAndPropagateNotMinusZero(BitVector* visited) {
- visited->Add(id());
- if (range() == NULL || range()->CanBeMinusZero()) {
- SetFlag(kBailoutOnMinusZero);
- }
- return NULL;
-}
-
-
-HValue* HMathFloorOfDiv::EnsureAndPropagateNotMinusZero(BitVector*
visited) {
- visited->Add(id());
- SetFlag(kBailoutOnMinusZero);
- return NULL;
-}
-
-
-HValue* HMul::EnsureAndPropagateNotMinusZero(BitVector* visited) {
- visited->Add(id());
- if (range() == NULL || range()->CanBeMinusZero()) {
- SetFlag(kBailoutOnMinusZero);
- }
- return NULL;
-}
-
-
-HValue* HSub::EnsureAndPropagateNotMinusZero(BitVector* visited) {
- visited->Add(id());
- // Propagate to the left argument. If the left argument cannot be -0,
then
- // the result of the add operation cannot be either.
- if (range() == NULL || range()->CanBeMinusZero()) {
- return left();
- }
- return NULL;
-}
-
-
-HValue* HAdd::EnsureAndPropagateNotMinusZero(BitVector* visited) {
- visited->Add(id());
- // Propagate to the left argument. If the left argument cannot be -0,
then
- // the result of the sub operation cannot be either.
- if (range() == NULL || range()->CanBeMinusZero()) {
- return left();
- }
- return NULL;
-}
bool HStoreKeyed::NeedsCanonicalization() {
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Fri Mar 7 14:58:41
2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Mon Mar 10 05:52:03
2014 UTC
@@ -738,21 +738,6 @@
bool IsHeapObject() {
return representation_.IsHeapObject() || type_.IsHeapObject();
}
-
- // An operation needs to override this function iff:
- // 1) it can produce an int32 output.
- // 2) the true value of its output can potentially be minus zero.
- // The implementation must set a flag so that it bails out in the case
where
- // it would otherwise output what should be a minus zero as an int32
zero.
- // If the operation also exists in a form that takes int32 and outputs
int32
- // then the operation should return its input value so that we can
propagate
- // back. There are three operations that need to propagate back to more
than
- // one input. They are phi and binary div and mul. They always return
NULL
- // and expect the caller to take care of things.
- virtual HValue* EnsureAndPropagateNotMinusZero(BitVector* visited) {
- visited->Add(id());
- return NULL;
- }
// There are HInstructions that do not really change a value, they
// only add pieces of information to it (like bounds checks, map checks,
@@ -1718,9 +1703,6 @@
Representation required_representation);
HValue* value() { return OperandAt(0); }
-
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
virtual Representation RequiredInputRepresentation(int index)
V8_OVERRIDE {
return representation(); // Same as the output representation.
@@ -1767,8 +1749,6 @@
return CheckUsesForFlag(kAllowUndefinedAsNaN);
}
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
virtual HType CalculateInferredType() V8_OVERRIDE;
virtual HValue* Canonicalize() V8_OVERRIDE;
@@ -2631,9 +2611,6 @@
virtual void PrintDataTo(StringStream* stream) V8_OVERRIDE;
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
-
virtual Representation RequiredInputRepresentation(int index)
V8_OVERRIDE {
if (index == 0) {
return Representation::Tagged();
@@ -4111,9 +4088,6 @@
HValue*,
HValue*);
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
-
DECLARE_CONCRETE_INSTRUCTION(MathFloorOfDiv)
protected:
@@ -4713,9 +4687,6 @@
virtual bool IsCommutative() const V8_OVERRIDE {
return !representation().IsTagged() && !representation().IsExternal();
}
-
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
virtual HValue* Canonicalize() V8_OVERRIDE;
@@ -4773,9 +4744,6 @@
HValue* left,
HValue* right);
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
-
virtual HValue* Canonicalize() V8_OVERRIDE;
virtual bool TryDecompose(DecompositionResult* decomposition)
V8_OVERRIDE {
@@ -4821,9 +4789,6 @@
mul->ClearFlag(HValue::kCanOverflow);
return mul;
}
-
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
virtual HValue* Canonicalize() V8_OVERRIDE;
@@ -4862,9 +4827,6 @@
HValue* left,
HValue* right);
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
-
virtual HValue* Canonicalize() V8_OVERRIDE;
virtual void UpdateRepresentation(Representation new_rep,
@@ -4898,9 +4860,6 @@
HValue* left,
HValue* right);
- virtual HValue* EnsureAndPropagateNotMinusZero(
- BitVector* visited) V8_OVERRIDE;
-
virtual HValue* Canonicalize() V8_OVERRIDE;
virtual void UpdateRepresentation(Representation new_rep,
=======================================
--- /branches/bleeding_edge/src/hydrogen-minus-zero.cc Tue Nov 12 11:53:13
2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-minus-zero.cc Mon Mar 10 05:52:03
2014 UTC
@@ -45,17 +45,13 @@
ASSERT(change->to().IsTagged() ||
change->to().IsDouble() ||
change->to().IsSmiOrInteger32());
- ASSERT(visited_.IsEmpty());
PropagateMinusZeroChecks(change->value());
- visited_.Clear();
}
} else if (current->IsCompareMinusZeroAndBranch()) {
HCompareMinusZeroAndBranch* check =
HCompareMinusZeroAndBranch::cast(current);
if (check->value()->representation().IsSmiOrInteger32()) {
- ASSERT(visited_.IsEmpty());
PropagateMinusZeroChecks(check->value());
- visited_.Clear();
}
}
}
@@ -64,28 +60,77 @@
void HComputeMinusZeroChecksPhase::PropagateMinusZeroChecks(HValue* value)
{
- for (HValue* current = value;
- current != NULL && !visited_.Contains(current->id());
- current = current->EnsureAndPropagateNotMinusZero(&visited_)) {
- // For phis, we must propagate the check to all of its inputs.
- if (current->IsPhi()) {
- visited_.Add(current->id());
- HPhi* phi = HPhi::cast(current);
+ ASSERT(worklist_.is_empty());
+ ASSERT(in_worklist_.IsEmpty());
+
+ AddToWorklist(value);
+ while (!worklist_.is_empty()) {
+ value = worklist_.RemoveLast();
+
+ if (value->IsPhi()) {
+ // For phis, we must propagate the check to all of its inputs.
+ HPhi* phi = HPhi::cast(value);
for (int i = 0; i < phi->OperandCount(); ++i) {
- PropagateMinusZeroChecks(phi->OperandAt(i));
+ AddToWorklist(phi->OperandAt(i));
}
- break;
- }
-
- // For multiplication, division, and Math.min/max(), we must propagate
- // to the left and the right side.
- if (current->IsMul() || current->IsDiv() || current->IsMathMinMax()) {
- HBinaryOperation* operation = HBinaryOperation::cast(current);
- operation->EnsureAndPropagateNotMinusZero(&visited_);
- PropagateMinusZeroChecks(operation->left());
- PropagateMinusZeroChecks(operation->right());
+ } else if (value->IsUnaryMathOperation()) {
+ HUnaryMathOperation* instr = HUnaryMathOperation::cast(value);
+ if (instr->representation().IsSmiOrInteger32() &&
+ !instr->value()->representation().Equals(instr->representation()))
{
+ if (instr->value()->range() == NULL ||
+ instr->value()->range()->CanBeMinusZero()) {
+ instr->SetFlag(HValue::kBailoutOnMinusZero);
+ }
+ }
+ if (instr->RequiredInputRepresentation(0).IsSmiOrInteger32() &&
+ instr->representation().Equals(
+ instr->RequiredInputRepresentation(0))) {
+ AddToWorklist(instr->value());
+ }
+ } else if (value->IsChange()) {
+ HChange* instr = HChange::cast(value);
+ if (!instr->from().IsSmiOrInteger32() &&
+ !instr->CanTruncateToInt32() &&
+ (instr->value()->range() == NULL ||
+ instr->value()->range()->CanBeMinusZero())) {
+ instr->SetFlag(HValue::kBailoutOnMinusZero);
+ }
+ } else if (value->IsForceRepresentation()) {
+ HForceRepresentation* instr = HForceRepresentation::cast(value);
+ AddToWorklist(instr->value());
+ } else if (value->IsMod()) {
+ HMod* instr = HMod::cast(value);
+ if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
+ instr->SetFlag(HValue::kBailoutOnMinusZero);
+ AddToWorklist(instr->left());
+ }
+ } else if (value->IsDiv() || value->IsMul()) {
+ HBinaryOperation* instr = HBinaryOperation::cast(value);
+ if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
+ instr->SetFlag(HValue::kBailoutOnMinusZero);
+ }
+ AddToWorklist(instr->right());
+ AddToWorklist(instr->left());
+ } else if (value->IsMathFloorOfDiv()) {
+ HMathFloorOfDiv* instr = HMathFloorOfDiv::cast(value);
+ instr->SetFlag(HValue::kBailoutOnMinusZero);
+ } else if (value->IsAdd() || value->IsSub()) {
+ HBinaryOperation* instr = HBinaryOperation::cast(value);
+ if (instr->range() == NULL || instr->range()->CanBeMinusZero()) {
+ // Propagate to the left argument. If the left argument cannot be
-0,
+ // then the result of the add/sub operation cannot be either.
+ AddToWorklist(instr->left());
+ }
+ } else if (value->IsMathMinMax()) {
+ HMathMinMax* instr = HMathMinMax::cast(value);
+ AddToWorklist(instr->right());
+ AddToWorklist(instr->left());
}
}
+
+ in_worklist_.Clear();
+ ASSERT(in_worklist_.IsEmpty());
+ ASSERT(worklist_.is_empty());
}
} } // namespace v8::internal
=======================================
--- /branches/bleeding_edge/src/hydrogen-minus-zero.h Wed Jul 10 14:08:19
2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-minus-zero.h Mon Mar 10 05:52:03
2014 UTC
@@ -38,14 +38,22 @@
public:
explicit HComputeMinusZeroChecksPhase(HGraph* graph)
: HPhase("H_Compute minus zero checks", graph),
- visited_(graph->GetMaximumValueID(), zone()) { }
+ in_worklist_(graph->GetMaximumValueID(), zone()),
+ worklist_(32, zone()) {}
void Run();
private:
+ void AddToWorklist(HValue* value) {
+ if (value->CheckFlag(HValue::kBailoutOnMinusZero)) return;
+ if (in_worklist_.Contains(value->id())) return;
+ in_worklist_.Add(value->id());
+ worklist_.Add(value, zone());
+ }
void PropagateMinusZeroChecks(HValue* value);
- BitVector visited_;
+ BitVector in_worklist_;
+ ZoneList<HValue*> worklist_;
DISALLOW_COPY_AND_ASSIGN(HComputeMinusZeroChecksPhase);
};
--
--
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/d/optout.
