10#include "clang/AST/ASTContext.h"
11#include "clang/ASTMatchers/ASTMatchFinder.h"
12#include "clang/Analysis/CallGraph.h"
13#include "llvm/ADT/SCCIterator.h"
25template <
typename T,
unsigned SmallSize>
class ImmutableSmallSet {
27 llvm::DenseSet<T> Set;
29 static_assert(SmallSize <= 32,
"N should be small");
31 bool isSmall()
const {
return Set.empty(); }
34 using size_type = size_t;
36 ImmutableSmallSet() =
delete;
37 ImmutableSmallSet(
const ImmutableSmallSet &) =
delete;
38 ImmutableSmallSet(ImmutableSmallSet &&) =
delete;
39 T &operator=(
const ImmutableSmallSet &) =
delete;
40 T &operator=(ImmutableSmallSet &&) =
delete;
43 ImmutableSmallSet(ArrayRef<T> Storage) {
45 if (Storage.size() <= SmallSize) {
52 Set.reserve(Storage.size());
53 Set.insert_range(Storage);
57 size_type count(
const T &V)
const {
60 return llvm::is_contained(Vector, V) ? 1 : 0;
72template <
typename T,
unsigned SmallSize>
class SmartSmallSetVector {
74 using size_type = size_t;
77 SmallVector<T, SmallSize> Vector;
78 llvm::DenseSet<T> Set;
80 static_assert(SmallSize <= 32,
"N should be small");
83 bool isSmall()
const {
return Set.empty(); }
86 bool entiretyOfVectorSmallSizeIsOccupied()
const {
87 assert(isSmall() && Vector.size() <= SmallSize &&
88 "Shouldn't ask if we have already [should have] migrated into Set.");
89 return Vector.size() == SmallSize;
93 assert(Set.empty() &&
"Should not have already utilized the Set.");
96 const size_t NewMaxElts = 4 * Vector.size();
97 Vector.reserve(NewMaxElts);
98 Set.reserve(NewMaxElts);
99 Set.insert_range(Vector);
103 size_type count(
const T &V)
const {
106 return llvm::is_contained(Vector, V) ? 1 : 0;
112 bool setInsert(
const T &V) {
118 if (!entiretyOfVectorSmallSizeIsOccupied())
125 bool SetInsertionSucceeded = Set.insert(V).second;
126 (void)SetInsertionSucceeded;
127 assert(SetInsertionSucceeded &&
"We did check that no such value existed");
134 bool insert(
const T &
X) {
135 bool Result = setInsert(
X);
142 decltype(Vector) takeVector() {
144 return std::move(Vector);
148constexpr unsigned SmallCallStackSize = 16;
149constexpr unsigned SmallSCCSize = 32;
152 llvm::SmallVector<CallGraphNode::CallRecord, SmallCallStackSize>;
157CallStackTy pathfindSomeCycle(ArrayRef<CallGraphNode *> SCC) {
160 const ImmutableSmallSet<CallGraphNode *, SmallSCCSize> SCCElts(SCC);
163 auto NodeIsPartOfSCC = [&SCCElts](CallGraphNode *N) {
164 return SCCElts.count(N) != 0;
168 SmartSmallSetVector<CallGraphNode::CallRecord, SmallCallStackSize>
172 CallGraphNode::CallRecord EntryNode(SCC.front(),
nullptr);
175 CallGraphNode::CallRecord *Node = &EntryNode;
178 if (!CallStackSet.insert(*Node))
182 Node = llvm::find_if(Node->Callee->callees(), NodeIsPartOfSCC);
187 CallStackTy CallStack = CallStackSet.takeVector();
188 CallStack.emplace_back(*Node);
196 Finder->addMatcher(translationUnitDecl().bind(
"TUDecl"),
this);
199void NoRecursionCheck::handleSCC(ArrayRef<CallGraphNode *> SCC) {
200 assert(!SCC.empty() &&
"Empty SCC does not make sense.");
203 for (CallGraphNode *N : SCC) {
204 FunctionDecl *D = N->getDefinition();
205 diag(D->getLocation(),
"function %0 is within a recursive call chain") << D;
212 const CallStackTy EventuallyCyclicCallStack = pathfindSomeCycle(SCC);
213 assert(!EventuallyCyclicCallStack.empty() &&
"We should've found the cycle");
218 const auto CyclicCallStack =
219 ArrayRef<CallGraphNode::CallRecord>(EventuallyCyclicCallStack)
220 .drop_until([LastNode = EventuallyCyclicCallStack.back()](
221 CallGraphNode::CallRecord FrontNode) {
222 return FrontNode == LastNode;
224 assert(CyclicCallStack.size() >= 2 &&
"Cycle requires at least 2 frames");
227 FunctionDecl *CycleEntryFn = CyclicCallStack.front().Callee->getDefinition();
230 diag(CycleEntryFn->getLocation(),
231 "example recursive call chain, starting from function %0",
234 for (
int CurFrame = 1, NumFrames = CyclicCallStack.size();
235 CurFrame != NumFrames; ++CurFrame) {
236 CallGraphNode::CallRecord PrevNode = CyclicCallStack[CurFrame - 1];
237 CallGraphNode::CallRecord CurrNode = CyclicCallStack[CurFrame];
239 Decl *PrevDecl = PrevNode.Callee->getDecl();
240 Decl *CurrDecl = CurrNode.Callee->getDecl();
242 diag(CurrNode.CallExpr->getBeginLoc(),
243 "Frame #%0: function %1 calls function %2 here:", DiagnosticIDs::Note)
244 << CurFrame << cast<NamedDecl>(PrevDecl) << cast<NamedDecl>(CurrDecl);
247 diag(CyclicCallStack.back().CallExpr->getBeginLoc(),
248 "... which was the starting point of the recursive call chain; there "
249 "may be other cycles",
250 DiagnosticIDs::Note);
255 const auto *TU = Result.Nodes.getNodeAs<TranslationUnitDecl>(
"TUDecl");
257 CG.addToCallGraph(
const_cast<TranslationUnitDecl *
>(TU));
261 for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
262 SCCE = llvm::scc_end(&CG);
263 SCCI != SCCE; ++SCCI) {
264 if (!SCCI.hasCycle())
void registerMatchers(ast_matchers::MatchFinder *Finder) override
void check(const ast_matchers::MatchFinder::MatchResult &Result) override
static ClangTidyModuleRegistry::Add< altera::AlteraModule > X("altera-module", "Adds Altera FPGA OpenCL lint checks.")