#include "config.h"

#include "ExpressionInfo.h"

#include "VM.h"

#include <numeric>

#include <wtf/DataLog.h>

#include <wtf/StringPrintStream.h>

namespace JSC {

struct ExpressionInfo::Diff {

using FieldID = ExpressionInfo::FieldID;

template<unsigned bitCount>

void LEGACY_NODELETE set(FieldID fieldID, unsigned value)

}

void reset()

}

unsigned instPC { 0 };

int divot { 0 };

unsigned start { 0 };

unsigned end { 0 };

};

static_assert(std::same_as<decltype(ExpressionInfo::Diff::divot), int>);

bool ExpressionInfo::EncodedInfo::isAbsInstPC() const

{

if (value < (specialHeader << headerShift))

return false;

bool isMulti = (value >> multiBitShift) & 1;

return !isMulti;

}

bool ExpressionInfo::EncodedInfo::isExtension() const

{

if (value < (specialHeader << headerShift))

return false;

bool isMulti = (value >> multiBitShift) & 1;

return isMulti;

}

auto ExpressionInfo::Encoder::encodeAbsInstPC(InstPC absInstPC) -> EncodedInfo

{

unsigned word = specialHeader << headerShift

| 0 << multiBitShift

| (absInstPC & maxSpecialValue) << specialValueShift;

return { word };

}

auto ExpressionInfo::Encoder::encodeExtension(unsigned offset) -> EncodedInfo

{

RELEASE_ASSERT((offset & maxSpecialValue) == offset);

unsigned word = specialHeader << headerShift

| 1 << multiBitShift

| (offset & maxSpecialValue) << specialValueShift;

return { word };

}

auto constexpr ExpressionInfo::Encoder::encodeExtensionEnd() -> EncodedInfo

{

unsigned word = wideHeader << headerShift

| 0 << multiBitShift

| static_cast<unsigned>(invalidFieldID) << firstFieldIDShift;

return { word };

}

auto ExpressionInfo::Encoder::encodeSingle(FieldID fieldID, unsigned value) -> EncodedInfo

{

unsigned word = wideHeader << headerShift

| 0 << multiBitShift

| static_cast<unsigned>(fieldID) << firstFieldIDShift

| (value & maxSingleValue) << singleValueShift;

return { word };

}

auto ExpressionInfo::Encoder::encodeDuo(FieldID fieldID1, unsigned value1, FieldID fieldID2, unsigned value2) -> EncodedInfo

{

unsigned word = wideHeader << headerShift

| 1 << multiBitShift

| static_cast<unsigned>(fieldID1) << firstFieldIDShift

| (value1 & maxDuoValue) << duoFirstValueShift

| static_cast<unsigned>(fieldID2) << duoSecondFieldIDShift

| (value2 & maxDuoValue) << duoSecondValueShift;

return { word };

}

auto ExpressionInfo::Encoder::encodeMultiHeader(unsigned numWides, Wide* wides) -> EncodedInfo

{

unsigned word = wideHeader << headerShift

| 1 << multiBitShift

| static_cast<unsigned>(invalidFieldID) << firstFieldIDShift

| numWides << multiSizeShift;

unsigned fieldShift = multiFirstFieldShift;

for (unsigned i = 0; i < numWides; ++i) {

word |= static_cast<unsigned>(wides[i].fieldID) << fieldShift;

fieldShift -= fieldIDBits;

}

return { word };

}

auto ExpressionInfo::Encoder::encodeBasic(const Diff& diff) -> EncodedInfo

{

ASSERT(diff.instPC <= maxInstPCValue);

ASSERT(diff.start <= maxStartValue);

ASSERT(diff.end <= maxEndValue);

unsigned biasedDivot = diff.divot + divotBias;

ASSERT(biasedDivot <= maxBiasedDivotValue);

unsigned word = diff.instPC << instPCShift | biasedDivot << divotShift

| diff.start << startShift | diff.end << endShift;

return { word };

}

void ExpressionInfo::Encoder::adjustInstPC(unsigned infoIndex, unsigned instPCDelta)

