V4 IR: make statement numbering fixed and clean up statement worklists.

Every statement in the IR now gets a fixed unique number. This number
can be used to store statements or information for a statement into an
array where the number is used as an index. This removes the need for
many hashes.

In the process of changing the code the two statement worklists in the
optimizer are merged into one. A single instance can be (and is) re-used
by the various algorithms.

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

4 files changed, 240 insertions, 179 deletions

diff --git a/src/qml/compiler/qv4isel_moth.cpp b/src/qml/compiler/qv4isel_moth.cpp
index f5038c8ae1..478346572e 100644
--- a/src/qml/compiler/qv4isel_moth.cpp
+++ b/src/qml/compiler/qv4isel_moth.cpp
@@ -219,7 +219,7 @@ protected:
 
     virtual void process(IR::Stmt *s)
     {
-        Q_ASSERT(s->id > 0);
+        Q_ASSERT(s->id() > 0);
 
 //        qDebug("L%d statement %d:", _currentBasicBlock->index, s->id);
 
@@ -229,7 +229,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() < 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]]);
@@ -243,7 +243,7 @@ protected:
             // active new ranges:
             while (!_unhandled.isEmpty()) {
                 const IR::LifeTimeInterval *lti = _unhandled.last();
-                if (lti->start() > s->id)
+                if (lti->start() > s->id())
                     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 80528f1007..8f2b2ca9e1 100644
--- a/src/qml/compiler/qv4jsir.cpp
+++ b/src/qml/compiler/qv4jsir.cpp
@@ -411,6 +411,7 @@ Function::Function(Module *module, Function *outer, const QString &name)
     , line(-1)
     , column(-1)
     , _allBasicBlocks(0)
+    , _statementCount(0)
 {
     this->name = newString(name);
     _basicBlocks.reserve(8);
@@ -493,6 +494,21 @@ 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)
@@ -665,7 +681,7 @@ Stmt *BasicBlock::EXP(Expr *expr)
     if (isTerminated())
         return 0;
 
-    Exp *s = function->New<Exp>();
+    Exp *s = function->NewStmt<Exp>();
     s->init(expr);
     appendStatement(s);
     return s;
@@ -677,7 +693,7 @@ Stmt *BasicBlock::MOVE(Expr *target, Expr *source)
     if (isTerminated())
         return 0;
 
-    Move *s = function->New<Move>();
+    Move *s = function->NewStmt<Move>();
     s->init(target, source);
     appendStatement(s);
     return s;
@@ -689,7 +705,7 @@ Stmt *BasicBlock::JUMP(BasicBlock *target)
     if (isTerminated())
         return 0;
 
-    Jump *s = function->New<Jump>();
+    Jump *s = function->NewStmt<Jump>();
     s->init(target);
     appendStatement(s);
 
@@ -713,7 +729,7 @@ Stmt *BasicBlock::CJUMP(Expr *cond, BasicBlock *iftrue, BasicBlock *iffalse)
         return JUMP(iftrue);
     }
 
-    CJump *s = function->New<CJump>();
+    CJump *s = function->NewStmt<CJump>();
     s->init(cond, iftrue, iffalse);
     appendStatement(s);
 
@@ -738,7 +754,7 @@ Stmt *BasicBlock::RET(Temp *expr)
     if (isTerminated())
         return 0;
 
-    Ret *s = function->New<Ret>();
+    Ret *s = function->NewStmt<Ret>();
     s->init(expr);
     appendStatement(s);
     return s;
@@ -955,8 +971,8 @@ void IRPrinter::print(BasicBlock *bb)
         QTextStream os(&buf);
         QTextStream *prevOut = &os;
         std::swap(out, prevOut);
-        if (s->id > 0)
-            *out << s->id << ": ";
+        if (s->id() >= 0)
+            *out << s->id() << ": ";
         s->accept(this);
         if (s->location.isValid()) {
             out->flush();
diff --git a/src/qml/compiler/qv4jsir_p.h b/src/qml/compiler/qv4jsir_p.h
index ea866f67f1..6b2f4a90a7 100644
--- a/src/qml/compiler/qv4jsir_p.h
+++ b/src/qml/compiler/qv4jsir_p.h
@@ -387,7 +387,11 @@ struct Q_AUTOTEST_EXPORT Temp: Expr {
     // Used when temp is used as base in member expression
     MemberExpressionResolver memberResolver;
 
-    Temp(): kind(Invalid) {}
+    Temp()
+        : index((1 << 28) - 1)
+        , kind(Invalid)
+        , isReadOnly(0)
+    {}
 
     void init(unsigned kind, unsigned index)
     {
@@ -614,11 +618,13 @@ struct Stmt {
         QVector<Expr *> incoming; // used by Phi nodes
     };
 
+    enum { InvalidId = -1 };
+
     Data *d;
-    int id;
     QQmlJS::AST::SourceLocation location;
 
-    Stmt(): d(0), id(-1) {}
+    explicit Stmt(int id): d(0), _id(id) {}
+
     virtual ~Stmt()
     {
 #ifdef Q_CC_MSVC
@@ -637,17 +643,25 @@ struct Stmt {
     virtual Ret *asRet() { return 0; }
     virtual Phi *asPhi() { return 0; }
 
+    int id() const { return _id; }
+
 private: // For memory management in BasicBlock
     friend struct BasicBlock;
     void destroyData() {
         delete d;
         d = 0;
     }
+
+private:
+    friend struct Function;
+    int _id;
 };
 
 struct Exp: Stmt {
     Expr *expr;
 
+    Exp(int id): Stmt(id) {}
+
     void init(Expr *expr)
     {
         this->expr = expr;
@@ -663,6 +677,8 @@ struct Move: Stmt {
     Expr *source;
     bool swap;
 
+    Move(int id): Stmt(id) {}
+
     void init(Expr *target, Expr *source)
     {
         this->target = target;
@@ -678,6 +694,8 @@ struct Move: Stmt {
 struct Jump: Stmt {
     BasicBlock *target;
 
+    Jump(int id): Stmt(id) {}
+
     void init(BasicBlock *target)
     {
         this->target = target;
@@ -694,6 +712,8 @@ struct CJump: Stmt {
     BasicBlock *iftrue;
     BasicBlock *iffalse;
 
+    CJump(int id): Stmt(id) {}
+
     void init(Expr *cond, BasicBlock *iftrue, BasicBlock *iffalse)
     {
         this->cond = cond;
@@ -710,6 +730,8 @@ struct CJump: Stmt {
 struct Ret: Stmt {
     Expr *expr;
 
+    Ret(int id): Stmt(id) {}
+
     void init(Expr *expr)
     {
         this->expr = expr;
@@ -724,6 +746,8 @@ struct Ret: Stmt {
 struct Phi: Stmt {
     Temp *targetTemp;
 
+    Phi(int id): Stmt(id) {}
+
     virtual void accept(StmtVisitor *v) { v->visitPhi(this); }
     virtual Phi *asPhi() { return this; }
 };
@@ -976,7 +1000,10 @@ struct Function {
     PropertyDependencyMap contextObjectPropertyDependencies;
     PropertyDependencyMap scopeObjectPropertyDependencies;
 
-    template <typename _Tp> _Tp *New() { return new (pool->allocate(sizeof(_Tp))) _Tp(); }
+    template <typename T> T *New() { return new (pool->allocate(sizeof(T))) T(); }
+    template <typename T> T *NewStmt() {
+        return new (pool->allocate(sizeof(T))) T(getNewStatementId());
+    }
 
     Function(Module *module, Function *outer, const QString &name);
     ~Function();
@@ -1016,9 +1043,14 @@ struct Function {
     void setScheduledBlocks(const QVector<BasicBlock *> &scheduled);
     void renumberBasicBlocks();
 
+    unsigned getNewStatementId() { return _statementCount++; }
+    unsigned statementCount() const { return _statementCount; }
+    void renumberForLifeRanges();
+
 private:
     QVector<BasicBlock *> _basicBlocks;
     QVector<BasicBlock *> *_allBasicBlocks;
+    unsigned _statementCount;
 };
 
 class CloneExpr: protected IR::ExprVisitor
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index c24d4a7c7a..377ede95d9 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -764,7 +764,7 @@ void insertPhiNode(const Temp &a, BasicBlock *y, IR::Function *f) {
     qout << " in block " << y->index << endl;
 #endif
 
-    Phi *phiNode = f->New<Phi>();
+    Phi *phiNode = f->NewStmt<Phi>();
     phiNode->d = new Stmt::Data;
     phiNode->targetTemp = f->New<Temp>();
     phiNode->targetTemp->init(a.kind, a.index);
@@ -1456,80 +1456,108 @@ void cleanupPhis(DefUsesCalculator &defUses)
 
 class StatementWorklist
 {
-    QVector<Stmt *> worklist;
-    QBitArray inWorklist;
-    QSet<Stmt *> removed;
-    QHash<Stmt*,Stmt*> replaced;
+    IR::Function *theFunction;
+    std::vector<Stmt *> stmts;
+    std::vector<bool> worklist;
+    unsigned worklistSize;
+    std::vector<int> replaced;
+    std::vector<bool> removed;
 
     Q_DISABLE_COPY(StatementWorklist)
 
 public:
     StatementWorklist(IR::Function *function)
+        : theFunction(function)
+        , stmts(function->statementCount(), 0)
+        , worklist(function->statementCount(), false)
+        , worklistSize(0)
+        , replaced(function->statementCount(), Stmt::InvalidId)
+        , removed(function->statementCount())
     {
-        QVector<Stmt *> w;
-        int stmtCount = 0;
+        grow();
 
-        // Put in all statements, and number them on the fly. The numbering is used to index the
-        // bit array.
         foreach (BasicBlock *bb, function->basicBlocks()) {
             if (bb->isRemoved())
                 continue;
 
             foreach (Stmt *s, bb->statements()) {
-                s->id = stmtCount++;
-                w.append(s);
+                if (!s)
+                    continue;
+
+                stmts[s->id()] = s;
+                worklist[s->id()] = true;
+                ++worklistSize;
             }
         }
+    }
 
-        // For QVector efficiency reasons, we process statements from the back. However, it is more
-        // effective to process the statements in ascending order. So we need to invert the
-        // order.
-        worklist.reserve(w.size());
-        for (int i = w.size() - 1; i >= 0; --i)
-            worklist.append(w.at(i));
+    void reset()
+    {
+        foreach (Stmt *s, stmts) {
+            if (!s)
+                continue;
+
+            worklist[s->id()] = true;
+            ++worklistSize;
+        }
 
-        inWorklist = QBitArray(stmtCount, true);
+        replaced.assign(replaced.size(), Stmt::InvalidId);
+        removed.assign(removed.size(), false);
     }
 
-    // This will clear the entry for the statement in the basic block. After processing all
-    // statements, the cleanup method needs to be run to remove all null-pointers.
-    void clear(Stmt *stmt)
+    void remove(Stmt *stmt)
     {
-        Q_ASSERT(!inWorklist.at(stmt->id));
-        removed.insert(stmt);
+        replaced[stmt->id()] = Stmt::InvalidId;
+        removed[stmt->id()] = true;
+        std::vector<bool>::reference inWorklist = worklist[stmt->id()];
+        if (inWorklist) {
+            inWorklist = false;
+            Q_ASSERT(worklistSize > 0);
+            --worklistSize;
+        }
     }
 
     void replace(Stmt *oldStmt, Stmt *newStmt)
     {
         Q_ASSERT(oldStmt);
+        Q_ASSERT(replaced[oldStmt->id()] == Stmt::InvalidId);
+        Q_ASSERT(removed[oldStmt->id()] == false);
+
         Q_ASSERT(newStmt);
-        Q_ASSERT(!removed.contains(oldStmt));
+        registerNewStatement(newStmt);
+        Q_ASSERT(replaced[newStmt->id()] == Stmt::InvalidId);
+        Q_ASSERT(removed[newStmt->id()] == false);
 
-        if (newStmt->id == -1)
-            newStmt->id = oldStmt->id;
-        QHash<Stmt *, Stmt *>::const_iterator it = replaced.find(oldStmt);
-        if (it != replaced.end())
-            oldStmt = it.key();
-        replaced[oldStmt] = newStmt;
+        replaced[oldStmt->id()] = newStmt->id();
+        worklist[oldStmt->id()] = false;
     }
 
-    void cleanup(IR::Function *function)
+    void applyToFunction()
     {
-        foreach (BasicBlock *bb, function->basicBlocks()) {
+        foreach (BasicBlock *bb, theFunction->basicBlocks()) {
             if (bb->isRemoved())
                 continue;
 
             for (int i = 0; i < bb->statementCount();) {
-                Stmt *stmt = bb->statements()[i];
-                QHash<Stmt *, Stmt *>::const_iterator it = replaced.find(stmt);
-                if (it != replaced.end() && !removed.contains(it.value())) {
-                    bb->replaceStatement(i, it.value());
-                } else if (removed.contains(stmt)) {
+                Stmt *stmt = bb->statements().at(i);
+
+                int id = stmt->id();
+                Q_ASSERT(id != Stmt::InvalidId);
+                Q_ASSERT(static_cast<unsigned>(stmt->id()) < stmts.size());
+
+                for (int replacementId = replaced[id]; replacementId != Stmt::InvalidId; replacementId = replaced[replacementId])
+                    id = replacementId;
+                Q_ASSERT(id != Stmt::InvalidId);
+                Q_ASSERT(static_cast<unsigned>(stmt->id()) < stmts.size());
+
+                if (removed[id]) {
                     bb->removeStatement(i);
-                    continue;
-                }
+                } else {
+                    if (id != stmt->id())
+                        bb->replaceStatement(i, stmts[id]);
 
-                ++i;
+                    ++i;
+                }
             }
         }
     }
@@ -1542,18 +1570,17 @@ public:
         return *this;
     }
 
-
     StatementWorklist &operator+=(Stmt *s)
     {
         if (!s)
             return *this;
 
-        Q_ASSERT(s->id >= 0);
-        Q_ASSERT(s->id < inWorklist.size());
+        Q_ASSERT(s->id() >= 0);
+        Q_ASSERT(static_cast<unsigned>(s->id()) < worklist.size());
 
-        if (!inWorklist.at(s->id)) {
-            worklist.append(s);
-            inWorklist.setBit(s->id);
+        if (!worklist[s->id()]) {
+            worklist[s->id()] = true;
+            ++worklistSize;
         }
 
         return *this;
@@ -1561,12 +1588,14 @@ public:
 
     StatementWorklist &operator-=(Stmt *s)
     {
-        Q_ASSERT(s->id >= 0);
-        Q_ASSERT(s->id < inWorklist.size());
-
-        if (inWorklist.at(s->id)) {
-            worklist.remove(worklist.indexOf(s));
-            inWorklist.clearBit(s->id);
+        Q_ASSERT(s->id() >= 0);
+        Q_ASSERT(static_cast<unsigned>(s->id()) < worklist.size());
+
+        std::vector<bool>::reference inWorklist = worklist[s->id()];
+        if (inWorklist) {
+            inWorklist = false;
+            Q_ASSERT(worklistSize > 0);
+            --worklistSize;
         }
 
         return *this;
@@ -1574,20 +1603,67 @@ public:
 
     bool isEmpty() const
     {
-        return worklist.isEmpty();
+        return worklistSize == 0;
     }
 
-    Stmt *takeOne()
+    Stmt *takeNext(Stmt *last)
     {
         if (isEmpty())
             return 0;
 
-        Stmt *s = worklist.last();
-        Q_ASSERT(s->id < inWorklist.size());
-        worklist.removeLast();
-        inWorklist.clearBit(s->id);
+        const int startAt = last ? last->id() + 1 : 0;
+        Q_ASSERT(startAt >= 0);
+        Q_ASSERT(static_cast<unsigned>(startAt) <= worklist.size());
+
+        Q_ASSERT(worklist.size() == stmts.size());
+
+        // Do not compare the result of find with the end iterator, because some libc++ versions
+        // have a bug where the result of the ++operator is past-the-end of the vector, but unequal
+        // to end().
+        size_t pos = std::find(worklist.begin() + startAt, worklist.end(), true) - worklist.begin();
+        if (pos >= worklist.size())
+            pos = std::find(worklist.begin(), worklist.begin() + startAt, true) - worklist.begin();
+
+        worklist[pos] = false;
+        Q_ASSERT(worklistSize > 0);
+        --worklistSize;
+        Stmt *s = stmts.at(pos);
+        Q_ASSERT(s);
         return s;
     }
+
+    IR::Function *function() const
+    {
+        return theFunction;
+    }
+
+    void registerNewStatement(Stmt *s)
+    {
+        Q_ASSERT(s->id() >= 0);
+        if (static_cast<unsigned>(s->id()) < stmts.size())
+            return;
+
+        if (static_cast<unsigned>(s->id()) >= stmts.capacity())
+            grow();
+
+        int newSize = s->id() + 1;
+        stmts.resize(newSize, 0);
+        worklist.resize(newSize, false);
+        replaced.resize(newSize, Stmt::InvalidId);
+        removed.resize(newSize, false);
+
+        stmts[s->id()] = s;
+    }
+
+private:
+    void grow()
+    {
+        size_t newCapacity = (stmts.capacity() * 3) / 2;
+        stmts.reserve(newCapacity);
+        worklist.reserve(newCapacity);
+        replaced.reserve(newCapacity);
+        removed.reserve(newCapacity);
+    }
 };
 
 class EliminateDeadCode: public ExprVisitor {
@@ -1822,69 +1898,10 @@ protected:
 
 class TypeInference: public StmtVisitor, public ExprVisitor {
     QQmlEnginePrivate *qmlEngine;
-    IR::Function *function;
     const DefUsesCalculator &_defUses;
     typedef QHash<Temp, DiscoveredType> TempTypes;
     TempTypes _tempTypes;
-    class W {
-        std::vector<bool> worklist;
-        std::vector<Stmt *> stmts;
-        int count;
-    public:
-        W(IR::Function *f)
-            : count(0)
-        {
-            foreach (BasicBlock *bb, f->basicBlocks()) {
-                if (bb->isRemoved())
-                    continue;
-                foreach (Stmt *stmt, bb->statements())
-                    stmt->id = count++;
-                stmts.insert(stmts.end(), bb->statements().begin(), bb->statements().end());
-            }
-            worklist.resize(stmts.size(), true);
-        }
-
-        ~W()
-        {
-            foreach (Stmt *stmt, stmts)
-                stmt->id = -1;
-        }
-
-        void append(const QVector<Stmt*>&stmts)
-        {
-            foreach (Stmt *stmt, stmts)
-                append(stmt);
-        }
-
-        void append(Stmt *stmt)
-        {
-            Q_ASSERT(stmt->id >= 0);
-
-            if (worklist[stmt->id])
-                return;
-            worklist[stmt->id] = true;
-            ++count;
-        }
-
-        bool empty() const
-        { return count == 0; }
-
-        Stmt *takeNext(Stmt *last)
-        {
-            if (empty())
-                return 0;
-
-            const int startAt = last ? last->id + 1 : 0;
-            Q_ASSERT(startAt >= 0);
-
-            size_t pos = std::distance(worklist.begin(), std::find(worklist.begin() + startAt, worklist.end(), true));
-            if (pos >= worklist.size())
-                pos = std::distance(worklist.begin(), std::find(worklist.begin(), worklist.begin() + startAt, true));
-            --count;
-            worklist[pos] = false;
-            return stmts[pos];
-        }
-    } *_worklist;
+    StatementWorklist *_worklist;
     struct TypingResult {
         DiscoveredType type;
         bool fullyTyped;
@@ -1902,10 +1919,8 @@ public:
         , _ty(UnknownType)
     {}
 
-    void run(IR::Function *f) {
-        W w(f);
+    void run(StatementWorklist &w) {
         _worklist = &w;
-        function = f;
 
         Stmt *s = 0;
         while ((s = _worklist->takeNext(s))) {
@@ -1917,7 +1932,7 @@ public:
 #endif
 
             if (!run(s)) {
-                _worklist->append(s);
+                *_worklist += s;
 #if defined(SHOW_SSA)
                 qout<<"Pushing back stmt: ";
                 s->dump(qout);qout<<endl;
@@ -1974,7 +1989,7 @@ private:
                 }
 #endif
 
-                _worklist->append(_defUses.uses(*t));
+                *_worklist += _defUses.uses(*t);
             }
         } else {
             e->type = (Type) ty.type;
@@ -2397,7 +2412,7 @@ class TypePropagation: public StmtVisitor, public ExprVisitor {
 public:
     TypePropagation(DefUsesCalculator &defUses) : _defUses(defUses), _ty(UnknownType) {}
 
-    void run(IR::Function *f) {
+    void run(IR::Function *f, StatementWorklist &worklist) {
         _f = f;
         foreach (BasicBlock *bb, f->basicBlocks()) {
             if (bb->isRemoved())
@@ -2422,7 +2437,8 @@ public:
                     Temp *target = bb->TEMP(bb->newTemp());
                     target->type = conversion.targetType;
                     Expr *convert = bb->CONVERT(al, conversion.targetType);
-                    Move *convCall = f->New<Move>();
+                    Move *convCall = f->NewStmt<Move>();
+                    worklist.registerNewStatement(convCall);
                     convCall->init(target, convert);
                     _defUses.addTemp(target, convCall, bb);
 
@@ -2442,7 +2458,8 @@ public:
                     Temp *target = bb->TEMP(bb->newTemp());
                     target->type = conversion.targetType;
                     Expr *convert = bb->CONVERT(t, conversion.targetType);
-                    Move *convCall = f->New<Move>();
+                    Move *convCall = f->NewStmt<Move>();
+                    worklist.registerNewStatement(convCall);
                     convCall->init(target, convert);
                     _defUses.addTemp(target, convCall, bb);
                     _defUses.addUse(*t, convCall);
@@ -2469,7 +2486,8 @@ public:
                     //   int32{%2} = int32{convert(double{%3})};
                     Temp *tmp = bb->TEMP(bb->newTemp());
                     tmp->type = u->type;
-                    Move *extraMove = f->New<Move>();
+                    Move *extraMove = f->NewStmt<Move>();
+                    worklist.registerNewStatement(extraMove);
                     extraMove->init(tmp, u);
                     _defUses.addTemp(tmp, extraMove, bb);
 
@@ -2609,7 +2627,7 @@ protected:
     }
 };
 
-void splitCriticalEdges(IR::Function *f, DominatorTree &df)
+void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &worklist)
 {
     foreach (BasicBlock *bb, f->basicBlocks()) {
         if (bb->isRemoved())
@@ -2627,7 +2645,8 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df)
 
             // create the basic block:
             BasicBlock *newBB = f->newBasicBlock(containingGroup, bb->catchBlock);
-            Jump *s = f->New<Jump>();
+            Jump *s = f->NewStmt<Jump>();
+            worklist.registerNewStatement(s);
             s->init(bb);
             newBB->appendStatement(s);
 
@@ -3184,22 +3203,22 @@ bool tryOptimizingComparison(Expr *&expr)
 }
 } // anonymous namespace
 
-void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTree &df)
+void optimizeSSA(StatementWorklist &W, DefUsesCalculator &defUses, DominatorTree &df)
 {
-    StatementWorklist W(function);
+    IR::Function *function = W.function();
     ExprReplacer replaceUses(defUses, function);
 
+    Stmt *s = 0;
     while (!W.isEmpty()) {
-        Stmt *s = W.takeOne();
-        if (!s)
-            continue;
+        s = W.takeNext(s);
+        Q_ASSERT(s);
 
         if (Phi *phi = s->asPhi()) {
             // constant propagation:
             if (Const *c = isConstPhi(phi)) {
                 replaceUses(phi->targetTemp, c, W);
                 defUses.removeDef(*phi->targetTemp);
-                W.clear(s);
+                W.remove(s);
                 continue;
             }
 
@@ -3215,7 +3234,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
                     defUses.addUses(*t2, newT2Uses);
                 }
                 defUses.removeDef(*t);
-                W.clear(s);
+                W.remove(s);
                 continue;
             }
 
@@ -3227,7 +3246,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
                 }
 
                 defUses.removeDef(*phi->targetTemp);
-                W.clear(s);
+                W.remove(s);
                 continue;
             }
         } else  if (Move *m = s->asMove()) {
@@ -3251,7 +3270,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
                 if (defUses.useCount(*targetTemp) == 0) {
                     EliminateDeadCode(defUses, W).run(m->source, s);
                     if (!m->source)
-                        W.clear(s);
+                        W.remove(s);
                     continue;
                 }
 
@@ -3259,7 +3278,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
                 if (Const *sourceConst = m->source->asConst()) {
                     replaceUses(targetTemp, sourceConst, W);
                     defUses.removeDef(*targetTemp);
-                    W.clear(s);
+                    W.remove(s);
                     continue;
                 }
                 if (Member *member = m->source->asMember()) {
@@ -3269,7 +3288,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
                         c->init(SInt32Type, enumValue);
                         replaceUses(targetTemp, c, W);
                         defUses.removeDef(*targetTemp);
-                        W.clear(s);
+                        W.remove(s);
                         defUses.removeUse(s, *member->base->asTemp());
                         continue;
                     } else if (member->attachedPropertiesIdOrEnumValue != 0 && member->property && member->base->asTemp()) {
@@ -3290,7 +3309,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
                     defUses.removeUse(s, *sourceTemp);
                     defUses.addUses(*sourceTemp, newT2Uses);
                     defUses.removeDef(*targetTemp);
-                    W.clear(s);
+                    W.remove(s);
                     continue;
                 }
 
@@ -3453,7 +3472,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
             if (Const *constantCondition = cjump->cond->asConst()) {
                 // Note: this assumes that there are no critical edges! Meaning, we can safely purge
                 //       any basic blocks that are found to be unreachable.
-                Jump *jump = function->New<Jump>();
+                Jump *jump = function->NewStmt<Jump>();
                 if (convertToValue(constantCondition).toBoolean()) {
                     jump->target = cjump->iftrue;
                     purgeBB(cjump->iffalse, function, defUses, W, df);
@@ -3475,7 +3494,7 @@ void optimizeSSA(IR::Function *function, DefUsesCalculator &defUses, DominatorTr
         }
     }
 
-    W.cleanup(function);
+    W.applyToFunction();
 }
 
 class InputOutputCollector: protected StmtVisitor, protected ExprVisitor {
@@ -3554,18 +3573,9 @@ class LifeRanges {
 public:
     LifeRanges(IR::Function *function, const QHash<BasicBlock *, BasicBlock *> &startEndLoops)
     {
+        function->renumberForLifeRanges();
         _liveIn.resize(function->basicBlockCount());
 
-        int id = 0;
-        foreach (BasicBlock *bb, function->basicBlocks()) {
-            foreach (Stmt *s, bb->statements()) {
-                if (s->asPhi())
-                    s->id = id + 1;
-                else
-                    s->id = ++id;
-            }
-        }
-
         for (int i = function->basicBlockCount() - 1; i >= 0; --i) {
             BasicBlock *bb = function->basicBlock(i);
             buildIntervals(bb, startEndLoops.value(bb, 0));
@@ -3626,7 +3636,7 @@ private:
         QVector<Stmt *> statements = bb->statements();
 
         foreach (const Temp &opd, live)
-            _intervals[opd].addRange(statements.first()->id, statements.last()->id);
+            _intervals[opd].addRange(statements.first()->id(), statements.last()->id());
 
         InputOutputCollector collector;
         for (int i = statements.size() - 1; i >= 0; --i) {
@@ -3647,14 +3657,14 @@ private:
                 live.remove(opd);
             }
             foreach (const Temp &opd, collector.inputs) {
-                _intervals[opd].addRange(statements.first()->id, s->id);
+                _intervals[opd].addRange(statements.first()->id(), s->id());
                 live.insert(opd);
             }
         }
 
         if (loopEnd) { // Meaning: bb is a loop header, because loopEnd is set to non-null.
             foreach (const Temp &opd, live)
-                _intervals[opd].addRange(statements.first()->id, loopEnd->terminator()->id);
+                _intervals[opd].addRange(statements.first()->id(), loopEnd->terminator()->id());
         }
 
         _liveIn[bb->index()] = live;
@@ -3674,14 +3684,14 @@ void removeUnreachleBlocks(IR::Function *function)
 } // anonymous namespace
 
 void LifeTimeInterval::setFrom(Stmt *from) {
-    Q_ASSERT(from && from->id > 0);
+    Q_ASSERT(from && from->id() > 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->id(), from->id()));
         if (_end == Invalid)
-            _end = from->id;
+            _end = from->id();
     } else {
-        _ranges.first().start = from->id;
+        _ranges.first().start = from->id();
     }
 }
 
@@ -3855,8 +3865,10 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine)
         cleanupPhis(defUses);
 //        showMeTheCode(function);
 
+        StatementWorklist worklist(function);
+
 //        qout << "Running type inference..." << endl;
-        TypeInference(qmlEngine, defUses).run(function);
+        TypeInference(qmlEngine, defUses).run(worklist);
 //        showMeTheCode(function);
 
 //        qout << "Doing reverse inference..." << endl;
@@ -3864,18 +3876,19 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine)
 //        showMeTheCode(function);
 
 //        qout << "Doing type propagation..." << endl;
-        TypePropagation(defUses).run(function);
+        TypePropagation(defUses).run(function, worklist);
 //        showMeTheCode(function);
 
         // Transform the CFG into edge-split SSA.
 //        qout << "Starting edge splitting..." << endl;
-        splitCriticalEdges(function, df);
+        splitCriticalEdges(function, df, worklist);
 //        showMeTheCode(function);
 
         static bool doOpt = qgetenv("QV4_NO_OPT").isEmpty();
         if (doOpt) {
 //            qout << "Running SSA optimization..." << endl;
-            optimizeSSA(function, defUses, df);
+            worklist.reset();
+            optimizeSSA(worklist, defUses, df);
 //            showMeTheCode(function);
         }
 
@@ -4097,7 +4110,7 @@ QList<IR::Move *> MoveMapping::insertMoves(BasicBlock *bb, IR::Function *functio
 
     int insertionPoint = atEnd ? bb->statements().size() - 1 : 0;
     foreach (const Move &m, _moves) {
-        IR::Move *move = function->New<IR::Move>();
+        IR::Move *move = function->NewStmt<IR::Move>();
         move->init(clone(m.to, function), clone(m.from, function));
         move->swap = m.needsSwap;
         bb->insertStatementBefore(insertionPoint++, move);