3.1 高水準中間表現HIRの論理構造

 高水準中間表現は、入力言語の論理構造を表現できるとともに、多くの言語に共通する表現でなければならない。 プログラミング言語の具体形式は、言語ごとに大きく異なる。しかし、現行の手続き型言語を見ると、演算式、代入文、 if文、反復文、整数型、浮動小数点型、配列、構造体など、共通する概念を持つ。具体形式にとらわれずに、 それらの処理操作と処理対象を抽象化してゆくと、多くの言語に共通する論理構造を持つ中間表現を設定することができる。

そのようにして定めた中間表現が本コンパイラ・インフラストラクチャの高水準中間表現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
図3-1 HIRの論理構造

 プログラムには、変数や副プログラムなどの記号が現れる。これらは文字列の ままでは扱いにくいので、記号表に登録し、 HIRでは記号表の記載項として扱う。 定数も定数用の記号表に登録し、HIRではその記載項として扱う。

記号に関する種々の属性は記号表の記載項に付与する形で記録する。 これらの属性には、宣言文やプログラム構造などによって決まるものや、 構文解析、意味解析のときに設定されるものが多い。 木構造として表したHIRは処理操作を中心として表現するものであり、 宣言文の抽象構文木は表現しない。記号に関する情報は記号表に記載する。

3.2 HIRによるプログラムの表現

3.2.1 HIRのプログラム表現例

 HIRではコンパイル単位全体を1つの木として表現する。その中には一般に、 複数の副プログラム(C言語では関数)の定義が含まれる。 図3-2に具体プログラムに対する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 
図3-2 HIRの例

3.2.2 HIRの作り方

ここでは、HIRの作り方と改変しかたの概要を示す。さらに詳しいことについては、 COINSの英語のドキュメント How to use COINS Infrastructureの中の「1.3.4. HIR Handling」にある HIRの作り方の記述も参照されたい。また、 SimpleMain.java は、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コンパイラのインタフェースモジュールとして記述されている。)
HIRのメソッドの仕様を参照するには、
   HIR -- Stmt -- IfStmt
のように、必ず上位のインタフェースから参照してゆく。そうでなく、 if文(IfStmt)、文(Stmt), HIRのように、下位のインタフェースから 参照してゆくと、誤った使い方をしやすい。

(b) HIRの全体構造

HIRでは、入力されたコンパイル単位全体を1つの木構造として表現する。

  programRoot
   |- …
   |- list
    |- SubpDefinition 1
    |- SubpDefinition 2
    |- SubpDefinition 3
    …

ここで、programRootはHIR全体の木の根を表すもの(HIRインスタンス)で、 COINSコンパイラの全体を制御するDriverで用意される。

(c) HIRと記号表

すでに述べたように、プログラムに現れる記号はすべて記号表(SymTable)に記載し、 HIRでは記号クラス(Sym)のインスタンスとして表現する。記号表は記号のスコープ ごとに作成し、それらはスコープの入れ子関係に対応した木として構造化する。

  SymTableRoot -- 大域的記号
    |- SymTable 1 -- 副プログラム1の局所的記号
    |  |- SymTable 1-1 -- その中のさらに局所的な記号
    |  |- SymTable 1-2
    |  …
    |- SymTable 2 -- 副プログラム2の局所的記号
    |  |- SymTable 2-1 -- その中のさらに局所的な記号
    |  |- SymTable 2-2
    |  …

  SymTableConst -- 定数

大域的記号を入れるSymTableRootと、定数をいれるSymTableConstは、 COINSコンパイラを起動したときに最初に動くDriverによって用意される。 その他の記号表は、入力プログラムに合わせて作成してゆく。
Driverで用意されるものとしては、そのほかに
   IoRoot  ioRoot  // 入出力ファイルに関係する情報へのリンク
   SymRoot symRoot // 記号情報への元締め(全ての記号情報はここからたどれる)
   HirRoot hirRoot // HIR情報への元締め(全てのHIR情報はここからたどれる)
等がある。

(d) コンパイル単位

コンパイルに必要な情報をすべて含んだプログラムをコンパイル単位というが、 それは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) 変数宣言と定数定義

変数宣言 int a, i; に対しては、次のような処理をする。
  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) 代入文

代入文は次のように assign で表現する。
//-- 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文のHIRは次のような形をとる。
//-- 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) ループ文

