この記事は

の6日目のために書かれました。22時くらいに投稿するのはギリギリセーフ？(すいません)

概要

4,5ヶ月前AttributorというパスがLLVMに追加されました（唐突)。自分はGSoCでこれの開発の手伝いをしたので紹介したいと思います。

www.youtube.com

上はメインに開発をしていたJohannesさん（メンターだった)がLLVM Devmtgで解説してる動画です。分かりやすいんで時間があれば見てみてください。もう一つチュートリアルがあるんですが難しめです。GSoCは全体の設計を彼がやって僕ともう一人の生徒で推論部分を実装するという感じでした。

Attributor

Attributorはもともと"Attribute"を推論するためのフレームワークでした *1。Attributeというのは最適化のパスにおいてて最適化が可能かどうかなどを判定するのに用いられるメタな情報です(llvm::Metadataとは違います *2 )。

例えば

int f(int *p, int u){
  return *p + u;
}

という適当な関数をclang -O2 -emit-llvm -S とかしてLLVM IRにすると

define i32 @f(i32* nocapture readonly %p, i32 %u) #0 {
  %p-deref = load i32, i32* %p, align 4
  %res = add nsw i32 %p-deref, %u
  ret i32 %res
}
attributes #0 = { norecurse nounwind readonly }

のようなコードが出てきます*3。上のnocaputre, readonly, nounwind, norecurse, align 4がAttributeです。

nocapture readonly %p は

%pが指すアドレスにstoreされない(readonly)
%pはcaptureされない(nocapture, 関数のスコープを超えてoutliveしない)

という情報を与えます。このように関数の引数につけられたAttributeをArgument Attributeと言います。

define i32 @f(i32* nocapture readonly %p, i32 %u) #0 {にある#0は関数を修飾しています。

つまりfに

fは再帰をしない(norecurse)
fは例外を投げない(nounwind)
fはstoreしない(readonly)

という性質があることを保証しています。このようなAttributeをFunction Attributeといます。

他にも関数の返り値につけることができます。またcontext sensitiveにCallSiteを区別してAttributeをつけることもできます。

全てのAttributeの定義はLangRefにあります。見てみてください。

まずデモとして上のコードをAttributorに通したときの結果を見てみましょう*4。 https://godbolt.org/z/nq9mQc

define i32 @f(i32* nocapture nofree nonnull readonly align 4 dereferenceable(4) %p, i32 %u) #0 {
  %p-deref = load i32, i32* %p, align 4 ... (i)
  %res = add nsw i32 %p-deref, %u ... (ii)
  ret i32 %res
}
attributes #0 = { nofree norecurse nosync nounwind readonly willreturn }

のようにAttributeが推論されます。%pを見てみるとnofree, nonnull, align 4, dereferenceable(4)が新たに推論され、fにはnofree, nosync, willreturnが推論されていることがわかります。

nonnullはそのポインタがnullでない
align 4はそのアドレスが4の倍数である
dereferenceable(4)はそのアドレスから最低4bytesはallocateされている
nofree は関数に対してはfree, deleteのようにメモリーをdeallocateする命令が関数内で呼ばれないこと、引数に対してはその値がfree, deleteされないこと
nosyncはスレッドの同期をするような命令が呼ばれない
willreturnは関数が必ず返る(無限ループ, exitとかが無い)

ことをそれぞれ保証します。このようなAttributeを推論していくのがAttributorがやっていることです。

軽く説明すると以下のような動きをします:

noXXXのようなFunction Attribute(ex. nounwind, nofree)に関してはXXXを満たす命令が関数f内にないことを示したい。primitive な命令に関しては簡単に判定できる。関数呼び出し(例えばgという関数を呼び出すとする)があったらgはnoXXXを満たすと仮定する。gの上でも推論を回しXXXを満たす命令があったらg,fともにXXXを満たす命令が実行されうるのでnoXXXは推論できない。逆にnoXXXでない証拠がでないならnoXXXと言って良い。
%argがnofreeであることを示したい。もし関数がnofreeと仮定されているなら直ちに言える。nofreeが仮定されていなくても%argの全てのUseを見てそこでfreeされなければ良い。関数の引数に使われているならばそこの引数がnofreeであると仮定されてれば良い。
%argがnonnullであることを示したい。もしも関数にload i32* %argのような命令があり、その命令が必ず実行されるなら%argがnullのときパニックするので%argがnonnullと言って良い。

