title: GCCとLLVMの内部の比較
author: Takahiro Shimizu
profile:
lang: Japanese

## このセッションの内容

- 現在の主要なCコンパイラであるGCCとLLVM/Clangが実際にどのような処理をするかを追っていきます
- コンパイラのトレースにはLLVMをバックエンドとして利用しているlldbを用います

## このセッションの目的
- 現在当研究室ではContinuation Based Cという言語を開発しています
- この言語はgcc/clangで実装されており，代々開発が引き継がれています
- 今回はこの発表を通して実際の開発の流れを体験していきます
- このセッションを聞くと実際にgcc/clangで開発を出来るかもしれない…!?

!SLIDE
## アジェンダ
- GCCとLLVM
- コンパイルの流れについて
- デバッグ方法
- コードリーディング

!SLIDE
## GCCとLLVM

- 今回のセッションではGCCとLLVM/Clangを対象に読んでいきます
- GCCとは**GNU Compiler Collection**の略で1985年から開発されているOSSなコンパイラパッケージです
    - C言語で実装され，様々な言語のコンパイルをサポートしているのが特徴です
- LLVMとはLLVMというコンパイラ基盤のことを指します
    - レジスタが無限にある仮想マシン用の言語であるLLVMIRをサポートしており，柔軟に言語処理系を実装する事が可能です
    - ClangはLLVMを用いたC言語系統の言語コンパイラです
    - 主な実装はC++で記述されています

!SLIDE
## コンパイルの流れ

- C言語がコンパイルされるまでは主に以下のフェーズがあります
- フロントエンド
    - 字句解析
    - 構文解析
    - 中間コード生成
- ミドルエンド
    - 最適化
- バックエンド
    - コード生成

!SLIDE
## 字句解析

- 対象のソースコードを解析して**トークン**と呼ばれる単位に分割します
- この処理を実行している箇所を主に「レキサー」と呼びます

```C
(4 + 3 ) * 2
// ==> [(] [4][+][3][)][*][2]
```

!SLIDE
## 構文解析
- 字句解析の結果を元に，言語の文法に則った構文として**構文抽象木(AST)** と呼ばれる木構造を生成します
- この時点で最適化が行われる箇所も存在します

```
 [(] [4][+][3][)][*][2]
	
    *
  +   2
4   3 
```

!SLIDE
## 中間コード生成
- コンパイラが扱いやすくするためにASTを利用し擬似的な中間言語に変換します
- 基本的にアセンブラに近い出力結果となります
- GCCではGIMPLE
- LLVM/ClangではLLVM IRと呼ばれる形式です

!SLIDE
## 最適化
- 生成するコードを最適化するフェーズです
- 主にインライン展開などが実行されます
    - インライン展開...呼び出し先の関数を呼び出し元に展開する

!SLIDE
## 今回のトレース箇所

- パーサー
- 構文抽象木の構造
- pass
- インライン展開
- コード生成部分


!SLIDE
## デバッグの準備
- 今回のセッションではソースコードを直接読むのではなく，処理をデバッガを用いてトレースしながら勧めていきます．
- トレースに利用するデバッガはLLVMをバックエンドとして利用しているlldbです.
- その為GCC/Clang共にデバッグオプションを付けた状態でビルドする必要があります
- GCC

```
CbC_gcc/configure CFLAGS="-g3 -O0" --prefix=$PWD \
    --disable-nls --disable-bootstrap --enable-languages=c \
    --enable-checking=tree,rtl,assert,types
```

- LLVM

```
cmake -G Ninja -DCMAKE_BUILD_TYPE:STRING=Debug -DCMAKE_INSTALL_PREFIX:PATH=`pwd` ~/hg/CbC/LLVM_original
```


!SLIDE
## デバッグ方法(gcc)
- 実は**gccではコンパイルを行わず**,C言語のコンパイルは**CC1**というコンパイラが内部的に実行されています．
- lldbでトレースする際にgccをトレースしてしまうと，CC1に処理を渡す余計な部分が出てしまいます
- その為cc1を直接読む用に実行します

```sh
$cat test.sh
lldb -- gcc/cc1 test.c
```

!SLIDE
## デバッグ方法(clang)

- clangは内部的にいくつかのオプションを自動的に付け加えて実行している
- `clang -v test.c`などとするとそのオプションを確認する事が出来る

