Patchwork Maintain order of LTO sections

login
register
mail settings
Submitter Andi Kleen
Date Oct. 3, 2011, 6:06 a.m.
Message ID <1317621974-4689-1-git-send-email-andi@firstfloor.org>
Download mbox | patch
Permalink /patch/117403/
State New
Headers show

Comments

Andi Kleen - Oct. 3, 2011, 6:06 a.m.
From: Andi Kleen <ak@linux.intel.com>

Currently when reading in LTO sections from ld -r files they can
get randomly reordered based on hash tables and random IDs.
This causes reordering later when the final code is generated and
also makes crashes harder to reproduce.

This patch maintains explicit lists based on the input order and uses
those lists to preserve that order when starting the rest of the
LTO passes.

This is the first step to working -fno-toplevel-reorder for
LTO. But this needs more changes because the LTO partitioner
can still reorder.

This add two lists: one for the section and another one for
the file_decl_datas. This is needed because the sections are
walked twice through different data structures.

In addition some code becomes slightly cleaner because we don't need
to pass state through abstract callbacks anymore, but
can just use direct type safe calls.

Passes LTO bootstrap and testsuite on x86_64-linux. Ok?

gcc/lto/:

2011-10-02   Andi Kleen <ak@linux.intel.com>

	* lto-object.c (lto_obj_add_section_data): Add list.
	(lto_obj_add_section): Fill in list.
	(ltoobj_build_section_table): Pass through list.
	* lto.c (file_data_list): Declare.
	(create_subid_section_table): Pass arguments directly.
	Fill in list of file_datas.
	(lwstate): Delete.
	(lto_create_files_from_ids): Pass in direct arguments.
	Don't maintain list.
	(lto_file_read): Use explicit section and file data lists.
	(lto_read_all_file_options): Pass in section_list.
	* lto.h (lto_obj_build_section_table): Add list.
	(lto_section_slot): Add next.
	(lto_section_list): Declare.
Jan Hubicka - Oct. 4, 2011, 10:17 a.m.
> From: Andi Kleen <ak@linux.intel.com>
> 
> Currently when reading in LTO sections from ld -r files they can
> get randomly reordered based on hash tables and random IDs.
> This causes reordering later when the final code is generated and
> also makes crashes harder to reproduce.
> 
> This patch maintains explicit lists based on the input order and uses
> those lists to preserve that order when starting the rest of the
> LTO passes.
> 
> This is the first step to working -fno-toplevel-reorder for
> LTO. But this needs more changes because the LTO partitioner
> can still reorder.
> 
> This add two lists: one for the section and another one for
> the file_decl_datas. This is needed because the sections are
> walked twice through different data structures.
> 
> In addition some code becomes slightly cleaner because we don't need
> to pass state through abstract callbacks anymore, but
> can just use direct type safe calls.
> 
> Passes LTO bootstrap and testsuite on x86_64-linux. Ok?

Note that this is also needed to make lto-symtab decisions consistent with linker
decisions. So it makes a lot of sense to me, but I can't approve it.
I was running into funny cases where things got resolved differently on
openoffice, so hopefully this will solve it.


