[analyzer] Add rudimentary handling of AtomicExpr.

[dcoughlin]

Summary

This proposed patch adds crude handling of atomics to the static analyzer.
Rather than ignore AtomicExprs, as we now do, this patch causes the analyzer
to escape the arguments. This is imprecise -- and we should model the
expressions fully in the future -- but it is less wrong than ignoring their
effects altogether.

Richard: Would you mind reviewing the changes I made to AtomicExpr in the AST? I had
to add a const accessor for the subexpressions.

Anna: Would you review the static analyzer portion?

This is rdar://problem/25353187

[grandinj]

test/Analysis/atomics.c

5

folly->fully

[zaks.anna]

lib/StaticAnalyzer/Core/ExprEngine.cpp

2079

alignment is off?

[dcoughlin]

Fix typo and bad indentation.

[dcoughlin]

test/Analysis/atomics.c

5

Thanks! Fixed.

[dcoughlin]

Ping.

Richard: Would you be willing to take a quick look at the change to the AST?

[dcoughlin]

Anna and Jordan said I should just go ahead and commit this.

include/clang/AST/Expr.h

Expr *getVal2() const {
     return cast<Expr>(SubExprs[VAL2]);
   }
   Expr *getWeak() const {
     assert(NumSubExprs > WEAK);
     return cast<Expr>(SubExprs[WEAK]);
   }
 
   AtomicOp getOp() const { return Op; }
-  unsigned getNumSubExprs() { return NumSubExprs; }
+  unsigned getNumSubExprs() const { return NumSubExprs; }
 
   Expr **getSubExprs() { return reinterpret_cast<Expr **>(SubExprs); }
+  const Expr * const *getSubExprs() const {
+    return reinterpret_cast<Expr * const *>(SubExprs);
+  }
 
   bool isVolatile() const {
     return getPtr()->getType()->getPointeeType().isVolatileQualified();
   }
 
   bool isCmpXChg() const {
     return getOp() == AO__c11_atomic_compare_exchange_strong ||
            getOp() == AO__c11_atomic_compare_exchange_weak ||

include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h

public:
   /// VisitLogicalExpr - Transfer function logic for '&&', '||'
   void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
                         ExplodedNodeSet &Dst);
 
   /// VisitMemberExpr - Transfer function for member expressions.
   void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, 
                            ExplodedNodeSet &Dst);
 
+  /// VisitMemberExpr - Transfer function for builtin atomic expressions
+  void VisitAtomicExpr(const AtomicExpr *E, ExplodedNode *Pred,
+                       ExplodedNodeSet &Dst);
+
   /// Transfer function logic for ObjCAtSynchronizedStmts.
   void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
                                    ExplodedNode *Pred, ExplodedNodeSet &Dst);
 
   /// Transfer function logic for computing the lvalue of an Objective-C ivar.
   void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred,
                                 ExplodedNodeSet &Dst);
 

lib/StaticAnalyzer/Core/ExprEngine.cpp

switch (S->getStmtClass()) {
     case Stmt::ObjCSelectorExprClass:
     case Stmt::ParenListExprClass:
     case Stmt::ShuffleVectorExprClass:
     case Stmt::ConvertVectorExprClass:
     case Stmt::VAArgExprClass:
     case Stmt::CUDAKernelCallExprClass:
     case Stmt::OpaqueValueExprClass:
     case Stmt::AsTypeExprClass:
-    case Stmt::AtomicExprClass:
       // Fall through.
 
     // 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::InitListExprClass:
       break;
 
     case Stmt::MemberExprClass:
       Bldr.takeNodes(Pred);
       VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
       Bldr.addNodes(Dst);
       break;
 
+    case Stmt::AtomicExprClass:
+      Bldr.takeNodes(Pred);
+      VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst);
+      Bldr.addNodes(Dst);
+      break;
+
     case Stmt::ObjCIvarRefExprClass:
       Bldr.takeNodes(Pred);
       VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
       Bldr.addNodes(Dst);
       break;
 
     case Stmt::ObjCForCollectionStmtClass:
       Bldr.takeNodes(Pred);
for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
         Bldr.addNodes(Tmp);
       }
     }
   }
 
   getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);
 }
 
