<ol>
<li><a href="#intro">Introduction</a></li>
- <li><a href="#questions">The Questions</a>
+ <li><a href="#addresses">Address Computation</a>
<ol>
<li><a href="#extra_index">Why is the extra 0 index required?</a></li>
<li><a href="#deref">What is dereferenced by GEP?</a></li>
subsequent ones?</a></li>
<li><a href="#lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
<li><a href="#trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
+ <li><a href="#vectors">Can GEP index into vector elements?</a>
+ <li><a href="#unions">Can GEP index into unions?</a>
+ <li><a href="#addrspace">What effect do address spaces have on GEPs?</a>
+ <li><a href="#int">How is GEP different from ptrtoint, arithmetic, and inttoptr?</a></li>
+ <li><a href="#be">I'm writing a backend for a target which needs custom lowering for GEP. How do I do this?</a>
+ <li><a href="#vla">How does VLA addressing work with GEPs?</a>
+ </ol></li>
+ <li><a href="#rules">Rules</a>
+ <ol>
+ <li><a href="#bounds">What happens if an array index is out of bounds?</a>
+ <li><a href="#negative">Can array indices be negative?</a>
+ <li><a href="#compare">Can I compare two values computed with GEPs?</a>
+ <li><a href="#types">Can I do GEP with a different pointer type than the type of the underlying object?</a>
+ <li><a href="#null">Can I cast an object's address to integer and add it to null?</a>
+ <li><a href="#ptrdiff">Can I compute the distance between two objects, and add that value to one address to compute the other address?</a>
+ <li><a href="#tbaa">Can I do type-based alias analysis on LLVM IR?</a>
+ <li><a href="#overflow">What happens if a GEP computation overflows?</a>
+ <li><a href="#check">How can I tell if my front-end is following the rules?</a>
+ </ol></li>
+ <li><a href="#rationale">Rationale</a>
+ <ol>
+ <li><a href="#goals">Why is GEP designed this way?</a></li>
+ <li><a href="#i32">Why do struct member indices always use i32?</a></li>
+ <li><a href="#uglygep">What's an uglygep?</a>
</ol></li>
<li><a href="#summary">Summary</a></li>
</ol>
<!-- *********************************************************************** -->
<div class="doc_section"><a name="intro"><b>Introduction</b></a></div>
<!-- *********************************************************************** -->
+
<div class="doc_text">
<p>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
+ GetElementPtr (GEP) instruction. Questions about the wily GEP instruction are
+ probably the most frequently occurring 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.
</p>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="questions"><b>The Questions</b></a></div>
+<div class="doc_section"><a name="addresses"><b>Address Computation</b></a></div>
<!-- *********************************************************************** -->
<div class="doc_text">
<p>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.</p>
- <ol>
- <li><a href="firstptr">What is the first index of the GEP instruction?</a>
- </li>
- <li><a href="extra_index">Why is the extra 0 index required?</a></li>
- <li><a href="deref">What is dereferenced by GEP?</a></li>
- <li><a href="lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
- <li><a href="trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
- </ol>
+ array indexing and field selection. GEP closely resembles C array indexing
+ and field selection, however it's is a little different and this leads to
+ the following questions.</p>
</div>
<!-- *********************************************************************** -->
<p>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":</p>
- <pre>
- AType* Foo;
- ...
- X = Foo[1];</pre>
- <p>it is natural to think that there is only one index, the constant value
- <tt>1</tt>. This results from C allowing you to treat pointers and arrays as
- equivalent. LLVM doesn't. In this example, Foo is a pointer. That pointer must
- be indexed. To arrive at the same address location as the C code, you would
- provide the GEP instruction with two indices. The first indexes through the
- pointer, the second index the second element of the array.</p>
+
+<div class="doc_code">
+<pre>
+AType *Foo;
+...
+X = &Foo->F;
+</pre>
+</div>
+
+ <p>it is natural to think that there is only one index, the selection of the
+ field <tt>F</tt>. However, in this example, <tt>Foo</tt> is a pointer. That
+ pointer must be indexed explicitly in LLVM. C, on the other hand, indices
+ 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 <tt>F</tt> of the structure, just as if you wrote:</p>
+
+<div class="doc_code">
+<pre>
+X = &Foo[0].F;
+</pre>
+</div>
+
<p>Sometimes this question gets rephrased as:</p>
- <blockquote><i>Why is it okay to index through the first pointer, but
- subsequent pointers won't be dereferenced?</i></blockquote>
+ <blockquote><p><i>Why is it okay to index through the first pointer, but
+ subsequent pointers won't be dereferenced?</i></p></blockquote>
<p>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 without any need for accessing memory. It must,
- therefore be indexed like any other operand. Consider this example:</p>
- <pre>
- 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);</pre>
+ 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:</p>
+
+<div class="doc_code">
+<pre>
+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);
+</pre>
+</div>
+
<p>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 <tt>P</tt> will be the first operand of each
- of these GEP instructions. The second operand will be the field offset into
- the <tt>struct munger_struct</tt> type, for either the <tt>f1</tt> or
+ of these GEP instructions. The second operand indexes through that pointer.
+ The third operand will be the field offset into the
+ <tt>struct munger_struct</tt> type, for either the <tt>f1</tt> or
<tt>f2</tt> field. So, in LLVM assembly the <tt>munge</tt> function looks
like:</p>
- <pre>
- void %munge(%struct.munger_struct* %P) {
- entry:
- %tmp = getelementptr %struct.munger_struct* %P, int 1, uint 0
- %tmp = load int* %tmp
- %tmp6 = getelementptr %struct.munger_struct* %P, int 2, uint 1
- %tmp7 = load int* %tmp6
- %tmp8 = add int %tmp7, %tmp
- %tmp9 = getelementptr %struct.munger_struct* %P, int 0, uint 0
- store int %tmp8, int* %tmp9
- ret void
- }</pre>
+
+<div class="doc_code">
+<pre>
+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
+}
+</pre>
+</div>
+
<p>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. </p>
<p>To make this clear, let's consider a more obtuse example:</p>
- <pre>
- %MyVar = unintialized global int
- ...
- %idx1 = getelementptr int* %MyVar, long 0
- %idx2 = getelementptr int* %MyVar, long 1
- %idx3 = getelementptr int* %MyVar, long 2</pre>
+
+<div class="doc_code">
+<pre>
+%MyVar = uninitialized global i32
+...
+%idx1 = getelementptr i32* %MyVar, i64 0
+%idx2 = getelementptr i32* %MyVar, i64 1
+%idx3 = getelementptr i32* %MyVar, i64 2
+</pre>
+</div>
+
<p>These GEP instructions are simply making address computations from the
base address of <tt>MyVar</tt>. They compute, as follows (using C syntax):
</p>
- <ul>
- <li> idx1 = (char*) &MyVar + 0</li>
- <li> idx2 = (char*) &MyVar + 4</li>
- <li> idx3 = (char*) &MyVar + 8</li>
- </ul>
- <p>Since the type <tt>int</tt> is known to be four bytes long, the indices
+
+<div class="doc_code">
+<pre>
+idx1 = (char*) &MyVar + 0
+idx2 = (char*) &MyVar + 4
+idx3 = (char*) &MyVar + 8
+</pre>
+</div>
+
+ <p>Since the type <tt>i32</tt> 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
<tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
<p>The obtuse part of this example is in the cases of <tt>%idx2</tt> and
<tt>%idx3</tt>. They result in the computation of addresses that point to
memory past the end of the <tt>%MyVar</tt> global, which is only one
- <tt>int</tt> long, not three <tt>int</tt>s long. While this is legal in LLVM,
+ <tt>i32</tt> long, not three <tt>i32</tt>s 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.</p>
</div>
<p>Quick answer: there are no superfluous indices.</p>
<p>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:</p><pre>
- %MyStruct = uninitialized global { float*, int }
- ...
- %idx = getelementptr { float*, int }* %MyStruct, long 0, ubyte 1</pre>
- <p>The GEP above yields an <tt>int*</tt> by indexing the <tt>int</tt> typed
+ this:</p>
+
+<div class="doc_code">
+<pre>
+%MyStruct = uninitialized global { float*, i32 }
+...
+%idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1
+</pre>
+</div>
+
+ <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed
field of the structure <tt>%MyStruct</tt>. When people first look at it, they
- wonder why the <tt>long 0</tt> index is needed. However, a closer inspection
+ wonder why the <tt>i64 0</tt> 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:</p>
+ facts will dispel the confusion:</p>
<ol>
- <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, int }</tt>
- but rather <tt>{ float*, int }*</tt>. That is, <tt>%MyStruct</tt> is a
+ <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, i32 }</tt>
+ but rather <tt>{ float*, i32 }*</tt>. That is, <tt>%MyStruct</tt> is a
pointer to a structure containing a pointer to a <tt>float</tt> and an
- <tt>int</tt>.</li>
+ <tt>i32</tt>.</li>
<li>Point #1 is evidenced by noticing the type of the first operand of
the GEP instruction (<tt>%MyStruct</tt>) which is
- <tt>{ float*, int }*</tt>.</li>
- <li>The first index, <tt>long 0</tt> is required to step over the global
+ <tt>{ float*, i32 }*</tt>.</li>
+ <li>The first index, <tt>i64 0</tt> is required to step over the global
variable <tt>%MyStruct</tt>. 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.</li>
- <li>The second index, <tt>ubyte 1</tt> selects the second field of the
- structure (the <tt>int</tt>). </li>
+ <li>The second index, <tt>i32 1</tt> selects the second field of the
+ structure (the <tt>i32</tt>). </li>
</ol>
</div>
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:</p>
- <pre>
- %MyVar = uninitialized global { [40 x int ]* }
- ...
- %idx = getelementptr { [40 x int]* }* %MyVar, long 0, ubyte 0, long 0, long 17</pre>
+
+<div class="doc_code">
+<pre>
+%MyVar = uninitialized global { [40 x i32 ]* }
+...
+%idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17
+</pre>
+</div>
+
<p>In this example, we have a global variable, <tt>%MyVar</tt> 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
GEP instruction never accesses memory, it is illegal.</p>
<p>In order to access the 18th integer in the array, you would need to do the
following:</p>
- <pre>
- %idx = getelementptr { [40 x int]* }* %, long 0, ubyte 0
- %arr = load [40 x int]** %idx
- %idx = getelementptr [40 x int]* %arr, long 0, long 17</pre>
+
+<div class="doc_code">
+<pre>
+%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
+</pre>
+</div>
+
<p>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:</p>
- <pre>
- %MyVar = uninitialized global { [40 x int ] }
- ...
- %idx = getelementptr { [40 x int] }*, long 0, ubyte 0, long 17</pre>
+
+<div class="doc_code">
+<pre>
+%MyVar = uninitialized global { [40 x i32 ] }
+...
+%idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17
+</pre>
+</div>
+
<p>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 <tt>int</tt> in the
+ into the first field of the structure and access the 18th <tt>i32</tt> in the
array there.</p>
</div>
<p>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:</p>
- <pre>
- %MyVar = global { [10 x int ] }
- %idx1 = getlementptr { [10 x int ] }* %MyVar, long 0, ubyte 0, long 1
- %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre>
+
+<div class="doc_code">
+<pre>
+%MyVar = global { [10 x i32 ] }
+%idx1 = getelementptr { [10 x i32 ] }* %MyVar, i64 0, i32 0, i64 1
+%idx2 = getelementptr { [10 x i32 ] }* %MyVar, i64 1
+</pre>
+</div>
+
<p>In this example, <tt>idx1</tt> computes the address of the second integer
- in the array that is in the structure in %MyVar, that is <tt>MyVar+4</tt>. The
- type of <tt>idx1</tt> is <tt>int*</tt>. However, <tt>idx2</tt> computes the
- address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of
- <tt>idx2</tt> is <tt>{ [10 x int] }*</tt> and its value is equivalent
- to <tt>MyVar + 40</tt> because it indexes past the ten 4-byte integers
- in <tt>MyVar</tt>. Obviously, in such a situation, the pointers don't
- alias.</p>
+ in the array that is in the structure in <tt>%MyVar</tt>, that is
+ <tt>MyVar+4</tt>. The type of <tt>idx1</tt> is <tt>i32*</tt>. However,
+ <tt>idx2</tt> computes the address of <i>the next</i> structure after
+ <tt>%MyVar</tt>. The type of <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its
+ value is equivalent to <tt>MyVar + 40</tt> because it indexes past the ten
+ 4-byte integers in <tt>MyVar</tt>. Obviously, in such a situation, the
+ pointers don't alias.</p>
+
</div>
<!-- *********************************************************************** -->
<div class="doc_subsection">
- <a name="lead0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
+ <a name="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
</div>
<div class="doc_text">
<p>Quick Answer: They compute the same address location.</p>
<p>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:</p>
- <pre>
- %MyVar = global { [10 x int ] }
- %idx1 = getlementptr { [10 x int ] }* %MyVar, long 1, ubyte 0, long 0
- %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre>
+
+<div class="doc_code">
+<pre>
+%MyVar = global { [10 x i32 ] }
+%idx1 = getelementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
+%idx2 = getelementptr { [10 x i32 ] }* %MyVar, i64 1
+</pre>
+</div>
+
<p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
- its type is <tt>int*</tt>. The value of <tt>%idx2</tt> is also
- <tt>MyVar+40</tt> but its type is <tt>{ [10 x int] }*</tt>.</p>
+ its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also
+ <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="vectors"><b>Can GEP index into vector elements?</b></a>
+</div>
+<div class="doc_text">
+ <p>This hasn't always been forcefully disallowed, though it's not recommended.
+ It leads to awkward special cases in the optimizers, and fundamental
+ inconsistency in the IR. In the future, it will probably be outright
+ disallowed.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="unions"><b>Can GEP index into unions?</b></a>
+</div>
+<div class="doc_text">
+ <p>Unknown.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="addrspace"><b>What effect do address spaces have on GEPs?</b></a>
+</div>
+<div class="doc_text">
+ <p>None, except that the address space qualifier on the first operand pointer
+ type always matches the address space qualifier on the result type.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="int"><b>How is GEP different from ptrtoint, arithmetic,
+ and inttoptr?</b></a>
+</div>
+<div class="doc_text">
+ <p>It's very similar; there are only subtle differences.</p>
+
+ <p>With ptrtoint, you have to pick an integer type. One approach is to pick i64;
+ this is safe on everything LLVM supports (LLVM internally assumes pointers
+ are never wider than 64 bits in many places), and the optimizer will actually
+ narrow the i64 arithmetic down to the actual pointer size on targets which
+ don't support 64-bit arithmetic in most cases. However, there are some cases
+ where it doesn't do this. With GEP you can avoid this problem.
+
+ <p>Also, GEP carries additional pointer aliasing rules. It's invalid to take a
+ GEP from one object, address into a different separately allocated
+ object, and dereference it. IR producers (front-ends) must follow this rule,
+ and consumers (optimizers, specifically alias analysis) benefit from being
+ able to rely on it. See the <a href="#rules">Rules</a> section for more
+ information.</p>
+
+ <p>And, GEP is more concise in common cases.</p>
+
+ <p>However, for the underlying integer computation implied, there
+ is no difference.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="be"><b>I'm writing a backend for a target which needs custom
+ lowering for GEP. How do I do this?</b></a>
+</div>
+<div class="doc_text">
+ <p>You don't. The integer computation implied by a GEP is target-independent.
+ Typically what you'll need to do is make your backend pattern-match
+ expressions trees involving ADD, MUL, etc., which are what GEP is lowered
+ into. This has the advantage of letting your code work correctly in more
+ cases.</p>
+
+ <p>GEP does use target-dependent parameters for the size and layout of data
+ types, which targets can customize.</p>
+
+ <p>If you require support for addressing units which are not 8 bits, you'll
+ need to fix a lot of code in the backend, with GEP lowering being only a
+ small piece of the overall picture.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="vla"><b>How does VLA addressing work with GEPs?</b></a>
+</div>
+<div class="doc_text">
+ <p>GEPs don't natively support VLAs. LLVM's type system is entirely static,
+ and GEP address computations are guided by an LLVM type.</p>
+
+ <p>VLA indices can be implemented as linearized indices. For example, an
+ expression like X[a][b][c], must be effectively lowered into a form
+ like X[a*m+b*n+c], so that it appears to the GEP as a single-dimensional
+ array reference.</p>
+
+ <p>This means if you want to write an analysis which understands array
+ indices and you want to support VLAs, your code will have to be
+ prepared to reverse-engineer the linearization. One way to solve this
+ problem is to use the ScalarEvolution library, which always presents
+ VLA and non-VLA indexing in the same manner.</p>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section"><a name="rules"><b>Rules</b></a></div>
+<!-- *********************************************************************** -->
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="bounds"><b>What happens if an array index is out of bounds?</b></a>
+</div>
+<div class="doc_text">
+ <p>There are two senses in which an array index can be out of bounds.</p>
+
+ <p>First, there's the array type which comes from the (static) type of
+ the first operand to the GEP. Indices greater than the number of elements
+ in the corresponding static array type are valid. There is no problem with
+ out of bounds indices in this sense. Indexing into an array only depends
+ on the size of the array element, not the number of elements.</p>
+
+ <p>A common example of how this is used is arrays where the size is not known.
+ It's common to use array types with zero length to represent these. The
+ fact that the static type says there are zero elements is irrelevant; it's
+ perfectly valid to compute arbitrary element indices, as the computation
+ only depends on the size of the array element, not the number of
+ elements. Note that zero-sized arrays are not a special case here.</p>
+
+ <p>This sense is unconnected with <tt>inbounds</tt> keyword. The
+ <tt>inbounds</tt> keyword is designed to describe low-level pointer
+ arithmetic overflow conditions, rather than high-level array
+ indexing rules.
+
+ <p>Analysis passes which wish to understand array indexing should not
+ assume that the static array type bounds are respected.</p>
+
+ <p>The second sense of being out of bounds is computing an address that's
+ beyond the actual underlying allocated object.</p>
+
+ <p>With the <tt>inbounds</tt> keyword, the result value of the GEP is
+ undefined if the address is outside the actual underlying allocated
+ object and not the address one-past-the-end.</p>
+
+ <p>Without the <tt>inbounds</tt> keyword, there are no restrictions
+ on computing out-of-bounds addresses. Obviously, performing a load or
+ a store requires an address of allocated and sufficiently aligned
+ memory. But the GEP itself is only concerned with computing addresses.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+ <a name="negative"><b>Can array indices be negative?</b></a>
+</div>
+<div class="doc_text">
+ <p>Yes. This is basically a special case of array indices being out
+ of bounds.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+ <a name="compare"><b>Can I compare two values computed with GEPs?</b></a>
+</div>
+<div class="doc_text">
+ <p>Yes. If both addresses are within the same allocated object, or
+ one-past-the-end, you'll get the comparison result you expect. If either
+ is outside of it, integer arithmetic wrapping may occur, so the
+ comparison may not be meaningful.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+ <a name="types"><b>Can I do GEP with a different pointer type than the type of
+ the underlying object?</b></a>
+</div>
+<div class="doc_text">
+ <p>Yes. There are no restrictions on bitcasting a pointer value to an arbitrary
+ pointer type. The types in a GEP serve only to define the parameters for the
+ underlying integer computation. They need not correspond with the actual
+ type of the underlying object.</p>
+
+ <p>Furthermore, loads and stores don't have to use the same types as the type
+ of the underlying object. Types in this context serve only to specify
+ memory size and alignment. Beyond that there are merely a hint to the
+ optimizer indicating how the value will likely be used.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+ <a name="null"><b>Can I cast an object's address to integer and add it
+ to null?</b></a>
+</div>
+<div class="doc_text">
+ <p>You can compute an address that way, but if you use GEP to do the add,
+ you can't use that pointer to actually access the object, unless the
+ object is managed outside of LLVM.</p>
+
+ <p>The underlying integer computation is sufficiently defined; null has a
+ defined value -- zero -- and you can add whatever value you want to it.</p>
+
+ <p>However, it's invalid to access (load from or store to) an LLVM-aware
+ object with such a pointer. This includes GlobalVariables, Allocas, and
+ objects pointed to by noalias pointers.</p>
+
+ <p>If you really need this functionality, you can do the arithmetic with
+ explicit integer instructions, and use inttoptr to convert the result to
+ an address. Most of GEP's special aliasing rules do not apply to pointers
+ computed from ptrtoint, arithmetic, and inttoptr sequences.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+ <a name="ptrdiff"><b>Can I compute the distance between two objects, and add
+ that value to one address to compute the other address?</b></a>
+</div>
+<div class="doc_text">
+ <p>As with arithmetic on null, You can use GEP to compute an address that
+ way, but you can't use that pointer to actually access the object if you
+ do, unless the object is managed outside of LLVM.</p>
+
+ <p>Also as above, ptrtoint and inttoptr provide an alternative way to do this
+ which do not have this restriction.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+ <a name="tbaa"><b>Can I do type-based alias analysis on LLVM IR?</b></a>
+</div>
+<div class="doc_text">
+ <p>You can't do type-based alias analysis using LLVM's built-in type system,
+ because LLVM has no restrictions on mixing types in addressing, loads or
+ stores.</p>
+
+ <p>It would be possible to add special annotations to the IR, probably using
+ metadata, to describe a different type system (such as the C type system),
+ and do type-based aliasing on top of that. This is a much bigger
+ undertaking though.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="overflow"><b>What happens if a GEP computation overflows?</b></a>
+</div>
+<div class="doc_text">
+ <p>If the GEP has the <tt>inbounds</tt> keyword, the result value is
+ undefined.</p>
+
+ <p>Otherwise, the result value is the result from evaluating the implied
+ two's complement integer computation. However, since there's no
+ guarantee of where an object will be allocated in the address space,
+ such values have limited meaning.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="check"><b>How can I tell if my front-end is following the
+ rules?</b></a>
+</div>
+<div class="doc_text">
+ <p>There is currently no checker for the getelementptr rules. Currently,
+ the only way to do this is to manually check each place in your front-end
+ where GetElementPtr operators are created.</p>
+
+ <p>It's not possible to write a checker which could find all rule
+ violations statically. It would be possible to write a checker which
+ works by instrumenting the code with dynamic checks though. Alternatively,
+ it would be possible to write a static checker which catches a subset of
+ possible problems. However, no such checker exists today.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section"><a name="rationale"><b>Rationale</b></a></div>
+<!-- *********************************************************************** -->
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="goals"><b>Why is GEP designed this way?</b></a>
+</div>
+<div class="doc_text">
+ <p>The design of GEP has the following goals, in rough unofficial
+ order of priority:</p>
+ <ul>
+ <li>Support C, C-like languages, and languages which can be
+ conceptually lowered into C (this covers a lot).</li>
+ <li>Support optimizations such as those that are common in
+ C compilers.</li>
+ <li>Provide a consistent method for computing addresses so that
+ address computations don't need to be a part of load and
+ store instructions in the IR.</li>
+ <li>Support non-C-like languages, to the extent that it doesn't
+ interfere with other goals.</li>
+ <li>Minimize target-specific information in the IR.</li>
+ </ul>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+ <a name="i32"><b>Why do struct member indices always use i32?</b></a>
+</div>
+<div class="doc_text">
+ <p>The specific type i32 is probably just a historical artifact, however it's
+ wide enough for all practical purposes, so there's been no need to change it.
+ It doesn't necessarily imply i32 address arithmetic; it's just an identifier
+ which identifies a field in a struct. Requiring that all struct indices be
+ the same reduces the range of possibilities for cases where two GEPs are
+ effectively the same but have distinct operand types.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<div class="doc_subsection">
+ <a name="uglygep"><b>What's an uglygep?</b></a>
+</div>
+<div class="doc_text">
+ <p>Some LLVM optimizers operate on GEPs by internally lowering them into
+ more primitive integer expressions, which allows them to be combined
+ with other integer expressions and/or split into multiple separate
+ integer expressions. If they've made non-trivial changes, translating
+ back into LLVM IR can involve reverse-engineering the structure of
+ the addressing in order to fit it into the static type of the original
+ first operand. It isn't always possibly to fully reconstruct this
+ structure; sometimes the underlying addressing doesn't correspond with
+ the static type at all. In such cases the optimizer instead will emit
+ a GEP with the base pointer casted to a simple address-unit pointer,
+ using the name "uglygep". This isn't pretty, but it's just as
+ valid, and it's sufficient to preserve the pointer aliasing guarantees
+ that GEP provides.</p>
+
</div>
<!-- *********************************************************************** -->
</ol>
</div>
-<!-- *********************************************************************** -->
-<div class="doc_section"><a name="discussion"><b>Appendix: Discussion</b></a></div>
-<!-- *********************************************************************** -->
-<div class="doc_text">
- <p>The following is a real discussion from the
- <a href="irc://irc.oftc.net/#llvm">#llvm IRC channel</a> about the GEP
- instruction. You may find this instructive as it was the basis for this
- document.</p>
- <table>
- <tr><th>User</th><th>Comment</th></tr>
- <tr><td>Yorion</td><td>If x & y must alias, are [ getelementptr x,0,0,1,2 ] and [ getelementptr x,1,2 ] aliased? (they obviously have different types, but they should alias...)</td></tr>
- <tr><td>Yorion</td><td>oops, for the second one I meant [ getelementptr y,1,2 ]</td></tr>
- <tr><td>Reid</td><td>I don't see how that could be, Yorion but I'm not the authority on this</td></tr>
- <tr><td>Yorion</td><td>hmm.. </td></tr>
- <tr><td>Reid</td><td>the two geps, by definition, are going to produce different pointers which are not aliased</td></tr>
- <tr><td>Yorion</td><td>would [ GEP x,1,0 ] and [ GEP y,1 ] be aliased?</td></tr>
- <tr><td>Reid</td><td>if the second gep was [gep y,0,0,1,2] then they should be aliased as well</td></tr>
- <tr><td>Reid</td><td>no, I wouldn't expect that to work either :)</td></tr>
- <tr><td>Reid</td><td>you can't just arbitrarily drop leading or trailing indices :)</td></tr>
- <tr><td>Reid</td><td>(.. leading or trailing 0 indices, I mean)</td></tr>
- <tr><td>Reid</td><td>this instruction walks through a data structure and generates a pointer to the resulting thing</td></tr>
- <tr><td>Reid</td><td>if the number of indices are different, you're ending up at a different place and by definition they'll have different addresses</td></tr>
- <tr><td>Yorion</td><td>oh, I see, because of different types, [ GEP x,0,1 ]
- & [ GEP x,1 ] actually might refer to different fields, but might also refer to the same ones... </td></tr>
- <tr><td>Reid</td><td>or, at least, that's my crude understanding of it :)</td></tr>
- <tr><td>Reid</td><td>no, they'll definitely refer to different fields</td></tr>
- <tr><td>nicholas</td><td>GEP x,0,1 ==> &((*(x+0))+1)? vs. GEP x,1 ==> &(*(x+1))?</td></tr>
- <tr><td>Reid</td><td>lemme grok that for a sec</td></tr>
- <tr><td>Reid</td><td>that might be true in some limited definition of x, but it wouldn't be generally</td></tr>
- <tr><td>nicholas</td><td>oh. fields of different sizes in a structure.</td></tr>
- <tr><td>Reid</td><td>yup</td></tr>
- <tr><td>Yorion</td><td>is perhaps the type unification the reason why [ GEP x,0,1 ] and [ GEP x,1 ] cannot alias?</td></tr>
- <tr><td>Reid</td><td>no</td></tr>
- <tr><td>Reid</td><td>they may or may not have the same type, but they are definitely different pointers</td></tr>
- <tr><td>Reid</td><td>lets use a concrete example for "x"</td></tr>
- <tr><td>Reid</td><td>suppose x is "struct {int a, float b} *"</td></tr>
- <tr><td>Reid</td><td>GEP X,0,1 is going to return the address of b</td></tr>
- <tr><td>Reid</td><td>GEP X,1 is going to return the address of the *second* "a" (after the first b)</td></tr>
- <tr><td>Yorion</td><td>ah, I see... </td></tr>
- <tr><td>Yorion</td><td>trailing zeros are still a bit confusing... </td></tr>
- <tr><td>Reid</td><td>same thing .. you're just selecting the 0th member of an array or structure</td></tr>
- <tr><td>Yorion</td><td>you don't move away from the pointer, only the type is changed</td></tr>
- <tr><td>Reid</td><td>no, you still move away from the pointer .. the type might change, or not</td></tr>
- <tr><td>Reid</td><td>the pointer definitely changes</td></tr>
- <tr><td>Reid</td><td>lets look at an example for trailing zero</td></tr>
- <tr><td>Reid</td><td>suppose x is "int x[10][10][10][10]" (in C)</td></tr>
- <tr><td>Reid</td><td>GEP X,0,0 will yield you a 3 dimensional array</td></tr>
- <tr><td>Reid</td><td>GEP X,0,0,0,0,0 will yield you an "int"</td></tr>
- <tr><td>Reid</td><td>make sense?</td></tr>
- <tr><td>Yorion</td><td>yes</td></tr>
- <tr><td>Reid</td><td>so, I think there's a law here: if the number of indices in two GEP instructions are not equivalent, there is no way the resulting pointers can alias</td></tr>
- <tr><td>Reid</td><td>(assuming the x and y alias)</td></tr>
- <tr><td>Yorion</td><td>I was confused with some code in BasicAliasAnalysis that says that two pointers are equal if they differ only in trailing zeros</td></tr>
- <tr><td>Yorion</td><td>BasicAliasAnalysis.cpp:504-518</td></tr>
- <tr><td>Reid</td><td>lemme look</td></tr>
- <tr><td>nicholas</td><td>if y1 = GEP X, 0, 0 and y2 = GEP X, 0, 0, 0, 0, 0 (from Reid's example)</td></tr>
- <tr><td>nicholas</td><td>then doesn't *y1 and *y2 both refer to the same "int"?</td></tr>
- <tr><td>Reid</td><td>they shouldn't</td></tr>
- <tr><td>Reid</td><td>hmm .. actually, maybe you're right :)</td></tr>
- <tr><td>Reid</td><td>they definitely have different *types*</td></tr>
- <tr><td>Yorion</td><td>true</td></tr>
- <tr><td>nicholas</td><td>different types just doesn't cut it. :)</td></tr>
- <tr><td>Reid</td><td>.. thinking on this :)</td></tr>
- <tr><td>nicholas</td><td>similarly, i could create a yucky with a struct that has a char *, then have you GEP right through the pointer into the pointed-to data. That could mean that the resulting point might alias anything.</td></tr>
- <tr><td>Yorion</td><td>my theory (after reading BAA) is that all zeros can be omitted, and that the pointers alias if they have the same sequence of indices</td></tr>
- <tr><td>Yorion</td><td>however, this screws the typing, so that's why zeros are for</td></tr>
- <tr><td>Yorion</td><td>nicholas, does that match your hunch?</td></tr>
- <tr><td>nicholas</td><td>I have to admit, I've had much grief with GEPIs already. I wish the semantics were plainly documented as part of their own language, instead of just relying on C aliasing rules and C semantics...</td></tr>
- <tr><td>nicholas</td><td>Yorion: leading zeroes can't be omitted.</td></tr>
- <tr><td>Reid</td><td>okay, if you have two GEPs and their leading indices are an exact match, if the one with more indices only has trailing 0s then they should alias</td></tr>
- <tr><td>nicholas</td><td>must alias, i think.</td></tr>
- <tr><td>Reid</td><td>yes, must alias, sorry</td></tr>
- <tr><td>Yorion</td><td>okay</td></tr>
- <tr><td>Yorion</td><td>I'm glad we cleared this up</td></tr>
- <tr><td>Reid</td><td>so, if y1 = GEP X, 1,2,0 and if y2 = GEP X, 1,2,0,0,0 then y1 "must alias" y2 :)</td></tr>
- <tr><td>Reid</td><td>but that doesn't work for leading 0s :)</td></tr>
- <tr><td>Yorion</td><td>yes, true... I was wrong </td></tr>
- <tr><td>Reid</td><td>I too have been having fun with GEP recently :)</td></tr>
- <tr><td>Yorion</td><td>but, there're cases like [a = GEP x,1,0; b = GEP a,1,0; c = GEP b,1,0], and that should be equivalent to GEP x,1,0,1,0,1</td></tr>
- <tr><td>Reid</td><td>not quite</td></tr>
- <tr><td>nicholas</td><td>I'm sure another rule can be written for GEPIs, but they would only apply to type-safe code.</td></tr>
- <tr><td>nicholas</td><td>another *tautology</td></tr>
- <tr><td>Yorion</td><td>Reid: why not, only the type should be different...</td></tr>
- <tr><td>Reid</td><td>its should be equivalent to GEP x,1,0,1,0,1,0</td></tr>
- <tr><td>Yorion</td><td>and that must alias GEP x,1,0,1,0,1</td></tr>
- <tr><td>Reid</td><td>hmm, by the previous rule, I guess you're right :)</td></tr>
- <tr><td>Yorion</td><td>I'm a bit scared that even you're a bit confused about GEP</td></tr>
- <tr><td>Reid</td><td>I'm glad I'm not the only one that gets a little confused wrapping my head around this stuff :)</td></tr>
- <tr><td>Reid</td><td>GEP has always confused me .. partly because I think its wrong :)</td></tr>
- <tr><td>Reid</td><td>well, actually, not so much that GEP is wrong, but that gvars being pointers without storage</td></tr>
- <tr><td>Reid</td><td>i.e. when you say "%x = global int" in LLVM, the type of X is int*</td></tr>
- <tr><td>Reid</td><td>yet, there is no storage for that pointer</td></tr>
- <tr><td>Reid</td><td>its magically deduced</td></tr>
- <tr><td>nicholas</td><td>well, it makes no sense to have globals be SSA...</td></tr>
- <tr><td>Reid</td><td>heh</td></tr>
- <tr><td>Reid</td><td>yeah, well .. practicalities :)</td></tr>
- <tr><td>Yorion</td><td>true</td></tr>
- <tr><td>Yorion</td><td>sabre gave me a reference on how globals are handled in SSA</td></tr>
- <tr><td>Reid</td><td>anyway, gotta run</td></tr>
- <tr><td>Yorion</td><td>the paper was crappy, but I do understand now why is it implemented that way in LLVM</td></tr>
- <tr><td>Yorion</td><td>thx for the interesting discussion Reid</td></tr>
- <tr><td>Reid</td><td>heh .. its one that Chris and I keep having .. he just tells me that C has rotted my brain :)</td></tr>
- <tr><td>nicholas</td><td>lol</td></tr>
- <tr><td>Yorion</td><td>hehehe</td></tr>
- <tr><td>Reid</td><td>he might be right :)</td></tr>
- <tr><td>Yorion</td><td>sabre: have you seen the discussion on GEP?</td></tr>
- <tr><td>sabre</td><td>no</td></tr>
- <tr><td>sabre</td><td>I'll read the backlog, j/s</td></tr>
- <tr><td>sabre</td><td>ok, there's a lot</td></tr>
- <tr><td>sabre</td><td>what's the executive summary?</td></tr>
- <tr><td>sabre</td><td>do you have a q?</td></tr>
- <tr><td>Yorion</td><td>is it possible that GEP x,0,0,1 and GEP x,1 alias?</td></tr>
- <tr><td>sabre</td><td>no</td></tr>
- <tr><td>Yorion</td><td>and b) GEP x,1,0,0 and GEP x,1 should alias, right?</td></tr>
- <tr><td>sabre</td><td>I assume you mean for size = 1 ?</td></tr>
- <tr><td>sabre</td><td>b) yes</td></tr>
- <tr><td>Yorion</td><td>although they have different types</td></tr>
- <tr><td>sabre</td><td>right</td></tr>
- <tr><td>Yorion</td><td>okay</td></tr>
- <tr><td>Yorion</td><td>I'm still not 100% convinced that: a=GEP x,1,0; b=GEP a,1,0; c=GEP b,1,0 cannot alias Z=GEP x,1,1,1</td></tr>
- <tr><td>Yorion</td><td>(that c and z cannot alias)</td></tr>
- <tr><td>sabre</td><td>that's becuse they do alias</td></tr>
- <tr><td>sabre</td><td>mustalias in fact</td></tr>
- <tr><td>Yorion</td><td>but then: GEP x,1,0,1,0,1,0 = GEP x,1,1,1</td></tr>
- <tr><td>sabre</td><td>Yorion: no</td></tr>
- <tr><td>sabre</td><td>c != GEP x,1,0,1,0,1,0</td></tr>
- <tr><td>sabre</td><td>the first index doesn't work like that</td></tr>
- <tr><td>Yorion</td><td>how does then the first index work? c and z must alias, but GEP x,1,0,1,0 != GEP x,1,1 ??</td></tr>
- <tr><td>sabre</td><td>*sigh*</td></tr>
- <tr><td>Reid</td><td>:)</td></tr>
- <tr><td>Reid</td><td>we need an FAQ on this</td></tr>
- <tr><td>sabre</td><td>Yorion: how did you get </td></tr>
- <tr><td>sabre</td><td>"GEP x,1,0,1,0"? </td></tr>
- <tr><td>Yorion</td><td>look</td></tr>
- <tr><td>sabre</td><td>you can't just concatenate subscripts</td></tr>
- <tr><td>Yorion</td><td>why?</td></tr>
- <tr><td>sabre</td><td>because... it doesn't work that way?</td></tr>
- <tr><td>sabre</td><td>consider C</td></tr>
- <tr><td>Yorion</td><td>how does it work?</td></tr>
- <tr><td>sabre</td><td>if I have blah* P</td></tr>
- <tr><td>sabre</td><td>P[0][1][2][3][4]</td></tr>
- <tr><td>sabre</td><td>this is *not* the same as:</td></tr>
- <tr><td>sabre</td><td>t = &P[0][1][2] ... t[3][4]</td></tr>
- <tr><td>sabre</td><td>Yorion: Consider: struct *P </td></tr>
- <tr><td>sabre</td><td>P->X == P[0].X</td></tr>
- <tr><td>sabre</td><td>You're losing the 0.</td></tr>
- <tr><td>sabre</td><td>P->X->Y == P[0].X[0].Y</td></tr>
- <tr><td>sabre</td><td>Not P.X.Y</td></tr>
- <tr><td>sabre</td><td>actually that's a bad analogy</td></tr>
- <tr><td>sabre</td><td>because C dereferences in this case</td></tr>
- <tr><td>sabre</td><td>Try: (&(P->X))->Y</td></tr>
- <tr><td>Yorion</td><td>so, a=GEP x,1,0; b=GEP a,1,0; c=GEP b,1,0, can you construct the definition of c in terms of x?</td></tr>
- <tr><td>sabre</td><td>yes, but you're going out of bounds :)</td></tr>
- <tr><td>sabre</td><td>consider this:</td></tr>
- <tr><td>sabre</td><td>{ float, { double , { int } } } *P</td></tr>
- <tr><td>sabre</td><td>int *X = gep P, 0, 1, 1, 0</td></tr>
- <tr><td>sabre</td><td>do you understand the leading zero?</td></tr>
- <tr><td>sabre</td><td>alternatively:</td></tr>
- <tr><td>sabre</td><td>t = gep P, 0, 1</td></tr>
- <tr><td>sabre</td><td>t2 = gep t, 0, 1</td></tr>
- <tr><td>sabre</td><td>X = gep t, 0, 0</td></tr>
- <tr><td>Yorion</td><td>what's t2 for?</td></tr>
- <tr><td>sabre</td><td>oh</td></tr>
- <tr><td>sabre</td><td>sorry :)</td></tr>
- <tr><td>sabre</td><td>X = gep t2, 0, 0</td></tr>
- <tr><td>Yorion</td><td>give me a minute please</td></tr>
- <tr><td>sabre</td><td>ok</td></tr>
- <tr><td>Yorion</td><td>sabre: shouldn't the type be: { float, { double, { int }* } }* P ?</td></tr>
- <tr><td>sabre</td><td>nope</td></tr>
- <tr><td>sabre</td><td>why the extra * ?</td></tr>
- <tr><td>sabre</td><td>if it helps, the type of t is { double, {int}}* and t2 is {int}* and X is int*</td></tr>
- <tr><td>Yorion</td><td>wait... 0 represents dereference, natural number i
- represents &A[i] ?</td></tr>
- <tr><td>sabre</td><td>gep does no dereferences, ever</td></tr>
- <tr><td>sabre</td><td>gep P, 0, 1 is equivalent to &P[0].X</td></tr>
- <tr><td>sabre</td><td>aka &P->X</td></tr>
- <tr><td>sabre</td><td>gep P, 1 == &P[1] aka P+1</td></tr>
- <tr><td>sabre</td><td>so gep P, 0, 1 can't alias gep P, 1 just like
- &P->Y can't alias P+1</td></tr>
- <tr><td>sabre</td><td>assuming P is a pointer to struct {X, Y }</td></tr>
- <tr><td>Yorion</td><td>sabre: is it possible to come up with a general rule for "arithmetic of GEP indices"? </td></tr>
- <tr><td>sabre</td><td>Yorion: of course, it's very simple</td></tr>
- <tr><td>sabre</td><td>just not what you're expecting :)</td></tr>
- <tr><td>sabre</td><td>See langref.html</td></tr>
- <tr><td>Yorion</td><td>for example, a=GEP x,0,0,1 b=GEP a,0,0,1, c=GEP b,0,0,1, that should be equal to GEP x,0,1,1,0, right?</td></tr>
- <tr><td>Yorion</td><td>I did</td></tr>
- <tr><td>Yorion</td><td>oops, equal to GEP x,0,1,1,1,0</td></tr>
- <tr><td>sabre</td><td>that would be:</td></tr>
- <tr><td>sabre</td><td>GEP X, 0, 0, 1, 0, 1, 0, 1</td></tr>
- <tr><td>Yorion</td><td>you're killing me</td></tr>
- <tr><td>sabre</td><td>The basic rule when turning: A = GEP B, C D = GEP A, 0, E</td></tr>
- <tr><td>sabre</td><td>is that you drop the 0, turning it into</td></tr>
- <tr><td>sabre</td><td>GEP B, C, E</td></tr>
- <tr><td>Yorion</td><td>okay, that's good. any other rules?</td></tr>
- <tr><td>nicholas</td><td>what if it isn't a 0?</td></tr>
- <tr><td>sabre</td><td>more generally: A = GEP Ptr, B, C, ... D = GEP A, 0, E, F, ... </td></tr>
- <tr><td>sabre</td><td>D = GEP Ptr, B, C, ... E, F, ...</td></tr>
- <tr><td>sabre</td><td>if it's not zero, you generally cannot concatenate them</td></tr>
- <tr><td>sabre</td><td>unless the first gep has one subscript</td></tr>
- <tr><td>sabre</td><td>in which case you drop the zero</td></tr>
- <tr><td>sabre</td><td>if you look in InstCombiner::visitGetElementPtrInst, it should have this logic</td></tr>
- <tr><td>Yorion</td><td>what if there is no zero? how can I compute the offset from the base pointer in that case?</td></tr>
- <tr><td>Yorion</td><td>like A=GEP B,C and D=GEP A,E,F</td></tr>
- <tr><td>sabre</td><td>you don't have to combine them to compute an offset</td></tr>
- <tr><td>sabre</td><td>are you *just* trying to get a byte offset from the pointer?</td></tr>
- <tr><td>Yorion</td><td>I'm trying to get offset of D from B</td></tr>
- <tr><td>sabre</td><td>why didn't you say so? :)</td></tr>
- <tr><td>sabre</td><td>with all constant subscripts, it's trivial</td></tr>
- <tr><td>sabre</td><td>look at SelectionDAGLowering::visitGetElementPtr</td></tr>
- <tr><td>sabre</td><td>in CodeGen/SelectionDAG/SelectionDAGISel.cpp</td></tr>
- <tr><td>sabre</td><td>basically the rule is that you multiply the index by the size of the thing indexed</td></tr>
- <tr><td>sabre</td><td>there is also a Support/GetElementPtrIterator or something</td></tr>
- <tr><td>sabre</td><td>that makes it trivial to see what type is indexed by which subscript</td></tr>
- <tr><td>sabre</td><td>for each subscript it gives you a type</td></tr>
- <tr><td>sabre</td><td>For an array subscript you multiply the index by the indexed type</td></tr>
- <tr><td>sabre</td><td>for a struct subscript, you add the field offset</td></tr>
- <tr><td>sabre</td><td>s/array/sequentialtype/ if you're in a pedantic mood</td></tr>
- <tr><td>Yorion</td><td>let's focus on structs: in that case, the above given example would be: D = GEP B,C,E,F?</td></tr>
- <tr><td>sabre</td><td>no</td></tr>
- <tr><td>sabre</td><td>you drop the E if it's zero</td></tr>
- <tr><td>sabre</td><td>if it's not you can't concat</td></tr>
- <tr><td>sabre</td><td>are you trying to trick me into saying "yes, just append the indices"? :)</td></tr>
- <tr><td>Yorion</td><td>okay, let's assume E is not zero, how do I compute offset from B for D for a struct?</td></tr>
- <tr><td>sabre</td><td>Why are you framing this in terms of concatenation?</td></tr>
- <tr><td>Yorion</td><td>no, I'm trying to understand it</td></tr>
- <tr><td>sabre</td><td>computing an offset and concatenating are entirely different</td></tr>
- <tr><td>sabre</td><td>Lets consider a specific example</td></tr>
- <tr><td>Yorion</td><td>because I want to express certain properties in the terms of base pointers either globals or parameters</td></tr>
- <tr><td>Yorion</td><td>I want to eliminate locals from my analysis</td></tr>
- <tr><td>sabre</td><td>you realize that parmeters can point into the middle of structs?</td></tr>
- <tr><td>Yorion</td><td>yes</td></tr>
- <tr><td>sabre</td><td>you realize invalid access paths can be constructed with geps/</td></tr>
- <tr><td>sabre</td><td>?</td></tr>
- <tr><td>Yorion</td><td>what do you mean by invalid access paths? </td></tr>
- <tr><td>Yorion</td><td>like offseting out of the struct which is passed to the function?</td></tr>
- <tr><td>sabre</td><td>The case where the subscript isn't zero is invalid code</td></tr>
- <tr><td>sabre</td><td>from a type-safety perspective</td></tr>
- <tr><td>DannyB</td><td>he means untypesafe things that seem valid :)</td></tr>
- <tr><td>DannyB</td><td>IE they point somewhere in the struct, but not to any particular field</td></tr>
- <tr><td>DannyB</td><td>(or whatever)</td></tr>
- <tr><td>sabre</td><td>right</td></tr>
- <tr><td>Yorion</td><td>okay</td></tr>
- <tr><td>sabre</td><td>or they might point in some other struct :)</td></tr>
- <tr><td>sabre</td><td>It's the equivalent to saying:</td></tr>
- <tr><td>sabre</td><td>struct Foo { int A, int B; }</td></tr>
- <tr><td>sabre</td><td>Foo* P = </td></tr>
- <tr><td>sabre</td><td>T = &P->B;</td></tr>
- <tr><td>sabre</td><td>S = T+1</td></tr>
- <tr><td>sabre</td><td>that is:</td></tr>
- <tr><td>sabre</td><td>T = gep 0, 1</td></tr>
- <tr><td>sabre</td><td>S = gep T, 1</td></tr>
- <tr><td>sabre</td><td>you can't concat those and get a type-safe access path</td></tr>
- <tr><td>sabre</td><td>remember T = &P->B === T = &P[0].B</td></tr>
- <tr><td>sabre</td><td>understand?</td></tr>
- <tr><td>Yorion</td><td>let me think for a minute</td></tr>
- <tr><td>sabre</td><td>Consider what the C case does, it will be most clear if you're used to C</td></tr>
- <tr><td>sabre</td><td>:)</td></tr>
- <tr><td>sabre</td><td>Consider the byte offset and why it doesn't point into P-> anything</td></tr>
- <tr><td>sabre</td><td>it points into P[1] not P[0]</td></tr>
- <tr><td>Yorion</td><td>it's perfectly fine if GEP offsets out of the type. I'd still need to express GEP in the terms of base pointers. Take the example above: T=GEP P,0,1; S=GEP T,1</td></tr>
- <tr><td>Yorion</td><td>type safety is not crucial in my case</td></tr>
- <tr><td>sabre</td><td>That specific example is GEP P, 1, 0</td></tr>
- <tr><td>sabre</td><td>however, you can form geps that are NOT equivalent to anything else</td></tr>
- <tr><td>sabre</td><td>for example, consider:</td></tr>
- <tr><td>sabre</td><td>struct X { int, char}</td></tr>
- <tr><td>Yorion</td><td>that is fine. they're equivalent to something in the calling context</td></tr>
- <tr><td>sabre</td><td>the same sequence points into padding</td></tr>
- <tr><td>sabre</td><td>and there is no gep that can do that</td></tr>
- <tr><td>Yorion</td><td>the bottom line is: if the program is valid, interprocedural analysis will match that offset with something in one of the functions on the call stack</td></tr>
- <tr><td>Yorion</td><td>and that's all I care about</td></tr>
- <tr><td>Yorion</td><td>can you give me a formula for structs for computing
- offsets that takes into account the case GEP T,&lt:non_zeros> and the size of the structs/fields?</td></tr>
- <tr><td>sabre</td><td>yes, I did above</td></tr>
- <tr><td>sabre</td><td>Two things:</td></tr>
- <tr><td>sabre</td><td>GEP Ptr, A, X, Y, Z</td></tr>
- <tr><td>sabre</td><td>The result is Ptr + A * sizeof(struct) + fieldoffs(X) + fieldoffs(Y) + fieldoffs(Z)</td></tr>
- <tr><td>sabre</td><td>simple enough?</td></tr>
- <tr><td>sabre</td><td>you see why "A" is special?</td></tr>
- <tr><td>Yorion</td><td>give me a min, I'm constructing an example</td></tr>
- <tr><td>Reid</td><td>sabre: I think I finally understand</td></tr>
- <tr><td>Reid</td><td>your comment that GEP *never* dereferences makes a lot of sense</td></tr>
- <tr><td>Reid</td><td>it is only doing address calculation, so the first one is taking the address of the var</td></tr>
- <tr><td>sabre</td><td>If C didn't conflate lvalues and rvalues, GEP would be much easier to understand for people</td></tr>
- <tr><td>Reid</td><td>yeah</td></tr>
- <tr><td>Yorion</td><td>so, for example: M=GEP A,B,C; N=GEP M,D,E; N = [ A + B*sizeof(struct) + fieldoffs(C) ]:(of type T) + D*sizeof(T) + fieldoffs(E)</td></tr>
- <tr><td>Reid</td><td>I just remember learning a hard lesson about the difference between char* A and char A[] .. long time ago when I was learning C</td></tr>
- <tr><td>sabre</td><td>of type T*</td></tr>
- <tr><td>sabre</td><td>otherwise fine</td></tr>
- <tr><td>Yorion</td><td>okay, I think I finally understand it</td></tr>
- <tr><td>sabre</td><td>without the T* your D sizeof will be wrong</td></tr>
- <tr><td>Yorion</td><td>a suggestion: the formula you gave above explains it all</td></tr>
- <tr><td>Yorion</td><td>I'd suggest explaining it that way in documentation</td></tr>
- <tr><td>sabre</td><td>That's not right though</td></tr>
- <tr><td>sabre</td><td>it doesn't include arrays or packed types</td></tr>
- <tr><td>sabre</td><td>so it is, at best, a half truth</td></tr>
- <tr><td>Yorion</td><td>tell me, how to compute the fieldoffs for an index?</td></tr>
- <tr><td>sabre</td><td>arrays can be in structs :)</td></tr>
- <tr><td>Yorion</td><td>in bytes</td></tr>
- <tr><td>sabre</td><td>idx * sizeof(arrayelt)</td></tr>
- <tr><td>sabre</td><td>just like for pointers (the first index)</td></tr>
- <tr><td>sabre</td><td>There are two cases: structs and sequentials</td></tr>
- <tr><td>sabre</td><td>for sequentials you use idx*sizeof(sequenced type)</td></tr>
- <tr><td>sabre</td><td>for structs you add their offset</td></tr>
- <tr><td>sabre</td><td>it's really very simple :)</td></tr>
- <tr><td>sabre</td><td>the first index of a gep is always over the pointer</td></tr>
- <tr><td>Yorion</td><td>no I meant in LLVM, how do I convert the field offset into bytes?</td></tr>
- <tr><td>sabre</td><td>which is why it's strange</td></tr>
- <tr><td>sabre</td><td>if you only think about structs</td></tr>
- <tr><td>sabre</td><td>TargetData::getFieldOffset </td></tr>
- <tr><td>sabre</td><td>or something</td></tr>
- <tr><td>sabre</td><td>look in SelectionDAGISel.cpp (visitGEP) as I suggested.</td></tr>
- <tr><td>Yorion</td><td>do you still have the energy to go over sequential types? :-)</td></tr>
- <tr><td>Yorion</td><td>what is the offset formula for sequential types?</td></tr>
- <tr><td>Reid</td><td>we just went over that: idx * sizeof(elementType)</td></tr>
- <tr><td>Yorion</td><td>so, if there's an array hidden somewhere in the struct, essentially I need to compute idx*sizeof() instead of fieldoffs() and that's it?</td></tr>
- <tr><td>sabre</td><td>yes</td></tr>
- <tr><td>Reid</td><td>yes</td></tr>
- <tr><td>Yorion</td><td>excellent.</td></tr>
- <tr><td>sabre</td><td>There are two cases: structs and sequentials</td></tr>
- <tr><td>sabre</td><td>[9:17pm] sabre: for sequentials you use idx*sizeof(sequenced type)</td></tr>
- <tr><td>sabre</td><td>[9:17pm] sabre: for structs you add their offset</td></tr>
- <tr><td>sabre</td><td>[9:17pm] sabre: it's really very simple :)</td></tr>
- <tr><td>Yorion</td><td>now when I understand it, it is simple... </td></tr>
- <tr><td>Yorion</td><td>thx</td></tr>
- </table>
-
<!-- *********************************************************************** -->
<hr>
<address>
<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
- src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+ src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
<a href="http://validator.w3.org/check/referer"><img
- src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
+ src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff