[LoopDeletion] Allows deletion of possibly infinite side-effect free loops

[atmnpatel]

Summary

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops with non-constant
conditionals that do not have any observable side-effects (as defined by
6.8.5p6) can be assumed by the implementation to terminate, and in the
case of C++, this assumption extends to all functions. The clang
frontend will emit the mustprogress function attribute for C++
functions (D86233, D85393, D86841) and emit the loop metadata
llvm.loop.mustprogress for every loop in C11 or later that has a
non-constant conditional.

This patch modifies LoopDeletion so that only loops with
the llvm.loop.mustprogress metadata or loops contained in functions
that are required to make progress (mustprogress or willreturn) are
checked for observable side-effects. If these loops do not have an
observable side-effect, then we delete them.

Loops without observable side-effects that do not satisfy the above
conditions will not be deleted.

[jdoerfert]

I think the metadata name needs to be reversed, or at least made the opposite of the attribute name.
By default progress is required/guaranteed. With the function attribute it is not. With the metadata it is again for the loop. It has to be this way because the metadata can be dropped. It is only sound to go from required/guaranteed progress to not required/guaranteed, not the other way around.

That means in loop deletion we can remove the loop if:

1. the trip count is known
2. the function does not have the attribute
3. the loop has the metadata

We also need llvm-ir tests for the loop deletion pass that go through all combinations of attribute and metadata.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

232

Describe the metadata rather then the effect.

llvm/lib/Transforms/Utils/LoopUtils.cpp

66

llvm.loop.XXXX, licm is an optimization, this is generic "loop metadata".

[atmnpatel]

Addressed comments, added tests.

[atmnpatel]

Cleaned up tests, and made the changes necessary for changing the attribute names.

[atmnpatel]

Renames.

[atmnpatel]

Updated to rely on the new mustprogress attrs.

[atmnpatel]

Added a helper for readibility, and some missed comment updates.

[atmnpatel]

No-op to fix buildbot failure to apply patch.

[atmnpatel]

Small renames.

[jdoerfert]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

94

Check this earlier. It is cheaper than the check before.

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll

1 ↗

