> On 2015-Jul-22, at 13:34, Vedant Kumar <v...@apple.com> wrote: (I had this reply already written when you sent it to llvm-commits; I didn't even notice it was the wrong list. I just copy/pasted, so I hope it's the same patch.)
> > Large CFGs cause clang::Sema::checkForFunctionCall() to stack overflow. > > I have a patch which breaks the recursion in checkForFunctionCall() by > manually > managing the call stack. This fixes the problem. The check-clang target > reports > no regressions. > > I don't have commit rights, so I'd appreciate someone taking a look at the > patch and getting it into trunk :). > In future, please attach patches an attachments. As you can see by the strange whitespace on lines without a -/+ in my reply below, some mailers don't handle inline patches very well. > thanks! > vedant > > ================================================================================ > > diff --git a/lib/Sema/AnalysisBasedWarnings.cpp > b/lib/Sema/AnalysisBasedWarnings.cpp > index f2ff48a..dc6dda0 100644 > --- a/lib/Sema/AnalysisBasedWarnings.cpp > +++ b/lib/Sema/AnalysisBasedWarnings.cpp > @@ -52,6 +52,8 @@ > #include <deque> > #include <iterator> > #include <vector> > +#include <functional> > +#include <utility> > > using namespace clang; > > @@ -175,59 +177,69 @@ static void checkForFunctionCall(Sema &S, const > FunctionDecl *FD, > CFGBlock &Block, unsigned ExitID, > llvm::SmallVectorImpl<RecursiveState> > &States, > RecursiveState State) { > - unsigned ID = Block.getBlockID(); > + std::vector<std::pair<std::reference_wrapper<CFGBlock>, RecursiveState>> > + Stack; Probably a `SmallVector<..., 16>` or some such would make sense instead of a `std::vector<...>`. I haven't seen `reference_wrapper<>` at all in LLVM, so I'm not sure all the supported standard libraries have it available. Please use `CFGBlock*` instead. > + Stack.emplace_back(std::make_pair(std::ref(Block), State)); With `emplace_back()`, you can call any constructor: Stack.emplace_back(&Block, State); > > - // A block's state can only move to a higher state. > - if (States[ID] >= State) > - return; > + while (!Stack.empty()) { > + CFGBlock &CurBlock = Stack.back().first.get(); (IIRC, reference_wrapper has an implicit conversion to `&`, so you wouldn't actually need the `.get()` here.) > + RecursiveState CurState = Stack.back().second; > + Stack.pop_back(); > > - States[ID] = State; > + unsigned ID = CurBlock.getBlockID(); > > - // Found a path to the exit node without a recursive call. > - if (ID == ExitID && State == FoundPathWithNoRecursiveCall) > - return; > + // A block's state can only move to a higher state. > + if (States[ID] >= CurState) > + continue; > > - if (State == FoundPathWithNoRecursiveCall) { > - // If the current state is FoundPathWithNoRecursiveCall, the successors > - // will be either FoundPathWithNoRecursiveCall or FoundPath. To > determine > - // which, process all the Stmt's in this block to find any recursive > calls. > - for (const auto &B : Block) { > - if (B.getKind() != CFGElement::Statement) > - continue; > + States[ID] = CurState; > + > + // Found a path to the exit node without a recursive call. > + if (ID == ExitID && CurState == FoundPathWithNoRecursiveCall) > + continue; > + > + if (CurState == FoundPathWithNoRecursiveCall) { This is a fairly large block of code to further indent. Can you move this to a helper function as a separate, preparatory patch with no functionality change (NFC) that returns the new value of `State`? > + // If the current state is FoundPathWithNoRecursiveCall, the successors > + // will be either FoundPathWithNoRecursiveCall or FoundPath. To > determine > + // which, process all the Stmt's in this block to find any recursive > + // calls. > + for (const auto &B : CurBlock) { > + if (B.getKind() != CFGElement::Statement) > + continue; > > - const CallExpr *CE = dyn_cast<CallExpr>(B.getAs<CFGStmt>()->getStmt()); > - if (CE && CE->getCalleeDecl() && > - CE->getCalleeDecl()->getCanonicalDecl() == FD) { > - > - // Skip function calls which are qualified with a templated class. > - if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>( > - CE->getCallee()->IgnoreParenImpCasts())) { > - if (NestedNameSpecifier *NNS = DRE->getQualifier()) { > - if (NNS->getKind() == NestedNameSpecifier::TypeSpec && > - isa<TemplateSpecializationType>(NNS->getAsType())) { > - continue; > + const CallExpr *CE = > dyn_cast<CallExpr>(B.getAs<CFGStmt>()->getStmt()); > + if (CE && CE->getCalleeDecl() && > + CE->getCalleeDecl()->getCanonicalDecl() == FD) { > + > + // Skip function calls which are qualified with a templated class. > + if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>( > + CE->getCallee()->IgnoreParenImpCasts())) { > + if (NestedNameSpecifier *NNS = DRE->getQualifier()) { > + if (NNS->getKind() == NestedNameSpecifier::TypeSpec && > + isa<TemplateSpecializationType>(NNS->getAsType())) { > + continue; > + } > } > } > - } > > - if (const CXXMemberCallExpr *MCE = dyn_cast<CXXMemberCallExpr>(CE)) { > - if (isa<CXXThisExpr>(MCE->getImplicitObjectArgument()) || > - !MCE->getMethodDecl()->isVirtual()) { > - State = FoundPath; > + if (const CXXMemberCallExpr *MCE = > dyn_cast<CXXMemberCallExpr>(CE)) { > + if (isa<CXXThisExpr>(MCE->getImplicitObjectArgument()) || > + !MCE->getMethodDecl()->isVirtual()) { > + CurState = FoundPath; > + break; > + } > + } else { > + CurState = FoundPath; > break; > } > - } else { > - State = FoundPath; > - break; > } > } > } > - } > > - for (CFGBlock::succ_iterator I = Block.succ_begin(), E = Block.succ_end(); > - I != E; ++I) > - if (*I) > - checkForFunctionCall(S, FD, **I, ExitID, States, State); > + for (auto I = CurBlock.succ_rbegin(), E = CurBlock.succ_rend(); I != E; > ++I) > + if (*I) > + Stack.emplace_back(std::make_pair(std::ref(**I), CurState)); I see you've maintained the visitation order by reversing iteration. Makes sense for this commit, but it might be nice to clean this up in a follow-up (assuming visitation order doesn't matter here, which I don't think it does?): for (BasicBlock *BB : CurBlock.successors()) if (BB) Stack.emplace_back(BB, CurState); (You'd have to add the `CFGBlock::successors()` API.) > + } > } > > static void checkRecursiveFunction(Sema &S, const FunctionDecl *FD, > > > > _______________________________________________ > llvm-commits mailing list > llvm-comm...@cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits _______________________________________________ cfe-commits mailing list cfe-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits