COINS FORTRAN Frontend

Fortranコンパイラの設計


(1)全体設計

 FortranコンパイラのためにHIRの仕様を変更することは出来るだけしないこと にした。その結果いくつかのプログラム変換が必要になる。そのためにFortran プログラムを抽象構文木のようなもので表現してから、HIRに変換することにし た。

 Fortranの文法は、lexやyaccのような生成系で簡単に処理できるようにはなっ ていない。そこで、lexerあるいはscannerと呼ばれる字句解析器は手書きで書き、 それで区別できることを出来るだけparserに伝えることによって、parserがyacc で生成できるようにした。これはOMNIの方法に習ったものであるが、さらに、 scannerからの情報を増やすことと構文規則の書き方を工夫することによって、 構文規則が出来るだけ構造的に書けるようにした。たとえば、プログラムユニッ トはend文で終る、などということを構文規則で表現した。

 parserはBerkeley yaccのJava版の一つであるjayを使うことにした。手書きの scannerを作るのには時間がかかるので、とりあえず後回しにして、ソースプロ グラムを手書きで書き直したものを受け付けるscannerをlexのJava版の一つであ るJFlexを使って作ることにした。(その後、ある程度のコンパイルが出来るよう になってから、ソースプログラムを読んで上記のscannerにトークンを渡すもう 一つのスキャナF77Scannerを作って、ソースプログラムを直接受け付けるように した。)

 最初にparserを作るための構文規則をyaccで書き、yaccの指摘するconflictが 無くなるように何回か書き直して、f77.yを作った。これでもまだshift/reduce conflictが5つ指摘されるが、それはOMNIのyacc記述で指摘されるものと同じで あり、OMNIではそれで問題がないようであるので、このf77.yをもとにすること にした。(その後、それでは入出力文でCOMPLEX定数が書けないという問題が生 じたので、その部分の文法を書き直した。この変更により、shift/reduce conflict は4つになった)

 次に、f77.yに抽象構文木を作るための意味規則を付加したファイルf77.jayを 作成した。抽象構文木はソースプログラムの形をそのまま表現するようにしたの で、意味規則は簡単な形だけである。ただし、この段階ではどのようなクラスを 使って抽象構文木を表現するかを決めずに、適当な名前のメソッドを呼ぶだけの 形にしておいた。(実は、このメソッドの実現法はいろいろ考えられるから、抽 象構文木を作らずに直接HIRを作るようにすることも可能である。実際にそのよ うなコーディングも少ししてみたが、プログラム変換がからむと難しくなるので、 すべて抽象構文木とすることにした。)

 なお、これらのメソッド全部を一つのクラスの中に書くと、クラスが大きくな って読みにくくなるかも知れないと思って、宣言文関係のメソッドと実行文関係 のメソッドを別のクラスに書くことにした(F77SymクラスとF77Hirクラス)。

 抽象構文木のクラスとしては、各実行文の種類ごとのクラス(すべてFStmtク ラスのサブクラス)と、式のクラスとしてUnaryExp、BinaryExp、 SubscrOrFunCall(配列要素または関数呼出し)、Token(scannerから渡されたも のが式にもなる)、およびそれらの部品として現れるリストFirList(LinkedList のサブクラス)、Pair、Triple、Quadを作った。なお、これらすべてのクラスは Node型(Interface Nodeをimplementsしている)である。宣言の情報は、その種 類ごとのリストとして蓄えられる。

 抽象構文木からHIRへの変換のメインはFirToHirクラスにある。各文ごと、あ るいは各式ごとの変換は、それぞれ各文のクラスあるいは各式のクラスに記述す る。それらの変換で使用される共通のメソッドもFirToHirクラスにおく。

 以上の方針のもとで、まず、PROGRAM文と、簡単な宣言(配列やCOMPLEXや CHARACTERを含まない)と、代入文とEND文だけからなるプログラムが通るだけの コーディングをして、簡単な例題でコンパイルが成功してアセンブリーコードが 生成されることを確かめてから、少しずつ機能を追加していった。

 全部の設計をしてからコーディングにかかるべきかも知れないが、設計するた めにはある程度コーディングレベルのことまで考える必要があり、それならばコ ーディングをしてみて、だめだったら設計し直せばいいとした。今までのところ 大きな設計のし直しはない。

 FirToHir というクラスの責任が非常に大きくなってしまった(1クラスで 2000行ほど)ので、いくつかのクラスに分割した。

