B3 should support multiple entrypoints
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 24 Jul 2016 20:33:40 +0000 (20:33 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 24 Jul 2016 20:33:40 +0000 (20:33 +0000)
https://bugs.webkit.org/show_bug.cgi?id=159391

Reviewed by Saam Barati.
Source/JavaScriptCore:

This teaches B3 how to compile procedures with multiple entrypoints in the best way ever.

Multiple entrypoints are useful. We could use them to reduce the cost of compiling OSR
entrypoints. We could use them to implement better try/catch.

Multiple entrypoints are hard to support. All of the code that assumed that the root block
is the entrypoint would have to be changed. Transformations like moveConstants() would have
to do crazy things if the existence of multiple entrypoints prevented it from finding a
single common dominator.

Therefore, we want to add multiple entrypoints without actually teaching the compiler that
there is such a thing. That's sort of what this change does.

This adds a new opcode to both B3 and Air called EntrySwitch. It's a terminal that takes
one or more successors and no value children. The number of successors must match
Procedure::numEntrypoints(), which could be arbitrarily large. The semantics of EntrySwitch
are:

- Each of the entrypoints sets a hidden Entry variable to that entrypoint's index and jumps
  to the procedure's root block.

- An EntrySwitch is a switch statement over this hidden Entry variable.

The way that we actually implement this is that Air has a very late phase - after all
register and stack layout - that clones all code where the Entry variable is live; i.e all
code in the closure over predecessors of all blocks that do EntrySwitch.

Usually, you would use this by creating an EntrySwitch in the root block, but you don't
have to do that. Just remember that the code before EntrySwitch gets cloned for each
entrypoint. We allow cloning of an arbitrarily large amount of code because restricting it,
and so restricing the placement of EntrySwitches, would be unelegant. It would be hard to
preserve this invariant. For example we wouldn't be able to lower any value before an
EntrySwitch to a control flow diamond.

This patch gives us an easy-to-use way to use B3 to compile code with multiple entrypoints.
Inside the compiler, only code that runs very late in Air has to know about this feature.
We get the best of both worlds!

Also, I finally got rid of the requirement that you explicitly cast BasicBlock* to
FrequentedBlock. I can no longer remember why I thought that was a good idea. Removing it
doesn't cause any problems and it makes code easier to write.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3BasicBlockUtils.h:
(JSC::B3::updatePredecessorsAfter):
(JSC::B3::clearPredecessors):
(JSC::B3::recomputePredecessors):
* b3/B3FrequencyClass.h:
(JSC::B3::maxFrequency):
* b3/B3Generate.h:
* b3/B3LowerToAir.cpp:
(JSC::B3::Air::LowerToAir::lower):
* b3/B3MoveConstants.cpp:
* b3/B3Opcode.cpp:
(WTF::printInternal):
* b3/B3Opcode.h:
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::isFastConstant):
(JSC::B3::Procedure::entrypointLabel):
(JSC::B3::Procedure::addDataSection):
* b3/B3Procedure.h:
(JSC::B3::Procedure::numEntrypoints):
(JSC::B3::Procedure::setNumEntrypoints):
(JSC::B3::Procedure::setLastPhaseName):
* b3/B3Validate.cpp:
* b3/B3Value.cpp:
(JSC::B3::Value::effects):
(JSC::B3::Value::typeFor):
* b3/B3Value.h:
* b3/air/AirCode.cpp:
(JSC::B3::Air::Code::cCallSpecial):
(JSC::B3::Air::Code::isEntrypoint):
(JSC::B3::Air::Code::resetReachability):
(JSC::B3::Air::Code::dump):
* b3/air/AirCode.h:
(JSC::B3::Air::Code::setFrameSize):
(JSC::B3::Air::Code::numEntrypoints):
(JSC::B3::Air::Code::entrypoints):
(JSC::B3::Air::Code::entrypoint):
(JSC::B3::Air::Code::setEntrypoints):
(JSC::B3::Air::Code::entrypointLabel):
(JSC::B3::Air::Code::setEntrypointLabels):
(JSC::B3::Air::Code::calleeSaveRegisters):
* b3/air/AirCustom.h:
(JSC::B3::Air::PatchCustom::isTerminal):
(JSC::B3::Air::PatchCustom::hasNonArgEffects):
(JSC::B3::Air::PatchCustom::hasNonArgNonControlEffects):
(JSC::B3::Air::PatchCustom::generate):
(JSC::B3::Air::CommonCustomBase::hasNonArgEffects):
(JSC::B3::Air::CCallCustom::forEachArg):
(JSC::B3::Air::ColdCCallCustom::forEachArg):
(JSC::B3::Air::ShuffleCustom::forEachArg):
(JSC::B3::Air::EntrySwitchCustom::forEachArg):
(JSC::B3::Air::EntrySwitchCustom::isValidFormStatic):
(JSC::B3::Air::EntrySwitchCustom::isValidForm):
(JSC::B3::Air::EntrySwitchCustom::admitsStack):
(JSC::B3::Air::EntrySwitchCustom::isTerminal):
(JSC::B3::Air::EntrySwitchCustom::hasNonArgNonControlEffects):
(JSC::B3::Air::EntrySwitchCustom::generate):
* b3/air/AirGenerate.cpp:
(JSC::B3::Air::prepareForGeneration):
(JSC::B3::Air::generate):
* b3/air/AirLowerEntrySwitch.cpp: Added.
(JSC::B3::Air::lowerEntrySwitch):
* b3/air/AirLowerEntrySwitch.h: Added.
* b3/air/AirOpcode.opcodes:
* b3/air/AirOptimizeBlockOrder.cpp:
(JSC::B3::Air::blocksInOptimizedOrder):
* b3/air/AirSpecial.cpp:
(JSC::B3::Air::Special::isTerminal):
(JSC::B3::Air::Special::hasNonArgEffects):
(JSC::B3::Air::Special::hasNonArgNonControlEffects):
* b3/air/AirSpecial.h:
* b3/air/AirValidate.cpp:
* b3/air/opcode_generator.rb:
* b3/testb3.cpp:

Source/WTF:

* wtf/GraphNodeWorklist.h: Expose some handy functionality.
(WTF::GraphNodeWorklist::pop):
(WTF::GraphNodeWorklist::saw):
(WTF::GraphNodeWorklist::seen):
* wtf/VectorTraits.h: Fix a bug! Otherwise filling a vector of byte-sized enum classes doesn't work.

Websites/webkit.org:

