[LTO]: Handle DW_form_ref_addr

[Daniel Berlin <dberlin at dberlin dot org>]

So, first, I just wanted to point out that the libelf 0.8.5 I found
included in my OpenSUSE 10.1 distro (and the web), and Ubuntu, doesn't
include "elf_getshstrndx" (all other functions are there).

The libelf from elfutils includes this function.

So this is just a heads up that we may have to include this function in
libiberty (it looks relatively simple to implement, it is just looking
at the elf header to find the string section index).

(I copied a friendly SuSE person so that they are aware of this, and
might be able to get upstream libelf to just add the function).

But on with the patch:

This patch enables us to handle DW_FORM_ref_addr, including both forward
and backward references to compilation units.

It does *not* change that we currently assume all CU's share the same
abbrevs, i will do this in a followup patch.

Along the way to supporting DW_FORM_ref_addr, I fixed a bug in the
compilation unit length calculation.  One niggle of the DWARF spec is
that the compilation unit length does *not* include the size of the
length field in the header.  We weren't taking this into account, so our
cu_start/cu_end was off by 4 or 12 bytes for every compilation unit
after the first.

I had to make a copy of the DWARF2_Internal_CompUnit structure, because
it does not include the offset from the beginning of debug_info.

Other than that, the only main changes are:
1  We now do a two pass walk of the compilation units, just like we were
doing for abbrevs.  We need to have all the cu_start/cu_end's at the
beginning of the reading in order to handle DW_FORM_ref_addr that point
*forward* to compilation units we haven't read yet.

2. lto_read_form has an extra output pointer to the context necessary to
read the form.

3. Changes necessary to do #1 and #2 (keep an array of compilation unit
structures, be able to find which compilation unit to switch to for a
given offset).

The only ugly part of this patch is that we have to have a pointer to
the info_fd in the context.

Alternatives include:

1. Change every single place that takes an lto_fd to take an
lto_info_fd, and change all of them to access the cur pointers through base.

2. Use a union of lto_info_fd, lto_abbrev_fd, and lto_fd, like we do
with union tree_node *tree, and use *this* type in all of those functions.

I wasn't sure which you would prefer, so i just stuck a pointer to the
info fd in the context for the moment (admittedly, a complete kludge :P)

I'm happy to do #1 or #2 and change the patch to use it if you like.

I tested this on the attached object file, which is a two CU object file
 with a back-referencing DW_form_ref_addr in the second compilation unit.
The abbrevs for both CU's are the same, even though there are two lists
of abbrevs in the debug_abbrev section.

What are we doing about testing, BTW?

--Dan

2006-07-02  Daniel Berlin  <dberlin@dberlin.org>

	* lto.c (lto_context): Add current_cu and info_fd members.
	(DWARF2_CompUnit): New structure.
	(lto_set_cu_context): New function
	(lto_info_fd_init): Ditto.
	(lto_info_fd_close): Ditto.
	(lto_file_init): Use lto_info_fd_init.
	(lto_file_close): Use lto_info_fd_close.
	(lto_read_initial_length): Pass in pointer to header size.
	(lto_read_comp_unit_header): Correct cu_length to
	real length from beginning of header.
	(find_cu_for_offset): New function.
	(lto_read_form): Add FORM_CONTEXT argument.
	Handle DW_FORM_ref_addr.
	(LTO_BEGIN_READ_ATTRS_UNCHECKED): Save old context.
	Swap contexts if necessary for form.
	(LTO_END_READ_ATTRS): Swap contexts back if it had changed.
	(lto_info_read): New function.
	(lto_set_cu_context): Ditto.
	(lto_file_read): Use lto_info_read, walk resulting CU's
	(lto_main): Update for lto_info_fd change.
	* lto-elf.c (lto_elf_file_open): Cast lto_info_fd to lto_fd where
	necessary.
	* lto.h (DWARF2_CompUnit): New structure.
	(lto_info_fd): Ditto.
	(lto_file): Change debug_info to be an lto_info_fd.

Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 115124)
+++ lto/lto.c	(working copy)
@@ -114,10 +114,15 @@ typedef struct DWARF2_form_data
    about the current location in the scope tree.  */
 typedef struct lto_context
 {
-  /* The start of the current compilation unit header.  */
+  /* The start of the current compilation unit info.  */
   const char *cu_start;
   /* The byte just past the end of the current compilation unit.  */
   const char *cu_end;
+  /* Pointer to the CompUnit structure currently being used.  */
+  const DWARF2_CompUnit *current_cu;
+  /* Pointer to the current debug_info fd being used.  Needed for
+     switching between compilation unit sections at ref_addr forms.  */
+  const lto_info_fd *info_fd;
   /* The scope (a NAMESPACE_DECL, FUNCTION_DECL, RECORD_TYPE, etc.)
      containing the DIE about to be read.  NULL_TREE if at the
      outermost level.  */
@@ -127,6 +132,26 @@ typedef struct lto_context
   tree type;
 } lto_context;
 
