Import LLVM, at r72732.

author: ed <ed@FreeBSD.org> 2009-06-02 17:52:33 +0000
committer: ed <ed@FreeBSD.org> 2009-06-02 17:52:33 +0000
commit: 3277b69d734b9c90b44ebde4ede005717e2c3b2e (patch)
tree: 64ba909838c23261cace781ece27d106134ea451 /docs/GetElementPtr.html
download: FreeBSD-src-3277b69d734b9c90b44ebde4ede005717e2c3b2e.zip
FreeBSD-src-3277b69d734b9c90b44ebde4ede005717e2c3b2e.tar.gz
1 files changed, 370 insertions, 0 deletions
diff --git a/docs/GetElementPtr.html b/docs/GetElementPtr.html
new file mode 100644
index 0000000..f4b096a
--- /dev/null
+++ b/docs/GetElementPtr.html
@@ -0,0 +1,370 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
+                      "http://www.w3.org/TR/html4/strict.dtd">
+<html>
+<head>
+  <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
+  <title>The Often Misunderstood GEP Instruction</title>
+  <link rel="stylesheet" href="llvm.css" type="text/css">
+  <style type="text/css">
+    TABLE   { text-align: left; border: 1px solid black; border-collapse: collapse; margin: 0 0 0 0; }
+  </style>
+</head>
+<body>
+
+<div class="doc_title">
+  The Often Misunderstood GEP Instruction
+</div>
+
+<ol>
+  <li><a href="#intro">Introduction</a></li>
+  <li><a href="#questions">The Questions</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>
+    <li><a href="#firstptr">Why can you index through the first pointer but not
+      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>
+  </ol></li>
+  <li><a href="#summary">Summary</a></li>
+</ol>
+
+<div class="doc_author">
+  <p>Written by: <a href="mailto:rspencer@reidspencer.com">Reid Spencer</a>.</p>
+</div>
+
+
+<!-- *********************************************************************** -->
+<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
+  probably the most frequently occuring 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.
+  </p>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section"><a name="questions"><b>The Questions</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>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+  <a name="firstptr"><b>What is the first index of the GEP instruction?</b></a>
+</div>
+<div class="doc_text">
+  <p>Quick answer: The index stepping through the first operand.</p> 
+  <p>The confusion with the first index usually arises from thinking about 
+  the GetElementPtr instruction as if it was a C index operator. They aren't the
+  same. For example, when we write, in "C":</p>
+
+<div class="doc_code">
+<pre>
+AType *Foo;
+...
+X = &amp;Foo-&gt;F;
+</pre>
+</div>
+
+  <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
+  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 
+  field <tt>F</tt> of the structure, just as if you wrote:</p>
+
+<div class="doc_code">
+<pre>
+X = &amp;Foo[0].F;
+</pre>
+</div>
+
+  <p>Sometimes this question gets rephrased as:</p>
+  <blockquote><p><i>Why is it okay to index through the first pointer, but 
+      subsequent pointers won't be dereferenced?</i></p></blockquote> 
+  <p>The answer is simply because memory does not have to be accessed to 
+  perform the computation. The first operand to the GEP instruction must be a 
+  value of a pointer type. The value of the pointer is provided directly to 
+  the GEP instruction as an operand without any need for accessing memory. It 
+  must, therefore be indexed and requires an index operand. Consider this 
+  example:</p>
+
+<div class="doc_code">
+<pre>
+struct munger_struct {
+  int f1;
+  int f2;
+};
+void munge(struct munger_struct *P) {
+  P[0].f1 = P[1].f1 + P[2].f2;
+}
+...
+munger_struct Array[3];
+...
+munge(Array);
+</pre>
+</div>
+
+  <p>In this "C" example, the front end compiler (llvm-gcc) will generate three
+  GEP instructions for the three indices through "P" in the assignment
+  statement.  The function argument <tt>P</tt> will be the first operand of each
+  of these GEP instructions.  The second operand indexes through that pointer.
+  The third operand will be the field offset into the 
+  <tt>struct munger_struct</tt> type,  for either the <tt>f1</tt> or 
+  <tt>f2</tt> field. So, in LLVM assembly the <tt>munge</tt> function looks 
+  like:</p>
+
+<div class="doc_code">
+<pre>
+void %munge(%struct.munger_struct* %P) {
+entry:
+  %tmp = getelementptr %struct.munger_struct* %P, i32 1, i32 0
+  %tmp = load i32* %tmp
+  %tmp6 = getelementptr %struct.munger_struct* %P, i32 2, i32 1
+  %tmp7 = load i32* %tmp6
+  %tmp8 = add i32 %tmp7, %tmp
+  %tmp9 = getelementptr %struct.munger_struct* %P, i32 0, i32 0
+  store i32 %tmp8, i32* %tmp9
+  ret void
+}
+</pre>
+</div>
+
+  <p>In each case the first operand is the pointer through which the GEP
+  instruction starts. The same is true whether the first operand is an
+  argument, allocated memory, or a global variable. </p>
+  <p>To make this clear, let's consider a more obtuse example:</p>
+
+<div class="doc_code">
+<pre>
+%MyVar = unintialized global i32
+...
+%idx1 = getelementptr i32* %MyVar, i64 0
+%idx2 = getelementptr i32* %MyVar, i64 1
+%idx3 = getelementptr i32* %MyVar, i64 2
+</pre>
+</div>
+
+  <p>These GEP instructions are simply making address computations from the 
+  base address of <tt>MyVar</tt>.  They compute, as follows (using C syntax):
+  </p>
+
+<div class="doc_code">
+<pre>
+idx1 = (char*) &amp;MyVar + 0
+idx2 = (char*) &amp;MyVar + 4
+idx3 = (char*) &amp;MyVar + 8
+</pre>
+</div>
+
+  <p>Since the type <tt>i32</tt> is known to be four bytes long, the indices 
+  0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No 
+  memory is accessed to make these computations because the address of 
+  <tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
+  <p>The obtuse part of this example is in the cases of <tt>%idx2</tt> and 
+  <tt>%idx3</tt>. They result in the computation of addresses that point to
+  memory past the end of the <tt>%MyVar</tt> global, which is only one
+  <tt>i32</tt> long, not three <tt>i32</tt>s long.  While this is legal in LLVM,
+  it is inadvisable because any load or store with the pointer that results 
+  from these GEP instructions would produce undefined results.</p>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+  <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
+</div>
+<!-- *********************************************************************** -->
+<div class="doc_text">
+  <p>Quick answer: there are no superfluous indices.</p>
+  <p>This question arises most often when the GEP instruction is applied to a
+  global variable which is always a pointer type. For example, consider
+  this:</p>
+
+<div class="doc_code">
+<pre>
+%MyStruct = uninitialized global { float*, i32 }
+...
+%idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1
+</pre>
+</div>
+
+  <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed 
+  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>
+  <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 
+    pointer to a structure containing a pointer to a <tt>float</tt> and an 
+    <tt>i32</tt>.</li>
+    <li>Point #1 is evidenced by noticing the type of the first operand of 
+    the GEP instruction (<tt>%MyStruct</tt>) which is 
+    <tt>{ float*, i32 }*</tt>.</li>
+    <li>The first index, <tt>i64 0</tt> is required to step over the global
+    variable <tt>%MyStruct</tt>.  Since the first argument to the GEP
+    instruction must always be a value of pointer type, the first index 
+    steps through that pointer. A value of 0 means 0 elements offset from that
+    pointer.</li>
+    <li>The second index, <tt>i32 1</tt> selects the second field of the
+    structure (the <tt>i32</tt>). </li>
+  </ol>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+  <a name="deref"><b>What is dereferenced by GEP?</b></a>
+</div>
+<div class="doc_text">
+  <p>Quick answer: nothing.</p> 
+  <p>The GetElementPtr instruction dereferences nothing. That is, it doesn't
+  access memory in any way. That's what the Load and Store instructions are for.
+  GEP is only involved in the computation of addresses. For example, consider 
+  this:</p>
+
+<div class="doc_code">
+<pre>
+%MyVar = uninitialized global { [40 x i32 ]* }
+...
+%idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17
+</pre>
+</div>
+
+  <p>In this example, we have a global variable, <tt>%MyVar</tt> that is a
+  pointer to a structure containing a pointer to an array of 40 ints. The 
+  GEP instruction seems to be accessing the 18th integer of the structure's
+  array of ints. However, this is actually an illegal GEP instruction. It 
+  won't compile. The reason is that the pointer in the structure <i>must</i>
+  be dereferenced in order to index into the array of 40 ints. Since the 
+  GEP instruction never accesses memory, it is illegal.</p>
+  <p>In order to access the 18th integer in the array, you would need to do the
+  following:</p>
+
+<div class="doc_code">
+<pre>
+%idx = getelementptr { [40 x i32]* }* %, i64 0, i32 0
+%arr = load [40 x i32]** %idx
+%idx = getelementptr [40 x i32]* %arr, i64 0, i64 17
+</pre>
+</div>
+
+  <p>In this case, we have to load the pointer in the structure with a load
+  instruction before we can index into the array. If the example was changed 
+  to:</p>
+
+<div class="doc_code">
+<pre>
+%MyVar = uninitialized global { [40 x i32 ] }
+...
+%idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17
+</pre>
+</div>
+
+  <p>then everything works fine. In this case, the structure does not contain a
+  pointer and the GEP instruction can index through the global variable,
+  into the first field of the structure and access the 18th <tt>i32</tt> in the 
+  array there.</p>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+  <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
+</div>
+<div class="doc_text">
+  <p>Quick Answer: They compute different address locations.</p>
+  <p>If you look at the first indices in these GEP
+  instructions you find that they are different (0 and 1), therefore the address
+  computation diverges with that index. Consider this example:</p>
+
+<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
+</pre>
+</div>
+
+  <p>In this example, <tt>idx1</tt> computes the address of the second integer
+  in the array that is in the structure in %MyVar, that is <tt>MyVar+4</tt>. The 
+  type of <tt>idx1</tt> is <tt>i32*</tt>. However, <tt>idx2</tt> computes the 
+  address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of 
+  <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its value is equivalent 
+  to <tt>MyVar + 40</tt> because it indexes past the ten 4-byte integers 
+  in <tt>MyVar</tt>. Obviously, in such a situation, the pointers don't 
+  alias.</p>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_subsection">
+  <a name="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
+</div>
+<div class="doc_text">
+  <p>Quick Answer: They compute the same address location.</p>
+  <p>These two GEP instructions will compute the same address because indexing
+  through the 0th element does not change the address. However, it does change
+  the type. Consider this example:</p>
+
+<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
+</pre>
+</div>
+
+  <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
+  its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also 
+  <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section"><a name="summary"><b>Summary</b></a></div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+  <p>In summary, here's some things to always remember about the GetElementPtr
+  instruction:</p>
+  <ol>
+    <li>The GEP instruction never accesses memory, it only provides pointer
+    computations.</li>
+    <li>The first operand to the GEP instruction is always a pointer and it must
+    be indexed.</li>
+    <li>There are no superfluous indices for the GEP instruction.</li>
+    <li>Trailing zero indices are superfluous for pointer aliasing, but not for
+    the types of the pointers.</li>
+    <li>Leading zero indices are not superfluous for pointer aliasing nor the
+    types of the pointers.</li>
+  </ol>
+</div>
+
+<!-- *********************************************************************** -->
+
+<hr>
+<address>
+  <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
+  src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
+  <a href="http://validator.w3.org/check/referer"><img
+  src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
+  <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
+  Last modified: $Date: 2008-12-11 19:23:24 +0100 (Thu, 11 Dec 2008) $
+</address>
+</body>
+</html>
author	ed <ed@FreeBSD.org>	2009-06-02 17:52:33 +0000
committer	ed <ed@FreeBSD.org>	2009-06-02 17:52:33 +0000
commit	3277b69d734b9c90b44ebde4ede005717e2c3b2e (patch)
tree	64ba909838c23261cace781ece27d106134ea451 /docs/GetElementPtr.html
download	FreeBSD-src-3277b69d734b9c90b44ebde4ede005717e2c3b2e.zip FreeBSD-src-3277b69d734b9c90b44ebde4ede005717e2c3b2e.tar.gz