[LoopDeletion] Check for irreducible cycles when deleting loops.

[fhahn]

Summary

Loops with irreducible cycles may loop infinitely. Those cannot be
removed, unless the loop/function is marked as mustprogress.

Also discussed in D103382.

[nikic]

LGTM

[asbirlea]

See clang-format suggestion, otherwise LGTM.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

 // side effects or volatile instructions, and do not contribute to the
 // computation of the function's return value.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopDeletion.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/IR/Dominators.h"
+
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 
 using namespace llvm;
 

 
 /// Determines if a loop is dead.
 ///
 /// This assumes that we've already checked for unique exit and exiting blocks,
 /// and that the code is in LCSSA form.
 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
                        SmallVectorImpl<BasicBlock *> &ExitingBlocks,
                        BasicBlock *ExitBlock, bool &Changed,
-                       BasicBlock *Preheader) {
+                       BasicBlock *Preheader, LoopInfo &LI) {
   // Make sure that all PHI entries coming from the loop are loop invariant.
   // Because the code is in LCSSA form, any values used outside of the loop
   // must pass through a PHI in the exit block, meaning that this check is
   // sufficient to guarantee that no loop-variant values are used outside
   // of the loop.
   bool AllEntriesInvariant = true;
   bool AllOutgoingValuesSame = true;
   if (!L->hasNoExitBlocks()) {
static bool isLoopDead(Loop *L, ScalarEvolution &SE,
 
   // The loop or any of its sub-loops looping infinitely is legal. The loop can
   // only be considered dead if either
   // a. the function is mustprogress.
   // b. all (sub-)loops are mustprogress or have a known trip-count.
   if (L->getHeader()->getParent()->mustProgress())
     return true;
 
+  LoopBlocksRPO RPOT(L);
+  RPOT.perform(&LI);
+  // If the loop contains an irreducible cycle, it may loop infinitely.
+  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
+    return false;
+
   SmallVector<Loop *, 8> WorkList;
   WorkList.push_back(L);
   while (!WorkList.empty()) {
     Loop *Current = WorkList.pop_back_val();
     if (hasMustProgress(Current))
       continue;
 
     const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
   // will be branched to, or trying to preserve the branching logic in a loop
   // invariant manner.
   if (!ExitBlock && !L->hasNoExitBlocks()) {
     LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
     return LoopDeletionResult::Unmodified;
   }
   // Finally, we have to check that the loop really is dead.
   bool Changed = false;
-  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
+  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
     LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
   ORE.emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),

llvm/test/Transforms/LoopDeletion/loops-with-irreducible-subloops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -loop-deletion -verify-dom-info -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"
 
+; loop1 contains an irreducible cycle, which may loop infinitely. Do not remove
+; the loop.
 define void @irreducible_subloop_no_mustprogress(i1 %c1, i1 %c2, i1 %c3) {
 ; CHECK-LABEL: @irreducible_subloop_no_mustprogress(
-; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP1:%.*]]
+; CHECK:       loop1:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_BB1:%.*]], label [[IRR_BB1:%.*]]
+; CHECK:       loop1.bb1:
+; CHECK-NEXT:    br label [[IRR_BB2:%.*]]
+; CHECK:       irr.bb1:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP1_LATCH:%.*]], label [[IRR_BB2]]
+; CHECK:       irr.bb2:
+; CHECK-NEXT:    br i1 [[C3:%.*]], label [[LOOP1_LATCH]], label [[IRR_BB1]]
+; CHECK:       loop1.latch:
+; CHECK-NEXT:    br i1 false, label [[LOOP1_LATCH_LOOP1_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop1.latch.loop1_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
+entry:
   br label %loop1
 
 loop1:
   br i1 %c1, label %loop1.bb1, label %irr.bb1
 
 loop1.bb1:
   br label %irr.bb2