V4: stack slot allocator for the interpreter.

Use the life-time intervals to track which temps go out of scope, in
order to re-use the stack-slots they occupied. This reduces the memory
consumption on the JavaScript stack and allows for deeper call stacks.

For the ECMA tests, this reduces the number of slots needed for the
main/entry function from more than 650 to about 10 (depending on the
test).

Change-Id: Iff4044f5ff7f25e1f88ff1a04f4e80dd99a67590
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

4 files changed, 205 insertions, 15 deletions

diff --git a/src/qml/compiler/qv4isel_moth.cpp b/src/qml/compiler/qv4isel_moth.cpp
index 09f4a88b30..130725f3ed 100644
--- a/src/qml/compiler/qv4isel_moth.cpp
+++ b/src/qml/compiler/qv4isel_moth.cpp
@@ -151,6 +151,167 @@ inline bool isBoolType(V4IR::Expr *e)
     return (e->type == V4IR::BoolType);
 }
 
+/*
+ * stack slot allocation:
+ *
+ * foreach bb do
+ *   foreach stmt do
+ *     if the current statement is not a phi-node:
+ *       purge ranges that end before the current statement
+ *       check for life ranges to activate, and if they don't have a stackslot associated then allocate one
+ *       renumber temps to stack
+ *     for phi nodes: check if all temps (src+dst) are assigned stack slots and marked as allocated
+ *     if it's a jump:
+ *       foreach phi node in the successor:
+ *         allocate slots for each temp (both sources and targets) if they don't have one allocated already
+ *         insert moves before the jump
+ */
+class AllocateStackSlots: protected ConvertTemps
+{
+    const QVector<V4IR::LifeTimeInterval> _intervals;
+    QVector<const V4IR::LifeTimeInterval *> _unhandled;
+    QVector<const V4IR::LifeTimeInterval *> _live;
+    QBitArray _slotIsInUse;
+    V4IR::Function *_function;
+
+public:
+    AllocateStackSlots(const QVector<V4IR::LifeTimeInterval> &intervals)
+        : _intervals(intervals)
+        , _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));
+    }
+
+    void forFunction(V4IR::Function *function)
+    {
+        V4IR::Optimizer::showMeTheCode(function);
+        _function = function;
+        toStackSlots(function);
+
+//        QTextStream os(stdout, QIODevice::WriteOnly);
+//        os << "Frame layout:" << endl;
+//        foreach (int t, _stackSlotForTemp.keys()) {
+//            os << "\t" << t << " -> " << _stackSlotForTemp[t] << endl;
+//        }
+    }
+
+protected:
+    virtual int allocateFreeSlot()
+    {
+        for (int i = 0, ei = _slotIsInUse.size(); i != ei; ++i) {
+            if (!_slotIsInUse[i]) {
+                if (_nextUnusedStackSlot <= i) {
+                    Q_ASSERT(_nextUnusedStackSlot == i);
+                    _nextUnusedStackSlot = i + 1;
+                }
+                _slotIsInUse[i] = true;
+                return i;
+            }
+        }
+
+        Q_UNREACHABLE();
+        return -1;
+    }
+
+    virtual void process(V4IR::Stmt *s)
+    {
+        Q_ASSERT(s->id > 0);
+
+//        qDebug("L%d statement %d:", _currentBasicBlock->index, s->id);
+
+        if (V4IR::Phi *phi = s->asPhi()) {
+            visitPhi(phi);
+        } else {
+            // purge ranges no longer alive:
+            for (int i = 0; i < _live.size(); ) {
+                const V4IR::LifeTimeInterval *lti = _live.at(i);
+                if (lti->end() < s->id) {
+//                    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]]);
+                    _slotIsInUse[_stackSlotForTemp[lti->temp().index]] = false;
+                    continue;
+                } else {
+                    ++i;
+                }
+            }
+
+            // active new ranges:
+            while (!_unhandled.isEmpty()) {
+                const V4IR::LifeTimeInterval *lti = _unhandled.last();
+                if (lti->start() > s->id)
+                    break; // we're done
+                Q_ASSERT(!_stackSlotForTemp.contains(lti->temp().index));
+                _stackSlotForTemp[lti->temp().index] = allocateFreeSlot();
+//                qDebug() << "\t - activating temp" << lti->temp().index << "on slot" << _stackSlotForTemp[lti->temp().index];
+                _live.append(lti);
+                _unhandled.removeLast();
+            }
+
+            s->accept(this);
+        }
+
+        if (V4IR::Jump *jump = s->asJump()) {
+            V4IR::MoveMapping moves;
+            foreach (V4IR::Stmt *succStmt, jump->target->statements) {
+                if (V4IR::Phi *phi = succStmt->asPhi()) {
+                    forceActivation(*phi->targetTemp);
+                    for (int i = 0, ei = phi->d->incoming.size(); i != ei; ++i) {
+                        V4IR::Expr *e = phi->d->incoming[i];
+                        if (V4IR::Temp *t = e->asTemp()) {
+                            forceActivation(*t);
+                        }
+                        if (jump->target->in[i] == _currentBasicBlock)
+                            moves.add(phi->d->incoming[i], phi->targetTemp);
+                    }
+                } else {
+                    break;
+                }
+            }
+            moves.order();
+            QList<V4IR::Move *> newMoves = moves.insertMoves(_currentBasicBlock, _function, true);
+            foreach (V4IR::Move *move, newMoves)
+                move->accept(this);
+        }
+    }
+
+    void forceActivation(const V4IR::Temp &t)
+    {
+        if (_stackSlotForTemp.contains(t.index))
+            return;
+
+        int i = _unhandled.size() - 1;
+        for (; i >= 0; --i) {
+            const V4IR::LifeTimeInterval *lti = _unhandled[i];
+            if (lti->temp() == t) {
+                _live.append(lti);
+                _unhandled.remove(i);
+                break;
+            }
+        }
+        Q_ASSERT(i >= 0); // check that we always found the entry
+
+        _stackSlotForTemp[t.index] = allocateFreeSlot();
+//        qDebug() << "\t - force activating temp" << t.index << "on slot" << _stackSlotForTemp[t.index];
+    }
+
+    virtual void visitPhi(V4IR::Phi *phi)
+    {
+        Q_UNUSED(phi);
+#if !defined(QT_NO_DEBUG)
+        Q_ASSERT(_stackSlotForTemp.contains(phi->targetTemp->index));
+        Q_ASSERT(_slotIsInUse[_stackSlotForTemp[phi->targetTemp->index]]);
+        foreach (V4IR::Expr *e, phi->d->incoming) {
+            if (V4IR::Temp *t = e->asTemp())
+                Q_ASSERT(_stackSlotForTemp.contains(t->index));
+        }
+#endif // defined(QT_NO_DEBUG)
+    }
+};
 } // anonymous namespace
 
 InstructionSelection::InstructionSelection(QQmlEnginePrivate *qmlEngine, QV4::ExecutableAllocator *execAllocator, V4IR::Module *module, QV4::Compiler::JSUnitGenerator *jsGenerator)
