B3 should have basic path specialization
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jan 2016 03:12:55 +0000 (03:12 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jan 2016 03:12:55 +0000 (03:12 +0000)
https://bugs.webkit.org/show_bug.cgi?id=153200

Reviewed by Benjamin Poulain.

Source/JavaScriptCore:

This adds two different kind of path specializations:

- Check(Select) where the Select results are constants is specialized into a Branch
  instead of a Select and duplicated paths where the results of the Select are folded.

- Tail duplication. A jump to a small block causes the block's contents to be copied over
  the Jump.

Both optimizations required being able to clone Values. We can now do that using
proc.clone(value).

Check(Select) specialization needed some utilities for walking graphs of Values.

Tail duplication needed SSA fixup, so I added a way to demote values to anonymous stack
slots (B3's equivalent of non-SSA variables) and a way to "fix SSA", i.e. to allocate
anonymous stack slots to SSA values along with an optimal Phi graph.

This is a big speed-up on Octane/deltablue. It's a 2.2% speed-up on Octane overall.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3ArgumentRegValue.cpp:
(JSC::B3::ArgumentRegValue::dumpMeta):
(JSC::B3::ArgumentRegValue::cloneImpl):
* b3/B3ArgumentRegValue.h:
* b3/B3BasicBlock.cpp:
(JSC::B3::BasicBlock::append):
(JSC::B3::BasicBlock::appendNonTerminal):
(JSC::B3::BasicBlock::removeLast):
* b3/B3BasicBlock.h:
(JSC::B3::BasicBlock::values):
* b3/B3BasicBlockInlines.h:
(JSC::B3::BasicBlock::appendNew):
(JSC::B3::BasicBlock::appendNewNonTerminal):
(JSC::B3::BasicBlock::replaceLastWithNew):
* b3/B3BlockInsertionSet.h:
* b3/B3BreakCriticalEdges.cpp: Added.
(JSC::B3::breakCriticalEdges):
* b3/B3BreakCriticalEdges.h: Added.
* b3/B3CCallValue.cpp:
(JSC::B3::CCallValue::~CCallValue):
(JSC::B3::CCallValue::cloneImpl):
* b3/B3CCallValue.h:
* b3/B3CheckValue.cpp:
(JSC::B3::CheckValue::convertToAdd):
(JSC::B3::CheckValue::cloneImpl):
(JSC::B3::CheckValue::CheckValue):
* b3/B3CheckValue.h:
* b3/B3Const32Value.cpp:
(JSC::B3::Const32Value::dumpMeta):
(JSC::B3::Const32Value::cloneImpl):
* b3/B3Const32Value.h:
* b3/B3Const64Value.cpp:
(JSC::B3::Const64Value::dumpMeta):
(JSC::B3::Const64Value::cloneImpl):
* b3/B3Const64Value.h:
* b3/B3ConstDoubleValue.cpp:
(JSC::B3::ConstDoubleValue::dumpMeta):
(JSC::B3::ConstDoubleValue::cloneImpl):
* b3/B3ConstDoubleValue.h:
* b3/B3ConstFloatValue.cpp:
(JSC::B3::ConstFloatValue::dumpMeta):
(JSC::B3::ConstFloatValue::cloneImpl):
* b3/B3ConstFloatValue.h:
* b3/B3ControlValue.cpp:
(JSC::B3::ControlValue::dumpMeta):
(JSC::B3::ControlValue::cloneImpl):
* b3/B3ControlValue.h:
* b3/B3DuplicateTails.cpp: Added.
(JSC::B3::duplicateTails):
* b3/B3DuplicateTails.h: Added.
* b3/B3FixSSA.cpp: Added.
(JSC::B3::demoteValues):
(JSC::B3::fixSSA):
* b3/B3FixSSA.h: Added.
* b3/B3Generate.cpp:
(JSC::B3::generateToAir):
* b3/B3IndexSet.h:
(JSC::B3::IndexSet::Iterable::Iterable):
(JSC::B3::IndexSet::values):
(JSC::B3::IndexSet::indices):
* b3/B3InsertionSet.cpp:
(JSC::B3::InsertionSet::insertIntConstant):
(JSC::B3::InsertionSet::insertBottom):
(JSC::B3::InsertionSet::execute):
* b3/B3InsertionSet.h:
* b3/B3LowerToAir.cpp:
(JSC::B3::Air::LowerToAir::run):
(JSC::B3::Air::LowerToAir::tmp):
* b3/B3MemoryValue.cpp:
(JSC::B3::MemoryValue::dumpMeta):
(JSC::B3::MemoryValue::cloneImpl):
* b3/B3MemoryValue.h:
* b3/B3OriginDump.cpp: Added.
(JSC::B3::OriginDump::dump):
* b3/B3OriginDump.h:
(JSC::B3::OriginDump::OriginDump):
(JSC::B3::OriginDump::dump): Deleted.
* b3/B3PatchpointValue.cpp:
(JSC::B3::PatchpointValue::dumpMeta):
(JSC::B3::PatchpointValue::cloneImpl):
(JSC::B3::PatchpointValue::PatchpointValue):
* b3/B3PatchpointValue.h:
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::addBlock):
(JSC::B3::Procedure::clone):
(JSC::B3::Procedure::addIntConstant):
(JSC::B3::Procedure::addBottom):
(JSC::B3::Procedure::addBoolConstant):
(JSC::B3::Procedure::deleteValue):
* b3/B3Procedure.h:
* b3/B3ReduceStrength.cpp:
* b3/B3SSACalculator.cpp: Added.
(JSC::B3::SSACalculator::Variable::dump):
(JSC::B3::SSACalculator::Variable::dumpVerbose):
(JSC::B3::SSACalculator::Def::dump):
(JSC::B3::SSACalculator::SSACalculator):
(JSC::B3::SSACalculator::~SSACalculator):
(JSC::B3::SSACalculator::reset):
(JSC::B3::SSACalculator::newVariable):
(JSC::B3::SSACalculator::newDef):
(JSC::B3::SSACalculator::nonLocalReachingDef):
(JSC::B3::SSACalculator::reachingDefAtTail):
(JSC::B3::SSACalculator::dump):
* b3/B3SSACalculator.h: Added.
(JSC::B3::SSACalculator::Variable::index):
(JSC::B3::SSACalculator::Variable::Variable):
(JSC::B3::SSACalculator::Def::variable):
(JSC::B3::SSACalculator::Def::block):
(JSC::B3::SSACalculator::Def::value):
(JSC::B3::SSACalculator::Def::Def):
(JSC::B3::SSACalculator::variable):
(JSC::B3::SSACalculator::computePhis):
(JSC::B3::SSACalculator::phisForBlock):
(JSC::B3::SSACalculator::reachingDefAtHead):
* b3/B3StackSlotKind.h:
* b3/B3StackSlotValue.cpp:
(JSC::B3::StackSlotValue::dumpMeta):
(JSC::B3::StackSlotValue::cloneImpl):
* b3/B3StackSlotValue.h:
* b3/B3SwitchValue.cpp:
(JSC::B3::SwitchValue::dumpMeta):
(JSC::B3::SwitchValue::cloneImpl):
(JSC::B3::SwitchValue::SwitchValue):
* b3/B3SwitchValue.h:
* b3/B3UpsilonValue.cpp:
(JSC::B3::UpsilonValue::dumpMeta):
(JSC::B3::UpsilonValue::cloneImpl):
* b3/B3UpsilonValue.h:
* b3/B3Validate.cpp:
* b3/B3Value.cpp:
(JSC::B3::Value::replaceWithNop):
(JSC::B3::Value::replaceWithPhi):
(JSC::B3::Value::dump):
(JSC::B3::Value::cloneImpl):
(JSC::B3::Value::dumpChildren):
(JSC::B3::Value::deepDump):
* b3/B3Value.h:
(JSC::B3::DeepValueDump::DeepValueDump):
(JSC::B3::DeepValueDump::dump):
(JSC::B3::deepDump):
* b3/B3ValueInlines.h:
(JSC::B3::Value::asNumber):
(JSC::B3::Value::walk):
* b3/B3ValueKey.cpp:
(JSC::B3::ValueKey::intConstant):
(JSC::B3::ValueKey::dump):
* b3/B3ValueKey.h:
(JSC::B3::ValueKey::ValueKey):
(JSC::B3::ValueKey::opcode):
(JSC::B3::ValueKey::type):
(JSC::B3::ValueKey::childIndex):
* b3/air/AirCode.h:
(JSC::B3::Air::Code::forAllTmps):
(JSC::B3::Air::Code::isFastTmp):
* b3/air/AirIteratedRegisterCoalescing.cpp:
* b3/air/AirUseCounts.h:
(JSC::B3::Air::UseCounts::UseCounts):
(JSC::B3::Air::UseCounts::operator[]):
(JSC::B3::Air::UseCounts::dump):
* b3/testb3.cpp:
(JSC::B3::testSelectInvert):
(JSC::B3::testCheckSelect):
(JSC::B3::testCheckSelectCheckSelect):
(JSC::B3::testPowDoubleByIntegerLoop):
(JSC::B3::run):
* runtime/Options.h:

Source/WTF:

* wtf/GraphNodeWorklist.h:
(WTF::GraphNodeWorklist::push):
(WTF::GraphNodeWorklist::pushAll):
(WTF::GraphNodeWorklist::isEmpty):
(WTF::GraphNodeWorklist::notEmpty):

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

68 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3ArgumentRegValue.cpp
Source/JavaScriptCore/b3/B3ArgumentRegValue.h
Source/JavaScriptCore/b3/B3BasicBlock.cpp
Source/JavaScriptCore/b3/B3BasicBlock.h
Source/JavaScriptCore/b3/B3BasicBlockInlines.h
Source/JavaScriptCore/b3/B3BlockInsertionSet.h
Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3BreakCriticalEdges.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3CCallValue.cpp
Source/JavaScriptCore/b3/B3CCallValue.h
Source/JavaScriptCore/b3/B3CheckValue.cpp
Source/JavaScriptCore/b3/B3CheckValue.h
Source/JavaScriptCore/b3/B3Const32Value.cpp
Source/JavaScriptCore/b3/B3Const32Value.h
Source/JavaScriptCore/b3/B3Const64Value.cpp
Source/JavaScriptCore/b3/B3Const64Value.h
Source/JavaScriptCore/b3/B3ConstDoubleValue.cpp
Source/JavaScriptCore/b3/B3ConstDoubleValue.h
Source/JavaScriptCore/b3/B3ConstFloatValue.cpp
Source/JavaScriptCore/b3/B3ConstFloatValue.h
Source/JavaScriptCore/b3/B3ControlValue.cpp
Source/JavaScriptCore/b3/B3ControlValue.h
Source/JavaScriptCore/b3/B3DuplicateTails.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3DuplicateTails.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3FixSSA.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3FixSSA.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3FoldPathConstants.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3FoldPathConstants.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3Generate.cpp
Source/JavaScriptCore/b3/B3IndexSet.h
Source/JavaScriptCore/b3/B3InsertionSet.cpp
Source/JavaScriptCore/b3/B3InsertionSet.h
Source/JavaScriptCore/b3/B3LowerToAir.cpp
Source/JavaScriptCore/b3/B3MemoryValue.cpp
Source/JavaScriptCore/b3/B3MemoryValue.h
Source/JavaScriptCore/b3/B3OriginDump.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3OriginDump.h
Source/JavaScriptCore/b3/B3PatchpointValue.cpp
Source/JavaScriptCore/b3/B3PatchpointValue.h
Source/JavaScriptCore/b3/B3Procedure.cpp
Source/JavaScriptCore/b3/B3Procedure.h
Source/JavaScriptCore/b3/B3ReduceStrength.cpp
Source/JavaScriptCore/b3/B3SSACalculator.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3SSACalculator.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3StackSlotKind.h
Source/JavaScriptCore/b3/B3StackSlotValue.cpp
Source/JavaScriptCore/b3/B3StackSlotValue.h
Source/JavaScriptCore/b3/B3SwitchValue.cpp
Source/JavaScriptCore/b3/B3SwitchValue.h
Source/JavaScriptCore/b3/B3UpsilonValue.cpp
Source/JavaScriptCore/b3/B3UpsilonValue.h
Source/JavaScriptCore/b3/B3Validate.cpp
Source/JavaScriptCore/b3/B3Value.cpp
Source/JavaScriptCore/b3/B3Value.h
Source/JavaScriptCore/b3/B3ValueInlines.h
Source/JavaScriptCore/b3/B3ValueKey.cpp
Source/JavaScriptCore/b3/B3ValueKey.h
Source/JavaScriptCore/b3/air/AirCode.h
Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp
Source/JavaScriptCore/b3/air/AirUseCounts.h
Source/JavaScriptCore/b3/testb3.cpp
Source/JavaScriptCore/runtime/Options.h
Source/WTF/ChangeLog
Source/WTF/wtf/GraphNodeWorklist.h
Tools/Scripts/display-profiler-output

index a18593a..ae7c41a 100644 (file)
@@ -104,6 +104,7 @@ set(JavaScriptCore_SOURCES
     b3/B3ArgumentRegValue.cpp
     b3/B3BasicBlock.cpp
     b3/B3BlockInsertionSet.cpp
+    b3/B3BreakCriticalEdges.cpp
     b3/B3CCallValue.cpp
     b3/B3CheckSpecial.cpp
     b3/B3CheckValue.cpp
@@ -117,7 +118,9 @@ set(JavaScriptCore_SOURCES
     b3/B3ConstrainedValue.cpp
     b3/B3ControlValue.cpp
     b3/B3DataSection.cpp
+    b3/B3DuplicateTails.cpp
     b3/B3Effects.cpp
+    b3/B3FixSSA.cpp
     b3/B3FrequencyClass.cpp
     b3/B3Generate.cpp
     b3/B3HeapRange.cpp
@@ -132,6 +135,7 @@ set(JavaScriptCore_SOURCES
     b3/B3OpaqueByproducts.cpp
     b3/B3Opcode.cpp
     b3/B3Origin.cpp
+    b3/B3OriginDump.cpp
     b3/B3PatchpointSpecial.cpp
     b3/B3PatchpointValue.cpp
     b3/B3PhaseScope.cpp
@@ -139,6 +143,7 @@ set(JavaScriptCore_SOURCES
     b3/B3Procedure.cpp
     b3/B3ReduceDoubleToFloat.cpp
     b3/B3ReduceStrength.cpp
+    b3/B3SSACalculator.cpp
     b3/B3StackmapGenerationParams.cpp
     b3/B3StackmapSpecial.cpp
     b3/B3StackmapValue.cpp
index 0561258..f61d6b7 100644 (file)
@@ -1,3 +1,198 @@
+2016-01-19  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should have basic path specialization
+        https://bugs.webkit.org/show_bug.cgi?id=153200
+
+        Reviewed by Benjamin Poulain.
+
+        This adds two different kind of path specializations:
+
+        - Check(Select) where the Select results are constants is specialized into a Branch
+          instead of a Select and duplicated paths where the results of the Select are folded.
+
+        - Tail duplication. A jump to a small block causes the block's contents to be copied over
+          the Jump.
+
+        Both optimizations required being able to clone Values. We can now do that using
+        proc.clone(value).
+
+        Check(Select) specialization needed some utilities for walking graphs of Values.
+
+        Tail duplication needed SSA fixup, so I added a way to demote values to anonymous stack
+        slots (B3's equivalent of non-SSA variables) and a way to "fix SSA", i.e. to allocate
+        anonymous stack slots to SSA values along with an optimal Phi graph.
+
+        This is a big speed-up on Octane/deltablue. It's a 2.2% speed-up on Octane overall.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * b3/B3ArgumentRegValue.cpp:
+        (JSC::B3::ArgumentRegValue::dumpMeta):
+        (JSC::B3::ArgumentRegValue::cloneImpl):
+        * b3/B3ArgumentRegValue.h:
+        * b3/B3BasicBlock.cpp:
+        (JSC::B3::BasicBlock::append):
+        (JSC::B3::BasicBlock::appendNonTerminal):
+        (JSC::B3::BasicBlock::removeLast):
+        * b3/B3BasicBlock.h:
+        (JSC::B3::BasicBlock::values):
+        * b3/B3BasicBlockInlines.h:
+        (JSC::B3::BasicBlock::appendNew):
+        (JSC::B3::BasicBlock::appendNewNonTerminal):
+        (JSC::B3::BasicBlock::replaceLastWithNew):
+        * b3/B3BlockInsertionSet.h:
+        * b3/B3BreakCriticalEdges.cpp: Added.
+        (JSC::B3::breakCriticalEdges):
+        * b3/B3BreakCriticalEdges.h: Added.
+        * b3/B3CCallValue.cpp:
+        (JSC::B3::CCallValue::~CCallValue):
+        (JSC::B3::CCallValue::cloneImpl):
+        * b3/B3CCallValue.h:
+        * b3/B3CheckValue.cpp:
+        (JSC::B3::CheckValue::convertToAdd):
+        (JSC::B3::CheckValue::cloneImpl):
+        (JSC::B3::CheckValue::CheckValue):
+        * b3/B3CheckValue.h:
+        * b3/B3Const32Value.cpp:
+        (JSC::B3::Const32Value::dumpMeta):
+        (JSC::B3::Const32Value::cloneImpl):
+        * b3/B3Const32Value.h:
+        * b3/B3Const64Value.cpp:
+        (JSC::B3::Const64Value::dumpMeta):
+        (JSC::B3::Const64Value::cloneImpl):
+        * b3/B3Const64Value.h:
+        * b3/B3ConstDoubleValue.cpp:
+        (JSC::B3::ConstDoubleValue::dumpMeta):
+        (JSC::B3::ConstDoubleValue::cloneImpl):
+        * b3/B3ConstDoubleValue.h:
+        * b3/B3ConstFloatValue.cpp:
+        (JSC::B3::ConstFloatValue::dumpMeta):
+        (JSC::B3::ConstFloatValue::cloneImpl):
+        * b3/B3ConstFloatValue.h:
+        * b3/B3ControlValue.cpp:
+        (JSC::B3::ControlValue::dumpMeta):
+        (JSC::B3::ControlValue::cloneImpl):
+        * b3/B3ControlValue.h:
+        * b3/B3DuplicateTails.cpp: Added.
+        (JSC::B3::duplicateTails):
+        * b3/B3DuplicateTails.h: Added.
+        * b3/B3FixSSA.cpp: Added.
+        (JSC::B3::demoteValues):
+        (JSC::B3::fixSSA):
+        * b3/B3FixSSA.h: Added.
+        * b3/B3Generate.cpp:
+        (JSC::B3::generateToAir):
+        * b3/B3IndexSet.h:
+        (JSC::B3::IndexSet::Iterable::Iterable):
+        (JSC::B3::IndexSet::values):
+        (JSC::B3::IndexSet::indices):
+        * b3/B3InsertionSet.cpp:
+        (JSC::B3::InsertionSet::insertIntConstant):
+        (JSC::B3::InsertionSet::insertBottom):
+        (JSC::B3::InsertionSet::execute):
+        * b3/B3InsertionSet.h:
+        * b3/B3LowerToAir.cpp:
+        (JSC::B3::Air::LowerToAir::run):
+        (JSC::B3::Air::LowerToAir::tmp):
+        * b3/B3MemoryValue.cpp:
+        (JSC::B3::MemoryValue::dumpMeta):
+        (JSC::B3::MemoryValue::cloneImpl):
+        * b3/B3MemoryValue.h:
+        * b3/B3OriginDump.cpp: Added.
+        (JSC::B3::OriginDump::dump):
+        * b3/B3OriginDump.h:
+        (JSC::B3::OriginDump::OriginDump):
+        (JSC::B3::OriginDump::dump): Deleted.
+        * b3/B3PatchpointValue.cpp:
+        (JSC::B3::PatchpointValue::dumpMeta):
+        (JSC::B3::PatchpointValue::cloneImpl):
+        (JSC::B3::PatchpointValue::PatchpointValue):
+        * b3/B3PatchpointValue.h:
+        * b3/B3Procedure.cpp:
+        (JSC::B3::Procedure::addBlock):
+        (JSC::B3::Procedure::clone):
+        (JSC::B3::Procedure::addIntConstant):
+        (JSC::B3::Procedure::addBottom):
+        (JSC::B3::Procedure::addBoolConstant):
+        (JSC::B3::Procedure::deleteValue):
+        * b3/B3Procedure.h:
+        * b3/B3ReduceStrength.cpp:
+        * b3/B3SSACalculator.cpp: Added.
+        (JSC::B3::SSACalculator::Variable::dump):
+        (JSC::B3::SSACalculator::Variable::dumpVerbose):
+        (JSC::B3::SSACalculator::Def::dump):
+        (JSC::B3::SSACalculator::SSACalculator):
+        (JSC::B3::SSACalculator::~SSACalculator):
+        (JSC::B3::SSACalculator::reset):
+        (JSC::B3::SSACalculator::newVariable):
+        (JSC::B3::SSACalculator::newDef):
+        (JSC::B3::SSACalculator::nonLocalReachingDef):
+        (JSC::B3::SSACalculator::reachingDefAtTail):
+        (JSC::B3::SSACalculator::dump):
+        * b3/B3SSACalculator.h: Added.
+        (JSC::B3::SSACalculator::Variable::index):
+        (JSC::B3::SSACalculator::Variable::Variable):
+        (JSC::B3::SSACalculator::Def::variable):
+        (JSC::B3::SSACalculator::Def::block):
+        (JSC::B3::SSACalculator::Def::value):
+        (JSC::B3::SSACalculator::Def::Def):
+        (JSC::B3::SSACalculator::variable):
+        (JSC::B3::SSACalculator::computePhis):
+        (JSC::B3::SSACalculator::phisForBlock):
+        (JSC::B3::SSACalculator::reachingDefAtHead):
+        * b3/B3StackSlotKind.h:
+        * b3/B3StackSlotValue.cpp:
+        (JSC::B3::StackSlotValue::dumpMeta):
+        (JSC::B3::StackSlotValue::cloneImpl):
+        * b3/B3StackSlotValue.h:
+        * b3/B3SwitchValue.cpp:
+        (JSC::B3::SwitchValue::dumpMeta):
+        (JSC::B3::SwitchValue::cloneImpl):
+        (JSC::B3::SwitchValue::SwitchValue):
+        * b3/B3SwitchValue.h:
+        * b3/B3UpsilonValue.cpp:
+        (JSC::B3::UpsilonValue::dumpMeta):
+        (JSC::B3::UpsilonValue::cloneImpl):
+        * b3/B3UpsilonValue.h:
+        * b3/B3Validate.cpp:
+        * b3/B3Value.cpp:
+        (JSC::B3::Value::replaceWithNop):
+        (JSC::B3::Value::replaceWithPhi):
+        (JSC::B3::Value::dump):
+        (JSC::B3::Value::cloneImpl):
+        (JSC::B3::Value::dumpChildren):
+        (JSC::B3::Value::deepDump):
+        * b3/B3Value.h:
+        (JSC::B3::DeepValueDump::DeepValueDump):
+        (JSC::B3::DeepValueDump::dump):
+        (JSC::B3::deepDump):
+        * b3/B3ValueInlines.h:
+        (JSC::B3::Value::asNumber):
+        (JSC::B3::Value::walk):
+        * b3/B3ValueKey.cpp:
+        (JSC::B3::ValueKey::intConstant):
+        (JSC::B3::ValueKey::dump):
+        * b3/B3ValueKey.h:
+        (JSC::B3::ValueKey::ValueKey):
+        (JSC::B3::ValueKey::opcode):
+        (JSC::B3::ValueKey::type):
+        (JSC::B3::ValueKey::childIndex):
+        * b3/air/AirCode.h:
+        (JSC::B3::Air::Code::forAllTmps):
+        (JSC::B3::Air::Code::isFastTmp):
+        * b3/air/AirIteratedRegisterCoalescing.cpp:
+        * b3/air/AirUseCounts.h:
+        (JSC::B3::Air::UseCounts::UseCounts):
+        (JSC::B3::Air::UseCounts::operator[]):
+        (JSC::B3::Air::UseCounts::dump):
+        * b3/testb3.cpp:
+        (JSC::B3::testSelectInvert):
+        (JSC::B3::testCheckSelect):
+        (JSC::B3::testCheckSelectCheckSelect):
+        (JSC::B3::testPowDoubleByIntegerLoop):
+        (JSC::B3::run):
+        * runtime/Options.h:
+
 2016-01-20  Benjamin Poulain  <bpoulain@apple.com>
 
         [JSC] Fix a typo in the Air definition of CeilDouble/CeilFloat
index 5ab6dc3..b77379b 100644 (file)
                0F4C91661C29F4F2004341A6 /* B3OriginDump.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4C91651C29F4F2004341A6 /* B3OriginDump.h */; };
                0F4DE1CE1C4C1B54004D6C11 /* AirFixObviousSpills.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4DE1CC1C4C1B54004D6C11 /* AirFixObviousSpills.cpp */; };
                0F4DE1CF1C4C1B54004D6C11 /* AirFixObviousSpills.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4DE1CD1C4C1B54004D6C11 /* AirFixObviousSpills.h */; };
+               0F4DE1D11C4D764B004D6C11 /* B3OriginDump.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4DE1D01C4D764B004D6C11 /* B3OriginDump.cpp */; };
                0F4F29DF18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F29DD18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp */; };
                0F4F29E018B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */; };
                0F50AF3C193E8B3900674EE8 /* DFGStructureClobberState.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */; };
                0F6B1CB91861244C00845D97 /* ArityCheckMode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6B1CB71861244C00845D97 /* ArityCheckMode.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F6B1CC51862C47800845D97 /* FTLUnwindInfo.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6B1CC11862C47800845D97 /* FTLUnwindInfo.cpp */; };
                0F6B1CC61862C47800845D97 /* FTLUnwindInfo.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6B1CC21862C47800845D97 /* FTLUnwindInfo.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F6B8AD81C4EDDA200969052 /* B3DuplicateTails.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6B8AD61C4EDDA200969052 /* B3DuplicateTails.cpp */; };
