js/src/frontend/SwitchEmitter.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "frontend/SwitchEmitter.h"
   8
   9 #include "mozilla/Assertions.h"  // MOZ_ASSERT
  10 #include "mozilla/Span.h"        // mozilla::Span
  11
  12 #include <algorithm>  // std::min, std::max
  13
  14 #include "jstypes.h"  // JS_BIT
  15
  16 #include "frontend/BytecodeEmitter.h"  // BytecodeEmitter
  17 #include "frontend/SharedContext.h"    // StatementKind
  18 #include "js/friend/ErrorMessages.h"   // JSMSG_*
  19 #include "js/TypeDecls.h"              // jsbytecode
  20 #include "util/BitArray.h"
  21 #include "vm/BytecodeUtil.h"  // SET_JUMP_OFFSET, JUMP_OFFSET_LEN, SET_RESUMEINDEX
  22 #include "vm/Opcodes.h"       // JSOp, JSOpLength_TableSwitch
  23 #include "vm/Runtime.h"       // ReportOutOfMemory
  24
  25 using namespace js;
  26 using namespace js::frontend;
  27
  28 bool SwitchEmitter::TableGenerator::addNumber(int32_t caseValue) {
  29   if (isInvalid()) {
  30     return true;
  31   }
  32
  33   if (unsigned(caseValue + int(Bit(15))) >= unsigned(Bit(16))) {
  34     setInvalid();
  35     return true;
  36   }
  37
  38   if (intmap_.isNothing()) {
  39     intmap_.emplace();
  40   }
  41
  42   low_ = std::min(low_, caseValue);
  43   high_ = std::max(high_, caseValue);
  44
  45   // Check for duplicates, which are not supported in a table switch.
  46   // We bias caseValue by 65536 if it's negative, and hope that's a rare case
  47   // (because it requires a malloc'd bitmap).
  48   if (caseValue < 0) {
  49     caseValue += Bit(16);
  50   }
  51   if (caseValue >= intmapBitLength_) {
  52     size_t newLength = NumWordsForBitArrayOfLength(caseValue + 1);
  53     if (!intmap_->resize(newLength)) {
  54       ReportOutOfMemory(bce_->fc);
  55       return false;
  56     }
  57     intmapBitLength_ = newLength * BitArrayElementBits;
  58   }
  59   if (IsBitArrayElementSet(intmap_->begin(), intmap_->length(), caseValue)) {
  60     // Duplicate entry is not supported in table switch.
  61     setInvalid();
  62     return true;
  63   }
  64   SetBitArrayElement(intmap_->begin(), intmap_->length(), caseValue);
  65   return true;
  66 }
  67
  68 void SwitchEmitter::TableGenerator::finish(uint32_t caseCount) {
  69   intmap_.reset();
  70
  71 #ifdef DEBUG
  72   finished_ = true;
  73 #endif
  74
  75   if (isInvalid()) {
  76     return;
  77   }
  78
  79   if (caseCount == 0) {
  80     low_ = 0;
  81     high_ = -1;
  82     return;
  83   }
  84
  85   // Compute table length. Don't use table switch if overlarge or more than
  86   // half-sparse.
  87   tableLength_ = uint32_t(high_ - low_ + 1);
  88   if (tableLength_ >= Bit(16) || tableLength_ > 2 * caseCount) {
  89     setInvalid();
  90   }
  91 }
  92
  93 uint32_t SwitchEmitter::TableGenerator::toCaseIndex(int32_t caseValue) const {
  94   MOZ_ASSERT(finished_);
  95   MOZ_ASSERT(isValid());
  96   uint32_t caseIndex = uint32_t(caseValue - low_);
  97   MOZ_ASSERT(caseIndex < tableLength_);
  98   return caseIndex;
  99 }
 100
 101 uint32_t SwitchEmitter::TableGenerator::tableLength() const {
 102   MOZ_ASSERT(finished_);
 103   MOZ_ASSERT(isValid());
 104   return tableLength_;
 105 }
 106
 107 SwitchEmitter::SwitchEmitter(BytecodeEmitter* bce) : bce_(bce) {}
 108
 109 bool SwitchEmitter::emitDiscriminant(uint32_t switchPos) {
 110   MOZ_ASSERT(state_ == State::Start);
 111   switchPos_ = switchPos;
 112
 113   // Ensure that the column of the switch statement is set properly.
 114   if (!bce_->updateSourceCoordNotes(switchPos_)) {
 115     return false;
 116   }
 117
 118   state_ = State::Discriminant;
 119   return true;
 120 }
 121
 122 bool SwitchEmitter::emitLexical(LexicalScope::ParserData* bindings) {
 123   MOZ_ASSERT(state_ == State::Discriminant);
 124   MOZ_ASSERT(bindings);
 125
 126   tdzCacheLexical_.emplace(bce_);
 127   emitterScope_.emplace(bce_);
 128   if (!emitterScope_->enterLexical(bce_, ScopeKind::Lexical, bindings
 129 #ifdef ENABLE_EXPLICIT_RESOURCE_MANAGEMENT
 130                                    ,
 131                                    EmitterScope::IsSwitchBlock::Yes
 132 #endif
 133                                    )) {
 134     return false;
 135   }
 136
 137   state_ = State::Lexical;
 138   return true;
 139 }
 140
 141 bool SwitchEmitter::validateCaseCount(uint32_t caseCount) {
 142   MOZ_ASSERT(state_ == State::Discriminant || state_ == State::Lexical);
 143   if (caseCount > Bit(16)) {
 144     bce_->reportError(switchPos_, JSMSG_TOO_MANY_CASES);
 145     return false;
 146   }
 147   caseCount_ = caseCount;
 148
 149   state_ = State::CaseCount;
 150   return true;
 151 }
 152
 153 bool SwitchEmitter::emitCond() {
 154   MOZ_ASSERT(state_ == State::CaseCount);
 155
 156   kind_ = Kind::Cond;
 157
 158   // After entering the scope if necessary, push the switch control.
 159   controlInfo_.emplace(bce_, StatementKind::Switch);
 160   top_ = bce_->bytecodeSection().offset();
 161
 162   if (!caseOffsets_.resize(caseCount_)) {
 163     ReportOutOfMemory(bce_->fc);
 164     return false;
 165   }
 166
 167   MOZ_ASSERT(top_ == bce_->bytecodeSection().offset());
 168
 169   tdzCacheCaseAndBody_.emplace(bce_);
 170
 171   state_ = State::Cond;
 172   return true;
 173 }
 174
 175 bool SwitchEmitter::emitTable(const TableGenerator& tableGen) {
 176   MOZ_ASSERT(state_ == State::CaseCount);
 177   kind_ = Kind::Table;
 178
 179   // After entering the scope if necessary, push the switch control.
 180   controlInfo_.emplace(bce_, StatementKind::Switch);
 181   top_ = bce_->bytecodeSection().offset();
 182
 183   if (!caseOffsets_.resize(tableGen.tableLength())) {
 184     ReportOutOfMemory(bce_->fc);
 185     return false;
 186   }
 187
 188   MOZ_ASSERT(top_ == bce_->bytecodeSection().offset());
 189   if (!bce_->emitN(JSOp::TableSwitch,
 190                    JSOpLength_TableSwitch - sizeof(jsbytecode))) {
 191     return false;
 192   }
 193
 194   // Skip default offset.
 195   jsbytecode* pc =
 196       bce_->bytecodeSection().code(top_ + BytecodeOffsetDiff(JUMP_OFFSET_LEN));
 197
 198   // Fill in switch bounds, which we know fit in 16-bit offsets.
 199   SET_JUMP_OFFSET(pc, tableGen.low());
 200   SET_JUMP_OFFSET(pc + JUMP_OFFSET_LEN, tableGen.high());
 201
 202   state_ = State::Table;
 203   return true;
 204 }
 205
 206 bool SwitchEmitter::emitCaseOrDefaultJump(uint32_t caseIndex, bool isDefault) {
 207   MOZ_ASSERT(kind_ == Kind::Cond);
 208
 209   if (isDefault) {
 210     if (!bce_->emitJump(JSOp::Default, &condSwitchDefaultOffset_)) {
 211       return false;
 212     }
 213     return true;
 214   }
 215
 216   JumpList caseJump;
 217   if (!bce_->emitJump(JSOp::Case, &caseJump)) {
 218     return false;
 219   }
 220   caseOffsets_[caseIndex] = caseJump.offset;
 221   lastCaseOffset_ = caseJump.offset;
 222
 223   return true;
 224 }
 225
 226 bool SwitchEmitter::prepareForCaseValue() {
 227   MOZ_ASSERT(kind_ == Kind::Cond);
 228   MOZ_ASSERT(state_ == State::Cond || state_ == State::Case);
 229
 230   if (!bce_->emit1(JSOp::Dup)) {
 231     return false;
 232   }
 233
 234   state_ = State::CaseValue;
 235   return true;
 236 }
 237
 238 bool SwitchEmitter::emitCaseJump() {
 239   MOZ_ASSERT(kind_ == Kind::Cond);
 240   MOZ_ASSERT(state_ == State::CaseValue);
 241
 242   if (!bce_->emit1(JSOp::StrictEq)) {
 243     return false;
 244   }
 245
 246   if (!emitCaseOrDefaultJump(caseIndex_, false)) {
 247     return false;
 248   }
 249   caseIndex_++;
 250
 251   state_ = State::Case;
 252   return true;
 253 }
 254
 255 bool SwitchEmitter::emitImplicitDefault() {
 256   MOZ_ASSERT(kind_ == Kind::Cond);
 257   MOZ_ASSERT(state_ == State::Cond || state_ == State::Case);
 258   if (!emitCaseOrDefaultJump(0, true)) {
 259     return false;
 260   }
 261
 262   caseIndex_ = 0;
 263
 264   // No internal state after emitting default jump.
 265   return true;
 266 }
 267
 268 bool SwitchEmitter::emitCaseBody() {
 269   MOZ_ASSERT(kind_ == Kind::Cond);
 270   MOZ_ASSERT(state_ == State::Cond || state_ == State::Case ||
 271              state_ == State::CaseBody || state_ == State::DefaultBody);
 272
 273   tdzCacheCaseAndBody_.reset();
 274
 275   if (state_ == State::Cond || state_ == State::Case) {
 276     // For cond switch, JSOp::Default is always emitted.
 277     if (!emitImplicitDefault()) {
 278       return false;
 279     }
 280   }
 281
 282   JumpList caseJump;
 283   caseJump.offset = caseOffsets_[caseIndex_];
 284   if (!bce_->emitJumpTargetAndPatch(caseJump)) {
 285     return false;
 286   }
 287
 288   JumpTarget here;
 289   if (!bce_->emitJumpTarget(&here)) {
 290     return false;
 291   }
 292   caseIndex_++;
 293
 294   tdzCacheCaseAndBody_.emplace(bce_);
 295
 296   state_ = State::CaseBody;
 297   return true;
 298 }
 299
 300 bool SwitchEmitter::emitCaseBody(int32_t caseValue,
 301                                  const TableGenerator& tableGen) {
 302   MOZ_ASSERT(kind_ == Kind::Table);
 303   MOZ_ASSERT(state_ == State::Table || state_ == State::CaseBody ||
 304              state_ == State::DefaultBody);
 305
 306   tdzCacheCaseAndBody_.reset();
 307
 308   JumpTarget here;
 309   if (!bce_->emitJumpTarget(&here)) {
 310     return false;
 311   }
 312   caseOffsets_[tableGen.toCaseIndex(caseValue)] = here.offset;
 313
 314   tdzCacheCaseAndBody_.emplace(bce_);
 315
 316   state_ = State::CaseBody;
 317   return true;
 318 }
 319
 320 bool SwitchEmitter::emitDefaultBody() {
 321   MOZ_ASSERT(state_ == State::Cond || state_ == State::Table ||
 322              state_ == State::Case || state_ == State::CaseBody);
 323   MOZ_ASSERT(!hasDefault_);
 324
 325   tdzCacheCaseAndBody_.reset();
 326
 327   if (state_ == State::Cond || state_ == State::Case) {
 328     // For cond switch, JSOp::Default is always emitted.
 329     if (!emitImplicitDefault()) {
 330       return false;
 331     }
 332   }
 333   JumpTarget here;
 334   if (!bce_->emitJumpTarget(&here)) {
 335     return false;
 336   }
 337   defaultJumpTargetOffset_ = here;
 338
 339   tdzCacheCaseAndBody_.emplace(bce_);
 340
 341   hasDefault_ = true;
 342   state_ = State::DefaultBody;
 343   return true;
 344 }
 345
 346 bool SwitchEmitter::emitEnd() {
 347   MOZ_ASSERT(state_ == State::Cond || state_ == State::Table ||
 348              state_ == State::CaseBody || state_ == State::DefaultBody);
 349
 350   tdzCacheCaseAndBody_.reset();
 351
 352   if (!hasDefault_) {
 353     // If no default case, offset for default is to end of switch.
 354     if (!bce_->emitJumpTarget(&defaultJumpTargetOffset_)) {
 355       return false;
 356     }
 357   }
 358   MOZ_ASSERT(defaultJumpTargetOffset_.offset.valid());
 359
 360   // Set the default offset (to end of switch if no default).
 361   jsbytecode* pc;
 362   if (kind_ == Kind::Cond) {
 363     pc = nullptr;
 364     bce_->patchJumpsToTarget(condSwitchDefaultOffset_,
 365                              defaultJumpTargetOffset_);
 366   } else {
 367     // Fill in the default jump target.
 368     pc = bce_->bytecodeSection().code(top_);
 369     SET_JUMP_OFFSET(pc, (defaultJumpTargetOffset_.offset - top_).value());
 370     pc += JUMP_OFFSET_LEN;
 371   }
 372
 373   if (kind_ == Kind::Table) {
 374     // Skip over the already-initialized switch bounds.
 375     pc += 2 * JUMP_OFFSET_LEN;
 376
 377     // Use the 'default' offset for missing cases.
 378     for (uint32_t i = 0, length = caseOffsets_.length(); i < length; i++) {
 379       if (caseOffsets_[i].value() == 0) {
 380         caseOffsets_[i] = defaultJumpTargetOffset_.offset;
 381       }
 382     }
 383
 384     // Allocate resume index range.
 385     uint32_t firstResumeIndex = 0;
 386     mozilla::Span<BytecodeOffset> offsets =
 387         mozilla::Span(caseOffsets_.begin(), caseOffsets_.end());
 388     if (!bce_->allocateResumeIndexRange(offsets, &firstResumeIndex)) {
 389       return false;
 390     }
 391     SET_RESUMEINDEX(pc, firstResumeIndex);
 392   }
 393
 394   // Patch breaks before leaving the scope, as all breaks are under the
 395   // lexical scope if it exists.
 396   if (!controlInfo_->patchBreaks(bce_)) {
 397     return false;
 398   }
 399
 400   if (emitterScope_ && !emitterScope_->leave(bce_)) {
 401     return false;
 402   }
 403
 404   emitterScope_.reset();
 405   tdzCacheLexical_.reset();
 406
 407   controlInfo_.reset();
 408
 409   state_ = State::End;
 410   return true;
 411 }
 412
 413 InternalSwitchEmitter::InternalSwitchEmitter(BytecodeEmitter* bce)
 414     : SwitchEmitter(bce) {
 415 #ifdef DEBUG
 416   // Skip emitDiscriminant (see the comment above InternalSwitchEmitter)
 417   state_ = State::Discriminant;
 418 #endif
 419 }