[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 ↗

(On Diff #89498)

CompRule?

100 ↗

(On Diff #89498)

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 ↗

(On Diff #89498)

I agree. Good point.

[a.sidorin]

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

99 ↗

(On Diff #89498)

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

46–49 ↗

(On Diff #92315)

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 ↗

(On Diff #92315)

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

46 ↗

(On Diff #92315)

+ 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

46 ↗

(On Diff #92315)

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 ↗

(On Diff #95740)

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 ↗

(On Diff #95740)

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

[danielmarjamaki]

lib/StaticAnalyzer/Core/CheckerHelpers.cpp

116 ↗

(On Diff #95740)

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 ↗

(On Diff #95740)

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 ↗

(On Diff #99022)

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

117

"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"

124

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 ↗

(On Diff #99022)

How about evalComparison as a name for this?

121 ↗

(On Diff #99022)

Please, use doxygen comment style here and below.

[danielmarjamaki]

Fix review comments

[danielmarjamaki]

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

124

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

124

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

134

Please print single quotes around the value.

138

"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

Maybe something like

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

203

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

138

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

138

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

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

static const MemRegion *getLocationRegionIfPostStore(const ExplodedNode *N) {
     return nullptr;
   }
 
   /// \brief Get the value of arbitrary expressions at this point in the path.
   SVal getSVal(const Stmt *S) const {
     return getState()->getSVal(S, getLocationContext());
   }
 
+  /// \brief Is value of expression greater or equal to value (unsigned
+  /// comparison)?
+  bool isGreaterOrEqual(const Expr *E, unsigned long long Val);
+
+  /// \brief Is value of expression negative?
+  bool isNegative(const Expr *E);
+
   /// \brief Generates a new transition in the program state graph
   /// (ExplodedGraph). Uses the default CheckerContext predecessor node.
   ///
   /// @param State The state of the generated node. If not specified, the state
   ///        will not be changed, but the new node will have the checker's tag.
   /// @param Tag The tag is used to uniquely identify the creation site. If no
   ///        tag is specified, a default tag, unique to the given checker,
   ///        will be used. Tags are used to prevent states generated at

lib/StaticAnalyzer/Checkers/ConversionChecker.cpp

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 C.isGreaterOrEqual(Cast->getSubExpr(), MaxVal);
 }
 
 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 C.isNegative(Cast->getSubExpr());
 }
 
 void ento::registerConversionChecker(CheckerManager &mgr) {
   mgr.registerChecker<ConversionChecker>();
 }

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

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 C.isGreaterOrEqual(
+      B->getRHS(), C.getASTContext().getIntWidth(B->getLHS()->getType()));
+}
+
 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 (state->getSVal(B->getLHS(), LCtx).isUndef()) {
       isLeft = true;
     }
     else if (state->getSVal(B->getRHS(), LCtx).isUndef()) {
       Ex = B->getRHS()->IgnoreParenCasts();
       isLeft = false;
     }
 
     if (Ex) {
-      OS << "The " << (isLeft ? "left" : "right")
-         << " operand of '"
+      OS << "The " << (isLeft ? "left" : "right") << " operand of '"
          << BinaryOperator::getOpcodeStr(B->getOpcode())
          << "' is a garbage value";
       if (isArrayIndexOutOfBounds(C, Ex))
         OS << " due to array index out of bounds";
-    }
-    else {
+    } else {
       // Neither operand was undefined, but the result is undefined.
+      if ((B->getOpcode() == BinaryOperatorKind::BO_Shl ||
+           B->getOpcode() == BinaryOperatorKind::BO_Shr) &&
+          C.isNegative(B->getRHS())) {
+        OS << "The result of the "
+           << ((B->getOpcode() == BinaryOperatorKind::BO_Shl) ? "left"
+                                                              : "right")
+           << " shift is undefined because the right operand is negative";
+      } else if ((B->getOpcode() == BinaryOperatorKind::BO_Shl ||
+                  B->getOpcode() == BinaryOperatorKind::BO_Shr) &&
+                 isShiftOverflow(B, C)) {
+
+        OS << "The result of the "
+           << ((B->getOpcode() == BinaryOperatorKind::BO_Shl) ? "left"
+                                                              : "right")
+           << " shift is undefined due to shifting by ";
+
+        SValBuilder &SB = C.getSValBuilder();
+        const llvm::APSInt *I =
+            SB.getKnownValue(C.getState(), C.getSVal(B->getRHS()));
+        if (!I)
+          OS << "a value that is";
+        else if (I->isUnsigned())
+          OS << '\'' << I->getZExtValue() << "\', which is";
+        else
+          OS << '\'' << I->getSExtValue() << "\', which is";
+
+        OS << " larger or equal to the width of type '"
+           << B->getLHS()->getType().getAsString() << "'.";
+      } 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/CheckerContext.cpp

 StringRef CheckerContext::getMacroNameOrSpelling(SourceLocation &Loc) {
   if (Loc.isMacroID())
     return Lexer::getImmediateMacroName(Loc, getSourceManager(),
                                              getLangOpts());
   SmallVector<char, 16> buf;
   return Lexer::getSpelling(Loc, buf, getSourceManager(), getLangOpts());
 }
 
+/// Evaluate comparison and return true if it's known that condition is true
+static bool evalComparison(SVal LHSVal, BinaryOperatorKind ComparisonOp,
+                           SVal RHSVal, ProgramStateRef State) {
+  if (LHSVal.isUnknownOrUndef())
+    return false;
+  ProgramStateManager &Mgr = State->getStateManager();
+  if (!LHSVal.getAs<NonLoc>()) {
+    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;
+}
+
+bool CheckerContext::isGreaterOrEqual(const Expr *E, unsigned long long Val) {
+  DefinedSVal V = getSValBuilder().makeIntVal(Val, getASTContext().LongLongTy);
+  return evalComparison(getSVal(E), BO_GE, V, getState());
+}
+
+bool CheckerContext::isNegative(const Expr *E) {
+  DefinedSVal V = getSValBuilder().makeIntVal(0, false);
+  return evalComparison(getSVal(E), BO_LT, V, getState());
+}

test/Analysis/bitwise-ops.c

int testConstantShifts_PR18073(int which) {
   // FIXME: We should have a checker that actually specifically checks bitwise
   // shifts against the width of the LHS's /static/ type, rather than just
   // having BasicValueFactory return "undefined" when dealing with two constant
   // operands.
   switch (which) {
   case 1:
     return 0ULL << 63; // no-warning
   case 2:
-    return 0ULL << 64; // expected-warning{{The result of the '<<' expression is undefined}}
+    return 0ULL << 64; // expected-warning{{The result of the left shift is undefined due to shifting by '64', which is larger or equal to the width of type 'unsigned long long'}}
   case 3:
-    return 0ULL << 65; // expected-warning{{The result of the '<<' expression is undefined}}
+    return 0ULL << 65; // expected-warning{{The result of the left shift is undefined due to shifting by '65', which is larger or equal to the width of type 'unsigned long long'}}
 
   default:
     return 0;
   }
-}
+}
+
+int testOverflowShift(int a) {
+  if (a == 323) {
+    return 1 << a; // expected-warning{{The result of the left shift is undefined due to shifting by '323', which is larger or equal to the width of type 'int'}}
+  }
+  return 0;
+}
+
+int testNegativeShift(int a) {
+  if (a == -5) {
+    return 1 << a; // expected-warning{{The result of the left shift is undefined because the right operand is negative}}
+  }
+  return 0;
+}