Honza
> 
> gcc/lto/:
> 
> 2011-10-02   Andi Kleen <ak@linux.intel.com>
> 
> 	* lto-object.c (lto_obj_add_section_data): Add list.
> 	(lto_obj_add_section): Fill in list.
> 	(ltoobj_build_section_table): Pass through list.
> 	* lto.c (file_data_list): Declare.
> 	(create_subid_section_table): Pass arguments directly.
> 	Fill in list of file_datas.
> 	(lwstate): Delete.
> 	(lto_create_files_from_ids): Pass in direct arguments.
> 	Don't maintain list.
> 	(lto_file_read): Use explicit section and file data lists.
> 	(lto_read_all_file_options): Pass in section_list.
> 	* lto.h (lto_obj_build_section_table): Add list.
> 	(lto_section_slot): Add next.
> 	(lto_section_list): Declare.
> 
> diff --git a/gcc/lto/lto-object.c b/gcc/lto/lto-object.c
> index 3be58de..daf3bd0 100644
> --- a/gcc/lto/lto-object.c
> +++ b/gcc/lto/lto-object.c
> @@ -204,6 +204,8 @@ struct lto_obj_add_section_data
>    htab_t section_hash_table;
>    /* The offset of this file.  */
>    off_t base_offset;
> +  /* List in linker order */
> +  struct lto_section_list *list;
>  };
>  
>  /* This is called for each section in the file.  */
> @@ -218,6 +220,7 @@ lto_obj_add_section (void *data, const char *name, off_t offset,
>    char *new_name;
>    struct lto_section_slot s_slot;
>    void **slot;
> +  struct lto_section_list *list = loasd->list;
>  
>    if (strncmp (name, LTO_SECTION_NAME_PREFIX,
>  	       strlen (LTO_SECTION_NAME_PREFIX)) != 0)
> @@ -228,12 +231,21 @@ lto_obj_add_section (void *data, const char *name, off_t offset,
>    slot = htab_find_slot (section_hash_table, &s_slot, INSERT);
>    if (*slot == NULL)
>      {
> -      struct lto_section_slot *new_slot = XNEW (struct lto_section_slot);
> +      struct lto_section_slot *new_slot = XCNEW (struct lto_section_slot);
>  
>        new_slot->name = new_name;
>        new_slot->start = loasd->base_offset + offset;
>        new_slot->len = length;
>        *slot = new_slot;
> +
> +      if (list != NULL)
> +        {
> +          if (!list->first)
> +            list->first = new_slot;
> +          if (list->last)
> +            list->last->next = new_slot;
> +          list->last = new_slot;
> +        }
>      }
>    else
>      {
> @@ -248,7 +260,7 @@ lto_obj_add_section (void *data, const char *name, off_t offset,
>     the start and size of each section in the .o file.  */
>  
>  htab_t
> -lto_obj_build_section_table (lto_file *lto_file)
> +lto_obj_build_section_table (lto_file *lto_file, struct lto_section_list *list)
>  {
>    struct lto_simple_object *lo = (struct lto_simple_object *) lto_file;
>    htab_t section_hash_table;
> @@ -261,6 +273,7 @@ lto_obj_build_section_table (lto_file *lto_file)
>    gcc_assert (lo->sobj_r != NULL && lo->sobj_w == NULL);
>    loasd.section_hash_table = section_hash_table;
>    loasd.base_offset = lo->base.offset;
> +  loasd.list = list;
>    errmsg = simple_object_find_sections (lo->sobj_r, lto_obj_add_section,
>  					&loasd, &err);
>    if (errmsg != NULL)
> diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
> index 778e33e..a77eeb4 100644
> --- a/gcc/lto/lto.c
> +++ b/gcc/lto/lto.c
> @@ -1052,6 +1052,12 @@ lto_resolution_read (splay_tree file_ids, FILE *resolution, lto_file *file)
>      }
>  }
>  
> +/* List of file_decl_datas */
> +struct file_data_list
> +  {
> +    struct lto_file_decl_data *first, *last;
> +  };
> +
>  /* Is the name for a id'ed LTO section? */
>  
>  static int 
> @@ -1068,11 +1074,10 @@ lto_section_with_id (const char *name, unsigned HOST_WIDE_INT *id)
>  /* Create file_data of each sub file id */
>  
>  static int 
> -create_subid_section_table (void **slot, void *data)
> +create_subid_section_table (struct lto_section_slot *ls, splay_tree file_ids,
> +                            struct file_data_list *list)
>  {
>    struct lto_section_slot s_slot, *new_slot;
> -  struct lto_section_slot *ls = *(struct lto_section_slot **)slot;
> -  splay_tree file_ids = (splay_tree)data;
>    unsigned HOST_WIDE_INT id;
>    splay_tree_node nd;
>    void **hash_slot;
> @@ -1095,6 +1100,13 @@ create_subid_section_table (void **slot, void *data)
>        file_data->id = id;
>        file_data->section_hash_table = lto_obj_create_section_hash_table ();;
>        lto_splay_tree_insert (file_ids, id, file_data);
> +
> +      /* Maintain list in linker order */
> +      if (!list->first)
> +        list->first = file_data;
> +      if (list->last)
> +        list->last->next = file_data;
> +      list->last = file_data;
>      }
>  
>    /* Copy section into sub module hash table */
> @@ -1129,27 +1141,17 @@ lto_file_finalize (struct lto_file_decl_data *file_data, lto_file *file)
>    lto_free_section_data (file_data, LTO_section_decls, NULL, data, len);
>  }
>  
> -struct lwstate
> -{
> -  lto_file *file;
> -  struct lto_file_decl_data **file_data;
> -  int *count;
> -};
> -
> -/* Traverse ids and create a list of file_datas out of it. */      
> +/* Finalize FILE_DATA in FILE and increase COUNT. */
>  
> -static int lto_create_files_from_ids (splay_tree_node node, void *data)
> +static int 
> +lto_create_files_from_ids (lto_file *file, struct lto_file_decl_data *file_data, 
> +			   int *count)
>  {
> -  struct lwstate *lw = (struct lwstate *)data;
> -  struct lto_file_decl_data *file_data = (struct lto_file_decl_data *)node->value;
> -
> -  lto_file_finalize (file_data, lw->file);
> +  lto_file_finalize (file_data, file);
>    if (cgraph_dump_file)
>      fprintf (cgraph_dump_file, "Creating file %s with sub id " HOST_WIDE_INT_PRINT_HEX "\n", 
>  	     file_data->file_name, file_data->id);
> -  file_data->next = *lw->file_data;
> -  *lw->file_data = file_data;
> -  (*lw->count)++;
> +  (*count)++;
>    return 0;
>  }
>  
> @@ -1166,29 +1168,31 @@ lto_file_read (lto_file *file, FILE *resolution_file, int *count)
>    struct lto_file_decl_data *file_data = NULL;
>    splay_tree file_ids;
>    htab_t section_hash_table;
> -  struct lwstate state;
> -  
> -  section_hash_table = lto_obj_build_section_table (file);
> +  struct lto_section_slot *section;
> +  struct file_data_list file_list;
> +  struct lto_section_list section_list;
> + 
> +  memset (&section_list, 0, sizeof (struct lto_section_list)); 
> +  section_hash_table = lto_obj_build_section_table (file, &section_list);
>  
>    /* Find all sub modules in the object and put their sections into new hash
>       tables in a splay tree. */
>    file_ids = lto_splay_tree_new ();
> -  htab_traverse (section_hash_table, create_subid_section_table, file_ids);
> -  
> +  memset (&file_list, 0, sizeof (struct file_data_list));
> +  for (section = section_list.first; section != NULL; section = section->next)
> +    create_subid_section_table (section, file_ids, &file_list);
> +
>    /* Add resolutions to file ids */
>    lto_resolution_read (file_ids, resolution_file, file);
>  
> -  /* Finalize each lto file for each submodule in the merged object
> -     and create list for returning. */
> -  state.file = file;
> -  state.file_data = &file_data;
> -  state.count = count;
> -  splay_tree_foreach (file_ids, lto_create_files_from_ids, &state);
> -    
> +  /* Finalize each lto file for each submodule in the merged object */
> +  for (file_data = file_list.first; file_data != NULL; file_data = file_data->next)
> +    lto_create_files_from_ids (file, file_data, count);
> + 
>    splay_tree_delete (file_ids);
>    htab_delete (section_hash_table);
>  
> -  return file_data;
> +  return file_list.first;
>  }
>  
>  #if HAVE_MMAP_FILE && HAVE_SYSCONF && defined _SC_PAGE_SIZE
> @@ -2427,7 +2431,7 @@ lto_read_all_file_options (void)
>  
>        file_data = XCNEW (struct lto_file_decl_data);
>        file_data->file_name = file->filename;
> -      file_data->section_hash_table = lto_obj_build_section_table (file);
> +      file_data->section_hash_table = lto_obj_build_section_table (file, NULL);
>  
>        lto_read_file_options (file_data);
>  
> diff --git a/gcc/lto/lto.h b/gcc/lto/lto.h
> index 8110ace..43fcca6 100644
> --- a/gcc/lto/lto.h
> +++ b/gcc/lto/lto.h
> @@ -43,7 +43,8 @@ extern void lto_read_all_file_options (void);
>  /* In lto-elf.c or lto-coff.c  */
>  extern lto_file *lto_obj_file_open (const char *filename, bool writable);
>  extern void lto_obj_file_close (lto_file *file);
> -extern htab_t lto_obj_build_section_table (lto_file *file);
> +struct lto_section_list;
> +extern htab_t lto_obj_build_section_table (lto_file *file, struct lto_section_list *list);
>  extern htab_t lto_obj_create_section_hash_table (void);
>  extern void lto_obj_begin_section (const char *name);
>  extern void lto_obj_append_data (const void *data, size_t len, void *block);
> @@ -58,6 +59,13 @@ struct lto_section_slot
>    const char *name;
>    intptr_t start;
>    size_t len;
> +  struct lto_section_slot *next;
> +};
> +
> +/* A list of section slots */
> +struct lto_section_list
> +{
> +  struct lto_section_slot *first, *last;
>  };
>  
>  int64_t lto_parse_hex (const char *p);
Richard Guenther - Oct. 4, 2011, 10:20 a.m.
On Tue, 4 Oct 2011, Jan Hubicka wrote:

