weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 1 | /*--------------------------------------------------------------------*/ |
| 2 | /*--- Callgrind ---*/ |
| 3 | /*--- bb.c ---*/ |
| 4 | /*--------------------------------------------------------------------*/ |
| 5 | |
| 6 | /* |
| 7 | This file is part of Callgrind, a Valgrind tool for call tracing. |
| 8 | |
sewardj | 4d474d0 | 2008-02-11 11:34:59 +0000 | [diff] [blame] | 9 | Copyright (C) 2002-2008, Josef Weidendorfer (Josef.Weidendorfer@gmx.de) |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 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 | /*--- Basic block (BB) operations ---*/ |
| 33 | /*------------------------------------------------------------*/ |
| 34 | |
| 35 | /* BB hash, resizable */ |
| 36 | bb_hash bbs; |
| 37 | |
| 38 | void CLG_(init_bb_hash)() |
| 39 | { |
| 40 | Int i; |
| 41 | |
| 42 | bbs.size = 8437; |
| 43 | bbs.entries = 0; |
| 44 | bbs.table = (BB**) CLG_MALLOC(bbs.size * sizeof(BB*)); |
| 45 | |
| 46 | for (i = 0; i < bbs.size; i++) bbs.table[i] = NULL; |
| 47 | } |
| 48 | |
| 49 | bb_hash* CLG_(get_bb_hash)() |
| 50 | { |
| 51 | return &bbs; |
| 52 | } |
| 53 | |
| 54 | /* The hash stores BBs according to |
| 55 | * - ELF object (is 0 for code in anonymous mapping) |
| 56 | * - BB base as object file offset |
| 57 | */ |
| 58 | static __inline__ |
| 59 | UInt bb_hash_idx(obj_node* obj, OffT offset, UInt size) |
| 60 | { |
| 61 | return (((Addr)obj) + offset) % size; |
| 62 | } |
| 63 | |
| 64 | /* double size of bb table */ |
| 65 | static |
| 66 | void resize_bb_table(void) |
| 67 | { |
| 68 | Int i, new_size, conflicts1 = 0, conflicts2 = 0; |
| 69 | BB **new_table, *curr, *next; |
| 70 | UInt new_idx; |
| 71 | |
| 72 | new_size = 2* bbs.size +3; |
| 73 | new_table = (BB**) CLG_MALLOC(new_size * sizeof(BB*)); |
| 74 | |
| 75 | if (!new_table) return; |
| 76 | |
| 77 | for (i = 0; i < new_size; i++) |
| 78 | new_table[i] = NULL; |
| 79 | |
| 80 | for (i = 0; i < bbs.size; i++) { |
| 81 | if (bbs.table[i] == NULL) continue; |
| 82 | |
| 83 | curr = bbs.table[i]; |
| 84 | while (NULL != curr) { |
| 85 | next = curr->next; |
| 86 | |
| 87 | new_idx = bb_hash_idx(curr->obj, curr->offset, new_size); |
| 88 | |
| 89 | curr->next = new_table[new_idx]; |
| 90 | new_table[new_idx] = curr; |
| 91 | if (curr->next) { |
| 92 | conflicts1++; |
| 93 | if (curr->next->next) |
| 94 | conflicts2++; |
| 95 | } |
| 96 | |
| 97 | curr = next; |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | VG_(free)(bbs.table); |
| 102 | |
| 103 | |
| 104 | CLG_DEBUG(0, "Resize BB Hash: %d => %d (entries %d, conflicts %d/%d)\n", |
| 105 | bbs.size, new_size, |
| 106 | bbs.entries, conflicts1, conflicts2); |
| 107 | |
| 108 | bbs.size = new_size; |
| 109 | bbs.table = new_table; |
| 110 | CLG_(stat).bb_hash_resizes++; |
| 111 | } |
| 112 | |
| 113 | |
| 114 | /** |
| 115 | * Allocate new BB structure (including space for event type list) |
| 116 | * Not initialized: |
| 117 | * - instr_len, cost_count, instr[] |
| 118 | */ |
| 119 | static BB* new_bb(obj_node* obj, OffT offset, |
| 120 | UInt instr_count, UInt cjmp_count, Bool cjmp_inverted) |
| 121 | { |
| 122 | BB* new; |
weidendo | c8e7615 | 2006-05-27 15:30:58 +0000 | [diff] [blame] | 123 | UInt new_idx, size; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 124 | |
| 125 | /* check fill degree of bb hash table and resize if needed (>80%) */ |
| 126 | bbs.entries++; |
| 127 | if (10 * bbs.entries / bbs.size > 8) |
| 128 | resize_bb_table(); |
| 129 | |
weidendo | c8e7615 | 2006-05-27 15:30:58 +0000 | [diff] [blame] | 130 | size = sizeof(BB) + instr_count * sizeof(InstrInfo) |
| 131 | + (cjmp_count+1) * sizeof(CJmpInfo); |
| 132 | new = (BB*) CLG_MALLOC(size); |
| 133 | VG_(memset)(new, 0, size); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 134 | |
| 135 | new->obj = obj; |
| 136 | new->offset = offset; |
| 137 | |
| 138 | new->instr_count = instr_count; |
| 139 | new->cjmp_count = cjmp_count; |
| 140 | new->cjmp_inverted = cjmp_inverted; |
| 141 | new->jmp = (CJmpInfo*) &(new->instr[instr_count]); |
| 142 | new->instr_len = 0; |
| 143 | new->cost_count = 0; |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 144 | new->sect_kind = VG_(seginfo_sect_kind)(NULL, 0, offset + obj->offset); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 145 | new->fn = 0; |
| 146 | new->line = 0; |
| 147 | new->is_entry = 0; |
| 148 | new->bbcc_list = 0; |
| 149 | new->last_bbcc = 0; |
| 150 | |
| 151 | /* insert into BB hash table */ |
| 152 | new_idx = bb_hash_idx(obj, offset, bbs.size); |
| 153 | new->next = bbs.table[new_idx]; |
| 154 | bbs.table[new_idx] = new; |
| 155 | |
| 156 | CLG_(stat).distinct_bbs++; |
| 157 | |
| 158 | #if CLG_ENABLE_DEBUG |
| 159 | CLG_DEBUGIF(3) { |
| 160 | VG_(printf)(" new_bb (instr %d, jmps %d, inv %s) [now %d]: ", |
| 161 | instr_count, cjmp_count, |
| 162 | cjmp_inverted ? "yes":"no", |
| 163 | CLG_(stat).distinct_bbs); |
| 164 | CLG_(print_bb)(0, new); |
| 165 | VG_(printf)("\n"); |
| 166 | } |
| 167 | #endif |
| 168 | |
| 169 | CLG_(get_fn_node)(new); |
| 170 | |
| 171 | return new; |
| 172 | } |
| 173 | |
| 174 | |
| 175 | /* get the BB structure for a BB start address */ |
| 176 | static __inline__ |
| 177 | BB* lookup_bb(obj_node* obj, OffT offset) |
| 178 | { |
| 179 | BB* bb; |
| 180 | Int idx; |
| 181 | |
| 182 | idx = bb_hash_idx(obj, offset, bbs.size); |
| 183 | bb = bbs.table[idx]; |
| 184 | |
| 185 | while(bb) { |
| 186 | if ((bb->obj == obj) && (bb->offset == offset)) break; |
| 187 | bb = bb->next; |
| 188 | } |
| 189 | |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 190 | CLG_DEBUG(5, " lookup_bb (Obj %s, off %#lx): %p\n", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 191 | obj->name, offset, bb); |
| 192 | return bb; |
| 193 | } |
| 194 | |
| 195 | static __inline__ |
| 196 | obj_node* obj_of_address(Addr addr) |
| 197 | { |
| 198 | obj_node* obj; |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 199 | DebugInfo* di; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 200 | OffT offset; |
| 201 | |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 202 | di = VG_(find_seginfo)(addr); |
| 203 | obj = CLG_(get_obj_node)( di ); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 204 | |
| 205 | /* Update symbol offset in object if remapped */ |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 206 | /* FIXME (or at least check this) 2008 Feb 19: 'offset' is |
| 207 | only correct for text symbols, not for data symbols */ |
| 208 | offset = di ? VG_(seginfo_get_text_bias)(di):0; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 209 | if (obj->offset != offset) { |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 210 | Addr start = di ? VG_(seginfo_get_text_avma)(di) : 0; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 211 | |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 212 | CLG_DEBUG(0, "Mapping changed for '%s': %#lx -> %#lx\n", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 213 | obj->name, obj->start, start); |
| 214 | |
| 215 | /* Size should be the same, and offset diff == start diff */ |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 216 | CLG_ASSERT( obj->size == (di ? VG_(seginfo_get_text_size)(di) : 0) ); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 217 | CLG_ASSERT( obj->start - start == obj->offset - offset ); |
| 218 | obj->offset = offset; |
| 219 | obj->start = start; |
| 220 | } |
| 221 | |
| 222 | return obj; |
| 223 | } |
| 224 | |
| 225 | /* Get the BB structure for a BB start address. |
| 226 | * If the BB has to be created, the IRBB is needed to |
| 227 | * compute the event type list for costs, and seen_before is |
| 228 | * set to False. Otherwise, seen_before is set to True. |
| 229 | * |
| 230 | * BBs are never discarded. There are 2 cases where this function |
| 231 | * is called from CLG_(instrument)() and a BB already exists: |
| 232 | * - The instrumented version was removed from Valgrinds TT cache |
| 233 | * - The ELF object of the BB was unmapped and mapped again. |
| 234 | * This involves a possibly different address, but is handled by |
| 235 | * looking up a BB keyed by (obj_node, file offset). |
| 236 | * |
| 237 | * bbIn==0 is possible for artifical BB without real code. |
| 238 | * Such a BB is created when returning to an unknown function. |
| 239 | */ |
sewardj | 0b9d74a | 2006-12-24 02:24:11 +0000 | [diff] [blame] | 240 | BB* CLG_(get_bb)(Addr addr, IRSB* bbIn, /*OUT*/ Bool *seen_before) |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 241 | { |
| 242 | BB* bb; |
| 243 | obj_node* obj; |
| 244 | UInt n_instrs, n_jmps; |
| 245 | Bool cjmp_inverted = False; |
| 246 | |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 247 | CLG_DEBUG(5, "+ get_bb(BB %#lx)\n", addr); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 248 | |
| 249 | obj = obj_of_address(addr); |
| 250 | bb = lookup_bb(obj, addr - obj->offset); |
| 251 | |
| 252 | n_instrs = 0; |
| 253 | n_jmps = 0; |
| 254 | CLG_(collectBlockInfo)(bbIn, &n_instrs, &n_jmps, &cjmp_inverted); |
| 255 | |
| 256 | *seen_before = bb ? True : False; |
| 257 | if (*seen_before) { |
| 258 | if (bb->instr_count != n_instrs) { |
| 259 | VG_(message)(Vg_DebugMsg, |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 260 | "ERROR: BB Retranslation Mismatch at BB %#lx", addr); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 261 | VG_(message)(Vg_DebugMsg, |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 262 | " new: Obj %s, Off %#lx, BBOff %#lx, Instrs %u", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 263 | obj->name, obj->offset, |
| 264 | addr - obj->offset, n_instrs); |
| 265 | VG_(message)(Vg_DebugMsg, |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 266 | " old: Obj %s, Off %#lx, BBOff %#lx, Instrs %u", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 267 | bb->obj->name, bb->obj->offset, |
| 268 | bb->offset, bb->instr_count); |
| 269 | CLG_ASSERT(bb->instr_count == n_instrs ); |
| 270 | } |
| 271 | CLG_ASSERT(bb->cjmp_count == n_jmps ); |
| 272 | CLG_(stat).bb_retranslations++; |
| 273 | |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 274 | CLG_DEBUG(5, "- get_bb(BB %#lx): seen before.\n", addr); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 275 | return bb; |
| 276 | } |
| 277 | |
| 278 | bb = new_bb(obj, addr - obj->offset, n_instrs, n_jmps, cjmp_inverted); |
| 279 | |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 280 | CLG_DEBUG(5, "- get_bb(BB %#lx)\n", addr); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 281 | |
| 282 | return bb; |
| 283 | } |
| 284 | |
| 285 | /* Delete the BB info for the bb with unredirected entry-point |
| 286 | address 'addr'. */ |
| 287 | void CLG_(delete_bb)(Addr addr) |
| 288 | { |
| 289 | BB *bb, *bp; |
| 290 | Int idx, size; |
| 291 | |
| 292 | obj_node* obj = obj_of_address(addr); |
| 293 | OffT offset = addr - obj->offset; |
| 294 | |
| 295 | idx = bb_hash_idx(obj, offset, bbs.size); |
| 296 | bb = bbs.table[idx]; |
| 297 | |
| 298 | /* bb points at the current bb under consideration, and bp is the |
| 299 | one before. */ |
| 300 | bp = NULL; |
| 301 | while(bb) { |
| 302 | if ((bb->obj == obj) && (bb->offset == offset)) break; |
| 303 | bp = bb; |
| 304 | bb = bb->next; |
| 305 | } |
| 306 | |
| 307 | if (bb == NULL) { |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 308 | CLG_DEBUG(3, " delete_bb (Obj %s, off %#lx): NOT FOUND\n", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 309 | obj->name, offset); |
| 310 | |
weidendo | f3e0b49 | 2006-09-10 22:34:20 +0000 | [diff] [blame] | 311 | /* we didn't find it. |
| 312 | * this happens when callgrinds instrumentation mode |
| 313 | * was off at BB translation time, ie. no BB was created. |
| 314 | */ |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 315 | return; |
| 316 | } |
| 317 | |
| 318 | /* unlink it from hash table */ |
| 319 | |
| 320 | if (bp == NULL) { |
| 321 | /* we found the first one in the list. */ |
| 322 | tl_assert(bb == bbs.table[idx]); |
| 323 | bbs.table[idx] = bb->next; |
| 324 | } else { |
| 325 | tl_assert(bb != bbs.table[idx]); |
| 326 | bp->next = bb->next; |
| 327 | } |
| 328 | |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 329 | CLG_DEBUG(3, " delete_bb (Obj %s, off %#lx): %p, BBCC head: %p\n", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 330 | obj->name, offset, bb, bb->bbcc_list); |
| 331 | |
| 332 | if (bb->bbcc_list == 0) { |
| 333 | /* can be safely deleted */ |
| 334 | |
| 335 | /* Fill the block up with junk and then free it, so we will |
| 336 | hopefully get a segfault if it is used again by mistake. */ |
| 337 | size = sizeof(BB) |
| 338 | + bb->instr_count * sizeof(InstrInfo) |
| 339 | + (bb->cjmp_count+1) * sizeof(CJmpInfo); |
| 340 | VG_(memset)( bb, 0xAA, size ); |
| 341 | CLG_FREE(bb); |
weidendo | f3e0b49 | 2006-09-10 22:34:20 +0000 | [diff] [blame] | 342 | return; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 343 | } |
| 344 | CLG_DEBUG(3, " delete_bb: BB in use, can not free!\n"); |
| 345 | } |