[analyzer][NFC] Refactor ArrayBoundCheckerV2

[steakhal]

Summary

This patch refactors the ArrayBoundCheckerV2 to use more SValVisitor machinery.
IMO this pattern leads to a more functional style, thus more readable - compared to an ad-hoc recursion what getSimplifiedOffsets did.
I also drastically reduce the scope of the mutated local variables for readability.
This resulted in a fairly large change:

• Use MemRegionVisitor to compute RegionRawOffsetV2 of a memory region.
• Use SymExprVisitor to simplify subscript expression.
• Remove getSimplifiedOffsets function.
• Split up ArrayBoundCheckerV2::checkLocation into checkLowerBound and checkUpperBound.

[martong]

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

52

Since you are already deep in refactoring. This calculation together with the enclosing class seems to be useful for other Checkers too. Would make sense to put this to CheckerHelpers?
E.g. the PlacementNewChecker could have benefited from this class if it had been available for use during the implementation of the checker.

298

What is the exact difference in between this algorithm and assumeInBound? What are the benefits (and disadvantages) of using each of them?

And oh wait, there's more: assumeInclusiveRange. Is that also related? (StdLibraryFunctionsChecker uses that for range assumptions.)

[Szelethus]

Before we dive into this too much, if you can point to discussion that explains why we have a 2 versions of the same checker, that would be nice. Why did you chose to work on this one, and not the other? I recall us talking about this in a meeting, but its always great to have it set in stone.

[steakhal]

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

52

You are probably right.
However, I'm not qualified enough to make such a decision.

By the same token, I don't really understand why would anyone do such unfolding by hand?
Could someone clarify the use-cases for RegionRawOffset and RegionRawOffsetV2? @NoQ @vsavchenko @Szelethus?
Eg. we don't use such facilities in the evalBindOpL# functions, but it would probably come handy.

171–172

