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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
/*
* Copyright 2021 WebAssembly Community Group participants
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef wasm_ir_lubs_h
#define wasm_ir_lubs_h
#include "ir/module-utils.h"
#include "wasm.h"
namespace wasm {
//
// Helper to find a LUB of a series of expressions. This works incrementally so
// that if we see we are not improving on an existing type then we can stop
// early. It also notes null expressions that can be updated later, and if
// updating them would allow a better LUB it can do so. That is, given this:
//
// (ref.null any) ;; an expression that we can update
// (.. something of type data ..)
//
// We can update that null to type (ref null data) which would allow setting
// that as the LUB. This is important in cases where there is a null initial
// value in a field, for example: we should not let the type there prevent us
// from optimizing - after all, all nulls compare equally anyhow.
//
struct LUBFinder {
LUBFinder() {}
LUBFinder(Type initialType) { note(initialType); }
// Note another type to take into account in the lub.
void note(Type type) { lub = Type::getLeastUpperBound(lub, type); }
// Note an expression that can be updated, that is, that we can modify in
// safe ways if doing so would allow us to get a better lub. The specific
// optimization possible here involves nulls, see the top comment.
void noteUpdatableExpression(Expression* curr) {
if (auto* null = curr->dynCast<RefNull>()) {
nulls.insert(null);
} else {
note(curr->type);
}
}
void noteNullDefault() {
// A default value is indicated by a null pointer.
nulls.insert(nullptr);
}
// Returns whether we noted any (reachable) value. This ignores nulls, as they
// do not contribute type information - we do not try to find a lub based on
// them (rather we update them to the LUB).
bool noted() { return lub != Type::unreachable; }
// Returns the best possible lub. This ignores updatable nulls for the reasons
// mentioned above, since they will not limit us, aside from making the type
// nullable if nulls exist. This does not update the nulls.
Type getBestPossible() {
if (lub == Type::unreachable) {
// Perhaps if we have seen nulls we could compute a lub on them, but it's
// not clear that is helpful.
return lub;
}
// We have a lub. Make it nullable if we need to.
if (!lub.isNullable() && !nulls.empty()) {
return Type(lub.getHeapType(), Nullable);
} else {
return lub;
}
}
// Update the nulls for the best possible LUB, if we found one.
void updateNulls() {
auto newType = getBestPossible();
if (newType != Type::unreachable) {
for (auto* null : nulls) {
// Default null values (represented as nullptr here) do not need to be
// updated. Aside from that, if this null is already of a more specific
// type, also do not update it - it's never worth making a type less
// specific. What we care about here is making sure the nulls are all
// specific enough given the LUB that is being applied.
if (null && !Type::isSubType(null->type, newType)) {
null->finalize(newType);
}
}
}
}
// Combines the information in another LUBFinder into this one, and returns
// whether we changed anything.
bool combine(const LUBFinder& other) {
// Check if the lub was changed.
auto old = lub;
note(other.lub);
bool changed = old != lub;
// Check if we added new updatable nulls.
for (auto* null : other.nulls) {
if (nulls.insert(null).second) {
changed = true;
}
}
return changed;
}
private:
// The least upper bound. As we go this always contains the latest value based
// on everything we've seen so far, except for nulls.
Type lub = Type::unreachable;
// Nulls that we can update. A nullptr here indicates an "implicit" null, that
// is, a null default value.
std::unordered_set<RefNull*> nulls;
};
namespace LUB {
// Given a function, computes a LUB for its results. The caller can then decide
// to apply a refined type if we found one.
//
// This modifies the called function even if it fails to find a refined type as
// it does a refinalize in order to be able to compute the new types. We could
// roll back that change, but it's not harmful and can help, so we keep it
// regardless.
LUBFinder getResultsLUB(Function* func, Module& wasm);
} // namespace LUB
} // namespace wasm
#endif // wasm_ir_lubs_h
|
