[llvm] Bug fix: Loop interchange for multiple loops with conditional statements

[masakazu.ueno]

Summary

Loop interchange for a multiple loop containing if-statement may be performed incorrectly.
Therefore, I modified the loop interchange so that it does not optimize loops that contain conditional statements.

For example, in the following example, "-1, -1" is correct. However, if the loop is interchanged, "1, 1" is output.

#include <stdio.h>

void bar(int x[restrict 2], int a[restrict 2][2]) {
    for (int i=0; i<2; ++i) {
        for (int j=0; j<2; ++j) {
            for (int k=0; k<2; ++k) {
                if (x[j] == a[k][i]) {
                    x[j] = i - k;
                }
            }
        }
    }
}

int main(void) {
    int x[2] = {2, 2};
    int a[2][2] = {{0, 2}, {2, 0}};
    bar(x, a);
    printf("%d, %d\n", x[0], x[1]);
    return 0;
}

Specified options are "-Ofast -mllvm -enable-loopinterchange=true -flegacy-pass-manager".

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

 }
 
 namespace {
 
 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
 class LoopInterchangeLegality {
 public:
   LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
-                          OptimizationRemarkEmitter *ORE)
-      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
+                          DominatorTree *DT, OptimizationRemarkEmitter *ORE)
+      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), DT(DT), ORE(ORE) {}
 
   /// Check if the loops can be interchanged.
   bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
                            CharMatrix &DepMatrix);
 
   /// Check if the loop structure is understood. We do not handle triangular
   /// loops for now.
   bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
 
   bool currentLimitations();
 
   const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
     return OuterInnerReductions;
   }
 
 private:
   bool tightlyNested(Loop *Outer, Loop *Inner);
+  bool hasConditionalStatements(Loop *L);
   bool containsUnsafeInstructions(BasicBlock *BB);
 
   /// Discover induction and reduction PHIs in the header of \p L. Induction
   /// PHIs are added to \p Inductions, reductions are added to
   /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
   /// to be passed as \p InnerLoop.
   bool findInductionAndReductions(Loop *L,
                                   SmallVector<PHINode *, 8> &Inductions,
                                   Loop *InnerLoop);
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   ScalarEvolution *SE;
+  DominatorTree *DT;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter *ORE;
 
   /// Set of reduction PHIs taking part of a reduction across the inner and
   /// outer loop.
   SmallPtrSet<PHINode *, 4> OuterInnerReductions;
 };
#endif
   bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
                    std::vector<std::vector<char>> &DependencyMatrix) {
     LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId << "\n");
     Loop *InnerLoop = LoopList[InnerLoopId];
     Loop *OuterLoop = LoopList[OuterLoopId];
 
-    LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
+    LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, DT, 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(InnerLoopId, OuterLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
if (PHINode *PHI = dyn_cast<PHINode>(User)) {
         return PHI;
       return nullptr;
     }
   }
 
   return nullptr;
 }
 
+/// Return true if the Loop has conditional statements.
+bool LoopInterchangeLegality::hasConditionalStatements(Loop *L) {
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+
+  for (auto BB : L->blocks()) {
+    for (BasicBlock *ExitingBlock : ExitingBlocks) {
+      if (!DT->dominates(BB, ExitingBlock)) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
 bool LoopInterchangeLegality::findInductionAndReductions(
     Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
   if (!L->getLoopLatch() || !L->getLoopPredecessor())
     return false;
   for (PHINode &PHI : L->getHeader()->phis()) {
     RecurrenceDescriptor RD;
     InductionDescriptor ID;
     if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
ORE->emit([&]() {
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())
              << "Only outer loops with induction or reduction PHI nodes can be"
                 " interchanged currently.";
     });
     return true;
   }
 
+  if (hasConditionalStatements(InnerLoop)) {
+    LLVM_DEBUG(dbgs() << "Loops including conditional statements cannot be"
+                      << " interchanged.\n ");
+    ORE->emit([&]() {
+      return OptimizationRemarkMissed(
+                 DEBUG_TYPE, "UnsupportedConditionalStatements",
+                 InnerLoop->getStartLoc(), InnerLoop->getHeader())
+             << "Loops including conditional statements cannot be "
+                "interchanged.";
+    });
+    return true;
+  }
+
   // TODO: Currently we handle only loops with 1 induction variable.
   if (Inductions.size() != 1) {
     LLVM_DEBUG(dbgs() << "Loops with more than 1 induction variables are not "
                       << "supported currently.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "MultiIndutionOuter",
                                       OuterLoop->getStartLoc(),
                                       OuterLoop->getHeader())

llvm/test/Transforms/LoopInterchange/lcssa.ll

for.exit:                                         ; preds = %outer.inc
   store float %float.outer.lcssa, float* @F
   br label %for.end16
 
 for.end16:                                        ; preds = %for.exit
   ret void
 }
 
 ; PHI node in inner latch with multiple predecessors.
-; REMARK: Interchanged
+; REMARK: UnsupportedConditionalStatements
 ; REMARK-NEXT: lcssa_05
 
 define void @lcssa_05(i32* %ptr) {
 entry:
   br label %outer.header
 
 outer.header:                                     ; preds = %outer.inc, %entry
   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]