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>

6 files changed, 128 insertions, 56 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;
 };
 
diff --git a/src/qml/jit/qv4regalloc.cpp b/src/qml/jit/qv4regalloc.cpp
index 144a700903..36c5761dbc 100644
--- a/src/qml/jit/qv4regalloc.cpp
+++ b/src/qml/jit/qv4regalloc.cpp
@@ -86,17 +86,24 @@ class RegAllocInfo: public IRDecoder
         bool isValid() const { return defStmt != 0; } // 0 is invalid, as stmt numbers start at 1.
     };
 
+    IR::LifeTimeIntervals::Ptr _lifeTimeIntervals;
     Stmt *_currentStmt;
     std::vector<Def> _defs;
     std::vector<QList<Use> > _uses;
     std::vector<int> _calls;
     std::vector<QList<Temp> > _hints;
 
+    int position(Stmt *s) const
+    {
+        return _lifeTimeIntervals->positionForStatement(s);
+    }
+
 public:
     RegAllocInfo(): _currentStmt(0) {}
 
-    void collect(IR::Function *function)
+    void collect(IR::Function *function, const IR::LifeTimeIntervals::Ptr &lifeTimeIntervals)
     {
+        _lifeTimeIntervals = lifeTimeIntervals;
         _defs.resize(function->tempCount);
         _uses.resize(function->tempCount);
         _calls.reserve(function->statementCount() / 3);
@@ -104,7 +111,7 @@ public:
 
         foreach (BasicBlock *bb, function->basicBlocks()) {
             foreach (Stmt *s, bb->statements()) {
-                Q_ASSERT(s->id() > 0);
+                Q_ASSERT(position(s) != Stmt::InvalidId);
                 _currentStmt = s;
                 s->accept(this);
             }
@@ -641,19 +648,19 @@ private:
             break;
         }
 
-        _defs[t->index] = Def(_currentStmt->id(), canHaveReg, isPhiTarget);
+        _defs[t->index] = Def(position(_currentStmt), canHaveReg, isPhiTarget);
     }
 
     void addUses(Expr *e, Use::RegisterFlag flag)
     {
-        Q_ASSERT(_currentStmt->id() > 0);
+        Q_ASSERT(position(_currentStmt) > 0);
         if (!e)
             return;
         Temp *t = e->asTemp();
         if (!t)
             return;
         if (t && t->kind == Temp::VirtualRegister)
-            _uses[t->index].append(Use(_currentStmt->id(), flag));
+            _uses[t->index].append(Use(position(_currentStmt), flag));
     }
 
     void addUses(ExprList *l, Use::RegisterFlag flag)
@@ -664,7 +671,7 @@ private:
 
     void addCall()
     {
-        _calls.push_back(_currentStmt->id());
+        _calls.push_back(position(_currentStmt));
     }
 
     void addHint(Expr *hinted, Temp *hint1, Temp *hint2 = 0)
