Compiler Construction Lecture No.8

Micro-C の全体構成

全体構成をつかみ、Cの文法を思い出しながら、個々の関数を読んでいくことにより、実際的なcompilerの詳細を理解して欲しい。自分で、すべてを理解しなくては、どんなプログラムでも完成させることはできない。あてずっぽうにコードを書いても、それは絶対に動くことはないし、それは、他のコードに影響を与え、正しい部分まで汚染してしまう。バグは避けられないものではあるが、自分で書いたコードを完全に理解していれば、どのようなバグにも対処できる。

Micor-C の全体構成

mc のコンパイル

/usr/open から Micro-C のソースをとってきてコンパイルしよう。

	cp -r /usr/open/lectures/kono/compiler/mc-intel  .
	cd mc-intel
	make

Mule の gdb mode

Mule (Emacs) には、gdb mode というのが付いている。コンパイラの動作をこれを使って調べる。

    M-X gdb

制御構造のコンパイル

コンパイラ全体の中から見ると制御構造のコンパイルは、それほど大きくない。statement()という一つの構文要素の中で閉じている。例えば、doif()では、if文の処理をおこなう。

   742  doif()
   743  {int l1,l2,slfree;
   744          getsym();
   745          checksym(LPAR);
   746          slfree=lfree;
   747          bexpr(expr(),0,l1=fwdlabel());
   748          lfree=slfree;
   749          checksym(RPAR);
   750          statement();
   751          if(sym==ELSE)
   752          {       if (l2 = control) jmp(l2=fwdlabel());
   753                  fwddef(l1);
   754                  getsym();
   755                  statement();
   756                  if (l2) fwddef(l2);
   757          }
   758          else fwddef(l1);
   759  }

l1=fwdlabel()というのが未来に使うラベルの生成を行っている。ラベルの位置が決まった時点でfwddef(l1)を行う。if文にはelse 節がある場合があり、その場合には、ラベルは二つ必要である。(controlの役目はなにか?)

これと、ラベルにjumpするjump(label)を使えば、ほとんどの制御構造のコード生成が可能となる。残りは、switch文やreturn文、そして、関数呼び出しである。

条件分岐の取り扱い

条件分岐は、構文解析はexpr()を使うが、コード生成がgexpr()とは異なり、bexpr()により処理がおこなわれる。bexpr()は、引き数として、構文木、条件、ラベルを取り、構文木の一番上が条件比較だったら、それお条件分岐に書き換えている。

  1560  bexpr(e1,cond,l1)
  1561  int e1,l1;
  1562  char cond;
  1563  {int e2,l2;
  1564          if (chk) return;
  1565          e2=cadr(e1);
  1566          switch(car(e1))
  1567          {case LNOT:
  1568                  bexpr(e2,!cond,l1);
  1569                  return;
  1570          case GT:
  1571                  rexpr(e1,l1,cond?"GT":"LE");
  1572                  return;
  1573          case UGT:
  1574                  rexpr(e1,l1,cond?"HI":"LS");
  1575                  return;

基本ブロックとフローグラフ

式の単位での最適化と、式を越えた大域的な最適化を考えるために、基本ブロック(Basic Block)とフローグラフ(Flow Graph)というものが工夫された。

基本単位は、単純に言えば、条件分岐や分岐を含まない逐次計算の部分である。フローグラフは、一つの手続の中で基本ブロックを分岐を結んだものである。

mc.c の reverse() はリストを逆順にするものだが、

   484	reverse(t1)
   485	int t1;
   486	{int t2,t3;
   487		t2=t1;
   488		while(type!=t1)
   489		{	t3=heap[type+1];
   490			heap[type+1]=t2;
   491			t2=type;
   492			type=t3;
   493		}
   494		type=t2;
   495	}

としてよい。

このフローグラフを考えてみよう。このフローグラフ(flow graph)を作るには、まず基本ブロック(basic block) を抜きだす。基本ブロックは、分岐(barch)の入らない部分のまとまりをさす。次に、flow-chart のように基本ブロックを接続する。あと、入力される変数と、出力される変数を記述する。

flow-chart と違い、基本ブロックは最適化の単位となるので、可能な限り一つにまとめなければならない。結果は以下のようになる。

基本ブロック

基本ブロック内部では条件分岐がないので、文(statement)の実行順序(execution order)をプログラムの意味を変えない範囲で変更してコンパイルして良い。これは局所的最適化と呼ばれる。

基本ブロックの間で再利用出来る式、計算する必要のない式、あるいは、使わない変数などを見つけると、それらを共有したり、削ったりすることができる。さらに、簡単なループの場合は内部の基本ブロックの定数などをループの外に出すことも行われる。これらは大域的最適化と呼ばれる。これらが終わると、変数にレジスタを割り当てる(register allocation)。RISCでは、このレジスタの割り当て方法が重要である。

問題8.1

以下のプログラムの基本ブロックを図示せよ。

    int 
    get_register() 
    {    /* 使われていないレジスタを調べる */
	int i;
	for(i=0;i<MAX_REGISTER;i++) {
	    if (! regs[i]) {    /* 使われていないなら */
		regs[i]=1;      /* そのレジスタを使うことを宣言し */
		return i;       /* その場所を表す番号を返す */
	    }
	}
	return -1;    /* 空いている場所がないなら、それを表す -1 を返す */
    }