Mercurial > hg > Events > OSC2018

changeset 0:db9deddc28c6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial commit
author Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
date Fri, 15 Jun 2018 16:01:15 +0900
parents
children 61e24cbc5f22
files slide.md
diffstat 1 files changed, 326 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /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)
+ <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
+## 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`と対応している