[-Wunsafe-buffer-usage] Move the whole analysis to the end of a translation unit

[ziqingluo-90]

Summary

Our analysis requires a complete view of the translation unit to be conservative. As mentioned in this patch, we need to know if there is any function overload of a function f declared after f. In addition, we later may want to make global variables safe too. In such a case, we need to know if a global variable is used somewhere in the translation unit. Moreover, the analysis now can ignore ill-formed code detected at the end of a TU.

A summary of the change:
Add a new IssueWarnings function in AnalysisBasedWarnings.cpp for TU-based analyses. So far [-Wunsafe-buffer-usage] is the only analysis using it but there could be more. Sema will call the new IssueWarnings function at the end of parsing a TU.

This patch is still work in progress as the existence of the following concerns:

1. [No] Can we move everything in AnalysisBasedWarnings.cpp to Sema? So far AnalysisBasedWarnings is used to bridge Sema and UnsafeBufferAnalysis so that the changes are minimal.
2. [Done] We probably need a more efficient TU traversal implementation.
3. [Solved] Current tests are mostly fine except that some notes with message "in instantiation of ... " are missing. Although these notes are not emitted by our analysis, we better understand why things change.
4. [Done] To test this patch on a branch with all ongoing [-Wunsafe-buffer-usage] patches.
5. Maybe there are better solutions? (Looking for comments!)

[NoQ]

Thank you for a detailed summary, it's very helpful!

Can we move everything in AnalysisBasedWarnings.cpp to Sema? So far AnalysisBasedWarnings is used to bridge Sema and UnsafeBufferAnalysis so that the changes are minimal.

Currently Sema is completely oblivious to what specific analysis-based-warnings get issued per-function, and I see no need to do it differently for per-translation-unit warnings. (See also the inline comment.)

Current tests are mostly fine except that some notes with message "in instantiation of ... " are missing. Although these notes are not emitted by our analysis, we better understand why things change.

This sounds familiar, I think @usama54321 ran into a similar problem from inside clang-tidy: https://discourse.llvm.org/t/clang-tidy-diagnostics-for-template-code/62909

clang/include/clang/Sema/AnalysisBasedWarnings.h

96–102

Let's make the name generic. It doesn't really matter to the caller which specific warnings are emitted here (just like in the original method). We're likely to add more warnings of this kind in the future. What we're really doing in this patch, is create a new home for them to live in, so let's call it what it is!

[ziqingluo-90]

Current tests are mostly fine except that some notes with message "in instantiation of ... " are missing. Although these notes are not emitted by our analysis, we better understand why things change.

This sounds familiar, I think @usama54321 ran into a similar problem from inside clang-tidy: https://discourse.llvm.org/t/clang-tidy-diagnostics-for-template-code/62909

Thank you for the reference. I checked out the code printing instantiation stacks:

