[MIPS] `MIPSELFObjectWriter::sortRelocs()` makes compilation near-unusably slow for O32

[alexrp]

Building and running the Zig standard library tests (with LLVM 18.1.8):

❯ time zig4 build -j8 -Dno-lib -Dno-bin -fqemu test-std -Dtest-target-filter=mips64- -Dtest-target-filter=mips64el-
________________________________________________________
Executed in  209.15 secs    fish           external
   usr time   18.17 mins  361.00 micros   18.17 mins
   sys time    1.02 mins   64.00 micros    1.02 mins
❯ time zig4 build -j8 -Dno-lib -Dno-bin -fqemu test-std -Dtest-target-filter=mips- -Dtest-target-filter=mipsel- -Dtest-slow-targets
________________________________________________________
Executed in   66.50 mins    fish           external
   usr time  242.35 mins    5.87 millis  242.35 mins
   sys time    1.06 mins    0.30 millis    1.06 mins

As a result of this, we've had to disable MIPS O32 tests for local development and only run them in CI.

Attaching a debugger made it clear that the overwhelming majority of time is spent in MIPSELFObjectWriter::sortRelocs(). Specifically (and perhaps unsurprisingly) here:

llvm-project/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

Lines 468 to 476 in ef67601

	// Find the best matching relocation for the current high part.
	// See isMatchingReloc for a description of a matching relocation and
	// compareMatchingRelocs for a description of what 'best' means.
	auto InsertionPoint =
	find_best(Sorted.begin(), Sorted.end(),
	[&R, &MatchingType](const MipsRelocationEntry &X) {
	return isMatchingReloc(X, R, MatchingType);
	},
	compareMatchingRelocs);

Some extra context:

(gdb) p Relocs.size()
$3 = 1412282
(gdb) p Remainder.size()
$4 = 439999
(gdb) p Sorted.size()
$5 = 1019010

We build the standard library tests as one big executable so we end up with a ton of relocations. Due to the size of the resulting LLVM IR, I can't easily post it here. 🙁

[llvmbot]

@llvm/issue-subscribers-backend-mips

Author: Alex Rønne Petersen (alexrp)

Building and running the Zig standard library tests (with LLVM 18.1.8):

❯ time zig4 build -j8 -Dno-lib -Dno-bin -fqemu test-std -Dtest-target-filter=mips64- -Dtest-target-filter=mips64el-
________________________________________________________
Executed in  209.15 secs    fish           external
   usr time   18.17 mins  361.00 micros   18.17 mins
   sys time    1.02 mins   64.00 micros    1.02 mins
❯ time zig4 build -j8 -Dno-lib -Dno-bin -fqemu test-std -Dtest-target-filter=mips- -Dtest-target-filter=mipsel- -Dtest-slow-targets
________________________________________________________
Executed in   66.50 mins    fish           external
   usr time  242.35 mins    5.87 millis  242.35 mins
   sys time    1.06 mins    0.30 millis    1.06 mins

As a result of this, we've had to disable MIPS O32 tests for local development and only run them in CI.

Attaching a debugger made it clear that the overwhelming majority of time is spent in MIPSELFObjectWriter::sortRelocs(). Specifically (and perhaps unsurprisingly) here:

llvm-project/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp

Lines 468 to 476 in ef67601

	// Find the best matching relocation for the current high part.
	// See isMatchingReloc for a description of a matching relocation and
	// compareMatchingRelocs for a description of what 'best' means.
	auto InsertionPoint =
	find_best(Sorted.begin(), Sorted.end(),
	[&R, &MatchingType](const MipsRelocationEntry &X) {
	return isMatchingReloc(X, R, MatchingType);
	},
	compareMatchingRelocs);

Some extra context:

(gdb) p Relocs.size()
$3 = 1412282
(gdb) p Remainder.size()
$4 = 439999
(gdb) p Sorted.size()
$5 = 1019010

We build the standard library tests as one big executable so we end up with a ton of relocations. Due to the size of the resulting LLVM IR, I can't easily post it here. 🙁

[alexrp]

and only run them in CI

We're unfortunately reverting even this. The extra load on CI machines across concurrent runs has caused the run times to jump from 2-3 hours to 6-7, resulting in frequent timeouts.