[LoopInterchange] Prevent from undoing its own transformation (#127473)

LoopInterchange uses the bubble-sort fashion algorithm to sort the loops
in a loop nest. For two loops `A` and `B`, it calls `isProfitable(A, B)`
to determine whether these loops should be exchanged. The result of
`isProfitable(A, B)` should be conservative, that is, it should return
true only when we are sure exchanging `A` and `B` will improve
performance. If it's not conservative enough, it's possible that a
subsequent `isProfitable(B, A)` will also return true, in which case
LoopInterchange will undo its previous transformation. To avoid such
cases, `isProfitable(B, A)` must not return true if `isProfitable(A, B)`
returned true in the past. However, the current implementation can be in
such a situation. This patch resolves it by correcting the handling of
two loops that have the same cache cost.

This resolve the problem mentioned in
https://github.com/llvm/llvm-project/pull/118267#issuecomment-2510759354.

1 files changed, 3 insertions, 5 deletions

diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
index 364acb0..4366418 100644
--- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
@@ -1146,17 +1146,15 @@ LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(
   if (OuterLoopIt == CostMap.end())
     return std::nullopt;
 
+  if (CC->getLoopCost(*OuterLoop) == CC->getLoopCost(*InnerLoop))
+    return std::nullopt;
   unsigned InnerIndex = InnerLoopIt->second;
   unsigned OuterIndex = OuterLoopIt->second;
   LLVM_DEBUG(dbgs() << "InnerIndex = " << InnerIndex
                     << ", OuterIndex = " << OuterIndex << "\n");
-  if (InnerIndex < OuterIndex)
-    return std::optional<bool>(true);
   assert(InnerIndex != OuterIndex && "CostMap should assign unique "
                                      "numbers to each loop");
-  if (CC->getLoopCost(*OuterLoop) == CC->getLoopCost(*InnerLoop))
-    return std::nullopt;
-  return std::optional<bool>(false);
+  return std::optional<bool>(InnerIndex < OuterIndex);
 }
 
 std::optional<bool>