Air::IRC doesn't need to have a special-case for uncolored Tmps since they all get...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 17 Oct 2016 21:45:56 +0000 (21:45 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 17 Oct 2016 21:45:56 +0000 (21:45 +0000)
https://bugs.webkit.org/show_bug.cgi?id=163548
<rdar://problem/28804381>

Reviewed by Geoffrey Garen.

Before r207408, IRC had a mode where it would silently assign the first assignable register (so
%rax, %xmm0, etc) to any tmp that was not colorable due to a pathological interference fencepost.
We reason about interference at instruction boundaries. This means that if you have, for example,
an instruction that clobbers all registers late followed by an instruction that has an early def
in the same register file, then the early def will not be colorable because it interferes with
all registers. This already happens in our tests, but IRC silently returns the first assignable
register to such tmps. For some reason the resulting code works OK - probably because this tends
to only be hit by fuzzing, which may not then stress that code enough to shake out the register
corruption. Also, this can only happen for floating point registers, so it's hard to get an
exciting crash. The worst case is that your numbers get all messed up.

This change fixes the issue:

- IRC will now crash if it can't color a tmp.

- IRC doesn't crash on our tests anymore because I added a padInterference() utility that works
  around the interference problem by inserting Nops to pad between those instructions where
  conflating their early and late actions into one interference fencepost could create an
  uncolorable graph.

See https://bugs.webkit.org/show_bug.cgi?id=163548#c2 for a detailed discussion of how the
problem can arise.

This problem almost made me want to abandon our use of interference at instruction boundaries,
and introduce something more comprehensive, like interference at various stages of an
instruction's execution. The reason why I didn't do this is that this problem only arises in well
confined corner cases: you need an instruction that does a late use or def followed by an
instruction that does an early def. Register clobbers count as defs for this equation.
Fortunately, early defs are rare, and even when they do happen, you still need the previous
instruction to have a late something. Late uses are rare and many instructions don't have defs at
all, which means that it's actually pretty common for an instruction to not have anything late.
This means that the padInterference() strategy is ideal: our algorithms stay simple because they
only have to worry about interference at boundaries, and we rarely insert any Nops in
padInterference() so the IR stays nice and compact. Those Nops get removed by any phase that does
DCE, which includes eliminateDeadCode(), allocateStack(), and reportUsedRegisters(). In practice
allocateStack() kills them.

This also finally refactors our passing of RegisterSet to pass it by value, since it's small
enough that we're not gaining anything by using references. On x86, RegisterSet ought to be
smaller than a pointer.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3StackmapSpecial.cpp:
(JSC::B3::StackmapSpecial::extraClobberedRegs):
(JSC::B3::StackmapSpecial::extraEarlyClobberedRegs):
* b3/B3StackmapSpecial.h:
* b3/air/AirCCallSpecial.cpp:
(JSC::B3::Air::CCallSpecial::extraEarlyClobberedRegs):
(JSC::B3::Air::CCallSpecial::extraClobberedRegs):
* b3/air/AirCCallSpecial.h:
* b3/air/AirInst.h:
* b3/air/AirInstInlines.h:
(JSC::B3::Air::Inst::extraClobberedRegs):
(JSC::B3::Air::Inst::extraEarlyClobberedRegs):
* b3/air/AirIteratedRegisterCoalescing.cpp:
(JSC::B3::Air::iteratedRegisterCoalescing):
* b3/air/AirPadInterference.cpp: Added.
(JSC::B3::Air::padInterference):
* b3/air/AirPadInterference.h: Added.
* b3/air/AirSpecial.h:
* b3/air/AirSpillEverything.cpp:
(JSC::B3::Air::spillEverything):
* jit/RegisterSet.h:
(JSC::RegisterSet::isEmpty):

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

