summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAlon Zakai <azakai@google.com>2021-11-11 11:24:44 -0800
committerGitHub <noreply@github.com>2021-11-11 11:24:44 -0800
commit50e66800dc28d67ea1cc88172f459df1ca96507d (patch)
treed4a42612823b3ba0f986d349288bfa3fa1671a1f
parenta113d39fe87e098c5b19ca75002b6995a3f69e3e (diff)
downloadbinaryen-50e66800dc28d67ea1cc88172f459df1ca96507d.tar.gz
binaryen-50e66800dc28d67ea1cc88172f459df1ca96507d.tar.bz2
binaryen-50e66800dc28d67ea1cc88172f459df1ca96507d.zip
DeadArgumentElimination argument subtyping: Add fixups if the param is used (#4319)
Before, if we saw a param is written, that prevented us from subtyping it: function foo(x : oldType) { .. x = someValue; .. } Even if all calls to foo send some specific struct type that we'd like to subtype to, seeing that write stopped us. To handle such a write we need to do some extra handling for the case in which it is written a less-specific type (that is, if someValue is of type oldType, something like this: function foo(x : newType) { var x_old : oldType; x_old = x; // copy the param to x_old, and use x_old everywhere .. x_old = someValue; .. } That is, still refine the param type, but inside the function use a new local that has the old type, and is guaranteed to validate. This PR implements that logic so that we can optimize more cases. To allow that, this PR avoids trying to both refine a type and remove a param as being unused - that has annoying corner cases. If it is unused, we can simply remove it anyhow.
-rw-r--r--src/passes/DeadArgumentElimination.cpp96
-rw-r--r--src/support/sorted_vector.h2
-rw-r--r--test/lit/passes/dae-gc-refine-params.wast157
3 files changed, 217 insertions, 38 deletions
diff --git a/src/passes/DeadArgumentElimination.cpp b/src/passes/DeadArgumentElimination.cpp
index 033e766b6..d7b4d7db2 100644
--- a/src/passes/DeadArgumentElimination.cpp
+++ b/src/passes/DeadArgumentElimination.cpp
@@ -327,7 +327,7 @@ struct DAE : public Pass {
// Refine argument types before doing anything else. This does not
// affect whether an argument is used or not, it just refines the type
// where possible.
- refineArgumentTypes(func, calls, module);
+ refineArgumentTypes(func, calls, module, infoMap[name]);
// Refine return types as well.
if (refineReturnTypes(func, calls, module)) {
refinedReturnTypes = true;
@@ -339,6 +339,7 @@ struct DAE : public Pass {
assert(call->target == name);
assert(call->operands.size() == numParams);
auto* operand = call->operands[i];
+ // TODO: refnull etc.
if (auto* c = operand->dynCast<Const>()) {
if (value.type == Type::none) {
// This is the first value seen.
@@ -544,7 +545,8 @@ private:
// is not exported or called from the table or by reference.
void refineArgumentTypes(Function* func,
const std::vector<Call*>& calls,
- Module* module) {
+ Module* module,
+ const DAEFunctionInfo& info) {
if (!module->features.hasGC()) {
return;
}
@@ -553,7 +555,13 @@ private:
newParamTypes.reserve(numParams);
for (Index i = 0; i < numParams; i++) {
auto originalType = func->getLocalType(i);
- if (!originalType.isRef()) {
+ // If the parameter type is not a reference, there is nothing to refine.
+ // And if it is unused, also do nothing, as we can leave it to the other
+ // parts of this pass to optimize it properly, which avoids having to
+ // think about corner cases involving refining the type of an unused
+ // param (in particular, unused params are turned into locals, which means
+ // we'd need to think about defaultability etc.).
+ if (!originalType.isRef() || info.unusedParams.has(i)) {
newParamTypes.push_back(originalType);
continue;
}
@@ -575,31 +583,84 @@ private:
// Check if we are able to optimize here before we do the work to scan the
// function body.
- if (Type(newParamTypes) == func->getParams()) {
+ auto newParams = Type(newParamTypes);
+ if (newParams == func->getParams()) {
return;
}
- // In terms of parameters, we can do this. However, we must also check
- // local operations in the body, as if the parameter is reused and written
- // to, then those types must be taken into account as well.
+ // We can do this!
+
+ // Before making this update, we must be careful if the param was "reused",
+ // specifically, if it is assigned a less-specific type in the body then
+ // we'd get a validation error when we refine it. To handle that, if a less-
+ // specific type is assigned simply switch to a new local, that is, we can
+ // do a fixup like this:
+ //
+ // function foo(x : oldType) {
+ // ..
+ // x = (oldType)val;
+ //
+ // =>
+ //
+ // function foo(x : newType) {
+ // var x_oldType = x; // assign the param immediately to a fixup var
+ // ..
+ // x_oldType = (oldType)val; // fixup var is used throughout the body
+ //
+ // Later optimization passes may be able to remove the extra var, and can
+ // take advantage of the refined argument type while doing so.
+
+ // A map of params that need a fixup to the new fixup var used for it.
+ std::unordered_map<Index, Index> paramFixups;
+
FindAll<LocalSet> sets(func->body);
+
for (auto* set : sets.list) {
auto index = set->index;
- if (func->isParam(index) &&
+ if (func->isParam(index) && !paramFixups.count(index) &&
!Type::isSubType(set->value->type, newParamTypes[index])) {
- // TODO: we could still optimize here, by creating a new local.
- newParamTypes[index] = func->getLocalType(index);
+ paramFixups[index] = Builder::addVar(func, func->getLocalType(index));
}
}
- auto newParams = Type(newParamTypes);
- if (newParams == func->getParams()) {
- return;
+ FindAll<LocalGet> gets(func->body);
+
+ // Apply the fixups we identified that we need.
+ if (!paramFixups.empty()) {
+ // Write the params immediately to the fixups.
+ Builder builder(*module);
+ std::vector<Expression*> contents;
+ for (Index index = 0; index < func->getNumParams(); index++) {
+ auto iter = paramFixups.find(index);
+ if (iter != paramFixups.end()) {
+ auto fixup = iter->second;
+ contents.push_back(builder.makeLocalSet(
+ fixup, builder.makeLocalGet(index, newParamTypes[index])));
+ }
+ }
+ contents.push_back(func->body);
+ func->body = builder.makeBlock(contents);
+
+ // Update gets and sets using the param to use the fixup.
+ for (auto* get : gets.list) {
+ auto iter = paramFixups.find(get->index);
+ if (iter != paramFixups.end()) {
+ get->index = iter->second;
+ }
+ }
+ for (auto* set : sets.list) {
+ auto iter = paramFixups.find(set->index);
+ if (iter != paramFixups.end()) {
+ set->index = iter->second;
+ }
+ }
}
- // We can do this! Update the types, including the types of gets and tees.
+ // Now that fixups are done, we can apply the new types.
func->setParams(newParams);
- for (auto* get : FindAll<LocalGet>(func->body).list) {
+
+ // Update local.get/local.tee operations that use the modified param type.
+ for (auto* get : gets.list) {
auto index = get->index;
if (func->isParam(index)) {
get->type = func->getLocalType(index);
@@ -615,6 +676,11 @@ private:
// Propagate the new get and set types outwards.
ReFinalize().walkFunctionInModule(func, module);
+
+ if (!paramFixups.empty()) {
+ // We have added locals, and must handle non-nullability of them.
+ TypeUpdating::handleNonDefaultableLocals(func, *module);
+ }
}
// See if the types returned from a function allow us to define a more refined
diff --git a/src/support/sorted_vector.h b/src/support/sorted_vector.h
index 5c1d9a731..234d4da7e 100644
--- a/src/support/sorted_vector.h
+++ b/src/support/sorted_vector.h
@@ -82,7 +82,7 @@ struct SortedVector : public std::vector<Index> {
return false;
}
- bool has(Index x) {
+ bool has(Index x) const {
auto it = std::lower_bound(begin(), end(), x);
return it != end() && *it == x;
}
diff --git a/test/lit/passes/dae-gc-refine-params.wast b/test/lit/passes/dae-gc-refine-params.wast
index 7ecbcc5c8..818c943b2 100644
--- a/test/lit/passes/dae-gc-refine-params.wast
+++ b/test/lit/passes/dae-gc-refine-params.wast
@@ -184,42 +184,76 @@
;; This function is called in ways that *do* allow us to alter the types of
;; its parameters (see last function), however, we reuse the parameters by
;; writing to them, which causes problems in one case.
- ;; CHECK: (func $various-params-set (param $x (ref null ${})) (param $y (ref null ${i32}))
- ;; CHECK-NEXT: (drop
+ ;; CHECK: (func $various-params-set (param $x (ref null ${i32})) (param $y (ref null ${i32}))
+ ;; CHECK-NEXT: (local $2 (ref null ${}))
+ ;; CHECK-NEXT: (local.set $2
;; CHECK-NEXT: (local.get $x)
;; CHECK-NEXT: )
- ;; CHECK-NEXT: (drop
- ;; CHECK-NEXT: (local.get $y)
- ;; CHECK-NEXT: )
- ;; CHECK-NEXT: (local.set $x
- ;; CHECK-NEXT: (ref.null ${})
- ;; CHECK-NEXT: )
- ;; CHECK-NEXT: (local.set $y
- ;; CHECK-NEXT: (ref.null ${i32_i64})
+ ;; CHECK-NEXT: (block
+ ;; CHECK-NEXT: (drop
+ ;; CHECK-NEXT: (local.get $2)
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (drop
+ ;; CHECK-NEXT: (local.get $y)
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (local.set $2
+ ;; CHECK-NEXT: (ref.null ${})
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (drop
+ ;; CHECK-NEXT: (local.get $2)
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (local.set $y
+ ;; CHECK-NEXT: (ref.null ${i32_i64})
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (drop
+ ;; CHECK-NEXT: (local.get $y)
+ ;; CHECK-NEXT: )
;; CHECK-NEXT: )
;; CHECK-NEXT: )
- ;; NOMNL: (func $various-params-set (type $ref?|${}|_ref?|${i32}|_=>_none) (param $x (ref null ${})) (param $y (ref null ${i32}))
- ;; NOMNL-NEXT: (drop
+ ;; NOMNL: (func $various-params-set (type $ref?|${i32}|_ref?|${i32}|_=>_none) (param $x (ref null ${i32})) (param $y (ref null ${i32}))
+ ;; NOMNL-NEXT: (local $2 (ref null ${}))
+ ;; NOMNL-NEXT: (local.set $2
;; NOMNL-NEXT: (local.get $x)
;; NOMNL-NEXT: )
- ;; NOMNL-NEXT: (drop
- ;; NOMNL-NEXT: (local.get $y)
- ;; NOMNL-NEXT: )
- ;; NOMNL-NEXT: (local.set $x
- ;; NOMNL-NEXT: (ref.null ${})
- ;; NOMNL-NEXT: )
- ;; NOMNL-NEXT: (local.set $y
- ;; NOMNL-NEXT: (ref.null ${i32_i64})
+ ;; NOMNL-NEXT: (block
+ ;; NOMNL-NEXT: (drop
+ ;; NOMNL-NEXT: (local.get $2)
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: (drop
+ ;; NOMNL-NEXT: (local.get $y)
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: (local.set $2
+ ;; NOMNL-NEXT: (ref.null ${})
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: (drop
+ ;; NOMNL-NEXT: (local.get $2)
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: (local.set $y
+ ;; NOMNL-NEXT: (ref.null ${i32_i64})
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: (drop
+ ;; NOMNL-NEXT: (local.get $y)
+ ;; NOMNL-NEXT: )
;; NOMNL-NEXT: )
;; NOMNL-NEXT: )
(func $various-params-set (param $x (ref null ${})) (param $y (ref null ${}))
;; "Use" the locals to avoid other optimizations kicking in.
(drop (local.get $x))
(drop (local.get $y))
- ;; Write to $x in a way that prevents us making the type more specific.
+ ;; Write to $x a value that will not fit in the refined type, which will
+ ;; force us to do a fixup: the param will get the new type, and a new local
+ ;; will stay at the old type, and we will use that local throughout the
+ ;; function.
(local.set $x (ref.null ${}))
- ;; Write to $y in a way that still allows us to make the type more specific.
+ (drop
+ (local.get $x)
+ )
+ ;; Write to $y in a way that does not cause any issue, and we should not do
+ ;; any fixup while we refine the type.
(local.set $y (ref.null ${i32_i64}))
+ (drop
+ (local.get $y)
+ )
)
;; CHECK: (func $call-various-params-tee
@@ -397,4 +431,83 @@
;; "Use" the local to avoid other optimizations kicking in.
(drop (local.get $x))
)
+
+ ;; CHECK: (func $unused-and-refinable
+ ;; CHECK-NEXT: (local $0 (ref null data))
+ ;; CHECK-NEXT: (nop)
+ ;; CHECK-NEXT: )
+ ;; NOMNL: (func $unused-and-refinable (type $none_=>_none)
+ ;; NOMNL-NEXT: (local $0 (ref null data))
+ ;; NOMNL-NEXT: (nop)
+ ;; NOMNL-NEXT: )
+ (func $unused-and-refinable (param $0 dataref)
+ ;; This function does not use $0. It is called with ${}, so it is also
+ ;; a parameter whose type we can refine. Do not do both operations: instead,
+ ;; just remove it because it is ignored, without altering the type (handling
+ ;; both operations would introduce some corner cases, and it just isn't worth
+ ;; handling them if the param is completely unused anyhow). We should see in
+ ;; the test output that the local $0 (the unused param) becomes a local
+ ;; because it is unused, and that local does *not* have its type refined to
+ ;; ${} (it will however be changed to be nullable, which it must be as a
+ ;; local).
+ )
+
+ ;; CHECK: (func $call-unused-and-refinable
+ ;; CHECK-NEXT: (call $unused-and-refinable)
+ ;; CHECK-NEXT: )
+ ;; NOMNL: (func $call-unused-and-refinable (type $none_=>_none)
+ ;; NOMNL-NEXT: (call $unused-and-refinable)
+ ;; NOMNL-NEXT: )
+ (func $call-unused-and-refinable
+ (call $unused-and-refinable
+ (struct.new_default ${})
+ )
+ )
+
+ ;; CHECK: (func $non-nullable-fixup (param $0 (ref ${}))
+ ;; CHECK-NEXT: (local $1 (ref null data))
+ ;; CHECK-NEXT: (local.set $1
+ ;; CHECK-NEXT: (local.get $0)
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: (local.set $1
+ ;; CHECK-NEXT: (ref.as_non_null
+ ;; CHECK-NEXT: (local.get $1)
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: )
+ ;; NOMNL: (func $non-nullable-fixup (type $ref|${}|_=>_none) (param $0 (ref ${}))
+ ;; NOMNL-NEXT: (local $1 (ref null data))
+ ;; NOMNL-NEXT: (local.set $1
+ ;; NOMNL-NEXT: (local.get $0)
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: (local.set $1
+ ;; NOMNL-NEXT: (ref.as_non_null
+ ;; NOMNL-NEXT: (local.get $1)
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: )
+ (func $non-nullable-fixup (param $0 dataref)
+ ;; Use the param to avoid other opts removing it, and to force us to do a
+ ;; fixup when we refine the param's type. When doing so, we must handle the
+ ;; fact that the new local's type is non-nullable.
+ (local.set $0
+ (local.get $0)
+ )
+ )
+
+ ;; CHECK: (func $call-non-nullable-fixup
+ ;; CHECK-NEXT: (call $non-nullable-fixup
+ ;; CHECK-NEXT: (struct.new_default ${})
+ ;; CHECK-NEXT: )
+ ;; CHECK-NEXT: )
+ ;; NOMNL: (func $call-non-nullable-fixup (type $none_=>_none)
+ ;; NOMNL-NEXT: (call $non-nullable-fixup
+ ;; NOMNL-NEXT: (struct.new_default ${})
+ ;; NOMNL-NEXT: )
+ ;; NOMNL-NEXT: )
+ (func $call-non-nullable-fixup
+ (call $non-nullable-fixup
+ (struct.new_default ${})
+ )
+ )
)