[LoopVersioning] Require loop-simplify form for loop versioning.

[fhahn]

Summary

Requiring loop-simplify form for loop versioning ensures that the
runtime check block always dominates the exit block.

This patch closes #30958 (https://llvm.org/bugs/show_bug.cgi?id=30958).

[anemet]

LGTM. @hfinkel, is there a better way to handle infinite loops like this?

[efriedma]

Why are we trying to optimize loops which aren't in loop-simplify form?

[fhahn]

@efriedma Only versioning loops that are in loop simplify form would prevent the error case. If that's the preferred solution I'd be happy to update the patch.

[efriedma]

Making versionLoop() assert that the loop is in loop-simplify form is probably a good idea; versionLoop() is already assuming the loop has a preheader, so it's not much of a stretch. Granted, I'm not sure how much code needs to be fixed to correctly preserve loop-simplify form; versionLoop() itself doesn't preserve it correctly.

[hfinkel]

In D27469#614831, @anemet wrote:

LGTM. @hfinkel, is there a better way to handle infinite loops like this?

I agree with Eli; we generally avoid this kind of situation by only handling loops that can be in loop-simplify form.

[anemet]

In D27469#615851, @hfinkel wrote:

In D27469#614831, @anemet wrote:

LGTM. @hfinkel, is there a better way to handle infinite loops like this?

I agree with Eli; we generally avoid this kind of situation by only handling loops that can be in loop-simplify form.

Yeah, same here, thank Eli! I even tried -loop-simplify on the test case before first replying but I failed to notice that it created an exit block that *no longer* dominated the loop header. So I wrongly concluded that loop-simplify wouldn't help here.

[fhahn]

Require loop-simplify form for loop versioning, as per review comments.

[fhahn]

This patch changed substantially since @anemet accepted it and it would be great if somebody could have another look.

The patch now requires loop-simplify form for loop versioning and the other optimizations requiring loop versioning, which may be to strict.

[ashutosh.nema]

It’s good to avoid loop which are not in loop-simplify form.

This looks OK to me except a minor comment.

lib/Transforms/Scalar/LoopVersioningLICM.cpp

450

Please move this check to "legalLoopStructure".

[fhahn]

@ashutosh.nema thanks for pointing that out, I've moved the check to legalLoopStructure and removed the redundant checks.

[ashutosh.nema]

LGTM, thanks!

lib/Transforms/Scalar/LoopDistribute.cpp

