diff --git a/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp b/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp --- a/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp +++ b/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp @@ -27,7 +27,7 @@ OS << " (" << N << ") "; OS << " calls: "; for (auto CI = N->begin(), CE = N->end(); CI != CE; ++CI) { - (*CI)->print(OS); + CI->Callee->print(OS); OS << " (" << CI << ") "; } OS << '\n'; @@ -48,7 +48,7 @@ // Allocate a new node, mark it as root, and process it's calls. CallGraphNode *CallerNode = getOrInsertNode(const_cast(Caller)); CallGraphNode *CalleeNode = getOrInsertNode(const_cast(Callee)); - CallerNode->addCallee(CalleeNode); + CallerNode->addCallee({CalleeNode, SourceLocation()}); } void HelperDeclRefGraph::dump() const { print(llvm::errs()); } diff --git a/clang-tools-extra/clang-tidy/misc/CMakeLists.txt b/clang-tools-extra/clang-tidy/misc/CMakeLists.txt --- a/clang-tools-extra/clang-tidy/misc/CMakeLists.txt +++ b/clang-tools-extra/clang-tidy/misc/CMakeLists.txt @@ -5,6 +5,7 @@ MiscTidyModule.cpp MisplacedConstCheck.cpp NewDeleteOverloadsCheck.cpp + NoRecursionCheck.cpp NonCopyableObjects.cpp NonPrivateMemberVariablesInClassesCheck.cpp RedundantExpressionCheck.cpp diff --git a/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp b/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp --- a/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp +++ b/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp @@ -12,6 +12,7 @@ #include "DefinitionsInHeadersCheck.h" #include "MisplacedConstCheck.h" #include "NewDeleteOverloadsCheck.h" +#include "NoRecursionCheck.h" #include "NonCopyableObjects.h" #include "NonPrivateMemberVariablesInClassesCheck.h" #include "RedundantExpressionCheck.h" @@ -35,6 +36,7 @@ CheckFactories.registerCheck("misc-misplaced-const"); CheckFactories.registerCheck( "misc-new-delete-overloads"); + CheckFactories.registerCheck("misc-no-recursion"); CheckFactories.registerCheck( "misc-non-copyable-objects"); CheckFactories.registerCheck( diff --git a/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h b/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h @@ -0,0 +1,41 @@ +//===--- NoRecursionCheck.h - clang-tidy ------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_NORECURSIONCHECK_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_NORECURSIONCHECK_H + +#include "../ClangTidyCheck.h" + +namespace clang { + +class CallGraphNode; + +namespace tidy { +namespace misc { + +/// Finds strongly connected functions (by analyzing call graph for SCC's +/// that are loops), diagnoses each function in the cycle, +/// and displays one example of possible call graph loop (recursion). +/// +/// For the user-facing documentation see: +/// http://clang.llvm.org/extra/clang-tidy/checks/misc-no-recursion.html +class NoRecursionCheck : public ClangTidyCheck { + void handleSCC(ArrayRef SCC); + +public: + NoRecursionCheck(StringRef Name, ClangTidyContext *Context) + : ClangTidyCheck(Name, Context) {} + void registerMatchers(ast_matchers::MatchFinder *Finder) override; + void check(const ast_matchers::MatchFinder::MatchResult &Result) override; +}; + +} // namespace misc +} // namespace tidy +} // namespace clang + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_NORECURSIONCHECK_H diff --git a/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp b/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp @@ -0,0 +1,315 @@ +//===--- NoRecursionCheck.cpp - clang-tidy --------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "NoRecursionCheck.h" +#include "clang/AST/ASTContext.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/Analysis/CallGraph.h" +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/SCCIterator.h" + +using namespace clang::ast_matchers; + +namespace clang { +namespace { + +inline bool operator==(const CallGraphNode::CallRecord &LHS, + const CallGraphNode::CallRecord &RHS) { + return LHS.Callee == RHS.Callee; +} + +} // namespace +} // namespace clang + +namespace llvm { + +// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord. +template <> struct DenseMapInfo { + static inline clang::CallGraphNode::CallRecord getEmptyKey() { + return clang::CallGraphNode::CallRecord( + DenseMapInfo::getEmptyKey(), + clang::SourceLocation()); + } + + static inline clang::CallGraphNode::CallRecord getTombstoneKey() { + return clang::CallGraphNode::CallRecord( + DenseMapInfo::getTombstoneKey(), + clang::SourceLocation()); + } + + static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) { + return DenseMapInfo::getHashValue(Val.Callee); + } + + static bool isEqual(const clang::CallGraphNode::CallRecord &LHS, + const clang::CallGraphNode::CallRecord &RHS) { + return LHS == RHS; + } +}; + +} // namespace llvm + +namespace clang { +namespace tidy { +namespace misc { + +namespace { + +// Much like SmallSet, with two differences: +// 1. It can *only* be constructed from an ArrayRef<>. If the element count +// is small, there is no copy and said storage *must* outlive us. +// 2. it is immutable, the way it was constructed it will stay. +template class ImmutableSmartSet { + ArrayRef Vector; + llvm::DenseSet Set; + + static_assert(SmallSize <= 32, "N should be small"); + + bool isSmall() const { return Set.empty(); } + +public: + using size_type = size_t; + + ImmutableSmartSet() = delete; + ImmutableSmartSet(const ImmutableSmartSet &) = delete; + ImmutableSmartSet(ImmutableSmartSet &&) = delete; + T &operator=(const ImmutableSmartSet &) = delete; + T &operator=(ImmutableSmartSet &&) = delete; + + // WARNING: Storage *must* outlive us if we decide that the size is small. + ImmutableSmartSet(ArrayRef Storage) { + // Is size small-enough to just keep using the existing storage? + if (Storage.size() <= SmallSize) { + Vector = Storage; + return; + } + + // We've decided that it isn't performant to keep using vector. + // Let's migrate the data into Set. + Set.reserve(Storage.size()); + Set.insert(Storage.begin(), Storage.end()); + } + + /// count - Return 1 if the element is in the set, 0 otherwise. + size_type count(const T &V) const { + if (isSmall()) { + // Since the collection is small, just do a linear search. + return llvm::find(Vector, V) == Vector.end() ? 0 : 1; + } else { + return Set.count(V); + } + } +}; + +template class SmartSmallSetVector { +public: + using size_type = size_t; + +private: + SmallVector Vector; + llvm::DenseSet Set; + + static_assert(SmallSize <= 32, "N should be small"); + + // Are we still using Vector for uniqness tracking? + bool isSmall() const { return Set.empty(); } + + // Will one more entry cause Vector to switch away from small-size storage? + bool entiretyOfVectorSmallSizeIsOccupied() const { + assert(isSmall() && Vector.size() <= SmallSize && + "Shouldn't ask if we have already [should have] migrated into Set."); + return Vector.size() == SmallSize; + } + + void populateSet() { + assert(Set.empty() && "Should not have already utilized the Set."); + // Magical growth factor prediction - to how many elements do we expect to + // sanely grow after switching away from small-size storage? + const size_t NewMaxElts = 4 * Vector.size(); + Vector.reserve(NewMaxElts); + Set.reserve(NewMaxElts); + Set.insert(Vector.begin(), Vector.end()); + } + + /// count - Return 1 if the element is in the set, 0 otherwise. + size_type count(const T &V) const { + if (isSmall()) { + // Since the collection is small, just do a linear search. + return llvm::find(Vector, V) == Vector.end() ? 0 : 1; + } + // Look-up in the Set. + return Set.count(V); + } + + bool setInsert(const T &V) { + if (count(V) != 0) + return false; // Already exists. + // Does not exist, Can/need to record it. + if (isSmall()) { // Are we still using Vector for uniqness tracking? + // Will one more entry fit within small-sized Vector? + if (!entiretyOfVectorSmallSizeIsOccupied()) + return true; // We'll insert into vector right afterwards anyway. + // Time to switch to Set. + populateSet(); + } + // Set time! + // Note that this must be after `populateSet()` might have been called. + bool SetInsertionSucceeded = Set.insert(V).second; + (void)SetInsertionSucceeded; + assert(SetInsertionSucceeded && "We did check that no such value existed"); + return true; + } + +public: + /// Insert a new element into the SmartSmallSetVector. + /// \returns true if the element was inserted into the SmartSmallSetVector. + bool insert(const T &X) { + bool result = setInsert(X); + if (result) + Vector.push_back(X); + return result; + } + + /// Clear the SmartSmallSetVector and return the underlying vector. + decltype(Vector) takeVector() { + Set.clear(); + return std::move(Vector); + } +}; + +constexpr unsigned SmallCallStackSize = 16; +constexpr unsigned SmallSCCSize = 32; + +using CallStackTy = + llvm::SmallVector; + +// In given SCC, find *some* call stack that will be cyclic. +// This will only find *one* such stack, it might not be the smallest one, +// and there may be other loops. +CallStackTy PathfindSomeCycle(ArrayRef SCC) { + // We'll need to be able to performantly look up whether some CallGraphNode + // is in SCC or not, so cache all the SCC elements in a set. + const ImmutableSmartSet SCCElts(SCC); + + // Is node N part if the current SCC? + auto NodeIsPartOfSCC = [&SCCElts](CallGraphNode *N) { + return SCCElts.count(N) != 0; + }; + + // Track the call stack that will cause a cycle. + SmartSmallSetVector + CallStackSet; + + // Arbitrairly take the first element of SCC as entry point. + CallGraphNode::CallRecord EntryNode(SCC.front(), SourceLocation()); + // Continue recursing into subsequent callees that are part of this SCC, + // and are thus known to be part of the call graph loop, until loop forms. + CallGraphNode::CallRecord *Node = &EntryNode; + while (1) { + // Did we see this node before? + if (!CallStackSet.insert(*Node)) + break; // Cycle completed! Note that didn't insert the node into stack! + // Else, perform depth-first traversal: out of all callees, pick first one + // that is part of this SCC. This is not guaranteed to yield shortest cycle. + Node = llvm::find_if(Node->Callee->callees(), NodeIsPartOfSCC); + } + + // Note that we failed to insert the last node, that completes the cycle. + // But we really want to have it. So insert it manually into stack only. + CallStackTy CallStack = CallStackSet.takeVector(); + CallStack.emplace_back(*Node); + + return CallStack; +} + +} // namespace + +void NoRecursionCheck::registerMatchers(MatchFinder *Finder) { + Finder->addMatcher(translationUnitDecl().bind("TUDecl"), this); +} + +void NoRecursionCheck::handleSCC(ArrayRef SCC) { + assert(!SCC.empty() && "Empty SCC does not make sense."); + + // First of all, call out every stongly connected function. + for (CallGraphNode *N : SCC) { + Decl *D = N->getDecl(); + diag(D->getLocation(), "function '%0' is part of call graph loop") + << cast(D)->getName(); + } + + // Now, SCC only tells us about strongly connected function declarations in + // the call graph. It doesn't *really* tell us about the cycles they form. + // And there may be more than one cycle in SCC. + // So let's form a call stack that eventually exposes *some* cycle. + const CallStackTy EventuallyCyclicCallStack = PathfindSomeCycle(SCC); + assert(!EventuallyCyclicCallStack.empty() && "We should've found the cycle"); + + // While last node of the call stack does cause a loop, due to the way we + // pathfind the cycle, the loop does not nessesairly begin at the first node + // of the call stack, so drop front nodes of the call stack until it does. + const auto CyclicCallStack = + ArrayRef(EventuallyCyclicCallStack) + .drop_until([LastNode = EventuallyCyclicCallStack.back()]( + CallGraphNode::CallRecord FrontNode) { + return FrontNode == LastNode; + }); + assert(CyclicCallStack.size() >= 2 && "Cycle requires at least 2 frames"); + + // Which function we decided to be the entry point that lead to the recursion? + Decl *CycleEntryFn = CyclicCallStack.front().Callee->getDecl(); + // And now, for ease of understanding, let's print the call sequence that + // forms the cycle in question. + diag(CycleEntryFn->getLocation(), + "Example call graph loop, starting from function '%0'", + DiagnosticIDs::Note) + << cast(CycleEntryFn)->getName(); + for (int CurFrame = 1, NumFrames = CyclicCallStack.size(); + CurFrame != NumFrames; ++CurFrame) { + CallGraphNode::CallRecord PrevNode = CyclicCallStack[CurFrame - 1]; + CallGraphNode::CallRecord CurrNode = CyclicCallStack[CurFrame]; + + Decl *PrevDecl = PrevNode.Callee->getDecl(); + Decl *CurrDecl = CurrNode.Callee->getDecl(); + + diag(CurrNode.Loc, "Frame #%0: function '%1' calls function '%2' here:", + DiagnosticIDs::Note) + << CurFrame << cast(PrevDecl)->getName() + << cast(CurrDecl)->getName(); + } + + diag(CyclicCallStack.back().Loc, + "... which was the starting point of this call graph", + DiagnosticIDs::Note); + + diag(CyclicCallStack.back().Loc, + "This report is non-exaustive. There may be other cycles.", + DiagnosticIDs::Note); +} + +void NoRecursionCheck::check(const MatchFinder::MatchResult &Result) { + // Build call graph for the entire translation unit. + const auto *TU = Result.Nodes.getNodeAs("TUDecl"); + CallGraph CG; + CG.addToCallGraph(const_cast(TU)); + // CG.viewGraph(); + + // Look for cycles in call graph, + // by looking for Strongly Connected Comonents (SCC's) + for (llvm::scc_iterator SCCI = llvm::scc_begin(&CG), + SCCE = llvm::scc_end(&CG); + SCCI != SCCE; ++SCCI) { + if (!SCCI.hasLoop()) // We only care about cycles, not standalone nodes. + continue; + handleSCC(*SCCI); + } +} + +} // namespace misc +} // namespace tidy +} // namespace clang diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -143,6 +143,13 @@ Finds historical use of ``unsigned`` to hold vregs and physregs and rewrites them to use ``Register`` +- New :doc:`misc-no-recursion + ` check. + + Finds strongly connected functions (by analyzing call graph for SCC's + that are loops), diagnoses each function in the cycle, + and displays one example of possible call graph loop (recursion). + - New :doc:`objc-missing-hash ` check. diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst b/clang-tools-extra/docs/clang-tidy/checks/list.rst --- a/clang-tools-extra/docs/clang-tidy/checks/list.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst @@ -181,6 +181,7 @@ `misc-definitions-in-headers `_, "Yes" `misc-misplaced-const `_, `misc-new-delete-overloads `_, + `misc-no-recursion `_, `misc-non-copyable-objects `_, `misc-non-private-member-variables-in-classes `_, `misc-redundant-expression `_, "Yes" diff --git a/clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst b/clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst new file mode 100644 --- /dev/null +++ b/clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst @@ -0,0 +1,8 @@ +.. title:: clang-tidy - misc-no-recursion + +misc-no-recursion +================= + +Finds strongly connected functions (by analyzing call graph for SCC's +that are loops), diagnoses each function in the cycle, +and displays one example of possible call graph loop (recursion). diff --git a/clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp b/clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp @@ -0,0 +1,136 @@ +// RUN: %check_clang_tidy %s misc-no-recursion %t + +// We don't have the definition of this function, +// so we can't tell anything about it.. +void external(); + +// This function is obviously not recursive. +void no_recursion() { +} + +// Since we don't know what `external()` does, +// we don't know if this is recursive or not. +void maybe_no_recursion() { + external(); +} + +// Function calls itself - obviously a recursion. +void endless_recursion() { + endless_recursion(); +} + +// CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-5]]:6: note: Example call graph loop, starting from function 'endless_recursion' +// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here: +// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph +// CHECK-NOTES: :[[@LINE-7]]:3: note: This report is non-exaustive. There may be other cycles. + +bool external_oracle(); +bool another_external_oracle(); + +// Function calls itself if some external function said so - recursion. +void maybe_endless_recursion() { + if (external_oracle()) + maybe_endless_recursion(); +} + +// CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-6]]:6: note: Example call graph loop, starting from function 'maybe_endless_recursion' +// CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here: +// CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of this call graph +// CHECK-NOTES: :[[@LINE-7]]:5: note: This report is non-exaustive. There may be other cycles. + +// Obviously-constrained recursion. +void recursive_countdown(unsigned x) { + if (x == 0) + return; + recursive_countdown(x - 1); +} + +// CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-7]]:6: note: Example call graph loop, starting from function 'recursive_countdown' +// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here: +// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph +// CHECK-NOTES: :[[@LINE-7]]:3: note: This report is non-exaustive. There may be other cycles. + +void indirect_recursion(); +void conditionally_executed() { + if (external_oracle()) + indirect_recursion(); +} +void indirect_recursion() { + if (external_oracle()) + conditionally_executed(); +} + +// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-12]]:6: note: Example call graph loop, starting from function 'indirect_recursion' +// CHECK-NOTES: :[[@LINE-6]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here: +// CHECK-NOTES: :[[@LINE-11]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here: +// CHECK-NOTES: :[[@LINE-12]]:5: note: ... which was the starting point of this call graph +// CHECK-NOTES: :[[@LINE-13]]:5: note: This report is non-exaustive. There may be other cycles. + +void taint(); +void maybe_selfrecursion_with_two_backedges() { + if (external_oracle()) + maybe_selfrecursion_with_two_backedges(); + taint(); + if (another_external_oracle()) + maybe_selfrecursion_with_two_backedges(); +} + +// CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-9]]:6: note: Example call graph loop, starting from function 'maybe_selfrecursion_with_two_backedges' +// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'maybe_selfrecursion_with_two_backedges' calls function 'maybe_selfrecursion_with_two_backedges' here: +// CHECK-NOTES: :[[@LINE-9]]:5: note: ... which was the starting point of this call graph +// CHECK-NOTES: :[[@LINE-10]]:5: note: This report is non-exaustive. There may be other cycles. + +void indirect_recursion_with_alternatives(); +void conditionally_executed_choice_0() { + if (external_oracle()) + indirect_recursion_with_alternatives(); +} +void conditionally_executed_choice_1() { + if (external_oracle()) + indirect_recursion_with_alternatives(); +} +void indirect_recursion_with_alternatives() { + if (external_oracle()) + conditionally_executed_choice_0(); + else + conditionally_executed_choice_1(); +} + +// CHECK-NOTES: :[[@LINE-16]]:6: warning: function 'indirect_recursion_with_alternatives' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-16]]:6: warning: function 'conditionally_executed_choice_0' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-18]]:6: note: Example call graph loop, starting from function 'indirect_recursion_with_alternatives' +// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'indirect_recursion_with_alternatives' calls function 'conditionally_executed_choice_0' here: +// CHECK-NOTES: :[[@LINE-17]]:5: note: Frame #2: function 'conditionally_executed_choice_0' calls function 'indirect_recursion_with_alternatives' here: +// CHECK-NOTES: :[[@LINE-18]]:5: note: ... which was the starting point of this call graph +// CHECK-NOTES: :[[@LINE-19]]:5: note: This report is non-exaustive. There may be other cycles. +// CHECK-NOTES: :[[@LINE-18]]:6: warning: function 'conditionally_executed_choice_1' is part of call graph loop [misc-no-recursion] + +static void indirect_recursion_with_depth2(); +static void conditionally_executed_depth1() { + if (external_oracle()) + indirect_recursion_with_depth2(); +} +static void conditionally_executed_depth0() { + if (external_oracle()) + conditionally_executed_depth1(); +} +void indirect_recursion_with_depth2() { + if (external_oracle()) + conditionally_executed_depth0(); +} + +// CHECK-NOTES: :[[@LINE-14]]:13: warning: function 'indirect_recursion_with_depth2' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-14]]:13: warning: function 'conditionally_executed_depth1' is part of call graph loop [misc-no-recursion] +// CHECK-NOTES: :[[@LINE-11]]:13: note: Example call graph loop, starting from function 'conditionally_executed_depth0' +// CHECK-NOTES: :[[@LINE-10]]:5: note: Frame #1: function 'conditionally_executed_depth0' calls function 'conditionally_executed_depth1' here: +// CHECK-NOTES: :[[@LINE-15]]:5: note: Frame #2: function 'conditionally_executed_depth1' calls function 'indirect_recursion_with_depth2' here: +// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #3: function 'indirect_recursion_with_depth2' calls function 'conditionally_executed_depth0' here: +// CHECK-NOTES: :[[@LINE-9]]:5: note: ... which was the starting point of this call graph +// CHECK-NOTES: :[[@LINE-10]]:5: note: This report is non-exaustive. There may be other cycles. +// CHECK-NOTES: :[[@LINE-17]]:13: warning: function 'conditionally_executed_depth0' is part of call graph loop [misc-no-recursion] diff --git a/clang/include/clang/Analysis/CallGraph.h b/clang/include/clang/Analysis/CallGraph.h --- a/clang/include/clang/Analysis/CallGraph.h +++ b/clang/include/clang/Analysis/CallGraph.h @@ -24,6 +24,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" #include namespace clang { @@ -136,14 +137,23 @@ private: /// Add the given declaration to the call graph. void addNodeForDecl(Decl *D, bool IsGlobal); - - /// Allocate a new node in the graph. - CallGraphNode *allocateNewNode(Decl *); }; class CallGraphNode { public: - using CallRecord = CallGraphNode *; + struct CallRecord { + CallGraphNode *Callee; + SourceLocation Loc; + + CallRecord() = default; + + CallRecord(CallGraphNode *Callee_, SourceLocation Loc_) + : Callee(Callee_), Loc(Loc_) {} + + // The call destination is the only important data here, + // allow to transparently unwrap into it. + operator CallGraphNode *() const { return Callee; } + }; private: /// The function/method declaration. @@ -164,12 +174,18 @@ const_iterator begin() const { return CalledFunctions.begin(); } const_iterator end() const { return CalledFunctions.end(); } + /// Iterator access to callees/children of the node. + llvm::iterator_range callees() { + return llvm::make_range(begin(), end()); + } + llvm::iterator_range callees() const { + return llvm::make_range(begin(), end()); + } + bool empty() const { return CalledFunctions.empty(); } unsigned size() const { return CalledFunctions.size(); } - void addCallee(CallGraphNode *N) { - CalledFunctions.push_back(N); - } + void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); } Decl *getDecl() const { return FD; } diff --git a/clang/lib/Analysis/CallGraph.cpp b/clang/lib/Analysis/CallGraph.cpp --- a/clang/lib/Analysis/CallGraph.cpp +++ b/clang/lib/Analysis/CallGraph.cpp @@ -66,16 +66,16 @@ return nullptr; } - void addCalledDecl(Decl *D) { + void addCalledDecl(Decl *D, SourceLocation Loc) { if (G->includeInGraph(D)) { CallGraphNode *CalleeNode = G->getOrInsertNode(D); - CallerNode->addCallee(CalleeNode); + CallerNode->addCallee({CalleeNode, Loc}); } } void VisitCallExpr(CallExpr *CE) { if (Decl *D = getDeclFromCall(CE)) - addCalledDecl(D); + addCalledDecl(D, CE->getBeginLoc()); VisitChildren(CE); } @@ -89,14 +89,14 @@ void VisitCXXNewExpr(CXXNewExpr *E) { if (FunctionDecl *FD = E->getOperatorNew()) - addCalledDecl(FD); + addCalledDecl(FD, E->getBeginLoc()); VisitChildren(E); } void VisitCXXConstructExpr(CXXConstructExpr *E) { CXXConstructorDecl *Ctor = E->getConstructor(); if (FunctionDecl *Def = Ctor->getDefinition()) - addCalledDecl(Def); + addCalledDecl(Def, Ctor->getBeginLoc()); VisitChildren(E); } @@ -122,7 +122,7 @@ else D = IDecl->lookupPrivateClassMethod(Sel); if (D) { - addCalledDecl(D); + addCalledDecl(D, ME->getBeginLoc()); NumObjCCallEdges++; } } @@ -207,7 +207,7 @@ Node = std::make_unique(F); // Make Root node a parent of all functions to make sure all are reachable. if (F) - Root->addCallee(Node.get()); + Root->addCallee({Node.get(), SourceLocation()}); return Node.get(); } @@ -230,8 +230,8 @@ OS << " calls: "; for (CallGraphNode::const_iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI) { - assert(*CI != Root && "No one can call the root node."); - (*CI)->print(OS); + assert(CI->Callee != Root && "No one can call the root node."); + CI->Callee->print(OS); OS << " "; } OS << '\n';