Home | History | Annotate | Download | only in callgrind
      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-2015, 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 %u 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     HChar trigger[VG_(strlen)(fn->name) + 20];
    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     HChar trigger[VG_(strlen)(fn->name) + 20];
    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 	    const HChar spaces[][41] = {
    277                                   "   .   .   .   .   .   .   .   .   .   .",
    278 				  "  .   .   .   .   .   .   .   .   .   . ",
    279 				  " .   .   .   .   .   .   .   .   .   .  ",
    280 				  ".   .   .   .   .   .   .   .   .   .   " };
    281 
    282 	    int s = CLG_(current_call_stack).sp;
    283 	    UInt* pars = (UInt*) sp;
    284 
    285 	    BB* bb = jcc->to->bb;
    286 	    if (s>40) s=40;
    287 	    VG_(printf)("%s> %s(0x%x, 0x%x, ...) [%s / %#lx]\n", spaces[s%4]+40-s, bb->fn->name,
    288                         pars ? pars[1]:0,
    289 			pars ? pars[2]:0,
    290 			bb->obj->name + bb->obj->last_slash_pos,
    291 			(UWord)bb->offset);
    292 	  }
    293 	}
    294 	else if (CLG_(clo).verbose<4) {
    295 	    VG_(printf)("+ %2d ", CLG_(current_call_stack).sp);
    296 	    CLG_(print_short_jcc)(jcc);
    297 	    VG_(printf)(", SP %#lx, RA %#lx\n", sp, ret_addr);
    298 	}
    299 	else {
    300 	    VG_(printf)("  Pushed ");
    301 	    CLG_(print_stackentry)(3, CLG_(current_call_stack).sp-1);
    302 	}
    303     }
    304 #endif
    305 
    306 }
    307 
    308 
    309 /* Pop call stack and update inclusive sums.
    310  * Returns modified fcc.
    311  *
    312  * If the JCC becomes inactive, call entries are freed if possible
    313  */
    314 void CLG_(pop_call_stack)()
    315 {
    316     jCC* jcc;
    317     Int depth = 0;
    318     call_entry* lower_entry;
    319 
    320     if (CLG_(current_state).sig >0) {
    321 	/* Check if we leave a signal handler; this can happen when
    322 	 * calling longjmp() in the handler */
    323 	CLG_(run_post_signal_on_call_stack_bottom)();
    324     }
    325 
    326     lower_entry =
    327 	&(CLG_(current_call_stack).entry[CLG_(current_call_stack).sp-1]);
    328 
    329     CLG_DEBUG(4,"+ pop_call_stack: frame %d, jcc %p\n",
    330 		CLG_(current_call_stack).sp, lower_entry->jcc);
    331 
    332     /* jCC item not any more on real stack: pop */
    333     jcc = lower_entry->jcc;
    334     CLG_(current_state).nonskipped = lower_entry->nonskipped;
    335 
    336     if (jcc) {
    337 	fn_node* to_fn  = jcc->to->cxt->fn[0];
    338 	UInt* pdepth =  CLG_(get_fn_entry)(to_fn->number);
    339 	if (CLG_(clo).skip_direct_recursion) {
    340 	    /* only decrement depth if another function was called */
    341 	  if (jcc->from->cxt->fn[0] != to_fn) (*pdepth)--;
    342 	}
    343 	else (*pdepth)--;
    344 	depth = *pdepth;
    345 
    346 	/* add cost difference to sum */
    347 	if ( CLG_(add_diff_cost_lz)( CLG_(sets).full, &(jcc->cost),
    348 				    lower_entry->enter_cost,
    349 				    CLG_(current_state).cost) ) {
    350 
    351 	  /* only count this call if it attributed some cost.
    352 	   * the ret_counter is used to check if a BBCC dump is needed.
    353 	   */
    354 	  jcc->from->ret_counter++;
    355 	}
    356 	CLG_(stat).ret_counter++;
    357 
    358 	/* restore context */
    359 	CLG_(current_state).cxt  = lower_entry->cxt;
    360 	CLG_(current_fn_stack).top =
    361 	  CLG_(current_fn_stack).bottom + lower_entry->fn_sp;
    362 	CLG_ASSERT(CLG_(current_state).cxt != 0);
    363 
    364 	if (depth == 0) function_left(to_fn);
    365     }
    366 
    367     /* To allow for an assertion in push_call_stack() */
    368     lower_entry->cxt = 0;
    369 
    370     CLG_(current_call_stack).sp--;
    371 
    372 #if CLG_ENABLE_DEBUG
    373     CLG_DEBUGIF(1) {
    374 	if (CLG_(clo).verbose<4) {
    375 	    if (jcc) {
    376 		/* popped JCC target first */
    377 		VG_(printf)("- %2d %#lx => ",
    378 			    CLG_(current_call_stack).sp,
    379 			    bb_addr(jcc->to->bb));
    380 		CLG_(print_addr)(bb_jmpaddr(jcc->from->bb));
    381 		VG_(printf)(", SP %#lx\n",
    382 			    CLG_(current_call_stack).entry[CLG_(current_call_stack).sp].sp);
    383 		CLG_(print_cost)(10, CLG_(sets).full, jcc->cost);
    384 	    }
    385 	    else
    386 		VG_(printf)("- %2d [Skipped JCC], SP %#lx\n",
    387 			    CLG_(current_call_stack).sp,
    388 			    CLG_(current_call_stack).entry[CLG_(current_call_stack).sp].sp);
    389 	}
    390 	else {
    391 	    VG_(printf)("  Popped ");
    392 	    CLG_(print_stackentry)(7, CLG_(current_call_stack).sp);
    393 	    if (jcc) {
    394 		VG_(printf)("       returned to ");
    395 		CLG_(print_addr_ln)(bb_jmpaddr(jcc->from->bb));
    396 	    }
    397 	}
    398     }
    399 #endif
    400 
    401 }
    402 
    403 
    404 /* Unwind enough CallStack items to sync with current stack pointer.
    405  * Returns the number of stack frames unwinded.
    406  */
    407 Int CLG_(unwind_call_stack)(Addr sp, Int minpops)
    408 {
    409     Int csp;
    410     Int unwind_count = 0;
    411     CLG_DEBUG(4,"+ unwind_call_stack(sp %#lx, minpops %d): frame %d\n",
    412 	      sp, minpops, CLG_(current_call_stack).sp);
    413 
    414     /* We pop old stack frames.
    415      * For a call, be p the stack address with return address.
    416      *  - call_stack_esp[] has SP after the CALL: p-4
    417      *  - current sp is after a RET: >= p
    418      */
    419 
    420     while( (csp=CLG_(current_call_stack).sp) >0) {
    421 	call_entry* top_ce = &(CLG_(current_call_stack).entry[csp-1]);
    422 
    423 	if ((top_ce->sp < sp) ||
    424 	    ((top_ce->sp == sp) && minpops>0)) {
    425 
    426 	    minpops--;
    427 	    unwind_count++;
    428 	    CLG_(pop_call_stack)();
    429 	    csp=CLG_(current_call_stack).sp;
    430 	    continue;
    431 	}
    432 	break;
    433     }
    434 
    435     CLG_DEBUG(4,"- unwind_call_stack\n");
    436     return unwind_count;
    437 }
    438