別名解析レベル1の仕様

                   2003/11/10 渡辺 坦

 

目次

 1.別名解析のインタフェース仕様

 2.別名情報の使われ方

 3.別名解析の起動仕方

 

 

1.別名解析のインタフェース仕様

 

(1)別名解析のレベル

レベル1

  フロー解析しない別名解析。

  コード最適化をしない最適化レベル0ではこの段階にとどめる。

  別名解析の結果は、レジスタ割付や並列化などに反映する予定。

  メモリ領域は次のように区分する。

    大域変数

    局所変数

    ヒープ

レベル2

  一般のデータフロー解析情報に基づく別名解析。

  コード最適化や並列化のときに、変換の安全性を確かめるのに使う。

  メモリ領域は次のように区分する。

    コンパイル単位の外から見える大域的変数

    コンパイル単位の中でしか見えない大域的変数

      (static宣言された大域的変数)

    ヒープ

    副プログラム内のstatic変数

    副プログラム内の自動変数(スタック)

      ブロックローカルな変数も副プログラム内の自動変数と

      同じ扱いをする

    定数領域(文字列定数、初期値、他)

レベル3

  別名解析用データフロー解析に基づく別名解析

  (詳細未定)

レベル4

  副プログラム間の変数関係を調べた上での別名解析

  (これはまだ当分実現しない)。

 

(2)別名オプション

(a) 楽観的想定オプション  alias=opt

 下記の条件を満たしているものとし、満たしていない場合に予想外の

 結果が出てもそれはコンパイラの責任ではないとする。

  ・相異なる仮引数は互いに別名関係にない。

  ・配列要素の添字値は配列宣言で指定された範囲内にある。

   仮引数についても、配列要素の添字値は宣言された範囲内にある。

  ・ポインタ変数のポイント先は、(ポイント先の型として)宣言

   された型に適合しない型のデータは指さない。

  ・相異なる一時変数(コンパイラの生成した変数)は

   互いに別名関係にない。

  ・一時変数とソースプログラム変数(実行文に出現する変数)とは

   別名関係にない。

  ・局所変数と大域変数とは別名関係にない。

  ・ 配列仮引数と大域的スカラー変数は別名でない。

  ・副プログラム内static変数は、実引数でもなくアドレスも

   とられていなければ、仮引数と別名関係にない。

(b) 悲観的想定オプション(暗黙指定)  alias=pes

  ・相異なる一時変数は互いに別名関係にない。

  ・一時変数とソースプログラム変数とは別名関係にない。

  ・局所変数と大域変数とは別名関係にない。

  ・副プログラム内static変数は、実引数でもなくアドレスも

   とられていなければ、仮引数と別名関係にない。

  上記以外の楽観的想定は成り立たないことがあるとする。

  ただし、次のような「超悲観的」見方はしない。

   ・ポインタは整数に型変換できるので、整数実引数は

    ポインタを表現していることがあり得る。したがって、

    整数の加減算は実はポインタの値を変えている可能性があり、

    整数変数の番地を実引数とする関数や整数値を返す関数は

    ポインタ値を変更する可能性がある。

  すなわち、悲観的見方でも、明示的ポインタに対する演算が

  なく、アドレスを実引数として渡していなければポインタ値は

  変化しないと想定する。

 

(3)別名解析準備(副プログラムごと)

 レベル1では副プログラムの中間表現を1回走査して別名情報

 を収集する。(ただし、収集した情報の走査は複数回行われること

 がある。)

 レベル2のときは一般のデータフロー解析ルーチンに基づく解析

 を行ない、

   設定・参照リスト、到達定義

 等を求める。

 レベル3以上のときは別名解析用データフロー解析を行う。

  (添字解析、ポインタ解析等、詳細未定)

 情報を収集するのは、最適化対象となる変数に限定する。

  それが具体的に何であるかは、設計を進めながら考える。

  (局所的スカラー変数、一時変数、大域的スカラー変数、

   配列要素、ポイント先オブジェクト、・・・)

 

別名解析準備メソッド

void prepareForAliasAnalHir1( SubpDefinition pSubpDefinition );

  データフロー解析しない別名解析の準備をする。

  (別名解析レベル1)

  HIRからLIRへの変換の前にレベル1別名解析を行うために

  呼び出す。

  別名解析レベル2,3,4については未実現

 

 LIRについても同様のメソッドを用意する予定であるが未実現。

 

(4)別名判定メソッド

・用語

  オブジェクト:値を持つメモリ領域

  左辺値:値を持つメモリ領域(オブジェクト)を表わす式

      (変数やポインタ式など)

・プログラム点を指定せずに、左辺値を表わす2つの式が別名関係に

 あるか否かを判定するメソッドとして次のものを設ける。ここで、

 pVar1, pVar2は左辺値とする(が当面は変数に限定する)。

 

boolean mayAlias( HIR pVar1, HIR pVar2 );

boolean mayAlias( LIR pVar1, LIR pVar2 );  未実現

  return value

    true : pVar1とpVar2が別名関係にある可能性がある。

    false: pVar1とpVar2が別名関係にある可能性はない。

 

boolean mustAlias( HIR pVar1, HIR pVar2 );

boolean mustAlias( LIR pVar1, LIR pVar2 );  未実現

  return value

    true : pVar1とpVar2が別名関係にあることは確実である。

    false: pVar1とpVar2は別名関係にないか、

      あるいは別名であるとしても確実ではない。

 

boolean AliasGroup getAliasGroup( HIR pVar1 );

  return value

    pVar1と別名関係にある可能性のある左辺値を表すHIRノードの

    集合をHashSetとして返す。HIRノード pVar2 の表す左辺値が

    pVar1と別名関係にある可能性は、

        getAliasGroup(pVar1).contains(pVar2)

    が true なら有り、false なら無しとすることで判定できる。

 

・次のメソッドは、プログラム点pAtにおいてpVar1, pVar2が

 別名関係にあるか否かを判定する。これらはレベル2以上のときに

 有効であり、レベル1のときはプログラム点指定のないメソッドと

 同じ答えを返す。

 

boolean mayAlias( HIR pAt, HIR pVar1, HIR pVar2 );

boolean mayAlias( LIR pAt, LIR pVar1, LIR pVar2 );  未実現

  return value

    true : pVar1とpVar2が別名関係にある可能性がある。

    false: pVar1とpVar2が別名関係にある可能性はない。

 

boolean mustAlias( HIR pAt, HIR pVar1, HIR pVar2 );

boolean mustAlias( LIR pAt, LIR pVar1, LIR pVar2 );  未実現

  return value

    true : pVar1とpVar2が別名関係にあることは確実である。

    false: pVar1とpVar2は別名関係にないか、

      あるいは別名であるとしても確実ではない。

 

(5)別名グループ

・別名解析準備の処理で、変数を別名グループに分ける。

 グループ分けの仕方は、楽観的想定か悲観的想定か

 によって異なる。

 いずれの想定に基づいても、どこまで解析できるかによって、

 確実さのレベルが異なる。

 各変数は、それの属する別名グループの情報(リンク)を持つ。

・解析の精度が上がると、より小さい別名グループに属することになる。

・ある変数への設定、参照は、それの属するグループの

 すべての変数に対する設定、参照として扱う。

 

 

2. 別名情報の使われ方

 

・最適化や並列化の変換では、プログラム点AとBにおいて変数の値が

 同じであるか否か等の判定や、変換によってそれと別名関係にある

 変数に対して悪影響を与える可能性のないことの確認に別名情報が

 使われる。

・最適化処理では、あるプログラム点Aから別のプログラム点Bに至る

 までに、ある変数xの値が変更される可能性があるか否かが問題と

 なる。それはAからBに至る経路にある値設定操作(定義)によって

 xまたはxと別名関係にある変数に値が設定されたか否かを判定する

 ことである。

・ある定義によって値の設定される変数の属する別名グループを、

 説明の便宜上、その定義の別名グループと呼ぶことにする。

・点AからBに至る経路にある定義dの別名グループがxの別名グループ

 と重なりがあるなら、定義dによってxの値は変化する可能性があり、

 重なりがなければ変化しない。

 定義dによって値の設定される変数をdvとすると、

    mayAlias(A, dv, x)==true

 であればxの値が変化する可能性があり、falseであれば可能性がない。

・最適化等で、点Aで算出した変数xの値が点Bで利用可能であるか

 否かを判定するには、点AからBに至る経路にあるすべての定義変数を

 dv1, dv2, ..., dvnとし、その定義点をp1, p2, ..., pnとするとき、

    mayAlias(p1, dv1, x), mayAlias(p2, dv2, x), ...

    mayAlias(pn, dvn, x)

のいずれもがfalseであることを確認すればよい。

・点Bを入り口点としたとき、点Aの値設定に影響する可能性のある

 定義は、点Aに到達する定義であり、それらに対応するグループの

 合併集合は点Aにおける変数xの値に影響を与える変数を表す。

xとyの別名グループに重なりがあっても、点pに到達する定義の

 グループの合併集合がxの別名グループと重ならないならば、pに

 おいてxはyの影響を受けない。また、点pに到達する定義の

 グループの合併集合がyの別名グループと重ならないならば、pに

 おいてyはxの影響を受けない。

・点pにおけるxにyが影響を与える可能性がある変数の集合を求める

 場合にも別名情報が利用できる。

 

 

3.別名解析の起動仕方

 

(1)機能確認

別名解析の機能確認は、仮リリース版では

    java -classpath ./classes coins.alias.AliasDriver \

     -S -coins:alias,trace=HIR.1 xxx.c

というコマンドで行うことができる。詳しくは

    cooins.alias.AliasDriver.java

を参照されたい。

 

(2)最適化等のモジュールからの起動

最適化や並列化等のモジュールで別名解析情報を利用するには、

    SubpDefinition subpDef = ....;

    hirRoot.symRoot.useSymTableOfSubpDefinition(subpDef);

    AliasAnal lAlias = new AliasAnalHir1(hirRoot);

    lAlias.prepareForAliasAnalHir(subpDef);

    ....

    if (lAlias.mayAlias(lHirNode1, lHirNode2)) { .... }

    if (lAlias.mustAlias(lHirNode1, lHirNode2)) { .... }

    if (lAlias.getAliasGroupFor(lHirNode1).contains(lHirNode2)) {  }

    ....

のようにすればよい。具体的なやり方は

    cooins.alias.AliasDriver.java

    makeAliasAnalysis( .... )

    testAliasByOptimizing( .... )

    cooins.alias.AliasAnalHir1.java

    printAliasPairs( .... )

等を参照されたい。