Here we 'c-style' integral cast the right-hand side value to match the signess and bitwidth of Index. @martong

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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/APSIntType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 using namespace taint;
+using ConcreteInt = nonloc::ConcreteInt;
+using SymbolVal = nonloc::SymbolVal;
 
 namespace {
-class ArrayBoundCheckerV2 :
-    public Checker<check::Location> {
-  mutable std::unique_ptr<BuiltinBug> BT;
+// FIXME: Eventually replace RegionRawOffset with this class.
+class RegionRawOffsetV2 {
+private:
+  const SubRegion *BaseRegion = nullptr;
+  SVal ByteOffset = UnknownVal();
 
-  enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted };
+  RegionRawOffsetV2() = default;
 
-  void reportOOB(CheckerContext &C, ProgramStateRef errorState, OOB_Kind kind,
-                 std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const;
+  /// Compute a raw byte offset from a base region.
+  /// Flatten the nested ElementRegion structure into a byte-offset in a
+  /// SubRegion. E.g:
+  ///   dereferenced location:
+  ///     &Element{Element{Sym{reg_p}, conj{n, int}, char}, 3, int}
+  /// Finds the base region:
+  ///   Region: Sym{reg_p}
+  /// Builds the corresponding symbolic offset expression:
+  ///   Offset: SymIntExpr{conj{n, int}, +, 12, long long}
+  class RawOffsetCalculator final
+      : public MemRegionVisitor<RawOffsetCalculator, RegionRawOffsetV2> {
+    ProgramStateRef State;
+    SValBuilder &SVB;
+
+    RegionRawOffsetV2 Leaf(const SubRegion *R) const {
+      return {R, SVB.makeArrayIndex(0)};
+    }
 
   public:
-  void checkLocation(SVal l, bool isLoad, const Stmt*S,
-                     CheckerContext &C) const;
+    RawOffsetCalculator(ProgramStateRef State, SValBuilder &SVB)
+        : State(State), SVB(SVB) {}
+    using MemRegionVisitor::Visit;
+
+    auto VisitMemRegion(const MemRegion *R) {
+      return Leaf(dyn_cast<SubRegion>(R));
+    }
+
+    RegionRawOffsetV2 VisitElementRegion(const ElementRegion *ER) {
+      // For: Elem{SuperReg, ElemTy, ElemIdx}
+      // 1) Calculate the raw offset of the SuperReg.
+      // 2) Handle the current level.
+      //    Offset := Offset + sizeof(ElemTy) * ElemIdx
+      const RegionRawOffsetV2 RawOffset = Visit(ER->getSuperRegion());
+
+      const QualType ElemTy = ER->getElementType();
+      const NonLoc Index = ER->getIndex();
+
+      // If we can not calculate the sizeof ElemTy, erase result and give up.
+      if (ElemTy->isIncompleteType())
+        return Leaf(nullptr);
+
+      const NonLoc SizeofElemTy = SVB.makeArrayIndex(
+          SVB.getContext().getTypeSizeInChars(ElemTy).getQuantity());
+
+      const QualType ArrayIndexTy = SVB.getArrayIndexType();
+      const NonLoc ByteElementOffset =
+          SVB.evalBinOpNN(State, BO_Mul, Index, SizeofElemTy, ArrayIndexTy)
+              .castAs<NonLoc>();
+
+      SVal NewByteOffset = SVB.evalBinOpNN(
+          State, BO_Add, RawOffset.getByteOffset().castAs<NonLoc>(),
+          ByteElementOffset, ArrayIndexTy);
+      return {RawOffset.getRegion(), NewByteOffset};
+    }
   };
 
-// FIXME: Eventually replace RegionRawOffset with this class.
-class RegionRawOffsetV2 {
-private:
-  const SubRegion *baseRegion;
-  SVal byteOffset;
-
-  RegionRawOffsetV2()
-    : baseRegion(nullptr), byteOffset(UnknownVal()) {}
-
 public:
-  RegionRawOffsetV2(const SubRegion* base, SVal offset)
-    : baseRegion(base), byteOffset(offset) {}
+  RegionRawOffsetV2(const SubRegion *BaseRegion, SVal ByteOffset)
+      : BaseRegion(BaseRegion), ByteOffset(ByteOffset) {}
 
-  NonLoc getByteOffset() const { return byteOffset.castAs<NonLoc>(); }
-  const SubRegion *getRegion() const { return baseRegion; }
+  NonLoc getByteOffset() const { return ByteOffset.castAs<NonLoc>(); }
+  const SubRegion *getRegion() const { return BaseRegion; }
 
-  static RegionRawOffsetV2 computeOffset(ProgramStateRef state,
-                                         SValBuilder &svalBuilder,
-                                         SVal location);
+  static RegionRawOffsetV2 computeOffset(ProgramStateRef State,
+                                         SValBuilder &SVB,
+                                         loc::MemRegionVal Location) {
+    return RawOffsetCalculator(State, SVB).Visit(Location.getRegion());
+  }
 
   void dump() const;
   void dumpToStream(raw_ostream &os) const;
 };
-}
-
-static SVal computeExtentBegin(SValBuilder &svalBuilder,
-                               const MemRegion *region) {
-  const MemSpaceRegion *SR = region->getMemorySpace();
-  if (SR->getKind() == MemRegion::UnknownSpaceRegionKind)
-    return UnknownVal();
-  else
-    return svalBuilder.makeZeroArrayIndex();
-}
-
-// TODO: once the constraint manager is smart enough to handle non simplified
-// symbolic expressions remove this function. Note that this can not be used in
-// the constraint manager as is, since this does not handle overflows. It is
-// safe to assume, however, that memory offsets will not overflow.
-static std::pair<NonLoc, nonloc::ConcreteInt>
-getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent,
-                     SValBuilder &svalBuilder) {
-  Optional<nonloc::SymbolVal> SymVal = offset.getAs<nonloc::SymbolVal>();
-  if (SymVal && SymVal->isExpression()) {
-    if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) {
-      llvm::APSInt constant =
-          APSIntType(extent.getValue()).convert(SIE->getRHS());
-      switch (SIE->getOpcode()) {
-      case BO_Mul:
-        // The constant should never be 0 here, since it the result of scaling
-        // based on the size of a type which is never 0.
-        if ((extent.getValue() % constant) != 0)
-          return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
-        else
-          return getSimplifiedOffsets(
-              nonloc::SymbolVal(SIE->getLHS()),
-              svalBuilder.makeIntVal(extent.getValue() / constant),
-              svalBuilder);
-      case BO_Add:
-        return getSimplifiedOffsets(
-            nonloc::SymbolVal(SIE->getLHS()),
-            svalBuilder.makeIntVal(extent.getValue() - constant), svalBuilder);
-      default:
-        break;
-      }
-    }
-  }
 
-  return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
-}
+/// Check if the pointer dereference would access (read or write) a memory
+/// region outside of an array.
+/// It has much smarter logic dealing with constant addition and multiplication
+/// in the indexer expression, such as: For 'buf[x+3]' it would check if 'x' is
+/// either **below** '-3' or 'x' is greater then or equal to 'extentOf(buf)' to
+/// emit a bug report. Otherwise, we will assume that the indexer expression
+/// **in bound of** the valid range.
+class ArrayBoundCheckerV2 : public Checker<check::Location> {
+  mutable std::unique_ptr<BuiltinBug> BT;
 
-void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad,
-                                        const Stmt* LoadS,
-                                        CheckerContext &checkerContext) const {
+  enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted };
 
