[LoopInterchange] Correcting the profitability check

[ram-NK]

Summary

If inner loop is loop independent or doesn't carry any dependency then, loop interchange is not profitable. Also if outer loop is not loop independent then, loop interchange is not profitable. if inner loop has dependence and outer loop is loop independent then, it is profitable to interchange to enable inner loop parallelism. Corrected the dependency checking inside isProfitableForVectorization(). Also addresses the endless interchange problem. If Cache analysis could decide the loop order then, isProfitable will not invoke isProfitableForVectorization for decidinding better loop interchange.

[ram-NK]

Before this patch, If outer loop dependency direction "=" and Inner loop dependency direction is "S" and "I" then, loop interchange is considered as profitable. Only two cases of dependency is profitable. But for vectorization, ">" and "<" dependency in outer loop is more profitable when interchanged. After patch [=,<] and [=,>] will be interchanged for vectorization.

[bmahjour]

The proper profitability analysis for loop interchange uses CacheCost, although there are cases where it may be unable to analyze certain accesses (eg due to delinearization issues). It would be good to understand why we don't go through the CacheCost path in your use case.

The legacy heuristic doesn't look right to me, although your changes make the logic more aligned with the comments in the code.

llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll

11 ↗

(On Diff #467235)

I'm worried about losing functional coverage by avoiding interchange here due to profitability. Can you play with -loop-interchange-threshold or make slight changes to the memory accesses to make the test case profitable?

[congzhe]

In D135808#3861367, @ram-NK wrote:

If outer loop dependency direction "=" and Inner loop dependency direction is "S" and "I" then, loop interchange is considered as profitable. Only two cases of dependency is profitable. But for vectorization, ">" and "<" dependency in outer loop is more profitable when interchanged. After patch [=,<] and [=,>] will be interchanged for vectorization.

I thought what you meant is that after this patch, [<, =] and [>, =] (not [=,<] and [=,>]) will be interchanged? Because after interchange the dependency vector would become [=, <] and [=, >] respectively, which could improve potential parallelization and enable finer-grained parallelism, i.e., outer loop parallelism instead of inner loop parallelism. I think this is what isProfitableForVectorization() is supposed to be.

I wonder if it makes sense to you @bmahjour ?

[bmahjour]

In D135808#3862874, @congzhe wrote:

In D135808#3861367, @ram-NK wrote:

If outer loop dependency direction "=" and Inner loop dependency direction is "S" and "I" then, loop interchange is considered as profitable. Only two cases of dependency is profitable. But for vectorization, ">" and "<" dependency in outer loop is more profitable when interchanged. After patch [=,<] and [=,>] will be interchanged for vectorization.

I thought what you meant is that after this patch, [<, =] and [>, =] (not [=,<] and [=,>]) will be interchanged? Because after interchange the dependency vector would become [=, <] and [=, >] respectively, which could improve potential parallelization and enable finer-grained parallelism, i.e., outer loop parallelism instead of inner loop parallelism. I think this is what isProfitableForVectorization() is supposed to be.

I wonder if it makes sense to you @bmahjour ?

I think profitability determination solely based on dependency matrix is fundamentally flawed. One obvious example is this

void f1() {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      B[j][i] = A[j][i];
    }  
}

Assuming A and B don't alias, there are no dependencies, nevertheless interchange is profitable.

Another example is:

void f2() {
  // > =
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      ... = A[i][j];
      A[i-1][j] = ...;
    }
}

The dependence is carried by the outer loop, yet it's not profitable to interchange (since it would make both locality and parallelism worse).

The following example is profitable to interchange, but won't be recognized as profitable after this patch:

void f3() {
  // = =
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      ... = A[j][i];
      A[j][i] = ...;
    }
}

[ram-NK]

I'm worried about losing functional coverage by avoiding interchange here due to profitability. Can you play with -loop-interchange-threshold or make slight changes to the memory accesses to make the test case profitable?