Update some statements about ControlValue (which doesn't exist anymore) and add a blurb
about EntrySwitch.

* docs/b3/index.html:
* docs/b3/intermediate-representation.html:

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

35 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3BasicBlockUtils.h
Source/JavaScriptCore/b3/B3FrequencyClass.h
Source/JavaScriptCore/b3/B3Generate.h
Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h
Source/JavaScriptCore/b3/B3LowerToAir.cpp
Source/JavaScriptCore/b3/B3MoveConstants.cpp
Source/JavaScriptCore/b3/B3Opcode.cpp
Source/JavaScriptCore/b3/B3Opcode.h
Source/JavaScriptCore/b3/B3Procedure.cpp
Source/JavaScriptCore/b3/B3Procedure.h
Source/JavaScriptCore/b3/B3Validate.cpp
Source/JavaScriptCore/b3/B3Value.cpp
Source/JavaScriptCore/b3/B3Value.h
Source/JavaScriptCore/b3/air/AirCode.cpp
Source/JavaScriptCore/b3/air/AirCode.h
Source/JavaScriptCore/b3/air/AirCustom.h
Source/JavaScriptCore/b3/air/AirGenerate.cpp
Source/JavaScriptCore/b3/air/AirLowerEntrySwitch.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirLowerEntrySwitch.h [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirOpcode.opcodes
Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp
Source/JavaScriptCore/b3/air/AirSpecial.cpp
Source/JavaScriptCore/b3/air/AirSpecial.h
Source/JavaScriptCore/b3/air/AirValidate.cpp
Source/JavaScriptCore/b3/air/opcode_generator.rb
Source/JavaScriptCore/b3/testb3.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/GraphNodeWorklist.h
Source/WTF/wtf/VectorTraits.h
Websites/webkit.org/ChangeLog
Websites/webkit.org/docs/b3/index.html
Websites/webkit.org/docs/b3/intermediate-representation.html

index d458c776862a4129c962edb734e66b3e40d2d73c..f8f23097ba9cd738d7433f36d61dc882cddef8bc 100644 (file)
@@ -89,6 +89,7 @@ set(JavaScriptCore_SOURCES
     b3/air/AirIteratedRegisterCoalescing.cpp
     b3/air/AirLogRegisterPressure.cpp
     b3/air/AirLowerAfterRegAlloc.cpp
+    b3/air/AirLowerEntrySwitch.cpp
     b3/air/AirLowerMacros.cpp
     b3/air/AirOptimizeBlockOrder.cpp
     b3/air/AirPhaseScope.cpp
index af7274e9bbdffb4391d9782e1a400b33e5cf5c72..6670121667b6870bf9d4f3e0fbf9cc4e8f239610 100644 (file)
@@ -1,3 +1,128 @@
+2016-07-24  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should support multiple entrypoints
+        https://bugs.webkit.org/show_bug.cgi?id=159391
+
+        Reviewed by Saam Barati.
+        
+        This teaches B3 how to compile procedures with multiple entrypoints in the best way ever.
+        
+        Multiple entrypoints are useful. We could use them to reduce the cost of compiling OSR
+        entrypoints. We could use them to implement better try/catch.
+        
+        Multiple entrypoints are hard to support. All of the code that assumed that the root block
+        is the entrypoint would have to be changed. Transformations like moveConstants() would have
+        to do crazy things if the existence of multiple entrypoints prevented it from finding a
+        single common dominator.
+        
+        Therefore, we want to add multiple entrypoints without actually teaching the compiler that
+        there is such a thing. That's sort of what this change does.
+        
+        This adds a new opcode to both B3 and Air called EntrySwitch. It's a terminal that takes
+        one or more successors and no value children. The number of successors must match
+        Procedure::numEntrypoints(), which could be arbitrarily large. The semantics of EntrySwitch
+        are:
+        
+        - Each of the entrypoints sets a hidden Entry variable to that entrypoint's index and jumps
+          to the procedure's root block.
+        
+        - An EntrySwitch is a switch statement over this hidden Entry variable.
+        
+        The way that we actually implement this is that Air has a very late phase - after all
+        register and stack layout - that clones all code where the Entry variable is live; i.e all
+        code in the closure over predecessors of all blocks that do EntrySwitch.
+        
+        Usually, you would use this by creating an EntrySwitch in the root block, but you don't
+        have to do that. Just remember that the code before EntrySwitch gets cloned for each
+        entrypoint. We allow cloning of an arbitrarily large amount of code because restricting it,
+        and so restricing the placement of EntrySwitches, would be unelegant. It would be hard to
+        preserve this invariant. For example we wouldn't be able to lower any value before an
+        EntrySwitch to a control flow diamond.
+        
+        This patch gives us an easy-to-use way to use B3 to compile code with multiple entrypoints.
+        Inside the compiler, only code that runs very late in Air has to know about this feature.
+        We get the best of both worlds!
+        
+        Also, I finally got rid of the requirement that you explicitly cast BasicBlock* to
+        FrequentedBlock. I can no longer remember why I thought that was a good idea. Removing it
+        doesn't cause any problems and it makes code easier to write.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * b3/B3BasicBlockUtils.h:
+        (JSC::B3::updatePredecessorsAfter):
+        (JSC::B3::clearPredecessors):
+        (JSC::B3::recomputePredecessors):
+        * b3/B3FrequencyClass.h:
+        (JSC::B3::maxFrequency):
+        * b3/B3Generate.h:
+        * b3/B3LowerToAir.cpp:
+        (JSC::B3::Air::LowerToAir::lower):
+        * b3/B3MoveConstants.cpp:
+        * b3/B3Opcode.cpp:
+        (WTF::printInternal):
+        * b3/B3Opcode.h:
+        * b3/B3Procedure.cpp:
+        (JSC::B3::Procedure::isFastConstant):
+        (JSC::B3::Procedure::entrypointLabel):
+        (JSC::B3::Procedure::addDataSection):
+        * b3/B3Procedure.h:
+        (JSC::B3::Procedure::numEntrypoints):
+        (JSC::B3::Procedure::setNumEntrypoints):
+        (JSC::B3::Procedure::setLastPhaseName):
+        * b3/B3Validate.cpp:
+        * b3/B3Value.cpp:
+        (JSC::B3::Value::effects):
+        (JSC::B3::Value::typeFor):
+        * b3/B3Value.h:
+        * b3/air/AirCode.cpp:
+        (JSC::B3::Air::Code::cCallSpecial):
+        (JSC::B3::Air::Code::isEntrypoint):
+        (JSC::B3::Air::Code::resetReachability):
+        (JSC::B3::Air::Code::dump):
+        * b3/air/AirCode.h:
+        (JSC::B3::Air::Code::setFrameSize):
+        (JSC::B3::Air::Code::numEntrypoints):
+        (JSC::B3::Air::Code::entrypoints):
+        (JSC::B3::Air::Code::entrypoint):
+        (JSC::B3::Air::Code::setEntrypoints):
+        (JSC::B3::Air::Code::entrypointLabel):
+        (JSC::B3::Air::Code::setEntrypointLabels):
+        (JSC::B3::Air::Code::calleeSaveRegisters):
+        * b3/air/AirCustom.h:
+        (JSC::B3::Air::PatchCustom::isTerminal):
+        (JSC::B3::Air::PatchCustom::hasNonArgEffects):
+        (JSC::B3::Air::PatchCustom::hasNonArgNonControlEffects):
+        (JSC::B3::Air::PatchCustom::generate):
+        (JSC::B3::Air::CommonCustomBase::hasNonArgEffects):
+        (JSC::B3::Air::CCallCustom::forEachArg):
+        (JSC::B3::Air::ColdCCallCustom::forEachArg):
+        (JSC::B3::Air::ShuffleCustom::forEachArg):
+        (JSC::B3::Air::EntrySwitchCustom::forEachArg):
+        (JSC::B3::Air::EntrySwitchCustom::isValidFormStatic):
+        (JSC::B3::Air::EntrySwitchCustom::isValidForm):
+        (JSC::B3::Air::EntrySwitchCustom::admitsStack):
+        (JSC::B3::Air::EntrySwitchCustom::isTerminal):
+        (JSC::B3::Air::EntrySwitchCustom::hasNonArgNonControlEffects):
+        (JSC::B3::Air::EntrySwitchCustom::generate):
+        * b3/air/AirGenerate.cpp:
+        (JSC::B3::Air::prepareForGeneration):
+        (JSC::B3::Air::generate):
+        * b3/air/AirLowerEntrySwitch.cpp: Added.
+        (JSC::B3::Air::lowerEntrySwitch):
+        * b3/air/AirLowerEntrySwitch.h: Added.
+        * b3/air/AirOpcode.opcodes:
+        * b3/air/AirOptimizeBlockOrder.cpp:
+        (JSC::B3::Air::blocksInOptimizedOrder):
+        * b3/air/AirSpecial.cpp:
+        (JSC::B3::Air::Special::isTerminal):
+        (JSC::B3::Air::Special::hasNonArgEffects):
+        (JSC::B3::Air::Special::hasNonArgNonControlEffects):
+        * b3/air/AirSpecial.h:
+        * b3/air/AirValidate.cpp:
+        * b3/air/opcode_generator.rb:
+        * b3/testb3.cpp:
+
 2016-07-24  Filip Pizlo  <fpizlo@apple.com>
 
         Unreviewed, fix broken test. I don't know why I goofed this up without seeing it before landing.
index b7fae8753d9b0d9bbe7f264dae5ee82f74649e74..c31b39781c643e3f97409e78bbd1a2ac3bf7e60c 100644 (file)
                0FDB2CEA174896C7007B3C1B /* ConcurrentJITLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDB2CE9174896C7007B3C1B /* ConcurrentJITLock.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FDDBFB51666EED800C55FEF /* DFGVariableAccessDataDump.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDDBFB21666EED500C55FEF /* DFGVariableAccessDataDump.cpp */; };
                0FDDBFB61666EEDA00C55FEF /* DFGVariableAccessDataDump.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFB31666EED500C55FEF /* DFGVariableAccessDataDump.h */; };
+               0FDF70851D3F2C2200927449 /* AirLowerEntrySwitch.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDF70831D3F2C1F00927449 /* AirLowerEntrySwitch.cpp */; };
+               0FDF70861D3F2C2500927449 /* AirLowerEntrySwitch.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDF70841D3F2C1F00927449 /* AirLowerEntrySwitch.h */; };
                0FE050141AA9091100D33B33 /* ArgumentsMode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE0500C1AA9091100D33B33 /* ArgumentsMode.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FE050151AA9091100D33B33 /* DirectArgumentsOffset.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE0500D1AA9091100D33B33 /* DirectArgumentsOffset.cpp */; };
                0FE050161AA9091100D33B33 /* DirectArgumentsOffset.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE0500E1AA9091100D33B33 /* DirectArgumentsOffset.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FDB2CE9174896C7007B3C1B /* ConcurrentJITLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ConcurrentJITLock.h; sourceTree = "<group>"; };
                0FDDBFB21666EED500C55FEF /* DFGVariableAccessDataDump.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGVariableAccessDataDump.cpp; path = dfg/DFGVariableAccessDataDump.cpp; sourceTree = "<group>"; };
                0FDDBFB31666EED500C55FEF /* DFGVariableAccessDataDump.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGVariableAccessDataDump.h; path = dfg/DFGVariableAccessDataDump.h; sourceTree = "<group>"; };
+               0FDF70831D3F2C1F00927449 /* AirLowerEntrySwitch.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirLowerEntrySwitch.cpp; path = b3/air/AirLowerEntrySwitch.cpp; sourceTree = "<group>"; };
+               0FDF70841D3F2C1F00927449 /* AirLowerEntrySwitch.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLowerEntrySwitch.h; path = b3/air/AirLowerEntrySwitch.h; sourceTree = "<group>"; };
                0FE0500C1AA9091100D33B33 /* ArgumentsMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ArgumentsMode.h; sourceTree = "<group>"; };
                0FE0500D1AA9091100D33B33 /* DirectArgumentsOffset.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DirectArgumentsOffset.cpp; sourceTree = "<group>"; };
                0FE0500E1AA9091100D33B33 /* DirectArgumentsOffset.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DirectArgumentsOffset.h; sourceTree = "<group>"; };
                                0FE34C181C4B39AE0003A512 /* AirLogRegisterPressure.h */,
                                0F6183251C45BF070072450B /* AirLowerAfterRegAlloc.cpp */,
                                0F6183261C45BF070072450B /* AirLowerAfterRegAlloc.h */,
+                               0FDF70831D3F2C1F00927449 /* AirLowerEntrySwitch.cpp */,
+                               0FDF70841D3F2C1F00927449 /* AirLowerEntrySwitch.h */,
                                0F6183271C45BF070072450B /* AirLowerMacros.cpp */,
                                0F6183281C45BF070072450B /* AirLowerMacros.h */,
                                264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
                                BC18C4630E16F5CD00B34460 /* SourceProvider.h in Headers */,
                                E49DC16C12EF294E00184A1F /* SourceProviderCache.h in Headers */,
                                E49DC16D12EF295300184A1F /* SourceProviderCacheItem.h in Headers */,