> > From: Andi Kleen <ak@linux.intel.com>
> > 
> > Currently when reading in LTO sections from ld -r files they can
> > get randomly reordered based on hash tables and random IDs.
> > This causes reordering later when the final code is generated and
> > also makes crashes harder to reproduce.
> > 
> > This patch maintains explicit lists based on the input order and uses
> > those lists to preserve that order when starting the rest of the
> > LTO passes.
> > 
> > This is the first step to working -fno-toplevel-reorder for
> > LTO. But this needs more changes because the LTO partitioner
> > can still reorder.
> > 
> > This add two lists: one for the section and another one for
> > the file_decl_datas. This is needed because the sections are
> > walked twice through different data structures.
> > 
> > In addition some code becomes slightly cleaner because we don't need
> > to pass state through abstract callbacks anymore, but
> > can just use direct type safe calls.
> > 
> > Passes LTO bootstrap and testsuite on x86_64-linux. Ok?
> 
> Note that this is also needed to make lto-symtab decisions consistent with linker
> decisions. So it makes a lot of sense to me, but I can't approve it.
> I was running into funny cases where things got resolved differently on
> openoffice, so hopefully this will solve it.

Well, I'm not sure we should jump through too much hoops to make
-flto work with -fno-toplevel-reorder.  Simply because I think nothing
defines any "toplevel order" for multiple object files.  So, I think
both ld and gcc/collect2 need to first document they will never
break toplevel order (what about ld with -ffunction-sections and
-gc-sections? Or -relax?)

Richard.

