DFG should be able to compute dominators
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 22 May 2012 00:51:05 +0000 (00:51 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 22 May 2012 00:51:05 +0000 (00:51 +0000)
https://bugs.webkit.org/show_bug.cgi?id=85269

Source/JavaScriptCore:

Reviewed by Oliver Hunt.

Merged r115754 from dfgopt.

Implements a naive dominator calculator, which is currently just used to
print information in graph dumps. I've enabled it by default mainly to
be able to track its performance impact. So far it appears that there is
none, which is unsurprising given that the number of basic blocks in most
procedures is small.

Also tweaked bytecode dumping to reveal more useful information about the
nature of the code block.

* CMakeLists.txt:
* GNUmakefile.list.am:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Target.pri:
* bytecode/CodeBlock.cpp:
(JSC::CodeBlock::dump):
* dfg/DFGDominators.cpp: Added.
(DFG):
(JSC::DFG::Dominators::Dominators):
(JSC::DFG::Dominators::~Dominators):
(JSC::DFG::Dominators::compute):
(JSC::DFG::Dominators::iterateForBlock):
* dfg/DFGDominators.h: Added.
(DFG):
(Dominators):
(JSC::DFG::Dominators::invalidate):
(JSC::DFG::Dominators::computeIfNecessary):
(JSC::DFG::Dominators::isValid):
(JSC::DFG::Dominators::dominates):
* dfg/DFGDriver.cpp:
(JSC::DFG::compile):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
* dfg/DFGGraph.h:
(Graph):

Source/WTF:

Reviewed by Oliver Hunt.

Merged r115754 from dfgopt.

Added a bitvector class suitable for cheap static analysis. This class
differs from BitVector in that instead of optimizing for space, it
optimizes for execution time. Its API is also somewhat less friendly,
which is intentional; it's meant to be used in places where you know
up front how bit your bitvectors are going to be.

* GNUmakefile.list.am:
* WTF.vcproj/WTF.vcproj:
* WTF.xcodeproj/project.pbxproj:
* wtf/FastBitVector.h: Added.
(WTF):
(FastBitVector):
(WTF::FastBitVector::FastBitVector):
(WTF::FastBitVector::operator=):
(WTF::FastBitVector::numBits):
(WTF::FastBitVector::resize):
(WTF::FastBitVector::setAll):
(WTF::FastBitVector::clearAll):
(WTF::FastBitVector::set):
(WTF::FastBitVector::setAndCheck):
(WTF::FastBitVector::equals):
(WTF::FastBitVector::merge):
(WTF::FastBitVector::filter):
(WTF::FastBitVector::exclude):
(WTF::FastBitVector::clear):
(WTF::FastBitVector::get):
(WTF::FastBitVector::arrayLength):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@117861 268f45cc-cd09-0410-ab3c-d52691b4dbfc

16 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/GNUmakefile.list.am
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/Target.pri
Source/JavaScriptCore/bytecode/CodeBlock.cpp
Source/JavaScriptCore/dfg/DFGDominators.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGDominators.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGDriver.cpp
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/WTF/ChangeLog
Source/WTF/GNUmakefile.list.am
Source/WTF/WTF.vcproj/WTF.vcproj
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/FastBitVector.h [new file with mode: 0644]

index b9e19a8..7aa332c 100644 (file)
@@ -66,6 +66,7 @@ SET(JavaScriptCore_SOURCES
     dfg/DFGConstantFoldingPhase.cpp
     dfg/DFGCorrectableJumpPoint.cpp
     dfg/DFGCSEPhase.cpp
+    dfg/DFGDominators.cpp
     dfg/DFGDriver.cpp
     dfg/DFGFixupPhase.cpp
     dfg/DFGGraph.cpp
index 2666426..e669cef 100644 (file)
@@ -1,3 +1,47 @@
+2012-05-21  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should be able to compute dominators
+        https://bugs.webkit.org/show_bug.cgi?id=85269
+
+        Reviewed by Oliver Hunt.
+        
+        Merged r115754 from dfgopt.
+        
+        Implements a naive dominator calculator, which is currently just used to
+        print information in graph dumps. I've enabled it by default mainly to
+        be able to track its performance impact. So far it appears that there is
+        none, which is unsurprising given that the number of basic blocks in most
+        procedures is small.
+        
+        Also tweaked bytecode dumping to reveal more useful information about the
+        nature of the code block.
+
+        * CMakeLists.txt:
+        * GNUmakefile.list.am:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * Target.pri:
+        * bytecode/CodeBlock.cpp:
+        (JSC::CodeBlock::dump):
+        * dfg/DFGDominators.cpp: Added.
+        (DFG):
+        (JSC::DFG::Dominators::Dominators):
+        (JSC::DFG::Dominators::~Dominators):
+        (JSC::DFG::Dominators::compute):
+        (JSC::DFG::Dominators::iterateForBlock):
+        * dfg/DFGDominators.h: Added.
+        (DFG):
+        (Dominators):
+        (JSC::DFG::Dominators::invalidate):
+        (JSC::DFG::Dominators::computeIfNecessary):
+        (JSC::DFG::Dominators::isValid):
+        (JSC::DFG::Dominators::dominates):
+        * dfg/DFGDriver.cpp:
+        (JSC::DFG::compile):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::dump):
+        * dfg/DFGGraph.h:
+        (Graph):
+
 2012-05-21  Michael Saboff  <msaboff@apple.com>
 
         Cleanup of Calls to operationStrCat and operationNewArray and Use Constructor after r117729
index 6cd3a65..17b0498 100644 (file)
@@ -161,6 +161,8 @@ javascriptcore_sources += \
        Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.h \
        Source/JavaScriptCore/dfg/DFGCSEPhase.cpp \
        Source/JavaScriptCore/dfg/DFGCSEPhase.h \
+       Source/JavaScriptCore/dfg/DFGDominators.cpp \
+       Source/JavaScriptCore/dfg/DFGDominators.h \
        Source/JavaScriptCore/dfg/DFGDoubleFormatState.h \
        Source/JavaScriptCore/dfg/DFGDriver.cpp \
        Source/JavaScriptCore/dfg/DFGDriver.h \
index a5ed0c3..157ce9d 100644 (file)
                0FC81516140511B500CFA603 /* VTableSpectrum.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC815121405118600CFA603 /* VTableSpectrum.cpp */; };
                0FD3C82614115D4000FD81CB /* DFGDriver.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD3C82014115CF800FD81CB /* DFGDriver.cpp */; };
                0FD3C82814115D4F00FD81CB /* DFGDriver.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD3C82214115D0E00FD81CB /* DFGDriver.h */; };
