2. LIRの内部構造
新LIRの内部構造は単純、直截的をモットーにしている。継承はほとんど使っていない。内部へのアクセスは、なるべくfinalなフィールドを多くし、直接アクセスできるようにしている。
LIRの内部表現は、クラスModuleのインスタンスの中にすべてまとめられている。
この中に、グローバルシンボル表やL関数がふくまれる。
次の図は、その内部表現をhas-a関係に注目して表わしたものである。
図はclickableであり、クラス名をクリックするとそのクラスの解説に飛ぶ。
FlowGraphの内部をclickすると、より詳しい構造図が表示される。
Moduleは、ひとつのコンパイル単位に対応するデータ構造である。
内部にはグローバルシンボル表と、クラスFunctionのインスタンスの集合をもつ。
L関数に対応するFunctionのインスタンスは、双方向リストクラスBiListの要素となっている。
インスタンス作成
Moduleのインスタンスは以下の手順で作成される。
Object sexp = ImList.readSexp(inputStream);
Module mod = new Module(sexp, debugOutputStream);
この例は、入力ストリームinputStreamからASCII形式のLIRファイルを読みこんで内部S式表現に変換したのち、Moduleのコンストラクタにそれを渡してModuleのインスタンスを構築している。
インスタンスメソッド
以下、mod は Module 型変数とする。
- String name = mod.name;
- Lモジュールの名前( (MODULE "foo" ...) の "foo" の部分)。
- SymTab t = mod.globalSymTab;
- グローバルシンボル表。
- BiList list = mod.functionList;
- L関数を表すクラスFunctionのインスタンスのリスト。
各L関数を順に処理するコードは次のように書ける。
for (BiLink p = mod.functionList.first(); !p.atEnd(); p = p.next()) {
Function func = p.elem();
// L関数funcに対する処理
}
クラスFunctionはL関数に対応するデータ構造である。
インスタンスの作成
Functionのインスタンスは、Moduleの内部で作成され、それ以外の部分で作成することはないと思われるが一応ここで作り方を示しておく。
Module mod;
ImList list;
PrintWriter debugOutput;
Function func = new Function(module, list, debugOutput)
インスタンスメソッド
以下、func は Function 型の変数とする。
- Symbol sym = func.symbol;
- このL関数のシンボルのエントリ。
そのインスタンスはModule内のglobalSymTab内に含まれる。
- SymTab symtbl = func.localSymTab;
- このL関数内のローカルシンボル表。
- Map labtbl = func.labelTable;
- このL関数内のラベル表。
- LirFactory factory = func.newLir;
- このL関数内のLirNodeを作るためのLirFactory。
LirNodeは、一意のid番号を振るため直接newで作成することは許されず、必ずこのインスタンスを経由して作成しなければならない。
- FlowGraph cfg = func.flowGraph;
- このL関数のControl Flow Graph。
- func.printIt(debugStream);
- PrintWriter のインスタンス debugStream 上に内部情報をダンプする。
FlowGraphは、L関数内の制御構造をあらわすグラフ(Control Flow Graph)である。
グラフは、基本ブロックという分岐を含まないプログラムの断片の集合と、それぞれを結ぶ辺(edge)から構成される。
基本ブロックはクラスBasicBlkで表現されるが、辺に対応するクラスはない。
インスタンスの作成
FlowGraphのインスタンス作成はFunctionの作成時におこなわれ、それ以外の部分で作られることはない。
次の手順で作成される。
Function func;
BiList instrList;
FlowGraph cfg = new FlowGraph(func, instrList);
instrList はLirNodeのリストである。
これは分岐命令やラベル定義を含む元のL関数で、基本ブロックの単位に分割される。元のリストは破壊されてなくなる。
インスタンスメソッド
以下、cfg はFlowGraph型の変数とする。
- Function func = cfg.function;
- このCFGが所属するFunctionのインスタンスを返す。
- BiList list = cfg.basicBlkList;
- 基本ブロックのリストを返す。
各基本ブロックを順に処理するコードは次のように書ける。
for (BiLink p = cfg.basicBlkList.first(); !p.atEnd(); p = p.next()) {
BasicBlk blk = p.elem();
// 基本ブロックblkに対する処理
}
- BasicBlk x;
- BasicBlk blk = cfg.insertNewBlkBefore(x);
- 新しい空の基本ブロックをxのひとつ前に挿入する。
- int n = cfg.idBound();
- 基本ブロックに付けられたid番号の最大値+1を返す。
基本ブロックの個数+1と一致しているとは限らない。
- cfg.dfstOrder();
- 入口ブロックを根とする 深さ優先木 を作成する。
- int n = cfg.maxDfn();
- Depth First Numberの最大値。
- BasicBlk[] v = cfg.blkVectorByRPost();
- 基本ブロックをDepth First Number (reverse postorder)の順に並べた配列を返す。
- BasicBlk[] v = cfg.blkVectorByPre();
- 基本ブロックをDepth First Number (preorder)の順に並べた配列を返す。
- BasicBlk b = cfg.entryBlk();
- 入口ブロックを返す。
- Iterator it = cfg.basicBlkIterator();
- 基本ブロックを順に訪問するためのIteratorを返す。
- cfg.printIt(stream);
- PrintWriterのインスタンスstream上にCFGの内容をダンプする。
基本ブロックに対応するクラス。
インスタンスの作成
BasicBlkは直接newで作成することはできない。通常の基本ブロックは
FlowGraph内のnewBasicBlkメソッドで作られるが、このメソッドもパケジ外からは呼ぶことはできない。
外部から新しい基本ブロックを作るにはFlowGraphのinsertNewBlkBeforeメソッドを呼ぶしかない。
インスタンスメソッド
以下の説明中、blkはBasicBlk型の変数とする。
- FlowGraph cfg = blk.flowGraph;
- この基本ブロックが所属するCFGを返す。
- int n = blk.id;
- 基本ブロックのid番号を返す。この番号はひとつのL関数内では一意で、変更されることはない。番号は1から順につけられ、削除されたブロックの番号は欠番となる。
- BiList l = blk.instrList();
- 基本ブロック内の命令のリストを返す。
- blk.setInstrList(l);
- 基本ブロックに命令のリストをセットする。
- Label label = blk.label();
- 基本ブロックに張られたラベルを返す。
このラベルは、基本ブロックの先頭に登場するDEFLABELに付いていたものである。
- BiList l = blk.succList();
- 基本ブロックのsuccessorのリストを返す。successorとは、この基本ブロックの次に実行される基本ブロックのことである。
- BiList l = blk.predList();
- 基本ブロックのpredecessorのリストを返す。predecessorとは、このブロックの前に実行される基本ブロックのことである。
- int n = blk.dfn();
- この基本ブロックの、深さ優先木の中をpostorderで訪問したときの逆順の順番を返す。番号は1から始まる。
- int n = blk.dfnPre();
- この基本ブロックの、深さ優先木の中をpreorderで訪問したときの順番を返す。番号は1から始まる。
- BasicBlk x;
- boolean b = blk.isAncestorOf(x);
- 深さ優先木の中でblkがxの先祖かどうかを判定する。先祖であればtrueを返す。
- BasicBlk x;
- boolean b = blk.isDescendantOf(x);
- 深さ優先木の中でblkがxの子孫かどうかを判定する。子孫であればtrueを返す。
- blk.clearEdges();
- 基本ブロックblkから出ている辺(edge)をすべて削除する。
succListは空となり、辺の行先基本ブロックのpredListからblkが削除される。
- blk.maintEdges();
- 基本ブロックblk内の分岐命令を調べて、正しくpredecessorとsuccessorを設定する。
- BasicBlk x, y;
- blk.replaceSucc(x, y);
- 基本ブロックblkのsuccessor中のxをyに置きかえる。xがsuccListの中になければ実行時エラーが発生する。
- PrintWriter stream;
- blk.printIt(stream);
- blkの内部をstreamにダンプする。命令列やsuccessor, predecessorが印字される。
LirNode はL式のひとつのノードに対応するクラスである。
LirNodeは抽象クラスであり、実際のインスタンスはそれを継承した次のいずれかのクラスに属する。
- LirIconst
- INTCONST式に対応したクラス。int型定数を内部に持つ。
- LirFconst
- FLOATCONST式に対応したクラス。double型定数を内部に持つ。
- LirSymRef
- STATIC式、FRAME式、REG式に対応したクラス。Symbolのインスタンスを内部に持つ。
- LirLabelRef
- LABEL式およびDEFLABEL式に対応したクラス。Labelのインスタンスを内部に持つ。
- LirUnaOp
- 単項演算子に対応したクラス。一つのLirNodeのインスタンスをオペランドに持つ。
- LirBinOp
- 二項演算子に対応したクラス。二つのLirNodeのインスタンスをオペランドに持つ。
- LirNaryOp
- オペランドの数が1,2以外の式に対応したクラス。LirNodeのインスタンスの配列をオペランドに持つ。
インスタンスの作成
LirNodeは直接newできない。クラスLirFactoryのインスタンスに以下のメソッドを送ることによって作られる。LirFactoryのインスタンスは通常、クラスFunctionの各インスタンスに一つずつ存在している。
以下、newLirはLirFactory型の変数とする。
- int type; int value;
- newLir.iconst(type, value);
- valueを値にもつtype型のLirIconstのインスタンスを生成して返す。
typeはLタイプをエンコードした整数で、クラスLtypeでencode/decodeされる。
- int type; double value;
- newLir.iconst(type, value);
- valueを値にもつtype型のLirFconstのインスタンスを生成して返す。
- int opCode; int type; Symbol symbol;
- newLir.symRef(opCode, type, symbol);
- LirSymRefのインスタンスを生成して返す。
opCodeはクラスOp中の定数として定義され、例えばLABEL命令のコードは
Op.LABELとして参照できる。
- int opCode; int type; Label label;
- newLir.labelRef(opCode, type, label);
- LirLabelRefのインスタンスを生成して返す。
- int opCode; int type; LirNode operand;
- newLir.operator(opCode, type, operand);
- LirUnaOpのインスタンスを生成して返す。
- int opCode; int type; LirNode operand0, operand1;
- newLir.operator(opCode, type, operand0, operand1);
- LirBinOpのインスタンスを生成して返す。
- int opCode; int type; LirNode[] operands;
- newLir.operator(opCode, type, operands);
- LirNaryOpのインスタンスを生成して返す。
インスタンスメソッド
以下の説明で、instはLirNode型(もしくはそのサブクラス)の変数とする。
- int id = inst.id;
- このL式のノードに割当てられたid番号を返す。この番号はひとつのL関数の中で一意であり、変更されることはない。番号は1から始まり、このノードが削除されると欠番となる。
- int opCode = inst.opCode;
- L式の命令コードを返す。命令コードの値はクラスOpで定義されている。
- int type = inst.type;
- L式のLタイプを返す。Lタイプを整数にエンコードする方法はクラスLtypeで記述されている。
- int n = inst.nSrcs();
- L式ノードinstの持つオペランド(部分L式)の数を返す。
FLOATCONST、INTCONST、STATIC、FRAME、REG、LABEL、DEFLABELでは0が返される。
- int n;
- LirNode src = inst.src(n);
- L式ノードinstのn番目のオペランドを返す。最初のオペランドは0番目である。
- int n; LirNode src;
- inst.setSrc(n, src);
- L式ノードinstのn番目のオペランドをsrcで置きかえる。
L式ノードのうち、生成されたのちに書き換えられるフィールドはこれだけである。
他のフィールド(OpCodeやtypeなど)は書き換え不能であり、これらを変更したい場合は別のインスタンスを作って、参照ごと書き換えるしかない。
- Label[] labels = inst.getTargets();
- L式ノードinstがJUMP/JUMPC/JUMPN式のいずれかであったとき、そこで参照されているラベルの配列を返す。ラベルの引用のない命令ならば null が返る。
- Label x, y; LirFactory f;
- inst.replaceLabel(x, y, f);
- L式ノードinst中で参照しているラベルxをyにおきかえる。新しいLirNodeインスタンスの生成をともなうので、LirFactoryのインスタンスfを引数として渡す必要がある。
- LirVisitor v;
- inst.accept(v);
- LirVisitorのインスタンスvを受けつけ、型によってv中の適切なメソッドを選んで実行させる。
- int value = ((LirIconst)inst).value;
- instがLirIconstのインスタンスのとき、その値を取りだす。
- double value = ((LirFconst)inst).value;
- instがLirFconstのインスタンスのとき、その値を取りだす。
- Symbol symbol = ((LirSymRef)inst).symbol;
- instがLirSymRefのインスタンスのとき、そこで参照しているシンボルを取りだす。
- Label label = ((LirLabelRef)inst).label;
- instがLirLabelRefのインスタンスのとき、そのラベルを取りだす。
BiListは双方向リストのクラスであり、BiLinkはBiListの内部の鎖となる節点のクラスである。
BiLinkのインスタンスそのものがリスト中の位置を表わす情報となっている。また、BiList自体が実はBiLinkのサブクラスである。
インスタンスの作成
BiList は、new BiList() で空リストが作成される。
BiLinkは、直接newでは作れない。BiListのメソッドによって間接的に作られる。
インスタンスメソッド
以下の説明では list はBiList型の変数、linkはBiLink型の変数とする。
- boolean b = list.isEmpty();
- リストlistが空ならtrueを返す。
- BiLink link = list.first();
- 最初のリンクを返す。
- BiLink link = list.last();
- リスト中の最後のリンクを返す。
- Object obj;
- BiLink x = list.add(obj);
- listの最後にobjという要素を追加する。その要素を含むリンクを返す。
- BiLink p = list.append(link);
- listの最後にリンクlinkを追加する。
- Object obj;
- BiLink p = list.addFirst(obj);
- listの先頭にobjという要素を追加する。
- BiLink p = list.prepend(link);
- listの先頭にリンクlinkを挿入する。
- Object obj;
- BiLink p = list.remove(obj);
- listの中にobjという要素があれば、それを含むリンクをはずす。
- Object obj;
- boolean b = list.contains(obj);
- listの中にobjという要素があればtrueを返す。
- Object obj;
- BiLink p = list.locate(obj);
- listの中にobjという要素があるか調べ、あればそれを含むリンクを、なければnullを返す。
- Object obj;
- int n = list.whereis(obj);
- listの中にobjという要素があるか調べ、あればその先頭からの位置を整数で返す。先頭は0である。なければ-1を返す。
- Object obj;
- list.addNew(obj);
- listの中にobjという要素がないときに限り、最後にobjを追加する。
- list.clear();
- listを空にする。
- BiList addend;
- BiList x = list.concatenate(addend);
- listの最後に別のリストaddendの中身を追加する。addendは空のリストになる。
listそのものを返す。
- BiLink mid;
- BiList x = list.split(mid);
- listをmidより前と後に切断する。後半の先頭要素はmidである。
前半のリストはlistに残り、後半のリストを返す。
- BiList x = list.copy();
- listのコピーを作って返す。ただし要素オブジェクトはコピーされず、共有される。
- int n = list.length();
- listにいくつの要素があるかを返す。
- Iterator it = list.iterator();
- listをアクセスするためのイテレータを返す。
BiList は BiLinkオブジェクトをたぐって順番にアクセスするのが普通だが、
イテレータでアクセスすることも可能である。
- boolean b = link.atEnd();
- linkが最後のリンクの次、もしくは最初のリンクの前であればtrueを返す。
- Objecgt obj = link.elem();
- linkの中身を返す。
- BiLink link = link.next();
- linkの次のリンクを返す。
- BiLink link = link.prev();
- linkの次のリンクを返す。
- Object obj;
- link.setElem(obj);
- このリンクの要素をobjで置きかえる。
- BiLink addend;
- BiLink x = link.insertAfter(addend);
- linkの次に別のリンクaddendを挿入する。
- Object obj;
- BiLink x = link.addAfter(obj);
- linkの次に要素objをもつ新しいリンクを挿入する。
- BiLink addend;
- BiLink x = link.insertBefore(addend);
- linkのひとつ前に別のリンクaddendを挿入する。
- Object obj;
- BiLink x = link.addBefore(obj);
- linkのひとつ前に要素objをもつ新しいリンクを挿入する。
- link.unlink();
- linkをリストから切りはなす。
SymbolはSTATIC式、FRAME式、REG式で参照される名前とその属性の組を表す抽象クラスである。実際のインスタンスはこれを継承したSymStatic(STATICシンボル)もしくはSymAuto(FRAMEまたはREGシンボル)クラスに属する。
インスタンスの生成
Symbolは直接newできない。クラスSymTabのインスタンスメソッドにて生成される。
インスタンスメソッド
以下、symはSymbol型の変数とする。
- String name = sym.name;
- シンボルsymの名前を返す。
- int id = sym.id;
- 表の中での一意の番号を返す。
- int stroage = sym.storage;
- シンボルの記憶クラスを返す。記憶クラスはSTATIC、FRAME、REGのいずれかで、
その値はクラスStorage中で定義されている。
- int type = sym.type;
- シンボルのLタイプを返す。LタイプのエンコーディングはクラスTypeで行なわれる。
- int boundary = sym.boundary;
- シンボルの要求する境界。4バイト境界なら4、8バイト境界なら8。
- int flag;
- boolean b = sym.testFlag(flag);
- シンボルsymのフラグflagがセットされているかどうか調べる。セットされていればtrueが返る。フラグは32bitの整数にパックされており、テストしたい位置のビットを立てた整数をわたして検査を行う。
- int flag; boolean set;
- sym.setFlag(flag, set);
- シンボルsymのフラグflagをセットしたりリセットしたりする。boolean変数setがtrueならばセット、falseならばリセットする。
- String s = sym.flagsToString();
- セットされているフラグの名前を「&フラグ名」の形式で文字列化する。
- Symbol shadow = sym.shadow();
- このシンボルに関連付けられている他のシンボルへの参照を返す。
主に、FRAME/STATICシンボルと、それをレジスタに割当てたときのREGシンボルの関連付けに用いる。
- Symbol ref;
- sym.setShadow(ref)
- このシンボルのshadowリファレンスをrefに書き換える。
シンボル表のクラス。インスタンスの作成は new SymTab();でOK。
インスタンスメソッド
- Symbol symbol = table.addSymbol(name, storage, type, boundary, segment, linkage);
- SymStaticクラスを生成し、SymTabのインスタンスtableに追加する。
STATICシンボルの生成に用いる。
- Symbol symbol = table.addSymbol(name, storage, type, boundary, offset);
- SymAutoクラスのインスタンスを生成し、SymTabのインスタンスtableに追加する。
FRAMEもしくはREGシンボルの生成に用いる。
- Symbol sym = table.get(name);
- 表からnameというキーを持つシンボルを探して返す。nameはinternされていなくてはならない。
- BiList list = table.symbols();
- tableに登録されているシンボルのリストを返す。シンボルは登録された順に並んでいる。
- Iterator it = table.iterator();
- table中に登録されているシンボルを順に処理するためのイテレータを返す。
- int n = table.idBound();
- 登録済シンボルの最大のid番号+1を返す。
- PrintWriter stream;
- table.printIt(stream);
- tableの中身をstream上にダンプする。
ラベルは、LABEL式やDEFLABEL式に現れ、L式列中の位置を示し、FlowGraphでは個々の基本ブロックを識別するのに使われる。
その実体は名前と基本ブロックの対であり、L関数の中にあるラベル表に登録される。
ラベル表専用のクラスは存在せず、汎用クラスのMapで実現している。
インスタンス作成
ラベルはnew Label("foo")のようにすれば作れるが、実際には新しい基本ブロックを作ると自動的にラベルが貼られるので、自前で作成する必要はほとんどないと思われる。
インスタンスメソッド
以下、labelはLabel型の変数とする。
- String s = label.name;
- ラベルlabelの名前を返す。
- BasicBlk blk = label.basicBlk();
- labelというラベルを持つ基本ブロックを返す。
- BasicBlk blk;
- label.setBasicBlk(blk);
- labelに対応する基本ブロックをblkにセットする。