l4/pkg/valgrind/src/valgrind-3.6.0-svn/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-2010, 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 #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   = Ijk_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