diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -19,6 +19,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopNestAnalysis.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -584,14 +585,26 @@ } bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) { - LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n"); - - if (!LoopNest::checkLoopsStructure(*OuterLoop, *InnerLoop, *SE)) - return false; BasicBlock *OuterLoopHeader = OuterLoop->getHeader(); BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader(); BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch(); + LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n"); + + // A perfectly nested loop will not have any branch in between the outer and + // inner block i.e. outer header will branch to either inner preheader and + // outerloop latch. + BranchInst *OuterLoopHeaderBI = + dyn_cast(OuterLoopHeader->getTerminator()); + if (!OuterLoopHeaderBI) + return false; + + for (BasicBlock *Succ : successors(OuterLoopHeaderBI)) + if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() && + Succ != OuterLoopLatch) + return false; + + LLVM_DEBUG(dbgs() << "Checking instructions in Loop Header and Loop Latch\n"); // We do not have any basic block in between now make sure the outer header // and outer loop latch doesn't contain any unsafe instructions. if (containsUnsafeInstructions(OuterLoopHeader) || @@ -605,6 +618,22 @@ containsUnsafeInstructions(InnerLoopPreHeader)) return false; + BasicBlock *InnerLoopExit = InnerLoop->getExitBlock(); + // Ensure the inner loop exit block flow to the outer loop latch possibly + // through empty blocks + const BasicBlock &SuccInner = + LoopNest::skipEmptyBlockUntil(InnerLoopExit, OuterLoopLatch); + if (&SuccInner != OuterLoopLatch) { + LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExit + << " does not lead to the outer loop latch.\n";); + return false; + } + // The inner loop exit block does flow to the outer loop latch and not some + // other BBs, now make sure it contains safe instructions, since it will be + // move into the (new) inner loop after interchange + if (containsUnsafeInstructions(InnerLoopExit)) + return false; + LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n"); // We have a perfect loop nest. return true; diff --git a/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll b/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll --- a/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll +++ b/llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll @@ -9,6 +9,7 @@ @B = common global [100 x i32] zeroinitializer @C = common global [100 x [100 x i32]] zeroinitializer @D = common global [100 x [100 x [100 x i32]]] zeroinitializer +@E = common global [100 x [100 x i64]] zeroinitializer ;; Loops not tightly nested are not interchanged ;; for(int j=0;j