Компиляторы *

Устройство компилятора (кратко) на LLVM
Компилятор - инструмент конвертации исходного кода, написанного на высокоуровневом языке программирования в машинный код, который может исполнять компьютер.

Компилятор делится на 3 этапа:

• FRONTEND - анализирует текст исходного кода и преобразует его в IR.

• MIDDLE - анализирует и оптимизирует этот сгенерированный код IR.

• BACKEND - преобразует IR в машинный код.

Сам компилятор, и собственно язык программирования состоит из нескольких частей.

Lexer - лексер

Лексер сканирует и превращает сырой текст в токены. То есть сам исходный код разбиваеты на набор токенов (такие как литералы, идентификаторы, ключевые слова, операторы, разделители)
Лексер читает исходный код символ за символом и идентифицирует последовательности символов, соответствующие определённым правилам языка.

Парсинг

Парсинг немного сложнее чем лексический анализ. Существует множество паресров и парсеров-генераторов.

Парсеры в компиляторах обычно принимают входные данные в форме токенов и строят определенное дерево - AST или дерево парсинга.

Обычно компиляторы строятся из множества маленьких компонентов, которые берут входные данные, меняют их или преобразуют их в различные выходные данные. Это одна из причин, по которым функциональные языки хорошо подходят для создания компиляторов. Другие причины — прекрасное сопоставление с эталоном и довольно обширные стандартные библиотеки. Прикольный факт: первая реализация компилятора Rust была на Ocaml.

Советую держать эти компоненты как можно более простыми и автономными — модульность сильно облегчит процесс. По-моему, то же можно сказать и о многих других аспектах разработки ПО.

AST

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

IR

Эта часть занимается созданием [[1.2 IR]]. Через примитивы LLVM мы можем сгенерировать промежуточное представление. Каждому типу в AST дается метод, называемый codegen, который всегда возвращает объект значение LLVM, используемый для представления одного регистра присваивания (single assignment register), который является переменной для компилятора, которая может быть назначена только один раз. Интересно, что в этих примитивах IR то, что в отличии от ассемблера, они не зависят от какой-либо конкретной архитектуры машины, и это значительно упрощает работу для разработчиков языков, которым больше не нужно сопоставлять вывод в набор инструкций процессора. Теперь, когда фронтенд может генерировать IR, инструмент LLVM Optimizer используется для анализа и оптимизации сгенерированного кода. Он выполняет несколько проходов по IR и выполняет такие действия как устранение мертвого кода и скалярная замена агрегатов, и, наконец, это приводит нас к бекенду, где мы пишем модуль, который принимает IR в качестве входных данных, который выдает объектный код, который может работать на любой архитектуре.

LLVM IR: что это такое?

Главной особенностью LLVM является промежуточное представление кода (англ. Intermediate Representation, IR), форма, которую использует LLVM для представления кода в компиляторе. LLVM IR был разработан для выполнения функций промежуточного анализа и преобразований внутри оптимизатора компилятора. Ее создание имело целью решение множества специализированных задач, включая поддержку легковесных оптимизаций среды выполнения, кроссфункциональные и межпроцедурные оптимизации, полный анализ программы и агрессивные реструктурирующие преобразования. Промежуточное представление кода определено как язык первого порядка с четкой семантикой.

IR (Intermediate Representation) в контексте LLVM — это промежуточное представление кода. Это низкоуровневое, независимое от платформы и типобезопасное представление программного кода, которое используется в качестве промежуточного языка между интерфейсной частью и серверной частью компилятора.

define i32 @add1(i32 %a, i32 %b) {
entry:
  %tmp1 = add i32 %a, %b
  ret i32 %tmp1
}

define i32 @add2(i32 %a, i32 %b) {
entry:
  %tmp1 = icmp eq i32 %a, 0
  br i1 %tmp1, label %done, label %recurse

recurse:
  %tmp2 = sub i32 %a, 1
  %tmp3 = add i32 %b, 1
  %tmp4 = call i32 @add2(i32 %tmp2, i32 %tmp3)
  ret i32 %tmp4

done:
  ret i32 %b
}

