diff options
-rw-r--r-- | src/qml/qml/v4/moth/qv4instr_moth_p.h | 24 | ||||
-rw-r--r-- | src/qml/qml/v4/moth/qv4isel_moth.cpp | 39 | ||||
-rw-r--r-- | src/qml/qml/v4/moth/qv4isel_moth_p.h | 2 | ||||
-rw-r--r-- | src/qml/qml/v4/moth/qv4vme_moth.cpp | 18 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4codegen.cpp | 804 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4codegen_p.h | 1 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4isel_llvm.cpp | 2 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4isel_llvm_p.h | 2 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4isel_masm.cpp | 56 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4isel_masm_p.h | 6 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4isel_p.cpp | 20 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4isel_p.h | 4 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4isel_util_p.h | 6 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4jsir.cpp | 74 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4jsir_p.h | 64 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4ssa.cpp | 1691 | ||||
-rw-r--r-- | src/qml/qml/v4/qv4ssa_p.h | 53 | ||||
-rw-r--r-- | src/qml/qml/v4/v4.pri | 2 | ||||
-rw-r--r-- | tests/manual/v4/fact.js | 13 |
19 files changed, 2023 insertions, 858 deletions
diff --git a/src/qml/qml/v4/moth/qv4instr_moth_p.h b/src/qml/qml/v4/moth/qv4instr_moth_p.h index ed762afb2d..0f28ed311c 100644 --- a/src/qml/qml/v4/moth/qv4instr_moth_p.h +++ b/src/qml/qml/v4/moth/qv4instr_moth_p.h @@ -54,6 +54,9 @@ F(CJump, cjump) \ F(Unop, unop) \ F(Binop, binop) \ + F(AddNumberParams, addNumberParams) \ + F(MulNumberParams, mulNumberParams) \ + F(SubNumberParams, subNumberParams) \ F(LoadThis, loadThis) \ F(InplaceElementOp, inplaceElementOp) \ F(InplaceMemberOp, inplaceMemberOp) \ @@ -427,6 +430,24 @@ union Instr Param rhs; Param result; }; + struct instr_addNumberParams { + MOTH_INSTR_HEADER + Param lhs; + Param rhs; + Param result; + }; + struct instr_mulNumberParams { + MOTH_INSTR_HEADER + Param lhs; + Param rhs; + Param result; + }; + struct instr_subNumberParams { + MOTH_INSTR_HEADER + Param lhs; + Param rhs; + Param result; + }; struct instr_loadThis { MOTH_INSTR_HEADER Param result; @@ -502,6 +523,9 @@ union Instr instr_cjump cjump; instr_unop unop; instr_binop binop; + instr_addNumberParams addNumberParams; + instr_mulNumberParams mulNumberParams; + instr_subNumberParams subNumberParams; instr_loadThis loadThis; instr_inplaceElementOp inplaceElementOp; instr_inplaceMemberOp inplaceMemberOp; diff --git a/src/qml/qml/v4/moth/qv4isel_moth.cpp b/src/qml/qml/v4/moth/qv4isel_moth.cpp index 9fb105ec77..9371806b4f 100644 --- a/src/qml/qml/v4/moth/qv4isel_moth.cpp +++ b/src/qml/qml/v4/moth/qv4isel_moth.cpp @@ -6,6 +6,8 @@ #include <private/qv4debugging_p.h> #include <private/qv4function_p.h> +#undef USE_TYPE_INFO + using namespace QQmlJS; using namespace QQmlJS::Moth; @@ -348,8 +350,41 @@ void InstructionSelection::unop(V4IR::AluOp oper, V4IR::Temp *sourceTemp, V4IR:: } } -void InstructionSelection::binop(V4IR::AluOp oper, V4IR::Temp *leftSource, V4IR::Temp *rightSource, V4IR::Temp *target) -{ +void InstructionSelection::binop(V4IR::AluOp oper, V4IR::Expr *leftSource, V4IR::Expr *rightSource, V4IR::Temp *target) +{ +#ifdef USE_TYPE_INFO + if (leftSource->type & V4IR::NumberType && rightSource->type & V4IR::NumberType) { + // TODO: add Temp+Const variation on the topic. + switch (oper) { + case V4IR::OpAdd: { + Instruction::AddNumberParams instr; + instr.lhs = getParam(leftSource); + instr.rhs = getParam(rightSource); + instr.result = getResultParam(target); + addInstruction(instr); + } return; + case V4IR::OpMul: { + Instruction::MulNumberParams instr; + instr.lhs = getParam(leftSource); + instr.rhs = getParam(rightSource); + instr.result = getResultParam(target); + addInstruction(instr); + } return; + case V4IR::OpSub: { + Instruction::SubNumberParams instr; + instr.lhs = getParam(leftSource); + instr.rhs = getParam(rightSource); + instr.result = getResultParam(target); + addInstruction(instr); + } return; + default: + break; + } + } +#else // !USE_TYPE_INFO + Q_ASSERT(leftSource->asTemp() && rightSource->asTemp()); +#endif // USE_TYPE_INFO + Instruction::Binop binop; binop.alu = aluOpFunction(oper); binop.lhs = getParam(leftSource); diff --git a/src/qml/qml/v4/moth/qv4isel_moth_p.h b/src/qml/qml/v4/moth/qv4isel_moth_p.h index 58f8eec03b..09d9de7c49 100644 --- a/src/qml/qml/v4/moth/qv4isel_moth_p.h +++ b/src/qml/qml/v4/moth/qv4isel_moth_p.h @@ -74,7 +74,7 @@ protected: virtual void setElement(V4IR::Temp *source, V4IR::Temp *targetBase, V4IR::Temp *targetIndex); virtual void copyValue(V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp); virtual void unop(V4IR::AluOp oper, V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp); - virtual void binop(V4IR::AluOp oper, V4IR::Temp *leftSource, V4IR::Temp *rightSource, V4IR::Temp *target); + virtual void binop(V4IR::AluOp oper, V4IR::Expr *leftSource, V4IR::Expr *rightSource, V4IR::Temp *target); virtual void inplaceNameOp(V4IR::AluOp oper, V4IR::Temp *rightSource, const QString &targetName); virtual void inplaceElementOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBaseTemp, V4IR::Temp *targetIndexTemp); virtual void inplaceMemberOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBase, const QString &targetName); diff --git a/src/qml/qml/v4/moth/qv4vme_moth.cpp b/src/qml/qml/v4/moth/qv4vme_moth.cpp index 3a11e2af39..675437330f 100644 --- a/src/qml/qml/v4/moth/qv4vme_moth.cpp +++ b/src/qml/qml/v4/moth/qv4vme_moth.cpp @@ -485,6 +485,24 @@ QV4::Value VME::run(QV4::ExecutionContext *context, const uchar *&code, instr.alu(context, VALUEPTR(instr.result), VALUE(instr.lhs), VALUE(instr.rhs)); MOTH_END_INSTR(Binop) + MOTH_BEGIN_INSTR(AddNumberParams) + double lhs = VALUEPTR(instr.lhs)->asDouble(); + double rhs = VALUEPTR(instr.rhs)->asDouble(); + VALUEPTR(instr.result)->setDouble(lhs + rhs); + MOTH_END_INSTR(AddNumberParams) + + MOTH_BEGIN_INSTR(MulNumberParams) + double lhs = VALUEPTR(instr.lhs)->asDouble(); + double rhs = VALUEPTR(instr.rhs)->asDouble(); + VALUEPTR(instr.result)->setDouble(lhs * rhs); + MOTH_END_INSTR(MulNumberParams) + + MOTH_BEGIN_INSTR(SubNumberParams) + double lhs = VALUEPTR(instr.lhs)->asDouble(); + double rhs = VALUEPTR(instr.rhs)->asDouble(); + VALUEPTR(instr.result)->setDouble(lhs - rhs); + MOTH_END_INSTR(SubNumberParams) + MOTH_BEGIN_INSTR(Ret) QV4::Value &result = VALUE(instr.result); // TRACE(Ret, "returning value %s", result.toString(context)->toQString().toUtf8().constData()); diff --git a/src/qml/qml/v4/qv4codegen.cpp b/src/qml/qml/v4/qv4codegen.cpp index fcbca56b38..ab48038efb 100644 --- a/src/qml/qml/v4/qv4codegen.cpp +++ b/src/qml/qml/v4/qv4codegen.cpp @@ -40,6 +40,7 @@ ****************************************************************************/ #include "qv4codegen_p.h" +#include "qv4ssa_p.h" #include "qv4util_p.h" #include "qv4debugging_p.h" @@ -48,6 +49,7 @@ #include <QtCore/QSet> #include <QtCore/QBuffer> #include <QtCore/QBitArray> +#include <QtCore/QLinkedList> #include <QtCore/QStack> #include <private/qqmljsast_p.h> #include <qv4runtime_p.h> @@ -60,585 +62,12 @@ #undef CONST #endif +#define QV4_NO_LIVENESS +#undef SHOW_SSA + using namespace QQmlJS; using namespace AST; -namespace { -QTextStream qout(stdout, QIODevice::WriteOnly); - -void dfs(V4IR::BasicBlock *block, - QSet<V4IR::BasicBlock *> *V, - QVector<V4IR::BasicBlock *> *blocks) -{ - if (! V->contains(block)) { - V->insert(block); - - foreach (V4IR::BasicBlock *succ, block->out) - dfs(succ, V, blocks); - - blocks->append(block); - } -} - -struct ComputeUseDef: V4IR::StmtVisitor, V4IR::ExprVisitor -{ - V4IR::Function *_function; - V4IR::Stmt *_stmt; - - ComputeUseDef(V4IR::Function *function) - : _function(function) - , _stmt(0) {} - - void operator()(V4IR::Stmt *s) { - assert(! s->d); - s->d = new V4IR::Stmt::Data; - qSwap(_stmt, s); - _stmt->accept(this); - qSwap(_stmt, s); - } - - virtual void visitConst(V4IR::Const *) {} - virtual void visitString(V4IR::String *) {} - virtual void visitRegExp(V4IR::RegExp *) {} - virtual void visitName(V4IR::Name *) {} - virtual void visitClosure(V4IR::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 *) {} - 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 *t) { - if (! _stmt->d->defs.contains(t->exceptionVar->index)) - _stmt->d->defs.append(t->exceptionVar->index); - } - - virtual void visitTemp(V4IR::Temp *e) { - if (e->index < 0 || e->scope != 0) - return; - - if (! _stmt->d->uses.contains(e->index)) - _stmt->d->uses.append(e->index); - } - - 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) { - if (V4IR::Temp *t = s->target->asTemp()) { - if (t->index >= 0 && t->scope == 0) // only collect unscoped locals and temps - if (! _stmt->d->defs.contains(t->index)) - _stmt->d->defs.append(t->index); - } else { - // source was not a temp, but maybe a sub-expression has a temp - // (e.g. base expressions for subscripts/member-access), - // so visit it. - s->target->accept(this); - } - // whatever the target expr was, always visit the source expr to collect - // temps there. - s->source->accept(this); - } -}; - -void liveness(V4IR::Function *function) -{ - QSet<V4IR::BasicBlock *> V; - QVector<V4IR::BasicBlock *> blocks; - - ComputeUseDef computeUseDef(function); - foreach (V4IR::BasicBlock *block, function->basicBlocks) { - foreach (V4IR::Stmt *s, block->statements) - computeUseDef(s); - } - - dfs(function->basicBlocks.at(0), &V, &blocks); - - bool changed; - do { - changed = false; - - foreach (V4IR::BasicBlock *block, blocks) { - const QBitArray previousLiveIn = block->liveIn; - const QBitArray previousLiveOut = block->liveOut; - QBitArray live(function->tempCount); - foreach (V4IR::BasicBlock *succ, block->out) - live |= succ->liveIn; - block->liveOut = live; - for (int i = block->statements.size() - 1; i != -1; --i) { - V4IR::Stmt *s = block->statements.at(i); - s->d->liveOut = live; - foreach (unsigned d, s->d->defs) - live.clearBit(d); - foreach (unsigned u, s->d->uses) - live.setBit(u); - s->d->liveIn = live; - } - block->liveIn = live; - if (! changed) { - if (previousLiveIn != block->liveIn || previousLiveOut != block->liveOut) - changed = true; - } - } - } while (changed); -} - -static inline bool isDeadAssignment(V4IR::Stmt *stmt, int localCount) -{ - V4IR::Move *move = stmt->asMove(); - if (!move || move->op != V4IR::OpInvalid) - return false; - V4IR::Temp *target = move->target->asTemp(); - if (!target) - return false; - if (target->scope || target->index < localCount) - return false; - - if (V4IR::Name *n = move->source->asName()) { - if (*n->id != QStringLiteral("this")) - return false; - } else if (!move->source->asConst() && !move->source->asTemp()) { - return false; - } - - return !stmt->d->liveOut.at(target->index); -} - -void removeDeadAssignments(V4IR::Function *function) -{ - const int localCount = function->locals.size(); - foreach (V4IR::BasicBlock *bb, function->basicBlocks) { - QVector<V4IR::Stmt *> &statements = bb->statements; - for (int i = 0; i < statements.size(); ) { - //qout<<"removeDeadAssignments: considering ";statements.at(i)->dump(qout);qout<<"\n";qout.flush(); - if (isDeadAssignment(statements.at(i), localCount)) { - statements.at(i)->destroyData(); - statements.remove(i); - } else - ++i; - } - } -} - -void removeUnreachableBlocks(V4IR::Function *function) -{ - // TODO: change this to use a worklist. - // FIXME: actually, use SSA and then re-implement it. - - for (int i = 1, ei = function->basicBlocks.size(); i != ei; ++i) { - V4IR::BasicBlock *bb = function->basicBlocks[i]; - if (bb->in.isEmpty()) { - function->basicBlocks.remove(i); - foreach (V4IR::BasicBlock *outBB, bb->out) { - int idx = outBB->in.indexOf(bb); - if (idx != -1) - outBB->in.remove(idx); - } - removeUnreachableBlocks(function); - return; - } - } -} - -class ConstantPropagation: public V4IR::StmtVisitor, public V4IR::ExprVisitor -{ - struct Value { - enum Type { - InvalidType = 0, - UndefinedType, - NullType, - BoolType, - NumberType, - ThisType, - StringType - } type; - - union { - double numberValue; - V4IR::String *stringValue; - }; - - Value() - : type(InvalidType), stringValue(0) - {} - - explicit Value(V4IR::String *str) - : type(StringType), stringValue(str) - {} - - explicit Value(Type t) - : type(t), stringValue(0) - {} - - Value(Type t, double val) - : type(t), numberValue(val) - {} - - bool isValid() const - { return type != InvalidType; } - - bool operator<(const Value &other) const - { - if (type < other.type) - return true; - if (type == Value::NumberType && other.type == Value::NumberType) { - if (numberValue == 0 && other.numberValue == 0) - return isNegative(numberValue) && !isNegative(other.numberValue); - else - return numberValue < other.numberValue; - } - if (type == Value::BoolType && other.type == Value::BoolType) - return numberValue < other.numberValue; - if (type == Value::StringType && other.type == Value::StringType) - return *stringValue->value < *other.stringValue->value; - return false; - } - - bool operator==(const Value &other) const - { - if (type != other.type) - return false; - if (type == Value::NumberType && other.type == Value::NumberType) { - if (numberValue == 0 && other.numberValue == 0) - return isNegative(numberValue) == isNegative(other.numberValue); - else - return numberValue == other.numberValue; - } - if (type == Value::BoolType && other.type == Value::BoolType) - return numberValue == other.numberValue; - if (type == Value::StringType && other.type == Value::StringType) - return *stringValue->value == *other.stringValue->value; - return false; - } - }; - -public: - void run(V4IR::Function *function) - { - if (function->hasTry) - return; - localCount = function->locals.size(); - if (function->hasWith) { - thisTemp = -1; - } else { - V4IR::BasicBlock *entryBlock = function->basicBlocks.at(0); - thisTemp = entryBlock->newTemp(); - V4IR::Move *fetchThis = function->New<V4IR::Move>(); - fetchThis->init(entryBlock->TEMP(thisTemp), - entryBlock->NAME(QStringLiteral("this"), 0, 0), - V4IR::OpInvalid); - entryBlock->statements.prepend(fetchThis); - } - - foreach (V4IR::BasicBlock *block, function->basicBlocks) { -// qDebug()<<"--- Starting with BB"<<block->index; - reset(); - QVector<V4IR::Stmt *> &statements = block->statements; - foreach (V4IR::Stmt *stmt, statements) { -// qout<<"*** ";stmt->dump(qout);qout<<"\n";qout.flush(); - stmt->accept(this); - } - } - } - -protected: - virtual void visitConst(V4IR::Const *) {} - virtual void visitString(V4IR::String *) {} - virtual void visitRegExp(V4IR::RegExp *) {} - virtual void visitName(V4IR::Name *) {} - virtual void visitClosure(V4IR::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 *) {} - 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 *) {} - - 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 visitTemp(V4IR::Temp *e) { - if (e->scope) - return; - - const int replacement = tempReplacement.value(e->index, -1); - if (replacement != -1) { -// qDebug() << "+++ Replacing" << e->index << "with" << replacement; - e->index = replacement; - } - } - - virtual void visitMove(V4IR::Move *s) { - V4IR::Temp *targetTemp = s->target->asTemp(); - if (targetTemp && targetTemp->index >= localCount && !targetTemp->scope) { - if (s->op == V4IR::OpInvalid) { - if (V4IR::Name *n = s->source->asName()) { - if (thisTemp != -1) { - if (*n->id == QStringLiteral("this")) { - check(targetTemp->index, Value(Value::ThisType)); - return; - } - } - } else if (V4IR::Const *c = s->source->asConst()) { - Value value; - switch (c->type) { - case V4IR::UndefinedType: value.type = Value::UndefinedType; break; - case V4IR::NullType: value.type = Value::NullType; break; - case V4IR::BoolType: value.type = Value::BoolType; value.numberValue = c->value == 0 ? 0 : 1; break; - case V4IR::NumberType: value.type = Value::NumberType; value.numberValue = c->value; break; - default: Q_ASSERT("unknown const type"); return; - } - check(targetTemp->index, value); - return; - } else if (V4IR::String *str = s->source->asString()) { - check(targetTemp->index, Value(str)); - return; - } - } - invalidate(targetTemp->index, Value()); - } else { - s->target->accept(this); - } - - s->source->accept(this); - } - - void invalidate(int &targetTempIndex, const Value &value) - { - QMap<int, Value>::iterator it = valueForTemp.find(targetTempIndex); - if (it != valueForTemp.end()) { - if (it.value() == value) - return; - tempForValue.remove(it.value()); - valueForTemp.erase(it); - } - - QMap<int, int>::iterator it2 = tempReplacement.find(targetTempIndex); - if (it2 != tempReplacement.end()) { - tempReplacement.erase(it2); - } - } - - void check(int &targetTempIndex, const Value &value) - { - Q_ASSERT(value.isValid()); - - invalidate(targetTempIndex, value); - - int replacementTemp = tempForValue.value(value, -1); - if (replacementTemp == -1) { -// qDebug() << "+++ inserting temp" << targetTempIndex; - tempForValue.insert(value, targetTempIndex); - valueForTemp.insert(targetTempIndex, value); - } else { -// qDebug() << "+++ temp" << targetTempIndex << "can be replaced with" << replacementTemp; - tempReplacement.insert(targetTempIndex, replacementTemp); - } - } - - void reset() - { - tempForValue.clear(); - tempReplacement.clear(); - if (thisTemp != -1) - tempForValue.insert(Value(Value::ThisType), thisTemp); - } - -private: - QMap<Value, int> tempForValue; - QMap<int, Value> valueForTemp; - QMap<int, int> tempReplacement; - - int localCount; - int thisTemp; -}; - -//#define DEBUG_TEMP_COMPRESSION -#ifdef DEBUG_TEMP_COMPRESSION -# define DBTC(x) x -#else // !DEBUG_TEMP_COMPRESSION -# define DBTC(x) -#endif // DEBUG_TEMP_COMPRESSION -class CompressTemps: public V4IR::StmtVisitor, V4IR::ExprVisitor -{ -public: - void run(V4IR::Function *function) - { - _nextFree = 0; - _active.reserve(function->tempCount); - _localCount = function->locals.size(); - - DBTC(qDebug() << "starting on function" << (*function->name) << "with" << (function->tempCount - _localCount) << "temps.";) - - QVector<int> pinned; - foreach (V4IR::BasicBlock *block, function->basicBlocks) { - if (V4IR::Stmt *last = block->terminator()) { - const QBitArray &liveOut = last->d->liveOut; - for (int i = _localCount, ei = liveOut.size(); i < ei; ++i) { - if (liveOut.at(i) && !pinned.contains(i)) { - pinned.append(i); - DBTC(qDebug() << "Pinning:";) - add(i - _localCount, _nextFree); - } - } - } - } - _pinnedCount = _nextFree; - - int maxUsed = _nextFree; - - foreach (V4IR::BasicBlock *block, function->basicBlocks) { - DBTC(qDebug("L%d:", block->index)); - - for (int i = 0, ei = block->statements.size(); i < ei; ++i ) { - _currentStatement = block->statements[i]; - if (i == 0) - expireOld(); - - DBTC(_currentStatement->dump(qout);qout<<endl<<flush;) - - if (_currentStatement->d) - _currentStatement->accept(this); - } - maxUsed = std::max(maxUsed, _nextFree); - } - DBTC(qDebug() << "function" << (*function->name) << "uses" << maxUsed << "temps.";) - function->tempCount = maxUsed + _localCount; - } - -protected: - virtual void visitConst(V4IR::Const *) {} - virtual void visitString(V4IR::String *) {} - virtual void visitRegExp(V4IR::RegExp *) {} - virtual void visitName(V4IR::Name *) {} - virtual void visitClosure(V4IR::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 *) {} - 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 *t) { visitTemp(t->exceptionVar); } - - virtual void visitTemp(V4IR::Temp *e) { - if (e->scope) // scoped local - return; - if (e->index < _localCount) // local or argument - return; - - e->index = remap(e->index - _localCount) + _localCount; - } - - 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->target->accept(this); - s->source->accept(this); - } - -private: - int remap(int tempIndex) { - for (ActiveTemps::const_iterator i = _active.begin(), ei = _active.end(); i < ei; ++i) { - if (i->first == tempIndex) { - DBTC(qDebug() << " lookup" << (tempIndex + _localCount) << "->" << (i->second + _localCount);) - return i->second; - } - } - - int firstFree = expireOld(); - add(tempIndex, firstFree); - return firstFree; - } - - void add(int tempIndex, int firstFree) { - if (_nextFree <= firstFree) - _nextFree = firstFree + 1; - _active.prepend(qMakePair(tempIndex, firstFree)); - DBTC(qDebug() << " add" << (tempIndex + _localCount) << "->" << (firstFree+ _localCount);) - } - - int expireOld() { - Q_ASSERT(_currentStatement->d); - - const QBitArray &liveIn = _currentStatement->d->liveIn; - QBitArray inUse(_nextFree); - int i = 0; - while (i < _active.size()) { - const QPair<int, int> &p = _active[i]; - - if (p.second < _pinnedCount) { - inUse.setBit(p.second); - ++i; - continue; - } - - if (liveIn[p.first + _localCount]) { - inUse[p.second] = true; - ++i; - } else { - DBTC(qDebug() << " remove" << (p.first + _localCount) << "->" << (p.second + _localCount);) - _active.remove(i); - } - } - for (int i = 0, ei = inUse.size(); i < ei; ++i) - if (!inUse[i]) - return i; - return _nextFree; - } - -private: - typedef QVector<QPair<int, int> > ActiveTemps; - ActiveTemps _active; - V4IR::Stmt *_currentStatement; - int _localCount; - int _nextFree; - int _pinnedCount; -}; -#undef DBTC - -} // end of anonymous namespace - class Codegen::ScanFunctions: Visitor { typedef QV4::TemporaryAssignment<bool> TemporaryBoolAssignment; @@ -1199,6 +628,9 @@ V4IR::Expr *Codegen::reference(V4IR::Expr *expr) V4IR::Expr *Codegen::unop(V4IR::AluOp op, V4IR::Expr *expr) { + Q_ASSERT(op != V4IR::OpIncrement); + Q_ASSERT(op != V4IR::OpDecrement); + if (V4IR::Const *c = expr->asConst()) { if (c->type == V4IR::NumberType) { switch (op) { @@ -1308,6 +740,12 @@ void Codegen::move(V4IR::Expr *target, V4IR::Expr *source, V4IR::AluOp op) { assert(target->isLValue()); + // TODO: verify the rest of the function for when op == OpInvalid + if (op != V4IR::OpInvalid) { + move(target, binop(op, target, source), V4IR::OpInvalid); + return; + } + if (!source->asTemp() && !source->asConst() && (op != V4IR::OpInvalid || ! target->asTemp())) { unsigned t = _block->newTemp(); _block->MOVE(_block->TEMP(t), source); @@ -2242,7 +1680,7 @@ bool Codegen::visit(PostDecrementExpression *ast) throwSyntaxErrorOnEvalOrArgumentsInStrictMode(*expr, ast->decrementToken); if (_expr.accept(nx)) { - move(*expr, unop(V4IR::OpDecrement, *expr)); + move(*expr, binop(V4IR::OpSub, *expr, _block->CONST(V4IR::NumberType, 1))); } else { V4IR::ExprList *args = _function->New<V4IR::ExprList>(); args->init(*expr); @@ -2259,7 +1697,7 @@ bool Codegen::visit(PostIncrementExpression *ast) throwSyntaxErrorOnEvalOrArgumentsInStrictMode(*expr, ast->incrementToken); if (_expr.accept(nx)) { - move(*expr, unop(V4IR::OpIncrement, *expr)); + move(*expr, binop(V4IR::OpAdd, unop(V4IR::OpUPlus, *expr), _block->CONST(V4IR::NumberType, 1))); } else { V4IR::ExprList *args = _function->New<V4IR::ExprList>(); args->init(*expr); @@ -2272,7 +1710,7 @@ bool Codegen::visit(PreDecrementExpression *ast) { Result expr = expression(ast->expression); throwSyntaxErrorOnEvalOrArgumentsInStrictMode(*expr, ast->decrementToken); - move(*expr, unop(V4IR::OpDecrement, *expr)); + move(*expr, binop(V4IR::OpSub, *expr, _block->CONST(V4IR::NumberType, 1))); if (_expr.accept(nx)) { // nothing to do } else { @@ -2285,7 +1723,7 @@ bool Codegen::visit(PreIncrementExpression *ast) { Result expr = expression(ast->expression); throwSyntaxErrorOnEvalOrArgumentsInStrictMode(*expr, ast->incrementToken); - move(*expr, unop(V4IR::OpIncrement, *expr)); + move(*expr, binop(V4IR::OpAdd, unop(V4IR::OpUPlus, *expr), _block->CONST(V4IR::NumberType, 1))); if (_expr.accept(nx)) { // nothing to do } else { @@ -2371,212 +1809,6 @@ bool Codegen::visit(FunctionDeclaration * /*ast*/) return false; } -void Codegen::linearize(V4IR::Function *function) -{ - V4IR::BasicBlock *exitBlock = function->basicBlocks.last(); - assert(exitBlock->isTerminated()); - assert(exitBlock->terminator()->asRet()); - - QSet<V4IR::BasicBlock *> V; - V.insert(exitBlock); - - QVector<V4IR::BasicBlock *> trace; - - for (int i = 0; i < function->basicBlocks.size(); ++i) { - V4IR::BasicBlock *block = function->basicBlocks.at(i); - if (!block->isTerminated() && (i + 1) < function->basicBlocks.size()) { - V4IR::BasicBlock *next = function->basicBlocks.at(i + 1); - block->JUMP(next); - } - } - - struct I { static void trace(V4IR::BasicBlock *block, QSet<V4IR::BasicBlock *> *V, - QVector<V4IR::BasicBlock *> *output) { - if (block == 0 || V->contains(block)) - return; - - V->insert(block); - block->index = output->size(); - output->append(block); - - if (V4IR::Stmt *term = block->terminator()) { - if (V4IR::Jump *j = term->asJump()) { - trace(j->target, V, output); - } else if (V4IR::CJump *cj = term->asCJump()) { - if (! V->contains(cj->iffalse)) - trace(cj->iffalse, V, output); - else - trace(cj->iftrue, V, output); - } else if (V4IR::Try *t = term->asTry()) { - trace(t->tryBlock, V, output); - trace(t->catchBlock, V, output); - } - } - - // We could do this for each type above, but it is safer to have a - // "catchall" here - for (int ii = 0; ii < block->out.count(); ++ii) - trace(block->out.at(ii), V, output); - } - }; - - I::trace(function->basicBlocks.first(), &V, &trace); - - V.insert(exitBlock); - exitBlock->index = trace.size(); - trace.append(exitBlock); - - QVarLengthArray<V4IR::BasicBlock*> blocksToDelete; - foreach (V4IR::BasicBlock *b, function->basicBlocks) { - if (!V.contains(b)) { - foreach (V4IR::BasicBlock *out, b->out) { - int idx = out->in.indexOf(b); - if (idx >= 0) - out->in.remove(idx); - } - blocksToDelete.append(b); - } - } - foreach (V4IR::BasicBlock *b, blocksToDelete) - foreach (V4IR::Stmt *s, b->statements) - s->destroyData(); - qDeleteAll(blocksToDelete); - function->basicBlocks = trace; - - function->removeSharedExpressions(); - - if (qgetenv("NO_OPT").isEmpty()) - ConstantPropagation().run(function); - -#ifndef QV4_NO_LIVENESS - liveness(function); -#endif - - if (qgetenv("NO_OPT").isEmpty()) { - removeDeadAssignments(function); - removeUnreachableBlocks(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) { - 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; - 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 << " goto L" << s->asCJump()->iffalse << ";" << endl; - } - } - - qout << "}" << endl - << endl; - } - - //### NOTE: after this pass, the liveness information is not correct anymore! - if (qgetenv("NO_OPT").isEmpty()) - CompressTemps().run(function); -} - V4IR::Function *Codegen::defineFunction(const QString &name, AST::Node *ast, AST::FormalParameterList *formals, AST::SourceElements *body, Mode mode, diff --git a/src/qml/qml/v4/qv4codegen_p.h b/src/qml/qml/v4/qv4codegen_p.h index a4d20e32e0..225784b7fe 100644 --- a/src/qml/qml/v4/qv4codegen_p.h +++ b/src/qml/qml/v4/qv4codegen_p.h @@ -280,7 +280,6 @@ protected: void move(V4IR::Expr *target, V4IR::Expr *source, V4IR::AluOp op = V4IR::OpInvalid); void cjump(V4IR::Expr *cond, V4IR::BasicBlock *iftrue, V4IR::BasicBlock *iffalse); - void linearize(V4IR::Function *function); V4IR::Function *defineFunction(const QString &name, AST::Node *ast, AST::FormalParameterList *formals, AST::SourceElements *body, diff --git a/src/qml/qml/v4/qv4isel_llvm.cpp b/src/qml/qml/v4/qv4isel_llvm.cpp index 5f06700e06..96b023e76d 100644 --- a/src/qml/qml/v4/qv4isel_llvm.cpp +++ b/src/qml/qml/v4/qv4isel_llvm.cpp @@ -684,7 +684,7 @@ void InstructionSelection::unop(V4IR::AluOp oper, V4IR::Temp *sourceTemp, V4IR:: } } -void InstructionSelection::binop(V4IR::AluOp oper, V4IR::Temp *leftSource, V4IR::Temp *rightSource, V4IR::Temp *target) +void InstructionSelection::binop(V4IR::AluOp oper, V4IR::Expr *leftSource, V4IR::Expr *rightSource, V4IR::Temp *target) { const char *opName = 0; switch (oper) { diff --git a/src/qml/qml/v4/qv4isel_llvm_p.h b/src/qml/qml/v4/qv4isel_llvm_p.h index aeccde067c..8ccdd43020 100644 --- a/src/qml/qml/v4/qv4isel_llvm_p.h +++ b/src/qml/qml/v4/qv4isel_llvm_p.h @@ -118,7 +118,7 @@ public: // methods from InstructionSelection: virtual void setElement(V4IR::Temp *source, V4IR::Temp *targetBase, V4IR::Temp *targetIndex); virtual void copyValue(V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp); virtual void unop(V4IR::AluOp oper, V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp); - virtual void binop(V4IR::AluOp oper, V4IR::Temp *leftSource, V4IR::Temp *rightSource, V4IR::Temp *target); + virtual void binop(V4IR::AluOp oper, V4IR::Expr *leftSource, V4IR::Expr *rightSource, V4IR::Temp *target); virtual void inplaceNameOp(V4IR::AluOp oper, V4IR::Temp *rightSource, const QString &targetName); virtual void inplaceElementOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBaseTemp, V4IR::Temp *targetIndexTemp); virtual void inplaceMemberOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBase, const QString &targetName); diff --git a/src/qml/qml/v4/qv4isel_masm.cpp b/src/qml/qml/v4/qv4isel_masm.cpp index f104b6e6fb..7a5467fac5 100644 --- a/src/qml/qml/v4/qv4isel_masm.cpp +++ b/src/qml/qml/v4/qv4isel_masm.cpp @@ -107,18 +107,19 @@ const int Assembler::calleeSavedRegisterCount = sizeof(calleeSavedRegisters) / s const Assembler::VoidType Assembler::Void; Assembler::Assembler(V4IR::Function* function, QV4::Function *vmFunction, QV4::ExecutionEngine *engine) - : _function(function), _vmFunction(vmFunction), _engine(engine) + : _function(function), _vmFunction(vmFunction), _engine(engine), _nextBlock(0) { } -void Assembler::registerBlock(V4IR::BasicBlock* block) +void Assembler::registerBlock(V4IR::BasicBlock* block, V4IR::BasicBlock *nextBlock) { _addrs[block] = label(); + _nextBlock = nextBlock; } void Assembler::jumpToBlock(V4IR::BasicBlock* current, V4IR::BasicBlock *target) { - if (current->index + 1 != target->index) + if (target != _nextBlock) _patches[target].append(jump()); } @@ -575,7 +576,8 @@ void InstructionSelection::run(QV4::Function *vmFunction, V4IR::Function *functi int locals = (_function->tempCount - _function->locals.size() + _function->maxNumberOfArguments) + 1; locals = (locals + 1) & ~1; - _as->enterStandardStackFrame(locals); + qSwap(_locals, locals); + _as->enterStandardStackFrame(_locals); int contextPointer = 0; #if !defined(RETURN_VALUE_IN_REGISTER) @@ -591,9 +593,10 @@ void InstructionSelection::run(QV4::Function *vmFunction, V4IR::Function *functi _as->loadPtr(addressForArgument(contextPointer), Assembler::ContextRegister); #endif - foreach (V4IR::BasicBlock *block, _function->basicBlocks) { - _block = block; - _as->registerBlock(_block); + for (int i = 0, ei = _function->basicBlocks.size(); i != ei; ++i) { + V4IR::BasicBlock *nextBlock = (i < ei - 1) ? _function->basicBlocks[i + 1] : 0; + _block = _function->basicBlocks[i]; + _as->registerBlock(_block, nextBlock); if (_reentryBlocks.contains(_block)) { _as->enterStandardStackFrame(/*locals*/0); @@ -606,24 +609,13 @@ void InstructionSelection::run(QV4::Function *vmFunction, V4IR::Function *functi #endif } - foreach (V4IR::Stmt *s, block->statements) { + foreach (V4IR::Stmt *s, _block->statements) { if (s->location.isValid()) _as->recordLineNumber(s->location.startLine); s->accept(this); } } - _as->leaveStandardStackFrame(locals); -#if !defined(RETURN_VALUE_IN_REGISTER) - // Emulate ret(n) instruction - // Pop off return address into scratch register ... - _as->pop(Assembler::ScratchRegister); - // ... and overwrite the invisible argument with - // the return address. - _as->poke(Assembler::ScratchRegister); -#endif - _as->ret(); - _as->link(_vmFunction); if (_lookups.size()) { @@ -637,6 +629,7 @@ void InstructionSelection::run(QV4::Function *vmFunction, V4IR::Function *functi qSwap(_function, function); qSwap(_lookups, lookups); qSwap(_reentryBlocks, reentryBlocks); + qSwap(_locals, locals); delete _as; _as = oldAssembler; } @@ -1019,9 +1012,10 @@ void InstructionSelection::unop(V4IR::AluOp oper, V4IR::Temp *sourceTemp, V4IR:: Assembler::Reference(sourceTemp)); } -void InstructionSelection::binop(V4IR::AluOp oper, V4IR::Temp *leftSource, V4IR::Temp *rightSource, V4IR::Temp *target) +void InstructionSelection::binop(V4IR::AluOp oper, V4IR::Expr *leftSource, V4IR::Expr *rightSource, V4IR::Temp *target) { - _as->generateBinOp(oper, target, leftSource, rightSource); + Q_ASSERT(leftSource->asTemp() && rightSource->asTemp()); + _as->generateBinOp(oper, target, leftSource->asTemp(), rightSource->asTemp()); } void InstructionSelection::inplaceNameOp(V4IR::AluOp oper, V4IR::Temp *rightSource, const QString &targetName) @@ -1267,10 +1261,24 @@ void InstructionSelection::visitRet(V4IR::Ret *s) _as->loadPtr(addressForArgument(0), Assembler::ReturnValueRegister); _as->copyValue(Address(Assembler::ReturnValueRegister, 0), t); #endif - return; + } else if (V4IR::Const *c = s->expr->asConst()) { + _as->copyValue(Assembler::ReturnValueRegister, c); + } else { + Q_UNIMPLEMENTED(); + Q_UNREACHABLE(); + Q_UNUSED(s); } - Q_UNIMPLEMENTED(); - Q_UNUSED(s); + + _as->leaveStandardStackFrame(_locals); +#if !defined(RETURN_VALUE_IN_REGISTER) + // Emulate ret(n) instruction + // Pop off return address into scratch register ... + _as->pop(Assembler::ScratchRegister); + // ... and overwrite the invisible argument with + // the return address. + _as->poke(Assembler::ScratchRegister); +#endif + _as->ret(); } int InstructionSelection::prepareVariableArguments(V4IR::ExprList* args) diff --git a/src/qml/qml/v4/qv4isel_masm_p.h b/src/qml/qml/v4/qv4isel_masm_p.h index 9a55ede441..8f4732336f 100644 --- a/src/qml/qml/v4/qv4isel_masm_p.h +++ b/src/qml/qml/v4/qv4isel_masm_p.h @@ -250,7 +250,7 @@ public: call(addr); } - void registerBlock(V4IR::BasicBlock*); + void registerBlock(V4IR::BasicBlock*, V4IR::BasicBlock *nextBlock); void jumpToBlock(V4IR::BasicBlock* current, V4IR::BasicBlock *target); void addPatch(V4IR::BasicBlock* targetBlock, Jump targetJump); void addPatch(DataLabelPtr patch, Label target); @@ -741,6 +741,7 @@ private: QList<DataLabelPatch> _dataLabelPatches; QHash<V4IR::BasicBlock *, QVector<DataLabelPtr> > _labelPatches; + V4IR::BasicBlock *_nextBlock; QV4::ExecutionEngine *_engine; @@ -807,7 +808,7 @@ protected: virtual void setElement(V4IR::Temp *source, V4IR::Temp *targetBase, V4IR::Temp *targetIndex); virtual void copyValue(V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp); virtual void unop(V4IR::AluOp oper, V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp); - virtual void binop(V4IR::AluOp oper, V4IR::Temp *leftSource, V4IR::Temp *rightSource, V4IR::Temp *target); + virtual void binop(V4IR::AluOp oper, V4IR::Expr *leftSource, V4IR::Expr *rightSource, V4IR::Temp *target); virtual void inplaceNameOp(V4IR::AluOp oper, V4IR::Temp *rightSource, const QString &targetName); virtual void inplaceElementOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBaseTemp, V4IR::Temp *targetIndexTemp); virtual void inplaceMemberOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBase, const QString &targetName); @@ -892,6 +893,7 @@ private: QVector<QV4::Lookup> _lookups; Assembler* _as; QSet<V4IR::BasicBlock*> _reentryBlocks; + int _locals; }; class Q_QML_EXPORT ISelFactory: public EvalISelFactory diff --git a/src/qml/qml/v4/qv4isel_p.cpp b/src/qml/qml/v4/qv4isel_p.cpp index 70713aa18f..48678d8f81 100644 --- a/src/qml/qml/v4/qv4isel_p.cpp +++ b/src/qml/qml/v4/qv4isel_p.cpp @@ -130,19 +130,20 @@ void InstructionSelection::visitMove(V4IR::Move *s) return; } } else if (V4IR::Binop *b = s->source->asBinop()) { - if (b->left->asTemp() && b->right->asTemp()) { - binop(b->op, b->left->asTemp(), b->right->asTemp(), t); - return; - } + binop(b->op, b->left, b->right, t); + return; } else if (V4IR::Call *c = s->source->asCall()) { if (c->base->asName()) { callBuiltin(c, t); return; } else if (Member *member = c->base->asMember()) { - callProperty(member->base, *member->name, c->args, t); + Q_ASSERT(member->base->asTemp()); + callProperty(member->base->asTemp(), *member->name, c->args, t); return; } else if (Subscript *s = c->base->asSubscript()) { - callSubscript(s->base, s->index, c->args, t); + Q_ASSERT(s->base->asTemp()); + Q_ASSERT(s->index->asTemp()); + callSubscript(s->base->asTemp(), s->index->asTemp(), c->args, t); return; } else if (V4IR::Temp *value = c->base->asTemp()) { callValue(value, c->args, t); @@ -218,9 +219,12 @@ void InstructionSelection::visitExp(V4IR::Exp *s) } else if (Temp *value = c->base->asTemp()) { callValue(value, c->args, 0); } else if (Member *member = c->base->asMember()) { - callProperty(member->base, *member->name, c->args, 0); + Q_ASSERT(member->base->asTemp()); + callProperty(member->base->asTemp(), *member->name, c->args, 0); } else if (Subscript *s = c->base->asSubscript()) { - callSubscript(s->base, s->index, c->args, 0); + Q_ASSERT(s->base->asTemp()); + Q_ASSERT(s->index->asTemp()); + callSubscript(s->base->asTemp(), s->index->asTemp(), c->args, 0); } else { Q_UNIMPLEMENTED(); } diff --git a/src/qml/qml/v4/qv4isel_p.h b/src/qml/qml/v4/qv4isel_p.h index 6739ff1d45..be30e0625c 100644 --- a/src/qml/qml/v4/qv4isel_p.h +++ b/src/qml/qml/v4/qv4isel_p.h @@ -91,6 +91,8 @@ class Q_QML_EXPORT InstructionSelection: protected V4IR::StmtVisitor public: virtual ~InstructionSelection() = 0; + virtual void visitPhi(V4IR::Phi *) { Q_UNIMPLEMENTED(); abort(); } + public: // visitor methods for StmtVisitor: virtual void visitMove(V4IR::Move *s); virtual void visitEnter(V4IR::Enter *); @@ -145,7 +147,7 @@ public: // to implement by subclasses: virtual void setElement(V4IR::Temp *source, V4IR::Temp *targetBase, V4IR::Temp *targetIndex) = 0; virtual void copyValue(V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp) = 0; virtual void unop(V4IR::AluOp oper, V4IR::Temp *sourceTemp, V4IR::Temp *targetTemp) = 0; - virtual void binop(V4IR::AluOp oper, V4IR::Temp *leftSource, V4IR::Temp *rightSource, V4IR::Temp *target) = 0; + virtual void binop(V4IR::AluOp oper, V4IR::Expr *leftSource, V4IR::Expr *rightSource, V4IR::Temp *target) = 0; virtual void inplaceNameOp(V4IR::AluOp oper, V4IR::Temp *rightSource, const QString &targetName) = 0; virtual void inplaceElementOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBaseTemp, V4IR::Temp *targetIndexTemp) = 0; virtual void inplaceMemberOp(V4IR::AluOp oper, V4IR::Temp *source, V4IR::Temp *targetBase, const QString &targetName) = 0; diff --git a/src/qml/qml/v4/qv4isel_util_p.h b/src/qml/qml/v4/qv4isel_util_p.h index a696f051e4..942a94ccfc 100644 --- a/src/qml/qml/v4/qv4isel_util_p.h +++ b/src/qml/qml/v4/qv4isel_util_p.h @@ -58,6 +58,12 @@ inline QV4::Value convertToValue(V4IR::Const *c) return QV4::Value::undefinedValue(); case V4IR::BoolType: return QV4::Value::fromBoolean(c->value != 0); + case V4IR::SInt32Type: + return QV4::Value::fromInt32(int(c->value)); + case V4IR::UInt32Type: + return QV4::Value::fromUInt32(unsigned(c->value)); + case V4IR::DoubleType: + return QV4::Value::fromDouble(c->value); case V4IR::NumberType: { int ival = (int)c->value; // +0 != -0, so we need to convert to double when negating 0 diff --git a/src/qml/qml/v4/qv4jsir.cpp b/src/qml/qml/v4/qv4jsir.cpp index 9f62b9451f..a7d6a3ca40 100644 --- a/src/qml/qml/v4/qv4jsir.cpp +++ b/src/qml/qml/v4/qv4jsir.cpp @@ -53,14 +53,21 @@ QT_BEGIN_NAMESPACE namespace QQmlJS { namespace V4IR { -const char *typeName(Type t) +QString typeName(Type t) { switch (t) { - case UndefinedType: return "undefined"; - case NullType: return "null"; - case BoolType: return "bool"; - case NumberType: return "number"; - default: return "invalid"; + case UnknownType: return QStringLiteral(""); + case MissingType: return QStringLiteral("missing"); + case UndefinedType: return QStringLiteral("undefined"); + case NullType: return QStringLiteral("null"); + case BoolType: return QStringLiteral("bool"); + case UInt32Type: return QStringLiteral("uint32"); + case SInt32Type: return QStringLiteral("int32"); + case DoubleType: return QStringLiteral("double"); + case NumberType: return QStringLiteral("number"); + case StringType: return QStringLiteral("string"); + case ObjectType: return QStringLiteral("object"); + default: return QStringLiteral("multiple"); } } @@ -221,6 +228,8 @@ struct RemoveSharedExpressions: V4IR::StmtVisitor, V4IR::ExprVisitor // nothing to do for Try statements } + virtual void visitPhi(V4IR::Phi *) { Q_UNIMPLEMENTED(); abort(); } + // expressions virtual void visitConst(Const *) {} virtual void visitString(String *) {} @@ -266,8 +275,25 @@ struct RemoveSharedExpressions: V4IR::StmtVisitor, V4IR::ExprVisitor } }; +static QString dumpStart(Expr *e) { + if (e->type == UnknownType) +// return QStringLiteral("**UNKNOWN**"); + return QString(); + else + return typeName(e->type) + QStringLiteral("{"); +} + +static const char *dumpEnd(Expr *e) { + if (e->type == UnknownType) + return ""; + else + return "}"; +} + void Const::dump(QTextStream &out) { + if (type != UndefinedType && type != NullType) + out << dumpStart(this); switch (type) { case QQmlJS::V4IR::UndefinedType: out << "undefined"; @@ -285,6 +311,8 @@ void Const::dump(QTextStream &out) out << QString::number(value, 'g', 16); break; } + if (type != UndefinedType && type != NullType) + out << dumpEnd(this); } void String::dump(QTextStream &out) @@ -405,6 +433,7 @@ void Name::dump(QTextStream &out) void Temp::dump(QTextStream &out) { + out << dumpStart(this); if (index < 0) { out << '#' << -(index + 1); // negative and 1-based. } else { @@ -412,6 +441,7 @@ void Temp::dump(QTextStream &out) } if (scope) out << "@" << scope; + out << dumpEnd(this); } void Closure::dump(QTextStream &out) @@ -424,15 +454,18 @@ void Closure::dump(QTextStream &out) void Unop::dump(QTextStream &out) { - out << opname(op); + out << dumpStart(this) << opname(op); expr->dump(out); + out << dumpEnd(this); } void Binop::dump(QTextStream &out) { + out << dumpStart(this); left->dump(out); out << ' ' << opname(op) << ' '; right->dump(out); + out << dumpEnd(this); } void Call::dump(QTextStream &out) @@ -543,6 +576,19 @@ void Try::dump(QTextStream &out, Stmt::Mode mode) out << " with the name " << exceptionVarName << " and go to L" << catchBlock->index << ';'; } +void Phi::dump(QTextStream &out, Stmt::Mode mode) +{ + targetTemp->dump(out); + out << " = phi("; + for (int i = 0, ei = incoming.size(); i < ei; ++i) { + if (i > 0) + out << ", "; + if (incoming[i]) + incoming[i]->dump(out); + } + out << ");"; +} + Function *Module::newFunction(const QString &name, Function *outer) { Function *f = new Function(this, outer, name); @@ -632,6 +678,14 @@ Temp *BasicBlock::TEMP(int index, uint scope) Expr *BasicBlock::CONST(Type type, double value) { Const *e = function->New<Const>(); + if (type == NumberType) { + int ival = (int)value; + // +0 != -0, so we need to convert to double when negating 0 + if (ival == value && !(value == 0 && isNegative(value))) + type = SInt32Type; + else + type = DoubleType; + } e->init(type, value); return e; } @@ -679,7 +733,7 @@ Closure *BasicBlock::CLOSURE(Function *function) return clos; } -Expr *BasicBlock::UNOP(AluOp op, Temp *expr) +Expr *BasicBlock::UNOP(AluOp op, Expr *expr) { Unop *e = function->New<Unop>(); e->init(op, expr); @@ -711,14 +765,14 @@ Expr *BasicBlock::NEW(Expr *base, ExprList *args) return e; } -Expr *BasicBlock::SUBSCRIPT(Temp *base, Temp *index) +Expr *BasicBlock::SUBSCRIPT(Expr *base, Expr *index) { Subscript *e = function->New<Subscript>(); e->init(base, index); return e; } -Expr *BasicBlock::MEMBER(Temp *base, const QString *name) +Expr *BasicBlock::MEMBER(Expr *base, const QString *name) { Member*e = function->New<Member>(); e->init(base, name); diff --git a/src/qml/qml/v4/qv4jsir_p.h b/src/qml/qml/v4/qv4jsir_p.h index 5755f8eb97..f2c0bdb459 100644 --- a/src/qml/qml/v4/qv4jsir_p.h +++ b/src/qml/qml/v4/qv4jsir_p.h @@ -119,6 +119,7 @@ struct Jump; struct CJump; struct Ret; struct Try; +struct Phi; enum AluOp { OpInvalid = 0, @@ -166,12 +167,22 @@ AluOp binaryOperator(int op); const char *opname(V4IR::AluOp op); enum Type { - MissingType, // Used to indicate holes in array initialization (e.g. [,,]) - UndefinedType, - NullType, - BoolType, - NumberType + UnknownType = 0, + + MissingType = 1 << 0, + UndefinedType = 1 << 1, + NullType = 1 << 2, + BoolType = 1 << 3, + + SInt32Type = 1 << 4, + UInt32Type = 1 << 5, + DoubleType = 1 << 6, + NumberType = SInt32Type | UInt32Type | DoubleType, + + StringType = 1 << 7, + ObjectType = 1 << 8 }; +QString typeName(Type t); struct ExprVisitor { virtual ~ExprVisitor() {} @@ -199,9 +210,13 @@ struct StmtVisitor { virtual void visitCJump(CJump *) = 0; virtual void visitRet(Ret *) = 0; virtual void visitTry(Try *) = 0; + virtual void visitPhi(Phi *) = 0; }; struct Expr { + Type type; + + Expr(): type(UnknownType) {} virtual ~Expr() {} virtual void accept(ExprVisitor *) = 0; virtual bool isLValue() { return false; } @@ -232,7 +247,6 @@ struct ExprList { }; struct Const: Expr { - Type type; double value; void init(Type type, double value) @@ -355,9 +369,9 @@ struct Closure: Expr { struct Unop: Expr { AluOp op; - Temp *expr; + Expr *expr; - void init(AluOp op, Temp *expr) + void init(AluOp op, Expr *expr) { this->op = op; this->expr = expr; @@ -432,10 +446,10 @@ struct New: Expr { }; struct Subscript: Expr { - Temp *base; - Temp *index; + Expr *base; + Expr *index; - void init(Temp *base, Temp *index) + void init(Expr *base, Expr *index) { this->base = base; this->index = index; @@ -449,10 +463,10 @@ struct Subscript: Expr { }; struct Member: Expr { - Temp *base; + Expr *base; const QString *name; - void init(Temp *base, const QString *name) + void init(Expr *base, const QString *name) { this->base = base; this->name = name; @@ -494,6 +508,7 @@ struct Stmt { virtual CJump *asCJump() { return 0; } virtual Ret *asRet() { return 0; } virtual Try *asTry() { return 0; } + virtual Phi *asPhi() { return 0; } virtual void dump(QTextStream &out, Mode mode = HIR) = 0; void destroyData() { @@ -594,9 +609,9 @@ struct CJump: Stmt { }; struct Ret: Stmt { - Temp *expr; + Expr *expr; - void init(Temp *expr) + void init(Expr *expr) { this->expr = expr; } @@ -631,6 +646,16 @@ struct Try: Stmt { virtual void dump(QTextStream &out, Mode mode); }; +struct Phi: Stmt { + Temp *targetTemp; + QVector<Expr *> incoming; + + virtual void accept(StmtVisitor *v) { v->visitPhi(this); } + virtual Phi *asPhi() { return this; } + + virtual void dump(QTextStream &out, Mode mode); +}; + struct Q_QML_EXPORT Module { MemoryPool pool; QVector<Function *> functions; @@ -705,6 +730,9 @@ struct Function { void removeSharedExpressions(); int indexOfArgument(const QStringRef &string) const; + + bool variablesCanEscape() const + { return hasDirectEval || !nestedFunctions.isEmpty(); } }; struct BasicBlock { @@ -754,12 +782,12 @@ struct BasicBlock { Closure *CLOSURE(Function *function); - Expr *UNOP(AluOp op, Temp *expr); + Expr *UNOP(AluOp op, Expr *expr); Expr *BINOP(AluOp op, Expr *left, Expr *right); Expr *CALL(Expr *base, ExprList *args = 0); Expr *NEW(Expr *base, ExprList *args = 0); - Expr *SUBSCRIPT(Temp *base, Temp *index); - Expr *MEMBER(Temp *base, const QString *name); + Expr *SUBSCRIPT(Expr *base, Expr *index); + Expr *MEMBER(Expr *base, const QString *name); Stmt *EXP(Expr *expr); Stmt *ENTER(Expr *expr); diff --git a/src/qml/qml/v4/qv4ssa.cpp b/src/qml/qml/v4/qv4ssa.cpp new file mode 100644 index 0000000000..696a8875e1 --- /dev/null +++ b/src/qml/qml/v4/qv4ssa.cpp @@ -0,0 +1,1691 @@ +/**************************************************************************** +** +** 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 + +using namespace QQmlJS; + +namespace { +QTextStream qout(stdout, QIODevice::WriteOnly); + +void showMeTheCode(V4IR::Function *function) +{ + // TODO: maybe we should move this somewhere else? + 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; + 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; + } +} + +using namespace V4IR; + +class DominatorTree { + int N = 0; + 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) { + 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]; + } +}; + +class VariableCollector: public StmtVisitor, ExprVisitor { + QHash<int, QSet<BasicBlock *> > _defsites; + QHash<BasicBlock *, QSet<int> > A_orig; + QSet<int> nonLocals; + QSet<int> killed; + + BasicBlock *currentBB; + int lastUncollectible; + +public: + VariableCollector(Function *function) + : lastUncollectible(function->variablesCanEscape() ? function->locals.size() - 1 : -1) + { +#ifdef SHOW_SSA + qout << "Variables collected:" << endl; +#endif // SHOW_SSA + + if (!function->variablesCanEscape() && false) { + BasicBlock *entryBlock = function->basicBlocks.at(0); + for (int i = -function->formals.size(); i < 0; ++i) { + _defsites[i].insert(entryBlock); + A_orig[entryBlock].insert(i); +#ifdef SHOW_SSA + qout << "\t#" << -i << " -> L0" << 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 (int nonLocal, nonLocals) + qout << "\t" << nonLocal << endl; + + qout << "end collected variables." << endl; +#endif // SHOW_SSA + } + + QList<int> vars() const { + return _defsites.keys(); + } + + QSet<BasicBlock *> defsite(int n) const { + return _defsites[n]; + } + + QSet<int> inBlock(BasicBlock *n) const { + return A_orig[n]; + } + + bool isNonLocal(int var) const { return nonLocals.contains(var); } + +protected: + virtual void visitPhi(Phi *) {}; + + 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 (t->scope == 0 && lastUncollectible < t->index) { +#ifdef SHOW_SSA + qout << '\t'; + t->dump(qout); + qout << " -> L" << currentBB->index << endl; +#endif // SHOW_SSA + + _defsites[t->index].insert(currentBB); + A_orig[currentBB].insert(t->index); + + // For semi-pruned SSA: + killed.insert(t->index); + } + } + } + + virtual void visitTemp(Temp *t) + { + if (t->scope == 0 && lastUncollectible < t->index) + if (!killed.contains(t->index)) + nonLocals.insert(t->index); + } +}; + +void insertPhiNode(int a, BasicBlock *y, Function *f) { +#ifdef SHOW_SSA + qout << "-> inserted phi node for variable " << a << " in block " << y->index << endl; +#endif + + Phi *phiNode = f->New<Phi>(); + phiNode->targetTemp = f->New<Temp>(); + phiNode->targetTemp->init(a); + 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); + phiNode->incoming[i] = t; + } +} + +class VariableRenamer: public StmtVisitor, public ExprVisitor +{ + Function *function; + QHash<int, QStack<int> > stack; + QSet<BasicBlock *> seen; + + QHash<int, unsigned> defCounts; + QHash<int, int> tempMapping; + + int lastUncollectible; + + 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; + + int a = f->variablesCanEscape() ? f->locals.size() : a = 0; + lastUncollectible = a - 1; + + for (; a < f->tempCount; ++a) { + stack[a].push(a); + } + } + + QHash<int, int> 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 + + return tempMapping; + } + + 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<int, 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()) { + int &a = phi->incoming[j]->asTemp()->index; + int newTmp = stack[a].top(); +// qDebug()<<"I: replacing phi use"<<a<<"with"<<newTmp<<"in L"<<Y->index; + a = newTmp; + } else { + break; + } + } + } + + // [3]: + foreach (BasicBlock *X, n->out) + rename(X); + + // [4]: + for (QHash<int, 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 (e->scope == 0 && lastUncollectible < e->index) { +// qDebug()<<"I: replacing use of"<<e->index<<"with"<<stack[e->index].top(); + e->index = stack[e->index].top(); + } + } + + 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 (t->scope == 0 && lastUncollectible < t->index) { + int &a = t->index; + defCounts[a] = defCounts.value(a, 0) + 1; + const int newIdx = nextFreeTemp(); + stack[a].push(newIdx); + updateLocalMapping(a, newIdx); +// qDebug()<<"I: replacing def of"<<a<<"with"<<newIdx; + a = newIdx; + } + } + + void updateLocalMapping(int origIdx, int newIdx) { + if (origIdx < function->locals.size()) { + tempMapping[newIdx] = origIdx; + return; + } + + int next = tempMapping.value(newIdx, INT32_MIN); + if (next == INT32_MIN) + return; + tempMapping[newIdx] = origIdx; + } + + 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); + } +}; + +QHash<int, int> convertToSSA(Function *function) +{ +#ifdef SHOW_SSA + qout << "Converting function "; + if (function->name) + qout << *function->name; + else + qout << "<no name>"; + qout << " to SSA..." << endl; +#endif // SHOW_SSA + + QVector<BasicBlock *> &nodes = function->basicBlocks; + + // Calculate the dominator tree: + DominatorTree df(nodes); + + // Collect all applicable variables: + VariableCollector variables(function); + + // Place phi functions: + QHash<BasicBlock *, QSet<int> > A_phi; + foreach (int 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); + } + } + } + } + + // Rename variables: + return VariableRenamer(function).run(); +} + +class DefUsesCalculator: public StmtVisitor, public ExprVisitor { +public: + struct DefUse { + Stmt *defStmt; + BasicBlock *blockOfStatement; + QList<Stmt *> uses; + }; + +private: + int _lastUncollectible; + QHash<int, DefUse> _defUses; + QHash<Stmt *, QList<int> > _usesPerStatement; + + BasicBlock *_block; + Stmt *_stmt; + + void addUse(Temp *t) { + Q_ASSERT(t); + if (t->scope || t->index <= _lastUncollectible) + return; + + _defUses[t->index].uses.append(_stmt); + _usesPerStatement[_stmt].append(t->index); + } + + void addDef(Temp *t) { + if (t->scope || t->index <= _lastUncollectible) + return; + + Q_ASSERT(!_defUses.contains(t->index) || _defUses.value(t->index).defStmt == 0 || _defUses.value(t->index).defStmt == _stmt); + + DefUse &defUse = _defUses[t->index]; + defUse.defStmt = _stmt; + defUse.blockOfStatement = _block; + } + +public: + DefUsesCalculator(Function *function) { + if (function->variablesCanEscape()) + _lastUncollectible = function->locals.size() - 1; + else + _lastUncollectible = -1; + + foreach (BasicBlock *bb, function->basicBlocks) { + _block = bb; + foreach (Stmt *stmt, bb->statements) { + _stmt = stmt; + stmt->accept(this); + } + } + + QMutableHashIterator<int, DefUse> it(_defUses); + while (it.hasNext()) { + it.next(); + if (!it.value().defStmt) + it.remove(); + } + } + + QList<int> defs() const { + return _defUses.keys(); + } + + void removeDef(int var) { + _defUses.remove(var); + } + + void addUses(int variable, QList<Stmt *>newUses) + { _defUses[variable].uses.append(newUses); } + + int useCount(int variable) const + { return _defUses[variable].uses.size(); } + + Stmt *defStmt(int variable) const + { return _defUses[variable].defStmt; } + + BasicBlock *defStmtBlock(int variable) const + { return _defUses[variable].blockOfStatement; } + + void removeUse(Stmt *usingStmt, int var) + { _defUses[var].uses.removeAll(usingStmt); } + + QList<int> usedVars(Stmt *s) const + { return _usesPerStatement[s]; } + + QList<Stmt *> uses(int var) const + { return _defUses[var].uses; } + + void dump() const + { + foreach (int var, _defUses.keys()) { + const DefUse &du = _defUses[var]; + qout<<var<<" -> 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 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->index)) { + 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 (int 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) { + int targetVar = phi->targetTemp->index; + + BasicBlock *bb = defUses.defStmtBlock(targetVar); + int idx = bb->statements.indexOf(phi); + bb->statements.remove(idx); + + foreach (int usedVar, defUses.usedVars(phi)) + defUses.removeUse(phi, usedVar); + defUses.removeDef(targetVar); + } +} + +class DeadCodeElimination: public ExprVisitor { + int _lastUncollectible; + DefUsesCalculator &_defUses; + QVector<int> _worklist; + +public: + DeadCodeElimination(DefUsesCalculator &defUses, Function *function) + : _defUses(defUses) + { + _worklist = QVector<int>::fromList(_defUses.defs()); + + if (function->variablesCanEscape()) + _lastUncollectible = function->locals.size() - 1; + else + _lastUncollectible = -1; + } + + void run() { + while (!_worklist.isEmpty()) { + const int 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)) { +// qDebug()<<"-- defining stmt for"<<v<<"has no side effect"; + QVector<Stmt *> &stmts = _defUses.defStmtBlock(v)->statements; + int idx = stmts.indexOf(s); + if (idx != -1) + stmts.remove(idx); + foreach (int 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()) + if (t->index <= _lastUncollectible || t->scope) + return true; + move->source->accept(this); + } + 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 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 { + const DefUsesCalculator &_defUses; + QHash<int, 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; + int _localCount; + +public: + TypeInference(const DefUsesCalculator &defUses): _defUses(defUses), _ty(UnknownType) {} + + void run(Function *function) { + _localCount = function->variablesCanEscape() ? function->locals.size() : 0; + + // 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; + } + + 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 (t->scope || t->index < _localCount) { + e->type = ObjectType; + } else { + e->type = (Type) ty; + + if (_tempTypes[t->index] != ty) { + _tempTypes[t->index] = ty; + +#if defined(SHOW_SSA) + foreach (Stmt *s, _defUses.uses(t->index)) { + qout << "Pushing back dependent stmt: "; + s->dump(qout); + qout << endl; + } +#endif + + _worklist += QSet<Stmt *>::fromList(_defUses.uses(t->index)); + } + } + } 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 (e->scope) + _ty = TypingResult(ObjectType); + else if (e->index < _localCount) + _ty = TypingResult(ObjectType); + else + _ty = TypingResult(_tempTypes.value(e->index, UnknownType)); + setType(e, _ty.type); + } + virtual void visitClosure(Closure *) { _ty = TypingResult(ObjectType); } // TODO: VERIFY THIS! + 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); + } + +public: + TypePropagation() : _ty(UnknownType) {} + + void run(Function *f) { + foreach (BasicBlock *bb, f->basicBlocks) + foreach (Stmt *s, bb->statements) + s->accept(this); + } + +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 visitUnop(Unop *e) { run(e->expr, e->type); } + virtual void visitBinop(Binop *e) { run(e->left, e->type); run(e->right, e->type); } + 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) + run(e, ty); + } +}; + +void insertMove(Function *function, BasicBlock *basicBlock, Temp *target, Expr *source) { + 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); + 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(QVector<BasicBlock *> &basicBlocks) +{ + // FIXME: this should not do DFS scheduling. + struct I { + QSet<BasicBlock *> visited; + QVector<BasicBlock *> &sequence; + + I(QVector<BasicBlock *> &sequence): sequence(sequence) {} + + void DFS(BasicBlock *bb) { + if (visited.contains(bb)) + return; + visited.insert(bb); + sequence.append(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(); + } + } + }; + + QVector<BasicBlock *> sequence; + sequence.reserve(basicBlocks.size()); + I(sequence).DFS(basicBlocks.first()); + qSwap(basicBlocks, sequence); +} + +/* + * 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, const QHash<int, int> &tempMapping) { + // 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); + } + } + } + } +} + +} // end of anonymous namespace + + + +void QQmlJS::linearize(V4IR::Function *function) +{ +#if defined(SHOW_SSA) + qout << "##### NOW IN FUNCTION " << (function->name ? qPrintable(*function->name) : "anonymous!") << endl << flush; +#endif +#if 0 + V4IR::BasicBlock *exitBlock = function->basicBlocks.last(); + assert(exitBlock->isTerminated()); + assert(exitBlock->terminator()->asRet()); + + QSet<V4IR::BasicBlock *> V; + V.insert(exitBlock); + + QVector<V4IR::BasicBlock *> trace; + + for (int i = 0; i < function->basicBlocks.size(); ++i) { + V4IR::BasicBlock *block = function->basicBlocks.at(i); + if (!block->isTerminated() && (i + 1) < function->basicBlocks.size()) { + V4IR::BasicBlock *next = function->basicBlocks.at(i + 1); + block->JUMP(next); + } + } + + struct I { static void trace(V4IR::BasicBlock *block, QSet<V4IR::BasicBlock *> *V, + QVector<V4IR::BasicBlock *> *output) { + if (block == 0 || V->contains(block)) + return; + + V->insert(block); + block->index = output->size(); + output->append(block); + + if (V4IR::Stmt *term = block->terminator()) { + if (V4IR::Jump *j = term->asJump()) { + trace(j->target, V, output); + } else if (V4IR::CJump *cj = term->asCJump()) { + if (! V->contains(cj->iffalse)) + trace(cj->iffalse, V, output); + else + trace(cj->iftrue, V, output); + } else if (V4IR::Try *t = term->asTry()) { + trace(t->tryBlock, V, output); + trace(t->catchBlock, V, output); + } + } + + // We could do this for each type above, but it is safer to have a + // "catchall" here + for (int ii = 0; ii < block->out.count(); ++ii) + trace(block->out.at(ii), V, output); + } + }; + + I::trace(function->basicBlocks.first(), &V, &trace); + + V.insert(exitBlock); + exitBlock->index = trace.size(); + trace.append(exitBlock); + + QVarLengthArray<V4IR::BasicBlock*> blocksToDelete; + foreach (V4IR::BasicBlock *b, function->basicBlocks) { + if (!V.contains(b)) { + foreach (V4IR::BasicBlock *out, b->out) { + int idx = out->in.indexOf(b); + if (idx >= 0) + out->in.remove(idx); + } + blocksToDelete.append(b); + } + } + foreach (V4IR::BasicBlock *b, blocksToDelete) + foreach (V4IR::Stmt *s, b->statements) + s->destroyData(); + qDeleteAll(blocksToDelete); + function->basicBlocks = trace; +#else + { +// 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; + } + + // number all basic blocks: + for (int i = 0; i < function->basicBlocks.size(); ++i) + function->basicBlocks[i]->index = i; + } +#endif + function->removeSharedExpressions(); +// if (qgetenv("NO_OPT").isEmpty()) +// ConstantPropagation().run(function); + +//#ifndef QV4_NO_LIVENESS +// liveness(function); +//#endif + +// if (qgetenv("NO_OPT").isEmpty()) { +// removeDeadAssignments(function); +// removeUnreachableBlocks(function); +// } + +// showMeTheCode(function); +// splitEdges(function); +// showMeTheCode(function); + + showMeTheCode(function); + + if (!function->hasTry && !function->hasWith) { +// qout << "Starting edge splitting..." << endl; + doEdgeSplitting(function); +// showMeTheCode(function); + +// qout << "Starting def/uses calculation..." << endl; + QHash<int, int> tempMapping = convertToSSA(function); +// showMeTheCode(function); + + 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); +// scheduleBlocks(function->basicBlocks); +// showMeTheCode(function); + +// qout << "Converting out of SSA..." << endl; + convertOutOfSSA(function, tempMapping); + showMeTheCode(function); + +#ifndef QT_NO_DEBUG + checkCriticalEdges(function->basicBlocks); +#endif + +// qout << "Finished." << endl; + } + + // TODO: remove blocks that only have a JUMP statement, and re-wire their predecessor/successor. +} diff --git a/src/qml/qml/v4/qv4ssa_p.h b/src/qml/qml/v4/qv4ssa_p.h new file mode 100644 index 0000000000..6f688f3f99 --- /dev/null +++ b/src/qml/qml/v4/qv4ssa_p.h @@ -0,0 +1,53 @@ +/**************************************************************************** +** +** 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$ +** +****************************************************************************/ + +#ifndef QV4SSA_P_H +#define QV4SSA_P_H + +#include "qv4jsir_p.h" + +namespace QQmlJS { + +void linearize(V4IR::Function *function); + +} + +#endif // QV4SSA_P_H diff --git a/src/qml/qml/v4/v4.pri b/src/qml/qml/v4/v4.pri index b392960d88..a55f8593ee 100644 --- a/src/qml/qml/v4/v4.pri +++ b/src/qml/qml/v4/v4.pri @@ -12,6 +12,7 @@ INCLUDEPATH += $$OUT_PWD SOURCES += \ $$PWD/qv4codegen.cpp \ + $$PWD/qv4ssa.cpp \ $$PWD/qv4jsir.cpp \ $$PWD/qv4engine.cpp \ $$PWD/qv4context.cpp \ @@ -57,6 +58,7 @@ SOURCES += \ HEADERS += \ $$PWD/qv4global_p.h \ $$PWD/qv4codegen_p.h \ + $$PWD/qv4ssa_p.h \ $$PWD/qv4jsir_p.h \ $$PWD/qv4engine_p.h \ $$PWD/qv4context_p.h \ diff --git a/tests/manual/v4/fact.js b/tests/manual/v4/fact.js index c00717d698..56727d6fb1 100644 --- a/tests/manual/v4/fact.js +++ b/tests/manual/v4/fact.js @@ -1,4 +1,3 @@ - function fact1(n) { if (n > 0) return n * fact1(n - 1); @@ -10,6 +9,14 @@ function fact2(n) { return n > 0 ? n * fact2(n - 1) : 1 } -print("fact(12) = ", fact1(12)) -print("fact(12) = ", fact2(12)) +function fact3(n) { + var res = 1; + for (var i = 2; i <= n; i=i+1) + res = res * i; + return res; +} + +print("fact1(12) = ", fact1(12)) +print("fact2(12) = ", fact2(12)) +print("fact3(12) = ", fact3(12)) |