2005/7/12 　ＩＶ．　記号表の概要 　　　　　　　　　　　　　　　　　　　2004/5/23, 6/9, 8/16 　　　　　　　　　　　　　　　　　　　(##25): 2004/08 改訂 　　　　　　　　　　　　　　　　　　　(##24): 2004/05-6 改訂 　　　　　　　　　　　　　　　　　　　(##21): 2003/06 改訂 　　　　　　　　　　　　　　　　　　　(##14): 2002/06 改訂 　　　　　　　　　　　　　　　　　　　(##9) : 2001/10 改訂 １．　全体構成 （１）作られ方 　ソースプログラムに現れる変数や副プログラム、型、定数などの情報、なら びに、コンパイラの生成する一時変数やレジスタなど、諸々の記号の情報は記 号表に保持する。同じ綴りの記号であってもスコープが異なると別物とするた めに、副プログラムなど、新しいスコープを開くものに対応させて、そこで新 たに定義される記号（Sym）を納める記号表（SymTable）を作る。 　　スコープAの記号表（SymTable）： 　　　　スコープAで定義される記号（Sym）を納めた表 記号の探索、登録の際は、副プログラム内の局所的な変数やレジスタなどを納 めた記号表、大域的な変数や副プログラムなどを納めた記号表など、スコープ の入れ子関係を見ながら、入力言語の文法に従って記号の同定を行なう。定数 はコンパイル単位全体からアクセスできる定数用記号表に登録する(##9)。 　コンパイル単位全体で大域的に定義された記号を納めた記号表 　　｜ーー副プログラムAで局所的に定義された記号を納めた記号表 　　｜　　　｜ーー副プログラムAの内側のスコープで定義された記号を納め た記号表 　　｜　　　　　　… 　　｜ーー副プログラムBで局所的に定義された記号を納めた記号表 　　｜ーー　… [[ 　入力言語がCの場合、記号表の階層は次のようになる。　(##9) 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で直接に作るときは、 そのための約束事を十分理解して作らないと、相互関連に不具合が生ずる可能 性が高いので、それは勧められない。(##14) 　LIRでは型やスコープ等の情報が大幅に簡単化されているので、バックエン ドで必要とする情報のみを記載したLIR用記号表を作る。本仕様書では、HIR 用の記号表について説明する。　(##24) （２）HIRとフロー情報との関連 　HIRでは、変数や副プログラム、ラベルなどは、通常、それが記号表のどこ に記載されているかを示す参照子（reference）として表現する。それらの型 や他の記号との関係など、種々の情報は参照子をたぐって記号表から取り出せ るよう、アクセスメソッドを用意する。 　フロー情報の表現では、変数やレジスタなどを記号表の参照子として表すこ ともあるが、データフロー方程式を解くときなどは、それらに一意的な識別番 号を付与して、その番号で示すこともある。その場合、参照子から識別番号を 求めるメソッドや、識別番号から参照子を求めるメソッドなどを用意する。 （３）記号のクラス階層 　記号（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 //##24 | | // shared between subprograms. | |- DefinedType // Types defined in a program (by typedef). | |- ExpId // Expression identifier // (generated to be used in data flow analysis, etc.) ２．　主要な記載内容 　記号表に記載された情報は、すべて、アクセスメソッドを介して参照ないし 設定する。ただし、アクセスメソッドと１対１に対応して実際のフィールドが あるとは限らない。記載項目間の整合性を保つために、１つのメソッドが複数 のフィールドを設定することや、あるクラスのアクセスメソッドが他のクラス のフィールドを見て値を算出することなどがある。したがって、アクセスメソ ッドを介さずに実装されているフィールドを直接に見ることは、使い間違いを 犯しやすく、整合性を崩す原因となりやすい。具体的なアクセスメソッドにつ いては、SymインタフェースとTypeインタフェース、ならびにその下位のイ ンタフェースを参照されたい。 　並列化や最適化では、配列が重要な対象となる。配列は、一般には１次元配 列であるベクター、あるいはベクターのベクター、・・・として定義できるが、 そのようにして定義した配列には種々の形態があるので、 　　　大きさ固定の長方形配列 　　　大きさを引数等で指定するconformant array 　　　分散ベクター（密着しているとは限らないベクターの集まり、 　　　　　　　　　　Javaの多次元配列など） 　　　その他の形態の配列 のいずれであるかを見分けておき、並列化や最適化の対象を認識しやすいよう にする。 （１）全部の記号に共通な内容（Sym） 　　名前の綴り（getName()） 　　記号の種類（変数、副プログラム、…、 getSymKind()） 　　型（getSymType()で得られる。型を持たない（voidも持たない） 　　　　記号に対してはnullが返される。） 　　定義位置（その記号を最初に宣言した行、getDefinedLine(), getDefinedFile()） 　　一意名（コンパイル単位全体で一意な名前、名前の綴りに同じもののある 　　　　記号に対しては、コンパイラが重複をさけるための名前を生成する 　　　　getUniqueName()。これはSymTableのsetUniqueNameToAllSym()が 　　　　呼ばれた後に有効となる。） 　　フェーズ別情報（特定の処理向きの情報）へのリンク（getWork()） （２）変数（Var） 　　初期値の式（getInitialValue()） 　　設定・参照リスト等のデータフロー情報 　　（getDefUseList() etc. in FlowAnalSym） （2-1）独立変数（仮引数でも要素でもない変数） 　　可視性（extern, public, private, ...）指定（getVisibility()） 　　記憶域（auto, static, register）指定（getStorageClass()） （2-2）仮引数（Param） 　　何番目の仮引数か（getParamIndex()） 　　call-by-value, call-by-referenceの区別 （2-3）要素（構造体、共用体の）（Elem） 　　　　　　ーー　構造体変数、共用体変数の各要素ごとに作成 　　変位（変位は式として表現可能、evaluateDisp()） 　　この要素を含む構造体または共用体（getUpperType()） 　　ビットフィールドか否か、ビットフィールドの場合はそのビット数 （３）副プログラム（Subp） 　　返却値の型（getReturnValueType()） 　　仮引数リスト（getParamList()）、 　　可変引数リストの有無（getOptionalParam()） 　　局所変数記号表（getSymTable()） 　　中間表現部分木（getSubpDefinition()） 　　ラベルリスト（getLabelDefList()） 　　呼び出し先リスト（getCallList()） 　　基本ブロックのグラフ（getEntyBBlock()） 　　データフロー情報へのリンク（getSubpFlow()） 　　フェーズ別情報（getFlowInf(), ... ） 　　　　内容はフェーズ別に定義し、フェーズ間で受け渡し可能 　　検出された誤りの数（getErrorCount()） 　　 （４）型（Type） 　　サイズ（バイト数）（getSizeValue()） 　　サイズ算出式（getSizeExp()） 　　const修飾の有無（isConst()） 　　volatile修飾の有無（isVolatile()） （4-1）基本型（BaseType） 　　基本型コード（どの基本型かを表現）（getTypeKind()） （4-2）ベクター（VectorType） 　　要素の型（getElemType()） 　　要素数（getElemCount()） 　　要素数算出式（getElemCountExp()） 　　インデックス始値（getLowerBound()） 　　固定長の長方形配列か否か（isRectangularArray()） （4-3）列挙型（EnumType） 　　列挙子の順序数（getEnumSeqNumber()） （4-4）ポインタ（PtrType） 　　ポイント先の型（getPointedType()） （4-5）構造体（StructType） 　　要素のリスト（getElemList()） （4-6）共用体（UnionType） 　　要素のリスト（getElemList()） （4-7）副プログラム型（SubpType） 　　仮引数の型のリスト（getParamTypeList()） 　　可変引数の有無（hasOptionalParam()） 　　返却値の型（getReturnType()） （4-8）命名型（typedefで命名された型）（DefinedType） 　　もとの型（getOrigin()） （５）定数（Const） （5-1）整定数（IntConst） 　整定数のgetName()で得られる表記形式は、「高水準中間表現の型と意味」 で説明するように、型を区別するための接尾辞（符号なしを表すU、longを表 すL、long longを表すLL）をもつ(##21)。整定数はJavaのlongで表される 内部表現値を持つ（shortValue(), intValue(), longValue()）。ただし、値が Javaのlongで表現できる範囲を越えている場合は、isOutOfValueRange()で trueが返却され、正しい内部表現値を持たない。 （5-2）浮動小数点定数（FloatConst） 　浮動小数点定数のgetName()で得られる表記形式は、「高水準中間表現の型 と意味」で説明するように、型を区別するための接尾辞（floatを表すF、 doubleを表すD）をもつ(##21)。浮動小数点定数はJavaのdoubleで表される 内部表現値を持つ（floatValue(), doubleValue()）。ただし、値がJavaの doubleで表現できる範囲を越えている場合は、isOutOfValueRange()でtrue が返却され、正しい内部表現値を持たない。 （5-3）文字定数（CharConst） 　文字定数は文字の両端に引用符（'）をつけた表記をもつ。文字定数の内部 表現値は、それに対応するintの内部表現値、またはunsigned charをintに 変換した内部表現値をとる。 （5-4）文字列定数（StringConst） 　文字列の表記においては、入力言語によって開始終了の印（引用符や\0 等）やエスケープ文字が加わったりするが、それらを除いて表現したい文字そ のものの列からなるものを文字列本体(string body)と呼ぶことにすると、HIR では文字列定数の内部表現は文字列本体の前後に引用符（"）をつけた形をと る。入力言語の文字列定数を文字列本体に変換するメソッド(makeStringBody) や、文字列本体を入力言語の文字列定数に変換するメソッド(makeCstring等) は、SourceLanguageクラスに用意する。中間表現を印字出力するときはコン パイラ記述言語であるJavaの表記形式に合わせて印字する。　(##25) 　　文字列本体（getStringBody()） 　　文字数（getLength()） （６）ラベル（Label） 　　HIRにおけるこのラベルのついた文へのリンク（getHirPosition()） （８）RegionType　　##24 　RegionTypeは、FortranのCOMMONのように、コンパイル単位間で共有され る記憶場所（共通領域）を定義する集成体である。概念的には、それは副プロ グラムごとに要素が定義される共用体のようなものであるが、１つのコンパイ ル単位の中では、全部の副プログラムがそろわないので、不完全なままの型で あり、リンク時にすべての要素がそろった時に初めて完全な型となる。したが って、それは共用体のように要素を列挙する形ではなく、（structやunionの tagに相当する）region名称によって表現される。 　RegionTypeは、副プログラムと記号表の対のリストを属性としてもつ。そ の記号表は、対応する副プログラムにおける共通領域を構成する変数の宣言か らなる。１つの副プログラムの内部では、共通領域はstructと類似した扱い をされ、それを構成する変数はstructの要素と同様の扱いをされる。 　メソッドの詳細については、SymインタフェースのregionTypeメソッドと、 RegionTypeインタフェースで定義されたメソッドを参照されたい。 ３．　記号表の使い方 ３．１　記号表の作り方 　まず、コンパイラの初期化処理の一環として、コンパイル単位全体に共通す る記号を入れるsymTableRootと、定数を入れるsymTableConstが作られる。 これらは 　　　symRoot.symTableRoot 副プログラム定義のときには、その中で局所的に使われる記号を入れる記号表 を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と同じ親のもとで次に作られた記号表を求める 　記号表には、その所有者を記録する（getOwner()）。副プログラムの局所変 数等を記録する記号表の所有者はその副プログラムであるが、一般には、その 記号表の下にさらに別の記号表が作られる。symTableRootやsymTableConst の所有者はnullである。 ３．２　記号表の初期化 　記号関連の共通情報をおさめたクラスSymRootのインスタンスを作ったあと、 それをinitiate()によって初期化すると、コンパイル単位全体に共通する記 号を入れるsymTableRootと、定数を入れるsymTableConstが作られる。その とき、symTableRootにはHIRの基本型などの備え付け記号が記載される。（一 番外側の）副プログラムの処理を開始するときは、symTableRootのもとでそ の副プログラムで局所的に定義する記号用の記号表を作る。SymRootには、 symTableRoot, symTableConstの他に、次の記号表レファレンスがある。 symTableCurrent 現在処理中の最も内側のスコープに対する記号表 symTableCurrentSubp 現在処理中の副プログラムの記号表 フロー解析や最適化、並列化変換のとき、symTableCurrentと symTableCurrentSubpを適切に設定しておかないと記号表関連のメソッドが正 しく働かないことがある。これらの記号表は、 　　symRoot.symTableRoot 　　symRoot.symTableCurrent 　　symRoot.symTableCurrentSubp のようにして参照できる。　(##24) ３．３　記号の作り方　##24 　記号表に入れる記号は、newを使って直接にコンストラクタを呼び出すので はなく、記号を作成するファクトリーメソッドを使って、 　　symRoot.sym.defineVar(変数名, 型) 　　symRoot.sym.defineSubp(副プログラム名, 型) 　　symRoot.sym.defineLabel(ラベル名) 　　・・・ のようにして作る。詳しくはSymインタフェースを参照されたい。 　最適化などの際に一時変数や内部ラベルなどを作るには、 　　symRoot.symTableCurrentSubp.generateVar(型名) 　　symRoot.symTableCurrentSubp.generateLabel() のようにする。詳しくはSymTableインタフェースを参照されたい。 ３．４　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とその下位のすべての記号表に含まれる変数を順次参照 することができる。 -------- 実装状況： ・wchar, wstring 未実装 削除した項目 　HIRとLIRでの記号表の共有　##24 Reg, MReg, ARegの記述　050712