【LLVM】レジスタ割り当てロジックを変更してみる

Last updated at 2024-03-05Posted at 2024-03-03

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz です。
本稿は、下記リンクにあるコンパイラの最適化について述べられているMicrosoftさんの記事をきっかけにして、LLVMでレジスタ割り当てのロジックを変更する手法を取り上げたいと思います。

著者の手元のPCは、このMicrosoftさんの記事とは異なる環境（M1チップのmacOS）です。ただし、LLVMの手順は動作しますので、本稿では「レジスタ割り当てのロジックが変更できる」ことを主題にして、実際に試してみるところまでを書きたいと思います。

レジスタ割り当て問題

レジスタ割り当て問題は、1981年にグレゴリー・チャイティンらによりNP完全であることが示されている¹問題です。無制限の数の仮想レジスタ（LLVM IR など）を持つプログラムを、特定のアーキテクチャの制限された（おそらく少数の）数の物理レジスタを使うプログラムにマッピングする問題です。

コンピュータがプログラムを実行していくには、様々なデータ（数値）を加工（計算）して処理が進みます。CPUの構造上、この数値を計算するには『レジスタ』と呼ばれる限られた個数しかないメモリでのみ実施できるになっています。そこで計算するべき数値は、必ずレジスタに置かれる必要がありますが、このレジスタの個数が僅か数十個であるため、プログラムは計算処理されない時間には、レジスタよりも多く数値を保持できるメモリを使います。レジスタを含む記憶領域には、そのアクセス性能（値を読み書きするスピード）に次のような特徴があります。

記憶領域	アクセス速度
レジスタ	1プロセッササイクル未満
キャッシュメモリ	数サイクル～数十サイクル
DRAMメモリ	キャッシュより遅い
ハードドライブ	非常に遅く、数百万サイクル

詳しい比較は@zacky1972さんの『各種メモリ／ストレージのアクセス時間，所要クロックサイクル，転送速度，容量の目安』に分かり易くまとめられてありました。参考にしてみてください。

このように数値を保持するためのメモリには、アクセスする時間に大きな差があり、プログラムを効率的に動作させようとすると、処理しようとする数値（変数）がその関係する全ての計算命令が実行されるまで、レジスタに割り当たったままの状態が理想です。この割り当て状態を維持できないと、変数がキャッシュ等などより遅いメモリに吐き出され、読み込み／書き込みが頻繁に行われ、プログラムの処理速度が遅くなることになります。
コンパイラは、プログラムを効率的に動作させるために、レジスタに割り当たった状態を維持するように最適化することが必要となります。しかしながら、この問題はNP完全問題であるため上手く最適化できるとは限りません。むしろ最適化できないというべきなのかもしれません。

LLVMのコンパイルでは、このレジスタ割り当ての最適化アルゴリズムを変更できるように工夫されています。素晴らしいアルゴリズムを別途開発することも可能ですが、デフォルトで幾つかのアルゴリズムが実装されております。
以下にそれらの紹介と実際動作するところを確認していきましょう。

本稿の環境

なお、本稿のために使用した環境は以下となります。

macOS: Sonoma 14.2.1 (chip: Apple M1)
Homebrew 4.2.9
LLVM: Homebrew LLVM version 17.0.6（homebrewにてインストール）

ここで、本稿で試している環境のCPUアーキテクチャを見ておきます。以下のサイトにレジスタの図が分かりやすく出ています。Aarch64には31個の汎用レジスタがあります。

レジスタ割り当てロジックを変える

LLVMでは Basic、Fast、Greedy、PBQP の4つのアロケータが実装されており、それぞれの特徴は以下の通りです。

Basic: レジスタアロケータとしての基本的な実装
Fast: 基本ブロック単位でレジスタを割り当てる手法
Greedy: 貪欲法を使った最適化アルゴリズム
PBQP: Partitioned Boolean Quadratic Programming に基づく手法

LLVMのIRを生成する

比較的多くの変数を使うような単純なサンプルプログラムを準備します。

サンプルプログラム（test.c）

test.c

