LLVM官方文檔翻譯---- LLVM原子指令與并發指引

注：該文章轉載已經得到譯者授權。

---------------------------------------------------------------------------------------------------------------------------------------------

LLVM支援線上程與異步信号面前定義良好的指令。

原子指令專門為以下定義來提供可讀的IR以及優化的代碼生成：

·        其他使用原子語義的場景，包括C++中帶有非平凡構造函數的static變量。

在IR中原子化與volatile是正交的：volatile是C/C++的volatile，它確定每個volatile讀、寫會發生，且以聲明的次序執行。幾個例子：如果一個順序一緻（SequentiallyConsistent）寫後緊跟着對同一個位址的另一個順序一緻寫，第一個寫可以被去除。對一對volatile寫，這個轉換是不允許的。另一方面，一個非volatile、非原子寫可以自由地跨過一個volatile寫，但不能跨過一個Acquire寫。

本文意在對為LLVM寫一個前端或者工作在LLVM優化遍的人提供，在并發條件下，如何處理具有特殊語義指令的一個指引。這不準備成為這些語義一個精确的指引；細節可以極端複雜且難以閱讀，這通常不是必要的。

基本的load與store允許各種優化，但在并發環境下會導緻未定義的結果；參考NotAtomic一節。本節特别地進入應用在并發環境中的一個優化器限制，我們對描述稍作展開，因為任何處理store的優化都需要了解它。

從優化器看來，規則是：如果沒有涉及任何帶有原子化次序的指令，并發不是問題，除了一個例外：如果一個變量對另一個線程或信号處理句柄可見，一個寫不能插入到它原本不會執行的路徑上。考慮以下例子：

/*C code, for readability; run through clang -O2 -S -emit-llvm to get

    equivalent IR */

 int x;

 void f(int* a) {

   for (int i = 0; i < 100; i++) {

     if (a[i])

       x += 1;

   }

 }

下面是非并發情形下等效的代碼：

int x;

void f(int* a) {

  int xtemp = x;

  for (int i = 0; i < 100; i++) {

    if (a[i])

      xtemp += 1;

  }

  x = xtemp;

}

不過，LLVM不允許從前者到後者的轉換：它會間接地引入未定義行為，如果另一個線程可以同時通路x。（這個例子特别令人感興趣，是因為在實作并發模型之前，LLVM會執行這個轉換）。

注意投機性的寫（speculative load）是允許的；作為一個競争的一部分的寫傳回undef，但不是未定義的行為。

對于簡單讀寫不足夠的情形，LLVM提供了各種原子指令。提供的具體保證依賴于表序（ordering）；參見“原子化表序”一節

原子讀寫提供了與非原子讀寫相同的基本語義，但在涉及線程與信号的環境裡，提供了額外的保證。

cmpchg與atomicrmw本質上就像一個原子讀，後跟一個原子寫（對cmpxchg寫是有條件的），但在讀寫之間，在任何線程上都不能發生其他記憶體操作。

Fence提供了不少另一個操作部分的Acquire以及/或者Release表序；它通常與單調的（Monotonic）記憶體操作一起使用。一個單調讀後跟一個Acquirefence大緻上等同于一個Acquire讀，一個單調寫後跟一個Releasefence大緻上等同于一個Release寫。順序一緻fence同時具有一個Acquirefence以及一個Releasefence的行為，并提供了額外的複雜的保證，細節參考C++11标準。

産生原子指令的前端通常需要一定程度地了解目标機器；原子指令是保證無鎖的，是以比目标機器天然支援的寬度要寬的指令是不可能産生的。

NotAtomic是顯而易見的，一個非原子的讀或寫。（這不是真正的一級原子性，但列在這裡用于比較）。這本質上是一個普通的讀或寫。如果在一個給定記憶體位置有競争，從該位置讀将傳回undef。

相關标準

對前端的注解

這個規則本質上是多線程所有以基本讀寫進行的記憶體通路都應該由一把鎖或其他同步機制保護；否則，你很可能碰到未定義的行為。如果你的前端是用于一個像Java的“安全”語言，對任何共享變量的讀寫使用Unordered。注意NotAtomicvolatile讀寫不是正确原子化的；不要嘗試使用它們作為替代。（按照C/C++标準，volatile确實圍繞異步資訊提供了一些有限的保證，但原子化通常是一個更好的方案）。

對優化器的注解

