[C++2a] Implement operator<=> Part 2: Operator Rewritting and Overload Resolution.

[EricWF]

Summary

This is a work-in-progress attempt to add operator<=> rewriting, including the required changes to overload resolution.

The rewritten expression is represented with the newly added AST node CXXRewrittenExpr. This node contains two sub-statements. The first is a "dummy" expression representing the syntactic form of the initial expression, where the input expressions are represented using OpaqueValueExpr. The second represents the rewritten expression, the input expressions are used here directly (ie are not wrapped in OpaqueValueExprs).

As currently implemented, rewritten and synthesized candidates are only partially checked for viability when they're added to the overload candidates (the conversion sequence from the argument type -> parameter type is checked, but nothing else). This can lead non-viable candidates being selected or causing ambiguity when final overload resolution is attempted.

The solution implemented in this patch is to fully build "potentially viable" candidates if they are selected or cause ambiguity. If building the candidate fails, it is marked as non-viable, and a new best viable function is computed.

The problem with this approach is that it's expensive and potentially wasteful. For example, if overload resolution results in ambiguity with N rewritten candidates with the same partial ordering, then all N candidates are fully built, and those results potentially thrown away.

For builtin candidates this can be avoided by separating out the bits of CheckBinaryOperands which compute it's result type from the bits which actually build the expression and convert the arguments. Once we know the return type of the builtin, we can deduce if the comparison category type can be used in the expression 0 @ <comp-category> without much effect.