15 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3StackmapSpecial.cpp
Source/JavaScriptCore/b3/B3StackmapSpecial.h
Source/JavaScriptCore/b3/air/AirCCallSpecial.cpp
Source/JavaScriptCore/b3/air/AirCCallSpecial.h
Source/JavaScriptCore/b3/air/AirInst.h
Source/JavaScriptCore/b3/air/AirInstInlines.h
Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp
Source/JavaScriptCore/b3/air/AirPadInterference.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirPadInterference.h [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirSpecial.h
Source/JavaScriptCore/b3/air/AirSpillEverything.cpp
Source/JavaScriptCore/jit/RegisterSet.h

index 95406ef..458a2b4 100644 (file)
@@ -95,6 +95,7 @@ set(JavaScriptCore_SOURCES
     b3/air/AirLowerEntrySwitch.cpp
     b3/air/AirLowerMacros.cpp
     b3/air/AirOptimizeBlockOrder.cpp
+    b3/air/AirPadInterference.cpp
     b3/air/AirPhaseScope.cpp
     b3/air/AirReportUsedRegisters.cpp
     b3/air/AirSimplifyCFG.cpp
index 6f1b6df..53b4f4c 100644 (file)
@@ -1,3 +1,77 @@
+2016-10-17  Filip Pizlo  <fpizlo@apple.com>
+
+        Air::IRC doesn't need to have a special-case for uncolored Tmps since they all get colored
+        https://bugs.webkit.org/show_bug.cgi?id=163548
+        <rdar://problem/28804381>
+
+        Reviewed by Geoffrey Garen.
+        
+        Before r207408, IRC had a mode where it would silently assign the first assignable register (so
+        %rax, %xmm0, etc) to any tmp that was not colorable due to a pathological interference fencepost.
+        We reason about interference at instruction boundaries. This means that if you have, for example,
+        an instruction that clobbers all registers late followed by an instruction that has an early def
+        in the same register file, then the early def will not be colorable because it interferes with
+        all registers. This already happens in our tests, but IRC silently returns the first assignable
+        register to such tmps. For some reason the resulting code works OK - probably because this tends
+        to only be hit by fuzzing, which may not then stress that code enough to shake out the register
+        corruption. Also, this can only happen for floating point registers, so it's hard to get an
+        exciting crash. The worst case is that your numbers get all messed up.
+        
+        This change fixes the issue:
+        
+        - IRC will now crash if it can't color a tmp.
+        
+        - IRC doesn't crash on our tests anymore because I added a padInterference() utility that works
+          around the interference problem by inserting Nops to pad between those instructions where
+          conflating their early and late actions into one interference fencepost could create an
+          uncolorable graph.
+        
+        See https://bugs.webkit.org/show_bug.cgi?id=163548#c2 for a detailed discussion of how the
+        problem can arise.
+        
+        This problem almost made me want to abandon our use of interference at instruction boundaries,
+        and introduce something more comprehensive, like interference at various stages of an
+        instruction's execution. The reason why I didn't do this is that this problem only arises in well
+        confined corner cases: you need an instruction that does a late use or def followed by an
+        instruction that does an early def. Register clobbers count as defs for this equation.
+        Fortunately, early defs are rare, and even when they do happen, you still need the previous
+        instruction to have a late something. Late uses are rare and many instructions don't have defs at
+        all, which means that it's actually pretty common for an instruction to not have anything late.
+        This means that the padInterference() strategy is ideal: our algorithms stay simple because they
+        only have to worry about interference at boundaries, and we rarely insert any Nops in
+        padInterference() so the IR stays nice and compact. Those Nops get removed by any phase that does
+        DCE, which includes eliminateDeadCode(), allocateStack(), and reportUsedRegisters(). In practice
+        allocateStack() kills them.
+        
+        This also finally refactors our passing of RegisterSet to pass it by value, since it's small
+        enough that we're not gaining anything by using references. On x86, RegisterSet ought to be
+        smaller than a pointer.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * b3/B3StackmapSpecial.cpp:
+        (JSC::B3::StackmapSpecial::extraClobberedRegs):
+        (JSC::B3::StackmapSpecial::extraEarlyClobberedRegs):
+        * b3/B3StackmapSpecial.h:
+        * b3/air/AirCCallSpecial.cpp:
+        (JSC::B3::Air::CCallSpecial::extraEarlyClobberedRegs):
+        (JSC::B3::Air::CCallSpecial::extraClobberedRegs):
+        * b3/air/AirCCallSpecial.h:
+        * b3/air/AirInst.h:
+        * b3/air/AirInstInlines.h:
+        (JSC::B3::Air::Inst::extraClobberedRegs):
+        (JSC::B3::Air::Inst::extraEarlyClobberedRegs):
+        * b3/air/AirIteratedRegisterCoalescing.cpp:
+        (JSC::B3::Air::iteratedRegisterCoalescing):
+        * b3/air/AirPadInterference.cpp: Added.
+        (JSC::B3::Air::padInterference):
+        * b3/air/AirPadInterference.h: Added.
+        * b3/air/AirSpecial.h:
+        * b3/air/AirSpillEverything.cpp:
+        (JSC::B3::Air::spillEverything):
+        * jit/RegisterSet.h:
+        (JSC::RegisterSet::isEmpty):
+
 2016-10-17  JF Bastien  <jfbastien@apple.com>
 
         WebAssembly JS API: implement basic stub
index a9349f1..a192e89 100644 (file)
                0F9B1DB41C0E42A500E5BFD2 /* FTLOutput.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9B1DB31C0E42A500E5BFD2 /* FTLOutput.cpp */; };
                0F9B1DB71C0E42BD00E5BFD2 /* FTLOSRExitHandle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9B1DB51C0E42BD00E5BFD2 /* FTLOSRExitHandle.cpp */; };
                0F9B1DB81C0E42BD00E5BFD2 /* FTLOSRExitHandle.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9B1DB61C0E42BD00E5BFD2 /* FTLOSRExitHandle.h */; };
