[Static Analyzer] Small array binding policy

[isuckatcs]

Summary

If a lazyCompoundVal to a struct is bound to the store, there is a policy which decides
whether a copy gets created instead.

This patch introduces a similar policy for arrays, which is required to model structured
binding to arrays without false negatives.

[xazax.hun]

Overall, the code looks good. I am a bit unsure about the default limit though. If someone already did the math that 2 is the sweet spot for structs would that mean we should lower this value for arrays? This is something that is easy to change/tune in the future, so I think it might be ok to commit as is.

[isuckatcs]

I think the sweet spot is between 3-5 somewhere. This number also corresponds to the size of the array which we can model without false negatives.

As for use cases I can think about having coordinates, color values, or similar related values stored in an array, where it makes sense to create a
named binding to each element. Most of these cases consist of at most 4 elements. I set the limit to 5 just in case one more binding must be
created.

Because we have another patch depending on this one, I'm going to merge it, and if 5 seems to be a too large number, we can tune it later as
you mentioned.

[NoQ]

Another magic number around these parts is 4, which is our loop iteration budget. If an array is initialized by a loop with unknown bounds, it'll have 4 bindings. So I think it makes sense to reduce the default to 4 just because weird things may start happening above this threshold.

[isuckatcs]

What's out desired approach for that? Create a new patch, or update this one? Also, should I commit it as usual, or revert this commit first?

[NoQ]

