Julia debug, LLVM (2)

juliaをソースからコンパイルすると、まずはdepsの中に入って行って、関係者達をひたすら 取り揃える事になる。おいらの知らない関係者も多いので、どんな事が得意か聞いてみた。

LLVM        compiler infrastructure.
FemtoLisp   packaged with Julia source, and used to implement the compiler front-end.
libuv       portable, high-performance event-based I/O library
OpenLibm    portable libm library containing elementary math functions.
OpenSpecFun library containing Bessel and error functions of complex arguments.
DSFMT       fast Mersenne Twister pseudorandom number generator library.
OpenBLAS    fast, open, and maintained basic linear algebra subprograms (BLAS) library, based on Kazushige Goto's famous GotoBLAS.
LAPACK      library of linear algebra routines for solving systems of simultaneous linear equations, least-squares solutions of linear systems of equations, eigenvalue problems, and singular value problems.
AMOS        subroutines for computing Bessel and Airy functions.
SuiteSparse library of linear algebra routines for sparse matrices.
ARPACK      collection of subroutines designed to solve large, sparse eigenvalue problems.
FFTW        library for computing fast Fourier transforms very quickly and efficiently.
PCRE        Perl-compatible regular expressions library.
GMP         GNU multiple precision arithmetic library, needed for BigInt support.
MPFR        GNU multiple precision floating point library, needed for arbitrary precision floating point (BigFloat) support.
libgit2     Git linkable library, used by Julia's package manager
utf8proc    library for processing UTF-8 encoded Unicode strings
libosxunwind clone of libunwind, a library that determines the call-chain of a program
Rmath-julia  library for commonly used statistical functions from the R project.

実に多彩なメンバー達が、裏でjuliaを支えている。これなくしてはjuliaの作成も おぼつかなかったであろう。オープンソース様々である。

libuvなんてのはnode.jsとかで採用された 非同期IOとかをサポートしてるらしい。こういう便利なものが有るので、juliaは上の 階層に集中出来るわけね。何から何まで作っていたら疲れてしまいますから。

で、juliaの根幹を成しているのは、前回やったfemtoLispとLLVMだろう。前者で、julia語を 扱い易いASTに変換し、後者でJITとかを実現してるのだろう。

今回は、後者のLLVM(のさわりだけ)を探っていきたいな。LLVMの生まれた背景は、 小島先生が丁寧に解説してくださっている。 第50回 X,MesaそしてLLVM[その1]

LLVMとClang

我がFreeBSDはデフォルトC語コンパイラーが、gccからClangに変わった。そういう訳で ccとclangは同義語になっている。

$ ls -i /usr/bin/cc
1456663 /usr/bin/cc*
$ find /usr/bin -inum 1456663
/usr/bin/clang
/usr/bin/clang-cpp
/usr/bin/cc
/usr/bin/cpp
/usr/bin/clang++
/usr/bin/CC
/usr/bin/c++

実に色々な名前が付けられているな。cフラフラまで面倒を見てくれるのね。 それはいいんだけど、どうした事かllvm系が標準では入っていない。

それじゃパッケージから持ってくればと思うと、入れた積もりが無いのに 既に入っている。

ちと気味が悪いので、誰がllvmを欲していたか探ってみた。

$ pkg info -d llvm36
llvm36-3.6.2_2:
        python27-2.7.11_1
        perl5-5.20.3_8
        libedit-3.1.20150325_1

お馴染みのpythonとかperlが欲しがって、一緒に入ってきたものみたいだ。 噂では、Haskell(ghc)も、LLVMが使えるらしいけど、

$ pkg info ghc
  :
Comment        : Compiler for the functional language Haskell
Options        :
        BCLANG         : off
        DOCS           : on
        DYNAMIC        : on
        GCC            : on
        LLVM           : off
        PCLANG         : off
        PROFILE        : on

LLVMの採用は見送って、代わりにgcc485が採用されてた。ghcは多分Linux中心に開発 されてるだろうから、主コンパイラーはずっとgccだろうね。

で、clangとllvmのバージョンがちぐはぐ状態。これじゃ実験にさしさわりが有るだろうと 思って、clang36を追加で入れてあげたよ。 まずは試運転。

