This is all 10 years old, but I think I first compiled all the packages GCC depends upon using the native tools. This often means rather crude hacks and/or using very old versions of these GNU packages.
Then bootstrap GCC, and finally rebuild everything with the GCC just built. Including GCC itself.
Code generation of GCC v3 wasn't all that terrible compared to the MIPS UCODE compiler. But GCC takes a lot more CPU cycles to do the compilation which can be a problem when all you've got is a 33MHz R3000. I think I used a 200MHz R4400 Indigo2 running a late version of IRIX 4.0.5.
At the very least IRIX 4.0 has a more or less complete ANSI C library. Not any of the fancy POSIX stuff, but still. You should try compiling software for IRIX 3.3: pre-ANSI library, K&R compilers. Now there's a challenge