Improved semantic analysis and AST respresentation for function

templates.

For example, this now type-checks (but does not instantiate the body
of deref<int>):

  template<typename T> T& deref(T* t) { return *t; }

  void test(int *ip) {
    int &ir = deref(ip);
  }

Specific changes/additions:
  * Template argument deduction from a call to a function template.
  * Instantiation of a function template specializations (just the
  declarations) from the template arguments deduced from a call.
  * FunctionTemplateDecls are stored directly in declaration contexts
  and found via name lookup (all forms), rather than finding the
  FunctionDecl and then realizing it is a template. This is
  responsible for most of the churn, since some of the core
  declaration matching and lookup code assumes that all functions are
  FunctionDecls.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@74213 91177308-0d34-0410-b5e6-96231b3b80d8

13 files changed, 398 insertions, 48 deletions

diff --git a/lib/AST/Decl.cpp b/lib/AST/Decl.cpp
index 71e88a9efc..e48ba156c9 100644
--- a/lib/AST/Decl.cpp
+++ b/lib/AST/Decl.cpp
@@ -269,6 +269,14 @@ bool NamedDecl::declarationReplaces(NamedDecl *OldD) const {
     // For function declarations, we keep track of redeclarations.
     return FD->getPreviousDeclaration() == OldD;
 
+  // For function templates, the underlying function declarations are linked.
+  if (const FunctionTemplateDecl *FunctionTemplate
+        = dyn_cast<FunctionTemplateDecl>(this))
+    if (const FunctionTemplateDecl *OldFunctionTemplate
+          = dyn_cast<FunctionTemplateDecl>(OldD))
+      return FunctionTemplate->getTemplatedDecl()
+               ->declarationReplaces(OldFunctionTemplate->getTemplatedDecl());
+  
   // For method declarations, we keep track of redeclarations.
   if (isa<ObjCMethodDecl>(this))
     return false;
diff --git a/lib/AST/DeclBase.cpp b/lib/AST/DeclBase.cpp
index 02e71d7a86..93bee84cff 100644
--- a/lib/AST/DeclBase.cpp
+++ b/lib/AST/DeclBase.cpp
@@ -96,6 +96,10 @@ bool Decl::isTemplateParameterPack() const {
   return false;
 }
 
+bool Decl::isFunctionOrFunctionTemplate() const {
+  return isa<FunctionDecl>(this) || isa<FunctionTemplateDecl>(this);
+}
+
 //===----------------------------------------------------------------------===//
 // PrettyStackTraceDecl Implementation
 //===----------------------------------------------------------------------===//
diff --git a/lib/AST/DeclCXX.cpp b/lib/AST/DeclCXX.cpp
index 25e4d19617..752218db04 100644
--- a/lib/AST/DeclCXX.cpp
+++ b/lib/AST/DeclCXX.cpp
@@ -420,6 +420,15 @@ OverloadedFunctionDecl::Create(ASTContext &C, DeclContext *DC,
   return new (C) OverloadedFunctionDecl(DC, N);
 }
 
+void OverloadedFunctionDecl::addOverload(FunctionTemplateDecl *FTD) {
+  Functions.push_back(FTD);
+  
+  // An overloaded function declaration always has the location of
+  // the most-recently-added function declaration.
+  if (FTD->getLocation().isValid())
+    this->setLocation(FTD->getLocation());  
+}
+
 LinkageSpecDecl *LinkageSpecDecl::Create(ASTContext &C,
                                          DeclContext *DC, 
                                          SourceLocation L,
diff --git a/lib/Sema/Sema.h b/lib/Sema/Sema.h
index faacb9f9f7..36f3ff96f3 100644
--- a/lib/Sema/Sema.h
+++ b/lib/Sema/Sema.h
@@ -697,6 +697,11 @@ public:
                           OverloadCandidateSet& CandidateSet,
                           bool SuppressUserConversions = false,
                           bool ForceRValue = false);
+  void AddTemplateOverloadCandidate(FunctionTemplateDecl *FunctionTemplate,
+                                    Expr **Args, unsigned NumArgs,
+                                    OverloadCandidateSet& CandidateSet,
+                                    bool SuppressUserConversions = false,
+                                    bool ForceRValue = false);
   void AddConversionCandidate(CXXConversionDecl *Conversion,
                               Expr *From, QualType ToType,
                               OverloadCandidateSet& CandidateSet);
@@ -2204,7 +2209,13 @@ public:
     /// into a non-deduced context produced a type or value that
     /// produces a type that does not match the original template
     /// arguments provided.
-    TDK_NonDeducedMismatch
+    TDK_NonDeducedMismatch,
+    /// \brief When performing template argument deduction for a function 
+    /// template, there were too many call arguments.
+    TDK_TooManyArguments,
+    /// \brief When performing template argument deduction for a class 
+    /// template, there were too few call arguments.
+    TDK_TooFewArguments
   };
 
   /// \brief Provides information about an attempted template argument
