コンパイラ 2012年11月12日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html.

Presentation on theme: "コンパイラ 2012年11月12日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html."— Presentation transcript:

1 コンパイラ 2012年11月12日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)

2 コンパイラと実行環境の連携１ ＯＳ 実行環境 プロセスやファイルシステムなど仮想化したハードウェアを提供
プログラミング言語に依存しない汎用的なインターフェース 実行環境 プログラミング言語固有のサービス メモリ管理（たとえば、割り付け・自動開放） スレッド管理（生成・消滅・同期・相互排除） 初期化処理 Ｃ言語の場合、この初期化処理だけで、限定的に動かすことができる ライブラリ 明示的に利用するもの・暗黙的に利用されるもの コンパイラと同時に開発する必要があるモノ もし、仮想化も汎用性も不要なら、ハードウェアを直接操作すればよく、ＯＳは不要。そうすると、Ｃでは最低限、コンパイラと初期化処理だけあればいい。

3 実行環境 ソースコード オブジェクト コード コンパイラ ＯＳ リンク ライブラリ 実行環境 システムコール

4 実行環境とコンパイラ たとえば、lookUpReturnAddressInException() たとえば、キャスト。
例外検査コードを生成するとしても、いちいち表を調べる コードをオブジェクトコードに入れておくことは無駄である。 通常はコンパイラが、そういったサブルーチンを呼ぶ。 たとえば、キャスト。 実行時の型検査、例外生成あるいは型変換、といった一連 の手続きを、いちいちコード生成しててはメモリを消費する。 こういったものも、コンパイラがサブルーチンを呼ぶ。 実行時に呼ばれる、そのような様々なサブルーチンも 実行環境であり、コンパイラとペアで開発する。

5 Garbage Collection (ごみ集め)
メモリ割り付けと開放の自動化・機械化 Lispでは、メモリは自動で割り付けられ自動で開放される 割り付けはオブジェクト生成時に行われる 使われていないオブジェクトのメモリは、ころあいを見て開放される Ｊａｖａでは、開放だけが機械化されている。 割り付けは new オペレータで、明示的に行う。 Ｃでは、メモリ割り付け・開放については機械化されていない。 malloc()/free() という、ライブラリ関数があるのみ。 メモリの開放に関する問題 開放忘れ：使用可能なメモリの不足による停止 二重開放：メモリ内容の意図せぬ変更によるプログラムの暴走。 不要メモリを機械的に回収し開放する。→ GC マニュアル化→自動化。人手を介在しないで処理が行われるのは機械化。

6 javaコマンド（Java VM Emulator）
Ｊａｖａｃ　（静的コンパイラ） ＯＳ Java 実行環境 ソースコード クラス ファイル その他 is_instance_of()など メモリ管理 newInstance()など スレッド管理 EnterSynchronizedBlock() ExitSynchronizedBlock()など javaコマンド（Java VM Emulator） クラスローダ 動的コンパイラ インタプリタ 例外処理 暗黙のnull検査、スタックバンギング用シグナルハンドラ lookUpReturnAddressInException()など 標準クラスライブラリ java.lang.System クラス java.io.orintStream クラス Ｃ言語の極端な例では、 スタックポインタを設定しmain()を呼ぶだけの初期化処理でもいい。 実行環境として、機械語で数命令書けば動くということ。 コンパイラ・アセンブラ・リンケージエディタ、といった コマンドだけでよい例は、 学群実験でやった。 Javaは、Ｃ言語より楽だ。 でも実行環境は相応に 大きく複雑になる。

7 静的コンパイラ プログラムを実行する前にコンパイルするコンパイラ
普通のコンパイラ。 Javaでは、利用者の書いたプログラムをコンパイルして 得た、Java VM向けのバイトコードが出力される。 class ファイルが生成される。 javaコマンド実行により、次の処理が行われる。 Java VM の初期化。 引数の class ファイルを読み、main() を探す。 class loader により、外部参照を解決する。 class ファイルや、jar ファイルを決められた順で探す。

