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