/*--------------------------------------------------------------------*/ /*--- 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 * in the JCC struct. * * For fast lookup, JCCs are reachable with a hash table, keyed by * the (from_bbcc,to) pair. is used for the JCC chain * of one hash table entry. * * Cost holds event counts for already returned executions. * are the event counters at last enter of the subroutine. * is updated on returning from the subroutine by * adding the diff of and current event counters to . * * After updating, 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(rec_separation>,) - 1; * unique_no = + 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 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 is unique; * and can change with each dlopen, and 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 * * 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 */