```sh
$ bin/clang -v  test.c
clang version 7.0.0
Target: x86_64-apple-darwin17.6.0
Thread model: posix
InstalledDir: /Users/anatofuz/workspace/cr/build_llvm/bin
 "/Users/anatofuz/workspace/cr/build_llvm/bin/clang-7.0" -cc1 -triple x86_64-apple-macosx10.13.0 -Wdeprecated-objc-isa-usage -Werror=deprecated-objc-isa-usage -emit-obj -mrelax-all -disable-free -main-file-name test.c -mrelocation-model pic -pic-level 2 -mthread-model posix -mdisable-fp-elim -masm-verbose -munwind-tables -target-cpu penryn -dwarf-column-info -debugger-tuning=lldb -target-linker-version 351.8 -v -resource-dir /Users/anatofuz/workspace/cr/build_llvm/lib/clang/7.0.0 -fdebug-compilation-dir /Users/anatofuz/workspace/cr/build_llvm -ferror-limit 19 -fmessage-length 120 -stack-protector 1 -fblocks -fencode-extended-block-signature -fobjc-runtime=macosx-10.13.0 -fmax-type-align=16 -fdiagnostics-show-option -fcolor-diagnostics -o /var/folders/jk/3jyh2t9j0lj11j4wks3r8bj40000gn/T/test-2169da.o -x c test.c
clang -cc1 version 7.0.0 based upon LLVM 7.0.0svn default target x86_64-apple-darwin17.6.0
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/include
 /Users/anatofuz/workspace/cr/build_llvm/lib/clang/7.0.0/include
 /usr/include
 /System/Library/Frameworks (framework directory)
 /Library/Frameworks (framework directory)
End of search list.
 "/usr/bin/ld" -demangle -lto_library /Users/anatofuz/workspace/cr/build_llvm/lib/libLTO.dylib -no_deduplicate -dynamic -arch x86_64 -macosx_version_min 10.13.0 -o a.out /var/folders/jk/3jyh2t9j0lj11j4wks3r8bj40000gn/T/test-2169da.o -lSystem /Users/anatofuz/workspace/cr/build_llvm/lib/clang/7.0.0/lib/darwin/libclang_rt.osx.a
```

- lldbではオプションを明示的に付け加えないと実行されない為にこれをコピーして実行する

!SLIDE
## デバッグ方法(clang)

- その為以下のようなシェルスクリプトを作成する

lldb -- bin/clang -cc1 -triple x86_64-apple-macosx10.13.0 -Wdeprecated-objc-isa-usage -Werror=deprecated-objc-isa-usage -emit-obj -mrelax-all -disable-free -main-file-name test.c -mrelocation-model pic -pic-level 2 -mthread-model posix -mdisable-fp-elim -masm-verbose -munwind-tables -target-cpu penryn -dwarf-column-info -debugger-tuning=lldb -target-linker-version 351.8 -v -resource-dir /Users/anatofuz/workspace/cr/build_llvm/lib/clang/7.0.0 -fdebug-compilation-dir /Users/anatofuz/workspace/cr/build_llvm -ferror-limit 19 -fmessage-length 120 -stack-protector 1 -fblocks -fencode-extended-block-signature -fobjc-runtime=macosx-10.13.0 -fmax-type-align=16 -fdiagnostics-show-option -fcolor-diagnostics -x c test.c


!SLIDE
## gccのparser

- gccのC言語のパーサーは `gcc/c/c-parser.c` で定義されています
- この中の`c_parser_expression`という関数でパースを実行する
- パースされた結果は`struct c_expr`という型で木構造として返却されます
- lldbでは`p debug_tree(expr.value)`とすることで内容を確認できる

```
$ sh test.sh
(lldb) target create "gcc/cc1"
Current executable set to 'gcc/cc1' (x86_64).
(lldb) settings set -- target.run-args  "test.c"
(lldb) b c_parser_expression
Breakpoint 1: where = cc1`c_parser_expression(c_parser*) + 23 [inlined] c_parser_peek_token(c_parser*) at c-parser.c:9230, address = 0x0000000100070967
(lldb) run
Process 12348 launched: '/Users/anatofuz/workspace/cr/build_gcc/gcc/cc1' (x86_64)
 maincc1 was compiled with optimization - stepping may behave oddly; variables may not be available.