However, for non-builtin overloads of operator<=> (which don't return a comparison category type), it seems non-trivial to check that 0 @ <result> is valid without actually attempting to build the overloaded binary operator.

[EricWF]

I'm guessing this implementation is super non-conforming, since expressions are evaluated during overload resolution.

My plan is to keep the general shape of this patch intact, but fix the eager building of expressions with something less wasteful.

[EricWF]

I know how to do better.

include/clang/Sema/Overload.h

943

This is unneeded. As long as the rewritten candidates are added last, restoring the Functions member is unneeded.

[rsmith]

lib/Sema/SemaOverload.cpp

839

I think this might be clearer if named getParamIndexForArgIndex or similar.

8880–8882

No \brief here (we use autobrief), and please use /// for continuation lines.

8888

Does the implementation below actually rely on this?

8901

No, you shouldn't be doing any lookups here. Instead, what you should do is to change the LookupOverloadedOperatorName call in BuildOverloadedBinOp to look up both operator@ and operator<=> in the case where @ is an equality or relational op, and then filter Fns by operator name both here and when adding the non-member function candidates.

The reason is that we need to do these lookups in the context of the template definition when an equality or relational expression appears within a template, so we need to look up both the original operator and <=> eagerly.

8936–8938

Type isn't sufficient to conclude this; you'll need to check the other relevant properties of LHS and RHS too (at least value kind, but maybe also bit-field-ness and others?).

9218–9219

You also need to check the reverse condition and return false (the "or if not that" is ... somehow ... supposed to imply that).

12502–12535

This results in an inadequate representation for the rewritten <=> form. We need to retain the "as-written" form of the operator, for multiple reasons (source fidelity for tooling, expression mangling, pretty-printing, ...). Generally, Clang's philosophy is to desugar the minimum amount that's necessary to capture both the syntactic and semantic forms.

A couple of possible representations come to mind here:

1. A specific Expr subclass for a rewritten <=> operator, which is just a wrapper around a (a <=> b) op 0 expression, and knows how to extract the subexpressions itself, or...
2. A general "rewritten operator wrapper" Expr subclass, which holds its operands and a rewritten expression, and for which the rewritten expression refers to its operands via OpaqueValueExprs. We already have such a class (PseudoObjectExpr).

The former is a smaller and simpler representation, but will likely be more work to implement.

12537–12565

Hmm, this is an interesting approach. It's quite a divergence from our usual approach, which is to perform the viability checks first, before partial ordering, even if we could eliminate some candidates based on partial ordering. And it's observable -- it will result in fewer template instantiations being performed, which will mean we do not diagnose some ill-formed (no diagnostic required) situations which would otherwise fail due to an error in a non-immediate context.

Can you say something about why you chose this approach instead of doing the lookup for operator @ early and marking the candidate non-viable if the lookup / overload resolution for it fails?

(I'm also vaguely wondering whether we should be pushing back on the C++ committee for making viability of the rewritten candidate depend on validity of the @ expression, not just the <=> expression.)

12570–12572

This is a really interesting situation. What does it even mean to consider the (a <=> b) @ c expression if lookup for <=> finds a deleted function? (It would be novel for the return type of a deleted function to be meaningful, and it would be novel to exclude an overload candidate because it's deleted.) And what if lookup for @ finds a deleted function?

I think this is good reason to go back to CWG and suggest that we don't check the @ expression at all until after overload resolution.

12608–12609

This is not correct, because it turns out that isBetterOverloadCandidate is not a strict weak order. It's not any kind of order at all, actually, since it lacks the transitivity property. I don't know whether you can do better than marking your chosen candidate non-viable and rerunning the candidate selection algorithm if your presumed-best candidate turns out to be non-viable.

12634

I am a vampire and

[EricWF]

lib/Sema/SemaOverload.cpp

8888

Like should it be possible to hit this line of code? No. It was preemptive. I'll remove it.

12537–12565

The main reason for choosing this approach was the current expense of validating the candidates eagerly when they're added. Currently builtin candidates need to be fully built before their viability is known. My initial attempt at this made the compiler just about hang.

If I understand what you mean by performing lookup/overload resolution early for operator @, and I probably don't, then it would require performing overload resolution separately every rewritten candidate added, since each candidate could have a different return type.

I think rewritten builtins could be checked more eagerly by moving a bunch of the checking from SemaExpr.cpp to SemaOverload.cpp, and using it to eagerly check the bits we need to, but not actually building the expression as calling into SemaExpr.cpp would currently do.

As for the root question: Should the validity of the @ expression be considered during overload resolution? I think the answer is tricky. For example, the following case could easily occur and break existing code, especially as more users add defaulted comparison operators. In this case if the base class adds <=> without the derived classes knowledge.

struct B {
  using CallbackTy = void(*)();
  CallbackTy CB = nullptr; // B carries around a function pointer.
#if __cplusplus >= 201703L
  friend auto operator<=>(B const&, B const&) = default;
#else
  friend bool operator==(B, B);
  friend bool operator!=(B, B);
#endif
};
struct D {
  operator int() const; // D uses this conversion to provide comparisons.
};
D d;
// comparison ill-formed if the `@` expression isn't considered for viability.
auto r = d < d;

However, allowing the @ expression to effect viability leads to a different set of bugs. For example this slicing comparison bug:

struct B {
  int x;
  friend auto operator<=>(B, B) = default;
};
struct D : B {
  decltype(nullptr) y = {};
  friend auto operator<=>(D, D) = default;
};
D d;
// If the `@` expression is considered for viability, then `operator<=>(B, B)` will be used, effectively slicing the data used during the comparison. 
auto r = d < d;

What is clear is that it should go back to CWG for more discussion.

12570–12572

What does it even mean to consider the (a <=> b) @ c expression if lookup for <=> finds a deleted function?

Separate from allowing return types to affect overload resolution, I suspect selecting a deleted rewritten candidate means that we should have never considered the candidate in the first place. For example:

struct B { auto operator<=>(B) const = delete; };
struct D : private B { operator int() const; };
D{} < D{};

In the above case, the intent of the code seems clear. But because the compiler invented a <=> candidate with a better conversion ranking, our code is ill-formed. Therefore, it makes sense to prefer non-rewritten candidates over deleted rewritten ones.

That said, it certainly doesn't make sense to "make way" for a worse rewritten candidate when the best viable function is deleted. For example:

struct Any { Any(...); };
auto operator<=>(Any, Any);
struct T { friend auto operator<=>(T, T) = delete; };
T{} < T{}; // selecting operator<=>(Any, Any) would be bad.

12608–12609

I was afraid of that, but I bit too tired to initially check this. Thanks for the correction.

If I'm not mistaken, isBetterOverloadCandidate should still be able to provide list of equivalent candidates, which could be used when handling this case.

12634

Ha. I had to look that reference up.

[EricWF]

lib/Sema/SemaOverload.cpp

12537–12565

It's quite a divergence from our usual approach, which is to perform the viability checks first, before partial ordering, even if we could eliminate some candidates based on partial ordering. And it's observable -- it will result in fewer template instantiations being performed, which will mean we do not diagnose some ill-formed (no diagnostic required) situations which would otherwise fail due to an error in a non-immediate context.

I should clarify that the same validity checks are applied to rewritten candidates are also applied to non-rewritten candidates, such as checking conversions to parameter types. So I suspect, for all intents and purposes, it should produce the same amount of template instantiations as existing operator lookup does.

[EricWF]

lib/Sema/SemaOverload.cpp

9218–9219

Hmm. So I'm wondering what is intended by the language F1 and F2 are rewritten candidates, and F2 is a synthesized candidate with reversed order of parameters and F1 is not. For example, what happens when comparing two distinct member functions with only one explicit parameter?

struct T;
struct U { auto operator<=>(T); };
struct T { auto operator<=>(U); };
auto r = T{} < U{}; // Are the synthesized and rewritten overloads ambiguous?

[EricWF]

lib/Sema/SemaOverload.cpp

9218–9219

And what about

struct U {};
struct T { auto operator<=>(U); };
auto operator<=>(U, T);
auto r = T{} < U{};

[EricWF]

lib/Sema/SemaOverload.cpp

9218–9219

Nevermind. I found the language. The implicit object parameter isn't considered in this case.

[rsmith]

Definitely some interesting questions to take to CWG here. :)

lib/Sema/SemaOverload.cpp

9218–9219

The parameters in scope in this rule are the parameters for the purpose of overload resolution, which include the implicit object parameter for a member function.

In your first example, both candidates have implicit conversion sequences with Exact Match rank for both parameters (and none of the ordering special cases apply), so we fall down to this tie-breaker and it selects the T::operator<=>(U) candidate, unless I'm missing something.

Your second example appears to receive the same treatment.

12537–12565

I'm not sure that it's true in general that we get the same amount of instantiation with this approach. For example, checking the @ expression will trigger instantiation of the return type of the operator<=>, and may trigger instantiation of the operator<=> function itself in some cases. (I think this is a conforming technique; I think the more interesting question is whether it's a good thing. I believe GCC uses techniques like this, and it does create portability problems in practice for code written against GCC, for example -- but on the other hand, they presumably spend less time in overload resolution as a result.)

12570–12572

I'm not sure I see clear intent in your first example. B is saying "any attempt to compare me is ill-formed". It's not clear to me what D's intent when privately inheriting from B is. But if the operator<=> were not deleted, we would[1] have selected it (and such selection would even be valid if done in a context in which B is an accessible base class of D) -- so I think that program should be rejected.

[1]: Well, here's the problem. We would have selected it if it returned a type that supports < 0. And that's not a meaningful question to ask. I suppose we could argue that if the "= delete" were simply removed, we'd have rejected it due to trying to use a function with a deduced return type before the return type is available.

[EricWF]

lib/Sema/SemaOverload.cpp

9218–9219

Alright. So I found the wrong language.

I think my first case meant to have const & parameters and const methods. That way the implicit object parameter type matched the reversed parameter type. The second example was meant to demonstrate the case where the implicit object parameter type doesn't match.

What type should we be comparing against in these cases?

[EricWF]

Updating this with the latest work. This adds the semantics for checking and generating default comparison operators.

The overload resolution bits are still a mess, and I'll clean those up shortly. Also there are not sufficient tests yet, those will also come shortly.
I also need to go through the wording for defaulted functions again, to ensure the constexpr and noexcept deduction is correct, as well
as the diagnostics for deleted comparisons.

One oddity introduced here is that defaulted comparisons are evaluated using the "Special Member" matchinary, even though they're
not technically special members, or even members. However, it seemed like the appropriate place to implement them. I'll probably rename
most FooSpecialMember functions to FooDefaultedMember to clear up any confusion.

[EricWF]

• Better integrate defaulted comparison with other special members; this buys correct access, constexpr, and except specification checking.

However it's not clear if this is the best approach. Lookups for defaulted comparison can't be cached like other special members, because the lookup can change after the class definition. It is clear, however, that using the existing machinery would be too expensive if not for cached lookup results, because the checks for constexpr, deletion, and noexcept all depend on the results for lookup being cached.

[rsmith]

Can you split this patch up a bit? There's changes here for the <=> rewriting, but also for supporting operator<=>(...) = default, and some constant evaluation and code generation changes too. It's a lot easier to review more directed, smaller patches.

include/clang/AST/ExprCXX.h

4212

This should have a name ending Expr.

4230–4231

It probably won't ever be type-dependent, but could absolutely be value-dependent, instantiation-dependent, or contain an unexpanded parameter pack.

4294–4296

I find the interface exposed by this class a little confusing. On the one hand, it provides the original expression as an Expr*, and on the other hand it hard-codes knowledge about the form of that expression and exposes accessors into that original form. The upshot is that we pay the cost of a general mechanism (that can cope with any form of original expression) but don't get any benefit from that (because the class hard-codes non-generality).

This also generates a distinctly non-tree-shaped AST; clients naively walking recursively over expressions and their subexpressions will see the same`Expr*` multiple times and potentially end up performing an exponential-time tree walk.

I think there are (at least) two reasonable approaches here:

1. Use OpaqueValueExprs to handle the repeated AST nodes, and track an original expression, a rewritten expression, and probably an original LHS expr and an original RHS expr; the original and rewrite would use OVEs to refer indirectly to the LHS and RHS. Remove all hardcoded knowledge of the original and rewrite from this expression node and make it generic for rewritten expression forms.

2. Make this node explicitly be specific to spaceship rewrites. Remove the original expression pointer and rename it to something more specific. Keep the accessors that make hardcoded assumptions about the form of the rewritten expression.

Option 2 looks closer to what this patch is currently doing (you're not using the original expression much).

lib/AST/ItaniumMangle.cpp

3555

No, the expression should mangle as-written.

[EricWF]

• Remove the = default changes as requested.

• Attempt to work around ambiguity in overload resolution caused by differing lvalue or qualification conversions when ranking synthesized candidates. For example:

struct T {};
auto operator<=>(T const&, T&&);
T{} <=> T{}; // Ambiguous according to the current spec.

The workaround ignores worse implicit conversions when the conversions are both an exact match and a rewritten candidate tie-breaker is present.

[EricWF]

lib/Sema/SemaOverload.cpp

9126

This doesn't seem anywhere close to correct, but It's the best I've come up with so far.
For now though, it seems nice to avoid the ambiguity caused by the current specification.

[EricWF]

Generalize CXXRewrittenExpr to contain only a "representation" of the original expression, and the fully checked rewritten expression. By "representation" i mean to imply that we can't actually build and check a full representation for the expression as written, because it need not be valid. For example:

struct T { auto operator<=>(T const&) const = default; };
T{} < T{};

Currently this patch builds a BinaryOperator node to represent the expression as written, regardless of whether the original expression would actually select a builtin comparison operator. A consequence of this pseudo-representation is that we can't effectively transform it in TreeTransform.h (currently we only transform the rewritten expression and not the representation of the original; there are some kinks I need to work out there).

[EricWF]

• Further generalize CXXRewrittenExpr and get it working with TreeTransform.h.

[EricWF]

• Rebase on master.

I think the correct direction to head with this patch is to start removing the bits of the implementation which evaluate and build rewritten expressions during overload resolution. I'll submit such an update tomorrow.

[EricWF]

I'm still not sure how to best generate a diff that best ignores white spaces changes caused by clang-format or my editor.

I'll work on removing existing whitespace changes.

[EricWF]

Remove a bunch of nonsense this patch originally had. Specifically remove the bits of overload resolution which disambiguated rewritten expressions after the fact; Instead attempt to validate that the return type of the three-way comparison operand in a rewritten relational or equality can be used with the the specified operand (e.g. std::strong_equality cannot be used with a relational operator).

[rsmith]

include/clang/AST/ExprCXX.h

4218–4226

I don't think you need this.

4294–4296

As noted, if you want this to be a general-purpose "rewritten expression" node, you should use OpaqueValueExprs to track the repeated AST nodes between the original and rewritten expression forms rather than forming a non-tree-shaped AST. However, if you want to take that path, you don't need to add a new Expr node for that; that's what PseudoObjectExpr is for.

include/clang/AST/Stmt.h

254

I don't think you need this either.

include/clang/Sema/Overload.h

81–83

These names are not very good. The standard describes both these cases as "rewritten", so ROC_Rewritten is ambiguous, and it says "a synthesized candidate with reversed order of parameters", not merely "synthesized" (which would fail to communicate what's going on).

How about ROC_AsThreeWayComparison and ROC_AsReversedThreeWayComparison or similar?

943

Please instead extend the Functions set to be a set of PointerIntPair<Decl*, 2, RewrittenOperatorCandidateKind>.

include/clang/Serialization/ASTBitCodes.h

1814

Drop the _OPERATOR here.

lib/Sema/SemaOverload.cpp

12542

in a *call* to a

12543–12547

If you want to model this as a generic (syntactic form, semantic form) pair, the syntactic form needs to preserve enough information that TreeTransform on it can recreate the semantic form. That means you need to store a CXXOperatorCallExpr to an UnresolvedLookupExpr to hold Fns if Fns is not empty (see the code at the start of CreateOverloadedBinOp that deals with the type-dependent case for an example of what you would need to do).

Though perhaps this is as good a reason as any to give up the idea of a generic rewrite expression and add something specific to a three-way comparison rewrite; the representation needed to fit this into a generic rewrite mechanism is very unwieldy. (If we add any more forms of rewritten operator later, we can consider whether a generalization is worthwhile.)

lib/Sema/TreeTransform.h

11569–11573

This doesn't seem right to me; TreeTransform should be transforming the original expression, not the rewritten one. We shouldn't be assuming we know what kind of transforms the client wants to perform, it's just our job to give them the syntactic pieces and ask for those pieces to be transformed.

(But this is all redundant if you switch to using PseudoObjectExpr.)

[EricWF]

• Change CXXRewrittenExpr to be a non-general wrapper only for rewritten comparison operators.
• Start fixing and improving overload resolution diagnostics.

[EricWF]

include/clang/AST/ExprCXX.h

4218–4226

I guess it's just future proofing, or an attempt to demonstrate how the class may be generalized. I'll remove it for now.

include/clang/Sema/Overload.h

81–83

Sounds good to me.

943

Sure. I'll get that done.

There are two options here:

(A) Keep the guard object. Store the RewrittenOverloadCandidateKind which we're currently adding candidates for, and have addCandidate and isNewCandidate handle the ROC.

(B) Change all of the AddFooCandidates interfaces in Sema to take yet another default parameter, and pass it around everywhere.

Which would you prefer @rsmith?

lib/Sema/SemaOverload.cpp

12543–12547

I think the FIXME comment may be incorrect.

Shouldn't this be sufficient since we never actually build the rewritten expression until the input expressions are no longer type dependent?
Additionally, with this representation TreeTransform can transform the semantic form, since (if I'm correct), a rebuild should never re-perform overload resolution to choose how to rewrite the initial expression. (Does that make sense, and is it correct?)

I'll go ahead and start converting to a less-general representation of the rewritten expression.

[EricWF]

lib/Sema/SemaOverload.cpp

12543–12547

Nevermind. This was answered offline.

[EricWF]

include/clang/AST/Stmt.h

254

Does keeping it help save bits in CXXRewrittenOperatorExpr?

[EricWF]

Do better english in diagnostics.

[EricWF]

Fix fetching the correct source location information in CXXRewrittenOperatorExpr.

[EricWF]

• Update tests and improve diagnostics. Still more work to be done here though.

include/clang/AST/Expr.h

: Expr(OpaqueValueExprClass, T, VK, OK,
            (SourceExpr && SourceExpr->isValueDependent()),
            T->isInstantiationDependentType() ||
            (SourceExpr && SourceExpr->isInstantiationDependent()),
            false),
       SourceExpr(SourceExpr), Loc(Loc) {
     setIsUnique(false);
   }
 
+  /// Create an OpaqueValueExpr representing the specified source expression
+  static OpaqueValueExpr *Create(const ASTContext &Ctx, Expr *Source);
+
   /// Given an expression which invokes a copy constructor --- i.e.  a
   /// CXXConstructExpr, possibly wrapped in an ExprWithCleanups ---
   /// find the OpaqueValueExpr that's the source of the construction.
   static const OpaqueValueExpr *findInCopyConstruct(const Expr *expr);
 
   explicit OpaqueValueExpr(EmptyShell Empty)
     : Expr(OpaqueValueExprClass, Empty) { }
 

include/clang/AST/ExprCXX.h

   SourceRange Range;
 
   // Only meaningful for floating point types.
   FPOptions FPFeatures;
 
   SourceRange getSourceRangeImpl() const LLVM_READONLY;
 
 public:
+  friend class ASTReader;
+  friend class ASTWriter;
   friend class ASTStmtReader;
   friend class ASTStmtWriter;
 
   CXXOperatorCallExpr(ASTContext& C, OverloadedOperatorKind Op, Expr *fn,
                       ArrayRef<Expr*> args, QualType t, ExprValueKind VK,
                       SourceLocation operatorloc, FPOptions FPFeatures)
       : CallExpr(C, CXXOperatorCallExprClass, fn, args, t, VK, operatorloc),
         Operator(Op), FPFeatures(FPFeatures) {

   static bool classof(const Stmt *T) {
     return T->getStmtClass() == CXXFoldExprClass;
   }
 
   // Iterators
   child_range children() { return child_range(SubExprs, SubExprs + 2); }
 };
 
+class CXXRewrittenExpr : public Expr {
+
+public:
+  enum RewrittenKind { Comparison };
+
+  struct ComparisonBits {
+    /// Whether this rewritten comparison expression has reverse-order
+    /// parameters.
+    unsigned IsSynthesized : 1;
+  };
+
+  union ExtraRewrittenBits {
+    ComparisonBits CompareBits;
+  };
+
+private:
+  friend class ASTReader;
+  friend class ASTStmtReader;
+  friend class ASTStmtWriter;
+
+  Stmt *SubExprs[2];
+  ExtraRewrittenBits ExtraBits;
+
+  CXXRewrittenExpr(EmptyShell Empty) : Expr(CXXRewrittenExprClass, Empty) {}
+
+public:
+  CXXRewrittenExpr(RewrittenKind Kind, Expr *Original, Expr *Rewritten,
+                   ExtraRewrittenBits ExtraBits)
+      : Expr(CXXRewrittenExprClass, Rewritten->getType(),
+             Rewritten->getValueKind(), Rewritten->getObjectKind(),
+             /*Dependent*/ Rewritten->isTypeDependent(),
+             Rewritten->isValueDependent(),
+             Original->isInstantiationDependent(),
+             Rewritten->containsUnexpandedParameterPack()),
+        ExtraBits(ExtraBits) {
+    SubExprs[0] = Original;
+    SubExprs[1] = Rewritten;
+  }
+
+  RewrittenKind getRewrittenKind() const {
+    return static_cast<RewrittenKind>(CXXRewrittenBits.Kind);
+  }
+  void setRewrittenKind(RewrittenKind Kind) { CXXRewrittenBits.Kind = Kind; }
+
+  ExtraRewrittenBits *getRewrittenInfo() { return &ExtraBits; }
+  const ExtraRewrittenBits *getRewrittenInfo() const { return &ExtraBits; }
+
+  Expr *getOriginalExpr() const { return static_cast<Expr *>(SubExprs[0]); }
+  Expr *getRewrittenExpr() const {
+    return static_cast<Expr *>(SubExprs[1]);
+  }
+
+  SourceLocation getLocStart() const {
+    return getOriginalExpr()->getLocStart();
+  }
+  SourceLocation getLocEnd() const { return getOriginalExpr()->getLocEnd(); }
+  SourceLocation getExprLoc() const { return getOriginalExpr()->getExprLoc(); }
+
+  child_range children() { return child_range(SubExprs, SubExprs + 2); }
+
+  static bool classof(const Stmt *T) {
+    return T->getStmtClass() == CXXRewrittenExprClass;
+  }
+};
+
 /// \brief Represents an expression that might suspend coroutine execution;
 /// either a co_await or co_yield expression.
 ///
 /// Evaluation of this expression first evaluates its 'ready' expression. If
 /// that returns 'false':
 ///  -- execution of the coroutine is suspended
 ///  -- the 'suspend' expression is evaluated
 ///     -- if the 'suspend' expression returns 'false', the coroutine is
 ///        resumed
 ///     -- otherwise, control passes back to the resumer.
 /// If the coroutine is not suspended, or when it is resumed, the 'resume'
 /// expression is evaluated, and its result is the result of the overall
 /// expression.
 class CoroutineSuspendExpr : public Expr {
   friend class ASTStmtReader;
 
   SourceLocation KeywordLoc;
 
   enum SubExpr { Common, Ready, Suspend, Resume, Count };
 
   Stmt *SubExprs[SubExpr::Count];
   OpaqueValueExpr *OpaqueValue = nullptr;
 
 public:
   CoroutineSuspendExpr(StmtClass SC, SourceLocation KeywordLoc, Expr *Common,
                        Expr *Ready, Expr *Suspend, Expr *Resume,
                        OpaqueValueExpr *OpaqueValue)
       : Expr(SC, Resume->getType(), Resume->getValueKind(),

include/clang/AST/RecursiveASTVisitor.h

 DEF_TRAVERSE_STMT(SizeOfPackExpr, {})
 DEF_TRAVERSE_STMT(SubstNonTypeTemplateParmPackExpr, {})
 DEF_TRAVERSE_STMT(SubstNonTypeTemplateParmExpr, {})
 DEF_TRAVERSE_STMT(FunctionParmPackExpr, {})
 DEF_TRAVERSE_STMT(MaterializeTemporaryExpr, {})
 DEF_TRAVERSE_STMT(CXXFoldExpr, {})
 DEF_TRAVERSE_STMT(AtomicExpr, {})
 
+DEF_TRAVERSE_STMT(CXXRewrittenExpr, {
+  TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getOriginalExpr());
+  if (!getDerived().shouldVisitImplicitCode()) {
+    TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getRewrittenExpr());
+  }
+  ShouldVisitChildren = false;
+})
+
 // For coroutines expressions, traverse either the operand
 // as written or the implied calls, depending on what the
 // derived class requests.
 DEF_TRAVERSE_STMT(CoroutineBodyStmt, {
   if (!getDerived().shouldVisitImplicitCode()) {
     TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(S->getBody());
     ShouldVisitChildren = false;
   }

include/clang/AST/Stmt.h

class OpaqueValueExprBitfields {
     friend class OpaqueValueExpr;
 
     unsigned : NumExprBits;
 
     /// The OVE is a unique semantic reference to its source expressio if this
     /// bit is set to true.
     unsigned IsUnique : 1;
   };
+  class CXXRewrittenExprBitfields {
+    friend class CXXRewrittenExpr;
+
+    unsigned : NumExprBits;
+
+    unsigned Kind : 1;
+  };
 
   class ObjCIndirectCopyRestoreExprBitfields {
     friend class ObjCIndirectCopyRestoreExpr;
 
     unsigned : NumExprBits;
 
     unsigned ShouldCopy : 1;
   };
union {
     CallExprBitfields CallExprBits;
     ExprWithCleanupsBitfields ExprWithCleanupsBits;
     PseudoObjectExprBitfields PseudoObjectExprBits;
     OpaqueValueExprBitfields OpaqueValueExprBits;
     ObjCIndirectCopyRestoreExprBitfields ObjCIndirectCopyRestoreExprBits;
     InitListExprBitfields InitListExprBits;
     TypeTraitExprBitfields TypeTraitExprBits;
     CoawaitExprBitfields CoawaitBits;
+    CXXRewrittenExprBitfields CXXRewrittenBits;
   };
 
 public:
   // Only allow allocation of Stmts using the allocator in ASTContext
   // or by doing a placement new.
   void* operator new(size_t bytes, const ASTContext& C,
                      unsigned alignment = 8);
 

include/clang/Basic/StmtNodes.td

 def PackExpansionExpr : DStmt<Expr>;
 def SizeOfPackExpr : DStmt<Expr>;
 def SubstNonTypeTemplateParmExpr : DStmt<Expr>;
 def SubstNonTypeTemplateParmPackExpr : DStmt<Expr>;
 def FunctionParmPackExpr : DStmt<Expr>;
 def MaterializeTemporaryExpr : DStmt<Expr>;
 def LambdaExpr : DStmt<Expr>;
 def CXXFoldExpr : DStmt<Expr>;
+def CXXRewrittenExpr : DStmt<Expr>;
 
 // C++ Coroutines TS expressions
 def CoroutineSuspendExpr : DStmt<Expr, 1>;
 def CoawaitExpr : DStmt<CoroutineSuspendExpr>;
 def DependentCoawaitExpr : DStmt<Expr>;
 def CoyieldExpr : DStmt<CoroutineSuspendExpr>;
 
 // Obj-C Expressions.

include/clang/Sema/Overload.h

enum OverloadCandidateDisplayKind {
     /// Requests that all candidates be shown.  Viable candidates will
     /// be printed first.
     OCD_AllCandidates,
 
     /// Requests that only viable candidates be shown.
     OCD_ViableCandidates
   };
 
+  /// OperatorOverloadCandidateKind - The kind of the operator candidate in
+  /// accordance with [over.match.oper].
+  enum RewrittenOverloadCandidateKind : unsigned char {
+    /// Not a rewritten candidate.
+    ROC_None,
+    /// Rewritten but not synthesized.
+    ROC_Rewritten,
+    /// Both rewritten and synthesized.
+    ROC_Synthesized
+  };
+
   /// ImplicitConversionKind - The kind of implicit conversion used to
   /// convert an argument to a parameter's type. The enumerator values
   /// match with the table titled 'Conversions' in [over.ics.scs] and are listed
   /// such that better conversion kinds have smaller values.
   enum ImplicitConversionKind {
     /// Identity conversion (no conversion)
     ICK_Identity = 0,
 
struct OverloadCandidate {
     /// The conversion sequences used to convert the function arguments
     /// to the function parameters.
     ConversionSequenceList Conversions;
 
     /// The FixIt hints which can be used to fix the Bad candidate.
     ConversionFixItGenerator Fix;
 
     /// Viable - True to indicate that this overload candidate is viable.
-    bool Viable;
+    bool Viable : 1;
 
     /// IsSurrogate - True to indicate that this candidate is a
     /// surrogate for a conversion to a function pointer or reference
     /// (C++ [over.call.object]).
-    bool IsSurrogate;
+    bool IsSurrogate : 1;
 
     /// IgnoreObjectArgument - True to indicate that the first
     /// argument's conversion, which for this function represents the
     /// implicit object argument, should be ignored. This will be true
     /// when the candidate is a static member function (where the
     /// implicit object argument is just a placeholder) or a
     /// non-static member function when the call doesn't have an
     /// object argument.
-    bool IgnoreObjectArgument;
+    bool IgnoreObjectArgument : 1;
+
+    /// RewrittenKind - For rewritten operator candidates, the kind of rewritten
+    /// candidate it is: rewritten or synthesized.
+    unsigned char RewrittenOpKind : 2;
 
     /// FailureKind - The reason why this candidate is not viable.
     /// Actually an OverloadFailureKind.
     unsigned char FailureKind;
 
     /// \brief The number of call arguments that were explicitly provided,
     /// to be used while performing partial ordering of function templates.
     unsigned ExplicitCallArguments;
bool TryToFixBadConversion(unsigned Idx, Sema &S) {
 
       // If at least one conversion fails, the candidate cannot be fixed.
       if (!CanFix)
         Fix.clear();
 
       return CanFix;
     }
 
+    /// \brief Return the index of the conversion corresponding to the specified
+    /// argument index. If this is not a synthesized candidate, 'Idx' is
+    /// returned. Otherwise the index corresponding to the reversed parameter
+    /// is returned.
+    unsigned getConversionIndexForArgIndex(unsigned Idx) const;
+
+    /// \brief Return the conversion sequence for the specified argument index.
+    /// If this is a synthesized candidate, the argument index is reversed.
+    const ImplicitConversionSequence &getConversion(unsigned ArgIdx) const;
+
+    /// \brief Returns the parameter type corresponding to the specified index.
+    /// (The index is not reversed for synthesized candidates).
+    QualType getParamType(unsigned Idx) const {
+      if (Function)
+        return Function->getParamDecl(Idx)->getType();
+      return BuiltinParamTypes[Idx];
+    }
+
     unsigned getNumParams() const {
       if (IsSurrogate) {
         auto STy = Surrogate->getConversionType();
         while (STy->isPointerType() || STy->isReferenceType())
           STy = STy->getPointeeType();
         return STy->getAs<FunctionProtoType>()->getNumParams();
       }
       if (Function)
         return Function->getNumParams();
       return ExplicitCallArguments;
     }
+
+    RewrittenOverloadCandidateKind getRewrittenKind() const {
+      return static_cast<RewrittenOverloadCandidateKind>(RewrittenOpKind);
+    }
   };
 
   /// OverloadCandidateSet - A set of overload candidates, used in C++
   /// overload resolution (C++ 13.3).
   class OverloadCandidateSet {
   public:
     enum CandidateSetKind {
       /// Normal lookup.
enum CandidateSetKind {
       /// C++ [over.match.ctor], [over.match.list]
       /// Initialization of an object of class type by constructor,
       /// using either a parenthesized or braced list of arguments.
       CSK_InitByConstructor,
     };
 
   private:
     SmallVector<OverloadCandidate, 16> Candidates;
-    llvm::SmallPtrSet<Decl *, 16> Functions;
+    using DeclSet = llvm::SmallPtrSet<Decl *, 16>;
+    DeclSet Functions;
 
+  private:
     // Allocator for ConversionSequenceLists. We store the first few of these
     // inline to avoid allocation for small sets.
     llvm::BumpPtrAllocator SlabAllocator;
 
     SourceLocation Loc;
     CandidateSetKind Kind;
 
     constexpr static unsigned NumInlineBytes =
T *slabAllocate(unsigned N) {
 
       NumInlineBytesUsed += NBytes;
       return reinterpret_cast<T *>(FreeSpaceStart);
     }
 
     void destroyCandidates();
 
   public:
+    /// \brief RewrittenCandidateContextGuard - Enter a context suitable for
+    /// adding rewritten overload candidates. Rewritten candidates can
+    /// re-consider previously seen functions, so save and clear the list of
+    /// considered functions, and restore it when the rewritten context is
+    /// exited.
+    struct RewrittenCandidateContextGuard {
+      RewrittenCandidateContextGuard(OverloadCandidateSet &CS)
+          : CandidateSet(CS) {
+        assert(CS.Kind == CSK_Operator &&
+               "rewritten expressions can only occur for operators");
+        OldFunctions = std::move(CandidateSet.Functions);
+      }
+
+      ~RewrittenCandidateContextGuard() {
+        CandidateSet.Functions.insert(OldFunctions.begin(), OldFunctions.end());
+      }
+
+    private:
+      OverloadCandidateSet &CandidateSet;
+      DeclSet OldFunctions;
+    };
+
+    friend struct RewrittenCandidateContextGuard;
+
+  public:
     OverloadCandidateSet(SourceLocation Loc, CandidateSetKind CSK)
         : Loc(Loc), Kind(CSK) {}
     OverloadCandidateSet(const OverloadCandidateSet &) = delete;
     OverloadCandidateSet &operator=(const OverloadCandidateSet &) = delete;
     ~OverloadCandidateSet() { destroyCandidates(); }
 
     SourceLocation getLocation() const { return Loc; }
     CandidateSetKind getKind() const { return Kind; }
OverloadCandidate &addCandidate(unsigned NumConversions = 0,
       OverloadCandidate &C = Candidates.back();
       C.Conversions = Conversions.empty()
                           ? allocateConversionSequences(NumConversions)
                           : Conversions;
       return C;
     }
 
     /// Find the best viable function on this overload set, if it exists.
-    OverloadingResult BestViableFunction(Sema &S, SourceLocation Loc,
-                                         OverloadCandidateSet::iterator& Best);
+    OverloadingResult BestViableFunction(
+        Sema &S, SourceLocation Loc, OverloadCandidateSet::iterator &Best,
+        SmallVectorImpl<OverloadCandidate *> *EquivalentCands = nullptr);
 
     void NoteCandidates(Sema &S,
                         OverloadCandidateDisplayKind OCD,
                         ArrayRef<Expr *> Args,
                         StringRef Opc = "",
                         SourceLocation Loc = SourceLocation(),
                         llvm::function_ref<bool(OverloadCandidate&)> Filter =
                           [](OverloadCandidate&) { return true; });

include/clang/Sema/Sema.h

                                     SourceLocation OpLoc, ArrayRef<Expr *> Args,
                                     OverloadCandidateSet& CandidateSet);
   void AddArgumentDependentLookupCandidates(DeclarationName Name,
                                             SourceLocation Loc,
                                             ArrayRef<Expr *> Args,
                                 TemplateArgumentListInfo *ExplicitTemplateArgs,
                                             OverloadCandidateSet& CandidateSet,
                                             bool PartialOverloading = false);
-
+  void AddRewrittenOperatorCandidates(OverloadedOperatorKind Op,
+                                      SourceLocation OpLoc,
+                                      ArrayRef<Expr *> InputArgs,
+                                      const UnresolvedSetImpl &Fns,
+                                      OverloadCandidateSet &CandidateSet,
+                                      bool PerformADL);
   // Emit as a 'note' the specific overload candidate
   void NoteOverloadCandidate(NamedDecl *Found, FunctionDecl *Fn,
                              QualType DestType = QualType(),
                              bool TakingAddress = false);
 
   // Emit as a series of 'note's all template and non-templates identified by
   // the expression Expr
   void NoteAllOverloadCandidates(Expr *E, QualType DestType = QualType(),

                               OverloadCandidateSet *CandidateSet,
                               ExprResult *Result);
 
   ExprResult CreateOverloadedUnaryOp(SourceLocation OpLoc,
                                      UnaryOperatorKind Opc,
                                      const UnresolvedSetImpl &Fns,
                                      Expr *input, bool RequiresADL = true);
 
-  ExprResult CreateOverloadedBinOp(SourceLocation OpLoc,
-                                   BinaryOperatorKind Opc,
-                                   const UnresolvedSetImpl &Fns,
-                                   Expr *LHS, Expr *RHS,
-                                   bool RequiresADL = true);
+  ExprResult CreateOverloadedBinOp(SourceLocation OpLoc, BinaryOperatorKind Opc,
+                                   const UnresolvedSetImpl &Fns, Expr *LHS,
+                                   Expr *RHS, bool RequiresADL = true,
+                                   bool AllowRewrittenCandidates = true);
 
   ExprResult CreateOverloadedArraySubscriptExpr(SourceLocation LLoc,
                                                 SourceLocation RLoc,
                                                 Expr *Base,Expr *Idx);
 
+  ExprResult BuildBinaryOperatorCandidate(SourceLocation OpLoc,
+                                          BinaryOperatorKind Opc,
+                                          const OverloadCandidate &Ovl,
+                                          Expr *LHS, Expr *RHS,
+                                          bool HadMultipleCandidates);
+
   ExprResult
   BuildCallToMemberFunction(Scope *S, Expr *MemExpr,
                             SourceLocation LParenLoc,
                             MultiExprArg Args,
                             SourceLocation RParenLoc);
   ExprResult
   BuildCallToObjectOfClassType(Scope *S, Expr *Object, SourceLocation LParenLoc,
                                MultiExprArg Args,

include/clang/Serialization/ASTBitCodes.h

 
       EXPR_PACK_EXPANSION,                    // PackExpansionExpr
       EXPR_SIZEOF_PACK,                       // SizeOfPackExpr
       EXPR_SUBST_NON_TYPE_TEMPLATE_PARM,      // SubstNonTypeTemplateParmExpr
       EXPR_SUBST_NON_TYPE_TEMPLATE_PARM_PACK, // SubstNonTypeTemplateParmPackExpr
       EXPR_FUNCTION_PARM_PACK,                // FunctionParmPackExpr
       EXPR_MATERIALIZE_TEMPORARY,             // MaterializeTemporaryExpr
       EXPR_CXX_FOLD,                          // CXXFoldExpr
+      EXPR_CXX_REWRITTEN_OPERATOR,            // CXXRewrittenExpr
 
       // CUDA
       EXPR_CUDA_KERNEL_CALL, // CUDAKernelCallExpr
 
       // OpenCL
       EXPR_ASTYPE, // AsTypeExpr
 
       // Microsoft

lib/AST/Expr.cpp

                                       E = LE->capture_end(); I != E; ++I)
       if (I->getCaptureKind() == LCK_ByCopy)
         // FIXME: Only has a side-effect if the variable is volatile or if
         // the copy would invoke a non-trivial copy constructor.
         return true;
     return false;
   }
 
+  case CXXRewrittenExprClass: {
+    const auto *RO = cast<CXXRewrittenExpr>(this);
+    return RO->getRewrittenExpr()->HasSideEffects(Ctx, IncludePossibleEffects);
+  }
+
   case PseudoObjectExprClass: {
     // Only look for side-effects in the semantic form, and look past
     // OpaqueValueExpr bindings in that form.
     const PseudoObjectExpr *PO = cast<PseudoObjectExpr>(this);
     for (PseudoObjectExpr::const_semantics_iterator I = PO->semantics_begin(),
                                                     E = PO->semantics_end();
          I != E; ++I) {
       const Expr *Subexpr = *I;

       ExprBits.InstantiationDependent = true;
     if (exprs[i]->containsUnexpandedParameterPack())
       ExprBits.ContainsUnexpandedParameterPack = true;
 
     Exprs[i] = exprs[i];
   }
 }
 
+OpaqueValueExpr *OpaqueValueExpr::Create(const ASTContext &Ctx, Expr *E) {
+  return new (Ctx) OpaqueValueExpr(E->getExprLoc(), E->getType(),
+                                   E->getValueKind(), E->getObjectKind(), E);
+}
+
 const OpaqueValueExpr *OpaqueValueExpr::findInCopyConstruct(const Expr *e) {
   if (const ExprWithCleanups *ewc = dyn_cast<ExprWithCleanups>(e))
     e = ewc->getSubExpr();
   if (const MaterializeTemporaryExpr *m = dyn_cast<MaterializeTemporaryExpr>(e))
     e = m->GetTemporaryExpr();
   e = cast<CXXConstructExpr>(e)->getArg(0);
   while (const ImplicitCastExpr *ice = dyn_cast<ImplicitCastExpr>(e))
     e = ice->getSubExpr();

lib/AST/ExprClassification.cpp

case Expr::ParenExprClass:
 
     // C11 6.5.1.1p4: [A generic selection] is an lvalue, a function designator,
     // or a void expression if its result expression is, respectively, an
     // lvalue, a function designator, or a void expression.
   case Expr::GenericSelectionExprClass:
     if (cast<GenericSelectionExpr>(E)->isResultDependent())
       return Cl::CL_PRValue;
     return ClassifyInternal(Ctx,cast<GenericSelectionExpr>(E)->getResultExpr());
-
+  case Expr::CXXRewrittenExprClass:
+    return ClassifyInternal(Ctx, cast<CXXRewrittenExpr>(E)->getRewrittenExpr());
   case Expr::BinaryOperatorClass:
   case Expr::CompoundAssignOperatorClass:
     // C doesn't have any binary expressions that are lvalues.
     if (Lang.CPlusPlus)
       return ClassifyBinaryOp(Ctx, cast<BinaryOperator>(E));
     return Cl::CL_PRValue;
 
   case Expr::CallExprClass:

lib/AST/ExprConstant.cpp

   /// Potentially visit a MemberExpr's base expression.
   void VisitIgnoredBaseExpression(const Expr *E) {
     // While MSVC doesn't evaluate the base expression, it does diagnose the
     // presence of side-effecting behavior.
     if (Info.getLangOpts().MSVCCompat && !E->HasSideEffects(Info.Ctx))
       return;
     VisitIgnoredValue(E);
   }
+
+  bool VisitCXXRewrittenExpr(const CXXRewrittenExpr *E) {
+    return StmtVisitorTy::Visit(E->getRewrittenExpr());
+  }
 };
 
 } // namespace
 
 //===----------------------------------------------------------------------===//
 // Common base class for lvalue and temporary evaluation.
 //===----------------------------------------------------------------------===//
 namespace {

   }
   case Expr::CXXDefaultArgExprClass:
     return CheckICE(cast<CXXDefaultArgExpr>(E)->getExpr(), Ctx);
   case Expr::CXXDefaultInitExprClass:
     return CheckICE(cast<CXXDefaultInitExpr>(E)->getExpr(), Ctx);
   case Expr::ChooseExprClass: {
     return CheckICE(cast<ChooseExpr>(E)->getChosenSubExpr(), Ctx);
   }
+  case Expr::CXXRewrittenExprClass:
+    return CheckICE(cast<CXXRewrittenExpr>(E)->getRewrittenExpr(), Ctx);
   }
 
   llvm_unreachable("Invalid StmtClass!");
 }
 
 /// Evaluate an expression as a C++11 integral constant expression.
 static bool EvaluateCPlusPlus11IntegralConstantExpr(const ASTContext &Ctx,
                                                     const Expr *E,

lib/AST/ItaniumMangle.cpp

       Diags.getCustomDiagID(DiagnosticsEngine::Error,
                 "?: operator with omitted middle operand cannot be mangled");
     Diags.Report(E->getExprLoc(), DiagID)
       << E->getStmtClassName() << E->getSourceRange();
     break;
   }
 
   // These are used for internal purposes and cannot be meaningfully mangled.
-  case Expr::OpaqueValueExprClass:
-    llvm_unreachable("cannot mangle opaque value; mangling wrong thing?");
-
+  case Expr::OpaqueValueExprClass: {
+    const OpaqueValueExpr *OVE = cast<OpaqueValueExpr>(E);
+    assert(OVE->getSourceExpr() && "cannot mangle opaque value without a "
+                                   "source expression; mangling wrong thing?");
+    mangleExpression(OVE->getSourceExpr());
+    break;
+  }
   case Expr::InitListExprClass: {
     Out << "il";
     mangleInitListElements(cast<InitListExpr>(E));
     Out << "E";
     break;
   }
 
   case Expr::DesignatedInitExprClass: {

         mangleExpression(DIE->getArrayRangeEnd(Designator));
       }
     }
     mangleExpression(DIE->getInit());
     break;
   }
 
   case Expr::CXXDefaultArgExprClass:
     mangleExpression(cast<CXXDefaultArgExpr>(E)->getExpr(), Arity);
     break;
 
   case Expr::CXXDefaultInitExprClass:
     mangleExpression(cast<CXXDefaultInitExpr>(E)->getExpr(), Arity);
     break;
 
   case Expr::CXXStdInitializerListExprClass:
     mangleExpression(cast<CXXStdInitializerListExpr>(E)->getSubExpr(), Arity);
     break;
 
+  case Expr::CXXRewrittenExprClass:
+    mangleExpression(cast<CXXRewrittenExpr>(E)->getOriginalExpr(), Arity);
+    break;
+
   case Expr::SubstNonTypeTemplateParmExprClass:
     mangleExpression(cast<SubstNonTypeTemplateParmExpr>(E)->getReplacement(),
                      Arity);
     break;
 
   case Expr::UserDefinedLiteralClass:
     // We follow g++'s approach of mangling a UDL as a call to the literal
     // operator.

lib/AST/StmtPrinter.cpp

   OS << "...";
   if (E->getRHS()) {
     OS << " " << BinaryOperator::getOpcodeStr(E->getOperator()) << " ";
     PrintExpr(E->getRHS());
   }
   OS << ")";
 }
 
+void StmtPrinter::VisitCXXRewrittenExpr(CXXRewrittenExpr *E) {
+  // FIXME(EricWF): Are there ever cases where we want to display the rewritten
+  // code? For example when producing diagnostics on implicitly generated
+  // expressions?
+  Visit(E->getOriginalExpr());
+}
+
 // C++ Coroutines TS
 
 void StmtPrinter::VisitCoroutineBodyStmt(CoroutineBodyStmt *S) {
   Visit(S->getBody());
 }
 
 void StmtPrinter::VisitCoreturnStmt(CoreturnStmt *S) {
   OS << "co_return";

lib/AST/StmtProfile.cpp

   VisitExpr(S);
 }
 
 void StmtProfiler::VisitCXXFoldExpr(const CXXFoldExpr *S) {
   VisitExpr(S);
   ID.AddInteger(S->getOperator());
 }
 
+void StmtProfiler::VisitCXXRewrittenExpr(const CXXRewrittenExpr *S) {
+  VisitExpr(S);
+  VisitExpr(S->getRewrittenExpr());
+}
+
 void StmtProfiler::VisitCoroutineBodyStmt(const CoroutineBodyStmt *S) {
   VisitStmt(S);
 }
 
 void StmtProfiler::VisitCoreturnStmt(const CoreturnStmt *S) {
   VisitStmt(S);
 }
 

lib/CodeGen/CGExprScalar.cpp

Value *VisitUnaryPreDec(const UnaryOperator *E) {
     LValue LV = EmitLValue(E->getSubExpr());
     return EmitScalarPrePostIncDec(E, LV, false, true);
   }
   Value *VisitUnaryPreInc(const UnaryOperator *E) {
     LValue LV = EmitLValue(E->getSubExpr());
     return EmitScalarPrePostIncDec(E, LV, true, true);
   }
 
+  Value *VisitCXXRewrittenExpr(const CXXRewrittenExpr *E) {
+    return Visit(E->getRewrittenExpr());
+  }
+
   llvm::Value *EmitIncDecConsiderOverflowBehavior(const UnaryOperator *E,
                                                   llvm::Value *InVal,
                                                   bool IsInc);
 
   llvm::Value *EmitScalarPrePostIncDec(const UnaryOperator *E, LValue LV,
                                        bool isInc, bool isPre);
 
 

lib/Sema/SemaExceptionSpec.cpp

   case Expr::ObjCIvarRefExprClass:
   case Expr::ParenExprClass:
   case Expr::ParenListExprClass:
   case Expr::ShuffleVectorExprClass:
   case Expr::ConvertVectorExprClass:
   case Expr::VAArgExprClass:
     return canSubExprsThrow(*this, E);
 
+  case Expr::CXXRewrittenExprClass:
+    return canThrow(cast<CXXRewrittenExpr>(E)->getRewrittenExpr());
+
     // Some might be dependent for other reasons.
   case Expr::ArraySubscriptExprClass:
   case Expr::OMPArraySectionExprClass:
   case Expr::BinaryOperatorClass:
   case Expr::DependentCoawaitExprClass:
   case Expr::CompoundAssignOperatorClass:
   case Expr::CStyleCastExprClass:
   case Expr::CXXStaticCastExprClass:

lib/Sema/SemaExpr.cpp

   // scope and an argument-dependent lookup based on the types of
   // the arguments.
   UnresolvedSet<16> Functions;
   OverloadedOperatorKind OverOp
     = BinaryOperator::getOverloadedOperator(Opc);
   if (Sc && OverOp != OO_None && OverOp != OO_Equal)
     S.LookupOverloadedOperatorName(OverOp, Sc, LHS->getType(),
                                    RHS->getType(), Functions);
-
+  if (S.getLangOpts().CPlusPlus2a) {
+    if (Sc && Opc != BO_Cmp && BinaryOperator::isRelationalOp(Opc)) {
+      S.LookupOverloadedOperatorName(OO_Spaceship, Sc, LHS->getType(),
+                                     RHS->getType(), Functions);
+    }
+  }
   // Build the (potentially-overloaded, potentially-dependent)
   // binary operation.
   return S.CreateOverloadedBinOp(OpLoc, Opc, Functions, LHS, RHS);
 }
 
 ExprResult Sema::BuildBinOp(Scope *S, SourceLocation OpLoc,
                             BinaryOperatorKind Opc,
                             Expr *LHSExpr, Expr *RHSExpr) {

lib/Sema/SemaOverload.cpp

   case Sema::TDK_DeducedMismatchNested:
     return static_cast<DFIDeducedMismatchArgs*>(Data)->CallArgIndex;
 
   default:
     return llvm::None;
   }
 }
 
+const ImplicitConversionSequence &
+OverloadCandidate::getConversion(unsigned ArgIdx) const {
+  return Conversions[getConversionIndexForArgIndex(ArgIdx)];
+}
+
+unsigned OverloadCandidate::getConversionIndexForArgIndex(unsigned Idx) const {
+  if (getRewrittenKind() != ROC_Synthesized)
+    return Idx;
+  // FIXME(EricWF): Handle these cases.
+  assert(Idx < 2);
+  return Idx == 0 ? 1 : 0;
+}
+
 void OverloadCandidateSet::destroyCandidates() {
   for (iterator i = begin(), e = end(); i != e; ++i) {
     for (auto &C : i->Conversions)
       C.~ImplicitConversionSequence();
     if (!i->Viable && i->FailureKind == ovl_fail_bad_deduction)
       i->DeductionFailure.Destroy();
   }
 }

   // 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))
+      !IsAcceptableNonMemberOperatorCandidate(Context, Function, Args)) {
     return;
+  }
 
   // C++11 [class.copy]p11: [DR1402]
   //   A defaulted move constructor that is defined as deleted is ignored by
   //   overload resolution.
   CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(Function);
