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

そのようにして定めた中間表現が本コンパイラ・インフラストラクチャの高水準中間表現HIR (High-level Intermediate Representation)である。

　HIRでは、処理操作はオペレータとそのオペランドとして表現される。オペランドとしては処理操作の結果も許されるので、 オペレータとそのオペランドを線で結んでゆくと、処理操作は木構造として表現できる。処理対象はスカラー量と配列、構造体、共用体として表現できる。

　HIRは次の特徴を持つ。

• 現在使われている多くの手続き型言語に対応できる。
• 記述水準はC言語に近く、HIRからCへの逆変換を可能としている。
• 式、代入文、if文など、高級言語の諸機能とほぼ１対１に対応するファクトリーメソッドを備え、それによってHIRを作成できる。
• HIRの走査、変換を行う各種のメソッドを備えている。

　HIRの論理構造を次の図3-１に示す。

   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は処理操作を中心として表現するものであり、 宣言文の抽象構文木は表現しない。記号の情報は記号表に記載する。

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.1 HIRの作り方

COINSの英語のドキュメント How to use COINS Infrastructureの中の「1.3.4. HIR Handling」にHIRの作り方の記述があります。また、 SimpleMain.java は作り方を示すサンプルプログラムです。

3.3 記号表の構成

3.3.1 全体構成

　　スコープAの記号表（SymTable）：
　　　　スコープAで定義される記号（Sym）を納めた表

　コンパイル単位全体で大域的に定義された記号を納めた記号表
　　｜ーー副プログラムAで局所的に定義された記号を納めた記号表
　　｜　　　｜ーー副プログラムAの内側のスコープで定義された記号を納めた記号表
　　｜　　　　　　…
　　｜ーー副プログラムBで局所的に定義された記号を納めた記号表
　　｜ーー　…

symTableConst　　定数（ソースプログラムに現れるものとコンパイラの生成するもの）

symTableRoot 　　HIRに備え付けの記号（基本型など）とコンパイル単位全体で定義された記号
   |- symTable A　　副プログラムAで局所的に定義された記号、
   |　|　　　　　　　副プログラムAでコンパイラが生成する（定数以外の）記号。　　　
   |　|- symTable A_b1　　副プログラムAの中のブロックb1で定義された記号。
   |　　　|- symTable A_b1_2　ブロックb1の中のブロックb1_2で定義された記号。
   |　　　　　　…
   |- symTable B　　副プログラムBで局所的に定義された記号、
   |　|　　　　　　　副プログラムBでコンパイラが生成する（定数以外の）記号。
   |　　　…

3.3.2. HIRやフロー情報との関連

　フロー情報の表現では、変数やレジスタなどを記号表の参照子として表すこ ともあるが、データフロー方程式を解くときなどは、それらに一意的な識別番 号を付与して、その番号で示すこともある。その場合、 参照子から識別番号を 求めるメソッドや、識別番号から参照子を求めるメソッドなどが用意されている。

3.3.3 記号のクラス階層

   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 //##24
     |    |              //   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. 全部の記号に共通な内容（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のように、コンパイル単位間で共有され る記憶場所（共通領域）を定義する集成体である。概念的には、それは副プロ グラムごとに要素が定義される共用体のようなものであるが、１つのコンパイ ル単位の中では、全部の副プログラムがそろわないので、不完全なままの型で あり、リンク時にすべての要素がそろった時に初めて完全な型となる。したが って、それは共用体のように要素を列挙する形ではなく、（structやunionの tagに相当する）region名称によって表現される。
   　RegionTypeは、副プログラムと記号表の対のリストを属性としてもつ。そ の記号表は、対応する副プログラムにおける共通領域を構成する変数の宣言か らなる。１つの副プログラムの内部では、共通領域はstructと類似した扱い をされ、それを構成する変数はstructの要素と同様の扱いをされる。
   　メソッドの詳細については、SymインタフェースのregionTypeメソッドと、 RegionTypeインタフェースで定義されたメソッドを参照されたい。

3.4 記号表の使い方

3.4.1 記号表の作り方

　　　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

• getParent
  thisで示される記号表を作ったときの親の記号表を求める
• getFirstChild
  thisのもとで最初に作られた記号表を求める
• getBrother
  thisと同じ親のもとで次に作られた記号表を求める

3.4.2 記号表の初期化

• symTableCurrent
  現在処理中の最も内側のスコープに対する記号表
• symTableCurrentSubp
  現在処理中の副プログラムの記号表

　　symRoot.symTableRoot
　　symRoot.symTableCurrent
　　symRoot.symTableCurrentSubp

3.4.3 記号の作り方

　　symRoot.sym.defineVar(変数名, 型)
　　symRoot.sym.defineSubp(副プログラム名, 型)
　　symRoot.sym.defineLabel(ラベル名)
　　・・・

　　symRoot.symTableCurrentSubp.generateVar(型名)
　　symRoot.symTableCurrentSubp.generateLabel()

3.4.4 Iterator

     SymIterator lSymIterator = symTableA.getSymIterator();

     lSymIterator.next()

     lSymIterator.nextVar()

     Sym lSym1, lSym;
     lSym1 = symTableA.getFirstSym();
     lSym  = lSym1.getNextSym();

     SymNestIterator lSymNestIterator = symTableA.getSymNestIterator();

     lSymNestIterator.next();

     lSymNestIterator.nextVar();

3.5 参考ドキュメント

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

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とLIRの概要（pdf）、 HIRとLIRの概要（txt）、 HIRの概要（pdf）、 HIRの概要（txt）、 HIRの型と意味（pdf）、 HIRの型と意味（txt）、 記号表の概要（pdf）、 記号表の概要（txt） などを参照されたい。