void PrintContextStack() {
  if (!CodeSynthesisContexts.empty() &&
      CodeSynthesisContexts.size() != LastEmittedCodeSynthesisContextDepth) {
    PrintInstantiationStack();
    LastEmittedCodeSynthesisContextDepth = CodeSynthesisContexts.size();
  }
...

The CodeSynthesisContexts keeps track of instantiation stack during parsing. It's not a surprise that CodeSynthesisContexts is empty by the end of parsing. That's why no such note gets printed.

[NoQ]

Yeah this information is probably at least partially unavailable in the fully parsed AST. We have all the instantiations with their AST copied from the original template AST, but we no longer remember *why* we copied it (which is what the CodeSynthesisContext stack captures) . And at this point there could actually be more than one reason (whereas the regular compiler warnings showed up the *first* time the instantiation was requested, so at that point there was just one reason *so far*).

I wonder if it's possible to build an "example" reason after the fact. There's probably no readily available solution but it might be possible to build one with relative ease 🤔 I'm not sure we need to do this for this patch.

But as a smaller subtask of this task, it's probably really valuable to at least make sure the current template arguments are explained. Eg., in

template <typename T>
T addFive(T t) {
  return t + 5;
}

void foo() {
  int *x = ...;
  x = addFive(x);
}

it's very important to make sure that the warning about unsafe buffer operation t + 5 carries a hint that T is int *. Without that the warning may be completely incomprehensible.

[ziqingluo-90]

The template specialization information is still available but we may need to print it by ourselves.
I will add a FIXME there and we will deal with it in a follow-up patch.

[ziqingluo-90]

Address comments.

[NoQ]

clang/lib/Analysis/UnsafeBufferUsage.cpp

1478 ↗

(On Diff #508249)

I think this entire matcher business can easily live in AnalysisBasedWarnings::IssueWarnings(TU). Just because we're running at the end of TU, doesn't mean each warning will need to figure out how to traverse it. In our case the warning still acts on function-by-function basis, it just benefits from other functions being already parsed. I suspect that this is going to be the case for almost every other analysis-based warning we ever put there. So I think let's run the matcher once in IssueWarnings(TU) , for all warnings at once, and then invoke void checkUnsafeBufferUsage(const Decl *D, ...) directly from inside it, just like we did before the patch. If we ever run into a warning that really needs a TranslationUnitDecl, we can always invoke it from outside the matcher.

[ziqingluo-90]

Move the traversal framework to AnalysisBasedWarnings so that the UnsafeBufferUsage analyzer (as well as other possible analyzers) is still function based. It is in the same pattern as the original IssueWarnings function.

[NoQ]

clang/lib/Sema/AnalysisBasedWarnings.cpp

2323–2326

RecursiveASTVisitor does this automatically. Just ask it to Visit(TU).

2338

The intended way to make recursive visitors is to have TraverseFunctionDecl, TraverseBlockDecl, etc., which automatically do the isa check and fall through to the superclass if the method isn't defined. Then they can all call a common method to analyze the body.

This doesn't necessarily lead to better code though, just to more traditional code, so up to you^^ in this case it probably doesn't matter. But it's definitely nice to separate the common part (the part that invokes all individual analyses) into its own method. And then you can eg. isolate the special hasBody() check in the TraverseFunctionDecl() method, so that other code paths didn't have an extra runtime check.

2346–2348

I wonder if ObjCMethodDecl has the same problem. They too can have prototypes and definitions separate from each other.

2366–2367

I suspect that you might have reinvented shouldVisitLambdaBody().

[ziqingluo-90]

Addressed the comments:

• 1) about using a more traditional way of AST traversal; and
• 2) about the concern on ObjcMethodDecl traversal.

clang/lib/Sema/AnalysisBasedWarnings.cpp

2338

yeah, I think overriding VisitFunctionDecl and others separately is a better form because I was clearly dealing with FunctionDecl and others case by case there. So put the specific logic for FunctionDecl in VisitFunctionDecl makes it clear.

Thanks for your advice.

2346–2348

It looks like hasBody() works properly for ObjCMethodDecl. I'm adding a test for it.

[ziqingluo-90]

clang/lib/Sema/AnalysisBasedWarnings.cpp

2366–2367

I tried shouldVisitLambdaBody but it didn't work (I didn't look into why though)

[ziqingluo-90]

Visit LambdaExpr properly

[ziqingluo-90]

Clean up the code for early return in case of ignoring unsafe_buffer_usage warnings.

[NoQ]

clang/lib/Sema/AnalysisBasedWarnings.cpp

2341

This code will grow bigger when more warnings are added, and it's quite likely that most warnings would want to duplicate themselves in each of the Visit methods. Maybe let's make a single function from which all per-function warnings are invoked?

Also, hmm, UnsafeBufferUsageReporter can probably be reused between callables.

Actually, here's an even fancier approach: maybe let's move the visitor outside the function so that it didn't get in the way of readability, and run warnings in a lambda so that we didn't need to explicitly capture anything:

class CallableVisitor {
  llvm::function_ref<void(const Decl *)> callback;

public:
  CallableVisitor(llvm::function_ref<void(const Decl *)> callback):
    callback(callback)
  {}

  VisitFunctionDecl(FunctionDecl *Node) {
      if (Node->doesThisDeclarationHaveABody()) {
        callback(Node);
      }
  }

  // More Visit() methods.
};