Reverted the changes in pr43797-lcssa-for-multiple-outer-loop-blocks.ll. In this case, CostMap is empty and calculated legacy cost is 0. For retaining the loop interchange functionality, lowered the loop interchange threshold to -1000 (added -loop-interchange-threshold=-1000).

[ram-NK]

In D135808#3865187, @bmahjour wrote:

In D135808#3862874, @congzhe wrote:

In D135808#3861367, @ram-NK wrote:

If outer loop dependency direction "=" and Inner loop dependency direction is "S" and "I" then, loop interchange is considered as profitable. Only two cases of dependency is profitable. But for vectorization, ">" and "<" dependency in outer loop is more profitable when interchanged. After patch [=,<] and [=,>] will be interchanged for vectorization.

I thought what you meant is that after this patch, [<, =] and [>, =] (not [=,<] and [=,>]) will be interchanged? Because after interchange the dependency vector would become [=, <] and [=, >] respectively, which could improve potential parallelization and enable finer-grained parallelism, i.e., outer loop parallelism instead of inner loop parallelism. I think this is what isProfitableForVectorization() is supposed to be.

I wonder if it makes sense to you @bmahjour ?

I think profitability determination solely based on dependency matrix is fundamentally flawed. One obvious example is this

void f1() {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      B[j][i] = A[j][i];
    }  
}

Assuming A and B don't alias, there are no dependencies, nevertheless interchange is profitable.

Another example is:

void f2() {
  // > =
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      ... = A[i][j];
      A[i-1][j] = ...;
    }
}

The dependence is carried by the outer loop, yet it's not profitable to interchange (since it would make both locality and parallelism worse).

The following example is profitable to interchange, but won't be recognized as profitable after this patch:

void f3() {
  // = =
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      ... = A[j][i];
      A[j][i] = ...;
    }
}

In loop interchange, profitablility is determined first by the cost model and then by isProfitableForVectorization(). Loops in f1() and f3() will be interchanged by CacheCost checking. In profitability checking of loop interchange, CacheCost analysis is done first. So this patch will not affect the f1() and f3() cases.

For f2() case, CacheCost and Legacy cost model will not show profitability. If loops in f2() is loop interchanged then, Outer loop parallelization is possible, which could improve parallelism.

[Meinersbur]

Could you add a test case that is not considered profitable where before it was not?

In D135808#3865187, @bmahjour wrote:

I think profitability determination solely based on dependency matrix is fundamentally flawed.

I understand the idea is that when the locality model says that interchanged and non-interchanged have the same profitability according to cache locality analysis, only then we fall back to a heuristic that determines whether maybe the innermost loop of the interchange loop nest can be vectorized when the one before vectorization could not.

Unfortunately LoopInterchangeProfitability::isProfitable is not structured like that. It falls back to isProfitableForVectorization whenever cache analysis does not want to interchange the loops. This includes the case where the old loop nest has better locality than the interchanged would have. This could result in a endless application of LoopInterchange if we would run it until no more change is to be made:

1. Cache analysis thinks non-interchanged nest has more locality => fall back to isProfitableForVectorization which returns true => do the interchange
2. Cache analysis thinks the interchange has more locality => do the interchange (with two interchanges we arrive at the original loop)
3. Cache analysis thinks non-interchanged nest has more locality => fall back to isProfitableForVectorization which returns true => do the interchange again
4. ...

In D135808#3862874, @congzhe wrote:

I thought what you meant is that after this patch, [<, =] and [>, =] (not [=,<] and [=,>]) will be interchanged? Because after interchange the dependency vector would become [=, <] and [=, >] respectively, which could improve potential parallelization and enable finer-grained parallelism, i.e., outer loop parallelism instead of inner loop parallelism. I think this is what isProfitableForVectorization() is supposed to be.

The current LoopVectorize pass only supports innermost loops, hence you would want the dependencies carried by the outer loops so the LoopVectorize pass does not have to consider them.

Btw, why does LopInterchange use a DepMatrix when the dependencies for all instructions in the loop could be just summarized in a single vector?

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1100–1101

Does you patch cover this TODO?

1100–1101

Shouldn't the condition on Row[InnerLoopId] and Row[OuterLoopId] be exact opposite? That is, it is profitable if the innermost loop has loop-carried dependencies while the outer has not?

1125–1137

Should this only be considered if InnerLoopId is actually an innermost loop (The only kind LoopVectorize can currently process)?

[ram-NK]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1100–1101

Corrected the dependency checking and corrected the comments.

1100–1101

Corrected the dependency check. If inner loop has loop carried dependency and outer loop is loop independent then, loop interchange is considered as profitable for vectorization.

[ram-NK]

llvm/test/Transforms/LoopInterchange/pr43797-lcssa-for-multiple-outer-loop-blocks.ll

11 ↗

(On Diff #467235)

These changes are not needed after correcting the dependency check in loop interchange.

[ram-NK]

Following changes are made as per the comments. If inner loop is loop independent or doesn't carry any dependency then, loop interchange is not considered as profitable. Also if outer loop is not loop independent then, loop interchange is not considered as profitable. If inner loop has dependence and outer loop is loop independent then, it is profitable to interchange to enable inner loop parallelism.

[ram-NK]

@Meinersbur and @bmahjour, Could you get the chance to review the code I modified as per your comment?

[bmahjour]

This looks better now, but the problem of "endless interchange" is still not addressed. Per discussion in the loop opt call, we should only use CacheCost when it was able to calculate a valid cost and the loops can be sorted based on "strictly less than" ordering relationship. Only when CacheCost result is indeterminate (eg. two loops have equal cost) or when it is unable to calculate the cost (eg. due to delinearization issues), we should fall back to the isProfitableForVectorization() function.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1105

not not -> not

[ram-NK]

This looks better now, but the problem of "endless interchange" is still not addressed. Per discussion in the loop opt call, we should only use CacheCost when it was able to calculate a valid cost and the loops can be sorted based on "strictly less than" ordering relationship. Only when CacheCost result is indeterminate (eg. two loops have equal cost) or when it is unable to calculate the cost (eg. due to delinearization issues), we should fall back to the isProfitableForVectorization() function.

Corrected the "endless interchange" possibility. Now isProfitableForVectorization() only invokes when two loops have equal cost or it is unable to calculate the cost.

[ram-NK]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1105

corrected

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1141

[ram-NK]

@congzhe and @bmahjour comments are addressed.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1141

Corrected the condition. any of the loop is failed to determine the loop nest and equal locality then only checks the profit of vectorization.

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1138–1139

Consider updating this message. Suggestion: "Interchanging loops not considered to improve cache locality nor vectorization."

1141

This is exactly the else branch of the cache analysis logic. It does not consider the fallback Cost < -LoopInterchangeCostThreshold legacy cost model. Please avoid the code duplication and needing to loop up the CostMap again.

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1115–1121

The structure suggested in the LoopWG call.

The more general pattern/refactoring would be:

std::optional<bool> shouldInterchange = isProfitableAccordingLoopCacheAnalysis(..);
if (shouldInterchange.has_value()) 
  return shouldInterchange.get_value();

shouldInterchange = isProfitableAccordingInstrOrderCost(..);
if (shouldInterchange.has_value()) 
  return shouldInterchange.get_value();

shouldInterchange = isProfitableForVectorization(..);
if (shouldInterchange.has_value()) 
  return shouldInterchange.get_value();

emitOptimizationRemark("Don't know");

However, this changes when the emitOptimizationRemark is called. If we would not want to change this, it would be (which corresponds to the current structure but with refactoring):

std::optional<bool> shouldInterchange = isProfitableAccordingLoopCacheAnalysis(..);
if (!shouldInterchange.has_value()) {
  shouldInterchange = isProfitableAccordingInstrOrderCost(..);
  if (!shouldInterchange.has_value()) {
     shouldInterchange = isProfitableForVectorization(..);
  }
}

if (!shouldInterchange.has_value())
  emitOptimizationRemark("Don't know");
else if (!shouldInterchange.get_value())
  emitOptimizationRemark("Profitability heuristic indicates this loop is good as-is");

although I would prefer the former over the nested if-else chain and instead emit different optimization remarks for each of the heuristic that indicates that/why the loops should (NOT) be interchanged.

[ram-NK]

@Meinersbur, I will update these comments and testcase accordingly.

[ram-NK]

As per the Michael 's comments. Code inside isProfitable function is cleaned.

Added test case. With two loop interchange passes make sure that, there is no endless interchange. Before this patch there is endless loop interchange possibility. There is no endless interchange after this patch.

[ram-NK]

@Meinersbur comments are addressed.

[congzhe]

I would suggest to revise the summary and/or the title to describe that this patch now also addresses the endless interchange problem, in addition to correction in isProfitableForVectorization().

llvm/test/Transforms/LoopInterchange/profitability.ll

179

I would suggest to apply --check-prefix=PROFIT only to interchange_05() and not to other existing tests. Because this opt command line runs interchange twice and shows that there would have been endless interchange with interchange_05() before this patch but there is no endless interchange after this patch, which applies only to interchange_05() and is not related to other tests.

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1133

Is it possible to make LoopInterchangeCostMeaningfulnessThreshold an opt flag so we can assign its value more flexibly? Possibly rename it to LegacyCostModelThreshold or whatever is more appropriate.

static cl::opt<int> LegacyCostModelThreshold(
    "legacy-cost-threshold", cl::init(10), cl::Hidden,
    cl::desc("The threshold for the legacy cost model to be considered."));

[ram-NK]

@congzhe Corrected as per the comments.

[ram-NK]

Added comments in Test case 05 for better understanding.
Corrected the comment in Test case 01. The loop interchange decision is made from the Cache cost analysis and is not from vectorization.

[congzhe]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1101–1104

nit: isProfitableAccordingToLoopCacheAnalysis, or isProfitablePerLoopCacheAnalysis

1126–1137

nit: isProfitableAccordingToInstrOrderCost, or isProfitablePerInstrOrderCost

1168

It could be worth adding some comments for this function that describe what it does now, and how it prevents endless interchange from happening.

llvm/test/Transforms/LoopInterchange/profitability.ll

175

nit:

may leads->may lead
before-> before D135808
now-> after D135808

[ram-NK]

@congzhe, All comments are addressed.

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

64

I don't see why we need two options to control the legacy cost model.

1117

We should return nullopt when/if InnerIndex == OuterIndex

1146

since the idea is to call this function only when CC has failed or been indecisive, we don't need to pass CC to this function and check it here.

llvm/test/Transforms/LoopInterchange/profitability.ll

171–176

reword:

This tests to make sure, that multiple invocations of loop interchange will not undo previous interchange and will converge to a particular order determined by the profitability analysis.

[ram-NK]

@bmahjour I will update the comments accordingly.

[ram-NK]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

64

This new parameter added as per @Meinersbur comments in Inline. This is considered as the upper limit of InstrOrderCost.

1117

The CostMap is assigned with unique number to each loop. So this condition "InnerIndex == OuterIndex" will not satisfy. But LoopCost may be same, CC->getLoopCost(*InnerLoop) == CC->getLoopCost(*OuterLoop) checking can be added for returning nullopt.

[ram-NK]

perserve-lcssa.ll corrected, Instruction order cost is 0, Not profitable to interchange.
loop-interchange-optimization-remarks.ll remark message corrected.
All comments are updated.

[ram-NK]

corrected the code formating

[ram-NK]

Hi @bmahjour, Changes are made as per your comments. Could you get the time to review it.
Hi @Meinersbur, Some changes are done over your suggested comments (https://reviews.llvm.org/D135808?id=474010#inline-1332682)

[bmahjour]

LGTM with some minor comments.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1117

ah, ok...in that case please add assert(InnerIndex != OuterIndex && "CostMap should assign unique numbers to each loop")

1151

ideally this should be

if (Row[OuterLoopId] != '=' && Row[OuterLoopId] != 'I')

[Meinersbur]

LGTM.

Sorry I didn't find time to review it.

llvm/test/Transforms/LoopInterchange/perserve-lcssa.ll

172

The test fails for me with the latest version because of opaque pointers emitted by opt.

Regeneration of the test should fix this.

[ram-NK]

All comments are updated.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

 #define DEBUG_TYPE "loop-interchange"
 
 STATISTIC(LoopsInterchanged, "Number of loops interchanged");
 
 static cl::opt<int> LoopInterchangeCostThreshold(
     "loop-interchange-threshold", cl::init(0), cl::Hidden,
     cl::desc("Interchange if you gain more than this number"));
 
 namespace {
 
 using LoopVector = SmallVector<Loop *, 8>;
 
 // TODO: Check if we can use a sparse matrix here.
 using CharMatrix = std::vector<std::vector<char>>;
 
 } // end anonymous namespace
 
public:
   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                                OptimizationRemarkEmitter *ORE)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
 
   /// Check if the loop interchange is profitable.
   bool isProfitable(const Loop *InnerLoop, const Loop *OuterLoop,
                     unsigned InnerLoopId, unsigned OuterLoopId,
                     CharMatrix &DepMatrix,
-                    const DenseMap<const Loop *, unsigned> &CostMap);
+                    const DenseMap<const Loop *, unsigned> &CostMap,
+                    std::unique_ptr<CacheCost> &CC);
 
 private:
   int getInstrOrderCost();
