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 @@ -16,10 +16,12 @@ #include "llvm/Transforms/IPO/Attributor.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/CaptureTracking.h" @@ -36,9 +38,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" @@ -2366,28 +2368,44 @@ /// ------------------------ 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 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(F); + LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction(F); + // If NoAnalysis is available for the function then we assume any cycle to be + // unbounded cycle. + if (!SE || !LI) { + for (scc_iterator 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. + using RPOTraversal = ReversePostOrderTraversal; + RPOTraversal FuncRPOT(&F); + if (containsIrreducibleCFG(FuncRPOT, *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 { @@ -2398,7 +2416,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,272 @@ } +; 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 @non_loop_inside_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) +; int loop_inside_loop(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 @loop_inside_loop(i32 %n) +define i32 @loop_inside_loop(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 @loop_inside_non_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 @non_loops_SCCs(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 }