+               0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */; };
+               0FD81AD3154FB4F000983E72 /* DFGDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AD0154FB4EB00983E72 /* DFGDominators.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FD82E2114172CE300179C94 /* DFGCapabilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */; };
                0FD82E39141AB14D00179C94 /* CompactJITCodeMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD82E37141AB14200179C94 /* CompactJITCodeMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FD82E54141DAEEE00179C94 /* PredictedType.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD82E4F141DAEA100179C94 /* PredictedType.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FC815141405118D00CFA603 /* VTableSpectrum.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VTableSpectrum.h; sourceTree = "<group>"; };
                0FD3C82014115CF800FD81CB /* DFGDriver.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGDriver.cpp; path = dfg/DFGDriver.cpp; sourceTree = "<group>"; };
                0FD3C82214115D0E00FD81CB /* DFGDriver.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGDriver.h; path = dfg/DFGDriver.h; sourceTree = "<group>"; };
+               0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGDominators.cpp; path = dfg/DFGDominators.cpp; sourceTree = "<group>"; };
+               0FD81AD0154FB4EB00983E72 /* DFGDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGDominators.h; path = dfg/DFGDominators.h; sourceTree = "<group>"; };
                0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGCapabilities.cpp; path = dfg/DFGCapabilities.cpp; sourceTree = "<group>"; };
                0FD82E1F14172C2F00179C94 /* DFGCapabilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGCapabilities.h; path = dfg/DFGCapabilities.h; sourceTree = "<group>"; };
                0FD82E37141AB14200179C94 /* CompactJITCodeMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CompactJITCodeMap.h; sourceTree = "<group>"; };
                                0F3B3A18153E68EF003ED0FF /* DFGConstantFoldingPhase.h */,
                                0FC0979D146B271E00CF2442 /* DFGCorrectableJumpPoint.cpp */,
                                0FC0979A146A772000CF2442 /* DFGCorrectableJumpPoint.h */,
+                               0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */,
+                               0FD81AD0154FB4EB00983E72 /* DFGDominators.h */,
                                0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */,
                                0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
                                0FD3C82214115D0E00FD81CB /* DFGDriver.h */,
                                0F1E3A67153A21E2000F9456 /* DFGSilentRegisterSavePlan.h in Headers */,
                                0F3B3A281544C997003ED0FF /* DFGCFGSimplificationPhase.h in Headers */,
                                0F3B3A2C15475002003ED0FF /* DFGValidate.h in Headers */,