-  // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping
-  // some new logic here that reasons directly about memory region extents.
-  // Once that logic is more mature, we can bring it back to assumeInBound()
-  // for all clients to use.
-  //
-  // The algorithm we are using here for bounds checking is to see if the
-  // memory access is within the extent of the base region.  Since we
-  // have some flexibility in defining the base region, we can achieve
-  // various levels of conservatism in our buffer overflow checking.
-  ProgramStateRef state = checkerContext.getState();
+  void reportOOB(CheckerContext &C, ProgramStateRef errorState, OOB_Kind kind,
+                 std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const;
 
-  SValBuilder &svalBuilder = checkerContext.getSValBuilder();
-  const RegionRawOffsetV2 &rawOffset =
-    RegionRawOffsetV2::computeOffset(state, svalBuilder, location);
+  // Returns null state if reported bug, non-null otherwise.
+  ProgramStateRef checkLowerBound(CheckerContext &Ctx, SValBuilder &SVB,
+                                  const ProgramStateRef State,
+                                  RegionRawOffsetV2 RawOffset) const;
+
+  // Returns null state if reported bug, non-null otherwise.
+  ProgramStateRef checkUpperBound(CheckerContext &Ctx, SValBuilder &SVB,
+                                  const ProgramStateRef State,
+                                  RegionRawOffsetV2 RawOffset) const;
 
-  if (!rawOffset.getRegion())
-    return;
+public:
+  void checkLocation(SVal l, bool isLoad, const Stmt *S,
+                     CheckerContext &Ctx) const;
+};
 
