From 3277b69d734b9c90b44ebde4ede005717e2c3b2e Mon Sep 17 00:00:00 2001 From: ed Date: Tue, 2 Jun 2009 17:52:33 +0000 Subject: Import LLVM, at r72732. --- docs/GetElementPtr.html | 370 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 370 insertions(+) create mode 100644 docs/GetElementPtr.html (limited to 'docs/GetElementPtr.html') diff --git a/docs/GetElementPtr.html b/docs/GetElementPtr.html new file mode 100644 index 0000000..f4b096a --- /dev/null +++ b/docs/GetElementPtr.html @@ -0,0 +1,370 @@ + + + + + The Often Misunderstood GEP Instruction + + + + + +
+ The Often Misunderstood GEP Instruction +
+ +
    +
  1. Introduction
    2. +
  2. The Questions +
      +
    1. Why is the extra 0 index required?
      2. +
    2. What is dereferenced by GEP?
      3. +
    3. Why can you index through the first pointer but not + subsequent ones?
      4. +
    4. Why don't GEP x,0,0,1 and GEP x,1 alias?
      5. +
    5. Why do GEP x,1,0,0 and GEP x,1 alias?
      6. +
    3. +
  3. Summary
    4. +
+ +
+

Written by: Reid Spencer.

+
+ + + +
Introduction
+ +
+

This document seeks to dispel the mystery and confusion surrounding LLVM's + GetElementPtr (GEP) instruction. Questions about the wiley GEP instruction are + probably the most frequently occuring questions once a developer gets down to + coding with LLVM. Here we lay out the sources of confusion and show that the + GEP instruction is really quite simple. +

+
+ + +
The Questions
+ +
+

When people are first confronted with the GEP instruction, they tend to + relate it to known concepts from other programming paradigms, most notably C + array indexing and field selection. However, GEP is a little different and + this leads to the following questions; all of which are answered in the + following sections.

+
    +
  1. What is the first index of the GEP instruction? +
    2. +
  2. Why is the extra 0 index required?
    3. +
  3. What is dereferenced by GEP?
    4. +
  4. Why don't GEP x,0,0,1 and GEP x,1 alias?
    5. +
  5. Why do GEP x,1,0,0 and GEP x,1 alias?
    6. +
+
+ + +
+ What is the first index of the GEP instruction? +
+
+

Quick answer: The index stepping through the first operand.

+

The confusion with the first index usually arises from thinking about + the GetElementPtr instruction as if it was a C index operator. They aren't the + same. For example, when we write, in "C":

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

it is natural to think that there is only one index, the selection of the + field F. However, in this example, Foo is a pointer. That + pointer must be indexed explicitly in LLVM. C, on the other hand, indexs + through it transparently. To arrive at the same address location as the C + code, you would provide the GEP instruction with two index operands. The + first operand indexes through the pointer; the second operand indexes the + field F of the structure, just as if you wrote:

+ +
+
+X = &Foo[0].F;
+
+
+ +

Sometimes this question gets rephrased as:

+

Why is it okay to index through the first pointer, but + subsequent pointers won't be dereferenced?

+

The answer is simply because memory does not have to be accessed to + perform the computation. The first operand to the GEP instruction must be a + value of a pointer type. The value of the pointer is provided directly to + the GEP instruction as an operand without any need for accessing memory. It + must, therefore be indexed and requires an index operand. Consider this + example:

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

In this "C" example, the front end compiler (llvm-gcc) will generate three + GEP instructions for the three indices through "P" in the assignment + statement. The function argument P will be the first operand of each + of these GEP instructions. The second operand indexes through that pointer. + The third operand will be the field offset into the + struct munger_struct type, for either the f1 or + f2 field. So, in LLVM assembly the munge function looks + like:

+ +
+
+void %munge(%struct.munger_struct* %P) {
+entry:
+  %tmp = getelementptr %struct.munger_struct* %P, i32 1, i32 0
+  %tmp = load i32* %tmp
+  %tmp6 = getelementptr %struct.munger_struct* %P, i32 2, i32 1
+  %tmp7 = load i32* %tmp6
+  %tmp8 = add i32 %tmp7, %tmp
+  %tmp9 = getelementptr %struct.munger_struct* %P, i32 0, i32 0
+  store i32 %tmp8, i32* %tmp9
+  ret void
+}
+
+
+ +

In each case the first operand is the pointer through which the GEP + instruction starts. The same is true whether the first operand is an + argument, allocated memory, or a global variable.

+

To make this clear, let's consider a more obtuse example:

+ +
+
+%MyVar = unintialized global i32
+...
+%idx1 = getelementptr i32* %MyVar, i64 0
+%idx2 = getelementptr i32* %MyVar, i64 1
+%idx3 = getelementptr i32* %MyVar, i64 2
+
+
+ +

These GEP instructions are simply making address computations from the + base address of MyVar. They compute, as follows (using C syntax): +

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

Since the type i32 is known to be four bytes long, the indices + 0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No + memory is accessed to make these computations because the address of + %MyVar is passed directly to the GEP instructions.

+

