aboutsummaryrefslogtreecommitdiffstats
path: root/src/qml/compiler/qv4ssa.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/qml/compiler/qv4ssa.cpp')
-rw-r--r--src/qml/compiler/qv4ssa.cpp1147
1 files changed, 695 insertions, 452 deletions
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index fdda69e167..deba41ef9d 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -642,7 +642,7 @@ public:
qout << from;
else
qout << "(none)";
- qout << " -> " << to->index() << endl;
+ qout << " dominates " << to->index() << endl;
}
qDebug("%s", buf.data().constData());
}
@@ -740,6 +740,21 @@ public:
return order;
}
+ void mergeIntoPredecessor(BasicBlock *successor)
+ {
+ int succIdx = successor->index();
+ if (succIdx == InvalidBasicBlockIndex) {
+ return;
+ }
+
+ int succDom = idom[unsigned(succIdx)];
+ for (BasicBlockIndex &idx : idom) {
+ if (idx == succIdx) {
+ idx = succDom;
+ }
+ }
+ }
+
private:
bool dominates(BasicBlockIndex dominator, BasicBlockIndex dominated) const {
// dominator can be Invalid when the dominated block has no dominator (i.e. the start node)
@@ -898,7 +913,7 @@ private:
}
};
-class VariableCollector: public StmtVisitor, ExprVisitor {
+class VariableCollector {
std::vector<Temp> _allTemps;
std::vector<BasicBlockSet> _defsites;
std::vector<std::vector<int> > A_orig;
@@ -946,7 +961,7 @@ public:
currentBB = bb;
killed.assign(function->tempCount, false);
for (Stmt *s : bb->statements())
- s->accept(this);
+ visit(s);
}
}
@@ -971,62 +986,45 @@ public:
return nonLocals.at(var.index);
}
-protected:
- virtual void visitPhi(Phi *) {}
- virtual void visitConvert(Convert *e) { e->expr->accept(this); }
-
- virtual void visitConst(Const *) {}
- virtual void visitString(IR::String *) {}
- virtual void visitRegExp(IR::RegExp *) {}
- virtual void visitName(Name *) {}
- virtual void visitArgLocal(ArgLocal *) {}
- 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 visitExp(Exp *s) { s->expr->accept(this); }
- virtual void visitJump(Jump *) {}
- virtual void visitCJump(CJump *s) { s->cond->accept(this); }
- virtual void visitRet(Ret *s) { s->expr->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 visitMove(Move *s) {
- s->source->accept(this);
+private:
+ void visit(Stmt *s)
+ {
+ if (s->asPhi()) {
+ // nothing to do
+ } else if (auto move = s->asMove()) {
+ visit(move->source);
- if (Temp *t = s->target->asTemp()) {
- addTemp(t);
+ if (Temp *t = move->target->asTemp()) {
+ addTemp(t);
- if (isCollectable(t)) {
- _defsites[t->index].insert(currentBB);
- addDefInCurrentBlock(t);
+ if (isCollectable(t)) {
+ _defsites[t->index].insert(currentBB);
+ addDefInCurrentBlock(t);
- // For semi-pruned SSA:
- killed.setBit(t->index);
+ // For semi-pruned SSA:
+ killed.setBit(t->index);
+ }
+ } else {
+ visit(move->target);
}
} else {
- s->target->accept(this);
+ STMT_VISIT_ALL_KINDS(s)
}
}
- virtual void visitTemp(Temp *t)
+ void visit(Expr *e)
{
- addTemp(t);
+ if (auto t = e->asTemp()) {
+ addTemp(t);
- if (isCollectable(t))
- if (!killed.at(t->index))
- nonLocals.setBit(t->index);
+ if (isCollectable(t)) {
+ if (!killed.at(t->index)) {
+ nonLocals.setBit(t->index);
+ }
+ }
+ } else {
+ EXPR_VISIT_ALL_KINDS(e);
+ }
}
};
@@ -1192,6 +1190,15 @@ public:
return _defUses[variable.index].blockOfStatement;
}
+ void replaceBasicBlock(BasicBlock *from, BasicBlock *to)
+ {
+ for (auto &du : _defUses) {
+ if (du.blockOfStatement == from) {
+ du.blockOfStatement = to;
+ }
+ }
+ }
+
void removeUse(Stmt *usingStmt, const Temp &var)
{
Q_ASSERT(static_cast<unsigned>(var.index) < _defUses.size());
@@ -1345,7 +1352,7 @@ void insertPhiNode(const Temp &a, BasicBlock *y, IR::Function *f) {
//
// Undo(t, c) =
// mapping[t] = c
-class VariableRenamer: public StmtVisitor, public ExprVisitor
+class VariableRenamer
{
Q_DISABLE_COPY(VariableRenamer)
@@ -1466,7 +1473,7 @@ private:
for (Stmt *s : bb->statements()) {
currentStmt = s;
- s->accept(this);
+ visit(s);
}
for (BasicBlock *Y : bb->out) {
@@ -1532,23 +1539,35 @@ private:
return newIndex;
}
-protected:
- virtual void visitTemp(Temp *e) { // only called for uses, not defs
-// qDebug()<<"I: replacing use of"<<e->index<<"with"<<stack[e->index].top();
- e->index = currentNumber(*e);
- e->kind = Temp::VirtualRegister;
- defUses.addUse(*e, currentStmt);
- }
+private:
+ void visit(Stmt *s)
+ {
+ if (auto move = s->asMove()) {
+ // uses:
+ visit(move->source);
- virtual void visitMove(Move *s) {
- // uses:
- s->source->accept(this);
+ // defs:
+ if (Temp *t = move->target->asTemp()) {
+ renameTemp(t);
+ } else {
+ visit(move->target);
+ }
+ } else if (auto phi = s->asPhi()) {
+ renameTemp(phi->targetTemp);
+ } else {
+ STMT_VISIT_ALL_KINDS(s);
+ }
+ }
- // defs:
- if (Temp *t = s->target->asTemp())
- renameTemp(t);
- else
- s->target->accept(this);
+ void visit(Expr *e)
+ {
+ if (auto temp = e->asTemp()) {
+ temp->index = currentNumber(*temp);
+ temp->kind = Temp::VirtualRegister;
+ defUses.addUse(*temp, currentStmt);
+ } else {
+ EXPR_VISIT_ALL_KINDS(e);
+ }
}
void renameTemp(Temp *t) { // only called for defs, not uses
@@ -1558,44 +1577,6 @@ protected:
t->index = newIdx;
defUses.addDef(t, currentStmt, currentBB);
}
-
- virtual void visitConvert(Convert *e) { e->expr->accept(this); }
- virtual void visitPhi(Phi *s) { renameTemp(s->targetTemp); }
-
- virtual void visitExp(Exp *s) { s->expr->accept(this); }
-
- virtual void visitJump(Jump *) {}
- virtual void visitCJump(CJump *s) { s->cond->accept(this); }
- virtual void visitRet(Ret *s) { s->expr->accept(this); }
-
- virtual void visitConst(Const *) {}
- virtual void visitString(IR::String *) {}
- virtual void visitRegExp(IR::RegExp *) {}
- virtual void visitName(Name *) {}
- virtual void visitArgLocal(ArgLocal *) {}
- 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);
- }
};
// This function converts the IR to semi-pruned SSA form. For details about SSA and the algorightm,
@@ -1921,7 +1902,7 @@ private:
}
};
-class SideEffectsChecker: public ExprVisitor
+class SideEffectsChecker
{
bool _sideEffect;
@@ -1930,11 +1911,14 @@ public:
: _sideEffect(false)
{}
+ ~SideEffectsChecker()
+ {}
+
bool hasSideEffects(Expr *expr)
{
bool sideEffect = false;
qSwap(_sideEffect, sideEffect);
- expr->accept(this);
+ visit(expr);
qSwap(_sideEffect, sideEffect);
return sideEffect;
}
@@ -1947,12 +1931,35 @@ protected:
bool seenSideEffects() const { return _sideEffect; }
-protected:
- void visitConst(Const *) Q_DECL_OVERRIDE {}
- void visitString(IR::String *) Q_DECL_OVERRIDE {}
- void visitRegExp(IR::RegExp *) Q_DECL_OVERRIDE {}
+ void visit(Expr *e)
+ {
+ if (auto n = e->asName()) {
+ visitName(n);
+ } else if (auto t = e->asTemp()) {
+ visitTemp(t);
+ } else if (auto c = e->asClosure()) {
+ visitClosure(c);
+ } else if (auto c = e->asConvert()) {
+ visitConvert(c);
+ } else if (auto u = e->asUnop()) {
+ visitUnop(u);
+ } else if (auto b = e->asBinop()) {
+ visitBinop(b);
+ } else if (auto c = e->asCall()) {
+ visitCall(c);
+ } else if (auto n = e->asNew()) {
+ visitNew(n);
+ } else if (auto s = e->asSubscript()) {
+ visitSubscript(s);
+ } else if (auto m = e->asMember()) {
+ visitMember(m);
+ }
+ }
- void visitName(Name *e) Q_DECL_OVERRIDE {
+ virtual void visitTemp(Temp *) {}
+
+private:
+ void visitName(Name *e) {
if (e->freeOfSideEffects)
return;
// TODO: maybe we can distinguish between built-ins of which we know that they do not have
@@ -1961,15 +1968,12 @@ protected:
markAsSideEffect();
}
- void visitTemp(Temp *) Q_DECL_OVERRIDE {}
- void visitArgLocal(ArgLocal *) Q_DECL_OVERRIDE {}
-
- void visitClosure(Closure *) Q_DECL_OVERRIDE {
+ void visitClosure(Closure *) {
markAsSideEffect();
}
- void visitConvert(Convert *e) Q_DECL_OVERRIDE {
- e->expr->accept(this);
+ void visitConvert(Convert *e) {
+ visit(e->expr);
switch (e->expr->type) {
case QObjectType:
@@ -1982,8 +1986,8 @@ protected:
}
}
- void visitUnop(Unop *e) Q_DECL_OVERRIDE {
- e->expr->accept(this);
+ void visitUnop(Unop *e) {
+ visit(e->expr);
switch (e->op) {
case OpUPlus:
@@ -2000,7 +2004,7 @@ protected:
}
}
- void visitBinop(Binop *e) Q_DECL_OVERRIDE {
+ void visitBinop(Binop *e) {
// TODO: prune parts that don't have a side-effect. For example, in:
// function f(x) { +x+1; return 0; }
// we can prune the binop and leave the unop/conversion.
@@ -2012,30 +2016,30 @@ protected:
markAsSideEffect();
}
- void visitSubscript(Subscript *e) Q_DECL_OVERRIDE {
- e->base->accept(this);
- e->index->accept(this);
+ void visitSubscript(Subscript *e) {
+ visit(e->base);
+ visit(e->index);
markAsSideEffect();
}
- void visitMember(Member *e) Q_DECL_OVERRIDE {
- e->base->accept(this);
+ void visitMember(Member *e) {
+ visit(e->base);
if (e->freeOfSideEffects)
return;
markAsSideEffect();
}
- void visitCall(Call *e) Q_DECL_OVERRIDE {
- e->base->accept(this);
+ void visitCall(Call *e) {
+ visit(e->base);
for (ExprList *args = e->args; args; args = args->next)
- args->expr->accept(this);
+ visit(args->expr);
markAsSideEffect(); // TODO: there are built-in functions that have no side effect.
}
- void visitNew(New *e) Q_DECL_OVERRIDE {
- e->base->accept(this);
+ void visitNew(New *e) {
+ visit(e->base);
for (ExprList *args = e->args; args; args = args->next)
- args->expr->accept(this);
+ visit(args->expr);
markAsSideEffect(); // TODO: there are built-in types that have no side effect.
}
};
@@ -2044,21 +2048,19 @@ class EliminateDeadCode: public SideEffectsChecker
{
DefUses &_defUses;
StatementWorklist &_worklist;
- QVector<Temp *> _collectedTemps;
+ QVarLengthArray<Temp *, 8> _collectedTemps;
public:
EliminateDeadCode(DefUses &defUses, StatementWorklist &worklist)
: _defUses(defUses)
, _worklist(worklist)
- {
- _collectedTemps.reserve(8);
- }
+ {}
void run(Expr *&expr, Stmt *stmt) {
_collectedTemps.clear();
if (!hasSideEffects(expr)) {
expr = 0;
- foreach (Temp *t, _collectedTemps) {
+ for (Temp *t : _collectedTemps) {
_defUses.removeUse(stmt, *t);
_worklist += _defUses.defStmt(*t);
}
@@ -2066,13 +2068,13 @@ public:
}
protected:
- void visitTemp(Temp *e) Q_DECL_OVERRIDE
+ void visitTemp(Temp *e) Q_DECL_OVERRIDE Q_DECL_FINAL
{
_collectedTemps.append(e);
}
};
-class PropagateTempTypes: public StmtVisitor, ExprVisitor
+class PropagateTempTypes
{
const DefUses &defUses;
UntypedTemp theTemp;
@@ -2088,64 +2090,31 @@ public:
newType = type;
theTemp = temp;
if (Stmt *defStmt = defUses.defStmt(temp.temp))
- defStmt->accept(this);
+ visit(defStmt);
foreach (Stmt *use, defUses.uses(temp.temp))
- use->accept(this);
+ visit(use);
}
-protected:
- virtual void visitConst(Const *) {}
- virtual void visitString(IR::String *) {}
- virtual void visitRegExp(IR::RegExp *) {}
- virtual void visitName(Name *) {}
- virtual void visitTemp(Temp *e) {
- if (theTemp == UntypedTemp(*e)) {
- e->type = static_cast<Type>(newType.type);
- e->memberResolver = newType.memberResolver;
- }
- }
- virtual void visitArgLocal(ArgLocal *) {}
- virtual void visitClosure(Closure *) {}
- virtual void visitConvert(Convert *e) { e->expr->accept(this); }
- virtual void visitUnop(Unop *e) { e->expr->accept(this); }
- virtual void visitBinop(Binop *e) { e->left->accept(this); e->right->accept(this); }
-
- virtual void 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);
- }
-
- virtual void visitExp(Exp *s) {s->expr->accept(this);}
- virtual void visitMove(Move *s) {
- s->source->accept(this);
- s->target->accept(this);
+private:
+ void visit(Stmt *s)
+ {
+ STMT_VISIT_ALL_KINDS(s);
}
- virtual void visitJump(Jump *) {}
- virtual void visitCJump(CJump *s) { s->cond->accept(this); }
- virtual void visitRet(Ret *s) { s->expr->accept(this); }
- virtual void visitPhi(Phi *s) {
- s->targetTemp->accept(this);
- foreach (Expr *e, s->incoming)
- e->accept(this);
+ void visit(Expr *e)
+ {
+ if (auto temp = e->asTemp()) {
+ if (theTemp == UntypedTemp(*temp)) {
+ temp->type = static_cast<Type>(newType.type);
+ temp->memberResolver = newType.memberResolver;
+ }
+ } else {
+ EXPR_VISIT_ALL_KINDS(e);
+ }
}
};
-class TypeInference: public StmtVisitor, public ExprVisitor
+class TypeInference
{
enum { DebugTypeInference = 0 };
@@ -2247,7 +2216,7 @@ private:
TypingResult ty;
std::swap(_ty, ty);
std::swap(_currentStmt, s);
- _currentStmt->accept(this);
+ visit(_currentStmt);
std::swap(_currentStmt, s);
std::swap(_ty, ty);
return ty.fullyTyped;
@@ -2256,7 +2225,7 @@ private:
TypingResult run(Expr *e) {
TypingResult ty;
std::swap(_ty, ty);
- e->accept(this);
+ visit(e);
std::swap(_ty, ty);
if (ty.type != UnknownType)
@@ -2298,39 +2267,74 @@ private:
}
}
-protected:
- virtual void visitConst(Const *e) {
- if (e->type & NumberType) {
- if (canConvertToSignedInteger(e->value))
+private:
+ void visit(Expr *e)
+ {
+ if (auto c = e->asConst()) {
+ visitConst(c);
+ } else if (auto s = e->asString()) {
+ visitString(s);
+ } else if (auto r = e->asRegExp()) {
+ visitRegExp(r);
+ } else if (auto n = e->asName()) {
+ visitName(n);
+ } else if (auto t = e->asTemp()) {
+ visitTemp(t);
+ } else if (auto a = e->asArgLocal()) {
+ visitArgLocal(a);
+ } else if (auto c = e->asClosure()) {
+ visitClosure(c);
+ } else if (auto c = e->asConvert()) {
+ visitConvert(c);
+ } else if (auto u = e->asUnop()) {
+ visitUnop(u);
+ } else if (auto b = e->asBinop()) {
+ visitBinop(b);
+ } else if (auto c = e->asCall()) {
+ visitCall(c);
+ } else if (auto n = e->asNew()) {
+ visitNew(n);
+ } else if (auto s = e->asSubscript()) {
+ visitSubscript(s);
+ } else if (auto m = e->asMember()) {
+ visitMember(m);
+ } else {
+ Q_UNREACHABLE();
+ }
+ }
+
+ void visitConst(Const *c) {
+ if (c->type & NumberType) {
+ if (canConvertToSignedInteger(c->value))
_ty = TypingResult(SInt32Type);
- else if (canConvertToUnsignedInteger(e->value))
+ else if (canConvertToUnsignedInteger(c->value))
_ty = TypingResult(UInt32Type);
else
- _ty = TypingResult(e->type);
+ _ty = TypingResult(c->type);
} else
- _ty = TypingResult(e->type);
+ _ty = TypingResult(c->type);
}
- virtual void visitString(IR::String *) { _ty = TypingResult(StringType); }
- virtual void visitRegExp(IR::RegExp *) { _ty = TypingResult(VarType); }
- virtual void visitName(Name *) { _ty = TypingResult(VarType); }
- virtual void visitTemp(Temp *e) {
+ void visitString(IR::String *) { _ty = TypingResult(StringType); }
+ void visitRegExp(IR::RegExp *) { _ty = TypingResult(VarType); }
+ void visitName(Name *) { _ty = TypingResult(VarType); }
+ void visitTemp(Temp *e) {
if (e->memberResolver && e->memberResolver->isValid())
_ty = TypingResult(e->memberResolver);
else
_ty = TypingResult(_tempTypes[e->index]);
setType(e, _ty.type);
}
- virtual void visitArgLocal(ArgLocal *e) {
+ void visitArgLocal(ArgLocal *e) {
_ty = TypingResult(VarType);
setType(e, _ty.type);
}
- virtual void visitClosure(Closure *) { _ty = TypingResult(VarType); }
- virtual void visitConvert(Convert *e) {
+ void visitClosure(Closure *) { _ty = TypingResult(VarType); }
+ void visitConvert(Convert *e) {
_ty = TypingResult(e->type);
}
- virtual void visitUnop(Unop *e) {
+ void visitUnop(Unop *e) {
_ty = run(e->expr);
switch (e->op) {
case OpUPlus: _ty.type = DoubleType; return;
@@ -2347,7 +2351,7 @@ protected:
}
}
- virtual void visitBinop(Binop *e) {
+ void visitBinop(Binop *e) {
TypingResult leftTy = run(e->left);
TypingResult rightTy = run(e->right);
_ty.fullyTyped = leftTy.fullyTyped && rightTy.fullyTyped;
@@ -2405,24 +2409,24 @@ protected:
}
}
- virtual void visitCall(Call *e) {
+ 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 = VarType;
}
- virtual void visitNew(New *e) {
+ 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 = VarType;
}
- virtual void visitSubscript(Subscript *e) {
+ void visitSubscript(Subscript *e) {
_ty.fullyTyped = run(e->base).fullyTyped && run(e->index).fullyTyped;
_ty.type = VarType;
}
- virtual void visitMember(Member *e) {
+ void visitMember(Member *e) {
_ty = run(e->base);
if (_ty.fullyTyped && _ty.type.memberResolver && _ty.type.memberResolver->isValid()) {
@@ -2432,8 +2436,27 @@ protected:
_ty.type = VarType;
}
- virtual void visitExp(Exp *s) { _ty = run(s->expr); }
- virtual void visitMove(Move *s) {
+ void visit(Stmt *s)
+ {
+ if (auto e = s->asExp()) {
+ visitExp(e);
+ } else if (auto m = s->asMove()) {
+ visitMove(m);
+ } else if (auto j = s->asJump()) {
+ visitJump(j);
+ } else if (auto c = s->asCJump()) {
+ visitCJump(c);
+ } else if (auto r = s->asRet()) {
+ visitRet(r);
+ } else if (auto p = s->asPhi()) {
+ visitPhi(p);
+ } else {
+ Q_UNREACHABLE();
+ }
+ }
+
+ void visitExp(Exp *s) { _ty = run(s->expr); }
+ void visitMove(Move *s) {
if (Temp *t = s->target->asTemp()) {
if (Name *n = s->source->asName()) {
if (n->builtin == Name::builtin_qml_context) {
@@ -2454,10 +2477,10 @@ protected:
_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 visitPhi(Phi *s) {
+ void visitJump(Jump *) { _ty = TypingResult(MissingType); }
+ void visitCJump(CJump *s) { _ty = run(s->cond); }
+ void visitRet(Ret *s) { _ty = run(s->expr); }
+ 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]);
@@ -2668,6 +2691,7 @@ void convertConst(Const *c, Type targetType)
case UndefinedType:
c->value = qt_qnan();
c->type = targetType;
+ break;
default:
Q_UNIMPLEMENTED();
Q_ASSERT(!"Unimplemented!");
@@ -2676,14 +2700,15 @@ void convertConst(Const *c, Type targetType)
c->type = targetType;
}
-class TypePropagation: public StmtVisitor, public ExprVisitor {
+class TypePropagation
+{
DefUses &_defUses;
Type _ty;
IR::Function *_f;
bool run(Expr *&e, Type requestedType = UnknownType, bool insertConversion = true) {
qSwap(_ty, requestedType);
- e->accept(this);
+ visit(e);
qSwap(_ty, requestedType);
if (requestedType != UnknownType) {
@@ -2730,7 +2755,7 @@ public:
for (Stmt *s : bb->statements()) {
_currStmt = s;
- s->accept(this);
+ visit(s);
}
foreach (const Conversion &conversion, _conversions) {
@@ -2816,8 +2841,29 @@ public:
}
}
-protected:
- virtual void visitConst(Const *c) {
+private:
+ void visit(Expr *e)
+ {
+ if (auto c = e->asConst()) {
+ visitConst(c);
+ } else if (auto c = e->asConvert()) {
+ run(c->expr, c->type);
+ } else if (auto u = e->asUnop()) {
+ run(u->expr, u->type);
+ } else if (auto b = e->asBinop()) {
+ visitBinop(b);
+ } else if (auto c = e->asCall()) {
+ visitCall(c);
+ } else if (auto n = e->asNew()) {
+ visitNew(n);
+ } else if (auto s = e->asSubscript()) {
+ visitSubscript(s);
+ } else if (auto m = e->asMember()) {
+ visitMember(m);
+ }
+ }
+
+ void visitConst(Const *c) {
if (_ty & NumberType && c->type & NumberType) {
if (_ty == SInt32Type)
c->value = QV4::Primitive::toInt32(c->value);
@@ -2827,15 +2873,7 @@ protected:
}
}
- virtual void visitString(IR::String *) {}
- virtual void visitRegExp(IR::RegExp *) {}
- virtual void visitName(Name *) {}
- virtual void visitTemp(Temp *) {}
- virtual void visitArgLocal(ArgLocal *) {}
- virtual void visitClosure(Closure *) {}
- virtual void visitConvert(Convert *e) { run(e->expr, e->type); }
- virtual void visitUnop(Unop *e) { run(e->expr, e->type); }
- virtual void visitBinop(Binop *e) {
+ void visitBinop(Binop *e) {
// FIXME: This routine needs more tuning!
switch (e->op) {
case OpAdd:
@@ -2886,20 +2924,36 @@ protected:
Q_UNREACHABLE();
}
}
- virtual void visitCall(Call *e) {
+ void visitCall(Call *e) {
run(e->base);
for (ExprList *it = e->args; it; it = it->next)
run(it->expr);
}
- virtual void visitNew(New *e) {
+ 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 visitMove(Move *s) {
+ void visitSubscript(Subscript *e) { run(e->base); run(e->index); }
+ void visitMember(Member *e) { run(e->base); }
+
+ void visit(Stmt *s)
+ {
+ if (auto e = s->asExp()) {
+ visitExp(e);
+ } else if (auto m = s->asMove()) {
+ visitMove(m);
+ } else if (auto c = s->asCJump()) {
+ visitCJump(c);
+ } else if (auto r = s->asRet()) {
+ visitRet(r);
+ } else if (auto p = s->asPhi()) {
+ visitPhi(p);
+ }
+ }
+
+ void visitExp(Exp *s) { run(s->expr); }
+ void visitMove(Move *s) {
if (s->source->asConvert())
return; // this statement got inserted for a phi-node type conversion
@@ -2924,12 +2978,11 @@ protected:
run(s->source, s->target->type, !inhibitConversion);
}
- virtual void visitJump(Jump *) {}
- virtual void visitCJump(CJump *s) {
+ void visitCJump(CJump *s) {
run(s->cond, BoolType);
}
- virtual void visitRet(Ret *s) { run(s->expr); }
- virtual void visitPhi(Phi *s) {
+ void visitRet(Ret *s) { run(s->expr); }
+ void visitPhi(Phi *s) {
Type ty = s->targetTemp->type;
for (int i = 0, ei = s->incoming.size(); i != ei; ++i)
run(s->incoming[i], ty);
@@ -3298,6 +3351,15 @@ class BlockScheduler
// this is a loop, where there in -> candidate edge is the jump back to the top of the loop.
continue;
+ if (in == candidate)
+ // this is a very tight loop, e.g.:
+ // L1: ...
+ // goto L1
+ // This can happen when, for example, the basic-block merging gets rid of the empty
+ // body block. In this case, we can safely schedule this block (if all other
+ // incoming edges are either loop-back edges, or have been scheduled already).
+ continue;
+
return false; // an incoming edge that is not yet emitted, and is not a back-edge
}
@@ -3503,7 +3565,7 @@ static Expr *clone(Expr *e, IR::Function *function) {
}
}
-class ExprReplacer: public StmtVisitor, public ExprVisitor
+class ExprReplacer
{
DefUses &_defUses;
IR::Function* _function;
@@ -3534,7 +3596,7 @@ public:
// qout << " " << uses.size() << " uses:"<<endl;
foreach (Stmt *use, uses) {
// qout<<" ";use->dump(qout);qout<<"\n";
- use->accept(this);
+ visit(use);
// qout<<" -> ";use->dump(qout);qout<<"\n";
W += use;
if (newUses)
@@ -3545,45 +3607,101 @@ public:
qSwap(_toReplace, toReplace);
}
-protected:
- virtual void visitConst(Const *) {}
- virtual void visitString(IR::String *) {}
- virtual void visitRegExp(IR::RegExp *) {}
- virtual void visitName(Name *) {}
- virtual void visitTemp(Temp *) {}
- virtual void visitArgLocal(ArgLocal *) {}
- virtual void visitClosure(Closure *) {}
- virtual void visitConvert(Convert *e) { check(e->expr); }
- virtual void visitUnop(Unop *e) { check(e->expr); }
- virtual void visitBinop(Binop *e) { check(e->left); check(e->right); }
- virtual void visitCall(Call *e) {
+private:
+ void visit(Expr *e)
+ {
+ if (auto c = e->asConst()) {
+ visitConst(c);
+ } else if (auto s = e->asString()) {
+ visitString(s);
+ } else if (auto r = e->asRegExp()) {
+ visitRegExp(r);
+ } else if (auto n = e->asName()) {
+ visitName(n);
+ } else if (auto t = e->asTemp()) {
+ visitTemp(t);
+ } else if (auto a = e->asArgLocal()) {
+ visitArgLocal(a);
+ } else if (auto c = e->asClosure()) {
+ visitClosure(c);
+ } else if (auto c = e->asConvert()) {
+ visitConvert(c);
+ } else if (auto u = e->asUnop()) {
+ visitUnop(u);
+ } else if (auto b = e->asBinop()) {
+ visitBinop(b);
+ } else if (auto c = e->asCall()) {
+ visitCall(c);
+ } else if (auto n = e->asNew()) {
+ visitNew(n);
+ } else if (auto s = e->asSubscript()) {
+ visitSubscript(s);
+ } else if (auto m = e->asMember()) {
+ visitMember(m);
+ } else {
+ Q_UNREACHABLE();
+ }
+ }
+
+ void visitConst(Const *) {}
+ void visitString(IR::String *) {}
+ void visitRegExp(IR::RegExp *) {}
+ void visitName(Name *) {}
+ void visitTemp(Temp *) {}
+ void visitArgLocal(ArgLocal *) {}
+ void visitClosure(Closure *) {}
+ void visitConvert(Convert *e) { check(e->expr); }
+ void visitUnop(Unop *e) { check(e->expr); }
+ void visitBinop(Binop *e) { check(e->left); check(e->right); }
+ void visitCall(Call *e) {
check(e->base);
for (ExprList *it = e->args; it; it = it->next)
check(it->expr);
}
- virtual void visitNew(New *e) {
+ void visitNew(New *e) {
check(e->base);
for (ExprList *it = e->args; it; it = it->next)
check(it->expr);
}
- virtual void visitSubscript(Subscript *e) { check(e->base); check(e->index); }
- virtual void visitMember(Member *e) { check(e->base); }
- virtual void visitExp(Exp *s) { check(s->expr); }
- virtual void visitMove(Move *s) { check(s->target); check(s->source); }
- virtual void visitJump(Jump *) {}
- virtual void visitCJump(CJump *s) { check(s->cond); }
- virtual void visitRet(Ret *s) { check(s->expr); }
- virtual void visitPhi(Phi *s) {
+ void visitSubscript(Subscript *e) { check(e->base); check(e->index); }
+ void visitMember(Member *e) { check(e->base); }
+
+ void visit(Stmt *s)
+ {
+ if (auto e = s->asExp()) {
+ visitExp(e);
+ } else if (auto m = s->asMove()) {
+ visitMove(m);
+ } else if (auto j = s->asJump()) {
+ visitJump(j);
+ } else if (auto c = s->asCJump()) {
+ visitCJump(c);
+ } else if (auto r = s->asRet()) {
+ visitRet(r);
+ } else if (auto p = s->asPhi()) {
+ visitPhi(p);
+ } else {
+ Q_UNREACHABLE();
+ }
+ }
+
+ void visitExp(Exp *s) { check(s->expr); }
+ void visitMove(Move *s) { check(s->target); check(s->source); }
+ void visitJump(Jump *) {}
+ void visitCJump(CJump *s) { check(s->cond); }
+ void visitRet(Ret *s) { check(s->expr); }
+ void visitPhi(Phi *s) {
for (int i = 0, ei = s->incoming.size(); i != ei; ++i)
check(s->incoming[i]);
}
private:
void check(Expr *&e) {
- if (equals(e, _toReplace))
+ if (equals(e, _toReplace)) {
e = clone(_replacement, _function);
- else
- e->accept(this);
+ } else {
+ visit(e);
+ }
}
// This only calculates equality for everything needed by constant propagation
@@ -3624,6 +3742,8 @@ namespace {
void unlink(BasicBlock *from, BasicBlock *to, IR::Function *func, DefUses &defUses,
StatementWorklist &W, DominatorTree &dt)
{
+ enum { DebugUnlinking = 0 };
+
struct Util {
static void removeIncomingEdge(BasicBlock *from, BasicBlock *to, DefUses &defUses, StatementWorklist &W)
{
@@ -3662,11 +3782,17 @@ void unlink(BasicBlock *from, BasicBlock *to, IR::Function *func, DefUses &defUs
}
};
+ Q_ASSERT(!from->isRemoved());
+ Q_ASSERT(!to->isRemoved());
+
// don't purge blocks that are entry points for catch statements. They might not be directly
// connected, but are required anyway
if (to->isExceptionHandler())
return;
+ if (DebugUnlinking)
+ qDebug("Unlinking L%d -> L%d...", from->index(), to->index());
+
// First, unlink the edge
from->out.removeOne(to);
Util::removeIncomingEdge(from, to, defUses, W);
@@ -3676,8 +3802,12 @@ void unlink(BasicBlock *from, BasicBlock *to, IR::Function *func, DefUses &defUs
// Check if the target is still reachable...
if (Util::isReachable(to, dt)) { // yes, recalculate the immediate dominator, and we're done.
+ if (DebugUnlinking)
+ qDebug(".. L%d is still reachable, recalulate idom.", to->index());
dt.collectSiblings(to, siblings);
} else {
+ if (DebugUnlinking)
+ qDebug(".. L%d is unreachable, purging it:", to->index());
// The target is unreachable, so purge it:
QVector<BasicBlock *> toPurge;
toPurge.reserve(8);
@@ -3685,6 +3815,8 @@ void unlink(BasicBlock *from, BasicBlock *to, IR::Function *func, DefUses &defUs
while (!toPurge.isEmpty()) {
BasicBlock *bb = toPurge.first();
toPurge.removeFirst();
+ if (DebugUnlinking)
+ qDebug("... purging L%d", bb->index());
if (bb->isRemoved())
continue;
@@ -3728,6 +3860,8 @@ void unlink(BasicBlock *from, BasicBlock *to, IR::Function *func, DefUses &defUs
}
dt.recalculateIDoms(siblings);
+ if (DebugUnlinking)
+ qDebug("Unlinking done.");
}
bool tryOptimizingComparison(Expr *&expr)
@@ -3747,42 +3881,42 @@ bool tryOptimizingComparison(Expr *&expr)
switch (b->op) {
case OpGt:
- leftConst->value = Runtime::compareGreaterThan(l, r);
+ leftConst->value = Runtime::method_compareGreaterThan(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
case OpLt:
- leftConst->value = Runtime::compareLessThan(l, r);
+ leftConst->value = Runtime::method_compareLessThan(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
case OpGe:
- leftConst->value = Runtime::compareGreaterEqual(l, r);
+ leftConst->value = Runtime::method_compareGreaterEqual(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
case OpLe:
- leftConst->value = Runtime::compareLessEqual(l, r);
+ leftConst->value = Runtime::method_compareLessEqual(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
case OpStrictEqual:
- leftConst->value = Runtime::compareStrictEqual(l, r);
+ leftConst->value = Runtime::method_compareStrictEqual(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
case OpEqual:
- leftConst->value = Runtime::compareEqual(l, r);
+ leftConst->value = Runtime::method_compareEqual(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
case OpStrictNotEqual:
- leftConst->value = Runtime::compareStrictNotEqual(l, r);
+ leftConst->value = Runtime::method_compareStrictNotEqual(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
case OpNotEqual:
- leftConst->value = Runtime::compareNotEqual(l, r);
+ leftConst->value = Runtime::method_compareNotEqual(l, r);
leftConst->type = BoolType;
expr = leftConst;
return true;
@@ -4150,7 +4284,8 @@ void optimizeSSA(StatementWorklist &W, DefUses &defUses, DominatorTree &df)
}
//### TODO: use DefUses from the optimizer, because it already has all this information
-class InputOutputCollector: protected StmtVisitor, protected ExprVisitor {
+class InputOutputCollector
+{
void setOutput(Temp *out)
{
Q_ASSERT(!output);
@@ -4167,48 +4302,33 @@ public:
void collect(Stmt *s) {
inputs.resize(0);
output = 0;
- s->accept(this);
+ visit(s);
}
-protected:
- virtual void visitConst(Const *) {}
- virtual void visitString(IR::String *) {}
- virtual void visitRegExp(IR::RegExp *) {}
- virtual void visitName(Name *) {}
- virtual void visitTemp(Temp *e) {
- inputs.push_back(e);
- }
- virtual void visitArgLocal(ArgLocal *) {}
- virtual void visitClosure(Closure *) {}
- virtual void visitConvert(Convert *e) { e->expr->accept(this); }
- virtual void visitUnop(Unop *e) { e->expr->accept(this); }
- virtual void visitBinop(Binop *e) { e->left->accept(this); e->right->accept(this); }
- virtual void 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); }
- virtual void visitExp(Exp *s) { s->expr->accept(this); }
- virtual void visitMove(Move *s) {
- s->source->accept(this);
- if (Temp *t = s->target->asTemp()) {
- setOutput(t);
+private:
+ void visit(Expr *e)
+ {
+ if (auto t = e->asTemp()) {
+ inputs.push_back(t);
} else {
- s->target->accept(this);
+ EXPR_VISIT_ALL_KINDS(e);
}
}
- virtual void visitJump(Jump *) {}
- virtual void visitCJump(CJump *s) { s->cond->accept(this); }
- virtual void visitRet(Ret *s) { s->expr->accept(this); }
- virtual void visitPhi(Phi *) {
- // Handled separately
+
+ void visit(Stmt *s)
+ {
+ if (auto m = s->asMove()) {
+ visit(m->source);
+ if (Temp *t = m->target->asTemp()) {
+ setOutput(t);
+ } else {
+ visit(m->target);
+ }
+ } else if (s->asPhi()) {
+ // Handled separately
+ } else {
+ STMT_VISIT_ALL_KINDS(s);
+ }
}
};
@@ -4221,7 +4341,59 @@ protected:
* See LifeTimeIntervals::renumber for details on the numbering.
*/
class LifeRanges {
- typedef QSet<Temp> LiveRegs;
+ class LiveRegs
+ {
+ typedef std::vector<int> Storage;
+ Storage regs;
+
+ public:
+ void insert(int r)
+ {
+ if (find(r) == end())
+ regs.push_back(r);
+ }
+
+ void unite(const LiveRegs &other)
+ {
+ if (other.empty())
+ return;
+ if (empty()) {
+ regs = other.regs;
+ return;
+ }
+ for (int r : other.regs)
+ insert(r);
+ }
+
+ typedef Storage::iterator iterator;
+ iterator find(int r)
+ { return std::find(regs.begin(), regs.end(), r); }
+
+ iterator begin()
+ { return regs.begin(); }
+
+ iterator end()
+ { return regs.end(); }
+
+ void erase(iterator it)
+ { regs.erase(it); }
+
+ void remove(int r)
+ {
+ iterator it = find(r);
+ if (it != end())
+ erase(it);
+ }
+
+ bool empty() const
+ { return regs.empty(); }
+
+ int size() const
+ { return int(regs.size()); }
+
+ int at(int idx) const
+ { return regs.at(idx); }
+ };
std::vector<LiveRegs> _liveIn;
std::vector<LifeTimeInterval *> _intervals;
@@ -4229,14 +4401,21 @@ class LifeRanges {
LifeTimeInterval &interval(const Temp *temp)
{
- LifeTimeInterval *&lti = _intervals[temp->index];
- if (Q_UNLIKELY(!lti)) {
- lti = new LifeTimeInterval;
- lti->setTemp(*temp);
- }
+ LifeTimeInterval *lti = _intervals[temp->index];
+ Q_ASSERT(lti);
return *lti;
}
+ void ensureInterval(const IR::Temp &temp)
+ {
+ Q_ASSERT(!temp.isInvalid());
+ LifeTimeInterval *&lti = _intervals[temp.index];
+ if (lti)
+ return;
+ lti = new LifeTimeInterval;
+ lti->setTemp(temp);
+ }
+
int defPosition(IR::Stmt *s) const
{
return usePosition(s) + 1;
@@ -4290,13 +4469,13 @@ public:
IRPrinter printer(&qout);
for (size_t i = 0, ei = _liveIn.size(); i != ei; ++i) {
qout << "L" << i <<" live-in: ";
- QList<Temp> live = QList<Temp>::fromSet(_liveIn.at(i));
- if (live.isEmpty())
+ auto live = _liveIn.at(i);
+ if (live.empty())
qout << "(none)";
std::sort(live.begin(), live.end());
for (int i = 0; i < live.size(); ++i) {
if (i > 0) qout << ", ";
- printer.print(&live[i]);
+ qout << '%' << live.at(i);
}
qout << endl;
}
@@ -4315,8 +4494,10 @@ private:
for (Stmt *s : successor->statements()) {
if (Phi *phi = s->asPhi()) {
- if (Temp *t = phi->incoming.at(bbIndex)->asTemp())
- live.insert(*t);
+ if (Temp *t = phi->incoming.at(bbIndex)->asTemp()) {
+ ensureInterval(*t);
+ live.insert(t->index);
+ }
} else {
break;
}
@@ -4325,14 +4506,15 @@ private:
const QVector<Stmt *> &statements = bb->statements();
- foreach (const Temp &opd, live)
- interval(&opd).addRange(start(bb), end(bb));
+ for (int reg : live)
+ _intervals[reg]->addRange(start(bb), end(bb));
InputOutputCollector collector;
for (int i = statements.size() - 1; i >= 0; --i) {
Stmt *s = statements.at(i);
if (Phi *phi = s->asPhi()) {
- LiveRegs::iterator it = live.find(*phi->targetTemp);
+ ensureInterval(*phi->targetTemp);
+ LiveRegs::iterator it = live.find(phi->targetTemp->index);
if (it == live.end()) {
// a phi node target that is only defined, but never used
interval(phi->targetTemp).setFrom(start(bb));
@@ -4345,25 +4527,27 @@ private:
collector.collect(s);
//### TODO: use DefUses from the optimizer, because it already has all this information
if (Temp *opd = collector.output) {
+ ensureInterval(*opd);
LifeTimeInterval &lti = interval(opd);
lti.setFrom(defPosition(s));
- live.remove(lti.temp());
+ live.remove(lti.temp().index);
_sortedIntervals->add(&lti);
}
//### TODO: use DefUses from the optimizer, because it already has all this information
for (size_t i = 0, ei = collector.inputs.size(); i != ei; ++i) {
Temp *opd = collector.inputs[i];
+ ensureInterval(*opd);
interval(opd).addRange(start(bb), usePosition(s));
- live.insert(*opd);
+ live.insert(opd->index);
}
}
if (loopEnd) { // Meaning: bb is a loop header, because loopEnd is set to non-null.
- foreach (const Temp &opd, live)
- interval(&opd).addRange(start(bb), usePosition(loopEnd->terminator()));
+ for (int reg : live)
+ _intervals[reg]->addRange(start(bb), usePosition(loopEnd->terminator()));
}
- _liveIn[bb->index()] = live;
+ _liveIn[bb->index()] = std::move(live);
}
};
@@ -4378,7 +4562,7 @@ void removeUnreachleBlocks(IR::Function *function)
function->renumberBasicBlocks();
}
-class ConvertArgLocals: protected StmtVisitor, protected ExprVisitor
+class ConvertArgLocals
{
public:
ConvertArgLocals(IR::Function *function)
@@ -4416,10 +4600,13 @@ public:
}
}
- for (BasicBlock *bb : function->basicBlocks())
- if (!bb->isRemoved())
- for (Stmt *s : bb->statements())
- s->accept(this);
+ for (BasicBlock *bb : function->basicBlocks()) {
+ if (!bb->isRemoved()) {
+ for (Stmt *s : bb->statements()) {
+ visit(s);
+ }
+ }
+ }
if (convertArgs && function->formals.size() > 0)
function->basicBlock(0)->prependStatements(extraMoves);
@@ -4427,39 +4614,45 @@ public:
function->locals.clear();
}
-protected:
- virtual void visitConst(Const *) {}
- virtual void visitString(IR::String *) {}
- virtual void visitRegExp(IR::RegExp *) {}
- virtual void visitName(Name *) {}
- virtual void visitTemp(Temp *) {}
- virtual void visitArgLocal(ArgLocal *) {}
- virtual void visitClosure(Closure *) {}
- virtual void visitConvert(Convert *e) { check(e->expr); }
- virtual void visitUnop(Unop *e) { check(e->expr); }
- virtual void visitBinop(Binop *e) { check(e->left); check(e->right); }
- virtual void visitCall(Call *e) {
- check(e->base);
- for (ExprList *it = e->args; it; it = it->next)
- check(it->expr);
- }
- virtual void visitNew(New *e) {
- check(e->base);
- for (ExprList *it = e->args; it; it = it->next)
- check(it->expr);
+private:
+ void visit(Stmt *s)
+ {
+ if (auto e = s->asExp()) {
+ check(e->expr);
+ } else if (auto m = s->asMove()) {
+ check(m->target); check(m->source);
+ } else if (auto c = s->asCJump()) {
+ check(c->cond);
+ } else if (auto r = s->asRet()) {
+ check(r->expr);
+ }
}
- virtual void visitSubscript(Subscript *e) { check(e->base); check(e->index); }
- virtual void visitMember(Member *e) { check(e->base); }
- virtual void visitExp(Exp *s) { check(s->expr); }
- virtual void visitMove(Move *s) { check(s->target); check(s->source); }
- virtual void visitJump(Jump *) {}
- virtual void visitCJump(CJump *s) { check(s->cond); }
- virtual void visitRet(Ret *s) { check(s->expr); }
- virtual void visitPhi(Phi *) {
- Q_UNREACHABLE();
+
+ void visit(Expr *e)
+ {
+ if (auto c = e->asConvert()) {
+ check(c->expr);
+ } else if (auto u = e->asUnop()) {
+ check(u->expr);
+ } else if (auto b = e->asBinop()) {
+ check(b->left); check(b->right);
+ } else if (auto c = e->asCall()) {
+ check(c->base);
+ for (ExprList *it = c->args; it; it = it->next) {
+ check(it->expr);
+ }
+ } else if (auto n = e->asNew()) {
+ check(n->base);
+ for (ExprList *it = n->args; it; it = it->next) {
+ check(it->expr);
+ }
+ } else if (auto s = e->asSubscript()) {
+ check(s->base); check(s->index);
+ } else if (auto m = e->asMember()) {
+ check(m->base);
+ }
}
-private:
void check(Expr *&e) {
if (ArgLocal *al = e->asArgLocal()) {
if (al->kind == ArgLocal::Local) {
@@ -4472,7 +4665,7 @@ private:
e = t;
}
} else {
- e->accept(this);
+ visit(e);
}
}
@@ -4495,7 +4688,7 @@ private:
std::vector<int> tempForLocal;
};
-class CloneBasicBlock: protected IR::StmtVisitor, protected CloneExpr
+class CloneBasicBlock: protected CloneExpr
{
public:
BasicBlock *operator()(IR::BasicBlock *originalBlock)
@@ -4503,38 +4696,37 @@ public:
block = new BasicBlock(originalBlock->function, 0);
for (Stmt *s : originalBlock->statements()) {
- s->accept(this);
+ visit(s);
clonedStmt->location = s->location;
}
return block;
}
-protected:
- virtual void visitExp(Exp *stmt)
- { clonedStmt = block->EXP(clone(stmt->expr)); }
-
- virtual void visitMove(Move *stmt)
- { clonedStmt = block->MOVE(clone(stmt->target), clone(stmt->source)); }
-
- virtual void visitJump(Jump *stmt)
- { clonedStmt = block->JUMP(stmt->target); }
-
- virtual void visitCJump(CJump *stmt)
- { clonedStmt = block->CJUMP(clone(stmt->cond), stmt->iftrue, stmt->iffalse); }
-
- virtual void visitRet(Ret *stmt)
- { clonedStmt = block->RET(clone(stmt->expr)); }
-
- virtual void visitPhi(Phi *stmt)
+private:
+ void visit(Stmt *s)
{
- Phi *phi = block->function->NewStmt<Phi>();
- clonedStmt = phi;
-
- phi->targetTemp = clone(stmt->targetTemp);
- foreach (Expr *in, stmt->incoming)
- phi->incoming.append(clone(in));
- block->appendStatement(phi);
+ if (auto e = s->asExp()) {
+ clonedStmt = block->EXP(clone(e->expr));
+ } else if (auto m = s->asMove()) {
+ clonedStmt = block->MOVE(clone(m->target), clone(m->source));
+ } else if (auto j = s->asJump()) {
+ clonedStmt = block->JUMP(j->target);
+ } else if (auto c = s->asCJump()) {
+ clonedStmt = block->CJUMP(clone(c->cond), c->iftrue, c->iffalse);
+ } else if (auto r = s->asRet()) {
+ clonedStmt = block->RET(clone(r->expr));
+ } else if (auto p = s->asPhi()) {
+ Phi *phi = block->function->NewStmt<Phi>();
+ clonedStmt = phi;
+
+ phi->targetTemp = clone(p->targetTemp);
+ foreach (Expr *in, p->incoming)
+ phi->incoming.append(clone(in));
+ block->appendStatement(phi);
+ } else {
+ Q_UNREACHABLE();
+ }
}
private:
@@ -4703,13 +4895,20 @@ static void verifyCFG(IR::Function *function)
Q_ASSERT(function->basicBlock(bb->index()) == bb);
// Check the terminators:
- if (Jump *jump = bb->terminator()->asJump()) {
+ Stmt *terminator = bb->terminator();
+ if (terminator == nullptr) {
+ Stmt *last = bb->statements().last();
+ Call *call = last->asExp()->expr->asCall();
+ Name *baseName = call->base->asName();
+ Q_ASSERT(baseName->builtin == Name::builtin_rethrow);
+ Q_UNUSED(baseName);
+ } else if (Jump *jump = terminator->asJump()) {
Q_UNUSED(jump);
Q_ASSERT(jump->target);
Q_ASSERT(!jump->target->isRemoved());
Q_ASSERT(bb->out.size() == 1);
Q_ASSERT(bb->out.first() == jump->target);
- } else if (CJump *cjump = bb->terminator()->asCJump()) {
+ } else if (CJump *cjump = terminator->asCJump()) {
Q_UNUSED(cjump);
Q_ASSERT(bb->out.size() == 2);
Q_ASSERT(cjump->iftrue);
@@ -4718,7 +4917,7 @@ static void verifyCFG(IR::Function *function)
Q_ASSERT(cjump->iffalse);
Q_ASSERT(!cjump->iffalse->isRemoved());
Q_ASSERT(cjump->iffalse == bb->out[1]);
- } else if (bb->terminator()->asRet()) {
+ } else if (terminator->asRet()) {
Q_ASSERT(bb->out.size() == 0);
} else {
Q_UNREACHABLE();
@@ -4766,7 +4965,7 @@ static void verifyNoPointerSharing(IR::Function *function)
if (!DoVerification)
return;
- class : public StmtVisitor, public ExprVisitor {
+ class {
public:
void operator()(IR::Function *f)
{
@@ -4774,44 +4973,23 @@ static void verifyNoPointerSharing(IR::Function *function)
if (bb->isRemoved())
continue;
- for (Stmt *s : bb->statements())
- s->accept(this);
+ for (Stmt *s : bb->statements()) {
+ visit(s);
+ }
}
}
- protected:
- virtual void visitExp(Exp *s) { check(s); s->expr->accept(this); }
- virtual void visitMove(Move *s) { check(s); s->target->accept(this); s->source->accept(this); }
- virtual void visitJump(Jump *s) { check(s); }
- virtual void visitCJump(CJump *s) { check(s); s->cond->accept(this); }
- virtual void visitRet(Ret *s) { check(s); s->expr->accept(this); }
- virtual void visitPhi(Phi *s)
+ private:
+ void visit(Stmt *s)
{
check(s);
- s->targetTemp->accept(this);
- foreach (Expr *e, s->incoming)
- e->accept(this);
- }
-
- virtual void visitConst(Const *e) { check(e); }
- virtual void visitString(IR::String *e) { check(e); }
- virtual void visitRegExp(IR::RegExp *e) { check(e); }
- virtual void visitName(Name *e) { check(e); }
- virtual void visitTemp(Temp *e) { check(e); }
- virtual void visitArgLocal(ArgLocal *e) { check(e); }
- virtual void visitClosure(Closure *e) { check(e); }
- virtual void visitConvert(Convert *e) { check(e); e->expr->accept(this); }
- virtual void visitUnop(Unop *e) { check(e); e->expr->accept(this); }
- virtual void visitBinop(Binop *e) { check(e); e->left->accept(this); e->right->accept(this); }
- virtual void visitCall(Call *e) { check(e); e->base->accept(this); check(e->args); }
- virtual void visitNew(New *e) { check(e); e->base->accept(this); check(e->args); }
- virtual void visitSubscript(Subscript *e) { check(e); e->base->accept(this); e->index->accept(this); }
- virtual void visitMember(Member *e) { check(e); e->base->accept(this); }
-
- void check(ExprList *l)
+ STMT_VISIT_ALL_KINDS(s);
+ }
+
+ void visit(Expr *e)
{
- for (ExprList *it = l; it; it = it->next)
- check(it->expr);
+ check(e);
+ EXPR_VISIT_ALL_KINDS(e);
}
private:
@@ -4833,7 +5011,7 @@ static void verifyNoPointerSharing(IR::Function *function)
V(function);
}
-class RemoveLineNumbers: public SideEffectsChecker, public StmtVisitor
+class RemoveLineNumbers: private SideEffectsChecker
{
public:
static void run(IR::Function *function)
@@ -4851,28 +5029,99 @@ public:
}
private:
+ ~RemoveLineNumbers() {}
+
static bool hasSideEffects(Stmt *stmt)
{
RemoveLineNumbers checker;
- stmt->accept(&checker);
+ if (auto e = stmt->asExp()) {
+ checker.visit(e->expr);
+ } else if (auto m = stmt->asMove()) {
+ checker.visit(m->source);
+ if (!checker.seenSideEffects()) {
+ checker.visit(m->target);
+ }
+ } else if (auto c = stmt->asCJump()) {
+ checker.visit(c->cond);
+ } else if (auto r = stmt->asRet()) {
+ checker.visit(r->expr);
+ }
return checker.seenSideEffects();
}
- void visitExp(Exp *s) Q_DECL_OVERRIDE { s->expr->accept(this); }
- void visitMove(Move *s) Q_DECL_OVERRIDE { s->source->accept(this); s->target->accept(this); }
- void visitJump(Jump *) Q_DECL_OVERRIDE {}
- void visitCJump(CJump *s) Q_DECL_OVERRIDE { s->cond->accept(this); }
- void visitRet(Ret *s) Q_DECL_OVERRIDE { s->expr->accept(this); }
- void visitPhi(Phi *) Q_DECL_OVERRIDE {}
+ void visitTemp(Temp *) Q_DECL_OVERRIDE Q_DECL_FINAL {}
};
+void mergeBasicBlocks(IR::Function *function, DefUses *du, DominatorTree *dt)
+{
+ enum { DebugBlockMerging = 0 };
+
+ if (function->hasTry)
+ return;
+
+ showMeTheCode(function, "Before basic block merging");
+
+ // Now merge a basic block with its successor when there is one outgoing edge, and the
+ // successor has one incoming edge.
+ for (int i = 0, ei = function->basicBlockCount(); i != ei; ++i) {
+ BasicBlock *bb = function->basicBlock(i);
+
+ bb->nextLocation = QQmlJS::AST::SourceLocation(); // make sure appendStatement doesn't mess with the line info
+
+ if (bb->isRemoved()) continue; // the block has been removed, so ignore it
+ if (bb->out.size() != 1) continue; // more than one outgoing edge
+ BasicBlock *successor = bb->out.first();
+ if (successor->in.size() != 1) continue; // more than one incoming edge
+
+ // Loop header? No efficient way to update the other blocks that refer to this as containing group,
+ // so don't do merging yet.
+ if (successor->isGroupStart()) continue;
+
+ // Ok, we can merge the two basic blocks.
+ if (DebugBlockMerging) {
+ qDebug("Merging L%d into L%d", successor->index(), bb->index());
+ }
+ Q_ASSERT(bb->terminator()->asJump());
+ bb->removeStatement(bb->statementCount() - 1); // remove the terminator, and replace it with:
+ for (Stmt *s : successor->statements()) {
+ bb->appendStatement(s); // add all statements from the successor to the current basic block
+ if (auto cjump = s->asCJump())
+ cjump->parent = bb;
+ }
+ bb->out = successor->out; // set the outgoing edges to the successor's so they're now in sync with our new terminator
+ for (auto newSuccessor : bb->out) {
+ for (auto &backlink : newSuccessor->in) {
+ if (backlink == successor) {
+ backlink = bb; // for all successors of our successor: set the incoming edges to come from bb, because we'll now jump there.
+ }
+ }
+ }
+ if (du) {
+ // all statements in successor have moved to bb, so make sure that the containing blocks
+ // stored in DefUses get updated (meaning: point to bb)
+ du->replaceBasicBlock(successor, bb);
+ }
+ if (dt) {
+ // update the immediate dominators to: any block that was dominated by the successor
+ // will now need to point to bb's immediate dominator. The reason is that bb itself
+ // won't be anyones immediate dominator, because it had just one outgoing edge.
+ dt->mergeIntoPredecessor(successor);
+ }
+ function->removeBasicBlock(successor);
+ --i; // re-run on the current basic-block, so any chain gets collapsed.
+ }
+
+ showMeTheCode(function, "After basic block merging");
+ verifyCFG(function);
+}
+
} // anonymous namespace
void LifeTimeInterval::setFrom(int from) {
Q_ASSERT(from > 0);
if (_ranges.isEmpty()) { // this is the case where there is no use, only a define
- _ranges.push_front(Range(from, from));
+ _ranges.prepend(Range(from, from));
if (_end == InvalidPosition)
_end = from;
} else {
@@ -4886,7 +5135,7 @@ void LifeTimeInterval::addRange(int from, int to) {
Q_ASSERT(to >= from);
if (_ranges.isEmpty()) {
- _ranges.push_front(Range(from, to));
+ _ranges.prepend(Range(from, to));
_end = to;
return;
}
@@ -4901,12 +5150,12 @@ void LifeTimeInterval::addRange(int from, int to) {
break;
p1->start = qMin(p->start, p1->start);
p1->end = qMax(p->end, p1->end);
- _ranges.pop_front();
+ _ranges.remove(0);
p = &_ranges.first();
}
} else {
if (to < p->start) {
- _ranges.push_front(Range(from, to));
+ _ranges.prepend(Range(from, to));
} else {
Q_ASSERT(from > _ranges.last().end);
_ranges.push_back(Range(from, to));
@@ -4947,7 +5196,7 @@ LifeTimeInterval LifeTimeInterval::split(int atPosition, int newStart)
}
if (newInterval._ranges.first().end == atPosition)
- newInterval._ranges.removeFirst();
+ newInterval._ranges.remove(0);
if (newStart == InvalidPosition) {
// the temp stays inactive for the rest of its lifetime
@@ -4967,7 +5216,7 @@ LifeTimeInterval LifeTimeInterval::split(int atPosition, int newStart)
break;
} else {
// the temp stays inactive for this interval, so remove it.
- newInterval._ranges.removeFirst();
+ newInterval._ranges.remove(0);
}
}
Q_ASSERT(!newInterval._ranges.isEmpty());
@@ -4998,15 +5247,6 @@ void LifeTimeInterval::dump(QTextStream &out) const {
out << " (register " << _reg << ")";
}
-bool LifeTimeInterval::lessThan(const LifeTimeInterval *r1, const LifeTimeInterval *r2) {
- if (r1->_ranges.first().start == r2->_ranges.first().start) {
- if (r1->isSplitFromInterval() == r2->isSplitFromInterval())
- return r1->_ranges.last().end < r2->_ranges.last().end;
- else
- return r1->isSplitFromInterval();
- } else
- return r1->_ranges.first().start < r2->_ranges.first().start;
-}
bool LifeTimeInterval::lessThanForTemp(const LifeTimeInterval *r1, const LifeTimeInterval *r2)
{
@@ -5100,6 +5340,8 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine, bool doTypeInference, bool pee
if (!function->hasTry && !function->hasWith && !function->module->debugMode && doSSA && statementCount <= 300) {
// qout << "SSA for " << (function->name ? qPrintable(*function->name) : "<anonymous>") << endl;
+ mergeBasicBlocks(function, nullptr, nullptr);
+
ConvertArgLocals(function).toTemps();
showMeTheCode(function, "After converting arguments to locals");
@@ -5175,6 +5417,7 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine, bool doTypeInference, bool pee
}
verifyNoPointerSharing(function);
+ mergeBasicBlocks(function, &defUses, &df);
// Basic-block cycles that are unreachable (i.e. for loops in a then-part where the
// condition is calculated to be always false) are not yet removed. This will choke the
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-07 04:16:46 +0000