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