+               0F6B8AD91C4EDDA200969052 /* B3DuplicateTails.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6B8AD71C4EDDA200969052 /* B3DuplicateTails.h */; };
+               0F6B8ADC1C4EFAC300969052 /* B3SSACalculator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6B8ADA1C4EFAC300969052 /* B3SSACalculator.cpp */; };
+               0F6B8ADD1C4EFAC300969052 /* B3SSACalculator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6B8ADB1C4EFAC300969052 /* B3SSACalculator.h */; };
+               0F6B8AE21C4EFE1700969052 /* B3BreakCriticalEdges.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6B8ADE1C4EFE1700969052 /* B3BreakCriticalEdges.cpp */; };
+               0F6B8AE31C4EFE1700969052 /* B3BreakCriticalEdges.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6B8ADF1C4EFE1700969052 /* B3BreakCriticalEdges.h */; };
+               0F6B8AE41C4EFE1700969052 /* B3FixSSA.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */; };
+               0F6B8AE51C4EFE1700969052 /* B3FixSSA.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6B8AE11C4EFE1700969052 /* B3FixSSA.h */; };
                0F6C73501AC9F99F00BE1682 /* VariableWriteFireDetail.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6C734E1AC9F99F00BE1682 /* VariableWriteFireDetail.cpp */; };
                0F6C73511AC9F99F00BE1682 /* VariableWriteFireDetail.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6C734F1AC9F99F00BE1682 /* VariableWriteFireDetail.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F6E845A19030BEF00562741 /* DFGVariableAccessData.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F6E845919030BEF00562741 /* DFGVariableAccessData.cpp */; };
                0F7025AA1714B0FC00382C0E /* DFGOSRExitCompilerCommon.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F7025A81714B0F800382C0E /* DFGOSRExitCompilerCommon.h */; };
                0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */; };
                0F714CA516EA92F200F3EBEB /* DFGBackwardsPropagationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */; };
