Merge 'wip/next' into dev

Change-Id: Iff9ee5e23bb326c4371ec8ed81d56f2f05d680e9

1 files changed, 176 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGNaturalLoops.h b/Source/JavaScriptCore/dfg/DFGNaturalLoops.h
new file mode 100644
index 000000000..8454d0cb5
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGNaturalLoops.h
@@ -0,0 +1,176 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGNaturalLoops_h
+#define DFGNaturalLoops_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+#include "DFGCommon.h"
+#include "DFGDominators.h"
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
+
+namespace JSC { namespace DFG {
+
+class NaturalLoops;
+
+class NaturalLoop {
+public:
+    NaturalLoop()
+        : m_header(0)
+        , m_outerLoopIndex(UINT_MAX)
+    {
+    }
+    
+    NaturalLoop(BasicBlock* header, unsigned index)
+        : m_header(header)
+        , m_outerLoopIndex(UINT_MAX)
+        , m_index(index)
+    {
+    }
+    
+    BasicBlock* header() const { return m_header; }
+    
+    unsigned size() const { return m_body.size(); }
+    BasicBlock* at(unsigned i) const { return m_body[i]; }
+    BasicBlock* operator[](unsigned i) const { return at(i); }
+
+    // This is the slower, but simpler, way of asking if a block belongs to
+    // a natural loop. It's faster to call NaturalLoops::belongsTo(), which
+    // tries to be O(loop depth) rather than O(loop size). Loop depth is
+    // almost always smaller than loop size. A *lot* smaller.
+    bool contains(BasicBlock* block) const
+    {
+        for (unsigned i = m_body.size(); i--;) {
+            if (m_body[i] == block)
+                return true;
+        }
+        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 {
+    WTF_MAKE_NONCOPYABLE(NaturalLoops);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    NaturalLoops(Graph&);
+    ~NaturalLoops();
+    
+    unsigned numLoops() const
+    {
+        return m_loops.size();
+    }
+    const NaturalLoop& loop(unsigned i) const
+    {
+        return m_loops[i];
+    }
+    
+    // Return either null if the block isn't a loop header, or the
+    // loop it belongs to.
+    const NaturalLoop* headerOf(BasicBlock* block) const
+    {
+        const NaturalLoop* loop = innerMostLoopOf(block);
+        if (!loop)
+            return 0;
+        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];
+    }
+    
+    bool belongsTo(BasicBlock* block, const NaturalLoop& candidateLoop) const
+    {
+        // It's faster to do this test using the loop itself, if it's small.
+        if (candidateLoop.size() < 4)
+            return candidateLoop.contains(block);
+        
+        for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
+            if (loop == &candidateLoop)
+                return true;
+        }
+        return false;
+    }
+    
+    unsigned loopDepth(BasicBlock* block) const
+    {
+        unsigned depth = 0;
+        for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
+            depth++;
+        return depth;
+    }
+    
+    // Return the indices of all loops this belongs to.
+    Vector<const NaturalLoop*> loopsOf(BasicBlock*) const;
+
+    void dump(PrintStream&) const;
+private:
+    // If we ever had a scalability problem in our natural loop finder, we could
+    // use some HashMap's here. But it just feels a heck of a lot less convenient.
+    Vector<NaturalLoop, 4> m_loops;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGNaturalLoops_h
+