[analyzer] Add support for pre-C++17 copy elision.

r335795 adds copy elision information to CFG. This commit allows static analyzer
to elide elidable copy constructors by constructing the objects that were
previously subject to elidable copy directly in the target region of the copy.

The chain of elided constructors may potentially be indefinitely long. This
only happens when the object is being returned from a function which in turn is
returned from another function, etc.

NRVO is not supported yet.

Differential Revision: https://reviews.llvm.org/D47671

llvm-svn: 335800

2 files changed, 150 insertions, 43 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 54139c229df..c3f5b42a9f6 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -139,7 +139,8 @@ public:
     // encountered. This list may be expanded when new actions are implemented.
     assert(getCXXCtorInitializer() || isa<DeclStmt>(getStmt()) ||
            isa<CXXNewExpr>(getStmt()) || isa<CXXBindTemporaryExpr>(getStmt()) ||
-           isa<MaterializeTemporaryExpr>(getStmt()));
+           isa<MaterializeTemporaryExpr>(getStmt()) ||
+           isa<CXXConstructExpr>(getStmt()));
   }
 
   const Stmt *getStmt() const {
@@ -183,6 +184,14 @@ typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
 REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,
                                  ObjectsUnderConstructionMap)
 
+// Additionally, track a set of destructors that correspond to elided
+// constructors when copy elision occurs.
+typedef std::pair<const CXXBindTemporaryExpr *, const LocationContext *>
+    ElidedDestructorItem;
+typedef llvm::ImmutableSet<ElidedDestructorItem>
+    ElidedDestructorSet;
+REGISTER_TRAIT_WITH_PROGRAMSTATE(ElidedDestructors,
+                                 ElidedDestructorSet);
 
 //===----------------------------------------------------------------------===//
 // Engine construction and deletion.
@@ -358,14 +367,12 @@ ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State,
   // a new temporary region out of thin air and copy the contents of the object
   // (which are currently present in the Environment, because Init is an rvalue)
   // into that region. This is not correct, but it is better than nothing.
-  bool FoundOriginalMaterializationRegion = false;
   const TypedValueRegion *TR = nullptr;
   if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) {
     if (Optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) {
-      FoundOriginalMaterializationRegion = true;
-      TR = cast<CXXTempObjectRegion>(V->getAsRegion());
-      assert(TR);
       State = finishObjectConstruction(State, MT, LC);
+      State = State->BindExpr(Result, LC, *V);
+      return State;
     } else {
       StorageDuration SD = MT->getStorageDuration();
       // If this object is bound to a reference with static storage duration, we
@@ -402,35 +409,33 @@ ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State,
     }
   }
 
-  if (!FoundOriginalMaterializationRegion) {
-    // What remains is to copy the value of the object to the new region.
-    // FIXME: In other words, what we should always do is copy value of the
-    // Init expression (which corresponds to the bigger object) to the whole
-    // temporary region TR. However, this value is often no longer present
-    // in the Environment. If it has disappeared, we instead invalidate TR.
-    // Still, what we can do is assign the value of expression Ex (which
-    // corresponds to the sub-object) to the TR's sub-region Reg. At least,
-    // values inside Reg would be correct.
-    SVal InitVal = State->getSVal(Init, LC);
-    if (InitVal.isUnknown()) {
-      InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(),
-                                                  currBldrCtx->blockCount());
-      State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
-
-      // Then we'd need to take the value that certainly exists and bind it
-      // over.
-      if (InitValWithAdjustments.isUnknown()) {
-        // Try to recover some path sensitivity in case we couldn't
-        // compute the value.
-        InitValWithAdjustments = getSValBuilder().conjureSymbolVal(
-            Result, LC, InitWithAdjustments->getType(),
-            currBldrCtx->blockCount());
-      }
-      State =
-          State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false);
-    } else {
-      State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
+  // What remains is to copy the value of the object to the new region.
+  // FIXME: In other words, what we should always do is copy value of the
+  // Init expression (which corresponds to the bigger object) to the whole
+  // temporary region TR. However, this value is often no longer present
+  // in the Environment. If it has disappeared, we instead invalidate TR.
+  // Still, what we can do is assign the value of expression Ex (which
+  // corresponds to the sub-object) to the TR's sub-region Reg. At least,
+  // values inside Reg would be correct.
+  SVal InitVal = State->getSVal(Init, LC);
+  if (InitVal.isUnknown()) {
+    InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(),
+                                                currBldrCtx->blockCount());
+    State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
+
+    // Then we'd need to take the value that certainly exists and bind it
+    // over.
+    if (InitValWithAdjustments.isUnknown()) {
+      // Try to recover some path sensitivity in case we couldn't
+      // compute the value.
+      InitValWithAdjustments = getSValBuilder().conjureSymbolVal(
+          Result, LC, InitWithAdjustments->getType(),
+          currBldrCtx->blockCount());
     }
+    State =
+        State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false);
+  } else {
+    State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
   }
 
   // The result expression would now point to the correct sub-region of the