+               0F9CABC81DB54A780008E83B /* AirPadInterference.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9CABC61DB54A760008E83B /* AirPadInterference.cpp */; };
+               0F9CABC91DB54A7A0008E83B /* AirPadInterference.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9CABC71DB54A760008E83B /* AirPadInterference.h */; };
                0F9D3370165DBB90005AD387 /* Disassembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D336E165DBB8D005AD387 /* Disassembler.cpp */; };
                0F9D339617FFC4E60073C2BC /* DFGFlushedAt.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D339417FFC4E60073C2BC /* DFGFlushedAt.cpp */; };
                0F9D339717FFC4E60073C2BC /* DFGFlushedAt.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9D339517FFC4E60073C2BC /* DFGFlushedAt.h */; };
                0F9B1DB31C0E42A500E5BFD2 /* FTLOutput.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLOutput.cpp; path = ftl/FTLOutput.cpp; sourceTree = "<group>"; };
                0F9B1DB51C0E42BD00E5BFD2 /* FTLOSRExitHandle.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLOSRExitHandle.cpp; path = ftl/FTLOSRExitHandle.cpp; sourceTree = "<group>"; };
                0F9B1DB61C0E42BD00E5BFD2 /* FTLOSRExitHandle.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLOSRExitHandle.h; path = ftl/FTLOSRExitHandle.h; sourceTree = "<group>"; };
+               0F9CABC61DB54A760008E83B /* AirPadInterference.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirPadInterference.cpp; path = b3/air/AirPadInterference.cpp; sourceTree = "<group>"; };
+               0F9CABC71DB54A760008E83B /* AirPadInterference.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirPadInterference.h; path = b3/air/AirPadInterference.h; sourceTree = "<group>"; };
                0F9D336E165DBB8D005AD387 /* Disassembler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Disassembler.cpp; path = disassembler/Disassembler.cpp; sourceTree = "<group>"; };
                0F9D339417FFC4E60073C2BC /* DFGFlushedAt.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGFlushedAt.cpp; path = dfg/DFGFlushedAt.cpp; sourceTree = "<group>"; };
                0F9D339517FFC4E60073C2BC /* DFGFlushedAt.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFlushedAt.h; path = dfg/DFGFlushedAt.h; sourceTree = "<group>"; };
                                264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
                                0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */,
                                0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */,
+                               0F9CABC61DB54A760008E83B /* AirPadInterference.cpp */,
+                               0F9CABC71DB54A760008E83B /* AirPadInterference.h */,
                                0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */,
                                0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */,
                                0F45703A1BE45F0A0062A629 /* AirReportUsedRegisters.cpp */,
                                0FF2CD5C1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h in Headers */,
                                A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */,
                                86ECA3EA132DEF1C002B2AD7 /* DFGNode.h in Headers */,
