Index: include/llvm/MC/MCFragment.h
===================================================================
--- include/llvm/MC/MCFragment.h
+++ include/llvm/MC/MCFragment.h
@@ -19,6 +19,7 @@
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/SMLoc.h"
+#include <algorithm>
 #include <cstdint>
 #include <utility>
 
@@ -481,11 +482,19 @@
   /// IsSigned - True if this is a sleb128, false if uleb128.
   bool IsSigned;
 
+  /// RelaxAllowances - Number of times relaxation is allowed to shrink the
+  /// fragment.
+  uint8_t RelaxAllowances;
+
+  /// PadLEBTo - Pad the LEB to this size.
+  uint8_t PadLEBTo;
+
   SmallString<8> Contents;
 
 public:
   MCLEBFragment(const MCExpr &Value_, bool IsSigned_, MCSection *Sec = nullptr)
-      : MCFragment(FT_LEB, false, 0, Sec), Value(&Value_), IsSigned(IsSigned_) {
+      : MCFragment(FT_LEB, false, 0, Sec), Value(&Value_), IsSigned(IsSigned_),
+        RelaxAllowances(4), PadLEBTo(0) {
     Contents.push_back(0);
   }
 
@@ -499,8 +508,21 @@
   SmallString<8> &getContents() { return Contents; }
   const SmallString<8> &getContents() const { return Contents; }
 
+  uint8_t getPadLEBTo() const { return PadLEBTo; }
+
   /// @}
 
+  bool hasRelaxAllowances() const { return RelaxAllowances > 0; }
+
+  void decrementRelaxAllowances() {
+    if (RelaxAllowances > 0)
+      --RelaxAllowances;
+  }
+
+  void increasePadLEBTo(uint8_t Value) {
+    PadLEBTo = std::max(PadLEBTo, Value);
+  }
+
   static bool classof(const MCFragment *F) {
     return F->getKind() == MCFragment::FT_LEB;
   }
Index: lib/MC/MCAssembler.cpp
===================================================================
--- lib/MC/MCAssembler.cpp
+++ lib/MC/MCAssembler.cpp
@@ -869,10 +869,21 @@
   Data.clear();
   raw_svector_ostream OSE(Data);
   if (LF.isSigned())
-    encodeSLEB128(Value, OSE);
+    encodeSLEB128(Value, OSE, LF.getPadLEBTo());
   else
-    encodeULEB128(Value, OSE);
-  return OldSize != LF.getContents().size();
+    encodeULEB128(Value, OSE, LF.getPadLEBTo());
+  uint64_t NewSize = LF.getContents().size();
+
+  // Sometimes the compiler generates EH table assembly that is impossible to
+  // assemble without either adding padding to an LEB fragment or adding extra
+  // padding to a later alignment fragment. Allow an LEB fragment's size to
+  // shrink a few times, then prevent it from further shrinking. See PR35809.
+  if (NewSize < OldSize)
+    LF.decrementRelaxAllowances();
+  if (!LF.hasRelaxAllowances())
+    LF.increasePadLEBTo(NewSize);
+
+  return OldSize != NewSize;
 }
 
 bool MCAssembler::relaxDwarfLineAddr(MCAsmLayout &Layout,
Index: test/MC/ELF/uleb-ehtable.s
===================================================================
--- /dev/null
+++ test/MC/ELF/uleb-ehtable.s
@@ -0,0 +1,28 @@
+// RUN: llvm-mc -filetype=obj -triple i686-pc-linux-gnu    %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=ELF
+// RUN: llvm-mc -filetype=obj -triple x86_64-pc-linux-gnu  %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=ELF
+// RUN: llvm-mc -filetype=obj -triple i386-apple-darwin9   %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=MACHO
+// RUN: llvm-mc -filetype=obj -triple x86_64-apple-darwin9 %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=MACHO
+
+// Test that we can assemble a GCC-like EH table that has 16381-16383 bytes of
+// non-padding data between .ttbaseref and .ttbase. The assembler must insert
+// extra padding either into the uleb128 or at the balign directive. See
+// PR35809.
+
+        .data
+        .balign 4
+foo:
+        .byte 0xff  // LPStart omitted
+        .byte 0x1   // TType encoding (uleb128)
+        .uleb128 .ttbase-.ttbaseref
+.ttbaseref:
+        .fill 128*128-1, 1, 0xcd    // call site and actions tables
+        .balign 4
+.ttbase:
+        .byte 1, 2, 3, 4
+
+// ELF:   Name: .data
+// MACHO: Name: __data
+// CHECK: SectionData (
+// CHECK:   0000: FF01FFFF 00CDCDCD CDCDCDCD CDCDCDCD
+// CHECK:   4000: CDCDCDCD 01020304
+// CHECK: )
Index: test/MC/ELF/uleb-optimal.s
===================================================================
--- /dev/null
+++ test/MC/ELF/uleb-optimal.s
@@ -0,0 +1,24 @@
+// RUN: llvm-mc -filetype=obj -triple i686-pc-linux-gnu    %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=ELF
+// RUN: llvm-mc -filetype=obj -triple x86_64-pc-linux-gnu  %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=ELF
+// RUN: llvm-mc -filetype=obj -triple i386-apple-darwin9   %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=MACHO
+// RUN: llvm-mc -filetype=obj -triple x86_64-apple-darwin9 %s -o - | llvm-readobj -s -sd | FileCheck %s -check-prefix=CHECK -check-prefix=MACHO
+
+// Test LEB relaxation: this file can be assembled without inserting padding into
+// the TTBase LEB128, but it requires iteration. See PR35809.
+
+        .data
+        .balign 4
+        .byte 0x11, 0x22, 0x33
+        .uleb128 end - start
+start:
+        .fill 128*128-3, 1, 0xcd
+        .align 4
+end:
+        .byte 1, 2, 3, 4
+
+// ELF:   Name: .data
+// MACHO: Name: __data
+// CHECK: SectionData (
+// CHECK:   0000: 112233FF 7FCDCDCD CDCDCDCD CDCDCDCD
+// CHECK:   4000: CDCD0000 01020304
+// CHECK: )