Home | History | Annotate | Download | only in callgrind
      1 /*--------------------------------------------------------------------*/
      2 /*--- Callgrind                                                    ---*/
      3 /*---                                                   ct_jumps.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 #define N_JCC_INITIAL_ENTRIES  4437
     32 
     33 /*------------------------------------------------------------*/
     34 /*--- Jump Cost Center (JCC) operations, including Calls   ---*/
     35 /*------------------------------------------------------------*/
     36 
     37 #define N_JCC_INITIAL_ENTRIES  4437
     38 
     39 jcc_hash current_jccs;
     40 
     41 void CLG_(init_jcc_hash)(jcc_hash* jccs)
     42 {
     43    Int i;
     44 
     45    CLG_ASSERT(jccs != 0);
     46 
     47    jccs->size    = N_JCC_INITIAL_ENTRIES;
     48    jccs->entries = 0;
     49    jccs->table = (jCC**) CLG_MALLOC("cl.jumps.ijh.1",
     50                                     jccs->size * sizeof(jCC*));
     51    jccs->spontaneous = 0;
     52 
     53    for (i = 0; i < jccs->size; i++)
     54      jccs->table[i] = 0;
     55 }
     56 
     57 
     58 void CLG_(copy_current_jcc_hash)(jcc_hash* dst)
     59 {
     60   CLG_ASSERT(dst != 0);
     61 
     62   dst->size        = current_jccs.size;
     63   dst->entries     = current_jccs.entries;
     64   dst->table       = current_jccs.table;
     65   dst->spontaneous = current_jccs.spontaneous;
     66 }
     67 
     68 void CLG_(set_current_jcc_hash)(jcc_hash* h)
     69 {
     70   CLG_ASSERT(h != 0);
     71 
     72   current_jccs.size        = h->size;
     73   current_jccs.entries     = h->entries;
     74   current_jccs.table       = h->table;
     75   current_jccs.spontaneous = h->spontaneous;
     76 }
     77 
     78 __inline__
     79 static UInt jcc_hash_idx(BBCC* from, UInt jmp, BBCC* to, UInt size)
     80 {
     81   return (UInt) ( (UWord)from + 7* (UWord)to + 13*jmp) % size;
     82 }
     83 
     84 /* double size of jcc table  */
     85 static void resize_jcc_table(void)
     86 {
     87     Int i, new_size, conflicts1 = 0, conflicts2 = 0;
     88     jCC** new_table;
     89     UInt new_idx;
     90     jCC *curr_jcc, *next_jcc;
     91 
     92     new_size  = 2* current_jccs.size +3;
     93     new_table = (jCC**) CLG_MALLOC("cl.jumps.rjt.1",
     94                                    new_size * sizeof(jCC*));
     95 
     96     if (!new_table) return;
     97 
     98     for (i = 0; i < new_size; i++)
     99       new_table[i] = NULL;
    100 
    101     for (i = 0; i < current_jccs.size; i++) {
    102 	if (current_jccs.table[i] == NULL) continue;
    103 
    104 	curr_jcc = current_jccs.table[i];
    105 	while (NULL != curr_jcc) {
    106 	    next_jcc = curr_jcc->next_hash;
    107 
    108 	    new_idx = jcc_hash_idx(curr_jcc->from, curr_jcc->jmp,
    109 				    curr_jcc->to, new_size);
    110 
    111 	    curr_jcc->next_hash = new_table[new_idx];
    112 	    new_table[new_idx] = curr_jcc;
    113 	    if (curr_jcc->next_hash) {
    114 		conflicts1++;
    115 		if (curr_jcc->next_hash->next_hash)
    116 		    conflicts2++;
    117 	    }
    118 
    119 	    curr_jcc = next_jcc;
    120 	}
    121     }
    122 
    123     VG_(free)(current_jccs.table);
    124 
    125 
    126     CLG_DEBUG(0, "Resize JCC Hash: %d => %d (entries %d, conflicts %d/%d)\n",
    127 	     current_jccs.size, new_size,
    128 	     current_jccs.entries, conflicts1, conflicts2);
    129 
    130     current_jccs.size  = new_size;
    131     current_jccs.table = new_table;
    132     CLG_(stat).jcc_hash_resizes++;
    133 }
    134 
    135 
    136 
    137 /* new jCC structure: a call was done to a BB of a BBCC
    138  * for a spontaneous call, from is 0 (i.e. caller unknown)
    139  */
    140 static jCC* new_jcc(BBCC* from, UInt jmp, BBCC* to)
    141 {
    142    jCC* jcc;
    143    UInt new_idx;
    144 
    145    /* check fill degree of jcc hash table and resize if needed (>80%) */
    146    current_jccs.entries++;
    147    if (10 * current_jccs.entries / current_jccs.size > 8)
    148        resize_jcc_table();
    149 
    150    jcc = (jCC*) CLG_MALLOC("cl.jumps.nj.1", sizeof(jCC));
    151 
    152    jcc->from      = from;
    153    jcc->jmp       = jmp;
    154    jcc->to        = to;
    155    jcc->jmpkind   = jk_Call;
    156    jcc->call_counter = 0;
    157    jcc->cost = 0;
    158 
    159    /* insert into JCC chain of calling BBCC.
    160     * This list is only used at dumping time */
    161 
    162    if (from) {
    163        /* Prohibit corruption by array overrun */
    164        CLG_ASSERT((0 <= jmp) && (jmp <= from->bb->cjmp_count));
    165        jcc->next_from = from->jmp[jmp].jcc_list;
    166        from->jmp[jmp].jcc_list = jcc;
    167    }
    168    else {
    169        jcc->next_from = current_jccs.spontaneous;
    170        current_jccs.spontaneous = jcc;
    171    }
    172 
    173    /* insert into JCC hash table */
    174    new_idx = jcc_hash_idx(from, jmp, to, current_jccs.size);
    175    jcc->next_hash = current_jccs.table[new_idx];
    176    current_jccs.table[new_idx] = jcc;
    177 
    178    CLG_(stat).distinct_jccs++;
    179 
    180    CLG_DEBUGIF(3) {
    181      VG_(printf)("  new_jcc (now %d): %p\n",
    182 		 CLG_(stat).distinct_jccs, jcc);
    183    }
    184 
    185    return jcc;
    186 }
    187 
    188 
    189 /* get the jCC for a call arc (BBCC->BBCC) */
    190 jCC* CLG_(get_jcc)(BBCC* from, UInt jmp, BBCC* to)
    191 {
    192     jCC* jcc;
    193     UInt idx;
    194 
    195     CLG_DEBUG(5, "+ get_jcc(bbcc %p/%d => bbcc %p)\n",
    196 		from, jmp, to);
    197 
    198     /* first check last recently used JCC */
    199     jcc = to->lru_to_jcc;
    200     if (jcc && (jcc->from == from) && (jcc->jmp == jmp)) {
    201 	CLG_ASSERT(to == jcc->to);
    202 	CLG_DEBUG(5,"- get_jcc: [LRU to] jcc %p\n", jcc);
    203 	return jcc;
    204     }
    205 
    206     jcc = from->lru_from_jcc;
    207     if (jcc && (jcc->to == to) && (jcc->jmp == jmp)) {
    208 	CLG_ASSERT(from == jcc->from);
    209 	CLG_DEBUG(5, "- get_jcc: [LRU from] jcc %p\n", jcc);
    210 	return jcc;
    211     }
    212 
    213     CLG_(stat).jcc_lru_misses++;
    214 
    215     idx = jcc_hash_idx(from, jmp, to, current_jccs.size);
    216     jcc = current_jccs.table[idx];
    217 
    218     while(jcc) {
    219 	if ((jcc->from == from) &&
    220 	    (jcc->jmp == jmp) &&
    221 	    (jcc->to == to)) break;
    222 	jcc = jcc->next_hash;
    223     }
    224 
    225     if (!jcc)
    226 	jcc = new_jcc(from, jmp, to);
    227 
    228     /* set LRU */
    229     from->lru_from_jcc = jcc;
    230     to->lru_to_jcc = jcc;
    231 
    232     CLG_DEBUG(5, "- get_jcc(bbcc %p => bbcc %p)\n",
    233 		from, to);
    234 
    235     return jcc;
    236 }
    237 
    238