1 files changed, 178 insertions, 3 deletions

diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h
index e608c08591..db8b6edd1a 100644
--- a/src/qml/compiler/qv4ssa_p.h
+++ b/src/qml/compiler/qv4ssa_p.h
@@ -52,6 +52,8 @@
 //
 
 #include "qv4jsir_p.h"
+#include "qv4isel_util_p.h"
+#include <private/qv4util_p.h>
 #include <QtCore/QSharedPointer>
 
 QT_BEGIN_NAMESPACE
@@ -74,7 +76,7 @@ public:
 
         bool covers(int position) const { return start <= position && position <= end; }
     };
-    typedef QVector<Range> Ranges;
+    typedef QVarLengthArray<Range, 4> Ranges;
 
 private:
     Temp _temp;
@@ -88,7 +90,7 @@ public:
     enum { InvalidPosition = -1 };
     enum { InvalidRegister = -1 };
 
-    explicit LifeTimeInterval(int rangeCapacity = 2)
+    explicit LifeTimeInterval(int rangeCapacity = 4)
         : _end(InvalidPosition)
         , _reg(InvalidRegister)
         , _isFixedInterval(0)
@@ -145,6 +147,17 @@ public:
     }
 };
 
+inline 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();
+    } else
+        return r1->_ranges.first().start < r2->_ranges.first().start;
+}
+
 class LifeTimeIntervals
 {
     Q_DISABLE_COPY(LifeTimeIntervals)
@@ -234,7 +247,7 @@ public:
 
     LifeTimeIntervals::Ptr lifeTimeIntervals() const;
 
-    QSet<IR::Jump *> calculateOptionalJumps();
+    BitVector calculateOptionalJumps();
 
     static void showMeTheCode(Function *function, const char *marker);
 
@@ -277,6 +290,168 @@ private:
                     QList<Move> &swaps) const;
 };
 
+/*
+ * 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
+{
+    IR::LifeTimeIntervals::Ptr _intervals;
+    QVector<IR::LifeTimeInterval *> _unhandled;
+    QVector<IR::LifeTimeInterval *> _live;
+    QBitArray _slotIsInUse;
+    IR::Function *_function;
+
+    int defPosition(IR::Stmt *s) const
+    {
+        return usePosition(s) + 1;
+    }
+
+    int usePosition(IR::Stmt *s) const
+    {
+        return _intervals->positionForStatement(s);
+    }
+
+public:
+    AllocateStackSlots(const IR::LifeTimeIntervals::Ptr &intervals)
+        : _intervals(intervals)
+        , _slotIsInUse(intervals->size(), false)
+        , _function(0)
+    {
+        _live.reserve(8);
+        _unhandled = _intervals->intervals();
+    }
+
+    void forFunction(IR::Function *function)
+    {
+        IR::Optimizer::showMeTheCode(function, "Before stack slot allocation");
+        _function = function;
+        toStackSlots(function);
+    }
+
+protected:
+    int allocateFreeSlot() override
+    {
+        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;
+    }
+
+    void process(IR::Stmt *s) override
+    {
+//        qDebug("L%d statement %d:", _currentBasicBlock->index, s->id);
+
+        if (IR::Phi *phi = s->asPhi()) {
+            visitPhi(phi);
+        } else {
+            // purge ranges no longer alive:
+            for (int i = 0; i < _live.size(); ) {
+                const IR::LifeTimeInterval *lti = _live.at(i);
+                if (lti->end() < usePosition(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]]);
+                    _slotIsInUse[_stackSlotForTemp[lti->temp().index]] = false;
+                    continue;
+                } else {
+                    ++i;
+                }
+            }
+
+            // active new ranges:
+            while (!_unhandled.isEmpty()) {
+                IR::LifeTimeInterval *lti = _unhandled.last();
+                if (lti->start() > defPosition(s))
+                    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();
+            }
+
+            visit(s);
+        }
+
+        if (IR::Jump *jump = s->asJump()) {
+            IR::MoveMapping moves;
+            for (IR::Stmt *succStmt : jump->target->statements()) {
+                if (IR::Phi *phi = succStmt->asPhi()) {
+                    forceActivation(*phi->targetTemp);
+                    for (int i = 0, ei = phi->incoming.size(); i != ei; ++i) {
+                        IR::Expr *e = phi->incoming[i];
+                        if (IR::Temp *t = e->asTemp()) {
+                            forceActivation(*t);
+                        }
+                        if (jump->target->in[i] == _currentBasicBlock)
+                            moves.add(phi->incoming[i], phi->targetTemp);
+                    }
+                } else {
+                    break;
+                }
+            }
+            moves.order();
+            const QList<IR::Move *> newMoves = moves.insertMoves(_currentBasicBlock, _function, true);
+            for (IR::Move *move : newMoves)
+                visit(move);
+        }
+    }
+
+    void forceActivation(const IR::Temp &t)
+    {
+        if (_stackSlotForTemp.contains(t.index))
+            return;
+
+        int i = _unhandled.size() - 1;
+        for (; i >= 0; --i) {
+            IR::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];
+    }
+
+    void visitPhi(IR::Phi *phi) override
+    {
+        Q_UNUSED(phi);
+#if !defined(QT_NO_DEBUG)
+        Q_ASSERT(_stackSlotForTemp.contains(phi->targetTemp->index));
+        Q_ASSERT(_slotIsInUse[_stackSlotForTemp[phi->targetTemp->index]]);
+        for (IR::Expr *e : phi->incoming) {
+            if (IR::Temp *t = e->asTemp())
+                Q_ASSERT(_stackSlotForTemp.contains(t->index));
+        }
+#endif // defined(QT_NO_DEBUG)
+    }
+};
+
 } // IR namespace
 } // QV4 namespace