From 515cef3937c4e3b6f3b7908ff79bfef3c935a360 Mon Sep 17 00:00:00 2001 From: Erik Verbruggen Date: Fri, 5 Jun 2015 12:30:32 +0200 Subject: Wrap std::vector in our own class. So we can replace the implementation when we encounter a broken version of std::vector or a broken specialization of std::find for it. Change-Id: I7d7c0af585388ddedf5167cd9863c52ab638442d Reviewed-by: Simon Hausmann --- src/qml/compiler/qv4ssa.cpp | 186 ++++++++++++++++++++++++++------------------ 1 file changed, 112 insertions(+), 74 deletions(-) (limited to 'src/qml/compiler/qv4ssa.cpp') diff --git a/src/qml/compiler/qv4ssa.cpp b/src/qml/compiler/qv4ssa.cpp index a0ed77ffc1..5829e1c813 100644 --- a/src/qml/compiler/qv4ssa.cpp +++ b/src/qml/compiler/qv4ssa.cpp @@ -81,16 +81,75 @@ static void showMeTheCode(IR::Function *function, const char *marker) } } -class ProcessedBlocks +class BitVector { - QBitArray processed; + std::vector bits; public: - ProcessedBlocks(IR::Function *function) + BitVector(int size = 0, bool value = false) + : bits(size, value) + {} + + void reserve(int size) + { bits.reserve(size); } + + int size() const { - processed = QBitArray(function->basicBlockCount(), false); + Q_ASSERT(bits.size() < INT_MAX); + return static_cast(bits.size()); + } + + void resize(int newSize) + { bits.resize(newSize); } + + void assign(int newSize, bool value) + { bits.assign(newSize, value); } + + int findNext(int start, bool value, bool wrapAround) const + { + // The ++operator of std::vector::iterator in libc++ has a bug when using it on an + // iterator pointing to the last element. It will not be set to ::end(), but beyond + // that. (It will be set to the first multiple of the native word size that is bigger + // than size().) + // + // See http://llvm.org/bugs/show_bug.cgi?id=19663 + // + // The work-around is to calculate the distance, and compare it to the size() to see if it's + // beyond the end, or take the minimum of the distance and the size. + + size_t pos = std::distance(bits.begin(), + std::find(bits.begin() + start, bits.end(), value)); + if (wrapAround && pos >= static_cast(size())) + pos = std::distance(bits.begin(), + std::find(bits.begin(), bits.begin() + start, value)); + + pos = qMin(pos, static_cast(size())); + + Q_ASSERT(pos <= static_cast(size())); + Q_ASSERT(pos < INT_MAX); + + return static_cast(pos); } + bool at(int idx) const + { return bits.at(idx); } + + void setBit(int idx) + { bits[idx] = true; } + + void clearBit(int idx) + { bits[idx] = false; } +}; + +class ProcessedBlocks +{ + BitVector processed; + +public: + ProcessedBlocks(IR::Function *function) + : processed(function->basicBlockCount(), false) + {} + bool alreadyProcessed(BasicBlock *bb) const { Q_ASSERT(bb); @@ -106,7 +165,7 @@ public: class BasicBlockSet { - typedef std::vector Flags; + typedef BitVector Flags; QVarLengthArray blockNumbers; Flags *blockFlags; @@ -119,7 +178,7 @@ public: const BasicBlockSet &set; // ### These two members could go into a union, but clang won't compile (https://codereview.qt-project.org/#change,74259) QVarLengthArray::const_iterator numberIt; - size_t flagIt; + int flagIt; friend class BasicBlockSet; const_iterator(const BasicBlockSet &set, bool end) @@ -138,24 +197,9 @@ public: } } - void findNextWithFlags(size_t start) + void findNextWithFlags(int start) { - flagIt = std::distance(set.blockFlags->begin(), - std::find(set.blockFlags->begin() + start, - set.blockFlags->end(), - true)); - - // The ++operator of std::vector::iterator in libc++ has a bug when using it on an - // iterator pointing to the last element. It will not be set to ::end(), but beyond - // that. (It will be set to the first multiple of the native word size that is bigger - // than size().) - // - // See http://llvm.org/bugs/show_bug.cgi?id=19663 - // - // As we use the size to for our end() iterator, take the minimum of the size and the - // distance for the flagIt: - flagIt = qMin(flagIt, set.blockFlags->size()); - + flagIt = set.blockFlags->findNext(start, true, /*wrapAround = */false); Q_ASSERT(flagIt <= set.blockFlags->size()); } @@ -165,8 +209,8 @@ public: if (!set.blockFlags) { return set.function->basicBlock(*numberIt); } else { - Q_ASSERT(flagIt <= static_cast(set.function->basicBlockCount())); - return set.function->basicBlock(static_cast(flagIt)); + Q_ASSERT(flagIt <= set.function->basicBlockCount()); + return set.function->basicBlock(flagIt); } } @@ -256,7 +300,7 @@ public: Q_ASSERT(function); if (blockFlags) { - (*blockFlags)[bb->index()] = true; + blockFlags->setBit(bb->index()); return; } @@ -268,10 +312,10 @@ public: if (blockNumbers.size() == MaxVectorCapacity) { blockFlags = new Flags(function->basicBlockCount(), false); for (int i = 0; i < blockNumbers.size(); ++i) { - blockFlags->operator[](blockNumbers[i]) = true; + blockFlags->setBit(blockNumbers[i]); } blockNumbers.clear(); - blockFlags->operator[](bb->index()) = true; + blockFlags->setBit(bb->index()); } else { blockNumbers.append(bb->index()); } @@ -282,7 +326,7 @@ public: Q_ASSERT(function); if (blockFlags) { - (*blockFlags)[bb->index()] = false; + blockFlags->clearBit(bb->index()); return; } @@ -310,7 +354,7 @@ public: Q_ASSERT(function); if (blockFlags) - return (*blockFlags)[bb->index()]; + return blockFlags->at(bb->index()); for (int i = 0; i < blockNumbers.size(); ++i) { if (blockNumbers[i] == bb->index()) @@ -539,12 +583,12 @@ public: np.todo = children[nodeIndex]; } - std::vector DF_done(function->basicBlockCount(), false); + BitVector DF_done(function->basicBlockCount(), false); while (!worklist.empty()) { BasicBlockIndex node = worklist.back(); - if (DF_done[node]) { + if (DF_done.at(node)) { worklist.pop_back(); continue; } @@ -552,7 +596,7 @@ public: NodeProgress &np = nodeStatus[node]; std::vector::iterator it = np.todo.begin(); while (it != np.todo.end()) { - if (DF_done[*it]) { + if (DF_done.at(*it)) { it = np.todo.erase(it); } else { worklist.push_back(*it); @@ -575,7 +619,7 @@ public: S.insert(w); } } - DF_done[node] = true; + DF_done.setBit(node); worklist.pop_back(); } } @@ -914,8 +958,8 @@ class VariableCollector: public StmtVisitor, ExprVisitor { std::vector _allTemps; std::vector _defsites; std::vector > A_orig; - std::vector nonLocals; - std::vector killed; + BitVector nonLocals; + BitVector killed; BasicBlock *currentBB; bool isCollectable(Temp *t) const @@ -979,8 +1023,8 @@ public: bool isNonLocal(const Temp &var) const { Q_ASSERT(!var.isInvalid()); - Q_ASSERT(var.index < nonLocals.size()); - return nonLocals[var.index]; + Q_ASSERT(static_cast(var.index) < nonLocals.size()); + return nonLocals.at(var.index); } protected: @@ -1025,7 +1069,7 @@ protected: addDefInCurrentBlock(t); // For semi-pruned SSA: - killed[t->index] = true; + killed.setBit(t->index); } } else { s->target->accept(this); @@ -1037,8 +1081,8 @@ protected: addTemp(t); if (isCollectable(t)) - if (!killed[t->index]) - nonLocals[t->index] = true; + if (!killed.at(t->index)) + nonLocals.setBit(t->index); } }; @@ -1619,7 +1663,7 @@ void convertToSSA(IR::Function *function, const DominatorTree &df, DefUses &defU VariableCollector variables(function); // Prepare for phi node insertion: - std::vector > A_phi; + std::vector A_phi; const size_t ei = function->basicBlockCount(); A_phi.resize(ei); for (size_t i = 0; i != ei; ++i) @@ -1646,7 +1690,7 @@ void convertToSSA(IR::Function *function, const DominatorTree &df, DefUses &defU BasicBlock *y = *it; if (!A_phi.at(y->index()).at(a.index)) { insertPhiNode(a, y, function); - A_phi[y->index()].at(a.index) = true; + A_phi[y->index()].setBit(a.index); const std::vector &varsInBlockY = variables.inBlock(y); if (std::find(varsInBlockY.begin(), varsInBlockY.end(), a.index) == varsInBlockY.end()) W.push_back(y); @@ -1723,10 +1767,10 @@ class StatementWorklist { IR::Function *theFunction; std::vector stmts; - std::vector worklist; + BitVector worklist; unsigned worklistSize; std::vector replaced; - std::vector removed; + BitVector removed; Q_DISABLE_COPY(StatementWorklist) @@ -1750,7 +1794,7 @@ public: continue; stmts[s->id()] = s; - worklist[s->id()] = true; + worklist.setBit(s->id()); ++worklistSize; } } @@ -1765,7 +1809,7 @@ public: if (!s) continue; - worklist[s->id()] = true; + worklist.setBit(s->id()); ++worklistSize; } @@ -1776,10 +1820,9 @@ public: void remove(Stmt *stmt) { replaced[stmt->id()] = Stmt::InvalidId; - removed[stmt->id()] = true; - std::vector::reference inWorklist = worklist[stmt->id()]; - if (inWorklist) { - inWorklist = false; + removed.setBit(stmt->id()); + if (worklist.at(stmt->id())) { + worklist.clearBit(stmt->id()); Q_ASSERT(worklistSize > 0); --worklistSize; } @@ -1789,15 +1832,15 @@ public: { Q_ASSERT(oldStmt); Q_ASSERT(replaced[oldStmt->id()] == Stmt::InvalidId); - Q_ASSERT(removed[oldStmt->id()] == false); + Q_ASSERT(removed.at(oldStmt->id()) == false); Q_ASSERT(newStmt); registerNewStatement(newStmt); Q_ASSERT(replaced[newStmt->id()] == Stmt::InvalidId); - Q_ASSERT(removed[newStmt->id()] == false); + Q_ASSERT(removed.at(newStmt->id()) == false); replaced[oldStmt->id()] = newStmt->id(); - worklist[oldStmt->id()] = false; + worklist.clearBit(oldStmt->id()); } void applyToFunction() @@ -1818,7 +1861,7 @@ public: Q_ASSERT(id != Stmt::InvalidId); Q_ASSERT(static_cast(stmt->id()) < stmts.size()); - if (removed[id]) { + if (removed.at(id)) { bb->removeStatement(i); } else { if (id != stmt->id()) @@ -1847,10 +1890,10 @@ public: return *this; Q_ASSERT(s->id() >= 0); - Q_ASSERT(static_cast(s->id()) < worklist.size()); + Q_ASSERT(s->id() < worklist.size()); - if (!worklist[s->id()]) { - worklist[s->id()] = true; + if (!worklist.at(s->id())) { + worklist.setBit(s->id()); ++worklistSize; } @@ -1860,11 +1903,10 @@ public: StatementWorklist &operator-=(Stmt *s) { Q_ASSERT(s->id() >= 0); - Q_ASSERT(static_cast(s->id()) < worklist.size()); + Q_ASSERT(s->id() < worklist.size()); - std::vector::reference inWorklist = worklist[s->id()]; - if (inWorklist) { - inWorklist = false; + if (worklist.at(s->id())) { + worklist.clearBit(s->id()); Q_ASSERT(worklistSize > 0); --worklistSize; } @@ -1884,18 +1926,13 @@ public: const int startAt = last ? last->id() + 1 : 0; Q_ASSERT(startAt >= 0); - Q_ASSERT(static_cast(startAt) <= worklist.size()); + Q_ASSERT(startAt <= worklist.size()); - Q_ASSERT(worklist.size() == stmts.size()); + Q_ASSERT(static_cast(worklist.size()) == stmts.size()); - // Do not compare the result of find with the end iterator, because some libc++ versions - // have a bug where the result of the ++operator is past-the-end of the vector, but unequal - // to end(). - size_t pos = std::find(worklist.begin() + startAt, worklist.end(), true) - worklist.begin(); - if (pos >= worklist.size()) - pos = std::find(worklist.begin(), worklist.begin() + startAt, true) - worklist.begin(); + int pos = worklist.findNext(startAt, true, /*wrapAround = */true); - worklist[pos] = false; + worklist.clearBit(pos); Q_ASSERT(worklistSize > 0); --worklistSize; Stmt *s = stmts.at(pos); @@ -1917,9 +1954,9 @@ public: int newSize = s->id() + 1; stmts.resize(newSize, 0); - worklist.resize(newSize, false); + worklist.resize(newSize); replaced.resize(newSize, Stmt::InvalidId); - removed.resize(newSize, false); + removed.resize(newSize); } stmts[s->id()] = s; @@ -1928,7 +1965,8 @@ public: private: void grow() { - size_t newCapacity = ((stmts.capacity() + 1) * 3) / 2; + Q_ASSERT(stmts.capacity() < INT_MAX / 2); + int newCapacity = ((static_cast(stmts.capacity()) + 1) * 3) / 2; stmts.reserve(newCapacity); worklist.reserve(newCapacity); replaced.reserve(newCapacity); -- cgit v1.2.3