From d74927cf5d6b6601e9ac01c22475c2cbe07f1a0e Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Wed, 14 May 2014 14:44:27 +0200 Subject: V4 RegAlloc: change life-time intervals from closed to half-open. There are two changes in this patch, that go hand-in-hand. First, when re-numbering the statements in order of occurrence in the scheduled basic-blocks, the (new) position is not stored in the statement itself, but in the LifeTimeIntervals class. This makes it possible to re-use information gathered during SSA formation or optimization. The re-numbering itself has also changed, resulting in some minor changes to the life-time interval calculation. The new numbering is described in LifeTimeIntervals::renumber(). The reason is to make it easy for the register allocator and stack-slot allocator to distinguish between definition of a temporary and its uses. Example: 20: %3 = %2 + %1 22: print(%3) If the life-time of %2 or %1 ends at 20, then at the point that %3 gets assigned, it can re-use the storage occupied by %1 or %2. Also, when both %1 and %2 need to get a register assigned (because they were spilled to the stack, for example), %3 should be allocated "after" both %1 and %2. So, instead of having a closed interval of [20-22] for %3, we want to use an open interval of (20-22]. To simulate the "open" part, the life-time of %3 is set to [21-22]. So, all statements live on even positions, and temporaries defined by a statement start at statmentPosition + 1. Change-Id: I0eda2c653b0edf1a529bd0762d338b0ea9a66aa0 Sanity-Review: Qt Sanity Bot Reviewed-by: Lars Knoll --- src/qml/compiler/qv4isel_moth.cpp | 13 +- src/qml/compiler/qv4jsir.cpp | 9 +- src/qml/compiler/qv4jsir_p.h | 1 + src/qml/compiler/qv4ssa.cpp | 86 ++++++-- src/qml/compiler/qv4ssa_p.h | 20 +- src/qml/jit/qv4regalloc.cpp | 395 +++++++++++++++++++---------------- src/qml/jit/qv4regalloc_p.h | 4 +- tests/auto/qml/v4misc/tst_v4misc.cpp | 2 +- 8 files changed, 310 insertions(+), 220 deletions(-) diff --git a/src/qml/compiler/qv4isel_moth.cpp b/src/qml/compiler/qv4isel_moth.cpp index 18877565da..c684aa3e79 100644 --- a/src/qml/compiler/qv4isel_moth.cpp +++ b/src/qml/compiler/qv4isel_moth.cpp @@ -174,7 +174,12 @@ class AllocateStackSlots: protected ConvertTemps QBitArray _slotIsInUse; IR::Function *_function; - int position(IR::Stmt *s) const + int defPosition(IR::Stmt *s) const + { + return usePosition(s) + 1; + } + + int usePosition(IR::Stmt *s) const { return _intervals->positionForStatement(s); } @@ -222,8 +227,6 @@ protected: virtual void process(IR::Stmt *s) { - Q_ASSERT(position(s) > 0); - // qDebug("L%d statement %d:", _currentBasicBlock->index, s->id); if (IR::Phi *phi = s->asPhi()) { @@ -232,7 +235,7 @@ protected: // purge ranges no longer alive: for (int i = 0; i < _live.size(); ) { const IR::LifeTimeInterval *lti = _live.at(i); - if (lti->end() < position(s)) { + if (lti->end() < usePosition(s)) { // qDebug() << "\t - moving temp" << lti->temp().index << "to handled, freeing slot" << _stackSlotForTemp[lti->temp().index]; _live.remove(i); Q_ASSERT(_slotIsInUse[_stackSlotForTemp[lti->temp().index]]); @@ -246,7 +249,7 @@ protected: // active new ranges: while (!_unhandled.isEmpty()) { IR::LifeTimeInterval *lti = _unhandled.last(); - if (lti->start() > position(s)) + if (lti->start() > defPosition(s)) break; // we're done Q_ASSERT(!_stackSlotForTemp.contains(lti->temp().index)); _stackSlotForTemp[lti->temp().index] = allocateFreeSlot(); diff --git a/src/qml/compiler/qv4jsir.cpp b/src/qml/compiler/qv4jsir.cpp index 6b309cc282..9a1a8bab42 100644 --- a/src/qml/compiler/qv4jsir.cpp +++ b/src/qml/compiler/qv4jsir.cpp @@ -956,8 +956,7 @@ void IRPrinter::print(BasicBlock *bb) QTextStream os(&buf); QTextStream *prevOut = &os; std::swap(out, prevOut); - if (s->id() >= 0) - *out << s->id() << ": "; + addStmtNr(s); s->accept(this); if (s->location.isValid()) { out->flush(); @@ -1226,6 +1225,12 @@ QString IRPrinter::escape(const QString &s) return r; } +void IRPrinter::addStmtNr(Stmt *s) +{ + if (s->id() >= 0) + *out << s->id() << ": "; +} + QString IRPrinter::dumpStart(const Expr *e) { if (e->type == UnknownType) diff --git a/src/qml/compiler/qv4jsir_p.h b/src/qml/compiler/qv4jsir_p.h index 0582a1a0ee..9dd113efc4 100644 --- a/src/qml/compiler/qv4jsir_p.h +++ b/src/qml/compiler/qv4jsir_p.h @@ -1174,6 +1174,7 @@ public: static QString escape(const QString &s); protected: + virtual void addStmtNr(Stmt *s); QString dumpStart(const Expr *e); const char *dumpEnd(const Expr *e); void printBlockStart(BasicBlock *bb); diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index 89909fbbbf..64f0cde9fe 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -3497,7 +3497,7 @@ void optimizeSSA(StatementWorklist &W, DefUses &defUses, DominatorTree &df) W.applyToFunction(); } -// TODO: replace this class by DefUses +//### TODO: use DefUses from the optimizer, because it already has all this information class InputOutputCollector: protected StmtVisitor, protected ExprVisitor { void setOutput(Temp *out) { @@ -3566,11 +3566,7 @@ protected: * Linear Scan Register Allocation on SSA Form * Christian Wimmer & Michael Franz, CGO'10, April 24-28, 2010 * - * There is one slight difference w.r.t. the phi-nodes: in the artice, the phi nodes are attached - * to the basic-blocks. Therefore, in the algorithm in the article, the ranges for input parameters - * for phi nodes run from their definition upto the branch instruction into the block with the phi - * node. In our representation, phi nodes are mostly treaded as normal instructions, so we have to - * enlarge the range to cover the phi node itself. + * See LifeTimeIntervals::renumber for details on the numbering. */ class LifeRanges { typedef QSet LiveRegs; @@ -3589,7 +3585,12 @@ class LifeRanges { return *lti; } - int position(IR::Stmt *s) const + int defPosition(IR::Stmt *s) const + { + return usePosition(s) + 1; + } + + int usePosition(IR::Stmt *s) const { return _sortedIntervals->positionForStatement(s); } @@ -3676,7 +3677,7 @@ private: LiveRegs::iterator it = live.find(*phi->targetTemp); if (it == live.end()) { // a phi node target that is only defined, but never used - interval(phi->targetTemp).setFrom(position(s)); + interval(phi->targetTemp).setFrom(start(bb)); } else { live.erase(it); } @@ -3684,22 +3685,24 @@ private: continue; } collector.collect(s); + //### TODO: use DefUses from the optimizer, because it already has all this information if (Temp *opd = collector.output) { LifeTimeInterval <i = interval(opd); - lti.setFrom(position(s)); + lti.setFrom(defPosition(s)); live.remove(lti.temp()); _sortedIntervals->add(<i); } + //### TODO: use DefUses from the optimizer, because it already has all this information for (unsigned i = 0, ei = collector.inputs.size(); i != ei; ++i) { Temp *opd = collector.inputs[i]; - interval(opd).addRange(start(bb), position(s)); + interval(opd).addRange(start(bb), usePosition(s)); live.insert(*opd); } } 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), position(loopEnd->terminator())); + interval(&opd).addRange(start(bb), usePosition(loopEnd->terminator())); } _liveIn[bb->index()] = live; @@ -3802,7 +3805,7 @@ void LifeTimeInterval::setFrom(int from) { if (_ranges.isEmpty()) { // this is the case where there is no use, only a define _ranges.push_front(Range(from, from)); - if (_end == Invalid) + if (_end == InvalidPosition) _end = from; } else { _ranges.first().start = from; @@ -3847,7 +3850,7 @@ void LifeTimeInterval::addRange(int from, int to) { LifeTimeInterval LifeTimeInterval::split(int atPosition, int newStart) { - Q_ASSERT(atPosition < newStart || newStart == Invalid); + Q_ASSERT(atPosition < newStart || newStart == InvalidPosition); if (_ranges.isEmpty() || atPosition < _ranges.first().start) return LifeTimeInterval(); @@ -3876,7 +3879,7 @@ LifeTimeInterval LifeTimeInterval::split(int atPosition, int newStart) if (newInterval._ranges.first().end == atPosition) newInterval._ranges.removeFirst(); - if (newStart == Invalid) { + if (newStart == InvalidPosition) { // the temp stays inactive for the rest of its lifetime newInterval = LifeTimeInterval(); } else { @@ -3921,7 +3924,7 @@ void LifeTimeInterval::dump(QTextStream &out) const { if (i > 0) out << ", "; out << _ranges[i].start << " - " << _ranges[i].end; } - if (_reg != Invalid) + if (_reg != InvalidRegister) out << " (register " << _reg << ")"; } @@ -3943,20 +3946,59 @@ bool LifeTimeInterval::lessThanForTemp(const LifeTimeInterval *r1, const LifeTim LifeTimeIntervals::LifeTimeIntervals(IR::Function *function) : _basicBlockPosition(function->basicBlockCount()) , _positionForStatement(function->statementCount(), IR::Stmt::InvalidId) + , _lastPosition(0) { - _intervals.reserve(function->tempCount + 32); + _intervals.reserve(function->tempCount + 32); // we reserve a bit more space for intervals, because the register allocator will add intervals with fixed ranges for each register. + renumber(function); +} - int id = 1; +// Renumbering works as follows: +// - phi statements are not numbered +// - statement numbers start at 0 (zero) and increment get an even number (lastPosition + 2) +// - basic blocks start at firstStatementNumber - 1, or rephrased: lastPosition + 1 +// - basic blocks end at the number of the last statement +// And during life-time calculation the next rule is used: +// - any temporary starts its life-time at definingStatementPosition + 1 +// +// This numbering simulates half-open intervals. For example: +// 0: %1 = 1 +// 2: %2 = 2 +// 4: %3 = %1 + %2 +// 6: print(%3) +// Here the half-open life-time intervals would be: +// %1: (0-4] +// %2: (2-4] +// %3: (4-6] +// Instead, we use the even statement positions for uses of temporaries, and the odd positions for +// their definitions: +// %1: [1-4] +// %2: [3-4] +// %3: [5-6] +// This has the nice advantage that placing %3 (for example) is really easy: the start will +// never overlap with the end of the uses of the operands used in the defining statement. +// +// The reason to start a basic-block at firstStatementPosition - 1 is to have correct start +// positions for target temporaries of phi-nodes. Those temporaries will now start before the +// first statement. This also means that any moves that get generated when transforming out of SSA +// form, will not interfere with (read: overlap) any defining statements in the preceding +// basic-block. +void LifeTimeIntervals::renumber(IR::Function *function) +{ foreach (BasicBlock *bb, function->basicBlocks()) { - _basicBlockPosition[bb->index()].start = id; + if (bb->isRemoved()) + continue; + + _basicBlockPosition[bb->index()].start = _lastPosition + 1; foreach (Stmt *s, bb->statements()) { - _positionForStatement[s->id()] = id; - if (!s->asPhi()) - ++id; + if (s->asPhi()) + continue; + + _lastPosition += 2; + _positionForStatement[s->id()] = _lastPosition; } - _basicBlockPosition[bb->index()].end = id - 1; + _basicBlockPosition[bb->index()].end = _lastPosition; } } diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h index 598b801cdd..95e22ff0b9 100644 --- a/src/qml/compiler/qv4ssa_p.h +++ b/src/qml/compiler/qv4ssa_p.h @@ -58,7 +58,7 @@ public: int start; int end; - Range(int start = Invalid, int end = Invalid) + Range(int start = InvalidPosition, int end = InvalidPosition) : start(start) , end(end) {} @@ -76,16 +76,17 @@ private: unsigned _isSplitFromInterval : 1; public: - enum { Invalid = -1 }; + enum { InvalidPosition = -1 }; + enum { InvalidRegister = -1 }; explicit LifeTimeInterval(int rangeCapacity = 2) - : _end(Invalid) - , _reg(Invalid) + : _end(InvalidPosition) + , _reg(InvalidRegister) , _isFixedInterval(0) , _isSplitFromInterval(0) { _ranges.reserve(rangeCapacity); } - bool isValid() const { return _end != Invalid; } + bool isValid() const { return _end != InvalidRegister; } void setTemp(const Temp &temp) { this->_temp = temp; } Temp temp() const { return _temp; } @@ -125,7 +126,7 @@ public: void validate() const { #if !defined(QT_NO_DEBUG) // Validate the new range - if (_end != Invalid) { + if (_end != InvalidPosition) { Q_ASSERT(!_ranges.isEmpty()); foreach (const Range &range, _ranges) { Q_ASSERT(range.start >= 0); @@ -142,6 +143,7 @@ class LifeTimeIntervals Q_DISABLE_COPY(LifeTimeIntervals) LifeTimeIntervals(IR::Function *function); + void renumber(IR::Function *function); public: typedef QSharedPointer Ptr; @@ -186,6 +188,11 @@ public: return _basicBlockPosition.at(bb->index()).end; } + int lastPosition() const + { + return _lastPosition; + } + private: struct BasicBlockPositions { int start; @@ -200,6 +207,7 @@ private: std::vector _basicBlockPosition; std::vector _positionForStatement; QVector _intervals; + int _lastPosition; }; class Q_QML_PRIVATE_EXPORT Optimizer diff --git a/src/qml/jit/qv4regalloc.cpp b/src/qml/jit/qv4regalloc.cpp index 36c5761dbc..d2e10bf123 100644 --- a/src/qml/jit/qv4regalloc.cpp +++ b/src/qml/jit/qv4regalloc.cpp @@ -68,38 +68,71 @@ using namespace QV4::IR; namespace QV4 { namespace JIT { +namespace { +class IRPrinterWithPositions: public IRPrinter +{ + LifeTimeIntervals::Ptr intervals; + const int positionSize; + +public: + IRPrinterWithPositions(QTextStream *out, const LifeTimeIntervals::Ptr &intervals) + : IRPrinter(out) + , intervals(intervals) + , positionSize(QString::number(intervals->lastPosition()).size()) + {} + +protected: + void addStmtNr(Stmt *s) + { + QString posStr; + int pos = intervals->positionForStatement(s); + if (pos != Stmt::InvalidId) + posStr = QString::number(pos); + *out << posStr.rightJustified(positionSize); + if (pos == Stmt::InvalidId) + *out << " "; + else + *out << ": "; + } +}; +} + class RegAllocInfo: public IRDecoder { struct Def { - unsigned defStmt : 30; + unsigned valid : 1; unsigned canHaveReg : 1; unsigned isPhiTarget : 1; - Def(): defStmt(0), canHaveReg(0), isPhiTarget(0) {} - Def(int defStmt, bool canHaveReg, bool isPhiTarget) - : defStmt(defStmt), canHaveReg(canHaveReg), isPhiTarget(isPhiTarget) + Def(): valid(0), canHaveReg(0), isPhiTarget(0) {} + Def(bool canHaveReg, bool isPhiTarget) + : valid(1), canHaveReg(canHaveReg), isPhiTarget(isPhiTarget) { - Q_ASSERT(defStmt > 0); - Q_ASSERT(defStmt < (1 << 30)); } - bool isValid() const { return defStmt != 0; } // 0 is invalid, as stmt numbers start at 1. + bool isValid() const { return valid != 0; } }; IR::LifeTimeIntervals::Ptr _lifeTimeIntervals; + BasicBlock *_currentBB; Stmt *_currentStmt; std::vector _defs; std::vector > _uses; std::vector _calls; std::vector > _hints; - int position(Stmt *s) const + int defPosition(Stmt *s) const + { + return usePosition(s) + 1; + } + + int usePosition(Stmt *s) const { return _lifeTimeIntervals->positionForStatement(s); } public: - RegAllocInfo(): _currentStmt(0) {} + RegAllocInfo(): _currentBB(0), _currentStmt(0) {} void collect(IR::Function *function, const IR::LifeTimeIntervals::Ptr &lifeTimeIntervals) { @@ -110,8 +143,8 @@ public: _hints.resize(function->tempCount); foreach (BasicBlock *bb, function->basicBlocks()) { + _currentBB = bb; foreach (Stmt *s, bb->statements()) { - Q_ASSERT(position(s) != Stmt::InvalidId); _currentStmt = s; s->accept(this); } @@ -137,10 +170,6 @@ public: return false; } - int def(const Temp &t) const { - Q_ASSERT(_defs[t.index].isValid()); - return _defs[t.index].defStmt; - } bool canHaveRegister(const Temp &t) const { Q_ASSERT(_defs[t.index].isValid()); return _defs[t.index].canHaveReg; @@ -165,12 +194,12 @@ public: return; QTextStream qout(stdout, QIODevice::WriteOnly); - IRPrinter printer(&qout); + IRPrinterWithPositions printer(&qout, _lifeTimeIntervals); qout << "RegAllocInfo:" << endl << "Defs/uses:" << endl; for (unsigned t = 0; t < _defs.size(); ++t) { qout << "%" << t <<": " - << " def at " << _defs[t].defStmt << " (" + << " (" << (_defs[t].canHaveReg ? "can" : "can NOT") << " have a register, and " << (_defs[t].isPhiTarget ? "is" : "is NOT") @@ -648,19 +677,22 @@ private: break; } - _defs[t->index] = Def(position(_currentStmt), canHaveReg, isPhiTarget); + _defs[t->index] = Def(canHaveReg, isPhiTarget); } void addUses(Expr *e, Use::RegisterFlag flag) { - Q_ASSERT(position(_currentStmt) > 0); + int usePos = usePosition(_currentStmt); + if (usePos == Stmt::InvalidId) + usePos = _lifeTimeIntervals->startPosition(_currentBB); + Q_ASSERT(usePos > 0); if (!e) return; Temp *t = e->asTemp(); if (!t) return; if (t && t->kind == Temp::VirtualRegister) - _uses[t->index].append(Use(position(_currentStmt), flag)); + _uses[t->index].append(Use(usePosition(_currentStmt), flag)); } void addUses(ExprList *l, Use::RegisterFlag flag) @@ -671,7 +703,7 @@ private: void addCall() { - _calls.push_back(position(_currentStmt)); + _calls.push_back(usePosition(_currentStmt)); } void addHint(Expr *hinted, Temp *hint1, Temp *hint2 = 0) @@ -709,9 +741,6 @@ class ResolutionPhase: protected StmtVisitor, protected ExprVisitor { LifeTimeIntervals::Ptr _intervals; QVector _unprocessed; IR::Function *_function; -#if !defined(QT_NO_DEBUG) - RegAllocInfo *_info; -#endif const std::vector &_assignedSpillSlots; QHash _intervalForTemp; const QVector &_intRegs; @@ -725,22 +754,15 @@ class ResolutionPhase: protected StmtVisitor, protected ExprVisitor { QHash > _liveAtEnd; public: - ResolutionPhase(const QVector &unprocessed, const LifeTimeIntervals::Ptr &intervals, IR::Function *function, RegAllocInfo *info, + ResolutionPhase(const QVector &unprocessed, const LifeTimeIntervals::Ptr &intervals, IR::Function *function, const std::vector &assignedSpillSlots, const QVector &intRegs, const QVector &fpRegs) : _intervals(intervals) , _function(function) -#if !defined(QT_NO_DEBUG) - , _info(info) -#endif , _assignedSpillSlots(assignedSpillSlots) , _intRegs(intRegs) , _fpRegs(fpRegs) { -#if defined(QT_NO_DEBUG) - Q_UNUSED(info) -#endif - _unprocessed = unprocessed; _liveAtStart.reserve(function->basicBlockCount()); _liveAtEnd.reserve(function->basicBlockCount()); @@ -748,12 +770,20 @@ public: void run() { renumber(); - Optimizer::showMeTheCode(_function); + if (DebugRegAlloc) { + QTextStream qout(stdout, QIODevice::WriteOnly); + IRPrinterWithPositions(&qout, _intervals).print(_function); + } resolve(); } private: - int position(Stmt *s) const + int defPosition(Stmt *s) const + { + return usePosition(s) + 1; + } + + int usePosition(Stmt *s) const { return _intervals->positionForStatement(s); } @@ -761,20 +791,24 @@ private: void renumber() { foreach (BasicBlock *bb, _function->basicBlocks()) { + _currentStmt = 0; + QVector statements = bb->statements(); QVector newStatements; newStatements.reserve(bb->statements().size() + 7); - bool seenFirstNonPhiStmt = false; + cleanOldIntervals(_intervals->startPosition(bb)); + addNewIntervals(_intervals->startPosition(bb)); + _liveAtStart[bb] = _intervalForTemp.values(); + for (int i = 0, ei = statements.size(); i != ei; ++i) { - _currentStmt = statements[i]; + _currentStmt = statements.at(i); _loads.clear(); _stores.clear(); - addNewIntervals(); - if (!seenFirstNonPhiStmt && !_currentStmt->asPhi()) { - seenFirstNonPhiStmt = true; - _liveAtStart[bb] = _intervalForTemp.values(); - } + if (_currentStmt->asTerminator()) + addNewIntervals(usePosition(_currentStmt)); + else + addNewIntervals(defPosition(_currentStmt)); _currentStmt->accept(this); foreach (Move *load, _loads) newStatements.append(load); @@ -786,7 +820,7 @@ private: newStatements.append(store); } - cleanOldIntervals(); + cleanOldIntervals(_intervals->endPosition(bb)); _liveAtEnd[bb] = _intervalForTemp.values(); if (DebugRegAlloc) { @@ -814,62 +848,42 @@ private: } - void activate(const LifeTimeInterval *i) + void maybeGenerateSpill(Temp *t) { - Q_ASSERT(!i->isFixedInterval()); - _intervalForTemp[i->temp()] = i; - - if (i->reg() != LifeTimeInterval::Invalid) { - // check if we need to generate spill/unspill instructions - if (i->start() == position(_currentStmt)) { - if (i->isSplitFromInterval()) { - int pReg = platformRegister(*i); - _loads.append(generateUnspill(i->temp(), pReg)); - } else { - int pReg = platformRegister(*i); - int spillSlot = _assignedSpillSlots[i->temp().index]; - if (spillSlot != -1) - _stores.append(generateSpill(spillSlot, i->temp().type, pReg)); - } - } - } + const LifeTimeInterval *i = _intervalForTemp[*t]; + if (i->reg() == LifeTimeInterval::InvalidRegister) + return; + + int pReg = platformRegister(*i); + int spillSlot = _assignedSpillSlots[i->temp().index]; + if (spillSlot != RegisterAllocator::InvalidSpillSlot) + _stores.append(generateSpill(spillSlot, i->temp().type, pReg)); } - void addNewIntervals() + void addNewIntervals(int position) { - if (Phi *phi = _currentStmt->asPhi()) { - // for phi nodes, only activate the range belonging to that node - for (int it = 0, eit = _unprocessed.size(); it != eit; ++it) { - const LifeTimeInterval *i = _unprocessed.at(it); - if (i->start() > position(_currentStmt)) - break; - if (i->temp() == *phi->targetTemp) { - activate(i); - _unprocessed.remove(it); - break; - } - } + if (position == Stmt::InvalidId) return; - } while (!_unprocessed.isEmpty()) { const LifeTimeInterval *i = _unprocessed.first(); - if (i->start() > position(_currentStmt)) + if (i->start() > position) break; - activate(i); + Q_ASSERT(!i->isFixedInterval()); + _intervalForTemp[i->temp()] = i; + qDebug()<<"-- Activating interval for temp"<temp().index; _unprocessed.removeFirst(); } } - void cleanOldIntervals() + void cleanOldIntervals(int position) { - const int id = position(_currentStmt); QMutableHashIterator it(_intervalForTemp); while (it.hasNext()) { const LifeTimeInterval *i = it.next().value(); - if (i->end() < id || i->isFixedInterval()) + if (i->end() < position || i->isFixedInterval()) it.remove(); } } @@ -882,72 +896,72 @@ private: } } + Phi *findDefPhi(const Temp &t, BasicBlock *bb) const + { + foreach (Stmt *s, bb->statements()) { + Phi *phi = s->asPhi(); + if (!phi) + return 0; + + if (*phi->targetTemp == t) + return phi; + } + + Q_UNREACHABLE(); + } + void resolveEdge(BasicBlock *predecessor, BasicBlock *successor) { if (DebugRegAlloc) { - Optimizer::showMeTheCode(_function); qDebug() << "Resolving edge" << predecessor->index() << "->" << successor->index(); + QTextStream qout(stdout, QIODevice::WriteOnly); + IRPrinterWithPositions printer(&qout, _intervals); + printer.print(predecessor); + printer.print(successor); + qout.flush(); } MoveMapping mapping; - const int predecessorEnd = position(predecessor->terminator()); // the terminator is always last and always has an id set... - Q_ASSERT(predecessorEnd > 0); // ... but we verify it anyway for good measure. - - int successorStart = -1; - foreach (Stmt *s, successor->statements()) { - if (s && position(s) != Stmt::InvalidId) { - successorStart = position(s); - break; - } - } + const int predecessorEnd = _intervals->endPosition(predecessor); + Q_ASSERT(predecessorEnd > 0); + int successorStart = _intervals->startPosition(successor); Q_ASSERT(successorStart > 0); foreach (const LifeTimeInterval *it, _liveAtStart[successor]) { - if (it->end() < successorStart) - continue; - bool isPhiTarget = false; Expr *moveFrom = 0; if (it->start() == successorStart) { - foreach (Stmt *s, successor->statements()) { - if (!s || position(s) == Stmt::InvalidId) - continue; - if (Phi *phi = s->asPhi()) { - if (*phi->targetTemp == it->temp()) { - isPhiTarget = true; - Expr *opd = phi->d->incoming[successor->in.indexOf(predecessor)]; - if (opd->asConst()) { - moveFrom = opd; - } else { - Temp *t = opd->asTemp(); - Q_ASSERT(t); - - foreach (const LifeTimeInterval *it2, _liveAtEnd[predecessor]) { - if (it2->temp() == *t - && it2->reg() != LifeTimeInterval::Invalid - && it2->covers(predecessorEnd)) { - moveFrom = createTemp(Temp::PhysicalRegister, - platformRegister(*it2), t->type); - break; - } - } - if (!moveFrom) - moveFrom = createTemp(Temp::StackSlot, - _assignedSpillSlots[t->index], - t->type); + if (Phi *phi = findDefPhi(it->temp(), successor)) { + isPhiTarget = true; + Expr *opd = phi->d->incoming[successor->in.indexOf(predecessor)]; + if (opd->asConst()) { + moveFrom = opd; + } else { + Temp *t = opd->asTemp(); + Q_ASSERT(t); + + foreach (const LifeTimeInterval *it2, _liveAtEnd[predecessor]) { + if (it2->temp() == *t + && it2->reg() != LifeTimeInterval::InvalidRegister + && it2->covers(predecessorEnd)) { + moveFrom = createTemp(Temp::PhysicalRegister, + platformRegister(*it2), t->type); + break; } } - } else { - break; + if (!moveFrom) + moveFrom = createTemp(Temp::StackSlot, + _assignedSpillSlots[t->index], + t->type); } } } else { foreach (const LifeTimeInterval *predIt, _liveAtEnd[predecessor]) { if (predIt->temp() == it->temp()) { - if (predIt->reg() != LifeTimeInterval::Invalid + if (predIt->reg() != LifeTimeInterval::InvalidRegister && predIt->covers(predecessorEnd)) { moveFrom = createTemp(Temp::PhysicalRegister, platformRegister(*predIt), predIt->temp().type); @@ -961,7 +975,7 @@ private: } } if (!moveFrom) { -#if !defined(QT_NO_DEBUG) +#if !defined(QT_NO_DEBUG) && 0 bool lifeTimeHole = false; if (it->ranges().first().start <= successorStart && it->ranges().last().end >= successorStart) lifeTimeHole = !it->covers(successorStart); @@ -998,11 +1012,11 @@ private: } Temp *moveTo; - if (it->reg() == LifeTimeInterval::Invalid || !it->covers(successorStart)) { + if (it->reg() == LifeTimeInterval::InvalidRegister || !it->covers(successorStart)) { if (!isPhiTarget) // if it->temp() is a phi target, skip it. continue; const int spillSlot = _assignedSpillSlots[it->temp().index]; - if (spillSlot == RegisterAllocator::Invalid) + if (spillSlot == RegisterAllocator::InvalidSpillSlot) continue; // it has a life-time hole here. moveTo = createTemp(Temp::StackSlot, spillSlot, it->temp().type); } else { @@ -1020,6 +1034,15 @@ private: bool insertIntoPredecessor = successor->in.size() > 1; mapping.insertMoves(insertIntoPredecessor ? predecessor : successor, _function, insertIntoPredecessor); + + if (DebugRegAlloc) { + qDebug() << ".. done, result:"; + QTextStream qout(stdout, QIODevice::WriteOnly); + IRPrinterWithPositions printer(&qout, _intervals); + printer.print(predecessor); + printer.print(successor); + qout.flush(); + } } Temp *createTemp(Temp::Kind kind, int index, Type type) const @@ -1068,7 +1091,16 @@ protected: const LifeTimeInterval *i = _intervalForTemp[*t]; Q_ASSERT(i->isValid()); - if (i->reg() != LifeTimeInterval::Invalid && i->covers(position(_currentStmt))) { + + if (_currentStmt != 0 && i->start() == usePosition(_currentStmt)) { + Q_ASSERT(i->isSplitFromInterval()); + int pReg = platformRegister(*i); + _loads.append(generateUnspill(i->temp(), pReg)); + } + + if (i->reg() != LifeTimeInterval::InvalidRegister && + (i->covers(defPosition(_currentStmt)) || + i->covers(usePosition(_currentStmt)))) { int pReg = platformRegister(*i); t->kind = Temp::PhysicalRegister; t->index = pReg; @@ -1105,11 +1137,23 @@ protected: } virtual void visitExp(Exp *s) { s->expr->accept(this); } - virtual void visitMove(Move *s) { s->source->accept(this); s->target->accept(this); } + + virtual void visitMove(Move *s) + { + if (Temp *t = s->target->asTemp()) + maybeGenerateSpill(t); + + s->source->accept(this); + s->target->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 visitPhi(Phi *) {} + virtual void visitPhi(Phi *s) + { + maybeGenerateSpill(s->targetTemp); + } }; } // anonymous namespace @@ -1129,8 +1173,8 @@ RegisterAllocator::~RegisterAllocator() void RegisterAllocator::run(IR::Function *function, const Optimizer &opt) { - _lastAssignedRegister.assign(function->tempCount, Invalid); - _assignedSpillSlots.assign(function->tempCount, Invalid); + _lastAssignedRegister.assign(function->tempCount, LifeTimeInterval::InvalidRegister); + _assignedSpillSlots.assign(function->tempCount, InvalidSpillSlot); _activeSpillSlots.resize(function->tempCount); if (DebugRegAlloc) @@ -1158,23 +1202,22 @@ void RegisterAllocator::run(IR::Function *function, const Optimizer &opt) prepareRanges(); - Optimizer::showMeTheCode(function); - linearScan(); if (DebugRegAlloc) - dump(); + dump(function); std::sort(_handled.begin(), _handled.end(), LifeTimeInterval::lessThan); - ResolutionPhase(_handled, _lifeTimeIntervals, function, _info.data(), _assignedSpillSlots, _normalRegisters, _fpRegisters).run(); + ResolutionPhase(_handled, _lifeTimeIntervals, function, _assignedSpillSlots, _normalRegisters, _fpRegisters).run(); function->tempCount = *std::max_element(_assignedSpillSlots.begin(), _assignedSpillSlots.end()) + 1; - Optimizer::showMeTheCode(function); - -#ifdef DEBUG_REGALLOC - qDebug() << "*** Finished regalloc for function" << (function->name ? qPrintable(*function->name) : "NO NAME") << "***"; -#endif // DEBUG_REGALLOC + if (DebugRegAlloc) { + qDebug() << "*** Finished regalloc for function" << (function->name ? qPrintable(*function->name) : "NO NAME") << "***"; + qDebug() << "*** Result:"; + QTextStream qout(stdout, QIODevice::WriteOnly); + IRPrinterWithPositions(&qout, _lifeTimeIntervals).print(function); + } } static inline LifeTimeInterval createFixedInterval(int rangeCount) @@ -1260,7 +1303,7 @@ void RegisterAllocator::linearScan() _handled += it; _inactive.remove(i); } else if (it->covers(position)) { - if (it->reg() != LifeTimeInterval::Invalid) { + if (it->reg() != LifeTimeInterval::InvalidRegister) { _active += it; _inactive.remove(i); } else { @@ -1281,9 +1324,9 @@ void RegisterAllocator::linearScan() if (_info->canHaveRegister(current->temp())) { tryAllocateFreeReg(*current, position); - if (current->reg() == LifeTimeInterval::Invalid) + if (current->reg() == LifeTimeInterval::InvalidRegister) allocateBlockedReg(*current, position); - if (current->reg() != LifeTimeInterval::Invalid) + if (current->reg() != LifeTimeInterval::InvalidRegister) _active += current; } else { assignSpillSlot(current->temp(), current->start(), current->end()); @@ -1327,7 +1370,7 @@ static inline bool isFP(const Temp &t) static void longestAvailableReg(int *nextUses, int nextUseCount, int ®, int &freeUntilPos_reg, int lastUse) { - reg = LifeTimeInterval::Invalid; + reg = LifeTimeInterval::InvalidRegister; freeUntilPos_reg = 0; for (int candidate = 0, candidateEnd = nextUseCount; candidate != candidateEnd; ++candidate) { @@ -1350,7 +1393,7 @@ static void longestAvailableReg(int *nextUses, int nextUseCount, int ®, int & void RegisterAllocator::tryAllocateFreeReg(LifeTimeInterval ¤t, const int position) { Q_ASSERT(!current.isFixedInterval()); - Q_ASSERT(current.reg() == LifeTimeInterval::Invalid); + Q_ASSERT(current.reg() == LifeTimeInterval::InvalidRegister); const bool needsFPReg = isFP(current.temp()); const int freeUntilPosCount = needsFPReg ? _fpRegisters.size() : _normalRegisters.size(); @@ -1377,7 +1420,7 @@ void RegisterAllocator::tryAllocateFreeReg(LifeTimeInterval ¤t, const int for (Intervals::const_iterator i = _inactive.constBegin(), ei = _inactive.constEnd(); i != ei; ++i) { const LifeTimeInterval *it = *i; if (current.isSplitFromInterval() || it->isFixedInterval()) { - if (it->isFP() == needsFPReg && it->reg() != LifeTimeInterval::Invalid) { + if (it->isFP() == needsFPReg && it->reg() != LifeTimeInterval::InvalidRegister) { const int intersectionPos = nextIntersection(current, *it, position); if (!isPhiTarget && it->isFixedInterval() && current.end() == intersectionPos) freeUntilPos[it->reg()] = qMin(freeUntilPos[it->reg()], intersectionPos + 1); @@ -1387,7 +1430,7 @@ void RegisterAllocator::tryAllocateFreeReg(LifeTimeInterval ¤t, const int } } - int reg = LifeTimeInterval::Invalid; + int reg = LifeTimeInterval::InvalidRegister; int freeUntilPos_reg = 0; foreach (const Temp &hint, _info->hints(current.temp())) { @@ -1398,7 +1441,7 @@ void RegisterAllocator::tryAllocateFreeReg(LifeTimeInterval ¤t, const int candidate = _lastAssignedRegister[hint.index]; const int end = current.end(); - if (candidate != LifeTimeInterval::Invalid) { + if (candidate != LifeTimeInterval::InvalidRegister) { if (current.isFP() == (hint.type == DoubleType)) { int fp = freeUntilPos[candidate]; if ((freeUntilPos_reg < end && fp > freeUntilPos_reg) @@ -1410,7 +1453,7 @@ void RegisterAllocator::tryAllocateFreeReg(LifeTimeInterval ¤t, const int } } - if (reg == LifeTimeInterval::Invalid) + if (reg == LifeTimeInterval::InvalidRegister) longestAvailableReg(freeUntilPos, freeUntilPosCount, reg, freeUntilPos_reg, current.end()); if (freeUntilPos_reg == 0) { @@ -1437,7 +1480,7 @@ void RegisterAllocator::tryAllocateFreeReg(LifeTimeInterval ¤t, const int void RegisterAllocator::allocateBlockedReg(LifeTimeInterval ¤t, const int position) { Q_ASSERT(!current.isFixedInterval()); - Q_ASSERT(current.reg() == LifeTimeInterval::Invalid); + Q_ASSERT(current.reg() == LifeTimeInterval::InvalidRegister); const bool isPhiTarget = _info->isPhiTarget(current.temp()); if (isPhiTarget && !current.isSplitFromInterval()) { @@ -1472,7 +1515,7 @@ void RegisterAllocator::allocateBlockedReg(LifeTimeInterval ¤t, const int for (Intervals::const_iterator i = _inactive.constBegin(), ei = _inactive.constEnd(); i != ei; ++i) { LifeTimeInterval &it = **i; if (current.isSplitFromInterval() || it.isFixedInterval()) { - if (it.isFP() == needsFPReg && it.reg() != LifeTimeInterval::Invalid) { + if (it.isFP() == needsFPReg && it.reg() != LifeTimeInterval::InvalidRegister) { if (nextIntersection(current, it, position) != -1) { int nu = nextUse(it.temp(), current.firstPossibleUsePosition(isPhiTarget)); if (nu != -1 && nu < nextUsePos[it.reg()]) { @@ -1598,18 +1641,10 @@ void RegisterAllocator::split(LifeTimeInterval ¤t, int beforePosition, assignSpillSlot(current.temp(), current.start(), current.end()); - const int defPosition = _info->def(current.temp()); - if (beforePosition < defPosition) { - if (DebugRegAlloc) { - QTextStream out(stderr, QIODevice::WriteOnly); - out << "***** split before position is before or at definition, so not splitting."< firstPosition && "split before start"); - int lastUse = -1; - if (defPosition < beforePosition) - lastUse = defPosition; + int lastUse = firstPosition; int nextUse = -1; QList usePositions = _info->uses(current.temp()); for (int i = 0, ei = usePositions.size(); i != ei; ++i) { @@ -1624,9 +1659,7 @@ void RegisterAllocator::split(LifeTimeInterval ¤t, int beforePosition, } } } - if (lastUse == -1) - lastUse = beforePosition - 1; - + Q_ASSERT(lastUse != -1); Q_ASSERT(lastUse < beforePosition); LifeTimeInterval newInterval = current.split(lastUse, nextUse); @@ -1637,9 +1670,9 @@ void RegisterAllocator::split(LifeTimeInterval ¤t, int beforePosition, out << "***** preceding interval: "; current.dump(out); out << endl; } if (newInterval.isValid()) { - if (current.reg() != LifeTimeInterval::Invalid) + if (current.reg() != LifeTimeInterval::InvalidRegister) _info->addHint(current.temp(), current.reg()); - newInterval.setReg(LifeTimeInterval::Invalid); + newInterval.setReg(LifeTimeInterval::InvalidRegister); LifeTimeInterval *newIntervalPtr = new LifeTimeInterval(newInterval); _lifeTimeIntervals->add(newIntervalPtr); insertReverseSorted(_unhandled, newIntervalPtr); @@ -1667,7 +1700,7 @@ void RegisterAllocator::splitInactiveAtEndOfLifetimeHole(int reg, bool isFPReg, void RegisterAllocator::assignSpillSlot(const Temp &t, int startPos, int endPos) { - if (_assignedSpillSlots[t.index] != Invalid) + if (_assignedSpillSlots[t.index] != InvalidSpillSlot) return; for (int i = 0, ei = _activeSpillSlots.size(); i != ei; ++i) { @@ -1681,25 +1714,23 @@ void RegisterAllocator::assignSpillSlot(const Temp &t, int startPos, int endPos) Q_UNREACHABLE(); } -void RegisterAllocator::dump() const +void RegisterAllocator::dump(IR::Function *function) const { QTextStream qout(stdout, QIODevice::WriteOnly); + IRPrinterWithPositions printer(&qout, _lifeTimeIntervals); - { - qout << "Ranges:" << endl; - QVector handled = _handled; - std::sort(handled.begin(), handled.end(), LifeTimeInterval::lessThanForTemp); - foreach (const LifeTimeInterval *r, handled) { - r->dump(qout); - qout << endl; - } + qout << "Ranges:" << endl; + QVector handled = _handled; + std::sort(handled.begin(), handled.end(), LifeTimeInterval::lessThanForTemp); + foreach (const LifeTimeInterval *r, handled) { + r->dump(qout); + qout << endl; } - { - IRPrinter printer(&qout); - qout << "Spill slots:" << endl; - for (unsigned i = 0; i < _assignedSpillSlots.size(); ++i) - if (_assignedSpillSlots[i] != Invalid) - qout << "\t%" << i << " -> " << _assignedSpillSlots[i] << endl; - } + qout << "Spill slots:" << endl; + for (unsigned i = 0; i < _assignedSpillSlots.size(); ++i) + if (_assignedSpillSlots[i] != InvalidSpillSlot) + qout << "\t%" << i << " -> " << _assignedSpillSlots[i] << endl; + + printer.print(function); } diff --git a/src/qml/jit/qv4regalloc_p.h b/src/qml/jit/qv4regalloc_p.h index ea7096ad17..020c8419e8 100644 --- a/src/qml/jit/qv4regalloc_p.h +++ b/src/qml/jit/qv4regalloc_p.h @@ -75,7 +75,7 @@ class RegisterAllocator Q_DISABLE_COPY(RegisterAllocator) public: - enum { Invalid = -1 }; + enum { InvalidSpillSlot = -1 }; RegisterAllocator(const QVector &normalRegisters, const QVector &fpRegisters); ~RegisterAllocator(); @@ -96,7 +96,7 @@ private: void assignSpillSlot(const IR::Temp &t, int startPos, int endPos); void resolve(IR::Function *function, const IR::Optimizer &opt); - void dump() const; + void dump(IR::Function *function) const; }; } // end of namespace JIT diff --git a/tests/auto/qml/v4misc/tst_v4misc.cpp b/tests/auto/qml/v4misc/tst_v4misc.cpp index 79ccdc9a4b..17f2fed3f9 100644 --- a/tests/auto/qml/v4misc/tst_v4misc.cpp +++ b/tests/auto/qml/v4misc/tst_v4misc.cpp @@ -139,7 +139,7 @@ void tst_v4misc::rangeSplitting_3() interval.validate(); QCOMPARE(interval.end(), 71); - LifeTimeInterval newInterval = interval.split(64, LifeTimeInterval::Invalid); + LifeTimeInterval newInterval = interval.split(64, LifeTimeInterval::InvalidPosition); interval.validate(); newInterval.validate(); QVERIFY(!newInterval.isValid()); -- cgit v1.2.3