void clang::sema::AnalysisBasedWarnings::IssueWarnings(const TranslationUnitDecl *TU) {
  // Common whole-TU safety checks go here.
  if (S.hasUncompilableErrorOccurred() || Diags.getIgnoreAllWarnings())
    return;

  // Whole-TU variables for all warnings go here. Then they're implicitly captured,
  // so no need to list them in the constructor anymore.
  UnsafeBufferUsageReporter UnsafeBufferUsageDiags(S);
  const bool UnsafeBufferUsageEmitFixits =
      Diags.getDiagnosticOptions().ShowFixits && S.getLangOpts().CPlusPlus20;
 
  CallableVisitor([&](const Decl *Node) {
    // Per-decl code for all warnings goes here.
    if (!Diags.isIgnored(diag::warn_unsafe_buffer_operation, D->getBeginLoc()) ||
        !Diags.isIgnored(diag::warn_unsafe_buffer_variable, D->getBeginLoc())) {
      checkUnsafeBufferUsage(Node, UnsafeBufferUsageDiags, UnsafeBufferUsageEmitFixits);
    }

  }).TraverseTranslationUnitDecl(TU);
}

I think that's a pretty neat way to organize this. This way it's immediately clear which code is executed how many times.

2370–2372

Ooo interesting, there is indeed a good reason to keep those checks outside; we shouldn't make an entire extra pass when none of the analysis-based warnings are enabled.

I suggest making the comment a bit more generic, so that users felt empowered to add more checks there and reuse the visitor for their warnings.

[ziqingluo-90]

Address comments: refactor the callable-definition visitor to take a lambda Callback, who calls various analyses that need whole-TU information. If one needs to add a new such analysis later, just add a call in the Callback function.

[NoQ]

Ok looks great to me now!

clang/lib/Sema/AnalysisBasedWarnings.cpp

2364

So WDYT about capturing the reporter from outside lambda instead?

[ziqingluo-90]

clang/lib/Sema/AnalysisBasedWarnings.cpp

2364

The Reporter is stateless so we definitely can let analyses of functions share it.

clang/include/clang/Sema/AnalysisBasedWarnings.h

 //=- AnalysisBasedWarnings.h - Sema warnings based on libAnalysis -*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines AnalysisBasedWarnings, a worker object used by Sema
 // that issues warnings based on dataflow-analysis.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_SEMA_ANALYSISBASEDWARNINGS_H
 #define LLVM_CLANG_SEMA_ANALYSISBASEDWARNINGS_H
 
+#include "clang/AST/Decl.h"
 #include "llvm/ADT/DenseMap.h"
 #include <memory>
 
 namespace clang {
 
 class Decl;
 class FunctionDecl;
 class QualType;
private:
   unsigned MaxUninitAnalysisBlockVisitsPerFunction;
 
   /// @}
 
 public:
   AnalysisBasedWarnings(Sema &s);
   ~AnalysisBasedWarnings();
 
   void IssueWarnings(Policy P, FunctionScopeInfo *fscope,
                      const Decl *D, QualType BlockType);
 
+  // Issue warnings that require whole-translation-unit analysis.
+  void IssueWarnings(const TranslationUnitDecl *D);
+
   Policy getDefaultPolicy() { return DefaultPolicy; }
 
   void PrintStats() const;
 };
 
 } // namespace sema
 } // namespace clang
 
 #endif

clang/lib/Sema/AnalysisBasedWarnings.cpp

 //=- AnalysisBasedWarnings.cpp - Sema warnings based on libAnalysis -*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines analysis_warnings::[Policy,Executor].
 // Together they are used by Sema to issue warnings based on inexpensive
 // static analysis algorithms in libAnalysis.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Sema/AnalysisBasedWarnings.h"
+#include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/EvaluatedExprVisitor.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/ExprObjC.h"
 #include "clang/AST/OperationKinds.h"
 #include "clang/AST/ParentMap.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtObjC.h"
 #include "clang/AST/StmtVisitor.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Type.h"
 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
 #include "clang/Analysis/Analyses/CalledOnceCheck.h"
 #include "clang/Analysis/Analyses/Consumed.h"
 #include "clang/Analysis/Analyses/ReachableCode.h"
 #include "clang/Analysis/Analyses/ThreadSafety.h"
 #include "clang/Analysis/Analyses/UninitializedValues.h"
 #include "clang/Analysis/Analyses/UnsafeBufferUsage.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/CFGStmtMap.h"