{

unsigned firstValue = m_expressionInfoEncodedInfo[infoIndex].value;

unsigned headerBits = firstValue >> headerShift;

bool isMulti = (firstValue >> multiBitShift) & 1;

unsigned firstFieldIDBits = (firstValue >> firstFieldIDShift) & fieldIDMask;

bool isBasic = false;

if (headerBits == specialHeader) {

// Handle AbsInstPC.

ASSERT(!isMulti); // firstWord cannot already be an Extension word.

unsigned instPC = cast<unsigned, specialValueBits>(firstValue);

unsigned updatedInstPC = instPC + instPCDelta;

if (fits<unsigned, specialValueBits>(updatedInstPC)) {

m_expressionInfoEncodedInfo[infoIndex] = encodeAbsInstPC(updatedInstPC);

return;

}

goto emitExtension;

}

if (headerBits == wideHeader) {

if (!isMulti) {

// Handle SingleWide.

ASSERT(firstFieldIDBits != invalidFieldID); // firstWord cannot already be an ExtensionEnd word.

FieldID fieldID = static_cast<FieldID>(firstFieldIDBits);

unsigned candidateInstPC = cast<unsigned, singleValueBits>(firstValue);

unsigned updatedInstPC = candidateInstPC + instPCDelta;

if (fieldID == FieldID::InstPC && fits<unsigned, singleValueBits>(updatedInstPC)) {

m_expressionInfoEncodedInfo[infoIndex] = encodeSingle(FieldID::InstPC, updatedInstPC);

return;

}

goto emitExtension;

}

if (firstFieldIDBits != invalidFieldID) {

// Handle DuoWide.

ASSERT(firstFieldIDBits != invalidFieldID); // firstWord cannot already be an ExtensionEnd word.

FieldID fieldID = static_cast<FieldID>(firstFieldIDBits);

unsigned candidateInstPC = cast<unsigned, duoValueBits>(firstValue >> duoFirstValueShift);

unsigned updatedInstPC = candidateInstPC + instPCDelta;

if (fieldID == FieldID::InstPC && fits<unsigned, duoValueBits>(updatedInstPC)) {

FieldID fieldID2 = static_cast<FieldID>((firstValue >> duoSecondFieldIDShift) & fieldIDMask);

unsigned value2 = cast<unsigned, duoValueBits>(firstValue >> duoSecondValueShift);

m_expressionInfoEncodedInfo[infoIndex] = encodeDuo(FieldID::InstPC, updatedInstPC, fieldID2, value2);

return;

}

goto emitExtension;

}

// Handle MultiWide.

FieldID firstMultiFieldID = static_cast<FieldID>((firstValue >> multiFirstFieldShift) & fieldIDMask);

if (firstMultiFieldID == FieldID::InstPC) {

unsigned instPC = m_expressionInfoEncodedInfo[infoIndex + 1].value;

unsigned updatedInstPC = instPC + instPCDelta;

m_expressionInfoEncodedInfo[infoIndex + 1].value = updatedInstPC;

return;

}

// We can't just move the MultiWide header to the extension: we have to move the

// whole MultiWide record (i.e. multiple words). The Decoder relies on them to

// being contiguous.

unsigned numberOfFields = (firstValue >> multiSizeShift) & multiSizeMask;

unsigned locationOfExtensionIsland = m_expressionInfoEncodedInfo.size();

m_expressionInfoEncodedInfo.append({ firstValue }); // MultiWide header.

for (unsigned i = 1; i < numberOfFields; ++i) {

auto fieldValue = m_expressionInfoEncodedInfo[infoIndex + i];

m_expressionInfoEncodedInfo.append(fieldValue);

m_expressionInfoEncodedInfo[infoIndex + i] = encodeSingle(FieldID::InstPC, 0); // Replace with a no-op.

}

// Save the last field in firstValue, and let the extension emitter below append it.

firstValue = m_expressionInfoEncodedInfo[infoIndex + numberOfFields].value;

m_expressionInfoEncodedInfo[infoIndex + numberOfFields] = encodeSingle(FieldID::InstPC, 0); // Replace with a no-op.

unsigned extensionOffset = locationOfExtensionIsland - infoIndex;

m_expressionInfoEncodedInfo[infoIndex] = encodeExtension(extensionOffset);

goto emitExtensionIsland;

}

// Handle Basic.

{

unsigned instPC = cast<unsigned, instPCBits>(firstValue >> instPCShift);

unsigned updatedInstPC = instPC + instPCDelta;

if (updatedInstPC < maxInstPCValue) {

unsigned replacement = firstValue & ((1u << instPCShift) - 1);

replacement |= updatedInstPC << instPCShift;

m_expressionInfoEncodedInfo[infoIndex] = { replacement };

return;

}

}

isBasic = true;

emitExtension:

{

unsigned extensionOffset = m_expressionInfoEncodedInfo.size() - infoIndex;

m_expressionInfoEncodedInfo[infoIndex] = encodeExtension(extensionOffset);

}

emitExtensionIsland:

// Because the Basic word is used as a terminator for the current Entry,

// if the firstValue is a Basic word, it needs to come last. Otherwise, we should

// just emit firstValue first. AbsInstPC and MultiWide relies on this for correctness.

if (!isBasic)

m_expressionInfoEncodedInfo.append({ firstValue });

if (fits<unsigned, singleValueBits>(instPCDelta))

m_expressionInfoEncodedInfo.append(encodeSingle(FieldID::InstPC, instPCDelta));

else {

// The wides array is really only to enable us to use encodeMultiHeader. Hence,

// we don't really need to store instPCDelta as the value here. It can be any value

// since it's not used. However, to avoid confusion, we'll just populate it consistently.

Wide wides[1] = { { instPCDelta, FieldID::InstPC } };

m_expressionInfoEncodedInfo.append(encodeMultiHeader(1, wides));

m_expressionInfoEncodedInfo.append({ instPCDelta });

}

if (isBasic) {

// If we're terminating with the Basic word, then we don't need the

// ExtensionEnd because the Basic word is an implied end.

m_expressionInfoEncodedInfo.append({ firstValue });

} else

m_expressionInfoEncodedInfo.append(encodeExtensionEnd());

}

