* dwarf2.c (struct line_sequence): New struct.

        (struct line_info_table): Add num_sequences, remove last_line,
        add sequences.
        (add_line_info): Add new sequences as necessary.
        (compare_sequences): New function.
        (sort_line_sequences): New function.
        (decode_line_info): Initialize new fields in line table.
        Call sort_line_sequences.
        (lookup_address_in_line_info_table): Binary search for proper
        sequence.

2 files changed, 185 insertions, 38 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index bce7915..cc33261 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,16 @@
+2009-12-31  Cary Coutant  <ccoutant@google.com>
+
+	* dwarf2.c (struct line_sequence): New struct.
+	(struct line_info_table): Add num_sequences, remove last_line,
+	add sequences.
+	(add_line_info): Add new sequences as necessary.
+	(compare_sequences): New function.
+	(sort_line_sequences): New function.
+	(decode_line_info): Initialize new fields in line table.
+	Call sort_line_sequences.
+	(lookup_address_in_line_info_table): Binary search for proper
+	sequence.
+
 2009-12-28  Daniel Gutson  <dgutson@codesourcery.com>
 
 	* elf32-arm.c (elf32_arm_final_link_relocate): limits
diff --git a/bfd/dwarf2.c b/bfd/dwarf2.c
index 98e8945..0e875a1 100644
--- a/bfd/dwarf2.c
+++ b/bfd/dwarf2.c
@@ -908,16 +908,24 @@ struct fileinfo
   unsigned int size;
 };
 
+struct line_sequence
+{
+  bfd_vma               low_pc;
+  struct line_sequence* prev_sequence;
+  struct line_info*     last_line;  /* Largest VMA.  */
+};
+
 struct line_info_table
 {
-  bfd* abfd;
-  unsigned int num_files;
-  unsigned int num_dirs;
-  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' */
+  bfd*                  abfd;
+  unsigned int          num_files;
+  unsigned int          num_dirs;
+  unsigned int          num_sequences;
+  char *                comp_dir;
+  char **               dirs;
+  struct fileinfo*      files;
+  struct line_sequence* sequences;
+  struct line_info*     lcl_head;   /* Local head; used in 'add_line_info'.  */
 };
 
 /* Remember some information about each function.  If the function is
@@ -981,6 +989,7 @@ add_line_info (struct line_info_table *table,
 	       int end_sequence)
 {
   bfd_size_type amt = sizeof (struct line_info);
+  struct line_sequence* seq = table->sequences;
   struct line_info* info = (struct line_info *) bfd_alloc (table->abfd, amt);
 
   /* Set member data of 'info'.  */
