Tacsim の実装 - 実行部分 長谷川啓 2019.02.28.

Presentation on theme: "Tacsim の実装 - 実行部分 長谷川啓 2019.02.28."— Presentation transcript:

1 tacsim の実装 - 実行部分 長谷川啓

2 普通のバックエンド hcc1 ・函数(名前、型等) ファイルに書かれた函数の個数回繰り返される ・函数のパラメータスコープ
・3番地コードの列 ・記号表 ファイルに書かれた函数の個数回繰り返される intel.dll 普通のバックエンドならば、すぐにコード生成するので問題 にならないが・・・

3 函数や(函数の外側の)変数はいつ評価する？
void f(int a) { ... } ※ int x = 5; int main(void) f(3); return 0; hcc1 の現状では f のパラメータスコープや3番地コードは※のポイントで捨てている。 f が static 宣言されていれば現状の実装が活きてくるように思えるが・・・

4 ファイルの最後でまとめて評価する必要がある
int main() { f(); g(); } ※ void f(){ ... } void g(){ ... } このポイントで main の3番地コードを実行しようとしても、f や g をまだ知らないから実行できない。

5 普通のバックエンドとの違い hcc1 hcc1 ・函数 ・3番地コードの列 ・記号表 ファイルに書かれた函数の個数回繰り返される
・函数1 ・函数1の3番地コードの列 ・函数2 ・函数2の3番地コードの列 ・... ・記号表 ・函数 ・3番地コードの列 ・記号表 ファイルに書かれた函数の個数回繰り返される intel.dll tacsim.dll ファイルの最後に到達したときにバックエンドの所定の函数が呼び出される

6 hcc1 → tacsim のインターフェース vector<info> funcs; &scope::root; // 記号表
struct info { fundef* m_func; vector<tac*> m_code; }; // static_inline::info とほぼ同じ &scope::root; // 記号表

