2009-12-02 [長年日記]
λ. PLDIr #4
PLDIの論文を読む PLDIr の第四回に参加。 今回はPLDI2000の論文が対象で、私は以下の2本の論文を紹介した。
- Symbolic bounds analysis of pointers, array indices, and accessed memory regions (著者版)
- Translation validation for an optimizing compiler (著者版)
前者の論文は手続きがアクセスするポインタ・配列の範囲を解析するアルゴリズムの話で、競合の検出、自動並列化、範囲外アクセスの検出、範囲チェックの省略とかに使える。特徴は不動点計算を使わずに線形計画問題に還元して解くこと。
後者の論文はコンパイラの最適化の前後で意味が変わらないことを検証する話。等価性の定義として simulation relation というのを使っている。最適化器がevidenceとして simulation relation を出力すれば意味が変わらないことは容易に確認できるけど、最適化器が simulation relation を出力してくれなくても、多くの場合には simulation relation を推論できるとか。
発表資料 (PDF):
“Symbolic bounds analysis of pointers, array indices, and accessed memory regions”他の紹介＠PLDIr#4 from Masahiro Sakai
関連リンク
[ツッコミを入れる]
