docs/GetElementPtr.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3 <html>
   4 <head>
   5   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   6   <title>The Often Misunderstood GEP Instruction</title>
   7   <link rel="stylesheet" href="llvm.css" type="text/css">
   8 </head>
   9 <body>
  10
  11 <div class="doc_title">
  12   The Often Misunderstood GEP Instruction
  13 </div>
  14
  15 <ol>
  16   <li><a href="#intro">Introduction</a></li>
  17   <li><a href="#questions">The Questions</a>
  18   <ol>
  19     <li><a href="#extra_index">Why is the extra 0 index required?</a></li>
  20     <li><a href="#deref">What is dereferenced by GEP?</a></li>
  21     <li><a href="#firstptr">Why can you index through the first pointer but not
  22       subsequent ones?</a></li>
  23     <li><a href="#lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
  24     <li><a href="#trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
  25   </ol></li>
  26   <li><a href="#summary">Summary</a></li>
  27 </ol>
  28
  29 <div class="doc_author">
  30   <p>Written by: <a href="mailto:rspencer@reidspencer.com">Reid Spencer</a>.</p>
  31 </div>
  32
  33
  34 <!-- *********************************************************************** -->
  35 <div class="doc_section"><a name="intro"><b>Introduction</b></a></div>
  36 <!-- *********************************************************************** -->
  37 <div class="doc_text">
  38   <p>This document seeks to dispel the mystery and confusion surrounding LLVM's
  39   GetElementPtr (GEP) instruction. Questions about the wiley GEP instruction are
  40   probably the most frequently occuring questions once a developer gets down to
  41   coding with LLVM. Here we lay out the sources of confusion and show that the
  42   GEP instruction is really quite simple.
  43   </p>
  44 </div>
  45
  46 <!-- *********************************************************************** -->
  47 <div class="doc_section"><a name="questions"><b>The Questions</b></a></div>
  48 <!-- *********************************************************************** -->
  49 <div class="doc_text">
  50   <p>When people are first confronted with the GEP instruction, they tend to
  51   relate it to known concepts from other programming paradigms, most notably C
  52   array indexing and field selection. However, GEP is a little different and
  53   this leads to the following questions, all of which are answered in the
  54   following sections.</p>
  55   <ol>
  56     <li><a href="extra_index">Why is the extra 0 index required?</a></li>
  57     <li><a href="deref">What is dereferenced by GEP?</a></li>
  58     <li><a href="firstptr">Why can you index through the first pointer but not
  59       subsequent ones?</a></li>
  60     <li><a href="lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
  61     <li><a href="trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
  62   </ol>
  63 </div>
  64
  65 <!-- *********************************************************************** -->
  66 <div class="doc_subsection">
  67   <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
  68 </div>
  69 <!-- *********************************************************************** -->
  70 <div class="doc_text">
  71   <p>Quick answer: there are no superfluous indices.</p>
  72   <p>This question arises most often when the GEP instruction is applied to a
  73   global variable which is always a pointer type. For example, consider
  74   this:</p><pre>
  75   %MyStruct = uninitialized global { float*, int }
  76   ...
  77   %idx = getelementptr { float*, int }* %MyStruct, long 0, ubyte 1</pre>
  78   <p>The GEP above yields an <tt>int*</tt> by indexing the <tt>int</tt> typed
  79   field of the structure <tt>%MyStruct</tt>. When people first look at it, they
  80   wonder why the <tt>long 0</tt> index is needed. However, a closer inspection
  81   of how globals and GEPs work reveals the need. Becoming aware of the following
  82   facts will dispell the confusion:</p>
  83   <ol>
  84     <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, int }</tt>
  85     but rather <tt>{ float*, int }*</tt>. That is, <tt>%MyStruct</tt> is a
  86     pointer to a structure containing a pointer to a <tt>float</tt> and an
  87     <tt>int</tt>.</li>
  88     <li>Point #1 is evidenced by noticing the type of the first operand of
  89     the GEP instruction (<tt>%MyStruct</tt>) which is
  90     <tt>{ float*, int }*</tt>.</li>
  91     <li>The first index, <tt>long 0</tt> is required to dereference the
  92     pointer associated with <tt>%MyStruct</tt>.</li>
  93     <li>The second index, <tt>ubyte 1</tt> selects the second field of the
  94     structure (the <tt>int</tt>). </li>
  95   </ol>
  96 </div>
  97
  98 <!-- *********************************************************************** -->
  99 <div class="doc_subsection">
 100   <a name="deref"><b>What is dereferenced by GEP?</b></a>
 101 </div>
 102 <div class="doc_text">
 103   <p>Quick answer: nothing.</p>
 104   <p>The GetElementPtr instruction dereferences nothing. That is, it doesn't
 105   access memory in any way. That's what the Load instruction is for. GEP is
 106   only involved in the computation of addresses. For example, consider this:</p>
 107   <pre>
 108   %MyVar = uninitialized global { [40 x int ]* }
 109   ...
 110   %idx = getelementptr { [40 x int]* }* %MyVar, long 0, ubyte 0, long 0, long 17</pre>
 111   <p>In this example, we have a global variable, <tt>%MyVar</tt> that is a
 112   pointer to a structure containing a pointer to an array of 40 ints. The
 113   GEP instruction seems to be accessing the 18th integer of of the structure's
 114   array of ints. However, this is actually an illegal GEP instruction. It
 115   won't compile. The reason is that the pointer in the structure <i>must</i>
 116   be dereferenced in order to index into the array of 40 ints. Since the
 117   GEP instruction never accesses memory, it is illegal.</p>
 118   <p>In order to access the 18th integer in the array, you would need to do the
 119   following:</p>
 120   <pre>
 121   %idx = getelementptr { [40 x int]* }* %, long 0, ubyte 0
 122   %arr = load [40 x int]** %idx
 123   %idx = getelementptr [40 x int]* %arr, long 0, long 17</pre>
 124   <p>In this case, we have to load the pointer in the structure with a load
 125   instruction before we can index into the array. If the example was changed
 126   to:</p>
 127   <pre>
 128   %MyVar = uninitialized global { [40 x int ] }
 129   ...
 130   %idx = getelementptr { [40 x int] }*, long 0, ubyte 0, long 17</pre>
 131   <p>then everything works fine. In this case, the structure does not contain a
 132   pointer and the GEP instruction can index through the global variable pointer,
 133   into the first field of the structure and access the 18th <tt>int</tt> in the
 134   array there.</p>
 135 </div>
 136
 137 <!-- *********************************************************************** -->
 138 <div class="doc_subsection">
 139   <a name="firstptr"><b>Why can you index through the first pointer?</b></a>
 140 </div>
 141 <div class="doc_text">
 142   <p>Quick answer: Because its already present.</p>
 143   <p>Having understood the <a href="#deref">previous question</a>, a new
 144   question then arises:</p>
 145   <blockquote><i>Why is it okay to index through the first pointer, but
 146       subsequent pointers won't be dereferenced?</i></blockquote>
 147   <p>The answer is simply because
 148   memory does not have to be accessed to perform the computation. The first
 149   operand to the GEP instruction must be a value of a pointer type. The value
 150   of the pointer is provided directly to the GEP instruction without any need
 151   for accessing memory. It must, therefore be indexed like any other operand.
 152   Consider this example:</p>
 153   <pre>
 154   %MyVar = unintialized global int
 155   ...
 156   %idx1 = getelementptr int* %MyVar, long 0
 157   %idx2 = getelementptr int* %MyVar, long 1
 158   %idx3 = getelementptr int* %MyVar, long 2</pre>
 159   <p>These GEP instructions are simply making address computations from the
 160   base address of <tt>MyVar</tt>.  They compute, as follows (using C syntax):</p>
 161   <ul>
 162     <li> idx1 = &amp;MyVar + 0</li>
 163     <li> idx2 = &amp;MyVar + 4</li>
 164     <li> idx3 = &amp;MyVar = 8</li>
 165   </ul>
 166   <p>Since the type <tt>int</tt> is known to be four bytes long, the indices
 167   0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No
 168   memory is accessed to make these computations because the address of
 169   <tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
 170   <p>Note that the cases of <tt>%idx2</tt> and <tt>%idx3</tt> are a bit silly.
 171   They are computing addresses of something of unknown type (and thus
 172   potentially breaking type safety) because <tt>%MyVar</tt> is only one
 173   integer long.</p>
 174 </div>
 175
 176 <!-- *********************************************************************** -->
 177 <div class="doc_subsection">
 178   <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
 179 </div>
 180 <div class="doc_text">
 181   <p>Quick Answer: They compute different address locations.</p>
 182   <p>If you look at the first indices in these GEP
 183   instructions you find that they are different (0 and 1), therefore the address
 184   computation diverges with that index. Consider this example:</p>
 185   <pre>
 186   %MyVar = global { [10 x int ] }
 187   %idx1 = getlementptr { [10 x int ] }* %MyVar, long 0, byte 0, long 1
 188   %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre>
 189   <p>In this example, <tt>idx1</tt> computes the address of the second integer
 190   in the array that is in the structure in %MyVar, that is <tt>MyVar+4</tt>. The
 191   type of <tt>idx1</tt> is <tt>int*</tt>. However, <tt>idx2</tt> computes the
 192   address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of
 193   <tt>idx2</tt> is <tt>{ [10 x int] }*</tt> and its value is equivalent
 194   to <tt>MyVar + 40</tt> because it indexes past the ten 4-byte integers
 195   in <tt>MyVar</tt>. Obviously, in such a situation, the pointers don't
 196   alias.</p>
 197 </div>
 198
 199 <!-- *********************************************************************** -->
 200 <div class="doc_subsection">
 201   <a name="lead0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
 202 </div>
 203 <div class="doc_text">
 204   <p>Quick Answer: They compute the same address location.</p>
 205   <p>These two GEP instructions will compute the same address because indexing
 206   through the 0th element does not change the address. However, it does change
 207   the type. Consider this example:</p>
 208   <pre>
 209   %MyVar = global { [10 x int ] }
 210   %idx1 = getlementptr { [10 x int ] }* %MyVar, long 1, byte 0, long 0
 211   %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre>
 212   <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
 213   its type is <tt>int*</tt>. The value of <tt>%idx2</tt> is also
 214   <tt>MyVar+40</tt> but its type is <tt>{ [10 x int] }*</tt>.</p>
 215 </div>
 216
 217 <!-- *********************************************************************** -->
 218 <div class="doc_section"><a name="summary"><b>Summary</b></a></div>
 219 <!-- *********************************************************************** -->
 220
 221 <div class="doc_text">
 222   <p>In summary, here's some things to always remember about the GetElementPtr
 223   instruction:</p>
 224   <ol>
 225     <li>The GEP instruction never accesses memory, it only provides pointer
 226     computations.</li>
 227     <li>The first operand to the GEP instruction is always a pointer and it must
 228     be indexed.</li>
 229     <li>There are no superfluous indices for the GEP instruction.</li>
 230     <li>Trailing zero indices are superfluous for pointer aliasing, but not for
 231     the types of the pointers.</li>
 232     <li>Leading zero indices are not superfluous for pointer aliasing nor the
 233     types of the pointers.</li>
 234   </ol>
 235 </div>
 236
 237 <!-- *********************************************************************** -->
 238
 239 <hr>
 240 <address>
 241   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 242   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 243   <a href="http://validator.w3.org/check/referer"><img
 244   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
 245   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
 246   Last modified: $Date$
 247 </address>
 248 </body>
 249 </html>