diff options
-rw-r--r-- | js/src/frontend/BytecodeEmitter.cpp | 336 | ||||
-rw-r--r-- | js/src/frontend/BytecodeEmitter.h | 2 | ||||
-rw-r--r-- | js/src/frontend/ParseNode.h | 13 | ||||
-rw-r--r-- | js/src/frontend/SwitchEmitter.cpp | 424 | ||||
-rw-r--r-- | js/src/frontend/SwitchEmitter.h | 470 | ||||
-rw-r--r-- | js/src/moz.build | 1 |
6 files changed, 978 insertions, 268 deletions
diff --git a/js/src/frontend/BytecodeEmitter.cpp b/js/src/frontend/BytecodeEmitter.cpp index 8a67a50655..d1c1082ad7 100644 --- a/js/src/frontend/BytecodeEmitter.cpp +++ b/js/src/frontend/BytecodeEmitter.cpp @@ -37,6 +37,7 @@ #include "frontend/NameOpEmitter.h" #include "frontend/Parser.h" #include "frontend/PropOpEmitter.h" +#include "frontend/SwitchEmitter.h" #include "frontend/TDZCheckCache.h" #include "frontend/TokenStream.h" #include "frontend/TryEmitter.h" @@ -1629,6 +1630,19 @@ BytecodeEmitter::reportError(ParseNode* pn, unsigned errorNumber, ...) } bool +BytecodeEmitter::reportError(const mozilla::Maybe<uint32_t>& maybeOffset, unsigned errorNumber, ...) +{ + uint32_t offset = maybeOffset ? *maybeOffset : tokenStream().currentToken().pos.begin; + + va_list args; + va_start(args, errorNumber); + bool result = tokenStream().reportCompileErrorNumberVA(nullptr, offset, JSREPORT_ERROR, + errorNumber, args); + va_end(args); + return result; +} + +bool BytecodeEmitter::reportExtraWarning(ParseNode* pn, unsigned errorNumber, ...) { TokenPos pos = pn ? pn->pn_pos : tokenStream().currentToken().pos; @@ -1642,6 +1656,19 @@ BytecodeEmitter::reportExtraWarning(ParseNode* pn, unsigned errorNumber, ...) } bool +BytecodeEmitter::reportExtraWarning(const mozilla::Maybe<uint32_t>& maybeOffset, unsigned errorNumber, ...) +{ + uint32_t offset = maybeOffset ? *maybeOffset : tokenStream().currentToken().pos.begin; + + va_list args; + va_start(args, errorNumber); + bool result = tokenStream().reportExtraWarningErrorNumberVA(nullptr, offset, + errorNumber, args); + va_end(args); + return result; +} + +bool BytecodeEmitter::reportStrictModeError(ParseNode* pn, unsigned errorNumber, ...) { TokenPos pos = pn ? pn->pn_pos : tokenStream().currentToken().pos; @@ -2030,33 +2057,27 @@ BytecodeEmitter::emitNumberOp(double dval) MOZ_NEVER_INLINE bool BytecodeEmitter::emitSwitch(ParseNode* pn) { - ParseNode* cases = pn->pn_right; - MOZ_ASSERT(cases->isKind(PNK_LEXICALSCOPE) || cases->isKind(PNK_STATEMENTLIST)); + ParseNode* lexical = pn->pn_right; + MOZ_ASSERT(lexical->isKind(PNK_LEXICALSCOPE)); + ParseNode* cases = lexical->scopeBody(); + MOZ_ASSERT(cases->isKind(PNK_STATEMENTLIST)); - // Emit code for the discriminant. + SwitchEmitter se(this); + if (!se.emitDiscriminant(Some(pn->pn_pos.begin))) + return false; if (!emitTree(pn->pn_left)) return false; // Enter the scope before pushing the switch BreakableControl since all // breaks are under this scope. - Maybe<TDZCheckCache> tdzCache; - Maybe<EmitterScope> emitterScope; - if (cases->isKind(PNK_LEXICALSCOPE)) { - if (!cases->isEmptyScope()) { - tdzCache.emplace(this); - emitterScope.emplace(this); - if (!emitterScope->enterLexical(this, ScopeKind::Lexical, cases->scopeBindings())) - return false; - } - - // Advance |cases| to refer to the switch case list. - cases = cases->scopeBody(); + if (!lexical->isEmptyScope()) { + if (!se.emitLexical(lexical->scopeBindings())) + return false; // A switch statement may contain hoisted functions inside its // cases. The PNX_FUNCDEFS flag is propagated from the STATEMENTLIST // bodies of the cases to the case list. if (cases->pn_xflags & PNX_FUNCDEFS) { - MOZ_ASSERT(emitterScope); for (ParseNode* caseNode = cases->pn_head; caseNode; caseNode = caseNode->pn_next) { if (caseNode->pn_right->pn_xflags & PNX_FUNCDEFS) { if (!emitHoistedFunctionsInList(caseNode->pn_right)) @@ -2064,302 +2085,103 @@ BytecodeEmitter::emitSwitch(ParseNode* pn) } } } + } else { + MOZ_ASSERT(!(cases->pn_xflags & PNX_FUNCDEFS)); } - // After entering the scope, push the switch control. - BreakableControl controlInfo(this, StatementKind::Switch); - - ptrdiff_t top = offset(); - - // Switch bytecodes run from here till end of final case. + SwitchEmitter::TableGenerator tableGen(this); uint32_t caseCount = cases->pn_count; - if (caseCount > JS_BIT(16)) { - parser->tokenStream.reportError(JSMSG_TOO_MANY_CASES); - return false; - } - - // Try for most optimal, fall back if not dense ints. - JSOp switchOp = JSOP_TABLESWITCH; - uint32_t tableLength = 0; - int32_t low, high; - bool hasDefault = false; CaseClause* firstCase = cases->pn_head ? &cases->pn_head->as<CaseClause>() : nullptr; - if (caseCount == 0 || - (caseCount == 1 && (hasDefault = firstCase->isDefault()))) - { + if (caseCount == 0) { + tableGen.finish(0); + } else if (caseCount == 1 && firstCase->isDefault()) { caseCount = 0; - low = 0; - high = -1; + tableGen.finish(0); } else { - Vector<jsbitmap, 128, SystemAllocPolicy> intmap; - int32_t intmapBitLength = 0; - - low = JSVAL_INT_MAX; - high = JSVAL_INT_MIN; - for (CaseClause* caseNode = firstCase; caseNode; caseNode = caseNode->next()) { if (caseNode->isDefault()) { - hasDefault = true; caseCount--; // one of the "cases" was the default continue; } - if (switchOp == JSOP_CONDSWITCH) + if (tableGen.isInvalid()) continue; - MOZ_ASSERT(switchOp == JSOP_TABLESWITCH); - ParseNode* caseValue = caseNode->caseExpression(); if (caseValue->getKind() != PNK_NUMBER) { - switchOp = JSOP_CONDSWITCH; + tableGen.setInvalid(); continue; } int32_t i; if (!NumberIsInt32(caseValue->pn_dval, &i)) { - switchOp = JSOP_CONDSWITCH; + tableGen.setInvalid(); continue; } - if (unsigned(i + int(JS_BIT(15))) >= unsigned(JS_BIT(16))) { - switchOp = JSOP_CONDSWITCH; - continue; - } - if (i < low) - low = i; - if (i > high) - high = i; - - // Check for duplicates, which require a JSOP_CONDSWITCH. - // We bias i by 65536 if it's negative, and hope that's a rare - // case (because it requires a malloc'd bitmap). - if (i < 0) - i += JS_BIT(16); - if (i >= intmapBitLength) { - size_t newLength = (i / JS_BITMAP_NBITS) + 1; - if (!intmap.resize(newLength)) - return false; - intmapBitLength = newLength * JS_BITMAP_NBITS; - } - if (JS_TEST_BIT(intmap, i)) { - switchOp = JSOP_CONDSWITCH; - continue; - } - JS_SET_BIT(intmap, i); + if (!tableGen.addNumber(i)) + return false; } - // Compute table length and select condswitch instead if overlarge or - // more than half-sparse. - if (switchOp == JSOP_TABLESWITCH) { - tableLength = uint32_t(high - low + 1); - if (tableLength >= JS_BIT(16) || tableLength > 2 * caseCount) - switchOp = JSOP_CONDSWITCH; - } + tableGen.finish(caseCount); } + if (!se.validateCaseCount(caseCount)) + return false; - // The note has one or two offsets: first tells total switch code length; - // second (if condswitch) tells offset to first JSOP_CASE. - unsigned noteIndex; - size_t switchSize; - if (switchOp == JSOP_CONDSWITCH) { - // 0 bytes of immediate for unoptimized switch. - switchSize = 0; - if (!newSrcNote3(SRC_CONDSWITCH, 0, 0, ¬eIndex)) + bool isTableSwitch = tableGen.isValid(); + if (isTableSwitch) { + if (!se.emitTable(tableGen)) return false; } else { - MOZ_ASSERT(switchOp == JSOP_TABLESWITCH); - - // 3 offsets (len, low, high) before the table, 1 per entry. - switchSize = size_t(JUMP_OFFSET_LEN * (3 + tableLength)); - if (!newSrcNote2(SRC_TABLESWITCH, 0, ¬eIndex)) + if (!se.emitCond()) return false; - } - - // Emit switchOp followed by switchSize bytes of jump or lookup table. - MOZ_ASSERT(top == offset()); - if (!emitN(switchOp, switchSize)) - return false; - - Vector<CaseClause*, 32, SystemAllocPolicy> table; - - JumpList condSwitchDefaultOff; - if (switchOp == JSOP_CONDSWITCH) { - unsigned caseNoteIndex; - bool beforeCases = true; - ptrdiff_t lastCaseOffset = -1; - - // The case conditions need their own TDZ cache since they might not - // all execute. - TDZCheckCache tdzCache(this); // Emit code for evaluating cases and jumping to case statements. for (CaseClause* caseNode = firstCase; caseNode; caseNode = caseNode->next()) { + if (caseNode->isDefault()) + continue; + ParseNode* caseValue = caseNode->caseExpression(); // If the expression is a literal, suppress line number emission so // that debugging works more naturally. - if (caseValue) { - if (!emitTree(caseValue, ValueUsage::WantValue, - caseValue->isLiteral() ? SUPPRESS_LINENOTE : EMIT_LINENOTE)) - { - return false; - } - } - - if (!beforeCases) { - // prevCase is the previous JSOP_CASE's bytecode offset. - if (!setSrcNoteOffset(caseNoteIndex, 0, offset() - lastCaseOffset)) - return false; - } - if (!caseValue) { - // This is the default clause. - continue; - } - - if (!newSrcNote2(SRC_NEXTCASE, 0, &caseNoteIndex)) - return false; - - // The case clauses are produced before any of the case body. The - // JumpList is saved on the parsed tree, then later restored and - // patched when generating the cases body. - JumpList caseJump; - if (!emitJump(JSOP_CASE, &caseJump)) + if (!emitTree(caseValue, ValueUsage::WantValue, + caseValue->isLiteral() ? SUPPRESS_LINENOTE : EMIT_LINENOTE)) + { return false; - caseNode->setOffset(caseJump.offset); - lastCaseOffset = caseJump.offset; - - if (beforeCases) { - // Switch note's second offset is to first JSOP_CASE. - unsigned noteCount = notes().length(); - if (!setSrcNoteOffset(noteIndex, 1, lastCaseOffset - top)) - return false; - unsigned noteCountDelta = notes().length() - noteCount; - if (noteCountDelta != 0) - caseNoteIndex += noteCountDelta; - beforeCases = false; } - } - - // If we didn't have an explicit default (which could fall in between - // cases, preventing us from fusing this setSrcNoteOffset with the call - // in the loop above), link the last case to the implicit default for - // the benefit of IonBuilder. - if (!hasDefault && - !beforeCases && - !setSrcNoteOffset(caseNoteIndex, 0, offset() - lastCaseOffset)) - { - return false; - } - - // Emit default even if no explicit default statement. - if (!emitJump(JSOP_DEFAULT, &condSwitchDefaultOff)) - return false; - } else { - MOZ_ASSERT(switchOp == JSOP_TABLESWITCH); - - // skip default offset. - jsbytecode* pc = code(top + JUMP_OFFSET_LEN); - - // Fill in switch bounds, which we know fit in 16-bit offsets. - SET_JUMP_OFFSET(pc, low); - pc += JUMP_OFFSET_LEN; - SET_JUMP_OFFSET(pc, high); - pc += JUMP_OFFSET_LEN; - - if (tableLength != 0) { - if (!table.growBy(tableLength)) + if (!se.emitCaseJump()) return false; - - for (CaseClause* caseNode = firstCase; caseNode; caseNode = caseNode->next()) { - if (ParseNode* caseValue = caseNode->caseExpression()) { - MOZ_ASSERT(caseValue->isKind(PNK_NUMBER)); - - int32_t i = int32_t(caseValue->pn_dval); - MOZ_ASSERT(double(i) == caseValue->pn_dval); - - i -= low; - MOZ_ASSERT(uint32_t(i) < tableLength); - MOZ_ASSERT(!table[i]); - table[i] = caseNode; - } - } } } - JumpTarget defaultOffset{ -1 }; - // Emit code for each case's statements. for (CaseClause* caseNode = firstCase; caseNode; caseNode = caseNode->next()) { - if (switchOp == JSOP_CONDSWITCH && !caseNode->isDefault()) { - // The case offset got saved in the caseNode structure after - // emitting the JSOP_CASE jump instruction above. - JumpList caseCond; - caseCond.offset = caseNode->offset(); - if (!emitJumpTargetAndPatch(caseCond)) + if (caseNode->isDefault()) { + if (!se.emitDefaultBody()) return false; - } - - JumpTarget here; - if (!emitJumpTarget(&here)) - return false; - if (caseNode->isDefault()) - defaultOffset = here; + } else { + if (isTableSwitch) { + ParseNode* caseValue = caseNode->caseExpression(); + MOZ_ASSERT(caseValue->isKind(PNK_NUMBER)); - // If this is emitted as a TABLESWITCH, we'll need to know this case's - // offset later when emitting the table. Store it in the node's - // pn_offset (giving the field a different meaning vs. how we used it - // on the immediately preceding line of code). - caseNode->setOffset(here.offset); + int32_t i = int32_t(caseValue->pn_dval); + MOZ_ASSERT(double(i) == caseValue->pn_dval); - TDZCheckCache tdzCache(this); + if (!se.emitCaseBody(i, tableGen)) + return false; + } else { + if (!se.emitCaseBody()) + return false; + } + } if (!emitTree(caseNode->statementList())) return false; } - if (!hasDefault) { - // If no default case, offset for default is to end of switch. - if (!emitJumpTarget(&defaultOffset)) - return false; - } - MOZ_ASSERT(defaultOffset.offset != -1); - - // Set the default offset (to end of switch if no default). - jsbytecode* pc; - if (switchOp == JSOP_CONDSWITCH) { - pc = nullptr; - patchJumpsToTarget(condSwitchDefaultOff, defaultOffset); - } else { - MOZ_ASSERT(switchOp == JSOP_TABLESWITCH); - pc = code(top); - SET_JUMP_OFFSET(pc, defaultOffset.offset - top); - pc += JUMP_OFFSET_LEN; - } - - // Set the SRC_SWITCH note's offset operand to tell end of switch. - if (!setSrcNoteOffset(noteIndex, 0, lastNonJumpTargetOffset() - top)) - return false; - - if (switchOp == JSOP_TABLESWITCH) { - // Skip over the already-initialized switch bounds. - pc += 2 * JUMP_OFFSET_LEN; - - // Fill in the jump table, if there is one. - for (uint32_t i = 0; i < tableLength; i++) { - CaseClause* caseNode = table[i]; - ptrdiff_t off = caseNode ? caseNode->offset() - top : 0; - SET_JUMP_OFFSET(pc, off); - pc += JUMP_OFFSET_LEN; - } - } - - // Patch breaks before leaving the scope, as all breaks are under the - // lexical scope if it exists. - if (!controlInfo.patchBreaks(this)) - return false; - - if (emitterScope && !emitterScope->leave(this)) + if (!se.emitEnd()) return false; return true; diff --git a/js/src/frontend/BytecodeEmitter.h b/js/src/frontend/BytecodeEmitter.h index bdbf2e6de2..79c36c5004 100644 --- a/js/src/frontend/BytecodeEmitter.h +++ b/js/src/frontend/BytecodeEmitter.h @@ -353,7 +353,9 @@ struct MOZ_STACK_CLASS BytecodeEmitter } bool reportError(ParseNode* pn, unsigned errorNumber, ...); + bool reportError(const mozilla::Maybe<uint32_t>& maybeOffset, unsigned errorNumber, ...); bool reportExtraWarning(ParseNode* pn, unsigned errorNumber, ...); + bool reportExtraWarning(const mozilla::Maybe<uint32_t>& maybeOffset, unsigned errorNumber, ...); bool reportStrictModeError(ParseNode* pn, unsigned errorNumber, ...); // If pn contains a useful expression, return true with *answer set to true. diff --git a/js/src/frontend/ParseNode.h b/js/src/frontend/ParseNode.h index bdba7a1ff9..2e5e29675e 100644 --- a/js/src/frontend/ParseNode.h +++ b/js/src/frontend/ParseNode.h @@ -254,16 +254,12 @@ IsTypeofKind(ParseNodeKind kind) * or (if the push was optimized away) empty * PNK_STATEMENTLIST. * PNK_SWITCH binary pn_left: discriminant - * pn_right: list of PNK_CASE nodes, with at most one - * default node, or if there are let bindings - * in the top level of the switch body's cases, a - * PNK_LEXICALSCOPE node that contains the list of - * PNK_CASE nodes. + * pn_right: PNK_LEXICALSCOPE node that contains the list + * of PNK_CASE nodes, with at most one default node. * PNK_CASE binary pn_left: case-expression if CaseClause, or * null if DefaultClause * pn_right: PNK_STATEMENTLIST node for this case's * statements - * pn_u.binary.offset: scratch space for the emitter * PNK_WHILE binary pn_left: cond, pn_right: body * PNK_DOWHILE binary pn_left: body, pn_right: cond * PNK_FOR binary pn_left: either PNK_FORIN (for-in statement), @@ -587,7 +583,6 @@ class ParseNode union { unsigned iflags; /* JSITER_* flags for PNK_{COMPREHENSION,}FOR node */ bool isStatic; /* only for PNK_CLASSMETHOD */ - uint32_t offset; /* for the emitter's use on PNK_CASE nodes */ }; } binary; struct { /* one kid if unary */ @@ -1069,10 +1064,6 @@ class CaseClause : public BinaryNode // The next CaseClause in the same switch statement. CaseClause* next() const { return pn_next ? &pn_next->as<CaseClause>() : nullptr; } - // Scratch space used by the emitter. - uint32_t offset() const { return pn_u.binary.offset; } - void setOffset(uint32_t u) { pn_u.binary.offset = u; } - static bool test(const ParseNode& node) { bool match = node.isKind(PNK_CASE); MOZ_ASSERT_IF(match, node.isArity(PN_BINARY)); diff --git a/js/src/frontend/SwitchEmitter.cpp b/js/src/frontend/SwitchEmitter.cpp new file mode 100644 index 0000000000..c72120e2d3 --- /dev/null +++ b/js/src/frontend/SwitchEmitter.cpp @@ -0,0 +1,424 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "frontend/SwitchEmitter.h" + +#include "jsutil.h" + +#include "frontend/BytecodeEmitter.h" +#include "frontend/SharedContext.h" +#include "frontend/SourceNotes.h" +#include "vm/Opcodes.h" +#include "vm/Runtime.h" + +using namespace js; +using namespace js::frontend; + +using mozilla::Maybe; + +bool +SwitchEmitter::TableGenerator::addNumber(int32_t caseValue) +{ + if (isInvalid()) + return true; + + if (unsigned(caseValue + int(JS_BIT(15))) >= unsigned(JS_BIT(16))) { + setInvalid(); + return true; + } + + if (intmap_.isNothing()) + intmap_.emplace(); + + low_ = std::min(low_, caseValue); + high_ = std::max(high_, caseValue); + + // Check for duplicates, which require a JSOP_CONDSWITCH. + // We bias caseValue by 65536 if it's negative, and hope that's a rare case + // (because it requires a malloc'd bitmap). + if (caseValue < 0) + caseValue += JS_BIT(16); + if (caseValue >= intmapBitLength_) { + size_t newLength = NumWordsForBitArrayOfLength(caseValue + 1); + if (!intmap_->resize(newLength)) { + ReportOutOfMemory(bce_->cx); + return false; + } + intmapBitLength_ = newLength * BitArrayElementBits; + } + if (IsBitArrayElementSet(intmap_->begin(), intmap_->length(), caseValue)) { + // Duplicate entry is not supported in table switch. + setInvalid(); + return true; + } + SetBitArrayElement(intmap_->begin(), intmap_->length(), caseValue); + return true; +} + +void +SwitchEmitter::TableGenerator::finish(uint32_t caseCount) +{ + intmap_.reset(); + +#ifdef DEBUG + finished_ = true; +#endif + + if (isInvalid()) + return; + + if (caseCount == 0) { + low_ = 0; + high_ = -1; + return; + } + + // Compute table length and select condswitch instead if overlarge + // or more than half-sparse. + tableLength_ = uint32_t(high_ - low_ + 1); + if (tableLength_ >= JS_BIT(16) || tableLength_ > 2 * caseCount) + setInvalid(); +} + +uint32_t +SwitchEmitter::TableGenerator::toCaseIndex(int32_t caseValue) const +{ + MOZ_ASSERT(finished_); + MOZ_ASSERT(isValid()); + uint32_t caseIndex = uint32_t(caseValue - low_); + MOZ_ASSERT(caseIndex < tableLength_); + return caseIndex; +} + +uint32_t +SwitchEmitter::TableGenerator::tableLength() const +{ + MOZ_ASSERT(finished_); + MOZ_ASSERT(isValid()); + return tableLength_; +} + +SwitchEmitter::SwitchEmitter(BytecodeEmitter* bce) + : bce_(bce) +{} + +bool +SwitchEmitter::emitDiscriminant(const Maybe<uint32_t>& switchPos) +{ + MOZ_ASSERT(state_ == State::Start); + switchPos_ = switchPos; + + if (switchPos_) { + // Ensure that the column of the switch statement is set properly. + if (!bce_->updateSourceCoordNotes(*switchPos_)) + return false; + } + + state_ = State::Discriminant; + return true; +} + +bool +SwitchEmitter::emitLexical(Handle<LexicalScope::Data*> bindings) +{ + MOZ_ASSERT(state_ == State::Discriminant); + MOZ_ASSERT(bindings); + + tdzCacheLexical_.emplace(bce_); + emitterScope_.emplace(bce_); + if (!emitterScope_->enterLexical(bce_, ScopeKind::Lexical, bindings)) + return false; + + state_ = State::Lexical; + return true; +} + +bool +SwitchEmitter::validateCaseCount(uint32_t caseCount) +{ + MOZ_ASSERT(state_ == State::Discriminant || state_ == State::Lexical); + if (caseCount > JS_BIT(16)) { + bce_->reportError(switchPos_, JSMSG_TOO_MANY_CASES); + return false; + } + caseCount_ = caseCount; + + state_ = State::CaseCount; + return true; +} + +bool +SwitchEmitter::emitCond() +{ + MOZ_ASSERT(state_ == State::CaseCount); + + kind_ = Kind::Cond; + + // After entering the scope if necessary, push the switch control. + controlInfo_.emplace(bce_, StatementKind::Switch); + top_ = bce_->offset(); + + if (!caseOffsets_.resize(caseCount_)) { + ReportOutOfMemory(bce_->cx); + return false; + } + + // The note has two offsets: first tells total switch code length; + // second tells offset to first JSOP_CASE. + if (!bce_->newSrcNote3(SRC_CONDSWITCH, 0, 0, ¬eIndex_)) + return false; + + MOZ_ASSERT(top_ == bce_->offset()); + if (!bce_->emitN(JSOP_CONDSWITCH, 0)) + return false; + + tdzCacheCaseAndBody_.emplace(bce_); + + state_ = State::Cond; + return true; +} + +bool +SwitchEmitter::emitTable(const TableGenerator& tableGen) +{ + MOZ_ASSERT(state_ == State::CaseCount); + kind_ = Kind::Table; + + // After entering the scope if necessary, push the switch control. + controlInfo_.emplace(bce_, StatementKind::Switch); + top_ = bce_->offset(); + + // The note has one offset that tells total switch code length. + + // 3 offsets (len, low, high) before the table, 1 per entry. + size_t switchSize = size_t(JUMP_OFFSET_LEN * (3 + tableGen.tableLength())); + if (!bce_->newSrcNote2(SRC_TABLESWITCH, 0, ¬eIndex_)) + return false; + + if (!caseOffsets_.resize(tableGen.tableLength())) { + ReportOutOfMemory(bce_->cx); + return false; + } + + MOZ_ASSERT(top_ == bce_->offset()); + if (!bce_->emitN(JSOP_TABLESWITCH, switchSize)) + return false; + + // Skip default offset. + jsbytecode* pc = bce_->code(top_ + JUMP_OFFSET_LEN); + + // Fill in switch bounds, which we know fit in 16-bit offsets. + SET_JUMP_OFFSET(pc, tableGen.low()); + SET_JUMP_OFFSET(pc + JUMP_OFFSET_LEN, tableGen.high()); + + state_ = State::Table; + return true; +} + +bool +SwitchEmitter::emitCaseOrDefaultJump(uint32_t caseIndex, bool isDefault) +{ + MOZ_ASSERT(kind_ == Kind::Cond); + + if (state_ == State::Case) { + // Link the last JSOP_CASE's SRC_NEXTCASE to current JSOP_CASE or + // JSOP_DEFAULT for the benefit of IonBuilder. + if (!bce_->setSrcNoteOffset(caseNoteIndex_, 0, bce_->offset() - lastCaseOffset_)) + return false; + } + + if (isDefault) { + if (!bce_->emitJump(JSOP_DEFAULT, &condSwitchDefaultOffset_)) + return false; + return true; + } + + if (!bce_->newSrcNote2(SRC_NEXTCASE, 0, &caseNoteIndex_)) + return false; + + JumpList caseJump; + if (!bce_->emitJump(JSOP_CASE, &caseJump)) + return false; + caseOffsets_[caseIndex] = caseJump.offset; + lastCaseOffset_ = caseJump.offset; + + if (state_ == State::Cond) { + // Switch note's second offset is to first JSOP_CASE. + unsigned noteCount = bce_->notes().length(); + if (!bce_->setSrcNoteOffset(noteIndex_, 1, lastCaseOffset_ - top_)) + return false; + unsigned noteCountDelta = bce_->notes().length() - noteCount; + if (noteCountDelta != 0) + caseNoteIndex_ += noteCountDelta; + } + + return true; +} + +bool +SwitchEmitter::emitCaseJump() +{ + MOZ_ASSERT(kind_ == Kind::Cond); + MOZ_ASSERT(state_ == State::Cond || state_ == State::Case); + if (!emitCaseOrDefaultJump(caseIndex_, false)) + return false; + caseIndex_++; + + state_ = State::Case; + return true; +} + +bool +SwitchEmitter::emitImplicitDefault() +{ + MOZ_ASSERT(kind_ == Kind::Cond); + MOZ_ASSERT(state_ == State::Cond || state_ == State::Case); + if (!emitCaseOrDefaultJump(0, true)) + return false; + + caseIndex_ = 0; + + // No internal state after emitting default jump. + return true; +} + +bool +SwitchEmitter::emitCaseBody() +{ + MOZ_ASSERT(kind_ == Kind::Cond); + MOZ_ASSERT(state_ == State::Cond || state_ == State::Case || + state_ == State::CaseBody || state_ == State::DefaultBody); + + tdzCacheCaseAndBody_.reset(); + + if (state_ == State::Cond || state_ == State::Case) { + // For cond switch, JSOP_DEFAULT is always emitted. + if (!emitImplicitDefault()) + return false; + } + + JumpList caseJump; + caseJump.offset = caseOffsets_[caseIndex_]; + if (!bce_->emitJumpTargetAndPatch(caseJump)) + return false; + + JumpTarget here; + if (!bce_->emitJumpTarget(&here)) + return false; + caseIndex_++; + + tdzCacheCaseAndBody_.emplace(bce_); + + state_ = State::CaseBody; + return true; +} + +bool +SwitchEmitter::emitCaseBody(int32_t caseValue, const TableGenerator& tableGen) +{ + MOZ_ASSERT(kind_ == Kind::Table); + MOZ_ASSERT(state_ == State::Table || + state_ == State::CaseBody || state_ == State::DefaultBody); + + tdzCacheCaseAndBody_.reset(); + + JumpTarget here; + if (!bce_->emitJumpTarget(&here)) + return false; + caseOffsets_[tableGen.toCaseIndex(caseValue)] = here.offset; + + tdzCacheCaseAndBody_.emplace(bce_); + + state_ = State::CaseBody; + return true; +} + +bool +SwitchEmitter::emitDefaultBody() +{ + MOZ_ASSERT(state_ == State::Cond || state_ == State::Table || + state_ == State::Case || + state_ == State::CaseBody); + MOZ_ASSERT(!hasDefault_); + + tdzCacheCaseAndBody_.reset(); + + if (state_ == State::Cond || state_ == State::Case) { + // For cond switch, JSOP_DEFAULT is always emitted. + if (!emitImplicitDefault()) + return false; + } + JumpTarget here; + if (!bce_->emitJumpTarget(&here)) + return false; + defaultJumpTargetOffset_ = here; + + tdzCacheCaseAndBody_.emplace(bce_); + + hasDefault_ = true; + state_ = State::DefaultBody; + return true; +} + +bool +SwitchEmitter::emitEnd() +{ + MOZ_ASSERT(state_ == State::Cond || state_ == State::Table || + state_ == State::CaseBody || state_ == State::DefaultBody); + + tdzCacheCaseAndBody_.reset(); + + if (!hasDefault_) { + // If no default case, offset for default is to end of switch. + if (!bce_->emitJumpTarget(&defaultJumpTargetOffset_)) + return false; + } + MOZ_ASSERT(defaultJumpTargetOffset_.offset != -1); + + // Set the default offset (to end of switch if no default). + jsbytecode* pc; + if (kind_ == Kind::Cond) { + pc = nullptr; + bce_->patchJumpsToTarget(condSwitchDefaultOffset_, defaultJumpTargetOffset_); + } else { + // Fill in the default jump target. + pc = bce_->code(top_); + SET_JUMP_OFFSET(pc, defaultJumpTargetOffset_.offset - top_); + pc += JUMP_OFFSET_LEN; + } + + // Set the SRC_SWITCH note's offset operand to tell end of switch. + if (!bce_->setSrcNoteOffset(noteIndex_, 0, bce_->lastNonJumpTargetOffset() - top_)) + return false; + + if (kind_ == Kind::Table) { + // Skip over the already-initialized switch bounds. + pc += 2 * JUMP_OFFSET_LEN; + + // Fill in the jump table, if there is one. + for (uint32_t i = 0, length = caseOffsets_.length(); i < length; i++) { + ptrdiff_t off = caseOffsets_[i]; + SET_JUMP_OFFSET(pc, off == 0 ? 0 : off - top_); + pc += JUMP_OFFSET_LEN; + } + } + + // Patch breaks before leaving the scope, as all breaks are under the + // lexical scope if it exists. + if (!controlInfo_->patchBreaks(bce_)) + return false; + + if (emitterScope_ && !emitterScope_->leave(bce_)) + return false; + + emitterScope_.reset(); + tdzCacheLexical_.reset(); + + controlInfo_.reset(); + + state_ = State::End; + return true; +} diff --git a/js/src/frontend/SwitchEmitter.h b/js/src/frontend/SwitchEmitter.h new file mode 100644 index 0000000000..f712059e67 --- /dev/null +++ b/js/src/frontend/SwitchEmitter.h @@ -0,0 +1,470 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef frontend_SwitchEmitter_h +#define frontend_SwitchEmitter_h + +#include "mozilla/Attributes.h" +#include "mozilla/Maybe.h" + +#include <stddef.h> +#include <stdint.h> + +#include "jsalloc.h" + +#include "frontend/BytecodeControlStructures.h" +#include "frontend/EmitterScope.h" +#include "frontend/JumpList.h" +#include "frontend/TDZCheckCache.h" +#include "gc/Rooting.h" +#include "js/Value.h" +#include "js/Vector.h" +#include "vm/Scope.h" + +namespace js { +namespace frontend { + +struct BytecodeEmitter; + +// Class for emitting bytecode for switch-case-default block. +// +// Usage: (check for the return value is omitted for simplicity) +// +// `switch (discriminant) { case c1_expr: c1_body; }` +// SwitchEmitter se(this); +// se.emitDiscriminant(Some(offset_of_switch)); +// emit(discriminant); +// +// se.validateCaseCount(1); +// se.emitCond(); +// +// emit(c1_expr); +// se.emitCaseJump(); +// +// se.emitCaseBody(); +// emit(c1_body); +// +// se.emitEnd(); +// +// `switch (discriminant) { case c1_expr: c1_body; case c2_expr: c2_body; +// default: def_body; }` +// SwitchEmitter se(this); +// se.emitDiscriminant(Some(offset_of_switch)); +// emit(discriminant); +// +// se.validateCaseCount(2); +// se.emitCond(); +// +// emit(c1_expr); +// se.emitCaseJump(); +// +// emit(c2_expr); +// se.emitCaseJump(); +// +// se.emitCaseBody(); +// emit(c1_body); +// +// se.emitCaseBody(); +// emit(c2_body); +// +// se.emitDefaultBody(); +// emit(def_body); +// +// se.emitEnd(); +// +// `switch (discriminant) { case c1_expr: c1_body; case c2_expr: c2_body; }` +// with Table Switch +// SwitchEmitter::TableGenerator tableGen(this); +// tableGen.addNumber(c1_expr_value); +// tableGen.addNumber(c2_expr_value); +// tableGen.finish(2); +// +// // If `!tableGen.isValid()` here, `emitCond` should be used instead. +// +// SwitchEmitter se(this); +// se.emitDiscriminant(Some(offset_of_switch)); +// emit(discriminant); +// se.validateCaseCount(2); +// se.emitTable(tableGen); +// +// se.emitCaseBody(c1_expr_value, tableGen); +// emit(c1_body); +// +// se.emitCaseBody(c2_expr_value, tableGen); +// emit(c2_body); +// +// se.emitEnd(); +// +// `switch (discriminant) { case c1_expr: c1_body; case c2_expr: c2_body; +// default: def_body; }` +// with Table Switch +// SwitchEmitter::TableGenerator tableGen(bce); +// tableGen.addNumber(c1_expr_value); +// tableGen.addNumber(c2_expr_value); +// tableGen.finish(2); +// +// // If `!tableGen.isValid()` here, `emitCond` should be used instead. +// +// SwitchEmitter se(this); +// se.emitDiscriminant(Some(offset_of_switch)); +// emit(discriminant); +// se.validateCaseCount(2); +// se.emitTable(tableGen); +// +// se.emitCaseBody(c1_expr_value, tableGen); +// emit(c1_body); +// +// se.emitCaseBody(c2_expr_value, tableGen); +// emit(c2_body); +// +// se.emitDefaultBody(); +// emit(def_body); +// +// se.emitEnd(); +// +// `switch (discriminant) { case c1_expr: c1_body; }` +// in case c1_body contains lexical bindings +// SwitchEmitter se(this); +// se.emitDiscriminant(Some(offset_of_switch)); +// emit(discriminant); +// +// se.validateCaseCount(1); +// +// se.emitLexical(bindings); +// +// se.emitCond(); +// +// emit(c1_expr); +// se.emitCaseJump(); +// +// se.emitCaseBody(); +// emit(c1_body); +// +// se.emitEnd(); +// +// `switch (discriminant) { case c1_expr: c1_body; }` +// in case c1_body contains hosted functions +// SwitchEmitter se(this); +// se.emitDiscriminant(Some(offset_of_switch)); +// emit(discriminant); +// +// se.validateCaseCount(1); +// +// se.emitLexical(bindings); +// emit(hosted functions); +// +// se.emitCond(); +// +// emit(c1_expr); +// se.emitCaseJump(); +// +// se.emitCaseBody(); +// emit(c1_body); +// +// se.emitEnd(); +// +class MOZ_STACK_CLASS SwitchEmitter +{ + // Bytecode for each case. + // + // Cond Switch + // {discriminant} + // JSOP_CONDSWITCH + // + // {c1_expr} + // JSOP_CASE c1 + // + // JSOP_JUMPTARGET + // {c2_expr} + // JSOP_CASE c2 + // + // ... + // + // JSOP_JUMPTARGET + // JSOP_DEFAULT default + // + // c1: + // JSOP_JUMPTARGET + // {c1_body} + // JSOP_GOTO end + // + // c2: + // JSOP_JUMPTARGET + // {c2_body} + // JSOP_GOTO end + // + // default: + // end: + // JSOP_JUMPTARGET + // + // Table Switch + // {discriminant} + // JSOP_TABLESWITCH c1, c2, ... + // + // c1: + // JSOP_JUMPTARGET + // {c1_body} + // JSOP_GOTO end + // + // c2: + // JSOP_JUMPTARGET + // {c2_body} + // JSOP_GOTO end + // + // ... + // + // end: + // JSOP_JUMPTARGET + + public: + enum class Kind { + Table, + Cond + }; + + // Class for generating optimized table switch data. + class MOZ_STACK_CLASS TableGenerator + { + BytecodeEmitter* bce_; + + // Bit array for given numbers. + mozilla::Maybe<js::Vector<size_t, 128, SystemAllocPolicy>> intmap_; + + // The length of the intmap_. + int32_t intmapBitLength_ = 0; + + // The length of the table. + uint32_t tableLength_ = 0; + + // The lower and higher bounds of the table. + int32_t low_ = JSVAL_INT_MAX, high_ = JSVAL_INT_MIN; + + // Whether the table is still valid. + bool valid_= true; + +#ifdef DEBUG + bool finished_ = false; +#endif + + public: + explicit TableGenerator(BytecodeEmitter* bce) + : bce_(bce) + {} + + void setInvalid() { + valid_ = false; + } + MOZ_MUST_USE bool isValid() const { + return valid_; + } + MOZ_MUST_USE bool isInvalid() const { + return !valid_; + } + + // Add the given number to the table. The number is the value of + // `expr` for `case expr:` syntax. + MOZ_MUST_USE bool addNumber(int32_t caseValue); + + // Finish generating the table. + // `caseCount` should be the number of cases in the switch statement, + // excluding the default case. + void finish(uint32_t caseCount); + + private: + friend SwitchEmitter; + + // The following methods can be used only after calling `finish`. + + // Returns the lower bound of the added numbers. + int32_t low() const { + MOZ_ASSERT(finished_); + return low_; + } + + // Returns the higher bound of the numbers. + int32_t high() const { + MOZ_ASSERT(finished_); + return high_; + } + + // Returns the index in SwitchEmitter.caseOffsets_ for table switch. + uint32_t toCaseIndex(int32_t caseValue) const; + + // Returns the length of the table. + // This method can be called only if `isValid()` is true. + uint32_t tableLength() const; + }; + + private: + BytecodeEmitter* bce_; + + // `kind_` should be set to the correct value in emitCond/emitTable. + Kind kind_ = Kind::Cond; + + // True if there's explicit default case. + bool hasDefault_ = false; + + // The source note index for SRC_CONDSWITCH. + unsigned noteIndex_ = 0; + + // Source note index of the previous SRC_NEXTCASE. + unsigned caseNoteIndex_ = 0; + + // The number of cases in the switch statement, excluding the default case. + uint32_t caseCount_ = 0; + + // Internal index for case jump and case body, used by cond switch. + uint32_t caseIndex_ = 0; + + // Bytecode offset after emitting `discriminant`. + ptrdiff_t top_ = 0; + + // Bytecode offset of the previous JSOP_CASE. + ptrdiff_t lastCaseOffset_ = 0; + + // Bytecode offset of the JSOP_JUMPTARGET for default body. + JumpTarget defaultJumpTargetOffset_ = { -1 }; + + // Bytecode offset of the JSOP_DEFAULT. + JumpList condSwitchDefaultOffset_; + + // Instantiated when there's lexical scope for entire switch. + mozilla::Maybe<TDZCheckCache> tdzCacheLexical_; + mozilla::Maybe<EmitterScope> emitterScope_; + + // Instantiated while emitting case expression and case/default body. + mozilla::Maybe<TDZCheckCache> tdzCacheCaseAndBody_; + + // Control for switch. + mozilla::Maybe<BreakableControl> controlInfo_; + + mozilla::Maybe<uint32_t> switchPos_; + + // Cond Switch: + // Offset of each JSOP_CASE. + // Table Switch: + // Offset of each JSOP_JUMPTARGET for case. + js::Vector<ptrdiff_t, 32, SystemAllocPolicy> caseOffsets_; + + // The state of this emitter. + // + // +-------+ emitDiscriminant +--------------+ + // | Start |----------------->| Discriminant |-+ + // +-------+ +--------------+ | + // | + // +-------------------------------------------+ + // | + // | validateCaseCount +-----------+ + // +->+------------------------>+------------------>| CaseCount |-+ + // | ^ +-----------+ | + // | emitLexical +---------+ | | + // +------------>| Lexical |-+ | + // +---------+ | + // | + // +--------------------------------------------------------------+ + // | + // | emitTable +-------+ + // +---------->| Table |---------------------------->+-+ + // | +-------+ ^ | + // | | | + // | emitCond +------+ | | + // +---------->| Cond |-+------------------------>+->+ | + // +------+ | ^ | + // | | | + // | emitCase +------+ | | + // +->+--------->| Case |->+-+ | + // ^ +------+ | | + // | | | + // +--------------------+ | + // | + // +---------------------------------------------------+ + // | + // | emitEnd +-----+ + // +-+----------------------------------------->+-------->| End | + // | ^ +-----+ + // | emitCaseBody +----------+ | + // +->+-+---------------->| CaseBody |--->+-+-+ + // ^ | +----------+ ^ | + // | | | | + // | | emitDefaultBody +-------------+ | | + // | +---------------->| DefaultBody |-+ | + // | +-------------+ | + // | | + // +-------------------------------------+ + // + enum class State { + // The initial state. + Start, + + // After calling emitDiscriminant. + Discriminant, + + // After calling validateCaseCount. + CaseCount, + + // After calling emitLexical. + Lexical, + + // After calling emitCond. + Cond, + + // After calling emitTable. + Table, + + // After calling emitCase. + Case, + + // After calling emitCaseBody. + CaseBody, + + // After calling emitDefaultBody. + DefaultBody, + + // After calling emitEnd. + End + }; + State state_ = State::Start; + + public: + explicit SwitchEmitter(BytecodeEmitter* bce); + + // `switchPos` is the offset in the source code for the character below: + // + // switch ( cond ) { ... } + // ^ + // | + // switchPos + // + // Can be Nothing() if not available. + MOZ_MUST_USE bool emitDiscriminant(const mozilla::Maybe<uint32_t>& switchPos); + + // `caseCount` should be the number of cases in the switch statement, + // excluding the default case. + MOZ_MUST_USE bool validateCaseCount(uint32_t caseCount); + + // `bindings` is a lexical scope for the entire switch, in case there's + // let/const effectively directly under case or default blocks. + MOZ_MUST_USE bool emitLexical(Handle<LexicalScope::Data*> bindings); + + MOZ_MUST_USE bool emitCond(); + MOZ_MUST_USE bool emitTable(const TableGenerator& tableGen); + + MOZ_MUST_USE bool emitCaseJump(); + + MOZ_MUST_USE bool emitCaseBody(); + MOZ_MUST_USE bool emitCaseBody(int32_t caseValue, const TableGenerator& tableGen); + MOZ_MUST_USE bool emitDefaultBody(); + MOZ_MUST_USE bool emitEnd(); + + private: + MOZ_MUST_USE bool emitCaseOrDefaultJump(uint32_t caseIndex, bool isDefault); + MOZ_MUST_USE bool emitImplicitDefault(); +}; + +} /* namespace frontend */ +} /* namespace js */ + +#endif /* frontend_SwitchEmitter_h */ diff --git a/js/src/moz.build b/js/src/moz.build index eae53d04b7..7a2d896600 100644 --- a/js/src/moz.build +++ b/js/src/moz.build @@ -152,6 +152,7 @@ UNIFIED_SOURCES += [ 'frontend/NameOpEmitter.cpp', 'frontend/ParseNode.cpp', 'frontend/PropOpEmitter.cpp', + 'frontend/SwitchEmitter.cpp', 'frontend/TDZCheckCache.cpp', 'frontend/TokenStream.cpp', 'frontend/TryEmitter.cpp', |