ULong* CLG_(get_costarray)(Int size)
{
  ULong* ptr;

  if (!cost_chunk_current ||
      (cost_chunk_current->size - cost_chunk_current->used < size)) {
    CostChunk* cc  = (CostChunk*) CLG_MALLOC(sizeof(CostChunk) +
					      COSTCHUNK_SIZE * sizeof(ULong));
    cc->size = COSTCHUNK_SIZE;
    cc->used = 0;
    cc->next = 0;

    if (cost_chunk_current)
      cost_chunk_current->next = cc;
    cost_chunk_current = cc;

    if (!cost_chunk_base) cost_chunk_base = cc;

    CLG_(costarray_chunks)++;
  }
  
  ptr = &(cost_chunk_current->data[cost_chunk_current->used]);
  cost_chunk_current->used += size;

  CLG_(costarray_entries) += size;

  return ptr;
}

void CLG_(print_bbno)(void)
{
  if (bb_written != CLG_(stat).bb_executions) {
    bb_written = CLG_(stat).bb_executions;
    VG_(printf)("BB# %llu\n",CLG_(stat).bb_executions);
  }
}

/* Lookup for a BBCC in hash.
 */ 
static
BBCC* lookup_bbcc(BB* bb, Context* cxt)
{
   BBCC* bbcc = bb->last_bbcc;
   UInt  idx;

   /* check LRU */
   if (bbcc->cxt == cxt) {
       if (!CLG_(clo).separate_threads) {
	   /* if we don't dump threads separate, tid doesn't have to match */
	   return bbcc;
       }
       if (bbcc->tid == CLG_(current_tid)) return bbcc;
   }

   CLG_(stat).bbcc_lru_misses++;

   idx = bbcc_hash_idx(bb, cxt, current_bbccs.size);
   bbcc = current_bbccs.table[idx];
   while (bbcc &&
	  (bb      != bbcc->bb ||
	   cxt     != bbcc->cxt)) {
       bbcc = bbcc->next;
   }
   
   CLG_DEBUG(2,"  lookup_bbcc(BB %#lx, Cxt %d, fn '%s'): %p (tid %d)\n",
	    bb_addr(bb), cxt->base_number, cxt->fn[0]->name, 
	    bbcc, bbcc ? bbcc->tid : 0);

   CLG_DEBUGIF(2)
     if (bbcc) CLG_(print_bbcc)(-2,bbcc);

   return bbcc;
}

/*
 * Zero all costs of a BBCC
 */
void CLG_(zero_bbcc)(BBCC* bbcc)
{
  Int i;
  jCC* jcc;

  CLG_ASSERT(bbcc->cxt != 0);
  CLG_DEBUG(1, "  zero_bbcc: BB %#lx, Cxt %d "
	   "(fn '%s', rec %d)\n", 
	   bb_addr(bbcc->bb),
	   bbcc->cxt->base_number + bbcc->rec_index,
	   bbcc->cxt->fn[0]->name,
	   bbcc->rec_index);

  if ((bbcc->ecounter_sum ==0) &&
      (bbcc->ret_counter ==0)) return;

  for(i=0;i<bbcc->bb->cost_count;i++)
    bbcc->cost[i] = 0;
  for(i=0;i <= bbcc->bb->cjmp_count;i++) {
    bbcc->jmp[i].ecounter = 0;
    for(jcc=bbcc->jmp[i].jcc_list; jcc; jcc=jcc->next_from)
	CLG_(init_cost)( CLG_(sets).full, jcc->cost );
  }
  bbcc->ecounter_sum = 0;
  bbcc->ret_counter = 0;
}

static
void CLG_(post_syscalltime)(ThreadId tid, UInt syscallno, SysRes res)
{
    if (CLG_(clo).collect_systime) {
        Int o = CLG_(sets).off_full_systime;
#if CLG_MICROSYSTIME
        struct vki_timeval tv_now;
        ULong diff;

        VG_(do_syscall)(__NR_gettimeofday, (UInt)&tv_now, (UInt)NULL);
        diff = (tv_now.tv_sec * 1000000ULL + tv_now.tv_usec) - syscalltime[tid];
#else
        UInt diff = VG_(read_millisecond_timer)() - syscalltime[tid];
#endif

        CLG_DEBUG(0,"   Time (Off %d) for Syscall %d: %ull\n", o, syscallno, diff);

        if (o<0) return;

        CLG_(current_state).cost[o] ++;
        CLG_(current_state).cost[o+1] += diff;
        if (!CLG_(current_state).bbcc->skipped)
            CLG_(init_cost_lz)(CLG_(sets).full,
                               &(CLG_(current_state).bbcc->skipped));
        CLG_(current_state).bbcc->skipped[o] ++;
        CLG_(current_state).bbcc->skipped[o+1] += diff;
    }
}

static void print_call_stack()
{
    int c;

    VG_(printf)("Call Stack:\n");
    for(c=0;c<CLG_(current_call_stack).sp;c++)
      CLG_(print_stackentry)(-2, c);
}

Bool CLG_(is_equal_cost)(EventSet* es, ULong* c1, ULong* c2)
{
    Int i;

    if (!c1) return CLG_(is_zero_cost)(es, c2);
    if (!c2) return CLG_(is_zero_cost)(es, c1);

    for(i=0; i<es->size; i++)
	if (c1[i] != c2[i]) return False;

    return True;
}

