Dead code elimination LLVM

Удаление мёртвого кода
В теории компиляторов удалением мёртвого кода называется оптимизация, удаляющая мёртвый код.
Мёртвым кодом называют код, исполнение которого не влияет на вывод программы, все результаты вычисления такого кода являются мёртвыми переменными, то есть переменными, значения которых в дальнейшем в программе не используются.

Примеры мёртвого кода
Переменные, значения которых в дальнейшем в программе не используются.
Данная оптимизация имеет эффект только при взаимодействии с SSA -регистрами.

Преимущества
1) Уменьшение:
размера IR программы
времени работы программы
2) Упрощение кода для дальнейших оптимизаций

DCE & LLVM
В LLVM технология DCE реализована на основе алгоритма Mark & Sweep.
Алгоритм выполняется в 2 этапа:
Фаза расставления меток
Фаза развертки
https://llvm.org/doxygen/DCE_8cpp_source.html

Mark & Sweep
Фаза расставления меток
В первой фазе сборщик мусора находит и помечает все достижимые объекты.
Объект называется достижимым, если на него указывает поле какого-нибудь другого достижимого объекта.

Объекты, к которым программа может обратиться напрямую, называются корнями.
Корни – это локальные переменные на стеке или глобальные переменные, указывающие на объекты в куче.
Mark & Sweep
Фаза расставления меток

Mark & Sweep
Фаза развертки
Во второй фазе выполняется обход всех объектов в куче и освобождение тех из них, которые не помечены как достижимые.
Для корректной работы при следующих сборках алгоритм также обнуляет все пометки о достижимости.

Устранение мертвого кода в LLVM
Объекты, подлежащие удалению:
AllocaInst – выделение памяти в стеке;
LoadInst – чтение из памяти;
GetElementPtrInst – указатели для доступа к элементам массива и структур;
SelectInst – используется для выбора одного значения на основе условия;
ExtractElementInst – извлекает один элемент из значения векторного типа;
InsertElementInst – вставляет один элемент в векторный тип;
ExtractValue – извлекает значение поля-члена из агрегированного значения;
InsertValue – вставляет значение в поле элемента в агрегированном значении;
Бинарные операции
Операции сравнения
Преобразование типов

Устранение мертвого кода в LLVM
Объекты, не подлежащие удалению:
ReturnInst – возвращает значение из функции;
SwitchInst – конструкция Switch;
BranchInst – условный и безусловный переход;
CallInst – вызов функции;
StoreInst – инструкция для хранения в памяти.
LLVM instructions definitions:
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/IR/Instruction.def