diff options
| author | Reid Spencer <rspencer@reidspencer.com> | 2006-08-10 20:15:58 +0000 |
|---|---|---|
| committer | Reid Spencer <rspencer@reidspencer.com> | 2006-08-10 20:15:58 +0000 |
| commit | e00906fbc222c19b7ab84a817b2be46b87484e99 (patch) | |
| tree | 5d230cb8ab6439c1bee0b1a0f2f46b7c0585b36e /docs | |
| parent | 6c8d90d65fa721d406c7a09a0045fa49254a9244 (diff) | |
| download | llvm-e00906fbc222c19b7ab84a817b2be46b87484e99.tar.gz llvm-e00906fbc222c19b7ab84a817b2be46b87484e99.tar.bz2 llvm-e00906fbc222c19b7ab84a817b2be46b87484e99.tar.xz | |
Answer the most frequently asked question, about GEPs. The answer is
sufficiently long that I placed it in a separate file but it links from
the FAQ page. More might need to be added to GetElementPtr.html to
address additional confusion surrounding GEP.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29594 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/FAQ.html | 2 | ||||
| -rw-r--r-- | docs/GetElementPtr.html | 249 |
2 files changed, 251 insertions, 0 deletions
diff --git a/docs/FAQ.html b/docs/FAQ.html index 2ab00ac7e9..6e0600be33 100644 --- a/docs/FAQ.html +++ b/docs/FAQ.html @@ -60,6 +60,8 @@ <li><a href="#langs">What source languages are supported?</a></li> <li><a href="#langhlsupp">What support is there for higher level source language constructs for building a compiler?</a></li> + <li><a href="GetElementPtr.html">I don't understand the GetElementPtr + instruction. Help!</a></li> </ol> <li><a href="#cfe">Using the GCC Front End</a> diff --git a/docs/GetElementPtr.html b/docs/GetElementPtr.html new file mode 100644 index 0000000000..13b5138ab2 --- /dev/null +++ b/docs/GetElementPtr.html @@ -0,0 +1,249 @@ +<!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"> +</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="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> +</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><pre> + %MyStruct = uninitialized global { float*, int } + ... + %idx = getelementptr { float*, int }* %MyStruct, long 0, ubyte 1</pre> + <p>The GEP above yields an <tt>int*</tt> by indexing the <tt>int</tt> typed + field of the structure <tt>%MyStruct</tt>. When people first look at it, they + wonder why the <tt>long 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*, int }</tt> + but rather <tt>{ float*, int }*</tt>. That is, <tt>%MyStruct</tt> is a + pointer to a structure containing a pointer to a <tt>float</tt> and an + <tt>int</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*, int }*</tt>.</li> + <li>The first index, <tt>long 0</tt> is required to dereference the + pointer associated with <tt>%MyStruct</tt>.</li> + <li>The second index, <tt>ubyte 1</tt> selects the second field of the + structure (the <tt>int</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 instruction is for. GEP is + only involved in the computation of addresses. For example, consider this:</p> + <pre> + %MyVar = uninitialized global { [40 x int ]* } + ... + %idx = getelementptr { [40 x int]* }* %MyVar, long 0, ubyte 0, long 0, long 17</pre> + <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 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> + <pre> + %idx = getelementptr { [40 x int]* }* %, long 0, ubyte 0 + %arr = load [40 x int]** %idx + %idx = getelementptr [40 x int]* %arr, long 0, long 17</pre> + <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> + <pre> + %MyVar = uninitialized global { [40 x int ] } + ... + %idx = getelementptr { [40 x int] }*, long 0, ubyte 0, long 17</pre> + <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 pointer, + into the first field of the structure and access the 18th <tt>int</tt> in the + array there.</p> +</div> + +<!-- *********************************************************************** --> +<div class="doc_subsection"> + <a name="firstptr"><b>Why can you index through the first pointer?</b></a> +</div> +<div class="doc_text"> + <p>Quick answer: Because its already present.</p> + <p>Having understood the <a href="#deref">previous question</a>, a new + question then arises:</p> + <blockquote><i>Why is it okay to index through the first pointer, but + subsequent pointers won't be dereferenced?</i></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 without any need + for accessing memory. It must, therefore be indexed like any other operand. + Consider this example:</p> + <pre> + %MyVar = unintialized global int + ... + %idx1 = getelementptr int* %MyVar, long 0 + %idx2 = getelementptr int* %MyVar, long 1 + %idx3 = getelementptr int* %MyVar, long 2</pre> + <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> + <ul> + <li> idx1 = &MyVar + 0</li> + <li> idx2 = &MyVar + 4</li> + <li> idx3 = &MyVar = 8</li> + </ul> + <p>Since the type <tt>int</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>Note that the cases of <tt>%idx2</tt> and <tt>%idx3</tt> are a bit silly. + They are computing addresses of something of unknown type (and thus + potentially breaking type safety) because <tt>%MyVar</tt> is only one + integer long.</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> + <pre> + %MyVar = global { [10 x int ] } + %idx1 = getlementptr { [10 x int ] }* %MyVar, long 0, byte 0, long 1 + %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre> + <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>int*</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 int] }*</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="lead0"><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> + <pre> + %MyVar = global { [10 x int ] } + %idx1 = getlementptr { [10 x int ] }* %MyVar, long 1, byte 0, long 0 + %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre> + <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and + its type is <tt>int*</tt>. The value of <tt>%idx2</tt> is also + <tt>MyVar+40</tt> but its type is <tt>{ [10 x int] }*</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" alt="Valid CSS!"></a> + <a href="http://validator.w3.org/check/referer"><img + src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a> + <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/> + Last modified: $Date$ +</address> +</body> +</html> |