Reviewers: Jarin (OOO), Benedikt Meurer,
Description:
[turbofan] LiveRange splinter merging optimizations.
A few benchmarks, e.g. Massive/SQLLite, turn out to be
sensitive to compile time. Upon analysis, splinter merging
and then splinter creation (splitting) appear to be the main
contributors to such regressions. This change tackles main
sources of regression in Merging. Profiling SQLLite shows,
after this change, Merging as noise (down from main C++
contributor of samples)
BUG=
Please review this at https://codereview.chromium.org/1318893002/
Base URL: https://chromium.googlesource.com/v8/v8.git@master
Affected files (+28, -24 lines):
M src/compiler/register-allocator.h
M src/compiler/register-allocator.cc
Index: src/compiler/register-allocator.cc
diff --git a/src/compiler/register-allocator.cc
b/src/compiler/register-allocator.cc
index
ebfb932b086be5d3a16cd437a46884f3c418f006..a36ea361208f73c2ee91a2abcb0e6c002eecb313
100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -427,7 +427,9 @@ LiveRange* LiveRange::SplitAt(LifetimePosition
position, Zone* zone) {
child->top_level_ = TopLevel();
child->next_ = next_;
next_ = child;
-
+ if (child->next() == nullptr) {
+ TopLevel()->set_last_child(child);
+ }
return child;
}
@@ -524,6 +526,7 @@ void LiveRange::AppendAsChild(TopLevelLiveRange* other)
{
other->UpdateParentForAllChildren(TopLevel());
TopLevel()->UpdateSpillRangePostMerge(other);
+ TopLevel()->set_last_child(other->last_child());
}
@@ -666,7 +669,9 @@ TopLevelLiveRange::TopLevelLiveRange(int vreg,
MachineType machine_type)
spill_operand_(nullptr),
spills_at_definition_(nullptr),
spilled_in_deferred_blocks_(false),
- spill_start_index_(kMaxInt) {
+ spill_start_index_(kMaxInt),
+ last_child_(this),
+ last_insertion_point_(this) {
bits_ |= SpillTypeField::encode(SpillType::kNoSpillType);
}
@@ -882,22 +887,15 @@ void
TopLevelLiveRange::UpdateSpillRangePostMerge(TopLevelLiveRange* merged) {
}
-LiveRange* TopLevelLiveRange::GetLastChild() {
- LiveRange* ret = this;
- for (; ret->next() != nullptr; ret = ret->next()) {
- }
- return ret;
-}
-
-
void TopLevelLiveRange::Merge(TopLevelLiveRange* other,
RegisterAllocationData* data) {
DCHECK(Start() < other->Start());
+ DCHECK(other->splintered_from() == this);
data->live_ranges()[other->vreg()] = nullptr;
- LiveRange* last_other = other->GetLastChild();
- LiveRange* last_me = GetLastChild();
+ LiveRange* last_other = other->last_child();
+ LiveRange* last_me = last_child();
// Simple case: we just append at the end.
if (last_me->End() <= other->Start()) return
last_me->AppendAsChild(other);
@@ -906,28 +904,32 @@ void TopLevelLiveRange::Merge(TopLevelLiveRange*
other,
// In the more general case, we need to find the ranges between which to
// insert.
- LiveRange* insertion_point = this;
- for (; insertion_point->next() != nullptr &&
- insertion_point->next()->Start() <= other->Start();
- insertion_point = insertion_point->next()) {
+ if (other->Start() < last_insertion_point_->Start()) {
+ last_insertion_point_ = this;
+ }
+
+ for (; last_insertion_point_->next() != nullptr &&
+ last_insertion_point_->next()->Start() <= other->Start();
+ last_insertion_point_ = last_insertion_point_->next()) {
}
// When we splintered the original range, we reconstituted the original
range
// into one range without children, but with discontinuities. To merge
the
// splinter back in, we need to split the range - or a child obtained
after
// register allocation splitting.
- LiveRange* after = insertion_point->next();
- if (insertion_point->End() > other->Start()) {
+ LiveRange* after = last_insertion_point_->next();
+ if (last_insertion_point_->End() > other->Start()) {
LiveRange* new_after =
- insertion_point->SplitAt(other->Start(), data->allocation_zone());
- new_after->set_spilled(insertion_point->spilled());
+ last_insertion_point_->SplitAt(other->Start(),
data->allocation_zone());
+ new_after->set_spilled(last_insertion_point_->spilled());
if (!new_after->spilled())
-
new_after->set_assigned_register(insertion_point->assigned_register());
+ new_after->set_assigned_register(
+ last_insertion_point_->assigned_register());
after = new_after;
}
last_other->next_ = after;
- insertion_point->next_ = other;
+ last_insertion_point_->next_ = other;
other->UpdateParentForAllChildren(TopLevel());
TopLevel()->UpdateSpillRangePostMerge(other);
}
Index: src/compiler/register-allocator.h
diff --git a/src/compiler/register-allocator.h
b/src/compiler/register-allocator.h
index
ff4ddd0c741403528424b3afc66e259f6ff4acae..5c8468cd8fad2d6d08d5c2fb80bd989a90df89e7
100644
--- a/src/compiler/register-allocator.h
+++ b/src/compiler/register-allocator.h
@@ -545,6 +545,8 @@ class TopLevelLiveRange final : public LiveRange {
SpillAtDefinitionList* spills_at_definition() const {
return spills_at_definition_;
}
+ void set_last_child(LiveRange* range) { last_child_ = range; }
+ LiveRange* last_child() const { return last_child_; }
private:
typedef BitField<bool, 1, 1> HasSlotUseField;
@@ -552,8 +554,6 @@ class TopLevelLiveRange final : public LiveRange {
typedef BitField<bool, 3, 1> IsNonLoopPhiField;
typedef BitField<SpillType, 4, 2> SpillTypeField;
- LiveRange* GetLastChild();
-
int vreg_;
int last_child_id_;
TopLevelLiveRange* splintered_from_;
@@ -567,6 +567,8 @@ class TopLevelLiveRange final : public LiveRange {
// just for spill in a single deferred block.
bool spilled_in_deferred_blocks_;
int spill_start_index_;
+ LiveRange* last_child_;
+ LiveRange* last_insertion_point_;
DISALLOW_COPY_AND_ASSIGN(TopLevelLiveRange);
};
--
--
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.
