</head>
<body>
-<div class="doc_title">
+<h1>
The Often Misunderstood GEP Instruction
-</div>
+</h1>
<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="#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>
+<h2><a name="intro">Introduction</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+
+<div>
<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
+ <a href="LangRef.html#i_getelementptr">GetElementPtr</a> (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>
+<h2><a name="addresses">Address Computation</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<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>
-</div>
+ 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 class="doc_subsection">
- <a name="firstptr"><b>What is the first index of the GEP instruction?</b></a>
-</div>
-<div class="doc_text">
+<h3>
+ <a name="firstptr">What is the first index of the GEP instruction?</a>
+</h3>
+<div>
<p>Quick answer: The index stepping through the first operand.</p>
<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
<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, indexs
+ 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
<div class="doc_code">
<pre>
-%MyVar = unintialized global i32
+%MyVar = uninitialized global i32
...
%idx1 = getelementptr i32* %MyVar, i64 0
%idx2 = getelementptr i32* %MyVar, i64 1
</div>
<!-- *********************************************************************** -->
-<div class="doc_subsection">
- <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
-</div>
+<h3>
+ <a name="extra_index">Why is the extra 0 index required?</a>
+</h3>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<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
field of the structure <tt>%MyStruct</tt>. When people first look at it, they
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*, i32 }</tt>
but rather <tt>{ float*, i32 }*</tt>. That is, <tt>%MyStruct</tt> is a
</div>
<!-- *********************************************************************** -->
-<div class="doc_subsection">
- <a name="deref"><b>What is dereferenced by GEP?</b></a>
-</div>
-<div class="doc_text">
+<h3>
+ <a name="deref">What is dereferenced by GEP?</a>
+</h3>
+<div>
<p>Quick answer: nothing.</p>
<p>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.
</div>
<!-- *********************************************************************** -->
-<div class="doc_subsection">
- <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
-</div>
-<div class="doc_text">
+<h3>
+ <a name="lead0">Why don't GEP x,0,0,1 and GEP x,1 alias?</a>
+</h3>
+<div>
<p>Quick Answer: They compute different address locations.</p>
<p>If you look at the first indices in these GEP
instructions you find that they are different (0 and 1), therefore the address
<div class="doc_code">
<pre>
%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
+%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>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>
+ 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="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
-</div>
-<div class="doc_text">
+<h3>
+ <a name="trail0">Why do GEP x,1,0,0 and GEP x,1 alias?</a>
+</h3>
+<div>
<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
<div class="doc_code">
<pre>
%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
+%idx1 = getelementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
+%idx2 = getelementptr { [10 x i32 ] }* %MyVar, i64 1
</pre>
</div>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="summary"><b>Summary</b></a></div>
+
+<h3>
+ <a name="vectors">Can GEP index into vector elements?</a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="addrspace">What effect do address spaces have on GEPs?</a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="int">
+ How is GEP different from ptrtoint, arithmetic, and inttoptr?
+ </a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="be">
+ I'm writing a backend for a target which needs custom lowering for GEP.
+ How do I do this?
+ </a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="vla">How does VLA addressing work with GEPs?</a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+<h2><a name="rules">Rules</a></h2>
+<!-- *********************************************************************** -->
+<div>
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="bounds">What happens if an array index is out of bounds?</a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+<h3>
+ <a name="negative">Can array indices be negative?</a>
+</h3>
+<div>
+ <p>Yes. This is basically a special case of array indices being out
+ of bounds.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<h3>
+ <a name="compare">Can I compare two values computed with GEPs?</a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+<h3>
+ <a name="types">
+ Can I do GEP with a different pointer type than the type of
+ the underlying object?
+ </a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+<h3>
+ <a name="null">
+ Can I cast an object's address to integer and add it to null?
+ </a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+<h3>
+ <a name="ptrdiff">
+ Can I compute the distance between two objects, and add
+ that value to one address to compute the other address?
+ </a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+<h3>
+ <a name="tbaa">Can I do type-based alias analysis on LLVM IR?</a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="overflow">What happens if a GEP computation overflows?</a>
+</h3>
+<div>
+ <p>If the GEP lacks the <tt>inbounds</tt> keyword, the 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>
+
+ <p>If the GEP has the <tt>inbounds</tt> keyword, the result value is
+ undefined (a "<a href="LangRef.html#trapvalues">trap value</a>") if the GEP
+ overflows (i.e. wraps around the end of the address space).</p>
+
+ <p>As such, there are some ramifications of this for inbounds GEPs: scales
+ implied by array/vector/pointer indices are always known to be "nsw" since
+ they are signed values that are scaled by the element size. These values
+ are also allowed to be negative (e.g. "gep i32 *%P, i32 -1") but the
+ pointer itself is logically treated as an unsigned value. This means that
+ GEPs have an asymmetric relation between the pointer base (which is treated
+ as unsigned) and the offset applied to it (which is treated as signed). The
+ result of the additions within the offset calculation cannot have signed
+ overflow, but when applied to the base pointer, there can be signed
+ overflow.
+ </p>
+
+
+</div>
+
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="check">
+ How can I tell if my front-end is following the rules?
+ </a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+<h2><a name="rationale">Rationale</a></h2>
+<!-- *********************************************************************** -->
+<div>
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="goals">Why is GEP designed this way?</a>
+</h3>
+<div>
+ <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. In particular, GEP is a cornerstone of LLVM's
+ <a href="LangRef.html#pointeraliasing">pointer aliasing model</a>.</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>
+
+<!-- *********************************************************************** -->
+<h3>
+ <a name="i32">Why do struct member indices always use i32?</a>
+</h3>
+<div>
+ <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>
+
+<!-- *********************************************************************** -->
+
+<h3>
+ <a name="uglygep">What's an uglygep?</a>
+</h3>
+<div>
+ <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>
+
+</div>
+
+<!-- *********************************************************************** -->
+<h2><a name="summary">Summary</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>In summary, here's some things to always remember about the GetElementPtr
instruction:</p>
<ol>
<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>
- <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
+ 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>
</body>
projects / oota-llvm.git / blobdiff