推論の仕組みは大きく分けて2つに分かれます。

１つ目は最初のnoXXXに対する推論法を見るとわかりやすいですが、「とりあえずそのAttributeを持っていると仮定して、その仮定に反するならば諦める」というものです。

そのAttributeを持っていると仮定する
仮定に反するかを確かめることを繰り返す、反するなら諦める。諦めたなら、諦めたという情報を依存関係がある所に伝搬する。
全体で変更がなくなったとき、その仮定は実際成立することが言える

という流れです。これについては後から詳しく説明します。

2つ目は「プログラムポイントPを通る任意の実行列においてそのAttributeを持つことが示されるならばPにおいてそのAttributeを持っているとして良い」というものです。例えば関数の引数について推論したいときは、Pとしてentry point(最初のBBの最初の命令）をとってあればよいです。

int f1(int *p){
  return *p;
}

のような関数ではpは必ず4バイトderefされるので引数pはdereferenceable(4)を有します。

int f2(int *p){
  if(rand()) {
     return p[0];
  }
  return 0;
}

のような関数ではrand()の値によってはpはderefされないのでダメです。

int f3(int *p){
  maybe_infinite_loop();
  return *p;
}

上の関数の場合pがderefされないで無限ループする可能性があるので推論できません。この次に命令に必ず進むことが保証されるかどうか判定するのにもAttributeが使われています。willreturn,nounwindがあると十分です。

int f4(int *p){
    return p[0] + p[1];
}

この場合8バイトderefされるのでdereferenceable(8)を言えます。

int f5(int *p){
  if(rand()){
    return p[0] + p[1];
  }else{
    return p[0];
  }
}

もっというとこの関数ではpはdereferenceable(4) or dereferenceable(8)が成立するのでdereferenceable(4)と言って良いです。

現在は「Pが実行されるならば必ず実行されるようなプログラムポイントの集合」を適当に推論して実装されています。上の例ですとf1,f4は推論されますが, f5を推論できません (一応これで対応できるんですが色々と考えることがあって放置してしまったhttps://reviews.llvm.org/D65593)。

ここから実装の話に移ります。ぶっちゃけヘッダーにめちゃめちゃ詳しく書いてあるのでそっちを見たほうがいいかもしれません。 http://llvm.org/doxygen/Attributor_8h_source.html

http://llvm.org/doxygen/Attributor_8cpp_source.html

実装

AbstractAttribute

AbstractAttributeは紐付けられているValue、推論の状態、IR上の場所などを保持するクラスです。各Attributeに対して個別にAbstractAttributeを継承したクラスを作ります(ex. AANoFree, AADereferenceable...)。更にIR上の場所ごとに継承したクラスを作ります(ex. AANoFreeArgument, AANoFreeFunction..)。

例外はありますが基本的に状態は束の2つ組で表すことが多いです。この2つの値はそれぞれ見ている性質の元々知っている情報(known, lkと置く), 仮定(assumption, laと置く)です。もともとあった情報より悪くなることないのでlk ≦ laを保った上で状態を変化させていきます。lk=laとなったらこれ以上変化しないので推論をやめます。

例えばnofreeに関するAANoFreeの状態はboolの組で、(false, true)が初期状態です。もし最初からすでにnofreeが修飾されていたなら状態は(true, true)となりこれ以上変化しないです。推論の途中で仮定が破られたなら(false, false)となり終わります。(false, true)のまま終われば推論は成功です。次の例を見てみます。

int f1(int *p) { return rand() ? f2(p) : 0; }
int f2(int *p) {   
  free(p); 
  return rand() ? f1(p) : f3(p); 
}
int f3(int *p) { return rand() ? f4(p) : f5(p); }
int f4(int *p) nofree { return 0; }
int f5(int *p) { return rand() ? f3(p) : 0; }

以下のcall graphを見てください。これらのnofreeのFunction Attributeの推論の動きですが、まずf4はすでにnofreeなのでf4のknownがtrueになります。 f:id:uenoku:20191206015354p:plain 次にf2にはfreeがあるのでf2のassumptionはfalseになります。 f:id:uenoku:20191206015401p:plain 次にf1はf2のassumptionはfalseになったことからf1のassumptionもfalseになります。 f:id:uenoku:20191206015422p:plain これ以上変化することは無いのでf3,f4,f5がnofreeであることを言えます。この伝搬をする関数がAbstractAttribute::updateImplです。これは仮定に対してmonotonicな状態遷移をする関数です*5。以下のようにAANoFreeFunction::updateImplが実装されています。

/// See AbstractAttribute::updateImpl(...).
ChangeStatus updateImpl(Attributor &A) override {
    // CallSite を引数にとってCalleeが`nofree`を持つ, もしくは仮定されているならば
    // trueを返す関数。
    auto CheckForNoFree = [&](Instruction &I) {
      ImmutableCallSite ICS(&I);
      if (ICS.hasFnAttr(Attribute::NoFree))
        return true;
      
      // CallerのAANoFreeFunctionをとってくる
      const auto &NoFreeAA =
          A.getAAFor<AANoFree>(*this, IRPosition::callsite_function(ICS));
      return NoFreeAA.isAssumedNoFree();
    };
    
    // 関数内の全てのCallSiteを回ってもしもfalseが見つかった場合
    // この関数の`nofree`の仮定も破られる(pessimisticなfixpoint)
    if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this))
      return indicatePessimisticFixpoint();

    return ChangeStatus::UNCHANGED;
}

他にはdereferenceableに関するAADereferenceableでは、自然数を台集合、∧ としてmin, ∨としてmaxを取った束の組を状態としてます。初期状態では(0, ∞)に初期化されます(実装では∞にはかなり大きめの整数を入れます)。次の例で動きを見てみます。

define internal i32* @f1(i32* %0, i32* %1, i1 %2) {
  %ret1 = getelementptr inbounds i32, i32* %0, i64 1
  %ret2 = getelementptr inbounds i32, i32* %1, i64 2
  %ret = select i1 %2, i32* %ret1, i32* %ret2
  ret i32* %ret
}

define i32* @f2(i32* dereferenceable(20) %0, i32* dereferenceable(32) %1, i1 %2) {
  %p = tail call i32* @f1(i32* %0, i32* %1, i1 %2)
  ret i32* %p
}
define i32* @f3(i32* dereferenceable(24) %0, i32* dereferenceable(36) %1, i1 %2) {
  %p = tail call i32* @f1(i32* %0, i32* %1, i1 %2)
  ret i32* %p
}

イメージとしてはこのようなプログラムです:

int* f1(int *a1, int *a2, int c){
   return c?a1+1:a2+2;
}
int* f2(int a1[5], int a2[8], int c){
  return f1(a1,a2,c);
}
int* f3(int a1[6], int a2[9], int c){
  return f1(a1, a2, c);
}

これは以下のように推論されていきます。 f:id:uenoku:20191206214618p:plain 初期化です。 f:id:uenoku:20191206214703p:plain 関数の先頭についている"internal"とはその関数がmodule内からのみ見えるという意味です。そして今ここでf1が呼ばれる場所が静的に全て分かっている状態です*6。するとf1の1つ目の引数に関してはdereferenceable(min(20, 24))で有ることがわかります。よってf1の1つ目の引数の状態は(0, 20)となります。同様に2つ目の引数は(0, 32)となります。

（どうでもいいのでこっからf3は消します)

f:id:uenoku:20191206212956p:plain そしてポインタの足し算を適当にしています。 f:id:uenoku:20191206213012p:plain そして関数の引数に関してはderefereneceable(min(16,24))であることが言えます。結局これ以上変化しないのでこれが不動点です。

実際に実行すると他にも色々ついてhttps://godbolt.org/z/J8tU22

; Function Attrs: nofree nosync nounwind readnone willreturn
define internal nonnull dereferenceable(16) i32* @f1(i32* nofree nonnull readnone dereferenceable(20) %0, i32* nofree nonnull readnone dereferenceable(32) %1, i1 %2) #0 {
  %ret1 = getelementptr inbounds i32, i32* %0, i64 1
  %ret2 = getelementptr inbounds i32, i32* %1, i64 2
  %ret = select i1 %2, i32* %ret1, i32* %ret2
  ret i32* %ret
}
; Function Attrs: nofree nosync nounwind readnone
define nonnull dereferenceable(16) i32* @f2(i32* nofree nonnull readnone dereferenceable(20) %0, i32* nofree nonnull readnone dereferenceable(32) %1, i1 %2) #1 {
  %p = tail call nonnull dereferenceable(16) i32* @f1(i32* nofree nonnull dereferenceable(20) %0, i32* nofree nonnull dereferenceable(32) %1, i1 %2) #0
  ret i32* %p
}

attributes #0 = { nofree nosync nounwind readnone willreturn }
attributes #1 = { nofree nosync nounwind readnone }

となります。

より強い推論

現在はできませんが、もう少しAttributorを強くすると以下の例(Attributorのテストにあります)で面白い推論ができます。

; From test/Transforms/Attributor/nonnull.ll
define internal i32* @f1(i32* %arg) {
bb:
  %tmp = icmp eq i32* %arg, null
  br i1 %tmp, label %bb9, label %bb1

bb1:                                              ; preds = %bb
  %tmp2 = load i32, i32* %arg, align 4
  %tmp3 = icmp eq i32 %tmp2, 0
  br i1 %tmp3, label %bb6, label %bb4

bb4:                                              ; preds = %bb1
  %tmp5 = getelementptr inbounds i32, i32* %arg, i64 1
  %tmp5b = tail call i32* @f3(i32* %tmp5)
  %tmp5c = getelementptr inbounds i32, i32* %tmp5b, i64 -1
  br label %bb9

bb6:                                              ; preds = %bb1
  %tmp7 = tail call i32* @f2(i32* %arg)
  ret i32* %tmp7

bb9:                                              ; preds = %bb4, %bb
  %tmp10 = phi i32* [ %tmp5c, %bb4 ], [ inttoptr (i64 4 to i32*), %bb ]
  ret i32* %tmp10
}

define internal i32* @f2(i32* %arg) {
  %tmp = tail call i32* @f1(i32* %arg)
  ret i32* %tmp
}

define internal noalias i32* @f3(i32* %arg) {
  %tmp = call i32* @f1(i32* %arg)
  ret i32* %tmp
}

f1のCFGは以下なのでf1:bb6において%argはnonnullであることが言えます。 f:id:uenoku:20191206023544p:plain 残念ながら現在はこのようなCFGを見るような推論はサポートされてません *7 。ここで%argがnonnullと言えるとf2のlinkageがinternalであることからf2の引数の%argもnonnullといえます。この場合だとf2が呼ばれるのはf1:bb6だけです。f1:bb6において%argはnonnullで成立してるのでf2の関数定義側の引数にもnonnullをつけて良いことになります。そうするとf3,f1もlinkageがinternalであることからそれぞれの引数の%argもnonnullといえます。そうするとf1:bbでの比較は無意味となり命令を減らすことができます。こんな感じです(汚くてすいません)。 f:id:uenoku:20191206025621p:plain

終わり

たまたま選んだプロジェクトがすごく好みの分野の内容だったので非常にラッキーでした。その他いろいろな話題が最初の動画で紹介されているのでぜひ見てみてください。

*1: 今現在はAttributeだけではなくInter-procedual optimizationに向けのフレームワークとして進められています。

*2:Metadataはより多岐に渡る情報を添付できます。例えば!range(値の範囲を区間に制限する), !alias_scope(最近議論されているfull restrict support)などです。AttributeとMetadataの違いですがかなり謎な感じになってます。例えばMetadataは関数の引数に付与できません。つまり!rangeを直接引数に修飾できないので、RustのNonZeroのような型を上手く表現できないです。これちょっとおもしろくてload命令には修飾できるのでRustでOptのレベルを下げて出力してそれをLLVMで最適化するとちゃんとしてくれるという話があります

*3: readonlyやnorecurseはIPO/FunctionAttrs.cppで推論されているはずです（もしかしたらclangがannotateしているかもしれませんが)

*4: 現在デフォルトではオフになっています。--attributor-disable=false をすると動きます。clangだと-mllvm --atributor-disable=falseとすればよいはず

*5:実を言うとmonotonicでは無い挙動を示しうるのが現在の実装です。前述した必ず実行される命令からの推論も同時に処理しているため、(n, n) みたいな状態から（同一イテレーションで) nより大きいn'で(n', n') のように遷移する可能性があります。

*6: 関数アドレスがどこかにcaptureされたりするとわからなくなります

*7:書いてて思ったけどisKnownNonZeroがやってくれそうな気もするけどなんでなんだろう、この手の推論をflow sensitiveといえばよいのかcontext sensitiveといえばよいのかよく分かんなくなる

日記

LLVMのAttributorというパス

概要

Attributor

実装

より強い推論

終わり