+
   if (Constructor && Constructor->isDefaulted() && Constructor->isDeleted() &&
       Constructor->isMoveConstructor())
     return;
 
   // Overload resolution is always an unevaluated context.
   EnterExpressionEvaluationContext Unevaluated(
       *this, Sema::ExpressionEvaluationContext::Unevaluated);
 
   // Add this candidate
   OverloadCandidate &Candidate =
       CandidateSet.addCandidate(Args.size(), EarlyConversions);
   Candidate.FoundDecl = FoundDecl;
   Candidate.Function = Function;
   Candidate.Viable = true;
   Candidate.IsSurrogate = false;
+  Candidate.RewrittenOpKind = ROC_None;
   Candidate.IgnoreObjectArgument = false;
   Candidate.ExplicitCallArguments = Args.size();
 
   if (Function->isMultiVersion() &&
       !Function->getAttr<TargetAttr>()->isDefaultVersion()) {
     Candidate.Viable = false;
     Candidate.FailureKind = ovl_non_default_multiversion_function;
     return;

                 ObjectClassification);
           })) {
     OverloadCandidate &Candidate =
         CandidateSet.addCandidate(Conversions.size(), Conversions);
     Candidate.FoundDecl = FoundDecl;
     Candidate.Function = MethodTmpl->getTemplatedDecl();
     Candidate.Viable = false;
     Candidate.IsSurrogate = false;
+    Candidate.RewrittenOpKind = ROC_None;
     Candidate.IgnoreObjectArgument =
         cast<CXXMethodDecl>(Candidate.Function)->isStatic() ||
         ObjectType.isNull();
     Candidate.ExplicitCallArguments = Args.size();
     if (Result == TDK_NonDependentConversionFailure)
       Candidate.FailureKind = ovl_fail_bad_conversion;
     else {
       Candidate.FailureKind = ovl_fail_bad_deduction;

                                                 SuppressUserConversions);
           })) {
     OverloadCandidate &Candidate =
         CandidateSet.addCandidate(Conversions.size(), Conversions);
     Candidate.FoundDecl = FoundDecl;
     Candidate.Function = FunctionTemplate->getTemplatedDecl();
     Candidate.Viable = false;
     Candidate.IsSurrogate = false;
+    Candidate.RewrittenOpKind = ROC_None;
     // Ignore the object argument if there is one, since we don't have an object
     // type.
     Candidate.IgnoreObjectArgument =
         isa<CXXMethodDecl>(Candidate.Function) &&
         !isa<CXXConstructorDecl>(Candidate.Function);
     Candidate.ExplicitCallArguments = Args.size();
     if (Result == TDK_NonDependentConversionFailure)
       Candidate.FailureKind = ovl_fail_bad_conversion;

   EnterExpressionEvaluationContext Unevaluated(
       *this, Sema::ExpressionEvaluationContext::Unevaluated);
 
   // Add this candidate
   OverloadCandidate &Candidate = CandidateSet.addCandidate(1);
   Candidate.FoundDecl = FoundDecl;
   Candidate.Function = Conversion;
   Candidate.IsSurrogate = false;
+  Candidate.RewrittenOpKind = ROC_None;
   Candidate.IgnoreObjectArgument = false;
   Candidate.FinalConversion.setAsIdentityConversion();
   Candidate.FinalConversion.setFromType(ConvType);
   Candidate.FinalConversion.setAllToTypes(ToType);
   Candidate.Viable = true;
   Candidate.ExplicitCallArguments = 1;
 
   // C++ [over.match.funcs]p4:

         = DeduceTemplateArguments(FunctionTemplate, ToType,
                                   Specialization, Info)) {
     OverloadCandidate &Candidate = CandidateSet.addCandidate();
     Candidate.FoundDecl = FoundDecl;
     Candidate.Function = FunctionTemplate->getTemplatedDecl();
     Candidate.Viable = false;
     Candidate.FailureKind = ovl_fail_bad_deduction;
     Candidate.IsSurrogate = false;
+    Candidate.RewrittenOpKind = ROC_None;
     Candidate.IgnoreObjectArgument = false;
     Candidate.ExplicitCallArguments = 1;
     Candidate.DeductionFailure = MakeDeductionFailureInfo(Context, Result,
                                                           Info);
     return;
   }
 
   // Add the conversion function template specialization produced by

       *this, Sema::ExpressionEvaluationContext::Unevaluated);
 
   OverloadCandidate &Candidate = CandidateSet.addCandidate(Args.size() + 1);
   Candidate.FoundDecl = FoundDecl;
   Candidate.Function = nullptr;
   Candidate.Surrogate = Conversion;
   Candidate.Viable = true;
   Candidate.IsSurrogate = true;
