First, Valgrind starts the program to debug:
$ valgrind --vgdb=yes --vgdb-error=0 [valgrind-options] [program] [program-options]
It will halt until GDB is hooked to the process, from another terminal:
$ gdb [program]
$ target remote | vgdb
Valgrind's tool callgrind
is a branch prediction profiler; its output can be visualized
with Kcachegrind to generate a call graph of the program, among other things.
$ valgrind --tool=callgrind [program] [program-options]
$ kcachegrind callgrind.out.<pid>