在原來不存在讀的代碼路徑上對共享變量引入讀是允許的；對共享變量引入寫則不允許。參考“原子化以外的優化”一節。

對代碼生成的注解

Unordered是最低級别的原子性。它本質上保證競争産生稍微正常的結果，而不是具有未定義的行為。它還保證操作是無鎖的，是以它不依賴資料成為一個特殊原子化結構體的部分，或者依賴一個獨立的每程序的全局鎖。注意對不支援的原子操作，代碼生成将失敗；如果你需要這樣一個操作，使用顯式鎖定。

這目的在于比對Java記憶體模型的共享變量。

這不能用于同步，但對于Java及其他需要保證生成代碼永遠不會出現未定義行為的“安全”語言是有用的。注意對在通常平台上一個自然寬度的讀，這個保證是廉價的，但對更寬的讀，像ARM上的一個64位讀（譯注，原文為store，但按上下文，應為load），是昂貴或不可用的。（Java或其他“安全”語言的前端通常在ARM上将一個64位讀分解為兩個32位ordered讀）。

就優化器而言，這禁止了任何将單個讀轉換為多個讀、将單個寫轉換為多個寫、縮窄一個寫、或寫入一個不能寫入的值的轉換。不安全優化的一些例子有：将一個指派縮窄為一個比特位，重新物化（rematerializing）一個讀，以及将讀寫轉換為一個memcpy調用。重排unordered操作是安全的，優化器應該利用之，因為unordered的操作在需要它們的語言中是常見的。

這些操作要求是原子性的，在這個意義上，如果你使用unordered讀與unordered寫，讀不能看到從未寫過的值。一個普通的讀或寫指令通常是足夠的，但注意一個unordered讀或寫不能分解為多條指令（或者一條執行多個記憶體操作的指令，像沒有LPAE的ARM上的LDRD，或者LPAEARM上非自然對齊的LDRD）。

Monotonic是可以用在同步原語中的最弱一級的原子性，盡管它不提供任何一般性的同步。它本質上保證，如果你采取所有影響一個特定位址的操作，存在一個一緻的次序。

這對應于C++11/C11memory_order_relaxed；确切定義參考這些标準。

如果你正在編寫直接使用這的一個前端，小心使用。就同步而言保證非常弱，是以確定這些僅用在你知道是正确的一個模式（pattern）。通常，這将要麼用于不保護其他記憶體的原子操作（像一個原子計數器），或者連同一個fence一起。

就優化器而言，這可以被處理作在相關記憶體位置上的一個讀+寫（别名分析将利用之）。另外，在Monotonic讀周圍重排非原子讀與Unordered讀是合法的。CSE/DSE以及其他幾個優化是允許的，但Monotonic操作不太可能以使得這些優化有用的方式來使用。

代碼生成本質上與Unordered讀寫相同。不要求fence。Cmpxchg與atomicrmw要求呈現為單個操作。

Acquire提供了擷取一把鎖以普通讀寫通路其他記憶體所需的屏障（barrier）。

這對應于C++11/C11的memory_order_acquire。它也用于C++11/C11的memory_order_consume。

如果你正在編寫直接使用這的一個前端，小心使用。Acquire僅在與一個Release操作結對時才提供一個語義保證。

不清楚原子性的優化器可以将這處理為一個非異常抛出調用。将一個Acquire讀或一個讀-修改-寫操作前的寫移到它之後，以及将一個Acquire操作前的非Acquire讀移到它之後是可能的。

帶有弱記憶體序的架構（基本上除了x86與SPARC，現在都是這樣的架構）要求某種fence來維護Acquire語義。所要求的正确fence根據架構變化很大，不過對于一個簡單的實作，大多數架構提供了一個足夠強大的屏障（ARM的dmb，PowerPC的sync等）。将這樣一個fence放在等效的Monotonic操作後足以對一個記憶體操作維護Acquire語義。

Release類似于Acquire，但帶有一個釋放一把鎖所需的屏障。

這對應于C++11/C11的memory_order_release。

如果你正在編寫直接使用這的一個前端，小心使用。Release僅在與一個Acquire操作結對時才提供一個語義保證。

不清楚原子性的優化器可以将這處理為一個非異常抛出調用。将一個Release寫或一個讀-修改-寫操作後的讀移到它之前，以及将一個Release操作後的非Release寫移到它之前是可能的。

參考關于Acquire的章節；在相關操作前的一個fence對Release通常足夠。注意一個寫-寫fence不足以實作Release語義；寫-寫fence通常不暴露給IR，因為它們極難正确使用。

