- Revision
- 152745
- Author
- [email protected]
- Date
- 2013-07-16 15:50:38 -0700 (Tue, 16 Jul 2013)
Log Message
fourthTier: NaturalLoops should be able to quickly answer questions like "what loops own this basic block"
https://bugs.webkit.org/show_bug.cgi?id=118750
Source/_javascript_Core:
Reviewed by Mark Hahnenberg.
* dfg/DFGBasicBlock.h:
(BasicBlock):
* dfg/DFGNaturalLoops.cpp:
(JSC::DFG::NaturalLoops::compute):
(JSC::DFG::NaturalLoops::loopsOf):
* dfg/DFGNaturalLoops.h:
(DFG):
(JSC::DFG::NaturalLoop::NaturalLoop):
(NaturalLoop):
(JSC::DFG::NaturalLoop::index):
(JSC::DFG::NaturalLoop::isOuterMostLoop):
(JSC::DFG::NaturalLoop::addBlock):
(JSC::DFG::NaturalLoops::headerOf):
(JSC::DFG::NaturalLoops::innerMostLoopOf):
(NaturalLoops):
(JSC::DFG::NaturalLoops::innerMostOuterLoop):
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
Source/WTF:
Reviewed by Mark Hahnenberg.
Add a utility function for inserting an element into a vector that has bounded size,
and where the insertion causes things to drop off the end.
* wtf/StdLibExtras.h:
(WTF):
(WTF::insertIntoBoundedVector):
Modified Paths
Diff
Modified: branches/dfgFourthTier/Source/_javascript_Core/ChangeLog (152744 => 152745)
--- branches/dfgFourthTier/Source/_javascript_Core/ChangeLog 2013-07-16 22:08:21 UTC (rev 152744)
+++ branches/dfgFourthTier/Source/_javascript_Core/ChangeLog 2013-07-16 22:50:38 UTC (rev 152745)
@@ -1,5 +1,31 @@
2013-07-16 Filip Pizlo <[email protected]>
+ fourthTier: NaturalLoops should be able to quickly answer questions like "what loops own this basic block"
+ https://bugs.webkit.org/show_bug.cgi?id=118750
+
+ Reviewed by Mark Hahnenberg.
+
+ * dfg/DFGBasicBlock.h:
+ (BasicBlock):
+ * dfg/DFGNaturalLoops.cpp:
+ (JSC::DFG::NaturalLoops::compute):
+ (JSC::DFG::NaturalLoops::loopsOf):
+ * dfg/DFGNaturalLoops.h:
+ (DFG):
+ (JSC::DFG::NaturalLoop::NaturalLoop):
+ (NaturalLoop):
+ (JSC::DFG::NaturalLoop::index):
+ (JSC::DFG::NaturalLoop::isOuterMostLoop):
+ (JSC::DFG::NaturalLoop::addBlock):
+ (JSC::DFG::NaturalLoops::headerOf):
+ (JSC::DFG::NaturalLoops::innerMostLoopOf):
+ (NaturalLoops):
+ (JSC::DFG::NaturalLoops::innerMostOuterLoop):
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+
+2013-07-16 Filip Pizlo <[email protected]>
+
fourthTier: don't GC when shutting down the VM
https://bugs.webkit.org/show_bug.cgi?id=118751
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGBasicBlock.h (152744 => 152745)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGBasicBlock.h 2013-07-16 22:08:21 UTC (rev 152744)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGBasicBlock.h 2013-07-16 22:50:38 UTC (rev 152745)
@@ -127,6 +127,10 @@
Operands<AbstractValue> valuesAtHead;
Operands<AbstractValue> valuesAtTail;
+ // These fields are reserved for NaturalLoops.
+ static const unsigned numberOfInnerMostLoopIndices = 2;
+ unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices];
+
struct SSAData {
Operands<FlushFormat> flushFormatAtHead;
Operands<FlushFormat> flushFormatAtTail;
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp (152744 => 152745)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2013-07-16 22:08:21 UTC (rev 152744)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2013-07-16 22:50:38 UTC (rev 152745)
@@ -84,7 +84,7 @@
}
if (found)
continue;
- NaturalLoop loop(successor);
+ NaturalLoop loop(successor, m_loops.size());
loop.addBlock(block);
m_loops.append(loop);
}
@@ -131,7 +131,66 @@
}
}
}
+
+ // Figure out reverse mapping from blocks to loops.
+ for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = graph.block(blockIndex);
+ if (!block)
+ continue;
+ for (unsigned i = BasicBlock::numberOfInnerMostLoopIndices; i--;)
+ block->innerMostLoopIndices[i] = UINT_MAX;
+ }
+ for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
+ NaturalLoop& loop = m_loops[loopIndex];
+
+ for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
+ BasicBlock* block = loop[blockIndexInLoop];
+
+ for (unsigned i = 0; i < BasicBlock::numberOfInnerMostLoopIndices; ++i) {
+ unsigned thisIndex = block->innerMostLoopIndices[i];
+ if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
+ insertIntoBoundedVector(
+ block->innerMostLoopIndices, BasicBlock::numberOfInnerMostLoopIndices,
+ loopIndex, i);
+ break;
+ }
+ }
+ }
+ }
+ // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
+ // this to figure out loop parenting.
+ for (unsigned i = m_loops.size(); i--;) {
+ NaturalLoop& loop = m_loops[i];
+ RELEASE_ASSERT(loop.header()->innerMostLoopIndices[0] == i);
+
+ loop.m_outerLoopIndex = loop.header()->innerMostLoopIndices[1];
+ }
+
+ if (validationEnabled()) {
+ // Do some self-verification that we've done some of this correctly.
+
+ for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = graph.block(blockIndex);
+ if (!block)
+ continue;
+
+ Vector<const NaturalLoop*> simpleLoopsOf;
+
+ for (unsigned i = m_loops.size(); i--;) {
+ if (m_loops[i].contains(block))
+ simpleLoopsOf.append(&m_loops[i]);
+ }
+
+ Vector<const NaturalLoop*> fancyLoopsOf = loopsOf(block);
+
+ std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
+ std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
+
+ RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
+ }
+ }
+
if (verbose)
dataLog("Results: ", *this, "\n");
}
@@ -139,12 +198,8 @@
Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
{
Vector<const NaturalLoop*> result;
-
- for (unsigned i = m_loops.size(); i--;) {
- if (m_loops[i].contains(block))
- result.append(&m_loops[i]);
- }
-
+ for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
+ result.append(loop);
return result;
}
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.h (152744 => 152745)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.h 2013-07-16 22:08:21 UTC (rev 152744)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGNaturalLoops.h 2013-07-16 22:50:38 UTC (rev 152745)
@@ -36,20 +36,23 @@
namespace JSC { namespace DFG {
+class NaturalLoops;
+
class NaturalLoop {
public:
NaturalLoop()
: m_header(0)
+ , m_outerLoopIndex(UINT_MAX)
{
}
- NaturalLoop(BasicBlock* header)
+ NaturalLoop(BasicBlock* header, unsigned index)
: m_header(header)
+ , m_outerLoopIndex(UINT_MAX)
+ , m_index(index)
{
}
- void addBlock(BasicBlock* block) { m_body.append(block); }
-
BasicBlock* header() const { return m_header; }
unsigned size() const { return m_body.size(); }
@@ -65,11 +68,22 @@
ASSERT(block != header()); // Header should be contained.
return false;
}
+
+ // The index of this loop in NaturalLoops.
+ unsigned index() const { return m_index; }
+ bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; }
+
void dump(PrintStream&) const;
private:
+ friend class NaturalLoops;
+
+ void addBlock(BasicBlock* block) { m_body.append(block); }
+
BasicBlock* m_header;
Vector<BasicBlock*, 4> m_body;
+ unsigned m_outerLoopIndex;
+ unsigned m_index;
};
class NaturalLoops : public Analysis<NaturalLoops> {
@@ -94,13 +108,31 @@
// loop it belongs to.
const NaturalLoop* headerOf(BasicBlock* block) const
{
- for (unsigned i = m_loops.size(); i--;) {
- if (m_loops[i].header() == block)
- return &m_loops[i];
+ const NaturalLoop* loop = innerMostLoopOf(block);
+ if (loop->header() == block)
+ return loop;
+ if (!ASSERT_DISABLED) {
+ for (; loop; loop = innerMostOuterLoop(*loop))
+ ASSERT(loop->header() != block);
}
return 0;
}
+ const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
+ {
+ unsigned index = block->innerMostLoopIndices[0];
+ if (index == UINT_MAX)
+ return 0;
+ return &m_loops[index];
+ }
+
+ const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
+ {
+ if (loop.m_outerLoopIndex == UINT_MAX)
+ return 0;
+ return &m_loops[loop.m_outerLoopIndex];
+ }
+
// Return the indices of all loops this belongs to.
Vector<const NaturalLoop*> loopsOf(BasicBlock*) const;
Modified: branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGPlan.cpp (152744 => 152745)
--- branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGPlan.cpp 2013-07-16 22:08:21 UTC (rev 152744)
+++ branches/dfgFourthTier/Source/_javascript_Core/dfg/DFGPlan.cpp 2013-07-16 22:50:38 UTC (rev 152745)
@@ -187,6 +187,13 @@
dfg.m_fixpointState = FixpointConverged;
performStoreElimination(dfg);
+
+ // If we're doing validation, then run some analyses, to give them an opportunity
+ // to self-validate. Now is as good a time as any to do this.
+ if (validationEnabled()) {
+ dfg.m_dominators.computeIfNecessary(dfg);
+ dfg.m_naturalLoops.computeIfNecessary(dfg);
+ }
#if ENABLE(FTL_JIT)
if (Options::useExperimentalFTL()
Modified: branches/dfgFourthTier/Source/WTF/ChangeLog (152744 => 152745)
--- branches/dfgFourthTier/Source/WTF/ChangeLog 2013-07-16 22:08:21 UTC (rev 152744)
+++ branches/dfgFourthTier/Source/WTF/ChangeLog 2013-07-16 22:50:38 UTC (rev 152745)
@@ -1,3 +1,17 @@
+2013-07-16 Filip Pizlo <[email protected]>
+
+ fourthTier: NaturalLoops should be able to quickly answer questions like "what loops own this basic block"
+ https://bugs.webkit.org/show_bug.cgi?id=118750
+
+ Reviewed by Mark Hahnenberg.
+
+ Add a utility function for inserting an element into a vector that has bounded size,
+ and where the insertion causes things to drop off the end.
+
+ * wtf/StdLibExtras.h:
+ (WTF):
+ (WTF::insertIntoBoundedVector):
+
2013-07-12 Filip Pizlo <[email protected]>
fourthTier: DFG should have an SSA form for use by FTL
Modified: branches/dfgFourthTier/Source/WTF/wtf/StdLibExtras.h (152744 => 152745)
--- branches/dfgFourthTier/Source/WTF/wtf/StdLibExtras.h 2013-07-16 22:08:21 UTC (rev 152744)
+++ branches/dfgFourthTier/Source/WTF/wtf/StdLibExtras.h 2013-07-16 22:50:38 UTC (rev 152745)
@@ -259,6 +259,14 @@
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
}
+template<typename VectorType, typename ElementType>
+inline void insertIntoBoundedVector(VectorType& vector, size_t size, const ElementType& element, size_t index)
+{
+ for (unsigned i = size; i-- > index + 1;)
+ vector[i] = vector[i - 1];
+ vector[index] = element;
+}
+
} // namespace WTF
// This version of placement new omits a 0 check.
@@ -271,6 +279,7 @@
using WTF::KB;
using WTF::MB;
+using WTF::insertIntoBoundedVector;
using WTF::isPointerAligned;
using WTF::is8ByteAligned;
using WTF::binarySearch;