@@ -195,10 +356,19 @@ void InstructionSelection::run(int functionIndex)
     V4IR::Optimizer opt(_function);
     opt.run(qmlEngine);
     if (opt.isInSSA()) {
-        opt.convertOutOfSSA();
+        static const bool doStackSlotAllocation =
+                qgetenv("QV4_NO_INTERPRETER_STACK_SLOT_ALLOCATION").isEmpty();
+
+        if (doStackSlotAllocation) {
+            AllocateStackSlots(opt.lifeRanges()).forFunction(_function);
+        } else {
+            opt.convertOutOfSSA();
+            ConvertTemps().toStackSlots(_function);
+        }
         opt.showMeTheCode(_function);
+    } else {
+        ConvertTemps().toStackSlots(_function);
     }
-    ConvertTemps().toStackSlots(_function);
 
     QSet<V4IR::Jump *> removableJumps = opt.calculateOptionalJumps();
     qSwap(_removableJumps, removableJumps);
diff --git a/src/qml/compiler/qv4isel_util_p.h b/src/qml/compiler/qv4isel_util_p.h
index 1d7a99941e..637746dce1 100644
--- a/src/qml/compiler/qv4isel_util_p.h
+++ b/src/qml/compiler/qv4isel_util_p.h
@@ -97,38 +97,52 @@ inline QV4::Primitive convertToValue(V4IR::Const *c)
 
 class ConvertTemps: protected V4IR::StmtVisitor, protected V4IR::ExprVisitor
 {
-    int _nextFreeStackSlot;
-    QHash<V4IR::Temp, int> _stackSlotForTemp;
-
     void renumber(V4IR::Temp *t)
     {
         if (t->kind != V4IR::Temp::VirtualRegister)
             return;
 
-        int stackSlot = _stackSlotForTemp.value(*t, -1);
+        int stackSlot = _stackSlotForTemp.value(t->index, -1);
         if (stackSlot == -1) {
-            stackSlot = _nextFreeStackSlot++;
-            _stackSlotForTemp[*t] = stackSlot;
+            stackSlot = allocateFreeSlot();
+            _stackSlotForTemp[t->index] = stackSlot;
         }
 
         t->kind = V4IR::Temp::StackSlot;
         t->index = stackSlot;
     }
 
+protected:
+    int _nextUnusedStackSlot;
+    QHash<int, int> _stackSlotForTemp;
+    V4IR::BasicBlock *_currentBasicBlock;
+    virtual int allocateFreeSlot()
+    {
+        return _nextUnusedStackSlot++;
+    }
+
+    virtual void process(V4IR::Stmt *s)
+    {
+        s->accept(this);
+    }
+
 public:
     ConvertTemps()
-        : _nextFreeStackSlot(0)
+        : _nextUnusedStackSlot(0)
+        , _currentBasicBlock(0)
     {}
 
     void toStackSlots(V4IR::Function *function)
     {
         _stackSlotForTemp.reserve(function->tempCount);
 
-        foreach (V4IR::BasicBlock *bb, function->basicBlocks)
+        foreach (V4IR::BasicBlock *bb, function->basicBlocks) {
+            _currentBasicBlock = bb;
             foreach (V4IR::Stmt *s, bb->statements)
-                s->accept(this);
+                process(s);
+        }
 
-        function->tempCount = _nextFreeStackSlot;
+        function->tempCount = _nextUnusedStackSlot;
     }
 
 protected:
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index d9cc51fc82..3ffaca5134 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -3994,15 +3994,21 @@ void MoveMapping::order()
     qSwap(_moves, output);
 }
 
