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