@@ -2284,6 +2295,12 @@ public:
                           const TemplateArgumentList &TemplateArgs,
                           TemplateDeductionInfo &Info);
                    
+  TemplateDeductionResult
+  DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
+                          Expr **Args, unsigned NumArgs,
+                          FunctionDecl *&Specialization,
+                          TemplateDeductionInfo &Info);
+  
   void MarkDeducedTemplateParameters(const TemplateArgumentList &TemplateArgs,
                                      llvm::SmallVectorImpl<bool> &Deduced);
           
diff --git a/lib/Sema/SemaDecl.cpp b/lib/Sema/SemaDecl.cpp
index d4b1566d51..c154ddf86c 100644
--- a/lib/Sema/SemaDecl.cpp
+++ b/lib/Sema/SemaDecl.cpp
@@ -319,16 +319,16 @@ void Sema::PushOnScopeChains(NamedDecl *D, Scope *S) {
         return;
       }
     }
-  } else if (isa<FunctionDecl>(D) &&
-             AllowOverloadingOfFunction(D, Context)) {
-    // We are pushing the name of a function, which might be an
-    // overloaded name.
-    FunctionDecl *FD = cast<FunctionDecl>(D);
+  } else if ((isa<FunctionDecl>(D) &&
+              AllowOverloadingOfFunction(D, Context)) ||
+             isa<FunctionTemplateDecl>(D)) {
+    // We are pushing the name of a function or function template,
+    // which might be an overloaded name.
     IdentifierResolver::iterator Redecl
-      = std::find_if(IdResolver.begin(FD->getDeclName()),
+      = std::find_if(IdResolver.begin(D->getDeclName()),
                      IdResolver.end(),
                      std::bind1st(std::mem_fun(&NamedDecl::declarationReplaces),
-                                  FD));
+                                  D));
     if (Redecl != IdResolver.end() &&
         S->isDeclScope(DeclPtrTy::make(*Redecl))) {
       // There is already a declaration of a function on our
@@ -655,7 +655,12 @@ bool Sema::MergeFunctionDecl(FunctionDecl *New, Decl *OldD) {
          "Cannot merge with an overloaded function declaration");
 
   // Verify the old decl was also a function.
-  FunctionDecl *Old = dyn_cast<FunctionDecl>(OldD);
+  FunctionDecl *Old = 0;
+  if (FunctionTemplateDecl *OldFunctionTemplate 
+        = dyn_cast<FunctionTemplateDecl>(OldD))
+    Old = OldFunctionTemplate->getTemplatedDecl();
+  else 
+    Old = dyn_cast<FunctionDecl>(OldD);
   if (!Old) {
     Diag(New->getLocation(), diag::err_redefinition_different_kind)
       << New->getDeclName();
@@ -2304,8 +2309,6 @@ Sema::ActOnFunctionDeclarator(Scope* S, Declarator& D, DeclContext* DC,
   }
   // Finally, we know we have the right number of parameters, install them.
   NewFD->setParams(Context, Params.data(), Params.size());
-
-  
     
   // If name lookup finds a previous declaration that is not in the
   // same scope as the new declaration, this may still be an
@@ -2388,6 +2391,12 @@ Sema::ActOnFunctionDeclarator(Scope* S, Declarator& D, DeclContext* DC,
   // Set this FunctionDecl's range up to the right paren.
   NewFD->setLocEnd(D.getSourceRange().getEnd());
 
+  if (FunctionTemplate && NewFD->isInvalidDecl())
+    FunctionTemplate->setInvalidDecl();
+  
+  if (FunctionTemplate)
+    return FunctionTemplate;
+  
   return NewFD;
 }
 
@@ -2516,7 +2525,11 @@ void Sema::CheckFunctionDeclaration(FunctionDecl *NewFD, NamedDecl *&PrevDecl,
       if (MergeFunctionDecl(NewFD, OldDecl))
         return NewFD->setInvalidDecl();
 
-      NewFD->setPreviousDeclaration(cast<FunctionDecl>(OldDecl));
+      if (FunctionTemplateDecl *OldTemplateDecl
+            = dyn_cast<FunctionTemplateDecl>(OldDecl))
+        NewFD->setPreviousDeclaration(OldTemplateDecl->getTemplatedDecl());
+      else
+        NewFD->setPreviousDeclaration(cast<FunctionDecl>(OldDecl));
     }
   }
 
diff --git a/lib/Sema/SemaDeclCXX.cpp b/lib/Sema/SemaDeclCXX.cpp
index 466015a164..f00acdac41 100644
--- a/lib/Sema/SemaDeclCXX.cpp
+++ b/lib/Sema/SemaDeclCXX.cpp
@@ -1625,7 +1625,8 @@ Sema::DeclPtrTy Sema::ActOnConversionDeclarator(CXXConversionDecl *Conversion) {
            Conv = Conversions->function_begin(),
            ConvEnd = Conversions->function_end();
          Conv != ConvEnd; ++Conv) {
-      if (*Conv == Conversion->getPreviousDeclaration()) {
+      if (*Conv 
+            == cast_or_null<NamedDecl>(Conversion->getPreviousDeclaration())) {
         *Conv = Conversion;
         return DeclPtrTy::make(Conversion);
       }
diff --git a/lib/Sema/SemaExpr.cpp b/lib/Sema/SemaExpr.cpp
index d94550cc5f..44b6802c10 100644
--- a/lib/Sema/SemaExpr.cpp
+++ b/lib/Sema/SemaExpr.cpp
@@ -2605,11 +2605,16 @@ Sema::ActOnCallExpr(Scope *S, ExprArg fn, SourceLocation LParenLoc,
                                                 CommaLocs, RParenLoc));
 
     // Determine whether this is a call to a member function.
-    if (MemberExpr *MemExpr = dyn_cast<MemberExpr>(Fn->IgnoreParens()))
-      if (isa<OverloadedFunctionDecl>(MemExpr->getMemberDecl()) ||
-          isa<CXXMethodDecl>(MemExpr->getMemberDecl()))
+    if (MemberExpr *MemExpr = dyn_cast<MemberExpr>(Fn->IgnoreParens())) {
+      NamedDecl *MemDecl = MemExpr->getMemberDecl();
+      if (isa<OverloadedFunctionDecl>(MemDecl) ||
+          isa<CXXMethodDecl>(MemDecl) ||
+          (isa<FunctionTemplateDecl>(MemDecl) &&
+           isa<CXXMethodDecl>(
+                cast<FunctionTemplateDecl>(MemDecl)->getTemplatedDecl())))
         return Owned(BuildCallToMemberFunction(S, Fn, LParenLoc, Args, NumArgs,
                                                CommaLocs, RParenLoc));
+    }
   }
 
   // If we're directly calling a function, get the appropriate declaration.
@@ -2645,13 +2650,19 @@ Sema::ActOnCallExpr(Scope *S, ExprArg fn, SourceLocation LParenLoc,
   }
 
   OverloadedFunctionDecl *Ovl = 0;
+  FunctionTemplateDecl *FunctionTemplate = 0;
   if (DRExpr) {
     FDecl = dyn_cast<FunctionDecl>(DRExpr->getDecl());
+    if ((FunctionTemplate = dyn_cast<FunctionTemplateDecl>(DRExpr->getDecl())))
+      FDecl = FunctionTemplate->getTemplatedDecl();
+    else
+      FDecl = dyn_cast<FunctionDecl>(DRExpr->getDecl());
     Ovl = dyn_cast<OverloadedFunctionDecl>(DRExpr->getDecl());
     NDecl = dyn_cast<NamedDecl>(DRExpr->getDecl());
   }
 
-  if (Ovl || (getLangOptions().CPlusPlus && (FDecl || UnqualifiedName))) {
+  if (Ovl || FunctionTemplate || 
+      (getLangOptions().CPlusPlus && (FDecl || UnqualifiedName))) {
     // We don't perform ADL for implicit declarations of builtins.
     if (FDecl && FDecl->getBuiltinID(Context) && FDecl->isImplicit())
       ADL = false;
@@ -2660,7 +2671,7 @@ Sema::ActOnCallExpr(Scope *S, ExprArg fn, SourceLocation LParenLoc,
     if (!getLangOptions().CPlusPlus)
       ADL = false;
 
-    if (Ovl || ADL) {
+    if (Ovl || FunctionTemplate || ADL) {
       FDecl = ResolveOverloadedCallFn(Fn, DRExpr? DRExpr->getDecl() : 0,
                                       UnqualifiedName, LParenLoc, Args,
                                       NumArgs, CommaLocs, RParenLoc, ADL);
diff --git a/lib/Sema/SemaLookup.cpp b/lib/Sema/SemaLookup.cpp
index 9bcf320771..e6f3d9ec3b 100644
--- a/lib/Sema/SemaLookup.cpp
+++ b/lib/Sema/SemaLookup.cpp
@@ -125,21 +125,30 @@ MaybeConstructOverloadSet(ASTContext &Context,
   assert(!isa<OverloadedFunctionDecl>(*I) && 
          "Cannot have an overloaded function");
 
-  if (isa<FunctionDecl>(*I)) {
+  if ((*I)->isFunctionOrFunctionTemplate()) {
     // If we found a function, there might be more functions. If
     // so, collect them into an overload set.
     DeclIterator Last = I;
     OverloadedFunctionDecl *Ovl = 0;
-    for (++Last; Last != IEnd && isa<FunctionDecl>(*Last); ++Last) {
+    for (++Last; 
+         Last != IEnd && (*Last)->isFunctionOrFunctionTemplate(); 
+         ++Last) {
       if (!Ovl) {
         // FIXME: We leak this overload set. Eventually, we want to stop
         // building the declarations for these overload sets, so there will be
         // nothing to leak.
         Ovl = OverloadedFunctionDecl::Create(Context, (*I)->getDeclContext(),
                                              (*I)->getDeclName());
-        Ovl->addOverload(cast<FunctionDecl>(*I));
+        if (isa<FunctionDecl>(*I))
+          Ovl->addOverload(cast<FunctionDecl>(*I));
+        else
+          Ovl->addOverload(cast<FunctionTemplateDecl>(*I));
       }
-      Ovl->addOverload(cast<FunctionDecl>(*Last));
+
+      if (isa<FunctionDecl>(*Last))
+        Ovl->addOverload(cast<FunctionDecl>(*Last));
+      else
+        Ovl->addOverload(cast<FunctionTemplateDecl>(*Last));
     }
     
     // If we had more than one function, we built an overload
@@ -206,7 +215,7 @@ MergeLookupResults(ASTContext &Context, LookupResultsTy &Results) {
       if (TagDecl *TD = dyn_cast<TagDecl>(ND)) {
         TagFound = Context.getCanonicalDecl(TD);
         TagNames += FoundDecls.insert(TagFound)?  1 : 0;
-      } else if (isa<FunctionDecl>(ND))
+      } else if (ND->isFunctionOrFunctionTemplate())
         Functions += FoundDecls.insert(ND)? 1 : 0;
       else
         FoundDecls.insert(ND);
@@ -334,10 +343,10 @@ Sema::LookupResult::CreateLookupResult(ASTContext &Context,
   LookupResult Result;
   Result.Context = &Context;
 
-  if (F != L && isa<FunctionDecl>(*F)) {
+  if (F != L && (*F)->isFunctionOrFunctionTemplate()) {
     IdentifierResolver::iterator Next = F;
     ++Next;
-    if (Next != L && isa<FunctionDecl>(*Next)) {
+    if (Next != L && (*Next)->isFunctionOrFunctionTemplate()) {
       Result.StoredKind = OverloadedDeclFromIdResolver;
       Result.First = F.getAsOpaqueValue();
       Result.Last = L.getAsOpaqueValue();
@@ -363,10 +372,10 @@ Sema::LookupResult::CreateLookupResult(ASTContext &Context,
   LookupResult Result;
   Result.Context = &Context;
 
-  if (F != L && isa<FunctionDecl>(*F)) {
+  if (F != L && (*F)->isFunctionOrFunctionTemplate()) {
     DeclContext::lookup_iterator Next = F;
     ++Next;
-    if (Next != L && isa<FunctionDecl>(*Next)) {
+    if (Next != L && (*Next)->isFunctionOrFunctionTemplate()) {
       Result.StoredKind = OverloadedDeclFromDeclContext;
       Result.First = reinterpret_cast<uintptr_t>(F);
       Result.Last = reinterpret_cast<uintptr_t>(L);
@@ -1083,7 +1092,7 @@ Sema::LookupQualifiedName(DeclContext *LookupCtx, DeclarationName Name,
   // Lookup in a base class succeeded; return these results.
 
   // If we found a function declaration, return an overload set.
-  if (isa<FunctionDecl>(*Paths.front().Decls.first))
+  if ((*Paths.front().Decls.first)->isFunctionOrFunctionTemplate())
     return LookupResult::CreateLookupResult(Context, 
                         Paths.front().Decls.first, Paths.front().Decls.second);
 
@@ -1489,7 +1498,9 @@ Sema::FindAssociatedClassesAndNamespaces(Expr **Args, unsigned NumArgs,
     for (OverloadedFunctionDecl::function_iterator Func = Ovl->function_begin(),
                                                 FuncEnd = Ovl->function_end();
          Func != FuncEnd; ++Func) {
-      FunctionDecl *FDecl = cast<FunctionDecl>(*Func);
+      FunctionDecl *FDecl = dyn_cast<FunctionDecl>(*Func);
+      if (!FDecl)
+        FDecl = cast<FunctionTemplateDecl>(*Func)->getTemplatedDecl();
 
       // Add the namespace in which this function was defined. Note
       // that, if this is a member function, we do *not* consider the
diff --git a/lib/Sema/SemaOverload.cpp b/lib/Sema/SemaOverload.cpp
index 6217e6d57a..fcc155750c 100644
--- a/lib/Sema/SemaOverload.cpp
+++ b/lib/Sema/SemaOverload.cpp
@@ -300,7 +300,9 @@ Sema::IsOverload(FunctionDecl *New, Decl* OldD,
 
     // This function overloads every function in the overload set.
     return true;
-  } else if (FunctionDecl* Old = dyn_cast<FunctionDecl>(OldD)) {
+  } else if (FunctionTemplateDecl *Old = dyn_cast<FunctionTemplateDecl>(OldD))
+    return IsOverload(New, Old->getTemplatedDecl(), MatchedDecl);
+  else if (FunctionDecl* Old = dyn_cast<FunctionDecl>(OldD)) {
     FunctionTemplateDecl *OldTemplate = Old->getDescribedFunctionTemplate();
     FunctionTemplateDecl *NewTemplate = New->getDescribedFunctionTemplate(); 
     
@@ -2073,7 +2075,9 @@ Sema::AddOverloadCandidate(FunctionDecl *Function,
   assert(Proto && "Functions without a prototype cannot be overloaded");
   assert(!isa<CXXConversionDecl>(Function) && 
          "Use AddConversionCandidate for conversion functions");
-
+  assert(!Function->getDescribedFunctionTemplate() && 
+         "Use AddTemplateOverloadCandidate for function templates");
+  
   if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
     if (!isa<CXXConstructorDecl>(Method)) {
       // If we get here, it's because we're calling a member function
@@ -2258,6 +2262,42 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, Expr *Object,
   }
 }
 
+/// \brief Add a C++ function template as a candidate in the candidate set,
+/// using template argument deduction to produce an appropriate function
+/// template specialization.
+void 
+Sema::AddTemplateOverloadCandidate(FunctionTemplateDecl *FunctionTemplate,
+                                   Expr **Args, unsigned NumArgs,
+                                   OverloadCandidateSet& CandidateSet,
+                                   bool SuppressUserConversions,
+                                   bool ForceRValue) {
+  // C++ [over.match.funcs]p7:
+  //   In each case where a candidate is a function template, candidate 
+  //   function template specializations are generated using template argument
+  //   deduction (14.8.3, 14.8.2). Those candidates are then handled as 
+  //   candidate functions in the usual way.113) A given name can refer to one
+  //   or more function templates and also to a set of overloaded non-template
+  //   functions. In such a case, the candidate functions generated from each
+  //   function template are combined with the set of non-template candidate
+  //   functions.
+  TemplateDeductionInfo Info(Context);
+  FunctionDecl *Specialization = 0;
+  if (TemplateDeductionResult Result
+        = DeduceTemplateArguments(FunctionTemplate, Args, NumArgs, 
+                                  Specialization, Info)) {
+    // FIXME: Record what happened with template argument deduction, so
+    // that we can give the user a beautiful diagnostic.
+    (void)Result;
+    return;
+  }
+                            
+  // Add the function template specialization produced by template argument
+  // deduction as a candidate.
+  assert(Specialization && "Missing function template specialization?");
+  AddOverloadCandidate(Specialization, Args, NumArgs, CandidateSet,
+                       SuppressUserConversions, ForceRValue);
+}
+  
 /// AddConversionCandidate - Add a C++ conversion function as a
 /// candidate in the candidate set (C++ [over.match.conv], 
 /// C++ [over.match.copy]). From is the expression we're converting from,
@@ -3678,8 +3718,15 @@ Sema::ResolveAddressOfOverloadedFunction(Expr *From, QualType ToType,
     } else if (IsMember)
       continue;
 
-    if (FunctionType == Context.getCanonicalType((*Fun)->getType()))
-      return *Fun;
+    if (FunctionDecl *FunDecl = dyn_cast<FunctionDecl>(*Fun)) {
+      if (FunctionType == Context.getCanonicalType(FunDecl->getType()))
+        return FunDecl;
+    } else {
+      unsigned DiagID 
+        = PP.getDiagnostics().getCustomDiagID(Diagnostic::Warning,
+                   "Clang does not yet support templated conversion functions");
+      Diag(From->getLocStart(), DiagID);
+    }
   }
 
   return 0;
@@ -3724,10 +3771,18 @@ FunctionDecl *Sema::ResolveOverloadedCallFn(Expr *Fn, NamedDecl *Callee,
     for (OverloadedFunctionDecl::function_iterator Func = Ovl->function_begin(),
                                                 FuncEnd = Ovl->function_end();
          Func != FuncEnd; ++Func) {
-      AddOverloadCandidate(*Func, Args, NumArgs, CandidateSet);
+      DeclContext *Ctx = 0;
+      if (FunctionDecl *FunDecl = dyn_cast<FunctionDecl>(*Func)) {
+        AddOverloadCandidate(FunDecl, Args, NumArgs, CandidateSet);
+        Ctx = FunDecl->getDeclContext();
+      } else {
+        FunctionTemplateDecl *FunTmpl = cast<FunctionTemplateDecl>(*Func);
+        AddTemplateOverloadCandidate(FunTmpl, Args, NumArgs, CandidateSet);
+        Ctx = FunTmpl->getDeclContext();
+      }
+
 
-      if ((*Func)->getDeclContext()->isRecord() ||
-          (*Func)->getDeclContext()->isFunctionOrMethod())
+      if (Ctx->isRecord() || Ctx->isFunctionOrMethod())
         ArgumentDependentLookup = false;
     }
   } else if (FunctionDecl *Func = dyn_cast_or_null<FunctionDecl>(Callee)) {
@@ -3736,7 +3791,13 @@ FunctionDecl *Sema::ResolveOverloadedCallFn(Expr *Fn, NamedDecl *Callee,
     if (Func->getDeclContext()->isRecord() ||
         Func->getDeclContext()->isFunctionOrMethod())
       ArgumentDependentLookup = false;
-  } 
+  } else if (FunctionTemplateDecl *FuncTemplate 
+               = dyn_cast_or_null<FunctionTemplateDecl>(Callee)) {
+    AddTemplateOverloadCandidate(FuncTemplate, Args, NumArgs, CandidateSet);
+
+    if (FuncTemplate->getDeclContext()->isRecord())
+      ArgumentDependentLookup = false;
+  }
 
   if (Callee)
     UnqualifiedName = Callee->getDeclName();
diff --git a/lib/Sema/SemaTemplate.cpp b/lib/Sema/SemaTemplate.cpp
index e456287293..cd985c536c 100644
--- a/lib/Sema/SemaTemplate.cpp
+++ b/lib/Sema/SemaTemplate.cpp
@@ -79,7 +79,7 @@ TemplateNameKind Sema::isTemplateName(const IdentifierInfo &II, Scope *S,
       for (OverloadedFunctionDecl::function_iterator F = Ovl->function_begin(),
                                                   FEnd = Ovl->function_end();
            F != FEnd; ++F) {
-        if ((*F)->getDescribedFunctionTemplate()) {
+        if (isa<FunctionTemplateDecl>(*F)) {
           TemplateResult = TemplateTy::make(Ovl);
           return TNK_Function_template;
         }
@@ -1809,8 +1809,8 @@ bool Sema::CheckTemplateArgument(TemplateTemplateParmDecl *Param,
       !isa<TemplateTemplateParmDecl>(Template)) {
     assert(isa<FunctionTemplateDecl>(Template) && 
            "Only function templates are possible here");
-    Diag(Arg->getSourceRange().getBegin(), 
-         diag::note_template_arg_refers_here_func)
+    Diag(Arg->getLocStart(), diag::err_template_arg_not_class_template);
+    Diag(Template->getLocation(), diag::note_template_arg_refers_here_func)
       << Template;
   }
 
@@ -2527,7 +2527,13 @@ Sema::ActOnStartOfFunctionTemplateDef(Scope *FnBodyScope,
   DeclPtrTy DP = HandleDeclarator(ParentScope, D, 
                                   move(TemplateParameterLists),
                                   /*IsFunctionDefinition=*/true);
-  return ActOnStartOfFunctionDef(FnBodyScope, DP);  
+  FunctionTemplateDecl *FunctionTemplate 
+    = cast_or_null<FunctionTemplateDecl>(DP.getAs<Decl>());
+  if (FunctionTemplate)
+    return ActOnStartOfFunctionDef(FnBodyScope, 
+                      DeclPtrTy::make(FunctionTemplate->getTemplatedDecl()));
+
+  return DeclPtrTy();
 }
 
 // Explicit instantiation of a class template specialization
diff --git a/lib/Sema/SemaTemplateDeduction.cpp b/lib/Sema/SemaTemplateDeduction.cpp
index de3e52df37..1d7e03eda3 100644
--- a/lib/Sema/SemaTemplateDeduction.cpp
+++ b/lib/Sema/SemaTemplateDeduction.cpp
@@ -717,6 +717,162 @@ Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
   return TDK_Success;
 }
 
+/// \brief Perform template argument deduction from a function call
+/// (C++ [temp.deduct.call]).
+///
+/// \param FunctionTemplate the function template for which we are performing
+/// template argument deduction.
+///
+/// \param Args the function call arguments
+///
+/// \param NumArgs the number of arguments in Args
+///
+/// \param Specialization if template argument deduction was successful,
+/// this will be set to the function template specialization produced by 
+/// template argument deduction.
+///
+/// \param Info the argument will be updated to provide additional information
+/// about template argument deduction.
+///
+/// \returns the result of template argument deduction.
+///
+/// FIXME: We will also need to pass in any explicitly-specified template
+/// arguments.
+Sema::TemplateDeductionResult
+Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
+                              Expr **Args, unsigned NumArgs,
+                              FunctionDecl *&Specialization,
+                              TemplateDeductionInfo &Info) {
+  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
+  
+  // C++ [temp.deduct.call]p1:
+  //   Template argument deduction is done by comparing each function template
+  //   parameter type (call it P) with the type of the corresponding argument
+  //   of the call (call it A) as described below.
+  unsigned CheckArgs = NumArgs;
+  if (NumArgs < Function->getNumParams())
+    return TDK_TooFewArguments;
+  else if (NumArgs > Function->getNumParams()) {
+    const FunctionProtoType *Proto 
+      = Function->getType()->getAsFunctionProtoType();
+    if (!Proto->isVariadic())
+      return TDK_TooManyArguments;
+    
+    CheckArgs = Function->getNumParams();
+  }
+  
+  SFINAETrap Trap(*this);
+  llvm::SmallVector<TemplateArgument, 4> Deduced;
+  Deduced.resize(FunctionTemplate->getTemplateParameters()->size());  
+  TemplateParameterList *TemplateParams
+    = FunctionTemplate->getTemplateParameters();
+  for (unsigned I = 0; I != CheckArgs; ++I) {
+    QualType ParamType = Function->getParamDecl(I)->getType();
+    QualType ArgType = Args[I]->getType();
+
+    // C++ [temp.deduct.call]p2:
+    //   If P is not a reference type:
+    QualType CanonParamType = Context.getCanonicalType(ParamType);
+    if (!isa<ReferenceType>(CanonParamType)) {
+      //   - If A is an array type, the pointer type produced by the 
+      //     array-to-pointer standard conversion (4.2) is used in place of 
+      //     A for type deduction; otherwise,
+      if (ArgType->isArrayType())
+        ArgType = Context.getArrayDecayedType(ArgType);
+      //   - If A is a function type, the pointer type produced by the 
+      //     function-to-pointer standard conversion (4.3) is used in place 
+      //     of A for type deduction; otherwise,
+      else if (ArgType->isFunctionType())
+        ArgType = Context.getPointerType(ArgType);
+      else {
+        // - If A is a cv-qualified type, the top level cv-qualifiers of A’s
+        //   type are ignored for type deduction.
+        QualType CanonArgType = Context.getCanonicalType(ArgType);
+        if (CanonArgType.getCVRQualifiers())
+          ArgType = CanonArgType.getUnqualifiedType();
+      }
+    }
+    
+    // C++0x [temp.deduct.call]p3:
+    //   If P is a cv-qualified type, the top level cv-qualifiers of P’s type
+    //   are ignored for type deduction. 
+    if (CanonParamType.getCVRQualifiers())
+      ParamType = CanonParamType.getUnqualifiedType();
+    if (const ReferenceType *ParamRefType = ParamType->getAsReferenceType()) {
+      //   [...] If P is a reference type, the type referred to by P is used 
+      //   for type deduction. 
+      ParamType = ParamRefType->getPointeeType();
+      
+      //   [...] If P is of the form T&&, where T is a template parameter, and 
+      //   the argument is an lvalue, the type A& is used in place of A for 
+      //   type deduction.
+      if (isa<RValueReferenceType>(ParamRefType) &&
+          ParamRefType->getAsTemplateTypeParmType() &&
+          Args[I]->isLvalue(Context) == Expr::LV_Valid)
+        ArgType = Context.getLValueReferenceType(ArgType);
+    }
+    
+    // C++0x [temp.deduct.call]p4:
+    //   In general, the deduction process attempts to find template argument
+    //   values that will make the deduced A identical to A (after the type A
+    //   is transformed as described above). [...]
+    //
+    // FIXME: we'll pass down a flag to indicate when these cases may apply,
+    // and then deal with them in the code that deduces template
+    // arguments from a type.
+    if (TemplateDeductionResult Result
+        = ::DeduceTemplateArguments(Context, TemplateParams,
+                                    ParamType, ArgType, Info, Deduced))
+      return Result;
+    
+    // FIXME: C++ [temp.deduct.call] paragraphs 6-9 deal with function
+    // pointer parameters. 
+  }
+
+  InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(), 
+                             FunctionTemplate, Deduced.data(), Deduced.size());
+  if (Inst)
+    return TDK_InstantiationDepth;
+  
+  // C++ [temp.deduct.type]p2:
+  //   [...] or if any template argument remains neither deduced nor
+  //   explicitly specified, template argument deduction fails.
+  TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size());
+  for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
+    if (Deduced[I].isNull()) {
+      Decl *Param 
+      = const_cast<Decl *>(TemplateParams->getParam(I));
+      if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
+        Info.Param = TTP;
+      else if (NonTypeTemplateParmDecl *NTTP 
+               = dyn_cast<NonTypeTemplateParmDecl>(Param))
+        Info.Param = NTTP;
+      else
+        Info.Param = cast<TemplateTemplateParmDecl>(Param);
+      return TDK_Incomplete;
+    }
+    
+    Builder.Append(Deduced[I]);
+  }
+  
+  // Form the template argument list from the deduced template arguments.
+  TemplateArgumentList *DeducedArgumentList 
+    = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true);
+  Info.reset(DeducedArgumentList);
+  
+  // Substitute the deduced template arguments into the function template 
+  // declaration to produce the function template specialization.
+  Specialization = cast_or_null<FunctionDecl>(
+                         InstantiateDecl(FunctionTemplate->getTemplatedDecl(),
+                                         FunctionTemplate->getDeclContext(),
+                                         *DeducedArgumentList));
+  
+  if (!Specialization || Trap.hasErrorOccurred())
+    return TDK_SubstitutionFailure;
+
+  return TDK_Success;
+}
+
 static void 
 MarkDeducedTemplateParameters(Sema &SemaRef,
                               const TemplateArgument &TemplateArg,
diff --git a/lib/Sema/SemaTemplateInstantiateDecl.cpp b/lib/Sema/SemaTemplateInstantiateDecl.cpp
index ece71bc0d3..95655d85c3 100644
--- a/lib/Sema/SemaTemplateInstantiateDecl.cpp
+++ b/lib/Sema/SemaTemplateInstantiateDecl.cpp
@@ -44,6 +44,7 @@ namespace {
     Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
     Decl *VisitEnumDecl(EnumDecl *D);
     Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
+    Decl *VisitFunctionDecl(FunctionDecl *D);
     Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
     Decl *VisitCXXMethodDecl(CXXMethodDecl *D);
     Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
@@ -61,6 +62,7 @@ namespace {
     // Helper functions for instantiating methods.
     QualType InstantiateFunctionType(FunctionDecl *D,
                              llvm::SmallVectorImpl<ParmVarDecl *> &Params);
+    bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
     bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
   };
 }
@@ -291,12 +293,47 @@ Decl *TemplateDeclInstantiator::VisitCXXRecordDecl(CXXRecordDecl *D) {
   return Record;
 }
 
-Decl *TemplateDeclInstantiator::VisitCXXMethodDecl(CXXMethodDecl *D) {
-  // Only handle actual methods; we'll deal with constructors,
-  // destructors, etc. separately.
-  if (D->getKind() != Decl::CXXMethod)
+Decl *TemplateDeclInstantiator::VisitFunctionDecl(FunctionDecl *D) {
+  // FIXME: Look for existing specializations (explicit or otherwise).
+  
+  Sema::LocalInstantiationScope Scope(SemaRef);
+  
+  llvm::SmallVector<ParmVarDecl *, 4> Params;
+  QualType T = InstantiateFunctionType(D, Params);
+  if (T.isNull())
     return 0;
+  
+  // Build the instantiated method declaration.
+  FunctionDecl *Function
+    = FunctionDecl::Create(SemaRef.Context, Owner, D->getLocation(), 
+                           D->getDeclName(), T, D->getStorageClass(),
+                           D->isInline(), D->hasWrittenPrototype(),
+                           D->getTypeSpecStartLoc());
+  
+  // FIXME: friend functions
+  
+  // Attach the parameters
+  for (unsigned P = 0; P < Params.size(); ++P)
+    Params[P]->setOwningFunction(Function);
+  Function->setParams(SemaRef.Context, Params.data(), Params.size());
+  
+  if (InitFunctionInstantiation(Function, D))
+    Function->setInvalidDecl();
+  
+  bool Redeclaration = false;
+  bool OverloadableAttrRequired = false;
+  NamedDecl *PrevDecl = 0;
+  SemaRef.CheckFunctionDeclaration(Function, PrevDecl, Redeclaration,
+                                   /*FIXME:*/OverloadableAttrRequired);
+  
+
+  // FIXME: link this to the function template from which it was instantiated.
+  
+  return Function;
+}
 
+Decl *TemplateDeclInstantiator::VisitCXXMethodDecl(CXXMethodDecl *D) {
+  // FIXME: Look for existing, explicit specializations.
   Sema::LocalInstantiationScope Scope(SemaRef);
 
   llvm::SmallVector<ParmVarDecl *, 4> Params;
@@ -340,6 +377,7 @@ Decl *TemplateDeclInstantiator::VisitCXXMethodDecl(CXXMethodDecl *D) {
 }