1 /*--------------------------------------------------------------------*/ 2 /*--- Callgrind ---*/ 3 /*--- ct_callstack.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 /*------------------------------------------------------------*/ 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("cl.callstack.ics.1", 56 s->size * sizeof(call_entry)); 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 100 cs->entry = (call_entry*) VG_(realloc)("cl.callstack.ess.1", 101 cs->entry, 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 */ 117 static void function_entered(fn_node* fn) 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, 127 "Entering %s: Verbosity set to %d\n", 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) */ 150 static void function_left(fn_node* fn) 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, 172 "Leaving %s: Verbosity set back to %d\n", 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 233 if (*pdepth == 1) function_entered(to_fn); 234 } 235 236 /* return address is only is useful with a real call; 237 * used to detect RET w/o CALL */ 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; 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; 286 VG_(printf)("%s> %s(0x%x, 0x%x, ...) [%s / %#lx]\n", spaces[s%4]+40-s, bb->fn->name, 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); 296 VG_(printf)(", SP %#lx, RA %#lx\n", sp, ret_addr); 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 363 if (depth == 0) function_left(to_fn); 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 */ 376 VG_(printf)("- %2d %#lx => ", 377 CLG_(current_call_stack).sp, 378 bb_addr(jcc->to->bb)); 379 CLG_(print_addr)(bb_jmpaddr(jcc->from->bb)); 380 VG_(printf)(", SP %#lx\n", 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 385 VG_(printf)("- %2d [Skipped JCC], SP %#lx\n", 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 403 /* Unwind enough CallStack items to sync with current stack pointer. 404 * Returns the number of stack frames unwinded. 405 */ 406 Int CLG_(unwind_call_stack)(Addr sp, Int minpops) 407 { 408 Int csp; 409 Int unwind_count = 0; 410 CLG_DEBUG(4,"+ unwind_call_stack(sp %#lx, minpops %d): frame %d\n", 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--; 426 unwind_count++; 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"); 435 return unwind_count; 436 } 437
