Air should support linear scan for optLevel<2
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 30 Mar 2017 22:55:44 +0000 (22:55 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 30 Mar 2017 22:55:44 +0000 (22:55 +0000)
https://bugs.webkit.org/show_bug.cgi?id=170161

Reviewed by Saam Barati.

Source/JavaScriptCore:

This changes the default opt level of B3 to 2. It makes the other opt levels useful by adding a
new register allocator. This new linear scan allocator will produce significantly worse code.
But it will produce that code a lot faster than IRC or Briggs.

The opt levels are:
    0: no optimizations, linear scan
    1: some optimizations, linear scan
    2: full optimizations, graph coloring (IRC or Briggs based on CPU)

What we used to call optLevel=1 is not called optLevel=2, or better yet,
optLevel=B3::defaultOptLevel(). We no longer have anything like the old optLevel=0 (which did no
optimizations but ran graph coloring).

allocateRegistersByLinearScan() faithfully implements Massimiliano Poletto and Vivek Sarkar's
famous algorithm. It uses the variant that handles clobbered registers by avoiding assigning
ranges to those registers if the range overlaps a clobber. It's engineered to allocate registers
very quickly and generate inefficient code without falling off a cliff.

The new optLevel=1 speeds up B3 by a factor of 2, and results in a 80% throughput regression.
Linear scan runs 4.7x faster than graph coloring on average.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3BasicBlockUtils.h:
(JSC::B3::blocksInPreOrder):
(JSC::B3::blocksInPostOrder):
* b3/B3BlockWorklist.h:
* b3/B3CFG.h:
(JSC::B3::CFG::newMap):
* b3/B3Common.h:
(JSC::B3::defaultOptLevel):
* b3/B3Compile.h:
* b3/B3DuplicateTails.cpp:
* b3/B3EliminateCommonSubexpressions.cpp:
* b3/B3FixSSA.cpp:
(JSC::B3::demoteValues):
(JSC::B3::fixSSA):
* b3/B3FixSSA.h:
* b3/B3Generate.cpp:
(JSC::B3::prepareForGeneration):
(JSC::B3::generateToAir):
* b3/B3Generate.h:
* b3/B3HeapRange.cpp: Removed.
* b3/B3HeapRange.h:
(JSC::B3::HeapRange::HeapRange): Deleted.
(JSC::B3::HeapRange::top): Deleted.
(JSC::B3::HeapRange::operator==): Deleted.
(JSC::B3::HeapRange::operator!=): Deleted.
(JSC::B3::HeapRange::operator|): Deleted.
(JSC::B3::HeapRange::operator bool): Deleted.
(JSC::B3::HeapRange::begin): Deleted.
(JSC::B3::HeapRange::end): Deleted.
(JSC::B3::HeapRange::overlaps): Deleted.
* b3/B3LowerToAir.cpp:
* b3/B3MoveConstants.cpp:
* b3/B3PhiChildren.h:
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::dump):
(JSC::B3::Procedure::deleteOrphans):
(JSC::B3::Procedure::setBlockOrderImpl):
* b3/B3ReduceDoubleToFloat.cpp:
* b3/B3ReduceStrength.cpp:
* b3/B3SSACalculator.h:
* b3/B3UseCounts.h:
* b3/air/AirAllocateRegistersByGraphColoring.cpp:
* b3/air/AirAllocateRegistersByLinearScan.cpp: Added.
(JSC::B3::Air::allocateRegistersByLinearScan):
* b3/air/AirAllocateRegistersByLinearScan.h: Added.
* b3/air/AirAllocateStack.cpp:
(JSC::B3::Air::allocateStack):
* b3/air/AirArg.cpp:
(WTF::printInternal):
* b3/air/AirArg.h:
(JSC::B3::Air::Arg::activeAt):
(JSC::B3::Air::Arg::timing):
(JSC::B3::Air::Arg::forEachPhase):
* b3/air/AirBasicBlock.h:
* b3/air/AirBlockWorklist.h:
* b3/air/AirCFG.h:
(JSC::B3::Air::CFG::newMap):
* b3/air/AirEliminateDeadCode.cpp:
(JSC::B3::Air::eliminateDeadCode):
* b3/air/AirFixObviousSpills.cpp:
* b3/air/AirFixPartialRegisterStalls.cpp:
(JSC::B3::Air::fixPartialRegisterStalls):
* b3/air/AirFixSpillsAfterTerminals.cpp: Added.
(JSC::B3::Air::fixSpillsAfterTerminals):
* b3/air/AirFixSpillsAfterTerminals.h: Added.
* b3/air/AirGenerate.cpp:
(JSC::B3::Air::prepareForGeneration):
(JSC::B3::Air::generate):
* b3/air/AirGenerate.h:
* b3/air/AirGenerationContext.h:
* b3/air/AirInsertionSet.h:
* b3/air/AirInst.cpp:
(JSC::B3::Air::Inst::needsPadding):
* b3/air/AirLowerAfterRegAlloc.cpp:
(JSC::B3::Air::lowerAfterRegAlloc):
* b3/air/AirLowerEntrySwitch.cpp:
(JSC::B3::Air::lowerEntrySwitch):
* b3/air/AirOpcode.opcodes:
* b3/air/AirPhaseInsertionSet.cpp: Added.
(JSC::B3::Air::PhaseInsertionSet::execute):
* b3/air/AirPhaseInsertionSet.h: Added.
(JSC::B3::Air::PhaseInsertion::PhaseInsertion):
(JSC::B3::Air::PhaseInsertion::phase):
(JSC::B3::Air::PhaseInsertion::operator<):
(JSC::B3::Air::PhaseInsertionSet::PhaseInsertionSet):
(JSC::B3::Air::PhaseInsertionSet::appendInsertion):
(JSC::B3::Air::PhaseInsertionSet::insertInst):
(JSC::B3::Air::PhaseInsertionSet::insert):
* b3/air/AirRegLiveness.h:
(JSC::B3::Air::RegLiveness::LocalCalc::LocalCalc):
* b3/air/AirSpillEverything.cpp:
(JSC::B3::Air::spillEverything):
* b3/air/AirTmp.cpp:
* b3/air/AirTmp.h:
(JSC::B3::Air::Tmp::tmpForIndex):
* b3/air/AirTmpInlines.h:
(JSC::B3::Air::Tmp::Indexed::Indexed):
(JSC::B3::Air::Tmp::Indexed::index):
(JSC::B3::Air::Tmp::AbsolutelyIndexed::AbsolutelyIndexed):
(JSC::B3::Air::Tmp::AbsolutelyIndexed::index):
(JSC::B3::Air::Tmp::indexed):
(JSC::B3::Air::Tmp::absolutelyIndexed):
(JSC::B3::Air::Tmp::tmpForAbsoluteIndex):
* b3/testb3.cpp:
(JSC::B3::compile):
(JSC::B3::testMulLoadTwice):
* jit/RegisterSet.h:
(JSC::RegisterSet::add):
(JSC::RegisterSet::remove):
* runtime/Options.h:
* wasm/WasmB3IRGenerator.h:

Source/WTF:

This change introduces a new low-latency register allocator. It can allocate registers very
quickly by doing a relatively poor job. Implementing this algorithm required beefing up some of
our core algorithms.

* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/Deque.h: Make it possible to do some basic priority queueing with this data structure.
(WTF::inlineCapacity>::removeAllMatching):
(WTF::inlineCapacity>::appendAndBubble):
(WTF::inlineCapacity>::takeLast):
* wtf/IndexKeyType.h: Added. This makes it possible to use IndexMap and IndexSet with value or pointer types. Previously they just worked with pointer types.
(WTF::IndexKeyType::index):
* wtf/IndexMap.h: Adopt IndexKeyType.
(WTF::IndexMap::operator[]):
(WTF::IndexMap::append):
* wtf/IndexSet.h: Adopt IndexKeyType.
(WTF::IndexSet::add):
(WTF::IndexSet::addAll):
(WTF::IndexSet::remove):
(WTF::IndexSet::contains):
(WTF::IndexSet::Iterable::iterator::operator*):
* wtf/Range.h: Added. This used to be B3::HeapRange. This generalizes that data structure to any kind of range stuff.
(WTF::Range::Range):
(WTF::Range::top):
(WTF::Range::operator==):
(WTF::Range::operator!=):
(WTF::Range::operator bool):
(WTF::Range::operator|):
(WTF::Range::operator|=):
(WTF::Range::begin):
(WTF::Range::end):
(WTF::Range::overlaps):
(WTF::Range::dump):
* wtf/RangeSet.h:
(WTF::RangeSet::add):

Tools:

This makes us run a bunch of JS tests at optLevel=1 to force testing of this new compiler
pipeline.

* Scripts/run-jsc-stress-tests:

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

67 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3BasicBlockUtils.h
Source/JavaScriptCore/b3/B3BlockWorklist.h
Source/JavaScriptCore/b3/B3CFG.h
Source/JavaScriptCore/b3/B3Common.h
Source/JavaScriptCore/b3/B3Compile.h
Source/JavaScriptCore/b3/B3DuplicateTails.cpp
Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp
Source/JavaScriptCore/b3/B3FixSSA.cpp
Source/JavaScriptCore/b3/B3FixSSA.h
Source/JavaScriptCore/b3/B3Generate.cpp
Source/JavaScriptCore/b3/B3Generate.h
Source/JavaScriptCore/b3/B3HeapRange.h
Source/JavaScriptCore/b3/B3LowerToAir.cpp
Source/JavaScriptCore/b3/B3MoveConstants.cpp
Source/JavaScriptCore/b3/B3PhiChildren.h
Source/JavaScriptCore/b3/B3Procedure.cpp
Source/JavaScriptCore/b3/B3ReduceDoubleToFloat.cpp
Source/JavaScriptCore/b3/B3ReduceStrength.cpp
Source/JavaScriptCore/b3/B3SSACalculator.h
Source/JavaScriptCore/b3/B3UseCounts.h
Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp
Source/JavaScriptCore/b3/air/AirAllocateRegistersByLinearScan.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirAllocateRegistersByLinearScan.h [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirAllocateStack.cpp
Source/JavaScriptCore/b3/air/AirArg.cpp
Source/JavaScriptCore/b3/air/AirArg.h
Source/JavaScriptCore/b3/air/AirBasicBlock.h
Source/JavaScriptCore/b3/air/AirBlockWorklist.h
Source/JavaScriptCore/b3/air/AirCFG.h
Source/JavaScriptCore/b3/air/AirEliminateDeadCode.cpp
Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp
Source/JavaScriptCore/b3/air/AirFixPartialRegisterStalls.cpp
Source/JavaScriptCore/b3/air/AirFixSpillsAfterTerminals.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirFixSpillsAfterTerminals.h [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirGenerate.cpp
Source/JavaScriptCore/b3/air/AirGenerate.h
Source/JavaScriptCore/b3/air/AirGenerationContext.h
Source/JavaScriptCore/b3/air/AirInsertionSet.h
Source/JavaScriptCore/b3/air/AirInst.cpp
Source/JavaScriptCore/b3/air/AirLowerAfterRegAlloc.cpp
Source/JavaScriptCore/b3/air/AirLowerEntrySwitch.cpp
Source/JavaScriptCore/b3/air/AirOpcode.opcodes
Source/JavaScriptCore/b3/air/AirPhaseInsertionSet.cpp [moved from Source/JavaScriptCore/b3/B3HeapRange.cpp with 77% similarity]
Source/JavaScriptCore/b3/air/AirPhaseInsertionSet.h [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirRegLiveness.h
Source/JavaScriptCore/b3/air/AirSpillEverything.cpp
Source/JavaScriptCore/b3/air/AirTmp.cpp
Source/JavaScriptCore/b3/air/AirTmp.h
Source/JavaScriptCore/b3/air/AirTmpInlines.h
Source/JavaScriptCore/b3/testb3.cpp
Source/JavaScriptCore/jit/RegisterSet.h
Source/JavaScriptCore/runtime/Options.h
Source/JavaScriptCore/wasm/WasmB3IRGenerator.h
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Deque.h
Source/WTF/wtf/IndexKeyType.h [new file with mode: 0644]
Source/WTF/wtf/IndexMap.h
Source/WTF/wtf/IndexSet.h
Source/WTF/wtf/Range.h [new file with mode: 0644]
Source/WTF/wtf/RangeSet.h
Tools/ChangeLog
Tools/Scripts/run-jsc-stress-tests

index 5cd5b4e..7ec2ada 100644 (file)
@@ -74,6 +74,7 @@ set(JavaScriptCore_SOURCES
     assembler/MacroAssemblerX86Common.cpp
 
     b3/air/AirAllocateRegistersByGraphColoring.cpp
+    b3/air/AirAllocateRegistersByLinearScan.cpp
     b3/air/AirAllocateStack.cpp
     b3/air/AirArg.cpp
     b3/air/AirBasicBlock.cpp
@@ -88,6 +89,7 @@ set(JavaScriptCore_SOURCES
     b3/air/AirEmitShuffle.cpp
     b3/air/AirFixObviousSpills.cpp
     b3/air/AirFixPartialRegisterStalls.cpp
+    b3/air/AirFixSpillsAfterTerminals.cpp
     b3/air/AirGenerate.cpp
     b3/air/AirGenerated.cpp
     b3/air/AirHandleCalleeSaves.cpp
@@ -100,6 +102,7 @@ set(JavaScriptCore_SOURCES
     b3/air/AirLowerMacros.cpp
     b3/air/AirOptimizeBlockOrder.cpp
     b3/air/AirPadInterference.cpp
+    b3/air/AirPhaseInsertionSet.cpp
     b3/air/AirPhaseScope.cpp
     b3/air/AirRegLiveness.cpp
     b3/air/AirReportUsedRegisters.cpp
@@ -140,7 +143,6 @@ set(JavaScriptCore_SOURCES
     b3/B3FoldPathConstants.cpp
     b3/B3FrequencyClass.cpp
     b3/B3Generate.cpp
-    b3/B3HeapRange.cpp
     b3/B3InferSwitches.cpp
     b3/B3InsertionSet.cpp
     b3/B3Kind.cpp
index b69813c..a8f6cb4 100644 (file)
@@ -1,3 +1,145 @@
+2017-03-30  Filip Pizlo  <fpizlo@apple.com>
+
+        Air should support linear scan for optLevel<2
+        https://bugs.webkit.org/show_bug.cgi?id=170161
+
+        Reviewed by Saam Barati.
+        
+        This changes the default opt level of B3 to 2. It makes the other opt levels useful by adding a
+        new register allocator. This new linear scan allocator will produce significantly worse code.
+        But it will produce that code a lot faster than IRC or Briggs.
+        
+        The opt levels are:
+            0: no optimizations, linear scan
+            1: some optimizations, linear scan
+            2: full optimizations, graph coloring (IRC or Briggs based on CPU)
+        
+        What we used to call optLevel=1 is not called optLevel=2, or better yet,
+        optLevel=B3::defaultOptLevel(). We no longer have anything like the old optLevel=0 (which did no
+        optimizations but ran graph coloring).
+        
+        allocateRegistersByLinearScan() faithfully implements Massimiliano Poletto and Vivek Sarkar's
+        famous algorithm. It uses the variant that handles clobbered registers by avoiding assigning
+        ranges to those registers if the range overlaps a clobber. It's engineered to allocate registers
+        very quickly and generate inefficient code without falling off a cliff.
+        
+        The new optLevel=1 speeds up B3 by a factor of 2, and results in a 80% throughput regression.
+        Linear scan runs 4.7x faster than graph coloring on average.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * b3/B3BasicBlockUtils.h:
+        (JSC::B3::blocksInPreOrder):
+        (JSC::B3::blocksInPostOrder):
+        * b3/B3BlockWorklist.h:
+        * b3/B3CFG.h:
+        (JSC::B3::CFG::newMap):
+        * b3/B3Common.h:
+        (JSC::B3::defaultOptLevel):
+        * b3/B3Compile.h:
+        * b3/B3DuplicateTails.cpp:
+        * b3/B3EliminateCommonSubexpressions.cpp:
+        * b3/B3FixSSA.cpp:
+        (JSC::B3::demoteValues):
+        (JSC::B3::fixSSA):
+        * b3/B3FixSSA.h:
+        * b3/B3Generate.cpp:
+        (JSC::B3::prepareForGeneration):
+        (JSC::B3::generateToAir):
+        * b3/B3Generate.h:
+        * b3/B3HeapRange.cpp: Removed.
+        * b3/B3HeapRange.h:
+        (JSC::B3::HeapRange::HeapRange): Deleted.
+        (JSC::B3::HeapRange::top): Deleted.
+        (JSC::B3::HeapRange::operator==): Deleted.
+        (JSC::B3::HeapRange::operator!=): Deleted.
+        (JSC::B3::HeapRange::operator|): Deleted.
+        (JSC::B3::HeapRange::operator bool): Deleted.
+        (JSC::B3::HeapRange::begin): Deleted.
+        (JSC::B3::HeapRange::end): Deleted.
+        (JSC::B3::HeapRange::overlaps): Deleted.
+        * b3/B3LowerToAir.cpp:
+        * b3/B3MoveConstants.cpp:
+        * b3/B3PhiChildren.h:
+        * b3/B3Procedure.cpp:
+        (JSC::B3::Procedure::dump):
+        (JSC::B3::Procedure::deleteOrphans):
+        (JSC::B3::Procedure::setBlockOrderImpl):
+        * b3/B3ReduceDoubleToFloat.cpp:
+        * b3/B3ReduceStrength.cpp:
+        * b3/B3SSACalculator.h:
+        * b3/B3UseCounts.h:
+        * b3/air/AirAllocateRegistersByGraphColoring.cpp:
+        * b3/air/AirAllocateRegistersByLinearScan.cpp: Added.
+        (JSC::B3::Air::allocateRegistersByLinearScan):
+        * b3/air/AirAllocateRegistersByLinearScan.h: Added.
+        * b3/air/AirAllocateStack.cpp:
+        (JSC::B3::Air::allocateStack):
+        * b3/air/AirArg.cpp:
+        (WTF::printInternal):
+        * b3/air/AirArg.h:
+        (JSC::B3::Air::Arg::activeAt):
+        (JSC::B3::Air::Arg::timing):
+        (JSC::B3::Air::Arg::forEachPhase):
+        * b3/air/AirBasicBlock.h:
+        * b3/air/AirBlockWorklist.h:
+        * b3/air/AirCFG.h:
+        (JSC::B3::Air::CFG::newMap):
+        * b3/air/AirEliminateDeadCode.cpp:
+        (JSC::B3::Air::eliminateDeadCode):
+        * b3/air/AirFixObviousSpills.cpp:
+        * b3/air/AirFixPartialRegisterStalls.cpp:
+        (JSC::B3::Air::fixPartialRegisterStalls):
+        * b3/air/AirFixSpillsAfterTerminals.cpp: Added.
+        (JSC::B3::Air::fixSpillsAfterTerminals):
+        * b3/air/AirFixSpillsAfterTerminals.h: Added.
+        * b3/air/AirGenerate.cpp:
+        (JSC::B3::Air::prepareForGeneration):
+        (JSC::B3::Air::generate):
+        * b3/air/AirGenerate.h:
+        * b3/air/AirGenerationContext.h:
+        * b3/air/AirInsertionSet.h:
+        * b3/air/AirInst.cpp:
+        (JSC::B3::Air::Inst::needsPadding):
+        * b3/air/AirLowerAfterRegAlloc.cpp:
+        (JSC::B3::Air::lowerAfterRegAlloc):
+        * b3/air/AirLowerEntrySwitch.cpp:
+        (JSC::B3::Air::lowerEntrySwitch):
+        * b3/air/AirOpcode.opcodes:
+        * b3/air/AirPhaseInsertionSet.cpp: Added.
+        (JSC::B3::Air::PhaseInsertionSet::execute):
+        * b3/air/AirPhaseInsertionSet.h: Added.
+        (JSC::B3::Air::PhaseInsertion::PhaseInsertion):
+        (JSC::B3::Air::PhaseInsertion::phase):
+        (JSC::B3::Air::PhaseInsertion::operator<):
+        (JSC::B3::Air::PhaseInsertionSet::PhaseInsertionSet):
+        (JSC::B3::Air::PhaseInsertionSet::appendInsertion):
+        (JSC::B3::Air::PhaseInsertionSet::insertInst):
+        (JSC::B3::Air::PhaseInsertionSet::insert):
+        * b3/air/AirRegLiveness.h:
+        (JSC::B3::Air::RegLiveness::LocalCalc::LocalCalc):
+        * b3/air/AirSpillEverything.cpp:
+        (JSC::B3::Air::spillEverything):
+        * b3/air/AirTmp.cpp:
+        * b3/air/AirTmp.h:
+        (JSC::B3::Air::Tmp::tmpForIndex):
+        * b3/air/AirTmpInlines.h:
+        (JSC::B3::Air::Tmp::Indexed::Indexed):
+        (JSC::B3::Air::Tmp::Indexed::index):
+        (JSC::B3::Air::Tmp::AbsolutelyIndexed::AbsolutelyIndexed):
+        (JSC::B3::Air::Tmp::AbsolutelyIndexed::index):
+        (JSC::B3::Air::Tmp::indexed):
+        (JSC::B3::Air::Tmp::absolutelyIndexed):
+        (JSC::B3::Air::Tmp::tmpForAbsoluteIndex):
+        * b3/testb3.cpp:
+        (JSC::B3::compile):
+        (JSC::B3::testMulLoadTwice):
+        * jit/RegisterSet.h:
+        (JSC::RegisterSet::add):
+        (JSC::RegisterSet::remove):
+        * runtime/Options.h:
+        * wasm/WasmB3IRGenerator.h:
+
 2017-03-30  Youenn Fablet  <youenn@apple.com>
 
         Clean up RTCDataChannel
index a8fb999..d5bae0c 100644 (file)
                0F25F1B2181635F300522F39 /* FTLSlowPathCall.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F25F1AB181635F300522F39 /* FTLSlowPathCall.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F25F1B3181635F300522F39 /* FTLSlowPathCallKey.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F25F1AC181635F300522F39 /* FTLSlowPathCallKey.cpp */; };
                0F25F1B4181635F300522F39 /* FTLSlowPathCallKey.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F25F1AD181635F300522F39 /* FTLSlowPathCallKey.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F2AC5661E8A0B770001EE3F /* AirFixSpillsAfterTerminals.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2AC5641E8A0B760001EE3F /* AirFixSpillsAfterTerminals.cpp */; };
+               0F2AC5671E8A0B790001EE3F /* AirFixSpillsAfterTerminals.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2AC5651E8A0B760001EE3F /* AirFixSpillsAfterTerminals.h */; };
+               0F2AC56A1E8A0BD30001EE3F /* AirAllocateRegistersByLinearScan.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2AC5681E8A0BD10001EE3F /* AirAllocateRegistersByLinearScan.cpp */; };
+               0F2AC56B1E8A0BD50001EE3F /* AirAllocateRegistersByLinearScan.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2AC5691E8A0BD10001EE3F /* AirAllocateRegistersByLinearScan.h */; };
+               0F2AC56E1E8D7B000001EE3F /* AirPhaseInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2AC56C1E8D7AFF0001EE3F /* AirPhaseInsertionSet.cpp */; };
+               0F2AC56F1E8D7B030001EE3F /* AirPhaseInsertionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2AC56D1E8D7AFF0001EE3F /* AirPhaseInsertionSet.h */; };
                0F2B66AC17B6B53F00A7AE3F /* GCIncomingRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A817B6B53D00A7AE3F /* GCIncomingRefCounted.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F2B66AD17B6B54500A7AE3F /* GCIncomingRefCountedInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A917B6B53D00A7AE3F /* GCIncomingRefCountedInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F2B66AE17B6B54500A7AE3F /* GCIncomingRefCountedSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66AA17B6B53D00A7AE3F /* GCIncomingRefCountedSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FEC85BC1BE1462F0080FF74 /* B3ReduceStrength.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC85B71BE1462F0080FF74 /* B3ReduceStrength.cpp */; };
                0FEC85BD1BE1462F0080FF74 /* B3ReduceStrength.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC85B81BE1462F0080FF74 /* B3ReduceStrength.h */; };
                0FEC85C11BE167A00080FF74 /* B3Effects.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC85BE1BE167A00080FF74 /* B3Effects.h */; };
