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