When I analyze /usr/bin/diff with gdb, I see that __gmon_start__ is being called before _start for some reason. Every document I have found so far has been claiming that _start is the entry point of a program; and the entry point field in the ELF header also points to the address of _start.
Why does diff not start executing with _start; and where is that information held?
Every document I have found so far has been claiming that _start is the entry point of a program
For fully-static executable, this is true.
For a dynamically linked executable, the user-space executions starts at the _start symbol of the loader (ld.so), and there are usually 10s of thousands of instructions and many system calls executed before the loader calls _start in the a.out.
In the process of getting to _start in a.out, functions from the main executable could be called (and that's what you are observing).