Почему LLVM может вызвать никогда не вызываемую функцию?

    Что бы ни сказал тебе твой дракон, он солгал. Драконы лживы. Ты не знаешь, что ждет тебя на другой стороне.
    Майкл Суэнвик. «Дочь железного дракона»

    Не так давно на Хабре был опубликован пост под названием "Как может вызваться никогда не вызываемая функция?". Выводы из статьи простые: в случае 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 world\n");
    }
    
    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 world\0A\00", 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 world\0A\00", 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.
    Что такое Comdat
    Comdat-секция, это секция в объектном файле, в котой размещаются объекты, которые могут дублироваться в других объектных файлах. Каждый объект имеет информацию для компоновщика, указывающую, что ему следует делать при обнаружении дубликатов. Варианты могут быть следующие: Any — что угодно, ExactMatch — дубликаты должны полностью совпадать, иначе возникает ошибка, Largest — взять объект с наибольшим значением, NoDublicates — не должно быть дубликата, SameSize — дубликаты должны иметь одинаковый размер, иначе возникает ошибка.

    В 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 world\0A\00", 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.

    По поводу этого примера нужно сказать ещё пару слов. Такие действия с указателями нарушают правило strict aliasing, что может привести к неоределённому поведению при компиляции с флагом -strict-aliasing на некоторых компиляторах и на некоторых платформах (на самом деле, в исчезающе малом количестве случаев). Для данного примера ошибка возникает при компиляции с gcc4.4.7 -m32 -O2, и исчезает в более свежих версиях gcc. Тем не менее, я вставил в список ссылок в конце ссылку на интересную лекцию по алиасингу.

    Третий пример


    Ещё один пример 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?»
    https://youtu.be/ACW-7dktyDk Дмитрий Кашицын «Троллейбус из буханки: алиасинг и векторизация в LLVM»
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 21
    • +4
      Спасибо за статью. Вот только написать
      Пусть мы решили написать функцию, которая меняет знак у float, меняя 31-й бит бинарного представления float
      и не сказать о том, что так лучше не делать — может быть чревато.
      • +3
        Если не вдаваться в ккаие-то теоретические дебри стандарта и чисто гипотетические случаи, то это ничем не чревато. Если используется стандарт IEEE754, то эта функция изменит знак числа. Я проверил генерацию кода на gcc и clang для основных платформ (x86 и ARM) и всё компилируется правильно.
        Если вы про gcc4.4.7 -m32 -strict-aliasing, то эта проблема проявляется исключительно в этой конкретной версии компилятора, и нигде более. Вот тут я немного написал про это: 32bit-me.livejournal.com/174869.html
        • +6
          Причем здесь проявляется или не проявляется? Вам ли не понимать, к чему может привести UB в коде. Если флаг -strict-aliasing указан то все, приехали.
          • +2
            Но его можно не указывать!
            На самом деле, для микроконтроллеров и других устройств без fpu операции манипулирования битами могут сильно оптимизировать скорость исполнения, и отказываться от них не следует. Подобные ограничения могут сильно усложнить дело.
            • +4
              Я не предлагаю отказываться полностью. Я предлагаю лишь не замалчивать потенциальные проблемы.

              Мир контроллеров это особый мир, со своими правилами и проблемами, и к нему уж точно не стоит апеллировать в статье на общую тему.

              Те, кому надо выжать из камня максимум, рано или поздно сами придут к битовым операциям, но уже с полным осознанием последствий.
              • 0
                Вставил в статью ссылку на ваше видео по алиасингу.
              • –2
                >> Но его можно не указывать!
                Есть стандартный способ кастить float в его бинарное представление через union. И не надо отключать strict aliasing.
                union { int dst; float src; } x;
                • +2
                  Это гарантируется только и исключительно в GCC — да и там со множеством оговорок.

                  memcpy — наше всё!
                  • –2
                    «Множество оговорок» про доступ к элементам union через указатели так себе аргумент. Ведь union и используется для того чтобы избежать использования указателей.
                    У меня для кастов есть темплейтная функция и проблем с ней не замечено на различных компиляторах и платформах.
                    • +6
                      Ведь union и используется для того чтобы избежать использования указателей.
                      Union — это средство экономии памяти. Точка. Запись в одно поле union'а, а чтение из другого — это неопределённое поведение со всеми вытекащими (вызовом невызываемой фукнции и форматированием винчестера).

                      GCC даёт некоторые, очень ограниченные гарантии, что программа, которая такое делает не сломается сразу же.

                      Вот так:
                      union a_union {
                        int i;
                        double d;
                      };
                      
                      int f() {
                        union a_union t;
                        t.d = 3.0;
                        return t.i;
                      }
                      
                      работает. Вот так:
                      int f() {
                        double d = 3.0;
                        return ((union a_union *) &d)->i;
                      }
                      уже нет.

                      Clang не делает даже этого. Единственный гарантированно работающий способ — это bit_cast (ну или ручная реализация оного через char*).

                      Дискусия на тему как бы это можно было разрешить делать в C++20 без memcpy — всё ещё продолжается.

                      У меня для кастов есть темплейтная функция и проблем с ней не замечено на различных компиляторах и платформах.
                      Вам очень хочется дождаться того, чтобы у заказчика отформатировался случайно винчестер? Дождётесь.

                      Мы говорили с разработчиками clang'а по поводу этого расширенного ипользования union'ов, разрешённого GCC. Их ответ был «ну, мы, по возможности, стараемся не ломать такой код, но если не уследим — поводом срочно выпускать фикс это не будет».

                      Потому и в документации ничего нет.
                    • 0
                      Это гарантируется стандартами C99 и C11. так что для C-кода всё норм, достаточно затребовать поддержку стандарта.
                      • +1
                        Вы «затребовали поддержку стандарта», разработчики компиляторов сказали нет, нет и не будет. Ваш следующий шаг? Нанять других разработчиков и сделать другой компилятор?

                        Если вы работаете с указателями и компилятор «не видит» вашего union'а — то он будет нарушать эту часть стандарта — можете убедиться. А если вы хотите скопировать данные в union, дальше использовать его для преобразования типов, потом скопировать обратно (что работает в GCC и обычно работает в clang) — так проще уж использовать memcpy и построенный поверх него bitcast.

                        Что делать с type punning'ом через union'ы в стандарте C (где он таки действительно определён) — сейчас обсуждается (скорее всего в следующей версии либо сильно обкорнают, либо выкинут), но на практике компиляторы его уже не поддерживают.
              • +6
                Я просто не пойму зачем провоцировать людей на подобное трюкачество? Вот такая функция точно так же будет преобразована в одну инструкцию fneg на тех компиляторах, которые это умеют:

                float negate(float num) {
                    return num * -1;
                }

                Только, в отличие от примера в статье, данная функция:
                • Абсолютно понятна читающему
                • Ни при каких условиях не провоцирует неопределенное поведение
                • Не работает с указателями — больше простора для оптимизации
                • На кривых компиляторах все равно отработает как надо
                • +6
                  В данном случае проще написать
                  return -num;

                  Основные компиляторы для основных платформ с этим справятся, это действительно так. Но в целом, есть случаи, когда нам необходимо сделать преобразование float в его битовое придставление, и работать непосредственно с ним.
                  Код приведен просто для примера, чтобы показать, что компилятор на самом деле довольно умный.
            • +1
              Список оптимизаций для впечатлительных
              -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
              • +1
                А еще никогда не вызываемая функция может вызваться в результате работы LTO. Не используйте LTO если работаете с cuda 8 + msvc14.
                • +2
                  О, если я буду работать с cuda 8 + msvc14, то обязательно это учту :)
                  Кстати, вы могли бы привести пример того, что при этом происходит.
                • +1
                  Отключая проходы один за другим, находим искомый

                  Попробуйте также: https://llvm.org/docs/OptBisect.html

                • 0
                  Не понял, почему автор считает, что неинициализированный указатель должен быть равен null?
                  • +5
                    a variable with static storage duration (3.7.1) or thread storageduration (3.7.2) is zero-initialized (8.6)

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