+/* We can't use DWARF_Internal_CompUnit because it does not track the
+   offset from the beginning of debug_info, which necessary for
+   lookups of DW_FORM_ref_addr data.  */
+   
+struct DWARF2_CompUnit
+{
+  /* Offset from start of .debug_info for this CU.  */
+  unsigned long cu_start_offset;  
+  /* Length of the CU header.  */
+  unsigned long cu_header_length;
+  /* Length of CU *including* the length field.  */
+  unsigned long cu_length;
+  /* DWARF version number of this CU.  */
+  unsigned short cu_version;
+  /* Offset of abbrevs for this CU from the start of debug_abbrev.  */
+  unsigned long cu_abbrev_offset;
+  /* Pointer size of this CU.  */
+  unsigned char cu_pointer_size;
+};
+
 /* Forward Declarations */
 
 static bool
@@ -138,6 +163,9 @@ lto_read_child_DIEs (lto_fd *fd, 
 		     const DWARF2_abbrev *abbrev, 
 		     lto_context *context);
 
+static void
+lto_set_cu_context (lto_context *context, lto_fd *fd,
+		    DWARF2_CompUnit *unit);
 /* Functions */ 
 
 /* Initialize FD, a newly allocated "file descriptor".  NAME indicates
@@ -155,6 +183,16 @@ lto_fd_init (lto_fd *fd, const char *nam
 }
 
 /* Initialize FD, a newly allocated file descriptor for a DWARF2
+   info section.  NAME and FILE are as for lto_fd_init.  */
+static void
+lto_info_fd_init (lto_info_fd *fd, const char *name, lto_file *file)
+{
+  lto_fd_init ((lto_fd *) fd, name, file);
+  fd->num_units = 0;
+  fd->units = NULL;
+}
+
+/* Initialize FD, a newly allocated file descriptor for a DWARF2
    abbreviation section.  NAME and FILE are as for lto_fd_init.  */
 static void
 lto_abbrev_fd_init (lto_abbrev_fd *fd, const char *name, lto_file *file)
