帰納変数
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