[Static Analyzer][CFG] Introducing the source array in the CFG of DecompositionDecl

[isuckatcs]

Summary

Before this patch the array being decomposed was not present in the CFG, which lead to liveness issues.

Consider this snippet:

int uninit[2];
int init[2] = {0};

uninit[0] = init[0];  <-- init is marked as a dead symbol and gets removed

auto [i, j] = init;   <-- init is not referenced in the CFG

This patch makes sure, that the required array is referenced in the CFG, so the liveness of the variable is handled properly.

The AST of auto [i, j] = init; and the solution looks like the following:

`-DecompositionDecl 
  |-ArrayInitLoopExpr 
  | |-OpaqueValueExpr          <-- ignore this OpaqueValueExpr
  | | `-DeclRefExpr 'int[2]'   <-- put this DeclRefExpr to the CFG
  | `-ImplicitCastExpr
  |   `-ArraySubscriptExpr
  |     |-ImplicitCastExpr 
  |     | `-OpaqueValueExpr
  |     |   `-DeclRefExpr
  |     `-ArrayInitIndexExpr
  ` ...

Comparing the old and the new CFG of DecompositionDecl:

                         Old CFG                         |                           New CFG                        
                                                         |   
15: init (ImplicitCastExpr, ArrayToPointerDecay, int *)  |  15: init
16: *                                                    |  16: [B1.15] (ImplicitCastExpr, ArrayToPointerDecay, int *)
17: [B1.15][[B1.16]]                                     |  17: *
18: [B1.17] (ImplicitCastExpr, LValueToRValue, int)      |  18: [B1.16][[B1.17]]
19: {[B1.18]}                                            |  19: [B1.18] (ImplicitCastExpr, LValueToRValue, int)
20: auto = {init[*]};                                    |  20: {[B1.19]}
                                                         |  21: auto = {init[*]};

[isuckatcs]

Applied clang-format

[xazax.hun]

I think a unit test would be nice. We have some CFG tests here: https://github.com/llvm/llvm-project/blob/main/clang/unittests/Analysis/CFGTest.cpp

clang/lib/Analysis/CFG.cpp

3866

I think visiting the children we want explicitly would be cleaner. I.e., instead of using a loop, querying each child using getters like getCommonExpr.

[NoQ]

There are also LIT tests in test/Analysis/cfg.cpp etc. which are easier to write and maintain so we usually do them until we have something very specific we want to test.

I see you're still omitting OpaqueValueExpr. I don't remember whether this is the right thing to do, somebody has to eventually omit them but I don't remember whether it's traditionally CFG's responsibility or the consumer (eg. static analyzer)'s responsibility. I think we'll cross this bridge when we get to it.

[isuckatcs]

In D127993#3590071, @NoQ wrote:

There are also LIT tests in test/Analysis/cfg.cpp etc. which are easier to write and maintain so we usually do them until we have something very specific we want to test.

I see you're still omitting OpaqueValueExpr. I don't remember whether this is the right thing to do, somebody has to eventually omit them but I don't remember whether it's traditionally CFG's responsibility or the consumer (eg. static analyzer)'s responsibility. I think we'll cross this bridge when we get to it.

OpaqueValueExpr terminates the CFG building, the expression it contains is not visited at all. My initial idea was that if we encounter the OpaqueValueExpr, just take the Expr is contains and visit it, however that resulted in 30+ failing testcases in analysis. I think this situation when the DeclRefExpr we need is wrapped in an OpaqueValueExpr is unique to ArrayInitLoopExpr, so there is no good general solution here.

We either handle it separately in the CFG, or in liveness analysis.

[NoQ]

Aha great, sounds like this is the right thing to do then!

[isuckatcs]

Addressed comments.

It seems unit tests are focusing more on the features of the CFG itself, and not on CFGs built from snippets.
As this change only affects how a specific expression is evaluated, and doesn't influence the core of the CFG,
I decided to only add a LIT test.

[xazax.hun]

Looks good to me, thanks!

clang/lib/Analysis/CFG.cpp

private:
   CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S);
   CFGBlock *VisitSEHTryStmt(SEHTryStmt *S);
   CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
   CFGBlock *VisitSwitchStmt(SwitchStmt *S);
   CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
                                           AddStmtChoice asc);
   CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
   CFGBlock *VisitWhileStmt(WhileStmt *W);
+  CFGBlock *VisitArrayInitLoopExpr(ArrayInitLoopExpr *A, AddStmtChoice asc);
 
   CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd,
                   bool ExternallyDestructed = false);
   CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
   CFGBlock *VisitChildren(Stmt *S);
   CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc);
   CFGBlock *VisitOMPExecutableDirective(OMPExecutableDirective *D,
                                         AddStmtChoice asc);
switch (S->getStmtClass()) {
     case Stmt::SwitchStmtClass:
       return VisitSwitchStmt(cast<SwitchStmt>(S));
 
     case Stmt::UnaryOperatorClass:
       return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
 
     case Stmt::WhileStmtClass:
       return VisitWhileStmt(cast<WhileStmt>(S));
+    
+    case Stmt::ArrayInitLoopExprClass:
+      return VisitArrayInitLoopExpr(cast<ArrayInitLoopExpr>(S), asc);
   }
 }
 
 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
   if (asc.alwaysAdd(*this, S)) {
     autoCreateBlock();
     appendStmt(Block, S);
   }
CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
   // to this block.  NULL out Block to force lazy creation of another block.
   Block = nullptr;
 
   // Return the condition block, which is the dominating block for the loop.
   Succ = EntryConditionBlock;
   return EntryConditionBlock;
 }
 
+CFGBlock *CFGBuilder::VisitArrayInitLoopExpr(ArrayInitLoopExpr *A, AddStmtChoice asc) {
+  if (asc.alwaysAdd(*this, A)) {
+    autoCreateBlock();
+    appendStmt(Block, A);
+  }
+
+  CFGBlock *B = Block;
+
+  // Visit the children in their reverse order so that they appear in
+  // left-to-right (natural) order in the CFG.
+  reverse_children RChildren(A);
+  for (Stmt *Child : RChildren) {
+    if (Child)
+    {
+      if(auto *OVE = dyn_cast<OpaqueValueExpr>(Child))
+        Child = OVE->getSourceExpr();
+
+      if (CFGBlock *R = Visit(Child))
+        B = R;
+    }
+  }
+  return B;
+}
+
 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *CS) {
   // ObjCAtCatchStmt are treated like labels, so they are the first statement
   // in a block.
 
   // Save local scope position because in case of exception variable ScopePos
   // won't be restored when traversing AST.
   SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);