void ExpressionInfo::Encoder::encode(InstPC instPC, unsigned divot, unsigned startOffset, unsigned endOffset)

{

unsigned numWides = 0;

std::array<Wide, 4> wides;

auto appendWide = [&] (FieldID id, unsigned value) {

wides[numWides++] = { value, id };

};

unsigned currentEncodedInfoIndex = m_expressionInfoEncodedInfo.size();

unsigned chapterSize = currentEncodedInfoIndex - m_currentChapterStartIndex;

if (chapterSize >= numberOfWordsBetweenChapters) {

m_expressionInfoChapters.append({ instPC, currentEncodedInfoIndex });

m_currentChapterStartIndex = currentEncodedInfoIndex;

unsigned absInstPC = std::min(instPC, maxSingleValue);

m_expressionInfoEncodedInfo.append(encodeAbsInstPC(absInstPC));

m_entry.reset();

m_entry.instPC = absInstPC;

}

Diff diff;

diff.instPC = instPC - m_entry.instPC;

diff.divot = divot - m_entry.divot;

diff.start = startOffset;

diff.end = endOffset;

// Only divot needs a bias to fit a Basic word: instPC increases monotonically, and start and

// end are measured from divot, so all three of those diffs are positive.

// Encode header:

if (diff.instPC > maxInstPCValue) {

appendWide(FieldID::InstPC, diff.instPC);

diff.instPC = 0;

}

// Encode divot:

if (diff.divot + divotBias > maxBiasedDivotValue) {

appendWide(FieldID::Divot, diff.divot);

diff.divot = 0;

}

// Encode start:

if (diff.start > maxStartValue) {

appendWide(FieldID::Start, diff.start);

diff.start = 0;

}

// Encode end:

if (diff.end > maxEndValue) {

appendWide(FieldID::End, diff.end);

diff.end = 0;

}

m_entry.instPC = instPC;

m_entry.divot = divot;

// Canonicalize the wide EncodedInfo.

{

unsigned lastDuoIndex = numWides;

unsigned numDuoWides = 0;

// We want to process the InstPC wide (if present) last. This enables an InstPC wide to be emitted

// first (if possible) to simplify the remap logic in adjustInst(). adjustInst() assumes that

// the InstPC wide (if present) will likely be in the first word.

for (unsigned i = numWides; i--; ) {

auto& wide = wides[i];

if (fits<duoValueBits>(wide)) {

wide.order = Wide::SortOrder::Duo;

numDuoWides++;

lastDuoIndex = i;

} else if (fits<singleValueBits>(wide))

wide.order = Wide::SortOrder::Single;

else

wide.order = Wide::SortOrder::Multi;

}

if (numDuoWides & 1)

wides[lastDuoIndex].order = Wide::SortOrder::Single;

auto* widesData = wides.data();

std::sort(widesData, widesData + numWides, [] (auto& a, auto& b) {

if (static_cast<unsigned>(a.order) < static_cast<unsigned>(b.order))

return true;

if (static_cast<unsigned>(a.order) == static_cast<unsigned>(b.order))

return a.fieldID < b.fieldID;

return false;

});

}

// Emit the wide EncodedInfo.

for (unsigned i = 0; i < numWides; ++i) {

auto& wide = wides[i];

if (wide.order == Wide::SortOrder::Single) {

m_expressionInfoEncodedInfo.append(encodeSingle(wide.fieldID, wide.value));

continue;

}

if (wide.order == Wide::SortOrder::Duo) {

auto& wide2 = wides[++i];

ASSERT(fits<duoValueBits>(wide));

ASSERT(fits<duoValueBits>(wide2));

m_expressionInfoEncodedInfo.append(encodeDuo(wide.fieldID, wide.value, wide2.fieldID, wide2.value));

continue;

}

ASSERT(wide.order == Wide::SortOrder::Multi);

unsigned remainingWides = numWides - i;

m_expressionInfoEncodedInfo.append(encodeMultiHeader(remainingWides, &wide));

while (i < numWides)

m_expressionInfoEncodedInfo.append({ wides[i++].value });

}

m_expressionInfoEncodedInfo.append(encodeBasic(diff));

}

