帰納変数

GCCやLLVMは帰納変数を解析する際に、伝統的なモデルである{iv, stride, init}のような表現はつかわず、
Chains of Recurrencesという帰納変数や漸化式をモデル化した表現を使用する。

LLVMでは変数の依存解析を行い、Chains of Recurrencesでモデル化し、正規化、さらには正規化した表現からLLVM IRへ逆変換する機能を、
ScalarEvolutionという解析パスで実装している。

ScalarEvolutionAndLoopOptimization

p22に、sum()のケースをCRで表現すると、{0,+, {0,+,1}<L> }<L> になるというサンプルがある。
ScalarEvolutionが参考にしている論文や資料は、ScalarEvolutionのソースコードの冒頭に掲載されている。

Chains of Recurrences

Chains of Recurrences (CR) algebra applied to SSA forms


  • 最終更新:2013-06-24 22:04:04

このWIKIを編集するにはパスワード入力が必要です

認証パスワード