The obtuse part of this example is in the cases of %idx2 and + %idx3. They result in the computation of addresses that point to + memory past the end of the %MyVar global, which is only one + i32 long, not three i32s long. While this is legal in LLVM, + it is inadvisable because any load or store with the pointer that results + from these GEP instructions would produce undefined results.

+
+ + +
+ Why is the extra 0 index required? +
+ +
+

Quick answer: there are no superfluous indices.

+

This question arises most often when the GEP instruction is applied to a + global variable which is always a pointer type. For example, consider + this:

+ +
+
+%MyStruct = uninitialized global { float*, i32 }
+...
+%idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1
+
+
+ +

The GEP above yields an i32* by indexing the i32 typed + field of the structure %MyStruct. When people first look at it, they + wonder why the i64 0 index is needed. However, a closer inspection + of how globals and GEPs work reveals the need. Becoming aware of the following + facts will dispell the confusion:

+
    +
  1. The type of %MyStruct is not { float*, i32 } + but rather { float*, i32 }*. That is, %MyStruct is a + pointer to a structure containing a pointer to a float and an + i32.
    2. +
  2. Point #1 is evidenced by noticing the type of the first operand of + the GEP instruction (%MyStruct) which is + { float*, i32 }*.
    3. +
  3. The first index, i64 0 is required to step over the global + variable %MyStruct. Since the first argument to the GEP + instruction must always be a value of pointer type, the first index + steps through that pointer. A value of 0 means 0 elements offset from that + pointer.
    4. +
  4. The second index, i32 1 selects the second field of the + structure (the i32).
    5. +
+
+ + +
+ What is dereferenced by GEP? +
+
+

Quick answer: nothing.

+

The GetElementPtr instruction dereferences nothing. That is, it doesn't + access memory in any way. That's what the Load and Store instructions are for. + GEP is only involved in the computation of addresses. For example, consider + this:

+ +
+
+%MyVar = uninitialized global { [40 x i32 ]* }
+...
+%idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17
+
+
+ +

In this example, we have a global variable, %MyVar that is a + pointer to a structure containing a pointer to an array of 40 ints. The + GEP instruction seems to be accessing the 18th integer of the structure's + array of ints. However, this is actually an illegal GEP instruction. It + won't compile. The reason is that the pointer in the structure must + be dereferenced in order to index into the array of 40 ints. Since the + GEP instruction never accesses memory, it is illegal.

+

In order to access the 18th integer in the array, you would need to do the + following:

+ +
+
+%idx = getelementptr { [40 x i32]* }* %, i64 0, i32 0
+%arr = load [40 x i32]** %idx
+%idx = getelementptr [40 x i32]* %arr, i64 0, i64 17
+
+
+ +

In this case, we have to load the pointer in the structure with a load + instruction before we can index into the array. If the example was changed + to:

+ +
+
+%MyVar = uninitialized global { [40 x i32 ] }
+...
+%idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17
+
+
+ +

then everything works fine. In this case, the structure does not contain a + pointer and the GEP instruction can index through the global variable, + into the first field of the structure and access the 18th i32 in the + array there.

+
+ + +
+ Why don't GEP x,0,0,1 and GEP x,1 alias? +
+
+

Quick Answer: They compute different address locations.

+

If you look at the first indices in these GEP + instructions you find that they are different (0 and 1), therefore the address + computation diverges with that index. Consider this example:

+ +
+
+%MyVar = global { [10 x i32 ] }
+%idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 0, i32 0, i64 1
+%idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1
+
+
+ +

In this example, idx1 computes the address of the second integer + in the array that is in the structure in %MyVar, that is MyVar+4. The + type of idx1 is i32*. However, idx2 computes the + address of the next structure after %MyVar. The type of + idx2 is { [10 x i32] }* and its value is equivalent + to MyVar + 40 because it indexes past the ten 4-byte integers + in MyVar. Obviously, in such a situation, the pointers don't + alias.

+
+ + +
+ Why do GEP x,1,0,0 and GEP x,1 alias? +
+
+

Quick Answer: They compute the same address location.

+

These two GEP instructions will compute the same address because indexing + through the 0th element does not change the address. However, it does change + the type. Consider this example:

+ +
+
+%MyVar = global { [10 x i32 ] }
+%idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
+%idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1
+
+
+ +

In this example, the value of %idx1 is %MyVar+40 and + its type is i32*. The value of %idx2 is also + MyVar+40 but its type is { [10 x i32] }*.

+
+ + +
Summary
+ + +
+

In summary, here's some things to always remember about the GetElementPtr + instruction:

+
    +
  1. The GEP instruction never accesses memory, it only provides pointer + computations.
    2. +
  2. The first operand to the GEP instruction is always a pointer and it must + be indexed.
    3. +
  3. There are no superfluous indices for the GEP instruction.
    4. +
  4. Trailing zero indices are superfluous for pointer aliasing, but not for + the types of the pointers.
    5. +
  5. Leading zero indices are not superfluous for pointer aliasing nor the + types of the pointers.
    6. +
+
+ + + +
+
+ Valid CSS + Valid HTML 4.01 + The LLVM Compiler Infrastructure
+ Last modified: $Date: 2008-12-11 19:23:24 +0100 (Thu, 11 Dec 2008) $ +
+ + -- cgit v1.1