[c++20] Add rewriting from comparison operators to <=> / ==.

This adds support for rewriting <, >, <=, and >= to a normal or reversed
call to operator<=>, for rewriting != to a normal or reversed call to
operator==, and for rewriting <=> and == to reversed forms of those same
operators.

Note that this is a breaking change for various C++17 code patterns,
including some in use in LLVM. The most common patterns (where an
operator== becomes ambiguous with a reversed form of itself) are still
accepted under this patch, as an extension (with a warning). I'm hopeful
that we can get the language rules fixed before C++20 ships, and the
extension warning is aimed primarily at providing data to inform that
decision.

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

7 files changed, 430 insertions, 129 deletions

diff --git a/lib/AST/ExprCXX.cpp b/lib/AST/ExprCXX.cpp
index 0b0d3c6880..904928bdf2 100644
--- a/lib/AST/ExprCXX.cpp
+++ b/lib/AST/ExprCXX.cpp
@@ -79,7 +79,7 @@ CXXRewrittenBinaryOperator::getDecomposedForm() const {
     Result.RHS = BO->getRHS();
     Result.InnerBinOp = BO;
   } else if (auto *BO = dyn_cast<CXXOperatorCallExpr>(E)) {
-    assert(!SkippedNot || BO->getOperator() == OO_Equal);
+    assert(!SkippedNot || BO->getOperator() == OO_EqualEqual);
     assert(BO->isInfixBinaryOp());
     switch (BO->getOperator()) {
     case OO_Less: Result.Opcode = BO_LT; break;
@@ -107,7 +107,7 @@ CXXRewrittenBinaryOperator::getDecomposedForm() const {
     return Result;
 
   // Otherwise, we expect a <=> to now be on the LHS.
-  E = Result.InnerBinOp->IgnoreImplicit();
+  E = Result.LHS->IgnoreImplicit();
   if (auto *BO = dyn_cast<BinaryOperator>(E)) {
     assert(BO->getOpcode() == BO_Cmp);
     Result.LHS = BO->getLHS();
diff --git a/lib/Frontend/FrontendActions.cpp b/lib/Frontend/FrontendActions.cpp
index fea5826179..4d47c768ad 100644
--- a/lib/Frontend/FrontendActions.cpp
+++ b/lib/Frontend/FrontendActions.cpp
@@ -415,6 +415,8 @@ private:
       return "DeclaringSpecialMember";
     case CodeSynthesisContext::DefiningSynthesizedFunction:
       return "DefiningSynthesizedFunction";
+    case CodeSynthesisContext::RewritingOperatorAsSpaceship:
+      return "RewritingOperatorAsSpaceship";
     case CodeSynthesisContext::Memoization:
       return "Memoization";
     case CodeSynthesisContext::ConstraintsCheck:
diff --git a/lib/Sema/SemaExpr.cpp b/lib/Sema/SemaExpr.cpp
index 333983a430..2734b4d076 100644
--- a/lib/Sema/SemaExpr.cpp
+++ b/lib/Sema/SemaExpr.cpp
@@ -13310,6 +13310,13 @@ static ExprResult BuildOverloadedBinOp(Sema &S, Scope *Sc, SourceLocation OpLoc,
     S.LookupOverloadedOperatorName(OverOp, Sc, LHS->getType(),
                                    RHS->getType(), Functions);
 
+  // In C++20 onwards, we may have a second operator to look up.
+  if (S.getLangOpts().CPlusPlus2a) {
+    if (OverloadedOperatorKind ExtraOp = getRewrittenOverloadedOperator(OverOp))
+      S.LookupOverloadedOperatorName(ExtraOp, Sc, LHS->getType(),
+                                     RHS->getType(), Functions);
+  }
+
   // Build the (potentially-overloaded, potentially-dependent)
   // binary operation.
   return S.CreateOverloadedBinOp(OpLoc, Opc, Functions, LHS, RHS);
diff --git a/lib/Sema/SemaOverload.cpp b/lib/Sema/SemaOverload.cpp
index 80bd3562bc..6793079ff0 100644
--- a/lib/Sema/SemaOverload.cpp
+++ b/lib/Sema/SemaOverload.cpp
@@ -848,6 +848,25 @@ llvm::Optional<unsigned> DeductionFailureInfo::getCallArgIndex() {
   }
 }
 
+bool OverloadCandidateSet::OperatorRewriteInfo::shouldAddReversed(
+    OverloadedOperatorKind Op) {
+  if (!AllowRewrittenCandidates)
+    return false;
+  return Op == OO_EqualEqual || Op == OO_Spaceship;
+}
+
+bool OverloadCandidateSet::OperatorRewriteInfo::shouldAddReversed(
+    ASTContext &Ctx, const FunctionDecl *FD) {
+  if (!shouldAddReversed(FD->getDeclName().getCXXOverloadedOperator()))
+    return false;
+  // Don't bother adding a reversed candidate that can never be a better
+  // match than the non-reversed version.
+  return FD->getNumParams() != 2 ||
+         !Ctx.hasSameUnqualifiedType(FD->getParamDecl(0)->getType(),
+                                     FD->getParamDecl(1)->getType()) ||
+         FD->hasAttr<EnableIfAttr>();
+}
+
 void OverloadCandidateSet::destroyCandidates() {
   for (iterator i = begin(), e = end(); i != e; ++i) {
     for (auto &C : i->Conversions)
@@ -6056,7 +6075,8 @@ void Sema::AddOverloadCandidate(
     FunctionDecl *Function, DeclAccessPair FoundDecl, ArrayRef<Expr *> Args,
     OverloadCandidateSet &CandidateSet, bool SuppressUserConversions,
     bool PartialOverloading, bool AllowExplicit, bool AllowExplicitConversions,
-    ADLCallKind IsADLCandidate, ConversionSequenceList EarlyConversions) {
+    ADLCallKind IsADLCandidate, ConversionSequenceList EarlyConversions,
+    OverloadCandidateParamOrder PO) {
   const FunctionProtoType *Proto
     = dyn_cast<FunctionProtoType>(Function->getType()->getAs<FunctionType>());
   assert(Proto && "Functions without a prototype cannot be overloaded");
@@ -6075,25 +6095,14 @@ void Sema::AddOverloadCandidate(
       AddMethodCandidate(Method, FoundDecl, Method->getParent(), QualType(),
                          Expr::Classification::makeSimpleLValue(), Args,
                          CandidateSet, SuppressUserConversions,
-                         PartialOverloading, EarlyConversions);
+                         PartialOverloading, EarlyConversions, PO);
       return;
     }
     // We treat a constructor like a non-member function, since its object
     // argument doesn't participate in overload resolution.
   }
 
-  if (!CandidateSet.isNewCandidate(Function))
-    return;
-
-  // C++ [over.match.oper]p3:
-  //   if no operand has a class type, only those non-member functions in the
-  //   lookup set that have a first parameter of type T1 or "reference to
-  //   (possibly cv-qualified) T1", when T1 is an enumeration type, or (if there
-  //   is a right operand) a second parameter of type T2 or "reference to
-  //   (possibly cv-qualified) T2", when T2 is an enumeration type, are
-  //   candidate functions.
-  if (CandidateSet.getKind() == OverloadCandidateSet::CSK_Operator &&
-      !IsAcceptableNonMemberOperatorCandidate(Context, Function, Args))
+  if (!CandidateSet.isNewCandidate(Function, PO))
     return;
 
   // C++11 [class.copy]p11: [DR1402]
@@ -6108,12 +6117,25 @@ void Sema::AddOverloadCandidate(
   EnterExpressionEvaluationContext Unevaluated(
       *this, Sema::ExpressionEvaluationContext::Unevaluated);
 
+  // C++ [over.match.oper]p3:
+  //   if no operand has a class type, only those non-member functions in the
+  //   lookup set that have a first parameter of type T1 or "reference to
+  //   (possibly cv-qualified) T1", when T1 is an enumeration type, or (if there
+  //   is a right operand) a second parameter of type T2 or "reference to
+  //   (possibly cv-qualified) T2", when T2 is an enumeration type, are
+  //   candidate functions.
+  if (CandidateSet.getKind() == OverloadCandidateSet::CSK_Operator &&
+      !IsAcceptableNonMemberOperatorCandidate(Context, Function, Args))
+    return;
+
   // Add this candidate
   OverloadCandidate &Candidate =
       CandidateSet.addCandidate(Args.size(), EarlyConversions);
   Candidate.FoundDecl = FoundDecl;
   Candidate.Function = Function;
   Candidate.Viable = true;
+  Candidate.RewriteKind =
+      CandidateSet.getRewriteInfo().getRewriteKind(Function, PO);
   Candidate.IsSurrogate = false;
   Candidate.IsADLCandidate = IsADLCandidate;
   Candidate.IgnoreObjectArgument = false;
@@ -6213,7 +6235,9 @@ void Sema::AddOverloadCandidate(
   // Determine the implicit conversion sequences for each of the
   // arguments.
   for (unsigned ArgIdx = 0; ArgIdx < Args.size(); ++ArgIdx) {
-    if (Candidate.Conversions[ArgIdx].isInitialized()) {
+    unsigned ConvIdx =
+        PO == OverloadCandidateParamOrder::Reversed ? 1 - ArgIdx : ArgIdx;
+    if (Candidate.Conversions[ConvIdx].isInitialized()) {
       // We already formed a conversion sequence for this parameter during
       // template argument deduction.
     } else if (ArgIdx < NumParams) {
@@ -6222,12 +6246,12 @@ void Sema::AddOverloadCandidate(
       // (13.3.3.1) that converts that argument to the corresponding
       // parameter of F.
       QualType ParamType = Proto->getParamType(ArgIdx);
-      Candidate.Conversions[ArgIdx] = TryCopyInitialization(
+      Candidate.Conversions[ConvIdx] = TryCopyInitialization(
           *this, Args[ArgIdx], ParamType, SuppressUserConversions,
           /*InOverloadResolution=*/true,
           /*AllowObjCWritebackConversion=*/
           getLangOpts().ObjCAutoRefCount, AllowExplicitConversions);
-      if (Candidate.Conversions[ArgIdx].isBad()) {
+      if (Candidate.Conversions[ConvIdx].isBad()) {
         Candidate.Viable = false;
         Candidate.FailureKind = ovl_fail_bad_conversion;
         return;
@@ -6236,7 +6260,7 @@ void Sema::AddOverloadCandidate(
       // (C++ 13.3.2p2): For the purposes of overload resolution, any
       // argument for which there is no corresponding parameter is
       // considered to ""match the ellipsis" (C+ 13.3.3.1.3).
-      Candidate.Conversions[ArgIdx].setEllipsis();
+      Candidate.Conversions[ConvIdx].setEllipsis();
     }
   }
 
@@ -6583,9 +6607,10 @@ void Sema::AddFunctionCandidates(const UnresolvedSetImpl &Fns,
         FunctionArgs = Args.slice(1);
       }
       if (FunTmpl) {
-        AddTemplateOverloadCandidate(
-            FunTmpl, F.getPair(), ExplicitTemplateArgs, FunctionArgs,
-            CandidateSet, SuppressUserConversions, PartialOverloading);
+        AddTemplateOverloadCandidate(FunTmpl, F.getPair(),
+                                     ExplicitTemplateArgs, FunctionArgs,
+                                     CandidateSet, SuppressUserConversions,
+                                     PartialOverloading);
       } else {
         AddOverloadCandidate(FD, F.getPair(), FunctionArgs, CandidateSet,
                              SuppressUserConversions, PartialOverloading);
@@ -6596,12 +6621,12 @@ void Sema::AddFunctionCandidates(const UnresolvedSetImpl &Fns,
 
 /// AddMethodCandidate - Adds a named decl (which is some kind of
 /// method) as a method candidate to the given overload set.
-void Sema::AddMethodCandidate(DeclAccessPair FoundDecl,
-                              QualType ObjectType,
+void Sema::AddMethodCandidate(DeclAccessPair FoundDecl, QualType ObjectType,
                               Expr::Classification ObjectClassification,
                               ArrayRef<Expr *> Args,
-                              OverloadCandidateSet& CandidateSet,
-                              bool SuppressUserConversions) {
+                              OverloadCandidateSet &CandidateSet,
+                              bool SuppressUserConversions,
+                              OverloadCandidateParamOrder PO) {
   NamedDecl *Decl = FoundDecl.getDecl();
   CXXRecordDecl *ActingContext = cast<CXXRecordDecl>(Decl->getDeclContext());
 
@@ -6614,11 +6639,11 @@ void Sema::AddMethodCandidate(DeclAccessPair FoundDecl,
     AddMethodTemplateCandidate(TD, FoundDecl, ActingContext,
                                /*ExplicitArgs*/ nullptr, ObjectType,
                                ObjectClassification, Args, CandidateSet,
-                               SuppressUserConversions);
+                               SuppressUserConversions, false, PO);
   } else {
     AddMethodCandidate(cast<CXXMethodDecl>(Decl), FoundDecl, ActingContext,
                        ObjectType, ObjectClassification, Args, CandidateSet,
-                       SuppressUserConversions);
+                       SuppressUserConversions, false, None, PO);
   }
 }
 
@@ -6637,14 +6662,15 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, DeclAccessPair FoundDecl,
                          OverloadCandidateSet &CandidateSet,
                          bool SuppressUserConversions,
                          bool PartialOverloading,
-                         ConversionSequenceList EarlyConversions) {
+                         ConversionSequenceList EarlyConversions,
+                         OverloadCandidateParamOrder PO) {
   const FunctionProtoType *Proto
     = dyn_cast<FunctionProtoType>(Method->getType()->getAs<FunctionType>());
   assert(Proto && "Methods without a prototype cannot be overloaded");
   assert(!isa<CXXConstructorDecl>(Method) &&
          "Use AddOverloadCandidate for constructors");
 
-  if (!CandidateSet.isNewCandidate(Method))
+  if (!CandidateSet.isNewCandidate(Method, PO))
     return;
 
   // C++11 [class.copy]p23: [DR1402]
@@ -6663,6 +6689,8 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, DeclAccessPair FoundDecl,
       CandidateSet.addCandidate(Args.size() + 1, EarlyConversions);
   Candidate.FoundDecl = FoundDecl;
   Candidate.Function = Method;
+  Candidate.RewriteKind =
+      CandidateSet.getRewriteInfo().getRewriteKind(Method, PO);
   Candidate.IsSurrogate = false;
   Candidate.IgnoreObjectArgument = false;
   Candidate.ExplicitCallArguments = Args.size();
@@ -6698,12 +6726,13 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, DeclAccessPair FoundDecl,
     // The implicit object argument is ignored.
     Candidate.IgnoreObjectArgument = true;
   else {
+    unsigned ConvIdx = PO == OverloadCandidateParamOrder::Reversed ? 1 : 0;
     // Determine the implicit conversion sequence for the object
     // parameter.
-    Candidate.Conversions[0] = TryObjectArgumentInitialization(
+    Candidate.Conversions[ConvIdx] = TryObjectArgumentInitialization(
         *this, CandidateSet.getLocation(), ObjectType, ObjectClassification,
         Method, ActingContext);
-    if (Candidate.Conversions[0].isBad()) {
+    if (Candidate.Conversions[ConvIdx].isBad()) {
       Candidate.Viable = false;
       Candidate.FailureKind = ovl_fail_bad_conversion;
       return;
@@ -6722,7 +6751,9 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, DeclAccessPair FoundDecl,
   // Determine the implicit conversion sequences for each of the
   // arguments.
   for (unsigned ArgIdx = 0; ArgIdx < Args.size(); ++ArgIdx) {
-    if (Candidate.Conversions[ArgIdx + 1].isInitialized()) {
+    unsigned ConvIdx =
+        PO == OverloadCandidateParamOrder::Reversed ? 0 : (ArgIdx + 1);
+    if (Candidate.Conversions[ConvIdx].isInitialized()) {
       // We already formed a conversion sequence for this parameter during
       // template argument deduction.
     } else if (ArgIdx < NumParams) {
@@ -6731,13 +6762,13 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, DeclAccessPair FoundDecl,
       // (13.3.3.1) that converts that argument to the corresponding
       // parameter of F.
       QualType ParamType = Proto->getParamType(ArgIdx);
-      Candidate.Conversions[ArgIdx + 1]
+      Candidate.Conversions[ConvIdx]
         = TryCopyInitialization(*this, Args[ArgIdx], ParamType,
                                 SuppressUserConversions,
                                 /*InOverloadResolution=*/true,
                                 /*AllowObjCWritebackConversion=*/
                                   getLangOpts().ObjCAutoRefCount);
-      if (Candidate.Conversions[ArgIdx + 1].isBad()) {
+      if (Candidate.Conversions[ConvIdx].isBad()) {
         Candidate.Viable = false;
         Candidate.FailureKind = ovl_fail_bad_conversion;
         return;
@@ -6746,7 +6777,7 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, DeclAccessPair FoundDecl,
       // (C++ 13.3.2p2): For the purposes of overload resolution, any
       // argument for which there is no corresponding parameter is
       // considered to "match the ellipsis" (C+ 13.3.3.1.3).
-      Candidate.Conversions[ArgIdx + 1].setEllipsis();
+      Candidate.Conversions[ConvIdx].setEllipsis();
     }
   }
 
@@ -6767,18 +6798,14 @@ Sema::AddMethodCandidate(CXXMethodDecl *Method, DeclAccessPair FoundDecl,
 /// Add a C++ member function template as a candidate to the candidate
 /// set, using template argument deduction to produce an appropriate member
 /// function template specialization.
-void
-Sema::AddMethodTemplateCandidate(FunctionTemplateDecl *MethodTmpl,
-                                 DeclAccessPair FoundDecl,
-                                 CXXRecordDecl *ActingContext,
-                                 TemplateArgumentListInfo *ExplicitTemplateArgs,
-                                 QualType ObjectType,
-                                 Expr::Classification ObjectClassification,
-                                 ArrayRef<Expr *> Args,
-                                 OverloadCandidateSet& CandidateSet,
-                                 bool SuppressUserConversions,
-                                 bool PartialOverloading) {
-  if (!CandidateSet.isNewCandidate(MethodTmpl))
+void Sema::AddMethodTemplateCandidate(
+    FunctionTemplateDecl *MethodTmpl, DeclAccessPair FoundDecl,
+    CXXRecordDecl *ActingContext,
+    TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ObjectType,
+    Expr::Classification ObjectClassification, ArrayRef<Expr *> Args,
+    OverloadCandidateSet &CandidateSet, bool SuppressUserConversions,
+    bool PartialOverloading, OverloadCandidateParamOrder PO) {
+  if (!CandidateSet.isNewCandidate(MethodTmpl, PO))
     return;
 
   // C++ [over.match.funcs]p7:
@@ -6799,13 +6826,15 @@ Sema::AddMethodTemplateCandidate(FunctionTemplateDecl *MethodTmpl,
             return CheckNonDependentConversions(
                 MethodTmpl, ParamTypes, Args, CandidateSet, Conversions,
                 SuppressUserConversions, ActingContext, ObjectType,
-                ObjectClassification);
+                ObjectClassification, PO);
           })) {
     OverloadCandidate &Candidate =
         CandidateSet.addCandidate(Conversions.size(), Conversions);
     Candidate.FoundDecl = FoundDecl;
     Candidate.Function = MethodTmpl->getTemplatedDecl();
     Candidate.Viable = false;
+    Candidate.RewriteKind =
+      CandidateSet.getRewriteInfo().getRewriteKind(Candidate.Function, PO);
     Candidate.IsSurrogate = false;
     Candidate.IgnoreObjectArgument =
         cast<CXXMethodDecl>(Candidate.Function)->isStatic() ||
@@ -6829,7 +6858,7 @@ Sema::AddMethodTemplateCandidate(FunctionTemplateDecl *MethodTmpl,
   AddMethodCandidate(cast<CXXMethodDecl>(Specialization), FoundDecl,
                      ActingContext, ObjectType, ObjectClassification, Args,
                      CandidateSet, SuppressUserConversions, PartialOverloading,
-                     Conversions);
+                     Conversions, PO);
 }
 
 /// Add a C++ function template specialization as a candidate
@@ -6839,8 +6868,9 @@ void Sema::AddTemplateOverloadCandidate(
     FunctionTemplateDecl *FunctionTemplate, DeclAccessPair FoundDecl,
     TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
     OverloadCandidateSet &CandidateSet, bool SuppressUserConversions,
-    bool PartialOverloading, bool AllowExplicit, ADLCallKind IsADLCandidate) {
-  if (!CandidateSet.isNewCandidate(FunctionTemplate))
+    bool PartialOverloading, bool AllowExplicit, ADLCallKind IsADLCandidate,
+    OverloadCandidateParamOrder PO) {
+  if (!CandidateSet.isNewCandidate(FunctionTemplate, PO))
     return;
 
   // C++ [over.match.funcs]p7:
@@ -6858,15 +6888,17 @@ void Sema::AddTemplateOverloadCandidate(
   if (TemplateDeductionResult Result = DeduceTemplateArguments(
           FunctionTemplate, ExplicitTemplateArgs, Args, Specialization, Info,
           PartialOverloading, [&](ArrayRef<QualType> ParamTypes) {
-            return CheckNonDependentConversions(FunctionTemplate, ParamTypes,
-                                                Args, CandidateSet, Conversions,
-                                                SuppressUserConversions);
+            return CheckNonDependentConversions(
+                FunctionTemplate, ParamTypes, Args, CandidateSet, Conversions,
+                SuppressUserConversions, nullptr, QualType(), {}, PO);
           })) {
     OverloadCandidate &Candidate =
         CandidateSet.addCandidate(Conversions.size(), Conversions);
     Candidate.FoundDecl = FoundDecl;
     Candidate.Function = FunctionTemplate->getTemplatedDecl();
     Candidate.Viable = false;
+    Candidate.RewriteKind =
+      CandidateSet.getRewriteInfo().getRewriteKind(Candidate.Function, PO);
     Candidate.IsSurrogate = false;
     Candidate.IsADLCandidate = IsADLCandidate;
     // Ignore the object argument if there is one, since we don't have an object
@@ -6891,7 +6923,7 @@ void Sema::AddTemplateOverloadCandidate(
   AddOverloadCandidate(
       Specialization, FoundDecl, Args, CandidateSet, SuppressUserConversions,
       PartialOverloading, AllowExplicit,
-      /*AllowExplicitConversions*/ false, IsADLCandidate, Conversions);
+      /*AllowExplicitConversions*/ false, IsADLCandidate, Conversions, PO);
 }
 
 /// Check that implicit conversion sequences can be formed for each argument
@@ -6902,7 +6934,7 @@ bool Sema::CheckNonDependentConversions(
     ArrayRef<Expr *> Args, OverloadCandidateSet &CandidateSet,
     ConversionSequenceList &Conversions, bool SuppressUserConversions,
     CXXRecordDecl *ActingContext, QualType ObjectType,
-    Expr::Classification ObjectClassification) {
+    Expr::Classification ObjectClassification, OverloadCandidateParamOrder PO) {
   // FIXME: The cases in which we allow explicit conversions for constructor
   // arguments never consider calling a constructor template. It's not clear
   // that is correct.
@@ -6925,10 +6957,11 @@ bool Sema::CheckNonDependentConversions(
   // overload resolution is permitted to sidestep instantiations.
   if (HasThisConversion && !cast<CXXMethodDecl>(FD)->isStatic() &&
       !ObjectType.isNull()) {
-    Conversions[0] = TryObjectArgumentInitialization(
+    unsigned ConvIdx = PO == OverloadCandidateParamOrder::Reversed ? 1 : 0;
+    Conversions[ConvIdx] = TryObjectArgumentInitialization(
         *this, CandidateSet.getLocation(), ObjectType, ObjectClassification,
         Method, ActingContext);
-    if (Conversions[0].isBad())
+    if (Conversions[ConvIdx].isBad())
       return true;
   }
 
@@ -6936,14 +6969,17 @@ bool Sema::CheckNonDependentConversions(
        ++I) {
     QualType ParamType = ParamTypes[I];
     if (!ParamType->isDependentType()) {
-      Conversions[ThisConversions + I]
+      unsigned ConvIdx = PO == OverloadCandidateParamOrder::Reversed
+                             ? 0
+                             : (ThisConversions + I);
+      Conversions[ConvIdx]
         = TryCopyInitialization(*this, Args[I], ParamType,
                                 SuppressUserConversions,
                                 /*InOverloadResolution=*/true,
                                 /*AllowObjCWritebackConversion=*/
                                   getLangOpts().ObjCAutoRefCount,
                                 AllowExplicit);
-      if (Conversions[ThisConversions + I].isBad())
+      if (Conversions[ConvIdx].isBad())
         return true;
     }
   }
@@ -7331,6 +7367,48 @@ void Sema::AddSurrogateCandidate(CXXConversionDecl *Conversion,
   }
 }
 
+/// Add all of the non-member operator function declarations in the given
+/// function set to the overload candidate set.
+void Sema::AddNonMemberOperatorCandidates(
+    const UnresolvedSetImpl &Fns, ArrayRef<Expr *> Args,
+    OverloadCandidateSet &CandidateSet,
+    TemplateArgumentListInfo *ExplicitTemplateArgs) {
+  for (UnresolvedSetIterator F = Fns.begin(), E = Fns.end(); F != E; ++F) {
+    NamedDecl *D = F.getDecl()->getUnderlyingDecl();
+    ArrayRef<Expr *> FunctionArgs = Args;
+
+    FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D);
+    FunctionDecl *FD =
+        FunTmpl ? FunTmpl->getTemplatedDecl() : cast<FunctionDecl>(D);
+
+    // Don't consider rewritten functions if we're not rewriting.
+    if (!CandidateSet.getRewriteInfo().isAcceptableCandidate(FD))
+      continue;
+
+    assert(!isa<CXXMethodDecl>(FD) &&
+           "unqualified operator lookup found a member function");
+
+    if (FunTmpl) {
+      AddTemplateOverloadCandidate(FunTmpl, F.getPair(), ExplicitTemplateArgs,
+                                   FunctionArgs, CandidateSet);
+      if (CandidateSet.getRewriteInfo().shouldAddReversed(Context, FD))
+        AddTemplateOverloadCandidate(
+            FunTmpl, F.getPair(), ExplicitTemplateArgs,
+            {FunctionArgs[1], FunctionArgs[0]}, CandidateSet, false, false,
+            true, ADLCallKind::NotADL, OverloadCandidateParamOrder::Reversed);
+    } else {
+      if (ExplicitTemplateArgs)
+        continue;
+      AddOverloadCandidate(FD, F.getPair(), FunctionArgs, CandidateSet);
+      if (CandidateSet.getRewriteInfo().shouldAddReversed(Context, FD))
+        AddOverloadCandidate(FD, F.getPair(),
+                             {FunctionArgs[1], FunctionArgs[0]}, CandidateSet,
+                             false, false, true, false, ADLCallKind::NotADL,
+                             None, OverloadCandidateParamOrder::Reversed);
+    }
+  }
+}
+
 /// Add overload candidates for overloaded operators that are
 /// member functions.
 ///
@@ -7342,8 +7420,8 @@ void Sema::AddSurrogateCandidate(CXXConversionDecl *Conversion,
 void Sema::AddMemberOperatorCandidates(OverloadedOperatorKind Op,
                                        SourceLocation OpLoc,
                                        ArrayRef<Expr *> Args,
-                                       OverloadCandidateSet& CandidateSet,
-                                       SourceRange OpRange) {
+                                       OverloadCandidateSet &CandidateSet,
+                                       OverloadCandidateParamOrder PO) {
   DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op);
 
   // C++ [over.match.oper]p3:
@@ -7378,7 +7456,7 @@ void Sema::AddMemberOperatorCandidates(OverloadedOperatorKind Op,
          ++Oper)
       AddMethodCandidate(Oper.getPair(), Args[0]->getType(),
                          Args[0]->Classify(Context), Args.slice(1),
-                         CandidateSet, /*SuppressUserConversion=*/false);
+                         CandidateSet, /*SuppressUserConversion=*/false, PO);
   }
 }
 
@@ -8183,10 +8261,16 @@ public:
           if (C->Function->isFunctionTemplateSpecialization())
             continue;
 
-          QualType FirstParamType =
-            C->Function->getParamDecl(0)->getType().getUnqualifiedType();
-          QualType SecondParamType =
-            C->Function->getParamDecl(1)->getType().getUnqualifiedType();
+          // We interpret "same parameter-type-list" as applying to the
+          // "synthesized candidate, with the order of the two parameters
+          // reversed", not to the original function.
+          bool Reversed = C->RewriteKind & CRK_Reversed;
+          QualType FirstParamType = C->Function->getParamDecl(Reversed ? 1 : 0)
+                                        ->getType()
+                                        .getUnqualifiedType();
+          QualType SecondParamType = C->Function->getParamDecl(Reversed ? 0 : 1)
+                                         ->getType()
+                                         .getUnqualifiedType();
 
           // Skip if either parameter isn't of enumeral type.
           if (!FirstParamType->isEnumeralType() ||
@@ -9240,6 +9324,7 @@ bool clang::isBetterOverloadCandidate(
   //   A viable function F1 is defined to be a better function than another
   //   viable function F2 if for all arguments i, ICSi(F1) is not a worse
   //   conversion sequence than ICSi(F2), and then...
+  bool HasWorseConversion = false;
   for (unsigned ArgIdx = StartArg; ArgIdx < NumArgs; ++ArgIdx) {
     switch (CompareImplicitConversionSequences(S, Loc,
                                                Cand1.Conversions[ArgIdx],
@@ -9250,6 +9335,24 @@ bool clang::isBetterOverloadCandidate(
       break;
 
     case ImplicitConversionSequence::Worse:
+      if (Cand1.Function && Cand1.Function == Cand2.Function &&
+          (Cand2.RewriteKind & CRK_Reversed) != 0) {
+        // Work around large-scale breakage caused by considering reversed
+        // forms of operator== in C++20:
+        //
+        // When comparing a function against its reversed form, if we have a
+        // better conversion for one argument and a worse conversion for the
+        // other, we prefer the non-reversed form.
+        //
+        // This prevents a conversion function from being considered ambiguous
+        // with its own reversed form in various where it's only incidentally
+        // heterogeneous.
+        //
+        // We diagnose this as an extension from CreateOverloadedBinOp.
+        HasWorseConversion = true;
+        break;
+      }
+
       // Cand1 can't be better than Cand2.
       return false;
 
@@ -9263,6 +9366,8 @@ bool clang::isBetterOverloadCandidate(
   //       ICSj(F2), or, if not that,
   if (HasBetterConversion)
     return true;
+  if (HasWorseConversion)
+    return false;
 
   //   -- the context is an initialization by user-defined conversion
   //      (see 8.5, 13.3.1.5) and the standard conversion sequence
@@ -9330,8 +9435,10 @@ bool clang::isBetterOverloadCandidate(
       return BetterTemplate == Cand1.Function->getPrimaryTemplate();
   }
 
-  // FIXME: Work around a defect in the C++17 inheriting constructor wording.
-  // A derived-class constructor beats an (inherited) base class constructor.
+  //   -- F1 is a constructor for a class D, F2 is a constructor for a base
+  //      class B of D, and for all arguments the corresponding parameters of
+  //      F1 and F2 have the same type.
+  // FIXME: Implement the "all parameters have the same type" check.
   bool Cand1IsInherited =
       dyn_cast_or_null<ConstructorUsingShadowDecl>(Cand1.FoundDecl.getDecl());
   bool Cand2IsInherited =
@@ -9349,6 +9456,16 @@ bool clang::isBetterOverloadCandidate(
     // Inherited from sibling base classes: still ambiguous.
   }
 
+  //   -- F2 is a rewritten candidate (12.4.1.2) and F1 is not
+  //   -- F1 and F2 are rewritten candidates, and F2 is a synthesized candidate
+  //      with reversed order of parameters and F1 is not
+  //
+  // We rank reversed + different operator as worse than just reversed, but
+  // that comparison can never happen, because we only consider reversing for
+  // the maximally-rewritten operator (== or <=>).
+  if (Cand1.RewriteKind != Cand2.RewriteKind)
+    return Cand1.RewriteKind < Cand2.RewriteKind;
+
   // Check C++17 tie-breakers for deduction guides.
   {
     auto *Guide1 = dyn_cast_or_null<CXXDeductionGuideDecl>(Cand1.Function);
@@ -9544,6 +9661,7 @@ namespace {
 enum OverloadCandidateKind {
   oc_function,
   oc_method,
+  oc_reversed_binary_operator,
   oc_constructor,
   oc_implicit_default_constructor,
   oc_implicit_copy_constructor,
@@ -9561,6 +9679,7 @@ enum OverloadCandidateSelect {
 
 static std::pair<OverloadCandidateKind, OverloadCandidateSelect>
 ClassifyOverloadCandidate(Sema &S, NamedDecl *Found, FunctionDecl *Fn,
+                          OverloadCandidateRewriteKind CRK,
                           std::string &Description) {
 
   bool isTemplate = Fn->isTemplateDecl() || Found->isTemplateDecl();
@@ -9577,6 +9696,9 @@ ClassifyOverloadCandidate(Sema &S, NamedDecl *Found, FunctionDecl *Fn,
   }();
 
   OverloadCandidateKind Kind = [&]() {
+    if (CRK & CRK_Reversed)
+      return oc_reversed_binary_operator;
+
     if (CXXConstructorDecl *Ctor = dyn_cast<CXXConstructorDecl>(Fn)) {
       if (!Ctor->isImplicit()) {
         if (isa<ConstructorUsingShadowDecl>(Found))
@@ -9701,6 +9823,7 @@ bool Sema::checkAddressOfFunctionIsAvailable(const FunctionDecl *Function,
 
 // Notes the location of an overload candidate.
 void Sema::NoteOverloadCandidate(NamedDecl *Found, FunctionDecl *Fn,
+                                 OverloadCandidateRewriteKind RewriteKind,
                                  QualType DestType, bool TakingAddress) {
   if (TakingAddress && !checkAddressOfCandidateIsAvailable(*this, Fn))
     return;
@@ -9710,7 +9833,7 @@ void Sema::NoteOverloadCandidate(NamedDecl *Found, FunctionDecl *Fn,
 
   std::string FnDesc;
   std::pair<OverloadCandidateKind, OverloadCandidateSelect> KSPair =
-      ClassifyOverloadCandidate(*this, Found, Fn, FnDesc);
+      ClassifyOverloadCandidate(*this, Found, Fn, RewriteKind, FnDesc);
   PartialDiagnostic PD = PDiag(diag::note_ovl_candidate)
                          << (unsigned)KSPair.first << (unsigned)KSPair.second
                          << Fn << FnDesc;
@@ -9734,11 +9857,11 @@ void Sema::NoteAllOverloadCandidates(Expr *OverloadedExpr, QualType DestType,
        I != IEnd; ++I) {
     if (FunctionTemplateDecl *FunTmpl =
                 dyn_cast<FunctionTemplateDecl>((*I)->getUnderlyingDecl()) ) {
-      NoteOverloadCandidate(*I, FunTmpl->getTemplatedDecl(), DestType,
+      NoteOverloadCandidate(*I, FunTmpl->getTemplatedDecl(), CRK_None, DestType,
                             TakingAddress);
     } else if (FunctionDecl *Fun
                       = dyn_cast<FunctionDecl>((*I)->getUnderlyingDecl()) ) {
-      NoteOverloadCandidate(*I, Fun, DestType, TakingAddress);
+      NoteOverloadCandidate(*I, Fun, CRK_None, DestType, TakingAddress);
     }
   }
 }
@@ -9788,7 +9911,8 @@ static void DiagnoseBadConversion(Sema &S, OverloadCandidate *Cand,
 
   std::string FnDesc;
   std::pair<OverloadCandidateKind, OverloadCandidateSelect> FnKindPair =
-      ClassifyOverloadCandidate(S, Cand->FoundDecl, Fn, FnDesc);
+      ClassifyOverloadCandidate(S, Cand->FoundDecl, Fn, Cand->RewriteKind,
+                                FnDesc);
 
   Expr *FromExpr = Conv.Bad.FromExpr;
   QualType FromTy = Conv.Bad.getFromType();
@@ -10060,7 +10184,7 @@ static void DiagnoseArityMismatch(Sema &S, NamedDecl *Found, Decl *D,
 
   std::string Description;
   std::pair<OverloadCandidateKind, OverloadCandidateSelect> FnKindPair =
-      ClassifyOverloadCandidate(S, Found, Fn, Description);
+      ClassifyOverloadCandidate(S, Found, Fn, CRK_None, Description);
 
   if (modeCount == 1 && Fn->getParamDecl(0)->getDeclName())
     S.Diag(Fn->getLocation(), diag::note_ovl_candidate_arity_one)
@@ -10357,7 +10481,8 @@ static void DiagnoseBadTarget(Sema &S, OverloadCandidate *Cand) {
 
   std::string FnDesc;
   std::pair<OverloadCandidateKind, OverloadCandidateSelect> FnKindPair =
-      ClassifyOverloadCandidate(S, Cand->FoundDecl, Callee, FnDesc);
+      ClassifyOverloadCandidate(S, Cand->FoundDecl, Callee, Cand->RewriteKind,
+                                FnDesc);
 
   S.Diag(Callee->getLocation(), diag::note_ovl_candidate_bad_target)
       << (unsigned)FnKindPair.first << (unsigned)ocs_non_template
@@ -10475,7 +10600,8 @@ static void NoteFunctionCandidate(Sema &S, OverloadCandidate *Cand,
     if (Fn->isDeleted()) {
       std::string FnDesc;
       std::pair<OverloadCandidateKind, OverloadCandidateSelect> FnKindPair =
-          ClassifyOverloadCandidate(S, Cand->FoundDecl, Fn, FnDesc);
+          ClassifyOverloadCandidate(S, Cand->FoundDecl, Fn, Cand->RewriteKind,
+                                    FnDesc);
 
       S.Diag(Fn->getLocation(), diag::note_ovl_candidate_deleted)
           << (unsigned)FnKindPair.first << (unsigned)FnKindPair.second << FnDesc
@@ -10485,7 +10611,7 @@ static void NoteFunctionCandidate(Sema &S, OverloadCandidate *Cand,
     }
 
     // We don't really have anything else to say about viable candidates.
-    S.NoteOverloadCandidate(Cand->FoundDecl, Fn);
+    S.NoteOverloadCandidate(Cand->FoundDecl, Fn, Cand->RewriteKind);
     return;
   }
 
@@ -10518,7 +10644,7 @@ static void NoteFunctionCandidate(Sema &S, OverloadCandidate *Cand,
   case ovl_fail_trivial_conversion:
   case ovl_fail_bad_final_conversion:
   case ovl_fail_final_conversion_not_exact:
-    return S.NoteOverloadCandidate(Cand->FoundDecl, Fn);
+    return S.NoteOverloadCandidate(Cand->FoundDecl, Fn, Cand->RewriteKind);
 
   case ovl_fail_bad_conversion: {
     unsigned I = (Cand->IgnoreObjectArgument ? 1 : 0);
@@ -10529,7 +10655,7 @@ static void NoteFunctionCandidate(Sema &S, OverloadCandidate *Cand,
     // FIXME: this currently happens when we're called from SemaInit
     // when user-conversion overload fails.  Figure out how to handle
     // those conditions and diagnose them well.
-    return S.NoteOverloadCandidate(Cand->FoundDecl, Fn);
+    return S.NoteOverloadCandidate(Cand->FoundDecl, Fn, Cand->RewriteKind);
   }
 
   case ovl_fail_bad_target:
@@ -10805,8 +10931,10 @@ struct CompareOverloadCandidatesForDisplay {
 /// CompleteNonViableCandidate - Normally, overload resolution only
 /// computes up to the first bad conversion. Produces the FixIt set if
 /// possible.
-static void CompleteNonViableCandidate(Sema &S, OverloadCandidate *Cand,
-                                       ArrayRef<Expr *> Args) {
+static void
+CompleteNonViableCandidate(Sema &S, OverloadCandidate *Cand,
+                           ArrayRef<Expr *> Args,
+                           OverloadCandidateSet::CandidateSetKind CSK) {
   assert(!Cand->Viable);
 
   // Don't do anything on failures other than bad conversion.
@@ -10834,6 +10962,7 @@ static void CompleteNonViableCandidate(Sema &S, OverloadCandidate *Cand,
   bool SuppressUserConversions = false;
 
   unsigned ConvIdx = 0;
+  unsigned ArgIdx = 0;
   ArrayRef<QualType> ParamTypes;
 
   if (Cand->IsSurrogate) {
@@ -10842,15 +10971,18 @@ static void CompleteNonViableCandidate(Sema &S, OverloadCandidate *Cand,
     if (const PointerType *ConvPtrType = ConvType->getAs<PointerType>())
       ConvType = ConvPtrType->getPointeeType();
     ParamTypes = ConvType->castAs<FunctionProtoType>()->getParamTypes();
-    // Conversion 0 is 'this', which doesn't have a corresponding argument.
+    // Conversion 0 is 'this', which doesn't have a corresponding parameter.
     ConvIdx = 1;
   } else if (Cand->Function) {
     ParamTypes =
         Cand->Function->getType()->castAs<FunctionProtoType>()->getParamTypes();
     if (isa<CXXMethodDecl>(Cand->Function) &&
         !isa<CXXConstructorDecl>(Cand->Function)) {
-      // Conversion 0 is 'this', which doesn't have a corresponding argument.
+      // Conversion 0 is 'this', which doesn't have a corresponding parameter.
       ConvIdx = 1;
+      if (CSK == OverloadCandidateSet::CSK_Operator)
+        // Argument 0 is 'this', which doesn't have a corresponding parameter.
+        ArgIdx = 1;
     }
   } else {
     // Builtin operator.
@@ -10859,16 +10991,19 @@ static void CompleteNonViableCandidate(Sema &S, OverloadCandidate *Cand,
   }
 
   // Fill in the rest of the conversions.
-  for (unsigned ArgIdx = 0; ConvIdx != ConvCount; ++ConvIdx, ++ArgIdx) {
+  bool Reversed = Cand->RewriteKind & CRK_Reversed;
+  for (unsigned ParamIdx = Reversed ? ParamTypes.size() - 1 : 0;
+       ConvIdx != ConvCount;
+       ++ConvIdx, ++ArgIdx, ParamIdx += (Reversed ? -1 : 1)) {
     if (Cand->Conversions[ConvIdx].isInitialized()) {
       // We've already checked this conversion.
     } else if (ArgIdx < ParamTypes.size()) {
-      if (ParamTypes[ArgIdx]->isDependentType())
+      if (ParamTypes[ParamIdx]->isDependentType())
         Cand->Conversions[ConvIdx].setAsIdentityConversion(
             Args[ArgIdx]->getType());
       else {
         Cand->Conversions[ConvIdx] =
-            TryCopyInitialization(S, Args[ArgIdx], ParamTypes[ArgIdx],
+            TryCopyInitialization(S, Args[ArgIdx], ParamTypes[ParamIdx],
                                   SuppressUserConversions,
                                   /*InOverloadResolution=*/true,
                                   /*AllowObjCWritebackConversion=*/
@@ -10896,7 +11031,7 @@ SmallVector<OverloadCandidate *, 32> OverloadCandidateSet::CompleteCandidates(
     if (Cand->Viable)
       Cands.push_back(Cand);
     else if (OCD == OCD_AllCandidates) {
-      CompleteNonViableCandidate(S, Cand, Args);
+      CompleteNonViableCandidate(S, Cand, Args, Kind);
       if (Cand->Function || Cand->IsSurrogate)
         Cands.push_back(Cand);
       // Otherwise, this a non-viable builtin candidate.  We do not, in general,
@@ -11453,7 +11588,7 @@ public:
         if (FunctionDecl *Fun =
                 dyn_cast<FunctionDecl>((*I)->getUnderlyingDecl()))
           if (!functionHasPassObjectSizeParams(Fun))
-            S.NoteOverloadCandidate(*I, Fun, TargetFunctionType,
+            S.NoteOverloadCandidate(*I, Fun, CRK_None, TargetFunctionType,
                                     /*TakingAddress=*/true);
       FailedCandidates.NoteCandidates(S, OvlExpr->getBeginLoc());
     }
@@ -12403,7 +12538,7 @@ Sema::CreateOverloadedUnaryOp(SourceLocation OpLoc, UnaryOperatorKind Opc,
   OverloadCandidateSet CandidateSet(OpLoc, OverloadCandidateSet::CSK_Operator);
 
   // Add the candidates from the given function set.
-  AddFunctionCandidates(Fns, ArgsArray, CandidateSet);
+  AddNonMemberOperatorCandidates(Fns, ArgsArray, CandidateSet);
 
   // Add operator candidates that are member functions.
   AddMemberOperatorCandidates(Op, OpLoc, ArgsArray, CandidateSet);
@@ -12548,14 +12683,17 @@ Sema::CreateOverloadedUnaryOp(SourceLocation OpLoc, UnaryOperatorKind Opc,
 ///
 /// \param LHS Left-hand argument.
 /// \param RHS Right-hand argument.
-ExprResult
-Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
-                            BinaryOperatorKind Opc,
-                            const UnresolvedSetImpl &Fns,
-                            Expr *LHS, Expr *RHS, bool PerformADL) {
+ExprResult Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
+                                       BinaryOperatorKind Opc,
+                                       const UnresolvedSetImpl &Fns, Expr *LHS,
+                                       Expr *RHS, bool PerformADL,
+                                       bool AllowRewrittenCandidates) {
   Expr *Args[2] = { LHS, RHS };
   LHS=RHS=nullptr; // Please use only Args instead of LHS/RHS couple
 
+  if (!getLangOpts().CPlusPlus2a)
+    AllowRewrittenCandidates = false;
+
   OverloadedOperatorKind Op = BinaryOperator::getOverloadedOperator(Opc);
   DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op);
 
@@ -12613,23 +12751,61 @@ Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
     return CreateBuiltinBinOp(OpLoc, Opc, Args[0], Args[1]);
 
   // Build an empty overload set.
-  OverloadCandidateSet CandidateSet(OpLoc, OverloadCandidateSet::CSK_Operator);
+  OverloadCandidateSet CandidateSet(
+      OpLoc, OverloadCandidateSet::CSK_Operator,
+      OverloadCandidateSet::OperatorRewriteInfo(Op, AllowRewrittenCandidates));
 
-  // Add the candidates from the given function set.
-  AddFunctionCandidates(Fns, Args, CandidateSet);
+  OverloadedOperatorKind ExtraOp =
+      AllowRewrittenCandidates ? getRewrittenOverloadedOperator(Op) : OO_None;
+
+  // Add the candidates from the given function set. This also adds the
+  // rewritten candidates using these functions if necessary.
+  AddNonMemberOperatorCandidates(Fns, Args, CandidateSet);
 
   // Add operator candidates that are member functions.
   AddMemberOperatorCandidates(Op, OpLoc, Args, CandidateSet);
+  if (CandidateSet.getRewriteInfo().shouldAddReversed(Op))
+    AddMemberOperatorCandidates(Op, OpLoc, {Args[1], Args[0]}, CandidateSet,
+                                OverloadCandidateParamOrder::Reversed);
+
+  // In C++20, also add any rewritten member candidates.
+  if (ExtraOp) {
+    AddMemberOperatorCandidates(ExtraOp, OpLoc, Args, CandidateSet);
+    if (CandidateSet.getRewriteInfo().shouldAddReversed(ExtraOp))
+      AddMemberOperatorCandidates(ExtraOp, OpLoc, {Args[1], Args[0]},
+                                  CandidateSet,
+                                  OverloadCandidateParamOrder::Reversed);
+  }
 
   // Add candidates from ADL. Per [over.match.oper]p2, this lookup is not
   // performed for an assignment operator (nor for operator[] nor operator->,
   // which don't get here).
-  if (Opc != BO_Assign && PerformADL)
+  if (Opc != BO_Assign && PerformADL) {
     AddArgumentDependentLookupCandidates(OpName, OpLoc, Args,
                                          /*ExplicitTemplateArgs*/ nullptr,
                                          CandidateSet);
+    if (ExtraOp) {
+      DeclarationName ExtraOpName =
+          Context.DeclarationNames.getCXXOperatorName(ExtraOp);
+      AddArgumentDependentLookupCandidates(ExtraOpName, OpLoc, Args,
+                                           /*ExplicitTemplateArgs*/ nullptr,
+                                           CandidateSet);
+    }
+  }
 
   // Add builtin operator candidates.
+  //
+  // FIXME: We don't add any rewritten candidates here. This is strictly
+  // incorrect; a builtin candidate could be hidden by a non-viable candidate,
+  // resulting in our selecting a rewritten builtin candidate. For example:
+  //
+  //   enum class E { e };
+  //   bool operator!=(E, E) requires false;
+  //   bool k = E::e != E::e;
+  //
+  // ... should select the rewritten builtin candidate 'operator==(E, E)'. But
+  // it seems unreasonable to consider rewritten builtin candidates. A core
+  // issue has been filed proposing to removed this requirement.
   AddBuiltinOperatorCandidates(Op, OpLoc, Args, CandidateSet);
 
   bool HadMultipleCandidates = (CandidateSet.size() > 1);
@@ -12641,11 +12817,57 @@ Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
       // We found a built-in operator or an overloaded operator.
       FunctionDecl *FnDecl = Best->Function;
 
+      bool IsReversed = (Best->RewriteKind & CRK_Reversed);
+      if (IsReversed)
+        std::swap(Args[0], Args[1]);
+
       if (FnDecl) {
         Expr *Base = nullptr;
         // We matched an overloaded operator. Build a call to that
         // operator.
 
+        OverloadedOperatorKind ChosenOp =
+            FnDecl->getDeclName().getCXXOverloadedOperator();
+
+        // C++2a [over.match.oper]p9:
+        //   If a rewritten operator== candidate is selected by overload
+        //   resolution for an operator@, its return type shall be cv bool
+        if (Best->RewriteKind && ChosenOp == OO_EqualEqual &&
+            !FnDecl->getReturnType()->isBooleanType()) {
+          Diag(OpLoc, diag::err_ovl_rewrite_equalequal_not_bool)
+              << FnDecl->getReturnType() << BinaryOperator::getOpcodeStr(Opc)
+              << Args[0]->getSourceRange() << Args[1]->getSourceRange();
+          Diag(FnDecl->getLocation(), diag::note_declared_at);
+          return ExprError();
+        }
+
+        if (AllowRewrittenCandidates && !IsReversed &&
+            CandidateSet.getRewriteInfo().shouldAddReversed(ChosenOp)) {
+          // We could have reversed this operator, but didn't. Check if the
+          // reversed form was a viable candidate, and if so, if it had a
+          // better conversion for either parameter. If so, this call is
+          // formally ambiguous, and allowing it is an extension.
+          for (OverloadCandidate &Cand : CandidateSet) {
+            if (Cand.Viable && Cand.Function == FnDecl &&
+                Cand.RewriteKind & CRK_Reversed) {
+              for (unsigned ArgIdx = 0; ArgIdx < 2; ++ArgIdx) {
+                if (CompareImplicitConversionSequences(
+                        *this, OpLoc, Cand.Conversions[ArgIdx],
+                        Best->Conversions[ArgIdx]) ==
+                    ImplicitConversionSequence::Better) {
+                  Diag(OpLoc, diag::ext_ovl_ambiguous_oper_binary_reversed)
+                      << BinaryOperator::getOpcodeStr(Opc)
+                      << Args[0]->getType() << Args[1]->getType()
+                      << Args[0]->getSourceRange() << Args[1]->getSourceRange();
+                  Diag(FnDecl->getLocation(),
+                       diag::note_ovl_ambiguous_oper_binary_reversed_candidate);
+                }
+              }
+              break;
+            }
+          }
+        }
+
         // Convert the arguments.
         if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(FnDecl)) {
           // Best->Access is only meaningful for class members.
@@ -12699,8 +12921,8 @@ Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
         ResultTy = ResultTy.getNonLValueExprType(Context);
 
         CXXOperatorCallExpr *TheCall = CXXOperatorCallExpr::Create(
-            Context, Op, FnExpr.get(), Args, ResultTy, VK, OpLoc, FPFeatures,
-            Best->IsADLCandidate);
+            Context, ChosenOp, FnExpr.get(), Args, ResultTy, VK, OpLoc,
+            FPFeatures, Best->IsADLCandidate);
 
         if (CheckCallReturnType(FnDecl->getReturnType(), OpLoc, TheCall,
                                 FnDecl))
@@ -12722,7 +12944,46 @@ Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
                   isa<CXXMethodDecl>(FnDecl), OpLoc, TheCall->getSourceRange(),
                   VariadicDoesNotApply);
 
-        return MaybeBindToTemporary(TheCall);
+        ExprResult R = MaybeBindToTemporary(TheCall);
+        if (R.isInvalid())
+          return ExprError();
+
+        // For a rewritten candidate, we've already reversed the arguments
+        // if needed. Perform the rest of the rewrite now.
+        if ((Best->RewriteKind & CRK_DifferentOperator) ||
+            (Op == OO_Spaceship && IsReversed)) {
+          if (Op == OO_ExclaimEqual) {
+            assert(ChosenOp == OO_EqualEqual && "unexpected operator name");
+            R = CreateBuiltinUnaryOp(OpLoc, UO_LNot, R.get());
+          } else {
+            assert(ChosenOp == OO_Spaceship && "unexpected operator name");
+            llvm::APSInt Zero(Context.getTypeSize(Context.IntTy), false);
+            Expr *ZeroLiteral =
+                IntegerLiteral::Create(Context, Zero, Context.IntTy, OpLoc);
+
+            Sema::CodeSynthesisContext Ctx;
+            Ctx.Kind = Sema::CodeSynthesisContext::RewritingOperatorAsSpaceship;
+            Ctx.Entity = FnDecl;
+            pushCodeSynthesisContext(Ctx);
+
+            R = CreateOverloadedBinOp(
+                OpLoc, Opc, Fns, IsReversed ? ZeroLiteral : R.get(),
+                IsReversed ? R.get() : ZeroLiteral, PerformADL,
+                /*AllowRewrittenCandidates=*/false);
+
+            popCodeSynthesisContext();
+          }
+          if (R.isInvalid())
+            return ExprError();
+        } else {
+          assert(ChosenOp == Op && "unexpected operator name");
+        }
+
+        // Make a note in the AST if we did any rewriting.
+        if (Best->RewriteKind != CRK_None)
+          R = new (Context) CXXRewrittenBinaryOperator(R.get(), IsReversed);
+
+        return R;
       } else {
         // We matched a built-in operator. Convert the arguments, then
         // break out so that we will build the appropriate built-in
@@ -12812,10 +13073,12 @@ Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
         return ExprError();
       }
       CandidateSet.NoteCandidates(
-          PartialDiagnosticAt(OpLoc, PDiag(diag::err_ovl_deleted_oper)
-                                         << BinaryOperator::getOpcodeStr(Opc)
-                                         << Args[0]->getSourceRange()
-                                         << Args[1]->getSourceRange()),
+          PartialDiagnosticAt(
+              OpLoc, PDiag(diag::err_ovl_deleted_oper)
+                         << getOperatorSpelling(Best->Function->getDeclName()
+                                                    .getCXXOverloadedOperator())
+                         << Args[0]->getSourceRange()
+                         << Args[1]->getSourceRange()),
           *this, OCD_AllCandidates, Args, BinaryOperator::getOpcodeStr(Opc),
           OpLoc);
       return ExprError();
@@ -13692,8 +13955,8 @@ ExprResult Sema::BuildLiteralOperatorCall(LookupResult &R,
 
   OverloadCandidateSet CandidateSet(UDSuffixLoc,
                                     OverloadCandidateSet::CSK_Normal);
-  AddFunctionCandidates(R.asUnresolvedSet(), Args, CandidateSet, TemplateArgs,
-                        /*SuppressUserConversions=*/true);
+  AddNonMemberOperatorCandidates(R.asUnresolvedSet(), Args, CandidateSet,
+                                 TemplateArgs);
 
   bool HadMultipleCandidates = (CandidateSet.size() > 1);
 
diff --git a/lib/Sema/SemaTemplate.cpp b/lib/Sema/SemaTemplate.cpp
index 09cc525837..3f2d38630c 100644
--- a/lib/Sema/SemaTemplate.cpp
+++ b/lib/Sema/SemaTemplate.cpp
@@ -24,6 +24,7 @@
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Sema/DeclSpec.h"
 #include "clang/Sema/Lookup.h"
+#include "clang/Sema/Overload.h"
 #include "clang/Sema/ParsedTemplate.h"
 #include "clang/Sema/Scope.h"
 #include "clang/Sema/SemaInternal.h"
@@ -8488,7 +8489,7 @@ bool Sema::CheckFunctionTemplateSpecialization(
     // candidates at once, to get proper sorting and limiting.
     for (auto *OldND : Previous) {
       if (auto *OldFD = dyn_cast<FunctionDecl>(OldND->getUnderlyingDecl()))
-        NoteOverloadCandidate(OldND, OldFD, FD->getType(), false);
+        NoteOverloadCandidate(OldND, OldFD, CRK_None, FD->getType(), false);
     }
     FailedCandidates.NoteCandidates(*this, FD->getLocation());
     return true;
diff --git a/lib/Sema/SemaTemplateInstantiate.cpp b/lib/Sema/SemaTemplateInstantiate.cpp
index 42411c9c33..0daa33cfbe 100644
--- a/lib/Sema/SemaTemplateInstantiate.cpp
+++ b/lib/Sema/SemaTemplateInstantiate.cpp
@@ -206,6 +206,7 @@ bool Sema::CodeSynthesisContext::isInstantiationRecord() const {
   case DefiningSynthesizedFunction:
   case ExceptionSpecEvaluation:
   case ConstraintSubstitution:
+  case RewritingOperatorAsSpaceship:
     return false;
 
   // This function should never be called when Kind's value is Memoization.
@@ -682,6 +683,11 @@ void Sema::PrintInstantiationStack() {
       break;
     }
 
+    case CodeSynthesisContext::RewritingOperatorAsSpaceship:
+      Diags.Report(Active->Entity->getLocation(),
+                   diag::note_rewriting_operator_as_spaceship);
+      break;
+
     case CodeSynthesisContext::Memoization:
       break;
     
@@ -754,6 +760,7 @@ Optional<TemplateDeductionInfo *> Sema::isSFINAEContext() const {
 
     case CodeSynthesisContext::DeclaringSpecialMember:
     case CodeSynthesisContext::DefiningSynthesizedFunction:
+    case CodeSynthesisContext::RewritingOperatorAsSpaceship:
       // This happens in a context unrelated to template instantiation, so
       // there is no SFINAE.
       return None;
diff --git a/lib/Sema/TreeTransform.h b/lib/Sema/TreeTransform.h
index 461cd909c2..89a7b8cc84 100644
--- a/lib/Sema/TreeTransform.h
+++ b/lib/Sema/TreeTransform.h
@@ -2355,13 +2355,13 @@ public:
 
   /// Build a new rewritten operator expression.
   ///
-  /// By default, builds the rewritten operator without performing any semantic
-  /// analysis. Subclasses may override this routine to provide different
-  /// behavior.
-  ExprResult RebuildCXXRewrittenBinaryOperator(Expr *SemanticForm,
-                                             bool IsReversed) {
-    return new (getSema().Context)
-        CXXRewrittenBinaryOperator(SemanticForm, IsReversed);
+  /// By default, performs semantic analysis to build the new expression.
+  /// Subclasses may override this routine to provide different behavior.
+  ExprResult RebuildCXXRewrittenBinaryOperator(
+      SourceLocation OpLoc, BinaryOperatorKind Opcode,
+      const UnresolvedSetImpl &UnqualLookups, Expr *LHS, Expr *RHS) {
+    return getSema().CreateOverloadedBinOp(OpLoc, Opcode, UnqualLookups, LHS,
+                                           RHS, /*RequiresADL*/false);
   }
 
   /// Build a new conditional operator expression.
@@ -9783,24 +9783,45 @@ TreeTransform<Derived>::TransformBinaryOperator(BinaryOperator *E) {
 template <typename Derived>
 ExprResult TreeTransform<Derived>::TransformCXXRewrittenBinaryOperator(
     CXXRewrittenBinaryOperator *E) {
-  // FIXME: C++ [temp.deduct]p7 "The substitution proceeds in lexical order and
-  // stops when a condition that causes deduction to fail is encountered."
-  // requires us to substitute into the LHS before the RHS, even in a rewrite
-  // that reversed the operand order.
-  //
-  // We can't decompose back to a binary operator here, because that would lose
-  // the unqualified lookup results from the phase 1 name lookup.
+  CXXRewrittenBinaryOperator::DecomposedForm Decomp = E->getDecomposedForm();
 
-  ExprResult SemanticForm = getDerived().TransformExpr(E->getSemanticForm());
-  if (SemanticForm.isInvalid())
+  ExprResult LHS = getDerived().TransformExpr(const_cast<Expr*>(Decomp.LHS));
+  if (LHS.isInvalid())
+    return ExprError();
+
+  ExprResult RHS = getDerived().TransformExpr(const_cast<Expr*>(Decomp.RHS));
+  if (RHS.isInvalid())
     return ExprError();
 
   if (!getDerived().AlwaysRebuild() &&
-      SemanticForm.get() == E->getSemanticForm())
+      LHS.get() == Decomp.LHS &&
+      RHS.get() == Decomp.RHS)
     return E;
 
-  return getDerived().RebuildCXXRewrittenBinaryOperator(SemanticForm.get(),
-                                                      E->isReversed());
+  // Extract the already-resolved callee declarations so that we can restrict
+  // ourselves to using them as the unqualified lookup results when rebuilding.
+  UnresolvedSet<2> UnqualLookups;
+  Expr *PossibleBinOps[] = {E->getSemanticForm(),
+                            const_cast<Expr *>(Decomp.InnerBinOp)};
+  for (Expr *PossibleBinOp : PossibleBinOps) {
+    auto *Op = dyn_cast<CXXOperatorCallExpr>(PossibleBinOp->IgnoreImplicit());
+    if (!Op)
+      continue;
+    auto *Callee = dyn_cast<DeclRefExpr>(Op->getCallee()->IgnoreImplicit());
+    if (!Callee || isa<CXXMethodDecl>(Callee->getDecl()))
+      continue;
+
+    // Transform the callee in case we built a call to a local extern
+    // declaration.
+    NamedDecl *Found = cast_or_null<NamedDecl>(getDerived().TransformDecl(
+        E->getOperatorLoc(), Callee->getFoundDecl()));
+    if (!Found)
+      return ExprError();
+    UnqualLookups.addDecl(Found);
+  }
+
+  return getDerived().RebuildCXXRewrittenBinaryOperator(
+      E->getOperatorLoc(), Decomp.Opcode, UnqualLookups, LHS.get(), RHS.get());
 }
 
 template<typename Derived>