そのようにして定めた中間表現が本コンパイラ・インフラストラクチャの高水準中間表現HIR (High-level Intermediate Representation)である。
HIRでは、処理操作はオペレータとそのオペランドとして表現される。 オペランドとしては処理操作の結果も許される、すなわち、ある処理操作の結果を 他の処理操作でさらに処理することもできるので、 オペレータとそのオペランドを線で結んでゆくと、処理操作は木構造として 表現できる。処理対象はスカラー量と配列、構造体、共用体として表現できる。
HIRは次の特徴を持つ。
HIRの論理構造を次の図3-1に示す。
HIR // High-level Intermediate Representation.
|- Program // Program definition node.
|- SubpDefinition // Subprogram definition node.
|- HirSeq // Sequence of definite number of HIR objects.
|- HirList // List whose elements are HIR objects.
|- Stmt // Statement
| |- LabeledStmt // Labeled statement.
| |- AssignStmt // Assignment statement.
| |- IfStmt // If-statement.
| |- JumpStmt // Jump (goto) statement (Jump unconditionally).
| |- LoopStmt // Loop statement.
| |- ReturnStmt // Return statement.
| |- SwitchStmt // Switch (case) statement.
| |- BlockStmt // Block representing a sequence of statements.
| |- ExpStmt // Expression treated as a statement.
| |- InfStmt // An information node (pragma, comment line, etc.)
| |- SetDataStmt // Statement to specify initial data.
|- LabelDef // Label definition node.
|- Exp // Expression
|- ConstNode // Constant node
|- SymNode // Symbol node
| |- VarNode // Variable name node.
| | |- ElemNode // struct/union element name node
| |- SubpNode // Subprogram name node.
| |- LabelNode // Label reference node.
| |- TypeNode // Type name node.
|
|- SubscriptedExp // Subscripted variable.
|- PointedExp // Pointed object.
|- QualifiedExp // Qualified variable.
|- FunctionExp // Function call expression.
|- PhiExp // Phi function used in SSA
|- ExpListExp // Expression representing a list of expressions.
|- NullNode // Null (no-operation) node
プログラムには、変数や副プログラムなどの記号が現れる。これらは文字列の ままでは扱いにくいので、記号表に登録し、 HIRでは記号表の記載項として扱う。 定数も定数用の記号表に登録し、HIRではその記載項として扱う。
記号に関する種々の属性は記号表の記載項に付与する形で記録する。 これらの属性には、宣言文やプログラム構造などによって決まるものや、 構文解析、意味解析のときに設定されるものが多い。 木構造として表したHIRは処理操作を中心として表現するものであり、 宣言文の抽象構文木は表現しない。記号に関する情報は記号表に記載する。
int fact( int p)
/* fact0.c: Factorial function */
{
if (p <= 1)
return 1;
else
return p * fact(p - 1);
}
(a) 入力プログラム
(prog 1
<null 0 void>
<nullNode 2>
(subpDef 3 void
<subp 4 <SUBP < int > false false int> fact>
<null 0 void>
(labeldSt 5 void
(list 6
<labelDef 7 _lab1>)
(block 8 void file fact0.c line 2
(if 9 void file fact0.c line 4
(cmpLe 10 bool _XId1
<var 11 int p _XId2>
<const 12 int 1>)
(labeldSt 13 int
(list 14
<labelDef 15 _lab3>)
(return 16 int file fact0.c line 5
<const 17 int 1>))
(labeldSt 18 int
(list 19
<labelDef 20 _lab4>)
(return 21 int file fact0.c line 7
(mult 22 int _XId3
<var 23 int p _XId2>
(call 24 int _XId4
(addr 25 <PTR <SUBP < int > false false int>> _XId5
<subp 26 <SUBP < int > false false int> fact>)
(list 27
(sub 28 int _XId6
<var 29 int p _XId2>
<const 30 int 1>))))))
(labeldSt 31 void
(list 32
<labelDef 33 _lab5>)
<null 0 void>))))))
(b) HIR
(a) HIRのメソッド
HIRの作成や変換を行うには、それ用に備えてあるメソッドを使う。
Javaのnewで直接にコンストラクタを呼んでHIRを作ることはしない。
(newを使って作る場合は、HIRのノード間の相互関係をよく心得ていなければ
誤りやすいからである。)主要なメソッドは、COINSのコンパイラの
src/coins/ir/hir
HIR.java : HIR全体にかかわるインタフェース
Stmt.java: 文のインタフェース
Exp.java : 式のインタフェース
src/coins/sym
Sym.java : 記号のインタフェース
SymTable.java: 記号表のインタフェース
等に仕様が説明されている。(HIR関連のメソッドの仕様は、すべて、
COINSコンパイラのインタフェースモジュールとして記述されている。)
IoRoot ioRoot // 入出力ファイルに関係する情報へのリンク SymRoot symRoot // 記号情報への元締め(全ての記号情報はここからたどれる) HirRoot hirRoot // HIR情報への元締め(全てのHIR情報はここからたどれる)等がある。
(prog 1 // <--- hirRoot.programRoot
<null 0 void>
<nullNode 0> // Global initiation code.
(subpDef 2 void // Subprogram definition.
<subp 3 <SUBP <> false int> main>
<null 0 void> // Subprogram initiation code.
(labeldSt 4 void
(list 5 <labelDef _lab1> // Entry point label (generated).
(block 7 void // Subprogram body.
(assign 11 int
<var 12 int i>
<const 13 int 0> … )
) // End of subprogram main.
(subpDef 102 void // Another subprogram.
<subp 103 <SUBP <> false int> main> … )
…
) // End of compile unit.
C言語の
int main()
{
...
}
から、それに対するHIRを作るには、次のようにする。
Sym sym = symRoot.sym; // symRoot.symを単にsymとして参照できるようにする。
HIR hir = hirRoot.hir; // hirRoot.hirを単にhirとして参照できるようにする。
//-- int main()
Subp lMain = sym.defineSubp("main".intern(), symRoot.typeInt);
// mainの記号を作ってSymTableRootに登録する。
SymTable lLocalSymTable2 = symRoot.symTableRoot.
pushSymTable(lMain); // main()用の記号表をlLocalSymTable2として作り
// それをsymRoot.symTableCurrentで参照可能にする。
// 仮引数がある場合にはその処理
...
lMain.closeSubpHeader(); // 仮引数処理の終わり
SubpDefinition lMainDef =
hir.subpDefinition(lMain, lLocalSymTable2);
// SubpDefinitionのノードを作る。
( (Program) hirRoot.programRoot).addSubpDefinition(lMainDef);
//-- {
BlockStmt lBlockStmt = hir.blockStmt(null);
実行文追加
//-- }
lMainDef.setHirBody(lBlockStmt); // 実行文のブロックをmainに接続
lLocalSymTable2.popSymTable(); // mainの記号表を閉じる。
(e) 変数宣言と定数定義
Var lVa = sym.defineVar(“a".intern(), symRoot.typeInt);
// Define an int variable named “a” where
// typeInt: int of basic type.
// Symbols are registered in symRoot.symTableCurrent.
Var lVi = sym.defineVar(“i".intern(), symRoot.typeInt);
配列宣言
int aa[100];
に対しては、次のような処理をする。
VectorType lVectorType1 = sym.vectorType(symRoot.typeInt, 100);
// Define a vector type having 100 int elements.
Var lVaa = sym.defineVar("aa", lVectorType1);
// Define a variable named “aa” as a vector with 100 int elements.
上記の宣言と前記のmain()のに対する処理によって、次のような記号表が作られる。
SymTable Root type int (flags 3 12) size 4 … subp main <SUBP <> true int> callList list 0 public type <VECT 10 0 int> size 40 elemCount 10 lowerBound 0 subp printf <SUBP <<PTR char> true int> (flags 6) extern type <PTR char> size 4 type <VECT 20 0 float> size 80 elemCount 20 lowerBound 0 … SymTable main parent SymTable Root subp main var i int in main private auto var aa <VECT 100 0 int> in main private auto var matrix <VECT 10 0 <VECT 20 0 float>> in main private auto … SymTable Constant intC 1 int stringC "%d %d \n" <VECT 8 0 char> (flags 6) length 8(f) 代入文
//-- a = 3;
(assign 8 int
<var 9 int a>
<const 10 int 3>))
//-- b = a * 5;
(assign 11 int
<var 12 int b>
(mult 13 int
<var 14 int a>
<const 15 int 5>))
このHIRを作るには、次のようにする。
//-- a = 3;
VarNode lVarNode1 = hir.varNode(lVa);
Const lC3 = sym.intConst(“3", symRoot.typeInt);
// Constants are registered in symRoot.symTableConst.
ConstNode lConstNode1 = hir.constNode(lC3);
AssignStmt lAssign1 = hir.assignStmt(lVarNode1, lConstNode1);
lBlockStmt.addLastStmt(lAssign1); // Add lAssign1 as a statement
// of lBlockStmt which is the body of int main() { }.
//-- b = a * 5;
Var lVb = sym.defineVar("b", symRoot.typeInt);
Const lC5 = sym.intConst(5, symRoot.typeInt);
Exp lMult1 = hir.exp(HIR.OP_MULT,
hir.varNode(lVa), hir.constNode(lC5));
AssignStmt lAssign2 = hir.assignStmt(hir.varNode(lVa), lMult1);
lBlockStmt.addLastStmt(lAssign2);
// VarNode of “a” should not be shared between statements
// so as not to violate the rule for tree structure.
(g) if文
//-- if (a < b) i = a; else i = b;
(if 11 void
(cmpLt 12 bool
<var 13 int a>
<var 14 int b>
(labeldSt 15 int
(list 16 <labelDef _lab3>)
(assign 18 int
<var 19 int i>
<var 20 int a>))
(labeldSt 21 int
(list 22 <labelDef _lab4>)
(assign 24 int
<var 25 int i>
<var 26 int b>)))
これを作るには次のようにする。
//-- if (a < b) i = a; else i = b; // lVb = sym.defineVar(“b", symRoot.typeInt); Exp lComp1 = hir.exp(HIR.OP_CMP_LT, hir.varNode(lVa), hir.varNode(lVb)); AssignStmt lAssign4 = hir.assignStmt(hir.varNode(lVi), hir.varNode(lVa)); AssignStmt lAssign5 = hir.assignStmt(hir.varNode(lVi), hir.varNode(lVb)); IfStmt lIf1 = hir.ifStmt(lComp1, lAssign4, lAssign5); lBlockStmt.addLastStmt(lIf1);(h) ループ文
//-- for (i = 0; i < 100; i = i + 1) {
// aa[i] = j; j = j - 1; }
(for 53 void
(assign 54 int // i = 0;
<var 55 int i>
<const 56 int 0>)
<null 0 void>
(labeldSt 57 bool
(list 58 <labelDef _lab6>)
(expStmt 60 bool // i < 100
(cmpLt 61 bool
<var 62 int i>
<const 63 int 100>)))
(labeldSt 64 void
(list 65 <labelDef _lab9>)
(block 67 void
(assign 68 int // aa[i] = j;
(subs 69 int
<var 70 <VECT 100 0 int> aa>
<var 71 int i>)
<var 71 int j>)
(assign 73 int // j = j - 1;
<var 74 int j>
(sub 75 int
<var 76 int j>
<const 77 int 1>))
(labeldSt 78 void
(list 79 <labelDef _lab7>)
<null 0 void>)))
(expStmt 81 int
<null 0 void>)
(assign 82 int // i = i + 1;
<var 83 int i>
(add 84 int
<var 85 int i>
<const 86 int 1>))
(labeldSt 87 void
(list 88 <labelDef _lab8>)
<null 0 void>))
これを作るには、次のようにする。
//-- for (i = 0; i < 100; i = i + 1) {
// aa[i] = j; j = j - 1; }
Exp lComp2 = hir.exp(HIR.OP_CMP_LT, hir.varNode(lVi),
hir.intConstNode(100)); // i < 100
Exp lAdd2 = hir.exp(HIR.OP_ADD, hir.varNode(lVi),
hir.intConstNode(1)); // i + 1
Stmt lLoopStepPart = hir.assignStmt(hir.varNode(lVi), lAdd2);
Label lLoopBackLabel1 = lLocalSymTable2.generateLabel();
Label lLoopStepLabel1 = lLocalSymTable2.generateLabel();
Label lLoopEndLabel1 = lLocalSymTable2.generateLabel();
// Above labels may be used in implementing “break” and “continue”
BlockStmt lBlockStmt2 = hir.blockStmt(null); // Loop body part.
LoopStmt lFor1 = hir.forStmt(lLoopInitStmt, lLoopBackLabel1,
lComp2, lBlockStmt2, lLoopStepLabel1, lLoopStepPart,
lLoopEndLabel1);
lBlockStmt.addLastStmt(lFor1);
Var lVj = sym.defineVar("j", symRoot.typeInt);
//-- aa[i] = 100; j = j - 1; }
SubscriptedExp lExp1 = hir.subscriptedExp(hir.varNode(lVaa),
hir.varNode(lVj)); // aa[i]
Stmt lAssign6 = hir.assignStmt(lExp1, hir.narNode(lVj)); // aa[i]=j;
lBlockStmt2.addLastStmt(lAssign6); // Add to the loop body part.
//-- j = j - 1;
VarNode lVarNode10 = hir.varNode(lVj);
Exp lSub1 = hir.exp(HIR.OP_SUB, lVarNode10,
hir.intConstNode(1));
VarNode lVarNode11 = hir.varNode(lVj);
Stmt lAssign7 = hir.assignStmt(lVarNode11, lSub1);
// In HIR, reference to the same node should not be used
// in different places so as not to violate tree structure.
lBlockStmt2.addLastStmt(lAssign7); // Add to the loop body part.
(i) 多次元配列
//-- float matrix[10][20];
//-- matrix[i][j] = 1.0;
(assign 31 float
(subs 32 float
(subs 33 <VECT 20 0 float>
<var 34 <VECT 10 0 <VECT 20 0 float>> matrix>
<var 35 int i>)
<var 36 int j>)
<const 37 float 1.0F>)
これは次のようにすれば作ることができる。
VectorType lVect20 = sym.vectorType(symRoot.typeFloat, 20);
VectorType lVect10_20 = sym.vectorType(lVect20, 10);
Var lMatrix = sym.defineVar(“matrix”, lVect10_20);
VarNode lMatrixNode1 = hir.varNode(lMatrix);
Const lFloat1=sym.floatConst(“1.0”, symRoot.typeDouble);
// In C, default type of floating point constant is double.
SubscriptedExp lVarNode11 = hir.subscriptedExp(lMatrixNode1,
hir.varNode(lVi));
SubscriptedExp lVarNode12 = hirSubscriptedExp(lVarNode11,
hir.varNode(lVj));
AssignStmt lAssign11 = hir.assignStmt(lVarNode12,
hir.constNode(lVarNode12, hir.constNode(lFloat1));
lBlockStmt1.addLastStmt(lAssign11); // Add to the main body.
(j) プロトタイプ宣言
関数のプロトタイプ宣言に対しては、関数名の他に仮引数の情報等を
記録する。現記号表symTableCurrentが大域的記号の記号表SymTableRoot
となっているとすれば、その処理は次のようにする。
//-- int printf(char* pFormat, ...);
Subp lPrintf = sym.defineSubp("printf", symRoot.typeInt);
PointerType lCharPtr = sym.pointerType(symRoot.typeChar);
SymTable lLocalSymTable1 = symRoot.symTableRoot.
pushSymTable(lPrintf); // Symbol table local to printf.
Param lParam1 = sym.defineParam("pFormat",
symRoot.typeStringAny); // Character array
// whose element count is not yet specified.
lPrintf.addParam(lParam1);
lPrintf.setVisibility(Sym.SYM_EXTERN);
lPrintf.setOptionalParam(); // This has optional parameter
// specification …
lPrintf.closeSubpHeader(); // End of parameter specification.
lLocalSymTable1.popSymTable(); // Pop off the local symbol table.
これによって、次のような項目が記号表に記載される。
SymTable Root
subp printf <SUBP <<PTR char>> true int> (flags 6) extern
type <PTR char> size 4
…
SymTable printf parent SymTable Root subp printf
param pFormat 0 < PTR char > in printf private auto
param _param1 0 int in printf (flags 2) private auto
type <SUBP << PTR char > true int>
(k) 関数呼び出し
関数呼び出しは、HIRでは次のように表現する。
//-- printf("%d %d \n", a, b);
(expStmt 22 int
(call 23 int
(addr 24 <PTR <SUBP <<PTR char>> true int>>
<subp 25 <SUBP <<PTR char>> true int> printf> )
(list 26
<const 27 <VECT 10 0 char> "\"%d %d \n\"">
<var 28 int a>
<var 29 int b>)))
このHIRを作るには次のようにする。
SubpNode lSubpNode1 = hir.subpNode(lPrintf);
IrList lParamList = hir.irList(); // Prepare parameter list.
StringConst lStr1 =
sym.stringConst( ("\"" + "%d %d \n" + "\"").intern());
// Make a string constant attaching heading and trailing
// quotation marks.
ConstNode lConstNode3 = hir.constNode(lStr1);
lParamList.add(lConstNode3);
lParamList.add(hir.varNode(lVa));
lParamList.add(hir.varNode(lVb));
Stmt lCallStmt = hir.callStmt(
hir.exp(HIR.OP_ADDR, lSubpNode1), // Give address of subprog
lParamList); // and parameter list.
lBlockStmt.addLastStmt(lCallStmt);
3.2.3 HIRのテキスト表現への変換
これまでの説明に用いたHIRの表現形式は、木構造としての内部表現を文字列
(テキスト)として表したものである。HIRの内部表現をテキストに変換する
ために、次のメソッドが用意されている。HIRが正しく作られているか
どうか調べる場合などには、これらを利用する。
hir1.toString( ) : get the string representation of the HIR node hir1.
hir1.toStringShort( ) : get the short representation of the node hir1
(with operator name, index number and symbol)
hir1.toStringDetail( ) : get the full representation of the node hir1.
hir1.toStringWithChildren( ) : get the string representation of the
subtree hir1 (together with all its children),
hir1.print(n) : print the subtree hir1 together with all children
in multi-line form.
n is starting indentation column position.
ioRoot.toStringObject(hir1) : if (hir1==null) return “null”;
else return hir1.toString( );
HIRで参照される記号をテキストで表す場合には、次のメソッドが使える。
sym1.toString( ) : get the string representation of the symbol sym1.
sym1.toStringShort( ) : get the short representation of sym1.
(with symbol name and index number)
sym1.toStringDetail( ) : get the detailed representation of sym1
with representation of all attributes.
3.2.4 HIRの走査
HIRで表現されたプログラムの変換や解析、あるいは変換のための情報収集を行う
には、HIRを走査(トラバース)する必要がある。HIRは木構造なので、それは木を
走査することになるが、それを簡単にするためのイテレータやビジターのメソッド
が備えてある。
プログラムは副プログラム(Cでは関数)の列でもあるので、その各副プログラム
を順次走査してゆくには、次のように、まずgetSubpDefinitionListという
メソッドで副プログラムの列をリストとして取り出し、それにイテレータを作用させる。
coins.ir.IrList lSubpDefList // Get the list of subprogram definition.
= ((Program)hirRoot.programRoot).getSubpDefinitionList();
Iterator lSubpDefIterator = lSubpDefList.iterator();
while (lSubpDefIterator.hasNext()) { // Traverse all subprogram
SubpDefinition lSubpDef = // definitions.
(SubpDefinition)(lSubpDefIterator.next());
System.out.println("\nSubpDefinition " + // Show the name
lSubpDef.getSubpSym().toString() + "\n" ); // of subprogram.
}
副プログラムの実行文を走査するには、次のように、
まずgetHirBodyというメソッドで実行文全体を表す木構造をとりだし、
それに対してHirIteratorというイテレータでその各ノードを走査すればよい。
SubpDefinition lSubpDef = ….
HIR lSubpBody = lSubpDef.getHirBody( ); //Get subprogram body.
HIR lNode;
for (HirIterator lHirIterator = lHirBody.hirIterator(lHirBody);
lHirIterator.hasNext(); ) { // Traverse all nodes of
lNode = lHirIterator.next(); // the HIR subtree lHirBody.
// ioRoot.printOut.print("\nHir " +
// ioRoot.toStringObject(lNode));
if (lNode instanceof IfStmt) { // Do some processing
… // for each if-statement.
}else if (lNode instanceof LoopStmt) { // Do some processing
… // for each loop statement.
}
....
}
HIRを走査するには、ビジターを使う方法もある。HirVisitorModel2等の
ビジターモデルが備えてあるので、次のように、それを継承(extend)する
クラス(例えばOptHirPrimary)を作り、その中で、
式の処理はatExpで、
if文の処理はatIfStmtで
というようにして記述する。
(これについてはあとの小節でさらに詳しく説明する。)
public class OptHirPrimary extends HirVisitorModel2
{
…
public void atExp(coins.ir.hir.Exp p) // For each expression
{
visitChildren(p); // Traverse children.
… // Do processing for this expression.
}
public void atIfStmt(coins.ir.hir.IfStmt p) // For each if-statement
{
visitChildren(p); // Traverse children.
… // Do processing for this if-statement.
}
…
}
public void visitChildren( HIR pHir )
{
HIR lChildNode;
if (pHir == null)
return;
for (int i = 1; i <= pHir.getChildCount(); i++) {
lChildNode = (HIR)pHir.getChild(i);
if (lChildNode != null) {
lChildNode.accept(this);
}
}
} // visitChildren
3.2.5 HIRの変換
HIRを最適化や並列化等の処理のために書きかえるとすると、それは木構造
を変換することなので、いくつか留意すべき点がある。
(a) 留意事項1:枝先が部分木間でリンクされないようにする
HIRを変換するには、ノードのリンクを張り替えるのではなく、
新規に作った部分木か複写して作った部分木で古い部分木を
置き換えるようにしなければならない。そうでないと、異なる
部分木の枝先がつながってしまって木構造でなくなり、処理が無限ループ
に陥ったりする。
部分木の複写や置き換えのためのメソッドとしては、次のものが
備えてある。
hir1.copyWithOperands( ) : copy the HIR subtree hir1
including all its descendants.
hir1.copyWithOperandsChangingLabels( ) : copy the HIR subtree
hir1 including all its descendants generating unique labels
if hir1 contains label definitions.
hir1.replaceThisNode(pNewNode) : replace hir1 with pNewNode.
hir1.setChild( i, pNewChild ) : replace the i-th child of hir1
with pNewChild.
これらのメソッドを使うと、複写して作ったオペランドに対してある演算子を
作用させて新しい式を作るような処理は、次のように記述できる。
Exp reorderOperands( Exp pExp ) { // Make evaluable operand
if ((pExp == null )||(pExp.getChildCount() != 2)) // as 1st operand.
return pExp;
Exp lChild1 = (Exp)pExp.getChild1();
Exp lChild2 = (Exp)pExp.getChild2();
if (lChild2.isEvaluable()&& (! lChild1.isEvaluable())&&
isCommutative(pExp)) { // If commutative expression, rebuild
Exp lExp = hirRoot.hir.exp(pExp.getOperator(), // expression
(Exp)lChild2.copyWithOperands(), // so that 1st operand
(Exp)lChild1.copyWithOperands()); // is evaluable expression
return lExp; // (constant expression).
}else
return pExp; // If condition is not satisfied, do not transform.
} // reorderOperands
(b) 留意事項2:走査中の木構造の下位の枝を変更しない
イテレータやビジターを使うとき、走査中の部分木の下位の枝を変更すると、
イテレータやビジターが誤動作し、処理が無限ループに陥ったりする。
イテレータやビジターを使わない場合も、置き換えたものをふたたび
走査して誤った処理を行ったりする。
したがって、ある部分木を変換するとすれば、その下位の部分木をすべて走査し
終わってから行わなければならない。すなわち、1つの部分木に対しては、
それに対してどのような変換を行うかを調べる処理や準備作業をすませてから
その部分木に対する変換を行う
というようにしなければならない。
public void atExp(coins.ir.hir.Exp p) {
… // Do transformation for this expression. -- 誤り
visitChildren(p); // Traverse children.
}
public void atExp(coins.ir.hir.Exp p) {
… // Do processing without transformation.
visitChildren(p); // Traverse children.
… // Do transformation for this expression. -- 正しいやりかた
}
先に述べたように、部分木aを部分bで置き換える場合は、bを新規に作ってから
aをbで置き換えるようにする。変換を間違えずに行うには、HIRで表現された
木構造を調べて、そのうちの置き換えを行うべき部分木 a1, a2, ... を
記録しながら、それらを置き換えるための部分木 b1, b2, ... を作ってゆく
というような準備作業を行い、それが全部終わってからa1をb1で、a2をb2で、...
というように置き換えるというのが1つの方法である。
(c) 留意事項3:変換後に後処理をする
1つの副プログラム全体、あるいはプログラム全体に対して、改変処理が
終わったら、HIRを木構造として整合性のとれた形に整える必要がある。
そのため、1つの副プログラムに対する改変が全部終わったら、それに対する
SubpDefinitionノード(たとえばlSubpDef)に対して、
lSubpDef.finishHir();
のようにして、後始末を行うメソッドfinishHirを作用させる。
finishHirでは、
木構造が正しく作られているか否か検査する
HIRの各ノードに、フロー解析などのときに使われるノード番号をつける
ラベルからその定義位置がわかるようにするリストを作る
などの処理を行う。
改変した副プログラムに対する新たな最適化や並列化の処理、あるいはコード生成
等の処理は、finishHirを呼んだあとで行う。
finishHirは、HIRに異常がなければtrueを返し、異常があればfalseを返す。
なお、全ての副プログラムに対して次々と改変処理を行い、最後にまとめて
コード生成をするような場合は、副プログラムごとにfinishHirを呼ぶのではなく、
プログラム全体に対して最後に一度
if (((HIR)hirRoot.programRoot).finishHir()) {
正常処理
}else {
エラー処理
}
のようにして作用させればよい。
(d) インスタンスの種類別処理
HIRでは、式を表す部分木はExpクラスのインスタンス、文を表す部分木は
Stmtクラスのインスタンスというように、意味を持つ部分木は何かのクラスの
インスタンスである。それらに対して、種類に応じた処理を行うには、
イテレータやビジターを使えばよい。
イテレータでは、次のように、instanceof で何のインスタンスであるかを判別して、
対応する処理を行う。
HIR lNode;
for (HirIterator lHirIterator = lHirBody.hirIterator(lHirBody);
lHirIterator.hasNext(); ) { // Traverse all nodes of
lNode = lHirIterator.next(); // the HIR subtree lHirBody.
if (lNode instanceof VarNode) { // Do some processing for variable.
…
}else if (lNode instanceof Exp) { // Do some processing for
switch (lNode.getOperator()) { // expressions other than variable.
case HIR.OP_ADD:
case HIR.OP_MULT:
…
break;
default: break;
}
}else ....
}
ビジターを使うときは、次のように、atVarNode、atExp等で何のインスタンス
であるかを識別して処理を行う。
public class OptHirPrimary extends HirVisitorModel2 {
…
public void atVarNode(coins.ir.hir.VarNode p) { // For each variable.
… // Do processing for this VarNode.
}
public void atExp(coins.ir.hir.Exp p) { // Expression other than var.
visitChildren(p); // Traverse children.
switch (lNode.getOperator()) {
case HIR.OP_ADD:
case HIR.OP_MULT:
… break;
default: break;
}
}
…
}
(e) 演算のコンパイル時実行
最適化などの処理においては、コンパイル時に実行できる演算を実行して、
式を定数ノードで置き換えてしまう場合がある。そのような処理に使う
メソッドとして
isEvaluable : 式がコンパイル時に実行可能か否か判定
isInteger : 式が整数式か否か判定
evaluateAsInt: 式の演算を実行して結果の整数値を返す
intConstNode : 与えられた整数値をもつ定数ノードを作る
等がある。これらを使うと、整数式のコンパイル時評価(コンパイル時実行)は
次のように書くことができる。
public void atExp(coins.ir.hir.Exp p)
{
visitChildren(p);
Exp lNewExp = evaluateIfPossible(p);
if (p != lNewExp) // If p is really evaluated,
p.replaceThisNode(lNewExp); // then replace p with lNewExp.
}
Exp evaluateIfPossible( Exp pExp ) {
if (pExp.isEvaluable()&& // If pExp is constant expression
pExp.getType().isInteger()) { // and its type is integer, then
Exp lEvaluated = hirRoot.hir.intConstNode( // make constant node
evaluateAsInt()); // with evaluated value.
return lEvaluated; // Floating point evaluation is not recommended
} // because it may depend on runtime environment.
return pExp;
}
3.2.6 HIRの変換例
これまでに説明したことを心得ていると、簡単な最適化変換などを記述
することができる。例として、定数の畳み込みと言われる定数式の
コンパイル時評価を検討してみる。
a = 1 + 2 + b;
b = 1 + 2 * 3 + c;
を
a = 3 + b;
b = 7 + c;
のように置き換えることは、通常の定数畳みこみで行われる。
これらの変換は、
優先順位の同じ演算子は左から順次結合してゆく
演算子の交換はしない
という制約があっても実行できる。
ところが、上記制約があると
x = ff(1) + 2 + 3;
y = x * 2 * 3;
z = 3 + y + 4 + 5;
に対しては定数畳みこみを実行できない。この制約をとりはらって、
演算子 + と * については、副作用のない場合、結合順序の変更や
演算子の交換が許されるとして、上記の式を
x = 2 + 3 + ff(1);
y = 2 * 3 * x;
z = 3 + 4 + 5 + y;
と変換したあと、左から順次コンパイル時に演算できる式は演算してしまう
とすれば、上記の式は
x = 5 + ff(1);
y = 6 * x;
z = 12 + y;
と変換できる。
この変換をビジターを使ったプログラムとして書くと次のようになる。
(注:このプログラムは、COINSのリリース番号1.4.4.4以降の版では
src/coins/opt/OptHirPrimary.java
として、COINSコンパイラの一部として入っている。しかし、それを
起動させる文は注釈に変えてあって、通常は起動されない。
その呼び出し部分を変更すると動かすことができ、
-coins:trace=HIR.2 とすると、変換結果を確認できるとともに、
ビジターによる動作を見ることもできる。)
package coins.opt;
import java.util.Iterator;
import coins.HirRoot;
import coins.ir.hir.*;
/** OptHirPrimary:
* Simple constant folding assuming that associative rule and
* commutative rule are permitted for addition and multiplication.
**/
public class
OptHirPrimary extends HirVisitorModel2
{
public
OptHirPrimary( HirRoot pHirRoot )
{
super(pHirRoot);
}
public void atExp(coins.ir.hir.Exp p)
{
visitChildren(p);
Exp lEvaluated = null;
Exp lEvaluatedOperand = null;
Exp lReordered = reorderOperands(p);
Exp lChild1 = (Exp)lReordered.getChild1();
Exp lChild2 = (Exp)lReordered.getChild2();
if (lChild1.isEvaluable()&&(lChild2 != null)&&
(! lChild2.isEvaluable())) {
Exp lGrandChild1 = (Exp)lChild2.getChild1();
if ((lGrandChild1 != null)&&
lGrandChild1.isEvaluable()&&
(lChild2.getOperator() == p.getOperator())&&
isAssociative(p)) {
Exp lEvaluable = hirRoot.hir.exp(p.getOperator(),
(Exp)lChild1.copyWithOperands(),
(Exp)lGrandChild1.copyWithOperands());
if (p.getType().isInteger()) {
lEvaluatedOperand = hirRoot.hir.intConstNode(lEvaluable.evaluateAsInt());
lEvaluated = hirRoot.hir.exp(p.getOperator(), lEvaluatedOperand,
(Exp)((Exp)lChild2.getChild2()).copyWithOperands());
}
}
}
if (lEvaluated != null) {
p.replaceThisNode(lEvaluated);
}else if (p != lReordered) {
p.replaceThisNode(lReordered);
}
}
public void atProgram(coins.ir.hir.Program p) {
visitChildren(p); }
public void atSubpDefinition(coins.ir.hir.SubpDefinition p) {
visitChildren(p);
}
public void atBlockStmt(coins.ir.hir.BlockStmt p) {
visitChildren(p);
for (Stmt lStmt = p.getFirstStmt(); lStmt != null;
lStmt = lStmt.getNextStmt()) {
lStmt.accept(this);
}
}
public void atHirList(coins.ir.hir.HirList p) {
HIR lHir;
for (Iterator lIterator = p.iterator(); lIterator.hasNext(); ) {
lHir = (HIR)lIterator.next();
if (lHir != null) {
visit(lHir);
}
}
} // atHirList
public void atIrList(coins.ir.IrList p) {
visitChildren((HIR)p); }
public void atHirSeq(coins.ir.hir.HirSeq p) {
visitChildren((HIR)p); }
public void atInfNode(coins.ir.hir.InfNode p) {
visitChildren(p); }
public void atInfStmt(coins.ir.hir.InfStmt p) {
visitChildren(p); }
public void atVarNode(coins.ir.hir.VarNode p) {
visitChildren(p); }
public void atElemNode(coins.ir.hir.ElemNode p) {
visitChildren(p); }
public void atSubpNode(coins.ir.hir.SubpNode p) {
visitChildren(p); }
public void atTypeNode(coins.ir.hir.TypeNode p) {
visitChildren(p); }
public void atConstNode(coins.ir.hir.ConstNode p) {
visitChildren(p); }
public void atLabelNode(coins.ir.hir.LabelNode p) {
visitChildren(p); }
public void atSymNode(coins.ir.hir.SymNode p) {
visitChildren(p); }
public void atNullNode(coins.ir.hir.NullNode p) {
visitChildren(p); }
public void atLabelDef(coins.ir.hir.LabelDef p) {
visitChildren(p); }
public void atSubscriptedExp(coins.ir.hir.SubscriptedExp p) {
visitChildren(p); }
public void atQualifiedExp(coins.ir.hir.QualifiedExp p) {
visitChildren(p); }
public void atPointedExp(coins.ir.hir.PointedExp p) {
visitChildren(p); }
public void atFunctionExp(coins.ir.hir.FunctionExp p) {
visitChildren(p); }
public void atAssignStmt(coins.ir.hir.AssignStmt p) {
visitChildren(p); }
public void atIfStmt(coins.ir.hir.IfStmt p) {
visitChildren(p); }
public void atWhileStmt(coins.ir.hir.WhileStmt p) {
visitChildren(p); }
public void atForStmt(coins.ir.hir.ForStmt p) {
visitChildren(p); }
public void atUntilStmt(coins.ir.hir.UntilStmt p) {
visitChildren(p); }
public void atLabeledStmt(coins.ir.hir.LabeledStmt p) {
visitChildren(p); }
public void atReturnStmt(coins.ir.hir.ReturnStmt p) {
visitChildren(p); }
public void atJumpStmt(coins.ir.hir.JumpStmt p) {
visitChildren(p); }
public void atSwitchStmt(coins.ir.hir.SwitchStmt p) {
visitChildren(p); }
public void atExpStmt(coins.ir.hir.ExpStmt p) {
visitChildren(p); }
public void atPhiExp(coins.ir.hir.PhiExp p) {
visitChildren(p); }
Exp
reorderOperands( Exp pExp )
{
if ((pExp == null )||
(pExp.getChildCount() != 2))
return pExp;
Exp lChild1 = (Exp)pExp.getChild1();
Exp lChild2 = (Exp)pExp.getChild2();
if (lChild2.isEvaluable()&&
(! lChild1.isEvaluable())&&
isCommutative(pExp)) {
Exp lExp = hirRoot.hir.exp(pExp.getOperator(),
(Exp)lChild2.copyWithOperands(),
(Exp)lChild1.copyWithOperands());
return lExp;
}else
return pExp;
} // reorderOperands
boolean
isCommutative( Exp pExp )
{
if (pExp == null)
return false;
switch (pExp.getOperator()) {
case HIR.OP_ADD:
case HIR.OP_MULT:
case HIR.OP_AND:
case HIR.OP_OR:
case HIR.OP_XOR:
return true;
default:
return false;
}
} // isCommutative
boolean
isAssociative( Exp pExp )
{
if (pExp == null)
return false;
switch (pExp.getOperator()) {
case HIR.OP_ADD:
case HIR.OP_MULT:
case HIR.OP_AND:
case HIR.OP_OR:
case HIR.OP_XOR:
return true;
default:
return false;
}
} // isAssociative
} // OptHirPrimary
3.3 記号表の構成
3.3.1 全体構成
ソースプログラムに現れる変数や副プログラム、型、定数などの情報、なら
びに、コンパイラの生成する一時変数やレジスタなど、諸々の記号の情報は記
号表に保持する。同じ綴りの記号であってもスコープが異なると別物とするた
めに、副プログラムなど、新しいスコープを開くものに対応させて、そこで新
たに定義される記号(Sym)を納める記号表(SymTable)を作る。
スコープAの記号表(SymTable):
スコープAで定義される記号(Sym)を納めた表
記号の探索、登録の際は、副プログラム内の局所的な変数やレジスタなどを納
めた記号表、大域的な変数や副プログラムなどを納めた記号表など、スコープ
の入れ子関係を見ながら、入力言語の文法に従って記号の同定を行なう。
定数はコンパイル単位全体からアクセスできる定数用記号表に登録する。
コンパイル単位全体で大域的に定義された記号を納めた記号表
|ーー副プログラムAで局所的に定義された記号を納めた記号表
| |ーー副プログラムAの内側のスコープで定義された記号を納めた記号表
| …
|ーー副プログラムBで局所的に定義された記号を納めた記号表
|ーー …
入力言語がCの場合、記号表の階層は次のようになる。
symTableConst 定数(ソースプログラムに現れるものとコンパイラの生成するもの)
symTableRoot HIRに備え付けの記号(基本型など)とコンパイル単位全体で定義された記号
|- symTable A 副プログラムAで局所的に定義された記号、
| | 副プログラムAでコンパイラが生成する(定数以外の)記号。
| |- symTable A_b1 副プログラムAの中のブロックb1で定義された記号。
| |- symTable A_b1_2 ブロックb1の中のブロックb1_2で定義された記号。
| …
|- symTable B 副プログラムBで局所的に定義された記号、
| | 副プログラムBでコンパイラが生成する(定数以外の)記号。
| …
記号表の記載項(エントリ)を作るのは、Symインタフェースのvar(),
subp(), label()などのファクトリメソッドを呼んで行なう。newで直接にイ
ンスタンスを作るのを禁じているわけではないが、newで直接に作るときは、
そのための約束事を十分理解して作らないと、相互関連に不具合が生ずる可能
性が高いので、それは勧められない。
3.3.2. HIRやフロー情報との関連
HIRでは、変数や副プログラム、ラベルなどは、通常、それが記号表のどこ
に記載されているかを示す参照子(reference)として表現する。それらの型
や他の記号との関係など、種々の情報は参照子をたぐって記号表から取り出せ
るよう、アクセスメソッドが用意されている。
フロー情報の表現では、変数やレジスタなどを記号表の参照子として表すこ
ともあるが、データフロー方程式を解くときなどは、それらに一意的な識別番
号を付与して、その番号で示すこともある。その場合、
参照子から識別番号を
求めるメソッドや、識別番号から参照子を求めるメソッドなどが用意されている。
3.3.3 記号のクラス階層
記号(Sym)は、それが実際のオブジェクトとして作られるときは、変数
(Var)、副プログラム(Subp)、型(Type)、定数(Const)、ラベル(Label)、
レジスタ(Reg)などのサブクラスのオブジェクトとして作られる。これらの
サブクラスには、さらに幾つかのサブクラスに分解されるものもある。そのク
ラスの階層関係を次に示す。
Sym // Symbol class (super class of all symbol classes).
| // Symbols in the same scope are contained in the same
| // symbol table (instance of SymTable).
|
|- OperandSym // Symbol that may be an operand
| | // of executable expressions.
| |
| |- Var // Variable that can be assigned a value
| | | // and variable with const attribute.
| | |- Param // Formal parameter class.
| | |- Elem // Class for structure element,
| | // union element, etc.
| |
| |- Const // Constant class
| | |- IntConst // integer constant
| | |- FloatConst // floating constant
| | |- CharConst // character constant
| | |- StringConst // string constant
| | |- BoolConst // boolean constant
| | |- NamedConst // Named constant including
| | // enumeration constant (other than bool).
| |- Label // Statement label class.
|
|- Subp // Subprogram class (procedures, functions, etc.)
|
|- Type // Type information class.
| |- BaseType // Base types intrinsic
| | // to many programming languages.
| |- VectorTyepe // Vector (1 dim. array) type.
| |- EnumType // Enumaration type.
| |- PtrType // Pointer type.
| |- StructType // Structure type.
| |- UnionType // Union type.
| |- SubpType // Subprogram type.
| |- RegionType // Region type to define storage area
| | // shared between subprograms.
| |- DefinedType // Types defined in a program (by typedef).
|
|- ExpId // Expression identifier
// (generated to be used in data flow analysis, etc.)
3.3.4 主要な記載内容
記号表に記載された情報は、すべて、アクセスメソッドを介して参照ないし
設定する。ただし、アクセスメソッドと1対1に対応して実際のフィールドが
あるとは限らない。記載項目間の整合性を保つために、1つのメソッドが複数
のフィールドを設定することや、あるクラスのアクセスメソッドが他のクラス
のフィールドを見て値を算出することなどがある。したがって、アクセスメソ
ッドを介さずに実装されているフィールドを直接に見ることは、使い間違いを
犯しやすく、整合性を崩す原因となりやすい。具体的なアクセスメソッドにつ
いては、Sym0インタフェース、Symインタフェース、Typeインタフェース、
ならびにその下位のインタフェースを参照されたい。
- 全部の記号に共通な内容(Sym)
- 名前の綴り
(getName())
- 記号の種類
(変数、副プログラム、…、 getSymKind())
- 型
(getSymType()で得られる。型を持たない(voidも持たない)記号に対してはnullが返される。)
- 定義位置
(その記号を最初に宣言した行、getDefinedLine(),
getDefinedFile())
- 一意名
(コンパイル単位全体で一意な名前、名前の綴りに同じもののある記号に対しては、
コンパイラが重複をさけるための名前を生成するgetUniqueName()。
これはSymTableのsetUniqueNameToAllSym()が呼ばれた後に有効となる。)
- フェーズ別情報(特定の処理向きの情報)へのリンク
(getWork())
- 変数(Var)
- 初期値の式
(getInitialValue())
- 設定・参照リスト等のデータフロー情報
(getDefUseList() etc. in FlowAnalSym)
- 独立変数(仮引数でも要素でもない変数)
- 可視性(extern, public, private, ...)指定
(getVisibility())
- 記憶域(auto, static, register)指定
(getStorageClass())
- 仮引数(Param)
- 何番目の仮引数か
(getParamIndex())
- call-by-value, call-by-referenceの区別
- 要素(構造体、共用体の)(Elem)
ーー 構造体変数、共用体変数の各要素ごとに作成
- 変位
(変位は式として表現可能、evaluateDisp())
- この要素を含む構造体または共用体
(getUpperType())
- ビットフィールドか否か、ビットフィールドの場合はそのビット数
- 副プログラム(Subp)
- 返却値の型(getReturnValueType())
- 仮引数リスト(getParamList())
- 可変引数リストの有無(getOptionalParam())
- 局所変数記号表(getSymTable())
- 中間表現部分木(getSubpDefinition())
- ラベルリスト(getLabelDefList())
- 呼び出し先リスト(getCallList())
- 基本ブロックのグラフ(getEntyBBlock())
- データフロー情報へのリンク(getSubpFlow())
- フェーズ別情報(getFlowInf(), ... )
内容はフェーズ別に定義し、フェーズ間で受け渡し可能
- 検出された誤りの数(getErrorCount())
- 型(Type)
- サイズ(バイト数)(getSizeValue())
- サイズ算出式(getSizeExp())
- const修飾の有無(isConst())
- volatile修飾の有無(isVolatile())
- 基本型(BaseType)
- 基本型コード(どの基本型かを表現)(getTypeKind())
- ベクター(VectorType)
- 要素の型(getElemType())
- 要素数(getElemCount())
- 要素数算出式(getElemCountExp())
- インデックス始値(getLowerBound())
- 固定長の長方形配列か否か(isRectangularArray())
- 列挙型(EnumType)
- 列挙子の順序数(getEnumSeqNumber())
- ポインタ(PtrType)
- ポイント先の型(getPointedType())
- 構造体(StructType)
- 要素のリスト(getElemList())
- 共用体(UnionType)
- 要素のリスト(getElemList())
- 副プログラム型(SubpType)
- 仮引数の型のリスト(getParamTypeList())
- 可変引数の有無(hasOptionalParam())
- 返却値の型(getReturnType())
- 命名型(typedefで命名された型)(DefinedType)
- もとの型(getOrigin())
- 定数(Const)
- 整定数(IntConst)
整定数のgetName()で得られる表記形式は、「高水準中間表現の型と意味」
で説明するように、型を区別するための接尾辞(符号なしを表すU、longを表
すL、long longを表すLL)をもつ。整定数はJavaのlongで表される
内部表現値を持つ(shortValue(), intValue(), longValue())。ただし、値が
Javaのlongで表現できる範囲を越えている場合は、isOutOfValueRange()で
trueが返却され、正しい内部表現値を持たない。
- 浮動小数点定数(FloatConst)
浮動小数点定数のgetName()で得られる表記形式は、「高水準中間表現の型
と意味」で説明するように、型を区別するための接尾辞(floatを表すF、
doubleを表すD)をもつ。浮動小数点定数はJavaのdoubleで表される
内部表現値を持つ(floatValue(), doubleValue())。ただし、値がJavaの
doubleで表現できる範囲を越えている場合は、isOutOfValueRange()でtrue
が返却され、正しい内部表現値を持たない。
- 文字定数(CharConst)
文字定数は文字の両端に引用符(')をつけた表記をもつ。文字定数の内部
表現値は、それに対応するintの内部表現値、またはunsigned charをintに
変換した内部表現値をとる。
- 文字列定数(StringConst)
文字列の表記においては、入力言語によって開始終了の印(引用符や0
等)やエスケープ文字が加わったりするが、それらを除いて表現したい文字そ
のものの列からなるものを文字列本体(string body)と呼ぶことにすると、HIR
では文字列定数の内部表現は文字列本体の前後に引用符(")をつけた形をと
る。入力言語の文字列定数を文字列本体に変換するメソッド(makeStringBody)
や、文字列本体を入力言語の文字列定数に変換するメソッド(makeCstring等)
は、SourceLanguageクラスに用意する。中間表現を印字出力するときはコン
パイラ記述言語であるJavaの表記形式に合わせて印字する。
- 文字列本体(getStringBody())
- 文字数(getLength())
- ラベル(Label)
- HIRにおけるこのラベルのついた文へのリンク(getHirPosition())
- RegionType
RegionTypeは、FortranのCOMMONのように、コンパイル単位間で共有され
る記憶場所(共通領域)を定義する集成体である。概念的には、それは副プロ
グラムごとに要素が定義される共用体のようなものであるが、1つのコンパイ
ル単位の中では、全部の副プログラムがそろわないので、不完全なままの型で
あり、リンク時にすべての要素がそろった時に初めて完全な型となる。したが
って、それは共用体のように要素を列挙する形ではなく、(structやunionの
tagに相当する)region名称によって表現される。
RegionTypeは、副プログラムと記号表の対のリストを属性としてもつ。そ
の記号表は、対応する副プログラムにおける共通領域を構成する変数の宣言か
らなる。1つの副プログラムの内部では、共通領域はstructと類似した扱い
をされ、それを構成する変数はstructの要素と同様の扱いをされる。
メソッドの詳細については、SymインタフェースのregionTypeメソッドと、
RegionTypeインタフェースで定義されたメソッドを参照されたい。
3.4 記号表の使い方
3.4.1 記号表の作り方
まず、コンパイラの初期化処理の一環として、コンパイル単位全体に共通す
る記号を入れるsymTableRootと、定数を入れるsymTableConstが作られる。
これらは
symRoot.symTableRoot
symRoot.symTableConst
に置かれる。
副プログラム定義のときには、その中で局所的に使われる記号を入れる記号表
をpushSymTable(push操作)によって作り、副プログラム終了時にそれに対
してpopSymTableを起動する(pop操作)。副プログラムの中で新しいスコー
プが始まる時(宣言を含むブロックなどの時)には、そのスコープ内での局所
的記号を入れる記号表をpushSymTableで作り、そのスコープから出るときに
popSymTableを実行する。
popSymTableは、最も最近pushSymTableしたときからあとに追加された記号を
廃棄するのではなく、以後の追加位置を戻すものであって、作成された記号表
は保存されている。したがって、記号表はツリー構造をとる。
記号表Aのもとでpushにより記号表A1を作るとA1はAの子供となる。A1
のもとでpushにより記号表A11を作り、A11をpopしたあと、pushで記号表
A12を作るとする。同じ記号表のもとでpushで作られた記号表は、兄弟とな
る。A12をpopしたあと、A1をpopし、そのあとpushでA2を作ると、A2は
A1の兄弟となる。上記の場合、記号表は
A -- A1 -- A11
| |- A12
|- A2
という階層構造をなす。1つのコンパイル単位に含まれる各副プログラムに対
して上記のことを繰り返すと、記号表のツリーが構成される。記号表のツリー
を1つ1つたどるメソッドとしては、次のものがある。
symRoot.symTableRoot symRoot.symTableCurrent symRoot.symTableCurrentSubpのようにして参照できる。
symRoot.sym.defineVar(変数名, 型) symRoot.sym.defineSubp(副プログラム名, 型) symRoot.sym.defineLabel(ラベル名) ・・・のようにして作る。詳しくはSym0インタフェースやSymインタフェースを参照されたい。 最適化などの際に一時変数や内部ラベルなどを作るには、
symRoot.symTableCurrentSubp.generateVar(型名) symRoot.symTableCurrentSubp.generateLabel()のようにする。詳しくはSymTableインタフェースを参照されたい。
SymIterator lSymIterator = symTableA.getSymIterator();
で、順次
lSymIterator.next()
と繰り返すことによって参照できる。
lSymIterator.nextVar()
とすると、変数(Var, Param, Elem)のみが次々と出てきて、変数以外の記号
はスキップされる。Iteratorを使わない場合は、
Sym lSym1, lSym;
lSym1 = symTableA.getFirstSym();
lSym = lSym1.getNextSym();
のように、記号表の最初の記号を取り出すgetFirstSym()と、ある記号の次の
記号を取り出すgetNextSym()を使って、次々と参照することができる。
SymNestIterator lSymNestIterator = symTableA.getSymNestIterator();
としたあと、
lSymNestIterator.next();
のようにすると、指定した記号表(symTableA)とその下位のすべての記号表
を全部走査して、そこに含まれる記号を順次参照することができる。このとき、
next()の代わりに
lSymNestIterator.nextVar();
を使うと、symTableAとその下位のすべての記号表に含まれる変数を順次参照
することができる。
HIRは多くの言語に対応可能としているため、かなり豊富な機能を持っている。したがってHIR.javaの中には、 単純なコンパイラでは利用しないような機能も含まれている。機能が豊富なことは初心者が理解するのに時間がかかることを意味する。
そこで、HIRに対する簡易インタフェースHIR0.javaと、Symに対する簡易インタフェースSym0.javaを設定し、 HIR0.javaとSym0.javaを理解すれば簡単なコンパイラは作成できるようにした。 実際に、 PL0コンパイラと Simpleコンパイラ はHIR0.javaとSym0.javaを使って書かれている。
これはCOINSを教育用に利用するような場合に有効である。HIR.javaはHIR0.javaを継承し、 Sym.javaはSym0.javaを継承しているので、この簡易インタフェースでカバーしきれなくなった場合、 importの仕方を変えるだけですべての機能を利用できるようになる。
その概要を説明する文書としては、 HIRとLIRの概要(pdf)、 HIRとLIRの概要(txt)、 HIRの概要(pdf)、 HIRの概要(txt)、 HIRの型と意味(pdf)、 HIRの型と意味(txt)、 記号表の概要(pdf)、 記号表の概要(txt) などを参照されたい。