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
  78 <div class="doc_code">
  79 <pre>
  80 AType *Foo;
  81 ...
  82 X = &amp;Foo-&gt;F;
  83 </pre>
  84 </div>
  85
  86   <p>it is natural to think that there is only one index, the selection of the
  87   field <tt>F</tt>.  However, in this example, <tt>Foo</tt> is a pointer. That
  88   pointer must be indexed explicitly in LLVM. C, on the other hand, indexs
  89   through it transparently.  To arrive at the same address location as the C
  90   code, you would provide the GEP instruction with two index operands. The
  91   first operand indexes through the pointer; the second operand indexes the
  92   field <tt>F</tt> of the structure, just as if you wrote:</p>
  93
  94 <div class="doc_code">
  95 <pre>
  96 X = &amp;Foo[0].F;
  97 </pre>
  98 </div>
  99
 100   <p>Sometimes this question gets rephrased as:</p>
 101   <blockquote><p><i>Why is it okay to index through the first pointer, but
 102       subsequent pointers won't be dereferenced?</i></p></blockquote>
 103   <p>The answer is simply because memory does not have to be accessed to
 104   perform the computation. The first operand to the GEP instruction must be a
 105   value of a pointer type. The value of the pointer is provided directly to
 106   the GEP instruction as an operand without any need for accessing memory. It
 107   must, therefore be indexed and requires an index operand. Consider this
 108   example:</p>
 109
 110 <div class="doc_code">
 111 <pre>
 112 struct munger_struct {
 113   int f1;
 114   int f2;
 115 };
 116 void munge(struct munger_struct *P) {
 117   P[0].f1 = P[1].f1 + P[2].f2;
 118 }
 119 ...
 120 munger_struct Array[3];
 121 ...
 122 munge(Array);
 123 </pre>
 124 </div>
 125
 126   <p>In this "C" example, the front end compiler (llvm-gcc) will generate three
 127   GEP instructions for the three indices through "P" in the assignment
 128   statement.  The function argument <tt>P</tt> will be the first operand of each
 129   of these GEP instructions.  The second operand indexes through that pointer.
 130   The third operand will be the field offset into the
 131   <tt>struct munger_struct</tt> type,  for either the <tt>f1</tt> or
 132   <tt>f2</tt> field. So, in LLVM assembly the <tt>munge</tt> function looks
 133   like:</p>
 134
 135 <div class="doc_code">
 136 <pre>
 137 void %munge(%struct.munger_struct* %P) {
 138 entry:
 139   %tmp = getelementptr %struct.munger_struct* %P, i32 1, i32 0
 140   %tmp = load i32* %tmp
 141   %tmp6 = getelementptr %struct.munger_struct* %P, i32 2, i32 1
 142   %tmp7 = load i32* %tmp6
 143   %tmp8 = add i32 %tmp7, %tmp
 144   %tmp9 = getelementptr %struct.munger_struct* %P, i32 0, i32 0
 145   store i32 %tmp8, i32* %tmp9
 146   ret void
 147 }
 148 </pre>
 149 </div>
 150
 151   <p>In each case the first operand is the pointer through which the GEP
 152   instruction starts. The same is true whether the first operand is an
 153   argument, allocated memory, or a global variable. </p>
 154   <p>To make this clear, let's consider a more obtuse example:</p>
 155
 156 <div class="doc_code">
 157 <pre>
 158 %MyVar = unintialized global i32
 159 ...
 160 %idx1 = getelementptr i32* %MyVar, i64 0
 161 %idx2 = getelementptr i32* %MyVar, i64 1
 162 %idx3 = getelementptr i32* %MyVar, i64 2
 163 </pre>
 164 </div>
 165
 166   <p>These GEP instructions are simply making address computations from the
 167   base address of <tt>MyVar</tt>.  They compute, as follows (using C syntax):
 168   </p>
 169
 170 <div class="doc_code">
 171 <pre>
 172 idx1 = (char*) &amp;MyVar + 0
 173 idx2 = (char*) &amp;MyVar + 4
 174 idx3 = (char*) &amp;MyVar + 8
 175 </pre>
 176 </div>
 177
 178   <p>Since the type <tt>i32</tt> is known to be four bytes long, the indices
 179   0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No
 180   memory is accessed to make these computations because the address of
 181   <tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
 182   <p>The obtuse part of this example is in the cases of <tt>%idx2</tt> and
 183   <tt>%idx3</tt>. They result in the computation of addresses that point to
 184   memory past the end of the <tt>%MyVar</tt> global, which is only one
 185   <tt>i32</tt> long, not three <tt>i32</tt>s long.  While this is legal in LLVM,
 186   it is inadvisable because any load or store with the pointer that results
 187   from these GEP instructions would produce undefined results.</p>
 188 </div>
 189
 190 <!-- *********************************************************************** -->
 191 <div class="doc_subsection">
 192   <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
 193 </div>
 194 <!-- *********************************************************************** -->
 195 <div class="doc_text">
 196   <p>Quick answer: there are no superfluous indices.</p>
 197   <p>This question arises most often when the GEP instruction is applied to a
 198   global variable which is always a pointer type. For example, consider
 199   this:</p>
 200
 201 <div class="doc_code">
 202 <pre>
 203 %MyStruct = uninitialized global { float*, i32 }
 204 ...
 205 %idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1
 206 </pre>
 207 </div>
 208
 209   <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed
 210   field of the structure <tt>%MyStruct</tt>. When people first look at it, they
 211   wonder why the <tt>i64 0</tt> index is needed. However, a closer inspection
 212   of how globals and GEPs work reveals the need. Becoming aware of the following
 213   facts will dispell the confusion:</p>
 214   <ol>
 215     <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, i32 }</tt>
 216     but rather <tt>{ float*, i32 }*</tt>. That is, <tt>%MyStruct</tt> is a
 217     pointer to a structure containing a pointer to a <tt>float</tt> and an
 218     <tt>i32</tt>.</li>
 219     <li>Point #1 is evidenced by noticing the type of the first operand of
 220     the GEP instruction (<tt>%MyStruct</tt>) which is
 221     <tt>{ float*, i32 }*</tt>.</li>
 222     <li>The first index, <tt>i64 0</tt> is required to step over the global
 223     variable <tt>%MyStruct</tt>.  Since the first argument to the GEP
 224     instruction must always be a value of pointer type, the first index
 225     steps through that pointer. A value of 0 means 0 elements offset from that
 226     pointer.</li>
 227     <li>The second index, <tt>i32 1</tt> selects the second field of the
 228     structure (the <tt>i32</tt>). </li>
 229   </ol>
 230 </div>
 231
 232 <!-- *********************************************************************** -->
 233 <div class="doc_subsection">
 234   <a name="deref"><b>What is dereferenced by GEP?</b></a>
 235 </div>
 236 <div class="doc_text">
 237   <p>Quick answer: nothing.</p>
 238   <p>The GetElementPtr instruction dereferences nothing. That is, it doesn't
 239   access memory in any way. That's what the Load and Store instructions are for.
 240   GEP is only involved in the computation of addresses. For example, consider
 241   this:</p>
 242
 243 <div class="doc_code">
 244 <pre>
 245 %MyVar = uninitialized global { [40 x i32 ]* }
 246 ...
 247 %idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17
 248 </pre>
 249 </div>
 250
 251   <p>In this example, we have a global variable, <tt>%MyVar</tt> that is a
 252   pointer to a structure containing a pointer to an array of 40 ints. The
 253   GEP instruction seems to be accessing the 18th integer of the structure's
 254   array of ints. However, this is actually an illegal GEP instruction. It
 255   won't compile. The reason is that the pointer in the structure <i>must</i>
 256   be dereferenced in order to index into the array of 40 ints. Since the
 257   GEP instruction never accesses memory, it is illegal.</p>
 258   <p>In order to access the 18th integer in the array, you would need to do the
 259   following:</p>
 260
 261 <div class="doc_code">
 262 <pre>
 263 %idx = getelementptr { [40 x i32]* }* %, i64 0, i32 0
 264 %arr = load [40 x i32]** %idx
 265 %idx = getelementptr [40 x i32]* %arr, i64 0, i64 17
 266 </pre>
 267 </div>
 268
 269   <p>In this case, we have to load the pointer in the structure with a load
 270   instruction before we can index into the array. If the example was changed
 271   to:</p>
 272
 273 <div class="doc_code">
 274 <pre>
 275 %MyVar = uninitialized global { [40 x i32 ] }
 276 ...
 277 %idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17
 278 </pre>
 279 </div>
 280
 281   <p>then everything works fine. In this case, the structure does not contain a
 282   pointer and the GEP instruction can index through the global variable,
 283   into the first field of the structure and access the 18th <tt>i32</tt> in the
 284   array there.</p>
 285 </div>
 286
 287 <!-- *********************************************************************** -->
 288 <div class="doc_subsection">
 289   <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
 290 </div>
 291 <div class="doc_text">
 292   <p>Quick Answer: They compute different address locations.</p>
 293   <p>If you look at the first indices in these GEP
 294   instructions you find that they are different (0 and 1), therefore the address
 295   computation diverges with that index. Consider this example:</p>
 296
 297 <div class="doc_code">
 298 <pre>
 299 %MyVar = global { [10 x i32 ] }
 300 %idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 0, i32 0, i64 1
 301 %idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1
 302 </pre>
 303 </div>
 304
 305   <p>In this example, <tt>idx1</tt> computes the address of the second integer
 306   in the array that is in the structure in %MyVar, that is <tt>MyVar+4</tt>. The
 307   type of <tt>idx1</tt> is <tt>i32*</tt>. However, <tt>idx2</tt> computes the
 308   address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of
 309   <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its value is equivalent
 310   to <tt>MyVar + 40</tt> because it indexes past the ten 4-byte integers
 311   in <tt>MyVar</tt>. Obviously, in such a situation, the pointers don't
 312   alias.</p>
 313 </div>
 314
 315 <!-- *********************************************************************** -->
 316 <div class="doc_subsection">
 317   <a name="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
 318 </div>
 319 <div class="doc_text">
 320   <p>Quick Answer: They compute the same address location.</p>
 321   <p>These two GEP instructions will compute the same address because indexing
 322   through the 0th element does not change the address. However, it does change
 323   the type. Consider this example:</p>
 324
 325 <div class="doc_code">
 326 <pre>
 327 %MyVar = global { [10 x i32 ] }
 328 %idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
 329 %idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1
 330 </pre>
 331 </div>
 332
 333   <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
 334   its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also
 335   <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
 336 </div>
 337
 338 <!-- *********************************************************************** -->
 339 <div class="doc_section"><a name="summary"><b>Summary</b></a></div>
 340 <!-- *********************************************************************** -->
 341
 342 <div class="doc_text">
 343   <p>In summary, here's some things to always remember about the GetElementPtr
 344   instruction:</p>
 345   <ol>
 346     <li>The GEP instruction never accesses memory, it only provides pointer
 347     computations.</li>
 348     <li>The first operand to the GEP instruction is always a pointer and it must
 349     be indexed.</li>
 350     <li>There are no superfluous indices for the GEP instruction.</li>
 351     <li>Trailing zero indices are superfluous for pointer aliasing, but not for
 352     the types of the pointers.</li>
 353     <li>Leading zero indices are not superfluous for pointer aliasing nor the
 354     types of the pointers.</li>
 355   </ol>
 356 </div>
 357
 358 <!-- *********************************************************************** -->
 359
 360 <hr>
 361 <address>
 362   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 363   src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
 364   <a href="http://validator.w3.org/check/referer"><img
 365   src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
 366   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
 367   Last modified: $Date$
 368 </address>
 369 </body>
 370 </html>