@@ -1008,28 +1017,39 @@ add_line_info (struct line_info_table *table,
        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
+     sub-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'.  */
 
-  if (table->last_line
-      && table->last_line->address == address
-      && table->last_line->end_sequence == end_sequence)
+  if (seq
+      && seq->last_line->address == address
+      && seq->last_line->end_sequence == end_sequence)
     {
       /* We only keep the last entry with the same address and end
 	 sequence.  See PR ld/4986.  */
-      if (table->lcl_head == table->last_line)
+      if (table->lcl_head == seq->last_line)
 	table->lcl_head = info;
-      info->prev_line = table->last_line->prev_line;
-      table->last_line = info;
+      info->prev_line = seq->last_line->prev_line;
+      seq->last_line = info;
+    }
+  else if (!seq || seq->last_line->end_sequence)
+    {
+      /* Start a new line sequence.  */
+      amt = sizeof (struct line_sequence);
+      seq = (struct line_sequence *) bfd_malloc (amt);
+      seq->low_pc = address;
+      seq->prev_sequence = table->sequences;
+      seq->last_line = info;
+      table->lcl_head = info;
+      table->sequences = seq;
+      table->num_sequences++;
     }
-  else if (!table->last_line
-      || new_line_sorts_after (info, table->last_line))
+  else if (new_line_sorts_after (info, seq->last_line))
     {
-      /* Normal case: add 'info' to the beginning of the list */
-      info->prev_line = table->last_line;
-      table->last_line = info;
+      /* Normal case: add 'info' to the beginning of the current sequence.  */
+      info->prev_line = seq->last_line;
+      seq->last_line = info;
 
       /* lcl_head: initialize to head a *possible* sequence at the end.  */
       if (!table->lcl_head)
@@ -1045,9 +1065,9 @@ add_line_info (struct line_info_table *table,
     }
   else
     {
-      /* Abnormal and hard: Neither 'last_line' nor 'lcl_head' are valid
-	 heads for 'info'.  Reset 'lcl_head'.  */
-      struct line_info* li2 = table->last_line; /* always non-NULL */
+      /* Abnormal and hard: Neither 'last_line' nor 'lcl_head'
+	 are valid heads for 'info'.  Reset 'lcl_head'.  */
+      struct line_info* li2 = seq->last_line; /* Always non-NULL.  */
       struct line_info* li1 = li2->prev_line;
 
       while (li1)
@@ -1062,6 +1082,8 @@ add_line_info (struct line_info_table *table,
       table->lcl_head = li2;
       info->prev_line = table->lcl_head->prev_line;
       table->lcl_head->prev_line = info;
+      if (address < seq->low_pc)
+        seq->low_pc = address;
     }
 }
 
@@ -1169,6 +1191,95 @@ arange_add (bfd *abfd, struct arange *first_arange, bfd_vma low_pc, bfd_vma high
   first_arange->next = arange;
 }
 
+/* Compare function for line sequences.  */
+
+static int
+compare_sequences (const void* a, const void* b)
+{
+  const struct line_sequence* seq1 = a;
+  const struct line_sequence* seq2 = b;
+
+  /* Sort by low_pc as the primary key.  */
+  if (seq1->low_pc < seq2->low_pc)
+    return -1;
+  if (seq1->low_pc > seq2->low_pc)
+    return 1;
+
+  /* If low_pc values are equal, sort in reverse order of
+     high_pc, so that the largest region comes first.  */
+  if (seq1->last_line->address < seq2->last_line->address)
+    return 1;
+  if (seq1->last_line->address > seq2->last_line->address)
+    return -1;
+
+  return 0;
+}
+
+/* Sort the line sequences for quick lookup.  */
+
+static void
+sort_line_sequences (struct line_info_table* table)
+{
+  bfd_size_type amt;
+  struct line_sequence* sequences;
+  struct line_sequence* seq;
+  unsigned int n = 0;
+  unsigned int num_sequences = table->num_sequences;
+  bfd_vma last_high_pc;
+
+  if (num_sequences == 0)
+    return;
+
+  /* Allocate space for an array of sequences.  */
+  amt = sizeof (struct line_sequence) * num_sequences;
+  sequences = (struct line_sequence *) bfd_alloc (table->abfd, amt);
+
+  /* Copy the linked list into the array, freeing the original nodes.  */
+  seq = table->sequences;
+  for (n = 0; n < num_sequences; n++)
+    {
+      struct line_sequence* last_seq = seq;
+
+      BFD_ASSERT (seq);
+      sequences[n].low_pc = seq->low_pc;
+      sequences[n].prev_sequence = NULL;
+      sequences[n].last_line = seq->last_line;
+      seq = seq->prev_sequence;
+      free (last_seq);
+    }
+  BFD_ASSERT (seq == NULL);
+
+  qsort (sequences, n, sizeof (struct line_sequence), compare_sequences);
+
+  /* Make the list binary-searchable by trimming overlapping entries
+     and removing nested entries.  */
+  num_sequences = 1;
+  last_high_pc = sequences[0].last_line->address;
+  for (n = 1; n < table->num_sequences; n++)
+    {
+      if (sequences[n].low_pc < last_high_pc)
+        {
+	  if (sequences[n].last_line->address <= last_high_pc)
+	    /* Skip nested entries.  */
+	    continue;
+
+	  /* Trim overlapping entries.  */
+	  sequences[n].low_pc = last_high_pc;
+        }
+      last_high_pc = sequences[n].last_line->address;
+      if (n > num_sequences)
+        {
+          /* Close up the gap.  */
+          sequences[num_sequences].low_pc = sequences[n].low_pc;
+          sequences[num_sequences].last_line = sequences[n].last_line;
+        }
+      num_sequences++;
+    }
+
+  table->sequences = sequences;
+  table->num_sequences = num_sequences;
+}
+
 /* Decode the line number information for UNIT.  */
 
 static struct line_info_table*
@@ -1200,8 +1311,9 @@ decode_line_info (struct comp_unit *unit, struct dwarf2_debug *stash)
   table->num_dirs = 0;
   table->dirs = NULL;
 
-  table->files = NULL;
-  table->last_line = NULL;
+  table->num_sequences = 0;
+  table->sequences = NULL;
+
   table->lcl_head = NULL;
 
   line_ptr = stash->dwarf_line_buffer + unit->line_offset;
@@ -1482,6 +1594,8 @@ decode_line_info (struct comp_unit *unit, struct dwarf2_debug *stash)
 	free (filename);
     }
 
+  sort_line_sequences (table);
+
   return table;
 }
 
@@ -1495,28 +1609,48 @@ lookup_address_in_line_info_table (struct line_info_table *table,
 				   const char **filename_ptr,
 				   unsigned int *linenumber_ptr)
 {
-  /* Note: table->last_line should be a descendingly sorted list. */
+  struct line_sequence *seq = NULL;
   struct line_info *each_line;
+  int low, high, mid;
+
+  /* Binary search the array of sequences.  */
+  low = 0;
+  high = table->num_sequences;
+  while (low < high)
+    {
+      mid = (low + high) / 2;
+      seq = &table->sequences[mid];
+      if (addr < seq->low_pc)
+	high = mid;
+      else if (addr >= seq->last_line->address)
+	low = mid + 1;
+      else
+	break;
+    }
 
-  for (each_line = table->last_line;
-       each_line;
-       each_line = each_line->prev_line)
-    if (addr >= each_line->address)
-      break;
-
-  if (each_line
-      && !(each_line->end_sequence || each_line == table->last_line))
+  if (seq && addr >= seq->low_pc && addr < seq->last_line->address)
     {
-      *filename_ptr = each_line->filename;
-      *linenumber_ptr = each_line->line;
-      return TRUE;
+      /* Note: seq->last_line should be a descendingly sorted list.  */
+      for (each_line = seq->last_line;
+           each_line;
+           each_line = each_line->prev_line)
+        if (addr >= each_line->address)
+          break;
+
+      if (each_line
+          && !(each_line->end_sequence || each_line == seq->last_line))
+        {
+          *filename_ptr = each_line->filename;
+          *linenumber_ptr = each_line->line;
+          return TRUE;
+        }
     }
 
   *filename_ptr = NULL;
   return FALSE;
 }
 
-/* Read in the .debug_ranges section for future reference */
+/* Read in the .debug_ranges section for future reference.  */
 
 static bfd_boolean
 read_debug_ranges (struct comp_unit *unit)