@@ -166,6 +204,17 @@ lto_abbrev_fd_init (lto_abbrev_fd *fd, c
 
 /* Close FD.  */
 static void
+lto_info_fd_close (lto_info_fd *fd)
+{
+  size_t i;
+
+  for (i = 0; i < fd->num_units; ++i)
+    XDELETE (fd->units[i]);
+  XDELETEVEC (fd->units);
+}
+
+/* Close FD.  */
+static void
 lto_abbrev_fd_close (lto_abbrev_fd *fd)
 {
   size_t i;
@@ -180,7 +229,7 @@ void
 lto_file_init (lto_file *file, const char *filename)
 {
   file->filename = filename;
-  lto_fd_init (&file->debug_info, ".debug_info", file);
+  lto_info_fd_init (&file->debug_info, ".debug_info", file);
   lto_abbrev_fd_init (&file->debug_abbrev, ".debug_abbrev", file);
 }
 
@@ -188,6 +237,7 @@ lto_file_init (lto_file *file, const cha
 void
 lto_file_close (lto_file *file)
 {
+  lto_info_fd_close (&file->debug_info);
   lto_abbrev_fd_close (&file->debug_abbrev);
   free (file);
 }
@@ -287,9 +337,10 @@ lto_read_uleb128 (lto_fd *fd)
 
 /* Read an initial length field from FD.  The length may be a 32-bit
    or 64-bit quantity, depending on whether 32-bit or 64-bit DWARF is
-   in use, so the value returned is always a 64-bit value.  */
+   in use, so the value returned is always a 64-bit value.
+   Set FIELD_SIZE to how long the initial length field was.  */
 static uint64_t
-lto_read_initial_length (lto_fd *fd)
+lto_read_initial_length (lto_fd *fd, unsigned int *field_size)
 {
   /* The length of the debugging information section, as indicated in
      the DWARF information itself.  We use a 64-bit value so that we
@@ -301,6 +352,7 @@ lto_read_initial_length (lto_fd *fd)
   length = lto_read_uword (fd);
   if (length == 0xffffffff) 
     {
+      *field_size = sizeof (uint32_t) + sizeof (uint64_t);
       /* 64-bit DWARF.  */
       fd->dwarf64 = true;
       /* The "dwarf2.h" header used by GCC does not declare 64-bit
@@ -311,6 +363,8 @@ lto_read_initial_length (lto_fd *fd)
     /* An extension to DWARF that we do not support.  */
     fatal_error ("link-time optimization does not support DWARF extension "
 		 HOST_WIDEST_INT_PRINT_UNSIGNED, length);
+  else
+    *field_size = sizeof (uint32_t);
   
   return length;
 }
@@ -457,20 +511,64 @@ lto_read_section_offset (lto_fd *fd)
    header in *CU.  */
 static void
 lto_read_comp_unit_header (lto_fd *fd, 
-			   DWARF2_Internal_CompUnit *cu)
+			   DWARF2_CompUnit *cu)
 {
-  cu->cu_length = lto_read_initial_length (fd);
+  unsigned int length_field_size;
+  
+  /* The cu length is the length of the compilation unit, *not*
+     including the length field.  Since the length field can be 4 or
+     12 bytes, and *our* cu_length is specified to *include* the
+     length field, we have to account for this.  */
+  cu->cu_length = lto_read_initial_length (fd, &length_field_size);
+  cu->cu_length += length_field_size;
   cu->cu_version = lto_read_uhalf (fd);
   cu->cu_abbrev_offset = lto_read_section_offset (fd);
   cu->cu_pointer_size = lto_read_ubyte (fd);
 }
 
+/* Find the compilation unit in FD that contains the DWARF2 DIE
+   at OFFSET from the beginning of .debug_info.  */
+static DWARF2_CompUnit *
+find_cu_for_offset (const lto_info_fd *fd,
+		    unsigned long offset)
+{
+  unsigned int len = fd->num_units;
+  unsigned int half, middle;
+  unsigned int first = 0;
+
+  while (len > 0)
+    {
+      DWARF2_CompUnit *middle_elem;
+
+      half = len >> 1;
+      middle = first;
+      middle += half;
+      middle_elem = fd->units[middle];
+      if (middle_elem->cu_start_offset < offset)
+	{
+	  first = middle;
+	  ++first;
+	  len = len - half - 1;
+	}
+      else
+	len = half;
+    }
+
+  /* The above calculation will give us the first place *after* the cu
+     we want.  So just subtract 1.  */
+  
+  gcc_assert (first > 0);
+  
+  return fd->units[first - 1];
+}
+
 /* Read the value of the attribute ATTR from FD.  CONTEXT is as for
    the DIE readers.  Upon return, *OUT contains the data read.  */
 static void
 lto_read_form (lto_fd *fd, 
 	       const DWARF2_attr *attr, 
-	       const lto_context *context,
+	       lto_context *context,
+	       lto_context **form_context,
 	       DWARF2_form_data *out)
 {
   /* The Nth element in this array specifies (as a bitmask) the
@@ -691,6 +789,45 @@ lto_read_form (lto_fd *fd, 
       out->u.flag = (lto_read_ubyte (fd) != 0);
       break;
 
+    case DW_FORM_ref_addr:
+      {
+	uint64_t offset;
+	DWARF2_CompUnit *cu;
+
+	/* The standard says 
+	   "In the 32-bit DWARF format, this offset is a 4-byte unsigned
+	   value; in the 64-bit DWARF format, it is an 8-byte unsigned
+	   value"
+	*/
+	if (!fd->dwarf64)
+	  offset = lto_read_uword (fd);
+	else
+	  offset = lto_read_udword (fd);
+	
+	cu = find_cu_for_offset (context->info_fd,
+				 offset);
+
+	/* Swap context if necessary.  */
+	if (cu != context->current_cu)
+	  {
+	    lto_context *new_context = XCNEW (lto_context);
+	    
+	    *new_context = *context;
+	    
+	    lto_set_cu_context (new_context, fd,
+				cu);
+	    *form_context = new_context;
+	  }
+
+	out->cl = DW_cl_reference;
+	out->u.reference 
+	  = ((*form_context)->cu_start 
+	     + lto_check_size_t_val (offset, "offset too large"));
+	if (out->u.reference >= (*form_context)->cu_end)
+	  lto_file_corrupt_error (fd);
+      }
+      break;
+
     case DW_FORM_ref1:
     case DW_FORM_ref2:
     case DW_FORM_ref4:
@@ -851,15 +988,24 @@ lto_read_form (lto_fd *fd, 
 	 attr != abbrev->attrs + abbrev->num_attrs;	\
 	 ++attr)					\
       {							\
+	lto_context *old_context = context;		\
+	lto_context *new_context = context;		\
 	DWARF2_form_data attr_data;			\
-        lto_read_form (fd, attr, context, &attr_data);	\
+							\
+        lto_read_form (fd, attr, context, &new_context, \
+		       &attr_data);			\
+	if (context != new_context)			\
+	  context = new_context;			\
 	switch (attr->name)				\
 	  {						\
           case DW_AT_sibling:				\
             break; 
 
 /* Like LTO_BEGIN_READ_ATTRS_UNCHECKED, except that unhandled
-   attribute are treated as indicating a corrupt object file.  */
+   attribute are treated as indicating a corrupt object file.  
+
+   NB: The lto_context may change depending on the form, so be careful
+   when falling through to another attr name.  */
 #define LTO_BEGIN_READ_ATTRS()			\
   LTO_BEGIN_READ_ATTRS_UNCHECKED()		\
     default:					\
@@ -869,7 +1015,12 @@ lto_read_form (lto_fd *fd, 
 /* Macro to create the end of a loop for reading attributes from a
    DIE.  */
 #define LTO_END_READ_ATTRS()			\
-	  }					\
+         }					\
+  if (context != old_context)			\
+    {						\
+      XDELETE (context);			\
+      context = old_context;			\
+    }						\
       }						\
   } while (false)
 
@@ -1289,32 +1440,108 @@ lto_read_child_DIEs (lto_fd *fd, 
     }
 }
 