AcquireRelease（IR中的acq_rel）同時提供了Acquire與Release屏障（對于同時讀寫記憶體的fence與操作）。

這對應于C++11/C11的memory_order_acq_rel。

如果你正在編寫直接使用這的一個前端，小心使用。Acquire僅在與一個Release操作結對時才提供一個語義保證，反之亦然。

通常，優化器應該将這處理為一個非異常抛出調用；可能的優化通常是不令人感興趣的。

這個操作具有Acquire與Release的語義；參考關于Acquire與Release的章節。

SequentiallyConsistent（IR中的seq_cst）對讀提供了Acquire語義，對寫提供了Release語義。另外，它保證在所有SequentiallyConsistent操作間存在一個全續（atotal ordering）。

這對應于C++11/C11的memory_order_seq_cst，Javavolatile，以及gcc相容的__sync_*固有函數。

如果前端正在導出原子操作，對于程式員，相比其他類型的操作，這些容易推理得多，使用它們通常是一個可行的性能權衡。

不清楚原子性的優化器可以将這處理為一個非異常抛出調用。對于SequentiallyConsistent的讀與寫，允許對Acquire讀與Release寫進行相同的重排，但不能重排SequentiallyConsistent的操作。

SequentiallyConsistent的讀最低限度要求與Acquire操作相同的屏障，而SequentiallyConsistent的寫要求Release屏障。另外，代碼生成器必須嚴格執行SequentiallyConsistent的寫與後跟的SequentiallyConsistent的讀之間的次序。這通常通過在讀之前或在寫之後釋出一個完整的fence來完成；不同的架構有自己的偏好。

優化器作者用于查詢的謂詞（Predicate）：

·        isSimple()：一個不是volatile或原子化的讀或寫。這是，比如memcpyopt，為它可能轉換的操作所做的檢查。

·        isUnordered()：一個不是volatile并且最多是Unordered的讀或寫。這是，比如LICM，在提升一個操作前所應該檢查的。

·        mayReadFromMemory()/mayWriteToMemory()：現存的謂詞，不過注意它們對任何是volatile或至少是Monotonic的操作傳回true。

·        isStrongerThan / isAtLeastOrStrongerThan：這些是在定序（ordering）上的謂詞。對于知道原子操作的遍它們是有用的，例如跨過單個原子通路，但不跨過一個release-acquire對的DSE執行（這樣的一個例子，參考MemoryDependencyAnalysis）。

·        别名分析：注意AA将對Acquire或Release的任何東西，以及由任何Monotonic操作通路的位址，傳回ModRef。

為了支援圍繞原子操作的優化，確定你使用正确的謂詞；如果做到了，應該就一切正常。如果你的遍應該優化某些原子操作（特别是Unordered操作），確定它不會以一個非原子操作替換一個原子讀或寫。

優化如何與各種原子操作互動的一些例子：

·        Memcpyopt：一個原子操作不能被優化為一個memcpy/memset的部分，包括unordered的讀寫。它可以将操作拖過某些原子操作。

·        LICM：Unordered讀寫可以移出一個循環。它僅是将Monotonic操作處理作對一個記憶體位置的讀+寫，任何比這嚴格的處理作一個非異常抛出調用。

·        DSE（死寫消除，dead store elimination）：Unordered寫可以像普通寫那樣處理。在某些情形下，Monotonic寫也可以DSE掉，但推理是微妙的，且不是特别重要。在某些情形下，DSE跨過一個更強的原子操作工作是可能的，但它相當棘手。DSE将這個推理委托給MemoryDependencyAnalysis（這被其他遍像GVN使用）。

·        折疊一個讀：任何來自一個全局常量的原子讀可以被常量折疊，因為它不能被觀察到。類似的推理允許對原子讀寫進行sroa（ScalarReplacement Of Aggregates，聚集類型的标量替換）。

在SelectionDAG中原子操作以ATOMIC_* 操作碼來表示。在對所有原子定序（ordering）使用屏障指令的架構上（像ARM），如果使用了setInsertFencesForAtomic()，合适的fence可以由Codegen遍AtomicExpand釋出。

所有原子操作的MachineMemOperand目前被标記為volatile；就IR的volatile觀念，這是不正确的，但CodeGen保守地處理任何标記為volatile的東西。在将來某個時候，這會得到修正。

