Stream: git-wasmtime

Topic: wasmtime / issue #6129 cranelift/egraphs: Normalize commu...

Wasmtime GitHub notifications bot (Mar 30 2023 at 22:03):

jameysharp opened issue #6129:

Feature

Ensure that commutative operations are unified in the GVN map even if their arguments are in different orders. For example, iadd v0, v1 should hit the same entry in the GVN map as iadd v1, v0.

Benefit

If more instructions unify through the GVN map, then fewer redundant computations will be performed at runtime. In addition, equality saturation may be able to identify more matching rules. This also keeps the size of the GVN map smaller.

Challenges

We currently have ISLE optimization rules which swap the operands to commutative operations if the left-hand operand is a constant, so that constants are always on the right. Other mid-end rules and some backend lowering rules (cc: @afonso360) currently rely on constants appearing on the right to avoid writing extra rules to match the commutative case.

This proposed feature would undo those rules. (We would like to solve that a different way though: see #6128.)

At first glance it seems appealing to fuse that policy into this feature: if exactly one operand is equivalent to a constant, then normalize it on the right, and otherwise use some other normalization policy. That could lead to more problems like #6126 though, if it's possible for a value to be discovered equivalent to a constant after it's already been used by another instruction in the GVN map.

Implementation

When inserting into or retrieving from the GVN map, first put the InstructionData in a normal form: If the opcode is commutative, compare the set-representative value number from the e-class for each of its operands; if they aren't already in non-descending order, swap them. Then proceed with the GVN map lookup.

Note that the GVN map already relies on having a stable set representative for each e-class (but see #6126). So using those representatives to normalize the operand order doesn't require anything new.

This generalizes to instructions where swapping operands isn't necessarily semantics-preserving by itself. For example, it's possible to swap the operands of any icmp as long as the condition code is also swapped, such as replacing icmp gt v1, v0 with icmp lt v0, v1.

Alternatives

The _status quo_ isn't the worst thing in the world. I don't know of any other alternatives if we want to improve this aspect of GVN.

cc: @cfallin

Wasmtime GitHub notifications bot (Mar 30 2023 at 22:03):

jameysharp labeled issue #6129:

Feature

Ensure that commutative operations are unified in the GVN map even if their arguments are in different orders. For example, iadd v0, v1 should hit the same entry in the GVN map as iadd v1, v0.

Benefit

If more instructions unify through the GVN map, then fewer redundant computations will be performed at runtime. In addition, equality saturation may be able to identify more matching rules. This also keeps the size of the GVN map smaller.

Challenges

We currently have ISLE optimization rules which swap the operands to commutative operations if the left-hand operand is a constant, so that constants are always on the right. Other mid-end rules and some backend lowering rules (cc: @afonso360) currently rely on constants appearing on the right to avoid writing extra rules to match the commutative case.

This proposed feature would undo those rules. (We would like to solve that a different way though: see #6128.)

At first glance it seems appealing to fuse that policy into this feature: if exactly one operand is equivalent to a constant, then normalize it on the right, and otherwise use some other normalization policy. That could lead to more problems like #6126 though, if it's possible for a value to be discovered equivalent to a constant after it's already been used by another instruction in the GVN map.

Implementation

When inserting into or retrieving from the GVN map, first put the InstructionData in a normal form: If the opcode is commutative, compare the set-representative value number from the e-class for each of its operands; if they aren't already in non-descending order, swap them. Then proceed with the GVN map lookup.

Note that the GVN map already relies on having a stable set representative for each e-class (but see #6126). So using those representatives to normalize the operand order doesn't require anything new.

This generalizes to instructions where swapping operands isn't necessarily semantics-preserving by itself. For example, it's possible to swap the operands of any icmp as long as the condition code is also swapped, such as replacing icmp gt v1, v0 with icmp lt v0, v1.

Alternatives

The _status quo_ isn't the worst thing in the world. I don't know of any other alternatives if we want to improve this aspect of GVN.

cc: @cfallin

Wasmtime GitHub notifications bot (Mar 30 2023 at 22:03):

jameysharp labeled issue #6129:

Feature

Ensure that commutative operations are unified in the GVN map even if their arguments are in different orders. For example, iadd v0, v1 should hit the same entry in the GVN map as iadd v1, v0.

Benefit

If more instructions unify through the GVN map, then fewer redundant computations will be performed at runtime. In addition, equality saturation may be able to identify more matching rules. This also keeps the size of the GVN map smaller.

Challenges

We currently have ISLE optimization rules which swap the operands to commutative operations if the left-hand operand is a constant, so that constants are always on the right. Other mid-end rules and some backend lowering rules (cc: @afonso360) currently rely on constants appearing on the right to avoid writing extra rules to match the commutative case.

This proposed feature would undo those rules. (We would like to solve that a different way though: see #6128.)

At first glance it seems appealing to fuse that policy into this feature: if exactly one operand is equivalent to a constant, then normalize it on the right, and otherwise use some other normalization policy. That could lead to more problems like #6126 though, if it's possible for a value to be discovered equivalent to a constant after it's already been used by another instruction in the GVN map.

Implementation

When inserting into or retrieving from the GVN map, first put the InstructionData in a normal form: If the opcode is commutative, compare the set-representative value number from the e-class for each of its operands; if they aren't already in non-descending order, swap them. Then proceed with the GVN map lookup.

Note that the GVN map already relies on having a stable set representative for each e-class (but see #6126). So using those representatives to normalize the operand order doesn't require anything new.

This generalizes to instructions where swapping operands isn't necessarily semantics-preserving by itself. For example, it's possible to swap the operands of any icmp as long as the condition code is also swapped, such as replacing icmp gt v1, v0 with icmp lt v0, v1.

Alternatives

The _status quo_ isn't the worst thing in the world. I don't know of any other alternatives if we want to improve this aspect of GVN.

cc: @cfallin

Wasmtime GitHub notifications bot (Apr 04 2023 at 01:04):

jameysharp closed issue #6129:

Feature

Ensure that commutative operations are unified in the GVN map even if their arguments are in different orders. For example, iadd v0, v1 should hit the same entry in the GVN map as iadd v1, v0.

Benefit

If more instructions unify through the GVN map, then fewer redundant computations will be performed at runtime. In addition, equality saturation may be able to identify more matching rules. This also keeps the size of the GVN map smaller.

Challenges

We currently have ISLE optimization rules which swap the operands to commutative operations if the left-hand operand is a constant, so that constants are always on the right. Other mid-end rules and some backend lowering rules (cc: @afonso360) currently rely on constants appearing on the right to avoid writing extra rules to match the commutative case.

This proposed feature would undo those rules. (We would like to solve that a different way though: see #6128.)

At first glance it seems appealing to fuse that policy into this feature: if exactly one operand is equivalent to a constant, then normalize it on the right, and otherwise use some other normalization policy. That could lead to more problems like #6126 though, if it's possible for a value to be discovered equivalent to a constant after it's already been used by another instruction in the GVN map.

Implementation

When inserting into or retrieving from the GVN map, first put the InstructionData in a normal form: If the opcode is commutative, compare the set-representative value number from the e-class for each of its operands; if they aren't already in non-descending order, swap them. Then proceed with the GVN map lookup.

Note that the GVN map already relies on having a stable set representative for each e-class (but see #6126). So using those representatives to normalize the operand order doesn't require anything new.

This generalizes to instructions where swapping operands isn't necessarily semantics-preserving by itself. For example, it's possible to swap the operands of any icmp as long as the condition code is also swapped, such as replacing icmp gt v1, v0 with icmp lt v0, v1.

Alternatives

The _status quo_ isn't the worst thing in the world. I don't know of any other alternatives if we want to improve this aspect of GVN.

cc: @cfallin

Wasmtime GitHub notifications bot (Apr 04 2023 at 19:56):

jameysharp reopened issue #6129:

Feature

Ensure that commutative operations are unified in the GVN map even if their arguments are in different orders. For example, iadd v0, v1 should hit the same entry in the GVN map as iadd v1, v0.

Benefit

If more instructions unify through the GVN map, then fewer redundant computations will be performed at runtime. In addition, equality saturation may be able to identify more matching rules. This also keeps the size of the GVN map smaller.

Challenges

We currently have ISLE optimization rules which swap the operands to commutative operations if the left-hand operand is a constant, so that constants are always on the right. Other mid-end rules and some backend lowering rules (cc: @afonso360) currently rely on constants appearing on the right to avoid writing extra rules to match the commutative case.

This proposed feature would undo those rules. (We would like to solve that a different way though: see #6128.)

At first glance it seems appealing to fuse that policy into this feature: if exactly one operand is equivalent to a constant, then normalize it on the right, and otherwise use some other normalization policy. That could lead to more problems like #6126 though, if it's possible for a value to be discovered equivalent to a constant after it's already been used by another instruction in the GVN map.

Implementation

When inserting into or retrieving from the GVN map, first put the InstructionData in a normal form: If the opcode is commutative, compare the set-representative value number from the e-class for each of its operands; if they aren't already in non-descending order, swap them. Then proceed with the GVN map lookup.

Note that the GVN map already relies on having a stable set representative for each e-class (but see #6126). So using those representatives to normalize the operand order doesn't require anything new.

This generalizes to instructions where swapping operands isn't necessarily semantics-preserving by itself. For example, it's possible to swap the operands of any icmp as long as the condition code is also swapped, such as replacing icmp gt v1, v0 with icmp lt v0, v1.

Alternatives

The _status quo_ isn't the worst thing in the world. I don't know of any other alternatives if we want to improve this aspect of GVN.

cc: @cfallin

Last updated: Oct 23 2024 at 20:03 UTC