diff options
| -rw-r--r-- | src/passes/DeadArgumentElimination.cpp | 96 | ||||
| -rw-r--r-- | src/support/sorted_vector.h | 2 | ||||
| -rw-r--r-- | test/lit/passes/dae-gc-refine-params.wast | 157 |
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 ${}) + ) + ) ) |