tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

WasmBCE.cpp (4869B)

      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 "jit/WasmBCE.h"
      8 
      9 #include "jit/JitSpewer.h"
     10 #include "jit/MIRGenerator.h"
     11 #include "jit/MIRGraph.h"
     12 #include "wasm/WasmMetadata.h"
     13 
     14 using mozilla::HashGeneric;
     15 
     16 using namespace js;
     17 using namespace js::jit;
     18 
     19 struct LastCheckedKey {
     20  // The type of collection being bounds checked (e.g. a memory or a table).
     21  MWasmBoundsCheck::Target target;
     22 
     23  // The index of the collection being bounds checked (e.g. memory 0).
     24  uint32_t targetIndex;
     25 
     26  // The MIR ID of the address being bounds checked.
     27  uint32_t addressID;
     28 
     29  using Lookup = LastCheckedKey;
     30  static HashNumber hash(const Lookup& l) {
     31    return HashGeneric(l.target, l.targetIndex, l.addressID);
     32  }
     33  static bool match(const LastCheckedKey& lhs, const Lookup& rhs) {
     34    return lhs.target == rhs.target && lhs.targetIndex == rhs.targetIndex &&
     35           lhs.addressID == rhs.addressID;
     36  }
     37 };
     38 
     39 using LastCheckedMap = js::HashMap<LastCheckedKey, MWasmBoundsCheck*,
     40                                   LastCheckedKey, SystemAllocPolicy>;
     41 
     42 // The Wasm Bounds Check Elimination (BCE) pass looks for bounds checks
     43 // on SSA values that have already been checked (in the same block or in a
     44 // dominating block). These bounds checks are redundant and thus eliminated.
     45 //
     46 // Note: This is safe in the presence of dynamic memory sizes as long as they
     47 // can ONLY GROW. If we allow SHRINKING the heap, this pass should be
     48 // RECONSIDERED.
     49 //
     50 // TODO (dbounov): Are there a lot of cases where there is no single dominating
     51 // check, but a set of checks that together dominate a redundant check?
     52 //
     53 // TODO (dbounov): Generalize to constant additions relative to one base
     54 bool jit::EliminateBoundsChecks(const MIRGenerator* mir, MIRGraph& graph) {
     55  JitSpew(JitSpew_WasmBCE, "Begin");
     56  // Map for dominating block where a given definition was checked
     57  LastCheckedMap lastChecked;
     58 
     59  for (ReversePostorderIterator bIter(graph.rpoBegin());
     60       bIter != graph.rpoEnd(); bIter++) {
     61    MBasicBlock* block = *bIter;
     62    for (MDefinitionIterator dIter(block); dIter;) {
     63      MDefinition* def = *dIter++;
     64 
     65      if (!def->isWasmBoundsCheck()) {
     66        continue;
     67      }
     68 
     69      MWasmBoundsCheck* bc = def->toWasmBoundsCheck();
     70      MDefinition* addr = bc->index();
     71 
     72      if (bc->target() == MWasmBoundsCheck::Other) {
     73        continue;
     74      }
     75 
     76      if (addr->isConstant()) {
     77        // Eliminate constant-address bounds checks to addresses below
     78        // the memory/table minimum length.
     79 
     80        uint64_t addrConstantValue = UINT64_MAX;
     81        switch (addr->type()) {
     82          case MIRType::Int32: {
     83            addrConstantValue = addr->toConstant()->toInt32();
     84          } break;
     85          case MIRType::Int64: {
     86            addrConstantValue = addr->toConstant()->toInt64();
     87          } break;
     88          default:
     89            break;
     90        }
     91 
     92        uint64_t initialLength = 0;
     93        switch (bc->target()) {
     94          case MWasmBoundsCheck::Memory: {
     95            initialLength = mir->wasmCodeMeta()
     96                                ->memories[bc->targetIndex()]
     97                                .initialLength();
     98          } break;
     99          case MWasmBoundsCheck::Table: {
    100            initialLength =
    101                mir->wasmCodeMeta()->tables[bc->targetIndex()].initialLength();
    102          } break;
    103          default:
    104            MOZ_CRASH();
    105        }
    106 
    107        if (addrConstantValue < initialLength) {
    108          bc->setRedundant();
    109          if (JitOptions.spectreIndexMasking) {
    110            bc->replaceAllUsesWith(addr);
    111          } else {
    112            MOZ_ASSERT(!bc->hasUses());
    113          }
    114        }
    115      } else {
    116        // Eliminate bounds checks that are dominated by another bounds check of
    117        // the same value.
    118 
    119        LastCheckedKey key = (LastCheckedKey){
    120            .target = bc->target(),
    121            .targetIndex = bc->targetIndex(),
    122            .addressID = addr->id(),
    123        };
    124        LastCheckedMap::AddPtr ptr = lastChecked.lookupForAdd(key);
    125        if (!ptr) {
    126          // We have not yet seen a bounds check for this address; track it.
    127          if (!lastChecked.add(ptr, key, bc)) {
    128            return false;
    129          }
    130        } else {
    131          MWasmBoundsCheck* prevCheckOfSameAddr = ptr->value();
    132          if (prevCheckOfSameAddr->block()->dominates(block)) {
    133            bc->setRedundant();
    134            if (JitOptions.spectreIndexMasking) {
    135              bc->replaceAllUsesWith(prevCheckOfSameAddr);
    136            } else {
    137              MOZ_ASSERT(!bc->hasUses());
    138            }
    139          }
    140        }
    141      }
    142    }
    143  }
    144 
    145  return true;
    146 }