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 @@ -2366,28 +2366,60 @@ /// ------------------------ Will-Return Attributes ---------------------------- -// Helper function that checks whether a function has any cycle. +// Helper function that checks for unbounded cycle which is either a loop +// that does not have a maximal trip count or any other cycle. // 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)) - return true; +static bool containsUnboundedCycle(Function &F, Attributor &A) { + bool NoAnalysis = false; + + ScalarEvolution *SE = + A.getInfoCache().getAnalysisResultForFunction(F); + LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction(F); + + if (!LI || !SE) + NoAnalysis = true; + + for (scc_iterator I = scc_begin(&F), IE = scc_end(&F); I != IE; + ++I) { + const std::vector &SCCBBs = *I; + bool SCCHasLoop = I.hasLoop(); + if (!SCCHasLoop) + continue; + // When NoAnalysis available then check only if the SCC has loop or not. + if (NoAnalysis && SCCHasLoop) { + return true; } + + std::vector::const_iterator BBI = SCCBBs.begin(); + + Loop *L = LI->getLoopFor(*BBI); + // Check whether the current SCC is a loop or not(Loop is Null). + if (!L) + return true; + + // get the outer most loop and compare the number of blocks of the SCC and + // the loop to check if the current SCC is a loop cycle or not if a loop + // then we check whether it is a bounded loop or unbounded loop + do { + if (L->getNumBlocks() > SCCBBs.size()) + return true; + + if (L->getNumBlocks() == SCCBBs.size()) { + if (!SE->getSmallConstantMaxTripCount(L)) + return true; + else + break; + } + + } while ((L = L->getParentLoop())); } 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); +static bool containsPossiblyEndlessLoop(Function *F, Attributor &A) { + return !F || !F->hasExactDefinition() || containsUnboundedCycle(*F, A); } struct AAWillReturnImpl : public AAWillReturn { @@ -2398,7 +2430,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,99 @@ } +; TEST 16 (negative case) +; non loop SCC inside a bounded loop +; int non_loop_inside_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 @non_loop_inside_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 +} + + attributes #0 = { nounwind uwtable noinline } attributes #1 = { uwtable noinline }