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/. */
7 #include "jit/WasmBCE.h"
9 #include "jit/JitSpewer.h"
10 #include "jit/MIRGenerator.h"
11 #include "jit/MIRGraph.h"
14 using namespace js::jit
;
16 typedef js::HashMap
<uint32_t, MDefinition
*, DefaultHasher
<uint32_t>,
20 // The Wasm Bounds Check Elimination (BCE) pass looks for bounds checks
21 // on SSA values that have already been checked. (in the same block or in a
22 // dominating block). These bounds checks are redundant and thus eliminated.
24 // Note: This is safe in the presense of dynamic memory sizes as long as they
25 // can ONLY GROW. If we allow SHRINKING the heap, this pass should be
28 // TODO (dbounov): Are there a lot of cases where there is no single dominating
29 // check, but a set of checks that together dominate a redundant check?
31 // TODO (dbounov): Generalize to constant additions relative to one base
32 bool jit::EliminateBoundsChecks(MIRGenerator
* mir
, MIRGraph
& graph
) {
33 JitSpew(JitSpew_WasmBCE
, "Begin");
34 // Map for dominating block where a given definition was checked
37 for (ReversePostorderIterator
bIter(graph
.rpoBegin());
38 bIter
!= graph
.rpoEnd(); bIter
++) {
39 MBasicBlock
* block
= *bIter
;
40 for (MDefinitionIterator
dIter(block
); dIter
;) {
41 MDefinition
* def
= *dIter
++;
44 case MDefinition::Opcode::WasmBoundsCheck
: {
45 MWasmBoundsCheck
* bc
= def
->toWasmBoundsCheck();
46 MDefinition
* addr
= bc
->index();
48 // We only support bounds check elimination on wasm memory 0, not
49 // other memories or tables. See bug 1625891.
50 if (!bc
->isMemory0()) {
54 // Eliminate constant-address memory bounds checks to addresses below
57 // The payload of the MConstant will be Double if the constant
58 // result is above 2^31-1, but we don't care about that for BCE.
60 if (addr
->isConstant() &&
61 ((addr
->toConstant()->type() == MIRType::Int32
&&
62 uint64_t(addr
->toConstant()->toInt32()) <
63 mir
->minWasmMemory0Length()) ||
64 (addr
->toConstant()->type() == MIRType::Int64
&&
65 uint64_t(addr
->toConstant()->toInt64()) <
66 mir
->minWasmMemory0Length()))) {
68 if (JitOptions
.spectreIndexMasking
) {
69 bc
->replaceAllUsesWith(addr
);
71 MOZ_ASSERT(!bc
->hasUses());
74 LastSeenMap::AddPtr ptr
= lastSeen
.lookupForAdd(addr
->id());
76 MDefinition
* prevCheckOrPhi
= ptr
->value();
77 if (prevCheckOrPhi
->block()->dominates(block
)) {
79 if (JitOptions
.spectreIndexMasking
) {
80 bc
->replaceAllUsesWith(prevCheckOrPhi
);
82 MOZ_ASSERT(!bc
->hasUses());
86 if (!lastSeen
.add(ptr
, addr
->id(), def
)) {
93 case MDefinition::Opcode::Phi
: {
94 MPhi
* phi
= def
->toPhi();
95 bool phiChecked
= true;
97 MOZ_ASSERT(phi
->numOperands() > 0);
99 // If all incoming values to a phi node are safe (i.e. have a
100 // check that dominates this block) then we can consider this
103 // Note that any phi that is part of a cycle
104 // will not be "safe" since the value coming on the backedge
105 // cannot be in lastSeen because its block hasn't been traversed yet.
106 for (int i
= 0, nOps
= phi
->numOperands(); i
< nOps
; i
++) {
107 MDefinition
* src
= phi
->getOperand(i
);
109 if (JitOptions
.spectreIndexMasking
) {
110 if (src
->isWasmBoundsCheck()) {
111 src
= src
->toWasmBoundsCheck()->index();
114 MOZ_ASSERT(!src
->isWasmBoundsCheck());
117 LastSeenMap::Ptr checkPtr
= lastSeen
.lookup(src
->id());
118 if (!checkPtr
|| !checkPtr
->value()->block()->dominates(block
)) {
125 if (!lastSeen
.put(def
->id(), def
)) {