From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 37528 invoked by alias); 6 Jan 2020 16:09:37 -0000 Mailing-List: contact dwz-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Post: List-Help: List-Subscribe: Sender: dwz-owner@sourceware.org Received: (qmail 37519 invoked by uid 89); 6 Jan 2020 16:09:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Checked: by ClamAV 0.100.3 on sourceware.org X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.2 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 spammy= X-Spam-Status: No, score=-25.2 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,SPF_PASS autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on sourceware.org X-Spam-Level: X-HELO: mx2.suse.de X-Virus-Scanned: by amavisd-new at test-mx.suse.de Date: Wed, 01 Jan 2020 00:00:00 -0000 From: Tom de Vries To: dwz@sourceware.org, jakub@redhat.com Subject: [committed 7/13][odr] Combine decls duplicate chain with def duplicate chain Message-ID: <20200106160930.GA19985@delia> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.10.1 (2018-07-13) X-SW-Source: 2020-q1/txt/msg00007.txt Hi, Add an optimization mode ODR_LINK in which we combine the decl chain with one of the defs chains. The duplicate chain containing the decls, combined with one type of def cannot be handled by the backend if it starts with a decl. So, we reorder it to make sure it doesn't start with a decl. We do this reordering ALAP, because the order of the duplicate chain is required to be in increasing die_cu (die)->cu_chunk order starting from the qsort in partition_dups (which sorts the array with duplicate chains into equivalence classes with the same set of referrer CUs) up until the outer loops of partition_dups_1 (which determine the equivalence class boundaries in the array with duplicate chains). Committed to trunk. Thanks, - Tom [odr] Combine decls duplicate chain with def duplicate chain 2020-01-06 Tom de Vries * dwz.c (enum odr_mode): New enum. (merge_dups): New function. (split_dups): Call merge_dups if odr_mode != ODR_BASIC. (reorder_dups): New function. (partition_dups_1): Call reorder_dups if odr_mode != ODR_BASIC. --- dwz.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 140 insertions(+), 3 deletions(-) diff --git a/dwz.c b/dwz.c index 9684adc..661cdb0 100644 --- a/dwz.c +++ b/dwz.c @@ -214,6 +214,8 @@ enum die_count_methods static enum die_count_methods die_count_method = estimate; int odr = 0; +enum odr_mode { ODR_BASIC, ODR_LINK }; +enum odr_mode odr_mode = ODR_LINK; typedef struct { @@ -6234,9 +6236,67 @@ sort_dups (dw_die_ref head) head->die_nextdup = prev; } +/* Merge duplicate chains D and D2, and return the head of the merged +chain. */ +static dw_die_ref +merge_dups (dw_die_ref d, dw_die_ref d2) +{ + if (d == NULL) + return d2; + if (d2 == NULL) + return d; + + dw_die_ref tail = NULL; + dw_die_ref head = NULL; + while (true) + { + dw_die_ref next; + if (d && d2) + { + if (d->die_offset < d2->die_offset) + { + next = d; + d = d->die_nextdup; + } + else + { + next = d2; + d2 = d2->die_nextdup; + } + } + else if (d) + { + next = d; + d = d->die_nextdup; + } + else if (d2) + { + next = d2; + d2 = d2->die_nextdup; + } + else + break; + if (!head) + head = next; + if (tail) + tail->die_nextdup = next; + tail = next; + } + + for (d = head; d; d = d->die_nextdup) + if (d == head) + d->die_dup = NULL; + else + d->die_dup = head; + + if (unlikely (verify_dups_p)) + verify_dups (head, true); + return head; +} + /* Split maximal duplicate chain DIE into smaller chains that contain - structurally equal defs. Return the first chain, and call - partition_found_dups for the others. */ + structurally equal defs, and combine the decls with one of those. + Return the first chain, and call partition_found_dups for the others. */ static dw_die_ref split_dups (dw_die_ref die, struct obstack *vec) { @@ -6277,6 +6337,7 @@ split_dups (dw_die_ref die, struct obstack *vec) d->die_dup = head; tail = d; } + dw_die_ref decls = head; /* Build def duplicate chains. */ unsigned int j; @@ -6299,6 +6360,24 @@ split_dups (dw_die_ref die, struct obstack *vec) sort_dups (d); } + if (odr_mode != ODR_BASIC) + { + /* Find the first duplicate chain containing defs. */ + dw_die_ref def = NULL; + for (i = 0; i < count; i++) + { + d = arr[i]; + if (die_odr_state (NULL, d) == ODR_DECL + || d->die_dup != NULL) + continue; + def = d; + break; + } + + /* Merge the def chain with the decls. */ + merge_dups (def, decls); + } + /* If some DIEs are no longer part of a duplicate chain, don't remove them. */ for (i = 0; i < count; i++) @@ -6358,6 +6437,62 @@ partition_find_dups (struct obstack *vec, dw_die_ref parent) } } +/* Reorder duplicate chain DIE to make sure it doesn't start with a decl. */ +static dw_die_ref +reorder_dups (dw_die_ref die) +{ + unsigned decl_count = 0; + unsigned def_count = 0; + dw_die_ref d; + + if (die_odr_state (NULL, die) == ODR_NONE) + return die; + + for (d = die; d; d = d->die_nextdup) + { + if (die_odr_state (NULL, d) == ODR_DECL) + decl_count++; + else + def_count++; + } + if (def_count == 0 || decl_count == 0) + return die; + + if (die_odr_state (NULL, die) != ODR_DECL) + return die; + + dw_die_ref def = NULL; + dw_die_ref prev = NULL; + for (d = die; d; prev = d, d = d->die_nextdup) + { + if (die_odr_state (NULL, d) == ODR_DECL) + continue; + def = d; + break; + } + + assert (!die->die_remove); + assert (def->die_remove); + def->die_remove = 0; + die->die_remove = 1; + def->die_ref_seen = die->die_ref_seen; + dw_die_ref next = def->die_nextdup; + if (prev) + prev->die_nextdup = next; + def->die_nextdup = die; + for (d = def; d; prev = d, d = d->die_nextdup) + { + if (d == def) + d->die_dup = NULL; + else + d->die_dup = def; + } + + if (unlikely (verify_dups_p)) + verify_dups (def, false); + return def; +} + /* Copy DIE tree of DIE, as children of new DIE PARENT. */ static dw_die_ref copy_die_tree (dw_die_ref parent, dw_die_ref die) @@ -6565,11 +6700,13 @@ partition_dups_1 (dw_die_ref *arr, size_t vec_size, dw_die_ref child; if (second_phase && !arr[k]->die_ref_seen) continue; + if (odr && odr_mode != ODR_BASIC) + arr[k] = reorder_dups (arr[k]); child = copy_die_tree (die, arr[k]); for (ref = arr[k]->die_nextdup; ref; ref = ref->die_nextdup) ref->die_dup = child; if (unlikely (verify_dups_p)) - verify_dups (child, true); + verify_dups (child, odr_mode == ODR_BASIC); if (namespaces) { for (ref = arr[k]->die_parent;