BytecodeBasicBlock.cpp [plain text]
#include "config.h"
#include "BytecodeBasicBlock.h"
#include "CodeBlock.h"
#include "PreciseJumpTargets.h"
#include "UnlinkedCodeBlockGenerator.h"
namespace JSC {
DEFINE_ALLOCATOR_WITH_HEAP_IDENTIFIER(BytecodeBasicBlock);
BytecodeBasicBlock::BytecodeBasicBlock(const InstructionStream::Ref& instruction, unsigned blockIndex)
: m_leaderOffset(instruction.offset())
, m_totalLength(0)
, m_index(blockIndex)
{
addLength(instruction->size());
}
BytecodeBasicBlock::BytecodeBasicBlock(BytecodeBasicBlock::SpecialBlockType blockType, unsigned blockIndex)
: m_leaderOffset(blockType == BytecodeBasicBlock::EntryBlock ? 0 : UINT_MAX)
, m_totalLength(blockType == BytecodeBasicBlock::EntryBlock ? 0 : UINT_MAX)
, m_index(blockIndex)
{
}
void BytecodeBasicBlock::addLength(unsigned bytecodeLength)
{
m_delta.append(bytecodeLength);
m_totalLength += bytecodeLength;
}
void BytecodeBasicBlock::shrinkToFit()
{
m_delta.shrinkToFit();
m_successors.shrinkToFit();
}
static bool isJumpTarget(OpcodeID opcodeID, const Vector<InstructionStream::Offset, 32>& jumpTargets, unsigned bytecodeOffset)
{
if (opcodeID == op_catch)
return true;
return std::binary_search(jumpTargets.begin(), jumpTargets.end(), bytecodeOffset);
}
template<typename Block>
auto BytecodeBasicBlock::computeImpl(Block* codeBlock, const InstructionStream& instructions) -> BasicBlockVector
{
BasicBlockVector basicBlocks;
Vector<InstructionStream::Offset, 32> jumpTargets;
computePreciseJumpTargets(codeBlock, instructions, jumpTargets);
auto linkBlocks = [&] (BytecodeBasicBlock& from, BytecodeBasicBlock& to) {
from.addSuccessor(to);
};
{
basicBlocks.reserveCapacity(jumpTargets.size() + 2);
{
basicBlocks.constructAndAppend(BytecodeBasicBlock::EntryBlock, basicBlocks.size());
basicBlocks.constructAndAppend(BytecodeBasicBlock::EntryBlock, basicBlocks.size());
linkBlocks(basicBlocks[0], basicBlocks[1]);
}
BytecodeBasicBlock* current = &basicBlocks.last();
auto appendBlock = [&] (const InstructionStream::Ref& instruction) -> BytecodeBasicBlock* {
basicBlocks.constructAndAppend(instruction, basicBlocks.size());
return &basicBlocks.last();
};
bool nextInstructionIsLeader = false;
for (const auto& instruction : instructions) {
auto bytecodeOffset = instruction.offset();
OpcodeID opcodeID = instruction->opcodeID();
bool createdBlock = false;
if (nextInstructionIsLeader || isJumpTarget(opcodeID, jumpTargets, bytecodeOffset)) {
current = appendBlock(instruction);
createdBlock = true;
nextInstructionIsLeader = false;
}
if (isBranch(opcodeID) || isTerminal(opcodeID) || isThrow(opcodeID))
nextInstructionIsLeader = true;
if (createdBlock)
continue;
current->addLength(instruction->size());
}
basicBlocks.constructAndAppend(BytecodeBasicBlock::ExitBlock, basicBlocks.size());
basicBlocks.shrinkToFit();
ASSERT(basicBlocks.last().isExitBlock());
}
for (unsigned i = 0; i < basicBlocks.size(); i++) {
BytecodeBasicBlock& block = basicBlocks[i];
if (block.isEntryBlock() || block.isExitBlock())
continue;
bool fallsThrough = true;
for (unsigned visitedLength = 0; visitedLength < block.totalLength();) {
InstructionStream::Ref instruction = instructions.at(block.leaderOffset() + visitedLength);
OpcodeID opcodeID = instruction->opcodeID();
visitedLength += instruction->size();
if (isTerminal(opcodeID)) {
ASSERT(instruction.offset() + instruction->size() == block.leaderOffset() + block.totalLength());
linkBlocks(block, basicBlocks.last());
fallsThrough = false;
break;
}
if (isThrow(opcodeID)) {
ASSERT(instruction.offset() + instruction->size() == block.leaderOffset() + block.totalLength());
auto* handler = codeBlock->handlerForBytecodeIndex(BytecodeIndex(instruction.offset()));
fallsThrough = false;
if (!handler) {
linkBlocks(block, basicBlocks.last());
break;
}
for (auto& otherBlock : basicBlocks) {
if (handler->target == otherBlock.leaderOffset()) {
linkBlocks(block, otherBlock);
break;
}
}
break;
}
if (isBranch(opcodeID)) {
ASSERT(instruction.offset() + instruction->size() == block.leaderOffset() + block.totalLength());
Vector<InstructionStream::Offset, 1> bytecodeOffsetsJumpedTo;
findJumpTargetsForInstruction(codeBlock, instruction, bytecodeOffsetsJumpedTo);
size_t numberOfJumpTargets = bytecodeOffsetsJumpedTo.size();
ASSERT(numberOfJumpTargets);
for (auto& otherBlock : basicBlocks) {
if (bytecodeOffsetsJumpedTo.contains(otherBlock.leaderOffset())) {
linkBlocks(block, otherBlock);
--numberOfJumpTargets;
if (!numberOfJumpTargets)
break;
}
}
if (isUnconditionalBranch(opcodeID))
fallsThrough = false;
break;
}
}
if (fallsThrough) {
ASSERT(i + 1 < basicBlocks.size());
BytecodeBasicBlock& nextBlock = basicBlocks[i + 1];
linkBlocks(block, nextBlock);
}
}
unsigned index = 0;
for (auto& basicBlock : basicBlocks) {
basicBlock.shrinkToFit();
ASSERT_UNUSED(index, basicBlock.index() == index++);
}
return basicBlocks;
}
auto BytecodeBasicBlock::compute(CodeBlock* codeBlock, const InstructionStream& instructions) -> BasicBlockVector
{
return computeImpl(codeBlock, instructions);
}
auto BytecodeBasicBlock::compute(UnlinkedCodeBlockGenerator* codeBlock, const InstructionStream& instructions) -> BasicBlockVector
{
return computeImpl(codeBlock, instructions);
}
}