linkonce and exceptions on Solaris

[Martin von Loewis]

When I run a g++ 2.8 compiled image on Solaris, exception handling may
consume a lot of computing power. In one particular case, I have an
image which has 9MB of text size. Throwing the first exception will
take about 10 seconds on an UltraSparc 1.

When analysing this, I found that these 10 seconds are spend inside
add_fdes. So I checked the size of the eh_frame section:

size protocol
text    data    bss     dec     hex     filename
8908320 2110138 170200  11188658        aab9b2  solarisg/protocol

objdump --headers solarisg/protocol |grep eh_frame
SECTION 13 [.eh_frame]  : size 0010dddc vma 009937c0 align 2**3

Next, I modified fde_insert to count various things:

static void
fde_insert (fde **array, size_t i, fde *this_fde)
{
  int this_bubble=0;
  array[i] = this_fde;
  mvl_fde_count++;

  for (; i > 0 && fde_compare (array[i], array[i-1]) < 0; --i)
    {
      mvl_fde_bubble++;
      this_bubble++;
      this_fde = array[i];
      array[i] = array[i-1];
      array[i-1] = this_fde;
    }
  if(this_bubble>mvl_fde_bubble_max)
    mvl_fde_bubble_max = this_bubble;
}

For this image, I got the following results:
Total number of FDEs:                 33618
Total number of bubble operations: 26896088
Maximum offset to move one FDE:        2469

So it seems that the bubble sort is the expensive operation
here. The assumption of O(n) is apparently broken.

When investigating this, I found that the out-of-order FDEs come from
gnu.linkonce sections. All linkonce functions are after all regular
functions, but their FDEs are spread all over the place. As more an
more of these FDEs are added, inserting regular FDEs will get more and
more expensive.

This happens with both the GNU linker (2.8.2) as well as
/usr/ccs/bin/ld, although GNU ld behaves somewhat better.

I know I can get rid of the linkonce by saying -fno-weak, but the
resulting code size would not be acceptable.

Are there any proposals which I could try?

Short of that, I can propose two possible solutions:

1. The heuristics 'insert at the end' is bad. I found that a better
heuristics would be 'insert one after the previous one'.

2. Add the FDEs in two passes. Both the regular FDEs, and the linked
once FDEs appear to be in order, on their own. So if there is a symbol
saying where the linked-once sections start, one can add all regular
entries in the first pass (skipping everything above this symbol), and
the linked onces in the second pass. This might get you back to O(n).

Please comment.

Martin