Revision: 13327
Author: [email protected]
Date: Mon Jan 7 07:28:20 2013
Log: 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
Review URL: https://codereview.chromium.org/11775016
http://code.google.com/p/v8/source/detail?r=13327
Modified:
/branches/bleeding_edge/src/data-flow.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/hydrogen.h
=======================================
--- /branches/bleeding_edge/src/data-flow.h Fri Jan 4 04:48:18 2013
+++ /branches/bleeding_edge/src/data-flow.h Mon Jan 7 07:28:20 2013
@@ -201,6 +201,19 @@
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 {
@@ -212,6 +225,14 @@
EnsureCapacity(value, zone);
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;
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Mon Jan 7 04:14:36 2013
+++ /branches/bleeding_edge/src/hydrogen.cc Mon Jan 7 07:28:20 2013
@@ -152,8 +152,11 @@
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 @@
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(Zone* zone)
: values_(0, zone),
- assigned_variables_(0, zone),
frame_type_(STUB),
parameter_count_(0),
specials_count_(0),
@@ -9604,7 +9605,6 @@
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 @@
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(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::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;
}
=======================================
--- /branches/bleeding_edge/src/hydrogen.h Tue Dec 18 08:25:45 2012
+++ /branches/bleeding_edge/src/hydrogen.h Mon Jan 7 07:28:20 2013
@@ -450,7 +450,7 @@
// 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 @@
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 @@
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