原子操作的一個非常重要的屬性是，如果你的後端支援任何一個給定尺寸的内聯無鎖原子操作，你應該以一個無鎖的方式支援該尺寸的所有操作。

當目标機器實作原子化cmpxchg或LL/SC指令（像大多數那樣）時，這是無足輕重的：所有其他操作可以在這些原語之上實作。不過，在許多舊的CPU上（比如ARMv5，SparcV8，Intel80386），有原子化的讀寫指令，但沒有cmpxchg或LL/SC。盡管使用原生指令實作原子化讀是無效的，但使用一個使用mutex的函數的庫調用的cmpxchg是有效的，原子讀也必須在這樣的架構上擴充為一個庫調用，是以通過使用同一個mutex，就一個同步的cmpxchg而言，它可以保持原子性。

AtomicExpandPass可以對此有幫助：它将所有超過setMaxAtomicSizeInBitsSupported設定最大值（預設為0）的任何尺寸的原子操作展開為合适的__atomic_*libcall。

在x86上，所有原子讀産生一個MOV。SequentiallyConsistent寫産生一個XCHG，其他寫産生一個MOV。SequentiallyConsistentfence産生一個MFENCE，其他fence不會産生任何代碼。Cmpxchg使用LOCKCMPXCHG指令。atomicrmw xchg使用XCHG，atomicrmw add與atomicrmw sub 使用XADD，所有其他atomicrmw操作産生一個帶有LOCKCMPXCHG的循環。依賴于結果的使用者，某些atomicrmw操作可以被轉換為像LOCKAND的操作，但這通常不能奏效。

在ARM（v8以前），MIPS以及許多其他RISC架構上，Acquire，Release與SequentiallyConsistent語義對每個這樣的操作要求屏障指令。讀與寫産生普通的指令。cmpxchg與atomicrmw可以使用一個帶有在緩存線上擷取某種互斥鎖的LL/SC形式指令（ARM上的LDREX與STRE等）的循環來代表。

後端使用AtomicExpandPass來降級某些原子構造通常是最簡單的。以下是一些它可以做的降級：

·        Cmpxchg：通過重載的shouldExpandAtomicCmpXchgInIR()，emitLoadLinked()，emitStoreConditional()，降級到帶有load-linked（ll）/ store-conditional（sc）的循環。

·        大的 loads/stores ：通過重載overriding shouldExpandAtomicStoreInIR()，shouldExpandAtomicLoadInIR()，降級到ll-sc/cmpxchg。

·        強原子通路：通過重載shouldInsertFencesForAtomic()，emitLeadingFence()，emitTrailingFence()，降級為monotonic通路+fences

·        原子rmw：通過重載overriding expandAtomicRMWInIR()，降級到帶有cmpxchg或load-linked（ll）/store-conditional（SC）的循環

·        對于不支援的尺寸擴充為__atomic_* libcalls。

所有這些的例子，查閱ARM後端。

有兩種原子庫調用由LLVM産生。請注意這兩組庫函數有點混淆地與clang定義的固有函數共享名字。盡管這樣，這些庫函數與這些固有函數不是直接關聯的：__atomic_*固有函數不是降級到__atomic_*庫調用，__sync_*固有函數也不是降級到__sync_*庫調用。

LLVM的AtomicExpandPass将資料大小超過MaxAtomicSizeInBitsSupported的原子操作轉換為對這些函數的調用。

有4個通用函數，可以任意尺寸或對齊的資料調用它們：

void__atomic_load(size_t size, void *ptr, void *ret, int ordering)

void__atomic_store(size_t size, void *ptr, void *val, int ordering)

void__atomic_exchange(size_t size, void *ptr, void *val, void *ret, int ordering)

bool __atomic_compare_exchange(size_t size, void *ptr, void *expected, void *desired, int success_order, int failure_order)

上面函數也有特定的版本，它們僅能與合适尺寸的自然對齊指針一起使用。在下面的署名裡，N是1，2，4，8之一，iN是該尺寸的合适的整數類型；如果不存在這樣的整數類型，不能使用這個專用函數：

iN__atomic_load_N(iN *ptr, iN val, int ordering)

void__atomic_store_N(iN *ptr, iN val, int ordering)

iN__atomic_exchange_N(iN *ptr, iN val, int ordering)

bool __atomic_compare_exchange_N(iN *ptr, iN *expected, iN desired, int success_order, int failure_order)

