diff --git a/llvm/include/llvm/Analysis/MustExecute.h b/llvm/include/llvm/Analysis/MustExecute.h
--- a/llvm/include/llvm/Analysis/MustExecute.h
+++ b/llvm/include/llvm/Analysis/MustExecute.h
@@ -102,7 +102,6 @@
virtual ~LoopSafetyInfo() = default;
};
-
/// Simple and conservative implementation of LoopSafetyInfo that can give
/// false-positive answers to its queries in order to avoid complicated
/// analysis.
@@ -176,6 +175,8 @@
virtual ~ICFLoopSafetyInfo() {};
};
+bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI);
+
struct MustBeExecutedContextExplorer;
/// Enum that allows us to spell out the direction.
diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp
--- a/llvm/lib/Analysis/MustExecute.cpp
+++ b/llvm/lib/Analysis/MustExecute.cpp
@@ -484,12 +484,12 @@
return true;
}
-static bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
+bool llvm::mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) {
if (!LI)
return false;
using RPOTraversal = ReversePostOrderTraversal<const Function *>;
RPOTraversal FuncRPOT(&F);
- return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
+ return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
const LoopInfo>(FuncRPOT, *LI);
}
diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp
--- a/llvm/lib/Transforms/IPO/Attributor.cpp
+++ b/llvm/lib/Transforms/IPO/Attributor.cpp
@@ -28,6 +28,7 @@
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MustExecute.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
@@ -36,9 +37,9 @@
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/NoFolder.h"
#include "llvm/IR/Verifier.h"
#include "llvm/InitializePasses.h"
-#include "llvm/IR/NoFolder.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
@@ -2414,28 +2415,43 @@
/// ------------------------ Will-Return Attributes ----------------------------
-// Helper function that checks whether a function has any cycle.
+// Helper function that checks whether a function has a cycle,then we check
+// further whether the cycle is a bounded loop cycle.
+// Loops with maximum trip count are considered bounded, any other cycle not.
// TODO: Replace with more efficent code
-static bool containsCycle(Function &F) {
- SmallPtrSet<BasicBlock *, 32> Visited;
-
- // Traverse BB by dfs and check whether successor is already visited.
- for (BasicBlock *BB : depth_first(&F)) {
- Visited.insert(BB);
- for (auto *SuccBB : successors(BB)) {
- if (Visited.count(SuccBB))
+static bool mayContainUnboundedCycle(Function &F, Attributor &A) {
+ ScalarEvolution *SE =
+ A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(F);
+ LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(F);
+ // If NoAnalysis is available for the function then we assume any cycle to be
+ // unbounded cycle.
+ // We use scc_iterator which uses Tarjan algorithm to find all the maximal
+ // SCCs. To detect if there's a cycle, you only need to find the maximal ones.
+ if (!SE || !LI) {
+ for (scc_iterator<Function *> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI)
+ if (SCCI.hasCycle())
return true;
- }
+ return false;
+ }
+
+ // Check whether there is Irreducible control then the function contains
+ // non-loop cycles.
+ if (mayContainIrreducibleControl(F,LI))
+ return true;
+
+ // Check whether the loops in the function have maxTripCount and if it has
+ // then it is a bounded loop.
+ for (auto *L : LI->getLoopsInPreorder()) {
+ if (!SE->getSmallConstantMaxTripCount(L))
+ return true;
}
return false;
}
// Helper function that checks the function have a loop which might become an
-// endless loop
-// FIXME: Any cycle is regarded as endless loop for now.
-// We have to allow some patterns.
-static bool containsPossiblyEndlessLoop(Function *F) {
- return !F || !F->hasExactDefinition() || containsCycle(*F);
+// endless loop.
+static bool containsPossiblyEndlessLoop(Function *F, Attributor &A) {
+ return !F || !F->hasExactDefinition() || mayContainUnboundedCycle(*F, A);
}
struct AAWillReturnImpl : public AAWillReturn {
@@ -2446,7 +2462,7 @@
AAWillReturn::initialize(A);
Function *F = getAssociatedFunction();
- if (containsPossiblyEndlessLoop(F))
+ if (containsPossiblyEndlessLoop(F, A))
indicatePessimisticFixpoint();
}
diff --git a/llvm/test/Transforms/Attributor/read_write_returned_arguments_scc.ll b/llvm/test/Transforms/Attributor/read_write_returned_arguments_scc.ll
--- a/llvm/test/Transforms/Attributor/read_write_returned_arguments_scc.ll
+++ b/llvm/test/Transforms/Attributor/read_write_returned_arguments_scc.ll
@@ -101,7 +101,7 @@
ret i32* %retval.0
}
-; CHECK: Function Attrs: argmemonly nofree norecurse nosync nounwind
+; CHECK: Function Attrs: argmemonly nofree norecurse nosync nounwind willreturn
; CHECK-NEXT: define i32* @external_sink_ret2_nrw(i32* nofree readnone %n0, i32* nocapture nofree readonly %r0, i32* nofree returned writeonly "no-capture-maybe-returned" %w0)
define i32* @external_sink_ret2_nrw(i32* %n0, i32* %r0, i32* %w0) {
entry:
@@ -160,6 +160,7 @@
;
; CHECK-NOT: attributes #
; CHECK: attributes #{{.*}} = { argmemonly nofree nosync nounwind }
-; CHECK: attributes #{{.*}} = { argmemonly nofree norecurse nosync nounwind }
+; CHECK: attributes #{{.*}} = { argmemonly nofree norecurse nosync nounwind willreturn }
; CHECK: attributes #{{.*}} = { nosync nounwind }
+; CHECK: attributes #{{.*}} = { norecurse nosync nounwind willreturn }
; CHECK-NOT: attributes #
diff --git a/llvm/test/Transforms/Attributor/willreturn.ll b/llvm/test/Transforms/Attributor/willreturn.ll
--- a/llvm/test/Transforms/Attributor/willreturn.ll
+++ b/llvm/test/Transforms/Attributor/willreturn.ll
@@ -87,9 +87,8 @@
; return ans;
; }
-; FIXME: missing willreturn
-; ATTRIBUTOR_MODULE: Function Attrs: nofree noinline nosync nounwind readnone uwtable
-; ATTRIBUTOR_CGSCC: Function Attrs: nofree noinline norecurse nosync nounwind readnone uwtable
+; ATTRIBUTOR_MODULE: Function Attrs: nofree noinline nosync nounwind readnone uwtable willreturn
+; ATTRIBUTOR_CGSCC: Function Attrs: nofree noinline norecurse nosync nounwind readnone uwtable willreturn
; ATTRIBUTOR-NEXT: define i32 @fact_loop(i32 %0) local_unnamed_addr
define i32 @fact_loop(i32 %0) local_unnamed_addr #0 {
%2 = icmp slt i32 %0, 1
@@ -296,7 +295,7 @@
; TEST 11 (positive case)
-; counstant trip count
+; constant trip count
; int loop_constant_trip_count(int*p){
; int ans = 0;
; for(int i = 0;i<10;i++){
@@ -305,9 +304,8 @@
; return ans;
; }
-; FIXME: missing willreturn
-; ATTRIBUTOR_MODULE: Function Attrs: argmemonly nofree noinline nosync nounwind readonly uwtable
-; ATTRIBUTOR_CGSCC: Function Attrs: argmemonly nofree noinline norecurse nosync nounwind readonly uwtable
+; ATTRIBUTOR_MODULE: Function Attrs: argmemonly nofree noinline nosync nounwind readonly uwtable willreturn
+; ATTRIBUTOR_CGSCC: Function Attrs: argmemonly nofree noinline norecurse nosync nounwind readonly uwtable willreturn
; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture nofree readonly %0)
define i32 @loop_constant_trip_count(i32* nocapture readonly %0) #0 {
br label %3
@@ -374,9 +372,8 @@
; }
-; FIXME: missing willreturn
-; ATTRIBUTOR_MODULE: Function Attrs: argmemonly nofree noinline nosync nounwind readonly uwtable
-; ATTRIBUTOR_CGSCC: Function Attrs: argmemonly nofree noinline norecurse nosync nounwind readonly uwtable
+; ATTRIBUTOR_MODULE: Function Attrs: argmemonly nofree noinline nosync nounwind readonly uwtable willreturn
+; ATTRIBUTOR_CGSCC: Function Attrs: argmemonly nofree noinline norecurse nosync nounwind readonly uwtable willreturn
; ATTRIBUTOR-NEXT: define i32 @loop_trip_dec(i32 %0, i32* nocapture nofree readonly %1) local_unnamed_addr
define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr #0 {
@@ -434,9 +431,8 @@
unreachable
}
-; FIXME: missing willreturn
-; ATTRIBUTOR_MODULE: Function Attrs: nofree noinline nosync nounwind readnone uwtable
-; ATTRIBUTOR_CGSCC: Function Attrs: nofree noinline norecurse nosync nounwind readnone uwtable
+; ATTRIBUTOR_MODULE: Function Attrs: nofree noinline nosync nounwind readnone uwtable willreturn
+; ATTRIBUTOR_CGSCC: Function Attrs: nofree noinline norecurse nosync nounwind readnone uwtable willreturn
; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32 %0)
define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #0 {
%2 = icmp slt i32 %0, 1
@@ -504,5 +500,273 @@
}
+; TEST 16 (negative case)
+; int infinite_loop_inside_bounded_loop(int n) {
+; int ans = 0;
+; for (int i = 0; i < n; i++) {
+; while (1)
+; ans++;
+; }
+; return ans;
+; }
+
+; ATTRIBUTOR_MODULE: Function Attrs: nofree nosync nounwind readnone
+; ATTRIBUTOR_CGSCC: Function Attrs: nofree norecurse nosync nounwind readnone
+; ATTRIBUTOR-NOT: willreturn
+; ATTRIBUTOR-NEXT: define i32 @infinite_loop_inside_bounded_loop(i32 %n)
+define i32 @infinite_loop_inside_bounded_loop(i32 %n) {
+entry:
+ br label %for.cond
+
+for.cond: ; preds = %for.inc, %entry
+ %cmp = icmp sgt i32 %n, 0
+ br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup: ; preds = %for.cond
+ br label %for.end
+
+for.body: ; preds = %for.cond
+ br label %while.cond
+
+while.cond: ; preds = %while.body, %for.body
+ br label %while.body
+
+while.body: ; preds = %while.cond
+ br label %while.cond
+
+for.inc: ; No predecessors!
+ br label %for.cond
+
+for.end: ; preds = %for.cond.cleanup
+ ret i32 0
+}
+
+
+; TEST 17 (positive case)
+; Nested loops with constant max trip count
+; int bounded_nested_loops(int n) {
+; int ans = 0;
+; for (int i = 0; i < n; i++) {
+; while (n--) {
+; ans++;
+; }
+; }
+; return ans;
+; }
+
+; ATTRIBUTOR_MODULE: Function Attrs: nofree nosync nounwind readnone willreturn
+; ATTRIBUTOR_CGSCC: Function Attrs: nofree norecurse nosync nounwind readnone willreturn
+; ATTRIBUTOR-NEXT: define i32 @bounded_nested_loops(i32 %n)
+define i32 @bounded_nested_loops(i32 %n) {
+entry:
+ br label %for.cond
+
+for.cond: ; preds = %for.inc, %entry
+ %i.0 = phi i32 [ 0, %entry ], [ %inc1, %for.inc ]
+ %ans.0 = phi i32 [ 0, %entry ], [ %tmp, %for.inc ]
+ %n.addr.0 = phi i32 [ %n, %entry ], [ -1, %for.inc ]
+ %cmp = icmp slt i32 %i.0, %n.addr.0
+ br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup: ; preds = %for.cond
+ %ans.0.lcssa = phi i32 [ %ans.0, %for.cond ]
+ br label %for.end
+
+for.body: ; preds = %for.cond
+ br label %while.cond
+
+while.cond: ; preds = %while.body, %for.body
+ br i1 true, label %while.end, label %while.body
+
+while.body: ; preds = %while.cond
+ br label %while.cond
+
+while.end: ; preds = %while.cond
+ %tmp = add i32 %n.addr.0, %ans.0
+ br label %for.inc
+
+for.inc: ; preds = %while.end
+ %inc1 = add nuw nsw i32 %i.0, 1
+ br label %for.cond
+
+for.end: ; preds = %for.cond.cleanup
+ ret i32 %ans.0.lcssa
+}
+
+
+; TEST 18 (negative case)
+; int bounded_loop_inside_unbounded_loop(int n) {
+; int ans = 0;
+; while (n++) {
+; for (int i = 0; i < n; i++) {
+; ans++;
+; }
+; }
+; return ans;
+; }
+
+; ATTRIBUTOR_MODULE: Function Attrs: nofree nosync nounwind readnone
+; ATTRIBUTOR_CGSCC: Function Attrs: nofree norecurse nosync nounwind readnone
+; ATTRIBUTOR-NOT: willreturn
+; ATTRIBUTOR-NEXT: define i32 @bounded_loop_inside_unbounded_loop(i32 %n)
+define i32 @bounded_loop_inside_unbounded_loop(i32 %n) {
+entry:
+ br label %while.cond
+
+while.cond: ; preds = %for.end, %entry
+ %ans.0 = phi i32 [ 0, %entry ], [ %tmp2, %for.end ]
+ %n.addr.0 = phi i32 [ %n, %entry ], [ %inc, %for.end ]
+ %tmp = icmp sgt i32 %n.addr.0, -1
+ %smax = select i1 %tmp, i32 %n.addr.0, i32 -1
+ %inc = add nsw i32 %n.addr.0, 1
+ %tobool = icmp eq i32 %n.addr.0, 0
+ br i1 %tobool, label %while.end, label %while.body
+
+while.body: ; preds = %while.cond
+ %tmp1 = add i32 %ans.0, 1
+ br label %for.cond
+
+for.cond: ; preds = %for.inc, %while.body
+ br i1 true, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup: ; preds = %for.cond
+ %tmp2 = add i32 %tmp1, %smax
+ br label %for.end
+
+for.body: ; preds = %for.cond
+ br label %for.inc
+
+for.inc: ; preds = %for.body
+ br label %for.cond
+
+for.end: ; preds = %for.cond.cleanup
+ br label %while.cond
+
+while.end: ; preds = %while.cond
+ %ans.0.lcssa = phi i32 [ %ans.0, %while.cond ]
+ ret i32 %ans.0.lcssa
+}
+
+
+; TEST 19 (negative case)
+; int nested_unbounded_loops(int n) {
+; int ans = 0;
+; while (n--) {
+; while (n--) {
+; ans++;
+; }
+; while (n--) {
+; ans++;
+; }
+; }
+; return ans;
+; }
+
+; ATTRIBUTOR_MODULE: Function Attrs: nofree nosync nounwind readnone
+; ATTRIBUTOR_CGSCC: Function Attrs: nofree norecurse nosync nounwind readnone
+; ATTRIBUTOR-NOT: willreturn
+; ATTRIBUTOR-NEXT: define i32 @nested_unbounded_loops(i32 %n)
+define i32 @nested_unbounded_loops(i32 %n) {
+entry:
+ br label %while.cond
+
+while.cond: ; preds = %while.end10, %entry
+ %ans.0 = phi i32 [ 0, %entry ], [ %tmp1, %while.end10 ]
+ %n.addr.0 = phi i32 [ %n, %entry ], [ -1, %while.end10 ]
+ %tobool = icmp eq i32 %n.addr.0, 0
+ br i1 %tobool, label %while.end11, label %while.body
+
+while.body: ; preds = %while.cond
+ br label %while.cond1
+
+while.cond1: ; preds = %while.body4, %while.body
+ br i1 true, label %while.end, label %while.body4
+
+while.body4: ; preds = %while.cond1
+ br label %while.cond1
+
+while.end: ; preds = %while.cond1
+ %tmp = add i32 %n.addr.0, -2
+ br label %while.cond5
+
+while.cond5: ; preds = %while.body8, %while.end
+ br i1 true, label %while.end10, label %while.body8
+
+while.body8: ; preds = %while.cond5
+ br label %while.cond5
+
+while.end10: ; preds = %while.cond5
+ %tmp1 = add i32 %tmp, %ans.0
+ br label %while.cond
+
+while.end11: ; preds = %while.cond
+ %ans.0.lcssa = phi i32 [ %ans.0, %while.cond ]
+ ret i32 %ans.0.lcssa
+}
+
+
+; TEST 20 (negative case)
+; void non_loop_cycle(int n) {
+; if (fact_loop(n)>5)
+; goto entry1;
+; else
+; goto entry2;
+;
+; entry1:
+; if (fact_loop(n)>5)
+; goto exit;
+; else
+; goto entry2;
+; entry2:
+; if (fact_loop(n)>5)
+; goto exit;
+; else
+; goto entry1;
+; exit:
+; return;
+; }
+
+; ATTRIBUTOR_MODULE: Function Attrs: nofree nosync nounwind readnone
+; ATTRIBUTOR_CGSCC: Function Attrs: nofree norecurse nosync nounwind readnone
+; ATTRIBUTOR-NOT: willreturn
+; ATTRIBUTOR-NEXT: define void @non_loop_cycle(i32 %n)
+define void @non_loop_cycle(i32 %n) {
+entry:
+ %call = call i32 @fact_loop(i32 %n)
+ %cmp = icmp sgt i32 %call, 5
+ br i1 %cmp, label %if.then, label %if.else
+
+if.then: ; preds = %entry
+ br label %entry1
+
+if.else: ; preds = %entry
+ br label %entry2
+
+entry1: ; preds = %if.else8, %if.then
+ %call1 = call i32 @fact_loop(i32 %n)
+ %cmp2 = icmp sgt i32 %call1, 5
+ br i1 %cmp2, label %if.then3, label %if.else4
+
+if.then3: ; preds = %entry1
+ br label %exit
+
+if.else4: ; preds = %entry1
+ br label %entry2
+
+entry2: ; preds = %if.else4, %if.else
+ %call5 = call i32 @fact_loop(i32 %n)
+ %cmp6 = icmp sgt i32 %call5, 5
+ br i1 %cmp6, label %if.then7, label %if.else8
+
+if.then7: ; preds = %entry2
+ br label %exit
+
+if.else8: ; preds = %entry2
+ br label %entry1
+
+exit: ; preds = %if.then7, %if.then3
+ ret void
+}
+
attributes #0 = { nounwind uwtable noinline }
attributes #1 = { uwtable noinline }