diff options
| -rw-r--r-- | src/passes/ConstantFieldPropagation.cpp | 66 | ||||
| -rw-r--r-- | test/lit/passes/cfp.wast | 298 |
2 files changed, 347 insertions, 17 deletions
diff --git a/src/passes/ConstantFieldPropagation.cpp b/src/passes/ConstantFieldPropagation.cpp index 7b13b1766..f4476ef04 100644 --- a/src/passes/ConstantFieldPropagation.cpp +++ b/src/passes/ConstantFieldPropagation.cpp @@ -53,20 +53,23 @@ struct Many : public std::monostate {}; // Represents data about what constant values are possible in a particular // place. There may be no values, or one, or many, or if a non-constant value is // possible, then all we can say is that the value is "unknown" - it can be -// anything. +// anything. The values can either be literal values (Literal) or the names of +// immutable globals (Name). // // Currently this just looks for a single constant value, and even two constant // values are treated as unknown. It may be worth optimizing more than that TODO struct PossibleConstantValues { private: - std::variant<None, Literal, Many> value; + using Variant = std::variant<None, Literal, Name, Many>; + Variant value; public: PossibleConstantValues() : value(None()) {} // Note a written value as we see it, and update our internal knowledge based - // on it and all previous values noted. - void note(Literal curr) { + // on it and all previous values noted. This can be called using either a + // Literal or a Name, so it uses a template. + template<typename T> void note(T curr) { if (std::get_if<None>(&value)) { // This is the first value. value = curr; @@ -79,9 +82,9 @@ public: } // This is a subsequent value. Check if it is different from all previous - // ones, and if so, we now represent many possible values. - if (curr != std::get<Literal>(value)) { - value = Many(); + // ones. + if (Variant(curr) != value) { + noteUnknown(); } } @@ -117,14 +120,25 @@ public: } // Check if all the values are identical and constant. - bool isConstant() const { return std::get_if<Literal>(&value); } + bool isConstant() const { + return !std::get_if<None>(&value) && !std::get_if<Many>(&value); + } + + bool isConstantLiteral() const { return std::get_if<Literal>(&value); } + + bool isConstantGlobal() const { return std::get_if<Name>(&value); } // Returns the single constant value. - Literal getConstantValue() const { + Literal getConstantLiteral() const { assert(isConstant()); return std::get<Literal>(value); } + Name getConstantGlobal() const { + assert(isConstant()); + return std::get<Name>(value); + } + // Returns whether we have ever noted a value. bool hasNoted() const { return !std::get_if<None>(&value); } @@ -134,8 +148,10 @@ public: o << "unwritten"; } else if (!isConstant()) { o << "unknown"; - } else { - o << getConstantValue(); + } else if (isConstantLiteral()) { + o << getConstantLiteral(); + } else if (isConstantGlobal()) { + o << '$' << getConstantGlobal(); } o << ']'; } @@ -200,9 +216,14 @@ struct FunctionOptimizer : public WalkerPass<PostWalker<FunctionOptimizer>> { // ref.as_non_null (we need to trap as the get would have done so), plus the // constant value. (Leave it to further optimizations to get rid of the // ref.) + Expression* value; + if (info.isConstantLiteral()) { + value = builder.makeConstantExpression(info.getConstantLiteral()); + } else { + value = builder.makeGlobalGet(info.getConstantGlobal(), curr->type); + } replaceCurrent(builder.makeSequence( - builder.makeDrop(builder.makeRefAs(RefAsNonNull, curr->ref)), - builder.makeConstantExpression(info.getConstantValue()))); + builder.makeDrop(builder.makeRefAs(RefAsNonNull, curr->ref)), value)); changed = true; } @@ -236,12 +257,23 @@ struct PCVScanner : public Scanner<PossibleConstantValues, PCVScanner> { HeapType type, Index index, PossibleConstantValues& info) { - - if (!Properties::isConstantExpression(expr)) { - info.noteUnknown(); - } else { + // If this is a constant literal value, note that. + if (Properties::isConstantExpression(expr)) { info.note(Properties::getLiteral(expr)); + return; + } + + // If this is an immutable global that we get, note that. + if (auto* get = expr->dynCast<GlobalGet>()) { + auto* global = getModule()->getGlobal(get->name); + if (global->mutable_ == Immutable) { + info.note(get->name); + return; + } } + + // Otherwise, this is not something we can reason about. + info.noteUnknown(); } void noteDefault(Type fieldType, diff --git a/test/lit/passes/cfp.wast b/test/lit/passes/cfp.wast index 99fd9d209..90eecf01b 100644 --- a/test/lit/passes/cfp.wast +++ b/test/lit/passes/cfp.wast @@ -1872,3 +1872,301 @@ ) ) ) + +(module + ;; CHECK: (type $struct (struct_subtype (field i32) data)) + (type $struct (struct i32)) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + + ;; CHECK: (global $global i32 (i32.const 42)) + (global $global i32 (i32.const 42)) + + ;; CHECK: (func $test + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test + ;; An immutable global is the only thing written to this field, so we can + ;; propagate the value to the struct.get and replace it with a global.get. + (drop + (struct.new $struct + (global.get $global) + ) + ) + (drop + (struct.get $struct 0 + (ref.null $struct) + ) + ) + ) +) + +(module + ;; CHECK: (type $struct (struct_subtype (field i32) data)) + (type $struct (struct i32)) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + + ;; CHECK: (global $global (mut i32) (i32.const 42)) + (global $global (mut i32) (i32.const 42)) + + ;; CHECK: (func $test + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test + ;; As above, but the global is *not* immutable, so we cannot optimize. + (drop + (struct.new $struct + (global.get $global) + ) + ) + (drop + (struct.get $struct 0 + (ref.null $struct) + ) + ) + ) +) + +(module + ;; CHECK: (type $struct (struct_subtype (field (mut i32)) data)) + (type $struct (struct (mut i32))) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + + ;; CHECK: (global $global i32 (i32.const 42)) + (global $global i32 (i32.const 42)) + + ;; CHECK: (func $test + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.set $struct 0 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test + (drop + (struct.new $struct + (global.get $global) + ) + ) + ;; As above, but there is another set of the field. It is the same, though, + ;; so that is fine. Also, the struct's field is now mutable as well to allow + ;; that, and that also does not prevent optimization. + (struct.set $struct 0 + (ref.null $struct) + (global.get $global) + ) + (drop + (struct.get $struct 0 + (ref.null $struct) + ) + ) + ) +) + +(module + ;; CHECK: (type $struct (struct_subtype (field (mut i32)) data)) + (type $struct (struct (mut i32))) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + + ;; CHECK: (global $global i32 (i32.const 42)) + (global $global i32 (i32.const 42)) + ;; CHECK: (global $global-2 i32 (i32.const 1337)) + (global $global-2 i32 (i32.const 1337)) + + ;; CHECK: (func $test + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.set $struct 0 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: (global.get $global-2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test + (drop + (struct.new $struct + (global.get $global) + ) + ) + ;; As above, but set a different global, which prevents optimization. + (struct.set $struct 0 + (ref.null $struct) + (global.get $global-2) + ) + (drop + (struct.get $struct 0 + (ref.null $struct) + ) + ) + ) +) + +(module + ;; CHECK: (type $struct (struct_subtype (field (mut i32)) data)) + (type $struct (struct (mut i32))) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + + ;; CHECK: (global $global i32 (i32.const 42)) + (global $global i32 (i32.const 42)) + ;; CHECK: (global $global-2 i32 (i32.const 1337)) + (global $global-2 i32 (i32.const 1337)) + + ;; CHECK: (func $test + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.set $struct 0 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: (i32.const 1337) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test + (drop + (struct.new $struct + (global.get $global) + ) + ) + ;; As above, but set a constant, which means we are mixing constants with + ;; globals, which prevents the optimization. + (struct.set $struct 0 + (ref.null $struct) + (i32.const 1337) + ) + (drop + (struct.get $struct 0 + (ref.null $struct) + ) + ) + ) +) + +(module + ;; Test a global type other than i32. Arrays of structs are a realistic case + ;; as they are used to implement itables. + + ;; CHECK: (type $vtable (struct_subtype (field funcref) data)) + (type $vtable (struct funcref)) + + ;; CHECK: (type $itable (array_subtype (ref $vtable) data)) + (type $itable (array (ref $vtable))) + + ;; CHECK: (type $object (struct_subtype (field $itable (ref $itable)) data)) + (type $object (struct (field $itable (ref $itable)))) + + ;; CHECK: (type $none_=>_funcref (func_subtype (result funcref) func)) + + ;; CHECK: (global $global (ref $itable) (array.init_static $itable + ;; CHECK-NEXT: (struct.new $vtable + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new $vtable + ;; CHECK-NEXT: (ref.func $test) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: )) + (global $global (ref $itable) (array.init_static $itable + (struct.new $vtable + (ref.null func) + ) + (struct.new $vtable + (ref.func $test) + ) + )) + + ;; CHECK: (func $test (result funcref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $object + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.get $vtable 0 + ;; CHECK-NEXT: (array.get $itable + ;; CHECK-NEXT: (block (result (ref $itable)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.null $object) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (global.get $global) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test (result funcref) + (drop + (struct.new $object + (global.get $global) + ) + ) + ;; Realistic usage of an itable: read an item from it, then a func from + ;; that, and return the value (all verifying that the types are correct + ;; after optimization). Note how after optimization everything is lined up + ;; so that precompute-propagate can infer from the global.get the specific + ;; object the array.get is on, allowing us to emit a constant value for the + ;; outer struct.get in principle. + (struct.get $vtable 0 + (array.get $itable + (struct.get $object $itable + (ref.null $object) + ) + (i32.const 1) + ) + ) + ) +) + |