# HG changeset patch # User Takahiro SHIMIZU # Date 1529046075 -32400 # Node ID db9deddc28c6b4ad97a548f0882e1a7a0f05effb initial commit diff -r 000000000000 -r db9deddc28c6 slide.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide.md Fri Jun 15 16:01:15 2018 +0900 @@ -0,0 +1,326 @@ +title: GCCとLLVMの内部の比較 +author: Takahiro Shimizu +profile: +lang: Japanese + +## このセッションの内容 + +- 現在の主要なCコンパイラであるGCCとLLVM/Clangが実際にどのような処理をするかを追っていきます +- コンパイラのトレースにはLLVMをバックエンドとして利用しているlldbを用います + +!SLIDE +# アジェンダ +- GCCとLLVM +- コンパイルの流れについて +- デバッグ方法 +- コードリーディング + +!SLIDE +## GCCとLLVM + +- 今回のセッションではGCCとLLVM/Clangを対象に読んでいきます +- GCCとは**GNU Compiler Collection**の略で1985年から開発されているOSSなコンパイラパッケージです + - C言語で実装され，様々な言語のコンパイルをサポートしているのが特徴です +- LLVMとはLLVMというコンパイラ基盤のことを指します + - JavaのByteCodeの用に仮想的な言語である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) + + unit-size + align:32 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x143c195e8 precision:32 min max + pointer_to_this > + side-effects + fn + unsigned DI + size + unit-size + align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x143d24498> + constant + arg:0 + 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 + unsigned DI size unit-size + align:64 warn_if_not_align:0 symtab:0 alias-set -1 canonical-type 0x143c26348> + readonly constant + arg:0 + readonly constant + arg:0 + 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 + + arg:0 + used read SI test.c:4:9 size unit-size + align:32 warn_if_not_align:0 context initial > + arg:1 + used read SI test.c:3:14 size unit-size + align:32 warn_if_not_align:0 context arg-type chain > + 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 +## 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`と対応している