Reviewers: Toon Verwaest,
Description:
Environment bookkeping has linear time complexity now, not a quadratic one.
This reduces the time take for mjsunit/limit-locals from 56.8s to 15.1s in
debug
mode and from 12.0s to 1.6s in release mode.
Note that GrowableBitVector and BitVector should really be merged, and
probably
have their allocation strategy parmeterized. The current state of affairs
involving tons of checks and delegation is extremely ugly, and it is far
from
clear if all that special casing is a clear win. STL FTW! :-P
Please review this at https://codereview.chromium.org/11775016/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/data-flow.h
M src/hydrogen.h
M src/hydrogen.cc
Index: src/data-flow.h
diff --git a/src/data-flow.h b/src/data-flow.h
index
268f21e127e12629cec29aefafe73f91ee14b054..7eeb794fa0b6f08fe7086bcd7e68520daf71a23a
100644
--- a/src/data-flow.h
+++ b/src/data-flow.h
@@ -201,6 +201,19 @@ class BitVector: public ZoneObject {
class GrowableBitVector BASE_EMBEDDED {
public:
+ class Iterator BASE_EMBEDDED {
+ public:
+ Iterator(const GrowableBitVector* target, Zone* zone)
+ : it_(target->bits_ == NULL
+ ? new(zone) BitVector(1, zone)
+ : target->bits_) { }
+ bool Done() const { return it_.Done(); }
+ void Advance() { it_.Advance(); }
+ int Current() const { return it_.Current(); }
+ private:
+ BitVector::Iterator it_;
+ };
+
GrowableBitVector() : bits_(NULL) { }
bool Contains(int value) const {
@@ -213,6 +226,14 @@ class GrowableBitVector BASE_EMBEDDED {
bits_->Add(value);
}
+ void Union(const GrowableBitVector& other, Zone* zone) {
+ for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
+ Add(it.Current(), zone);
+ }
+ }
+
+ void Clear() { if (bits_ != NULL) bits_->Clear(); }
+
private:
static const int kInitialLength = 1024;
Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index
0aa063bb628b3b1cbb8fbd28eaeadff91e1cc913..f286dacbe8d43366828c5dfad4651c6056cff07c
100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -152,8 +152,11 @@ HSimulate* HBasicBlock::CreateSimulate(BailoutId
ast_id,
for (int i = 0; i < push_count; ++i) {
instr->AddPushedValue(environment->ExpressionStackAt(i));
}
- for (int i = 0; i < environment->assigned_variables()->length(); ++i) {
- int index = environment->assigned_variables()->at(i);
+ for (GrowableBitVector::Iterator it(environment->assigned_variables(),
+ zone());
+ !it.Done();
+ it.Advance()) {
+ int index = it.Current();
instr->AddAssignedValue(index, environment->Lookup(index));
}
environment->ClearHistory();
@@ -9570,7 +9573,6 @@ HEnvironment::HEnvironment(HEnvironment* outer,
Zone* zone)
: closure_(closure),
values_(0, zone),
- assigned_variables_(4, zone),
frame_type_(JS_FUNCTION),
parameter_count_(0),
specials_count_(1),
@@ -9587,7 +9589,6 @@ HEnvironment::HEnvironment(HEnvironment* outer,
HEnvironment::HEnvironment(Zone* zone)
: values_(0, zone),
- assigned_variables_(0, zone),
frame_type_(STUB),
parameter_count_(0),
specials_count_(0),
@@ -9604,7 +9605,6 @@ HEnvironment::HEnvironment(Zone* zone)
HEnvironment::HEnvironment(const HEnvironment* other, Zone* zone)
: values_(0, zone),
- assigned_variables_(0, zone),
frame_type_(JS_FUNCTION),
parameter_count_(0),
specials_count_(1),
@@ -9626,7 +9626,6 @@ HEnvironment::HEnvironment(HEnvironment* outer,
Zone* zone)
: closure_(closure),
values_(arguments, zone),
- assigned_variables_(0, zone),
frame_type_(frame_type),
parameter_count_(arguments),
local_count_(0),
@@ -9655,7 +9654,7 @@ void HEnvironment::Initialize(int parameter_count,
void HEnvironment::Initialize(const HEnvironment* other) {
closure_ = other->closure();
values_.AddAll(other->values_, zone());
- assigned_variables_.AddAll(other->assigned_variables_, zone());
+ assigned_variables_.Union(other->assigned_variables_, zone());
frame_type_ = other->frame_type_;
parameter_count_ = other->parameter_count_;
local_count_ = other->local_count_;
@@ -9699,9 +9698,7 @@ void HEnvironment::AddIncomingEdge(HBasicBlock*
block, HEnvironment* other) {
void HEnvironment::Bind(int index, HValue* value) {
ASSERT(value != NULL);
- if (!assigned_variables_.Contains(index)) {
- assigned_variables_.Add(index, zone());
- }
+ assigned_variables_.Add(index, zone());
values_[index] = value;
}
Index: src/hydrogen.h
diff --git a/src/hydrogen.h b/src/hydrogen.h
index
0837bf9634e33cc088a7a8dea90e479161c65902..eb5ec52da6350a7126ef0f45f5e4d34f5b95bdf9
100644
--- a/src/hydrogen.h
+++ b/src/hydrogen.h
@@ -450,7 +450,7 @@ class HEnvironment: public ZoneObject {
// Simple accessors.
Handle<JSFunction> closure() const { return closure_; }
const ZoneList<HValue*>* values() const { return &values_; }
- const ZoneList<int>* assigned_variables() const {
+ const GrowableBitVector* assigned_variables() const {
return &assigned_variables_;
}
FrameType frame_type() const { return frame_type_; }
@@ -557,7 +557,7 @@ class HEnvironment: public ZoneObject {
void ClearHistory() {
pop_count_ = 0;
push_count_ = 0;
- assigned_variables_.Rewind(0);
+ assigned_variables_.Clear();
}
void SetValueAt(int index, HValue* value) {
@@ -606,7 +606,7 @@ class HEnvironment: public ZoneObject {
Handle<JSFunction> closure_;
// Value array [parameters] [specials] [locals] [temporaries].
ZoneList<HValue*> values_;
- ZoneList<int> assigned_variables_;
+ GrowableBitVector assigned_variables_;
FrameType frame_type_;
int parameter_count_;
int specials_count_;
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
