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   <style type="text/css">
   9     TABLE   { text-align: left; border: 1px solid black; border-collapse: collapse; margin: 0 0 0 0; }
  10   </style>
  11 </head>
  12 <body>
  13
  14 <div class="doc_title">
  15   The Often Misunderstood GEP Instruction
  16 </div>
  17
  18 <ol>
  19   <li><a href="#intro">Introduction</a></li>
  20   <li><a href="#questions">The Questions</a>
  21   <ol>
  22     <li><a href="#extra_index">Why is the extra 0 index required?</a></li>
  23     <li><a href="#deref">What is dereferenced by GEP?</a></li>
  24     <li><a href="#firstptr">Why can you index through the first pointer but not
  25       subsequent ones?</a></li>
  26     <li><a href="#lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
  27     <li><a href="#trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
  28   </ol></li>
  29   <li><a href="#summary">Summary</a></li>
  30 </ol>
  31
  32 <div class="doc_author">
  33   <p>Written by: <a href="mailto:rspencer@reidspencer.com">Reid Spencer</a>.</p>
  34 </div>
  35
  36
  37 <!-- *********************************************************************** -->
  38 <div class="doc_section"><a name="intro"><b>Introduction</b></a></div>
  39 <!-- *********************************************************************** -->
  40 <div class="doc_text">
  41   <p>This document seeks to dispel the mystery and confusion surrounding LLVM's
  42   GetElementPtr (GEP) instruction. Questions about the wiley GEP instruction are
  43   probably the most frequently occuring questions once a developer gets down to
  44   coding with LLVM. Here we lay out the sources of confusion and show that the
  45   GEP instruction is really quite simple.
  46   </p>
  47 </div>
  48
  49 <!-- *********************************************************************** -->
  50 <div class="doc_section"><a name="questions"><b>The Questions</b></a></div>
  51 <!-- *********************************************************************** -->
  52 <div class="doc_text">
  53   <p>When people are first confronted with the GEP instruction, they tend to
  54   relate it to known concepts from other programming paradigms, most notably C
  55   array indexing and field selection. However, GEP is a little different and
  56   this leads to the following questions, all of which are answered in the
  57   following sections.</p>
  58   <ol>
  59     <li><a href="#firstptr">What is the first index of the GEP instruction?</a>
  60     </li>
  61     <li><a href="#extra_index">Why is the extra 0 index required?</a></li>
  62     <li><a href="#deref">What is dereferenced by GEP?</a></li>
  63     <li><a href="#lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
  64     <li><a href="#trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
  65   </ol>
  66 </div>
  67
  68 <!-- *********************************************************************** -->
  69 <div class="doc_subsection">
  70   <a name="firstptr"><b>What is the first index of the GEP instruction?</b></a>
  71 </div>
  72 <div class="doc_text">
  73   <p>Quick answer: The index stepping through the first operand.</p>
  74   <p>The confusion with the first index usually arises from thinking about
  75   the GetElementPtr instruction as if it was a C index operator. They aren't the
  76   same. For example, when we write, in "C":</p>
  77   <pre>
  78   AType* Foo;
  79   ...
  80   X = &amp;Foo-&gt;F;</pre>
  81   <p>it is natural to think that there is only one index, the selection of the
  82   field <tt>F</tt>.  However, in this example, <tt>Foo</tt> is a pointer. That
  83   pointer must be indexed explicitly in LLVM. C, on the other hand, indexs
  84   through it transparently.  To arrive at the same address location as the C
  85   code, you would provide the GEP instruction with two index operands. The
  86   first operand indexes through the pointer; the second operand indexes the
  87   field <tt>F</tt> of the structure, just as if you wrote:</p>
  88   <pre>
  89   X = &amp;Foo[0].F;</pre>
  90   <p>Sometimes this question gets rephrased as:</p>
  91   <blockquote><p><i>Why is it okay to index through the first pointer, but
  92       subsequent pointers won't be dereferenced?</i></p></blockquote>
  93   <p>The answer is simply because memory does not have to be accessed to
  94   perform the computation. The first operand to the GEP instruction must be a
  95   value of a pointer type. The value of the pointer is provided directly to
  96   the GEP instruction as an operand without any need for accessing memory. It
  97   must, therefore be indexed and requires an index operand. Consider this
  98   example:</p>
  99   <pre>
 100   struct munger_struct {
 101     int f1;
 102     int f2;
 103   };
 104   void munge(struct munger_struct *P)
 105   {
 106     P[0].f1 = P[1].f1 + P[2].f2;
 107   }
 108   ...
 109   munger_struct Array[3];
 110   ...
 111   munge(Array);</pre>
 112   <p>In this "C" example, the front end compiler (llvm-gcc) will generate three
 113   GEP instructions for the three indices through "P" in the assignment
 114   statement.  The function argument <tt>P</tt> will be the first operand of each
 115   of these GEP instructions.  The second operand indexes through that pointer.
 116   The third operand will be the field offset into the
 117   <tt>struct munger_struct</tt> type,  for either the <tt>f1</tt> or
 118   <tt>f2</tt> field. So, in LLVM assembly the <tt>munge</tt> function looks
 119   like:</p>
 120   <pre>
 121   void %munge(%struct.munger_struct* %P) {
 122   entry:
 123     %tmp = getelementptr %struct.munger_struct* %P, i32 1, i32 0
 124     %tmp = load i32* %tmp
 125     %tmp6 = getelementptr %struct.munger_struct* %P, i32 2, i32 1
 126     %tmp7 = load i32* %tmp6
 127     %tmp8 = add i32 %tmp7, %tmp
 128     %tmp9 = getelementptr %struct.munger_struct* %P, i32 0, i32 0
 129     store i32 %tmp8, i32* %tmp9
 130     ret void
 131   }</pre>
 132   <p>In each case the first operand is the pointer through which the GEP
 133   instruction starts. The same is true whether the first operand is an
 134   argument, allocated memory, or a global variable. </p>
 135   <p>To make this clear, let's consider a more obtuse example:</p>
 136   <pre>
 137   %MyVar = unintialized global i32
 138   ...
 139   %idx1 = getelementptr i32* %MyVar, i64 0
 140   %idx2 = getelementptr i32* %MyVar, i64 1
 141   %idx3 = getelementptr i32* %MyVar, i64 2</pre>
 142   <p>These GEP instructions are simply making address computations from the
 143   base address of <tt>MyVar</tt>.  They compute, as follows (using C syntax):
 144   </p>
 145   <ul>
 146     <li> idx1 = (char*) &amp;MyVar + 0</li>
 147     <li> idx2 = (char*) &amp;MyVar + 4</li>
 148     <li> idx3 = (char*) &amp;MyVar + 8</li>
 149   </ul>
 150   <p>Since the type <tt>i32</tt> is known to be four bytes long, the indices
 151   0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No
 152   memory is accessed to make these computations because the address of
 153   <tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
 154   <p>The obtuse part of this example is in the cases of <tt>%idx2</tt> and
 155   <tt>%idx3</tt>. They result in the computation of addresses that point to
 156   memory past the end of the <tt>%MyVar</tt> global, which is only one
 157   <tt>i32</tt> long, not three <tt>i32</tt>s long.  While this is legal in LLVM,
 158   it is inadvisable because any load or store with the pointer that results
 159   from these GEP instructions would produce undefined results.</p>
 160 </div>
 161
 162 <!-- *********************************************************************** -->
 163 <div class="doc_subsection">
 164   <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
 165 </div>
 166 <!-- *********************************************************************** -->
 167 <div class="doc_text">
 168   <p>Quick answer: there are no superfluous indices.</p>
 169   <p>This question arises most often when the GEP instruction is applied to a
 170   global variable which is always a pointer type. For example, consider
 171   this:</p><pre>
 172   %MyStruct = uninitialized global { float*, i32 }
 173   ...
 174   %idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1</pre>
 175   <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed
 176   field of the structure <tt>%MyStruct</tt>. When people first look at it, they
 177   wonder why the <tt>i64 0</tt> index is needed. However, a closer inspection
 178   of how globals and GEPs work reveals the need. Becoming aware of the following
 179   facts will dispell the confusion:</p>
 180   <ol>
 181     <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, i32 }</tt>
 182     but rather <tt>{ float*, i32 }*</tt>. That is, <tt>%MyStruct</tt> is a
 183     pointer to a structure containing a pointer to a <tt>float</tt> and an
 184     <tt>i32</tt>.</li>
 185     <li>Point #1 is evidenced by noticing the type of the first operand of
 186     the GEP instruction (<tt>%MyStruct</tt>) which is
 187     <tt>{ float*, i32 }*</tt>.</li>
 188     <li>The first index, <tt>i64 0</tt> is required to step over the global
 189     variable <tt>%MyStruct</tt>.  Since the first argument to the GEP
 190     instruction must always be a value of pointer type, the first index
 191     steps through that pointer. A value of 0 means 0 elements offset from that
 192     pointer.</li>
 193     <li>The second index, <tt>i32 1</tt> selects the second field of the
 194     structure (the <tt>i32</tt>). </li>
 195   </ol>
 196 </div>
 197
 198 <!-- *********************************************************************** -->
 199 <div class="doc_subsection">
 200   <a name="deref"><b>What is dereferenced by GEP?</b></a>
 201 </div>
 202 <div class="doc_text">
 203   <p>Quick answer: nothing.</p>
 204   <p>The GetElementPtr instruction dereferences nothing. That is, it doesn't
 205   access memory in any way. That's what the Load and Store instructions are for.
 206   GEP is only involved in the computation of addresses. For example, consider
 207   this:</p>
 208   <pre>
 209   %MyVar = uninitialized global { [40 x i32 ]* }
 210   ...
 211   %idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17</pre>
 212   <p>In this example, we have a global variable, <tt>%MyVar</tt> that is a
 213   pointer to a structure containing a pointer to an array of 40 ints. The
 214   GEP instruction seems to be accessing the 18th integer of the structure's
 215   array of ints. However, this is actually an illegal GEP instruction. It
 216   won't compile. The reason is that the pointer in the structure <i>must</i>
 217   be dereferenced in order to index into the array of 40 ints. Since the
 218   GEP instruction never accesses memory, it is illegal.</p>
 219   <p>In order to access the 18th integer in the array, you would need to do the
 220   following:</p>
 221   <pre>
 222   %idx = getelementptr { [40 x i32]* }* %, i64 0, i32 0
 223   %arr = load [40 x i32]** %idx
 224   %idx = getelementptr [40 x i32]* %arr, i64 0, i64 17</pre>
 225   <p>In this case, we have to load the pointer in the structure with a load
 226   instruction before we can index into the array. If the example was changed
 227   to:</p>
 228   <pre>
 229   %MyVar = uninitialized global { [40 x i32 ] }
 230   ...
 231   %idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17</pre>
 232   <p>then everything works fine. In this case, the structure does not contain a
 233   pointer and the GEP instruction can index through the global variable,
 234   into the first field of the structure and access the 18th <tt>i32</tt> in the
 235   array there.</p>
 236 </div>
 237
 238 <!-- *********************************************************************** -->
 239 <div class="doc_subsection">
 240   <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
 241 </div>
 242 <div class="doc_text">
 243   <p>Quick Answer: They compute different address locations.</p>
 244   <p>If you look at the first indices in these GEP
 245   instructions you find that they are different (0 and 1), therefore the address
 246   computation diverges with that index. Consider this example:</p>
 247   <pre>
 248   %MyVar = global { [10 x i32 ] }
 249   %idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 0, i32 0, i64 1
 250   %idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1</pre>
 251   <p>In this example, <tt>idx1</tt> computes the address of the second integer
 252   in the array that is in the structure in %MyVar, that is <tt>MyVar+4</tt>. The
 253   type of <tt>idx1</tt> is <tt>i32*</tt>. However, <tt>idx2</tt> computes the
 254   address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of
 255   <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its value is equivalent
 256   to <tt>MyVar + 40</tt> because it indexes past the ten 4-byte integers
 257   in <tt>MyVar</tt>. Obviously, in such a situation, the pointers don't
 258   alias.</p>
 259 </div>
 260
 261 <!-- *********************************************************************** -->
 262 <div class="doc_subsection">
 263   <a name="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
 264 </div>
 265 <div class="doc_text">
 266   <p>Quick Answer: They compute the same address location.</p>
 267   <p>These two GEP instructions will compute the same address because indexing
 268   through the 0th element does not change the address. However, it does change
 269   the type. Consider this example:</p>
 270   <pre>
 271   %MyVar = global { [10 x i32 ] }
 272   %idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
 273   %idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1</pre>
 274   <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
 275   its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also
 276   <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
 277 </div>
 278
 279 <!-- *********************************************************************** -->
 280 <div class="doc_section"><a name="summary"><b>Summary</b></a></div>
 281 <!-- *********************************************************************** -->
 282
 283 <div class="doc_text">
 284   <p>In summary, here's some things to always remember about the GetElementPtr
 285   instruction:</p>
 286   <ol>
 287     <li>The GEP instruction never accesses memory, it only provides pointer
 288     computations.</li>
 289     <li>The first operand to the GEP instruction is always a pointer and it must
 290     be indexed.</li>
 291     <li>There are no superfluous indices for the GEP instruction.</li>
 292     <li>Trailing zero indices are superfluous for pointer aliasing, but not for
 293     the types of the pointers.</li>
 294     <li>Leading zero indices are not superfluous for pointer aliasing nor the
 295     types of the pointers.</li>
 296   </ol>
 297 </div>
 298
 299 <!-- *********************************************************************** -->
 300
 301 <hr>
 302 <address>
 303   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 304   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 305   <a href="http://validator.w3.org/check/referer"><img
 306   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
 307   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
 308   Last modified: $Date$
 309 </address>
 310 </body>
 311 </html>