Author: codafi Date: Wed Mar 21 20:16:23 2018 New Revision: 328173 URL: http://llvm.org/viewvc/llvm-project?rev=328173&view=rev Log: Improve -Winfinite-recursion
Summary: Rewrites -Winfinite-recursion to remove the state dictionary and explore paths in loops - especially infinite loops. The new check now detects recursion in loop bodies dominated by a recursive call. Reviewers: rsmith, rtrieu Reviewed By: rtrieu Subscribers: lebedev.ri, cfe-commits Differential Revision: https://reviews.llvm.org/D43737 Modified: cfe/trunk/lib/Sema/AnalysisBasedWarnings.cpp cfe/trunk/test/SemaCXX/warn-infinite-recursion.cpp Modified: cfe/trunk/lib/Sema/AnalysisBasedWarnings.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Sema/AnalysisBasedWarnings.cpp?rev=328173&r1=328172&r2=328173&view=diff ============================================================================== --- cfe/trunk/lib/Sema/AnalysisBasedWarnings.cpp (original) +++ cfe/trunk/lib/Sema/AnalysisBasedWarnings.cpp Wed Mar 21 20:16:23 2018 @@ -200,60 +200,41 @@ static bool hasRecursiveCallInPath(const return false; } -// All blocks are in one of three states. States are ordered so that blocks -// can only move to higher states. -enum RecursiveState { - FoundNoPath, - FoundPath, - FoundPathWithNoRecursiveCall -}; - -// Returns true if there exists a path to the exit block and every path -// to the exit block passes through a call to FD. +// Returns true if every path from the entry block passes through a call to FD. static bool checkForRecursiveFunctionCall(const FunctionDecl *FD, CFG *cfg) { + llvm::SmallPtrSet<CFGBlock *, 16> Visited; + llvm::SmallVector<CFGBlock *, 16> WorkList; + // Keep track of whether we found at least one recursive path. + bool foundRecursion = false; const unsigned ExitID = cfg->getExit().getBlockID(); - // Mark all nodes as FoundNoPath, then set the status of the entry block. - SmallVector<RecursiveState, 16> States(cfg->getNumBlockIDs(), FoundNoPath); - States[cfg->getEntry().getBlockID()] = FoundPathWithNoRecursiveCall; - - // Make the processing stack and seed it with the entry block. - SmallVector<CFGBlock *, 16> Stack; - Stack.push_back(&cfg->getEntry()); - - while (!Stack.empty()) { - CFGBlock *CurBlock = Stack.back(); - Stack.pop_back(); - - unsigned ID = CurBlock->getBlockID(); - RecursiveState CurState = States[ID]; - - if (CurState == FoundPathWithNoRecursiveCall) { - // Found a path to the exit node without a recursive call. - if (ExitID == ID) - return false; - - // Only change state if the block has a recursive call. - if (hasRecursiveCallInPath(FD, *CurBlock)) - CurState = FoundPath; - } + // Seed the work list with the entry block. + WorkList.push_back(&cfg->getEntry()); - // Loop over successor blocks and add them to the Stack if their state - // changes. - for (auto I = CurBlock->succ_begin(), E = CurBlock->succ_end(); I != E; ++I) - if (*I) { - unsigned next_ID = (*I)->getBlockID(); - if (States[next_ID] < CurState) { - States[next_ID] = CurState; - Stack.push_back(*I); + while (!WorkList.empty()) { + CFGBlock *Block = WorkList.pop_back_val(); + + for (auto I = Block->succ_begin(), E = Block->succ_end(); I != E; ++I) { + if (CFGBlock *SuccBlock = *I) { + if (!Visited.insert(SuccBlock).second) + continue; + + // Found a path to the exit node without a recursive call. + if (ExitID == SuccBlock->getBlockID()) + return false; + + // If the successor block contains a recursive call, end analysis there. + if (hasRecursiveCallInPath(FD, *SuccBlock)) { + foundRecursion = true; + continue; } + + WorkList.push_back(SuccBlock); } + } } - - // Return true if the exit node is reachable, and only reachable through - // a recursive call. - return States[ExitID] == FoundPath; + return foundRecursion; } static void checkRecursiveFunction(Sema &S, const FunctionDecl *FD, @@ -269,10 +250,6 @@ static void checkRecursiveFunction(Sema CFG *cfg = AC.getCFG(); if (!cfg) return; - // If the exit block is unreachable, skip processing the function. - if (cfg->getExit().pred_empty()) - return; - // Emit diagnostic if a recursive function call is detected for all paths. if (checkForRecursiveFunctionCall(FD, cfg)) S.Diag(Body->getLocStart(), diag::warn_infinite_recursive_function); Modified: cfe/trunk/test/SemaCXX/warn-infinite-recursion.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/SemaCXX/warn-infinite-recursion.cpp?rev=328173&r1=328172&r2=328173&view=diff ============================================================================== --- cfe/trunk/test/SemaCXX/warn-infinite-recursion.cpp (original) +++ cfe/trunk/test/SemaCXX/warn-infinite-recursion.cpp Wed Mar 21 20:16:23 2018 @@ -29,8 +29,7 @@ void f(); void e() { f(); } void f() { e(); } -// Don't warn on infinite loops -void g() { +void g() { // expected-warning{{call itself}} while (true) g(); @@ -54,6 +53,19 @@ int j() { // expected-warning{{call its return 5 + j(); } +void k() { // expected-warning{{call itself}} + while(true) { + k(); + } +} + +// Don't warn on infinite loops +void l() { + while (true) {} + + l(); +} + class S { static void a(); void b(); _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