template<unsigned bitCount>

bool ExpressionInfo::Encoder::fits(Wide wide)

{

switch (wide.fieldID) {

case FieldID::InstPC:

case FieldID::Start:

case FieldID::End:

return fits<unsigned, bitCount>(wide.value);

case FieldID::Divot:

return fits<int, bitCount>(wide.value);

}

return false; // placate GCC.

}

template<typename T, unsigned bitCount>

bool ExpressionInfo::Encoder::fits(T value)

{

struct Caster {

T value : bitCount;

} caster;

caster.value = value;

return caster.value == value;

}

std::unique_ptr<ExpressionInfo> ExpressionInfo::Encoder::createExpressionInfo()

{

size_t numberOfChapters = m_expressionInfoChapters.size();

size_t numberOfEncodedInfo = m_expressionInfoEncodedInfo.size() - m_numberOfEncodedInfoExtensions;

size_t totalSize = ExpressionInfo::totalSizeInBytes(numberOfChapters, numberOfEncodedInfo, m_numberOfEncodedInfoExtensions);

void* allocation = FastMalloc::malloc(totalSize);

return std::unique_ptr<ExpressionInfo>(new (allocation) ExpressionInfo(WTF::move(m_expressionInfoChapters), WTF::move(m_expressionInfoEncodedInfo), m_numberOfEncodedInfoExtensions));

}

ExpressionInfo::Decoder::Decoder(const ExpressionInfo& expressionInfo)

: m_startInfo(expressionInfo.encodedInfo())

, m_endInfo(expressionInfo.endEncodedInfo())

, m_endExtensionInfo(expressionInfo.endExtensionEncodedInfo())

, m_currentInfo(m_startInfo)

, m_nextInfo(m_startInfo)