+                               0FD81AD3154FB4F000983E72 /* DFGDominators.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
                                0F3B3A1A153E68F2003ED0FF /* DFGConstantFoldingPhase.cpp in Sources */,
                                0F3B3A271544C995003ED0FF /* DFGCFGSimplificationPhase.cpp in Sources */,
                                0F3B3A2B15475000003ED0FF /* DFGValidate.cpp in Sources */,
+                               0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index b43cdf0..793afc7 100644 (file)
@@ -97,6 +97,7 @@ SOURCES += \
     dfg/DFGConstantFoldingPhase.cpp \
     dfg/DFGCorrectableJumpPoint.cpp \
     dfg/DFGCSEPhase.cpp \
+    dfg/DFGDominators.cpp \
     dfg/DFGDriver.cpp \
     dfg/DFGFixupPhase.cpp \
     dfg/DFGGraph.cpp \
index a702564..e4e48fa 100644 (file)
@@ -475,10 +475,23 @@ void CodeBlock::dump(ExecState* exec)
     for (size_t i = 0; i < instructions().size(); i += opcodeLengths[exec->interpreter()->getOpcodeID(instructions()[i].u.opcode)])
         ++instructionCount;
 
-    dataLog("%lu m_instructions; %lu bytes at %p; %d parameter(s); %d callee register(s); %d variable(s)\n\n",
+    dataLog(
+        "%lu m_instructions; %lu bytes at %p (%s); %d parameter(s); %d callee register(s); %d variable(s)",
         static_cast<unsigned long>(instructions().size()),
         static_cast<unsigned long>(instructions().size() * sizeof(Instruction)),
-        this, m_numParameters, m_numCalleeRegisters, m_numVars);
+        this, codeTypeToString(codeType()), m_numParameters, m_numCalleeRegisters,
+        m_numVars);
+    if (m_numCapturedVars)
+        dataLog("; %d captured var(s)", m_numCapturedVars);
+    if (usesArguments()) {
+        dataLog(
+            "; uses arguments, in r%d, r%d",
+            argumentsRegister(),
+            unmodifiedArgumentsRegister(argumentsRegister()));
+    }
+    if (needsFullScopeChain() && codeType() == FunctionCode)
+        dataLog("; activation in r%d", activationRegister());
+    dataLog("\n\n");
 
     Vector<Instruction>::const_iterator begin = instructions().begin();
     Vector<Instruction>::const_iterator end = instructions().end();
diff --git a/Source/JavaScriptCore/dfg/DFGDominators.cpp b/Source/JavaScriptCore/dfg/DFGDominators.cpp
new file mode 100644 (file)
index 0000000..0b23d96
--- /dev/null
@@ -0,0 +1,109 @@
+/*
+ * Copyright (C) 2011 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. 
+ */
+
+#include "config.h"
+#include "DFGDominators.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+
+namespace JSC { namespace DFG {
+
+Dominators::Dominators()
+    : m_valid(false)
+{
+}
+
+Dominators::~Dominators()
+{
+}
+
+void Dominators::compute(Graph& graph)
+{
+    // This implements a naive dominator solver.
+    
+    ASSERT(graph.m_blocks[0]->m_predecessors.isEmpty());
+    
+    unsigned numBlocks = graph.m_blocks.size();
+    
+    if (numBlocks > m_results.size()) {
+        m_results.grow(numBlocks);
+        for (unsigned i = numBlocks; i--;)
+            m_results[i].resize(numBlocks);
+        m_scratch.resize(numBlocks);
+    }
+    
+    m_results[0].clearAll();
+    m_results[0].set(0);
+    
+    m_scratch.clearAll();
+    for (unsigned i = numBlocks; i--;) {
+        if (!graph.m_blocks[i])
+            continue;
+        m_scratch.set(i);
+    }
+    
+    for (unsigned i = numBlocks; i-- > 1;) {
+        if (!graph.m_blocks[i] || graph.m_blocks[i]->m_predecessors.isEmpty())
+            m_results[i].clearAll();
+        else
+            m_results[i].set(m_scratch);
+    }
+    
+    bool changed;
+    do {
+        changed = false;
+        for (unsigned i = 1; i < numBlocks; ++i)
+            changed |= iterateForBlock(graph, i);
+        if (!changed)
+            break;
+        
+        changed = false;
+        for (unsigned i = numBlocks; i-- > 1;)
+            changed |= iterateForBlock(graph, i);
+    } while (changed);
+    
+    m_valid = true;
+}
+
+bool Dominators::iterateForBlock(Graph& graph, BlockIndex i)
+{
+    BasicBlock* block = graph.m_blocks[i].get();
+    if (!block)
+        return false;
+    if (block->m_predecessors.isEmpty())
+        return false;
+    m_scratch.set(m_results[block->m_predecessors[0]]);
+    for (unsigned j = block->m_predecessors.size(); j-- > 1;)
+        m_scratch.filter(m_results[block->m_predecessors[j]]);
+    m_scratch.set(i);
+    return m_results[i].setAndCheck(m_scratch);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGDominators.h b/Source/JavaScriptCore/dfg/DFGDominators.h
new file mode 100644 (file)
index 0000000..8eee3e8
--- /dev/null
@@ -0,0 +1,77 @@
+/*
+ * Copyright (C) 2011 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 DFGDominators_h
+#define DFGDominators_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCommon.h"
+#include <wtf/FastBitVector.h>
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+class Dominators {
+public:
+    Dominators();
+    ~Dominators();
+    
+    void compute(Graph& graph);
+    void invalidate()
+    {
+        m_valid = false;
+    }
+    void computeIfNecessary(Graph& graph)
+    {
+        if (m_valid)
+            return;
+        compute(graph);
+    }
+    
+    bool isValid() const { return m_valid; }
+    
+    bool dominates(BlockIndex from, BlockIndex to) const
+    {
+        ASSERT(isValid());
+        return m_results[to].get(from);
+    }
+    
+private:
+    bool iterateForBlock(Graph& graph, BlockIndex);
+    
+    Vector<FastBitVector> m_results;
+    FastBitVector m_scratch;
+    bool m_valid;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGDominators_h
index 77fd3d1..feb8ab1 100644 (file)
@@ -87,6 +87,7 @@ inline bool compile(CompileMode compileMode, ExecState* exec, CodeBlock* codeBlo
 #if DFG_ENABLE(DEBUG_VERBOSE)
     dataLog("DFG optimization fixpoint converged in %u iterations.\n", cnt);
 #endif
+    dfg.m_dominators.compute(dfg);
     performVirtualRegisterAllocation(dfg);
 
 #if DFG_ENABLE(DEBUG_VERBOSE)
index fc2fbb8..b14585a 100644 (file)
@@ -283,6 +283,22 @@ void Graph::dump()
         for (size_t i = 0; i < block->m_predecessors.size(); ++i)
             dataLog(" #%u", block->m_predecessors[i]);
         dataLog("\n");
+        if (m_dominators.isValid()) {
+            dataLog("  Dominated by:");
+            for (size_t i = 0; i < m_blocks.size(); ++i) {
+                if (!m_dominators.dominates(i, b))
+                    continue;
+                dataLog(" #%lu", i);
+            }
+            dataLog("\n");
+            dataLog("  Dominates:");
+            for (size_t i = 0; i < m_blocks.size(); ++i) {
+                if (!m_dominators.dominates(b, i))
+                    continue;
+                dataLog(" #%lu", i);
+            }
+            dataLog("\n");
+        }
         dataLog("  Phi Nodes:\n");
         for (size_t i = 0; i < block->phis.size(); ++i) {
             dumpCodeOrigin(lastNodeIndex, block->phis[i]);
index 590d6ed..c40ce49 100644 (file)
 #ifndef DFGGraph_h
 #define DFGGraph_h
 
+#include <wtf/Platform.h>
+
 #if ENABLE(DFG_JIT)
 
 #include "CodeBlock.h"
 #include "DFGArgumentPosition.h"
 #include "DFGAssemblyHelpers.h"
 #include "DFGBasicBlock.h"
+#include "DFGDominators.h"
 #include "DFGNode.h"
 #include "MethodOfGettingAValueProfile.h"
 #include "RegisterFile.h"
@@ -450,6 +453,7 @@ public:
     SegmentedVector<StructureSet, 16> m_structureSet;
     SegmentedVector<StructureTransitionData, 8> m_structureTransitionData;
     BitVector m_preservedVars;
+    Dominators m_dominators;
     unsigned m_localVars;
     unsigned m_parameterSlots;
 private:
index 04a6c25..cbd5d95 100644 (file)
@@ -1,3 +1,40 @@
+2012-05-21  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG should be able to compute dominators
+        https://bugs.webkit.org/show_bug.cgi?id=85269
+
+        Reviewed by Oliver Hunt.
+        
+        Merged r115754 from dfgopt.
+        
+        Added a bitvector class suitable for cheap static analysis. This class
+        differs from BitVector in that instead of optimizing for space, it
+        optimizes for execution time. Its API is also somewhat less friendly,
+        which is intentional; it's meant to be used in places where you know
+        up front how bit your bitvectors are going to be.
+
+        * GNUmakefile.list.am:
+        * WTF.vcproj/WTF.vcproj:
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/FastBitVector.h: Added.
+        (WTF):
+        (FastBitVector):
+        (WTF::FastBitVector::FastBitVector):
+        (WTF::FastBitVector::operator=):
+        (WTF::FastBitVector::numBits):
+        (WTF::FastBitVector::resize):
+        (WTF::FastBitVector::setAll):
+        (WTF::FastBitVector::clearAll):
+        (WTF::FastBitVector::set):
+        (WTF::FastBitVector::setAndCheck):
+        (WTF::FastBitVector::equals):
+        (WTF::FastBitVector::merge):
+        (WTF::FastBitVector::filter):
+        (WTF::FastBitVector::exclude):
+        (WTF::FastBitVector::clear):
+        (WTF::FastBitVector::get):
+        (WTF::FastBitVector::arrayLength):
+
 2012-05-15  Gavin Barraclough  <barraclough@apple.com>
 
         Add support for private names
index 1955666..3f9aea9 100644 (file)
@@ -43,6 +43,7 @@ wtf_sources += \
     Source/WTF/wtf/Encoder.h \
     Source/WTF/wtf/ExportMacros.h \
     Source/WTF/wtf/FastAllocBase.h \
+    Source/WTF/wtf/FastBitVector.h \
     Source/WTF/wtf/FastMalloc.cpp \
     Source/WTF/wtf/FastMalloc.h \
     Source/WTF/wtf/FixedArray.h \
index 0882695..0392a8d 100644 (file)
                        >
                </File>
                <File
+                       RelativePath="..\wtf\FastBitVector.h"
+                       >
+               </File>
+               <File
                        RelativePath="..\wtf\FastMalloc.cpp"
                        >
                        <FileConfiguration
index 023e398..e75142f 100644 (file)
@@ -7,6 +7,7 @@
        objects = {
 
 /* Begin PBXBuildFile section */
+               0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AC4154FB22E00983E72 /* FastBitVector.h */; settings = {ATTRIBUTES = (); }; };
                4F0321BC156AA8D1006EBAF6 /* BitArray.h in Headers */ = {isa = PBXBuildFile; fileRef = 4F0321BB156AA8D1006EBAF6 /* BitArray.h */; };
                A876DBD8151816E500DADB95 /* Platform.h in Headers */ = {isa = PBXBuildFile; fileRef = A876DBD7151816E500DADB95 /* Platform.h */; };
                A8A4737F151A825B004123FF /* Alignment.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47254151A825A004123FF /* Alignment.h */; };
 /* End PBXBuildFile section */
 
 /* Begin PBXFileReference section */
+               0FD81AC4154FB22E00983E72 /* FastBitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FastBitVector.h; sourceTree = "<group>"; };
                4F0321BB156AA8D1006EBAF6 /* BitArray.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BitArray.h; sourceTree = "<group>"; };
                5D247B6214689B8600E78B76 /* libWTF.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libWTF.a; sourceTree = BUILT_PRODUCTS_DIR; };
                5D247B6E14689C4700E78B76 /* Base.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = Base.xcconfig; sourceTree = "<group>"; };
                                A8A4729E151A825A004123FF /* Encoder.h */,
                                A8A4729F151A825A004123FF /* ExportMacros.h */,
                                A8A472A0151A825A004123FF /* FastAllocBase.h */,
+                               0FD81AC4154FB22E00983E72 /* FastBitVector.h */,
                                A8A472A1151A825A004123FF /* FastMalloc.cpp */,
                                A8A472A2151A825A004123FF /* FastMalloc.h */,
                                A8A472A3151A825A004123FF /* FixedArray.h */,
                                A8A47480151A825B004123FF /* VMTags.h in Headers */,
                                A8A47487151A825B004123FF /* WTFThreadData.h in Headers */,
                                A8A4748C151A8264004123FF /* config.h in Headers */,
+                               0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
diff --git a/Source/WTF/wtf/FastBitVector.h b/Source/WTF/wtf/FastBitVector.h
new file mode 100644 (file)
index 0000000..49aa52d
--- /dev/null
@@ -0,0 +1,171 @@
+/*
+ * Copyright (C) 2012 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 FastBitVector_h
+#define FastBitVector_h
+
+#include <wtf/FastMalloc.h>
+#include <wtf/OwnArrayPtr.h>
+#include <wtf/PassOwnArrayPtr.h>
+#include <wtf/StdLibExtras.h>
+
+namespace WTF {
+
+class FastBitVector {
+public:
+    FastBitVector() : m_numBits(0) { }
+    
+    FastBitVector(const FastBitVector& other)
+        : m_numBits(0)
+    {
+        *this = other;
+    }
+    
+    FastBitVector& operator=(const FastBitVector& other)
+    {
+        size_t length = other.arrayLength();
+        PassOwnArrayPtr<uint32_t> newArray = adoptArrayPtr(
+            static_cast<uint32_t*>(fastCalloc(length, 4)));
+        memcpy(newArray.get(), other.m_array.get(), length * 4);
+        m_array = newArray;
+        m_numBits = other.m_numBits;
+        return *this;
+    }
+    
+    size_t numBits() const { return m_numBits; }
+    
+    void resize(size_t numBits)
+    {
+        // Use fastCalloc instead of fastRealloc because we expect the common
+        // use case for this method to be initializing the size of the bitvector.
+        
+        size_t newLength = (numBits + 31) >> 5;
+        PassOwnArrayPtr<uint32_t> newArray = adoptArrayPtr(
+            static_cast<uint32_t*>(fastCalloc(newLength, 4)));
+        memcpy(newArray.get(), m_array.get(), arrayLength() * 4);
+        m_array = newArray;
+        m_numBits = numBits;
+    }
+    
+    void setAll()
+    {
+        memset(m_array.get(), 255, arrayLength() * 4);
+    }
+    
+    void clearAll()
+    {
+        memset(m_array.get(), 0, arrayLength() * 4);
+    }
+    
+    void set(const FastBitVector& other)
+    {
+        ASSERT(m_numBits == other.m_numBits);
+        memcpy(m_array.get(), other.m_array.get(), arrayLength() * 4);
+    }
+    
+    bool setAndCheck(const FastBitVector& other)
+    {
+        bool changed = false;
+        ASSERT(m_numBits == other.m_numBits);
+        for (unsigned i = arrayLength(); i--;) {
+            if (m_array[i] == other.m_array[i])
+                continue;
+            m_array[i] = other.m_array[i];
+            changed = true;
+        }
+        return changed;
+    }
+    
+    bool equals(const FastBitVector& other) const
+    {
+        ASSERT(m_numBits == other.m_numBits);
+        // Use my own comparison loop because memcmp does more than what I want
+        // and bcmp is not as standard.
+        for (unsigned i = arrayLength(); i--;) {
+            if (m_array[i] != other.m_array[i])
+                return false;
+        }
+        return true;
+    }
+    
+    void merge(const FastBitVector& other)
+    {
+        ASSERT(m_numBits == other.m_numBits);
+        for (unsigned i = arrayLength(); i--;)
+            m_array[i] |= other.m_array[i];
+    }
+    
+    void filter(const FastBitVector& other)
+    {
+        ASSERT(m_numBits == other.m_numBits);
+        for (unsigned i = arrayLength(); i--;)
+            m_array[i] &= other.m_array[i];
+    }
+    
+    void exclude(const FastBitVector& other)
+    {
+        ASSERT(m_numBits == other.m_numBits);
+        for (unsigned i = arrayLength(); i--;)
+            m_array[i] &= ~other.m_array[i];
+    }
+    
+    void set(size_t i)
+    {
+        ASSERT(i < m_numBits);
+        m_array[i >> 5] |= (1 << (i & 31));
+    }
+    
+    void clear(size_t i)
+    {
+        ASSERT(i < m_numBits);
+        m_array[i >> 5] &= ~(1 << (i & 31));
+    }
+    
+    void set(size_t i, bool value)
+    {
+        if (value)
+            set(i);
+        else
+            clear(i);
+    }
+    
+    bool get(size_t i) const
+    {
+        ASSERT(i < m_numBits);
+        return !!(m_array[i >> 5] & (1 << (i & 31)));
+    }
+private:
+    size_t arrayLength() const { return (m_numBits + 31) >> 5; }
+    
+    OwnArrayPtr<uint32_t> m_array;
+    size_t m_numBits;
+};
+
+} // namespace WTF
+
+using WTF::FastBitVector;
+
+#endif // FastBitVector_h
+