最後，存在一些讀-修改-寫函數，它們僅有指定尺寸的版本可用（其他的尺寸使用一個_atomic_compare_exchange循環）：

iN__atomic_fetch_add_N(iN *ptr, iN val, int ordering)

iN__atomic_fetch_sub_N(iN *ptr, iN val, int ordering)

iN__atomic_fetch_and_N(iN *ptr, iN val, int ordering)

iN__atomic_fetch_or_N(iN *ptr, iN val, int ordering)

iN__atomic_fetch_xor_N(iN *ptr, iN val, int ordering)

iN__atomic_fetch_nand_N(iN *ptr, iN val, int ordering)

這組庫函數有一些需要注意的，有趣的實作要求：

·        它們支援所有的尺寸與對齊——包括在任何現存硬體上不能自然實作的那些。是以，它們将肯定對某些尺寸、對齊使用互斥量。

·        結果，它們不能在一個靜态連結的編譯器支援庫中釋出，因為它們具有必須在程式載入的所有DSO中共享的狀态。它們必須提供為一個所有對象使用的共享庫。

·        支援無鎖的原子化尺寸的集合必須是任何編譯器能釋出的大小集合的一個超集。即：如果一個新編譯器引入對尺寸N的内聯無鎖原子操作的支援，__atomic_*函數也必須對尺寸N有一個無鎖實作。

·        這個要求使得由舊編譯器産生的代碼（将調用__atomic_*函數）與新編譯器生成的代碼（将使用原生原子操作指令）可以互動。

注意，通過使用編譯器原子操作内置函數，實作在所支援大小，自然對齊的指針上的操作，否則通過一個通用的互斥量的實作，來編寫這些庫函數的一個完全目标機器無關的實作是可能的。

某些目标機器或OS/目标機器組合可以支援無鎖原子操作，但出于各種原因，釋出内聯指令是不現實的。

這有兩個典型的例子。

有些CPU支援可以在函數調用邊界來回切換的多個指令集。例如，MIPS支援MPIS16ISA，它具有比MIPS32ISA更小的指令編碼。類似的，ARM具有ThumbISA。在MPIS16以及Thumb的更早版本，原子操作指令是不可編碼的。不過，這些指令通過對一個帶有更長編碼的函數的調用可用。

在這些情形裡，LLVM中的Target可以宣稱支援一個合适大小的原子操作，然後通過對__sync__*函數的libcall實作這些操作的某些子集。這樣的函數在它們的實作裡不能使用鎖，因為不像由AtomicExpandPass使用的__atomic__*例程，通過目标機器降級，它們可能與原生指令混合-及-比對（mixed-and-matched）。

另外，這些例程不需要共享，因為它們是無狀态的。是以，在一個庫裡包含多個拷貝沒有問題。是以，這些例程通常由靜态連結的編譯器運作時支援庫實作。

LLVM将釋出對一個合适__sync_*例程的調用，如果目标機器IselLowering代碼将對應的ATOMIC_CMPXCHG，ATOMIC_SWAP，或ATOMIC_LOAD_*操作設定為“展開”，而且如果它已經通過對initSyncLibcalls的一個調用選擇這些庫函數。

可以由LLVM調用的完整的函數集是（N是1，2，4，8或16）：

iN__sync_val_compare_and_swap_N(iN *ptr, iN expected, iN desired)

iN__sync_lock_test_and_set_N(iN *ptr, iN val)

iN__sync_fetch_and_add_N(iN *ptr, iN val)

iN__sync_fetch_and_sub_N(iN *ptr, iN val)

iN__sync_fetch_and_and_N(iN *ptr, iN val)

iN__sync_fetch_and_or_N(iN *ptr, iN val)

iN__sync_fetch_and_xor_N(iN *ptr, iN val)

iN__sync_fetch_and_nand_N(iN *ptr, iN val)

iN__sync_fetch_and_max_N(iN *ptr, iN val)

iN__sync_fetch_and_umax_N(iN *ptr, iN val)

iN__sync_fetch_and_min_N(iN *ptr, iN val)

iN__sync_fetch_and_umin_N(iN *ptr, iN val)

這個清單不包括任何原子讀寫函數；所有已知的架構直接支援原子讀寫（可能通過在一個普通讀寫的一邊釋出一個栅欄）。

某種程度上還有獨立地降級ATOMIC_FENCE為 __sync_synchronize()的可能性。這發生與否與上面無關，完全由setOperationAction(ISD::ATOMIC_FENCE, ...)控制。