I can't provide the .o files exhibiting this problem, hence I have to just give my analysis. We have a case where there are big object files containing many of such relocations: 000000030328 042c00000027 R_IA64_DIR64LSB 0000000000000000 .text + 2ee51 000000030330 042c00000027 R_IA64_DIR64LSB 0000000000000000 .text + 2ed41 000000030338 042c00000027 R_IA64_DIR64LSB 0000000000000000 .text + 2ee41 Thousands of them. The special thing here is, many relocations against the same symbol (here a local pseudo symbol for .text) but differing addends. The ia64 linker in elfNN_ia64_check_relocs goes over all relocs, calling get_dyn_sym_info() on each one. For local symbols (as is the case here) this collects a linked list of elfNN_ia64_dyn_sym_info entries _for each addend_ without duplicates. As this is a linked list just checking for duplicates is O(N^2) in the number of such relocs. The above relocs specifically where in the .rela.debug_ranges section, so in this case it's debug info which leads to ld breaking down. Linking the specific .o files in question needs many hours it seems (I wasn't yet patient enough to really leave it running through the end), but in gdb one can see that elfNN_ia64_check_relocs doesn't finish for a long time. The O(N^2) is quite obvious, but I don't know yet if that's the only cause for the huge reported link time.
I need a testcase to look into it. You can contact me at hongjiu.lu@intel.com if it helps.
A patch is posted at http://sourceware.org/ml/binutils/2006-03/msg00377.html The link time went from 1300 minutes to 1 minute.
Fixed by http://sourceware.org/ml/binutils/2006-04/msg00076.html