1 /*--------------------------------------------------------------------*/
2 /*--- Callgrind ---*/
3 /*--- ct_jumps.c ---*/
4 /*--------------------------------------------------------------------*/
5
6 /*
7 This file is part of Callgrind, a Valgrind tool for call tracing.
8
9 Copyright (C) 2002-2010, Josef Weidendorfer (Josef.Weidendorfer@gmx.de)
10
11 This program is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License as
13 published by the Free Software Foundation; either version 2 of the
14 License, or (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful, but
17 WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
24 02111-1307, USA.
25
26 The GNU General Public License is contained in the file COPYING.
27 */
28
29 #include "global.h"
30
31 #define N_JCC_INITIAL_ENTRIES 4437
32
33 /*------------------------------------------------------------*/
34 /*--- Jump Cost Center (JCC) operations, including Calls ---*/
35 /*------------------------------------------------------------*/
36
37 #define N_JCC_INITIAL_ENTRIES 4437
38
39 jcc_hash current_jccs;
40
CLG_(init_jcc_hash)41 void CLG_(init_jcc_hash)(jcc_hash* jccs)
42 {
43 Int i;
44
45 CLG_ASSERT(jccs != 0);
46
47 jccs->size = N_JCC_INITIAL_ENTRIES;
48 jccs->entries = 0;
49 jccs->table = (jCC**) CLG_MALLOC("cl.jumps.ijh.1",
50 jccs->size * sizeof(jCC*));
51 jccs->spontaneous = 0;
52
53 for (i = 0; i < jccs->size; i++)
54 jccs->table[i] = 0;
55 }
56
57
CLG_(copy_current_jcc_hash)58 void CLG_(copy_current_jcc_hash)(jcc_hash* dst)
59 {
60 CLG_ASSERT(dst != 0);
61
62 dst->size = current_jccs.size;
63 dst->entries = current_jccs.entries;
64 dst->table = current_jccs.table;
65 dst->spontaneous = current_jccs.spontaneous;
66 }
67
CLG_(set_current_jcc_hash)68 void CLG_(set_current_jcc_hash)(jcc_hash* h)
69 {
70 CLG_ASSERT(h != 0);
71
72 current_jccs.size = h->size;
73 current_jccs.entries = h->entries;
74 current_jccs.table = h->table;
75 current_jccs.spontaneous = h->spontaneous;
76 }
77
78 __inline__
jcc_hash_idx(BBCC * from,UInt jmp,BBCC * to,UInt size)79 static UInt jcc_hash_idx(BBCC* from, UInt jmp, BBCC* to, UInt size)
80 {
81 return (UInt) ( (UWord)from + 7* (UWord)to + 13*jmp) % size;
82 }
83
84 /* double size of jcc table */
resize_jcc_table(void)85 static void resize_jcc_table(void)
86 {
87 Int i, new_size, conflicts1 = 0, conflicts2 = 0;
88 jCC** new_table;
89 UInt new_idx;
90 jCC *curr_jcc, *next_jcc;
91
92 new_size = 2* current_jccs.size +3;
93 new_table = (jCC**) CLG_MALLOC("cl.jumps.rjt.1",
94 new_size * sizeof(jCC*));
95
96 if (!new_table) return;
97
98 for (i = 0; i < new_size; i++)
99 new_table[i] = NULL;
100
101 for (i = 0; i < current_jccs.size; i++) {
102 if (current_jccs.table[i] == NULL) continue;
103
104 curr_jcc = current_jccs.table[i];
105 while (NULL != curr_jcc) {
106 next_jcc = curr_jcc->next_hash;
107
108 new_idx = jcc_hash_idx(curr_jcc->from, curr_jcc->jmp,
109 curr_jcc->to, new_size);
110
111 curr_jcc->next_hash = new_table[new_idx];
112 new_table[new_idx] = curr_jcc;
113 if (curr_jcc->next_hash) {
114 conflicts1++;
115 if (curr_jcc->next_hash->next_hash)
116 conflicts2++;
117 }
118
119 curr_jcc = next_jcc;
120 }
121 }
122
123 VG_(free)(current_jccs.table);
124
125
126 CLG_DEBUG(0, "Resize JCC Hash: %d => %d (entries %d, conflicts %d/%d)\n",
127 current_jccs.size, new_size,
128 current_jccs.entries, conflicts1, conflicts2);
129
130 current_jccs.size = new_size;
131 current_jccs.table = new_table;
132 CLG_(stat).jcc_hash_resizes++;
133 }
134
135
136
137 /* new jCC structure: a call was done to a BB of a BBCC
138 * for a spontaneous call, from is 0 (i.e. caller unknown)
139 */
new_jcc(BBCC * from,UInt jmp,BBCC * to)140 static jCC* new_jcc(BBCC* from, UInt jmp, BBCC* to)
141 {
142 jCC* jcc;
143 UInt new_idx;
144
145 /* check fill degree of jcc hash table and resize if needed (>80%) */
146 current_jccs.entries++;
147 if (10 * current_jccs.entries / current_jccs.size > 8)
148 resize_jcc_table();
149
150 jcc = (jCC*) CLG_MALLOC("cl.jumps.nj.1", sizeof(jCC));
151
152 jcc->from = from;
153 jcc->jmp = jmp;
154 jcc->to = to;
155 jcc->jmpkind = Ijk_Call;
156 jcc->call_counter = 0;
157 jcc->cost = 0;
158
159 /* insert into JCC chain of calling BBCC.
160 * This list is only used at dumping time */
161
162 if (from) {
163 /* Prohibit corruption by array overrun */
164 CLG_ASSERT((0 <= jmp) && (jmp <= from->bb->cjmp_count));
165 jcc->next_from = from->jmp[jmp].jcc_list;
166 from->jmp[jmp].jcc_list = jcc;
167 }
168 else {
169 jcc->next_from = current_jccs.spontaneous;
170 current_jccs.spontaneous = jcc;
171 }
172
173 /* insert into JCC hash table */
174 new_idx = jcc_hash_idx(from, jmp, to, current_jccs.size);
175 jcc->next_hash = current_jccs.table[new_idx];
176 current_jccs.table[new_idx] = jcc;
177
178 CLG_(stat).distinct_jccs++;
179
180 CLG_DEBUGIF(3) {
181 VG_(printf)(" new_jcc (now %d): %p\n",
182 CLG_(stat).distinct_jccs, jcc);
183 }
184
185 return jcc;
186 }
187
188
189 /* get the jCC for a call arc (BBCC->BBCC) */
CLG_(get_jcc)190 jCC* CLG_(get_jcc)(BBCC* from, UInt jmp, BBCC* to)
191 {
192 jCC* jcc;
193 UInt idx;
194
195 CLG_DEBUG(5, "+ get_jcc(bbcc %p/%d => bbcc %p)\n",
196 from, jmp, to);
197
198 /* first check last recently used JCC */
199 jcc = to->lru_to_jcc;
200 if (jcc && (jcc->from == from) && (jcc->jmp == jmp)) {
201 CLG_ASSERT(to == jcc->to);
202 CLG_DEBUG(5,"- get_jcc: [LRU to] jcc %p\n", jcc);
203 return jcc;
204 }
205
206 jcc = from->lru_from_jcc;
207 if (jcc && (jcc->to == to) && (jcc->jmp == jmp)) {
208 CLG_ASSERT(from == jcc->from);
209 CLG_DEBUG(5, "- get_jcc: [LRU from] jcc %p\n", jcc);
210 return jcc;
211 }
212
213 CLG_(stat).jcc_lru_misses++;
214
215 idx = jcc_hash_idx(from, jmp, to, current_jccs.size);
216 jcc = current_jccs.table[idx];
217
218 while(jcc) {
219 if ((jcc->from == from) &&
220 (jcc->jmp == jmp) &&
221 (jcc->to == to)) break;
222 jcc = jcc->next_hash;
223 }
224
225 if (!jcc)
226 jcc = new_jcc(from, jmp, to);
227
228 /* set LRU */
229 from->lru_from_jcc = jcc;
230 to->lru_to_jcc = jcc;
231
232 CLG_DEBUG(5, "- get_jcc(bbcc %p => bbcc %p)\n",
233 from, to);
234
235 return jcc;
236 }
237
238