static
void unwind_thread(thread_info* t)
{
    /* unwind signal handlers */
    while(CLG_(current_state).sig !=0)
        CLG_(post_signal)(CLG_(current_tid),CLG_(current_state).sig);

    /* unwind regular call stack */
    while(CLG_(current_call_stack).sp>0)
        CLG_(pop_call_stack)();

    /* reset context and function stack for context generation */
    CLG_(init_exec_state)( &CLG_(current_state) );
    CLG_(current_fn_stack).top = CLG_(current_fn_stack).bottom;
}

void CLG_(print_eventset)(int s, EventSet* es)
{
    int i, j;
    UInt mask;
    EventGroup* eg;

    if (s<0) {
	s = -s;
	print_indent(s);
    }

    if (!es) {
	VG_(printf)("(EventSet not set)\n");
	return;
    }

    VG_(printf)("EventSet %d (%d groups, size %d):",
		es->mask, es->count, es->size);

    if (es->count == 0) {
	VG_(printf)("-\n");
	return;
    }

    for(i=0, mask=1; i<MAX_EVENTGROUP_COUNT; i++, mask=mask<<1) {
	if ((es->mask & mask)==0) continue;
	eg = CLG_(get_event_group)(i);
	if (!eg) continue;
	VG_(printf)(" (%d: %s", i, eg->name[0]);
	for(j=1; j<eg->size; j++)
	    VG_(printf)(" %s", eg->name[j]);
	VG_(printf)(")");
    }
    VG_(printf)("\n");
}

void CLG_(print_bbcc)(int s, BBCC* bbcc, Bool jumpaddr)
{
  BB* bb;

  if (s<0) {
    s = -s;
    print_indent(s);
  }
  
  if (!bbcc) {
    VG_(printf)("BBCC 0x0\n");
    return;
  }
 
  bb = bbcc->bb;
  CLG_ASSERT(bb!=0);

#if 0 
  if (jumpaddr)
    VG_(printf)("%s +%p=%p, ",
	      bb->obj->name + bb->obj->last_slash_pos,
	      bb->jmp_offset, bb_jmpaddr(bb));
  else
#endif
    VG_(printf)("%s +%p=%p, ",
		bb->obj->name + bb->obj->last_slash_pos,
		bb->offset, bb_addr(bb));
  CLG_(print_cxt)(s+8, bbcc->cxt, bbcc->rec_index);
}

static void clg_start_client_code_callback ( ThreadId tid, ULong blocks_done )
{
   static ULong last_blocks_done = 0;

   if (0)
      VG_(printf)("%d R %llu\n", (Int)tid, blocks_done);

   /* throttle calls to CLG_(run_thread) by number of BBs executed */
   if (blocks_done - last_blocks_done < 5000) return;
   last_blocks_done = blocks_done;

   CLG_(run_thread)( tid );
}

/* double size of hash table 1 (addr->BBCC) */
static void resize_bbcc_hash(void)
{
    Int i, new_size, conflicts1 = 0, conflicts2 = 0;
    BBCC** new_table;
    UInt new_idx;
    BBCC *curr_BBCC, *next_BBCC;

    new_size = 2*current_bbccs.size+3;
    new_table = (BBCC**) CLG_MALLOC("cl.bbcc.rbh.1",
                                    new_size * sizeof(BBCC*));
 
    if (!new_table) return;
 
    for (i = 0; i < new_size; i++)
      new_table[i] = NULL;
 
    for (i = 0; i < current_bbccs.size; i++) {
	if (current_bbccs.table[i] == NULL) continue;
 
	curr_BBCC = current_bbccs.table[i];
	while (NULL != curr_BBCC) {
	    next_BBCC = curr_BBCC->next;

	    new_idx = bbcc_hash_idx(curr_BBCC->bb,
				    curr_BBCC->cxt,
				    new_size);

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

	    curr_BBCC = next_BBCC;
	}
    }

    VG_(free)(current_bbccs.table);


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

    current_bbccs.size = new_size;
    current_bbccs.table = new_table;
    CLG_(stat).bbcc_hash_resizes++;
}

// Called when a translation is removed from the translation cache for
// any reason at all: to free up space, because the guest code was
// unmapped or modified, or for any arbitrary reason.
static
void clg_discard_basic_block_info ( Addr64 orig_addr64, VexGuestExtents vge )
{
    Addr orig_addr = (Addr)orig_addr64;

    tl_assert(vge.n_used > 0);

    if (0)
        VG_(printf)( "discard_basic_block_info: %p, %p, %llu\n",
                     (void*)(Addr)orig_addr,
                     (void*)(Addr)vge.base[0], (ULong)vge.len[0]);

    // Get BB info, remove from table, free BB info.  Simple!  Note that we
    // use orig_addr, not the first instruction address in vge.
    CLG_(delete_bb)(orig_addr);
}

/* double size of bb table  */
static
void resize_bb_table(void)
{
    Int i, new_size, conflicts1 = 0, conflicts2 = 0;
    BB **new_table, *curr, *next;
    UInt new_idx;

    new_size  = 2* bbs.size +3;
    new_table = (BB**) CLG_MALLOC(new_size * sizeof(BB*));
 
    if (!new_table) return;
 
    for (i = 0; i < new_size; i++)
      new_table[i] = NULL;
 
    for (i = 0; i < bbs.size; i++) {
	if (bbs.table[i] == NULL) continue;
 
	curr = bbs.table[i];
	while (NULL != curr) {
	    next = curr->next;

	    new_idx = bb_hash_idx(curr->obj, curr->offset, 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)(bbs.table);


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

    bbs.size  = new_size;
    bbs.table = new_table;
    CLG_(stat).bb_hash_resizes++;
}