+/* Read all the DWARF2 compile units from INFO_FD, placing them in
+   INFO_FD->UNITS.  */
+static void
+lto_info_read (lto_info_fd *info_fd)
+{
+  size_t num_units;
+  lto_fd *fd;
+  unsigned long offset;
+  size_t current_unit;
+
+  /* We should only read the abbreviations once.  */
+  gcc_assert (!info_fd->units);
+  fd = (lto_fd *)info_fd;
+
+  /* Start reading from the beginning of the section.  */
+  fd->cur = fd->start;
+
+  num_units = 0;
+
+  /* Get the number of compilation units.  */
+  while (fd->cur < fd->end)
+    {
+      /* The compilation-unit header.  */ 
+      DWARF2_CompUnit cu;
+      const char *before_header = fd->cur;
+      
+      /* Read the compilation unit header.  */
+      lto_read_comp_unit_header (fd, &cu);
+
+      fd->cur = before_header + cu.cu_length;
+      num_units++;
+    }
+ 
+  info_fd->num_units = num_units;
+  info_fd->units = XCNEWVEC (DWARF2_CompUnit *, num_units);
+
+  /* Now read the actual compilation units.  */
+  fd->cur = fd->start;
+  offset = 0;
+  current_unit = 0;
+
+  /* Read the compilation units.  */
+  while (fd->cur < fd->end)
+    {
+      const char *before_header = fd->cur;
+      unsigned long header_length;
+      DWARF2_CompUnit *cu;
+
+      cu = XCNEW (DWARF2_CompUnit);
+      info_fd->units[current_unit] = cu;
+
+      /* Read the compilation unit header.  */
+      lto_read_comp_unit_header (fd, cu);
+          
+      header_length = fd->cur - before_header;
+      cu->cu_start_offset = offset + header_length;
+      cu->cu_header_length = header_length;
+
+      fd->cur = before_header + cu->cu_length;
+      offset = fd->cur - fd->start;
+      current_unit++;
+    }
+}
+
+/* Setup compile unit fields in CONTEXT from FD and UNIT */
+static void
+lto_set_cu_context (lto_context *context, lto_fd *fd,
+		    DWARF2_CompUnit *unit)
+{
+  context->cu_start = fd->start;
+  context->cu_end = fd->start + unit->cu_length;
+  context->current_cu = unit;
+}
+
 bool
 lto_file_read (lto_file *file)
 {
+  size_t i;
   /* The descriptor for the .debug_info section.  */
   lto_fd *fd;
 
   /* Read the abbreviation entries.  */
   lto_abbrev_read (&file->debug_abbrev);
-  
-  /* Start reading from the beginning of the section.  */
-  fd = &file->debug_info;
-  fd->cur = fd->start;
+  /* Read the compilation units.  */
+  lto_info_read (&file->debug_info);
 
-  /* Read compilation units until there are no more.  */
-  while (fd->cur < fd->end)
+  fd = &file->debug_info.base;
+
+  for (i = 0; i < file->debug_info.num_units; i++)
     {
-      /* The compilation-unit header.  */ 
-      DWARF2_Internal_CompUnit cu;
+      /* The current compilation unit.  */
+      DWARF2_CompUnit *unit = file->debug_info.units[i];
       /* The context information for this compilation unit.  */
       lto_context context;
-      /* Read the compilation unit header.  */
-      context.cu_start = fd->cur;
-      lto_read_comp_unit_header (fd, &cu);
-      context.cu_end = context.cu_start + cu.cu_length;
+
+      /* Set up the context.  */
+      lto_set_cu_context (&context, fd, unit);
+      context.info_fd = &file->debug_info;
+      fd->cur = context.cu_start + unit->cu_header_length;
       context.scope = NULL_TREE;
       context.type = NULL_TREE;
+
       /* Read DIEs.  */
       while (fd->cur < context.cu_end)
 	lto_read_DIE (fd, &context);
@@ -1336,7 +1563,7 @@ lto_main (int debug_p ATTRIBUTE_UNUSED)
       file = lto_elf_file_open (in_fnames[i]);
       if (!file)
 	break;
-      gcc_assert (file->debug_info.start);
+      gcc_assert (file->debug_info.base.start);
       gcc_assert (file->debug_abbrev.base.start);
       if (!lto_file_read (file))
 	break;
Index: lto/lto-elf.c
===================================================================
--- lto/lto-elf.c	(revision 115124)
+++ lto/lto-elf.c	(working copy)
@@ -196,7 +196,7 @@ lto_elf_file_open (const char *filename)
       
       /* Check to see if this is one of the sections of interest.  */
       if (strcmp (name, ".debug_info") == 0)
-	fd = &result->debug_info;
+	fd = (lto_fd *) &result->debug_info;
       else if (strcmp (name, ".debug_abbrev") == 0)
 	fd = (lto_fd *) &result->debug_abbrev;
       else
@@ -221,7 +221,7 @@ lto_elf_file_open (const char *filename)
       fd->end = fd->start + data->d_size;
     }
 
-  if (!result->debug_info.start 
+  if (!((lto_fd *) (&result->debug_info))->start
       || !((lto_fd *) (&result->debug_abbrev))->start)
     {
       error ("could not read DWARF debugging information");
Index: lto/lto.h
===================================================================
--- lto/lto.h	(revision 115124)
+++ lto/lto.h	(working copy)
@@ -26,6 +26,7 @@ Boston, MA 02110-1301, USA.  */
 
 typedef struct lto_file lto_file;
 typedef struct DWARF2_abbrev DWARF2_abbrev;
+typedef struct DWARF2_CompUnit DWARF2_CompUnit;
 
 /* Types */
 
@@ -46,6 +47,17 @@ typedef struct lto_fd
   bool dwarf64;
 } lto_fd;
 
+/* A file descriptor for reading from a DWARF information section. */
+typedef struct lto_info_fd
+{
+  /* The base object.  */
+  lto_fd base;
+  /* The number of compilation units in this section.  */
+  size_t num_units;
+  /* The compilation units themselves.  */
+  DWARF2_CompUnit **units;
+} lto_info_fd;
+
 /* A file descriptor for reading from a DWARF abbreviation section.  */
 typedef struct lto_abbrev_fd
 {
@@ -63,7 +75,7 @@ struct lto_file
   /* The name of the file.  */
   const char *filename;
   /* The contents of the .debug_info section.  */
-  lto_fd debug_info;
+  lto_info_fd debug_info;
   /* The contents of the .debug_abbrev section.  */
   lto_abbrev_fd debug_abbrev;
 };

Attachment: multicu.o
Description: application/object