> 
> Honza
> > 
> > gcc/lto/:
> > 
> > 2011-10-02   Andi Kleen <ak@linux.intel.com>
> > 
> > 	* lto-object.c (lto_obj_add_section_data): Add list.
> > 	(lto_obj_add_section): Fill in list.
> > 	(ltoobj_build_section_table): Pass through list.
> > 	* lto.c (file_data_list): Declare.
> > 	(create_subid_section_table): Pass arguments directly.
> > 	Fill in list of file_datas.
> > 	(lwstate): Delete.
> > 	(lto_create_files_from_ids): Pass in direct arguments.
> > 	Don't maintain list.
> > 	(lto_file_read): Use explicit section and file data lists.
> > 	(lto_read_all_file_options): Pass in section_list.
> > 	* lto.h (lto_obj_build_section_table): Add list.
> > 	(lto_section_slot): Add next.
> > 	(lto_section_list): Declare.
> > 
> > diff --git a/gcc/lto/lto-object.c b/gcc/lto/lto-object.c
> > index 3be58de..daf3bd0 100644
> > --- a/gcc/lto/lto-object.c
> > +++ b/gcc/lto/lto-object.c
> > @@ -204,6 +204,8 @@ struct lto_obj_add_section_data
> >    htab_t section_hash_table;
> >    /* The offset of this file.  */
> >    off_t base_offset;
> > +  /* List in linker order */
> > +  struct lto_section_list *list;
> >  };
> >  
> >  /* This is called for each section in the file.  */
> > @@ -218,6 +220,7 @@ lto_obj_add_section (void *data, const char *name, off_t offset,
> >    char *new_name;
> >    struct lto_section_slot s_slot;
> >    void **slot;
> > +  struct lto_section_list *list = loasd->list;
> >  
> >    if (strncmp (name, LTO_SECTION_NAME_PREFIX,
> >  	       strlen (LTO_SECTION_NAME_PREFIX)) != 0)
> > @@ -228,12 +231,21 @@ lto_obj_add_section (void *data, const char *name, off_t offset,
> >    slot = htab_find_slot (section_hash_table, &s_slot, INSERT);
> >    if (*slot == NULL)
> >      {
> > -      struct lto_section_slot *new_slot = XNEW (struct lto_section_slot);
> > +      struct lto_section_slot *new_slot = XCNEW (struct lto_section_slot);
> >  
> >        new_slot->name = new_name;
> >        new_slot->start = loasd->base_offset + offset;
> >        new_slot->len = length;
> >        *slot = new_slot;
> > +
> > +      if (list != NULL)
> > +        {
> > +          if (!list->first)
> > +            list->first = new_slot;
> > +          if (list->last)
> > +            list->last->next = new_slot;
> > +          list->last = new_slot;
> > +        }
> >      }
> >    else
> >      {
> > @@ -248,7 +260,7 @@ lto_obj_add_section (void *data, const char *name, off_t offset,
> >     the start and size of each section in the .o file.  */
> >  
> >  htab_t
> > -lto_obj_build_section_table (lto_file *lto_file)
> > +lto_obj_build_section_table (lto_file *lto_file, struct lto_section_list *list)
> >  {
> >    struct lto_simple_object *lo = (struct lto_simple_object *) lto_file;
> >    htab_t section_hash_table;
> > @@ -261,6 +273,7 @@ lto_obj_build_section_table (lto_file *lto_file)
> >    gcc_assert (lo->sobj_r != NULL && lo->sobj_w == NULL);
> >    loasd.section_hash_table = section_hash_table;
> >    loasd.base_offset = lo->base.offset;
> > +  loasd.list = list;
> >    errmsg = simple_object_find_sections (lo->sobj_r, lto_obj_add_section,
> >  					&loasd, &err);
> >    if (errmsg != NULL)
> > diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
> > index 778e33e..a77eeb4 100644
> > --- a/gcc/lto/lto.c
> > +++ b/gcc/lto/lto.c
> > @@ -1052,6 +1052,12 @@ lto_resolution_read (splay_tree file_ids, FILE *resolution, lto_file *file)
> >      }
> >  }
> >  
> > +/* List of file_decl_datas */
> > +struct file_data_list
> > +  {
> > +    struct lto_file_decl_data *first, *last;
> > +  };
> > +
> >  /* Is the name for a id'ed LTO section? */
> >  
> >  static int 
> > @@ -1068,11 +1074,10 @@ lto_section_with_id (const char *name, unsigned HOST_WIDE_INT *id)
> >  /* Create file_data of each sub file id */
> >  
> >  static int 
> > -create_subid_section_table (void **slot, void *data)
> > +create_subid_section_table (struct lto_section_slot *ls, splay_tree file_ids,
> > +                            struct file_data_list *list)
> >  {
> >    struct lto_section_slot s_slot, *new_slot;
> > -  struct lto_section_slot *ls = *(struct lto_section_slot **)slot;
> > -  splay_tree file_ids = (splay_tree)data;
> >    unsigned HOST_WIDE_INT id;
> >    splay_tree_node nd;
> >    void **hash_slot;
> > @@ -1095,6 +1100,13 @@ create_subid_section_table (void **slot, void *data)
> >        file_data->id = id;
> >        file_data->section_hash_table = lto_obj_create_section_hash_table ();;
> >        lto_splay_tree_insert (file_ids, id, file_data);
> > +
> > +      /* Maintain list in linker order */
> > +      if (!list->first)
> > +        list->first = file_data;
> > +      if (list->last)
> > +        list->last->next = file_data;
> > +      list->last = file_data;
> >      }
> >  
> >    /* Copy section into sub module hash table */
> > @@ -1129,27 +1141,17 @@ lto_file_finalize (struct lto_file_decl_data *file_data, lto_file *file)
> >    lto_free_section_data (file_data, LTO_section_decls, NULL, data, len);
> >  }
> >  
> > -struct lwstate
> > -{
> > -  lto_file *file;
> > -  struct lto_file_decl_data **file_data;
> > -  int *count;
> > -};
> > -
> > -/* Traverse ids and create a list of file_datas out of it. */      
> > +/* Finalize FILE_DATA in FILE and increase COUNT. */
> >  
> > -static int lto_create_files_from_ids (splay_tree_node node, void *data)
> > +static int 
> > +lto_create_files_from_ids (lto_file *file, struct lto_file_decl_data *file_data, 
> > +			   int *count)
> >  {
> > -  struct lwstate *lw = (struct lwstate *)data;
> > -  struct lto_file_decl_data *file_data = (struct lto_file_decl_data *)node->value;
> > -
> > -  lto_file_finalize (file_data, lw->file);
> > +  lto_file_finalize (file_data, file);
> >    if (cgraph_dump_file)
> >      fprintf (cgraph_dump_file, "Creating file %s with sub id " HOST_WIDE_INT_PRINT_HEX "\n", 
> >  	     file_data->file_name, file_data->id);
> > -  file_data->next = *lw->file_data;
> > -  *lw->file_data = file_data;
> > -  (*lw->count)++;
> > +  (*count)++;
> >    return 0;
> >  }
> >  
> > @@ -1166,29 +1168,31 @@ lto_file_read (lto_file *file, FILE *resolution_file, int *count)
> >    struct lto_file_decl_data *file_data = NULL;
> >    splay_tree file_ids;
> >    htab_t section_hash_table;
> > -  struct lwstate state;
> > -  
> > -  section_hash_table = lto_obj_build_section_table (file);
> > +  struct lto_section_slot *section;
> > +  struct file_data_list file_list;
> > +  struct lto_section_list section_list;
> > + 
> > +  memset (&section_list, 0, sizeof (struct lto_section_list)); 
> > +  section_hash_table = lto_obj_build_section_table (file, &section_list);
> >  
> >    /* Find all sub modules in the object and put their sections into new hash
> >       tables in a splay tree. */
> >    file_ids = lto_splay_tree_new ();
> > -  htab_traverse (section_hash_table, create_subid_section_table, file_ids);
> > -  
> > +  memset (&file_list, 0, sizeof (struct file_data_list));
> > +  for (section = section_list.first; section != NULL; section = section->next)
> > +    create_subid_section_table (section, file_ids, &file_list);
> > +
> >    /* Add resolutions to file ids */
> >    lto_resolution_read (file_ids, resolution_file, file);
> >  
> > -  /* Finalize each lto file for each submodule in the merged object
> > -     and create list for returning. */
> > -  state.file = file;
> > -  state.file_data = &file_data;
> > -  state.count = count;
> > -  splay_tree_foreach (file_ids, lto_create_files_from_ids, &state);
> > -    
> > +  /* Finalize each lto file for each submodule in the merged object */
> > +  for (file_data = file_list.first; file_data != NULL; file_data = file_data->next)
> > +    lto_create_files_from_ids (file, file_data, count);
> > + 
> >    splay_tree_delete (file_ids);
> >    htab_delete (section_hash_table);
> >  
> > -  return file_data;
> > +  return file_list.first;
> >  }
> >  
> >  #if HAVE_MMAP_FILE && HAVE_SYSCONF && defined _SC_PAGE_SIZE
> > @@ -2427,7 +2431,7 @@ lto_read_all_file_options (void)
> >  
> >        file_data = XCNEW (struct lto_file_decl_data);
> >        file_data->file_name = file->filename;
> > -      file_data->section_hash_table = lto_obj_build_section_table (file);
> > +      file_data->section_hash_table = lto_obj_build_section_table (file, NULL);
> >  
> >        lto_read_file_options (file_data);
> >  
> > diff --git a/gcc/lto/lto.h b/gcc/lto/lto.h
> > index 8110ace..43fcca6 100644
> > --- a/gcc/lto/lto.h
> > +++ b/gcc/lto/lto.h
> > @@ -43,7 +43,8 @@ extern void lto_read_all_file_options (void);
> >  /* In lto-elf.c or lto-coff.c  */
> >  extern lto_file *lto_obj_file_open (const char *filename, bool writable);
> >  extern void lto_obj_file_close (lto_file *file);
> > -extern htab_t lto_obj_build_section_table (lto_file *file);
> > +struct lto_section_list;
> > +extern htab_t lto_obj_build_section_table (lto_file *file, struct lto_section_list *list);
> >  extern htab_t lto_obj_create_section_hash_table (void);
> >  extern void lto_obj_begin_section (const char *name);
> >  extern void lto_obj_append_data (const void *data, size_t len, void *block);
> > @@ -58,6 +59,13 @@ struct lto_section_slot
> >    const char *name;
> >    intptr_t start;
> >    size_t len;
> > +  struct lto_section_slot *next;
> > +};
> > +
> > +/* A list of section slots */
> > +struct lto_section_list
> > +{
> > +  struct lto_section_slot *first, *last;
> >  };
> >  
> >  int64_t lto_parse_hex (const char *p);
> 
>
Andi Kleen - Oct. 4, 2011, 1:03 p.m.
> Well, I'm not sure we should jump through too much hoops to make
> -flto work with -fno-toplevel-reorder.  Simply because I think nothing
> defines any "toplevel order" for multiple object files.  So, I think

In practice it seems to work because real programs rely on it.

I can just say with this patch and Honza's my program works
(with -flto-partition=none), without it it doesn't.

Also as Honza pointed out it has other benefits, like making
compiles more reproducible. For example if you have a memory corruption
somewhere the random order currently will randomly move it from
run to run and make it harder to debug.

> both ld and gcc/collect2 need to first document they will never
> break toplevel order (what about ld with -ffunction-sections and
> -gc-sections? Or -relax?)

-ffunction-sections and -gc-sections do not reorder as far as I know.
Not sure about -relax.

But the programs that rely on order should "don't do it when it hurts"
so not set too magic options. I'm sure there are other creative ways to break
order too, but it doesn't seem to be too hard in practice to avoid
them.


-Andi
Richard Guenther - Oct. 4, 2011, 1:08 p.m.
On Tue, 4 Oct 2011, Andi Kleen wrote:

> > Well, I'm not sure we should jump through too much hoops to make
> > -flto work with -fno-toplevel-reorder.  Simply because I think nothing
> > defines any "toplevel order" for multiple object files.  So, I think
> 
> In practice it seems to work because real programs rely on it.
> 
> I can just say with this patch and Honza's my program works
> (with -flto-partition=none), without it it doesn't.
> 
> Also as Honza pointed out it has other benefits, like making
> compiles more reproducible. For example if you have a memory corruption
> somewhere the random order currently will randomly move it from
> run to run and make it harder to debug.
> 
> > both ld and gcc/collect2 need to first document they will never
> > break toplevel order (what about ld with -ffunction-sections and
> > -gc-sections? Or -relax?)
> 
> -ffunction-sections and -gc-sections do not reorder as far as I know.
> Not sure about -relax.
> 
> But the programs that rely on order should "don't do it when it hurts"
> so not set too magic options. I'm sure there are other creative ways to break
> order too, but it doesn't seem to be too hard in practice to avoid
> them.

