[analyzer] Add a CFG node for the allocator call in a C++ 'new' expression.

In an expression like "new (a, b) Foo(x, y)", two things happen:
- Memory is allocated by calling a function named 'operator new'.
- The memory is initialized using the constructor for 'Foo'.

Currently the analyzer only models the second event, though it has special
cases for both the default and placement forms of operator new. This patch
is the first step towards properly modeling both events: it changes the CFG
so that the above expression now generates the following elements.

1. a
2. b
3. (CFGNewAllocator)
4. x
5. y
6. Foo::Foo

The analyzer currently ignores the CFGNewAllocator element, but the next
step is to treat that as a call like any other.

The CFGNewAllocator element is not added to the CFG for analysis-based
warnings, since none of them take advantage of it yet.

llvm-svn: 199123

9 files changed, 164 insertions, 20 deletions

diff --git a/clang/include/clang/Analysis/AnalysisContext.h b/clang/include/clang/Analysis/AnalysisContext.h
index b1cd212ef92..8fc05f0561f 100644
--- a/clang/include/clang/Analysis/AnalysisContext.h
+++ b/clang/include/clang/Analysis/AnalysisContext.h
@@ -409,7 +409,8 @@ public:
                              bool addInitializers = false,
                              bool addTemporaryDtors = false,
                              bool synthesizeBodies = false,
-                             bool addStaticInitBranches = false);
+                             bool addStaticInitBranches = false,
+                             bool addCXXNewAllocator = true);
 
   ~AnalysisDeclContextManager();
 
diff --git a/clang/include/clang/Analysis/CFG.h b/clang/include/clang/Analysis/CFG.h
index f715055f605..8332f68581a 100644
--- a/clang/include/clang/Analysis/CFG.h
+++ b/clang/include/clang/Analysis/CFG.h
@@ -46,6 +46,7 @@ namespace clang {
   class ASTContext;
   class CXXRecordDecl;
   class CXXDeleteExpr;
+  class CXXNewExpr;
 
 /// CFGElement - Represents a top-level expression in a basic block.
 class CFGElement {
@@ -54,6 +55,7 @@ public:
     // main kind
     Statement,
     Initializer,
+    NewAllocator,
     // dtor kind
     AutomaticObjectDtor,
     DeleteDtor,
@@ -71,7 +73,9 @@ protected:
 
   CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = 0)
     : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),
-      Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {}
+      Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {
+    assert(getKind() == kind);
+  }
 
   CFGElement() {}
 public:
@@ -142,6 +146,25 @@ private:
   }
 };
 
+/// CFGNewAllocator - Represents C++ allocator call.
+class CFGNewAllocator : public CFGElement {
+public:
+  explicit CFGNewAllocator(const CXXNewExpr *S)
+    : CFGElement(NewAllocator, S) {}
+
+  // Get the new expression.
+  const CXXNewExpr *getAllocatorExpr() const {
+    return static_cast<CXXNewExpr *>(Data1.getPointer());
+  }
+
+private:
+  friend class CFGElement;
+  CFGNewAllocator() {}
+  static bool isKind(const CFGElement &elem) {
+    return elem.getKind() == NewAllocator;
+  }
+};
+
 /// CFGImplicitDtor - Represents C++ object destructor implicitly generated
 /// by compiler on various occasions.
 class CFGImplicitDtor : public CFGElement {
@@ -580,6 +603,11 @@ public:
     Elements.push_back(CFGInitializer(initializer), C);
   }
 
+  void appendNewAllocator(CXXNewExpr *NE,
+                          BumpVectorContext &C) {
+    Elements.push_back(CFGNewAllocator(NE), C);
+  }
+
   void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
     Elements.push_back(CFGBaseDtor(BS), C);
   }
@@ -638,6 +666,7 @@ public:
     bool AddImplicitDtors;
     bool AddTemporaryDtors;
     bool AddStaticInitBranches;
+    bool AddCXXNewAllocator;
 
     bool alwaysAdd(const Stmt *stmt) const {
       return alwaysAddMask[stmt->getStmtClass()];
@@ -659,7 +688,8 @@ public:
       ,AddInitializers(false)
       ,AddImplicitDtors(false)
       ,AddTemporaryDtors(false)
-      ,AddStaticInitBranches(false) {}
+      ,AddStaticInitBranches(false)
+      ,AddCXXNewAllocator(false) {}
   };
 
   /// \brief Provides a custom implementation of the iterator class to have the
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
index d89dffe63b0..e0dbc5e583d 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -201,7 +201,9 @@ public:
 
   void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred);
 
