Index: lib/MC/MCAssembler.cpp
===================================================================
--- lib/MC/MCAssembler.cpp
+++ lib/MC/MCAssembler.cpp
@@ -868,10 +868,14 @@
   SmallString<8> &Data = LF.getContents();
   Data.clear();
   raw_svector_ostream OSE(Data);
+  // The compiler can generate 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. To accommodate such tables, relaxation can
+  // only increase an LEB fragment size here, not decrease it. See PR35809.
   if (LF.isSigned())
-    encodeSLEB128(Value, OSE);
+    encodeSLEB128(Value, OSE, OldSize);
   else
-    encodeULEB128(Value, OSE);
+    encodeULEB128(Value, OSE, OldSize);
   return OldSize != LF.getContents().size();
 }
 
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-NEXT:   0000: FF01FFFF 00CDCDCD CDCDCDCD CDCDCDCD
+// CHECK:        4000: CDCDCDCD 01020304
+// CHECK-NEXT: )