OSDN Git Service

cbc192a664493a7a0e8e042c4b30f9384db94fa9
[pf3gnuchains/gcc-fork.git] / gcc / lto / lto.c
1 /* Top-level LTO routines.
2    Copyright 2009, 2010 Free Software Foundation, Inc.
3    Contributed by CodeSourcery, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "opts.h"
25 #include "toplev.h"
26 #include "tree.h"
27 #include "diagnostic-core.h"
28 #include "tm.h"
29 #include "cgraph.h"
30 #include "ggc.h"
31 #include "tree-ssa-operands.h"
32 #include "tree-pass.h"
33 #include "langhooks.h"
34 #include "vec.h"
35 #include "bitmap.h"
36 #include "pointer-set.h"
37 #include "ipa-prop.h"
38 #include "common.h"
39 #include "debug.h"
40 #include "timevar.h"
41 #include "gimple.h"
42 #include "lto.h"
43 #include "lto-tree.h"
44 #include "lto-streamer.h"
45 #include "splay-tree.h"
46 #include "params.h"
47
48 static GTY(()) tree first_personality_decl;
49
50 /* Returns a hash code for P.  */
51
52 static hashval_t
53 hash_name (const void *p)
54 {
55   const struct lto_section_slot *ds = (const struct lto_section_slot *) p;
56   return (hashval_t) htab_hash_string (ds->name);
57 }
58
59
60 /* Returns nonzero if P1 and P2 are equal.  */
61
62 static int
63 eq_name (const void *p1, const void *p2)
64 {
65   const struct lto_section_slot *s1 =
66     (const struct lto_section_slot *) p1;
67   const struct lto_section_slot *s2 =
68     (const struct lto_section_slot *) p2;
69
70   return strcmp (s1->name, s2->name) == 0;
71 }
72
73 /* Free lto_section_slot */
74
75 static void
76 free_with_string (void *arg)
77 {
78   struct lto_section_slot *s = (struct lto_section_slot *)arg;
79
80   free (CONST_CAST (char *, s->name));
81   free (arg);
82 }
83
84 /* Create section hash table */
85
86 htab_t 
87 lto_obj_create_section_hash_table (void)
88 {
89   return htab_create (37, hash_name, eq_name, free_with_string);
90 }
91
92 /* Read the constructors and inits.  */
93
94 static void
95 lto_materialize_constructors_and_inits (struct lto_file_decl_data * file_data)
96 {
97   size_t len;
98   const char *data = lto_get_section_data (file_data, 
99                                            LTO_section_static_initializer,
100                                            NULL, &len);
101   lto_input_constructors_and_inits (file_data, data);
102   lto_free_section_data (file_data, LTO_section_static_initializer, NULL,
103                          data, len);
104 }
105
106 /* Return true when NODE has a clone that is analyzed (i.e. we need
107    to load its body even if the node itself is not needed).  */
108
109 static bool
110 has_analyzed_clone_p (struct cgraph_node *node)
111 {
112   struct cgraph_node *orig = node;
113   node = node->clones;
114   if (node)
115     while (node != orig)
116       {
117         if (node->analyzed)
118           return true;
119         if (node->clones)
120           node = node->clones;
121         else if (node->next_sibling_clone)
122           node = node->next_sibling_clone;
123         else
124           {
125             while (node != orig && !node->next_sibling_clone)
126               node = node->clone_of;
127             if (node != orig)
128               node = node->next_sibling_clone;
129           }
130       }
131   return false;
132 }
133
134 /* Read the function body for the function associated with NODE.  */
135
136 static void
137 lto_materialize_function (struct cgraph_node *node)
138 {
139   tree decl;
140   struct lto_file_decl_data *file_data;
141   const char *data, *name;
142   size_t len;
143
144   decl = node->decl;
145   /* Read in functions with body (analyzed nodes)
146      and also functions that are needed to produce virtual clones.  */
147   if (node->analyzed || has_analyzed_clone_p (node))
148     {
149       /* Clones don't need to be read.  */
150       if (node->clone_of)
151         return;
152       file_data = node->local.lto_file_data;
153       name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)); 
154
155       /* We may have renamed the declaration, e.g., a static function.  */
156       name = lto_get_decl_name_mapping (file_data, name);
157
158       data = lto_get_section_data (file_data, LTO_section_function_body,
159                                    name, &len);
160       if (!data)
161         fatal_error ("%s: section %s is missing",
162                      file_data->file_name,
163                      name);
164
165       gcc_assert (DECL_STRUCT_FUNCTION (decl) == NULL);
166
167       /* Load the function body only if not operating in WPA mode.  In
168          WPA mode, the body of the function is not needed.  */
169       if (!flag_wpa)
170         {
171           allocate_struct_function (decl, false);
172           announce_function (decl);
173           lto_input_function_body (file_data, decl, data);
174           if (DECL_FUNCTION_PERSONALITY (decl) && !first_personality_decl)
175             first_personality_decl = DECL_FUNCTION_PERSONALITY (decl);
176           lto_stats.num_function_bodies++;
177         }
178
179       lto_free_section_data (file_data, LTO_section_function_body, name,
180                              data, len);
181       if (!flag_wpa)
182         ggc_collect ();
183     }
184
185   /* Let the middle end know about the function.  */
186   rest_of_decl_compilation (decl, 1, 0);
187 }
188
189
190 /* Decode the content of memory pointed to by DATA in the the
191    in decl state object STATE. DATA_IN points to a data_in structure for
192    decoding. Return the address after the decoded object in the input.  */
193
194 static const uint32_t *
195 lto_read_in_decl_state (struct data_in *data_in, const uint32_t *data,
196                         struct lto_in_decl_state *state)
197 {
198   uint32_t ix;
199   tree decl;
200   uint32_t i, j;
201   
202   ix = *data++;
203   decl = lto_streamer_cache_get (data_in->reader_cache, (int) ix);
204   if (TREE_CODE (decl) != FUNCTION_DECL)
205     {
206       gcc_assert (decl == void_type_node);
207       decl = NULL_TREE;
208     }
209   state->fn_decl = decl;
210
211   for (i = 0; i < LTO_N_DECL_STREAMS; i++)
212     {
213       uint32_t size = *data++;
214       tree *decls = ggc_alloc_vec_tree (size);
215
216       for (j = 0; j < size; j++)
217         {
218           decls[j] = lto_streamer_cache_get (data_in->reader_cache, data[j]);
219
220           /* Register every type in the global type table.  If the
221              type existed already, use the existing type.  */
222           if (TYPE_P (decls[j]))
223             decls[j] = gimple_register_type (decls[j]);
224         }
225
226       state->streams[i].size = size;
227       state->streams[i].trees = decls;
228       data += size;
229     }
230
231   return data;
232 }
233
234
235 /* Read all the symbols from buffer DATA, using descriptors in DECL_DATA.
236    RESOLUTIONS is the set of symbols picked by the linker (read from the
237    resolution file when the linker plugin is being used).  */
238
239 static void
240 lto_read_decls (struct lto_file_decl_data *decl_data, const void *data,
241                 VEC(ld_plugin_symbol_resolution_t,heap) *resolutions)
242 {
243   const struct lto_decl_header *header = (const struct lto_decl_header *) data;
244   const int32_t decl_offset = sizeof (struct lto_decl_header);
245   const int32_t main_offset = decl_offset + header->decl_state_size;
246   const int32_t string_offset = main_offset + header->main_size;
247   struct lto_input_block ib_main;
248   struct data_in *data_in;
249   unsigned int i;
250   const uint32_t *data_ptr, *data_end;
251   uint32_t num_decl_states;
252
253   LTO_INIT_INPUT_BLOCK (ib_main, (const char *) data + main_offset, 0,
254                         header->main_size);
255
256   data_in = lto_data_in_create (decl_data, (const char *) data + string_offset,
257                                 header->string_size, resolutions);
258
259   /* Read the global declarations and types.  */
260   while (ib_main.p < ib_main.len)
261     {
262       tree t = lto_input_tree (&ib_main, data_in);
263       gcc_assert (t && ib_main.p <= ib_main.len);
264     }
265
266   /* Read in lto_in_decl_state objects.  */
267   data_ptr = (const uint32_t *) ((const char*) data + decl_offset); 
268   data_end =
269      (const uint32_t *) ((const char*) data_ptr + header->decl_state_size);
270   num_decl_states = *data_ptr++;
271   
272   gcc_assert (num_decl_states > 0);
273   decl_data->global_decl_state = lto_new_in_decl_state ();
274   data_ptr = lto_read_in_decl_state (data_in, data_ptr,
275                                      decl_data->global_decl_state);
276
277   /* Read in per-function decl states and enter them in hash table.  */
278   decl_data->function_decl_states =
279     htab_create_ggc (37, lto_hash_in_decl_state, lto_eq_in_decl_state, NULL);
280
281   for (i = 1; i < num_decl_states; i++)
282     {
283       struct lto_in_decl_state *state = lto_new_in_decl_state ();
284       void **slot;
285
286       data_ptr = lto_read_in_decl_state (data_in, data_ptr, state);
287       slot = htab_find_slot (decl_data->function_decl_states, state, INSERT);
288       gcc_assert (*slot == NULL);
289       *slot = state;
290     }
291
292   if (data_ptr != data_end)
293     internal_error ("bytecode stream: garbage at the end of symbols section");
294   
295   /* Set the current decl state to be the global state. */
296   decl_data->current_decl_state = decl_data->global_decl_state;
297
298   lto_data_in_delete (data_in);
299 }
300
301 /* strtoll is not portable. */
302 int64_t
303 lto_parse_hex (const char *p) {
304   uint64_t ret = 0;
305   for (; *p != '\0'; ++p)
306     {
307       char c = *p;
308       unsigned char part;
309       ret <<= 4;
310       if (c >= '0' && c <= '9')
311         part = c - '0';
312       else if (c >= 'a' && c <= 'f')
313         part = c - 'a' + 10;
314       else if (c >= 'A' && c <= 'F')
315         part = c - 'A' + 10;
316       else
317         internal_error ("could not parse hex number");
318       ret |= part;
319     }
320   return ret;
321 }
322
323 /* Read resolution for file named FILE_NAME. The resolution is read from
324    RESOLUTION. */
325
326 static void
327 lto_resolution_read (splay_tree file_ids, FILE *resolution, lto_file *file)
328 {
329   /* We require that objects in the resolution file are in the same
330      order as the lto1 command line. */
331   unsigned int name_len;
332   char *obj_name;
333   unsigned int num_symbols;
334   unsigned int i;
335   struct lto_file_decl_data *file_data;
336   unsigned max_index = 0;
337   splay_tree_node nd = NULL; 
338
339   if (!resolution)
340     return;
341
342   name_len = strlen (file->filename);
343   obj_name = XNEWVEC (char, name_len + 1);
344   fscanf (resolution, " ");   /* Read white space. */
345
346   fread (obj_name, sizeof (char), name_len, resolution);
347   obj_name[name_len] = '\0';
348   if (strcmp (obj_name, file->filename) != 0)
349     internal_error ("unexpected file name %s in linker resolution file. "
350                     "Expected %s", obj_name, file->filename);
351   if (file->offset != 0)
352     {
353       int t;
354       char offset_p[17];
355       int64_t offset;
356       t = fscanf (resolution, "@0x%16s", offset_p);
357       if (t != 1)
358         internal_error ("could not parse file offset");
359       offset = lto_parse_hex (offset_p);
360       if (offset != file->offset)
361         internal_error ("unexpected offset");
362     }
363
364   free (obj_name);
365
366   fscanf (resolution, "%u", &num_symbols);
367
368   for (i = 0; i < num_symbols; i++)
369     {
370       int t;
371       unsigned index, id;
372       char r_str[27];
373       enum ld_plugin_symbol_resolution r = (enum ld_plugin_symbol_resolution) 0;
374       unsigned int j;
375       unsigned int lto_resolution_str_len =
376         sizeof (lto_resolution_str) / sizeof (char *);
377
378       t = fscanf (resolution, "%u %x %26s %*[^\n]\n", &index, &id, r_str);
379       if (t != 3)
380         internal_error ("invalid line in the resolution file");
381       if (index > max_index)
382         max_index = index;
383
384       for (j = 0; j < lto_resolution_str_len; j++)
385         {
386           if (strcmp (lto_resolution_str[j], r_str) == 0)
387             {
388               r = (enum ld_plugin_symbol_resolution) j;
389               break;
390             }
391         }
392       if (j == lto_resolution_str_len)
393         internal_error ("invalid resolution in the resolution file");
394
395       if (!(nd && nd->key == id))
396         {
397           nd = splay_tree_lookup (file_ids, id);
398           if (nd == NULL)
399             internal_error ("resolution sub id %x not in object file", id);
400         }
401
402       file_data = (struct lto_file_decl_data *)nd->value;
403       if (cgraph_dump_file)
404         fprintf (cgraph_dump_file, "Adding resolution %u %u to id %x\n",
405                  index, r, file_data->id);
406       VEC_safe_grow_cleared (ld_plugin_symbol_resolution_t, heap, 
407                              file_data->resolutions,
408                              max_index + 1);
409       VEC_replace (ld_plugin_symbol_resolution_t, 
410                    file_data->resolutions, index, r);
411     }
412 }
413
414 /* Is the name for a id'ed LTO section? */
415
416 static int 
417 lto_section_with_id (const char *name, unsigned *id)
418 {
419   const char *s;
420
421   if (strncmp (name, LTO_SECTION_NAME_PREFIX, strlen (LTO_SECTION_NAME_PREFIX)))
422     return 0;
423   s = strrchr (name, '.');
424   return s && sscanf (s, ".%x", id) == 1;
425 }
426
427 /* Create file_data of each sub file id */
428
429 static int 
430 create_subid_section_table (void **slot, void *data)
431 {
432   struct lto_section_slot s_slot, *new_slot;
433   struct lto_section_slot *ls = *(struct lto_section_slot **)slot;
434   splay_tree file_ids = (splay_tree)data;
435   unsigned id;
436   splay_tree_node nd;
437   void **hash_slot;
438   char *new_name;
439   struct lto_file_decl_data *file_data;
440
441   if (!lto_section_with_id (ls->name, &id))
442     return 1;
443   
444   /* Find hash table of sub module id */
445   nd = splay_tree_lookup (file_ids, id);
446   if (nd != NULL)
447     {
448       file_data = (struct lto_file_decl_data *)nd->value;
449     }
450   else
451     {
452       file_data = ggc_alloc_lto_file_decl_data ();
453       memset(file_data, 0, sizeof (struct lto_file_decl_data));
454       file_data->id = id;
455       file_data->section_hash_table = lto_obj_create_section_hash_table ();;
456       splay_tree_insert (file_ids, id, (splay_tree_value)file_data);
457     }
458
459   /* Copy section into sub module hash table */
460   new_name = XDUPVEC (char, ls->name, strlen (ls->name) + 1);
461   s_slot.name = new_name;
462   hash_slot = htab_find_slot (file_data->section_hash_table, &s_slot, INSERT);
463   gcc_assert (*hash_slot == NULL);
464
465   new_slot = XDUP (struct lto_section_slot, ls);
466   new_slot->name = new_name;
467   *hash_slot = new_slot;
468   return 1;
469 }
470
471 /* Read declarations and other initializations for a FILE_DATA. */
472
473 static void
474 lto_file_finalize (struct lto_file_decl_data *file_data, lto_file *file)
475 {
476   const char *data;
477   size_t len;
478
479   file_data->renaming_hash_table = lto_create_renaming_table ();
480   file_data->file_name = file->filename;
481   data = lto_get_section_data (file_data, LTO_section_decls, NULL, &len);
482   if (data == NULL)
483     {
484       internal_error ("cannot read LTO decls from %s", file_data->file_name);
485       return;
486     }
487   lto_read_decls (file_data, data, file_data->resolutions);
488   lto_free_section_data (file_data, LTO_section_decls, NULL, data, len);
489 }
490
491 struct lwstate
492 {
493   lto_file *file;
494   struct lto_file_decl_data **file_data;
495   int *count;
496 };
497
498 /* Traverse ids and create a list of file_datas out of it. */      
499
500 static int lto_create_files_from_ids (splay_tree_node node, void *data)
501 {
502   struct lwstate *lw = (struct lwstate *)data;
503   struct lto_file_decl_data *file_data = (struct lto_file_decl_data *)node->value;
504
505   lto_file_finalize (file_data, lw->file);
506   if (cgraph_dump_file)
507     fprintf (cgraph_dump_file, "Creating file %s with sub id %x\n", 
508              file_data->file_name, file_data->id);
509   file_data->next = *lw->file_data;
510   *lw->file_data = file_data;
511   (*lw->count)++;
512   return 0;
513 }
514
515 /* Generate a TREE representation for all types and external decls
516    entities in FILE.  
517
518    Read all of the globals out of the file.  Then read the cgraph
519    and process the .o index into the cgraph nodes so that it can open
520    the .o file to load the functions and ipa information.   */
521
522 static struct lto_file_decl_data *
523 lto_file_read (lto_file *file, FILE *resolution_file, int *count)
524 {
525   struct lto_file_decl_data *file_data = NULL;
526   splay_tree file_ids;
527   htab_t section_hash_table;
528   struct lwstate state;
529   
530   section_hash_table = lto_obj_build_section_table (file);
531
532   /* Find all sub modules in the object and put their sections into new hash
533      tables in a splay tree. */
534   file_ids = splay_tree_new (splay_tree_compare_ints, NULL, NULL);
535   htab_traverse (section_hash_table, create_subid_section_table, file_ids);
536   
537   /* Add resolutions to file ids */
538   lto_resolution_read (file_ids, resolution_file, file);
539
540   /* Finalize each lto file for each submodule in the merged object
541      and create list for returning. */
542   state.file = file;
543   state.file_data = &file_data;
544   state.count = count;
545   splay_tree_foreach (file_ids, lto_create_files_from_ids, &state);
546     
547   splay_tree_delete (file_ids);
548   htab_delete (section_hash_table);
549
550   return file_data;
551 }
552
553 #if HAVE_MMAP_FILE && HAVE_SYSCONF && defined _SC_PAGE_SIZE
554 #define LTO_MMAP_IO 1
555 #endif
556
557 #if LTO_MMAP_IO
558 /* Page size of machine is used for mmap and munmap calls.  */
559 static size_t page_mask;
560 #endif
561
562 /* Get the section data of length LEN from FILENAME starting at
563    OFFSET.  The data segment must be freed by the caller when the
564    caller is finished.  Returns NULL if all was not well.  */
565
566 static char *
567 lto_read_section_data (struct lto_file_decl_data *file_data,
568                        intptr_t offset, size_t len)
569 {
570   char *result;
571   static int fd = -1;
572   static char *fd_name;
573 #if LTO_MMAP_IO
574   intptr_t computed_len;
575   intptr_t computed_offset;
576   intptr_t diff;
577 #endif
578
579   /* Keep a single-entry file-descriptor cache.  The last file we
580      touched will get closed at exit.
581      ???  Eventually we want to add a more sophisticated larger cache
582      or rather fix function body streaming to not stream them in
583      practically random order.  */
584   if (fd != -1
585       && strcmp (fd_name, file_data->file_name) != 0)
586     {
587       free (fd_name);
588       close (fd);
589       fd = -1;
590     }
591   if (fd == -1)
592     {
593       fd_name = xstrdup (file_data->file_name);
594       fd = open (file_data->file_name, O_RDONLY|O_BINARY);
595       if (fd == -1)
596         return NULL;
597     }
598
599 #if LTO_MMAP_IO
600   if (!page_mask)
601     {
602       size_t page_size = sysconf (_SC_PAGE_SIZE);
603       page_mask = ~(page_size - 1);
604     }
605
606   computed_offset = offset & page_mask;
607   diff = offset - computed_offset;
608   computed_len = len + diff;
609
610   result = (char *) mmap (NULL, computed_len, PROT_READ, MAP_PRIVATE,
611                           fd, computed_offset);
612   if (result == MAP_FAILED)
613     return NULL;
614
615   return result + diff;
616 #else
617   result = (char *) xmalloc (len);
618   if (lseek (fd, offset, SEEK_SET) != offset
619       || read (fd, result, len) != (ssize_t) len)
620     {
621       free (result);
622       return NULL;
623     }
624
625   return result;
626 #endif
627 }    
628
629
630 /* Get the section data from FILE_DATA of SECTION_TYPE with NAME.
631    NAME will be NULL unless the section type is for a function
632    body.  */
633
634 static const char *
635 get_section_data (struct lto_file_decl_data *file_data,
636                       enum lto_section_type section_type,
637                       const char *name,
638                       size_t *len)
639 {
640   htab_t section_hash_table = file_data->section_hash_table;
641   struct lto_section_slot *f_slot;
642   struct lto_section_slot s_slot;
643   const char *section_name = lto_get_section_name (section_type, name, file_data);
644   char *data = NULL;
645
646   *len = 0;
647   s_slot.name = section_name;
648   f_slot = (struct lto_section_slot *) htab_find (section_hash_table, &s_slot);
649   if (f_slot)
650     {
651       data = lto_read_section_data (file_data, f_slot->start, f_slot->len);
652       *len = f_slot->len;
653     }
654
655   free (CONST_CAST (char *, section_name));
656   return data;
657 }
658
659
660 /* Free the section data from FILE_DATA of SECTION_TYPE with NAME that
661    starts at OFFSET and has LEN bytes.  */
662
663 static void
664 free_section_data (struct lto_file_decl_data *file_data ATTRIBUTE_UNUSED,
665                    enum lto_section_type section_type ATTRIBUTE_UNUSED,
666                    const char *name ATTRIBUTE_UNUSED,
667                    const char *offset, size_t len ATTRIBUTE_UNUSED)
668 {
669 #if LTO_MMAP_IO
670   intptr_t computed_len;
671   intptr_t computed_offset;
672   intptr_t diff;
673 #endif
674
675 #if LTO_MMAP_IO
676   computed_offset = ((intptr_t) offset) & page_mask;
677   diff = (intptr_t) offset - computed_offset;
678   computed_len = len + diff;
679
680   munmap ((caddr_t) computed_offset, computed_len);
681 #else
682   free (CONST_CAST(char *, offset));
683 #endif
684 }
685
686 /* Structure describing ltrans partitions.  */
687
688 struct GTY (()) ltrans_partition_def
689 {
690   cgraph_node_set cgraph_set;
691   varpool_node_set varpool_set;
692   const char * GTY ((skip)) name;
693   int insns;
694 };
695
696 typedef struct ltrans_partition_def *ltrans_partition;
697 DEF_VEC_P(ltrans_partition);
698 DEF_VEC_ALLOC_P(ltrans_partition,gc);
699
700 static GTY (()) VEC(ltrans_partition, gc) *ltrans_partitions;
701
702 static void add_cgraph_node_to_partition (ltrans_partition part, struct cgraph_node *node);
703 static void add_varpool_node_to_partition (ltrans_partition part, struct varpool_node *vnode);
704
705 /* Create new partition with name NAME.  */
706 static ltrans_partition
707 new_partition (const char *name)
708 {
709   ltrans_partition part = ggc_alloc_ltrans_partition_def ();
710   part->cgraph_set = cgraph_node_set_new ();
711   part->varpool_set = varpool_node_set_new ();
712   part->name = name;
713   part->insns = 0;
714   VEC_safe_push (ltrans_partition, gc, ltrans_partitions, part);
715   return part;
716 }
717
718 /* See all references that go to comdat objects and bring them into partition too.  */
719 static void
720 add_references_to_partition (ltrans_partition part, struct ipa_ref_list *refs)
721 {
722   int i;
723   struct ipa_ref *ref;
724   for (i = 0; ipa_ref_list_reference_iterate (refs, i, ref); i++)
725     {
726       if (ref->refered_type == IPA_REF_CGRAPH
727           && DECL_COMDAT (ipa_ref_node (ref)->decl)
728           && !cgraph_node_in_set_p (ipa_ref_node (ref), part->cgraph_set))
729         add_cgraph_node_to_partition (part, ipa_ref_node (ref));
730       else
731         if (ref->refered_type == IPA_REF_VARPOOL
732             && DECL_COMDAT (ipa_ref_varpool_node (ref)->decl)
733             && !varpool_node_in_set_p (ipa_ref_varpool_node (ref), part->varpool_set))
734           add_varpool_node_to_partition (part, ipa_ref_varpool_node (ref));
735     }
736 }
737
738 /* Add NODE to partition as well as the inline callees and referred comdats into partition PART. */
739
740 static void
741 add_cgraph_node_to_partition (ltrans_partition part, struct cgraph_node *node)
742 {
743   struct cgraph_edge *e;
744
745   part->insns += node->local.inline_summary.self_size;
746
747   if (node->aux)
748     {
749       node->in_other_partition = 1;
750       if (cgraph_dump_file)
751         fprintf (cgraph_dump_file, "Node %s/%i now used in multiple partitions\n",
752                  cgraph_node_name (node), node->uid);
753     }
754   node->aux = (void *)((size_t)node->aux + 1);
755
756   cgraph_node_set_add (part->cgraph_set, node);
757
758   for (e = node->callees; e; e = e->next_callee)
759     if ((!e->inline_failed || DECL_COMDAT (e->callee->decl))
760         && !cgraph_node_in_set_p (e->callee, part->cgraph_set))
761       add_cgraph_node_to_partition (part, e->callee);
762
763   add_references_to_partition (part, &node->ref_list);
764
765   if (node->same_comdat_group
766       && !cgraph_node_in_set_p (node->same_comdat_group, part->cgraph_set))
767     add_cgraph_node_to_partition (part, node->same_comdat_group);
768 }
769
770 /* Add VNODE to partition as well as comdat references partition PART. */
771
772 static void
773 add_varpool_node_to_partition (ltrans_partition part, struct varpool_node *vnode)
774 {
775   varpool_node_set_add (part->varpool_set, vnode);
776
777   if (vnode->aux)
778     {
779       vnode->in_other_partition = 1;
780       if (cgraph_dump_file)
781         fprintf (cgraph_dump_file, "Varpool node %s now used in multiple partitions\n",
782                  varpool_node_name (vnode));
783     }
784   vnode->aux = (void *)((size_t)vnode->aux + 1);
785
786   add_references_to_partition (part, &vnode->ref_list);
787
788   if (vnode->same_comdat_group
789       && !varpool_node_in_set_p (vnode->same_comdat_group, part->varpool_set))
790     add_varpool_node_to_partition (part, vnode->same_comdat_group);
791 }
792
793 /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
794    and number of varpool nodes is N_VARPOOL_NODES.  */
795
796 static void
797 undo_partition (ltrans_partition partition, unsigned int n_cgraph_nodes,
798                 unsigned int n_varpool_nodes)
799 {
800   while (VEC_length (cgraph_node_ptr, partition->cgraph_set->nodes) >
801          n_cgraph_nodes)
802     {
803       struct cgraph_node *node = VEC_index (cgraph_node_ptr,
804                                             partition->cgraph_set->nodes,
805                                             n_cgraph_nodes);
806       partition->insns -= node->local.inline_summary.self_size;
807       cgraph_node_set_remove (partition->cgraph_set, node);
808       node->aux = (void *)((size_t)node->aux - 1);
809     }
810   while (VEC_length (varpool_node_ptr, partition->varpool_set->nodes) >
811          n_varpool_nodes)
812     {
813       struct varpool_node *node = VEC_index (varpool_node_ptr,
814                                              partition->varpool_set->nodes,
815                                              n_varpool_nodes);
816       varpool_node_set_remove (partition->varpool_set, node);
817       node->aux = (void *)((size_t)node->aux - 1);
818     }
819 }
820
821 /* Return true if NODE should be partitioned.
822    This means that partitioning algorithm should put NODE into one of partitions.
823    This apply to most functions with bodies.  Functions that are not partitions
824    are put into every unit needing them.  This is the case of i.e. COMDATs.  */
825
826 static bool
827 partition_cgraph_node_p (struct cgraph_node *node)
828 {
829   /* We will get proper partition based on function they are inlined to.  */
830   if (node->global.inlined_to)
831     return false;
832   /* Nodes without a body do not need partitioning.  */
833   if (!node->analyzed)
834     return false;
835   /* Extern inlines and comdat are always only in partitions they are needed.  */
836   if (DECL_EXTERNAL (node->decl)
837       || (DECL_COMDAT (node->decl)
838           && !cgraph_used_from_object_file_p (node)))
839     return false;
840   if (lookup_attribute ("weakref", DECL_ATTRIBUTES (node->decl)))
841     return false;
842   return true;
843 }
844
845 /* Return true if VNODE should be partitioned. 
846    This means that partitioning algorithm should put VNODE into one of partitions. */
847
848 static bool
849 partition_varpool_node_p (struct varpool_node *vnode)
850 {
851   if (vnode->alias || !vnode->needed)
852     return false;
853   /* Constant pool and comdat are always only in partitions they are needed.  */
854   if (DECL_IN_CONSTANT_POOL (vnode->decl)
855       || (DECL_COMDAT (vnode->decl)
856           && !vnode->force_output
857           && !varpool_used_from_object_file_p (vnode)))
858     return false;
859   if (lookup_attribute ("weakref", DECL_ATTRIBUTES (vnode->decl)))
860     return false;
861   return true;
862 }
863
864 /* Group cgrah nodes by input files.  This is used mainly for testing
865    right now.  */
866
867 static void
868 lto_1_to_1_map (void)
869 {
870   struct cgraph_node *node;
871   struct varpool_node *vnode;
872   struct lto_file_decl_data *file_data;
873   struct pointer_map_t *pmap;
874   ltrans_partition partition;
875   void **slot;
876   int npartitions = 0;
877
878   timevar_push (TV_WHOPR_WPA);
879
880   pmap = pointer_map_create ();
881
882   for (node = cgraph_nodes; node; node = node->next)
883     {
884       if (!partition_cgraph_node_p (node))
885         continue;
886
887       file_data = node->local.lto_file_data;
888       gcc_assert (!node->same_body_alias);
889
890       if (file_data)
891         {
892           slot = pointer_map_contains (pmap, file_data);
893           if (slot)
894             partition = (ltrans_partition) *slot;
895           else
896             {
897               partition = new_partition (file_data->file_name);
898               slot = pointer_map_insert (pmap, file_data);
899               *slot = partition;
900               npartitions++;
901             }
902         }
903       else if (!file_data
904                && VEC_length (ltrans_partition, ltrans_partitions))
905         partition = VEC_index (ltrans_partition, ltrans_partitions, 0);
906       else
907         {
908           partition = new_partition ("");
909           slot = pointer_map_insert (pmap, NULL);
910           *slot = partition;
911           npartitions++;
912         }
913
914       if (!node->aux)
915         add_cgraph_node_to_partition (partition, node);
916     }
917
918   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
919     {
920       if (!partition_varpool_node_p (vnode))
921         continue;
922       file_data = vnode->lto_file_data;
923       slot = pointer_map_contains (pmap, file_data);
924       if (slot)
925         partition = (ltrans_partition) *slot;
926       else
927         {
928           partition = new_partition (file_data->file_name);
929           slot = pointer_map_insert (pmap, file_data);
930           *slot = partition;
931           npartitions++;
932         }
933
934       if (!vnode->aux)
935         add_varpool_node_to_partition (partition, vnode);
936     }
937   for (node = cgraph_nodes; node; node = node->next)
938     node->aux = NULL;
939   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
940     vnode->aux = NULL;
941
942   /* If the cgraph is empty, create one cgraph node set so that there is still
943      an output file for any variables that need to be exported in a DSO.  */
944   if (!npartitions)
945     new_partition ("empty");
946
947   pointer_map_destroy (pmap);
948
949   timevar_pop (TV_WHOPR_WPA);
950
951   lto_stats.num_cgraph_partitions += VEC_length (ltrans_partition, 
952                                                  ltrans_partitions);
953 }
954
955
956 /* Group cgraph nodes in qually sized partitions.
957
958    The algorithm deciding paritions are simple: nodes are taken in predefined
959    order.  The order correspond to order we wish to have functions in final
960    output.  In future this will be given by function reordering pass, but at
961    the moment we use topological order that serve a good approximation.
962
963    The goal is to partition this linear order into intervals (partitions) such
964    that all partitions have approximately the same size and that the number of
965    callgraph or IPA reference edgess crossing boundaries is minimal.
966
967    This is a lot faster (O(n) in size of callgraph) than algorithms doing
968    priority based graph clustering that are generally O(n^2) and since WHOPR
969    is designed to make things go well across partitions, it leads to good results.
970
971    We compute the expected size of partition as
972    max (total_size / lto_partitions, min_partition_size).
973    We use dynamic expected size of partition, so small programs
974    are partitioning into enough partitions to allow use of multiple CPUs while
975    large programs are not partitioned too much. Creating too many partition
976    increase streaming overhead significandly.
977
978    In the future we would like to bound maximal size of partition to avoid
979    ltrans stage consuming too much memory.  At the moment however WPA stage is
980    most memory intensive phase at large benchmark since too many types and
981    declarations are read into memory.
982
983    The function implement simple greedy algorithm.  Nodes are begin added into
984    current partition until 3/4th of expected partition size is reached.
985    After this threshold we keep track of boundary size (number of edges going to
986    other partitions) and continue adding functions until the current partition
987    grows into a double of expected partition size.  Then the process is undone
988    till the point when minimal ration of boundary size and in partition calls
989    was reached.  */
990
991 static void
992 lto_balanced_map (void)
993 {
994   int n_nodes = 0;
995   struct cgraph_node **postorder =
996     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
997   struct cgraph_node **order = XNEWVEC (struct cgraph_node *, cgraph_max_uid);
998   int i, postorder_len;
999   struct cgraph_node *node;
1000   int total_size = 0, best_total_size = 0;
1001   int partition_size;
1002   ltrans_partition partition;
1003   unsigned int last_visited_cgraph_node = 0, last_visited_varpool_node = 0;
1004   struct varpool_node *vnode;
1005   int cost = 0, internal = 0;
1006   int best_n_nodes = 0, best_n_varpool_nodes = 0, best_i = 0, best_cost =
1007     INT_MAX, best_internal = 0;
1008   int npartitions;
1009
1010   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
1011     gcc_assert (!vnode->aux);
1012   /* Until we have better ordering facility, use toplogical order.
1013      Include only nodes we will partition and compute estimate of program
1014      size.  Note that since nodes that are not partitioned might be put into
1015      multiple partitions, this is just an estimate of real size.  This is why
1016      we keep partition_size updated after every partition is finalized.  */
1017   postorder_len = cgraph_postorder (postorder);
1018   for (i = 0; i < postorder_len; i++)
1019     {
1020       node = postorder[i];
1021       if (partition_cgraph_node_p (node))
1022         {
1023           order[n_nodes++] = node;
1024           total_size += node->global.size;
1025         }
1026     }
1027   free (postorder);
1028
1029   /* Compute partition size and create the first partition.  */
1030   partition_size = total_size / PARAM_VALUE (PARAM_LTO_PARTITIONS);
1031   if (partition_size < PARAM_VALUE (MIN_PARTITION_SIZE))
1032     partition_size = PARAM_VALUE (MIN_PARTITION_SIZE);
1033   npartitions = 1;
1034   partition = new_partition ("");
1035   if (cgraph_dump_file)
1036     fprintf (cgraph_dump_file, "Total unit size: %i, partition size: %i\n",
1037              total_size, partition_size);
1038
1039   for (i = 0; i < n_nodes; i++)
1040     {
1041       if (!order[i]->aux)
1042         add_cgraph_node_to_partition (partition, order[i]);
1043       total_size -= order[i]->global.size;
1044
1045       /* Once we added a new node to the partition, we also want to add
1046          all referenced variables unless they was already added into some
1047          earlier partition.
1048          add_cgraph_node_to_partition adds possibly multiple nodes and
1049          variables that are needed to satisfy needs of ORDER[i].
1050          We remember last visited cgraph and varpool node from last iteration
1051          of outer loop that allows us to process every new addition. 
1052
1053          At the same time we compute size of the boundary into COST.  Every
1054          callgraph or IPA reference edge leaving the partition contributes into
1055          COST.  Every edge inside partition was earlier computed as one leaving
1056          it and thus we need to subtract it from COST.  */
1057       while (last_visited_cgraph_node <
1058              VEC_length (cgraph_node_ptr, partition->cgraph_set->nodes)
1059              || last_visited_varpool_node < VEC_length (varpool_node_ptr,
1060                                                         partition->varpool_set->
1061                                                         nodes))
1062         {
1063           struct ipa_ref_list *refs;
1064           int j;
1065           struct ipa_ref *ref;
1066           bool cgraph_p = false;
1067
1068           if (last_visited_cgraph_node <
1069               VEC_length (cgraph_node_ptr, partition->cgraph_set->nodes))
1070             {
1071               struct cgraph_edge *edge;
1072
1073               cgraph_p = true;
1074               node = VEC_index (cgraph_node_ptr, partition->cgraph_set->nodes,
1075                                 last_visited_cgraph_node);
1076               refs = &node->ref_list;
1077
1078               last_visited_cgraph_node++;
1079
1080               gcc_assert (node->analyzed);
1081
1082               /* Compute boundary cost of callgrpah edges.  */
1083               for (edge = node->callees; edge; edge = edge->next_callee)
1084                 if (edge->callee->analyzed)
1085                   {
1086                     int edge_cost = edge->frequency;
1087                     cgraph_node_set_iterator csi;
1088
1089                     if (!edge_cost)
1090                       edge_cost = 1;
1091                     gcc_assert (edge_cost > 0);
1092                     csi = cgraph_node_set_find (partition->cgraph_set, edge->callee);
1093                     if (!csi_end_p (csi)
1094                         && csi.index < last_visited_cgraph_node - 1)
1095                       cost -= edge_cost, internal+= edge_cost;
1096                     else
1097                       cost += edge_cost;
1098                   }
1099               for (edge = node->callers; edge; edge = edge->next_caller)
1100                 {
1101                   int edge_cost = edge->frequency;
1102                   cgraph_node_set_iterator csi;
1103
1104                   gcc_assert (edge->caller->analyzed);
1105                   if (!edge_cost)
1106                     edge_cost = 1;
1107                   gcc_assert (edge_cost > 0);
1108                   csi = cgraph_node_set_find (partition->cgraph_set, edge->caller);
1109                   if (!csi_end_p (csi)
1110                       && csi.index < last_visited_cgraph_node)
1111                     cost -= edge_cost;
1112                   else
1113                     cost += edge_cost;
1114                 }
1115             }
1116           else
1117             {
1118               refs =
1119                 &VEC_index (varpool_node_ptr, partition->varpool_set->nodes,
1120                             last_visited_varpool_node)->ref_list;
1121               last_visited_varpool_node++;
1122             }
1123
1124           /* Compute boundary cost of IPA REF edges and at the same time look into
1125              variables referenced from current partition and try to add them.  */
1126           for (j = 0; ipa_ref_list_reference_iterate (refs, j, ref); j++)
1127             if (ref->refered_type == IPA_REF_VARPOOL)
1128               {
1129                 varpool_node_set_iterator vsi;
1130
1131                 vnode = ipa_ref_varpool_node (ref);
1132                 if (!vnode->finalized)
1133                   continue;
1134                 if (!vnode->aux && partition_varpool_node_p (vnode))
1135                   add_varpool_node_to_partition (partition, vnode);
1136                 vsi = varpool_node_set_find (partition->varpool_set, vnode);
1137                 if (!vsi_end_p (vsi)
1138                     && vsi.index < last_visited_varpool_node - !cgraph_p)
1139                   cost--, internal++;
1140                 else
1141                   cost++;
1142               }
1143             else
1144               {
1145                 cgraph_node_set_iterator csi;
1146
1147                 node = ipa_ref_node (ref);
1148                 if (!node->analyzed)
1149                   continue;
1150                 csi = cgraph_node_set_find (partition->cgraph_set, node);
1151                 if (!csi_end_p (csi)
1152                     && csi.index < last_visited_cgraph_node - cgraph_p)
1153                   cost--, internal++;
1154                 else
1155                   cost++;
1156               }
1157           for (j = 0; ipa_ref_list_refering_iterate (refs, j, ref); j++)
1158             if (ref->refering_type == IPA_REF_VARPOOL)
1159               {
1160                 varpool_node_set_iterator vsi;
1161
1162                 vnode = ipa_ref_refering_varpool_node (ref);
1163                 gcc_assert (vnode->finalized);
1164                 if (!vnode->aux && partition_varpool_node_p (vnode))
1165                   add_varpool_node_to_partition (partition, vnode);
1166                 vsi = varpool_node_set_find (partition->varpool_set, vnode);
1167                 if (!vsi_end_p (vsi)
1168                     && vsi.index < last_visited_varpool_node)
1169                   cost--;
1170                 else
1171                   cost++;
1172               }
1173             else
1174               {
1175                 cgraph_node_set_iterator csi;
1176
1177                 node = ipa_ref_refering_node (ref);
1178                 gcc_assert (node->analyzed);
1179                 csi = cgraph_node_set_find (partition->cgraph_set, node);
1180                 if (!csi_end_p (csi)
1181                     && csi.index < last_visited_cgraph_node)
1182                   cost--;
1183                 else
1184                   cost++;
1185               }
1186         }
1187
1188       /* If the partition is large enough, start looking for smallest boundary cost.  */
1189       if (partition->insns < partition_size * 3 / 4
1190           || best_cost == INT_MAX
1191           || ((!cost 
1192                || (best_internal * (HOST_WIDE_INT) cost
1193                    > (internal * (HOST_WIDE_INT)best_cost)))
1194               && partition->insns < partition_size * 5 / 4))
1195         {
1196           best_cost = cost;
1197           best_internal = internal;
1198           best_i = i;
1199           best_n_nodes = VEC_length (cgraph_node_ptr,
1200                                      partition->cgraph_set->nodes);
1201           best_n_varpool_nodes = VEC_length (varpool_node_ptr,
1202                                              partition->varpool_set->nodes);
1203           best_total_size = total_size;
1204         }
1205       if (cgraph_dump_file)
1206         fprintf (cgraph_dump_file, "Step %i: added %s/%i, size %i, cost %i/%i best %i/%i, step %i\n", i,
1207                  cgraph_node_name (order[i]), order[i]->uid, partition->insns, cost, internal,
1208                  best_cost, best_internal, best_i);
1209       /* Partition is too large, unwind into step when best cost was reached and
1210          start new partition.  */
1211       if (partition->insns > 2 * partition_size)
1212         {
1213           if (best_i != i)
1214             {
1215               if (cgraph_dump_file)
1216                 fprintf (cgraph_dump_file, "Unwinding %i insertions to step %i\n",
1217                          i - best_i, best_i);
1218               undo_partition (partition, best_n_nodes, best_n_varpool_nodes);
1219             }
1220           i = best_i;
1221           /* When we are finished, avoid creating empty partition.  */
1222           if (i == n_nodes - 1)
1223             break;
1224           partition = new_partition ("");
1225           last_visited_cgraph_node = 0;
1226           last_visited_varpool_node = 0;
1227           total_size = best_total_size;
1228           cost = 0;
1229
1230           if (cgraph_dump_file)
1231             fprintf (cgraph_dump_file, "New partition\n");
1232           best_n_nodes = 0;
1233           best_n_varpool_nodes = 0;
1234           best_cost = INT_MAX;
1235
1236           /* Since the size of partitions is just approximate, update the size after
1237              we finished current one.  */
1238           if (npartitions < PARAM_VALUE (PARAM_LTO_PARTITIONS))
1239             partition_size = total_size
1240               / (PARAM_VALUE (PARAM_LTO_PARTITIONS) - npartitions);
1241           else
1242             partition_size = INT_MAX;
1243
1244           if (partition_size < PARAM_VALUE (MIN_PARTITION_SIZE))
1245             partition_size = PARAM_VALUE (MIN_PARTITION_SIZE);
1246           npartitions ++;
1247         }
1248     }
1249
1250   /* Varables that are not reachable from the code go into last partition.  */
1251   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
1252     if (partition_varpool_node_p (vnode) && !vnode->aux)
1253       add_varpool_node_to_partition (partition, vnode);
1254   free (order);
1255 }
1256
1257 /* Promote variable VNODE to be static.  */
1258
1259 static bool
1260 promote_var (struct varpool_node *vnode)
1261 {
1262   if (TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl))
1263     return false;
1264   gcc_assert (flag_wpa);
1265   TREE_PUBLIC (vnode->decl) = 1;
1266   DECL_VISIBILITY (vnode->decl) = VISIBILITY_HIDDEN;
1267   DECL_VISIBILITY_SPECIFIED (vnode->decl) = true;
1268   if (cgraph_dump_file)
1269     fprintf (cgraph_dump_file,
1270             "Promoting var as hidden: %s\n", varpool_node_name (vnode));
1271   return true;
1272 }
1273
1274 /* Promote function NODE to be static.  */
1275
1276 static bool
1277 promote_fn (struct cgraph_node *node)
1278 {
1279   gcc_assert (flag_wpa);
1280   if (TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl))
1281     return false;
1282   TREE_PUBLIC (node->decl) = 1;
1283   DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN;
1284   DECL_VISIBILITY_SPECIFIED (node->decl) = true;
1285   if (node->same_body)
1286     {
1287       struct cgraph_node *alias;
1288       for (alias = node->same_body;
1289            alias; alias = alias->next)
1290         {
1291           TREE_PUBLIC (alias->decl) = 1;
1292           DECL_VISIBILITY (alias->decl) = VISIBILITY_HIDDEN;
1293           DECL_VISIBILITY_SPECIFIED (alias->decl) = true;
1294         }
1295     }
1296   if (cgraph_dump_file)
1297     fprintf (cgraph_dump_file,
1298              "Promoting function as hidden: %s/%i\n",
1299              cgraph_node_name (node), node->uid);
1300   return true;
1301 }
1302
1303 /* Find out all static decls that need to be promoted to global because
1304    of cross file sharing.  This function must be run in the WPA mode after
1305    all inlinees are added.  */
1306
1307 static void
1308 lto_promote_cross_file_statics (void)
1309 {
1310   struct varpool_node *vnode;
1311   unsigned i, n_sets;
1312   cgraph_node_set set;
1313   varpool_node_set vset;
1314   cgraph_node_set_iterator csi;
1315   varpool_node_set_iterator vsi;
1316   VEC(varpool_node_ptr, heap) *promoted_initializers = NULL;
1317   struct pointer_set_t *inserted = pointer_set_create ();
1318
1319   gcc_assert (flag_wpa);
1320
1321   n_sets = VEC_length (ltrans_partition, ltrans_partitions);
1322   for (i = 0; i < n_sets; i++)
1323     {
1324       ltrans_partition part = VEC_index (ltrans_partition, ltrans_partitions, i);
1325       set = part->cgraph_set;
1326       vset = part->varpool_set;
1327
1328       /* If node has either address taken (and we have no clue from where)
1329          or it is called from other partition, it needs to be globalized.  */
1330       for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
1331         {
1332           struct cgraph_node *node = csi_node (csi);
1333           if (node->local.externally_visible)
1334             continue;
1335           if (node->global.inlined_to)
1336             continue;
1337           if ((!DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1338               && (referenced_from_other_partition_p (&node->ref_list, set, vset)
1339                   || reachable_from_other_partition_p (node, set)))
1340             promote_fn (node);
1341         }
1342       for (vsi = vsi_start (vset); !vsi_end_p (vsi); vsi_next (&vsi))
1343         {
1344           vnode = vsi_node (vsi);
1345           /* Constant pool references use internal labels and thus can not
1346              be made global.  It is sensible to keep those ltrans local to
1347              allow better optimization.  */
1348           if (!DECL_IN_CONSTANT_POOL (vnode->decl) && !DECL_COMDAT (vnode->decl)
1349               && !vnode->externally_visible && vnode->analyzed
1350               && referenced_from_other_partition_p (&vnode->ref_list,
1351                                                     set, vset))
1352             promote_var (vnode);
1353         }
1354
1355       /* We export initializers of read-only var into each partition
1356          referencing it.  Folding might take declarations from the
1357          initializers and use it; so everything referenced from the
1358          initializers needs can be accessed from this partition after
1359          folding.
1360
1361          This means that we need to promote all variables and functions
1362          referenced from all initializers from readonly vars referenced
1363          from this partition that are not in this partition.
1364          This needs to be done recursively.  */
1365       for (vnode = varpool_nodes; vnode; vnode = vnode->next)
1366         if (const_value_known_p (vnode->decl)
1367             && DECL_INITIAL (vnode->decl)
1368             && !varpool_node_in_set_p (vnode, vset)
1369             && referenced_from_this_partition_p (&vnode->ref_list, set, vset)
1370             && !pointer_set_insert (inserted, vnode))
1371         VEC_safe_push (varpool_node_ptr, heap, promoted_initializers, vnode);
1372       while (!VEC_empty (varpool_node_ptr, promoted_initializers))
1373         {
1374           int i;
1375           struct ipa_ref *ref;
1376
1377           vnode = VEC_pop (varpool_node_ptr, promoted_initializers);
1378           for (i = 0; ipa_ref_list_reference_iterate (&vnode->ref_list, i, ref); i++)
1379             {
1380               if (ref->refered_type == IPA_REF_CGRAPH)
1381                 {
1382                   struct cgraph_node *n = ipa_ref_node (ref);
1383                   gcc_assert (!n->global.inlined_to);
1384                   if (!n->local.externally_visible
1385                       && !cgraph_node_in_set_p (n, set))
1386                     promote_fn (n);
1387                 }
1388               else
1389                 {
1390                   struct varpool_node *v = ipa_ref_varpool_node (ref);
1391                   if (varpool_node_in_set_p (v, vset))
1392                     continue;
1393                   /* Constant pool references use internal labels and thus can not
1394                      be made global.  It is sensible to keep those ltrans local to
1395                      allow better optimization.  */
1396                   if (DECL_IN_CONSTANT_POOL (v->decl))
1397                     {
1398                       if (!pointer_set_insert (inserted, vnode))
1399                         VEC_safe_push (varpool_node_ptr, heap,
1400                                        promoted_initializers, v);
1401                     }
1402                   else if (!DECL_IN_CONSTANT_POOL (v->decl)
1403                            && !v->externally_visible && v->analyzed)
1404                     {
1405                       if (promote_var (v)
1406                           && DECL_INITIAL (v->decl)
1407                           && const_value_known_p (v->decl)
1408                           && !pointer_set_insert (inserted, vnode))
1409                         VEC_safe_push (varpool_node_ptr, heap,
1410                                        promoted_initializers, v);
1411                     }
1412                 }
1413             }
1414         }
1415     }
1416   pointer_set_destroy (inserted);
1417 }
1418
1419 static lto_file *current_lto_file;
1420
1421 /* Helper for qsort; compare partitions and return one with smaller size.
1422    We sort from greatest to smallest so parallel build doesn't stale on the
1423    longest compilation being executed too late.  */
1424
1425 static int
1426 cmp_partitions (const void *a, const void *b)
1427 {
1428   const struct ltrans_partition_def *pa
1429      = *(struct ltrans_partition_def *const *)a;
1430   const struct ltrans_partition_def *pb
1431      = *(struct ltrans_partition_def *const *)b;
1432   return pb->insns - pa->insns;
1433 }
1434
1435 /* Write all output files in WPA mode and the file with the list of
1436    LTRANS units.  */
1437
1438 static void
1439 lto_wpa_write_files (void)
1440 {
1441   unsigned i, n_sets;
1442   lto_file *file;
1443   cgraph_node_set set;
1444   varpool_node_set vset;
1445   ltrans_partition part;
1446   FILE *ltrans_output_list_stream;
1447   char *temp_filename;
1448   size_t blen;
1449
1450   /* Open the LTRANS output list.  */
1451   if (!ltrans_output_list)
1452     fatal_error ("no LTRANS output list filename provided");
1453   ltrans_output_list_stream = fopen (ltrans_output_list, "w");
1454   if (ltrans_output_list_stream == NULL)
1455     fatal_error ("opening LTRANS output list %s: %m", ltrans_output_list);
1456
1457   timevar_push (TV_WHOPR_WPA);
1458
1459   FOR_EACH_VEC_ELT (ltrans_partition, ltrans_partitions, i, part)
1460     lto_stats.num_output_cgraph_nodes += VEC_length (cgraph_node_ptr,
1461                                                      part->cgraph_set->nodes);
1462
1463   /* Find out statics that need to be promoted
1464      to globals with hidden visibility because they are accessed from multiple
1465      partitions.  */
1466   lto_promote_cross_file_statics ();
1467
1468   timevar_pop (TV_WHOPR_WPA);
1469
1470   timevar_push (TV_WHOPR_WPA_IO);
1471
1472   /* Generate a prefix for the LTRANS unit files.  */
1473   blen = strlen (ltrans_output_list);
1474   temp_filename = (char *) xmalloc (blen + sizeof ("2147483648.o"));
1475   strcpy (temp_filename, ltrans_output_list);
1476   if (blen > sizeof (".out")
1477       && strcmp (temp_filename + blen - sizeof (".out") + 1,
1478                  ".out") == 0)
1479     temp_filename[blen - sizeof (".out") + 1] = '\0';
1480   blen = strlen (temp_filename);
1481
1482   n_sets = VEC_length (ltrans_partition, ltrans_partitions);
1483   VEC_qsort (ltrans_partition, ltrans_partitions, cmp_partitions);
1484   for (i = 0; i < n_sets; i++)
1485     {
1486       size_t len;
1487       ltrans_partition part = VEC_index (ltrans_partition, ltrans_partitions, i);
1488
1489       set = part->cgraph_set;
1490       vset = part->varpool_set;
1491
1492       /* Write all the nodes in SET.  */
1493       sprintf (temp_filename + blen, "%u.o", i);
1494       file = lto_obj_file_open (temp_filename, true);
1495       if (!file)
1496         fatal_error ("lto_obj_file_open() failed");
1497
1498       if (!quiet_flag)
1499         fprintf (stderr, " %s (%s %i insns)", temp_filename, part->name, part->insns);
1500       if (cgraph_dump_file)
1501         {
1502           fprintf (cgraph_dump_file, "Writting partition %s to file %s, %i insns\n",
1503                    part->name, temp_filename, part->insns);
1504           fprintf (cgraph_dump_file, "cgraph nodes:");
1505           dump_cgraph_node_set (cgraph_dump_file, set);
1506           fprintf (cgraph_dump_file, "varpool nodes:");
1507           dump_varpool_node_set (cgraph_dump_file, vset);
1508         }
1509       gcc_assert (cgraph_node_set_nonempty_p (set)
1510                   || varpool_node_set_nonempty_p (vset) || !i);
1511
1512       lto_set_current_out_file (file);
1513
1514       ipa_write_optimization_summaries (set, vset);
1515
1516       lto_set_current_out_file (NULL);
1517       lto_obj_file_close (file);
1518
1519       len = strlen (temp_filename);
1520       if (fwrite (temp_filename, 1, len, ltrans_output_list_stream) < len
1521           || fwrite ("\n", 1, 1, ltrans_output_list_stream) < 1)
1522         fatal_error ("writing to LTRANS output list %s: %m",
1523                      ltrans_output_list);
1524     }
1525
1526   lto_stats.num_output_files += n_sets;
1527
1528   /* Close the LTRANS output list.  */
1529   if (fclose (ltrans_output_list_stream))
1530     fatal_error ("closing LTRANS output list %s: %m", ltrans_output_list);
1531
1532   timevar_pop (TV_WHOPR_WPA_IO);
1533 }
1534
1535
1536 typedef struct {
1537   struct pointer_set_t *seen;
1538 } lto_fixup_data_t;
1539
1540 #define LTO_FIXUP_SUBTREE(t) \
1541   do \
1542     walk_tree (&(t), lto_fixup_tree, data, NULL); \
1543   while (0)
1544
1545 #define LTO_REGISTER_TYPE_AND_FIXUP_SUBTREE(t) \
1546   do \
1547     { \
1548       if (t) \
1549         (t) = gimple_register_type (t); \
1550       walk_tree (&(t), lto_fixup_tree, data, NULL); \
1551     } \
1552   while (0)
1553
1554 static tree lto_fixup_tree (tree *, int *, void *);
1555
1556 /* Return true if T does not need to be fixed up recursively.  */
1557
1558 static inline bool
1559 no_fixup_p (tree t)
1560 {
1561   return (t == NULL
1562           || CONSTANT_CLASS_P (t)
1563           || TREE_CODE (t) == IDENTIFIER_NODE);
1564 }
1565
1566 /* Fix up fields of a tree_common T.  DATA points to fix-up states.  */
1567
1568 static void
1569 lto_fixup_common (tree t, void *data)
1570 {
1571   /* The following re-creates the TYPE_REFERENCE_TO and TYPE_POINTER_TO
1572      lists.  We do not stream TYPE_REFERENCE_TO, TYPE_POINTER_TO or
1573      TYPE_NEXT_PTR_TO and TYPE_NEXT_REF_TO.
1574      First remove us from any pointer list we are on.  */
1575   if (TREE_CODE (t) == POINTER_TYPE)
1576     {
1577       if (TYPE_POINTER_TO (TREE_TYPE (t)) == t)
1578         TYPE_POINTER_TO (TREE_TYPE (t)) = TYPE_NEXT_PTR_TO (t);
1579       else
1580         {
1581           tree tem = TYPE_POINTER_TO (TREE_TYPE (t));
1582           while (tem && TYPE_NEXT_PTR_TO (tem) != t)
1583             tem = TYPE_NEXT_PTR_TO (tem);
1584           if (tem)
1585             TYPE_NEXT_PTR_TO (tem) = TYPE_NEXT_PTR_TO (t);
1586         }
1587       TYPE_NEXT_PTR_TO (t) = NULL_TREE;
1588     }
1589   else if (TREE_CODE (t) == REFERENCE_TYPE)
1590     {
1591       if (TYPE_REFERENCE_TO (TREE_TYPE (t)) == t)
1592         TYPE_REFERENCE_TO (TREE_TYPE (t)) = TYPE_NEXT_REF_TO (t);
1593       else
1594         {
1595           tree tem = TYPE_REFERENCE_TO (TREE_TYPE (t));
1596           while (tem && TYPE_NEXT_REF_TO (tem) != t)
1597             tem = TYPE_NEXT_REF_TO (tem);
1598           if (tem)
1599             TYPE_NEXT_REF_TO (tem) = TYPE_NEXT_REF_TO (t);
1600         }
1601       TYPE_NEXT_REF_TO (t) = NULL_TREE;
1602     }
1603
1604   /* Fixup our type.  */
1605   LTO_REGISTER_TYPE_AND_FIXUP_SUBTREE (TREE_TYPE (t));
1606
1607   /* Second put us on the list of pointers of the new pointed-to type
1608      if we are a main variant.  This is done in lto_fixup_type after
1609      fixing up our main variant.  */
1610
1611   /* This is not very efficient because we cannot do tail-recursion with
1612      a long chain of trees. */
1613   LTO_FIXUP_SUBTREE (TREE_CHAIN (t));
1614 }
1615
1616 /* Fix up fields of a decl_minimal T.  DATA points to fix-up states.  */
1617
1618 static void
1619 lto_fixup_decl_minimal (tree t, void *data)
1620 {
1621   lto_fixup_common (t, data);
1622   LTO_FIXUP_SUBTREE (DECL_NAME (t));
1623   LTO_FIXUP_SUBTREE (DECL_CONTEXT (t));
1624 }
1625
1626 /* Fix up fields of a decl_common T.  DATA points to fix-up states.  */
1627
1628 static void
1629 lto_fixup_decl_common (tree t, void *data)
1630 {
1631   lto_fixup_decl_minimal (t, data);
1632   LTO_FIXUP_SUBTREE (DECL_SIZE (t));
1633   LTO_FIXUP_SUBTREE (DECL_SIZE_UNIT (t));
1634   LTO_FIXUP_SUBTREE (DECL_INITIAL (t));
1635   LTO_FIXUP_SUBTREE (DECL_ATTRIBUTES (t));
1636   LTO_FIXUP_SUBTREE (DECL_ABSTRACT_ORIGIN (t));
1637 }
1638
1639 /* Fix up fields of a decl_with_vis T.  DATA points to fix-up states.  */
1640
1641 static void
1642 lto_fixup_decl_with_vis (tree t, void *data)
1643 {
1644   lto_fixup_decl_common (t, data);
1645
1646   /* Accessor macro has side-effects, use field-name here. */
1647   LTO_FIXUP_SUBTREE (t->decl_with_vis.assembler_name);
1648
1649   gcc_assert (no_fixup_p (DECL_SECTION_NAME (t)));
1650 }
1651
1652 /* Fix up fields of a decl_non_common T.  DATA points to fix-up states.  */
1653
1654 static void
1655 lto_fixup_decl_non_common (tree t, void *data)
1656 {
1657   lto_fixup_decl_with_vis (t, data);
1658   LTO_FIXUP_SUBTREE (DECL_ARGUMENT_FLD (t));
1659   LTO_FIXUP_SUBTREE (DECL_RESULT_FLD (t));
1660   LTO_FIXUP_SUBTREE (DECL_VINDEX (t));
1661
1662   /* SAVED_TREE should not cleared by now.  Also no accessor for base type. */
1663   gcc_assert (no_fixup_p (t->decl_non_common.saved_tree));
1664 }
1665
1666 /* Fix up fields of a decl_non_common T.  DATA points to fix-up states.  */
1667
1668 static void
1669 lto_fixup_function (tree t, void *data)
1670 {
1671   lto_fixup_decl_non_common (t, data);
1672   LTO_FIXUP_SUBTREE (DECL_FUNCTION_PERSONALITY (t));
1673 }
1674
1675 /* Fix up fields of a field_decl T.  DATA points to fix-up states.  */
1676
1677 static void
1678 lto_fixup_field_decl (tree t, void *data)
1679 {
1680   lto_fixup_decl_common (t, data);
1681   LTO_FIXUP_SUBTREE (DECL_FIELD_OFFSET (t));
1682   LTO_FIXUP_SUBTREE (DECL_BIT_FIELD_TYPE (t));
1683   LTO_FIXUP_SUBTREE (DECL_QUALIFIER (t));
1684   gcc_assert (no_fixup_p (DECL_FIELD_BIT_OFFSET (t)));
1685   LTO_FIXUP_SUBTREE (DECL_FCONTEXT (t));
1686 }
1687
1688 /* Fix up fields of a type T.  DATA points to fix-up states.  */
1689
1690 static void
1691 lto_fixup_type (tree t, void *data)
1692 {
1693   tree tem, mv;
1694
1695   lto_fixup_common (t, data);
1696   LTO_FIXUP_SUBTREE (TYPE_CACHED_VALUES (t));
1697   LTO_FIXUP_SUBTREE (TYPE_SIZE (t));
1698   LTO_FIXUP_SUBTREE (TYPE_SIZE_UNIT (t));
1699   LTO_FIXUP_SUBTREE (TYPE_ATTRIBUTES (t));
1700   LTO_FIXUP_SUBTREE (TYPE_NAME (t));
1701
1702   /* Accessors are for derived node types only. */
1703   if (!POINTER_TYPE_P (t))
1704     LTO_FIXUP_SUBTREE (t->type.minval);
1705   LTO_FIXUP_SUBTREE (t->type.maxval);
1706
1707   /* Accessor is for derived node types only. */
1708   LTO_FIXUP_SUBTREE (t->type.binfo);
1709
1710   if (TYPE_CONTEXT (t))
1711     {
1712       if (TYPE_P (TYPE_CONTEXT (t)))
1713         LTO_REGISTER_TYPE_AND_FIXUP_SUBTREE (TYPE_CONTEXT (t));
1714       else
1715         LTO_FIXUP_SUBTREE (TYPE_CONTEXT (t));
1716     }
1717
1718   /* Compute the canonical type of t and fix that up.  From this point
1719      there are no longer any types with TYPE_STRUCTURAL_EQUALITY_P
1720      and its type-based alias problems.  */
1721   if (!TYPE_CANONICAL (t))
1722     {
1723       TYPE_CANONICAL (t) = gimple_register_canonical_type (t);
1724       LTO_FIXUP_SUBTREE (TYPE_CANONICAL (t));
1725     }
1726
1727   /* The following re-creates proper variant lists while fixing up
1728      the variant leaders.  We do not stream TYPE_NEXT_VARIANT so the
1729      variant list state before fixup is broken.  */
1730
1731   /* Remove us from our main variant list if we are not the variant leader.  */
1732   if (TYPE_MAIN_VARIANT (t) != t)
1733     {
1734       tem = TYPE_MAIN_VARIANT (t);
1735       while (tem && TYPE_NEXT_VARIANT (tem) != t)
1736         tem = TYPE_NEXT_VARIANT (tem);
1737       if (tem)
1738         TYPE_NEXT_VARIANT (tem) = TYPE_NEXT_VARIANT (t);
1739       TYPE_NEXT_VARIANT (t) = NULL_TREE;
1740     }
1741
1742   /* Query our new main variant.  */
1743   mv = gimple_register_type (TYPE_MAIN_VARIANT (t));
1744
1745   /* If we were the variant leader and we get replaced ourselves drop
1746      all variants from our list.  */
1747   if (TYPE_MAIN_VARIANT (t) == t
1748       && mv != t)
1749     {
1750       tem = t;
1751       while (tem)
1752         {
1753           tree tem2 = TYPE_NEXT_VARIANT (tem);
1754           TYPE_NEXT_VARIANT (tem) = NULL_TREE;
1755           tem = tem2;
1756         }
1757     }
1758
1759   /* If we are not our own variant leader link us into our new leaders
1760      variant list.  */
1761   if (mv != t)
1762     {
1763       TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (mv);
1764       TYPE_NEXT_VARIANT (mv) = t;
1765     }
1766
1767   /* Finally adjust our main variant and fix it up.  */
1768   TYPE_MAIN_VARIANT (t) = mv;
1769   LTO_FIXUP_SUBTREE (TYPE_MAIN_VARIANT (t));
1770
1771   /* As the second step of reconstructing the pointer chains put us
1772      on the list of pointers of the new pointed-to type
1773      if we are a main variant.  See lto_fixup_common for the first step.  */
1774   if (TREE_CODE (t) == POINTER_TYPE
1775       && TYPE_MAIN_VARIANT (t) == t)
1776     {
1777       TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (TREE_TYPE (t));
1778       TYPE_POINTER_TO (TREE_TYPE (t)) = t;
1779     }
1780   else if (TREE_CODE (t) == REFERENCE_TYPE
1781            && TYPE_MAIN_VARIANT (t) == t)
1782     {
1783       TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (TREE_TYPE (t));
1784       TYPE_REFERENCE_TO (TREE_TYPE (t)) = t;
1785     }
1786 }
1787
1788 /* Fix up fields of a BINFO T.  DATA points to fix-up states.  */
1789
1790 static void
1791 lto_fixup_binfo (tree t, void *data)
1792 {
1793   unsigned HOST_WIDE_INT i, n;
1794   tree base, saved_base;
1795
1796   lto_fixup_common (t, data);
1797   gcc_assert (no_fixup_p (BINFO_OFFSET (t)));
1798   LTO_FIXUP_SUBTREE (BINFO_VTABLE (t));
1799   LTO_FIXUP_SUBTREE (BINFO_VIRTUALS (t));
1800   LTO_FIXUP_SUBTREE (BINFO_VPTR_FIELD (t));
1801   n = VEC_length (tree, BINFO_BASE_ACCESSES (t));
1802   for (i = 0; i < n; i++)
1803     {
1804       saved_base = base = BINFO_BASE_ACCESS (t, i);
1805       LTO_FIXUP_SUBTREE (base);
1806       if (base != saved_base)
1807         VEC_replace (tree, BINFO_BASE_ACCESSES (t), i, base);
1808     }
1809   LTO_FIXUP_SUBTREE (BINFO_INHERITANCE_CHAIN (t));
1810   LTO_FIXUP_SUBTREE (BINFO_SUBVTT_INDEX (t));
1811   LTO_FIXUP_SUBTREE (BINFO_VPTR_INDEX (t));
1812   n = BINFO_N_BASE_BINFOS (t);
1813   for (i = 0; i < n; i++)
1814     {
1815       saved_base = base = BINFO_BASE_BINFO (t, i);
1816       LTO_FIXUP_SUBTREE (base);
1817       if (base != saved_base)
1818         VEC_replace (tree, BINFO_BASE_BINFOS (t), i, base);
1819     }
1820 }
1821
1822 /* Fix up fields of a CONSTRUCTOR T.  DATA points to fix-up states.  */
1823
1824 static void
1825 lto_fixup_constructor (tree t, void *data)
1826 {
1827   unsigned HOST_WIDE_INT idx;
1828   constructor_elt *ce;
1829
1830   LTO_REGISTER_TYPE_AND_FIXUP_SUBTREE (TREE_TYPE (t));
1831
1832   for (idx = 0;
1833        VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (t), idx, ce);
1834        idx++)
1835     {
1836       LTO_FIXUP_SUBTREE (ce->index);
1837       LTO_FIXUP_SUBTREE (ce->value);
1838     }
1839 }
1840
1841 /* A walk_tree callback used by lto_fixup_state. TP is the pointer to the
1842    current tree. WALK_SUBTREES indicates if the subtrees will be walked.
1843    DATA is a pointer set to record visited nodes. */
1844
1845 static tree
1846 lto_fixup_tree (tree *tp, int *walk_subtrees, void *data)
1847 {
1848   tree t;
1849   lto_fixup_data_t *fixup_data = (lto_fixup_data_t *) data;
1850   tree prevailing;
1851
1852   t = *tp;
1853   *walk_subtrees = 0;
1854   if (!t || pointer_set_contains (fixup_data->seen, t))
1855     return NULL;
1856
1857   if (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == FUNCTION_DECL)
1858     {
1859       prevailing = lto_symtab_prevailing_decl (t);
1860
1861       if (t != prevailing)
1862         {
1863            /* Also replace t with prevailing defintion.  We don't want to
1864               insert the other defintion in the seen set as we want to
1865               replace all instances of it.  */
1866           *tp = prevailing;
1867           t = prevailing;
1868         }
1869     }
1870   else if (TYPE_P (t))
1871     {
1872       /* Replace t with the prevailing type.  We don't want to insert the
1873          other type in the seen set as we want to replace all instances of it.  */
1874       t = gimple_register_type (t);
1875       *tp = t;
1876     }
1877
1878   if (pointer_set_insert (fixup_data->seen, t))
1879     return NULL;
1880
1881   /* walk_tree does not visit all reachable nodes that need to be fixed up.
1882      Hence we do special processing here for those kind of nodes. */
1883   switch (TREE_CODE (t))
1884     {
1885     case FIELD_DECL:
1886       lto_fixup_field_decl (t, data);
1887       break;
1888
1889     case LABEL_DECL:
1890     case CONST_DECL:
1891     case PARM_DECL:
1892     case RESULT_DECL:
1893     case IMPORTED_DECL:
1894       lto_fixup_decl_common (t, data);
1895       break;
1896
1897     case VAR_DECL:
1898       lto_fixup_decl_with_vis (t, data);
1899       break;    
1900
1901     case TYPE_DECL:
1902       lto_fixup_decl_non_common (t, data);
1903       break;
1904
1905     case FUNCTION_DECL:
1906       lto_fixup_function (t, data);
1907       break;
1908
1909     case TREE_BINFO:
1910       lto_fixup_binfo (t, data);
1911       break;
1912
1913     default:
1914       if (TYPE_P (t))
1915         lto_fixup_type (t, data);
1916       else if (TREE_CODE (t) == CONSTRUCTOR)
1917         lto_fixup_constructor (t, data);
1918       else if (CONSTANT_CLASS_P (t))
1919         LTO_REGISTER_TYPE_AND_FIXUP_SUBTREE (TREE_TYPE (t));
1920       else if (EXPR_P (t))
1921         {
1922           /* walk_tree only handles TREE_OPERANDs. Do the rest here.  */
1923           lto_fixup_common (t, data);
1924           LTO_FIXUP_SUBTREE (t->exp.block);
1925           *walk_subtrees = 1;
1926         }
1927       else
1928         {
1929           /* Let walk_tree handle sub-trees.  */
1930           *walk_subtrees = 1;
1931         }
1932     }
1933
1934   return NULL;
1935 }
1936
1937 /* Helper function of lto_fixup_decls. Walks the var and fn streams in STATE,
1938    replaces var and function decls with the corresponding prevailing def and
1939    records the old decl in the free-list in DATA. We also record visted nodes
1940    in the seen-set in DATA to avoid multiple visit for nodes that need not
1941    to be replaced.  */
1942
1943 static void
1944 lto_fixup_state (struct lto_in_decl_state *state, lto_fixup_data_t *data)
1945 {
1946   unsigned i, si;
1947   struct lto_tree_ref_table *table;
1948
1949   /* Although we only want to replace FUNCTION_DECLs and VAR_DECLs,
1950      we still need to walk from all DECLs to find the reachable
1951      FUNCTION_DECLs and VAR_DECLs.  */
1952   for (si = 0; si < LTO_N_DECL_STREAMS; si++)
1953     {
1954       table = &state->streams[si];
1955       for (i = 0; i < table->size; i++)
1956         walk_tree (table->trees + i, lto_fixup_tree, data, NULL);
1957     }
1958 }
1959
1960 /* A callback of htab_traverse. Just extract a state from SLOT and the
1961    lto_fixup_data_t object from AUX and calls lto_fixup_state. */
1962
1963 static int
1964 lto_fixup_state_aux (void **slot, void *aux)
1965 {
1966   struct lto_in_decl_state *state = (struct lto_in_decl_state *) *slot;
1967   lto_fixup_state (state, (lto_fixup_data_t *) aux);
1968   return 1;
1969 }
1970
1971 /* Fix the decls from all FILES. Replaces each decl with the corresponding
1972    prevailing one.  */
1973
1974 static void
1975 lto_fixup_decls (struct lto_file_decl_data **files)
1976 {
1977   unsigned int i;
1978   tree decl;
1979   struct pointer_set_t *seen = pointer_set_create ();
1980   lto_fixup_data_t data;
1981
1982   data.seen = seen;
1983   for (i = 0; files[i]; i++)
1984     {
1985       struct lto_file_decl_data *file = files[i];
1986       struct lto_in_decl_state *state = file->global_decl_state;
1987       lto_fixup_state (state, &data);
1988
1989       htab_traverse (file->function_decl_states, lto_fixup_state_aux, &data);
1990     }
1991
1992   FOR_EACH_VEC_ELT (tree, lto_global_var_decls, i, decl)
1993     {
1994       tree saved_decl = decl;
1995       walk_tree (&decl, lto_fixup_tree, &data, NULL);
1996       if (decl != saved_decl)
1997         VEC_replace (tree, lto_global_var_decls, i, decl);
1998     }
1999
2000   pointer_set_destroy (seen);
2001 }
2002
2003 /* Read the options saved from each file in the command line.  Called
2004    from lang_hooks.post_options which is called by process_options
2005    right before all the options are used to initialize the compiler.
2006    This assumes that decode_options has already run, so the
2007    num_in_fnames and in_fnames are properly set.
2008
2009    Note that this assumes that all the files had been compiled with
2010    the same options, which is not a good assumption.  In general,
2011    options ought to be read from all the files in the set and merged.
2012    However, it is still unclear what the merge rules should be.  */
2013
2014 void
2015 lto_read_all_file_options (void)
2016 {
2017   size_t i;
2018
2019   /* Clear any file options currently saved.  */
2020   lto_clear_file_options ();
2021
2022   /* Set the hooks to read ELF sections.  */
2023   lto_set_in_hooks (NULL, get_section_data, free_section_data);
2024   if (!quiet_flag)
2025     fprintf (stderr, "Reading command line options:");
2026
2027   for (i = 0; i < num_in_fnames; i++)
2028     {
2029       struct lto_file_decl_data *file_data;
2030       lto_file *file = lto_obj_file_open (in_fnames[i], false);
2031       if (!file)
2032         break;
2033       if (!quiet_flag)
2034         {
2035           fprintf (stderr, " %s", in_fnames[i]);
2036           fflush (stderr);
2037         }
2038
2039       file_data = XCNEW (struct lto_file_decl_data);
2040       file_data->file_name = file->filename;
2041       file_data->section_hash_table = lto_obj_build_section_table (file);
2042
2043       lto_read_file_options (file_data);
2044
2045       lto_obj_file_close (file);
2046       htab_delete (file_data->section_hash_table);
2047       free (file_data);
2048     }
2049
2050   if (!quiet_flag)
2051     fprintf (stderr, "\n");
2052
2053   /* Apply globally the options read from all the files.  */
2054   lto_reissue_options ();
2055 }
2056
2057 static GTY((length ("lto_stats.num_input_files + 1"))) struct lto_file_decl_data **all_file_decl_data;
2058
2059 /* Turn file datas for sub files into a single array, so that they look
2060    like separate files for further passes. */
2061
2062 static void
2063 lto_flatten_files (struct lto_file_decl_data **orig, int count, int last_file_ix)
2064 {
2065   struct lto_file_decl_data *n, *next;
2066   int i, k;
2067
2068   lto_stats.num_input_files = count;
2069   all_file_decl_data
2070     = ggc_alloc_cleared_vec_lto_file_decl_data_ptr (count + 1);
2071   /* Set the hooks so that all of the ipa passes can read in their data.  */
2072   lto_set_in_hooks (all_file_decl_data, get_section_data, free_section_data);
2073   for (i = 0, k = 0; i < last_file_ix; i++) 
2074     {
2075       for (n = orig[i]; n != NULL; n = next)
2076         {
2077           all_file_decl_data[k++] = n;
2078           next = n->next;
2079           n->next = NULL;
2080         }
2081     }
2082   all_file_decl_data[k] = NULL;
2083   gcc_assert (k == count);
2084 }
2085
2086 /* Input file data before flattening (i.e. splitting them to subfiles to support
2087    incremental linking.  */
2088 static int real_file_count;
2089 static GTY((length ("real_file_count + 1"))) struct lto_file_decl_data **real_file_decl_data;
2090
2091 /* Read all the symbols from the input files FNAMES.  NFILES is the
2092    number of files requested in the command line.  Instantiate a
2093    global call graph by aggregating all the sub-graphs found in each
2094    file.  */
2095
2096 static void
2097 read_cgraph_and_symbols (unsigned nfiles, const char **fnames)
2098 {
2099   unsigned int i, last_file_ix;
2100   FILE *resolution;
2101   struct cgraph_node *node;
2102   int count = 0;
2103   struct lto_file_decl_data **decl_data;
2104
2105   init_cgraph ();
2106
2107   timevar_push (TV_IPA_LTO_DECL_IN);
2108
2109   real_file_decl_data
2110     = decl_data = ggc_alloc_cleared_vec_lto_file_decl_data_ptr (nfiles + 1);
2111   real_file_count = nfiles;
2112
2113   /* Read the resolution file.  */
2114   resolution = NULL;
2115   if (resolution_file_name)
2116     {
2117       int t;
2118       unsigned num_objects;
2119
2120       resolution = fopen (resolution_file_name, "r");
2121       if (resolution == NULL)
2122         fatal_error ("could not open symbol resolution file: %m");
2123
2124       t = fscanf (resolution, "%u", &num_objects);
2125       gcc_assert (t == 1);
2126
2127       /* True, since the plugin splits the archives.  */
2128       gcc_assert (num_objects == nfiles);
2129     }
2130
2131   if (!quiet_flag)
2132     fprintf (stderr, "Reading object files:");
2133
2134   /* Read all of the object files specified on the command line.  */
2135   for (i = 0, last_file_ix = 0; i < nfiles; ++i)
2136     {
2137       struct lto_file_decl_data *file_data = NULL;
2138       if (!quiet_flag)
2139         {
2140           fprintf (stderr, " %s", fnames[i]);
2141           fflush (stderr);
2142         }
2143
2144       current_lto_file = lto_obj_file_open (fnames[i], false);
2145       if (!current_lto_file)
2146         break;
2147
2148       file_data = lto_file_read (current_lto_file, resolution, &count);
2149       if (!file_data)
2150         break;
2151
2152       decl_data[last_file_ix++] = file_data;
2153
2154       lto_obj_file_close (current_lto_file);
2155       current_lto_file = NULL;
2156       ggc_collect ();
2157     }
2158
2159   lto_flatten_files (decl_data, count, last_file_ix);
2160   lto_stats.num_input_files = count;
2161   ggc_free(decl_data);
2162   real_file_decl_data = NULL;
2163
2164   if (resolution_file_name)
2165     fclose (resolution);
2166
2167   /* Set the hooks so that all of the ipa passes can read in their data.  */
2168   lto_set_in_hooks (all_file_decl_data, get_section_data, free_section_data);
2169
2170   timevar_pop (TV_IPA_LTO_DECL_IN);
2171
2172   if (!quiet_flag)
2173     fprintf (stderr, "\nReading the callgraph\n");
2174
2175   timevar_push (TV_IPA_LTO_CGRAPH_IO);
2176   /* Read the callgraph.  */
2177   input_cgraph ();
2178   timevar_pop (TV_IPA_LTO_CGRAPH_IO);
2179
2180   if (!quiet_flag)
2181     fprintf (stderr, "Merging declarations\n");
2182
2183   timevar_push (TV_IPA_LTO_DECL_MERGE);
2184   /* Merge global decls.  */
2185   lto_symtab_merge_decls ();
2186
2187   /* If there were errors during symbol merging bail out, we have no
2188      good way to recover here.  */
2189   if (seen_error ())
2190     fatal_error ("errors during merging of translation units");
2191
2192   /* Fixup all decls and types and free the type hash tables.  */
2193   lto_fixup_decls (all_file_decl_data);
2194   free_gimple_type_tables ();
2195   ggc_collect ();
2196
2197   timevar_pop (TV_IPA_LTO_DECL_MERGE);
2198   /* Each pass will set the appropriate timer.  */
2199
2200   if (!quiet_flag)
2201     fprintf (stderr, "Reading summaries\n");
2202
2203   /* Read the IPA summary data.  */
2204   if (flag_ltrans)
2205     ipa_read_optimization_summaries ();
2206   else
2207     ipa_read_summaries ();
2208
2209   /* Finally merge the cgraph according to the decl merging decisions.  */
2210   timevar_push (TV_IPA_LTO_CGRAPH_MERGE);
2211   if (cgraph_dump_file)
2212     {
2213       fprintf (cgraph_dump_file, "Before merging:\n");
2214       dump_cgraph (cgraph_dump_file);
2215       dump_varpool (cgraph_dump_file);
2216     }
2217   lto_symtab_merge_cgraph_nodes ();
2218   ggc_collect ();
2219
2220   if (flag_ltrans)
2221     for (node = cgraph_nodes; node; node = node->next)
2222       {
2223         /* FIXME: ipa_transforms_to_apply holds list of passes that have optimization
2224            summaries computed and needs to apply changes.  At the moment WHOPR only
2225            supports inlining, so we can push it here by hand.  In future we need to stream
2226            this field into ltrans compilation.  */
2227         if (node->analyzed)
2228           VEC_safe_push (ipa_opt_pass, heap,
2229                          node->ipa_transforms_to_apply,
2230                          (ipa_opt_pass)&pass_ipa_inline);
2231       }
2232   lto_symtab_free ();
2233
2234   timevar_pop (TV_IPA_LTO_CGRAPH_MERGE);
2235
2236   timevar_push (TV_IPA_LTO_DECL_INIT_IO);
2237
2238   /* FIXME lto. This loop needs to be changed to use the pass manager to
2239      call the ipa passes directly.  */
2240   if (!seen_error ())
2241     for (i = 0; i < last_file_ix; i++)
2242       {
2243         struct lto_file_decl_data *file_data = all_file_decl_data [i];
2244         lto_materialize_constructors_and_inits (file_data);
2245       }
2246
2247   /* Indicate that the cgraph is built and ready.  */
2248   cgraph_function_flags_ready = true;
2249
2250   timevar_pop (TV_IPA_LTO_DECL_INIT_IO);
2251   ggc_free (all_file_decl_data);
2252   all_file_decl_data = NULL;
2253 }
2254
2255
2256 /* Materialize all the bodies for all the nodes in the callgraph.  */
2257
2258 static void
2259 materialize_cgraph (void)
2260 {
2261   tree decl;
2262   struct cgraph_node *node; 
2263   unsigned i;
2264   timevar_id_t lto_timer;
2265
2266   if (!quiet_flag)
2267     fprintf (stderr,
2268              flag_wpa ? "Materializing decls:" : "Reading function bodies:");
2269
2270
2271   /* Now that we have input the cgraph, we need to clear all of the aux
2272      nodes and read the functions if we are not running in WPA mode.  */
2273   timevar_push (TV_IPA_LTO_GIMPLE_IN);
2274
2275   for (node = cgraph_nodes; node; node = node->next)
2276     {
2277       if (node->local.lto_file_data)
2278         {
2279           lto_materialize_function (node);
2280           lto_stats.num_input_cgraph_nodes++;
2281         }
2282     }
2283
2284   timevar_pop (TV_IPA_LTO_GIMPLE_IN);
2285
2286   /* Start the appropriate timer depending on the mode that we are
2287      operating in.  */
2288   lto_timer = (flag_wpa) ? TV_WHOPR_WPA
2289               : (flag_ltrans) ? TV_WHOPR_LTRANS
2290               : TV_LTO;
2291   timevar_push (lto_timer);
2292
2293   current_function_decl = NULL;
2294   set_cfun (NULL);
2295
2296   /* Inform the middle end about the global variables we have seen.  */
2297   FOR_EACH_VEC_ELT (tree, lto_global_var_decls, i, decl)
2298     rest_of_decl_compilation (decl, 1, 0);
2299
2300   if (!quiet_flag)
2301     fprintf (stderr, "\n");
2302
2303   timevar_pop (lto_timer);
2304 }
2305
2306
2307 /* Perform whole program analysis (WPA) on the callgraph and write out the
2308    optimization plan.  */
2309
2310 static void
2311 do_whole_program_analysis (void)
2312 {
2313   /* Note that since we are in WPA mode, materialize_cgraph will not
2314      actually read in all the function bodies.  It only materializes
2315      the decls and cgraph nodes so that analysis can be performed.  */
2316   materialize_cgraph ();
2317
2318   /* Reading in the cgraph uses different timers, start timing WPA now.  */
2319   timevar_push (TV_WHOPR_WPA);
2320
2321   if (pre_ipa_mem_report)
2322     {
2323       fprintf (stderr, "Memory consumption before IPA\n");
2324       dump_memory_report (false);
2325     }
2326
2327   cgraph_function_flags_ready = true;
2328
2329   if (cgraph_dump_file)
2330     {
2331       dump_cgraph (cgraph_dump_file);
2332       dump_varpool (cgraph_dump_file);
2333     }
2334   bitmap_obstack_initialize (NULL);
2335   ipa_register_cgraph_hooks ();
2336   cgraph_state = CGRAPH_STATE_IPA_SSA;
2337
2338   execute_ipa_pass_list (all_regular_ipa_passes);
2339
2340   if (cgraph_dump_file)
2341     {
2342       fprintf (cgraph_dump_file, "Optimized ");
2343       dump_cgraph (cgraph_dump_file);
2344       dump_varpool (cgraph_dump_file);
2345     }
2346   verify_cgraph ();
2347   bitmap_obstack_release (NULL);
2348
2349   /* We are about to launch the final LTRANS phase, stop the WPA timer.  */
2350   timevar_pop (TV_WHOPR_WPA);
2351
2352   if (flag_lto_partition_1to1)
2353     lto_1_to_1_map ();
2354   else
2355     lto_balanced_map ();
2356
2357   if (!quiet_flag)
2358     {
2359       fprintf (stderr, "\nStreaming out");
2360       fflush (stderr);
2361     }
2362   lto_wpa_write_files ();
2363   ggc_collect ();
2364   if (!quiet_flag)
2365     fprintf (stderr, "\n");
2366
2367   if (post_ipa_mem_report)
2368     {
2369       fprintf (stderr, "Memory consumption after IPA\n");
2370       dump_memory_report (false);
2371     }
2372
2373   /* Show the LTO report before launching LTRANS.  */
2374   if (flag_lto_report)
2375     print_lto_report ();
2376 }
2377
2378
2379 static GTY(()) tree lto_eh_personality_decl;
2380
2381 /* Return the LTO personality function decl.  */
2382
2383 tree
2384 lto_eh_personality (void)
2385 {
2386   if (!lto_eh_personality_decl)
2387     {
2388       /* Use the first personality DECL for our personality if we don't
2389          support multiple ones.  This ensures that we don't artificially
2390          create the need for them in a single-language program.  */
2391       if (first_personality_decl && !dwarf2out_do_cfi_asm ())
2392         lto_eh_personality_decl = first_personality_decl;
2393       else
2394         lto_eh_personality_decl = lhd_gcc_personality ();
2395     }
2396
2397   return lto_eh_personality_decl;
2398 }
2399
2400 /* Set the process name based on the LTO mode. */
2401
2402 static void 
2403 lto_process_name (void)
2404 {
2405   if (flag_lto)
2406     setproctitle ("lto1-lto");
2407   if (flag_wpa)
2408     setproctitle ("lto1-wpa");
2409   if (flag_ltrans)
2410     setproctitle ("lto1-ltrans");
2411 }
2412
2413 /* Main entry point for the GIMPLE front end.  This front end has
2414    three main personalities:
2415
2416    - LTO (-flto).  All the object files on the command line are
2417      loaded in memory and processed as a single translation unit.
2418      This is the traditional link-time optimization behavior.
2419
2420    - WPA (-fwpa).  Only the callgraph and summary information for
2421      files in the command file are loaded.  A single callgraph
2422      (without function bodies) is instantiated for the whole set of
2423      files.  IPA passes are only allowed to analyze the call graph
2424      and make transformation decisions.  The callgraph is
2425      partitioned, each partition is written to a new object file
2426      together with the transformation decisions.
2427
2428    - LTRANS (-fltrans).  Similar to -flto but it prevents the IPA
2429      summary files from running again.  Since WPA computed summary
2430      information and decided what transformations to apply, LTRANS
2431      simply applies them.  */
2432
2433 void
2434 lto_main (void)
2435 {
2436   lto_process_name ();
2437
2438   lto_init_reader ();
2439
2440   /* Read all the symbols and call graph from all the files in the
2441      command line.  */
2442   read_cgraph_and_symbols (num_in_fnames, in_fnames);
2443
2444   if (!seen_error ())
2445     {
2446       /* If WPA is enabled analyze the whole call graph and create an
2447          optimization plan.  Otherwise, read in all the function
2448          bodies and continue with optimization.  */
2449       if (flag_wpa)
2450         do_whole_program_analysis ();
2451       else
2452         {
2453           materialize_cgraph ();
2454
2455           /* Let the middle end know that we have read and merged all of
2456              the input files.  */ 
2457           cgraph_optimize ();
2458
2459           /* FIXME lto, if the processes spawned by WPA fail, we miss
2460              the chance to print WPA's report, so WPA will call
2461              print_lto_report before launching LTRANS.  If LTRANS was
2462              launched directly by the driver we would not need to do
2463              this.  */
2464           if (flag_lto_report)
2465             print_lto_report ();
2466         }
2467     }
2468 }
2469
2470 #include "gt-lto-lto.h"