+  Candidate.RewrittenOpKind = ROC_None;
   Candidate.IgnoreObjectArgument = false;
   Candidate.ExplicitCallArguments = Args.size();
 
   // Determine the implicit conversion sequence for the implicit
   // object parameter.
   ImplicitConversionSequence ObjectInit = TryObjectArgumentInitialization(
       *this, CandidateSet.getLocation(), Object->getType(),
       Object->Classify(Context), Conversion, ActingContext);

   EnterExpressionEvaluationContext Unevaluated(
       *this, Sema::ExpressionEvaluationContext::Unevaluated);
 
   // Add this candidate
   OverloadCandidate &Candidate = CandidateSet.addCandidate(Args.size());
   Candidate.FoundDecl = DeclAccessPair::make(nullptr, AS_none);
   Candidate.Function = nullptr;
   Candidate.IsSurrogate = false;
+  Candidate.RewrittenOpKind = ROC_None;
   Candidate.IgnoreObjectArgument = false;
   std::copy(ParamTys, ParamTys + Args.size(), Candidate.BuiltinParamTypes);
 
   // Determine the implicit conversion sequences for each of the
   // arguments.
   Candidate.Viable = true;
   Candidate.ExplicitCallArguments = Args.size();
   for (unsigned ArgIdx = 0, N = Args.size(); ArgIdx != N; ++ArgIdx) {

   case OO_Subscript:
     OpBuilder.addSubscriptOverloads();
     break;
 
   case OO_ArrowStar:
     OpBuilder.addArrowStarOverloads();
     break;
 
   case OO_Conditional:
     OpBuilder.addConditionalOperatorOverloads();
     OpBuilder.addGenericBinaryArithmeticOverloads();
     break;
   }
 }
 
+/// Add the rewritten and synthesized candidates for binary comparison
+///  operators. No additional semantic checking is done to see if the candidate
+///    is well formed.
+void Sema::AddRewrittenOperatorCandidates(OverloadedOperatorKind Op,
+                                          SourceLocation OpLoc,
+                                          ArrayRef<Expr *> InputArgs,
+                                          const UnresolvedSetImpl &Fns,
+                                          OverloadCandidateSet &CandidateSet,
+                                          bool PerformADL) {
+  auto Opc = BinaryOperator::getOverloadedOpcode(Op);
+
+  bool IsRelationalOrEquality =
+      BinaryOperator::isRelationalOp(Opc) || BinaryOperator::isEqualityOp(Opc);
+  if (!IsRelationalOrEquality && Opc != BO_Cmp)
+    return;
+  assert(InputArgs.size() == 2);
+
+  OverloadedOperatorKind CmpOp = OO_Spaceship;
+  DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(CmpOp);
+
+  // AddCandidates - Add operator<=> candidates for the specified set of args,
+  // and mark all newly generated candidates as having the specified
+  // 'RewrittenOverloadCandidateKind'.
+  auto AddCandidates = [&](ArrayRef<Expr *> Args,
+                           RewrittenOverloadCandidateKind Kind) {
+    OverloadCandidateSet::RewrittenCandidateContextGuard Guard(CandidateSet);
+
+    unsigned InitialSize = CandidateSet.size();
+    AddFunctionCandidates(Fns, Args, CandidateSet);
+    AddMemberOperatorCandidates(CmpOp, OpLoc, Args, CandidateSet);
+    if (PerformADL)
+      AddArgumentDependentLookupCandidates(OpName, OpLoc, Args,
+                                           /*ExplicitTemplateArgs*/ nullptr,
+                                           CandidateSet);
+    AddBuiltinOperatorCandidates(CmpOp, OpLoc, Args, CandidateSet);
+
+    for (auto It = std::next(CandidateSet.begin(), InitialSize);
+         It != CandidateSet.end(); ++It) {
+      OverloadCandidate &Ovl = *It;
+      Ovl.RewrittenOpKind = Kind;
+    }
+  };
+
+  // If we have a relational or equality operation, add the rewritten candidates
+  // of the form: (LHS <=> RHS) @ 0
+  if (IsRelationalOrEquality)
+   AddCandidates(InputArgs, ROC_Rewritten);
+
+  // TODO: We should be able to avoid adding synthesized candidates when LHS and
+  // RHS have the same type, value category, and other relevent properties.
+  // In that case synthesized candidates for <=> should be the same as the
+  // rewritten ones. Note: It's still possible for the result of operator<=> to
+  // be usable only on the left or right side of the expression (0 @ <result>)
+  // or (<result> @ 0).
+
+  // For relational, equality, and three-way comparisons, add the rewritten and
+  // synthesized candidates of the form: 0 @ (RHS <=> LHS)
+  SmallVector<Expr *, 2> ReverseArgs(InputArgs.rbegin(), InputArgs.rend());
+  AddCandidates(ReverseArgs, ROC_Synthesized);
+}
+
 /// \brief Add function candidates found via argument-dependent lookup
 /// to the set of overloading candidates.
 ///
 /// This routine performs argument-dependent name lookup based on the
 /// given function name (which may also be an operator name) and adds
 /// all of the overload candidates found by ADL to the overload
 /// candidate set (C++ [basic.lookup.argdep]).
-void
-Sema::AddArgumentDependentLookupCandidates(DeclarationName Name,
-                                           SourceLocation Loc,
-                                           ArrayRef<Expr *> Args,
+void Sema::AddArgumentDependentLookupCandidates(
+    DeclarationName Name, SourceLocation Loc, ArrayRef<Expr *> Args,
     TemplateArgumentListInfo *ExplicitTemplateArgs,
-                                           OverloadCandidateSet& CandidateSet,
-                                           bool PartialOverloading) {
+    OverloadCandidateSet &CandidateSet, bool PartialOverloading) {
   ADLResult Fns;
 
   // FIXME: This approach for uniquing ADL results (and removing
   // redundant candidates from the set) relies on pointer-equality,
   // which means we need to key off the canonical decl.  However,
   // always going back to the canonical decl might not get us the
   // right set of default arguments.  What default arguments are
   // we supposed to consider on ADL candidates, anyway?

   };
 
   // Define functions that don't require ill-formed conversions for a given
   // argument to be better candidates than functions that do.
   unsigned NumArgs = Cand1.Conversions.size();
   assert(Cand2.Conversions.size() == NumArgs && "Overload candidate mismatch");
   bool HasBetterConversion = false;
   for (unsigned ArgIdx = StartArg; ArgIdx < NumArgs; ++ArgIdx) {
-    bool Cand1Bad = IsIllFormedConversion(Cand1.Conversions[ArgIdx]);
-    bool Cand2Bad = IsIllFormedConversion(Cand2.Conversions[ArgIdx]);
+    bool Cand1Bad = IsIllFormedConversion(Cand1.getConversion(ArgIdx));
+    bool Cand2Bad = IsIllFormedConversion(Cand2.getConversion(ArgIdx));
     if (Cand1Bad != Cand2Bad) {
       if (Cand1Bad)
         return false;
       HasBetterConversion = true;
     }
   }
 
   if (HasBetterConversion)
     return true;
 
   // C++ [over.match.best]p1:
   //   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...
   for (unsigned ArgIdx = StartArg; ArgIdx < NumArgs; ++ArgIdx) {
     switch (CompareImplicitConversionSequences(S, Loc,
-                                               Cand1.Conversions[ArgIdx],
-                                               Cand2.Conversions[ArgIdx])) {
+                                               Cand1.getConversion(ArgIdx),
+                                               Cand2.getConversion(ArgIdx))) {
     case ImplicitConversionSequence::Better:
       // Cand1 has a better conversion sequence.
       HasBetterConversion = true;
       break;
 
     case ImplicitConversionSequence::Worse:
       // Cand1 can't be better than Cand2.
       return false;
 
     case ImplicitConversionSequence::Indistinguishable:
       // Do nothing.
       break;
     }
   }
 
   //    -- for some argument j, ICSj(F1) is a better conversion sequence than
   //       ICSj(F2), or, if not that,
   if (HasBetterConversion)
     return true;
 
   //   -- the context is an initialization by user-defined conversion
   //      (see 8.5, 13.3.1.5) and the standard conversion sequence
   //      from the return type of F1 to the destination type (i.e.,
   //      the type of the entity being initialized) is a better

     auto *Cand2Class = cast<CXXRecordDecl>(Cand2.Function->getDeclContext());
     if (Cand1Class->isDerivedFrom(Cand2Class))
       return true;
     if (Cand2Class->isDerivedFrom(Cand1Class))
       return false;
     // Inherited from sibling base classes: still ambiguous.
   }
 
+  // Check C++2a tie-breakers for rewritten candidates
+  {
+    // --- F2 is a rewritten candidate ([over.match.oper]) and F1 is not.
+    RewrittenOverloadCandidateKind C1Roc = Cand1.getRewrittenKind();
+    RewrittenOverloadCandidateKind C2Roc = Cand2.getRewrittenKind();
+    if (C1Roc || C2Roc) {
+      if (!C1Roc || !C2Roc)
+        return !C1Roc;
+      // --- F1 and F2 are rewritten candidates, and F2 is a synthesized
+      // candidate with reversed order of parameters and F1 is not.
+      if ((C1Roc == ROC_Synthesized || C2Roc == ROC_Synthesized) &&
+          C1Roc != C2Roc) {
+        auto GetParamTypes = [&](const OverloadCandidate &Ovl) {
+          SmallVector<QualType, 2> Types;
+          // If the candidate is a method, compute the implicit object type.
+          if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Ovl.Function)) {
+            assert(Ovl.Conversions[0].isStandard());
+            QualType Ty = Ovl.Conversions[0].Standard.getToType(2);
+            assert(!Ty->isReferenceType());
+            const auto *FTP = MD->getType()->getAs<FunctionProtoType>();
+            switch (FTP->getRefQualifier()) {
+            case RQ_LValue:
+            case RQ_None:
+              Types.push_back(S.Context.getLValueReferenceType(Ty));
+              break;
+            case RQ_RValue:
+              Types.push_back(S.Context.getRValueReferenceType(Ty));
+              break;
+            }
+          }
+          for (unsigned I = 0; I < Ovl.getNumParams(); ++I)
+            Types.push_back(Ovl.getParamType(I).getCanonicalType());
+          if (Ovl.getRewrittenKind() == ROC_Synthesized)
+            llvm::reverse(Types);
+          return Types;
+        };
+        if (GetParamTypes(Cand1) == GetParamTypes(Cand2))
+          return C2Roc == ROC_Synthesized;
+      }
+    }
+  }
+
   // Check C++17 tie-breakers for deduction guides.
   {
     auto *Guide1 = dyn_cast_or_null<CXXDeductionGuideDecl>(Cand1.Function);
     auto *Guide2 = dyn_cast_or_null<CXXDeductionGuideDecl>(Cand2.Function);
     if (Guide1 && Guide2) {
       //  -- F1 is generated from a deduction-guide and F2 is not
       if (Guide1->isImplicit() != Guide2->isImplicit())
         return Guide2->isImplicit();

 ///
 /// \param Loc The location of the function name (or operator symbol) for
 /// which overload resolution occurs.
 ///
 /// \param Best If overload resolution was successful or found a deleted
 /// function, \p Best points to the candidate function found.
 ///
 /// \returns The result of overload resolution.
-OverloadingResult
-OverloadCandidateSet::BestViableFunction(Sema &S, SourceLocation Loc,
-                                         iterator &Best) {
+OverloadingResult OverloadCandidateSet::BestViableFunction(
+    Sema &S, SourceLocation Loc, iterator &Best,
+    SmallVectorImpl<OverloadCandidate *> *EquivalentCands) {
   llvm::SmallVector<OverloadCandidate *, 16> Candidates;
   std::transform(begin(), end(), std::back_inserter(Candidates),
                  [](OverloadCandidate &Cand) { return &Cand; });
 
   // [CUDA] HD->H or HD->D calls are technically not allowed by CUDA but
   // are accepted by both clang and NVCC. However, during a particular
   // compilation mode only one call variant is viable. We need to
   // exclude non-viable overload candidates from consideration based

       if (Best == end() ||
           isBetterOverloadCandidate(S, *Cand, *Best, Loc, Kind))
         Best = Cand;
 
   // If we didn't find any viable functions, abort.
   if (Best == end())
     return OR_No_Viable_Function;
 
-  llvm::SmallVector<const NamedDecl *, 4> EquivalentCands;
-
+  llvm::SmallVector<const NamedDecl *, 4> EquivalentFunctionCands;
+  if (EquivalentCands)
+    EquivalentCands->push_back(&(*Best));
   // Make sure that this function is better than every other viable
   // function. If not, we have an ambiguity.
   for (auto *Cand : Candidates) {
     if (Cand->Viable && Cand != Best &&
         !isBetterOverloadCandidate(S, *Best, *Cand, Loc, Kind)) {
+      if (EquivalentCands)
+        EquivalentCands->push_back(Cand);
       if (S.isEquivalentInternalLinkageDeclaration(Best->Function,
                                                    Cand->Function)) {
-        EquivalentCands.push_back(Cand->Function);
+        EquivalentFunctionCands.push_back(Cand->Function);
         continue;
       }
+      if (EquivalentCands)
+        continue;
 
       Best = end();
       return OR_Ambiguous;
     }
   }
+  if (EquivalentCands && EquivalentCands->size() > 1) {
+    Best = end();
+    return OR_Ambiguous;
+  }
 
   // Best is the best viable function.
   if (Best->Function &&
       (Best->Function->isDeleted() ||
        S.isFunctionConsideredUnavailable(Best->Function)))
     return OR_Deleted;
 
-  if (!EquivalentCands.empty())
+  if (!EquivalentFunctionCands.empty())
     S.diagnoseEquivalentInternalLinkageDeclarations(Loc, Best->Function,
-                                                    EquivalentCands);
+                                                    EquivalentFunctionCands);
 
   return OR_Success;
 }
 
 namespace {
 
 enum OverloadCandidateKind {
   oc_function,

   }
 
   // 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.
   return CreateBuiltinUnaryOp(OpLoc, Opc, Input);
 }
 
+ExprResult Sema::BuildBinaryOperatorCandidate(SourceLocation OpLoc,
+                                              BinaryOperatorKind Opc,
+                                              const OverloadCandidate &Ovl,
+                                              Expr *LHSE, Expr *RHSE,
+                                              bool HadMultipleCandidates) {
+  Expr *Args[2] = {LHSE, RHSE};
+  OverloadedOperatorKind Op = BinaryOperator::getOverloadedOperator(Opc);
+  // We found a built-in operator or an overloaded operator.
+  FunctionDecl *FnDecl = Ovl.Function;
+
+  if (FnDecl) {
+    Expr *Base = nullptr;
+    // We matched an overloaded operator. Build a call to that
+    // operator.
+
+    // Convert the arguments.
+    if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(FnDecl)) {
+      // Ovl.Access is only meaningful for class members.
+      CheckMemberOperatorAccess(OpLoc, Args[0], Args[1], Ovl.FoundDecl);
+
+      ExprResult Arg1 =
+          PerformCopyInitialization(InitializedEntity::InitializeParameter(
+                                        Context, FnDecl->getParamDecl(0)),
+                                    SourceLocation(), Args[1]);
+      if (Arg1.isInvalid())
+        return ExprError();
+
+      ExprResult Arg0 = PerformObjectArgumentInitialization(
+          Args[0], /*Qualifier=*/nullptr, Ovl.FoundDecl, Method);
+      if (Arg0.isInvalid())
+        return ExprError();
+      Base = Args[0] = Arg0.getAs<Expr>();
+      Args[1] = Arg1.getAs<Expr>();
+    } else {
+      // Convert the arguments.
+      ExprResult Arg0 =
+          PerformCopyInitialization(InitializedEntity::InitializeParameter(
+                                        Context, FnDecl->getParamDecl(0)),
+                                    SourceLocation(), Args[0]);
+      if (Arg0.isInvalid())
+        return ExprError();
+
+      ExprResult Arg1 =
+          PerformCopyInitialization(InitializedEntity::InitializeParameter(
+                                        Context, FnDecl->getParamDecl(1)),
+                                    SourceLocation(), Args[1]);
+      if (Arg1.isInvalid())
+        return ExprError();
+      Args[0] = Arg0.getAs<Expr>();
+      Args[1] = Arg1.getAs<Expr>();
+    }
+
+    // Build the actual expression node.
+    ExprResult FnExpr = CreateFunctionRefExpr(
+        *this, FnDecl, Ovl.FoundDecl, Base, HadMultipleCandidates, OpLoc);
+    if (FnExpr.isInvalid())
+      return ExprError();
+
+    // Determine the result type.
+    QualType ResultTy = FnDecl->getReturnType();
+    ExprValueKind VK = Expr::getValueKindForType(ResultTy);
+    ResultTy = ResultTy.getNonLValueExprType(Context);
+
+    CXXOperatorCallExpr *TheCall = new (Context) CXXOperatorCallExpr(
+        Context, Op, FnExpr.get(), Args, ResultTy, VK, OpLoc, FPFeatures);
+
+    if (CheckCallReturnType(FnDecl->getReturnType(), OpLoc, TheCall, FnDecl))
+      return ExprError();
+
+    ArrayRef<const Expr *> ArgsArray(Args, 2);
+    const Expr *ImplicitThis = nullptr;
+    // Cut off the implicit 'this'.
+    if (isa<CXXMethodDecl>(FnDecl)) {
+      ImplicitThis = ArgsArray[0];
+      ArgsArray = ArgsArray.slice(1);
+    }
+
+    // Check for a self move.
+    if (Op == OO_Equal)
+      DiagnoseSelfMove(Args[0], Args[1], OpLoc);
+
+    checkCall(FnDecl, nullptr, ImplicitThis, ArgsArray,
+              isa<CXXMethodDecl>(FnDecl), OpLoc, TheCall->getSourceRange(),
+              Sema::VariadicDoesNotApply);
+
+    return MaybeBindToTemporary(TheCall);
+
+  } else {
+    // We matched a built-in operator. Convert the arguments, then
+    // break out so that we will build the appropriate built-in
+    // operator node.
+    ExprResult ArgsRes0 =
+        PerformImplicitConversion(Args[0], Ovl.BuiltinParamTypes[0],
+                                  Ovl.Conversions[0], Sema::AA_Passing);
+    if (ArgsRes0.isInvalid())
+      return ExprError();
+    Args[0] = ArgsRes0.get();
+
+    ExprResult ArgsRes1 =
+        PerformImplicitConversion(Args[1], Ovl.BuiltinParamTypes[1],
+                                  Ovl.Conversions[1], Sema::AA_Passing);
+    if (ArgsRes1.isInvalid())
+      return ExprError();
+    Args[1] = ArgsRes1.get();
+  }
+  // We matched a built-in operator; build it.
+  return CreateBuiltinBinOp(OpLoc, Opc, Args[0], Args[1]);
+}
+
+namespace {
+
+/// \brief RewrittenOverloadResolver - This class handles initial
+/// overload resolution for candidate sets which include rewritten candidates.
+///
+/// Rewritten candidates haven't been fully checked for validity. They may still
+/// be invalid if:
+///    (A) The rewritten candidate is a builtin, but semantic checking of the
+///        builtin would fail.
+///    (B) The result of the "partially rewritten expression"
+///        (ie the (LHS <=> RHS) part) is ill-formed when used as an operand to
+///        (<result> @ 0) or (0 @ <result>).
+///
+/// TODO: Separate out the bits of semantic checking for builtin spaceship
+/// operators which determine validity and the return type, and use that instead
+/// of building the full expression to check validity.
+class RewrittenOverloadResolver {
+  enum CheckOverloadResult { Done, Continue };
+
+public:
+  RewrittenOverloadResolver(Sema &S, SourceLocation OpLoc,
+                            BinaryOperatorKind Opc, ArrayRef<Expr *> Args,
+                            const UnresolvedSetImpl &Fns, bool PerformADL,
+                            OverloadCandidateSet &CS)
+      : S(S), OpLoc(OpLoc), Opc(Opc), Args(Args), Fns(Fns),
+        PerformADL(PerformADL), CandidateSet(CS) {}
+
+  ExprResult ResolveRewrittenCandidates() {
+    ExprResult FinalResult = ExprError();
+    OverloadCandidateSet::iterator Best;
+    OverloadingResult OvlRes;
+    llvm::SmallVector<OverloadCandidate *, 4> EquivCands;
+    do {
+      EquivCands.clear();
+      OvlRes = CandidateSet.BestViableFunction(S, OpLoc, Best, &EquivCands);
+    } while (Continue == RemoveNonViableRewrittenCandidates(
+                             OvlRes, Best, EquivCands, FinalResult));
+    return FinalResult;
+  }
+private:
+  CheckOverloadResult RemoveNonViableRewrittenCandidates(
+      OverloadingResult OvlRes, OverloadCandidateSet::iterator Best,
+      ArrayRef<OverloadCandidate *> EquivCands, ExprResult &FinalResult);
+  ExprResult BuildRewrittenCandidate(const OverloadCandidate &Ovl);
+
+  RewrittenOverloadResolver(RewrittenOverloadResolver const &) = delete;
+  RewrittenOverloadResolver &
+  operator=(RewrittenOverloadResolver const &) = delete;
+
+private:
+  Sema &S;
+  SourceLocation OpLoc;
+  BinaryOperatorKind Opc;
+  ArrayRef<Expr *> Args;
+  const UnresolvedSetImpl &Fns;
+  bool PerformADL;
+  OverloadCandidateSet &CandidateSet;
+};
+} // end namespace
+
+ExprResult RewrittenOverloadResolver::BuildRewrittenCandidate(
+    const OverloadCandidate &Ovl) {
+  Expr *RewrittenArgs[2] = {Args[0], Args[1]};
+  assert(Ovl.getRewrittenKind());
+  bool IsSynthesized = Ovl.getRewrittenKind() == ROC_Synthesized;
+  if (IsSynthesized)
+    std::swap(RewrittenArgs[0], RewrittenArgs[1]);
+
+  // Supress diagnostics when building the expressions for the specified
+  // candidate. If evaluation fails the candidate will be marked non-viable
+  // and the best viable candidate re-computed.
+  Sema::TentativeAnalysisScope DiagnosticScopeGuard(S);
+
+  // Build the '(LHS <=> RHS)' operand to the full expression.
+  ExprResult RewrittenRes = S.BuildBinaryOperatorCandidate(
+      OpLoc, BO_Cmp, Ovl, RewrittenArgs[0], RewrittenArgs[1],
+      /*HadMultipleCandidates*/ false);
+  if (RewrittenRes.isInvalid())
+    return ExprError();
+
+  if (Opc != BO_Cmp) {
+    // Now attempt to build the full expression '(LHS <=> RHS) @ 0' using the
+    // evaluated operand and the literal 0.
+    llvm::APInt I =
+        llvm::APInt::getNullValue(S.Context.getIntWidth(S.Context.IntTy));
+    Expr *Zero =
+        IntegerLiteral::Create(S.Context, I, S.Context.IntTy, SourceLocation());
+
+    Expr *NewLHS = RewrittenRes.get();
+    Expr *NewRHS = Zero;
+    if (Ovl.getRewrittenKind() == ROC_Synthesized)
+      std::swap(NewLHS, NewRHS);
+
+    RewrittenRes =
+        S.CreateOverloadedBinOp(OpLoc, Opc, Fns, NewLHS, NewRHS, PerformADL,
+                                /*AllowRewrittenCandidates*/ false);
+    if (RewrittenRes.isInvalid())
+      return ExprError();
+  }
+  Expr *Rewritten = RewrittenRes.get();
+
+  // Create a dummy expression representing the original expression as written.
+  // FIXME(EricWF): This doesn't actually really represent the expression as
+  // written, because it may not result in a to a builtin operator.
+  Expr *Original = new (S.Context)
+      BinaryOperator(OpaqueValueExpr::Create(S.Context, Args[0]),
+                     OpaqueValueExpr::Create(S.Context, Args[1]), Opc,
+                     Rewritten->getType(), Rewritten->getValueKind(),
+                     Rewritten->getObjectKind(), OpLoc, S.FPFeatures);
+
+  CXXRewrittenExpr::ExtraRewrittenBits ExtraBits;
+  ExtraBits.CompareBits.IsSynthesized = IsSynthesized;
+  return new (S.Context) CXXRewrittenExpr(CXXRewrittenExpr::Comparison,
+                                          Original, Rewritten, ExtraBits);
+}
+
+/// Rewritten candidates have been added but not checked for validity. They
+/// could still be non-viable if:
+///  (A) The rewritten call (x <=> y) is a builtin, but it will be ill-formed
+///      when built (for example it has narrowing conversions).
+///  (B) The expression (x <=> y) @ 0 is ill-formed for the result of (x <=> y).
+///
+/// If either is the case, this function should be considered non-viable and
+/// another best viable function needs to be computed.
+///
+/// Therefore, we do the following:
+///  (1) If we have no viable candidate, or a deleted candidate, stop.
+///      Otherwise, if we have a best viable candidate or a set of ambiguous
+///      candidates and none of them are rewritten, stop.
+///
+///  (2) If the best viable candidate is a rewritten candidate, build and
+///      check the full expression for that candidate. If it succeeds return
+///      the result. Otherwise, mark the candidate as non-viable, re-compute
+///      the best viable function, and continue.
+///
+///  (3) If we have ambiguity attempt to resolve it by evaluating each rewritten
+///      candidate causing ambiguity:
+///
+///        (3.1) build the full expression for the specified candidate.
+///        (3.2) If the result is invalid, mark the candidate as non-viable.
+///
+///      If only one viable candidate remains, stop. If the viable candidate is
+///      rewritten, return the previously computed full expression. Otherwise,
+///      if we have more than one viable candidate, stop. If no viable candidates
+///      remain from the initial set of equally ranked candidates, recompute the
+///      new best viable overload and continue.
+RewrittenOverloadResolver::CheckOverloadResult
+RewrittenOverloadResolver::RemoveNonViableRewrittenCandidates(
+    OverloadingResult OvlRes, OverloadCandidateSet::iterator Best,
+    ArrayRef<OverloadCandidate *> EquivCands, ExprResult &FinalResult) {
+  auto Success = [&](ExprResult Res) {
+    FinalResult = Res;
+    return Done;
+  };
+  switch (OvlRes) {
+  case OR_Deleted:
+    // FIXME(EricWF): If we've found a deleted rewritten operator, it's
+    // possible we should have never considered it a viable candidate.
+  case OR_No_Viable_Function:
+    return Done;
+
+  case OR_Success: {
+    OverloadCandidate &Ovl = *Best;
+    if (!Ovl.getRewrittenKind())
+      return Done;
+    // Build the full expression for the rewritten candidate, and return it if
+    // it's valid. Otherwise mark this candidate as non-viable and continue.
+    ExprResult Res = BuildRewrittenCandidate(Ovl);
+    if (Res.isInvalid()) {
+      Ovl.Viable = false;
+      return Continue;
+    }
+    return Success(Res);
+  }
+  case OR_Ambiguous: {
+    assert(EquivCands.size() > 1);
+    // If none of the viable candidates are rewritten, stop.
+    if (llvm::none_of(EquivCands, [](const OverloadCandidate *Cand) {
+          return (bool)Cand->getRewrittenKind();
+        }))
+      return Done;
+    int NumViableCandidates = 0;
+    ExprResult ViableRewritten = ExprError();
+    for (auto *Cand : EquivCands) {
+      OverloadCandidate &Ovl = *Cand;
+      if (Ovl.getRewrittenKind()) {
+        ExprResult Res = BuildRewrittenCandidate(Ovl);
+        if (Res.isInvalid()) {
+          Ovl.Viable = false;
+          continue;
+        }
+        ViableRewritten = Res;
+      }
+      ++NumViableCandidates;
+    }
+    // If only one of the candidates turns out to be viable, and it's a
+    // rewritten candidate, return that candidate as the result.
+    if (NumViableCandidates == 1 && !ViableRewritten.isInvalid())
+      return Success(ViableRewritten);
+    // If we still have ambiguity, return and let the caller diagnose it.
+    if (NumViableCandidates > 1)
+      return Done;
+    // All of the equally ranked candidates are invalid. Loop and try overload
+    // resolution again.
+    return Continue;
+  }
+  }
+  llvm_unreachable("unhandled case");
+}
+
 /// \brief Create a binary operation that may resolve to an overloaded
 /// operator.
 ///
 /// \param OpLoc The location of the operator itself (e.g., '+').
 ///
 /// \param Opc The BinaryOperatorKind that describes this operator.
 ///
 /// \param Fns The set of non-member functions that will be
 /// considered by overload resolution. The caller needs to build this
 /// set based on the context using, e.g.,
 /// LookupOverloadedOperatorName() and ArgumentDependentLookup(). This
 /// set should not contain any member functions; those will be added
 /// by CreateOverloadedBinOp().
 ///
 /// \param LHS Left-hand argument.
 /// \param RHS Right-hand argument.
-ExprResult
-Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
+ExprResult Sema::CreateOverloadedBinOp(SourceLocation OpLoc,
                                        BinaryOperatorKind Opc,
-                            const UnresolvedSetImpl &Fns,
-                            Expr *LHS, Expr *RHS, bool PerformADL) {
+                                       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
 
   OverloadedOperatorKind Op = BinaryOperator::getOverloadedOperator(Opc);
   DeclarationName OpName = Context.DeclarationNames.getCXXOperatorName(Op);
 
   // If either side is type-dependent, create an appropriate dependent
   // expression.

   if (Opc == BO_Assign && !Args[0]->getType()->isOverloadableType())
     return CreateBuiltinBinOp(OpLoc, Opc, Args[0], Args[1]);
 
   // If this is the .* operator, which is not overloadable, just
   // create a built-in binary operator.
   if (Opc == BO_PtrMemD)
     return CreateBuiltinBinOp(OpLoc, Opc, Args[0], Args[1]);
 
+  UnresolvedSet<6> OrigFuncs;
+  UnresolvedSet<6> ThreeWayFuncs;
+  for (NamedDecl *D : Fns) {
+    FunctionDecl *FD = D->getAsFunction();
+    if (FD) {
+      assert(FD->isOverloadedOperator());
+      if (FD->getOverloadedOperator() == OO_Spaceship) {
+        ThreeWayFuncs.addDecl(D);
+        if (Op == OO_Spaceship)
+          OrigFuncs.addDecl(D);
+      } else
+        OrigFuncs.addDecl(D);
+    } else
+      OrigFuncs.addDecl(D);
+  }
+
   // Build an empty overload set.
   OverloadCandidateSet CandidateSet(OpLoc, OverloadCandidateSet::CSK_Operator);
 
   // Add the candidates from the given function set.
-  AddFunctionCandidates(Fns, Args, CandidateSet);
+  AddFunctionCandidates(OrigFuncs, Args, CandidateSet);
 
   // Add operator candidates that are member functions.
   AddMemberOperatorCandidates(Op, OpLoc, Args, CandidateSet);
 
   // 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)
     AddArgumentDependentLookupCandidates(OpName, OpLoc, Args,
                                          /*ExplicitTemplateArgs*/ nullptr,
                                          CandidateSet);
 
   // Add builtin operator candidates.
   AddBuiltinOperatorCandidates(Op, OpLoc, Args, CandidateSet);
 
-  bool HadMultipleCandidates = (CandidateSet.size() > 1);
-
-  // Perform overload resolution.
-  OverloadCandidateSet::iterator Best;
-  switch (CandidateSet.BestViableFunction(*this, OpLoc, Best)) {
-    case OR_Success: {
-      // We found a built-in operator or an overloaded operator.
-      FunctionDecl *FnDecl = Best->Function;
-
-      if (FnDecl) {
-        Expr *Base = nullptr;
-        // We matched an overloaded operator. Build a call to that
-        // operator.
-
-        // Convert the arguments.
-        if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(FnDecl)) {
-          // Best->Access is only meaningful for class members.
-          CheckMemberOperatorAccess(OpLoc, Args[0], Args[1], Best->FoundDecl);
-
-          ExprResult Arg1 =
-            PerformCopyInitialization(
-              InitializedEntity::InitializeParameter(Context,
-                                                     FnDecl->getParamDecl(0)),
-              SourceLocation(), Args[1]);
-          if (Arg1.isInvalid())
-            return ExprError();
-
-          ExprResult Arg0 =
-            PerformObjectArgumentInitialization(Args[0], /*Qualifier=*/nullptr,
-                                                Best->FoundDecl, Method);
-          if (Arg0.isInvalid())
-            return ExprError();
-          Base = Args[0] = Arg0.getAs<Expr>();
-          Args[1] = RHS = Arg1.getAs<Expr>();
-        } else {
-          // Convert the arguments.
-          ExprResult Arg0 = PerformCopyInitialization(
-            InitializedEntity::InitializeParameter(Context,
-                                                   FnDecl->getParamDecl(0)),
-            SourceLocation(), Args[0]);
-          if (Arg0.isInvalid())
-            return ExprError();
-
-          ExprResult Arg1 =
-            PerformCopyInitialization(
-              InitializedEntity::InitializeParameter(Context,
-                                                     FnDecl->getParamDecl(1)),
-              SourceLocation(), Args[1]);
-          if (Arg1.isInvalid())
-            return ExprError();
-          Args[0] = LHS = Arg0.getAs<Expr>();
-          Args[1] = RHS = Arg1.getAs<Expr>();
+  // C++2a Add rewritten and synthesized operator candidates.
+  bool HasRewrittenCandidates = false;
+  if (getLangOpts().CPlusPlus2a && AllowRewrittenCandidates &&
+      BinaryOperator::isComparisonOp(Opc)) {
+    unsigned BeforeRewrittenSize = CandidateSet.size();
+    AddRewrittenOperatorCandidates(Op, OpLoc, Args, ThreeWayFuncs, CandidateSet,
+                                   PerformADL);
+    HasRewrittenCandidates = BeforeRewrittenSize != CandidateSet.size();
   }
 
-        // Build the actual expression node.
-        ExprResult FnExpr = CreateFunctionRefExpr(*this, FnDecl,
-                                                  Best->FoundDecl, Base,
-                                                  HadMultipleCandidates, OpLoc);
-        if (FnExpr.isInvalid())
-          return ExprError();
-
-        // Determine the result type.
-        QualType ResultTy = FnDecl->getReturnType();
-        ExprValueKind VK = Expr::getValueKindForType(ResultTy);
-        ResultTy = ResultTy.getNonLValueExprType(Context);
-
-        CXXOperatorCallExpr *TheCall =
-          new (Context) CXXOperatorCallExpr(Context, Op, FnExpr.get(),
-                                            Args, ResultTy, VK, OpLoc,
-                                            FPFeatures);
-
-        if (CheckCallReturnType(FnDecl->getReturnType(), OpLoc, TheCall,
-                                FnDecl))
-          return ExprError();
-
-        ArrayRef<const Expr *> ArgsArray(Args, 2);
-        const Expr *ImplicitThis = nullptr;
-        // Cut off the implicit 'this'.
-        if (isa<CXXMethodDecl>(FnDecl)) {
-          ImplicitThis = ArgsArray[0];
-          ArgsArray = ArgsArray.slice(1);
-        }
-
-        // Check for a self move.
-        if (Op == OO_Equal)
-          DiagnoseSelfMove(Args[0], Args[1], OpLoc);
-
-        checkCall(FnDecl, nullptr, ImplicitThis, ArgsArray,
-                  isa<CXXMethodDecl>(FnDecl), OpLoc, TheCall->getSourceRange(),
-                  VariadicDoesNotApply);
+  if (HasRewrittenCandidates) {
+    RewrittenOverloadResolver RewrittenOvlResolver(*this, OpLoc, Opc, Args, Fns,
+                                                   PerformADL, CandidateSet);
 
-        return MaybeBindToTemporary(TheCall);
-      } else {
-        // We matched a built-in operator. Convert the arguments, then
-        // break out so that we will build the appropriate built-in
-        // operator node.
-        ExprResult ArgsRes0 =
-            PerformImplicitConversion(Args[0], Best->BuiltinParamTypes[0],
-                                      Best->Conversions[0], AA_Passing);
-        if (ArgsRes0.isInvalid())
-          return ExprError();
-        Args[0] = ArgsRes0.get();
+    // Perform initial overload resolution that includes partially checked
+    // rewritten candidates, removing rewritten candidates which turn out to be
+    // invalid as needed.
+    ExprResult RewrittenResult =
+        RewrittenOvlResolver.ResolveRewrittenCandidates();
 
-        ExprResult ArgsRes1 =
-            PerformImplicitConversion(Args[1], Best->BuiltinParamTypes[1],
-                                      Best->Conversions[1], AA_Passing);
-        if (ArgsRes1.isInvalid())
-          return ExprError();
-        Args[1] = ArgsRes1.get();
-        break;
-      }
+    // If overload resolution was successful and the result was a re-written
+    // overload candidate, then that candidate was evaluated and we can return
+    // the result directly.
+    if (!RewrittenResult.isInvalid())
+      return RewrittenResult;
   }
 
+  // Perform final overload resolution.
+  bool HadMultipleCandidates = (CandidateSet.size() > 1);
+  OverloadCandidateSet::iterator Best;
+  switch (CandidateSet.BestViableFunction(*this, OpLoc, Best)) {
+  case OR_Success:
+    assert(
+        !Best->getRewrittenKind() &&
+        "rewritten candidates should have already been resolved and evaluated");
+    return BuildBinaryOperatorCandidate(OpLoc, Opc, *Best, Args[0], Args[1],
+                                        HadMultipleCandidates);
   case OR_No_Viable_Function: {
     // C++ [over.match.oper]p9:
     //   If the operator is the operator , [...] and there are no
     //   viable functions, then the operator is assumed to be the
     //   built-in operator and interpreted according to clause 5.
     if (Opc == BO_Comma)
       break;
 
     // For class as left operand for assignment or compound assignment
     // operator do not fall through to handling in built-in, but report that
     // no overloaded assignment operator found
     ExprResult Result = ExprError();
-      if (Args[0]->getType()->isRecordType() &&
-          Opc >= BO_Assign && Opc <= BO_OrAssign) {
+    if (Args[0]->getType()->isRecordType() && Opc >= BO_Assign &&
+        Opc <= BO_OrAssign) {
       Diag(OpLoc, diag::err_ovl_no_viable_oper)
-             << BinaryOperator::getOpcodeStr(Opc)
-             << Args[0]->getSourceRange() << Args[1]->getSourceRange();
+          << BinaryOperator::getOpcodeStr(Opc) << Args[0]->getSourceRange()
+          << Args[1]->getSourceRange();
       if (Args[0]->getType()->isIncompleteType()) {
         Diag(OpLoc, diag::note_assign_lhs_incomplete)
-            << Args[0]->getType()
-            << Args[0]->getSourceRange() << Args[1]->getSourceRange();
+            << Args[0]->getType() << Args[0]->getSourceRange()
+            << Args[1]->getSourceRange();
       }
     } else {
       // This is an erroneous use of an operator which can be overloaded by
       // a non-member function. Check for non-member operators which were
       // defined too late to be candidates.
       if (DiagnoseTwoPhaseOperatorLookup(*this, Op, OpLoc, Args))
         // FIXME: Recover by calling the found function.
         return ExprError();
 
       // No viable function; try to create a built-in operation, which will
       // produce an error. Then, show the non-viable candidates.
       Result = CreateBuiltinBinOp(OpLoc, Opc, Args[0], Args[1]);
     }
     assert(Result.isInvalid() &&
            "C++ binary operator overloading is missing candidates!");
     if (Result.isInvalid())
       CandidateSet.NoteCandidates(*this, OCD_AllCandidates, Args,
                                   BinaryOperator::getOpcodeStr(Opc), OpLoc);
     return Result;
   }
-
   case OR_Ambiguous:
     Diag(OpLoc, diag::err_ovl_ambiguous_oper_binary)
-          << BinaryOperator::getOpcodeStr(Opc)
-          << Args[0]->getType() << Args[1]->getType()
-          << Args[0]->getSourceRange() << Args[1]->getSourceRange();
+        << BinaryOperator::getOpcodeStr(Opc) << Args[0]->getType()
+        << Args[1]->getType() << Args[0]->getSourceRange()
+        << Args[1]->getSourceRange();
     CandidateSet.NoteCandidates(*this, OCD_ViableCandidates, Args,
                                 BinaryOperator::getOpcodeStr(Opc), OpLoc);
     return ExprError();
 
   case OR_Deleted:
     if (isImplicitlyDeleted(Best->Function)) {
       CXXMethodDecl *Method = cast<CXXMethodDecl>(Best->Function);
       Diag(OpLoc, diag::err_ovl_deleted_special_oper)
           << Context.getRecordType(Method->getParent())
           << getSpecialMember(Method);
 
       // The user probably meant to call this special member. Just
       // explain why it's deleted.
       NoteDeletedFunction(Method);
       return ExprError();
     } else {
       Diag(OpLoc, diag::err_ovl_deleted_oper)
-          << Best->Function->isDeleted()
-          << BinaryOperator::getOpcodeStr(Opc)
+          << Best->Function->isDeleted() << BinaryOperator::getOpcodeStr(Opc)
           << getDeletedOrUnavailableSuffix(Best->Function)
           << Args[0]->getSourceRange() << Args[1]->getSourceRange();
     }
     CandidateSet.NoteCandidates(*this, OCD_AllCandidates, Args,
                                 BinaryOperator::getOpcodeStr(Opc), OpLoc);
     return ExprError();
   }
 

lib/Sema/TreeTransform.h

   ///
   /// By default, produces the fallback value for the fold-expression, or
   /// produce an error if there is no fallback value.
   ExprResult RebuildEmptyCXXFoldExpr(SourceLocation EllipsisLoc,
                                      BinaryOperatorKind Operator) {
     return getSema().BuildEmptyCXXFoldExpr(EllipsisLoc, Operator);
   }
 
+  ExprResult
+  RebuildCXXRewrittenExpr(CXXRewrittenExpr::RewrittenKind Kind, Expr *Original,
+                          Expr *Rewritten,
+                          CXXRewrittenExpr::ExtraRewrittenBits ExtraBits) {
+    return new (SemaRef.Context)
+        CXXRewrittenExpr(Kind, Original, Rewritten, ExtraBits);
+  }
+
   /// \brief Build a new atomic operation expression.
   ///
   /// By default, performs semantic analysis to build the new expression.
   /// Subclasses may override this routine to provide different behavior.
   ExprResult RebuildAtomicExpr(SourceLocation BuiltinLoc,
                                MultiExprArg SubExprs,
                                QualType RetTy,
                                AtomicExpr::AtomicOp Op,

 
 template<typename Derived>
 ExprResult
 TreeTransform<Derived>::TransformMaterializeTemporaryExpr(
                                                   MaterializeTemporaryExpr *E) {
   return getDerived().TransformExpr(E->GetTemporaryExpr());
 }
 
+static Expr *extractOperand(Expr *E, unsigned Idx) {
+  assert(Idx < 2);
+  if (auto *BO = dyn_cast<BinaryOperator>(E)) {
+    if (Idx == 0)
+      return BO->getLHS();
+    return BO->getRHS();
+  }
+  if (auto *CE = dyn_cast<CallExpr>(E)) {
+    assert(CE->getNumArgs() == 2);
+    return CE->getArg(Idx);
+  }
+  llvm_unreachable("unhandled case");
+}
+static std::pair<Expr *, Expr *>
+extractOriginalOperandsFromRewrittenComparison(Expr *E, bool IsThreeWay,
+                                               bool IsSynthesized) {
+  if (IsThreeWay)
+    return {extractOperand(E, IsSynthesized ? 1 : 0),
+            extractOperand(E, IsSynthesized ? 0 : 1)};
+  return extractOriginalOperandsFromRewrittenComparison(
+      extractOperand(E, IsSynthesized ? 1 : 0), true, IsSynthesized);
+}
+
+template <typename Derived>
+ExprResult
+TreeTransform<Derived>::TransformCXXRewrittenExpr(CXXRewrittenExpr *E) {
+
+  // FIXME(EricWF): Is there a case where the underlying expression has been
+  // transformed in such a way that we need to re-compute the rewritten
+  // expression? (and not just re-build it).
+  ExprResult RewrittenRes = getDerived().TransformExpr(E->getRewrittenExpr());
+  if (RewrittenRes.isInvalid())
+    return ExprError();
+  Expr *Rewritten = RewrittenRes.get();
+
+  if (Rewritten == E->getRewrittenExpr() && !getDerived().AlwaysRebuild())
+    return E;
+
+  Expr *Original;
+  switch (E->getRewrittenKind()) {
+  case CXXRewrittenExpr::Comparison: {
+    BinaryOperator *Op = cast<BinaryOperator>(E->getOriginalExpr());
+
+    // Extract the already transformed operands from the rewritten expression.
+    std::pair<Expr *, Expr *> OrigArgs =
+        extractOriginalOperandsFromRewrittenComparison(
+            Rewritten, Op->getOpcode() == BO_Cmp,
+            E->getRewrittenInfo()->CompareBits.IsSynthesized);
+
+    // Build a dummy node representing the expression as written.
+    Original = new (SemaRef.Context) BinaryOperator(
+        OpaqueValueExpr::Create(SemaRef.Context, OrigArgs.first),
+        OpaqueValueExpr::Create(SemaRef.Context, OrigArgs.second),
+        Op->getOpcode(), Rewritten->getType(), Rewritten->getValueKind(),
+        Rewritten->getObjectKind(), Op->getOperatorLoc(), Op->getFPFeatures());
+    break;
+  }
+  }
+  return getDerived().RebuildCXXRewrittenExpr(
+      E->getRewrittenKind(), Original, Rewritten, *E->getRewrittenInfo());
+}
+
 template<typename Derived>
 ExprResult
 TreeTransform<Derived>::TransformCXXFoldExpr(CXXFoldExpr *E) {
   Expr *Pattern = E->getPattern();
 
   SmallVector<UnexpandedParameterPack, 2> Unexpanded;
   getSema().collectUnexpandedParameterPacks(Pattern, Unexpanded);
   assert(!Unexpanded.empty() && "Pack expansion without parameter packs?");

lib/Serialization/ASTReaderStmt.cpp

   E->LParenLoc = ReadSourceLocation();
   E->EllipsisLoc = ReadSourceLocation();
   E->RParenLoc = ReadSourceLocation();
   E->SubExprs[0] = Record.readSubExpr();
   E->SubExprs[1] = Record.readSubExpr();
   E->Opcode = (BinaryOperatorKind)Record.readInt();
 }
 
+void ASTStmtReader::VisitCXXRewrittenExpr(CXXRewrittenExpr *E) {
+  VisitExpr(E);
+  E->setRewrittenKind(
+      static_cast<CXXRewrittenExpr::RewrittenKind>(Record.readInt()));
+  E->SubExprs[0] = Record.readSubExpr();
+  E->SubExprs[1] = Record.readSubExpr();
+  switch (E->getRewrittenKind()) {
+  case CXXRewrittenExpr::Comparison: {
+    CXXRewrittenExpr::ComparisonBits &Bits = E->ExtraBits.CompareBits;
+    Bits.IsSynthesized = Record.readInt();
+    break;
+  }
+  }
+}
+
 void ASTStmtReader::VisitOpaqueValueExpr(OpaqueValueExpr *E) {
   VisitExpr(E);
   E->SourceExpr = Record.readSubExpr();
   E->Loc = ReadSourceLocation();
   E->setIsUnique(Record.readInt());
 }
 
 void ASTStmtReader::VisitTypoExpr(TypoExpr *E) {

     case EXPR_MATERIALIZE_TEMPORARY:
       S = new (Context) MaterializeTemporaryExpr(Empty);
       break;
 
     case EXPR_CXX_FOLD:
       S = new (Context) CXXFoldExpr(Empty);
       break;
 
+    case EXPR_CXX_REWRITTEN_OPERATOR:
+      S = new (Context) CXXRewrittenExpr(Empty);
+
     case EXPR_OPAQUE_VALUE:
       S = new (Context) OpaqueValueExpr(Empty);
       break;
 
     case EXPR_CUDA_KERNEL_CALL:
       S = new (Context) CUDAKernelCallExpr(Context, Empty);
       break;
 

lib/Serialization/ASTWriterStmt.cpp

   Record.AddSourceLocation(E->EllipsisLoc);
   Record.AddSourceLocation(E->RParenLoc);
   Record.AddStmt(E->SubExprs[0]);
   Record.AddStmt(E->SubExprs[1]);
   Record.push_back(E->Opcode);
   Code = serialization::EXPR_CXX_FOLD;
 }
 
+void ASTStmtWriter::VisitCXXRewrittenExpr(CXXRewrittenExpr *E) {
+  VisitExpr(E);
+  Record.push_back(E->getRewrittenKind());
+  Record.AddStmt(E->SubExprs[0]);
+  Record.AddStmt(E->SubExprs[1]);
+  switch (E->getRewrittenKind()) {
+  case CXXRewrittenExpr::Comparison: {
+    CXXRewrittenExpr::ComparisonBits Bits = E->ExtraBits.CompareBits;
+    Record.push_back(Bits.IsSynthesized);
+    break;
+  }
+  }
+  Code = serialization::EXPR_CXX_REWRITTEN_OPERATOR;
+}
+
 void ASTStmtWriter::VisitOpaqueValueExpr(OpaqueValueExpr *E) {
   VisitExpr(E);
   Record.AddStmt(E->getSourceExpr());
   Record.AddSourceLocation(E->getLocation());
   Record.push_back(E->isUnique());
   Code = serialization::EXPR_OPAQUE_VALUE;
 }
 

lib/StaticAnalyzer/Core/ExprEngine.cpp

     case Stmt::ExpressionTraitExprClass:
     case Stmt::UnresolvedLookupExprClass:
     case Stmt::UnresolvedMemberExprClass:
     case Stmt::TypoExprClass:
     case Stmt::CXXNoexceptExprClass:
     case Stmt::PackExpansionExprClass:
     case Stmt::SubstNonTypeTemplateParmPackExprClass:
     case Stmt::FunctionParmPackExprClass:
+    case Stmt::CXXRewrittenExprClass:
     case Stmt::CoroutineBodyStmtClass:
     case Stmt::CoawaitExprClass:
     case Stmt::DependentCoawaitExprClass:
     case Stmt::CoreturnStmtClass:
     case Stmt::CoyieldExprClass:
     case Stmt::SEHTryStmtClass:
     case Stmt::SEHExceptStmtClass:
     case Stmt::SEHLeaveStmtClass:

                           const Expr *NodeEx,
                           const Expr *BoundEx,
                           ExplodedNode *Pred,
                           ProgramStateRef state,
                           SVal location,
                           const ProgramPointTag *tag,
                           QualType LoadTy) {
   assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
-
-  // Are we loading from a region?  This actually results in two loads; one
-  // to fetch the address of the referenced value and one to fetch the
-  // referenced value.
-  if (const auto *TR =
-        dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) {
-
-    QualType ValTy = TR->getValueType();
-    if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
-      static SimpleProgramPointTag
-             loadReferenceTag(TagProviderName, "Load Reference");
-      ExplodedNodeSet Tmp;
-      evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state,
-                     location, &loadReferenceTag,
-                     getContext().getPointerType(RT->getPointeeType()));
-
-      // Perform the load from the referenced value.
-      for (const auto I : Tmp) {
-        state = I->getState();
-        location = state->getSVal(BoundEx, I->getLocationContext());
-        evalLoadCommon(Dst, NodeEx, BoundEx, I, state, location, tag, LoadTy);
-      }
-      return;
-    }
-  }
-
-  evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy);
-}
-
-void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst,
-                                const Expr *NodeEx,
-                                const Expr *BoundEx,
-                                ExplodedNode *Pred,
-                                ProgramStateRef state,
-                                SVal location,
-                                const ProgramPointTag *tag,
-                                QualType LoadTy) {
   assert(NodeEx);
   assert(BoundEx);
   // Evaluate the location (checks for bad dereferences).
   ExplodedNodeSet Tmp;
   evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true);
   if (Tmp.empty())
     return;
 

test/CodeGenCXX/cxx2a-compare.cpp

auto test_int(_Complex int x, _Complex int y) {
   // CHECK: %and.eq = and i1 %cmp.eq.r, %cmp.eq.i
   // CHECK: %sel.eq = select i1 %and.eq, i8 [[EQ]], i8 [[NE]]
   // CHECK: %__value_ = getelementptr inbounds %[[SE]], %[[SE]]* %retval
   // CHECK: store i8 %sel.eq, i8* %__value_, align 1
   return x <=> y;
 }
 
 } // namespace ComplexTest