-  void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D, 
+  void ProcessNewAllocator(const CXXNewExpr *NE, ExplodedNode *Pred);
+
+  void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
                                ExplodedNode *Pred, ExplodedNodeSet &Dst);
   void ProcessDeleteDtor(const CFGDeleteDtor D,
                          ExplodedNode *Pred, ExplodedNodeSet &Dst);
diff --git a/clang/lib/Analysis/AnalysisDeclContext.cpp b/clang/lib/Analysis/AnalysisDeclContext.cpp
index 79918a3dbcc..5a9b10775af 100644
--- a/clang/lib/Analysis/AnalysisDeclContext.cpp
+++ b/clang/lib/Analysis/AnalysisDeclContext.cpp
@@ -68,7 +68,8 @@ AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
                                                        bool addInitializers,
                                                        bool addTemporaryDtors,
                                                        bool synthesizeBodies,
-                                                       bool addStaticInitBranch)
+                                                       bool addStaticInitBranch,
+                                                       bool addCXXNewAllocator)
   : SynthesizeBodies(synthesizeBodies)
 {
   cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG;
@@ -76,6 +77,7 @@ AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
   cfgBuildOptions.AddInitializers = addInitializers;
   cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
   cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
+  cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
 }
 
 void AnalysisDeclContextManager::clear() {
diff --git a/clang/lib/Analysis/CFG.cpp b/clang/lib/Analysis/CFG.cpp
index 5837d80b8d3..79966fd887d 100644
--- a/clang/lib/Analysis/CFG.cpp
+++ b/clang/lib/Analysis/CFG.cpp
@@ -363,6 +363,7 @@ private:
                                       AddStmtChoice asc);
   CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
   CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
+  CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc);
   CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc);
   CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
   CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
@@ -459,6 +460,9 @@ private:
   void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
     B->appendInitializer(I, cfg->getBumpVectorContext());
   }
+  void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {
+    B->appendNewAllocator(NE, cfg->getBumpVectorContext());
+  }
   void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
     B->appendBaseDtor(BS, cfg->getBumpVectorContext());
   }
@@ -1122,6 +1126,9 @@ CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) {
     case Stmt::CXXConstructExprClass:
       return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
 
+    case Stmt::CXXNewExprClass:
+      return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc);
+
     case Stmt::CXXDeleteExprClass:
       return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc);
 
@@ -3124,6 +3131,22 @@ CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
   return VisitChildren(C);
 }
 
+CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
+                                      AddStmtChoice asc) {
+
+  autoCreateBlock();
+  appendStmt(Block, NE);
+  if (NE->getInitializer())
+    Block = VisitStmt(NE->getInitializer(), asc);
+  if (BuildOpts.AddCXXNewAllocator)
+    appendNewAllocator(Block, NE);
+  if (NE->isArray())
+    Block = VisitStmt(NE->getArraySize(), asc);
+  for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),
+       E = NE->placement_arg_end(); I != E; ++I)
+    Block = VisitStmt(*I, asc);
+  return Block;
+}
 
 CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
                                          AddStmtChoice asc) {
@@ -3426,6 +3449,7 @@ CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
   switch (getKind()) {
     case CFGElement::Statement:
     case CFGElement::Initializer:
+    case CFGElement::NewAllocator:
       llvm_unreachable("getDestructorDecl should only be used with "
                        "ImplicitDtors");
     case CFGElement::AutomaticObjectDtor: {
@@ -3789,6 +3813,11 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
     OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()";
     OS << " (Implicit destructor)\n";
 
+  } else if (Optional<CFGNewAllocator> NE = E.getAs<CFGNewAllocator>()) {
+    OS << "CFGNewAllocator(";
+    if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr())
+      AllocExpr->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
+    OS << ")\n";
   } else if (Optional<CFGDeleteDtor> DE = E.getAs<CFGDeleteDtor>()) {
     const CXXRecordDecl *RD = DE->getCXXRecordDecl();
     if (!RD)
diff --git a/clang/lib/Sema/AnalysisBasedWarnings.cpp b/clang/lib/Sema/AnalysisBasedWarnings.cpp
index 72f8ee1d29d..9864072b722 100644
--- a/clang/lib/Sema/AnalysisBasedWarnings.cpp
+++ b/clang/lib/Sema/AnalysisBasedWarnings.cpp
@@ -1730,6 +1730,7 @@ AnalysisBasedWarnings::IssueWarnings(sema::AnalysisBasedWarnings::Policy P,
   AC.getCFGBuildOptions().AddInitializers = true;
   AC.getCFGBuildOptions().AddImplicitDtors = true;
   AC.getCFGBuildOptions().AddTemporaryDtors = true;
+  AC.getCFGBuildOptions().AddCXXNewAllocator = false;
 
   // Force that certain expressions appear as CFGElements in the CFG.  This
   // is used to speed up various analyses.
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index ad97801cc0e..095e09795da 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -286,6 +286,10 @@ void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
     case CFGElement::Initializer:
       ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred);
       return;
+    case CFGElement::NewAllocator:
+      ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(),
+                          Pred);
+      return;
     case CFGElement::AutomaticObjectDtor:
     case CFGElement::DeleteDtor:
     case CFGElement::BaseDtor:
@@ -547,6 +551,17 @@ void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
 }
 
