Changeset 220625 in webkit


Ignore:
Timestamp:
Aug 12, 2017 11:44:48 AM (7 years ago)
Author:
fpizlo@apple.com
Message:

Caging shouldn't have to use a patchpoint for adding
​https://bugs.webkit.org/show_bug.cgi?id=175483

Reviewed by Mark Lam.
Source/JavaScriptCore:

Caging involves doing a Add(ptr, largeConstant). All of B3's heuristics for how to deal with
constants and associative operations dictate that you always want to sink constants. For example,
Add(Add(a, constant), b) always becomes Add(Add(a, b), constant). This is profitable because in
typical code, it reveals downstream optimizations. But it's terrible in the case of caging, because
we want the large constant (which is shared by all caging operations) to be hoisted. Reassociating to
sink constants obscures the constant in this case. Currently, moveConstants is not smart enough to
reassociate, so instead of sinking largeConstant, it tries (and often fails) to sink some other
constants instead. Without some hacks, this is a 5% Kraken regression and a 1.6% Octane regression.
It's not clear that moveConstants could ever be smart enough to rematerialize that constant and then
hoist it - that would require quite a bit of algebraic reasoning. But the only case we know of where
our current constant reassociation heuristics are wrong is caging. So, we can get away with some
hacks for just stopping B3's reassociation only in this specific case.

Previously, we achieved this by concealing the Add(ptr, largeConstant) inside a patchpoint. That's
OK, but patchpoints are expensive. They require a SharedTask instance. They require callbacks from
the backend, including during register allocation. And they cannot be CSE'd. We do want B3 to know
that if we cage the same pointer in two places, both places will compute the same value.

This patch improves the situation by introducing the Opaque opcode. This is handled by LowerToAir as
if it was Identity, but all prior phases treat it as an unknown pure unary idempotent operation. I.e.
they know that Opaque(x) == Opaque(x) and that Opaque(Opaque(x)) == Opaque(x). But they don't know
that Opaque(x) == x until LowerToAir. So, you can use Opaque exactly when you know that B3 will mess
up your code but Air won't. (Currently we know of no cases where Air messes things up on a large
enough scale to warrant new opcodes.)

This change is perf-neutral, but may start to help as I add more uses of caged() in the FTL. It also
makes the code a bit less ugly.

  • b3/B3LowerToAir.cpp:

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

  • b3/B3Opcode.cpp:

(WTF::printInternal):

  • b3/B3Opcode.h:
  • b3/B3ReduceStrength.cpp:
  • b3/B3Validate.cpp:
  • b3/B3Value.cpp:

(JSC::B3::Value::effects const):
(JSC::B3::Value::key const):
(JSC::B3::Value::isFree const):
(JSC::B3::Value::typeFor):

  • b3/B3Value.h:
  • b3/B3ValueKey.cpp:

(JSC::B3::ValueKey::materialize const):

  • ftl/FTLLowerDFGToB3.cpp:

(JSC::FTL::DFG::LowerDFGToB3::caged):

  • ftl/FTLOutput.cpp:

(JSC::FTL::Output::opaque):

  • ftl/FTLOutput.h:

Websites/webkit.org:


Write documentation for the new Opaque opcode.

  • docs/b3/intermediate-representation.html:
Location:
trunk
Files:
14 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r220624 r220625  
     12017-08-11  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Caging shouldn't have to use a patchpoint for adding
     4        https://bugs.webkit.org/show_bug.cgi?id=175483
     5
     6        Reviewed by Mark Lam.
     7
     8        Caging involves doing a Add(ptr, largeConstant). All of B3's heuristics for how to deal with
     9        constants and associative operations dictate that you always want to sink constants. For example,
     10        Add(Add(a, constant), b) always becomes Add(Add(a, b), constant). This is profitable because in
     11        typical code, it reveals downstream optimizations. But it's terrible in the case of caging, because
     12        we want the large constant (which is shared by all caging operations) to be hoisted. Reassociating to
     13        sink constants obscures the constant in this case. Currently, moveConstants is not smart enough to
     14        reassociate, so instead of sinking largeConstant, it tries (and often fails) to sink some other
     15        constants instead. Without some hacks, this is a 5% Kraken regression and a 1.6% Octane regression.
     16        It's not clear that moveConstants could ever be smart enough to rematerialize that constant and then
     17        hoist it - that would require quite a bit of algebraic reasoning. But the only case we know of where
     18        our current constant reassociation heuristics are wrong is caging. So, we can get away with some
     19        hacks for just stopping B3's reassociation only in this specific case.
     20       
     21        Previously, we achieved this by concealing the Add(ptr, largeConstant) inside a patchpoint. That's
     22        OK, but patchpoints are expensive. They require a SharedTask instance. They require callbacks from
     23        the backend, including during register allocation. And they cannot be CSE'd. We do want B3 to know
     24        that if we cage the same pointer in two places, both places will compute the same value.
     25       
     26        This patch improves the situation by introducing the Opaque opcode. This is handled by LowerToAir as
     27        if it was Identity, but all prior phases treat it as an unknown pure unary idempotent operation. I.e.
     28        they know that Opaque(x) == Opaque(x) and that Opaque(Opaque(x)) == Opaque(x). But they don't know
     29        that Opaque(x) == x until LowerToAir. So, you can use Opaque exactly when you know that B3 will mess
     30        up your code but Air won't. (Currently we know of no cases where Air messes things up on a large
     31        enough scale to warrant new opcodes.)
     32       
     33        This change is perf-neutral, but may start to help as I add more uses of caged() in the FTL. It also
     34        makes the code a bit less ugly.
     35
     36        * b3/B3LowerToAir.cpp:
     37        (JSC::B3::Air::LowerToAir::shouldCopyPropagate):
     38        (JSC::B3::Air::LowerToAir::lower):
     39        * b3/B3Opcode.cpp:
     40        (WTF::printInternal):
     41        * b3/B3Opcode.h:
     42        * b3/B3ReduceStrength.cpp:
     43        * b3/B3Validate.cpp:
     44        * b3/B3Value.cpp:
     45        (JSC::B3::Value::effects const):
     46        (JSC::B3::Value::key const):
     47        (JSC::B3::Value::isFree const):
     48        (JSC::B3::Value::typeFor):
     49        * b3/B3Value.h:
     50        * b3/B3ValueKey.cpp:
     51        (JSC::B3::ValueKey::materialize const):
     52        * ftl/FTLLowerDFGToB3.cpp:
     53        (JSC::FTL::DFG::LowerDFGToB3::caged):
     54        * ftl/FTLOutput.cpp:
     55        (JSC::FTL::Output::opaque):
     56        * ftl/FTLOutput.h:
     57
    1582017-08-11  Filip Pizlo  <fpizlo@apple.com>
    259

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

    r220579 r220625  
    190190        case Trunc:
    191191        case Identity:
     192        case Opaque:
    192193            return true;
    193194        default:
    … …  
    33373338        }
    33383339           
    3339         case Identity: {
     3340        case Identity:
     3341        case Opaque: {
    33403342            ASSERT(tmp(m_value->child(0)) == tmp(m_value));
    33413343            return;

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

    r214942 r220625  
    107107        out.print("Identity");
    108108        return;
     109    case Opaque:
     110        out.print("Opaque");
     111        return;
    109112    case Const32:
    110113        out.print("Const32");

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

    r214592 r220625  
    4444    // Polymorphic identity, usable with any value type.
    4545    Identity,
     46       
     47    // This is an identity, but we prohibit the compiler from realizing this until the bitter end. This can
     48    // be used to block reassociation and other compiler reasoning, if we find that it's wrong or
     49    // unprofitable and we need an escape hatch.
     50    Opaque,
    4651
    4752    // Constants. Use the ConstValue* classes. Constants exist in the control flow, so that we can
    … …  
    259264    // because it unlocks reordering of users of @result and @phantom.
    260265    //
    261     // On X86, this is lowered to a load-load fence and @result uses @phantom directly.
     266    // On X86, this is lowered to a load-load fence and @result folds to zero.
    262267    //
    263268    // On ARM, this is lowered as if like:

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

    r219702 r220625  
    486486    {
    487487        switch (m_value->opcode()) {
     488        case Opaque:
     489            // Turn this: Opaque(Opaque(value))
     490            // Into this: Opaque(value)
     491            if (m_value->child(0)->opcode() == Opaque) {
     492                replaceWithIdentity(m_value->child(0));
     493                break;
     494            }
     495            break;
     496           
    488497        case Add:
    489498            handleCommutativity();

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

    r215533 r220625  
    140140                break;
    141141            case Identity:
     142            case Opaque:
    142143                VALIDATE(!value->kind().hasExtraBits(), ("At ", *value));
    143144                VALIDATE(value->numChildren() == 1, ("At ", *value));

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

    r215533 r220625  
    547547    case Nop:
    548548    case Identity:
     549    case Opaque:
    549550    case Const32:
    550551    case Const64:
    … …  
    701702ValueKey Value::key() const
    702703{
     704    // NOTE: Except for exotic things like CheckAdd and friends, we want every case here to have a
     705    // corresponding case in ValueKey::materialize().
    703706    switch (opcode()) {
    704707    case FramePointer:
    705708        return ValueKey(kind(), type());
    706709    case Identity:
     710    case Opaque:
    707711    case Abs:
    708712    case Ceil:
    … …  
    795799    case ConstFloat:
    796800    case Identity:
     801    case Opaque:
    797802    case Nop:
    798803        return true;
    … …  
    810815    switch (kind.opcode()) {
    811816    case Identity:
     817    case Opaque:
    812818    case Add:
    813819    case Sub:

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

    r215407 r220625  
    329329            break;
    330330        case Identity:
     331        case Opaque:
    331332        case Neg:
    332333        case Clz:

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

    r208848 r220625  
    11/*
    2  * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
     2 * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    5757Value* ValueKey::materialize(Procedure& proc, Origin origin) const
    5858{
     59    // NOTE: We sometimes cannot return a Value* for some key, like for Check and friends. That's because
     60    // though those nodes have side exit effects. It would be weird to materialize anything that has a side
     61    // exit. We can't possibly know enough about a side exit to know where it would be safe to emit one.
    5962    switch (opcode()) {
    6063    case FramePointer:
    6164        return proc.add<Value>(kind(), type(), origin);
    6265    case Identity:
     66    case Opaque:
     67    case Abs:
     68    case Floor:
     69    case Ceil:
    6370    case Sqrt:
     71    case Neg:
     72    case Depend:
    6473    case SExt8:
    6574    case SExt16:
    … …  
    7281    case FloatToDouble:
    7382    case DoubleToFloat:
    74     case Check:
    7583        return proc.add<Value>(kind(), type(), origin, child(proc, 0));
    7684    case Add:
    … …  
    97105    case AboveEqual:
    98106    case BelowEqual:
     107    case EqualOrUnordered:
    99108        return proc.add<Value>(kind(), type(), origin, child(proc, 0), child(proc, 1));
    100109    case Select:

  • trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp

    r220624 r220625  
    1162711627        LValue mask = m_out.constIntPtr(GIGACAGE_MASK);
    1162811628       
    11629         // We don't have to worry about B3 messing up the bitAnd. Also, we want to get B3's excellent
    11630         // codegen for 2-operand andq on x86-64.
    1163111629        LValue masked = m_out.bitAnd(ptr, mask);
    11632        
    11633         // But B3 will currently mess up the code generation of this add. Basically, any offset from what we
    11634         // compute here will get reassociated and folded with Gigacage::basePtr. There's a world in which
    11635         // moveConstants() observes that it needs to reassociate in order to hoist the big constants. But
    11636         // it's much easier to just block B3's badness here. That's what we do for now.
    11637         // FIXME: It would be better if we didn't have to do this hack.
    11638         // https://bugs.webkit.org/show_bug.cgi?id=175483
    11639         PatchpointValue* patchpoint = m_out.patchpoint(pointerType());
    11640         patchpoint->appendSomeRegister(basePtr);
    11641         patchpoint->appendSomeRegister(masked);
    11642         patchpoint->setGenerator(
    11643             [] (CCallHelpers& jit, const StackmapGenerationParams& params) {
    11644                 jit.addPtr(params[1].gpr(), params[2].gpr(), params[0].gpr());
    11645             });
    11646         patchpoint->effects = Effects::none();
    11647         return patchpoint;
     11630        LValue result = m_out.add(masked, basePtr);
     11631
     11632        // Make sure that B3 doesn't try to do smart reassociation of these pointer bits.
     11633        // FIXME: In an ideal world, B3 would not do harmful reassociations, and if it did, it would be able
     11634        // to undo them during constant hoisting and regalloc. As it stands, if you remove this then Octane
     11635        // gets 1.6% slower and Kraken gets 5% slower. It's all because the basePtr, which is a constant,
     11636        // gets reassociated out of the add above and into the address arithmetic. This disables hoisting of
     11637        // the basePtr constant. Hoisting that constant is worth a lot more perf than the reassociation. One
     11638        // way to make this all work happily is to combine offset legalization with constant hoisting, and
     11639        // then teach it reassociation. So, Add(Add(a, b), const) where a is loop-invariant while b isn't
     11640        // will turn into Add(Add(a, const), b) by the constant hoister. We would have to teach B3 to do this
     11641        // and possibly other smart things if we want to be able to remove this opaque.
     11642        // https://bugs.webkit.org/show_bug.cgi?id=175493
     11643        return m_out.opaque(result);
    1164811644    }
    1164911645   

  • trunk/Source/JavaScriptCore/ftl/FTLOutput.cpp

    r216178 r220625  
    128128}
    129129
     130LValue Output::opaque(LValue value)
     131{
     132    return m_block->appendNew<Value>(m_proc, Opaque, origin(), value);
     133}
     134
    130135LValue Output::add(LValue left, LValue right)
    131136{

  • trunk/Source/JavaScriptCore/ftl/FTLOutput.h

    r216178 r220625  
    152152    template<typename... Params>
    153153    void addIncomingToPhi(LValue phi, ValueFromBlock, Params... theRest);
     154   
     155    LValue opaque(LValue);
    154156
    155157    LValue add(LValue, LValue);

  • trunk/Websites/webkit.org/ChangeLog

    r220360 r220625  
     12017-08-11  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Caging shouldn't have to use a patchpoint for adding
     4        https://bugs.webkit.org/show_bug.cgi?id=175483
     5
     6        Reviewed by Mark Lam.
     7       
     8        Write documentation for the new Opaque opcode.
     9
     10        * docs/b3/intermediate-representation.html:
     11
    1122017-08-07  Jon Davis  <jond@apple.com>
    213

  • trunk/Websites/webkit.org/docs/b3/intermediate-representation.html

    r217722 r220625  
    216216        to an Identity by doing convertToIdentity(otherValue).  If the value is Void,
    217217        convertToIdentity() converts it to a Nop instead.</dd>
     218
     219      <dt>T Opaque(T)</dt>
     220      <dd>Returns the passed value.  May be used for any type except Void.  This opcode is provided as a hack
     221        for avoiding B3 optimizations that the client finds unprofitable.  B3 treats Opaque as an identity
     222        only during instruction selection.  All prior optimizations (including all B3 IR optimizations) do
     223        not know what Opaque does, other than Opaque(x) == Opaque(x) and Opaque(Opaque(x)) == Opaque(x).</dd>
    218224
    219225      <dt>Int32 Const32(constant)</dt>
Note: See TracChangeset for help on using the changeset viewer.