+
+namespace RewrittenTest {
+struct U {
+  int x;
+  std::strong_ordering operator<=>(U const &) const;
+};
+// FIXME(EricWF): Write this test
+auto test(U t1, U t2) {
+  return (t1 < t2);
+}
+
+} // namespace RewrittenTest
+
+

test/SemaCXX/compare-cxx2a.cpp

void test_enum_enum_compare_no_builtin() {
   ASSERT_EXPR_TYPE(r1, std::strong_ordering);
   (void)(EnumA::A <=> EnumA::A); // expected-warning {{self-comparison always evaluates to 'std::strong_ordering::equal'}}
   (void)(EnumA::A <=> EnumB::B); // expected-error {{invalid operands to binary expression ('EnumCompareTests::EnumA' and 'EnumCompareTests::EnumB')}}
   (void)(EnumB::B <=> EnumA::A); // expected-error {{invalid operands}}
 }
 
 template <int>
 struct Tag {};
-// expected-note@+1 {{candidate}}
-Tag<0> operator<=>(EnumA, EnumA) {
-  return {};
+std::strong_ordering operator<=>(EnumA, EnumA) {
+  return std::strong_ordering::equal;
 }
-Tag<1> operator<=>(EnumA, EnumB) {
-  return {};
+// expected-note@+1 {{candidate function}},
+std::strong_ordering operator<=>(EnumA a, EnumB b) {
+  return ((int)a <=> (int)b);
 }
 
 void test_enum_ovl_provided() {
   auto r1 = (EnumA::A <=> EnumA::A);
-  ASSERT_EXPR_TYPE(r1, Tag<0>);
+  ASSERT_EXPR_TYPE(r1, std::strong_ordering);
   auto r2 = (EnumA::A <=> EnumB::B);
-  ASSERT_EXPR_TYPE(r2, Tag<1>);
-  (void)(EnumB::B <=> EnumA::A); // expected-error {{invalid operands to binary expression ('EnumCompareTests::EnumB' and 'EnumCompareTests::EnumA')}}
+  ASSERT_EXPR_TYPE(r2, std::strong_ordering);
+  (void)(EnumB::B <=> EnumA::A); // OK, chooses reverse order synthesized candidate.
+  (void)(EnumB::B <=> EnumC::C); // expected-error {{invalid operands to binary expression ('EnumCompareTests::EnumB' and 'EnumCompareTests::EnumC')}}
 }
 
 void enum_float_test() {
   enum EnumA { A };
   (void)(A <=> (float)0);       // expected-error {{invalid operands to binary expression ('EnumA' and 'float')}}
   (void)((double)0 <=> A);      // expected-error {{invalid operands to binary expression ('double' and 'EnumA')}}
   (void)((long double)0 <=> A); // expected-error {{invalid operands to binary expression ('long double' and 'EnumA')}}
 }

 }
 
 void test_double(_Complex double x, _Complex double y) {
   auto r = x <=> y;
   ASSERT_EXPR_TYPE(r, std::weak_equality);
 }
 
 } // namespace ComplexTest
+
+namespace TestRewritting {
+
+struct T {
+  int x;
+  // expected-note@+1 {{candidate}}
+  constexpr std::strong_ordering operator<=>(T y) const {
+    return (x <=> y.x);
+  }
+};
+
+struct U {
+  int x;
+  // FIXME: This diagnostic is wrong-ish.
+  // expected-note@+1 {{candidate function not viable: requires single argument 'y', but 2 arguments were provided}}
+  constexpr std::strong_equality operator<=>(T y) const {
+    if (x == y.x)
+      return std::strong_equality::equal;
+    return std::strong_equality::nonequal;
+  }
+};
+
+struct X { int x; };
+struct Y { int x; };
+template <int>
+struct Tag {};
+// expected-note@+1 2 {{candidate}}
+Tag<0> operator<=>(X, Y) {
+  return {};
+}
+// expected-note@+1 2 {{candidate}}
+constexpr auto operator<=>(Y y, X x) {
+  return y.x <=> x.x;
+}
+
+void foo() {
+  T t{42};
+  T t2{0};
+  U u{101};
+  auto r1 = (t <=> u);
+  ASSERT_EXPR_TYPE(r1, std::strong_equality);
+  auto r2 = (t <=> t2);
+  ASSERT_EXPR_TYPE(r2, std::strong_ordering);
+
+  auto r3 = t == u;
+  ASSERT_EXPR_TYPE(r3, bool);
+
+  (void)(t < u); // expected-error {{invalid operands to binary expression ('TestRewritting::T' and 'TestRewritting::U')}}
+
+  constexpr X x{1};
+  constexpr Y y{2};
+  constexpr auto r4 = (y < x);
+  static_assert(r4 == false);
+  constexpr auto r5 = (x < y);
+  static_assert(r5 == true);
+}
+
+} // namespace TestRewritting
+
+// The implicit object parameter is not considered when performing partial
+// ordering. That makes the reverse synthesized candidates ambiguous with the
+// rewritten candidates if any of them resolve to a member function.
+namespace TestOvlMatchingIgnoresImplicitObject {
+struct U;
+// expected-note@+2 {{candidate}}
+struct T {
+  std::strong_ordering operator<=>(U const &RHS) const;
+};
+// expected-note@+2 {{candidate}}
+struct U {
+  std::strong_ordering operator<=>(T const &RHS) const;
+};
+
+struct V {
+  int x;
+};
+auto operator<=>(V const &LHS, V &&RHS) { // expected-note 4 {{candidate}}
+  return LHS.x <=> RHS.x;
+}
+auto operator<(V const &, V &&) { // expected-note {{candidate}}
+  return std::strong_equality::equal;
+}
+
+void test() {
+  // expected-error@+1 {{use of overloaded operator '<' is ambiguous}}
+  (void)(T{} < U{});
+  // expected-error@+1 {{use of overloaded operator '<' is ambiguous}}
+  (void)(V{} < V{});
+  // expected-error@+1 {{use of overloaded operator '<=>' is ambiguous}}
+  (void)(V{} <=> V{});
+}
+
+} // namespace TestOvlMatchingIgnoresImplicitObject
+
+namespace TestRewrittenTemplate {
+
+template <class T>
+auto test(T const &LHS, T const &RHS) {
+  // expected-error@+1 {{invalid operands to binary expression ('const TestRewrittenTemplate::None'}}
+  return LHS < RHS;
+}
+struct None {};
+template auto test<None>(None const &, None const &); // expected-note {{requested here}}
+
+struct Relational {};
+bool operator<(Relational, Relational);
+template auto test<Relational>(Relational const &, Relational const &);
+
+struct ThreeWay {};
+std::strong_ordering operator<=>(ThreeWay, ThreeWay);
+template auto test<ThreeWay>(ThreeWay const &, ThreeWay const &);
+
+} // namespace TestRewrittenTemplate