[analyzer] Fix offset overflow check in MemRegion

[george.karpenkov]

Summary

rdar://39593879
https://bugs.llvm.org/show_bug.cgi?id=37142

[NoQ]

Aha, ok, so Add and Mul were swapped in the pre-patch code, and the result was then discarded and recomputed correctly, but overflow checks didn't fire. Makes sense :)

This one looks as if it'd need a rebase because previous patches in the stack change the API that's being removed here.

clang/lib/StaticAnalyzer/Core/MemRegion.cpp

 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Support/CheckedArithmetic.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <cstdint>
 #include <functional>
 #include <iterator>
const SymbolicRegion *MemRegion::getSymbolicBase() const {
   while (SubR) {
     if (const auto *SymR = dyn_cast<SymbolicRegion>(SubR))
       return SymR;
     SubR = dyn_cast<SubRegion>(SubR->getSuperRegion());
   }
   return nullptr;
 }
 
-/// Perform a given operation on two integers, return whether it overflows.
-/// Optionally write the resulting output into \p Res.
-static bool checkedOp(
-    int64_t LHS,
-    int64_t RHS,
-    std::function<llvm::APInt(llvm::APInt *, const llvm::APInt &, bool &)> Op,
-    int64_t *Res = nullptr) {
-  llvm::APInt ALHS(/*BitSize=*/64, LHS, /*Signed=*/true);
-  llvm::APInt ARHS(/*BitSize=*/64, RHS, /*Signed=*/true);
-  bool Overflow;
-  llvm::APInt Out = Op(&ALHS, ARHS, Overflow);
-  if (!Overflow && Res)
-    *Res = Out.getSExtValue();
-  return Overflow;
-}
-
-static bool checkedAdd(
-    int64_t LHS,
-    int64_t RHS,
-    int64_t *Res=nullptr) {
-  return checkedOp(LHS, RHS, &llvm::APInt::sadd_ov, Res);
-}
-
-static bool checkedMul(
-    int64_t LHS,
-    int64_t RHS,
-    int64_t *Res=nullptr) {
-  return checkedOp(LHS, RHS, &llvm::APInt::smul_ov, Res);
-}
-
 RegionRawOffset ElementRegion::getAsArrayOffset() const {
-  CharUnits offset = CharUnits::Zero();
+  int64_t offset = 0;
   const ElementRegion *ER = this;
   const MemRegion *superR = nullptr;
   ASTContext &C = getContext();
 
   // FIXME: Handle multi-dimensional arrays.
 
   while (ER) {
     superR = ER->getSuperRegion();
 
     // FIXME: generalize to symbolic offsets.
     SVal index = ER->getIndex();
-    if (Optional<nonloc::ConcreteInt> CI = index.getAs<nonloc::ConcreteInt>()) {
+    if (auto CI = index.getAs<nonloc::ConcreteInt>()) {
       // Update the offset.
       int64_t i = CI->getValue().getSExtValue();
 
       if (i != 0) {
         QualType elemType = ER->getElementType();
 
         // If we are pointing to an incomplete type, go no further.
         if (elemType->isIncompleteType()) {
           superR = ER;
           break;
         }
 
-        CharUnits size = C.getTypeSizeInChars(elemType);
-
-        int64_t Mult;
-        bool Overflow = checkedAdd(i, size.getQuantity(), &Mult);
-        if (!Overflow)
-          Overflow = checkedMul(Mult, offset.getQuantity());
-        if (Overflow) {
+        int64_t size = C.getTypeSizeInChars(elemType).getQuantity();
+        if (auto NewOffset = llvm::checkedMulAdd(i, size, offset)) {
+          offset = *NewOffset;
+        } else {
           LLVM_DEBUG(llvm::dbgs() << "MemRegion::getAsArrayOffset: "
                                   << "offset overflowing, returning unknown\n");
 
           return nullptr;
         }
-
-        offset += (i * size);
       }
 
       // Go to the next ElementRegion (if any).
       ER = dyn_cast<ElementRegion>(superR);
       continue;
     }
 
     return nullptr;
   }
 
   assert(superR && "super region cannot be NULL");
-  return RegionRawOffset(superR, offset);
+  return RegionRawOffset(superR, CharUnits::fromQuantity(offset));
 }
 
 /// Returns true if \p Base is an immediate base class of \p Child
 static bool isImmediateBase(const CXXRecordDecl *Child,
                             const CXXRecordDecl *Base) {
   assert(Child && "Child must not be null");
   // Note that we do NOT canonicalize the base class here, because
   // ASTRecordLayout doesn't either. If that leads us down the wrong path,

clang/test/Analysis/region_store_overflow.c

 // RUN: %clang_analyze_cc1 -analyze -analyzer-checker=core -verify %s
 
-// expected-no-diagnostics
 int **h;
 int overflow_in_memregion(long j) {
   for (int l = 0;; ++l) {
     if (j - l > 0)
       return h[j - l][0]; // no-crash
   }
   return 0;
 }
+
+void rdar39593879(long long *d) {
+  long e, f;
+  e = f = d[1]; // no-crash
+  for (; d[e];) f-- > 0; // expected-warning{{relational comparison result unused}}; 
+}