Skip to content

Commit 7e143ba

Browse files
ConstellationConstellation
committed
Unreviewed, relanding 297160@main
https://bugs.webkit.org/show_bug.cgi?id=295759 rdar://problem/155581946 We may have duped keys for the list style switch. In jump-table switch, we only record the first-come one (which is aligned to the semantics). We should do the same for the list style switch too. * Source/JavaScriptCore/bytecode/BytecodeDumper.cpp: (JSC::CodeBlockBytecodeDumper<Block>::dumpSwitchJumpTables): * Source/JavaScriptCore/bytecode/PreciseJumpTargetsInlines.h: * Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h: (JSC::UnlinkedSimpleJumpTable::isList const): * Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp: (JSC::BytecodeGenerator::beginSwitch): (JSC::BytecodeGenerator::endSwitch): (JSC::keyForImmediateSwitch): Deleted. (JSC::keyForCharacterSwitch): Deleted. (JSC::prepareJumpTableForSwitch): Deleted. (JSC::prepareJumpTableForStringSwitch): Deleted. * Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h: * Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp: (JSC::CaseBlockNode::tryTableSwitch): (JSC::CaseBlockNode::emitBytecodeForBlock): (JSC::length): Deleted. * Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp: (JSC::DFG::ByteCodeParser::parseBlock): * Source/JavaScriptCore/dfg/DFGMayExit.cpp: * Source/JavaScriptCore/dfg/DFGOperations.cpp: * Source/JavaScriptCore/dfg/DFGOperations.h: * Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp: * Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp: (JSC::FTL::DFG::LowerDFGToB3::compileCompareStrictEq): * Source/JavaScriptCore/jit/JIT.cpp: (JSC::JIT::link): * Source/JavaScriptCore/jit/JITOpcodes.cpp: (JSC::JIT::emit_op_switch_imm): (JSC::JIT::emit_op_switch_char): * Source/JavaScriptCore/jit/JITOperations.cpp: (JSC::JSC_DEFINE_JIT_OPERATION): * Source/JavaScriptCore/jit/JITOperations.h: * Source/JavaScriptCore/llint/LLIntSlowPaths.cpp: (JSC::LLInt::LLINT_SLOW_PATH_DECL): * Source/JavaScriptCore/llint/LowLevelInterpreter32_64.asm: * Source/JavaScriptCore/llint/LowLevelInterpreter64.asm: * Source/JavaScriptCore/parser/Nodes.h: Canonical link: https://commits.webkit.org/297251@main
1 parent 0a7ce00 commit 7e143ba

20 files changed

Lines changed: 403 additions & 269 deletions

‎Source/JavaScriptCore/bytecode/BytecodeDumper.cpp‎