$ clang -v fact.c
clang version 3.6.2 (tags/RELEASE_362/final)
Target: i386-portbld-freebsd10.1
Thread model: posix
 "/usr/local/llvm36/bin/clang" -cc1 -triple i386-portbld-freebsd10.1 -emit-obj -mrelax-all -disable-free -disable-llvm-verifier -main-file-name fact.c -mrelocation-model static -mthread-model posix -mdisable-fp-elim -masm-verbose -mconstructor-aliases -target-cpu i486 -target-linker-version 2.17.50 -v -dwarf-column-info -resource-dir /usr/local/llvm36/bin/../lib/clang/3.6.2 -fdebug-compilation-dir /usr/home/sakae/t -ferror-limit 19 -fmessage-length 80 -mstackrealign -fobjc-runtime=gnustep -fdiagnostics-show-option -fcolor-diagnostics -o /tmp/fact-b7e9e0.o -x c fact.c
clang -cc1 version 3.6.2 based upon LLVM 3.6.2 default target i386-portbld-freebsd10.1
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/llvm36/bin/../lib/clang/3.6.2/include
 /usr/include
End of search list.
 "/usr/local/bin/ld" --eh-frame-hdr -dynamic-linker /libexec/ld-elf.so.1 --hash-style=both --enable-new-dtags -m elf_i386_fbsd -o a.out /usr/lib/crt1.o /usr/lib/crti.o /usr/lib/crtbegin.o -L/usr/lib /tmp/fact-b7e9e0.o -lgcc --as-needed -lgcc_s --no-as-needed -lc -lgcc --as-needed -lgcc_s --no-as-needed /usr/lib/crtend.o /usr/lib/crtn.o

コンパイルまでがclangの領分で、リンクは備え付けのやつを使ってるっぽい。 ここまでは、普通のC語の範疇。

clangにオプションを与えると、llvmのアセンブラーを出力出来るそうな。

$ clang -S -emit-llvm fact.c
$ ls
a.out*          fact.c          fact.ll

コマンドオプションは、--helpで確認出来る。上記の引数中 -emit-llvmって、直訳すれば llvm語を放出するって意味だな。emitって単語でピーンときたのさ。

エミッターで放出、コレクターで収集、間に入るはベース、そうトランジスターの 電極の名前そのものじゃないですか。もっと昔の球なら、電極をフィラメントで暖めて、 自由電子を放出。サーサー電子さん寄っといでって事で、プラスの高電圧をかけたプレート、 その間で電子の通りぬけを拒むのは、電子の嫌いなマイナス電圧を加えたグリッド。 これが真空管の基本、3極菅。

上記の3極菅のプレートとグリッド間の間にスクリーングリッドというのを設けここに正電圧を加えると 電子が加速されるので、プレート電圧が低くても性能が出る。そしてこの電極が制御用 グリッドとプレート間のシールドの役目も果たしてくれるので、高周波特性が上がる。

更に、プレートに電子が衝突して反射するのを防ぐために、 サプレッサーグリッドとかを付け加えると、高級な5極菅になったりする。懐かしいな。

話が逸れた。emitするとC語をllvm語(仮想マシン用アセンブラー)に変換したfact.llが出て来る。

@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1

define i32 @factorial(i32 %n) #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 %n, i32* %2, align 4
  %3 = load i32* %2, align 4
  %4 = icmp sgt i32 %3, 0
  br i1 %4, label %5, label %11

; <label>:5                                       ; preds = %0
  %6 = load i32* %2, align 4
  %7 = load i32* %2, align 4
  %8 = sub nsw i32 %7, 1
  %9 = call i32 @factorial(i32 %8)
  %10 = mul nsw i32 %6, %9
  store i32 %10, i32* %1
  br label %12

; <label>:11                                      ; preds = %0
  store i32 1, i32* %1
  br label %12

; <label>:12                                      ; preds = %11, %5
  %13 = load i32* %1
  ret i32 %13
}

define i32 @main() #0 {
  %1 = call i32 @factorial(i32 10)
  %2 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i32 0, i32 0), i32 %1)
  ret i32 0
}

declare i32 @printf(i8*, ...) #1

clangが放出したコードから、主要な部分だけを抜き出した。頭に@マークが付くのは、 グローバル関数なり変数だ。%が付くのはローカル変数。;は勿論、コメント。

左変数には一度しか代入されない(しない)関数言語っぽい仕様になってて、これをSAA形式 とか言うそうな。こうする事で、最適化がやり易くなるとか。

