RustのLLVMに関する問題

概要

この記事はRust Advent Calendar 2019の12日目の記事として書かれました。

qiita.com

遅刻してしまった...すいません(最悪)。

言わずもがなRustはLLVMをバックエンドに持つ言語です。 なのでバグがLLVMの最適化のせいだったりします。有名な例はnoaliasとか無限ループとかです。この辺りは定期的(2ヶ月一回くらい?)にTwitterとかで話題になりますね。またRustでの強い制約がLLVMにおける意味とのギャップで弱く表現せざるを得なかったりもします。そんな感じのこと少しだけ掘り下げて、RustのIssueとかLLVMのPhabricatorから幾つかまとめてみます。怪しいこと言ってたら教えて下さい。

dereferenceable_globally

LLVMにおいて現在のdereferenceable(n)というAttributeは壊れているという話があります。dereferenceable(n)は付けられたポインタが、指すアドレスから少なくともnバイトallocateされていると保証するものです。C++における参照だと思ってくれて大丈夫です。その定義を直そうとするパッチ上での会話が面白かったので紹介します。

⚙ D61652 [Attr] Introduce dereferenceable_globally

そもそものdereferenceableが壊れているというのはそのderef可能という性質がどの範囲で保証されているのか曖昧であるという問題が背景にあります。

struct A {int i, j; double k;};
int f(A& a){ ... }
int g(A* a){ ... }

c++で上のような関数があったとき, 以下のようなIRが出力されます。

%struct.A = type { i32, i32, double }

define i32 @_Z1fR1A(%struct.A* dereferenceable(16) %a)  {..}
define i32 @_Z1gP1A(%struct.A*  %a)  {}

マングルされているので分かりづらいですが上がfで下がgです。dereferenceable(16)があるのが分かると思います。当然16はstructのサイズです。さて次に

struct A {int i, j; double k;}
int f(A& a){
   delete &a;
   return a.i;
}

は

define i32 @_Z1fR1A(%struct.A* dereferenceable(16) %a) {
  %a-p = bitcast %struct.A* %a to i8*
  tail call void @_ZdlPv(i8* nonnull %a-p) ; delete関数
  %a-i = load i32, i32* %a, align 8
  ret i32 %a-i
}

のようにコンパイルされます。これは所謂use after freeですので実行時に落ちます。

このコードは平然とclangはコンパイルするので、dereferenceableというのはclang的にはそのプログラムポイントでderefすることが可能であることを指していることが分かります。

一方LLVMの最適化パスにおいてはdereferenceable(n)という性質が関数のスコープ内の任意のプログラムポイントで成立することを仮定しているかのように最適化を現状しています。ここでバグを生み出します。

43387 – Dereferenceable attribute incorrectly applied to reference that may be deleted; leads to use-after-free following LICM hoist からとってきた例を示すと

int *obj;
void foo(int& c, int * __restrict a, int * __restrict b) {
    delete obj;
    for (int i = 0; i < 3; ++i) {
        if (a[i] > 999) {
            a[i] = c * b[i];
        }
    }
}

ここで引数のcはc++の参照ですのでdereferenceable(4)です。 さてプログラマが(a[i] <= 999 ならばobj = &c)であると思いならがらコードを書いてるとします。さてここでaとcはaliasしないのでcの中身はループ内で値が変わりません。またLLVM的には関数内どこでもderefできると思ってます。よって

int *obj;
void foo(int& c, int * __restrict a, int * __restrict b) {
    delete obj;
    int c_loaded = c; // ロードしてる
    for (int i = 0; i < 3; ++i) {
        if (a[i] > 999) {
            a[i] = c_loaded * b[i];
        }
    }
}

のほうが効率が良さそうです。さてa[i] <= 999の場合を考えます。最適化前はcはロードされないはずだったのですが最適化後はロードされてしまいます。ここでa[i] <= 999よりobj=&cなのでuse after freeで終わりです。

このように本来であれば引数%argがプログラムポイントPにおいてもdereferenceable(n)であるためにはP以前にdeallocateされ得ないことをLLVM側で確かめる必要があるわけです。これは多少保守的になってしまいますがCFGをSCCして上の方から伝搬するとかでうまくいきそうです。

ここで、まず定義から直そうとしているのが以下のパッチです。

