занимательно

"variable renaming" и "No SSA" :)

Да, вроде, вот прямо из книги определение: E(n) - это минимальное число регистров, необходимое для вычисления n.

И классическая проблема оптимизатора, что делать раньше, регаллокатор или планирование.

Only the most valuable optimization usage:

* function inlining
* global common sub-expression elimination
* variable renaming
* register pressure sensitive loop invariant code motion
* sparse conditional constant propagation
* dead code elimination
* code selection
* fast register allocator with implicit * coalescing hard registers and stack slots for copy elimination

Different optimization levels to tune compilation speed vs generated code performance

No SSA (single static assignment form)

"code selection" это подбор особых инструкций процессора?

Да, Ершов придумал много разных компиляторных вещей. Просто VN и числа Ершова — вещи совершенно разные.

Вроде того, обычно это фаза трансляции IR в инструкции.

Нет. Просто инструкций

Ок, а в чём оптимизация заключается? 🤔

Тут скорее всего смешали пипхол и селекцию вместе.

Важный вопрос, а никто не знает использует ли Владимир Макаров Телеграм? Можно его напрямую сюда пригласить?

В том, что этот выбор неоднозначен. Вот недавно на HN вспоминали древнюю систему BURS как раз :)

Для тех, кто считает, что там нечего оптимизировать — https://www.springer.com/gp/book/9783319340173

Вот оно как называется,peephole

спс

Написал письмо Владимиру Макарову с просьбой взглянуть на заданные в нашем чате вопросы, вот что он ответил (у него нет на клавиатуре русских букв, легче писать на английском):

"Code selection is an old term, e.g. used by Davidson and Fraser before inventing their IBURG approach.  Code selection is to combine several data-dependent machine insns into one.  This approach is still used in GCC.  GCC code selection pass called combiner is basically pattern
matching algorithm where different GCC IR (called RTL at this level) patterns corresponding to one or more machine insns are described in GCC machine-dependent description.  Additionally GCC can split a combined
IR-insn into several IR-insns in hope to match them by the existing patterns. Writting patterns to generate a good code is an art in GCC.

MIR uses GCC approach but w/o IR insn splitting.  For simplicity it is also done after RA, not before as in GCC.

Modern approach    (more frequently called insn selection) is to cover IR data-dependent tree (or DAG) by IR patterns describing machine insns with the minimal cost.  For IR data-dependent tree it is a simple task.
For DAG it is a NP-complete problem.  LLVM uses    this approach.
Writing patterns for LLVM is more mechanical process than in GCC.

Peephole optimization is to change adjacent insns in some small-sized window to better ones.  Insns in the window might be not data-dependent.  Although GCC has a newer peephole optimizations (called peephole2) for which you can describe data-dependent insn
patterns.  Peephole optimization is done after RA.

MIR code selection is done after RA too    but its    algorithm closer to GCC combiner one therefore I use the code selection term.

I do a lot of GCC bechmarking on SPEC (the latest one is CPU2017).  So I can answer about the most valuable optimizations for this benchmark suite on x86-64.  They are a decent global RA (a stupid local one can make code 5 times slower), code selection which gives additional 5-7% for modern x86_64 micro-arhitectures, and inlining to remove call related insns and increase scope for optimizations (including global RA).

Auto-vectorization can be profitable for FP programs (SPECFP 2017 can be improved by 4% with auto-мectorization) but actually can worsen code for SPEC2017 integer benchmarks because grouping data for vectorization is not free.

As for register renaming and SSA.  People are a right.  It    is better do this with SSA. I started MIR project having only RA and code selection.  Then I added SCCP and CGSE as I found them important for my future Ruby specific JIT.  Then I added loop    invariant code motion which requires reaching definition analysis.  Having the analysis
implementation of register renaming is not a big deal.

May be it is worth to switch to SSA now    or remove loop invariant motion and register renaming as they give practically nothing for my test cases.

By the way, register renaming in GCC is    done w/o SSA.  It is based on data-flow analysis written by Kenneth Zadeck (one of SSA inventor). So SSA has not only pros.  There are some cons also.
"

Спасибо, но Вы бы предупредили хоть! Если бы я знал, что он будет отвечать на то, что мы тут пишем, то постарался бы сформулировать интересные вопросы :)

Чуть позже постараюсь прокомментировать по пунктам.

Древний подход от Davidson&Fraser как раз ведь и основан на peephole-оптимизации.

Вот пример из проекта MIR: https://github.com/vnmakarov/mir/blob/master/mir-gen.c#L5082
Здесь загрузка константы отдельной командой заменяется в add значением в поле disp (смещение).

К слову сказать, сам термин peephole-оптимизация сегодня довольно неоднозначный. Под ним часто подразумевают любые локальные замены. Хоть на DAG, хоть в списке команд. Хоть до распределения регистров, хоть после него.

Не очень ясно, почему в MIR не используется выбор команд на тех же деревьях. Возможно, использование динамического программирования представляется слишком накладным, но ведь вместо учета стоимостей можно использовать классический maximal munch (Cattell).

На практике выбор команд с DAG не является NP-полным. Мы можем за линейное время проверить два корневых (rooted) DAG с пронумерованными ребрами. В LLVM как раз используется жадный подход.

Построение SSA для линейного участка, то есть переименование без использования phi-функций, это одно из старейших оптимизирующих преобразований. Здесь, кстати говоря, есть давнее, но занятное обсуждение "Block Single Assignment" :) https://compilers.iecc.com/comparch/article/07-04-075

Ну так оно и есть peephole это переписывание (или комбинирование / упрощение) нескольких инструкций/выражений в небольшом окне на более оптимальный набор. Ну а учитывая что компиляторы сейчас имеют несколько уровней - HIR, MIR, LIR то это можно применять на любом уровне и смысл от этого не меняется

Это не совсем так. Классический алгоритм peephole-оптимизации работает в окне для списка команд. И процесс замен происходит от конца к началу списка. Там свои нюансы.
А локальные замены на графе как представить в виде окна? Какая-то часть подграфа, заменяемого по образцу, может образовать тесный кластер, но некоторые ребра могут простираться очень далеко, особенно, если это константы. На графе понятие локальности уже иное.