2 /*--------------------------------------------------------------------*/
3 /*--- Cache simulation cg_sim.c ---*/
4 /*--------------------------------------------------------------------*/
7 This file is part of Cachegrind, a Valgrind tool for cache
10 Copyright (C) 2002-2017 Nicholas Nethercote
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.
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.
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
28 The GNU General Public License is contained in the file COPYING.
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)
44 Int line_size
; /* bytes */
49 HChar desc_line
[128]; /* large enough */
53 /* By this point, the size/assoc/line_size has been checked. */
54 static void cachesim_initcache(cache_t config
, cache_t2
* c
)
58 c
->size
= config
.size
;
59 c
->assoc
= config
.assoc
;
60 c
->line_size
= config
.line_size
;
62 c
->sets
= (c
->size
/ c
->line_size
) / c
->assoc
;
63 c
->sets_min_1
= c
->sets
- 1;
64 c
->line_size_bits
= VG_(log2
)(c
->line_size
);
65 c
->tag_shift
= c
->line_size_bits
+ VG_(log2
)(c
->sets
);
68 VG_(sprintf
)(c
->desc_line
, "%d B, %d B, direct-mapped",
69 c
->size
, c
->line_size
);
71 VG_(sprintf
)(c
->desc_line
, "%d B, %d B, %d-way associative",
72 c
->size
, c
->line_size
, c
->assoc
);
75 c
->tags
= VG_(malloc
)("cg.sim.ci.1",
76 sizeof(UWord
) * c
->sets
* c
->assoc
);
78 for (i
= 0; i
< c
->sets
* c
->assoc
; i
++)
82 /* This attribute forces GCC to inline the function, getting rid of a
83 * lot of indirection around the cache_t2 pointer, if it is known to be
84 * constant in the caller (the caller is inlined itself).
85 * Without inlining of simulator functions, cachegrind can get 40% slower.
87 __attribute__((always_inline
))
89 Bool
cachesim_setref_is_miss(cache_t2
* c
, UInt set_no
, UWord tag
)
94 set
= &(c
->tags
[set_no
* c
->assoc
]);
96 /* This loop is unrolled for just the first case, which is the most */
97 /* common. We can't unroll any further because it would screw up */
98 /* if we have a direct-mapped (1-way) cache. */
102 /* If the tag is one other than the MRU, move it into the MRU spot */
103 /* and shuffle the rest down. */
104 for (i
= 1; i
< c
->assoc
; i
++) {
106 for (j
= i
; j
> 0; j
--) {
115 /* A miss; install this tag as MRU, shuffle rest down. */
116 for (j
= c
->assoc
- 1; j
> 0; j
--) {
124 __attribute__((always_inline
))
126 Bool
cachesim_ref_is_miss(cache_t2
* c
, Addr a
, UChar size
)
128 /* A memory block has the size of a cache line */
129 UWord block1
= a
>> c
->line_size_bits
;
130 UWord block2
= (a
+size
-1) >> c
->line_size_bits
;
131 UInt set1
= block1
& c
->sets_min_1
;
133 /* Tags used in real caches are minimal to save space.
134 * As the last bits of the block number of addresses mapping
135 * into one cache set are the same, real caches use as tag
136 * tag = block >> log2(#sets)
137 * But using the memory block as more specific tag is fine,
138 * and saves instructions.
142 /* Access entirely within line. */
143 if (block1
== block2
)
144 return cachesim_setref_is_miss(c
, set1
, tag1
);
146 /* Access straddles two lines. */
147 else if (block1
+ 1 == block2
) {
148 UInt set2
= block2
& c
->sets_min_1
;
151 /* always do both, as state is updated as side effect */
152 if (cachesim_setref_is_miss(c
, set1
, tag1
)) {
153 cachesim_setref_is_miss(c
, set2
, tag2
);
156 return cachesim_setref_is_miss(c
, set2
, tag2
);
158 VG_(printf
)("addr: %lx size: %u blocks: %lu %lu",
159 a
, size
, block1
, block2
);
160 VG_(tool_panic
)("item straddles more than two cache sets");
170 static void cachesim_initcaches(cache_t I1c
, cache_t D1c
, cache_t LLc
)
172 cachesim_initcache(I1c
, &I1
);
173 cachesim_initcache(D1c
, &D1
);
174 cachesim_initcache(LLc
, &LL
);
177 __attribute__((always_inline
))
179 void cachesim_I1_doref_Gen(Addr a
, UChar size
, ULong
* m1
, ULong
*mL
)
181 if (cachesim_ref_is_miss(&I1
, a
, size
)) {
183 if (cachesim_ref_is_miss(&LL
, a
, size
))
188 // common special case IrNoX
189 __attribute__((always_inline
))
191 void cachesim_I1_doref_NoX(Addr a
, UChar size
, ULong
* m1
, ULong
*mL
)
193 UWord block
= a
>> I1
.line_size_bits
;
194 UInt I1_set
= block
& I1
.sets_min_1
;
197 if (cachesim_setref_is_miss(&I1
, I1_set
, block
)) {
198 UInt LL_set
= block
& LL
.sets_min_1
;
200 // can use block as tag as L1I and LL cache line sizes are equal
201 if (cachesim_setref_is_miss(&LL
, LL_set
, block
))
206 __attribute__((always_inline
))
208 void cachesim_D1_doref(Addr a
, UChar size
, ULong
* m1
, ULong
*mL
)
210 if (cachesim_ref_is_miss(&D1
, a
, size
)) {
212 if (cachesim_ref_is_miss(&LL
, a
, size
))
217 /* Check for special case IrNoX. Called at instrumentation time.
219 * Does this Ir only touch one cache line, and are L1I/LL cache
220 * line sizes the same? This allows to get rid of a runtime check.
222 * Returning false is always fine, as this calls the generic case
224 static Bool
cachesim_is_IrNoX(Addr a
, UChar size
)
226 UWord block1
, block2
;
228 if (I1
.line_size_bits
!= LL
.line_size_bits
) return False
;
229 block1
= a
>> I1
.line_size_bits
;
230 block2
= (a
+size
-1) >> I1
.line_size_bits
;
231 if (block1
!= block2
) return False
;
236 /*--------------------------------------------------------------------*/
237 /*--- end cg_sim.c ---*/
238 /*--------------------------------------------------------------------*/