GitHub Viewer
/*
* 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
#include
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, std::span cases, Type type)
: m_weakRandom(globalCounter++)
, m_type(type)
, m_value(value)
, m_totalCases(cases.size())
{
RELEASE_ASSERT(type == Int32 || type == IntPtr);
if (cases.empty())
return;
if (BinarySwitchInternal::verbose)
dataLog("Original cases: ", listDump(cases), "\n");
m_cases.reserveInitialCapacity(cases.size());
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(GPRReg value, std::span runs)
: m_weakRandom(globalCounter++)
, m_type(UInt32CheckRuns)
, m_value(value)
{
if (runs.empty())
return;
m_cases.reserveInitialCapacity(runs.size());
unsigned keyStart = 0;
for (auto [firstKey, runLength] : runs) {
RELEASE_ASSERT(runLength);
RELEASE_ASSERT(firstKey == keyStart);
m_cases.append(Case(firstKey, keyStart));
keyStart += static_cast(runLength);
}
m_totalCases = keyStart;
if (BinarySwitchInternal::verbose)
dataLog("CheckRuns cases: ", listDump(m_cases), " totalKeys=", m_totalCases, "\n");
#if ASSERT_ENABLED
for (unsigned i = 1; i < m_cases.size(); ++i)
ASSERT(m_cases[i - 1].index < m_cases[i].index);
#endif
buildCheckRuns(0, m_cases.size());
}
BinarySwitch::~BinarySwitch() = default;
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(m_cases[code.index].value))));
break;
case IntPtr:
m_fallThrough.append(jit.branchPtr(
MacroAssembler::NotEqual, m_value,
MacroAssembler::ImmPtr(std::bit_cast(static_cast(m_cases[code.index].value)))));
break;
case UInt32CheckRuns:
RELEASE_ASSERT_NOT_REACHED();
break;
}
break;
case NotEqualToPush:
switch (m_type) {
case Int32:
m_jumpStack.append(jit.branch32(
MacroAssembler::NotEqual, m_value,
MacroAssembler::Imm32(static_cast(m_cases[code.index].value))));
break;
case IntPtr:
m_jumpStack.append(jit.branchPtr(
MacroAssembler::NotEqual, m_value,
MacroAssembler::ImmPtr(std::bit_cast(static_cast(m_cases[code.index].value)))));
break;
case UInt32CheckRuns:
RELEASE_ASSERT_NOT_REACHED();
break;
}
break;
case LessThanToPush:
switch (m_type) {
case Int32:
m_jumpStack.append(jit.branch32(
MacroAssembler::LessThan, m_value,
MacroAssembler::Imm32(static_cast(m_cases[code.index].value))));
break;
case IntPtr:
m_jumpStack.append(jit.branchPtr(
MacroAssembler::LessThan, m_value,
MacroAssembler::ImmPtr(std::bit_cast(static_cast(m_cases[code.index].value)))));
break;
case UInt32CheckRuns:
RELEASE_ASSERT_NOT_REACHED();
break;
}
break;
case BelowToPush:
ASSERT(isCheckRuns());
m_jumpStack.append(jit.branch32(
MacroAssembler::Below, m_value,
MacroAssembler::Imm32(static_cast(m_cases[code.index].value))));
break;
case AboveOrEqualToFallThrough:
ASSERT(isCheckRuns());
m_fallThrough.append(jit.branch32(
MacroAssembler::AboveOrEqual, m_value,
MacroAssembler::Imm32(static_cast(m_totalCases))));
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 NODELETE min() { return std::numeric_limits::min(); }
static constexpr uint32_t NODELETE max() { return std::numeric_limits::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 ", code, "\n");
m_branches.append(code);
};
unsigned size = end - start;
RELEASE_ASSERT(size);
if (size == 1) {
if (end == m_cases.size())
append(BranchCode(AboveOrEqualToFallThrough));
append(BranchCode(ExecuteCase, start));
return;
}
unsigned medianIndex = std::midpoint(start, end);
if (size & 1)
medianIndex += m_weakRandom.getUint32() & 1;
RELEASE_ASSERT(medianIndex > start);
RELEASE_ASSERT(medianIndex < end);
append(BranchCode(BelowToPush, medianIndex));
buildCheckRuns(medianIndex, end);
append(BranchCode(Pop));
buildCheckRuns(start, medianIndex);
}
void BinarySwitch::Case::dump(PrintStream& out) const
{
out.print("");
}
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 BelowToPush:
out.print("BelowToPush");
break;
case AboveOrEqualToFallThrough:
out.print("AboveOrEqualToFallThrough");
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)