/*--------------------------------------------------------------------*/
/*--- Callgrind ---*/
/*--- ct_include.h ---*/
/*--- (C) 2004, Josef Weidendorfer ---*/
/*--------------------------------------------------------------------*/
#ifndef CT_INCLUDE
#define CT_INCLUDE
#include "vg_skin.h"
#include "ct_events.h"
/*------------------------------------------------------------*/
/*--- Calltree compile options --- */
/*------------------------------------------------------------*/
/* Enable debug output */
#define CT_ENABLE_DEBUG 0
/* Enable experimental features? */
#define CT_EXPERIMENTAL 0
/* Enable data collection ? */
#define CT_DATA 0
/* Enable hardware prefetch simulation ? */
#define CT_HWPREFETCH 1
/* Syscall Timing in microseconds?
* (define to 0 if you get compile errors) */
#define CT_MICROSYSTIME 1
/* Set to 1 if you want full sanity checks for JCC */
#define JCC_CHECK 0
/*------------------------------------------------------------*/
/*--- Command line options ---*/
/*------------------------------------------------------------*/
#define DEFAULT_DUMPNAME "callgrind.out"
#define DEFAULT_COMMANDNAME "callgrind.cmd"
#define DEFAULT_RESULTNAME "callgrind.res"
#define DEFAULT_INFONAME "/tmp/callgrind.info"
typedef struct _CommandLineOptions CommandLineOptions;
struct _CommandLineOptions {
/* Dump format options */
Char* filename_base; /* Base name for dumps */
Bool separate_dumps; /* Dump trace parts as separate files? */
Bool compress_strings;
Bool compress_events;
Bool compress_pos;
Bool mangle_names;
Bool compress_mangled;
Bool dump_line;
Bool dump_instr;
Bool dump_bb;
Bool dump_bbs; /* Dump basic block information? */
/* Dump generation options */
Int dump_every_bb; /* Dump every xxx BBs. */
/* Collection options */
Bool separate_threads; /* Separate threads in dump? */
Int separate_callers; /* Separate dependent on how many callers? */
Int separate_recursions; /* Max level of recursions to separate */
Bool skip_plt; /* Skip functions in PLT section? */
Bool skip_direct_recursion; /* Increment direct recursions the level? */
Bool collect_data; /* Collect Accesses to Datastructures ? */
Bool collect_atstart; /* Start in collecting state ? */
Bool collect_jumps; /* Collect (cond.) jumps in functions ? */
Bool collect_alloc; /* Collect size of allocated memory */
Bool collect_systime; /* Collect time for system calls */
/* Simulation options */
Bool simulate_cache;
Bool simulate_hwpref;
Bool instrument_atstart; /* Instrumentate at start? */
#if CT_ENABLE_DEBUG
Int verbose;
ULong verbose_start;
#endif
};
/*------------------------------------------------------------*/
/*--- Constants ---*/
/*------------------------------------------------------------*/
/* According to IA-32 Intel Architecture Software Developer's Manual: Vol 2 */
#define MAX_x86_INSTR_SIZE 16
/* Minimum cache line size allowed */
#define MIN_LINE_SIZE 16
/* Size of various buffers used for storing strings */
#define FILENAME_LEN 256
#define FN_NAME_LEN 4096 /* for C++ code :-) */
#define OBJ_NAME_LEN 256
#define BUF_LEN 512
#define COMMIFY_BUF_LEN 128
#define RESULTS_BUF_LEN 128
#define LINE_BUF_LEN 64
/*------------------------------------------------------------*/
/*--- Statistics ---*/
/*------------------------------------------------------------*/
typedef struct _Statistics Statistics;
struct _Statistics {
ULong call_counter;
ULong jcnd_counter;
ULong jump_counter;
ULong rec_call_counter;
ULong ret_counter;
ULong bb_executions;
Int context_counter;
Int bb_retranslations;
Int distinct_objs;
Int distinct_files;
Int distinct_fns;
Int distinct_contexts;
Int distinct_bbs;
Int distinct_jccs;
Int distinct_bbccs;
Int distinct_instrs;
Int distinct_skips;
Int bb_hash_resizes;
Int bbcc_hash_resizes;
Int jcc_hash_resizes;
Int cxt_hash_resizes;
Int fn_array_resizes;
Int call_stack_resizes;
Int fn_stack_resizes;
Int full_debug_BBs;
Int file_line_debug_BBs;
Int fn_name_debug_BBs;
Int no_debug_BBs;
Int bbcc_lru_misses;
Int jcc_lru_misses;
Int cxt_lru_misses;
Int bbcc_clones;
};
/*------------------------------------------------------------*/
/*--- Structure declarations ---*/
/*------------------------------------------------------------*/
typedef struct _Context Context;
typedef struct _CC CC;
typedef struct _BB BB;
typedef struct _Skipped Skipped;
typedef struct _BBCC BBCC;
typedef struct _jCC jCC;
typedef struct _fCC fCC;
typedef struct _fn_node fn_node;
typedef struct _file_node file_node;
typedef struct _obj_node obj_node;
typedef struct _fn_config fn_config;
typedef struct _call_entry call_entry;
typedef struct _thread_info thread_info;
/* Costs of event sets. Aliases to arrays of 64-bit values */
typedef ULong* SimCost; /* All events the simulator can produce */
typedef ULong* UserCost;
typedef ULong* FullCost; /* Simular + User */
/* For cache simulation */
typedef struct {
int size; /* bytes */
int assoc;
int line_size; /* bytes */
} cache_t;
/* JmpCall cost center
* for subroutine call (from->bb->jmp_addr => to->bb->addr)
*
* Each BB has at most one CALL instruction. The list of JCC from
* this call is a pointer to the list head (stored in BBCC), and
* <next_from> in the JCC struct.
*
* For fast lookup, JCCs are reachable with a hash table, keyed by
* the (from_bbcc,to) pair. <next_hash> is used for the JCC chain
* of one hash table entry.
*
* Cost <sum> holds event counts for already returned executions.
* <last> are the event counters at last enter of the subroutine.
* <sum> is updated on returning from the subroutine by
* adding the diff of <last> and current event counters to <sum>.
*
* After updating, <last> is set to current event counters. Thus,
* events are not counted twice for recursive calls (TODO: True?)
*/
#define JmpNone -1
#define JmpCond -2
struct _jCC {
Int jmpkind; /* JmpCall, JmpBoring, JmpCond */
jCC* next_hash; /* for hash entry chain */
jCC* next_from; /* next JCC from a BBCC */
BBCC *from, *to; /* call arc from/to this BBCC */
ULong call_counter; /* no wraparound with 64 bit */
FullCost cost; /* simulator + user counters */
};
/*
* Info for one instruction of a basic block.
*/
typedef struct _InstrInfo InstrInfo;
struct _InstrInfo {
Int instr_offset;
Int instr_size;
Int data_size;
Int cost_offset;
EventSet* eventset;
};
/**
* An instrumented basic block (BB).
*
* BBs are put into a resizable hash to allow for fast detection if a
* BB is to be retranslated but cost info is already available.
* The key for a BB is a (object, offset) tupel making it independent
* from possibly multiple mappings of the same ELF object.
*
* At the beginning of each instrumented BB,
* a call to setup_bbcc(), specifying a pointer to the
* according BB structure, is added.
*
* As cost of a BB has to be distinguished depending on the context,
* multiple cost centers for one BB (struct BBCC) exist and the according
* BBCC is set by setup_bbcc.
*/
struct _BB {
obj_node* obj; /* ELF object of BB */
UInt offset; /* file offset of BB in object file */
VgSectKind sect_kind; /* section of this BB, e.g. PLT */
UInt instr_count;
/* filled by SK_(get_fn_node) if debug info is available */
fn_node* fn; /* debug info for this BB */
Int line;
Bool is_entry; /* True if this BB is a function entry */
BBCC* bbcc_list; /* BBCCs for same BB (see next_bbcc in BBCC) */
BBCC* last_bbcc; /* Temporary: Cached for faster access (LRU) */
BB* next; /* chaining for a hash entry */
/* filled by SK_(instrument) if not seen before */
UInt jmp_offset; /* offset to 1st jmp instr */
UInt instr_len;
UInt cost_count;
InstrInfo instr[0]; /* info on instruction sizes and costs */
};
/**
* Function context
*
* Basic blocks are always executed in the scope of a context.
* A function context is a list of function nodes representing
* the call chain to the current context: I.e. fn[0] is the
* function we are currently in, fn[1] has called fn[0], and so on.
* Recursion levels are used for fn[0].
*
* To get a unique number for a full execution context, use
* rec_index = min(<fn->rec_separation>,<active>) - 1;
* unique_no = <number> + rec_index
*
* For each Context, recursion index and BB, there can be a BBCC.
*/
struct _Context {
UInt size; // number of function dependencies
UInt base_number; // for context compression & dump array
Context* next; // entry chaining for hash
UInt hash; // for faster lookup...
fn_node* fn[0];
};
/*
* Basic Block Cost Center
*
* On demand, multiple BBCCs will be created for the same BB
* dependend on command line options and:
* - current function (it's possible that a BB is executed in the
* context of different functions, e.g. in manual assembler/PLT)
* - current thread ID
* - position where current function is called from
* - recursion level of current function
*
* The cost centres for the instructions of a basic block are
* stored in a contiguous array.
* They are distinguishable by their tag field.
*/
struct _BBCC {
BB* bb; /* BB for this cost center */
Context* cxt; /* execution context of this BBCC */
ThreadId tid; /* only for assertion check purpose */
UInt rec_index; /* Recursion index in rec->bbcc for this bbcc */
BBCC** rec_array; /* Variable sized array of pointers to
* recursion BBCCs. Shared. */
ULong exe_counter; /* execution counter for BB in this context */
ULong ret_counter; /* how often returned from jccs of this bbcc */
BBCC* next_bbcc; /* Chain of BBCCs for same BB */
BBCC* lru_next_bbcc; /* BBCC executed next the last time */
jCC* lru_from_jcc; /* Temporary: Cached for faster access (LRU) */
jCC* lru_to_jcc; /* Temporary: Cached for faster access (LRU) */
jCC* jcc_list; /* list of arcs called from jmp_addr */
FullCost skipped; /* cost for skipped functions called from
* jmp_addr. Allocated lazy */
BBCC* next; /* entry chain in hash */
ULong* cost; /* start of 64bit costs for this BBCC */
};
/* the <number> of fn_node, file_node and obj_node are for compressed dumping
* and a index into the dump boolean table and fn_info_table
*/
struct _fn_node {
Char* name;
UInt number;
Context* last_cxt; /* LRU info */
Context* pure_cxt; /* the context with only the function itself */
file_node* file; /* reverse mapping for 2nd hash */
fn_node* next;
Bool dump_before;
Bool dump_after;
Bool zero_before;
Bool toggle_collect;
Bool skip;
Int group;
Int separate_callers;
Int separate_recursions;
#if CT_ENABLE_DEBUG
Int verbosity; /* Stores old verbosity level while in function */
#endif
};
/* Quite arbitrary fixed hash sizes */
#define N_OBJ_ENTRIES 47
#define N_FILE_ENTRIES 53
#define N_FN_ENTRIES 87
#define N_BBCC2_ENTRIES 37
struct _file_node {
Char* name;
fn_node* fns[N_FN_ENTRIES];
UInt number;
obj_node* obj;
file_node* next;
};
/* If an object is dlopened multiple times, we hope that <name> is unique;
* <start> and <offset> can change with each dlopen, and <start> is
* zero when object is unmapped (possible at dump time).
*/
struct _obj_node {
Char* name;
UInt size;
#if CT_ENABLE_DEBUG
UInt last_slash_pos;
#endif
Addr start; /* Start address of text segment mapping */
UInt offset; /* Offset between symbol address and file offset */
file_node* files[N_FILE_ENTRIES];
UInt number;
obj_node* next;
};
/* an entry in the callstack
*
* <nonskipped> is 0 if the function called is not skipped (usual case).
* Otherwise, it is the last non-skipped BBCC. This one gets all
* the calls to non-skipped functions and all costs in skipped
* instructions.
*/
struct _call_entry {
jCC* jcc; /* jCC for this call */
FullCost enter_cost; /* cost event counters at entering frame */
Addr esp; /* ESP at call time */
BBCC* nonskipped; /* see above */
Context* cxt; /* context before call */
Int fn_sp; /* function stack index before call */
};
/*
* Execution state of main thread or a running signal handler in
* a thread while interrupted by another signal handler.
* As there's no scheduling among running signal handlers of one thread,
* we only need a subset of a full thread state:
* - event counter
* - collect state
* - last BB, last jump kind, last nonskipped BB
* - callstack pointer for sanity checking and correct unwinding
* after exit
*/
typedef struct _exec_state exec_state;
struct _exec_state {
/* the signum of the handler, 0 for main thread context
*/
Int sig;
/* the old call stack pointer at entering the signal handler */
Int orig_sp;
FullCost cost;
Bool collect;
Context* cxt;
Int jmpkind; /* kind of jump from last BB executed
* -1 is "unset", -2 is "conditional jump" */
BBCC* bbcc; /* last BB executed */
BBCC* nonskipped;
Int call_stack_bottom; /* Index into fn_stack */
};
/* Global state structures */
typedef struct _bb_hash bb_hash;
struct _bb_hash {
Int size, entries;
BB** table;
};
typedef struct _cxt_hash cxt_hash;
struct _cxt_hash {
Int size, entries;
Context** table;
};
/* Thread specific state structures, i.e. parts of a thread state.
* There are variables for the current state of each part,
* on which a thread state is copied at thread switch.
*/
typedef struct _bbcc_hash bbcc_hash;
struct _bbcc_hash {
Int size, entries;
BBCC** table;
};
typedef struct _jcc_hash jcc_hash;
struct _jcc_hash {
Int size, entries;
jCC** table;
jCC* spontaneous;
};
typedef struct _fn_array fn_array;
struct _fn_array {
Int size;
UInt* array;
};
typedef struct _call_stack call_stack;
struct _call_stack {
Int size, sp;
call_entry* entry;
};
typedef struct _fn_stack fn_stack;
struct _fn_stack {
Int size;
fn_node **bottom, **top;
};
/* The maximum number of simultaneous running signal handlers per thread.
* This is the number of execution states storable in a thread.
*/
#define MAX_SIGHANDLERS 10
typedef struct _exec_stack exec_stack;
struct _exec_stack {
Int sp; /* > 0 if a handler is running */
exec_state* entry[MAX_SIGHANDLERS];
};
/* Thread State
*
* This structure stores thread specific info while a thread is *not*
* running. See function switch_thread() for save/restore on thread switch.
*
* If --separate-threads=no, BBCCs and JCCs can be shared by all threads, i.e.
* only structures of thread 1 are used.
* This involves variables fn_info_table, bbcc_table and jcc_table.
*/
struct _thread_info {
/* state */
fn_stack fns; /* function stack */
call_stack calls; /* context call arc stack */
exec_stack states; /* execution states interrupted by signals */
/* dump statistics */
FullCost lastdump_cost; /* Cost at last dump */
FullCost sighandler_cost;
/* thread specific data structure containers */
fn_array fn_active;
jcc_hash jccs;
bbcc_hash bbccs;
};
/*------------------------------------------------------------*/
/*--- Functions ---*/
/*------------------------------------------------------------*/
/* from ct_clo.c */
void SK_(set_clo_defaults)();
void SK_(update_fn_config)(fn_node*);
/* from ct_sim.c */
struct event_sets {
EventSet *Ir, *Dr, *Dw;
EventSet *D0, *D1r, *D1w, *D2;
EventSet *sim;
EventSet *full; /* sim plus user events */
/* offsets into eventsets */
Int off_sim_Ir, off_sim_Dr, off_sim_Dw;
Int off_full_Ir, off_full_Dr, off_full_Dw;
Int off_full_user, off_full_alloc, off_full_systime;
};
extern struct event_sets SK_(sets);
void SK_(cachesim_init)(void);
void SK_(cachesim_getdesc)(Char*);
void SK_(init_eventsets)(Bool do_cache, Int user);
void SK_(add_and_zero_Dx)(EventSet* es, SimCost dst, ULong* cost);
__attribute__ ((regparm (1))) void SK_(log_0D)(InstrInfo*);
__attribute__ ((regparm (2))) void SK_(log_1Dr)(InstrInfo*, Addr data);
__attribute__ ((regparm (2))) void SK_(log_1Dw)(InstrInfo*, Addr data);
__attribute__ ((regparm (3))) void SK_(log_2D)(InstrInfo*,
Addr data1, Addr data2);
/* from ct_main.c */
Bool SK_(get_debug_info)(Addr, Char filename[FILENAME_LEN],
Char fn_name[FN_NAME_LEN], Int*, SegInfo**);
void SK_(set_instrument_state)(Char*,Bool);
void SK_(dump_profile)(Char* trigger,Bool only_current_thread);
void SK_(zero_all_cost)(Bool only_current_thread);
Int SK_(get_dump_counter)(void);
/* from ct_command.c */
void SK_(init_command)(Char* dir, Char* dumps);
void SK_(check_command)(void);
void SK_(finish_command)(void);
/* from ct_bb.c */
void SK_(init_bb_hash)();
bb_hash* SK_(get_bb_hash)();
BB* SK_(get_bb)(Addr addr, UCodeBlock* cb_in, Bool *seen_before);
static __inline__ Addr bb_addr(BB* bb)
{ return bb->offset + bb->obj->offset; }
static __inline__ Addr bb_jmpaddr(BB* bb)
{ return bb->jmp_offset + bb->offset + bb->obj->offset; }
/* from ct_fn.c */
void SK_(init_fn_array)(fn_array*);
void SK_(copy_current_fn_array)(fn_array* dst);
fn_array* SK_(get_current_fn_array)();
void SK_(set_current_fn_array)(fn_array*);
UInt* SK_(get_fn_entry)(Int n);
void SK_(init_obj_table)();
obj_node* SK_(get_obj_node)(SegInfo* si);
file_node* SK_(get_file_node)(obj_node*, Char* filename);
fn_node* SK_(get_fn_node)(BB* bb);
/* from ct_bbcc.c */
void SK_(init_bbcc_hash)(bbcc_hash* bbccs);
void SK_(copy_current_bbcc_hash)(bbcc_hash* dst);
bbcc_hash* SK_(get_current_bbcc_hash)();
void SK_(set_current_bbcc_hash)(bbcc_hash*);
void SK_(forall_bbccs)(void (*func)(BBCC*));
void SK_(zero_bbcc)(BBCC* bbcc);
BBCC* SK_(get_bbcc)(BB* bb);
BBCC* SK_(clone_bbcc)(BBCC* orig, Context* cxt, Int rec_index);
__attribute__ ((regparm (1))) void SK_(setup_bbcc)(BB* bb);
/* from ct_jumps.c */
void SK_(init_jcc_hash)(jcc_hash*);
void SK_(copy_current_jcc_hash)(jcc_hash* dst);
jcc_hash* SK_(get_current_jcc_hash)();
void SK_(set_current_jcc_hash)(jcc_hash*);
jCC* SK_(get_jcc)(BBCC* from, BBCC* to);
/* from ct_callstack.c */
void SK_(init_call_stack)(call_stack*);
void SK_(copy_current_call_stack)(call_stack* dst);
void SK_(set_current_call_stack)(call_stack*);
call_entry* SK_(get_call_entry)(Int n);
void SK_(push_call_stack)(BBCC* from, BBCC* to, Addr esp, Bool skip);
void SK_(pop_call_stack)();
Int SK_(unwind_call_stack)(Addr esp);
/* from ct_context.c */
void SK_(init_fn_stack)(fn_stack*);
void SK_(copy_current_fn_stack)(fn_stack*);
fn_stack* SK_(get_current_fn_stack)();
void SK_(set_current_fn_stack)(fn_stack*);
void SK_(init_cxt_table)();
cxt_hash* SK_(get_cxt_hash)();
Context* SK_(get_cxt)(fn_node** fn);
void SK_(push_cxt)(fn_node* fn);
/* from ct_threads.c */
void SK_(init_threads)();
thread_info** SK_(get_threads)();
thread_info* SK_(get_current_thread)();
void SK_(switch_thread)(ThreadId tid);
void SK_(forall_threads)(void (*func)(thread_info*));
void SK_(run_thread)(ThreadId tid);
void SK_(init_exec_state)(exec_state* es);
void SK_(init_exec_stack)(exec_stack*);
void SK_(copy_current_exec_stack)(exec_stack*);
void SK_(set_current_exec_stack)(exec_stack*);
void SK_(pre_signal)(ThreadId tid, Int sigNum, Bool alt_stack);
void SK_(post_signal)(ThreadId tid, Int sigNum);
/* from ct_dump.c */
extern FullCost SK_(total_cost);
void SK_(init_files)(Char** dir, Char** file);
/*------------------------------------------------------------*/
/*--- Exported global variables ---*/
/*------------------------------------------------------------*/
extern CommandLineOptions SK_(clo);
extern Statistics SK_(stat);
extern EventMapping* SK_(dumpmap);
/* Function active counter array, indexed by function number */
extern UInt* SK_(fn_active_array);
extern Bool SK_(instrument_state);
extern call_stack SK_(current_call_stack);
extern fn_stack SK_(current_fn_stack);
extern exec_state SK_(current_state);
extern ThreadId SK_(current_tid);
extern Addr SK_(bb_base);
extern ULong* SK_(cost_base);
/*------------------------------------------------------------*/
/*--- Debugging ---*/
/*------------------------------------------------------------*/
#if CT_ENABLE_DEBUG
#define CT_DEBUGIF(x) \
if ( (SK_(clo).verbose >x) && \
(SK_(stat).bb_executions >= SK_(clo).verbose_start))
#define CT_DEBUG(x,format,args...) \
CT_DEBUGIF(x) { \
SK_(print_bbno)(); \
VG_(printf)(format,##args); \
}
#define CT_ASSERT(cond) \
if (!(cond)) { \
SK_(print_context)(); \
sk_assert(cond); \
}
#else
#define CT_DEBUGIF(x) if (0)
#define CT_DEBUG(x...) {}
#define CT_ASSERT(cond) sk_assert(cond);
#endif
/* from ct_debug.c */
void SK_(print_bbno)(void);
void SK_(print_context)(void);
void SK_(print_jcc)(int s, jCC* jcc);
void SK_(print_bbcc)(int s, BBCC* bbcc, Bool);
void SK_(print_bbcc_fn)(BBCC* bbcc);
void SK_(print_cost)(int s, EventSet*, ULong* cost);
void SK_(print_bb)(int s, BB* bb);
void SK_(print_cxt)(int s, Context* cxt, int rec_index);
void SK_(print_short_jcc)(jCC* jcc);
void SK_(print_stackentry)(int s, int sp);
void SK_(print_addr)(Addr addr);
void SK_(print_addr_ln)(Addr addr);
#endif /* CT_INCLUDE */
syntax highlighted by Code2HTML, v. 0.9.1