Changeset 207434 in webkit


Ignore:
Timestamp:
Oct 17, 2016 2:45:56 PM (8 years ago)
Author:
fpizlo@apple.com
Message:

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):

Location:
trunk/Source/JavaScriptCore
Files:
2 added
13 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/CMakeLists.txt

    r207432 r207434  
    9696    b3/air/AirLowerMacros.cpp
    9797    b3/air/AirOptimizeBlockOrder.cpp
     98    b3/air/AirPadInterference.cpp
    9899    b3/air/AirPhaseScope.cpp
    99100    b3/air/AirReportUsedRegisters.cpp

  • trunk/Source/JavaScriptCore/ChangeLog

    r207432 r207434  
     12016-10-17  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Air::IRC doesn't need to have a special-case for uncolored Tmps since they all get colored
     4        https://bugs.webkit.org/show_bug.cgi?id=163548
     5        <rdar://problem/28804381>
     6
     7        Reviewed by Geoffrey Garen.
     8       
     9        Before r207408, IRC had a mode where it would silently assign the first assignable register (so
     10        %rax, %xmm0, etc) to any tmp that was not colorable due to a pathological interference fencepost.
     11        We reason about interference at instruction boundaries. This means that if you have, for example,
     12        an instruction that clobbers all registers late followed by an instruction that has an early def
     13        in the same register file, then the early def will not be colorable because it interferes with
     14        all registers. This already happens in our tests, but IRC silently returns the first assignable
     15        register to such tmps. For some reason the resulting code works OK - probably because this tends
     16        to only be hit by fuzzing, which may not then stress that code enough to shake out the register
     17        corruption. Also, this can only happen for floating point registers, so it's hard to get an
     18        exciting crash. The worst case is that your numbers get all messed up.
     19       
     20        This change fixes the issue:
     21       
     22        - IRC will now crash if it can't color a tmp.
     23       
     24        - IRC doesn't crash on our tests anymore because I added a padInterference() utility that works
     25          around the interference problem by inserting Nops to pad between those instructions where
     26          conflating their early and late actions into one interference fencepost could create an
     27          uncolorable graph.
     28       
     29        See https://bugs.webkit.org/show_bug.cgi?id=163548#c2 for a detailed discussion of how the
     30        problem can arise.
     31       
     32        This problem almost made me want to abandon our use of interference at instruction boundaries,
     33        and introduce something more comprehensive, like interference at various stages of an
     34        instruction's execution. The reason why I didn't do this is that this problem only arises in well
     35        confined corner cases: you need an instruction that does a late use or def followed by an
     36        instruction that does an early def. Register clobbers count as defs for this equation.
     37        Fortunately, early defs are rare, and even when they do happen, you still need the previous
     38        instruction to have a late something. Late uses are rare and many instructions don't have defs at
     39        all, which means that it's actually pretty common for an instruction to not have anything late.
     40        This means that the padInterference() strategy is ideal: our algorithms stay simple because they
     41        only have to worry about interference at boundaries, and we rarely insert any Nops in
     42        padInterference() so the IR stays nice and compact. Those Nops get removed by any phase that does
     43        DCE, which includes eliminateDeadCode(), allocateStack(), and reportUsedRegisters(). In practice
     44        allocateStack() kills them.
     45       
     46        This also finally refactors our passing of RegisterSet to pass it by value, since it's small
     47        enough that we're not gaining anything by using references. On x86, RegisterSet ought to be
     48        smaller than a pointer.
     49
     50        * CMakeLists.txt:
     51        * JavaScriptCore.xcodeproj/project.pbxproj:
     52        * b3/B3StackmapSpecial.cpp:
     53        (JSC::B3::StackmapSpecial::extraClobberedRegs):
     54        (JSC::B3::StackmapSpecial::extraEarlyClobberedRegs):
     55        * b3/B3StackmapSpecial.h:
     56        * b3/air/AirCCallSpecial.cpp:
     57        (JSC::B3::Air::CCallSpecial::extraEarlyClobberedRegs):
     58        (JSC::B3::Air::CCallSpecial::extraClobberedRegs):
     59        * b3/air/AirCCallSpecial.h:
     60        * b3/air/AirInst.h:
     61        * b3/air/AirInstInlines.h:
     62        (JSC::B3::Air::Inst::extraClobberedRegs):
     63        (JSC::B3::Air::Inst::extraEarlyClobberedRegs):
     64        * b3/air/AirIteratedRegisterCoalescing.cpp:
     65        (JSC::B3::Air::iteratedRegisterCoalescing):
     66        * b3/air/AirPadInterference.cpp: Added.
     67        (JSC::B3::Air::padInterference):
     68        * b3/air/AirPadInterference.h: Added.
     69        * b3/air/AirSpecial.h:
     70        * b3/air/AirSpillEverything.cpp:
     71        (JSC::B3::Air::spillEverything):
     72        * jit/RegisterSet.h:
     73        (JSC::RegisterSet::isEmpty):
     74
    1752016-10-17  JF Bastien  <jfbastien@apple.com>
    276

  • trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r207432 r207434  
    571571                0F9B1DB71C0E42BD00E5BFD2 /* FTLOSRExitHandle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9B1DB51C0E42BD00E5BFD2 /* FTLOSRExitHandle.cpp */; };
    572572                0F9B1DB81C0E42BD00E5BFD2 /* FTLOSRExitHandle.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9B1DB61C0E42BD00E5BFD2 /* FTLOSRExitHandle.h */; };
     573                0F9CABC81DB54A780008E83B /* AirPadInterference.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9CABC61DB54A760008E83B /* AirPadInterference.cpp */; };
     574                0F9CABC91DB54A7A0008E83B /* AirPadInterference.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9CABC71DB54A760008E83B /* AirPadInterference.h */; };
    573575                0F9D3370165DBB90005AD387 /* Disassembler.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D336E165DBB8D005AD387 /* Disassembler.cpp */; };
    574576                0F9D339617FFC4E60073C2BC /* DFGFlushedAt.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D339417FFC4E60073C2BC /* DFGFlushedAt.cpp */; };
    … …  
    28412843                0F9B1DB51C0E42BD00E5BFD2 /* FTLOSRExitHandle.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLOSRExitHandle.cpp; path = ftl/FTLOSRExitHandle.cpp; sourceTree = "<group>"; };
    28422844                0F9B1DB61C0E42BD00E5BFD2 /* FTLOSRExitHandle.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLOSRExitHandle.h; path = ftl/FTLOSRExitHandle.h; sourceTree = "<group>"; };
     2845                0F9CABC61DB54A760008E83B /* AirPadInterference.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirPadInterference.cpp; path = b3/air/AirPadInterference.cpp; sourceTree = "<group>"; };
     2846                0F9CABC71DB54A760008E83B /* AirPadInterference.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirPadInterference.h; path = b3/air/AirPadInterference.h; sourceTree = "<group>"; };
    28432847                0F9D336E165DBB8D005AD387 /* Disassembler.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = Disassembler.cpp; path = disassembler/Disassembler.cpp; sourceTree = "<group>"; };
    28442848                0F9D339417FFC4E60073C2BC /* DFGFlushedAt.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGFlushedAt.cpp; path = dfg/DFGFlushedAt.cpp; sourceTree = "<group>"; };
    … …  
    50825086                                0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */,
    50835087                                0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */,
     5088                                0F9CABC61DB54A760008E83B /* AirPadInterference.cpp */,
     5089                                0F9CABC71DB54A760008E83B /* AirPadInterference.h */,
    50845090                                0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */,
    50855091                                0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */,
    … …  
    76307636                                A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */,
    76317637                                86ECA3EA132DEF1C002B2AD7 /* DFGNode.h in Headers */,
     7638                                0F9CABC91DB54A7A0008E83B /* AirPadInterference.h in Headers */,
    76327639                                0FFB921B16D02F010055A5DB /* DFGNodeAllocator.h in Headers */,
    76337640                                0FA581BB150E953000B9A2D9 /* DFGNodeFlags.h in Headers */,
    … …  
    95479554                                E3D239C81B829C1C00BBEF67 /* JSModuleEnvironment.cpp in Sources */,
    95489555                                E318CBC01B8AEF5100A2929D /* JSModuleNamespaceObject.cpp in Sources */,
     9556                                0F9CABC81DB54A780008E83B /* AirPadInterference.cpp in Sources */,
    95499557                                E39DA4A61B7E8B7C0084F33A /* JSModuleRecord.cpp in Sources */,
    95509558                                0FB387921BFD31A100E3AB1E /* FTLCompile.cpp in Sources */,

  • trunk/Source/JavaScriptCore/b3/B3StackmapSpecial.cpp

    r203488 r207434  
    5656}
    5757
    58 const RegisterSet& StackmapSpecial::extraClobberedRegs(Inst& inst)
     58RegisterSet StackmapSpecial::extraClobberedRegs(Inst& inst)
    5959{
    6060    StackmapValue* value = inst.origin->as<StackmapValue>();
    … …  
    6464}
    6565
    66 const RegisterSet& StackmapSpecial::extraEarlyClobberedRegs(Inst& inst)
     66RegisterSet StackmapSpecial::extraEarlyClobberedRegs(Inst& inst)
    6767{
    6868    StackmapValue* value = inst.origin->as<StackmapValue>();

  • trunk/Source/JavaScriptCore/b3/B3StackmapSpecial.h

    r206525 r207434  
    5353protected:
    5454    void reportUsedRegisters(Air::Inst&, const RegisterSet&) override;
    55     const RegisterSet& extraEarlyClobberedRegs(Air::Inst&) override;
    56     const RegisterSet& extraClobberedRegs(Air::Inst&) override;
     55    RegisterSet extraEarlyClobberedRegs(Air::Inst&) override;
     56    RegisterSet extraClobberedRegs(Air::Inst&) override;
    5757
    5858    // Note that this does not override generate() or dumpImpl()/deepDumpImpl(). We have many some

  • trunk/Source/JavaScriptCore/b3/air/AirCCallSpecial.cpp

    r196736 r207434  
    143143}
    144144
    145 const RegisterSet& CCallSpecial::extraEarlyClobberedRegs(Inst&)
     145RegisterSet CCallSpecial::extraEarlyClobberedRegs(Inst&)
    146146{
    147147    return m_emptyRegs;
    148148}
    149149
    150 const RegisterSet& CCallSpecial::extraClobberedRegs(Inst&)
     150RegisterSet CCallSpecial::extraClobberedRegs(Inst&)
    151151{
    152152    return m_clobberedRegs;

  • trunk/Source/JavaScriptCore/b3/air/AirCCallSpecial.h

    r206525 r207434  
    5858    void reportUsedRegisters(Inst&, const RegisterSet&) override;
    5959    CCallHelpers::Jump generate(Inst&, CCallHelpers&, GenerationContext&) override;
    60     const RegisterSet& extraEarlyClobberedRegs(Inst&) override;
    61     const RegisterSet& extraClobberedRegs(Inst&) override;
     60    RegisterSet extraEarlyClobberedRegs(Inst&) override;
     61    RegisterSet extraClobberedRegs(Inst&) override;
    6262
    6363    void dumpImpl(PrintStream&) const override;

  • trunk/Source/JavaScriptCore/b3/air/AirInst.h

    r206640 r207434  
    129129    // Reports any additional registers clobbered by this operation. Note that for efficiency,
    130130    // extraClobberedRegs() only works for the Patch opcode.
    131     const RegisterSet& extraClobberedRegs();
    132     const RegisterSet& extraEarlyClobberedRegs();
     131    RegisterSet extraClobberedRegs();
     132    RegisterSet extraEarlyClobberedRegs();
    133133
    134134    // Iterate over all Def's that happen at the end of an instruction. You supply a pair

  • trunk/Source/JavaScriptCore/b3/air/AirInstInlines.h

    r206640 r207434  
    4545}
    4646
    47 inline const RegisterSet& Inst::extraClobberedRegs()
     47inline RegisterSet Inst::extraClobberedRegs()
    4848{
    4949    ASSERT(kind.opcode == Patch);
    … …  
    5151}
    5252
    53 inline const RegisterSet& Inst::extraEarlyClobberedRegs()
     53inline RegisterSet Inst::extraEarlyClobberedRegs()
    5454{
    5555    ASSERT(kind.opcode == Patch);

  • trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp

    r207408 r207434  
    3333#include "AirInstInlines.h"
    3434#include "AirLiveness.h"
     35#include "AirPadInterference.h"
    3536#include "AirPhaseScope.h"
    3637#include "AirTmpInlines.h"
    … …  
    845846        Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
    846847        if (!reg) {
    847             // We only care about Tmps that interfere. A Tmp that never interfere with anything
    848             // can take any register.
    849             reg = m_code.regsInPriorityOrder(type).first();
     848            dataLog("FATAL: No color for ", tmp, "\n");
     849            dataLog("Code:\n");
     850            dataLog(m_code);
     851            RELEASE_ASSERT_NOT_REACHED();
    850852        }
    851853        return reg;
    … …  
    929931    void build(Inst* prevInst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
    930932    {
     933        if (traceDebug)
     934            dataLog("Building between ", pointerDump(prevInst), " and ", pointerDump(nextInst), ":\n");
    931935        Inst::forEachDefWithExtraClobberedRegs<Tmp>(
    932936            prevInst, nextInst,
    … …  
    944948                            return;
    945949                       
     950                        if (traceDebug)
     951                            dataLog("    Adding def-def edge: ", arg, ", ", otherArg, "\n");
    946952                        this->addEdge(arg, otherArg);
    947953                    });
    … …  
    980986
    981987            for (const Tmp& liveTmp : localCalc.live()) {
    982                 if (liveTmp != useTmp)
     988                if (liveTmp != useTmp) {
     989                    if (traceDebug)
     990                        dataLog("    Adding def-live for coalescable: ", defTmp, ", ", liveTmp, "\n");
    983991                    addEdge(defTmp, liveTmp);
     992                }
    984993            }
    985994
    … …  
    10271036                for (const Tmp& liveTmp : liveTmps) {
    10281037                    ASSERT(liveTmp.isGP() == (type == Arg::GP));
     1038                   
     1039                    if (traceDebug)
     1040                        dataLog("    Adding def-live edge: ", arg, ", ", liveTmp, "\n");
     1041                   
    10291042                    addEdge(arg, liveTmp);
    10301043                }
    … …  
    12571270    void run()
    12581271    {
     1272        padInterference(m_code);
     1273       
    12591274        iteratedRegisterCoalescingOnType<Arg::GP>();
    12601275        iteratedRegisterCoalescingOnType<Arg::FP>();
    … …  
    15701585{
    15711586    PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
    1572 
     1587   
    15731588    IteratedRegisterCoalescing iteratedRegisterCoalescing(code);
    15741589    iteratedRegisterCoalescing.run();

  • trunk/Source/JavaScriptCore/b3/air/AirSpecial.h

    r206525 r207434  
    8585    virtual CCallHelpers::Jump generate(Inst&, CCallHelpers&, GenerationContext&) = 0;
    8686
    87     virtual const RegisterSet& extraEarlyClobberedRegs(Inst&) = 0;
    88     virtual const RegisterSet& extraClobberedRegs(Inst&) = 0;
     87    virtual RegisterSet extraEarlyClobberedRegs(Inst&) = 0;
     88    virtual RegisterSet extraClobberedRegs(Inst&) = 0;
    8989   
    9090    // By default, this returns false.

  • trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp

    r207004 r207434  
    3434#include "AirInstInlines.h"
    3535#include "AirLiveness.h"
     36#include "AirPadInterference.h"
    3637#include "AirPhaseScope.h"
    3738#include <wtf/IndexMap.h>
    … …  
    4243{
    4344    PhaseScope phaseScope(code, "spillEverything");
     45   
     46    padInterference(code);
    4447
    4548    // We want to know the set of registers used at every point in every basic block.

  • trunk/Source/JavaScriptCore/jit/RegisterSet.h

    r207004 r207434  
    108108    size_t numberOfSetRegisters() const { return m_bits.count(); }
    109109   
     110    bool isEmpty() const { return m_bits.isEmpty(); }
     111   
    110112    JS_EXPORT_PRIVATE void dump(PrintStream&) const;
    111113   
Note: See TracChangeset for help on using the changeset viewer.