+#include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Sema/ScopeInfo.h"
 #include "clang/Sema/SemaInternal.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include <algorithm>
 #include <deque>
 #include <iterator>
 #include <optional>

 // We need this here for unique_ptr with forward declared class.
 sema::AnalysisBasedWarnings::~AnalysisBasedWarnings() = default;
 
 static void flushDiagnostics(Sema &S, const sema::FunctionScopeInfo *fscope) {
   for (const auto &D : fscope->PossiblyUnreachableDiags)
     S.Diag(D.Loc, D.PD);
 }
 
+// An AST Visitor that calls a callback function on each callable DEFINITION
+// that is NOT in a dependent context:
+class CallableVisitor : public RecursiveASTVisitor<CallableVisitor> {
+private:
+  llvm::function_ref<void(const Decl *)> Callback;
+
+public:
+  CallableVisitor(llvm::function_ref<void(const Decl *)> Callback)
+      : Callback(Callback) {}
+
+  bool VisitFunctionDecl(FunctionDecl *Node) {
+    if (cast<DeclContext>(Node)->isDependentContext())
+      return true; // Not to analyze dependent decl
+    // `FunctionDecl->hasBody()` returns true if the function has a body
+    // somewhere defined.  But we want to know if this `Node` has a body
+    // child.  So we use `doesThisDeclarationHaveABody`:
+    if (Node->doesThisDeclarationHaveABody())
+      Callback(Node);
+    return true;
+  }
+
+  bool VisitBlockDecl(BlockDecl *Node) {
+    if (cast<DeclContext>(Node)->isDependentContext())
+      return true; // Not to analyze dependent decl
+    Callback(Node);
+    return true;
+  }
+
+  bool VisitObjCMethodDecl(ObjCMethodDecl *Node) {
+    if (cast<DeclContext>(Node)->isDependentContext())
+      return true; // Not to analyze dependent decl
+    if (Node->hasBody())
+      Callback(Node);
+    return true;
+  }
+
+  bool VisitLambdaExpr(LambdaExpr *Node) {
+    return VisitFunctionDecl(Node->getCallOperator());
+  }
+
+  bool shouldVisitTemplateInstantiations() const { return true; }
+  bool shouldVisitImplicitCode() const { return false; }
+};
+
+void clang::sema::AnalysisBasedWarnings::IssueWarnings(
+    const TranslationUnitDecl *TU) {
+  if (!TU)
+    return; // This is unexpected, give up quietly.
+
+  DiagnosticsEngine &Diags = S.getDiagnostics();
+
+  if (S.hasUncompilableErrorOccurred() || Diags.getIgnoreAllWarnings())
+    // exit if having uncompilable errors or ignoring all warnings:
+    return;
+
+  // Whether -Wunsafe-buffer-usage should emit fix-its:
+  const bool UnsafeBufferEmitFixits =
+      Diags.getDiagnosticOptions().ShowFixits && S.getLangOpts().CPlusPlus20;
+  UnsafeBufferUsageReporter R(S);
+
+  // The Callback function that performs analyses:
+  auto CallAnalyzers = [&](const Decl *Node) -> void {
+    // Perform unsafe buffer analysis:
+    if (!Diags.isIgnored(diag::warn_unsafe_buffer_operation,
+                         Node->getBeginLoc()) ||
+        !Diags.isIgnored(diag::warn_unsafe_buffer_variable,
+                         Node->getBeginLoc()))
+      clang::checkUnsafeBufferUsage(Node, R, UnsafeBufferEmitFixits);
+
+    // More analysis ...
+  };
+  // Emit per-function analysis-based warnings that require the whole-TU
+  // reasoning. Check if any of them is enabled at all before scanning the AST:
+  if (!Diags.isIgnored(diag::warn_unsafe_buffer_operation, SourceLocation()) ||
+      !Diags.isIgnored(diag::warn_unsafe_buffer_variable, SourceLocation())) {
+    CallableVisitor(CallAnalyzers)
+        .TraverseTranslationUnitDecl(
+            std::remove_const_t<TranslationUnitDecl *>(TU));
+  }
+}
+
 void clang::sema::AnalysisBasedWarnings::IssueWarnings(
     sema::AnalysisBasedWarnings::Policy P, sema::FunctionScopeInfo *fscope,
     const Decl *D, QualType BlockType) {
 
   // We avoid doing analysis-based warnings when there are errors for
   // two reasons:
   // (1) The CFGs often can't be constructed (if the body is invalid), so
   //     don't bother trying.
void clang::sema::AnalysisBasedWarnings::IssueWarnings(
   }
 
   // Check for throw out of non-throwing function.
   if (!Diags.isIgnored(diag::warn_throw_in_noexcept_func, D->getBeginLoc()))
     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
       if (S.getLangOpts().CPlusPlus && !fscope->isCoroutine() && isNoexcept(FD))
         checkThrowInNonThrowingFunc(S, FD, AC);
 
-  // Emit unsafe buffer usage warnings and fixits.
-  if (!Diags.isIgnored(diag::warn_unsafe_buffer_operation, D->getBeginLoc()) ||
-      !Diags.isIgnored(diag::warn_unsafe_buffer_variable, D->getBeginLoc())) {
-    UnsafeBufferUsageReporter R(S);
-    checkUnsafeBufferUsage(
-        D, R,
-        /*EmitFixits=*/S.getDiagnostics().getDiagnosticOptions().ShowFixits &&
-            S.getLangOpts().CPlusPlus20);
-  }
-
   // If none of the previous checks caused a CFG build, trigger one here
   // for the logical error handler.
   if (LogicalErrorHandler::hasActiveDiagnostics(Diags, D->getBeginLoc())) {
     AC.getCFG();
   }
 
   // Collect statistics about the CFG if it was built.
   if (S.CollectStats && AC.isCFGBuilt()) {

clang/lib/Sema/Sema.cpp

if (!Diags.isIgnored(diag::warn_mismatched_delete_new, SourceLocation())) {
     for (const auto &DeletedFieldInfo : DeleteExprs) {
       for (const auto &DeleteExprLoc : DeletedFieldInfo.second) {
         AnalyzeDeleteExprMismatch(DeletedFieldInfo.first, DeleteExprLoc.first,
                                   DeleteExprLoc.second);
       }
     }
   }
 
+  AnalysisWarnings.IssueWarnings(Context.getTranslationUnitDecl());
+
   // Check we've noticed that we're no longer parsing the initializer for every
   // variable. If we miss cases, then at best we have a performance issue and
   // at worst a rejects-valid bug.
   assert(ParsingInitForAutoVars.empty() &&
          "Didn't unmark var as having its initializer parsed");
 
   if (!PP.isIncrementalProcessingEnabled())
     TUScope = nullptr;

clang/test/SemaCXX/warn-unsafe-buffer-usage.cpp

// expected-warning@-2{{'x' is an unsafe pointer used for buffer access}}
   *q += 1; *q -= 1; // expected-warning2{{unsafe pointer arithmetic}}
   y += 1; y -= 1;   // expected-note2{{used in pointer arithmetic here}}
   x += 1; x -= 1;   // expected-note2{{used in pointer arithmetic here}}
 }
 
 void testTemplate(int * p) {
   int *a[10];
   foo(f(p, &p, a, a)[1]); // expected-warning{{unsafe buffer access}}
-                          // expected-note@-1{{in instantiation of function template specialization 'f<int *, 10>' requested here}}
+                          // FIXME: expected note@-1{{in instantiation of function template specialization 'f<int *, 10>' requested here}}
 
   const int **q = const_cast<const int **>(&p);
 
-  testPointerArithmetic(p, q, p); //expected-note{{in instantiation of}}
+  testPointerArithmetic(p, q, p); //FIXME: expected note{{in instantiation of}}
 }
 
 void testPointerToMember() {
   struct S_t {
     int x;
     int * y;
   } S;
 

 
 template<typename T> void fArr(T t[]) {
   // expected-warning@-1{{'t' is an unsafe pointer used for buffer access}}
   foo(t[1]);    // expected-note{{used in buffer access here}}
   T ar[8];      // expected-warning{{'ar' is an unsafe buffer that does not perform bounds checks}}
   foo(ar[5]);   // expected-note{{used in buffer access here}}
 }
 
-template void fArr<int>(int t[]); // expected-note {{in instantiation of}}
+template void fArr<int>(int t[]); // FIXME: expected note {{in instantiation of}}
 
 int testReturn(int t[]) {
   // expected-warning@-1{{'t' is an unsafe pointer used for buffer access}}
   return t[1]; // expected-note{{used in buffer access here}}
 }
 
 int testArrayAccesses(int n) {
     // auto deduced array type