Based on the various suggestions here about canonicalizing commutative operations (by sorting their operands), I am proposing a solution below that is not PDL-specific. Rather, it is a generic solution that will provide commutativity support to both PDL and C++ patterns. Kindly share your views on the same.
Solution:
We add a new pass to llvm-project called the canonicalize-commutative-ops pass. This pass walks through each op from top to bottom. When it finds a commutative op, it sorts its operands based on each operand’s origins.
For example, if we have the following pattern and foo is a commutative op:
s = sub a, b
d = div a, b
z0 = arg0
f = foo z0, d, s
Then, the canonicalize-commutative-ops pass will sort the operands of foo op to "d, s, z0" (div < sub < arg0). Basically, while sorting, ops come before block arguments, each op is arranged alphabetically, and each block argument is arranged numerically (arg0 < arg3).
And, if two operands come from the same op, we will backtrack and look even further to sort them. This backtracking can done in a breadth-first traversal.
This algorithm is complete because two different operands cannot have the same breadth-first traversal (this can be enforced by calling the cse pass before this pass). Note that this pass will also solve the recursion problem (which was a rightful concern of @Mogball) because the ops are being traversed from top to bottom exactly once.
We can see that this pass will reduce the number of checks we need to write in a PDL/C++ pattern to match something.
For the above pattern:
1. With canonicalize-commutative-ops: No. of checks = 3.
2. Without canonicalize-commutative-ops: No. of checks = 15.