こうして出来たアセンブリコードは、lliって言うllvmのインタープリタで実行出来る。

$ lli fact.ll
3628800
$ ./a.out
3628800

そして、アセンブリコードをコンパイルして、ネイティブ語(この場合は、糞石用の アセンブリコード) に変換出来る。

$ llc fact.ll
$ lv fact.s
        .text
        .file   "fact.ll"
        .globl  factorial
        .align  16, 0x90
        .type   factorial,@function
factorial:                              # @factorial
# BB#0:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %esi
        subl    $12, %esp
        movl    8(%ebp), %eax
        movl    %eax, -12(%ebp)
        testl   %eax, %eax
        jle     .LBB0_2
# BB#1:
        movl    -12(%ebp), %esi
        leal    -1(%esi), %eax
        movl    %eax, (%esp)
        calll   factorial
        imull   %esi, %eax
        movl    %eax, -8(%ebp)
          :
.L.str:
        .asciz  "%d\n"
        .size   .L.str, 4

        .ident  "clang version 3.6.2 (tags/RELEASE_362/final)"
        .section        ".note.GNU-stack","",@progbits

ここまでで、糞石用のアセンブリコードが得られた。次はそれを糞石用アセンブラーに かけて、オブジェクトファイルに変換しそれをリンカーでリンクしてみよう。

$ as fact.s
$ ld --eh-frame-hdr -dynamic-linker /libexec/ld-elf.so.1 --hash-style=both --enable-new-dtags -m elf_i386_fbsd -o hoge /usr/lib/crt1.o /usr/lib/crti.o /usr/lib/crtbegin.o -L/usr/lib a.out -lgcc --as-needed -lgcc_s --no-as-needed -lc -lgcc --as-needed -lgcc_s --no-as-needed /usr/lib/crtend.o /usr/lib/crtn.o 
$ ./hoge
3628800

asすると a.outが得られる。ldの出力にhogeを指定して実行用のバイナリーを作成して みた。それにしても、リンカーのオプションが複雑だな。asもldもgcc485が引き連れてきた binutils-2.25.1だった。 両方共GNU製だから、LLVMとGNUは下層では友好的なんだな。

gcc vs clang

haskellが引き連れてきたgcc、LL族であるPerl/Pythonが連れてきたllvmが期せずして、 FreeBSD上に揃った。これはもうHaskellとLL族の代理戦争をやってみれって事だろう。 Linux上では、こんな楽しい場面はなかなか無いだろうからね。

戦争と言うかスピード競技のお題は例によって、

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 2) + fib(n - 1);
}

int main(int argc, char *argv[]) {
    printf("%d\n", fib(42));
    return 0;
}

ひたすら速さを競う100m競技ですよ。

$ clang fib.c
$ time ./a.out
267914296
       11.77 real        11.71 user         0.00 sys

$ clang -O2 fib.c
$ time ./a.out
267914296
       12.53 real        12.49 user         0.00 sys

$ clang -O3 fib.c
$ time ./a.out
267914296
       10.99 real        10.95 user         0.00 sys

$ clang -S -emit-llvm fib.c
$ time lli fib.ll
267914296
       10.81 real        10.75 user         0.02 sys

$ gcc48 fib.c
$ time ./a.out
267914296
       10.03 real         9.99 user         0.00 sys

$ gcc48 -O2 fib.c
$ time ./a.out
267914296
        6.26 real         6.23 user         0.00 sys

$ gcc48 -O3 fib.c
$ time ./a.out
267914296
        2.14 real         2.12 user         0.00 sys

lliを使うと強力な最適化がかかったJITが発動するのかな。 それにしても最適化したgccは。ぶっちぎりで速いな。

でも、gcc -O4 が指定されたら、コンパイル時にfib(42)を計算してしまい、その結果 だけを表示するぐらいの事はやって貰いたいな。これぞ究極の畳み込みですから。 えっ、そうすると -O3の威力を世間に誇示出来ないから駄目だって? それに その計算をしてる時間がコンパイル時間に加算されちゃうんで、gccはコンパイルが 遅いって評判が立ってしまいますから却下らしいです。

clang++

clangにはclangフラフラが有るそうなので、 LLVM フレームワークで実用的なコンパイラーを作成する(1) を参考に実行してみると、

$ clang++ `llvm-config  --cxxflags --ldflags --libs` -v hw.cpp
  :
