[analyzer] Add checker to model builtin functions

[xazax.hun]

Summary

Model __builtin_assume. The motivation behind using __builtin_assume from the analyzers point of view is to add assumptions. The conventional way to express invariants is to use asserts (with correct annotations for noreturn functions). However on some platform the users do not want to pay the price of an assert, even in the debug build (especially in a hot code). This way we can express these invariants to the analyzer without runtime overhead. Also it is good to use these constraints even if they are only there to aid the optimizer.

What do you think?

[NoQ]

Hmm, shouldn't this be part of BuiltinFunctionChecker aka core.builtin.BuiltinFunctions? We already have __builtin_assume_aligned here (though it doesn't seem to assume anything because that particular assumption is hard to model).

lib/StaticAnalyzer/Checkers/ModelBuiltinChecker.cpp

49

We could also pretend we modeled the call, so that to avoid invalidation.

[xazax.hun]

• Move this to the right checker.

[xazax.hun]

In D33092#752039, @NoQ wrote:

Hmm, shouldn't this be part of BuiltinFunctionChecker aka core.builtin.BuiltinFunctions? We already have __builtin_assume_aligned here (though it doesn't seem to assume anything because that particular assumption is hard to model).

You are completely right! I do not know how could I miss that. :)

[NoQ]

Great, thanks!

lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp

51 ↗

(On Diff #98609)

That's a good question, because assume(false) seems much more broken than assert(false).

But because we are overaggressive on branching as compared to only relying on presumption of code liveness (eg. splitting void foo(x, y) { if (x) ...; if (y) ...; } into 4 paths is unsafe - all code may be live without all paths being feasible - but we do that anyway, same with loops and eager assumptions and our aliasing approach and the whole inlining thing), i think we'd rather not warn.

I mean, due to the above, it is much more likely that the assumption is valid and the branch on which it fails is infeasible due to some function contract we dont' see, than that the assumption is actually violated. We may do well about null dereferences and such, but generally the static analyzer should try to avoid parts of code that have been carefully thought out :) We may probably want to catch cases when the assumption fails on all paths reaching it, but we shouldn't use symbolic execution for all-paths warnings.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Core in {
 
 def DereferenceChecker : Checker<"NullDereference">,
   HelpText<"Check for dereferences of null pointers">,
   DescFile<"DereferenceChecker.cpp">;
 
+def ModelBuiltinsChecker : Checker<"ModelBuiltins">,
+  HelpText<"Model some compiler builtin functions">,
+  DescFile<"ModelBuiltinChecker.cpp">;
+
 def CallAndMessageChecker : Checker<"CallAndMessage">,
   HelpText<"Check for logical errors for function calls and Objective-C message expressions (e.g., uninitialized arguments, null function pointers)">,
   DescFile<"CallAndMessageChecker.cpp">;
 
 def NonNullParamChecker : Checker<"NonNullParamChecker">,
   HelpText<"Check for null pointers passed as arguments to a function whose arguments are references or marked with the 'nonnull' attribute">,
   DescFile<"NonNullParamChecker.cpp">;
 

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp
   MisusedMovedObjectChecker.cpp
+  ModelBuiltinChecker.cpp
   MPI-Checker/MPIBugReporter.cpp
   MPI-Checker/MPIChecker.cpp
   MPI-Checker/MPIFunctionClassifier.cpp
   NSAutoreleasePoolChecker.cpp
   NSErrorChecker.cpp
   NoReturnFunctionChecker.cpp
   NonNullParamChecker.cpp
   NullabilityChecker.cpp

lib/StaticAnalyzer/Checkers/ModelBuiltinChecker.cpp

+//=== ModelBuiltinChecker.cpp --------- Model builtin functions -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This checker improves modeling of a few builtin compiler functions.
+// It does not generate warnings.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+using namespace clang;
+using namespace clang::ento;
+
+namespace {
+class ModelBuiltinsChecker : public Checker<eval::Call> {
+public:
+  bool evalCall(const CallExpr *CE, CheckerContext &C) const {
+    const FunctionDecl *FD =
+        dyn_cast_or_null<FunctionDecl>(CE->getCalleeDecl());
+    if (!FD)
+      return false;
+    if (!FD->getIdentifier())
+      return false;
+
+    StringRef Name = FD->getName();
+    if (Name.empty() || !C.isCLibraryFunction(FD, Name) ||
+        Name != "__builtin_assume")
+      return false;
+
+    ProgramStateRef State = C.getState();
+    const LocationContext *LC = C.getLocationContext();
+    SVal ArgSVal = State->getSVal(CE->getArg(0), LC);
+    if (ArgSVal.isUndef())
+      return false;
+
+    State = State->assume(ArgSVal.castAs<DefinedOrUnknownSVal>(), true);
+    // FIXME: do we want to warn here?
+    if (!State)
+      return false;
+
+    C.addTransition(State);
+    return true;
+  }
+};
+} // end of anonymous namespace
+
+void ento::registerModelBuiltinsChecker(CheckerManager &mgr) {
+  mgr.registerChecker<ModelBuiltinsChecker>();
+}

test/Analysis/builtin-assume.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+
+void f(int i) {
+  __builtin_assume(i < 10);
+  clang_analyzer_eval(i < 15); // expected-warning {{TRUE}}
+}