+void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE,
+                                     ExplodedNode *Pred) {
+  //TODO: Implement VisitCXXNewAllocatorCall
+  ExplodedNodeSet Dst;
+  NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
+  const LocationContext *LCtx = Pred->getLocationContext();
+  PostImplicitCall PP(NE->getOperatorNew(), NE->getLocStart(), LCtx);
+  Bldr.generateNode(PP, Pred->getState(), Pred);
+  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
+}
+
 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
                                          ExplodedNode *Pred,
                                          ExplodedNodeSet &Dst) {
diff --git a/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp b/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
index 2d3caf9332a..c4297292e97 100644
--- a/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
+++ b/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp
@@ -571,6 +571,7 @@ getLocationForCaller(const StackFrameContext *SFC,
     return PathDiagnosticLocation::create(CallerInfo->getDecl(), SM);
   }
   case CFGElement::TemporaryDtor:
+  case CFGElement::NewAllocator:
     llvm_unreachable("not yet implemented!");
   }
 
diff --git a/clang/test/Analysis/cfg.cpp b/clang/test/Analysis/cfg.cpp
index 9da220e8c32..40bc3138b66 100644
--- a/clang/test/Analysis/cfg.cpp
+++ b/clang/test/Analysis/cfg.cpp
@@ -110,13 +110,14 @@ public:
 // CHECK: [B2 (ENTRY)]
 // CHECK-NEXT:   Succs (1): B1
 // CHECK: [B1]
-// CHECK-NEXT:   1:  (CXXConstructExpr, class A)
-// CHECK-NEXT:   2: new A([B1.1])
-// CHECK-NEXT:   3: A *a = new A();
-// CHECK-NEXT:   4: a
-// CHECK-NEXT:   5: [B1.4] (ImplicitCastExpr, LValueToRValue, class A *)
-// CHECK-NEXT:   6: [B1.5]->~A() (Implicit destructor)
-// CHECK-NEXT:   7: delete [B1.5]
+// CHECK-NEXT:   1:  CFGNewAllocator(A *)
+// CHECK-NEXT:   2:  (CXXConstructExpr, class A)
+// CHECK-NEXT:   3: new A([B1.2])
+// CHECK-NEXT:   4: A *a = new A();
+// CHECK-NEXT:   5: a
+// CHECK-NEXT:   6: [B1.5] (ImplicitCastExpr, LValueToRValue, class A *)
+// CHECK-NEXT:   7: [B1.6]->~A() (Implicit destructor)
+// CHECK-NEXT:   8: delete [B1.6]
 // CHECK-NEXT:   Preds (1): B2
 // CHECK-NEXT:   Succs (1): B0
 // CHECK: [B0 (EXIT)]
