⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 194402 in webkit


Ignore:
Timestamp:
Dec 23, 2015, 4:26:04 PM (11 years ago)
Author:
fpizlo@apple.com
Message:

FTL B3 should be able to run crypto-sha1 in eager mode
​https://bugs.webkit.org/show_bug.cgi?id=152539

Reviewed by Saam Barati.

This patch contains one real bug fix and some other fixes that are primarily there for sanity
because I don't believe they are symptomatic.

The real fix is the instruction selector's handling of Phi. It was assuming that the correct
lowering of Phi is to do nothing and the correct lowering of Upsilon is to store into the tmp
that the Phi uses. But this fails for code patterns like:

@a = Phi()
Upsilon(@x, a)
use(@a) this should see the value that @a had at the point that "@a = Phi()" executed.

This arises when we have a lot of Upsilons in a row and they are trying to perform a
shuffling. Prior to this change, "use(@a)" would see the new value of @a, i.e. @x. That's
wrong. So, this changes the lowering to make each Phi have a special shadow Tmp, and Upsilon
stores to it while Phi loads from it. Most of these assignments get copy-propagated by IRC,
so it doesn't really hurt us. I couldn't find any benchmarks that slowed down because of
this. In fact, I believe that the only time that this would lead to extra interference or
extra assignments is when it's actually needed to be correct.

This also contains other fixes, which are probably not for real bugs, but they make me feel
all warm and fuzzy:

  • spillEverything() works again. Previously, it didn't have all of IRC's smarts for handling a spill of a ZDef. I fixed this by creating a helper phase that finds all subwidth ZDefs to spill slots and amends them with zero-fills of the top bits.
  • IRC no longer requires precise TmpWidth analysis. Previously, if TmpWidth gave pessimistic results, the subwidth ZDef bug would return. That probably means that it was never fixed to begin with, since it's totally cool for just a single def or use of a tmp to cause it to become pessimistic. But there may still have been some subwidth ZDefs. The way that I fixed this bug is to have IRC also run the ZDef fixup code that spillEverything() uses. This is abstracted behind the beautifully named Air::fixSpillSlotZDef().
  • B3::validate() does dominance checks! So, if you shoot yourself in the foot by using something before defining it, validate() will tell you.
  • Air::TmpWidth is now easy to "turn off" - i.e. to make it go fully conservative. It's not an Option; you have to hack code. But that's better than nothing, and it's consistent with what we do for other super-internal compiler options that we use rarely.
  • You can now run spillEverything() without hacking code. Just use Options::airSpillSeverything().

(JSC::B3::Air::LowerToAir::LowerToAir):
(JSC::B3::Air::LowerToAir::run):
(JSC::B3::Air::LowerToAir::lower):

  • b3/B3Validate.cpp:
  • b3/air/AirCode.h:

(JSC::B3::Air::Code::specials):
(JSC::B3::Air::Code::forAllTmps):
(JSC::B3::Air::Code::isFastTmp):

  • b3/air/AirFixSpillSlotZDef.h: Added.

(JSC::B3::Air::fixSpillSlotZDef):

  • b3/air/AirGenerate.cpp:

(JSC::B3::Air::prepareForGeneration):

  • b3/air/AirIteratedRegisterCoalescing.cpp:
  • b3/air/AirSpillEverything.cpp:

(JSC::B3::Air::spillEverything):

  • b3/air/AirTmpWidth.cpp:

(JSC::B3::Air::TmpWidth::recompute):

  • jit/JITOperations.cpp:
  • runtime/Options.h:
Location:
trunk/Source/JavaScriptCore
Files:
1 added
10 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r194401 r194402  
     12015-12-23  Filip Pizlo  <fpizlo@apple.com>
     2
     3        FTL B3 should be able to run crypto-sha1 in eager mode
     4        https://bugs.webkit.org/show_bug.cgi?id=152539
     5
     6        Reviewed by Saam Barati.
     7
     8        This patch contains one real bug fix and some other fixes that are primarily there for sanity
     9        because I don't believe they are symptomatic.
     10
     11        The real fix is the instruction selector's handling of Phi. It was assuming that the correct
     12        lowering of Phi is to do nothing and the correct lowering of Upsilon is to store into the tmp
     13        that the Phi uses. But this fails for code patterns like:
     14
     15            @a = Phi()
     16            Upsilon(@x, ^a)
     17            use(@a) // this should see the value that @a had at the point that "@a = Phi()" executed.
     18
     19        This arises when we have a lot of Upsilons in a row and they are trying to perform a
     20        shuffling. Prior to this change, "use(@a)" would see the new value of @a, i.e. @x. That's
     21        wrong. So, this changes the lowering to make each Phi have a special shadow Tmp, and Upsilon
     22        stores to it while Phi loads from it. Most of these assignments get copy-propagated by IRC,
     23        so it doesn't really hurt us. I couldn't find any benchmarks that slowed down because of
     24        this. In fact, I believe that the only time that this would lead to extra interference or
     25        extra assignments is when it's actually needed to be correct.
     26
     27        This also contains other fixes, which are probably not for real bugs, but they make me feel
     28        all warm and fuzzy:
     29
     30        - spillEverything() works again.  Previously, it didn't have all of IRC's smarts for handling
     31          a spill of a ZDef.  I fixed this by creating a helper phase that finds all subwidth ZDefs
     32          to spill slots and amends them with zero-fills of the top bits.
     33
     34        - IRC no longer requires precise TmpWidth analysis.  Previously, if TmpWidth gave pessimistic
     35          results, the subwidth ZDef bug would return.  That probably means that it was never fixed
     36          to begin with, since it's totally cool for just a single def or use of a tmp to cause it
     37          to become pessimistic. But there may still have been some subwidth ZDefs.  The way that I
     38          fixed this bug is to have IRC also run the ZDef fixup code that spillEverything() uses.
     39          This is abstracted behind the beautifully named Air::fixSpillSlotZDef().
     40
     41        - B3::validate() does dominance checks!  So, if you shoot yourself in the foot by using
     42          something before defining it, validate() will tell you.
     43
     44        - Air::TmpWidth is now easy to "turn off" - i.e. to make it go fully conservative. It's not
     45          an Option; you have to hack code. But that's better than nothing, and it's consistent with
     46          what we do for other super-internal compiler options that we use rarely.
     47
     48        - You can now run spillEverything() without hacking code.  Just use
     49          Options::airSpillSeverything().
     50
     51        * JavaScriptCore.xcodeproj/project.pbxproj:
     52        * b3/B3LowerToAir.cpp:
     53        (JSC::B3::Air::LowerToAir::LowerToAir):
     54        (JSC::B3::Air::LowerToAir::run):
     55        (JSC::B3::Air::LowerToAir::lower):
     56        * b3/B3Validate.cpp:
     57        * b3/air/AirCode.h:
     58        (JSC::B3::Air::Code::specials):
     59        (JSC::B3::Air::Code::forAllTmps):
     60        (JSC::B3::Air::Code::isFastTmp):
     61        * b3/air/AirFixSpillSlotZDef.h: Added.
     62        (JSC::B3::Air::fixSpillSlotZDef):
     63        * b3/air/AirGenerate.cpp:
     64        (JSC::B3::Air::prepareForGeneration):
     65        * b3/air/AirIteratedRegisterCoalescing.cpp:
     66        * b3/air/AirSpillEverything.cpp:
     67        (JSC::B3::Air::spillEverything):
     68        * b3/air/AirTmpWidth.cpp:
     69        (JSC::B3::Air::TmpWidth::recompute):
     70        * jit/JITOperations.cpp:
     71        * runtime/Options.h:
     72
    1732015-12-23  Filip Pizlo  <fpizlo@apple.com>
    274

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

    r194394 r194402  
    375375                0F4B94DC17B9F07500DD03A4 /* TypedArrayInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4B94DB17B9F07500DD03A4 /* TypedArrayInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
    376376                0F4C91661C29F4F2004341A6 /* B3OriginDump.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4C91651C29F4F2004341A6 /* B3OriginDump.h */; };
     377                0F4C91681C2B3D68004341A6 /* AirFixSpillSlotZDef.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4C91671C2B3D68004341A6 /* AirFixSpillSlotZDef.h */; };
    377378                0F4F29DF18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F4F29DD18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp */; };
    378379                0F4F29E018B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */; };
    … …  
    25092510                0F4B94DB17B9F07500DD03A4 /* TypedArrayInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TypedArrayInlines.h; sourceTree = "<group>"; };
    25102511                0F4C91651C29F4F2004341A6 /* B3OriginDump.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3OriginDump.h; path = b3/B3OriginDump.h; sourceTree = "<group>"; };
     2512                0F4C91671C2B3D68004341A6 /* AirFixSpillSlotZDef.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirFixSpillSlotZDef.h; path = b3/air/AirFixSpillSlotZDef.h; sourceTree = "<group>"; };
    25112513                0F4F29DD18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGStaticExecutionCountEstimationPhase.cpp; path = dfg/DFGStaticExecutionCountEstimationPhase.cpp; sourceTree = "<group>"; };
    25122514                0F4F29DE18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGStaticExecutionCountEstimationPhase.h; path = dfg/DFGStaticExecutionCountEstimationPhase.h; sourceTree = "<group>"; };
    … …  
    47774779                                262D85B41C0D650F006ACB61 /* AirFixPartialRegisterStalls.cpp */,
    47784780                                262D85B51C0D650F006ACB61 /* AirFixPartialRegisterStalls.h */,
     4781                                0F4C91671C2B3D68004341A6 /* AirFixSpillSlotZDef.h */,
    47794782                                0FEC85521BDACDC70080FF74 /* AirFrequentedBlock.h */,
    47804783                                0FEC85531BDACDC70080FF74 /* AirGenerate.cpp */,
    … …  
    72177220                                0FBE0F7516C1DB0B0082C5E8 /* DFGPredictionInjectionPhase.h in Headers */,
    72187221                                0FFFC95E14EF90B700C72532 /* DFGPredictionPropagationPhase.h in Headers */,
     7222                                0F4C91681C2B3D68004341A6 /* AirFixSpillSlotZDef.h in Headers */,
    72197223                                0F3E01AB19D353A500F61B7F /* DFGPrePostNumbering.h in Headers */,
    72207224                                0F2B9CED19D0BA7D00B1D1B5 /* DFGPromotedHeapLocation.h in Headers */,

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

    r194401 r194402  
    6565    LowerToAir(Procedure& procedure)
    6666        : m_valueToTmp(procedure.values().size())
     67        , m_phiToTmp(procedure.values().size())
    6768        , m_blockToBlock(procedure.size())
    6869        , m_useCounts(procedure)
    … …  
    7778        for (B3::BasicBlock* block : m_procedure)
    7879            m_blockToBlock[block] = m_code.addBlock(block->frequency());
     80       
    7981        for (Value* value : m_procedure.values()) {
    80             if (StackSlotValue* stackSlotValue = value->as<StackSlotValue>())
     82            switch (value->opcode()) {
     83            case Phi: {
     84                m_phiToTmp[value] = m_code.newTmp(Arg::typeForB3Type(value->type()));
     85                break;
     86            }
     87            case B3::StackSlot: {
     88                StackSlotValue* stackSlotValue = value->as<StackSlotValue>();
    8189                m_stackToStack.add(stackSlotValue, m_code.addStackSlot(stackSlotValue));
     90                break;
     91            }
     92            default:
     93                break;
     94            }
    8295        }
    8396
    … …  
    21272140            append(
    21282141                relaxedMoveForType(value->type()), immOrTmp(value),
    2129                 tmp(m_value->as<UpsilonValue>()->phi()));
     2142                m_phiToTmp[m_value->as<UpsilonValue>()->phi()]);
    21302143            return;
    21312144        }
    21322145
    21332146        case Phi: {
    2134             // Our semantics are determined by Upsilons, so we have nothing to do here.
     2147            // Snapshot the value of the Phi. It may change under us because you could do:
     2148            // a = Phi()
     2149            // Upsilon(@x, ^a)
     2150            // @a => this should get the value of the Phi before the Upsilon, i.e. not @x.
     2151
     2152            append(relaxedMoveForType(m_value->type()), m_phiToTmp[m_value], tmp(m_value));
    21352153            return;
    21362154        }
    … …  
    22102228    IndexSet<Value> m_locked; // These are values that will have no Tmp in Air.
    22112229    IndexMap<Value, Tmp> m_valueToTmp; // These are values that must have a Tmp in Air. We say that a Value* with a non-null Tmp is "pinned".
     2230    IndexMap<Value, Tmp> m_phiToTmp; // Each Phi gets its own Tmp.
    22122231    IndexMap<B3::BasicBlock, Air::BasicBlock*> m_blockToBlock;
    22132232    HashMap<StackSlotValue*, Air::StackSlot*> m_stackToStack;

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

    r194341 r194402  
    3131#include "B3ArgumentRegValue.h"
    3232#include "B3BasicBlockInlines.h"
     33#include "B3Dominators.h"
    3334#include "B3MemoryValue.h"
    3435#include "B3Procedure.h"
    … …  
    6364        HashSet<Value*> valueInProc;
    6465        HashMap<Value*, unsigned> valueInBlock;
     66        HashMap<Value*, BasicBlock*> valueOwner;
     67        HashMap<Value*, unsigned> valueIndex;
    6568
    6669        for (BasicBlock* block : m_procedure) {
    6770            blocks.add(block);
    68             for (Value* value : *block)
     71            for (unsigned i = 0; i < block->size(); ++i) {
     72                Value* value = block->at(i);
    6973                valueInBlock.add(value, 0).iterator->value++;
     74                valueOwner.add(value, block);
     75                valueIndex.add(value, i);
     76            }
    7077        }
    7178
    … …  
    8087        }
    8188
     89        // Compute dominators ourselves to avoid perturbing Procedure.
     90        Dominators dominators(m_procedure);
     91
    8292        for (Value* value : valueInProc) {
    8393            for (Value* child : value->children()) {
    8494                VALIDATE(child, ("At ", *value));
    8595                VALIDATE(valueInProc.contains(child), ("At ", *value, "->", pointerDump(child)));
     96                if (valueOwner.get(child) == valueOwner.get(value))
     97                    VALIDATE(valueIndex.get(value) > valueIndex.get(child), ("At ", *value, "->", pointerDump(child)));
     98                else
     99                    VALIDATE(dominators.dominates(valueOwner.get(child), valueOwner.get(value)), ("at ", *value, "->", pointerDump(child)));
    86100            }
    87101        }

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

    r193682 r194402  
    5858    BasicBlock* addBlock(double frequency = 1);
    5959
     60    // Note that you can rely on stack slots always getting indices that are larger than the index
     61    // of any prior stack slot. In fact, all stack slots you create in the future will have an index
     62    // that is >= stackSlots().size().
    6063    StackSlot* addStackSlot(unsigned byteSize, StackSlotKind, StackSlotValue* = nullptr);
    6164    StackSlot* addStackSlot(StackSlotValue*);
    … …  
    291294
    292295    SpecialsCollection specials() const { return SpecialsCollection(*this); }
     296
     297    template<typename Callback>
     298    void forAllTmps(const Callback& callback) const
     299    {
     300        for (unsigned i = m_numGPTmps; i--;)
     301            callback(Tmp::gpTmpForIndex(i));
     302        for (unsigned i = m_numFPTmps; i--;)
     303            callback(Tmp::fpTmpForIndex(i));
     304    }
    293305
    294306    void addFastTmp(Tmp);

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

    r192981 r194402  
    7575    //
    7676    // For debugging, you can use spillEverything() to put everything to the stack between each Inst.
    77     if (false)
     77    if (Options::airSpillsEverything())
    7878        spillEverything(code);
    7979    else

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

    r194385 r194402  
    3030
    3131#include "AirCode.h"
     32#include "AirFixSpillSlotZDef.h"
    3233#include "AirInsertionSet.h"
    3334#include "AirInstInlines.h"
    … …  
    11651166    {
    11661167        HashMap<Tmp, StackSlot*> stackSlots;
     1168        unsigned newStackSlotThreshold = m_code.stackSlots().size();
    11671169        for (Tmp tmp : allocator.spilledTmps()) {
    11681170            // All the spilled values become unspillable.
    … …  
    12611263            }
    12621264        }
     1265
     1266        fixSpillSlotZDef(
     1267            m_code,
     1268            [&] (StackSlot* stackSlot) -> bool {
     1269                return stackSlot->index() >= newStackSlotThreshold;
     1270            });
    12631271    }
    12641272

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

    r194331 r194402  
    3030
    3131#include "AirCode.h"
     32#include "AirFixSpillSlotZDef.h"
    3233#include "AirInsertionSet.h"
    3334#include "AirInstInlines.h"
    … …  
    8788    // Allocate a stack slot for each tmp.
    8889    Vector<StackSlot*> allStackSlots[Arg::numTypes];
     90    unsigned newStackSlotThreshold = code.stackSlots().size();
    8991    for (unsigned typeIndex = 0; typeIndex < Arg::numTypes; ++typeIndex) {
    9092        Vector<StackSlot*>& stackSlots = allStackSlots[typeIndex];
    … …  
    110112                        continue;
    111113
    112                     if (inst.admitsStack(i)) { 
     114                    if (inst.admitsStack(i)) {
    113115                        StackSlot* stackSlot = allStackSlots[arg.type()][arg.tmpIndex()];
    114116                        arg = Arg::stack(stackSlot);
    … …  
    185187        insertionSet.execute(block);
    186188    }
     189
     190    fixSpillSlotZDef(
     191        code,
     192        [&] (StackSlot* stackSlot) -> bool {
     193            return stackSlot->index() >= newStackSlotThreshold;
     194        });
    187195}
    188196

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

    r194331 r194402  
    4949void TmpWidth::recompute(Code& code)
    5050{
     51    // Set this to true to cause this analysis to always return pessimistic results.
     52    const bool beCareful = false;
     53   
    5154    m_width.clear();
     55   
     56    auto assumeTheWorst = [&] (Tmp tmp) {
     57        Widths& widths = m_width.add(tmp, Widths()).iterator->value;
     58        Arg::Type type = Arg(tmp).type();
     59        widths.use = Arg::conservativeWidth(type);
     60        widths.def = Arg::conservativeWidth(type);
     61    };
    5262   
    5363    // Assume the worst for registers.
    5464    RegisterSet::allRegisters().forEach(
    5565        [&] (Reg reg) {
    56             Widths& widths = m_width.add(Tmp(reg), Widths()).iterator->value;
    57             Arg::Type type = Arg(Tmp(reg)).type();
    58             widths.use = Arg::conservativeWidth(type);
    59             widths.def = Arg::conservativeWidth(type);
     66            assumeTheWorst(Tmp(reg));
    6067        });
    61    
     68
     69    if (beCareful) {
     70        code.forAllTmps(assumeTheWorst);
     71       
     72        // We fall through because the fixpoint that follows can only make things even more
     73        // conservative. This mode isn't meant to be fast, just safe.
     74    }
     75
    6276    // Now really analyze everything but Move's over Tmp's, but set aside those Move's so we can find
    6377    // them quickly during the fixpoint below. Note that we can make this analysis stronger by

  • trunk/Source/JavaScriptCore/runtime/Options.h

    r193424 r194402  
    341341    v(bool, logB3PhaseTimes, false, nullptr) \
    342342    v(double, rareBlockPenalty, 0.001, nullptr) \
     343    v(bool, airSpillsEverything, false, nullptr) \
    343344    \
    344345    v(bool, useDollarVM, false, "installs the $vm debugging tool in global objects") \
Note: See TracChangeset for help on using the changeset viewer.