blob: ddf50b419c22e61c071aae5d2bb3b2b526a4979f [file] [log] [blame]
nethercote27fc1da2004-01-04 16:56:57 +00001
2/*--------------------------------------------------------------------*/
3/*--- Cache simulation cg_sim.c ---*/
4/*--------------------------------------------------------------------*/
5
6/*
7 This file is part of Cachegrind, a Valgrind tool for cache
8 profiling programs.
9
sewardj4d474d02008-02-11 11:34:59 +000010 Copyright (C) 2002-2008 Nicholas Nethercote
njn2bc10122005-05-08 02:10:27 +000011 njn@valgrind.org
nethercote27fc1da2004-01-04 16:56:57 +000012
13 This program is free software; you can redistribute it and/or
14 modify it under the terms of the GNU General Public License as
15 published by the Free Software Foundation; either version 2 of the
16 License, or (at your option) any later version.
17
18 This program is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 General Public License for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26 02111-1307, USA.
27
28 The GNU General Public License is contained in the file COPYING.
29*/
30
31/* Notes:
32 - simulates a write-allocate cache
33 - (block --> set) hash function uses simple bit selection
34 - handling of references straddling two cache blocks:
35 - counts as only one cache access (not two)
36 - both blocks hit --> one hit
37 - one block hits, the other misses --> one miss
38 - both blocks miss --> one miss (not two)
39*/
40
41typedef struct {
njn0103de52005-10-10 16:49:01 +000042 Int size; /* bytes */
43 Int assoc;
44 Int line_size; /* bytes */
45 Int sets;
46 Int sets_min_1;
47 Int assoc_bits;
48 Int line_size_bits;
49 Int tag_shift;
50 Char desc_line[128];
njnb619ca72005-10-10 16:18:09 +000051 UWord* tags;
nethercote27fc1da2004-01-04 16:56:57 +000052} cache_t2;
53
54/* By this point, the size/assoc/line_size has been checked. */
55static void cachesim_initcache(cache_t config, cache_t2* c)
56{
njn0103de52005-10-10 16:49:01 +000057 Int i;
nethercote27fc1da2004-01-04 16:56:57 +000058
59 c->size = config.size;
60 c->assoc = config.assoc;
61 c->line_size = config.line_size;
62
63 c->sets = (c->size / c->line_size) / c->assoc;
64 c->sets_min_1 = c->sets - 1;
65 c->assoc_bits = VG_(log2)(c->assoc);
66 c->line_size_bits = VG_(log2)(c->line_size);
67 c->tag_shift = c->line_size_bits + VG_(log2)(c->sets);
68
69 if (c->assoc == 1) {
70 VG_(sprintf)(c->desc_line, "%d B, %d B, direct-mapped",
71 c->size, c->line_size);
72 } else {
73 VG_(sprintf)(c->desc_line, "%d B, %d B, %d-way associative",
74 c->size, c->line_size, c->assoc);
75 }
76
njnb619ca72005-10-10 16:18:09 +000077 c->tags = VG_(malloc)(sizeof(UWord) * c->sets * c->assoc);
nethercote27fc1da2004-01-04 16:56:57 +000078
79 for (i = 0; i < c->sets * c->assoc; i++)
80 c->tags[i] = 0;
81}
82
nethercote27fc1da2004-01-04 16:56:57 +000083/* This is done as a macro rather than by passing in the cache_t2 as an
84 * arg because it slows things down by a small amount (3-5%) due to all
85 * that extra indirection. */
86
87#define CACHESIM(L, MISS_TREATMENT) \
88/* The cache and associated bits and pieces. */ \
89static cache_t2 L; \
90 \
91static void cachesim_##L##_initcache(cache_t config) \
92{ \
93 cachesim_initcache(config, &L); \
94} \
95 \
njnfcd04882005-11-13 17:57:32 +000096/* This attribute forces GCC to inline this function, even though it's */ \
97/* bigger than its usual limit. Inlining gains around 5--10% speedup. */ \
98__attribute__((always_inline)) \
99static __inline__ \
nethercote27fc1da2004-01-04 16:56:57 +0000100void cachesim_##L##_doref(Addr a, UChar size, ULong* m1, ULong *m2) \
101{ \
njncbdfcd62006-11-22 11:38:07 +0000102 UInt set1 = ( a >> L.line_size_bits) & (L.sets_min_1); \
103 UInt set2 = ((a+size-1) >> L.line_size_bits) & (L.sets_min_1); \
104 UWord tag = a >> L.tag_shift; \
105 UWord tag2; \
njn0103de52005-10-10 16:49:01 +0000106 Int i, j; \
nethercote27fc1da2004-01-04 16:56:57 +0000107 Bool is_miss = False; \
njnb619ca72005-10-10 16:18:09 +0000108 UWord* set; \
nethercote27fc1da2004-01-04 16:56:57 +0000109 \
110 /* First case: word entirely within line. */ \
111 if (set1 == set2) { \
112 \
113 /* Shifting is a bit faster than multiplying */ \
114 set = &(L.tags[set1 << L.assoc_bits]); \
115 \
116 /* This loop is unrolled for just the first case, which is the most */\
117 /* common. We can't unroll any further because it would screw up */\
118 /* if we have a direct-mapped (1-way) cache. */\
119 if (tag == set[0]) { \
120 return; \
121 } \
122 /* If the tag is one other than the MRU, move it into the MRU spot */\
123 /* and shuffle the rest down. */\
124 for (i = 1; i < L.assoc; i++) { \
125 if (tag == set[i]) { \
126 for (j = i; j > 0; j--) { \
127 set[j] = set[j - 1]; \
128 } \
129 set[0] = tag; \
130 return; \
131 } \
132 } \
133 \
134 /* A miss; install this tag as MRU, shuffle rest down. */ \
135 for (j = L.assoc - 1; j > 0; j--) { \
136 set[j] = set[j - 1]; \
137 } \
138 set[0] = tag; \
139 MISS_TREATMENT; \
140 return; \
141 \
142 /* Second case: word straddles two lines. */ \
143 /* Nb: this is a fast way of doing ((set1+1) % L.sets) */ \
144 } else if (((set1 + 1) & (L.sets-1)) == set2) { \
145 set = &(L.tags[set1 << L.assoc_bits]); \
146 if (tag == set[0]) { \
147 goto block2; \
148 } \
149 for (i = 1; i < L.assoc; i++) { \
150 if (tag == set[i]) { \
151 for (j = i; j > 0; j--) { \
152 set[j] = set[j - 1]; \
153 } \
154 set[0] = tag; \
155 goto block2; \
156 } \
157 } \
158 for (j = L.assoc - 1; j > 0; j--) { \
159 set[j] = set[j - 1]; \
160 } \
161 set[0] = tag; \
162 is_miss = True; \
163block2: \
164 set = &(L.tags[set2 << L.assoc_bits]); \
njncbdfcd62006-11-22 11:38:07 +0000165 tag2 = (a+size-1) >> L.tag_shift; \
166 if (tag2 == set[0]) { \
nethercote27fc1da2004-01-04 16:56:57 +0000167 goto miss_treatment; \
168 } \
169 for (i = 1; i < L.assoc; i++) { \
njncbdfcd62006-11-22 11:38:07 +0000170 if (tag2 == set[i]) { \
nethercote27fc1da2004-01-04 16:56:57 +0000171 for (j = i; j > 0; j--) { \
172 set[j] = set[j - 1]; \
173 } \
njncbdfcd62006-11-22 11:38:07 +0000174 set[0] = tag2; \
nethercote27fc1da2004-01-04 16:56:57 +0000175 goto miss_treatment; \
176 } \
177 } \
178 for (j = L.assoc - 1; j > 0; j--) { \
179 set[j] = set[j - 1]; \
180 } \
njncbdfcd62006-11-22 11:38:07 +0000181 set[0] = tag2; \
nethercote27fc1da2004-01-04 16:56:57 +0000182 is_miss = True; \
183miss_treatment: \
184 if (is_miss) { MISS_TREATMENT; } \
185 \
186 } else { \
njn8a7b41b2007-09-23 00:51:24 +0000187 VG_(printf)("addr: %lx size: %u sets: %d %d", a, size, set1, set2);\
njn67993252004-11-22 18:02:32 +0000188 VG_(tool_panic)("item straddles more than two cache sets"); \
nethercote27fc1da2004-01-04 16:56:57 +0000189 } \
190 return; \
191}
192
193CACHESIM(L2, (*m2)++ );
194CACHESIM(I1, { (*m1)++; cachesim_L2_doref(a, size, m1, m2); } );
195CACHESIM(D1, { (*m1)++; cachesim_L2_doref(a, size, m1, m2); } );
196
197/*--------------------------------------------------------------------*/
198/*--- end cg_sim.c ---*/
199/*--------------------------------------------------------------------*/
200