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 asiadd 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 replacingicmp gt v1, v0
withicmp 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
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 asiadd 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 replacingicmp gt v1, v0
withicmp 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
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 asiadd 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 replacingicmp gt v1, v0
withicmp 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
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 asiadd 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 replacingicmp gt v1, v0
withicmp 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
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 asiadd 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 replacingicmp gt v1, v0
withicmp 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: Dec 23 2024 at 12:05 UTC