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="#addresses">Address Computation</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     <li><a href="#vectors">Can GEP index into vector elements?</a>
  29     <li><a href="#unions">Can GEP index into unions?</a>
  30     <li><a href="#addrspace">What effect do address spaces have on GEPs?</a>
  31     <li><a href="#int">How is GEP different from ptrtoint, arithmetic, and inttoptr?</a></li>
  32     <li><a href="#be">I'm writing a backend for a target which needs custom lowering for GEP. How do I do this?</a>
  33     <li><a href="#vla">How does VLA addressing work with GEPs?</a>
  34   </ol></li>
  35   <li><a href="#rules">Rules</a>
  36   <ol>
  37     <li><a href="#bounds">What happens if an array index is out of bounds?</a>
  38     <li><a href="#negative">Can array indices be negative?</a>
  39     <li><a href="#compare">Can I compare two values computed with GEPs?</a>
  40     <li><a href="#types">Can I do GEP with a different pointer type than the type of the underlying object?</a>
  41     <li><a href="#null">Can I cast an object's address to integer and add it to null?</a>
  42     <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>
  43     <li><a href="#tbaa">Can I do type-based alias analysis on LLVM IR?</a>
  44     <li><a href="#overflow">What happens if a GEP computation overflows?</a>
  45     <li><a href="#check">How can I tell if my front-end is following the rules?</a>
  46   </ol></li>
  47   <li><a href="#rationale">Rationale</a>
  48   <ol>
  49     <li><a href="#goals">Why is GEP designed this way?</a></li>
  50     <li><a href="#i32">Why do struct member indices always use i32?</a></li>
  51     <li><a href="#uglygep">What's an uglygep?</a>
  52   </ol></li>
  53   <li><a href="#summary">Summary</a></li>
  54 </ol>
  55
  56 <div class="doc_author">
  57   <p>Written by: <a href="mailto:rspencer@reidspencer.com">Reid Spencer</a>.</p>
  58 </div>
  59
  60
  61 <!-- *********************************************************************** -->
  62 <div class="doc_section"><a name="intro"><b>Introduction</b></a></div>
  63 <!-- *********************************************************************** -->
  64
  65 <div class="doc_text">
  66   <p>This document seeks to dispel the mystery and confusion surrounding LLVM's
  67   <a href="LangRef.html#i_getelementptr">GetElementPtr</a> (GEP) instruction.
  68   Questions about the wily GEP instruction are
  69   probably the most frequently occurring questions once a developer gets down to
  70   coding with LLVM. Here we lay out the sources of confusion and show that the
  71   GEP instruction is really quite simple.
  72   </p>
  73 </div>
  74
  75 <!-- *********************************************************************** -->
  76 <div class="doc_section"><a name="addresses"><b>Address Computation</b></a></div>
  77 <!-- *********************************************************************** -->
  78 <div class="doc_text">
  79   <p>When people are first confronted with the GEP instruction, they tend to
  80   relate it to known concepts from other programming paradigms, most notably C
  81   array indexing and field selection. GEP closely resembles C array indexing
  82   and field selection, however it's is a little different and this leads to
  83   the following questions.</p>
  84 </div>
  85
  86 <!-- *********************************************************************** -->
  87 <div class="doc_subsection">
  88   <a name="firstptr"><b>What is the first index of the GEP instruction?</b></a>
  89 </div>
  90 <div class="doc_text">
  91   <p>Quick answer: The index stepping through the first operand.</p>
  92   <p>The confusion with the first index usually arises from thinking about
  93   the GetElementPtr instruction as if it was a C index operator. They aren't the
  94   same. For example, when we write, in "C":</p>
  95
  96 <div class="doc_code">
  97 <pre>
  98 AType *Foo;
  99 ...
 100 X = &amp;Foo-&gt;F;
 101 </pre>
 102 </div>
 103
 104   <p>it is natural to think that there is only one index, the selection of the
 105   field <tt>F</tt>.  However, in this example, <tt>Foo</tt> is a pointer. That
 106   pointer must be indexed explicitly in LLVM. C, on the other hand, indices
 107   through it transparently.  To arrive at the same address location as the C
 108   code, you would provide the GEP instruction with two index operands. The
 109   first operand indexes through the pointer; the second operand indexes the
 110   field <tt>F</tt> of the structure, just as if you wrote:</p>
 111
 112 <div class="doc_code">
 113 <pre>
 114 X = &amp;Foo[0].F;
 115 </pre>
 116 </div>
 117
 118   <p>Sometimes this question gets rephrased as:</p>
 119   <blockquote><p><i>Why is it okay to index through the first pointer, but
 120       subsequent pointers won't be dereferenced?</i></p></blockquote>
 121   <p>The answer is simply because memory does not have to be accessed to
 122   perform the computation. The first operand to the GEP instruction must be a
 123   value of a pointer type. The value of the pointer is provided directly to
 124   the GEP instruction as an operand without any need for accessing memory. It
 125   must, therefore be indexed and requires an index operand. Consider this
 126   example:</p>
 127
 128 <div class="doc_code">
 129 <pre>
 130 struct munger_struct {
 131   int f1;
 132   int f2;
 133 };
 134 void munge(struct munger_struct *P) {
 135   P[0].f1 = P[1].f1 + P[2].f2;
 136 }
 137 ...
 138 munger_struct Array[3];
 139 ...
 140 munge(Array);
 141 </pre>
 142 </div>
 143
 144   <p>In this "C" example, the front end compiler (llvm-gcc) will generate three
 145   GEP instructions for the three indices through "P" in the assignment
 146   statement.  The function argument <tt>P</tt> will be the first operand of each
 147   of these GEP instructions.  The second operand indexes through that pointer.
 148   The third operand will be the field offset into the
 149   <tt>struct munger_struct</tt> type,  for either the <tt>f1</tt> or
 150   <tt>f2</tt> field. So, in LLVM assembly the <tt>munge</tt> function looks
 151   like:</p>
 152
 153 <div class="doc_code">
 154 <pre>
 155 void %munge(%struct.munger_struct* %P) {
 156 entry:
 157   %tmp = getelementptr %struct.munger_struct* %P, i32 1, i32 0
 158   %tmp = load i32* %tmp
 159   %tmp6 = getelementptr %struct.munger_struct* %P, i32 2, i32 1
 160   %tmp7 = load i32* %tmp6
 161   %tmp8 = add i32 %tmp7, %tmp
 162   %tmp9 = getelementptr %struct.munger_struct* %P, i32 0, i32 0
 163   store i32 %tmp8, i32* %tmp9
 164   ret void
 165 }
 166 </pre>
 167 </div>
 168
 169   <p>In each case the first operand is the pointer through which the GEP
 170   instruction starts. The same is true whether the first operand is an
 171   argument, allocated memory, or a global variable. </p>
 172   <p>To make this clear, let's consider a more obtuse example:</p>
 173
 174 <div class="doc_code">
 175 <pre>
 176 %MyVar = uninitialized global i32
 177 ...
 178 %idx1 = getelementptr i32* %MyVar, i64 0
 179 %idx2 = getelementptr i32* %MyVar, i64 1
 180 %idx3 = getelementptr i32* %MyVar, i64 2
 181 </pre>
 182 </div>
 183
 184   <p>These GEP instructions are simply making address computations from the
 185   base address of <tt>MyVar</tt>.  They compute, as follows (using C syntax):
 186   </p>
 187
 188 <div class="doc_code">
 189 <pre>
 190 idx1 = (char*) &amp;MyVar + 0
 191 idx2 = (char*) &amp;MyVar + 4
 192 idx3 = (char*) &amp;MyVar + 8
 193 </pre>
 194 </div>
 195
 196   <p>Since the type <tt>i32</tt> is known to be four bytes long, the indices
 197   0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No
 198   memory is accessed to make these computations because the address of
 199   <tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
 200   <p>The obtuse part of this example is in the cases of <tt>%idx2</tt> and
 201   <tt>%idx3</tt>. They result in the computation of addresses that point to
 202   memory past the end of the <tt>%MyVar</tt> global, which is only one
 203   <tt>i32</tt> long, not three <tt>i32</tt>s long.  While this is legal in LLVM,
 204   it is inadvisable because any load or store with the pointer that results
 205   from these GEP instructions would produce undefined results.</p>
 206 </div>
 207
 208 <!-- *********************************************************************** -->
 209 <div class="doc_subsection">
 210   <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
 211 </div>
 212 <!-- *********************************************************************** -->
 213 <div class="doc_text">
 214   <p>Quick answer: there are no superfluous indices.</p>
 215   <p>This question arises most often when the GEP instruction is applied to a
 216   global variable which is always a pointer type. For example, consider
 217   this:</p>
 218
 219 <div class="doc_code">
 220 <pre>
 221 %MyStruct = uninitialized global { float*, i32 }
 222 ...
 223 %idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1
 224 </pre>
 225 </div>
 226
 227   <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed
 228   field of the structure <tt>%MyStruct</tt>. When people first look at it, they
 229   wonder why the <tt>i64 0</tt> index is needed. However, a closer inspection
 230   of how globals and GEPs work reveals the need. Becoming aware of the following
 231   facts will dispel the confusion:</p>
 232   <ol>
 233     <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, i32 }</tt>
 234     but rather <tt>{ float*, i32 }*</tt>. That is, <tt>%MyStruct</tt> is a
 235     pointer to a structure containing a pointer to a <tt>float</tt> and an
 236     <tt>i32</tt>.</li>
 237     <li>Point #1 is evidenced by noticing the type of the first operand of
 238     the GEP instruction (<tt>%MyStruct</tt>) which is
 239     <tt>{ float*, i32 }*</tt>.</li>
 240     <li>The first index, <tt>i64 0</tt> is required to step over the global
 241     variable <tt>%MyStruct</tt>.  Since the first argument to the GEP
 242     instruction must always be a value of pointer type, the first index
 243     steps through that pointer. A value of 0 means 0 elements offset from that
 244     pointer.</li>
 245     <li>The second index, <tt>i32 1</tt> selects the second field of the
 246     structure (the <tt>i32</tt>). </li>
 247   </ol>
 248 </div>
 249
 250 <!-- *********************************************************************** -->
 251 <div class="doc_subsection">
 252   <a name="deref"><b>What is dereferenced by GEP?</b></a>
 253 </div>
 254 <div class="doc_text">
 255   <p>Quick answer: nothing.</p>
 256   <p>The GetElementPtr instruction dereferences nothing. That is, it doesn't
 257   access memory in any way. That's what the Load and Store instructions are for.
 258   GEP is only involved in the computation of addresses. For example, consider
 259   this:</p>
 260
 261 <div class="doc_code">
 262 <pre>
 263 %MyVar = uninitialized global { [40 x i32 ]* }
 264 ...
 265 %idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17
 266 </pre>
 267 </div>
 268
 269   <p>In this example, we have a global variable, <tt>%MyVar</tt> that is a
 270   pointer to a structure containing a pointer to an array of 40 ints. The
 271   GEP instruction seems to be accessing the 18th integer of the structure's
 272   array of ints. However, this is actually an illegal GEP instruction. It
 273   won't compile. The reason is that the pointer in the structure <i>must</i>
 274   be dereferenced in order to index into the array of 40 ints. Since the
 275   GEP instruction never accesses memory, it is illegal.</p>
 276   <p>In order to access the 18th integer in the array, you would need to do the
 277   following:</p>
 278
 279 <div class="doc_code">
 280 <pre>
 281 %idx = getelementptr { [40 x i32]* }* %, i64 0, i32 0
 282 %arr = load [40 x i32]** %idx
 283 %idx = getelementptr [40 x i32]* %arr, i64 0, i64 17
 284 </pre>
 285 </div>
 286
 287   <p>In this case, we have to load the pointer in the structure with a load
 288   instruction before we can index into the array. If the example was changed
 289   to:</p>
 290
 291 <div class="doc_code">
 292 <pre>
 293 %MyVar = uninitialized global { [40 x i32 ] }
 294 ...
 295 %idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17
 296 </pre>
 297 </div>
 298
 299   <p>then everything works fine. In this case, the structure does not contain a
 300   pointer and the GEP instruction can index through the global variable,
 301   into the first field of the structure and access the 18th <tt>i32</tt> in the
 302   array there.</p>
 303 </div>
 304
 305 <!-- *********************************************************************** -->
 306 <div class="doc_subsection">
 307   <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
 308 </div>
 309 <div class="doc_text">
 310   <p>Quick Answer: They compute different address locations.</p>
 311   <p>If you look at the first indices in these GEP
 312   instructions you find that they are different (0 and 1), therefore the address
 313   computation diverges with that index. Consider this example:</p>
 314
 315 <div class="doc_code">
 316 <pre>
 317 %MyVar = global { [10 x i32 ] }
 318 %idx1 = getelementptr { [10 x i32 ] }* %MyVar, i64 0, i32 0, i64 1
 319 %idx2 = getelementptr { [10 x i32 ] }* %MyVar, i64 1
 320 </pre>
 321 </div>
 322
 323   <p>In this example, <tt>idx1</tt> computes the address of the second integer
 324   in the array that is in the structure in <tt>%MyVar</tt>, that is
 325   <tt>MyVar+4</tt>. The type of <tt>idx1</tt> is <tt>i32*</tt>. However,
 326   <tt>idx2</tt> computes the address of <i>the next</i> structure after
 327   <tt>%MyVar</tt>. The type of <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its
 328   value is equivalent to <tt>MyVar + 40</tt> because it indexes past the ten
 329   4-byte integers in <tt>MyVar</tt>. Obviously, in such a situation, the
 330   pointers don't alias.</p>
 331
 332 </div>
 333
 334 <!-- *********************************************************************** -->
 335 <div class="doc_subsection">
 336   <a name="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
 337 </div>
 338 <div class="doc_text">
 339   <p>Quick Answer: They compute the same address location.</p>
 340   <p>These two GEP instructions will compute the same address because indexing
 341   through the 0th element does not change the address. However, it does change
 342   the type. Consider this example:</p>
 343
 344 <div class="doc_code">
 345 <pre>
 346 %MyVar = global { [10 x i32 ] }
 347 %idx1 = getelementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
 348 %idx2 = getelementptr { [10 x i32 ] }* %MyVar, i64 1
 349 </pre>
 350 </div>
 351
 352   <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
 353   its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also
 354   <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
 355 </div>
 356
 357 <!-- *********************************************************************** -->
 358
 359 <div class="doc_subsection">
 360   <a name="vectors"><b>Can GEP index into vector elements?</b></a>
 361 </div>
 362 <div class="doc_text">
 363   <p>This hasn't always been forcefully disallowed, though it's not recommended.
 364      It leads to awkward special cases in the optimizers, and fundamental
 365      inconsistency in the IR. In the future, it will probably be outright
 366      disallowed.</p>
 367
 368 </div>
 369
 370 <!-- *********************************************************************** -->
 371
 372 <div class="doc_subsection">
 373   <a name="unions"><b>Can GEP index into unions?</b></a>
 374 </div>
 375 <div class="doc_text">
 376    <p>Unknown.</p>
 377
 378 </div>
 379
 380 <!-- *********************************************************************** -->
 381
 382 <div class="doc_subsection">
 383   <a name="addrspace"><b>What effect do address spaces have on GEPs?</b></a>
 384 </div>
 385 <div class="doc_text">
 386    <p>None, except that the address space qualifier on the first operand pointer
 387       type always matches the address space qualifier on the result type.</p>
 388
 389 </div>
 390
 391 <!-- *********************************************************************** -->
 392
 393 <div class="doc_subsection">
 394   <a name="int"><b>How is GEP different from ptrtoint, arithmetic,
 395                    and inttoptr?</b></a>
 396 </div>
 397 <div class="doc_text">
 398   <p>It's very similar; there are only subtle differences.</p>
 399
 400   <p>With ptrtoint, you have to pick an integer type. One approach is to pick i64;
 401      this is safe on everything LLVM supports (LLVM internally assumes pointers
 402      are never wider than 64 bits in many places), and the optimizer will actually
 403      narrow the i64 arithmetic down to the actual pointer size on targets which
 404      don't support 64-bit arithmetic in most cases. However, there are some cases
 405      where it doesn't do this. With GEP you can avoid this problem.
 406
 407   <p>Also, GEP carries additional pointer aliasing rules. It's invalid to take a
 408      GEP from one object, address into a different separately allocated
 409      object, and dereference it. IR producers (front-ends) must follow this rule,
 410      and consumers (optimizers, specifically alias analysis) benefit from being
 411      able to rely on it. See the <a href="#rules">Rules</a> section for more
 412      information.</p>
 413
 414   <p>And, GEP is more concise in common cases.</p>
 415
 416   <p>However, for the underlying integer computation implied, there
 417      is no difference.</p>
 418
 419 </div>
 420
 421 <!-- *********************************************************************** -->
 422
 423 <div class="doc_subsection">
 424   <a name="be"><b>I'm writing a backend for a target which needs custom
 425                   lowering for GEP. How do I do this?</b></a>
 426 </div>
 427 <div class="doc_text">
 428   <p>You don't. The integer computation implied by a GEP is target-independent.
 429      Typically what you'll need to do is make your backend pattern-match
 430      expressions trees involving ADD, MUL, etc., which are what GEP is lowered
 431      into. This has the advantage of letting your code work correctly in more
 432      cases.</p>
 433
 434   <p>GEP does use target-dependent parameters for the size and layout of data
 435      types, which targets can customize.</p>
 436
 437   <p>If you require support for addressing units which are not 8 bits, you'll
 438      need to fix a lot of code in the backend, with GEP lowering being only a
 439      small piece of the overall picture.</p>
 440
 441 </div>
 442
 443 <!-- *********************************************************************** -->
 444
 445 <div class="doc_subsection">
 446   <a name="vla"><b>How does VLA addressing work with GEPs?</b></a>
 447 </div>
 448 <div class="doc_text">
 449   <p>GEPs don't natively support VLAs. LLVM's type system is entirely static,
 450      and GEP address computations are guided by an LLVM type.</p>
 451
 452   <p>VLA indices can be implemented as linearized indices. For example, an
 453      expression like X[a][b][c], must be effectively lowered into a form
 454      like X[a*m+b*n+c], so that it appears to the GEP as a single-dimensional
 455      array reference.</p>
 456
 457   <p>This means if you want to write an analysis which understands array
 458      indices and you want to support VLAs, your code will have to be
 459      prepared to reverse-engineer the linearization. One way to solve this
 460      problem is to use the ScalarEvolution library, which always presents
 461      VLA and non-VLA indexing in the same manner.</p>
 462 </div>
 463
 464 <!-- *********************************************************************** -->
 465 <div class="doc_section"><a name="rules"><b>Rules</b></a></div>
 466 <!-- *********************************************************************** -->
 467
 468 <!-- *********************************************************************** -->
 469
 470 <div class="doc_subsection">
 471   <a name="bounds"><b>What happens if an array index is out of bounds?</b></a>
 472 </div>
 473 <div class="doc_text">
 474   <p>There are two senses in which an array index can be out of bounds.</p>
 475
 476   <p>First, there's the array type which comes from the (static) type of
 477      the first operand to the GEP. Indices greater than the number of elements
 478      in the corresponding static array type are valid. There is no problem with
 479      out of bounds indices in this sense. Indexing into an array only depends
 480      on the size of the array element, not the number of elements.</p>
 481
 482   <p>A common example of how this is used is arrays where the size is not known.
 483      It's common to use array types with zero length to represent these. The
 484      fact that the static type says there are zero elements is irrelevant; it's
 485      perfectly valid to compute arbitrary element indices, as the computation
 486      only depends on the size of the array element, not the number of
 487      elements. Note that zero-sized arrays are not a special case here.</p>
 488
 489   <p>This sense is unconnected with <tt>inbounds</tt> keyword. The
 490      <tt>inbounds</tt> keyword is designed to describe low-level pointer
 491      arithmetic overflow conditions, rather than high-level array
 492      indexing rules.
 493
 494   <p>Analysis passes which wish to understand array indexing should not
 495      assume that the static array type bounds are respected.</p>
 496
 497   <p>The second sense of being out of bounds is computing an address that's
 498      beyond the actual underlying allocated object.</p>
 499
 500   <p>With the <tt>inbounds</tt> keyword, the result value of the GEP is
 501      undefined if the address is outside the actual underlying allocated
 502      object and not the address one-past-the-end.</p>
 503
 504   <p>Without the <tt>inbounds</tt> keyword, there are no restrictions
 505      on computing out-of-bounds addresses. Obviously, performing a load or
 506      a store requires an address of allocated and sufficiently aligned
 507      memory. But the GEP itself is only concerned with computing addresses.</p>
 508
 509 </div>
 510
 511 <!-- *********************************************************************** -->
 512 <div class="doc_subsection">
 513   <a name="negative"><b>Can array indices be negative?</b></a>
 514 </div>
 515 <div class="doc_text">
 516   <p>Yes. This is basically a special case of array indices being out
 517      of bounds.</p>
 518
 519 </div>
 520
 521 <!-- *********************************************************************** -->
 522 <div class="doc_subsection">
 523   <a name="compare"><b>Can I compare two values computed with GEPs?</b></a>
 524 </div>
 525 <div class="doc_text">
 526   <p>Yes. If both addresses are within the same allocated object, or
 527      one-past-the-end, you'll get the comparison result you expect. If either
 528      is outside of it, integer arithmetic wrapping may occur, so the
 529      comparison may not be meaningful.</p>
 530
 531 </div>
 532
 533 <!-- *********************************************************************** -->
 534 <div class="doc_subsection">
 535   <a name="types"><b>Can I do GEP with a different pointer type than the type of
 536                      the underlying object?</b></a>
 537 </div>
 538 <div class="doc_text">
 539   <p>Yes. There are no restrictions on bitcasting a pointer value to an arbitrary
 540      pointer type. The types in a GEP serve only to define the parameters for the
 541      underlying integer computation. They need not correspond with the actual
 542      type of the underlying object.</p>
 543
 544   <p>Furthermore, loads and stores don't have to use the same types as the type
 545      of the underlying object. Types in this context serve only to specify
 546      memory size and alignment. Beyond that there are merely a hint to the
 547      optimizer indicating how the value will likely be used.</p>
 548
 549 </div>
 550
 551 <!-- *********************************************************************** -->
 552 <div class="doc_subsection">
 553   <a name="null"><b>Can I cast an object's address to integer and add it
 554                     to null?</b></a>
 555 </div>
 556 <div class="doc_text">
 557   <p>You can compute an address that way, but if you use GEP to do the add,
 558      you can't use that pointer to actually access the object, unless the
 559      object is managed outside of LLVM.</p>
 560
 561   <p>The underlying integer computation is sufficiently defined; null has a
 562      defined value -- zero -- and you can add whatever value you want to it.</p>
 563
 564   <p>However, it's invalid to access (load from or store to) an LLVM-aware
 565      object with such a pointer. This includes GlobalVariables, Allocas, and
 566      objects pointed to by noalias pointers.</p>
 567
 568   <p>If you really need this functionality, you can do the arithmetic with
 569      explicit integer instructions, and use inttoptr to convert the result to
 570      an address. Most of GEP's special aliasing rules do not apply to pointers
 571      computed from ptrtoint, arithmetic, and inttoptr sequences.</p>
 572
 573 </div>
 574
 575 <!-- *********************************************************************** -->
 576 <div class="doc_subsection">
 577   <a name="ptrdiff"><b>Can I compute the distance between two objects, and add
 578                        that value to one address to compute the other address?</b></a>
 579 </div>
 580 <div class="doc_text">
 581   <p>As with arithmetic on null, You can use GEP to compute an address that
 582      way, but you can't use that pointer to actually access the object if you
 583      do, unless the object is managed outside of LLVM.</p>
 584
 585   <p>Also as above, ptrtoint and inttoptr provide an alternative way to do this
 586      which do not have this restriction.</p>
 587
 588 </div>
 589
 590 <!-- *********************************************************************** -->
 591 <div class="doc_subsection">
 592   <a name="tbaa"><b>Can I do type-based alias analysis on LLVM IR?</b></a>
 593 </div>
 594 <div class="doc_text">
 595   <p>You can't do type-based alias analysis using LLVM's built-in type system,
 596      because LLVM has no restrictions on mixing types in addressing, loads or
 597      stores.</p>
 598
 599   <p>It would be possible to add special annotations to the IR, probably using
 600      metadata, to describe a different type system (such as the C type system),
 601      and do type-based aliasing on top of that. This is a much bigger
 602      undertaking though.</p>
 603
 604 </div>
 605
 606 <!-- *********************************************************************** -->
 607
 608 <div class="doc_subsection">
 609   <a name="overflow"><b>What happens if a GEP computation overflows?</b></a>
 610 </div>
 611 <div class="doc_text">
 612    <p>If the GEP has the <tt>inbounds</tt> keyword, the result value is
 613       undefined.</p>
 614
 615    <p>Otherwise, the result value is the result from evaluating the implied
 616       two's complement integer computation. However, since there's no
 617       guarantee of where an object will be allocated in the address space,
 618       such values have limited meaning.</p>
 619
 620 </div>
 621
 622 <!-- *********************************************************************** -->
 623
 624 <div class="doc_subsection">
 625   <a name="check"><b>How can I tell if my front-end is following the
 626                      rules?</b></a>
 627 </div>
 628 <div class="doc_text">
 629    <p>There is currently no checker for the getelementptr rules. Currently,
 630       the only way to do this is to manually check each place in your front-end
 631       where GetElementPtr operators are created.</p>
 632
 633    <p>It's not possible to write a checker which could find all rule
 634       violations statically. It would be possible to write a checker which
 635       works by instrumenting the code with dynamic checks though. Alternatively,
 636       it would be possible to write a static checker which catches a subset of
 637       possible problems. However, no such checker exists today.</p>
 638
 639 </div>
 640
 641 <!-- *********************************************************************** -->
 642 <div class="doc_section"><a name="rationale"><b>Rationale</b></a></div>
 643 <!-- *********************************************************************** -->
 644
 645 <!-- *********************************************************************** -->
 646
 647 <div class="doc_subsection">
 648   <a name="goals"><b>Why is GEP designed this way?</b></a>
 649 </div>
 650 <div class="doc_text">
 651    <p>The design of GEP has the following goals, in rough unofficial
 652       order of priority:</p>
 653    <ul>
 654      <li>Support C, C-like languages, and languages which can be
 655          conceptually lowered into C (this covers a lot).</li>
 656      <li>Support optimizations such as those that are common in
 657          C compilers. In particular, GEP is a cornerstone of LLVM's
 658          <a href="LangRef.html#pointeraliasing">pointer aliasing model</a>.</li>
 659      <li>Provide a consistent method for computing addresses so that
 660          address computations don't need to be a part of load and
 661          store instructions in the IR.</li>
 662      <li>Support non-C-like languages, to the extent that it doesn't
 663          interfere with other goals.</li>
 664      <li>Minimize target-specific information in the IR.</li>
 665    </ul>
 666 </div>
 667
 668 <!-- *********************************************************************** -->
 669 <div class="doc_subsection">
 670   <a name="i32"><b>Why do struct member indices always use i32?</b></a>
 671 </div>
 672 <div class="doc_text">
 673   <p>The specific type i32 is probably just a historical artifact, however it's
 674      wide enough for all practical purposes, so there's been no need to change it.
 675      It doesn't necessarily imply i32 address arithmetic; it's just an identifier
 676      which identifies a field in a struct. Requiring that all struct indices be
 677      the same reduces the range of possibilities for cases where two GEPs are
 678      effectively the same but have distinct operand types.</p>
 679
 680 </div>
 681
 682 <!-- *********************************************************************** -->
 683
 684 <div class="doc_subsection">
 685   <a name="uglygep"><b>What's an uglygep?</b></a>
 686 </div>
 687 <div class="doc_text">
 688   <p>Some LLVM optimizers operate on GEPs by internally lowering them into
 689      more primitive integer expressions, which allows them to be combined
 690      with other integer expressions and/or split into multiple separate
 691      integer expressions. If they've made non-trivial changes, translating
 692      back into LLVM IR can involve reverse-engineering the structure of
 693      the addressing in order to fit it into the static type of the original
 694      first operand. It isn't always possibly to fully reconstruct this
 695      structure; sometimes the underlying addressing doesn't correspond with
 696      the static type at all. In such cases the optimizer instead will emit
 697      a GEP with the base pointer casted to a simple address-unit pointer,
 698      using the name "uglygep". This isn't pretty, but it's just as
 699      valid, and it's sufficient to preserve the pointer aliasing guarantees
 700      that GEP provides.</p>
 701
 702 </div>
 703
 704 <!-- *********************************************************************** -->
 705 <div class="doc_section"><a name="summary"><b>Summary</b></a></div>
 706 <!-- *********************************************************************** -->
 707
 708 <div class="doc_text">
 709   <p>In summary, here's some things to always remember about the GetElementPtr
 710   instruction:</p>
 711   <ol>
 712     <li>The GEP instruction never accesses memory, it only provides pointer
 713     computations.</li>
 714     <li>The first operand to the GEP instruction is always a pointer and it must
 715     be indexed.</li>
 716     <li>There are no superfluous indices for the GEP instruction.</li>
 717     <li>Trailing zero indices are superfluous for pointer aliasing, but not for
 718     the types of the pointers.</li>
 719     <li>Leading zero indices are not superfluous for pointer aliasing nor the
 720     types of the pointers.</li>
 721   </ol>
 722 </div>
 723
 724 <!-- *********************************************************************** -->
 725
 726 <hr>
 727 <address>
 728   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 729   src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
 730   <a href="http://validator.w3.org/check/referer"><img
 731   src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
 732   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
 733   Last modified: $Date$
 734 </address>
 735 </body>
 736 </html>