-               0FEC85C21BE167A00080FF74 /* B3HeapRange.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC85BF1BE167A00080FF74 /* B3HeapRange.cpp */; };
                0FEC85C31BE167A00080FF74 /* B3HeapRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC85C01BE167A00080FF74 /* B3HeapRange.h */; };
                0FEC85C51BE16F5A0080FF74 /* B3Effects.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC85C41BE16F5A0080FF74 /* B3Effects.cpp */; };
                0FED67B91B26256D0066CE15 /* DFGConstantHoistingPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */; };
                0F25F1AB181635F300522F39 /* FTLSlowPathCall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLSlowPathCall.h; path = ftl/FTLSlowPathCall.h; sourceTree = "<group>"; };
                0F25F1AC181635F300522F39 /* FTLSlowPathCallKey.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLSlowPathCallKey.cpp; path = ftl/FTLSlowPathCallKey.cpp; sourceTree = "<group>"; };
                0F25F1AD181635F300522F39 /* FTLSlowPathCallKey.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLSlowPathCallKey.h; path = ftl/FTLSlowPathCallKey.h; sourceTree = "<group>"; };
+               0F2AC5641E8A0B760001EE3F /* AirFixSpillsAfterTerminals.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirFixSpillsAfterTerminals.cpp; path = b3/air/AirFixSpillsAfterTerminals.cpp; sourceTree = "<group>"; };
+               0F2AC5651E8A0B760001EE3F /* AirFixSpillsAfterTerminals.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirFixSpillsAfterTerminals.h; path = b3/air/AirFixSpillsAfterTerminals.h; sourceTree = "<group>"; };
+               0F2AC5681E8A0BD10001EE3F /* AirAllocateRegistersByLinearScan.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirAllocateRegistersByLinearScan.cpp; path = b3/air/AirAllocateRegistersByLinearScan.cpp; sourceTree = "<group>"; };
+               0F2AC5691E8A0BD10001EE3F /* AirAllocateRegistersByLinearScan.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirAllocateRegistersByLinearScan.h; path = b3/air/AirAllocateRegistersByLinearScan.h; sourceTree = "<group>"; };
+               0F2AC56C1E8D7AFF0001EE3F /* AirPhaseInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirPhaseInsertionSet.cpp; path = b3/air/AirPhaseInsertionSet.cpp; sourceTree = "<group>"; };
+               0F2AC56D1E8D7AFF0001EE3F /* AirPhaseInsertionSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirPhaseInsertionSet.h; path = b3/air/AirPhaseInsertionSet.h; sourceTree = "<group>"; };
                0F2B66A817B6B53D00A7AE3F /* GCIncomingRefCounted.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = GCIncomingRefCounted.h; sourceTree = "<group>"; };
                0F2B66A917B6B53D00A7AE3F /* GCIncomingRefCountedInlines.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = GCIncomingRefCountedInlines.h; sourceTree = "<group>"; };
                0F2B66AA17B6B53D00A7AE3F /* GCIncomingRefCountedSet.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = GCIncomingRefCountedSet.h; sourceTree = "<group>"; };
                0FEC85B71BE1462F0080FF74 /* B3ReduceStrength.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3ReduceStrength.cpp; path = b3/B3ReduceStrength.cpp; sourceTree = "<group>"; };
                0FEC85B81BE1462F0080FF74 /* B3ReduceStrength.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ReduceStrength.h; path = b3/B3ReduceStrength.h; sourceTree = "<group>"; };
                0FEC85BE1BE167A00080FF74 /* B3Effects.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3Effects.h; path = b3/B3Effects.h; sourceTree = "<group>"; };
-               0FEC85BF1BE167A00080FF74 /* B3HeapRange.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3HeapRange.cpp; path = b3/B3HeapRange.cpp; sourceTree = "<group>"; };
                0FEC85C01BE167A00080FF74 /* B3HeapRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3HeapRange.h; path = b3/B3HeapRange.h; sourceTree = "<group>"; };
                0FEC85C41BE16F5A0080FF74 /* B3Effects.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3Effects.cpp; path = b3/B3Effects.cpp; sourceTree = "<group>"; };
                0FED67B71B26256D0066CE15 /* DFGConstantHoistingPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGConstantHoistingPhase.cpp; path = dfg/DFGConstantHoistingPhase.cpp; sourceTree = "<group>"; };
                                0FEC84CF1BDACDAC0080FF74 /* B3Generate.h */,
                                0F2C63B51E6343E800C13839 /* B3GenericBlockInsertionSet.h */,
                                0FEC84D01BDACDAC0080FF74 /* B3GenericFrequentedBlock.h */,