+                               0F9CABC91DB54A7A0008E83B /* AirPadInterference.h in Headers */,
                                0FFB921B16D02F010055A5DB /* DFGNodeAllocator.h in Headers */,
                                0FA581BB150E953000B9A2D9 /* DFGNodeFlags.h in Headers */,
                                0F300B7818AB051100A6D72E /* DFGNodeOrigin.h in Headers */,
                                A74DEF95182D991400522C22 /* JSMapIterator.cpp in Sources */,
                                E3D239C81B829C1C00BBEF67 /* JSModuleEnvironment.cpp in Sources */,
                                E318CBC01B8AEF5100A2929D /* JSModuleNamespaceObject.cpp in Sources */,
+                               0F9CABC81DB54A780008E83B /* AirPadInterference.cpp in Sources */,
                                E39DA4A61B7E8B7C0084F33A /* JSModuleRecord.cpp in Sources */,
                                0FB387921BFD31A100E3AB1E /* FTLCompile.cpp in Sources */,
                                E33E8D1C1B9013C300346B52 /* JSNativeStdFunction.cpp in Sources */,
index f3f929d..8cf81d0 100644 (file)
@@ -55,7 +55,7 @@ void StackmapSpecial::reportUsedRegisters(Inst& inst, const RegisterSet& usedReg
     value->m_usedRegisters.merge(usedRegisters);
 }
 
-const RegisterSet& StackmapSpecial::extraClobberedRegs(Inst& inst)
+RegisterSet StackmapSpecial::extraClobberedRegs(Inst& inst)
 {
     StackmapValue* value = inst.origin->as<StackmapValue>();
     ASSERT(value);
@@ -63,7 +63,7 @@ const RegisterSet& StackmapSpecial::extraClobberedRegs(Inst& inst)
     return value->lateClobbered();
 }
 
-const RegisterSet& StackmapSpecial::extraEarlyClobberedRegs(Inst& inst)
+RegisterSet StackmapSpecial::extraEarlyClobberedRegs(Inst& inst)
 {
     StackmapValue* value = inst.origin->as<StackmapValue>();
     ASSERT(value);
index a158949..bd6a3b5 100644 (file)
@@ -52,8 +52,8 @@ public:
 
 protected:
     void reportUsedRegisters(Air::Inst&, const RegisterSet&) override;
-    const RegisterSet& extraEarlyClobberedRegs(Air::Inst&) override;
-    const RegisterSet& extraClobberedRegs(Air::Inst&) override;
+    RegisterSet extraEarlyClobberedRegs(Air::Inst&) override;
+    RegisterSet extraClobberedRegs(Air::Inst&) override;
 
     // Note that this does not override generate() or dumpImpl()/deepDumpImpl(). We have many some
     // subclasses that implement that.
index 72b5fde..f1b6d71 100644 (file)
@@ -142,12 +142,12 @@ CCallHelpers::Jump CCallSpecial::generate(Inst& inst, CCallHelpers& jit, Generat
     return CCallHelpers::Jump();
 }
 
-const RegisterSet& CCallSpecial::extraEarlyClobberedRegs(Inst&)
+RegisterSet CCallSpecial::extraEarlyClobberedRegs(Inst&)
 {
     return m_emptyRegs;
 }
 
-const RegisterSet& CCallSpecial::extraClobberedRegs(Inst&)
+RegisterSet CCallSpecial::extraClobberedRegs(Inst&)
 {
     return m_clobberedRegs;
 }
index f5cf73b..ec909b9 100644 (file)
@@ -57,8 +57,8 @@ protected:
     bool admitsStack(Inst&, unsigned argIndex) override;
     void reportUsedRegisters(Inst&, const RegisterSet&) override;
     CCallHelpers::Jump generate(Inst&, CCallHelpers&, GenerationContext&) override;
-    const RegisterSet& extraEarlyClobberedRegs(Inst&) override;
-    const RegisterSet& extraClobberedRegs(Inst&) override;
+    RegisterSet extraEarlyClobberedRegs(Inst&) override;
+    RegisterSet extraClobberedRegs(Inst&) override;
 
     void dumpImpl(PrintStream&) const override;
     void deepDumpImpl(PrintStream&) const override;
index b1dc9cb..30f24d8 100644 (file)
@@ -128,8 +128,8 @@ public:
 
     // Reports any additional registers clobbered by this operation. Note that for efficiency,
     // extraClobberedRegs() only works for the Patch opcode.
-    const RegisterSet& extraClobberedRegs();
-    const RegisterSet& extraEarlyClobberedRegs();
+    RegisterSet extraClobberedRegs();
+    RegisterSet extraEarlyClobberedRegs();
 
     // Iterate over all Def's that happen at the end of an instruction. You supply a pair
     // instructions. The instructions must appear next to each other, in that order, in some basic
index 9249492..be11605 100644 (file)
@@ -44,13 +44,13 @@ void Inst::forEach(const Functor& functor)
         });
 }
 
