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 (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 /*------------------------------------------------------------*/ 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 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 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 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__ 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 */ 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 */ 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) */ 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