⚙ D61652 [Attr] Introduce dereferenceable_globally

ここでは

  • dereferenceableは修飾されたプログラムポイントでのみ有効であるという意味に変更
  • dereferenceable_globallyというそのポインタが定義されたときからプログラムの終了までallocate可能であることを保証するメタデータの導入

2点が提案されています。dereferenceable_globallyに関していうとグローバル変数くらいにしか付けられなさそうですが...

そこにRustの開発者の方(RustBeltのRalf Jungさんだった)が

  1. Rustにおいては「関数のスコープ全体でdereferenceableが成立する」という意味で参照に無条件に付与されている（別スレッドから、違う参照からdeallocateされ得ないので)
  2. dereferenceable_globallyは強すぎてRustの参照にも付けれないので意味がない

という観点から"generally happy with its semantics"と主張しています。Rustが吐くコードに関してはuse afte freeなどの危険なコードは言語レベルで弾くことができるので、現状のLLVMのdereferenceableの定義を変える必要が全く無いわけです*1。むしろ変更に対応するコストと最適化がされづらくなるというRust側からするとマイナス面が大きいです。

折衷案として出てるのが関数の引数に対して「関数のスコープ全体でdereferenceableが成立する」をnofree,noalias,dereferecneableで表現するという考えです。確かに

  • nofree はdeallocateする関数の引数/命令のオペランドにならない
  • noaliasはポインタのaliasが存在しない

の2つがdereferenceableに加えて成立するならば、dereferenceableは損なわれることが無いように思えます。

上のスレッドではRustにおいて、noaliasはimmutable refに対しては付与していいだろうが、mutalbe refに対してはnoaliasは危ないからやめたほうが良いという意見が出ています。個人的にはもう一つ問題があると思っていてnoaliasをimmutable refに対して無条件につけるのはRust的にはmutateされないことが保証されているので、LLVMで最適化してもバグったりしないとは思いますが、

pub fn f(b:&i32, c:&i32) -> i32 {
  return b + c;
}
pub fn main() {
  let a = 42;
  
  println!("{}", f(&a,&a));
}

上のような場合,b, cにnoaliasをつけるのは、b, cがaliasしうるので未定義なのでやっぱりダメだと思います。 かと言って全ての参照にnoalias付けないようにすると先述した「関数のスコープ全体でdereferenceableが成立する」をimmutable refにすら付けらなくなってしまうので困ったなあという感じです。やっぱり専用のdereferenceable_scopeみたいなものを導入するのが丸い気がしますね。

NonZeroUXXのLower

github.com

Rustには正の数を表すような型NonZeroUXXのような型があります。現在のLLVMはこれを上手く表現することができません。

use std::num::NonZeroU64;
pub fn foo(x: u64, y: NonZeroU64) -> u64 {
    x / y.get()
}

をReleaseでコンパイルすると

define i64 @_ZN10playground3foo17h6f7b350790e360ceE(i64 %x, i64 %y) unnamed_addr #0 {
start:
  %0 = icmp eq i64 %y, 0 ; これは消せるはず
  br i1 %0, label %panic, label %bb2, !prof !1

bb2:                                              ; preds = %start
  %1 = udiv i64 %x, %y
  ret i64 %1

panic: ; 当然ここも消せる                                         
   ...
}

となり、現在は最適化できていないことが分かります、残念。 Rust Playground

さてこれは引数%yに(0, MAX]のような制約をつけられると良さそうです。 この問題のややこしいところはLLVMには範囲に制限するメタデータがあるという点です。

LLVM Language Reference Manual — LLVM 10 documentation にある例を引用すると

%a = load i8, i8* %x, align 1, !range !0 ; %a ∈ [0, 2)
%b = load i8, i8* %y, align 1, !range !1 ; %b ∈ [-1, 2)
%c = call i8 @foo(),       !range !2 ; %c ∈ [0, 2) ∪ [3, 6)
...
!0 = !{ i8 0, i8 2 }
!1 = !{ i8 255, i8 2 }
!2 = !{ i8 0, i8 2, i8 3, i8 6 } ;  0,1番目, 2,3番目でそれぞれ半開区間を表す。

つまり以下のようなLLVM IRをopt -O1にかける*2 と