int main(int argc, char **argv){
  int x00 = 0;
  int x01 = 1;
  int x02 = 2;
  int x03 = 3;
  int x04 = 4;
  int x05 = 5;
  int x06 = 6;
  int x07 = 7;
  int x08 = 8;
  int x09 = 9;
  int x10 = 10;
  int x11 = 11;
  int x12 = 12;
  int x13 = 13;
  int x14 = 14;
  int x15 = 15;
  int x16 = 16;
  int x17 = 17;
  int x18 = 18;
  int x19 = 19;
  int x20 = 20;
  int x21 = 21;
  int x22 = 22;
  int x23 = 23;
  int x24 = 24;
  int x25 = 25;
  int x26 = 26;
  int x27 = 27;
  int x28 = 28;
  int x29 = 29;
  x00 = x00 + x01;
  x00 = x00 + x02;
  x00 = x00 + x03;
  x00 = x00 + x04;
  x00 = x00 + x05;
  x00 = x00 + x06;
  x00 = x00 + x07;
  x00 = x00 + x08;
  x00 = x00 + x09;
  x11 = x11 + x09;
  x12 = x12 + x08;
  x13 = x13 + x07;
  x14 = x14 + x06;
  x15 = x15 + x04;
  x16 = x16 + x04;
  x17 = x17 + x03;
  x18 = x18 + x02;
  x19 = x19 + x01;
  x10 = x10 + x19;
  x10 = x10 + x18;
  x10 = x10 + x17;
  x10 = x10 + x16;
  x10 = x10 + x15;
  x10 = x10 + x14;
  x10 = x10 + x13;
  x10 = x10 + x12;
  x10 = x10 + x11;
  x20 = x20 + x10;
  x20 = x20 + x00;
  return 0;
}

仮想マシン上で動作する中間言語(LLVM-IR)を生成します。

$ clang -S -emit-llvm test.c

ファイルtest.llが出力されます。

LLVM IR（test.ll）

test.ll

; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
target triple = "arm64-apple-macosx14.0.0"

