weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 1 | /*--------------------------------------------------------------------*/ |
| 2 | /*--- Callgrind ---*/ |
| 3 | /*--- ct_callstack.c ---*/ |
| 4 | /*--------------------------------------------------------------------*/ |
| 5 | |
| 6 | /* |
| 7 | This file is part of Callgrind, a Valgrind tool for call tracing. |
| 8 | |
sewardj | 4505790 | 2006-06-05 23:27:18 +0000 | [diff] [blame] | 9 | Copyright (C) 2002-2006, 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 | /*--- Call stack, operations ---*/ |
| 33 | /*------------------------------------------------------------*/ |
| 34 | |
| 35 | /* Stack of current thread. Gets initialized when switching to 1st thread. |
| 36 | * |
| 37 | * The artificial call stack is an array of call_entry's, representing |
| 38 | * stack frames of the executing program. |
| 39 | * Array call_stack and call_stack_esp have same size and grow on demand. |
| 40 | * Array call_stack_esp holds SPs of corresponding stack frames. |
| 41 | * |
| 42 | */ |
| 43 | |
| 44 | #define N_CALL_STACK_INITIAL_ENTRIES 500 |
| 45 | |
| 46 | call_stack CLG_(current_call_stack); |
| 47 | |
| 48 | void CLG_(init_call_stack)(call_stack* s) |
| 49 | { |
| 50 | Int i; |
| 51 | |
| 52 | CLG_ASSERT(s != 0); |
| 53 | |
| 54 | s->size = N_CALL_STACK_INITIAL_ENTRIES; |
| 55 | s->entry = (call_entry*) CLG_MALLOC(s->size * sizeof(call_entry)); |
| 56 | s->sp = 0; |
| 57 | s->entry[0].cxt = 0; /* for assertion in push_cxt() */ |
| 58 | |
| 59 | for(i=0; i<s->size; i++) s->entry[i].enter_cost = 0; |
| 60 | } |
| 61 | |
| 62 | call_entry* CLG_(get_call_entry)(Int sp) |
| 63 | { |
| 64 | CLG_ASSERT(sp <= CLG_(current_call_stack).sp); |
| 65 | return &(CLG_(current_call_stack).entry[sp]); |
| 66 | } |
| 67 | |
| 68 | void CLG_(copy_current_call_stack)(call_stack* dst) |
| 69 | { |
| 70 | CLG_ASSERT(dst != 0); |
| 71 | |
| 72 | dst->size = CLG_(current_call_stack).size; |
| 73 | dst->entry = CLG_(current_call_stack).entry; |
| 74 | dst->sp = CLG_(current_call_stack).sp; |
| 75 | } |
| 76 | |
| 77 | void CLG_(set_current_call_stack)(call_stack* s) |
| 78 | { |
| 79 | CLG_ASSERT(s != 0); |
| 80 | |
| 81 | CLG_(current_call_stack).size = s->size; |
| 82 | CLG_(current_call_stack).entry = s->entry; |
| 83 | CLG_(current_call_stack).sp = s->sp; |
| 84 | } |
| 85 | |
| 86 | |
| 87 | static __inline__ |
| 88 | void ensure_stack_size(Int i) |
| 89 | { |
| 90 | Int oldsize; |
| 91 | call_stack *cs = &CLG_(current_call_stack); |
| 92 | |
| 93 | if (i < cs->size) return; |
| 94 | |
| 95 | oldsize = cs->size; |
| 96 | cs->size *= 2; |
| 97 | while (i > cs->size) cs->size *= 2; |
| 98 | |
| 99 | cs->entry = (call_entry*) VG_(realloc)(cs->entry, |
| 100 | cs->size * sizeof(call_entry)); |
| 101 | |
| 102 | for(i=oldsize; i<cs->size; i++) |
| 103 | cs->entry[i].enter_cost = 0; |
| 104 | |
| 105 | CLG_(stat).call_stack_resizes++; |
| 106 | |
| 107 | CLG_DEBUGIF(2) |
| 108 | VG_(printf)(" call stack enlarged to %d entries\n", |
| 109 | CLG_(current_call_stack).size); |
| 110 | } |
| 111 | |
| 112 | |
| 113 | |
| 114 | /* Called when function entered nonrecursive */ |
| 115 | static void function_entered(fn_node* fn, BBCC* to) |
| 116 | { |
| 117 | CLG_ASSERT(fn != 0); |
| 118 | |
| 119 | #if CLG_ENABLE_DEBUG |
| 120 | if (fn->verbosity >=0) { |
| 121 | Int old = CLG_(clo).verbose; |
| 122 | CLG_(clo).verbose = fn->verbosity; |
| 123 | fn->verbosity = old; |
| 124 | VG_(message)(Vg_DebugMsg, |
| 125 | "Entering %s: Verbosity set to %d", |
| 126 | fn->name, CLG_(clo).verbose); |
| 127 | } |
| 128 | #endif |
| 129 | |
| 130 | if (fn->dump_before) { |
| 131 | Char trigger[FN_NAME_LEN]; |
| 132 | VG_(sprintf)(trigger, "--dump-before=%s", fn->name); |
| 133 | CLG_(dump_profile)(trigger, True); |
| 134 | } |
| 135 | else if (fn->zero_before) { |
| 136 | CLG_(zero_all_cost)(True); |
| 137 | } |
| 138 | |
| 139 | if (fn->toggle_collect) { |
| 140 | CLG_(current_state).collect = !CLG_(current_state).collect; |
| 141 | CLG_DEBUG(2," entering %s: toggled collection state to %s\n", |
| 142 | fn->name, |
| 143 | CLG_(current_state).collect ? "ON" : "OFF"); |
| 144 | } |
| 145 | } |
| 146 | |
| 147 | /* Called when function left (no recursive level active) */ |
| 148 | static void function_left(fn_node* fn, BBCC* from) |
| 149 | { |
| 150 | CLG_ASSERT(fn != 0); |
| 151 | |
| 152 | if (fn->dump_after) { |
| 153 | Char trigger[FN_NAME_LEN]; |
| 154 | VG_(sprintf)(trigger, "--dump-after=%s", fn->name); |
| 155 | CLG_(dump_profile)(trigger, True); |
| 156 | } |
| 157 | if (fn->toggle_collect) { |
| 158 | CLG_(current_state).collect = !CLG_(current_state).collect; |
| 159 | CLG_DEBUG(2," leaving %s: toggled collection state to %s\n", |
| 160 | fn->name, |
| 161 | CLG_(current_state).collect ? "ON" : "OFF"); |
| 162 | } |
| 163 | |
| 164 | #if CLG_ENABLE_DEBUG |
| 165 | if (fn->verbosity >=0) { |
| 166 | Int old = CLG_(clo).verbose; |
| 167 | CLG_(clo).verbose = fn->verbosity; |
| 168 | fn->verbosity = old; |
| 169 | VG_(message)(Vg_DebugMsg, |
| 170 | "Leaving %s: Verbosity set back to %d", |
| 171 | fn->name, CLG_(clo).verbose); |
| 172 | } |
| 173 | #endif |
| 174 | } |
| 175 | |
| 176 | |
| 177 | /* Push call on call stack. |
| 178 | * |
| 179 | * Increment the usage count for the function called. |
| 180 | * A jump from <from> to <to>, with <sp>. |
| 181 | * If <skip> is true, this is a call to a function to be skipped; |
| 182 | * for this, we set jcc = 0. |
| 183 | */ |
| 184 | void CLG_(push_call_stack)(BBCC* from, UInt jmp, BBCC* to, Addr sp, Bool skip) |
| 185 | { |
| 186 | jCC* jcc; |
| 187 | UInt* pdepth; |
| 188 | call_entry* current_entry; |
| 189 | Addr ret_addr; |
| 190 | |
| 191 | /* Ensure a call stack of size <current_sp>+1. |
| 192 | * The +1 is needed as push_cxt will store the |
| 193 | * context at [current_sp] |
| 194 | */ |
| 195 | ensure_stack_size(CLG_(current_call_stack).sp +1); |
| 196 | current_entry = &(CLG_(current_call_stack).entry[CLG_(current_call_stack).sp]); |
| 197 | |
| 198 | if (skip) { |
| 199 | jcc = 0; |
| 200 | } |
| 201 | else { |
| 202 | fn_node* to_fn = to->cxt->fn[0]; |
| 203 | |
| 204 | if (CLG_(current_state).nonskipped) { |
| 205 | /* this is a jmp from skipped to nonskipped */ |
| 206 | CLG_ASSERT(CLG_(current_state).nonskipped == from); |
| 207 | } |
| 208 | |
| 209 | /* As push_cxt() has to be called before push_call_stack if not |
| 210 | * skipping, the old context should already be saved on the stack */ |
| 211 | CLG_ASSERT(current_entry->cxt != 0); |
| 212 | CLG_(copy_cost_lz)( CLG_(sets).full, &(current_entry->enter_cost), |
| 213 | CLG_(current_state).cost ); |
| 214 | |
| 215 | jcc = CLG_(get_jcc)(from, jmp, to); |
| 216 | CLG_ASSERT(jcc != 0); |
| 217 | |
| 218 | pdepth = CLG_(get_fn_entry)(to_fn->number); |
| 219 | if (CLG_(clo).skip_direct_recursion) { |
| 220 | /* only increment depth if another function is called */ |
| 221 | if (jcc->from->cxt->fn[0] != to_fn) (*pdepth)++; |
| 222 | } |
| 223 | else (*pdepth)++; |
| 224 | |
| 225 | if (*pdepth>1) |
| 226 | CLG_(stat).rec_call_counter++; |
| 227 | |
| 228 | jcc->call_counter++; |
| 229 | CLG_(stat).call_counter++; |
| 230 | |
| 231 | if (*pdepth == 1) function_entered(to_fn, to); |
| 232 | } |
| 233 | |
| 234 | /* return address is only is useful with a real call; |
| 235 | * used to detect RET w/o CALL */ |
| 236 | ret_addr = (from->bb->jmpkind == Ijk_Call) ? |
| 237 | bb_addr(from->bb) + from->bb->instr_len : 0; |
| 238 | |
| 239 | /* put jcc on call stack */ |
| 240 | current_entry->jcc = jcc; |
| 241 | current_entry->sp = sp; |
| 242 | current_entry->ret_addr = ret_addr; |
| 243 | current_entry->nonskipped = CLG_(current_state).nonskipped; |
| 244 | |
| 245 | CLG_(current_call_stack).sp++; |
| 246 | |
| 247 | /* To allow for above assertion we set context of next frame to 0 */ |
| 248 | CLG_ASSERT(CLG_(current_call_stack).sp < CLG_(current_call_stack).size); |
| 249 | current_entry++; |
| 250 | current_entry->cxt = 0; |
| 251 | |
| 252 | if (!skip) |
| 253 | CLG_(current_state).nonskipped = 0; |
| 254 | else if (!CLG_(current_state).nonskipped) { |
| 255 | /* a call from nonskipped to skipped */ |
| 256 | CLG_(current_state).nonskipped = from; |
| 257 | if (!CLG_(current_state).nonskipped->skipped) { |
| 258 | CLG_(init_cost_lz)( CLG_(sets).full, |
| 259 | &CLG_(current_state).nonskipped->skipped); |
| 260 | CLG_(stat).distinct_skips++; |
| 261 | } |
| 262 | } |
| 263 | |
| 264 | #if CLG_ENABLE_DEBUG |
| 265 | CLG_DEBUGIF(0) { |
| 266 | if (CLG_(clo).verbose<2) { |
| 267 | if (jcc && jcc->to && jcc->to->bb) { |
| 268 | char spaces[][41] = { " . . . . . . . . . .", |
| 269 | " . . . . . . . . . . ", |
| 270 | " . . . . . . . . . . ", |
| 271 | ". . . . . . . . . . " }; |
| 272 | |
| 273 | int s = CLG_(current_call_stack).sp; |
| 274 | Int* pars = (Int*) sp; |
| 275 | |
| 276 | BB* bb = jcc->to->bb; |
| 277 | if (s>40) s=40; |
| 278 | VG_(printf)("%s> %s(0x%x, 0x%x, ...) [%s / %p]\n", spaces[s%4]+40-s, bb->fn->name, |
| 279 | pars ? pars[1]:0, |
| 280 | pars ? pars[2]:0, |
| 281 | bb->obj->name + bb->obj->last_slash_pos, |
| 282 | bb->offset); |
| 283 | } |
| 284 | } |
| 285 | else if (CLG_(clo).verbose<4) { |
| 286 | VG_(printf)("+ %2d ", CLG_(current_call_stack).sp); |
| 287 | CLG_(print_short_jcc)(jcc); |
| 288 | VG_(printf)(", SP %p, RA %p\n", sp, ret_addr); |
| 289 | } |
| 290 | else { |
| 291 | VG_(printf)(" Pushed "); |
| 292 | CLG_(print_stackentry)(3, CLG_(current_call_stack).sp-1); |
| 293 | } |
| 294 | } |
| 295 | #endif |
| 296 | |
| 297 | } |
| 298 | |
| 299 | |
| 300 | /* Pop call stack and update inclusive sums. |
| 301 | * Returns modified fcc. |
| 302 | * |
| 303 | * If the JCC becomes inactive, call entries are freed if possible |
| 304 | */ |
| 305 | void CLG_(pop_call_stack)() |
| 306 | { |
| 307 | jCC* jcc; |
| 308 | Int depth = 0; |
| 309 | call_entry* lower_entry; |
| 310 | |
| 311 | if (CLG_(current_state).sig >0) { |
| 312 | /* Check if we leave a signal handler; this can happen when |
| 313 | * calling longjmp() in the handler */ |
| 314 | CLG_(run_post_signal_on_call_stack_bottom)(); |
| 315 | } |
| 316 | |
| 317 | lower_entry = |
| 318 | &(CLG_(current_call_stack).entry[CLG_(current_call_stack).sp-1]); |
| 319 | |
| 320 | CLG_DEBUG(4,"+ pop_call_stack: frame %d, jcc %p\n", |
| 321 | CLG_(current_call_stack).sp, lower_entry->jcc); |
| 322 | |
| 323 | /* jCC item not any more on real stack: pop */ |
| 324 | jcc = lower_entry->jcc; |
| 325 | CLG_(current_state).nonskipped = lower_entry->nonskipped; |
| 326 | |
| 327 | if (jcc) { |
| 328 | fn_node* to_fn = jcc->to->cxt->fn[0]; |
| 329 | UInt* pdepth = CLG_(get_fn_entry)(to_fn->number); |
| 330 | if (CLG_(clo).skip_direct_recursion) { |
| 331 | /* only decrement depth if another function was called */ |
| 332 | if (jcc->from->cxt->fn[0] != to_fn) (*pdepth)--; |
| 333 | } |
| 334 | else (*pdepth)--; |
| 335 | depth = *pdepth; |
| 336 | |
| 337 | /* add cost difference to sum */ |
| 338 | if ( CLG_(add_diff_cost_lz)( CLG_(sets).full, &(jcc->cost), |
| 339 | lower_entry->enter_cost, |
| 340 | CLG_(current_state).cost) ) { |
| 341 | |
| 342 | /* only count this call if it attributed some cost. |
| 343 | * the ret_counter is used to check if a BBCC dump is needed. |
| 344 | */ |
| 345 | jcc->from->ret_counter++; |
| 346 | } |
| 347 | CLG_(stat).ret_counter++; |
| 348 | |
| 349 | /* restore context */ |
| 350 | CLG_(current_state).cxt = lower_entry->cxt; |
| 351 | CLG_(current_fn_stack).top = |
| 352 | CLG_(current_fn_stack).bottom + lower_entry->fn_sp; |
| 353 | CLG_ASSERT(CLG_(current_state).cxt != 0); |
| 354 | |
| 355 | if (depth == 0) function_left(to_fn, jcc->from); |
| 356 | } |
| 357 | |
| 358 | /* To allow for an assertion in push_call_stack() */ |
| 359 | lower_entry->cxt = 0; |
| 360 | |
| 361 | CLG_(current_call_stack).sp--; |
| 362 | |
| 363 | #if CLG_ENABLE_DEBUG |
| 364 | CLG_DEBUGIF(1) { |
| 365 | if (CLG_(clo).verbose<4) { |
| 366 | if (jcc) { |
| 367 | /* popped JCC target first */ |
| 368 | VG_(printf)("- %2d %p => ", |
| 369 | CLG_(current_call_stack).sp, |
| 370 | bb_addr(jcc->to->bb)); |
| 371 | CLG_(print_addr)(bb_jmpaddr(jcc->from->bb)); |
| 372 | VG_(printf)(", SP %p\n", |
| 373 | CLG_(current_call_stack).entry[CLG_(current_call_stack).sp].sp); |
| 374 | CLG_(print_cost)(10, CLG_(sets).full, jcc->cost); |
| 375 | } |
| 376 | else |
| 377 | VG_(printf)("- %2d [Skipped JCC], SP %p\n", |
| 378 | CLG_(current_call_stack).sp, |
| 379 | CLG_(current_call_stack).entry[CLG_(current_call_stack).sp].sp); |
| 380 | } |
| 381 | else { |
| 382 | VG_(printf)(" Popped "); |
| 383 | CLG_(print_stackentry)(7, CLG_(current_call_stack).sp); |
| 384 | if (jcc) { |
| 385 | VG_(printf)(" returned to "); |
| 386 | CLG_(print_addr_ln)(bb_jmpaddr(jcc->from->bb)); |
| 387 | } |
| 388 | } |
| 389 | } |
| 390 | #endif |
| 391 | |
| 392 | } |
| 393 | |
| 394 | |
| 395 | /* remove CallStack items to sync with current SP |
| 396 | */ |
| 397 | void CLG_(unwind_call_stack)(Addr sp, Int minpops) |
| 398 | { |
| 399 | Int csp; |
| 400 | CLG_DEBUG(4,"+ unwind_call_stack(sp %p, minpops %d): frame %d\n", |
| 401 | sp, minpops, CLG_(current_call_stack).sp); |
| 402 | |
| 403 | /* We pop old stack frames. |
| 404 | * For a call, be p the stack address with return address. |
| 405 | * - call_stack_esp[] has SP after the CALL: p-4 |
| 406 | * - current sp is after a RET: >= p |
| 407 | */ |
| 408 | |
| 409 | while( (csp=CLG_(current_call_stack).sp) >0) { |
| 410 | call_entry* top_ce = &(CLG_(current_call_stack).entry[csp-1]); |
| 411 | |
| 412 | if ((top_ce->sp < sp) || |
| 413 | ((top_ce->sp == sp) && minpops>0)) { |
| 414 | |
| 415 | minpops--; |
| 416 | CLG_(pop_call_stack)(); |
| 417 | csp=CLG_(current_call_stack).sp; |
| 418 | continue; |
| 419 | } |
| 420 | break; |
| 421 | } |
| 422 | |
| 423 | CLG_DEBUG(4,"- unwind_call_stack\n"); |
| 424 | } |