Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
       2             :  * vim: set ts=8 sts=4 et sw=4 tw=99:
       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             : #include "jit/WasmBCE.h"
       7             : #include "jit/MIRGenerator.h"
       8             : #include "jit/MIRGraph.h"
       9             : #include "wasm/WasmTypes.h"
      10             : 
      11             : using namespace js;
      12             : using namespace js::jit;
      13             : using namespace mozilla;
      14             : 
      15             : typedef js::HashMap<uint32_t, MDefinition*, DefaultHasher<uint32_t>, SystemAllocPolicy>
      16             :     LastSeenMap;
      17             : 
      18             : // The Wasm Bounds Check Elimination (BCE) pass looks for bounds checks
      19             : // on SSA values that have already been checked. (in the same block or in a
      20             : // dominating block). These bounds checks are redundant and thus eliminated.
      21             : //
      22             : // Note: This is safe in the presense of dynamic memory sizes as long as they
      23             : // can ONLY GROW. If we allow SHRINKING the heap, this pass should be
      24             : // RECONSIDERED.
      25             : //
      26             : // TODO (dbounov): Are there a lot of cases where there is no single dominating
      27             : // check, but a set of checks that together dominate a redundant check?
      28             : //
      29             : // TODO (dbounov): Generalize to constant additions relative to one base
      30             : bool
      31           0 : jit::EliminateBoundsChecks(MIRGenerator* mir, MIRGraph& graph)
      32             : {
      33             :     // Map for dominating block where a given definition was checked
      34           0 :     LastSeenMap lastSeen;
      35           0 :     if (!lastSeen.init())
      36           0 :         return false;
      37             : 
      38           0 :     for (ReversePostorderIterator bIter(graph.rpoBegin()); bIter != graph.rpoEnd(); bIter++) {
      39           0 :         MBasicBlock* block = *bIter;
      40           0 :         for (MDefinitionIterator dIter(block); dIter;) {
      41           0 :             MDefinition* def = *dIter++;
      42             : 
      43           0 :             switch (def->op()) {
      44             :               case MDefinition::Op_WasmBoundsCheck: {
      45           0 :                 MWasmBoundsCheck* bc = def->toWasmBoundsCheck();
      46           0 :                 MDefinition* addr = bc->index();
      47             : 
      48             :                 // Eliminate constant-address bounds checks to addresses below
      49             :                 // the heap minimum.
      50             :                 //
      51             :                 // The payload of the MConstant will be Double if the constant
      52             :                 // result is above 2^31-1, but we don't care about that for BCE.
      53             : 
      54             : #ifndef WASM_HUGE_MEMORY
      55             :                 MOZ_ASSERT(wasm::MaxMemoryAccessSize < wasm::GuardSize,
      56             :                            "Guard page handles partial out-of-bounds");
      57             : #endif
      58             : 
      59           0 :                 if (addr->isConstant() && addr->toConstant()->type() == MIRType::Int32 &&
      60           0 :                     uint32_t(addr->toConstant()->toInt32()) < mir->minWasmHeapLength())
      61             :                 {
      62           0 :                     bc->setRedundant();
      63             :                 }
      64             :                 else
      65             :                 {
      66           0 :                     LastSeenMap::AddPtr ptr = lastSeen.lookupForAdd(addr->id());
      67           0 :                     if (ptr) {
      68           0 :                         if (ptr->value()->block()->dominates(block))
      69           0 :                             bc->setRedundant();
      70             :                     } else {
      71           0 :                         if (!lastSeen.add(ptr, addr->id(), def))
      72           0 :                             return false;
      73             :                     }
      74             :                 }
      75           0 :                 break;
      76             :               }
      77             :               case MDefinition::Op_Phi: {
      78           0 :                 MPhi* phi = def->toPhi();
      79           0 :                 bool phiChecked = true;
      80             : 
      81           0 :                 MOZ_ASSERT(phi->numOperands() > 0);
      82             : 
      83             :                 // If all incoming values to a phi node are safe (i.e. have a
      84             :                 // check that dominates this block) then we can consider this
      85             :                 // phi node checked.
      86             :                 //
      87             :                 // Note that any phi that is part of a cycle
      88             :                 // will not be "safe" since the value coming on the backedge
      89             :                 // cannot be in lastSeen because its block hasn't been traversed yet.
      90           0 :                 for (int i = 0, nOps = phi->numOperands(); i < nOps; i++) {
      91           0 :                     MDefinition* src = phi->getOperand(i);
      92             : 
      93           0 :                     LastSeenMap::Ptr checkPtr = lastSeen.lookup(src->id());
      94           0 :                     if (!checkPtr || !checkPtr->value()->block()->dominates(block)) {
      95           0 :                         phiChecked = false;
      96           0 :                         break;
      97             :                     }
      98             :                 }
      99             : 
     100           0 :                 if (phiChecked) {
     101           0 :                     if (!lastSeen.put(def->id(), def))
     102           0 :                         return false;
     103             :                 }
     104             : 
     105           0 :                 break;
     106             :               }
     107             :               default:
     108           0 :                 break;
     109             :             }
     110             :         }
     111             :     }
     112             : 
     113           0 :     return true;
     114             : }