I've looked into #20 (ld-tigcc optimization).
topics/108648-ld-tigcc-flash-os-bss-special/4 tells us two things:
[ul][li]The major performance offenders are the Reloc and Symbol linked lists[/li]
[li]the data structure faster than linked lists that we're going to use should be a tree structure[/li][/ul]

Finding a red-black tree library is easy: there's a GPLed one in the Linux kernel.
However:
[ul][li]mapping the InsertAfter, InsertBefore, Append, Push list operations to a colored tree structure is maybe not that trivial[/li]
[li]the list macros are used at dozen of places (most places just _read_ the lists), and each of these places must be changed...[/li][/ul]