Implement semantic analysis and an AST representation for the named

return value optimization. Sema marks return statements with their
NRVO candidates (which may or may not end up using the NRVO), then, at
the end of a function body, computes and marks those variables that
can be allocated into the return slot.

I've checked this locally with some debugging statements (not
committed), but there won't be any tests until CodeGen comes along.

llvm-svn: 103865

9 files changed, 153 insertions, 77 deletions

diff --git a/clang/lib/CodeGen/CGObjC.cpp b/clang/lib/CodeGen/CGObjC.cpp
index b3e9dc52513..df0263ee129 100644
--- a/clang/lib/CodeGen/CGObjC.cpp
+++ b/clang/lib/CodeGen/CGObjC.cpp
@@ -255,7 +255,8 @@ void CodeGenFunction::GenerateObjCGetter(ObjCImplementationDecl *IMP,
         if (PID->getGetterCXXConstructor()) {
           ReturnStmt *Stmt = 
             new (getContext()) ReturnStmt(SourceLocation(), 
-                                          PID->getGetterCXXConstructor());
+                                          PID->getGetterCXXConstructor(),
+                                          0);
           EmitReturnStmt(*Stmt);
         }
         else {
diff --git a/clang/lib/Frontend/PCHReaderDecl.cpp b/clang/lib/Frontend/PCHReaderDecl.cpp
index 3f91d0cafb7..49010bf0d6d 100644
--- a/clang/lib/Frontend/PCHReaderDecl.cpp
+++ b/clang/lib/Frontend/PCHReaderDecl.cpp
@@ -435,6 +435,7 @@ void PCHDeclReader::VisitVarDecl(VarDecl *VD) {
   VD->setCXXDirectInitializer(Record[Idx++]);
   VD->setDeclaredInCondition(Record[Idx++]);
   VD->setExceptionVariable(Record[Idx++]);
+  VD->setNRVOVariable(Record[Idx++]);
   VD->setPreviousDeclaration(
                          cast_or_null<VarDecl>(Reader.GetDecl(Record[Idx++])));
   if (Record[Idx++])
diff --git a/clang/lib/Frontend/PCHReaderStmt.cpp b/clang/lib/Frontend/PCHReaderStmt.cpp
index 7595d03a15f..3931adbe8f2 100644
--- a/clang/lib/Frontend/PCHReaderStmt.cpp
+++ b/clang/lib/Frontend/PCHReaderStmt.cpp
@@ -291,6 +291,7 @@ unsigned PCHStmtReader::VisitReturnStmt(ReturnStmt *S) {
   VisitStmt(S);
   S->setRetValue(cast_or_null<Expr>(StmtStack.back()));
   S->setReturnLoc(SourceLocation::getFromRawEncoding(Record[Idx++]));
+  S->setNRVOCandidate(cast_or_null<VarDecl>(Reader.GetDecl(Record[Idx++])));
   return 1;
 }
 
diff --git a/clang/lib/Frontend/PCHWriterDecl.cpp b/clang/lib/Frontend/PCHWriterDecl.cpp
index 28a10ad6b0a..cc58e8ee465 100644
--- a/clang/lib/Frontend/PCHWriterDecl.cpp
+++ b/clang/lib/Frontend/PCHWriterDecl.cpp
@@ -415,6 +415,7 @@ void PCHDeclWriter::VisitVarDecl(VarDecl *D) {
   Record.push_back(D->hasCXXDirectInitializer());
   Record.push_back(D->isDeclaredInCondition());
   Record.push_back(D->isExceptionVariable());
+  Record.push_back(D->isNRVOVariable());
   Writer.AddDeclRef(D->getPreviousDeclaration(), Record);
   Record.push_back(D->getInit() ? 1 : 0);
   if (D->getInit())
@@ -683,6 +684,7 @@ void PCHWriter::WriteDeclsBlockAbbrevs() {
   Abv->Add(BitCodeAbbrevOp(0));                       // hasCXXDirectInitializer
   Abv->Add(BitCodeAbbrevOp(0));                       // isDeclaredInCondition
   Abv->Add(BitCodeAbbrevOp(0));                       // isExceptionVariable
+  Abv->Add(BitCodeAbbrevOp(0));                       // isNRVOVariable
   Abv->Add(BitCodeAbbrevOp(0));                       // PrevDecl
   Abv->Add(BitCodeAbbrevOp(0));                       // HasInit
   // ParmVarDecl
diff --git a/clang/lib/Frontend/PCHWriterStmt.cpp b/clang/lib/Frontend/PCHWriterStmt.cpp
index a7f73a17fa6..a9ee43527ce 100644
--- a/clang/lib/Frontend/PCHWriterStmt.cpp
+++ b/clang/lib/Frontend/PCHWriterStmt.cpp
@@ -275,6 +275,7 @@ void PCHStmtWriter::VisitReturnStmt(ReturnStmt *S) {
   VisitStmt(S);
   Writer.WriteSubStmt(S->getRetValue());
   Writer.AddSourceLocation(S->getReturnLoc(), Record);
+  Writer.AddDeclRef(S->getNRVOCandidate(), Record);
   Code = pch::STMT_RETURN;
 }
 
diff --git a/clang/lib/Sema/Sema.cpp b/clang/lib/Sema/Sema.cpp
index 569de3203aa..b9aa61144af 100644
--- a/clang/lib/Sema/Sema.cpp
+++ b/clang/lib/Sema/Sema.cpp
@@ -33,6 +33,7 @@ void FunctionScopeInfo::Clear(unsigned NumErrors) {
   NeedsScopeChecking = false;
   LabelMap.clear();
   SwitchStack.clear();
+  Returns.clear();
   NumErrorsAtStartOfFunction = NumErrors;
 }
 
diff --git a/clang/lib/Sema/Sema.h b/clang/lib/Sema/Sema.h
index d97dc676823..3e143bb3b00 100644
--- a/clang/lib/Sema/Sema.h
+++ b/clang/lib/Sema/Sema.h
@@ -134,6 +134,11 @@ struct FunctionScopeInfo {
   /// block.
   llvm::SmallVector<SwitchStmt*, 8> SwitchStack;
 
+  /// \brief The list of return statements that occur within the function or
+  /// block, if there is any chance of applying the named return value
+  /// optimization.
+  llvm::SmallVector<ReturnStmt *, 4> Returns;
+  
   FunctionScopeInfo(unsigned NumErrors)
     : IsBlockInfo(false), NeedsScopeChecking(false),
       NumErrorsAtStartOfFunction(NumErrors) { }
diff --git a/clang/lib/Sema/SemaDecl.cpp b/clang/lib/Sema/SemaDecl.cpp
index 5bb0b524d15..fb3100353b8 100644
--- a/clang/lib/Sema/SemaDecl.cpp
+++ b/clang/lib/Sema/SemaDecl.cpp
@@ -4548,6 +4548,38 @@ Sema::DeclPtrTy Sema::ActOnStartOfFunctionDef(Scope *FnBodyScope, DeclPtrTy D) {
   return DeclPtrTy::make(FD);
 }
 
+/// \brief Given the set of return statements within a function body,
+/// compute the variables that are subject to the named return value 
+/// optimization.
+///
+/// Each of the variables that is subject to the named return value 
+/// optimization will be marked as NRVO variables in the AST, and any
+/// return statement that has a marked NRVO variable as its NRVO candidate can
+/// use the named return value optimization.
+///
+/// This function applies a very simplistic algorithm for NRVO: if every return
+/// statement in the function has the same NRVO candidate, that candidate is
+/// the NRVO variable.
+///
+/// FIXME: Employ a smarter algorithm that accounts for multiple return 
+/// statements and the lifetimes of the NRVO candidates. We should be able to
+/// find a maximal set of NRVO variables.
+static void ComputeNRVO(Stmt *Body, ReturnStmt **Returns, unsigned NumReturns) {
+  const VarDecl *NRVOCandidate = 0;
+  for (unsigned I = 0; I != NumReturns; ++I) {
+    if (!Returns[I]->getNRVOCandidate())
+      return;
+    
+    if (!NRVOCandidate)
+      NRVOCandidate = Returns[I]->getNRVOCandidate();
+    else if (NRVOCandidate != Returns[I]->getNRVOCandidate())
+      return;
+  }
+  
+  if (NRVOCandidate)
+    const_cast<VarDecl*>(NRVOCandidate)->setNRVOVariable(true);
+}
+
 Sema::DeclPtrTy Sema::ActOnFinishFunctionBody(DeclPtrTy D, StmtArg BodyArg) {
   return ActOnFinishFunctionBody(D, move(BodyArg), false);
 }
@@ -4581,6 +4613,9 @@ Sema::DeclPtrTy Sema::ActOnFinishFunctionBody(DeclPtrTy D, StmtArg BodyArg,
       // If this is a constructor, we need a vtable.
       if (CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(FD))
         MarkVTableUsed(FD->getLocation(), Constructor->getParent());
+      
+      ComputeNRVO(Body, FunctionScopes.back()->Returns.data(),
+                  FunctionScopes.back()->Returns.size());
     }
     
     assert(FD == getCurFunctionDecl() && "Function parsing confused");
diff --git a/clang/lib/Sema/SemaStmt.cpp b/clang/lib/Sema/SemaStmt.cpp
index d9210f6a1b0..f8fe4fe21c0 100644
--- a/clang/lib/Sema/SemaStmt.cpp
+++ b/clang/lib/Sema/SemaStmt.cpp
@@ -1058,29 +1058,42 @@ Sema::ActOnBreakStmt(SourceLocation BreakLoc, Scope *CurScope) {
   return Owned(new (Context) BreakStmt(BreakLoc));
 }
 
-/// IsReturnCopyElidable - Whether returning @p RetExpr from a function that
-/// returns a @p RetType fulfills the criteria for copy elision (C++0x 12.8p34).
-static bool IsReturnCopyElidable(ASTContext &Ctx, QualType RetType,
-                                 Expr *RetExpr) {
+/// \brief Determine whether a return statement is a candidate for the named
+/// return value optimization (C++0x 12.8p34, bullet 1).
+///
+/// \param Ctx The context in which the return expression and type occur.
+///
+/// \param RetType The return type of the function or block.
+///
+/// \param RetExpr The expression being returned from the function or block.
+///
+/// \returns The NRVO candidate variable, if the return statement may use the
+/// NRVO, or NULL if there is no such candidate.
+static const VarDecl *getNRVOCandidate(ASTContext &Ctx, QualType RetType,
+                                       Expr *RetExpr) {
   QualType ExprType = RetExpr->getType();
   // - in a return statement in a function with ...
   // ... a class return type ...
   if (!RetType->isRecordType())
-    return false;
+    return 0;
   // ... the same cv-unqualified type as the function return type ...
   if (!Ctx.hasSameUnqualifiedType(RetType, ExprType))
-    return false;
+    return 0;
   // ... the expression is the name of a non-volatile automatic object ...
   // We ignore parentheses here.
   // FIXME: Is this compliant? (Everyone else does it)
   const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(RetExpr->IgnoreParens());
   if (!DR)
-    return false;
+    return 0;
   const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
   if (!VD)
-    return false;
-  return VD->getKind() == Decl::Var && VD->hasLocalStorage() && 
-    !VD->getType()->isReferenceType() && !VD->getType().isVolatileQualified();
+    return 0;
+  
+  if (VD->getKind() == Decl::Var && VD->hasLocalStorage() && 
+      !VD->getType()->isReferenceType() && !VD->getType().isVolatileQualified())
+    return VD;
+  
+  return 0;
 }
 
 /// ActOnBlockReturnStmt - Utility routine to figure out block's return type.
@@ -1117,46 +1130,58 @@ Sema::ActOnBlockReturnStmt(SourceLocation ReturnLoc, Expr *RetValExp) {
   // Otherwise, verify that this result type matches the previous one.  We are
   // pickier with blocks than for normal functions because we don't have GCC
   // compatibility to worry about here.
+  ReturnStmt *Result = 0;
   if (CurBlock->ReturnType->isVoidType()) {
     if (RetValExp) {
       Diag(ReturnLoc, diag::err_return_block_has_expr);
       RetValExp->Destroy(Context);
       RetValExp = 0;
     }
-    return Owned(new (Context) ReturnStmt(ReturnLoc, RetValExp));
-  }
-
-  if (!RetValExp)
+    Result = new (Context) ReturnStmt(ReturnLoc, RetValExp, 0);
+  } else if (!RetValExp) {
     return StmtError(Diag(ReturnLoc, diag::err_block_return_missing_expr));
+  } else {
+    const VarDecl *NRVOCandidate = 0;
+    
+    if (!FnRetType->isDependentType() && !RetValExp->isTypeDependent()) {
+      // we have a non-void block with an expression, continue checking
+
+      // C99 6.8.6.4p3(136): The return statement is not an assignment. The
+      // overlap restriction of subclause 6.5.16.1 does not apply to the case of
+      // function return.
+
+      // In C++ the return statement is handled via a copy initialization.
+      // the C version of which boils down to CheckSingleAssignmentConstraints.
+      NRVOCandidate = getNRVOCandidate(Context, FnRetType, RetValExp);
+      OwningExprResult Res = PerformCopyInitialization(
+                               InitializedEntity::InitializeResult(ReturnLoc, 
+                                                                   FnRetType,
+                                                            NRVOCandidate != 0),
+                               SourceLocation(),
+                               Owned(RetValExp));
+      if (Res.isInvalid()) {
+        // FIXME: Cleanup temporaries here, anyway?
+        return StmtError();
+      }
+      
+      if (RetValExp)
+        RetValExp = MaybeCreateCXXExprWithTemporaries(RetValExp);
 
-  if (!FnRetType->isDependentType() && !RetValExp->isTypeDependent()) {
-    // we have a non-void block with an expression, continue checking
-
-    // C99 6.8.6.4p3(136): The return statement is not an assignment. The
-    // overlap restriction of subclause 6.5.16.1 does not apply to the case of
-    // function return.
-
-    // In C++ the return statement is handled via a copy initialization.
-    // the C version of which boils down to CheckSingleAssignmentConstraints.
-    OwningExprResult Res = PerformCopyInitialization(
-                             InitializedEntity::InitializeResult(ReturnLoc, 
-                                                                 FnRetType,
-                                               IsReturnCopyElidable(Context, 
-                                                                    FnRetType, 
-                                                                    RetValExp)),
-                             SourceLocation(),
-                             Owned(RetValExp));
-    if (Res.isInvalid()) {
-      // FIXME: Cleanup temporaries here, anyway?
-      return StmtError();
+      RetValExp = Res.takeAs<Expr>();
+      if (RetValExp) 
+        CheckReturnStackAddr(RetValExp, FnRetType, ReturnLoc);
     }
     
-    RetValExp = Res.takeAs<Expr>();
-    if (RetValExp) 
-      CheckReturnStackAddr(RetValExp, FnRetType, ReturnLoc);
+    Result = new (Context) ReturnStmt(ReturnLoc, RetValExp, NRVOCandidate);
   }
 
-  return Owned(new (Context) ReturnStmt(ReturnLoc, RetValExp));
+  // If we need to check for the named return value optimization, save the 
+  // return statement in our scope for later processing.
+  if (getLangOptions().CPlusPlus && FnRetType->isRecordType() &&
+      !CurContext->isDependentContext())
+    FunctionScopes.back()->Returns.push_back(Result);
+  
+  return Owned(Result);
 }
 
 Action::OwningStmtResult
@@ -1177,6 +1202,7 @@ Sema::ActOnReturnStmt(SourceLocation ReturnLoc, ExprArg rex) {
   else // If we don't have a function/method context, bail.
     return StmtError();
 
+  ReturnStmt *Result = 0;
   if (FnRetType->isVoidType()) {
     if (RetValExp && !RetValExp->isTypeDependent()) {
       // C99 6.8.6.4p1 (ext_ since GCC warns)
@@ -1195,10 +1221,9 @@ Sema::ActOnReturnStmt(SourceLocation ReturnLoc, ExprArg rex) {
 
       RetValExp = MaybeCreateCXXExprWithTemporaries(RetValExp);
     }
-    return Owned(new (Context) ReturnStmt(ReturnLoc, RetValExp));
-  }
-
-  if (!RetValExp && !FnRetType->isDependentType()) {
+    
+    Result = new (Context) ReturnStmt(ReturnLoc, RetValExp, 0);
+  } else if (!RetValExp && !FnRetType->isDependentType()) {
     unsigned DiagID = diag::warn_return_missing_expr;  // C90 6.6.6.4p4
     // C99 6.8.6.4p1 (ext_ since GCC warns)
     if (getLangOptions().C99) DiagID = diag::ext_return_missing_expr;
@@ -1207,43 +1232,47 @@ Sema::ActOnReturnStmt(SourceLocation ReturnLoc, ExprArg rex) {
       Diag(ReturnLoc, DiagID) << FD->getIdentifier() << 0/*fn*/;
     else
       Diag(ReturnLoc, DiagID) << getCurMethodDecl()->getDeclName() << 1/*meth*/;
-    return Owned(new (Context) ReturnStmt(ReturnLoc, (Expr*)0));
-  }
-
-  if (!FnRetType->isDependentType() && !RetValExp->isTypeDependent()) {
-    // we have a non-void function with an expression, continue checking
-
-    // C99 6.8.6.4p3(136): The return statement is not an assignment. The
-    // overlap restriction of subclause 6.5.16.1 does not apply to the case of
-    // function return.
+    Result = new (Context) ReturnStmt(ReturnLoc);
+  } else {
+    const VarDecl *NRVOCandidate = 0;
+    if (!FnRetType->isDependentType() && !RetValExp->isTypeDependent()) {
+      // we have a non-void function with an expression, continue checking
+
+      // C99 6.8.6.4p3(136): The return statement is not an assignment. The
+      // overlap restriction of subclause 6.5.16.1 does not apply to the case of
+      // function return.
+
+      // In C++ the return statement is handled via a copy initialization.
+      // the C version of which boils down to CheckSingleAssignmentConstraints.
+      NRVOCandidate = getNRVOCandidate(Context, FnRetType, RetValExp);
+      OwningExprResult Res = PerformCopyInitialization(
+                               InitializedEntity::InitializeResult(ReturnLoc, 
+                                                                   FnRetType,
+                                                            NRVOCandidate != 0),
+                               SourceLocation(),
+                               Owned(RetValExp));
+      if (Res.isInvalid()) {
+        // FIXME: Cleanup temporaries here, anyway?
+        return StmtError();
+      }
 
-    // C++0x [class.copy]p34:
-    //
-    
-    
-    // In C++ the return statement is handled via a copy initialization.
-    // the C version of which boils down to CheckSingleAssignmentConstraints.
-    OwningExprResult Res = PerformCopyInitialization(
-                             InitializedEntity::InitializeResult(ReturnLoc, 
-                                                                 FnRetType,
-                                               IsReturnCopyElidable(Context, 
-                                                                    FnRetType, 
-                                                                    RetValExp)),
-                             SourceLocation(),
-                             Owned(RetValExp));
-    if (Res.isInvalid()) {
-      // FIXME: Cleanup temporaries here, anyway?
-      return StmtError();
+      RetValExp = Res.takeAs<Expr>();
+      if (RetValExp) 
+        CheckReturnStackAddr(RetValExp, FnRetType, ReturnLoc);
     }
-
-    RetValExp = Res.takeAs<Expr>();
-    if (RetValExp) 
-      CheckReturnStackAddr(RetValExp, FnRetType, ReturnLoc);
+    
+    if (RetValExp)
+      RetValExp = MaybeCreateCXXExprWithTemporaries(RetValExp);
+    Result = new (Context) ReturnStmt(ReturnLoc, RetValExp, NRVOCandidate);
   }
-
-  if (RetValExp)
-    RetValExp = MaybeCreateCXXExprWithTemporaries(RetValExp);
-  return Owned(new (Context) ReturnStmt(ReturnLoc, RetValExp));
+  
+  // If we need to check for the named return value optimization, save the 
+  // return statement in our scope for later processing.
+  if (getLangOptions().CPlusPlus && FnRetType->isRecordType() &&
+      !CurContext->isDependentContext())
+    FunctionScopes.back()->Returns.push_back(Result);
+  
+  return Owned(Result);
 }
 
 /// CheckAsmLValue - GNU C has an extremely ugly extension whereby they silently