[analyzer] clarify undef shift result when shift count is negative or exceeds the bit width

[danielmarjamaki]

Summary

The error messages are confusing when shift result is undefined because the shift count is negative or exceeds the bit width. I have seen that users often draw the conclusion that Clang thinks some operand is uninitialized and determine that Clang shows a false positive.

I also know that some users use negative shift count by intention and don't think that would cause problems.

This patch clarify the error message and refactors the code a little.

[danielmarjamaki]

Ping

[a.sidorin]

Hello Daniel,
Your patch looks mostly good to me. I have only minor naming comments.

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

99

CompRule?

100

I think we should rename these variables to LHSExpr, RHSVal, LHSVal. I don't like LVal/RVal because they may be associated with rvalue/lvalue types which is not what we want.

[danielmarjamaki]

Fix review comments

[danielmarjamaki]

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

100

I agree. Good point.

[a.sidorin]

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

99

Oops. I meant renaming of the BOK argument, not the method :) Sorry for misleading.

[danielmarjamaki]

Fix review comment. Made isShiftOverflow() static.

[danielmarjamaki]

Ping

[NoQ]

Hello, sorry for your having to wait on me. The implementation looks good, i'm only having a couple of public API concerns.

include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h

51–52

Because you are making these functions public, i think it's worth it to make it obvious what they do without looking at the particular checker code. Comments are definitely worth it. I think function names could be worded better; i suggest exprComparesTo(const Expr *LHSExpr, BinaryOperatorKind ComparisonOp, SVal RHSVal, CheckerContext &C); and isGreaterOrEqual(...); i'm personally fond of having CheckerContext at the back because that's where we have it in checker callbacks, but that's not important.

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

101

I believe it is enough to pass only State to this function. SValBuilder and ConstraintManager objects can be obtained from the state's ProgramStateManager. The good thing about requiring only State is that we'd be able to use these functions in checker callbacks that don't provide the CheckerContext object, eg. checkEndAnalysis or checkRegionChanges.

[zaks.anna]

include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h

51

+ 1 on Artem's comment of making the names more clear and providing documentation. Also, should these be part of CheckerContext?

[danielmarjamaki]

Fix review comments

• renamed
• reorder function arguments (CheckerContext last)

[danielmarjamaki]

include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h

51

Also, should these be part of CheckerContext?

I chose not to. Then as NoQ suggested it's not possible to use this when CheckerContext is not available:

"The good thing about requiring only State is that we'd be able to use these functions in checker callbacks that don't provide the CheckerContext object, eg. checkEndAnalysis or checkRegionChanges."

[danielmarjamaki]

Ping.

[xazax.hun]

I only found two nits otherwise looks good to me.

include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h

46

Right now the name of this function is exprComparesTo, but none of its arguments are expressions. You should either rename it to svalComparesTo, or use expr as its arguments.

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

116

Any reason why do you get the constraint manager and not using ProgramState::assume?

[danielmarjamaki]

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

116

Mostly that it's just 1 call instead of 2. assumeDual() has some extra logic (early return , assertion). are there some special reason to use assume()?

[xazax.hun]

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

116

Basically it would be a bit shorter, it also calls AssumeDual in the background.
See https://clang.llvm.org/doxygen/ProgramState_8h_source.html#l00652

[danielmarjamaki]

minor tweak

[danielmarjamaki]

renamed exprComparesTo to svalComparesTo

[danielmarjamaki]

ping

[NoQ]

I have just one comment and i think it'd be good to land.

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

104

Every SVal is either Unknown or Undefined or NonLoc or Loc, so the check after && is unnecessary.

Also, i believe that it'd be more correct to look at the AST's Expr::isLValue() (in the caller function, where the expression is still available) instead of looking at the SVal type here. These approaches are significantly different: you need to discriminate between pointer-type rvalues and integer-type lvalues, both of which are represented as Loc values; in the former case, we shouldn't blindly get the binding. I've seen these incorrectly discriminated-between in multiple places in the analyzer, and i believe we should fix this eventually.

[zaks.anna]

These are great additions!

Going back to my comment about adding these to CheckerContext, I think we should be adding helper functions as methods on CheckerContext as it is the primary place where checker writers look for helpers. Two of the three methods added take CheckerContext as an argument, so what is the reason for adding them elsewhere?

As for the svalComparesTo method, if we want to make it available to the two callbacks that do not have checker context, we can include a method on checker context that calls into a helper in CheckerHelpers.h. However, given that even this patch is not using the function, I would argue for leaving it as a helper function internal to CheckerContext.cpp.

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

