He very well may have, since you compile gcc using gcc.

I think blhack was referring to Ken Thompson's ACM Turing Award acceptance speech "Reflections On Trusting Trust"?

http://c2.com/cgi/wiki?TheKenThompsonHack

"a hack (in every sense), the most subversive ever perpetrated, nothing less than the root password of all evil."

A very very good read :)

And where did the bin version of GCC he or she used to compile that version of GCC come from?

Eventually, somewhere down the chain, you have to have trusted a compiler that wasn't GCC and you probably don't have the source to.

Diff the binaries :)

Which a diff tool you compiled your self, or looking at the hard drive with a magnifying glass?

If they really want to get you they could use a birthday attack?

Since we are talking about checking the compiler that compiles your compiler here.