From 72dd050adedc5652d58794b24f498f0ffcf485e6 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Sun, 1 Mar 1998 17:09:39 +0000 Subject: [PATCH] frame.c (start_fde_sort, [...]): New functions for fast sorting of an FDE array. * frame.c (start_fde_sort, fde_split, heapsort, fde_merge, end_fde_sort): New functions for fast sorting of an FDE array. (fde_insert): Simplified. (add_fdes): Change argument list. (frame_init): Use the new functions. From-SVN: r18345 --- gcc/ChangeLog | 8 +++ gcc/frame.c | 197 +++++++++++++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 183 insertions(+), 22 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 549fc26..de994e8 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +Sun Feb 22 16:23:46 1998 Bruno Haible + + * frame.c (start_fde_sort, fde_split, heapsort, fde_merge, + end_fde_sort): New functions for fast sorting of an FDE array. + (fde_insert): Simplified. + (add_fdes): Change argument list. + (frame_init): Use the new functions. + Sun Mar 1 18:06:21 1998 Jeffrey A Law (law@cygnus.com) * i386.c (reg_mentioned_in_mem): Fix dangling else statement. diff --git a/gcc/frame.c b/gcc/frame.c index a875498..4c38721 100644 --- a/gcc/frame.c +++ b/gcc/frame.c @@ -191,24 +191,182 @@ next_fde (fde *p) return (fde *)(((char *)p) + p->length + sizeof (p->length)); } -/* One iteration of an insertion sort, for adding new FDEs to the array. - Usually the new FDE will go in at the end, so we can expect close to - O(n) performance. If this turns out to be overly optimistic, we can have - the linker sort the FDEs so we don't have to do it at run time. */ +/* Sorting an array of FDEs by address. + (Ideally we would have the linker sort the FDEs so we don't have to do + it at run time. But the linkers are not yet prepared for this.) */ + +/* This is a special mix of insertion sort and heap sort, optimized for + the data sets that actually occur. They look like + 101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130. + I.e. a linearly increasing sequence (coming from functions in the text + section), with additionally a few unordered elements (coming from functions + in gnu_linkonce sections) whose values are higher than the values in the + surrounding linear sequence (but not necessarily higher than the values + at the end of the linear sequence!). + The worst-case total run time is O(N) + O(n log (n)), where N is the + total number of FDEs and n is the number of erratic ones. */ + +typedef struct fde_vector +{ + fde **array; + size_t count; +} fde_vector; + +typedef struct fde_accumulator +{ + fde_vector linear; + fde_vector erratic; +} fde_accumulator; + +static inline void +start_fde_sort (fde_accumulator *accu, size_t count) +{ + accu->linear.array = (fde **) malloc (sizeof (fde *) * count); + accu->erratic.array = (fde **) malloc (sizeof (fde *) * count); + accu->linear.count = 0; + accu->erratic.count = 0; +} +static inline void +fde_insert (fde_accumulator *accu, fde *this_fde) +{ + accu->linear.array[accu->linear.count++] = this_fde; +} + +/* Split LINEAR into a linear sequence with low values and an erratic + sequence with high values, put the linear one (of longest possible + length) into LINEAR and the erratic one into ERRATIC. This is O(N). */ +static inline void +fde_split (fde_vector *linear, fde_vector *erratic) +{ + size_t count = linear->count; + size_t linear_max = (size_t) -1; + size_t previous_max[count]; + size_t i, j; + + for (i = 0; i < count; i++) + { + for (j = linear_max; + j != (size_t) -1 + && fde_compare (linear->array[i], linear->array[j]) < 0; + j = previous_max[j]) + { + erratic->array[erratic->count++] = linear->array[j]; + linear->array[j] = (fde *) NULL; + } + previous_max[i] = j; + linear_max = i; + } + + for (i = 0, j = 0; i < count; i++) + if (linear->array[i] != (fde *) NULL) + linear->array[j++] = linear->array[i]; + linear->count = j; +} + +/* This is O(n log(n)). */ +static inline void +heapsort (fde_vector *erratic) +{ + /* For a description of this algorithm, see: + Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed., + p. 60-61. */ + fde ** a = erratic->array; + /* A portion of the array is called a "heap" if for all i>=0: + If i and 2i+1 are valid indices, then a[i] >= a[2i+1]. + If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */ +#define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0) + size_t n = erratic->count; + size_t m = n; + size_t i; + + while (m > 0) + { + /* Invariant: a[m..n-1] is a heap. */ + m--; + for (i = m; 2*i+1 < n; ) + { + if (2*i+2 < n + && fde_compare (a[2*i+2], a[2*i+1]) > 0 + && fde_compare (a[2*i+2], a[i]) > 0) + { + SWAP (a[i], a[2*i+2]); + i = 2*i+2; + } + else if (fde_compare (a[2*i+1], a[i]) > 0) + { + SWAP (a[i], a[2*i+1]); + i = 2*i+1; + } + else + break; + } + } + while (n > 1) + { + /* Invariant: a[0..n-1] is a heap. */ + n--; + SWAP (a[0], a[n]); + for (i = 0; 2*i+1 < n; ) + { + if (2*i+2 < n + && fde_compare (a[2*i+2], a[2*i+1]) > 0 + && fde_compare (a[2*i+2], a[i]) > 0) + { + SWAP (a[i], a[2*i+2]); + i = 2*i+2; + } + else if (fde_compare (a[2*i+1], a[i]) > 0) + { + SWAP (a[i], a[2*i+1]); + i = 2*i+1; + } + else + break; + } + } +#undef SWAP +} + +/* Merge V1 and V2, both sorted, and put the result into V1. */ static void -fde_insert (fde **array, size_t i, fde *this_fde) +fde_merge (fde_vector *v1, const fde_vector *v2) { - array[i] = this_fde; + size_t i1, i2; + fde * fde2; - for (; i > 0 && fde_compare (array[i], array[i-1]) < 0; --i) + i2 = v2->count; + if (i2 > 0) { - this_fde = array[i]; - array[i] = array[i-1]; - array[i-1] = this_fde; + i1 = v1->count; + do { + i2--; + fde2 = v2->array[i2]; + while (i1 > 0 && fde_compare (v1->array[i1-1], fde2) > 0) + { + v1->array[i1+i2] = v1->array[i1-1]; + i1--; + } + v1->array[i1+i2] = fde2; + } while (i2 > 0); + v1->count += v2->count; } } +static fde ** +end_fde_sort (fde_accumulator *accu, size_t count) +{ + if (accu->linear.count != count) + abort (); + fde_split (&accu->linear, &accu->erratic); + if (accu->linear.count + accu->erratic.count != count) + abort (); + heapsort (&accu->erratic); + fde_merge (&accu->linear, &accu->erratic); + free (accu->erratic.array); + return accu->linear.array; +} + static size_t count_fdes (fde *this_fde) { @@ -227,10 +385,8 @@ count_fdes (fde *this_fde) } static void -add_fdes (fde *this_fde, fde **array, size_t *i_ptr, - void **beg_ptr, void **end_ptr) +add_fdes (fde *this_fde, fde_accumulator *accu, void **beg_ptr, void **end_ptr) { - size_t i = *i_ptr; void *pc_begin = *beg_ptr; void *pc_end = *end_ptr; @@ -240,7 +396,7 @@ add_fdes (fde *this_fde, fde **array, size_t *i_ptr, if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0) continue; - fde_insert (array, i++, this_fde); + fde_insert (accu, this_fde); if (this_fde->pc_begin < pc_begin) pc_begin = this_fde->pc_begin; @@ -248,7 +404,6 @@ add_fdes (fde *this_fde, fde **array, size_t *i_ptr, pc_end = this_fde->pc_begin + this_fde->pc_range; } - *i_ptr = i; *beg_ptr = pc_begin; *end_ptr = pc_end; } @@ -260,9 +415,8 @@ add_fdes (fde *this_fde, fde **array, size_t *i_ptr, static void frame_init (struct object* ob) { - fde *this_fde; size_t count; - fde **array; + fde_accumulator accu; void *pc_begin, *pc_end; if (ob->fde_array) @@ -275,22 +429,21 @@ frame_init (struct object* ob) count = count_fdes (ob->fde_begin); ob->count = count; - array = (fde **) malloc (sizeof (fde *) * count); + start_fde_sort (&accu, count); pc_begin = (void*)(uaddr)-1; pc_end = 0; - count = 0; if (ob->fde_array) { fde **p = ob->fde_array; for (; *p; ++p) - add_fdes (*p, array, &count, &pc_begin, &pc_end); + add_fdes (*p, &accu, &pc_begin, &pc_end); } else - add_fdes (ob->fde_begin, array, &count, &pc_begin, &pc_end); + add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end); - ob->fde_array = array; + ob->fde_array = end_fde_sort (&accu, count); ob->pc_begin = pc_begin; ob->pc_end = pc_end; } -- 2.7.4