define i64 @f(i64 %x, i64* %y) {
start:
  %y-deref = load i64, i64* %y, !range !0
  %0 = icmp eq i64 %y-deref, 0 ; 
  br i1 %0, label %panic, label %bb2

bb2:                                              ; preds = %start
  %1 = udiv i64 %x, %y-deref
  ret i64 %1

panic:                                         
  unreachable
}
!0 = !{i64 1, i64 0}

こうなります。

define i64 @f(i64 %x, i64* %y) {
start:
  %y-deref = load i64, i64* %y, !range !0
  %0 = udiv i64 %x, %y-deref
  ret i64 %0
}
!0 = !{i64 1, i64 0} ; 0はMAX+1なので[1, MAX)を表します

godbolt.org この場合は実際に最適化できていることが分かります。 違いは

  • %yを参照渡しにしている
  • load命令に!rangeメタデータを付与している

です。じゃあどうして%yに!rangeをつけれないのかという疑問が出るんですけど !rangeはload, call命令にのみ付けられる仕様に現在はなっています。よって関数の引数に!rangeを付与することができません。

解決方法としては

  • assertを挟む、つまり関数が始まってすぐにcmpとllvm.assumeをぶっこむ

    フロントエンド(Rust)側のみで対応でき、良い感じですが区間にあるという情報がそこそこ複雑な幾つかの比較命令のconjunction/disjunctionになってしまうという点で良くないです。

  • LLVM側を拡張して引数にメタデータを載せられるようにする

    これは割と根本的な解決になっていそうで良さそうです。実際に以前に拡張しようとした形跡があります。ですが、文法、パーサー(bitcodeも!), llvm::Valueにメタデータを持たせる、Verifierの拡張、...とLLVM側をかなり変更する必要性があり実装されていません。またllvm::Metadataはllvm::Attributeに比べてコストが大きいと言われているので難しいかもしれません。

  • Attributeにrangeを追加する
    Attributeなら関数の引数に情報を添付できます。dereferenceable(n), align nのように整数を持ったAttributeもあるのでrange(integer type, l, r)のようなAttributeがあると問題を解決できそうです。問題はAttributeの引数にはlistをもたせるのが恐らく不可能であるという点です。よって表現できるのは一つの半開区間のみです。Rustに関してはNonZero以外のユースケースが無いと思うので問題ないんですが...

となり一長一短な感じです。

さて最初のRustのコードをDebugでコンパイルしてみると

 %3 = load i64, i64* %y, align 8, !range !30 ;これ
; call core::num::NonZeroU64::get
  %4 = call i64 @_ZN4core3num10NonZeroU643get17h15203f6a455e7f46E(i64 %3), !range !30;これ
...

!30 = !{i64 1, i64 0} ; [0, MAX)

これを見ると!rangeがついています。 先述しましたがload, callには!rangeが付けれるのでDebugだと上手く付けることができます😜 まあrangeの伝搬が上手くできていないんで最適化はされないんですが...

空無限ループ

github.com これは有名ですね(またRalf Jungさんだった)。

pub fn f() {
  loop{}
}
pub fn main() {
  f();
  println!("end");
}

のようなプログラムが終わってしまう（実際は"end"が表示されず落ちる)のが問題だということです。

上のissueに全て説明がありますが、軽く説明すると副作用が無い無限ループが定義されているRustと、定義されているが消しても良いとするっぽいLLVMとのギャップが原因です。「っぽい」と書いたのはLLVMにおいて定義か未定義かLangRefには書いてないからです。空ループそのものは未定義では無くて無限ループのbodyにmalloc(positive_number)みたいなことをすると未定義であると教わった記憶があります...よくわからん...

例として

define i32 @f1(){
  br label %loop

loop:
  br label %loop
}

define i32 @f2() {
  %ret = tail call i32 @f2()
  ret i32 0
}

define i32 @f3() {
  %ret = tail call i32 @f1()
  ret i32 0
}

define i32 @f4() {
  %ret = tail call i32 @f2()
  ret i32 0
}

というコードをLLVMで最適化することを考えます。opt -O1とかすると

define i32 @f1() local_unnamed_addr #0 {
  br label %loop

loop:                                             ; preds = %loop, %0
  br label %loop
}

; Function Attrs: nounwind readnone
define i32 @f2() local_unnamed_addr #1 {
  ret i32 0
}