{

}

ExpressionInfo::Decoder::Decoder(Vector<ExpressionInfo::EncodedInfo>& encodedInfoVector)

: m_startInfo(encodedInfoVector.begin())

, m_endInfo(encodedInfoVector.end())

, m_endExtensionInfo(encodedInfoVector.end())

, m_currentInfo(m_startInfo)

, m_nextInfo(m_startInfo)

{

}

void ExpressionInfo::Decoder::recacheInfo(Vector<ExpressionInfo::EncodedInfo>& encodedInfoVector)

{

if (m_endInfo == encodedInfoVector.end())

return; // Did not resize i.e nothing changed.

m_currentInfo = &encodedInfoVector[m_currentInfo - m_startInfo];

m_nextInfo = &encodedInfoVector[m_nextInfo - m_startInfo];

m_endInfo = &encodedInfoVector[m_endInfo - m_startInfo];

m_startInfo = encodedInfoVector.begin();

m_endExtensionInfo = encodedInfoVector.end();

}

template<typename T, unsigned bitCount>

T ExpressionInfo::cast(unsigned value)

}

bool ExpressionInfo::isSpecial(unsigned value)

{

return value >= (specialHeader << headerShift);

}

bool ExpressionInfo::isWideOrSpecial(unsigned value)

{

return value >= (wideHeader << headerShift);

}

IterationStatus ExpressionInfo::Decoder::decode(std::optional<ExpressionInfo::InstPC> targetInstPC)

{

m_currentInfo = m_nextInfo; // Go decode the next Entry.

ASSERT(m_currentInfo <= m_endInfo);

ASSERT(m_endInfo <= m_endExtensionInfo);

auto* currentInfo = m_currentInfo;

if (currentInfo == m_endInfo)

return IterationStatus::Done;

Diff diff;

unsigned value = currentInfo->value;

EncodedInfo* savedInfo = nullptr;

bool hasAbsInstPC = false;

InstPC currentInstPC = m_entry.instPC;

// Decode wide words.

while (isWideOrSpecial(value)) {

bool isSpecial = ExpressionInfo::isSpecial(value);

bool isMulti = (value >> multiBitShift) & 1;

unsigned firstFieldIDBits = (value >> firstFieldIDShift) & fieldIDMask;

if (isSpecial) {

if (isMulti) {

// Decode Extension word.

unsigned extensionOffset = cast<unsigned, specialValueBits>(value);

savedInfo = currentInfo;

currentInfo += extensionOffset - 1; // -1 to compensate for the increment below.

ASSERT(currentInfo >= m_endInfo - 1);

ASSERT(currentInfo < m_endExtensionInfo);

} else {

// Decode AbsInstPC word.

ASSERT(currentInfo == m_currentInfo);

// We can't call m_entry.reset() here because we always scan up to the entry

// above the one that we're looking for before declaring Done. Hence, we have

// to defer any changes to m_entry until we know that the current entry does

// not exceed what we're looking for, and that we can commit it.

hasAbsInstPC = true;

currentInstPC = 0;

diff.reset();

diff.set<specialValueBits>(FieldID::InstPC, value);

}

} else if (firstFieldIDBits == invalidFieldID && !isMulti) {

// Decode ExtensionEnd word.

ASSERT(savedInfo);

currentInfo = savedInfo;

// We need to clear savedInfo to indicate that we terminated the Extension with

// ExtensionEnd. Otherwise, we need to restore currentInfo after we decode the Basic word

// terminator.

savedInfo = nullptr;

} else if (firstFieldIDBits == invalidFieldID) {

// Decode MultiWide word.

unsigned numberOfFields = (value >> multiSizeShift) & multiSizeMask;

unsigned fieldShift = multiFirstFieldShift;

for (unsigned i = 0; i < numberOfFields; ++i) {

++currentInfo;

auto fieldID = static_cast<FieldID>((value >> fieldShift) & fieldIDMask);

diff.set<fullValueBits>(fieldID, currentInfo->value);

fieldShift -= fieldIDBits;

}

} else if (isMulti) {

// Decode DuoWide word.

auto fieldID1 = static_cast<FieldID>(firstFieldIDBits);

auto fieldID2 = static_cast<FieldID>((value >> duoSecondFieldIDShift) & fieldIDMask);

diff.set<duoValueBits>(fieldID1, value >> duoFirstValueShift);

diff.set<duoValueBits>(fieldID2, value >> duoSecondValueShift);

} else {

// Decode SingleWide word.

diff.set<singleValueBits>(static_cast<FieldID>(firstFieldIDBits), value);

}

++currentInfo;

value = currentInfo->value;

}

// Decode Basic word.

// We check the bounds against m_endExtensionInfo here because the Basic word may be in

// the extensions section.

ASSERT(currentInfo < m_endExtensionInfo);

diff.instPC += value >> instPCShift;

currentInstPC += diff.instPC;

IterationStatus status = IterationStatus::Continue;

// We want to find the entry whose InstPC is below the targetInstPC but not to exceed it.

// This means by necessity, we must always decode the next one above it before we

// know that we're done. If the current decode exceeds the target, then we need to

// abort immediately and not commit any changes to m_entry.

//

// The only exception to this is that we need to at least decode 1 entry before

// calling it quits. This only applies to opcodes at the start of the function before

// the first ExpressionInfo entry. Our historical convention is to map those to the

// first entry. The m_hasDecodedFirstEntry flag helps us achieve this.

if (targetInstPC && m_hasDecodedFirstEntry && currentInstPC > targetInstPC.value()) {

// We're done because we have reached our targetInstPC.

status = IterationStatus::Done;

} else {

m_hasDecodedFirstEntry = true;

if (hasAbsInstPC)

m_entry.reset();

m_entry.instPC = currentInstPC;

diff.divot += cast<int, divotBits>((value >> divotShift) - divotBias);

m_entry.divot += diff.divot;

// Unlike other values, startOffset and endOffset are always relative

// to the divot. Hence, they are never cummulative relative to the last expression

// info entry.

static constexpr unsigned startMask = (1 << startBits) - 1;

diff.start += (value >> startShift) & startMask;

m_entry.startOffset = diff.start; // Not cummulative.

static constexpr unsigned endMask = (1 << endBits) - 1;

diff.end += (value >> endShift) & endMask;

m_entry.endOffset = diff.end; // Not cummulative.

}

if (savedInfo) {

// We got here because we are terminating an Extension with a Basic word.

// So, we have to restore currentInfo for the next Entry.

currentInfo = savedInfo;

}

m_nextInfo = ++currentInfo; // This is where the next Entry to decode will start.

return status;

}

std::unique_ptr<ExpressionInfo> ExpressionInfo::createUninitialized(unsigned numberOfChapters, unsigned numberOfEncodedInfo, unsigned numberOfEncodedInfoExtensions)

}

ExpressionInfo::ExpressionInfo(unsigned numberOfChapters, unsigned numberOfEncodedInfo, unsigned numberOfEncodedInfoExtensions)

}

ExpressionInfo::ExpressionInfo(Vector<Chapter>&& chapters, Vector<EncodedInfo>&& encodedInfo, unsigned numberOfEncodedInfoExtensions)

}

size_t ExpressionInfo::byteSize() const

{

return totalSizeInBytes(m_numberOfChapters, m_numberOfEncodedInfo, m_numberOfEncodedInfoExtensions);

}

auto ExpressionInfo::findChapterEncodedInfoJustBelow(InstPC instPC) const -> EncodedInfo*

}

auto ExpressionInfo::entryForInstPC(const ConcurrentJSLocker&, InstPC instPC) -> Entry

}

auto ExpressionInfo::decodeEntryForInstPC(InstPC instPC) -> Entry

}

template<unsigned bitCount>

void ExpressionInfo::print(PrintStream& out, FieldID fieldID, unsigned value)

};

void ExpressionInfo::dumpEncodedInfo(ExpressionInfo::EncodedInfo* start, ExpressionInfo::EncodedInfo* end)

}

} // namespace JSC