+                               0FDF70861D3F2C2500927449 /* AirLowerEntrySwitch.h in Headers */,
                                0FB7F39E15ED8E4600F167B2 /* SparseArrayValueMap.h in Headers */,
                                A7386554118697B400540279 /* SpecializedThunkJIT.h in Headers */,
                                0F5541B21613C1FB00CE3E25 /* SpecialPointer.h in Headers */,
                                0F24E55017EE274900ABB217 /* Repatch.cpp in Sources */,
                                0F6B8AD81C4EDDA200969052 /* B3DuplicateTails.cpp in Sources */,
                                527773DE1AAF83AC00BDE7E8 /* RuntimeType.cpp in Sources */,
+                               0FDF70851D3F2C2200927449 /* AirLowerEntrySwitch.cpp in Sources */,
                                0F7700921402FF3C0078EB39 /* SamplingCounter.cpp in Sources */,
                                7905BB681D12050E0019FE57 /* InlineAccess.cpp in Sources */,
                                0FE050271AA9095600D33B33 /* ScopedArguments.cpp in Sources */,
index ba558dc2d9e51eb6007af3d62d89050c5cf0bce5..4a71767878c6eb3723050de92195edea585019f7 100644 (file)
@@ -86,14 +86,18 @@ void updatePredecessorsAfter(BasicBlock* root)
 }
 
 template<typename BasicBlock>
-void recomputePredecessors(Vector<std::unique_ptr<BasicBlock>>& blocks)
+void clearPredecessors(Vector<std::unique_ptr<BasicBlock>>& blocks)
 {
-    // Clear all predecessor lists first.
     for (auto& block : blocks) {
         if (block)
             block->predecessors().resize(0);
     }
+}
 
+template<typename BasicBlock>
+void recomputePredecessors(Vector<std::unique_ptr<BasicBlock>>& blocks)
+{
+    clearPredecessors(blocks);
     updatePredecessorsAfter(blocks[0].get());
 }
 
index 072bd851f790f0ee2c6e0a218c4f418c36712f1e..4a9621d4879329179a4f8c7d78e3ac94228b3943 100644 (file)
@@ -43,6 +43,13 @@ enum class FrequencyClass : uint8_t {
     Rare
 };
 
+inline FrequencyClass maxFrequency(FrequencyClass a, FrequencyClass b)
+{
+    if (a == FrequencyClass::Normal)
+        return FrequencyClass::Normal;
+    return b;
+}
+
 } } // namespace JSC::B3
 
 namespace WTF {
index bd09035c4f4028bb9601af4bc78837b069f2d911..88b2fa5f56a527e0e7a36340d3a469c7d45abb01 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -39,12 +39,12 @@ namespace Air { class Code; }
 
 // This takes a B3::Procedure, optimizes it in-place, lowers it to Air, and prepares the Air for
 // generation.
-void prepareForGeneration(Procedure&, unsigned optLevel = 1);
+JS_EXPORT_PRIVATE void prepareForGeneration(Procedure&, unsigned optLevel = 1);
 
 // 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
 // Air::generate() on the Procedure::code().
-void generate(Procedure&, CCallHelpers&);
+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
index d1b7a5d12a480a7d86ecdae3870778e60a274d97..21c9b5cafbfb0ffd92efde6792b523ea8403c388 100644 (file)
@@ -39,7 +39,7 @@ namespace JSC { namespace B3 {
 template<typename BasicBlock>
 class GenericFrequentedBlock {
 public:
-    explicit GenericFrequentedBlock(
+    GenericFrequentedBlock(
         BasicBlock* block = nullptr, FrequencyClass frequency = FrequencyClass::Normal)
         : m_block(block)
         , m_frequency(frequency)
index 8d910fc6a4ad4f07aa5f3c06688d0bf85d13f451..e247043b678b2083f1227233995504d8d539ae05 100644 (file)
@@ -2464,6 +2464,11 @@ private:
             append(Air::Oops);
             return;
         }
+            
+        case B3::EntrySwitch: {
+            append(Air::EntrySwitch);
+            return;
+        }
 
         default:
             break;
index 5093f8b800f2fd6f397f91e7a1cd787ad5da22da..ad01539dd7c11ed621dcef2fe01766665e56c41e 100644 (file)
@@ -62,7 +62,7 @@ public:
         
         hoistConstants(
             [&] (const ValueKey& key) -> bool {
-                return key.opcode() == Const32 || key.opcode() == Const64;
+                return key.opcode() == Const32 || key.opcode() == Const64 || key.opcode() == ArgumentReg;
             });
     }
 
index 207221dc0925c90a65adcc2f957a14ffc34e0454..b57ba26a335485ae13c16c9cd851649623727f07 100644 (file)
@@ -290,6 +290,9 @@ void printInternal(PrintStream& out, Opcode opcode)
     case Switch:
         out.print("Switch");
         return;
+    case EntrySwitch:
+        out.print("EntrySwitch");
+        return;
     case Return:
         out.print("Return");
         return;
index 13ab017ce0c0e525e42e9317f8b981236cf73caf..6a617ec293fcfc25c44afc9a5bf248501b190c7e 100644 (file)
@@ -216,6 +216,11 @@ enum Opcode : int16_t {
 
     // Switch. Switches over either Int32 or Int64. Uses the SwitchValue class.
     Switch,
+    
+    // Multiple entrypoints are supported via the EntrySwitch operation. Place this in the root
+    // block and list the entrypoints as the successors. All blocks backwards-reachable from
+    // EntrySwitch are duplicated for each entrypoint.
+    EntrySwitch,
 
     // Return. Note that B3 procedures don't know their return type, so this can just return any
     // type.
index 077c905cf524317aebf5d806dbd9a9b61f4f574e..c30dbabafadd9d5d9dfddcd3335e09c7fba89650 100644 (file)
@@ -280,6 +280,11 @@ bool Procedure::isFastConstant(const ValueKey& constant)
     return m_fastConstants.contains(constant);
 }
 
+CCallHelpers::Label Procedure::entrypointLabel(unsigned index) const
+{
+    return m_code->entrypointLabel(index);
+}
+
 void* Procedure::addDataSection(size_t size)
 {
     if (!size)
index d9bd029521273c2d82caa132fde59490d9ec7fd0..576413e1090a8477e34d42358c698465c1ad591d 100644 (file)
@@ -34,6 +34,7 @@
 #include "B3SparseCollection.h"
 #include "B3Type.h"
 #include "B3ValueKey.h"
+#include "CCallHelpers.h"
 #include "PureNaN.h"
 #include "RegisterAtOffsetList.h"
 #include <wtf/Bag.h>
@@ -57,6 +58,13 @@ class Variable;
 
 namespace Air { class Code; }
 
+// This represents B3's view of a piece of code. Note that this object must exist in a 1:1
+// relationship with Air::Code. B3::Procedure and Air::Code are just different facades of the B3
+// compiler's knowledge about a piece of code. Some kinds of state aren't perfect fits for either
+// Procedure or Code, and are placed in one or the other based on convenience. Procedure always
+// allocates a Code, and a Code cannot be allocated without an owning Procedure and they always
+// have references to each other.
+
 class Procedure {
     WTF_MAKE_NONCOPYABLE(Procedure);
     WTF_MAKE_FAST_ALLOCATED;
@@ -209,6 +217,14 @@ public:
 
     void addFastConstant(const ValueKey&);
     bool isFastConstant(const ValueKey&);
+    
+    unsigned numEntrypoints() const { return m_numEntrypoints; }
+    void setNumEntrypoints(unsigned numEntrypoints) { m_numEntrypoints = numEntrypoints; }
+    
+    // Only call this after code generation is complete. Note that the label for the 0th entrypoint
+    // should point to exactly where the code generation cursor was before you started generating
+    // code.
+    JS_EXPORT_PRIVATE CCallHelpers::Label entrypointLabel(unsigned entrypointIndex) const;
 
     // The name has to be a string literal, since we don't do any memory management for the string.
     void setLastPhaseName(const char* name)
@@ -261,6 +277,7 @@ private:
     std::unique_ptr<CFG> m_cfg;
     std::unique_ptr<Dominators> m_dominators;
     HashSet<ValueKey> m_fastConstants;
+    unsigned m_numEntrypoints { 1 };
     const char* m_lastPhaseName;
     std::unique_ptr<OpaqueByproducts> m_byproducts;
     std::unique_ptr<Air::Code> m_code;
index ec5a83ba261e088ff531a5d54820cc754b50265b..edc2054817a3ea3cdf906c8509bfd1b150240451 100644 (file)
@@ -414,7 +414,13 @@ public:
                 for (unsigned i = 1; i < caseValues.size(); ++i)
                     VALIDATE(caseValues[i - 1] != caseValues[i], ("At ", *value, ", caseValue = ", caseValues[i]));
                 break;
-            } }
+            }
+            case EntrySwitch:
+                VALIDATE(!value->numChildren(), ("At ", *value));
+                VALIDATE(value->type() == Void, ("At ", *value));
+                VALIDATE(valueOwner.get(value)->numSuccessors() == m_procedure.numEntrypoints(), ("At ", *value));
+                break;
+            }
 
             VALIDATE(!(value->effects().writes && value->key()), ("At ", *value));
         }
