Visual Studio 2019でllvmがビルドできない問題とその対処

例によって「Visual Studioでclangを使う」話ではなく、「Visual Studioでllvm自体をビルドする」話です。

症状

Building Attributes.inc...
llvm-tblgen.exe: Unknown command line argument '-gen-attrs'. Try: '..\..\..\Debug\bin\llvm-tblgen.exe -help'
llvm-tblgen.exe: Did you mean '-stats'?
llvm\include\llvm/IR/Attributes.h(74,14): fatal error C1083: include ファイルを開けません。'llvm/IR/Attributes.inc':No such file or directory

などのエラーメッセージが出てビルドできません。

確かにllvm/IR/Attributes.incは存在しません。これは自動生成されるファイルなのですが、生成するllvm-tblgen.exeというプログラムが、（ビルドできているにもかかわらず）正しく動作しないことが原因です。

原因究明

「'llvm/IR/Attributes.inc'」などとググっても原因はよくわかりません（単に依存関係を間違えている事例ばかり出てきます）。

「llvm-tblgen msvc」とググったところ、以下の手掛かりを得ました（二つ目のサイトは一つ目のサイトにリンクがありました）。

• [llvm] llvm-tblgen.exe fails when building LLVM · Issue #11558 · microsoft/vcpkg · GitHub
• <atomic>: In pre-C++20 mode, the constructor should be trivial · Issue #661 · microsoft/STL · GitHub

原因

最新のmsvcではヘッダが更新されC++20の機能が追加されました。この機能はC++11/14/17でコンパイルする際は（マクロ等で）適切に無効にされる必要がありますが、そうなっていないというmsvcのバグが原因です。

アトミック変数の初期化周りの仕様がC++20から変更されますが、どうやらこれが破壊的変更になっていて、コンパイルは素通りするものの動作が変わってしまっているようです。

解決法

コンパイラを変更する方法

問題のあるヘッダファイルが使われるのは16.6以降のバージョンです。

したがって、Visual Studio 2019 のビルド番号とリリース日 | Microsoft Docs から16.6以前のバージョン（例えば16.5.5）をインストールすれば、問題は発生しません。

ソースコードを変更する方法

この問題へのワークアラウンドがコミットされている（[ManagedStatic] Fix build errors with clang-tblgen in Debug mode usin… · llvm/llvm-project@28a6713 · GitHub）ため、このコミット以降であれば問題は発生しません。

先日リリースされたllvm10.0.1には、このコミットが含まれています。

RISC-Vのビット操作系拡張（B拡張）のまとめ（その3）

gorc, gorci

gorc命令では、「入力の両方が0なら出力の両方が0、それ以外なら出力の両方が1」というバタフライ演算を、FFTのように適用します。段のバタフライネットワークのうち、どこを有効にし、どこを無効（入力を素通し）にするかをrs2/immで指定します。

XLEN'(1,2,4,8,16,32,64)ビット毎に、「X(1,2,4,8,16,32)ビット飛ばしのXLEN/Xビットすべてが0ならそれらを0のままに、そうでないならそれらをすべて1に変更」を行うというSIMD命令が実現可能です。

8ビット毎に、「その8ビット全てが0なら0のまま、そうでないならそれらをすべて1に変更」というSIMD命令orc.bは、文字列検索に有用です。

RISC-Vのビット操作系拡張（B拡張）のまとめ（その2）

レジスタ中のビット列の順序を入れ替える命令についてまとめます。

rsレジスタの中身が[tex: \Sum{i=0}^{XLEN-1}2ⁱ\dot a_i]だった時、rdレジスタに[tex: \Sum{i=0}^{XLEN-1}2ⁱ\dot a_{f(i)}]を書き込みます。 ここで、は、[0, X_LEN-1]から[0, X_LEN-1]への全単射です。XLENは、レジスタの幅で、32とか64です。

rol, ror, rori

循環シフト（ローテート）です。入れ替えの計算式は、循環シフト幅をとして（左ローテートの場合）、です。

循環シフト幅が定数の命令は、roriのみです。これは、左ローテートでできることと右ローテートでできることは同一だからです。 実際、左kビットローテートは、右(XLEN-k)ビットローテートと同値です。

grev, grevi

ビット列順序逆転の一般化です。入れ替えの計算式は、パラメータ値をとしてです。の時、ビット列順序逆転になります。 それ以外のパラメータのうち、二進法で表した時010*のようにあらわせるパラメータ値では、より幅の短いXLEN'(1, 2, 4, 8, 16, 32)に対するXLEN''(1,2,4,8,16,32)ビット毎のブロックの列順序逆転のSIMD命令とみなせます。 さらにそれ以外のパラメータ値の場合は、解釈の難しい動作をすることになります。

