Changeset 263116 in webkit


Ignore:
Timestamp:
Jun 16, 2020 2:17:04 PM (4 years ago)
Author:
rmorisset@apple.com
Message:

Optimize Air::TmpWidth analysis in IRC
https://bugs.webkit.org/show_bug.cgi?id=152478

Reviewed by Filip Pizlo.

AirTmpWidth currently uses a HashMap to map tmps to their width.
Since tmps have consecutive indices, we can instead use vectors (one for GP and one for FP tmps).
As a bonus, we can just compute the width of the tmps of the bank the register allocator is currently looking at.
This cuts the time spent in the register allocator in JetStream2 by about 100ms out of 3.4s
(or sometimes 80ms out of 2.4, the bimodality of the time spent is due to a huge function in tagcloud-SP which usually but not always reach the FTL, I'll check later if it can be fixed by tweaking the inliner).

  • b3/air/AirAllocateRegistersByGraphColoring.cpp:

(JSC::B3::Air::allocateRegistersByGraphColoring):

  • b3/air/AirTmpWidth.cpp:

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

  • b3/air/AirTmpWidth.h:

(JSC::B3::Air::TmpWidth::width const):
(JSC::B3::Air::TmpWidth::requiredWidth):
(JSC::B3::Air::TmpWidth::defWidth const):
(JSC::B3::Air::TmpWidth::useWidth const):
(JSC::B3::Air::TmpWidth::Widths::Widths):
(JSC::B3::Air::TmpWidth::widths):
(JSC::B3::Air::TmpWidth::widths const):
(JSC::B3::Air::TmpWidth::addWidths):
(JSC::B3::Air::TmpWidth::widthsVector):

Location:
trunk/Source/JavaScriptCore
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r263108 r263116  
     12020-06-16  Robin Morisset  <rmorisset@apple.com>
     2
     3        Optimize Air::TmpWidth analysis in IRC
     4        https://bugs.webkit.org/show_bug.cgi?id=152478
     5
     6        Reviewed by Filip Pizlo.
     7
     8        AirTmpWidth currently uses a HashMap to map tmps to their width.
     9        Since tmps have consecutive indices, we can instead use vectors (one for GP and one for FP tmps).
     10        As a bonus, we can just compute the width of the tmps of the bank the register allocator is currently looking at.
     11        This cuts the time spent in the register allocator in JetStream2 by about 100ms out of 3.4s
     12        (or sometimes 80ms out of 2.4, the bimodality of the time spent is due to a huge function in tagcloud-SP which usually but not always reach the FTL, I'll check later if it can be fixed by tweaking the inliner).
     13
     14        * b3/air/AirAllocateRegistersByGraphColoring.cpp:
     15        (JSC::B3::Air::allocateRegistersByGraphColoring):
     16        * b3/air/AirTmpWidth.cpp:
     17        (JSC::B3::Air::TmpWidth::TmpWidth):
     18        (JSC::B3::Air::TmpWidth::recompute):
     19        * b3/air/AirTmpWidth.h:
     20        (JSC::B3::Air::TmpWidth::width const):
     21        (JSC::B3::Air::TmpWidth::requiredWidth):
     22        (JSC::B3::Air::TmpWidth::defWidth const):
     23        (JSC::B3::Air::TmpWidth::useWidth const):
     24        (JSC::B3::Air::TmpWidth::Widths::Widths):
     25        (JSC::B3::Air::TmpWidth::widths):
     26        (JSC::B3::Air::TmpWidth::widths const):
     27        (JSC::B3::Air::TmpWidth::addWidths):
     28        (JSC::B3::Air::TmpWidth::widthsVector):
     29
    1302020-06-16  Fujii Hironori  <Hironori.Fujii@sony.com>
    231
  • trunk/Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp

    r262040 r263116  
    18401840            // recomputation, in which case speeding up the lookup would be a bigger win.
    18411841            // https://bugs.webkit.org/show_bug.cgi?id=152478
    1842             m_tmpWidth.recompute(m_code);
     1842            m_tmpWidth.recompute<bank>(m_code);
    18431843
    18441844            auto doAllocation = [&] (auto& allocator) -> bool {
     
    22052205    PhaseScope phaseScope(code, "allocateRegistersByGraphColoring");
    22062206   
    2207     if (false)
     2207    if (traceDebug)
    22082208        dataLog("Code before graph coloring:\n", code);
    22092209
  • trunk/Source/JavaScriptCore/b3/air/AirTmpWidth.cpp

    r262040 r263116  
    4141TmpWidth::TmpWidth(Code& code)
    4242{
    43     recompute(code);
     43    recompute<GP>(code);
     44    recompute<FP>(code);
    4445}
    4546
     
    4849}
    4950
     51template <Bank bank>
    5052void TmpWidth::recompute(Code& code)
    5153{
    5254    // Set this to true to cause this analysis to always return pessimistic results.
    53     const bool beCareful = false;
    54 
     55    constexpr bool beCareful = false;
    5556    constexpr bool verbose = false;
    5657
    5758    if (verbose) {
    58         dataLog("Code before TmpWidth:\n");
     59        dataLogLn("Code before TmpWidth:");
    5960        dataLog(code);
    6061    }
    61    
    62     m_width.clear();
     62
     63    auto& bankWidthsVector = widthsVector(bank);
     64    bankWidthsVector.resize(AbsoluteTmpMapper<bank>::absoluteIndex(code.numTmps(bank)));
     65    for (unsigned i = 0; i < bankWidthsVector.size(); ++i)
     66        bankWidthsVector[i] = Widths(bank);
    6367   
    6468    auto assumeTheWorst = [&] (Tmp tmp) {
    65         Widths& widths = m_width.add(tmp, Widths()).iterator->value;
    66         Bank bank = Arg(tmp).bank();
    67         widths.use = conservativeWidth(bank);
    68         widths.def = conservativeWidth(bank);
     69        if (bank == Arg(tmp).bank()) {
     70            Width conservative = conservativeWidth(bank);
     71            addWidths(tmp, { conservative, conservative });
     72        }
    6973    };
    7074   
     
    9094        for (Inst& inst : *block) {
    9195            if (inst.kind.opcode == Move && inst.args[1].isTmp()) {
     96                if (Arg(inst.args[1]).bank() != bank)
     97                    continue;
     98
    9299                if (inst.args[0].isTmp()) {
    93                     // Make sure that both sides of the Move have a width already initialized. The
    94                     // fixpoint below assumes that it never has to add things to the HashMap.
    95                     m_width.add(inst.args[0].tmp(), Widths(GP));
    96                     m_width.add(inst.args[1].tmp(), Widths(GP));
    97                    
    98100                    moves.append(&inst);
    99101                    continue;
    100102                }
    101                 if (inst.args[0].isImm()
    102                     && inst.args[0].value() >= 0) {
     103                if (inst.args[0].isImm() && inst.args[0].value() >= 0) {
    103104                    Tmp tmp = inst.args[1].tmp();
    104                     Widths& widths = m_width.add(tmp, Widths(GP)).iterator->value;
    105                    
     105                    Widths& tmpWidths = widths(tmp);
     106                    Width maxWidth = Width64;
    106107                    if (inst.args[0].value() <= std::numeric_limits<int8_t>::max())
    107                         widths.def = std::max(widths.def, Width8);
     108                        maxWidth = Width8;
    108109                    else if (inst.args[0].value() <= std::numeric_limits<int16_t>::max())
    109                         widths.def = std::max(widths.def, Width16);
     110                        maxWidth = Width16;
    110111                    else if (inst.args[0].value() <= std::numeric_limits<int32_t>::max())
    111                         widths.def = std::max(widths.def, Width32);
    112                     else
    113                         widths.def = std::max(widths.def, Width64);
     112                        maxWidth = Width32;
     113
     114                    tmpWidths.def = std::max(tmpWidths.def, maxWidth);
    114115
    115116                    continue;
     
    117118            }
    118119            inst.forEachTmp(
    119                 [&] (Tmp& tmp, Arg::Role role, Bank bank, Width width) {
    120                     Widths& widths = m_width.add(tmp, Widths(bank)).iterator->value;
    121                    
     120                [&] (Tmp& tmp, Arg::Role role, Bank tmpBank, Width width) {
     121                    if (Arg(tmp).bank() != bank)
     122                        return;
     123
     124                    Widths& tmpWidths = widths(tmp);
    122125                    if (Arg::isAnyUse(role))
    123                         widths.use = std::max(widths.use, width);
     126                        tmpWidths.use = std::max(tmpWidths.use, width);
    124127
    125128                    if (Arg::isZDef(role))
    126                         widths.def = std::max(widths.def, width);
     129                        tmpWidths.def = std::max(tmpWidths.def, width);
    127130                    else if (Arg::isAnyDef(role))
    128                         widths.def = conservativeWidth(bank);
     131                        tmpWidths.def = conservativeWidth(tmpBank);
    129132                });
    130133        }
     
    140143            ASSERT(move->args[1].isTmp());
    141144
    142             // We already ensure that both tmps are added to the width map. That's important
    143             // because you cannot add both tmps here while simultaneously getting a reference to
    144             // their values, since the second add would invalidate the reference returned by the
    145             // first one.
    146             Widths& srcWidths = m_width.find(move->args[0].tmp())->value;
    147             Widths& dstWidths = m_width.find(move->args[1].tmp())->value;
     145            Widths& srcWidths = widths(move->args[0].tmp());
     146            Widths& dstWidths = widths(move->args[1].tmp());
    148147
    149148            // Legend:
     
    169168    }
    170169
    171     if (verbose)
    172         dataLog("width: ", mapDump(m_width), "\n");
     170    if (verbose) {
     171        dataLogLn("bank: ", bank, ", widthsVector: ");
     172        for (unsigned i = 0; i < bankWidthsVector.size(); ++i)
     173            dataLogLn("\t", i, " : ", bankWidthsVector[i]);
     174    }
    173175}
    174176
  • trunk/Source/JavaScriptCore/b3/air/AirTmpWidth.h

    r212970 r263116  
    4040    ~TmpWidth();
    4141
     42    template <Bank bank>
    4243    void recompute(Code&);
    4344
     
    5354    Width width(Tmp tmp) const
    5455    {
    55         auto iter = m_width.find(tmp);
    56         if (iter == m_width.end())
    57             return minimumWidth(Arg(tmp).bank());
    58         return std::min(iter->value.use, iter->value.def);
     56        Widths tmpWidths = widths(tmp);
     57        return std::min(tmpWidths.use, tmpWidths.def);
    5958    }
    6059
     
    6261    Width requiredWidth(Tmp tmp)
    6362    {
    64         auto iter = m_width.find(tmp);
    65         if (iter == m_width.end())
    66             return minimumWidth(Arg(tmp).bank());
    67         return std::max(iter->value.use, iter->value.def);
     63        Widths tmpWidths = widths(tmp);
     64        return std::max(tmpWidths.use, tmpWidths.def);
    6865    }
    6966
     
    7673    Width defWidth(Tmp tmp) const
    7774    {
    78         auto iter = m_width.find(tmp);
    79         if (iter == m_width.end())
    80             return minimumWidth(Arg(tmp).bank());
    81         return iter->value.def;
     75        return widths(tmp).def;
    8276    }
    8377
     
    8579    Width useWidth(Tmp tmp) const
    8680    {
    87         auto iter = m_width.find(tmp);
    88         if (iter == m_width.end())
    89             return minimumWidth(Arg(tmp).bank());
    90         return iter->value.use;
     81        return widths(tmp).use;
    9182    }
    9283   
     
    9687
    9788        Widths(Bank bank)
     89            : use(minimumWidth(bank))
     90            , def(minimumWidth(bank))
    9891        {
    99             use = minimumWidth(bank);
    100             def = minimumWidth(bank);
     92        }
     93
     94        Widths(Width useArg, Width defArg)
     95            : use(useArg)
     96            , def(defArg)
     97        {
    10198        }
    10299
     
    106103        Width def;
    107104    };
    108    
    109     HashMap<Tmp, Widths> m_width;
     105
     106    Widths& widths(Tmp tmp)
     107    {
     108        if (tmp.isGP()) {
     109            unsigned index = AbsoluteTmpMapper<GP>::absoluteIndex(tmp);
     110            ASSERT(index < m_widthGP.size());
     111            return m_widthGP[index];
     112        }
     113        unsigned index = AbsoluteTmpMapper<FP>::absoluteIndex(tmp);
     114        ASSERT(index < m_widthFP.size());
     115        return m_widthFP[index];
     116    }
     117    const Widths& widths(Tmp tmp) const
     118    {
     119        return const_cast<TmpWidth*>(this)->widths(tmp);
     120    }
     121
     122    void addWidths(Tmp tmp, Widths tmpWidths)
     123    {
     124        widths(tmp) = tmpWidths;
     125    }
     126
     127    Vector<Widths>& widthsVector(Bank bank)
     128    {
     129        return bank == GP ? m_widthGP : m_widthFP;
     130    }
     131
     132    // These are initialized at the beginning of recompute<bank>, which is called in the constructor for both values of bank.
     133    Vector<Widths> m_widthGP;
     134    Vector<Widths> m_widthFP;
    110135};
    111136
Note: See TracChangeset for help on using the changeset viewer.