From 8d0d1b11e381130dec12f46b959c3107c3f47160 Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Thu, 6 Apr 2017 15:42:51 +0200 Subject: V4: Fix issues with very small loops 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 --- src/qml/compiler/qv4jsir.cpp | 4 - src/qml/compiler/qv4jsir_p.h | 1 - src/qml/compiler/qv4ssa.cpp | 336 +++++++++++---------- tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml | 14 + .../auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp | 10 + 5 files changed, 208 insertions(+), 157 deletions(-) create mode 100644 tests/auto/qml/qqmlecmascript/data/qtbug_59012.qml 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 &scheduled) Q_ASSERT(!_allBasicBlocks); _allBasicBlocks = new QVector(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 &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 &backedges) { loopHead->markAsGroupStart(); + LoopInfo *info = new LoopInfo; + info->loopHeader = loopHead; + loopInfos.append(info); std::vector 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 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 stmts; + QSet 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 stmts; - QSet 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 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 obj(component.create()); + QVERIFY(obj != 0); + QVERIFY(!component.isError()); +} + QTEST_MAIN(tst_qqmlecmascript) #include "tst_qqmlecmascript.moc" -- cgit v1.2.3