チャイティンのアルゴリズムは、コスト/次数をスピル指標とするボトムアップ型のグラフ彩色 レジスタ割り当て アルゴリズムです。このアルゴリズムは、設計者であるグレゴリー・チャイティンにちなんで名付けられました。チャイティンのアルゴリズムは、レジスタ割り当てとスピルの両方において干渉グラフの彩色を利用した 最初のレジスタ割り当てアルゴリズムでした。
チャイティンのアルゴリズムは、1982年のSIGPLANコンパイラ構築シンポジウムで発表され、シンポジウムの議事録に掲載されました。これは、レジスタ割り当てにおけるグラフカラーリングの利用に関する1981年の論文を拡張したものです。チャイティンのアルゴリズムは、レジスタアロケータに関する研究の大部分の基礎となりました。
参考文献