Этот код LLVM IR соответствует следующему коду на языке C, обеспечивающему возможность сложения целых чисел двумя разными способами:

unsigned add1(unsigned a, unsigned b) {
  return a+b;

}
// возможно не самый лучший способ сложения двух чисел
unsigned add2(unsigned a, unsigned b) {
  if (a == 0) return b;
  return add2(a-1, b+1);
}

Как видно из этого примера, LLVM IR — низкоуровневый RISC-подобный набор виртуальных инструкций. Как и настоящий набор инструкций RISC, он поддерживает линейные последовательности простых инструкций (сложение, вычитание, сравнение и ветвление). Эти инструкции имеют трехадресную форму. Это значит, что они берут некоторое количество входных данных и вычисляют результат в другом регистре. LLVM IR поддерживает метки и в целом выглядит как необычная форма языка ассемблера.

Строго говоря, промежуточное представление LLVM является четко определенным и единственным интерфейсом оптимизатора. Это означает, что всё, что необходимо знать, чтобы писать фронтенды для LLVM, это: что такое LLVM IR, как он работает и какие инварианты ему необходимы. Так как LLVM IR имеет текстовую форму, то имеет смысл создавать фронтенд, который выводит LLVM IR в виде текста, а затем отправляет его на оптимизатор и необходимый генератор кода при помощи каналов Unix.

Я доделал компилятор C на Python.

Баги всё ещё есть но их намного меньше

Его я назвал pycc.

Если хотите попробовать, вот гитхаб: https://github.com/SystemSoftware2/pycc

Всё остальное смотрите там.

[UPD]: А за что минусуете?

Всем привет.

Как вы знаете я пишу компилятор C на Python.

Сегодня я исправил баг с типизацией, который случайно нашёл когда делал ошибки.

Вот этот отрывок: void main() { int x = "h"; } обрабатывался как правильный синтатикс. Теперь нет.

И я добавил цикл do-while. Правда в нём есть проблема: в конце если выражения = false то он ещё раз выполняет и потом останавливает цикл do-while. Ну, пока что так.

Пример цикла do-while:

void main() {
  int a = 10;
  do {
    a = a + 1;
  } while (a > 2);
}

Только вывод не то что "a" это 1 а 0. Правда, сил нету добавлять ненужные части кода для исправления.

Ну. Хотя бы работает как то. А то когда в первый раз делал этот цикл то вообще нечего не работало.

Всем пока.

Снова всем привет. В прошлом посту я писал о том что пишу компилятор C (на Python).

Вчера я добавил функции, вот пример программы вычисления факториала с функциями:

void fac(n) {
  int f = 1;
  while (n > 1) {
    f = f * n;
    n = n - 1;
  }
}

void main() {
  fac(5);
}

Что можно заметить нового и чего нету:

• Функция main стала обязательной

• Не обрабатывается тип данных у аргументов (не везде)

• Все переменные и параметры - глобальные

• Оператора return не существует

• Функции объявляются только с помощью void

Вот как компилятор создаёт функции:

1. Добавляет в словарь self.funcs данные о функции

2. Когда видит вызов функции то компилирует код функции но перед компиляцией создаёт переменные со значениями аргументов

Получается мы не заставляем виртуальную машину работать с функциями ВООБЩЕ.

Но и в этом есть свой минус: return сделать будет невозможно.

Самым сложным это сделать нормальный парсер для этого чуда.

Из-за этого я испортил код парсера. Главное работает 😅.

Всем пока.

Всем привет.

Сегодня на данный момент я пишу компилятор C в байткод.

Вы скажете: но C же в машинный код компилируется? В моём случае нет. Лишь в байткод.

Вот правила которые мой C поддерживает:

• цикл do-while, цикл while, условие if-else, цикл for (возможно)

• Из операций: +, -, /, *, ==, !=, <, >

• Декларация переменных только с инициализацией (не int x;) а (int x = 5;)

• Присваивание (типо a = a + 1;) можно при созданной переменной

• Из типов данных только два: int, char

• Функции не обещаю но возможно будут

