Dependence Tracing Algorithm

created by TongxinBai - 21 Jan 2008

The profiling tool is built upon a compile-time instrumentation framework and a separate tool file that contains the realizations of the instrumented functions.


Each function is instrumented in one of the two modes: DETAIL and SKETCH. A text file named which is expected to be put in the source directory indicates which functions are to be instrumented in DETAIL mode.
  • In SKETCH mode each memory reference is instrumented.
  • In DETAIL mode, besides memory reference, function entry and exits will be instrumented too.
For each memory reference four items of data are passed as parameters to the instrumentation call.
  • run-time address of the memory access
  • source file name
  • line number in source code
For each function entry or exit the function name should be provided.


The main instrumentation interfaces are:
  • _bop_prof_rec_write,
  • _bop_prof_rec_read,
  • bop_instm_func_entry, and
  • bop_instm_func_exit

recording write

void _bop_prof_rec_write (unsigned long addr, int sketch_p, char *file_name, int line) {
   update_pseudo_time ();
   if (!sketch_p) {
      update_frozen_time ();
      update_toplev_location (file_name, line);
   update_write (addr, file_name, line);
recording read
void _bop_prof_rec_read (unsigned long addr, int sketch_p, char *file_name, int line) {
   update_pseudo_time ();
   if (!sketch_p) {
      update_fronzen_time ();
      update_toplev_location (file_name, line);
   w = lookup_write (addr);
   if (!w) return;
   /* not a function level dependence. ignore. 
       Here I use frozen time to facilitate recording function level dependences.
       Frozen time only increments in DETAIL mode */
   if (w->frozen_time == current_frozen_time) return;

   output_dependence (...);
recording function entry
void bop_instm_func_entry (char *file_name, char *func_name) {
   output_function_entering ();
recording function exit
void bop_instm_func_exit (char *func_name) {
   output_function_leaving ();

The data structure for memory write operation is

struct _write
   unsigned int addr;
   long long psu_time;
   long long frozen_time;
   char *file_name;
   int line;
   char *toplev_file_name;
   int toplev_line;
   struct _write *hash_next;
Field file_name and line hold the access level location of the write while field toplev_file_name and toplev_line hold the function level location.

To help record function (top) level locations, two global variables are used, toplev_file_name and toplev_line. The two variables hold the current function level location so that they can be copied to the corresponding two fields in struct _write when a write is to be recorded.


For a function marked for detailed recording, we would like to record the dependence between any pair of its statements, even though the actual data access happens in a function call to some other functions. The function-level dependence is between two statements of a detail recorded function. The access-level dependence is between the two statements accessing the memory.

The frozen time increments only when a statement in a detail recorded function is executed. The analyzer records a dependence only when the source and the sink happen at different frozen times. It removes from consideration dependences that span an execution without any occurrence of detail recorded statements.

More notes

This topic: Main > TWikiGroups > CompilerGroup > CompilerRepository > GccVersion4_1_0 > DTTAlgorithm
Topic revision: r6 - 2008-01-22 - ChenDing
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback