○コンパイラがソースコードから実行バイナリを生成する過程について、
現在知っている範囲で説明してください。
ソースコードの言語については、好きなものでかまいません。
ここではC言語のソースコードを例にとって説明していきます｡
ソースコードの表現はバッククォートで括ります｡
ソースコードを解析してからバイナリを生成するまで､
｢大まかに｣言うと次のようなフェーズを辿ります｡
- プリプロセス(コンパイラではないソフトウェア､プリプロセッサの責務)
- ソースコード解析
- 中間表現生成
- (狭義の)コンパイル
- 中間表現とアーキテクチャ固有の命令セット､ニーモニックを対応
- アセンブル(アセンブラというソフトウェアが担う役割だが､一般的にコンパイルするというときアセンブルも内包される)
- ELFフォーマットに準拠したオブジェクトファイル
- アセンブリ言語から機械語を生成する
- リンク(同じくリンカの役割だが広義のコンパイルに含まれる時もある)
以下詳しく各フェーズについて解説していきます｡
C言語のソースコードには #include<stdio.h>等､
ヘッダファイルのinclude宣言が先頭に記載されています｡
C言語におけるプリプロセスは大きく分けて
等があります｡
まずヘッダファイルの展開ですが､
ここではポピュラーであり分かりやすい stdio.h の展開を例に取ります｡
私達はstdio.hをインクルードすることでprintf関数を含む多くのAPIを利用できますが､
これにはプリプロセッサの仕事が大きく作用しています｡
gccではcppというプリプロセッサが動いています｡
C言語は関数の定義順が大きく影響する言語です｡
書く関数はソースコード上で自身より先に(ファイルで言えば上に)定義されていなければ､
各関数はその関数を｢知りません｣｡
より具体的に言えば､
コンパイラがその関数名を 未定義の識別子 として判定します｡
C言語にはプロトタイプ宣言という方法で､
main関数に識別子の存在を｢知らせる｣という技がありますが､
ファイル内でprintf関数のプロトタイプ宣言を記述しなくても､
main関数はprintf関数等を｢知っている｣状態になっています｡
より具体的に言えば､
コンパイラがprintf関数を定義済み識別子と認識します｡
プリプロセッサはヘッダファイルを参照し､
各API関数の定義を同ファイル内に展開します｡
実際に展開した様子です｡
#include<stdio.h>
int main(void){
printf("Hello,World!\n"); //コメント
return 0;
}プリプロセス実行結果
実際にprintfのプロトタイプ宣言が確認出来ると思います｡
またコメントというコメントも出力された結果の末尾で削除されているのが確認できると思います｡
他にはマクロ定義を追って展開したり､
定数を即値に変換したり等が挙げられます｡
プリプロセッサの実装によって差異は異なりますが､
最も大きな仕事はヘッダファイルの展開に他なりません｡
プリプロセッサはコンパイル時に動作するような字句解析器とは独立して､
プリプロセス専用のトークナイズ処理を行う実装が必要です｡
同様に構文解析のアルゴリズムもC言語とは異なるものを用います｡
まずCプリプロセッサの挙動･アルゴリズムですが､
Daveという方がその実装の詳細を発表しています｡
参考: Dave Prosser's C Preprocessing Algorithm
Dave氏は 完全なCプリプロセッサを実装 するために約5年間を費やし､
このアルゴリズムを考えたようです｡
実装を解説するPDFファイルには､
擬似コードと共にC言語における マクロ展開 アルゴリズムが紹介されています｡
**ISO Draft**には､
具体的なC言語の規格が定義されています｡
以下プリプロセッサに関係する言語仕様を紹介します｡
実行バイナリの生成とは直接関係ありませんが､
Cプリプロセッサがどのようなディレクティブを展開するのかを知る事が出来ます｡
#ifdef INTEGER_CONSTANT
/* do something...*/
#endifのようにして用いる文です｡
整数の定数INTEGER_CONSTANTが既に定義されていれば､
#endifまでをブロックとし､実行するようなコードになっています｡
サンプルコードで解説します｡
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define DEBUG
int main(void){
srand((unsigned)time(NULL));
int secret_number = rand() % 10 + 1;
#ifdef DEBUG
printf("SecretNumber is %d\n",secret_number);
#endif
int input;
printf("Please input number\n");
scanf("%d",&input);
printf("Your Number : %d\n",input);
if(secret_number == input ){
printf("number is correct!\n");
return 0;
}
printf("wrong number!\n");
return 0;
}簡単な数当てゲームを作ってみました｡
ここでは#define DEBUGによってマクロ定数を定義しています｡
このコードをコンパイルし実行すると､
のように､
隠し番号が出力され､
ゲームの挙動を細かく確認しながらプログラミングすることが出来ます｡
#DEFINE DEBUGの行をコメントアウトすれば､
printf("SecretNumber is %d\n",secret_number);の行は実行されません｡
main関数内に#ifdefディレクティブがあるのが気に入らない場合は､
#elseを用いて次のように記述できます｡
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//#define DEBUG
#ifdef DEBUG
const int debugflg = 1;
#else
const int debugflg = 0;
#endif
int main(void){
srand((unsigned)time(NULL));
int secret_number = rand() % 10 + 1;
if(debugflg)
printf("SecretNumber is %d\n",secret_number);
int input;
printf("Please input number\n");
scanf("%d",&input);
printf("Your Number : %d\n",input);
if(secret_number == input ){
printf("number is correct!\n");
return 0;
}
printf("wrong number!\n");
return 0;
}gcc -E c.cとして､
プリプロセス結果を見てみましょう｡
# 10 "c.c"
const int debugflg = 0;
int main(void){
srand((unsigned)time(
# 15 "c.c" 3 4
((void *)0)
# 15 "c.c"
));
int secret_number = rand() % 10 + 1;
if(debugflg)
printf("SecretNumber is %d\n",secret_number);
int input;
printf("Please input number\n");
scanf("%d",&input);
printf("Your Number : %d\n",input);
if(secret_number == input ){
printf("number is correct!\n");
return 0;
}
printf("wrong number!\n");
return 0;
}const int debugflg = 0;だけが残っており､
確かに条件処理が実行されている 事が確認できました｡
#ifディレクティブを使用することで､
#if (DEBUG && LOGLEVEL >= 30)
printf("Warning:unexpected such as number:%d",invalid_number);
#endifのような挙動を起こす事も可能です｡
ヘッダ･ソースファイルを展開するためのディレクティブです｡
#include宣言等がここに内包されます｡
#include <Standard-headerfile>#include <userdefined-headerfile>#include <preprocessing token>
がサポートされています｡
三番目だけあまり見ないので､
ここで解説を加えます｡
#define ARCHITECTURE "x86_64"
#if ARCHITECTURE == "x86_64"
#define HEADFILE "IA.h"
#elif ARCHITECRE == "POWERPC"
#define HEADFILE "POWERPC.h"
#else
#define HEADFILE "UNKNOWN.h"
#endif
#include HEADFILE
のようにして､include宣言のオペランドを変更させる場合に用います｡
上記に述べた以外にも､以下のようなディレクティブが存在します
- Macro replacement
- Line Control
- error directive
- Pragma directive
- Null directive
#include等､preprocess directiveを解析し､展開する- コメント削除等を行う
次のコードを見てみます｡
#include "stdio.h"
int sum(int a,int b);
int main(void){
int num = 10;
printf("%d\n",sum(num,10));
return 0;
}これは実際に動作するC言語のコードですが､
このコードを ｢最も高レイヤ｣であり､ ｢C言語の構文を具現化したもの｣ として考えます｡
次にかなり抽象化されたものを紹介します｡
<import header-file>
<Expression Statement --Prototype-->
<Definition function>
ソースコードの構成要素を意味のまとまった実体に分割しています｡
これを実現するのが ソースコード解析という手法になります｡
ソースコード解析のやることは､
- 言語仕様に準拠したトークンを定義
- 正しく最小単位(トークン)に分割できるように ルールベースで字句解析器を定義
- トークンを一つ一つジャンプしながら 構文が正しいかどうかチェック
- 正しい場合は ASTノード を生成する｡
- 関数定義のノードを例に取ると､
引数の数､ 関数名 等を保持することが目標
中間表現の生成はソースコード解析には含めないこととします｡
ここではAST構築までを扱います｡
ソースコード解析の目指すところは､
上記に示したように｢具体的なソースコードを言語仕様に準拠した抽象的な実体｣に変換することです｡
この例でいうところの num は変数名です｡
実際に代入される10の部分はint型の即値､int型を返す関数呼び出し等が使えます｡
<type-INT> <IDENTIFER> <ASSIGN> <Literal-INT> <SEMICOLON>
変数の初期化を **｢トークン毎｣**に見ています｡
これは 字句解析 というフェーズで､
ソースコードを C言語で意味を持つ最小単位に分割 する処理になります｡
字句解析･トークナイズ処理は ルールベース であり､
機械学習タスクのように モデルを定義して推論させる というわけではありません｡
C言語に(ほぼ)準拠したトークン定義
上記に示したコードのように､
まず 言語毎に使用するトークンを定義しておきます｡
これは予約語( キーワード とも)だけではなく､
INTLITとリテラルに用いるようなものも定義しておきます｡
goccの実装では､
予約語を列挙したMapを定義しています｡
var keywords = map[string]TokenType{
"_Alignas": ALIGNAS,
"_Atomic": ATOMIC,
"alignof": ALIGNOF,
"auto": AUTO,
"break": BREAK,
"_Bool": BOOL,
"case": CASE,
"const": CONST,
"char": CHAR,
"continue": CONTINUE,
"default": DEFAULT,
"do": DO,
"double": DOUBLE,
"else": ELSE,
"enum": ENUM,
"extern": EXTERN,
"float": FLOAT,
"for": FOR,
"goto": GOTO,
"if": IF,
"inline": INLINE,
"int": INT,
"long": LONG,
"register": REGISTER,
"restrict": RESTRICT,
"return": RETURN,
"short": SHORT,
"signed": SIGNED,
"sizeof": SIZEOF,
"static": STATIC,
"struct": STRUCT,
"switch": SWITCH,
"typedef": TYPEDEF,
"unsigned": UNSIGNED,
"void": VOID,
"volatile": VOLATILE,
"while": WHILE,
"_Complex": COMPLEX,
"_Generic": GENERIC,
"_Noreturn": NORETURN,
"_Static_assert": STATICASSERT,
"_Thread_local": THREADLOCAL,
}このMapはどうやって用いるかと言うと､
識別子を解析する際に
ユーザが定義した変数･定数･関数なのか､
それとも言語に組み込まれた予約語なのかを判定するために用いることが出来ます｡
//LookupIdent judge whether Keywords include the token or not
func LookupIdent(ident string) TokenType { //識別子が予約語かどうか
if tok, ok := keywords[ident]; ok {
return tok
}
return IDENT
}私達は識別子の意味を考える事が出来るので､
のようなコードを見た時､
int,voidは型の名前で､
addは私達がつけた関数名だと判断出来ますが､
コンパイラは違いがわかりません｡
同じくアルファベットで構成された文字列と考えます｡
これは後述しますが､
字句解析時にASCIIコードを用いるなど､
機械的に決められたルールによってソースコードを解析しているからです｡
トークンに最低限必要な情報は､
です｡
上記のコードではそれぞれ､
Type,Literalが該当します｡
これ以外にもトークン時点で値情報を保持する場合もありますし､
デバッグのために ソースコード上での行･列情報 を保持するというのも考えられます｡
トークンは定義するだけでは利用出来ず､
字句解析器によって初めて成り立ちます｡
字句解析器は次のように定義されます｡
type Lexer struct {
input string
position, readPosition int
ch rune
Line int
Col int
Filename string
}inputは入力されたソースコードであり､
position,readPositionによってinputを辿って行きます｡
Go言語はUnicodeコードポイントを用いたrune単位の解析が出来ますが､
その他プログラミング言語で字句解析器を定義する場合は､
ASCIIコードをベースに字句解析をしていきます｡
ここにASCIIコードの対応表を示します｡
このコードを見ると､
文字とそれに対応するASCIIコードが示されています｡
字句解析を行う時には､
受け取ったソースコード中の文字がASCIIコード表のどの範囲にあるかを逐次判定しながら､
字句解析器のオフセットを進めていきます｡
ソースコードとASCIIが深い関係にある例として､
次のコードを見てみましょう｡
#include<stdio.h>
int main(void){
printf("%d\n",'A'); //char型の文字Aを10進数のフォーマット指定子で出力する｡
return 0;
}このコードの出力結果は､
**65**となります｡
この65は上記のASCIIコード表でいうAに相当しますよね｡
このように､文字はASCIIコードで表す事が可能です｡
GoはUnicodeコードポイントという点では異なりますが､
文字を番号で表すという点については同じです｡
実際にソースコード上の文字列を解析する関数をいくつか見てみましょう｡
func isDigit(ch rune) bool { //数値か判定する関数
return '0' <= ch && ch <= '9'
}
func isLetter(ch rune) bool { //アルファベットか判定する関数
return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}渡されたruneが文字の範囲に存在するかを判定しています｡
この関数を用いて実際に文字の判定をしてみましょう｡
package main
import "fmt"
func main() {
for _, char := range "GOLGO13" {
fmt.Printf("%s: isLetter? => %v\n", string(char), isLetter(char))
}
}
func isLetter(ch rune) bool { //アルファベットか判定する関数
return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}GOLGO13という文字列を一つずつ取り出し､
文字かどうかチェックします｡
出力結果を以下に示します｡
G: isLetter? => true
O: isLetter? => true
L: isLetter? => true
G: isLetter? => true
O: isLetter? => true
1: isLetter? => false
3: isLetter? => false
このようにソースコード上の文字を解析する関数を作ったら､
後は言語要素毎により上位の関数を定義します｡
例えば識別子を受け付ける関数は､
func (l *Lexer) readIdentifier() string {
position := l.position //現在の位置をとっておき
for isLetter(l.ch) { //文字である間
l.readChar() //読み進めて
}
return string([]rune(l.input[position:l.position])) //文字と判別した範囲の文字列を返す
}のように記述します｡
字句解析は何度も言うようにルールベースで進めるプロセスである点が重要です｡
具体的な字句解析器･字句解析のコードはこちらにあります
構文解析は､入力されたソースコードが言語仕様の構文上間違っていないかどうかをチェックしつつ､
合っている場合はASTノードを定義します｡
構文解析器は様々あるが､
最もメジャーであり最も実装がシンプルなものに
再帰下降構文解析器が挙げられます｡
こちらの記事では､
四則演算を例に再帰下降構文解析器の挙動を解説しています｡
構文解析のコードから､
stmt()関数を見てみましょう｡
この関数は､
現在パーサーが見ているトークンからASTノードの種類を定め､
その後の挙動を変化させています｡
intであれば変数定義だとしてdecl()関数(変数定義を解析する関数)を､
returnであればreturn文だとしてassign()関数(Expressionを解析する関数)を呼び出しています｡
ここでは
というコードを題材に､
構文解析の様子を追ってみましょう｡
まずdecl()関数を呼び出します｡
func (p *Parser) decl() *Node {
n := &Node{Type: ND_VARDEF, CType: *p.typeCheck()}
if p.curToken.Type != token.IDENT {
logrus.Errorf("variable name expected, but got %s", p.curToken.Literal)
}
n.Name = p.curToken.Literal
p.nextToken()
if p.curToken.Type == token.ASSIGN {
p.nextToken()
n.Init = p.assign()
}
p.expect(token.SEMICOLON)
return n
}この関数はASTノードの種類をND_VARDEF( variable define)とし､
構文解析をスタートします｡
型名の次には変数名が来なければなりません｡
なので
if p.curToken.Type != token.IDENT {
logrus.Errorf("variable name expected, but got %s", p.curToken.Literal)
}という処理を加え､エラー出力をしています｡
n.Nameは変数名･関数名を保有するメンバです｡
p.nextToken()によってオフセットを進め､
=であるかをチェックします｡
=であれば初期化文としてまた解析を行います｡
因みにC言語の文法として
というのがありますよね｡
この場合はif p.curToken.Type == token.ASSIGNの処理には入らないので､
セミコロンを受け付けて解析を終了しています｡
n.Init はp.assign()によってノードが代入されます｡
p.assign()は代入式の右辺を解析するとても大きな関数です｡
コード量は小さいですが､様々な関数を呼び出す大元の関数をなっています｡
今回は即値10を代入しているので､
様々な関数を辿った結果10が返ってきます｡
このように､
ソースコード一つに対して構文解析関数が対応するようになっており､
トークン列のオフセット (字句解析は1文字をオフセット) を進めながら構文解析が行われるようになっています｡
このようにして定義されたASTノードは､
Node構造体として返されます｡
type Node struct {
CType ClangType //C言語上の型
Type NodeType //ノードの種類
Lhs *Node //左子ノード
Rhs *Node //右子ノード
Val int //即値用の値
Expr *Node //return <expression>等の式部分
Name string //識別子の名前等
Stmts []*Node //for文等が持つ文の集まり
Condition *Node //if文の条件式
Then *Node //if文における実行部分
Else *Node //else文
Args []*Node //関数定義におけるパラメータ群
Body *Node //for文等､ブレースに囲まれた部分
Init *Node //for文の初期化文等
Inc *Node //for文のi++等
Stacksize int
Offset int
}この実装では全てのASTノードは*Nodeによって管理される為､
ASTについてはこの構造体を見れば詳細がわかるという利点があります｡
また関数も小分けされない為に､
複雑に大量の関数が入り乱れる､という事態を回避出来るようになっています｡
欠点として､
構造体が大きくなりすぎるとコードが見づらい･把握しにくいというものがあります｡
この欠点は､
- ベースの構造体
Nodeを定義する
TypeやName等､殆どのASTノードで必要なメンバのみ定義
- ジャンルごとに構造体をラップする構造体を定義し､
Nodeを埋め込む
if文､for文は複数文を格納するためBlockStatementとする- 関数の実体･変数の実体は同じく
identifier等にしておく
という方法を用いる事で改善出来ます｡
先程とは違うアプローチとして､
- ASTノードの種類を小分けに
- 各ノード毎に解析関数を定義
という方法があります｡
実際に､
**Go言語でつくるインタプリタ**という書籍では
この実装方法を取っていました｡
ここではその実装を紹介します｡
まず､最も抽象的かつ全てのASTノードの親を定義します｡
type Node interface {
TokenLiteral() string
String() string
}そして､ 式や 文等､
構文要素を直下に定義します｡
type Statement interface {
Node
statementNode()
}
type Expression interface {
Node
expressionNode()
}後は各構文に対して､
対応するノードを定義するだけです｡
ここでは return文を例に紹介します｡
return文は､
return <expression>という形を取りますよね｡
type ReturnStatement struct {
Token token.Token //returnが格納
ReturnValue Expression //expressionを解析して代入
}
func (rs *ReturnStatement) statementNode() {}
func (rs *ReturnStatement) TokenLiteral() string { return rs.Token.Literal }後は､
この return statementを解析する関数を定義します｡
func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
stmt := &ast.ReturnStatement{Token: p.curToken} //returnを見ている状態で呼び出される
p.nextToken() //オフセットを進める
stmt.ReturnValue = p.parseExpression(LOWEST) //演算の優先順位を考慮しながらExpressionを定義
if p.peekTokenIs(token.SEMICOLON) { //セミコロンが記述されてなくても良いように
p.nextToken()
}
return stmt
}この実装方法の場合､
先に述べた方法と比べて次の特徴があります｡
- メリット
- ｢各ASTノードを定義→解析関数を定義｣というフローに添えばいいだけなのでとても簡単
- コードの可読性は高い( 修正するときは特定のノードを参照するだけでいい )
- デメリット
構文に制約を課すというデメリットについて詳しく解説します｡
この実装方法は､
- 各文の先頭を見る
- 対応する解析関数に飛ばす
return なら parseReturnStatement()にdefなら parseDefStatement() に<identifier>なら次のチェックを
- 次のトークン が
=なら parseReAssignStatement()
- そうでなければ
parseExpressionStatement()
このように､
先頭に対して解析するフローを制御しているのです｡
Node構造体で一括管理する手法では､
解析する最中で Node.Typeを変化させる事で､
汎用性の高い関数+巨大な構造体によるASTの生成を実現しています｡
ASTごとに解析関数を定義している場合､
int main(void){
}
というコードを見た時､
intが来たので変数定義だとする
- 次のトークンは
mainと識別子なので上手くいく
- けど
(で関数定義だと 初めてわかる
ということから､
現在見ているトークン･次のトークン･その次のトークンの､
3つの情報を解析器に持たせる必要があります｡
構文解析がかなり複雑になってしまいますよね｡
C言語のプログラムを大きく分けると､
- Expression …変数定義の右辺
- Mul …Expression内で用いられる乗除演算
- Function …C言語で言えば一番大きな単位｡
stmt()関数の上
等が存在しますが､
プログラムに存在する言語要素ごとに解析関数を定義し､
後はif文やfor文等､C言語を構成する文法ごとに解析関数を取り回しています｡
余談ですがこれはボトムアップ方式とも呼ばれ､
一度定義した部品ともいえる関数を再利用して様々な構文を解析出来るため､
プログラムの設計として優れているといえます｡
ASTノードの生成方法は他にもあって､
｢Goでつくるインタプリタ｣では
if文､return文という単位毎に解析関数を定義しています｡
この場合再利用するわけではなく､
各解析関数ごとにトークン列のオフセットを進めるため､
可読性は高いですが､コード量は多くなりがちです｡
- コンパイラ(内の解析器) にソースコードを入力する
- 入力されたコード→トークン列→AST のフローで変換していく
- 字句解析 は､入力されたコードから トークン列 を生成する｡
- トークンとは ソースコード上において意味を持つ最小単位
- 識別子と予約語は 辞書のようなもの を定義して判別できるように
- 構文解析 は､トークン列を受け付けて 整合性をチェック
- 言語仕様に即した構文であれば ASTに組み込む
- 再帰下降構文解析は最も実装がシンプル
ここからは先程生成したASTから中間表現を生成するフェーズになります｡
中間表現というのは ASTノードの情報をできるだけ保持したまま､
アセンブリコードを出力する為の表現です｡
中間表現とニーモニックは1対1に対応しています｡
私がGo言語で再実装している9ccを例に取ってみましょう｡
IR_MOVという中間表現から､
mov reg1, reg2というニーモニックを生成している様子です｡
このIR_MOVは様々なASTノードから生成されます｡
変数定義のために即値がレジスタに読み込まれますが､
そのときにも勿論IR_MOVの中間表現が作られますし､
ret命令を実行する時には最終的な演算結果をeaxに格納する為に
IR_MOVが生成されます｡
goccの場合はかなり冗長なアセンブリが生成されます｡
これは最適化の処理があまり組まれていないからです｡
int main(void){
int a = 2;
int b = 3;
return a+b;
}というコードをそれぞれgcc( -O3 オプションをつけて )とgoccでコンパイルしてみると､
↓gocc
.intel_syntax noprefix
.global main
main:
push rbp
mov rbp,rsp
sub rsp, 16
push r12
push r13
push r14
push r15
mov r10, 2
mov r11, rbp
sub r11, 8
mov [r11], r10
mov r10, 3
mov r11, rbp
sub r11, 16
mov [r11], r10
mov r10, rbp
sub r10, 8
mov r10, [r10]
mov r11, rbp
sub r11, 16
mov r11, [r11]
add r10, r11
mov rax, r10
jmp .Lend0
.Lend0:
pop r15
pop r14
pop r13
pop r12
mov rsp, rbp
pop rbp
ret
↓gcc
.file "c.c"
.intel_syntax noprefix
.text
.section .text.startup,"ax",@progbits
.p2align 4,,15
.globl main
.type main, @function
main:
mov eax, 5
ret
.size main, .-main
.ident "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
.section .note.GNU-stack,"",@progbitsと大きな違いが見られます｡
gccは定数展開等､多くの最適化パスが適用されている事がわかります｡
コンパイラの実装によって中間表現の種類も様々です｡
代表的なものに**SSA(静的単一代入)**があります｡
これは(擬似コードを示します)､
a = 2
a = 3
b = a
のようなコードを､
a_1 = 2
a_2 = 3
b_1 = a_2
として保持しておく中間表現の形式です｡
ここで a_1に代入するコードは完全に冗長であり､
コンパイル時に最適化の一環で削除が可能になります｡
今日のコンパイラ実装で最も用いられている中間表現形式であり､
例に上げたように 最適化しやすい形を取ることが出来ます｡
実装によっては段階的に中間表現を生成するものもあります｡
高級言語(元々のソースコード)→ 高レベルな中間表現→ アーキテクチャ固有の中間表現→アセンブリ
のような感じです｡
中間表現の段階を多く踏むことで､最適化の実装がしやすいという背景があります｡
ここで中間表現に対応したニーモニックの生成が行われます｡
中間表現は
- オペランドの状態
- 即値であればその値だったり
- レジスタであればそれを示す番号だったり
- ニーモニックの種類
の情報を保持しています｡
後はそれにアセンブリコードを対応付けるだけです｡
コンパイルの本体は中間表現に変換する部分とも言えそうです｡
実際に変換するコードを紹介します｡
for _, ir := range fn.IRs {
switch ir.Operand {
case IR_IMM:
fmt.Fprintf(f, " mov %s, %d\n", Registers[ir.Lhs], ir.Rhs)
case IR_SUBIMM:
fmt.Fprintf(f, " sub %s, %d\n", Registers[ir.Lhs], ir.Rhs)
case IR_MOV:
fmt.Fprintf(f, " mov %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
case IR_RETURN:
fmt.Fprintf(f, " mov rax, %s\n", Registers[ir.Lhs])
fmt.Fprintf(f, " jmp %s\n", ret)
case IR_LOAD:
fmt.Fprintf(f, " mov %s, [%s]\n", Registers[ir.Lhs], Registers[ir.Rhs])
case IR_STORE:
fmt.Fprintf(f, " mov [%s], %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
case IR_SAVEARGS:
for i := 0; i < ir.Lhs; i++ {
fmt.Fprintf(f, " mov [rbp-%d], %s\n", (i+1)*8, argRegisters[i])
}
case IR_ADD:
fmt.Fprintf(f, " add %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
case IR_SUB:
fmt.Fprintf(f, " sub %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
case IR_MUL:
fmt.Fprintf(f, " mov rax, %s\n", Registers[ir.Rhs])
fmt.Fprintf(f, " mul %s\n", Registers[ir.Lhs])
fmt.Fprintf(f, " mov %s, rax\n", Registers[ir.Lhs])
case IR_DIV:
fmt.Fprintf(f, " mov rax, %s\n", Registers[ir.Lhs])
fmt.Fprintf(f, " cqo\n")
fmt.Fprintf(f, " div %s\n", Registers[ir.Rhs])
fmt.Fprintf(f, " mov %s, rax\n", Registers[ir.Lhs])
case IR_LABEL:
fmt.Fprintf(f, ".L%d:\n", ir.Lhs)
case IR_UNLESS:
fmt.Fprintf(f, " cmp %s, 0\n", Registers[ir.Lhs])
fmt.Fprintf(f, " je .L%d\n", ir.Rhs)
case IR_JMP:
fmt.Fprintf(f, " jmp .L%d\n", ir.Lhs)
case IR_LT:
fmt.Fprintf(f, " cmp %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
fmt.Fprintf(f, " setl %s\n", Registers8[ir.Lhs])
fmt.Fprintf(f, " movzb %s, %s\n", Registers[ir.Lhs], Registers8[ir.Lhs])
case IR_CALL:
for i := range ir.Args {
fmt.Fprintf(f, " mov %s, %s\n", argRegisters[i], Registers[ir.Args[i]])
}
fmt.Fprintf(f, " push r10\n")
fmt.Fprintf(f, " push r11\n")
fmt.Fprintf(f, " mov rax, 0\n")
fmt.Fprintf(f, " call %s\n", ir.Name)
fmt.Fprintf(f, " pop r11\n")
fmt.Fprintf(f, " pop r10\n")
fmt.Fprintf(f, " mov %s, rax\n", Registers[ir.Lhs])
case IR_NOP:
break
default:
logrus.Errorf("Unknown Operator")
}goccの実装では､
Functionという構造体毎に中間表現の配列が格納されています｡
FunctionはC言語のプログラム上で最も大きな単位であり､
#include<stdio.h>
int sum(int a,int b);
int main(void){
int a = 3;
int b = 5;
printf("result:%d\n",sum(a,b));
return 0;
}
int sum(int a,int b){
return a+b;
}でいえば､
mainとsumがそれぞれ構造体 Functionになります｡
Function の持つ中間表現の配列を回し､
次々にアセンブリコードを出力していきます｡
goccにおいて fはファイルディスクリプタのラップであり､
標準出力やファイルなどを操作できる実装になっています｡
コンパイラは言語仕様によって､
バイナリにデータを組み込む､という挙動を示します｡
具体例を紹介します｡
次のようなコードを記述し､
コンパイルしてみます｡
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const char name[] = "Drumato";
int main(void){
char *buf = (char*)malloc(sizeof(char)*strlen(name));
strcpy(buf,name);
printf("%s\n",buf);
return 0;
} .file "c.c"
.intel_syntax noprefix
.text
.globl name
.section .rodata
.align 8
.type name, @object
.size name, 8
name:
.string "Drumato"
.text
.globl main
.type main, @function
main:
push rbp
mov rbp, rsp
sub rsp, 16
mov edi, 7
call malloc@PLT
mov QWORD PTR -8[rbp], rax
mov rax, QWORD PTR -8[rbp]
mov rdx, QWORD PTR name[rip]
mov QWORD PTR [rax], rdx
mov rax, QWORD PTR -8[rbp]
mov rdi, rax
call puts@PLT
mov eax, 0
leave
ret
.size main, .-main
.ident "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
.section .note.GNU-stack,"",@progbits.rodataセクションに nameシンボルが定義されていることがわかります｡
.rodataセクjションはその名の通り読み込み専用領域を表し､
データセグメントの中でも特に静的な空間となっています｡
#include <stdio.h>
#include <string.h>
char name[] = "Drumato";
int main(void) {
strcpy(name, "ahahaha");
printf("%s\n", name);
return 0;
}のようにコードを変更すると､
書き換え可能なデータセグメント(.dataセクション)"Drumato"`が格納されます｡
.file "c.c"
.intel_syntax noprefix
.text
.globl name
.data
.align 8
.type name, @object
.size name, 8
name:
.string "Drumato"
.text
.globl main
.type main, @function
main:
push rbp
mov rbp, rsp
movabs rax, 27417840313264225
mov QWORD PTR name[rip], rax
lea rdi, name[rip]
call puts@PLT
mov eax, 0
pop rbp
ret
.size main, .-main
.ident "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
.section .note.GNU-stack,"",@progbitsmovabsの右オペランドには､
リトルエンディアンで表示されたASCIIコードが入っています｡
(10進数のため見づらいですが)
文字列に限らず､
コンパイラは静的なリテラル値をバイナリに組み込む事で省メモリ化を実現しているのです｡
また､
malloc関数のように 動的にメモリをアロケートする関数は､
プロセス空間のヒープ領域を利用しています｡
この空間は静的にデータが格納されているわけではなく､
プログラムの実行によって動的にデータが格納されていくというわけです｡
アセンブルとは､
先程生成したアセンブリコードをバイナリに変換します｡
変換されたファイルを オブジェクトファイルと言い､
後述しますが ELF形式 に準拠している場合がほとんどです｡
ここからはコンパイラの役割から外れる場合もありますが､
gcc等一般的に用いられるコンパイラは勿論この機能をサポートしています｡
主に行われる事は､
- アセンブリに対応したバイナリに変換する
- ELFフォーマットに準拠したファイルを排出する
の2つです｡
アセンブリはアーキテクチャによって固有の命令セットが用意されており､
それぞれ オペコード を指定することでCPUに命令実行させる事が出来ます｡
オペランドにレジスタが来るのか､即値が来るのか｡
レジスタ(即値)は何ビット長なのかによってオペコードは細かく変化します｡
詳細にはプロセッサの仕様書に記載されていることが多く､
またアセンブラの実装をしている人は多くないため 自作する場合はとても難しいです｡
const (
ASCIICode = 0x0a
AAA = 0x37
AAD = 0xd5
AAM = 0xd4
AAS = 0x3f
ADCAImm8 = 0x14
ADCAImm16 = 0x15
ADCRMImm8 = 0x80
ADCRMImm8_2 = 0x83
ADCRMImm16 = 0x81
ADCRM8 = 0x10
ADCRM16 = 0x11
ADCR8 = 0x12
ADCR16 = 0x13
MovRM32 = 0x89
MovRImm8 = 0xb0
MovRImm16 = 0xb8
MovRImm32 = 0xb8
MovRMImm8 = 0xc6
MovRMImm16 = 0xc7
MovRMImm32 = 0xc7
PushR32 = 0x50
PopR32 = 0x58
)
これは私の自作しているアセンブラのオペコード一覧の一部です｡
x86ニーモニックに対してこのようにオペコードが対応しており､
アセンブル時にはオペランドがレジスタか?即値か?
はたまたビット長は?
などなどを解析しながら機械語に変換していきます｡
上記に示したように機械語に変換したアセンブリコードは､
ELFフォーマットに従ってファイルに配置されます｡
ELFフォーマットについては記事を書いているのでそちらも合わせてご覧ください｡
基本的に命令は.textセクションに格納されていきます｡
またプログラムに利用されるデータ構造は.dataや.bssに格納されます｡
これらセクションはOS( 厳密にはOSに組み込まれているローダ)が､
プログラムを実行する上で必要な情報を辿れるように ヘッダ情報が付与されています｡
逆に言うと､
実行可能なファイルを作成するためには､
ELFフォーマットに準拠したバイナリを構成する必要がある､ということです｡
最後に､プログラムがlibc.so.6等のライブラリを実行ファイルにリンクします｡
動的リンク のバイナリの場合は､
実行時にライブラリを参照出来るようにパス等の情報がDYNAMICセグメントに格納されます｡
実際にlddコマンドを実行してみます｡
$ ldd a.out
linux-vdso.so.1 (0x00007fffeebd9000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fbd78eb0000)
/lib64/ld-linux-x86-64.so.2 (0x00007fbd79600000)のように､libcの情報が表示されています｡
gccを利用する場合､-staticフラグを付けることで 静的リンクが可能になります｡
この場合バイナリにlibc等ライブラリの機能が組み込まれる為､
実行時にライブラリを参照する必要はなくなります｡
そのかわり ファイルサイズは動的リンクに比べとても大きく なります｡
また､ライブラリの情報を格納するセクションが新たに追加されます｡
readelf -hコマンドを用いると詳しく確認できますが､
リンク方式の違いは生成ファイルの違いを生んでいることがわかります｡
同じELFバイナリでも､
動的リンクの場合は DYN (Shared Object File)に､
静的リンクの場合はEXEC (Executable file)になります｡
どちらの場合であれ､この時既に実行可能なバイナリが生成できていると言えます｡
動的リンクの場合は実行時にライブラリを参照するため､
Linux Namespace等の機能でマウント名前空間を変更すれば上手く実行できなくなります｡