Lines changed: 12 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -190,10 +190,18 @@ void CodeBlockBytecodeDumper<Block>::dumpSwitchJumpTables()
190190
const auto& unlinkedTable = this->block()->unlinkedSwitchJumpTable(i);
191191
int entry = 0;
192192
auto end = unlinkedTable.m_branchOffsets.end();
193-
for (auto iter = unlinkedTable.m_branchOffsets.begin(); iter != end; ++iter, ++entry) {
194-
if (!*iter)
195-
continue;
196-
this->m_out.printf("\t\t%4d => %04d\n", entry + unlinkedTable.m_min, *iter);
193+
if (unlinkedTable.isList()) {
194+
for (auto iter = unlinkedTable.m_branchOffsets.begin(); iter != end;) {
195+
int32_t value = *iter++;
196+
int32_t>
197+
this->m_out.printf("\t\t%4d => %04d\n", value, target);
198+
}
199+
} else {
200+
for (auto iter = unlinkedTable.m_branchOffsets.begin(); iter != end; ++iter, ++entry) {
201+
if (!*iter)
202+
continue;
203+
this->m_out.printf("\t\t%4d => %04d\n", entry + unlinkedTable.m_min, *iter);
204+
}
197205
}
198206
this->m_out.printf("\t\tdefault => %04d\n", unlinkedTable.m_defaultOffset);
199207
this->m_out.printf(" }\n");

‎Source/JavaScriptCore/bytecode/PreciseJumpTargetsInlines.h‎

Lines changed: 14 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -63,16 +63,26 @@ namespace JSC {
6363
case op_switch_imm: { \
6464
auto bytecode = instruction->as<OpSwitchImm>(); \
6565
auto& table = codeBlock->unlinkedSwitchJumpTable(bytecode.m_tableIndex); \
66-
for (unsigned i = table.m_branchOffsets.size(); i--;) \
67-
SWITCH_CASE(table.m_branchOffsets[i]); \
66+
if (table.isList()) { \
67+
for (unsigned i = 0; i < table.m_branchOffsets.size(); i += 2) \
68+
SWITCH_CASE(table.m_branchOffsets[i + 1]); \
69+
} else { \
70+
for (unsigned i = table.m_branchOffsets.size(); i--;) \
71+
SWITCH_CASE(table.m_branchOffsets[i]); \
72+
} \
6873
SWITCH_CASE(table.m_defaultOffset); \
6974
break; \
7075
} \
7176
case op_switch_char: { \
7277
auto bytecode = instruction->as<OpSwitchChar>(); \
7378
auto& table = codeBlock->unlinkedSwitchJumpTable(bytecode.m_tableIndex); \
74-
for (unsigned i = table.m_branchOffsets.size(); i--;) \
75-
SWITCH_CASE(table.m_branchOffsets[i]); \
79+
if (table.isList()) { \
80+
for (unsigned i = 0; i < table.m_branchOffsets.size(); i += 2) \
81+
SWITCH_CASE(table.m_branchOffsets[i + 1]); \
82+
} else { \
83+
for (unsigned i = table.m_branchOffsets.size(); i--;) \
84+
SWITCH_CASE(table.m_branchOffsets[i]); \
85+
} \
7686
SWITCH_CASE(table.m_defaultOffset); \
7787
break; \
7888
} \

‎Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -133,6 +133,9 @@ struct UnlinkedSimpleJumpTable {
133133
}
134134

135135
int32_t defaultOffset() const { return m_defaultOffset; }
136+
137+
// Returns true if this is a list-style jump table (key-offset pairs), used for sparse switches.
138+
bool isList() const { return m_min == INT32_MAX; }
136139
};
137140

138141
class UnlinkedCodeBlock : public JSCell {

‎Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp‎

Lines changed: 114 additions & 86 deletions
Original file line numberDiff line numberDiff line change
@@ -4331,133 +4331,161 @@ void BytecodeGenerator::emitPopCatchScope(VariableEnvironment& environment)
43314331
void BytecodeGenerator::beginSwitch(RegisterID* scrutineeRegister, SwitchInfo::SwitchType type)
43324332
{
43334333
switch (type) {
4334-
case SwitchInfo::SwitchImmediate: {
4334+
case SwitchInfo::SwitchType::Immediate:
4335+
case SwitchInfo::SwitchType::ImmediateList: {
43354336
size_t tableIndex = m_codeBlock->numberOfUnlinkedSwitchJumpTables();
43364337
m_codeBlock->addUnlinkedSwitchJumpTable();
43374338
OpSwitchImm::emit(this, tableIndex, scrutineeRegister);
43384339
break;
43394340
}
4340-
case SwitchInfo::SwitchCharacter: {
4341+
case SwitchInfo::SwitchType::Character:
4342+
case SwitchInfo::SwitchType::CharacterList: {
43414343
size_t tableIndex = m_codeBlock->numberOfUnlinkedSwitchJumpTables();
43424344
m_codeBlock->addUnlinkedSwitchJumpTable();
43434345
OpSwitchChar::emit(this, tableIndex, scrutineeRegister);
43444346
break;
43454347
}
4346-
case SwitchInfo::SwitchString: {
4348+
case SwitchInfo::SwitchType::String: {
43474349
size_t tableIndex = m_codeBlock->numberOfUnlinkedStringSwitchJumpTables();
43484350
m_codeBlock->addUnlinkedStringSwitchJumpTable();
43494351
OpSwitchString::emit(this, tableIndex, scrutineeRegister);
43504352
break;
43514353
}
4352-
default:
4354+
case SwitchInfo::SwitchType::None:
43534355
RELEASE_ASSERT_NOT_REACHED();
43544356
}
43554357

43564358
SwitchInfo info = { m_lastInstruction.offset(), type };
43574359
m_switchContextStack.append(info);
43584360
}
43594361

4360-
static int32_t keyForImmediateSwitch(ExpressionNode* node, int32_t min, int32_t max)
4362+
void BytecodeGenerator::endSwitch(const Vector<Ref<Label>, 8>& labels, ExpressionNode** nodes, Label& defaultLabel, int32_t min, int32_t max)
43614363
{
4362-
UNUSED_PARAM(max);
4363-
ASSERT(node->isNumber());
4364-
double value = static_cast<NumberNode*>(node)->value();
4365-
int32_t key = static_cast<int32_t>(value);
4366-
ASSERT(key == value);
4367-
ASSERT(key >= min);
4368-
ASSERT(key <= max);
4369-
return key - min;
4370-
}
4364+
SwitchInfo switchInfo = m_switchContextStack.last();
4365+
m_switchContextStack.removeLast();
43714366

4372-
static int32_t keyForCharacterSwitch(ExpressionNode* node, int32_t min, int32_t max)
4373-
{
4374-
UNUSED_PARAM(max);
4375-
ASSERT(node->isString());
4376-
StringImpl* clause = static_cast<StringNode*>(node)->value().impl();
4377-
ASSERT(clause->length() == 1);
4378-
4379-
int32_t key = (*clause)[0];
4380-
ASSERT(key >= min);
4381-
ASSERT(key <= max);
4382-
return key - min;
4383-
}
4367+
auto handleSwitch = [&](auto bytecode) {
4368+
UnlinkedSimpleJumpTable& jumpTable = m_codeBlock->unlinkedSwitchJumpTable(bytecode.m_tableIndex);
4369+
jumpTable.m_min = min;
4370+
jumpTable.m_branchOffsets = FixedVector<int32_t>(max - min + 1);
4371+
std::fill(jumpTable.m_branchOffsets.begin(), jumpTable.m_branchOffsets.end(), 0);
4372+
for (uint32_t i = 0; i < labels.size(); ++i) {
4373+
// We're emitting this after the clause labels should have been fixed, so
4374+
// the labels should not be "forward" references
4375+
ASSERT(!labels[i]->isForward());
4376+
int32_t key = 0;
4377+
if (switchInfo.switchType == SwitchInfo::SwitchType::Immediate) {
4378+
ASSERT(nodes[i]->isNumber());
4379+
double value = static_cast<NumberNode*>(nodes[i])->value();
4380+
int32_t extracted = static_cast<int32_t>(value);
4381+
ASSERT(extracted == value);
4382+
ASSERT(extracted >= min);
4383+
ASSERT(extracted <= max);
4384+
key = extracted - min;
4385+
} else {
4386+
ASSERT(nodes[i]->isString());
4387+
StringImpl* clause = static_cast<StringNode*>(nodes[i])->value().impl();
4388+
ASSERT(clause->length() == 1);
4389+
int32_t extracted = (*clause)[0];
4390+
ASSERT(extracted >= min);
4391+
ASSERT(extracted <= max);
4392+
key = extracted - min;
4393+
}
4394+
jumpTable.add(key, labels[i]->bind(switchInfo.bytecodeOffset));
4395+
}
4396+
ASSERT(!defaultLabel.isForward());
4397+
jumpTable.m_defaultOffset = defaultLabel.bind(switchInfo.bytecodeOffset);
4398+
};
43844399

4385-
static void prepareJumpTableForSwitch(
4386-
UnlinkedSimpleJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount,
4387-
const Vector<Ref<Label>, 8>& labels, Label& defaultLabel, ExpressionNode** nodes, int32_t min, int32_t max,
4388-
int32_t (*keyGetter)(ExpressionNode*, int32_t min, int32_t max))
4389-
{
4390-
jumpTable.m_min = min;
4391-
jumpTable.m_branchOffsets = FixedVector<int32_t>(max - min + 1);
4392-
std::fill(jumpTable.m_branchOffsets.begin(), jumpTable.m_branchOffsets.end(), 0);
4393-
for (uint32_t i = 0; i < clauseCount; ++i) {
4394-
// We're emitting this after the clause labels should have been fixed, so
4395-
// the labels should not be "forward" references
4396-
ASSERT(!labels[i]->isForward());
4397-
jumpTable.add(keyGetter(nodes[i], min, max), labels[i]->bind(switchAddress));
4398-
}
4399-
ASSERT(!defaultLabel.isForward());
4400-
jumpTable.m_defaultOffset = defaultLabel.bind(switchAddress);
4401-
}
4400+
auto handleSwitchList = [&](auto bytecode) {
4401+
UnlinkedSimpleJumpTable& jumpTable = m_codeBlock->unlinkedSwitchJumpTable(bytecode.m_tableIndex);
4402+
jumpTable.m_min = INT32_MAX;
4403+
4404+
Vector<int32_t> branchOffsets;
4405+
branchOffsets.reserveInitialCapacity(labels.size() * 2);
4406+
UncheckedKeyHashSet<GenericHashKey<int32_t>> alreadyHandled;
4407+
4408+
for (uint32_t i = 0; i < labels.size(); ++i) {
4409+
// We're emitting this after the clause labels should have been fixed, so
4410+
// the labels should not be "forward" references
4411+
ASSERT(!labels[i]->isForward());
4412+
int32_t key = 0;
4413+
if (switchInfo.switchType == SwitchInfo::SwitchType::ImmediateList) {
4414+
double value = static_cast<NumberNode*>(nodes[i])->value();
4415+
key = static_cast<int32_t>(value);
4416+
} else {
4417+
StringImpl* clause = static_cast<StringNode*>(nodes[i])->value().impl();
4418+
ASSERT(clause->length() == 1);
4419+
key = (*clause)[0];
4420+
}
44024421

4403-
static void prepareJumpTableForStringSwitch(UnlinkedStringJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, const Vector<Ref<Label>, 8>& labels, Label& defaultLabel, ExpressionNode** nodes)
4404-
{
4405-
for (uint32_t i = 0; i < clauseCount; ++i) {
4406-
// We're emitting this after the clause labels should have been fixed, so
4407-
// the labels should not be "forward" references
4408-
ASSERT(!labels[i]->isForward());
4409-
4410-
ASSERT(nodes[i]->isString());
4411-
UniquedStringImpl* clause = static_cast<StringNode*>(nodes[i])->value().impl();
4412-
ASSERT(clause->isAtom());
4413-
auto result = jumpTable.m_offsetTable.add(clause, UnlinkedStringJumpTable::OffsetLocation { labels[i]->bind(switchAddress), 0 });
4414-
if (result.isNewEntry) {
4415-
result.iterator->value.m_indexInTable = jumpTable.m_offsetTable.size() - 1;
4416-
jumpTable.m_minLength = std::min(jumpTable.m_minLength, clause->length());
4417-
jumpTable.m_maxLength = std::max(jumpTable.m_maxLength, clause->length());
4422+
// There is a chance that we may list up duplicate keys. In this case, the first one wins.
4423+
if (!alreadyHandled.add(key).isNewEntry)
4424+
continue;
4425+
4426+
branchOffsets.append(key);
4427+
branchOffsets.append(labels[i]->bind(switchInfo.bytecodeOffset));
44184428
}
4419-
}
4420-
ASSERT(!defaultLabel.isForward());
4421-
jumpTable.m_defaultOffset = defaultLabel.bind(switchAddress);
44224429

4423-
if (jumpTable.m_offsetTable.isEmpty()) {
4424-
jumpTable.m_minLength = 0;
4425-
jumpTable.m_maxLength = 0;
4426-
}
4427-
}
4430+
ASSERT(!defaultLabel.isForward());
4431+
jumpTable.m_branchOffsets = WTFMove(branchOffsets);
4432+
jumpTable.m_defaultOffset = defaultLabel.bind(switchInfo.bytecodeOffset);
4433+
};
44284434

4429-
void BytecodeGenerator::endSwitch(uint32_t clauseCount, const Vector<Ref<Label>, 8>& labels, ExpressionNode** nodes, Label& defaultLabel, int32_t min, int32_t max)
4430-
{
4431-
SwitchInfo switchInfo = m_switchContextStack.last();
4432-
m_switchContextStack.removeLast();
4435+
auto handleStringSwitch = [&](auto bytecode) {
4436+
UnlinkedStringJumpTable& jumpTable = m_codeBlock->unlinkedStringSwitchJumpTable(bytecode.m_tableIndex);
4437+
for (uint32_t i = 0; i < labels.size(); ++i) {
4438+
// We're emitting this after the clause labels should have been fixed, so
4439+
// the labels should not be "forward" references
4440+
ASSERT(!labels[i]->isForward());
4441+
4442+
ASSERT(nodes[i]->isString());
4443+
UniquedStringImpl* clause = static_cast<StringNode*>(nodes[i])->value().impl();
4444+
ASSERT(clause->isAtom());
4445+
auto result = jumpTable.m_offsetTable.add(clause, UnlinkedStringJumpTable::OffsetLocation { labels[i]->bind(switchInfo.bytecodeOffset), 0 });
4446+
if (result.isNewEntry) {
4447+
result.iterator->value.m_indexInTable = jumpTable.m_offsetTable.size() - 1;
4448+
jumpTable.m_minLength = std::min(jumpTable.m_minLength, clause->length());
4449+
jumpTable.m_maxLength = std::max(jumpTable.m_maxLength, clause->length());
4450+
}
4451+
}
4452+
ASSERT(!defaultLabel.isForward());
4453+
jumpTable.m_defaultOffset = defaultLabel.bind(switchInfo.bytecodeOffset);
44334454

4434-
auto handleSwitch = [&](auto bytecode) {
4435-
UnlinkedSimpleJumpTable& jumpTable = m_codeBlock->unlinkedSwitchJumpTable(bytecode.m_tableIndex);
4436-
prepareJumpTableForSwitch(
4437-
jumpTable, switchInfo.bytecodeOffset, clauseCount, labels, defaultLabel, nodes, min, max,
4438-
switchInfo.switchType == SwitchInfo::SwitchImmediate
4439-
? keyForImmediateSwitch
4440-
: keyForCharacterSwitch);
4455+
if (jumpTable.m_offsetTable.isEmpty()) {
4456+
jumpTable.m_minLength = 0;
4457+
jumpTable.m_maxLength = 0;
4458+
}
44414459
};
4442-
4460+
44434461
auto ref = m_writer.ref(switchInfo.bytecodeOffset);
44444462
switch (switchInfo.switchType) {
4445-
case SwitchInfo::SwitchImmediate: {
4463+
case SwitchInfo::SwitchType::Immediate: {
44464464
handleSwitch(ref->as<OpSwitchImm>());
44474465
break;
44484466
}
4449-
case SwitchInfo::SwitchCharacter: {
4467+
4468+
case SwitchInfo::SwitchType::ImmediateList: {
4469+
handleSwitchList(ref->as<OpSwitchImm>());
4470+
break;
4471+
}
4472+
4473+
case SwitchInfo::SwitchType::Character: {
44504474
handleSwitch(ref->as<OpSwitchChar>());
44514475
break;
44524476
}
4453-
4454-
case SwitchInfo::SwitchString: {
4455-
UnlinkedStringJumpTable& jumpTable = m_codeBlock->unlinkedStringSwitchJumpTable(ref->as<OpSwitchString>().m_tableIndex);
4456-
prepareJumpTableForStringSwitch(jumpTable, switchInfo.bytecodeOffset, clauseCount, labels, defaultLabel, nodes);
4477+
4478+
case SwitchInfo::SwitchType::CharacterList: {
4479+
handleSwitchList(ref->as<OpSwitchChar>());
44574480
break;
44584481
}
4459-
4460-
default:
4482+
4483+
case SwitchInfo::SwitchType::String: {
4484+
handleStringSwitch(ref->as<OpSwitchString>());
4485+
break;
4486+
}
4487+
4488+
case SwitchInfo::SwitchType::None:
44614489
RELEASE_ASSERT_NOT_REACHED();
44624490
break;
44634491
}

‎Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1052,7 +1052,7 @@ namespace JSC {
10521052
LabelScope* continueTarget(const Identifier&);
10531053

10541054
void beginSwitch(RegisterID*, SwitchInfo::SwitchType);
1055-
void endSwitch(uint32_t clauseCount, const Vector<Ref<Label>, 8>&, ExpressionNode**, Label& defaultLabel, int32_t min, int32_t range);
1055+
void endSwitch(const Vector<Ref<Label>, 8>&, ExpressionNode**, Label& defaultLabel, int32_t min, int32_t range);
10561056

10571057
void emitYieldPoint(RegisterID*, JSAsyncGenerator::AsyncGeneratorSuspendReason);
10581058

0 commit comments

Comments
 (0)