-void MoveMapping::insertMoves(BasicBlock *bb, Function *function, bool atEnd) const
+QList<V4IR::Move *> MoveMapping::insertMoves(BasicBlock *bb, Function *function, bool atEnd) const
 {
+    QList<V4IR::Move *> newMoves;
+    newMoves.reserve(_moves.size());
+
     int insertionPoint = atEnd ? bb->statements.size() - 1 : 0;
     foreach (const Move &m, _moves) {
         V4IR::Move *move = function->New<V4IR::Move>();
-        move->init(m.to, m.from);
+        move->init(clone(m.to, function), clone(m.from, function));
         move->swap = m.needsSwap;
         bb->statements.insert(insertionPoint++, move);
+        newMoves.append(move);
     }
+
+    return newMoves;
 }
 
 void MoveMapping::dump() const
diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h
index 2ec81b9577..95bed40a27 100644
--- a/src/qml/compiler/qv4ssa_p.h
+++ b/src/qml/compiler/qv4ssa_p.h
@@ -188,7 +188,7 @@ class MoveMapping
 public:
     void add(Expr *from, Temp *to);
     void order();
-    void insertMoves(BasicBlock *bb, Function *function, bool atEnd) const;
+    QList<V4IR::Move *> insertMoves(BasicBlock *bb, Function *function, bool atEnd) const;
 
     void dump() const;