+void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
+                                 ExplodedNodeSet &Dst) {
+  ExplodedNodeSet AfterPreSet;
+  getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);
+
+  // For now, treat all the arguments to C11 atomics as escaping.
+  // FIXME: Ideally we should model the behavior of the atomics precisely here.
+
+  ExplodedNodeSet AfterInvalidateSet;
+  StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
+
+  for (ExplodedNodeSet::iterator I = AfterPreSet.begin(), E = AfterPreSet.end();
+       I != E; ++I) {
+    ProgramStateRef State = (*I)->getState();
+    const LocationContext *LCtx = (*I)->getLocationContext();
+
+    SmallVector<SVal, 8> ValuesToInvalidate;
+    for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {
+      const Expr *SubExpr = AE->getSubExprs()[SI];
+      SVal SubExprVal = State->getSVal(SubExpr, LCtx);
+      ValuesToInvalidate.push_back(SubExprVal);
+    }
+
+    State = State->invalidateRegions(ValuesToInvalidate, AE,
+                                    currBldrCtx->blockCount(),
+                                    LCtx,
+                                    /*CausedByPointerEscape*/true,
+                                    /*Symbols=*/nullptr);
+
+    SVal ResultVal = UnknownVal();
+    State = State->BindExpr(AE, LCtx, ResultVal);
+    Bldr.generateNode(AE, *I, State, nullptr,
+                      ProgramPoint::PostStmtKind);
+  }
+
+  getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
+}
+
 namespace {
 class CollectReachableSymbolsCallback final : public SymbolVisitor {
   InvalidatedSymbols Symbols;
 
 public:
   CollectReachableSymbolsCallback(ProgramStateRef State) {}
   const InvalidatedSymbols &getSymbols() const { return Symbols; }
 

test/Analysis/atomics.c

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,debug.ExprInspection -verify %s
+
+// Tests for c11 atomics. Many of these tests currently yield unknown
+// because we don't fully model the atomics and instead imprecisely
+// treat their arguments as escaping.
+
+typedef unsigned int uint32_t;
+typedef enum memory_order {
+  memory_order_relaxed = __ATOMIC_RELAXED,
+  memory_order_consume = __ATOMIC_CONSUME,
+  memory_order_acquire = __ATOMIC_ACQUIRE,
+  memory_order_release = __ATOMIC_RELEASE,
+  memory_order_acq_rel = __ATOMIC_ACQ_REL,
+  memory_order_seq_cst = __ATOMIC_SEQ_CST
+} memory_order;
+
+void clang_analyzer_eval(int);
+
+struct RefCountedStruct {
+  uint32_t refCount;
+  void *ptr;
+};
+
+void test_atomic_fetch_add(struct RefCountedStruct *s) {
+  s->refCount = 1;
+
+  uint32_t result = __c11_atomic_fetch_add((volatile _Atomic(uint32_t) *)&s->refCount,- 1, memory_order_relaxed);
+
+  // When we model atomics fully this should (probably) be FALSE. It should never
+  // be TRUE (because the operation mutates the passed in storage).
+  clang_analyzer_eval(s->refCount == 1); // expected-warning {{UNKNOWN}}
+
+  // When fully modeled this should be TRUE
+  clang_analyzer_eval(result == 1); // expected-warning {{UNKNOWN}}
+}
+
+void test_atomic_load(struct RefCountedStruct *s) {
+  s->refCount = 1;
+
+  uint32_t result = __c11_atomic_load((volatile _Atomic(uint32_t) *)&s->refCount, memory_order_relaxed);
+
+  // When we model atomics fully this should (probably) be TRUE.
+  clang_analyzer_eval(s->refCount == 1); // expected-warning {{UNKNOWN}}
+
+  // When fully modeled this should be TRUE
+  clang_analyzer_eval(result == 1); // expected-warning {{UNKNOWN}}
+}
+
+void test_atomic_store(struct RefCountedStruct *s) {
+  s->refCount = 1;
+
+  __c11_atomic_store((volatile _Atomic(uint32_t) *)&s->refCount, 2, memory_order_relaxed);
+
+  // When we model atomics fully this should (probably) be FALSE. It should never
+  // be TRUE (because the operation mutates the passed in storage).
+  clang_analyzer_eval(s->refCount == 1); // expected-warning {{UNKNOWN}}
+}
+
+void test_atomic_exchange(struct RefCountedStruct *s) {
+  s->refCount = 1;
+
+  uint32_t result = __c11_atomic_exchange((volatile _Atomic(uint32_t) *)&s->refCount, 2, memory_order_relaxed);
+
+  // When we model atomics fully this should (probably) be FALSE. It should never
+  // be TRUE (because the operation mutates the passed in storage).
+  clang_analyzer_eval(s->refCount == 1); // expected-warning {{UNKNOWN}}
+
+  // When fully modeled this should be TRUE
+  clang_analyzer_eval(result == 1); // expected-warning {{UNKNOWN}}
+}
+
+
+void test_atomic_compare_exchange_strong(struct RefCountedStruct *s) {
+  s->refCount = 1;
+  uint32_t expected = 2;
+  uint32_t desired = 3;
+  _Bool result = __c11_atomic_compare_exchange_strong((volatile _Atomic(uint32_t) *)&s->refCount, &expected, desired, memory_order_relaxed, memory_order_relaxed);
+
+  // For now we expect both expected and refCount to be invalidated by the
+  // call. In the future we should model more precisely.
+  clang_analyzer_eval(s->refCount == 3); // expected-warning {{UNKNOWN}}
+  clang_analyzer_eval(expected == 2); // expected-warning {{UNKNOWN}}
+}
+
+void test_atomic_compare_exchange_weak(struct RefCountedStruct *s) {
+  s->refCount = 1;
+  uint32_t expected = 2;
+  uint32_t desired = 3;
+  _Bool result = __c11_atomic_compare_exchange_weak((volatile _Atomic(uint32_t) *)&s->refCount, &expected, desired, memory_order_relaxed, memory_order_relaxed);
+
+  // For now we expect both expected and refCount to be invalidated by the
+  // call. In the future we should model more precisely.
+  clang_analyzer_eval(s->refCount == 3); // expected-warning {{UNKNOWN}}
+  clang_analyzer_eval(expected == 2); // expected-warning {{UNKNOWN}}
+}