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