Attachment 360667 Details for Bug 194036 – WIP

[patch] WIP

patch.diff (text/plain), 9.59 KB, created by Saam Barati on 2019-01-30 18:37:52 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Saam Barati

Created: 2019-01-30 18:37:52 PST

Size: 9.59 KB

patch

obsolete

>Index: Source/JavaScriptCore/b3/air/AirAllocateRegistersAndStackByLinearScan.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/air/AirAllocateRegistersAndStackByLinearScan.cpp	(revision 240697)
>+++ Source/JavaScriptCore/b3/air/AirAllocateRegistersAndStackByLinearScan.cpp	(working copy)
>@@ -61,6 +61,223 @@ NO_RETURN_DUE_TO_CRASH NEVER_INLINE void
>     } \
> } while (0)
> 
>+
>+class DumbRegAlloc {
>+    struct TmpData {
>+        StackSlot* spillSlot;
>+        Reg reg;
>+    };
>+
>+public:
>+    DumbRegAlloc(Code& code)
>+        : m_code(code)
>+        , m_map(code)
>+    {
>+        m_code.forEachTmp([&] (Tmp tmp) {
>+            RELEASE_ASSERT(!tmp.isReg());
>+            TmpData data;
>+            data.spillSlot = m_code.addStackSlot(8, StackSlotKind::Spill);
>+            data.reg = Reg();
>+            m_map[tmp] = data;
>+            m_allTmps[tmp.bank()].append(tmp);
>+        });
>+
>+        forEachBank([&] (Bank bank) {
>+            m_registers[bank] = m_code.regsInPriorityOrder(bank);
>+            for (Reg reg : m_registers[bank]) {
>+                TmpData data;
>+                data.spillSlot = m_code.addStackSlot(8, StackSlotKind::Spill);
>+                data.reg = Reg();
>+                m_map[Tmp(reg)] = data;
>+                m_allTmps[bank].append(Tmp(reg));
>+            }
>+        });
>+
>+        for (BasicBlock* block : m_code) {
>+
>+            forEachBank([&] (Bank bank) {
>+                m_availableRegs[bank] = RegisterSet();
>+            });
>+
>+            m_currentAllocation.clear();
>+
>+            forEachBank([&] (Bank bank) {
>+                for (Tmp tmp : m_allTmps[bank])
>+                    m_map[tmp].reg = Reg(); // Everything is spilled at block boundaries.
>+                for (Reg reg : m_registers[bank])
>+                    m_availableRegs[Tmp(reg).bank()].set(reg);
>+            });
>+
>+            if (block == m_code[0]) {
>+                forEachBank([&] (Bank bank) {
>+                    for (Reg reg : m_registers[bank]) {
>+                        m_map[Tmp(reg)].reg = reg;
>+                        m_availableRegs[bank].clear(reg);
>+                        m_currentAllocation.set(reg, Tmp(reg));
>+                    }
>+                });
>+            }
>+            
>+            InsertionSet insertionSet(code);
>+            for (size_t i = 0; i < block->size(); ++i) {
>+                Inst& inst = block->at(i);
>+
>+                auto flush = [&] (Tmp tmp) {
>+                    if (Reg reg = m_map[tmp].reg) {
>+                        Opcode move = tmp.bank() == GP ? Move : MoveDouble;
>+                        insertionSet.insert(i, move, inst.origin, reg, Arg::stack(m_map[tmp].spillSlot));
>+                    }
>+                };
>+
>+                auto spill = [&] (Tmp tmp) {
>+                    if (Reg reg = m_map[tmp].reg) {
>+                        m_availableRegs[tmp.bank()].set(reg);
>+                        m_currentAllocation.set(reg, Tmp());
>+                        flush(tmp);
>+                    } else {
>+                        ASSERT(!m_currentAllocation.get(reg));
>+                    }
>+
>+                    m_map[tmp].reg = Reg();
>+                };
>+
>+                // OOPS: This does dumb things for defs like loads a value right before we def!
>+                auto alloc = [&] (Tmp tmp, Reg reg) {
>+                    if (Tmp occupyingTmp = m_currentAllocation.get(reg))
>+                        spill(occupyingTmp);
>+
>+                    m_map[tmp].reg = reg;
>+                    m_availableRegs[tmp.bank()].clear(reg);
>+                    m_currentAllocation.set(reg, tmp);
>+
>+                    Opcode move = tmp.bank() == GP ? Move : MoveDouble;
>+                    insertionSet.insert(i, move, inst.origin, Arg::stack(m_map[tmp].spillSlot), reg);
>+                };
>+
>+                if (inst.isTerminal()) {
>+                    // OOPS: Only do this if we have successor blocks
>+                    // We spill everything between block boundaries.
>+                    Vector<Tmp, 30> toSpill;
>+                    for (Tmp tmp : m_currentAllocation.values())
>+                        flush(tmp);
>+                }
>+
>+                RegisterSet namedUsedRegs;
>+                RegisterSet namedDefdRegs;
>+
>+                Vector<Tmp*, 8> tmpsToAlloc[numBanks];
>+                inst.forEachTmp([&] (Tmp& tmp, Arg::Role role, Bank bank, Width) {
>+                    if (tmp.isReg()) {
>+                        if (Arg::isAnyUse(role))
>+                            namedUsedRegs.set(tmp.reg());
>+                        if (Arg::isAnyDef(role))
>+                            namedDefdRegs.set(tmp.reg());
>+                        return;
>+                    }
>+
>+                    tmpsToAlloc[bank].append(&tmp);
>+                });
>+
>+                for (Reg reg : namedUsedRegs) {
>+                    if (Tmp occupyingTmp = m_currentAllocation.get(reg)) {
>+                        // Something is in this register.
>+                        if (occupyingTmp == Tmp(reg))
>+                            continue;
>+                    }
>+
>+                    alloc(Tmp(reg), reg);
>+                }
>+
>+                forEachBank([&] (Bank bank) {
>+                    auto& toAlloc = tmpsToAlloc[bank];
>+                    Vector<Tmp*, 8> needToAlloc; // OOPS: Logically should be a HashSet of Tmps. For example, we may have two Tmp*, but their Tmps are equal.
>+                    for (Tmp* tmp : toAlloc) {
>+                        if (Reg reg = m_map[*tmp].reg) {
>+                            if (!namedDefdRegs.contains(reg)) {
>+                                *tmp = Tmp(reg);
>+                                namedUsedRegs.set(reg);
>+                                ASSERT(!m_availableRegs[bank].get(reg));
>+                                continue;
>+                            }
>+                            spill(*tmp);
>+                        }
>+                        needToAlloc.append(tmp);
>+                    }
>+
>+                    while (needToAlloc.size()) {
>+                        Tmp* tmp = needToAlloc.takeLast();
>+                        if (Reg reg = m_map[*tmp].reg) {
>+                            *tmp = Tmp(reg);
>+                            ASSERT(namedUsedRegs.get(reg));
>+                            ASSERT(!m_availableRegs[bank].get(reg));
>+                            continue;
>+                        }
>+                        bool alreadyAlloc = false;
>+                        if (m_availableRegs[bank].numberOfSetRegisters()) {
>+                            for (Reg reg : m_registers[bank]) {
>+                                // We first take any available registers.
>+                                if (namedUsedRegs.contains(reg) || namedDefdRegs.contains(reg))
>+                                    continue;
>+                                if (!m_availableRegs[bank].contains(reg))
>+                                    continue;
>+                                namedUsedRegs.set(reg);
>+                                alloc(*tmp, reg);
>+                                alreadyAlloc = true;
>+                                *tmp = Tmp(reg);
>+                                break;
>+                            }
>+                            RELEASE_ASSERT(alreadyAlloc);
>+
>+                            continue;
>+                        }
>+
>+                        // Nothing was available, let's make some room.
>+                        for (unsigned i = 0; i < m_registers[bank].size(); ++i) {
>+                            // OOPS: Super inefficient, but logically what we want.
>+                            Reg reg = m_registers[bank][i];
>+                            if (namedUsedRegs.contains(reg) || namedDefdRegs.contains(reg))
>+                                continue;
>+                            namedUsedRegs.set(reg);
>+                            alloc(*tmp, reg);
>+                            *tmp = Tmp(reg);
>+                            m_registers[bank].remove(i);
>+                            m_registers[bank].append(reg);
>+                            break;
>+                        }
>+                    }
>+                });
>+            }
>+
>+            insertionSet.execute(block);
>+        }
>+
>+        handleCalleeSaves(m_code);
>+        allocateEscapedStackSlots(m_code);
>+
>+        {
>+            unsigned index = 0;
>+            forEachBank([&] (Bank bank) {
>+                for (Tmp tmp : m_allTmps[bank]) {
>+                    ptrdiff_t offset = -static_cast<ptrdiff_t>(m_code.frameSize()) - static_cast<ptrdiff_t>(index) * 8 - 8;
>+                    m_map[tmp].spillSlot->setOffsetFromFP(offset);
>+                    ++index;
>+                }
>+            });
>+        }
>+
>+        updateFrameSizeBasedOnStackSlots(m_code);
>+        m_code.setStackIsAllocated(true);
>+    }
>+
>+private:
>+    Code& m_code;
>+    Vector<Tmp> m_allTmps[numBanks];
>+    TmpMap<TmpData> m_map;
>+    Vector<Reg> m_registers[numBanks];
>+    RegisterSet m_availableRegs[numBanks];
>+    HashMap<Reg, Tmp> m_currentAllocation; // OOPS: Use an indexed mapping if possible.
>+}; 
>+
> bool verbose() { return Options::airLinearScanVerbose(); }
> 
> // Phase constants we use for the PhaseInsertionSet.
>@@ -69,6 +286,7 @@ const unsigned secondPhase = 1;
> 
> typedef Range<size_t> Interval;
> 
>+
> struct TmpData {
>     void dump(PrintStream& out) const
>     {
>@@ -659,8 +877,9 @@ void allocateRegistersAndStackByLinearSc
>     PhaseScope phaseScope(code, "allocateRegistersAndStackByLinearScan");
>     if (verbose())
>         dataLog("Air before linear scan:\n", code);
>-    LinearScan linearScan(code);
>-    linearScan.run();
>+    DumbRegAlloc regAlloc(code);
>+    //LinearScan linearScan(code);
>+    //linearScan.run();
>     if (verbose())
>         dataLog("Air after linear scan:\n", code);
> }

Actions: View | Formatted Diff | Diff

Attachments on bug 194036: 360608 | 360647 | 360667 | 360907 | 360947 | 360948 | 361270 | 361481 | 361488 | 361496 | 361497 | 361716 | 361742 | 361989 | 361990 | 361991 | 362002 | 362055 | 362098