(2)各機能の設計

 現在までにほとんどの機能を実現したが、入出力の実装に不完全なところがあ る。以下、実現したものについてその実現法を少し説明する。文関数の呼出しは インラインに展開する。COMPLEXの式は実数部と虚数部の演算に展開する。変数 は、単純変数のみで配列はまだである。COMPLEX型の変数はstruct型としてシン ボルテーブルに登録する。演算は四則演算の他にべき乗演算が使える。整数定数 の0〜4によるべき乗はインラインの乗算などに展開し、それ以外はライブラリ呼 出しとする(Powerクラスで実現)。

 COMPLEX型を実現するために、ComplexConst、ComplexType、ComplexExpのクラ スを設けた。ComplexConstはCOMPLEX定数の抽象構文木を作るものである。 ComplexTypeはHIRのType型(TypeImplのサブクラス)であり、式の型を区別する ためと、COMPLEX型の変数を表現するstruct型の情報を得るために使われる。 ComplexExpはHIRのExp型(ExpImplのサブクラス)であり、実数部のExpと虚数部 のExpを保持する。COMPLEX型の式のHIR木が作られて行く途中ではComplexExp型 として作られ、それがCOMPLEX型の変数に代入される代入文の場合は、実数部の 代入文と、虚数部の代入文の二つがHIRの木として生成される。REAL型の変数に 代入する場合は虚数部のExpは捨てられる。

 文関数定義文の処理をするために、StmtFuncTypeとStmtFuncParamTypeのクラ スを設けた。

 文関数定義文であるかどうかは構文だけからは分からない。抽象構文木では、 代入文の形をしているものはAssignOrFuncクラスのオブジェクトとして表現され ている。まず、それが文関数であると判断できるのは、左辺がSubscrOrFunCall のオブジェクトであり、その名前(そのオブジェクトの左の子のTokenの名前)が 初出の名前か、すでに登録されている場合は配列名でないかの場合である。その 場合は、この名前のシンボルをSubpとして登録し、TypeをStmtFuncTypeとしてお く。(シンボルテーブルにはこのままの情報が残ってしまうが、作られたHIRの 木にこの情報は現れず、HIR以降のフェーズでこの情報を見ることはないので、 問題は起きていない。しかし、COMPLEXの場合にシンボルテーブルにComplexType として変数を登録しておいたら、LIRのフェーズでその変数に(それが使われて いなくても)メモリ割付をしようとして例外を発生したので、今はそうはせず、 struct型として登録している)。なお、この名前のSubpシンボルからもとの AssignOrFuncオブジェクトを取り出せるように、StmtFuncTypeオブジェクトに、 もとのAssignOrFuncオブジェクトと、関数としての戻り値の型を入れておく。

 式オブジェクトに対してHIRのExpを作っていくのは、そのオブジェクトの makeExpメソッドを呼び出せばよい。式の中に文関数の呼出しがあった場合は、 SubscrOrFunCallオブジェクトのmakeExpメソッドが呼ばれたとき、そこから呼ば れるmakeFunCallでそのことが分かる。その時、まず、StmtFuncTypeオブジェク トからもとのAssignOrFuncオブジェクトを取り出し、それから仮引数のリストと その型のリストを作る。仮引数の型は別の宣言文で宣言されているかも知れない ので、シンボルテーブルでそれを調べる必要がある。

 これ以後、もとのAssignOrFuncオブジェクトの右辺の式からExpを作っていく のであるが、その右辺の式の中に仮引数が現れたら、それはこの SubscrOrFunCallオブジェクトの実引数で置き換える必要がある。したがって仮 引数はシンボルテーブルにサブプログラムの仮引数などとは違う文関数の仮引数 として登録しておく必要がある。そのためのクラスがStmtFuncParamTypeである。 また、文関数は多重に呼び出されるかも知れないから、それらを区別できるよう に、呼ばれるたびにシンボルテーブルをpushしてそこに仮引数を StmtFuncParamTypeのものとして登録する。StmtFuncParamTypeオブジェクトには、 この仮引数の型と、このSubscrOrFunCallオブジェクトと、何番目の仮引数であ るかの情報を入れておく。呼出しの処理が終ったらシンボルテーブルをpopする。

 右辺の式の中にその仮引数が現れたときの処理は、TokenクラスのmakeExpメソ ッドに書けばよい。そこで、文関数の仮引数であることが分かったら、もとの SubscrOrFunCallオブジェクトから対応する実引数を取り出して、それをこの Tokenから得られるExpとして返せばよい。

 実行文の多くは、それぞれ独立にコーディングできるが、独立に出来ないもの にラベルでループの終わりを指定するDO文(LabeledDoStmtクラスのオブジェク ト)がある。DOループの終わりはラベル(文番号)によって判定しなければならな い。また、一つのラベルで複数のループの終わりを示すものもある。それらの情 報はスタックで処理をすることとし、スタックに積む情報はDoInfクラスのオブ ジェクトとした。同じ文番号で終るループは、DoInfの中のサブ番号でいくつ目 のそのようなループであるかを表す。同じ文番号のものがあるかどうかは、スタ ックのトップのDoInfの文番号を調べるだけで分かる。

 HIR.javaには、Fortran用にIndexedLoopStmtがあるように書いてあるが、まだ 実装されていなかったので、ForStmtの木を作ることにして、そのメソッドは DoInfクラスに書いてある。そのもとになるStmtやExpはLabeledDoStmtオブジェ クトで作られる。なお、でき上がったコードを見やすくするために、ForStmtの loopBackLabel、loopStepLabel、loopEndLabelにはもとの文番号とサブ番号を使 うことにした。

 入出力については、f2cと同じようにしている。実行時ライブラリとしては libf2cを使用している。

