Merge the advanced getelementptr FAQ into the regular

getelementptr FAQ.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97154 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 384 insertions, 21 deletions

diff --git a/docs/GetElementPtr.html b/docs/GetElementPtr.html
index dd49ef7..1bf6f43 100644
--- a/docs/GetElementPtr.html
+++ b/docs/GetElementPtr.html
@@ -17,7 +17,7 @@
 
 <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>
@@ -25,6 +25,30 @@
       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>
@@ -37,9 +61,10 @@
 <!-- *********************************************************************** -->
 <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
+  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.
@@ -47,22 +72,14 @@
 </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>
 
 <!-- *********************************************************************** -->
@@ -85,7 +102,7 @@ X = &amp;Foo-&gt;F;
 
   <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 
@@ -155,7 +172,7 @@ entry:
 
 <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
@@ -210,7 +227,7 @@ idx3 = (char*) &amp;MyVar + 8
   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 
@@ -297,8 +314,8 @@ idx3 = (char*) &amp;MyVar + 8
 <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>
 
@@ -326,8 +343,8 @@ idx3 = (char*) &amp;MyVar + 8
 <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>
 
@@ -337,6 +354,352 @@ idx3 = (char*) &amp;MyVar + 8
 </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>
+
+<!-- *********************************************************************** -->
 <div class="doc_section"><a name="summary"><b>Summary</b></a></div>
 <!-- *********************************************************************** -->