V4 RegAlloc: store, pass, and use life-time intervals by pointer.

By storing LifeTimeIntervals by pointer (instead of by value), other
data-structures can safely use pointers too. This removes a lot of
copies, especially in vectors that act as worklists.

Also change the order of the "unhandled" list of intervals to be sorted
in descending order. Not only is this more efficient, but it also
removes the need to reverse the results of the life-range calculation
(which produces the list in exactly this order).

This change speeds up register allocation by about 20%.

Change-Id: I6ea3dcd110f250d9ccc881753dc7392510a26d87
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

3 files changed, 62 insertions, 36 deletions

diff --git a/src/qml/compiler/qv4isel_moth.cpp b/src/qml/compiler/qv4isel_moth.cpp
index 478346572e..b1debbda3d 100644
--- a/src/qml/compiler/qv4isel_moth.cpp
+++ b/src/qml/compiler/qv4isel_moth.cpp
@@ -168,22 +168,20 @@ inline bool isBoolType(IR::Expr *e)
  */
 class AllocateStackSlots: protected ConvertTemps
 {
-    const QVector<IR::LifeTimeInterval> _intervals;
-    QVector<const IR::LifeTimeInterval *> _unhandled;
-    QVector<const IR::LifeTimeInterval *> _live;
+    IR::LifeTimeIntervals::Ptr _intervals;
+    QVector<IR::LifeTimeInterval *> _unhandled;
+    QVector<IR::LifeTimeInterval *> _live;
     QBitArray _slotIsInUse;
     IR::Function *_function;
 
 public:
-    AllocateStackSlots(const QVector<IR::LifeTimeInterval> &intervals)
+    AllocateStackSlots(const IR::LifeTimeIntervals::Ptr &intervals)
         : _intervals(intervals)
-        , _slotIsInUse(intervals.size(), false)
+        , _slotIsInUse(intervals->size(), false)
         , _function(0)
     {
         _live.reserve(8);
-        _unhandled.reserve(_intervals.size());
-        for (int i = _intervals.size() - 1; i >= 0; --i)
-            _unhandled.append(&_intervals.at(i));
+        _unhandled = _intervals->intervals();
     }
 
     void forFunction(IR::Function *function)
@@ -242,7 +240,7 @@ protected:
 
             // active new ranges:
             while (!_unhandled.isEmpty()) {
-                const IR::LifeTimeInterval *lti = _unhandled.last();
+                IR::LifeTimeInterval *lti = _unhandled.last();
                 if (lti->start() > s->id())
                     break; // we're done
                 Q_ASSERT(!_stackSlotForTemp.contains(lti->temp().index));
@@ -286,7 +284,7 @@ protected:
 
         int i = _unhandled.size() - 1;
         for (; i >= 0; --i) {
-            const IR::LifeTimeInterval *lti = _unhandled[i];
+            IR::LifeTimeInterval *lti = _unhandled[i];
             if (lti->temp() == t) {
                 _live.append(lti);
                 _unhandled.remove(i);
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 82c3628b28..9c269dc122 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -3578,9 +3578,7 @@ class LifeRanges {
 
     std::vector<LiveRegs> _liveIn;
     std::vector<LifeTimeInterval *> _intervals;
-    std::vector<LifeTimeInterval *> _finishedIntervals;
-    typedef QVector<LifeTimeInterval> LifeTimeIntervals;
-    LifeTimeIntervals _sortedIntervals;
+    LifeTimeIntervals::Ptr _sortedIntervals;
 
     LifeTimeInterval &interval(const Temp *temp)
     {
@@ -3595,32 +3593,27 @@ class LifeRanges {
 public:
     LifeRanges(IR::Function *function, const QHash<BasicBlock *, BasicBlock *> &startEndLoops)
         : _intervals(function->tempCount)
+        , _sortedIntervals(LifeTimeIntervals::create(function->tempCount))
     {
         function->renumberForLifeRanges();
         _liveIn.resize(function->basicBlockCount());
-        _finishedIntervals.reserve(function->tempCount);
 
         for (int i = function->basicBlockCount() - 1; i >= 0; --i) {
             BasicBlock *bb = function->basicBlock(i);
             buildIntervals(bb, startEndLoops.value(bb, 0));
         }
 
-        _sortedIntervals.reserve(_finishedIntervals.size());
-        for (unsigned i = _finishedIntervals.size(); i > 0;)
-            if (LifeTimeInterval *lti = _finishedIntervals[--i])
-                _sortedIntervals.append(*lti);
-        qDeleteAll(_intervals);
         _intervals.clear();
     }
 
-    QVector<LifeTimeInterval> intervals() const { return _sortedIntervals; }
+    LifeTimeIntervals::Ptr intervals() const { return _sortedIntervals; }
 
     void dump() const
     {
         qout << "Life ranges:" << endl;
         qout << "Intervals:" << endl;
-        foreach (const LifeTimeInterval &range, _sortedIntervals) {
-            range.dump(qout);
+        foreach (const LifeTimeInterval *range, _sortedIntervals->intervals()) {
+            range->dump(qout);
             qout << endl;
         }
 
@@ -3673,8 +3666,8 @@ private:
                     interval(phi->targetTemp).setFrom(s);
                 } else {
                     live.erase(it);
-                    _finishedIntervals.push_back(&interval(phi->targetTemp));
                 }
+                _sortedIntervals->add(&interval(phi->targetTemp));
                 continue;
             }
             collector.collect(s);
@@ -3682,7 +3675,7 @@ private:
                 LifeTimeInterval &lti = interval(opd);
                 lti.setFrom(s);
                 live.remove(lti.temp());
-                _finishedIntervals.push_back(&lti);
+                _sortedIntervals->add(&lti);
             }
             for (unsigned i = 0, ei = collector.inputs.size(); i != ei; ++i) {
                 Temp *opd = collector.inputs[i];
@@ -3919,19 +3912,24 @@ void LifeTimeInterval::dump(QTextStream &out) const {
         out << " (register " << _reg << ")";
 }
 
-bool LifeTimeInterval::lessThan(const LifeTimeInterval &r1, const LifeTimeInterval &r2) {
-    if (r1._ranges.first().start == r2._ranges.first().start) {
-        if (r1.isSplitFromInterval() == r2.isSplitFromInterval())
-            return r1._ranges.last().end < r2._ranges.last().end;
+bool LifeTimeInterval::lessThan(const LifeTimeInterval *r1, const LifeTimeInterval *r2) {
+    if (r1->_ranges.first().start == r2->_ranges.first().start) {
+        if (r1->isSplitFromInterval() == r2->isSplitFromInterval())
+            return r1->_ranges.last().end < r2->_ranges.last().end;
         else
-            return r1.isSplitFromInterval();
+            return r1->isSplitFromInterval();
     } else
-        return r1._ranges.first().start < r2._ranges.first().start;
+        return r1->_ranges.first().start < r2->_ranges.first().start;
 }
 
-bool LifeTimeInterval::lessThanForTemp(const LifeTimeInterval &r1, const LifeTimeInterval &r2)
+bool LifeTimeInterval::lessThanForTemp(const LifeTimeInterval *r1, const LifeTimeInterval *r2)
 {
-    return r1.temp() < r2.temp();
+    return r1->temp() < r2->temp();
+}
+
+LifeTimeIntervals::~LifeTimeIntervals()
+{
+    qDeleteAll(_intervals);
 }
 
 Optimizer::Optimizer(IR::Function *function)
@@ -4079,7 +4077,7 @@ void Optimizer::convertOutOfSSA() {
     }
 }
 
-QVector<LifeTimeInterval> Optimizer::lifeTimeIntervals() const
+LifeTimeIntervals::Ptr Optimizer::lifeTimeIntervals() const
 {
     Q_ASSERT(isInSSA());
 
diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h
index 372fe5cdeb..324532afd7 100644
--- a/src/qml/compiler/qv4ssa_p.h
+++ b/src/qml/compiler/qv4ssa_p.h
@@ -43,6 +43,7 @@
 #define QV4SSA_P_H
 
 #include "qv4jsir_p.h"
+#include <QtCore/QSharedPointer>
 
 QT_BEGIN_NAMESPACE
 class QTextStream;
@@ -118,8 +119,8 @@ public:
     void setSplitFromInterval(bool isSplitFromInterval) { _isSplitFromInterval = isSplitFromInterval; }
 
     void dump(QTextStream &out) const;
-    static bool lessThan(const LifeTimeInterval &r1, const LifeTimeInterval &r2);
-    static bool lessThanForTemp(const LifeTimeInterval &r1, const LifeTimeInterval &r2);
+    static bool lessThan(const LifeTimeInterval *r1, const LifeTimeInterval *r2);
+    static bool lessThanForTemp(const LifeTimeInterval *r1, const LifeTimeInterval *r2);
 
     void validate() const {
 #if !defined(QT_NO_DEBUG)
@@ -136,6 +137,35 @@ public:
     }
 };
 
+class LifeTimeIntervals
+{
+    Q_DISABLE_COPY(LifeTimeIntervals)
+
+    LifeTimeIntervals(int sizeHint)
+    { _intervals.reserve(sizeHint + 32); }
+
+public:
+    typedef QSharedPointer<LifeTimeIntervals> Ptr;
+    static Ptr create(int sizeHint)
+    { return Ptr(new LifeTimeIntervals(sizeHint)); }
+
+    ~LifeTimeIntervals();
+
+    // takes ownership of the pointer
+    void add(LifeTimeInterval *interval)
+    { _intervals.append(interval); }
+
+    // After calling Optimizer::lifeTimeIntervals() the result will have all intervals in descending order of start position.
+    QVector<LifeTimeInterval *> intervals() const
+    { return _intervals; }
+
+    int size() const
+    { return _intervals.size(); }
+
+private:
+    QVector<LifeTimeInterval *> _intervals;
+};
+
 class Q_QML_PRIVATE_EXPORT Optimizer
 {
     Q_DISABLE_COPY(Optimizer)
@@ -151,7 +181,7 @@ public:
 
     QHash<BasicBlock *, BasicBlock *> loopStartEndBlocks() const { return startEndLoops; }
 
-    QVector<LifeTimeInterval> lifeTimeIntervals() const;
+    LifeTimeIntervals::Ptr lifeTimeIntervals() const;
 
     QSet<IR::Jump *> calculateOptionalJumps();