RustのLLVMに関する問題
概要
この記事はRust Advent Calendar 2019の12日目の記事として書かれました。
遅刻してしまった...すいません(最悪)。
言わずもがな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)
という性質が関数のスコープ内の任意のプログラムポイントで成立することを仮定しているかのように最適化を現状しています。ここでバグを生み出します。
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さんだった)が
- Rustにおいては「関数のスコープ全体で
dereferenceable
が成立する」という意味で参照に無条件に付与されている(別スレッドから、違う参照からdeallocateされ得ないので) 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
みたいなものを導入するのが丸い気がしますね。
(訂正) 上の議論は間違っていって現状noalias
はすでにimmutable refについているようです。それとb,c
がaliasしたときに未定義であるというのはLangRefに定義されておらず、自分の思い違いでした。訂正します。
てかstoreされない参照にnoaliasつけるのはバグらないのかなあ....
NonZeroUXXのLower
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になってしまうという点で良くないです。
-
これは割と根本的な解決になっていそうで良さそうです。実際に以前に拡張しようとした形跡があります。ですが、文法、パーサー(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から提供されている方法です。
しかしながらこの命令を入れることによって最適化が上手く行かなくなる現象が起こります😨 *5。実際Rustでも起こっています。
処理時間12倍なってるベンチマークは何があったんですかね...早く治ると良いですね
終わりに
本当はnoalias, LTOやConstant propについても扱いたかったのですが長くなってしまうので違う機会にしたいなと思います。来年こそは(研究とかで)Rustを使いこなせるように頑張りたいです✌
*1: 考えれるのはインラインして命令の順番を変えるみたいな状況であるが流石にそこまでヤバい最適化はしないだろうですし..
*2:正確にはopt -simplifycfg -early-cseで十分です
*3: 前回書いた記事でAttributorについて書いてみたので読んでみてください🙏
*4: Chandlerさんの返信を見て確かにと思ったのがRustからC++を呼ぶみたいなシュチュエーションはどうすればいいでしょうね
*5: 例えば関数内の命令数が多くなってinlineしなくなってしまうとか, カウントする際にハードコーディングして省けばよいですが.. 絶対漏れが出るし挙動がわかりづらくなる..流石にinlineとかloop unrollとかの有名所は上手くやってるでしょうが..