[analyzer] ConversionChecker: handle floating point

[donat.nagy]

Summary

Extend the alpha.core.Conversion checker to handle implicit converions
where a too large integer value is converted to a floating point type. Each
floating point type has a range where it can exactly represent all integers; we
emit a warning when the integer value is above this range. Although it is
possible to exactly represent some integers which are outside of this range
(those that are divisible by a large enough power of 2); we still report cast
involving those, because their usage may lead to bugs. (For example, if 1<<24
is stored in a float variable x, then x==x+1 holds.)

[Szelethus]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

176

How about AC.getSizeType(AC.UnsignedLongLongTy))?

test/Analysis/conversion.c

190

Need formatting.

193

This too -- how about running clang-format on this file?

[Szelethus]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

176

I'm actually not too sure about this. @whisperity?

[NoQ]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

176

Yeah, i suspect it's a host machine check (to prevent our own overflow on line 189) rather than a target machine check.

[Szelethus]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

176

Oh right, thanks for clarifying that.
I looked it up, and the number of bits in a char can be acquired from CHAR_BITS, maybe use that instead of hard coding 8? https://en.cppreference.com/w/c/types/limits

[donat.nagy]

Fix formatting in tests; add a comment.

[donat.nagy]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

176

Yes, this is intended to be a host machine check (corresponding to the W >= 64U in the old version). I will add a comment to clarify this.

[donat.nagy]

polite ping

[xazax.hun]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

163

A link to the source of these number would be useful. How are these calculated. Also, as far as I know the current C++ standard does not require anything about how floating points are represented in an implementation. So it would be great to somehow refer to the representation used by clang rather than hardcoding these values. (Note that I am perfectly fine with warning for implementation defined behavior as the original version also warn for such in case of integers.)

171

Comment should be full sentences with a full stop at the end.

172

Do not add redundant braces when we only guard one line. It is perfectly ok when the one statements spans over multiple lines (maybe due to comments).

[donat.nagy]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

163

I took these magic numbers from the IEEE 754 standard; I completely agree that their introduction is far from being elegant.

Unfortunately it seems that referring to the representation used by clang seems to be somewhat difficult, see e.g. this old stackoverflow answer. In the Z3 solver a similar problem was solved by defining a static function (getFloatSemantics()) which uses a switch to translate the bit width of a floating point type into an llvm::fltSemantics value (which contains the precision value as a field).

I could imagine three solutions:

• reimplementing the logic getFloatSemantics,
• moving getFloatSemantics to some utility library and using it from there,
• keeping the current code, with comments describing my assumptions and referencing the IEEE standard.

Which of these is the best?

Note: According to the documentation the floating point types supported by the LLVM IR are just float, double and some high precision extension types (which are handled by the default: branch of my code). Unfortunately, I do not know what happens to the [[ https://clang.llvm.org/docs/LanguageExtensions.html#half-precision-floating-point | _Float16 ]] half-width float type.

[donat.nagy]

Give a reference for the significand size values of the IEEE 754 floating point types; cleanup comments and formatting.

[donat.nagy]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

163

I updated the patch with a comment describing my assumptions, but I will implement a different solution if that would be better.

[NoQ]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

164

Continuing the float semantics discussion on the new revision - Did you consider llvm::APFloat? (http://llvm.org/doxygen/classllvm_1_1APFloat.html) This looks like something that you're trying to re-implement.

[donat.nagy]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

164

This switch statement essentially fulfills two functions: it maps QualTypes to standardized IEEE floating point types and it immediately maps the standardized IEEE types to their precision values.

The difficulty is that I don't think that the first map is available as a public function in the clang libraries. This means that although a switch over the bit width of the floating point type is certainly inelegant, I cannot avoid it.

The second map is available in the APFloat library (via the llvm::fltSemantics constants, which describe the standard IEEE types). However, this map is extremely stable (e.g. I don't think that the binary structure of the IEEE double type will ever change), so I think that re-implementing it is justified by the fact that it yields shorter and cleaner code. However, as I had noted previously, I am open to using the llvm::fltSemantics constants to implement this mapping.

As an additional remark, my current code supports the _Float16 type, which is currently not supported by the APFloat/fltSemantics library. If we decide to use the llvm::fltSemantics constants, then we must either extend the APFloat library or apply some workarounds for this case.

[NoQ]

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

164

The difficulty is that I don't think that the first map is available as a public function in the clang libraries. This means that although a switch over the bit width of the floating point type is certainly inelegant, I cannot avoid it.

fltSemantics are not just enum constants, they contain a lot of fancy data:

static const fltSemantics semIEEEhalf = {15, -14, 11, 16};
static const fltSemantics semIEEEsingle = {127, -126, 24, 32};
static const fltSemantics semIEEEdouble = {1023, -1022, 53, 64};
static const fltSemantics semIEEEquad = {16383, -16382, 113, 128};
static const fltSemantics semX87DoubleExtended = {16383, -16382, 64, 80};

[donat.nagy]

Use APFloat to determine precision of floating point type

Additionally, fix a typo in the tests.

[xazax.hun]

LGTM!
I only wonder if this should be on by default or guarded by a config option. I do not have strong feelings about any of the options though.

[donat.nagy]

I found a solution for determining the precision value of a floating point type. Is this acceptable?

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

164

I knew about the data members of fltSemantics, but I did not see a way to use them elegantly (although fltSemantics has sizeInBits as a member, the possible fltSemantics values are not collected into one data structure, so I could not look up the precision field).

However, as I examined the APFloat.h source again, I found the function llvm::APFloat::getAllOnesValue which allows me to map bit width to semantics. While this is a somewhat indirect solution, it avoids using a switch.

The `missing _Float16' problem mentioned in my previous comments was my mistake, somehow I managed to overlook semIEEEhalf.

[NoQ]

The new addition makes perfect sense, please feel free to commit :) Eventually i guess we'll need to declare where is this checker going and what specific lint rule is this checker designed to check, document this rule, and move it to optin once it has no false positives with respect to that rule and warning messages are improved. I suspect that it would need trackNullOrUndefValue() aka trackExpressionValue() and the currently discussed constraint tracking so that to explain why does the checker thinks that the input value of the cast is constrained to be losing precision on the current path.

I only wonder if this should be on by default or guarded by a config option.

Off-by-default flags mostly make sense when the newly added feature is somehow more opt-in than the rest of the checker, and for now i don't see any indication of that. If it turns out that this part of the checker has its own specific problems, i guess we can put it behind a flag, otherwise kinda why bother?

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

158–162

Hmm, so the remaining problem is how to extract float semantics from a float QualType? Would ASTContext::getFloatTypeSemantics(DestType) make sense?

test/Analysis/conversion.c

193

Tests are often unformatted and we usually don't care. Additionally, they are almost always violating LLVM's camelCase vs. under_score conventions.

[donat.nagy]

Use ASTContext::getFloatTypeSemantics()

[donat.nagy]

Could someone with commit rights commit this patch (if it is acceptable)? I don't have commit rights myself.

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

158–162

Thank you, that is the method I was looking for!

[Szelethus]

test/Analysis/conversion.c

193

Hmm, okay :)

[Szelethus]

In D52730#1289989, @donat.nagy wrote:

Could someone with commit rights commit this patch (if it is acceptable)? I don't have commit rights myself.

I'll do the honors. Thanks!

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

 //=== ConversionChecker.cpp -------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Check that there is no loss of sign/precision in assignments, comparisons
 // and multiplications.
 //
 // ConversionChecker uses path sensitive analysis to determine possible values
 // of expressions. A warning is reported when:
 // * a negative value is implicitly converted to an unsigned value in an
 //   assignment, comparison or multiplication.
-// * assignment / initialization when source value is greater than the max
-//   value of target
+// * assignment / initialization when the source value is greater than the max
+//   value of the target integer type
+// * assignment / initialization when the source integer is above the range
+//   where the target floating point type can represent all integers
 //
 // Many compilers and tools have similar checks that are based on semantic
 // analysis. Those checks are sound but have poor precision. ConversionChecker
 // is an alternative to those checks.
 //
 //===----------------------------------------------------------------------===//
 #include "ClangSACheckers.h"
 #include "clang/AST/ParentMap.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "llvm/ADT/APFloat.h"
+
+#include <climits>
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class ConversionChecker : public Checker<check::PreStmt<ImplicitCastExpr>> {
 public:
   void checkPreStmt(const ImplicitCastExpr *Cast, CheckerContext &C) const;
 
 private:
   mutable std::unique_ptr<BuiltinBug> BT;
 
-  // Is there loss of precision
   bool isLossOfPrecision(const ImplicitCastExpr *Cast, QualType DestType,
                          CheckerContext &C) const;
 
-  // Is there loss of sign
   bool isLossOfSign(const ImplicitCastExpr *Cast, CheckerContext &C) const;
 
   void reportBug(ExplodedNode *N, CheckerContext &C, const char Msg[]) const;
 };
 }
 
 void ConversionChecker::checkPreStmt(const ImplicitCastExpr *Cast,
                                      CheckerContext &C) const {
bool ConversionChecker::isLossOfPrecision(const ImplicitCastExpr *Cast,
                                           QualType DestType,
                                           CheckerContext &C) const {
   // Don't warn about explicit loss of precision.
   if (Cast->isEvaluatable(C.getASTContext()))
     return false;
 
   QualType SubType = Cast->IgnoreParenImpCasts()->getType();
 
-  if (!DestType->isIntegerType() || !SubType->isIntegerType())
+  if (!DestType->isRealType() || !SubType->isIntegerType())
     return false;
 
-  if (C.getASTContext().getIntWidth(DestType) >=
-      C.getASTContext().getIntWidth(SubType))
+  const bool isFloat = DestType->isFloatingType();
+
+  const auto &AC = C.getASTContext();
+
+  // We will find the largest RepresentsUntilExp value such that the DestType
+  // can exactly represent all nonnegative integers below 2^RepresentsUntilExp.
+  unsigned RepresentsUntilExp;
+
+  if (isFloat) {
+    const llvm::fltSemantics &Sema = AC.getFloatTypeSemantics(DestType);
+    RepresentsUntilExp = llvm::APFloat::semanticsPrecision(Sema);
+  } else {
+    RepresentsUntilExp = AC.getIntWidth(DestType);
+    if (RepresentsUntilExp == 1) {
+      // This is just casting a number to bool, probably not a bug.
       return false;
+    }
+    if (DestType->isSignedIntegerType())
+      RepresentsUntilExp--;
+  }
 
-  unsigned W = C.getASTContext().getIntWidth(DestType);
-  if (W == 1 || W >= 64U)
+  if (RepresentsUntilExp >= sizeof(unsigned long long) * CHAR_BIT) {
+    // Avoid overflow in our later calculations.
     return false;
+  }
 
-  unsigned long long MaxVal = 1ULL << W;
+  unsigned CorrectedSrcWidth = AC.getIntWidth(SubType);
+  if (SubType->isSignedIntegerType())
+    CorrectedSrcWidth--;
+
+  if (RepresentsUntilExp >= CorrectedSrcWidth) {
+    // Simple case: the destination can store all values of the source type.
+    return false;
+  }
+
+  unsigned long long MaxVal = 1ULL << RepresentsUntilExp;
+  if (isFloat) {
+    // If this is a floating point type, it can also represent MaxVal exactly.
+    MaxVal++;
+  }
   return C.isGreaterOrEqual(Cast->getSubExpr(), MaxVal);
+  // TODO: maybe also check negative values with too large magnitude.
 }
 
 bool ConversionChecker::isLossOfSign(const ImplicitCastExpr *Cast,
                                      CheckerContext &C) const {
   QualType CastType = Cast->getType();
   QualType SubType = Cast->IgnoreParenImpCasts()->getType();
 
   if (!CastType->isUnsignedIntegerType() || !SubType->isSignedIntegerType())
     return false;
 
   return C.isNegative(Cast->getSubExpr());
 }
 
 void ento::registerConversionChecker(CheckerManager &mgr) {
   mgr.registerChecker<ConversionChecker>();
 }

test/Analysis/conversion.c

 // don't warn for calculations
 // seen some fp. For instance:  c2 = (c2 >= 'A' && c2 <= 'Z') ? c2 - 'A' + 'a' : c2;
 // there is a todo in the checker to handle calculations
 void dontwarn5() {
   signed S = -32;
   U8 = S + 10;
 }
 
+char dontwarn6(long long x) {
+  long long y = 42;
+  y += x;
+  return y == 42;
+}
+
 
 // C library functions, handled via apiModeling.StdCLibraryFunctions
 
 int isascii(int c);
 void libraryFunction1() {
   char kb2[5];
   int X = 1000;
   if (isascii(X)) {
     kb2[0] = X; // no-warning
   }
 }
 
 
 typedef struct FILE {} FILE; int getc(FILE *stream);
 # define EOF (-1)
 char reply_string[8192];
 FILE *cin;
-extern int dostuff (void);
+extern int dostuff(void);
 int libraryFunction2() {
   int c, n;
   int dig;
   char *cp = reply_string;
   int pflag = 0;
   int code;
 
   for (;;) {
     dig = n = code = 0;
     while ((c = getc(cin)) != '\n') {
       if (dig < 4 && dostuff())
         code = code * 10 + (c - '0');
       if (!pflag && code == 227)
         pflag = 1;
       if (n == 0)
         n = c;
       if (c == EOF)
         return(4);
       if (cp < &reply_string[sizeof(reply_string) - 1])
         *cp++ = c; // no-warning
     }
   }
 }
 
+double floating_point(long long a, int b) {
+  if (a > 1LL << 55) {
+    double r = a; // expected-warning {{Loss of precision}}
+    return r;
+  } else if (b > 1 << 25) {
+    float f = b; // expected-warning {{Loss of precision}}
+    return f;
+  }
+  return 137;
+}
+
+double floating_point2() {
+  int a = 1 << 24;
+  long long b = 1LL << 53;
+  float f = a; // no-warning
+  double d = b; // no-warning
+  return d - f;
+}
+
+int floating_point_3(unsigned long long a) {
+  double b = a; // no-warning
+  return 42;
+}