Index: clang/lib/Sema/SemaDecl.cpp
===================================================================
--- clang/lib/Sema/SemaDecl.cpp
+++ clang/lib/Sema/SemaDecl.cpp
@@ -12883,6 +12883,7 @@
     }
 
     if (!IsInstantiation && FD && FD->isConstexpr() && !FD->isInvalidDecl() &&
+        !isLambdaCallOperator(FD) &&
         (!CheckConstexprFunctionDecl(FD) ||
          !CheckConstexprFunctionBody(FD, Body)))
       FD->setInvalidDecl();
Index: clang/lib/Sema/SemaLambda.cpp
===================================================================
--- clang/lib/Sema/SemaLambda.cpp
+++ clang/lib/Sema/SemaLambda.cpp
@@ -1604,17 +1604,27 @@
                                           ExplicitParams, ExplicitResultType,
                                           CaptureInits, EndLoc,
                                           ContainsUnexpandedParameterPack);
-  // If the lambda expression's call operator is not explicitly marked constexpr
-  // and we are not in a dependent context, analyze the call operator to infer
-  // its constexpr-ness, suppressing diagnostics while doing so.
-  if (getLangOpts().CPlusPlus17 && !CallOperator->isInvalidDecl() &&
-      !CallOperator->isConstexpr() &&
-      !isa<CoroutineBodyStmt>(CallOperator->getBody()) &&
-      !Class->getDeclContext()->isDependentContext()) {
-    TentativeAnalysisScope DiagnosticScopeGuard(*this);
-    CallOperator->setConstexpr(
-        CheckConstexprFunctionDecl(CallOperator) &&
-        CheckConstexprFunctionBody(CallOperator, CallOperator->getBody()));
+
+  if (!CallOperator->isInvalidDecl()) {
+    // If the call operator is explicitly marked constexpr, verify that that is
+    // actually the case. This is done here instead of in
+    // ActOnFinishFunctionBody because the constexpr evaluator needs access to
+    // the completed lambda class to check this.
+    if (CallOperator->isConstexpr()) {
+      if (!CheckConstexprFunctionDecl(CallOperator) ||
+          !CheckConstexprFunctionBody(CallOperator, CallOperator->getBody()))
+        CallOperator->setInvalidDecl();
+    }
+    // Otherwise, if we're not in a dependent context, analyze the call operator
+    // to infer its constexpr-ness, suppressing diagnostics while doing so.
+    else if (getLangOpts().CPlusPlus17 &&
+             !isa<CoroutineBodyStmt>(CallOperator->getBody()) &&
+             !Class->getDeclContext()->isDependentContext()) {
+      TentativeAnalysisScope DiagnosticScopeGuard(*this);
+      CallOperator->setConstexpr(
+          CheckConstexprFunctionDecl(CallOperator) &&
+          CheckConstexprFunctionBody(CallOperator, CallOperator->getBody()));
+    }
   }
 
   // Emit delayed shadowing warnings now that the full capture list is known.
Index: clang/test/SemaCXX/cxx1z-constexpr-lambdas.cpp
===================================================================
--- clang/test/SemaCXX/cxx1z-constexpr-lambdas.cpp
+++ clang/test/SemaCXX/cxx1z-constexpr-lambdas.cpp
@@ -270,4 +270,37 @@
 
 } // end ns test_lambda_is_cce
 
+namespace PR36054 {
+constexpr int fn() {
+  int Capture = 42;
+  return [=]() constexpr { return Capture; }();
+}
+
+static_assert(fn() == 42, "");
+
+template <class T>
+constexpr int tfn() {
+  int Capture = 42;
+  return [=]() constexpr { return Capture; }();
+}
+
+static_assert(tfn<int>() == 42, "");
+
+constexpr int gfn() {
+  int Capture = 42;
+  return [=](auto P) constexpr { return Capture + P; }(58);
+}
+
+static_assert(gfn() == 100, "");
+
+constexpr bool OtherCaptures() {
+  int Capture = 42;
+  constexpr auto Outer = [](auto P) constexpr { return 42 + P; };
+  auto Inner = [&](auto O) constexpr { return O(58) + Capture; };
+  return Inner(Outer) == 142;
+}
+
+static_assert(OtherCaptures(), "");
+} // namespace PR36054
+
 #endif // ndef CPP14_AND_EARLIER