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
37static jcc_hash current_jccs;
38
39void 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
56void 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
66void 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__
77static 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  */
83static 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 */
136static 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) */
186jCC* 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