Changeset 263195 in webkit


Ignore:
Timestamp:
Jun 17, 2020 6:55:49 PM (4 years ago)
Author:
mark.lam@apple.com
Message:

Replace JSC::FreeList linked list with a Bitmap.
https://bugs.webkit.org/show_bug.cgi?id=213071

Reviewed by Filip Pizlo.

Source/JavaScriptCore:

Implement an alternative to the linked list FreeList. This alternative uses
a Bitmap to record which atom in the block is available for allocation.

The intuition here is that allocation using the Bitmap implementation will do:

2 loads - m_currentRowBitmap, m_currentMarkedBlockRowAddress
1 store - m_currentRowBitmap

whereas the linked list implementation will do:

3 loads - m_scrambledHead, m_secret, result->scrambledNext
1 store - m_scrambledHead

and result->scrambledNext is from a different region of code and therefore not
in the same cache line.

The downside of the Bitmap implementation is that it uses more instructions.

This change is currently only enabled for x86_64, which shows about a 0.8%
progression on Speedometer 2.

It appears to be about a 1% regression on ARM64E. Hence, for now, we keep the
linked list implementation for ARM64 builds.

This is how the Bitmap FreeList works:

  1. The Bitmap implementation only replaces the linked list implementation. It does not replace the bump allocator.
  1. The Bitmap allocator keeps a m_bitmap that is initialized in MarkedBlock::Handle::specializedSweep() to have a bit set for each atom location that is available for allocation (i.e. is free). Note that a cell is usually allocated using more than 1 atom. Only the bit corresponding to the first atom (in that cell length range of free atoms) will be set.

This is consistent with how bits in MarkedBlock::Footer::m_marks and
MarkedBlock::Footer::m_newlyAllocated are set i.e. only the bit for the first
atom in the cell can be set.

  1. The allocation algorithm thinks of the MarkedBlock as consisting of rows of atoms, where the number of atoms in a row equals the number of bits in a AtomsBitmap::Word. On 64-bit CPUs, this would be 64.

We will start allocating from the last (highest numbered) row down to the
first (row 0). As we allocate, we will only update m_currentRowIndex and
m_currentRowBitmap. m_bitmap will not be updated. This is so in order to
reduce the number of instructions executed during an allocation.

When m_currentRowIndex points to N, the AtomsBitmap::Word for row N in
m_bitmap will have been copied into m_currentRowBitmap. This is the row
that we will be allocating from until the row is exhausted.

This is how we know whether an atom is available for allocation or not:

  1. Atoms in any rows above m_currentRowIndex are guaranteed to be allocated already (because we allocate downwards), and hence, are not available.
  1. For row m_currentRowIndex, m_currentRowBitmap is the source of truth

on which atoms in the row are available for allocation.

  1. For rows below m_currentRowIndex, m_bitmap is the source of truth on

which atoms are available for allocation.

When m_currentRowIndex reaches 0, the info in m_bitmap is completely
obsoleted, and m_currentRowBitmap holds the availability info for row 0.
When both m_currentRowIndex and m_currentRowBitmap are 0, then we have
completely exhausted the block and no more atoms are available for
allocation.

  1. Allocation happens in 3 paths: fast, middle, slow.

The fast path checks m_currentRowBitmap. If it's not 0, then we compute the
bit number of the lowest set bit in it. That bit number will be used together
with m_currentMarkedBlockRowAddress to compute the address of the atom
location available for allocation. m_currentRowBitmap will be updated to clear
the bit for the atom that has just ben allocated.

If m_currentRowBitmap is 0, then we'll go to the middle path.

The middle path checks m_currentRowIndex to see if we have more rows to allocate
from. For each m_currentRowIndex, we check its corresponding AtomsBitmap::Word
in m_bitmap. If the word is non-zero, we copy it to m_currentRowBitmap and
jump to the fast path to do the allocation. The middle path will update
m_currentRowIndex to point to the current row we're allocating from.

If we have decremented m_currentRowIndex down to 0 but still can't find a
non-zero AtomsBitmap::Word in m_bitmap, then the block has been exhausted, and
we'll go to the slow path.

The slow path is analogous to the old slow path i.e. we try to refill the
LocalAllocator with a new MarkedBlock.

  1. On the layout of fields in FreeList (see changes in FreeList.h), we try to preserve the positions of the bump allocator fields. The only change we made there is n the location of m_cellSize. It is now moved up next to m_remaining, and m_originalSize is moved down. This is because m_originalSize is only accessed in the slow path, and m_cellSize is accessed in the bump allocation path.

Next, we try to put Bitmap allocation fields where the linked list fields
would have been. The one bit of trickiness is that we'll put
m_currentMarkedBlockRowAddress in a union with m_payloadEnd. This is because
m_payloadEnd is only used in the bump allocation path. If m_remaining is 0,
then we can reuse this location for m_currentMarkedBlockRowAddress.

With this, we would have 4 bytes of padding after m_currentRowIndex. For
compactness, we put m_originalSize there in that space. For builds that use
the linked list implementation, m_originalSize will be located below after
m_cellSize.

  • ftl/FTLLowerDFGToB3.cpp:

(JSC::FTL::DFG::LowerDFGToB3::allocateHeapCell):

  • heap/FreeList.cpp:

(JSC::FreeList::clear):
(JSC::FreeList::initializeAtomsBitmap):
(JSC::FreeList::initializeBump):
(JSC::FreeList::contains const):
(JSC::FreeList::dump const):

  • heap/FreeList.h:

(JSC::FreeList::bitmapIsEmpty const):
(JSC::FreeList::allocationWillFail const):
(JSC::FreeList::offsetOfCurrentRowBitmap):
(JSC::FreeList::offsetOfBitmapRows):
(JSC::FreeList::offsetOfCurrentRowIndex):
(JSC::FreeList::offsetOfCurrentMarkedBlockRowAddress):
(JSC::FreeList::offsetOfRemaining):
(JSC::FreeList::atomsBitmap):
(JSC::FreeList::bitmapRows const):
(JSC::FreeList::offsetOfOriginalSize): Deleted.

  • heap/FreeListInlines.h:

(JSC::FreeList::allocate):
(JSC::FreeList::forEach const):

  • heap/LocalAllocator.cpp:

(JSC::LocalAllocator::isFreeListedCell const):

  • heap/MarkedBlock.h:

(JSC::MarkedBlock::Handle::atomAt const):

  • heap/MarkedBlockInlines.h:

(JSC::MarkedBlock::Handle::specializedSweep):

  • jit/AssemblyHelpers.cpp:

(JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator):

  • jit/AssemblyHelpers.h:

(JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator):

Source/WTF:

  1. Use countOfBits<> template to compute the number of bits.
  2. Introduce log2() and log2Constexpr() utility functions.
  3. Make Bitmap<>::forEachSetBit() a little bit more efficient: we don't need to keep iterating if the bitmap word is already empty of bits.
  • wtf/Bitmap.h:

(WTF::WordType>::forEachSetBit const):

  • wtf/MathExtras.h:

(WTF::clzConstexpr):
(WTF::clz):
(WTF::ctzConstexpr):
(WTF::ctz):
(WTF::getMSBSet):
(WTF::getMSBSetConstexpr):
(WTF::log2):
(WTF::log2Constexpr):

Location:
trunk/Source
Files:
13 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r263193 r263195  
     12020-06-17  Mark Lam  <mark.lam@apple.com>
     2
     3        Replace JSC::FreeList linked list with a Bitmap.
     4        https://bugs.webkit.org/show_bug.cgi?id=213071
     5
     6        Reviewed by Filip Pizlo.
     7
     8        Implement an alternative to the linked list FreeList.  This alternative uses
     9        a Bitmap to record which atom in the block is available for allocation.
     10
     11        The intuition here is that allocation using the Bitmap implementation will do:
     12            2 loads - m_currentRowBitmap, m_currentMarkedBlockRowAddress
     13            1 store - m_currentRowBitmap
     14
     15        whereas the linked list implementation will do:
     16            3 loads - m_scrambledHead, m_secret, result->scrambledNext
     17            1 store - m_scrambledHead
     18
     19        and result->scrambledNext is from a different region of code and therefore not
     20        in the same cache line.
     21
     22        The downside of the Bitmap implementation is that it uses more instructions.
     23
     24        This change is currently only enabled for x86_64, which shows about a 0.8%
     25        progression on Speedometer 2.
     26
     27        It appears to be about a 1% regression on ARM64E.  Hence, for now, we keep the
     28        linked list implementation for ARM64 builds.
     29
     30        This is how the Bitmap FreeList works:
     31
     32        1. The Bitmap implementation only replaces the linked list implementation.  It
     33           does not replace the bump allocator.
     34
     35        2. The Bitmap allocator keeps a m_bitmap that is initialized in
     36           MarkedBlock::Handle::specializedSweep() to have a bit set for each atom
     37           location that is available for allocation (i.e. is free).  Note that a cell
     38           is usually allocated using more than 1 atom.  Only the bit corresponding to
     39           the first atom (in that cell length range of free atoms) will be set.
     40
     41           This is consistent with how bits in MarkedBlock::Footer::m_marks and
     42           MarkedBlock::Footer::m_newlyAllocated are set i.e. only the bit for the first
     43           atom in the cell can be set.
     44
     45        3. The allocation algorithm thinks of the MarkedBlock as consisting of rows
     46           of atoms, where the number of atoms in a row equals the number of bits in
     47           a AtomsBitmap::Word.  On 64-bit CPUs, this would be 64.
     48
     49           We will start allocating from the last (highest numbered) row down to the
     50           first (row 0).  As we allocate, we will only update m_currentRowIndex and
     51           m_currentRowBitmap.  m_bitmap will not be updated.  This is so in order to
     52           reduce the number of instructions executed during an allocation.
     53
     54           When m_currentRowIndex points to N, the AtomsBitmap::Word for row N in
     55           m_bitmap will have been copied into m_currentRowBitmap.  This is the row
     56           that we will be allocating from until the row is exhausted.
     57
     58           This is how we know whether an atom is available for allocation or not:
     59             i. Atoms in any rows above m_currentRowIndex are guaranteed to be
     60                allocated already (because we allocate downwards), and hence, are not
     61                available.
     62            ii. For row m_currentRowIndex, m_currentRowBitmap is the source of truth
     63                on which atoms in the row are available for allocation.
     64           iii. For rows below m_currentRowIndex, m_bitmap is the source of truth on
     65                which atoms are available for allocation.
     66
     67           When m_currentRowIndex reaches 0, the info in m_bitmap is completely
     68           obsoleted, and m_currentRowBitmap holds the availability info for row 0.
     69           When both m_currentRowIndex and m_currentRowBitmap are 0, then we have
     70           completely exhausted the block and no more atoms are available for
     71           allocation.
     72
     73        4. Allocation happens in 3 paths: fast, middle, slow.
     74
     75           The fast path checks m_currentRowBitmap.  If it's not 0, then we compute the
     76           bit number of the lowest set bit in it.  That bit number will be used together
     77           with m_currentMarkedBlockRowAddress to compute the address of the atom
     78           location available for allocation.  m_currentRowBitmap will be updated to clear
     79           the bit for the atom that has just ben allocated.
     80
     81           If m_currentRowBitmap is 0, then we'll go to the middle path.
     82
     83           The middle path checks m_currentRowIndex to see if we have more rows to allocate
     84           from.  For each m_currentRowIndex, we check its corresponding AtomsBitmap::Word
     85           in m_bitmap.  If the word is non-zero, we copy it to m_currentRowBitmap and
     86           jump to the fast path to do the allocation.  The middle path will update
     87           m_currentRowIndex to point to the current row we're allocating from.
     88
     89           If we have decremented m_currentRowIndex down to 0 but still can't find a
     90           non-zero AtomsBitmap::Word in m_bitmap, then the block has been exhausted, and
     91           we'll go to the slow path.
     92
     93           The slow path is analogous to the old slow path i.e. we try to refill the
     94           LocalAllocator with a new MarkedBlock.
     95
     96        5. On the layout of fields in FreeList (see changes in FreeList.h), we try to
     97           preserve the positions of the bump allocator fields.  The only change we made
     98           there is n the location of m_cellSize.  It is now moved up next to m_remaining,
     99           and m_originalSize is moved down.  This is because m_originalSize is only
     100           accessed in the slow path, and m_cellSize is accessed in the bump allocation
     101           path.
     102
     103           Next, we try to put Bitmap allocation fields where the linked list fields
     104           would have been.  The one bit of trickiness is that we'll put
     105           m_currentMarkedBlockRowAddress in a union with m_payloadEnd.  This is because
     106           m_payloadEnd is only used in the bump allocation path.  If m_remaining is 0,
     107           then we can reuse this location for m_currentMarkedBlockRowAddress.
     108
     109           With this, we would have 4 bytes of padding after m_currentRowIndex.  For
     110           compactness, we put m_originalSize there in that space.  For builds that use
     111           the linked list implementation, m_originalSize will be located below after
     112           m_cellSize.
     113
     114        * ftl/FTLLowerDFGToB3.cpp:
     115        (JSC::FTL::DFG::LowerDFGToB3::allocateHeapCell):
     116        * heap/FreeList.cpp:
     117        (JSC::FreeList::clear):
     118        (JSC::FreeList::initializeAtomsBitmap):
     119        (JSC::FreeList::initializeBump):
     120        (JSC::FreeList::contains const):
     121        (JSC::FreeList::dump const):
     122        * heap/FreeList.h:
     123        (JSC::FreeList::bitmapIsEmpty const):
     124        (JSC::FreeList::allocationWillFail const):
     125        (JSC::FreeList::offsetOfCurrentRowBitmap):
     126        (JSC::FreeList::offsetOfBitmapRows):
     127        (JSC::FreeList::offsetOfCurrentRowIndex):
     128        (JSC::FreeList::offsetOfCurrentMarkedBlockRowAddress):
     129        (JSC::FreeList::offsetOfRemaining):
     130        (JSC::FreeList::atomsBitmap):
     131        (JSC::FreeList::bitmapRows const):
     132        (JSC::FreeList::offsetOfOriginalSize): Deleted.
     133        * heap/FreeListInlines.h:
     134        (JSC::FreeList::allocate):
     135        (JSC::FreeList::forEach const):
     136        * heap/LocalAllocator.cpp:
     137        (JSC::LocalAllocator::isFreeListedCell const):
     138        * heap/MarkedBlock.h:
     139        (JSC::MarkedBlock::Handle::atomAt const):
     140        * heap/MarkedBlockInlines.h:
     141        (JSC::MarkedBlock::Handle::specializedSweep):
     142        * jit/AssemblyHelpers.cpp:
     143        (JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator):
     144        * jit/AssemblyHelpers.h:
     145        (JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator):
     146
    11472020-06-17  Mark Lam  <mark.lam@apple.com>
    2148
  • trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp

    r263165 r263195  
    1508015080        else
    1508115081            patchpoint->appendSomeRegisterWithClobber(allocator);
    15082         patchpoint->numGPScratchRegisters++;
     15082#if ENABLE(BITMAP_FREELIST)
     15083        constexpr unsigned scratchRegistersNeeded = 3;
     15084        constexpr unsigned allocatorScratch = 3;
     15085#else
     15086        constexpr unsigned scratchRegistersNeeded = 1;
     15087        constexpr unsigned allocatorScratch = 1;
     15088#endif
     15089        patchpoint->numGPScratchRegisters += scratchRegistersNeeded;
    1508315090        patchpoint->resultConstraints = { ValueRep::SomeEarlyRegister };
    1508415091       
     
    1509315100                GPRReg allocatorGPR;
    1509415101                if (actualAllocator.isConstant())
    15095                     allocatorGPR = params.gpScratch(1);
     15102                    allocatorGPR = params.gpScratch(allocatorScratch);
    1509615103                else
    1509715104                    allocatorGPR = params[1].gpr();
     
    1510515112                jit.emitAllocateWithNonNullAllocator(
    1510615113                    params[0].gpr(), actualAllocator, allocatorGPR, params.gpScratch(0),
    15107                     jumpToSlowPath);
     15114                    jumpToSlowPath
     15115#if ENABLE(BITMAP_FREELIST)
     15116                    , params.gpScratch(1), params.gpScratch(2)
     15117#endif
     15118                    );
    1510815119               
    1510915120                CCallHelpers::Jump jumpToSuccess;
  • trunk/Source/JavaScriptCore/heap/FreeList.cpp

    r261755 r263195  
    11/*
    2  * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2016-2020 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
     
    4040void FreeList::clear()
    4141{
     42#if ENABLE(BITMAP_FREELIST)
     43    m_currentRowBitmap = 0;
     44    m_currentRowIndex = 0;
     45#else
    4246    m_scrambledHead = 0;
    4347    m_secret = 0;
     48#endif
    4449    m_payloadEnd = nullptr;
    4550    m_remaining = 0;
    4651    m_originalSize = 0;
    4752}
     53
     54#if ENABLE(BITMAP_FREELIST)
     55
     56void FreeList::initializeAtomsBitmap(MarkedBlock::Handle* block, AtomsBitmap& freeAtoms, unsigned bytes)
     57{
     58#if ASSERT_ENABLED
     59    m_markedBlock = block;
     60#endif
     61    ASSERT_UNUSED(freeAtoms, &freeAtoms == &m_bitmap);
     62    // m_bitmap has already been filled in by MarkedBlock::Handle::specializedSweep().
     63
     64    m_currentRowBitmap = 0;
     65    size_t rowIndex = AtomsBitmap::numberOfWords;
     66    while (rowIndex--) {
     67        auto rowBitmap = m_bitmap.wordAt(rowIndex);
     68        if (rowBitmap) {
     69            m_currentRowBitmap = rowBitmap;
     70            break;
     71        }
     72    }
     73    ASSERT(m_currentRowBitmap || m_bitmap.isEmpty());
     74    m_currentRowIndex = m_currentRowBitmap ? rowIndex : 0;
     75
     76    size_t firstAtomInRow = m_currentRowIndex * atomsPerRow;
     77    m_currentMarkedBlockRowAddress = bitwise_cast<Atom*>(block->atomAt(firstAtomInRow));
     78    m_originalSize = bytes;
     79}
     80
     81#else
     82// Linked List implementation.
    4883
    4984void FreeList::initializeList(FreeCell* head, uintptr_t secret, unsigned bytes)
     
    5792}
    5893
     94#endif // ENABLE(BITMAP_FREELIST)
     95
    5996void FreeList::initializeBump(char* payloadEnd, unsigned remaining)
    6097{
     98#if ENABLE(BITMAP_FREELIST)
     99    m_currentRowBitmap = 0;
     100    m_currentRowIndex = 0;
     101#else
    61102    m_scrambledHead = 0;
    62103    m_secret = 0;
     104#endif
    63105    m_payloadEnd = payloadEnd;
    64106    m_remaining = remaining;
     
    66108}
    67109
    68 bool FreeList::contains(HeapCell* target) const
     110bool FreeList::contains(HeapCell* target, MarkedBlock::Handle* currentBlock) const
    69111{
    70112    if (m_remaining) {
     
    74116    }
    75117
     118#if ENABLE(BITMAP_FREELIST)
     119    if (bitmapIsEmpty())
     120        return false;
     121
     122    // currentBlock may be null if the allocator has been reset (and therefore,
     123    // the FreeList cleared. Hence, we should only check this assertion after
     124    // we check if the FreeList bitmap is empty above.
     125    ASSERT(m_markedBlock == currentBlock);
     126    if (!currentBlock->contains(target))
     127        return false;
     128
     129    unsigned atomNumber = currentBlock->block().atomNumber(target);
     130    unsigned rowIndex = atomNumber / atomsPerRow;
     131    if (rowIndex > m_currentRowIndex)
     132        return false;
     133    if (rowIndex == m_currentRowIndex) {
     134        constexpr AtomsBitmap::Word one = 1;
     135        unsigned firstAtomInRow = rowIndex * atomsPerRow;
     136        unsigned atomIndexInRow = atomNumber - firstAtomInRow;
     137        return m_currentRowBitmap & (one << atomIndexInRow);
     138    }
     139    return m_bitmap.get(atomNumber);
     140
     141#else
     142    UNUSED_PARAM(currentBlock);
    76143    FreeCell* candidate = head();
    77144    while (candidate) {
     
    80147        candidate = candidate->next(m_secret);
    81148    }
    82 
    83149    return false;
     150#endif
    84151}
    85152
    86153void FreeList::dump(PrintStream& out) const
    87154{
     155#if ENABLE(BITMAP_FREELIST)
     156    if (m_remaining)
     157        out.print("{payloadEnd = ", RawPointer(m_payloadEnd), ", remaining = ", m_remaining, ", originalSize = ", m_originalSize, "}");
     158    else
     159        out.print("{currentRowBitmap = ", m_currentRowBitmap, ", currentRowIndex = ", m_currentRowIndex, ", originalSize = ", m_originalSize, "}");
     160#else
    88161    out.print("{head = ", RawPointer(head()), ", secret = ", m_secret, ", payloadEnd = ", RawPointer(m_payloadEnd), ", remaining = ", m_remaining, ", originalSize = ", m_originalSize, "}");
     162#endif
    89163}
    90164
  • trunk/Source/JavaScriptCore/heap/FreeList.h

    r253443 r263195  
    11/*
    2  * Copyright (C) 2016-2019 Apple Inc. All rights reserved.
     2 * Copyright (C) 2016-2020 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
     
    2626#pragma once
    2727
     28#include "MarkedBlock.h"
    2829#include <wtf/Noncopyable.h>
    2930#include <wtf/PrintStream.h>
     31#include <wtf/StdIntExtras.h>
    3032
    3133namespace JSC {
     
    3335class HeapCell;
    3436
     37#if CPU(X86_64)
     38#define ENABLE_BITMAP_FREELIST 1
     39#else
     40#define ENABLE_BITMAP_FREELIST 0
     41#endif
     42
     43#if !ENABLE(BITMAP_FREELIST)
    3544struct FreeCell {
    3645    static uintptr_t scramble(FreeCell* cell, uintptr_t secret)
     
    5968    uintptr_t scrambledNext;
    6069};
     70#endif
    6171
    6272class FreeList {
     
    6777    void clear();
    6878   
    69     JS_EXPORT_PRIVATE void initializeList(FreeCell* head, uintptr_t secret, unsigned bytes);
    7079    JS_EXPORT_PRIVATE void initializeBump(char* payloadEnd, unsigned remaining);
    7180   
    72     bool allocationWillFail() const { return !head() && !m_remaining; }
    7381    bool allocationWillSucceed() const { return !allocationWillFail(); }
    7482   
     
    7684    HeapCell* allocate(const Func& slowPath);
    7785   
    78     bool contains(HeapCell*) const;
     86    bool contains(HeapCell*, MarkedBlock::Handle* currentBlock) const;
    7987   
    8088    template<typename Func>
     
    8391    unsigned originalSize() const { return m_originalSize; }
    8492
     93#if ENABLE(BITMAP_FREELIST)
     94    using Atom = MarkedBlock::Atom;
     95    using AtomsBitmap = MarkedBlock::AtomsBitmap;
     96
     97    static constexpr size_t atomsPerRow = AtomsBitmap::bitsInWord;
     98    static constexpr size_t atomsRowBytes = atomsPerRow * sizeof(Atom);
     99    static constexpr unsigned atomSizeShift = WTF::log2Constexpr(sizeof(Atom));
     100    static_assert((static_cast<size_t>(1) << atomSizeShift) == sizeof(Atom));
     101
     102    JS_EXPORT_PRIVATE void initializeAtomsBitmap(MarkedBlock::Handle*, AtomsBitmap& freeAtoms, unsigned bytes);
     103
     104    bool bitmapIsEmpty() const
     105    {
     106        // Remember, we don't actually clear the bits in m_bitmap as we allocate
     107        // the atoms. Instead, m_currentRowBitmap and m_currentRowIndex tells us
     108        // if there atoms still available for allocation. See comment blob below
     109        // at the declaration of m_currentRowIndex for more details.
     110        return !m_currentRowBitmap && !m_currentRowIndex;
     111    }
     112    bool allocationWillFail() const { return bitmapIsEmpty() && !m_remaining; }
     113
     114    static ptrdiff_t offsetOfCurrentRowBitmap() { return OBJECT_OFFSETOF(FreeList, m_currentRowBitmap); }
     115
     116    // We're deliberately returning the address of 1 word before m_bitmap so that
     117    // we can schedule instructions better i.e. to do a load before decrementing the
     118    // row index.
     119    static ptrdiff_t offsetOfBitmapRows() { return OBJECT_OFFSETOF(FreeList, m_bitmap) - sizeof(AtomsBitmap::Word); }
     120
     121    static ptrdiff_t offsetOfCurrentRowIndex() { return OBJECT_OFFSETOF(FreeList, m_currentRowIndex); }
     122    static ptrdiff_t offsetOfCurrentMarkedBlockRowAddress() { return OBJECT_OFFSETOF(FreeList, m_currentMarkedBlockRowAddress); }
     123#else
     124    JS_EXPORT_PRIVATE void initializeList(FreeCell* head, uintptr_t secret, unsigned bytes);
     125
     126    bool allocationWillFail() const { return !head() && !m_remaining; }
     127
    85128    static ptrdiff_t offsetOfScrambledHead() { return OBJECT_OFFSETOF(FreeList, m_scrambledHead); }
    86129    static ptrdiff_t offsetOfSecret() { return OBJECT_OFFSETOF(FreeList, m_secret); }
     130#endif
     131
    87132    static ptrdiff_t offsetOfPayloadEnd() { return OBJECT_OFFSETOF(FreeList, m_payloadEnd); }
    88133    static ptrdiff_t offsetOfRemaining() { return OBJECT_OFFSETOF(FreeList, m_remaining); }
    89     static ptrdiff_t offsetOfOriginalSize() { return OBJECT_OFFSETOF(FreeList, m_originalSize); }
    90134    static ptrdiff_t offsetOfCellSize() { return OBJECT_OFFSETOF(FreeList, m_cellSize); }
    91135   
     
    95139   
    96140private:
     141
     142#if ENABLE(BITMAP_FREELIST)
     143    AtomsBitmap& atomsBitmap() { return m_bitmap; }
     144    AtomsBitmap::Word* bitmapRows() const
     145    {
     146        // See comment about offsetOfBitmapRows().
     147        return bitwise_cast<AtomsBitmap::Word*>(&m_bitmap) - 1;
     148    }
     149
     150    // This allocation algorithm thinks of the MarkedBlock as consisting of rows
     151    // of atoms, where the number of atoms in a row equals the number of bits in
     152    // a AtomsBitmap::Word. On 64-bit CPUs, this would be 64.
     153    //
     154    // We will start allocating from the last (highest numbered) row down to the
     155    // first (row 0). As we allocate, we will only update m_currentRowIndex and
     156    // m_currentRowBitmap. m_bitmap will not be updated. This is so in oder to
     157    // reduce the number of instructions executed during an allocation.
     158    //
     159    // When m_currentRowIndex points to N, the AtomsBitmap::Word for row N in
     160    // m_bitmap will have been copied into m_currentRowBitmap. This is the row
     161    // that we will be allocating from until the row is exhausted.
     162    //
     163    // This is how we know whether an atom is available for allocation or not:
     164    // 1. Atoms in any rows above m_currentRowIndex are guaranteed to be
     165    //    allocated already (because we allocate downwards), and hence, are not
     166    //    available.
     167    // 2. For row m_currentRowIndex, m_currentRowBitmap is the source of truth
     168    //    on which atoms in the row are available for allocation.
     169    // 3. For rows below m_currentRowIndex, m_bitmap is the source of truth on
     170    //    which atoms are available for allocation.
     171    //
     172    // When m_currentRowIndex reaches 0, the info in m_bitmap is completely
     173    // obsoleted, and m_currentRowBitmap holds the availability info for row 0.
     174    // When both m_currentRowIndex and m_currentRowBitmap are 0, then we have
     175    // completely exhausted the block and no more atoms are available for
     176    // allocation.
     177
     178    AtomsBitmap::Word m_currentRowBitmap { 0 };
     179    unsigned m_currentRowIndex { 0 };
     180    unsigned m_originalSize { 0 };
     181
     182#else
    97183    FreeCell* head() const { return FreeCell::descramble(m_scrambledHead, m_secret); }
    98    
     184
    99185    uintptr_t m_scrambledHead { 0 };
    100186    uintptr_t m_secret { 0 };
    101     char* m_payloadEnd { nullptr };
     187#endif
     188
     189    union {
     190        char* m_payloadEnd { nullptr };
     191#if ENABLE(BITMAP_FREELIST)
     192        Atom* m_currentMarkedBlockRowAddress;
     193#endif
     194    };
    102195    unsigned m_remaining { 0 };
     196    unsigned m_cellSize { 0 };
     197
     198#if ENABLE(BITMAP_FREELIST)
     199    AtomsBitmap m_bitmap;
     200#else
    103201    unsigned m_originalSize { 0 };
    104     unsigned m_cellSize { 0 };
     202#endif
     203
     204#if ASSERT_ENABLED
     205    MarkedBlock::Handle* m_markedBlock { nullptr };
     206#endif
     207
     208    friend class MarkedBlock;
    105209};
    106210
  • trunk/Source/JavaScriptCore/heap/FreeListInlines.h

    r232132 r263195  
    11/*
    2  * Copyright (C) 2017 Apple Inc. All rights reserved.
     2 * Copyright (C) 2017-2020 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
     
    2727
    2828#include "FreeList.h"
    29 #include "MarkedBlock.h"
     29#include <wtf/MathExtras.h>
    3030
    3131namespace JSC {
     
    4141        return bitwise_cast<HeapCell*>(m_payloadEnd - remaining - cellSize);
    4242    }
    43    
     43
     44#if ENABLE(BITMAP_FREELIST)
     45    AtomsBitmap::Word rowBitmap = m_currentRowBitmap;
     46    do {
     47        if (rowBitmap) {
     48            constexpr AtomsBitmap::Word one = 1;
     49            unsigned atomIndexInRow = ctz(rowBitmap);
     50            auto* cell = bitwise_cast<HeapCell*>(&m_currentMarkedBlockRowAddress[atomIndexInRow]);
     51            rowBitmap &= ~(one << atomIndexInRow);
     52            m_currentRowBitmap = rowBitmap;
     53            return cell;
     54        }
     55
     56        unsigned rowIndex = m_currentRowIndex;
     57        auto* rowAddress = m_currentMarkedBlockRowAddress;
     58        while (rowIndex) {
     59            // We load before decrementing rowIndex because bitmapRows() points
     60            // to 1 word before m_bitmap. See comments about offsetOfBitmapRows()
     61            // for why we do this.
     62            rowBitmap = bitmapRows()[rowIndex--];
     63            rowAddress -= atomsPerRow;
     64            if (rowBitmap)
     65                break;
     66        }
     67        m_currentMarkedBlockRowAddress = rowAddress;
     68        m_currentRowIndex = rowIndex;
     69    } while (rowBitmap);
     70
     71    m_currentRowBitmap = rowBitmap;
     72    ASSERT(bitmapIsEmpty());
     73    return slowPath();
     74
     75#else // !ENABLE(BITMAP_FREELIST)
    4476    FreeCell* result = head();
    4577    if (UNLIKELY(!result))
     
    4880    m_scrambledHead = result->scrambledNext;
    4981    return bitwise_cast<HeapCell*>(result);
     82#endif // !ENABLE(BITMAP_FREELIST)
    5083}
    5184
     
    5790            func(bitwise_cast<HeapCell*>(m_payloadEnd - remaining));
    5891    } else {
     92#if ENABLE(BITMAP_FREELIST)
     93        if (bitmapIsEmpty())
     94            return;
     95
     96        AtomsBitmap::Word rowBitmap = m_currentRowBitmap;
     97        unsigned rowIndex = m_currentRowIndex;
     98        Atom* currentMarkedBlockRowAddress = m_currentMarkedBlockRowAddress;
     99        do {
     100            while (rowBitmap) {
     101                constexpr AtomsBitmap::Word one = 1;
     102                unsigned atomIndexInRow = ctz(rowBitmap);
     103                auto* cell = bitwise_cast<HeapCell*>(&currentMarkedBlockRowAddress[atomIndexInRow]);
     104                rowBitmap &= ~(one << atomIndexInRow);
     105                func(cell);
     106            }
     107
     108            while (rowIndex) {
     109                // We load before decrementing rowIndex because bitmapRows() points
     110                // to 1 word before m_bitmap. See comments about offsetOfBitmapRows()
     111                // for why we do this.
     112                rowBitmap = bitmapRows()[rowIndex--];
     113                currentMarkedBlockRowAddress -= atomsPerRow;
     114                if (rowBitmap)
     115                    break;
     116            }
     117        } while (rowBitmap);
     118#else
    59119        for (FreeCell* cell = head(); cell;) {
    60120            // We can use this to overwrite free objects before destroying the free list. So, we need
     
    64124            cell = next;
    65125        }
     126#endif
    66127    }
    67128}
    68129
    69130} // namespace JSC
    70 
  • trunk/Source/JavaScriptCore/heap/LocalAllocator.cpp

    r261755 r263195  
    11/*
    2  * Copyright (C) 2018-2019 Apple Inc. All rights reserved.
     2 * Copyright (C) 2018-2020 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
     
    273273    // objects to be in the dead-but-not-destructed state.
    274274    // FIXME: Get rid of this abomination. https://bugs.webkit.org/show_bug.cgi?id=181655
    275     return m_freeList.contains(bitwise_cast<HeapCell*>(target));
     275    return m_freeList.contains(bitwise_cast<HeapCell*>(target), m_currentBlock);
    276276}
    277277
  • trunk/Source/JavaScriptCore/heap/MarkedBlock.h

    r258857 r263195  
    22 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
    33 *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
    4  *  Copyright (C) 2003-2019 Apple Inc. All rights reserved.
     4 *  Copyright (C) 2003-2020 Apple Inc. All rights reserved.
    55 *
    66 *  This library is free software; you can redistribute it and/or
     
    8585    static_assert(!(MarkedBlock::blockSize & (MarkedBlock::blockSize - 1)), "MarkedBlock::blockSize must be a power of two.");
    8686   
     87    using AtomsBitmap = Bitmap<atomsPerBlock>;
     88
    8789    struct VoidFunctor {
    8890        typedef void ReturnType;
     
    204206        void* start() const { return &m_block->atoms()[0]; }
    205207        void* end() const { return &m_block->atoms()[m_endAtom]; }
     208        void* atomAt(size_t i) const { return &m_block->atoms()[i]; }
    206209        bool contains(void* p) const { return start() <= p && p < end(); }
    207210
     
    295298        HeapVersion m_newlyAllocatedVersion;
    296299
    297         Bitmap<atomsPerBlock> m_marks;
    298         Bitmap<atomsPerBlock> m_newlyAllocated;
     300        AtomsBitmap m_marks;
     301        AtomsBitmap m_newlyAllocated;
    299302    };
    300303   
     
    337340    void setNewlyAllocated(const void*);
    338341    void clearNewlyAllocated(const void*);
    339     const Bitmap<atomsPerBlock>& newlyAllocated() const;
     342    const AtomsBitmap& newlyAllocated() const;
    340343   
    341344    HeapVersion newlyAllocatedVersion() const { return footer().m_newlyAllocatedVersion; }
     
    375378    HeapVersion markingVersion() const { return footer().m_markingVersion; }
    376379   
    377     const Bitmap<atomsPerBlock>& marks() const;
     380    const AtomsBitmap& marks() const;
    378381   
    379382    CountingLock& lock() { return footer().m_lock; }
     
    400403    inline bool marksConveyLivenessDuringMarking(HeapVersion markingVersion);
    401404    inline bool marksConveyLivenessDuringMarking(HeapVersion myMarkingVersion, HeapVersion markingVersion);
     405
     406    friend class FreeList;
    402407};
    403408
  • trunk/Source/JavaScriptCore/heap/MarkedBlockInlines.h

    r261464 r263195  
    304304    }
    305305
     306#if ENABLE(BITMAP_FREELIST)
     307    AtomsBitmap localFreeAtoms;
     308    AtomsBitmap& freeAtoms = freeList ? freeList->atomsBitmap() : localFreeAtoms;
     309    size_t count = 0;
     310
     311    auto handleDeadCell = [&] (size_t i) {
     312        HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(atomAt(i));
     313
     314        if (destructionMode != BlockHasNoDestructors)
     315            destroy(cell);
     316
     317        if (sweepMode == SweepToFreeList) {
     318            if (scribbleMode == Scribble)
     319                scribble(cell, cellSize);
     320            ++count;
     321        }
     322    };
     323
     324    bool isEmpty = true;
     325
     326    AtomsBitmap cellLocations;
     327    cellLocations.setEachNthBit(m_atomsPerCell, 0, m_endAtom);
     328
     329    if (emptyMode == NotEmpty) {
     330        if (marksMode == MarksNotStale) {
     331            freeAtoms = footer.m_marks;
     332            if (newlyAllocatedMode == HasNewlyAllocated)
     333                freeAtoms |= footer.m_newlyAllocated;
     334        } else if (newlyAllocatedMode == HasNewlyAllocated)
     335            freeAtoms = footer.m_newlyAllocated;
     336        // At this point, a set bit in freeAtoms represents live cells.
     337        isEmpty = freeAtoms.isEmpty();
     338
     339        // Invert the bits at each cell location so that the ones for live cells
     340        // are cleared, and the ones for dead cells are set.
     341        freeAtoms ^= cellLocations;
     342    } else
     343        freeAtoms = cellLocations; // all cells are free.
     344   
     345    // We only want to discard the newlyAllocated bits if we're creating a FreeList,
     346    // otherwise we would lose information on what's currently alive.
     347    if (sweepMode == SweepToFreeList && newlyAllocatedMode == HasNewlyAllocated)
     348        footer.m_newlyAllocatedVersion = MarkedSpace::nullVersion;
     349
     350    if (space()->isMarking())
     351        footer.m_lock.unlock();
     352
     353    if (destructionMode != BlockHasNoDestructors)
     354        freeAtoms.forEachSetBit(handleDeadCell);
     355
     356    if (sweepMode == SweepToFreeList) {
     357        freeList->initializeAtomsBitmap(this, freeAtoms, count * cellSize);
     358        setIsFreeListed();
     359    } else if (isEmpty)
     360        m_directory->setIsEmpty(NoLockingNecessary, this, true);
     361    if (false)
     362        dataLog("Slowly swept block ", RawPointer(&block), " with cell size ", cellSize, " and attributes ", m_attributes, ": ", pointerDump(freeList), "\n");
     363
     364#else // not ENABLE(BITMAP_FREELIST)
     365
    306366    // This produces a free list that is ordered in reverse through the block.
    307367    // This is fine, since the allocation code makes no assumptions about the
     
    362422    if (false)
    363423        dataLog("Slowly swept block ", RawPointer(&block), " with cell size ", cellSize, " and attributes ", m_attributes, ": ", pointerDump(freeList), "\n");
     424#endif // ENABLE(BITMAP_FREELIST)
    364425}
    365426
  • trunk/Source/JavaScriptCore/jit/AssemblyHelpers.cpp

    r263049 r263195  
    504504#endif
    505505
    506 void AssemblyHelpers::emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath)
     506void AssemblyHelpers::emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath, Optional<GPRReg> optionalScratchGPR2, Optional<GPRReg> optionalScratchGPR3)
    507507{
    508508    if (Options::forceGCSlowPaths()) {
     
    517517
    518518    Jump popPath;
    519     Jump done;
     519    JumpList done;
    520520   
    521521    if (allocator.isConstant())
     
    535535    addPtr(payloadEndAddr, resultGPR);
    536536
    537     done = jump();
     537    done.append(jump());
    538538       
     539#if ENABLE(BITMAP_FREELIST)
     540    ASSERT(resultGPR != scratchGPR);
     541
     542    auto rowIndexGPR = resultGPR;
     543    auto rowBitmapGPR = scratchGPR;
     544
     545    GPRReg scratchGPR2 = optionalScratchGPR2 ? optionalScratchGPR2.value() : scratchRegister();
     546    ASSERT(scratchGPR2 != resultGPR);
     547    ASSERT(scratchGPR2 != scratchGPR);
     548
     549    auto rowAddressGPR = scratchGPR2;
     550    auto clearBit64ScratchGPR = scratchGPR2;
     551
     552    bool canPreloadRowAddressGPR = false;
     553    if (optionalScratchGPR3) {
     554        clearBit64ScratchGPR = optionalScratchGPR3.value();
     555        canPreloadRowAddressGPR = true;
     556    } else if (isX86_64()) {
     557        // x86_64's clearBit64() does actually need to use clearBit64ScratchGPR.
     558        // So, we can preload the row address into it.
     559        clearBit64ScratchGPR = InvalidGPRReg;
     560        canPreloadRowAddressGPR = true;
     561#if CPU(ARM64)
     562    } else if (isARM64()) {
     563        // ARM64's fast path does actually need to use the memoryTempRegister.
     564        // So, we can use that for the clearBit64ScratchGPR and allow the
     565        // row address to be preloaded in scratchGPR2.
     566        clearBit64ScratchGPR = getCachedMemoryTempRegisterIDAndInvalidate();
     567        canPreloadRowAddressGPR = true;
     568#endif
     569    }
     570    ASSERT(clearBit64ScratchGPR != resultGPR);
     571    ASSERT(clearBit64ScratchGPR != scratchGPR);
     572    if (canPreloadRowAddressGPR)
     573        ASSERT(clearBit64ScratchGPR != scratchGPR2);
     574
     575    // The code below for rowBitmapGPR relies on this.
     576    static_assert(sizeof(FreeList::AtomsBitmap::Word) == sizeof(uint64_t));
     577
     578    // Check for middle path: have another row to visit?
     579    Label checkForMoreRows = label();
     580
     581    load32(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowIndex()), rowIndexGPR);
     582
     583    if (!canPreloadRowAddressGPR)
     584        loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress()), rowAddressGPR);
     585
     586    slowPath.append(branchTestPtr(Zero, rowIndexGPR));
     587
     588    // Middle path: there is another row left to visit.
     589    Jump foundNonEmptyRow;
     590    Label checkNextRow = label();
     591    {
     592        // Load the next row bitmap and point m_currentMarkedBlockRowAddress to the next row.
     593
     594        // Note: offsetOfBitmapRows() points to 1 word before m_bitmap. We do this
     595        // deliberately because it allows us to schedule instructions better and
     596        // do this load before the decrement below.
     597        load64(BaseIndex(allocatorGPR, rowIndexGPR, TimesEight, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfBitmapRows()), rowBitmapGPR);
     598
     599        sub64(TrustedImm32(1), rowIndexGPR);
     600        subPtr(TrustedImm32(FreeList::atomsRowBytes), rowAddressGPR);
     601
     602        foundNonEmptyRow = branchTest64(NonZero, rowBitmapGPR);
     603        branchTestPtr(NonZero, rowIndexGPR).linkTo(checkNextRow, this);
     604    }
     605
     606    // Slow path: no more rows.
     607    // Both rowIndexGPR and rowBitmapGPR should be null here.
     608    store32(rowIndexGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowIndex()));
     609    store64(rowBitmapGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowBitmap()));
     610    slowPath.append(jump());
     611
     612    // Transition from middle path back to fast path to allocate.
     613    foundNonEmptyRow.link(this);
     614    storePtr(rowAddressGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress()));
     615    store32(rowIndexGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowIndex()));
     616
     617    Jump allocateFromCurrentRow = jump();
     618
    539619    popPath.link(this);
    540        
     620
     621    // Check for fast path: have available bit in m_currentRowBitmap?
     622    load64(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowBitmap()), rowBitmapGPR);
     623
     624    if (canPreloadRowAddressGPR) {
     625        // Preload the row address needed on the fast and middle path.
     626        loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress()), rowAddressGPR);
     627    }
     628
     629    branchTest64(Zero, rowBitmapGPR).linkTo(checkForMoreRows, this);
     630
     631    // Fast path: we have a bit to use.
     632    allocateFromCurrentRow.link(this);
     633    {
     634        // Remove this bit from m_currentRowBitmap.
     635        auto atomIndexInRowGPR = resultGPR;
     636        countTrailingZeros64WithoutNullCheck(rowBitmapGPR, atomIndexInRowGPR);
     637        clearBit64(atomIndexInRowGPR, rowBitmapGPR, clearBit64ScratchGPR);
     638
     639        if (!canPreloadRowAddressGPR)
     640            loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentMarkedBlockRowAddress()), rowAddressGPR);
     641
     642        store64(rowBitmapGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfCurrentRowBitmap()));
     643
     644        // Compute atom address of this bit.
     645        ASSERT(resultGPR == atomIndexInRowGPR);
     646        shiftAndAdd(rowAddressGPR, resultGPR, FreeList::atomSizeShift, resultGPR);
     647    }
     648
     649#else
     650    UNUSED_PARAM(optionalScratchGPR2);
     651    UNUSED_PARAM(optionalScratchGPR3);
     652
     653    popPath.link(this);
     654
    541655    loadPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfScrambledHead()), resultGPR);
    542656    xorPtr(Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfSecret()), resultGPR);
     
    547661    loadPtr(Address(resultGPR, FreeCell::offsetOfScrambledNext()), scratchGPR);
    548662    storePtr(scratchGPR, Address(allocatorGPR, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfScrambledHead()));
    549        
     663#endif
     664
    550665    done.link(this);
    551666}
  • trunk/Source/JavaScriptCore/jit/AssemblyHelpers.h

    r263151 r263195  
    4545#include "TypeofType.h"
    4646#include "VM.h"
     47#include <wtf/Optional.h>
    4748
    4849namespace JSC {
     
    19521953    // value of allocatorGPR is. Additionally, if the allocator is not null, then there is no need
    19531954    // to populate allocatorGPR - this code will ignore the contents of allocatorGPR.
    1954     void emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath);
    1955    
     1955    void emitAllocateWithNonNullAllocator(GPRReg resultGPR, const JITAllocator&, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath, Optional<GPRReg> scratchGPR2 = { }, Optional<GPRReg> scratchGPR3 = { });
     1956
    19561957    void emitAllocate(GPRReg resultGPR, const JITAllocator& allocator, GPRReg allocatorGPR, GPRReg scratchGPR, JumpList& slowPath);
    19571958   
  • trunk/Source/WTF/ChangeLog

    r263178 r263195  
     12020-06-17  Mark Lam  <mark.lam@apple.com>
     2
     3        Replace JSC::FreeList linked list with a Bitmap.
     4        https://bugs.webkit.org/show_bug.cgi?id=213071
     5
     6        Reviewed by Filip Pizlo.
     7
     8        1. Use countOfBits<> template to compute the number of bits.
     9        2. Introduce log2() and log2Constexpr() utility functions.
     10        3. Make Bitmap<>::forEachSetBit() a little bit more efficient: we don't need to
     11           keep iterating if the bitmap word is already empty of bits.
     12
     13        * wtf/Bitmap.h:
     14        (WTF::WordType>::forEachSetBit const):
     15        * wtf/MathExtras.h:
     16        (WTF::clzConstexpr):
     17        (WTF::clz):
     18        (WTF::ctzConstexpr):
     19        (WTF::ctz):
     20        (WTF::getMSBSet):
     21        (WTF::getMSBSetConstexpr):
     22        (WTF::log2):
     23        (WTF::log2Constexpr):
     24
    1252020-06-17  David Kilzer  <ddkilzer@apple.com>
    226
  • trunk/Source/WTF/wtf/Bitmap.h

    r262211 r263195  
    131131    unsigned hash() const;
    132132
     133    // Low level interface.
     134    using Word = WordType;
     135    static constexpr unsigned bitsInWord = countOfBits<WordType>;
     136    static constexpr unsigned numberOfWords = (bitmapSize + bitsInWord - 1) / bitsInWord;
     137    WordType wordAt(size_t wordIndex) const { return bits[wordIndex]; }
     138
    133139private:
    134     static constexpr unsigned wordSize = sizeof(WordType) * 8;
    135     static constexpr unsigned words = (bitmapSize + wordSize - 1) / wordSize;
     140    static constexpr unsigned wordSize = bitsInWord;
     141    static constexpr unsigned words = numberOfWords;
    136142
    137143    // the literal '1' is of type signed int.  We want to use an unsigned
     
    378384    for (size_t i = 0; i < words; ++i) {
    379385        WordType word = bits[i];
    380         if (!word)
    381             continue;
    382386        size_t base = i * wordSize;
    383         for (size_t j = 0; j < wordSize; ++j) {
     387        size_t j = 0;
     388        for (; word; ++j) {
    384389            if (word & 1)
    385390                func(base + j);
    386391            word >>= 1;
    387392        }
     393        ASSERT(j <= wordSize);
    388394    }
    389395}
  • trunk/Source/WTF/wtf/MathExtras.h

    r259537 r263195  
    594594constexpr unsigned clzConstexpr(T value)
    595595{
    596     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     596    constexpr unsigned bitSize = countOfBits<T>;
    597597
    598598    using UT = typename std::make_unsigned<T>::type;
     
    611611inline unsigned clz(T value)
    612612{
    613     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     613    constexpr unsigned bitSize = countOfBits<T>;
    614614
    615615    using UT = typename std::make_unsigned<T>::type;
     
    617617
    618618#if COMPILER(GCC_COMPATIBLE)
    619     constexpr unsigned bitSize64 = sizeof(uint64_t) * CHAR_BIT;
     619    constexpr unsigned bitSize64 = countOfBits<uint64_t>;
    620620    if (uValue)
    621621        return __builtin_clzll(uValue) - (bitSize64 - bitSize);
     
    639639constexpr unsigned ctzConstexpr(T value)
    640640{
    641     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     641    constexpr unsigned bitSize = countOfBits<T>;
    642642
    643643    using UT = typename std::make_unsigned<T>::type;
     
    658658inline unsigned ctz(T value)
    659659{
    660     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     660    constexpr unsigned bitSize = countOfBits<T>;
    661661
    662662    using UT = typename std::make_unsigned<T>::type;
     
    696696inline unsigned getMSBSet(T t)
    697697{
    698     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     698    constexpr unsigned bitSize = countOfBits<T>;
    699699    ASSERT(t);
    700700    return bitSize - 1 - clz(t);
     
    704704constexpr unsigned getMSBSetConstexpr(T t)
    705705{
    706     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     706    constexpr unsigned bitSize = countOfBits<T>;
    707707    ASSERT_UNDER_CONSTEXPR_CONTEXT(t);
    708708    return bitSize - 1 - clzConstexpr(t);
    709709}
     710
     711template<typename T> unsigned log2(T value) { return getMSBSet(value); }
     712template<typename T> constexpr unsigned log2Constexpr(T value) { return getMSBSetConstexpr(value); }
    710713
    711714} // namespace WTF
Note: See TracChangeset for help on using the changeset viewer.