Fight the Future

Java言語とJVM、そしてJavaエコシステム全般にまつわること

GraalでのTrace Register Allocation

Graalのレジスタ割り付けアルゴリズムはlinear scan allocationでした。

jyukutyo.hatenablog.com

ただ、org.graalvm.compiler.lir.phases.AllocationStageクラスを見ていると、こういうコードでした。

public class AllocationStage extends LIRPhaseSuite<AllocationContext> {

    public AllocationStage(OptionValues options) {
        appendPhase(new MarkBasePointersPhase());
        if (TraceRA.getValue(options)) {
            appendPhase(new TraceBuilderPhase());
            appendPhase(new GlobalLivenessAnalysisPhase());
            appendPhase(new TraceRegisterAllocationPhase());
        } else {
            appendPhase(new LinearScanPhase());
        }
...

オプションをONにすると、"Enable experimental Trace Register Allocation"となるようです。linear scanに代わり、実験的にTrace Register Allocationというアルゴリズムが搭載されています。

Trace Register Allocationの論文のプレプリントがあります。

http://ssw.jku.at/General/Staff/Eisl/papers/SPLASH15-ds-trace-ra-preprint.pdf

The basic idea is to offload costly operations such as spilling and splitting to less frequently executed branches and to focus on efficient registers allocation for the hot parts of a program. This is done by performing register allocation on traces instead of on the program as a whole.

基本的なアイデアとしては、それほど実行されない分岐のあふれや分割といったコストの掛かる操作を外し、プログラムのホットな部分に対して効果的なレジスタ割り付けに焦点を当てる。これはプログラム全体ではなくトレース上でレジスタ割り付けを行うことで実現する。

f:id:jyukutyo:20171201143649p:plain

プレプリントを全部読みました。Trace Register Allocationはlinear scanアルゴリズムと両立します。トレースはさまざまな分岐があるコードでの1つのルート、パターンを表します。JVMからのプロファイル結果を用いて、まずもっとも"ホット"なルートにあるブロックをトレースの中にセットします。それから次、その次とトレースを作っていきます。

その後、もっとも"ホット"なトレースからレジスタを割り当てていきますが、Trace Register Allocationにはレジスタ割り当てのアルゴリズムはありません。各トレースへのレジスタ割り当てのアルゴリズムは実装者が選ぶことができます。そのため、linear scanにすることもできますし、他のアルゴリズムにすることもできます。もちろん画一的にすることもなく、ホットなものはAアルゴリズム、あまり実行されないトレースに対しては別のBアルゴリズムを適用するといったことも実装できます。

こういう仕組みですので、Trace Register Allocationはすべてのトレースに対して効果的な割り当てはできません。ホットなトレースを優先するためこちらはより効果的になり、そうでないものは遅くなりそうです。