-
+  std::optional<bool> isProfitablePerLoopCacheAnalysis(
+      const DenseMap<const Loop *, unsigned> &CostMap,
+      std::unique_ptr<CacheCost> &CC);
+  std::optional<bool> isProfitablePerInstrOrderCost();
+  std::optional<bool> isProfitableForVectorization(unsigned InnerLoopId,
+                                                   unsigned OuterLoopId,
+                                                   CharMatrix &DepMatrix);
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   /// Scev analysis.
   ScalarEvolution *SE;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
       return false;
     }
     LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
     LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
     if (!LIP.isProfitable(InnerLoop, OuterLoop, InnerLoopId, OuterLoopId,
-                          DependencyMatrix, CostMap)) {
+                          DependencyMatrix, CostMap, CC)) {
       LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
       return false;
     }
 
     ORE->emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "Interchanged",
                                 InnerLoop->getStartLoc(),
                                 InnerLoop->getHeader())
for (Instruction &Ins : *BB) {
             }
           }
         }
       }
     }
   }
   return GoodOrder - BadOrder;
 }
 
-static bool isProfitableForVectorization(unsigned InnerLoopId,
-                                         unsigned OuterLoopId,
-                                         CharMatrix &DepMatrix) {
-  // TODO: Improve this heuristic to catch more cases.
-  // If the inner loop is loop independent or doesn't carry any dependency it is
-  // profitable to move this to outer position.
-  for (auto &Row : DepMatrix) {
-    if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
-      return false;
-    // TODO: We need to improve this heuristic.
-    if (Row[OuterLoopId] != '=')
-      return false;
-  }
-  // If outer loop has dependence and inner loop is loop independent then it is
-  // profitable to interchange to enable parallelism.
-  // If there are no dependences, interchanging will not improve anything.
-  return !DepMatrix.empty();
-}
-
-bool LoopInterchangeProfitability::isProfitable(
-    const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,
-    unsigned OuterLoopId, CharMatrix &DepMatrix,
-    const DenseMap<const Loop *, unsigned> &CostMap) {
-  // TODO: Remove the legacy cost model.
-
+std::optional<bool>
+LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(
+    const DenseMap<const Loop *, unsigned> &CostMap,
+    std::unique_ptr<CacheCost> &CC) {
   // This is the new cost model returned from loop cache analysis.
   // A smaller index means the loop should be placed an outer loop, and vice
   // versa.
   if (CostMap.find(InnerLoop) != CostMap.end() &&
       CostMap.find(OuterLoop) != CostMap.end()) {
     unsigned InnerIndex = 0, OuterIndex = 0;
     InnerIndex = CostMap.find(InnerLoop)->second;
     OuterIndex = CostMap.find(OuterLoop)->second;
     LLVM_DEBUG(dbgs() << "InnerIndex = " << InnerIndex
                       << ", OuterIndex = " << OuterIndex << "\n");
     if (InnerIndex < OuterIndex)
-      return true;
-  } else {
-    // Legacy cost model: this is rough cost estimation algorithm. It counts the
-    // good and bad order of induction variables in the instruction and allows
-    // reordering if number of bad orders is more than good.
-    int Cost = getInstrOrderCost();
-    LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
-    if (Cost < -LoopInterchangeCostThreshold)
-      return true;
-  }
+      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::nullopt;
+}
+
+std::optional<bool>
+LoopInterchangeProfitability::isProfitablePerInstrOrderCost() {
+  if (Cost < 0 && Cost < LoopInterchangeCostThreshold)
+    return std::optional<bool>(true);
+
+  return std::nullopt;
 
-  // It is not profitable as per current cache profitability model. But check if
-  // we can move this loop outside to improve parallelism.
-  if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
-    return true;
+std::optional<bool> LoopInterchangeProfitability::isProfitableForVectorization(
+    unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix) {
+  for (auto &Row : DepMatrix) {
+    // If the inner loop is loop independent or doesn't carry any dependency
+    // it is not profitable to move this to outer position, since we are
+    // likely able to do inner loop vectorization already.
+    if (Row[InnerLoopId] == 'I' || Row[InnerLoopId] == '=')
+      return std::optional<bool>(false);
+
+    // If the outer loop is not loop independent it is not profitable to move
+    // this to inner position, since doing so would not enable inner loop
+    // parallelism.
+    if (Row[OuterLoopId] != 'I' && Row[OuterLoopId] != '=')
+      return std::optional<bool>(false);
+  }
+  // If inner loop has dependence and outer loop is loop independent then it
+  // is/ profitable to interchange to enable inner loop parallelism.
+  // If there are no dependences, interchanging will not improve anything.
+  return std::optional<bool>(!DepMatrix.empty());
+}
 
+bool LoopInterchangeProfitability::isProfitable(
+    const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,
+    unsigned OuterLoopId, CharMatrix &DepMatrix,
+    const DenseMap<const Loop *, unsigned> &CostMap,
+    std::unique_ptr<CacheCost> &CC) {
+  // isProfitable() is structured to avoid endless loop interchange.
+  // If loop cache analysis could decide the profitability then,
+  // profitability check will stop and return the analysis result.
+  // If cache analysis failed to analyze the loopnest (e.g.,
+  // due to delinearization issues) then only check whether it is
+  // profitable for InstrOrderCost. Likewise, if InstrOrderCost failed to
+  // analysis the profitability then only, isProfitableForVectorization
+  // will decide.
+  std::optional<bool> shouldInterchange =
+      isProfitablePerLoopCacheAnalysis(CostMap, CC);
+  if (!shouldInterchange.has_value()) {
+    shouldInterchange = isProfitablePerInstrOrderCost();
+    if (!shouldInterchange.has_value())
+      shouldInterchange =
+          isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
+  }
+  if (!shouldInterchange.has_value()) {
+    ORE->emit([&]() {
+      return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
+                                      InnerLoop->getStartLoc(),
+                                      InnerLoop->getHeader())
+             << "Insufficient information to calculate the cost of loop for "
+                "interchange.";
+    });
+    return false;
+  } else if (!shouldInterchange.value()) {
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
-           << "Interchanging loops is too costly and it does not improve "
-              "parallelism.";
+             << "Interchanging loops is not considered to improve cache "
+                "locality nor vectorization.";
     });
     return false;
   }