There's nothing immediately wrong with this patch so no need to revert it. It makes sense to revert a patch if it breaks buildbots or if there's no fix coming soon (eg. if we're about to have an entire LLVM release broken). If there was a revert it would have made sense to reuse the phabricator revision as well. But as it is, just make a new patch :-)

[Szelethus]

No need for post commit fixes, just general observations since I noticed them.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

2427

Unless we use this a lot, it'd be better to just use AnalyzerOptions natively, it'd be more visible that this is directly configurable by the user.

There is no need to change this once its here, just a general design observation.

2466

For SVal::getAs, we usually use auto for the return value type (which has its history: D54877#inline-484319!).

clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def

ANALYZER_OPTION(
     "The value 'none' means that all foreign functions are inlined only in the "
     "second phase, 'ctu-max-nodes-*' budge limits the second phase. "
     "Value: \"none\", \"small\", \"all\".",
     "small")
 
 ANALYZER_OPTION(
     unsigned, RegionStoreSmallStructLimit, "region-store-small-struct-limit",
     "The largest number of fields a struct can have and still be considered "
-    "small This is currently used to decide whether or not it is worth forcing "
+    "small. This is currently used to decide whether or not it is worth forcing "
     "a LazyCompoundVal on bind. To disable all small-struct-dependent "
     "behavior, set the option to 0.",
     2)
 
+ANALYZER_OPTION(
+    unsigned, RegionStoreSmallArrayLimit, "region-store-small-array-limit",
+    "The largest number of elements an array can have and still be considered "
+    "small. This is currently used to decide whether or not it is worth forcing "
+    "a LazyCompoundVal on bind. To disable all small-array-dependent "
+    "behavior, set the option to 0.",
+    5)
+
 //===----------------------------------------------------------------------===//
 // String analyzer options.
 //===----------------------------------------------------------------------===//
 
 ANALYZER_OPTION(StringRef, CTUDir, "ctu-dir",
                 "The directory containing the CTU related files.", "")
 
 ANALYZER_OPTION(StringRef, CTUIndexName, "ctu-index-name",

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

private:
   ///
   /// This is currently used to decide whether or not it is worth "forcing" a
   /// LazyCompoundVal on bind.
   ///
   /// This is controlled by 'region-store-small-struct-limit' option.
   /// To disable all small-struct-dependent behavior, set the option to "0".
   unsigned SmallStructLimit;
 
+  /// The largest number of element an array can have and still be
+  /// considered "small".
+  ///
+  /// This is currently used to decide whether or not it is worth "forcing" a
+  /// LazyCompoundVal on bind.
+  ///
+  /// This is controlled by 'region-store-small-struct-limit' option.
+  /// To disable all small-struct-dependent behavior, set the option to "0".
+  unsigned SmallArrayLimit;
+
   /// A helper used to populate the work list with the given set of
   /// regions.
   void populateWorkList(InvalidateRegionsWorker &W,
                         ArrayRef<SVal> Values,
                         InvalidatedRegions *TopLevelRegions);
 
 public:
   RegionStoreManager(ProgramStateManager &mgr)
       : StoreManager(mgr), RBFactory(mgr.getAllocator()),
-        CBFactory(mgr.getAllocator()), SmallStructLimit(0) {
+        CBFactory(mgr.getAllocator()), SmallStructLimit(0), SmallArrayLimit(0) {
     ExprEngine &Eng = StateMgr.getOwningEngine();
     AnalyzerOptions &Options = Eng.getAnalysisManager().options;
     SmallStructLimit = Options.RegionStoreSmallStructLimit;
+    SmallArrayLimit = Options.RegionStoreSmallArrayLimit;
   }
 
   /// setImplicitDefaultValue - Set the default binding for the provided
   ///  MemRegion to the value implicitly defined for compound literals when
   ///  the value is not specified.
   RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B,
                                             const MemRegion *R, QualType T);
 
public: // Part of public interface to class.
   /// BindStruct - Bind a compound value to a structure.
   RegionBindingsRef bindStruct(RegionBindingsConstRef B,
                                const TypedValueRegion* R, SVal V);
 
   /// BindVector - Bind a compound value to a vector.
   RegionBindingsRef bindVector(RegionBindingsConstRef B,
                                const TypedValueRegion* R, SVal V);
 
+  Optional<RegionBindingsRef> tryBindSmallArray(RegionBindingsConstRef B,
+                                                const TypedValueRegion *R,
+                                                const ArrayType *AT,
+                                                nonloc::LazyCompoundVal LCV);
+
   RegionBindingsRef bindArray(RegionBindingsConstRef B,
                               const TypedValueRegion* R,
                               SVal V);
 
   /// Clears out all bindings in the given region and assigns a new value
   /// as a Default binding.
   RegionBindingsRef bindAggregate(RegionBindingsConstRef B,
                                   const TypedRegion *R,
else {
     // should know how to default-initialize any value we can symbolicate.
     assert(!SymbolManager::canSymbolicate(T) && "This type is representable");
     V = UnknownVal();
   }
 
   return B.addBinding(R, BindingKey::Default, V);
 }
 
+Optional<RegionBindingsRef> RegionStoreManager::tryBindSmallArray(
+    RegionBindingsConstRef B, const TypedValueRegion *R, const ArrayType *AT,
+    nonloc::LazyCompoundVal LCV) {
+
+  auto CAT = dyn_cast<ConstantArrayType>(AT);
+
+  // If we don't know the size, create a lazyCompoundVal instead.
+  if (!CAT)
+    return None;
+
+  QualType Ty = CAT->getElementType();
+  if (!(Ty->isScalarType() || Ty->isReferenceType()))
+    return None;
+
+  // If the array is too big, create a LCV instead.
+  uint64_t ArrSize = CAT->getSize().getLimitedValue();
+  if (ArrSize > SmallArrayLimit)
+    return None;
+
+  RegionBindingsRef NewB = B;
+
+  for (uint64_t i = 0; i < ArrSize; ++i) {
+    auto Idx = svalBuilder.makeArrayIndex(i);
+    const ElementRegion *SrcER =
+        MRMgr.getElementRegion(Ty, Idx, LCV.getRegion(), Ctx);
+    SVal V = getBindingForElement(getRegionBindings(LCV.getStore()), SrcER);
+
+    const ElementRegion *DstER = MRMgr.getElementRegion(Ty, Idx, R, Ctx);
+    NewB = bind(NewB, loc::MemRegionVal(DstER), V);
+  }
+
+  return NewB;
+}
+
 RegionBindingsRef
 RegionStoreManager::bindArray(RegionBindingsConstRef B,
                               const TypedValueRegion* R,
                               SVal Init) {
 
   const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
   QualType ElementTy = AT->getElementType();
   Optional<uint64_t> Size;
 
   if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
     Size = CAT->getSize().getZExtValue();
 
   // Check if the init expr is a literal. If so, bind the rvalue instead.
   // FIXME: It's not responsibility of the Store to transform this lvalue
   // to rvalue. ExprEngine or maybe even CFG should do this before binding.
   if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) {
     SVal V = getBinding(B.asStore(), *MRV, R->getValueType());
     return bindAggregate(B, R, V);
   }
 
   // Handle lazy compound values.
-  if (isa<nonloc::LazyCompoundVal>(Init))
+  if (Optional<nonloc::LazyCompoundVal> LCV =
+          Init.getAs<nonloc::LazyCompoundVal>()) {
+    if (Optional<RegionBindingsRef> NewB = tryBindSmallArray(B, R, AT, *LCV))
+      return *NewB;
+
     return bindAggregate(B, R, Init);
+  }
 
   if (Init.isUnknown())
     return bindAggregate(B, R, UnknownVal());
 
   // Remaining case: explicit compound values.
   const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>();
   nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
   uint64_t i = 0;

clang/test/Analysis/analyzer-config.c

 // CHECK-NEXT: optin.cplusplus.UninitializedObject:Pedantic = false
 // CHECK-NEXT: optin.cplusplus.VirtualCall:PureOnly = false
 // CHECK-NEXT: optin.cplusplus.VirtualCall:ShowFixIts = false
 // CHECK-NEXT: optin.osx.cocoa.localizability.NonLocalizedStringChecker:AggressiveReport = false
 // CHECK-NEXT: optin.performance.Padding:AllowedPad = 24
 // CHECK-NEXT: osx.NumberObjectConversion:Pedantic = false
 // CHECK-NEXT: osx.cocoa.RetainCount:TrackNSCFStartParam = false
 // CHECK-NEXT: prune-paths = true
+// CHECK-NEXT: region-store-small-array-limit = 5
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: report-in-main-source-file = false
 // CHECK-NEXT: serialize-stats = false
 // CHECK-NEXT: silence-checkers = ""
 // CHECK-NEXT: stable-report-filename = false
 // CHECK-NEXT: support-symbolic-integer-casts = false
 // CHECK-NEXT: suppress-c++-stdlib = true
 // CHECK-NEXT: suppress-inlined-defensive-checks = true
 // CHECK-NEXT: suppress-null-return-paths = true
 // CHECK-NEXT: track-conditions = true
 // CHECK-NEXT: track-conditions-debug = false
 // CHECK-NEXT: unix.DynamicMemoryModeling:AddNoOwnershipChangeNotes = true
 // CHECK-NEXT: unix.DynamicMemoryModeling:Optimistic = false
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: verbose-report-filename = false
 // CHECK-NEXT: widen-loops = false