-                               0FEC85BF1BE167A00080FF74 /* B3HeapRange.cpp */,
                                0FEC85C01BE167A00080FF74 /* B3HeapRange.h */,
                                DC69B99A1D15F90F002E3C00 /* B3InferSwitches.cpp */,
                                DC69B99B1D15F90F002E3C00 /* B3InferSwitches.h */,
                        children = (
                                7965C2141E5D799600B7591D /* AirAllocateRegistersByGraphColoring.cpp */,
                                7965C2151E5D799600B7591D /* AirAllocateRegistersByGraphColoring.h */,
+                               0F2AC5681E8A0BD10001EE3F /* AirAllocateRegistersByLinearScan.cpp */,
+                               0F2AC5691E8A0BD10001EE3F /* AirAllocateRegistersByLinearScan.h */,
                                0FEC85481BDACDC70080FF74 /* AirAllocateStack.cpp */,
                                0FEC85491BDACDC70080FF74 /* AirAllocateStack.h */,
                                0FEC854A1BDACDC70080FF74 /* AirArg.cpp */,
                                0F4DE1CD1C4C1B54004D6C11 /* AirFixObviousSpills.h */,
                                262D85B41C0D650F006ACB61 /* AirFixPartialRegisterStalls.cpp */,
                                262D85B51C0D650F006ACB61 /* AirFixPartialRegisterStalls.h */,
+                               0F2AC5641E8A0B760001EE3F /* AirFixSpillsAfterTerminals.cpp */,
+                               0F2AC5651E8A0B760001EE3F /* AirFixSpillsAfterTerminals.h */,
                                0FEC85521BDACDC70080FF74 /* AirFrequentedBlock.h */,
                                0FEC85531BDACDC70080FF74 /* AirGenerate.cpp */,
                                0FEC85541BDACDC70080FF74 /* AirGenerate.h */,
                                0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */,
                                0F9CABC61DB54A760008E83B /* AirPadInterference.cpp */,
                                0F9CABC71DB54A760008E83B /* AirPadInterference.h */,
+                               0F2AC56C1E8D7AFF0001EE3F /* AirPhaseInsertionSet.cpp */,
+                               0F2AC56D1E8D7AFF0001EE3F /* AirPhaseInsertionSet.h */,
                                0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */,
                                0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */,
                                0FF4B4BA1E88449500DBBE86 /* AirRegLiveness.cpp */,
                                0FEC85101BDACDAC0080FF74 /* B3Const64Value.h in Headers */,
                                0FEC85121BDACDAC0080FF74 /* B3ConstDoubleValue.h in Headers */,
                                43422A631C158E6D00E2EB98 /* B3ConstFloatValue.h in Headers */,
+                               0F2AC56B1E8A0BD50001EE3F /* AirAllocateRegistersByLinearScan.h in Headers */,
                                0FEC85B31BDED9570080FF74 /* B3ConstPtrValue.h in Headers */,
                                0F338DF61BE93D550013C88F /* B3ConstrainedValue.h in Headers */,
                                0F2C63B81E6343F700C13839 /* B3GenericBlockInsertionSet.h in Headers */,
                                0FFFC95814EF90A200C72532 /* DFGCFAPhase.h in Headers */,
                                0F3B3A281544C997003ED0FF /* DFGCFGSimplificationPhase.h in Headers */,
                                0F9D36951AE9CC33000D4DFB /* DFGCleanUpPhase.h in Headers */,
+                               0F2AC56F1E8D7B030001EE3F /* AirPhaseInsertionSet.h in Headers */,
                                A77A424017A0BBFD00A8DB81 /* DFGClobberize.h in Headers */,
                                A77A424217A0BBFD00A8DB81 /* DFGClobberSet.h in Headers */,
                                0F3C1F1B1B868E7900ABB08B /* DFGClobbersExitState.h in Headers */,
                                709FB86A1AE335C60039D069 /* WeakSetConstructor.h in Headers */,
                                14150133154BB13F005D8C98 /* WeakSetInlines.h in Headers */,
                                709FB86C1AE335C60039D069 /* WeakSetPrototype.h in Headers */,
+                               0F2AC5671E8A0B790001EE3F /* AirFixSpillsAfterTerminals.h in Headers */,
                                AD2FCBED1DB58DAD00B3E736 /* WebAssemblyCompileErrorConstructor.h in Headers */,
                                AD2FCC161DB59CB200B3E736 /* WebAssemblyCompileErrorConstructor.lut.h in Headers */,
                                AD2FCBEF1DB58DAD00B3E736 /* WebAssemblyCompileErrorPrototype.h in Headers */,
                                0F725CAF1C506D3B00AD943A /* B3FoldPathConstants.cpp in Sources */,
                                0FEC85151BDACDAC0080FF74 /* B3FrequencyClass.cpp in Sources */,
                                0FEC85181BDACDAC0080FF74 /* B3Generate.cpp in Sources */,
-                               0FEC85C21BE167A00080FF74 /* B3HeapRange.cpp in Sources */,
                                DC69B99C1D15F912002E3C00 /* B3InferSwitches.cpp in Sources */,
                                0FEC85B91BE1462F0080FF74 /* B3InsertionSet.cpp in Sources */,
                                0FDF67D31D9C6D2A001B9825 /* B3Kind.cpp in Sources */,
                                A78A9776179738B8009DF744 /* DFGFinalizer.cpp in Sources */,
                                0F2BDC15151C5D4D00CD8910 /* DFGFixupPhase.cpp in Sources */,
                                0F20177F1DCADC3300EA5950 /* DFGFlowIndexing.cpp in Sources */,
+                               0F2AC56A1E8A0BD30001EE3F /* AirAllocateRegistersByLinearScan.cpp in Sources */,
                                0F9D339617FFC4E60073C2BC /* DFGFlushedAt.cpp in Sources */,
                                A7D89CF717A0B8CC00773AD8 /* DFGFlushFormat.cpp in Sources */,
                                0F69CC88193AC60A0045759E /* DFGFrozenValue.cpp in Sources */,
                                2A83638518D7D0EE0000EBCC /* EdenGCActivityCallback.cpp in Sources */,
                                99E45A2518A1B2590026D88F /* EncodedValue.cpp in Sources */,
                                147F39C7107EC37600427A48 /* Error.cpp in Sources */,
+                               0F2AC5661E8A0B770001EE3F /* AirFixSpillsAfterTerminals.cpp in Sources */,
                                147F39C8107EC37600427A48 /* ErrorConstructor.cpp in Sources */,
                                FEB58C14187B8B160098EF0B /* ErrorHandlingScope.cpp in Sources */,
                                147F39C9107EC37600427A48 /* ErrorInstance.cpp in Sources */,
                                E35E035F1B7AB43E0073AD2A /* InspectorInstrumentationObject.cpp in Sources */,
                                A532438B18568335002ED692 /* InspectorProtocolObjects.cpp in Sources */,
                                A50E4B6118809DD50068A46D /* InspectorRuntimeAgent.cpp in Sources */,
+                               0F2AC56E1E8D7B000001EE3F /* AirPhaseInsertionSet.cpp in Sources */,
                                0F2C63BB1E63440A00C13839 /* AirBlockInsertionSet.cpp in Sources */,
                                A55165D21BDF0B98003B75C1 /* InspectorScriptProfilerAgent.cpp in Sources */,
                                A593CF821840377100BFCE27 /* InspectorValues.cpp in Sources */,
index e5998c8..2459178 100644 (file)
@@ -114,7 +114,7 @@ template<typename BasicBlock>
 Vector<BasicBlock*> blocksInPreOrder(BasicBlock* root)
 {
     Vector<BasicBlock*> result;
-    GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> worklist;
+    GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> worklist;
     worklist.push(root);
     while (BasicBlock* block = worklist.pop()) {
         result.append(block);
@@ -128,7 +128,7 @@ template<typename BasicBlock>
 Vector<BasicBlock*> blocksInPostOrder(BasicBlock* root)
 {
     Vector<BasicBlock*> result;
-    PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> worklist;
+    PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> worklist;
     worklist.push(root);
     while (GraphNodeWithOrder<BasicBlock*> item = worklist.pop()) {
         switch (item.order) {
index 6fa197c..5b1f031 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -35,7 +35,7 @@ namespace JSC { namespace B3 {
 
 class BasicBlock;
 
-typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> BlockWorklist;
+typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> BlockWorklist;
 
 // When you say BlockWith<int> you should read it as "block with an int".
 template<typename T> using BlockWith = GraphNodeWith<BasicBlock*, T>;
@@ -44,13 +44,13 @@ template<typename T> using BlockWith = GraphNodeWith<BasicBlock*, T>;
 // permits forcibly enqueueing things even if the block has already been seen. It's useful for
 // things like building a spanning tree, in which case T (the auxiliary payload) would be the
 // successor index.
-template<typename T> using ExtendedBlockWorklist = ExtendedGraphNodeWorklist<BasicBlock*, T, IndexSet<BasicBlock>>;
+template<typename T> using ExtendedBlockWorklist = ExtendedGraphNodeWorklist<BasicBlock*, T, IndexSet<BasicBlock*>>;
 
 typedef GraphVisitOrder VisitOrder;
 
 typedef GraphNodeWithOrder<BasicBlock*> BlockWithOrder;
 
-typedef PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> PostOrderBlockWorklist;
+typedef PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> PostOrderBlockWorklist;
 
 } } // namespace JSC::B3
 
index 3d1418e..36606c9 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -39,8 +39,8 @@ class CFG {
     WTF_MAKE_FAST_ALLOCATED;
 public:
     typedef BasicBlock* Node;
-    typedef IndexSet<BasicBlock> Set;
-    template<typename T> using Map = IndexMap<BasicBlock, T>;
+    typedef IndexSet<BasicBlock*> Set;
+    template<typename T> using Map = IndexMap<BasicBlock*, T>;
     typedef Vector<BasicBlock*, 4> List;
 
     CFG(Procedure& proc)
@@ -51,7 +51,7 @@ public:
     Node root() { return m_proc[0]; }
 
     template<typename T>
-    Map<T> newMap() { return IndexMap<JSC::B3::BasicBlock, T>(m_proc.size()); }
+    Map<T> newMap() { return IndexMap<JSC::B3::BasicBlock*, T>(m_proc.size()); }
 
     SuccessorCollection<BasicBlock, BasicBlock::SuccessorList> successors(Node node) { return node->successorBlocks(); }
     BasicBlock::PredecessorList& predecessors(Node node) { return node->predecessors(); }
index 41e8ee0..4a94da7 100644 (file)
@@ -28,6 +28,7 @@
 #if ENABLE(B3_JIT)
 
 #include "JSExportMacros.h"
+#include "Options.h"
 #include <wtf/Optional.h>
 
 namespace JSC { namespace B3 {
@@ -170,6 +171,13 @@ static IntType rotateLeft(IntType value, int32_t shift)
     return (uValue << shift) | (uValue >> ((bits - shift) & mask));
 }
 
+inline unsigned defaultOptLevel()
+{
+    // This should almost always return 2, but we allow this default to be lowered for testing. Some
+    // components will deliberately set the optLevel.
+    return Options::defaultB3OptLevel();
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 9538cc0..71ef490 100644 (file)
@@ -27,6 +27,7 @@
 
 #if ENABLE(B3_JIT)
 
+#include "B3Common.h"
 #include "B3Compilation.h"
 
 namespace JSC {
@@ -45,7 +46,7 @@ class Procedure;
 // Then you keep the Compilation object alive for as long as you want to be able to run the code.
 // If this API feels too high-level, you can use B3::generate() directly.
 
-JS_EXPORT_PRIVATE Compilation compile(Procedure&, unsigned optLevel = 1);
+JS_EXPORT_PRIVATE Compilation compile(Procedure&, unsigned optLevel = defaultOptLevel());
 
 } } // namespace JSC::B3
 
index fe94a60..fd65790 100644 (file)
@@ -68,7 +68,7 @@ public:
 
         m_proc.resetValueOwners();
 
-        IndexSet<BasicBlock> candidates;
+        IndexSet<BasicBlock*> candidates;
 
         for (BasicBlock* block : m_proc) {
             if (block->size() > m_maxSize)
@@ -82,7 +82,7 @@ public:
         }
 
         // Collect the set of values that must be de-SSA'd.
-        IndexSet<Value> valuesToDemote;
+        IndexSet<Value*> valuesToDemote;
         for (BasicBlock* block : m_proc) {
             for (Value* value : *block) {
                 if (value->opcode() == Phi && candidates.contains(block))
index 8c519a8..b0bef8e 100644 (file)
@@ -682,7 +682,7 @@ private:
     Dominators& m_dominators;
     PureCSE m_pureCSE;
     
-    IndexMap<BasicBlock, ImpureBlockData> m_impureBlockData;
+    IndexMap<BasicBlock*, ImpureBlockData> m_impureBlockData;
 
     ImpureBlockData m_data;
 
index 3828887..d41214f 100644 (file)
@@ -49,7 +49,7 @@ namespace {
 const bool verbose = false;
 } // anonymous namespace
 
-void demoteValues(Procedure& proc, const IndexSet<Value>& values)
+void demoteValues(Procedure& proc, const IndexSet<Value*>& values)
 {
     HashMap<Value*, Variable*> map;
     HashMap<Value*, Variable*> phiMap;
@@ -121,7 +121,7 @@ bool fixSSA(Procedure& proc)
     // Just for sanity, remove any unused variables first. It's unlikely that this code has any
     // bugs having to do with dead variables, but it would be silly to have to fix such a bug if
     // it did arise.
-    IndexSet<Variable> liveVariables;
+    IndexSet<Variable*> liveVariables;
     for (Value* value : proc.values()) {
         if (VariableValue* variableValue = value->as<VariableValue>())
             liveVariables.add(variableValue->variable());
@@ -145,7 +145,7 @@ bool fixSSA(Procedure& proc)
 
     // Create a SSACalculator::Variable ("calcVar") for every variable.
     Vector<Variable*> calcVarToVariable;
-    IndexMap<Variable, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
+    IndexMap<Variable*, SSACalculator::Variable*> variableToCalcVar(proc.variables().size());
 
     for (Variable* variable : proc.variables()) {
         SSACalculator::Variable* calcVar = ssa.newVariable();
@@ -185,7 +185,7 @@ bool fixSSA(Procedure& proc)
 
     // Now perform the conversion.
     InsertionSet insertionSet(proc);
-    IndexMap<Variable, Value*> mapping(proc.variables().size());
+    IndexMap<Variable*, Value*> mapping(proc.variables().size());
     for (BasicBlock* block : proc.blocksInPreOrder()) {
         mapping.clear();
 
index 775c322..06f0240 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -37,7 +37,7 @@ class Procedure;
 
 // Turns all mentions of the given values into accesses to variables. This is meant to be used
 // from phases that don't like SSA for whatever reason.
-void demoteValues(Procedure&, const IndexSet<Value>&);
+void demoteValues(Procedure&, const IndexSet<Value*>&);
 
 // This fixes SSA for you. Use this after you have done demoteValues() and you have performed
 // whatever evil transformation you needed.
index d141be7..fdd2800 100644 (file)
@@ -57,7 +57,7 @@ void prepareForGeneration(Procedure& procedure, unsigned optLevel)
     TimingScope timingScope("prepareForGeneration");
 
     generateToAir(procedure, optLevel);
-    Air::prepareForGeneration(procedure.code());
+    Air::prepareForGeneration(procedure.code(), optLevel);
 }
 
 void generate(Procedure& procedure, CCallHelpers& jit)
@@ -80,7 +80,7 @@ void generateToAir(Procedure& procedure, unsigned optLevel)
     if (shouldValidateIR())
         validate(procedure);
 
-    if (optLevel >= 1) {
+    if (optLevel >= 2) {
         reduceDoubleToFloat(procedure);
         reduceStrength(procedure);
         eliminateCommonSubexpressions(procedure);
@@ -91,12 +91,15 @@ void generateToAir(Procedure& procedure, unsigned optLevel)
         
         // FIXME: Add more optimizations here.
         // https://bugs.webkit.org/show_bug.cgi?id=150507
+    } else if (optLevel >= 1) {
+        // FIXME: Explore better "quick mode" optimizations.
+        reduceStrength(procedure);
     }
 
     // This puts the IR in quirks mode.
     lowerMacros(procedure);
 
-    if (optLevel >= 1) {
+    if (optLevel >= 2) {
         reduceStrength(procedure);
 
         // FIXME: Add more optimizations here.
index 2ffcd0e..14aa133 100644 (file)
@@ -27,6 +27,8 @@
 
 #if ENABLE(B3_JIT)
 
+#include "B3Common.h"
+
 namespace JSC {
 
 class CCallHelpers;
@@ -38,7 +40,7 @@ namespace Air { class Code; }
 
 // This takes a B3::Procedure, optimizes it in-place, lowers it to Air, and prepares the Air for
 // generation.
-JS_EXPORT_PRIVATE void prepareForGeneration(Procedure&, unsigned optLevel = 1);
+JS_EXPORT_PRIVATE void prepareForGeneration(Procedure&, unsigned optLevel = defaultOptLevel());
 
 // This takes a B3::Procedure that has been prepared for generation (i.e. it has been lowered to Air and
 // the Air has been prepared for generation) and generates it. This is the equivalent of calling
@@ -48,7 +50,7 @@ JS_EXPORT_PRIVATE void generate(Procedure&, CCallHelpers&);
 // This takes a B3::Procedure, optimizes it in-place, and lowers it to Air. You can then generate
 // the Air to machine code using Air::prepareForGeneration() and Air::generate() on the Procedure's
 // code().
-void generateToAir(Procedure&, unsigned optLevel = 1);
+void generateToAir(Procedure&, unsigned optLevel = defaultOptLevel());
 
 } } // namespace JSC::B3
 
index 3c15a6e..5ddd591 100644 (file)
 
 #if ENABLE(B3_JIT)
 
-#include <limits.h>
-#include <wtf/MathExtras.h>
-#include <wtf/PrintStream.h>
+#include <wtf/Range.h>
 
 namespace JSC { namespace B3 {
 
 // Alias analysis in B3 is done by checking if two integer ranges overlap. This is powerful enough
 // to be used for TBAA-style alias analysis used by the DFG, FTL, and LLVM: you just turn each node
 // in the tree of abstract heaps into a pre/post range.
-//
-// Note that the 'begin' is inclusive, while the 'end' is exclusive. These two ranges are non-
-// overlapping:
-//
-//     rangeA = 0...8
-//     rangeB = 8...16
 
-class HeapRange {
-public:
-    typedef unsigned Type;
-    
-    HeapRange()
-        : m_begin(0)
-        , m_end(0)
-    {
-    }
-
-    explicit HeapRange(unsigned value)
-        : m_begin(value)
-        , m_end(value + 1)
-    {
-        ASSERT(m_end >= m_begin);
-    }
-
-    HeapRange(unsigned begin, unsigned end)
-        : m_begin(begin)
-        , m_end(end)
-    {
-        ASSERT(m_end >= m_begin);
-        if (m_begin == m_end) {
-            // Canonicalize empty ranges.
-            m_begin = 0;
-            m_end = 0;
-        }
-    }
-
-    static HeapRange top()
-    {
-        return HeapRange(0, UINT_MAX);
-    }
-
-    bool operator==(const HeapRange& other) const
-    {
-        return m_begin == other.m_begin
-            && m_end == other.m_end;
-    }
-
-    bool operator!=(const HeapRange& other) const
-    {
-        return !(*this == other);
-    }
-    
-    HeapRange operator|(const HeapRange& other) const
-    {
-        return HeapRange(
-            std::min(m_begin, other.m_begin),
-            std::max(m_end, other.m_end));
-    }
-    
-    explicit operator bool() const { return m_begin != m_end; }
-
-    unsigned begin() const { return m_begin; }
-    unsigned end() const { return m_end; }
-
-    bool overlaps(const HeapRange& other) const
-    {
-        return WTF::rangesOverlap(m_begin, m_end, other.m_begin, other.m_end);
-    }
-
-    JS_EXPORT_PRIVATE void dump(PrintStream& out) const;
-
-private:
-    unsigned m_begin;
-    unsigned m_end;
-};
+typedef Range<unsigned> HeapRange;
 
 } } // namespace JSC::B3
 
index 8a20067..3e26c4f 100644 (file)
@@ -3379,10 +3379,10 @@ private:
         RELEASE_ASSERT_NOT_REACHED();
     }
     
-    IndexSet<Value> m_locked; // These are values that will have no Tmp in Air.
-    IndexMap<Value, Tmp> m_valueToTmp; // These are values that must have a Tmp in Air. We say that a Value* with a non-null Tmp is "pinned".
-    IndexMap<Value, Tmp> m_phiToTmp; // Each Phi gets its own Tmp.
-    IndexMap<B3::BasicBlock, Air::BasicBlock*> m_blockToBlock;
+    IndexSet<Value*> m_locked; // These are values that will have no Tmp in Air.
+    IndexMap<Value*, Tmp> m_valueToTmp; // These are values that must have a Tmp in Air. We say that a Value* with a non-null Tmp is "pinned".
+    IndexMap<Value*, Tmp> m_phiToTmp; // Each Phi gets its own Tmp.
+    IndexMap<B3::BasicBlock*, Air::BasicBlock*> m_blockToBlock;
     HashMap<B3::StackSlot*, Air::StackSlot*> m_stackToStack;
     HashMap<Variable*, Tmp> m_variableToTmp;
 
index 1f9d8a0..a32c58f 100644 (file)
@@ -73,7 +73,7 @@ private:
     {
         Dominators& dominators = m_proc.dominators();
         HashMap<ValueKey, Value*> valueForConstant;
-        IndexMap<BasicBlock, Vector<Value*>> materializations(m_proc.size());
+        IndexMap<BasicBlock*, Vector<Value*>> materializations(m_proc.size());
 
         // We determine where things get materialized based on where they are used.
         for (BasicBlock* block : m_proc) {
@@ -274,7 +274,7 @@ private:
         for (auto& entry : m_constTable)
             m_dataSection[entry.value] = entry.key.value();
 
-        IndexSet<Value> offLimits;
+        IndexSet<Value*> offLimits;
         for (BasicBlock* block : m_proc) {
             for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
                 StackmapValue* value = block->at(valueIndex)->as<StackmapValue>();
index 22b8277..1d2c73d 100644 (file)
@@ -168,7 +168,7 @@ public:
     const Vector<Value*, 8>& phis() const { return m_phis; }
 
 private:
-    IndexMap<Value, Vector<UpsilonValue*>> m_upsilons;
+    IndexMap<Value*, Vector<UpsilonValue*>> m_upsilons;
     Vector<Value*, 8> m_phis;
 };
 
index a7dad4f..526ab7c 100644 (file)
@@ -204,7 +204,7 @@ void Procedure::invalidateCFG()
 
 void Procedure::dump(PrintStream& out) const
 {
-    IndexSet<Value> valuesInBlocks;
+    IndexSet<Value*> valuesInBlocks;
     for (BasicBlock* block : *this) {
         out.print(deepDump(*this, block));
         valuesInBlocks.addAll(*block);
@@ -263,7 +263,7 @@ void Procedure::deleteValue(Value* value)
 
 void Procedure::deleteOrphans()
 {
-    IndexSet<Value> valuesInBlocks;
+    IndexSet<Value*> valuesInBlocks;
     for (BasicBlock* block : *this)
         valuesInBlocks.addAll(*block);
 
@@ -351,7 +351,7 @@ Value* Procedure::addValueImpl(Value* value)
 
 void Procedure::setBlockOrderImpl(Vector<BasicBlock*>& blocks)
 {
-    IndexSet<BasicBlock> blocksSet;
+    IndexSet<BasicBlock*> blocksSet;
     blocksSet.addAll(blocks);
 
     for (BasicBlock* block : *this) {
index ef92811..23abf3a 100644 (file)
@@ -424,18 +424,18 @@ private:
 
     // Set of all the Double values that are actually used as Double.
     // Converting any of them to Float would lose precision.
-    IndexSet<Value> m_valuesUsedAsDouble;
+    IndexSet<Value*> m_valuesUsedAsDouble;
 
     // Set of all the Phi of type Double that really contains a Double.
     // Any Double Phi not in the set can be converted to Float without losing precision.
-    IndexSet<Value> m_phisContainingDouble;
+    IndexSet<Value*> m_phisContainingDouble;
 
     // Any value that was converted from producing a Double to producing a Float.
     // This set does not include Phi-Upsilons.
-    IndexSet<Value> m_convertedValue;
+    IndexSet<Value*> m_convertedValue;
 
     // Any value that previously produced Double and now produce Float.
-    IndexSet<Value> m_convertedPhis;
+    IndexSet<Value*> m_convertedPhis;
 };
 
 void printGraphIfConverting(Procedure& procedure)
index 3c6bf7c..b068637 100644 (file)
@@ -2392,7 +2392,7 @@ private:
 
     void killDeadCode()
     {
-        GraphNodeWorklist<Value*, IndexSet<Value>> worklist;
+        GraphNodeWorklist<Value*, IndexSet<Value*>> worklist;
         Vector<UpsilonValue*, 64> upsilons;
         for (BasicBlock* block : m_proc) {
             for (Value* value : *block) {
@@ -2429,7 +2429,7 @@ private:
                 break;
         }
 
-        IndexSet<Variable> liveVariables;
+        IndexSet<Variable*> liveVariables;
         
         for (BasicBlock* block : m_proc) {
             size_t sourceIndex = 0;
index be9a064..622995a 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -156,7 +156,7 @@ private:
         Vector<Def*> m_phis;
     };
     
-    IndexMap<BasicBlock, BlockData> m_data;
+    IndexMap<BasicBlock*, BlockData> m_data;
 
     Dominators* m_dominators { nullptr };
     Procedure& m_proc;
index f5a0492..848e238 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -48,7 +48,7 @@ private:
         unsigned numUsingInstructions { 0 };
     };
     
-    IndexMap<Value, Counts> m_counts;
+    IndexMap<Value*, Counts> m_counts;
 };
 
 } } // namespace JSC::B3
index 5245b25..41cbc99 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(B3_JIT)
 
 #include "AirCode.h"
+#include "AirFixSpillsAfterTerminals.h"
 #include "AirInsertionSet.h"
 #include "AirInstInlines.h"
 #include "AirLiveness.h"
@@ -1585,6 +1586,9 @@ protected:
         m_coalescingCandidates.clear();
         m_worklistMoves.clear();
 
+        // FIXME: It seems like we don't need to recompute liveness. We just need to update its data
+        // structures so that it knows that the newly introduced temporaries are not live at any basic
+        // block boundary. This should trivially be true for now.
         TmpLiveness<bank> liveness(m_code);
         for (BasicBlock* block : m_code) {
             typename TmpLiveness<bank>::LocalCalc localCalc(liveness, block);
@@ -1798,7 +1802,7 @@ public:
         m_numIterations = 0;
         allocateOnBank<FP>();
 
-        fixSpillsAfterTerminals();
+        fixSpillsAfterTerminals(m_code);
 
         if (reportStats)
             dataLog("Num iterations = ", m_numIterations, "\n");
@@ -1954,7 +1958,7 @@ private:
                 }
 
                 inst.forEachTmpFast([&] (Tmp& tmp) {
-                    if (tmp.isReg() || tmp.isGP() == (bank != GP))
+                    if (tmp.isReg() || tmp.bank() != bank)
                         return;
 
                     Tmp aliasTmp = allocator.getAlias(tmp);
@@ -2132,7 +2136,7 @@ private:
                     // other. As well, we need this if the previous instruction had any late effects,
                     // since otherwise the scratch would appear to interfere with those. On the other
                     // hand, the late use added at the end of this spill move (previously it was just a
-                    // late def) doesn't change the padding situation: the late def would have already
+                    // late def) doesn't change the padding situation.: the late def would have already
                     // caused it to report hasLateUseOrDef in Inst::needsPadding.
                     insertionSet.insert(instIndex, Nop, inst.origin);
                     continue;
@@ -2169,9 +2173,12 @@ private:
 
                     tmp = m_code.newTmp(bank);
                     unspillableTmps.add(AbsoluteTmpMapper<bank>::absoluteIndex(tmp));
+                    
+                    if (role == Arg::Scratch)
+                        return;
 
                     Arg arg = Arg::stack(stackSlotEntry->value);
-                    if (Arg::isAnyUse(role) && role != Arg::Scratch)
+                    if (Arg::isAnyUse(role))
                         insertionSet.insert(instIndex, move, inst.origin, arg, tmp);
                     if (Arg::isAnyDef(role))
                         insertionSet.insert(instIndex + 1, move, inst.origin, tmp, arg);
@@ -2187,66 +2194,6 @@ private:
         }
     }
 
-    void fixSpillsAfterTerminals()
-    {
-        // Because there may be terminals that produce values, IRC may
-        // want to spill those terminals. It'll happen to spill it after
-        // the terminal. If we left the graph in this state, it'd be invalid
-        // because a terminal must be the last instruction in a block.
-        // We fix that here.
-
-        InsertionSet insertionSet(m_code);
-
-        bool addedBlocks = false;
-
-        for (BasicBlock* block : m_code) {
-            unsigned terminalIndex = block->size();
-            bool foundTerminal = false;
-            while (terminalIndex--) {
-                if (block->at(terminalIndex).isTerminal()) {
-                    foundTerminal = true;
-                    break;
-                }
-            }
-            ASSERT_UNUSED(foundTerminal, foundTerminal);
-
-            if (terminalIndex == block->size() - 1)
-                continue;
-
-            // There must be instructions after the terminal because it's not the last instruction.
-            ASSERT(terminalIndex < block->size() - 1);
-            Vector<Inst, 1> instsToMove;
-            for (unsigned i = terminalIndex + 1; i < block->size(); i++)
-                instsToMove.append(block->at(i));
-            RELEASE_ASSERT(instsToMove.size());
-
-            for (FrequentedBlock& frequentedSuccessor : block->successors()) {
-                BasicBlock* successor = frequentedSuccessor.block();
-                // If successor's only predecessor is block, we can plant the spill inside
-                // the successor. Otherwise, we must split the critical edge and create
-                // a new block for the spill.
-                if (successor->numPredecessors() == 1) {
-                    insertionSet.insertInsts(0, instsToMove);
-                    insertionSet.execute(successor);
-                } else {
-                    addedBlocks = true;
-                    // FIXME: We probably want better block ordering here.
-                    BasicBlock* newBlock = m_code.addBlock();
-                    for (const Inst& inst : instsToMove)
-                        newBlock->appendInst(inst);
-                    newBlock->appendInst(Inst(Jump, instsToMove.last().origin));
-                    newBlock->successors().append(successor);
-                    frequentedSuccessor.block() = newBlock;
-                }
-            }
-
-            block->resize(terminalIndex + 1);
-        }
-
-        if (addedBlocks)
-            m_code.resetReachability();
-    }
-
     Code& m_code;
     TmpWidth m_tmpWidth;
     UseCounts<Tmp>& m_useCounts;
diff --git a/Source/JavaScriptCore/b3/air/AirAllocateRegistersByLinearScan.cpp b/Source/JavaScriptCore/b3/air/AirAllocateRegistersByLinearScan.cpp
new file mode 100644 (file)
index 0000000..0be20ab
--- /dev/null
@@ -0,0 +1,594 @@
+/*
+ * Copyright (C) 2017 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 "AirAllocateRegistersByLinearScan.h"
+
+#if ENABLE(B3_JIT)
+
+#include "AirArgInlines.h"
+#include "AirCode.h"
+#include "AirFixSpillsAfterTerminals.h"
+#include "AirPhaseInsertionSet.h"
+#include "AirInstInlines.h"
+#include "AirLiveness.h"
+#include "AirPadInterference.h"
+#include "AirPhaseScope.h"
+#include "AirRegLiveness.h"
+#include "AirTmpInlines.h"
+#include <wtf/ListDump.h>
+#include <wtf/Range.h>
+
+namespace JSC { namespace B3 { namespace Air {
+
+namespace {
+
+NO_RETURN_DUE_TO_CRASH NEVER_INLINE void crash()
+{
+    CRASH();
+}
+
+#undef RELEASE_ASSERT
+#define RELEASE_ASSERT(assertion) do { \
+    if (!(assertion)) { \
+        WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
+        crash(); \
+    } \
+} while (0)
+
+bool verbose() { return Options::airLinearScanVerbose(); }
+
+// Phase constants we use for the PhaseInsertionSet.
+const unsigned firstPhase = 0;
+const unsigned secondPhase = 1;
+
+typedef Range<size_t> Interval;
+
+struct TmpData {
+    void dump(PrintStream& out) const
+    {
+        out.print("{interval = ", interval, ", spilled = ", pointerDump(spilled), ", assigned = ", assigned, ", isUnspillable = ", isUnspillable, ", possibleRegs = ", possibleRegs, ", didBuildPossibleRegs = ", didBuildPossibleRegs, "}");
+    }
+    
+    void validate()
+    {
+        RELEASE_ASSERT(!(spilled && assigned));
+    }
+    
+    Interval interval;
+    StackSlot* spilled { nullptr };
+    RegisterSet possibleRegs;
+    Reg assigned;
+    bool isUnspillable { false };
+    bool didBuildPossibleRegs { false };
+};
+
+struct Clobber {
+    Clobber()
+    {
+    }
+    
+    Clobber(size_t index, RegisterSet regs)
+        : index(index)
+        , regs(regs)
+    {
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        out.print(index, ":", regs);
+    }
+    
+    size_t index { 0 };
+    RegisterSet regs;
+};
+
+template<Bank bank>
+class LinearScan {
+public:
+    LinearScan(Code& code)
+        : m_code(code)
+        , m_startIndex(code.size())
+        , m_map(code.numTmps(bank))
+        , m_insertionSets(code.size())
+    {
+    }
+    
+    void run()
+    {
+        buildRegisterSet();
+        buildIndices();
+        buildIntervals();
+        if (shouldSpillEverything()) {
+            spillEverything();
+            emitSpillCode();
+        }
+        for (;;) {
+            prepareIntervals();
+            attemptScan();
+            if (!m_didSpill)
+                break;
+            emitSpillCode();
+        }
+        insertSpillCode();
+        assignRegisters();
+    }
+    
+private:
+    void buildRegisterSet()
+    {
+        m_registers = m_code.regsInPriorityOrder(bank);
+        m_registerSet.setAll(m_registers);
+    }
+
+    void buildIndices()
+    {
+        size_t index = 0;
+        for (BasicBlock* block : m_code) {
+            m_startIndex[block] = index;
+            index += block->size() * 2;
+        }
+    }
+    
+    size_t indexOfHead(BasicBlock* block)
+    {
+        return m_startIndex[block];
+    }
+    
+    size_t indexOfTail(BasicBlock* block)
+    {
+        return indexOfHead(block) + block->size() * 2;
+    }
+    
+    Interval interval(size_t indexOfEarly, Arg::Timing timing)
+    {
+        switch (timing) {
+        case Arg::OnlyEarly:
+            return Interval(indexOfEarly);
+        case Arg::OnlyLate:
+            return Interval(indexOfEarly + 1);
+        case Arg::EarlyAndLate:
+            return Interval(indexOfEarly, indexOfEarly + 2);
+        }
+        ASSERT_NOT_REACHED();
+        return Interval();
+    }
+    
+    void buildIntervals()
+    {
+        TmpLiveness<bank> liveness(m_code);
+        
+        for (BasicBlock* block : m_code) {
+            size_t indexOfHead = this->indexOfHead(block);
+            size_t indexOfTail = this->indexOfTail(block);
+            if (verbose()) {
+                dataLog("At block ", pointerDump(block), "\n");
+                dataLog("  indexOfHead = ", indexOfHead, "\n");
+                dataLog("  idnexOfTail = ", indexOfTail, "\n");
+            }
+            for (Tmp tmp : liveness.liveAtHead(block)) {
+                if (!tmp.isReg())
+                    m_map[tmp].interval |= Interval(indexOfHead);
+            }
+            for (Tmp tmp : liveness.liveAtTail(block)) {
+                if (!tmp.isReg())
+                    m_map[tmp].interval |= Interval(indexOfTail);
+            }
+            
+            for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+                Inst& inst = block->at(instIndex);
+                size_t indexOfEarly = indexOfHead + instIndex * 2;
+                inst.forEachTmp(
+                    [&] (Tmp& tmp, Arg::Role role, Bank tmpBank, Width) {
+                        if (tmp.isReg())
+                            return;
+                        if (tmpBank != bank)
+                            return;
+                        m_map[tmp].interval |= interval(indexOfEarly, Arg::timing(role));
+                    });
+            }
+
+            RegLiveness::LocalCalc localCalc(liveness, block);
+            
+            auto record = [&] (unsigned instIndex) {
+                RegisterSet regs = localCalc.live();
+                if (Inst* prev = block->get(instIndex - 1)) {
+                    RegisterSet prevRegs = regs;
+                    prev->forEach<Reg>(
+                        [&] (Reg& reg, Arg::Role role, Bank, Width) {
+                            if (Arg::isLateDef(role))
+                                prevRegs.add(reg);
+                        });
+                    if (prev->kind.opcode == Patch)
+                        prevRegs.merge(prev->extraClobberedRegs());
+                    prevRegs.filter(m_registerSet);
+                    if (!prevRegs.isEmpty())
+                        m_clobbers.append(Clobber(indexOfHead + instIndex * 2 - 1, prevRegs));
+                }
+                if (Inst* next = block->get(instIndex)) {
+                    RegisterSet nextRegs = regs;
+                    next->forEach<Reg>(
+                        [&] (Reg& reg, Arg::Role role, Bank, Width) {
+                            if (Arg::isEarlyDef(role))
+                                nextRegs.add(reg);
+                        });
+                    if (next->kind.opcode == Patch)
+                        nextRegs.merge(next->extraEarlyClobberedRegs());
+                    if (!nextRegs.isEmpty())
+                        m_clobbers.append(Clobber(indexOfHead + instIndex * 2, nextRegs));
+                }
+            };
+            
+            record(block->size());
+            for (unsigned instIndex = block->size(); instIndex--;) {
+                localCalc.execute(instIndex);
+                record(instIndex);
+            }
+        }
+        
+        std::sort(
+            m_clobbers.begin(), m_clobbers.end(),
+            [] (Clobber& a, Clobber& b) -> bool {
+                return a.index < b.index;
+            });
+        
+        if (verbose()) {
+            dataLog("Intervals:\n");
+            for (unsigned tmpIndex = 0; tmpIndex < m_code.numTmps(bank); ++tmpIndex) {
+                Tmp tmp = Tmp::tmpForIndex(bank, tmpIndex);
+                dataLog("    ", tmp, ": ", m_map[tmp], "\n");
+            }
+        }
+    }
+    
+    bool shouldSpillEverything()
+    {
+        if (!Options::airLinearScanSpillsEverything())
+            return false;
+        
+        // You're meant to hack this so that you selectively spill everything depending on reasons.
+        // That's super useful for debugging.
+
+        return true;
+    }
+    
+    void spillEverything()
+    {
+        for (unsigned tmpIndex = 0; tmpIndex < m_code.numTmps(bank); ++tmpIndex)
+            spill(Tmp::tmpForIndex(bank, tmpIndex));
+    }
+    
+    void prepareIntervals()
+    {
+        m_tmps.resize(0);
+        
+        for (unsigned tmpIndex = 0; tmpIndex < m_code.numTmps(bank); ++tmpIndex) {
+            Tmp tmp = Tmp::tmpForIndex(bank, tmpIndex);
+            TmpData& data = m_map[tmp];
+            if (data.spilled)
+                continue;
+            
+            data.assigned = Reg();
+            m_tmps.append(tmp);
+        }
+        
+        std::sort(
+            m_tmps.begin(), m_tmps.end(),
+            [&] (Tmp& a, Tmp& b) {
+                return m_map[a].interval.begin() < m_map[b].interval.begin();
+            });
+        
+        if (verbose()) {
+            dataLog("Tmps: ", listDump(m_tmps), "\n");
+            dataLog("Clobbers: ", listDump(m_clobbers), "\n");
+        }
+    }
+    
+    Tmp addSpillTmpWithInterval(Interval interval)
+    {
+        TmpData data;
+        data.interval = interval;
+        data.isUnspillable = true;
+        
+        Tmp tmp = m_code.newTmp(bank);
+        m_map.append(tmp, data);
+        return tmp;
+    }
+    
+    void attemptScan()
+    {
+        // This is modeled after LinearScanRegisterAllocation in Fig. 1 in
+        // http://dl.acm.org/citation.cfm?id=330250.
+
+        m_didSpill = false;
+        m_active.clear();
+        m_activeRegs = RegisterSet();
+        
+        size_t clobberIndex = 0;
+        for (Tmp& tmp : m_tmps) {
+            TmpData& entry = m_map[tmp];
+            size_t index = entry.interval.begin();
+            
+            if (verbose()) {
+                dataLog("Index #", index, ": ", tmp, "\n");
+                dataLog("  ", tmp, ": ", entry, "\n");
+                dataLog("  clobberIndex = ", clobberIndex, "\n");
+                // This could be so much faster.
+                BasicBlock* block = m_code[0];
+                for (BasicBlock* candidateBlock : m_code) {
+                    if (m_startIndex[candidateBlock] > index)
+                        break;
+                    block = candidateBlock;
+                }
+                unsigned instIndex = (index - m_startIndex[block] + 1) / 2;
+                dataLog("  At: ", pointerDump(block), ", instIndex = ", instIndex, "\n");
+                dataLog("    Prev: ", pointerDump(block->get(instIndex - 1)), "\n");
+                dataLog("    Next: ", pointerDump(block->get(instIndex)), "\n");
+                dataLog("  Active:\n");
+                for (Tmp tmp : m_active)
+                    dataLog("    ", tmp, ": ", m_map[tmp], "\n");
+            }
+            
+            // This is ExpireOldIntervals in Fig. 1.
+            while (!m_active.isEmpty()) {
+                Tmp tmp = m_active.first();
+                TmpData& entry = m_map[tmp];
+                
+                bool expired = entry.interval.end() <= index;
+                
+                if (!expired)
+                    break;
+                
+                m_active.removeFirst();
+                m_activeRegs.remove(entry.assigned);
+            }
+
+            // If necessary, compute the set of registers that this tmp could even use. This is not
+            // part of Fig. 1, but it's a technique that the authors claim to have implemented in one of
+            // their two implementations. There may be other more efficient ways to do this, but this
+            // implementation gets some perf wins from piggy-backing this calculation in the scan.
+            //
+            // Note that the didBuild flag sticks through spilling. Spilling doesn't change the
+            // interference situation.
+            //
+            // Note that we could short-circuit this if we're dealing with a spillable tmp, there are no
+            // free registers, and this register's interval ends after the one on the top of the active
+            // stack.
+            if (!entry.didBuildPossibleRegs) {
+                // Advance the clobber index until it's at a clobber that is relevant to us.
+                while (clobberIndex < m_clobbers.size() && m_clobbers[clobberIndex].index < index)
+                    clobberIndex++;
+                
+                RegisterSet possibleRegs = m_registerSet;
+                for (size_t i = clobberIndex; i < m_clobbers.size() && m_clobbers[i].index < entry.interval.end(); ++i)
+                    possibleRegs.exclude(m_clobbers[i].regs);
+                
+                entry.possibleRegs = possibleRegs;
+                entry.didBuildPossibleRegs = true;
+            }
+            
+            if (verbose())
+                dataLog("  Possible regs: ", entry.possibleRegs, "\n");
+            
+            // Find a free register that we are allowed to use.
+            if (m_active.size() != m_registers.size()) {
+                bool didAssign = false;
+                for (Reg reg : m_registers) {
+                    // FIXME: Could do priority coloring here.
+                    // https://bugs.webkit.org/show_bug.cgi?id=170304
+                    if (!m_activeRegs.contains(reg) && entry.possibleRegs.contains(reg)) {
+                        assign(tmp, reg);
+                        didAssign = true;
+                        break;
+                    }
+                }
+                if (didAssign)
+                    continue;
+            }
+            
+            // This is SpillAtInterval in Fig. 1, but modified to handle clobbers.
+            Tmp spillTmp = m_active.takeLast(
+                [&] (Tmp spillCandidate) -> bool {
+                    return entry.possibleRegs.contains(m_map[spillCandidate].assigned);
+                });
+            if (!spillTmp) {
+                spill(tmp);
+                continue;
+            }
+            TmpData& spillEntry = m_map[spillTmp];
+            RELEASE_ASSERT(spillEntry.assigned);
+            if (spillEntry.isUnspillable ||
+                (!entry.isUnspillable && spillEntry.interval.end() <= entry.interval.end())) {
+                spill(tmp);
+                addToActive(spillTmp);
+                continue;
+            }
+            
+            assign(tmp, spillEntry.assigned);
+            spill(spillTmp);
+        }
+    }
+    
+    void addToActive(Tmp tmp)
+    {
+        if (m_map[tmp].isUnspillable) {
+            m_active.prepend(tmp);
+            return;
+        }
+        
+        m_active.appendAndBubble(
+            tmp,
+            [&] (Tmp otherTmp) -> bool {
+                TmpData& otherEntry = m_map[otherTmp];
+                if (otherEntry.isUnspillable)
+                    return false;
+                return m_map[otherTmp].interval.end() > m_map[tmp].interval.end();
+            });
+    }
+    
+    void assign(Tmp tmp, Reg reg)
+    {
+        TmpData& entry = m_map[tmp];
+        RELEASE_ASSERT(!entry.spilled);
+        entry.assigned = reg;
+        m_activeRegs.add(reg);
+        addToActive(tmp);
+    }
+    
+    void spill(Tmp tmp)
+    {
+        TmpData& entry = m_map[tmp];
+        RELEASE_ASSERT(!entry.isUnspillable);
+        entry.spilled = m_code.addStackSlot(8, StackSlotKind::Spill);
+        entry.assigned = Reg();
+        m_didSpill = true;
+    }
+    
+    void emitSpillCode()
+    {
+        for (BasicBlock* block : m_code) {
+            size_t indexOfHead = this->indexOfHead(block);
+            for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+                Inst& inst = block->at(instIndex);
+                unsigned indexOfEarly = indexOfHead + instIndex * 2;
+                
+                // First try to spill directly.
+                for (unsigned i = 0; i < inst.args.size(); ++i) {
+                    Arg& arg = inst.args[i];
+                    if (!arg.isTmp())
+                        continue;
+                    if (arg.isReg())
+                        continue;
+                    if (arg.bank() != bank)
+                        continue;
+                    StackSlot* spilled = m_map[arg.tmp()].spilled;
+                    if (!spilled)
+                        continue;
+                    if (!inst.admitsStack(i))
+                        continue;
+                    arg = Arg::stack(spilled);
+                }
+                
+                // Fall back on the hard way.
+                inst.forEachTmp(
+                    [&] (Tmp& tmp, Arg::Role role, Bank tmpBank, Width) {
+                        if (tmp.isReg())
+                            return;
+                        if (tmpBank != bank)
+                            return;
+                        StackSlot* spilled = m_map[tmp].spilled;
+                        if (!spilled)
+                            return;
+                        Opcode move = bank == GP ? Move : MoveDouble;
+                        tmp = addSpillTmpWithInterval(interval(indexOfEarly, Arg::timing(role)));
+                        if (role == Arg::Scratch)
+                            return;
+                        if (Arg::isAnyUse(role))
+                            m_insertionSets[block].insert(instIndex, secondPhase, move, inst.origin, Arg::stack(spilled), tmp);
+                        if (Arg::isAnyDef(role))
+                            m_insertionSets[block].insert(instIndex + 1, firstPhase, move, inst.origin, tmp, Arg::stack(spilled));
+                    });
+            }
+        }
+    }
+    
+    void insertSpillCode()
+    {
+        for (BasicBlock* block : m_code)
+            m_insertionSets[block].execute(block);
+    }
+    
+    void assignRegisters()
+    {
+        if (verbose()) {
+            dataLog("About to allocate registers. State of all tmps:\n");
+            for (unsigned tmpIndex = 0; tmpIndex < m_code.numTmps(bank); ++tmpIndex) {
+                Tmp tmp = Tmp::tmpForIndex(bank, tmpIndex);
+                dataLog("    ", tmp, ": ", m_map[tmp], "\n");
+            }
+            dataLog("IR:\n");
+            dataLog(m_code);
+        }
+        
+        for (BasicBlock* block : m_code) {
+            for (Inst& inst : *block) {
+                if (verbose())
+                    dataLog("At: ", inst, "\n");
+                inst.forEachTmpFast(
+                    [&] (Tmp& tmp) {
+                        if (tmp.isReg())
+                            return;
+                        if (tmp.bank() != bank)
+                            return;
+                        
+                        Reg reg = m_map[tmp].assigned;
+                        if (!reg) {
+                            dataLog("Failed to allocate reg for: ", tmp, "\n");
+                            RELEASE_ASSERT_NOT_REACHED();
+                        }
+                        tmp = Tmp(reg);
+                    });
+            }
+        }
+    }
+    
+    Code& m_code;
+    Vector<Reg> m_registers;
+    RegisterSet m_registerSet;
+    IndexMap<BasicBlock*, size_t> m_startIndex;
+    IndexMap<Tmp::Indexed<bank>, TmpData> m_map;
+    IndexMap<BasicBlock*, PhaseInsertionSet> m_insertionSets;
+    Vector<Clobber> m_clobbers; // After we allocate this, we happily point pointers into it.
+    Vector<Tmp> m_tmps;
+    Deque<Tmp> m_active;
+    RegisterSet m_activeRegs;
+    bool m_didSpill { false };
+};
+
+template<Bank bank>
+void runLinearScan(Code& code)
+{
+    if (verbose())
+        dataLog("Air before linear scan for ", bank, ":\n", code);
+    LinearScan<bank> linearScan(code);
+    linearScan.run();
+    if (verbose())
+        dataLog("Air after linear scan for ", bank, ":\n", code);
+}
+
+} // anonymous namespace
+
+void allocateRegistersByLinearScan(Code& code)
+{
+    PhaseScope phaseScope(code, "allocateRegistersByLinearScan");
+    padInterference(code);
+    runLinearScan<FP>(code);
+    runLinearScan<GP>(code);
+    fixSpillsAfterTerminals(code);
+}
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
diff --git a/Source/JavaScriptCore/b3/air/AirAllocateRegistersByLinearScan.h b/Source/JavaScriptCore/b3/air/AirAllocateRegistersByLinearScan.h
new file mode 100644 (file)
index 0000000..96a63e6
--- /dev/null
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "CPU.h"
+#include "Options.h"
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// This implements the Poletto and Sarkar register allocator called "linear scan":
+// http://dl.acm.org/citation.cfm?id=330250
+//
+// This is not Air's primary register allocator. We use it only when running at optLevel<2. That's not
+// the default level. This register allocator is optimized primarily for running quickly. It's expected
+// that improvements to this register allocator should focus on improving its execution time without much
+// regard for the quality of generated code. If you want good code, use graph coloring.
+//
+// For Air's primary register allocator, see AirAllocateRegistersByGraphColoring.h|cpp.
+void allocateRegistersByLinearScan(Code&);
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
index e19e640..169c7de 100644 (file)
@@ -161,7 +161,7 @@ void allocateStack(Code& code)
 
     // Now we handle the spill slots.
     StackSlotLiveness liveness(code);
-    IndexMap<StackSlot, HashSet<StackSlot*>> interference(code.stackSlots().size());
+    IndexMap<StackSlot*, HashSet<StackSlot*>> interference(code.stackSlots().size());
     Vector<StackSlot*> slots;
 
     // We will perform some spill coalescing. To make that effective, we need to be able to identify
@@ -309,7 +309,7 @@ void allocateStack(Code& code)
             return a.frequency > b.frequency;
         });
     
-    IndexMap<StackSlot, StackSlot*> remappedStackSlots(code.stackSlots().size());
+    IndexMap<StackSlot*, StackSlot*> remappedStackSlots(code.stackSlots().size());
     auto remap = [&] (StackSlot* slot) -> StackSlot* {
         if (!slot)
             return nullptr;
index 259d37b..5889cbf 100644 (file)
@@ -282,6 +282,37 @@ void printInternal(PrintStream& out, Arg::Temperature temperature)
     RELEASE_ASSERT_NOT_REACHED();
 }
 
+void printInternal(PrintStream& out, Arg::Phase phase)
+{
+    switch (phase) {
+    case Arg::Early:
+        out.print("Early");
+        return;
+    case Arg::Late:
+        out.print("Late");
+        return;
+    }
+
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+void printInternal(PrintStream& out, Arg::Timing timing)
+{
+    switch (timing) {
+    case Arg::OnlyEarly:
+        out.print("OnlyEarly");
+        return;
+    case Arg::OnlyLate:
+        out.print("OnlyLate");
+        return;
+    case Arg::EarlyAndLate:
+        out.print("EarlyAndLate");
+        return;
+    }
+
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
 void printInternal(PrintStream& out, Arg::Role role)
 {
     switch (role) {
index 7dd41ea..b1b7479 100644 (file)
@@ -92,6 +92,17 @@ public:
         Cold,
         Warm
     };
+    
+    enum Phase : int8_t {
+        Early,
+        Late
+    };
+    
+    enum Timing : int8_t {
+        OnlyEarly,
+        OnlyLate,
+        EarlyAndLate
+    };
 
     enum Role : int8_t {
         // Use means that the Inst will read from this value before doing anything else.
@@ -253,7 +264,82 @@ public:
     {
         return isColdUse(role) ? Cold : Warm;
     }
-
+    
+    static bool activeAt(Role role, Phase phase)
+    {
+        switch (role) {
+        case Use:
+        case ColdUse:
+        case EarlyDef:
+        case EarlyZDef:
+        case UseAddr:
+            return phase == Early;
+        case LateUse:
+        case LateColdUse:
+        case Def:
+        case ZDef:
+            return phase == Late;
+        case UseDef:
+        case UseZDef:
+        case Scratch:
+            return true;
+        }
+        ASSERT_NOT_REACHED();
+    }
+    
+    static bool activeAt(Timing timing, Phase phase)
+    {
+        switch (timing) {
+        case OnlyEarly:
+            return phase == Early;
+        case OnlyLate:
+            return phase == Late;
+        case EarlyAndLate:
+            return true;
+        }
+        ASSERT_NOT_REACHED();
+    }
+    
+    static Timing timing(Role role)
+    {
+        switch (role) {
+        case Use:
+        case ColdUse:
+        case EarlyDef:
+        case EarlyZDef:
+        case UseAddr:
+            return OnlyEarly;
+        case LateUse:
+        case LateColdUse:
+        case Def:
+        case ZDef:
+            return OnlyLate;
+        case UseDef:
+        case UseZDef:
+        case Scratch:
+            return EarlyAndLate;
+        }
+        ASSERT_NOT_REACHED();
+    }
+    
+    template<typename Func>
+    static void forEachPhase(Timing timing, const Func& func)
+    {
+        if (activeAt(timing, Early))
+            func(Early);
+        if (activeAt(timing, Late))
+            func(Late);
+    }
+    
+    template<typename Func>
+    static void forEachPhase(Role role, const Func& func)
+    {
+        if (activeAt(role, Early))
+            func(Early);
+        if (activeAt(role, Late))
+            func(Late);
+    }
+    
     // Returns true if the Role implies that the Inst will Use the Arg before doing anything else.
     static bool isEarlyUse(Role role)
     {
@@ -1354,6 +1440,8 @@ namespace WTF {
 
 JS_EXPORT_PRIVATE void printInternal(PrintStream&, JSC::B3::Air::Arg::Kind);
 JS_EXPORT_PRIVATE void printInternal(PrintStream&, JSC::B3::Air::Arg::Temperature);
+JS_EXPORT_PRIVATE void printInternal(PrintStream&, JSC::B3::Air::Arg::Phase);
+JS_EXPORT_PRIVATE void printInternal(PrintStream&, JSC::B3::Air::Arg::Timing);
 JS_EXPORT_PRIVATE void printInternal(PrintStream&, JSC::B3::Air::Arg::Role);
 JS_EXPORT_PRIVATE void printInternal(PrintStream&, JSC::B3::Air::Arg::Signedness);
 
index 7ae4097..379c635 100644 (file)
@@ -42,6 +42,7 @@ namespace Air {
 class BlockInsertionSet;
 class Code;
 class InsertionSet;
+class PhaseInsertionSet;
 
 class BasicBlock {
     WTF_MAKE_NONCOPYABLE(BasicBlock);
@@ -140,6 +141,7 @@ private:
     friend class BlockInsertionSet;
     friend class Code;
     friend class InsertionSet;
+    friend class PhaseInsertionSet;
     template<typename> friend class B3::GenericBlockInsertionSet;
     
     BasicBlock(unsigned index, double frequency);
index ba231a9..f192935 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -32,7 +32,7 @@
 
 namespace JSC { namespace B3 { namespace Air {
 
-typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> BlockWorklist;
+typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> BlockWorklist;
 
 // When you say BlockWith<int> you should read it as "block with an int".
 template<typename T> using BlockWith = GraphNodeWith<BasicBlock*, T>;
@@ -41,11 +41,11 @@ template<typename T> using BlockWith = GraphNodeWith<BasicBlock*, T>;
 // permits forcibly enqueueing things even if the block has already been seen. It's useful for
 // things like building a spanning tree, in which case T (the auxiliary payload) would be the
 // successor index.
-template<typename T> using ExtendedBlockWorklist = ExtendedGraphNodeWorklist<BasicBlock*, T, IndexSet<BasicBlock>>;
+template<typename T> using ExtendedBlockWorklist = ExtendedGraphNodeWorklist<BasicBlock*, T, IndexSet<BasicBlock*>>;
 
 typedef GraphNodeWithOrder<BasicBlock*> BlockWithOrder;
 
-typedef PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> PostOrderBlockWorklist;
+typedef PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> PostOrderBlockWorklist;
 
 } } } // namespace JSC::B3::Air
 
index 8f57afc..2e45adb 100644 (file)
@@ -39,8 +39,8 @@ class CFG {
     WTF_MAKE_FAST_ALLOCATED;
 public:
     typedef BasicBlock* Node;
-    typedef IndexSet<BasicBlock> Set;
-    template<typename T> using Map = IndexMap<BasicBlock, T>;
+    typedef IndexSet<BasicBlock*> Set;
+    template<typename T> using Map = IndexMap<BasicBlock*, T>;
     typedef Vector<BasicBlock*, 4> List;
 
     CFG(Code& code)
@@ -51,7 +51,7 @@ public:
     Node root() { return m_code[0]; }
 
     template<typename T>
-    Map<T> newMap() { return IndexMap<JSC::B3::Air::BasicBlock, T>(m_code.size()); }
+    Map<T> newMap() { return IndexMap<JSC::B3::Air::BasicBlock*, T>(m_code.size()); }
 
     SuccessorCollection<BasicBlock, BasicBlock::SuccessorList> successors(Node node) { return node->successorBlocks(); }
     BasicBlock::PredecessorList& predecessors(Node node) { return node->predecessors(); }
index ccc3c8d..acf5018 100644 (file)
@@ -40,7 +40,7 @@ bool eliminateDeadCode(Code& code)
     PhaseScope phaseScope(code, "eliminateDeadCode");
 
     HashSet<Tmp> liveTmps;
-    IndexSet<StackSlot> liveStackSlots;
+    IndexSet<StackSlot*> liveStackSlots;
     bool changed;
 
     auto isArgLive = [&] (const Arg& arg) -> bool {
index d7a40f7..d795931 100644 (file)
@@ -547,7 +547,7 @@ private:
     };
 
     Code& m_code;
-    IndexMap<BasicBlock, State> m_atHead;
+    IndexMap<BasicBlock*, State> m_atHead;
     State m_state;
     BasicBlock* m_block { nullptr };
     unsigned m_instIndex { 0 };
index ae4bd28..037c40f 100644 (file)
@@ -155,10 +155,10 @@ void fixPartialRegisterStalls(Code& code)
 
     // For each block, this provides the distance to the last instruction setting each register
     // on block *entry*.
-    IndexMap<BasicBlock, FPDefDistance> lastDefDistance(code.size());
+    IndexMap<BasicBlock*, FPDefDistance> lastDefDistance(code.size());
 
     // Blocks with dirty distance at head.
-    IndexSet<BasicBlock> dirty;
+    IndexSet<BasicBlock*> dirty;
 
     // First, we compute the local distance for each block and push it to the successors.
     for (BasicBlock* block : code) {
diff --git a/Source/JavaScriptCore/b3/air/AirFixSpillsAfterTerminals.cpp b/Source/JavaScriptCore/b3/air/AirFixSpillsAfterTerminals.cpp
new file mode 100644 (file)
index 0000000..8ee3a67
--- /dev/null
@@ -0,0 +1,99 @@
+/*
+ * Copyright (C) 2017 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 "AirFixSpillsAfterTerminals.h"
+
+#if ENABLE(B3_JIT)
+
+#include "AirBlockInsertionSet.h"
+#include "AirCode.h"
+#include "AirInsertionSet.h"
+#include "AirInstInlines.h"
+#include "AirTmpInlines.h"
+
+namespace JSC { namespace B3 { namespace Air {
+
+void fixSpillsAfterTerminals(Code& code)
+{
+    // Because there may be terminals that produce values, IRC may
+    // want to spill those terminals. It'll happen to spill it after
+    // the terminal. If we left the graph in this state, it'd be invalid
+    // because a terminal must be the last instruction in a block.
+    // We fix that here.
+
+    BlockInsertionSet blockInsertionSet(code);
+    InsertionSet insertionSet(code);
+
+    for (BasicBlock* block : code) {
+        unsigned terminalIndex = block->size();
+        bool foundTerminal = false;
+        while (terminalIndex--) {
+            if (block->at(terminalIndex).isTerminal()) {
+                foundTerminal = true;
+                break;
+            }
+        }
+        ASSERT_UNUSED(foundTerminal, foundTerminal);
+
+        if (terminalIndex == block->size() - 1)
+            continue;
+
+        // There must be instructions after the terminal because it's not the last instruction.
+        ASSERT(terminalIndex < block->size() - 1);
+        Vector<Inst, 1> instsToMove;
+        for (unsigned i = terminalIndex + 1; i < block->size(); i++)
+            instsToMove.append(block->at(i));
+        RELEASE_ASSERT(instsToMove.size());
+
+        for (FrequentedBlock& frequentedSuccessor : block->successors()) {
+            BasicBlock* successor = frequentedSuccessor.block();
+            // If successor's only predecessor is block, we can plant the spill inside
+            // the successor. Otherwise, we must split the critical edge and create
+            // a new block for the spill.
+            if (successor->numPredecessors() == 1) {
+                insertionSet.insertInsts(0, instsToMove);
+                insertionSet.execute(successor);
+            } else {
+                BasicBlock* newBlock = blockInsertionSet.insertBefore(successor, successor->frequency());
+                for (const Inst& inst : instsToMove)
+                    newBlock->appendInst(inst);
+                newBlock->appendInst(Inst(Jump, instsToMove.last().origin));
+                newBlock->successors().append(successor);
+                frequentedSuccessor.block() = newBlock;
+            }
+        }
+
+        block->resize(terminalIndex + 1);
+    }
+
+    if (blockInsertionSet.execute())
+        code.resetReachability();
+}
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/air/AirFixSpillsAfterTerminals.h b/Source/JavaScriptCore/b3/air/AirFixSpillsAfterTerminals.h
new file mode 100644 (file)
index 0000000..1a5fc52
--- /dev/null
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// Because there may be terminals that produce values, the register allocator may
+// want to spill those terminals. It'll happen to spill it after
+// the terminal. If we left the graph in this state, it'd be invalid
+// because a terminal must be the last instruction in a block.
+// We fix that here.
+void fixSpillsAfterTerminals(Code&);
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
index 9b57012..4420e64 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(B3_JIT)
 
 #include "AirAllocateRegistersByGraphColoring.h"
+#include "AirAllocateRegistersByLinearScan.h"
 #include "AirAllocateStack.h"
 #include "AirCode.h"
 #include "AirEliminateDeadCode.h"
@@ -57,7 +58,7 @@
 
 namespace JSC { namespace B3 { namespace Air {
 
-void prepareForGeneration(Code& code)
+void prepareForGeneration(Code& code, unsigned optLevel)
 {
     TimingScope timingScope("Air::prepareForGeneration");
     
@@ -89,18 +90,22 @@ void prepareForGeneration(Code& code)
     // For debugging, you can use spillEverything() to put everything to the stack between each Inst.
     if (Options::airSpillsEverything())
         spillEverything(code);
-    else
+    else if (optLevel >= 2)
         allocateRegistersByGraphColoring(code);
+    else
+        allocateRegistersByLinearScan(code);
 
     if (Options::logAirRegisterPressure()) {
         dataLog("Register pressure after register allocation:\n");
         logRegisterPressure(code);
     }
-
-    // This replaces uses of spill slots with registers or constants if possible. It does this by
-    // minimizing the amount that we perturb the already-chosen register allocation. It may extend
-    // the live ranges of registers though.
-    fixObviousSpills(code);
+    
+    if (optLevel >= 2) {
+        // This replaces uses of spill slots with registers or constants if possible. It does this by
+        // minimizing the amount that we perturb the already-chosen register allocation. It may extend
+        // the live ranges of registers though.
+        fixObviousSpills(code);
+    }
 
     lowerAfterRegAlloc(code);
 
@@ -165,7 +170,7 @@ void generate(Code& code, CCallHelpers& jit)
         if (block)
             context.blockLabels[block] = Box<CCallHelpers::Label>::create();
     }
-    IndexMap<BasicBlock, CCallHelpers::JumpList> blockJumps(code.size());
+    IndexMap<BasicBlock*, CCallHelpers::JumpList> blockJumps(code.size());
 
     auto link = [&] (CCallHelpers::Jump jump, BasicBlock* target) {
         if (context.blockLabels[target]->isSet()) {
index 60839be..73b722b 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -27,6 +27,8 @@
 
 #if ENABLE(B3_JIT)
 
+#include "B3Common.h"
+
 namespace JSC {
 
 class CCallHelpers;
@@ -37,7 +39,7 @@ class Code;
 
 // This takes an Air::Code that hasn't had any stack allocation and optionally hasn't had any
 // register allocation and does both of those things.
-JS_EXPORT_PRIVATE void prepareForGeneration(Code&);
+JS_EXPORT_PRIVATE void prepareForGeneration(Code&, unsigned optLevel = defaultOptLevel());
 
 // This generates the code using the given CCallHelpers instance. Note that this may call callbacks
 // in the supplied code as it is generating.
index f48b5bb..62fea03 100644 (file)
@@ -48,7 +48,7 @@ public:
     typedef SharedTask<LatePathFunction> LatePath;
 
     Vector<RefPtr<LatePath>> latePaths;
-    IndexMap<BasicBlock, Box<CCallHelpers::Label>> blockLabels;
+    IndexMap<BasicBlock*, Box<CCallHelpers::Label>> blockLabels;
     BasicBlock* currentBlock { nullptr };
     unsigned indexInBlock { UINT_MAX };
     Code* code { nullptr };
index 44047b6..2f25fbc 100644 (file)
@@ -59,7 +59,7 @@ public:
         appendInsertion(Insertion(index, std::forward<Inst>(inst)));
     }
 
-    template <typename InstVector>
+    template<typename InstVector>
     void insertInsts(size_t index, const InstVector& insts)
     {
         for (const Inst& inst : insts)
index 951117c..5666dab 100644 (file)
@@ -60,7 +60,8 @@ bool Inst::hasLateUseOrDef()
 
 bool Inst::needsPadding(Inst* prevInst, Inst* nextInst)
 {
-    return prevInst && nextInst && prevInst->hasLateUseOrDef() && nextInst->hasEarlyDef();
+    bool result = prevInst && nextInst && prevInst->hasLateUseOrDef() && nextInst->hasEarlyDef();
+    return result;
 }
 
 bool Inst::hasArgEffects()
index 3ba4b7f..bf7b522 100644 (file)
@@ -55,6 +55,14 @@ void lowerAfterRegAlloc(Code& code)
 
     if (verbose)
         dataLog("Code before lowerAfterRegAlloc:\n", code);
+    
+    // FIXME:
+    // 1) This should bail early if there are no Shuffles or ColdCCalls.
+    //    https://bugs.webkit.org/show_bug.cgi?id=170305
+    // 2) We should not introduce Shuffles for normal calls.
+    //    https://bugs.webkit.org/show_bug.cgi?id=170306
+    // 3) We should emit ColdCCall only at optLevel==1.
+    //    https://bugs.webkit.org/show_bug.cgi?id=170307
 
     HashMap<Inst*, RegisterSet> usedRegisters;
 
index e14641d..b5507c3 100644 (file)
@@ -82,7 +82,7 @@ void lowerEntrySwitch(Code& code)
     // Now duplicate them.
     Vector<FrequentedBlock> entrypoints;
     entrypoints.append(FrequentedBlock(code[0], entrypointFrequencies[0]));
-    IndexMap<BasicBlock, BasicBlock*> map(code.size());
+    IndexMap<BasicBlock*, BasicBlock*> map(code.size());
     for (unsigned entrypointIndex = 1; entrypointIndex < code.proc().numEntrypoints(); ++entrypointIndex) {
         map.clear();
         for (BasicBlock* block : worklist.seen().values(code))
index 714b819..595b6f9 100644 (file)
@@ -649,7 +649,7 @@ Move32 U:G:32, ZD:G:32
 Move32 U:G:32, ZD:G:32, S:G:32
     Addr, Addr, Tmp
 
-StoreZero32 U:G:32
+StoreZero32 D:G:32
     Addr
     Index
 
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  */
 
 #include "config.h"
-#include "B3HeapRange.h"
+#include "AirPhaseInsertionSet.h"
 
 #if ENABLE(B3_JIT)
 
-namespace JSC { namespace B3 {
+#include "AirBasicBlock.h"
+#include <wtf/BubbleSort.h>
 
-void HeapRange::dump(PrintStream& out) const
+namespace JSC { namespace B3 { namespace Air {
+
+void PhaseInsertionSet::execute(BasicBlock* block)
 {
-    if (*this == HeapRange()) {
-        out.print("Bottom");
-        return;
-    }
-    if (*this == top()) {
-        out.print("Top");
-        return;
-    }
-    out.print(m_begin, "...", m_end);
+    bubbleSort(m_insertions.begin(), m_insertions.end());
+    executeInsertions(block->m_insts, m_insertions);
 }
 
-} } // namespace JSC::B3
+} } } // namespace JSC::B3::Air
 
 #endif // ENABLE(B3_JIT)
 
diff --git a/Source/JavaScriptCore/b3/air/AirPhaseInsertionSet.h b/Source/JavaScriptCore/b3/air/AirPhaseInsertionSet.h
new file mode 100644 (file)
index 0000000..ced2299
--- /dev/null
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2017 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. 
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "AirInsertionSet.h"
+#include <wtf/Insertion.h>
+#include <wtf/Vector.h>
+
+namespace JSC { namespace B3 { namespace Air {
+
+class BasicBlock;
+class Code;
+
+// Phased insertions allow you to ascribe phases to the things inserted at an instruction boundary.
+class PhaseInsertion : public Insertion {
+public:
+    PhaseInsertion() { }
+    
+    template<typename T>
+    PhaseInsertion(size_t index, unsigned phase, T&& element)
+        : Insertion(index, std::forward<T>(element))
+        , m_phase(phase)
+    {
+    }
+    
+    unsigned phase() const { return m_phase; }
+    
+    bool operator<(const PhaseInsertion& other) const
+    {
+        if (index() != other.index())
+            return index() < other.index();
+        return m_phase < other.m_phase;
+    }
+
+private:
+    unsigned m_phase { 0 };
+};
+
+class PhaseInsertionSet {
+public:
+    PhaseInsertionSet()
+    {
+    }
+    
+    template<typename T>
+    void appendInsertion(T&& insertion)
+    {
+        m_insertions.append(std::forward<T>(insertion));
+    }
+    
+    template<typename Inst>
+    void insertInst(size_t index, unsigned phase, Inst&& inst)
+    {
+        appendInsertion(PhaseInsertion(index, phase, std::forward<Inst>(inst)));
+    }
+    
+    template<typename... Arguments>
+    void insert(size_t index, unsigned phase, Arguments&&... arguments)
+    {
+        insertInst(index, phase, Inst(std::forward<Arguments>(arguments)...));
+    }
+    
+    void execute(BasicBlock*);
+
+private:
+    Vector<PhaseInsertion, 8> m_insertions;
+};
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
index 0dab1bc..055abc6 100644 (file)
@@ -30,6 +30,7 @@
 #include "AirBasicBlock.h"
 #include "AirCode.h"
 #include "AirInst.h"
+#include "AirLiveness.h"
 #include "RegisterSet.h"
 
 namespace JSC { namespace B3 { namespace Air {
@@ -54,6 +55,19 @@ public:
         {
         }
         
+        // If you computed Tmp liveness for some bank, you can use reg liveness to fill in the blanks.
+        // Note that what happens to the registers not belonging to the bank is arbitrary - they may get
+        // set or not.
+        template<Bank bank>
+        LocalCalc(TmpLiveness<bank>& liveness, BasicBlock* block)
+            : m_block(block)
+        {
+            for (Tmp tmp : liveness.liveAtTail(block)) {
+                if (tmp.isReg())
+                    m_workset.set(tmp.reg());
+            }
+        }
+        
         const RegisterSet& live() const
         {
             return m_workset;
@@ -84,8 +98,8 @@ public:
     }
     
 private:
-    IndexMap<BasicBlock, RegisterSet> m_liveAtHead;
-    IndexMap<BasicBlock, RegisterSet> m_liveAtTail;
+    IndexMap<BasicBlock*, RegisterSet> m_liveAtHead;
+    IndexMap<BasicBlock*, RegisterSet> m_liveAtTail;
 };
 
 } } } // namespace JSC::B3::Air
index 6dc6545..7e9af7b 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "AirArgInlines.h"
 #include "AirCode.h"
+#include "AirFixSpillsAfterTerminals.h"
 #include "AirInsertionSet.h"
 #include "AirInstInlines.h"
 #include "AirLiveness.h"
@@ -46,7 +47,7 @@ void spillEverything(Code& code)
     padInterference(code);
 
     // We want to know the set of registers used at every point in every basic block.
-    IndexMap<BasicBlock, Vector<RegisterSet>> usedRegisters(code.size());
+    IndexMap<BasicBlock*, Vector<RegisterSet>> usedRegisters(code.size());
     GPLiveness gpLiveness(code);
     FPLiveness fpLiveness(code);
     for (BasicBlock* block : code) {
@@ -173,10 +174,13 @@ void spillEverything(Code& code)
                     RELEASE_ASSERT(chosenReg);
 
                     tmp = Tmp(chosenReg);
+                    
+                    if (role == Arg::Scratch)
+                        return;
 
                     Opcode move = bank == GP ? Move : MoveDouble;
 
-                    if (Arg::isAnyUse(role) && role != Arg::Scratch)
+                    if (Arg::isAnyUse(role))
                         insertionSet.insert(instIndex, move, inst.origin, arg, tmp);
                     if (Arg::isAnyDef(role))
                         insertionSet.insert(instIndex + 1, move, inst.origin, tmp, arg);
@@ -184,6 +188,8 @@ void spillEverything(Code& code)
         }
         insertionSet.execute(block);
     }
+    
+    fixSpillsAfterTerminals(code);
 }
 
 } } } // namespace JSC::B3::Air
index 487f521..63c6840 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 #if ENABLE(B3_JIT)
 
+#include "AirTmpInlines.h"
+
 namespace JSC { namespace B3 { namespace Air {
 
+template<> const char* const Tmp::Indexed<GP>::dumpPrefix = "%tmp";
+template<> const char* const Tmp::Indexed<FP>::dumpPrefix = "%ftmp";
+template<> const char* const Tmp::AbsolutelyIndexed<GP>::dumpPrefix = "%abs";
+template<> const char* const Tmp::AbsolutelyIndexed<FP>::dumpPrefix = "%fabs";
+
 void Tmp::dump(PrintStream& out) const
 {
     if (!*this) {
index 95b3926..85d9d5f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -74,6 +74,14 @@ public:
         result.m_value = encodeFPTmp(index);
         return result;
     }
+    
+    static Tmp tmpForIndex(Bank bank, unsigned index)
+    {
+        if (bank == GP)
+            return gpTmpForIndex(index);
+        ASSERT(bank == FP);
+        return fpTmpForIndex(index);
+    }
 
     explicit operator bool() const { return !!m_value; }
     
@@ -154,7 +162,16 @@ public:
             return gpTmpIndex();
         return fpTmpIndex();
     }
-
+    
+    template<Bank bank> class Indexed;
+    template<Bank bank> class AbsolutelyIndexed;
+    
+    template<Bank bank>
+    Indexed<bank> indexed() const;
+    
+    template<Bank bank>
+    AbsolutelyIndexed<bank> absolutelyIndexed() const;
+    
     bool isAlive() const
     {
         return !!*this;
@@ -195,6 +212,8 @@ public:
         result.m_value = static_cast<int>(index);
         return result;
     }
+    
+    static Tmp tmpForAbsoluteIndex(Bank, unsigned);
 
 private:
     static int encodeGP(unsigned index)
index c113f14..2e3eab3 100644 (file)
@@ -92,6 +92,58 @@ struct AbsoluteTmpMapper<FP> {
     }
 };
 
+template<Bank theBank>
+class Tmp::Indexed : public Tmp {
+public:
+    static const char* const dumpPrefix;
+    
+    Indexed(Tmp tmp)
+        : Tmp(tmp)
+    {
+    }
+    
+    unsigned index() const
+    {
+        return tmpIndex(theBank);
+    }
+};
+
+template<Bank theBank>
+class Tmp::AbsolutelyIndexed : public Tmp {
+public:
+    static const char* const dumpPrefix;
+
+    AbsolutelyIndexed(Tmp tmp)
+        : Tmp(tmp)
+    {
+    }
+    
+    unsigned index() const
+    {
+        return AbsoluteTmpMapper<theBank>::absoluteIndex(*this);
+    }
+};
+
+template<Bank theBank>
+inline Tmp::Indexed<theBank> Tmp::indexed() const
+{
+    return Indexed<theBank>(*this);
+}
+
+template<Bank theBank>
+inline Tmp::AbsolutelyIndexed<theBank> Tmp::absolutelyIndexed() const
+{
+    return AbsolutelyIndexed<theBank>(*this);
+}
+
+inline Tmp Tmp::tmpForAbsoluteIndex(Bank bank, unsigned index)
+{
+    if (bank == GP)
+        return AbsoluteTmpMapper<GP>::tmpFromAbsoluteIndex(index);
+    ASSERT(bank == FP);
+    return AbsoluteTmpMapper<FP>::tmpFromAbsoluteIndex(index);
+}
+
 } } } // namespace JSC::B3::Air
 
 #endif // ENABLE(B3_JIT)
index bd6d8fe..f3ec028 100644 (file)
@@ -117,7 +117,7 @@ StaticLock crashLock;
         CRASH(); \
     } while (false)
 
-std::unique_ptr<Compilation> compileProc(Procedure& procedure, unsigned optLevel = 1)
+std::unique_ptr<Compilation> compileProc(Procedure& procedure, unsigned optLevel = defaultOptLevel())
 {
     return std::make_unique<Compilation>(B3::compile(procedure, optLevel));
 }
@@ -987,6 +987,7 @@ void testMulLoadTwice()
 
     test(0);
     test(1);
+    test(2);
 }
 
 void testMulAddArgsLeft()
index 6849f9d..87fd224 100644 (file)
@@ -102,8 +102,16 @@ public:
     }
     
     // Also allow add/remove/contains terminology, which means the same thing as set/clear/get.
-    void add(Reg reg) { set(reg); }
-    void remove(Reg reg) { clear(reg); }
+    bool add(Reg reg)
+    {
+        ASSERT(!!reg);
+        return !m_bits.testAndSet(reg.index());
+    }
+    bool remove(Reg reg)
+    {
+        ASSERT(!!reg);
+        return m_bits.testAndClear(reg.index());
+    }
     bool contains(Reg reg) const { return get(reg); }
     
     void merge(const RegisterSet& other) { m_bits.merge(other.m_bits); }
index 67b90e3..9941a95 100644 (file)
@@ -225,6 +225,7 @@ typedef const char* optionString;
     v(bool, useFTLJIT, true, Normal, "allows the FTL JIT to be used if true") \
     v(bool, useFTLTBAA, true, Normal, nullptr) \
     v(bool, validateFTLOSRExitLiveness, false, Normal, nullptr) \
+    v(unsigned, defaultB3OptLevel, 2, Normal, nullptr) \
     v(bool, b3AlwaysFailsBeforeCompile, false, Normal, nullptr) \
     v(bool, b3AlwaysFailsBeforeLink, false, Normal, nullptr) \
     v(bool, ftlCrashes, false, Normal, nullptr) /* fool-proof way of checking that you ended up in the FTL. ;-) */\
@@ -398,6 +399,8 @@ typedef const char* optionString;
     v(bool, logB3PhaseTimes, false, Normal, nullptr) \
     v(double, rareBlockPenalty, 0.001, Normal, nullptr) \
     v(bool, airSpillsEverything, false, Normal, nullptr) \
+    v(bool, airLinearScanVerbose, false, Normal, nullptr) \
+    v(bool, airLinearScanSpillsEverything, false, Normal, nullptr) \
     v(bool, airForceBriggsAllocator, false, Normal, nullptr) \
     v(bool, airForceIRCAllocator, false, Normal, nullptr) \
     v(bool, coalesceSpillSlots, true, Normal, nullptr) \
index de56a1c..79c24d8 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -27,6 +27,7 @@
 
 #if ENABLE(WEBASSEMBLY)
 
+#include "B3Common.h"
 #include "B3Compilation.h"
 #include "CCallHelpers.h"
 #include "VM.h"
@@ -48,7 +49,7 @@ struct CompilationContext {
     CCallHelpers::Call jsEntrypointToWasmEntrypointCall;
 };
 
-Expected<std::unique_ptr<WasmInternalFunction>, String> parseAndCompile(VM&, CompilationContext&, const uint8_t*, size_t, const Signature*, Vector<UnlinkedWasmToWasmCall>&, const ModuleInformation&, const Vector<SignatureIndex>&, MemoryMode, unsigned optLevel = 1);
+Expected<std::unique_ptr<WasmInternalFunction>, String> parseAndCompile(VM&, CompilationContext&, const uint8_t*, size_t, const Signature*, Vector<UnlinkedWasmToWasmCall>&, const ModuleInformation&, const Vector<SignatureIndex>&, MemoryMode, unsigned optLevel = B3::defaultOptLevel());
 
 } } // namespace JSC::Wasm
 
index 676109f..b9298ac 100644 (file)
@@ -1,3 +1,46 @@
+2017-03-30  Filip Pizlo  <fpizlo@apple.com>
+
+        Air should support linear scan for optLevel<2
+        https://bugs.webkit.org/show_bug.cgi?id=170161
+
+        Reviewed by Saam Barati.
+        
+        This change introduces a new low-latency register allocator. It can allocate registers very
+        quickly by doing a relatively poor job. Implementing this algorithm required beefing up some of
+        our core algorithms.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/CMakeLists.txt:
+        * wtf/Deque.h: Make it possible to do some basic priority queueing with this data structure.
+        (WTF::inlineCapacity>::removeAllMatching):
+        (WTF::inlineCapacity>::appendAndBubble):
+        (WTF::inlineCapacity>::takeLast):
+        * wtf/IndexKeyType.h: Added. This makes it possible to use IndexMap and IndexSet with value or pointer types. Previously they just worked with pointer types.
+        (WTF::IndexKeyType::index):
+        * wtf/IndexMap.h: Adopt IndexKeyType.
+        (WTF::IndexMap::operator[]):
+        (WTF::IndexMap::append):
+        * wtf/IndexSet.h: Adopt IndexKeyType.
+        (WTF::IndexSet::add):
+        (WTF::IndexSet::addAll):
+        (WTF::IndexSet::remove):
+        (WTF::IndexSet::contains):
+        (WTF::IndexSet::Iterable::iterator::operator*):
+        * wtf/Range.h: Added. This used to be B3::HeapRange. This generalizes that data structure to any kind of range stuff.
+        (WTF::Range::Range):
+        (WTF::Range::top):
+        (WTF::Range::operator==):
+        (WTF::Range::operator!=):
+        (WTF::Range::operator bool):
+        (WTF::Range::operator|):
+        (WTF::Range::operator|=):
+        (WTF::Range::begin):
+        (WTF::Range::end):
+        (WTF::Range::overlaps):
+        (WTF::Range::dump):
+        * wtf/RangeSet.h:
+        (WTF::RangeSet::add):
+
 2017-03-25  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [JSC] Move platformThreadSignal to WTF
index 658c7ab..2725e1b 100644 (file)
@@ -23,6 +23,8 @@
 /* Begin PBXBuildFile section */
                0F0D85B417234CC100338210 /* NoLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F0D85B317234CB100338210 /* NoLock.h */; };
                0F0FCDDE1DD167F900CCAB53 /* LockAlgorithm.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F0FCDDD1DD167F900CCAB53 /* LockAlgorithm.h */; };
+               0F2AC5611E89F70C0001EE3F /* Range.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2AC5601E89F70C0001EE3F /* Range.h */; };
+               0F2AC5631E8A01490001EE3F /* IndexKeyType.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2AC5621E8A01490001EE3F /* IndexKeyType.h */; };
                0F2B66A617B6B4FB00A7AE3F /* DeferrableRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */; };
                0F2B66A717B6B4FD00A7AE3F /* FlipBytes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */; };
                0F30BA901E78708E002CA847 /* GlobalVersion.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F30BA8A1E78708E002CA847 /* GlobalVersion.cpp */; };
 /* Begin PBXFileReference section */
                0F0D85B317234CB100338210 /* NoLock.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = NoLock.h; sourceTree = "<group>"; };
                0F0FCDDD1DD167F900CCAB53 /* LockAlgorithm.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LockAlgorithm.h; sourceTree = "<group>"; };
+               0F2AC5601E89F70C0001EE3F /* Range.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Range.h; sourceTree = "<group>"; };
+               0F2AC5621E8A01490001EE3F /* IndexKeyType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexKeyType.h; sourceTree = "<group>"; };
                0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DeferrableRefCounted.h; sourceTree = "<group>"; };
                0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FlipBytes.h; sourceTree = "<group>"; };
                0F300B7D18AB48B400A6D72E /* HashMethod.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HashMethod.h; sourceTree = "<group>"; };
                                A8A472BA151A825A004123FF /* HashTraits.h */,
                                A8A472BB151A825A004123FF /* HexNumber.h */,
                                FE8925AF1D00DAEC0046907E /* Indenter.h */,
-                               9C67C542589348E285B49699 /* IndexedContainerIterator.h */,
+                               0F2AC5621E8A01490001EE3F /* IndexKeyType.h */,
                                5B43383A5D0B463C9433D933 /* IndexMap.h */,
                                3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */,
                                2684D4351C000D400081D663 /* IndexSparseSet.h */,
+                               9C67C542589348E285B49699 /* IndexedContainerIterator.h */,
                                A8A472BC151A825A004123FF /* InlineASM.h */,
                                A70DA0821799F04D00529A9B /* Insertion.h */,
                                7CDD7FF7186D291E007433CD /* IteratorAdaptors.h */,
                                A8A472FB151A825B004123FF /* RandomNumber.cpp */,
                                A8A472FC151A825B004123FF /* RandomNumber.h */,
                                A8A472FD151A825B004123FF /* RandomNumberSeed.h */,
+                               0F2AC5601E89F70C0001EE3F /* Range.h */,
                                0F725CAB1C50461600AD943A /* RangeSet.h */,
                                0F87105916643F190090B0AD /* RawPointer.h */,
                                0FDE87F61DFD07CC0064C390 /* RecursiveLockAdapter.h */,
                                C916B975F02F4F7E8B4AB12D /* IndexMap.h in Headers */,
                                C8B0E1A1E01A486EB95E0D11 /* IndexSet.h in Headers */,
                                2684D4361C000D400081D663 /* IndexSparseSet.h in Headers */,
+                               0F2AC5631E8A01490001EE3F /* IndexKeyType.h in Headers */,
                                A8A473DC151A825B004123FF /* InlineASM.h in Headers */,
                                A70DA0841799F04D00529A9B /* Insertion.h in Headers */,
                                26147B0A15DDCCDC00DDB907 /* IntegerToStringConversion.h in Headers */,
                                430B47891AAAAC1A001223DA /* StringCommon.h in Headers */,
                                A8A4743E151A825B004123FF /* StringConcatenate.h in Headers */,
                                7CD4C2701E2C82B900929470 /* StringConcatenateNumbers.h in Headers */,
+                               0F2AC5611E89F70C0001EE3F /* Range.h in Headers */,
                                A8A4742C151A825B004123FF /* StringExtras.h in Headers */,
                                A8A4743F151A825B004123FF /* StringHash.h in Headers */,
                                A748745417A0BDAE00FA04CB /* StringHashDumpContext.h in Headers */,
index 856eae9..11f283d 100644 (file)
@@ -100,6 +100,7 @@ set(WTF_HEADERS
     RAMSize.h
     RandomNumber.h
     RandomNumberSeed.h
+    Range.h
     RangeSet.h
     RawPointer.h
     RecursiveLockAdapter.h
index 2205a07..2c95085 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2007, 2008, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2007-2017 Apple Inc. All rights reserved.
  * Copyright (C) 2009 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -89,6 +89,19 @@ public:
     void removeLast();
     void remove(iterator&);
     void remove(const_iterator&);
+    
+    template<typename Func> void removeAllMatching(const Func&);
+    
+    // This is a priority enqueue. The callback is given a value, and if it returns true, then this
+    // will put the appended value before that value. It will keep bubbling until the callback returns
+    // false or the value ends up at the head of the queue.
+    template<typename U, typename Func>
+    void appendAndBubble(U&&, const Func&);
+    
+    // Remove and return the last element for which the callback returns true. Returns a null version of
+    // T if it the callback always returns false.
+    template<typename Func>
+    T takeLast(const Func&);
 
     void clear();
 
@@ -524,6 +537,55 @@ inline void Deque<T, inlineCapacity>::remove(size_t position)
     checkValidity();
 }
 
+template<typename T, size_t inlineCapacity>
+template<typename Func>
+inline void Deque<T, inlineCapacity>::removeAllMatching(const Func& func)
+{
+    size_t count = size();
+    while (count--) {
+        T value = takeFirst();
+        if (!func(value))
+            append(WTFMove(value));
+    }
+}
+
+template<typename T, size_t inlineCapacity>
+template<typename U, typename Func>
+inline void Deque<T, inlineCapacity>::appendAndBubble(U&& value, const Func& func)
+{
+    append(WTFMove(value));
+    iterator begin = this->begin();
+    iterator iter = end();
+    --iter;
+    while (iter != begin) {
+        iterator prev = iter;
+        --prev;
+        if (!func(*prev))
+            return;
+        std::swap(*prev, *iter);
+        iter = prev;
+    }
+}
+
+template<typename T, size_t inlineCapacity>
+template<typename Func>
+inline T Deque<T, inlineCapacity>::takeLast(const Func& func)
+{
+    unsigned count = 0;
+    unsigned size = this->size();
+    while (count < size) {
+        T candidate = takeLast();
+        if (func(candidate)) {
+            while (count--)
+                append(takeFirst());
+            return candidate;
+        }
+        count++;
+        prepend(WTFMove(candidate));
+    }
+    return T();
+}
+
 #ifdef NDEBUG
 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity() const { }
 template<typename T, size_t inlineCapacity> inline void DequeIteratorBase<T, inlineCapacity>::checkValidity(const DequeIteratorBase<T, inlineCapacity>&) const { }
diff --git a/Source/WTF/wtf/IndexKeyType.h b/Source/WTF/wtf/IndexKeyType.h
new file mode 100644 (file)
index 0000000..c5a22eb
--- /dev/null
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2017 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. 
+ */
+
+#pragma once
+
+namespace WTF {
+
+template<typename T>
+struct IndexKeyType {
+    static size_t index(const T& key) { return key.index(); }
+};
+
+template<typename T>
+struct IndexKeyType<T*> {
+    static size_t index(T* key) { return key->index(); }
+};
+
+} // namespace WTF
+
index 164051e..79c223c 100644 (file)
@@ -25,6 +25,7 @@
 
 #pragma once
 
+#include <wtf/IndexKeyType.h>
 #include <wtf/Vector.h>
 
 namespace WTF {
@@ -70,18 +71,24 @@ public:
         return m_vector[index];
     }
     
-    Value& operator[](Key* key)
+    Value& operator[](const Key& key)
     {
-        return m_vector[key->index()];
+        return m_vector[IndexKeyType<Key>::index(key)];
     }
     
-    const Value& operator[](Key* key) const
+    const Value& operator[](const Key& key) const
     {
-        return m_vector[key->index()];
+        return m_vector[IndexKeyType<Key>::index(key)];
+    }
+    
+    void append(const Key& key, Value value)
+    {
+        RELEASE_ASSERT(IndexKeyType<Key>::index(key) == m_vector.size());
+        m_vector.append(value);
     }
 
 private:
-    Vector<Value> m_vector;
+    Vector<Value, 0, UnsafeVectorOverflow> m_vector;
 };
 
 } // namespace WTF
