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-2013, 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
39jcc_hash current_jccs;
40
41void 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
58void 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
68void 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__
79static 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  */
85static 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 */
140static 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   = jk_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) */
190jCC* 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