V4 IR: Store positions for life-time intervals outside the statement.

The statement ids are now stable, so the life-time interval calculation
can re-use information calculated by the optimizer. This re-use will
be done in a separate patch.

It also allows for changes to the numbering in a non-intrusive way. This
will also come in a later patch.

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

5 files changed, 96 insertions, 36 deletions

diff --git a/src/qml/compiler/qv4isel_moth.cpp b/src/qml/compiler/qv4isel_moth.cpp
index b1debbda3d..18877565da 100644
--- a/src/qml/compiler/qv4isel_moth.cpp
+++ b/src/qml/compiler/qv4isel_moth.cpp
@@ -174,6 +174,11 @@ class AllocateStackSlots: protected ConvertTemps
     QBitArray _slotIsInUse;
     IR::Function *_function;
 
+    int position(IR::Stmt *s) const
+    {
+        return _intervals->positionForStatement(s);
+    }
+
 public:
     AllocateStackSlots(const IR::LifeTimeIntervals::Ptr &intervals)
         : _intervals(intervals)
@@ -217,7 +222,7 @@ protected:
 
     virtual void process(IR::Stmt *s)
     {
-        Q_ASSERT(s->id() > 0);
+        Q_ASSERT(position(s) > 0);
 
 //        qDebug("L%d statement %d:", _currentBasicBlock->index, s->id);
 
@@ -227,7 +232,7 @@ protected:
             // purge ranges no longer alive:
             for (int i = 0; i < _live.size(); ) {
                 const IR::LifeTimeInterval *lti = _live.at(i);
-                if (lti->end() < s->id()) {
+                if (lti->end() < position(s)) {
 //                    qDebug() << "\t - moving temp" << lti->temp().index << "to handled, freeing slot" << _stackSlotForTemp[lti->temp().index];
                     _live.remove(i);
                     Q_ASSERT(_slotIsInUse[_stackSlotForTemp[lti->temp().index]]);
@@ -241,7 +246,7 @@ protected:
             // active new ranges:
             while (!_unhandled.isEmpty()) {
                 IR::LifeTimeInterval *lti = _unhandled.last();
-                if (lti->start() > s->id())
+                if (lti->start() > position(s))
                     break; // we're done
                 Q_ASSERT(!_stackSlotForTemp.contains(lti->temp().index));
                 _stackSlotForTemp[lti->temp().index] = allocateFreeSlot();
diff --git a/src/qml/compiler/qv4jsir.cpp b/src/qml/compiler/qv4jsir.cpp
index 8f2b2ca9e1..6b309cc282 100644
--- a/src/qml/compiler/qv4jsir.cpp
+++ b/src/qml/compiler/qv4jsir.cpp
@@ -494,21 +494,6 @@ void Function::renumberBasicBlocks()
         basicBlock(i)->changeIndex(i);
 }
 
-void Function::renumberForLifeRanges()
-{
-    //### TODO: check if this can be done in a more elegant way.
-
-    int id = 0;
-    foreach (BasicBlock *bb, basicBlocks()) {
-        foreach (Stmt *s, bb->statements()) {
-            if (s->asPhi())
-                s->_id = id + 1;
-            else
-                s->_id = ++id;
-        }
-    }
-}
-
 BasicBlock::~BasicBlock()
 {
     foreach (Stmt *s, _statements)
diff --git a/src/qml/compiler/qv4jsir_p.h b/src/qml/compiler/qv4jsir_p.h
index 6b2f4a90a7..0582a1a0ee 100644
--- a/src/qml/compiler/qv4jsir_p.h
+++ b/src/qml/compiler/qv4jsir_p.h
@@ -1045,7 +1045,6 @@ struct Function {
 
     unsigned getNewStatementId() { return _statementCount++; }
     unsigned statementCount() const { return _statementCount; }
-    void renumberForLifeRanges();
 
 private:
     QVector<BasicBlock *> _basicBlocks;
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 9149c757b6..89909fbbbf 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -3497,6 +3497,7 @@ void optimizeSSA(StatementWorklist &W, DefUses &defUses, DominatorTree &df)
     W.applyToFunction();
 }
 
+// TODO: replace this class by DefUses
 class InputOutputCollector: protected StmtVisitor, protected ExprVisitor {
     void setOutput(Temp *out)
     {
@@ -3588,12 +3589,26 @@ class LifeRanges {
         return *lti;
     }
 
+    int position(IR::Stmt *s) const
+    {
+        return _sortedIntervals->positionForStatement(s);
+    }
+
+    int start(IR::BasicBlock *bb) const
+    {
+        return _sortedIntervals->startPosition(bb);
+    }
+
+    int end(IR::BasicBlock *bb) const
+    {
+        return _sortedIntervals->endPosition(bb);
+    }
+
 public:
     LifeRanges(IR::Function *function, const QHash<BasicBlock *, BasicBlock *> &startEndLoops)
         : _intervals(function->tempCount)
-        , _sortedIntervals(LifeTimeIntervals::create(function->tempCount))
     {
-        function->renumberForLifeRanges();
+        _sortedIntervals = LifeTimeIntervals::create(function);
         _liveIn.resize(function->basicBlockCount());
 
         for (int i = function->basicBlockCount() - 1; i >= 0; --i) {
@@ -3652,7 +3667,7 @@ private:
         QVector<Stmt *> statements = bb->statements();
 
         foreach (const Temp &opd, live)
-            interval(&opd).addRange(statements.first()->id(), statements.last()->id());
+            interval(&opd).addRange(start(bb), end(bb));
 
         InputOutputCollector collector;
         for (int i = statements.size() - 1; i >= 0; --i) {
@@ -3661,7 +3676,7 @@ private:
                 LiveRegs::iterator it = live.find(*phi->targetTemp);
                 if (it == live.end()) {
                     // a phi node target that is only defined, but never used
-                    interval(phi->targetTemp).setFrom(s);
+                    interval(phi->targetTemp).setFrom(position(s));
                 } else {
                     live.erase(it);
                 }
@@ -3671,20 +3686,20 @@ private:
             collector.collect(s);
             if (Temp *opd = collector.output) {
                 LifeTimeInterval &lti = interval(opd);
-                lti.setFrom(s);
+                lti.setFrom(position(s));
                 live.remove(lti.temp());
                 _sortedIntervals->add(&lti);
             }
             for (unsigned i = 0, ei = collector.inputs.size(); i != ei; ++i) {
                 Temp *opd = collector.inputs[i];
-                interval(opd).addRange(statements.first()->id(), s->id());
+                interval(opd).addRange(start(bb), position(s));
                 live.insert(*opd);
             }
         }
 
         if (loopEnd) { // Meaning: bb is a loop header, because loopEnd is set to non-null.
             foreach (const Temp &opd, live)
-                interval(&opd).addRange(statements.first()->id(), loopEnd->terminator()->id());
+                interval(&opd).addRange(start(bb), position(loopEnd->terminator()));
         }
 
         _liveIn[bb->index()] = live;
@@ -3782,15 +3797,15 @@ private:
 };
 } // anonymous namespace
 
-void LifeTimeInterval::setFrom(Stmt *from) {
-    Q_ASSERT(from && from->id() > 0);
+void LifeTimeInterval::setFrom(int from) {
+    Q_ASSERT(from > 0);
 
     if (_ranges.isEmpty()) { // this is the case where there is no use, only a define
-        _ranges.push_front(Range(from->id(), from->id()));
+        _ranges.push_front(Range(from, from));
         if (_end == Invalid)
-            _end = from->id();
+            _end = from;
     } else {
-        _ranges.first().start = from->id();
+        _ranges.first().start = from;
     }
 }
 
@@ -3925,6 +3940,26 @@ bool LifeTimeInterval::lessThanForTemp(const LifeTimeInterval *r1, const LifeTim
     return r1->temp() < r2->temp();
 }
 
+LifeTimeIntervals::LifeTimeIntervals(IR::Function *function)
+    : _basicBlockPosition(function->basicBlockCount())
+    , _positionForStatement(function->statementCount(), IR::Stmt::InvalidId)
+{
+    _intervals.reserve(function->tempCount + 32);
+
+    int id = 1;
+    foreach (BasicBlock *bb, function->basicBlocks()) {
+        _basicBlockPosition[bb->index()].start = id;
+
+        foreach (Stmt *s, bb->statements()) {
+            _positionForStatement[s->id()] = id;
+            if (!s->asPhi())
+                ++id;
+        }
+
+        _basicBlockPosition[bb->index()].end = id - 1;
+    }
+}
+
 LifeTimeIntervals::~LifeTimeIntervals()
 {
     qDeleteAll(_intervals);
diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h
index 208aabcdd8..598b801cdd 100644
--- a/src/qml/compiler/qv4ssa_p.h
+++ b/src/qml/compiler/qv4ssa_p.h
@@ -91,7 +91,7 @@ public:
     Temp temp() const { return _temp; }
     bool isFP() const { return _temp.type == IR::DoubleType; }
 
-    void setFrom(Stmt *from);
+    void setFrom(int from);
     void addRange(int from, int to);
     const Ranges &ranges() const { return _ranges; }
 
@@ -141,13 +141,12 @@ class LifeTimeIntervals
 {
     Q_DISABLE_COPY(LifeTimeIntervals)
 
-    LifeTimeIntervals(int sizeHint)
-    { _intervals.reserve(sizeHint + 32); }
+    LifeTimeIntervals(IR::Function *function);
 
 public:
     typedef QSharedPointer<LifeTimeIntervals> Ptr;
-    static Ptr create(int sizeHint)
-    { return Ptr(new LifeTimeIntervals(sizeHint)); }
+    static Ptr create(IR::Function *function)
+    { return Ptr(new LifeTimeIntervals(function)); }
 
     ~LifeTimeIntervals();
 
@@ -162,7 +161,44 @@ public:
     int size() const
     { return _intervals.size(); }
 
+    int positionForStatement(Stmt *stmt) const
+    {
+        Q_ASSERT(stmt->id() >= 0);
+        if (static_cast<unsigned>(stmt->id()) < _positionForStatement.size())
+            return _positionForStatement[stmt->id()];
+
+        return Stmt::InvalidId;
+    }
+
+    int startPosition(BasicBlock *bb) const
+    {
+        Q_ASSERT(bb->index() >= 0);
+        Q_ASSERT(static_cast<unsigned>(bb->index()) < _basicBlockPosition.size());
+
+        return _basicBlockPosition.at(bb->index()).start;
+    }
+
+    int endPosition(BasicBlock *bb) const
+    {
+        Q_ASSERT(bb->index() >= 0);
+        Q_ASSERT(static_cast<unsigned>(bb->index()) < _basicBlockPosition.size());
+
+        return _basicBlockPosition.at(bb->index()).end;
+    }
+
 private:
+    struct BasicBlockPositions {
+        int start;
+        int end;
+
+        BasicBlockPositions()
+            : start(IR::Stmt::InvalidId)
+            , end(IR::Stmt::InvalidId)
+        {}
+    };
+
+    std::vector<BasicBlockPositions> _basicBlockPosition;
+    std::vector<int> _positionForStatement;
     QVector<LifeTimeInterval *> _intervals;
 };