From 6f0f73e63182afc92cb1b8255b114fb8f8232f22 Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Wed, 15 Jan 2014 10:46:08 +0100 Subject: V4 IR: update immediate dominators when purging unreachable basic-blocks The basic block scheduling uses this information to place loops. When the immediate dominator information is invalid, the scheduling can be sub-optimal, or will sometimes forget to schedule some blocks. Change-Id: Iaeb45f2b757b676310be25a658ceadc07d5722ec Reviewed-by: Simon Hausmann --- src/qml/compiler/qv4ssa.cpp | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) (limited to 'src/qml/compiler') diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index a668375da0..c2889a2b9a 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -695,10 +695,6 @@ public: computeDF(); } -// QSet operator[](BasicBlock *n) const { -// return DF[n->index]; -// } - const BasicBlockSet &dominatorFrontier(BasicBlock *n) const { return DF[n->index]; } @@ -707,6 +703,11 @@ public: return nodes[idom[bb->index]]; } + void updateImmediateDominator(BasicBlock *bb, BasicBlock *newDominator) + { + idom[bb->index] = newDominator->index; + } + bool dominates(BasicBlock *dominator, BasicBlock *dominated) const { // The index of the basic blocks might have changed, or the nodes array might have changed, // or the block got deleted, so get the index from our copy of the array. @@ -2895,7 +2896,8 @@ namespace { /// and removes unreachable staements from the worklist, so that optimiseSSA won't consider them /// anymore. /// Important: this assumes that there are no critical edges in the control-flow graph! -void purgeBB(BasicBlock *bb, Function *func, DefUsesCalculator &defUses, QVector &W) +void purgeBB(BasicBlock *bb, Function *func, DefUsesCalculator &defUses, QVector &W, + DominatorTree &df) { // TODO: change this to mark the block as deleted, but leave it alone so that other references // won't be dangling pointers. @@ -2945,11 +2947,15 @@ void purgeBB(BasicBlock *bb, Function *func, DefUsesCalculator &defUses, QVector } } - // if a successor has no incoming edges after unlinking the current basic block, then - // it is unreachable, and can be purged too - if (out->in.isEmpty()) + if (out->in.isEmpty()) { + // if a successor has no incoming edges after unlinking the current basic block, then + // it is unreachable, and can be purged too toPurge.append(out); - + } else if (out->in.size() == 1) { + // if the successor now has only one incoming edge, we that edge is the new + // immediate dominator + df.updateImmediateDominator(out, out->in.first()); + } } // unlink all defs/uses from the statements in the basic block @@ -3032,7 +3038,7 @@ bool tryOptimizingComparison(Expr *&expr) } } // anonymous namespace -void optimizeSSA(Function *function, DefUsesCalculator &defUses) +void optimizeSSA(Function *function, DefUsesCalculator &defUses, DominatorTree &df) { const bool variablesCanEscape = function->variablesCanEscape(); @@ -3298,10 +3304,10 @@ void optimizeSSA(Function *function, DefUsesCalculator &defUses) Jump *jump = function->New(); if (convertToValue(constantCondition).toBoolean()) { jump->target = cjump->iftrue; - purgeBB(cjump->iffalse, function, defUses, W); + purgeBB(cjump->iffalse, function, defUses, W, df); } else { jump->target = cjump->iffalse; - purgeBB(cjump->iftrue, function, defUses, W); + purgeBB(cjump->iftrue, function, defUses, W, df); } *ref[s] = jump; @@ -3681,7 +3687,7 @@ void Optimizer::run(QQmlEnginePrivate *qmlEngine) static bool doOpt = qgetenv("QV4_NO_OPT").isEmpty(); if (doOpt) { // qout << "Running SSA optimization..." << endl; - optimizeSSA(function, defUses); + optimizeSSA(function, defUses, df); // showMeTheCode(function); } -- cgit v1.2.3