Improve behavior in the case of stack exhaustion.

[rsmith]

Summary

Clang performs various recursive operations (such as template instantiation),
and may use non-trivial amounts of stack space in each recursive step (for
instance, due to recursive AST walks). While we try to keep the stack space
used by such steps to a minimum and we have explicit limits on the number of
such steps we perform, it's impractical to guarantee that we won't blow out the
stack on deeply recursive template instantiations on complex ASTs, even with
only a moderately high instantiation depth limit.

The user experience in these cases is generally terrible: we crash with
no hint of what went wrong. Under this patch, we attempt to do better:

• Detect when the stack is nearly exhausted, and produce a warning with a nice template instantiation backtrace, telling the user that we might run slowly or crash.
• For cases where we're forced to trigger recursive template instantiation in arbitrarily-deeply-nested contexts, check whether we're nearly out of stack space and allocate a new stack (by spawning a new thread) after producing the warning.

[rnk]

include/clang/Basic/Stack.h

42

For LLVM_THREADS_DISABLED builds used by Chromium today, maybe we should skip this completely?

lib/Basic/Stack.cpp

24

I think _AddressOfReturnAddress() ifdef _MSC_VER would be the proper way to ask MSVC for a reasonable stack pointer, if we're worried about returning the address of a local.

54–55

So, for example, ASan with UAR, where frames are heap allocated. I suppose in that case we will go down the __builtin_frame_address path, though.

test/SemaTemplate/stack-exhaustion.cpp

11

This test seems like it could be fragile. If threads are disabled, it will probably crash.

[rsmith]

• Review feedback: use _AddressOfReturnAddress with MSVC, and simplify

[rsmith]

lib/Basic/Stack.cpp

54–55

Can we detect that? It seems better to turn this all off if we think there's anything funny going on with the stack layout.

test/SemaTemplate/stack-exhaustion.cpp

11

I've handled the "threads are disabled" case. Is there anything else that can meaningfully be detected here? (ASan maybe? Are there any other cases that lead to a non-linear stack layout that we can detect?)

[rsmith]

• Disable stack exhaustion test if threads are disabled.

[aaron.ballman]

include/clang/Basic/DiagnosticSemaKinds.td

14–17

Should this be a Sema warning as opposed to a Basic warning? It seems to me that we may want to guard against similar stack exhaustion from the parser as well, wouldn't we?

include/clang/Basic/Stack.h

43–47

Elide braces.

lib/Sema/SemaExpr.cpp

15070–15079

This seems unrelated to the patch?

[rsmith]

• Address review comments from Aaron.

include/clang/Basic/DiagnosticSemaKinds.td

14–17

Sure, moved to DiagnosticCommonKinds.td. We have no uses of it outside Sema yet, but it's definitely plausible that some would be added.

lib/Sema/SemaExpr.cpp

15070–15079

I agree it seems that way, but it is related:

The block of code below that got turned into a lambda contains early exits via return for the cases that get downgraded to FormallyOdrUsed here. We used to bail out of the whole function and not mark these trivial special member functions as "used" (in the code after the NeedDefinition && !Func->getBody() condition), which seems somewhat reasonable since we don't actually need definitions of them; other parts of Clang (specifically the static analyzer) have developed a reliance on that behavior.

So this is preserving the existing behavior and (hopefully) making it more obvious what that behavior is, rather than getting that behavior by an early exit from the "need a definition?" portion of this function leaking into the semantics of the "mark used" portion.

I can split this out and make this change first if you like.

test/SemaTemplate/stack-exhaustion.cpp

11

I've read through the ASan UAR design and played with some testcases, and I think this is fine. ASan will allocate the locals for some frames on the heap instead of on the stack, but that's OK, it just might mean that the stack usage grows more slowly. The stack pointer still points to the real stack, __builtin_frame_address(0) still returns a stack pointer (and critically, not a pointer to the ASan-heap-allocated frame), and we can still detect when we're getting close to stack exhaustion -- it just happens more slowly in this mode because we have another pool of places to allocate frames that's tried before we fall back to the stack.

[aaron.ballman]

LGTM aside from an accidental newline change.

include/clang/Basic/DiagnosticSemaKinds.td

15

Spurious removal?

lib/Sema/SemaExpr.cpp

15070–15079

I can split this out and make this change first if you like.

No need, I appreciate the explanation!

[krytarowski]

This change broke on NetBSD.

http://lab.llvm.org:8011/builders/netbsd-amd64/builds/22003/steps/run%20unit%20tests/logs/FAIL%3A%20Clang%3A%3Astack-exhaustion.cpp

 (view as text)

******************** TEST 'Clang :: SemaTemplate/stack-exhaustion.cpp' FAILED ********************
Script:
--
: 'RUN: at line 1';   /home/motus/netbsd8/netbsd8/build/bin/clang -cc1 -internal-isystem /data/motus/netbsd8/netbsd8/build/lib/clang/10.0.0/include -nostdsysteminc -verify /data/motus/netbsd8/netbsd8/llvm/tools/clang/test/SemaTemplate/stack-exhaustion.cpp
--
Exit Code: 139

Command Output (stderr):
--
+ : 'RUN: at line 1'
+ /home/motus/netbsd8/netbsd8/build/bin/clang -cc1 -internal-isystem /data/motus/netbsd8/netbsd8/build/lib/clang/10.0.0/include -nostdsysteminc -verify /data/motus/netbsd8/netbsd8/llvm/tools/clang/test/SemaTemplate/stack-exhaustion.cpp
Stack dump:
0.	Program arguments: /home/motus/netbsd8/netbsd8/build/bin/clang -cc1 -internal-isystem /data/motus/netbsd8/netbsd8/build/lib/clang/10.0.0/include -nostdsysteminc -verify /data/motus/netbsd8/netbsd8/llvm/tools/clang/test/SemaTemplate/stack-exhaustion.cpp 
1.	/data/motus/netbsd8/netbsd8/llvm/tools/clang/test/SemaTemplate/stack-exhaustion.cpp:9:10: current parser token ';'
#0 0x000000000242038c llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/motus/netbsd8/netbsd8/build/bin/clang+0x242038c)
#1 0x000000000241e5ee llvm::sys::RunSignalHandlers() (/home/motus/netbsd8/netbsd8/build/bin/clang+0x241e5ee)
#2 0x000000000241e6ee SignalHandler(int) (/home/motus/netbsd8/netbsd8/build/bin/clang+0x241e6ee)
/data/motus/netbsd8/netbsd8/build/tools/clang/test/SemaTemplate/Output/stack-exhaustion.cpp.script: line 1:  7058 Segmentation fault      (core dumped) /home/motus/netbsd8/netbsd8/build/bin/clang -cc1 -internal-isystem /data/motus/netbsd8/netbsd8/build/lib/clang/10.0.0/include -nostdsysteminc -verify /data/motus/netbsd8/netbsd8/llvm/tools/clang/test/SemaTemplate/stack-exhaustion.cpp

--

********************

Please fix.

[rsmith]

In D66361#1655903, @krytarowski wrote:

This change broke on NetBSD.

http://lab.llvm.org:8011/builders/netbsd-amd64/builds/22003/steps/run%20unit%20tests/logs/FAIL%3A%20Clang%3A%3Astack-exhaustion.cpp

Test disabled for NetBSD in r370801. If you're interested in investigating why this isn't working there, feel free, but this is only a best-effort mitigation for the case where things have already gone wrong, so there are limits to how much effort it makes sense to resolve this.

Does NetBSD set a hard stack rlimit of less than 8MB by any chance?

[krytarowski]

In D66361#1656037, @rsmith wrote:

In D66361#1655903, @krytarowski wrote:

This change broke on NetBSD.

http://lab.llvm.org:8011/builders/netbsd-amd64/builds/22003/steps/run%20unit%20tests/logs/FAIL%3A%20Clang%3A%3Astack-exhaustion.cpp

Test disabled for NetBSD in r370801. If you're interested in investigating why this isn't working there, feel free, but this is only a best-effort mitigation for the case where things have already gone wrong, so there are limits to how much effort it makes sense to resolve this.

Does NetBSD set a hard stack rlimit of less than 8MB by any chance?

The stack rlimit is restricted by default to 4MB. The maximum at least on amd64 is 128MB... but if someone really needs it, it could by bypassed with more stacks.

$ ulimit -a
time(cpu-seconds)    unlimited
file(blocks)         unlimited
coredump(blocks)     unlimited
data(kbytes)         262144
stack(kbytes)        4096
lockedmem(kbytes)    10847213
memory(kbytes)       32541640
nofiles(descriptors) 1024
processes            1024
threads              1024
vmemory(kbytes)      unlimited
sbsize(bytes)        unlimited

Should the limit by raised by default in the system?

include/clang/Basic/DiagnosticSemaKinds.td

 //==--- DiagnosticSemaKinds.td - libsema diagnostics ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 //===----------------------------------------------------------------------===//
 // Semantic Analysis
 //===----------------------------------------------------------------------===//
 
 let Component = "Sema" in {
-let CategoryName = "Semantic Issue" in {
+def warn_stack_exhausted : Warning<
+  "stack nearly exhausted; compilation time may suffer, and "
+  "crashes due to stack overflow are likely">,
+  InGroup<DiagGroup<"stack-exhausted">>, NoSFINAE;
 
+let CategoryName = "Semantic Issue" in {
 def note_previous_decl : Note<"%0 declared here">;
 def note_entity_declared_at : Note<"%0 declared here">;
 def note_callee_decl : Note<"%0 declared here">;
 def note_defined_here : Note<"%0 defined here">;
 
 // For loop analysis
 def warn_variables_not_in_loop_body : Warning<
   "variable%select{s| %1|s %1 and %2|s %1, %2, and %3|s %1, %2, %3, and %4}0 "

include/clang/Basic/Stack.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_BASIC_STACK_H
 #define LLVM_CLANG_BASIC_STACK_H
 
 #include <cstddef>
 
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Compiler.h"
+
 namespace clang {
   /// The amount of stack space that Clang would like to be provided with.
   /// If less than this much is available, we may be unable to reach our
   /// template instantiation depth limit and other similar limits.
   constexpr size_t DesiredStackSize = 8 << 20;
+
+  /// Call this once on each thread, as soon after starting the thread as
+  /// feasible, to note the approximate address of the bottom of the stack.
+  void noteBottomOfStack();
+
+  /// Determine whether the stack is nearly exhausted.
+  bool isStackNearlyExhausted();
+
+  void runWithSufficientStackSpaceSlow(llvm::function_ref<void()> Diag,
+                                       llvm::function_ref<void()> Fn);
+
+  /// Run a given function on a stack with "sufficient" space. If stack space
+  /// is insufficient, calls Diag to emit a diagnostic before calling Fn.
+  inline void runWithSufficientStackSpace(llvm::function_ref<void()> Diag,
+                                          llvm::function_ref<void()> Fn) {
+#ifdef LLVM_ENABLE_THREADS
+    if (LLVM_UNLIKELY(isStackNearlyExhausted())) {
+      runWithSufficientStackSpaceSlow(Diag, Fn);
+    } else {
+      Fn();
+    }
+#else
+    if (LLVM_UNLIKELY(isStackNearlyExhausted()))
+      Diag();
+    Fn();
+#endif
+  }
 } // end namespace clang
 
 #endif // LLVM_CLANG_BASIC_STACK_H

include/clang/Sema/Sema.h

public:
 
   private:
     Sema& S;
     FPOptions OldFPFeaturesState;
   };
 
   void addImplicitTypedef(StringRef Name, QualType T);
 
+  bool WarnedStackExhausted = false;
+
 public:
   Sema(Preprocessor &pp, ASTContext &ctxt, ASTConsumer &consumer,
        TranslationUnitKind TUKind = TU_Complete,
        CodeCompleteConsumer *CompletionConsumer = nullptr);
   ~Sema();
 
   /// Perform initialization that occurs after the parser has been
   /// initialized but before it parses anything.
public:
   /// creates a multiplex external source and appends to it.
   ///
   ///\param[in] E - A non-null external sema source.
   ///
   void addExternalSource(ExternalSemaSource *E);
 
   void PrintStats() const;
 
+  /// Warn that the stack is nearly exhausted.
+  void warnStackExhausted(SourceLocation Loc);
+
+  /// Run some code with "sufficient" stack space. (Currently, at least 256K is
+  /// guaranteed). Produces a warning if we're low on stack space and allocates
+  /// more in that case. Use this in code that may recurse deeply (for example,
+  /// in template instantiation) to avoid stack overflow.
+  void runWithSufficientStackSpace(SourceLocation Loc,
+                                   llvm::function_ref<void()> Fn);
+
   /// Helper class that creates diagnostics with optional
   /// template instantiation stacks.
   ///
   /// This class provides a wrapper around the basic DiagnosticBuilder
   /// class that emits diagnostics. SemaDiagnosticBuilder is
   /// responsible for emitting the diagnostic (as DiagnosticBuilder
   /// does) and, if the diagnostic comes from inside a template
   /// instantiation, printing the template instantiation stack as

lib/Basic/CMakeLists.txt

add_clang_library(clangBasic
   ObjCRuntime.cpp
   OpenMPKinds.cpp
   OperatorPrecedence.cpp
   SanitizerBlacklist.cpp
   SanitizerSpecialCaseList.cpp
   Sanitizers.cpp
   SourceLocation.cpp
   SourceManager.cpp
+  Stack.cpp
   TargetInfo.cpp
   Targets.cpp
   Targets/AArch64.cpp
   Targets/AMDGPU.cpp
   Targets/ARC.cpp
   Targets/ARM.cpp
   Targets/AVR.cpp
   Targets/BPF.cpp

lib/Basic/Stack.cpp

+//===--- Stack.h - Utilities for dealing with stack space -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Defines utilities for dealing with stack allocation and stack space.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/Basic/Stack.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/Support/CrashRecoveryContext.h"
+
+static LLVM_THREAD_LOCAL void *BottomOfStack = nullptr;
+
+static void *getStackPointer() {
+#if __GNUC__ || __has_builtin(__builtin_frame_address)
+  return __builtin_frame_address(0);
+#elif defined(_MSC_VER)
+  return _AddressOfReturnAddress();
+#else
+  char CharOnStack = 0;
+  // The volatile store here is intended to escape the local variable, to
+  // prevent the compiler from optimizing CharOnStack into anything other
+  // than a char on the stack.
+  //
+  // Tested on: MSVC 2015 - 2019, GCC 4.9 - 9, Clang 3.2 - 9, ICC 13 - 19.
+  char *volatile Ptr = &CharOnStack;
+  return Ptr;
+#endif
+}
+
+void clang::noteBottomOfStack() {
+  if (!BottomOfStack)
+    BottomOfStack = getStackPointer();
+}
+
+bool clang::isStackNearlyExhausted() {
+  // We consider 256 KiB to be sufficient for any code that runs between checks
+  // for stack size.
+  constexpr size_t SufficientStack = 256 << 10;
+
+  // If we don't know where the bottom of the stack is, hope for the best.
+  if (!BottomOfStack)
+    return false;
+
+  intptr_t StackDiff = (intptr_t)getStackPointer() - (intptr_t)BottomOfStack;
+  size_t StackUsage = (size_t)std::abs(StackDiff);
+
+  // If the stack pointer has a surprising value, we do not understand this
+  // stack usage scheme. (Perhaps the target allocates new stack regions on
+  // demand for us.) Don't try to guess what's going on.
+  if (StackUsage > DesiredStackSize)
+    return false;
+
+  return StackUsage >= DesiredStackSize - SufficientStack;
+}
+
+void clang::runWithSufficientStackSpaceSlow(llvm::function_ref<void()> Diag,
+                                            llvm::function_ref<void()> Fn) {
+  llvm::CrashRecoveryContext CRC;
+  CRC.RunSafelyOnThread([&] {
+    noteBottomOfStack();
+    Diag();
+    Fn();
+  }, DesiredStackSize);
+}

lib/Frontend/CompilerInstance.cpp

 
 // High-Level Operations
 
 bool CompilerInstance::ExecuteAction(FrontendAction &Act) {
   assert(hasDiagnostics() && "Diagnostics engine is not initialized!");
   assert(!getFrontendOpts().ShowHelp && "Client must handle '-help'!");
   assert(!getFrontendOpts().ShowVersion && "Client must handle '-version'!");
 
+  // Mark this point as the bottom of the stack if we don't have somewhere
+  // better. We generally expect frontend actions to be invoked with (nearly)
+  // DesiredStackSpace available.
+  noteBottomOfStack();
+
   // FIXME: Take this as an argument, once all the APIs we used have moved to
   // taking it as an input instead of hard-coding llvm::errs.
   raw_ostream &OS = llvm::errs();
 
   if (!Act.PrepareToExecute(*this))
     return false;
 
   // Create the target instance.

lib/Sema/Sema.cpp

 #include "clang/AST/DeclFriend.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/PrettyDeclStackTrace.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/PartialDiagnostic.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Sema/CXXFieldCollector.h"
 #include "clang/Sema/DelayedDiagnostic.h"
 #include "clang/Sema/ExternalSemaSource.h"
 #include "clang/Sema/Initialization.h"
 #include "clang/Sema/MultiplexExternalSemaSource.h"
Sema::~Sema() {
 
   // Detach from the PP callback handler which outlives Sema since it's owned
   // by the preprocessor.
   SemaPPCallbackHandler->reset();
 
   assert(DelayedTypos.empty() && "Uncorrected typos!");
 }
 
+void Sema::warnStackExhausted(SourceLocation Loc) {
+  // Only warn about this once.
+  if (!WarnedStackExhausted) {
+    Diag(Loc, diag::warn_stack_exhausted);
+    WarnedStackExhausted = true;
+  }
+}
+
+void Sema::runWithSufficientStackSpace(SourceLocation Loc,
+                                       llvm::function_ref<void()> Fn) {
+  clang::runWithSufficientStackSpace([&] { warnStackExhausted(Loc); }, Fn);
+}
+
 /// makeUnavailableInSystemHeader - There is an error in the current
 /// context.  If we're still in a system header, and we can plausibly
 /// make the relevant declaration unavailable instead of erroring, do
 /// so and return true.
 bool Sema::makeUnavailableInSystemHeader(SourceLocation loc,
                                       UnavailableAttr::ImplicitReason reason) {
   // If we're not in a function, it's an error.
   FunctionDecl *fn = dyn_cast<FunctionDecl>(CurContext);

lib/Sema/SemaExpr.cpp

if (Param->hasUninstantiatedDefaultArg()) {
     ExprResult Result;
     {
       // C++ [dcl.fct.default]p5:
       //   The names in the [default argument] expression are bound, and
       //   the semantic constraints are checked, at the point where the
       //   default argument expression appears.
       ContextRAII SavedContext(*this, FD);
       LocalInstantiationScope Local(*this);
+      runWithSufficientStackSpace(CallLoc, [&] {
         Result = SubstInitializer(UninstExpr, MutiLevelArgList,
                                   /*DirectInit*/false);
+      });
     }
     if (Result.isInvalid())
       return true;
 
     // Check the expression as an initializer for the parameter.
     InitializedEntity Entity
       = InitializedEntity::InitializeParameter(Context, Param);
     InitializationKind Kind = InitializationKind::CreateCopy(
void Sema::MarkFunctionReferenced(SourceLocation Loc, FunctionDecl *Func,
   //
   // We (incorrectly) mark overload resolution as an unevaluated context, so we
   // can just check that here.
   OdrUseContext OdrUse =
       MightBeOdrUse ? isOdrUseContext(*this) : OdrUseContext::None;
   if (IsRecursiveCall && OdrUse == OdrUseContext::Used)
     OdrUse = OdrUseContext::FormallyOdrUsed;
 
+  // Trivial default constructors and destructors are never actually used.
+  // FIXME: What about other special members?
+  if (Func->isTrivial() && !Func->hasAttr<DLLExportAttr>() &&
+      OdrUse == OdrUseContext::Used) {
+    if (auto *Constructor = dyn_cast<CXXConstructorDecl>(Func))
+      if (Constructor->isDefaultConstructor())
+        OdrUse = OdrUseContext::FormallyOdrUsed;
+    if (isa<CXXDestructorDecl>(Func))
+      OdrUse = OdrUseContext::FormallyOdrUsed;
+  }
+
   // C++20 [expr.const]p12:
   //   A function [...] is needed for constant evaluation if it is [...] a
   //   constexpr function that is named by an expression that is potentially
   //   constant evaluated
   bool NeededForConstantEvaluation =
       isPotentiallyConstantEvaluatedContext(*this) &&
       isImplicitlyDefinableConstexprFunction(Func);
 
void Sema::MarkFunctionReferenced(SourceLocation Loc, FunctionDecl *Func,
   if (FPT && isUnresolvedExceptionSpec(FPT->getExceptionSpecType()))
     ResolveExceptionSpec(Loc, FPT);
 
   if (getLangOpts().CUDA)
     CheckCUDACall(Loc, Func);
 
   // If we need a definition, try to create one.
   if (NeedDefinition && !Func->getBody()) {
-    if (CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(Func)) {
+    runWithSufficientStackSpace(Loc, [&] {
+      if (CXXConstructorDecl *Constructor =
+              dyn_cast<CXXConstructorDecl>(Func)) {
         Constructor = cast<CXXConstructorDecl>(Constructor->getFirstDecl());
         if (Constructor->isDefaulted() && !Constructor->isDeleted()) {
           if (Constructor->isDefaultConstructor()) {
             if (Constructor->isTrivial() &&
                 !Constructor->hasAttr<DLLExportAttr>())
               return;
             DefineImplicitDefaultConstructor(Loc, Constructor);
           } else if (Constructor->isCopyConstructor()) {
             DefineImplicitCopyConstructor(Loc, Constructor);
           } else if (Constructor->isMoveConstructor()) {
             DefineImplicitMoveConstructor(Loc, Constructor);
           }
         } else if (Constructor->getInheritedConstructor()) {
           DefineInheritingConstructor(Loc, Constructor);
         }
       } else if (CXXDestructorDecl *Destructor =
                      dyn_cast<CXXDestructorDecl>(Func)) {
         Destructor = cast<CXXDestructorDecl>(Destructor->getFirstDecl());
         if (Destructor->isDefaulted() && !Destructor->isDeleted()) {
           if (Destructor->isTrivial() && !Destructor->hasAttr<DLLExportAttr>())
             return;
           DefineImplicitDestructor(Loc, Destructor);
         }
         if (Destructor->isVirtual() && getLangOpts().AppleKext)
           MarkVTableUsed(Loc, Destructor->getParent());
       } else if (CXXMethodDecl *MethodDecl = dyn_cast<CXXMethodDecl>(Func)) {
         if (MethodDecl->isOverloadedOperator() &&
             MethodDecl->getOverloadedOperator() == OO_Equal) {
           MethodDecl = cast<CXXMethodDecl>(MethodDecl->getFirstDecl());
           if (MethodDecl->isDefaulted() && !MethodDecl->isDeleted()) {
             if (MethodDecl->isCopyAssignmentOperator())
               DefineImplicitCopyAssignment(Loc, MethodDecl);
             else if (MethodDecl->isMoveAssignmentOperator())
               DefineImplicitMoveAssignment(Loc, MethodDecl);
           }
         } else if (isa<CXXConversionDecl>(MethodDecl) &&
                    MethodDecl->getParent()->isLambda()) {
           CXXConversionDecl *Conversion =
               cast<CXXConversionDecl>(MethodDecl->getFirstDecl());
           if (Conversion->isLambdaToBlockPointerConversion())
             DefineImplicitLambdaToBlockPointerConversion(Loc, Conversion);
           else
             DefineImplicitLambdaToFunctionPointerConversion(Loc, Conversion);
         } else if (MethodDecl->isVirtual() && getLangOpts().AppleKext)
           MarkVTableUsed(Loc, MethodDecl->getParent());
       }
 
       // Implicit instantiation of function templates and member functions of
       // class templates.
       if (Func->isImplicitlyInstantiable()) {
         TemplateSpecializationKind TSK =
             Func->getTemplateSpecializationKindForInstantiation();
         SourceLocation PointOfInstantiation = Func->getPointOfInstantiation();
         bool FirstInstantiation = PointOfInstantiation.isInvalid();
         if (FirstInstantiation) {
           PointOfInstantiation = Loc;
           Func->setTemplateSpecializationKind(TSK, PointOfInstantiation);
         } else if (TSK != TSK_ImplicitInstantiation) {
           // Use the point of use as the point of instantiation, instead of the
           // point of explicit instantiation (which we track as the actual point
           // of instantiation). This gives better backtraces in diagnostics.
           PointOfInstantiation = Loc;
         }
 
         if (FirstInstantiation || TSK != TSK_ImplicitInstantiation ||
             Func->isConstexpr()) {
           if (isa<CXXRecordDecl>(Func->getDeclContext()) &&
               cast<CXXRecordDecl>(Func->getDeclContext())->isLocalClass() &&
               CodeSynthesisContexts.size())
             PendingLocalImplicitInstantiations.push_back(
                 std::make_pair(Func, PointOfInstantiation));
           else if (Func->isConstexpr())
             // Do not defer instantiations of constexpr functions, to avoid the
             // expression evaluator needing to call back into Sema if it sees a
             // call to such a function.
             InstantiateFunctionDefinition(PointOfInstantiation, Func);
           else {
             Func->setInstantiationIsPending(true);
             PendingInstantiations.push_back(
                 std::make_pair(Func, PointOfInstantiation));
             // Notify the consumer that a function was implicitly instantiated.
             Consumer.HandleCXXImplicitFunctionInstantiation(Func);
           }
         }
       } else {
         // Walk redefinitions, as some of them may be instantiable.
         for (auto i : Func->redecls()) {
           if (!i->isUsed(false) && i->isImplicitlyInstantiable())
             MarkFunctionReferenced(Loc, i, MightBeOdrUse);
         }
       }
+    });
   }
 
   // If this is the first "real" use, act on that.
   if (OdrUse == OdrUseContext::Used && !Func->isUsed(/*CheckUsedAttr=*/false)) {
     // Keep track of used but undefined functions.
     if (!Func->isDefined()) {
       if (mightHaveNonExternalLinkage(Func))
         UndefinedButUsed.insert(std::make_pair(Func->getCanonicalDecl(), Loc));
if (TryInstantiating) {
                         VarSpec->getTemplateArgsInfo(), InstantiationDependent)
                   : true;
 
       // Do not instantiate specializations that are still type-dependent.
       if (IsNonDependent) {
         if (UsableInConstantExpr) {
           // Do not defer instantiations of variables that could be used in a
           // constant expression.
+          SemaRef.runWithSufficientStackSpace(PointOfInstantiation, [&] {
             SemaRef.InstantiateVariableDefinition(PointOfInstantiation, Var);
+          });
         } else if (FirstInstantiation ||
                    isa<VarTemplateSpecializationDecl>(Var)) {
           // FIXME: For a specialization of a variable template, we don't
           // distinguish between "declaration and type implicitly instantiated"
           // and "implicit instantiation of definition requested", so we have
           // no direct way to avoid enqueueing the pending instantiation
           // multiple times.
           SemaRef.PendingInstantiations

lib/Sema/SemaInit.cpp

SourceLocation Loc = (Kind.isCopyInit() && Kind.getEqualLoc().isValid())
                          : Kind.getLocation();
 
   if (Kind.getKind() == InitializationKind::IK_Default) {
     // Force even a trivial, implicit default constructor to be
     // semantically checked. We do this explicitly because we don't build
     // the definition for completely trivial constructors.
     assert(Constructor->getParent() && "No parent class for constructor.");
     if (Constructor->isDefaulted() && Constructor->isDefaultConstructor() &&
-        Constructor->isTrivial() && !Constructor->isUsed(false))
+        Constructor->isTrivial() && !Constructor->isUsed(false)) {
+      S.runWithSufficientStackSpace(Loc, [&] {
         S.DefineImplicitDefaultConstructor(Loc, Constructor);
+      });
+    }
   }
 
   ExprResult CurInit((Expr *)nullptr);
 
   // C++ [over.match.copy]p1:
   //   - When initializing a temporary to be bound to the first parameter
   //     of a constructor that takes a reference to possibly cv-qualified
   //     T as its first argument, called with a single argument in the

lib/Sema/SemaLookup.cpp

Sema::SpecialMemberOverloadResult Sema::LookupSpecialMember(CXXRecordDecl *RD,
   if (Result)
     return *Result;
 
   Result = BumpAlloc.Allocate<SpecialMemberOverloadResultEntry>();
   Result = new (Result) SpecialMemberOverloadResultEntry(ID);
   SpecialMemberCache.InsertNode(Result, InsertPoint);
 
   if (SM == CXXDestructor) {
-    if (RD->needsImplicitDestructor())
+    if (RD->needsImplicitDestructor()) {
+      runWithSufficientStackSpace(RD->getLocation(), [&] {
         DeclareImplicitDestructor(RD);
+      });
+    }
     CXXDestructorDecl *DD = RD->getDestructor();
     assert(DD && "record without a destructor");
     Result->setMethod(DD);
     Result->setKind(DD->isDeleted() ?
                     SpecialMemberOverloadResult::NoMemberOrDeleted :
                     SpecialMemberOverloadResult::Success);
     return *Result;
   }
 
   // Prepare for overload resolution. Here we construct a synthetic argument
   // if necessary and make sure that implicit functions are declared.
   CanQualType CanTy = Context.getCanonicalType(Context.getTagDeclType(RD));
   DeclarationName Name;
   Expr *Arg = nullptr;
   unsigned NumArgs;
 
   QualType ArgType = CanTy;
   ExprValueKind VK = VK_LValue;
 
   if (SM == CXXDefaultConstructor) {
     Name = Context.DeclarationNames.getCXXConstructorName(CanTy);
     NumArgs = 0;
-    if (RD->needsImplicitDefaultConstructor())
+    if (RD->needsImplicitDefaultConstructor()) {
+      runWithSufficientStackSpace(RD->getLocation(), [&] {
         DeclareImplicitDefaultConstructor(RD);
+      });
+    }
   } else {
     if (SM == CXXCopyConstructor || SM == CXXMoveConstructor) {
       Name = Context.DeclarationNames.getCXXConstructorName(CanTy);
-      if (RD->needsImplicitCopyConstructor())
+      if (RD->needsImplicitCopyConstructor()) {
+        runWithSufficientStackSpace(RD->getLocation(), [&] {
           DeclareImplicitCopyConstructor(RD);
-      if (getLangOpts().CPlusPlus11 && RD->needsImplicitMoveConstructor())
+        });
+      }
+      if (getLangOpts().CPlusPlus11 && RD->needsImplicitMoveConstructor()) {
+        runWithSufficientStackSpace(RD->getLocation(), [&] {
           DeclareImplicitMoveConstructor(RD);
+        });
+      }
     } else {
       Name = Context.DeclarationNames.getCXXOperatorName(OO_Equal);
-      if (RD->needsImplicitCopyAssignment())
+      if (RD->needsImplicitCopyAssignment()) {
+        runWithSufficientStackSpace(RD->getLocation(), [&] {
           DeclareImplicitCopyAssignment(RD);
-      if (getLangOpts().CPlusPlus11 && RD->needsImplicitMoveAssignment())
+        });
+      }
+      if (getLangOpts().CPlusPlus11 && RD->needsImplicitMoveAssignment()) {
+        runWithSufficientStackSpace(RD->getLocation(), [&] {
           DeclareImplicitMoveAssignment(RD);
+        });
+      }
     }
 
     if (ConstArg)
       ArgType.addConst();
     if (VolatileArg)
       ArgType.addVolatile();
 
     // This isn't /really/ specified by the standard, but it's implied
CXXConstructorDecl *Sema::LookupMovingConstructor(CXXRecordDecl *Class,
 
   return cast_or_null<CXXConstructorDecl>(Result.getMethod());
 }
 
 /// Look up the constructors for the given class.
 DeclContext::lookup_result Sema::LookupConstructors(CXXRecordDecl *Class) {
   // If the implicit constructors have not yet been declared, do so now.
   if (CanDeclareSpecialMemberFunction(Class)) {
+    runWithSufficientStackSpace(Class->getLocation(), [&] {
       if (Class->needsImplicitDefaultConstructor())
         DeclareImplicitDefaultConstructor(Class);
       if (Class->needsImplicitCopyConstructor())
         DeclareImplicitCopyConstructor(Class);
       if (getLangOpts().CPlusPlus11 && Class->needsImplicitMoveConstructor())
         DeclareImplicitMoveConstructor(Class);
+    });
   }
 
   CanQualType T = Context.getCanonicalType(Context.getTypeDeclType(Class));
   DeclarationName Name = Context.DeclarationNames.getCXXConstructorName(T);
   return Class->lookup(Name);
 }
 
 /// Look up the copying assignment operator for the given class.

lib/Sema/SemaTemplate.cpp

 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/TypeVisitor.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/PartialDiagnostic.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Sema/DeclSpec.h"
 #include "clang/Sema/Lookup.h"
 #include "clang/Sema/ParsedTemplate.h"
 #include "clang/Sema/Scope.h"
 #include "clang/Sema/SemaInternal.h"
 #include "clang/Sema/Template.h"
 #include "clang/Sema/TemplateDeduction.h"

lib/Sema/SemaTemplateDeduction.cpp

if (isLambdaConversionOperator(FD)) {
     if (auto *Args = FD->getTemplateSpecializationArgs()) {
       CallOp = InstantiateFunctionDeclaration(
           CallOp->getDescribedFunctionTemplate(), Args, Loc);
       if (!CallOp || CallOp->isInvalidDecl())
         return true;
 
       // We might need to deduce the return type by instantiating the definition
       // of the operator() function.
-      if (CallOp->getReturnType()->isUndeducedType())
+      if (CallOp->getReturnType()->isUndeducedType()) {
+        runWithSufficientStackSpace(Loc, [&] {
           InstantiateFunctionDefinition(Loc, CallOp);
+        });
+      }
     }
 
     if (CallOp->isInvalidDecl())
       return true;
     assert(!CallOp->getReturnType()->isUndeducedType() &&
            "failed to deduce lambda return type");
 
     // Build the new return type from scratch.
     QualType RetType = getLambdaConversionFunctionResultType(
         CallOp->getType()->castAs<FunctionProtoType>());
     if (FD->getReturnType()->getAs<PointerType>())
       RetType = Context.getPointerType(RetType);
     else {
       assert(FD->getReturnType()->getAs<BlockPointerType>());
       RetType = Context.getBlockPointerType(RetType);
     }
     Context.adjustDeducedFunctionResultType(FD, RetType);
     return false;
   }
 
-  if (FD->getTemplateInstantiationPattern())
+  if (FD->getTemplateInstantiationPattern()) {
+    runWithSufficientStackSpace(Loc, [&] {
       InstantiateFunctionDefinition(Loc, FD);
+    });
+  }
 
   bool StillUndeduced = FD->getReturnType()->isUndeducedType();
   if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
     Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
     Diag(FD->getLocation(), diag::note_callee_decl) << FD;
   }
 
   return StillUndeduced;

lib/Sema/SemaTemplateInstantiate.cpp

 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTLambda.h"
 #include "clang/AST/ASTMutationListener.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/PrettyDeclStackTrace.h"
 #include "clang/Basic/LangOptions.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Sema/DeclSpec.h"
 #include "clang/Sema/Initialization.h"
 #include "clang/Sema/Lookup.h"
 #include "clang/Sema/Template.h"
 #include "clang/Sema/TemplateDeduction.h"
 #include "clang/Sema/TemplateInstCallback.h"
 #include "llvm/Support/TimeProfiler.h"
 

 void Sema::pushCodeSynthesisContext(CodeSynthesisContext Ctx) {
   Ctx.SavedInNonInstantiationSFINAEContext = InNonInstantiationSFINAEContext;
   InNonInstantiationSFINAEContext = false;
 
   CodeSynthesisContexts.push_back(Ctx);
 
   if (!Ctx.isInstantiationRecord())
     ++NonInstantiationEntries;
+
+  // Check to see if we're low on stack space. We can't do anything about this
+  // from here, but we can at least warn the user.
+  if (isStackNearlyExhausted())
+    warnStackExhausted(Ctx.PointOfInstantiation);
 }
 
 void Sema::popCodeSynthesisContext() {
   auto &Active = CodeSynthesisContexts.back();
   if (!Active.isInstantiationRecord()) {
     assert(NonInstantiationEntries > 0);
     --NonInstantiationEntries;
   }

lib/Sema/SemaTemplateInstantiateDecl.cpp

 }
 
 Decl *Sema::SubstDecl(Decl *D, DeclContext *Owner,
                       const MultiLevelTemplateArgumentList &TemplateArgs) {
   TemplateDeclInstantiator Instantiator(*this, Owner, TemplateArgs);
   if (D->isInvalidDecl())
     return nullptr;
 
-  return Instantiator.Visit(D);
+  Decl *SubstD;
+  runWithSufficientStackSpace(D->getLocation(), [&] {
+    SubstD = Instantiator.Visit(D);
+  });
+  return SubstD;
 }
 
 /// Instantiates a nested template parameter list in the current
 /// instantiation context.
 ///
 /// \param L The parameter list to instantiate
 ///
 /// \returns NULL if there was an error

lib/Sema/SemaType.cpp

 
 void Sema::completeExprArrayBound(Expr *E) {
   if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E->IgnoreParens())) {
     if (VarDecl *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
       if (isTemplateInstantiation(Var->getTemplateSpecializationKind())) {
         auto *Def = Var->getDefinition();
         if (!Def) {
           SourceLocation PointOfInstantiation = E->getExprLoc();
+          runWithSufficientStackSpace(PointOfInstantiation, [&] {
             InstantiateVariableDefinition(PointOfInstantiation, Var);
+          });
           Def = Var->getDefinition();
 
           // If we don't already have a point of instantiation, and we managed
           // to instantiate a definition, this is the point of instantiation.
           // Otherwise, we don't request an end-of-TU instantiation, so this is
           // not a point of instantiation.
           // FIXME: Is this really the right behavior?
           if (Var->getPointOfInstantiation().isInvalid() && Def) {
if (auto *RD = dyn_cast_or_null<CXXRecordDecl>(Tag)) {
     bool Diagnosed = false;
     if (RD->isDependentContext()) {
       // Don't try to instantiate a dependent class (eg, a member template of
       // an instantiated class template specialization).
       // FIXME: Can this ever happen?
     } else if (auto *ClassTemplateSpec =
             dyn_cast<ClassTemplateSpecializationDecl>(RD)) {
       if (ClassTemplateSpec->getSpecializationKind() == TSK_Undeclared) {
+        runWithSufficientStackSpace(Loc, [&] {
           Diagnosed = InstantiateClassTemplateSpecialization(
               Loc, ClassTemplateSpec, TSK_ImplicitInstantiation,
               /*Complain=*/Diagnoser);
+        });
         Instantiated = true;
       }
     } else {
       CXXRecordDecl *Pattern = RD->getInstantiatedFromMemberClass();
       if (!RD->isBeingDefined() && Pattern) {
         MemberSpecializationInfo *MSI = RD->getMemberSpecializationInfo();
         assert(MSI && "Missing member specialization information?");
         // This record was instantiated from a class within a template.
         if (MSI->getTemplateSpecializationKind() !=
             TSK_ExplicitSpecialization) {
+          runWithSufficientStackSpace(Loc, [&] {
             Diagnosed = InstantiateClass(Loc, RD, Pattern,
                                          getTemplateInstantiationArgs(RD),
                                          TSK_ImplicitInstantiation,
                                          /*Complain=*/Diagnoser);
+          });
           Instantiated = true;
         }
       }
     }
 
     if (Instantiated) {
       // Instantiate* might have already complained that the template is not
       // defined, if we asked it to.

test/SemaTemplate/stack-exhaustion.cpp

+// RUN: %clang_cc1 -verify %s
+// expected-warning@* 0-1{{stack nearly exhausted}}
+// expected-note@* 0+{{}}
+
+template<int N> struct X : X<N-1> {};
+template<> struct X<0> {};
+X<1000> x;
+
+template<typename ...T> struct tuple {};
+template<typename ...T> auto f(tuple<T...> t) -> decltype(f(tuple<T...>(t))) {} // expected-error {{exceeded maximum depth}}
+void g() { f(tuple<int, int>()); }
+
+int f(X<0>);
+template<int N> auto f(X<N>) -> f(X<N-1>());
+
+int k = f(X<1000>());

tools/driver/driver.cpp

 //===-- driver.cpp - Clang GCC-Compatible Driver --------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This is the entry point to the clang driver; it is a thin wrapper
 // for functionality in the Driver clang library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Driver/Driver.h"
 #include "clang/Basic/DiagnosticOptions.h"
+#include "clang/Basic/Stack.h"
 #include "clang/Driver/Compilation.h"
 #include "clang/Driver/DriverDiagnostic.h"
 #include "clang/Driver/Options.h"
 #include "clang/Driver/ToolChain.h"
 #include "clang/Frontend/ChainedDiagnosticConsumer.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/SerializedDiagnosticPrinter.h"
 #include "clang/Frontend/TextDiagnosticPrinter.h"
static int ExecuteCC1Tool(ArrayRef<const char *> argv, StringRef Tool) {
 
   // Reject unknown tools.
   llvm::errs() << "error: unknown integrated tool '" << Tool << "'. "
                << "Valid tools include '-cc1' and '-cc1as'.\n";
   return 1;
 }
 
 int main(int argc_, const char **argv_) {
+  noteBottomOfStack();
   llvm::InitLLVM X(argc_, argv_);
   SmallVector<const char *, 256> argv(argv_, argv_ + argc_);
 
   if (llvm::sys::Process::FixupStandardFileDescriptors())
     return 1;
 
   llvm::InitializeAllTargets();
   auto TargetAndMode = ToolChain::getTargetAndModeFromProgramName(argv[0]);