summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Verbruggen <erik.verbruggen@qt.io>2017-04-06 15:42:51 +0200
committerErik Verbruggen <erik.verbruggen@qt.io>2017-04-18 07:53:48 +0000
commit8d0d1b11e381130dec12f46b959c3107c3f47160 (patch)
tree584d150a9304add12e411aff1adba88f923e34d2
parent671ada303aaa16228511eee8032778fea0b84915 (diff)
V4: Fix issues with very small loops5.8
Loops consisting of just a single basic block (e.g. a do-while loop with no nested loops or if statements) have a back-edge to themselves. There were 2 problems: - loop detection would create LoopInfo for any loop header referred to by blocks inside the loop (and a 1 block loop doesn't have body blocks), nor would it mark the loop header as such - when splitting critical edges, the newly inserted block would not be marked as part of the loop This is a problem specifically for 1 block loops: the block ends with a CJUMP, so the back-edge is a critical edge. So the new block inserted by edge splitting wouldn't be marked as belonging to the loop. The end result was that the life-time intervals for temporaries that are defined before the loop, but that are used inside the loop, and not after the loop, would have their life-time ended before the loop ends (instead of spanning the whole loop, *including* the back-edge). This in turns could lead to the stack/register allocator re-using the storage for that temporary, resulting in strange things happening. Task-number: QTBUG-59012 Change-Id: Ic946c73913711272efea2151cb85350412ca2fde Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>
-rw-r--r--src/qml/compiler/qv4jsir.cpp4
-rw-r--r--src/qml/compiler/qv4jsir_p.h1
-rw-r--r--src/qml/compiler/qv4ssa.cpp336
-rw-r--r--tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml14
-rw-r--r--tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp10
5 files changed, 208 insertions, 157 deletions
diff --git a/src/qml/compiler/qv4jsir.cpp b/src/qml/compiler/qv4jsir.cpp
index 5687834b00..1dff7c9ac3 100644
--- a/src/qml/compiler/qv4jsir.cpp
+++ b/src/qml/compiler/qv4jsir.cpp
@@ -448,10 +448,6 @@ void Function::setScheduledBlocks(const QVector<BasicBlock *> &scheduled)
Q_ASSERT(!_allBasicBlocks);
_allBasicBlocks = new QVector<BasicBlock *>(basicBlocks());
_basicBlocks = scheduled;
-}
-
-void Function::renumberBasicBlocks()
-{
for (int i = 0, ei = basicBlockCount(); i != ei; ++i)
basicBlock(i)->changeIndex(i);
}
diff --git a/src/qml/compiler/qv4jsir_p.h b/src/qml/compiler/qv4jsir_p.h
index a614d3fe1c..d55726cd0f 100644
--- a/src/qml/compiler/qv4jsir_p.h
+++ b/src/qml/compiler/qv4jsir_p.h
@@ -1347,7 +1347,6 @@ struct Function {
{ return hasDirectEval || !nestedFunctions.isEmpty() || module->debugMode; }
void setScheduledBlocks(const QVector<BasicBlock *> &scheduled);
- void renumberBasicBlocks();
int getNewStatementId() { return _statementCount++; }
int statementCount() const { return _statementCount; }
diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp
index 45ca56584f..fa4bd93eb0 100644
--- a/src/qml/compiler/qv4ssa.cpp
+++ b/src/qml/compiler/qv4ssa.cpp
@@ -3023,14 +3023,19 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w
// add newBB to the correct loop group
if (toBB->isGroupStart()) {
- BasicBlock *container;
- for (container = fromBB->containingGroup(); container; container = container->containingGroup())
- if (container == toBB)
- break;
- if (container == toBB) // if we were already inside the toBB loop
+ if (fromBB == toBB) {
+ // special case: the loop header points back to itself (so it's a small loop).
newBB->setContainingGroup(toBB);
- else
- newBB->setContainingGroup(toBB->containingGroup());
+ } else {
+ BasicBlock *container;
+ for (container = fromBB->containingGroup(); container; container = container->containingGroup())
+ if (container == toBB)
+ break;
+ if (container == toBB) // if we were already inside the toBB loop
+ newBB->setContainingGroup(toBB);
+ else
+ newBB->setContainingGroup(toBB->containingGroup());
+ }
} else {
newBB->setContainingGroup(toBB->containingGroup());
}
@@ -3061,7 +3066,7 @@ void splitCriticalEdges(IR::Function *f, DominatorTree &df, StatementWorklist &w
bool toNeedsNewIdom = true;
for (BasicBlock *bb : toBB->in) {
- if (bb != newBB && !df.dominates(toBB, bb)) {
+ if (bb != newBB && bb != toBB && !df.dominates(toBB, bb)) {
toNeedsNewIdom = false;
break;
}
@@ -3171,7 +3176,7 @@ public:
backedges.clear();
for (BasicBlock *in : bb->in)
- if (dt.dominates(bb, in))
+ if (bb == in || dt.dominates(bb, in))
backedges.push_back(in);
if (!backedges.empty()) {
@@ -3188,6 +3193,7 @@ public:
if (!DebugLoopDetection)
return;
+ qDebug() << "Found" << loopInfos.size() << "loops";
foreach (LoopInfo *info, loopInfos) {
qDebug() << "Loop header:" << info->loopHeader->index()
<< "for loop" << quint64(info);
@@ -3221,6 +3227,9 @@ private:
void subLoop(BasicBlock *loopHead, const std::vector<BasicBlock *> &backedges)
{
loopHead->markAsGroupStart();
+ LoopInfo *info = new LoopInfo;
+ info->loopHeader = loopHead;
+ loopInfos.append(info);
std::vector<BasicBlock *> worklist;
worklist.reserve(backedges.size() + 8);
@@ -3290,10 +3299,8 @@ private:
return info;
}
- LoopInfo *info = new LoopInfo;
- info->loopHeader = loopHeader;
- loopInfos.append(info);
- return info;
+ Q_UNREACHABLE();
+ return nullptr;
}
};
@@ -3323,6 +3330,8 @@ private:
// the same reason.
class BlockScheduler
{
+ enum { DebugBlockScheduler = 0 };
+
IR::Function *function;
const DominatorTree &dominatorTree;
@@ -3438,6 +3447,14 @@ class BlockScheduler
Q_UNREACHABLE();
}
+ void dumpLoopStartsEnds() const
+ {
+ qDebug() << "Found" << loopsStartEnd.size() << "loops:";
+ for (auto key : loopsStartEnd.keys())
+ qDebug("Loop starting at L%d ends at L%d.", key->index(),
+ loopsStartEnd.value(key)->index());
+ }
+
public:
BlockScheduler(IR::Function *function, const DominatorTree &dominatorTree)
: function(function)
@@ -3449,11 +3466,15 @@ public:
QHash<BasicBlock *, BasicBlock *> go()
{
showMeTheCode(function, "Before block scheduling");
+ if (DebugBlockScheduler)
+ dominatorTree.dumpImmediateDominators();
+
schedule(function->basicBlock(0));
Q_ASSERT(function->liveBasicBlocksCount() == sequence.size());
function->setScheduledBlocks(sequence);
- function->renumberBasicBlocks();
+ if (DebugBlockScheduler)
+ dumpLoopStartsEnds();
return loopsStartEnd;
}
};
@@ -4588,7 +4609,6 @@ void removeUnreachleBlocks(IR::Function *function)
if (!bb->isRemoved())
newSchedule.append(bb);
function->setScheduledBlocks(newSchedule);
- function->renumberBasicBlocks();
}
class ConvertArgLocals
@@ -4762,6 +4782,137 @@ private:
IR::Stmt *clonedStmt;
};
+static void verifyCFG(IR::Function *function)
+{
+ if (!DoVerification)
+ return;
+
+ for (BasicBlock *bb : function->basicBlocks()) {
+ if (bb->isRemoved()) {
+ Q_ASSERT(bb->in.isEmpty());
+ Q_ASSERT(bb->out.isEmpty());
+ continue;
+ }
+
+ Q_ASSERT(function->basicBlock(bb->index()) == bb);
+
+ // Check the terminators:
+ 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 = terminator->asCJump()) {
+ Q_UNUSED(cjump);
+ Q_ASSERT(bb->out.size() == 2);
+ Q_ASSERT(cjump->iftrue);
+ Q_ASSERT(!cjump->iftrue->isRemoved());
+ Q_ASSERT(cjump->iftrue == bb->out[0]);
+ Q_ASSERT(cjump->iffalse);
+ Q_ASSERT(!cjump->iffalse->isRemoved());
+ Q_ASSERT(cjump->iffalse == bb->out[1]);
+ } else if (terminator->asRet()) {
+ Q_ASSERT(bb->out.size() == 0);
+ } else {
+ Q_UNREACHABLE();
+ }
+
+ // Check the outgoing edges:
+ for (BasicBlock *out : bb->out) {
+ Q_UNUSED(out);
+ Q_ASSERT(!out->isRemoved());
+ Q_ASSERT(out->in.contains(bb));
+ }
+
+ // Check the incoming edges:
+ for (BasicBlock *in : bb->in) {
+ Q_UNUSED(in);
+ Q_ASSERT(!in->isRemoved());
+ Q_ASSERT(in->out.contains(bb));
+ }
+ }
+}
+
+static void verifyImmediateDominators(const DominatorTree &dt, IR::Function *function)
+{
+ if (!DoVerification)
+ return;
+
+ cfg2dot(function);
+ dt.dumpImmediateDominators();
+ DominatorTree referenceTree(function);
+
+ for (BasicBlock *bb : function->basicBlocks()) {
+ if (bb->isRemoved())
+ continue;
+
+ BasicBlock *idom = dt.immediateDominator(bb);
+ BasicBlock *referenceIdom = referenceTree.immediateDominator(bb);
+ Q_UNUSED(idom);
+ Q_UNUSED(referenceIdom);
+ Q_ASSERT(idom == referenceIdom);
+ }
+}
+
+static void verifyNoPointerSharing(IR::Function *function)
+{
+ if (!DoVerification)
+ return;
+
+ class {
+ public:
+ void operator()(IR::Function *f)
+ {
+ for (BasicBlock *bb : f->basicBlocks()) {
+ if (bb->isRemoved())
+ continue;
+
+ for (Stmt *s : bb->statements()) {
+ visit(s);
+ }
+ }
+ }
+
+ private:
+ void visit(Stmt *s)
+ {
+ check(s);
+ STMT_VISIT_ALL_KINDS(s);
+ }
+
+ void visit(Expr *e)
+ {
+ check(e);
+ EXPR_VISIT_ALL_KINDS(e);
+ }
+
+ private:
+ void check(Stmt *s)
+ {
+ Q_ASSERT(!stmts.contains(s));
+ stmts.insert(s);
+ }
+
+ void check(Expr *e)
+ {
+ Q_ASSERT(!exprs.contains(e));
+ exprs.insert(e);
+ }
+
+ QSet<Stmt *> stmts;
+ QSet<Expr *> exprs;
+ } V;
+ V(function);
+}
+
// Loop-peeling is done by unfolding the loop once. The "original" loop basic blocks stay where they
// are, and a copy of the loop is placed after it. Special care is taken while copying the loop body:
// by having the copies of the basic-blocks point to the same nodes as the "original" basic blocks,
@@ -4822,12 +4973,14 @@ private:
void peelLoop(LoopDetection::LoopInfo *loop)
{
+ IR::Function *f = loop->loopHeader->function;
CloneBasicBlock clone;
LoopDetection::LoopInfo unpeeled(*loop);
unpeeled.loopHeader = clone(unpeeled.loopHeader);
unpeeled.loopHeader->setContainingGroup(loop->loopHeader->containingGroup());
unpeeled.loopHeader->markAsGroupStart(true);
+ f->addBasicBlock(unpeeled.loopHeader);
for (int i = 0, ei = unpeeled.loopBody.size(); i != ei; ++i) {
BasicBlock *&bodyBlock = unpeeled.loopBody[i];
bodyBlock = clone(bodyBlock);
@@ -4841,8 +4994,8 @@ private:
BasicBlock::IncomingEdges inCopy = loop->loopHeader->in;
for (BasicBlock *in : inCopy) {
- if (unpeeled.loopHeader != in // this can happen for really tight loops (where there are no body blocks). This is a back-edge in that case.
- && !unpeeled.loopBody.contains(in) // if the edge is not coming from within the copied set, leave it alone
+ if (loop->loopHeader != in // this can happen for really tight loops (where there are no body blocks). This is a back-edge in that case.
+ && unpeeled.loopHeader != in && !unpeeled.loopBody.contains(in) // if the edge is not coming from within the copied set, leave it alone
&& !dt.dominates(loop->loopHeader, in)) // an edge coming from within the loop (so a back-edge): this is handled when rewiring all outgoing edges
continue;
@@ -4872,9 +5025,7 @@ private:
loopExits.reserve(8);
loopExits.append(unpeeled.loopHeader);
- IR::Function *f = unpeeled.loopHeader->function;
rewire(unpeeled.loopHeader, loop->loopBody, unpeeled.loopBody, loopExits);
- f->addBasicBlock(unpeeled.loopHeader);
for (int i = 0, ei = unpeeled.loopBody.size(); i != ei; ++i) {
BasicBlock *bodyBlock = unpeeled.loopBody.at(i);
rewire(bodyBlock, loop->loopBody, unpeeled.loopBody, loopExits);
@@ -4887,6 +5038,9 @@ private:
foreach (BasicBlock *bb, loop->loopBody)
bb->setContainingGroup(loop->loopHeader->containingGroup());
+ // Set the immediate dominator of the new loop header to the old one. The real immediate
+ // dominator will be calculated later.
+ dt.setImmediateDominator(unpeeled.loopHeader, loop->loopHeader);
// calculate the idoms in a separate loop, because addBasicBlock in the previous loop will
// set the block index, which in turn is used by the dominator tree.
for (int i = 0, ei = unpeeled.loopBody.size(); i != ei; ++i) {
@@ -4905,141 +5059,13 @@ private:
foreach (BasicBlock *bb, loopExits)
dt.collectSiblings(bb, siblings);
+ siblings.insert(unpeeled.loopHeader);
dt.recalculateIDoms(siblings, loop->loopHeader);
+ dt.dumpImmediateDominators();
+ verifyImmediateDominators(dt, f);
}
};
-static void verifyCFG(IR::Function *function)
-{
- if (!DoVerification)
- return;
-
- for (BasicBlock *bb : function->basicBlocks()) {
- if (bb->isRemoved()) {
- Q_ASSERT(bb->in.isEmpty());
- Q_ASSERT(bb->out.isEmpty());
- continue;
- }
-
- Q_ASSERT(function->basicBlock(bb->index()) == bb);
-
- // Check the terminators:
- 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 = terminator->asCJump()) {
- Q_UNUSED(cjump);
- Q_ASSERT(bb->out.size() == 2);
- Q_ASSERT(cjump->iftrue);
- Q_ASSERT(!cjump->iftrue->isRemoved());
- Q_ASSERT(cjump->iftrue == bb->out[0]);
- Q_ASSERT(cjump->iffalse);
- Q_ASSERT(!cjump->iffalse->isRemoved());
- Q_ASSERT(cjump->iffalse == bb->out[1]);
- } else if (terminator->asRet()) {
- Q_ASSERT(bb->out.size() == 0);
- } else {
- Q_UNREACHABLE();
- }
-
- // Check the outgoing edges:
- for (BasicBlock *out : bb->out) {
- Q_UNUSED(out);
- Q_ASSERT(!out->isRemoved());
- Q_ASSERT(out->in.contains(bb));
- }
-
- // Check the incoming edges:
- for (BasicBlock *in : bb->in) {
- Q_UNUSED(in);
- Q_ASSERT(!in->isRemoved());
- Q_ASSERT(in->out.contains(bb));
- }
- }
-}
-
-static void verifyImmediateDominators(const DominatorTree &dt, IR::Function *function)
-{
- if (!DoVerification)
- return;
-
- cfg2dot(function);
- dt.dumpImmediateDominators();
- DominatorTree referenceTree(function);
-
- for (BasicBlock *bb : function->basicBlocks()) {
- if (bb->isRemoved())
- continue;
-
- BasicBlock *idom = dt.immediateDominator(bb);
- BasicBlock *referenceIdom = referenceTree.immediateDominator(bb);
- Q_UNUSED(idom);
- Q_UNUSED(referenceIdom);
- Q_ASSERT(idom == referenceIdom);
- }
-}
-
-static void verifyNoPointerSharing(IR::Function *function)
-{
- if (!DoVerification)
- return;
-
- class {
- public:
- void operator()(IR::Function *f)
- {
- for (BasicBlock *bb : f->basicBlocks()) {
- if (bb->isRemoved())
- continue;
-
- for (Stmt *s : bb->statements()) {
- visit(s);
- }
- }
- }
-
- private:
- void visit(Stmt *s)
- {
- check(s);
- STMT_VISIT_ALL_KINDS(s);
- }
-
- void visit(Expr *e)
- {
- check(e);
- EXPR_VISIT_ALL_KINDS(e);
- }
-
- private:
- void check(Stmt *s)
- {
- Q_ASSERT(!stmts.contains(s));
- stmts.insert(s);
- }
-
- void check(Expr *e)
- {
- Q_ASSERT(!exprs.contains(e));
- exprs.insert(e);
- }
-
- QSet<Stmt *> stmts;
- QSet<Expr *> exprs;
- } V;
- V(function);
-}
-
class RemoveLineNumbers: private SideEffectsChecker
{
public:
@@ -5448,6 +5474,9 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine, bool doTypeInference, bool pee
verifyNoPointerSharing(function);
mergeBasicBlocks(function, &defUses, &df);
+ verifyImmediateDominators(df, function);
+ verifyCFG(function);
+
// 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
// block scheduling, so remove those now.
@@ -5455,10 +5484,13 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine, bool doTypeInference, bool pee
cleanupBasicBlocks(function);
// showMeTheCode(function);
+ verifyImmediateDominators(df, function);
+ verifyCFG(function);
+
// Transform the CFG into edge-split SSA.
-// qout << "Starting edge splitting..." << endl;
+ showMeTheCode(function, "Before edge splitting");
splitCriticalEdges(function, df, worklist, defUses);
-// showMeTheCode(function);
+ showMeTheCode(function, "After edge splitting");
verifyImmediateDominators(df, function);
verifyCFG(function);
diff --git a/tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml b/tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml
new file mode 100644
index 0000000000..5283614435
--- /dev/null
+++ b/tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml
@@ -0,0 +1,14 @@
+import QtQuick 2.0
+
+QtObject {
+ Component.onCompleted: {
+ var pieces = [[4,21],[6,22],[8,23],[12,24],[10,25],[8,26],[6,27],[4,28],[2,31],[2,32],[2,33],[2,35],[2,36],[2,37],[2,38],[2,54]]
+ var i = pieces.length;
+ var king = 10
+ var val
+ do {
+ var p = pieces[--i];
+ val = p[0]
+ } while (val !== king);
+ }
+}
diff --git a/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp b/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
index 20f7940e9d..068881affb 100644
--- a/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
+++ b/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
@@ -331,6 +331,7 @@ private slots:
void qtbug_54589();
void qtbug_54687();
void stringify_qtbug_50592();
+ void singleBlockLoops();
private:
// static void propertyVarWeakRefCallback(v8::Persistent<v8::Value> object, void* parameter);
@@ -8119,6 +8120,15 @@ void tst_qqmlecmascript::stringify_qtbug_50592()
QCOMPARE(obj->property("source").toString(), QString::fromLatin1("http://example.org/some_nonexistant_image.png"));
}
+void tst_qqmlecmascript::singleBlockLoops()
+{
+ QQmlComponent component(&engine, testFileUrl("qtbug_59012.qml"));
+
+ QScopedPointer<QObject> obj(component.create());
+ QVERIFY(obj != 0);
+ QVERIFY(!component.isError());
+}
+
QTEST_MAIN(tst_qqmlecmascript)
#include "tst_qqmlecmascript.moc"