From a03a6499ab64da2003d2d8a4691ea89606af1f8b Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Thu, 16 Jan 2014 14:55:41 +0100 Subject: V4: lower memory allocator pressure. Changes to datastructures and more re-using of locally used temporary vectors. For the test regress-74474-002.js this lowers the total allocated memory from 1.98GB to 158MB. Thse peak memory usage stays at 75MB. There is no functional change. This should give a modest performance improvement which mainly depends on the speed of malloc()/free(). Change-Id: I1877c1903e59a33ee79ff2b801ef6f2c1cee30a6 Reviewed-by: Simon Hausmann --- src/qml/compiler/qv4regalloc.cpp | 141 +++++++++++++++++++++------------------ src/qml/compiler/qv4ssa.cpp | 30 +++++---- src/qml/compiler/qv4ssa_p.h | 1 + 3 files changed, 95 insertions(+), 77 deletions(-) (limited to 'src/qml') diff --git a/src/qml/compiler/qv4regalloc.cpp b/src/qml/compiler/qv4regalloc.cpp index 5597759ee1..df1687f267 100644 --- a/src/qml/compiler/qv4regalloc.cpp +++ b/src/qml/compiler/qv4regalloc.cpp @@ -124,7 +124,7 @@ public: return _defs[t].isPhiTarget; } - QList calls() const { return _calls; } + const QList &calls() const { return _calls; } QList hints(const Temp &t) const { return _hints[t]; } void addHint(const Temp &t, int physicalRegister) { @@ -658,13 +658,14 @@ using namespace QT_PREPEND_NAMESPACE(QQmlJS); namespace { class ResolutionPhase: protected StmtVisitor, protected ExprVisitor { - QVector _intervals; + const QVector &_intervals; + QVector _unprocessed; Function *_function; #if !defined(QT_NO_DEBUG) RegAllocInfo *_info; #endif const QHash &_assignedSpillSlots; - QHash _intervalForTemp; + QHash _intervalForTemp; const QVector &_intRegs; const QVector &_fpRegs; @@ -672,8 +673,8 @@ class ResolutionPhase: protected StmtVisitor, protected ExprVisitor { QVector _loads; QVector _stores; - QHash > _liveAtStart; - QHash > _liveAtEnd; + QHash > _liveAtStart; + QHash > _liveAtEnd; public: ResolutionPhase(const QVector &intervals, Function *function, RegAllocInfo *info, @@ -691,6 +692,13 @@ public: #if defined(QT_NO_DEBUG) Q_UNUSED(info) #endif + + _unprocessed.resize(_intervals.size()); + for (int i = 0, ei = _intervals.size(); i != ei; ++i) + _unprocessed[i] = &_intervals[i]; + + _liveAtStart.reserve(function->basicBlocks.size()); + _liveAtEnd.reserve(function->basicBlocks.size()); } void run() { @@ -704,6 +712,7 @@ private: { foreach (BasicBlock *bb, _function->basicBlocks) { QVector newStatements; + newStatements.reserve(bb->statements.size() + 7); bool seenFirstNonPhiStmt = false; for (int i = 0, ei = bb->statements.size(); i != ei; ++i) { @@ -754,22 +763,22 @@ private: } - void activate(const LifeTimeInterval &i) + void activate(const LifeTimeInterval *i) { - Q_ASSERT(!i.isFixedInterval()); - _intervalForTemp[i.temp()] = i; + Q_ASSERT(!i->isFixedInterval()); + _intervalForTemp[i->temp()] = i; - if (i.reg() != LifeTimeInterval::Invalid) { + if (i->reg() != LifeTimeInterval::Invalid) { // check if we need to generate spill/unspill instructions - if (i.start() == _currentStmt->id) { - if (i.isSplitFromInterval()) { - int pReg = platformRegister(i); - _loads.append(generateUnspill(i.temp(), pReg)); + if (i->start() == _currentStmt->id) { + if (i->isSplitFromInterval()) { + int pReg = platformRegister(*i); + _loads.append(generateUnspill(i->temp(), pReg)); } else { - int pReg = platformRegister(i); - int spillSlot = _assignedSpillSlots.value(i.temp(), -1); + int pReg = platformRegister(*i); + int spillSlot = _assignedSpillSlots.value(i->temp(), -1); if (spillSlot != -1) - _stores.append(generateSpill(spillSlot, i.temp().type, pReg)); + _stores.append(generateSpill(spillSlot, i->temp().type, pReg)); } } } @@ -779,37 +788,37 @@ private: { if (Phi *phi = _currentStmt->asPhi()) { // for phi nodes, only activate the range belonging to that node - for (int it = 0, eit = _intervals.size(); it != eit; ++it) { - const LifeTimeInterval &i = _intervals.at(it); - if (i.start() > _currentStmt->id) + for (int it = 0, eit = _unprocessed.size(); it != eit; ++it) { + const LifeTimeInterval *i = _unprocessed.at(it); + if (i->start() > _currentStmt->id) break; - if (i.temp() == *phi->targetTemp) { + if (i->temp() == *phi->targetTemp) { activate(i); - _intervals.remove(it); + _unprocessed.remove(it); break; } } return; } - while (!_intervals.isEmpty()) { - const LifeTimeInterval &i = _intervals.first(); - if (i.start() > _currentStmt->id) + while (!_unprocessed.isEmpty()) { + const LifeTimeInterval *i = _unprocessed.first(); + if (i->start() > _currentStmt->id) break; activate(i); - _intervals.removeFirst(); + _unprocessed.removeFirst(); } } void cleanOldIntervals() { const int id = _currentStmt->id; - QMutableHashIterator it(_intervalForTemp); + QMutableHashIterator it(_intervalForTemp); while (it.hasNext()) { - const LifeTimeInterval &i = it.next().value(); - if (i.end() < id || i.isFixedInterval()) + const LifeTimeInterval *i = it.next().value(); + if (i->end() < id || i->isFixedInterval()) it.remove(); } } @@ -844,20 +853,20 @@ private: Q_ASSERT(successorStart > 0); - foreach (const LifeTimeInterval &it, _liveAtStart[successor]) { - if (it.end() < successorStart) + foreach (const LifeTimeInterval *it, _liveAtStart[successor]) { + if (it->end() < successorStart) continue; bool lifeTimeHole = false; bool isPhiTarget = false; Expr *moveFrom = 0; - if (it.start() == successorStart) { + if (it->start() == successorStart) { foreach (Stmt *s, successor->statements) { if (!s || s->id < 1) continue; if (Phi *phi = s->asPhi()) { - if (*phi->targetTemp == it.temp()) { + if (*phi->targetTemp == it->temp()) { isPhiTarget = true; Expr *opd = phi->d->incoming[successor->in.indexOf(predecessor)]; if (opd->asConst()) { @@ -866,12 +875,12 @@ private: Temp *t = opd->asTemp(); Q_ASSERT(t); - foreach (const LifeTimeInterval &it2, _liveAtEnd[predecessor]) { - if (it2.temp() == *t - && it2.reg() != LifeTimeInterval::Invalid - && it2.covers(predecessorEnd)) { + 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); + platformRegister(*it2), t->type); break; } } @@ -886,18 +895,18 @@ private: } } } else { - foreach (const LifeTimeInterval &predIt, _liveAtEnd[predecessor]) { - if (predIt.temp() == it.temp()) { - if (predIt.reg() != LifeTimeInterval::Invalid - && predIt.covers(predecessorEnd)) { - moveFrom = createTemp(Temp::PhysicalRegister, platformRegister(predIt), - predIt.temp().type); + foreach (const LifeTimeInterval *predIt, _liveAtEnd[predecessor]) { + if (predIt->temp() == it->temp()) { + if (predIt->reg() != LifeTimeInterval::Invalid + && predIt->covers(predecessorEnd)) { + moveFrom = createTemp(Temp::PhysicalRegister, platformRegister(*predIt), + predIt->temp().type); } else { - int spillSlot = _assignedSpillSlots.value(predIt.temp(), -1); + int spillSlot = _assignedSpillSlots.value(predIt->temp(), -1); if (spillSlot == -1) lifeTimeHole = true; else - moveFrom = createTemp(Temp::StackSlot, spillSlot, predIt.temp().type); + moveFrom = createTemp(Temp::StackSlot, spillSlot, predIt->temp().type); } break; } @@ -906,20 +915,20 @@ private: if (!moveFrom) { Q_UNUSED(lifeTimeHole); #if !defined(QT_NO_DEBUG) - Q_ASSERT(!_info->isPhiTarget(it.temp()) || it.isSplitFromInterval() || lifeTimeHole); - if (_info->def(it.temp()) != successorStart && !it.isSplitFromInterval()) { + Q_ASSERT(!_info->isPhiTarget(it->temp()) || it->isSplitFromInterval() || lifeTimeHole); + if (_info->def(it->temp()) != successorStart && !it->isSplitFromInterval()) { const int successorEnd = successor->statements.last()->id; const int idx = successor->in.indexOf(predecessor); - foreach (const Use &use, _info->uses(it.temp())) { + foreach (const Use &use, _info->uses(it->temp())) { if (use.pos == static_cast(successorStart)) { // only check the current edge, not all other possible ones. This is // important for phi nodes: they have uses that are only valid when // coming in over a specific edge. foreach (Stmt *s, successor->statements) { if (Phi *phi = s->asPhi()) { - Q_ASSERT(it.temp().index != phi->targetTemp->index); + Q_ASSERT(it->temp().index != phi->targetTemp->index); Q_ASSERT(phi->d->incoming[idx]->asTemp() == 0 - || it.temp().index != phi->d->incoming[idx]->asTemp()->index); + || it->temp().index != phi->d->incoming[idx]->asTemp()->index); } else { // TODO: check that the first non-phi statement does not use // the temp. @@ -938,18 +947,18 @@ private: } Temp *moveTo; - if (it.reg() == LifeTimeInterval::Invalid || !it.covers(successorStart)) { - if (!isPhiTarget) // if it.temp() is a phi target, skip it. + if (it->reg() == LifeTimeInterval::Invalid || !it->covers(successorStart)) { + if (!isPhiTarget) // if it->temp() is a phi target, skip it. continue; - const int spillSlot = _assignedSpillSlots.value(it.temp(), -1); + const int spillSlot = _assignedSpillSlots.value(it->temp(), -1); if (spillSlot == -1) continue; // it has a life-time hole here. - moveTo = createTemp(Temp::StackSlot, spillSlot, it.temp().type); + moveTo = createTemp(Temp::StackSlot, spillSlot, it->temp().type); } else { - moveTo = createTemp(Temp::PhysicalRegister, platformRegister(it), it.temp().type); - const int spillSlot = _assignedSpillSlots.value(it.temp(), -1); + moveTo = createTemp(Temp::PhysicalRegister, platformRegister(*it), it->temp().type); + const int spillSlot = _assignedSpillSlots.value(it->temp(), -1); if (isPhiTarget && spillSlot != -1) - mapping.add(moveFrom, createTemp(Temp::StackSlot, spillSlot, it.temp().type)); + mapping.add(moveFrom, createTemp(Temp::StackSlot, spillSlot, it->temp().type)); } // add move to mapping @@ -1010,10 +1019,10 @@ protected: if (t->kind != Temp::VirtualRegister) return; - const LifeTimeInterval &i = _intervalForTemp[*t]; - Q_ASSERT(i.isValid()); - if (i.reg() != LifeTimeInterval::Invalid && i.covers(_currentStmt->id)) { - int pReg = platformRegister(i); + const LifeTimeInterval *i = _intervalForTemp[*t]; + Q_ASSERT(i->isValid()); + if (i->reg() != LifeTimeInterval::Invalid && i->covers(_currentStmt->id)) { + int pReg = platformRegister(*i); t->kind = Temp::PhysicalRegister; t->index = pReg; } else { @@ -1119,7 +1128,7 @@ void RegisterAllocator::run(Function *function, const Optimizer &opt) #endif // DEBUG_REGALLOC } -static inline LifeTimeInterval createFixedInterval(int reg, bool isFP) +static inline LifeTimeInterval createFixedInterval(int reg, bool isFP, int rangeCount) { Temp t; t.init(Temp::PhysicalRegister, reg, 0); @@ -1128,6 +1137,7 @@ static inline LifeTimeInterval createFixedInterval(int reg, bool isFP) i.setTemp(t); i.setReg(reg); i.setFixedInterval(true); + i.reserveRanges(rangeCount); return i; } @@ -1136,12 +1146,13 @@ void RegisterAllocator::prepareRanges() const int regCount = _normalRegisters.size(); _fixedRegisterRanges.resize(regCount); for (int reg = 0; reg < regCount; ++reg) - _fixedRegisterRanges[reg] = createFixedInterval(reg, false); + _fixedRegisterRanges[reg] = createFixedInterval(reg, false, _info->calls().size()); const int fpRegCount = _fpRegisters.size(); _fixedFPRegisterRanges.resize(fpRegCount); - for (int fpReg = 0; fpReg < fpRegCount; ++fpReg) - _fixedFPRegisterRanges[fpReg] = createFixedInterval(fpReg, true); + for (int fpReg = 0; fpReg < fpRegCount; ++fpReg) { + _fixedFPRegisterRanges[fpReg] = createFixedInterval(fpReg, true, _info->calls().size()); + } foreach (int callPosition, _info->calls()) { for (int reg = 0; reg < regCount; ++reg) diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index c2889a2b9a..f14205519d 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -308,9 +308,9 @@ public: BasicBlock *operator*() const { if (set.blockNumbers) - return set.allBlocks[*numberIt]; + return set.allBlocks.at(*numberIt); else - return set.allBlocks[flagIt]; + return set.allBlocks.at(flagIt); } bool operator==(const const_iterator &other) const @@ -472,9 +472,8 @@ class DominatorTree { #endif // SHOW_SSA } - BasicBlockIndex ancestorWithLowestSemi(BasicBlockIndex v) { - std::vector worklist; - worklist.reserve(vertex.capacity() / 2); + BasicBlockIndex ancestorWithLowestSemi(BasicBlockIndex v, std::vector &worklist) { + worklist.clear(); for (BasicBlockIndex it = v; it != InvalidBasicBlockIndex; it = ancestor[it]) worklist.push_back(it); @@ -517,6 +516,9 @@ class DominatorTree { DFS(nodes.first()->index); Q_ASSERT(N == nodes.size()); // fails with unreachable nodes, but those should have been removed before. + std::vector worklist; + worklist.reserve(vertex.capacity() / 2); + for (int i = N - 1; i > 0; --i) { BasicBlockIndex n = vertex[i]; BasicBlockIndex p = parent[n]; @@ -527,7 +529,7 @@ class DominatorTree { if (dfnum[v->index] <= dfnum[n]) ss = v->index; else - ss = semi[ancestorWithLowestSemi(v->index)]; + ss = semi[ancestorWithLowestSemi(v->index, worklist)]; if (dfnum[ss] < dfnum[s]) s = ss; } @@ -536,7 +538,7 @@ class DominatorTree { link(p, n); if (bucket.contains(p)) { foreach (BasicBlockIndex v, bucket[p]) { - BasicBlockIndex y = ancestorWithLowestSemi(v); + BasicBlockIndex y = ancestorWithLowestSemi(v, worklist); BasicBlockIndex semi_v = semi[v]; if (semi[y] == semi_v) idom[v] = semi_v; @@ -602,7 +604,7 @@ class DominatorTree { std::vector worklist; worklist.reserve(nodes.size() * 2); for (int i = 0, ei = nodes.size(); i != ei; ++i) { - BasicBlockIndex nodeIndex = nodes[i]->index; + BasicBlockIndex nodeIndex = nodes.at(i)->index; worklist.push_back(nodeIndex); NodeProgress &np = nodeStatus[nodeIndex]; np.children = children[nodeIndex]; @@ -633,7 +635,7 @@ class DominatorTree { if (np.todo.empty()) { BasicBlockSet &S = DF[node]; S.init(nodes); - foreach (BasicBlock *y, nodes[node]->out) + foreach (BasicBlock *y, nodes.at(node)->out) if (idom[y->index] != node) S.insert(y); foreach (BasicBlockIndex child, np.children) { @@ -755,6 +757,8 @@ public: VariableCollector(Function *function) : variablesCanEscape(function->variablesCanEscape()) { + _defsites.reserve(function->tempCount); + #if defined(SHOW_SSA) qout << "Variables collected:" << endl; #endif // SHOW_SSA @@ -1019,6 +1023,9 @@ public: , tempCount(0) , processed(f->basicBlocks) { + localMapping.reserve(f->tempCount); + vregMapping.reserve(f->tempCount); + todo.reserve(f->basicBlocks.size()); } void run() { @@ -2466,9 +2473,8 @@ protected: void splitCriticalEdges(Function *f) { - const QVector oldBBs = f->basicBlocks; - - foreach (BasicBlock *bb, oldBBs) { + for (int i = 0, ei = f->basicBlocks.size(); i != ei; ++i) { + BasicBlock *bb = f->basicBlocks[i]; if (bb->in.size() > 1) { for (int inIdx = 0, eInIdx = bb->in.size(); inIdx != eInIdx; ++inIdx) { BasicBlock *inBB = bb->in[inIdx]; diff --git a/src/qml/compiler/qv4ssa_p.h b/src/qml/compiler/qv4ssa_p.h index 2c61a2fe1a..f90fc5b05b 100644 --- a/src/qml/compiler/qv4ssa_p.h +++ b/src/qml/compiler/qv4ssa_p.h @@ -93,6 +93,7 @@ public: void setFrom(Stmt *from); void addRange(int from, int to); Ranges ranges() const { return _ranges; } + void reserveRanges(int capacity) { _ranges.reserve(capacity); } int start() const { return _ranges.first().start; } int end() const { return _end; } -- cgit v1.2.3