; Function Attrs: noinline nounwind optnone ssp uwtable(sync)
define i32 @main(i32 noundef %0, ptr noundef %1) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca ptr, align 8
  %6 = alloca i32, align 4
  %7 = alloca i32, align 4
  %8 = alloca i32, align 4
  %9 = alloca i32, align 4
  %10 = alloca i32, align 4
  %11 = alloca i32, align 4
  %12 = alloca i32, align 4
  %13 = alloca i32, align 4
  %14 = alloca i32, align 4
  %15 = alloca i32, align 4
  %16 = alloca i32, align 4
  %17 = alloca i32, align 4
  %18 = alloca i32, align 4
  %19 = alloca i32, align 4
  %20 = alloca i32, align 4
  %21 = alloca i32, align 4
  %22 = alloca i32, align 4
  %23 = alloca i32, align 4
  %24 = alloca i32, align 4
  %25 = alloca i32, align 4
  %26 = alloca i32, align 4
  %27 = alloca i32, align 4
  %28 = alloca i32, align 4
  %29 = alloca i32, align 4
  %30 = alloca i32, align 4
  %31 = alloca i32, align 4
  %32 = alloca i32, align 4
  %33 = alloca i32, align 4
  %34 = alloca i32, align 4
  %35 = alloca i32, align 4
  store i32 0, ptr %3, align 4
  store i32 %0, ptr %4, align 4
  store ptr %1, ptr %5, align 8
  store i32 0, ptr %6, align 4
  store i32 1, ptr %7, align 4
  store i32 2, ptr %8, align 4
  store i32 3, ptr %9, align 4
  store i32 4, ptr %10, align 4
  store i32 5, ptr %11, align 4
  store i32 6, ptr %12, align 4
  store i32 7, ptr %13, align 4
  store i32 8, ptr %14, align 4
  store i32 9, ptr %15, align 4
  store i32 10, ptr %16, align 4
  store i32 11, ptr %17, align 4
  store i32 12, ptr %18, align 4
  store i32 13, ptr %19, align 4
  store i32 14, ptr %20, align 4
  store i32 15, ptr %21, align 4
  store i32 16, ptr %22, align 4
  store i32 17, ptr %23, align 4
  store i32 18, ptr %24, align 4
  store i32 19, ptr %25, align 4
  store i32 20, ptr %26, align 4
  store i32 21, ptr %27, align 4
  store i32 22, ptr %28, align 4
  store i32 23, ptr %29, align 4
  store i32 24, ptr %30, align 4
  store i32 25, ptr %31, align 4
  store i32 26, ptr %32, align 4
  store i32 27, ptr %33, align 4
  store i32 28, ptr %34, align 4
  store i32 29, ptr %35, align 4
  %36 = load i32, ptr %6, align 4
  %37 = load i32, ptr %7, align 4
  %38 = add nsw i32 %36, %37
  store i32 %38, ptr %6, align 4
  %39 = load i32, ptr %6, align 4
  %40 = load i32, ptr %8, align 4
  %41 = add nsw i32 %39, %40
  store i32 %41, ptr %6, align 4
  %42 = load i32, ptr %6, align 4
  %43 = load i32, ptr %9, align 4
  %44 = add nsw i32 %42, %43
  store i32 %44, ptr %6, align 4
  %45 = load i32, ptr %6, align 4
  %46 = load i32, ptr %10, align 4
  %47 = add nsw i32 %45, %46
  store i32 %47, ptr %6, align 4
  %48 = load i32, ptr %6, align 4
  %49 = load i32, ptr %11, align 4
  %50 = add nsw i32 %48, %49
  store i32 %50, ptr %6, align 4
  %51 = load i32, ptr %6, align 4
  %52 = load i32, ptr %12, align 4
  %53 = add nsw i32 %51, %52
  store i32 %53, ptr %6, align 4
  %54 = load i32, ptr %6, align 4
  %55 = load i32, ptr %13, align 4
  %56 = add nsw i32 %54, %55
  store i32 %56, ptr %6, align 4
  %57 = load i32, ptr %6, align 4
  %58 = load i32, ptr %14, align 4
  %59 = add nsw i32 %57, %58
  store i32 %59, ptr %6, align 4
  %60 = load i32, ptr %6, align 4
  %61 = load i32, ptr %15, align 4
  %62 = add nsw i32 %60, %61
  store i32 %62, ptr %6, align 4
  %63 = load i32, ptr %17, align 4
  %64 = load i32, ptr %15, align 4
  %65 = add nsw i32 %63, %64
  store i32 %65, ptr %17, align 4
  %66 = load i32, ptr %18, align 4
  %67 = load i32, ptr %14, align 4
  %68 = add nsw i32 %66, %67
  store i32 %68, ptr %18, align 4
  %69 = load i32, ptr %19, align 4
  %70 = load i32, ptr %13, align 4
  %71 = add nsw i32 %69, %70
  store i32 %71, ptr %19, align 4
  %72 = load i32, ptr %20, align 4
  %73 = load i32, ptr %12, align 4
  %74 = add nsw i32 %72, %73
  store i32 %74, ptr %20, align 4
  %75 = load i32, ptr %21, align 4
  %76 = load i32, ptr %10, align 4
  %77 = add nsw i32 %75, %76
  store i32 %77, ptr %21, align 4
  %78 = load i32, ptr %22, align 4
  %79 = load i32, ptr %10, align 4
  %80 = add nsw i32 %78, %79
  store i32 %80, ptr %22, align 4
  %81 = load i32, ptr %23, align 4
  %82 = load i32, ptr %9, align 4
  %83 = add nsw i32 %81, %82
  store i32 %83, ptr %23, align 4
  %84 = load i32, ptr %24, align 4
  %85 = load i32, ptr %8, align 4
  %86 = add nsw i32 %84, %85
  store i32 %86, ptr %24, align 4
  %87 = load i32, ptr %25, align 4
  %88 = load i32, ptr %7, align 4
  %89 = add nsw i32 %87, %88
  store i32 %89, ptr %25, align 4
  %90 = load i32, ptr %16, align 4
  %91 = load i32, ptr %25, align 4
  %92 = add nsw i32 %90, %91
  store i32 %92, ptr %16, align 4
  %93 = load i32, ptr %16, align 4
  %94 = load i32, ptr %24, align 4
  %95 = add nsw i32 %93, %94
  store i32 %95, ptr %16, align 4
  %96 = load i32, ptr %16, align 4
  %97 = load i32, ptr %23, align 4
  %98 = add nsw i32 %96, %97
  store i32 %98, ptr %16, align 4
  %99 = load i32, ptr %16, align 4
  %100 = load i32, ptr %22, align 4
  %101 = add nsw i32 %99, %100
  store i32 %101, ptr %16, align 4
  %102 = load i32, ptr %16, align 4
  %103 = load i32, ptr %21, align 4
  %104 = add nsw i32 %102, %103
  store i32 %104, ptr %16, align 4
  %105 = load i32, ptr %16, align 4
  %106 = load i32, ptr %20, align 4
  %107 = add nsw i32 %105, %106
  store i32 %107, ptr %16, align 4
  %108 = load i32, ptr %16, align 4
  %109 = load i32, ptr %19, align 4
  %110 = add nsw i32 %108, %109
  store i32 %110, ptr %16, align 4
  %111 = load i32, ptr %16, align 4
  %112 = load i32, ptr %18, align 4
  %113 = add nsw i32 %111, %112
  store i32 %113, ptr %16, align 4
  %114 = load i32, ptr %16, align 4
  %115 = load i32, ptr %17, align 4
  %116 = add nsw i32 %114, %115
  store i32 %116, ptr %16, align 4
  %117 = load i32, ptr %26, align 4
  %118 = load i32, ptr %16, align 4
  %119 = add nsw i32 %117, %118
  store i32 %119, ptr %26, align 4
  %120 = load i32, ptr %26, align 4
  %121 = load i32, ptr %6, align 4
  %122 = add nsw i32 %120, %121
  store i32 %122, ptr %26, align 4
  ret i32 0
}

