[mlir] Commutativity Operand Sorting Pattern Key Comparison Fix

[amandatang]

Summary

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.

---

Example:
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.

[amandatang]

mlir/lib/Transforms/Utils/CommutativityUtils.cpp

90–105

Highlighting the logic added to fix the bug

mlir/include/mlir/Transforms/CommutativityUtils.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_TRANSFORMS_COMMUTATIVITYUTILS_H
 #define MLIR_TRANSFORMS_COMMUTATIVITYUTILS_H
 
 #include "mlir/Transforms/DialectConversion.h"
 
+#include <queue>
+
 namespace mlir {
 
+/// The possible "types" of ancestors. Here, an ancestor is an op or a block
+/// argument present in the backward slice of a value.
+enum AncestorType {
+  /// Pertains to a block argument.
+  BLOCK_ARGUMENT,
+
+  /// Pertains to a non-constant-like op.
+  NON_CONSTANT_OP,
+
+  /// Pertains to a constant-like op.
+  CONSTANT_OP
+};
+
+/// Stores the "key" associated with an ancestor.
+struct AncestorKey {
+  /// Holds `BLOCK_ARGUMENT`, `NON_CONSTANT_OP`, or `CONSTANT_OP`, depending on
+  /// the ancestor.
+  AncestorType type;
+
+  /// Holds the op name of the ancestor if its `type` is `NON_CONSTANT_OP` or
+  /// `CONSTANT_OP`. Else, holds "".
+  StringRef opName;
+
+  /// Constructor for `AncestorKey`.
+  AncestorKey(Operation *op);
+
+  /// Overloaded operator `<` for `AncestorKey`.
+  ///
+  /// AncestorKeys of type `BLOCK_ARGUMENT` are considered the smallest, those
+  /// of type `CONSTANT_OP`, the largest, and `NON_CONSTANT_OP` types come in
+  /// between. Within the types `NON_CONSTANT_OP` and `CONSTANT_OP`, the smaller
+  /// ones are the ones with smaller op names (lexicographically).
+  ///
+  /// TODO: Include other information like attributes, value type, etc., to
+  /// enhance this comparison. For example, currently this comparison doesn't
+  /// differentiate between `cmpi sle` and `cmpi sgt` or `addi (in i32)` and
+  /// `addi (in i64)`. Such an enhancement should only be done if the need
+  /// arises.
+  bool operator<(const AncestorKey &key) const;
+};
+
+/// Stores a commutative operand along with its BFS traversal information.
+struct CommutativeOperand {
+  /// Stores the operand.
+  Value operand;
+
+  /// Stores the queue of ancestors of the operand's BFS traversal at a
+  /// particular point in time.
+  std::queue<Operation *> ancestorQueue;
+
+  /// Stores the list of ancestors that have been visited by the BFS traversal
+  /// at a particular point in time.
+  DenseSet<Operation *> visitedAncestors;
+
+  /// Stores the operand's "key". This "key" is defined as a list of the
+  /// "AncestorKeys" associated with the ancestors of this operand, in a
+  /// breadth-first order.
+  ///
+  /// So, if an operand, say `A`, was produced as follows:
+  ///
+  /// `<block argument>`  `<block argument>`
+  ///             \          /
+  ///              \        /
+  ///             `arith.subi`           `arith.constant`
+  ///                       \            /
+  ///                        `arith.addi`
+  ///                              |
+  ///                         returns `A`
+  ///
+  /// Then, the ancestors 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: "arith.constant"},
+  ///  {type: `BLOCK_ARGUMENT`, opName: ""},
+  ///  {type: `BLOCK_ARGUMENT`, opName: ""}
+  /// }
+  SmallVector<AncestorKey, 4> key;
+
+  /// Push an ancestor into the operand's BFS information structure. This
+  /// entails it being pushed into the queue (always) and inserted into the
+  /// "visited ancestors" list (iff it is an op rather than a block argument).
+  void pushAncestor(Operation *op);
+
+  /// Refresh the key.
+  ///
+  /// Refreshing a key entails making it up-to-date with the operand's BFS
+  /// traversal that has happened till that point in time, i.e, appending the
+  /// existing key with the front ancestor's "AncestorKey". Note that a key
+  /// directly reflects the BFS and thus needs to be refreshed during the
+  /// progression of the traversal.
+  void refreshKey();
+
+  /// Pop the front ancestor, if any, from the queue and then push its adjacent
+  /// unvisited ancestors, if any, to the queue (this is the main body of the
+  /// BFS algorithm).
+  void popFrontAndPushAdjacentUnvisitedAncestors();
+
+  // Custom comparator for two commutative operands, which returns true iff
+  // the "key" of `constCommOperandA` < the "key" of `constCommOperandB`,
+  // i.e.,
+  // 1. In the first unequal pair of corresponding AncestorKeys, the
+  // AncestorKey in `constCommOperandA` is smaller, or,
+  // 2. Both the AncestorKeys in every pair are the same and the size of
+  // `constCommOperandA`'s "key" is smaller.
+  static bool commutativeOperandComparator(
+      const std::unique_ptr<CommutativeOperand> &constCommOperandA,
+      const std::unique_ptr<CommutativeOperand> &constCommOperandB);
+};
+
 /// Populates the commutativity utility patterns.
 void populateCommutativityUtilsPatterns(RewritePatternSet &patterns);
 
 } // namespace mlir
 
 #endif // MLIR_TRANSFORMS_COMMUTATIVITYUTILS_H

mlir/lib/Transforms/Utils/CommutativityUtils.cpp

 // populate this pattern. The function is intended to be used inside passes to
 // simplify the matching of commutative operations by fixing the order of their
 // operands.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Transforms/CommutativityUtils.h"
 
-#include <queue>
-
 using namespace mlir;
 
-/// The possible "types" of ancestors. Here, an ancestor is an op or a block
-/// argument present in the backward slice of a value.
-enum AncestorType {
-  /// Pertains to a block argument.
-  BLOCK_ARGUMENT,
-
-  /// Pertains to a non-constant-like op.
-  NON_CONSTANT_OP,
-
-  /// Pertains to a constant-like op.
-  CONSTANT_OP
-};
-
-/// Stores the "key" associated with an ancestor.
-struct AncestorKey {
-  /// Holds `BLOCK_ARGUMENT`, `NON_CONSTANT_OP`, or `CONSTANT_OP`, depending on
-  /// the ancestor.
-  AncestorType type;
-
-  /// Holds the op name of the ancestor if its `type` is `NON_CONSTANT_OP` or
-  /// `CONSTANT_OP`. Else, holds "".
-  StringRef opName;
-
-  /// Constructor for `AncestorKey`.
-  AncestorKey(Operation *op) {
-    if (!op) {
-      type = BLOCK_ARGUMENT;
-    } else {
-      type =
-          op->hasTrait<OpTrait::ConstantLike>() ? CONSTANT_OP : NON_CONSTANT_OP;
-      opName = op->getName().getStringRef();
-    }
-  }
+AncestorKey::AncestorKey(Operation *op) {
 
-  /// Overloaded operator `<` for `AncestorKey`.
-  ///
-  /// AncestorKeys of type `BLOCK_ARGUMENT` are considered the smallest, those
-  /// of type `CONSTANT_OP`, the largest, and `NON_CONSTANT_OP` types come in
-  /// between. Within the types `NON_CONSTANT_OP` and `CONSTANT_OP`, the smaller
-  /// ones are the ones with smaller op names (lexicographically).
-  ///
-  /// TODO: Include other information like attributes, value type, etc., to
-  /// enhance this comparison. For example, currently this comparison doesn't
-  /// differentiate between `cmpi sle` and `cmpi sgt` or `addi (in i32)` and
-  /// `addi (in i64)`. Such an enhancement should only be done if the need
-  /// arises.
-  bool operator<(const AncestorKey &key) const {
-    return std::tie(type, opName) < std::tie(key.type, key.opName);
-  }
-};
+bool AncestorKey::operator<(const AncestorKey &key) const {
 
-/// Stores a commutative operand along with its BFS traversal information.
-struct CommutativeOperand {
-  /// Stores the operand.
-  Value operand;
-
-  /// Stores the queue of ancestors of the operand's BFS traversal at a
-  /// particular point in time.
-  std::queue<Operation *> ancestorQueue;
-
-  /// Stores the list of ancestors that have been visited by the BFS traversal
-  /// at a particular point in time.
-  DenseSet<Operation *> visitedAncestors;
-
-  /// Stores the operand's "key". This "key" is defined as a list of the
-  /// "AncestorKeys" associated with the ancestors of this operand, in a
-  /// breadth-first order.
-  ///
-  /// So, if an operand, say `A`, was produced as follows:
-  ///
-  /// `<block argument>`  `<block argument>`
-  ///             \          /
-  ///              \        /
-  ///             `arith.subi`           `arith.constant`
-  ///                       \            /
-  ///                        `arith.addi`
-  ///                              |
-  ///                         returns `A`
-  ///
-  /// Then, the ancestors 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: "arith.constant"},
-  ///  {type: `BLOCK_ARGUMENT`, opName: ""},
-  ///  {type: `BLOCK_ARGUMENT`, opName: ""}
-  /// }
-  SmallVector<AncestorKey, 4> key;
-
-  /// Push an ancestor into the operand's BFS information structure. This
-  /// entails it being pushed into the queue (always) and inserted into the
-  /// "visited ancestors" list (iff it is an op rather than a block argument).
-  void pushAncestor(Operation *op) {
-    ancestorQueue.push(op);
-    if (op)
-      visitedAncestors.insert(op);
-  }
+void CommutativeOperand::pushAncestor(Operation *op) {
 
-  /// Refresh the key.
-  ///
-  /// Refreshing a key entails making it up-to-date with the operand's BFS
-  /// traversal that has happened till that point in time, i.e, appending the
-  /// existing key with the front ancestor's "AncestorKey". Note that a key
-  /// directly reflects the BFS and thus needs to be refreshed during the
-  /// progression of the traversal.
-  void refreshKey() {
-    if (ancestorQueue.empty())
-      return;
+void CommutativeOperand::refreshKey() {
 
-    Operation *frontAncestor = ancestorQueue.front();
-    AncestorKey frontAncestorKey(frontAncestor);
-    key.push_back(frontAncestorKey);
-  }
 
-  /// Pop the front ancestor, if any, from the queue and then push its adjacent
-  /// unvisited ancestors, if any, to the queue (this is the main body of the
-  /// BFS algorithm).
-  void popFrontAndPushAdjacentUnvisitedAncestors() {
-    if (ancestorQueue.empty())
-      return;
-    Operation *frontAncestor = ancestorQueue.front();
-    ancestorQueue.pop();
-    if (!frontAncestor)
-      return;
-    for (Value operand : frontAncestor->getOperands()) {
-      Operation *operandDefOp = operand.getDefiningOp();
-      if (!operandDefOp || !visitedAncestors.contains(operandDefOp))
-        pushAncestor(operandDefOp);
-    }
-  }
-};
+void CommutativeOperand::popFrontAndPushAdjacentUnvisitedAncestors() {
+
+bool CommutativeOperand::commutativeOperandComparator(
+    const std::unique_ptr<CommutativeOperand> &constCommOperandA,
+    const std::unique_ptr<CommutativeOperand> &constCommOperandB) {
+  if (constCommOperandA->operand == constCommOperandB->operand)
+    return false;
+
+  auto &commOperandA =
+      const_cast<std::unique_ptr<CommutativeOperand> &>(constCommOperandA);
+  auto &commOperandB =
+      const_cast<std::unique_ptr<CommutativeOperand> &>(constCommOperandB);
+
+  // Iteratively perform the BFS's of both operands until an order among
+  // them can be determined.
+  unsigned keyIndex = 0;
+  while (true) {
+    if (commOperandA->key.size() <= keyIndex) {
+      if (commOperandA->ancestorQueue.empty())
+        return true;
+      commOperandA->popFrontAndPushAdjacentUnvisitedAncestors();
+      commOperandA->refreshKey();
+    }
+    if (commOperandB->key.size() <= keyIndex) {
+      if (commOperandB->ancestorQueue.empty())
+        return false;
+      commOperandB->popFrontAndPushAdjacentUnvisitedAncestors();
+      commOperandB->refreshKey();
+    }
+    // Try comparing the keys at the current keyIndex
+    if (keyIndex < commOperandA->key.size() &&
+        keyIndex < commOperandB->key.size()) {
+      if (commOperandA->key[keyIndex] < commOperandB->key[keyIndex])
+        return true;
+      if (commOperandB->key[keyIndex] < commOperandA->key[keyIndex])
+        return false;
+    } else { // keyIndex exceeds one or both key sizes
+      // Compare key sizes if the values at every possible keyIndex were
+      // equal Both operands must have fully generated key and cannot
+      // have anything in the ancestorQueue
+      if (commOperandA->ancestorQueue.empty() &&
+          commOperandB->ancestorQueue.empty())
+        return commOperandA->key.size() < commOperandB->key.size();
+    }
+    keyIndex++;
+  }
+}
 
 /// Sorts the operands of `op` in ascending order of the "key" associated with
 /// each operand iff `op` is commutative. This is a stable sort.
 ///
 /// After the application of this 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.

 /// Here,
 /// 1. The key associated with %1 is:
 ///     `{
 ///       {CONSTANT_OP, "foo.const"}
 ///      }`
 /// 2. The key associated with %2 is:
 ///     `{
 ///       {NON_CONSTANT_OP, "foo.mul"},
+///       {BLOCK_ARGUMENT, ""},
 ///       {BLOCK_ARGUMENT, ""}
 ///      }`
 /// 3. The key associated with %3 is:
 ///     `{
 ///       {NON_CONSTANT_OP, "foo.mul"},
 ///       {NON_CONSTANT_OP, "foo.mul"},
 ///       {CONSTANT_OP, "foo.const"},
 ///       {BLOCK_ARGUMENT, ""},
 ///       {BLOCK_ARGUMENT, ""}
 ///      }`
 /// 4. The key associated with %4 is:
 ///     `{
 ///       {NON_CONSTANT_OP, "foo.add"},
 ///       {NON_CONSTANT_OP, "foo.mul"},
 ///       {CONSTANT_OP, "foo.const"},
 ///       {BLOCK_ARGUMENT, ""},
 ///       {BLOCK_ARGUMENT, ""}
 ///      }`
 ///
 /// Thus, the sorted `foo.commutative` is:
-/// %5 = foo.commutative %4, %3, %2, %1
-class SortCommutativeOperands : public RewritePattern {
-public:
+/// %5 = foo.commutative %4, %2, %3, %1
+struct SortCommutativeOperands final
+    : public OpTraitRewritePattern<OpTrait::IsCommutative> {
   SortCommutativeOperands(MLIRContext *context)
-      : RewritePattern(MatchAnyOpTypeTag(), /*benefit=*/5, context) {}
+      : OpTraitRewritePattern<OpTrait::IsCommutative>(context, /*benefit=*/5) {}
   LogicalResult matchAndRewrite(Operation *op,
                                 PatternRewriter &rewriter) const override {
-    // Custom comparator for two commutative operands, which returns true iff
-    // the "key" of `constCommOperandA` < the "key" of `constCommOperandB`,
-    // i.e.,
-    // 1. In the first unequal pair of corresponding AncestorKeys, the
-    // AncestorKey in `constCommOperandA` is smaller, or,
-    // 2. Both the AncestorKeys in every pair are the same and the size of
-    // `constCommOperandA`'s "key" is smaller.
-    auto commutativeOperandComparator =
-        [](const std::unique_ptr<CommutativeOperand> &constCommOperandA,
-           const std::unique_ptr<CommutativeOperand> &constCommOperandB) {
-          if (constCommOperandA->operand == constCommOperandB->operand)
-            return false;
-
-          auto &commOperandA =
-              const_cast<std::unique_ptr<CommutativeOperand> &>(
-                  constCommOperandA);
-          auto &commOperandB =
-              const_cast<std::unique_ptr<CommutativeOperand> &>(
-                  constCommOperandB);
-
-          // Iteratively perform the BFS's of both operands until an order among
-          // them can be determined.
-          unsigned keyIndex = 0;
-          while (true) {
-            if (commOperandA->key.size() <= keyIndex) {
-              if (commOperandA->ancestorQueue.empty())
-                return true;
-              commOperandA->popFrontAndPushAdjacentUnvisitedAncestors();
-              commOperandA->refreshKey();
-            }
-            if (commOperandB->key.size() <= keyIndex) {
-              if (commOperandB->ancestorQueue.empty())
-                return false;
-              commOperandB->popFrontAndPushAdjacentUnvisitedAncestors();
-              commOperandB->refreshKey();
-            }
-            if (commOperandA->ancestorQueue.empty() ||
-                commOperandB->ancestorQueue.empty())
-              return commOperandA->key.size() < commOperandB->key.size();
-            if (commOperandA->key[keyIndex] < commOperandB->key[keyIndex])
-              return true;
-            if (commOperandB->key[keyIndex] < commOperandA->key[keyIndex])
-              return false;
-            keyIndex++;
-          }
-        };
-
-    // If `op` is not commutative, do nothing.
-    if (!op->hasTrait<OpTrait::IsCommutative>())
-      return failure();
-
     // Populate the list of commutative operands.
     SmallVector<Value, 2> operands = op->getOperands();
     SmallVector<std::unique_ptr<CommutativeOperand>, 2> commOperands;
     for (Value operand : operands) {
       std::unique_ptr<CommutativeOperand> commOperand =
           std::make_unique<CommutativeOperand>();
       commOperand->operand = operand;
       commOperand->pushAncestor(operand.getDefiningOp());
       commOperand->refreshKey();
       commOperands.push_back(std::move(commOperand));
     }
 
     // Sort the operands.
     std::stable_sort(commOperands.begin(), commOperands.end(),
-                     commutativeOperandComparator);
+                     CommutativeOperand::commutativeOperandComparator);
     SmallVector<Value, 2> sortedOperands;
     for (const std::unique_ptr<CommutativeOperand> &commOperand : commOperands)
       sortedOperands.push_back(commOperand->operand);
     if (sortedOperands == operands)
       return failure();
     rewriter.updateRootInPlace(op, [&] { op->setOperands(sortedOperands); });
     return success();
   }
 };
 
 void mlir::populateCommutativityUtilsPatterns(RewritePatternSet &patterns) {
   patterns.add<SortCommutativeOperands>(patterns.getContext());
 }

mlir/unittests/Transforms/CMakeLists.txt

 add_mlir_unittest(MLIRTransformsTests
   Canonicalizer.cpp
   DialectConversion.cpp
 )
 target_link_libraries(MLIRTransformsTests
   PRIVATE
   MLIRParser
   MLIRTransforms)
+
+add_subdirectory(Utils)

mlir/unittests/Transforms/Utils/CMakeLists.txt

+add_mlir_unittest(MLIRTransformUtilsTests
+  CommutativityUtils.cpp
+)
+target_link_libraries(MLIRTransformUtilsTests
+  PRIVATE
+  MLIRTransformUtils)

mlir/unittests/Transforms/Utils/CommutativityUtils.cpp

+//===- CommutativityUtils.cpp - Commutative Operand Comparison unit tests -===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Transforms/CommutativityUtils.h"
+#include "mlir/IR/Value.h"
+#include "llvm/Support/Casting.h"
+#include "gtest/gtest.h"
+#include <cstddef>
+
+using namespace mlir;
+
+static Operation *createOp(MLIRContext *context, StringRef name,
+                           TypeRange types = std::nullopt) {
+  context->allowUnregisteredDialects();
+  return Operation::create(
+      UnknownLoc::get(context), OperationName(name, context), types,
+      std::nullopt, std::nullopt, /*properties=*/nullptr, std::nullopt, 0);
+}
+
+// The following test case is based on this example
+// %0 = dummy1 <block-argument> <block-argument>
+// %1 = dummy2 <block-argument> <block-argument>
+// %commutative = %0, %1
+//
+// The test case compares the commutative operands dummy1 and dummy2.
+// dummy1's key is complete and its ancestorQueue is empty while dummy2's
+// key only has one element and its ancestorQueue has the remaining 2
+// elements.
+//
+// dummy1 is the smaller operand because its name is lexicographically
+// smaller than dummy2
+TEST(CommutativityUtilsTest, TestOneEmptyAncestorQueue) {
+  MLIRContext context;
+  Builder builder(&context);
+  Operation *dummy1 = createOp(&context, "dummy1", builder.getIntegerType(32));
+  Operation *dummy2 = createOp(&context, "dummy2", builder.getIntegerType(32));
+
+  std::unique_ptr<CommutativeOperand> commOperandA =
+      std::make_unique<CommutativeOperand>();
+  commOperandA->operand = dummy1->getOpResult(0);
+  AncestorKey commOperandAKey0(dummy1);
+  AncestorKey commOperandAKey1(nullptr);
+  AncestorKey commOperandAKey2(nullptr);
+  commOperandA->key.push_back(commOperandAKey0);
+  commOperandA->key.push_back(commOperandAKey1);
+  commOperandA->key.push_back(commOperandAKey2);
+
+  std::unique_ptr<CommutativeOperand> commOperandB =
+      std::make_unique<CommutativeOperand>();
+  commOperandB->operand = dummy2->getOpResult(0);
+  AncestorKey commOperandBKey0(dummy2);
+  commOperandB->key.push_back(commOperandBKey0);
+  commOperandB->ancestorQueue.push(nullptr);
+  commOperandB->ancestorQueue.push(nullptr);
+
+  EXPECT_TRUE(CommutativeOperand::commutativeOperandComparator(commOperandA,
+                                                               commOperandB));
+}