WEKO3
アイテム
静的単一代入形式を用いた構造体型のポインタ変数解析アルゴリズム
http://hdl.handle.net/10076/12898
http://hdl.handle.net/10076/128986f12291f-95ac-4de5-8a72-48e73d0aa36c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
2011M250.pdf (1.1 MB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-06-11 | |||||||
| タイトル | ||||||||
| タイトル | 静的単一代入形式を用いた構造体型のポインタ変数解析アルゴリズム | |||||||
| 言語 | ja | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||||
| 資源タイプ | thesis | |||||||
| 著者 |
木下, 将典
× 木下, 将典
|
|||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | 「ポインタ変数がどの変数を指しうるか」という情報は多くのプログラム解析において必須であり，プログラムの最適化や信頼性の向上に役立つ．そのため，これまでに様々なポインタ解析の手法が提案されてきた．解析結果の正確さと解析の実行効率はトレードオフの関係にあり，その１つの指針としてプログラムの文の実行順序を考慮するか否かを意味するフロー依存性がある．フロー非依存ポインタ解析は，文の実行順序を考慮しない解析で，実行効率は良いが，その解析結果はフロー依存のものに比べ正確さの点で劣る．Hasti らは，静的単一代入形式(SSA 形式) を用いたフロー非依存ポインタ解析の手法を提案し，その解析結果が通常のフロー非依存ポインタ解析よりも有用であることを示した(1998)．しかし，「提案手法がフロー依存ポインタ解析と同等な解析能力を持つか否か」については考察しておらず，これを未解決問題として提起した．これに対し，田中は多重度の概念に着目し，あるサブセットにおいて両者が同等の解析能力を持つことを示した2011)．ここで，多重度とはポインタ変数の型における「*」の数である．しかし，いずれの研究においても構造体型のポインタ変数について十分には考察されなかった．したがって，本研究は構造体型のポインタ変数解析手法の提案を目的とする．本研究では，まず構造体型のポインタ変数が存在する場合，Hasti らの手法で正しく解析できないプログラムが存在することを示して，未解決問題を否定的に解決した．次に，制限されたサブセットにおける，SSA 形式を用いた構造体型のポインタ変数解析手法を新たに提案した．本研究では，構造体の参照関係をDAG で表現する．グラフの各頂点は「構造体の型」を，各有向辺は「参照関係」を表す（例えば，S 型の構造体がT 型の構造体をメンバとして持つとき，S からT への有向辺を持つ）．ただし，グラフに強連結成分があれば，それを１つの頂点とみなす．また，本研究では新たに「ポインタ変数の指し先が未確定」を表「⊥」の概念を導入する．この概念を用い，本手法では最初の解析において，他の文の解析結果に依存した解析を必要とする文を，ボトム文とトップ文に変換する．本研究では，この変換手法を用いた新しいポインタ解析の手法を提示し，その解析能力が先行研究よりも向上していることを示した．なお，本手法は上述のDAG を利用することで，一度解析が終わった文を繰り返し解析しない．したがって，プログラム全体を繰り返し解析するHasti らの手法と比べて効率よく解析ができる． | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 三重大学大学院工学研究科博士前期課程情報工学専攻 | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 2, 39 | |||||||
| 書誌情報 |
発行日 2011-01-01 |
|||||||
| フォーマット | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | application/pdf | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
| 出版者 | ||||||||
| 出版者 | 三重大学 | |||||||
| 修士論文指導教員 | ||||||||
| 寄与者識別子Scheme | WEKO | |||||||
| 寄与者識別子 | 22929 | |||||||
| 姓名 | 大山口, 通夫 | |||||||
| 言語 | ja | |||||||
| 資源タイプ（三重大） | ||||||||
| Master's Thesis / 修士論文 | ||||||||