attributes #0 = { noinline nounwind optnone ssp uwtable(sync) "frame-pointer"="non-leaf" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="apple-m1" "target-features"="+aes,+crc,+dotprod,+fp-armv8,+fp16fml,+fullfp16,+lse,+neon,+ras,+rcpc,+rdm,+sha2,+sha3,+v8.1a,+v8.2a,+v8.3a,+v8.4a,+v8.5a,+v8a,+zcm,+zcz" }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"uwtable", i32 1}
!3 = !{i32 7, !"frame-pointer", i32 1}
!4 = !{!"Homebrew clang version 17.0.6"}

長くつまらないコードですが、仮想マシンではレジスタ数に制限がないため、%122という122番めのレジスタまで使われています。コンパイラは次に、これを物理的な実際のCPUに割り当てる処理をします。

次に挙げるllcコマンドでCPUアーキテクチャにあったアセンブリ言語（test.s）に変換されます。

Basic

デフォルトで設定されるレジスタ・アロケータです。

$ llc -regalloc=basic test.ll

test.s

	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 14, 0
	.globl	_main                           ; -- Begin function main
	.p2align	2
_main:                                  ; @main
	.cfi_startproc
; %bb.0:
	sub	sp, sp, #144
	.cfi_def_cfa_offset 144
	str	wzr, [sp, #140]
	str	w0, [sp, #136]
	str	x1, [sp, #128]
	str	wzr, [sp, #124]
	mov	w8, #1                          ; =0x1
	str	w8, [sp, #120]
	mov	w8, #2                          ; =0x2
	str	w8, [sp, #116]
	mov	w8, #3                          ; =0x3
	str	w8, [sp, #112]
	mov	w8, #4                          ; =0x4
	str	w8, [sp, #108]
	mov	w8, #5                          ; =0x5
	str	w8, [sp, #104]
	mov	w8, #6                          ; =0x6
	str	w8, [sp, #100]
	mov	w8, #7                          ; =0x7
	str	w8, [sp, #96]
	mov	w8, #8                          ; =0x8
	str	w8, [sp, #92]
	mov	w8, #9                          ; =0x9
	str	w8, [sp, #88]
	mov	w8, #10                         ; =0xa
	str	w8, [sp, #84]
	mov	w8, #11                         ; =0xb
	str	w8, [sp, #80]
	mov	w8, #12                         ; =0xc
	str	w8, [sp, #76]
	mov	w8, #13                         ; =0xd
	str	w8, [sp, #72]
	mov	w8, #14                         ; =0xe
	str	w8, [sp, #68]
	mov	w8, #15                         ; =0xf
	str	w8, [sp, #64]
	mov	w8, #16                         ; =0x10
	str	w8, [sp, #60]
	mov	w8, #17                         ; =0x11
	str	w8, [sp, #56]
	mov	w8, #18                         ; =0x12
	str	w8, [sp, #52]
	mov	w8, #19                         ; =0x13
	str	w8, [sp, #48]
	mov	w8, #20                         ; =0x14
	str	w8, [sp, #44]
	mov	w8, #21                         ; =0x15
	str	w8, [sp, #40]
	mov	w8, #22                         ; =0x16
	str	w8, [sp, #36]
	mov	w8, #23                         ; =0x17
	str	w8, [sp, #32]
	mov	w8, #24                         ; =0x18
	str	w8, [sp, #28]
	mov	w8, #25                         ; =0x19
	str	w8, [sp, #24]
	mov	w8, #26                         ; =0x1a
	str	w8, [sp, #20]
	mov	w8, #27                         ; =0x1b
	str	w8, [sp, #16]
	mov	w8, #28                         ; =0x1c
	str	w8, [sp, #12]
	mov	w8, #29                         ; =0x1d
	str	w8, [sp, #8]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #120]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #116]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #112]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #108]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #104]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #100]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #96]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #92]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #124]
	ldr	w8, [sp, #88]
	add	w8, w9, w8
	str	w8, [sp, #124]
	ldr	w9, [sp, #80]
	ldr	w8, [sp, #88]
	add	w8, w9, w8
	str	w8, [sp, #80]
	ldr	w9, [sp, #76]
	ldr	w8, [sp, #92]
	add	w8, w9, w8
	str	w8, [sp, #76]
	ldr	w9, [sp, #72]
	ldr	w8, [sp, #96]
	add	w8, w9, w8
	str	w8, [sp, #72]
	ldr	w9, [sp, #68]
	ldr	w8, [sp, #100]
	add	w8, w9, w8
	str	w8, [sp, #68]
	ldr	w9, [sp, #64]
	ldr	w8, [sp, #108]
	add	w8, w9, w8
	str	w8, [sp, #64]
	ldr	w9, [sp, #60]
	ldr	w8, [sp, #108]
	add	w8, w9, w8
	str	w8, [sp, #60]
	ldr	w9, [sp, #56]
	ldr	w8, [sp, #112]
	add	w8, w9, w8
	str	w8, [sp, #56]
	ldr	w9, [sp, #52]
	ldr	w8, [sp, #116]
	add	w8, w9, w8
	str	w8, [sp, #52]
	ldr	w9, [sp, #48]
	ldr	w8, [sp, #120]
	add	w8, w9, w8
	str	w8, [sp, #48]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #48]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #52]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #56]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #60]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #64]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #68]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #72]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #76]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #84]
	ldr	w8, [sp, #80]
	add	w8, w9, w8
	str	w8, [sp, #84]
	ldr	w9, [sp, #44]
	ldr	w8, [sp, #84]
	add	w8, w9, w8
	str	w8, [sp, #44]
	ldr	w9, [sp, #44]
	ldr	w8, [sp, #124]
	add	w8, w9, w8
	str	w8, [sp, #44]
	mov	w0, #0                          ; =0x0
	add	sp, sp, #144
	ret
	.cfi_endproc
                                        ; -- End function
.subsections_via_symbols

Fast

Basicよりも高速になるレジスタ・アロケータです。

$ llc -regalloc=fast test.ll

test.s

	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 14, 0
	.globl	_main                           ; -- Begin function main
	.p2align	2
_main:                                  ; @main
	.cfi_startproc
; %bb.0:
	sub	sp, sp, #144
	.cfi_def_cfa_offset 144
	str	wzr, [sp, #140]
	str	w0, [sp, #136]
	str	x1, [sp, #128]
	str	wzr, [sp, #124]
	mov	w8, #1                          ; =0x1
	str	w8, [sp, #120]
	mov	w8, #2                          ; =0x2
	str	w8, [sp, #116]
	mov	w8, #3                          ; =0x3
	str	w8, [sp, #112]
	mov	w8, #4                          ; =0x4
	str	w8, [sp, #108]
	mov	w8, #5                          ; =0x5
	str	w8, [sp, #104]
	mov	w8, #6                          ; =0x6
	str	w8, [sp, #100]
	mov	w8, #7                          ; =0x7
	str	w8, [sp, #96]
	mov	w8, #8                          ; =0x8
	str	w8, [sp, #92]
	mov	w8, #9                          ; =0x9
	str	w8, [sp, #88]
	mov	w8, #10                         ; =0xa
	str	w8, [sp, #84]
	mov	w8, #11                         ; =0xb
	str	w8, [sp, #80]
	mov	w8, #12                         ; =0xc
	str	w8, [sp, #76]
	mov	w8, #13                         ; =0xd
	str	w8, [sp, #72]
	mov	w8, #14                         ; =0xe
	str	w8, [sp, #68]
	mov	w8, #15                         ; =0xf
	str	w8, [sp, #64]
	mov	w8, #16                         ; =0x10
	str	w8, [sp, #60]
	mov	w8, #17                         ; =0x11
	str	w8, [sp, #56]
	mov	w8, #18                         ; =0x12
	str	w8, [sp, #52]
	mov	w8, #19                         ; =0x13
	str	w8, [sp, #48]
	mov	w8, #20                         ; =0x14
	str	w8, [sp, #44]
	mov	w8, #21                         ; =0x15
	str	w8, [sp, #40]
	mov	w8, #22                         ; =0x16
	str	w8, [sp, #36]
	mov	w8, #23                         ; =0x17
	str	w8, [sp, #32]
	mov	w8, #24                         ; =0x18
	str	w8, [sp, #28]
	mov	w8, #25                         ; =0x19
	str	w8, [sp, #24]
	mov	w8, #26                         ; =0x1a
	str	w8, [sp, #20]
	mov	w8, #27                         ; =0x1b
	str	w8, [sp, #16]
	mov	w8, #28                         ; =0x1c
	str	w8, [sp, #12]
	mov	w8, #29                         ; =0x1d
	str	w8, [sp, #8]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #120]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #116]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #112]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #104]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #100]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #96]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #92]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #88]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #80]
	ldr	w9, [sp, #88]
	add	w8, w8, w9
	str	w8, [sp, #80]
	ldr	w8, [sp, #76]
	ldr	w9, [sp, #92]
	add	w8, w8, w9
	str	w8, [sp, #76]
	ldr	w8, [sp, #72]
	ldr	w9, [sp, #96]
	add	w8, w8, w9
	str	w8, [sp, #72]
	ldr	w8, [sp, #68]
	ldr	w9, [sp, #100]
	add	w8, w8, w9
	str	w8, [sp, #68]
	ldr	w8, [sp, #64]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #64]
	ldr	w8, [sp, #60]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #60]
	ldr	w8, [sp, #56]
	ldr	w9, [sp, #112]
	add	w8, w8, w9
	str	w8, [sp, #56]
	ldr	w8, [sp, #52]
	ldr	w9, [sp, #116]
	add	w8, w8, w9
	str	w8, [sp, #52]
	ldr	w8, [sp, #48]
	ldr	w9, [sp, #120]
	add	w8, w8, w9
	str	w8, [sp, #48]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #48]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #52]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #56]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #60]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #64]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #68]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #72]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #76]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #80]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #44]
	ldr	w9, [sp, #84]
	add	w8, w8, w9
	str	w8, [sp, #44]
	ldr	w8, [sp, #44]
	ldr	w9, [sp, #124]
	add	w8, w8, w9
	str	w8, [sp, #44]
	mov	w0, #0                          ; =0x0
	add	sp, sp, #144
	ret
	.cfi_endproc
                                        ; -- End function
.subsections_via_symbols

グリーディ法

最適化問題を解くための技法の一つで「貪欲法」とも呼ばれるアルゴリズムです。

$ llc -regalloc=greedy test.ll

test.s

	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 14, 0
	.globl	_main                           ; -- Begin function main
	.p2align	2
_main:                                  ; @main
	.cfi_startproc
; %bb.0:
	sub	sp, sp, #144
	.cfi_def_cfa_offset 144
	str	wzr, [sp, #140]
	str	w0, [sp, #136]
	str	x1, [sp, #128]
	str	wzr, [sp, #124]
	mov	w8, #1                          ; =0x1
	str	w8, [sp, #120]
	mov	w8, #2                          ; =0x2
	str	w8, [sp, #116]
	mov	w8, #3                          ; =0x3
	str	w8, [sp, #112]
	mov	w8, #4                          ; =0x4
	str	w8, [sp, #108]
	mov	w8, #5                          ; =0x5
	str	w8, [sp, #104]
	mov	w8, #6                          ; =0x6
	str	w8, [sp, #100]
	mov	w8, #7                          ; =0x7
	str	w8, [sp, #96]
	mov	w8, #8                          ; =0x8
	str	w8, [sp, #92]
	mov	w8, #9                          ; =0x9
	str	w8, [sp, #88]
	mov	w8, #10                         ; =0xa
	str	w8, [sp, #84]
	mov	w8, #11                         ; =0xb
	str	w8, [sp, #80]
	mov	w8, #12                         ; =0xc
	str	w8, [sp, #76]
	mov	w8, #13                         ; =0xd
	str	w8, [sp, #72]
	mov	w8, #14                         ; =0xe
	str	w8, [sp, #68]
	mov	w8, #15                         ; =0xf
	str	w8, [sp, #64]
	mov	w8, #16                         ; =0x10
	str	w8, [sp, #60]
	mov	w8, #17                         ; =0x11
	str	w8, [sp, #56]
	mov	w8, #18                         ; =0x12
	str	w8, [sp, #52]
	mov	w8, #19                         ; =0x13
	str	w8, [sp, #48]
	mov	w8, #20                         ; =0x14
	str	w8, [sp, #44]
	mov	w8, #21                         ; =0x15
	str	w8, [sp, #40]
	mov	w8, #22                         ; =0x16
	str	w8, [sp, #36]
	mov	w8, #23                         ; =0x17
	str	w8, [sp, #32]
	mov	w8, #24                         ; =0x18
	str	w8, [sp, #28]
	mov	w8, #25                         ; =0x19
	str	w8, [sp, #24]
	mov	w8, #26                         ; =0x1a
	str	w8, [sp, #20]
	mov	w8, #27                         ; =0x1b
	str	w8, [sp, #16]
	mov	w8, #28                         ; =0x1c
	str	w8, [sp, #12]
	mov	w8, #29                         ; =0x1d
	str	w8, [sp, #8]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #120]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #116]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #112]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #104]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #100]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #96]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #92]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #88]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #80]
	ldr	w9, [sp, #88]
	add	w8, w8, w9
	str	w8, [sp, #80]
	ldr	w8, [sp, #76]
	ldr	w9, [sp, #92]
	add	w8, w8, w9
	str	w8, [sp, #76]
	ldr	w8, [sp, #72]
	ldr	w9, [sp, #96]
	add	w8, w8, w9
	str	w8, [sp, #72]
	ldr	w8, [sp, #68]
	ldr	w9, [sp, #100]
	add	w8, w8, w9
	str	w8, [sp, #68]
	ldr	w8, [sp, #64]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #64]
	ldr	w8, [sp, #60]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #60]
	ldr	w8, [sp, #56]
	ldr	w9, [sp, #112]
	add	w8, w8, w9
	str	w8, [sp, #56]
	ldr	w8, [sp, #52]
	ldr	w9, [sp, #116]
	add	w8, w8, w9
	str	w8, [sp, #52]
	ldr	w8, [sp, #48]
	ldr	w9, [sp, #120]
	add	w8, w8, w9
	str	w8, [sp, #48]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #48]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #52]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #56]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #60]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #64]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #68]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #72]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #76]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #80]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #44]
	ldr	w9, [sp, #84]
	add	w8, w8, w9
	str	w8, [sp, #44]
	ldr	w8, [sp, #44]
	ldr	w9, [sp, #124]
	add	w8, w8, w9
	str	w8, [sp, #44]
	mov	w0, #0                          ; =0x0
	add	sp, sp, #144
	ret
	.cfi_endproc
                                        ; -- End function
.subsections_via_symbols

PBQP（Partitioned Boolean Quadratic Programming）

分割0-1整数2次計画問題に関する数理最適化アルゴリズムの１つです。

$ llc -regalloc=pbqp test.ll

test.s

	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 14, 0
	.globl	_main                           ; -- Begin function main
	.p2align	2
_main:                                  ; @main
	.cfi_startproc
; %bb.0:
	sub	sp, sp, #144
	.cfi_def_cfa_offset 144
	mov	x8, x1
	mov	x9, x0
	str	wzr, [sp, #140]
	str	w9, [sp, #136]
	str	x8, [sp, #128]
	str	wzr, [sp, #124]
	mov	w8, #1                          ; =0x1
	str	w8, [sp, #120]
	mov	w8, #2                          ; =0x2
	str	w8, [sp, #116]
	mov	w8, #3                          ; =0x3
	str	w8, [sp, #112]
	mov	w8, #4                          ; =0x4
	str	w8, [sp, #108]
	mov	w8, #5                          ; =0x5
	str	w8, [sp, #104]
	mov	w8, #6                          ; =0x6
	str	w8, [sp, #100]
	mov	w8, #7                          ; =0x7
	str	w8, [sp, #96]
	mov	w8, #8                          ; =0x8
	str	w8, [sp, #92]
	mov	w8, #9                          ; =0x9
	str	w8, [sp, #88]
	mov	w8, #10                         ; =0xa
	str	w8, [sp, #84]
	mov	w8, #11                         ; =0xb
	str	w8, [sp, #80]
	mov	w8, #12                         ; =0xc
	str	w8, [sp, #76]
	mov	w8, #13                         ; =0xd
	str	w8, [sp, #72]
	mov	w8, #14                         ; =0xe
	str	w8, [sp, #68]
	mov	w8, #15                         ; =0xf
	str	w8, [sp, #64]
	mov	w8, #16                         ; =0x10
	str	w8, [sp, #60]
	mov	w8, #17                         ; =0x11
	str	w8, [sp, #56]
	mov	w8, #18                         ; =0x12
	str	w8, [sp, #52]
	mov	w8, #19                         ; =0x13
	str	w8, [sp, #48]
	mov	w8, #20                         ; =0x14
	str	w8, [sp, #44]
	mov	w8, #21                         ; =0x15
	str	w8, [sp, #40]
	mov	w8, #22                         ; =0x16
	str	w8, [sp, #36]
	mov	w8, #23                         ; =0x17
	str	w8, [sp, #32]
	mov	w8, #24                         ; =0x18
	str	w8, [sp, #28]
	mov	w8, #25                         ; =0x19
	str	w8, [sp, #24]
	mov	w8, #26                         ; =0x1a
	str	w8, [sp, #20]
	mov	w8, #27                         ; =0x1b
	str	w8, [sp, #16]
	mov	w8, #28                         ; =0x1c
	str	w8, [sp, #12]
	mov	w8, #29                         ; =0x1d
	str	w8, [sp, #8]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #120]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #116]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #112]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #104]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #100]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #96]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #92]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #124]
	ldr	w9, [sp, #88]
	add	w8, w8, w9
	str	w8, [sp, #124]
	ldr	w8, [sp, #80]
	ldr	w9, [sp, #88]
	add	w8, w8, w9
	str	w8, [sp, #80]
	ldr	w8, [sp, #76]
	ldr	w9, [sp, #92]
	add	w8, w8, w9
	str	w8, [sp, #76]
	ldr	w8, [sp, #72]
	ldr	w9, [sp, #96]
	add	w8, w8, w9
	str	w8, [sp, #72]
	ldr	w8, [sp, #68]
	ldr	w9, [sp, #100]
	add	w8, w8, w9
	str	w8, [sp, #68]
	ldr	w8, [sp, #64]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #64]
	ldr	w8, [sp, #60]
	ldr	w9, [sp, #108]
	add	w8, w8, w9
	str	w8, [sp, #60]
	ldr	w8, [sp, #56]
	ldr	w9, [sp, #112]
	add	w8, w8, w9
	str	w8, [sp, #56]
	ldr	w8, [sp, #52]
	ldr	w9, [sp, #116]
	add	w8, w8, w9
	str	w8, [sp, #52]
	ldr	w8, [sp, #48]
	ldr	w9, [sp, #120]
	add	w8, w8, w9
	str	w8, [sp, #48]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #48]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #52]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #56]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #60]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #64]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #68]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #72]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #76]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #84]
	ldr	w9, [sp, #80]
	add	w8, w8, w9
	str	w8, [sp, #84]
	ldr	w8, [sp, #44]
	ldr	w9, [sp, #84]
	add	w8, w8, w9
	str	w8, [sp, #44]
	ldr	w8, [sp, #44]
	ldr	w9, [sp, #124]
	add	w8, w8, w9
	str	w8, [sp, #44]
	mov	w0, #0                          ; =0x0
	add	sp, sp, #144
	ret
	.cfi_endproc
                                        ; -- End function
.subsections_via_symbols

おわりに

それぞれの結果を確認して頂くと分かりますが、今回のサンプルではレジスタを効率的に使っているような結果は得られませんでした。これがCPUのアーキテクチャがARMであるAArch64だからなのかがはっきりしておりませんが、コンパイラのレジスタ割り当てはCPUアーキテクチャに依存するレイアであることは確かです。この辺りはLLVMの内部処理をより詳しく調べなければなりません。著者にはそこまでの力がなく、本稿は「ロジックの切り替えの手段の紹介」に留めさせて頂きます。
最後に、本稿を記載するにあたって参考にした文献（サイト）を脚注²に列挙しておきます。
（●）（●） Happy Hacking!
/""　＿＿""＼

Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; Markstein, Peter W. (1981). "Register allocation via coloring". Computer Languages. 6 (1): 47–57. doi:10.1016/0096-0551(81)90048-5 ↩
本稿のために、参考にしたサイトは以下です。
　https://cs420.epfl.ch/archive/20/c/08_reg-alloc.html
　https://www.lighterra.com/papers/graphcoloring/
　https://github.com/nael8r/How-To-Write-An-LLVM-Register-Allocator/blob/master/HowToWriteAnLLVMRegisterAllocator.rst
　https://www.complang.tuwien.ac.at/scholz/pbqp.html
　https://www.youtube.com/@pronesto/videos
　https://db.in.tum.de/teaching/ws2324/codegen/lec08.pdf
　https://en.wikipedia.org/wiki/Register_allocation
　https://www.slideshare.net/chimerawang/llvm-register-allocation-2nd-version ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up