7 main 函数を実行するコード 以下の函数を "main" を指定して呼び出す。
bool call_direct(string name, pc_t ra) { vector<info>::const_iterator p = find_if(funcs.begin(),funcs.end(),bind2nd(ptr_fun(cmp_name),name)); if ( p == funcs.end() ) return false; return_address.push_back(ra); allocate_stack(p->m_func->m_parameter); const vector<tac*>& code = p->m_code; pc_t pc = code.begin(); while ( pc != code.end() ){ tac* ptr = *pc; pc = exec(pc); if (*ptr が return3ac ) break; } deallocate_stack(p->m_func->m_parameter); return_address.pop_back(); return true;

8 main 函数を実行する前に記号表の静的なメモリの部分を評価する
これは通常のバックエンドで、函数の3番地コード列をアセンブリに変換する前に行っていることと同じ 静的でないメモリに置かれる変数、つまり函数のローカル変数、中間変数は函数の入り口で評価する。 なので main 函数内のそれらは、やはり main 函数実行前に評価することになる。 静的なメモリには、実際にメモリを割り当てる。初期値があれば、その値もセットする。 似たようなことは通常のバックエンドでも行っている。

9 静的なメモリの初期値はアドレスも参照することができる。
extern void* q; void* p = (void*)&q; void* q = (void*)&p; どのような実装にしても初期値をすぐに計算することができない(と思う)。 だから、アドレスを初期値とするものに関しては、後でまとめて計算したほうが簡単。上の例なら: p のアドレスを決める。 q のアドレスを決める。 p の初期値、q の初期値を計算する。

10 3番地コードのオペランドの扱い(1) 記号表のエントリ
map<string, vector<usr*> > scope::m_usrs; vector<var*> block::m_vars; 各 usr*, var* に必要ならばメモリを確保する 例えば extern int errno; のような宣言にはメモリを割り当てない。 extern 宣言されているユーザー定義の変数はアドレス 0 を割り当てておく。 対応表を作成する typedef map<var*, void*> address_table_t; address_table_t tacsim::memory; stack<address_table_t> tacsim::stack; 定数の扱い 3番地コードの実行部分を簡単にするなら、定数にメモリを割り当て、そこに値をセットしておく。 普通のバックエンドでも long double などのサイズの大きい定数に対しては同じことをしている。 函数の扱い 函数の定義に対して 0 でないアドレスを割り当てる。このアドレスに対して函数呼び出し演算子が適用されたときに、その函数を呼び出せるようにする。 定義ではない宣言に対しては 0 を割り当てておく。

11 3番地コードのオペランドの扱い(2) 記号表のエントリ
函数のパラメータスコープ以下のスコープに関してはその函数が呼び出されたときに対応表を作成し、函数から戻るときに確保したメモリを解放し、対応表を破棄する。 特に、函数のパラメータには連続したメモリを割り当てる。 例 void f(int* p, double d, struct S s){ ... } に対して align(p に確保したアドレス + sizeof p, double ) == d に確保したアドレス align(d に確保したアドレス + sizeof d, struct S) == s に確保したアドレス が満たされるようにする.

12 x := y typedef vector<tac*>::const_iterator pc_t;
pc_t assign(pc_t pc) { tac* ptr = *pc; const type* T = ptr->x->m_type; memcpy(getaddr(ptr->x), getaddr(ptr->y), T->size()); return pc + 1; } こうすれば、T がスカラ型でも構造体型でも問題なし

13 getaddr (1) address_table_t tacsim::memory;
stack<address_table_t> tacsim::stack; メモリ割り当てを行ったもの map<string, void*> external::table; メモリを割り当てていないがライブラリ等で定義されているもの void* getaddr(var* v) { const address_tabl_t& curr = tacim::stack.top(); address_tabl_t ::const_iterator p = curr.find(v); if (p != curr.end()) return p->second; // v はローカル変数か中間変数 p = tacsim::memory.find(v); if (p != tacsim::memory.end()) if ( void* r = p->second ) return r; usr& u = dynamic_cast<usr&>(*v);

14 getaddr (2) } external::table には tacsim のコンパイル時に代表的なものを登録しておく
// tacsim::memory の中から、同じ名前の変数で、函数の外側で定義されていて、メモリが割り当てられているものを探す。 p = find_if(tacsim::memory.begin(), tacsim::memory.end(), bind2nd(ptr_fun(definition),u.m_name)); if ( p != tacsim::memory.end() ) return p->second; map<string, void*>::const_iterator q = external::table.find(u.m_name); if (q != external::table.end()) return q->second; // 例えば errno, printf などがこれに該当する。 throw not_found(u); // 宣言はされているが定義されていない変数。 } external::table には tacsim のコンパイル時に代表的なものを登録しておく

15 x := y + z pc_t add(pc_t pc) { tac* ptr = *pc;
const type* T = ptr->x->m_type; if ( T->real() ){ if ( T->size() == sizeof(float) ) *(float*)getaddr(ptr->x) = *(float*)getaddr (ptr->y) + *(float*)getaddr (ptr->z); else if ( ... ) } else if ( T->integer() ){ 整数の加算 else { ポインタ + 整数か整数+ポインタの加算 return pc + 1;

16 x := y op z のポイント 型 T の op を実際に行う。T は op によるが以下の型が考えられる。
long double, double, float unsigned long long int, long long int, unsigned long int, long int, unsigned int, int ポインタ型 例えば減算で sizeof(long int) = sizeof(int) ならば以下を実際に行う。 long double - long double double - double float - float long long int - long long int int - int ポインタ - ポインタ ポインタ - long long int ポインタ - int op によっては符号付き整数と符号なし整数を区別する必要があったり、なかったりする。また、実数型に対して定義されていなかったりする。

17 x := &y pc_t addr(pc_t pc) { } tac* ptr = *pc;
*(void**)getaddr(ptr->x) = getaddr(ptr->y); return pc + 1; }

18 x := *y pc_t invraddr(pc_t pc) { } tac* ptr = *pc;
const type* T = ptr->x->m_type; memcpy(getaddr(ptr->x), *(void**)getaddr(ptr->y),T->size()); return pc + 1; }

19 x[y] := z pc_t loff(pc_t pc) { } tac* ptr = *pc;
const type* Tz = ptr->z->m_type; char* dst = (char*)getaddr(ptr->x); const type* Ty = ptr->y->m_type; int sy = Ty->size(); int64_t delta = (sy == 4) ? *(int32_t*)getaddr(ptr->y) : *(int64_t*)getaddr(ptr->y); memcpy(dst+delta, getaddr(ptr->z), Tz->size()); return pc + 1; }

20 param y extern vector<pair<void*,const type*> > parameters; pc_t param(pc_t pc) { tac* ptr = *pc; const type* T = ptr->y->m_type; int size = T->size(); void* p = new char[size]; memcpy(p,getaddr(ptr->y),size); parameters.push_back(make_pair(p,T)); return pc + 1; } 函数が呼び出されたときパラメータ全体に連続したメモリを割り当てて、parameters の中身をそこにコピーするようにする。コピーしたら各 i に対して parameters[i].first を解放して parameters.clear() としておく。

21 x := call y, call y pc_t call(pc_t pc) { } pc_t call_via_name(pc_t pc)
tac* ptr = *pc; const type* T = ptr->y->m_type; return T->scalar() ? call_via_ptr(pc) : call_via_name(pc); } pc_t call_via_name(pc_t pc) string name = ptr->y->m_name; if ( !call_direct(name, pc+1) ) { // name は、例えば printf のような、ユーザー定義ではない函数 void* pf = (external::table から計算); const type* T = ptr->y->m_type; // T は函数型 const func_type* ft = static_cast<const func_type*>(T); call_common(ptr->x, pf, ft); return pc + 1;

22 ポインタ経由の函数呼び出し pc_t call_via_pointer(pc_t pc) { tac* ptr = *pc;
void* pf = *(void**)getaddr(ptr->y); if ( pf がユーザー定義の函数のアドレスになっている ) { string name = ...; call_direct(name, pc+1); return pc + 1; } const type* T = ptr->y->m_type; T = T->unqualified(); const pointer_type* pt = static_cast<const pointer_type*>(T); T = pt->referenced_type(); const func_type* ft = static_cast<const func_type*>(T); call_common(ptr->x, pf, ft);

23 call_common(1) 函数の引数の指定は、ターゲットプロセッサと tacsim をコンパイルするコンパイラに依存する。
一般的なRISCプロセッサなら最初の数個の引数は所定のレジスタに値をセット それ以降の引数は、スタックポインタ相対位置にループしてセット 一般的なCISCプロセッサならこっちのみ

24 call_common(2) enum kind_t { }; union U {
NONE, LD, DOUBLE, FLOAT, U64, S64, U32, S32, U16, S16, U8, S8, VP, REC }; union U { long double ld; double d; float f; uint64_t u64; int64_t s64; uint32_t u32; int32_t s32; uint16_t u16; int16_t s16; uint8_t u8; int8_t s8; void* vp; struct uks { U m_u; kind_t m_kind; int m_size; }; void call_common(var* x, void* pf, const func_type* ft) { const vector<const type*>& param = ft->param(); int nth = (param から計算する。ft が可変個引数をとるならば最初の何引数の型が指定されているか、可変個引数をとらないならば numeric_limits<int>::max()); vector<uks> Us; transform(params.begin(),params.end(),back_inserter(Us), conv);

25 call_common(3) for_each(params.begin(), params.end(), destroy<void*, const type*>()); params.clear (); T = ft->return_type(); int size = T->size(); U r; r.vp = T->aggregate() ? new char[size] : 0; kind_t rk = conv_type(T); call_Us(&r, pf, &Us[0], &Us[Us.size()],nth,rk); if ( x ) { void* p = T->aggregate() ? r.vp : &r ; memcpy(getaddr(x), p, size); }

26 call_Us intel x64, Visual Studio 版(1)
rsp pf を呼び出すとき の引数 call_Us 実行時に t0 := end - begin t1 := t0 / sizeof(uks) t2 := t1 * 8 を計算して t2 の分だけ rsp をずらすことになる call_Us の ローカル変数 中間変数 rbp

27 call_Us intel x64, Visual Studio 版(2)
// void call_Us(U* r, void* pf, uks* begin, uks* end, int nth, kind_t rk) // ここからはマイクロソフトアセンブラで書く rsp を `pf' の引数の分だけずらす。 if (r->vp){ // 函数 pf の戻り値は構造体型 // rcx に r->vp をセットする }

28 call_Us intel x64, Visual Studio 版(3)
uks* p = begin; if (p == end) goto LAST; if (p->m_kind <= kind_t::FLOAT) { // 第1引数は実数型 // nth が 0 ならば float は double に変換する。 r->vp が 0 ならば rcx に、r->vp が 0 でなければ rdx に値をセット // nth が 0 でなければ xmm0 に値をセット } else if (p->m_kind <= kind_t::VP) { // 第1引数は整数型かポインタ型 // nth が 0 ならば格上げする。r->vp が 0 ならば rcx に、r->vpが0でなければ rdx に値をセット else { // 第1引数は構造体型 // r->vp が 0 ならば rcx に、そうでなければ rdx に構造体の先頭アドレスをセット // ここまでが第1引数の処理

29 call_Us intel x64, Visual Studio 版(4)
++p; if (p == end) goto LAST; if (p->m_kind <= kind_t::FLOAT) { // 第2引数は実数型 // nth が 1 以下ならばfloat は double に変換する。 r->vp が 0 ならば rdx に、r->vp が 0 でなければ r8 に値をセット // nth が 1 以下でなければ xmm1 に値をセット } else if (p->m_kind <= kind_t::VP) { // 第2引数は整数型かポインタ型 // nth が 1 以下ならば格上げする。r->vp が 0 ならば rdx に、r->vpが0でなければ r8 に値をセット else { // 第2引数は構造体型 // r->vp が 0 ならば rdx に、そうでなければ r8 に構造体の先頭アドレスをセット // ここまでが第2引数の処理

30 call_Us intel x64, Visual Studio 版(5)
第1引数と第2引数の処理は似通っているので、マクロを書くのがよい: #define SET_REG_MACRO(NNN, GPR1, GPR2, XMMN) ... ... uks* p = begin; SET_REG_MACRO(0, rcx, rdx, xmm0); // 第1引数 ++p; SET_REG_MACRO(1, rdx, r8, xmm1); // 第2引数 SET_REG_MACRO(2, r8, r9, xmm2); // 第3引数

31 call_Us intel x64, Visual Studio 版(6)
++p; // p は第4引数を指している if (p == end) goto LAST; int narg = p - begin; // 第何引数を処理しているかを表す if (!r->vp) { // 第4引数は、第1、第2、第3引数と同様に xmm3 か r9 レジスタで渡す。 ++p; // p は第5引数を指している ++narg; }

32 call_Us intel x64, Visual Studio 版(7)
for (int offset = 32 ; p != end ; ++p, ++narg, offset += 8 ) { // p->m_kind に応じた値をrsp 相対offset の位置にセットする。nth が narg 以下ならば float は double に、整数型は格上げした値にする } LAST: pf(); // ポインタ経由の函数呼び出し。すなわち intel x64 なら // pf の値を rax にセットする // call rax

33 call_Us intel x64, Visual Studio 版(8)
// pf の戻り値が構造体の場合は何もしなくてよい。 // 戻り値がスカラ型の場合は rax, xmm0 のいずれかに入っている。 if (rk == kind_t::NONE) return; if (rk <= kind_t::FLOAT) { // 戻り値は実数型。xmm0 を r->ld, r->d, r->f に適切に書き込む。 } else if (rk <= kind_t::VP) { // 戻り値は整数型かポインタ。rax を r->u64 に書き込む。

34 call_Us intel x64, g++ 版(1) Visual Studio 版との差異
long double 型の引数は構造体のようにコピーを作ってアドレス渡しにする pf が long double 型を返す函数へのポインタならば、やはり構造体のように戻り値を書き込むアドレスを rcx レジスタにセットする. gcc のインラインアセンブラを使用するとよい

35 call_Us intel x64, g++ 版(2) call_Us:
// void call_Us(U* r, void* pf, uks* begin, uks* end, int nth, kind_t rk) rsp をずらす。 if (rk == kind_t::REC || rk == kind_t:: LD){ // 函数 pf の戻り値は構造体型か long double 型 // 構造体型なら rcx に r->vp をセットする // long double 型なら rcx に &r->ld をセットする }

36 call_Us intel x64, g++ 版(3) uks* p = begin; if (p == end) goto LAST;
if (p->m_kind <= kind_t::FLOAT) { // 第1引数は実数型 if ( p->m_kind == kind_t::LD ) { long double tmp = p->m_u.ld; // tmp は第1引数とその他の引数とでそれぞれ別に確保する rk == kind_t::REC || rk == kind_t::LD ならば rcx に、 rk == kind_t::REC || rk == kind_t::LD でなければ rdx に &tmp をセット } else { // nth が 0 ならば float は double に変換する。 rk == kind_t::REC || rk == kind_t::LD ならば rcx に、 rk == kind_t::REC || rk == kind_t::LD でなければ rdx に値をセット // nth が 0 でなければ xmm0 に値をセット else ... // ここまでが第1引数の処理

37 call_Us intel x64, g++ 版(4) ... LAST: pf(); // ポインタ経由の函数呼び出し
// pf の戻り値が構造体か long double の場合は何もしなくてよい。 if (rk == kind_t::NONE) return; if (rk <= kind_t::FLOAT) { // 戻り値は実数型。xmm0 を r->d, r->f に適切に書き込む。特に、r->ld は変更してはならない。 } else if (rk <= kind_t::VP) { // 戻り値は整数型かポインタ。rax を r->u64 に書き込む。

38 call_Us intel x86, g++ 版 (1) esp pf を呼び出すとき 構造体はベタっと貼り付けられる の引数
int n = accumulate(begin, end,0,add_size); int add_size(int n, uks* p){ return n + p->m_size; } を計算して n の分だけ esp をずらすことになる 構造体はベタっと貼り付けられる call_Us の ローカル変数 中間変数 ebp

39 call_Us intel x86, g++ 版 (2) x64, g++ 版との差異 引数はすべてスタックポインタ相対で渡す。
long double 型の引数も構造体型の引数もスタックにコピーを貼り付ける。 pf の戻り値の型 整数型かポインタ型 eax レジスタに入っている 実数型 浮動小数点スタックのトップ(st0) に入っている 構造体型、共用体型 戻り値をセットする領域は確保されているので、そのアドレスを第一引数として渡す。rcx を使わないことを除けば x64, g++ 版と同じ。

40 call_Us intel x86, g++ 版 (3) call_Us:
// void call_Us(U* r, void* pf, uks* begin, uks* end, int nth, kind_t rk) esp をずらす。 int offset = 0; if (rk == kind_t::REC){ // 函数 pf の戻り値は構造体型 // スタックポインタオフセット 0 に r->vp をセットする offset += sizeof(void*); }

41 call_Us intel x86, g++ 版 (4) for ( uks* p = begin ; p != end ; ++p ){
p->m_kind に応じて p->m_u のメンバを参照し、スタックポインタ相対 offset の位置にセットする。 int size = p->m_size; offset += (size <= sizeof(int)) ? sizeof(int) : size; } switch (rk) { case NONE: case REC: ((void (*)())pf)(); return; case LD: r->ld = ((long double (*)())pf)(); return; ...

42 return y, return extern vector<vector<tac*>::const_iterator> return_address; pc_t return_(pc_t pc) { tac* ptr = *pc; pc = return_address.back(); tac* call = *(pc - 1); // 呼び出した call3ac if ( ptr->y ){ const type* T = ptr->y->m_type; int size = T->size(); if ( call->x ) memcpy(getaddr(call->x), getaddr(ptr->y),size); } return pc; // 実際は無視されるが、戻りアドレスでも返しておく。

43 goto, to pc_t goto(pc_t pc) { } pc_t to(pc_t pc){ return pc + 1; }
tac* ptr = *pc; if ( ptr->m_op ) return ifgoto(pc); const vector<tac*>& code = current_code(); // 現在シミュレートしている函数の3番地コード列を取得できるようにしておく pc_t p = find(code.begin(), code.end(), ptr->m_to); assert( p != code.end() ); return p; } pc_t to(pc_t pc){ return pc + 1; }

44 ifgoto (1) pc_t ifgoto(pc_t pc) { tac* ptr = *pc;
const type* T = ptr->y->m_type; if ( T->real() ){ switch(T->size()){ case sizeof(float): bool (*pred)(float, float) = table[ptr->m_op]; if ( pred(*(float*)getaddr(ptr->y), *(float*)getaddr(ptr->z)){ const vector<tac*>& code = current_code(); return find(code.begin(),code.end(),ptr->m_to); } return pc + 1; ... else {

45 ifgoto (2) 実際に型 T について比較演算を行う
long double, double, float, unsigned long long int, long long int, unsigned long int, long int, unsigned int, int, ポインタの比較 == や != に関しては整数の符号付き、符号なしは区別する必要はない。一方で、sizeof(int) バイト未満の比較がある。

46 alloca x, y pc_t alloc(pc_t pc) { tac* ptr = *pc;
const type* T = ptr->y->m_type; uint64_t size; if (T->size() == 4) size = *(uint32_t*)getaddr(ptr->y); else { assert(T->size()==8); size = *(uint64_t*)getaddr(ptr->y); } address_table_t& curr =tacsim::stack.top(); curr[ptr->x] = new char[size]; // このタイミングでテーブルに登録する。 return pc + 1;

47 asm "string" そもそも eval できないので実装できない。

48 函数のパラメータ 函数の入り口で param y で使用したグローバル変数
extern vector<pair<void*,const type*> > parameters; を連続した領域にコピーする: int n = accumulate(parameters.begin(),parameters.end(),0,add_size); char* p = n ? new char[n+alpha] : 0; // 連続した領域。第一引数のアラインメントの都合から少しだけ多めに確保。 accumulate(parameters.begin(),parameters.end(),p,save_param); parameters[i].first から parameters[i].second->size() 分 p の指す領域にコピーしたら p を進めて params[i+1].first を再び p の指す領域にコピーする. for_each(parameters.begin(), parameters.end(), destroy<void*, const type*>()); parameters.clear (); param_scope* ps = (呼び出された函数のパラメータスコープ); const vector<usr*>& order = ps->m_order; accumulate(order.begin(), order.end(), p, decide_address);

49 x := va_start y pc_t vastart(pc_t pc) { } tac* ptr = *pc;
char* p = (char*)getaddr(ptr->y); const type* T = ptr->y->m_type; int size = T->size(); *(char**)getaddr(ptr->x) = p + size; return pc + 1; }

50 x := va_arg y, T tac* ptr = *pc;
pc_t vaarg(pc_t pc) { tac* ptr = *pc; char* src = *(char**)getaddr(ptr->y); va_arg3ac* varg = static_cast<va_arg3ac*>(ptr); const type* T = varg->m_type; src = align(src, T->align()); int size = T->size(); memcpy(getaddr(ptr->x), src, size); *(char**)getaddr(ptr->y) = size + size; return pc + 1; }