[analyzer] Trust global initializers when analyzing main().

[NoQ]

Summary

This is inspired by https://bugs.llvm.org/show_bug.cgi?id=42780, even though it doesn't fix the bug.

If the global variable has an initializer, we'll ignore it because we're normally not analyzing the program from the beginning. This means that a global variable may have changed before we start our analysis.

However when we're analyzing main() as the top-level function, we can rely on global initializers to still be valid. At least in C; in C++ we have global constructors for breaking this logic. In C we can also have global constructors as a GNU extension, but i'd rather not worry about that.

In this patch i don't try to evaluate global initializers; the patch only covers the case when they're constants. This is the reason why we don't cover https://bugs.llvm.org/show_bug.cgi?id=42780, however we could cover it if SValBuilder.getConstantVal() was a bit more feature-rich (namely, we need to be able to constant-evaluate expressions like &var.field where var is a global variable; it's a concrete region (i.e., without symbolic base) value in our model, so we can make getConstantVal() powerful enough to emit it).

For initializers of fields and elements i'm piggybacking on @r.stahl's work to cover global constant initializers (D45774).

The main benefit of this patch is to make it harder for people to send us false positive reproducers that don't actually reproduce the false positive that they're having :)

[NoQ]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

157 ↗

(On Diff #212030)

We could have put this flag into RegionStoreManager instead - after all, it doesn't change for the whole duration of the analysis. It would have made it easier to handle (avoid weird bitwise logic) and probably cheaper, but it'll make the manager needlessly stateful (which wouldn't really hurt at all right now, just looks ugly).

[NoQ]

Actually add the logic for C++.

[baloghadamsoftware]

Thank you for working on this! I agree, we should trust global initializers in main() in C. Can we maybe detect whether GNU global constructors are enabled or better: used?

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

395 ↗

(On Diff #212035)

I think this function deserves now some doc comments since it is not a trivial getter anymore.

630 ↗

(On Diff #212035)

(uintptr_t)1 look like a bit like some kind of magic number. Could we define it as a constant instead?

1693 ↗

(On Diff #212035)

Please, update the comment as well.

1785 ↗

(On Diff #212035)

This one as well.

2005 ↗

(On Diff #212035)

Please add a comment to the block as well.

clang/test/Analysis/main.c

21 ↗

(On Diff #212035)

Please add a negative test case (i.e. function that is not main) as well.

[xazax.hun]

I like the change.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

630 ↗

(On Diff #212035)

Or maybe this can be abstracted away using llvm::PointerIntPair?

[NoQ]

Fxd!

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

630 ↗

(On Diff #212035)

Or maybe this can be abstracted away using llvm::PointerIntPair?

!!!

[Szelethus]

I really like the high level idea proposed by this patch, and the test files make me believe that its correct as well! I'm really not familiar around this part of the code, so if its okay, I'll take my time to do the usual find references, inserting unreachables/asserts to gain a better understanding before the green checkmark.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

215 ↗

(On Diff #214470)

To me personally, reinterpret_cast is a louder shout about having to use statically unverifiable casts that may be dangerous. I don't insist on it however.

394 ↗

(On Diff #214470)

https://llvm.org/docs/CodingStandards.html#doxygen-use-in-documentation-comments

Don’t duplicate function or class name at the beginning of the comment.

Though I'll concede to the argument that we're keeping consistency.

157 ↗

(On Diff #212030)

Could you please add some comments to this? We'll forget about this name I fear in no time.

[NoQ]

Fxd.

[Szelethus]

Sorry for not accepting this -- I actually read the code multiple times and didn't see anything that stood out! I didn't have the time to dig too deep, but if the tests are anything to go by, its gotta be alright.

[NoQ]

Np, post-commit review is always welcome (:

cfe/trunk/lib/StaticAnalyzer/Core/RegionStore.cpp

 typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>
         RegionBindings;
 
 namespace {
 class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *,
                                  ClusterBindings> {
   ClusterBindings::Factory *CBFactory;
 
+  // This flag indicates whether the current bindings are within the analysis
+  // that has started from main(). It affects how we perform loads from
+  // global variables that have initializers: if we have observed the
+  // program execution from the start and we know that these variables
+  // have not been overwritten yet, we can be sure that their initializers
+  // are still relevant. This flag never gets changed when the bindings are
+  // updated, so it could potentially be moved into RegionStoreManager
+  // (as if it's the same bindings but a different loading procedure)
+  // however that would have made the manager needlessly stateful.
+  bool IsMainAnalysis;
+
 public:
   typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>
           ParentTy;
 
   RegionBindingsRef(ClusterBindings::Factory &CBFactory,
                     const RegionBindings::TreeTy *T,
-                    RegionBindings::TreeTy::Factory *F)
+                    RegionBindings::TreeTy::Factory *F,
+                    bool IsMainAnalysis)
       : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F),
-        CBFactory(&CBFactory) {}
+        CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}
 
-  RegionBindingsRef(const ParentTy &P, ClusterBindings::Factory &CBFactory)
+  RegionBindingsRef(const ParentTy &P,
+                    ClusterBindings::Factory &CBFactory,
+                    bool IsMainAnalysis)
       : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P),
-        CBFactory(&CBFactory) {}
+        CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}
 
   RegionBindingsRef add(key_type_ref K, data_type_ref D) const {
     return RegionBindingsRef(static_cast<const ParentTy *>(this)->add(K, D),
-                             *CBFactory);
+                             *CBFactory, IsMainAnalysis);
   }
 
   RegionBindingsRef remove(key_type_ref K) const {
     return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K),
-                             *CBFactory);
+                             *CBFactory, IsMainAnalysis);
   }
 
   RegionBindingsRef addBinding(BindingKey K, SVal V) const;
 
   RegionBindingsRef addBinding(const MemRegion *R,
                                BindingKey::Kind k, SVal V) const;
 
   const SVal *lookup(BindingKey K) const;
public:
   Optional<SVal> getDirectBinding(const MemRegion *R) const;
 
   /// getDefaultBinding - Returns an SVal* representing an optional default
   ///  binding associated with a region and its subregions.
   Optional<SVal> getDefaultBinding(const MemRegion *R) const;
 
   /// Return the internal tree as a Store.
   Store asStore() const {
-    return asImmutableMap().getRootWithoutRetain();
+    llvm::PointerIntPair<Store, 1, bool> Ptr = {
+        asImmutableMap().getRootWithoutRetain(), IsMainAnalysis};
+    return reinterpret_cast<Store>(Ptr.getOpaqueValue());
+  }
+
+  bool isMainAnalysis() const {
+    return IsMainAnalysis;
   }
 
   void printJson(raw_ostream &Out, const char *NL = "\n",
                  unsigned int Space = 0, bool IsDot = false) const {
     for (iterator I = begin(); I != end(); ++I) {
       // TODO: We might need a .printJson for I.getKey() as well.
       Indent(Out, Space, IsDot)
           << "{ \"cluster\": \"" << I.getKey() << "\", \"pointer\": \""
public:
   /// ArrayToPointer - Emulates the "decay" of an array to a pointer
   ///  type.  'Array' represents the lvalue of the array being decayed
   ///  to a pointer, and the returned SVal represents the decayed
   ///  version of that lvalue (i.e., a pointer to the first element of
   ///  the array).  This is called by ExprEngine when evaluating
   ///  casts from arrays to pointers.
   SVal ArrayToPointer(Loc Array, QualType ElementTy) override;
 
+  /// Creates the Store that correctly represents memory contents before
+  /// the beginning of the analysis of the given top-level stack frame.
   StoreRef getInitialStore(const LocationContext *InitLoc) override {
-    return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this);
+    bool IsMainAnalysis = false;
+    if (const auto *FD = dyn_cast<FunctionDecl>(InitLoc->getDecl()))
+      IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus;
+    return StoreRef(RegionBindingsRef(
+        RegionBindingsRef::ParentTy(RBFactory.getEmptyMap(), RBFactory),
+        CBFactory, IsMainAnalysis).asStore(), *this);
   }
 
   //===-------------------------------------------------------------------===//
   // Binding values to regions.
   //===-------------------------------------------------------------------===//
   RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K,
                                            const Expr *Ex,
                                            unsigned Count,
DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state,
                                          const MemRegion* R,
                                          QualType EleTy) override;
 
   //===------------------------------------------------------------------===//
   // Utility methods.
   //===------------------------------------------------------------------===//
 
   RegionBindingsRef getRegionBindings(Store store) const {
-    return RegionBindingsRef(CBFactory,
-                             static_cast<const RegionBindings::TreeTy*>(store),
-                             RBFactory.getTreeFactory());
+    llvm::PointerIntPair<Store, 1, bool> Ptr;
+    Ptr.setFromOpaqueValue(const_cast<void *>(store));
+    return RegionBindingsRef(
+        CBFactory,
+        static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()),
+        RBFactory.getTreeFactory(),
+        Ptr.getInt());
   }
 
   void printJson(raw_ostream &Out, Store S, const char *NL = "\n",
                  unsigned int Space = 0, bool IsDot = false) const override;
 
   void iterBindings(Store store, BindingsHandler& f) override {
     RegionBindingsRef B = getRegionBindings(store);
     for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) {
       // Technically, only i == length is guaranteed to be null.
       // However, such overflows should be caught before reaching this point;
       // the only time such an access would be made is if a string literal was
       // used to initialize a larger array.
       char c = (i >= length) ? '\0' : Str->getCodeUnit(i);
       return svalBuilder.makeIntVal(c, T);
     }
   } else if (const VarRegion *VR = dyn_cast<VarRegion>(superR)) {
-    // Check if the containing array is const and has an initialized value.
+    // Check if the containing array has an initialized value that we can trust.
+    // We can trust a const value or a value of a global initializer in main().
     const VarDecl *VD = VR->getDecl();
-    // Either the array or the array element has to be const.
-    if (VD->getType().isConstQualified() || R->getElementType().isConstQualified()) {
+    if (VD->getType().isConstQualified() ||
+        R->getElementType().isConstQualified() ||
+        (B.isMainAnalysis() && VD->hasGlobalStorage())) {
       if (const Expr *Init = VD->getAnyInitializer()) {
         if (const auto *InitList = dyn_cast<InitListExpr>(Init)) {
           // The array index has to be known.
           if (auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
             int64_t i = CI->getValue().getSExtValue();
             // If it is known that the index is out of bounds, we can return
             // an undefined value.
             if (i < 0)
if (const Expr *Init = FD->getInClassInitializer())
         return *V;
 
   // If the containing record was initialized, try to get its constant value.
   const MemRegion* superR = R->getSuperRegion();
   if (const auto *VR = dyn_cast<VarRegion>(superR)) {
     const VarDecl *VD = VR->getDecl();
     QualType RecordVarTy = VD->getType();
     unsigned Index = FD->getFieldIndex();
-    // Either the record variable or the field has to be const qualified.
-    if (RecordVarTy.isConstQualified() || Ty.isConstQualified())
+    // Either the record variable or the field has an initializer that we can
+    // trust. We trust initializers of constants and, additionally, respect
+    // initializers of globals when analyzing main().
+    if (RecordVarTy.isConstQualified() || Ty.isConstQualified() ||
+        (B.isMainAnalysis() && VD->hasGlobalStorage()))
       if (const Expr *Init = VD->getAnyInitializer())
         if (const auto *InitList = dyn_cast<InitListExpr>(Init)) {
           if (Index < InitList->getNumInits()) {
             if (const Expr *FieldInit = InitList->getInit(Index))
               if (Optional<SVal> V = svalBuilder.getConstantVal(FieldInit))
                 return *V;
           } else {
             return svalBuilder.makeZeroVal(Ty);
SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
   // This must come after the check for constants because closure-captured
   // constant variables may appear in UnknownSpaceRegion.
   if (isa<UnknownSpaceRegion>(MS))
     return svalBuilder.getRegionValueSymbolVal(R);
 
   if (isa<GlobalsSpaceRegion>(MS)) {
     QualType T = VD->getType();
 
+    // If we're in main(), then global initializers have not become stale yet.
+    if (B.isMainAnalysis())
+      if (const Expr *Init = VD->getAnyInitializer())
+        if (Optional<SVal> V = svalBuilder.getConstantVal(Init))
+          return *V;
+
     // Function-scoped static variables are default-initialized to 0; if they
     // have an initializer, it would have been processed by now.
     // FIXME: This is only true when we're starting analysis from main().
     // We're losing a lot of coverage here.
     if (isa<StaticGlobalSpaceRegion>(MS))
       return svalBuilder.makeZeroVal(T);
 
     if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) {

cfe/trunk/test/Analysis/main.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+int x = 1;
+
+struct {
+  int a, b;
+} s = {2, 3};
+
+int arr[] = {4, 5, 6};
+
+void clang_analyzer_eval(int);
+
+int main() {
+  // In main() we know that the initial values are still valid.
+  clang_analyzer_eval(x == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(s.a == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(s.b == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(arr[0] == 4); // expected-warning{{TRUE}}
+  clang_analyzer_eval(arr[1] == 5); // expected-warning{{TRUE}}
+  clang_analyzer_eval(arr[2] == 6); // expected-warning{{TRUE}}
+  return 0;
+}
+
+void foo() {
+  // In other functions these values may already be overwritten.
+  clang_analyzer_eval(x == 1); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(s.a == 2); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(s.b == 3); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(arr[0] == 4); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(arr[1] == 5); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(arr[2] == 6); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+}

cfe/trunk/test/Analysis/main.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+int x = 1;
+
+struct {
+  int a, b;
+} s = {2, 3};
+
+int arr[] = {4, 5, 6};
+
+void clang_analyzer_eval(int);
+
+int main() {
+  // Do not trust global initializers in C++.
+  clang_analyzer_eval(x == 1); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(s.a == 2); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(s.b == 3); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(arr[0] == 4); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(arr[1] == 5); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  clang_analyzer_eval(arr[2] == 6); // expected-warning{{TRUE}} // expected-warning{{FALSE}}
+  return 0;
+}