組み込み関数について

abs(exp)は、整数の場合は

   _i_temp = exp;
   if (_i_temp <0) _i_temp = - _i_temp;
   _i_temp

とする。実数の場合は_r_tempとする。複素数の場合はsqrtを使う

 たとえば、代入文の右辺にこれが現れると、上記の文をその代入文の前に生成 し、右辺のabs(exp)は_i_tempで置き換えることになる。その代入文にラベルが ついていたら、そのラベルはこのように生成された文の先頭についていることに なる。各文のクラスのスーパクラスであるFStmtクラスの中のgeneratedStmtsは このような生成された文のリストを表現するものである。たとえば、COMPLEX型 の代入文からは、実数部の代入文と虚数部の代入文が作られるが、その一方が generatedStmtsに入る。

 その他の組み込み関数では、HIRで表現できるものはそれで、sin、cos 関数な どは libm の関数を利用する。COMPLEX のこれらの計算は libf2c の対応する関 数を利用する。

ASSIGN文とassigned GO TO 文について

   ASSIGN s TO i

 は

   i = s (通常の整数の代入文とし)

としており、

   GO TO i [ (s [,s]...)]

 は

   switch(i){
   case s: GO TO L_s   (最初のsは整数定数。後ろのsは文番号)
   . . .
   }

 としている。

 HIRでは、switch文はswitch(i)のiの値とそれに対応する飛び先の組(jump list)を作り、それによって各caseへのjump命令を作るようにしているが、assigned GOTOの場合は、各caseがjump命令だけからなるのであるから、jump listの中にそのjump先を入れておけば、case文を経由せずに直接飛べるはずである。そう考えてcase文からなるブロックを空のブロックにしてみたところ、LIRで例外が発生してしまった。今は、2段のjumpをするHIRになっている。

 assigned GOTOの飛び先のリスト ( [,s]...)は省略可能であるから、それが省略された場合が問題である。プログラム中のASSIGNをすべて調べて、assignされている値のリストを作る必要がある。そのために、抽象構文木を作っていくときにASSIGNのリストを別途作っている。それを見て、変数iにASSIGNされているすべてのラベルをswitchのcaseに入れることにした。

expressionの評価について

 カッコで囲まれたexpressionは一つのentityとして扱わねばならないので、HIRにはENCLOSEというoperationが用意されている。最初はそれを使ったHIRに変換していたが、LIRで例外が発生するので、現在は、抽象構文木のレベルではカッコの情報を保持しているが、HIRに変換するときに捨てている。

ENTRY文について

 次の例題を使って説明する。

  FUNCTION f(r) 
  INTEGER f, r, g, s
  f = r
  ENTRY g(s)
  g = f + s
  END 

(1)プログラムの中にENTRY文がある場合は、構文解析時にそれらのリストを作っておく。

(2)関数の型(戻り値の型)を決める。defineFunctionType()で関数fの型INTEGERを求めている。そのために型宣言の処理をしている(processTypeDecl(ident))。

(3)checkEntryStmt()でENTRYがあるかを調べ、あったらFUNCTION文(またはSUBROUTINE文)からそれと同じ名前のENTRY文を作り、それをENTRYリストの先頭に加え、プログラム本体の先頭にも加える。今の例ではENTRYがあるから、

   FUNCTION f

 から、

   ENTRY f

 を作り、ENTRY fをプログラム本体の先頭とENTRYのリストに追加する(addEntryStmt())。

(4)すべてのENTRY文の仮引数のorをとり、その先頭にint型の仮引数をつけたリストを作る。それが新たなFUNCTION文(またはSUBROUTINE文)の仮引数になる。今の例では

   (i_, r, s)

 が作られる。

(5)もとのFUNCTION文(またはSUBROUTINE文)を変更して新しい文を作る(change())。また、プログラム本体の先頭にComputedGoto文を付け加える。今の例では

   FUNCTION f_(i_, r, s)
   GO TO (f, g) i_

 が作られる。後者はL_f:, L_g:に分岐するswitch文になる。

(6)各ENTRY文からサブプログラムを作りそれをHIRに変換する(makeSubp())。今の例では、

   FUNCTION f(r)
   _f = f_(1, r, dummy_)
   END

   FUNCTION g(s)
   _g = f_(2, dummy_, s)
   END

 が作られ、それぞれHIRに変換される。END文はそれぞれreturn _f;と return _g;に変換される。

(7)プログラム本体がHIRに変換される。その際、ENTRY文からはラベルだけが作られる。今の例ではENTRY fとgからL_f:とL_g:が作られる。また、実行文中のFUNCTION名やENTRY名は戻り値を入れる変数に置き換えられる。今の例ではfもgも_f_に置き換えられる。その結果、次のようなプログラムになる。

   int f_(int *i, int *r, int *s){
    int _f_;
    switch(*i){
    case 1: goto L_f;
    case 2: goto L_g;
    }
   L_f: _f_ = *r;
   L_g: _f_ = _f_ + *s;
    return _f_;
   }
COINS Project