ループ文のHIRは、すこし複雑であるが、次のようになる。
//-- 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) 多次元配列

多次元配列は、配列の配列として表現する。2次元の場合は次のように表す。
//-- 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インタフェース、 ならびにその下位のインタフェースを参照されたい。

  1. 全部の記号に共通な内容(Sym)
    • 名前の綴り
      (getName())
    • 記号の種類
      (変数、副プログラム、…、 getSymKind())

    • (getSymType()で得られる。型を持たない(voidも持たない)記号に対してはnullが返される。)
    • 定義位置
      (その記号を最初に宣言した行、getDefinedLine(), getDefinedFile())
    • 一意名
      (コンパイル単位全体で一意な名前、名前の綴りに同じもののある記号に対しては、 コンパイラが重複をさけるための名前を生成するgetUniqueName()。 これはSymTableのsetUniqueNameToAllSym()が呼ばれた後に有効となる。)
    • フェーズ別情報(特定の処理向きの情報)へのリンク
      (getWork())
  2. 変数(Var)
    • 初期値の式
      (getInitialValue())
    • 設定・参照リスト等のデータフロー情報
        (getDefUseList() etc. in FlowAnalSym)
    1. 独立変数(仮引数でも要素でもない変数)
      • 可視性(extern, public, private, ...)指定
        (getVisibility())
      • 記憶域(auto, static, register)指定
        (getStorageClass())
    2. 仮引数(Param)
      • 何番目の仮引数か
        (getParamIndex())
      • call-by-value, call-by-referenceの区別
    3. 要素(構造体、共用体の)(Elem)
      ーー 構造体変数、共用体変数の各要素ごとに作成
      • 変位
        (変位は式として表現可能、evaluateDisp())
      • この要素を含む構造体または共用体
        (getUpperType())
      •  ビットフィールドか否か、ビットフィールドの場合はそのビット数
  3. 副プログラム(Subp)
    • 返却値の型(getReturnValueType())
    • 仮引数リスト(getParamList())
    • 可変引数リストの有無(getOptionalParam())
    • 局所変数記号表(getSymTable())
    • 中間表現部分木(getSubpDefinition())
    • ラベルリスト(getLabelDefList())
    • 呼び出し先リスト(getCallList())
    • 基本ブロックのグラフ(getEntyBBlock())
    • データフロー情報へのリンク(getSubpFlow())
    • フェーズ別情報(getFlowInf(), ... )
       内容はフェーズ別に定義し、フェーズ間で受け渡し可能
    • 検出された誤りの数(getErrorCount())
  4. 型(Type)
    • サイズ(バイト数)(getSizeValue())
    • サイズ算出式(getSizeExp())
    • const修飾の有無(isConst())
    • volatile修飾の有無(isVolatile())
    1. 基本型(BaseType)
      • 基本型コード(どの基本型かを表現)(getTypeKind())
    2. ベクター(VectorType)
      • 要素の型(getElemType())
      • 要素数(getElemCount())
      • 要素数算出式(getElemCountExp())
      • インデックス始値(getLowerBound())
      • 固定長の長方形配列か否か(isRectangularArray())
    3. 列挙型(EnumType)
      • 列挙子の順序数(getEnumSeqNumber())
    4. ポインタ(PtrType)
      • ポイント先の型(getPointedType())
    5. 構造体(StructType)
      • 要素のリスト(getElemList())
    6. 共用体(UnionType)
      • 要素のリスト(getElemList())
    7. 副プログラム型(SubpType)
      • 仮引数の型のリスト(getParamTypeList())
      • 可変引数の有無(hasOptionalParam())
      • 返却値の型(getReturnType())
    8. 命名型(typedefで命名された型)(DefinedType)
      • もとの型(getOrigin())
  5. 定数(Const)
    1. 整定数(IntConst)
       整定数のgetName()で得られる表記形式は、「高水準中間表現の型と意味」 で説明するように、型を区別するための接尾辞(符号なしを表すU、longを表 すL、long longを表すLL)をもつ。整定数はJavaのlongで表される 内部表現値を持つ(shortValue(), intValue(), longValue())。ただし、値が Javaのlongで表現できる範囲を越えている場合は、isOutOfValueRange()で trueが返却され、正しい内部表現値を持たない。
    2. 浮動小数点定数(FloatConst)
       浮動小数点定数のgetName()で得られる表記形式は、「高水準中間表現の型 と意味」で説明するように、型を区別するための接尾辞(floatを表すF、 doubleを表すD)をもつ。浮動小数点定数はJavaのdoubleで表される 内部表現値を持つ(floatValue(), doubleValue())。ただし、値がJavaの doubleで表現できる範囲を越えている場合は、isOutOfValueRange()でtrue が返却され、正しい内部表現値を持たない。
    3. 文字定数(CharConst)
       文字定数は文字の両端に引用符(')をつけた表記をもつ。文字定数の内部 表現値は、それに対応するintの内部表現値、またはunsigned charをintに 変換した内部表現値をとる。
    4. 文字列定数(StringConst)
       文字列の表記においては、入力言語によって開始終了の印(引用符や0 等)やエスケープ文字が加わったりするが、それらを除いて表現したい文字そ のものの列からなるものを文字列本体(string body)と呼ぶことにすると、HIR では文字列定数の内部表現は文字列本体の前後に引用符(")をつけた形をと る。入力言語の文字列定数を文字列本体に変換するメソッド(makeStringBody) や、文字列本体を入力言語の文字列定数に変換するメソッド(makeCstring等) は、SourceLanguageクラスに用意する。中間表現を印字出力するときはコン パイラ記述言語であるJavaの表記形式に合わせて印字する。
      • 文字列本体(getStringBody())
      • 文字数(getLength())
  6. ラベル(Label)
    • HIRにおけるこのラベルのついた文へのリンク(getHirPosition())
  7. 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つたどるメソッドとしては、次のものがある。  記号表には、その所有者を記録する(getOwner())。副プログラムの局所変 数等を記録する記号表の所有者はその副プログラムであるが、一般には、その 記号表の下にさらに別の記号表が作られる。symTableRootやsymTableConst の所有者はnullである。

3.4.2 記号表の初期化

 記号関連の共通情報をおさめたクラスSymRootのインスタンスを作ったあと、 それをinitiate()によって初期化すると、コンパイル単位全体に共通する記 号を入れるsymTableRootと、定数を入れるsymTableConstが作られる。その とき、symTableRootにはHIRの基本型などの備え付け記号が記載される。(一 番外側の)副プログラムの処理を開始するときは、symTableRootのもとでそ の副プログラムで局所的に定義する記号用の記号表を作る。SymRootには、 symTableRoot, symTableConstの他に、次の記号表レファレンスがある。 フロー解析や最適化、並列化変換のとき、symTableCurrentと symTableCurrentSubpを適切に設定しておかないと記号表関連のメソッドが正 しく働かないことがある。これらの記号表は、
  symRoot.symTableRoot
  symRoot.symTableCurrent
  symRoot.symTableCurrentSubp
のようにして参照できる。

3.4.3 記号の作り方

 記号表に入れる記号は、newを使って直接にコンストラクタを呼び出すので はなく、記号を作成するファクトリーメソッドを使って、
  symRoot.sym.defineVar(変数名, 型)
  symRoot.sym.defineSubp(副プログラム名, 型)
  symRoot.sym.defineLabel(ラベル名)
  ・・・
のようにして作る。詳しくはSym0インタフェースやSymインタフェースを参照されたい。  最適化などの際に一時変数や内部ラベルなどを作るには、
  symRoot.symTableCurrentSubp.generateVar(型名)
  symRoot.symTableCurrentSubp.generateLabel()
のようにする。詳しくはSymTableインタフェースを参照されたい。

3.4.4 Iterator

 記号表symTableAの中の記号は
     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とその下位のすべての記号表に含まれる変数を順次参照 することができる。

     

3.5 参考ドキュメント

3.5.1 HIRと記号表の簡易インタフェース

 HIRの仕様はHIR.javaというファイルに、記号表の仕様はSym.javaというファイルに、 Java言語のinterfaceとして書かれている。

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の仕方を変えるだけですべての機能を利用できるようになる。

3.5.2 HIRと記号表の詳細仕様

HIRの詳細な仕様は、coins.ir.hirパッケージにあるHIR0.javaとHIR.java、 およびcoins.symパッケージにあるSym0.javaとSym0.javaに記述してある。

その概要を説明する文書としては、 HIRとLIRの概要(pdf)HIRとLIRの概要(txt)HIRの概要(pdf)HIRの概要(txt) HIRの型と意味(pdf)HIRの型と意味(txt) 記号表の概要(pdf)記号表の概要(txt) などを参照されたい。