[flang][mlir] fix irreflexibility violation of strict weak ordering in #155348

[cota]

This fixes strict weak ordering checks violations from #155348 when running these two tests:

mlir/test/Dialect/OpenMP/omp-offload-privatization-prepare.mlir
mlir/test/Dialect/OpenMP/omp-offload-privatization-prepare-by-value.mlir

Sample error:

/stable/src/libcxx/include/__debug_utils/strict_weak_ordering_check.h:50: libc++ Hardening assertion !__comp(*(__first + __a), *(__first + __b)) failed: Your comparator is not a valid strict-weak ordering

This is because (x < x) should be false, not true, to meet the irreflexibility property. (Note that .dominates(x, x) returns true.)

I'm afraid that even after this commit we can't guarantee a strict weak ordering, because we can't guarantee transitivity of equivalence by sorting with a strict dominance function. However the tests are not failing anymore, and I am not at all familiar with this code so I will leave this concern up to the original author for consideration. (Ideas without any further context: I would consider a topological sort or walking a dominator tree.)

Reference on std::sort and strict weak ordering:
https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/

[llvmbot]

@llvm/pr-subscribers-mlir-openmp
@llvm/pr-subscribers-flang-openmp

@llvm/pr-subscribers-mlir

Author: Emilio Cota (cota)

Changes

This fixes strict weak ordering checks violations from #155348 when running these two tests:

mlir/test/Dialect/OpenMP/omp-offload-privatization-prepare.mlir
mlir/test/Dialect/OpenMP/omp-offload-privatization-prepare-by-value.mlir

Sample error:

/stable/src/libcxx/include/__debug_utils/strict_weak_ordering_check.h:50: libc++ Hardening assertion !__comp(*(__first + __a), *(__first + __b)) failed: Your comparator is not a valid strict-weak ordering

This is because (x < x) should be false, not true, to meet the irreflexibility property. (Note that .contains(x, x) returns true.)

I'm afraid that even after this commit we can't guarantee a strict weak ordering, because we can't guarantee transitivity of equivalence by sorting with a strict dominance function. However the tests are not failing anymore, and I am not at all familiar with this code so I will leave this concern up to the original author for consideration. (Ideas without any further context: I would consider a topological sort or walking a dominator tree.)

Reference on std::sort and strict weak ordering:
https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/

---

Full diff: https://github.com/llvm/llvm-project/pull/164833.diff

1 Files Affected:

• (modified) mlir/lib/Dialect/OpenMP/Transforms/OpenMPOffloadPrivatizationPrepare.cpp (+3-1)

diff --git a/mlir/lib/Dialect/OpenMP/Transforms/OpenMPOffloadPrivatizationPrepare.cpp b/mlir/lib/Dialect/OpenMP/Transforms/OpenMPOffloadPrivatizationPrepare.cpp
index a9125ec8f74c3..c117d9b034b7a 100644
--- a/mlir/lib/Dialect/OpenMP/Transforms/OpenMPOffloadPrivatizationPrepare.cpp
+++ b/mlir/lib/Dialect/OpenMP/Transforms/OpenMPOffloadPrivatizationPrepare.cpp
@@ -189,7 +189,9 @@ class PrepareForOMPOffloadPrivatizationPass
 
         DominanceInfo dom;
         llvm::sort(chainOfOps, [&](Operation *l, Operation *r) {
-          return dom.dominates(l, r);
+          if (l == r)
+            return false;
+          return dom.properlyDominates(l, r);
         });
 
         rewriter.setInsertionPoint(chainOfOps.front());

[ergawy]

LGTM! Thanks! As you suggested, I think a topolical sort would be a more suitable solution as well. We have some utils under mlir/include/mlir/Analysis/TopologicalSortUtils.h but I will leave that to Pranav to decide.

[efriedma-quic]

Please open a bug for the remaining issue.

LLVM's DominatorTree has support for numbering nodes in the tree, but I'm not sure if there's an mlir equivalent.