[LoopInterchange] Use getExitBlock()/getExitingBlock instead of manual impl.

[fhahn]

Summary

This also means we have to check if the latch is the exiting block now, as transform expects the latches to be the exiting blocks too.

https://bugs.llvm.org/show_bug.cgi?id=36586

[fhahn]

ping

[efriedma]

lib/Transforms/Scalar/LoopInterchange.cpp

762

This is slightly more generous than getLoopLatchExitBlock; is it okay if the terminator of the exiting block is a switch or invoke? Or do we check that somewhere else?

865–866

Is it actually possible for OuterExit to be null here?

[fhahn]

Thank you very much for having a look Eli and sorry for the delay, I needed to find some time to investigate another failure in the test suite with this change. Together with D45970 and this patch, building the test-suite with LoopInterchange + LTO passes.

I've updated the code to make sure the exiting's block's terminator is a branch instruction.

[fhahn]

lib/Transforms/Scalar/LoopInterchange.cpp

762

Thanks for pointing that out, it was not checked anywhere else. I added checks.

865–866

I had a look and could not spot any other checks ensuring we have a unique exit block.

[efriedma]

lib/Transforms/Scalar/LoopInterchange.cpp

555

What is this closing brace doing here?

Also, the indentation looks weird.

865–866

processLoopList contains an identical check. And I think OuterLoop->getExitingBlock() == OuterLoop->getLoopLatch() && isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator()) implies the exit is unique.

[fhahn]

Fix brace and remove null checks for getExitBlock()

[fhahn]

lib/Transforms/Scalar/LoopInterchange.cpp

555

Argh, sorry about that. Should be fixed now

865–866

There's one check to ensure the outermost loop in a nest has a unique exit block in processLoopList. Ah yes, the check Latch == single exiting block & isa<BranchInst> should guarantee that we have a unique exit block, thanks!

[efriedma]

LGTM

lib/Transforms/Scalar/LoopInterchange.cpp

if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
       DEBUG(dbgs() << "Populating dependency matrix failed\n");
       return false;
     }
 #ifdef DUMP_DEP_MATRICIES
     DEBUG(dbgs() << "Dependence before interchange\n");
     printDepMatrix(DependencyMatrix);
 #endif
 
-    BasicBlock *OuterMostLoopLatch = OuterMostLoop->getLoopLatch();
-    BranchInst *OuterMostLoopLatchBI =
-        dyn_cast<BranchInst>(OuterMostLoopLatch->getTerminator());
-    if (!OuterMostLoopLatchBI || OuterMostLoopLatchBI->getNumSuccessors() != 2)
-      return false;
-
     // Since we currently do not handle LCSSA PHI's any failure in loop
     // condition will now branch to LoopNestExit.
     // TODO: This should be removed once we handle LCSSA PHI nodes.
 
     // Get the Outermost loop exit.
-    BasicBlock *LoopNestExit;
-    if (OuterMostLoopLatchBI->getSuccessor(0) == OuterMostLoop->getHeader())
-      LoopNestExit = OuterMostLoopLatchBI->getSuccessor(1);
-    else
-      LoopNestExit = OuterMostLoopLatchBI->getSuccessor(0);
+    BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
+    if (!LoopNestExit)
+      DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
+    return false;
+  }
 
-    if (isa<PHINode>(LoopNestExit->begin())) {
-      DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "
-                      "since on failure all loops branch to loop nest exit.\n");
-      return false;
     }
 
     unsigned SelecLoopId = selectLoopForInterchange(LoopList);
     // Move the selected loop outwards to the best possible position.
     for (unsigned i = SelecLoopId; i > 0; i--) {
       bool Interchanged =
           processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
       if (!Interchanged)
for (auto I = Block->begin(); isa<PHINode>(I); ++I) {
     // Incoming value for lcssa phi's in outer loop exit can only be inner loop
     // exits lcssa phi else it would not be tightly nested.
     if (!isa<PHINode>(Ins) && isOuterLoopExitBlock)
       return false;
   }
   return true;
 }
 
