callgrind/jumps.c

   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-2013, Josef Weidendorfer (Josef.Weidendorfer@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: %d => %d (entries %d, 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/%d => 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