public:
 
   /// \brief Try to distribute an inner-most loop.
   bool processLoop(std::function<const LoopAccessInfo &(Loop &)> &GetLAA) {
     assert(L->empty() && "Only process inner loops.");
 
     DEBUG(dbgs() << "\nLDist: In \"" << L->getHeader()->getParent()->getName()
                  << "\" checking " << *L << "\n");
 
-    BasicBlock *PH = L->getLoopPreheader();
-    if (!PH)
-      return fail("NoHeader", "no preheader");
     if (!L->getExitBlock())
       return fail("MultipleExitBlocks", "multiple exit blocks");
+    if (!L->isLoopSimplifyForm())
+      return fail("NotLoopSimplifyForm",
+                  "loop is not in loop-simplify form");
+
+    BasicBlock *PH = L->getLoopPreheader();
 
     // LAA will check that we only have a single exiting block.
     LAI = &GetLAA(*L);
 
     // Currently, we only distribute to isolate the part of the loop with
     // dependence cycles to enable partial vectorization.
     if (LAI->canVectorizeMemory())
       return fail("MemOpsCanBeVectorized",

lib/Transforms/Scalar/LoopLoadElimination.cpp

bool processLoop() {
 
     if (!Checks.empty() || !LAI.getPSE().getUnionPredicate().isAlwaysTrue()) {
       if (L->getHeader()->getParent()->optForSize()) {
         DEBUG(dbgs() << "Versioning is needed but not allowed when optimizing "
                         "for size.\n");
         return false;
       }
 
+      if (!L->isLoopSimplifyForm()) {
+        DEBUG(dbgs() << "Loop is not is loop-simplify form");
+        return false;
+      }
+
       // Point of no-return, start the transformation.  First, version the loop
       // if necessary.
 
       LoopVersioning LV(LAI, L, LI, DT, PSE.getSE(), false);
       LV.setAliasChecks(std::move(Checks));
       LV.setSCEVChecks(LAI.getPSE().getUnionPredicate());
       LV.versionLoop();
     }

lib/Transforms/Scalar/LoopVersioningLICM.cpp

private:
   bool isLoopAlreadyVisited();
   void setNoAliasToLoop(Loop *);
   bool instructionSafeForVersioning(Instruction *);
 };
 }
 
 /// \brief Check loop structure and confirms it's good for LoopVersioningLICM.
 bool LoopVersioningLICM::legalLoopStructure() {
-  // Loop must have a preheader, if not return false.
-  if (!CurLoop->getLoopPreheader()) {
-    DEBUG(dbgs() << "    loop preheader is missing\n");
+  // Loop must be in loop simplify form.
+  if (!CurLoop->isLoopSimplifyForm()) {
+    DEBUG(
+        dbgs() << "    loop is not in loop-simplify form.\n");
     return false;
   }
   // Loop should be innermost loop, if not return false.
   if (CurLoop->getSubLoops().size()) {
     DEBUG(dbgs() << "    loop is not innermost\n");
     return false;
   }
   // Loop should have a single backedge, if not return false.
if (CurLoop->isAnnotatedParallel()) {
     DEBUG(dbgs() << "    Parallel loop is not worth versioning\n");
     return false;
   }
   // Loop depth more then LoopDepthThreshold are not allowed
   if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
     DEBUG(dbgs() << "    loop depth is more then threshold\n");
     return false;
   }
-  // Loop should have a dedicated exit block, if not return false.
-  if (!CurLoop->hasDedicatedExits()) {
-    DEBUG(dbgs() << "    loop does not has dedicated exit blocks\n");
-    return false;
-  }
   // We need to be able to compute the loop trip count in order
   // to generate the bound checks.
   const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
   if (ExitCount == SE->getCouldNotCompute()) {
     DEBUG(dbgs() << "    loop does not has trip count\n");
     return false;
   }
   return true;

 
 /// \brief Checks legality for LoopVersioningLICM by considering following:
 /// a) loop structure legality   b) loop instruction legality
 /// c) loop memory access legality.
 /// Return true if legal else returns false.
 bool LoopVersioningLICM::isLegalForVersioning() {
   DEBUG(dbgs() << "Loop: " << *CurLoop);
   // Make sure not re-visiting same loop again.
   if (isLoopAlreadyVisited()) {
     DEBUG(
         dbgs() << "    Revisiting loop in LoopVersioningLICM not allowed.\n\n");
     return false;
   }
   // Check loop structure leagality.
   if (!legalLoopStructure()) {
     DEBUG(
         dbgs() << "    Loop structure not suitable for LoopVersioningLICM\n\n");

lib/Transforms/Utils/LoopVersioning.cpp

AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
                              "are disambiguated by memchecks"));
 
 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
                                DominatorTree *DT, ScalarEvolution *SE,
                                bool UseLAIChecks)
     : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT),
       SE(SE) {
   assert(L->getExitBlock() && "No single exit block");
-  assert(L->getLoopPreheader() && "No preheader");
+  assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form");
   if (UseLAIChecks) {
     setAliasChecks(LAI.getRuntimePointerChecking()->getChecks());
     setSCEVChecks(LAI.getPSE().getUnionPredicate());
   }
 }
 
 void LoopVersioning::setAliasChecks(
     SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) {
for (Loop *TopLevelLoop : *LI)
         // We only handle inner-most loops.
         if (L->empty())
           Worklist.push_back(L);
 
     // Now walk the identified inner loops.
     bool Changed = false;
     for (Loop *L : Worklist) {
       const LoopAccessInfo &LAI = LAA->getInfo(L);
-      if (LAI.getNumRuntimePointerChecks() ||
-          !LAI.getPSE().getUnionPredicate().isAlwaysTrue()) {
+      if (L->isLoopSimplifyForm() && (LAI.getNumRuntimePointerChecks() ||
+          !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) {
         LoopVersioning LVer(LAI, L, LI, DT, SE);
         LVer.versionLoop();
         LVer.annotateLoopWithNoAlias();
         Changed = true;
       }
     }
 
     return Changed;

test/Transforms/LoopDistribute/diagnostics-with-hotness.ll

-; RUN: opt -loop-distribute -S -pass-remarks-missed=loop-distribute \
+; RUN: opt -loop-simplify -loop-distribute -S -pass-remarks-missed=loop-distribute \
 ; RUN:     -pass-remarks-analysis=loop-distribute \
 ; RUN:     -pass-remarks-with-hotness < %s 2>&1 | FileCheck %s --check-prefix=HOTNESS
-; RUN: opt -loop-distribute -S -pass-remarks-missed=loop-distribute \
+; RUN: opt -loop-simplify -loop-distribute -S -pass-remarks-missed=loop-distribute \
 ; RUN:     -pass-remarks-analysis=loop-distribute \
 ; RUN:                                < %s 2>&1 | FileCheck %s --check-prefix=NO_HOTNESS
 
-; RUN: opt -passes='require<aa>,loop-distribute' -S -pass-remarks-missed=loop-distribute \
+; RUN: opt -passes='loop-simplify,require<aa>,loop-distribute' -S -pass-remarks-missed=loop-distribute \
 ; RUN:     -pass-remarks-analysis=loop-distribute \
 ; RUN:     -pass-remarks-with-hotness < %s 2>&1 | FileCheck %s --check-prefix=HOTNESS
-; RUN: opt -passes='require<aa>,loop-distribute' -S -pass-remarks-missed=loop-distribute \
+; RUN: opt -passes='loop-simplify,require<aa>,loop-distribute' -S -pass-remarks-missed=loop-distribute \
 ; RUN:     -pass-remarks-analysis=loop-distribute \
 ; RUN:                                < %s 2>&1 | FileCheck %s --check-prefix=NO_HOTNESS
 
 ; This is the input program:
 ;
 ;     1 void forced (char *A, char *B, char *C, int N) {
 ;     2 #pragma clang loop distribute(enable)
 ;     3   for(int i = 0; i < N; i++) {

test/Transforms/LoopDistribute/diagnostics.ll

-; RUN: opt -loop-distribute -S < %s 2>&1 \
+; RUN: opt -loop-simplify -loop-distribute -S < %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=ALWAYS --check-prefix=NO_REMARKS
-; RUN: opt -loop-distribute -S -pass-remarks-missed=loop-distribute < %s 2>&1 \
+; RUN: opt -loop-simplify -loop-distribute -S \
+; RUN:     -pass-remarks-missed=loop-distribute < %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=ALWAYS --check-prefix=MISSED_REMARKS
-; RUN: opt -loop-distribute -S -pass-remarks-analysis=loop-distribute < %s 2>&1 \
+; RUN: opt -loop-simplify -loop-distribute -S \
+; RUN:     -pass-remarks-analysis=loop-distribute < %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=ALWAYS --check-prefix=ANALYSIS_REMARKS
-; RUN: opt -loop-distribute -S -pass-remarks=loop-distribute < %s 2>&1 \
+; RUN: opt -loop-simplify -loop-distribute -S \
+; RUN:     -pass-remarks=loop-distribute < %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=ALWAYS --check-prefix=REMARKS
 
 ; This is the input program:
 ;
 ;     1 void forced (char *A, char *B, char *C, int N) {
 ;     2 #pragma clang loop distribute(enable)
 ;     3   for(int i = 0; i < N; i++) {
 ;     4     A[i] = B[i] * C[i];

test/Transforms/LoopVectorize/diag-with-hotness-info.ll

 ; RUN: opt -S -loop-vectorize -pass-remarks-missed=loop-vectorize \
 ; RUN:     -pass-remarks-with-hotness < %s 2>&1 | \
 ; RUN:     FileCheck -check-prefix=HOTNESS -check-prefix=BOTH %s
 
 ; RUN: opt -S -loop-vectorize -pass-remarks-missed=loop-vectorize < %s 2>&1 | \
 ; RUN:     FileCheck -check-prefix=NO_HOTNESS -check-prefix=BOTH %s
 
 
 ; RUN: opt -S -passes=loop-vectorize -pass-remarks-missed=loop-vectorize \
 ; RUN:     -pass-remarks-with-hotness < %s 2>&1 | \
 ; RUN:     FileCheck -check-prefix=HOTNESS -check-prefix=BOTH %s
 
-; RUN: opt -S -passes=loop-vectorize -pass-remarks-missed=loop-vectorize < %s 2>&1 | \
+; RUN: opt -S -passes=loop-vectorize \
+; RUN:     -pass-remarks-missed=loop-vectorize < %s 2>&1 | \
 ; RUN:     FileCheck -check-prefix=NO_HOTNESS -check-prefix=BOTH %s
 
 
 ;   1 void cold(char *A, char *B, char *C, char *D, char *E, int N) {
 ;   2   for(int i = 0; i < N; i++) {
 ;   3     A[i + 1] = A[i] + B[i];
 ;   4     C[i] = D[i] * E[i];
 ;   5   }

test/Transforms/LoopVersioning/exit-block-dominates-rt-check-block.ll

+; This test ensures loop versioning does not produce an invalid dominator tree
+; if the exit block of the loop (bb0) dominates the runtime check block
+; (bb1 will become the runtime check block).
+
+; RUN: opt -loop-distribute -verify-dom-info -S -o - %s > %t
+; RUN: opt -loop-simplify -loop-distribute -verify-dom-info -S -o - %s > %t
+; RUN: FileCheck --check-prefix CHECK-VERSIONING -input-file %t %s
+
+; RUN: opt -loop-versioning -verify-dom-info -S -o - %s > %t
+; RUN: opt -loop-simplify -loop-versioning -verify-dom-info -S -o - %s > %t
+; RUN: FileCheck --check-prefix CHECK-VERSIONING -input-file %t %s
+
+@c1 = external global i16
+
+define void @f(i16 %a) {
+  br label %bb0
+
+bb0:
+  br label %bb1
+
+bb1:
+  %tmp1 = load i16, i16* @c1
+  br label %bb2
+
+bb2:
+  %tmp2 = phi i16 [ %tmp1, %bb1 ], [ %tmp3, %bb2 ]
+  %tmp4 = getelementptr inbounds [1 x i32], [1 x i32]* undef, i32 0, i32 4
+  store i32 1, i32* %tmp4
+  %tmp5 = getelementptr inbounds [1 x i32], [1 x i32]* undef, i32 0, i32 9
+  store i32 0, i32* %tmp5
+  %tmp3 = add i16 %tmp2, 1
+  store i16 %tmp2, i16* @c1
+  %tmp6 = icmp sle i16 %tmp3, 0
+  br i1 %tmp6, label %bb2, label %bb0
+}
+
+; Simple check to make sure loop versioning happened.
+; CHECK-VERSIONING: bb2.lver.check:

test/Transforms/LoopVersioning/noalias-version-twice.ll

-; RUN: opt -basicaa -loop-distribute -scoped-noalias -loop-versioning -S < %s | FileCheck %s
+; RUN: opt -basicaa -loop-distribute -loop-simplify -scoped-noalias \
+; RUN:     -loop-versioning -S < %s | FileCheck %s
 
 ; Test the metadata generated when versioning an already versioned loop.  Here
 ; we invoke loop distribution to perform the first round of versioning.  It
 ; adds memchecks for accesses that can alias across the distribution boundary.
 ; Then we further version the distributed loops to fully disambiguate accesses
 ; within each.
 ;
 ; So as an example, we add noalias between C and A during the versioning