/tmp/hw-6295b7.o: In function `main':
hw.cpp:(.text.main+0x1c): undefined reference to `llvm::getGlobalContext()'
hw.cpp:(.text.main+0x6e): undefined reference to `llvm::Module::Module(llvm::StringRef, llvm::LLVMContext&)'
  :
clang: error: linker command failed with exit code 1

エラーだよ。llvm-configの使い方間違ってる? それとも、進化の速いLLVMに対して 記事内容が古い? LLVM フレームワークで実用的コンパイラーを作成する(2) を勉強すると、解決出来るかなあ?

$ clang++ -c hw.cpp `llvm-config  --cxxflags`
$ clang++ hw.o `llvm-config --ldflags --libs`
/usr/local/llvm36/lib/libLLVMSupport.a(Process.o): In function `llvm::sys::Process::FileDescriptorHasColors(int)':
Process.cpp:(.text._ZN4llvm3sys7Process23FileDescriptorHasColorsEi+0x86): undefined reference to `setupterm'
Process.cpp:(.text._ZN4llvm3sys7Process23FileDescriptorHasColorsEi+0xa0): undefined reference to `tigetnum'
Process.cpp:(.text._ZN4llvm3sys7Process23FileDescriptorHasColorsEi+0xb3): undefined reference to `set_curterm'
Process.cpp:(.text._ZN4llvm3sys7Process23FileDescriptorHasColorsEi+0xbb): undefined reference to `del_curterm'
/usr/local/llvm36/lib/libLLVMSupport.a(Threading.o): In function `llvm::llvm_execute_on_thread(void (*)(void*), void*, unsigned int)':
Threading.cpp:(.text._ZN4llvm22llvm_execute_on_threadEPFvPvES0_j+0x6d): undefined reference to `pthread_create'
clang: error: linker command failed with exit code 1 (use -v to see invocation)

こう使うのが正しい方法のようだけど、依然としてエラーだ。llvm-configが最適な リンクを導出してくれているのにリンクエラーって事は、もう尻尾巻いて逃げ出せって 事だ。もうこれぐらいにしておこう。

fedoraではどうかな?

100m競争はサーキットを転戦するんであります。Fedoraではどうか? 下記を 入れたよ。

 clang               i686          3.7.0-4.fc23          updates           15 M
 clang-libs          i686          3.7.0-4.fc23          updates          5.2 M
 clang-devel         i686         3.7.0-4.fc23            updates         1.5 M
 llvm                i686          3.7.0-4.fc23          updates          1.8 M
 llvm-devel          i686          3.7.0-4.fc23          updates          1.9 M
 llvm-static         i686         3.7.0-4.fc23            updates          31 M
[sakae@fedora z]$ clang fib.c
[sakae@fedora z]$ /bin/time -p ./a.out
267914296
real 10.41
user 10.32
sys 0.04

[sakae@fedora z]$ clang -O2 fib.c
[sakae@fedora z]$ /bin/time -p ./a.out
267914296
real 9.18
user 9.11
sys 0.00

[sakae@fedora z]$ clang -O3 fib.c
[sakae@fedora z]$ /bin/time -p ./a.out
267914296
real 9.16
user 9.08
sys 0.01

[sakae@fedora z]$ clang -S -emit-llvm fib.c
[sakae@fedora z]$ /bin/time -p lli fib.ll
267914296
real 10.69
user 10.54
sys 0.03

[sakae@fedora z]$ cc fib.c
[sakae@fedora z]$ /bin/time -p ./a.out
267914296
real 10.31
user 10.22
sys 0.01

[sakae@fedora z]$ cc -O2 fib.c
[sakae@fedora z]$ /bin/time -p ./a.out
267914296
real 5.47
user 5.42
sys 0.02

[sakae@fedora z]$ cc -O3 fib.c
[sakae@fedora z]$ /bin/time -p ./a.out
267914296
real 2.01
user 2.00
sys 0.00

ふむ、FreeBSDと同じ結果だな。

で、問題のLLVM IRを作るやつ

