This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Use strictly less than comparison in Commutative operand sorting
AbandonedPublic

Authored by amandatang on Aug 23 2023, 4:23 PM.

Details

Summary

There is an assertion failure within stable_sort on the comparison function that is passed. stable_sort expects a strictly less than comparison function, which means it should return false for equivalent values.

Note that equivalent operands have the same key size and key values at each index. When the algorithm reaches a keyIndex that exceeds the operands' key sizes, it checks commOperandA first and separately from commOperandB. If the current keyIndex exceeds commOperandA's key size and commOperandA's ancestorQueue is empty, then the comparison function returns true, implying commOperandA is smaller regardless of commOperandB's key.

To fix this, before returning true if commOperandA's ancestorQueue is empty, commOperandB's key size and ancestorQueue is checked for equivalence.

This patch also includes an improvement that uses the OpTraitRewritePattern which is a wrapper for the RewritePattern class that only performs matchAndRewrite on Ops with a specified trait.

Finally, 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.

Diff Detail

Event Timeline

amandatang created this revision.Aug 23 2023, 4:23 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 23 2023, 4:23 PM
amandatang requested review of this revision.Aug 23 2023, 4:23 PM
amandatang retitled this revision from [MLIR] Use strictly less than comparison in Commutative operand sorting to [mlir] Use strictly less than comparison in Commutative operand sorting.Aug 23 2023, 4:24 PM
amandatang abandoned this revision.Aug 24 2023, 4:48 PM