Как работают профайлеры для компилируемых языков?

Два крайних случая - статистические и точные; первые прерывают исполнение программы с определенной частотой и смотрят, где находилось исполнение; вторые ставят точки прерывания или служебные вызовы в определенных точках программы (обычно точки входа в функции. В реальности может использоваться комбинация подходов.

Еще можно пускать программу в эмуляторе ЦП (valgrind и К).

Я вот не могу понять, там какие-то супер алгоритмы? Или где?

В основном берут бабки за гуйню.

Лол, я как раз написал свой недавно. Для фри, драгонфлая и нет бздей должен пахать (под нет особо не тестировал)

https://github.com/shamazmazum/vsprofiler/

Смысл, да, такой: таймер (man setitimer) посылает программе сигнал через определенное время. Ты ловишь сигнал и анализируешь rip регистр (где программа сейчас) и стек (rsp, rbp). Смотришь, каким функциям это соответствует (анализируя бинарник и /proc/<pid>/map и строишь отчет.

Как точное количество вызовов функции посчитать и что делать, если было скомпилировано с -fomit-frame-pointer я не знаю. Хотя можно по всякому поизвращаться, но мне и не надо особо

https://software.intel.com/en-us/intel-vtune-amplifier-xe

Если надо, то его можно поиметь бесплатно для некоммерческого использования (см. гугл).

valgrind - открываешь исходники и смотришь как оно устроено