-static BasicBlock *getLoopLatchExitBlock(BasicBlock *LatchBlock,
-                                         BasicBlock *LoopHeader) {
-  if (BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator())) {
-    assert(BI->getNumSuccessors() == 2 &&
-           "Branch leaving loop latch must have 2 successors");
-    for (BasicBlock *Succ : BI->successors()) {
-      if (Succ == LoopHeader)
-        continue;
-      return Succ;
-    }
-  }
-  return nullptr;
-}
-
 // This function indicates the current limitations in the transform as a result
 // of which we do not proceed.
 bool LoopInterchangeLegality::currentLimitations() {
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
-  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
-  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
-  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
+
+  // transform currently expects the loop latches to also be the exiting
+  // blocks.
+  if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
+      OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
+      !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
+      !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
+    DEBUG(dbgs() << "Loops where the latch is not the exiting block are not"
+                 << " supported currently.\n");
+    ORE->emit([&]() {
+      return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
+                                      OuterLoop->getStartLoc(),
+                                      OuterLoop->getHeader())
+             << "Loops where the latch is not the exiting block cannot be"
+                " interchange currently.";
+    });
+    return true;
+  }
 
   PHINode *InnerInductionVar;
   SmallVector<PHINode *, 8> Inductions;
   SmallVector<PHINode *, 8> Reductions;
   if (!findInductionAndReductions(InnerLoop, Inductions, Reductions)) {
     DEBUG(dbgs() << "Only inner loops with induction or reduction PHI nodes "
                  << "are supported currently.\n");
     ORE->emit([&]() {
ORE->emit([&]() {
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Inner loop structure not understood currently.";
     });
     return true;
   }
 
   // TODO: We only handle LCSSA PHI's corresponding to reduction for now.
-  BasicBlock *LoopExitBlock =
-      getLoopLatchExitBlock(OuterLoopLatch, OuterLoopHeader);
-  if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, true)) {
+  BasicBlock *OuterExit = OuterLoop->getExitBlock();
+  if (!OuterExit || !containsSafePHI(OuterExit, true)) {
     DEBUG(dbgs() << "Can only handle LCSSA PHIs in outer loops currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuter",
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())
              << "Only outer loops with LCSSA PHIs can be interchange "
                 "currently.";
     });
     return true;
   }
 
-  LoopExitBlock = getLoopLatchExitBlock(InnerLoopLatch, InnerLoopHeader);
-  if (!LoopExitBlock || !containsSafePHI(LoopExitBlock, false)) {
+  BasicBlock *InnerExit = InnerLoop->getExitBlock();
+  if (!InnerExit || !containsSafePHI(InnerExit, false)) {
     DEBUG(dbgs() << "Can only handle LCSSA PHIs in inner loops currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "NoLCSSAPHIOuterInner",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Only inner loops with LCSSA PHIs can be interchange "
                 "currently.";
     });

test/Transforms/LoopInterchange/currentLimitation.ll

-; REQUIRES: asserts
-; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info \
-; RUN:     -S -debug 2>&1 | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' \
+; RUN:   -pass-remarks-output=%t -verify-loop-info -verify-dom-info -S | FileCheck -check-prefix=IR %s
+; RUN: FileCheck --input-file=%t %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
  
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x [100 x [100 x i32]]] zeroinitializer
+@C = common global [100 x [100 x i64]] zeroinitializer
  
 ;;--------------------------------------Test case 01------------------------------------
 ;; [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++)
 ;;      A[j+1][i+1] = A[j+1][i+1] + k;
 
-; CHECK: Not interchanging loops. Cannot prove legality.
+; FIXME: Currently fails because of DA changes.
+; IR-LABEL: @interchange_01
+; IR-NOT: split
+
+; CHECK:      Name:            Dependence
+; CHECK-NEXT: Function:        interchange_01
 
 define void @interchange_01(i32 %k, i32 %N) {
  entry:
    %sub = add nsw i32 %N, -1
    %cmp26 = icmp sgt i32 %N, 1
    br i1 %cmp26, label %for.cond1.preheader.lr.ph, label %for.end17
  
  for.cond1.preheader.lr.ph:
for.body4:
    store i32 %add8, i32* %arrayidx7
    %lftr.wideiv = trunc i64 %indvars.iv to i32
    %exitcond = icmp eq i32 %lftr.wideiv, %0
    br i1 %exitcond, label %for.cond.loopexit, label %for.body4
  
  for.end17: 
    ret void
 }
+
+; When currently cannot interchange this loop, because transform currently
+; expects the latches to be the exiting blocks too.
+
+; IR-LABEL: @interchange_02
+; IR-NOT: split
+;
+; CHECK:      Name:            ExitingNotLatch
+; CHECK-NEXT: Function:        interchange_02
+define void @interchange_02(i64 %k, i64 %N) {
+entry:
+  br label %for1.header
+
+for1.header:
+  %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ]
+  br label %for2
+
+for2:
+  %j = phi i64 [ %j.next, %latch ], [ 0, %for1.header ]
+  %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @C, i64 0, i64 %j, i64 %j23
+  %lv = load i64, i64* %arrayidx5
+  %add = add nsw i64 %lv, %k
+  store i64 %add, i64* %arrayidx5
+  %exitcond = icmp eq i64 %j, 99
+  br i1 %exitcond, label %for1.inc10, label %latch
+latch:
+  %j.next = add nuw nsw i64 %j, 1
+  br label %for2
+
+for1.inc10:
+  %j.next24 = add nuw nsw i64 %j23, 1
+  %exitcond26 = icmp eq i64 %j23, 99
+  br i1 %exitcond26, label %for.end12, label %for1.header
+
+for.end12:
+  ret void
+}