Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / e00906fbc222c19b7ab84a817b2be46b87484e99 / . / docs / GetElementPtr.html
blob: 13b5138ab2da4a4a4c3009eb400475412fa01782 [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">
8</head>
9<body>
10
11<div class="doc_title">
12 The Often Misunderstood GEP Instruction
13</div>
14
15<ol>
16 <li><a href="#intro">Introduction</a></li>
17 <li><a href="#questions">The Questions</a>
18 <ol>
19 <li><a href="#extra_index">Why is the extra 0 index required?</a></li>
20 <li><a href="#deref">What is dereferenced by GEP?</a></li>
21 <li><a href="#firstptr">Why can you index through the first pointer but not
22 subsequent ones?</a></li>
23 <li><a href="#lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
24 <li><a href="#trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
25 </ol></li>
26 <li><a href="#summary">Summary</a></li>
27</ol>
28
29<div class="doc_author">
30 <p>Written by: <a href="mailto:rspencer@reidspencer.com">Reid Spencer</a>.</p>
31</div>
32
33
34<!-- *********************************************************************** -->
35<div class="doc_section"><a name="intro"><b>Introduction</b></a></div>
36<!-- *********************************************************************** -->
37<div class="doc_text">
38 <p>This document seeks to dispel the mystery and confusion surrounding LLVM's
39 GetElementPtr (GEP) instruction. Questions about the wiley GEP instruction are
40 probably the most frequently occuring questions once a developer gets down to
41 coding with LLVM. Here we lay out the sources of confusion and show that the
42 GEP instruction is really quite simple.
43 </p>
44</div>
45
46<!-- *********************************************************************** -->
47<div class="doc_section"><a name="questions"><b>The Questions</b></a></div>
48<!-- *********************************************************************** -->
49<div class="doc_text">
50 <p>When people are first confronted with the GEP instruction, they tend to
51 relate it to known concepts from other programming paradigms, most notably C
52 array indexing and field selection. However, GEP is a little different and
53 this leads to the following questions, all of which are answered in the
54 following sections.</p>
55 <ol>
56 <li><a href="extra_index">Why is the extra 0 index required?</a></li>
57 <li><a href="deref">What is dereferenced by GEP?</a></li>
58 <li><a href="firstptr">Why can you index through the first pointer but not
59 subsequent ones?</a></li>
60 <li><a href="lead0">Why don't GEP x,0,0,1 and GEP x,1 alias? </a></li>
61 <li><a href="trail0">Why do GEP x,1,0,0 and GEP x,1 alias? </a></li>
62 </ol>
63</div>
64
65<!-- *********************************************************************** -->
66<div class="doc_subsection">
67 <a name="extra_index"><b>Why is the extra 0 index required?</b></a>
68</div>
69<!-- *********************************************************************** -->
70<div class="doc_text">
71 <p>Quick answer: there are no superfluous indices.</p>
72 <p>This question arises most often when the GEP instruction is applied to a
73 global variable which is always a pointer type. For example, consider
74 this:</p><pre>
75 %MyStruct = uninitialized global { float*, int }
76 ...
77 %idx = getelementptr { float*, int }* %MyStruct, long 0, ubyte 1</pre>
78 <p>The GEP above yields an <tt>int*</tt> by indexing the <tt>int</tt> typed
79 field of the structure <tt>%MyStruct</tt>. When people first look at it, they
80 wonder why the <tt>long 0</tt> index is needed. However, a closer inspection
81 of how globals and GEPs work reveals the need. Becoming aware of the following
82 facts will dispell the confusion:</p>
83 <ol>
84 <li>The type of <tt>%MyStruct</tt> is <i>not</i> <tt>{ float*, int }</tt>
85 but rather <tt>{ float*, int }*</tt>. That is, <tt>%MyStruct</tt> is a
86 pointer to a structure containing a pointer to a <tt>float</tt> and an
87 <tt>int</tt>.</li>
88 <li>Point #1 is evidenced by noticing the type of the first operand of
89 the GEP instruction (<tt>%MyStruct</tt>) which is
90 <tt>{ float*, int }*</tt>.</li>
91 <li>The first index, <tt>long 0</tt> is required to dereference the
92 pointer associated with <tt>%MyStruct</tt>.</li>
93 <li>The second index, <tt>ubyte 1</tt> selects the second field of the
94 structure (the <tt>int</tt>). </li>
95 </ol>
96</div>
97
98<!-- *********************************************************************** -->
99<div class="doc_subsection">
100 <a name="deref"><b>What is dereferenced by GEP?</b></a>
101</div>
102<div class="doc_text">
103 <p>Quick answer: nothing.</p>
104 <p>The GetElementPtr instruction dereferences nothing. That is, it doesn't
105 access memory in any way. That's what the Load instruction is for. GEP is
106 only involved in the computation of addresses. For example, consider this:</p>
107 <pre>
108 %MyVar = uninitialized global { [40 x int ]* }
109 ...
110 %idx = getelementptr { [40 x int]* }* %MyVar, long 0, ubyte 0, long 0, long 17</pre>
111 <p>In this example, we have a global variable, <tt>%MyVar</tt> that is a
112 pointer to a structure containing a pointer to an array of 40 ints. The
113 GEP instruction seems to be accessing the 18th integer of of the structure's
114 array of ints. However, this is actually an illegal GEP instruction. It
115 won't compile. The reason is that the pointer in the structure <i>must</i>
116 be dereferenced in order to index into the array of 40 ints. Since the
117 GEP instruction never accesses memory, it is illegal.</p>
118 <p>In order to access the 18th integer in the array, you would need to do the
119 following:</p>
120 <pre>
121 %idx = getelementptr { [40 x int]* }* %, long 0, ubyte 0
122 %arr = load [40 x int]** %idx
123 %idx = getelementptr [40 x int]* %arr, long 0, long 17</pre>
124 <p>In this case, we have to load the pointer in the structure with a load
125 instruction before we can index into the array. If the example was changed
126 to:</p>
127 <pre>
128 %MyVar = uninitialized global { [40 x int ] }
129 ...
130 %idx = getelementptr { [40 x int] }*, long 0, ubyte 0, long 17</pre>
131 <p>then everything works fine. In this case, the structure does not contain a
132 pointer and the GEP instruction can index through the global variable pointer,
133 into the first field of the structure and access the 18th <tt>int</tt> in the
134 array there.</p>
135</div>
136
137<!-- *********************************************************************** -->
138<div class="doc_subsection">
139 <a name="firstptr"><b>Why can you index through the first pointer?</b></a>
140</div>
141<div class="doc_text">
142 <p>Quick answer: Because its already present.</p>
143 <p>Having understood the <a href="#deref">previous question</a>, a new
144 question then arises:</p>
145 <blockquote><i>Why is it okay to index through the first pointer, but
146 subsequent pointers won't be dereferenced?</i></blockquote>
147 <p>The answer is simply because
148 memory does not have to be accessed to perform the computation. The first
149 operand to the GEP instruction must be a value of a pointer type. The value
150 of the pointer is provided directly to the GEP instruction without any need
151 for accessing memory. It must, therefore be indexed like any other operand.
152 Consider this example:</p>
153 <pre>
154 %MyVar = unintialized global int
155 ...
156 %idx1 = getelementptr int* %MyVar, long 0
157 %idx2 = getelementptr int* %MyVar, long 1
158 %idx3 = getelementptr int* %MyVar, long 2</pre>
159 <p>These GEP instructions are simply making address computations from the
160 base address of <tt>MyVar</tt>. They compute, as follows (using C syntax):</p>
161 <ul>
162 <li> idx1 = &amp;MyVar + 0</li>
163 <li> idx2 = &amp;MyVar + 4</li>
164 <li> idx3 = &amp;MyVar = 8</li>
165 </ul>
166 <p>Since the type <tt>int</tt> is known to be four bytes long, the indices
167 0, 1 and 2 translate into memory offsets of 0, 4, and 8, respectively. No
168 memory is accessed to make these computations because the address of
169 <tt>%MyVar</tt> is passed directly to the GEP instructions.</p>
170 <p>Note that the cases of <tt>%idx2</tt> and <tt>%idx3</tt> are a bit silly.
171 They are computing addresses of something of unknown type (and thus
172 potentially breaking type safety) because <tt>%MyVar</tt> is only one
173 integer long.</p>
174</div>
175
176<!-- *********************************************************************** -->
177<div class="doc_subsection">
178 <a name="lead0"><b>Why don't GEP x,0,0,1 and GEP x,1 alias?</b></a>
179</div>
180<div class="doc_text">
181 <p>Quick Answer: They compute different address locations.</p>
182 <p>If you look at the first indices in these GEP
183 instructions you find that they are different (0 and 1), therefore the address
184 computation diverges with that index. Consider this example:</p>
185 <pre>
186 %MyVar = global { [10 x int ] }
187 %idx1 = getlementptr { [10 x int ] }* %MyVar, long 0, byte 0, long 1
188 %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre>
189 <p>In this example, <tt>idx1</tt> computes the address of the second integer
190 in the array that is in the structure in %MyVar, that is <tt>MyVar+4</tt>. The
191 type of <tt>idx1</tt> is <tt>int*</tt>. However, <tt>idx2</tt> computes the
192 address of <i>the next</i> structure after <tt>%MyVar</tt>. The type of
193 <tt>idx2</tt> is <tt>{ [10 x int] }*</tt> and its value is equivalent
194 to <tt>MyVar + 40</tt> because it indexes past the ten 4-byte integers
195 in <tt>MyVar</tt>. Obviously, in such a situation, the pointers don't
196 alias.</p>
197</div>
198
199<!-- *********************************************************************** -->
200<div class="doc_subsection">
201 <a name="lead0"><b>Why do GEP x,1,0,0 and GEP x,1 alias?</b></a>
202</div>
203<div class="doc_text">
204 <p>Quick Answer: They compute the same address location.</p>
205 <p>These two GEP instructions will compute the same address because indexing
206 through the 0th element does not change the address. However, it does change
207 the type. Consider this example:</p>
208 <pre>
209 %MyVar = global { [10 x int ] }
210 %idx1 = getlementptr { [10 x int ] }* %MyVar, long 1, byte 0, long 0
211 %idx2 = getlementptr { [10 x int ] }* %MyVar, long 1</pre>
212 <p>In this example, the value of <tt>%idx1</tt> is <tt>%MyVar+40</tt> and
213 its type is <tt>int*</tt>. The value of <tt>%idx2</tt> is also
214 <tt>MyVar+40</tt> but its type is <tt>{ [10 x int] }*</tt>.</p>
215</div>
216
217<!-- *********************************************************************** -->
218<div class="doc_section"><a name="summary"><b>Summary</b></a></div>
219<!-- *********************************************************************** -->
220
221<div class="doc_text">
222 <p>In summary, here's some things to always remember about the GetElementPtr
223 instruction:</p>
224 <ol>
225 <li>The GEP instruction never accesses memory, it only provides pointer
226 computations.</li>
227 <li>The first operand to the GEP instruction is always a pointer and it must
228 be indexed.</li>
229 <li>There are no superfluous indices for the GEP instruction.</li>
230 <li>Trailing zero indices are superfluous for pointer aliasing, but not for
231 the types of the pointers.</li>
232 <li>Leading zero indices are not superfluous for pointer aliasing nor the
233 types of the pointers.</li>
234 </ol>
235</div>
236
237<!-- *********************************************************************** -->
238
239<hr>
240<address>
241 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
242 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
243 <a href="http://validator.w3.org/check/referer"><img
244 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
245 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br/>
246 Last modified: $Date$
247</address>
248</body>
249</html>