Diff
Modified: trunk/Source/_javascript_Core/CMakeLists.txt (195416 => 195417)
--- trunk/Source/_javascript_Core/CMakeLists.txt 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/CMakeLists.txt 2016-01-21 19:54:51 UTC (rev 195417)
@@ -120,6 +120,7 @@
b3/B3DataSection.cpp
b3/B3DuplicateTails.cpp
b3/B3Effects.cpp
+ b3/B3EliminateCommonSubexpressions.cpp
b3/B3FixSSA.cpp
b3/B3FoldPathConstants.cpp
b3/B3FrequencyClass.cpp
@@ -142,6 +143,7 @@
b3/B3PhaseScope.cpp
b3/B3PhiChildren.cpp
b3/B3Procedure.cpp
+ b3/B3PureCSE.cpp
b3/B3ReduceDoubleToFloat.cpp
b3/B3ReduceStrength.cpp
b3/B3SSACalculator.cpp
Modified: trunk/Source/_javascript_Core/ChangeLog (195416 => 195417)
--- trunk/Source/_javascript_Core/ChangeLog 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-01-21 19:54:51 UTC (rev 195417)
@@ -1,3 +1,49 @@
+2016-01-21 Filip Pizlo <[email protected]>
+
+ B3 should have load elimination
+ https://bugs.webkit.org/show_bug.cgi?id=153288
+
+ Reviewed by Geoffrey Garen.
+
+ This adds a complete GCSE pass that includes load elimination. It would have been super hard
+ to make this work as part of the reduceStrength() fixpoint, since GCSE needs to analyze
+ control flow and reduceStrength() is messing with control flow. So, I did a compromise: I
+ factored out the pure CSE that reduceStrength() was already doing, and now we have:
+
+ - reduceStrength() still does pure CSE using the new PureCSE helper.
+
+ - eliminateCommonSubexpressions() is a separate phase that does general CSE. It uses the
+ PureCSE helper for pure values and does its own special thing for memory values.
+
+ Unfortunately, this doesn't help any benchmark right now. It doesn't hurt anything, either,
+ and it's likely to become a bigger pay-off once we implement other features, like mapping
+ FTL's abstract heaps onto B3's heap ranges.
+
+ * CMakeLists.txt:
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * b3/B3EliminateCommonSubexpressions.cpp: Added.
+ (JSC::B3::eliminateCommonSubexpressions):
+ * b3/B3EliminateCommonSubexpressions.h: Added.
+ * b3/B3Generate.cpp:
+ (JSC::B3::generateToAir):
+ * b3/B3HeapRange.h:
+ (JSC::B3::HeapRange::HeapRange):
+ * b3/B3InsertionSet.h:
+ (JSC::B3::InsertionSet::InsertionSet):
+ (JSC::B3::InsertionSet::isEmpty):
+ (JSC::B3::InsertionSet::code):
+ (JSC::B3::InsertionSet::appendInsertion):
+ * b3/B3MemoryValue.h:
+ * b3/B3PureCSE.cpp: Added.
+ (JSC::B3::PureCSE::PureCSE):
+ (JSC::B3::PureCSE::~PureCSE):
+ (JSC::B3::PureCSE::clear):
+ (JSC::B3::PureCSE::process):
+ * b3/B3PureCSE.h: Added.
+ * b3/B3ReduceStrength.cpp:
+ * b3/B3ReduceStrength.h:
+ * b3/B3Validate.cpp:
+
2016-01-21 Keith Miller <[email protected]>
Fix bug in TypedArray.prototype.set and add tests
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (195416 => 195417)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-01-21 19:54:51 UTC (rev 195417)
@@ -467,6 +467,10 @@
0F7025AA1714B0FC00382C0E /* DFGOSRExitCompilerCommon.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F7025A81714B0F800382C0E /* DFGOSRExitCompilerCommon.h */; };
0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */; };
0F714CA516EA92F200F3EBEB /* DFGBackwardsPropagationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */; };
+ 0F725CA71C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */; };
+ 0F725CA81C503DED00AD943A /* B3EliminateCommonSubexpressions.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */; };
+ 0F725CA91C503DED00AD943A /* B3PureCSE.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CA51C503DED00AD943A /* B3PureCSE.cpp */; };
+ 0F725CAA1C503DED00AD943A /* B3PureCSE.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CA61C503DED00AD943A /* B3PureCSE.h */; };
0F725CAF1C506D3B00AD943A /* B3FoldPathConstants.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */; };
0F725CB01C506D3B00AD943A /* B3FoldPathConstants.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */; };
0F743BAA16B88249009F9277 /* ARM64Disassembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 652A3A201651C66100A80AFE /* ARM64Disassembler.cpp */; };
@@ -2647,6 +2651,10 @@
0F7025A81714B0F800382C0E /* DFGOSRExitCompilerCommon.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGOSRExitCompilerCommon.h; path = dfg/DFGOSRExitCompilerCommon.h; sourceTree = "<group>"; };
0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBackwardsPropagationPhase.cpp; path = dfg/DFGBackwardsPropagationPhase.cpp; sourceTree = "<group>"; };
0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsPropagationPhase.h; path = dfg/DFGBackwardsPropagationPhase.h; sourceTree = "<group>"; };
+ 0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3EliminateCommonSubexpressions.cpp; path = b3/B3EliminateCommonSubexpressions.cpp; sourceTree = "<group>"; };
+ 0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3EliminateCommonSubexpressions.h; path = b3/B3EliminateCommonSubexpressions.h; sourceTree = "<group>"; };
+ 0F725CA51C503DED00AD943A /* B3PureCSE.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3PureCSE.cpp; path = b3/B3PureCSE.cpp; sourceTree = "<group>"; };
+ 0F725CA61C503DED00AD943A /* B3PureCSE.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3PureCSE.h; path = b3/B3PureCSE.h; sourceTree = "<group>"; };
0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3FoldPathConstants.cpp; path = b3/B3FoldPathConstants.cpp; sourceTree = "<group>"; };
0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3FoldPathConstants.h; path = b3/B3FoldPathConstants.h; sourceTree = "<group>"; };
0F766D1C15A5028D008F363E /* JITStubRoutine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITStubRoutine.h; sourceTree = "<group>"; };
@@ -4783,6 +4791,8 @@
0F6B8AD71C4EDDA200969052 /* B3DuplicateTails.h */,
0FEC85C41BE16F5A0080FF74 /* B3Effects.cpp */,
0FEC85BE1BE167A00080FF74 /* B3Effects.h */,
+ 0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */,
+ 0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */,
0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */,
0F6B8AE11C4EFE1700969052 /* B3FixSSA.h */,
0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */,
@@ -4834,6 +4844,8 @@
0FEC84E11BDACDAC0080FF74 /* B3Procedure.cpp */,
0FEC84E21BDACDAC0080FF74 /* B3Procedure.h */,
0FEC84E31BDACDAC0080FF74 /* B3ProcedureInlines.h */,
+ 0F725CA51C503DED00AD943A /* B3PureCSE.cpp */,
+ 0F725CA61C503DED00AD943A /* B3PureCSE.h */,
43422A641C16221E00E2EB98 /* B3ReduceDoubleToFloat.cpp */,
43422A651C16221E00E2EB98 /* B3ReduceDoubleToFloat.h */,
0FEC85B71BE1462F0080FF74 /* B3ReduceStrength.cpp */,
@@ -7324,6 +7336,7 @@
0FC97F3E18202119002C9B26 /* DFGInvalidationPointInjectionPhase.h in Headers */,
0FEA0A34170D40BF00BB722C /* DFGJITCode.h in Headers */,
86EC9DCC1328DF82002B2AD7 /* DFGJITCompiler.h in Headers */,
+ 0F725CA81C503DED00AD943A /* B3EliminateCommonSubexpressions.h in Headers */,
A78A9779179738B8009DF744 /* DFGJITFinalizer.h in Headers */,
0FC97F4018202119002C9B26 /* DFGJumpReplacement.h in Headers */,
A73A535B1799CD5D00170C19 /* DFGLazyJSValue.h in Headers */,
@@ -7651,6 +7664,7 @@
A1D792FD1B43864B004516F5 /* IntlNumberFormat.h in Headers */,
A1D792FF1B43864B004516F5 /* IntlNumberFormatConstructor.h in Headers */,
A125846E1B45A36000CC7F6C /* IntlNumberFormatConstructor.lut.h in Headers */,
+ 0F725CAA1C503DED00AD943A /* B3PureCSE.h in Headers */,
A1D793011B43864B004516F5 /* IntlNumberFormatPrototype.h in Headers */,
A125846F1B45A36000CC7F6C /* IntlNumberFormatPrototype.lut.h in Headers */,
A55165D31BDF0B9E003B75C1 /* InspectorScriptProfilerAgent.h in Headers */,
@@ -8880,6 +8894,7 @@
A7D9A29417A0BC7400EE2618 /* DFGAtTailAbstractState.cpp in Sources */,
0F666EC61835672B00D017F1 /* DFGAvailability.cpp in Sources */,
0F2B9CE219D0BA7D00B1D1B5 /* DFGAvailabilityMap.cpp in Sources */,
+ 0F725CA71C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp in Sources */,
0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */,
A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */,
A7D89CF317A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp in Sources */,
@@ -9328,6 +9343,7 @@
14D2F3DA139F4BE200491031 /* MarkedSpace.cpp in Sources */,
142D6F1113539A4100B02E86 /* MarkStack.cpp in Sources */,
70B791981C024A29002481E2 /* GeneratorPrototype.cpp in Sources */,
+ 0F725CA91C503DED00AD943A /* B3PureCSE.cpp in Sources */,
4340A4841A9051AF00D73CCA /* MathCommon.cpp in Sources */,
0F37308C1C0BD29100052BFA /* B3PhiChildren.cpp in Sources */,
14469DDF107EC7E700650446 /* MathObject.cpp in Sources */,
Added: trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.cpp (0 => 195417)
--- trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.cpp (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.cpp 2016-01-21 19:54:51 UTC (rev 195417)
@@ -0,0 +1,378 @@
+/*
+ * Copyright (C) 2016 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 "B3EliminateCommonSubexpressions.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3BlockWorklist.h"
+#include "B3Dominators.h"
+#include "B3HeapRange.h"
+#include "B3InsertionSetInlines.h"
+#include "B3MemoryValue.h"
+#include "B3PhaseScope.h"
+#include "B3ProcedureInlines.h"
+#include "B3PureCSE.h"
+#include "B3ValueKey.h"
+#include "B3ValueInlines.h"
+#include <wtf/HashMap.h>
+#include <wtf/RangeSet.h>
+
+namespace JSC { namespace B3 {
+
+namespace {
+
+const bool verbose = false;
+
+// FIXME: We could treat Patchpoints with a non-empty set of reads as a "memory value" and somehow
+// eliminate redundant ones. We would need some way of determining if two patchpoints are replacable.
+// It doesn't seem right to use the reads set for this. We could use the generator, but that feels
+// lame because the FTL will pretty much use a unique generator for each patchpoint even when two
+// patchpoints have the same semantics as far as CSE would be concerned. We could invent something
+// like a "value ID" for patchpoints. By default, each one gets a unique value ID, but FTL could force
+// some patchpoints to share the same one as a signal that they will return the same value if executed
+// in the same heap with the same inputs.
+
+typedef Vector<MemoryValue*, 1> MemoryMatches;
+
+struct ImpureBlockData {
+ RangeSet<HeapRange> writes;
+
+ // Maps an address base to all of the MemoryValues that do things to it. After we're done
+ // processing a map, this tells us the values at tail.
+ HashMap<Value*, MemoryMatches> memoryValues;
+};
+
+class CSE {
+public:
+ CSE(Procedure& proc)
+ : m_proc(proc)
+ , m_dominators(proc.dominators())
+ , m_impureBlockData(proc.size())
+ , m_insertionSet(proc)
+ {
+ }
+
+ bool run()
+ {
+ if (verbose)
+ dataLog("B3 before CSE:\n", m_proc);
+
+ m_proc.resetValueOwners();
+
+ for (BasicBlock* block : m_proc) {
+ m_data = &m_impureBlockData[block];
+ for (Value* value : *block)
+ m_data->writes.add(value->effects().writes);
+ }
+
+ for (BasicBlock* block : m_proc.blocksInPreOrder()) {
+ m_block = block;
+ m_data = &m_impureBlockData[block];
+ m_writes.clear();
+ for (m_index = 0; m_index < block->size(); ++m_index) {
+ m_value = block->at(m_index);
+ process();
+ }
+ m_insertionSet.execute(block);
+ }
+
+ return m_changed;
+ }
+
+private:
+ void process()
+ {
+ m_value->performSubstitution();
+
+ if (m_pureCSE.process(m_value, m_dominators)) {
+ ASSERT(!m_value->effects().writes);
+ m_changed = true;
+ return;
+ }
+
+ if (HeapRange writes = m_value->effects().writes)
+ clobber(writes);
+
+ if (MemoryValue* memory = m_value->as<MemoryValue>())
+ processMemory(memory);
+ }
+
+ void clobber(HeapRange writes)
+ {
+ m_writes.add(writes);
+
+ m_data->memoryValues.removeIf(
+ [&] (HashMap<Value*, MemoryMatches>::KeyValuePairType& entry) -> bool {
+ entry.value.removeAllMatching(
+ [&] (MemoryValue* memory) -> bool {
+ return memory->range().overlaps(writes);
+ });
+ return entry.value.isEmpty();
+ });
+ }
+
+ void processMemory(MemoryValue* memory)
+ {
+ Value* ptr = memory->lastChild();
+ HeapRange range = memory->range();
+ int32_t offset = memory->offset();
+ Type type = memory->type();
+
+ // FIXME: Empower this to insert more casts and shifts. For example, a Load8 could match a
+ // Store and mask the result. You could even have:
+ //
+ // Store(@value, @ptr, offset = 0)
+ // Load8Z(@ptr, offset = 2)
+ //
+ // Which could be turned into something like this:
+ //
+ // Store(@value, @ptr, offset = 0)
+ // ZShr(@value, 16)
+
+ switch (memory->opcode()) {
+ case Load8Z: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load8Z || candidate->opcode() == Store8);
+ });
+ if (replace(match))
+ break;
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load8S: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load8S || candidate->opcode() == Store8);
+ });
+ if (match) {
+ if (match->opcode() == Store8) {
+ m_value->replaceWithIdentity(
+ m_insertionSet.insert<Value>(
+ m_index, SExt8, m_value->origin(), match->child(0)));
+ m_changed = true;
+ break;
+ }
+ replace(match);
+ break;
+ }
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load16Z: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load16Z || candidate->opcode() == Store16);
+ });
+ if (replace(match))
+ break;
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load16S: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && (candidate->opcode() == Load16S || candidate->opcode() == Store16);
+ });
+ if (match) {
+ if (match->opcode() == Store16) {
+ m_value->replaceWithIdentity(
+ m_insertionSet.insert<Value>(
+ m_index, SExt16, m_value->origin(), match->child(0)));
+ m_changed = true;
+ break;
+ }
+ replace(match);
+ break;
+ }
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Load: {
+ MemoryValue* match = findMemoryValue(
+ ptr, range, [&] (MemoryValue* candidate) -> bool {
+ if (candidate->offset() != offset)
+ return false;
+
+ if (candidate->opcode() == Load && candidate->type() == type)
+ return true;
+
+ if (candidate->opcode() == Store && candidate->child(0)->type() == type)
+ return true;
+
+ return false;
+ });
+ if (replace(match))
+ break;
+ addMemoryValue(memory);
+ break;
+ }
+
+ case Store8:
+ case Store16:
+ case Store: {
+ addMemoryValue(memory);
+ break;
+ }
+
+ default:
+ dataLog("Bad memory value: ", deepDump(m_proc, m_value), "\n");
+ RELEASE_ASSERT_NOT_REACHED();
+ break;
+ }
+ }
+
+ bool replace(MemoryValue* match)
+ {
+ if (!match)
+ return false;
+
+ if (verbose)
+ dataLog("Eliminating ", *m_value, " due to ", *match, "\n");
+
+ if (match->isStore())
+ m_value->replaceWithIdentity(match->child(0));
+ else
+ m_value->replaceWithIdentity(match);
+ m_changed = true;
+ return true;
+ }
+
+ void addMemoryValue(MemoryValue* memory)
+ {
+ addMemoryValue(*m_data, memory);
+ }
+
+ void addMemoryValue(ImpureBlockData& data, MemoryValue* memory)
+ {
+ MemoryMatches& matches =
+ data.memoryValues.add(memory->lastChild(), MemoryMatches()).iterator->value;
+
+ if (matches.contains(memory))
+ return;
+
+ matches.append(memory);
+ }
+
+ template<typename Filter>
+ MemoryValue* findMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
+ {
+ auto find = [&] (ImpureBlockData& data) -> MemoryValue* {
+ auto iter = data.memoryValues.find(ptr);
+ if (iter != data.memoryValues.end()) {
+ for (MemoryValue* candidate : iter->value) {
+ if (filter(candidate))
+ return candidate;
+ }
+ }
+ return nullptr;
+ };
+
+ if (MemoryValue* match = find(*m_data))
+ return match;
+
+ if (m_writes.overlaps(range))
+ return nullptr;
+
+ BlockWorklist worklist;
+ Vector<BasicBlock*, 8> seenList;
+
+ worklist.pushAll(m_block->predecessors());
+
+ MemoryValue* match = nullptr;
+
+ while (BasicBlock* block = worklist.pop()) {
+ seenList.append(block);
+
+ ImpureBlockData& data = ""
+
+ if (m_dominators.strictlyDominates(block, m_block)) {
+ match = find(data);
+ if (match)
+ continue;
+ }
+
+ if (data.writes.overlaps(range))
+ return nullptr;
+
+ worklist.pushAll(block->predecessors());
+ }
+
+ if (!match)
+ return nullptr;
+
+ for (BasicBlock* block : seenList)
+ addMemoryValue(m_impureBlockData[block], match);
+ addMemoryValue(match);
+
+ return match;
+ }
+
+ typedef Vector<Value*, 1> Matches;
+
+ Procedure& m_proc;
+
+ Dominators& m_dominators;
+ PureCSE m_pureCSE;
+
+ IndexMap<BasicBlock, ImpureBlockData> m_impureBlockData;
+
+ ImpureBlockData* m_data;
+ RangeSet<HeapRange> m_writes;
+
+ BasicBlock* m_block;
+ unsigned m_index;
+ Value* m_value;
+
+ InsertionSet m_insertionSet;
+
+ bool m_changed { false };
+};
+
+} // anonymous namespace
+
+bool eliminateCommonSubexpressions(Procedure& proc)
+{
+ PhaseScope phaseScope(proc, "eliminateCommonSubexpressions");
+
+ CSE cse(proc);
+ return cse.run();
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
Added: trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.h (0 => 195417)
--- trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3EliminateCommonSubexpressions.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2016 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 B3EliminateCommonSubexpressions_h
+#define B3EliminateCommonSubexpressions_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+// This does global common subexpression elimination (CSE) over both pure values and memory accesses.
+
+bool eliminateCommonSubexpressions(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3EliminateCommonSubexpressions_h
+
Modified: trunk/Source/_javascript_Core/b3/B3Generate.cpp (195416 => 195417)
--- trunk/Source/_javascript_Core/b3/B3Generate.cpp 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/b3/B3Generate.cpp 2016-01-21 19:54:51 UTC (rev 195417)
@@ -33,6 +33,7 @@
#include "AirInstInlines.h"
#include "B3Common.h"
#include "B3DuplicateTails.h"
+#include "B3EliminateCommonSubexpressions.h"
#include "B3FoldPathConstants.h"
#include "B3LegalizeMemoryOffsets.h"
#include "B3LowerMacros.h"
@@ -78,6 +79,7 @@
if (optLevel >= 1) {
reduceDoubleToFloat(procedure);
reduceStrength(procedure);
+ eliminateCommonSubexpressions(procedure);
duplicateTails(procedure);
foldPathConstants(procedure);
Modified: trunk/Source/_javascript_Core/b3/B3HeapRange.h (195416 => 195417)
--- trunk/Source/_javascript_Core/b3/B3HeapRange.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/b3/B3HeapRange.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -40,6 +40,8 @@
class HeapRange {
public:
+ typedef unsigned Type;
+
HeapRange()
: m_begin(0)
, m_end(0)
Modified: trunk/Source/_javascript_Core/b3/B3InsertionSet.h (195416 => 195417)
--- trunk/Source/_javascript_Core/b3/B3InsertionSet.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/b3/B3InsertionSet.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -48,6 +48,8 @@
{
}
+ bool isEmpty() const { return m_insertions.isEmpty(); }
+
Procedure& code() { return m_procedure; }
void appendInsertion(const Insertion& insertion)
Modified: trunk/Source/_javascript_Core/b3/B3MemoryValue.h (195416 => 195417)
--- trunk/Source/_javascript_Core/b3/B3MemoryValue.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/b3/B3MemoryValue.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -60,6 +60,9 @@
const HeapRange& range() const { return m_range; }
void setRange(const HeapRange& range) { m_range = range; }
+ bool isStore() const { return type() == Void; }
+ bool isLoad() const { return type() != Void; }
+
size_t accessByteSize() const;
protected:
Added: trunk/Source/_javascript_Core/b3/B3PureCSE.cpp (0 => 195417)
--- trunk/Source/_javascript_Core/b3/B3PureCSE.cpp (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3PureCSE.cpp 2016-01-21 19:54:51 UTC (rev 195417)
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2016 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 "B3PureCSE.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3Dominators.h"
+#include "B3Value.h"
+
+namespace JSC { namespace B3 {
+
+PureCSE::PureCSE()
+{
+}
+
+PureCSE::~PureCSE()
+{
+}
+
+void PureCSE::clear()
+{
+ m_map.clear();
+}
+
+bool PureCSE::process(Value* value, Dominators& dominators)
+{
+ if (value->opcode() == Identity)
+ return false;
+
+ ValueKey key = value->key();
+ if (!key)
+ return false;
+
+ Matches& matches = m_map.add(key, Matches()).iterator->value;
+
+ for (Value* match : matches) {
+ if (dominators.dominates(match->owner, value->owner)) {
+ value->replaceWithIdentity(match);
+ return true;
+ }
+ }
+
+ matches.append(value);
+ return false;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
Added: trunk/Source/_javascript_Core/b3/B3PureCSE.h (0 => 195417)
--- trunk/Source/_javascript_Core/b3/B3PureCSE.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3PureCSE.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -0,0 +1,62 @@
+/*
+ * Copyright (C) 2016 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 B3PureCSE_h
+#define B3PureCSE_h
+
+#if ENABLE(B3_JIT)
+
+#include "B3ValueKey.h"
+#include <wtf/HashMap.h>
+#include <wtf/Vector.h>
+
+namespace JSC { namespace B3 {
+
+class Dominators;
+class Value;
+
+typedef Vector<Value*, 1> Matches;
+
+// This is a reusable utility for doing pure CSE. You can use it to do pure CSE on a program by just
+// proceeding in order an calling process().
+class PureCSE {
+public:
+ PureCSE();
+ ~PureCSE();
+
+ void clear();
+
+ bool process(Value*, Dominators&);
+
+private:
+ HashMap<ValueKey, Matches> m_map;
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3PureCSE_h
+
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp (195416 => 195417)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2016-01-21 19:54:51 UTC (rev 195417)
@@ -38,6 +38,7 @@
#include "B3PhaseScope.h"
#include "B3PhiChildren.h"
#include "B3ProcedureInlines.h"
+#include "B3PureCSE.h"
#include "B3UpsilonValue.h"
#include "B3UseCounts.h"
#include "B3ValueKey.h"
@@ -282,7 +283,7 @@
m_proc.resetValueOwners();
m_dominators = &m_proc.dominators(); // Recompute if necessary.
- m_pureValues.clear();
+ m_pureCSE.clear();
for (BasicBlock* block : m_proc.blocksInPreOrder()) {
m_block = block;
@@ -1751,31 +1752,7 @@
void replaceIfRedundant()
{
- // This does a very simple pure dominator-based CSE. In the future we could add load elimination.
- // Note that if we add load elimination, we should do it by directly matching load and store
- // instructions instead of using the ValueKey functionality or doing DFG HeapLocation-like
- // things.
-
- // Don't bother with identities. We kill those anyway.
- if (m_value->opcode() == Identity)
- return;
-
- ValueKey key = m_value->key();
- if (!key)
- return;
-
- Vector<Value*, 1>& matches = m_pureValues.add(key, Vector<Value*, 1>()).iterator->value;
-
- // Replace this value with whichever value dominates us.
- for (Value* match : matches) {
- if (m_dominators->dominates(match->owner, m_value->owner)) {
- m_value->replaceWithIdentity(match);
- m_changed = true;
- return;
- }
- }
-
- matches.append(m_value);
+ m_changed |= m_pureCSE.process(m_value, *m_dominators);
}
void simplifyCFG()
@@ -2042,7 +2019,7 @@
unsigned m_index { 0 };
Value* m_value { nullptr };
Dominators* m_dominators { nullptr };
- HashMap<ValueKey, Vector<Value*, 1>> m_pureValues;
+ PureCSE m_pureCSE;
bool m_changed { false };
bool m_changedCFG { false };
};
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.h (195416 => 195417)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -32,11 +32,13 @@
class Procedure;
-// Does strength reduction, constant folding, canonicalization, CFG simplification, DCE, and CSE. This
-// phase runs those optimizations to fixpoint. The goal of the phase is to dramatically reduce the
-// complexity of the code. In the future, it's preferable to add optimizations to this phase rather than
-// creating new optimizations because then the optimizations can participate in the fixpoint. However,
-// this phase shouldn't become too expensive, so expensive optimizations should be separate.
+// Does strength reduction, constant folding, canonicalization, CFG simplification, DCE, and very
+// simple CSE. This phase runs those optimizations to fixpoint. The goal of the phase is to
+// dramatically reduce the complexity of the code. In the future, it's preferable to add optimizations
+// to this phase rather than creating new optimizations because then the optimizations can participate
+// in the fixpoint. However, because of the many interlocking optimizations, it can be difficult to
+// add sophisticated optimizations to it. For that reason we have full CSE in a different phase, for
+// example.
bool reduceStrength(Procedure&);
Modified: trunk/Source/_javascript_Core/b3/B3Validate.cpp (195416 => 195417)
--- trunk/Source/_javascript_Core/b3/B3Validate.cpp 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/_javascript_Core/b3/B3Validate.cpp 2016-01-21 19:54:51 UTC (rev 195417)
@@ -371,6 +371,8 @@
VALIDATE(value->type() == Void, ("At ", *value));
break;
}
+
+ VALIDATE(!(value->effects().writes && value->key()), ("At ", *value));
}
}
Modified: trunk/Source/WTF/ChangeLog (195416 => 195417)
--- trunk/Source/WTF/ChangeLog 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/ChangeLog 2016-01-21 19:54:51 UTC (rev 195417)
@@ -1,3 +1,41 @@
+2016-01-21 Filip Pizlo <[email protected]>
+
+ B3 should have load elimination
+ https://bugs.webkit.org/show_bug.cgi?id=153288
+
+ Reviewed by Geoffrey Garen.
+
+ I needed a way to track sets of ranges, where there is a high likelihood that all of the
+ ranges overlap. So I created RangeSet. It's a usually-sorted list of coalesced ranges.
+ Practically this means that right now, FTL B3 will end up with two kinds of range sets: a set
+ that just contains top and a set that contains nothing. In the future, most sets will either
+ be top of empty but some of them will contain a handful of other things.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/MathExtras.h:
+ (WTF::leftShiftWithSaturation):
+ (WTF::nonEmptyRangesOverlap):
+ (WTF::rangesOverlap):
+ * wtf/RangeSet.h: Added.
+ (WTF::RangeSet::RangeSet):
+ (WTF::RangeSet::~RangeSet):
+ (WTF::RangeSet::add):
+ (WTF::RangeSet::contains):
+ (WTF::RangeSet::overlaps):
+ (WTF::RangeSet::clear):
+ (WTF::RangeSet::dump):
+ (WTF::RangeSet::dumpRaw):
+ (WTF::RangeSet::compact):
+ (WTF::RangeSet::overlapsNonEmpty):
+ (WTF::RangeSet::subsumesNonEmpty):
+ (WTF::RangeSet::findRange):
+ * wtf/StdLibExtras.h:
+ (WTF::binarySearchImpl):
+ (WTF::binarySearch):
+ (WTF::tryBinarySearch):
+ (WTF::approximateBinarySearch):
+
2016-01-19 Ada Chan <[email protected]>
Make it possible to enable VIDEO_PRESENTATION_MODE on other Cocoa platforms.
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (195416 => 195417)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-01-21 19:54:51 UTC (rev 195417)
@@ -27,6 +27,7 @@
0F3501641BB258D500F0A2A3 /* WeakRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3501631BB258C800F0A2A3 /* WeakRandom.h */; };
0F4570431BE5B58F0062A629 /* Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570421BE5B58F0062A629 /* Dominators.h */; };
0F4570451BE834410062A629 /* BubbleSort.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570441BE834410062A629 /* BubbleSort.h */; };
+ 0F725CAC1C50461600AD943A /* RangeSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CAB1C50461600AD943A /* RangeSet.h */; };
0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
@@ -332,6 +333,7 @@
0F3501631BB258C800F0A2A3 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = "<group>"; };
0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
0F4570441BE834410062A629 /* BubbleSort.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BubbleSort.h; sourceTree = "<group>"; };
+ 0F725CAB1C50461600AD943A /* RangeSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RangeSet.h; sourceTree = "<group>"; };
0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
@@ -876,6 +878,7 @@
A8A472FB151A825B004123FF /* RandomNumber.cpp */,
A8A472FC151A825B004123FF /* RandomNumber.h */,
A8A472FD151A825B004123FF /* RandomNumberSeed.h */,
+ 0F725CAB1C50461600AD943A /* RangeSet.h */,
0F87105916643F190090B0AD /* RawPointer.h */,
A8A472FE151A825B004123FF /* RedBlackTree.h */,
26299B6D17A9E5B800ADEBE5 /* Ref.h */,
@@ -1168,6 +1171,7 @@
A8A473B4151A825B004123FF /* fast-dtoa.h in Headers */,
0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */,
A8A473C4151A825B004123FF /* FastMalloc.h in Headers */,
+ 0F725CAC1C50461600AD943A /* RangeSet.h in Headers */,
B38FD7BD168953E80065C969 /* FeatureDefines.h in Headers */,
0F9D3361165DBA73005AD387 /* FilePrintStream.h in Headers */,
A8A473B6151A825B004123FF /* fixed-dtoa.h in Headers */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (195416 => 195417)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-01-21 19:54:51 UTC (rev 195417)
@@ -77,6 +77,7 @@
RAMSize.h
RandomNumber.h
RandomNumberSeed.h
+ RangeSet.h
RawPointer.h
RedBlackTree.h
Ref.h
Modified: trunk/Source/WTF/wtf/MathExtras.h (195416 => 195417)
--- trunk/Source/WTF/wtf/MathExtras.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/wtf/MathExtras.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013, 2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -419,6 +419,20 @@
return result;
}
+// Check if two ranges overlap assuming that neither range is empty.
+template<typename T>
+inline bool nonEmptyRangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
+{
+ ASSERT(leftMin < leftMax);
+ ASSERT(rightMin < rightMax);
+
+ if (leftMin <= rightMin && leftMax > rightMin)
+ return true;
+ if (rightMin <= leftMin && rightMax > leftMin)
+ return true;
+ return false;
+}
+
// Pass ranges with the min being inclusive and the max being exclusive. For example, this should
// return false:
//
@@ -434,12 +448,8 @@
return false;
if (rightMin == rightMax)
return false;
-
- if (leftMin <= rightMin && leftMax > rightMin)
- return true;
- if (rightMin <= leftMin && rightMax > leftMin)
- return true;
- return false;
+
+ return nonEmptyRangesOverlap(leftMin, leftMax, rightMin, rightMax);
}
} // namespace WTF
Added: trunk/Source/WTF/wtf/RangeSet.h (0 => 195417)
--- trunk/Source/WTF/wtf/RangeSet.h (rev 0)
+++ trunk/Source/WTF/wtf/RangeSet.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -0,0 +1,213 @@
+/*
+ * Copyright (C) 2016 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 WTF_RangeSet_h
+#define WTF_RangeSet_h
+
+#include <wtf/ListDump.h>
+#include <wtf/MathExtras.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/Vector.h>
+
+namespace WTF {
+
+// A RangeSet is a set of numerical ranges. A value belongs to the set if it is within any of the
+// ranges. A range belongs to the set if every value in the range belongs to the set. A range overlaps
+// the set if any value in the range belongs to the set. You can add ranges and query range
+// membership. The internal representation is a list of ranges that gets periodically compacted. This
+// representation is optimal so long as the number of distinct ranges tends to be small, and the
+// number of range sets tends to be small as well. This works reasonably well in a bunch of compiler
+// algorithms, where the top range ends up being used a lot.
+//
+// The initial user of this is JSC::B3::HeapRange, which is used to perform alias analysis. You can
+// model new users on that class. Basically, you need to define:
+//
+// T::Type - the type of the members of the range. HeapRange uses unsigned.
+// T(T::Type begin, T::Type end) - construct a new range.
+// T::Type T::begin() const - instance method giving the inclusive beginning of the range.
+// T::Type T::end() const - instance method giving the exclusive end of the range.
+// void T::dump(PrintStream&) const - some kind of dumping.
+
+template<typename RangeType>
+class RangeSet {
+public:
+ typedef RangeType Range;
+ typedef typename Range::Type Type;
+
+ RangeSet()
+ {
+ }
+
+ ~RangeSet()
+ {
+ }
+
+ void add(const Range& range)
+ {
+ if (range.begin() == range.end())
+ return;
+
+ // We expect the range set to become top in a lot of cases. We also expect the same range to
+ // be added repeatedly. That's why this is here.
+ if (!m_ranges.isEmpty() && subsumesNonEmpty(m_ranges.last(), range))
+ return;
+
+ m_isCompact = false;
+
+ // We append without compacting only if doing so is guaranteed not to resize the vector.
+ if (m_ranges.size() + 1 < m_ranges.capacity()) {
+ m_ranges.append(range);
+ return;
+ }
+
+ m_ranges.append(range);
+ compact();
+ }
+
+ bool contains(const Range& range) const
+ {
+ if (range.begin() == range.end())
+ return false;
+
+ unsigned index = findRange(range);
+ if (index + 1 < m_ranges.size()
+ && subsumesNonEmpty(m_ranges[index + 1], range))
+ return true;
+ if (index < m_ranges.size()
+ && subsumesNonEmpty(m_ranges[index], range))
+ return true;
+ if (static_cast<unsigned>(index - 1) < m_ranges.size()
+ && subsumesNonEmpty(m_ranges[index - 1], range))
+ return true;
+ return false;
+ }
+
+ bool overlaps(const Range& range) const
+ {
+ if (range.begin() == range.end())
+ return false;
+
+ unsigned index = findRange(range);
+ if (index + 1 < m_ranges.size()
+ && overlapsNonEmpty(m_ranges[index + 1], range))
+ return true;
+ if (index < m_ranges.size()
+ && overlapsNonEmpty(m_ranges[index], range))
+ return true;
+ if (static_cast<unsigned>(index - 1) < m_ranges.size()
+ && overlapsNonEmpty(m_ranges[index - 1], range))
+ return true;
+ return false;
+ }
+
+ void clear()
+ {
+ m_ranges.clear();
+ m_isCompact = true;
+ }
+
+ void dump(PrintStream& out) const
+ {
+ const_cast<RangeSet*>(this)->compact();
+ out.print(listDump(m_ranges));
+ }
+
+ void dumpRaw(PrintStream& out) const
+ {
+ out.print("{", listDump(m_ranges), ", isCompact = ", m_isCompact, "}");
+ }
+
+private:
+ void compact()
+ {
+ if (m_isCompact)
+ return;
+
+ if (m_ranges.isEmpty()) {
+ m_isCompact = true;
+ return;
+ }
+
+ std::sort(
+ m_ranges.begin(), m_ranges.end(),
+ [&] (const Range& a, const Range& b) -> bool {
+ return a.begin() < b.begin();
+ });
+
+ unsigned srcIndex = 1;
+ unsigned dstIndex = 1;
+ Range* lastRange = &m_ranges[0];
+ while (srcIndex < m_ranges.size()) {
+ Range range = m_ranges[srcIndex++];
+ ASSERT(range.begin() >= lastRange->begin());
+ if (range.end() <= lastRange->end())
+ continue;
+ if (range.begin() <= lastRange->end()) {
+ *lastRange = Range(lastRange->begin(), range.end());
+ continue;
+ }
+ ASSERT(!overlapsNonEmpty(*lastRange, range));
+ lastRange = &m_ranges[dstIndex++];
+ *lastRange = range;
+ }
+ m_ranges.resize(dstIndex);
+
+ m_isCompact = true;
+ }
+
+ static bool overlapsNonEmpty(const Range& a, const Range& b)
+ {
+ return nonEmptyRangesOverlap(a.begin(), a.end(), b.begin(), b.end());
+ }
+
+ static bool subsumesNonEmpty(const Range& a, const Range& b)
+ {
+ return a.begin() <= b.begin() && a.end() >= b.end();
+ }
+
+ unsigned findRange(const Range& range) const
+ {
+ const_cast<RangeSet*>(this)->compact();
+
+ const Range* found = approximateBinarySearch<const Range, Type>(
+ m_ranges, m_ranges.size(), range.begin(), [&] (const Range* range) -> Type {
+ return range->begin();
+ });
+ if (!found)
+ return UINT_MAX;
+
+ return found - m_ranges.begin();
+ }
+
+ Vector<Range, 8> m_ranges;
+ bool m_isCompact { true };
+};
+
+} // namespace WTF
+
+using WTF::RangeSet;
+
+#endif // WTF_RangeSet_h
+
Modified: trunk/Source/WTF/wtf/StdLibExtras.h (195416 => 195417)
--- trunk/Source/WTF/wtf/StdLibExtras.h 2016-01-21 19:16:30 UTC (rev 195416)
+++ trunk/Source/WTF/wtf/StdLibExtras.h 2016-01-21 19:54:51 UTC (rev 195417)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2008 Apple Inc. All Rights Reserved.
+ * Copyright (C) 2008, 2016 Apple Inc. All Rights Reserved.
* Copyright (C) 2013 Patrick Gansterer <[email protected]>
*
* Redistribution and use in source and binary forms, with or without
@@ -212,7 +212,7 @@
ASSERT(mode != KeyMustBePresentInArray || size);
}
- if (mode == KeyMightNotBePresentInArray && !size)
+ if (mode != KeyMustBePresentInArray && !size)
return 0;
ArrayElementType* result = &array[offset];
@@ -230,38 +230,38 @@
// If the element is not found, crash if asserts are enabled, and behave like approximateBinarySearch in release builds.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
+inline ArrayElementType* binarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(array, size, key, extractKey);
}
// Return zero if the element is not found.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
+inline ArrayElementType* tryBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(array, size, key, extractKey);
}
// Return the element that is either to the left, or the right, of where the element would have been found.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
+inline ArrayElementType* approximateBinarySearch(ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(array, size, key, extractKey);
}
// Variants of the above that use const.
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
+inline ArrayElementType* binarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMustBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
}
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
+inline ArrayElementType* tryBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, KeyMightNotBePresentInArray>(const_cast<ArrayType&>(array), size, key, extractKey);
}
template<typename ArrayElementType, typename KeyType, typename ArrayType, typename ExtractKey>
-inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, ExtractKey extractKey = ExtractKey())
+inline ArrayElementType* approximateBinarySearch(const ArrayType& array, size_t size, KeyType key, const ExtractKey& extractKey = ExtractKey())
{
return binarySearchImpl<ArrayElementType, KeyType, ArrayType, ExtractKey, ReturnAdjacentElementIfKeyIsNotPresent>(const_cast<ArrayType&>(array), size, key, extractKey);
}