shfl, unshfl, shfli

ビット列のアウトシャッフルの一般化です。入れ替えの計算式を書き下すことは難しいですが、になっています。パラメータ値がXLEN-1の時、アウトシャッフルになります。

RISC-Vのビット操作系拡張（B拡張）のまとめ（その1）

ビット操作系の命令は多くのCPUにあり、各種のアルゴリズムを高速化することに役立っています。

オープンな命令セットのRISC-Vにもビット操作系の命令を拡張命令として導入しようという機運があり、どういった命令を追加するべきか議論されているようです。

とりあえずVersion 0.92版のpdfを見てまとめていきます。

riscv-bitmanip/bitmanip-0.92.pdf at master · riscv/riscv-bitmanip · GitHub

ビットカウント系命令

clz

count leading zeros です。二進数としてあらわした時、上位ビットから何ビット0が続くかを数えます。

ctz

count trailing zeros です。二進数としてあらわした時、下位ビットから何ビット0が続くかを数えます。「その数が2^kの倍数である」が成り立つ最大のkを求めることになります。

pcnt

pop count です。二進数としてあらわした時の1の数を数えます。三オペランド命令（二引数命令）にし、第二引数がゼロレジスタであるときの挙動がpop countと一致するような命令にしたほうが便利との提案が出されています。 github.com

ビット毎論理演算命令

andn

rs1 & ~rs2を計算します。

orn

rs1 | ~rs2を計算します。

xnor

rs1 ^ ~rs2を計算します。

パック命令

pack

二つのレジスタの下位半分を連結した値を計算します。 0xffff0000ffff0000のような数を二命令で生成することができます。 また、16bit/32bitのローテート操作の実現に利用可能です。 さらに、ゼロ拡張にも使えます。

pack命令の動作（32bitの場合）

packu

二つのレジスタの上位半分を連結した値を計算します。

packu命令の動作（32bitの場合）

packh

二つのレジスタの下位八ビットを連結した十六ビット値を計算します。

packh命令の動作

最大・最小を求める命令

min/max

rs1とrs2を符号付き整数として解釈した時、両者のうち大きくないほう/小さくないほうの値を計算します。 maxは絶対値を求めるのにも使えます。 また、飽和演算にも役立てられます。

minu/maxu

rs1とrs2を符号無し整数として解釈した時、両者のうち大きくないほう/小さくないほうの値を計算します。

サブワード符号拡張命令

sext.b

下位八ビットの内容を符号拡張した数を計算します。

sext.h

下位十六ビットの内容を符号拡張した数を計算します。

その他

• zext.bはandi rd, rs, 255で実現可能です。
• zext.hは32bitの場合はpack rd, rs, zero、64bitの場合はpackw rd, rs, zeroで実現可能です。
• zext.wはpack rd, rs, zeroで実現可能です（64bitの場合のみ利用価値があるため、64bitの場合を前提としています）。
• sext.wはaddiw rd, rs, 0で実現可能です。

一ビット操作命令

sbset/sbseti

rs1のrs2/immビット目を1にした数を計算します。

sbclr/sbclri

rs1のrs2/immビット目を0にした数を計算します。

sbinv/sbinvi

rs1のrs2/immビット目を反転した数を計算します。

sbext/sbexti

rs1のrs2/immビット目を計算します。計算される値は、0か1のどちらかです。

一のシフト系命令

（うまい訳語がないので「一のシフト」としました）

slo/sloi

左シフトですが、下位ビットは1で埋められます。 ~(~rs1 << (rs2 & XLEN-1))と書けます。 0xffffffみたいな数を一命令で生成することができます。

sro/sroi

右シフトですが、上位ビットは1で埋められます。 ~(~rs1 >> (rs2 & XLEN-1))と書けます。

条件分岐内蔵命令

ChampSimの変な点についてメモ

ChampSimというコンピュータアーキテクチャの研究でよく使われている（？）シミュレータがあります。 他のシミュレータと比べてソースコードが簡潔なのはいい点ですが、シミュレーションの正確性はかなり怪しいです。 ソースコードを全部読んで見つけた変な点をメモしておきます（大半は先週今週あたりに直りました）。

ソースコードの問題点

デコード幅がおかしい

不等号を間違えていてデコード幅が1多くなっています。今は直っています。

デコーダーがパイプライン化されていない

このサイクルにデコードした命令数ではなく、デコードステージにあるすべての命令数がデコード幅以下になるようなコードになっています。今は直っています。

何回もフェッチされる

フェッチ完了後に同じキャッシュラインにある命令がフェッチ開始されると、フェッチ中状態に戻ってしまいます。developブランチでは直っています。

