lebedev.ri updated this revision to Diff 236843.
lebedev.ri marked an inline comment as done.
lebedev.ri added a comment.
s/1/true/
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D72362/new/
https://reviews.llvm.org/D72362
Files:
clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
clang-tools-extra/clang-tidy/misc/CMakeLists.txt
clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
clang-tools-extra/docs/ReleaseNotes.rst
clang-tools-extra/docs/clang-tidy/checks/list.rst
clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
clang/include/clang/Analysis/CallGraph.h
clang/lib/Analysis/CallGraph.cpp
Index: clang/lib/Analysis/CallGraph.cpp
===================================================================
--- clang/lib/Analysis/CallGraph.cpp
+++ 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<CallGraphNode>(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';
Index: clang/include/clang/Analysis/CallGraph.h
===================================================================
--- clang/include/clang/Analysis/CallGraph.h
+++ 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 <memory>
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<iterator> callees() {
+ return llvm::make_range(begin(), end());
+ }
+ llvm::iterator_range<const_iterator> 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; }
Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===================================================================
--- /dev/null
+++ 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]
Index: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
===================================================================
--- /dev/null
+++ 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).
Index: clang-tools-extra/docs/clang-tidy/checks/list.rst
===================================================================
--- clang-tools-extra/docs/clang-tidy/checks/list.rst
+++ clang-tools-extra/docs/clang-tidy/checks/list.rst
@@ -181,6 +181,7 @@
`misc-definitions-in-headers <misc-definitions-in-headers.html>`_, "Yes"
`misc-misplaced-const <misc-misplaced-const.html>`_,
`misc-new-delete-overloads <misc-new-delete-overloads.html>`_,
+ `misc-no-recursion <misc-no-recursion>`_,
`misc-non-copyable-objects <misc-non-copyable-objects.html>`_,
`misc-non-private-member-variables-in-classes <misc-non-private-member-variables-in-classes.html>`_,
`misc-redundant-expression <misc-redundant-expression.html>`_, "Yes"
Index: clang-tools-extra/docs/ReleaseNotes.rst
===================================================================
--- clang-tools-extra/docs/ReleaseNotes.rst
+++ 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
+ <clang-tidy/checks/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
<clang-tidy/checks/objc-missing-hash>` check.
Index: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
===================================================================
--- /dev/null
+++ 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<CallGraphNode *> 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
Index: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
===================================================================
--- /dev/null
+++ 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<clang::CallGraphNode::CallRecord> {
+ static inline clang::CallGraphNode::CallRecord getEmptyKey() {
+ return clang::CallGraphNode::CallRecord(
+ DenseMapInfo<clang::CallGraphNode *>::getEmptyKey(),
+ clang::SourceLocation());
+ }
+
+ static inline clang::CallGraphNode::CallRecord getTombstoneKey() {
+ return clang::CallGraphNode::CallRecord(
+ DenseMapInfo<clang::CallGraphNode *>::getTombstoneKey(),
+ clang::SourceLocation());
+ }
+
+ static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) {
+ return DenseMapInfo<clang::CallGraphNode *>::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 <typename T, unsigned SmallSize> class ImmutableSmartSet {
+ ArrayRef<T> Vector;
+ llvm::DenseSet<T> 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<T> 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 <typename T, unsigned SmallSize> class SmartSmallSetVector {
+public:
+ using size_type = size_t;
+
+private:
+ SmallVector<T, SmallSize> Vector;
+ llvm::DenseSet<T> 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<CallGraphNode::CallRecord, SmallCallStackSize>;
+
+// 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<CallGraphNode *> 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<CallGraphNode *, SmallSCCSize> 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<CallGraphNode::CallRecord, SmallCallStackSize>
+ 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 (true) {
+ // 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<CallGraphNode *> 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<NamedDecl>(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<CallGraphNode::CallRecord>(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<NamedDecl>(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<NamedDecl>(PrevDecl)->getName()
+ << cast<NamedDecl>(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<TranslationUnitDecl>("TUDecl");
+ CallGraph CG;
+ CG.addToCallGraph(const_cast<TranslationUnitDecl *>(TU));
+ // CG.viewGraph();
+
+ // Look for cycles in call graph,
+ // by looking for Strongly Connected Comonents (SCC's)
+ for (llvm::scc_iterator<CallGraph *> 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
Index: clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
===================================================================
--- clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
+++ 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<MisplacedConstCheck>("misc-misplaced-const");
CheckFactories.registerCheck<NewDeleteOverloadsCheck>(
"misc-new-delete-overloads");
+ CheckFactories.registerCheck<NoRecursionCheck>("misc-no-recursion");
CheckFactories.registerCheck<NonCopyableObjectsCheck>(
"misc-non-copyable-objects");
CheckFactories.registerCheck<NonPrivateMemberVariablesInClassesCheck>(
Index: clang-tools-extra/clang-tidy/misc/CMakeLists.txt
===================================================================
--- clang-tools-extra/clang-tidy/misc/CMakeLists.txt
+++ 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
Index: clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
===================================================================
--- clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
+++ 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<Decl *>(Caller));
CallGraphNode *CalleeNode = getOrInsertNode(const_cast<Decl *>(Callee));
- CallerNode->addCallee(CalleeNode);
+ CallerNode->addCallee({CalleeNode, SourceLocation()});
}
void HelperDeclRefGraph::dump() const { print(llvm::errs()); }
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
