From patchwork Tue Mar 20 17:59:57 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sriraman Tallam X-Patchwork-Id: 147823 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id D7023B6F13 for ; Wed, 21 Mar 2012 05:00:35 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1332871236; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Received:To:Subject:Message-Id:Date: From:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=hQEBTnI iCyrP/lJNa7IkQOMh2D4=; b=EWnCxrAcdyua/uS7YP1WehAEPikHcO7fi3VBe9t errolcnHpbVDTKvw79zPDFZ/3d5WOFoSiMlqBgskS3Vm9/89ZfXAKv9+Ix7v812C 67N1h/xabqnu6R0nfqilDKBzRGTABNpoLsxMgRD6UtFJZEZSZ16/S1zYA9iRsAHq PElI= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:X-Google-DKIM-Signature:Received:Received:Received:Received:Received:To:Subject:Message-Id:Date:From:X-Gm-Message-State:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=BBsyC+X6bvMEPirgWijK6OpY2fOegweXpKwnAywjWibfA0506aU5DqOgVJ/Nwv pu5tZ7y7+EHzyu3s3lgTlqDYafNUDb4Lsd0Z1xkKJVwgeZzBFeF5QU6aFaIvBgpT CE+xy20lb/4F6hGP3oNVHLK77uHvBnOk11CDSKRYw2XVg=; Received: (qmail 16586 invoked by alias); 20 Mar 2012 18:00:25 -0000 Received: (qmail 16539 invoked by uid 22791); 20 Mar 2012 18:00:20 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_LOW, TW_CP, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-lpp01m010-f73.google.com (HELO mail-lpp01m010-f73.google.com) (209.85.215.73) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 20 Mar 2012 18:00:00 +0000 Received: by laah2 with SMTP id h2so18559laa.2 for ; Tue, 20 Mar 2012 10:59:58 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=to:subject:message-id:date:from:x-gm-message-state; bh=iaujoA2KKfI27/zDR05cMSyCgEr0eBFcNEbON2XA7IM=; b=ntLCxwWxAQqqNvq2y9hkkjhs/BrVSb/SGuUVvKuoELayUHe+6HDqd36i4g0UEFK0Bq 0G4hLgDjzUau3qQiAGM/E5BTJC44l3hPJYfN+TdREsdtDdrkHeamtWOeqYF0h6kG6D1V oDmHntlzCZI7jE/oszAEyLmrcDHclWHTZRv6953Zdhr5DwpjEIyPtm8+cKLbh5qO1qRI PW8TI5+9coC5spVmXTuohcHlLD4/UT230BgKlyr8Fecw7k9+lGogWSCZhyskV2noXGOk Ee7e8FADhFnx9PG0w13EB0K1zVV1J2gqE7iuXQuWRpkMd0fd07q34tl8k8tDF+FuqBbD xk1w== Received: by 10.14.199.133 with SMTP id x5mr227889een.7.1332266398619; Tue, 20 Mar 2012 10:59:58 -0700 (PDT) Received: by 10.14.199.133 with SMTP id x5mr227874een.7.1332266398530; Tue, 20 Mar 2012 10:59:58 -0700 (PDT) Received: from hpza10.eem.corp.google.com ([74.125.121.33]) by gmr-mx.google.com with ESMTPS id f5si1504753eeo.2.2012.03.20.10.59.58 (version=TLSv1/SSLv3 cipher=AES128-SHA); Tue, 20 Mar 2012 10:59:58 -0700 (PDT) Received: from azwildcat.mtv.corp.google.com (azwildcat.mtv.corp.google.com [172.18.110.231]) by hpza10.eem.corp.google.com (Postfix) with ESMTP id 0B79620004E; Tue, 20 Mar 2012 10:59:58 -0700 (PDT) Received: by azwildcat.mtv.corp.google.com (Postfix, from userid 69128) id 5ADCDB21CE; Tue, 20 Mar 2012 10:59:57 -0700 (PDT) To: reply@codereview.appspotmail.com, eraman@google.com, davidxl@google.com, gcc-patches@gcc.gnu.org Subject: [google][4.6] Bug fixes to function reordering linker plugin to handle local and comdat functions. (issue5851044) Message-Id: <20120320175957.5ADCDB21CE@azwildcat.mtv.corp.google.com> Date: Tue, 20 Mar 2012 10:59:57 -0700 (PDT) From: tmsriram@google.com (Sriraman Tallam) X-Gm-Message-State: ALoCoQlKBcanEvdEuBiL2iWlQs7NDt5bnxJM1duXfq1Nyu8CySweB4ckH9o+JL0oSV5DMRvC/oygIQJ5K5cxxL3GbdjjJo0mIYi08agJD1Asv1Nzfs6wmzKJH+ebql9bDaKajTnmH9mKFapNaTZcMG9HZemBEXr74UPukgdEUV1I29FwPE0VVqQ= X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org This patch fixes bugs in section_ordering linker plugin to correctly handle functions that are file local or comdat. Such functions could be defined more than once in different object files and can have the same name. The callgraph edge profiles should be attributed to the right local function. Also, comdat functions in the same group must be treated as one function. This linker plugin is only available in the google/gcc-4_6 branch. I am working on preparing a patch for trunk. * callgraph.h (push_mm_ptr): New function. (make_edge_list): Call push_mm_ptr for heap allocs. (make_mode): Ditto. (make_edge): Ditto. (section_type, comdat_group, next, group): Add new fields to struct Section_id. (make_section_id): Initialize new fields. Add new args. (parse_callgraph_section_contents): Add args. * function_reordering_plugin.c (claim_file_hook): Call push_mm_ptr. Fix call to parse_callgraph_section_contents. (all_symbols_read_hook): Call push_mm_ptr. Remove calls to free. * callgraph.c (mm_node): New struct. (push_mm_ptr): New function. (canonicalize_function_name): New function. (parse_callgraph_section_contents): Add args. Call canonicalize_function_name. (num_sections): New global. (NUM_SECTION_TYPES): New constant. (section_types): New constant. (section_priority): New constant. (map_section_name_to_index): Remove sections. Replace sections with section_types. Call canonicalize_function_name. Chain all created sections. Check for comdat sections and group them together. (write_out_node): Output sections into section_start and section_end chain. Handle comdats. (get_layout): Make new chains for each section type. Output each chain one by one into handles and shndx. Output all the sections created. (cleanup): Free all heap allocated objects tracked by mm_node_chain. --- This patch is available for review at http://codereview.appspot.com/5851044 Index: callgraph.h =================================================================== --- callgraph.h (revision 185543) +++ callgraph.h (working copy) @@ -1,6 +1,7 @@ /* Callgraph implementation. Copyright (C) 2011 Free Software Foundation, Inc. - Contributed by Sriraman Tallam (tmsriram@google.com). + Contributed by Sriraman Tallam (tmsriram@google.com) + and Easwaran Raman (eraman@google.com). This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -26,6 +27,9 @@ along with this program; see the file COPYING3. I #include #include "libiberty.h" +/* Push a pointer that should be freed after the plugin is done. */ +void push_mm_ptr (void *ptr); + struct edge_d; typedef struct edge_d Edge; @@ -41,6 +45,7 @@ inline static Edge_list * make_edge_list (Edge *e) { Edge_list *list = XNEW (Edge_list); + push_mm_ptr (list); list->edge = e; list->next = NULL; list->prev = NULL; @@ -69,6 +74,7 @@ inline static Node * make_node (unsigned int id, char *name) { Node *node = XNEW (Node); + push_mm_ptr (node); node->id = id; node->name = name; node->is_real_node = 0; @@ -86,9 +92,9 @@ make_node (unsigned int id, char *name) inline static void merge_node (Node *merger, Node *mergee) { - merger->last_merge_node->merge_next = mergee; - merger->last_merge_node = mergee->last_merge_node; - mergee->is_merged = 1; + merger->last_merge_node->merge_next = mergee; + merger->last_merge_node = mergee->last_merge_node; + mergee->is_merged = 1; } inline static void @@ -136,6 +142,7 @@ inline static Edge * make_edge (Node *first, Node *second, unsigned int weight) { Edge *edge = XNEW (Edge); + push_mm_ptr (edge); edge->first_function = first; edge->second_function = second; edge->weight = weight; @@ -148,21 +155,7 @@ make_edge (Node *first, Node *second, unsigned int return edge; } -/* Frees the chain of edges. */ inline static void -free_edge_chain (Edge *edge_chain) -{ - Edge *edge; - - for (edge = edge_chain; edge != NULL; ) - { - Edge *next_edge = edge->next; - free (edge); - edge = next_edge; - } -} - -inline static void set_edge_type (Edge *edge) { if (edge->first_function->is_real_node @@ -200,7 +193,7 @@ reset_functions (Edge *e, Node *n1, Node *n2) } /* A Section is represented by its object handle and the section index. */ -typedef struct +typedef struct section_id_ { /* Name of the function. */ char *name; @@ -208,16 +201,34 @@ reset_functions (Edge *e, Node *n1, Node *n2) char *full_name; void *handle; int shndx; + /* Type of prefix in section name. */ + int section_type; + /* Pointer to the next section in the same comdat_group. */ + struct section_id_ *comdat_group; + /* Chain all the sections created. */ + struct section_id_ *next; + /* Used for grouping sections. */ + struct section_id_ *group; + /* Check if this section has been considered for output. */ + char processed; } Section_id; inline static Section_id * -make_section_id (char *name, char *full_name, void *handle, int shndx) +make_section_id (char *name, char *full_name, + int section_type, + void *handle, int shndx) { Section_id *s = XNEW (Section_id); + push_mm_ptr (s); s->name = name; s->full_name = full_name; + s->section_type = section_type; s->handle = handle; s->shndx = shndx; + s->comdat_group = NULL; + s->next = NULL; + s->group = NULL; + s->processed = 0; return s; } @@ -256,8 +267,9 @@ void map_section_name_to_index (char *section_name, void *handle, int shndx); void -parse_callgraph_section_contents (unsigned char *section_contents, - unsigned int length); +parse_callgraph_section_contents (void *handle, + unsigned char *section_contents, + unsigned int length); void dump_functions (); void dump_edges (); Index: function_reordering_plugin.c =================================================================== --- function_reordering_plugin.c (revision 185543) +++ function_reordering_plugin.c (working copy) @@ -1,6 +1,7 @@ /* Function re-ordering plugin for gold. Copyright (C) 2011 Free Software Foundation, Inc. - Contributed by Sriraman Tallam (tmsriram@google.com). + Contributed by Sriraman Tallam (tmsriram@google.com) + and Easwaran Raman (eraman@google.com). This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -89,6 +90,7 @@ static int no_op = 0; void get_filename (const char *name) { out_file = (char *) malloc (strlen (name) + 1); + push_mm_ptr (out_file); strcpy (out_file, name); } @@ -230,6 +232,7 @@ claim_file_hook (const struct ld_plugin_input_file (*get_input_section_type) (section, &type); (*get_input_section_name) (section, &name); + push_mm_ptr (name); if (type == SHT_PROGBITS && is_prefix_of (".text.", name)) { map_section_name_to_index (name, file->handle, shndx); @@ -244,11 +247,12 @@ claim_file_hook (const struct ld_plugin_input_file &length); unsigned char *section_contents; section_contents = (unsigned char *) malloc (length); + push_mm_ptr (section_contents); memcpy (section_contents, section_contents_ptr, length); - parse_callgraph_section_contents (section_contents, (unsigned int)length); + parse_callgraph_section_contents (file->handle, + section_contents, + (unsigned int)length); } - else if (name != NULL) - free (name); } return LDPS_OK; @@ -290,6 +294,8 @@ all_symbols_read_hook (void) num_entries = get_layout (fp, &handles, &shndx); section_list = (struct ld_plugin_section *) malloc (num_entries * sizeof (struct ld_plugin_section)); + push_mm_ptr (section_list); + for (i = 0; i < num_entries; i++) { section_list[i].handle = handles[i]; @@ -301,9 +307,6 @@ all_symbols_read_hook (void) fclose (fp); /* Pass the new order of functions to the linker. */ update_section_order (section_list, num_entries); - free (section_list); - free (handles); - free (shndx); cleanup (); return LDPS_OK; } Index: callgraph.c =================================================================== --- callgraph.c (revision 185543) +++ callgraph.c (working copy) @@ -1,6 +1,7 @@ /* Callgraph implementation. Copyright (C) 2011 Free Software Foundation, Inc. - Contributed by Sriraman Tallam (tmsriram@google.com). + Contributed by Sriraman Tallam (tmsriram@google.com) + and Easwaran Raman (eraman@google.com). This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -110,6 +111,25 @@ edge_map_htab_eq_descriptor (const void *p1, const /*****************************************************************************/ + +/* Keep track of all allocated memory. */ +typedef struct +{ + void *ptr; + void *next; +} mm_node; + +mm_node *mm_node_chain = NULL; + +void +push_mm_ptr (void *ptr) +{ + mm_node *node = XNEW (mm_node); + node->ptr = ptr; + node->next = mm_node_chain; + mm_node_chain = node; +} + /* Chain of all the created nodes. */ Node *node_chain = NULL; /* Number of nodes that correspond to functions which will be reordered. */ @@ -275,9 +295,26 @@ void dump_edges (FILE *fp) } } -/* HEADER_LEN is the length of string 'Function '. */ -const int HEADER_LEN = 9; +/* For file local functions, append a unique identifier corresponding to + the file, FILE_HANDLE, to the NAME to keep the name unique. */ +static char * +canonicalize_function_name (void *file_handle, char *name) +{ + /* Number of hexadecimal digits in file_handle, plus length of "0x". */ + const int FILE_HANDLE_LEN = sizeof (void *) * 2 + 2; + char *canonical_name; + + /* File local functions have _ZL prefix in the mangled name. */ + if (!is_prefix_of ("_ZL", name)) + return name; + + canonical_name = (char *) malloc (strlen(name) + FILE_HANDLE_LEN + 2); + push_mm_ptr (canonical_name); + sprintf (canonical_name, "%s.%p", name, file_handle); + return canonical_name; +} + /* Parse the section contents of ".gnu.callgraph.text" sections and create call graph edges with appropriate weights. The section contents have the following format : @@ -288,7 +325,8 @@ void dump_edges (FILE *fp) .... */ void -parse_callgraph_section_contents (unsigned char *section_contents, +parse_callgraph_section_contents (void *file_handle, + unsigned char *section_contents, unsigned int length) { char *contents; @@ -296,12 +334,15 @@ void unsigned int read_length = 0, curr_length = 0; Node *caller_node; + /* HEADER_LEN is the length of string 'Function '. */ + const int HEADER_LEN = 9; + /* First string in contents is 'Function '. */ assert (length > 0); contents = (char*) (section_contents); caller = get_next_string (&contents, &read_length); assert (read_length > HEADER_LEN); - caller = caller + HEADER_LEN; + caller = canonicalize_function_name (file_handle, caller + HEADER_LEN); curr_length = read_length; caller_node = get_function_node (caller); @@ -314,6 +355,7 @@ void Node *callee_node; callee = get_next_string (&contents, &read_length); + callee = canonicalize_function_name (file_handle, callee); curr_length += read_length; callee_node = get_function_node (callee); @@ -456,6 +498,20 @@ find_pettis_hansen_function_layout (FILE *fp) } } +/* The list of sections created, excluding comdat duplicates. */ +Section_id *first_section = NULL; +/* The number of sections. */ +int num_sections = 0; + +const int NUM_SECTION_TYPES = 5; +const char *section_types[] = {".text.hot.", + ".text.cold.", + ".text.unlikely.", + ".text.startup.", + ".text." }; + +const int section_priority[] = {0, 3, 4, 2, 1}; + /* Maps the function name corresponding to section SECTION_NAME to the object handle and the section index. */ @@ -463,24 +519,23 @@ void map_section_name_to_index (char *section_name, void *handle, int shndx) { void **slot; - const char *sections[] = {".text.hot.", - ".text.unlikely.", - ".text.cold.", - ".text.startup.", - ".text." }; char *function_name = NULL; - int i; + int i, section_type = -1; - for (i = 0; i < ARRAY_SIZE (sections); ++i) + for (i = 0; i < ARRAY_SIZE (section_types); ++i) { - if (is_prefix_of (sections[i], section_name)) + if (is_prefix_of (section_types[i], section_name)) { - function_name = section_name + strlen (sections[i]); + function_name = section_name + strlen (section_types[i]); + section_type = i; break; } } - assert (function_name != NULL); + assert (function_name != NULL && section_type >= 0); + function_name = canonicalize_function_name (handle, function_name); + num_sections++; + /* Allocate section_map. */ if (section_map == NULL) { @@ -494,24 +549,67 @@ map_section_name_to_index (char *section_name, voi htab_hash_string (function_name), INSERT); if (*slot == NULL) - *slot = make_section_id (function_name, section_name, handle, shndx); + { + Section_id *section = make_section_id (function_name, section_name, + section_type, handle, shndx); + /* Chain it to the list of sections. */ + section->next = first_section; + first_section = section; + *slot = section; + } + else + { + /* The function already exists, it must be a COMDAT. Only one section + in the comdat group will be kept, we don't know which. Chain all the + comdat sections in the same comdat group to be emitted together later. + Keep one section as representative (kept) and update its section_type + to be equal to the type of the highest priority section in the + group. */ + Section_id *kept = (Section_id *)(*slot); + Section_id *section = make_section_id (function_name, section_name, + section_type, handle, shndx); + if (section_priority[kept->section_type] + > section_priority[section_type]) + kept->section_type = section_type; + + section->comdat_group = kept->comdat_group; + kept->comdat_group = section; + } } +/* Find the section corresponding to function name NAME. If it is a comdat, + get all the comdat sections in the group. Chain these sections to + SECTION_END. Set SECTION_START if it is NULL. */ + static void -write_out_node (FILE *fp, char *name, - void **handles, unsigned int *shndx, int position) +write_out_node (char *name, Section_id **section_start, + Section_id **section_end) { void *slot; slot = htab_find_with_hash (section_map, name, htab_hash_string (name)); if (slot != NULL) { Section_id *s = (Section_id *)slot; - handles[position] = s->handle; - shndx[position] = s->shndx; - if (fp != NULL) - fprintf (fp, "%s\n", s->full_name); - /* No more use of full_name */ - free (s->full_name); + s->processed = 1; + if (*section_start == NULL) + { + *section_start = s; + *section_end = s; + } + else + { + (*section_end)->group = s; + *section_end = s; + } + + /* Print all other sections in the same comdat group. */ + while (s->comdat_group) + { + s = s->comdat_group; + s->processed = 1; + (*section_end)->group = s; + *section_end = s; + } } } @@ -521,67 +619,95 @@ unsigned int get_layout (FILE *fp, void*** handles, unsigned int** shndx) { - Node *it; - int position = 0; + Node *n_it; + int i = 0; + int position; + /* Form NUM_SECTION_TYPES + 1 groups of sections. Index 0 corresponds + to the list of sections that correspond to functions in the callgraph. + For other sections, they are grouped by section_type and stored in + index: (section_type + 1). SECTION_START points to the first + section in each section group and SECTION_END points to the last. */ + Section_id *section_start[NUM_SECTION_TYPES + 1]; + Section_id *section_end[NUM_SECTION_TYPES + 1]; + Section_id *s_it; - *handles = XNEWVEC (void *, num_real_nodes); - *shndx = XNEWVEC (unsigned int, num_real_nodes); + *handles = XNEWVEC (void *, num_sections); + *shndx = XNEWVEC (unsigned int, num_sections); - /* Dump edges to the final reordering file. */ + push_mm_ptr (*handles); + push_mm_ptr (*shndx); - for (it = node_chain; it != NULL; it = it->next) + for (i = 0; i < NUM_SECTION_TYPES + 1; i++) { + section_start[i] = NULL; + section_end[i] = NULL; + } + + /* Dump edges to the final reordering file. */ + for (n_it = node_chain; n_it != NULL; n_it = n_it->next) + { Node *node; - if (it->is_merged) + /* First, only consider nodes that are real and that have other + nodes merged with it. */ + if (n_it->is_merged || !n_it->is_real_node || !n_it->merge_next) continue; - if (it->is_real_node) - { - write_out_node (fp, it->name, *handles, *shndx, position); - position++; - } - node = it->merge_next; + + write_out_node (n_it->name, §ion_start[0], §ion_end[0]); + node = n_it->merge_next; while (node != NULL) { if (node->is_real_node) - { - write_out_node (fp, node->name, *handles, *shndx, position); - position++; - } + write_out_node (node->name, §ion_start[0], §ion_end[0]); node = node->merge_next; } } + + /* Go through all the sections and sort unprocessed sections into different + section_type groups. */ + s_it = first_section; + while (s_it) + { + if (!s_it->processed) + { + write_out_node (s_it->name, §ion_start[s_it->section_type + 1], + §ion_end[s_it->section_type + 1]); + s_it->processed = 1; + } + s_it = s_it->next; + } + + + position = 0; + for (i=0; i < NUM_SECTION_TYPES + 1; i++) + { + s_it = section_start[i]; + while (s_it) + { + assert (position < num_sections); + (*handles)[position] = s_it->handle; + (*shndx)[position] = s_it->shndx; + position++; + if (fp != NULL) + fprintf (fp, "%s\n", s_it->full_name); + s_it = s_it->group; + } + } return position; } -/* Free all heap objects. */ - void cleanup () { - Node *node; - - /* Free all nodes and edge_lists. */ - for (node = node_chain; node != NULL; ) + /* Go through heap allocated objects and free them. */ + while (mm_node_chain) { - Node *next_node = node->next; - Edge_list *it; - for (it = node->edge_list; it != NULL; ) - { - Edge_list *next_it = it->next; - free (it); - it = next_it; - } + mm_node *node = mm_node_chain; + free (node->ptr); + mm_node_chain = node->next; free (node); - node = next_node; } - /* Free all active_edges. */ - free_edge_chain (active_edges); - - /* Free all inactive edges. */ - free_edge_chain (inactive_edges); - - /* Delete all htabs. */ + /* Delete all htabs. */ htab_delete (section_map); htab_delete (function_map); htab_delete (edge_map);