常被誤解的 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. 註 1 的證據是注意到 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 位元），並且最佳化器實際上會在大多數情況下將 i64 算術縮小到不支援 64 位元算術的目標上的實際指標大小。但是，在某些情況下，它不會這樣做。使用 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 基於類型的別名分析傳遞使用元資料來描述不同的類型系統（例如 C 類型系統），並在此基礎上執行基於類型的別名。更多詳細資訊請參閱語言參考。

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

如果 GEP 缺少 inbounds 關鍵字，則該值是評估隱含的二補數整數計算的結果。但是，由於無法保證物件將在位址空間中的哪個位置分配，因此這些值的意義有限。

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

因此，這對 inbounds 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 降低為更原始的整數表達式來對 GEP 進行運算，這允許它們與其他整數表達式組合和/或拆分為多個單獨的整數表達式。如果它們進行了非瑣碎的更改，則轉換回 LLVM IR 可能涉及逆向工程定址結構，以便使其適合原始第一個運算元的靜態類型。並非總是能夠完全重建此結構；有時底層定址與靜態類型完全不對應。在這種情況下，最佳化器將改為發出一個 GEP，其中基底指標轉換為簡單的位址單位指標，並使用名稱 “uglygep”。這不太美觀，但它同樣有效，並且足以保留 GEP 提供的指標別名保證。

摘要

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

  1. GEP 指令永遠不會存取記憶體，它僅提供指標計算。

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

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

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

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