[analyzer] Model and check unrepresentable left shifts

[rnkovacs]

Summary

Left shifting a signed positive value is undefined if the result is not representable in the unsigned version of the return type.

The analyzer now returns an UndefVal in this case and UndefResultChecker is updated to warn about it.

[xazax.hun]

Overall looks good to me, one comment inline. I think it is good to have these checks to prevent the analyzer executing undefined behavior. Maybe this would make it more feasible to run the analyzer with ubsan :)
In the future, it would be great to also look for these cases symbolically, but I believe it is perfectly fine to have that in a separate patch.

lib/StaticAnalyzer/Core/BasicValueFactory.cpp

238

Do you get a warning if you remove the cast above? I am not sure that we actually want to have the cast here.

[rnkovacs]

In D41816#970845, @xazax.hun wrote:

Overall looks good to me, one comment inline. I think it is good to have these checks to prevent the analyzer executing undefined behavior. Maybe this would make it more feasible to run the analyzer with ubsan :)
In the future, it would be great to also look for these cases symbolically, but I believe it is perfectly fine to have that in a separate patch.

I agree, but I thought that making these checks complete first might be a good idea.

[NoQ]

Looks great. @dcoughlin: would you approve the warning message text?

Maybe actually we could print out the exact numbers that cause the bit shift to overflow, since we do have them when we check.

[rnkovacs]

I extended the warning message to include more information. What do you think?

[dcoughlin]

The diagnostic text looks to me, but I do have a comment about the nested 'if' inline.

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

159

This inner 'if' looks fishy to me because if the 'else' branch is ever taken then OS will be empty.

If the else branch can't be taken then you should turn it into an assert(). If it can be taken, then you should make sure that the fall through goes through the "default" else case at the bottom. One way to do this is to pull out the "is representable logic" into a helper function and call that in the containing 'else if'.

Something like:

if (B->getOpcode() == BinaryOperatorKind::BO_Shl && isLeftShiftResultRepresentable(LHS, RHS)) {
  OS << "The result of the left shift ..."
}

[rnkovacs]

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

159

I overlooked this issue, thanks for pointing out. I pulled the logic out into a helper function.

[dcoughlin]

Looks good to me, thanks!

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

static bool isArrayIndexOutOfBounds(CheckerContext &C, const Expr *Ex) {
   return StOutBound && !StInBound;
 }
 
 static bool isShiftOverflow(const BinaryOperator *B, CheckerContext &C) {
   return C.isGreaterOrEqual(
       B->getRHS(), C.getASTContext().getIntWidth(B->getLHS()->getType()));
 }
 
+static bool isLeftShiftResultUnrepresentable(const BinaryOperator *B,
+                                             CheckerContext &C) {
+  SValBuilder &SB = C.getSValBuilder();
+  ProgramStateRef State = C.getState();
+  const llvm::APSInt *LHS = SB.getKnownValue(State, C.getSVal(B->getLHS()));
+  const llvm::APSInt *RHS = SB.getKnownValue(State, C.getSVal(B->getRHS()));
+  return (unsigned)RHS->getZExtValue() > LHS->countLeadingZeros();
+}
+
 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) {
           OS << '\'' << I->getSExtValue() << "\', which is";
 
         OS << " greater or equal to the width of type '"
            << B->getLHS()->getType().getAsString() << "'.";
       } else if (B->getOpcode() == BinaryOperatorKind::BO_Shl &&
                  C.isNegative(B->getLHS())) {
         OS << "The result of the left shift is undefined because the left "
               "operand is negative";
+      } else if (B->getOpcode() == BinaryOperatorKind::BO_Shl &&
+                 isLeftShiftResultUnrepresentable(B, C)) {
+        SValBuilder &SB = C.getSValBuilder();
+        const llvm::APSInt *LHS =
+            SB.getKnownValue(state, C.getSVal(B->getLHS()));
+        const llvm::APSInt *RHS =
+            SB.getKnownValue(state, C.getSVal(B->getRHS()));
+        OS << "The result of the left shift is undefined due to shifting \'"
+           << LHS->getSExtValue() << "\' by \'" << RHS->getZExtValue()
+           << "\', which is unrepresentable in the unsigned version of "
+           << "the return 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) {

lib/StaticAnalyzer/Core/BasicValueFactory.cpp

switch (Op) {
     case BO_Sub:
       return &getValue( V1 - V2 );
 
     case BO_Shl: {
 
       // FIXME: This logic should probably go higher up, where we can
       // test these conditions symbolically.
 
-      // FIXME: Expand these checks to include all undefined behavior.
       if (V1.isSigned() && V1.isNegative())
         return nullptr;
 
       if (V2.isSigned() && V2.isNegative())
         return nullptr;
 
       uint64_t Amt = V2.getZExtValue();
 
       if (Amt >= V1.getBitWidth())
         return nullptr;
 
+      if (V1.isSigned() && Amt > V1.countLeadingZeros())
+          return nullptr;
+
       return &getValue( V1.operator<<( (unsigned) Amt ));
     }
 
     case BO_Shr: {
 
       // FIXME: This logic should probably go higher up, where we can
       // test these conditions symbolically.
 
-      // FIXME: Expand these checks to include all undefined behavior.
-
       if (V2.isSigned() && V2.isNegative())
         return nullptr;
 
       uint64_t Amt = V2.getZExtValue();
 
       if (Amt >= V1.getBitWidth())
         return nullptr;
 

test/Analysis/bitwise-ops.c

 }
 
 int testNegativeLeftShift(int a) {
   if (a == -3) {
     return a << 1; // expected-warning{{The result of the left shift is undefined because the left operand is negative}}
   }
   return 0;
 }
+
+int testUnrepresentableLeftShift(int a) {
+  if (a == 8)
+    return a << 30; // expected-warning{{The result of the left shift is undefined due to shifting '8' by '30', which is unrepresentable in the unsigned version of the return type 'int'}}
+  return 0;
+}