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     return false;
 130   }
 131
 132   state_ = State::Lexical;
 133   return true;
 134 }
 135
 136 bool SwitchEmitter::validateCaseCount(uint32_t caseCount) {
 137   MOZ_ASSERT(state_ == State::Discriminant || state_ == State::Lexical);
 138   if (caseCount > Bit(16)) {
 139     bce_->reportError(switchPos_, JSMSG_TOO_MANY_CASES);
 140     return false;
 141   }
 142   caseCount_ = caseCount;
 143
 144   state_ = State::CaseCount;
 145   return true;
 146 }
 147
 148 bool SwitchEmitter::emitCond() {
 149   MOZ_ASSERT(state_ == State::CaseCount);
 150
 151   kind_ = Kind::Cond;
 152
 153   // After entering the scope if necessary, push the switch control.
 154   controlInfo_.emplace(bce_, StatementKind::Switch);
 155   top_ = bce_->bytecodeSection().offset();
 156
 157   if (!caseOffsets_.resize(caseCount_)) {
 158     ReportOutOfMemory(bce_->fc);
 159     return false;
 160   }
 161
 162   MOZ_ASSERT(top_ == bce_->bytecodeSection().offset());
 163
 164   tdzCacheCaseAndBody_.emplace(bce_);
 165
 166   state_ = State::Cond;
 167   return true;
 168 }
 169
 170 bool SwitchEmitter::emitTable(const TableGenerator& tableGen) {
 171   MOZ_ASSERT(state_ == State::CaseCount);
 172   kind_ = Kind::Table;
 173
 174   // After entering the scope if necessary, push the switch control.
 175   controlInfo_.emplace(bce_, StatementKind::Switch);
 176   top_ = bce_->bytecodeSection().offset();
 177
 178   if (!caseOffsets_.resize(tableGen.tableLength())) {
 179     ReportOutOfMemory(bce_->fc);
 180     return false;
 181   }
 182
 183   MOZ_ASSERT(top_ == bce_->bytecodeSection().offset());
 184   if (!bce_->emitN(JSOp::TableSwitch,
 185                    JSOpLength_TableSwitch - sizeof(jsbytecode))) {
 186     return false;
 187   }
 188
 189   // Skip default offset.
 190   jsbytecode* pc =
 191       bce_->bytecodeSection().code(top_ + BytecodeOffsetDiff(JUMP_OFFSET_LEN));
 192
 193   // Fill in switch bounds, which we know fit in 16-bit offsets.
 194   SET_JUMP_OFFSET(pc, tableGen.low());
 195   SET_JUMP_OFFSET(pc + JUMP_OFFSET_LEN, tableGen.high());
 196
 197   state_ = State::Table;
 198   return true;
 199 }
 200
 201 bool SwitchEmitter::emitCaseOrDefaultJump(uint32_t caseIndex, bool isDefault) {
 202   MOZ_ASSERT(kind_ == Kind::Cond);
 203
 204   if (isDefault) {
 205     if (!bce_->emitJump(JSOp::Default, &condSwitchDefaultOffset_)) {
 206       return false;
 207     }
 208     return true;
 209   }
 210
 211   JumpList caseJump;
 212   if (!bce_->emitJump(JSOp::Case, &caseJump)) {
 213     return false;
 214   }
 215   caseOffsets_[caseIndex] = caseJump.offset;
 216   lastCaseOffset_ = caseJump.offset;
 217
 218   return true;
 219 }
 220
 221 bool SwitchEmitter::prepareForCaseValue() {
 222   MOZ_ASSERT(kind_ == Kind::Cond);
 223   MOZ_ASSERT(state_ == State::Cond || state_ == State::Case);
 224
 225   if (!bce_->emit1(JSOp::Dup)) {
 226     return false;
 227   }
 228
 229   state_ = State::CaseValue;
 230   return true;
 231 }
 232
 233 bool SwitchEmitter::emitCaseJump() {
 234   MOZ_ASSERT(kind_ == Kind::Cond);
 235   MOZ_ASSERT(state_ == State::CaseValue);
 236
 237   if (!bce_->emit1(JSOp::StrictEq)) {
 238     return false;
 239   }
 240
 241   if (!emitCaseOrDefaultJump(caseIndex_, false)) {
 242     return false;
 243   }
 244   caseIndex_++;
 245
 246   state_ = State::Case;
 247   return true;
 248 }
 249
 250 bool SwitchEmitter::emitImplicitDefault() {
 251   MOZ_ASSERT(kind_ == Kind::Cond);
 252   MOZ_ASSERT(state_ == State::Cond || state_ == State::Case);
 253   if (!emitCaseOrDefaultJump(0, true)) {
 254     return false;
 255   }
 256
 257   caseIndex_ = 0;
 258
 259   // No internal state after emitting default jump.
 260   return true;
 261 }
 262
 263 bool SwitchEmitter::emitCaseBody() {
 264   MOZ_ASSERT(kind_ == Kind::Cond);
 265   MOZ_ASSERT(state_ == State::Cond || state_ == State::Case ||
 266              state_ == State::CaseBody || state_ == State::DefaultBody);
 267
 268   tdzCacheCaseAndBody_.reset();
 269
 270   if (state_ == State::Cond || state_ == State::Case) {
 271     // For cond switch, JSOp::Default is always emitted.
 272     if (!emitImplicitDefault()) {
 273       return false;
 274     }
 275   }
 276
 277   JumpList caseJump;
 278   caseJump.offset = caseOffsets_[caseIndex_];
 279   if (!bce_->emitJumpTargetAndPatch(caseJump)) {
 280     return false;
 281   }
 282
 283   JumpTarget here;
 284   if (!bce_->emitJumpTarget(&here)) {
 285     return false;
 286   }
 287   caseIndex_++;
 288
 289   tdzCacheCaseAndBody_.emplace(bce_);
 290
 291   state_ = State::CaseBody;
 292   return true;
 293 }
 294
 295 bool SwitchEmitter::emitCaseBody(int32_t caseValue,
 296                                  const TableGenerator& tableGen) {
 297   MOZ_ASSERT(kind_ == Kind::Table);
 298   MOZ_ASSERT(state_ == State::Table || state_ == State::CaseBody ||
 299              state_ == State::DefaultBody);
 300
 301   tdzCacheCaseAndBody_.reset();
 302
 303   JumpTarget here;
 304   if (!bce_->emitJumpTarget(&here)) {
 305     return false;
 306   }
 307   caseOffsets_[tableGen.toCaseIndex(caseValue)] = here.offset;
 308
 309   tdzCacheCaseAndBody_.emplace(bce_);
 310
 311   state_ = State::CaseBody;
 312   return true;
 313 }
 314
 315 bool SwitchEmitter::emitDefaultBody() {
 316   MOZ_ASSERT(state_ == State::Cond || state_ == State::Table ||
 317              state_ == State::Case || state_ == State::CaseBody);
 318   MOZ_ASSERT(!hasDefault_);
 319
 320   tdzCacheCaseAndBody_.reset();
 321
 322   if (state_ == State::Cond || state_ == State::Case) {
 323     // For cond switch, JSOp::Default is always emitted.
 324     if (!emitImplicitDefault()) {
 325       return false;
 326     }
 327   }
 328   JumpTarget here;
 329   if (!bce_->emitJumpTarget(&here)) {
 330     return false;
 331   }
 332   defaultJumpTargetOffset_ = here;
 333
 334   tdzCacheCaseAndBody_.emplace(bce_);
 335
 336   hasDefault_ = true;
 337   state_ = State::DefaultBody;
 338   return true;
 339 }
 340
 341 bool SwitchEmitter::emitEnd() {
 342   MOZ_ASSERT(state_ == State::Cond || state_ == State::Table ||
 343              state_ == State::CaseBody || state_ == State::DefaultBody);
 344
 345   tdzCacheCaseAndBody_.reset();
 346
 347   if (!hasDefault_) {
 348     // If no default case, offset for default is to end of switch.
 349     if (!bce_->emitJumpTarget(&defaultJumpTargetOffset_)) {
 350       return false;
 351     }
 352   }
 353   MOZ_ASSERT(defaultJumpTargetOffset_.offset.valid());
 354
 355   // Set the default offset (to end of switch if no default).
 356   jsbytecode* pc;
 357   if (kind_ == Kind::Cond) {
 358     pc = nullptr;
 359     bce_->patchJumpsToTarget(condSwitchDefaultOffset_,
 360                              defaultJumpTargetOffset_);
 361   } else {
 362     // Fill in the default jump target.
 363     pc = bce_->bytecodeSection().code(top_);
 364     SET_JUMP_OFFSET(pc, (defaultJumpTargetOffset_.offset - top_).value());
 365     pc += JUMP_OFFSET_LEN;
 366   }
 367
 368   if (kind_ == Kind::Table) {
 369     // Skip over the already-initialized switch bounds.
 370     pc += 2 * JUMP_OFFSET_LEN;
 371
 372     // Use the 'default' offset for missing cases.
 373     for (uint32_t i = 0, length = caseOffsets_.length(); i < length; i++) {
 374       if (caseOffsets_[i].value() == 0) {
 375         caseOffsets_[i] = defaultJumpTargetOffset_.offset;
 376       }
 377     }
 378
 379     // Allocate resume index range.
 380     uint32_t firstResumeIndex = 0;
 381     mozilla::Span<BytecodeOffset> offsets =
 382         mozilla::Span(caseOffsets_.begin(), caseOffsets_.end());
 383     if (!bce_->allocateResumeIndexRange(offsets, &firstResumeIndex)) {
 384       return false;
 385     }
 386     SET_RESUMEINDEX(pc, firstResumeIndex);
 387   }
 388
 389   // Patch breaks before leaving the scope, as all breaks are under the
 390   // lexical scope if it exists.
 391   if (!controlInfo_->patchBreaks(bce_)) {
 392     return false;
 393   }
 394
 395   if (emitterScope_ && !emitterScope_->leave(bce_)) {
 396     return false;
 397   }
 398
 399   emitterScope_.reset();
 400   tdzCacheLexical_.reset();
 401
 402   controlInfo_.reset();
 403
 404   state_ = State::End;
 405   return true;
 406 }
 407
 408 InternalSwitchEmitter::InternalSwitchEmitter(BytecodeEmitter* bce)
 409     : SwitchEmitter(bce) {
 410 #ifdef DEBUG
 411   // Skip emitDiscriminant (see the comment above InternalSwitchEmitter)
 412   state_ = State::Discriminant;
 413 #endif
 414 }