@@ -699,7 +706,7 @@ namespace {
 class ResolutionPhase: protected StmtVisitor, protected ExprVisitor {
     Q_DISABLE_COPY(ResolutionPhase)
 
-    QVector<LifeTimeInterval *> _intervals;
+    LifeTimeIntervals::Ptr _intervals;
     QVector<LifeTimeInterval *> _unprocessed;
     IR::Function *_function;
 #if !defined(QT_NO_DEBUG)
@@ -718,7 +725,7 @@ class ResolutionPhase: protected StmtVisitor, protected ExprVisitor {
     QHash<BasicBlock *, QList<const LifeTimeInterval *> > _liveAtEnd;
 
 public:
-    ResolutionPhase(const QVector<LifeTimeInterval *> &intervals, IR::Function *function, RegAllocInfo *info,
+    ResolutionPhase(const QVector<LifeTimeInterval *> &unprocessed, const LifeTimeIntervals::Ptr &intervals, IR::Function *function, RegAllocInfo *info,
                     const std::vector<int> &assignedSpillSlots,
                     const QVector<int> &intRegs, const QVector<int> &fpRegs)
         : _intervals(intervals)
@@ -734,7 +741,7 @@ public:
         Q_UNUSED(info)
 #endif
 
-        _unprocessed = _intervals;
+        _unprocessed = unprocessed;
         _liveAtStart.reserve(function->basicBlockCount());
         _liveAtEnd.reserve(function->basicBlockCount());
     }
@@ -746,6 +753,11 @@ public:
     }
 
 private:
+    int position(Stmt *s) const
+    {
+        return _intervals->positionForStatement(s);
+    }
+
     void renumber()
     {
         foreach (BasicBlock *bb, _function->basicBlocks()) {
@@ -809,7 +821,7 @@ private:
 
         if (i->reg() != LifeTimeInterval::Invalid) {
             // check if we need to generate spill/unspill instructions
-            if (i->start() == _currentStmt->id()) {
+            if (i->start() == position(_currentStmt)) {
                 if (i->isSplitFromInterval()) {
                     int pReg = platformRegister(*i);
                     _loads.append(generateUnspill(i->temp(), pReg));
@@ -829,7 +841,7 @@ private:
             // for phi nodes, only activate the range belonging to that node
             for (int it = 0, eit = _unprocessed.size(); it != eit; ++it) {
                 const LifeTimeInterval *i = _unprocessed.at(it);
-                if (i->start() > _currentStmt->id())
+                if (i->start() > position(_currentStmt))
                     break;
                 if (i->temp() == *phi->targetTemp) {
                     activate(i);
@@ -842,7 +854,7 @@ private:
 
         while (!_unprocessed.isEmpty()) {
             const LifeTimeInterval *i = _unprocessed.first();
-            if (i->start() > _currentStmt->id())
+            if (i->start() > position(_currentStmt))
                 break;
 
             activate(i);
@@ -853,7 +865,7 @@ private:
 
     void cleanOldIntervals()
     {
-        const int id = _currentStmt->id();
+        const int id = position(_currentStmt);
         QMutableHashIterator<Temp, const LifeTimeInterval *> it(_intervalForTemp);
         while (it.hasNext()) {
             const LifeTimeInterval *i = it.next().value();
@@ -879,13 +891,13 @@ private:
 
         MoveMapping mapping;
 
-        const int predecessorEnd = predecessor->terminator()->id(); // the terminator is always last and always has an id set...
+        const int predecessorEnd = position(predecessor->terminator()); // the terminator is always last and always has an id set...
         Q_ASSERT(predecessorEnd > 0); // ... but we verify it anyway for good measure.
 
         int successorStart = -1;
         foreach (Stmt *s, successor->statements()) {
-            if (s && s->id() > 0) {
-                successorStart = s->id();
+            if (s && position(s) != Stmt::InvalidId) {
+                successorStart = position(s);
                 break;
             }
         }
@@ -901,7 +913,7 @@ private:
 
             if (it->start() == successorStart) {
                 foreach (Stmt *s, successor->statements()) {
-                    if (!s || s->id() < 1)
+                    if (!s || position(s) == Stmt::InvalidId)
                         continue;
                     if (Phi *phi = s->asPhi()) {
                         if (*phi->targetTemp == it->temp()) {
@@ -1056,7 +1068,7 @@ protected:
 
         const LifeTimeInterval *i = _intervalForTemp[*t];
         Q_ASSERT(i->isValid());
-        if (i->reg() != LifeTimeInterval::Invalid && i->covers(_currentStmt->id())) {
+        if (i->reg() != LifeTimeInterval::Invalid && i->covers(position(_currentStmt))) {
             int pReg = platformRegister(*i);
             t->kind = Temp::PhysicalRegister;
             t->index = pReg;
@@ -1130,7 +1142,7 @@ void RegisterAllocator::run(IR::Function *function, const Optimizer &opt)
     _handled.reserve(_unhandled.size());
 
     _info.reset(new RegAllocInfo);
-    _info->collect(function);
+    _info->collect(function, _lifeTimeIntervals);
 
     if (DebugRegAlloc) {
         QTextStream qout(stdout, QIODevice::WriteOnly);
@@ -1154,7 +1166,7 @@ void RegisterAllocator::run(IR::Function *function, const Optimizer &opt)
         dump();
 
     std::sort(_handled.begin(), _handled.end(), LifeTimeInterval::lessThan);
-    ResolutionPhase(_handled, function, _info.data(), _assignedSpillSlots, _normalRegisters, _fpRegisters).run();
+    ResolutionPhase(_handled, _lifeTimeIntervals, function, _info.data(), _assignedSpillSlots, _normalRegisters, _fpRegisters).run();
 
     function->tempCount = *std::max_element(_assignedSpillSlots.begin(), _assignedSpillSlots.end()) + 1;