命令のスケジューリングがおかしい1

[ROB.head, ROB.size)の範囲のみをスケジューリングしていたため、[0, ROB.head)の範囲の命令はROB.headが一巡するまでスケジューリングされなくなっています。developブランチでは直っています。

SPPというプリフェッチャが間違っている

配列外アクセスをしている部分があります。DPC3に参加したSPP+PPFというプリフェッチャもバグっているらしいです（2020 ISCA p.125）。

キャッシュのレイテンシ設定がおかしい

L2キャッシュでヒットした場合、そのレイテンシはL1D_LATENCY+L2C_LATENCY+L1D_LATENCYになります。意図したものとは思いづらいです。

分岐命令が全て方向分岐予測器にかけられる

無条件分岐命令であっても、分岐方向予測器がnot-takenだと言えば分岐予測ミスになります。 逆に、間接分岐命令であっても、分岐方向予測器がtakenだと言えば分岐予測成功になります。 BTBが欠如しているため、こういうことになるようです。

x86トレースにおける問題点

pop命令のレイテンシが長すぎる

pop命令はRSPレジスタとなんらかのメモリをソースとし、RSPレジスタと他のレジスタをデスティネーションとする命令です。RSPレジスタの値は、RSPレジスタの値足す8になるのですが、見た目上、メモリから読み出した内容に依存してRSPが決まるようにも見えるため、そのような依存の連鎖でシミュレーションされています。シミュレーション対象プログラムの実行速度はほとんどこれに支配されています。DPC3の性能向上値はこの点で怪しいです。

A64トレースにおける問題点

命令のスケジューリングがおかしい2

命令間の依存関係を推定する部分にヒューリスティクスが導入されましたが、A64トレースでは完全におかしくなります。

条件分岐命令が即実行される

条件分岐命令のソースレジスタがEIPレジスタだけになってしまっているため、本当はほかのレジスタに依存しているであろう条件命令が即実行されてしまいます。これはシミュレーション対象プログラムを不当に高速化しています。IPC1の性能向上値はこの点で怪しいです。

ポラードのロー法で64bit符号なし整数を素因数分解する

ポラードのロー法（Pollard's rho algorithm）は、与えられた数nの非自明な因数を一つ見つける乱択アルゴリズムです。この手法が答えを返した場合、解は常に正しいことが保証されます。ただし、このアルゴリズムは「失敗」を返して終了することもあります*1。

ポラードのロー法の概要

ポラードのロー法では、与えられた数nの任意の因数pについて、乱数列のうちmod pで見た時に同じ値になる部分を、フロイドの循環検出アルゴリズムを用いて発見します。 発見された二つの乱数値をx、yとすると、gcd(|x-y|, n)はpの倍数になるため、これを非自明な因数として返却します。 完全にランダムな乱数列を使った場合、mod pで見た時に同じ値のペアを一つ見つけるのに必要な乱数生成回数は、回です。

この手法の肝は、nの因数pについて、疑似乱数列の中にあるmod pで見た時に同じ値になるペアを、pを知らないままに検出することです。 そのためには、mod pで循環する疑似乱数列を使用しないといけません。ここで、pはまだわからない点が難しいですが、幸いmod nでの線形合同法が条件を満たします*2。

素因数分解プログラム

先週紹介した、高速gcdプログラムを使用しています。 clang++でコンパイルする場合に高速化するようなコードになっています。 __builtin_ctzllや__uint128_tなど非標準の機能を使っていますが、勘弁してください。

#include <cstdint>
#include <iostream>

std::uint64_t gcd_impl( std::uint64_t x, std::uint64_t y ) noexcept {
    if( x == y ) { return x; }
    const std::uint64_t a = y - x;
    const std::uint64_t b = x - y;
    const int n = __builtin_ctzll( b );
    const std::uint64_t s = x < y ? a : b;
    const std::uint64_t t = x < y ? x : y;
    return ::gcd_impl( s >> n, t );
}

std::uint64_t gcd( std::uint64_t x, std::uint64_t y ) noexcept {
    const int n = __builtin_ctzll( x );
    const int m = __builtin_ctzll( y );
    return ::gcd_impl( x >> n, y >> m ) << ( n < m ? n : m );
}

int main() {
    std::uint64_t n;
    std::cin >> n;

    for( std::uint64_t x = 2, y = 2; ; ) {
        x = ((__uint128_t)x * x + 1) % n;
        y = ((__uint128_t)y * y + 1) % n;
        y = ((__uint128_t)y * y + 1) % n;
        if( std::uint64_t z = ::gcd( x < y ? y - x : x - y, n ); z != 1 ) {
            std::cout << n << " = " << z << " * " << n / z << std::endl;
            return 0;
        }
    }
}

