Software: Apache/2.0.54 (Fedora). PHP/5.0.4 uname -a: Linux mina-info.me 2.6.17-1.2142_FC4smp #1 SMP Tue Jul 11 22:57:02 EDT 2006 i686 uid=48(apache) gid=48(apache) groups=48(apache) Safe-mode: OFF (not secure) /usr/share/doc/valgrind-2.4.0/ drwxr-xr-x | |
| Viewing file: Select action/file-type: How Cachegrind works
njn25@cam.ac.uk Copyright © 2001-2003 Nick Nethercote
Cache profilingValgrind is a very nice platform for doing cache profiling and other kinds of simulation, because it converts horrible x86 instructions into nice clean RISC-like UCode. For example, for cache profiling we are interested in instructions that read and write memory; in UCode there are only four instructions that do this:LOAD, STORE,
FPU_R and FPU_W. By contrast, because of the x86
addressing modes, almost every instruction can read or write memory.
Most of the cache profiling machinery is in the file
These notes are a somewhat haphazard guide to how Valgrind's cache profiling works.
Cost centresValgrind gathers cache profiling about every instruction executed, individually. Each instruction has a cost centre associated with it. There are two kinds of cost centre: one for instructions that don't reference memory (iCC), and one for instructions that do
(idCC):
typedef struct _CC {
ULong a;
ULong m1;
ULong m2;
} CC;
typedef struct _iCC {
/* word 1 */
UChar tag;
UChar instr_size;
/* words 2+ */
Addr instr_addr;
CC I;
} iCC;
typedef struct _idCC {
/* word 1 */
UChar tag;
UChar instr_size;
UChar data_size;
/* words 2+ */
Addr instr_addr;
CC I;
CC D;
} idCC;
Each CC has three fields a, m1,
m2 for recording references, level 1 misses and level 2 misses.
Each of these is a 64-bit ULong -- the numbers can get very large,
ie. greater than 4.2 billion allowed by a 32-bit unsigned int.
A
The
idCC. This is
because for many memory-referencing instructions the data address can change
each time it's executed (eg. if it uses register-offset addressing). We have
to give this item to the cache simulation in a different way (see
Instrumentation section below). Some memory-referencing instructions do always
reference the same address, but we don't try to treat them specialy in order to
keep things simple.
Also note that there is only room for recording info about one data cache
access in an
Storing cost-centresCost centres are stored in a way that makes them very cheap to lookup, which is important since one is looked up for every original x86 instruction executed.Valgrind does JIT translations at the basic block level, and cost centres are also setup and stored at the basic block level. By doing things carefully, we store all the cost centres for a basic block in a contiguous array, and lookup comes almost for free. Consider this part of a basic block (for exposition purposes, pretend it's an entire basic block): movl $0x0,%eax movl $0x99, -4(%ebp)The translation to UCode looks like this: MOVL $0x0, t20 PUTL t20, %EAX INCEIPo $5 LEA1L -4(t4), t14 MOVL $0x99, t18 STL t18, (t14) INCEIPo $7The first step is to allocate the cost centres. This requires a preliminary pass to count how many x86 instructions were in the basic block, and their types (and thus sizes). UCode translations for single x86 instructions are delimited by the INCEIPo instruction, the argument of which gives
the byte size of the instruction (note that lazy INCEIP updating is turned off
to allow this).
We can tell if an x86 instruction references memory by looking for
Consider the example code above. After the preliminary pass, we know we need
two cost centres, one |(uninit)| tag (1 byte) |(uninit)| instr_size (1 bytes) |(uninit)| (padding) (2 bytes) |(uninit)| instr_addr (4 bytes) |(uninit)| I.a (8 bytes) |(uninit)| I.m1 (8 bytes) |(uninit)| I.m2 (8 bytes) |(uninit)| tag (1 byte) |(uninit)| instr_size (1 byte) |(uninit)| data_size (1 byte) |(uninit)| (padding) (1 byte) |(uninit)| instr_addr (4 bytes) |(uninit)| I.a (8 bytes) |(uninit)| I.m1 (8 bytes) |(uninit)| I.m2 (8 bytes) |(uninit)| D.a (8 bytes) |(uninit)| D.m1 (8 bytes) |(uninit)| D.m2 (8 bytes)(We can see now why we need tags to distinguish between the two types of cost centres.) We also record the size of the array. We look up the debug info of the first instruction in the basic block, and then stick the array into a table indexed by filename and function name. This makes it easy to dump the information quickly to file at the end.
InstrumentationThe instrumentation pass has two main jobs:
|INSTR_CC| tag (1 byte) |5 | instr_size (1 bytes) |(uninit)| (padding) (2 bytes) |i_addr1 | instr_addr (4 bytes) |0 | I.a (8 bytes) |0 | I.m1 (8 bytes) |0 | I.m2 (8 bytes) |WRITE_CC| tag (1 byte) |7 | instr_size (1 byte) |4 | data_size (1 byte) |(uninit)| (padding) (1 byte) |i_addr2 | instr_addr (4 bytes) |0 | I.a (8 bytes) |0 | I.m1 (8 bytes) |0 | I.m2 (8 bytes) |0 | D.a (8 bytes) |0 | D.m1 (8 bytes) |0 | D.m2 (8 bytes)(Note that this step is not performed if a basic block is re-translated; see here for more information.)
GCC inserts padding before the The instrumentation added to call the cache simulation function looks like this (instrumentation is indented to distinguish it from the original UCode): MOVL $0x0, t20 PUTL t20, %EAX PUSHL %eax PUSHL %ecx PUSHL %edx MOVL $0x4091F8A4, t46 # address of 1st CC PUSHL t46 CALLMo $0x12 # second cachesim function CLEARo $0x4 POPL %edx POPL %ecx POPL %eax INCEIPo $5 LEA1L -4(t4), t14 MOVL $0x99, t18 MOVL t14, t42 STL t18, (t14) PUSHL %eax PUSHL %ecx PUSHL %edx PUSHL t42 MOVL $0x4091F8C4, t44 # address of 2nd CC PUSHL t44 CALLMo $0x13 # second cachesim function CLEARo $0x8 POPL %edx POPL %ecx POPL %eax INCEIPo $7Consider the first instruction's UCode. Each call is surrounded by three PUSHL and POPL instructions to save and restore the
caller-save registers. Then the address of the instruction's cost centre is
pushed onto the stack, to be the first argument to the cache simulation
function. The address is known at this point because we are doing a
simultaneous pass through the cost centre array. This means the cost centre
lookup for each instruction is almost free (just the cost of pushing an
argument for a function call). Then the call to the cache simulation function
for non-memory-reference instructions is made (note that the
CALLMo UInstruction takes an offset into a table of predefined
functions; it is not an absolute address), and the single argument is
CLEARed from the stack.
The second instruction's UCode is similar. The only difference is that, as
mentioned before, we have to pass the address of the data item referenced to
the cache simulation function too. This explains the Note that instead of storing unchanging information about each instruction (instruction size, data size, etc) in its cost centre, we could have passed in these arguments to the simulation function. But this would slow the calls down (two or three extra arguments pushed onto the stack). Also it would bloat the UCode instrumentation by amounts similar to the space required for them in the cost centre; bloated UCode would also fill the translation cache more quickly, requiring more translations for large programs and slowing them down more. Handling basic block retranslationsThe above description ignores one complication. Valgrind has a limited size cache for basic block translations; if it fills up, old translations are discarded. If a discarded basic block is executed again, it must be re-translated.However, we can't use this approach for profiling -- we can't throw away cost centres for instructions in the middle of execution! So when a basic block is translated, we first look for its cost centre array in the hash table. If there is no cost centre array, it must be the first translation, so we proceed as described above. But if there is a cost centre array already, it must be a retranslation. In this case, we skip the cost centre allocation and initialisation steps, but still do the UCode instrumentation step.
The cache simulationThe cache simulation is fairly straightforward. It just tracks which memory blocks are in the cache at the moment (it doesn't track the contents, since that is irrelevant).
The interface to the simulation is quite clean. The functions called from the
UCode contain calls to the simulation functions in the files
OutputOutput is fairly straightforward, basically printing the cost centre for every instruction, grouped by files and functions. Total counts (eg. total cache accesses, total L1 misses) are calculated when traversing this structure rather than during execution, to save time; the cache simulation functions are called so often that even one or two extra adds can make a sizeable difference.Input file has the following format:
file ::= desc_line* cmd_line events_line data_line+ summary_line
desc_line ::= "desc:" ws? non_nl_string
cmd_line ::= "cmd:" ws? cmd
events_line ::= "events:" ws? (event ws)+
data_line ::= file_line | fn_line | count_line
file_line ::= ("fl=" | "fi=" | "fe=") filename
fn_line ::= "fn=" fn_name
count_line ::= line_num ws? (count ws)+
summary_line ::= "summary:" ws? (count ws)+
count ::= num | "."
Where:
Counts can be "." to represent "N/A", eg. the number of write misses for an instruction that doesn't write to memory.
The number of counts in each
A
Each
Summary of performance featuresQuite a lot of work has gone into making the profiling as fast as possible. This is a summary of the important features:
AnnotationAnnotation is done by cg_annotate. It is a fairly straightforward Perl script that slurps up all the cost centres, and then runs through all the chosen source files, printing out cost centres with them. It too has been carefully optimised.Similar work, extensionsIt would be relatively straightforward to do other simulations and obtain line-by-line information about interesting events. A good example would be branch prediction -- all branches could be instrumented to interact with a branch prediction simulator, using very similar techniques to those described above.
In particular, cg_annotate would not need to change -- the file format is such
that it is not specific to the cache simulation, but could be used for any kind
of line-by-line information. The only part of cg_annotate that is specific to
the cache simulation is the name of the input file
(
|
:: Command execute :: | |
--[ c99shell v. 1.0 pre-release build #16 powered by Captain Crunch Security Team | http://ccteam.ru | Generation time: 0.0027 ]-- |