index cd977e5671a774a96b977f72e85f0e486b14a52c..4082324da73457d0b7164e173c9586215ffe4fd6 100644 (file)
@@ -612,6 +612,7 @@ Effects Value::effects() const
     case Switch:
     case Return:
     case Oops:
+    case EntrySwitch:
         result.terminal = true;
         break;
     }
@@ -790,6 +791,7 @@ Type Value::typeFor(Opcode opcode, Value* firstChild, Value* secondChild)
     case Branch:
     case Return:
     case Oops:
+    case EntrySwitch:
         return Void;
     case Select:
         ASSERT(secondChild);
index 81bb810eb832c171f76073671f248e1b2342b6d7..3a1beff4922087858c342d8eb1b3c8b0119094d3 100644 (file)
@@ -283,6 +283,7 @@ private:
         case Phi:
         case Jump:
         case Oops:
+        case EntrySwitch:
             if (UNLIKELY(numArgs))
                 badOpcode(opcode, numArgs);
             break;
index d8e88e6f45d213f0d802b5fa6baf12e7116a29a9..0d0fda38405ec77de56610e0fa08d71caa468d4d 100644 (file)
@@ -32,6 +32,7 @@
 #include "B3BasicBlockUtils.h"
 #include "B3Procedure.h"
 #include "B3StackSlot.h"
