Look at the directories and built-in.o files that show up in a tinyconfig build, and check for directories where all of the code depends (directly or indirectly) on a single configuration symbol. (find -name built-in.o -size 8c will find built-in.o files that contain no code.) in the Makefile for the parent directory, change obj-y to obj-$(CONFIG_THAT_SYMBOL), to stop the build system from recursing into that directory at all. This doesn't directly make the kernel smaller, but makes the build faster and makes it easier to identify which code gets built in.

Compile out kernel/time/ntp.c, along with adjtimex and similar syscalls. (done)

Remove runtime extable sorting logic if CONFIG_BUILDTIME_EXTABLE_SORT (in progress)

Sort module extables at build time, as CONFIG_BUILDTIME_EXTABLE_SORT does for vmlinux, and drop the runtime sort.

Compile out printks below a certain priority level. (in progress)

Compile out x86 CPU information printing and corresponding structure fields: model decoding, TLB size decoding. Add a config option for this, and make it depend on CONFIG_PRINTK or in some cases CONFIG_PROC_FS (for /proc/cpuinfo). (in progress)

Reverse CONFIG_DISABLE_DEV_COREDUMP to have "default y" and use 'n' to force-disable, so allnoconfig and tinyconfig do the right thing. (done)

Drop legacy processor names from struct cpu_dev. May need to make this a configuration option. (done)

Make mm/debug.c optional. (in progress)

Make lib/halfmd4.c optional, and make ext3 and ext4 select it. (done)

Make lib/rhashtable.c optional, and make the relevant bits of net/ select it. (done)

Make flex_array optional, and make the three things using it (selinux, openvswitch, PROC_FS) select it. (done)

Enhance scripts/bloat-o-meter to detect size changes in sections like .rodata not associated with a symbol. In particular, this should detect changes to string constants.

Make SRCU optional; make portions of the kernel that define an srcu_struct depend on the resulting new Kconfig symbol. This will include the srcu_notifier mechanism, in turn used by the clock framework and cpufreq.

Rip out the rest of kernel/smpboot.c if !CONFIG_SMP

Make ptrace optional.

Rip out more of the per-CPU infrastructure when CONFIG_SMP=n

Support configuring out kswapd.

Make the kernel's entire random number infrastructure optional.

Compile out mm/vmstat (need to stub out bits that obtain statistics used by other bits of the kernel)

Compile out signal handling.

Compile out support for capabilities; make capable always return true for root and false for non-root. (done)

Compile out support for "personalities".

Compile out support for non-root users and groups. When disabled, UID and GID effectively always equal 0, and all the syscalls involving UIDs and GIDs go away. (done)

Compile out support for supplementary GIDs. (This option would depend on the previous option for non-root users and groups.)

Compile out support for xattrs, and all the corresponding syscalls.

Compile out support for sockets and all the socket-related syscalls.

Compile out support for character devices, similar to the existing CONFIG_BLOCK.

Support nommu on x86.

Revive the function-sections support. (Note: LTO would make this obsolete; only worth working on this if LTO takes too long to get upstream.)

Drop exported symbols not used by the set of modules compiled with the kernel. Add a new Kconfig option (default y) to export all symbols; when turned off, analyze the set of symbols needed by all compiled modules, and allow the compiler to omit all other symbols from the compiled kernel. (Note that stripping those symbols from the kernel after building won't allow the compiler to throw away other symbols that then become unused.)

Automatic syscall elimination: Given a specific userspace, automatically find out what syscalls it needs and compile everything else out.

Kernel command-line constant folding: Given a kernel command line at compile-time, parse it and turn all the variables it would end up in into compile-time constants.

Execute in place (XIP) for x86

Constant folding for unused mount options (for instance, drop ext4's dioread_lock options at build time)

Add size test for kselftest: boot a minimal kernel under qemu/kvm, and capture information from that kernel. CONFIG_PRINTK would allow capturing the display of available memory from early boot, but we want to support kernels without CONFIG_PRINTK. This could also use -mem-path and capture data directly from a memory address. Ideally, the memory check and writing to a specified address should occur right before the kernel would attempt to run /sbin/init; the check itself needs to be optional too, though.

Go look at patches in OpenWRT to make the kernel smaller

Analyze size of inlines (Andi Kleen has some scripts)

make kernel/pid.o configurable (replace pidhash system with simpler pid allocator (e.g. from 1.0))

Compile out TSC support and calibration.

Compile out types of video support from arch/x86/boot: VESA, VGA, and BIOS

Compile out MCA support from arch/x86/boot.

Compile out arch/x86/kernel/cpu/intel_cacheinfo.c

Compile out spurious interrupt support (kernel/irq/spurious.c)

Compile out process exit support (kernel/exit.c and the corresponding syscalls), for systems that will only ever run a fixed set of processes that should never exit.

Revive and complete the patches to remove perf and the instruction decoder. Need to rework the config option structure.

Allow board-specific DT parser removal. From Josh, "… effectively compile in a parsed description and ditch the parser. Bonus if you can make the values parsed out of it into compile-time constants for constant folding." Jason Cooper jason@lakedaemon.net is responsible for this idea.

Modify GCC's __attribute__((section(...))) to support specifying different sections for initialized (.data) and uninitialized (.bss) data. Use that to put uninitialized __initdata or per-CPU data into .bss. (This will require very detailed exploration of the toolchain, Linux's linker scripts, and similar.)

Teach GCC to merge identical function bodies

Make link-time optimization work

Compress "cold" code paths (saves runtime memory)

Analysis to detect dead structure fields

Automatic structure re-layout to drop fields not referenced

Dropping structure field assignments; mark dead fields with an attribute, ignore writes, error on reads

Compile out support for specific format-string components from snprintf and family; would require some support from the toolchain to detect which ones get used in a build. Alternatively, replace all the non-human-targeted uses of snprintf with a call to an underlying helper function shared with snprintf, and then use dead code elimination to drop the unused ones.