/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- * vim: set ts=8 sts=2 et sw=2 tw=80: * 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/Assertions.h" // MOZ_ASSERT #include "mozilla/Attributes.h" // MOZ_STACK_CLASS, MOZ_MUST_USE #include "mozilla/Maybe.h" // mozilla::Maybe #include // size_t #include // int32_t, uint32_t #include "frontend/BytecodeControlStructures.h" // BreakableControl #include "frontend/EmitterScope.h" // EmitterScope #include "frontend/JumpList.h" // JumpList, JumpTarget #include "frontend/TDZCheckCache.h" // TDZCheckCache #include "gc/Rooting.h" // Handle #include "js/AllocPolicy.h" // SystemAllocPolicy #include "js/Value.h" // JSVAL_INT_MAX, JSVAL_INT_MIN #include "js/Vector.h" // Vector #include "vm/Scope.h" // LexicalScope 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(); // // se.prepareForCaseValue(); // 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(); // // se.prepareForCaseValue(); // emit(c1_expr); // se.emitCaseJump(); // // se.prepareForCaseValue(); // 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(); // // se.prepareForCaseValue(); // 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(); // // se.prepareForCaseValue(); // emit(c1_expr); // se.emitCaseJump(); // // se.emitCaseBody(); // emit(c1_body); // // se.emitEnd(); // class MOZ_STACK_CLASS SwitchEmitter { // Bytecode for each case. // // Cond Switch (uses an equality comparison for each case) // {discriminant} // // {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> 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 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`. BytecodeOffset top_; // Bytecode offset of the previous JSOp::Case. BytecodeOffset lastCaseOffset_; // Bytecode offset of the JSOp::JumpTarget for default body. JumpTarget defaultJumpTargetOffset_; // Bytecode offset of the JSOp::Default. JumpList condSwitchDefaultOffset_; // Instantiated when there's lexical scope for entire switch. mozilla::Maybe tdzCacheLexical_; mozilla::Maybe emitterScope_; // Instantiated while emitting case expression and case/default body. mozilla::Maybe tdzCacheCaseAndBody_; // Control for switch. mozilla::Maybe controlInfo_; mozilla::Maybe switchPos_; // Cond Switch: // Offset of each JSOp::Case. // Table Switch: // Offset of each JSOp::JumpTarget for case. js::Vector caseOffsets_; // The state of this emitter. // // +-------+ emitDiscriminant +--------------+ // | Start |----------------->| Discriminant |-+ // +-------+ +--------------+ | // | // +-------------------------------------------+ // | // | validateCaseCount +-----------+ // +->+------------------------>+------------------>| CaseCount |-+ // | ^ +-----------+ | // | emitLexical +---------+ | | // +------------>| Lexical |-+ | // +---------+ | // | // +--------------------------------------------------------------+ // | // | emitTable +-------+ // +---------->| Table |----------------------------------->+-+ // | +-------+ ^ | // | | | // | emitCond +------+ | | // +---------->| Cond |-+------------------------------->+->+ | // +------+ | ^ | // | | | // +------------------+ | | // | | | // |prepareForCaseValue +-----------+ | | // +----------+--------->| CaseValue | | | // ^ +-----------+ | | // | | | | // | | emitCaseJump +------+ | | // | +------------->| 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 prepareForCaseValue. CaseValue, // After calling emitCaseJump. 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& 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(LexicalScope::ParserData* bindings); MOZ_MUST_USE bool emitCond(); MOZ_MUST_USE bool emitTable(const TableGenerator& tableGen); MOZ_MUST_USE bool prepareForCaseValue(); 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 */