А то что уже есть:

• if-else, while

• Декларация переменных

• Присваивание переменных

• Все типы данных

• Все операции

Сделать факториал уже можно. Вот пример факториала 5:

int n = 5;
int f = 1;
while (n > 1) {
  f = f * n;
  n = n - 1;
}

Вывод:

Execution finished
n: 0
f: 120

Вот как он работает:

• С помощью регулярок лексер получает нужный токен и тег

• Парсер строит AST

• Компилятор делает байткод

• Виртуальная машина выполняет его

Вот так всё работает.

Все инструкции байткода (на данный момент):

FETCH переменная - положить на стек значение переменной
PUSH число - положить на стек число
POP - я не помню зачем это ведь это не нужно будет нам
ADD, SUB, MUL, DIV - бинарные операции
NOTEQ, EQ, LT, GT - реляционные операции
JMP адрес - перейти по адресу
JNZ адрес - перейти по адресу если на вершине стека не 0
JZ адрес - перейти по адресу если на вершине стека 0
PASS - игнорировать
STORE имя - сделать переменную если она есть и её тип данных
      соответствует типу данных значения
TSTORE имя - декларация переменной
HALT - конец программы

Вот так. На данный момент в проекте где-то 400 строчек кода но это с комментариями и всеми пустыми строками.

Конец. Всем пока.

Заранее создаваемые объекты - целые числа в Питоне

И снова здравствуйте! Здесь мы проверяем "руками" разные штуки в Питоне.

Наверняка все что-то слышали о том, что часть объектов - целых чисел в Питоне заводится заранее, чтобы сэкономить на создании объектов. В Питоне каждая сущность, даже такая как целые числа - это полноценный объект со всеми положенными объекту прибамбасами. Создавать полноценные объекты - дорого. Поэтому в Питоне, да и в других языках, насколько я помню, кажется в Java, например, часть целых чисел, которые считаются часто используемыми, создаётся заранее и потом используется всё время жизни программы. Т.е. когда вы используете какое-то большое целое число, например, n = 10_000 , то под такое число создаётся новый объект каждый раз, а если используете маленькое, например, n = 10, то новый объект не создаётся, а делается ссылка на один и тот же, заранее созданный объект.

Но давайте сами проверим: действительно ли есть такие числа и каков их диапазон. Будем проделывать с числом простейшие манипуляции - сначала увеличивать на 1, потом уменьшать на 1, чтобы получилось тоже самое число. И потом проверим, поменялся ли id (адрес в памяти) у этого числа. Конечно, тут многое будет зависеть от конкретной версии интерпретатора. Какой-то интерпретатор и код k = n - 1 + 1 не будет оптимизировать, а какой-то и в приведённом ниже коде догадается, что все операции можно сделать как одну операцию, посокращает все добавления-вычитания и мы ничего не сможем определить. И тогда нас спасёт только какой-нибудь eval с вычислениями в виде строки. Но обычно интерпретаторы Питона не настолько хитрые и приведённый ниже код вполне работает в Google Colab.

def check_if_int_cached(n):
    k = n + 1
    k -= 1
    return id(k) == id(n)

checks = [(i, check_if_int_cached(i)) for i in range(-10000, 10000)]
for (x, a), (y, b) in zip(checks, checks[1:]):
    if a != b:
        print((x, y)[b])

В этом коде мы:

• Проверяем, сохраняется ли idу числа после некоторых математических манипуляций, которые в итоге дают тоже самое число

• Создаём последовательность из чисел диапазона [-10000, 9999] и результатов нашей проверки [(число, результат_проверки), ...]

• Сцепляем попарно текущий и следующий элемент нашей последовательности, чтобы легче было проверять смену результата проверки, т.е. найти границу диапазона, где проверка даёт уже другой результат

• Если результат поменялся - выводим либо текущий элемент, либо следующий, пользуясь тем трюком питона, что True - это 1. а False - это 0, и таким образом можно легко выбрать из двух чисел либо первое либо второе не через тернарный оператор, а через индексацию [num1, num2][условие]

Запустим наш код. Вывод:

-5

256

Итак, мы определили, что, действительно, целые числа в диапазоне [-5, 256] заранее создаются Питоном и какие бы ни были вычисления в программе, если в их результате получается число из этого диапазона, то под него не создаётся новый объект, а переиспользуется старый.

Давайте ещё проверим - а действительно ли эта оптимизация Питона даёт какой-то выигрыш. Попробуем создавать список из чисел диапазонов [0, 200] и [1000, 1200] и проделаем это миллион раз для солидности стабильности результата.

import time

n = 1_000_000
k = (0, 1000)
m = 200
for i in k:
    t1 = time.perf_counter()
    for _ in range(n):
      lst = list(range(i, i+m))
    t2 = time.perf_counter()
    print(t2-t1)

1.732138877000125

3.547805026000333

Выигрыш по времени получился практически ровно в 2 раза! Но это если ничего не делать, а только создавать список из объектов-чисел. Если там будут ещё какие-то действия и вычисления, возможно, выигрыш будет вообще не заметен.

В предыдущем посте я писал о встроенной оптимизации добавления символов в строку в Питоне. Далее будут и другие посты об интересных мелочах в Питоне, которые быстро и просто могут быть проверены своими руками (за что мне и нравится Питон) . Спасибо за чтение.

Principles and Practice of Programming Languages 

Новый зверь среди академических учебников.

Выложен втихую, доступен свободно, нигде не анонсировался.

Встроенная оптимизация добавления символов в строку.

Люблю делать мини-эксперименты на Питоне. Попробую оформлять их постами, посмотрю, как пойдёт.

Суть проблемы.

Недавно опять всплыл в обсуждении тот неочевидный факт, что современный Питон оптимизирует добавление символов в строку и не всегда создаёт новые строки при этом. Хотя на собеседованиях мы и говорим, что строки в Питоне иммутабельны, и если мы хотим поменять строку, то Питон нам создаёт новую строку, а старую строку мы изменить не можем... Но при этом существует оптимизация, противоречащая этому очевидному знанию.

В общем, давайте проверим, сохраняется ли строка на том же самом месте памяти. Это мы проверим по id объекта. Сохранился id - это тот же объект (хотя и, возможно, изменённый) в том же месте памяти. Поменялся id - это уже другой объект в другом месте, Питон потратил ресурсы на то, чтобы скопировать исходный объект в новое место.

def test_str():
    string = ''
    old_id = id(string)
    print(0, 0, old_id)
    old_i = 0
    for i in range(1, 20000):
        string += '-'
        new_id = id(string)
        if new_id != old_id:
            print(i, i - old_i, new_id)
            old_i = i
            old_id = new_id

test_str()

Запустим (часть строк я сократил для наглядности):

|"№|Шаг|Id|
|:---|:---|:---|
|0|0|2160689512496|
|1|1|2160690869616|
|2|1|2160740037552|
|16|14|2160761306960|
|32|16|2160761158704|
|48|16|2160738952768|
|64|16|2160760928688|
|...|...|...|
|448|16|2160739774000|
|464|16|2160724879344|
|465|1|2160724880928|
|...|...|...|
|1016|1|2160635636480|
|2176|1160|2160726063040|
|3200|1024|2160724362096|
|4128|928|2160688590304|
|4576|448|2160635890208|
|4736|160|2160724769808|
|5056|320|2160744468544|
|8096|3040|2160745279680|
|12064|3968|2160703847904|
|13072|1008|2160724677104|
|14592|1520|2160745337504|
|15600|1008|2160724821296|
|16288|688|2160726148256|

Как интересно. Получается такая картина:

• Первое прибавление. Питон честно выделяет новую строку.

• Второе прибавление. Питон кажется что-то подозревает и выделяет сразу место под следующие прибавления - по 16 ячеек (но в первый раз чуть меньше).

• Прибавление 464. Питон почему-то вдруг обратно переключается на копирование строки каждый раз.

• Прибавление 1016 (тут цифры разные при разных запусках). Питон вдруг вспоминает про оптимизацию и начинает выделять под строку большие куски памяти, довольно неравномерные. Возможно, он выделяет просто те сплошные куски, которые у него есть в куче и поэтому такое отсутствие системы? Тут уже нужно будет смотреть исходники.

В целом картина получается интересная. Кстати, Питон умный и если заменить код на такой, то ничего не изменится, оптимизация сохранится:

string = string + '-'

Оптимизация пропадёт только если сохранять результат в другую переменную.

Почему это важно.

Если бы не было этой оптимизации, то при каждом добавлении символа или строки в нашу строку происходило бы копирование старой строки в новое место, где достаточно памяти под новую строку. Такой процесс имел бы асимптотику O(n²) при добавлении n символов в строку по одному и это было бы очень долго и нерационально. Вместо этого обычно рекомендуют добавлять части строки в список и в самом конце собирать итоговую строку с помощью метода join, что-то типа ''.join(lst). Но, благодаря описываемой тут оптимизации мы видим, что такие добавления можно делать и к строке и производительность при этом должна не сильно страдать. Но конкретика будет зависеть от длины добавляемых фрагментов строки.

"А теперь - слайды!"

Люблю проверять всё "руками", благо Питон это легко и удобно позволяет. Планирую постепенно публиковать и другие эксперименты с Питоном. Спасибо за чтение.

P.S. Таблица в markdown похоже не получилась, подскажите, плиз, как поправить!

P.P.S. Пишут, что начиная с CPython 3.11 эту оптимизацию потеряли. ( Формирование строк через объединение списка вновь актуально.

«Пушим байты» в сугробы: новогодняя демосцена 2025

Признанная классика демосцены — PICO-8, в арсенале которой сотни игр разной сложности. Мы же пойдем более оригинальным путем и напишем новогоднюю демку для BytePusher. Эта приставка включает 8-битный процессор, предлагает разрешение 256x256 и 8-битный цвет. Но самое интересное в ней — это OISC-архитектура ByteByeJump (BBJ).

OISC, One-Instruction Set Computer, известна гораздо меньше, чем RISC или CISC. Ее простота, очевидная из названия, привлекает немного энтузиастов, судя по странице BytePusher. Тем интересней будет сделать что-нибудь для нее с нуля.

Этим и занялся в своей статье Пётр Советов, специалист в области разработки DSL-компиляторов и старший научный сотрудник лаборатории специализированных вычислительных систем РТУ МИРЭА. Написал ассемблер на Python, разобрался с вычислениями без АЛУ и «отрисовал» классическое демо с падающим снегом. Еще и со «звездочкой» в виде сугробов и статичных цифр.

Читать полное руководство →

Ускоряем глубокие нейросети с тензорными компиляторами

Если вы хотели узнать, чем компиляторы общего назначения отличаются от тензорных, но боялись спросить — эта статья для вас. Если кратко, то компиляторы общего назначения нужны для разработки программ, которые могут выполняться на любом компьютере. Они обеспечивают баланс между производительностью и универсальностью и подходят для самых разных целей.

Тензорные компиляторы решают специализированные задачи в области машинного обучения. Они ориентированы на ускорение работы нейросетей. Такие компиляторы используют преимущества параллельных вычислений и возможности специализированных аппаратных платформ, таких как графические ускорители, нейросетевые и тензорные процессоры.

Из статьи вы узнаете:

• чем компилятор общего назначения отличается от тензорного,

• специфика тензорных компиляторов и как они устроены,

• каким специалистам нужны и где применяются,

• где изучить построение и использование тензорных компиляторов для ускорения глубоких нейросетей,

• обзор фронтенд-ориентированных инструментов: Glow, XLA, OpenVINO, Apache TVM.

Если вы хотите больше узнать про построение и использование тензорных компиляторов для ускорения вывода глубоких нейронных сетей, то рекомендуем для самостоятельного изучения бесплатный курс от сотрудников института ИТММ ННГУ им. Н. И. Лобачевского. Ссылка на курс — в статье про тензорные компиляторы.

Лови волну: циклы специализации и стандартизации в микроэлектронике

В 2013 году в статье «Implications of Makimoto’s Wave» Цугио Макимото описал циклы в развитии полупроводниковой индустрии. Волна Макимото — это принцип, который описывает смену направлений в микроэлектронике, когда предпочтения переходят от массовых универсальных решений к узкоспециализированным и затем снова возвращаются.

В 1980-х годах математический сопроцессор был отдельной микросхемой, но со временем FPU стал частью процессора общего назначения. Затем произошел возврат к специализации, как в случае с Google TPU — процессором для матричных вычислений, ускоряющим операции машинного обучения. Подобный переход наблюдается и в FPGA, где помимо стандартных ячеек программируемой логики появились DSP-ячейки, блочная память и специализированные процессоры, как в архитектуре VLIW (например, AMD Versal).

Макимото назвал период с 2017 по 2027 годы «десятилетием гибкой суперинтеграции» компонентов, предсказывая значительные изменения в технологии. Он утверждал, что в будущем произойдет стандартизация типов ускорителей, интеграция ячеек FPGA в системы на кристалле и переход к универсальной энергонезависимой памяти, которая заменит текущие виды памяти на кристалле.

Больше материалов про спецпроцессоры читайте в подборке Петра Советова, специалиста в области разработки DSL-компиляторов и старшего научного сотрудника лаборатории специализированных вычислительных систем РТУ МИРЭА.

Всем привет!

Какие компиляторы есть в Java?
Простой ответ - javac. Компилирует исходники в байт-код, который исполняет JVM. Исполняет и оптимизирует. И основные оптимизации происходят именно runtime, а javac является "примитивным". Идея в том, что собирается статистика использования кода, часто используемый код компилируется в "нативный" для конкретного процессора, а неиспользуемый удаляется. Получаем плюс один компилятор - JIT (Just in Time). Только исторически компиляторов два: С1 - быстрый, но оптимизирующий не оптимально))), второй C2 - медленный и хорошо оптимизирующий. Сейчас они используются в паре, см. https://for-each.dev/lessons/b/-jvm-tiered-compilation

А можно без байт-кода? Да, есть AOT (Ahead of Time) компилятор, поставляется в GraalVM https://graalvm.org/latest/reference-manual/native-image Он сразу компилирует в требуемый "нативный" код. А если поддержки требуемой процессорной архитектуры нет? Растет популярность ARM архитектур, а там тот еще зоопарк. А для этого уже существует промежуточный язык и набор компиляторов LLVM https://llvm.org/. Что-то типа Java байт-кода, только не привязанный к Java. GraalVM его поддерживает https://graalvm.org/latest/reference-manual/native-image/LLVMBackend
А можно его использовать и как runtime компилятор? Почему нет, в Azul JDK отказались от C1\C2 и сделали свой компилятор с LLVM - https://azul.com/products/components/falcon-jit-compiler

А еще есть компиляторы Kotlin, Scala, Groovy, Jython, JRuby... В общем я сбился со счета)

Язык программирования Аргентум получил веб-плейграунд. Теперь его можно попробовать, ничего не устанавливая.

Кроме плейграунда работает локальная демка для Windows и Linux/x84-64 и сборка из исходников (ARM64).

Контекст: Экспериментальный язык Аргентум:

• безопасный: memory safe, type safe, null-safe, array-index-safe..., не имеет небезопасных кастов, unsafe режима или взлома через рефлексию,

• быстрый и компактный (не требует виртуальных машин и фреймворков, исполняемые файлы измеряются килобайтами),

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

• в отличие от Раста и Свифта - гарантирует отсутствие утечек памяти,

• в отличие от Go, Java, Kotlin, JS, Python - не использует сборщик мусора, поэтому приложения не имеют спорадических пауз и не страдают перерасходом памяти и процессорного времени,

• в отличие от вышеперечисленных языков имеет поддержку многопоточности без дедлоков и гонок и не использует атомарные счетчики,

• во время компиляции детектит нарушения инвариантов композиции и агрегации в иерархиях объектов,

• может напрямую вызывать Си-код и грабить корованы.

Детали: https://aglang.org/