ChangeLog

2019-05-03  Robin Morisset  <rmorisset@apple.com>

        [Air] highOrderAdjacents in AbstractColoringAllocator::conservativeHeuristic should be some kind of array

        https://bugs.webkit.org/show_bug.cgi?id=197305

        Reviewed by NOBODY (OOPS!).

        Currently it is a HashSet, but it only ever holds at most registerCount() items. And linear search tends to be faster on such a small collection than hashing + searching in a HashSet.

        Further benefits include avoiding the allocation of the HashSet, not actually adding the nodes adjacent to V (since there are no duplicates in the adjacency lists).

        This patch also contains a trivial optimization: if the remaining number of nodes to consider + the number of highOrderAdjacents already seen is smaller than registerCount() we can return true directly.

        Apart from that, the patch got some trivial cleanup of GraphColoringRegisterAllocation::allocateOnBank() (that for example was only logging the number of iterations for FP registers, and not the more interesting number for GP registers).

        The time spent in the register allocator throughout JetStream2 on this MacBook Pro moves from 3767 / 3710 / 3785 ms to 3551 / 3454 / 3503 ms.

        So about a 6% speedup for that phase, and between 1 and 1.5% speedup for FTL/OMG compilation overall.

        No new tests as there is no intended change to the code being generated, and this was already tested by running testb3 + JetStream2.

        * b3/air/AirAllocateRegistersByGraphColoring.cpp:

2019-05-03  Devin Rousso  <drousso@apple.com>

        Web Inspector: Record actions performed on WebGL2RenderingContext

Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp

@@protected:

        const auto& adjacentsOfU = m_adjacencyList[u];

        const auto& adjacentsOfV = m_adjacencyList[v];

195 if (adjacentsOfU.size() + adjacentsOfV.size() < registerCount()) {

        Vector<IndexType, 100> highOrderAdjacents;

        RELEASE_ASSERT(registerCount() < 100);

        unsigned numCandidates = adjacentsOfU.size() + adjacentsOfV.size();

        if (numCandidates < registerCount()) {

            // Shortcut: if the total number of adjacents is less than the number of register, the condition is always met.

            return true;

        }

200 HashSet<IndexType> highOrderAdjacents;

201

        for (IndexType adjacentTmpIndex : adjacentsOfU) {

            ASSERT(adjacentTmpIndex != v);

            ASSERT(adjacentTmpIndex != u);

206 numCandidates--;

205207 if (!hasBeenSimplified(adjacentTmpIndex) && m_degrees[adjacentTmpIndex] >= registerCount()) {

206 auto addResult = highOrderAdjacents.add(adjacentTmpIndex);

207 if (addResult.isNewEntry && highOrderAdjacents.size() >= registerCount())

                ASSERT(std::find(highOrderAdjacents.begin(), highOrderAdjacents.end(), adjacentTmpIndex) == highOrderAdjacents.end());

                highOrderAdjacents.uncheckedAppend(adjacentTmpIndex);

                if (highOrderAdjacents.size() >= registerCount())

208211 return false;

209 }

212 } else if (highOrderAdjacents.size() + numCandidates < registerCount())

213 return true;

210214 }

        ASSERT(numCandidates == adjacentsOfV.size());

        auto iteratorEndHighOrderAdjacentsOfU = highOrderAdjacents.end();

        for (IndexType adjacentTmpIndex : adjacentsOfV) {

            ASSERT(adjacentTmpIndex != u);

            ASSERT(adjacentTmpIndex != v);

            if (!hasBeenSimplified(adjacentTmpIndex) && m_degrees[adjacentTmpIndex] >= registerCount()) {

                auto addResult = highOrderAdjacents.add(adjacentTmpIndex);

                if (addResult.isNewEntry && highOrderAdjacents.size() >= registerCount())

            numCandidates--;

            if (!hasBeenSimplified(adjacentTmpIndex)

                && m_degrees[adjacentTmpIndex] >= registerCount()

                && std::find(highOrderAdjacents.begin(), iteratorEndHighOrderAdjacentsOfU, adjacentTmpIndex) == iteratorEndHighOrderAdjacentsOfU) {

                ASSERT(std::find(iteratorEndHighOrderAdjacentsOfU, highOrderAdjacents.end(), adjacentTmpIndex) == highOrderAdjacents.end());

                highOrderAdjacents.uncheckedAppend(adjacentTmpIndex);

                if (highOrderAdjacents.size() >= registerCount())

217228 return false;

218 }

229 } else if (highOrderAdjacents.size() + numCandidates < registerCount())

230 return true;

219231 }