-  NonLoc rawOffsetVal = rawOffset.getByteOffset();
+std::pair<NonLoc, ConcreteInt> simplify(SValBuilder &SVB, NonLoc Root,
+                                        ConcreteInt Index) {
+  /// Peel of SymIntExprs one by one while folding the constants on the right.
+  ///
+  /// It reorders the expression `Root` and `Index` at the same time.
+  /// Eg: if `Root` is:
+  ///   `x + 5` then `Index := Index - (typeof(Index))5`
+  ///   `x * 5` then `Index := Index / (typeof(Index))5`
+  /// Then recurse on `x`.
+  class SymExprSimplifier final : public SymExprVisitor<SymExprSimplifier> {
+    SValBuilder &SVB;
+    const SymExpr *RootSymbol;
+    ConcreteInt Index;
 
-  // CHECK LOWER BOUND: Is byteOffset < extent begin?
-  //  If so, we are doing a load/store
-  //  before the first valid offset in the memory region.
+  public:
+    SymExprSimplifier(SValBuilder &SVB, const SymExpr *RootSymbol,
+                      ConcreteInt Index)
+        : SVB(SVB), RootSymbol(RootSymbol), Index(Index) {}
+    using SymExprVisitor::Visit;
+
+    void VisitSymIntExpr(const SymIntExpr *E) {
+      const BinaryOperator::Opcode Op = E->getOpcode();
+      if (Op != BO_Add && Op != BO_Mul)
+        return;
 
-  SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion());
+      llvm::APSInt RHSConstant =
+          APSIntType(Index.getValue()).convert(E->getRHS());
 
-  if (Optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
-    if (NV->getAs<nonloc::ConcreteInt>()) {
-      std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
-          getSimplifiedOffsets(rawOffset.getByteOffset(),
-                               NV->castAs<nonloc::ConcreteInt>(),
-                               svalBuilder);
-      rawOffsetVal = simplifiedOffsets.first;
-      *NV = simplifiedOffsets.second;
+      if (Op == BO_Add) {
+        Index = SVB.makeIntVal(Index.getValue() - RHSConstant);
+        RootSymbol = E->getLHS();
+        Visit(RootSymbol);
+        return;
       }
 
-    SVal lowerBound = svalBuilder.evalBinOpNN(state, BO_LT, rawOffsetVal, *NV,
-                                              svalBuilder.getConditionType());
+      assert(Op == BO_Mul);
 
-    Optional<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>();
-    if (!lowerBoundToCheck)
-      return;
+      // The constant should never be 0 here, since it the result of scaling
+      // based on the size of a type which is never 0.
+      assert(!RHSConstant.isNullValue());
 
-    ProgramStateRef state_precedesLowerBound, state_withinLowerBound;
-    std::tie(state_precedesLowerBound, state_withinLowerBound) =
-      state->assume(*lowerBoundToCheck);
-
-    // Are we constrained enough to definitely precede the lower bound?
-    if (state_precedesLowerBound && !state_withinLowerBound) {
-      reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes);
+      // If the NewExtent is not divisible, we can not further simplify
+      // expressions.
+      if ((Index.getValue() % RHSConstant) != 0)
         return;
-    }
 
-    // Otherwise, assume the constraint of the lower bound.
-    assert(state_withinLowerBound);
-    state = state_withinLowerBound;
+      Index = SVB.makeIntVal(Index.getValue() / RHSConstant);
+      RootSymbol = E->getLHS();
+      Visit(RootSymbol);
     }
 
-  do {
-    // CHECK UPPER BOUND: Is byteOffset >= size(baseRegion)?  If so,
-    // we are doing a load/store after the last valid offset.
-    const MemRegion *MR = rawOffset.getRegion();
-    DefinedOrUnknownSVal Size = getDynamicSize(state, MR, svalBuilder);
-    if (!Size.getAs<NonLoc>())
-      break;
-
-    if (Size.getAs<nonloc::ConcreteInt>()) {
-      std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
-          getSimplifiedOffsets(rawOffset.getByteOffset(),
-                               Size.castAs<nonloc::ConcreteInt>(), svalBuilder);
-      rawOffsetVal = simplifiedOffsets.first;
-      Size = simplifiedOffsets.second;
-    }
+    SymbolVal getRootSymbol() const { return RootSymbol; }
+    ConcreteInt getFoldedIndex() const { return Index; }
+  };
+  if (const auto SymbolicRoot = Root.getAs<SymbolVal>()) {
+    SymExprSimplifier Visitor(SVB, SymbolicRoot->getSymbol(), Index);
+    Visitor.Visit(SymbolicRoot->getSymbol());
+    return {Visitor.getRootSymbol(), Visitor.getFoldedIndex()};
+  }
+  assert(Root.getAs<ConcreteInt>() && "Root must be either int or symbol.");
+  return {Root, Index};
+}
+} // namespace
+
+ProgramStateRef
+ArrayBoundCheckerV2::checkLowerBound(CheckerContext &Ctx, SValBuilder &SVB,
+                                     const ProgramStateRef State,
+                                     RegionRawOffsetV2 RawOffset) const {
+  // If we don't know that the pointer points to the beginning of the region,
+  // skip lower-bound check.
+  if (isa<UnknownSpaceRegion>(RawOffset.getRegion()->getMemorySpace()))
+    return State;
+
+  ConcreteInt Zero = SVB.makeZeroArrayIndex().castAs<ConcreteInt>();
+  SVal RootNonLoc;
+  SVal ConstantFoldedRHS;
+  std::tie(RootNonLoc, ConstantFoldedRHS) =
+      simplify(SVB, RawOffset.getByteOffset(), Zero);
+
+  NonLoc LowerBoundCheck =
+      SVB.evalBinOpNN(State, BO_LT, RootNonLoc.castAs<NonLoc>(),
+                      ConstantFoldedRHS.castAs<ConcreteInt>(),
+                      SVB.getConditionType())
+          .castAs<NonLoc>();
+
+  ProgramStateRef PrecedesLowerBound, WithinLowerBound;
+  std::tie(PrecedesLowerBound, WithinLowerBound) =
+      State->assume(LowerBoundCheck);
+
+  if (PrecedesLowerBound && !WithinLowerBound) {
+    reportOOB(Ctx, PrecedesLowerBound, OOB_Precedes);
+    return nullptr;
 
-    SVal upperbound = svalBuilder.evalBinOpNN(state, BO_GE, rawOffsetVal,
-                                              Size.castAs<NonLoc>(),
-                                              svalBuilder.getConditionType());
-
-    Optional<NonLoc> upperboundToCheck = upperbound.getAs<NonLoc>();
-    if (!upperboundToCheck)
-      break;
+  // Otherwise, assume the constraint of the lower bound.
+  assert(WithinLowerBound);
+  return WithinLowerBound;
+}
 
-    ProgramStateRef state_exceedsUpperBound, state_withinUpperBound;
-    std::tie(state_exceedsUpperBound, state_withinUpperBound) =
-      state->assume(*upperboundToCheck);
+// Returns null state if reported bug, non-null otherwise.
+ProgramStateRef
+ArrayBoundCheckerV2::checkUpperBound(CheckerContext &Ctx, SValBuilder &SVB,
+                                     const ProgramStateRef State,
+                                     RegionRawOffsetV2 RawOffset) const {
+  DefinedOrUnknownSVal Extent =
+      getDynamicSize(State, RawOffset.getRegion(), SVB);
+
+  if (!Extent.getAs<NonLoc>())
+    return State;
+
+  NonLoc RawByteOffset = RawOffset.getByteOffset();
+  if (const auto ExtentInt = Extent.getAs<ConcreteInt>()) {
+    std::tie(RawByteOffset, Extent) =
+        simplify(SVB, RawOffset.getByteOffset(), *ExtentInt);
+  }
+
+  NonLoc UpperBoundCheck =
+      SVB.evalBinOpNN(State, BO_GE, RawByteOffset, Extent.castAs<NonLoc>(),
+                      SVB.getConditionType())
+          .castAs<NonLoc>();
+
+  ProgramStateRef ExceedsUpperBound, WithinUpperBound;
+  std::tie(ExceedsUpperBound, WithinUpperBound) =
+      State->assume(UpperBoundCheck);
 
-    // If we are under constrained and the index variables are tainted, report.
-    if (state_exceedsUpperBound && state_withinUpperBound) {
-      SVal ByteOffset = rawOffset.getByteOffset();
-      if (isTainted(state, ByteOffset)) {
-        reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted,
-                  std::make_unique<TaintBugVisitor>(ByteOffset));
-        return;
-      }
-    } else if (state_exceedsUpperBound) {
-      // If we are constrained enough to definitely exceed the upper bound,
-      // report.
-      assert(!state_withinUpperBound);
-      reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes);
-      return;
-    }
+  if (ExceedsUpperBound && WithinUpperBound) {
+    SVal ByteOffset = RawOffset.getByteOffset();
+    if (isTainted(State, ByteOffset)) {
+      reportOOB(Ctx, ExceedsUpperBound, OOB_Tainted,
+      return nullptr;
+  } else if (ExceedsUpperBound) {
+    assert(!WithinUpperBound);
+    reportOOB(Ctx, ExceedsUpperBound, OOB_Excedes);
+    return nullptr;
 
-    assert(state_withinUpperBound);
-    state = state_withinUpperBound;
-  }
-  while (false);
+  assert(WithinUpperBound);
+  return WithinUpperBound;
 
-  checkerContext.addTransition(state);
+void ArrayBoundCheckerV2::checkLocation(SVal Location, bool, const Stmt *,
+                                        CheckerContext &Ctx) const {
+  // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping
+  // some new logic here that reasons directly about memory region extents.
+  // Once that logic is more mature, we can bring it back to assumeInBound()
+  // for all clients to use.
+  //
+  // The algorithm we are using here for bounds checking is to see if the
+  // memory access is within the extent of the base region.  Since we
+  // have some flexibility in defining the base region, we can achieve
+  // various levels of conservatism in our buffer overflow checking.
+  // TODO: Check if these comments are still valid:
+  //  - Why would anyone use this 'experimental logic' if it does not handle
+  //  overflows?
+  //  - "we can achieve various levels of conservatism" What?
+  ProgramStateRef State = Ctx.getState();
+  SValBuilder &SVB = Ctx.getSValBuilder();
+  const RegionRawOffsetV2 RawOffset = RegionRawOffsetV2::computeOffset(
+      State, SVB, Location.castAs<loc::MemRegionVal>());
+  assert(RawOffset.getRegion() && "It should be a valid region.");
+
+  // Is byteOffset < extent begin?
+  // If so, we are doing a load/store before the first valid offset in the
+  // memory region.
+  State = checkLowerBound(Ctx, SVB, State, RawOffset);
+  if (!State)
+    return;
+
+  // Is byteOffset >= extentOf(BaseRegion)?
+  // If so, we are doing a load/store after the last valid offset.
+  State = checkUpperBound(Ctx, SVB, State, RawOffset);
+  if (!State)
+    return;
+
+  // Continue the analysis while we know that this access must be valid.
+  Ctx.addTransition(State);
 }
 
 void ArrayBoundCheckerV2::reportOOB(
     CheckerContext &checkerContext, ProgramStateRef errorState, OOB_Kind kind,
     std::unique_ptr<BugReporterVisitor> Visitor) const {
 
   ExplodedNode *errorNode = checkerContext.generateErrorNode(errorState);
   if (!errorNode)
LLVM_DUMP_METHOD void RegionRawOffsetV2::dump() const {
   dumpToStream(llvm::errs());
 }
 
 void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const {
   os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}';
 }
 #endif
 
-// Lazily computes a value to be used by 'computeOffset'.  If 'val'
-// is unknown or undefined, we lazily substitute '0'.  Otherwise,
-// return 'val'.
-static inline SVal getValue(SVal val, SValBuilder &svalBuilder) {
-  return val.getAs<UndefinedVal>() ? svalBuilder.makeArrayIndex(0) : val;
-}
-
-// Scale a base value by a scaling factor, and return the scaled
-// value as an SVal.  Used by 'computeOffset'.
-static inline SVal scaleValue(ProgramStateRef state,
-                              NonLoc baseVal, CharUnits scaling,
-                              SValBuilder &sb) {
-  return sb.evalBinOpNN(state, BO_Mul, baseVal,
-                        sb.makeArrayIndex(scaling.getQuantity()),
-                        sb.getArrayIndexType());
-}
-
-// Add an SVal to another, treating unknown and undefined values as
-// summing to UnknownVal.  Used by 'computeOffset'.
-static SVal addValue(ProgramStateRef state, SVal x, SVal y,
-                     SValBuilder &svalBuilder) {
-  // We treat UnknownVals and UndefinedVals the same here because we
-  // only care about computing offsets.
-  if (x.isUnknownOrUndef() || y.isUnknownOrUndef())
-    return UnknownVal();
-
-  return svalBuilder.evalBinOpNN(state, BO_Add, x.castAs<NonLoc>(),
-                                 y.castAs<NonLoc>(),
-                                 svalBuilder.getArrayIndexType());
-}
-
-/// Compute a raw byte offset from a base region.  Used for array bounds
-/// checking.
-RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state,
-                                                   SValBuilder &svalBuilder,
-                                                   SVal location)
-{
-  const MemRegion *region = location.getAsRegion();
-  SVal offset = UndefinedVal();
-
-  while (region) {
-    switch (region->getKind()) {
-      default: {
-        if (const SubRegion *subReg = dyn_cast<SubRegion>(region)) {
-          offset = getValue(offset, svalBuilder);
-          if (!offset.isUnknownOrUndef())
-            return RegionRawOffsetV2(subReg, offset);
-        }
-        return RegionRawOffsetV2();
-      }
-      case MemRegion::ElementRegionKind: {
-        const ElementRegion *elemReg = cast<ElementRegion>(region);
-        SVal index = elemReg->getIndex();
-        if (!index.getAs<NonLoc>())
-          return RegionRawOffsetV2();
-        QualType elemType = elemReg->getElementType();
-        // If the element is an incomplete type, go no further.
-        ASTContext &astContext = svalBuilder.getContext();
-        if (elemType->isIncompleteType())
-          return RegionRawOffsetV2();
-
-        // Update the offset.
-        offset = addValue(state,
-                          getValue(offset, svalBuilder),
-                          scaleValue(state,
-                          index.castAs<NonLoc>(),
-                          astContext.getTypeSizeInChars(elemType),
-                          svalBuilder),
-                          svalBuilder);
-
-        if (offset.isUnknownOrUndef())
-          return RegionRawOffsetV2();
-
-        region = elemReg->getSuperRegion();
-        continue;
-      }
-    }
-  }
-  return RegionRawOffsetV2();
-}
-
 void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) {
   mgr.registerChecker<ArrayBoundCheckerV2>();
 }
 
 bool ento::shouldRegisterArrayBoundCheckerV2(const CheckerManager &mgr) {
   return true;
 }