(On Diff #294456)

Why?

llvm/test/Transforms/LoopDeletion/mustprogress.ll

46

The result is the same as above because the function attribute is still present. Is that intended?

193

Why is this not deleted?

[jdoerfert]

Please upload with full context

[atmnpatel]

Fixes.

[atmnpatel]

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll

1 ↗

(On Diff #294456)

If we don't apply the pass, there are extra labels that are generated and left there i.e.
`` br label %step1

step1:
  br label %step2
step2:
...

``
Does it make sense to remove that extra pass and check for this?

llvm/test/Transforms/LoopDeletion/mustprogress.ll

46

Yep, just wanted to cover all bases.

[jdoerfert]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

76

Early exists "always". Though I feel this is not the right place for this. Do you need it here at all when u check it also later?

217

This seems to be the only change we need, isn't it?

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll

1 ↗

(On Diff #294456)

add/modify check lines as needed, I think running more passes here is not helpful, it runs enough as it is.

llvm/test/Transforms/LoopDeletion/mustprogress.ll

85

Why is this not deleted. We should know the trip count, right?

[atmnpatel]

fixes.

[jdoerfert]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

210

not accurate anymore, just go back to the old version, also in the comment above.

220

-or +and

llvm/test/Transforms/LoopDeletion/mustprogress.ll

19

why is the loop not deleted?

50

same as above.

[atmnpatel]

llvm/test/Transforms/LoopDeletion/mustprogress.ll

19

Loop Deletion requires a single exit block.

50

same thing, there's no single exit block

[atmnpatel]

Fixes.

[atmnpatel]

Updates made to try to remove infinite loops with no exit edge. It seems to work with the new pass manager, but hopelessly breaks for the old pass manager, changes planned.

[atmnpatel]

Fixes.

[jdoerfert]

The new code/functionality wrt. no exit blocks should be a separate commit.

[atmnpatel]

Reverted to prior diff.

[atmnpatel]

This comment was removed by atmnpatel.

[atmnpatel]

fixed splice.

[jdoerfert]

LGTM.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

59

Nit: add the word back.

[atmnpatel]

Added word back in.

[atmnpatel]

final fixes.

[atmnpatel]

This introduced a compile-time error that showed up during a stage 2 build.

[atmnpatel]

I believe this happened becase when I removed the loop, I did not update MemorySSA. The exact error was from GVN, but this update seems to fix the stage 2 build compile time error locally (I checked by running the build bot script).

[nikic]

llvm/lib/Transforms/Utils/LoopUtils.cpp

658

These fixes look unrelated. Is it possible to test them separately?

[atmnpatel]

llvm/lib/Transforms/Utils/LoopUtils.cpp

658

So my understanding is that the actual line that fixes the compile time error is 651, that is, just having that line fixes the compile time error. I would assume its because before I didn't tell the dominator tree to remove the edge connecting the preheader and header, and not having that cascade, GVN was unable to iterate properly in some cases over the (now) dead blocks because it wasn't updated in LLVM's internal structures. The actual error was from the iteration in GVN::assignValNumForDeadCode() where it would try to iterate through a block that partially existed but didn't really.

The lines 652-660 that update MemorySSA I added because in the other more general case above, we seem to update MemorySSA right after updating the Dominator Tree.

[jdoerfert]

@nikic Is this OK or do you want it split?

llvm/lib/Transforms/Utils/LoopUtils.cpp

658

Nit: Move DTU into the conditional

[nikic]

In D86844#2465027, @jdoerfert wrote:

@nikic Is this OK or do you want it split?

After looking again, I assume this can't really be split, because prior to this change we would never delete a loop without an exit block, so the code was not reachable before. So this looks fine to me.

llvm/lib/Transforms/Utils/LoopUtils.cpp

626

Unrelated, but why do these updates happen before the branch from preheader to exit is added in IR? Shouldn't it be the other way around according to the DTU contract?

658

You might also move this code after the if/else, as it's the same in both branches. As the update strategy is eager, reusing the same DTU object shouldn't make a difference. (Feel free to leave as is though.)

[fhahn]

clang/test/Misc/loop-opt-setup.c

26

This comment needs updating, there's no loop there now. Or better, add a run-line with a C standard version that does not have the forward progress guarantee, e.g. -std=c99 and one with an explicit standard that has it and have different check lines for the 2 cases.

llvm/test/Other/loop-deletion-printer.ll

17

Is this change related to the patch? Same for the other test changes that just add willreturn?

[jonpa]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

136

Seems like it would be nice to update this comment.

215

and also this comment..?

[atmnpatel]

Addressed comments

[atmnpatel]

llvm/lib/Transforms/Utils/LoopUtils.cpp

626

Isn't that branch added on line 602? My understanding was the changes on line 640 onwards are for removing, not introducing a branch.

llvm/test/Other/loop-deletion-printer.ll

17

Yep, if these test functions aren't marked willreturn, we won't delete the loop because it could be a legal infinite loop from C/C++.

[fhahn]

llvm/test/Other/loop-deletion-printer.ll

17

I don't think that is the case here. The trip count of the loop here is constant, so it cannot be infinite. Also, the existing code already removes the loop, without willreturn, as implied by no changes to the check lines?

I did not check all other cases, but I would expect that willreturn does not need to be added to cases where the trip count is a known constant and that already get removed.

[atmnpatel]

As expected, @fhahn was right, adding willreturn to all those tests was an artifact from previous revisions of this patch and it passed the tests so I didn't pay them any mind, but I removed them now.

[xbolva00]

Can you reland this patch now?

[atmnpatel]

Yep, sorry, I'm just waiting for a final stamp of approval from one of the reviewers.

[fhahn]

LGTM, thanks!

clang/test/Misc/loop-opt-setup.c

26

Can you also explain the C99 case in the comment?

llvm/lib/Transforms/Utils/LoopUtils.cpp

626

Shouldn't it be the other way around according to the DTU contract?

Yes I think so. Perhaps a missing case in the DTU validator. Probably good to check/fix separately.

llvm/test/Transforms/LoopDeletion/mustprogress.ll

2

probably good to also add -verify-dom-info

5

FWIW, I don't think the C code doesn't add much, but I don't have any strong feelings about it. The IR is what is key and it's really small.

[xbolva00]

Do you plan to implement gcc’s option in Clang as followup?

-ffinite-loops / -fno-finite-loops
Assume that a loop with an exit will eventually take the exit and not loop indefinitely. This allows the compiler to remove loops that otherwise have no side-effects, not considering eventual endless looping as such.

This option is enabled by default at -O2 for C++ with -std=c++11 or higher.

?

[atmnpatel]

In D86844#2475552, @xbolva00 wrote:

Do you plan to implement gcc’s option in Clang as followup?

I was not planning on it but I can if no one is planning on it and doesn't mind waiting a bit.

Also, clang/test/Misc/loop-opt-setup.c had a bad run line, it's being fixed in D93952, and I'll try to land it again after that.

[fhahn]

Now that the test is fixed, this could be re-landed, right?

[xbolva00]

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

[fhahn]

In D86844#2481922, @xbolva00 wrote:

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

[atmnpatel]

In D86844#2484568, @fhahn wrote:

In D86844#2481922, @xbolva00 wrote:

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

[fhahn]

In D86844#2484639, @atmnpatel wrote:

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

The source is C++, so the C11 standard should be irrelevant. I left a comment at D86841, this seems more appropriate to discuss the issue, as it is unrelated to -loop-deletion.

[xbolva00]

In D86844#2484639, @atmnpatel wrote:

In D86844#2484568, @fhahn wrote:

In D86844#2481922, @xbolva00 wrote:

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

For C yes, but are there such rules for C++? GCC in c++ mode does not check for non-zero constant expr and happily performs this optimization.

[jdoerfert]

In D86844#2484679, @xbolva00 wrote:

In D86844#2484639, @atmnpatel wrote:

In D86844#2484568, @fhahn wrote:

In D86844#2481922, @xbolva00 wrote:

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

For C yes, but are there such rules for C++? GCC in c++ mode does not check for non-zero constant expr and happily performs this optimization.

@xbolva00 want to provide a follow up patch then :) ?

[uabelho]

I wrote
https://github.com/llvm/llvm-project/issues/58123
about a crash that I bisected to this patch.

clang/test/Misc/loop-opt-setup.c

void Helper() {
 
   while (num_active)
 #pragma clang loop unroll(full)
     for (int i = 0; i < 5; ++i)
       if (nodes[i])
         --num_active;
 }
 
 // Check br i1 to make sure the loop is gone, there will still be a label branch for the infinite loop.
-// CHECK-LABEL: Helper
-// CHECK: br label
+// CHECK-LABEL: Helper 
+// CHECK: entry:
 // CHECK-NOT: br i1
-// CHECK: br label
+// CHECK-NEXT: ret void

llvm/include/llvm/Transforms/Utils/LoopUtils.h

makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
                    bool AlwaysNew = false);
 
 /// Look for the loop attribute that disables all transformation heuristic.
 bool hasDisableAllTransformsHint(const Loop *L);
 
 /// Look for the loop attribute that disables the LICM transformation heuristics.
 bool hasDisableLICMTransformsHint(const Loop *L);
 
+/// Look for the loop attribute that requires progress within the loop.
+bool hasMustProgress(const Loop *L);
+
 /// The mode sets how eager a transformation should be applied.
 enum TransformationMode {
   /// The pass can use heuristics to determine whether a transformation should
   /// be applied.
   TM_Unspecified,
 
   /// The transformation should be applied without considering a cost model.
   TM_Enable,

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

static bool isLoopDead(Loop *L, ScalarEvolution &SE,
   // 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;
   for (PHINode &P : ExitBlock->phis()) {
     Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
 
-    // Make sure all exiting blocks produce the same incoming value for the exit
-    // block.  If there are different incoming values for different exiting
-    // blocks, then it is impossible to statically determine which value should
-    // be used.
+    // Make sure all exiting blocks produce the same incoming value for the
+    // exit block.  If there are different incoming values for different
+    // exiting blocks, then it is impossible to statically determine which
+    // value should be used.
     AllOutgoingValuesSame =
         all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
           return incoming == P.getIncomingValueForBlock(BB);
         });
 
     if (!AllOutgoingValuesSame)
       break;
 
     if (Instruction *I = dyn_cast<Instruction>(incoming))
       if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
         AllEntriesInvariant = false;
         break;
 
       if (Instruction *I = dyn_cast<Instruction>(incoming))
         if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
           AllEntriesInvariant = false;
           break;
         }
     }
   }
 
   if (Changed)
     SE.forgetLoopDispositions(L);
 
   if (!AllEntriesInvariant || !AllOutgoingValuesSame)
     return false;
 
   // Make sure that no instructions in the block have potential side-effects.
   // This includes instructions that could write to memory, and loads that are
   // marked volatile.
   for (auto &I : L->blocks())
     if (any_of(*I, [](Instruction &I) {
           return I.mayHaveSideEffects() && !I.isDroppable();
         }))
       return false;
   return true;
 }
 
 /// This function returns true if there is no viable path from the
 /// entry block to the header of \p L. Right now, it only does