120

"right side of operand" does not sound right..

How about:
"The result of the '<<' expression is undefined due to negative value on the right side of operand"
->
"The result of the left shift is undefined because the right operand is negative"
or
"The result of the '<<' expression is undefined because the right operand is negative"

127

It's best not to use ">=" in diagnostic messages.
Suggestions: "due to shift count >= width of type" ->

• "due to shifting by a value larger than the width of type"
• "due to shifting by 5, which is larger than the width of type 'int'" // Providing the exact value and the type would be very useful and this information is readily available to us. Note that the users might not see the type or the value because of macros and such.

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

98

How about evalComparison as a name for this?

121

Please, use doxygen comment style here and below.

[danielmarjamaki]

Fix review comments

[danielmarjamaki]

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

127

I used "due to shifting by 5, which is larger than the width of type 'int'"

However I did not see an easy way to show the exact value. So I added getConcreteValue(). Maybe you have a better suggestion. If it's a ConcreteInt I show the exact value, but if it's some range etc then I write "due to shifting by a value that is larger..." instead.

The message "due to shifting by 64, which is larger than the width of type 'unsigned long long'" is a bit weird imho. Because 64 is not larger than the width. Not sure how this can be rephrazed better though.

[xazax.hun]

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

127

SValBuilder has a getKnownValue, does that help?

[danielmarjamaki]

Cleaned up the patch a little. Thanks Gabor for telling me about SValBuilder::getKnownValue()

[xazax.hun]

It looks good to me but let's wait for Anna, NoQ, or Devin for the final word.

[danielmarjamaki]

ping

[danielmarjamaki]

ping

[danielmarjamaki]

ping

[danielmarjamaki]

ping

[danielmarjamaki]

ping

[zaks.anna]

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

137

Please print single quotes around the value.

141

"equal with the width" -> "equal to the width"

[zaks.anna]

Sorry for the wait!

[danielmarjamaki]

fixed review comments

[danielmarjamaki]

ping

[paquette]

include/clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h

201 ↗

(On Diff #116865)

Maybe something like

/// Returns true if the value of \p E is greater than or equal to \p Val under unsigned comparison.

203 ↗

(On Diff #116865)

This shouldn't need a \brief, since it's a single line comment.

It could also be something like

/// Returns true if the value of \p E is negative.

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

141

Maybe "greater than or equal to" instead of "larger or equal to" just for convention? I hear/read that more often, so seeing "larger" is a little weird.

Minor point though, so if it makes the message too long it doesn't matter.

[zaks.anna]

Once the comments by @paquette are addressed, LGTM. Thanks!

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

141

I agree that "greater than or equal to" is better, so let's change to that.

include/clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h

 //  This file defines CheckerVisitor.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CHECKERHELPERS_H
 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CHECKERHELPERS_H
 
 #include "clang/AST/Stmt.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include <tuple>
 
 namespace clang {
 
 class Expr;
 class VarDecl;
 
 namespace ento {
if (Child && containsStmt<T>(Child))
       return true;
 
   return false;
 }
 
 std::pair<const clang::VarDecl *, const clang::Expr *>
 parseAssignment(const Stmt *S);
 
+bool exprComparesTo(SVal LHSVal, BinaryOperatorKind ComparisonOp, SVal RHSVal,
+                    ProgramStateRef State);
+bool isGreaterOrEqual(const Expr *E, unsigned long long Val, CheckerContext &C);
+bool isNegative(const Expr *E, CheckerContext &C);
+
 } // end GR namespace
 
 } // end clang namespace
 
 #endif

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

 //
 //===----------------------------------------------------------------------===//
 #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 "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class ConversionChecker : public Checker<check::PreStmt<ImplicitCastExpr>> {
 public:
   void checkPreStmt(const ImplicitCastExpr *Cast, CheckerContext &C) const;
if (!BT)
     BT.reset(
         new BuiltinBug(this, "Conversion", "Possible loss of sign/precision."));
 
   // Generate a report for this bug.
   auto R = llvm::make_unique<BugReport>(*BT, Msg, N);
   C.emitReport(std::move(R));
 }
 
-// Is E value greater or equal than Val?
-static bool isGreaterEqual(CheckerContext &C, const Expr *E,
-                           unsigned long long Val) {
-  ProgramStateRef State = C.getState();
-  SVal EVal = C.getSVal(E);
-  if (EVal.isUnknownOrUndef())
-    return false;
-  if (!EVal.getAs<NonLoc>() && EVal.getAs<Loc>()) {
-    ProgramStateManager &Mgr = C.getStateManager();
-    EVal =
-        Mgr.getStoreManager().getBinding(State->getStore(), EVal.castAs<Loc>());
-  }
-  if (EVal.isUnknownOrUndef() || !EVal.getAs<NonLoc>())
-    return false;
-
-  SValBuilder &Bldr = C.getSValBuilder();
-  DefinedSVal V = Bldr.makeIntVal(Val, C.getASTContext().LongLongTy);
-
-  // Is DefinedEVal greater or equal with V?
-  SVal GE = Bldr.evalBinOp(State, BO_GE, EVal, V, Bldr.getConditionType());
-  if (GE.isUnknownOrUndef())
-    return false;
-  ConstraintManager &CM = C.getConstraintManager();
-  ProgramStateRef StGE, StLT;
-  std::tie(StGE, StLT) = CM.assumeDual(State, GE.castAs<DefinedSVal>());
-  return StGE && !StLT;
-}
-
-// Is E value negative?
-static bool isNegative(CheckerContext &C, const Expr *E) {
-  ProgramStateRef State = C.getState();
-  SVal EVal = State->getSVal(E, C.getLocationContext());
-  if (EVal.isUnknownOrUndef() || !EVal.getAs<NonLoc>())
-    return false;
-  DefinedSVal DefinedEVal = EVal.castAs<DefinedSVal>();
-
-  SValBuilder &Bldr = C.getSValBuilder();
-  DefinedSVal V = Bldr.makeIntVal(0, false);
-
-  SVal LT =
-      Bldr.evalBinOp(State, BO_LT, DefinedEVal, V, Bldr.getConditionType());
-
-  // Is E value greater than MaxVal?
-  ConstraintManager &CM = C.getConstraintManager();
-  ProgramStateRef StNegative, StPositive;
-  std::tie(StNegative, StPositive) =
-      CM.assumeDual(State, LT.castAs<DefinedSVal>());
-
-  return StNegative && !StPositive;
-}
-
 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())
     return false;
 
   if (C.getASTContext().getIntWidth(DestType) >=
       C.getASTContext().getIntWidth(SubType))
     return false;
 
   unsigned W = C.getASTContext().getIntWidth(DestType);
   if (W == 1 || W >= 64U)
     return false;
 
   unsigned long long MaxVal = 1ULL << W;
-  return isGreaterEqual(C, Cast->getSubExpr(), MaxVal);
+  return isGreaterOrEqual(Cast->getSubExpr(), MaxVal, C);
 }
 
 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 isNegative(C, Cast->getSubExpr());
+  return isNegative(Cast->getSubExpr(), C);
 }
 
 void ento::registerConversionChecker(CheckerManager &mgr) {
   mgr.registerChecker<ConversionChecker>();
 }

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangSACheckers.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 "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
static bool isArrayIndexOutOfBounds(CheckerContext &C, const Expr *Ex) {
   DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();
   DefinedOrUnknownSVal NumElements = C.getStoreManager().getSizeInElements(
       state, ER->getSuperRegion(), ER->getValueType());
   ProgramStateRef StInBound = state->assumeInBound(Idx, NumElements, true);
   ProgramStateRef StOutBound = state->assumeInBound(Idx, NumElements, false);
   return StOutBound && !StInBound;
 }
 
