LLVMが呼び出されない関数を呼び出すことができるのはなぜですか？

あなたのドラゴンが何を言っても、彼は嘘をついた。 ドラゴンは偽です。 反対側で何があなたを待っているのかわかりません。

マイケル・スワンウィック。 「鉄竜の娘」

少し前、Habréに「 呼び出されなかった関数をどのように呼び出すことができますか？ 」というタイトルの投稿がありました。 この記事からの結論は簡単です。未定義の動作の場合、コンパイラは完全に予期しないものであっても、何らかのアクションを取る権利を持っています。 しかし、私はこの最適化のメカニズムに興味がありました。 ちょっとした研究の結果、評判の良いHabrのコミュニティと共有したいと思います。







ポイントを教えてください。 以下のソースコードでは、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ポインターを使用して関数を呼び出そうとすると、プログラムの動作が未定義（未定義の動作、UB）になる場合があり、コンパイラーはより便利なためUBを最適化する権利があります。 この場合、コンパイラーは割り当てDo = EraseAllを直ちに実行しました。



彼がなぜこれをしたのか、私たちは今それを理解しようとします。 本文全体で、LLVMおよびClangバージョン5.0.0がコンパイラとして使用されます。



まず、-O0および-O1を使用した最適化中のIRコードを見てみましょう。 劇的にならないようにソースを少し変更します。

 #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(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

-O0でIRコードをコンパイルします（明確にするために詳細は省略されています）。

 ; ModuleID = 'test.c' source_filename = "test.c" target datalayout = "em: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 = "em: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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実行可能ファイルをコンパイルして、最初のケースではセグメンテーションエラーが発生し、2番目のケースでは「hello world」が表示されることを確認できます。 他の最適化オプションを使用した場合、結果は-O1と同じです。



これで、この最適化を実行するコンパイラコードの一部が見つかりました。 LLVMアーキテクチャでは、フロントエンドはそれ自体を最適化しない、つまり、 cfe（Clangフロントエンド）は常に最適化なしでコードを生成します。これは-O0のオプションにあり、optユーティリティは最適化を実行します。







-O1では、次の最適化パスが実行されます。





パッセージを1つずつオフにして、目的のパッセージを見つけます。これは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 world\0A\00", align 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

（少し先を見て、オプティマイザーは最初の反復で最初の変数を削除すると言います）



機能：

 define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

printfは宣言（宣言）されるだけで、定義（定義）されないことに注意してください。

グローバルエイリアスはありません。



この最適化パスの例、この結果が得られた方法を見てみましょう。 もちろん、1回のパスですべての最適化オプションを完全に分解することは非常に膨大な作業です。 最適化のさまざまな特殊なケースを提供します。 この最適化パスの動作を理解するために重要な関数とデータ構造を同時に調べながら、例に特に焦点を当てましょう。



この場合、最初にオプティマイザーはさまざまな興味深いチェックを行い、グローバル変数を最適化しようとする関数processInternalGlobalを呼び出します。 この関数も非常に複雑で、多くの異なることを行いますが、私たちはそれに興味があります：

 if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ... //    ,   ,    //    ,    . if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL, TLI)) return true; ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

グローバル変数に値が1回だけ割り当てられるという情報は、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; ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、もう1つの興味深い事実がわかります。名前が「llvm」で始まるオブジェクトです。最適化できません（llvmランタイムのシステムコールであるため）。 また、念のため、LLVM IR言語の変数名にはピリオドを含めることができます（プレフィックス@または％を含む1つのポイントで構成することもできます）。 analyzeGlobal関数はLLVM APIの呼び出しであり、その内部操作は考慮しません。 GlobalStatus構造には最適化パスのための非常に重要な情報が含まれているため、GlobalStatus構造について詳しく説明する価値があります。

 ///     ,     .   /// ,     ,      ///    struct GlobalStatus { /// True,         bool IsCompared = false; /// True,     .  ,  ///    bool IsLoaded = false; ///      enum StoredType { ///   .       NotStored, ///  ,     ,    ///  .      . InitializerStored, ///  ,         ///  .   isStoredOnce,   , ///   ,   StoredOnceValue .      /// . StoredOnce, ///      ,  ///    . Stored } StoredType = NotStored; ///     (  )  ///    ,   . Value *StoredOnceValue = nullptr; ... };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「変数のアドレスが取得されていることがわかった場合、この構造からの情報は信頼できない」という理由を説明する価値があるでしょう。 実際、グローバル変数のアドレスを取得し、名前ではなくそのアドレスに何かを書き留めると、追跡するのが非常に難しくなります。最適化を試みずに、そのような変数をそのままにしておく方が良いでしょう。



したがって、変数（GV）と保存された値（StoredOnceVal）が渡される引数でoptimizeOnceStoredGlobal関数に入ります。 ここにあります：

 @Do = internal unnamed_addr global i32 (...)* null, align 8 // i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*) // 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さらに、値に対して重要でないビットキャストが削除され、変数について次の条件がチェックされます。

  if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、変数はNULLポインターで初期化する必要があります。 その場合、GV型にキャストされたStoredOnceValの値に対応する新しいSOVC変数を作成します。

  if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、getBitCastは、LLVM IRで型をキャストするビットキャストコマンドを返すメソッドです。

その後、OptimizeAwayTrappingUsesOfLoads関数が呼び出されます。 グローバル変数GVと定数LVが渡されます。

最適化は、OptimizeAwayTrappingUsesOfValue関数（値* V、定数* 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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

変数が呼び出しまたは呼び出し関数で使用される場合（つまり、この例ではこれが発生します）、新しい関数を作成し、引数を新しい値に置き換えます。

 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変数を挿入しました。 かなり複雑な最適化されていないアセンブラコードを分析することでこれを行ったことに注意してください。 スポイラーの下には、ループで直接カウントされる同じ関数の最適化されていないコードがあります。





バックエンドでこの例で何が起こるかを見るのはさらに興味深いです。 i33変数はi64に変換され、プロセッサが32ビットの場合、32ビットシステムで64ビット数を乗算およ​​び加算するためのコマンドシーケンスが生成されます。 さらに興味深いのは、元の例でデータ型をlongに変更した場合です。 次に、引数と戻り値はi64型になり、中間変数はi65型になります！

2番目の例

floatの符号を反転し、floatのバイナリ表現の31ビット目を変更する関数を記述することにしたと仮定します。

 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は、fnegコマンドが31ビット目の変更で浮動小数点の符号を変更することを認識しました。 比較のために、GCCは「verbatim」オプションを発行する方法を知りません。

GCC 6.3（ARM 64）：

 invert(float): fmov w0, s0 eor w0, w0, -2147483648 fmov s0, w0 ret
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、ターゲット固有の最適化の例であり、optユーティリティではなくバックエンドで実行されます。



この例について、いくつかの言葉を言う必要があります。 このようなポインターアクションは、厳密なエイリアスルールに違反します。これは、一部のコンパイラーおよび一部のプラットフォーム（実際には、ごく少数の場合）で-strict-aliasingフラグを使用してコンパイルすると、未定義の動作を引き起こす可能性があります。 この例では、gcc4.4.7 -m32 -O2でコンパイルするとエラーが発生し、最新バージョンのgccでは表示されなくなります。 それにもかかわらず、私はリンクのリストにエイリアスの興味深い講義へのリンクを挿入しました。

3番目の例

ターゲット固有の最適化のもう1つの例、今回は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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数全体が1つの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、「最近私のコンパイラは何をしてくれましたか？」

https://youtu.be/ACW-7dktyDk Dmitry Kashitsyn「ローフトロリーバス：LLVMのエイリアシングとベクトル化」