Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / valgrind / aad8c1930e4c41d88fdc16796ac8914cb95147f4 / . / cachegrind / docs / cg_techdocs.html
blob: 95f29c00180c6ddc4d46b5110ab0cb0d38c361c9 [file] [log] [blame]
sewardja9a2dcf2002-11-11 00:20:07 +0000[diff] [blame]1<html>
2 <head>
3 <style type="text/css">
4 body { background-color: #ffffff;
5 color: #000000;
6 font-family: Times, Helvetica, Arial;
7 font-size: 14pt}
8 h4 { margin-bottom: 0.3em}
9 code { color: #000000;
10 font-family: Courier;
11 font-size: 13pt }
12 pre { color: #000000;
13 font-family: Courier;
14 font-size: 13pt }
15 a:link { color: #0000C0;
16 text-decoration: none; }
17 a:visited { color: #0000C0;
18 text-decoration: none; }
19 a:active { color: #0000C0;
20 text-decoration: none; }
21 </style>
sewardjf555ac72002-11-18 00:07:28 +0000[diff] [blame]22 <title>How Cachegrind works</title>
sewardja9a2dcf2002-11-11 00:20:07 +0000[diff] [blame]23 </head>
24
25<body bgcolor="#ffffff">
26
sewardjf555ac72002-11-18 00:07:28 +0000[diff] [blame]27<a name="cg-techdocs">&nbsp;</a>
sewardja9a2dcf2002-11-11 00:20:07 +0000[diff] [blame]28<h1 align=center>How Cachegrind works</h1>
29
30<center>
31Detailed technical notes for hackers, maintainers and the
32overly-curious<br>
sewardja9a2dcf2002-11-11 00:20:07 +0000[diff] [blame]33<p>
sewardjf555ac72002-11-18 00:07:28 +0000[diff] [blame]34<a href="mailto:njn25@cam.ac.uk">njn25@cam.ac.uk</a><br>
35<a
36href="http://developer.kde.org/~sewardj">http://developer.kde.org/~sewardj</a><br>
sewardja9a2dcf2002-11-11 00:20:07 +0000[diff] [blame]37<p>
njn0e1b5142003-04-15 14:58:06 +0000[diff] [blame]38Copyright &copy; 2001-2003 Nick Nethercote
sewardjf555ac72002-11-18 00:07:28 +0000[diff] [blame]39<p>
sewardja9a2dcf2002-11-11 00:20:07 +0000[diff] [blame]40</center>
41
42<p>
43
44
45
46
47<hr width="100%">
48
49<h2>Cache profiling</h2>
50Valgrind is a very nice platform for doing cache profiling and other kinds of
51simulation, because it converts horrible x86 instructions into nice clean
52RISC-like UCode. For example, for cache profiling we are interested in
53instructions that read and write memory; in UCode there are only four
54instructions that do this: <code>LOAD</code>, <code>STORE</code>,
55<code>FPU_R</code> and <code>FPU_W</code>. By contrast, because of the x86
56addressing modes, almost every instruction can read or write memory.<p>
57
58Most of the cache profiling machinery is in the file
59<code>vg_cachesim.c</code>.<p>
60
61These notes are a somewhat haphazard guide to how Valgrind's cache profiling
62works.<p>
63
64<h3>Cost centres</h3>
65Valgrind gathers cache profiling about every instruction executed,
66individually. Each instruction has a <b>cost centre</b> associated with it.
67There are two kinds of cost centre: one for instructions that don't reference
68memory (<code>iCC</code>), and one for instructions that do
69(<code>idCC</code>):
70
71<pre>
72typedef struct _CC {
73 ULong a;
74 ULong m1;
75 ULong m2;
76} CC;
77
78typedef struct _iCC {
79 /* word 1 */
80 UChar tag;
81 UChar instr_size;
82
83 /* words 2+ */
84 Addr instr_addr;
85 CC I;
86} iCC;
87
88typedef struct _idCC {
89 /* word 1 */
90 UChar tag;
91 UChar instr_size;
92 UChar data_size;
93
94 /* words 2+ */
95 Addr instr_addr;
96 CC I;
97 CC D;
98} idCC;
99</pre>
100
101Each <code>CC</code> has three fields <code>a</code>, <code>m1</code>,
102<code>m2</code> for recording references, level 1 misses and level 2 misses.
103Each of these is a 64-bit <code>ULong</code> -- the numbers can get very large,
104ie. greater than 4.2 billion allowed by a 32-bit unsigned int.<p>
105
106A <code>iCC</code> has one <code>CC</code> for instruction cache accesses. A
107<code>idCC</code> has two, one for instruction cache accesses, and one for data
108cache accesses.<p>
109
110The <code>iCC</code> and <code>dCC</code> structs also store unchanging
111information about the instruction:
112<ul>
113 <li>An instruction-type identification tag (explained below)</li><p>
114 <li>Instruction size</li><p>
115 <li>Data reference size (<code>idCC</code> only)</li><p>
116 <li>Instruction address</li><p>
117</ul>
118
119Note that data address is not one of the fields for <code>idCC</code>. This is
120because for many memory-referencing instructions the data address can change
121each time it's executed (eg. if it uses register-offset addressing). We have
122to give this item to the cache simulation in a different way (see
123Instrumentation section below). Some memory-referencing instructions do always
124reference the same address, but we don't try to treat them specialy in order to
125keep things simple.<p>
126
127Also note that there is only room for recording info about one data cache
128access in an <code>idCC</code>. So what about instructions that do a read then
129a write, such as:
130
131<blockquote><code>inc %(esi)</code></blockquote>
132
133In a write-allocate cache, as simulated by Valgrind, the write cannot miss,
134since it immediately follows the read which will drag the block into the cache
135if it's not already there. So the write access isn't really interesting, and
136Valgrind doesn't record it. This means that Valgrind doesn't measure
137memory references, but rather memory references that could miss in the cache.
138This behaviour is the same as that used by the AMD Athlon hardware counters.
139It also has the benefit of simplifying the implementation -- instructions that
140read and write memory can be treated like instructions that read memory.<p>
141
142<h3>Storing cost-centres</h3>
143Cost centres are stored in a way that makes them very cheap to lookup, which is
144important since one is looked up for every original x86 instruction
145executed.<p>
146
147Valgrind does JIT translations at the basic block level, and cost centres are
148also setup and stored at the basic block level. By doing things carefully, we
149store all the cost centres for a basic block in a contiguous array, and lookup
150comes almost for free.<p>
151
152Consider this part of a basic block (for exposition purposes, pretend it's an
153entire basic block):
154
155<pre>
156movl $0x0,%eax
157movl $0x99, -4(%ebp)
158</pre>
159
160The translation to UCode looks like this:
161
162<pre>
163MOVL $0x0, t20
164PUTL t20, %EAX
165INCEIPo $5
166
167LEA1L -4(t4), t14
168MOVL $0x99, t18
169STL t18, (t14)
170INCEIPo $7
171</pre>
172
173The first step is to allocate the cost centres. This requires a preliminary
174pass to count how many x86 instructions were in the basic block, and their
175types (and thus sizes). UCode translations for single x86 instructions are
176delimited by the <code>INCEIPo</code> instruction, the argument of which gives
177the byte size of the instruction (note that lazy INCEIP updating is turned off
178to allow this).<p>
179
180We can tell if an x86 instruction references memory by looking for
181<code>LDL</code> and <code>STL</code> UCode instructions, and thus what kind of
182cost centre is required. From this we can determine how many cost centres we
183need for the basic block, and their sizes. We can then allocate them in a
184single array.<p>
185
186Consider the example code above. After the preliminary pass, we know we need
187two cost centres, one <code>iCC</code> and one <code>dCC</code>. So we
188allocate an array to store these which looks like this:
189
190<pre>
191|(uninit)| tag (1 byte)
192|(uninit)| instr_size (1 bytes)
193|(uninit)| (padding) (2 bytes)
194|(uninit)| instr_addr (4 bytes)
195|(uninit)| I.a (8 bytes)
196|(uninit)| I.m1 (8 bytes)
197|(uninit)| I.m2 (8 bytes)
198
199|(uninit)| tag (1 byte)
200|(uninit)| instr_size (1 byte)
201|(uninit)| data_size (1 byte)
202|(uninit)| (padding) (1 byte)
203|(uninit)| instr_addr (4 bytes)
204|(uninit)| I.a (8 bytes)
205|(uninit)| I.m1 (8 bytes)
206|(uninit)| I.m2 (8 bytes)
207|(uninit)| D.a (8 bytes)
208|(uninit)| D.m1 (8 bytes)
209|(uninit)| D.m2 (8 bytes)
210</pre>
211
212(We can see now why we need tags to distinguish between the two types of cost
213centres.)<p>
214
215We also record the size of the array. We look up the debug info of the first
216instruction in the basic block, and then stick the array into a table indexed
217by filename and function name. This makes it easy to dump the information
218quickly to file at the end.<p>
219
220<h3>Instrumentation</h3>
221The instrumentation pass has two main jobs:
222
223<ol>
224 <li>Fill in the gaps in the allocated cost centres.</li><p>
225 <li>Add UCode to call the cache simulator for each instruction.</li><p>
226</ol>
227
228The instrumentation pass steps through the UCode and the cost centres in
229tandem. As each original x86 instruction's UCode is processed, the appropriate
230gaps in the instructions cost centre are filled in, for example:
231
232<pre>
233|INSTR_CC| tag (1 byte)
234|5 | instr_size (1 bytes)
235|(uninit)| (padding) (2 bytes)
236|i_addr1 | instr_addr (4 bytes)
237|0 | I.a (8 bytes)
238|0 | I.m1 (8 bytes)
239|0 | I.m2 (8 bytes)
240
241|WRITE_CC| tag (1 byte)
242|7 | instr_size (1 byte)
243|4 | data_size (1 byte)
244|(uninit)| (padding) (1 byte)
245|i_addr2 | instr_addr (4 bytes)
246|0 | I.a (8 bytes)
247|0 | I.m1 (8 bytes)
248|0 | I.m2 (8 bytes)
249|0 | D.a (8 bytes)
250|0 | D.m1 (8 bytes)
251|0 | D.m2 (8 bytes)
252</pre>
253
254(Note that this step is not performed if a basic block is re-translated; see
255<a href="#retranslations">here</a> for more information.)<p>
256
257GCC inserts padding before the <code>instr_size</code> field so that it is word
258aligned.<p>
259
260The instrumentation added to call the cache simulation function looks like this
261(instrumentation is indented to distinguish it from the original UCode):
262
263<pre>
264MOVL $0x0, t20
265PUTL t20, %EAX
266 PUSHL %eax
267 PUSHL %ecx
268 PUSHL %edx
269 MOVL $0x4091F8A4, t46 # address of 1st CC
270 PUSHL t46
271 CALLMo $0x12 # second cachesim function
272 CLEARo $0x4
273 POPL %edx
274 POPL %ecx
275 POPL %eax
276INCEIPo $5
277
278LEA1L -4(t4), t14
279MOVL $0x99, t18
280 MOVL t14, t42
281STL t18, (t14)
282 PUSHL %eax
283 PUSHL %ecx
284 PUSHL %edx
285 PUSHL t42
286 MOVL $0x4091F8C4, t44 # address of 2nd CC
287 PUSHL t44
288 CALLMo $0x13 # second cachesim function
289 CLEARo $0x8
290 POPL %edx
291 POPL %ecx
292 POPL %eax
293INCEIPo $7
294</pre>
295
296Consider the first instruction's UCode. Each call is surrounded by three
297<code>PUSHL</code> and <code>POPL</code> instructions to save and restore the
298caller-save registers. Then the address of the instruction's cost centre is
299pushed onto the stack, to be the first argument to the cache simulation
300function. The address is known at this point because we are doing a
301simultaneous pass through the cost centre array. This means the cost centre
302lookup for each instruction is almost free (just the cost of pushing an
303argument for a function call). Then the call to the cache simulation function
304for non-memory-reference instructions is made (note that the
305<code>CALLMo</code> UInstruction takes an offset into a table of predefined
306functions; it is not an absolute address), and the single argument is
307<code>CLEAR</code>ed from the stack.<p>
308
309The second instruction's UCode is similar. The only difference is that, as
310mentioned before, we have to pass the address of the data item referenced to
311the cache simulation function too. This explains the <code>MOVL t14,
312t42</code> and <code>PUSHL t42</code> UInstructions. (Note that the seemingly
313redundant <code>MOV</code>ing will probably be optimised away during register
314allocation.)<p>
315
316Note that instead of storing unchanging information about each instruction
317(instruction size, data size, etc) in its cost centre, we could have passed in
318these arguments to the simulation function. But this would slow the calls down
319(two or three extra arguments pushed onto the stack). Also it would bloat the
320UCode instrumentation by amounts similar to the space required for them in the
321cost centre; bloated UCode would also fill the translation cache more quickly,
322requiring more translations for large programs and slowing them down more.<p>
323
324<a name="retranslations"></a>
325<h3>Handling basic block retranslations</h3>
326The above description ignores one complication. Valgrind has a limited size
327cache for basic block translations; if it fills up, old translations are
328discarded. If a discarded basic block is executed again, it must be
329re-translated.<p>
330
331However, we can't use this approach for profiling -- we can't throw away cost
332centres for instructions in the middle of execution! So when a basic block is
333translated, we first look for its cost centre array in the hash table. If
334there is no cost centre array, it must be the first translation, so we proceed
335as described above. But if there is a cost centre array already, it must be a
336retranslation. In this case, we skip the cost centre allocation and
337initialisation steps, but still do the UCode instrumentation step.<p>
338
339<h3>The cache simulation</h3>
340The cache simulation is fairly straightforward. It just tracks which memory
341blocks are in the cache at the moment (it doesn't track the contents, since
342that is irrelevant).<p>
343
344The interface to the simulation is quite clean. The functions called from the
345UCode contain calls to the simulation functions in the files
346<Code>vg_cachesim_{I1,D1,L2}.c</code>; these calls are inlined so that only
347one function call is done per simulated x86 instruction. The file
348<code>vg_cachesim.c</code> simply <code>#include</code>s the three files
349containing the simulation, which makes plugging in new cache simulations is
350very easy -- you just replace the three files and recompile.<p>
351
352<h3>Output</h3>
353Output is fairly straightforward, basically printing the cost centre for every
354instruction, grouped by files and functions. Total counts (eg. total cache
355accesses, total L1 misses) are calculated when traversing this structure rather
356than during execution, to save time; the cache simulation functions are called
357so often that even one or two extra adds can make a sizeable difference.<p>
358
359Input file has the following format:
360
361<pre>
362file ::= desc_line* cmd_line events_line data_line+ summary_line
363desc_line ::= "desc:" ws? non_nl_string
364cmd_line ::= "cmd:" ws? cmd
365events_line ::= "events:" ws? (event ws)+
366data_line ::= file_line | fn_line | count_line
367file_line ::= ("fl=" | "fi=" | "fe=") filename
368fn_line ::= "fn=" fn_name
369count_line ::= line_num ws? (count ws)+
370summary_line ::= "summary:" ws? (count ws)+
371count ::= num | "."
372</pre>
373
374Where:
375
376<ul>
377 <li><code>non_nl_string</code> is any string not containing a newline.</li><p>
378 <li><code>cmd</code> is a command line invocation.</li><p>
379 <li><code>filename</code> and <code>fn_name</code> can be anything.</li><p>
380 <li><code>num</code> and <code>line_num</code> are decimal numbers.</li><p>
381 <li><code>ws</code> is whitespace.</li><p>
382 <li><code>nl</code> is a newline.</li><p>
383</ul>
384
385The contents of the "desc:" lines is printed out at the top of the summary.
386This is a generic way of providing simulation specific information, eg. for
387giving the cache configuration for cache simulation.<p>
388
389Counts can be "." to represent "N/A", eg. the number of write misses for an
390instruction that doesn't write to memory.<p>
391
392The number of counts in each <code>line</code> and the
393<code>summary_line</code> should not exceed the number of events in the
394<code>event_line</code>. If the number in each <code>line</code> is less,
395cg_annotate treats those missing as though they were a "." entry. <p>
396
397A <code>file_line</code> changes the current file name. A <code>fn_line</code>
398changes the current function name. A <code>count_line</code> contains counts
399that pertain to the current filename/fn_name. A "fn=" <code>file_line</code>
400and a <code>fn_line</code> must appear before any <code>count_line</code>s to
401give the context of the first <code>count_line</code>s.<p>
402
403Each <code>file_line</code> should be immediately followed by a
404<code>fn_line</code>. "fi=" <code>file_lines</code> are used to switch
405filenames for inlined functions; "fe=" <code>file_lines</code> are similar, but
406are put at the end of a basic block in which the file name hasn't been switched
407back to the original file name. (fi and fe lines behave the same, they are
408only distinguished to help debugging.)<p>
409
410
411<h3>Summary of performance features</h3>
412Quite a lot of work has gone into making the profiling as fast as possible.
413This is a summary of the important features:
414
415<ul>
416 <li>The basic block-level cost centre storage allows almost free cost centre
417 lookup.</li><p>
418
419 <li>Only one function call is made per instruction simulated; even this
420 accounts for a sizeable percentage of execution time, but it seems
421 unavoidable if we want flexibility in the cache simulator.</li><p>
422
423 <li>Unchanging information about an instruction is stored in its cost centre,
424 avoiding unnecessary argument pushing, and minimising UCode
425 instrumentation bloat.</li><p>
426
427 <li>Summary counts are calculated at the end, rather than during
428 execution.</li><p>
429
430 <li>The <code>cachegrind.out</code> output files can contain huge amounts of
431 information; file format was carefully chosen to minimise file
432 sizes.</li><p>
433</ul>
434
435
436<h3>Annotation</h3>
437Annotation is done by cg_annotate. It is a fairly straightforward Perl script
438that slurps up all the cost centres, and then runs through all the chosen
439source files, printing out cost centres with them. It too has been carefully
440optimised.
441
442
443<h3>Similar work, extensions</h3>
444It would be relatively straightforward to do other simulations and obtain
445line-by-line information about interesting events. A good example would be
446branch prediction -- all branches could be instrumented to interact with a
447branch prediction simulator, using very similar techniques to those described
448above.<p>
449
450In particular, cg_annotate would not need to change -- the file format is such
451that it is not specific to the cache simulation, but could be used for any kind
452of line-by-line information. The only part of cg_annotate that is specific to
453the cache simulation is the name of the input file
454(<code>cachegrind.out</code>), although it would be very simple to add an
455option to control this.<p>
456
457</body>
458</html>