このソースコードをclang++-10 -std=c++17 -O3でコンパイルした場合、10023859281455311421*3の素因数分解を0.01秒で完了することができました。

ちなみに、21,25,95,125, ... などは、合成数にもかかわらず、このプログラムで素因数分解できません。 そういった数の存在数を以下の表にまとめてみました。

範囲	個数
102以下	3個
103以下	14個
104以下	62個
105以下	213個
106以下	919個
107以下	3660個

*1:乱数生成器のパラメータ変更のみによって常に答えが得られるのかは知りません。

*2:線形合同法の乱数の質が条件を満たしているのかは怪しいところですが、実験的にはうまくいっているようです。

*3:Wikipediaに載っていた例で、1.1×2⁶³程度の大きさ

SonicBOOM (BOOMv3) の論文をながめて思ったこと

5/29～6/4に行われたコンピューターアーキテクチャの国際会議、ISCA 2020 で開催されたワークショップ「CARRV」で発表されていた、Sonic BOOMの論文をながめて思ったことを書いておきます。

Figure 1 について

この手の図ってWikiChipでよく見る（例えば、 SkylakeやSunnyCoveの図に非常に似ている）のですが、なんか業界の慣行なんでしょうか……？

分岐予測について

同じ ISCA 2020 の Industry Track で発表されていた IBM の分岐予測器の論文にも書かれていましたが、最近の商用プロセッサについている分岐予測器は、教科書的な分岐予測器とはかなり違う構成になっているようです。命令フェッチユニットは以下の物から構成されているようです。

• 簡易分岐予測器
• フェッチバッファ
• 数サイクルかかるパイプライン化されている正確な分岐予測器
• スナップショット付きの return address stack (RAS)

まず、簡易分岐予測器（L0 BTB*1）が毎サイクル動きます。

1サイクルで完了する簡易分岐予測器はたまに間違い、数サイクルかかる正確な分岐予測器が訂正するという事態が発生します。しかし、デコード速度よりフェッチ速度のほうが高いので、この問題は隠蔽されることが多いです。これを実現するため、フェッチユニットとデコードユニットの間にフェッチバッファが置かれます。

分岐予測器は、自分の出した予測に従って「過去の分岐の情報」を更新しつつどんどん未来を予測していきます。分岐予測ミスが発覚した場合、間違った予測に基づいて更新していた「過去の分岐の情報」を復帰しないと、狂った「過去の分岐の情報」に基づいて予測をすることになり、特に方向分岐予測器では、予測がボロボロになります。ここで、リターン命令に特化した補助分岐予測器であるRASは、そのような復帰をしなくても破滅的なことにはならない＆復帰にかかるコストが方向分岐予測器より大きい、という理由から復帰しないことが多かったような気がしますが、最近はRASもちゃんと復帰するようにしたようです。

Short-forwards Branch optimizations について

非常に短いif節をコンパイルしたときに出現するような短距離前方分岐を、条件実行命令に変換するという最適化を内部で行うというものです。この最適化により、CoreMarkスコアが4.9から6.15に向上したと書かれています。

Figure 3 は「当てにくい分岐」の例だと思われますが、不適切な例です。 最大値を求めるループというのは、条件実行命令を使うとかえって遅くなる例として非常に有名です（条件分岐とcmovとmaxps）。 というのも、配列の中のほとんどの値は「現状最大値」より小さいので、not-takenと予測するのが精度よく当たるためです。 かえって遅くなる理由は、条件計算命令がクリティカルパスを伸ばすためです。

CoreMarkで大きな性能向上が得られる理由は、CoreMarkに巡回冗長検査 (Cyclic Redundancy Check, CRC) のコードが含まれるためです。 CRCの計算には完全ランダムな分岐が含まれ、分岐予測が当たらないため、条件分岐命令を使うとこのような性能向上が得られるのです。

ちなみに、CoreMarkをRV32Gの設定でgcc9.2.0を使ってコンパイルしたバイナリを使った場合、CoreMark/MHzは3.39×IPCに等しくなります。ここから算出すると、SonicBOOMの6.15CoreMark/MHzは、IPC=1.81ほどということになります（SonicBOOMはRV64GCですが、RV32Gと命令数が変わらないと仮定しました）。

*1:Column predictor（way予測器）が使われることもあります。n-wayセットアソシアティブキャッシュの何way目にありそうかを予測するものです。こう聞くと頭のおかしい予測器に聞こえますが、もっとも単純にはMRUポジションを予測するという方法があり、うまくいくらしいです。その場合、ダイレクトマップキャッシュ（L0）と(n-1)-wayセットアソシアティブキャッシュ（L1）の階層構造になっていることに相当します。