Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

[mlir] Commutativity Operand Sorting Pattern Key Comparison Fix
Needs ReviewPublic

Authored by amandatang on Aug 24 2023, 4:48 PM.



This patch addresses a bug when comparing key sizes when at least one ancestorQueue is empty. If one ancestorQueue is not empty, its traversal isn't complete and the size comparison may be incorrect. In the while loop of the comparison method, before comparing the entries at the current key index, if one of the ancestor queues is empty, then the sizes of the ancestor keys are compared.

Consider operandA and operandB with the following keys and ancestorQueues.

operand A key = {
  {type: NON_CONSTANT_OP, opName: "arith.addi"}, 
  {type: BLOCK_ARGUMENT, opName: ""}, 
  {type: BLOCK_ARGUMENT, opName: ""}

operand A ancestorQueue = empty

operand B key = {
    {type: NON_CONSTANT_OP, opName: "arith.divsi"}

operand B ancestorQueue = {block_argument, block_argument}

Operand A has a fully generated key and empty ancestor queue while Operand B is not fully generated. When they are compared, operand A should be smaller because at keyIndex 0, "arith.addi" is smaller than "arith.divsi". However, Operand A's ancestor queue is empty, so the following if statement is executed:

if (commOperandA->ancestorQueue.empty() || commOperandB->ancestorQueue.empty())
  return commOperandA->key.size() < commOperandB->key.size();
The comparison incorrectly returns false since operand A's key size is 3 and operand B's key size is 1.

To fix this, the entries at the current index must be checked and compared first if possible. The ancestor key sizes must only be compared if the current index exceeds one of the sizes and both ancestor keys are fully generated.

Additional Changes
To demonstrate the behavior, a unit test is added. The AncestorType enum, AncestorKey struct and CommutativeOperand struct are moved to the header file and the comparison lambda is moved to a static method under CommutativeOperand to enable usage within the unit test.

The OpTraitRewritePattern which is a wrapper for the RewritePattern class is used to perform matchAndRewrite on Ops with a specified trait.

Example 2 in the comments is corrected. The key associated with operand %2 is missing a block argument entry at the end. Additionally, the final sorted operand ordering should be %4, %2, %3, %1. Both examples in the comments are added as tests.

Diff Detail

Event Timeline

amandatang created this revision.Aug 24 2023, 4:48 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 24 2023, 4:48 PM
amandatang requested review of this revision.Aug 24 2023, 4:48 PM
amandatang retitled this revision from Summary: to [mlir] Commutativity Operand Sorting Pattern ancestorQueue Fix.Aug 24 2023, 4:55 PM
amandatang edited the summary of this revision. (Show Details)
amandatang retitled this revision from [mlir] Commutativity Operand Sorting Pattern ancestorQueue Fix to [mlir] Commutativity Operand Sorting Pattern Key Comparison Fix.Aug 24 2023, 5:12 PM
amandatang added inline comments.Aug 25 2023, 12:05 PM

Highlighting the logic added to fix the bug