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

21 files changed, 467 insertions, 75 deletions

diff --git a/include/clang/AST/DeclBase.h b/include/clang/AST/DeclBase.h
index a75eecd022..c959b05473 100644
--- a/include/clang/AST/DeclBase.h
+++ b/include/clang/AST/DeclBase.h
@@ -329,6 +329,9 @@ public:
   /// template parameter pack.
   bool isTemplateParameterPack() const;
 
+  /// \brief Whether this declaration is a function or function template.
+  bool isFunctionOrFunctionTemplate() const;
+  
   // Implement isa/cast/dyncast/etc.
   static bool classof(const Decl *) { return true; }
   static DeclContext *castToDeclContext(const Decl *);
diff --git a/include/clang/AST/DeclCXX.h b/include/clang/AST/DeclCXX.h
index 84a49d7882..4e006c08ea 100644
--- a/include/clang/AST/DeclCXX.h
+++ b/include/clang/AST/DeclCXX.h
@@ -27,6 +27,40 @@ class CXXConversionDecl;
 class CXXMethodDecl;
 class ClassTemplateSpecializationDecl;
 
+/// \brief Represents any kind of function declaration, whether it is a 
+/// concrete function or a function template.
+class AnyFunctionDecl {
+  NamedDecl *Function;
+  
+public:
+  AnyFunctionDecl(FunctionDecl *FD) : Function(FD) { }
+  AnyFunctionDecl(FunctionTemplateDecl *FTD);
+  
+  /// \brief Implicily converts any function or function template into a 
+  /// named declaration.
+  operator NamedDecl *() const { return Function; }
+  
+  /// \brief Retrieve the underlying function or function template.
+  NamedDecl *get() const { return Function; }
+};
+  
+} // end namespace clang
+
+namespace llvm {
+  /// Implement simplify_type for AnyFunctionDecl, so that we can dyn_cast from 
+  /// AnyFunctionDecl to any function or function template declaration.
+  template<> struct simplify_type<const ::clang::AnyFunctionDecl> {
+    typedef ::clang::NamedDecl* SimpleType;
+    static SimpleType getSimplifiedValue(const ::clang::AnyFunctionDecl &Val) {
+      return Val;
+    }
+  };
+  template<> struct simplify_type< ::clang::AnyFunctionDecl>
+  : public simplify_type<const ::clang::AnyFunctionDecl> {};
+} // end namespace llvm
+
+namespace clang {
+  
 /// OverloadedFunctionDecl - An instance of this class represents a
 /// set of overloaded functions. All of the functions have the same
 /// name and occur within the same scope.
@@ -43,15 +77,15 @@ protected:
 
   /// Functions - the set of overloaded functions contained in this
   /// overload set.
-  llvm::SmallVector<FunctionDecl *, 4> Functions;
+  llvm::SmallVector<AnyFunctionDecl, 4> Functions;
 
   // FIXME: This should go away when we stop using
   // OverloadedFunctionDecl to store conversions in CXXRecordDecl.
   friend class CXXRecordDecl;
 
 public:
-  typedef llvm::SmallVector<FunctionDecl *, 4>::iterator function_iterator;
-  typedef llvm::SmallVector<FunctionDecl *, 4>::const_iterator
+  typedef llvm::SmallVector<AnyFunctionDecl, 4>::iterator function_iterator;
+  typedef llvm::SmallVector<AnyFunctionDecl, 4>::const_iterator
     function_const_iterator;
 
   static OverloadedFunctionDecl *Create(ASTContext &C, DeclContext *DC,
@@ -71,30 +105,18 @@ public:
       this->setLocation(FD->getLocation());
   }
 
+  /// addOverload - Add an overloaded function template FTD to this set of
+  /// overloaded functions.
+  void addOverload(FunctionTemplateDecl *FTD);
+  
   function_iterator function_begin() { return Functions.begin(); }
   function_iterator function_end() { return Functions.end(); }
   function_const_iterator function_begin() const { return Functions.begin(); }
   function_const_iterator function_end() const { return Functions.end(); }
 
-  /// getNumFunctions - the number of overloaded functions stored in
+  /// \brief Returns the number of overloaded functions stored in
   /// this set.
-  unsigned getNumFunctions() const { return Functions.size(); }
-
-  /// getFunction - retrieve the ith function in the overload set.
-  const FunctionDecl *getFunction(unsigned i) const {
-    assert(i < getNumFunctions() && "Illegal function #");
-    return Functions[i];
-  }
-  FunctionDecl *getFunction(unsigned i) {
-    assert(i < getNumFunctions() && "Illegal function #");
-    return Functions[i];
-  }
-
-  // getDeclContext - Get the context of these overloaded functions.
-  DeclContext *getDeclContext() {
-    assert(getNumFunctions() > 0 && "Context of an empty overload set");
-    return getFunction(0)->getDeclContext();
-  }
+  unsigned size() const { return Functions.size(); }
 
   // Implement isa/cast/dyncast/etc.
   static bool classof(const Decl *D) { 
diff --git a/include/clang/AST/DeclTemplate.h b/include/clang/AST/DeclTemplate.h
index 2608dd9d31..c64c974183 100644
--- a/include/clang/AST/DeclTemplate.h
+++ b/include/clang/AST/DeclTemplate.h
@@ -957,6 +957,10 @@ public:
   virtual void Destroy(ASTContext& C);
 };
 
+/// Implementation of inline functions that require the template declarations
+inline AnyFunctionDecl::AnyFunctionDecl(FunctionTemplateDecl *FTD) 
+  : Function(FTD) { }
+
 } /* end of namespace clang */
 
 #endif
diff --git a/include/clang/Basic/DiagnosticSemaKinds.td b/include/clang/Basic/DiagnosticSemaKinds.td
index babcc2660b..927f6b95f3 100644
--- a/include/clang/Basic/DiagnosticSemaKinds.td
+++ b/include/clang/Basic/DiagnosticSemaKinds.td
@@ -704,14 +704,15 @@ def err_template_arg_must_be_expr : Error<
 def err_template_arg_nontype_ambig : Error<
   "template argument for non-type template parameter is treated as type %0">;
 def err_template_arg_must_be_template : Error<
-  "template argument for template template parameter must be a template">;
+  "template argument for template template parameter must be a class template">;
 def err_template_arg_local_type : Error<"template argument uses local type %0">;
 def err_template_arg_unnamed_type : Error<
   "template argument uses unnamed type">;
 def note_template_unnamed_type_here : Note<
   "unnamed type used in template argument was declared here">;
 def err_template_arg_not_class_template : Error<
-  "template argument does not refer to a class template">;
+  "template argument does not refer to a class template or template "
+  "template parameter">;
 def note_template_arg_refers_here_func : Note<
   "template argument refers to function template %0, here">;
 def err_template_arg_template_params_mismatch : Error<
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,
+