assert(!pred_empty(Preheader) &&
          "Preheader should have predecessors at this point!");
   // All the predecessors have the loop preheader as not-taken target.
   return true;
 }
 
 /// Remove a loop if it is dead.
 ///
 /// A loop is considered dead if it does not impact the observable behavior of
 /// the program other than finite running time. This never removes a loop that
 /// might be infinite (unless it is never executed), as doing so could change
 /// the halting/non-halting nature of a program.
 ///
 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
 /// order to make various safety checks work.
 ///
 /// \returns true if any changes were made. This may mutate the loop even if it
 /// is unable to delete it due to hoisting trivially loop invariant
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
   // in the loop are invariant.
   SmallVector<BasicBlock *, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   // We require that the loop have either a single exit block or no exit
   // blocks. Otherwise, we'd be in the situation of needing to be able to
   // solve statically which exit block will be branched to, or trying to
   // preserve the branching logic in a loop invariant manner.
-  if (!ExitBlock && L->getNumExitBlocks() != 0) {
+  if (!ExitBlock) {
     LLVM_DEBUG(dbgs() << "Deletion requires single 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)) {
     LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   // Don't remove loops for which we can't solve the trip count.
   // They could be infinite, in which case we'd be changing program behavior.
   const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
-  if (isa<SCEVCouldNotCompute>(S)) {
-    LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
+  if (isa<SCEVCouldNotCompute>(S) &&
+      !L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) {
+    LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
+                         "not required to make progress.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
   ORE.emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
                               L->getHeader())

llvm/lib/Transforms/Utils/LoopUtils.cpp

static cl::opt<bool> ForceReductionIntrinsic(
     "force-reduction-intrinsics", cl::Hidden,
     cl::desc("Force creating reduction intrinsics for testing."),
     cl::init(false));
 
 #define DEBUG_TYPE "loop-utils"
 
 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
 static const char *LLVMLoopDisableLICM = "llvm.licm.disable";
+static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
 
 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                    MemorySSAUpdater *MSSAU,
                                    bool PreserveLCSSA) {
   bool Changed = false;
 
   // We re-use a vector for the in-loop predecesosrs.
   SmallVector<BasicBlock *, 4> InLoopPredecessors;

 bool llvm::hasDisableAllTransformsHint(const Loop *L) {
   return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
 }
 
 bool llvm::hasDisableLICMTransformsHint(const Loop *L) {
   return getBooleanLoopAttribute(L, LLVMLoopDisableLICM);
 }
 
+bool llvm::hasMustProgress(const Loop *L) {
+  return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
+}
+
 TransformationMode llvm::hasUnrollTransformation(Loop *L) {
   if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable"))
     return TM_SuppressedByUser;
 
   Optional<int> Count =
       getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
   if (Count.hasValue())
     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
if (L->getNumExitBlocks() == 0) {
     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
     if (DT) {
       DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}});
       if (MSSA) {
         MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}, *DT);
         if (VerifyMemorySSA)
           MSSA->verifyMemorySSA();
       }
     }
 
     // Disconnect the loop body by branching directly to its exit.
     Builder.SetInsertPoint(Preheader->getTerminator());
     Builder.CreateBr(ExitBlock);
     // Remove the old branch.
     Preheader->getTerminator()->eraseFromParent();
 
     if (DT) {
void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
   llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
 
   // Given LCSSA form is satisfied, we should not have users of instructions
   // within the dead loop outside of the loop. However, LCSSA doesn't take
   // unreachable uses into account. We handle them here.
   // We could do it after drop all references (in this case all users in the
   // loop will be already eliminated and we have less work to do but according
   // to API doc of User::dropAllReferences only valid operation after dropping
   // references, is deletion. So let's substitute all usages of
   // instruction from the loop with undef value of corresponding type first.
   for (auto *Block : L->blocks())
     for (Instruction &I : *Block) {
       auto *Undef = UndefValue::get(I.getType());
       for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
         Use &U = *UI;
         ++UI;
         if (auto *Usr = dyn_cast<Instruction>(U.getUser()))

llvm/test/Other/loop-deletion-printer.ll

 ; Make sure that Loop which was invalidated by loop-deletion
 ; does not lead to problems for -print-after-all and is just skipped.
 ;
 ; RUN: opt < %s -disable-output \
 ; RUN:     -passes=loop-instsimplify -print-after-all  2>&1 | FileCheck %s -check-prefix=SIMPLIFY
 ; RUN: opt < %s -disable-output \
 ; RUN:     -passes=loop-deletion,loop-instsimplify -print-after-all  2>&1 | FileCheck %s -check-prefix=DELETED
 ; RUN: opt < %s -disable-output \
 ; RUN:     -passes=loop-deletion,loop-instsimplify -print-after-all -print-module-scope  2>&1 | FileCheck %s -check-prefix=DELETED-BUT-PRINTED
 ;
 ; SIMPLIFY: IR Dump {{.*}} LoopInstSimplifyPass
 ; DELETED-NOT: IR Dump {{.*}}LoopInstSimplifyPass
 ; DELETED-NOT: IR Dump {{.*}}LoopDeletionPass
 ; DELETED-BUT-PRINTED: IR Dump {{.*}}LoopDeletionPass {{.*invalidated:}}
 ; DELETED-BUT-PRINTED-NOT: IR Dump {{.*}}LoopInstSimplifyPass
 
-define void @deleteme() {
+define void @deleteme() willreturn {
 entry:
   br label %loop
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
   %iv.next = add i32 %iv, 1
   %check = icmp ult i32 %iv.next, 3
   br i1 %check, label %loop, label %exit
 exit:
   ret void
 }
 

llvm/test/Other/loop-pm-invalidation.ll

 l.0.latch:
   %flag.0 = load volatile i1, i1* %ptr
   br i1 %flag.0, label %l.0.header, label %exit
 
 exit:
   ret void
 }
 
-define void @dead_loop() {
+define void @dead_loop() willreturn {
 ; CHECK-LOOP-INV: Starting {{.*}}Function pass manager run
 ; CHECK-LOOP-INV-NEXT: Starting {{.*}}Function pass manager run
 ; CHECK-LOOP-INV-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-LOOP-INV-NEXT: Running analysis: LoopAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-LOOP-INV-NEXT: Running pass: LCSSAPass
 ; CHECK-LOOP-INV-NEXT: Finished {{.*}}Function pass manager run

llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll

 ; Here we have a case where there are two loops and LICM is hoisting an 
 ; instruction from one loop into the other loop!  This is obviously bad and 
 ; happens because preheader insertion doesn't insert a preheader for this
 ; case... bad.
 
 ; RUN: opt < %s -licm -loop-deletion -simplifycfg -S | \
 ; RUN:   not grep "br "
 
-define i32 @main(i32 %argc) {
+define i32 @main(i32 %argc) willreturn {
 ; <label>:0
   br label %bb5
 bb5:    ; preds = %bb5, %0
   %I = phi i32 [ 0, %0 ], [ %I2, %bb5 ]    ; <i32> [#uses=1]
   %I2 = add i32 %I, 1   ; <i32> [#uses=2]
   %c = icmp eq i32 %I2, 10    ; <i1> [#uses=1]
   br i1 %c, label %bb5, label %bb8
 bb8:    ; preds = %bb8, %bb5
   %cann-indvar = phi i32 [ 0, %bb8 ], [ 0, %bb5 ]    ; <i32> [#uses=0]
   %X = add i32 %argc, %argc   ; <i32> [#uses=1]
   br i1 false, label %bb8, label %bb10
 bb10:   ; preds = %bb8
   ret i32 %X
 }
 

llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll

 ; RUN: opt < %s -loop-deletion -S
 ; RUN: opt < %s -loop-deletion -analyze -domtree 2>&1 | FileCheck -check-prefix=DT %s
 ; RUN: opt < %s -loop-deletion -analyze -verify-dom-info
 
 ; CHECK: for.body
 ; CHECK-NOT: for.cond1
 
 ; Verify only the important parts of the DomTree.
 ; DT: [1] %entry
 ; DT:   [2] %for.cond
 ; DT:     [3] %lbl63A679E5
 ; DT:     [3] %for.cond9
 ; DT:     [3] %lbl64774A9B
 ; DT:     [3] %for.body
 ; DT:       [4] %for.cond3.loopexit
 
-define i32 @fn1() {
+define i32 @fn1() willreturn {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %entry
   br i1 undef, label %lbl63A679E5, label %for.body
 
 for.body:                                         ; preds = %for.cond
   br label %for.cond1

llvm/test/Transforms/LoopDeletion/basic-remark.ll

 ; RUN: opt -loop-deletion %s -o /dev/null --pass-remarks-output=%t --pass-remarks-filter=loop-delete
 ; RUN: cat %t | FileCheck %s
 
 ; Check that we use the right debug location: the loop header.
 ; CHECK:      --- !Passed
 ; CHECK-NEXT: Pass:            loop-delete
 ; CHECK-NEXT: Name:            Invariant
 ; CHECK-NEXT: DebugLoc:        { File: loop.c, Line: 2, Column: 3 }
 ; CHECK-NEXT: Function:        main
 ; CHECK-NEXT: Args:
 ; CHECK-NEXT:   - String:          Loop deleted because it is invariant
 ; CHECK-NEXT: ...
-define i32 @main() local_unnamed_addr #0 {
+define i32 @main() local_unnamed_addr willreturn {
 entry:
   br label %for.cond, !dbg !9
 
 for.cond:
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.cond ]
   %cmp = icmp ult i32 %i.0, 1000
   %inc = add nuw nsw i32 %i.0, 1
   br i1 %cmp, label %for.cond, label %for.cond.cleanup

llvm/test/Transforms/LoopDeletion/diundef.ll

 ; RUN: opt %s -loop-deletion -S | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.14.0"
 
 @a = common local_unnamed_addr global i32 0, align 4, !dbg !0
 
-define i32 @b() local_unnamed_addr !dbg !12 {
+define i32 @b() local_unnamed_addr willreturn !dbg !12 {
 entry:
   call void @llvm.dbg.value(metadata i32 0, metadata !16, metadata !DIExpression()), !dbg !17
   br label %for.cond, !dbg !18
 
 for.cond:                                         ; preds = %for.cond, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.cond ], !dbg !20
   call void @llvm.dbg.value(metadata i32 %i.0, metadata !16, metadata !DIExpression()), !dbg !17
   %inc = add nuw nsw i32 %i.0, 1, !dbg !21

llvm/test/Transforms/LoopDeletion/invalidation.ll

 ; Ensure we don't run analyses over loops after they've been deleted. We run
 ; one version with a no-op loop pass to make sure that the loop doesn't get
 ; simplified away.
 ;
 ; RUN: opt < %s -passes='require<iv-users>,no-op-loop,require<iv-users>' -S \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK,BEFORE
 ; RUN: opt < %s -passes='require<iv-users>,loop-deletion,require<iv-users>' -S \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK,AFTER
 
 
-define void @foo(i64 %n, i64 %m) nounwind {
+define void @foo(i64 %n, i64 %m) nounwind willreturn {
 ; CHECK-LABEL: @foo(
 
 entry:
   br label %bb
 ; CHECK:       entry:
 ; BEFORE-NEXT:   br label %bb
 ; AFTER-NEXT:    br label %return
 

llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll

 ; RUN: opt < %s -loop-deletion -S | FileCheck %s
 ; RUN: opt < %s -passes='loop(loop-deletion)' -S | FileCheck %s
 
 ; ScalarEvolution can prove the loop iteration is finite, even though
 ; it can't represent the exact trip count as an expression. That's
 ; good enough to let the loop be deleted.
 
 ; CHECK:      entry:
 ; CHECK-NEXT:   br label %return
 
 ; CHECK:      return:
 ; CHECK-NEXT:   ret void
 
-define void @foo(i64 %n, i64 %m) nounwind {
+define void @foo(i64 %n, i64 %m) nounwind willreturn {
 entry:
   br label %bb
 
 bb:
   %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]
   %t0 = add i64 %x.0, 1
   %t1 = icmp slt i64 %x.0, %n
   %t3 = icmp sgt i64 %x.0, %m
   %t4 = and i1 %t1, %t3
   br i1 %t4, label %bb, label %return
 
 return:
   ret void
 }

llvm/test/Transforms/LoopDeletion/multiple-exits.ll

 ; Checks whether dead loops with multiple exits can be eliminated.
 ; Note that we loop simplify and LCSSA over the test cases to make sure the
 ; critical components remain after those passes and are visible to the loop
 ; deletion pass.
 ;
 ; RUN: opt < %s -loop-simplify -lcssa -S | FileCheck %s --check-prefixes=CHECK,BEFORE
 ; RUN: opt < %s -loop-deletion -S | FileCheck %s --check-prefixes=CHECK,AFTER
 ;
 ; RUN: opt < %s -passes=no-op-loop -S | FileCheck %s --check-prefixes=CHECK,BEFORE
 ; RUN: opt < %s -passes=loop-deletion -S | FileCheck %s --check-prefixes=CHECK,AFTER
 
 
-define void @foo(i64 %n, i64 %m) nounwind {
+define void @foo(i64 %n, i64 %m) #0 {
 ; CHECK-LABEL: @foo(
 
 entry:
   br label %bb
 ; CHECK:       entry:
 ; BEFORE-NEXT:   br label %bb
 ; AFTER-NEXT:    br label %return
 

 ; AFTER-NOT:     br
 
 return:
   ret void
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 }
 
-define i64 @bar(i64 %n, i64 %m, i64 %maybe_zero) nounwind {
+define i64 @bar(i64 %n, i64 %m, i64 %maybe_zero) #0 {
 ; CHECK-LABEL: @bar(
 
 entry:
   br label %bb
 ; CHECK:       entry:
 ; BEFORE-NEXT:   br label %bb
 ; AFTER-NEXT:    br label %return
 

 ; CHECK:       return:
 ; BEFORE-NEXT:   %[[X:.*]] = phi i64 [ 10, %bb ], [ 10, %bb2 ], [ 10, %bb3 ]
 ; AFTER-NEXT:    %[[X:.*]] = phi i64 [ 10, %entry ]
 ; CHECK-NEXT:    ret i64 %[[X]]
 }
 
 ; This function has a loop which looks like @bar's but that cannot be deleted
 ; because which path we exit through determines which value is selected.
-define i64 @baz(i64 %n, i64 %m, i64 %maybe_zero) nounwind {
+define i64 @baz(i64 %n, i64 %m, i64 %maybe_zero) #0 {
 ; CHECK-LABEL:  @baz(
 
 entry:
   br label %bb
 ; CHECK:       entry:
 ; CHECK-NEXT:    br label %bb
 
 bb:

 
 return:
   %x.lcssa = phi i64 [ 12, %bb ], [ 10, %bb2 ], [ 10, %bb3 ]
   ret i64 %x.lcssa
 ; CHECK: return:
 ; CHECK-NEXT:  %[[X:.*]] = phi i64 [ 12, %bb ], [ 10, %bb2 ], [ 10, %bb3 ]
 ; CHECK-NEXT:  ret i64 %[[X]]
 }
+
+attributes #0 = { nounwind willreturn }
 No newline at end of file

llvm/test/Transforms/LoopDeletion/mustprogress.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --check-attributes
 ; RUN: opt < %s -loop-deletion -S | FileCheck %s
 
 ;; Original C Code:
 ;;  void unknown_tripcount_mustprogress_attr_mustprogress_loopmd(int a, int b) {
 ;;    for (; a < b;) ;
 ;;    for (;;) ;
 ;;  }
 
 define void @unknown_tripcount_mustprogress_attr_mustprogress_loopmd(i32 %a, i32 %b) #0 {
 ; CHECK: Function Attrs: mustprogress
 ; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_mustprogress_attr_mustprogress_loopmd
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) [[ATTR0:#.*]] {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_END:%.*]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    br label [[FOR_COND1]]
 ;
 entry:
   br label %for.cond
 for.cond:
   %cmp = icmp slt i32 %a, %b
   br i1 %cmp, label %for.body, label %for.end
 for.body:
   br label %for.cond, !llvm.loop !2

 ;;  }
 ;;  => Removed mustprogress loop attribute
 
 define void @unknown_tripcount_mustprogress_attr_no_mustprogess_loopmd(i32 %a, i32 %b) #0 {
 ; CHECK: Function Attrs: mustprogress
 ; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_mustprogress_attr_no_mustprogess_loopmd
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) [[ATTR0]] {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_END:%.*]]
 ; CHECK:       for.end:
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    br label [[FOR_COND1]]
 ;
 entry:
   br label %for.cond
 for.cond:
   %cmp = icmp slt i32 %a, %b
   br i1 %cmp, label %for.body, label %for.end
 for.body:
   br label %for.cond

 entry:
   br label %for.cond
 for.cond:
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %cmp = icmp slt i32 %i.0, 5
   br i1 %cmp, label %for.body, label %for.end
 for.body:
   br label %for.inc
 for.inc:
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 for.end:
   ret void
 }
 
 ;; Original C Code:
 ;;  void known_tripcount_no_mustprogress_attr_mustprogress_loopmd() {

 
 define void @unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd(i32 %a, i32 %b) {
 ; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_END:%.*]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.cond
 for.cond:
   %cmp = icmp slt i32 %a, %b
   br i1 %cmp, label %for.body, label %for.end
 for.body:
   br label %for.cond, !llvm.loop !6
 for.end:

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

 exit:
  ret i64 %y.add
 }
 
 
 ; Show recursive deletion of loops. Since we start with subloops and progress outward 
 ; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge
 ; from L2's preheader to L1's exit block is never taken. So, L1 gets deleted as well.
-define void @test8(i64 %n) {
+define void @test8(i64 %n) #0 {
 ; CHECK-LABEL: test8
 ; CHECK-LABEL: entry:
 ; CHECK-NEXT: br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT: ret void
 ; REMARKS-LABEL: Function: test8
 ; REMARKS: Loop deleted because it never executes
 entry: 

  ret void
 }
 
 ; same as test10, but L3 does not contain call.
 ; So, in the first iteration, all statements of L3 are made invariant, and L3 is
 ; deleted.
 ; In the next iteration, since L2 is never executed and has no subloops, we delete
 ; L2 as well. Finally, the outermost loop L1 is deleted.
-define void @test11(i64 %n) {
+define void @test11(i64 %n) #0 {
 ; CHECK-LABEL: test11
 ; CHECK-LABEL: entry:
 ; CHECK-NEXT: br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT: ret void
 ; REMARKS-LABEL: Function: test11
 ; REMARKS: Loop deleted because it is invariant
 ; REMARKS-LABEL: Function: test11
L3:
   br i1 %cond2, label %L3, label %L2
 
 exit:
  ret void
 }
 
 
 ; 2 edges from a single exiting block to the exit block.
-define i64 @test12(i64 %n){
+define i64 @test12(i64 %n) #0 {
 ;CHECK-LABEL: @test12
 ; CHECK-NOT: L1:
 ; CHECK-NOT: L1Latch:
 ; CHECK-LABEL: L1.preheader:
 ; CHECK-NEXT:    br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT:    %y.phi = phi i64 [ undef, %L1.preheader ]
 ; CHECK-NEXT:    ret i64 %y.phi
L1Latch:                                          ; preds = %L1
   ]
 
 exit:                                             ; preds = %L1Latch, %L1Latch
   %y.phi = phi i64 [ 10, %L1Latch ], [ 10, %L1Latch ], [ %y.next, %L1]
   ret i64 %y.phi
 }
 
 ; multiple edges to exit block from the same exiting blocks
-define i64 @test13(i64 %n) {
+define i64 @test13(i64 %n) #0 {
 ; CHECK-LABEL: @test13
 ; CHECK-NOT: L1:
 ; CHECK-NOT: L1Latch:
 ; CHECK-LABEL: L1.preheader:
 ; CHECK-NEXT:    br label %exit
 ; CHECK-LABEL: exit:
 ; CHECK-NEXT:    %y.phi = phi i64 [ undef, %L1.preheader ]
 ; CHECK-NEXT:    ret i64 %y.phi
switch i64 %n, label %L1 [
     i64 30, label %exit
     i64 40, label %exit
   ]
 
 exit:                                             ; preds = %L1Block, %L1, %L1Latch
   %y.phi = phi i64 [ 10, %L1Block ], [ 10, %L1Block ], [ %y.next, %L1 ], [ 30, %L1Latch ], [ 30, %L1Latch ]
   ret i64 %y.phi
 }
+
+attributes #0 = { willreturn }

llvm/test/Transforms/LoopDeletion/use-in-unreachable.ll

 ; RUN: opt < %s -loop-deletion -S | FileCheck %s
 
 ; Checking that possible users of instruction from the loop in
 ; unreachable blocks are handled.
 
-define i64 @foo() {
+define i64 @foo() willreturn {
 entry:
   br label %invloop
 ; CHECK-LABEL-NOT: invloop
 invloop:
   %indvar1 = phi i64 [ 3, %entry ], [ %indvar2, %invloop_iter ]
   %check = icmp ult i64 %indvar1, 400
   br i1 %check, label %invloop_iter, label %loopexit
 invloop_iter:

llvm/test/Transforms/SCCP/calltest.ll

 ; RUN: opt < %s -sccp -loop-deletion -simplifycfg -S | FileCheck %s
 
 declare double @sqrt(double) readnone nounwind
 %empty = type {}
 declare %empty @has_side_effects()
 
-define double @test_0(i32 %param) {
+define double @test_0(i32 %param) willreturn {
 ; CHECK-LABEL: @test_0(
 ; CHECK-NOT: br
 entry:
 ; No matter how hard you try, sqrt(1.0) is always 1.0.  This allows the
 ; optimizer to delete this loop.
 
   br label %Loop
 Loop:   ; preds = %Loop, %entry

llvm/test/Transforms/SimpleLoopUnswitch/pr37888.ll

 ; RUN: opt -simple-loop-unswitch -loop-deletion -S < %s | FileCheck %s
 ; RUN: opt -simple-loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -loop-deletion -S < %s | FileCheck %s
 ;
 ; Check that when we do unswitching where we re-enqueue the loop to be processed
 ; again, but manage to delete the loop before ever getting to iterate on it, it
 ; doesn't crash the legacy pass manager.
 
 target triple = "x86_64-unknown-linux-gnu"
 
-define void @pr37888() {
+define void @pr37888() willreturn {
 ; CHECK-LABEL: define void @pr37888()
 entry:
   %tobool = icmp ne i16 undef, 0
   br label %for.body
 ; CHECK:         %[[TOBOOL:.*]] = icmp ne
 ; CHECK-NEXT:    br i1 %[[TOBOOL]], label %if.then, label %[[ENTRY_SPLIT:.*]]
 ;
 ; CHECK:       [[ENTRY_SPLIT]]: