[clang-tidy] new opencl recursion not supported check

[ffrankies]

Summary

This lint check is part of the FLOCL (FPGA Linters for OpenCL) project out of the Synergy Lab at Virginia Tech.

FLOCL is a set of lint checks aimed at FPGA developers who code in OpenCL.

The opencl recursion not supported check is placed in a new "opencl" module.

The check finds and flags recursive function calls, which are not supported by the OpenCL standard.

As per the official OpenCL restrictions list.

[Eugene.Zelenko]

I think will be good idea to separate module code in own review or refer to previous one of previous reviews as dependency.

clang-tidy/opencl/RecursionNotSupportedCheck.cpp

28

const auto *

29

const auto *

53

const auto &, because Loc is iterator.

76

{}

78

const auto &, because Caller is iterator.

108

Are two steps and temporary variable are really necessary?

docs/ReleaseNotes.rst

131

Please synchronize with first statement in documentation.

docs/clang-tidy/checks/opencl-recursion-not-supported.rst

38

Please highlight 100 with single back-quotes.

[lebedev.ri]

I was just going to look into this kind of check.
This can be implemented without recursion in the check itself.
Let me write it and post my variant.

[lebedev.ri]

In D72239#1805281, @lebedev.ri wrote:

I was just going to look into this kind of check.
This can be implemented without recursion in the check itself.
Let me write it and post my variant.

D72362

[JonasToth]

The other recursion check seems more sophisticated. What is your take on it? Would you consider it better as well, what is your opinion on it?

[ffrankies]

In D72239#1815583, @JonasToth wrote:

The other recursion check seems more sophisticated. What is your take on it? Would you consider it better as well, what is your opinion on it?

I agree, I would go with the other check if I had to choose between the two. Since @lebedev.ri's version uses an existing CallGraph structure instead of re-creating it (like we did), I'd guess it is more performant than our version. Plus it doesn't have a user-defined recursion depth limit, which is one less thing for the user to worry about.

[lebedev.ri]

D72362 has landed.
I'd advise to see if any of the testcases here aren't being reported by that check, and filing a bugs for them.
Other than that, abandon?

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

clang-tidy/CMakeLists.txt

 add_subdirectory(linuxkernel)
 add_subdirectory(llvm)
 add_subdirectory(misc)
 add_subdirectory(modernize)
 if(CLANG_ENABLE_STATIC_ANALYZER)
   add_subdirectory(mpi)
 endif()
 add_subdirectory(objc)
+add_subdirectory(opencl)
 add_subdirectory(openmp)
 add_subdirectory(performance)
 add_subdirectory(portability)
 add_subdirectory(readability)
 add_subdirectory(zircon)
 set(ALL_CLANG_TIDY_CHECKS
   clangTidyAndroidModule
   clangTidyAbseilModule
   clangTidyBoostModule
   clangTidyBugproneModule
   clangTidyCERTModule
   clangTidyCppCoreGuidelinesModule
   clangTidyDarwinModule
   clangTidyFuchsiaModule
   clangTidyGoogleModule
   clangTidyHICPPModule
   clangTidyLinuxKernelModule
   clangTidyLLVMModule
   clangTidyMiscModule
   clangTidyModernizeModule
   clangTidyObjCModule
+  clangTidyOpenCLModule
   clangTidyOpenMPModule
   clangTidyPerformanceModule
   clangTidyPortabilityModule
   clangTidyReadabilityModule
   clangTidyZirconModule
   )
 if(CLANG_ENABLE_STATIC_ANALYZER)
   list(APPEND ALL_CLANG_TIDY_CHECKS clangTidyMPIModule)
 endif()
 set(ALL_CLANG_TIDY_CHECKS ${ALL_CLANG_TIDY_CHECKS} PARENT_SCOPE)
 
 # Other subtargets. These may reference ALL_CLANG_TIDY_CHECKS
 # and must be below its definition.
 add_subdirectory(plugin)
 add_subdirectory(tool)
 add_subdirectory(utils)

clang-tidy/ClangTidyForceLinker.h

 #if CLANG_ENABLE_STATIC_ANALYZER &&                                            \
     !defined(CLANG_TIDY_DISABLE_STATIC_ANALYZER_CHECKS)
 // This anchor is used to force the linker to link the MPIModule.
 extern volatile int MPIModuleAnchorSource;
 static int LLVM_ATTRIBUTE_UNUSED MPIModuleAnchorDestination =
     MPIModuleAnchorSource;
 #endif
 
+// This anchor is used to force the linker to link the OpenCLModule.
+extern volatile int OpenCLModuleAnchorSource;
+static int LLVM_ATTRIBUTE_UNUSED OpenCLModuleAnchorDestination =
+    OpenCLModuleAnchorSource;
+
 // This anchor is used to force the linker to link the OpenMPModule.
 extern volatile int OpenMPModuleAnchorSource;
 static int LLVM_ATTRIBUTE_UNUSED OpenMPModuleAnchorDestination =
     OpenMPModuleAnchorSource;
 
 // This anchor is used to force the linker to link the PerformanceModule.
 extern volatile int PerformanceModuleAnchorSource;
 static int LLVM_ATTRIBUTE_UNUSED PerformanceModuleAnchorDestination =

clang-tidy/opencl/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS support)
+
+add_clang_library(clangTidyOpenCLModule
+  OpenCLTidyModule.cpp
+  RecursionNotSupportedCheck.cpp
+
+  LINK_LIBS
+  clangAnalysis
+  clangAST
+  clangASTMatchers
+  clangBasic
+  clangLex
+  clangTidy
+  clangTidyUtils
+  )

clang-tidy/opencl/OpenCLTidyModule.cpp

+//===--- OpenCLTidyModule.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 "../ClangTidy.h"
+#include "../ClangTidyModule.h"
+#include "../ClangTidyModuleRegistry.h"
+#include "RecursionNotSupportedCheck.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace opencl {
+
+class OpenCLModule : public ClangTidyModule {
+public:
+  void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
+    CheckFactories.registerCheck<RecursionNotSupportedCheck>(
+        "opencl-recursion-not-supported");
+  }
+};
+
+static ClangTidyModuleRegistry::Add<OpenCLModule>
+    X("opencl-module", "Adds General OpenCL lint checks.");
+
+} // namespace opencl
+
+// This anchor is used to force the linker to link in the generated object file
+// and thus register the MyModule.
+volatile int OpenCLModuleAnchorSource = 0;
+
+} // namespace tidy
+} // namespace clang

clang-tidy/opencl/RecursionNotSupportedCheck.h

+//===--- RecursionNotSupportedCheck.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_OPENCL_RECURSION_NOT_SUPPORTED_CHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_OPENCL_RECURSION_NOT_SUPPORTED_CHECK_H
+
+#include "../ClangTidy.h"
+#include <map>
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace tidy {
+namespace opencl {
+
+/// Flags instances of recurrent function calls as errors.
+///
+/// This lint check makes use of a recurrent function to find instances of
+/// recursive function calls. To reduce the impact of this lint check on the
+/// linting time, an option parameter MaxRecursionDepth is used to set how
+/// deep the recursive function goes to look for recursive function calls.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/opencl-recursion-not-supported.html
+class RecursionNotSupportedCheck : public ClangTidyCheck {
+  const unsigned MaxRecursionDepth;
+
+public:
+  RecursionNotSupportedCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context),
+        MaxRecursionDepth(Options.get("MaxRecursionDepth", 5U)) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  /// Stores the names of all the callers of each function, as well as the
+  /// location at which the function calls are made.
+  std::map<std::string, std::vector<std::pair<SourceLocation, std::string>>>
+      Callers;
+  /// Stores the source location ranges of every function declaration.
+  std::map<std::string, SourceRange> Locations;
+  /// Stores the source location range of the newly matched function
+  /// declaration.
+  void handleFunctionDecl(const FunctionDecl *FunDecl);
+  /// Stores the caller of the newly matched function call, and performs the
+  /// check for whether or not the function call is recursive.
+  void handleFunctionCall(const DeclRefExpr *FunCall, const SourceManager *SM);
+  /// Checks if the current function call is recursive, and returns the
+  /// recursion path as a traceback-like string. If the function call is not
+  /// recursive, returns an empty string.
+  std::string isRecursive(std::string &FunCallName, std::string &CallerName,
+                          unsigned Depth, const SourceManager *SM);
+  /// Builds a single traceback-line line of the recursion path.
+  std::string buildStringPath(std::string &FunCallName, std::string &CallerName,
+                              const SourceManager *SM, SourceLocation Loc);
+  void storeOptions(ClangTidyOptions::OptionMap &Opts);
+};
+
+} // namespace opencl
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_OPENCL_RECURSION_NOT_SUPPORTED_CHECK_H

clang-tidy/opencl/RecursionNotSupportedCheck.cpp

+//===--- RecursionNotSupportedCheck.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 "RecursionNotSupportedCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include <sstream>
+#include <string>
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace opencl {
+
+void RecursionNotSupportedCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(functionDecl().bind("functionDecl"), this);
+  Finder->addMatcher(declRefExpr(to(functionDecl())).bind("functionCall"),
+                     this);
+}
+
+void RecursionNotSupportedCheck::check(const MatchFinder::MatchResult &Result) {
+  auto MatchedFunDecl = Result.Nodes.getNodeAs<FunctionDecl>("functionDecl");
+  auto MatchedFunCall = Result.Nodes.getNodeAs<DeclRefExpr>("functionCall");
+
+  if (MatchedFunDecl) {
+    handleFunctionDecl(MatchedFunDecl);
+  } else {
+    handleFunctionCall(MatchedFunCall, Result.SourceManager);
+  }
+}
+
+void RecursionNotSupportedCheck::handleFunctionDecl(
+    const FunctionDecl *FunDecl) {
+  std::string FunDeclName = FunDecl->getNameInfo().getName().getAsString();
+  Locations[FunDeclName] = FunDecl->getSourceRange();
+}
+
+void RecursionNotSupportedCheck::handleFunctionCall(const DeclRefExpr *FunCall,
+                                                    const SourceManager *SM) {
+  std::string FunCallName = FunCall->getNameInfo().getName().getAsString();
+  // Update Callees map
+  auto Iter = Callers.find(FunCallName);
+  if (Iter == Callers.end()) { // First instance of a call to this function
+    Callers[FunCallName] =
+        std::vector<std::pair<SourceLocation, std::string>>();
+  }
+  for (std::pair<const std::string, SourceRange> &Loc : Locations) {
+    if (SM->isPointWithin(FunCall->getLocation(), Loc.second.getBegin(),
+                          Loc.second.getEnd())) {
+      Callers[FunCallName].push_back(
+          std::make_pair(FunCall->getBeginLoc(), Loc.first));
+    }
+  }
+  // Check if function call is recursive
+  std::string RecursivePath = isRecursive(FunCallName, FunCallName, 0, SM);
+  if (!RecursivePath.empty()) {
+    diag(FunCall->getBeginLoc(),
+         "The call to function %0 is recursive, which is not supported by "
+         "OpenCL.\n%1",
+         DiagnosticIDs::Error)
+        << FunCallName << RecursivePath;
+  }
+}
+
+std::string RecursionNotSupportedCheck::isRecursive(std::string &FunCallName,
+                                                    std::string &CallerName,
+                                                    unsigned Depth,
+                                                    const SourceManager *SM) {
+  if (Depth == MaxRecursionDepth) {
+    return "";
+  }
+  for (std::pair<SourceLocation, std::string> &Caller : Callers[CallerName]) {
+    if (Caller.second.compare(FunCallName) == 0) {
+      return buildStringPath(CallerName, FunCallName, SM, Caller.first);
+    }
+    std::string StringPath =
+        isRecursive(FunCallName, Caller.second, Depth + 1, SM);
+    if (!StringPath.empty()) {
+      std::ostringstream StringStream;
+      StringStream << buildStringPath(CallerName, Caller.second, SM,
+                                      Caller.first)
+                   << "\n"
+                   << StringPath;
+      return StringStream.str();
+    }
+  }
+  return "";
+}
+
+std::string RecursionNotSupportedCheck::buildStringPath(
+    std::string &FunCallName, std::string &CallerName, const SourceManager *SM,
+    SourceLocation Loc) {
+  std::ostringstream StringStream;
+  StringStream << "\t";
+  std::pair<FileID, unsigned> FileOffset = SM->getDecomposedLoc(Loc);
+  std::string FilePath =
+      SM->getFileEntryForID(FileOffset.first)->tryGetRealPathName();
+  unsigned LineNum = SM->getLineNumber(FileOffset.first, FileOffset.second);
+  unsigned ColNum = SM->getColumnNumber(FileOffset.first, FileOffset.second);
+  StringStream << FunCallName << " is called by " << CallerName << " in "
+               << FilePath << ":" << LineNum << ":" << ColNum;
+  std::string StringPath = StringStream.str();
+  return StringPath;
+}
+
+void RecursionNotSupportedCheck::storeOptions(
+    ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "MaxRecursionDepth", MaxRecursionDepth);
+}
+
+} // namespace opencl
+} // namespace tidy
+} // namespace clang

docs/ReleaseNotes.rst

- New :doc:`llvm-prefer-register-over-unsigned
   them to use ``Register``
 
 - New :doc:`objc-missing-hash
   <clang-tidy/checks/objc-missing-hash>` check.
 
   Finds Objective-C implementations that implement ``-isEqual:`` without also
   appropriately implementing ``-hash``.
 
+- New :doc:`opencl <clang-tidy/modules/opencl>` module.
+
+  Checks related to OpenCL usage and API.
+
+- New :doc:`opencl-recursion-not-supported
+  <clang-tidy/checks/opencl-recursion-not-supported>` check.
+
+  Finds recursive function calls, which are not supported by OpenCL. 
+
 - Improved :doc:`bugprone-posix-return
   <clang-tidy/checks/bugprone-posix-return>` check.
 
   Now also checks if any calls to ``pthread_*`` functions expect negative return
   values.
 
 - The 'objc-avoid-spinlock' check was renamed to :doc:`darwin-avoid-spinlock
   <clang-tidy/checks/darwin-avoid-spinlock>`

docs/clang-tidy/checks/list.rst

.. toctree::
    modernize-use-using
    mpi-buffer-deref
    mpi-type-mismatch
    objc-avoid-nserror-init
    objc-forbidden-subclassing
    objc-missing-hash
    objc-property-declaration
    objc-super-self
+   opencl-recursion-not-supported
    openmp-exception-escape
    openmp-use-default-none
    performance-faster-string-find
    performance-for-range-copy
    performance-implicit-conversion-in-loop
    performance-inefficient-algorithm
    performance-inefficient-string-concatenation
    performance-inefficient-vector-operation

docs/clang-tidy/checks/opencl-recursion-not-supported.rst

+.. title:: clang-tidy - opencl-recursion-not-supported
+
+opencl-recursion-not-supported
+==============================
+
+Finds recursive function calls and flags them as compiler errors, since 
+recursion is not supported in OpenCL.
+
+Based on the official list of `OpenCL Restrictions
+<https://www.khronos.org/registry/OpenCL/sdk/1.0/docs/man/xhtml/restrictions.html>`_.
+Examples:
+
+.. code-block:: c++
+
+  int fibonacci(int num) {
+    if (num < 2) {
+      return 1;
+    }
+    // error: fibonacci calls itself
+    return fibonacci(num-2) + fibonacci(num-1);
+  }
+
+  void recursiveA() {
+    recursiveB();
+  }
+
+  void recursiveB() {
+    // error: recursiveB calls recursiveA, and recursiveA calls recursiveB
+    recursiveA();
+  }
+
+Options
+-------
+
+.. option:: MaxRecursionDepth
+
+   Defines the maximum depth of function calls through which the lint check will
+   attempt to find instances of recursion. Default is 100.

docs/clang-tidy/index.rst

 ``google-``            Checks related to Google coding conventions.
 ``hicpp-``             Checks related to High Integrity C++ Coding Standard.
 ``llvm-``              Checks related to the LLVM coding conventions.
 ``misc-``              Checks that we didn't have a better category for.
 ``modernize-``         Checks that advocate usage of modern (currently "modern"
                        means "C++11") language constructs.
 ``mpi-``               Checks related to MPI (Message Passing Interface).
 ``objc-``              Checks related to Objective-C coding conventions.
+``opencl-``            Checks related to OpenCL usage and API.
 ``openmp-``            Checks related to OpenMP API.
 ``performance-``       Checks that target performance-related issues.
 ``portability-``       Checks that target portability-related issues that don't
                        relate to any particular coding style.
 ``readability-``       Checks that target readability-related issues that don't
                        relate to any particular coding style.
 ``zircon-``            Checks related to Zircon kernel coding conventions.
 ====================== =========================================================

test/clang-tidy/checkers/opencl-recursion-not-supported.cpp

+// RUN: %check_clang_tidy -expect-clang-tidy-error %s opencl-recursion-not-supported %t -- -config="{CheckOptions: [{key: "opencl-recursion-not-supported.MaxRecursionDepth", value: 3}]}" -header-filter=.* "--" --include opencl-c.h -cl-std=CL1.2 -c
+
+// Simple recursive function should trigger an error
+void recfun() {
+  recfun();
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: error: The call to function recfun is recursive, which is not supported by OpenCL.
+  // CHECK-NEXT: recfun is called by recfun in {{.*:\d+:\d+}}
+}
+
+// Declare functions first
+void recfun1();
+void recfun2();
+void recfun3();
+
+void recfundeep1();
+void recfundeep2();
+void recfundeep3();
+void recfundeep4();
+
+// Recursive function with depth 3 should trigger error
+void recfun1() {
+  recfun2();
+}
+
+void recfun2() {
+  recfun3();
+}
+
+void recfun3() {
+  recfun1();
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: error: The call to function recfun1 is recursive, which is not supported by OpenCL.
+  // CHECK-NEXT: recfun1 is called by recfun3 in {{.*:\d+:\d+}}
+  // CHECK-NEXT: recfun3 is called by recfun2 in {{.*:\d+:\d+}}
+  // CHECK-NEXT: recfun2 is called by recfun1 in {{.*:\d+:\d+}}
+}
+
+// Non-recursive function should not trigger an error
+int nonrecursivefun() {
+  return 100; 
+}
+
+// Recursive function with depth greater than 3 should not trigger an error
+void recfundeep1() {
+  recfundeep2();
+}
+
+void recfundeep2() {
+  recfundeep3();
+}
+
+void recfundeep3() {
+  recfundeep4();
+}
+
+void recfundeep4() {
+  recfundeep1();
+}