[analyzer] Model and check unrepresentable left shifts

Patch by: Reka Nikolett Kovacs

Differential Revision: https://reviews.llvm.org/D41816

llvm-svn: 323115

3 files changed, 31 insertions, 3 deletions

diff --git a/clang/lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp
index 08e9a08bfc9..b9a93bedca2 100644
--- a/clang/lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp
@@ -63,6 +63,15 @@ static bool isShiftOverflow(const BinaryOperator *B, CheckerContext &C) {
       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 {
   if (C.getSVal(B).isUndef()) {
@@ -138,6 +147,19 @@ void UndefResultChecker::checkPostStmt(const BinaryOperator *B,
                  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)) {
+        ProgramStateRef State = C.getState();
+        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())
diff --git a/clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp b/clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp
index ec7a7e9e4b1..11658816ed2 100644
--- a/clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp
+++ b/clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp
@@ -224,7 +224,6 @@ BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
       // 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;
 
@@ -236,6 +235,9 @@ BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
       if (Amt >= V1.getBitWidth())
         return nullptr;
 
+      if (V1.isSigned() && Amt > V1.countLeadingZeros())
+          return nullptr;
+
       return &getValue( V1.operator<<( (unsigned) Amt ));
     }
 
@@ -244,8 +246,6 @@ BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
       // 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;
 
diff --git a/clang/test/Analysis/bitwise-ops.c b/clang/test/Analysis/bitwise-ops.c
index fe546580be3..5cdb668867b 100644
--- a/clang/test/Analysis/bitwise-ops.c
+++ b/clang/test/Analysis/bitwise-ops.c
@@ -51,3 +51,9 @@ int testNegativeLeftShift(int a) {
   }
   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;
+}