+#include <wtf/ListDump.h>
 
 namespace JSC { namespace B3 { namespace Air {
 
@@ -79,18 +80,38 @@ CCallSpecial* Code::cCallSpecial()
     return m_cCallSpecial;
 }
 
+bool Code::isEntrypoint(BasicBlock* block) const
+{
+    if (m_entrypoints.isEmpty())
+        return !block->index();
+    
+    for (const FrequentedBlock& entrypoint : m_entrypoints) {
+        if (entrypoint.block() == block)
+            return true;
+    }
+    return false;
+}
+
 void Code::resetReachability()
 {
-    recomputePredecessors(m_blocks);
+    clearPredecessors(m_blocks);
+    if (m_entrypoints.isEmpty())
+        updatePredecessorsAfter(m_blocks[0].get());
+    else {
+        for (const FrequentedBlock& entrypoint : m_entrypoints)
+            updatePredecessorsAfter(entrypoint.block());
+    }
     
     for (auto& block : m_blocks) {
-        if (isBlockDead(block.get()))
+        if (isBlockDead(block.get()) && !isEntrypoint(block.get()))
             block = nullptr;
     }
 }
 
 void Code::dump(PrintStream& out) const
 {
+    if (!m_entrypoints.isEmpty())
+        out.print("Entrypoints: ", listDump(m_entrypoints), "\n");
     for (BasicBlock* block : *this)
         out.print(deepDump(block));
     if (stackSlots().size()) {
index 59ce9578473f6b7c804e2af512771c5dfb1cf12a..64a745d0210b6a7fcb7a9351b130ae09a26d250d 100644 (file)
@@ -35,6 +35,7 @@
 #include "AirTmp.h"
 #include "B3IndexMap.h"
 #include "B3SparseCollection.h"
+#include "CCallHelpers.h"
 #include "RegisterAtOffsetList.h"
 #include "StackAlignment.h"
 
@@ -119,6 +120,32 @@ public:
         m_frameSize = frameSize;
     }
 
+    // Note that this is not the same thing as proc().numEntrypoints(). This value here may be zero
+    // until we lower EntrySwitch.
+    unsigned numEntrypoints() const { return m_entrypoints.size(); }
+    const Vector<FrequentedBlock>& entrypoints() const { return m_entrypoints; }
+    const FrequentedBlock& entrypoint(unsigned index) const { return m_entrypoints[index]; }
+    bool isEntrypoint(BasicBlock*) const;
+    
+    // This is used by lowerEntrySwitch().
+    template<typename Vector>
+    void setEntrypoints(Vector&& vector)
+    {
+        m_entrypoints = std::forward<Vector>(vector);
+    }
+    
+    CCallHelpers::Label entrypointLabel(unsigned index) const
+    {
+        return m_entrypointLabels[index];
+    }
+    
+    // This is used by generate().
+    template<typename Vector>
+    void setEntrypointLabels(Vector&& vector)
+    {
+        m_entrypointLabels = std::forward<Vector>(vector);
+    }
+
     const RegisterAtOffsetList& calleeSaveRegisters() const { return m_calleeSaveRegisters; }
     RegisterAtOffsetList& calleeSaveRegisters() { return m_calleeSaveRegisters; }
 
@@ -235,6 +262,8 @@ private:
     unsigned m_frameSize { 0 };
     unsigned m_callArgAreaSize { 0 };
     RegisterAtOffsetList m_calleeSaveRegisters;
+    Vector<FrequentedBlock> m_entrypoints; // This is empty until after lowerEntrySwitch().
+    Vector<CCallHelpers::Label> m_entrypointLabels; // This is empty until code generation.
     const char* m_lastPhaseName;
 };
 
index dc84c584395a58eda4c9934f40fa307b98634b38..3a92ed5d9215219a0408a1c9a58d5418e6eab3e2 100644 (file)
@@ -90,6 +90,11 @@ struct PatchCustom {
         return inst.args[0].special()->isTerminal(inst);
     }
 
+    static bool hasNonArgEffects(Inst& inst)
+    {
+        return inst.args[0].special()->hasNonArgEffects(inst);
+    }
+
     static bool hasNonArgNonControlEffects(Inst& inst)
     {
         return inst.args[0].special()->hasNonArgNonControlEffects(inst);
@@ -102,10 +107,18 @@ struct PatchCustom {
     }
 };
 
+template<typename Subtype>
+struct CommonCustomBase {
+    static bool hasNonArgEffects(Inst& inst)
+    {
+        return Subtype::isTerminal(inst) || Subtype::hasNonArgNonControlEffects(inst);
+    }
+};
+
 // Definition of CCall instruction. CCall is used for hot path C function calls. It's lowered to a
 // Patch with an Air CCallSpecial along with code to marshal instructions. The lowering happens
 // before register allocation, so that the register allocator sees the clobbers.
-struct CCallCustom {
+struct CCallCustom : public CommonCustomBase<CCallCustom> {
     template<typename Functor>
     static void forEachArg(Inst& inst, const Functor& functor)
     {
@@ -171,7 +184,7 @@ struct ColdCCallCustom : CCallCustom {
     }
 };
 
-struct ShuffleCustom {
+struct ShuffleCustom : public CommonCustomBase<ShuffleCustom> {
     template<typename Functor>
     static void forEachArg(Inst& inst, const Functor& functor)
     {
@@ -220,6 +233,47 @@ struct ShuffleCustom {
     static CCallHelpers::Jump generate(Inst&, CCallHelpers&, GenerationContext&);
 };
 
+struct EntrySwitchCustom : public CommonCustomBase<EntrySwitchCustom> {
+    template<typename Func>
+    static void forEachArg(Inst&, const Func&)
+    {
+    }
+    
+    template<typename... Arguments>
+    static bool isValidFormStatic(Arguments...)
+    {
+        return !sizeof...(Arguments);
+    }
+    
+    static bool isValidForm(Inst& inst)
+    {
+        return inst.args.isEmpty();
+    }
+    
+    static bool admitsStack(Inst&, unsigned)
+    {
+        return false;
+    }
+    
+    static bool isTerminal(Inst&)
+    {
+        return true;
+    }
+    
+    static bool hasNonArgNonControlEffects(Inst&)
+    {
+        return false;
+    }
+
+    static CCallHelpers::Jump generate(Inst&, CCallHelpers&, GenerationContext&)
+    {
+        // This should never be reached because we should have lowered EntrySwitch before
+        // generation.
+        UNREACHABLE_FOR_PLATFORM();
+        return CCallHelpers::Jump();
+    }
+};
+
 } } } // namespace JSC::B3::Air
 
 #endif // ENABLE(B3_JIT)
index 5171922250f5f4bfea04e7d46ad682ad906e3839..41184121c850c37b53618dfe8ba394f4407bda00 100644 (file)
@@ -39,6 +39,7 @@
 #include "AirIteratedRegisterCoalescing.h"
 #include "AirLogRegisterPressure.h"
 #include "AirLowerAfterRegAlloc.h"
+#include "AirLowerEntrySwitch.h"
 #include "AirLowerMacros.h"
 #include "AirOpcodeUtils.h"
 #include "AirOptimizeBlockOrder.h"
@@ -127,10 +128,6 @@ void prepareForGeneration(Code& code)
     // phase.
     simplifyCFG(code);
 
-    // This sorts the basic blocks in Code to achieve an ordering that maximizes the likelihood that a high
-    // frequency successor is also the fall-through target.
-    optimizeBlockOrder(code);
-
     // This is needed to satisfy a requirement of B3::StackmapValue.
     reportUsedRegisters(code);
 
@@ -139,6 +136,16 @@ void prepareForGeneration(Code& code)
     // use. We _must_ run this after reportUsedRegisters(), since that kills variable assignments
     // that seem dead. Luckily, this phase does not change register liveness, so that's OK.
     fixPartialRegisterStalls(code);
+    
+    // Actually create entrypoints.
+    lowerEntrySwitch(code);
+    
+    // The control flow graph can be simplified further after we have lowered EntrySwitch.
+    simplifyCFG(code);
+
+    // This sorts the basic blocks in Code to achieve an ordering that maximizes the likelihood that a high
+    // frequency successor is also the fall-through target.
+    optimizeBlockOrder(code);
 
     if (shouldValidateIR())
         validate(code);
@@ -157,22 +164,11 @@ void generate(Code& code, CCallHelpers& jit)
 
     DisallowMacroScratchRegisterUsage disallowScratch(jit);
 
-    // And now, we generate code.
-    jit.emitFunctionPrologue();
-    if (code.frameSize())
-        jit.addPtr(CCallHelpers::TrustedImm32(-code.frameSize()), MacroAssembler::stackPointerRegister);
-
     auto argFor = [&] (const RegisterAtOffset& entry) -> CCallHelpers::Address {
         return CCallHelpers::Address(GPRInfo::callFrameRegister, entry.offset());
     };
     
-    for (const RegisterAtOffset& entry : code.calleeSaveRegisters()) {
-        if (entry.reg().isGPR())
-            jit.storePtr(entry.reg().gpr(), argFor(entry));
-        else
-            jit.storeDouble(entry.reg().fpr(), argFor(entry));
-    }
-
+    // And now, we generate code.
     GenerationContext context;
     context.code = &code;
     context.blockLabels.resize(code.size());
@@ -206,6 +202,20 @@ void generate(Code& code, CCallHelpers& jit)
         blockJumps[block].link(&jit);
         CCallHelpers::Label label = jit.label();
         *context.blockLabels[block] = label;
+
+        if (code.isEntrypoint(block)) {
+            jit.emitFunctionPrologue();
+            if (code.frameSize())
+                jit.addPtr(CCallHelpers::TrustedImm32(-code.frameSize()), MacroAssembler::stackPointerRegister);
+            
+            for (const RegisterAtOffset& entry : code.calleeSaveRegisters()) {
+                if (entry.reg().isGPR())
+                    jit.storePtr(entry.reg().gpr(), argFor(entry));
+                else
+                    jit.storeDouble(entry.reg().fpr(), argFor(entry));
+            }
+        }
+        
         ASSERT(block->size() >= 1);
         for (unsigned i = 0; i < block->size() - 1; ++i) {
             context.indexInBlock = i;
@@ -264,6 +274,11 @@ void generate(Code& code, CCallHelpers& jit)
     
     context.currentBlock = nullptr;
     context.indexInBlock = UINT_MAX;
+    
+    Vector<CCallHelpers::Label> entrypointLabels(code.numEntrypoints());
+    for (unsigned i = code.numEntrypoints(); i--;)
+        entrypointLabels[i] = *context.blockLabels[code.entrypoint(i).block()];
+    code.setEntrypointLabels(WTFMove(entrypointLabels));
 
     pcToOriginMap.appendItem(jit.label(), Origin());
     // FIXME: Make late paths have Origins: https://bugs.webkit.org/show_bug.cgi?id=153689
diff --git a/Source/JavaScriptCore/b3/air/AirLowerEntrySwitch.cpp b/Source/JavaScriptCore/b3/air/AirLowerEntrySwitch.cpp
new file mode 100644 (file)
index 0000000..b43ab71
--- /dev/null
@@ -0,0 +1,114 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "AirLowerEntrySwitch.h"
+
+#if ENABLE(B3_JIT)
+
+#include "AirBlockWorklist.h"
+#include "AirCode.h"
+#include "AirInstInlines.h"
+#include "AirPhaseScope.h"
+#include "B3Procedure.h"
+
+namespace JSC { namespace B3 { namespace Air {
+
+void lowerEntrySwitch(Code& code)
+{
+    PhaseScope phaseScope(code, "lowerEntrySwitch");
+    
+    // Figure out the set of blocks that should be duplicated.
+    BlockWorklist worklist;
+    for (BasicBlock* block : code) {
+        if (block->last().opcode == EntrySwitch)
+            worklist.push(block);
+    }
+    
+    // It's possible that we don't have any EntrySwitches. That's fine.
+    if (worklist.seen().isEmpty()) {
+        Vector<FrequentedBlock> entrypoints(code.proc().numEntrypoints(), FrequentedBlock(code[0]));
+        code.setEntrypoints(WTFMove(entrypoints));
+        return;
+    }
+    
+    while (BasicBlock* block = worklist.pop())
+        worklist.pushAll(block->predecessors());
+    
+    RELEASE_ASSERT(worklist.saw(code[0]));
+    
+    Vector<FrequencyClass> entrypointFrequencies(code.proc().numEntrypoints(), FrequencyClass::Rare);
+    for (BasicBlock* block : code) {
+        if (block->last().opcode != EntrySwitch)
+            continue;
+        for (unsigned entrypointIndex = code.proc().numEntrypoints(); entrypointIndex--;) {
+            entrypointFrequencies[entrypointIndex] = maxFrequency(
+                entrypointFrequencies[entrypointIndex],
+                block->successor(entrypointIndex).frequency());
+        }
+    }
+    
+    auto fixEntrySwitch = [&] (BasicBlock* block, unsigned entrypointIndex) {
+        if (block->last().opcode != EntrySwitch)
+            return;
+        FrequentedBlock target = block->successor(entrypointIndex);
+        block->last().opcode = Jump;
+        block->successors().resize(1);
+        block->successor(0) = target;
+    };
+    
+    // Now duplicate them.
+    Vector<FrequentedBlock> entrypoints;
+    entrypoints.append(FrequentedBlock(code[0], entrypointFrequencies[0]));
+    IndexMap<BasicBlock, BasicBlock*> map(code.size());
+    for (unsigned entrypointIndex = 1; entrypointIndex < code.proc().numEntrypoints(); ++entrypointIndex) {
+        map.clear();
+        for (BasicBlock* block : worklist.seen().values(code))
+            map[block] = code.addBlock(block->frequency());
+        entrypoints.append(FrequentedBlock(map[code[0]], entrypointFrequencies[entrypointIndex]));
+        for (BasicBlock* block : worklist.seen().values(code)) {
+            BasicBlock* newBlock = map[block];
+            for (const Inst& inst : *block)
+                newBlock->appendInst(inst);
+            newBlock->successors() = block->successors();
+            for (BasicBlock*& successor : newBlock->successorBlocks()) {
+                if (BasicBlock* replacement = map[successor])
+                    successor = replacement;
+            }
+            fixEntrySwitch(newBlock, entrypointIndex);
+        }
+    }
+    for (BasicBlock* block : worklist.seen().values(code))
+        fixEntrySwitch(block, 0);
+    
+    code.setEntrypoints(WTFMove(entrypoints));
+    code.resetReachability();
+}
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
+
diff --git a/Source/JavaScriptCore/b3/air/AirLowerEntrySwitch.h b/Source/JavaScriptCore/b3/air/AirLowerEntrySwitch.h
new file mode 100644 (file)
index 0000000..34215d5
--- /dev/null
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef AirLowerEntrySwitch_h
+#define AirLowerEntrySwitch_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// Converts code that seems to have one entrypoint and emulates multiple entrypoints with
+// EntrySwitch into code that really has multiple entrypoints. This is accomplished by duplicating
+// the backwards transitive closure from all EntrySwitches.
+void lowerEntrySwitch(Code&);
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
+#endif // AirLowerEntrySwitch_h
+
index a899a475330ed82c27db37822155dc77141c4f94..c982b3b40c858403cf62f94cfe87ffa7d41e1159 100644 (file)
@@ -850,6 +850,10 @@ RetDouble U:F:64 /return
 
 Oops /terminal
 
+# This is a terminal but we express it as a Custom because we don't want it to have a code
+# generator.
+custom EntrySwitch
+
 # A Shuffle is a multi-source, multi-destination move. It simultaneously does multiple moves at once.
 # The moves are specified as triplets of src, dst, and width. For example you can request a swap this
 # way:
index 3e84a0bd8a3b09a7106ff3d59f812be38ca40283..d05aadbb4b73d3545d8725e528f2a2d778b5de91 100644 (file)
@@ -81,16 +81,28 @@ Vector<BasicBlock*> blocksInOptimizedOrder(Code& code)
     SortedSuccessors sortedSuccessors;
     SortedSuccessors sortedSlowSuccessors;
     
-    fastWorklist.push(code[0]);
+    // We expect entrypoint lowering to have already happened.
+    RELEASE_ASSERT(code.numEntrypoints());
+
+    auto appendSuccessor = [&] (const FrequentedBlock& block) {
+        if (block.isRare())
+            sortedSlowSuccessors.append(block.block());
+        else
+            sortedSuccessors.append(block.block());
+    };
+    
+    // For everything but the first entrypoint, we push them in order of frequency and frequency
+    // class.
+    for (unsigned i = 1; i < code.numEntrypoints(); ++i)
+        appendSuccessor(code.entrypoint(i));
+    
+    // Always push the primary successor last so that it gets highest priority.
+    fastWorklist.push(code.entrypoint(0).block());
     
     while (BasicBlock* block = fastWorklist.pop()) {
         blocksInOrder.append(block);
-        for (FrequentedBlock& successor : block->successors()) {
-            if (successor.isRare())
-                sortedSlowSuccessors.append(successor.block());
-            else
-                sortedSuccessors.append(successor.block());
-        }
+        for (FrequentedBlock& successor : block->successors())
+            appendSuccessor(successor);
         sortedSuccessors.process(fastWorklist);
     }
 
index 05a7f25f9708f8a43b3e8ca8f1df2efe82d6480d..0a722e810a56d5455c12ad011e1375f8eb327e29 100644 (file)
@@ -60,6 +60,11 @@ bool Special::isTerminal(Inst&)
     return false;
 }
 
+bool Special::hasNonArgEffects(Inst&)
+{
+    return true;
+}
+
 bool Special::hasNonArgNonControlEffects(Inst&)
 {
     return true;
index 0bdbcb4602e13a628e18e6fd5ba02e348821976b..18726551e05bd84f283f6adf3617446c3248883d 100644 (file)
@@ -91,6 +91,9 @@ public:
     // By default, this returns false.
     virtual bool isTerminal(Inst&);
 
+    // By default, this returns true.
+    virtual bool hasNonArgEffects(Inst&);
+
     // By default, this returns true.
     virtual bool hasNonArgNonControlEffects(Inst&);
 
index 88baed7e1430e50eae605e3b579bf2660885b366..5e3419b3bba9adf5dbba701f2407495799e89897 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "AirCode.h"
 #include "AirInstInlines.h"
+#include "B3Procedure.h"
 
 namespace JSC { namespace B3 { namespace Air {
 
@@ -54,7 +55,7 @@ public:
         HashSet<StackSlot*> validSlots;
         HashSet<BasicBlock*> validBlocks;
         HashSet<Special*> validSpecials;
-
+        
         for (BasicBlock* block : m_code)
             validBlocks.add(block);
         for (StackSlot* slot : m_code.stackSlots())
@@ -63,6 +64,10 @@ public:
             validSpecials.add(special);
 
         for (BasicBlock* block : m_code) {
+            // Blocks that are entrypoints must not have predecessors.
+            if (m_code.isEntrypoint(block))
+                VALIDATE(!block->numPredecessors(), ("At entrypoint ", *block));
+            
             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
                 Inst& inst = block->at(instIndex);
                 for (Arg& arg : inst.args) {
@@ -89,6 +94,14 @@ public:
                         VALIDATE(&arg >= &inst.args[0], ("At ", arg, " in ", inst, " in ", *block));
                         VALIDATE(&arg <= &inst.args.last(), ("At ", arg, " in ", inst, " in ", *block));
                     });
+                
+                switch (inst.opcode) {
+                case EntrySwitch:
+                    VALIDATE(block->numSuccessors() == m_code.proc().numEntrypoints(), ("At ", inst, " in ", *block));
+                    break;
+                default:
+                    break;
+                }
             }
             for (BasicBlock* successor : block->successorBlocks())
                 VALIDATE(validBlocks.contains(successor), ("In ", *block));
index 94eaae3117fcc7974cc3298d9fef03cc9a062e4b..d0900a3cb2b6fca94f20b516ff2547550d8aef33 100644 (file)
@@ -1046,7 +1046,7 @@ writeH("OpcodeGenerated") {
         | opcode |
         if opcode.custom
             outp.puts "case #{opcode.name}:"
-            outp.puts "return #{opcode.name}Custom::hasNonArgNonControlEffects(*this);"
+            outp.puts "return #{opcode.name}Custom::hasNonArgEffects(*this);"
         end
     }
     outp.puts "default:"
index 6e4086097b69d27f742a2905a0492ca39a424cb7..2bd96e06bcad97d28ed273eb31ca3ad0207cd30b 100644 (file)
@@ -37,6 +37,7 @@
 #include "B3Const32Value.h"
 #include "B3ConstPtrValue.h"
 #include "B3Effects.h"
+#include "B3Generate.h"
 #include "B3LowerToAir.h"
 #include "B3MathExtras.h"
 #include "B3MemoryValue.h"
@@ -116,12 +117,18 @@ std::unique_ptr<Compilation> compile(Procedure& procedure, unsigned optLevel = 1
 }
 
 template<typename T, typename... Arguments>
-T invoke(const Compilation& code, Arguments... arguments)
+T invoke(MacroAssemblerCodePtr ptr, Arguments... arguments)
 {
-    T (*function)(Arguments...) = bitwise_cast<T(*)(Arguments...)>(code.code().executableAddress());
+    T (*function)(Arguments...) = bitwise_cast<T(*)(Arguments...)>(ptr.executableAddress());
     return function(arguments...);
 }
 
+template<typename T, typename... Arguments>
+T invoke(const Compilation& code, Arguments... arguments)
+{
+    return invoke<T>(code.code(), arguments...);
+}
+
 template<typename T, typename... Arguments>
 T compileAndRun(Procedure& procedure, Arguments... arguments)
 {
@@ -12407,6 +12414,376 @@ void testResetReachabilityDanglingReference()
     validate(proc);
 }
 
+void testEntrySwitchSimple()
+{
+    Procedure proc;
+    proc.setNumEntrypoints(3);
+    
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* one = proc.addBlock();
+    BasicBlock* two = proc.addBlock();
+    BasicBlock* three = proc.addBlock();
+    
+    root->appendNew<Value>(proc, EntrySwitch, Origin());
+    root->appendSuccessor(FrequentedBlock(one));
+    root->appendSuccessor(FrequentedBlock(two));
+    root->appendSuccessor(FrequentedBlock(three));
+    
+    one->appendNew<Value>(
+        proc, Return, Origin(),
+        one->appendNew<Value>(
+            proc, Add, Origin(),
+            one->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+            one->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1)));
+    
+    two->appendNew<Value>(
+        proc, Return, Origin(),
+        two->appendNew<Value>(
+            proc, Sub, Origin(),
+            two->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+            two->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1)));
+    
+    three->appendNew<Value>(
+        proc, Return, Origin(),
+        three->appendNew<Value>(
+            proc, Mul, Origin(),
+            three->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+            three->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1)));
+    
+    prepareForGeneration(proc);
+    
+    CCallHelpers jit(vm);
+    generate(proc, jit);
+    LinkBuffer linkBuffer(*vm, jit, nullptr);
+    CodeLocationLabel labelOne = linkBuffer.locationOf(proc.entrypointLabel(0));
+    CodeLocationLabel labelTwo = linkBuffer.locationOf(proc.entrypointLabel(1));
+    CodeLocationLabel labelThree = linkBuffer.locationOf(proc.entrypointLabel(2));
+    
+    MacroAssemblerCodeRef codeRef = FINALIZE_CODE(linkBuffer, ("testb3 compilation"));
+    
+    CHECK(invoke<int>(labelOne, 1, 2) == 3);
+    CHECK(invoke<int>(labelTwo, 1, 2) == -1);
+    CHECK(invoke<int>(labelThree, 1, 2) == 2);
+    CHECK(invoke<int>(labelOne, -1, 2) == 1);
+    CHECK(invoke<int>(labelTwo, -1, 2) == -3);
+    CHECK(invoke<int>(labelThree, -1, 2) == -2);
+}
+
+void testEntrySwitchNoEntrySwitch()
+{
+    Procedure proc;
+    proc.setNumEntrypoints(3);
+    
+    BasicBlock* root = proc.addBlock();
+    
+    root->appendNew<Value>(
+        proc, Return, Origin(),
+        root->appendNew<Value>(
+            proc, Add, Origin(),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1)));
+    
+    prepareForGeneration(proc);
+    
+    CCallHelpers jit(vm);
+    generate(proc, jit);
+    LinkBuffer linkBuffer(*vm, jit, nullptr);
+    CodeLocationLabel labelOne = linkBuffer.locationOf(proc.entrypointLabel(0));
+    CodeLocationLabel labelTwo = linkBuffer.locationOf(proc.entrypointLabel(1));
+    CodeLocationLabel labelThree = linkBuffer.locationOf(proc.entrypointLabel(2));
+    
+    MacroAssemblerCodeRef codeRef = FINALIZE_CODE(linkBuffer, ("testb3 compilation"));
+    
+    CHECK_EQ(invoke<int>(labelOne, 1, 2), 3);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2), 3);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2), 3);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2), 1);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2), 1);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2), 1);
+}
+
+void testEntrySwitchWithCommonPaths()
+{
+    Procedure proc;
+    proc.setNumEntrypoints(3);
+    
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* one = proc.addBlock();
+    BasicBlock* two = proc.addBlock();
+    BasicBlock* three = proc.addBlock();
+    BasicBlock* end = proc.addBlock();
+    
+    root->appendNew<Value>(proc, EntrySwitch, Origin());
+    root->appendSuccessor(FrequentedBlock(one));
+    root->appendSuccessor(FrequentedBlock(two));
+    root->appendSuccessor(FrequentedBlock(three));
+    
+    UpsilonValue* upsilonOne = one->appendNew<UpsilonValue>(
+        proc, Origin(),
+        one->appendNew<Value>(
+            proc, Add, Origin(),
+            one->appendNew<Value>(
+                proc, Trunc, Origin(),
+                one->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0)),
+            one->appendNew<Value>(
+                proc, Trunc, Origin(),
+                one->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1))));
+    one->appendNew<Value>(proc, Jump, Origin());
+    one->setSuccessors(FrequentedBlock(end));
+    
+    UpsilonValue* upsilonTwo = two->appendNew<UpsilonValue>(
+        proc, Origin(),
+        two->appendNew<Value>(
+            proc, Sub, Origin(),
+            two->appendNew<Value>(
+                proc, Trunc, Origin(),
+                two->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0)),
+            two->appendNew<Value>(
+                proc, Trunc, Origin(),
+                two->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1))));
+    two->appendNew<Value>(proc, Jump, Origin());
+    two->setSuccessors(FrequentedBlock(end));
+    
+    UpsilonValue* upsilonThree = three->appendNew<UpsilonValue>(
+        proc, Origin(),
+        three->appendNew<Value>(
+            proc, Mul, Origin(),
+            three->appendNew<Value>(
+                proc, Trunc, Origin(),
+                three->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0)),
+            three->appendNew<Value>(
+                proc, Trunc, Origin(),
+                three->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1))));
+    three->appendNew<Value>(proc, Jump, Origin());
+    three->setSuccessors(FrequentedBlock(end));
+    
+    Value* phi = end->appendNew<Value>(proc, Phi, Int32, Origin());
+    upsilonOne->setPhi(phi);
+    upsilonTwo->setPhi(phi);
+    upsilonThree->setPhi(phi);
+    
+    end->appendNew<Value>(
+        proc, Return, Origin(),
+        end->appendNew<Value>(
+            proc, ChillMod, Origin(),
+            phi, end->appendNew<Value>(
+                proc, Trunc, Origin(),
+                end->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2))));
+    
+    prepareForGeneration(proc);
+    
+    CCallHelpers jit(vm);
+    generate(proc, jit);
+    LinkBuffer linkBuffer(*vm, jit, nullptr);
+    CodeLocationLabel labelOne = linkBuffer.locationOf(proc.entrypointLabel(0));
+    CodeLocationLabel labelTwo = linkBuffer.locationOf(proc.entrypointLabel(1));
+    CodeLocationLabel labelThree = linkBuffer.locationOf(proc.entrypointLabel(2));
+    
+    MacroAssemblerCodeRef codeRef = FINALIZE_CODE(linkBuffer, ("testb3 compilation"));
+    
+    CHECK_EQ(invoke<int>(labelOne, 1, 2, 10), 3);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2, 10), -1);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2, 10), 2);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2, 10), 1);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2, 10), -3);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2, 10), -2);
+    CHECK_EQ(invoke<int>(labelOne, 1, 2, 2), 1);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2, 2), -1);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2, 2), 0);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2, 2), 1);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2, 2), -1);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2, 2), 0);
+    CHECK_EQ(invoke<int>(labelOne, 1, 2, 0), 0);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2, 0), 0);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2, 0), 0);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2, 0), 0);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2, 0), 0);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2, 0), 0);
+}
+
+void testEntrySwitchWithCommonPathsAndNonTrivialEntrypoint()
+{
+    Procedure proc;
+    proc.setNumEntrypoints(3);
+    
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* negate = proc.addBlock();
+    BasicBlock* dispatch = proc.addBlock();
+    BasicBlock* one = proc.addBlock();
+    BasicBlock* two = proc.addBlock();
+    BasicBlock* three = proc.addBlock();
+    BasicBlock* end = proc.addBlock();
+
+    UpsilonValue* upsilonBase = root->appendNew<UpsilonValue>(
+        proc, Origin(), root->appendNew<Value>(
+            proc, Trunc, Origin(),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0)));
+    root->appendNew<Value>(
+        proc, Branch, Origin(),
+        root->appendNew<Value>(
+            proc, BitAnd, Origin(),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR3),
+            root->appendNew<ConstPtrValue>(proc, Origin(), 0xff)));
+    root->setSuccessors(FrequentedBlock(negate), FrequentedBlock(dispatch));
+    
+    UpsilonValue* upsilonNegate = negate->appendNew<UpsilonValue>(
+        proc, Origin(),
+        negate->appendNew<Value>(
+            proc, Neg, Origin(),
+            negate->appendNew<Value>(
+                proc, Trunc, Origin(),
+                negate->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0))));
+    negate->appendNew<Value>(proc, Jump, Origin());
+    negate->setSuccessors(FrequentedBlock(dispatch));
+    
+    Value* arg0 = dispatch->appendNew<Value>(proc, Phi, Int32, Origin());
+    upsilonBase->setPhi(arg0);
+    upsilonNegate->setPhi(arg0);
+    dispatch->appendNew<Value>(proc, EntrySwitch, Origin());
+    dispatch->appendSuccessor(FrequentedBlock(one));
+    dispatch->appendSuccessor(FrequentedBlock(two));
+    dispatch->appendSuccessor(FrequentedBlock(three));
+    
+    UpsilonValue* upsilonOne = one->appendNew<UpsilonValue>(
+        proc, Origin(),
+        one->appendNew<Value>(
+            proc, Add, Origin(),
+            arg0, one->appendNew<Value>(
+                proc, Trunc, Origin(),
+                one->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1))));
+    one->appendNew<Value>(proc, Jump, Origin());
+    one->setSuccessors(FrequentedBlock(end));
+    
+    UpsilonValue* upsilonTwo = two->appendNew<UpsilonValue>(
+        proc, Origin(),
+        two->appendNew<Value>(
+            proc, Sub, Origin(),
+            arg0, two->appendNew<Value>(
+                proc, Trunc, Origin(),
+                two->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1))));
+    two->appendNew<Value>(proc, Jump, Origin());
+    two->setSuccessors(FrequentedBlock(end));
+    
+    UpsilonValue* upsilonThree = three->appendNew<UpsilonValue>(
+        proc, Origin(),
+        three->appendNew<Value>(
+            proc, Mul, Origin(),
+            arg0, three->appendNew<Value>(
+                proc, Trunc, Origin(),
+                three->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1))));
+    three->appendNew<Value>(proc, Jump, Origin());
+    three->setSuccessors(FrequentedBlock(end));
+    
+    Value* phi = end->appendNew<Value>(proc, Phi, Int32, Origin());
+    upsilonOne->setPhi(phi);
+    upsilonTwo->setPhi(phi);
+    upsilonThree->setPhi(phi);
+    
+    end->appendNew<Value>(
+        proc, Return, Origin(),
+        end->appendNew<Value>(
+            proc, ChillMod, Origin(),
+            phi, end->appendNew<Value>(
+                proc, Trunc, Origin(),
+                end->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR2))));
+    
+    prepareForGeneration(proc);
+    
+    CCallHelpers jit(vm);
+    generate(proc, jit);
+    LinkBuffer linkBuffer(*vm, jit, nullptr);
+    CodeLocationLabel labelOne = linkBuffer.locationOf(proc.entrypointLabel(0));
+    CodeLocationLabel labelTwo = linkBuffer.locationOf(proc.entrypointLabel(1));
+    CodeLocationLabel labelThree = linkBuffer.locationOf(proc.entrypointLabel(2));
+    
+    MacroAssemblerCodeRef codeRef = FINALIZE_CODE(linkBuffer, ("testb3 compilation"));
+    
+    CHECK_EQ(invoke<int>(labelOne, 1, 2, 10, false), 3);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2, 10, false), -1);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2, 10, false), 2);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2, 10, false), 1);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2, 10, false), -3);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2, 10, false), -2);
+    CHECK_EQ(invoke<int>(labelOne, 1, 2, 10, true), 1);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2, 10, true), -3);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2, 10, true), -2);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2, 10, true), 3);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2, 10, true), -1);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2, 10, true), 2);
+    CHECK_EQ(invoke<int>(labelOne, 1, 2, 2, false), 1);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2, 2, false), -1);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2, 2, false), 0);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2, 2, false), 1);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2, 2, false), -1);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2, 2, false), 0);
+    CHECK_EQ(invoke<int>(labelOne, 1, 2, 0, false), 0);
+    CHECK_EQ(invoke<int>(labelTwo, 1, 2, 0, false), 0);
+    CHECK_EQ(invoke<int>(labelThree, 1, 2, 0, false), 0);
+    CHECK_EQ(invoke<int>(labelOne, -1, 2, 0, false), 0);
+    CHECK_EQ(invoke<int>(labelTwo, -1, 2, 0, false), 0);
+    CHECK_EQ(invoke<int>(labelThree, -1, 2, 0, false), 0);
+}
+
+void testEntrySwitchLoop()
+{
+    // This is a completely absurd use of EntrySwitch, where it impacts the loop condition. This
+    // should cause duplication of either nearly the entire Procedure. At time of writing, we ended
+    // up duplicating all of it, which is fine. It's important to test this case, to make sure that
+    // the duplication algorithm can handle interesting control flow.
+    
+    Procedure proc;
+    proc.setNumEntrypoints(2);
+    
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* loopHeader = proc.addBlock();
+    BasicBlock* loopFooter = proc.addBlock();
+    BasicBlock* end = proc.addBlock();
+
+    UpsilonValue* initialValue = root->appendNew<UpsilonValue>(
+        proc, Origin(), root->appendNew<Value>(
+            proc, Trunc, Origin(),
+            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0)));
+    root->appendNew<Value>(proc, Jump, Origin());
+    root->setSuccessors(loopHeader);
+    
+    Value* valueInLoop = loopHeader->appendNew<Value>(proc, Phi, Int32, Origin());
+    initialValue->setPhi(valueInLoop);
+    Value* newValue = loopHeader->appendNew<Value>(
+        proc, Add, Origin(), valueInLoop,
+        loopHeader->appendNew<Const32Value>(proc, Origin(), 1));
+    loopHeader->appendNew<Value>(proc, EntrySwitch, Origin());
+    loopHeader->appendSuccessor(end);
+    loopHeader->appendSuccessor(loopFooter);
+    
+    loopFooter->appendNew<UpsilonValue>(proc, Origin(), newValue, valueInLoop);
+    loopFooter->appendNew<Value>(
+        proc, Branch, Origin(),
+        loopFooter->appendNew<Value>(
+            proc, LessThan, Origin(), newValue,
+            loopFooter->appendNew<Const32Value>(proc, Origin(), 100)));
+    loopFooter->setSuccessors(loopHeader, end);
+    
+    end->appendNew<Value>(proc, Return, Origin(), newValue);
+    
+    prepareForGeneration(proc);
+    
+    CCallHelpers jit(vm);
+    generate(proc, jit);
+    LinkBuffer linkBuffer(*vm, jit, nullptr);
+    CodeLocationLabel labelOne = linkBuffer.locationOf(proc.entrypointLabel(0));
+    CodeLocationLabel labelTwo = linkBuffer.locationOf(proc.entrypointLabel(1));
+    
+    MacroAssemblerCodeRef codeRef = FINALIZE_CODE(linkBuffer, ("testb3 compilation"));
+
+    CHECK(invoke<int>(labelOne, 0) == 1);
+    CHECK(invoke<int>(labelOne, 42) == 43);
+    CHECK(invoke<int>(labelOne, 1000) == 1001);
+    
+    CHECK(invoke<int>(labelTwo, 0) == 100);
+    CHECK(invoke<int>(labelTwo, 42) == 100);
+    CHECK(invoke<int>(labelTwo, 1000) == 1001);
+}
+
 void testSomeEarlyRegister()
 {
     auto run = [&] (bool succeed) {
@@ -12503,8 +12880,6 @@ double negativeZero()
     return -zero();
 }
 
-
-
 #define RUN(test) do {                          \
         if (!shouldRun(#test))                  \
             break;                              \
@@ -13898,6 +14273,13 @@ void run(const char* filter)
     RUN(testInterpreter());
     RUN(testReduceStrengthCheckBottomUseInAnotherBlock());
     RUN(testResetReachabilityDanglingReference());
+    
+    RUN(testEntrySwitchSimple());
+    RUN(testEntrySwitchNoEntrySwitch());
+    RUN(testEntrySwitchWithCommonPaths());
+    RUN(testEntrySwitchWithCommonPathsAndNonTrivialEntrypoint());
+    RUN(testEntrySwitchLoop());
+
     RUN(testSomeEarlyRegister());
     
     RUN(testBranchBitAndImmFusion(Identity, Int64, 1, Air::BranchTest32, Air::Arg::Tmp));
index d82c375066cc8fa86bd7102675db07ae0587d451..a34a5ac4b61ed96651afbdcb90137b6943161556 100644 (file)
@@ -1,3 +1,16 @@
+2016-07-24  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should support multiple entrypoints
+        https://bugs.webkit.org/show_bug.cgi?id=159391
+
+        Reviewed by Saam Barati.
+
+        * wtf/GraphNodeWorklist.h: Expose some handy functionality.
+        (WTF::GraphNodeWorklist::pop):
+        (WTF::GraphNodeWorklist::saw):
+        (WTF::GraphNodeWorklist::seen):
+        * wtf/VectorTraits.h: Fix a bug! Otherwise filling a vector of byte-sized enum classes doesn't work.
+
 2016-07-21  Myles C. Maxfield  <mmaxfield@apple.com>
 
         [macOS] Caret placement occurs in the middle of new emoji group candidates
index d4f71374cfcbe633911f44e4318cb2f630017bdf..e2ab0781c9594736dbe33dca52ea7d32ec6abac7 100644 (file)
@@ -63,6 +63,8 @@ public:
     }
 
     bool saw(Node node) { return m_seen.contains(node); }
+    
+    const Set& seen() const { return m_seen; }
 
 private:
     Set m_seen;
index 94db8cab7d9fd068db1fb4845142b1c1e34cefd1..b3fb077bbff73f5633e15be33202a4221a8e7604 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2006, 2007, 2008 Apple Inc. All rights reserved.
+ * Copyright (C) 2006, 2007, 2008, 2016 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -25,6 +25,7 @@
 #include <wtf/RefPtr.h>
 #include <utility>
 #include <memory>
+#include <type_traits>
 
 namespace WTF {
 
@@ -51,7 +52,7 @@ namespace WTF {
         static const bool canInitializeWithMemset = false;
         static const bool canMoveWithMemcpy = true;
         static const bool canCopyWithMemcpy = true;
-        static const bool canFillWithMemset = sizeof(T) == sizeof(char);
+        static const bool canFillWithMemset = sizeof(T) == sizeof(char) && std::is_integral<T>::value;
         static const bool canCompareWithMemcmp = true;
     };
 
index 5303bdfe2ca4c3da71ac19bbbd21776d4d426aa2..dbdcf128564ae77c51d03f6d961697c54c6a22ce 100644 (file)
@@ -1,3 +1,16 @@
+2016-07-24  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should support multiple entrypoints
+        https://bugs.webkit.org/show_bug.cgi?id=159391
+
+        Reviewed by Saam Barati.
+        
+        Update some statements about ControlValue (which doesn't exist anymore) and add a blurb
+        about EntrySwitch.
+
+        * docs/b3/index.html:
+        * docs/b3/intermediate-representation.html:
+
 2016-07-20  Frederic Wang  <fwang@igalia.com>
 
         Unreviewed, new demo files for an up-coming blog post.
index dd41a5a2e69d2e52ae73cf8d8047c98d8f90ad0c..a433f6630d3b17c6919e1341e991c2ba3d920015 100644 (file)
@@ -33,7 +33,7 @@
     <pre><code>// Create a Procedure that holds our code.
 Procedure proc;
 BasicBlock* root = proc.addBlock();
-root->appendNew&lt;ControlValue&gt;(
+root->appendNew&lt;Value&gt;(
     proc, Return, Origin(),
     root->appendNew&lt;Value&gt;(
         proc, Add, Origin(),
index df009a774bffc4ceed9faf7527e5ce3bfdaedf5c..fa8385c8206f4cf5539329bef2a85db77d6204a4 100644 (file)
@@ -541,32 +541,69 @@ patchpoint->setGenerator(
         with Upsilon.</dd>
 
       <dt>Void Jump(takenBlock)</dt>
-      <dd>Jumps to takenBlock.  This is a ControlValue, so it must appear at the end of the
-        basic block.</dd>
+      <dd>Jumps to takenBlock.  This must appear at the end of the basic block. The basic block
+        must have exactly one successor.</dd>
 
       <dt>Void Branch(T, takenBlock, notTakenBlock)</dt>
       <dd>Works for T = Int32 or T = Int64.  Branches on the child.  If the child is non-zero,
-        it branches to the takenBlock.  Otherwise it branches to the notTakenBlock.  Must use
-        the ControlValue class.  Must appear at the end of the basic block.</dd>
+        it branches to the takenBlock.  Otherwise it branches to the notTakenBlock.  Must appear
+        at the end of the basic block. The block must have exactly two successors.</dd>
 
       <dt>Void Switch(T, cases...)</dt>
       <dd>Works for T = Int32 or T = Int64.  Switches on the child.  Contains a list of switch
         cases.  Each switch case has an integer constant and a target block.  The switch value
         also contains a fall-through target in case the child has a value that wasn't mentioned
         in the cases list.  Must use the SwitchValue class.  Must appear at the end of the basic
-        block.</dd>
+        block. The block must have one successor for each case, plus a successor for the
+        fall-through (default) case. You can manage the successors of a block containing a Switch
+        using API in SwitchValue, like SwitchValue::appendCase() and
+        SwitchValue::setFallThrough().</dd>
+      
+      <dt>Void EntrySwitch()</dt>
+      <dd>
+        <p>B3 supports multiple procedure entrypoints. The way you create multiple entrypoints is
+          by placing an EntrySwitch at the end of the root block. The root block must then have a
+          successor for each entrypoint. Additionally, you must tell the Procedure how many
+          entrypoints you want. For example:</p>
+        <pre><code>Procedure proc;
+proc.setNumEntrypoints(3);
+BasicBlock* root = proc.addBlock();
+BasicBlock* firstEntrypoint = proc.addBlock();
+BasicBlock* secondEntrypoint = proc.addBlock();
+BasicBlock* thirdEntrypoint = proc.addBlock();
+root->appendNew&lt;Value&gt;(proc, EntrySwitch, Origin());
+root->appendSuccessor(firstEntrypoint);
+root->appendSuccessor(secondEntrypoint);
+root->appendSuccessor(thirdEntrypoint);</code></pre>
+        <p>This is the canonical way to use EntrySwitch, however the semantics are flexible enough
+          to allow its use anywhere in the control flow graph. You can have an arbitrary number of
+          EntrySwitches. This flexibility ensures that EntrySwitch works even when B3 does
+          transformations that move code above the EntrySwitch, duplicate the EntrySwitch itself,
+          or do any number of other unexpected things.</p>
+        <p>EntrySwitch behaves as if each Procedure has a variable called Entry. Each physical
+          entrypoint sets Entry to the index of that entrypoint (so 0, 1, or 2, above) and jumps to
+          the root block. EntrySwitch is just a switch on the Entry variable. Transformations over
+          code that uses EntrySwitch are valid so long as they don't change the procedure's
+          behavior under these semantics.</p>
+        <p>EntrySwitch is implemented without any actual variables or switching. Instead, all code
+          that lies on some path from the root block to some EntrySwitch is cloned for each
+          entrypoint. This lowering is done as a very late phase in Air, so most of the compiler
+          does not have to know anything about entrypoints. Most of the compiler treats EntrySwitch
+          as an opaque control flow construct. EntrySwitch lowering is allowed to clone an
+          arbitrary amount of code. However, normal uses of EntrySwitch will place it at the end of
+          an empty root block and B3 will only hoist a handful of things above EntrySwitch. This
+          leads to only a small amount of cloned code in practice.</p>
+      </dd>
 
       <dt>Void Return(T)</dt>
       <dd>Works for any type except Void.  Returns the given value and terminates the procedure.
-        This is a ControlValue, but it must have an empty successors list.  Must appear at the
-        end of the basic block.</dd>
+        Must appear at the end of the basic block. The block must have zero successors.</dd>
 
       <dt>Void Oops()</dt>
       <dd>Indicates unreachable code.  This may be implemented as either a trap or as a bare
-        fall-through, since B3 is allowed to assume that this will never be reached.  This is a
-        ControlValue, but it must have an empty successors list.  Must appear at the end of the
-        basic block.  Note that we also use the Oops opcode to mean "no such opcode" in some B3
-        transformations.</dd>
+        fall-through, since B3 is allowed to assume that this will never be reached.  Must appear
+        at the end of the basic block.  The block must have zero successors. Note that we also use
+        the Oops opcode to mean "no such opcode" in some B3 transformations.</dd>
     </dl>
 
   </div>