[sakae@fedora z]$ clang++ hw.o `llvm-config --ldflags --libs`
/usr/lib/llvm/libLLVMSupport.a(Mutex.o): 関数 `llvm::sys::MutexImpl::MutexImpl(bool)' 内:
(.text._ZN4llvm3sys9MutexImplC2Eb+0x47): `pthread_mutexattr_init' に対する定義されていない参照です
/usr/lib/llvm/libLLVMSupport.a(Mutex.o): 関数 `llvm::sys::MutexImpl::MutexImpl(bool)' 内:
(.text._ZN4llvm3sys9MutexImplC2Eb+0x58): `pthread_mutexattr_settype' に対する定 義されていない参照です
 :

もう、わけわかめ。llvmのtutoralに挑戦してみようかな。

luliaでlisp

疲れたので、気分転換します。少しはjulia関連の事も書いておかないとね。

juliaの隠れコマンドと言うかdebugのお供にどうぞってやつだな。

[sakae@fedora ~]$ julia --lisp
;  _
; |_ _ _ |_ _ |  . _ _
; | (-||||_(_)|__|_)|_)
;-------------------|----------------------------------------------------------

> (jl-parse-string "1 + 3")
(call + 1 3)

> (exit)

ちゃんとparserが組み込まれたlispが起動してきた。

この隠れ機能は、stack overflowで知ったんだけど、他にも隠れ機能が有るのかなあ? ソース観光を続けて、自分だけの穴場を探してみたいぞ。

昔の環境でLLVM IRを吐き出す

どうも上でやったIBMさんの例題が気になってしょうがない。ふと思ったんだ。 あの記事はかなり古い。と言う事は、LLVMな環境も今となってはかなり古いんでは なかろうか。古いLLVMって言うと、、、、有ったぞ。juliaを作った時のやつが。 LLVM 3.3ですってさ。

だめもとで、/home/sakae/src/julia-0.4.3/usr/bin へPATHを通しておいて、

$ g++  -c hw.cpp `llvm-config  --cxxflags`
$ g++  hw.o `llvm-config --ldflags --libs`
$ ./a.out
; ModuleID = 'asdf'

@0 = private unnamed_addr constant [14 x i8] c"hello world!\0A\00"

define void @main() {
entrypoint:
  %0 = call i32 @puts(i8* getelementptr inbounds ([14 x i8]* @0, i32 0, i32 0))
  ret void
}

declare i32 @puts(i8*)

$ ./a.out 2> hw.ll
$ lli hw.ll
hello world!

オイラーの粘り勝ち。粘っこいのは、毎朝かかさず納豆を食べているおかげ。なにやら 中華な人も納豆を食べるようになったとか。それぐらいは許せるとして、生な魚は どうかなと言っていた連中が、喜んで寿司などを食うのはいかながものかと。

やつらにみんな食われてしまって、日本人は高くて食べられなくなったらどうして くれる。世界に日本食を勧めた連中よ、責任を取ってくれ。 思わずの愚痴でした。

上の、hw.cppは、記事からちょっと改変してるので、記録しておく。

#include "llvm/ADT/ArrayRef.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/IRBuilder.h"
#include <vector>
#include <string>

int main() {
  llvm::LLVMContext & context = llvm::getGlobalContext();
  llvm::Module *module = new llvm::Module("asdf", context);
  llvm::IRBuilder<> builder(context);

  llvm::FunctionType *funcType = llvm::FunctionType::get(builder.getVoidTy(), false);
  llvm::Function *mainFunc =
    llvm::Function::Create(funcType, llvm::Function::ExternalLinkage, "main", module);
  llvm::BasicBlock *entry = llvm::BasicBlock::Create(context, "entrypoint", mainFunc);
  builder.SetInsertPoint(entry);

  llvm::Value *helloWorld = builder.CreateGlobalStringPtr("hello world!\n");

  std::vector<llvm::Type *> putsArgs;
  putsArgs.push_back(builder.getInt8Ty()->getPointerTo());
  llvm::ArrayRef<llvm::Type*>  argsRef(putsArgs);

  llvm::FunctionType *putsType =
    llvm::FunctionType::get(builder.getInt32Ty(), argsRef, false);
  llvm::Constant *putsFunc = module->getOrInsertFunction("puts", putsType);

  builder.CreateCall(putsFunc, helloWorld);
  builder.CreateRetVoid();
  module->dump();
}

このコードはclang++ではコンパイルしない事。LLVMとの謹慎相姦でエラーになる。 異種な親である g++ を使って、コンパイルする事。 これ、世界と言うか、生物界の常識であります。

etc

訳:非推奨になったLinuxネットワークコマンドの代替コマンド

List of languages that compile to JS