Gitiles
Code Review Sign In
gerrit-public.fairphone.software / toolchain / llvm-project / 850f09baca8538e7c1bec631ae0d4b176c29c9c3 / . / llvm / docs / GetElementPtr.html
blob: 710273fb6dafe972cfc051b92b93cd565dc7ff1c [file] [log] [blame]
Reid Spencer4bded9c2006-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 Spencerba02d8f2006-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 Spencer4bded9c2006-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 Laskey6cef9de2006-08-15 12:11:42 +0000[diff] [blame]59 <li><a href="#firstptr">What is the first index of the GEP instruction?</a>
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]60 </li>
Jim Laskey6cef9de2006-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 Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]65 </ol>
66</div>
67
68<!-- *********************************************************************** -->
69<div class="doc_subsection">
Reid Spencerafa58f12006-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 Spencer6500f402006-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 Spencer334e26b2006-08-15 03:57:05 +0000[diff] [blame]80 X = &amp;Foo-&gt;F;</pre>
Reid Spencerc438e082006-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 Laskey00389a82006-08-15 08:14:19 +0000[diff] [blame]84 through it transparently. To arrive at the same address location as the C
Reid Spencerc438e082006-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 Spencer334e26b2006-08-15 03:57:05 +0000[diff] [blame]88 <pre>
89 X = &amp;Foo[0].F;</pre>
Reid Spencer6500f402006-08-15 03:43:31 +0000[diff] [blame]90 <p>Sometimes this question gets rephrased as:</p>
Chris Lattner00597282006-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 Spencerafa58f12006-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 Spencer334e26b2006-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 Spencerafa58f12006-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 Spencer22bb5c32006-08-15 03:46:38 +0000[diff] [blame]109 munger_struct Array[3];
Reid Spencerafa58f12006-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 Spencer9d121b02006-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 Spencerafa58f12006-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:
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]123 %tmp = getelementptr %struct.munger_struct* %P, i32 1, i32 0
124 %tmp = load i32* %tmp
125 %tmp6 = getelementptr %struct.munger_struct* %P, i32 2, i32 1
126 %tmp7 = load i32* %tmp6
127 %tmp8 = add i32 %tmp7, %tmp
128 %tmp9 = getelementptr %struct.munger_struct* %P, i32 0, i32 0
129 store i32 %tmp8, i32* %tmp9
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]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>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]137 %MyVar = unintialized global i32
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]138 ...
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]139 %idx1 = getelementptr i32* %MyVar, i64 0
140 %idx2 = getelementptr i32* %MyVar, i64 1
141 %idx3 = getelementptr i32* %MyVar, i64 2</pre>
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]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>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]150 <p>Since the type <tt>i32</tt> is known to be four bytes long, the indices
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]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
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]157 <tt>i32</tt> long, not three <tt>i32</tt>s long. While this is legal in LLVM,
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]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 Spencer4bded9c2006-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>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]172 %MyStruct = uninitialized global { float*, i32 }
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]173 ...
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]174 %idx = getelementptr { float*, i32 }* %MyStruct, i64 0, i32 1</pre>
175 <p>The GEP above yields an <tt>i32*</tt> by indexing the <tt>i32</tt> typed
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]176 field of the structure <tt>%MyStruct</tt>. When people first look at it, they
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]177 wonder why the <tt>i64 0</tt> index is needed. However, a closer inspection
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]178 of how globals and GEPs work reveals the need. Becoming aware of the following
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]179 facts will dispell the confusion:</p>
180 <ol>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]181 <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, i32 }</tt>
182 but rather <tt>{ float*, i32 }*</tt>. That is, <tt>%MyStruct</tt> is a
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]183 pointer to a structure containing a pointer to a <tt>float</tt> and an
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]184 <tt>i32</tt>.</li>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]185 <li>Point #1 is evidenced by noticing the type of the first operand of
186 the GEP instruction (<tt>%MyStruct</tt>) which is
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]187 <tt>{ float*, i32 }*</tt>.</li>
188 <li>The first index, <tt>i64 0</tt> is required to step over the global
Reid Spencerafa58f12006-08-15 03:32:10 +0000[diff] [blame]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 Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]193 <li>The second index, <tt>i32 1</tt> selects the second field of the
194 structure (the <tt>i32</tt>). </li>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]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 Spencerafa58f12006-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 Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]208 <pre>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]209 %MyVar = uninitialized global { [40 x i32 ]* }
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]210 ...
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]211 %idx = getelementptr { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17</pre>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]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 Spencer6500f402006-08-15 03:43:31 +0000[diff] [blame]214 GEP instruction seems to be accessing the 18th integer of the structure's
Reid Spencer4bded9c2006-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>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]222 %idx = getelementptr { [40 x i32]* }* %, i64 0, i32 0
223 %arr = load [40 x i32]** %idx
224 %idx = getelementptr [40 x i32]* %arr, i64 0, i64 17</pre>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]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>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]229 %MyVar = uninitialized global { [40 x i32 ] }
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]230 ...
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]231 %idx = getelementptr { [40 x i32] }*, i64 0, i32 0, i64 17</pre>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]232 <p>then everything works fine. In this case, the structure does not contain a
Reid Spencer6500f402006-08-15 03:43:31 +0000[diff] [blame]233 pointer and the GEP instruction can index through the global variable,
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]234 into the first field of the structure and access the 18th <tt>i32</tt> in the
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]235 array there.</p>
236</div>
237
238<!-- *********************************************************************** -->
239<div class="doc_subsection">
Reid Spencer4bded9c2006-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>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]248 %MyVar = global { [10 x i32 ] }
249 %idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 0, i32 0, i64 1
250 %idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1</pre>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]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
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]253 type of <tt>idx1</tt> is <tt>i32*</tt>. However, <tt>idx2</tt> computes the
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]254 address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]255 <tt>idx2</tt> is <tt>{ [10 x i32] }*</tt> and its value is equivalent
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]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 Laskey6047ec97e2006-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 Spencer4bded9c2006-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>
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]271 %MyVar = global { [10 x i32 ] }
272 %idx1 = getlementptr { [10 x i32 ] }* %MyVar, i64 1, i32 0, i64 0
273 %idx2 = getlementptr { [10 x i32 ] }* %MyVar, i64 1</pre>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]274 <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
Reid Spencer850f09b2007-02-09 17:56:02 +0000[diff] [blame^]275 its type is <tt>i32*</tt>. The value of <tt>%idx2</tt> is also
276 <tt>MyVar+40</tt> but its type is <tt>{ [10 x i32] }*</tt>.</p>
Reid Spencer4bded9c2006-08-10 20:15:58 +0000[diff] [blame]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 Spencer4bded9c2006-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>