Attachment 339163 Details for Bug 185060 – mostly works, not a speed-up

[patch] mostly works, not a speed-up

blah.patch (text/plain), 64.69 KB, created by Filip Pizlo on 2018-04-30 17:03:10 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2018-04-30 17:03:10 PDT

Size: 64.69 KB

patch

obsolete

>Index: JSTests/microbenchmarks/path-specialization-loop-unswitching-big.js
>===================================================================
>--- JSTests/microbenchmarks/path-specialization-loop-unswitching-big.js	(nonexistent)
>+++ JSTests/microbenchmarks/path-specialization-loop-unswitching-big.js	(working copy)
>@@ -0,0 +1,29 @@
>+// benefitOverCost = 1
>+
>+function foo(o)
>+{
>+    var a = 0;
>+    for (var i = 0; i < 100; ++i) {
>+        var value;
>+        if (o.p)
>+            value = o.f;
>+        else
>+            value = o.g;
>+        a += value;
>+        a *= 1.5;
>+        a += o.x;
>+        if (o.p)
>+            o.f = i;
>+        else
>+            o.g = i;
>+    }
>+    return a;
>+}
>+
>+noInline(foo);
>+
>+for (var i = 0; i < 100000; ++i) {
>+    var result = foo(i & 1 ? {p:true, f:42, x:1} : {p:false, x:1, g:42});
>+    if (result != 19514936521690325000)
>+        throw "Error: bad result: " + result;
>+}
>Index: JSTests/microbenchmarks/path-specialization-loop-unswitching-impossible.js
>===================================================================
>--- JSTests/microbenchmarks/path-specialization-loop-unswitching-impossible.js	(nonexistent)
>+++ JSTests/microbenchmarks/path-specialization-loop-unswitching-impossible.js	(working copy)
>@@ -0,0 +1,34 @@
>+// benefitOverCost = 1.1875
>+
>+function bar(value)
>+{
>+    return value;
>+}
>+
>+noInline(bar);
>+
>+function foo(o)
>+{
>+    var a = 0;
>+    for (var i = 0; i < 100; ++i) {
>+        var value;
>+        if (o.p)
>+            value = o.f;
>+        else
>+            value = o.g;
>+        a += bar(value);
>+        if (o.p)
>+            o.f = i;
>+        else
>+            o.g = i;
>+    }
>+    return a;
>+}
>+
>+noInline(foo);
>+
>+for (var i = 0; i < 100000; ++i) {
>+    var result = foo(i & 1 ? {p:true, f:42} : {p:false, g:42});
>+    if (result != 4893)
>+        throw "Error: bad result: " + result;
>+}
>Index: JSTests/microbenchmarks/path-specialization-loop-unswitching.js
>===================================================================
>--- JSTests/microbenchmarks/path-specialization-loop-unswitching.js	(nonexistent)
>+++ JSTests/microbenchmarks/path-specialization-loop-unswitching.js	(working copy)
>@@ -0,0 +1,29 @@
>+// benefitOverCost = 1.1875
>+
>+function foo(o)
>+{
>+    var a = 0;
>+    var b = 0;
>+    for (var i = 0; i < 100; ++i) {
>+        var value;
>+        if (o.p)
>+            value = o.f;
>+        else
>+            value = o.g;
>+        a += value;
>+        b += i;
>+        if (o.p)
>+            o.f = i;
>+        else
>+            o.g = i;
>+    }
>+    return a - b;
>+}
>+
>+noInline(foo);
>+
>+for (var i = 0; i < 100000; ++i) {
>+    var result = foo(i & 1 ? {p:true, f:42} : {p:false, g:42});
>+    if (result != -57)
>+        throw "Error: bad result: " + result;
>+}
>Index: JSTests/microbenchmarks/path-specialization-multi-by-offset-smaller.js
>===================================================================
>--- JSTests/microbenchmarks/path-specialization-multi-by-offset-smaller.js	(nonexistent)
>+++ JSTests/microbenchmarks/path-specialization-multi-by-offset-smaller.js	(working copy)
>@@ -0,0 +1,18 @@
>+// benefitOverCost = 2
>+
>+function foo(o) {
>+    var result = 0;
>+    for (var i = 0; i < 100; ++i) {
>+        result = (result + o.f) | 0;
>+        o.f = i;
>+    }
>+    return result;
>+}
>+
>+noInline(foo);
>+
>+for (var i = 0; i < 100000; ++i) {
>+    var result = foo(i & 1 ? {f:42} : {e:41, f:42});
>+    if (result != (99 * 98) / 2 + 42)
>+        throw "Error: bad result: " + result;
>+}
>Index: JSTests/microbenchmarks/path-specialization-multi-by-offset.js
>===================================================================
>--- JSTests/microbenchmarks/path-specialization-multi-by-offset.js	(nonexistent)
>+++ JSTests/microbenchmarks/path-specialization-multi-by-offset.js	(working copy)
>@@ -0,0 +1,18 @@
>+// benefitOverCost = 2
>+
>+function foo(o) {
>+    var result = 0;
>+    for (var i = 0; i < 100; ++i) {
>+        result += o.f;
>+        o.f = i;
>+    }
>+    return result;
>+}
>+
>+noInline(foo);
>+
>+for (var i = 0; i < 100000; ++i) {
>+    var result = foo(i & 1 ? {f:42} : {e:41, f:42});
>+    if (result != (99 * 98) / 2 + 42)
>+        throw "Error: bad result: " + result;
>+}
>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 231128)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,96 @@
>+2018-04-28  Filip Pizlo  <fpizlo@apple.com>
>+
>+        B3 should have generalized path specialization
>+        https://bugs.webkit.org/show_bug.cgi?id=185060
>+
>+        Reviewed by NOBODY (OOPS!).
>+        
>+        This adds a new phase, called specializePaths, that duplicates code in order to remove
>+        branches. It's a superset of loop unswitching that will also handle strait paths from one
>+        branch to another. For example, it will convert:
>+        
>+            if (p)
>+                foo
>+            else
>+                bar
>+            thingy
>+            if (p)
>+                fuzz
>+            else
>+                buzz
>+        
>+        into:
>+        
>+            if (p) {
>+                foo
>+                thingy
>+                fuzz
>+            } else {
>+                bar
>+                thingy
>+                buzz
>+            }
>+        
>+        Provided that the benefit (elimination of the second branch) outweighs the cost (the space
>+        cost of thingy being emitted twice). This will do a O(blocks^3) search to find the most
>+        profitable such specializations to do, and it will only do the most profitable of those. It
>+        will never duplicate code more than once.
>+        
>+        The search considers all duplication paths (called traces in the phase's code) that can be
>+        formed by:
>+        
>+        - Pairs of branches on the same predicate, where one branch dominates the other.
>+        
>+        - Hoisting a branch, or some other trace, out of a loop.
>+        
>+        I believe that in the worst case, this is a O(blocks^3) search, if you created a program
>+        whose loop depth was O(blocks) and you had O(blocks) different traces inside the loop body.
>+        That's certainly possible but not very probable.
>+        
>+        I haven't tested this yet. It's still a work in progress.
>+
>+        * JavaScriptCore.xcodeproj/project.pbxproj:
>+        * Sources.txt:
>+        * b3/B3BreakCriticalEdges.cpp:
>+        (JSC::B3::breakCriticalEdges):
>+        * b3/B3FixSSA.cpp:
>+        (JSC::B3::fixSSA):
>+        * b3/B3Generate.cpp:
>+        (JSC::B3::generateToAir):
>+        * b3/B3Procedure.cpp:
>+        * b3/B3Procedure.h:
>+        (JSC::B3::Procedure::takeBlock):
>+        * b3/B3SpecializePaths.cpp: Added.
>+        (JSC::B3::SpecializePaths::SpecializePaths):
>+        (JSC::B3::SpecializePaths::run):
>+        (JSC::B3::SpecializePaths::createHoistingTargets):
>+        (JSC::B3::SpecializePaths::findBranches):
>+        (JSC::B3::SpecializePaths::findBlocksDuplicatedForPredicates):
>+        (JSC::B3::SpecializePaths::createTracesByDominantRedundancy):
>+        (JSC::B3::SpecializePaths::createTracesByHoisting):
>+        (JSC::B3::SpecializePaths::closeTrace):
>+        (JSC::B3::SpecializePaths::chooseTraceOrder):
>+        (JSC::B3::SpecializePaths::simulateDuplicationAndPruneTraces):
>+        (JSC::B3::SpecializePaths::demoteAppropriateValues):
>+        (JSC::B3::SpecializePaths::duplicateTraces):
>+        (JSC::B3::SpecializePaths::Trace::benefitOverCost const):
>+        (JSC::B3::specializePaths):
>+        * b3/B3SpecializePaths.h: Added.
>+        * b3/B3ValueInBlock.cpp: Added.
>+        (JSC::B3::ValueInBlock::dump const):
>+        * b3/B3ValueInBlock.h: Added.
>+        (JSC::B3::ValueInBlock::ValueInBlock):
>+        (JSC::B3::ValueInBlock::block const):
>+        (JSC::B3::ValueInBlock::index const):
>+        (JSC::B3::ValueInBlock::value const):
>+        (JSC::B3::ValueInBlock::operator== const):
>+        (JSC::B3::ValueInBlock::operator!= const):
>+        (JSC::B3::ValueInBlock::operator bool const):
>+        (JSC::B3::ValueInBlock::hash const):
>+        (JSC::B3::ValueInBlock::isHashTableDeletedValue const):
>+        (JSC::B3::ValueInBlockHash::hash):
>+        (JSC::B3::ValueInBlockHash::equal):
>+
> 2018-04-27  Yusuke Suzuki  <utatane.tea@gmail.com>
> 
>         [JSC][ARM64][Linux] Add collectCPUFeatures using auxiliary vector
>Index: Source/JavaScriptCore/Sources.txt
>===================================================================
>--- Source/JavaScriptCore/Sources.txt	(revision 231128)
>+++ Source/JavaScriptCore/Sources.txt	(working copy)
>@@ -153,6 +153,7 @@ b3/B3ReduceDoubleToFloat.cpp
> b3/B3ReduceStrength.cpp
> b3/B3SSACalculator.cpp
> b3/B3SlotBaseValue.cpp
>+b3/B3SpecializePaths.cpp
> b3/B3StackmapGenerationParams.cpp
> b3/B3StackmapSpecial.cpp
> b3/B3StackmapValue.cpp
>@@ -165,6 +166,7 @@ b3/B3UpsilonValue.cpp
> b3/B3UseCounts.cpp
> b3/B3Validate.cpp
> b3/B3Value.cpp
>+b3/B3ValueInBlock.cpp
> b3/B3ValueKey.cpp
> b3/B3ValueRep.cpp
> b3/B3Variable.cpp
>Index: Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
>===================================================================
>--- Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj	(revision 231128)
>+++ Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj	(working copy)
>@@ -695,6 +695,8 @@
> 		0FF4B4C71E8893C500DBBE86 /* AirCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C61E8893BF00DBBE86 /* AirCFG.h */; };
> 		0FF4B4CB1E889D7E00DBBE86 /* B3VariableLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */; };
> 		0FF60AC216740F8300029779 /* ReduceWhitespace.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF60AC016740F8100029779 /* ReduceWhitespace.h */; settings = {ATTRIBUTES = (Private, ); }; };
>+		0FF68C1D20940EBC00FC5DDC /* B3SpecializePaths.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF68C1A20940EB700FC5DDC /* B3SpecializePaths.h */; };
>+		0FF68C1E20940EBF00FC5DDC /* B3ValueInBlock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF68C1B20940EB700FC5DDC /* B3ValueInBlock.h */; };
> 		0FF7168C15A3B235008F5DAA /* PropertyOffset.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF7168A15A3B231008F5DAA /* PropertyOffset.h */; settings = {ATTRIBUTES = (Private, ); }; };
> 		0FF729A5166AD351000F5BA3 /* ProfilerBytecode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF72993166AD347000F5BA3 /* ProfilerBytecode.h */; settings = {ATTRIBUTES = (Private, ); }; };
> 		0FF729B9166AD360000F5BA3 /* ProfilerBytecodes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF72995166AD347000F5BA3 /* ProfilerBytecodes.h */; settings = {ATTRIBUTES = (Private, ); }; };
>@@ -2961,6 +2963,10 @@
> 		0FF4B4C91E889D7800DBBE86 /* B3VariableLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3VariableLiveness.h; path = b3/B3VariableLiveness.h; sourceTree = "<group>"; };
> 		0FF60ABF16740F8100029779 /* ReduceWhitespace.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ReduceWhitespace.cpp; sourceTree = "<group>"; };
> 		0FF60AC016740F8100029779 /* ReduceWhitespace.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ReduceWhitespace.h; sourceTree = "<group>"; };
>+		0FF68C1920940EB700FC5DDC /* B3SpecializePaths.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3SpecializePaths.cpp; path = b3/B3SpecializePaths.cpp; sourceTree = "<group>"; };
>+		0FF68C1A20940EB700FC5DDC /* B3SpecializePaths.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3SpecializePaths.h; path = b3/B3SpecializePaths.h; sourceTree = "<group>"; };
>+		0FF68C1B20940EB700FC5DDC /* B3ValueInBlock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ValueInBlock.h; path = b3/B3ValueInBlock.h; sourceTree = "<group>"; };
>+		0FF68C1C20940EB700FC5DDC /* B3ValueInBlock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3ValueInBlock.cpp; path = b3/B3ValueInBlock.cpp; sourceTree = "<group>"; };
> 		0FF7168A15A3B231008F5DAA /* PropertyOffset.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PropertyOffset.h; sourceTree = "<group>"; };
> 		0FF72992166AD347000F5BA3 /* ProfilerBytecode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ProfilerBytecode.cpp; path = profiler/ProfilerBytecode.cpp; sourceTree = "<group>"; };
> 		0FF72993166AD347000F5BA3 /* ProfilerBytecode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = ProfilerBytecode.h; path = profiler/ProfilerBytecode.h; sourceTree = "<group>"; };
>@@ -5198,6 +5204,8 @@
> 				0FEC84EA1BDACDAC0080FF74 /* B3SlotBaseValue.cpp */,
> 				0FEC84EB1BDACDAC0080FF74 /* B3SlotBaseValue.h */,
> 				0F2BBD911C5FF3F50023EF23 /* B3SparseCollection.h */,
>+				0FF68C1920940EB700FC5DDC /* B3SpecializePaths.cpp */,
>+				0FF68C1A20940EB700FC5DDC /* B3SpecializePaths.h */,
> 				0F6B8ADA1C4EFAC300969052 /* B3SSACalculator.cpp */,
> 				0F6B8ADB1C4EFAC300969052 /* B3SSACalculator.h */,
> 				0F33FCF51C136E2500323F67 /* B3StackmapGenerationParams.cpp */,
>@@ -5226,6 +5234,8 @@
> 				0FEC84F81BDACDAC0080FF74 /* B3Validate.h */,
> 				0FEC84F91BDACDAC0080FF74 /* B3Value.cpp */,
> 				0FEC84FA1BDACDAC0080FF74 /* B3Value.h */,
>+				0FF68C1C20940EB700FC5DDC /* B3ValueInBlock.cpp */,
>+				0FF68C1B20940EB700FC5DDC /* B3ValueInBlock.h */,
> 				0FEC84FB1BDACDAC0080FF74 /* B3ValueInlines.h */,
> 				0F338E081BF0276C0013C88F /* B3ValueKey.cpp */,
> 				0F338E091BF0276C0013C88F /* B3ValueKey.h */,
>@@ -8688,6 +8698,7 @@
> 				FEB58C15187B8B160098EF0B /* ErrorHandlingScope.h in Headers */,
> 				BC02E98D0E183E38000F9297 /* ErrorInstance.h in Headers */,
> 				BC02E90F0E1839DB000F9297 /* ErrorPrototype.h in Headers */,
>+				0FF68C1E20940EBF00FC5DDC /* B3ValueInBlock.h in Headers */,
> 				996B731B1BDA08D100331B84 /* ErrorPrototype.lut.h in Headers */,
> 				14AD910C1DCA92940014F9FE /* EvalCodeBlock.h in Headers */,
> 				147341D21DC02E2E00AA29BA /* EvalExecutable.h in Headers */,
>@@ -9356,6 +9367,7 @@
> 				A503FA22188EFF6800110F14 /* ScriptDebugListener.h in Headers */,
> 				A503FA26188EFFFD00110F14 /* ScriptDebugServer.h in Headers */,
> 				147341CE1DC02D7900AA29BA /* ScriptExecutable.h in Headers */,
>+				0FF68C1D20940EBC00FC5DDC /* B3SpecializePaths.h in Headers */,
> 				CEAE7D7B889B477BA93ABA6C /* ScriptFetcher.h in Headers */,
> 				E3201C1E1F8E824C0076A032 /* ScriptFetchParameters.h in Headers */,
> 				A55D93A6185012A800400DED /* ScriptFunctionCall.h in Headers */,
>Index: Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp	(revision 231128)
>+++ Source/JavaScriptCore/b3/B3BreakCriticalEdges.cpp	(working copy)
>@@ -1,5 +1,5 @@
> /*
>- * Copyright (C) 2016 Apple Inc. All rights reserved.
>+ * Copyright (C) 2016-2018 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,7 +40,10 @@ void breakCriticalEdges(Procedure& proc)
>     BlockInsertionSet insertionSet(proc);
>     
>     for (BasicBlock* block : proc) {
>-        if (block->numSuccessors() <= 1)
>+        // Non-void terminals that are the moral equivalent of jumps trigger critical edge braking
>+        // because of fixSSA's demoteValues.
>+        if (block->numSuccessors() <= 1
>+            && block->last()->type() == Void)
>             continue;
> 
>         for (BasicBlock*& successor : block->successorBlocks()) {
>@@ -57,8 +60,8 @@ void breakCriticalEdges(Procedure& proc)
>         }
>     }
> 
>-    insertionSet.execute();
>-    proc.invalidateCFG();
>+    if (insertionSet.execute())
>+        proc.invalidateCFG();
> }
> 
> } } // namespace JSC::B3
>Index: Source/JavaScriptCore/b3/B3FixSSA.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3FixSSA.cpp	(revision 231128)
>+++ Source/JavaScriptCore/b3/B3FixSSA.cpp	(working copy)
>@@ -1,5 +1,5 @@
> /*
>- * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
>+ * Copyright (C) 2016-2018 Apple Inc. All rights reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
>  * modification, are permitted provided that the following conditions
>@@ -172,6 +172,7 @@ void fixSSAGlobally(Procedure& proc)
>     TimingScope timingScope("fixSSA: convert");
>     InsertionSet insertionSet(proc);
>     IndexSparseSet<KeyValuePair<unsigned, Value*>> mapping(proc.variables().size());
>+    IndexSet<Value*> valuesToDelete;
>     for (BasicBlock* block : proc.blocksInPreOrder()) {
>         mapping.clear();
>         
>@@ -207,6 +208,7 @@ void fixSSAGlobally(Procedure& proc)
>                 Variable* variable = variableValue->variable();
> 
>                 value->replaceWithIdentity(ensureMapping(variable, valueIndex, value->origin()));
>+                valuesToDelete.add(value);
>                 break;
>             }
>                 
>@@ -240,12 +242,25 @@ void fixSSAGlobally(Procedure& proc)
>                 }
>                 
>                 insertionSet.insert<UpsilonValue>(
>-                    upsilonInsertionPoint, upsilonOrigin, mappedValue, phi);
>+                    upsilonInsertionPoint, upsilonOrigin, mappedValue->foldIdentity(), phi);
>             }
>         }
> 
>         insertionSet.execute(block);
>     }
>+    
>+    // This is isn't strictly necessary, but it leaves the IR nice and tidy, which is particularly
>+    // useful for phases that do size estimates.
>+    for (BasicBlock* block : proc) {
>+        block->values().removeAllMatching(
>+            [&] (Value* value) -> bool {
>+                if (!valuesToDelete.contains(value) && value->opcode() != Nop)
>+                    return false;
>+                
>+                proc.deleteValue(value);
>+                return true;
>+            });
>+    }
> 
>     if (B3FixSSAInternal::verbose) {
>         dataLog("B3 after SSA conversion:\n");
>@@ -285,6 +300,15 @@ void demoteValues(Procedure& proc, const
>     // Change accesses to the values to accesses to the stack slots.
>     InsertionSet insertionSet(proc);
>     for (BasicBlock* block : proc) {
>+        if (block->numPredecessors()) {
>+            Value* value = block->predecessor(0)->last();
>+            Variable* variable = map.get(value);
>+            if (variable) {
>+                RELEASE_ASSERT(block->numPredecessors() == 1); // Critical edges better be broken.
>+                insertionSet.insert<VariableValue>(0, Set, value->origin(), variable, value);
>+            }
>+        }
>+        
>         for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
>             Value* value = block->at(valueIndex);
> 
>@@ -312,8 +336,10 @@ void demoteValues(Procedure& proc, const
>             }
> 
>             if (Variable* variable = map.get(value)) {
>-                insertionSet.insert<VariableValue>(
>-                    valueIndex + 1, Set, value->origin(), variable, value);
>+                if (valueIndex + 1 < block->size()) {
>+                    insertionSet.insert<VariableValue>(
>+                        valueIndex + 1, Set, value->origin(), variable, value);
>+                }
>             }
>         }
>         insertionSet.execute(block);
>@@ -324,6 +350,9 @@ bool fixSSA(Procedure& proc)
> {
>     PhaseScope phaseScope(proc, "fixSSA");
> 
>+    if (proc.variables().isEmpty())
>+        return false;
>+    
>     // Lots of variables have trivial local liveness. We can allocate those without any
>     // trouble.
>     fixSSALocally(proc);
>@@ -336,7 +365,6 @@ bool fixSSA(Procedure& proc)
>     if (proc.variables().isEmpty())
>         return false;
>     
>-    // We know that we have variables to optimize, so do that now.
>     breakCriticalEdges(proc);
> 
>     fixSSAGlobally(proc);
>Index: Source/JavaScriptCore/b3/B3Generate.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3Generate.cpp	(revision 231128)
>+++ Source/JavaScriptCore/b3/B3Generate.cpp	(working copy)
>@@ -47,6 +47,7 @@
> #include "B3PureCSE.h"
> #include "B3ReduceDoubleToFloat.h"
> #include "B3ReduceStrength.h"
>+#include "B3SpecializePaths.h"
> #include "B3TimingScope.h"
> #include "B3Validate.h"
> #include "PCToCodeOriginMap.h"
>@@ -87,12 +88,7 @@ void generateToAir(Procedure& procedure)
>         hoistLoopInvariantValues(procedure);
>         if (eliminateCommonSubexpressions(procedure))
>             eliminateCommonSubexpressions(procedure);
>-        foldPathConstants(procedure);
>-        reduceStrength(procedure);
>         inferSwitches(procedure);
>-        duplicateTails(procedure);
>-        fixSSA(procedure);
>-        foldPathConstants(procedure);
>         
>         // FIXME: Add more optimizations here.
>         // https://bugs.webkit.org/show_bug.cgi?id=150507
>@@ -106,6 +102,13 @@ void generateToAir(Procedure& procedure)
> 
>     if (procedure.optLevel() >= 2) {
>         reduceStrength(procedure);
>+        foldPathConstants(procedure);
>+        specializePaths(procedure);
>+        fixSSA(procedure);
>+        duplicateTails(procedure);
>+        fixSSA(procedure);
>+        foldPathConstants(procedure);
>+        reduceStrength(procedure);
> 
>         // FIXME: Add more optimizations here.
>         // https://bugs.webkit.org/show_bug.cgi?id=150507
>Index: Source/JavaScriptCore/b3/B3Procedure.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3Procedure.cpp	(revision 231128)
>+++ Source/JavaScriptCore/b3/B3Procedure.cpp	(working copy)
>@@ -93,7 +93,6 @@ Value* Procedure::clone(Value* value)
>     return m_values.add(WTFMove(clone));
> }
> 
>-
> Value* Procedure::addIntConstant(Origin origin, Type type, int64_t value)
> {
>     switch (type) {
>Index: Source/JavaScriptCore/b3/B3Procedure.h
>===================================================================
>--- Source/JavaScriptCore/b3/B3Procedure.h	(revision 231128)
>+++ Source/JavaScriptCore/b3/B3Procedure.h	(working copy)
>@@ -142,6 +142,8 @@ public:
>     unsigned size() const { return m_blocks.size(); }
>     BasicBlock* at(unsigned index) const { return m_blocks[index].get(); }
>     BasicBlock* operator[](unsigned index) const { return at(index); }
>+    
>+    std::unique_ptr<BasicBlock> takeBlock(unsigned index) { return WTFMove(m_blocks[index]); }
> 
>     typedef WTF::IndexedContainerIterator<Procedure> iterator;
> 
>Index: Source/JavaScriptCore/b3/B3SpecializePaths.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3SpecializePaths.cpp	(nonexistent)
>+++ Source/JavaScriptCore/b3/B3SpecializePaths.cpp	(working copy)
>@@ -0,0 +1,691 @@
>+/*
>+ * Copyright (C) 2018 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 "B3SpecializePaths.h"
>+
>+#include "B3BasicBlockInlines.h"
>+#include "B3BreakCriticalEdges.h"
>+#include "B3Dominators.h"
>+#include "B3FixSSA.h"
>+#include "B3PhaseScope.h"
>+#include "B3ProcedureInlines.h"
>+#include "B3ValueInBlock.h"
>+#include "B3ValueInlines.h"
>+#include <wtf/IndexMap.h>
>+#include <wtf/IndexSet.h>
>+
>+#if ENABLE(B3_JIT)
>+
>+namespace JSC { namespace B3 {
>+
>+class SpecializePaths {
>+    struct Path {
>+        double benefitOverCost() const
>+        {
>+            // Super valuable:
>+            // 1) Pair of branches with very little code to duplicate between them.
>+            // 2) Branch inside of small loop.
>+            //
>+            // Not valuable:
>+            // 3) Duplicating a large nested loop to hoist an inner branch.
>+            //
>+            // In case of (1), we expect spaceCost to be > 1 but the benefit to be 1.
>+            //
>+            // In case of (2), we expect spaceCost to be 5-20 but the benefit to be 9.
>+            //
>+            // In case of (3), we expect spaceCost to be >100 but the benefit to be >100.
>+            return netBenefit() / spaceCost;
>+        }
>+        
>+        double netBenefit() const
>+        {
>+            return benefit - insertedBranchCost();
>+        }
>+        
>+        double insertedBranchCost() const
>+        {
>+            return insertionPoint->frequency();
>+        }
>+        
>+        void dump(PrintStream& out) const
>+        {
>+            out.print(
>+                "{predicate = ", pointerDump(predicate), ","
>+                " insertionPoint = ", pointerDump(insertionPoint), ","
>+                " branchPoint = ", branchPoint, ","
>+                " benefit = ", benefit, ","
>+                " insertedBranchCost = ", insertedBranchCost(), ","
>+                " spaceCost = ", spaceCost, ","
>+                " benefitOverCost = ", benefitOverCost(), ","
>+                " blocks = [", pointerListDump(blocks), "]}");
>+        }
>+        
>+        Value* predicate { nullptr };
>+        BasicBlock* insertionPoint { nullptr }; // This is a block that ends in a branch that we're specializing, or it ends in a Jump because this is a hoisting target.
>+        ValueInBlock branchPoint;
>+        double benefit { 0 };
>+        double spaceCost { 0 };
>+        Vector<BasicBlock*> blocks; // The list of duplicated blocks not including the branchPoint.
>+    };
>+    
>+public:
>+    SpecializePaths(Procedure& proc)
>+        : m_proc(proc)
>+    {
>+    }
>+    
>+    bool run()
>+    {
>+        if (m_verbose)
>+            dataLog("Starting specializePaths. IR before any changes:\n", m_proc);
>+        
>+        breakCriticalEdges(m_proc);
>+        createHoistingTargets();
>+
>+        if (m_verbose)
>+            dataLog("IR after hoisting target creation, before analysis:\n", m_proc);
>+        
>+        m_dominators = &m_proc.dominators();
>+        m_proc.resetValueOwners();
>+        findBranches();
>+        findBlocksDuplicatedForPredicates();
>+        createPathsByDominantRedundancy();
>+        createPathsByHoisting();
>+        choosePathOrder();
>+        simulateDuplicationAndPrunePaths();
>+        
>+        if (m_pathsInOrder.isEmpty()) {
>+            if (m_verbose)
>+                dataLog("Did not select any paths.\n");
>+            return false;
>+        }
>+        
>+        if (m_verbose) {
>+            dataLog("Selected paths in descending order of benefitOverCost:\n");
>+            for (Path* path : m_pathsInOrder)
>+                dataLog("    ", *path, "\n");
>+        }
>+        
>+        demoteAppropriateValues();
>+
>+        if (m_verbose)
>+            dataLog("IR after demoting appropriate values:\n", m_proc);
>+        
>+        duplicatePaths();
>+
>+        if (m_verbose)
>+            dataLog("IR after specializePaths:\n", m_proc);
>+        
>+        return true;
>+    }
>+    
>+private:
>+    void createHoistingTargets()
>+    {
>+        // All lower-frequency predecessors of a block should jump to that block via a hoisting
>+        // target block. If we don't use these blocks, they'll get collected by reduceStrength.
>+        
>+        BlockInsertionSet insertionSet(m_proc);
>+        
>+        for (BasicBlock* block : m_proc) {
>+            unsigned numberOfLowerFrequencyPredecessors = 0;
>+            double maxFrequencyOfLowerFrequencyPredecessors = 0;
>+            for (BasicBlock* predecessor : block->predecessors()) {
>+                if (predecessor->frequency() >= block->frequency())
>+                    continue;
>+                
>+                numberOfLowerFrequencyPredecessors++;
>+                maxFrequencyOfLowerFrequencyPredecessors =
>+                    std::max(maxFrequencyOfLowerFrequencyPredecessors, predecessor->frequency());
>+            }
>+            
>+            if (numberOfLowerFrequencyPredecessors < 2)
>+                continue;
>+            
>+            BasicBlock* hoistingTarget = insertionSet.insertBefore(block, maxFrequencyOfLowerFrequencyPredecessors);
>+            hoistingTarget->appendNew<Value>(m_proc, Jump, block->at(0)->origin());
>+            hoistingTarget->setSuccessors(block);
>+            for (BasicBlock* predecessor : block->predecessors()) {
>+                if (predecessor->frequency() >= block->frequency())
>+                    continue;
>+                
>+                predecessor->replaceSuccessor(block, hoistingTarget);
>+                hoistingTarget->addPredecessor(predecessor);
>+                block->removePredecessor(predecessor);
>+            }
>+            block->addPredecessor(hoistingTarget);
>+        }
>+        
>+        if (insertionSet.execute())
>+            m_proc.invalidateCFG();
>+    }
>+    
>+    void findBranches()
>+    {
>+        for (BasicBlock* block : m_proc) {
>+            for (unsigned index = block->size(); index--;) {
>+                Value* value = block->at(index);
>+                switch (value->opcode()) {
>+                case Branch:
>+                case Check: {
>+                    Value* predicate = value->child(0);
>+                    
>+                    m_predicateToBranches.add(predicate, Vector<ValueInBlock>()).iterator->value.append(ValueInBlock(block, index));
>+
>+                    // Each block can only have one "branch", since:
>+                    //
>+                    // 1) This redundancy would have already been fixed:
>+                    //
>+                    //    BB#foo:
>+                    //        Check(@p)
>+                    //        Check(@p)
>+                    //
>+                    // 2) This redundancy would have already been fixed:
>+                    //
>+                    //    BB#foo:
>+                    //        Check(@p)
>+                    //        Branch(@p)
>+                    //
>+                    // 3) This redundancy is not valid IR:
>+                    //
>+                    //    BB#foo:
>+                    //        Branch(@p)
>+                    //        Check(@p)
>+                    //
>+                    // 4) This redundancy is not valid IR:
>+                    //
>+                    //    BB#foo:
>+                    //        Branch(@p)
>+                    //        Branch(@p)
>+                    //
>+                    // Of course, the first two assumptions could be violated because of a missed
>+                    // optimization opportunity. This phase is prepared for that.
>+                    m_blocksWithBranches.add(std::make_pair(block, predicate));
>+                    break;
>+                }
>+                    
>+                default:
>+                    break;
>+                }
>+            }
>+        }
>+    }
>+    
>+    void findBlocksDuplicatedForPredicates()
>+    {
>+        for (BasicBlock* block : m_proc) {
>+            if (block->last()->opcode() != Branch)
>+                continue;
>+            
>+            Value* predicate = block->last()->child(0);
>+            
>+            auto handleSuccessor = [&] (BasicBlock* start, bool predicateValue) {
>+                m_dominators->forAllBlocksDominatedBy(
>+                    start,
>+                    [&] (BasicBlock* duplicatedBlock) {
>+                        // It's possible that this will have collisions if a branch dominated by
>+                        // another branch wasn't eliminated by foldPathConstants.
>+                        m_duplicatedForPredicate.add(std::make_pair(duplicatedBlock, predicate), predicateValue);
>+                    });
>+            };
>+            
>+            handleSuccessor(block->taken().block(), true);
>+            handleSuccessor(block->notTaken().block(), false);
>+        }
>+    }
>+    
>+    void createPathsByDominantRedundancy()
>+    {
>+        for (auto& entry : m_predicateToBranches) {
>+            Value* predicate = entry.key;
>+            Vector<ValueInBlock>& branches = entry.value;
>+            
>+            for (ValueInBlock insertionPoint : branches) {
>+                if (insertionPoint.value()->opcode() != Branch)
>+                    continue;
>+                
>+                for (ValueInBlock branchPoint : branches) {
>+                    if (!m_dominators->dominates(insertionPoint.block(), branchPoint.block()))
>+                        continue;
>+                    
>+                    if (insertionPoint.block() == branchPoint.block()) {
>+                        if (insertionPoint.index() > branchPoint.index())
>+                            continue;
>+                        
>+                        RELEASE_ASSERT(insertionPoint.index() == branchPoint.index());
>+                    }
>+                    
>+                    m_path = m_paths.add();
>+                    m_path->predicate = predicate;
>+                    m_path->insertionPoint = insertionPoint.block();
>+                    m_path->branchPoint = branchPoint;
>+                    
>+                    if (insertionPoint.value() == branchPoint.value()) {
>+                        m_path->spaceCost = 0;
>+                        m_path->benefit = insertionPoint.block()->frequency();
>+                    } else {
>+                        m_path->spaceCost = branchPoint.index();
>+                        m_path->benefit = branchPoint.block()->frequency() + insertionPoint.block()->frequency();
>+                        
>+                        RELEASE_ASSERT(insertionPoint.block() != branchPoint.block());
>+
>+                        BlockWorklist worklist;
>+                        worklist.pushAll(branchPoint.block()->predecessors());
>+                        closePath(worklist);
>+                    }
>+                    
>+                    if (m_verbose)
>+                        dataLog("Adding path by dominant redundancy: ", *m_path, "\n");
>+                }
>+            }
>+        }
>+    }
>+    
>+    void createPathsByHoisting()
>+    {
>+        Vector<Path*> pathsToProcess;
>+        for (Path* path : m_paths)
>+            pathsToProcess.append(path);
>+        while (!pathsToProcess.isEmpty()) {
>+            Path* oldPath = pathsToProcess.takeLast();
>+            if (oldPath->insertionPoint->frequency() <= oldPath->predicate->owner->frequency())
>+                continue;
>+            
>+            BasicBlock* newInsertionPointBlock = oldPath->insertionPoint;
>+            for (;;) {
>+                newInsertionPointBlock = m_dominators->idom(newInsertionPointBlock);
>+                
>+                if (!newInsertionPointBlock)
>+                    break;
>+
>+                if (newInsertionPointBlock->last()->opcode() == Jump
>+                    && newInsertionPointBlock->frequency() < oldPath->insertionPoint->frequency())
>+                    break;
>+            }
>+            
>+            if (!newInsertionPointBlock)
>+                continue;
>+            
>+            if (!m_dominators->dominates(oldPath->predicate->owner, newInsertionPointBlock))
>+                continue;
>+            
>+            if (newInsertionPointBlock == oldPath->insertionPoint)
>+                continue;
>+            
>+            // Hoisting targets must have jumps at the end of them because we created hoisting
>+            // targets that have jumps.
>+            RELEASE_ASSERT(newInsertionPointBlock->last()->opcode() == Jump);
>+            
>+            m_path = m_paths.add(*oldPath);
>+            m_path->insertionPoint = newInsertionPointBlock;
>+            
>+            m_path->spaceCost += oldPath->insertionPoint->size();
>+            
>+            BlockWorklist worklist;
>+            for (BasicBlock* block : oldPath->blocks)
>+                worklist.pretendToHaveSeen(block);
>+            
>+            worklist.pushAll(oldPath->insertionPoint->predecessors());
>+            closePath(worklist);
>+            
>+            pathsToProcess.append(m_path);
>+            
>+            if (m_verbose) {
>+                dataLog("Adding path by hoisting:\n");
>+                dataLog("    Old path: ", *oldPath, "\n");
>+                dataLog("    New path: ", *m_path, "\n");
>+            }
>+        }
>+    }
>+    
>+    void closePath(BlockWorklist& worklist)
>+    {
>+        while (BasicBlock* block = worklist.pop()) {
>+            if (block == m_path->insertionPoint)
>+                continue;
>+            
>+            m_path->blocks.append(block);
>+            
>+            if (block == m_path->branchPoint.block()) {
>+                // We only want to add the end of this block. Note, if we see this block,
>+                // it's because it wasn't already in the blocks set. That means that oldPath was a
>+                // a dominant redundancy path rather than a hoisted path. It also means
>+                // that this block doesn't have any unaccounted-for branches.
>+                //
>+                // But the only way for there to be anything after the branchPoint in the block is if
>+                // the branchPoint is a Check. Code after a Check only needs to be duplicated for
>+                // when the predicate is false. So, that code doesn't get duplicated at all.
>+                // Therefore, there is no additional cost.
>+                continue;
>+            }
>+            
>+            if (!m_duplicatedForPredicate.contains(std::make_pair(block, m_path->predicate))) {
>+                m_path->spaceCost += block->size();
>+
>+                // This `if` is nested because if a duplicated block *did* have a
>+                // branch for our predicate then it's probably because we missed an
>+                // optimization opportunity in the last reduceStrength pass. That is
>+                // most likely to happen because this redundancy was revealed only
>+                // after some phase that ran after reduceStrength, like
>+                // eliminateCommonSubexpressions. Therefore, a future pass of
>+                // reduceStrength is very likely to remove a duplicated branch for
>+                // our predicate without needing to specialize. Therefore, we don't
>+                // want to could it as a benefit here. Also, we don't duplicate
>+                // duplicated blocks, so we wouldn't be creating any benefit anyway.
>+                if (m_blocksWithBranches.contains(std::make_pair(block, m_path->predicate)))
>+                    m_path->benefit += block->frequency();
>+            }
>+            
>+            worklist.pushAll(block->predecessors());
>+        }
>+    }
>+    
>+    void choosePathOrder()
>+    {
>+        for (Path* path : m_paths) {
>+            // We don't know anything about this heuristic yet.
>+            if (path->benefitOverCost() > Options::b3PathSpecializationThreshold())
>+                m_pathsInOrder.append(path);
>+        }
>+        
>+        std::sort(
>+            m_pathsInOrder.begin(), m_pathsInOrder.end(),
>+            [&] (Path* left, Path* right) -> bool {
>+                // Sort in descending order of benefit.
>+                return left->netBenefit() > right->netBenefit();
>+            });
>+    }
>+    
>+    void simulateDuplicationAndPrunePaths()
>+    {
>+        m_affectedBlocks.resize(m_proc.size());
>+
>+        m_pathsInOrder.removeAllMatching(
>+            [&] (Path* path) -> bool {
>+                if (m_affectedBlocks[path->predicate->owner] != HowAffected::NotAffected)
>+                    return true;
>+                if (m_affectedBlocks[path->insertionPoint] != HowAffected::NotAffected)
>+                    return true;
>+                if (m_affectedBlocks[path->branchPoint.block()] != HowAffected::NotAffected)
>+                    return true;
>+                for (BasicBlock* block : path->blocks) {
>+                    if (m_affectedBlocks[block] != HowAffected::NotAffected)
>+                        return true;
>+                }
>+                
>+                m_affectedBlocks[path->predicate->owner] = HowAffected::Predicate;
>+                m_affectedBlocks[path->insertionPoint] = HowAffected::InsertionPoint;
>+                m_affectedBlocks[path->branchPoint.block()] = HowAffected::Duplicated;
>+                for (BasicBlock* block : path->blocks)
>+                    m_affectedBlocks[block] = HowAffected::Duplicated;
>+                return false;
>+            });
>+    }
>+    
>+    void demoteAppropriateValues()
>+    {
>+        IndexSet<Value*> valuesToDemote;
>+        for (BasicBlock* block : m_proc) {
>+            for (Value* value : *block) {
>+                if (value->opcode() == Phi && m_affectedBlocks[block] == HowAffected::Duplicated)
>+                    valuesToDemote.add(value);
>+                for (Value* child : value->children()) {
>+                    if (child->owner != block && m_affectedBlocks[child->owner] == HowAffected::Duplicated)
>+                        valuesToDemote.add(child);
>+                }
>+            }
>+        }
>+        demoteValues(m_proc, valuesToDemote);
>+    }
>+    
>+    void duplicatePaths()
>+    {
>+        BlockInsertionSet insertionSet(m_proc);
>+        
>+        IndexMap<BasicBlock*, BasicBlock*> blockMap(m_proc.size());
>+        IndexMap<Value*, Value*> valueMap(m_proc.values().size());
>+        
>+        for (Path* path : m_pathsInOrder) {
>+            m_path = path;
>+            
>+            auto addBlockToDuplicate = [&] (BasicBlock* block) {
>+                m_blocksToDuplicateList.append(block);
>+                bool result = m_blocksToDuplicateSet.add(block);
>+                RELEASE_ASSERT(result);
>+            };
>+            
>+            addBlockToDuplicate(m_path->branchPoint.block());
>+            for (BasicBlock* block : m_path->blocks) {
>+                if (block != m_path->branchPoint.block())
>+                    addBlockToDuplicate(block);
>+            }
>+            
>+            std::sort(
>+                m_blocksToDuplicateList.begin(), m_blocksToDuplicateList.end(),
>+                [&] (BasicBlock* left, BasicBlock* right) -> bool {
>+                    return left->index() < right->index();
>+                });
>+            
>+            // Order matters! We try to create a CFG that doesn't look like garbage. That's
>+            // particularly important for the performance of linear scan. It doesn't matter for
>+            // graph coloring though. It definitely matters for debugging the compiler.
>+            BasicBlock* blockBeforeInsertionPoint = m_blocksToDuplicateList.last();
>+            for (BasicBlock* block : m_blocksToDuplicateList) {
>+                auto iter = m_duplicatedForPredicate.find(std::make_pair(block, m_path->predicate));
>+                if (iter != m_duplicatedForPredicate.end()) {
>+                    bool predicateValue = iter->value;
>+                    
>+                    // We don't duplicate then/else blocks. Note that because of how
>+                    // m_duplicatedForPredicate works, this could be both a then and a else block if:
>+                    // - This is dominated by (and duplicated for) a branch that is dominated by our
>+                    //   insertion point, and a branch dominated by our insertion point.
>+                    // - Our insertion point is dominated by (and duplicated for) another branch on
>+                    //   our predicate.
>+                    // But if this block is in the then and else case of the same predicate, then it
>+                    // is unreachable. So, we can do whatever we want with it.
>+
>+                    // We leave then blocks where they are.
>+                    if (predicateValue)
>+                        continue;
>+                    
>+                    // Move the location of the block in the program flow. Gotta keep the CFG sane.
>+                    insertionSet.insert(
>+                        BlockInsertionSet::BlockInsertion(
>+                            blockBeforeInsertionPoint->index() + 1,
>+                            m_proc.takeBlock(block->index())));
>+                    continue;
>+                }
>+                
>+                BasicBlock* newBlock =
>+                    insertionSet.insertAfter(blockBeforeInsertionPoint, block->frequency());
>+                blockMap[block] = newBlock;
>+                newBlock->successors() = block->successors();
>+            }
>+            
>+            auto elseBlockFor = [&] (BasicBlock* block) -> BasicBlock* {
>+                if (BasicBlock* result = blockMap[block])
>+                    return result;
>+                return block;
>+            };
>+            
>+            for (BasicBlock* block : m_blocksToDuplicateList) {
>+                auto foldValueFor = [&] (BasicBlock* block, Value* value, bool predicateValue) {
>+                    switch (value->opcode()) {
>+                    case Branch:
>+                        if (value->child(0) != m_path->predicate)
>+                            return;
>+                        value->replaceWithJump(
>+                            block, predicateValue ? block->taken() : block->notTaken());
>+                        return;
>+                    case Check:
>+                        if (value->child(0) != m_path->predicate)
>+                            return;
>+                        if (!predicateValue)
>+                            value->replaceWithNop();
>+                        return;
>+                    default:
>+                        return;
>+                    }
>+                };
>+                
>+                auto rewireBlockFor = [&] (BasicBlock* block, bool predicateValue) {
>+                    // Here are the cases we need to worry about:
>+                    //
>+                    // 1) Before: unduplicated, after: unduplicated.
>+                    //    -> We don't see that here. The only block like that that would need to
>+                    //       be changed is the insertionPoint. We edit the insertionPoint way below.
>+                    //
>+                    // 2) Before: unduplicated, after: duplicated.
>+                    //    S1) Successor was unduplicated before, is unduplicated after.
>+                    //        -> Nothing to do. This is a jump out of code affected by the predicate.
>+                    //    S2) Successor was unduplicated before, is duplicated after.
>+                    //        -> Make sure that we point to the else successor in the else duplicate.
>+                    //    S3) Successor was duplicated before, is duplicated after.
>+                    //        -> This part is tricky! We currently do nothing in this case.
>+                    //
>+                    // 3) Before: duplicated, after: duplicated.
>+                    //    S1) Successor was unduplicated before, is unduplicated after.
>+                    //        -> Nothing to do. This is a jump out of code affected by the predicate.
>+                    //    S2) Successor was unduplicated before, is duplicated after.
>+                    //        -> Make sure that we point to the else duplicate.
>+                    //    S3) Successor was duplicated before, is duplicated after.
>+                    //        -> Nothing to do. Just preserve what was there.
>+                    
>+                    if (predicateValue) {
>+                        // In the current rewiring we don't have to do anything for then blocks.
>+                        return;
>+                    }
>+                    
>+                    for (BasicBlock*& successor : block->successorBlocks()) {
>+                        if (m_blocksToDuplicateSet.contains(successor))
>+                            successor = elseBlockFor(successor);
>+                    }
>+                };
>+                
>+                auto iter = m_duplicatedForPredicate.find(std::make_pair(block, m_path->predicate));
>+                if (iter != m_duplicatedForPredicate.end()) {
>+                    bool predicateValue = iter->value;
>+                    rewireBlockFor(block, predicateValue);
>+                    foldValueFor(block, block->last(), predicateValue);
>+                    continue;
>+                }
>+                
>+                BasicBlock* elseBlock = elseBlockFor(block);
>+                rewireBlockFor(block, true);
>+                rewireBlockFor(elseBlock, false);
>+                
>+                // Fun fact: this loop will duplicate code after the then case of a Check. That's
>+                // dead code. And that's OK.
>+                for (Value* value : *block) {
>+                    Value* clone = m_proc.clone(value);
>+                    for (Value*& child : clone->children()) {
>+                        if (Value* replacement = valueMap[child])
>+                            child = replacement;
>+                    }
>+                    if (value->type() != Void)
>+                        valueMap[value] = clone;
>+                    elseBlock->append(clone);
>+                    
>+                    foldValueFor(block, value, true);
>+                    foldValueFor(elseBlock, clone, false);
>+                }
>+            }
>+            
>+            Value* insertionPointJump = m_path->insertionPoint->last();
>+            switch (insertionPointJump->opcode()) {
>+            case Branch:
>+                RELEASE_ASSERT(insertionPointJump->child(0) == m_path->predicate);
>+                // There shouldn't be anything left to do if we're in this situation.
>+                break;
>+                
>+            case Jump:
>+                m_path->insertionPoint->replaceLastWithNew<Value>(
>+                    m_proc, Branch, insertionPointJump->origin(), m_path->predicate);
>+                // The unduplicated code that this jump already has as its successor is what we
>+                // want to be the `then` case of the branch. So, we want to append the `else`
>+                // (notTaken) case.
>+                m_path->insertionPoint->appendSuccessor(
>+                    elseBlockFor(m_path->insertionPoint->successorBlock(0)));
>+                break;
>+                
>+            default:
>+                RELEASE_ASSERT_NOT_REACHED();
>+            }
>+            
>+            while (!m_blocksToDuplicateList.isEmpty()) {
>+                BasicBlock* block = m_blocksToDuplicateList.takeLast();
>+                m_blocksToDuplicateSet.remove(block);
>+            }
>+        }
>+        
>+        if (insertionSet.execute()) {
>+            m_proc.resetReachability();
>+            m_proc.invalidateCFG();
>+        }
>+    }
>+    
>+    Procedure& m_proc;
>+    
>+    bool m_verbose { Options::verboseB3PathSpecialization() };
>+    
>+    Dominators* m_dominators { nullptr };
>+    
>+    HashMap<Value*, Vector<ValueInBlock>> m_predicateToBranches;
>+    
>+    HashSet<std::pair<BasicBlock*, Value*>> m_blocksWithBranches;
>+    
>+    // We say that a block is duplicated for a branch if it's dominated by the successor of one of
>+    // those branches. The bool value is the predicate's value when we are in that block.
>+    HashMap<std::pair<BasicBlock*, Value*>, bool> m_duplicatedForPredicate;
>+    
>+    Path* m_path;
>+
>+    Bag<Path> m_paths;
>+    Vector<Path*> m_pathsInOrder;
>+    
>+    enum class HowAffected {
>+        NotAffected,
>+        Predicate, // Need to track these because we don't want to duplicate, and so demote, the predicates of other paths.
>+        InsertionPoint,
>+        Duplicated
>+    };
>+    IndexMap<BasicBlock*, HowAffected> m_affectedBlocks;
>+    
>+    Vector<BasicBlock*> m_blocksToDuplicateList;
>+    IndexSet<BasicBlock*> m_blocksToDuplicateSet;
>+};
>+
>+bool specializePaths(Procedure& proc)
>+{
>+    PhaseScope phaseScope(proc, "specializePaths");
>+    SpecializePaths specializePaths(proc);
>+    return specializePaths.run();
>+}
>+
>+} } // namespace JSC::B3
>+
>+#endif // ENABLE(B3_JIT)
>+
>Index: Source/JavaScriptCore/b3/B3SpecializePaths.h
>===================================================================
>--- Source/JavaScriptCore/b3/B3SpecializePaths.h	(nonexistent)
>+++ Source/JavaScriptCore/b3/B3SpecializePaths.h	(working copy)
>@@ -0,0 +1,41 @@
>+/*
>+ * Copyright (C) 2018 Apple Inc. All rights reserved.
>+ *
>+ * Redistribution and use in source and binary forms, with or without
>+ * modification, are permitted provided that the following conditions
>+ * are met:
>+ * 1. Redistributions of source code must retain the above copyright
>+ *    notice, this list of conditions and the following disclaimer.
>+ * 2. Redistributions in binary form must reproduce the above copyright
>+ *    notice, this list of conditions and the following disclaimer in the
>+ *    documentation and/or other materials provided with the distribution.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
>+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
>+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
>+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
>+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
>+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
>+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
>+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
>+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
>+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
>+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
>+ */
>+
>+#pragma once
>+
>+#if ENABLE(B3_JIT)
>+
>+namespace JSC { namespace B3 {
>+
>+class Procedure;
>+
>+// Duplicates code to remove branches. Each piece of code gets duplicated at most once, so there
>+// is no exponential blow-up.
>+
>+bool specializePaths(Procedure&);
>+
>+} } // namespace JSC::B3
>+
>+#endif // ENABLE(B3_JIT)
>Index: Source/JavaScriptCore/b3/B3Value.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3Value.cpp	(revision 231128)
>+++ Source/JavaScriptCore/b3/B3Value.cpp	(working copy)
>@@ -778,13 +778,21 @@ ValueKey Value::key() const
>     }
> }
> 
>+Value* Value::foldIdentity() const
>+{
>+    Value* current = const_cast<Value*>(this);
>+    while (current->opcode() == Identity)
>+        current = current->child(0);
>+    return current;
>+}
>+
> bool Value::performSubstitution()
> {
>     bool result = false;
>     for (Value*& child : children()) {
>-        while (child->opcode() == Identity) {
>+        if (child->opcode() == Identity) {
>             result = true;
>-            child = child->child(0);
>+            child = child->foldIdentity();
>         }
>     }
>     return result;
>Index: Source/JavaScriptCore/b3/B3Value.h
>===================================================================
>--- Source/JavaScriptCore/b3/B3Value.h	(revision 231128)
>+++ Source/JavaScriptCore/b3/B3Value.h	(working copy)
>@@ -260,6 +260,8 @@ public:
>     // empty ValueKey if this Value is impure. Note that an operation that returns Void could still
>     // have a non-empty ValueKey. This happens for example with Check operations.
>     ValueKey key() const;
>+    
>+    Value* foldIdentity() const;
> 
>     // Makes sure that none of the children are Identity's. If a child points to Identity, this will
>     // repoint it at the Identity's child. For simplicity, this will follow arbitrarily long chains
>Index: Source/JavaScriptCore/b3/B3ValueInBlock.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3ValueInBlock.cpp	(nonexistent)
>+++ Source/JavaScriptCore/b3/B3ValueInBlock.cpp	(working copy)
>@@ -0,0 +1,41 @@
>+/*
>+ * Copyright (C) 2018 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 "B3ValueInBlock.h"
>+
>+#if ENABLE(B3_JIT)
>+
>+namespace JSC { namespace B3 {
>+
>+void ValueInBlock::dump(PrintStream& out) const
>+{
>+    out.print(pointerDump(m_block), ":", m_index, "->", pointerDump(m_value));
>+}
>+
>+} } // namespace JSC::B3
>+
>+#endif // ENABLE(B3_JIT)
>+
>Index: Source/JavaScriptCore/b3/B3ValueInBlock.h
>===================================================================
>--- Source/JavaScriptCore/b3/B3ValueInBlock.h	(nonexistent)
>+++ Source/JavaScriptCore/b3/B3ValueInBlock.h	(working copy)
>@@ -0,0 +1,113 @@
>+/*
>+ * Copyright (C) 2018 Apple Inc. All rights reserved.
>+ *
>+ * Redistribution and use in source and binary forms, with or without
>+ * modification, are permitted provided that the following conditions
>+ * are met:
>+ * 1. Redistributions of source code must retain the above copyright
>+ *    notice, this list of conditions and the following disclaimer.
>+ * 2. Redistributions in binary form must reproduce the above copyright
>+ *    notice, this list of conditions and the following disclaimer in the
>+ *    documentation and/or other materials provided with the distribution.
>+ *
>+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
>+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
>+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
>+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
>+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
>+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
>+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
>+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
>+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
>+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
>+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
>+ */
>+
>+#pragma once
>+
>+#if ENABLE(B3_JIT)
>+
>+#include "B3BasicBlock.h"
>+#include "B3Value.h"
>+
>+namespace JSC { namespace B3 {
>+
>+class ValueInBlock {
>+public:
>+    ValueInBlock() { }
>+    
>+    ValueInBlock(BasicBlock* block, unsigned index)
>+        : m_block(block)
>+        , m_index(index)
>+        , m_value(block->at(index)) // We save this because that's useful after the phase messes up indices.
>+    {
>+    }
>+    
>+    BasicBlock* block() const { return m_block; }
>+    unsigned index() const { return m_index; }
>+    Value* value() const { return m_value; }
>+    
>+    bool operator==(const ValueInBlock& other) const
>+    {
>+        return m_block == other.m_block
>+            && m_index == other.m_index
>+            && m_value == other.m_value;
>+    }
>+    
>+    bool operator!=(const ValueInBlock& other) const
>+    {
>+        return !(*this == other);
>+    }
>+    
>+    explicit operator bool() const
>+    {
>+        return *this != ValueInBlock();
>+    }
>+    
>+    void dump(PrintStream& out) const;
>+    
>+    unsigned hash() const
>+    {
>+        return WTF::PtrHash<BasicBlock*>::hash(m_block) + m_index;
>+    }
>+    
>+    ValueInBlock(WTF::HashTableDeletedValueType)
>+    {
>+        m_index--;
>+    }
>+    
>+    bool isHashTableDeletedValue() const
>+    {
>+        return *this == ValueInBlock(WTF::HashTableDeletedValue);
>+    }
>+    
>+private:
>+    BasicBlock* m_block { nullptr };
>+    unsigned m_index { UINT_MAX };
>+    Value* m_value { nullptr };
>+};
>+
>+struct ValueInBlockHash {
>+    static unsigned hash(const ValueInBlock& key) { return key.hash(); }
>+    static bool equal(const ValueInBlock& a, const ValueInBlock& b) { return a == b; }
>+    static constexpr bool safeToCompareToEmptyOrDeleted = true;
>+};
>+
>+} } // namespace JSC::B3
>+
>+namespace WTF {
>+
>+template<typename> struct DefaultHash;
>+template<> struct DefaultHash<JSC::B3::ValueInBlock> {
>+    typedef JSC::B3::ValueInBlockHash Hash;
>+};
>+
>+template<typename> struct HashTraits;
>+template<> struct HashTraits<JSC::B3::ValueInBlock> : public SimpleClassHashTraits<JSC::B3::ValueInBlock> {
>+    static constexpr bool emptyValueIsZero = false;
>+};
>+
>+} // namespace WTF
>+
>+#endif // ENABLE(B3_JIT)
>+
>Index: Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGLICMPhase.cpp	(revision 231128)
>+++ Source/JavaScriptCore/dfg/DFGLICMPhase.cpp	(working copy)
>@@ -281,7 +281,7 @@ private:
>             && !m_graph.m_controlEquivalenceAnalysis->dominatesEquivalently(data.preHeader, fromBlock);
>         
>         if (addsBlindSpeculation
>-            && m_graph.hasExitSite(originalOrigin.semantic, HoistingFailed)) {
>+            && m_graph.hasGlobalExitSite(originalOrigin.semantic, HoistingFailed)) {
>             if (verbose) {
>                 dataLog(
>                     "    Not hoisting ", node, " because it may exit and the pre-header (",
>Index: Source/JavaScriptCore/runtime/Options.h
>===================================================================
>--- Source/JavaScriptCore/runtime/Options.h	(revision 231128)
>+++ Source/JavaScriptCore/runtime/Options.h	(working copy)
>@@ -439,6 +439,8 @@ constexpr bool enableIntlPluralRules = f
>     v(bool, logAirRegisterPressure, false, Normal, nullptr) \
>     v(unsigned, maxB3TailDupBlockSize, 3, Normal, nullptr) \
>     v(unsigned, maxB3TailDupBlockSuccessors, 3, Normal, nullptr) \
>+    v(bool, verboseB3PathSpecialization, false, Normal, nullptr) \
>+    v(double, b3PathSpecializationThreshold, 1.1, Normal, nullptr) \
>     \
>     v(bool, useDollarVM, false, Restricted, "installs the $vm debugging tool in global objects") \
>     v(optionString, functionOverrides, nullptr, Restricted, "file with debugging overrides for function bodies") \
>Index: Source/WTF/ChangeLog
>===================================================================
>--- Source/WTF/ChangeLog	(revision 231128)
>+++ Source/WTF/ChangeLog	(working copy)
>@@ -1,3 +1,18 @@
>+2018-04-28  Filip Pizlo  <fpizlo@apple.com>
>+
>+        B3 should have generalized path specialization
>+        https://bugs.webkit.org/show_bug.cgi?id=185060
>+
>+        Reviewed by NOBODY (OOPS!).
>+        
>+        Add some comments and some supporting functions that were useful for the new phase.
>+
>+        * wtf/BitVector.h:
>+        * wtf/GraphNodeWorklist.h:
>+        (WTF::GraphNodeWorklist::pretendToHaveSeen):
>+        * wtf/IndexSet.h:
>+        (WTF::IndexSet::removeAll):
>+
> 2018-04-26  Mark Lam  <mark.lam@apple.com>
> 
>         Gardening: Speculative build fix for Windows.
>Index: Source/WTF/wtf/BitVector.h
>===================================================================
>--- Source/WTF/wtf/BitVector.h	(revision 231128)
>+++ Source/WTF/wtf/BitVector.h	(working copy)
>@@ -110,6 +110,8 @@ public: 
>     // Like ensureSize(), but supports reducing the size of the bitvector.
>     WTF_EXPORT_PRIVATE void resize(size_t numBits);
>     
>+    // Clears the set without freeing memory. If you want to clear the set and free memory, then
>+    // you want *this = BitVector().
>     WTF_EXPORT_PRIVATE void clearAll();
> 
>     bool quickGet(size_t bit) const
>Index: Source/WTF/wtf/GraphNodeWorklist.h
>===================================================================
>--- Source/WTF/wtf/GraphNodeWorklist.h	(revision 231128)
>+++ Source/WTF/wtf/GraphNodeWorklist.h	(working copy)
>@@ -1,5 +1,5 @@
> /*
>- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
>+ * Copyright (C) 2015-2018 Apple Inc. All rights reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
>  * modification, are permitted provided that the following conditions
>@@ -64,8 +64,10 @@ public:
> 
>     bool saw(Node node) { return m_seen.contains(node); }
>     
>+    bool pretendToHaveSeen(Node node) { return m_seen.add(node); }
>+    
>     const Set& seen() const { return m_seen; }
>-
>+    
> private:
>     Set m_seen;
>     Vector<Node, 16> m_stack;
>Index: Source/WTF/wtf/IndexSet.h
>===================================================================
>--- Source/WTF/wtf/IndexSet.h	(revision 231128)
>+++ Source/WTF/wtf/IndexSet.h	(working copy)
>@@ -61,6 +61,12 @@ public:
>     {
>         return m_set.clear(IndexKeyType<T>::index(value));
>     }
>+    
>+    // Removes everything from the set without freeing memory.
>+    void removeAll()
>+    {
>+        m_set.clearAll();
>+    }
> 
>     bool contains(const T& value) const
>     {

Actions: View | Formatted Diff | Diff

Attachments on bug 185060: 338939 | 338952 | 338954 | 338965 | 339038 | 339050 | 339075 | 339087 | 339104 | 339163