[analyzer] Get construction into `operator new` running in simple cases.

[NoQ]

Summary

Under the assumption of -analyzer-config c++-allocator-inlining=true, which enables evaluation of operator new as a regular function call, this patch shows what it takes to actually inline the constructor into the return value of such operator call.

The CFG for a new C() expression looks like:

• CXXNewAllocator new C() (a special kind of CFGElement on which operator new is being evaluated)
• CXXConstructExpr C() (a regular CFGStmt element on which we call the constructor)
• CXXNewExpr new C() (a regular CFGStmt element on which we should ideally have nothing to do)

What i did here is:

1. First, i relax the requirements for constructor regions, as discussed on the mailing list (http://lists.llvm.org/pipermail/cfe-dev/2017-November/056095.html). We can now construct into ElementRegion unless it actually represents an array element (we're not dealing with operator new[] yet). Also we remove the explicit bailout for constructions that correspond to operator new parent expressions, as long as -analyzer-config c++-allocator-inlining is enabled. See changes in mayInlineCallKind().

2. Then, when the constructor is being modeled, we're trying to get back the value returned by operator new. This is done similarly to other construction cases - by finding the next (!!) element in the CFG, figuring out that it's a CXXNewExpr, and then taking the respective region to construct into from the Environment. The CXXNewAllocator element is not relied upon on this phase - for now it only triggers the evaluation of operator new at the right moment, so that we had the return value. See changes in getRegionForConstructedObject() and canHaveDirectConstructor().

3. When we reach the actual CXXNewExpr CFG element (the third one), we need to preserve the value we already have for the CXXNewExpr in the environment. The old code that's conjuring a (heap) pointer here would probably still remain to handle the case when an inlined operator new has actually returned an UnknownVal. Still, this needs polishing, as the FIXME at the top of VisitCXXNewExpr() suggests. See the newly added hack in VisitCXXNewExpr().

4. Finally, the CXXNewExpr value keeps dying in the Environment. From the point of view of the current liveness analysis, the new-expression is dead (or rather not yet born) until the CXXNewExpr statement element is reached, so it immediately gets purged on every step. The really dirty code that prevents this, that should never be committed, is in shouldRemoveDeadBindings(): for the sake of this proof-of-concept, i've crudely disabled garbage collection on the respective moments of time. I believe that the proper fix would be on the liveness analysis side: mark the new-expression as live between the CXXNewAllocator element and CXXNewExpr statement element.

My todo list before committing this would be:

1. Fix the live expressions hack.
2. See how reliable is findElementDirectlyInitializedByCurrentConstructor() in this case.
3. Understand how my code works for non-object constructors (eg. new int).
4. See how much VisitCXXNewExpr can be refactored.

Once this lands, i think we should be looking into enabling -analyzer-config c++-allocator-inlining by default.

[NoQ]

for the sake of this proof-of-concept, i've crudely disabled garbage collection on the respective moments of time

Forgot to mention that this breaks tests in NewDeleteLeaks-PR19102.cpp, which are still failing in the present revision. Leak warnings get delayed to much later lines of code here. This example shows that this liveness hack may delay garbage collection indefinitely.

[NoQ]

Replaced the live expression hack with a slightly better approach. It doesn't update the live variables analysis to take CFGNewAllocator into account, but at least tests now pass.

In order to keep the return value produced by the operator new() call around until CXXNewExpr is evaluated, i added a program state trait, CXXNewAllocatorValueStack:

1. Upon evaluating CFGNewAllocator, the return SVal of the evaluated allocator call is put here;
2. Upon evaluating CXXConstructExpr, that return value is retrieved from here;
3. Upon evaluating CXXNewExpr, the return value is retrieved from here again and then wiped.

In order to support nested allocator calls, this state trait is organized as a stack/FIFO, with push in CFGNewAllocator and pop in CXXNewExpr. The llvm::ImmutableList thing offers some asserts for warning us when we popped more times than we pushed; we might want to add more asserts here to detect other mismatches, but i don't see a need for implementing this as an environment-like map from (Expr, LocationContext) to SVal.

Why SVal and not MemRegion? Because i believe that ideally we want to produce constructor calls with null or undefined this-arguments. Constructors into null pointers should be skipped - this is how operator new(std::nothrow) works, for instance. Constructors into garbage pointers should be immediately caught by the checkers (to throw a warning and generate a sink), but we still need to produce them so that the checkers could catch them. But for now CXXConstructorCall has room only for one pointer, which is currently const MemRegion *, so this still remains to be tackled.

Also we need to make sure that not only the expression lives, but also its value lives, with all the various traits attached to it. Hence the new facility in ExprEngine::removeDead() to mark the values in CXXNewAllocatorValueStack as live. Test included in new-ctor-inlined.cpp (the one with s != 0) covers this situation.

Some doxygen comments updated.

[xazax.hun]

In D40560#947514, @NoQ wrote:

Replaced the live expression hack with a slightly better approach. It doesn't update the live variables analysis to take CFGNewAllocator into account, but at least tests now pass.

In order to keep the return value produced by the operator new() call around until CXXNewExpr is evaluated, i added a program state trait, CXXNewAllocatorValueStack:

1. Upon evaluating CFGNewAllocator, the return SVal of the evaluated allocator call is put here;
2. Upon evaluating CXXConstructExpr, that return value is retrieved from here;
3. Upon evaluating CXXNewExpr, the return value is retrieved from here again and then wiped.

In order to support nested allocator calls, this state trait is organized as a stack/FIFO, with push in CFGNewAllocator and pop in CXXNewExpr. The llvm::ImmutableList thing offers some asserts for warning us when we popped more times than we pushed; we might want to add more asserts here to detect other mismatches, but i don't see a need for implementing this as an environment-like map from (Expr, LocationContext) to SVal.

I think it would be great to have tests for such cases to make it apparent it is not trivial to do this only based on the cfg.
Maybe something like:

A *a = new A(new B, coin ? new C : new D, inlinedCallWithMoreAllocs());

Or in case it turns out to be an easy problem to match these from CFG, I prefer avoiding the state.

Also having a new expression within an overloaded operator new might be interesting.

Why SVal and not MemRegion? Because i believe that ideally we want to produce constructor calls with null or undefined this-arguments. Constructors into null pointers should be skipped - this is how operator new(std::nothrow) works, for instance. Constructors into garbage pointers should be immediately caught by the checkers (to throw a warning and generate a sink), but we still need to produce them so that the checkers could catch them. But for now CXXConstructorCall has room only for one pointer, which is currently const MemRegion *, so this still remains to be tackled.

Are you sure we need to produce undef vals? Couldn't a checker subscribe to the post allocator call and check for the undefined value and generate a sink before the constructor call? I am not opposed to using SVals there, just curious.

Also we need to make sure that not only the expression lives, but also its value lives, with all the various traits attached to it. Hence the new facility in ExprEngine::removeDead() to mark the values in CXXNewAllocatorValueStack as live. Test included in new-ctor-inlined.cpp (the one with s != 0) covers this situation.

Some doxygen comments updated.

[a.sidorin]

Hi Artem. This patch looks OK, just stylish issues.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

112 ↗

(On Diff #125850)

constructors

474 ↗

(On Diff #125850)

Space after ':'? (Same below and upper)

522 ↗

(On Diff #125850)

Should this be under 'if' as well?

[NoQ]

• Fix pop from empty stack.
• Add recursive operator new tests.
  • Disable argument invalidation when the allocator was inlined (needed for those tests to work)

In D40560#957653, @xazax.hun wrote:

I think it would be great to have tests for such cases to make it apparent it is not trivial to do this only based on the cfg.
Maybe something like:

A *a = new A(new B, coin ? new C : new D, inlinedCallWithMoreAllocs());

Or in case it turns out to be an easy problem to match these from CFG, I prefer avoiding the state.

Also having a new expression within an overloaded operator new might be interesting.

Yeah, that's an excellent idea, thanks! I totally forgot about it.

Note, however, that neither chaining operator new as new(new) C(...) nor calling new from within the allocator actually makes our stack grow. In the former case, inner new-expression is fully evaluated before the outer new-expression even starts. In the latter case, the value for the outer allocator will only be put on stack after the outer allocator exits, after the inner new-expression is fully evaluated.

So in order to actually make use of the stack, we need to call operator new within a constructor that constructs into an outer operator new. In this case we first evaluate the outer allocator and put its results on the stack, then we evaluate the constructor and the operator new within it and put another value on the stack, and only then we pop both values.

See newly added tests for more details.

Are you sure we need to produce undef vals? Couldn't a checker subscribe to the post allocator call and check for the undefined value and generate a sink before the constructor call? I am not opposed to using SVals there, just curious.

Yep, you're totally right. Now that we understand how these work, we can actually catch the undefined operator new return value in or just after the allocator. Other reasons still stand though.

[NoQ]

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp

522 ↗

(On Diff #125850)

Whooooooooops!! Thanks!

Apparently, ImmutableList::getTail() doesn't crash when the list is empty. And i thought we're catching this sort of bugs.

Added the relevant assertion into popCXXNewAllocatorValue().

[NoQ]

I think this commit starts to make sense, so i removed the "WIP" marker. I guess it's better to leave todos 2 and 4 to follow-up commits, and 1 and 3 are already addressed.

[NoQ]

• Actually fix the comment about why we need to act on null or undefined values.
• Fix for(:) whitespace.

[NoQ]

• Fix more for(:) whitespace.

[NoQ]

Sorry for the spam.

[NoQ]

1. Devin suggested a fantastic idea: it may be great to have a new LocationContext for whatever happens within the big-new-expression. This would help immensely with CFG look-aheads and look-behinds and reduce parent map usage - not only for operator new, but for other constructors (into initializer lists, probably into function arguments). Let's call it ConstructionTriggerContext for now. We can also store our "_this" value in a program state map from ConstructionTriggerContext into SVal.

2. My reaction was that we can instead store our "_this" value in some sort of "CXX_ThisRegion" within the StackLocalsSpaceRegion that corresponds to ConstructionTriggerContext, and then copy it over to CXXThisRegion that corresponds to the StackFrameContext of the constructor. This would kinda make sense given the pseudocode that we're imagine here for the new-expression. However, this sounds a bit over-engineered because we're using the Store to just temporarily stash the value. Well, right now we're using Environment for that, but it's equally dirty.

3. Now, it might actually be better to store "_this" value directly into CXXThisRegion that corresponds to the StackFrameContext of the constructor (rather than stash it in another place and eventually copy), even if that stack frame has not been entered yet. Because the stack frame would anyway be entered almost immediately, we already know the parameters of the stack frame (parent location context, call site, block count, block id, element id), and location contexts are uniqued, so we can add the store binding now to the stack frame of the future, and whenever we actually enter the stack frame, when formerly we'd have bound the value to CXXThisRegion, we'd see that the value is already there. In this case we don't immediately need ConstructionTriggerContext - we can still add it later to refactor look-aheads and stuff. The binding would anyway be garbage-collected once the constructor exits.

I'd be glad to implement approach 3. instead of the stack of values if it sounds reasonable.

[NoQ]

A slower explanation of the approach in '3.' in the previous message:

(1) Evaluate operator new() aka the allocator call as usual.
(2) Take the return value of (1) as usual.
(3) Take CXXConstructExpr which is the child of the CXXNewExpr that triggered the allocator call on (1).
(4) Construct a StackFrameContext with CXXConstructExpr from (3).
(5) Don't put the newly constructed StackFrameContext on the location context stack.
(6) Construct the StackArgumentsSpaceRegion for the StackFrameContext from (4).
(7) Construct the CXXThisRegion for the StackArgumentsSpaceRegion from (6).
(8) Bind the return value from (2) to CXXThisRegion from (7) in the Store.
(9) Put the node with the state from (8) to the worklist as usual.
(10) CoreEngine says it's time to evaluate CXXConstructExpr from (3) as usual.
(11) Make sure that the binding we made in (8) survives garbage collection*.
(11) Construct StackFrameContext for the CXXConstructExpr from (3) as usual.
(12) LocationContextManager ensures that on (4) and on (11) we get the same StackFrameContext.
(13) Don't bind CXXThisRegion while entering the stack frame - it was already done in (8).
(14) Finally enter the stack frame we've constructed twice on (4) and on (11), as usual.
(15) Evaluate the constructor, as usual.
(16) Bind this-value to CXXConstructExpr after evaluation (as usual? not sure).
(17) Allow the binding in the Store we made on (8) to be garbage-colllected as usual.
(18) When evaluating CXXNewExpr, take value of CXXConstructExpr and bind it to CXXNewExpr.

__
*We may modify SymbolReaper::isLiveRegion() for this purpose. Sounds easy.

[NoQ]

That thing didn't immediately work, because there are a lot of other places where we need to put the value, not just the Store, before entering the constructor - such as our constructor call events for checker callbacks. It'd be hard for the call event to extract the target region by looking at their caller stack frame and program state, and perhaps they shouldn't be doing this, and it's actually fine that they receive the target region directly, because if we want to reconstruct the call event after the fact, we'd anyway be able to do this only from within the constructor call, because later the value would disappear from the program state anyway.

The idea with the new location context class still stands. For now i made a simple map from (CallerStackFrameContext, CXXNewExpr) pairs to SVal. This map can be trivially refactored into a map from OurNewLocationContext to SVal, because CallerStackFrame would be its parent context, and CXXNewExpr would be its parameter. Note that it's not possible to use only CallerStackFrameContext as the key because multiple CXXNewExprs might be active simultaneously, eg. new X(new Y()) - respective test case added. But with CXXNewExpr as part of the key, the key is indeed unique in the sense that by the time we encounter the same CXXNewExpr again we'd be done with the old CXXNewExpr - respective assertion added. With these assertions i guess it's more reliable than the stack approach.

I think i'm getting done with these patches, so they can be treated as in sort of final shape, i.e. i have no planned changes for these myself anymore (but i'd definitely gladly address any review comments).

[NoQ]

Rename getters and setters for the new state trait (i.e. "push" -> "set", etc., because we no longer have a stack).

Also make them static, so that it was potentially possible to access them from elsewhere, eg. from CallEvent, if deemed necessary.

[NoQ]

Add a stronger assertion: when ending an inlined call, assert that no stale allocator values remain.

[dcoughlin]

LGTM with the TODO and the test case I requested inline.

lib/StaticAnalyzer/Core/ExprEngine.cpp

487 ↗

(On Diff #129552)

Do we have a test for the MemRegion case? Commenting it out doesn't seem to affect the tests.

lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

607 ↗

(On Diff #127437)

Can you add a TODO saying that we really shouldn't be using the parent map here? That is fragile and is a sign we're not providing enough context.

[NoQ]

Address the final comments.

lib/StaticAnalyzer/Core/ExprEngine.cpp

487 ↗

(On Diff #129552)

Right, added one (new-ctor-symbolic.cpp).

[NoQ]

Remove pointer casts from the newly added symbolic index test, because once we properly perform the cast of the allocated value (as in D41250), our solver would blow up.

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

private:
   /// For a DeclStmt or CXXInitCtorInitializer, walk backward in the current CFG
   /// block to find the constructor expression that directly constructed into
   /// the storage for this statement. Returns null if the constructor for this
   /// statement created a temporary object region rather than directly
   /// constructing into an existing region.
   const CXXConstructExpr *findDirectConstructorForCurrentCFGElement();
 
   /// For a CXXConstructExpr, walk forward in the current CFG block to find the
-  /// CFGElement for the DeclStmt or CXXInitCtorInitializer for which is
-  /// directly constructed by this constructor. Returns None if the current
+  /// CFGElement for the DeclStmt or CXXInitCtorInitializer or CXXNewExpr which
+  /// is directly constructed by this constructor. Returns None if the current
   /// constructor expression did not directly construct into an existing
   /// region.
   Optional<CFGElement> findElementDirectlyInitializedByCurrentConstructor();
 
   /// For a given constructor, look forward in the current CFG block to
   /// determine the region into which an object will be constructed by \p CE.
   /// Returns either a field or local variable region if the object will be
   /// directly constructed in an existing region or a temporary object region
   /// if not.
   const MemRegion *getRegionForConstructedObject(const CXXConstructExpr *CE,
                                                  ExplodedNode *Pred);
+
+  /// Store the region returned by operator new() so that the constructor
+  /// that follows it knew what location to initialize. The value should be
+  /// cleared once the respective CXXNewExpr CFGStmt element is processed.
+  static ProgramStateRef
+  setCXXNewAllocatorValue(ProgramStateRef State, const CXXNewExpr *CNE,
+                          const LocationContext *CallerLC, SVal V);
+
+  /// Retrieve the location returned by the current operator new().
+  static SVal
+  getCXXNewAllocatorValue(ProgramStateRef State, const CXXNewExpr *CNE,
+                          const LocationContext *CallerLC);
+
+  /// Clear the location returned by the respective operator new(). This needs
+  /// to be done as soon as CXXNewExpr CFG block is evaluated.
+  static ProgramStateRef
+  clearCXXNewAllocatorValue(ProgramStateRef State, const CXXNewExpr *CNE,
+                            const LocationContext *CallerLC);
+
+  /// Check if all allocator values are clear for the given context range
+  /// (including FromLC, not including ToLC). This is useful for assertions.
+  static bool areCXXNewAllocatorValuesClear(ProgramStateRef State,
+                                            const LocationContext *FromLC,
+                                            const LocationContext *ToLC);
 };
 
 /// Traits for storing the call processing policy inside GDM.
 /// The GDM stores the corresponding CallExpr pointer.
 // FIXME: This does not use the nice trait macros because it must be accessible
 // from multiple translation units.
 struct ReplayWithoutInlining{};
 template <>

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

typedef std::pair<const CXXBindTemporaryExpr *, const StackFrameContext *>
     CXXBindTemporaryContext;
 
 // Keeps track of whether CXXBindTemporaryExpr nodes have been evaluated.
 // The StackFrameContext assures that nested calls due to inlined recursive
 // functions do not interfere.
 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedTemporariesSet,
                                  llvm::ImmutableSet<CXXBindTemporaryContext>)
 
+typedef llvm::ImmutableMap<std::pair<const CXXNewExpr *,
+                           const LocationContext *>, SVal>
+    CXXNewAllocatorValuesTy;
+
+// Keeps track of return values of various operator new() calls between
+// evaluation of the inlined operator new(), through the constructor call,
+// to the actual evaluation of the CXXNewExpr.
+// TODO: Refactor the key for this trait into a LocationContext sub-class,
+// which would be put on the stack of location contexts before operator new()
+// is evaluated, and removed from the stack when the whole CXXNewExpr
+// is fully evaluated.
+// Probably do something similar to the previous trait as well.
+REGISTER_TRAIT_WITH_PROGRAMSTATE(CXXNewAllocatorValues, CXXNewAllocatorValuesTy)
+
 //===----------------------------------------------------------------------===//
 // Engine construction and deletion.
 //===----------------------------------------------------------------------===//
 
 static const char* TagProviderName = "ExprEngine";
 
 ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled,
                        SetOfConstDecls *VisitedCalleesIn,
ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State,
   State = State->BindExpr(Result, LC, Reg);
 
   // Notify checkers once for two bindLoc()s.
   State = processRegionChange(State, TR, LC);
 
   return State;
 }
 
+ProgramStateRef
+ExprEngine::setCXXNewAllocatorValue(ProgramStateRef State,
+                                    const CXXNewExpr *CNE,
+                                    const LocationContext *CallerLC, SVal V) {
+  assert(!State->get<CXXNewAllocatorValues>(std::make_pair(CNE, CallerLC)) &&
+         "Allocator value already set!");
+  return State->set<CXXNewAllocatorValues>(std::make_pair(CNE, CallerLC), V);
+}
+
+SVal ExprEngine::getCXXNewAllocatorValue(ProgramStateRef State,
+                                         const CXXNewExpr *CNE,
+                                         const LocationContext *CallerLC) {
+  return *State->get<CXXNewAllocatorValues>(std::make_pair(CNE, CallerLC));
+}
+
+ProgramStateRef
+ExprEngine::clearCXXNewAllocatorValue(ProgramStateRef State,
+                                      const CXXNewExpr *CNE,
+                                      const LocationContext *CallerLC) {
+  return State->remove<CXXNewAllocatorValues>(std::make_pair(CNE, CallerLC));
+}
+
+bool ExprEngine::areCXXNewAllocatorValuesClear(ProgramStateRef State,
+                                               const LocationContext *FromLC,
+                                               const LocationContext *ToLC) {
+  const LocationContext *LC = FromLC;
+  do {
+    for (auto I : State->get<CXXNewAllocatorValues>())
+      if (I.first.second == LC)
+        return false;
+
+    LC = LC->getParent();
+    assert(LC && "ToLC must be a parent of FromLC!");
+  } while (LC != ToLC);
+  return true;
+}
+
 //===----------------------------------------------------------------------===//
 // Top-level transfer function logic (Dispatcher).
 //===----------------------------------------------------------------------===//
 
 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
 ///  logic for handling assumptions on symbolic values.
 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
                                               SVal cond, bool assumption) {
if (!ReferenceStmt) {
     assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
            "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
     LC = LC->getParent();
   }
 
   const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : nullptr;
   SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
 
+  for (auto I : CleanedState->get<CXXNewAllocatorValues>()) {
+    if (SymbolRef Sym = I.second.getAsSymbol())
+      SymReaper.markLive(Sym);
+    if (const MemRegion *MR = I.second.getAsRegion())
+      SymReaper.markElementIndicesLive(MR);
+  }
+
   getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
 
   // Create a state in which dead bindings are removed from the environment
   // and the store. TODO: The function should just return new env and store,
   // not a new state.
   CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
 
   // Process any special transfer function for dead symbols.

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

ExprEngine::getRegionForConstructedObject(const CXXConstructExpr *CE,
   const LocationContext *LCtx = Pred->getLocationContext();
   ProgramStateRef State = Pred->getState();
 
   // See if we're constructing an existing region by looking at the next
   // element in the CFG.
 
   if (auto Elem = findElementDirectlyInitializedByCurrentConstructor()) {
     if (Optional<CFGStmt> StmtElem = Elem->getAs<CFGStmt>()) {
-      auto *DS = cast<DeclStmt>(StmtElem->getStmt());
+      if (const CXXNewExpr *CNE = dyn_cast<CXXNewExpr>(StmtElem->getStmt())) {
+        if (AMgr.getAnalyzerOptions().mayInlineCXXAllocator()) {
+          // TODO: Detect when the allocator returns a null pointer.
+          // Constructor shall not be called in this case.
+          if (const MemRegion *MR =
+                  getCXXNewAllocatorValue(State, CNE, LCtx).getAsRegion())
+            return MR;
+        }
+      } else if (auto *DS = dyn_cast<DeclStmt>(StmtElem->getStmt())) {
         if (const auto *Var = dyn_cast<VarDecl>(DS->getSingleDecl())) {
           if (Var->getInit() && Var->getInit()->IgnoreImplicit() == CE) {
             SVal LValue = State->getLValue(Var, LCtx);
             QualType Ty = Var->getType();
             LValue = makeZeroElementRegion(State, LValue, Ty);
             return LValue.getAsRegion();
           }
         }
+      } else {
+        llvm_unreachable("Unexpected directly initialized element!");
+      }
     } else if (Optional<CFGInitializer> InitElem = Elem->getAs<CFGInitializer>()) {
       const CXXCtorInitializer *Init = InitElem->getInitializer();
       assert(Init->isAnyMemberInitializer());
       const CXXMethodDecl *CurCtor = cast<CXXMethodDecl>(LCtx->getDecl());
       Loc ThisPtr =
       getSValBuilder().getCXXThis(CurCtor, LCtx->getCurrentStackFrame());
       SVal ThisVal = State->getSVal(ThisPtr);
 

 /// constructor.
 static bool canHaveDirectConstructor(CFGElement Elem){
   // DeclStmts and CXXCtorInitializers for fields can be directly constructed.
 
   if (Optional<CFGStmt> StmtElem = Elem.getAs<CFGStmt>()) {
     if (isa<DeclStmt>(StmtElem->getStmt())) {
       return true;
     }
+    if (isa<CXXNewExpr>(StmtElem->getStmt())) {
+      return true;
+    }
   }
 
   if (Elem.getKind() == CFGElement::Initializer) {
     return true;
   }
 
   return false;
 }
void ExprEngine::VisitCXXNewAllocatorCall(const CXXNewExpr *CNE,
   CallEventManager &CEMgr = getStateManager().getCallEventManager();
   CallEventRef<CXXAllocatorCall> Call =
     CEMgr.getCXXAllocatorCall(CNE, State, LCtx);
 
   ExplodedNodeSet DstPreCall;
   getCheckerManager().runCheckersForPreCall(DstPreCall, Pred,
                                             *Call, *this);
 
-  ExplodedNodeSet DstInvalidated;
-  StmtNodeBuilder Bldr(DstPreCall, DstInvalidated, *currBldrCtx);
-  for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
-       I != E; ++I)
-    defaultEvalCall(Bldr, *I, *Call);
-  getCheckerManager().runCheckersForPostCall(Dst, DstInvalidated,
+  ExplodedNodeSet DstPostCall;
+  StmtNodeBuilder CallBldr(DstPreCall, DstPostCall, *currBldrCtx);
+  for (auto I : DstPreCall)
+    defaultEvalCall(CallBldr, I, *Call);
+
+  // Store return value of operator new() for future use, until the actual
+  // CXXNewExpr gets processed.
+  ExplodedNodeSet DstPostValue;
+  StmtNodeBuilder ValueBldr(DstPostCall, DstPostValue, *currBldrCtx);
+  for (auto I : DstPostCall) {
+    ProgramStateRef State = I->getState();
+    ValueBldr.generateNode(
+        CNE, I,
+        setCXXNewAllocatorValue(State, CNE, LCtx, State->getSVal(CNE, LCtx)));
+  }
+
+  getCheckerManager().runCheckersForPostCall(Dst, DstPostValue,
                                              *Call, *this);
 }
 
 
 void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
                                    ExplodedNodeSet &Dst) {
   // FIXME: Much of this should eventually migrate to CXXAllocatorCall.
   // Also, we need to decide how allocators actually work -- they're not
   // really part of the CXXNewExpr because they happen BEFORE the
   // CXXConstructExpr subexpression. See PR12014 for some discussion.
 
   unsigned blockCount = currBldrCtx->blockCount();
   const LocationContext *LCtx = Pred->getLocationContext();
-  DefinedOrUnknownSVal symVal = UnknownVal();
+  SVal symVal = UnknownVal();
   FunctionDecl *FD = CNE->getOperatorNew();
 
   bool IsStandardGlobalOpNewFunction = false;
   if (FD && !isa<CXXMethodDecl>(FD) && !FD->isVariadic()) {
     if (FD->getNumParams() == 2) {
       QualType T = FD->getParamDecl(1)->getType();
       if (const IdentifierInfo *II = T.getBaseTypeIdentifier())
         // NoThrow placement new behaves as a standard new.
         IsStandardGlobalOpNewFunction = II->getName().equals("nothrow_t");
     }
     else
       // Placement forms are considered non-standard.
       IsStandardGlobalOpNewFunction = (FD->getNumParams() == 1);
   }
 
+  ProgramStateRef State = Pred->getState();
+
+  // Retrieve the stored operator new() return value.
+  if (AMgr.getAnalyzerOptions().mayInlineCXXAllocator()) {
+    symVal = getCXXNewAllocatorValue(State, CNE, LCtx);
+    State = clearCXXNewAllocatorValue(State, CNE, LCtx);
+  }
+
   // We assume all standard global 'operator new' functions allocate memory in
   // heap. We realize this is an approximation that might not correctly model
   // a custom global allocator.
+  if (symVal.isUnknown()) {
     if (IsStandardGlobalOpNewFunction)
       symVal = svalBuilder.getConjuredHeapSymbolVal(CNE, LCtx, blockCount);
     else
       symVal = svalBuilder.conjureSymbolVal(nullptr, CNE, LCtx, CNE->getType(),
                                             blockCount);
+  }
 
-  ProgramStateRef State = Pred->getState();
   CallEventManager &CEMgr = getStateManager().getCallEventManager();
   CallEventRef<CXXAllocatorCall> Call =
     CEMgr.getCXXAllocatorCall(CNE, State, LCtx);
 
+  if (!AMgr.getAnalyzerOptions().mayInlineCXXAllocator()) {
     // Invalidate placement args.
     // FIXME: Once we figure out how we want allocators to work,
     // we should be using the usual pre-/(default-)eval-/post-call checks here.
     State = Call->invalidateRegions(blockCount);
     if (!State)
       return;
+  }
 
   // If this allocation function is not declared as non-throwing, failures
   // /must/ be signalled by exceptions, and thus the return value will never be
   // NULL. -fno-exceptions does not influence this semantics.
   // FIXME: GCC has a -fcheck-new option, which forces it to consider the case
   // where new can return NULL. If we end up supporting that option, we can
   // consider adding a check for it here.
   // C++11 [basic.stc.dynamic.allocation]p3.
   if (FD) {
     QualType Ty = FD->getType();
     if (const FunctionProtoType *ProtoType = Ty->getAs<FunctionProtoType>())
       if (!ProtoType->isNothrow(getContext()))
-        State = State->assume(symVal, true);
+        if (auto dSymVal = symVal.getAs<DefinedOrUnknownSVal>())
+          State = State->assume(*dSymVal, true);
   }
 
   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
 
   if (CNE->isArray()) {
     // FIXME: allocating an array requires simulating the constructors.
     // For now, just return a symbolicated region.
     const SubRegion *NewReg =

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

if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
       SVal ThisV = state->getSVal(This);
 
       // If the constructed object is a temporary prvalue, get its bindings.
       if (isTemporaryPRValue(CCE, ThisV))
         ThisV = state->getSVal(ThisV.castAs<Loc>());
 
       state = state->BindExpr(CCE, callerCtx, ThisV);
     }
+
+    if (const CXXNewExpr *CNE = dyn_cast<CXXNewExpr>(CE)) {
+      // We are currently evaluating a CXXNewAllocator CFGElement. It takes a
+      // while to reach the actual CXXNewExpr element from here, so keep the
+      // region for later use.
+      state = setCXXNewAllocatorValue(state, CNE, calleeCtx->getParent(),
+                                      state->getSVal(CE, callerCtx));
+    }
   }
 
   // Step 3: BindedRetNode -> CleanedNodes
   // If we can find a statement and a block in the inlined function, run remove
   // dead bindings before returning from the call. This is important to ensure
   // that we report the issues such as leaks in the stack contexts in which
   // they occurred.
   ExplodedNodeSet CleanedNodes;
void ExprEngine::processCallExit(ExplodedNode *CEBNode) {
   for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
                                  E = CleanedNodes.end(); I != E; ++I) {
 
     // Step 4: Generate the CallExit and leave the callee's context.
     // CleanedNodes -> CEENode
     CallExitEnd Loc(calleeCtx, callerCtx);
     bool isNew;
     ProgramStateRef CEEState = (*I == CEBNode) ? state : (*I)->getState();
+
+    // See if we have any stale C++ allocator values.
+    assert(areCXXNewAllocatorValuesClear(CEEState, calleeCtx, callerCtx));
+
     ExplodedNode *CEENode = G.getNode(Loc, CEEState, false, &isNew);
     CEENode->addPredecessor(*I, G);
     if (!isNew)
       return;
 
     // Step 5: Perform the post-condition check of the CallExpr and enqueue the
     // result onto the work list.
     // CEENode -> Dst -> WorkList
if (!Opts.mayInlineCXXMemberFunction(CIMK_MemberFunctions))
       return CIP_DisallowedAlways;
     break;
   case CE_CXXConstructor: {
     if (!Opts.mayInlineCXXMemberFunction(CIMK_Constructors))
       return CIP_DisallowedAlways;
 
     const CXXConstructorCall &Ctor = cast<CXXConstructorCall>(Call);
 
+    const CXXConstructExpr *CtorExpr = Ctor.getOriginExpr();
+
+    // FIXME: ParentMap is slow and ugly. The callee should provide the
+    // necessary context. Ideally as part of the call event, or maybe as part of
+    // location context.
+    const Stmt *ParentExpr = CurLC->getParentMap().getParent(CtorExpr);
+
+    if (ParentExpr && isa<CXXNewExpr>(ParentExpr) &&
+        !Opts.mayInlineCXXAllocator())
+      return CIP_DisallowedOnce;
+
     // FIXME: We don't handle constructors or destructors for arrays properly.
     // Even once we do, we still need to be careful about implicitly-generated
     // initializers for array fields in default move/copy constructors.
+    // We still allow construction into ElementRegion targets when they don't
+    // represent array elements.
     const MemRegion *Target = Ctor.getCXXThisVal().getAsRegion();
-    if (Target && isa<ElementRegion>(Target))
+    if (Target && isa<ElementRegion>(Target)) {
+      if (ParentExpr)
+        if (const CXXNewExpr *NewExpr = dyn_cast<CXXNewExpr>(ParentExpr))
+          if (NewExpr->isArray())
             return CIP_DisallowedOnce;
 
-    // FIXME: This is a hack. We don't use the correct region for a new
-    // expression, so if we inline the constructor its result will just be
-    // thrown away. This short-term hack is tracked in <rdar://problem/12180598>
-    // and the longer-term possible fix is discussed in PR12014.
-    const CXXConstructExpr *CtorExpr = Ctor.getOriginExpr();
-    if (const Stmt *Parent = CurLC->getParentMap().getParent(CtorExpr))
-      if (isa<CXXNewExpr>(Parent))
+      if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(
+              cast<SubRegion>(Target)->getSuperRegion()))
+        if (TR->getValueType()->isArrayType())
           return CIP_DisallowedOnce;
+    }
 
     // Inlining constructors requires including initializers in the CFG.
     const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext();
     assert(ADC->getCFGBuildOptions().AddInitializers && "No CFG initializers");
     (void)ADC;
 
     // If the destructor is trivial, it's always safe to inline the constructor.
     if (Ctor.getDecl()->getParent()->hasTrivialDestructor())
       break;
 
     // For other types, only inline constructors if destructor inlining is
     // also enabled.
     if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
       return CIP_DisallowedAlways;
 
     // FIXME: This is a hack. We don't handle temporary destructors
     // right now, so we shouldn't inline their constructors.
     if (CtorExpr->getConstructionKind() == CXXConstructExpr::CK_Complete)
-      if (!Target || !isa<DeclRegion>(Target))
+      if (!Target || isa<CXXTempObjectRegion>(Target))
         return CIP_DisallowedOnce;
 
     break;
   }
   case CE_CXXDestructor: {
     if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
       return CIP_DisallowedAlways;
 

cfe/trunk/test/Analysis/inline.cpp

 }
 
 namespace OperatorNew {
   class IntWrapper {
   public:
     int value;
 
     IntWrapper(int input) : value(input) {
-      // We don't want this constructor to be inlined unless we can actually
-      // use the proper region for operator new.
-      // See PR12014 and <rdar://problem/12180598>.
-      clang_analyzer_checkInlined(false); // no-warning
+      clang_analyzer_checkInlined(true); // expected-warning{{TRUE}}
     }
   };
 
   void test() {
     IntWrapper *obj = new IntWrapper(42);
-    // should be TRUE
-    clang_analyzer_eval(obj->value == 42); // expected-warning{{UNKNOWN}}
+    clang_analyzer_eval(obj->value == 42); // expected-warning{{TRUE}}
     delete obj;
   }
 
   void testPlacement() {
     IntWrapper *obj = static_cast<IntWrapper *>(malloc(sizeof(IntWrapper)));
     IntWrapper *alias = new (obj) IntWrapper(42);
 
     clang_analyzer_eval(alias == obj); // expected-warning{{TRUE}}
 
-    // should be TRUE
-    clang_analyzer_eval(obj->value == 42); // expected-warning{{UNKNOWN}}
+    clang_analyzer_eval(obj->value == 42); // expected-warning{{TRUE}}
+    // Because malloc() was never free()d:
+    // expected-warning@-2{{Potential leak of memory pointed to by 'alias'}}
   }
 }
 
 
 namespace VirtualWithSisterCasts {
   // This entire set of tests exercises casts from sister classes and
   // from classes outside the hierarchy, which can very much confuse
   // code that uses DynamicTypeInfo or needs to construct CXXBaseObjectRegions.

cfe/trunk/test/Analysis/new-ctor-conservative.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config c++-allocator-inlining=true -std=c++11 -verify %s
+
+void clang_analyzer_eval(bool);
+
+struct S {
+  int x;
+  S() : x(1) {}
+  ~S() {}
+};
+
+void checkConstructorInlining() {
+  S *s = new S;
+  clang_analyzer_eval(s->x == 1); // expected-warning{{TRUE}}
+}

cfe/trunk/test/Analysis/new-ctor-inlined.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config c++-allocator-inlining=true -std=c++11 -verify %s
+
+void clang_analyzer_eval(bool);
+
+typedef __typeof__(sizeof(int)) size_t;
+
+void *conjure();
+void exit(int);
+
+void *operator new(size_t size) throw() {
+  void *x = conjure();
+  if (x == 0)
+    exit(1);
+  return x;
+}
+
+struct S {
+  int x;
+  S() : x(1) {}
+  ~S() {}
+};
+
+void checkNewAndConstructorInlining() {
+  S *s = new S;
+  // Check that the symbol for 's' is not dying.
+  clang_analyzer_eval(s != 0); // expected-warning{{TRUE}}
+  // Check that bindings are correct (and also not dying).
+  clang_analyzer_eval(s->x == 1); // expected-warning{{TRUE}}
+}
+
+struct Sp {
+  Sp *p;
+  Sp(Sp *p): p(p) {}
+  ~Sp() {}
+};
+
+void checkNestedNew() {
+  Sp *p = new Sp(new Sp(0));
+  clang_analyzer_eval(p->p->p == 0); // expected-warning{{TRUE}}
+}

cfe/trunk/test/Analysis/new-ctor-recursive.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus.NewDelete,cplusplus.NewDeleteLeaks,debug.ExprInspection -analyzer-config c++-allocator-inlining=true -std=c++11 -verify %s
+
+void clang_analyzer_eval(bool);
+void clang_analyzer_dump(int);
+
+typedef __typeof__(sizeof(int)) size_t;
+
+void *conjure();
+void exit(int);
+
+struct S;
+
+S *global_s;
+
+// Recursive operator kinda placement new.
+void *operator new(size_t size, S *place);
+
+enum class ConstructionKind : char {
+  Garbage,
+  Recursive
+};
+
+struct S {
+public:
+  int x;
+  S(): x(1) {}
+  S(int y): x(y) {}
+
+  S(ConstructionKind k) {
+    switch (k) {
+    case ConstructionKind::Recursive: { // Call one more operator new 'r'ecursively.
+      S *s = new (nullptr) S(5);
+      x = s->x + 1;
+      global_s = s;
+      return;
+    }
+    case ConstructionKind::Garbage: {
+      // Leaves garbage in 'x'.
+    }
+    }
+  }
+  ~S() {}
+};
+
+// Do not try this at home!
+void *operator new(size_t size, S *place) {
+  if (!place)
+    return new S();
+  return place;
+}
+
+void testThatCharConstructorIndeedYieldsGarbage() {
+  S *s = new S(ConstructionKind::Garbage);
+  clang_analyzer_eval(s->x == 0); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(s->x == 1); // expected-warning{{UNKNOWN}}
+  // FIXME: This should warn, but MallocChecker doesn't default-bind regions
+  // returned by standard operator new to garbage.
+  s->x += 1; // no-warning
+  delete s;
+}
+
+
+void testChainedOperatorNew() {
+  S *s;
+  // * Evaluate standard new.
+  // * Evaluate constructor S(3).
+  // * Bind value for standard new.
+  // * Evaluate our custom new.
+  // * Evaluate constructor S(Garbage).
+  // * Bind value for our custom new.
+  s = new (new S(3)) S(ConstructionKind::Garbage);
+  clang_analyzer_eval(s->x == 3); // expected-warning{{TRUE}}
+  // expected-warning@+9{{Potential leak of memory pointed to by 's'}}
+
+  // * Evaluate standard new.
+  // * Evaluate constructor S(Garbage).
+  // * Bind value for standard new.
+  // * Evaluate our custom new.
+  // * Evaluate constructor S(4).
+  // * Bind value for our custom new.
+  s = new (new S(ConstructionKind::Garbage)) S(4);
+  clang_analyzer_eval(s->x == 4); // expected-warning{{TRUE}}
+  delete s;
+
+  // -> Enter our custom new (nullptr).
+  //   * Evaluate standard new.
+  //   * Inline constructor S().
+  //   * Bind value for standard new.
+  // <- Exit our custom new (nullptr).
+  // * Evaluate constructor S(Garbage).
+  // * Bind value for our custom new.
+  s = new (nullptr) S(ConstructionKind::Garbage);
+  clang_analyzer_eval(s->x == 1); // expected-warning{{TRUE}}
+  delete s;
+
+  // -> Enter our custom new (nullptr).
+  //   * Evaluate standard new.
+  //   * Inline constructor S().
+  //   * Bind value for standard new.
+  // <- Exit our custom new (nullptr).
+  // -> Enter constructor S(Recursive).
+  //   -> Enter our custom new (nullptr).
+  //     * Evaluate standard new.
+  //     * Inline constructor S().
+  //     * Bind value for standard new.
+  //   <- Exit our custom new (nullptr).
+  //   * Evaluate constructor S(5).
+  //   * Bind value for our custom new (nullptr).
+  //   * Assign that value to global_s.
+  // <- Exit constructor S(Recursive).
+  // * Bind value for our custom new (nullptr).
+  global_s = nullptr;
+  s = new (nullptr) S(ConstructionKind::Recursive);
+  clang_analyzer_eval(global_s); // expected-warning{{TRUE}}
+  clang_analyzer_eval(global_s->x == 5); // expected-warning{{TRUE}}
+  clang_analyzer_eval(s->x == 6); // expected-warning{{TRUE}}
+  delete s;
+}

cfe/trunk/test/Analysis/new-ctor-symbolic.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config c++-allocator-inlining=true -std=c++11 -verify %s
+
+void clang_analyzer_eval(bool);
+void clang_analyzer_warnOnDeadSymbol(int);
+
+typedef __typeof__(sizeof(int)) size_t;
+
+int conjure();
+void exit(int);
+
+struct S {
+  S() {}
+  ~S() {}
+
+  static S buffer[1000];
+
+  // This operator allocates stuff within the buffer. Additionally, it never
+  // places anything at the beginning of the buffer.
+  void *operator new(size_t size) {
+    int i = conjure();
+    if (i == 0)
+      exit(1);
+    // Let's see if the symbol dies before new-expression is evaluated.
+    // It shouldn't.
+    clang_analyzer_warnOnDeadSymbol(i);
+    return buffer + i;
+  }
+};
+
+void testIndexLiveness() {
+  S *s = new S();
+  clang_analyzer_eval(s == S::buffer); // expected-warning{{FALSE}}
+} // expected-warning{{SYMBOL DEAD}}