Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 39a1fab856acec40e486d075a8017ed824c8bc25 / . / docs / GetElementPtr.html
blob: dd49ef7ec4c1e47e7c145e8582794c41cb3e94a1 [file] [log] [blame]
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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">
Reid Spencerf19ccf82006-08-10 21:01:14 +0000[diff] [blame]8 <style type="text/css">
9 TABLE { text-align: left; border: 1px solid black; border-collapse: collapse; margin: 0 0 0 0; }
10 </style>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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
Benjamin Kramer8040cd32009-10-12 14:46:08 +0000[diff] [blame]43 probably the most frequently occurring questions once a developer gets down to
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]56 this leads to the following questions; all of which are answered in the
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]57 following sections.</p>
58 <ol>
Jim Laskeyaf2cca12006-08-15 12:11:42 +0000[diff] [blame]59 <li><a href="#firstptr">What is the first index of the GEP instruction?</a>
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]60 </li>
Jim Laskeyaf2cca12006-08-15 12:11:42 +0000[diff] [blame]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>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]65 </ol>
66</div>
67
68<!-- *********************************************************************** -->
69<div class="doc_subsection">
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]70 <a name="firstptr"><b>What is the first index of the GEP instruction?</b></a>
71</div>
72<div class="doc_text">
Reid Spencer80a4d052006-08-15 03:43:31 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]77
78<div class="doc_code">
79<pre>
80AType *Foo;
81...
82X = &amp;Foo-&gt;F;
83</pre>
84</div>
85
Reid Spencereda573d2006-08-15 04:00:29 +0000[diff] [blame]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
Jim Laskeye3c312f2006-08-15 08:14:19 +0000[diff] [blame]89 through it transparently. To arrive at the same address location as the C
Reid Spencereda573d2006-08-15 04:00:29 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]93
94<div class="doc_code">
95<pre>
96X = &amp;Foo[0].F;
97</pre>
98</div>
99
Reid Spencer80a4d052006-08-15 03:43:31 +0000[diff] [blame]100 <p>Sometimes this question gets rephrased as:</p>
Chris Lattner4a5dfee2006-08-17 03:26:50 +0000[diff] [blame]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>
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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
Reid Spencer1c6f87d2006-08-15 03:57:05 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]109
110<div class="doc_code">
111<pre>
112struct munger_struct {
113 int f1;
114 int f2;
115};
116void munge(struct munger_struct *P) {
117 P[0].f1 = P[1].f1 + P[2].f2;
118}
119...
120munger_struct Array[3];
121...
122munge(Array);
123</pre>
124</div>
125
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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
Reid Spencer10146472006-08-16 05:53:32 +0000[diff] [blame]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
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]132 <tt>f2</tt> field. So, in LLVM assembly the <tt>munge</tt> function looks
133 like:</p>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]134
135<div class="doc_code">
136<pre>
137void %munge(%struct.munger_struct* %P) {
138entry:
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
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]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
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]169
170<div class="doc_code">
171<pre>
172idx1 = (char*) &amp;MyVar + 0
173idx2 = (char*) &amp;MyVar + 4
174idx3 = (char*) &amp;MyVar + 8
175</pre>
176</div>
177
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]178 <p>Since the type <tt>i32</tt> is known to be four bytes long, the indices
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]185 <tt>i32</tt> long, not three <tt>i32</tt>s long. While this is legal in LLVM,
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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">
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]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
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]209 <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]210 field of the structure <tt>%MyStruct</tt>. When people first look at it, they
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]211 wonder why the <tt>i64 0</tt> index is needed. However, a closer inspection
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]212 of how globals and GEPs work reveals the need. Becoming aware of the following
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]213 facts will dispell the confusion:</p>
214 <ol>
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]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
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]217 pointer to a structure containing a pointer to a <tt>float</tt> and an
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]218 <tt>i32</tt>.</li>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]219 <li>Point #1 is evidenced by noticing the type of the first operand of
220 the GEP instruction (<tt>%MyStruct</tt>) which is
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]221 <tt>{ float*, i32 }*</tt>.</li>
222 <li>The first index, <tt>i64 0</tt> is required to step over the global
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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>
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]227 <li>The second index, <tt>i32 1</tt> selects the second field of the
228 structure (the <tt>i32</tt>). </li>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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
Reid Spencer919d3712006-08-15 03:32:10 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]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
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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
Reid Spencer80a4d052006-08-15 03:43:31 +0000[diff] [blame]253 GEP instruction seems to be accessing the 18th integer of the structure's
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]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
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]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
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]281 <p>then everything works fine. In this case, the structure does not contain a
Reid Spencer80a4d052006-08-15 03:43:31 +0000[diff] [blame]282 pointer and the GEP instruction can index through the global variable,
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]283 into the first field of the structure and access the 18th <tt>i32</tt> in the
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]284 array there.</p>
285</div>
286
287<!-- *********************************************************************** -->
288<div class="doc_subsection">
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]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>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]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
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]305 <p>In this example, <tt>idx1</tt> computes the address of the second integer
Misha Brukmanfc13d1c2009-08-18 19:18:40 +0000[diff] [blame]306 in the array that is in the structure in <tt>%MyVar</tt>, that is
307 <tt>MyVar+4</tt>. The type of <tt>idx1</tt> is <tt>i32*</tt>. However,
308 <tt>idx2</tt> computes the address of <i>the next</i> structure after
309 <tt>%MyVar</tt>. The type of <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its
310 value is equivalent to <tt>MyVar + 40</tt> because it indexes past the ten
311 4-byte integers in <tt>MyVar</tt>. Obviously, in such a situation, the
312 pointers don't alias.</p>
313
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]314</div>
315
316<!-- *********************************************************************** -->
317<div class="doc_subsection">
Jim Laskey19af0e12006-08-15 12:15:08 +0000[diff] [blame]318 <a name="trail0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]319</div>
320<div class="doc_text">
321 <p>Quick Answer: They compute the same address location.</p>
322 <p>These two GEP instructions will compute the same address because indexing
323 through the 0th element does not change the address. However, it does change
324 the type. Consider this example:</p>
Bill Wendling32759082008-01-04 12:04:32 +0000[diff] [blame]325
326<div class="doc_code">
327<pre>
328%MyVar = global { [10 x i32 ] }
329%idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
330%idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1
331</pre>
332</div>
333
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]334 <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
Reid Spencerb913a512007-02-09 17:56:02 +0000[diff] [blame]335 its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also
336 <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]337</div>
338
339<!-- *********************************************************************** -->
340<div class="doc_section"><a name="summary"><b>Summary</b></a></div>
341<!-- *********************************************************************** -->
342
343<div class="doc_text">
344 <p>In summary, here's some things to always remember about the GetElementPtr
345 instruction:</p>
346 <ol>
347 <li>The GEP instruction never accesses memory, it only provides pointer
348 computations.</li>
349 <li>The first operand to the GEP instruction is always a pointer and it must
350 be indexed.</li>
351 <li>There are no superfluous indices for the GEP instruction.</li>
352 <li>Trailing zero indices are superfluous for pointer aliasing, but not for
353 the types of the pointers.</li>
354 <li>Leading zero indices are not superfluous for pointer aliasing nor the
355 types of the pointers.</li>
356 </ol>
357</div>
358
359<!-- *********************************************************************** -->
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]360
361<hr>
362<address>
363 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
Misha Brukman44408702008-12-11 17:34:48 +0000[diff] [blame]364 src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]365 <a href="http://validator.w3.org/check/referer"><img
Misha Brukmanf00ddb02008-12-11 18:23:24 +0000[diff] [blame]366 src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
Reid Spencere00906f2006-08-10 20:15:58 +0000[diff] [blame]367 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
368 Last modified: $Date$
369</address>
370</body>
371</html>