diff options
Diffstat (limited to 'src/qml/qml/v4/qv4ssa.cpp')
| -rw-r--r-- | src/qml/qml/v4/qv4ssa.cpp | 1838 |
1 files changed, 1838 insertions, 0 deletions
diff --git a/src/qml/qml/v4/qv4ssa.cpp b/src/qml/qml/v4/qv4ssa.cpp new file mode 100644 index 0000000000..294cb7cb47 --- /dev/null +++ b/src/qml/qml/v4/qv4ssa.cpp @@ -0,0 +1,1838 @@ +/**************************************************************************** +** +** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the V4VM module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and Digia. For licensing terms and +** conditions see http://qt.digia.com/licensing. For further information +** use the contact form at http://qt.digia.com/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Digia gives you certain additional +** rights. These rights are described in the Digia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qv4ssa_p.h" +#include "qv4util_p.h" + +#include <QtCore/QCoreApplication> +#include <QtCore/QStringList> +#include <QtCore/QSet> +#include <QtCore/QBuffer> +#include <QtCore/QBitArray> +#include <QtCore/QLinkedList> +#include <QtCore/QStack> +#include <qv4runtime_p.h> +#include <qv4context_p.h> +#include <cmath> +#include <iostream> +#include <cassert> + +#ifdef CONST +#undef CONST +#endif + +#define QV4_NO_LIVENESS +#undef SHOW_SSA + +QT_USE_NAMESPACE + +using namespace QQmlJS; + +namespace { +using namespace V4IR; + +QTextStream qout(stdout, QIODevice::WriteOnly); + +void showMeTheCode(V4IR::Function *function) +{ + static bool showCode = !qgetenv("SHOW_CODE").isNull(); + if (showCode) { + QVector<V4IR::Stmt *> code; + QHash<V4IR::Stmt *, V4IR::BasicBlock *> leader; + + foreach (V4IR::BasicBlock *block, function->basicBlocks) { + if (block->statements.isEmpty()) + continue; + leader.insert(block->statements.first(), block); + foreach (V4IR::Stmt *s, block->statements) { + code.append(s); + } + } + + QString name; + if (function->name && !function->name->isEmpty()) + name = *function->name; + else + name.sprintf("%p", function); + + qout << "function " << name << "("; + for (int i = 0; i < function->formals.size(); ++i) { + if (i != 0) + qout << ", "; + qout << *function->formals.at(i); + } + qout << ")" << endl + << "{" << endl; + + foreach (const QString *local, function->locals) { + qout << " var " << *local << ';' << endl; + } + + for (int i = 0; i < code.size(); ++i) { + V4IR::Stmt *s = code.at(i); + + if (V4IR::BasicBlock *bb = leader.value(s)) { + qout << endl; + QByteArray str; + str.append('L'); + str.append(QByteArray::number(bb->index)); + str.append(':'); + for (int i = 66 - str.length(); i; --i) + str.append(' '); + qout << str; + qout << "// predecessor blocks:"; + foreach (V4IR::BasicBlock *in, bb->in) + qout << " L" << in->index; + if (bb->in.isEmpty()) + qout << "(none)"; + if (V4IR::BasicBlock *container = bb->containingGroup()) + qout << "; container block: L" << container->index; + if (bb->isGroupStart()) + qout << "; group start"; + qout << endl; + } + V4IR::Stmt *n = (i + 1) < code.size() ? code.at(i + 1) : 0; +// if (n && s->asJump() && s->asJump()->target == leader.value(n)) { +// continue; +// } + + QByteArray str; + QBuffer buf(&str); + buf.open(QIODevice::WriteOnly); + QTextStream out(&buf); + s->dump(out, V4IR::Stmt::MIR); + out.flush(); + + if (s->location.isValid()) + qout << " // line: " << s->location.startLine << " column: " << s->location.startColumn << endl; + +#ifndef QV4_NO_LIVENESS + for (int i = 60 - str.size(); i >= 0; --i) + str.append(' '); + + qout << " " << str; + + // if (! s->uses.isEmpty()) { + // qout << " // uses:"; + // foreach (unsigned use, s->uses) { + // qout << " %" << use; + // } + // } + + // if (! s->defs.isEmpty()) { + // qout << " // defs:"; + // foreach (unsigned def, s->defs) { + // qout << " %" << def; + // } + // } + +# if 0 + if (! s->d->liveIn.isEmpty()) { + qout << " // lives in:"; + for (int i = 0; i < s->d->liveIn.size(); ++i) { + if (s->d->liveIn.testBit(i)) + qout << " %" << i; + } + } +# else + if (! s->d->liveOut.isEmpty()) { + qout << " // lives out:"; + for (int i = 0; i < s->d->liveOut.size(); ++i) { + if (s->d->liveOut.testBit(i)) + qout << " %" << i; + } + } +# endif +#else + qout << " " << str; +#endif + + qout << endl; + + if (n && s->asCJump() /*&& s->asCJump()->iffalse != leader.value(n)*/) { + qout << " else goto L" << s->asCJump()->iffalse->index << ";" << endl; + } + } + + qout << "}" << endl + << endl; + } +} + +class DominatorTree { + int N; + QHash<BasicBlock *, int> dfnum; + QVector<BasicBlock *> vertex; + QHash<BasicBlock *, BasicBlock *> parent; + QHash<BasicBlock *, BasicBlock *> ancestor; + QHash<BasicBlock *, BasicBlock *> best; + QHash<BasicBlock *, BasicBlock *> semi; + QHash<BasicBlock *, BasicBlock *> idom; + QHash<BasicBlock *, BasicBlock *> samedom; + QHash<BasicBlock *, QSet<BasicBlock *> > bucket; + + void DFS(BasicBlock *p, BasicBlock *n) { + if (dfnum[n] == 0) { + dfnum[n] = N; + vertex[N] = n; + parent[n] = p; + ++N; + foreach (BasicBlock *w, n->out) + DFS(n, w); + } + } + + BasicBlock *ancestorWithLowestSemi(BasicBlock *v) { + BasicBlock *a = ancestor[v]; + if (ancestor[a]) { + BasicBlock *b = ancestorWithLowestSemi(a); + ancestor[v] = ancestor[a]; + if (dfnum[semi[b]] < dfnum[semi[best[v]]]) + best[v] = b; + } + return best[v]; + } + + void link(BasicBlock *p, BasicBlock *n) { + ancestor[n] = p; + best[n] = n; + } + + void calculateIDoms(const QVector<BasicBlock *> &nodes) { + Q_ASSERT(nodes.first()->in.isEmpty()); + vertex.resize(nodes.size()); + foreach (BasicBlock *n, nodes) { + dfnum[n] = 0; + semi[n] = 0; + ancestor[n] = 0; + idom[n] = 0; + samedom[n] = 0; + } + + DFS(0, nodes.first()); + Q_ASSERT(N == nodes.size()); // fails with unreachable nodes... + + for (int i = N - 1; i > 0; --i) { + BasicBlock *n = vertex[i]; + BasicBlock *p = parent[n]; + BasicBlock *s = p; + + foreach (BasicBlock *v, n->in) { + BasicBlock *ss; + if (dfnum[v] <= dfnum[n]) + ss = v; + else + ss = semi[ancestorWithLowestSemi(v)]; + if (dfnum[ss] < dfnum[s]) + s = ss; + } + semi[n] = s; + bucket[s].insert(n); + link(p, n); + foreach (BasicBlock *v, bucket[p]) { + BasicBlock *y = ancestorWithLowestSemi(v); + Q_ASSERT(semi[y] == p); + if (semi[y] == semi[v]) + idom[v] = p; + else + samedom[v] = y; + } + bucket[p].clear(); + } + for (int i = 1; i < N; ++i) { + BasicBlock *n = vertex[i]; + Q_ASSERT(ancestor[n] && ((semi[n] && dfnum[ancestor[n]] <= dfnum[semi[n]]) || semi[n] == n)); + Q_ASSERT(bucket[n].isEmpty()); + if (BasicBlock *sdn = samedom[n]) + idom[n] = idom[sdn]; + } + +#ifdef SHOW_SSA + qout << "Immediate dominators:" << endl; + foreach (BasicBlock *to, nodes) { + qout << '\t'; + if (BasicBlock *from = idom.value(to)) + qout << from->index; + else + qout << "(none)"; + qout << " -> " << to->index << endl; + } +#endif // SHOW_SSA + } + + bool dominates(BasicBlock *dominator, BasicBlock *dominated) const { + for (BasicBlock *it = dominated; it; it = idom[it]) { + if (it == dominator) + return true; + } + + return false; + } + + void computeDF(BasicBlock *n) { + if (DF.contains(n)) + return; // TODO: verify this! + + QSet<BasicBlock *> S; + foreach (BasicBlock *y, n->out) + if (idom[y] != n) + S.insert(y); + + /* + * foreach child c of n in the dominator tree + * computeDF[c] + * foreach element w of DF[c] + * if n does not dominate w or if n = w + * S.insert(w) + * DF[n] = S; + */ + foreach (BasicBlock *c, children[n]) { + computeDF(c); + foreach (BasicBlock *w, DF[c]) + if (!dominates(n, w) || n == w) + S.insert(w); + } + DF[n] = S; + +#ifdef SHOW_SSA + qout << "\tDF[" << n->index << "]: {"; + QList<BasicBlock *> SList = S.values(); + for (int i = 0; i < SList.size(); ++i) { + if (i > 0) + qout << ", "; + qout << SList[i]->index; + } + qout << "}" << endl; +#endif // SHOW_SSA +#ifndef QT_NO_DEBUG + foreach (BasicBlock *fBlock, S) { + Q_ASSERT(!dominates(n, fBlock) || fBlock == n); + bool hasDominatedSucc = false; + foreach (BasicBlock *succ, fBlock->in) + if (dominates(n, succ)) + hasDominatedSucc = true; + if (!hasDominatedSucc) { + qout << fBlock->index << " in DF[" << n->index << "] has no dominated predecessors" << endl; + } + Q_ASSERT(hasDominatedSucc); + } +#endif // !QT_NO_DEBUG + } + + QHash<BasicBlock *, QSet<BasicBlock *> > children; + QHash<BasicBlock *, QSet<BasicBlock *> > DF; + +public: + DominatorTree(const QVector<BasicBlock *> &nodes) + : N(0) + { + calculateIDoms(nodes); + + // compute children of n + foreach (BasicBlock *n, nodes) + children[idom[n]].insert(n); + +#ifdef SHOW_SSA + qout << "Dominator Frontiers:" << endl; +#endif // SHOW_SSA + foreach (BasicBlock *n, nodes) + computeDF(n); + } + + QSet<BasicBlock *> operator[](BasicBlock *n) const { + return DF[n]; + } + + BasicBlock *immediateDominator(BasicBlock *bb) const { + return idom[bb]; + } +}; + +class VariableCollector: public StmtVisitor, ExprVisitor { + QHash<Temp, QSet<BasicBlock *> > _defsites; + QHash<BasicBlock *, QSet<Temp> > A_orig; + QSet<Temp> nonLocals; + QSet<Temp> killed; + + BasicBlock *currentBB; + const bool variablesCanEscape; + bool isCollectable(Temp *t) const + { + switch (t->kind) { + case Temp::Formal: + case Temp::ScopedFormal: + case Temp::ScopedLocal: + return false; + case Temp::Local: + return !variablesCanEscape; + case Temp::VirtualRegister: + return true; + default: + // PhysicalRegister and StackSlot can only get inserted later. + Q_ASSERT(!"Invalid temp kind!"); + return false; + } + } + +public: + VariableCollector(Function *function) + : variablesCanEscape(function->variablesCanEscape()) + { +#ifdef SHOW_SSA + qout << "Variables collected:" << endl; +#endif // SHOW_SSA + + foreach (BasicBlock *bb, function->basicBlocks) { + currentBB = bb; + killed.clear(); + killed.reserve(bb->statements.size() / 2); + foreach (Stmt *s, bb->statements) { + s->accept(this); + } + } + +#ifdef SHOW_SSA + qout << "Non-locals:" << endl; + foreach (const Temp &nonLocal, nonLocals) { + qout << "\t"; + nonLocal.dump(qout); + qout << endl; + } + + qout << "end collected variables." << endl; +#endif // SHOW_SSA + } + + QList<Temp> vars() const { + return _defsites.keys(); + } + + QSet<BasicBlock *> defsite(const Temp &n) const { + return _defsites[n]; + } + + QSet<Temp> inBlock(BasicBlock *n) const { + return A_orig[n]; + } + + bool isNonLocal(const Temp &var) const { return nonLocals.contains(var); } + +protected: + virtual void visitPhi(Phi *) {}; + virtual void visitConvert(Convert *e) { e->expr->accept(this); }; + + virtual void visitConst(Const *) {} + virtual void visitString(String *) {} + virtual void visitRegExp(RegExp *) {} + virtual void visitName(Name *) {} + virtual void visitClosure(Closure *) {} + virtual void visitUnop(V4IR::Unop *e) { e->expr->accept(this); } + virtual void visitBinop(V4IR::Binop *e) { e->left->accept(this); e->right->accept(this); } + virtual void visitSubscript(V4IR::Subscript *e) { e->base->accept(this); e->index->accept(this); } + virtual void visitMember(V4IR::Member *e) { e->base->accept(this); } + virtual void visitExp(V4IR::Exp *s) { s->expr->accept(this); } + virtual void visitEnter(V4IR::Enter *s) { s->expr->accept(this); } + virtual void visitLeave(V4IR::Leave *) {} + virtual void visitJump(V4IR::Jump *) {} + virtual void visitCJump(V4IR::CJump *s) { s->cond->accept(this); } + virtual void visitRet(V4IR::Ret *s) { s->expr->accept(this); } + virtual void visitTry(V4IR::Try *) { // ### TODO + } + + virtual void visitCall(V4IR::Call *e) { + e->base->accept(this); + for (V4IR::ExprList *it = e->args; it; it = it->next) + it->expr->accept(this); + } + + virtual void visitNew(V4IR::New *e) { + e->base->accept(this); + for (V4IR::ExprList *it = e->args; it; it = it->next) + it->expr->accept(this); + } + + virtual void visitMove(V4IR::Move *s) { + s->source->accept(this); + + if (Temp *t = s->target->asTemp()) { + if (isCollectable(t)) { +#ifdef SHOW_SSA + qout << '\t'; + t->dump(qout); + qout << " -> L" << currentBB->index << endl; +#endif // SHOW_SSA + + _defsites[*t].insert(currentBB); + A_orig[currentBB].insert(*t); + + // For semi-pruned SSA: + killed.insert(*t); + } + } + } + + virtual void visitTemp(Temp *t) + { + if (isCollectable(t)) + if (!killed.contains(*t)) + nonLocals.insert(*t); + } +}; + +void insertPhiNode(const Temp &a, BasicBlock *y, Function *f) { +#if defined(SHOW_SSA) + qout << "-> inserted phi node for variable "; + a.dump(qout); + qout << " in block " << y->index << endl; +#endif + + Phi *phiNode = f->New<Phi>(); + phiNode->targetTemp = f->New<Temp>(); + phiNode->targetTemp->init(a.kind, a.index, 0); + y->statements.prepend(phiNode); + + phiNode->incoming.resize(y->in.size()); + for (int i = 0, ei = y->in.size(); i < ei; ++i) { + Temp *t = f->New<Temp>(); + t->init(a.kind, a.index, 0); + phiNode->incoming[i] = t; + } +} + +class VariableRenamer: public StmtVisitor, public ExprVisitor +{ + Function *function; + QHash<Temp, QStack<unsigned> > stack; + QSet<BasicBlock *> seen; + + QHash<Temp, unsigned> defCounts; + + const bool variablesCanEscape; + bool isRenamable(Temp *t) const + { + switch (t->kind) { + case Temp::Formal: + case Temp::ScopedFormal: + case Temp::ScopedLocal: + return false; + case Temp::Local: + return !variablesCanEscape; + case Temp::VirtualRegister: + return true; + default: + Q_ASSERT(!"Invalid temp kind!"); + return false; + } + } + int nextFreeTemp() { + const int next = function->tempCount++; +// qDebug()<<"Next free temp:"<<next; + return next; + } + + /* + + Initialization: + for each variable a + count[a] = 0; + stack[a] = empty; + push 0 onto stack + + Rename(n) = + for each statement S in block n [1] + if S not in a phi-function + for each use of some variable x in S + i = top(stack[x]) + replace the use of x with x_i in S + for each definition of some variable a in S + count[a] = count[a] + 1 + i = count[a] + push i onto stack[a] + replace definition of a with definition of a_i in S + for each successor Y of block n [2] + Suppose n is the j-th predecessor of Y + for each phi function in Y + suppose the j-th operand of the phi-function is a + i = top(stack[a]) + replace the j-th operand with a_i + for each child X of n [3] + Rename(X) + for each statement S in block n [4] + for each definition of some variable a in S + pop stack[a] + + */ + +public: + VariableRenamer(Function *f) + : function(f) + , variablesCanEscape(f->variablesCanEscape()) + { + if (!variablesCanEscape) { + Temp t; + t.init(Temp::Local, 0, 0); + for (int i = 0, ei = f->locals.size(); i != ei; ++i) { + t.index = i; + stack[t].push(nextFreeTemp()); + } + } + + Temp t; + t.init(Temp::VirtualRegister, 0, 0); + for (int i = 0, ei = f->tempCount; i != ei; ++i) { + t.index = i; + stack[t].push(i); + } + } + + void run() { + foreach (BasicBlock *n, function->basicBlocks) + rename(n); + +#ifdef SHOW_SSA +// qout << "Temp to local mapping:" << endl; +// foreach (int key, tempMapping.keys()) +// qout << '\t' << key << " -> " << tempMapping[key] << endl; +#endif + } + + void rename(BasicBlock *n) { + if (seen.contains(n)) + return; + seen.insert(n); +// qDebug() << "I: L"<<n->index; + + // [1]: + foreach (Stmt *s, n->statements) + s->accept(this); + + QHash<Temp, unsigned> dc = defCounts; + defCounts.clear(); + + // [2]: + foreach (BasicBlock *Y, n->out) { + const int j = Y->in.indexOf(n); + Q_ASSERT(j >= 0 && j < Y->in.size()); + foreach (Stmt *s, Y->statements) { + if (Phi *phi = s->asPhi()) { + Temp *t = phi->incoming[j]->asTemp(); + unsigned newTmp = stack[*t].top(); +// qDebug()<<"I: replacing phi use"<<a<<"with"<<newTmp<<"in L"<<Y->index; + t->index = newTmp; + t->kind = Temp::VirtualRegister; + } else { + break; + } + } + } + + // [3]: + foreach (BasicBlock *X, n->out) + rename(X); + + // [4]: + for (QHash<Temp, unsigned>::const_iterator i = dc.begin(), ei = dc.end(); i != ei; ++i) { +// qDebug()<<i.key() <<" -> " << i.value(); + for (unsigned j = 0, ej = i.value(); j < ej; ++j) + stack[i.key()].pop(); + } + } + +protected: + virtual void visitTemp(Temp *e) { // only called for uses, not defs + if (isRenamable(e)) { +// qDebug()<<"I: replacing use of"<<e->index<<"with"<<stack[e->index].top(); + e->index = stack[*e].top(); + e->kind = Temp::VirtualRegister; + } + } + + virtual void visitMove(Move *s) { + // uses: + s->source->accept(this); + + // defs: + if (Temp *t = s->target->asTemp()) + renameTemp(t); + else + s->target->accept(this); + } + + void renameTemp(Temp *t) { + if (isRenamable(t)) { + defCounts[*t] = defCounts.value(*t, 0) + 1; + const int newIdx = nextFreeTemp(); + stack[*t].push(newIdx); +// qDebug()<<"I: replacing def of"<<a<<"with"<<newIdx; + t->kind = Temp::VirtualRegister; + t->index = newIdx; + } + } + + virtual void visitConvert(Convert *e) { e->expr->accept(this); } + virtual void visitPhi(Phi *s) { renameTemp(s->targetTemp); } + + virtual void visitExp(Exp *s) { s->expr->accept(this); } + virtual void visitEnter(Enter *) { Q_UNIMPLEMENTED(); abort(); } + virtual void visitLeave(Leave *) { Q_UNIMPLEMENTED(); abort(); } + + virtual void visitJump(Jump *) {} + virtual void visitCJump(CJump *s) { s->cond->accept(this); } + virtual void visitRet(Ret *s) { s->expr->accept(this); } + virtual void visitTry(Try *s) { /* this should never happen */ } + + virtual void visitConst(Const *) {} + virtual void visitString(String *) {} + virtual void visitRegExp(RegExp *) {} + virtual void visitName(Name *) {} + virtual void visitClosure(Closure *) {} + virtual void visitUnop(Unop *e) { e->expr->accept(this); } + virtual void visitBinop(Binop *e) { e->left->accept(this); e->right->accept(this); } + virtual void visitCall(Call *e) { + e->base->accept(this); + for (ExprList *it = e->args; it; it = it->next) + it->expr->accept(this); + } + + virtual void visitNew(New *e) { + e->base->accept(this); + for (ExprList *it = e->args; it; it = it->next) + it->expr->accept(this); + } + + virtual void visitSubscript(Subscript *e) { + e->base->accept(this); + e->index->accept(this); + } + + virtual void visitMember(Member *e) { + e->base->accept(this); + } +}; + +void convertToSSA(Function *function, const DominatorTree &df) +{ +#ifdef SHOW_SSA + qout << "Converting function "; + if (function->name) + qout << *function->name; + else + qout << "<no name>"; + qout << " to SSA..." << endl; +#endif // SHOW_SSA + + // Collect all applicable variables: + VariableCollector variables(function); + + // Place phi functions: + QHash<BasicBlock *, QSet<Temp> > A_phi; + foreach (Temp a, variables.vars()) { + if (!variables.isNonLocal(a)) + continue; // for semi-pruned SSA + + QList<BasicBlock *> W = QList<BasicBlock *>::fromSet(variables.defsite(a)); + while (!W.isEmpty()) { + BasicBlock *n = W.first(); + W.removeFirst(); + foreach (BasicBlock *y, df[n]) { + if (!A_phi[y].contains(a)) { + insertPhiNode(a, y, function); + A_phi[y].insert(a); + if (!variables.inBlock(y).contains(a)) + W.append(y); + } + } + } + } + showMeTheCode(function); + + // Rename variables: + VariableRenamer(function).run(); +} + +class DefUsesCalculator: public StmtVisitor, public ExprVisitor { +public: + struct DefUse { + Stmt *defStmt; + BasicBlock *blockOfStatement; + QList<Stmt *> uses; + }; + +private: + const bool _variablesCanEscape; + QHash<Temp, DefUse> _defUses; + QHash<Stmt *, QList<Temp> > _usesPerStatement; + + BasicBlock *_block; + Stmt *_stmt; + + bool isCollectible(Temp *t) const { + switch (t->kind) { + case Temp::Formal: + case Temp::ScopedFormal: + case Temp::ScopedLocal: + return false; + case Temp::Local: + return !_variablesCanEscape; + case Temp::VirtualRegister: + return true; + default: + Q_UNREACHABLE(); + return false; + } + } + + void addUse(Temp *t) { + Q_ASSERT(t); + if (!isCollectible(t)) + return; + + _defUses[*t].uses.append(_stmt); + _usesPerStatement[_stmt].append(*t); + } + + void addDef(Temp *t) { + if (!isCollectible(t)) + return; + + Q_ASSERT(!_defUses.contains(*t) || _defUses.value(*t).defStmt == 0 || _defUses.value(*t).defStmt == _stmt); + + DefUse &defUse = _defUses[*t]; + defUse.defStmt = _stmt; + defUse.blockOfStatement = _block; + } + +public: + DefUsesCalculator(Function *function) + : _variablesCanEscape(function->variablesCanEscape()) + { + foreach (BasicBlock *bb, function->basicBlocks) { + _block = bb; + foreach (Stmt *stmt, bb->statements) { + _stmt = stmt; + stmt->accept(this); + } + } + + QMutableHashIterator<Temp, DefUse> it(_defUses); + while (it.hasNext()) { + it.next(); + if (!it.value().defStmt) + it.remove(); + } + } + + QList<Temp> defs() const { + return _defUses.keys(); + } + + void removeDef(const Temp &var) { + _defUses.remove(var); + } + + void addUses(const Temp &variable, const QList<Stmt *> &newUses) + { _defUses[variable].uses.append(newUses); } + + int useCount(const Temp &variable) const + { return _defUses[variable].uses.size(); } + + Stmt *defStmt(const Temp &variable) const + { return _defUses[variable].defStmt; } + + BasicBlock *defStmtBlock(const Temp &variable) const + { return _defUses[variable].blockOfStatement; } + + void removeUse(Stmt *usingStmt, const Temp &var) + { _defUses[var].uses.removeAll(usingStmt); } + + QList<Temp> usedVars(Stmt *s) const + { return _usesPerStatement[s]; } + + QList<Stmt *> uses(const Temp &var) const + { return _defUses[var].uses; } + + void dump() const + { + foreach (const Temp &var, _defUses.keys()) { + const DefUse &du = _defUses[var]; + var.dump(qout); + qout<<" -> defined in block "<<du.blockOfStatement->index<<", statement: "; + du.defStmt->dump(qout); + qout<<endl<<" uses:"<<endl; + foreach (Stmt *s, du.uses) { + qout<<" ";s->dump(qout);qout<<endl; + } + } + } + +protected: + virtual void visitExp(Exp *s) { s->expr->accept(this); } + virtual void visitEnter(Enter *) {} + virtual void visitLeave(Leave *) {} + virtual void visitJump(Jump *) {} + virtual void visitCJump(CJump *s) { s->cond->accept(this); } + virtual void visitRet(Ret *s) { s->expr->accept(this); } + virtual void visitTry(Try *) {} + + virtual void visitPhi(Phi *s) { + addDef(s->targetTemp); + foreach (Expr *e, s->incoming) + addUse(e->asTemp()); + } + + virtual void visitMove(Move *s) { + if (Temp *t = s->target->asTemp()) + addDef(t); + else + s->target->accept(this); + + s->source->accept(this); + } + + virtual void visitTemp(Temp *e) { addUse(e); } + + virtual void visitConst(Const *) {} + virtual void visitString(String *) {} + virtual void visitRegExp(RegExp *) {} + virtual void visitName(Name *) {} + virtual void visitClosure(Closure *) {} + virtual void visitConvert(Convert *e) { e->expr->accept(this); } + virtual void visitUnop(Unop *e) { e->expr->accept(this); } + virtual void visitBinop(Binop *e) { e->left->accept(this); e->right->accept(this); } + virtual void visitSubscript(Subscript *e) { e->base->accept(this); e->index->accept(this); } + virtual void visitMember(Member *e) { e->base->accept(this); } + virtual void visitCall(Call *e) { + e->base->accept(this); + for (ExprList *it = e->args; it; it = it->next) + it->expr->accept(this); + } + + virtual void visitNew(New *e) { + e->base->accept(this); + for (ExprList *it = e->args; it; it = it->next) + it->expr->accept(this); + } +}; + +bool hasPhiOnlyUses(Phi *phi, const DefUsesCalculator &defUses, QSet<Phi *> &collectedPhis) +{ + collectedPhis.insert(phi); + foreach (Stmt *use, defUses.uses(*phi->targetTemp)) { + if (Phi *dependentPhi = use->asPhi()) { + if (!collectedPhis.contains(dependentPhi)) { + if (!hasPhiOnlyUses(dependentPhi, defUses, collectedPhis)) + return false; + } + } else { + return false; + } + } + return true; +} + +void cleanupPhis(DefUsesCalculator &defUses) +{ + QLinkedList<Phi *> phis; + foreach (const Temp &def, defUses.defs()) + if (Phi *phi = defUses.defStmt(def)->asPhi()) + phis.append(phi); + + QSet<Phi *> toRemove; + while (!phis.isEmpty()) { + Phi *phi = phis.first(); + phis.removeFirst(); + if (toRemove.contains(phi)) + continue; + QSet<Phi *> collectedPhis; + if (hasPhiOnlyUses(phi, defUses, collectedPhis)) + toRemove.unite(collectedPhis); + } + + foreach (Phi *phi, toRemove) { + Temp targetVar = *phi->targetTemp; + + BasicBlock *bb = defUses.defStmtBlock(targetVar); + int idx = bb->statements.indexOf(phi); + bb->statements.remove(idx); + + foreach (const Temp &usedVar, defUses.usedVars(phi)) + defUses.removeUse(phi, usedVar); + defUses.removeDef(targetVar); + } +} + +class DeadCodeElimination: public ExprVisitor { + const bool variablesCanEscape; + DefUsesCalculator &_defUses; + QVector<Temp> _worklist; + +public: + DeadCodeElimination(DefUsesCalculator &defUses, Function *function) + : variablesCanEscape(function->variablesCanEscape()) + , _defUses(defUses) + { + _worklist = QVector<Temp>::fromList(_defUses.defs()); + } + + void run() { + while (!_worklist.isEmpty()) { + const Temp v = _worklist.first(); + _worklist.removeFirst(); + + if (_defUses.useCount(v) == 0) { +// qDebug()<<"-"<<v<<"has no uses..."; + Stmt *s = _defUses.defStmt(v); + if (!s) { + _defUses.removeDef(v); + } else if (!hasSideEffect(s)) { +#ifdef SHOW_SSA + qout<<"-- defining stmt for"; + v.dump(qout); + qout<<"has no side effect"<<endl; +#endif + QVector<Stmt *> &stmts = _defUses.defStmtBlock(v)->statements; + int idx = stmts.indexOf(s); + if (idx != -1) + stmts.remove(idx); + foreach (const Temp &usedVar, _defUses.usedVars(s)) { + _defUses.removeUse(s, usedVar); + _worklist.append(usedVar); + } + _defUses.removeDef(v); + } + } + } + +#ifdef SHOW_SSA + qout<<"******************* After dead-code elimination:"; + _defUses.dump(); +#endif + } + +private: + bool _sideEffect; + + bool hasSideEffect(Stmt *s) { + // TODO: check if this can be moved to IR building. + _sideEffect = false; + if (Move *move = s->asMove()) { + if (Temp *t = move->target->asTemp()) { + switch (t->kind) { + case Temp::Formal: + case Temp::ScopedFormal: + case Temp::ScopedLocal: + return true; + case Temp::Local: + if (variablesCanEscape) + return true; + else + break; + case Temp::VirtualRegister: + break; + default: + Q_ASSERT(!"Invalid temp kind!"); + return true; + } + move->source->accept(this); + } else { + return true; + } + } + return _sideEffect; + } + +protected: + virtual void visitConst(Const *) {} + virtual void visitString(String *) {} + virtual void visitRegExp(RegExp *) {} + virtual void visitName(Name *e) { + // TODO: maybe we can distinguish between built-ins of which we know that they do not have + // a side-effect. + if (e->builtin == Name::builtin_invalid || (e->id && *e->id != QStringLiteral("this"))) + _sideEffect = true; + } + virtual void visitTemp(Temp *e) { + } + virtual void visitClosure(Closure *) {} + virtual void visitConvert(Convert *e) { + // we do not have type information yet, so: + _sideEffect = true; + } + + virtual void visitUnop(Unop *e) { + switch (e->op) { + case V4IR::OpIncrement: + case V4IR::OpDecrement: + _sideEffect = true; + break; + + default: + break; + } + + if (!_sideEffect) e->expr->accept(this); + } + virtual void visitBinop(Binop *e) { if (!_sideEffect) e->left->accept(this); if (!_sideEffect) e->right->accept(this); } + virtual void visitSubscript(Subscript *e) { + // TODO: see if we can have subscript accesses without side effect + _sideEffect = true; + } + virtual void visitMember(Member *e) { + // TODO: see if we can have member accesses without side effect + _sideEffect = true; + } + virtual void visitCall(Call *e) { + _sideEffect = true; // TODO: there are built-in functions that have no side effect. + } + virtual void visitNew(New *e) { + _sideEffect = true; // TODO: there are built-in types that have no side effect. + } +}; + +class TypeInference: public StmtVisitor, public ExprVisitor { + bool _variablesCanEscape; + const DefUsesCalculator &_defUses; + QHash<Temp, int> _tempTypes; + QSet<Stmt *> _worklist; + struct TypingResult { + int type; + bool fullyTyped; + + TypingResult(int type, bool fullyTyped): type(type), fullyTyped(fullyTyped) {} + explicit TypingResult(int type = UnknownType): type(type), fullyTyped(type != UnknownType) {} + }; + TypingResult _ty; + +public: + TypeInference(const DefUsesCalculator &defUses) + : _defUses(defUses) + , _ty(UnknownType) + {} + + void run(Function *function) { + _variablesCanEscape = function->variablesCanEscape(); + + // TODO: the worklist handling looks a bit inefficient... check if there is something better + _worklist.clear(); + for (int i = 0, ei = function->basicBlocks.size(); i != ei; ++i) { + BasicBlock *bb = function->basicBlocks[i]; + if (i == 0 || !bb->in.isEmpty()) + foreach (Stmt *s, bb->statements) + _worklist.insert(s); + } + + while (!_worklist.isEmpty()) { + QList<Stmt *> worklist = _worklist.values(); + _worklist.clear(); + while (!worklist.isEmpty()) { + Stmt *s = worklist.first(); + worklist.removeFirst(); +#if defined(SHOW_SSA) + qout<<"Typing stmt ";s->dump(qout);qout<<endl; +#endif + + if (!run(s)) { + _worklist.insert(s); +#if defined(SHOW_SSA) + qout<<"Pushing back stmt: "; + s->dump(qout);qout<<endl; + } else { + qout<<"Finished: "; + s->dump(qout);qout<<endl; +#endif + } + } + } + } + +private: + bool run(Stmt *s) { + TypingResult ty; + std::swap(_ty, ty); + s->accept(this); + std::swap(_ty, ty); + return ty.fullyTyped; + } + + TypingResult run(Expr *e) { + TypingResult ty; + std::swap(_ty, ty); + e->accept(this); + std::swap(_ty, ty); + + if (ty.type != UnknownType) + setType(e, ty.type); + return ty; + } + + bool isAlwaysAnObject(Temp *t) { + switch (t->kind) { + case Temp::Formal: + case Temp::ScopedFormal: + case Temp::ScopedLocal: + return true; + case Temp::Local: + return _variablesCanEscape; + default: + return false; + } + } + + void setType(Expr *e, int ty) { + if (Temp *t = e->asTemp()) { +#if defined(SHOW_SSA) + qout<<"Setting type for "<< (t->scope?"scoped temp ":"temp ") <<t->index<< " to "<<typeName(Type(ty)) << " (" << ty << ")" << endl; +#endif + if (isAlwaysAnObject(t)) { + e->type = ObjectType; + } else { + e->type = (Type) ty; + + if (_tempTypes[*t] != ty) { + _tempTypes[*t] = ty; + +#if defined(SHOW_SSA) + foreach (Stmt *s, _defUses.uses(*t)) { + qout << "Pushing back dependent stmt: "; + s->dump(qout); + qout << endl; + } +#endif + + _worklist += QSet<Stmt *>::fromList(_defUses.uses(*t)); + } + } + } else { + e->type = (Type) ty; + } + } + +protected: + virtual void visitConst(Const *e) { _ty = TypingResult(e->type); } + virtual void visitString(String *) { _ty = TypingResult(StringType); } + virtual void visitRegExp(RegExp *) { _ty = TypingResult(ObjectType); } + virtual void visitName(Name *) { _ty = TypingResult(ObjectType); } + virtual void visitTemp(Temp *e) { + if (isAlwaysAnObject(e)) + _ty = TypingResult(ObjectType); + else + _ty = TypingResult(_tempTypes.value(*e, UnknownType)); + setType(e, _ty.type); + } + virtual void visitClosure(Closure *) { _ty = TypingResult(ObjectType); } // TODO: VERIFY THIS! + virtual void visitConvert(Convert *e) { + _ty = run(e->expr); + } + + virtual void visitUnop(Unop *e) { + _ty = run(e->expr); + switch (e->op) { + case OpUPlus: _ty.type = DoubleType; return; + case OpUMinus: _ty.type = DoubleType; return; + case OpCompl: _ty.type = SInt32Type; return; + case OpNot: _ty.type = BoolType; return; + + case OpIncrement: + case OpDecrement: + Q_ASSERT(!"Inplace operators should have been removed!"); + default: + Q_UNIMPLEMENTED(); + Q_UNREACHABLE(); + } + } + + virtual void visitBinop(Binop *e) { + TypingResult leftTy = run(e->left); + TypingResult rightTy = run(e->right); + _ty.fullyTyped = leftTy.fullyTyped && rightTy.fullyTyped; + + switch (e->op) { + case OpAdd: + if (leftTy.type & StringType || rightTy.type & StringType) + _ty.type = StringType; + else if (leftTy.type != UnknownType && rightTy.type != UnknownType) + _ty.type = DoubleType; + else + _ty.type = UnknownType; + break; + case OpSub: + _ty.type = DoubleType; + break; + + case OpMul: + case OpDiv: + case OpMod: + _ty.type = DoubleType; + break; + + case OpBitAnd: + case OpBitOr: + case OpBitXor: + case OpLShift: + case OpRShift: + _ty.type = SInt32Type; + break; + case OpURShift: + _ty.type = UInt32Type; + break; + + case OpGt: + case OpLt: + case OpGe: + case OpLe: + case OpEqual: + case OpNotEqual: + case OpStrictEqual: + case OpStrictNotEqual: + case OpAnd: + case OpOr: + case OpInstanceof: + case OpIn: + _ty.type = BoolType; + break; + + default: + Q_UNIMPLEMENTED(); + Q_UNREACHABLE(); + } + } + + virtual void visitCall(Call *e) { + _ty = run(e->base); + for (ExprList *it = e->args; it; it = it->next) + _ty.fullyTyped &= run(it->expr).fullyTyped; + _ty.type = ObjectType; + } + virtual void visitNew(New *e) { + _ty = run(e->base); + for (ExprList *it = e->args; it; it = it->next) + _ty.fullyTyped &= run(it->expr).fullyTyped; + _ty.type = ObjectType; + } + virtual void visitSubscript(Subscript *e) { + _ty.fullyTyped = run(e->base).fullyTyped && run(e->index).fullyTyped; + _ty.type = ObjectType; + } + + virtual void visitMember(Member *e) { + // TODO: for QML, try to do a static lookup + _ty = run(e->base); + _ty.type = ObjectType; + } + + virtual void visitExp(Exp *s) { _ty = run(s->expr); } + virtual void visitEnter(Enter *s) { _ty = run(s->expr); } + virtual void visitLeave(Leave *) { _ty = TypingResult(MissingType); } + virtual void visitMove(Move *s) { + TypingResult sourceTy = run(s->source); + Q_ASSERT(s->op == OpInvalid); + if (Temp *t = s->target->asTemp()) { + setType(t, sourceTy.type); + _ty = sourceTy; + return; + } + + _ty = run(s->target); + _ty.fullyTyped &= sourceTy.fullyTyped; + } + + virtual void visitJump(Jump *) { _ty = TypingResult(MissingType); } + virtual void visitCJump(CJump *s) { _ty = run(s->cond); } + virtual void visitRet(Ret *s) { _ty = run(s->expr); } + virtual void visitTry(Try *s) { setType(s->exceptionVar, ObjectType); _ty = TypingResult(MissingType); } + virtual void visitPhi(Phi *s) { + _ty = run(s->incoming[0]); + for (int i = 1, ei = s->incoming.size(); i != ei; ++i) { + TypingResult ty = run(s->incoming[i]); + _ty.type |= ty.type; + _ty.fullyTyped &= ty.fullyTyped; + } + + // TODO: check & double check the next condition! + if (_ty.type & ObjectType || _ty.type & UndefinedType || _ty.type & NullType) + _ty.type = ObjectType; + else if (_ty.type & NumberType) + _ty.type = DoubleType; + + setType(s->targetTemp, _ty.type); + } +}; + +class TypePropagation: public StmtVisitor, public ExprVisitor { + Type _ty; + + void run(Expr *&e, Type requestedType = UnknownType) { + qSwap(_ty, requestedType); + e->accept(this); + qSwap(_ty, requestedType); + + if (requestedType != UnknownType) + if (e->type != requestedType) + if (requestedType & NumberType) { +// qDebug()<<"adding conversion from"<<typeName(e->type)<<"to"<<typeName(requestedType); + addConversion(e, requestedType); + } + } + + struct Conversion { + Expr **expr; + Type targetType; + Stmt *stmt; + + Conversion(Expr **expr = 0, Type targetType = UnknownType, Stmt *stmt = 0) + : expr(expr) + , targetType(targetType) + , stmt(stmt) + {} + }; + + Stmt *_currStmt; + QVector<Conversion> _conversions; + + void addConversion(Expr *&expr, Type targetType) { + _conversions.append(Conversion(&expr, targetType, _currStmt)); + } + +public: + TypePropagation() : _ty(UnknownType) {} + + void run(Function *f) { + foreach (BasicBlock *bb, f->basicBlocks) { + _conversions.clear(); + + foreach (Stmt *s, bb->statements) { + _currStmt = s; + s->accept(this); + } + + foreach (const Conversion &conversion, _conversions) { + if (conversion.stmt->asMove() && conversion.stmt->asMove()->source->asTemp()) { + *conversion.expr = bb->CONVERT(*conversion.expr, conversion.targetType); + } else { + Temp *target = bb->TEMP(bb->newTemp()); + target->type = conversion.targetType; + Expr *convert = bb->CONVERT(*conversion.expr, conversion.targetType); + Move *convCall = f->New<Move>(); + convCall->init(target, convert, OpInvalid); + + Temp *source = bb->TEMP(target->index); + source->type = conversion.targetType; + *conversion.expr = source; + + int idx = bb->statements.indexOf(conversion.stmt); + bb->statements.insert(idx, convCall); + } + } + } + } + +protected: + virtual void visitConst(Const *c) { + if (_ty & NumberType && c->type & NumberType) { + c->type = _ty; + } + } + + virtual void visitString(String *) {} + virtual void visitRegExp(RegExp *) {} + virtual void visitName(Name *) {} + virtual void visitTemp(Temp *) {} + virtual void visitClosure(Closure *) {} + virtual void visitConvert(Convert *e) { run(e->expr, e->type); } + virtual void visitUnop(Unop *e) { run(e->expr, e->type); } + virtual void visitBinop(Binop *e) { + // FIXME: This routine needs more tuning! + switch (e->op) { + case OpAdd: + case OpSub: + case OpMul: + case OpDiv: + case OpMod: + case OpBitAnd: + case OpBitOr: + case OpBitXor: + case OpLShift: + case OpRShift: + case OpURShift: + run(e->left, e->type); + run(e->right, e->type); + break; + + case OpGt: + case OpLt: + case OpGe: + case OpLe: + if (e->left->type == DoubleType) + run(e->right, DoubleType); + else if (e->right->type == DoubleType) + run(e->left, DoubleType); + else { + run(e->left, e->type); + run(e->right, e->type); + } + break; + + case OpEqual: + case OpNotEqual: + case OpStrictEqual: + case OpStrictNotEqual: + break; + + case OpInstanceof: + case OpIn: + run(e->left, e->type); + run(e->right, e->type); + break; + + default: + Q_UNIMPLEMENTED(); + Q_UNREACHABLE(); + } + } + virtual void visitCall(Call *e) { + run(e->base); + for (ExprList *it = e->args; it; it = it->next) + run(it->expr); + } + virtual void visitNew(New *e) { + run(e->base); + for (ExprList *it = e->args; it; it = it->next) + run(it->expr); + } + virtual void visitSubscript(Subscript *e) { run(e->base); run(e->index); } + virtual void visitMember(Member *e) { run(e->base); } + virtual void visitExp(Exp *s) { run(s->expr); } + virtual void visitEnter(Enter *s) { run(s->expr); } + virtual void visitLeave(Leave *) {} + virtual void visitMove(Move *s) { + run(s->target); + run(s->source, s->target->type); + } + virtual void visitJump(Jump *) {} + virtual void visitCJump(CJump *s) { + run(s->cond, BoolType); + } + virtual void visitRet(Ret *s) { run(s->expr); } + virtual void visitTry(Try *) {} + virtual void visitPhi(Phi *s) { + Type ty = s->targetTemp->type; + foreach (Expr *e, s->incoming) + if (e->asConst()) + run(e, ty); + } +}; + +void insertMove(Function *function, BasicBlock *basicBlock, Temp *target, Expr *source) { + if (target->type != source->type) + source = basicBlock->CONVERT(source, target->type); + + Move *s = function->New<Move>(); + s->init(target, source, OpInvalid); + basicBlock->statements.insert(basicBlock->statements.size() - 1, s); +} + +bool doEdgeSplitting(Function *f) +{ + const QVector<BasicBlock *> oldBBs = f->basicBlocks; + + foreach (BasicBlock *bb, oldBBs) { + if (bb->in.size() > 1) { + for (int inIdx = 0, eInIdx = bb->in.size(); inIdx != eInIdx; ++inIdx) { + BasicBlock *inBB = bb->in[inIdx]; + if (inBB->out.size() > 1) { // this should have been split! +#if defined(SHOW_SSA) + qDebug() << "Splitting edge from block" << inBB->index << "to block" << bb->index; +#endif + + // create the basic block: + BasicBlock *newBB = new BasicBlock(f, bb->containingGroup()); + newBB->index = f->basicBlocks.last()->index + 1; + f->basicBlocks.append(newBB); + Jump *s = f->New<Jump>(); + s->init(bb); + newBB->statements.append(s); + + // rewire the old outgoing edge + int outIdx = inBB->out.indexOf(bb); + inBB->out[outIdx] = newBB; + newBB->in.append(inBB); + + // rewire the old incoming edge + bb->in[inIdx] = newBB; + newBB->out.append(bb); + + // patch the terminator + Stmt *terminator = inBB->terminator(); + if (Jump *j = terminator->asJump()) { + Q_ASSERT(outIdx == 0); + j->target = newBB; + } else if (CJump *j = terminator->asCJump()) { + if (outIdx == 0) + j->iftrue = newBB; + else if (outIdx == 1) + j->iffalse = newBB; + else + Q_ASSERT(!"Invalid out edge index for CJUMP!"); + } else { + Q_ASSERT(!"Unknown terminator!"); + } + } + } + } + } +} + +void scheduleBlocks(Function *function, const DominatorTree &df) +{ + struct I { + const DominatorTree &df; + QSet<BasicBlock *> visited; + QVector<BasicBlock *> &sequence; + BasicBlock *currentGroup; + QList<BasicBlock *> postponed; + + I(const DominatorTree &df, QVector<BasicBlock *> &sequence) + : df(df), sequence(sequence), currentGroup(0) + {} + + void DFS(BasicBlock *bb) { + Q_ASSERT(bb); + if (visited.contains(bb)) + return; + + if (bb->containingGroup() != currentGroup) { + postponed.append(bb); + return; + } + if (bb->isGroupStart()) + currentGroup = bb; + else if (bb->in.size() > 1) + foreach (BasicBlock *inBB, bb->in) + if (!visited.contains(inBB)) + return; + + Q_ASSERT(df.immediateDominator(bb) == 0 || sequence.contains(df.immediateDominator(bb))); + layout(bb); + if (Stmt *terminator = bb->terminator()) { + if (Jump *j = terminator->asJump()) { + Q_ASSERT(bb->out.size() == 1); + DFS(j->target); + } else if (CJump *cj = terminator->asCJump()) { + Q_ASSERT(bb->out.size() == 2); + DFS(cj->iftrue); + DFS(cj->iffalse); + } else if (terminator->asRet()) { + Q_ASSERT(bb->out.size() == 0); + // nothing to do. + } else { + Q_UNREACHABLE(); + } + } else { + Q_UNREACHABLE(); + } + + if (bb->isGroupStart()) { + currentGroup = bb->containingGroup(); + QList<BasicBlock *> p = postponed; + foreach (BasicBlock *pBB, p) + DFS(pBB); + } + } + + void layout(BasicBlock *bb) { + sequence.append(bb); + visited.insert(bb); + postponed.removeAll(bb); + } + }; + + QVector<BasicBlock *> sequence; + sequence.reserve(function->basicBlocks.size()); + I(df, sequence).DFS(function->basicBlocks.first()); + qSwap(function->basicBlocks, sequence); + + showMeTheCode(function); +} + +/* + * Quick function to convert out of SSA, so we can put the stuff through the ISel phases. This + * has to be replaced by a phase in the specific ISel back-ends and do register allocation at the + * same time. That way the huge number of redundant moves generated by this function are eliminated. + */ +void convertOutOfSSA(Function *function) { + // We assume that edge-splitting is already done. + foreach (BasicBlock *bb, function->basicBlocks) { + QVector<Stmt *> &stmts = bb->statements; + while (!stmts.isEmpty()) { + Stmt *s = stmts.first(); + if (Phi *phi = s->asPhi()) { + stmts.removeFirst(); + for (int i = 0, ei = phi->incoming.size(); i != ei; ++i) + insertMove(function, bb->in[i], phi->targetTemp, phi->incoming[i]); + } else { + break; + } + } + } +} + +void checkCriticalEdges(QVector<BasicBlock *> basicBlocks) { + foreach (BasicBlock *bb, basicBlocks) { + if (bb && bb->out.size() > 1) { + foreach (BasicBlock *bb2, bb->out) { + if (bb2 && bb2->in.size() > 1) { + qout << "found critical edge between block " + << bb->index << " and block " << bb2->index; + Q_ASSERT(false); + } + } + } + } +} + +void cleanupBasicBlocks(Function *function) +{ +// showMeTheCode(function); + + // remove all basic blocks that have no incoming edges, but skip the entry block + QVector<BasicBlock *> W = function->basicBlocks; + W.removeFirst(); + QSet<BasicBlock *> toRemove; + + while (!W.isEmpty()) { + BasicBlock *bb = W.first(); + W.removeFirst(); + if (toRemove.contains(bb)) + continue; + if (bb->in.isEmpty()) { + foreach (BasicBlock *outBB, bb->out) { + int idx = outBB->in.indexOf(bb); + if (idx != -1) { + outBB->in.remove(idx); + W.append(outBB); + } + } + toRemove.insert(bb); + } + } + + // TODO: merge 2 basic blocks A and B if A has one outgoing edge (to B), B has one incoming + // edge (from A), but not when A has more than 1 incoming edge and B has more than one + // outgoing edge. + + foreach (BasicBlock *bb, toRemove) { + foreach (Stmt *s, bb->statements) + s->destroyData(); + int idx = function->basicBlocks.indexOf(bb); + if (idx != -1) + function->basicBlocks.remove(idx); + delete bb; + } + + // re-number all basic blocks: + for (int i = 0; i < function->basicBlocks.size(); ++i) + function->basicBlocks[i]->index = i; +} + +} // end of anonymous namespace + +void QQmlJS::linearize(V4IR::Function *function) +{ +#if defined(SHOW_SSA) + qout << "##### NOW IN FUNCTION " << (function->name ? qPrintable(*function->name) : "anonymous!") << " with " << function->basicBlocks.size() << " basic blocks." << endl << flush; +#endif + + // Number all basic blocks, so we have nice numbers in the dumps: + for (int i = 0; i < function->basicBlocks.size(); ++i) + function->basicBlocks[i]->index = i; + showMeTheCode(function); + + cleanupBasicBlocks(function); + + function->removeSharedExpressions(); + +// showMeTheCode(function); + + if (!function->hasTry && !function->hasWith) { +// qout << "Starting edge splitting..." << endl; + doEdgeSplitting(function); +// showMeTheCode(function); + + // Calculate the dominator tree: + DominatorTree df(function->basicBlocks); + + convertToSSA(function, df); +// showMeTheCode(function); + +// qout << "Starting def/uses calculation..." << endl; + DefUsesCalculator defUses(function); + +// qout << "Cleaning up phi nodes..." << endl; + cleanupPhis(defUses); +// showMeTheCode(function); + +// qout << "Starting dead-code elimination..." << endl; + DeadCodeElimination(defUses, function).run(); +// showMeTheCode(function); + +// qout << "Running type inference..." << endl; + TypeInference(defUses).run(function); +// showMeTheCode(function); + +// qout << "Doing type propagation..." << endl; + TypePropagation().run(function); +// showMeTheCode(function); + +// qout << "Doing block scheduling..." << endl; + scheduleBlocks(function, df); +// showMeTheCode(function); + +// qout << "Converting out of SSA..." << endl; + convertOutOfSSA(function); +// showMeTheCode(function); + +#ifndef QT_NO_DEBUG + checkCriticalEdges(function->basicBlocks); +#endif + +// qout << "Finished." << endl; + } +} |