[analyzer] Do not cache out on some shared implicit AST nodes.

[xazax.hun]

Summary

Some AST nodes that stands for implicit initialization is shared. The analyzer will do the same evaluation on the same nodes resulting in the same state. The analyzer will "cache out", i.e. it thinks that it visited an already existing node in the exploded graph. This is not true in this case and we lose coverage.

[NoQ]

Ahaa. Ahaa. Okay.

So the AST is like

|   |-DeclStmt 0x7f9f3b8932e0 <line:6:3, col:43>
|   | `-VarDecl 0x7f9f3b892f50 <col:3, col:42> col:7 used a 'int [5]' cinit
|   |   `-InitListExpr 0x7f9f3b893268 <col:14, col:42> 'int [5]'
|   |     |-array_filler: ImplicitValueInitExpr 0x7f9f3b8932d0 <<invalid sloc>> 'int'
|   |     |-IntegerLiteral 0x7f9f3b893118 <col:41> 'int' 4
|   |     |-ImplicitValueInitExpr 0x7f9f3b8932d0 <<invalid sloc>> 'int'
|   |     |-IntegerLiteral 0x7f9f3b893078 <col:31> 'int' 15
|   |     |-ImplicitValueInitExpr 0x7f9f3b8932d0 <<invalid sloc>> 'int'
|   |     `-IntegerLiteral 0x7f9f3b892fd8 <col:21> 'int' 29

And the CFG is like

[B1]
   1: 4
   2: [B1.4]
   3: 15
   4: /*implicit*/(int)0
   5: 29
   6: {[4] = [B1.5], [2] = [B1.3], [0] = [B1.1]}
   7: int a[5] = {[4] = 29, [2] = 15, [0] = 4};

And you're trying to avoid agglutinating program points for [B1.2] and [B1.4].

Can we simply erase the implicit initializers from the CFG? Under an option, of course. We ignore them in the static analyzer anyway (like all constants).

We could do a custom program point just for this problem (which includes the index as part of its identity), but it's kinda underwhelming to build a whole new program point that always does nothing.

[NoQ]

One way to criticize the current solution would be to put an InitListExpr in a loop and immediately discard it and see how states after different numbers of iterations no longer join together only because they have different NoCachingOutForConsts values.

[xazax.hun]

Hmm loops. Right. So this solution is insufficient because it can prevent legitimate caching out in loops.

If we remove those initializers from the CFG wouldn't we loose the Pre/PostStmt callbacks? Is that acceptable? If not, we might need to create a new program point :(

[NoQ]

I doubt we'll ever need these callbacks. I can't imagine any kind of analysis that would need them. Like, these statements have absolutely no effect on the runtime program state.

[xazax.hun]

• Omit nodes from CFG instead of trying to make the states distinct.

[xazax.hun]

• Removed leftover code from previous approach.

[NoQ]

Thanks!!

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

1323–1328

We already have a similar unreachable here :p

clang/include/clang/Analysis/CFG.h

public:
     bool AddTemporaryDtors = false;
     bool AddScopes = false;
     bool AddStaticInitBranches = false;
     bool AddCXXNewAllocator = false;
     bool AddCXXDefaultInitExprInCtors = false;
     bool AddRichCXXConstructors = false;
     bool MarkElidedCXXConstructors = false;
     bool AddVirtualBaseBranches = false;
+    bool OmitImplicitValueInitializers = false;
 
     BuildOptions() = default;
 
     bool alwaysAdd(const Stmt *stmt) const {
       return alwaysAddMask[stmt->getStmtClass()];
     }
 
     BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {

clang/lib/Analysis/CFG.cpp

CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc,
   if (Context->getLangOpts().OpenMP)
     if (auto *D = dyn_cast<OMPExecutableDirective>(S))
       return VisitOMPExecutableDirective(D, asc);
 
   switch (S->getStmtClass()) {
     default:
       return VisitStmt(S, asc);
 
+    case Stmt::ImplicitValueInitExprClass:
+      if (BuildOpts.OmitImplicitValueInitializers)
+        return Block;
+      return VisitStmt(S, asc);
+
     case Stmt::AddrLabelExprClass:
       return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
 
     case Stmt::BinaryConditionalOperatorClass:
       return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
 
     case Stmt::BinaryOperatorClass:
       return VisitBinaryOperator(cast<BinaryOperator>(S), asc);

clang/lib/StaticAnalyzer/Core/AnalysisManager.cpp

: AnaCtxMgr(
           Options.ShouldElideConstructors,
           /*addVirtualBaseBranches=*/true,
           injector),
       Ctx(ASTCtx), LangOpts(ASTCtx.getLangOpts()),
       PathConsumers(PDC), CreateStoreMgr(storemgr),
       CreateConstraintMgr(constraintmgr), CheckerMgr(checkerMgr),
       options(Options) {
   AnaCtxMgr.getCFGBuildOptions().setAllAlwaysAdd();
+  AnaCtxMgr.getCFGBuildOptions().OmitImplicitValueInitializers = true;
 }
 
 AnalysisManager::~AnalysisManager() {
   FlushDiagnostics();
   for (PathDiagnosticConsumers::iterator I = PathConsumers.begin(),
        E = PathConsumers.end(); I != E; ++I) {
     delete *I;
   }

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

switch (S->getStmtClass()) {
     case Stmt::IfStmtClass:
     case Stmt::IndirectGotoStmtClass:
     case Stmt::LabelStmtClass:
     case Stmt::NoStmtClass:
     case Stmt::NullStmtClass:
     case Stmt::SwitchStmtClass:
     case Stmt::WhileStmtClass:
     case Expr::MSDependentExistsStmtClass:
       llvm_unreachable("Stmt should not be in analyzer evaluation loop");
+    case Stmt::ImplicitValueInitExprClass:
+      // These nodes are shared in the CFG and would case caching out.
+      // Moreover, no additional evaluation required for them, the
+      // analyzer can reconstruct these values from the AST.
+      llvm_unreachable("Should be pruned from CFG");
 
     case Stmt::ObjCSubscriptRefExprClass:
     case Stmt::ObjCPropertyRefExprClass:
       llvm_unreachable("These are handled by PseudoObjectExpr");
 
     case Stmt::GNUNullExprClass: {
       // GNU __null is a pointer-width integer, not an actual pointer.
       ProgramStateRef state = Pred->getState();
switch (S->getStmtClass()) {
     // Cases we intentionally don't evaluate, since they don't need
     // to be explicitly evaluated.
     case Stmt::PredefinedExprClass:
     case Stmt::AddrLabelExprClass:
     case Stmt::AttributedStmtClass:
     case Stmt::IntegerLiteralClass:
     case Stmt::FixedPointLiteralClass:
     case Stmt::CharacterLiteralClass:
-    case Stmt::ImplicitValueInitExprClass:
     case Stmt::CXXScalarValueInitExprClass:
     case Stmt::CXXBoolLiteralExprClass:
     case Stmt::ObjCBoolLiteralExprClass:
     case Stmt::ObjCAvailabilityCheckExprClass:
     case Stmt::FloatingLiteralClass:
     case Stmt::NoInitExprClass:
     case Stmt::SizeOfPackExprClass:
     case Stmt::StringLiteralClass:

clang/test/Analysis/designated-initializer-values.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -std=c99 -verify %s
+
+void clang_analyzer_eval(int);
+
+void array_init() {
+  int a[5] = {[4] = 29, [2] = 15, [0] = 4};
+  clang_analyzer_eval(a[0] == 4);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(a[1] == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(a[2] == 15); // expected-warning{{TRUE}}
+  clang_analyzer_eval(a[3] == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(a[4] == 29); // expected-warning{{TRUE}}
+  int b[5] = {[0 ... 2] = 1, [4] = 5};
+  clang_analyzer_eval(b[0] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(b[1] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(b[2] == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(b[3] == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(b[4] == 5); // expected-warning{{TRUE}}
+}
+
+struct point {
+  int x, y;
+};
+
+void struct_init() {
+  struct point p = {.y = 5, .x = 3};
+  clang_analyzer_eval(p.x == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(p.y == 5); // expected-warning{{TRUE}}
+}
+
+void array_of_struct() {
+  struct point ptarray[3] = { [2].y = 1, [2].x = 2, [0].x = 3 };
+  clang_analyzer_eval(ptarray[0].x == 3); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ptarray[0].y == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ptarray[1].x == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ptarray[1].y == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ptarray[2].x == 2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(ptarray[2].y == 1); // expected-warning{{TRUE}}
+}

clang/test/Analysis/designated-initializer.c

 // CHECK:   6: /*no init*/
 // CHECK:   7: {[B1.4], [B1.5], [B1.6]}
 // CHECK:   8: {[B1.7]}
 // CHECK:   9: {/*base*/[B1.3], /*updater*/[B1.8]}
 // CHECK:  10: {[B1.3], .uq.q.a = [B1.4]}
 // CHECK:  11: struct LUQ var = {getUQ(), .uq.q.a = 100};
 // CHECK:  12: 1
 // CHECK:  13: 2
-// CHECK:  14: /*implicit*/(int)0
-// CHECK:  15: {[B1.12], [B1.13]}
+// CHECK:  14: {[B1.12], [B1.13]}
+// CHECK:  17: /*no init*/
 // CHECK:  18: /*no init*/
-// CHECK:  19: /*no init*/
-// CHECK:  20: 3
-// CHECK:  21: {[B1.18], [B1.19], [B1.20]}
-// CHECK:  22: {/*base*/[B1.17], /*updater*/[B1.21]} 
-// CHECK:  24: struct Q s[] = {[0] = (struct Q){1, 2}, [0].c = 3};
+// CHECK:  19: 3
+// CHECK:  20: {[B1.17], [B1.18], [B1.19]}
+// CHECK:  21: {/*base*/[B1.16], /*updater*/[B1.20]} 
+// CHECK:  23: struct Q s[] = {[0] = (struct Q){1, 2}, [0].c = 3};

clang/test/Analysis/initializers-cfg-output.cpp

 // ANALYZER-NEXT:     1:  (CXXConstructExpr, C() (Base initializer), class C)
 // CHECK-NEXT:     2: C([B1.1]) (Base initializer)
 // WARNINGS-NEXT:     3:  (CXXConstructExpr, class B)
 // ANALYZER-NEXT:     3:  (CXXConstructExpr, B() (Base initializer), class B)
 // CHECK-NEXT:     4: B([B1.3]) (Base initializer)
 // WARNINGS-NEXT:     5:  (CXXConstructExpr, class A)
 // ANALYZER-NEXT:     5:  (CXXConstructExpr, A() (Base initializer), class A)
 // CHECK-NEXT:     6: A([B1.5]) (Base initializer)
-// CHECK-NEXT:     7: /*implicit*/(int)0
-// CHECK-NEXT:     8: i([B1.7]) (Member initializer)
-// CHECK-NEXT:     9: this
-// CHECK-NEXT:    10: [B1.9]->i
-// CHECK-NEXT:    11: r([B1.10]) (Member initializer)
-// WARNINGS-NEXT:    12:  (CXXConstructExpr, class A)
-// ANALYZER-NEXT:    12:  (CXXConstructExpr, [B1.13], class A)
-// CHECK-NEXT:    13: A a;
+// CHECK-NEXT:     7: i(/*implicit*/(int)0) (Member initializer)
+// CHECK-NEXT:     8: this
+// CHECK-NEXT:    9: [B1.8]->i
+// CHECK-NEXT:    10: r([B1.9]) (Member initializer)
+// WARNINGS-NEXT:    11:  (CXXConstructExpr, class A)
+// ANALYZER-NEXT:    11:  (CXXConstructExpr, [B1.12], class A)
+// CHECK-NEXT:    12: A a;
 // CHECK-NEXT:     Preds (2): B2 B3
 // CHECK-NEXT:     Succs (1): B0
 // CHECK:        [B2]
 // WARNINGS-NEXT:     1:  (CXXConstructExpr, class A)
 // ANALYZER-NEXT:     1:  (CXXConstructExpr, A() (Base initializer), class A)
 // CHECK-NEXT:     2: A([B2.1]) (Base initializer)
 // CHECK-NEXT:     Preds (1): B3
 // CHECK-NEXT:     Succs (1): B1

clang/test/Analysis/temp-obj-dtors-cfg-output.cpp

 // CHECK:    11: [B1.10].operator int
 // CHECK:    12: [B1.10]
 // CHECK:    13: [B1.12] (ImplicitCastExpr, UserDefinedConversion, int)
 // CHECK:    14: int([B1.13]) (CXXFunctionalCastExpr, NoOp, int)
 // CHECK:    15: [B1.7] + [B1.14]
 // CHECK:    16: a([B1.15]) (Member initializer)
 // CHECK:    17: ~B() (Temporary object destructor)
 // CHECK:    18: ~A() (Temporary object destructor)
-// CHECK:    19: /*implicit*/(int)0
-// CHECK:    20: b([B1.19]) (Member initializer)
+// CHECK:    19: b(/*implicit*/(int)0) (Member initializer)
 // CHECK:     Preds (1): B2
 // CHECK:     Succs (1): B0
 // CHECK:   [B0 (EXIT)]
 // CHECK:     Preds (1): B1
 // CHECK:   [B3 (ENTRY)]
 // CHECK:     Succs (1): B2
 // CHECK:   [B1]
 // CHECK:     1: int b;