+static bool isShiftOverflow(const BinaryOperator *B, CheckerContext &C) {
+  return isGreaterOrEqual(
+      B->getRHS(), C.getASTContext().getIntWidth(B->getLHS()->getType()), C);
+}
+
 void UndefResultChecker::checkPostStmt(const BinaryOperator *B,
                                        CheckerContext &C) const {
   ProgramStateRef state = C.getState();
   const LocationContext *LCtx = C.getLocationContext();
   if (state->getSVal(B, LCtx).isUndef()) {
 
     // Do not report assignments of uninitialized values inside swap functions.
     // This should allow to swap partially uninitialized structs
if (Ex) {
          << " operand of '"
          << BinaryOperator::getOpcodeStr(B->getOpcode())
          << "' is a garbage value";
       if (isArrayIndexOutOfBounds(C, Ex))
         OS << " due to array index out of bounds";
     }
     else {
       // Neither operand was undefined, but the result is undefined.
+      if ((B->getOpcode() == BinaryOperatorKind::BO_Shl ||
+           B->getOpcode() == BinaryOperatorKind::BO_Shr) &&
+          isNegative(B->getRHS(), C)) {
+        OS << "The result of the '"
+           << BinaryOperator::getOpcodeStr(B->getOpcode())
+           << "' expression is undefined due to negative value on the right "
+              "side of operand";
+      } else if ((B->getOpcode() == BinaryOperatorKind::BO_Shl ||
+                  B->getOpcode() == BinaryOperatorKind::BO_Shr) &&
+                 isShiftOverflow(B, C)) {
+        OS << "The result of the '"
+           << BinaryOperator::getOpcodeStr(B->getOpcode())
+           << "' expression is undefined due to shift count >= width of type";
+      } else {
         OS << "The result of the '"
            << BinaryOperator::getOpcodeStr(B->getOpcode())
            << "' expression is undefined";
       }
+    }
     auto report = llvm::make_unique<BugReport>(*BT, OS.str(), N);
     if (Ex) {
       report->addRange(Ex->getSourceRange());
       bugreporter::trackNullOrUndefValue(N, Ex, *report);
     }
     else
       bugreporter::trackNullOrUndefValue(N, B, *report);
 
     C.emitReport(std::move(report));
   }
 }
 
 void ento::registerUndefResultChecker(CheckerManager &mgr) {
   mgr.registerChecker<UndefResultChecker>();
 }

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

if (auto Assign = dyn_cast_or_null<BinaryOperator>(S)) {
     // Initialization
     assert(PD->isSingleDecl() && "We process decls one by one");
     VD = dyn_cast_or_null<VarDecl>(PD->getSingleDecl());
     RHS = VD->getAnyInitializer();
   }
 
   return std::make_pair(VD, RHS);
 }
+
+bool clang::ento::exprComparesTo(SVal LHSVal, BinaryOperatorKind ComparisonOp,
+                                 SVal RHSVal, ProgramStateRef State) {
+
+  if (LHSVal.isUnknownOrUndef())
+    return false;
+  ProgramStateManager &Mgr = State->getStateManager();
+  if (!LHSVal.getAs<NonLoc>() && LHSVal.getAs<Loc>()) {
+    LHSVal = Mgr.getStoreManager().getBinding(State->getStore(),
+                                              LHSVal.castAs<Loc>());
+  }
+  if (LHSVal.isUnknownOrUndef() || !LHSVal.getAs<NonLoc>())
+    return false;
+
+  SValBuilder &Bldr = Mgr.getSValBuilder();
+  SVal Eval = Bldr.evalBinOp(State, ComparisonOp, LHSVal, RHSVal,
+                             Bldr.getConditionType());
+  if (Eval.isUnknownOrUndef())
+    return false;
+  ProgramStateRef StTrue, StFalse;
+  std::tie(StTrue, StFalse) = State->assume(Eval.castAs<DefinedSVal>());
+  return StTrue && !StFalse;
+}
+
+// Is E value greater or equal than Val?
+bool clang::ento::isGreaterOrEqual(const Expr *E, unsigned long long Val,
+                                   CheckerContext &C) {
+  DefinedSVal V =
+      C.getSValBuilder().makeIntVal(Val, C.getASTContext().LongLongTy);
+  return exprComparesTo(C.getSVal(E), BO_GE, V, C.getState());
+}
+
+// Is E value negative?
+bool clang::ento::isNegative(const Expr *E, CheckerContext &C) {
+  DefinedSVal V = C.getSValBuilder().makeIntVal(0, false);
+  return exprComparesTo(C.getSVal(E), BO_LT, V, C.getState());
+}

test/Analysis/bitwise-ops.c

int testConstantShifts_PR18073(int which) {
   case 2:
     return 0ULL << 64; // expected-warning{{The result of the '<<' expression is undefined}}
   case 3:
     return 0ULL << 65; // expected-warning{{The result of the '<<' expression is undefined}}
 
   default:
     return 0;
   }
-}
+}
+
+int testOverflowShift(int a) {
+  if (a == 323) {
+    return 1 << a; // expected-warning{{The result of the '<<' expression is undefined due to shift count >= width of type}}
+  }
+  return 0;
+}
+
+int testNegativeShift(int a) {
+  if (a == -5) {
+    return 1 << a; // expected-warning{{The result of the '<<' expression is undefined due to negative value on the right side of operand}}
+  }
+  return 0;
+}