This is the mail archive of the binutils@sources.redhat.com mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

patch for binutils bfd/dwarf2.c.


Below is a patch for bfd/dwarf2.c.  It has been reviewed by Daniel Jacobowitz.

Description:
------------
Here are two coordinated changes to handle strange debugging info generated
by Intel's 6.0 C++ compiler.  In particular, 1) line sequences are (against
the DWARF2 standard) not always sorted by VMA and 2) sometimes not all
VMA's in a function have entries that should.  

'add_line_info' has been changed to build an ordered line_info_table even
when it is given unsorted input.  In these abnormal cases the list will
usually still be built very quickly, on order of O(n), where n is the line
sequence length.  In normal cases it always runs in O(n).

'lookup_address_in_line_info_table' has been changed to return line
information with the closest VMA in the event that an exact VMA match is not
found. 

Testing and testcases: 
----------------------
I have run the binutils regression tests with and without my changes and
the results are the same.

Our tests: We are using bintuils as the binary reader for a program
that performs source code structure recovery on binaries from a number of
different platforms.  (We esp. focus on loop recovery for scientific
programs.) This program is also a cross-tool and we have successfully
tested these changes (and a number of others to follow eventually) on a
number of different binaries (from GNU and non-GNU compilers) and
platforms.

hosts (all of which are enabled on each platform)
  mips64-sgi-irix6
  alpha-*-linux-gnu, alpha-*-osf
  sparc32-*-elf, sparc64-*-solaris2
  i386-*-linux-gnu
  ia64-*-linux-gnu

ChangeLog:
----------
2002-10-17  Nathan Tallent  <eraxxon@alumni.rice.edu>

	* dwarf2.c (add_line_info): Ensure that the line_info_table
	is sorted even when given an out-of-order line sequence by
	decode_line_info().  Optimize for speed.
	(lookup_address_in_line_info_table): When an exact VMA match is
	not found, return line information with the closest VMA.


Patch: bfd/dwarf2.c
(created with 'cvs diff -c3p' against cvs repository on 10/17/02)
------

Index: dwarf2.c
===================================================================
RCS file: /cvs/src/src/bfd/dwarf2.c,v
retrieving revision 1.36
diff -c -3 -p -r1.36 dwarf2.c
*** dwarf2.c	24 Sep 2002 07:11:16 -0000	1.36
--- dwarf2.c	17 Oct 2002 13:03:25 -0000
*************** struct line_info_table
*** 806,812 ****
    char* comp_dir;
    char** dirs;
    struct fileinfo* files;
!   struct line_info* last_line;
  };
  
  struct funcinfo
--- 806,813 ----
    char* comp_dir;
    char** dirs;
    struct fileinfo* files;
!   struct line_info* last_line;  /* largest VMA */
!   struct line_info* lcl_head;   /* local head; used in 'add_line_info' */
  };
  
  struct funcinfo
*************** struct funcinfo
*** 817,822 ****
--- 818,828 ----
    bfd_vma high;
  };
  
+ /* add_line_info: adds a new entry to the line_info list in the
+    line_info_table, ensuring that the list is sorted.  Note that the
+    line_info list is sorted from highest to lowest VMA (with possible
+    duplicates); that is, line_info->prev_line always accesses an equal
+    or smaller VMA.  */
  static void
  add_line_info (table, address, filename, line, column, end_sequence)
       struct line_info_table* table;