220232

233 ASSERT(!numCandidates);

        ASSERT(highOrderAdjacents.size() < registerCount());

        return true;

    }

@@protected:

    }

    // Low-degree vertex can always be colored: just pick any of the color taken by any

1024 // other adjacent verices.

1037 // other adjacent vertices.

    // The "Simplify" phase takes a low-degree out of the interference graph to simplify it.

    void simplify()

    {

@@public:

        padInterference(m_code);

        allocateOnBank<GP>();

1792 m_numIterations = 0;

        allocateOnBank<FP>();

        fixSpillsAfterTerminals(m_code);

        if (reportStats)

            dataLog("Num iterations = ", m_numIterations, "\n");

    }

private:

@@private:

        // we should add the Tmp to unspillableTmps. That will help avoid relooping only to turn the

        // Tmp into an unspillable Tmp.

        // https://bugs.webkit.org/show_bug.cgi?id=152699

        
        while (true) {

            ++m_numIterations;

        unsigned numIterations = 0;

        bool done = false;

        while (!done) {

            ++numIterations;

18141826

18151827 if (traceDebug)

1816 dataLog("Code at iteration ", m_numIterations, ":\n", m_code);

1828 dataLog("Code at iteration ", numIterations, ":\n", m_code);

            // FIXME: One way to optimize this code is to remove the recomputation inside the fixpoint.

            // We need to recompute because spilling adds tmps, but we could just update tmpWidth when we

@@private:

            // spill code we emit. Since we currently recompute TmpWidth after spilling, the newly

            // created Tmps may get narrower use/def widths. On the other hand, the spiller already

            // selects which move instruction to use based on the original Tmp's widths, so it may not

1825 // matter than a subsequent iteration sees a coservative width for the new Tmps. Also, the

1837 // matter than a subsequent iteration sees a conservative width for the new Tmps. Also, the

            // recomputation may not actually be a performance problem; it's likely that a better way to

            // improve performance of TmpWidth is to replace its HashMap with something else. It's

            // possible that most of the TmpWidth overhead is from queries of TmpWidth rather than the

@@private:

                if (!allocator.requiresSpilling()) {

                    this->assignRegistersToTmp<bank>(allocator);

                    if (traceDebug)

1838 dataLog("Successfull allocation at iteration ", m_numIterations, ":\n", m_code);

1850 dataLog("Successfull allocation at iteration ", numIterations, ":\n", m_code);

                    return true;

                }

@@private:

                this->addSpillAndFill<bank>(allocator, unspillableTmps);

                return false;

            };

1846

1847 bool done;

1858

            if (useIRC()) {

                ColoringAllocator<bank, IRC> allocator(m_code, m_tmpWidth, m_useCounts, unspillableTmps);

                done = doAllocation(allocator);

@@private:

                ColoringAllocator<bank, Briggs> allocator(m_code, m_tmpWidth, m_useCounts, unspillableTmps);

                done = doAllocation(allocator);

            }

1855 if (done)

1856 return;

18571866 }

1867 dataLogLnIf(reportStats, "Num iterations = ", numIterations, " for bank: ", bank);

    }

    template<Bank bank>

@@private:

    Code& m_code;

    TmpWidth m_tmpWidth;

    UseCounts<Tmp>& m_useCounts;

2190 unsigned m_numIterations { 0 };

};

} // anonymous namespace