@@ -438,10 +443,8 @@ ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State,
   // correctly in case (Result == Init).
   State = State->BindExpr(Result, LC, Reg);
 
-  if (!FoundOriginalMaterializationRegion) {
-    // Notify checkers once for two bindLoc()s.
-    State = processRegionChange(State, TR, LC);
-  }
+  // Notify checkers once for two bindLoc()s.
+  State = processRegionChange(State, TR, LC);
 
   return State;
 }
@@ -475,6 +478,30 @@ ProgramStateRef ExprEngine::finishObjectConstruction(
   return State->remove<ObjectsUnderConstruction>(Key);
 }
 
+ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State,
+                                            const CXXBindTemporaryExpr *BTE,
+                                            const LocationContext *LC) {
+  ElidedDestructorItem I(BTE, LC);
+  assert(!State->contains<ElidedDestructors>(I));
+  return State->add<ElidedDestructors>(I);
+}
+
+ProgramStateRef
+ExprEngine::cleanupElidedDestructor(ProgramStateRef State,
+                                    const CXXBindTemporaryExpr *BTE,
+                                    const LocationContext *LC) {
+  ElidedDestructorItem I(BTE, LC);
+  assert(State->contains<ElidedDestructors>(I));
+  return State->remove<ElidedDestructors>(I);
+}
+
+bool ExprEngine::isDestructorElided(ProgramStateRef State,
+                                    const CXXBindTemporaryExpr *BTE,
+                                    const LocationContext *LC) {
+  ElidedDestructorItem I(BTE, LC);
+  return State->contains<ElidedDestructors>(I);
+}
+
 bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,
                                                const LocationContext *FromLC,
                                                const LocationContext *ToLC) {
@@ -485,6 +512,10 @@ bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,
       if (I.first.getLocationContext() == LC)
         return false;
 
+    for (auto I: State->get<ElidedDestructors>())
+      if (I.second == LC)
+        return false;
+
     LC = LC->getParent();
   }
   return true;
@@ -529,6 +560,14 @@ static void printObjectsUnderConstructionForContext(raw_ostream &Out,
     Key.print(Out, nullptr, PP);
     Out << " : " << Value << NL;
   }
+
+  for (auto I : State->get<ElidedDestructors>()) {
+    if (I.second != LC)
+      continue;
+    Out << '(' << I.second << ',' << (const void *)I.first << ") ";
+    I.first->printPretty(Out, nullptr, PP);
+    Out << " : (constructor elided)" << NL;
+  }
 }
 
 void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State,
@@ -1003,10 +1042,11 @@ void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
                                       ExplodedNode *Pred,
                                       ExplodedNodeSet &Dst) {
-  ExplodedNodeSet CleanDtorState;
-  StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx);
+  const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr();
   ProgramStateRef State = Pred->getState();
+  const LocationContext *LC = Pred->getLocationContext();
   const MemRegion *MR = nullptr;
+
   if (Optional<SVal> V =
           getObjectUnderConstruction(State, D.getBindTemporaryExpr(),
                                      Pred->getLocationContext())) {
@@ -1017,6 +1057,21 @@ void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
                                      Pred->getLocationContext());
     MR = V->getAsRegion();
   }
+
+  // If copy elision has occured, and the constructor corresponding to the
+  // destructor was elided, we need to skip the destructor as well.
+  if (isDestructorElided(State, BTE, LC)) {
+    State = cleanupElidedDestructor(State, BTE, LC);
+    NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
+    PostImplicitCall PP(D.getDestructorDecl(getContext()),
+                        D.getBindTemporaryExpr()->getLocStart(),
+                        Pred->getLocationContext());
+    Bldr.generateNode(PP, State, Pred);
+    return;
+  }
+
+  ExplodedNodeSet CleanDtorState;
+  StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx);
   StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State);
 
   QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType();
