Фаза 4: Linearizer
Цель: Преобразовать DAG в линейную последовательность инструкций.
Стадия 16: Пост-индексная символика
Стадия кратко
Цель: Полное символическое упрощение после понижения индексов Ключевые паттерны: Все символические правила (140+) Эффект: Финальная чистка перед сериализацией
Что делает: Полное символическое упрощение после понижения индексов.
Зачем это нужно: Теперь, когда индексы стали конкретными целыми (i32/i64), арифметика может полностью упроститься. Это последний шанс вычистить выражения перед линеаризацией.
Паттерн: symbolic
Включает паттерны проталкивания GEP — перенос вычислений адресов через арифметику:
Before: GEP(ADD(arr_a, arr_b), idx)
↓ [Push GEP through ADD]
After: ADD(GEP(arr_a, idx), GEP(arr_b, idx))
Зачем? Даёт возможность параллельного вычисления GEP и может открыть путь для дальнейшей векторизации. (Примечание: паттерн применяется только когда DType у GEP и ALU — НЕ указатели.)
Стадия 17: Pre-Matcher (опциональная)
Стадия кратко
Цель: Бэкенд-специфичные паттерны перед декомпозицией Ключевые паттерны: Специфичные для рендерера Эффект: Аппаратно-специфичные оптимизации
Что делает: Специфичные для рендерера паттерны, применяемые до декомпозиции.
Зачем это нужно: Каждый бэкенд может добавить свои паттерны. Например, DSP-бэкенды используют это для замены общих паттернов на DSP-специфичные SIMD-интринсики. Это позволяет выполнять аппаратно-специфичные оптимизации, не трогая общий пайплайн.
Паттерн: renderer.pre_matcher
Большинству бэкендов (CPU, GPU) это не нужно. Только специализированное железо использует эту стадию.
Примечание: Morok пока не реализует эту стадию. Трейт Renderer имеет методы render(), backend_name() и decompositor(), но поддержки pre_matcher пока нет. Это будущее расширение для DSP и других специализированных бэкендов.
Стадия 18: Декомпозиции
Стадия кратко
Цель: Переписать операции, которые целевое железо не поддерживает Ключевые паттерны: Степени двойки, аппроксимации трансцендентных функций Эффект: Маппинг высокоуровневых операций на аппаратные инструкции
Что делает: Поздние перезаписи для операций, которые целевое устройство не поддерживает.
Зачем это нужно: У железа нет всех операций. Например, у большинства CPU нет прямой инструкции sin. Мы аппроксимируем её через операции, которые существуют (сложение, умножение и т.д.).
Паттерн: symbolic_simple() + get_late_rewrite_patterns()
Примечание: pm_render() и pm_split_ends() не входят в этот объединённый проход — они запускаются отдельно на стадии 19.
| Паттерн | Пример | Когда используется |
|---|---|---|
MOD → AND | x % 8 → x & 7 | Степень двойки в делителе |
MUL → SHL | x * 16 → x << 4 | Степень двойки в множителе |
DIV → SHR | x // 8 → x >> 3 | Степень двойки в делителе |
FDIV → MUL | x / 2.0 → x * 0.5 | Константа в float-делителе |
NEG | x * -1 → NEG(x) | Когда NEG поддерживается |
MULACC | a * b + c → MULACC(a, b, c) | Когда FMA поддерживается |
| Быстрое целочисленное деление | x // 7 → (x * M) >> S | Делитель не степень двойки |
| Законы Де Моргана | (!x) & (!y) → !(x | y) | Булево упрощение (в обе стороны) |
| Отрицания сравнений | !(x < c) → (c-1) < x | Целочисленные сравнения |
Аппроксимации трансцендентных функций (SIN, EXP, LOG и т.д.) реализованы через путь decompositor() (см. ir/src/decompositions/transcendentals.rs).
Morok: optimizer/mod.rs
Стадия 19: Финальная перезапись
Стадия кратко
Цель: Подготовка к линеаризации Ключевые паттерны: Векторизация CONST, разрешение GEP, разделение END Эффект: Чистое представление, готовое к линеаризации
Что делает: Подготовка к линеаризации.
Зачем это нужно: Некоторые паттерны проще применить после декомпозиции. Эта стадия делает финальную чистку перед преобразованием в линейную последовательность.
Паттерн: symbolic_simple() + get_late_rewrite_patterns() + pm_render()
Примечание: extra_matcher и pm_split_ends запускаются отдельно, а не как часть этого объединённого прохода.
Векторизация CONST:
// Make vector constants explicit
CONST(1.0) used as vec4 → VECTORIZE(1.0, 1.0, 1.0, 1.0)
CAT в VECTORIZE (через pm_render):
CAT(a, b, c, d) → VECTORIZE(a, b, c, d)
CAT нельзя отрендерить напрямую; для кодогенерации нужен явный VECTORIZE.
Разрешение GEP: Преобразование оставшихся GEP-операций.
Разделение многодиапазонных END:
// Before: END closing multiple ranges
END(op, [range_a, range_b])
// After: nested single ENDs
END(END(op, range_a), range_b)
extra_matcher: Каждый бэкенд может добавить свои финальные паттерны. Это позволяет выполнять аппаратно-специфичные оптимизации, не трогая общий пайплайн.
Morok: devectorize.rs, linearize/mod.rs, optimizer/mod.rs
Стадия 20: Добавление управления потоком
Стадия кратко
Цель: Построить граф управления потоком и добавить зависимости между RANGE Ключевая концепция: Три типа отношений (вложенные, зависимые, независимые) Эффект: Правильный порядок инструкций
Что делает: Строит граф управления потоком и добавляет зависимости между RANGE.
Зачем это нужно: Операции должны выполняться в корректном порядке. Если загрузка использует значение RANGE, RANGE должен идти первым. Эта стадия отслеживает и обеспечивает эти зависимости.
Паттерн: pm_add_control_flow (bottom-up)
// Analyze which END operations depend on which
END(computation, [RANGE_A]) and END(other_computation, [RANGE_B]) are siblings
→ Creates edge: RANGE_B.src += END(computation)
// Add explicit dependency
RANGE_B waits for RANGE_A to complete
Три типа отношений:
| Отношение | Пример | Значение |
|---|---|---|
| Вложенные | RANGE_A внутри RANGE_B | A должен завершиться до начала B |
| Зависимые | END_A и END_B — сиблинги | END_B должен дождаться END_A (зависимость сиблингов) |
| Независимые | RANGE_X и RANGE_Y не взаимодействуют | Могут выполняться параллельно |
Bottom-up обход гарантирует, что зависимости корректно распространяются от листьев к корням.
Morok: schedule/src/linearize/mod.rs
Стадия 21: Линеаризация
Стадия кратко
Цель: Преобразовать DAG в линейную последовательность инструкций Ключевой алгоритм: Топологическая сортировка с учётом приоритетов Эффект: Корректный порядок выполнения
Что делает: Преобразует DAG в линейную последовательность инструкций через топологическую сортировку с учётом приоритетов.
Зачем это нужно: Структура графа не задаёт порядок выполнения. Нужно развернуть его в линейную последовательность, соблюдая зависимости. Приоритеты обеспечивают осмысленный порядок (определения до использований, загрузки до вычислений, записи после).
Функция: linearize(sink)
| Операция | Приоритет | Зачем |
|---|---|---|
| DEFINE_GLOBAL | -20 | Аргументы должны быть определены первыми |
| DEFINE_VAR | -19 | Переменные должны быть определены первыми |
| DEFINE_LOCAL | -18 | Аллокации первыми |
| DEFINE_REG | -17 | Регистры первыми |
| CONST | -10 | Константы раньше для переиспользования (расширение Morok; в Tinygrad по умолчанию 0) |
| LOAD | -1 | Загрузки до использования |
| END | -5 | Закрывает RANGE |
| STORE | +1 | Записи после вычислений |
| RANGE | +5 | RANGE открываются до использования |
Меньший приоритет = раньше в последовательности. Это гарантирует:
- Определения идут первыми
- Загрузки происходят до вычислений
- Записи происходят последними
- RANGE открываются до содержимого, закрываются после
Порядок по run_count: Операции сортируются в первую очередь по частоте выполнения (run_count), затем по приоритету. Операции с меньшей частотой (вне внутренних циклов) планируются раньше, а операции во внутренних циклах (больший run_count) — позже. Пример: CONST, выполняемый 100 раз, появляется раньше CONST, выполняемого 1M раз.
Вычисление run_count:
run_count = prod(int(r.vmax) + 1 for r in u.ranges)
Это вычисляет, сколько раз операция выполняется, исходя из охватывающих RANGE.
Morok: schedule/src/linearize/mod.rs
Стадия 22: Чистка IF/ENDIF
Стадия кратко
Цель: Финальная чистка линейного списка инструкций Ключевая трансформация: Gated INDEX → IF/STORE/ENDIF Эффект: Поддержка железа без predicated stores
Что делает: Финальная чистка линейного списка инструкций.
Зачем это нужно: Некоторое железо (современные GPU) поддерживает «predicated stores» — запись в память только при истинном условии. Старое железо — нет. Для такого оборачиваем STORE в IF-блок. Эта стадия запускается ТОЛЬКО когда железо не поддерживает predicated stores.
Паттерн: pm_linearize_cleanups (через line_rewrite, а не graph_rewrite)
// Gated INDEX in STORE becomes conditional store
STORE(INDEX(ptr, idx, valid=cond), value)
→ IF(cond) { STORE(INDEX(ptr, idx), value) } ENDIF
Примечание: Эта стадия использует line_rewrite вместо graph_rewrite, потому что работает с уже линеаризованным списком инструкций, а не с DAG.
На этом этапе список инструкций готов к кодогенерации.
Morok: schedule/src/linearize/mod.rs (путь predicated stores)