Профиль программы и его предсказание

Сегодня хотел бы рассказать про то как в компиляторе представлена профильная информация и как она предсказывается. Студентам и просто людям часто выносит мозг тот факт что компилятор статически (т.е. без реального исполнения) может предсказывать такие вещи как количество итераций у цикла или просто вероятности переходов, поэтому расскажу об этом по подробнее.
Для начала опишу проблему. В некоторых процессорах с прямым порядком исполнения команд (in-order) нужно уметь хорошо планировать код. Более того ситуация становится совсем плохой если в процессоре отсутствует предсказатель переходов. Т.о. компилятору становится необходимо брать все эти функции на себя. Необходимо понять по какой ветке и с какой вероятностью пойдёт исполнение, какой цикл является горячим и стоит ли его раскручивать/конвейеризовывать, какая функция является горячей и стоит ли её инлайнить. (Кстати, из интеловских лекций следует что они также используют предсказатель и для x86 процессоров).

Чтобы уметь делать всё выше перечисленное, мы приходим к понятию профиля. Внутри компилятора он представляет из себя немного не то к чему привыкли пользователи gprof/perf/etc. Надеюсь что читатель уже знает что такое cfg, поэтому перейдём к описанию. Профилем программы является информация о количестве проходов по узлам cfg и вероятность перехода по каждой дуге. Чтобы было понятно, можно посмотреть на рисунок:

На нём видно, что каждая дуга (исходящая, но к входящим это тоже относится) имеет 2 цифры. Первая - это счётчик. Он говорит сколько раз мы прошли по данной дуге. Вторая - это вероятность. Она говорит с какой вероятностью мы переходим на данную дугу из исходного узла. Эти две цифры вазимозаменяемы и должны постоянно поддерживаться в согласованном состоянии. Для узла вероятность смысла не имеет (на самом деле имеет, но не в данном контексте), поэтому у него есть только счётчик.

Откуда берётся данная информация? Есть два способа её получить. Первый, и довольно очевидный - исполнить программу и посмотреть. Но такой метод имеет много минусов, и к сожалению используется редко (а ведь он может значительно ускорить программа на Эльбрусах, да и не только).

Второй метод - предсказать. Предсказание проходит по следующему принципу: мы полагаем что стартовый узел имеет счётчик 1. Далее для всех исходящих дуг мы вычисляем счётчики по формуле:
$$
C(E_{\text{out}}) = C(N) C(P_{\text{out}})
$$
Далее для каждого узла мы вычисляем счётчик по формуле:
$$
C(N) = \sum\limits_{i = 1}^K C(E^{in}_i)
$$
Таким образом проходим по всей процедуре и предсказываем профиль. Возникает логичный вопрос: откуда взять вероятности? Их берём с полка выставляем исходя из данных, известных во время компиляции или некоторых эвристик. Например если мы можем статически прикинуть результат условного оператора, то вероятность вычислить легко. Если нет, то компилятор имеет определённую статистику по вероятностям переходов при определённой структуре cfg.

Теперь вопрос: что делать если у нас встретилась обратная дуга? Т.е. имеем cfg следующего вида:

Если будем действовать по описанному выше алгоритму, то зациклимся и будем постоянно наращивать счётчик. Решается это поиском вероятности выйти из цикла (т.е. без учёта обратной дуги) и проставления счётчиков в соответствии с этой вероятностью. Формула для этого на удивление простая, а реализация её вычисления на удивление сложное:
$$
I = \frac1{P_{loop\_out}(E^{out}_i)}
$$
Самая большая хитрость в том чтобы её посчитать. Не буду описывать здесь как это делается (это долго и скучно), скажу только что сложность алгоритма немного возрастает если идёт гнездо циклов, и сильно возрастает если цикл несводимый.

Касательно точности такого предсказания могу сказать что никогда не делал исследования этого вопроса, но попытки отключения профиля или неаккуратная его корректировка могут просаживать производительность в разы.