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-2012, Josef Weidendorfer (Josef.Weidendorfer (at) 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 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 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 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__ 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 */ 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 */ 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 = 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) */ 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
