Attachment 271719 Details for Bug 154405 – oh man

[patch] oh man

blah.patch (text/plain), 17.00 KB, created by Filip Pizlo on 2016-02-18 17:54:28 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2016-02-18 17:54:28 PST

Size: 17.00 KB

patch

obsolete

>Index: Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp	(revision 196765)
>+++ Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp	(working copy)
>@@ -751,9 +751,20 @@ public:
>     // This tells you if a Move will be coalescable if the src and dst end up matching. This method
>     // relies on an analysis that is invalidated by register allocation, so you it's only meaningful to
>     // call this *before* replacing the Tmp's in this Inst with registers or spill slots.
>-    bool mayBeCoalescable(const Inst& inst) const
>+    bool mayBeCoalescableMove(const Inst& inst) const
>     {
>-        return mayBeCoalescableImpl(inst, &m_tmpWidth);
>+        return mayBeCoalescableMoveImpl(inst, &m_tmpWidth);
>+    }
>+
>+    bool mayBeCoalescableShufflePair(const Inst& inst, unsigned index) const
>+    {
>+        return mayBeCoalescable(
>+            inst.args[index + 2].width(), inst.args[index + 0], inst.args[index + 1]);
>+    }
>+
>+    bool mayBeCoalescable(Arg::Width width, const Arg& src, const Arg& dest)
>+    {
>+        return mayBeCoalescableImpl(width, src, dest, &m_tmpWidth);
>     }
> 
>     bool isUselessMove(const Inst& inst) const
>@@ -761,6 +772,17 @@ public:
>         return mayBeCoalescableImpl(inst, nullptr) && inst.args[0].tmp() == inst.args[1].tmp();
>     }
> 
>+    bool isUselessShufflePair(const Inst& inst, unsigned index) const
>+    {
>+        return isUselessMove(
>+            inst.args[index + 2].width(), inst.args[index + 0], inst.args[index + 1]);
>+    }
>+
>+    bool isUselessMove(Arg::Width width, const Arg& src, const Arg& dest)
>+    {
>+        return mayBeCoalescableImpl(width, src, dest, nullptr) && src.tmp() == dest.tmp();
>+    }
>+
>     Tmp getAliasWhenSpilling(Tmp tmp) const
>     {
>         ASSERT_WITH_MESSAGE(!m_spilledTmps.isEmpty(), "This function is only valid for coalescing during spilling.");
>@@ -941,47 +963,78 @@ private:
>                     });
>             });
> 
>-        if (prevInst && mayBeCoalescable(*prevInst)) {
>-            // We do not want the Use() of this move to interfere with the Def(), even if it is live
>-            // after the Move. If we were to add the interference edge, it would be impossible to
>-            // coalesce the Move even if the two Tmp never interfere anywhere.
>-            Tmp defTmp;
>-            Tmp useTmp;
>-            prevInst->forEachTmp([&defTmp, &useTmp] (Tmp& argTmp, Arg::Role role, Arg::Type, Arg::Width) {
>-                if (Arg::isLateDef(role))
>-                    defTmp = argTmp;
>-                else {
>-                    ASSERT(Arg::isEarlyUse(role));
>-                    useTmp = argTmp;
>-                }
>-            });
>-            ASSERT(defTmp);
>-            ASSERT(useTmp);
>+        if (prevInst) {
>+            // This code path attempts to handle coalescable instructions. It handles both Moves and
>+            // Shuffles. The trick is to ensure that the definitions in a Move don't interfere with
>+            // the sources, so if we detect a coalescing opportunity we also avoid taking the usual
>+            // interference path by doing the interference calculation manually and returning early.
>+            
>+            auto addCoalescableMove = [&] (Tmp srcTmp, Tmp destTmp) {
>+                unsigned srcIndex = AbsoluteTmpMapper<type>::absoluteIndex(srcTmp);
>+                unsigned destIndex = AbsoluteTmpMapper<type>::absoluteIndex(destTmp);
>+                
>+                unsigned nextMoveIndex = m_coalescingCandidates.size();
>+                m_coalescingCandidates.append({ srcIndex, destIndex });
>+                
>+                unsigned newIndexInWorklist = m_worklistMoves.addMove();
>+                ASSERT_UNUSED(newIndexInWorklist, newIndexInWorklist == nextMoveIndex);
>+                
>+                ASSERT(nextMoveIndex <= m_activeMoves.size());
>+                m_activeMoves.ensureSize(nextMoveIndex + 1);
> 
>-            unsigned nextMoveIndex = m_coalescingCandidates.size();
>-            m_coalescingCandidates.append({ AbsoluteTmpMapper<type>::absoluteIndex(useTmp), AbsoluteTmpMapper<type>::absoluteIndex(defTmp) });
>+                m_moveList[srcIndex].add(nextMoveIndex);
>+                m_moveList[destIndex].add(nextMoveIndex);
>+            };
>+            
>+            if (mayBeCoalescableMove(*prevInst)) {
>+                Tmp srcTmp = prevInst->args[0].tmp();
>+                Tmp destTmp = prevInst->args[1].tmp();
>+                addCoalescableMove(srcTmp, destTmp);
>+
>+                for (Tmp liveTmp : localCalc.live()) {
>+                    if (liveTmp != srcTmp)
>+                        addEdge(destTmp, liveTmp);
>+                }
> 
>-            unsigned newIndexInWorklist = m_worklistMoves.addMove();
>-            ASSERT_UNUSED(newIndexInWorklist, newIndexInWorklist == nextMoveIndex);
>+                // The next instruction could have early clobbers or early def's. Consider those
>+                // now.
>+                addEdges(nullptr, nextInst, localCalc.live());
>+                return;
>+            }
> 
>-            ASSERT(nextMoveIndex <= m_activeMoves.size());
>-            m_activeMoves.ensureSize(nextMoveIndex + 1);
>+            if (prevInst->opcode == Shuffle) {
>+                for (unsigned i = 0; i < prevInst->args.size(); i += 3) {
>+                    Arg dest = prevInst->args[i + 1];
>+                    
>+                    if (mayBeCoalescableShufflePair(*prevInst, i)) {
>+                        Tmp srcTmp = prevInst->args[i + 0].tmp();
>+                        Tmp destTmp = dest.tmp();
>+                        addCoalescableMove(srcTmp, destTemp);
>+
>+                        // Conservatively, dest would interfere with everything live. But in this
>+                        // case it only interferes with all live variables except srcTmp.
>+                        for (Tmp liveTmp : localCalc.live()) {
>+                            if (liveTmp != srcTmp)
>+                                addEdge(destTmp, liveTmp);
>+                        }
>+                        continue;
>+                    }
> 
>-            for (const Arg& arg : prevInst->args) {
>-                auto& list = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(arg.tmp())];
>-                list.add(nextMoveIndex);
>-            }
>+                    // If the destination is a tmp, it needs to interfere with everything live.
>+                    if (dest.isTmp()) {
>+                        for (Tmp liveTmp : localCalc.live())
>+                            addEdge(dest.tmp(), liveTmp);
>+                    }
>+                }
> 
>-            for (const Tmp& liveTmp : localCalc.live()) {
>-                if (liveTmp != useTmp)
>-                    addEdge(defTmp, liveTmp);
>+                // The next instruction could have early clobbers or early def's. Consider those
>+                // now.
>+                addEdges(nullptr, nextInst, localCalc.live());
>+                return;
>             }
>+        }
> 
>-            // The next instruction could have early clobbers or early def's. We need to consider
>-            // those now.
>-            addEdges(nullptr, nextInst, localCalc.live());
>-        } else
>-            addEdges(prevInst, nextInst, localCalc.live());
>+        addEdges(prevInst, nextInst, localCalc.live());
>     }
> 
>     void buildLowPriorityMoveList()
>@@ -1037,13 +1090,18 @@ private:
> 
>     // Calling this without a tmpWidth will perform a more conservative coalescing analysis that assumes
>     // that Move32's are not coalescable.
>-    static bool mayBeCoalescableImpl(const Inst& inst, TmpWidth* tmpWidth)
>+    static bool mayBeCoalescableMoveImpl(const Inst& inst, TmpWidth* tmpWidth)
>     {
>+        Arg::Width width;
>+        
>         switch (type) {
>         case Arg::GP:
>             switch (inst.opcode) {
>             case Move:
>+                width = Arg::conservativeWidth(type);
>+                break;
>             case Move32:
>+                width = Arg::Width32;
>                 break;
>             default:
>                 return false;
>@@ -1052,7 +1110,10 @@ private:
>         case Arg::FP:
>             switch (inst.opcode) {
>             case MoveFloat:
>+                width = Arg::Width32;
>+                break;
>             case MoveDouble:
>+                width = Arg::Width64;
>                 break;
>             default:
>                 return false;
>@@ -1062,29 +1123,32 @@ private:
> 
>         ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
> 
>-        if (!inst.args[0].isTmp() || !inst.args[1].isTmp())
>+        return mayBeCoalescableImpl(width, inst.args[0], inst.args[1], tmpWidth);
>+    }
>+
>+    static bool mayBeCoalescableImpl(
>+        Arg::Width width, const Arg& src, const Arg& dest, TmpWidth* tmpWidth)
>+    {
>+        if (!src.isTmp() || !dest.isTmp())
>             return false;
> 
>-        ASSERT(inst.args[0].type() == type);
>-        ASSERT(inst.args[1].type() == type);
>+        if (!src.isType(type))
>+            return false;
> 
>-        // We can coalesce a Move32 so long as either of the following holds:
>-        // - The input is already zero-filled.
>-        // - The output only cares about the low 32 bits.
>-        //
>-        // Note that the input property requires an analysis over ZDef's, so it's only valid so long
>-        // as the input gets a register. We don't know if the input gets a register, but we do know
>-        // that if it doesn't get a register then we will still emit this Move32.
>-        if (inst.opcode == Move32) {
>-            if (!tmpWidth)
>-                return false;
>+        ASSERT(width == Width32 || width == Width64);
>+        ASSERT(src.type() == dest.type());
> 
>-            if (tmpWidth->defWidth(inst.args[0].tmp()) > Arg::Width32
>-                && tmpWidth->useWidth(inst.args[1].tmp()) > Arg::Width32)
>-                return false;
>-        }
>-        
>-        return true;
>+        if (type == Arg::FP)
>+            return true;
>+
>+        if (width == Arg::conservativeWidth(type))
>+            return true;
>+
>+        if (!tmpWidth)
>+            return false;
>+
>+        return tmpWidth->defWidth(src) <= Arg::Width32
>+            || tmpWidth->useWidth(dest) <= Arg::Width32;
>     }
> 
>     void selectSpill()
>@@ -1375,9 +1439,9 @@ private:
>             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
>                 Inst& inst = block->at(instIndex);
> 
>-                // The mayBeCoalescable() method will change its mind for some operations after we
>-                // complete register allocation. So, we record this before starting.
>-                bool mayBeCoalescable = allocator.mayBeCoalescable(inst);
>+                // The mayBeCoalescableMove() method will change its mind for some operations after
>+                // we complete register allocation. So, we record this before starting.
>+                bool mayBeCoalescableMove = allocator.mayBeCoalescableMove(inst);
> 
>                 // Move32 is cheaper if we know that it's equivalent to a Move. It's
>                 // equivalent if the destination's high bits are not observable or if the source's high
>@@ -1390,6 +1454,25 @@ private:
>                         inst.opcode = Move32;
>                 }
> 
>+                // All of the stuff we do for Moves also applies to Shuffles.
>+                BitVector coalescableShufflePairs;
>+                if (inst.opcode == Shuffle) {
>+                    for (unsigned i = 0; i < inst.args.size(); i += 3) {
>+                        Arg src = inst.args[i + 0];
>+                        Arg dest = inst.args[i + 1];
>+                        Arg::Width width = inst.args[i + 2].width();
>+                        
>+                        if (allocator.mayBeCoalescableShufflePair(inst, i))
>+                            coalescableShufflePairs.set(i);
>+                        
>+                        if (type == Arg::GP && src.isTmp() && dest.isTmp() && src.isGP()
>+                            && width == Width64
>+                            && (m_tmpWidth.useWidth(dest) <= Arg::Width32
>+                                || m_tmpWidth.defWidth(src) <= Arg::Width32))
>+                            inst.args[i + 2] = Arg::widthArg(Arg::Width32);
>+                    }
>+                }
>+
>                 inst.forEachTmpFast([&] (Tmp& tmp) {
>                     if (tmp.isReg() || tmp.isGP() == (type != Arg::GP))
>                         return;
>@@ -1410,11 +1493,29 @@ private:
>                 if (mayBeCoalescable && inst.args[0].isTmp() && inst.args[1].isTmp()
>                     && inst.args[0].tmp() == inst.args[1].tmp())
>                     inst = Inst();
>-            }
> 
>+                if (inst.opcode == Shuffle) {
>+                    Inst::ArgList newArgs;
>+                    for (unsigned i = 0; i < inst.args.size(); i += 3) {
>+                        Arg src = inst.args[i + 0];
>+                        Arg dest = inst.args[i + 1];
>+                        Arg::Width width = inst.args[i + 2];
>+                        if (coalescableShufflePairs.get(i)
>+                            && src.isTmp() && dest.isTmp() && src.tmp() == dest.tmp())
>+                            continue;
>+
>+                        newArgs.append(src);
>+                        newArgs.append(dest);
>+                        newArgs.append(Arg::widthArg(width));
>+                    }
>+                    
>+                    inst.args = WTFMove(newArgs);
>+                }
>+            }
>+            
>             // Remove all the useless moves we created in this block.
>             block->insts().removeAllMatching([&] (const Inst& inst) {
>-                return !inst;
>+                return !inst || (inst.opcode == Shuffle && inst.args.isEmpty());
>             });
>         }
>     }
>@@ -1442,6 +1543,62 @@ private:
>             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
>                 Inst& inst = block->at(instIndex);
> 
>+                // The Shuffle instruction requires some special care. The TmpWidth analysis will
>+                // say that a shuffle pair only stores 32-bits into the destination if the source
>+                // only had 32 bits worth of non-zero bits. Same for the source: it will only claim
>+                // to read 32 bits from the source if only 32 bits of the destination are read. This
>+                // happens on a per-pair basis. We also happen to know that Shuffle admits stack
>+                // everywhere, which makes spilling easier.
>+                //
>+                // Note that it's OK for this to fall through for not GP, since we handle Shuffle
>+                // just fine if we don't have to handle the width special cases.
>+                if (inst.opcode == Shuffle && type) {
>+                    for (unsigned i = 0; i < inst.args.size(); i += 3) {
>+                        Arg src = inst.args[i + 0];
>+                        Arg dest = inst.args[i + 1];
>+                        Arg::Width width = inst.args[i + 2].width();
>+
>+                        // This excludes everything except mem->mem pairs, which we gracefully
>+                        // ignore down below.
>+                        if (!src.isType(type) || !dest.isType(type))
>+                            return;
>+
>+                        bool forceWidth32IfDidSpill = false;
>+                        bool didSpill = false;
>+
>+                        if (type == GP && width == Arg::Width64) {
>+                            if ((src.isTmp() && m_tmpWidth.useWidth(dest.tmp()) <= Arg::Width32)
>+                                || (dest.isTmp() && m_tmpWidth.defWidth(src.tmp()) <= Arg::Width32))
>+                                forceWidth32IfDidSpill = true;
>+                        }
>+
>+                        auto handleTmp = [&] (Arg& arg) {
>+                            if (!arg.isTmp())
>+                                return;
>+                            if (arg.isReg())
>+                                return;
>+                            auto stackSlotEntry = stackSlots.find(arg.tmp());
>+                            if (stackSlotEntry == stackSlots.end())
>+                                return;
>+                            stackSlotEntry->value->ensureSize(
>+                                forceWidth32IfDidSpill ? 4 : Arg::bytes(width));
>+                            arg = Arg::stack(stackSlotEntry->value);
>+                            didSpill = true;
>+                        };
>+                        
>+                        handleTmp(src);
>+                        handleTmp(dest);
>+
>+                        if (didSpill && forceWidth32IfDidSpill)
>+                            width = Arg::Width32;
>+
>+                        inst.args[i + 0] = src;
>+                        inst.args[i + 1] = dest;
>+                        inst.args[i + 2] = Arg::widthArg(width);
>+                    }
>+                    continue;
>+                }
>+                
>                 // The TmpWidth analysis will say that a Move only stores 32 bits into the destination,
>                 // if the source only had 32 bits worth of non-zero bits. Same for the source: it will
>                 // only claim to read 32 bits from the source if only 32 bits of the destination are

Actions: View | Formatted Diff | Diff

Attachments on bug 154405: 271683 | 271710 | 271719 | 272036 | 272628