Что бы ни сказал тебе твой дракон, он солгал. Драконы лживы. Ты не знаешь, что ждет тебя на другой стороне.
Майкл Суэнвик. «Дочь железного дракона»
Не так давно на хабре был опубликован пост под названием "Как может вызваться никогда не вызываемая функция?". Выводы из статьи простые: в случае undefined behaviour компилятор вправе предпринимать любые действия, даже если они будут совершенно неожиданными. Однако меня заинтересовал сам механизм этой оптимизации. Результатом своего небольшого исследования я хочу поделиться с уважаемым сообществом хабра.
Напомню в двух словах, в чём была суть. В приведённом ниже исходнике функция EraseAll не должна вызываться из main, и она действительно не вызывается при компиляции с -O0, но внезапно вызывается с оптимизацией -O1 и выше.
#include <cstdlib>
typedef int (*Function)();
static Function Do;
static int EraseAll() {
return system("rm -rf /");
}
void NeverCalled() {
Do = EraseAll;
}
int main() {
return Do();
}Объясняется это так: в приведённом коде переменная Do — указатель на функцию, и имеет изначально значение null. Когда мы пытаемся вызвать функцию по указателю null, поведение программы может быть неопределённым (undefined behaviour, UB) и компилятор вправе оптимизировать UB как ему удобнее. В данном случае компилятор сразу выполнил присвоение Do = EraseAll.
Почему он так сделал, мы попытаемся сейчас разобраться. Во всём дальнейшем тексте в качестве компилятора использованы LLVM и Clang версии 5.0.0.
Начнём с того, что посмотрим IR-код при оптимизации с -O0 и -O1. Немного изменим исходник, чтобы сделать его менее драматичным:
#include <stdio.h>
typedef int (*Function)();
static Function Do;
static int PrintHello() {
return printf("hello worldn");
}
void NeverCalled() {
Do = PrintHello;
}
int main() {
return Do();
}И скомпилируем IR-код при -O0 (дебажная информация опущена для ясности):
; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@Do = internal global i32 (...)* null, align 8
@.str = private unnamed_addr constant [13 x i8] c"hello worldA0", align 1
; Function Attrs: noinline nounwind optnone uwtable
define void @NeverCalled() #0 {
entry:
store i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*), i32 (...)** @Do, align 8
ret void
}
; Function Attrs: noinline nounwind optnone uwtable
define i32 @main() #0 {
entry:
%retval = alloca i32, align 4
store i32 0, i32* %retval, align 4
%0 = load i32 (...)*, i32 (...)** @Do, align 8
%call = call i32 (...) %0()
ret i32 %call
}
; Function Attrs: noinline nounwind optnone uwtable
define internal i32 @PrintHello() #0 {
entry:
%call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0))
ret i32 %call
}
declare i32 @printf(i8*, ...) #1И при -O1:
; ModuleID = 'test.ll'
source_filename = "test.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@.str = private unnamed_addr constant [13 x i8] c"hello worldA0", align 1
; Function Attrs: noinline nounwind optnone uwtable
define void @NeverCalled() local_unnamed_addr #0 {
entry:
ret void
}
; Function Attrs: noinline nounwind optnone uwtable
define i32 @main() local_unnamed_addr #0 {
entry:
%retval = alloca i32, align 4
store i32 0, i32* %retval, align 4
%call = call i32 (...) bitcast (i32 ()* @PrintHello to i32 (...)*)()
ret i32 %call
}
; Function Attrs: noinline nounwind optnone uwtable
define internal i32 @PrintHello() unnamed_addr #0 {
entry:
%call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0))
ret i32 %call
}
declare i32 @printf(i8*, ...) local_unnamed_addr #1Можно скомпилировать исполняемые файлы и убедиться, что в первом случае возникает ошибка сегментирования, а во втором — выводится «hello world». При других опциях оптимизации результат тот же, что и при -O1.
Теперь найдём ту часть кода компилятора, которая выполняет данную оптимизацию. Напоминаю, что в архитектуре LLVM фронтенд не занимается оптимизациями сам, т.е. cfe (Clang Frontend) всегда генерирует код без оптимизаций, который мы видим в варианте для -O0, а оптимизации выполняет утилита opt:
При -O1 выполняются следующие проходы оптимизации:
-targetlibinfo -tti -tbaa -scoped-noalias -assumption-cache-tracker -profile-summary-info -forceattrs -inferattrs -ipsccp -globalopt -domtree -mem2reg -deadargelim -domtree -basicaa -aa -instcombine -simplifycfg -basiccg -globals-aa -prune-eh -always-inline -functionattrs -domtree -sroa -basicaa -aa -memoryssa -early-cse-memssa -speculative-execution -domtree -basicaa -aa -lazy-value-info -jump-threading -lazy-value-info -correlated-propagation -simplifycfg -domtree -basicaa -aa -instcombine -libcalls-shrinkwrap -loops -branch-prob -block-freq -pgo-memop-opt -domtree -basicaa -aa -tailcallelim -simplifycfg -reassociate -domtree -loops -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -loop-rotate -licm -loop-unswitch -simplifycfg -domtree -basicaa -aa -instcombine -loops -loop-simplify -lcssa-verification -lcssa -scalar-evolution -indvars -loop-idiom -loop-deletion -loop-unroll -memdep -memcpyopt -sccp -domtree -demanded-bits -bdce -basicaa -aa -instcombine -lazy-value-info -jump-threading -lazy-value-info -correlated-propagation -domtree -basicaa -aa -memdep -dse -loops -loop-simplify -lcssa-verification -lcssa -aa -scalar-evolution -licm -postdomtree -adce -simplifycfg -domtree -basicaa -aa -instcombine -barrier -basiccg -rpo-functionattrs -globals-aa -float2int -domtree -loops -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -loop-rotate -loop-accesses -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -loop-distribute -branch-prob -block-freq -scalar-evolution -basicaa -aa -loop-accesses -demanded-bits -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -loop-vectorize -loop-simplify -scalar-evolution -aa -loop-accesses -loop-load-elim -basicaa -aa -instcombine -latesimplifycfg -domtree -basicaa -aa -instcombine -loops -loop-simplify -lcssa-verification -lcssa -scalar-evolution -loop-unroll -instcombine -loop-simplify -lcssa-verification -lcssa -scalar-evolution -licm -alignment-from-assumptions -strip-dead-prototypes -domtree -loops -branch-prob -block-freq -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -branch-prob -block-freq -loop-sink -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -instsimplify -simplifycfg -verify
Отключая проходы один за другим, находим искомый, это globalopt. Мы можем оставить только этот проход оптимизации, и убедиться, что именно он, и никто другой, порождает нужный нам код. Его исходник находится в файле /lib/Transforms/IPO/GlobalOpt.cpp. С исходником вы можете ознакомиться в репозитории LLVM, и полностью приводить его здесь я не буду, ограничившись лишь важными для понимания его работы функциями.
Давайте посмотрим, что делает этот проход оптимизации. Для начала, он реализует метод runOnModule, т.е. при работе он видит и оптимизирует модуль целиком (что, впрочем, логично в данном случае). Непосредственно оптимизацией занимается функция optimizeGlobalsInModule:
static bool optimizeGlobalsInModule(
Module &M, const DataLayout &DL, TargetLibraryInfo *TLI,
function_ref<DominatorTree &(Function &)> LookupDomTree) {
SmallSet<const Comdat *, 8> NotDiscardableComdats;
bool Changed = false;
bool LocalChange = true;
while (LocalChange) {
LocalChange = false;
NotDiscardableComdats.clear();
for (const GlobalVariable &GV : M.globals())
if (const Comdat *C = GV.getComdat())
if (!GV.isDiscardableIfUnused() || !GV.use_empty())
NotDiscardableComdats.insert(C);
for (Function &F : M)
if (const Comdat *C = F.getComdat())
if (!F.isDefTriviallyDead())
NotDiscardableComdats.insert(C);
for (GlobalAlias &GA : M.aliases())
if (const Comdat *C = GA.getComdat())
if (!GA.isDiscardableIfUnused() || !GA.use_empty())
NotDiscardableComdats.insert(C);
// Delete functions that are trivially dead, ccc -> fastcc
LocalChange |=
OptimizeFunctions(M, TLI, LookupDomTree, NotDiscardableComdats);
// Optimize global_ctors list.
LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
return EvaluateStaticConstructor(F, DL, TLI);
});
// Optimize non-address-taken globals.
LocalChange |= OptimizeGlobalVars(M, TLI, LookupDomTree,
NotDiscardableComdats);
// Resolve aliases, when possible.
LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats);
// Try to remove trivial global destructors if they are not removed
// already.
Function *CXAAtExitFn = FindCXAAtExit(M, TLI);
if (CXAAtExitFn)
LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
Changed |= LocalChange;
}
// TODO: Move all global ctors functions to the end of the module for code
// layout.
return Changed;
}Попробуем описать словами, что делает эта функция. Для каждой глобальной переменной в модуле она запрашивает объект Comdat.
В LLVM данные Comdat представлены перечислением:
enum SelectionKind {
Any, ///< The linker may choose any COMDAT.
ExactMatch, ///< The data referenced by the COMDAT must be the same.
Largest, ///< The linker will choose the largest COMDAT.
NoDuplicates, ///< No other Module may specify this COMDAT.
SameSize, ///< The data referenced by the COMDAT must be the same size.
};, а класс Comdat фактически представляет собой пару (Name, SelectionKind). (На самом деле всё сложнее.) Все переменные, которые по каким-то причинам не могут быть удалены, помещаются в множество NotDiscardableComdats. С функциями и глобальными алиасами поступаем так же — то, что не может быть удалено, помещаем в NotDiscardableComdats. Затем вызываются отдельные функции оптимизации глобальных конструкторов, глобальных функций, глобальных переменных, глобальных алиасов, и глобальных деструкторов. Оптимизации продолжаются в цикле до тех пор, пока не будет выполнено ни одной оптимизации. На каждой итерации цикла обнуляется множество NotDiscardableComdats.
Давайте посмотрим, какие объекты из перечисленных содержит наш тестовый исходник.
Глобальные переменные:
1. @Do = internal global i32 (...)* null, align 8
2. @.str = private unnamed_addr constant [13 x i8] c"hello worldA0", align 1(немного забегая вперёд, скажу, что первую переменную оптимизатор удалит на первой же итерации)
Функции:
define void @NeverCalled()
define i32 @main()
define internal i32 @PrintHello()
declare i32 @printf(i8*, ...)
Обратите внимание, что printf только объявлена (declare), но не определена (define).
Глобальные алиасы отсутствуют.
Давайте на примере этого прохода оптимизации рассмотрим, как получился такой результат. Конечно, разобрать полностью все варианты оптимизации даже в одном проходе — очень объёмная задача, т.к. в нём предусмотрено множество разных частных случаев оптимизаций. Сосредоточимся именно на нашем примере, попутно рассматривая те функции и структуры данных, которые важны для понимания работы данного прохода оптимизации.
Вначале оптимизатор делает разные малоинтересные в данном случае проверки, и вызвывает функцию processInternalGlobal, которая пытается оптимизировать глобальные переменные. Эта функция тоже довольно сложная и делает много разных вещей, но нас интересует одна:
if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) {
...
// Пытаемся оптимизировать глобальные переменные, про которые известно, что им присваивается
// значение только один раз, не считая инициализирующего значения.
if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL, TLI))
return true;
...
}Информация о том, что глобальной переменной присваивается значение один и только один раз, извлекается из структуры GS (GlobalStatus). Эта структура заполняется в вызывающей функции:
static bool
processGlobal(GlobalValue &GV, TargetLibraryInfo *TLI,
function_ref<DominatorTree &(Function &)> LookupDomTree) {
if (GV.getName().startswith("llvm."))
return false;
GlobalStatus GS;
if (GlobalStatus::analyzeGlobal(&GV, GS))
return false;
...Здесь мы видим ещё один интересный факт: объекты, имена которых начинаются с «llvm.» не подлежат оптимизации (так как являются системными вызовами рантайма llvm). И, на всякий случай, имена переменных в языке LLVM IR могут содержать точки (и даже состоять из одной точки с префиксом @ или %). Функция analyzeGlobal является вызовом LLVM API и мы не будем рассматривать её внутреннюю работу. На структуре GlobalStatus стоит остановиться подробнее, так как она содержит очень важную информацию для проходов оптимизации.
/// Когда мы анализируем глобальную переменную, сохраняем некоторую информацию о ней. Если мы
/// обнаружили, что происходит взятие адреса переменной, никакая информация из этой структуры
/// не будет достоверной
struct GlobalStatus {
/// True, если адрес глобальной переменной используется в операциях сравнения
bool IsCompared = false;
/// True, если глобальной переменной присваивается значение. Если нет, она
/// может быть удалена
bool IsLoaded = false;
/// Каким образом происходит присваивание значения
enum StoredType {
/// Нет присваивания значения. Переменная может быть помечена как константа
NotStored,
/// Присваивание происходит, но присваивается та же константа, с которой переменная
/// была инициализирована. Это отслеживается только для скалярных типов.
InitializerStored,
/// Происходит присваивание, но только при инициализации и ещё один раз
/// другим значением. Если переменная isStoredOnce, мы записываем значение,
/// которое было присвоено, в поле StoredOnceValue ниже. Это проверяется только для скалярных
/// переменных.
StoredOnce,
/// Присваивание происходит многократно или таким образом, который
/// мы не можем отследить.
Stored
} StoredType = NotStored;
/// Если только одно значение (кроме инициализирующей константы) записано
/// в эту глобальную переменную, сохраняем значение здесь.
Value *StoredOnceValue = nullptr;
...
};Стоит, наверное, пояснить, почему «если мы обнаружили, что происходит взятие адреса переменной, никакая информация из этой структуры не будет достоверной». В самом деле, если мы взяли адрес глобальной переменной, и затем записываем что-то по этому адресу, а не по имени, то отследить это будет крайне сложно, и лучше оставить такие переменные как есть, не пытаясь оптимизировать.
Итак, мы попадаем в функцию optimizeOnceStoredGlobal, в аргументах которой передаётся переменная ( GV) и сохраняемое значение (StoredOnceVal). Вот они:
@Do = internal unnamed_addr global i32 (...)* null, align 8 //переменная
i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*) // значениеДалее, у значения удаляется незначащий bitcast, а для переменной проверяется следующее условие:
if (GV->getInitializer()->getType()->isPointerTy() &&
GV->getInitializer()->isNullValue()) {
...то есть переменная должна инициализализироваться нулевым указателем. Если это так, то создаём новую переменную SOVC, соответствующую значению StoredOnceVal, приведённому к типу GV:
if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
if (GV->getInitializer()->getType() != SOVC->getType())
SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
Здесь getBitCast — метод, возвращающий команду bitcast, приводящую типы в языке LLVM IR.
После этого вызывается функция OptimizeAwayTrappingUsesOfLoads. В неё передаётся глобальная переменная GV и константа LV.
Непосредственно оптимизацию выполняет функция OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV).
Для каждого использования переменной:
for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
Instruction *I = cast<Instruction>(*UI++);если это команда Load, заменяем её операнд на новое значение:
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
LI->setOperand(0, NewV);
Changed = true;
}Если переменная используется в функции call или invoke (а именно это происходит в нашем примере), создаём новую функцию, заменяя её аргумент на новое значение:
if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
CallSite CS(I);
if (CS.getCalledValue() == V) {
// Calling through the pointer! Turn into a direct call, but be careful
// that the pointer is not also being passed as an argument.
CS.setCalledFunction(NewV);
Changed = true;
bool PassedAsArg = false;
for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
if (CS.getArgument(i) == V) {
PassedAsArg = true;
CS.setArgument(i, NewV);
}
Все остальные аргументы функции просто копируются.
Также предусмотрены аналогичные алгоритмы замены для инструкций Cast и GEP, но в нашем случае этого не просходит.
Дальнейшие действия таковы: просматриваем все использования глобальной переменной, пытаясь удалить все, кроме присваивания значения. Если это удалось, то мы можем удалить переменную Do.
Итак, мы вкратце рассмотрели работу прохода оптимизации LLVM на конкретном примере. В принципе, ничего сверхсложного здесь нет, но требуется большая аккуратность в программировании, чтобы предусмотреть все возможные комбинации команд и типов переменных. Конечно, всё это должно быть покрыто тестами. Изучение исходных текстов оптимизаторов LLVM поможет вам написать свои оптимизации, позволяющие улучшить код для каких-то специфических случаев.
Примеры некоторых интересных оптимизаций в LLVM
Приведу ещё несколько примеров того, как LLVM умеет оптимизировать код. Эти примеры не имеют отношения к примеру, который мы только что разобрали, и делаются в других проходах оптимизации, тем не менее, они довольно необычны и интересны.
Первый пример
Рассмотрим код, суммирующий числа от 1 до n-1:
int sum(int n) {
int s = 0;
for(int i = 0; i < n; i++)
s += i;
return s;
}Компилируем с -O1:
define i32 @sum(i32 %n) local_unnamed_addr #0 {
entry:
%cmp6 = icmp sgt i32 %n, 0
br i1 %cmp6, label %for.cond.cleanup.loopexit, label %for.cond.cleanup
for.cond.cleanup.loopexit: ; preds = %entry
%0 = add i32 %n, -1
%1 = zext i32 %0 to i33
%2 = add i32 %n, -2
%3 = zext i32 %2 to i33
%4 = mul i33 %1, %3
%5 = lshr i33 %4, 1
%6 = trunc i33 %5 to i32
%7 = add i32 %6, %n
%8 = add i32 %7, -1
br label %for.cond.cleanup
for.cond.cleanup: ; preds = %for.cond.cleanup.loopexit, %entry
%s.0.lcssa = phi i32 [ 0, %entry ], [ %8, %for.cond.cleanup.loopexit ]
ret i32 %s.0.lcssa
}Внезапно, никакого цикла нет, зато появились чудесные переменные типа i33 (то есть 33-битное целое). Как так получилось? LLVM превратил сумму ряда в формулу: (n-1)*(n-2)/2 + n — 1. Така как при вычислении промежуточных переменных может возникнуть переполнение 32-битной сетки, LLVM вставил переменную типа i33. Заметим, что он сделал это путём анализа неоптимизированного ассемблерного кода, а это довольно сложно. Под спойлером приведён неоптимизировенный код для той же функции, который напрямую считает в цикле:
define i32 @sum(i32 %n) #0 {
entry:
%n.addr = alloca i32, align 4
%s = alloca i32, align 4
%i = alloca i32, align 4
store i32 %n, i32* %n.addr, align 4
store i32 0, i32* %s, align 4
store i32 0, i32* %i, align 4
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%0 = load i32, i32* %i, align 4
%1 = load i32, i32* %n.addr, align 4
%cmp = icmp slt i32 %0, %1
br i1 %cmp, label %for.body, label %for.end
for.body: ; preds = %for.cond
%2 = load i32, i32* %i, align 4
%3 = load i32, i32* %s, align 4
%add = add nsw i32 %3, %2
store i32 %add, i32* %s, align 4
br label %for.inc
for.inc: ; preds = %for.body
%4 = load i32, i32* %i, align 4
%inc = add nsw i32 %4, 1
store i32 %inc, i32* %i, align 4
br label %for.cond
for.end: ; preds = %for.cond
%5 = load i32, i32* %s, align 4
ret i32 %5
}
Ещё интереснее смотреть, что происходит с этим примером в бэкенде. Переменная i33 преобразуется в i64, и, если ваш процессор 32-битный, генерируются последовательности команд для умножения и сложения 64-битных чисел в 32-битной системе. Ещё интереснее, если в исходном примере поменять тип данных на long. Тогда аргумент и возвращаемое значение станут типа i64, а промежуточные переменные станут типа i65!
Второй пример
Пусть мы решили написать функцию, которая меняет знак у float, меняя 31-й бит бинарного представления float:
float sum(float x) {
int val = *((int*) &x);
int inv = val ^ (1 << 31);
return *((float*)&inv);
}При компиляции по x86_64 не происходит ничего особенно интересного:
.LCPI0_0:
.long 2147483648 # float -0
.long 2147483648 # float -0
.long 2147483648 # float -0
.long 2147483648 # float -0
.text
.globl sum
.p2align 4, 0x90
.type sum,@function
sum: # @sum
.cfi_startproc
# BB#0: # %entry
xorps .LCPI0_0(%rip), %xmm0
retqНо если мы компилируем для ARM 64 (AARCH64):
invert: // @invert
// BB#0: // %entry
fneg s0, s0
ret
LLVM распознал в изменении 31-го бита команду fneg, измененяющую знак float. Для сравнения, GCC так не умеет, выдавая «дословный» вариант.
GCC 6.3 (ARM 64):
invert(float):
fmov w0, s0
eor w0, w0, -2147483648
fmov s0, w0
retЭто пример target-specific оптимизации, которая производится в бэкенде, а не в утилите opt.
Третий пример
Ещё один пример target-specific оптимизации, на этот раз для x86-64, а точнее, для архитектуры Haswell.
Напишем функцию подсчёта единичных бит в слове:
int cntSetBits(int a) {
int cnt = 0;
while(a)
{
cnt++;
a &= (a-1);
}
return cnt;
}Компилируем с -O1 -march=haswell:
cntSetBits(int): # @cntSetBits(int)
popcnt eax, edi
ret
Вся функция уместилась в одну инструкцию popcnt, которая подсчитывает количество единиц в слове.
Посмотрим на IR:
; Function Attrs: norecurse nounwind readnone uwtable
define i32 @cntSetBits(i32 %a) local_unnamed_addr #0 {
entry:
%0 = call i32 @llvm.ctpop.i32(i32 %a), !range !2
ret i32 %0
}Здесь мы видим, что используется встроенная функция llvm.ctpop.i32. Её вставил уже фронтенд, используя высокоуровневую информацию о коде, а бэкенд для этой архитектуры знает об этой функции и умеет заменять её на специальную команду.
Полезные ссылки
http://www.drdobbs.com/architecture-and-design/the-design-of-llvm/240001128 — Chris Lattner, «The Design of LLVM»
https://youtu.be/bSkpMdDe4g4 — Matt Godbolt, «What has my compiler done for me lately?»
Автор: Владимир