@@ -130,13 +131,14 @@ void test_deletedtor() {
 // CHECK-NEXT:   Succs (1): B1
 // CHECK: [B1]
 // CHECK-NEXT:   1: 5
-// CHECK-NEXT:   2:  (CXXConstructExpr, class A)
-// CHECK-NEXT:   3: new A {{\[\[}}B1.1]]
-// CHECK-NEXT:   4: A *a = new A [5];
-// CHECK-NEXT:   5: a
-// CHECK-NEXT:   6: [B1.5] (ImplicitCastExpr, LValueToRValue, class A *)
-// CHECK-NEXT:   7: [B1.6]->~A() (Implicit destructor)
-// CHECK-NEXT:   8: delete [] [B1.6]
+// CHECK-NEXT:   2: CFGNewAllocator(A *)
+// CHECK-NEXT:   3:  (CXXConstructExpr, class A)
+// CHECK-NEXT:   4: new A {{\[\[}}B1.1]]
+// CHECK-NEXT:   5: A *a = new A [5];
+// CHECK-NEXT:   6: a
+// CHECK-NEXT:   7: [B1.6] (ImplicitCastExpr, LValueToRValue, class A *)
+// CHECK-NEXT:   8: [B1.7]->~A() (Implicit destructor)
+// CHECK-NEXT:   9: delete [] [B1.7]
 // CHECK-NEXT:   Preds (1): B2
 // CHECK-NEXT:   Succs (1): B0
 // CHECK: [B0 (EXIT)]
@@ -308,4 +310,65 @@ int test_enum_with_extension_default(enum MyEnum value) {
     default: x = 4; break;
   }
   return x;
-}
\ No newline at end of file
+}
+
+
+// CHECK:  [B1 (ENTRY)]
+// CHECK-NEXT:  Succs (1): B0
+// CHECK:  [B0 (EXIT)]
+// CHECK-NEXT:  Preds (1): B1
+// CHECK:  [B1 (ENTRY)]
+// CHECK-NEXT:  Succs (1): B0
+// CHECK:  [B0 (EXIT)]
+// CHECK-NEXT:  Preds (1): B1
+// CHECK:  [B2 (ENTRY)]
+// CHECK-NEXT:  Succs (1): B1
+// CHECK:  [B1]
+// CHECK-NEXT:  1: int buffer[16];
+// CHECK-NEXT:  2: buffer
+// CHECK-NEXT:  3: [B1.2] (ImplicitCastExpr, ArrayToPointerDecay, int *)
+// CHECK-NEXT:  4: [B1.3] (ImplicitCastExpr, BitCast, void *)
+// CHECK-NEXT:  5: CFGNewAllocator(MyClass *)
+// CHECK-NEXT:  6:  (CXXConstructExpr, class MyClass)
+// CHECK-NEXT:  7: new ([B1.4]) MyClass([B1.6])
+// CHECK-NEXT:  8: MyClass *obj = new (buffer) MyClass();
+// CHECK-NEXT:  Preds (1): B2
+// CHECK-NEXT:  Succs (1): B0
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT:  Preds (1): B1
+
+extern void* operator new (unsigned long sz, void* v);
+extern void* operator new[] (unsigned long sz, void* ptr);
+
+class MyClass {
+public:
+  MyClass() {}
+  ~MyClass() {}
+};
+
+void test_placement_new() {
+  int buffer[16];
+  MyClass* obj = new (buffer) MyClass();
+}
+
+// CHECK:  [B2 (ENTRY)]
+// CHECK-NEXT:  Succs (1): B1
+// CHECK: [B1]
+// CHECK-NEXT:  1: int buffer[16];
+// CHECK-NEXT:  2: buffer
+// CHECK-NEXT:  3: [B1.2] (ImplicitCastExpr, ArrayToPointerDecay, int *)
+// CHECK-NEXT:  4: [B1.3] (ImplicitCastExpr, BitCast, void *)
+// CHECK-NEXT:  5: 5
+// CHECK-NEXT:  6: CFGNewAllocator(MyClass *)
+// CHECK-NEXT:  7:  (CXXConstructExpr, class MyClass)
+// CHECK-NEXT:  8: new ([B1.4]) MyClass {{\[\[}}B1.5]]
+// CHECK-NEXT:  9: MyClass *obj = new (buffer) MyClass [5];
+// CHECK-NEXT:  Preds (1): B2
+// CHECK-NEXT:  Succs (1): B0
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT:  Preds (1): B1
+
+void test_placement_new_array() {
+  int buffer[16];
+  MyClass* obj = new (buffer) MyClass[5];
+}