lebedev.ri created this revision.
lebedev.ri added reviewers: JonasToth, aaron.ballman, ffrankies,
Eugene.Zelenko, erichkeane, NoQ.
lebedev.ri added a project: LLVM.
Herald added subscribers: xazax.hun, Anastasia, mgorny.
Herald added a project: clang.
Recursion is a powerful tool, but like any tool
without care it can be dangerous. For example,
if the recursion is unbounded, you will
eventually run out of stack and crash.
You can of course track the recursion depth
but if it is hardcoded, there can always be some
other environment when that depth is too large,
so said magic number would need to be env-dependent.
But then your program's behavior is suddenly more env-dependent.
Also, recursion, while it does not outright stop optimization,
recursive calls are less great than normal calls,
for example they hinder inlining.
Recursion is banned in some coding guidelines:
- SEI CERT DCL56-CPP. Avoid cycles during initialization of static objects
- JPL 2.4 Do not use direct or indirect recursion.
- I'd say it is frowned upon in LLVM, although not banned
And is plain unsupported in some cases:
- OpenCL 1.2, 6.9 Restrictions: i. Recursion is not supported.
So there's clearly a lot of reasons why one might want to
avoid recursion, and replace it with worklist handling.
It would be great to have a enforcement for it though.
This implements such a check.
Here we detect both direct and indirect recursive calls.
The algorithm is pretty straight-forward:
1. Build call-graph for the entire TU. For that, the existing
`clang::CallGraph` is re-used, although it had to be modified to also track the
location of the call.
2. Then, the hard problem: how do we detect recursion? Since we have a graph,
let's just do the sane thing, and look for Strongly Connected Function
Declarations - widely known as `SCC`. For that LLVM provides
`llvm::scc_iterator`, which is internally an Tarjan's DFS algorithm, and is
used throught LLVM, so this should be as performant as possible.
3. Now that we've got SCC's, we discard those that don't contain loops. Note
that there may be more than one loop in SCC!
4. For each loopy SCC, we call out each function, and print a single example
call graph that shows recursion -- it didn't seem worthwhile enumerating every
possible loop in SCC, although i suppose it could be implemented.
- To come up with that call graph cycle example, we start at first SCC node,
see which callee of the node is within SCC (and is thus known to be in cycle),
and recurse into it until we hit the callee that is already in call stack.
Repository:
rG LLVM Github Monorepo
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 (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<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