Process 12348 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
    frame #0: 0x0000000100070967 cc1`c_parser_expression(c_parser*) [inlined] c_parser_peek_token(parser=0x0000000143d45000) at c-parser.c:439 [opt]
   436 	c_token *
   437 	c_parser_peek_token (c_parser *parser)
   438 	{
-> 439 	  if (parser->tokens_avail == 0)
   440 	    {
   441 	      c_lex_one_token (parser, &parser->tokens[0]);
   442 	      parser->tokens_avail = 1;
Target 0: (cc1) stopped.
```

!SLIDE
## gccのparser

```
(lldb) n
Process 12348 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = step over
    frame #0: 0x0000000100070997 cc1`c_parser_expression(parser=0x0000000143d45000) at c-parser.c:9233 [opt]
   9230	  location_t tloc = c_parser_peek_token (parser)->location;
   9231	  struct c_expr expr;
   9232	  expr = c_parser_expr_no_commas (parser, NULL);
-> 9233	  if (c_parser_next_token_is (parser, CPP_COMMA))
   9234	    expr = convert_lvalue_to_rvalue (tloc, expr, true, false);
   9235	  while (c_parser_next_token_is (parser, CPP_COMMA))
   9236	    {
Target 0: (cc1) stopped.
(lldb) p expr
(c_expr) $1 = {
  value = 0x0000000143c14040
  original_code = ERROR_MARK
  original_type = 0x0000000000000000
  src_range = (m_start = 16672, m_finish = 17440)
}
(lldb) p debug_tree(expr.value)
 <call_expr 0x143c14040
    type <integer_type 0x143c195e8 int public SI
        size <integer_cst 0x143c01f30 constant 32>
        unit-size <integer_cst 0x143c01f48 constant 4>
        align:32 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x143c195e8 precision:32 min <integer_cst 0x143c01ee8 -2147483648> max <integer_cst 0x143c01f00 2147483647>
        pointer_to_this <pointer_type 0x143c21a80>>
    side-effects
    fn <addr_expr 0x143d34660
        type <pointer_type 0x143d243f0 type <function_type 0x143c99a80>
            unsigned DI
            size <integer_cst 0x143c01cf0 constant 64>
            unit-size <integer_cst 0x143c01d08 constant 8>
            align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x143d24498>
        constant
        arg:0 <function_decl 0x143ca2500 printf type <function_type 0x143c99a80>
            addressable used public external built-in decl_3 decl_5 QI defer-output test.c:1:12
            align:8 warn_if_not_align:0 built-in: BUILT_IN_NORMAL:BUILT_IN_PRINTF>
        test.c:5:5 start: test.c:5:5 finish: test.c:5:10>
    arg:0 <nop_expr 0x143d34680
        type <pointer_type 0x143c26348 type <integer_type 0x143c262a0 char>
            unsigned DI size <integer_cst 0x143c01cf0 64> unit-size <integer_cst 0x143c01d08 8>
            align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x143c26348>
        readonly constant
        arg:0 <addr_expr 0x143d34620 type <pointer_type 0x143d24f18>
            readonly constant
            arg:0 <string_cst 0x143d34600 type <array_type 0x143d24e70>
                readonly constant static "Hello %d\012\000">
            test.c:5:12 start: test.c:5:12 finish: test.c:5:23>
        test.c:5:12 start: test.c:5:12 finish: test.c:5:23>
    arg:1 <plus_expr 0x143d25348 type <integer_type 0x143c195e8 int>

        arg:0 <var_decl 0x142352f30 a type <integer_type 0x143c195e8 int>
            used read SI test.c:4:9 size <integer_cst 0x143c01f30 32> unit-size <integer_cst 0x143c01f48 4>
            align:32 warn_if_not_align:0 context <function_decl 0x143d26500 main> initial <integer_cst 0x143c1e3f0 4>>
        arg:1 <parm_decl 0x143d45100 ac type <integer_type 0x143c195e8 int>
            used read SI test.c:3:14 size <integer_cst 0x143c01f30 32> unit-size <integer_cst 0x143c01f48 4>
            align:32 warn_if_not_align:0 context <function_decl 0x143d26500 main> arg-type <integer_type 0x143c195e8 int> chain <parm_decl 0x143d45180 av>>
        test.c:5:26 start: test.c:5:25 finish: test.c:5:28>
    test.c:5:5 start: test.c:5:5 finish: test.c:5:29>
```

!SLIDE
## llvmのparser

- llvmでは`ParseExpression`という関数でパースしている
- ここではパースした結果を`LHS`という変数に代入している

```
$sh lldb.sh            
(lldb) target create "bin/clang"
Current executable set to 'bin/clang' (x86_64).
(lldb) settings set -- target.run-args  "-cc1" "-triple" "x86_64-apple-macosx10.13.0" "-Wdeprecated-objc-isa-usage" "-Werror=deprecated-objc-isa-usage" "-emit-obj" "-mrelax-all" "-disable-free" "-main-file-name" "test.c" "-mrelocation-model" "pic" "-pic-level" "2" "-mthread-model" "posix" "-mdisable-fp-elim" "-masm-verbose" "-munwind-tables" "-target-cpu" "penryn" "-dwarf-column-info" "-debugger-tuning=lldb" "-target-linker-version" "351.8" "-v" "-resource-dir" "/Users/anatofuz/workspace/cr/build_llvm/lib/clang/7.0.0" "-fdebug-compilation-dir" "/Users/anatofuz/workspace/cr/build_llvm" "-ferror-limit" "19" "-fmessage-length" "120" "-stack-protector" "1" "-fblocks" "-fencode-extended-block-signature" "-fobjc-runtime=macosx-10.13.0" "-fmax-type-align=16" "-fdiagnostics-show-option" "-fcolor-diagnostics" "-x" "c" "test.c"
(lldb) b ParseExpression
Breakpoint 1: 2 locations.
(lldb) run
Process 12147 launched: '/Users/anatofuz/workspace/cr/build_llvm/bin/clang' (x86_64)
clang -cc1 version 7.0.0 based upon LLVM 7.0.0svn default target x86_64-apple-darwin17.6.0
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/include
 /Users/anatofuz/workspace/cr/build_llvm/lib/clang/7.0.0/include
 /usr/include
 /System/Library/Frameworks (framework directory)
 /Library/Frameworks (framework directory)
End of search list.
Process 12147 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.2
    frame #0: 0x0000000105a9df53 clang`clang::Parser::ParseExpression(this=0x0000000114053400, isTypeCast=MaybeTypeCast) at ParseExpr.cpp:126
   123 	///         expression ',' assignment-expression ...[opt]
   124 	/// \endverbatim
   125 	ExprResult Parser::ParseExpression(TypeCastState isTypeCast) {
-> 126 	  ExprResult LHS(ParseAssignmentExpression(isTypeCast));
   127 	  return ParseRHSOfBinaryExpression(LHS, prec::Comma);
   128 	}
   129
Target 0: (clang) stopped.
```

!SLIDE
## llvmのパース

- stepで関数の内部に入ってみる
- ここでは`Tok`というオブジェクトにトークンが格納されている.
- このトークンを`tools/clang/include/clang/Sema/Sema.h`で定義されているActionsというオブジェクトを呼ぶことでASTに変換している

```
(lldb) step
Process 12147 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = step in
    frame #0: 0x0000000105a9dfa8 clang`clang::Parser::ParseAssignmentExpression(this=0x0000000114053400, isTypeCast=MaybeTypeCast) at ParseExpr.cpp:163
   160
   161 	/// \brief Parse an expr that doesn't include (top-level) commas.
   162 	ExprResult Parser::ParseAssignmentExpression(TypeCastState isTypeCast) {
-> 163 	  if (Tok.is(tok::code_completion)) {
   164 	    Actions.CodeCompleteOrdinaryName(getCurScope(), Sema::PCC_Expression);
   165 	    cutOffParsing();
   166 	    return ExprError();
Target 0: (clang) stopped.
(lldb) p Tok
(clang::Token) $0 = (Loc = 2151358386, UintData = 1, PtrData = 0x0000000116020184, Kind = numeric_constant, Flags = 0)
```

!SLIDE
## pass

- Passとは内部表現のコードを対象に，解析を行い最適化を行うフレームワークのことです
- そのPassに応じた処理をそれぞれdefファイルを用いて定義しています
- Passを操作することで自由に最適化処理を付け加えることが可能です
- 今回はCbCを実装する際に利用するインライン展開の制御部分を確認します

!SLIDE
## gccのpass

- gccは`gcc/passes.def`という定義ファイルで処理を定義している
- この内部処理は`passes.c`内で定義されている`execute_one_pass`関数が実行する



!SLIDE
## gccのコード生成

- `expand_expr`から`expand_call`が呼び出される
- この`expand_call`内でトークンに応じて状態を作成する
- 実際にgccの内部的な関数を作成している箇所は`gcc/cfgexpand.c`に書かれている`expand_gimple_stmt_1`である
- 帰ってきた値は`debug_rtx(val)`および`debug_rtx_list`を利用することで視覚化出来る

!SLIDE
## llvmのコード生成

- llvmでは`EmitCall`という関数が主に生成を担っている
- この中の`Builder.CreateCall`が関数呼び出しを変換している
    - この部分はgccの`expand_call`と対応している