+  return true;
+}
 
 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
                                                Loop *InnerLoop) {
   for (Loop *L : *OuterLoop)
     if (L == InnerLoop) {
       OuterLoop->removeChildLoop(L);
       return;
     }

llvm/test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll

 ; CHECK-NEXT:   - String:          Cannot interchange loops due to dependences.
 ; CHECK-NEXT: ...
 
 ; DELIN: --- !Missed
 ; DELIN-NEXT: Pass:            loop-interchange
 ; DELIN-NEXT: Name:            InterchangeNotProfitable
 ; DELIN-NEXT: Function:        test01
 ; DELIN-NEXT: Args:
-; DELIN-NEXT:   - String:          Interchanging loops is too costly and it does not improve parallelism.
+; DELIN-NEXT:   - String:          Interchanging loops is not considered to improve cache locality nor vectorization.
 ; DELIN-NEXT: ...
 
 ;;--------------------------------------Test case 02------------------------------------
 ;; [FIXME] This loop though valid is currently not interchanged due to the
 ;; limitation that we cannot split the inner loop latch due to multiple use of inner induction
 ;; variable.(used to increment the loop counter and to access A[j+1][i+1]
 ;;  for(int i=0;i<N-1;i++)
 ;;    for(int j=1;j<N-1;j++)

llvm/test/Transforms/LoopInterchange/perserve-lcssa.ll

exit:                                             ; preds = %outer.latch
   store i64 %r1, ptr @b, align 4
   store i64 %v4.lcssa, ptr @a, align 4
   ret void
 }
 
 
 ; Make sure we do not crash for loops without reachable exits.
 define void @no_reachable_exits() {
-; Check we interchanged.
-; CHECK-LABEL: @no_reachable_exits() {
+; Check we do not crash.
+; CHECK-LABEL: @no_reachable_exits(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    br label %inner.ph
-; CHECK-LABEL: outer.ph:
-; CHECK-NEXT:    br label %outer.header
-; CHECK-LABEL: inner.ph:
-; CHECK-NEXT:    br label %inner.body
-; CHECK-LABEL: inner.body:
-; CHECK-NEXT:    %tmp31 = phi i32 [ 0, %inner.ph ], [ %[[IVNEXT:[0-9]]], %inner.body.split ]
-; CHECK-NEXT:    br label %outer.ph
-; CHECK-LABEL: inner.body.split:
-; CHECK-NEXT:    %[[IVNEXT]] = add nsw i32 %tmp31, 1
-; CHECK-NEXT:    br i1 false, label %inner.body, label %exit
+; CHECK-NEXT:    br label [[OUTER_PH:%.*]]
+; CHECK:       outer.ph:
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ 0, [[OUTER_PH]] ], [ [[TMP8:%.*]], [[OUTER_LATCH:%.*]] ]
+; CHECK-NEXT:    br i1 undef, label [[INNER_PH:%.*]], label [[OUTER_LATCH]]
+; CHECK:       inner.ph:
+; CHECK-NEXT:    br label [[INNER_BODY:%.*]]
+; CHECK:       inner.body:
+; CHECK-NEXT:    [[TMP31:%.*]] = phi i32 [ 0, [[INNER_PH]] ], [ [[TMP6:%.*]], [[INNER_BODY]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = load ptr, ptr undef, align 8
+; CHECK-NEXT:    [[TMP6]] = add nsw i32 [[TMP31]], 1
+; CHECK-NEXT:    br i1 false, label [[INNER_BODY]], label [[OUTER_LATCH_LOOPEXIT:%.*]]
+; CHECK:       outer.latch.loopexit:
+; CHECK-NEXT:    br label [[OUTER_LATCH]]
+; CHECK:       outer.latch:
+; CHECK-NEXT:    [[TMP8]] = add nsw i32 [[TMP2]], 1
+; CHECK-NEXT:    br i1 false, label [[OUTER_HEADER]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    unreachable
 
 
 bb:
   br label %outer.ph
 
 outer.ph:                              ; preds = %bb
   br label %outer.header
 

llvm/test/Transforms/LoopInterchange/pr57148.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=loop-interchange -cache-line-size=4 -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s
+; RUN: opt < %s -passes=loop-interchange -cache-line-size=4 -loop-interchange-threshold=-100 -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s
 
 ; Make sure the loops are in LCSSA form after loop interchange,
 ; and loop interchange does not hit assertion errors and crash.
 
 target triple = "x86_64-unknown-linux-gnu"
 
 @b = external global [512 x [4 x i32]], align 1
 @c = external global [2 x [4 x i32]], align 1

llvm/test/Transforms/LoopInterchange/profitability.ll

 ; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -pass-remarks-output=%t -verify-dom-info -verify-loop-info \
 ; RUN:     -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange
 ; RUN: FileCheck -input-file %t %s
 
+; RUN: opt < %s -passes=loop-interchange,loop-interchange -cache-line-size=64 \
+; RUN:     -pass-remarks-output=%t -pass-remarks='loop-interchange' -S
+; RUN: cat %t |  FileCheck --check-prefix=PROFIT %s
+
 ;; We test profitability model in these test cases.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x [100 x i32]] zeroinitializer
 
 ;;---------------------------------------Test case 01---------------------------------
-;; Loops interchange will result in code vectorization and hence profitable. Check for interchange.
+;; Loops interchange will result in better cache locality and hence profitable. Check for interchange.
 ;;   for(int i=1;i<100;i++)
 ;;     for(int j=1;j<100;j++)
 ;;       A[j][i] = A[j - 1][i] + B[j][i];
 
 ; CHECK:      Name:            Interchanged
 ; CHECK-NEXT: Function:        interchange_01
 
 define void @interchange_01() {

 for.inc10:
   %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
   %exitcond23 = icmp eq i64 %indvars.iv.next22, 100
   br i1 %exitcond23, label %for.end12, label %for.cond1.preheader
 
 for.end12:
   ret void
 }
+
+;;---------------------------------------Test case 05---------------------------------
+;; This test is to make sure, that multiple invocations of loop interchange will not
+;; undo previous interchange and will converge to a particular order determined by the
+;; profitability analysis.
+;;   for(int i=1;i<100;i++)
+;;     for(int j=1;j<100;j++)
+;;       A[j][0] = A[j][0] + B[j][i];
+
+; CHECK:      Name:            Interchanged
+; CHECK-NEXT: Function:        interchange_05
+
+; PROFIT-LABEL: --- !Passed
+; PROFIT-NEXT: Pass:            loop-interchange
+; PROFIT-NEXT: Name:            Interchanged
+; PROFIT-LABEL: Function:        interchange_05
+; PROFIT-NEXT: Args:
+; PROFIT-NEXT:   - String:          Loop interchanged with enclosing loop.
+; PROFIT-NEXT: ...
+; PROFIT: --- !Missed
+; PROFIT-NEXT: Pass:            loop-interchange
+; PROFIT-NEXT: Name:            InterchangeNotProfitable
+; PROFIT-NEXT: Function:        interchange_05
+; PROFIT-NEXT: Args:
+; PROFIT-NEXT:   - String:          Interchanging loops is not considered to improve cache locality nor vectorization.
+; PROFIT-NEXT: ...
+define void @interchange_05() {
+entry:
+  br label %for2.preheader
+
+for2.preheader:
+  %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]
+  br label %for2
+
+for2:
+  %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]
+  %j.prev = add nsw i64 %j,  -1
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j, i64 0
+  %lv1 = load i32, i32* %arrayidx5
+  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %j,  i64 %i30
+  %lv2 = load i32, i32* %arrayidx9
+  %add = add nsw i32 %lv1, %lv2
+  %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j,  i64 0
+  store i32 %add, i32* %arrayidx13
+  %i.next = add nuw nsw i64 %j,  1
+  %exitcond = icmp eq i64 %j,  99
+  br i1 %exitcond, label %for1.inc14, label %for2
+
+for1.inc14:
+  %i.next31 = add nuw nsw i64 %i30, 1
+  %exitcond33 = icmp eq i64 %i30, 99
+  br i1 %exitcond33, label %for.end16, label %for2.preheader
+
+for.end16:
+  ret void
+}
+