+               0F725CAF1C506D3B00AD943A /* B3FoldPathConstants.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */; };
+               0F725CB01C506D3B00AD943A /* B3FoldPathConstants.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */; };
                0F743BAA16B88249009F9277 /* ARM64Disassembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 652A3A201651C66100A80AFE /* ARM64Disassembler.cpp */; };
                0F766D2815A8CC1E008F363E /* JITStubRoutine.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F766D2615A8CC1B008F363E /* JITStubRoutine.cpp */; };
                0F766D2B15A8CC38008F363E /* JITStubRoutineSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F766D2915A8CC34008F363E /* JITStubRoutineSet.cpp */; };
                0F4C91651C29F4F2004341A6 /* B3OriginDump.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3OriginDump.h; path = b3/B3OriginDump.h; sourceTree = "<group>"; };
                0F4DE1CC1C4C1B54004D6C11 /* AirFixObviousSpills.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirFixObviousSpills.cpp; path = b3/air/AirFixObviousSpills.cpp; sourceTree = "<group>"; };
                0F4DE1CD1C4C1B54004D6C11 /* AirFixObviousSpills.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirFixObviousSpills.h; path = b3/air/AirFixObviousSpills.h; sourceTree = "<group>"; };
+               0F4DE1D01C4D764B004D6C11 /* B3OriginDump.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3OriginDump.cpp; path = b3/B3OriginDump.cpp; sourceTree = "<group>"; };
                0F4F29DD18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGStaticExecutionCountEstimationPhase.cpp; path = dfg/DFGStaticExecutionCountEstimationPhase.cpp; sourceTree = "<group>"; };
                0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStaticExecutionCountEstimationPhase.h; path = dfg/DFGStaticExecutionCountEstimationPhase.h; sourceTree = "<group>"; };
                0F50AF3B193E8B3900674EE8 /* DFGStructureClobberState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStructureClobberState.h; path = dfg/DFGStructureClobberState.h; sourceTree = "<group>"; };
                0F6B1CB71861244C00845D97 /* ArityCheckMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ArityCheckMode.h; sourceTree = "<group>"; };
                0F6B1CC11862C47800845D97 /* FTLUnwindInfo.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLUnwindInfo.cpp; path = ftl/FTLUnwindInfo.cpp; sourceTree = "<group>"; };
                0F6B1CC21862C47800845D97 /* FTLUnwindInfo.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLUnwindInfo.h; path = ftl/FTLUnwindInfo.h; sourceTree = "<group>"; };
+               0F6B8AD61C4EDDA200969052 /* B3DuplicateTails.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3DuplicateTails.cpp; path = b3/B3DuplicateTails.cpp; sourceTree = "<group>"; };
+               0F6B8AD71C4EDDA200969052 /* B3DuplicateTails.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3DuplicateTails.h; path = b3/B3DuplicateTails.h; sourceTree = "<group>"; };
+               0F6B8ADA1C4EFAC300969052 /* B3SSACalculator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3SSACalculator.cpp; path = b3/B3SSACalculator.cpp; sourceTree = "<group>"; };
+               0F6B8ADB1C4EFAC300969052 /* B3SSACalculator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3SSACalculator.h; path = b3/B3SSACalculator.h; sourceTree = "<group>"; };
+               0F6B8ADE1C4EFE1700969052 /* B3BreakCriticalEdges.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3BreakCriticalEdges.cpp; path = b3/B3BreakCriticalEdges.cpp; sourceTree = "<group>"; };
+               0F6B8ADF1C4EFE1700969052 /* B3BreakCriticalEdges.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3BreakCriticalEdges.h; path = b3/B3BreakCriticalEdges.h; sourceTree = "<group>"; };
+               0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3FixSSA.cpp; path = b3/B3FixSSA.cpp; sourceTree = "<group>"; };
+               0F6B8AE11C4EFE1700969052 /* B3FixSSA.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3FixSSA.h; path = b3/B3FixSSA.h; sourceTree = "<group>"; };
                0F6C734E1AC9F99F00BE1682 /* VariableWriteFireDetail.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = VariableWriteFireDetail.cpp; sourceTree = "<group>"; };
                0F6C734F1AC9F99F00BE1682 /* VariableWriteFireDetail.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VariableWriteFireDetail.h; sourceTree = "<group>"; };
                0F6E845919030BEF00562741 /* DFGVariableAccessData.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGVariableAccessData.cpp; path = dfg/DFGVariableAccessData.cpp; sourceTree = "<group>"; };
                0F7025A81714B0F800382C0E /* DFGOSRExitCompilerCommon.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGOSRExitCompilerCommon.h; path = dfg/DFGOSRExitCompilerCommon.h; sourceTree = "<group>"; };
                0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBackwardsPropagationPhase.cpp; path = dfg/DFGBackwardsPropagationPhase.cpp; sourceTree = "<group>"; };
                0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBackwardsPropagationPhase.h; path = dfg/DFGBackwardsPropagationPhase.h; sourceTree = "<group>"; };
+               0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3FoldPathConstants.cpp; path = b3/B3FoldPathConstants.cpp; sourceTree = "<group>"; };
+               0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3FoldPathConstants.h; path = b3/B3FoldPathConstants.h; sourceTree = "<group>"; };
                0F766D1C15A5028D008F363E /* JITStubRoutine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JITStubRoutine.h; sourceTree = "<group>"; };
                0F766D2615A8CC1B008F363E /* JITStubRoutine.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JITStubRoutine.cpp; sourceTree = "<group>"; };
                0F766D2915A8CC34008F363E /* JITStubRoutineSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JITStubRoutineSet.cpp; sourceTree = "<group>"; };
                                0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */,
                                0F338E181BF286EA0013C88F /* B3BlockInsertionSet.h */,
                                0FEC84BA1BDACDAC0080FF74 /* B3BlockWorklist.h */,
+                               0F6B8ADE1C4EFE1700969052 /* B3BreakCriticalEdges.cpp */,
+                               0F6B8ADF1C4EFE1700969052 /* B3BreakCriticalEdges.h */,
                                0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */,
                                0F338DF81BE96AA80013C88F /* B3CCallValue.h */,
                                0F33FCF91C1625BE00323F67 /* B3CFG.h */,
                                0F338E011BF0276C0013C88F /* B3DataSection.cpp */,
                                0F338E021BF0276C0013C88F /* B3DataSection.h */,
                                0F33FCFA1C1625BE00323F67 /* B3Dominators.h */,
+                               0F6B8AD61C4EDDA200969052 /* B3DuplicateTails.cpp */,
+                               0F6B8AD71C4EDDA200969052 /* B3DuplicateTails.h */,
                                0FEC85C41BE16F5A0080FF74 /* B3Effects.cpp */,
                                0FEC85BE1BE167A00080FF74 /* B3Effects.h */,
+                               0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */,
+                               0F6B8AE11C4EFE1700969052 /* B3FixSSA.h */,
+                               0F725CAD1C506D3B00AD943A /* B3FoldPathConstants.cpp */,
+                               0F725CAE1C506D3B00AD943A /* B3FoldPathConstants.h */,
                                0FEC84CB1BDACDAC0080FF74 /* B3FrequencyClass.cpp */,
                                0FEC84CC1BDACDAC0080FF74 /* B3FrequencyClass.h */,
                                0FEC84CD1BDACDAC0080FF74 /* B3FrequentedBlock.h */,
                                0FEC84D81BDACDAC0080FF74 /* B3Opcode.h */,
                                0FEC84D91BDACDAC0080FF74 /* B3Origin.cpp */,
                                0FEC84DA1BDACDAC0080FF74 /* B3Origin.h */,
+                               0F4DE1D01C4D764B004D6C11 /* B3OriginDump.cpp */,
                                0F4C91651C29F4F2004341A6 /* B3OriginDump.h */,
                                0FEC84DB1BDACDAC0080FF74 /* B3PatchpointSpecial.cpp */,
                                0FEC84DC1BDACDAC0080FF74 /* B3PatchpointSpecial.h */,
                                43422A651C16221E00E2EB98 /* B3ReduceDoubleToFloat.h */,
                                0FEC85B71BE1462F0080FF74 /* B3ReduceStrength.cpp */,
                                0FEC85B81BE1462F0080FF74 /* B3ReduceStrength.h */,
+                               0F6B8ADA1C4EFAC300969052 /* B3SSACalculator.cpp */,
+                               0F6B8ADB1C4EFAC300969052 /* B3SSACalculator.h */,
                                0F33FCF51C136E2500323F67 /* B3StackmapGenerationParams.cpp */,
                                0F33FCF61C136E2500323F67 /* B3StackmapGenerationParams.h */,
                                0FEC84E61BDACDAC0080FF74 /* B3StackmapSpecial.cpp */,
                                0F24E54217EA9F5900ABB217 /* CCallHelpers.h in Headers */,
                                0F1C3DDA1BBCE09E00E523E4 /* CellState.h in Headers */,
                                BC6AAAE50E1F426500AD87D8 /* ClassInfo.h in Headers */,
+                               0F6B8AD91C4EDDA200969052 /* B3DuplicateTails.h in Headers */,
                                0FE050261AA9095600D33B33 /* ClonedArguments.h in Headers */,
                                969A07970ED1D3AE00F1F681 /* CodeBlock.h in Headers */,
                                0F8F94411667633200D61971 /* CodeBlockHash.h in Headers */,
                                0F04396E1B03DC0B009598B7 /* DFGCombinedLiveness.h in Headers */,
                                0F7B294D14C3CD4C007C3DB1 /* DFGCommon.h in Headers */,
                                0FEA0A32170D40BF00BB722C /* DFGCommonData.h in Headers */,
+                               0F725CB01C506D3B00AD943A /* B3FoldPathConstants.h in Headers */,
                                0F38B01817CFE75500B144D3 /* DFGCompilationKey.h in Headers */,
                                0F9D4C111C3E2C74006CD984 /* FTLPatchpointExceptionHandle.h in Headers */,
                                0F38B01A17CFE75500B144D3 /* DFGCompilationMode.h in Headers */,
                                79F8FC1F1B9FED0F00CA66AB /* DFGMaximalFlushInsertionPhase.h in Headers */,
                                0F5874EE194FEB1200AAB2C1 /* DFGMayExit.h in Headers */,
                                0F2BDC451522801B00CD8910 /* DFGMinifiedGraph.h in Headers */,
+                               0F6B8AE31C4EFE1700969052 /* B3BreakCriticalEdges.h in Headers */,
                                0F2E892D16D02BAF009E4FD2 /* DFGMinifiedID.h in Headers */,
                                0F2BDC461522802000CD8910 /* DFGMinifiedNode.h in Headers */,
                                0F8F14361ADF090100ED792C /* DFGMovHintRemovalPhase.h in Headers */,
                                0FEA0A1D1708B00700BB722C /* FTLAbstractHeap.h in Headers */,
                                0FEA0A1F1708B00700BB722C /* FTLAbstractHeapRepository.h in Headers */,
                                0F485328187DFDEC0083B687 /* FTLAvailableRecovery.h in Headers */,
+                               0F6B8AE51C4EFE1700969052 /* B3FixSSA.h in Headers */,
                                0FEA0A0A170513DB00BB722C /* FTLCapabilities.h in Headers */,
                                0FEA0A231709606900BB722C /* FTLCommonValues.h in Headers */,
                                0FEA0A0C170513DB00BB722C /* FTLCompile.h in Headers */,
                                7B2E010E1B97AA6900EF5D5C /* WASMFunctionCompiler.h in Headers */,
                                7B8329BF1BB21FE300649A6E /* WASMFunctionLLVMIRGenerator.h in Headers */,
                                7B0247571B8682E400542440 /* WASMFunctionParser.h in Headers */,
+                               0F6B8ADD1C4EFAC300969052 /* B3SSACalculator.h in Headers */,
                                7B0247591B868EB700542440 /* WASMFunctionSyntaxChecker.h in Headers */,
                                7B39F76E1B62DE3200360FB4 /* WASMModuleParser.h in Headers */,
                                7B39F7701B62DE3200360FB4 /* WASMReader.h in Headers */,
                                62D755D41B84FB3D001801FA /* CallFrameShuffler64.cpp in Sources */,
                                0F0B83B014BCF71600885B4F /* CallLinkInfo.cpp in Sources */,
                                0F93329D14CA7DC30085F3C6 /* CallLinkStatus.cpp in Sources */,
+                               0F6B8ADC1C4EFAC300969052 /* B3SSACalculator.cpp in Sources */,
                                627673231B680C1E00FD9F2E /* CallMode.cpp in Sources */,
                                0F3B7E2A19A11B8000D9BC56 /* CallVariant.cpp in Sources */,
                                0FE050251AA9095600D33B33 /* ClonedArguments.cpp in Sources */,
                                0FC09791146A6F7100CF2442 /* DFGOSRExit.cpp in Sources */,
                                0F235BEB17178E7300690C7F /* DFGOSRExitBase.cpp in Sources */,
                                0FC09792146A6F7300CF2442 /* DFGOSRExitCompiler.cpp in Sources */,
+                               0F4DE1D11C4D764B004D6C11 /* B3OriginDump.cpp in Sources */,
                                FE3A06B11C10CB8400390FDD /* JITBitAndGenerator.cpp in Sources */,
                                0FC09776146943B000CF2442 /* DFGOSRExitCompiler32_64.cpp in Sources */,
                                0FC0977214693AF900CF2442 /* DFGOSRExitCompiler64.cpp in Sources */,
                                0F25F1AF181635F300522F39 /* FTLInlineCacheSize.cpp in Sources */,
                                0FEA0A281709623B00BB722C /* FTLIntrinsicRepository.cpp in Sources */,
                                0FEA0A0D170513DB00BB722C /* FTLJITCode.cpp in Sources */,
+                               0F6B8AE21C4EFE1700969052 /* B3BreakCriticalEdges.cpp in Sources */,
                                A78A9780179738D5009DF744 /* FTLJITFinalizer.cpp in Sources */,
                                0F6B1CB5185FC9E900845D97 /* FTLJSCall.cpp in Sources */,
                                0FD1202F1A8AED12000F5280 /* FTLJSCallBase.cpp in Sources */,
+                               0F725CAF1C506D3B00AD943A /* B3FoldPathConstants.cpp in Sources */,
                                0FD120331A8C85BD000F5280 /* FTLJSCallVarargs.cpp in Sources */,
                                62774DAA1B8D4B190006F05A /* FTLJSTailCall.cpp in Sources */,
                                FE187A0E1C030D640038BBCA /* JITDivGenerator.cpp in Sources */,
                                A5BA15EC182340B400A82E69 /* RemoteConnectionToTarget.mm in Sources */,
                                A5BA15EE182340B400A82E69 /* RemoteInspectorXPCConnection.mm in Sources */,
                                0F24E55017EE274900ABB217 /* Repatch.cpp in Sources */,
+                               0F6B8AD81C4EDDA200969052 /* B3DuplicateTails.cpp in Sources */,
                                527773DE1AAF83AC00BDE7E8 /* RuntimeType.cpp in Sources */,
                                0F7700921402FF3C0078EB39 /* SamplingCounter.cpp in Sources */,
                                1429D8850ED21C3D00B89619 /* SamplingTool.cpp in Sources */,
                                52C952B919A28A1C0069B386 /* TypeProfiler.cpp in Sources */,
                                0F2D4DEB19832DC4007D4B19 /* TypeProfilerLog.cpp in Sources */,
                                0F2D4DEF19832DD3007D4B19 /* TypeSet.cpp in Sources */,
+                               0F6B8AE41C4EFE1700969052 /* B3FixSSA.cpp in Sources */,
                                0FF4274A158EBE91004CB9FF /* udis86.c in Sources */,
                                0FF42740158EBE8B004CB9FF /* udis86_decode.c in Sources */,
                                0FF42743158EBE91004CB9FF /* udis86_input.c in Sources */,
index cdd1135..594d0d6 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,6 +39,11 @@ void ArgumentRegValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.print(comma, m_reg);
 }
 
+Value* ArgumentRegValue::cloneImpl() const
+{
+    return new ArgumentRegValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 09dd0b6..a6bdcc9 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
@@ -44,6 +44,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Procedure;
 
index e2ab3c2..ddd89cc 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
@@ -54,6 +54,12 @@ void BasicBlock::append(Value* value)
     m_values.append(value);
 }
 
+void BasicBlock::appendNonTerminal(Value* value)
+{
+    m_values.append(m_values.last());
+    m_values[m_values.size() - 1] = value;
+}
+
 void BasicBlock::removeLast(Procedure& proc)
 {
     ASSERT(!m_values.isEmpty());
index 5d95907..d3e1f04 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
@@ -71,10 +71,13 @@ public:
     ValueList& values() { return m_values; }
 
     JS_EXPORT_PRIVATE void append(Value*);
+    JS_EXPORT_PRIVATE void appendNonTerminal(Value*);
     JS_EXPORT_PRIVATE void replaceLast(Procedure&, Value*);
 
     template<typename ValueType, typename... Arguments>
     ValueType* appendNew(Procedure&, Arguments...);
+    template<typename ValueType, typename... Arguments>
+    ValueType* appendNewNonTerminal(Procedure&, Arguments...);
 
     JS_EXPORT_PRIVATE Value* appendIntConstant(Procedure&, Origin, Type, int64_t value);
     Value* appendIntConstant(Procedure&, Value* likeValue, int64_t value);
index efbb9e1..43a9d62 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
@@ -43,6 +43,14 @@ ValueType* BasicBlock::appendNew(Procedure& procedure, Arguments... arguments)
 }
 
 template<typename ValueType, typename... Arguments>
