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-2017, 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 /*------------------------------------------------------------*/
32 /*--- Jump Cost Center (JCC) operations, including Calls ---*/
33 /*------------------------------------------------------------*/
34
35 #define N_JCC_INITIAL_ENTRIES 4437
36
37 static jcc_hash current_jccs;
38
CLG_(init_jcc_hash)39 void CLG_(init_jcc_hash)(jcc_hash* jccs)
40 {
41 Int i;
42
43 CLG_ASSERT(jccs != 0);
44
45 jccs->size = N_JCC_INITIAL_ENTRIES;
46 jccs->entries = 0;
47 jccs->table = (jCC**) CLG_MALLOC("cl.jumps.ijh.1",
48 jccs->size * sizeof(jCC*));
49 jccs->spontaneous = 0;
50
51 for (i = 0; i < jccs->size; i++)
52 jccs->table[i] = 0;
53 }
54
55
CLG_(copy_current_jcc_hash)56 void CLG_(copy_current_jcc_hash)(jcc_hash* dst)
57 {
58 CLG_ASSERT(dst != 0);
59
60 dst->size = current_jccs.size;
61 dst->entries = current_jccs.entries;
62 dst->table = current_jccs.table;
63 dst->spontaneous = current_jccs.spontaneous;
64 }
65
CLG_(set_current_jcc_hash)66 void CLG_(set_current_jcc_hash)(jcc_hash* h)
67 {
68 CLG_ASSERT(h != 0);
69
70 current_jccs.size = h->size;
71 current_jccs.entries = h->entries;
72 current_jccs.table = h->table;
73 current_jccs.spontaneous = h->spontaneous;
74 }
75
76 __inline__
jcc_hash_idx(BBCC * from,UInt jmp,BBCC * to,UInt size)77 static UInt jcc_hash_idx(BBCC* from, UInt jmp, BBCC* to, UInt size)
78 {
79 return (UInt) ( (UWord)from + 7* (UWord)to + 13*jmp) % size;
80 }
81
82 /* double size of jcc table */
resize_jcc_table(void)83 static void resize_jcc_table(void)
84 {
85 Int i, new_size, conflicts1 = 0, conflicts2 = 0;
86 jCC** new_table;
87 UInt new_idx;
88 jCC *curr_jcc, *next_jcc;
89
90 new_size = 2* current_jccs.size +3;
91 new_table = (jCC**) CLG_MALLOC("cl.jumps.rjt.1",
92 new_size * sizeof(jCC*));
93
94 for (i = 0; i < new_size; i++)
95 new_table[i] = NULL;
96
97 for (i = 0; i < current_jccs.size; i++) {
98 if (current_jccs.table[i] == NULL) continue;
99
100 curr_jcc = current_jccs.table[i];
101 while (NULL != curr_jcc) {
102 next_jcc = curr_jcc->next_hash;
103
104 new_idx = jcc_hash_idx(curr_jcc->from, curr_jcc->jmp,
105 curr_jcc->to, new_size);
106
107 curr_jcc->next_hash = new_table[new_idx];
108 new_table[new_idx] = curr_jcc;
109 if (curr_jcc->next_hash) {
110 conflicts1++;
111 if (curr_jcc->next_hash->next_hash)
112 conflicts2++;
113 }
114
115 curr_jcc = next_jcc;
116 }
117 }
118
119 VG_(free)(current_jccs.table);
120
121
122 CLG_DEBUG(0, "Resize JCC Hash: %u => %d (entries %u, conflicts %d/%d)\n",
123 current_jccs.size, new_size,
124 current_jccs.entries, conflicts1, conflicts2);
125
126 current_jccs.size = new_size;
127 current_jccs.table = new_table;
128 CLG_(stat).jcc_hash_resizes++;
129 }
130
131
132
133 /* new jCC structure: a call was done to a BB of a BBCC
134 * for a spontaneous call, from is 0 (i.e. caller unknown)
135 */
new_jcc(BBCC * from,UInt jmp,BBCC * to)136 static jCC* new_jcc(BBCC* from, UInt jmp, BBCC* to)
137 {
138 jCC* jcc;
139 UInt new_idx;
140
141 /* check fill degree of jcc hash table and resize if needed (>80%) */
142 current_jccs.entries++;
143 if (10 * current_jccs.entries / current_jccs.size > 8)
144 resize_jcc_table();
145
146 jcc = (jCC*) CLG_MALLOC("cl.jumps.nj.1", sizeof(jCC));
147
148 jcc->from = from;
149 jcc->jmp = jmp;
150 jcc->to = to;
151 jcc->jmpkind = jk_Call;
152 jcc->call_counter = 0;
153 jcc->cost = 0;
154
155 /* insert into JCC chain of calling BBCC.
156 * This list is only used at dumping time */
157
158 if (from) {
159 /* Prohibit corruption by array overrun */
160 CLG_ASSERT((0 <= jmp) && (jmp <= from->bb->cjmp_count));
161 jcc->next_from = from->jmp[jmp].jcc_list;
162 from->jmp[jmp].jcc_list = jcc;
163 }
164 else {
165 jcc->next_from = current_jccs.spontaneous;
166 current_jccs.spontaneous = jcc;
167 }
168
169 /* insert into JCC hash table */
170 new_idx = jcc_hash_idx(from, jmp, to, current_jccs.size);
171 jcc->next_hash = current_jccs.table[new_idx];
172 current_jccs.table[new_idx] = jcc;
173
174 CLG_(stat).distinct_jccs++;
175
176 CLG_DEBUGIF(3) {
177 VG_(printf)(" new_jcc (now %d): %p\n",
178 CLG_(stat).distinct_jccs, jcc);
179 }
180
181 return jcc;
182 }
183
184
185 /* get the jCC for a call arc (BBCC->BBCC) */
CLG_(get_jcc)186 jCC* CLG_(get_jcc)(BBCC* from, UInt jmp, BBCC* to)
187 {
188 jCC* jcc;
189 UInt idx;
190
191 CLG_DEBUG(5, "+ get_jcc(bbcc %p/%u => bbcc %p)\n",
192 from, jmp, to);
193
194 /* first check last recently used JCC */
195 jcc = to->lru_to_jcc;
196 if (jcc && (jcc->from == from) && (jcc->jmp == jmp)) {
197 CLG_ASSERT(to == jcc->to);
198 CLG_DEBUG(5,"- get_jcc: [LRU to] jcc %p\n", jcc);
199 return jcc;
200 }
201
202 jcc = from->lru_from_jcc;
203 if (jcc && (jcc->to == to) && (jcc->jmp == jmp)) {
204 CLG_ASSERT(from == jcc->from);
205 CLG_DEBUG(5, "- get_jcc: [LRU from] jcc %p\n", jcc);
206 return jcc;
207 }
208
209 CLG_(stat).jcc_lru_misses++;
210
211 idx = jcc_hash_idx(from, jmp, to, current_jccs.size);
212 jcc = current_jccs.table[idx];
213
214 while(jcc) {
215 if ((jcc->from == from) &&
216 (jcc->jmp == jmp) &&
217 (jcc->to == to)) break;
218 jcc = jcc->next_hash;
219 }
220
221 if (!jcc)
222 jcc = new_jcc(from, jmp, to);
223
224 /* set LRU */
225 from->lru_from_jcc = jcc;
226 to->lru_to_jcc = jcc;
227
228 CLG_DEBUG(5, "- get_jcc(bbcc %p => bbcc %p)\n",
229 from, to);
230
231 return jcc;
232 }
233
234