blob: 0616c67daaa61d08d406f7894609534a73f80cbb [file] [log] [blame]
weidendoa17f2a32006-03-20 10:27:30 +00001/*--------------------------------------------------------------------*/
2/*--- Callgrind ---*/
3/*--- ct_context.c ---*/
4/*--------------------------------------------------------------------*/
5
6/*
7 This file is part of Callgrind, a Valgrind tool for call tracing.
8
sewardj4d474d02008-02-11 11:34:59 +00009 Copyright (C) 2002-2008, Josef Weidendorfer (Josef.Weidendorfer@gmx.de)
weidendoa17f2a32006-03-20 10:27:30 +000010
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/*------------------------------------------------------------*/
33/*--- Context operations ---*/
34/*------------------------------------------------------------*/
35
36#define N_FNSTACK_INITIAL_ENTRIES 500
37#define N_CXT_INITIAL_ENTRIES 2537
38
39fn_stack CLG_(current_fn_stack);
40
41void CLG_(init_fn_stack)(fn_stack* s)
42{
43 CLG_ASSERT(s != 0);
44
45 s->size = N_FNSTACK_INITIAL_ENTRIES;
sewardj9c606bd2008-09-18 18:12:50 +000046 s->bottom = (fn_node**) CLG_MALLOC("cl.context.ifs.1",
47 s->size * sizeof(fn_node*));
weidendoa17f2a32006-03-20 10:27:30 +000048 s->top = s->bottom;
49 s->bottom[0] = 0;
50}
51
52void CLG_(copy_current_fn_stack)(fn_stack* dst)
53{
54 CLG_ASSERT(dst != 0);
55
56 dst->size = CLG_(current_fn_stack).size;
57 dst->bottom = CLG_(current_fn_stack).bottom;
58 dst->top = CLG_(current_fn_stack).top;
59}
60
61void CLG_(set_current_fn_stack)(fn_stack* s)
62{
63 CLG_ASSERT(s != 0);
64
65 CLG_(current_fn_stack).size = s->size;
66 CLG_(current_fn_stack).bottom = s->bottom;
67 CLG_(current_fn_stack).top = s->top;
68}
69
70static cxt_hash cxts;
71
72void CLG_(init_cxt_table)()
73{
74 Int i;
75
76 cxts.size = N_CXT_INITIAL_ENTRIES;
77 cxts.entries = 0;
sewardj9c606bd2008-09-18 18:12:50 +000078 cxts.table = (Context**) CLG_MALLOC("cl.context.ict.1",
79 cxts.size * sizeof(Context*));
weidendoa17f2a32006-03-20 10:27:30 +000080
81 for (i = 0; i < cxts.size; i++)
82 cxts.table[i] = 0;
83}
84
85cxt_hash* CLG_(get_cxt_hash)()
86{
87 return &cxts;
88}
89
90/* double size of cxt table */
91static void resize_cxt_table(void)
92{
93 UInt i, new_size, conflicts1 = 0, conflicts2 = 0;
94 Context **new_table, *curr, *next;
95 UInt new_idx;
96
97 new_size = 2* cxts.size +3;
sewardj9c606bd2008-09-18 18:12:50 +000098 new_table = (Context**) CLG_MALLOC("cl.context.rct.1",
99 new_size * sizeof(Context*));
weidendoa17f2a32006-03-20 10:27:30 +0000100
101 if (!new_table) return;
102
103 for (i = 0; i < new_size; i++)
104 new_table[i] = NULL;
105
106 for (i = 0; i < cxts.size; i++) {
107 if (cxts.table[i] == NULL) continue;
108
109 curr = cxts.table[i];
110 while (NULL != curr) {
111 next = curr->next;
112
113 new_idx = (UInt) (curr->hash % new_size);
114
115 curr->next = new_table[new_idx];
116 new_table[new_idx] = curr;
117 if (curr->next) {
118 conflicts1++;
119 if (curr->next->next)
120 conflicts2++;
121 }
122
123 curr = next;
124 }
125 }
126
127 VG_(free)(cxts.table);
128
129
130 CLG_DEBUG(0, "Resize Context Hash: %d => %d (entries %d, conflicts %d/%d)\n",
131 cxts.size, new_size,
132 cxts.entries, conflicts1, conflicts2);
133
134 cxts.size = new_size;
135 cxts.table = new_table;
136 CLG_(stat).cxt_hash_resizes++;
137}
138
139__inline__
140static UWord cxt_hash_val(fn_node** fn, UInt size)
141{
142 UWord hash = 0;
143 UInt count = size;
144 while(*fn != 0) {
145 hash = (hash<<7) + (hash>>25) + (UWord)(*fn);
146 fn--;
147 count--;
148 if (count==0) break;
149 }
150 return hash;
151}
152
153__inline__
154static Bool is_cxt(UWord hash, fn_node** fn, Context* cxt)
155{
156 int count;
157 fn_node** cxt_fn;
158
159 if (hash != cxt->hash) return False;
160
161 count = cxt->size;
162 cxt_fn = &(cxt->fn[0]);
163 while((*fn != 0) && (count>0)) {
164 if (*cxt_fn != *fn) return False;
165 fn--;
166 cxt_fn++;
167 count--;
168 }
169 return True;
170}
171
172/**
173 * Allocate new Context structure
174 */
175static Context* new_cxt(fn_node** fn)
176{
177 Context* new;
178 UInt idx, offset;
179 UWord hash;
180 int size, recs;
181 fn_node* top_fn;
182
183 CLG_ASSERT(fn);
184 top_fn = *fn;
185 if (top_fn == 0) return 0;
186
187 size = top_fn->separate_callers +1;
188 recs = top_fn->separate_recursions;
189 if (recs<1) recs=1;
190
191 /* check fill degree of context hash table and resize if needed (>80%) */
192 cxts.entries++;
193 if (10 * cxts.entries / cxts.size > 8)
194 resize_cxt_table();
195
sewardj9c606bd2008-09-18 18:12:50 +0000196 new = (Context*) CLG_MALLOC("cl.context.nc.1",
197 sizeof(Context)+sizeof(fn_node*)*size);
weidendoa17f2a32006-03-20 10:27:30 +0000198
199 // hash value calculation similar to cxt_hash_val(), but additionally
200 // copying function pointers in one run
201 hash = 0;
202 offset = 0;
203 while(*fn != 0) {
204 hash = (hash<<7) + (hash>>25) + (UWord)(*fn);
205 new->fn[offset] = *fn;
206 offset++;
207 fn--;
208 if (offset >= size) break;
209 }
210 if (offset < size) size = offset;
211
212 new->size = size;
213 new->base_number = CLG_(stat).context_counter;
214 new->hash = hash;
215
216 CLG_(stat).context_counter += recs;
217 CLG_(stat).distinct_contexts++;
218
219 /* insert into Context hash table */
220 idx = (UInt) (hash % cxts.size);
221 new->next = cxts.table[idx];
222 cxts.table[idx] = new;
223
224#if CLG_ENABLE_DEBUG
225 CLG_DEBUGIF(3) {
226 VG_(printf)(" new_cxt ox%p: ", new);
227 CLG_(print_cxt)(12, new, 0);
228 }
229#endif
230
231 return new;
232}
233
234/* get the Context structure for current context */
235Context* CLG_(get_cxt)(fn_node** fn)
236{
237 Context* cxt;
238 UInt size, idx;
239 UWord hash;
240
241 CLG_ASSERT(fn != 0);
242 if (*fn == 0) return 0;
243 size = (*fn)->separate_callers+1;
244 if (size<=0) { size = -size+1; }
245
246 CLG_DEBUG(5, "+ get_cxt(fn '%s'): size %d\n",
247 (*fn)->name, size);
248
249 hash = cxt_hash_val(fn, size);
250
251 if ( ((cxt = (*fn)->last_cxt) != 0) && is_cxt(hash, fn, cxt)) {
252 CLG_DEBUG(5, "- get_cxt: %p\n", cxt);
253 return cxt;
254 }
255
256 CLG_(stat).cxt_lru_misses++;
257
258 idx = (UInt) (hash % cxts.size);
259 cxt = cxts.table[idx];
260
261 while(cxt) {
262 if (is_cxt(hash,fn,cxt)) break;
263 cxt = cxt->next;
264 }
265
266 if (!cxt)
267 cxt = new_cxt(fn);
268
269 (*fn)->last_cxt = cxt;
270
271 CLG_DEBUG(5, "- get_cxt: %p\n", cxt);
272
273 return cxt;
274}
275
276
277/**
278 * Change execution context by calling a new function from current context
279 *
280 */
281void CLG_(push_cxt)(fn_node* fn)
282{
283 call_stack* cs = &CLG_(current_call_stack);
284 Int fn_entries;
285
weidendof3e0b492006-09-10 22:34:20 +0000286 CLG_DEBUG(5, "+ push_cxt(fn '%s'): old ctx %d\n",
287 fn ? fn->name : (Char*)"0x0",
288 CLG_(current_state).cxt ?
289 CLG_(current_state).cxt->base_number : -1);
290
weidendoa17f2a32006-03-20 10:27:30 +0000291 /* save old context on stack (even if not changed at all!) */
292 CLG_ASSERT(cs->sp < cs->size);
293 CLG_ASSERT(cs->entry[cs->sp].cxt == 0);
294 cs->entry[cs->sp].cxt = CLG_(current_state).cxt;
295 cs->entry[cs->sp].fn_sp = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom;
296
297 if (*(CLG_(current_fn_stack).top) == fn) return;
298 if (fn && (fn->group>0) &&
299 ((*(CLG_(current_fn_stack).top))->group == fn->group)) return;
300
301 /* resizing needed ? */
302 fn_entries = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom;
303 if (fn_entries == CLG_(current_fn_stack).size-1) {
304 int new_size = CLG_(current_fn_stack).size *2;
sewardj9c606bd2008-09-18 18:12:50 +0000305 fn_node** new = (fn_node**) CLG_MALLOC("cl.context.pc.1",
306 new_size * sizeof(fn_node*));
weidendoa17f2a32006-03-20 10:27:30 +0000307 int i;
308 for(i=0;i<CLG_(current_fn_stack).size;i++)
309 new[i] = CLG_(current_fn_stack).bottom[i];
310 VG_(free)(CLG_(current_fn_stack).bottom);
311 CLG_(current_fn_stack).top = new + fn_entries;
312 CLG_(current_fn_stack).bottom = new;
313
314 CLG_DEBUG(0, "Resize Context Stack: %d => %d (pushing '%s')\n",
315 CLG_(current_fn_stack).size, new_size,
316 fn ? fn->name : (Char*)"0x0");
317
318 CLG_(current_fn_stack).size = new_size;
319 }
320
321 if (*(CLG_(current_fn_stack).top) == 0) {
322 UInt *pactive;
323
324 /* this is first function: increment its active count */
325 CLG_ASSERT(fn != 0);
326 pactive = CLG_(get_fn_entry)(fn->number);
327 (*pactive)++;
328 }
329
330 CLG_(current_fn_stack).top++;
331 *(CLG_(current_fn_stack).top) = fn;
332 CLG_(current_state).cxt = CLG_(get_cxt)(CLG_(current_fn_stack).top);
333
barta0b6b2c2008-07-07 06:49:24 +0000334 CLG_DEBUG(5, "- push_cxt(fn '%s'): new cxt %d, fn_sp %ld\n",
weidendof3e0b492006-09-10 22:34:20 +0000335 fn ? fn->name : (Char*)"0x0",
336 CLG_(current_state).cxt ?
337 CLG_(current_state).cxt->base_number : -1,
barta0b6b2c2008-07-07 06:49:24 +0000338 CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom + 0L);
weidendoa17f2a32006-03-20 10:27:30 +0000339}
340