Diff
Modified: branches/dfgopt/Source/_javascript_Core/ChangeLog (115753 => 115754)
--- branches/dfgopt/Source/_javascript_Core/ChangeLog 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/_javascript_Core/ChangeLog 2012-05-01 22:30:42 UTC (rev 115754)
@@ -1,3 +1,42 @@
+2012-05-01 Filip Pizlo <fpi...@apple.com>
+
+ DFG should be able to compute dominators
+ https://bugs.webkit.org/show_bug.cgi?id=85269
+
+ Reviewed by Oliver Hunt.
+
+ 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.
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * 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-04-30 Filip Pizlo <fpi...@apple.com>
Bytecode dumps should contain data about the state of get_by_id caches
Modified: branches/dfgopt/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (115753 => 115754)
--- branches/dfgopt/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2012-05-01 22:30:42 UTC (rev 115754)
@@ -174,6 +174,8 @@
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, ); }; };
@@ -853,6 +855,8 @@
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>"; };
@@ -2064,6 +2068,8 @@
0F3B3A18153E68EF003ED0FF /* DFGConstantFoldingPhase.h */,
0FC0979D146B271E00CF2442 /* DFGCorrectableJumpPoint.cpp */,
0FC0979A146A772000CF2442 /* DFGCorrectableJumpPoint.h */,
+ 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */,
+ 0FD81AD0154FB4EB00983E72 /* DFGDominators.h */,
0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */,
0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
0FD3C82214115D0E00FD81CB /* DFGDriver.h */,
@@ -2597,6 +2603,7 @@
0F1E3A67153A21E2000F9456 /* DFGSilentRegisterSavePlan.h in Headers */,
0F3B3A281544C997003ED0FF /* DFGCFGSimplificationPhase.h in Headers */,
0F3B3A2C15475002003ED0FF /* DFGValidate.h in Headers */,
+ 0FD81AD3154FB4F000983E72 /* DFGDominators.h in Headers */,
);
runOnlyForDeploymentPostprocessing = 0;
};
@@ -3163,6 +3170,7 @@
0F3B3A1A153E68F2003ED0FF /* DFGConstantFoldingPhase.cpp in Sources */,
0F3B3A271544C995003ED0FF /* DFGCFGSimplificationPhase.cpp in Sources */,
0F3B3A2B15475000003ED0FF /* DFGValidate.cpp in Sources */,
+ 0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
Modified: branches/dfgopt/Source/_javascript_Core/bytecode/CodeBlock.cpp (115753 => 115754)
--- branches/dfgopt/Source/_javascript_Core/bytecode/CodeBlock.cpp 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/_javascript_Core/bytecode/CodeBlock.cpp 2012-05-01 22:30:42 UTC (rev 115754)
@@ -475,10 +475,23 @@
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();
Added: branches/dfgopt/Source/_javascript_Core/dfg/DFGDominators.cpp (0 => 115754)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGDominators.cpp (rev 0)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGDominators.cpp 2012-05-01 22:30:42 UTC (rev 115754)
@@ -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)
+
Added: branches/dfgopt/Source/_javascript_Core/dfg/DFGDominators.h (0 => 115754)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGDominators.h (rev 0)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGDominators.h 2012-05-01 22:30:42 UTC (rev 115754)
@@ -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
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGDriver.cpp (115753 => 115754)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGDriver.cpp 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGDriver.cpp 2012-05-01 22:30:42 UTC (rev 115754)
@@ -81,6 +81,7 @@
#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)
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.cpp (115753 => 115754)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.cpp 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.cpp 2012-05-01 22:30:42 UTC (rev 115754)
@@ -283,6 +283,22 @@
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]);
Modified: branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.h (115753 => 115754)
--- branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.h 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/_javascript_Core/dfg/DFGGraph.h 2012-05-01 22:30:42 UTC (rev 115754)
@@ -26,12 +26,15 @@
#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 @@
SegmentedVector<StructureSet, 16> m_structureSet;
SegmentedVector<StructureTransitionData, 8> m_structureTransitionData;
BitVector m_preservedVars;
+ Dominators m_dominators;
unsigned m_localVars;
unsigned m_parameterSlots;
private:
Modified: branches/dfgopt/Source/WTF/ChangeLog (115753 => 115754)
--- branches/dfgopt/Source/WTF/ChangeLog 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/WTF/ChangeLog 2012-05-01 22:30:42 UTC (rev 115754)
@@ -1,3 +1,37 @@
+2012-05-01 Filip Pizlo <fpi...@apple.com>
+
+ DFG should be able to compute dominators
+ https://bugs.webkit.org/show_bug.cgi?id=85269
+
+ Reviewed by Oliver Hunt.
+
+ 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.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/FastBitVector.h: Added.
+ (WTF):
+ (FastBitVector):
+ (WTF::FastBitVector::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-04-16 Nico Weber <tha...@chromium.org>
Make NullPtr.h compile with clang -std=c++11 and libstdc++4.2
Modified: branches/dfgopt/Source/WTF/WTF.xcodeproj/project.pbxproj (115753 => 115754)
--- branches/dfgopt/Source/WTF/WTF.xcodeproj/project.pbxproj 2012-05-01 22:25:36 UTC (rev 115753)
+++ branches/dfgopt/Source/WTF/WTF.xcodeproj/project.pbxproj 2012-05-01 22:30:42 UTC (rev 115754)
@@ -7,6 +7,7 @@
objects = {
/* Begin PBXBuildFile section */
+ 0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AC4154FB22E00983E72 /* FastBitVector.h */; settings = {ATTRIBUTES = (); }; };
A876DBD8151816E500DADB95 /* Platform.h in Headers */ = {isa = PBXBuildFile; fileRef = A876DBD7151816E500DADB95 /* Platform.h */; };
A8A4737F151A825B004123FF /* Alignment.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47254151A825A004123FF /* Alignment.h */; };
A8A47380151A825B004123FF /* AlwaysInline.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47255151A825A004123FF /* AlwaysInline.h */; };
@@ -242,6 +243,7 @@
/* End PBXBuildFile section */
/* Begin PBXFileReference section */
+ 0FD81AC4154FB22E00983E72 /* FastBitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FastBitVector.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>"; };
5D247B6F14689C4700E78B76 /* CompilerVersion.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = CompilerVersion.xcconfig; sourceTree = "<group>"; };
@@ -585,6 +587,7 @@
A8A4729E151A825A004123FF /* Encoder.h */,
A8A4729F151A825A004123FF /* ExportMacros.h */,
A8A472A0151A825A004123FF /* FastAllocBase.h */,
+ 0FD81AC4154FB22E00983E72 /* FastBitVector.h */,
A8A472A1151A825A004123FF /* FastMalloc.cpp */,
A8A472A2151A825A004123FF /* FastMalloc.h */,
A8A472A3151A825A004123FF /* FixedArray.h */,
@@ -1030,6 +1033,7 @@
A8A47480151A825B004123FF /* VMTags.h in Headers */,
A8A47487151A825B004123FF /* WTFThreadData.h in Headers */,
A8A4748C151A8264004123FF /* config.h in Headers */,
+ 0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */,
);
runOnlyForDeploymentPostprocessing = 0;
};
Added: branches/dfgopt/Source/WTF/wtf/FastBitVector.h (0 => 115754)
--- branches/dfgopt/Source/WTF/wtf/FastBitVector.h (rev 0)
+++ branches/dfgopt/Source/WTF/wtf/FastBitVector.h 2012-05-01 22:30:42 UTC (rev 115754)
@@ -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
+
