容易被誤解的 GEP 指令

簡介

本文旨在消除圍繞 LLVM 的 GetElementPtr (GEP) 指令的神秘和困惑。關於 GEP 指令的問題可能是開發人員開始使用 LLVM 編碼後最常遇到的問題。在這裡，我們將說明困惑的根源，並說明 GEP 指令實際上非常簡單。

地址計算

當人們第一次接觸到 GEP 指令時，他們往往會將其與其他程式設計範例中的已知概念聯繫起來，最顯著的是 C 陣列索引和欄位選擇。GEP 與 C 陣列索引和欄位選擇非常相似，但略有不同，這導致了以下問題。

GEP 指令的第一個索引是什麼？

簡短的答案是：遍歷第二個運算元的索引。

對第一個索引的困惑通常源於將 GetElementPtr 指令想像成 C 索引運算符。它們並不相同。例如，當我們在“C”中編寫時

AType *Foo;
...
X = &Foo->F;

很自然地會認為只有一個索引，即欄位 F 的選擇。然而，在此範例中，Foo 是一個指標。該指標在 LLVM 中必須明確索引。另一方面，C 語言會透明地對其進行索引。若要到達與 C 語言程式碼相同的地址位置，您需要為 GEP 指令提供兩個索引運算元。第一個運算元透過指標進行索引；第二個運算元索引結構的欄位 F，就像您撰寫以下程式碼一樣

X = &Foo[0].F;

有時這個問題會被改寫為

為什麼可以透過第一個指標進行索引，但後續的指標不會被解引用？

答案很簡單，因為不需要存取記憶體即可執行計算。GEP 指令的第二個運算元必須是指標類型的值。指標的值會直接作為運算元提供給 GEP 指令，而不需要存取記憶體。因此，它必須被索引並需要一個索引運算元。請參考以下範例

struct munger_struct {
  int f1;
  int f2;
};
void munge(struct munger_struct *P) {
  P[0].f1 = P[1].f1 + P[2].f2;
}
...
struct munger_struct Array[3];
...
munge(Array);

在此「C」範例中，前端編譯器 (Clang) 將為賦值語句中透過「P」的三個索引產生三個 GEP 指令。函數引數 P 將會是這些 GEP 指令中每一個的第二個運算元。第三個運算元透過該指標進行索引。第四個運算元將是 struct munger_struct 類型的欄位偏移量，適用於 f1 或 f2 欄位。因此，在 LLVM 組合語言中，munge 函數看起來像這樣

define void @munge(ptr %P) {
entry:
  %tmp = getelementptr %struct.munger_struct, ptr %P, i32 1, i32 0
  %tmp1 = load i32, ptr %tmp
  %tmp2 = getelementptr %struct.munger_struct, ptr %P, i32 2, i32 1
  %tmp3 = load i32, ptr %tmp2
  %tmp4 = add i32 %tmp3, %tmp1
  %tmp5 = getelementptr %struct.munger_struct, ptr %P, i32 0, i32 0
  store i32 %tmp4, ptr %tmp5
  ret void
}

在每種情況下，第二個運算元都是 GEP 指令開始執行的指標。無論第二個運算元是引數、已配置的記憶體還是全域變數，都是如此。

為了更清楚地說明這一點，讓我們考慮一個更難懂的範例

@MyVar = external global i32
...
%idx1 = getelementptr i32, ptr @MyVar, i64 0
%idx2 = getelementptr i32, ptr @MyVar, i64 1
%idx3 = getelementptr i32, ptr @MyVar, i64 2

這些 GEP 指令只是根據 MyVar 的基底地址進行地址計算。它們的計算方式如下（使用 C 語法）

idx1 = (char*) &MyVar + 0
idx2 = (char*) &MyVar + 4
idx3 = (char*) &MyVar + 8

由於已知 i32 類型長度為四個位元組，因此索引 0、1 和 2 分別轉換為記憶體偏移量 0、4 和 8。由於 @MyVar 的地址直接傳遞給 GEP 指令，因此不需要存取記憶體即可進行這些計算。

此範例中難懂的部分在於 %idx2 和 %idx3 的情況。它們會導致計算出指向 @MyVar 全域變數結尾之後的記憶體的地址，該變數只有一個 i32 長，而不是三個 i32 長。雖然這在 LLVM 中是合法的，但並不建議這樣做，因為任何使用這些 GEP 指令產生的指標進行載入或儲存的操作都會觸發未定義行為 (UB)。

為什麼需要額外的 0 索引？

簡短的回答是：沒有多餘的索引。

當 GEP 指令應用於始終是指標類型的全域變數時，最常出現這個問題。例如，請參考以下範例

%MyStruct = external global { ptr, i32 }
...
%idx = getelementptr { ptr, i32 }, ptr %MyStruct, i64 0, i32 1

上述 GEP 通過索引結構 %MyStruct 的 i32 類型欄位產生一個 ptr。當人們第一次看到它時，他們會想知道為什麼需要 i64 0 索引。然而，仔細觀察全局變數和 GEP 的工作原理就會發現其必要性。了解以下事實將消除這種困惑

  1. %MyStruct 的類型*不是* { ptr, i32 } 而是 ptr。也就是說，%MyStruct 是一個指向結構的指標，而不是結構本身。

  2. 通過觀察 GEP 指令的第二個操作數（%MyStruct）的類型為 ptr 可以證明第一點。

  3. 第一個索引 i64 0 是必需的，用於跳過全局變數 %MyStruct。由於 GEP 指令的第二個參數必須始終是指標類型的值，因此第一個索引會遍歷該指標。值 0 表示從該指標偏移 0 個元素。

  4. 第二個索引 i32 1 選擇結構的第二個欄位（i32）。

GEP 解引用了什麼？

簡短的答案：沒有。

GetElementPtr 指令不會解引用任何內容。也就是說，它不會以任何方式訪問記憶體。這就是 Load 和 Store 指令的用途。GEP 僅參與地址的計算。例如，請考慮以下內容

@MyVar = external global { i32, ptr }
...
%idx = getelementptr { i32, ptr }, ptr @MyVar, i64 0, i32 1
%arr = load ptr, ptr %idx
%idx = getelementptr [40 x i32], ptr %arr, i64 0, i64 17

在本例中，我們有一個全局變數 @MyVar，它是一個指向包含指標的結構的指標。假設這個內部指標指向一個類型為 [40 x i32] 的陣列。上述 IR 將首先計算內部指標的地址，然後載入該指標，然後計算第 18 個陣列元素的地址。

這不能用單個 GEP 指令表示，因為它需要在中間進行記憶體解引用。但是，以下示例可以正常工作

@MyVar = external global { i32, [40 x i32 ] }
...
%idx = getelementptr { i32, [40 x i32] }, ptr @MyVar, i64 0, i32 1, i64 17

在這種情況下，結構不包含指標，GEP 指令可以通過全局變數索引，進入結構的第二個欄位並訪問那裡的第 18 個 i32。

為什麼 GEP x,0,0,1 和 GEP x,1 不會發生別名？

簡短的答案：它們計算不同的地址位置。

如果您查看這些 GEP 指令中的第一個索引，您會發現它們不同（0 和 1），因此地址計算會隨著該索引而不同。考慮以下示例

@MyVar = external global { [10 x i32] }
%idx1 = getelementptr { [10 x i32] }, ptr @MyVar, i64 0, i32 0, i64 1
%idx2 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1

在此示例中，idx1 計算 @MyVar 中結構體中第二個整數的地址，即 MyVar+4。但是，idx2 計算 @MyVar 之後*下一個*結構體的地址，即 MyVar+40，因為它索引了 MyVar 中十個 4 位元組整數之後的位置。顯然，在這種情況下，指標不會發生別名。

為什麼 GEP x,1,0,0 和 GEP x,1 會發生別名？

簡答：它們計算相同的地址位置。

這兩條 GEP 指令會計算相同的地址，因為通過第 0 個元素索引不會改變地址。請考慮以下示例

@MyVar = global { [10 x i32] }
%idx1 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1, i32 0, i64 0
%idx2 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1

在此示例中，%idx1 的值為 MyVar+40，%idx2 的值也為 MyVar+40。

GEP 可以索引向量元素嗎？

這並非一直都被強制禁止，儘管不推薦這樣做。這會導致最佳化器出現尷尬的特殊情況，並且 IR 中存在根本性的不一致。將來，它可能會被徹底禁止。

位址空間對 GEP 有什麼影響？

沒有影響，除了第二個運算元指標類型上的位址空間限定詞始終與結果類型上的位址空間限定詞相符。

GEP 與 ptrtoint、算術運算和 inttoptr 有什麼不同？

它們非常相似；只有一些細微的差異。

使用 ptrtoint 時，您必須選擇一種整數類型。一種方法是選擇 i64；這在 LLVM 支援的所有平台上都是安全的（LLVM 在內部許多地方假設指標永遠不會超過 64 位元），並且在目標平台不支援 64 位元算術運算的情況下，最佳化器實際上會將 i64 算術運算縮小到實際的指標大小。但是，在某些情況下，它不會這樣做。使用 GEP 可以避免這個問題。

此外，GEP 帶有額外的指標別名規則。從一個物件獲取 GEP，將地址指向另一個單獨分配的物件，然後對其進行解引用是無效的。IR 生產者（前端）必須遵循此規則，而消費者（最佳化器，特別是指標別名分析）則受益於能夠依賴此規則。有關更多資訊，請參閱規則章節。

而且，GEP 在常見情況下更簡潔。

但是，對於隱含的底層整數計算，它們之間沒有區別。

我正在為需要自訂 GEP 降低的目標平台編寫後端。我該怎麼做？

您不需要這樣做。GEP 隱含的整數計算與目標平台無關。通常，您需要做的是讓後端模式匹配涉及 ADD、MUL 等的表達式樹，這些表達式樹是 GEP 被降低成的目標。這樣做的好處是，您的程式碼可以在更多情況下正常工作。

GEP 確實使用目標平台相關的參數來表示資料類型的大小和佈局，目標平台可以自訂這些參數。

如果您需要支援非 8 位元的定址單元，則需要修復後端中的大量程式碼，而 GEP 降低只是整個過程中的一小部分。

VLA 位址與 GEP 的運作方式

GEP 本身不支援 VLA。LLVM 的類型系統完全是靜態的，而 GEP 位址計算則是由 LLVM 類型所引導。

VLA 索引可以實作為線性化索引。舉例來說，像 X[a][b][c] 這樣的表達式，必須有效地降級為 X[a*m+b*n+c] 的形式，以便 GEP 將其視為單一維度的陣列參考。

這意味著，如果您想編寫一個能理解陣列索引並支援 VLA 的分析程式，您的程式碼必須準備好反向工程線性化過程。解決這個問題的一種方法是使用 ScalarEvolution 函式庫，它始終以相同的方式呈現 VLA 和非 VLA 索引。

規則

如果陣列索引超出範圍會發生什麼事？

陣列索引超出範圍有兩種情況。

首先，陣列類型來自 GEP 第一個運算元的（靜態）類型。大於對應靜態陣列類型中元素數量的索引是有效的。在這個意義上，超出範圍的索引沒有問題。索引到陣列只取決於陣列元素的大小，而不是元素的數量。

一個常見的例子是大小未知的陣列。通常使用長度為零的陣列類型來表示這些陣列。靜態類型表示有零個元素的事實並不重要；計算任意元素索引是完全有效的，因為計算只取決於陣列元素的大小，而不是元素的數量。請注意，零大小的陣列在這裡不是特例。

這種情況與 inbounds 關鍵字無關。inbounds 關鍵字旨在描述低階指標算術溢位條件，而不是高階陣列索引規則。

希望理解陣列索引的分析過程不應假設靜態陣列類型範圍受到尊重。

超出範圍的第二種情況是計算的位址超出了實際底層配置的物件。

使用 inbounds 關鍵字時，如果位址超出實際底層配置的物件且不是超出末尾一個位置的位址，則 GEP 的結果值為 poison。

如果沒有 inbounds 關鍵字，則對計算超出範圍的位址沒有任何限制。顯然，執行載入或儲存操作需要已配置且對齊足夠的記憶體位址。但 GEP 本身只關心計算位址。

陣列索引可以是負數嗎？

可以。這基本上是陣列索引超出範圍的特例。

我可以比較兩個使用 GEP 計算的值嗎？

可以。如果兩個位址都在同一個配置的物件內，或者其中一個超出末尾一個位置，您將得到預期的比較結果。如果其中一個在物件外部，可能會發生整數算術環繞，因此比較結果可能沒有意義。

我可以使用與底層物件類型不同的指標類型來執行 GEP 嗎？

可以。將指針值位元轉換為任意指針類型沒有任何限制。 GEP 中的類型僅用於定義底層整數計算的參數。它們不需要與底層物件的實際類型相符。

此外，載入和存放不需要使用與底層物件類型相同的類型。在此上下文中，類型僅用於指定記憶體大小和對齊方式。除此之外，它們只是對優化器的提示，指示該值可能會如何使用。

我可以將物件的地址轉換為整數並將其添加到 null 嗎？

您可以透過這種方式計算地址，但如果您使用 GEP 進行加法運算，則不能使用該指針實際存取物件，除非該物件是在 LLVM 之外管理的。

底層的整數計算已充分定義；null 具有定義的值 — 零 — 您可以將任何想要的值添加到其中。

但是，使用此類指針存取（從中載入或儲存到）LLVM 感知的物件是無效的。這包括 GlobalVariables、Allocas 以及由 noalias 指針指向的物件。