8 動的コンパイラ Java VM はエミュレーションなので、やはり遅い
native code に静的コンパイルしないことで、class ファイル （オブジェクトファイル）を機種非依存にできたことは利点。 そこで、必要に応じて、javac (Java VM emulator) で、 バイトコードを native code に翻訳する。 バイトコードと native code を切り替えながら実行する。 ちなみに、native code 実装したメソッドなどを、 java プログラムから呼び出す手段がある。 混ぜて実行できるくらいなので、当然といえば当然。

9 標準クラスライブラリ 実行環境が用意する標準的なライブラリ群 ＧＵＩ bean Java 固有 数学 ネット I/O セキュリティ
text 処理 ユーティリティ

10 Write once, run anywhere にも例外がある
ずーっと前の情報工学実験 JavaからWebカメラを使って画像をキャプチャしていた。 もちろん標準クラスライブラリにはキャプチャ用クラスはない。 当然ながら、ＯＳ経由でカメラを直接操作するクラスがない。 実はJavaにも、非標準的実装方法ある。 もちろん方法は標準化してある。 JNI (Java Native Interface) 無いものは仕方ないという状況で、どうするか？ あきらめてもらう。 Javaは使ってもらえなくなるかもしれない。 プログラマに非標準的実装方法を提供する。 Java VMコードではなく、java VMが動作する環境のコードで「実装」。

11 public class WebCam { public WebCam() { if(initializeWebCam("/dev/video0", 640, 480)){ throw new java.lang.IllegalArgumentException(); } public WebCam(String device) { if(initializeWebCam(device, 640, 480)){ public WebCam(int width, int height) { if(initializeWebCam("/dev/video0", width, height)){ public WebCam(String device, int width, int height) { if(initializeWebCam(device, width, height)){ private static native boolean initializeWebCam(String device, int width, int height); public static native void finalizeWebCam(); public static native int getWidth(); public static native int getHeight(); public static native int[] grabPixels(int[] array); public static native byte[] grabPixels(byte[] array); static { System.loadLibrary("WebCam");

12 #include <jni.h>
#include "WebCam.h" #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <errno.h> #include <sys/types.h> #include <sys/mman.h> #include <sys/fcntl.h> #include <sys/ioctl.h> #include <time.h> #include <linux/videodev.h> #ifdef USE_MMX #include <mmintrin.h> #endif #define SYNC_TIMEOUT 1 /* device stuff */ static int bt848, gb_grab, gb_sync, even, start; static char *gb_frame; static int *gb_work; static struct video_mbuf gb_buffers; static struct video_mmap gb_even, gb_odd; /* geometry stuff */ static int cols, rows, pxls; /* * Class: WebCam * Method: getWidth * Signature: ()I */ JNIEXPORT jint JNICALL Java_WebCam_getWidth(JNIEnv *env, jclass obj) { return cols; } * Method: getHeight Java_WebCam_getHeight(JNIEnv *env, jclass obj) return rows; static void YUV420PtoYRGB(unsigned char *dest, unsigned char *src) int i, j; unsigned char *yp0, *yp1, *dp0, *dp1; unsigned char *up, *vp; int vu; __m64 gb, yr, yrgb, yyyy0, yyyy1, vuvu; short int vu_gb[4], vu_yr[4]; vu_gb[0] = 454; vu_gb[1] = 0; vu_gb[2] = -88; vu_gb[3] = -183; vu_yr[0] = 0; vu_yr[1] = 359; vu_yr[2] = 0; vu_yr[3] = 0; up = src + pxls; vp = up + pxls/4; yp1 = src; dp1 = dest; for(i = 0; i < rows; i+=2){ yp0 = yp1; yp1 = yp0 + cols; dp0 = dp1; dp1 = dp0 + 4*cols; for(j = 0; j < cols; j+=2){ vu = (*vp ) << 16; /* v */ vu |= (*up ) & 0x0000FFFF; /* u */ vuvu = _mm_cvtsi32_si64(vu); vuvu = _mm_unpacklo_pi32(vuvu, vuvu); gb = _mm_srai_pi32(_mm_madd_pi16(vuvu, *((__m64 *)vu_gb)), 8); yr = _mm_srai_pi32(_mm_madd_pi16(vuvu, *((__m64 *)vu_yr)), 8); yrgb = _mm_packs_pi32(gb, yr); yyyy0 = _mm_unpacklo_pi8(*((__m64 *)yp0), _mm_setzero_si64()); yyyy0 = yyyy1 = _mm_unpacklo_pi16(yyyy0, yyyy0); yyyy0 = _mm_add_pi16(_mm_unpacklo_pi32(yyyy0, yyyy0), yrgb); yyyy1 = _mm_add_pi16(_mm_unpackhi_pi32(yyyy1, yyyy1), yrgb); yyyy0 = _mm_packs_pu16(yyyy0, yyyy1); *((__m64 *)dp0) = yyyy0; yp0 += 2; dp0+= 8; yyyy0 = _mm_unpacklo_pi8(*((__m64 *)yp1), _mm_setzero_si64()); *((__m64 *)dp1) = yyyy0; yp1 += 2; dp1+= 8; _mm_empty(); #else int u, v; int r, g, b; yp0 = src; src += cols; dp0 = dest; dest += 4*cols; u = *up ; v = *vp ; r = (359*v) >> 8; g = (-88*u - 183*v) >> 8; b = (454*u) >> 8; dp0[0] = ((b + yp0[0]) > 255)? 255: ((b + yp0[0]) < 0)? 0: (b + yp0[0]); dp0[1] = ((g + yp0[0]) > 255)? 255: ((g + yp0[0]) < 0)? 0: (g + yp0[0]); dp0[2] = ((r + yp0[0]) > 255)? 255: ((r + yp0[0]) < 0)? 0: (r + yp0[0]); dp0[3] = yp0[0]; dp0[4] = ((b + yp0[1]) > 255)? 255: ((b + yp0[1]) < 0)? 0: (b + yp0[1]); dp0[5] = ((g + yp0[1]) > 255)? 255: ((g + yp0[1]) < 0)? 0: (g + yp0[1]); dp0[6] = ((r + yp0[1]) > 255)? 255: ((r + yp0[1]) < 0)? 0: (r + yp0[1]); dp0[7] = yp0[1]; dp1[0] = ((b + yp1[0]) > 255)? 255: ((b + yp1[0]) < 0)? 0: (b + yp1[0]); dp1[1] = ((g + yp1[0]) > 255)? 255: ((g + yp1[0]) < 0)? 0: (g + yp1[0]); dp1[2] = ((r + yp1[0]) > 255)? 255: ((r + yp1[0]) < 0)? 0: (r + yp1[0]); dp1[3] = yp1[0]; dp1[4] = ((b + yp1[1]) > 255)? 255: ((b + yp1[1]) < 0)? 0: (b + yp1[1]); dp1[5] = ((g + yp1[1]) > 255)? 255: ((g + yp1[1]) < 0)? 0: (g + yp1[1]); dp1[6] = ((r + yp1[1]) > 255)? 255: ((r + yp1[1]) < 0)? 0: (r + yp1[1]); dp1[7] = yp1[1]; static int grab_queue(struct video_mmap *gb) if (-1 == ioctl(bt848,VIDIOCMCAPTURE,gb)) { perror("ioctl VIDIOCMCAPTURE"); return -1; gb_grab++; return 0; grab_wait(struct video_mmap *gb) int ret = 0; alarm(SYNC_TIMEOUT); if (-1 == ioctl(bt848,VIDIOCSYNC,&(gb->frame))) { perror("ioctl VIDIOCSYNC"); ret = -1; gb_sync++; alarm(0); return ret; * Method: grabPixels * Signature: ([I)[I JNIEXPORT jintArray JNICALL Java_WebCam_grabPixels___3I(JNIEnv *env, jclass obj, jintArray array) if((*env)->GetArrayLength(env, array) < pxls){ return NULL; if (gb_grab == gb_sync){ /* started */ start = clock(); if (-1 == grab_queue(even ? &gb_even : &gb_odd)){ if (-1 == grab_queue(even ? &gb_odd : &gb_even)){ grab_wait(even ? &gb_even : &gb_odd); even = !even; YUV420PtoYRGB((unsigned char *)gb_work, (gb_frame + gb_buffers.offsets[even ? 1 : 0])); (*env)->SetIntArrayRegion(env, array, 0, pxls, gb_work); return array; * Signature: ([B)[B JNIEXPORT jbyteArray JNICALL Java_WebCam_grabPixels___3B(JNIEnv *env, jclass obj, jbyteArray array) if((*env)->GetArrayLength(env, array) < pxls*3/2){ (*env)->SetByteArrayRegion(env, array, 0, pxls*3/2, (gb_frame + gb_buffers.offsets[even ? 1 : 0])); * Method: finalizeWebCam * Signature: ()V JNIEXPORT void JNICALL Java_WebCam_finalizeWebCam(JNIEnv *env, jclass obj) double elapsed; if (gb_grab > gb_sync){ elapsed = (double)(clock() - start)/CLOCKS_PER_SEC; munmap(gb_work, (pxls* ) & ~4095); munmap(gb_frame, gb_buffers.size); close(bt848); gb_sync--; fprintf(stderr, "%d frames grabbed in %.1f seconds(%.1f[fps]).\n", gb_sync, elapsed, (double)gb_sync/elapsed); gb_sync = gb_grab = even = 0; initialize(void) struct video_capability vcap; struct video_channel vchan; struct video_picture vpic; /* find video capture card */ if(ioctl(bt848, VIDIOCGCAP, &vcap)){ fprintf(stderr, "Can't get video capability.\n"); return 1; fprintf(stderr, "Video capture card is \"%s\".\n" "Width: %d - %d, Height: %d - %d\n", vcap.name, vcap.minwidth, vcap.maxwidth, vcap.minheight, vcap.maxheight); if((cols & 1) || (rows & 1) || (vcap.minwidth > cols) || (cols > vcap.maxwidth) || (vcap.minheight > rows) || (rows > vcap.maxheight)){ for(vchan.channel = 0; vchan.channel < vcap.channels; vchan.channel++){ if(ioctl(bt848, VIDIOCGCHAN, &vchan)){ fprintf(stderr, "Can't get channel info.\n"); if(vchan.flags & VIDEO_VC_TUNER){ continue; if(vchan.type & VIDEO_TYPE_CAMERA){ vchan.norm = VIDEO_MODE_NTSC; ioctl(bt848, VIDIOCSCHAN, &vchan); fprintf(stderr, "Video source is set to \"%s\".\n", vchan.name); break; if(vchan.channel == vcap.channels){ fprintf(stderr, "Can't find camera.\n"); /* set picture */ vpic.brightness = vpic.hue = vpic.colour = vpic.contrast = vpic.whiteness = 32768; vpic.depth = 12; vpic.palette = VIDEO_PALETTE_YUV420P; if(ioctl(bt848, VIDIOCSPICT, &vpic)){ fprintf(stderr, "Can't set YUV420P.\n"); gb_even.frame = 0; gb_odd.frame = 1; gb_odd.format = gb_even.format = vpic.palette; gb_odd.width = gb_even.width = cols; gb_odd.height = gb_even.height = rows; /* map grab buffer */ if (-1 == ioctl(bt848,VIDIOCGMBUF,&gb_buffers)) { perror("ioctl VIDIOCGMBUF"); gb_frame = mmap(0,gb_buffers.size,PROT_READ|PROT_WRITE,MAP_SHARED,bt848,0); if ((char*)-1 == gb_frame) { perror("mmap"); fprintf(stderr, "%d buffers starting at %p. Frame buffer size is %d.\n", gb_buffers.frames, gb_frame + gb_buffers.offsets[0], (gb_buffers.offsets[1] - gb_buffers.offsets[0])); /* map working area */ gb_work = mmap(0, (pxls* ) & ~4095, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0); if((int *)-1 == gb_work){ * Method: initializeWebCam * Signature: (Ljava/lang/String;II)Z JNIEXPORT jboolean JNICALL Java_WebCam_initializeWebCam (JNIEnv *env, jclass obj, jstring device, jint width, jint height) const jbyte *str; cols = width; rows = height; pxls = cols*rows; /* open video camera device */ str = (*env)->GetStringUTFChars(env, device, 0); bt848 = open(str, O_RDWR); if (bt848 < 0) { fprintf(stderr, "failed to open device %s\n", str); (*env)->ReleaseStringUTFChars(env, device, str); return JNI_TRUE; if(initialize()){ return JNI_FALSE;

13 メモリ管理 プログラムの実行に必要なメモリ領域の確保・管理・開放 ＯＳの上で動く場合 ＯＳへのメモリ要求
brk()・sbrk()やvalloc()やmmap()システムコール 獲得したメモリのJavaプログラムへの割り付け・回収 ＯＳへのメモリ返却 メモリ管理 方式 比較項目 手動 自動 実行時スタック ごみ集め 適用範囲 広い 狭い 除去困難なバグを生成する確率 大 なし オーバーヘッド 小

14 実行時スタック 関数やメソッド内の局所変数領域として使われる スタックポインタだけでメモリ管理機構が実装できる
エントリー時に確保、return 時に開放。 スタックポインタだけでメモリ管理機構が実装できる たいていは、プロセッサによるサポートがある。 特定のレジスタがスタックポインタになってる。 スタックフレームを形成・破棄する機械語命令がある。 スタックポインタの操作だけなのでオーバーヘッドが少ない。 コンパイラがスタック操作コードを生成するので 開放ミスはない 原理的に静的な割り付けができない ポインタで参照してても、return 後には必ず消滅する。

15 ※ object変数はスタックフレームに置かれてますが、 object変数が指す本体はヒープに置かれている。
メソッド呼び出し メソッドからの返戻 空き領域 newInstance()の スタックフレーム Example8_methos2()の Example8_method1()の Example8_main()の スタックポインタ (TOS) 変数objectの内容 を保存する場所 ※ object変数はスタックフレームに置かれてますが、 object変数が指す本体はヒープに置かれている。

16 Heap (ヒープ) 静的データ・実行時スタック以外のメモリ領域 ヒープを使う方法に３とおりある。
静的データの一部をあらかじめ割り付ける方法もある たいていはＯＳから随時割り当てられた仮想記憶領域 ＯＳからはページングサイズで割り当てられたりして使いにくい ヒープを使う方法に３とおりある。 オブジェクトへの割り付けも開放も手動 Ｃ言語のmalloc()/free()が典型例 オブジェクトへの割り付けは手動、開放は自動 Java のnew 開放はＧＣが安全に機械的に行う 割り付けも開放も自動 LispやSchemeなど

17 手動によるメモリ管理 うまく書ければ最高の効率でメモリが管理できる？
必要なときに確保し、不要になった時点で即開放すれば、 メモリ領域は効率よく再利用されていいかもしれない。 現実には… 間違いなくfree()することはとても面倒 フローグラフ上で、free() する位置が異なるブロックに現れる malloc()コードと対応するfree()を常に同時に記述・抹消する メモリ割り当てが成功したかどうかの検査も面倒 メモリ割り当て失敗はプログラマの責任じゃないでしょう。 オブジェクトの性質に応じたメモリの割り当ての区別が面倒 スクラッチパッド用の細かなデータ領域 行列演算用領域 フレームバッファ用領域

18 Garbage Collection の必要性
割り付けはオブジェクトが生成されるとき、という明確な タイミングがある。一方で開放には、そこまで明確な タイミングがない。 free()に関する次の問題をＧＣが解決する 開放忘れ （短期的には）ヒープを圧迫する ＯＳからメモリを一方的に獲得し続ける結果、システム不安定をきたす 誤開放 使用中のエリアを開放して、再利用されたら暴走しかねない 二重開放 開放済み領域を再び開放したら、ヒープ管理が破綻しかねない