Implement support for operator overloading using candidate operator

functions for built-in operators, e.g., the builtin

  bool operator==(int const*, int const*)

can be used for the expression "x1 == x2" given:

  struct X {
    operator int const*();
  } x1, x2;

The scheme for handling these built-in operators is relatively simple:
for each candidate required by the standard, create a special kind of
candidate function for the built-in. If overload resolution picks the
built-in operator, we perform the appropriate conversions on the
arguments and then let the normal built-in operator take care of it. 

There may be some optimization opportunity left: if we can reduce the
number of built-in operator overloads we generate, overload resolution
for these cases will go faster. However, one must be careful when
doing this: GCC generates too few operator overloads in our little
test program, and fails to compile it because none of the overloads it
generates match.

Note that we only support operator overload for non-member binary
operators at the moment. The other operators will follow.

As part of this change, ImplicitCastExpr can now be an lvalue.





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

14 files changed, 837 insertions, 75 deletions

diff --git a/Driver/RewriteObjC.cpp b/Driver/RewriteObjC.cpp
index 9d78c42d02..65e8841ec7 100644
--- a/Driver/RewriteObjC.cpp
+++ b/Driver/RewriteObjC.cpp
@@ -1519,7 +1519,8 @@ CallExpr *RewriteObjC::SynthesizeCallToFunctionDecl(
                                      
   // Now, we cast the reference to a pointer to the objc_msgSend type.
   QualType pToFunc = Context->getPointerType(msgSendType);
-  ImplicitCastExpr *ICE = new ImplicitCastExpr(pToFunc, DRE);
+  ImplicitCastExpr *ICE = new ImplicitCastExpr(pToFunc, DRE, 
+                                               /*isLvalue=*/false);
   
   const FunctionType *FT = msgSendType->getAsFunctionType();
   
diff --git a/include/clang/AST/Expr.h b/include/clang/AST/Expr.h
index efab1a14e1..6fe205cd08 100644
--- a/include/clang/AST/Expr.h
+++ b/include/clang/AST/Expr.h
@@ -834,14 +834,23 @@ public:
 /// (*f)(), float->double, short->int, etc.
 ///
 class ImplicitCastExpr : public CastExpr {
+  /// LvalueCast - Whether this cast produces an lvalue.
+  bool LvalueCast;
+
 public:
-  ImplicitCastExpr(QualType ty, Expr *op) : 
-    CastExpr(ImplicitCastExprClass, ty, op) {}
+  ImplicitCastExpr(QualType ty, Expr *op, bool Lvalue) : 
+    CastExpr(ImplicitCastExprClass, ty, op), LvalueCast(Lvalue) {}
 
   virtual SourceRange getSourceRange() const {
     return getSubExpr()->getSourceRange();
   }
 
+  /// isLvalueCast - Whether this cast produces an lvalue.
+  bool isLvalueCast() const { return LvalueCast; }
+
+  /// setLvalueCast - Set whether this cast produces an lvalue.
+  void setLvalueCast(bool Lvalue) { LvalueCast = Lvalue; }
+
   static bool classof(const Stmt *T) { 
     return T->getStmtClass() == ImplicitCastExprClass; 
   }
diff --git a/include/clang/AST/TypeOrdering.h b/include/clang/AST/TypeOrdering.h
index a21655b580..a23ca75ff0 100644
--- a/include/clang/AST/TypeOrdering.h
+++ b/include/clang/AST/TypeOrdering.h
@@ -7,9 +7,9 @@
 //
 //===----------------------------------------------------------------------===//
 //
-//  This file provides a function object that gives a total ordering
-//  on QualType values, so that they can be sorted, used in std::maps
-//  and std::sets, and so on.
+//  This file provides a function objects and specializations that
+//  allow QualType values to be sorted, used in std::maps, std::sets,
+//  llvm::DenseMaps, and llvm::DenseSets.
 //
 //===----------------------------------------------------------------------===//
 
@@ -17,6 +17,7 @@
 #define LLVM_CLANG_TYPE_ORDERING_H
 
 #include "clang/AST/Type.h"
+#include "llvm/ADT/DenseMap.h"
 #include <functional>
 
 namespace clang {
@@ -31,4 +32,30 @@ struct QualTypeOrdering : std::binary_function<QualType, QualType, bool> {
 
 }
 
+namespace llvm {
+  template<> struct DenseMapInfo<clang::QualType> {
+    static inline clang::QualType getEmptyKey() { return clang::QualType(); }
+
+    static inline clang::QualType getTombstoneKey() { 
+      using clang::QualType;
+      return QualType::getFromOpaquePtr(reinterpret_cast<clang::Type *>(-1));
+    }
+
+    static unsigned getHashValue(clang::QualType Val) {
+      return (unsigned)Val.getAsOpaquePtr();
+    }
+
+    static bool isEqual(clang::QualType LHS, clang::QualType RHS) {
+      return LHS == RHS;
+    }
+
+    static bool isPod() { 
+      // QualType isn't *technically* a POD type. However, we can get
+      // away with calling it a POD type since its copy constructor,
+      // copy assignment operator, and destructor are all trivial.
+      return true; 
+    }
+  };
+}
+
 #endif
diff --git a/include/clang/Basic/DiagnosticKinds.def b/include/clang/Basic/DiagnosticKinds.def
index 8d821e4362..451e8de630 100644
--- a/include/clang/Basic/DiagnosticKinds.def
+++ b/include/clang/Basic/DiagnosticKinds.def
@@ -867,6 +867,8 @@ DIAG(err_ovl_ambiguous_call, ERROR,
      "call to '%0' is ambiguous; candidates are:")
 DIAG(err_ovl_candidate, NOTE,
      "candidate function")
+DIAG(err_ovl_builtin_candidate, NOTE,
+     "built-in candidate function '%0'")
 DIAG(err_ovl_no_viable_function_in_init, ERROR,
      "no matching constructor for initialization of '%0'.")
 DIAG(err_ovl_no_viable_function_in_init_with_cands, ERROR,
diff --git a/lib/AST/Expr.cpp b/lib/AST/Expr.cpp
index fbb225613f..c54fc40ecb 100644
--- a/lib/AST/Expr.cpp
+++ b/lib/AST/Expr.cpp
@@ -389,8 +389,28 @@ Expr::isLvalueResult Expr::isLvalue(ASTContext &Ctx) const {
         cast<UnaryOperator>(this)->getOpcode() == UnaryOperator::Extension)
       return cast<UnaryOperator>(this)->getSubExpr()->isLvalue(Ctx);  // GNU.
     break;
+  case ImplicitCastExprClass:
+    return cast<ImplicitCastExpr>(this)->isLvalueCast()? LV_Valid 
+                                                       : LV_InvalidExpression;
   case ParenExprClass: // C99 6.5.1p5
     return cast<ParenExpr>(this)->getSubExpr()->isLvalue(Ctx);
+  case BinaryOperatorClass:
+  case CompoundAssignOperatorClass: {
+    const BinaryOperator *BinOp = cast<BinaryOperator>(this);
+    if (BinOp->isAssignmentOp()) {
+      if (Ctx.getLangOptions().CPlusPlus)
+        // C++ [expr.ass]p1: 
+        //   The result of an assignment operation [...] is an lvalue.
+        return LV_Valid;
+      else 
+        // C99 6.5.16:
+        //   An assignment expression [...] is not an lvalue.
+        return LV_InvalidExpression;
+    } else
+      return LV_InvalidExpression;
+
+    break;
+  }
   case CallExprClass: {
     // C++ [expr.call]p10:
     //   A function call is an lvalue if and only if the result type
diff --git a/lib/AST/StmtSerialization.cpp b/lib/AST/StmtSerialization.cpp
index f71b88b46f..667f597b8a 100644
--- a/lib/AST/StmtSerialization.cpp
+++ b/lib/AST/StmtSerialization.cpp
@@ -662,12 +662,14 @@ ImaginaryLiteral* ImaginaryLiteral::CreateImpl(Deserializer& D, ASTContext& C) {
 void ImplicitCastExpr::EmitImpl(Serializer& S) const {
   S.Emit(getType());
   S.EmitOwnedPtr(getSubExpr());
+  S.Emit(LvalueCast);
 }
 
 ImplicitCastExpr* ImplicitCastExpr::CreateImpl(Deserializer& D, ASTContext& C) {
   QualType t = QualType::ReadVal(D);
   Expr* Op = D.ReadOwnedPtr<Expr>(C);
-  return new ImplicitCastExpr(t,Op);
+  bool isLvalue = D.ReadBool();
+  return new ImplicitCastExpr(t,Op,isLvalue);
 }
 
 void IndirectGotoStmt::EmitImpl(Serializer& S) const {
diff --git a/lib/Sema/Sema.cpp b/lib/Sema/Sema.cpp
index 9c8d0c8bcb..b78336b6cd 100644
--- a/lib/Sema/Sema.cpp
+++ b/lib/Sema/Sema.cpp
@@ -124,7 +124,8 @@ Sema::Sema(Preprocessor &pp, ASTContext &ctxt, ASTConsumer &consumer)
 
 /// ImpCastExprToType - If Expr is not of type 'Type', insert an implicit cast. 
 /// If there is already an implicit cast, merge into the existing one.
-void Sema::ImpCastExprToType(Expr *&Expr, QualType Ty) {
+  /// If isLvalue, the result of the cast is an lvalue.
+void Sema::ImpCastExprToType(Expr *&Expr, QualType Ty, bool isLvalue) {
   QualType ExprTy = Context.getCanonicalType(Expr->getType());
   QualType TypeTy = Context.getCanonicalType(Ty);
   
@@ -143,10 +144,11 @@ void Sema::ImpCastExprToType(Expr *&Expr, QualType Ty) {
     }
   }
   
-  if (ImplicitCastExpr *ImpCast = dyn_cast<ImplicitCastExpr>(Expr))
+  if (ImplicitCastExpr *ImpCast = dyn_cast<ImplicitCastExpr>(Expr)) {
     ImpCast->setType(Ty);
-  else 
-    Expr = new ImplicitCastExpr(Ty, Expr);
+    ImpCast->setLvalueCast(isLvalue);
+  } else 
+    Expr = new ImplicitCastExpr(Ty, Expr, isLvalue);
 }
 
 void Sema::DeleteExpr(ExprTy *E) {
diff --git a/lib/Sema/Sema.h b/lib/Sema/Sema.h
index 7cd507a0aa..5b66694e04 100644
--- a/lib/Sema/Sema.h
+++ b/lib/Sema/Sema.h
@@ -435,6 +435,12 @@ public:
   void AddConversionCandidate(CXXConversionDecl *Conversion,
                               Expr *From, QualType ToType,
                               OverloadCandidateSet& CandidateSet);
+  void AddBuiltinCandidate(QualType ResultTy, QualType *ParamTys, 
+                           Expr **Args, unsigned NumArgs,
+                           OverloadCandidateSet& CandidateSet);
+  void AddBuiltinBinaryOperatorCandidates(OverloadedOperatorKind Op, 
+                                          Expr **Args, 
+                                          OverloadCandidateSet& CandidateSet);
   void AddOverloadCandidates(const OverloadedFunctionDecl *Ovl, 
                              Expr **Args, unsigned NumArgs,
                              OverloadCandidateSet& CandidateSet,
@@ -1052,16 +1058,13 @@ public:
 
   /// ImpCastExprToType - If Expr is not of type 'Type', insert an implicit
   /// cast.  If there is already an implicit cast, merge into the existing one.
-  void ImpCastExprToType(Expr *&Expr, QualType Type);
+  /// If isLvalue, the result of the cast is an lvalue.
+  void ImpCastExprToType(Expr *&Expr, QualType Type, bool isLvalue = false);
 
   // UsualUnaryConversions - promotes integers (C99 6.3.1.1p2) and converts
   // functions and arrays to their respective pointers (C99 6.3.2.1).
   Expr *UsualUnaryConversions(Expr *&expr); 
 
-  // UsualUnaryConversionType - Same as UsualUnaryConversions, but works
-  // on types instead of expressions
-  QualType UsualUnaryConversionType(QualType Ty); 
-  
   // DefaultFunctionArrayConversion - converts functions and arrays
   // to their respective pointers (C99 6.3.2.1). 
   void DefaultFunctionArrayConversion(Expr *&expr);
@@ -1079,6 +1082,12 @@ public:
   QualType UsualArithmeticConversions(Expr *&lExpr, Expr *&rExpr,
                                       bool isCompAssign = false);
   
+  /// UsualArithmeticConversionsType - handles the various conversions
+  /// that are common to binary operators (C99 6.3.1.8, C++ [expr]p9)
+  /// and returns the result type of that conversion.
+  QualType UsualArithmeticConversionsType(QualType lhs, QualType rhs);
+                                          
+
   /// AssignConvertType - All of the 'assignment' semantic checks return this
   /// enum to indicate whether the assignment was allowed.  These checks are
   /// done for simple assignments, as well as initialization, return from
diff --git a/lib/Sema/SemaDecl.cpp b/lib/Sema/SemaDecl.cpp
index fc412a605e..aaceb4f559 100644
--- a/lib/Sema/SemaDecl.cpp
+++ b/lib/Sema/SemaDecl.cpp
@@ -3021,7 +3021,8 @@ void Sema::ActOnEnumBody(SourceLocation EnumLoc, DeclTy *EnumDeclX,
     ECD->setInitVal(InitVal);
     
     // Adjust the Expr initializer and type.
-    ECD->setInitExpr(new ImplicitCastExpr(NewTy, ECD->getInitExpr()));
+    ECD->setInitExpr(new ImplicitCastExpr(NewTy, ECD->getInitExpr(), 
+                                          /*isLvalue=*/false));
     ECD->setType(NewTy);
   }
   
diff --git a/lib/Sema/SemaDeclCXX.cpp b/lib/Sema/SemaDeclCXX.cpp
index 2f43e5fa9e..128df11385 100644
--- a/lib/Sema/SemaDeclCXX.cpp
+++ b/lib/Sema/SemaDeclCXX.cpp
@@ -1597,7 +1597,7 @@ Sema::CheckReferenceInit(Expr *&Init, QualType &DeclType,
       // Perform the conversion.
       // FIXME: Binding to a subobject of the lvalue is going to require
       // more AST annotation than this.
-      ImpCastExprToType(Init, T1);    
+      ImpCastExprToType(Init, T1, /*isLvalue=*/true);    
     }
   }
 
@@ -1656,7 +1656,7 @@ Sema::CheckReferenceInit(Expr *&Init, QualType &DeclType,
         // Perform the conversion.
         // FIXME: Binding to a subobject of the lvalue is going to require
         // more AST annotation than this.
-        ImpCastExprToType(Init, T1);
+        ImpCastExprToType(Init, T1, /*isLvalue=*/true);
       }
       break;
 
@@ -1741,7 +1741,7 @@ Sema::CheckReferenceInit(Expr *&Init, QualType &DeclType,
     } else {
       // FIXME: Binding to a subobject of the rvalue is going to require
       // more AST annotation than this.
-      ImpCastExprToType(Init, T1);
+      ImpCastExprToType(Init, T1, /*isLvalue=*/true);
     }
     return false;
   }
diff --git a/lib/Sema/SemaExpr.cpp b/lib/Sema/SemaExpr.cpp
index 92efa68cc4..21bf990fba 100644
--- a/lib/Sema/SemaExpr.cpp
+++ b/lib/Sema/SemaExpr.cpp
@@ -99,13 +99,47 @@ QualType Sema::UsualArithmeticConversions(Expr *&lhsExpr, Expr *&rhsExpr,
     UsualUnaryConversions(lhsExpr);
     UsualUnaryConversions(rhsExpr);
   }
+
   // For conversion purposes, we ignore any qualifiers. 
   // For example, "const float" and "float" are equivalent.
   QualType lhs =
     Context.getCanonicalType(lhsExpr->getType()).getUnqualifiedType();
   QualType rhs = 
     Context.getCanonicalType(rhsExpr->getType()).getUnqualifiedType();
-  
+
+  // If both types are identical, no conversion is needed.
+  if (lhs == rhs)
+    return lhs;
+
+  // If either side is a non-arithmetic type (e.g. a pointer), we are done.
+  // The caller can deal with this (e.g. pointer + int).
+  if (!lhs->isArithmeticType() || !rhs->isArithmeticType())
+    return lhs;
+
+  QualType destType = UsualArithmeticConversionsType(lhs, rhs);
+  if (!isCompAssign) {
+    ImpCastExprToType(lhsExpr, destType);
+    ImpCastExprToType(rhsExpr, destType);
+  }
+  return destType;
+}
+
+QualType Sema::UsualArithmeticConversionsType(QualType lhs, QualType rhs) {
+  // Perform the usual unary conversions. We do this early so that
+  // integral promotions to "int" can allow us to exit early, in the
+  // lhs == rhs check. Also, for conversion purposes, we ignore any
+  // qualifiers.  For example, "const float" and "float" are
+  // equivalent.
+  if (lhs->isPromotableIntegerType())
+    lhs = Context.IntTy;
+  else
+    lhs = Context.getCanonicalType(lhs).getUnqualifiedType();
+
+  if (rhs->isPromotableIntegerType())
+    rhs = Context.IntTy;
+  else
+    rhs = Context.getCanonicalType(rhs).getUnqualifiedType();
+
   // If both types are identical, no conversion is needed.
   if (lhs == rhs)
     return lhs;
@@ -122,12 +156,10 @@ QualType Sema::UsualArithmeticConversions(Expr *&lhsExpr, Expr *&rhsExpr,
     // if we have an integer operand, the result is the complex type.
     if (rhs->isIntegerType() || rhs->isComplexIntegerType()) { 
       // convert the rhs to the lhs complex type.
-      if (!isCompAssign) ImpCastExprToType(rhsExpr, lhs);
       return lhs;
     }
     if (lhs->isIntegerType() || lhs->isComplexIntegerType()) { 
       // convert the lhs to the rhs complex type.
-      if (!isCompAssign) ImpCastExprToType(lhsExpr, rhs);
       return rhs;
     }
     // This handles complex/complex, complex/float, or float/complex.
@@ -144,24 +176,16 @@ QualType Sema::UsualArithmeticConversions(Expr *&lhsExpr, Expr *&rhsExpr,
     
     if (result > 0) { // The left side is bigger, convert rhs. 
       rhs = Context.getFloatingTypeOfSizeWithinDomain(lhs, rhs);
-      if (!isCompAssign)
-        ImpCastExprToType(rhsExpr, rhs);
     } else if (result < 0) { // The right side is bigger, convert lhs. 
       lhs = Context.getFloatingTypeOfSizeWithinDomain(rhs, lhs);
-      if (!isCompAssign)
-        ImpCastExprToType(lhsExpr, lhs);
     } 
     // At this point, lhs and rhs have the same rank/size. Now, make sure the
     // domains match. This is a requirement for our implementation, C99
     // does not require this promotion.
     if (lhs != rhs) { // Domains don't match, we have complex/float mix.
       if (lhs->isRealFloatingType()) { // handle "double, _Complex double".
-        if (!isCompAssign)
-          ImpCastExprToType(lhsExpr, rhs);
         return rhs;
       } else { // handle "_Complex double, double".
-        if (!isCompAssign)
-          ImpCastExprToType(rhsExpr, lhs);
         return lhs;
       }
     }
@@ -172,12 +196,10 @@ QualType Sema::UsualArithmeticConversions(Expr *&lhsExpr, Expr *&rhsExpr,
     // if we have an integer operand, the result is the real floating type.
     if (rhs->isIntegerType() || rhs->isComplexIntegerType()) { 
       // convert rhs to the lhs floating point type.
-      if (!isCompAssign) ImpCastExprToType(rhsExpr, lhs);
       return lhs;
     }
     if (lhs->isIntegerType() || lhs->isComplexIntegerType()) { 
       // convert lhs to the rhs floating point type.
-      if (!isCompAssign) ImpCastExprToType(lhsExpr, rhs);
       return rhs;
     }
     // We have two real floating types, float/complex combos were handled above.
@@ -185,14 +207,12 @@ QualType Sema::UsualArithmeticConversions(Expr *&lhsExpr, Expr *&rhsExpr,
     int result = Context.getFloatingTypeOrder(lhs, rhs);
     
     if (result > 0) { // convert the rhs
-      if (!isCompAssign) ImpCastExprToType(rhsExpr, lhs);
       return lhs;
     }
     if (result < 0) { // convert the lhs
-      if (!isCompAssign) ImpCastExprToType(lhsExpr, rhs); // convert the lhs
       return rhs;
     }
-    assert(0 && "Sema::UsualArithmeticConversions(): illegal float comparison");
+    assert(0 && "Sema::UsualArithmeticConversionsType(): illegal float comparison");
   }
   if (lhs->isComplexIntegerType() || rhs->isComplexIntegerType()) {
     // Handle GCC complex int extension.
@@ -203,19 +223,14 @@ QualType Sema::UsualArithmeticConversions(Expr *&lhsExpr, Expr *&rhsExpr,
       if (Context.getIntegerTypeOrder(lhsComplexInt->getElementType(), 
                                       rhsComplexInt->getElementType()) >= 0) {
         // convert the rhs
-        if (!isCompAssign) ImpCastExprToType(rhsExpr, lhs);
         return lhs;
       }
-      if (!isCompAssign) 
-        ImpCastExprToType(lhsExpr, rhs); // convert the lhs
       return rhs;
     } else if (lhsComplexInt && rhs->isIntegerType()) {
       // convert the rhs to the lhs complex type.
-      if (!isCompAssign) ImpCastExprToType(rhsExpr, lhs);
       return lhs;
     } else if (rhsComplexInt && lhs->isIntegerType()) {
       // convert the lhs to the rhs complex type.
-      if (!isCompAssign) ImpCastExprToType(lhsExpr, rhs);
       return rhs;
     }
   }
@@ -244,10 +259,6 @@ QualType Sema::UsualArithmeticConversions(Expr *&lhsExpr, Expr *&rhsExpr,
     // to the signed type.
     destType = Context.getCorrespondingUnsignedType(lhsSigned ? lhs : rhs);
   }
-  if (!isCompAssign) {
-    ImpCastExprToType(lhsExpr, destType);
-    ImpCastExprToType(rhsExpr, destType);
-  }
   return destType;
 }
 
@@ -2765,6 +2776,14 @@ Action::ExprResult Sema::ActOnBinOp(Scope *S, SourceLocation TokLoc,
   if (getLangOptions().CPlusPlus &&
       (lhs->getType()->isRecordType() || lhs->getType()->isEnumeralType() ||
        rhs->getType()->isRecordType() || rhs->getType()->isEnumeralType())) {
+    // If this is one of the assignment operators, we only perform
+    // overload resolution if the left-hand side is a class or
+    // enumeration type (C++ [expr.ass]p3).
+    if (Opc >= BinaryOperator::Assign && Opc <= BinaryOperator::OrAssign &&
+        !(lhs->getType()->isRecordType() || lhs->getType()->isEnumeralType())) {
+      return CreateBuiltinBinOp(TokLoc, Opc, lhs, rhs);
+    }
+
     // C++ [over.binary]p1:
     //   A binary operator shall be implemented either by a non-static
     //   member function (9.3) with one parameter or by a non-member
@@ -2809,40 +2828,57 @@ Action::ExprResult Sema::ActOnBinOp(Scope *S, SourceLocation TokLoc,
                = dyn_cast_or_null<OverloadedFunctionDecl>(D))
       AddOverloadCandidates(Ovl, Args, 2, CandidateSet);
 
-    // FIXME: Add builtin overload candidates (C++ [over.built]).
+    // Add builtin overload candidates (C++ [over.built]).
+    AddBuiltinBinaryOperatorCandidates(OverOp, Args, CandidateSet);
 
     // Perform overload resolution.
     OverloadCandidateSet::iterator Best;
     switch (BestViableFunction(CandidateSet, Best)) {
     case OR_Success: {
-      // FIXME: We might find a built-in candidate here.
+      // We found a built-in operator or an overloaded operator.
       FunctionDecl *FnDecl = Best->Function;
 
-      // Convert the arguments.
-      // FIXME: Conversion will be different for member operators.
-      if (PerformCopyInitialization(lhs, FnDecl->getParamDecl(0)->getType(),
-                                    "passing") ||
-          PerformCopyInitialization(rhs, FnDecl->getParamDecl(1)->getType(),
-                                    "passing"))
-        return true;
-
-      // Determine the result type
-      QualType ResultTy 
-        = FnDecl->getType()->getAsFunctionType()->getResultType();
-      ResultTy = ResultTy.getNonReferenceType();
-
-      // Build the actual expression node.
-      // FIXME: We lose the fact that we have a function here!
-      if (Opc > BinaryOperator::Assign && Opc <= BinaryOperator::OrAssign)
-        return new CompoundAssignOperator(lhs, rhs, Opc, ResultTy, ResultTy,
-                                          TokLoc);
-      else
-        return new BinaryOperator(lhs, rhs, Opc, ResultTy, TokLoc);
+      if (FnDecl) {
+        // We matched an overloaded operator. Build a call to that
+        // operator.
+
+        // Convert the arguments.
+        // FIXME: Conversion will be different for member operators.
+        if (PerformCopyInitialization(lhs, FnDecl->getParamDecl(0)->getType(),
+                                      "passing") ||
+            PerformCopyInitialization(rhs, FnDecl->getParamDecl(1)->getType(),
+                                      "passing"))
+          return true;
+
+        // Determine the result type
+        QualType ResultTy 
+          = FnDecl->getType()->getAsFunctionType()->getResultType();
+        ResultTy = ResultTy.getNonReferenceType();
+        
+        // Build the actual expression node.
+        // FIXME: We lose the fact that we have a function here!
+        if (Opc > BinaryOperator::Assign && Opc <= BinaryOperator::OrAssign)
+          return new CompoundAssignOperator(lhs, rhs, Opc, ResultTy, ResultTy,
+                                            TokLoc);
+        else
+          return new BinaryOperator(lhs, rhs, Opc, ResultTy, TokLoc);
+      } else {
+        // We matched a built-in operator. Convert the arguments, then
+        // break out so that we will build the appropriate built-in
+        // operator node.
+        if (PerformCopyInitialization(lhs, Best->BuiltinTypes.ParamTypes[0],
+                                      "passing") ||
+            PerformCopyInitialization(rhs, Best->BuiltinTypes.ParamTypes[1],
+                                      "passing"))
+          return true;
+
+        break;
+      } 
     }
 
     case OR_No_Viable_Function:
       // No viable function; fall through to handling this as a
-      // built-in operator.
+      // built-in operator, which will produce an error message for us.
       break;
 
     case OR_Ambiguous:
@@ -2854,7 +2890,9 @@ Action::ExprResult Sema::ActOnBinOp(Scope *S, SourceLocation TokLoc,
       return true;
     }
 
-    // There was no viable overloaded operator; fall through.
+    // Either we found no viable overloaded operator or we matched a
+    // built-in operator. In either case, fall through to trying to
+    // build a built-in operation.
   } 
 
   
diff --git a/lib/Sema/SemaOverload.cpp b/lib/Sema/SemaOverload.cpp
index b60e55492b..9229fa35d2 100644
--- a/lib/Sema/SemaOverload.cpp
+++ b/lib/Sema/SemaOverload.cpp
@@ -14,8 +14,11 @@
 #include "Sema.h"
 #include "SemaInherit.h"
 #include "clang/Basic/Diagnostic.h"
+#include "clang/Lex/Preprocessor.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Expr.h"
+#include "clang/AST/TypeOrdering.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/Compiler.h"
 #include <algorithm>
 
@@ -413,6 +416,7 @@ Sema::IsStandardConversion(Expr* From, QualType ToType,
     return false;
 
   // Standard conversions (C++ [conv])
+  SCS.setAsIdentityConversion();
   SCS.Deprecated = false;
   SCS.FromTypePtr = FromType.getAsOpaquePtr();
   SCS.CopyConstructor = 0;
@@ -1530,7 +1534,7 @@ Sema::AddConversionCandidate(CXXConversionDecl *Conversion,
   DeclRefExpr ConversionRef(Conversion, Conversion->getType(), 
                             SourceLocation());
   ImplicitCastExpr ConversionFn(Context.getPointerType(Conversion->getType()),
-                                &ConversionRef);
+                                &ConversionRef, false);
   CallExpr Call(&ConversionFn, 0, 0, 
                 Conversion->getConversionType().getNonReferenceType(),
                 SourceLocation());
@@ -1550,6 +1554,562 @@ Sema::AddConversionCandidate(CXXConversionDecl *Conversion,
   }
 }
 
+/// AddBuiltinCandidate - Add a candidate for a built-in
+/// operator. ResultTy and ParamTys are the result and parameter types
+/// of the built-in candidate, respectively. Args and NumArgs are the
+/// arguments being passed to the candidate.
+void Sema::AddBuiltinCandidate(QualType ResultTy, QualType *ParamTys, 
+                               Expr **Args, unsigned NumArgs,
+                               OverloadCandidateSet& CandidateSet) {
+  // Add this candidate
+  CandidateSet.push_back(OverloadCandidate());
+  OverloadCandidate& Candidate = CandidateSet.back();
+  Candidate.Function = 0;
+  Candidate.BuiltinTypes.ResultTy = ResultTy;
+  for (unsigned ArgIdx = 0; ArgIdx < NumArgs; ++ArgIdx)
+    Candidate.BuiltinTypes.ParamTypes[ArgIdx] = ParamTys[ArgIdx];
+
+  // Determine the implicit conversion sequences for each of the
+  // arguments.
+  Candidate.Viable = true;
+  Candidate.Conversions.resize(NumArgs);
+  for (unsigned ArgIdx = 0; ArgIdx < NumArgs; ++ArgIdx) {
+    Candidate.Conversions[ArgIdx] 
+      = TryCopyInitialization(Args[ArgIdx], ParamTys[ArgIdx], false);
+    if (Candidate.Conversions[ArgIdx].ConversionKind 
+        == ImplicitConversionSequence::BadConversion)
+      Candidate.Viable = false;
+  }
+}
+
+/// BuiltinCandidateTypeSet - A set of types that will be used for the
+/// candidate operator functions for built-in operators (C++
+/// [over.built]). The types are separated into pointer types and
+/// enumeration types.
+class BuiltinCandidateTypeSet  {
+  /// TypeSet - A set of types.
+  typedef llvm::DenseSet<QualType> TypeSet;
+
+  /// PointerTypes - The set of pointer types that will be used in the
+  /// built-in candidates.
+  TypeSet PointerTypes;
+
+  /// EnumerationTypes - The set of enumeration types that will be
+  /// used in the built-in candidates.
+  TypeSet EnumerationTypes;
+
+  /// Context - The AST context in which we will build the type sets.
+  ASTContext &Context;
+
+  bool AddWithMoreQualifiedTypeVariants(QualType Ty);
+
+public:
+  /// iterator - Iterates through the types that are part of the set.
+  typedef TypeSet::iterator iterator;
+
+  BuiltinCandidateTypeSet(ASTContext &Context) : Context(Context) { }
+
+  void AddTypesConvertedFrom(QualType Ty, bool AllowUserConversions = true);
+
+  /// pointer_begin - First pointer type found;
+  iterator pointer_begin() { return PointerTypes.begin(); }
+
+  /// pointer_end - Last pointer type found;
+  iterator pointer_end() { return PointerTypes.end(); }
+
+  /// enumeration_begin - First enumeration type found;
+  iterator enumeration_begin() { return EnumerationTypes.begin(); }
+
+  /// enumeration_end - Last enumeration type found;
+  iterator enumeration_end() { return EnumerationTypes.end(); }
+};
+
+/// AddWithMoreQualifiedTypeVariants - Add the pointer type @p Ty to
+/// the set of pointer types along with any more-qualified variants of
+/// that type. For example, if @p Ty is "int const *", this routine
+/// will add "int const *", "int const volatile *", "int const
+/// restrict *", and "int const volatile restrict *" to the set of
+/// pointer types. Returns true if the add of @p Ty itself succeeded,
+/// false otherwise.
+bool BuiltinCandidateTypeSet::AddWithMoreQualifiedTypeVariants(QualType Ty) {
+  // Insert this type.
+  if (!PointerTypes.insert(Ty).second)
+    return false;
+
+  if (const PointerType *PointerTy = Ty->getAsPointerType()) {
+    QualType PointeeTy = PointerTy->getPointeeType();
+    // FIXME: Optimize this so that we don't keep trying to add the same types.
+
+    // FIXME: Do we have to add CVR qualifiers at *all* levels to deal
+    // with all pointer conversions that don't cast away constness?
+    if (!PointeeTy.isConstQualified())
+      AddWithMoreQualifiedTypeVariants
+        (Context.getPointerType(PointeeTy.withConst()));
+    if (!PointeeTy.isVolatileQualified())
+      AddWithMoreQualifiedTypeVariants
+        (Context.getPointerType(PointeeTy.withVolatile()));
+    if (!PointeeTy.isRestrictQualified())
+      AddWithMoreQualifiedTypeVariants
+        (Context.getPointerType(PointeeTy.withRestrict()));
+  }
+
+  return true;
+}
+
+/// AddTypesConvertedFrom - Add each of the types to which the type @p
+/// Ty can be implicit converted to the given set of @p Types. We're
+/// primarily interested in pointer types, enumeration types,
+void BuiltinCandidateTypeSet::AddTypesConvertedFrom(QualType Ty,
+                                                    bool AllowUserConversions) {
+  // Only deal with canonical types.
+  Ty = Context.getCanonicalType(Ty);
+
+  // Look through reference types; they aren't part of the type of an
+  // expression for the purposes of conversions.
+  if (const ReferenceType *RefTy = Ty->getAsReferenceType())
+    Ty = RefTy->getPointeeType();
+
+  // We don't care about qualifiers on the type.
+  Ty = Ty.getUnqualifiedType();
+
+  if (const PointerType *PointerTy = Ty->getAsPointerType()) {
+    QualType PointeeTy = PointerTy->getPointeeType();
+
+    // Insert our type, and its more-qualified variants, into the set
+    // of types.
+    if (!AddWithMoreQualifiedTypeVariants(Ty))
+      return;
+
+    // Add 'cv void*' to our set of types.
+    if (!Ty->isVoidType()) {
+      QualType QualVoid 
+        = Context.VoidTy.getQualifiedType(PointeeTy.getCVRQualifiers());
+      AddWithMoreQualifiedTypeVariants(Context.getPointerType(QualVoid));
+    }
+
+    // If this is a pointer to a class type, add pointers to its bases
+    // (with the same level of cv-qualification as the original
+    // derived class, of course).
+    if (const RecordType *PointeeRec = PointeeTy->getAsRecordType()) {
+      CXXRecordDecl *ClassDecl = cast<CXXRecordDecl>(PointeeRec->getDecl());
+      for (CXXRecordDecl::base_class_iterator Base = ClassDecl->bases_begin();
+           Base != ClassDecl->bases_end(); ++Base) {
+        QualType BaseTy = Context.getCanonicalType(Base->getType());
+        BaseTy = BaseTy.getQualifiedType(PointeeTy.getCVRQualifiers());
+
+        // Add the pointer type, recursively, so that we get all of
+        // the indirect base classes, too.
+        AddTypesConvertedFrom(Context.getPointerType(BaseTy), false);
+      }
+    }
+  } else if (Ty->isEnumeralType()) {
+    EnumerationTypes.insert(Ty);
+  } else if (AllowUserConversions) {
+    if (const RecordType *TyRec = Ty->getAsRecordType()) {
+      CXXRecordDecl *ClassDecl = cast<CXXRecordDecl>(TyRec->getDecl());
+      // FIXME: Visit conversion functions in the base classes, too.
+      OverloadedFunctionDecl *Conversions 
+        = ClassDecl->getConversionFunctions();
+      for (OverloadedFunctionDecl::function_iterator Func 
+             = Conversions->function_begin();
+           Func != Conversions->function_end(); ++Func) {
+        CXXConversionDecl *Conv = cast<CXXConversionDecl>(*Func);
+        AddTypesConvertedFrom(Conv->getConversionType(), false);
+      }
+    }
+  }
+}
+
+/// AddBuiltinCandidates - Add the appropriate built-in operator
+/// overloads to the candidate set (C++ [over.built]), based on the
+/// operator @p Op and the arguments given. For example, if the
+/// operator is a binary '+', this routine might add
+///   "int operator+(int, int)"
+/// to cover integer addition.
+void
+Sema::AddBuiltinBinaryOperatorCandidates(OverloadedOperatorKind Op, 
+                                         Expr **Args, 
+                                         OverloadCandidateSet& CandidateSet) {
+  // The set of "promoted arithmetic types", which are the arithmetic
+  // types are that preserved by promotion (C++ [over.built]p2). Note
+  // that the first few of these types are the promoted integral
+  // types; these types need to be first.
+  // FIXME: What about complex?
+  const unsigned FirstIntegralType = 0;
+  const unsigned LastIntegralType = 13;
+  const unsigned FirstPromotedIntegralType = 7, 
+                 LastPromotedIntegralType = 13;
+  const unsigned FirstPromotedArithmeticType = 7,
+                 LastPromotedArithmeticType = 16;
+  const unsigned NumArithmeticTypes = 16;
+  QualType ArithmeticTypes[NumArithmeticTypes] = {
+    Context.BoolTy, Context.CharTy, Context.WCharTy,
+    Context.SignedCharTy, Context.ShortTy,
+    Context.UnsignedCharTy, Context.UnsignedShortTy,
+    Context.IntTy, Context.LongTy, Context.LongLongTy,
+    Context.UnsignedIntTy, Context.UnsignedLongTy, Context.UnsignedLongLongTy,
+    Context.FloatTy, Context.DoubleTy, Context.LongDoubleTy
+  };
+
+  // Find all of the types that the arguments can convert to, but only
+  // if the operator we're looking at has built-in operator candidates
+  // that make use of these types.
+  Bu