-inline const RegisterSet& Inst::extraClobberedRegs()
+inline RegisterSet Inst::extraClobberedRegs()
 {
     ASSERT(kind.opcode == Patch);
     return args[0].special()->extraClobberedRegs(*this);
 }
 
-inline const RegisterSet& Inst::extraEarlyClobberedRegs()
+inline RegisterSet Inst::extraEarlyClobberedRegs()
 {
     ASSERT(kind.opcode == Patch);
     return args[0].special()->extraEarlyClobberedRegs(*this);
index 2c7c28b..94d6291 100644 (file)
@@ -32,6 +32,7 @@
 #include "AirInsertionSet.h"
 #include "AirInstInlines.h"
 #include "AirLiveness.h"
+#include "AirPadInterference.h"
 #include "AirPhaseScope.h"
 #include "AirTmpInlines.h"
 #include "AirTmpWidth.h"
@@ -844,9 +845,10 @@ public:
 
         Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
         if (!reg) {
-            // We only care about Tmps that interfere. A Tmp that never interfere with anything
-            // can take any register.
-            reg = m_code.regsInPriorityOrder(type).first();
+            dataLog("FATAL: No color for ", tmp, "\n");
+            dataLog("Code:\n");
+            dataLog(m_code);
+            RELEASE_ASSERT_NOT_REACHED();
         }
         return reg;
     }
@@ -928,6 +930,8 @@ private:
 
     void build(Inst* prevInst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
     {
+        if (traceDebug)
+            dataLog("Building between ", pointerDump(prevInst), " and ", pointerDump(nextInst), ":\n");
         Inst::forEachDefWithExtraClobberedRegs<Tmp>(
             prevInst, nextInst,
             [&] (const Tmp& arg, Arg::Role, Arg::Type argType, Arg::Width) {
@@ -943,6 +947,8 @@ private:
                         if (argType != type)
                             return;
                         
+                        if (traceDebug)
+                            dataLog("    Adding def-def edge: ", arg, ", ", otherArg, "\n");
                         this->addEdge(arg, otherArg);
                     });
             });
@@ -979,8 +985,11 @@ private:
             }
 
             for (const Tmp& liveTmp : localCalc.live()) {
-                if (liveTmp != useTmp)
+                if (liveTmp != useTmp) {
+                    if (traceDebug)
+                        dataLog("    Adding def-live for coalescable: ", defTmp, ", ", liveTmp, "\n");
                     addEdge(defTmp, liveTmp);
+                }
             }
 
             // The next instruction could have early clobbers or early def's. We need to consider
@@ -1026,6 +1035,10 @@ private:
                 
                 for (const Tmp& liveTmp : liveTmps) {
                     ASSERT(liveTmp.isGP() == (type == Arg::GP));
+                    
+                    if (traceDebug)
+                        dataLog("    Adding def-live edge: ", arg, ", ", liveTmp, "\n");
+                    
                     addEdge(arg, liveTmp);
                 }
 
