From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 53454 invoked by alias); 6 Dec 2019 10:34:55 -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 53443 invoked by uid 89); 6 Dec 2019 10:34:54 -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.1 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.1 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: mx1.suse.de X-Virus-Scanned: by amavisd-new at test-mx.suse.de Date: Tue, 01 Jan 2019 00:00:00 -0000 From: Tom de Vries To: dwz@sourceware.org, jakub@redhat.com Subject: [committed] Add transformation examples in create_import_tree Message-ID: <20191206103448.GA15505@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: 2019-q4/txt/msg00118.txt.bz2 Hi, Function create_import_tree creates a graph and then applies a few transformations to it. Add a schematic example for each transformation. Committed to trunk. Thanks, - Tom Add transformation examples in create_import_tree 2019-12-05 Tom de Vries * dwz.c (create_import_tree): Add transformation examples in comments. --- dwz.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 76 insertions(+), 5 deletions(-) diff --git a/dwz.c b/dwz.c index 1c1ae93..313c317 100644 --- a/dwz.c +++ b/dwz.c @@ -6826,7 +6826,34 @@ create_import_tree (void) ptr_size 8 it can be even x == 4) and add a new PU node, where all CUs from the component will point to the new PU node and that new PU will point to all the destination PUs. In theory with DWARF2 - and ptr_size 1 we could need x >= 9. */ + and ptr_size 1 we could need x >= 9. + + The example below demonstrates the type of transformation. The + transformation is an optimization if the benefit of reducing the number + of imports (in other words, edges) is bigger than the cost of adding an + extra PU. OTOH, the transformation can be done in the presence of + additional incoming edges for PU_3 and PU_4. + + Before: After: + + CU_1---------->PU_3 CU_1 PU_3 + \ ^ ^ \ ^ + \ / / \ / + \ / / \ / + x----o / \ / + / \ / \ / + / \ / \ / + / \ / v / + CU_2 x CU_2----->PU_5 + \ / \ ^ \ + \ / \ / \ + \ / \ / \ + x----o \ / \ + / \ \ / \ + / \ \ / \ + / v v / v + CU_3---------->PU_4 CU_3 PU_4 + */ for (i = 0; i < npus - 1; i++) { struct import_cu *pudst[2], *pusrc[10]; @@ -6984,10 +7011,54 @@ create_import_tree (void) if (unlikely (verify_edges_p)) verify_edges (ipus, npus, ncus, 2); /* Try to merge PUs which have the same set of referrers if - beneficial, or if one PU has a subset of referrers of the - other, attempt to replace all the incoming edges from the - referrers intersection to the PU with larger number of - incoming edges by an edge from the other PU. */ + beneficial. + + The example below demonstrates the type of transformation. The + transformation is an optimization because it reduces the number of import + statements (in other words, edges) as well as the number of PUs. It can + however not be done if PU_3 or PU_4 have additional incoming edges. + + Before: After: + + CU_1----->PU_3 CU_1 + \ ^ \ + \ / \ + \ / v + x PU_3_4 + / \ ^ + / \ / + / v / + CU_2----->PU_4 CU_2 + + Or, if one PU has a subset of referrers of the other, attempt to replace + all the incoming edges from the referrers intersection to the PU with + larger number of incoming edges by an edge from the other PU. + + The example below demonstrates the type of transformation. The + transformation is an optimization because it reduces the number of import + statements (in other words, edges). It can however not be done if PU_3 + has additional incoming edges. + + Before: After: + + CU_1----->PU_3 CU_1------>PU_3 + \ ^ ^ | + \ / / | + \ / / | + x / | + / \ / | + / \ / | + / \ / | + CU_2 \ CU_2 o + \ \ | + \ o | + \ | | + \ | | + \ | | + \ | | + v v v + CU_3----->PU_4 CU_3------>PU_4 + */ for (ipu = ipus[0]; ipu; ipu = ipu->next) { struct import_edge *e1, *e2, *e3, *e4, **e1p, **ep;