Как JIT инлайнит наш C# код (эвристики)

Инлайнинг — одна из самых важных оптимизаций в компиляторах. Она не только убирает оверхед от вызова, но и открывает много возможностей для других оптимизаций, например, constant folding, dead code elimination и т.д. Более того, иногда инлайнинг приводит к уменьшению размера вызывающей ф-ции! Я опросил несколько человек на предмет знают ли они по каким правилам инлайнятся ф-ции в C# и большинство ответили, что JIT смотрит на размер IL кода и инлайнит только маленькие ф-ции размером, скажем, до 32 байт. Поэтому я решил написать этот пост, чтобы раскрыть детали реализации при помощи вот такого примера, который покажет сразу несколько эвристик в деле:

Как вы думаете, заинлайнится ли вызов конструктора Volume тут? Очевидно, что нет. Он слишком большой, особенно из-за тяжеловесных throw new операторов, которые приводят к довольно жирному кодгену. Давайте проверим в Disasmo:

Заинлайнился! Более того, все выбросы исключений и их ветки успешно удалились! Вы можете сказать что-то в стиле «А, окей, джит очень умен и проделал полный анализ всех кандидатов к инлайну, посмотрел что будет если передать конкретные аргументы» или «Джит пробует заинлайнить всё что можно, выполняет все оптимизации, а потом решает профитно это или нет» (возьмите в руки комбинаторику и посчитайте сложность этой операции, например, для графа вызовов из десятка-двух методов).

Ну… нет, это нереалистично, особенно в терминах just in time. Поэтому, большинство компиляторов используют так называемые наблюдения и эвристики для решения это классической задачи о рюкзаке ^[1] и пытаются сами определить себе бюджет и в него максимально эффективно вписаться (и нет, PGO не панацея). RyuJIT имеет положительные и отрицательные наблюдения. Положительные увеличивают коэффициент выгоды (benefit multiplier). Чем больше коэффициент — тем больше кода мы можем заинлайнить. Отрицательные наблюдения наоборот — понижают его или вообще могут запретить инлайнинг. Давайте посмотрим какие наблюдения сделал RyuJIT для нашего примера:

Эти наблюдения можно увидеть в логах из COMPlus_JitDump (например, в Disasmo):

Все эти простые наблюдения повысили коэффициент с 1.0 до 11.5 и помогли успешно побороть бюджет инлайнера, например, тот факт, что мы передаем аргумент-константу и она сравнивается с другой константой говорит нам, что с большой долей вероятности после схлопывания констант удалится одна из веток условия и код станет меньше. Или, например, то, что это конструктор и он вызывается внутри цикла — это тоже намек джиту, что он должен смягчить требования к инлайнингу.

Помимо benefit multiplier, RyuJIT так же использует наблюдения для прогноза размера нативного кода ф-ции и ее performance impact используя магические константы в EstimateCodeSize() ^[2] и EstimatePerformanceImpact() ^[3] полученные при помощи ML.

Кстати, а вы заметили этот трюк?:

if ((value - 'A') > ('Z' - 'A'))

Это оптимизировання версия к:

if (value < 'A' || value > 'Z')

Оба выражения являются одним и тем же, но в первом случае у нас один базовый блок, а во втором их целых три. Оказывается, в инлайнере есть строгий лимит на кол-во базовых блоков в ф-ции и если оно превышает 5 то не важно какой большой у нас benefit multiplier — инлайнинг отменяется. Поэтому я применил эту уловку, чтобы вписаться в это строгое требование. Было бы классно если бы Roslyn делал это за меня.

Issue в Roslyn: github.com/dotnet/runtime/issues/13347 ^[4]
PR в RyuJIT (моя неловкая попытка): github.com/dotnet/coreclr/pull/27480 ^[5]

Там же ^[6] я описал пример почему это имеет смысл сделать не только в Jit но и в компиляторе C#.

Инлайнинг и виртуальные методы

Тут всё понятно, нельзя заинлайнить то, о чем нет информации на этапе компиляции, хотя если тип или метод sealed то почему бы и нет ^[7].

Инлайнинг и выброс исключений

Если метод никогда не возвращает значение (например, просто делает throw new ...) то такие методы автоматически помечаются как throw-helpers и не инлайнятся. Это такой способ замести сложный кодген от throw new под ковер и ублажить инлайнер.

Инлайнинг и [AggressiveInlining] атрибут

В этом случае вы рекомендуете инлайнеру заинлайнить метод, но тут надо быть предельно осторожным по двум причинам:

• Возможно, вы оптимизируете один случай и ухудшаете все остальные (например, улучшаете случай константных аргументов) по размеру кодгена.
• Инлайнинг частенько генерирует большое количество временные переменных, которые могут перешагнуть определенный лимит — количество переменных, жизненный цикл которых RyuJIT может отследить (512) и после него код начнет обрастать жуткими спиллами в стек и сильно замедляться. Два хороших примера: тыц ^[8] и тыц ^[9].

Инлайнинг и динамические методы

В данный момент такие методы ничего не инлайнят и сами не инлайнятся: github.com/dotnet/runtime/issues/34500 ^[10]

Моя попытка написать свою эвристику

Недавно я попытался написать собственную эвристику чтобы помочь вот такому случаю:

В своем прошлом посте ^[11] я упоминал что совсем недавно я оптимизировал в RyuJIT вычисление длины от константных строк ("Hello".Length -> 5), так вот, в примере выше ^ мы видим что если заинлайнить Validate в Test, то мы получим if ("hello".Length > 10) что оптимизируется в if (5 > 10) что оптимизируется в удаление всего условия/ветки. Однако, инлайнер отказался инлайнить Validate:

И главная проблема тут в том, что пока нет эвристики, которая подскажет джиту, что мы передаем константную строку в System.String::get_Length, а значит что callvirt-вызов скорее всего свернется в константу и вся ветка удалится. Собственно, моя эвристика ^[12] и добавляет это наблюдение (единственный минус — приходится резолвить все callvirt'ы что является не очень быстрым).

Существуют и другие ограничения, со списком которых можно в целом ознакомиться вот тут ^[13]. А тут ^[14] можно прочитать мысли одного из главных разработчиков JIT о дизайне инлайнера и его статью ^[15] на тему использования Machine Learning для этого дела.

Автор: Егор

Источник ^[16]