如果您真的需要此功能，可以使用顯式整數指令進行算術運算，並使用 inttoptr 將結果轉換為地址。大多數 GEP 的特殊別名規則不適用於從 ptrtoint、算術和 inttoptr 序列計算的指針。

我可以計算兩個物件之間的距離，並將該值添加到一個地址以計算另一個地址嗎？

與對 null 進行算術運算一樣，您可以使用 GEP 透過這種方式計算地址，但如果這樣做，則不能使用該指針實際存取物件，除非該物件是在 LLVM 之外管理的。

同樣如上所述，ptrtoint 和 inttoptr 提供了另一種方法來執行此操作，而沒有此限制。

我可以對 LLVM IR 執行基於類型的別名分析嗎？

您無法使用 LLVM 的內建類型系統執行基於類型的別名分析，因為 LLVM 對在定址、載入或存放中混合類型沒有任何限制。

LLVM 的基於類型的別名分析 pass 使用中繼資料來描述不同的類型系統（例如 C 類型系統），並在此基礎上執行基於類型的別名分析。更多詳細資訊請參閱語言參考。

如果 GEP 計算溢位會發生什麼情況？

如果 GEP 缺少 inbounds 關鍵字，則該值是評估隱含的二進制補碼整數計算的結果。但是，由於無法保證物件將在地址空間中的何處分配，因此此類值的意義有限。

如果 GEP 具有 inbounds 關鍵字，則如果 GEP 溢位（即環繞地址空間的末尾），則結果值為 poison。

因此，對於入站 GEP 來說，這會產生一些後果：陣列/向量/指標索引所暗示的比例總是已知為“nsw”，因為它們是由元素大小縮放的有符號值。這些值也允許為負數（例如“gep i32, ptr %P, i32 -1”），但指標本身在邏輯上被視為無符號值。這表示 GEP 在指標基址（被視為無符號）和應用於它的偏移量（被視為有符號）之間具有不對稱關係。偏移量計算中加法的結果不能有符號溢位，但當應用於基址指標時，可能會發生符號溢位。

如何判斷我的前端是否符合規則？

目前沒有針對 getelementptr 規則的檢查器。當前，執行此操作的唯一方法是手動檢查前端中建立 GetElementPtr 運算符的每個位置。

無法編寫可以靜態找到所有違規行為的檢查器。可以編寫一個檢查器，通過使用動態檢查來檢測程式碼來工作。或者，可以編寫一個靜態檢查器來捕捉可能的子問題集。但是，目前不存在這樣的檢查器。

基本原理

為什麼 GEP 要這樣設計？

GEP 的設計具有以下目標，按非官方的大致優先順序排列：

  • 支援 C 語言、類 C 語言以及可以概念上降低為 C 語言的語言（這涵蓋了很多）。

  • 支援 C 編譯器中常見的最佳化。特別是，GEP 是 LLVM 指標別名模型 的基石。

  • 提供一種一致的地址計算方法，以便地址計算不需要成為 IR 中加載和存儲指令的一部分。

  • 支援非類 C 語言，只要它不干擾其他目標。

  • 最大程度地減少 IR 中特定於目標的資訊。

為什麼結構成員索引始終使用 i32？

特定的類型 i32 可能只是一個歷史文物，但是它對於所有實際目的來說都足夠寬，因此沒有必要更改它。它不一定意味著 i32 地址算術；它只是一個標識符，用於標識結構中的欄位。要求所有結構索引都相同減少了兩個 GEP 實際上相同但具有不同操作數類型的可能性範圍。

什麼是 uglygep？

某些 LLVM 優化器會透過將 GEP 內部降低為更原始的整數運算式來對其進行操作，這使得它們能夠與其他整數運算式組合和/或拆分為多個獨立的整數運算式。 如果它們進行了非平凡的更改，則轉換回 LLVM IR 可能涉及對尋址結構進行逆向工程，以便使其符合原始第一個運算元的靜態類型。 並非總是能夠完全重建此結構；有時底層尋址根本與靜態類型不符。 在這種情況下，優化器將發出一個 GEP，其基址指標轉換為簡單的地址單元指標，並使用名稱“uglygep”。 這並不漂亮，但它同樣有效，並且足以保留 GEP 提供的指標別名保證。

總結

總之，以下是一些關於 GetElementPtr 指令始終需要記住的事項

  1. GEP 指令從不訪問記憶體，它只提供指標計算。

  2. GEP 指令的第二個運算元始終是指標，並且必須被索引。

  3. GEP 指令沒有多餘的索引。

  4. 尾隨零索引對於指標別名來說是多餘的，但對於指標的類型則不然。

  5. 前導零索引對於指標別名和指標的類型都不是多餘的。