@@ -1256,6 +1269,8 @@ public:
 
     void run()
     {
+        padInterference(m_code);
+        
         iteratedRegisterCoalescingOnType<Arg::GP>();
         iteratedRegisterCoalescingOnType<Arg::FP>();
 
@@ -1569,7 +1584,7 @@ private:
 void iteratedRegisterCoalescing(Code& code)
 {
     PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
-
+    
     IteratedRegisterCoalescing iteratedRegisterCoalescing(code);
     iteratedRegisterCoalescing.run();
 }
diff --git a/Source/JavaScriptCore/b3/air/AirPadInterference.cpp b/Source/JavaScriptCore/b3/air/AirPadInterference.cpp
new file mode 100644 (file)
index 0000000..91de56b
--- /dev/null
@@ -0,0 +1,88 @@
+/*
+ * 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 "AirPadInterference.h"
+
+#if ENABLE(B3_JIT)
+
+#include "AirCode.h"
+#include "AirInsertionSet.h"
+#include "AirInstInlines.h"
+
+namespace JSC { namespace B3 { namespace Air {
+
+void padInterference(Code& code)
+{
+    InsertionSet insertionSet(code);
+    for (BasicBlock* block : code) {
+        bool prevHadLate = false;
+        for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+            Inst& inst = block->at(instIndex);
+            
+            bool hasEarlyDef = false;
+            bool hasLate = false;
+            inst.forEachArg(
+                [&] (Arg&, Arg::Role role, Arg::Type, Arg::Width) {
+                    switch (role) {
+                    case Arg::EarlyDef:
+                        hasEarlyDef = true;
+                        break;
+                    case Arg::LateUse:
+                    case Arg::Def:
+                    case Arg::ZDef:
+                    case Arg::LateColdUse:
+                    case Arg::UseDef:
+                    case Arg::UseZDef:
+                        hasLate = true;
+                        break;
+                    case Arg::Scratch:
+                        hasEarlyDef = true;
+                        hasLate = true;
+                        break;
+                    case Arg::Use:
+                    case Arg::ColdUse:
+                    case Arg::UseAddr:
+                        break;
+                    }
+                });
+            if (inst.kind.opcode == Patch) {
+                hasEarlyDef |= !inst.extraEarlyClobberedRegs().isEmpty();
+                hasLate |= !inst.extraClobberedRegs().isEmpty();
+            }
+            
+            if (hasEarlyDef && prevHadLate)
+                insertionSet.insert(instIndex, Nop, inst.origin);
+            
+            prevHadLate = hasLate;
+        }
+        insertionSet.execute(block);
+    }
+}
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/air/AirPadInterference.h b/Source/JavaScriptCore/b3/air/AirPadInterference.h
new file mode 100644 (file)
index 0000000..18f8083
--- /dev/null
@@ -0,0 +1,48 @@
+/*
+ * 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. 
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// This isn't a phase - it's meant to be a utility that other phases use. Air reasons about liveness by
+// reasoning about interference at boundaries between instructions. This can go wrong - for example, a
+// late use in one instruction doesn't actually interfere with an early def of the next instruction, but
+// Air thinks that it does. This is convenient because it works great in the most common case: early uses
+// and late defs. In practice, only the register allocators need to use this, since only they need to be
+// able to color the interference graph using a bounded number of colors.
+//
+// See https://bugs.webkit.org/show_bug.cgi?id=163548#c2 for more info.
+
+void padInterference(Code&);
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
index cd2ad2b..6c10cb5 100644 (file)
@@ -84,8 +84,8 @@ public:
     
     virtual CCallHelpers::Jump generate(Inst&, CCallHelpers&, GenerationContext&) = 0;
 
-    virtual const RegisterSet& extraEarlyClobberedRegs(Inst&) = 0;
-    virtual const RegisterSet& extraClobberedRegs(Inst&) = 0;
+    virtual RegisterSet extraEarlyClobberedRegs(Inst&) = 0;
+    virtual RegisterSet extraClobberedRegs(Inst&) = 0;
     
     // By default, this returns false.
     virtual bool isTerminal(Inst&);
index 35d412e..ebf3774 100644 (file)
@@ -33,6 +33,7 @@
 #include "AirInsertionSet.h"
 #include "AirInstInlines.h"
 #include "AirLiveness.h"
+#include "AirPadInterference.h"
 #include "AirPhaseScope.h"
 #include <wtf/IndexMap.h>
 
@@ -41,6 +42,8 @@ namespace JSC { namespace B3 { namespace Air {
 void spillEverything(Code& code)
 {
     PhaseScope phaseScope(code, "spillEverything");
+    
+    padInterference(code);
 
     // We want to know the set of registers used at every point in every basic block.
     IndexMap<BasicBlock, Vector<RegisterSet>> usedRegisters(code.size());
index aec53c9..0359066 100644 (file)
@@ -107,6 +107,8 @@ public:
     size_t numberOfSetFPRs() const;
     size_t numberOfSetRegisters() const { return m_bits.count(); }
     
+    bool isEmpty() const { return m_bits.isEmpty(); }
+    
     JS_EXPORT_PRIVATE void dump(PrintStream&) const;
     
     enum EmptyValueTag { EmptyValue };