callgrind/context.c

/*--------------------------------------------------------------------*/
/*--- Callgrind                                                    ---*/
/*---                                                 ct_context.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Callgrind, a Valgrind tool for call tracing.

   Copyright (C) 2002-2008, Josef Weidendorfer (Josef.Weidendorfer@gmx.de)

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307, USA.

   The GNU General Public License is contained in the file COPYING.
*/

#include "global.h"


/*------------------------------------------------------------*/
/*--- Context operations                                   ---*/
/*------------------------------------------------------------*/

#define N_FNSTACK_INITIAL_ENTRIES 500
#define N_CXT_INITIAL_ENTRIES 2537

fn_stack CLG_(current_fn_stack);

void CLG_(init_fn_stack)(fn_stack* s)
{
  CLG_ASSERT(s != 0);

  s->size   = N_FNSTACK_INITIAL_ENTRIES;   
  s->bottom = (fn_node**) CLG_MALLOC(s->size * sizeof(fn_node*));
  s->top    = s->bottom;
  s->bottom[0] = 0;
}

void CLG_(copy_current_fn_stack)(fn_stack* dst)
{
  CLG_ASSERT(dst != 0);

  dst->size   = CLG_(current_fn_stack).size;
  dst->bottom = CLG_(current_fn_stack).bottom;
  dst->top    = CLG_(current_fn_stack).top;
}

void CLG_(set_current_fn_stack)(fn_stack* s)
{
  CLG_ASSERT(s != 0);

  CLG_(current_fn_stack).size   = s->size;
  CLG_(current_fn_stack).bottom = s->bottom;
  CLG_(current_fn_stack).top    = s->top;
}

static cxt_hash cxts;

void CLG_(init_cxt_table)()
{
   Int i;
   
   cxts.size    = N_CXT_INITIAL_ENTRIES;
   cxts.entries = 0;
   cxts.table   = (Context**) CLG_MALLOC(cxts.size * sizeof(Context*));

   for (i = 0; i < cxts.size; i++)
     cxts.table[i] = 0;
}

cxt_hash* CLG_(get_cxt_hash)()
{
  return &cxts;
}

/* double size of cxt table  */
static void resize_cxt_table(void)
{
    UInt i, new_size, conflicts1 = 0, conflicts2 = 0;
    Context **new_table, *curr, *next;
    UInt new_idx;

    new_size  = 2* cxts.size +3;
    new_table = (Context**) CLG_MALLOC(new_size * sizeof(Context*));

    if (!new_table) return;

    for (i = 0; i < new_size; i++)
      new_table[i] = NULL;

    for (i = 0; i < cxts.size; i++) {
        if (cxts.table[i] == NULL) continue;

        curr = cxts.table[i];
        while (NULL != curr) {
            next = curr->next;

            new_idx = (UInt) (curr->hash % new_size);

            curr->next = new_table[new_idx];
            new_table[new_idx] = curr;
            if (curr->next) {
                conflicts1++;
                if (curr->next->next)
                    conflicts2++;
            }

            curr = next;
        }
    }

    VG_(free)(cxts.table);


    CLG_DEBUG(0, "Resize Context Hash: %d => %d (entries %d, conflicts %d/%d)\n",
             cxts.size, new_size,
             cxts.entries, conflicts1, conflicts2);

    cxts.size  = new_size;
    cxts.table = new_table;
    CLG_(stat).cxt_hash_resizes++;
}

__inline__
static UWord cxt_hash_val(fn_node** fn, UInt size)
{
    UWord hash = 0;
    UInt count = size;
    while(*fn != 0) {
        hash = (hash<<7) + (hash>>25) + (UWord)(*fn);
        fn--;
        count--;
        if (count==0) break;
    }
    return hash;
}

__inline__
static Bool is_cxt(UWord hash, fn_node** fn, Context* cxt)
{
    int count;
    fn_node** cxt_fn;

    if (hash != cxt->hash) return False;

    count = cxt->size;
    cxt_fn = &(cxt->fn[0]);
    while((*fn != 0) && (count>0)) {
        if (*cxt_fn != *fn) return False;
        fn--;
        cxt_fn++;
        count--;
    }
    return True;
}

/**
 * Allocate new Context structure
 */
static Context* new_cxt(fn_node** fn)
{
    Context* new;
    UInt idx, offset;
    UWord hash;
    int size, recs;
    fn_node* top_fn;

    CLG_ASSERT(fn);
    top_fn = *fn;
    if (top_fn == 0) return 0;

    size = top_fn->separate_callers +1;
    recs = top_fn->separate_recursions;
    if (recs<1) recs=1;

    /* check fill degree of context hash table and resize if needed (>80%) */
    cxts.entries++;
    if (10 * cxts.entries / cxts.size > 8)
        resize_cxt_table();

    new = (Context*) CLG_MALLOC(sizeof(Context)+sizeof(fn_node*)*size);

    // hash value calculation similar to cxt_hash_val(), but additionally
    // copying function pointers in one run
    hash = 0;
    offset = 0;
    while(*fn != 0) {
        hash = (hash<<7) + (hash>>25) + (UWord)(*fn);
        new->fn[offset] = *fn;
        offset++;
        fn--;
        if (offset >= size) break;
    }
    if (offset < size) size = offset;

    new->size        = size;
    new->base_number = CLG_(stat).context_counter;
    new->hash        = hash;

    CLG_(stat).context_counter += recs;
    CLG_(stat).distinct_contexts++;

    /* insert into Context hash table */
    idx = (UInt) (hash % cxts.size);
    new->next = cxts.table[idx];
    cxts.table[idx] = new;

#if CLG_ENABLE_DEBUG
    CLG_DEBUGIF(3) {
      VG_(printf)("  new_cxt ox%p: ", new);
      CLG_(print_cxt)(12, new, 0);
    }
#endif

    return new;
}

/* get the Context structure for current context */
Context* CLG_(get_cxt)(fn_node** fn)
{
    Context* cxt;
    UInt size, idx;
    UWord hash;

    CLG_ASSERT(fn != 0);
    if (*fn == 0) return 0;
    size = (*fn)->separate_callers+1;
    if (size<=0) { size = -size+1; }

    CLG_DEBUG(5, "+ get_cxt(fn '%s'): size %d\n",
                (*fn)->name, size);

    hash = cxt_hash_val(fn, size);

    if ( ((cxt = (*fn)->last_cxt) != 0) && is_cxt(hash, fn, cxt)) {
        CLG_DEBUG(5, "- get_cxt: %p\n", cxt);
        return cxt;
    }

    CLG_(stat).cxt_lru_misses++;

    idx = (UInt) (hash % cxts.size);
    cxt = cxts.table[idx];

    while(cxt) {
        if (is_cxt(hash,fn,cxt)) break;
        cxt = cxt->next;
    }

    if (!cxt)
        cxt = new_cxt(fn);

    (*fn)->last_cxt = cxt;

    CLG_DEBUG(5, "- get_cxt: %p\n", cxt);

    return cxt;
}


/**
 * Change execution context by calling a new function from current context
 *
 */
void CLG_(push_cxt)(fn_node* fn)
{
  call_stack* cs = &CLG_(current_call_stack);
  Int fn_entries;

  CLG_DEBUG(5, "+ push_cxt(fn '%s'): old ctx %d\n", 
	    fn ? fn->name : (Char*)"0x0",
	    CLG_(current_state).cxt ?
	    CLG_(current_state).cxt->base_number : -1);

  /* save old context on stack (even if not changed at all!) */
  CLG_ASSERT(cs->sp < cs->size);
  CLG_ASSERT(cs->entry[cs->sp].cxt == 0);
  cs->entry[cs->sp].cxt = CLG_(current_state).cxt;
  cs->entry[cs->sp].fn_sp = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom;

  if (*(CLG_(current_fn_stack).top) == fn) return;
  if (fn && (fn->group>0) &&
      ((*(CLG_(current_fn_stack).top))->group == fn->group)) return;

  /* resizing needed ? */
  fn_entries = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom;
  if (fn_entries == CLG_(current_fn_stack).size-1) {
    int new_size = CLG_(current_fn_stack).size *2;
    fn_node** new = (fn_node**) CLG_MALLOC(new_size * sizeof(fn_node*));
    int i;
    for(i=0;i<CLG_(current_fn_stack).size;i++)
      new[i] = CLG_(current_fn_stack).bottom[i];
    VG_(free)(CLG_(current_fn_stack).bottom);
    CLG_(current_fn_stack).top = new + fn_entries;
    CLG_(current_fn_stack).bottom = new;

    CLG_DEBUG(0, "Resize Context Stack: %d => %d (pushing '%s')\n", 
	     CLG_(current_fn_stack).size, new_size,
	     fn ? fn->name : (Char*)"0x0");

    CLG_(current_fn_stack).size = new_size;
  }

  if (*(CLG_(current_fn_stack).top) == 0) {
    UInt *pactive;

    /* this is first function: increment its active count */
    CLG_ASSERT(fn != 0);
    pactive = CLG_(get_fn_entry)(fn->number);
    (*pactive)++;
  }

  CLG_(current_fn_stack).top++;
  *(CLG_(current_fn_stack).top) = fn;
  CLG_(current_state).cxt = CLG_(get_cxt)(CLG_(current_fn_stack).top);

  CLG_DEBUG(5, "- push_cxt(fn '%s'): new cxt %d, fn_sp %d\n", 
	    fn ? fn->name : (Char*)"0x0",
	    CLG_(current_state).cxt ?
	      CLG_(current_state).cxt->base_number : -1,
	    CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom);
}