チャイティンのアルゴリズム

チャイティンのアルゴリズムは、コスト/次数をスピルメトリックとして使用するボトムアップのグラフカラーリングレジスタ 割り当て アルゴリズムです。このアルゴリズムは、設計者であるグレゴリー・チャイティンにちなんで名付けられました。チャイティンのアルゴリズムは、レジスタ割り当てとスピルの両方に干渉グラフの色付けを利用した 最初のレジスタ割り当てアルゴリズムでした。

チャイティンのアルゴリズムは、1982 年のSIGPLANコンパイラ構築シンポジウムで発表され、シンポジウムの議事録に掲載されました。これは、レジスタ割り当てにグラフ カラーリングを使用するという 1981 年の以前の論文の拡張でした。チャイティンのアルゴリズムは、レジスタ アロケータに関する研究の大部分の基礎となりました。

• Gregory Chaitin (2004 年 4 月)。 「グラフ カラーリングによるレジスタ割り当てとスピル」。ACM SIGPLAN Notices。39 ( 4): 66–74。doi :10.1145 / 989393.989403。S2CID  23108905。