+ValueType* BasicBlock::appendNewNonTerminal(Procedure& procedure, Arguments... arguments)
+{
+    ValueType* result = procedure.add<ValueType>(arguments...);
+    appendNonTerminal(result);
+    return result;
+}
+
+template<typename ValueType, typename... Arguments>
 ValueType* BasicBlock::replaceLastWithNew(Procedure& procedure, Arguments... arguments)
 {
     ValueType* result = procedure.add<ValueType>(arguments...);
index d23ad29..6c8f7b2 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
@@ -61,8 +61,8 @@ public:
     // everything at and after valueIndex. If the optional InsertionSet is provided, it will get
     // executed on the newly created block - this makes sense if you had previously inserted
     // things into the original block, since the newly created block will be indexed identically
-    // to hold this block was indexed for all values prior to valueIndex. After this runs, it
-    // sets valueIndex to zero. This allows you to use this method for things like:
+    // to how this block was indexed for all values prior to valueIndex. After this runs, it sets
+    // valueIndex to zero. This allows you to use this method for things like:
     //
     // for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
     //     Value* value = block->at(valueIndex);
diff --git a/Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp b/Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp
new file mode 100644 (file)
index 0000000..60272d5
--- /dev/null
@@ -0,0 +1,68 @@
+/*
+ * 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 "B3BreakCriticalEdges.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3BlockInsertionSet.h"
+#include "B3ControlValue.h"
+#include "B3ProcedureInlines.h"
+#include "B3ValueInlines.h"
+
+namespace JSC { namespace B3 {
+
+void breakCriticalEdges(Procedure& proc)
+{
+    BlockInsertionSet insertionSet(proc);
+    
+    for (BasicBlock* block : proc) {
+        if (block->numSuccessors() <= 1)
+            continue;
+
+        for (BasicBlock*& successor : block->successorBlocks()) {
+            if (successor->numPredecessors() <= 1)
+                continue;
+
+            BasicBlock* pad =
+                insertionSet.insertBefore(successor, successor->frequency());
+            pad->appendNew<ControlValue>(
+                proc, Jump, successor->at(0)->origin(), FrequentedBlock(successor));
+            pad->addPredecessor(block);
+            successor->replacePredecessor(block, pad);
+            successor = pad;
+        }
+    }
+
+    insertionSet.execute();
+    proc.invalidateCFG();
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3BreakCriticalEdges.h b/Source/JavaScriptCore/b3/B3BreakCriticalEdges.h
new file mode 100644 (file)
index 0000000..e9b7168
--- /dev/null
@@ -0,0 +1,42 @@
+/*
+ * 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 B3BreakCriticalEdges_h
+#define B3BreakCriticalEdges_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+void breakCriticalEdges(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3BreakCriticalEdges_h
+
index 7c50858..518d723 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
@@ -34,6 +34,11 @@ CCallValue::~CCallValue()
 {
 }
 
+Value* CCallValue::cloneImpl() const
+{
+    return new CCallValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 6df6222..6155527 100644 (file)
@@ -41,6 +41,9 @@ public:
 
     Effects effects { Effects::forCall() };
 
+protected:
+    Value* cloneImpl() const override;
+    
 private:
     friend class Procedure;
 
index 99ce426..69576fa 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
@@ -40,6 +40,11 @@ void CheckValue::convertToAdd()
     m_opcode = CheckAdd;
 }
 
+Value* CheckValue::cloneImpl() const
+{
+    return new CheckValue(*this);
+}
+
 // Use this form for CheckAdd, CheckSub, and CheckMul.
 CheckValue::CheckValue(unsigned index, Opcode opcode, Origin origin, Value* left, Value* right)
     : StackmapValue(index, CheckedOpcode, opcode, left->type(), origin)
index b02a56b..c2fab6f 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
@@ -51,6 +51,9 @@ public:
 
     void convertToAdd();
 
+protected:
+    Value* cloneImpl() const override;
+    
 private:
     friend class Procedure;
 
index 827ae90..c429c55 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
@@ -241,6 +241,11 @@ void Const32Value::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.print(comma, m_value);
 }
 
+Value* Const32Value::cloneImpl() const
+{
+    return new Const32Value(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 17c34a5..7d564b6 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
@@ -73,6 +73,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
     friend class Procedure;
 
     Const32Value(unsigned index, Origin origin, int32_t value)
index 01dcc69..be7e468 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
@@ -241,6 +241,11 @@ void Const64Value::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.print(comma, m_value);
 }
 
+Value* Const64Value::cloneImpl() const
+{
+    return new Const64Value(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 0c63aa0..406c451 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
@@ -73,6 +73,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
     friend class Procedure;
 
     Const64Value(unsigned index, Origin origin, int64_t value)
index a2537c4..f9ce296 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
@@ -175,6 +175,11 @@ void ConstDoubleValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.printf("%le", m_value);
 }
 
+Value* ConstDoubleValue::cloneImpl() const
+{
+    return new ConstDoubleValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index a9f0bf7..ddd3c5c 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
@@ -65,6 +65,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Procedure;
 
index 4c57b8e..44f6403 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
@@ -157,6 +157,11 @@ void ConstFloatValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.printf("%le", m_value);
 }
 
+Value* ConstFloatValue::cloneImpl() const
+{
+    return new ConstFloatValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 9f99cb2..c705460 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
@@ -63,6 +63,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Procedure;
 
index 762feab..ea86a68 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
@@ -83,6 +83,11 @@ void ControlValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
         out.print(comma, successor);
 }
 
+Value* ControlValue::cloneImpl() const
+{
+    return new ControlValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 82bc65b..9b838ad 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
@@ -29,6 +29,7 @@
 #if ENABLE(B3_JIT)
 
 #include "B3FrequentedBlock.h"
+#include "B3SuccessorCollection.h"
 #include "B3Value.h"
 
 namespace JSC { namespace B3 {
@@ -64,6 +65,17 @@ public:
     const SuccessorList& successors() const { return m_successors; }
     SuccessorList& successors() { return m_successors; }
 
+    BasicBlock* successorBlock(unsigned index) const { return successor(index).block(); }
+    BasicBlock*& successorBlock(unsigned index) { return successor(index).block(); }
+    SuccessorCollection<BasicBlock, SuccessorList> successorBlocks()
+    {
+        return SuccessorCollection<BasicBlock, SuccessorList>(successors());
+    }
+    SuccessorCollection<const BasicBlock, const SuccessorList> successorBlocks() const
+    {
+        return SuccessorCollection<const BasicBlock, const SuccessorList>(successors());
+    }
+
     bool replaceSuccessor(BasicBlock* from, BasicBlock* to);
 
     const FrequentedBlock& taken() const
@@ -93,6 +105,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
     // Use this for subclasses.
     template<typename... Arguments>
     ControlValue(unsigned index, Opcode opcode, Type type, Origin origin, Arguments... arguments)
diff --git a/Source/JavaScriptCore/b3/B3DuplicateTails.cpp b/Source/JavaScriptCore/b3/B3DuplicateTails.cpp
new file mode 100644 (file)
index 0000000..ae891ad
--- /dev/null
@@ -0,0 +1,154 @@
+/*
+ * 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 "B3DuplicateTails.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3ControlValue.h"
+#include "B3Dominators.h"
+#include "B3FixSSA.h"
+#include "B3IndexSet.h"
+#include "B3InsertionSetInlines.h"
+#include "B3PhaseScope.h"
+#include "B3ProcedureInlines.h"
+#include "B3SwitchValue.h"
+#include "B3UpsilonValue.h"
+#include "B3ValueInlines.h"
+
+namespace JSC { namespace B3 {
+
+namespace {
+
+const bool verbose = false;
+
+class DuplicateTails {
+public:
+    DuplicateTails(Procedure& proc)
+        : m_proc(proc)
+        , m_insertionSet(proc)
+        , m_maxSize(Options::maxB3TailDupBlockSize())
+        , m_maxSuccessors(Options::maxB3TailDupBlockSuccessors())
+    {
+    }
+
+    void run()
+    {
+        // Find blocks that would be candidates for tail duplication. They must be small enough
+        // and they much not have too many successors.
+
+        m_proc.resetValueOwners();
+
+        IndexSet<BasicBlock> candidates;
+
+        for (BasicBlock* block : m_proc) {
+            if (block->size() > m_maxSize || block->numSuccessors() > m_maxSuccessors)
+                continue;
+
+            candidates.add(block);
+        }
+
+        // Collect the set of values that must be de-SSA'd.
+        IndexSet<Value> valuesToDemote;
+        for (BasicBlock* block : m_proc) {
+            for (Value* value : *block) {
+                if (value->opcode() == Phi && candidates.contains(block))
+                    valuesToDemote.add(value);
+                for (Value* child : value->children()) {
+                    if (child->owner != block && candidates.contains(child->owner))
+                        valuesToDemote.add(child);
+                }
+            }
+        }
+        demoteValues(m_proc, valuesToDemote);
+        if (verbose) {
+            dataLog("Procedure after value demotion:\n");
+            dataLog(m_proc);
+        }
+
+        for (BasicBlock* block : m_proc) {
+            ControlValue* jump = block->last()->as<ControlValue>();
+            if (jump->opcode() != Jump)
+                continue;
+
+            BasicBlock* tail = jump->successorBlock(0);
+            if (!candidates.contains(tail))
+                continue;
+
+            // We're about to change 'block'. Make sure that nobody duplicates block after this
+            // point.
+            candidates.remove(block);
+
+            if (verbose)
+                dataLog("Duplicating ", *tail, " into ", *block, "\n");
+
+            block->removeLast(m_proc);
+
+            HashMap<Value*, Value*> map;
+            for (Value* value : *tail) {
+                Value* clone = m_proc.clone(value);
+                for (Value*& child : clone->children()) {
+                    if (Value* replacement = map.get(child))
+                        child = replacement;
+                }
+                if (value->type() != Void)
+                    map.add(value, clone);
+                block->append(clone);
+            }
+        }
+
+        m_proc.resetReachability();
+        m_proc.invalidateCFG();
+
+        if (verbose) {
+            dataLog("Procedure just before SSA conversion:\n");
+            dataLog(m_proc);
+        }
+        fixSSA(m_proc);
+    }
+    
+private:
+
+    Procedure& m_proc;
+    InsertionSet m_insertionSet;
+    unsigned m_maxSize;
+    unsigned m_maxSuccessors;
+};
+
+} // anonymous namespace
+
+void duplicateTails(Procedure& proc)
+{
+    PhaseScope phaseScope(proc, "duplicateTails");
+    DuplicateTails duplicateTails(proc);
+    duplicateTails.run();
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3DuplicateTails.h b/Source/JavaScriptCore/b3/B3DuplicateTails.h
new file mode 100644 (file)
index 0000000..a085e05
--- /dev/null
@@ -0,0 +1,46 @@
+/*
+ * 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 B3DuplicateTails_h
+#define B3DuplicateTails_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+// Replaces jumps to tiny basic blocks with the contents of those basic blocks. Also simplifies
+// branches that are path-redundant. Does not do a fixpoint, because it does not have a good way
+// of detecting termination.
+
+void duplicateTails(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3DuplicateTails_h
+
diff --git a/Source/JavaScriptCore/b3/B3FixSSA.cpp b/Source/JavaScriptCore/b3/B3FixSSA.cpp
new file mode 100644 (file)
index 0000000..d547b73
--- /dev/null
@@ -0,0 +1,335 @@
+/*
+ * 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 "B3FixSSA.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3BreakCriticalEdges.h"
+#include "B3ControlValue.h"
+#include "B3Dominators.h"
+#include "B3IndexSet.h"
+#include "B3InsertionSetInlines.h"
+#include "B3MemoryValue.h"
+#include "B3PhaseScope.h"
+#include "B3ProcedureInlines.h"
+#include "B3SSACalculator.h"
+#include "B3StackSlotValue.h"
+#include "B3UpsilonValue.h"
+#include "B3ValueInlines.h"
+#include <wtf/CommaPrinter.h>
+
+namespace JSC { namespace B3 {
+
+namespace {
+const bool verbose = false;
+} // anonymous namespace
+
+void demoteValues(Procedure& proc, const IndexSet<Value>& values)
+{
+    HashMap<Value*, StackSlotValue*> map;
+    HashMap<Value*, StackSlotValue*> phiMap;
+
+    // Create stack slots.
+    InsertionSet insertionSet(proc);
+    for (Value* value : values.values(proc.values())) {
+        StackSlotValue* stack = insertionSet.insert<StackSlotValue>(
+            0, value->origin(), sizeofType(value->type()), StackSlotKind::Anonymous);
+        map.add(value, stack);
+
+        if (value->opcode() == Phi) {
+            StackSlotValue* phiStack = insertionSet.insert<StackSlotValue>(
+                0, value->origin(), sizeofType(value->type()), StackSlotKind::Anonymous);
+            phiMap.add(value, phiStack);
+        }
+    }
+    insertionSet.execute(proc[0]);
+
+    if (verbose) {
+        dataLog("Demoting values as follows:\n");
+        dataLog("   map = ");
+        CommaPrinter comma;
+        for (auto& entry : map)
+            dataLog(comma, *entry.key, "=>", *entry.value);
+        dataLog("\n");
+        dataLog("   phiMap = ");
+        comma = CommaPrinter();
+        for (auto& entry : phiMap)
+            dataLog(comma, *entry.key, "=>", *entry.value);
+        dataLog("\n");
+    }
+
+    // Change accesses to the values to accesses to the stack slots.
+    for (BasicBlock* block : proc) {
+        for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
+            Value* value = block->at(valueIndex);
+
+            if (value->opcode() == Phi) {
+                if (StackSlotValue* stack = phiMap.get(value)) {
+                    value->replaceWithIdentity(
+                        insertionSet.insert<MemoryValue>(
+                            valueIndex, Load, value->type(), value->origin(), stack));
+                }
+            } else {
+                for (Value*& child : value->children()) {
+                    if (StackSlotValue* stack = map.get(child)) {
+                        child = insertionSet.insert<MemoryValue>(
+                            valueIndex, Load, child->type(), value->origin(), stack);
+                    }
+                }
+
+                if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
+                    if (StackSlotValue* stack = phiMap.get(upsilon->phi())) {
+                        insertionSet.insert<MemoryValue>(
+                            valueIndex, Store, upsilon->origin(), upsilon->child(0), stack);
+                        value->replaceWithNop();
+                    }
+                }
+            }
+
+            if (StackSlotValue* stack = map.get(value)) {
+                insertionSet.insert<MemoryValue>(
+                    valueIndex + 1, Store, value->origin(), value, stack);
+            }
+        }
+        insertionSet.execute(block);
+    }
+}
+
+bool fixSSA(Procedure& proc)
+{
+    // Collect the stack "variables". If there aren't any, then we don't have anything to do.
+    // That's a fairly common case.
+    HashMap<StackSlotValue*, Type> stackVariable;
+    for (Value* value : proc.values()) {
+        if (StackSlotValue* stack = value->as<StackSlotValue>()) {
+            if (stack->kind() == StackSlotKind::Anonymous)
+                stackVariable.add(stack, Void);
+        }
+    }
+
+    if (stackVariable.isEmpty())
+        return false;
+
+    // Make sure that we know how to optimize all of these. We only know how to handle Load and
+    // Store on anonymous variables.
+    for (Value* value : proc.values()) {
+        auto reject = [&] (Value* value) {
+            if (StackSlotValue* stack = value->as<StackSlotValue>())
+                stackVariable.remove(stack);
+        };
+        
+        auto handleAccess = [&] (Value* access, Type type) {
+            StackSlotValue* stack = access->lastChild()->as<StackSlotValue>();
+            if (!stack)
+                return;
+            
+            if (value->as<MemoryValue>()->offset()) {
+                stackVariable.remove(stack);
+                return;
+            }
+
+            auto result = stackVariable.find(stack);
+            if (result == stackVariable.end())
+                return;
+            if (result->value == Void) {
+                result->value = type;
+                return;
+            }
+            if (result->value == type)
+                return;
+            stackVariable.remove(result);
+        };
+        
+        switch (value->opcode()) {
+        case Load:
+            // We're OK with loads from stack variables at an offset of zero.
+            handleAccess(value, value->type());
+            break;
+        case Store:
+            // We're OK with stores to stack variables, but not storing stack variables.
+            reject(value->child(0));
+            handleAccess(value, value->child(0)->type());
+            break;
+        default:
+            for (Value* child : value->children())
+                reject(child);
+            break;
+        }
+    }
+
+    Vector<StackSlotValue*> deadValues;
+    for (auto& entry : stackVariable) {
+        if (entry.value == Void)
+            deadValues.append(entry.key);
+    }
+
+    for (StackSlotValue* deadValue : deadValues) {
+        deadValue->replaceWithNop();
+        stackVariable.remove(deadValue);
+    }
+
+    if (stackVariable.isEmpty())
+        return false;
+
+    // We know that we have variables to optimize, so do that now.
+    breakCriticalEdges(proc);
+
+    SSACalculator ssa(proc);
+
+    // Create a SSACalculator::Variable for every stack variable.
+    Vector<StackSlotValue*> variableToStack;
+    HashMap<StackSlotValue*, SSACalculator::Variable*> stackToVariable;
+
+    for (auto& entry : stackVariable) {
+        StackSlotValue* stack = entry.key;
+        SSACalculator::Variable* variable = ssa.newVariable();
+        RELEASE_ASSERT(variable->index() == variableToStack.size());
+        variableToStack.append(stack);
+        stackToVariable.add(stack, variable);
+    }
+
+    // Create Defs for all of the stores to the stack variable.
+    for (BasicBlock* block : proc) {
+        for (Value* value : *block) {
+            if (value->opcode() != Store)
+                continue;
+
+            StackSlotValue* stack = value->child(1)->as<StackSlotValue>();
+            if (!stack)
+                continue;
+
+            if (SSACalculator::Variable* variable = stackToVariable.get(stack))
+                ssa.newDef(variable, block, value->child(0));
+        }
+    }
+
+    // Decide where Phis are to be inserted. This creates them but does not insert them.
+    ssa.computePhis(
+        [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Value* {
+            StackSlotValue* stack = variableToStack[variable->index()];
+            Value* phi = proc.add<Value>(Phi, stackVariable.get(stack), stack->origin());
+            if (verbose) {
+                dataLog(
+                    "Adding Phi for ", pointerDump(stack), " at ", *block, ": ",
+                    deepDump(proc, phi), "\n");
+            }
+            return phi;
+        });
+
+    // Now perform the conversion.
+    InsertionSet insertionSet(proc);
+    HashMap<StackSlotValue*, Value*> mapping;
+    for (BasicBlock* block : proc.blocksInPreOrder()) {
+        mapping.clear();
+
+        for (auto& entry : stackToVariable) {
+            StackSlotValue* stack = entry.key;
+            SSACalculator::Variable* variable = entry.value;
+
+            SSACalculator::Def* def = ssa.reachingDefAtHead(block, variable);
+            if (def)
+                mapping.set(stack, def->value());
+        }
+
+        for (SSACalculator::Def* phiDef : ssa.phisForBlock(block)) {
+            StackSlotValue* stack = variableToStack[phiDef->variable()->index()];
+
+            insertionSet.insertValue(0, phiDef->value());
+            mapping.set(stack, phiDef->value());
+        }
+
+        for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
+            Value* value = block->at(valueIndex);
+            value->performSubstitution();
+
+            switch (value->opcode()) {
+            case Load: {
+                if (StackSlotValue* stack = value->child(0)->as<StackSlotValue>()) {
+                    if (Value* replacement = mapping.get(stack))
+                        value->replaceWithIdentity(replacement);
+                }
+                break;
+            }
+                
+            case Store: {
+                if (StackSlotValue* stack = value->child(1)->as<StackSlotValue>()) {
+                    if (stackToVariable.contains(stack)) {
+                        mapping.set(stack, value->child(0));
+                        value->replaceWithNop();
+                    }
+                }
+                break;
+            }
+
+            default:
+                break;
+            }
+        }
+
+        unsigned upsilonInsertionPoint = block->size() - 1;
+        Origin upsilonOrigin = block->last()->origin();
+        for (BasicBlock* successorBlock : block->successorBlocks()) {
+            for (SSACalculator::Def* phiDef : ssa.phisForBlock(successorBlock)) {
+                Value* phi = phiDef->value();
+                SSACalculator::Variable* variable = phiDef->variable();
+                StackSlotValue* stack = variableToStack[variable->index()];
+
+                Value* mappedValue = mapping.get(stack);
+                if (verbose) {
+                    dataLog(
+                        "Mapped value for ", *stack, " with successor Phi ", *phi, " at end of ",
+                        *block, ": ", pointerDump(mappedValue), "\n");
+                }
+                
+                if (!mappedValue)
+                    mappedValue = insertionSet.insertBottom(upsilonInsertionPoint, phi);
+                
+                insertionSet.insert<UpsilonValue>(
+                    upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
+            }
+        }
+
+        insertionSet.execute(block);
+    }
+
+    // Finally, kill the stack slots.
+    for (StackSlotValue* stack : variableToStack)
+        stack->replaceWithNop();
+
+    if (verbose) {
+        dataLog("B3 after SSA conversion:\n");
+        dataLog(proc);
+    }
+
+    return true;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3FixSSA.h b/Source/JavaScriptCore/b3/B3FixSSA.h
new file mode 100644 (file)
index 0000000..1b412ae
--- /dev/null
@@ -0,0 +1,52 @@
+/*
+ * 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 B3FixSSA_h
+#define B3FixSSA_h
+
+#if ENABLE(B3_JIT)
+
+#include "B3IndexSet.h"
+#include "B3Value.h"
+#include <wtf/Vector.h>
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+// Turns all mentions of the given values into accesses to anonymous stack slots. This is meant
+// to be used from phases that don't like SSA for whatever reason.
+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.
+bool fixSSA(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3FixSSA_h
+
diff --git a/Source/JavaScriptCore/b3/B3FoldPathConstants.cpp b/Source/JavaScriptCore/b3/B3FoldPathConstants.cpp
new file mode 100644 (file)
index 0000000..7922867
--- /dev/null
@@ -0,0 +1,265 @@
+/*
+ * 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 "B3FoldPathConstants.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3ControlValue.h"
+#include "B3Dominators.h"
+#include "B3InsertionSetInlines.h"
+#include "B3PhaseScope.h"
+#include "B3ProcedureInlines.h"
+#include "B3SwitchValue.h"
+#include "B3ValueInlines.h"
+
+namespace JSC { namespace B3 {
+
+namespace {
+
+const bool verbose = false;
+
+class FoldPathConstants {
+public:
+    FoldPathConstants(Procedure& proc)
+        : m_proc(proc)
+        , m_insertionSet(proc)
+    {
+    }
+
+    void run()
+    {
+        bool changed = false;
+
+        if (verbose)
+            dataLog("B3 before folding path constants: \n", m_proc, "\n");
+        
+        // Find all of the values that are the subject of a branch or switch. For any successor
+        // that we dominate, install a value override at that block.
+
+        HashMap<Value*, Vector<Override>> overrides;
+
+        Dominators& dominators = m_proc.dominators();
+        
+        auto addOverride = [&] (
+            BasicBlock* from, Value* value, const Override& override) {
+
+            if (override.block->numPredecessors() != 1)
+                return;
+            ASSERT(override.block->predecessor(0) == from);
+
+            Vector<Override>& forValue =
+                overrides.add(value, Vector<Override>()).iterator->value;
+
+            if (!ASSERT_DISABLED) {
+                for (const Override& otherOverride : forValue)
+                    ASSERT_UNUSED(otherOverride, otherOverride.block != override.block);
+            }
+
+            if (verbose)
+                dataLog("Overriding ", *value, " from ", *from, ": ", override, "\n");
+            
+            forValue.append(override);
+        };
+        
+        for (BasicBlock* block : m_proc) {
+            ControlValue* branch = block->last()->as<ControlValue>();
+            switch (branch->opcode()) {
+            case Branch:
+                addOverride(
+                    block, branch->child(0),
+                    Override::nonZero(branch->successorBlock(0)));
+                addOverride(
+                    block, branch->child(0),
+                    Override::constant(branch->successorBlock(1), 0));
+                break;
+            case Switch:
+                for (const SwitchCase& switchCase : *branch->as<SwitchValue>()) {
+                    addOverride(
+                        block, branch->child(0),
+                        Override::constant(switchCase.targetBlock(), switchCase.caseValue()));
+                }
+                break;
+            default:
+                break;
+            }
+        }
+
+        // Install the constants in the override blocks. We use one-shot insertion sets because
+        // each block will get at most one thing inserted into it anyway.
+        for (auto& entry : overrides) {
+            for (Override& override : entry.value) {
+                if (!override.hasValue)
+                    continue;
+                override.valueNode =
+                    m_insertionSet.insertIntConstant(0, entry.key, override.value);
+                m_insertionSet.execute(override.block);
+            }
+        }
+
+        // Replace all uses of a value that has an override with that override, if appropriate.
+        // Certain instructions get special treatment.
+        auto getOverride = [&] (BasicBlock* block, Value* value) -> Override {
+            auto iter = overrides.find(value);
+            if (iter == overrides.end())
+                return Override();
+
+            Vector<Override>& forValue = iter->value;
+            Override result;
+            for (Override& override : forValue) {
+                if (dominators.dominates(override.block, block)
+                    && override.isBetterThan(result))
+                    result = override;
+            }
+
+            if (verbose)
+                dataLog("In block ", *block, " getting override for ", *value, ": ", result, "\n");
+
+            return result;
+        };
+        
+        for (BasicBlock* block : m_proc) {
+            for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
+                Value* value = block->at(valueIndex);
+
+                switch (value->opcode()) {
+                case Branch: {
+                    ControlValue* branch = value->as<ControlValue>();
+                    if (getOverride(block, branch->child(0)).isNonZero) {
+                        branch->convertToJump(branch->taken().block());
+                        changed = true;
+                    }
+                    break;
+                }
+
+                case Equal: {
+                    if (value->child(1)->isInt(0)
+                        && getOverride(block, value->child(0)).isNonZero) {
+                        value->replaceWithIdentity(
+                            m_insertionSet.insertIntConstant(valueIndex, value, 0));
+                    }
+                    break;
+                }
+
+                case NotEqual: {
+                    if (value->child(1)->isInt(0)
+                        && getOverride(block, value->child(0)).isNonZero) {
+                        value->replaceWithIdentity(
+                            m_insertionSet.insertIntConstant(valueIndex, value, 1));
+                    }
+                    break;
+                }
+
+                default:
+                    break;
+                }
+
+                for (Value*& child : value->children()) {
+                    Override override = getOverride(block, child);
+                    if (override.valueNode)
+                        child = override.valueNode;
+                }
+            }
+        }
+
+        if (changed) {
+            m_proc.resetReachability();
+            m_proc.invalidateCFG();
+        }
+    }
+    
+private:
+    struct Override {
+        Override()
+        {
+        }
+
+        static Override constant(BasicBlock* block, int64_t value)
+        {
+            Override result;
+            result.block = block;
+            result.hasValue = true;
+            result.value = value;
+            if (value)
+                result.isNonZero = true;
+            return result;
+        }
+
+        static Override nonZero(BasicBlock* block)
+        {
+            Override result;
+            result.block = block;
+            result.isNonZero = true;
+            return result;
+        }
+
+        bool isBetterThan(const Override& override)
+        {
+            if (hasValue && !override.hasValue)
+                return true;
+            if (isNonZero && !override.isNonZero)
+                return true;
+            return false;
+        }
+
+        void dump(PrintStream& out) const
+        {
+            out.print("{block = ", pointerDump(block), ", value = ");
+            if (hasValue)
+                out.print(value);
+            else
+                out.print("<none>");
+            out.print(", isNonZero = ", isNonZero);
+            if (valueNode)
+                out.print(", valueNode = ", *valueNode);
+            out.print("}");
+        }
+
+        BasicBlock* block { nullptr };
+        bool hasValue { false };
+        bool isNonZero { false };
+        int64_t value { 0 };
+        Value* valueNode { nullptr };
+    };
+
+    Procedure& m_proc;
+    InsertionSet m_insertionSet;
+};
+
+} // anonymous namespace
+
+void foldPathConstants(Procedure& proc)
+{
+    PhaseScope phaseScope(proc, "foldPathConstants");
+    FoldPathConstants foldPathConstants(proc);
+    foldPathConstants.run();
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3FoldPathConstants.h b/Source/JavaScriptCore/b3/B3FoldPathConstants.h
new file mode 100644 (file)
index 0000000..165ee94
--- /dev/null
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef B3FoldPathConstants_h
+#define B3FoldPathConstants_h
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+// Does very basic simplification of uses of values that were branched on by a dominating branch.
+
+void foldPathConstants(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3FoldPathConstants_h
+
index d691d10..bd61664 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
@@ -32,6 +32,8 @@
 #include "AirGenerate.h"
 #include "AirInstInlines.h"
 #include "B3Common.h"
+#include "B3DuplicateTails.h"
+#include "B3FoldPathConstants.h"
 #include "B3LegalizeMemoryOffsets.h"
 #include "B3LowerMacros.h"
 #include "B3LowerMacrosAfterOptimizations.h"
@@ -73,11 +75,19 @@ void generateToAir(Procedure& procedure, unsigned optLevel)
     if (shouldValidateIR())
         validate(procedure);
 
-    lowerMacros(procedure);
-
     if (optLevel >= 1) {
         reduceDoubleToFloat(procedure);
+        reduceStrength(procedure);
+        duplicateTails(procedure);
+        foldPathConstants(procedure);
+        
+        // FIXME: Add more optimizations here.
+        // https://bugs.webkit.org/show_bug.cgi?id=150507
+    }
+
+    lowerMacros(procedure);
 
+    if (optLevel >= 1) {
         reduceStrength(procedure);
         
         // FIXME: Add more optimizations here.
@@ -85,9 +95,7 @@ void generateToAir(Procedure& procedure, unsigned optLevel)
     }
 
     lowerMacrosAfterOptimizations(procedure);
-
     legalizeMemoryOffsets(procedure);
-
     moveConstants(procedure);
 
     if (shouldValidateIR())
index e96fdb3..e5c6ded 100644 (file)
@@ -72,7 +72,7 @@ public:
     template<typename CollectionType>
     class Iterable {
     public:
-        Iterable(const CollectionType& collection, const IndexSet& set)
+        Iterable(const CollectionType& collection, const BitVector& set)
             : m_collection(collection)
             , m_set(set)
         {
@@ -122,7 +122,7 @@ public:
 
     private:
         const CollectionType& m_collection;
-        const IndexSet& m_set;
+        const BitVector& m_set;
     };
 
     // For basic blocks, you do:
@@ -133,7 +133,7 @@ public:
     template<typename CollectionType>
     Iterable<CollectionType> values(const CollectionType& collection) const
     {
-        return Iterable<CollectionType>(collection);
+        return Iterable<CollectionType>(collection, indices());
     }
 
     const BitVector& indices() const { return m_set; }
index 6347db7..16820cb 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
@@ -45,6 +45,16 @@ Value* InsertionSet::insertIntConstant(size_t index, Value* likeValue, int64_t v
     return insertIntConstant(index, likeValue->origin(), likeValue->type(), value);
 }
 
+Value* InsertionSet::insertBottom(size_t index, Origin origin, Type type)
+{
+    return insertValue(index, m_procedure.addBottom(origin, type));
+}
+
+Value* InsertionSet::insertBottom(size_t index, Value* likeValue)
+{
+    return insertBottom(index, likeValue->origin(), likeValue->type());
+}
+
 void InsertionSet::execute(BasicBlock* block)
 {
     bubbleSort(m_insertions.begin(), m_insertions.end());
index 6fd2046..d42e44d 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
@@ -67,6 +67,9 @@ public:
     Value* insertIntConstant(size_t index, Origin, Type, int64_t value);
     Value* insertIntConstant(size_t index, Value* likeValue, int64_t value);
 
+    Value* insertBottom(size_t index, Origin, Type);
+    Value* insertBottom(size_t index, Value*);
+
     void execute(BasicBlock*);
 
 private:
index 623d34d..fbcb2fd 100644 (file)
@@ -88,6 +88,8 @@ public:
             switch (value->opcode()) {
             case Phi: {
                 m_phiToTmp[value] = m_code.newTmp(Arg::typeForB3Type(value->type()));
+                if (verbose)
+                    dataLog("Phi tmp for ", *value, ": ", m_phiToTmp[value], "\n");
                 break;
             }
             case B3::StackSlot: {
@@ -306,6 +308,8 @@ private:
                 realTmp = m_code.newTmp(Arg::typeForB3Type(value->type()));
                 if (m_procedure.isFastConstant(value->key()))
                     m_code.addFastTmp(realTmp);
+                if (verbose)
+                    dataLog("Tmp for ", *value, ": ", realTmp, "\n");
             }
             tmp = realTmp;
         }
index e0481c6..8f78714 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
@@ -61,6 +61,11 @@ void MemoryValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
         out.print(comma, "offset = ", m_offset);
 }
 
+Value* MemoryValue::cloneImpl() const
+{
+    return new MemoryValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 93f048e..0f10ead 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
@@ -65,6 +65,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter& comma, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Procedure;
 
diff --git a/Source/JavaScriptCore/b3/B3OriginDump.cpp b/Source/JavaScriptCore/b3/B3OriginDump.cpp
new file mode 100644 (file)
index 0000000..da7afee
--- /dev/null
@@ -0,0 +1,46 @@
+/*
+ * 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 "B3OriginDump.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3Procedure.h"
+
+namespace JSC { namespace B3 {
+
+void OriginDump::dump(PrintStream& out) const
+{
+    if (m_proc)
+        m_proc->printOrigin(out, m_origin);
+    else
+        out.print(m_origin);
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
index 38534e9..169eb28 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
 #if ENABLE(B3_JIT)
 
 #include "B3Origin.h"
-#include "B3Procedure.h"
 
 namespace JSC { namespace B3 {
 
+class Procedure;
+
 class OriginDump {
 public:
-    OriginDump(const Procedure& proc, Origin origin)
+    OriginDump(const Procedure* proc, Origin origin)
         : m_proc(proc)
         , m_origin(origin)
     {
     }
 
-    void dump(PrintStream& out) const
-    {
-        m_proc.printOrigin(out, m_origin);
-    }
+    void dump(PrintStream& out) const;
 
 private:
-    const Procedure& m_proc;
+    const Procedure* m_proc;
     Origin m_origin;
 };
 
index dc4e5d0..1125a8d 100644 (file)
@@ -44,6 +44,11 @@ void PatchpointValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
         out.print(comma, "numFPScratchRegisters = ", numFPScratchRegisters);
 }
 
+Value* PatchpointValue::cloneImpl() const
+{
+    return new PatchpointValue(*this);
+}
+
 PatchpointValue::PatchpointValue(unsigned index, Type type, Origin origin)
     : Base(index, CheckedOpcode, Patchpoint, type, origin)
     , effects(Effects::forCall())
index 3696228..99c9d52 100644 (file)
@@ -65,6 +65,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Procedure;
 
index 2c4784a..4dcc665 100644 (file)
@@ -68,6 +68,16 @@ BasicBlock* Procedure::addBlock(double frequency)
     return result;
 }
 
+Value* Procedure::clone(Value* value)
+{
+    std::unique_ptr<Value> clone(value->cloneImpl());
+    Value* result = clone.get();
+    clone->m_index = addValueIndex();
+    clone->owner = nullptr;
+    m_values[clone->m_index] = WTFMove(clone);
+    return result;
+}
+
 Value* Procedure::addIntConstant(Origin origin, Type type, int64_t value)
 {
     switch (type) {
@@ -90,6 +100,16 @@ Value* Procedure::addIntConstant(Value* likeValue, int64_t value)
     return addIntConstant(likeValue->origin(), likeValue->type(), value);
 }
 
+Value* Procedure::addBottom(Origin origin, Type type)
+{
+    return addIntConstant(origin, type, 0);
+}
+
+Value* Procedure::addBottom(Value* value)
+{
+    return addBottom(value->origin(), value->type());
+}
+
 Value* Procedure::addBoolConstant(Origin origin, TriState triState)
 {
     int32_t value = 0;
@@ -165,7 +185,7 @@ Vector<BasicBlock*> Procedure::blocksInPostOrder()
 
 void Procedure::deleteValue(Value* value)
 {
-    ASSERT(m_values[value->index()].get() == value);
+    RELEASE_ASSERT(m_values[value->index()].get() == value);
     m_valueIndexFreeList.append(value->index());
     m_values[value->index()] = nullptr;
 }
index d26efb7..0db7be8 100644 (file)
@@ -76,9 +76,14 @@ public:
     template<typename ValueType, typename... Arguments>
     ValueType* add(Arguments...);
 
+    Value* clone(Value*);
+
     Value* addIntConstant(Origin, Type, int64_t value);
     Value* addIntConstant(Value*, int64_t value);
 
+    Value* addBottom(Origin, Type);
+    Value* addBottom(Value*);
+
     // Returns null for MixedTriState.
     Value* addBoolConstant(Origin, TriState);
 
index 50f45f4..937a211 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(B3_JIT)
 
 #include "B3BasicBlockInlines.h"
+#include "B3BlockInsertionSet.h"
 #include "B3ControlValue.h"
 #include "B3Dominators.h"
 #include "B3IndexSet.h"
@@ -258,6 +259,7 @@ public:
     ReduceStrength(Procedure& proc)
         : m_proc(proc)
         , m_insertionSet(proc)
+        , m_blockInsertionSet(proc)
     {
     }
 
@@ -286,6 +288,11 @@ public:
                 m_block = block;
                 
                 for (m_index = 0; m_index < block->size(); ++m_index) {
+                    if (verbose) {
+                        dataLog(
+                            "Looking at ", *block, " #", m_index, ": ",
+                            deepDump(m_proc, block->at(m_index)), "\n");
+                    }
                     m_value = m_block->at(m_index);
                     m_value->performSubstitution();
                     
@@ -295,6 +302,13 @@ public:
                 m_insertionSet.execute(m_block);
             }
 
+            if (m_blockInsertionSet.execute()) {
+                m_proc.resetReachability();
+                m_proc.invalidateCFG();
+                m_dominators = &m_proc.dominators(); // Recompute if necessary.
+                m_changedCFG = true;
+            }
+            
             simplifyCFG();
 
             if (m_changedCFG) {
@@ -1387,6 +1401,51 @@ private:
                 && checkValue->child(0)->child(1)->isInt(0)) {
                 checkValue->child(0) = checkValue->child(0)->child(0);
                 m_changed = true;
+            }
+
+            // If we are checking some bounded-size SSA expression that leads to a Select that
+            // has a constant as one of its results, then turn the Select into a Branch and split
+            // the code between the Check and the Branch. For example, this:
+            //
+            //     @a = Select(@p, @x, 42)
+            //     @b = Add(@a, 35)
+            //     Check(@b)
+            //
+            // becomes this:
+            //
+            //     Branch(@p, #truecase, #falsecase)
+            //
+            //   BB#truecase:
+            //     @b_truecase = Add(@x, 35)
+            //     Check(@b_truecase)
+            //     Upsilon(@x, ^a)
+            //     Upsilon(@b_truecase, ^b)
+            //     Jump(#continuation)
+            //
+            //   BB#falsecase:
+            //     @b_falsecase = Add(42, 35)
+            //     Check(@b_falsecase)
+            //     Upsilon(42, ^a)
+            //     Upsilon(@b_falsecase, ^b)
+            //     Jump(#continuation)
+            //
+            //   BB#continuation:
+            //     @a = Phi()
+            //     @b = Phi()
+            //
+            // The goal of this optimization is to kill a lot of code in one of those basic
+            // blocks. This is pretty much guaranteed since one of those blocks will replace all
+            // uses of the Select with a constant, and that constant will be transitively used
+            // from the check.
+            static const unsigned selectSpecializationBound = 3;
+            Value* select = findRecentNodeMatching(
+                m_value->child(0), selectSpecializationBound,
+                [&] (Value* value) -> bool {
+                    return value->opcode() == Select
+                        && (value->child(1)->isConstant() && value->child(2)->isConstant());
+                });
+            if (select) {
+                specializeSelect(select);
                 break;
             }
             break;
@@ -1458,6 +1517,148 @@ private:
         }
     }
 
+    // Find a node that:
+    //     - functor(node) returns true.
+    //     - it's reachable from the given node via children.
+    //     - it's in the last "bound" slots in the current basic block.
+    // This algorithm is optimized under the assumption that the bound is small.
+    template<typename Functor>
+    Value* findRecentNodeMatching(Value* start, unsigned bound, const Functor& functor)
+    {
+        unsigned startIndex = bound < m_index ? m_index - bound : 0;
+        Value* result = nullptr;
+        start->walk(
+            [&] (Value* value) -> Value::WalkStatus {
+                bool found = false;
+                for (unsigned i = startIndex; i <= m_index; ++i) {
+                    if (m_block->at(i) == value)
+                        found = true;
+                }
+                if (!found)
+                    return Value::IgnoreChildren;
+
+                if (functor(value)) {
+                    result = value;
+                    return Value::Stop;
+                }
+
+                return Value::Continue;
+            });
+        return result;
+    }
+
+    // This specializes a sequence of code up to a Select. This doesn't work when we're at a
+    // terminal. It would be cool to fix that eventually. The main problem is that instead of
+    // splitting the block, we should just insert the then/else blocks. We'll have to create
+    // double the Phis and double the Upsilons. It'll probably be the sort of optimization that
+    // we want to do only after we've done loop optimizations, since this will *definitely*
+    // obscure things. In fact, even this simpler form of select specialization will possibly
+    // obscure other optimizations. It would be great to have two modes of strength reduction,
+    // one that does obscuring optimizations and runs late, and another that does not do
+    // obscuring optimizations and runs early.
+    // FIXME: Make select specialization handle branches.
+    // FIXME: Have a form of strength reduction that does no obscuring optimizations and runs
+    // early.
+    void specializeSelect(Value* source)
+    {
+        if (verbose)
+            dataLog("Specializing select: ", deepDump(m_proc, source), "\n");
+
+        // This mutates startIndex to account for the fact that m_block got the front of it
+        // chopped off.
+        BasicBlock* predecessor =
+            m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
+
+        // Splitting will commit the insertion set, which changes the exact position of the
+        // source. That's why we do the search after splitting.
+        unsigned startIndex = UINT_MAX;
+        for (unsigned i = predecessor->size(); i--;) {
+            if (predecessor->at(i) == source) {
+                startIndex = i;
+                break;
+            }
+        }
+        
+        RELEASE_ASSERT(startIndex != UINT_MAX);
+
+        // By BasicBlock convention, caseIndex == 0 => then, caseIndex == 1 => else.
+        static const unsigned numCases = 2;
+        BasicBlock* cases[numCases];
+        for (unsigned i = 0; i < numCases; ++i)
+            cases[i] = m_blockInsertionSet.insertBefore(m_block);
+
+        HashMap<Value*, Value*> mappings[2];
+
+        // Save things we want to know about the source.
+        Value* predicate = source->child(0);
+
+        for (unsigned i = 0; i < numCases; ++i)
+            mappings[i].add(source, source->child(1 + i));
+
+        auto cloneValue = [&] (Value* value) {
+            ASSERT(value != source);
+
+            for (unsigned i = 0; i < numCases; ++i) {
+                Value* clone = m_proc.clone(value);
+                for (Value*& child : clone->children()) {
+                    if (Value* newChild = mappings[i].get(child))
+                        child = newChild;
+                }
+                if (value->type() != Void)
+                    mappings[i].add(value, clone);
+
+                cases[i]->append(clone);
+                if (value->type() != Void)
+                    cases[i]->appendNew<UpsilonValue>(m_proc, value->origin(), clone, value);
+            }
+
+            value->replaceWithPhi();
+        };
+
+        // The jump that the splitter inserted is of no use to us.
+        predecessor->removeLast(m_proc);
+
+        // Hance the source, it's special.
+        for (unsigned i = 0; i < numCases; ++i) {
+            cases[i]->appendNew<UpsilonValue>(
+                m_proc, source->origin(), source->child(1 + i), source);
+        }
+        source->replaceWithPhi();
+        m_insertionSet.insertValue(m_index, source);
+
+        // Now handle all values between the source and the check.
+        for (unsigned i = startIndex + 1; i < predecessor->size(); ++i) {
+            Value* value = predecessor->at(i);
+            value->owner = nullptr;
+
+            cloneValue(value);
+
+            if (value->type() != Void)
+                m_insertionSet.insertValue(m_index, value);
+            else
+                m_proc.deleteValue(value);
+        }
+
+        // Finally, deal with the check.
+        cloneValue(m_value);
+
+        // Remove the values from the predecessor.
+        predecessor->values().resize(startIndex);
+        
+        predecessor->appendNew<ControlValue>(
+            m_proc, Branch, source->origin(), predicate,
+            FrequentedBlock(cases[0]), FrequentedBlock(cases[1]));
+
+        for (unsigned i = 0; i < numCases; ++i) {
+            cases[i]->appendNew<ControlValue>(
+                m_proc, Jump, m_value->origin(), FrequentedBlock(m_block));
+        }
+
+        m_changed = true;
+
+        predecessor->updatePredecessorsAfter();
+    }
+
     // Turn this: Add(constant, value)
     // Into this: Add(value, constant)
     //
@@ -1836,6 +2037,7 @@ private:
 
     Procedure& m_proc;
     InsertionSet m_insertionSet;
+    BlockInsertionSet m_blockInsertionSet;
     BasicBlock* m_block { nullptr };
     unsigned m_index { 0 };
     Value* m_value { nullptr };
diff --git a/Source/JavaScriptCore/b3/B3SSACalculator.cpp b/Source/JavaScriptCore/b3/B3SSACalculator.cpp
new file mode 100644 (file)
index 0000000..30692a9
--- /dev/null
@@ -0,0 +1,150 @@
+/*
+ * 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 "B3SSACalculator.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include <wtf/CommaPrinter.h>
+#include <wtf/ListDump.h>
+
+namespace JSC { namespace B3 {
+
+void SSACalculator::Variable::dump(PrintStream& out) const
+{
+    out.print("var", m_index);
+}
+
+void SSACalculator::Variable::dumpVerbose(PrintStream& out) const
+{
+    dump(out);
+    if (!m_blocksWithDefs.isEmpty()) {
+        out.print("(defs: ");
+        CommaPrinter comma;
+        for (BasicBlock* block : m_blocksWithDefs)
+            out.print(comma, *block);
+        out.print(")");
+    }
+}
+
+void SSACalculator::Def::dump(PrintStream& out) const
+{
+    out.print("def(", *m_variable, ", ", *m_block, ", ", pointerDump(m_value), ")");
+}
+
+SSACalculator::SSACalculator(Procedure& proc)
+    : m_data(proc.size())
+    , m_proc(proc)
+{
+}
+
+SSACalculator::~SSACalculator()
+{
+}
+
+void SSACalculator::reset()
+{
+    m_variables.clear();
+    m_defs.clear();
+    m_phis.clear();
+    for (unsigned blockIndex = m_data.size(); blockIndex--;) {
+        m_data[blockIndex].m_defs.clear();
+        m_data[blockIndex].m_phis.clear();
+    }
+}
+
+SSACalculator::Variable* SSACalculator::newVariable()
+{
+    return &m_variables.alloc(Variable(m_variables.size()));
+}
+
+SSACalculator::Def* SSACalculator::newDef(Variable* variable, BasicBlock* block, Value* value)
+{
+    Def* def = m_defs.add(Def(variable, block, value));
+    auto result = m_data[block].m_defs.add(variable, def);
+    if (result.isNewEntry)
+        variable->m_blocksWithDefs.append(block);
+    else
+        result.iterator->value = def;
+    return def;
+}
+
+SSACalculator::Def* SSACalculator::nonLocalReachingDef(BasicBlock* block, Variable* variable)
+{
+    return reachingDefAtTail(m_dominators->idom(block), variable);
+}
+
+SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
+{
+    for (; block; block = m_dominators->idom(block)) {
+        if (Def* def = m_data[block].m_defs.get(variable))
+            return def;
+    }
+    return nullptr;
+}
+
+void SSACalculator::dump(PrintStream& out) const
+{
+    out.print("<Variables: [");
+    CommaPrinter comma;
+    for (unsigned i = 0; i < m_variables.size(); ++i) {
+        out.print(comma);
+        m_variables[i].dumpVerbose(out);
+    }
+    out.print("], Defs: [");
+    comma = CommaPrinter();
+    for (Def* def : const_cast<SSACalculator*>(this)->m_defs)
+        out.print(comma, *def);
+    out.print("], Phis: [");
+    comma = CommaPrinter();
+    for (Def* def : const_cast<SSACalculator*>(this)->m_phis)
+        out.print(comma, *def);
+    out.print("], Block data: [");
+    comma = CommaPrinter();
+    for (unsigned blockIndex = 0; blockIndex < m_proc.size(); ++blockIndex) {
+        BasicBlock* block = m_proc[blockIndex];
+        if (!block)
+            continue;
+        
+        out.print(comma, *block, "=>(");
+        out.print("Defs: {");
+        CommaPrinter innerComma;
+        for (auto entry : m_data[block].m_defs)
+            out.print(innerComma, *entry.key, "->", *entry.value);
+        out.print("}, Phis: {");
+        innerComma = CommaPrinter();
+        for (Def* def : m_data[block].m_phis)
+            out.print(innerComma, *def);
+        out.print("})");
+    }
+    out.print("]>");
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3SSACalculator.h b/Source/JavaScriptCore/b3/B3SSACalculator.h
new file mode 100644 (file)
index 0000000..f576682
--- /dev/null
@@ -0,0 +1,171 @@
+/*
+ * 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 B3SSACalculator_h
+#define B3SSACalculator_h
+
+#if ENABLE(B3_JIT)
+
+#include "B3Dominators.h"
+#include "B3IndexMap.h"
+#include "B3ProcedureInlines.h"
+#include <wtf/Bag.h>
+#include <wtf/SegmentedVector.h>
+
+namespace JSC { namespace B3 {
+
+// SSACalculator provides a reusable tool for building SSA's. It's modeled after
+// DFG::SSACalculator.
+
+class SSACalculator {
+public:
+    SSACalculator(Procedure&);
+    ~SSACalculator();
+
+    void reset();
+
+    class Variable {
+    public:
+        unsigned index() const { return m_index; }
+        
+        void dump(PrintStream&) const;
+        void dumpVerbose(PrintStream&) const;
+        
+    private:
+        friend class SSACalculator;
+        
+        Variable()
+            : m_index(UINT_MAX)
+        {
+        }
+        
+        Variable(unsigned index)
+            : m_index(index)
+        {
+        }
+
+        Vector<BasicBlock*, 4> m_blocksWithDefs;
+        unsigned m_index;
+    };
+
+    class Def {
+    public:
+        Variable* variable() const { return m_variable; }
+        BasicBlock* block() const { return m_block; }
+        
+        Value* value() const { return m_value; }
+        
+        void dump(PrintStream&) const;
+        
+    private:
+        friend class SSACalculator;
+        
+        Def()
+            : m_variable(nullptr)
+            , m_block(nullptr)
+            , m_value(nullptr)
+        {
+        }
+        
+        Def(Variable* variable, BasicBlock* block, Value* value)
+            : m_variable(variable)
+            , m_block(block)
+            , m_value(value)
+        {
+        }
+        
+        Variable* m_variable;
+        BasicBlock* m_block;
+        Value* m_value;
+    };
+
+    Variable* newVariable();
+    Def* newDef(Variable*, BasicBlock*, Value*);
+
+    Variable* variable(unsigned index) { return &m_variables[index]; }
+
+    template<typename Functor>
+    void computePhis(const Functor& functor)
+    {
+        m_dominators = &m_proc.dominators();
+        for (Variable& variable : m_variables) {
+            m_dominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
+                variable.m_blocksWithDefs,
+                [&] (BasicBlock* block) -> bool {
+                    Value* phi = functor(&variable, block);
+                    if (!phi)
+                        return false;
+
+                    BlockData& data = m_data[block];
+                    Def* phiDef = m_phis.add(Def(&variable, block, phi));
+                    data.m_phis.append(phiDef);
+
+                    data.m_defs.add(&variable, phiDef);
+                    return true;
+                });
+        }
+    }
+
+    const Vector<Def*>& phisForBlock(BasicBlock* block)
+    {
+        return m_data[block].m_phis;
+    }
+    
+    // Ignores defs within the given block; it assumes that you've taken care of those
+    // yourself.
+    Def* nonLocalReachingDef(BasicBlock*, Variable*);
+    Def* reachingDefAtHead(BasicBlock* block, Variable* variable)
+    {
+        return nonLocalReachingDef(block, variable);
+    }
+    
+    // Considers the def within the given block, but only works at the tail of the block.
+    Def* reachingDefAtTail(BasicBlock*, Variable*);
+    
+    void dump(PrintStream&) const;
+    
+private:
+    SegmentedVector<Variable> m_variables;
+    Bag<Def> m_defs;
+    
+    Bag<Def> m_phis;
+    
+    struct BlockData {
+        HashMap<Variable*, Def*> m_defs;
+        Vector<Def*> m_phis;
+    };
+    
+    IndexMap<BasicBlock, BlockData> m_data;
+
+    Dominators* m_dominators { nullptr };
+    Procedure& m_proc;
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3SSACalculator_h
+
index bdf6c97..3a89842 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
@@ -36,9 +36,8 @@ enum class StackSlotKind : uint8_t {
     // slot.
     Locked,
 
-    // These stack slots could share space with other stack slots, provided that they aren't live
-    // at the same time. The compiler still has to do escape analysis, since these can be escaped
-    // explicitly in IR.
+    // These stack slots behave like variables. Undefined behavior happens if you store less than
+    // the width of the slot.
     Anonymous
 
     // FIXME: We should add a third mode, which means that the stack slot will be read asynchronously
index e404e64..650ea30 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,6 +39,11 @@ void StackSlotValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.print(comma, "byteSize = ", m_byteSize, ", kind = ", m_kind);
 }
 
+Value* StackSlotValue::cloneImpl() const
+{
+    return new StackSlotValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 6904b5e..dbac604 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
@@ -59,6 +59,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Air::StackSlot;
     friend class Procedure;
index 759af9f..5e09d04 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
@@ -63,6 +63,11 @@ void SwitchValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     out.print(comma, "fallThrough = ", fallThrough());
 }
 
+Value* SwitchValue::cloneImpl() const
+{
+    return new SwitchValue(*this);
+}
+
 SwitchValue::SwitchValue(
     unsigned index, Origin origin, Value* child, const FrequentedBlock& fallThrough)
     : ControlValue(index, Switch, Void, origin, child)
index 5f17087..d0d5e1f 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
@@ -116,6 +116,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Procedure;
 
index 4c53f8d..c87432f 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
@@ -45,6 +45,11 @@ void UpsilonValue::dumpMeta(CommaPrinter& comma, PrintStream& out) const
     }
 }
 
+Value* UpsilonValue::cloneImpl() const
+{
+    return new UpsilonValue(*this);
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index 9d5ca6a..0fbbbf7 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
@@ -49,6 +49,8 @@ public:
 protected:
     void dumpMeta(CommaPrinter&, PrintStream&) const override;
 
+    Value* cloneImpl() const override;
+
 private:
     friend class Procedure;
 
@@ -59,10 +61,8 @@ private:
         : Value(index, CheckedOpcode, Upsilon, Void, origin, value)
         , m_phi(phi)
     {
-        if (phi) {
+        if (phi)
             ASSERT(value->type() == phi->type());
-            ASSERT(phi->opcode() == Phi);
-        }
     }
 
     Value* m_phi;
index aef24e8..29b506c 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
@@ -352,6 +352,7 @@ public:
             case Upsilon:
                 VALIDATE(value->numChildren() == 1, ("At ", *value));
                 VALIDATE(value->as<UpsilonValue>()->phi(), ("At ", *value));
+                VALIDATE(value->as<UpsilonValue>()->phi()->opcode() == Phi, ("At ", *value));
                 VALIDATE(value->child(0)->type() == value->as<UpsilonValue>()->phi()->type(), ("At ", *value));
                 VALIDATE(valueInProc.contains(value->as<UpsilonValue>()->phi()), ("At ", *value));
                 break;
index a41c9be..91c2335 100644 (file)
@@ -89,18 +89,42 @@ void Value::replaceWithNop()
     this->owner = owner;
 }
 
+void Value::replaceWithPhi()
+{
+    if (m_type == Void) {
+        replaceWithNop();
+        return;
+    }
+    
+    unsigned index = m_index;
+    Origin origin = m_origin;
+    BasicBlock* owner = this->owner;
+    Type type = m_type;
+
+    this->Value::~Value();
+
+    new (this) Value(index, Phi, type, origin);
+
+    this->owner = owner;
+}
+
 void Value::dump(PrintStream& out) const
 {
     out.print(dumpPrefix, m_index);
 }
 
+Value* Value::cloneImpl() const
+{
+    return new Value(*this);
+}
+
 void Value::dumpChildren(CommaPrinter& comma, PrintStream& out) const
 {
     for (Value* child : children())
         out.print(comma, pointerDump(child));
 }
 
-void Value::deepDump(const Procedure& proc, PrintStream& out) const
+void Value::deepDump(const Procedure* proc, PrintStream& out) const
 {
     out.print(m_type, " ", *this, " = ", m_opcode);
 
index d0bec64..d3a6ec5 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
@@ -42,10 +42,10 @@ namespace JSC { namespace B3 {
 
 class BasicBlock;
 class CheckValue;
+class PhiChildren;
 class Procedure;
 
 class JS_EXPORT_PRIVATE Value {
-    WTF_MAKE_NONCOPYABLE(Value);
     WTF_MAKE_FAST_ALLOCATED;
 public:
     typedef Vector<Value*, 3> AdjacencyList;
@@ -84,9 +84,10 @@ public:
 
     void replaceWithIdentity(Value*);
     void replaceWithNop();
+    void replaceWithPhi();
 
     void dump(PrintStream&) const;
-    void deepDump(const Procedure&, PrintStream&) const;
+    void deepDump(const Procedure*, PrintStream&) const;
 
     // This is how you cast Values. For example, if you want to do something provided that we have a
     // ArgumentRegValue, you can do:
@@ -204,7 +205,22 @@ public:
     // of Identity's.
     void performSubstitution();
 
+    // Walk the ancestors of this value (i.e. the graph of things it transitively uses). This
+    // either walks phis or not, depending on whether PhiChildren is null. Your callback gets
+    // called with the signature:
+    //
+    //     (Value*) -> WalkStatus
+    enum WalkStatus {
+        Continue,
+        IgnoreChildren,
+        Stop
+    };
+    template<typename Functor>
+    void walk(const Functor& functor, PhiChildren* = nullptr);
+
 protected:
+    virtual Value* cloneImpl() const;
+    
     virtual void dumpChildren(CommaPrinter&, PrintStream&) const;
     virtual void dumpMeta(CommaPrinter&, PrintStream&) const;
 
@@ -220,6 +236,9 @@ private:
 
 protected:
     enum CheckedOpcodeTag { CheckedOpcode };
+
+    Value(const Value&) = default;
+    Value& operator=(const Value&) = default;
     
     // Instantiate values via Procedure.
     // This form requires specifying the type explicitly:
@@ -315,7 +334,7 @@ public:
 
 class DeepValueDump {
 public:
-    DeepValueDump(const Procedure& proc, const Value* value)
+    DeepValueDump(const Procedure* proc, const Value* value)
         : m_proc(proc)
         , m_value(value)
     {
@@ -330,13 +349,17 @@ public:
     }
 
 private:
-    const Procedure& m_proc;
+    const Procedure* m_proc;
     const Value* m_value;
 };
 
 inline DeepValueDump deepDump(const Procedure& proc, const Value* value)
 {
-    return DeepValueDump(proc, value);
+    return DeepValueDump(&proc, value);
+}
+inline DeepValueDump deepDump(const Value* value)
+{
+    return DeepValueDump(nullptr, value);
 }
 
 } } // namespace JSC::B3
index 8c67c90..86cb8f6 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
 #include "B3ConstDoubleValue.h"
 #include "B3ConstFloatValue.h"
 #include "B3PatchpointValue.h"
+#include "B3PhiChildren.h"
 #include "B3Procedure.h"
 #include "B3Value.h"
+#include <wtf/GraphNodeWorklist.h>
 
 namespace JSC { namespace B3 {
 
@@ -204,6 +206,29 @@ inline T Value::asNumber() const
     }
 }
 
+template<typename Functor>
+void Value::walk(const Functor& functor, PhiChildren* phiChildren)
+{
+    GraphNodeWorklist<Value*> worklist;
+    worklist.push(this);
+    while (Value* value = worklist.pop()) {
+        WalkStatus status = functor(value);
+        switch (status) {
+        case Continue:
+            if (value->opcode() == Phi) {
+                if (phiChildren)
+                    worklist.pushAll(phiChildren->at(value).values());
+            } else
+                worklist.pushAll(value->children());
+            break;
+        case IgnoreChildren:
+            break;
+        case Stop:
+            return;
+        }
+    }
+}
+
 } } // namespace JSC::B3
 
 #endif // ENABLE(B3_JIT)
index ddddd7c..8983e5c 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
 
 namespace JSC { namespace B3 {
 
+ValueKey ValueKey::intConstant(Type type, int64_t value)
+{
+    switch (type) {
+    case Int32:
+        return ValueKey(Const32, Int32, value);
+    case Int64:
+        return ValueKey(Const64, Int64, value);
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+        return ValueKey();
+    }
+}
+
 void ValueKey::dump(PrintStream& out) const
 {
     out.print(m_type, " ", m_opcode, "(", u.indices[0], ", ", u.indices[1], ", ", u.indices[2], ")");
index f83e3e6..6efd5b5 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
@@ -85,6 +85,8 @@ public:
         u.floatValue = value;
     }
 
+    static ValueKey intConstant(Type type, int64_t value);
+
     Opcode opcode() const { return m_opcode; }
     Type type() const { return m_type; }
     unsigned childIndex(unsigned index) const { return u.indices[index]; }
index ebb15e9..fadaa61 100644 (file)
@@ -28,6 +28,7 @@
 
 #if ENABLE(B3_JIT)
 
+#include "AirArg.h"
 #include "AirBasicBlock.h"
 #include "AirSpecial.h"
 #include "AirStackSlot.h"
index 9d87828..cda8b6d 100644 (file)
@@ -53,9 +53,10 @@ bool reportStats = false;
 template<typename IndexType>
 class AbstractColoringAllocator {
 public:
-    AbstractColoringAllocator(const Vector<Reg>& regsInPriorityOrder, IndexType lastPrecoloredRegisterIndex, unsigned tmpArraySize)
+    AbstractColoringAllocator(const Vector<Reg>& regsInPriorityOrder, IndexType lastPrecoloredRegisterIndex, unsigned tmpArraySize, const HashSet<unsigned>& unspillableTmp)
         : m_regsInPriorityOrder(regsInPriorityOrder)
         , m_lastPrecoloredRegisterIndex(lastPrecoloredRegisterIndex)
+        , m_unspillableTmps(unspillableTmp)
     {
         initializeDegrees(tmpArraySize);
 
@@ -90,7 +91,7 @@ protected:
                 continue;
 
             if (degree >= m_regsInPriorityOrder.size())
-                m_spillWorklist.add(i);
+                addToSpill(i);
             else if (!m_moveList[i].isEmpty())
                 m_freezeWorklist.add(i);
             else
@@ -98,6 +99,14 @@ protected:
         }
     }
 
+    void addToSpill(unsigned toSpill)
+    {
+        if (m_unspillableTmps.contains(toSpill))
+            return;
+
+        m_spillWorklist.add(toSpill);
+    }
+
     // Low-degree vertex can always be colored: just pick any of the color taken by any
     // other adjacent verices.
     // The "Simplify" phase takes a low-degree out of the interference graph to simplify it.
@@ -361,7 +370,7 @@ private:
         });
 
         if (m_degrees[u] >= m_regsInPriorityOrder.size() && m_freezeWorklist.remove(u))
-            m_spillWorklist.add(u);
+            addToSpill(u);
     }
 
     bool canBeSafelyCoalesced(IndexType u, IndexType v)
@@ -625,6 +634,8 @@ protected:
 
     // The mapping of Tmp to their alias for Moves that are always coalescing regardless of spilling.
     Vector<IndexType, 0, UnsafeVectorOverflow> m_coalescedTmpsAtSpill;
+    
+    const HashSet<unsigned>& m_unspillableTmps;
 };
 
 // This perform all the tasks that are specific to certain register type.
@@ -632,11 +643,10 @@ template<Arg::Type type>
 class ColoringAllocator : public AbstractColoringAllocator<unsigned> {
 public:
     ColoringAllocator(Code& code, TmpWidth& tmpWidth, const UseCounts<Tmp>& useCounts, const HashSet<unsigned>& unspillableTmp)
-        : AbstractColoringAllocator<unsigned>(regsInPriorityOrder(type), AbsoluteTmpMapper<type>::lastMachineRegisterIndex(), tmpArraySize(code))
+        : AbstractColoringAllocator<unsigned>(regsInPriorityOrder(type), AbsoluteTmpMapper<type>::lastMachineRegisterIndex(), tmpArraySize(code), unspillableTmp)
         , m_code(code)
         , m_tmpWidth(tmpWidth)
         , m_useCounts(useCounts)
-        , m_unspillableTmps(unspillableTmp)
     {
         initializePrecoloredTmp();
         build();
@@ -927,10 +937,8 @@ private:
 
         auto iterator = m_spillWorklist.begin();
 
-        while (iterator != m_spillWorklist.end() && m_unspillableTmps.contains(*iterator))
-            ++iterator;
-
-        RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
+        RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "selectSpill() called when there was no spill.");
+        RELEASE_ASSERT_WITH_MESSAGE(!m_unspillableTmps.contains(*iterator), "trying to spill unspillable tmp");
 
         // Higher score means more desirable to spill. Lower scores maximize the likelihood that a tmp
         // gets a register.
@@ -945,12 +953,15 @@ private:
 
             // All else being equal, the score should be inversely related to the number of warm uses and
             // defs.
-            const UseCounts<Tmp>::Counts& counts = m_useCounts[tmp];
-            double uses = counts.numWarmUses + counts.numDefs;
+            const UseCounts<Tmp>::Counts* counts = m_useCounts[tmp];
+            if (!counts)
+                return std::numeric_limits<double>::infinity();
+            
+            double uses = counts->numWarmUses + counts->numDefs;
 
             // If it's a constant, then it's not as bad to spill. We can rematerialize it in many
             // cases.
-            if (counts.numConstDefs == counts.numDefs)
+            if (counts->numConstDefs == counts->numDefs)
                 uses /= 2;
 
             return degree / uses;
@@ -961,11 +972,9 @@ private:
 
         ++iterator;
         for (;iterator != m_spillWorklist.end(); ++iterator) {
-            if (m_unspillableTmps.contains(*iterator))
-                continue;
-
             double tmpScore = score(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*iterator));
             if (tmpScore > maxScore) {
+                ASSERT(!m_unspillableTmps.contains(*iterator));
                 victimIterator = iterator;
                 maxScore = tmpScore;
             }
@@ -1058,7 +1067,6 @@ private:
     TmpWidth& m_tmpWidth;
     // FIXME: spilling should not type specific. It is only a side effect of using UseCounts.
     const UseCounts<Tmp>& m_useCounts;
-    const HashSet<unsigned>& m_unspillableTmps;
 };
 
 class IteratedRegisterCoalescing {
index 8218fde..0c39da3 100644 (file)
@@ -97,11 +97,12 @@ public:
         }
     }
 
-    const Counts& operator[](const Thing& arg) const
+    const Counts* operator[](const Thing& arg) const
     {
-        auto iterator = m_counts.find(arg);
-        ASSERT(iterator != m_counts.end());
-        return iterator->value;
+        auto iter = m_counts.find(arg);
+        if (iter == m_counts.end())
+            return nullptr;
+        return &iter->value;
     }
 
     void dump(PrintStream& out) const
index 2a86849..9043c00 100644 (file)
@@ -9065,6 +9065,121 @@ void testSelectInvert()
     CHECK(invoke<intptr_t>(*code, 43, 642462, 32533) == 32533);
 }
 
+void testCheckSelect()
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+
+    CheckValue* check = root->appendNew<CheckValue>(
+        proc, Check, Origin(),
+        root->appendNew<Value>(
+            proc, Add, Origin(),
+            root->appendNew<Value>(
+                proc, Select, Origin(),
+                root->appendNew<Value>(
+                    proc, BitAnd, Origin(),
+                    root->appendNew<Value>(
+                        proc, Trunc, Origin(),
+                        root->appendNew<ArgumentRegValue>(
+                            proc, Origin(), GPRInfo::argumentGPR0)),
+                    root->appendNew<Const32Value>(proc, Origin(), 0xff)),
+                root->appendNew<ConstPtrValue>(proc, Origin(), -42),
+                root->appendNew<ConstPtrValue>(proc, Origin(), 35)),
+            root->appendNew<ConstPtrValue>(proc, Origin(), 42)));
+    unsigned generationCount = 0;
+    check->setGenerator(
+        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
+            AllowMacroScratchRegisterUsage allowScratch(jit);
+
+            generationCount++;
+            jit.move(CCallHelpers::TrustedImm32(666), GPRInfo::returnValueGPR);
+            jit.emitFunctionEpilogue();
+            jit.ret();
+        });
+    
+    root->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        root->appendNew<Const32Value>(proc, Origin(), 0));
+
+    auto code = compile(proc);
+    CHECK(generationCount == 1);
+    CHECK(invoke<int>(*code, true) == 0);
+    CHECK(invoke<int>(*code, false) == 666);
+}
+
+void testCheckSelectCheckSelect()
+{
+    Procedure proc;
+    BasicBlock* root = proc.addBlock();
+
+    CheckValue* check = root->appendNew<CheckValue>(
+        proc, Check, Origin(),
+        root->appendNew<Value>(
+            proc, Add, Origin(),
+            root->appendNew<Value>(
+                proc, Select, Origin(),
+                root->appendNew<Value>(
+                    proc, BitAnd, Origin(),
+                    root->appendNew<Value>(
+                        proc, Trunc, Origin(),
+                        root->appendNew<ArgumentRegValue>(
+                            proc, Origin(), GPRInfo::argumentGPR0)),
+                    root->appendNew<Const32Value>(proc, Origin(), 0xff)),
+                root->appendNew<ConstPtrValue>(proc, Origin(), -42),
+                root->appendNew<ConstPtrValue>(proc, Origin(), 35)),
+            root->appendNew<ConstPtrValue>(proc, Origin(), 42)));
+
+    unsigned generationCount = 0;
+    check->setGenerator(
+        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
+            AllowMacroScratchRegisterUsage allowScratch(jit);
+
+            generationCount++;
+            jit.move(CCallHelpers::TrustedImm32(666), GPRInfo::returnValueGPR);
+            jit.emitFunctionEpilogue();
+            jit.ret();
+        });
+    
+    CheckValue* check2 = root->appendNew<CheckValue>(
+        proc, Check, Origin(),
+        root->appendNew<Value>(
+            proc, Add, Origin(),
+            root->appendNew<Value>(
+                proc, Select, Origin(),
+                root->appendNew<Value>(
+                    proc, BitAnd, Origin(),
+                    root->appendNew<Value>(
+                        proc, Trunc, Origin(),
+                        root->appendNew<ArgumentRegValue>(
+                            proc, Origin(), GPRInfo::argumentGPR1)),
+                    root->appendNew<Const32Value>(proc, Origin(), 0xff)),
+                root->appendNew<ConstPtrValue>(proc, Origin(), -43),
+                root->appendNew<ConstPtrValue>(proc, Origin(), 36)),
+            root->appendNew<ConstPtrValue>(proc, Origin(), 43)));
+
+    unsigned generationCount2 = 0;
+    check2->setGenerator(
+        [&] (CCallHelpers& jit, const StackmapGenerationParams&) {
+            AllowMacroScratchRegisterUsage allowScratch(jit);
+
+            generationCount2++;
+            jit.move(CCallHelpers::TrustedImm32(667), GPRInfo::returnValueGPR);
+            jit.emitFunctionEpilogue();
+            jit.ret();
+        });
+    
+    root->appendNew<ControlValue>(
+        proc, Return, Origin(),
+        root->appendNew<Const32Value>(proc, Origin(), 0));
+
+    auto code = compile(proc);
+    CHECK(generationCount == 1);
+    CHECK(generationCount2 == 1);
+    CHECK(invoke<int>(*code, true, true) == 0);
+    CHECK(invoke<int>(*code, false, true) == 666);
+    CHECK(invoke<int>(*code, true, false) == 667);
+}
+
 void testPowDoubleByIntegerLoop(double xOperand, int32_t yOperand)
 {
     Procedure proc;
@@ -10074,8 +10189,6 @@ void run(const char* filter)
     RUN(testBranchLoad16Z());
 
     RUN(testComplex(64, 128));
-    RUN(testComplex(64, 256));
-    RUN(testComplex(64, 384));
     RUN(testComplex(4, 128));
     RUN(testComplex(4, 256));
     RUN(testComplex(4, 384));
@@ -10524,6 +10637,8 @@ void run(const char* filter)
     RUN(testSelectFold(42));
     RUN(testSelectFold(43));
     RUN(testSelectInvert());
+    RUN(testCheckSelect());
+    RUN(testCheckSelectCheckSelect());
     RUN_BINARY(testPowDoubleByIntegerLoop, floatingPointOperands<double>(), int64Operands());
 
     RUN(testTruncOrHigh());
index 5756e46..b011b00 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-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
@@ -344,6 +344,8 @@ typedef const char* optionString;
     v(double, rareBlockPenalty, 0.001, nullptr) \
     v(bool, airSpillsEverything, false, nullptr) \
     v(bool, logAirRegisterPressure, false, nullptr) \
+    v(unsigned, maxB3TailDupBlockSize, 3, nullptr) \
+    v(unsigned, maxB3TailDupBlockSuccessors, 3, nullptr) \
     \
     v(bool, useDollarVM, false, "installs the $vm debugging tool in global objects") \
     v(optionString, functionOverrides, nullptr, "file with debugging overrides for function bodies") \
index d828d15..ee7b151 100644 (file)
@@ -1,3 +1,16 @@
+2016-01-19  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should have basic path specialization
+        https://bugs.webkit.org/show_bug.cgi?id=153200
+
+        Reviewed by Benjamin Poulain.
+
+        * wtf/GraphNodeWorklist.h:
+        (WTF::GraphNodeWorklist::push):
+        (WTF::GraphNodeWorklist::pushAll):
+        (WTF::GraphNodeWorklist::isEmpty):
+        (WTF::GraphNodeWorklist::notEmpty):
+
 2016-01-20  Said Abou-Hallawa  <sabouhallawa@apple.com>
 
         Refactor AtomicStringKeyedMRUCache to be a generic LRU cache
index 42f507c..b5f2dba 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
@@ -45,6 +45,13 @@ public:
         return true;
     }
 
+    template<typename Iterable>
+    void pushAll(const Iterable& iterable)
+    {
+        for (Node node : iterable)
+            push(node);
+    }
+
     bool isEmpty() const { return m_stack.isEmpty(); }
     bool notEmpty() const { return !m_stack.isEmpty(); }
     
index 498e639..50f17bd 100755 (executable)
@@ -535,7 +535,7 @@ def sortByMode(list)
     end
 end
 
-def summary(mode)
+def summary(mode, order)
     remaining = screenWidth
     
     # Figure out how many columns we need for the code block names, and for counts
@@ -618,7 +618,14 @@ def summary(mode)
     puts
     $bytecodes.sort {
         | a, b |
-        b.totalMaxTopExecutionCount <=> a.totalMaxTopExecutionCount
+        case order
+        when :bytecode
+            b.totalMaxTopExecutionCount <=> a.totalMaxTopExecutionCount
+        when :machine
+            b.totalMaxBottomExecutionCount <=> a.totalMaxBottomExecutionCount
+        else
+            raise
+        end
     }.each {
         | bytecode |
         print(center(bytecode.name(hashCols), hashCols))
@@ -738,9 +745,13 @@ def executeCommand(*commandArray)
     when "quit", "q", "exit"
         exit 0
     when "summary", "s"
-        summary(:summary)
+        summary(:summary, :bytecode)
     when "full", "f"
-        summary(:full)
+        if args[0] and (args[0] == "m" or args[0] == "machine")
+            summary(:full, :machine)
+        else
+            summary(:full, :bytecode)
+        end
     when "source"
         if args.length != 1
             puts "Usage: source <code block hash>"