diff options
| -rw-r--r-- | src/passes/DeadArgumentElimination.cpp | 84 | ||||
| -rw-r--r-- | test/lit/passes/dae-gc.wast | 250 |
2 files changed, 332 insertions, 2 deletions
diff --git a/src/passes/DeadArgumentElimination.cpp b/src/passes/DeadArgumentElimination.cpp index a2231469d..ddba3bee8 100644 --- a/src/passes/DeadArgumentElimination.cpp +++ b/src/passes/DeadArgumentElimination.cpp @@ -43,6 +43,7 @@ #include "ir/find_all.h" #include "ir/module-utils.h" #include "ir/type-updating.h" +#include "ir/utils.h" #include "pass.h" #include "passes/opt-utils.h" #include "support/sorted_vector.h" @@ -308,6 +309,9 @@ struct DAE : public Pass { allDroppedCalls[pair.first] = pair.second; } } + // If we refine return types then we will need to do more type updating + // at the end. + bool refinedReturnTypes = false; // We now have a mapping of all call sites for each function, and can look // for optimization opportunities. for (auto& pair : allCalls) { @@ -323,6 +327,10 @@ struct DAE : public Pass { // affect whether an argument is used or not, it just refines the type // where possible. refineArgumentTypes(func, calls, module); + // Refine return types as well. + if (refineReturnTypes(func, calls, module)) { + refinedReturnTypes = true; + } // Check if all calls pass the same constant for a particular argument. for (Index i = 0; i < numParams; i++) { Literal value; @@ -357,6 +365,12 @@ struct DAE : public Pass { } } } + if (refinedReturnTypes) { + // Changing a call expression's return type can propagate out to its + // parents, and so we must refinalize. + // TODO: We could track in which functions we actually make changes. + ReFinalize().run(runner, module); + } // Track which functions we changed, and optimize them later if necessary. std::unordered_set<Function*> changed; // We now know which parameters are unused, and can potentially remove them. @@ -444,7 +458,7 @@ struct DAE : public Pass { if (optimize && !changed.empty()) { OptUtils::optimizeAfterInlining(changed, module, runner); } - return !changed.empty(); + return !changed.empty() || refinedReturnTypes; } private: @@ -591,6 +605,74 @@ private: } } } + + // See if the types returned from a function allow us to define a more refined + // return type for it. If so, we can update it and all calls going to it. + // + // This assumes that the function has no calls aside from |calls|, that is, it + // is not exported or called from the table or by reference. Exports should be + // fine, as should indirect calls in principle, but VMs will need to support + // function subtyping in indirect calls. TODO: relax this when possible + // + // Returns whether we optimized. + // + // TODO: We may be missing a global optimum here, as e.g. if a function calls + // itself and returns that value, then we would not do any change here, + // as one of the return values is exactly what it already is. Similar + // unoptimality can happen with multiple functions, more local code in + // the middle, etc. + bool refineReturnTypes(Function* func, + const std::vector<Call*>& calls, + Module* module) { + if (!module->features.hasGC()) { + return false; + } + + Type originalType = func->getResults(); + if (!originalType.hasRef()) { + // Nothing to refine. + return false; + } + + // Before we do anything, we must refinalize the function, because otherwise + // its body may contain a block with a forced type, + // + // (func (result X) + // (block (result X) + // (..content with more specific type Y..) + // ) + ReFinalize().walkFunctionInModule(func, module); + + Type refinedType = func->body->type; + if (refinedType == originalType) { + return false; + } + + // Scan the body and look at the returns. + for (auto* ret : FindAll<Return>(func->body).list) { + refinedType = Type::getLeastUpperBound(refinedType, ret->value->type); + if (refinedType == originalType) { + return false; + } + } + assert(refinedType != originalType); + + // If the refined type is unreachable then nothing actually returns from + // this function. + // TODO: We can propagate that to the outside, and not just for GC. + if (refinedType == Type::unreachable) { + return false; + } + + // Success. Update the type, and the calls. + func->setResults(refinedType); + for (auto* call : calls) { + if (call->type != Type::unreachable) { + call->type = refinedType; + } + } + return true; + } }; Pass* createDAEPass() { return new DAE(); } diff --git a/test/lit/passes/dae-gc.wast b/test/lit/passes/dae-gc.wast index b3f8eddd2..f80673cf2 100644 --- a/test/lit/passes/dae-gc.wast +++ b/test/lit/passes/dae-gc.wast @@ -9,10 +9,11 @@ (type ${i32} (struct (field i32))) ;; CHECK: (type ${i32_i64} (struct (field i32) (field i64))) + ;; CHECK: (type ${i32_f32} (struct (field i32) (field f32))) + ;; CHECK: (type ${f64} (struct (field f64))) (type ${f64} (struct (field f64))) (type ${i32_i64} (struct (field i32) (field i64))) - ;; CHECK: (type ${i32_f32} (struct (field i32) (field f32))) (type ${i32_f32} (struct (field i32) (field f32))) ;; CHECK: (func $foo @@ -293,4 +294,251 @@ ;; "Use" the local to avoid other optimizations kicking in. (drop (local.get $x)) ) + + ;; We cannot refine the return type if nothing is actually returned. + ;; CHECK: (func $refine-return-no-return (result anyref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-no-return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $refine-return-no-return (result anyref) + ;; Call this function, so that we attempt to optimize it. Note that we do not + ;; just drop the result, as that would cause the drop optimizations to kick + ;; in. + (local $temp anyref) + (local.set $temp (call $refine-return-no-return)) + + (unreachable) + ) + + ;; We cannot refine the return type if it is already the best it can be. + ;; CHECK: (func $refine-return-no-refining (result anyref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-no-refining) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null any) + ;; CHECK-NEXT: ) + (func $refine-return-no-refining (result anyref) + (local $temp anyref) + (local.set $temp (call $refine-return-no-refining)) + + (ref.null any) + ) + + ;; Refine the return type based on the value flowing out. + ;; CHECK: (func $refine-return-flow (result funcref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-flow) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + (func $refine-return-flow (result anyref) + (local $temp anyref) + (local.set $temp (call $refine-return-flow)) + + (ref.null func) + ) + ;; CHECK: (func $call-refine-return-flow (result funcref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $call-refine-return-flow) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if (result funcref) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (call $refine-return-flow) + ;; CHECK-NEXT: (call $refine-return-flow) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $call-refine-return-flow (result anyref) + (local $temp anyref) + (local.set $temp (call $call-refine-return-flow)) + + ;; After refining the return value of the above function, refinalize will + ;; update types here, which will lead to updating the if, and then the entire + ;; function's return value. + (if (result anyref) + (i32.const 1) + (call $refine-return-flow) + (call $refine-return-flow) + ) + ) + + ;; Refine the return type based on a return. + ;; CHECK: (func $refine-return-return (result funcref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-return) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $refine-return-return (result anyref) + (local $temp anyref) + (local.set $temp (call $refine-return-return)) + + (return (ref.null func)) + ) + + ;; Refine the return type based on multiple values. + ;; CHECK: (func $refine-return-many (result funcref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-many) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + (func $refine-return-many (result anyref) + (local $temp anyref) + (local.set $temp (call $refine-return-many)) + + (if + (i32.const 1) + (return (ref.null func)) + ) + (if + (i32.const 2) + (return (ref.null func)) + ) + (ref.null func) + ) + + ;; CHECK: (func $refine-return-many-blocked (result anyref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-many-blocked) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null data) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + (func $refine-return-many-blocked (result anyref) + (local $temp anyref) + (local.set $temp (call $refine-return-many-blocked)) + + (if + (i32.const 1) + (return (ref.null func)) + ) + (if + (i32.const 2) + ;; The refined return value is blocked by this return. + (return (ref.null data)) + ) + (ref.null func) + ) + + ;; CHECK: (func $refine-return-many-blocked-2 (result anyref) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-many-blocked-2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null data) + ;; CHECK-NEXT: ) + (func $refine-return-many-blocked-2 (result anyref) + (local $temp anyref) + (local.set $temp (call $refine-return-many-blocked-2)) + + (if + (i32.const 1) + (return (ref.null func)) + ) + (if + (i32.const 2) + (return (ref.null func)) + ) + ;; The refined return value is blocked by this value. + (ref.null data) + ) + + ;; CHECK: (func $refine-return-many-middle (result (ref null ${i32})) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (call $refine-return-many-middle) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (return + ;; CHECK-NEXT: (ref.null ${i32_i64}) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null ${i32_f32}) + ;; CHECK-NEXT: ) + (func $refine-return-many-middle (result anyref) + (local $temp anyref) + (local.set $temp (call $refine-return-many-middle)) + + ;; Return two different struct types, with an LUB that is not equal to either + ;; of them. + (if + (i32.const 1) + (return (ref.null ${i32_i64})) + ) + (ref.null ${i32_f32}) + ) + + ;; We can refine the return types of tuples. + ;; CHECK: (func $refine-return-tuple (result funcref i32) + ;; CHECK-NEXT: (local $temp anyref) + ;; CHECK-NEXT: (local.set $temp + ;; CHECK-NEXT: (tuple.extract 0 + ;; CHECK-NEXT: (call $refine-return-tuple) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (tuple.make + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $refine-return-tuple (result anyref i32) + (local $temp anyref) + (local.set $temp + (tuple.extract 0 + (call $refine-return-tuple) + ) + ) + + (tuple.make + (ref.null func) + (i32.const 1) + ) + ) ) |