index 61bd04f..a186911 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -27,6 +27,7 @@
 
 #include <wtf/BitVector.h>
 #include <wtf/CommaPrinter.h>
+#include <wtf/IndexKeyType.h>
 
 namespace WTF {
 
@@ -42,30 +43,30 @@ public:
     {
     }
 
-    bool add(T* value)
+    bool add(const T& value)
     {
-        return !m_set.set(value->index());
+        return !m_set.set(IndexKeyType<T>::index(value));
     }
 
     template<typename Iterable>
     bool addAll(const Iterable& iterable)
     {
         bool result = false;
-        for (T* value : iterable)
+        for (const T& value : iterable)
             result |= add(value);
         return result;
     }
 
-    bool remove(T* value)
+    bool remove(const T& value)
     {
-        return m_set.clear(value->index());
+        return m_set.clear(IndexKeyType<T>::index(value));
     }
 
-    bool contains(T* value) const
+    bool contains(const T& value) const
     {
         if (!value)
             return false;
-        return m_set.get(value->index());
+        return m_set.get(IndexKeyType<T>::index(value));
     }
 
     size_t size() const
@@ -100,7 +101,7 @@ public:
             {
             }
 
-            T* operator*()
+            T operator*()
             {
                 return m_collection->at(*m_iter);
             }
diff --git a/Source/WTF/wtf/Range.h b/Source/WTF/wtf/Range.h
new file mode 100644 (file)
index 0000000..272a50f
--- /dev/null
@@ -0,0 +1,137 @@
+/*
+ * Copyright (C) 2015-2017 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. 
+ */
+
+#pragma once
+
+#include <limits.h>
+#include <wtf/MathExtras.h>
+#include <wtf/PrintStream.h>
+
+namespace WTF {
+
+// Note that the 'begin' is inclusive, while the 'end' is exclusive. These two ranges are non-
+// overlapping:
+//
+//     rangeA = 0...8
+//     rangeB = 8...16
+
+template<typename PassedType>
+class Range {
+public:
+    typedef PassedType Type;
+    
+    Range()
+        : m_begin(0)
+        , m_end(0)
+    {
+    }
+
+    explicit Range(Type value)
+        : m_begin(value)
+        , m_end(value + 1)
+    {
+        ASSERT(m_end >= m_begin);
+    }
+
+    Range(Type begin, Type end)
+        : m_begin(begin)
+        , m_end(end)
+    {
+        ASSERT(m_end >= m_begin);
+        if (m_begin == m_end) {
+            // Canonicalize empty ranges.
+            m_begin = 0;
+            m_end = 0;
+        }
+    }
+
+    static Range top()
+    {
+        return Range(std::numeric_limits<Type>::min(), std::numeric_limits<Type>::max());
+    }
+
+    bool operator==(const Range& other) const
+    {
+        return m_begin == other.m_begin
+            && m_end == other.m_end;
+    }
+
+    bool operator!=(const Range& other) const
+    {
+        return !(*this == other);
+    }
+    
+    explicit operator bool() const { return m_begin != m_end; }
+
+    Range operator|(const Range& other) const
+    {
+        if (!*this)
+            return other;
+        if (!other)
+            return *this;
+        return Range(
+            std::min(m_begin, other.m_begin),
+            std::max(m_end, other.m_end));
+    }
+    
+    Range& operator|=(const Range& other)
+    {
+        return *this = *this | other;
+    }
+    
+    Type begin() const { return m_begin; }
+    Type end() const { return m_end; }
+
+    bool overlaps(const Range& other) const
+    {
+        return WTF::rangesOverlap(m_begin, m_end, other.m_begin, other.m_end);
+    }
+
+    void dump(PrintStream& out) const
+    {
+        if (*this == Range()) {
+            out.print("Bottom");
+            return;
+        }
+        if (*this == top()) {
+            out.print("Top");
+            return;
+        }
+        if (m_begin == m_end + 1) {
+            out.print(m_begin);
+            return;
+        }
+        out.print(m_begin, "...", m_end);
+    }
+
+private:
+    Type m_begin;
+    Type m_end;
+};
+
+} // namespace WTF
+
+using WTF::Range;
+
index 75471ad..ed3b4ad 100644 (file)
@@ -77,6 +77,10 @@ public:
         m_isCompact = false;
 
         // We append without compacting only if doing so is guaranteed not to resize the vector.
+        // FIXME: This heuristic is almost certainly wrong, because we don't control the capacity. I
+        // think that this means that we will sometimes be rage-compacting when we are just shy of the
+        // capacity.
+        // https://bugs.webkit.org/show_bug.cgi?id=170308
         if (m_ranges.size() + 1 < m_ranges.capacity()) {
             m_ranges.append(range);
             return;
index a16aacb..5363f03 100644 (file)
@@ -1,3 +1,15 @@
+2017-03-30  Filip Pizlo  <fpizlo@apple.com>
+
+        Air should support linear scan for optLevel<2
+        https://bugs.webkit.org/show_bug.cgi?id=170161
+
+        Reviewed by Saam Barati.
+        
+        This makes us run a bunch of JS tests at optLevel=1 to force testing of this new compiler
+        pipeline.
+
+        * Scripts/run-jsc-stress-tests:
+
 2017-03-30  Aakash Jain  <aakash_jain@apple.com>
 
         Support tvOS and watchOS in webkitdirs.pm
index ed334d1..be0f9d6 100755 (executable)
@@ -428,6 +428,7 @@ $numPasses = 0
 BASE_OPTIONS = ["--useFTLJIT=false", "--useFunctionDotArguments=true", "--maxPerThreadStackUsage=1572864"]
 EAGER_OPTIONS = ["--thresholdForJITAfterWarmUp=10", "--thresholdForJITSoon=10", "--thresholdForOptimizeAfterWarmUp=20", "--thresholdForOptimizeAfterLongWarmUp=20", "--thresholdForOptimizeSoon=20", "--thresholdForFTLOptimizeAfterWarmUp=20", "--thresholdForFTLOptimizeSoon=20", "--maximumEvalCacheableSourceLength=150000", "--useEagerCodeBlockJettisonTiming=true"]
 NO_CJIT_OPTIONS = ["--useConcurrentJIT=false", "--thresholdForJITAfterWarmUp=100", "--scribbleFreeCells=true"]
+B3O1_OPTIONS = ["--defaultB3OptLevel=1"]
 FTL_OPTIONS = ["--useFTLJIT=true"]
 
 def shouldCollectContinuously?
@@ -853,6 +854,10 @@ def runFTLNoCJIT(*optionalTestSpecificOptions)
     run("misc-ftl-no-cjit", *(FTL_OPTIONS + NO_CJIT_OPTIONS + optionalTestSpecificOptions))
 end
 
+def runFTLNoCJITB3O1(*optionalTestSpecificOptions)
+    run("ftl-no-cjit-b3o1", *(FTL_OPTIONS + NO_CJIT_OPTIONS + B3O1_OPTIONS + optionalTestSpecificOptions))
+end
+
 def runFTLNoCJITValidate(*optionalTestSpecificOptions)
     run("ftl-no-cjit-validate-sampling-profiler", "--validateGraph=true", "--useSamplingProfiler=true", "--airForceIRCAllocator=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + optionalTestSpecificOptions))
 end
@@ -885,6 +890,10 @@ def runFTLEagerNoCJITValidate(*optionalTestSpecificOptions)
     run("ftl-eager-no-cjit", "--validateGraph=true", "--airForceIRCAllocator=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + EAGER_OPTIONS + COLLECT_CONTINUOUSLY_OPTIONS + optionalTestSpecificOptions))
 end
 
+def runFTLEagerNoCJITB3O1(*optionalTestSpecificOptions)
+    run("ftl-eager-no-cjit", "--validateGraph=true", "--airForceIRCAllocator=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + EAGER_OPTIONS + B3O1_OPTIONS + optionalTestSpecificOptions))
+end
+
 def runFTLEagerNoCJITOSRValidation(*optionalTestSpecificOptions)
     run("ftl-eager-no-cjit-osr-validation", "--validateFTLOSRExitLiveness=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + EAGER_OPTIONS + COLLECT_CONTINUOUSLY_OPTIONS + optionalTestSpecificOptions))
 end
@@ -934,10 +943,12 @@ def defaultRun
 
             runNoFTL
             runFTLNoCJITValidate
+            runFTLNoCJITB3O1
             runFTLNoCJITNoPutStackValidate
             runFTLNoCJITNoInlineValidate
             runFTLEager
             runFTLEagerNoCJITValidate
+            runFTLEagerNoCJITB3O1
             runFTLNoCJITSmallPool
         end
     end
@@ -959,6 +970,7 @@ def defaultNoNoLLIntRun
 
             runNoFTL
             runFTLNoCJITValidate
+            runFTLNoCJITB3O1
             runFTLNoCJITNoPutStackValidate
             runFTLNoCJITNoInlineValidate
             runFTLEager
@@ -988,6 +1000,7 @@ def defaultSpotCheckNoMaximalFlush
 
     runFTLNoCJITOSRValidation
     runFTLNoCJITNoAccessInlining
+    runFTLNoCJITB3O1
 end
 
 def defaultSpotCheck
@@ -1010,6 +1023,7 @@ def defaultNoEagerRun
         runNoFTL
         runFTLNoCJITValidate
         runFTLNoCJITNoInlineValidate
+        runFTLNoCJITB3O1
     end
 end
 
@@ -1279,6 +1293,10 @@ def runLayoutTestFTLEagerNoCJIT
     runLayoutTest("ftl-eager-no-cjit", "--testTheFTL=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + EAGER_OPTIONS))
 end
 
+def runLayoutTestFTLEagerNoCJITB3O1
+    runLayoutTest("ftl-eager-no-cjit-b3o1", "--testTheFTL=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + EAGER_OPTIONS + B3O1_OPTIONS))
+end
+
 def noFTLRunLayoutTest
     if !$jitTests
         return
@@ -1463,6 +1481,10 @@ def runNoisyTestNoCJIT
     runNoisyTest("ftl-no-cjit", "--validateBytecode=true", "--validateGraphAtEachPhase=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + COLLECT_CONTINUOUSLY_OPTIONS))
 end
 
+def runNoisyTestNoCJITB3O1
+    runNoisyTest("ftl-no-cjit", "--validateBytecode=true", "--validateGraphAtEachPhase=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + B3O1_OPTIONS))
+end
+
 def runNoisyTestEagerNoCJIT
     runNoisyTest("ftl-eager-no-cjit", "--validateBytecode=true", "--validateGraphAtEachPhase=true", *(FTL_OPTIONS + NO_CJIT_OPTIONS + EAGER_OPTIONS + COLLECT_CONTINUOUSLY_OPTIONS))
 end
@@ -1472,6 +1494,7 @@ def defaultRunNoisyTest
     if $jitTests and $isFTLPlatform
         runNoisyTestNoFTL
         runNoisyTestNoCJIT
+        runNoisyTestNoCJITB3O1
         runNoisyTestEagerNoCJIT
     end
 end