; Function Attrs: norecurse noreturn nounwind readnone
define i32 @f3() local_unnamed_addr #0 {
  unreachable
}

; Function Attrs: nounwind readnone
define i32 @f4() local_unnamed_addr #1 {
  ret i32 0
}

とかになります。f1を見てくれると分かりますが空ループそのものはLLVMでも定義されています。Rustならば全て無限ループが残ってほしいというのに、 f2、f3、f4は関数呼び出しが消され、f3はunrechableというterminatorが追加されているという感じに変更されています。実はこれは無限ループ自体は全く関係なく「副作用を持たないかつ例外を投げない関数呼び出しは返り値が使われないならば消しても良い」という最適化です。

この最適化は（今回の場合は) 主にこの2つのパスがしています。

LLVM: lib/Transforms/IPO/PruneEH.cpp Source File PruneEH はPrune (unused) exception handlersの略です。これはTransforms/IPO/FunctionAttrs.cpp, Attributor.cppのようにCallGraphの下からnounwind, noreturnをボトムアップに推論していくパスのようです*3。 また推論の後noreturnを持つ関数を呼んでいるときにterminatorをunrechableにするということも行っています。

LLVM: lib/Transforms/Scalar/EarlyCSE.cpp Source File

Common-subexpression eliminationのはずなんですが、むしろDead code eliminationをしています。isInstructionTriviallyDeadという関数が副作用のない無限ループをする関数呼び出しをDeadだと判定して関数呼び出しを消すようです。isInstructionTriviallyDeadはwouldInstructionBeTriviallyDeadを中で呼んでいて、 llvm-project/Local.cpp at 97572775d2fe088d8059b3a9423f6d8539fafe33 · llvm/llvm-project · GitHub の

bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
                                           const TargetLibraryInfo *TLI) {
  ....
  if (!I->mayHaveSideEffects())
    return true;
  /*
     mayHaveSideEffects { return I->mayWriteToMemory() || I-> mayThrow(); }
  */

にあるようにI->mayHaveSideEffects()で副作用が無いので、falseを返すので結局関数呼び出しが消えます。

さて今見たようにLLVMは副作用が無い無限ループを消すようです。それはしょうがないとして問題点はこれがLangRefに書いておらず文書化されていないことです。

本職の方々の間ですら解釈に違いがある様子(これの真ん中下くらいから）が見れます。文書化しようとする動き(これとかこれ)もありますが現状それには至っていません。 *4

一方C++には仕様で副作用がない無限ループが未定義であると決まっています(Forward progressについての言及)。 en.cppreference.com

つまりclangのバックエンドとしてのLLVMは副作用が無い無限ループを消してもよく（消したほうが一般に最適化としては優れている),

RustのバックエンドとしてのLLVMは副作用が無い無限ループを消さないという挙動をLLVMは求められているわけですが、現状は前者側にべったりです。

後者の言語実装者は llvm.sideeffectというinaccessiblememonly nounwindというAttributeをもったダミーの命令を適宜ループに挿入することが一応LLVMから提供されている方法です。

github.com

しかしながらこの命令を入れることによって最適化が上手く行かなくなる現象が起こります😨 *5。実際Rustでも起こっています。

Add llvm.sideeffect to potential infinite loops and recursions by sfanxiang · Pull Request #59546 · rust-lang/rust · GitHub

処理時間12倍なってるベンチマークは何があったんですかね...早く治ると良いですね

終わりに

本当はnoalias, LTOやConstant propについても扱いたかったのですが長くなってしまうので違う機会にしたいなと思います。来年こそは(研究とかで)Rustを使いこなせるように頑張りたいです✌

*1: 考えれるのはインラインして命令の順番を変えるみたいな状況であるが流石にそこまでヤバい最適化はしないだろうですし..

*2:正確にはopt -simplifycfg -early-cseで十分です

*3: 前回書いた記事でAttributorについて書いてみたので読んでみてください🙏

*4: Chandlerさんの返信を見て確かにと思ったのがRustからC++を呼ぶみたいなシュチュエーションはどうすればいいでしょうね

*5: 例えば関数内の命令数が多くなってinlineしなくなってしまうとか, カウントする際にハードコーディングして省けばよいですが.. 絶対漏れが出るし挙動がわかりづらくなる..流石にinlineとかloop unrollとかの有名所は上手くやってるでしょうが..