*************** add_line_info (table, address, filename,
*** 829,837 ****
    bfd_size_type amt = sizeof (struct line_info);
    struct line_info* info = (struct line_info*) bfd_alloc (table->abfd, amt);
  
!   info->prev_line = table->last_line;
!   table->last_line = info;
! 
    info->address = address;
    info->filename = filename;
    info->line = line;
--- 835,903 ----
    bfd_size_type amt = sizeof (struct line_info);
    struct line_info* info = (struct line_info*) bfd_alloc (table->abfd, amt);
  
!   /* Find the correct location for 'info'.  Normally we will receive
!      new line_info data 1) in order and 2) with increasing VMAs.
!      However some compilers break the rules (cf. decode_line_info) and
!      so we include some heuristics for quickly finding the correct
!      location for 'info'. In particular, these heuristics optimize for
!      the common case in which the VMA sequence that we receive is a
!      list of locally sorted VMAs such as
!        p...z a...j  (where a < j < p < z)
! 
!      Note: table->lcl_head is used to head an *actual* or *possible*
!      sequence within the list (such as a...j) that is not directly
!      headed by table->last_line
! 
!      Note: we may receive duplicate entries from 'decode_line_info' */
! 
! #define LHEAD table->lcl_head
!   if ( !table->last_line || (address >= table->last_line->address) )
!     {
!       /* Normal case: add 'info' to the beginning of the list */
!       info->prev_line = table->last_line;
!       table->last_line = info;
! 
!       /* lcl_head: initialize to head a *possible* sequence at the end */
!       if (!LHEAD)
! 	LHEAD = info; 
!     }
!   else if ( !LHEAD->prev_line && (LHEAD->address > address) )
!     {
!       /* Abnormal but easy: lcl_head is 1) at the *end* of the line
!          list and 2) the head of 'info' */
!       info->prev_line = NULL;
!       LHEAD->prev_line = info;
!     }
!   else if ( LHEAD->prev_line && (LHEAD->address > address
! 				 && address >= LHEAD->prev_line->address) )
!     {
!       /* Abnormal but easy: lcl_head is 1) in the *middle* of the line
!          list and 2) the head of 'info' */
!       info->prev_line = LHEAD->prev_line;
!       LHEAD->prev_line = info;
!     }
!   else
!     {
!       /* Abnormal but hard: Neither 'last_line' nor 'lcl_head' are valid
!          heads for 'info'.  Reset 'lcl_head' and recur. */
!       struct line_info* li2 = table->last_line; /* always non-NULL */
!       struct line_info* li1 = li2->prev_line;
!       while (li1)
! 	{
! 	  if (li2->address > address && address >= li1->address)
! 	    break;
! 	  
! 	  li2 = li1; /* always non-NULL */
! 	  li1 = li1->prev_line;
! 	}
!       LHEAD = li2;
!       
!       add_line_info(table, address, filename, line, column, end_sequence);
!       return;
!     }
! #undef LHEAD
!   
!   /* Set member data of 'info' */
    info->address = address;
    info->filename = filename;
    info->line = line;
*************** decode_line_info (unit, stash)
*** 982,987 ****
--- 1048,1054 ----
  
    table->files = NULL;
    table->last_line = NULL;
+   table->lcl_head = NULL;  
  
    line_ptr = stash->dwarf_line_buffer + unit->line_offset;
  
*************** lookup_address_in_line_info_table (table
*** 1249,1267 ****
       const char **filename_ptr;
       unsigned int *linenumber_ptr;
  {
    struct line_info* next_line = table->last_line;
!   struct line_info* each_line;
  
    if (!next_line)
      return false;
  
    each_line = next_line->prev_line;
! 
    while (each_line && next_line)
      {
!       if (!each_line->end_sequence
! 	  && addr >= each_line->address && addr < next_line->address)
! 	{
  	  /* If this line appears to span functions, and addr is in the
  	     later function, return the first line of that function instead
  	     of the last line of the earlier one.  This check is for GCC
--- 1316,1346 ----
       const char **filename_ptr;
       unsigned int *linenumber_ptr;
  {
+   /* Note: table->last_line should be a descendingly sorted list. */
    struct line_info* next_line = table->last_line;
!   struct line_info* each_line = NULL;
!   *filename_ptr = NULL;
  
    if (!next_line)
      return false;
  
    each_line = next_line->prev_line;
!   
!   /* Check for large addresses */
!   if (addr > next_line->address)
!     each_line = NULL; /* ensure we skip over the normal case */
!      
!   /* Normal case: search the list; save  */
    while (each_line && next_line)
      {
!       /* If we have an address match, save this info.  This allows us
!          to return as good as results as possible for strange debugging
!          info.  */
!       boolean addr_match = false;
!       if (each_line->address <= addr && addr <= next_line->address)
!         {
! 	  addr_match = true;
! 
  	  /* If this line appears to span functions, and addr is in the
  	     later function, return the first line of that function instead
  	     of the last line of the earlier one.  This check is for GCC
*************** lookup_address_in_line_info_table (table
*** 1278,1293 ****
  	      *filename_ptr = each_line->filename;
  	      *linenumber_ptr = each_line->line;
  	    }
! 	  return true;
! 	}
        next_line = each_line;
        each_line = each_line->prev_line;
      }
  
!   /* At this point each_line is NULL but next_line is not.  If we found the
!      containing function in this compilation unit, return the first line we
!      have a number for.  This is also for compatibility with GCC 2.95.  */
!   if (function != NULL)
      {
        *filename_ptr = next_line->filename;
        *linenumber_ptr = next_line->line;
--- 1357,1378 ----
  	      *filename_ptr = each_line->filename;
  	      *linenumber_ptr = each_line->line;
  	    }
!         }
! 
!       if (addr_match && !each_line->end_sequence)
!         return true; /* we have definitely found what we want */
! 
        next_line = each_line;
        each_line = each_line->prev_line;
      }
  
!   /* At this point each_line is NULL but next_line is not.  If we found
!      a candidate end-of-sequence point in the loop above, we can return
!      that (compatibility with a bug in the Intel compiler); otherwise,
!      assuming that we found the containing function for this address in
!      this compilation unit, return the first line we have a number for
!      (compatibility with GCC 2.95).  */
!   if (*filename_ptr == NULL && function != NULL)
      {
        *filename_ptr = next_line->filename;
        *linenumber_ptr = next_line->line;


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]