Added a commutativity utility pattern and a function to populate it. The pattern sorts the operands of an op in ascending order of the "key" associated with each operand iff the op is commutative.
The function is intended to be used inside passes to simplify the matching of commutative operations. After the application of the above-mentioned pattern, since the commutative operands now have a deterministic order in which they occur in an op, the matching of large DAGs becomes much simpler, i.e., requires much less number of checks to be written by a user in her/his pattern matching function.
The "key" associated with an operand is the list of the "AncestorKeys" associated with the ancestors of this operand, in a breadth-first order.
The operand of any op is produced by a set of ops and block arguments. Each of these ops and block arguments is called an "ancestor" of this operand.
Now, the "AncestorKey" associated with:
- A block argument is {type: BLOCK_ARGUMENT, opName: ""}.
- A non-constant-like op, for example, arith.addi, is {type: NON_CONSTANT_OP, opName: "arith.addi"}.
- A constant-like op, for example, arith.constant, is {type: CONSTANT_OP, opName: ""}.
So, if an operand, say A, was produced as follows:
`<block argument>` `<block argument>`
\ /
\ /
`arith.subi` `arith.constant`
\ /
`arith.addi`
|
returns `A`Then, the block arguments and operations present in the backward slice of A, in the breadth-first order are:
arith.addi, arith.subi, arith.constant, <block argument>, and <block argument>.
Thus, the "key" associated with operand A is:
{{type: NON_CONSTANT_OP, opName: "arith.addi"}, {type: NON_CONSTANT_OP, opName: "arith.subi"}, {type: CONSTANT_OP, opName: ""}, {type: BLOCK_ARGUMENT, opName: ""}, {type: BLOCK_ARGUMENT, opName: ""}}.
Now, if "keyA" is the key associated with operand A and "keyB" is the key associated with operand B, then:
- "keyA" == "keyB" iff: Both these keys, each of which is a list, have the same size and both the elements in each pair of corresponding elements among them is the same.
- "keyA" < "keyB" iff: 2.1. In the first unequal pair of corresponding elements among them, "keyA"'s element is smaller, or 2.2. Both the elements in every pair of corresponding elements are the same in both keys and the size of "keyA" is smaller.
Now, "AncestorKey1" is considered smaller than "AncestorKey2" iff:
- The type of "AncestorKey1" is BLOCK_ARGUMENT and that of "AncestorKey2" isn't,
- The type of "AncestorKey1" is NON_CONSTANT_OP and that of "AncestorKey2" is CONSTANT_OP, or
- Both have the same type and the opName of "AncestorKey1" is alphabetically smaller than that of "AncestorKey2".
Some examples of such a sorting:
Assume that the sorting is being applied to foo.commutative, which is a commutative op.
Example 1:
%1 = foo.const 0
%2 = foo.mul <block argument>, <block argument>
%3 = foo.commutative %1, %2
Here,
- The key associated with %1 is {{CONSTANT_OP, ""}}, and,
- The key associated with %2 is {{NON_CONSTANT_OP, "foo.mul"}, {BLOCK_ARGUMENT, ""}, {BLOCK_ARGUMENT, ""}}.
Thus, the key of %2 < key of %1, and so, the sorted foo.commutative will look like:
%3 = foo.commutative %2, %1
Note that in this example, it wasn't necessary to get the entire backward slice of operand %2 to decide that it has the smaller key. Just the comparision of {{CONSTANT_OP, ""}} and {{NON_CONSTANT_OP, "foo.mul"}} is enough to determine this. Thus, this sorting utility does not store the entire backward slice of an operand at once. It seeks the slice in a breadth-first fashion, one at a time, to create an operand "key" but stops when the relative ordering of that operand can be determined.
So, here,
- The key computed for %1 is {{CONSTANT_OP, ""}}, and,
- The key computed for %2 is {{NON_CONSTANT_OP, "foo.mul"}} (instead of {{NON_CONSTANT_OP, "foo.mul"}, {BLOCK_ARGUMENT, ""}, {BLOCK_ARGUMENT, ""}}).
Example 2:
%1 = foo.const 0
%2 = foo.mul <block argument>, <block argument>
%3 = foo.mul %2, %1
%4 = foo.add %2, %1
%5 = foo.commutative %1, %2, %3, %4
Here,
- The key associated with %1 is {{CONSTANT_OP, ""}},
- The key associated with %2 is {{NON_CONSTANT_OP, "foo.mul"}, {BLOCK_ARGUMENT, ""}},
- The key associated with %3 is {{NON_CONSTANT_OP, "foo.mul"}, {NON_CONSTANT_OP, "foo.mul"}, {CONSTANT_OP, ""}, {BLOCK_ARGUMENT, ""}, {BLOCK_ARGUMENT, ""}}, and,
- The key associated with %4 is {{NON_CONSTANT_OP, "foo.add"}, {NON_CONSTANT_OP, "foo.mul"}, {CONSTANT_OP, ""}, {BLOCK_ARGUMENT, ""}, {BLOCK_ARGUMENT, ""}}.
And,
- The key computed for %1 is {{CONSTANT_OP, ""}},
- The key computed for %2 is {{NON_CONSTANT_OP, "foo.mul"}, {BLOCK_ARGUMENT, ""}},
- The key computed for %3 is {{NON_CONSTANT_OP, "foo.mul"}, {NON_CONSTANT_OP, "foo.mul"}}, and,
- The key computed for %4 is {{NON_CONSTANT_OP, "foo.add"}}.
Note that the BFS's for operands %1 and %4 stop after one iteration while those for operands %2 and %3 stop after the second iteration.
And, the sorted foo.commutative will look like:
%5 = foo.commutative %4, %3, %2, %1
Signed-off-by: Srishti Srivastava <srishti.srivastava@polymagelabs.com>