Changeset 214187 in webkit

Timestamp:

Mar 20, 2017 11:58:59 AM (7 years ago)

Author:

fpizlo@apple.com

Message:

Graph coloring should use coalescable moves when spilling
​https://bugs.webkit.org/show_bug.cgi?id=169820

Reviewed by Michael Saboff.

This makes our graph coloring register allocator use a new family of move instructions when
spilling both operands of the move. It's a three-operand move:

Move (src), (dst), %scratch

Previously, if both operands got spilled, we would emit a new instruction to load or store that
spill slot. But this made it hard for allocateStack to see that the two spill locations are
coalescable. This new kind of instruction makes it obvious that it's a coalescable move.

This change implements the coalescing of spill slots inside allocateStack.

This is an outrageous speed-up on the tsf_ir_speed benchmark from ​http://filpizlo.com/tsf/. This
is an interesting benchmark because it has a super ugly interpreter loop with ~20 live variables
carried around the loop back edge. This change makes that interpreter run 5x faster.

This isn't a speed-up on any other benchmarks. It also doesn't regress anything. Compile time is
neither progressed or regressed, since the coalescing is super cheap, and this does not add any
significant new machinery to the register allocator (it's just a small change to spill codegen).
Overall on our wasm benchmarks, this is a 16% throughput progression.

• assembler/MacroAssembler.h:

(JSC::MacroAssembler::move):
(JSC::MacroAssembler::move32):
(JSC::MacroAssembler::moveFloat):
(JSC::MacroAssembler::moveDouble):

• b3/air/AirAllocateRegistersByGraphColoring.cpp:

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

• b3/air/AirAllocateStack.cpp:

(JSC::B3::Air::allocateStack):

• b3/air/AirInst.cpp:

(JSC::B3::Air::Inst::hasEarlyDef):
(JSC::B3::Air::Inst::hasLateUseOrDef):
(JSC::B3::Air::Inst::needsPadding):

• b3/air/AirInst.h:
• b3/air/AirOpcode.opcodes:
• b3/air/AirPadInterference.cpp:

(JSC::B3::Air::padInterference):

• runtime/Options.h:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• assembler/MacroAssembler.h (modified) (3 diffs)
• b3/air/AirAllocateRegistersByGraphColoring.cpp (modified) (6 diffs)
• b3/air/AirAllocateStack.cpp (modified) (6 diffs)
• b3/air/AirInst.cpp (modified) (1 diff)
• b3/air/AirInst.h (modified) (1 diff)
• b3/air/AirOpcode.opcodes (modified) (4 diffs)
• b3/air/AirPadInterference.cpp (modified) (1 diff)
• runtime/Options.h (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2017-03-20  Filip Pizlo  <fpizlo@apple.com>
+
+        Graph coloring should use coalescable moves when spilling
+        https://bugs.webkit.org/show_bug.cgi?id=169820
+
+        Reviewed by Michael Saboff.
+        
+        This makes our graph coloring register allocator use a new family of move instructions when
+        spilling both operands of the move. It's a three-operand move:
+        
+            Move (src), (dst), %scratch
+        
+        Previously, if both operands got spilled, we would emit a new instruction to load or store that
+        spill slot. But this made it hard for allocateStack to see that the two spill locations are
+        coalescable. This new kind of instruction makes it obvious that it's a coalescable move.
+        
+        This change implements the coalescing of spill slots inside allocateStack.
+        
+        This is an outrageous speed-up on the tsf_ir_speed benchmark from http://filpizlo.com/tsf/. This
+        is an interesting benchmark because it has a super ugly interpreter loop with ~20 live variables
+        carried around the loop back edge. This change makes that interpreter run 5x faster.
+        
+        This isn't a speed-up on any other benchmarks. It also doesn't regress anything. Compile time is
+        neither progressed or regressed, since the coalescing is super cheap, and this does not add any
+        significant new machinery to the register allocator (it's just a small change to spill codegen).
+        Overall on our wasm benchmarks, this is a 16% throughput progression.
+        
+        * assembler/MacroAssembler.h:
+        (JSC::MacroAssembler::move):
+        (JSC::MacroAssembler::move32):
+        (JSC::MacroAssembler::moveFloat):
+        (JSC::MacroAssembler::moveDouble):
+        * b3/air/AirAllocateRegistersByGraphColoring.cpp:
+        (JSC::B3::Air::allocateRegistersByGraphColoring):
+        * b3/air/AirAllocateStack.cpp:
+        (JSC::B3::Air::allocateStack):
+        * b3/air/AirInst.cpp:
+        (JSC::B3::Air::Inst::hasEarlyDef):
+        (JSC::B3::Air::Inst::hasLateUseOrDef):
+        (JSC::B3::Air::Inst::needsPadding):
+        * b3/air/AirInst.h:
+        * b3/air/AirOpcode.opcodes:
+        * b3/air/AirPadInterference.cpp:
+        (JSC::B3::Air::padInterference):
+        * runtime/Options.h:
+
 2017-03-19  Chris Dumez  <cdumez@apple.com>
 

trunk/Source/JavaScriptCore/assembler/MacroAssembler.h

@@ -112 +112 @@
     using MacroAssemblerBase::compare32;
     using MacroAssemblerBase::move;
+    using MacroAssemblerBase::moveDouble;
     using MacroAssemblerBase::add32;
     using MacroAssemblerBase::mul32;
@@ -488 +489 @@
     }
 
+    void move(Address src, Address dest, RegisterID scratch)
+    {
+        loadPtr(src, scratch);
+        storePtr(scratch, dest);
+    }
+    
+    void move32(Address src, Address dest, RegisterID scratch)
+    {
+        load32(src, scratch);
+        store32(scratch, dest);
+    }
+    
+    void moveFloat(Address src, Address dest, FPRegisterID scratch)
+    {
+        loadFloat(src, scratch);
+        storeFloat(scratch, dest);
+    }
+    
+    void moveDouble(Address src, Address dest, FPRegisterID scratch)
+    {
+        loadDouble(src, scratch);
+        storeDouble(scratch, dest);
+    }
+
     // Ptr methods
     // On 32-bit platforms (i.e. x86), these methods directly map onto their 32-bit equivalents.
@@ -649 +674 @@
         move(Imm32(imm.asTrustedImmPtr()), dest);
     }
-
+    
     void comparePtr(RelationalCondition cond, RegisterID left, TrustedImm32 right, RegisterID dest)
     {

trunk/Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp

@@ -1751 +1751 @@
         }
 
-        ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
+        // Avoid the three-argument coalescable spill moves.
+        if (inst.args.size() != 2)
+            return false;
 
         if (!inst.args[0].isTmp() || !inst.args[1].isTmp())
@@ -2016 +2018 @@
                 bool canUseMove32IfDidSpill = false;
                 bool didSpill = false;
+                bool needScratch = false;
                 if (bank == GP && inst.kind.opcode == Move) {
                     if ((inst.args[0].isTmp() && m_tmpWidth.width(inst.args[0].tmp()) <= Width32)
@@ -2035 +2038 @@
                         if (stackSlotEntry == stackSlots.end())
                             return;
-                        if (!inst.admitsStack(arg))
-                            return;
+                        bool needScratchIfSpilledInPlace = false;
+                        if (!inst.admitsStack(arg)) {
+                            if (traceDebug)
+                                dataLog("Have an inst that won't admit stack: ", inst, "\n");
+                            switch (inst.kind.opcode) {
+                            case Move:
+                            case MoveDouble:
+                            case MoveFloat:
+                            case Move32: {
+                                unsigned argIndex = &arg - &inst.args[0];
+                                unsigned otherArgIndex = argIndex ^ 1;
+                                Arg otherArg = inst.args[otherArgIndex];
+                                if (inst.args.size() == 2
+                                    && otherArg.isStack()
+                                    && otherArg.stackSlot()->isSpill()) {
+                                    needScratchIfSpilledInPlace = true;
+                                    break;
+                                }
+                                return;
+                            }
+                            default:
+                                return;
+                            }
+                        }
                         
                         // If the Tmp holds a constant then we want to rematerialize its
@@ -2049 +2074 @@
                         
                         Width spillWidth = m_tmpWidth.requiredWidth(arg.tmp());
-                        if (Arg::isAnyDef(role) && width < spillWidth)
+                        if (Arg::isAnyDef(role) && width < spillWidth) {
+                            // Either there are users of this tmp who will use more than width,
+                            // or there are producers who will produce more than width non-zero
+                            // bits.
+                            // FIXME: It's not clear why we should have to return here. We have
+                            // a ZDef fixup in allocateStack. And if this isn't a ZDef, then it
+                            // doesn't seem like it matters what happens to the high bits. Note
+                            // that this isn't the case where we're storing more than what the
+                            // spill slot can hold - we already got that covered because we
+                            // stretch the spill slot on demand. One possibility is that it's ZDefs of
+                            // smaller width than 32-bit.
+                            // https://bugs.webkit.org/show_bug.cgi?id=169823
                             return;
+                        }
                         ASSERT(inst.kind.opcode == Move || !(Arg::isAnyUse(role) && width > spillWidth));
                         
@@ -2060 +2097 @@
                         arg = Arg::stack(stackSlotEntry->value);
                         didSpill = true;
+                        if (needScratchIfSpilledInPlace)
+                            needScratch = true;
                     });
 
                 if (didSpill && canUseMove32IfDidSpill)
                     inst.kind.opcode = Move32;
-
+                
+                if (needScratch) {
+                    Bank instBank;
+                    switch (inst.kind.opcode) {
+                    case Move:
+                    case Move32:
+                        instBank = GP;
+                        break;
+                    case MoveDouble:
+                    case MoveFloat:
+                        instBank = FP;
+                        break;
+                    default:
+                        RELEASE_ASSERT_NOT_REACHED();
+                        instBank = GP;
+                        break;
+                    }
+                    
+                    RELEASE_ASSERT(instBank == bank);
+                    
+                    Tmp tmp = m_code.newTmp(bank);
+                    unspillableTmps.add(AbsoluteTmpMapper<bank>::absoluteIndex(tmp));
+                    inst.args.append(tmp);
+                    RELEASE_ASSERT(inst.args.size() == 3);
+                    
+                    // Without this, a chain of spill moves would need two registers, not one, because
+                    // the scratch registers of successive moves would appear to interfere with each
+                    // other. As well, we need this if the previous instruction had any late effects,
+                    // since otherwise the scratch would appear to interfere with those. On the other
+                    // hand, the late use added at the end of this spill move (previously it was just a
+                    // late def) doesn't change the padding situation: the late def would have already
+                    // caused it to report hasLateUseOrDef in Inst::needsPadding.
+                    insertionSet.insert(instIndex, Nop, inst.origin);
+                    continue;
+                }
+                
                 // For every other case, add Load/Store as needed.
                 inst.forEachTmp([&] (Tmp& tmp, Arg::Role role, Bank argBank, Width) {
@@ -2185 +2259 @@
 {
     PhaseScope phaseScope(code, "Air::allocateRegistersByGraphColoring");
+    
+    if (false)
+        dataLog("Code before graph coloring:\n", code);
 
     UseCounts<Tmp> useCounts(code);

trunk/Source/JavaScriptCore/b3/air/AirAllocateStack.cpp

@@ -91 +91 @@
 }
 
+struct CoalescableMove {
+    CoalescableMove()
+    {
+    }
+
+    CoalescableMove(StackSlot* src, StackSlot* dst, double frequency)
+        : src(src)
+        , dst(dst)
+        , frequency(frequency)
+    {
+    }
+    
+    bool operator==(const CoalescableMove& other) const
+    {
+        return src == other.src
+            && dst == other.dst
+            && frequency == other.frequency;
+    }
+    
+    bool operator!=(const CoalescableMove& other) const
+    {
+        return !(*this == other);
+    }
+    
+    explicit operator bool() const
+    {
+        return *this != CoalescableMove();
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        out.print(pointerDump(src), "->", pointerDump(dst), "(", frequency, ")");
+    }
+    
+    StackSlot* src { nullptr };
+    StackSlot* dst { nullptr };
+    double frequency { PNaN };
+};
+
 } // anonymous namespace
 
@@ -126 +165 @@
     Vector<StackSlot*> slots;
 
+    // We will perform some spill coalescing. To make that effective, we need to be able to identify
+    // coalescable moves and handle them specially in interference analysis.
+    auto isCoalescableMove = [&] (Inst& inst) -> bool {
+        Width width;
+        switch (inst.kind.opcode) {
+        case Move:
+            width = pointerWidth();
+            break;
+        case Move32:
+        case MoveFloat:
+            width = Width32;
+            break;
+        case MoveDouble:
+            width = Width64;
+            break;
+        default:
+            return false;
+        }
+        
+        if (!Options::coalesceSpillSlots())
+            return false;
+        
+        if (inst.args.size() != 3)
+            return false;
+        
+        for (unsigned i = 0; i < 2; ++i) {
+            Arg arg = inst.args[i];
+            if (!arg.isStack())
+                return false;
+            StackSlot* slot = arg.stackSlot();
+            if (slot->kind() != StackSlotKind::Spill)
+                return false;
+            if (slot->byteSize() != bytes(width))
+                return false;
+        }
+        
+        return true;
+    };
+    
+    auto isUselessMove = [&] (Inst& inst) -> bool {
+        return isCoalescableMove(inst) && inst.args[0] == inst.args[1];
+    };
+    
+    auto addEdge = [&] (StackSlot* a, StackSlot* b) {
+        interference[a].add(b);
+        interference[b].add(a);
+    };
+    
+    Vector<CoalescableMove> coalescableMoves;
+
     for (BasicBlock* block : code) {
         StackSlotLiveness::LocalCalc localCalc(liveness, block);
@@ -133 +222 @@
                 dataLog("Interfering: ", WTF::pointerListDump(localCalc.live()), "\n");
 
+            Inst* prevInst = block->get(instIndex);
+            Inst* nextInst = block->get(instIndex + 1);
+            if (prevInst && isCoalescableMove(*prevInst)) {
+                CoalescableMove move(prevInst->args[0].stackSlot(), prevInst->args[1].stackSlot(), block->frequency());
+                
+                coalescableMoves.append(move);
+                
+                for (StackSlot* otherSlot : localCalc.live()) {
+                    if (otherSlot != move.src)
+                        addEdge(move.dst, otherSlot);
+                }
+                
+                prevInst = nullptr;
+            }
             Inst::forEachDef<Arg>(
-                block->get(instIndex), block->get(instIndex + 1),
+                prevInst, nextInst,
                 [&] (Arg& arg, Arg::Role, Bank, Width) {
                     if (!arg.isStack())
@@ -142 +245 @@
                         return;
 
-                    for (StackSlot* otherSlot : localCalc.live()) {
-                        interference[slot].add(otherSlot);
-                        interference[otherSlot].add(slot);
-                    }
+                    for (StackSlot* otherSlot : localCalc.live())
+                        addEdge(slot, otherSlot);
                 });
         };
@@ -201 +302 @@
             dataLog("Interference of ", pointerDump(slot), ": ", pointerListDump(interference[slot]), "\n");
     }
-
+    
+    // Now try to coalesce some moves.
+    std::sort(
+        coalescableMoves.begin(), coalescableMoves.end(),
+        [&] (CoalescableMove& a, CoalescableMove& b) -> bool {
+            return a.frequency > b.frequency;
+        });
+    
+    IndexMap<StackSlot, StackSlot*> remappedStackSlots(code.stackSlots().size());
+    auto remap = [&] (StackSlot* slot) -> StackSlot* {
+        if (!slot)
+            return nullptr;
+        for (;;) {
+            StackSlot* remappedSlot = remappedStackSlots[slot];
+            if (!remappedSlot)
+                return slot;
+            slot = remappedSlot;
+        }
+    };
+    
+    for (CoalescableMove& move : coalescableMoves) {
+        move.src = remap(move.src);
+        move.dst = remap(move.dst);
+        if (move.src == move.dst)
+            continue;
+        if (interference[move.src].contains(move.dst))
+            continue;
+        
+        StackSlot* slotToKill = move.src;
+        StackSlot* slotToKeep = move.dst;
+        
+        remappedStackSlots[slotToKill] = slotToKeep;
+        for (StackSlot* interferingSlot : interference[slotToKill]) {
+            if (interferingSlot == slotToKill)
+                continue;
+            interference[interferingSlot].remove(slotToKill);
+            interference[interferingSlot].add(slotToKeep);
+        }
+        interference[slotToKeep].add(interference[slotToKill].begin(), interference[slotToKill].end());
+        interference[slotToKill].clear();
+    }
+    
+    for (BasicBlock* block : code) {
+        for (Inst& inst : *block) {
+            for (Arg& arg : inst.args) {
+                if (arg.isStack())
+                    arg = Arg::stack(remap(arg.stackSlot()), arg.offset());
+            }
+            if (isUselessMove(inst))
+                inst = Inst();
+        }
+    }
+    
     // Now we assign stack locations. At its heart this algorithm is just first-fit. For each
     // StackSlot we just want to find the offsetFromFP that is closest to zero while ensuring no
@@ -207 +360 @@
     Vector<StackSlot*> otherSlots = assignedEscapedStackSlots;
     for (StackSlot* slot : code.stackSlots()) {
+        if (remappedStackSlots[slot])
+            continue;
+        
         if (slot->offsetFromFP()) {
             // Already assigned an offset.

trunk/Source/JavaScriptCore/b3/air/AirInst.cpp

@@ -34 +34 @@
 
 namespace JSC { namespace B3 { namespace Air {
+
+bool Inst::hasEarlyDef()
+{
+    if (kind.opcode == Patch && !extraEarlyClobberedRegs().isEmpty())
+        return true;
+    bool result = false;
+    forEachArg(
+        [&] (Arg&, Arg::Role role, Bank, Width) {
+            result |= Arg::isEarlyDef(role);
+        });
+    return result;
+}
+
+bool Inst::hasLateUseOrDef()
+{
+    if (kind.opcode == Patch && !extraClobberedRegs().isEmpty())
+        return true;
+    bool result = false;
+    forEachArg(
+        [&] (Arg&, Arg::Role role, Bank, Width) {
+            result |= Arg::isLateUse(role) || Arg::isLateDef(role);
+        });
+    return result;
+}
+
+bool Inst::needsPadding(Inst* prevInst, Inst* nextInst)
+{
+    return prevInst && nextInst && prevInst->hasLateUseOrDef() && nextInst->hasEarlyDef();
+}
 
 bool Inst::hasArgEffects()

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

@@ -144 +144 @@
     template<typename Thing, typename Functor>
     static void forEachDefWithExtraClobberedRegs(Inst* prevInst, Inst* nextInst, const Functor&);
-
+    
+    // Some summaries about all arguments. These are useful for needsPadding().
+    bool hasEarlyDef();
+    bool hasLateUseOrDef();
+    
+    // Check if there needs to be a padding Nop between these two instructions.
+    static bool needsPadding(Inst* prevInst, Inst* nextInst);
+    
     // Use this to report which registers are live. This should be done just before codegen. Note
     // that for efficiency, reportUsedRegisters() only works for the Patch opcode.

trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes

@@ -624 +624 @@
     x86: Imm, Addr as storePtr
 
+# This is for moving between spill slots.
+Move U:G:Ptr, D:G:Ptr, S:G:Ptr
+    Addr, Addr, Tmp
+
 x86: Swap32 UD:G:32, UD:G:32
     Tmp, Tmp
@@ -642 +646 @@
     x86: Imm, Index as store32
 
+# This is for moving between spill slots.
+Move32 U:G:32, ZD:G:32, S:G:32
+    Addr, Addr, Tmp
+
 StoreZero32 U:G:32
     Addr
@@ -676 +684 @@
     Tmp, Index as storeFloat
 
+MoveFloat U:F:32, D:F:32, S:F:32
+    Addr, Addr, Tmp
+
 MoveDouble U:F:64, D:F:64
     Tmp, Tmp
@@ -682 +693 @@
     Tmp, Addr as storeDouble
     Tmp, Index as storeDouble
+
+MoveDouble U:F:64, D:F:64, S:F:64
+    Addr, Addr, Tmp
 
 MoveZeroToDouble D:F:64

trunk/Source/JavaScriptCore/b3/air/AirPadInterference.cpp

@@ -39 +39 @@
     InsertionSet insertionSet(code);
     for (BasicBlock* block : code) {
-        bool prevHadLate = false;
-        for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+        for (unsigned instIndex = 1; instIndex < block->size(); ++instIndex) {
             Inst& inst = block->at(instIndex);
-            
-            bool hasEarlyDef = false;
-            bool hasLate = false;
-            inst.forEachArg(
-                [&] (Arg&, Arg::Role role, Bank, Width) {
-                    switch (role) {
-                    case Arg::EarlyDef:
-                    case Arg::EarlyZDef:
-                        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)
+            if (Inst::needsPadding(&block->at(instIndex - 1), &inst))
                 insertionSet.insert(instIndex, Nop, inst.origin);
-            
-            prevHadLate = hasLate;
         }
         insertionSet.execute(block);

trunk/Source/JavaScriptCore/runtime/Options.h

@@ -398 +398 @@
     v(bool, airForceBriggsAllocator, false, Normal, nullptr) \
     v(bool, airForceIRCAllocator, false, Normal, nullptr) \
+    v(bool, coalesceSpillSlots, true, Normal, nullptr) \
     v(bool, logAirRegisterPressure, false, Normal, nullptr) \
     v(unsigned, maxB3TailDupBlockSize, 3, Normal, nullptr) \