source: webkit/trunk/Source/JavaScriptCore/jit/BinarySwitch.cpp

/*
 * Copyright (C) 2013-2019 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
#include "BinarySwitch.h"

#if ENABLE(JIT)

#include <wtf/ListDump.h>

namespace JSC {

namespace BinarySwitchInternal {
static constexpr bool verbose = false;
}

static unsigned globalCounter; // We use a different seed every time we are invoked.

BinarySwitch::BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type type)
    : m_type(type)
    , m_value(value)
    , m_weakRandom(globalCounter++)
    , m_index(0)
    , m_caseIndex(UINT_MAX)
{
    if (cases.isEmpty())
        return;

    if (BinarySwitchInternal::verbose)
        dataLog("Original cases: ", listDump(cases), "\n");
    
    for (unsigned i = 0; i < cases.size(); ++i)
        m_cases.append(Case(cases[i], i));
    
    std::sort(m_cases.begin(), m_cases.end());

    if (BinarySwitchInternal::verbose)
        dataLog("Sorted cases: ", listDump(m_cases), "\n");

#if ASSERT_ENABLED
    for (unsigned i = 1; i < m_cases.size(); ++i)
        ASSERT(m_cases[i - 1] < m_cases[i], i, m_cases.size(), m_cases[i].value, m_cases[i].index);
#endif

    build(0, false, m_cases.size());
}

BinarySwitch::~BinarySwitch()
{
}

bool BinarySwitch::advance(MacroAssembler& jit)
{
    if (m_cases.isEmpty()) {
        m_fallThrough.append(jit.jump());
        return false;
    }
    
    if (m_index == m_branches.size()) {
        RELEASE_ASSERT(m_jumpStack.isEmpty());
        return false;
    }
    
    for (;;) {
        const BranchCode& code = m_branches[m_index++];
        switch (code.kind) {
        case NotEqualToFallThrough:
            switch (m_type) {
            case Int32:
                m_fallThrough.append(jit.branch32(
                    MacroAssembler::NotEqual, m_value,
                    MacroAssembler::Imm32(static_cast<int32_t>(m_cases[code.index].value))));
                break;
            case IntPtr:
                m_fallThrough.append(jit.branchPtr(
                    MacroAssembler::NotEqual, m_value,
                    MacroAssembler::ImmPtr(bitwise_cast<const void*>(static_cast<intptr_t>(m_cases[code.index].value)))));
                break;
            }
            break;
        case NotEqualToPush:
            switch (m_type) {
            case Int32:
                m_jumpStack.append(jit.branch32(
                    MacroAssembler::NotEqual, m_value,
                    MacroAssembler::Imm32(static_cast<int32_t>(m_cases[code.index].value))));
                break;
            case IntPtr:
                m_jumpStack.append(jit.branchPtr(
                    MacroAssembler::NotEqual, m_value,
                    MacroAssembler::ImmPtr(bitwise_cast<const void*>(static_cast<intptr_t>(m_cases[code.index].value)))));
                break;
            }
            break;
        case LessThanToPush:
            switch (m_type) {
            case Int32:
                m_jumpStack.append(jit.branch32(
                    MacroAssembler::LessThan, m_value,
                    MacroAssembler::Imm32(static_cast<int32_t>(m_cases[code.index].value))));
                break;
            case IntPtr:
                m_jumpStack.append(jit.branchPtr(
                    MacroAssembler::LessThan, m_value,
                    MacroAssembler::ImmPtr(bitwise_cast<const void*>(static_cast<intptr_t>(m_cases[code.index].value)))));
                break;
            }
            break;
        case Pop:
            m_jumpStack.takeLast().link(&jit);
            break;
        case ExecuteCase:
            m_caseIndex = code.index;
            return true;
        }
    }
}

class RandomNumberGenerator {
public:
    using result_type = uint32_t;

    RandomNumberGenerator(WeakRandom& weakRandom)
        : m_weakRandom(weakRandom)
    {
    }

    uint32_t operator()()
    {
        return m_weakRandom.getUint32();
    }

    static constexpr uint32_t min() { return std::numeric_limits<uint32_t>::min(); }
    static constexpr uint32_t max() { return std::numeric_limits<uint32_t>::max(); }

private:
    WeakRandom& m_weakRandom;
};

void BinarySwitch::build(unsigned start, bool hardStart, unsigned end)
{
    if (BinarySwitchInternal::verbose)
        dataLog("Building with start = ", start, ", hardStart = ", hardStart, ", end = ", end, "\n");

    auto append = [&] (const BranchCode& code) {
        if (BinarySwitchInternal::verbose)
            dataLog("==> ", code, "\n");
        m_branches.append(code);
    };
    
    unsigned size = end - start;
    
    RELEASE_ASSERT(size);
    
    // This code uses some random numbers to keep things balanced. It's important to keep in mind
    // that this does not improve average-case throughput under the assumption that all cases fire
    // with equal probability. It just ensures that there will not be some switch structure that
    // when combined with some input will always produce pathologically good or pathologically bad
    // performance.
    
    const unsigned leafThreshold = 3;
    
    if (size <= leafThreshold) {
        if (BinarySwitchInternal::verbose)
            dataLog("It's a leaf.\n");
        
        // It turns out that for exactly three cases or less, it's better to just compare each
        // case individually. This saves 1/6 of a branch on average, and up to 1/3 of a branch in
        // extreme cases where the divide-and-conquer bottoms out in a lot of 3-case subswitches.
        //
        // This assumes that we care about the cost of hitting some case more than we care about
        // bottoming out in a default case. I believe that in most places where we use switch
        // statements, we are more likely to hit one of the cases than we are to fall through to
        // default. Intuitively, if we wanted to improve the performance of default, we would
        // reduce the value of leafThreshold to 2 or even to 1. See below for a deeper discussion.
        
        bool allConsecutive = false;
        
        if ((hardStart || (start && m_cases[start - 1].value == m_cases[start].value - 1))
            && start + size < m_cases.size()
            && m_cases[start + size - 1].value == m_cases[start + size].value - 1) {
            allConsecutive = true;
            for (unsigned i = 0; i < size - 1; ++i) {
                if (m_cases[start + i].value + 1 != m_cases[start + i + 1].value) {
                    allConsecutive = false;
                    break;
                }
            }
        }

        if (BinarySwitchInternal::verbose)
            dataLog("allConsecutive = ", allConsecutive, "\n");
        
        Vector<unsigned, 3> localCaseIndices;
        for (unsigned i = 0; i < size; ++i)
            localCaseIndices.append(start + i);
        
        std::shuffle(
            localCaseIndices.begin(), localCaseIndices.end(),
            RandomNumberGenerator(m_weakRandom));
        
        for (unsigned i = 0; i < size - 1; ++i) {
            append(BranchCode(NotEqualToPush, localCaseIndices[i]));
            append(BranchCode(ExecuteCase, localCaseIndices[i]));
            append(BranchCode(Pop));
        }
        
        if (!allConsecutive)
            append(BranchCode(NotEqualToFallThrough, localCaseIndices.last()));
        
        append(BranchCode(ExecuteCase, localCaseIndices.last()));
        return;
    }

    if (BinarySwitchInternal::verbose)
        dataLog("It's not a leaf.\n");
        
    // There are two different strategies we could consider here:
    //
    // Isolate median and split: pick a median and check if the comparison value is equal to it;
    // if so, execute the median case. Otherwise check if the value is less than the median, and
    // recurse left or right based on this. This has two subvariants: we could either first test
    // equality for the median and then do the less-than, or we could first do the less-than and
    // then check equality on the not-less-than path.
    //
    // Ignore median and split: do a less-than comparison on a value that splits the cases in two
    // equal-sized halves. Recurse left or right based on the comparison. Do not test for equality
    // against the median (or anything else); let the recursion handle those equality comparisons
    // once we bottom out in a list that case 3 cases or less (see above).
    //
    // I'll refer to these strategies as Isolate and Ignore. I initially believed that Isolate
    // would be faster since it leads to less branching for some lucky cases. It turns out that
    // Isolate is almost a total fail in the average, assuming all cases are equally likely. How
    // bad Isolate is depends on whether you believe that doing two consecutive branches based on
    // the same comparison is cheaper than doing the compare/branches separately. This is
    // difficult to evaluate. For small immediates that aren't blinded, we just care about
    // avoiding a second compare instruction. For large immediates or when blinding is in play, we
    // also care about the instructions used to materialize the immediate a second time. Isolate
    // can help with both costs since it involves first doing a < compare+branch on some value,
    // followed by a == compare+branch on the same exact value (or vice-versa). Ignore will do a <
    // compare+branch on some value, and then the == compare+branch on that same value will happen
    // much later.
    //
    // To evaluate these costs, I wrote the recurrence relation for Isolate and Ignore, assuming
    // that ComparisonCost is the cost of a compare+branch and ChainedComparisonCost is the cost
    // of a compare+branch on some value that you've just done another compare+branch for. These
    // recurrence relations compute the total cost incurred if you executed the switch statement
    // on each matching value. So the average cost of hitting some case can be computed as
    // Isolate[n]/n or Ignore[n]/n, respectively for the two relations.
    //
    // Isolate[1] = ComparisonCost
    // Isolate[2] = (2 + 1) * ComparisonCost
    // Isolate[3] = (3 + 2 + 1) * ComparisonCost
    // Isolate[n_] := With[
    //     {medianIndex = Floor[n/2] + If[EvenQ[n], RandomInteger[], 1]},
    //     ComparisonCost + ChainedComparisonCost +
    //     (ComparisonCost * (medianIndex - 1) + Isolate[medianIndex - 1]) +
    //     (2 * ComparisonCost * (n - medianIndex) + Isolate[n - medianIndex])]
    //
    // Ignore[1] = ComparisonCost
    // Ignore[2] = (2 + 1) * ComparisonCost
    // Ignore[3] = (3 + 2 + 1) * ComparisonCost
    // Ignore[n_] := With[
    //     {medianIndex = If[EvenQ[n], n/2, Floor[n/2] + RandomInteger[]]},
    //     (medianIndex * ComparisonCost + Ignore[medianIndex]) +
    //     ((n - medianIndex) * ComparisonCost + Ignore[n - medianIndex])]
    //
    // This does not account for the average cost of hitting the default case. See further below
    // for a discussion of that.
    //
    // It turns out that for ComparisonCost = 1 and ChainedComparisonCost = 1, Ignore is always
    // better than Isolate. If we assume that ChainedComparisonCost = 0, then Isolate wins for
    // switch statements that have 20 cases or fewer, though the margin of victory is never large
    // - it might sometimes save an average of 0.3 ComparisonCost. For larger switch statements,
    // we see divergence between the two with Ignore winning. This is of course rather
    // unrealistic since the chained comparison is never free. For ChainedComparisonCost = 0.5, we
    // see Isolate winning for 10 cases or fewer, by maybe 0.2 ComparisonCost. Again we see
    // divergence for large switches with Ignore winning, for example if a switch statement has
    // 100 cases then Ignore saves one branch on average.
    //
    // Our current JIT backends don't provide for optimization for chained comparisons, except for
    // reducing the code for materializing the immediate if the immediates are large or blinding
    // comes into play. Probably our JIT backends live somewhere north of
    // ChainedComparisonCost = 0.5.
    //
    // This implies that using the Ignore strategy is likely better. If we wanted to incorporate
    // the Isolate strategy, we'd want to determine the switch size threshold at which the two
    // cross over and then use Isolate for switches that are smaller than that size.
    //
    // The average cost of hitting the default case is similar, but involves a different cost for
    // the base cases: you have to assume that you will always fail each branch. For the Ignore
    // strategy we would get this recurrence relation; the same kind of thing happens to the
    // Isolate strategy:
    //
    // Ignore[1] = ComparisonCost
    // Ignore[2] = (2 + 2) * ComparisonCost
    // Ignore[3] = (3 + 3 + 3) * ComparisonCost
    // Ignore[n_] := With[
    //     {medianIndex = If[EvenQ[n], n/2, Floor[n/2] + RandomInteger[]]},
    //     (medianIndex * ComparisonCost + Ignore[medianIndex]) +
    //     ((n - medianIndex) * ComparisonCost + Ignore[n - medianIndex])]
    //
    // This means that if we cared about the default case more, we would likely reduce
    // leafThreshold. Reducing it to 2 would reduce the average cost of the default case by 1/3
    // in the most extreme cases (num switch cases = 3, 6, 12, 24, ...). But it would also
    // increase the average cost of taking one of the non-default cases by 1/3. Typically the
    // difference is 1/6 in either direction. This makes it a very simple trade-off: if we believe
    // that the default case is more important then we would want leafThreshold to be 2, and the
    // default case would become 1/6 faster on average. But we believe that most switch statements
    // are more likely to take one of the cases than the default, so we use leafThreshold = 3
    // and get a 1/6 speed-up on average for taking an explicit case.
        
    unsigned medianIndex = (start + end) / 2;

    if (BinarySwitchInternal::verbose)
        dataLog("medianIndex = ", medianIndex, "\n");

    // We want medianIndex to point to the thing we will do a less-than compare against. We want
    // this less-than compare to split the current sublist into equal-sized sublists, or
    // nearly-equal-sized with some randomness if we're in the odd case. With the above
    // calculation, in the odd case we will have medianIndex pointing at either the element we
    // want or the element to the left of the one we want. Consider the case of five elements:
    //
    //     0 1 2 3 4
    //
    // start will be 0, end will be 5. The average is 2.5, which rounds down to 2. If we do
    // value < 2, then we will split the list into 2 elements on the left and three on the right.
    // That's pretty good, but in this odd case we'd like to at random choose 3 instead to ensure
    // that we don't become unbalanced on the right. This does not improve throughput since one
    // side will always get shafted, and that side might still be odd, in which case it will also
    // have two sides and one of them will get shafted - and so on. We just want to avoid
    // deterministic pathologies.
    //
    // In the even case, we will always end up pointing at the element we want:
    //
    //     0 1 2 3
    //
    // start will be 0, end will be 4. So, the average is 2, which is what we'd like.
    if (size & 1) {
        RELEASE_ASSERT(medianIndex - start + 1 == end - medianIndex);
        medianIndex += m_weakRandom.getUint32() & 1;
    } else
        RELEASE_ASSERT(medianIndex - start == end - medianIndex);
        
    RELEASE_ASSERT(medianIndex > start);
    RELEASE_ASSERT(medianIndex + 1 < end);
        
    if (BinarySwitchInternal::verbose)
        dataLog("fixed medianIndex = ", medianIndex, "\n");

    append(BranchCode(LessThanToPush, medianIndex));
    build(medianIndex, true, end);
    append(BranchCode(Pop));
    build(start, hardStart, medianIndex);
}

void BinarySwitch::Case::dump(PrintStream& out) const
{
    out.print("<value: " , value, ", index: ", index, ">");
}

void BinarySwitch::BranchCode::dump(PrintStream& out) const
{
    switch (kind) {
    case NotEqualToFallThrough:
        out.print("NotEqualToFallThrough");
        break;
    case NotEqualToPush:
        out.print("NotEqualToPush");
        break;
    case LessThanToPush:
        out.print("LessThanToPush");
        break;
    case Pop:
        out.print("Pop");
        break;
    case ExecuteCase:
        out.print("ExecuteCase");
        break;
    }

    if (index != UINT_MAX)
        out.print("(", index, ")");
}

} // namespace JSC

#endif // ENABLE(JIT)