Author: Atmn Patel
Date: 2021-01-05T09:56:16-05:00
New Revision: f88a7975210fc995197af4b393e3bb5030e97a5c
URL:
https://github.com/llvm/llvm-project/commit/f88a7975210fc995197af4b393e3bb5030e97a5c
DIFF:
https://github.com/llvm/llvm-project/commit/f88a7975210fc995197af4b393e3bb5030e97a5c.diff
LOG: [LoopDeletion] Allows deletion of possibly infinite side-effect free loops
>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.
Reviewed By: jdoerfert
Differential Revision: https://reviews.llvm.org/D86844
Added:
llvm/test/Transforms/LoopDeletion/mustprogress.ll
Modified:
clang/test/Misc/loop-opt-setup.c
llvm/include/llvm/Transforms/Utils/LoopUtils.h
llvm/lib/Transforms/Scalar/LoopDeletion.cpp
llvm/lib/Transforms/Utils/LoopUtils.cpp
llvm/test/Transforms/LoopDeletion/no-exit-blocks.ll
Removed:
diff --git a/clang/test/Misc/loop-opt-setup.c
b/clang/test/Misc/loop-opt-setup.c
index 9cea02a8bcb3..e9a9c1e8ae2d 100644
--- a/clang/test/Misc/loop-opt-setup.c
+++ b/clang/test/Misc/loop-opt-setup.c
@@ -1,5 +1,6 @@
-// This relies on %clang_cc1, %clang does not emit the block names in Release
mode.
+// This tests loop unrolling and loop deletion (enabled under -O1)
// RUN: %clang_cc1 -O1 -fno-unroll-loops -S -o - %s -emit-llvm | FileCheck %s
+// RUN: %clang_cc1 -std=c99 -O1 -fno-unroll-loops -S -o - %s -emit-llvm |
FileCheck %s --check-prefix C99
extern int a[16];
int b = 0;
@@ -25,7 +26,12 @@ void Helper() {
}
// Check br i1 to make sure the loop is gone, there will still be a label
branch for the infinite loop.
+// In C99, there was no forward progress requirement, so we expect the
infinite loop to still exist,
+// but for C11 and onwards, the infinite loop can be deleted.
// CHECK-LABEL: Helper
-// CHECK: br label
-// CHECK-NOT: br i1
-// CHECK: br label
+// C99: br label
+// C99-NOT: br i1
+// C99: br label
+// CHECK: entry:
+// CHECK-NOT: br i1
+// CHECK-NEXT: ret void
diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h
b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
index d606fa954f95..80c6b09d9cf0 100644
--- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
@@ -255,6 +255,9 @@ 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
diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
index 065db647561e..814cfc7ac6a9 100644
--- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
@@ -128,10 +128,11 @@ static bool isLoopNeverExecuted(Loop *L) {
/// 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.
+/// A loop is considered dead either if it does not impact the observable
+/// behavior of the program other than finite running time, or if it is
+/// required to make progress by an attribute such as 'mustprogress' or
+/// 'llvm.loop.mustprogress' and does not make any. This may remove
+/// infinite loops that have been required to make progress.
///
/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
/// order to make various safety checks work.
@@ -207,11 +208,13 @@ static LoopDeletionResult deleteLoopIfDead(Loop *L,
DominatorTree &DT,
: LoopDeletionResult::Unmodifie
