How does gcc find as, ld and other binutils executables?

Some of the paths (e.g., to cc1) are compiled in. Others (e.g., as) use normal lookup in $PATH. This can vary depending on the options GCC is configured with.

You can tell fairly easily by running with strace, and grepping for exec|stat.

$ strace -f gcc foo.c -o foo |& grep exec
⋮
[pid 24943] execve("/usr/lib/x86_64-linux-gnu/gcc/x86_64-linux-gnu/4.6.1/cc1", …

That is a call to cc1 by a compiled-in path, as you can see from the lack of looking for it. Its also not in $PATH.

[pid 24944] execve("/home/anthony/bin/as", ["as", "--64", "-o", "/tmp/ccCIrcGi.o", "/tmp/ccbw3PkL.s"], [/* 51 vars */]) = -1 ENOENT (No such file or directory)
[pid 24944] execve("/usr/local/bin/as", ["as", "--64", "-o", "/tmp/ccCIrcGi.o", "/tmp/ccbw3PkL.s"], [/* 51 vars */]) = -1 ENOENT (No such file or directory)
[pid 24944] execve("/usr/bin/as", ["as", "--64", "-o", "/tmp/ccCIrcGi.o", "/tmp/ccbw3PkL.s"], [/* 51 vars */]) = 0

That is looking for as in $PATH. You can tell because its trying each location in $PATH in order.

I've omitted a lot of strace output—even with just stat and exec, its several pages long.

Running gcc -v will show you some of the compiled-in paths (as part of the configure line).

How could we create two completely separate gcc toolchains?

Compile GCC from source twice, detailed instructions at: Multiple glibc libraries on a single host

Everything is hardcoded and highly coupled as far as I can see, I don't think there is any other decent solution.

Query the GCC search path

You can also query the GCC search path with:

gcc -print-search-dirs | grep -E '^programs' | tr ':' '\n'

sample output:

programs
 =/usr/lib/gcc/x86_64-linux-gnu/6/
/usr/lib/gcc/x86_64-linux-gnu/6/
/usr/lib/gcc/x86_64-linux-gnu/
/usr/lib/gcc/x86_64-linux-gnu/6/
/usr/lib/gcc/x86_64-linux-gnu/
/usr/lib/gcc/x86_64-linux-gnu/6/../../../../x86_64-linux-gnu/bin/x86_64-linux-gnu/6/
/usr/lib/gcc/x86_64-linux-gnu/6/../../../../x86_64-linux-gnu/bin/x86_64-linux-gnu/
/usr/lib/gcc/x86_64-linux-gnu/6/../../../../x86_64-linux-gnu/bin/

and a specific program with:

gcc -print-prog-name=cc1

sample output:

/usr/lib/gcc/x86_64-linux-gnu/6/cc1

GCC spec files

It is wort mentioning that what actually determines the final cpp, ld, as are the "spec" files in the GCC source code, see also: What are GCC's passes and invoked programs?