Sure, the question is if "-flto" counts as magic and thus
"don't do it when it hurts" ;))  I suppose with -flto-partition=none
(or 1to1) it would be reasonable to make -fno-toplevel-reorder work
(and thus maybe -fno-toplevel-reorder should simply force 1to1 
partitioning).

Richard.
Andi Kleen - Oct. 4, 2011, 1:16 p.m.
On Tue, Oct 04, 2011 at 03:08:02PM +0200, Richard Guenther wrote

> Sure, the question is if "-flto" counts as magic and thus
> "don't do it when it hurts" ;))  I suppose with -flto-partition=none
> (or 1to1) it would be reasonable to make -fno-toplevel-reorder work
> (and thus maybe -fno-toplevel-reorder should simply force 1to1 
> partitioning).

At least =none is incredible slow for larger programs. I would really
prefer normal whopr, otherwise at some point LTO becomes unpracticable
due to the extreme compile time penalty. I can use it right now as 
a workaround, but it's not a long term solution.

What I really want is not full -fno-toplevel-reorder anyways, but just
marking a few special variables with a special attribute to not
reorder. But this patch is still needed even for that and likely a good 
idea anyways for the other reasons.

-Andi
Richard Guenther - Oct. 4, 2011, 1:38 p.m.
On Tue, 4 Oct 2011, Andi Kleen wrote:

> On Tue, Oct 04, 2011 at 03:08:02PM +0200, Richard Guenther wrote
> 
> > Sure, the question is if "-flto" counts as magic and thus
> > "don't do it when it hurts" ;))  I suppose with -flto-partition=none
> > (or 1to1) it would be reasonable to make -fno-toplevel-reorder work
> > (and thus maybe -fno-toplevel-reorder should simply force 1to1 
> > partitioning).
> 
> At least =none is incredible slow for larger programs. I would really
> prefer normal whopr, otherwise at some point LTO becomes unpracticable
> due to the extreme compile time penalty. I can use it right now as 
> a workaround, but it's not a long term solution.
> 
> What I really want is not full -fno-toplevel-reorder anyways, but just
> marking a few special variables with a special attribute to not
> reorder. But this patch is still needed even for that and likely a good 
> idea anyways for the other reasons.

Yes, of course - I was just arguing about the supposed final state
we want to arrive at with respect to -fno-toplevel-reorder and LTO.

The patch is ok (it probably will also help testcase reductions).

Thanks,
Richard.
Mike Stump - Oct. 4, 2011, 6:58 p.m.
On Oct 4, 2011, at 6:03 AM, Andi Kleen wrote:
> Also as Honza pointed out it has other benefits, like making
> compiles more reproducible. For example if you have a memory corruption
> somewhere the random order currently will randomly move it from
> run to run and make it harder to debug.

I like deterministic compilers.  :-)  I like an ordering that has a specific deterministic reason for it.
Jan Hubicka - Oct. 4, 2011, 9:08 p.m.
> On Tue, 4 Oct 2011, Andi Kleen wrote:
> 
> > > Well, I'm not sure we should jump through too much hoops to make
> > > -flto work with -fno-toplevel-reorder.  Simply because I think nothing
> > > defines any "toplevel order" for multiple object files.  So, I think
> > 
> > In practice it seems to work because real programs rely on it.

I don't see much jump in undefinedness in between single file and LTO definition
of -fno-toplevel-reorder.
-fno-toplevel reorder is "please outout functions as they are written in the
source file because it is what GCC used to do. Ignore inlines and comdats"
at IPA level we just concatenate the order in order how files are passed
to linker.  Again there is bit of undefinedness in how static libraries and
garbage collected sections are handled, but in the common cases people care
about it just does the job.
> > 
> > I can just say with this patch and Honza's my program works
> > (with -flto-partition=none), without it it doesn't.
> > 
> > Also as Honza pointed out it has other benefits, like making
> > compiles more reproducible. For example if you have a memory corruption
> > somewhere the random order currently will randomly move it from
> > run to run and make it harder to debug.
> > 
> > > both ld and gcc/collect2 need to first document they will never
> > > break toplevel order (what about ld with -ffunction-sections and
> > > -gc-sections? Or -relax?)
> > 
> > -ffunction-sections and -gc-sections do not reorder as far as I know.
> > Not sure about -relax.
> > 
> > But the programs that rely on order should "don't do it when it hurts"
> > so not set too magic options. I'm sure there are other creative ways to break
> > order too, but it doesn't seem to be too hard in practice to avoid
> > them.
> 
> Sure, the question is if "-flto" counts as magic and thus
> "don't do it when it hurts" ;))  I suppose with -flto-partition=none
> (or 1to1) it would be reasonable to make -fno-toplevel-reorder work
> (and thus maybe -fno-toplevel-reorder should simply force 1to1 
> partitioning).

Note that 1to1 partitioning won't give you -fno-toplevel-reorder as currently
implemented. It assigns the partitions in random order and then the partitions
get sorted by size.

The default partitioner is written to honor predefined order. In fact I do have
patch to make it honnor -fno-toplevel-reorder from very beggining, just I have
never submitted it.  it is how my ipa-reorder pass works (it simply decides on
"optimal" function order and then assigns them ->order indexes).
It does not handle variables and asm statements. Neither is terribly difficult
to do so I will post patches for those.

Honza
> 
> Richard.

Patch

diff --git a/gcc/lto/lto-object.c b/gcc/lto/lto-object.c
index 3be58de..daf3bd0 100644
--- a/gcc/lto/lto-object.c
+++ b/gcc/lto/lto-object.c
@@ -204,6 +204,8 @@  struct lto_obj_add_section_data
   htab_t section_hash_table;
   /* The offset of this file.  */
   off_t base_offset;
+  /* List in linker order */
+  struct lto_section_list *list;
 };
 
 /* This is called for each section in the file.  */
@@ -218,6 +220,7 @@  lto_obj_add_section (void *data, const char *name, off_t offset,
   char *new_name;
   struct lto_section_slot s_slot;
   void **slot;
+  struct lto_section_list *list = loasd->list;
 
   if (strncmp (name, LTO_SECTION_NAME_PREFIX,
 	       strlen (LTO_SECTION_NAME_PREFIX)) != 0)
@@ -228,12 +231,21 @@  lto_obj_add_section (void *data, const char *name, off_t offset,
   slot = htab_find_slot (section_hash_table, &s_slot, INSERT);
   if (*slot == NULL)
     {
-      struct lto_section_slot *new_slot = XNEW (struct lto_section_slot);
+      struct lto_section_slot *new_slot = XCNEW (struct lto_section_slot);
 
       new_slot->name = new_name;
       new_slot->start = loasd->base_offset + offset;
       new_slot->len = length;
       *slot = new_slot;
+
+      if (list != NULL)
+        {
+          if (!list->first)
+            list->first = new_slot;
+          if (list->last)
+            list->last->next = new_slot;
+          list->last = new_slot;
+        }
     }
   else
     {
@@ -248,7 +260,7 @@  lto_obj_add_section (void *data, const char *name, off_t offset,
    the start and size of each section in the .o file.  */
 
 htab_t
-lto_obj_build_section_table (lto_file *lto_file)
+lto_obj_build_section_table (lto_file *lto_file, struct lto_section_list *list)
 {
   struct lto_simple_object *lo = (struct lto_simple_object *) lto_file;
   htab_t section_hash_table;
@@ -261,6 +273,7 @@  lto_obj_build_section_table (lto_file *lto_file)
   gcc_assert (lo->sobj_r != NULL && lo->sobj_w == NULL);
   loasd.section_hash_table = section_hash_table;
   loasd.base_offset = lo->base.offset;
+  loasd.list = list;
   errmsg = simple_object_find_sections (lo->sobj_r, lto_obj_add_section,
 					&loasd, &err);
   if (errmsg != NULL)
diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
index 778e33e..a77eeb4 100644
--- a/gcc/lto/lto.c
+++ b/gcc/lto/lto.c
@@ -1052,6 +1052,12 @@  lto_resolution_read (splay_tree file_ids, FILE *resolution, lto_file *file)
     }
 }
 
+/* List of file_decl_datas */
+struct file_data_list
+  {
+    struct lto_file_decl_data *first, *last;
+  };
+
 /* Is the name for a id'ed LTO section? */
 
 static int 
@@ -1068,11 +1074,10 @@  lto_section_with_id (const char *name, unsigned HOST_WIDE_INT *id)
 /* Create file_data of each sub file id */
 
 static int 
-create_subid_section_table (void **slot, void *data)
+create_subid_section_table (struct lto_section_slot *ls, splay_tree file_ids,
+                            struct file_data_list *list)
 {
   struct lto_section_slot s_slot, *new_slot;
-  struct lto_section_slot *ls = *(struct lto_section_slot **)slot;
-  splay_tree file_ids = (splay_tree)data;
   unsigned HOST_WIDE_INT id;
   splay_tree_node nd;
   void **hash_slot;
@@ -1095,6 +1100,13 @@  create_subid_section_table (void **slot, void *data)
       file_data->id = id;
       file_data->section_hash_table = lto_obj_create_section_hash_table ();;
       lto_splay_tree_insert (file_ids, id, file_data);
+
+      /* Maintain list in linker order */
+      if (!list->first)
+        list->first = file_data;
+      if (list->last)
+        list->last->next = file_data;
+      list->last = file_data;
     }
 
   /* Copy section into sub module hash table */
@@ -1129,27 +1141,17 @@  lto_file_finalize (struct lto_file_decl_data *file_data, lto_file *file)
   lto_free_section_data (file_data, LTO_section_decls, NULL, data, len);
 }
 
-struct lwstate
-{
-  lto_file *file;
-  struct lto_file_decl_data **file_data;
-  int *count;
-};
-
-/* Traverse ids and create a list of file_datas out of it. */      
+/* Finalize FILE_DATA in FILE and increase COUNT. */
 
-static int lto_create_files_from_ids (splay_tree_node node, void *data)
+static int 
+lto_create_files_from_ids (lto_file *file, struct lto_file_decl_data *file_data, 
+			   int *count)
 {
-  struct lwstate *lw = (struct lwstate *)data;
-  struct lto_file_decl_data *file_data = (struct lto_file_decl_data *)node->value;
-
-  lto_file_finalize (file_data, lw->file);
+  lto_file_finalize (file_data, file);
   if (cgraph_dump_file)
     fprintf (cgraph_dump_file, "Creating file %s with sub id " HOST_WIDE_INT_PRINT_HEX "\n", 
 	     file_data->file_name, file_data->id);
-  file_data->next = *lw->file_data;
-  *lw->file_data = file_data;
-  (*lw->count)++;
+  (*count)++;
   return 0;
 }
 
@@ -1166,29 +1168,31 @@  lto_file_read (lto_file *file, FILE *resolution_file, int *count)
   struct lto_file_decl_data *file_data = NULL;
   splay_tree file_ids;
   htab_t section_hash_table;
-  struct lwstate state;
-  
-  section_hash_table = lto_obj_build_section_table (file);
+  struct lto_section_slot *section;
+  struct file_data_list file_list;
+  struct lto_section_list section_list;
+ 
+  memset (&section_list, 0, sizeof (struct lto_section_list)); 
+  section_hash_table = lto_obj_build_section_table (file, &section_list);
 
   /* Find all sub modules in the object and put their sections into new hash
      tables in a splay tree. */
   file_ids = lto_splay_tree_new ();
-  htab_traverse (section_hash_table, create_subid_section_table, file_ids);
-  
+  memset (&file_list, 0, sizeof (struct file_data_list));
+  for (section = section_list.first; section != NULL; section = section->next)
+    create_subid_section_table (section, file_ids, &file_list);
+
   /* Add resolutions to file ids */
   lto_resolution_read (file_ids, resolution_file, file);
 
-  /* Finalize each lto file for each submodule in the merged object
-     and create list for returning. */
-  state.file = file;
-  state.file_data = &file_data;
-  state.count = count;
-  splay_tree_foreach (file_ids, lto_create_files_from_ids, &state);
-    
+  /* Finalize each lto file for each submodule in the merged object */
+  for (file_data = file_list.first; file_data != NULL; file_data = file_data->next)
+    lto_create_files_from_ids (file, file_data, count);
+ 
   splay_tree_delete (file_ids);
   htab_delete (section_hash_table);
 
-  return file_data;
+  return file_list.first;
 }
 
 #if HAVE_MMAP_FILE && HAVE_SYSCONF && defined _SC_PAGE_SIZE
@@ -2427,7 +2431,7 @@  lto_read_all_file_options (void)
 
       file_data = XCNEW (struct lto_file_decl_data);
       file_data->file_name = file->filename;
-      file_data->section_hash_table = lto_obj_build_section_table (file);
+      file_data->section_hash_table = lto_obj_build_section_table (file, NULL);
 
       lto_read_file_options (file_data);
 
diff --git a/gcc/lto/lto.h b/gcc/lto/lto.h
index 8110ace..43fcca6 100644
--- a/gcc/lto/lto.h
+++ b/gcc/lto/lto.h
@@ -43,7 +43,8 @@  extern void lto_read_all_file_options (void);
 /* In lto-elf.c or lto-coff.c  */
 extern lto_file *lto_obj_file_open (const char *filename, bool writable);
 extern void lto_obj_file_close (lto_file *file);
-extern htab_t lto_obj_build_section_table (lto_file *file);
+struct lto_section_list;
+extern htab_t lto_obj_build_section_table (lto_file *file, struct lto_section_list *list);
 extern htab_t lto_obj_create_section_hash_table (void);
 extern void lto_obj_begin_section (const char *name);
 extern void lto_obj_append_data (const void *data, size_t len, void *block);
@@ -58,6 +59,13 @@  struct lto_section_slot
   const char *name;
   intptr_t start;
   size_t len;
+  struct lto_section_slot *next;
+};
+
+/* A list of section slots */
+struct lto_section_list
+{
+  struct lto_section_slot *first, *last;
 };
 
 int64_t lto_parse_hex (const char *p);