@@ -2201,8 +2256,21 @@ void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
           // it must be a separate problem.
           assert(isa<CXXBindTemporaryExpr>(I.first.getStmt()));
           State = State->remove<ObjectsUnderConstruction>(I.first);
+          // Also cleanup the elided destructor info.
+          ElidedDestructorItem Item(
+              cast<CXXBindTemporaryExpr>(I.first.getStmt()),
+              I.first.getLocationContext());
+          State = State->remove<ElidedDestructors>(Item);
         }
 
+      // Also suppress the assertion for elided destructors when temporary
+      // destructors are not provided at all by the CFG, because there's no
+      // good place to clean them up.
+      if (!AMgr.getAnalyzerOptions().includeTemporaryDtorsInCFG())
+        for (auto I : State->get<ElidedDestructors>())
+          if (I.second == LC)
+            State = State->remove<ElidedDestructors>(I);
+
       LC = LC->getParent();
     }
     if (State != Pred->getState()) {
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
index 5d0428ac656..dc124fc3ff2 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
@@ -209,12 +209,37 @@ std::pair<ProgramStateRef, SVal> ExprEngine::prepareForObjectConstruction(
       }
       llvm_unreachable("Unhandled return value construction context!");
     }
-    case ConstructionContext::ElidedTemporaryObjectKind:
+    case ConstructionContext::ElidedTemporaryObjectKind: {
       assert(AMgr.getAnalyzerOptions().shouldElideConstructors());
-      // FALL-THROUGH
+      const auto *TCC = cast<ElidedTemporaryObjectConstructionContext>(CC);
+      const CXXBindTemporaryExpr *BTE = TCC->getCXXBindTemporaryExpr();
+      const MaterializeTemporaryExpr *MTE = TCC->getMaterializedTemporaryExpr();
+      const CXXConstructExpr *CE = TCC->getConstructorAfterElision();
+
+      // Support pre-C++17 copy elision. We'll have the elidable copy
+      // constructor in the AST and in the CFG, but we'll skip it
+      // and construct directly into the final object. This call
+      // also sets the CallOpts flags for us.
+      SVal V;
+      std::tie(State, V) = prepareForObjectConstruction(
+          CE, State, LCtx, TCC->getConstructionContextAfterElision(), CallOpts);
+
+      // Remember that we've elided the constructor.
+      State = addObjectUnderConstruction(State, CE, LCtx, V);
+
+      // Remember that we've elided the destructor.
+      if (BTE)
+        State = elideDestructor(State, BTE, LCtx);
+
+      // Instead of materialization, shamelessly return
+      // the final object destination.
+      if (MTE)
+        State = addObjectUnderConstruction(State, MTE, LCtx, V);
+
+      return std::make_pair(State, V);
+    }
     case ConstructionContext::SimpleTemporaryObjectKind: {
-      // TODO: Copy elision implementation goes here.
-      const auto *TCC = cast<TemporaryObjectConstructionContext>(CC);
+      const auto *TCC = cast<SimpleTemporaryObjectConstructionContext>(CC);
       const CXXBindTemporaryExpr *BTE = TCC->getCXXBindTemporaryExpr();
       const MaterializeTemporaryExpr *MTE = TCC->getMaterializedTemporaryExpr();
       SVal V = UnknownVal();
@@ -266,6 +291,20 @@ void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE,
 
   SVal Target = UnknownVal();
 
+  if (Optional<SVal> ElidedTarget =
+          getObjectUnderConstruction(State, CE, LCtx)) {
+    // We've previously modeled an elidable constructor by pretending that it in
+    // fact constructs into the correct target. This constructor can therefore
+    // be skipped.
+    Target = *ElidedTarget;
+    StmtNodeBuilder Bldr(Pred, destNodes, *currBldrCtx);
+    State = finishObjectConstruction(State, CE, LCtx);
+    if (auto L = Target.getAs<Loc>())
+      State = State->BindExpr(CE, LCtx, State->getSVal(*L, CE->getType()));
+    Bldr.generateNode(CE, Pred, State);
+    return;
+  }
+
   // FIXME: Handle arrays, which run the same constructor for every element.
   // For now, we just run the first constructor (which should still invalidate
   // the entire array).