1/* Top-level control of tree optimizations.
2   Copyright 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3   Contributed by Diego Novillo <dnovillo@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 2, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to
19the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20Boston, MA 02110-1301, USA.  */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "tm.h"
26#include "tree.h"
27#include "rtl.h"
28#include "tm_p.h"
29#include "hard-reg-set.h"
30#include "basic-block.h"
31#include "output.h"
32#include "expr.h"
33#include "diagnostic.h"
34#include "basic-block.h"
35#include "flags.h"
36#include "tree-flow.h"
37#include "tree-dump.h"
38#include "timevar.h"
39#include "function.h"
40#include "langhooks.h"
41#include "toplev.h"
42#include "flags.h"
43#include "cgraph.h"
44#include "tree-inline.h"
45#include "tree-mudflap.h"
46#include "tree-pass.h"
47#include "ggc.h"
48#include "cgraph.h"
49#include "graph.h"
50#include "cfgloop.h"
51#include "except.h"
52
53
54/* Gate: execute, or not, all of the non-trivial optimizations.  */
55
56static bool
57gate_all_optimizations (void)
58{
59  return (optimize >= 1
60	  /* Don't bother doing anything if the program has errors.  */
61	  && !(errorcount || sorrycount));
62}
63
64struct tree_opt_pass pass_all_optimizations =
65{
66  NULL,					/* name */
67  gate_all_optimizations,		/* gate */
68  NULL,					/* execute */
69  NULL,					/* sub */
70  NULL,					/* next */
71  0,					/* static_pass_number */
72  0,					/* tv_id */
73  0,					/* properties_required */
74  0,					/* properties_provided */
75  0,					/* properties_destroyed */
76  0,					/* todo_flags_start */
77  0,					/* todo_flags_finish */
78  0					/* letter */
79};
80
81struct tree_opt_pass pass_early_local_passes =
82{
83  NULL,					/* name */
84  gate_all_optimizations,		/* gate */
85  NULL,					/* execute */
86  NULL,					/* sub */
87  NULL,					/* next */
88  0,					/* static_pass_number */
89  0,					/* tv_id */
90  0,					/* properties_required */
91  0,					/* properties_provided */
92  0,					/* properties_destroyed */
93  0,					/* todo_flags_start */
94  0,					/* todo_flags_finish */
95  0					/* letter */
96};
97
98/* Pass: cleanup the CFG just before expanding trees to RTL.
99   This is just a round of label cleanups and case node grouping
100   because after the tree optimizers have run such cleanups may
101   be necessary.  */
102
103static void
104execute_cleanup_cfg_pre_ipa (void)
105{
106  cleanup_tree_cfg ();
107}
108
109struct tree_opt_pass pass_cleanup_cfg =
110{
111  "cleanup_cfg",			/* name */
112  NULL,					/* gate */
113  execute_cleanup_cfg_pre_ipa,		/* execute */
114  NULL,					/* sub */
115  NULL,					/* next */
116  0,					/* static_pass_number */
117  0,					/* tv_id */
118  PROP_cfg,				/* properties_required */
119  0,					/* properties_provided */
120  0,					/* properties_destroyed */
121  0,					/* todo_flags_start */
122  TODO_dump_func,					/* todo_flags_finish */
123  0					/* letter */
124};
125
126
127/* Pass: cleanup the CFG just before expanding trees to RTL.
128   This is just a round of label cleanups and case node grouping
129   because after the tree optimizers have run such cleanups may
130   be necessary.  */
131
132static void
133execute_cleanup_cfg_post_optimizing (void)
134{
135  fold_cond_expr_cond ();
136  cleanup_tree_cfg ();
137  cleanup_dead_labels ();
138  group_case_labels ();
139}
140
141struct tree_opt_pass pass_cleanup_cfg_post_optimizing =
142{
143  "final_cleanup",			/* name */
144  NULL,					/* gate */
145  execute_cleanup_cfg_post_optimizing,	/* execute */
146  NULL,					/* sub */
147  NULL,					/* next */
148  0,					/* static_pass_number */
149  0,					/* tv_id */
150  PROP_cfg,				/* properties_required */
151  0,					/* properties_provided */
152  0,					/* properties_destroyed */
153  0,					/* todo_flags_start */
154  TODO_dump_func,					/* todo_flags_finish */
155  0					/* letter */
156};
157
158/* Pass: do the actions required to finish with tree-ssa optimization
159   passes.  */
160
161static void
162execute_free_datastructures (void)
163{
164  /* ??? This isn't the right place for this.  Worse, it got computed
165     more or less at random in various passes.  */
166  free_dominance_info (CDI_DOMINATORS);
167  free_dominance_info (CDI_POST_DOMINATORS);
168
169  /* Remove the ssa structures.  Do it here since this includes statement
170     annotations that need to be intact during disband_implicit_edges.  */
171  delete_tree_ssa ();
172}
173
174struct tree_opt_pass pass_free_datastructures =
175{
176  NULL,					/* name */
177  NULL,					/* gate */
178  execute_free_datastructures,			/* execute */
179  NULL,					/* sub */
180  NULL,					/* next */
181  0,					/* static_pass_number */
182  0,					/* tv_id */
183  PROP_cfg,				/* properties_required */
184  0,					/* properties_provided */
185  0,					/* properties_destroyed */
186  0,					/* todo_flags_start */
187  0,					/* todo_flags_finish */
188  0					/* letter */
189};
190/* Pass: free cfg annotations.  */
191
192static void
193execute_free_cfg_annotations (void)
194{
195  basic_block bb;
196  block_stmt_iterator bsi;
197
198  /* Emit gotos for implicit jumps.  */
199  disband_implicit_edges ();
200
201  /* Remove annotations from every tree in the function.  */
202  FOR_EACH_BB (bb)
203    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
204      {
205	tree stmt = bsi_stmt (bsi);
206	ggc_free (stmt->common.ann);
207	stmt->common.ann = NULL;
208      }
209
210  /* And get rid of annotations we no longer need.  */
211  delete_tree_cfg_annotations ();
212}
213
214struct tree_opt_pass pass_free_cfg_annotations =
215{
216  NULL,					/* name */
217  NULL,					/* gate */
218  execute_free_cfg_annotations,		/* execute */
219  NULL,					/* sub */
220  NULL,					/* next */
221  0,					/* static_pass_number */
222  0,					/* tv_id */
223  PROP_cfg,				/* properties_required */
224  0,					/* properties_provided */
225  0,					/* properties_destroyed */
226  0,					/* todo_flags_start */
227  0,					/* todo_flags_finish */
228  0					/* letter */
229};
230/* Pass: fixup_cfg - IPA passes or compilation of earlier functions might've
231   changed some properties - such as marked functions nothrow.  Remove now
232   redundant edges and basic blocks.  */
233
234static void
235execute_fixup_cfg (void)
236{
237  basic_block bb;
238  block_stmt_iterator bsi;
239
240  if (cfun->eh)
241    FOR_EACH_BB (bb)
242      {
243	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
244	  {
245	    tree stmt = bsi_stmt (bsi);
246	    tree call = get_call_expr_in (stmt);
247
248	    if (call && call_expr_flags (call) & (ECF_CONST | ECF_PURE))
249	      TREE_SIDE_EFFECTS (call) = 0;
250	    if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
251	      remove_stmt_from_eh_region (stmt);
252	  }
253	tree_purge_dead_eh_edges (bb);
254      }
255
256  cleanup_tree_cfg ();
257}
258
259struct tree_opt_pass pass_fixup_cfg =
260{
261  "fixupcfg",				/* name */
262  NULL,					/* gate */
263  execute_fixup_cfg,			/* execute */
264  NULL,					/* sub */
265  NULL,					/* next */
266  0,					/* static_pass_number */
267  0,					/* tv_id */
268  PROP_cfg,				/* properties_required */
269  0,					/* properties_provided */
270  0,					/* properties_destroyed */
271  0,					/* todo_flags_start */
272  TODO_dump_func,			/* todo_flags_finish */
273  0					/* letter */
274};
275
276/* Do the actions required to initialize internal data structures used
277   in tree-ssa optimization passes.  */
278
279static void
280execute_init_datastructures (void)
281{
282  /* Allocate hash tables, arrays and other structures.  */
283  init_tree_ssa ();
284}
285
286struct tree_opt_pass pass_init_datastructures =
287{
288  NULL,					/* name */
289  NULL,					/* gate */
290  execute_init_datastructures,		/* execute */
291  NULL,					/* sub */
292  NULL,					/* next */
293  0,					/* static_pass_number */
294  0,					/* tv_id */
295  PROP_cfg,				/* properties_required */
296  0,					/* properties_provided */
297  0,					/* properties_destroyed */
298  0,					/* todo_flags_start */
299  0,					/* todo_flags_finish */
300  0					/* letter */
301};
302
303void
304tree_lowering_passes (tree fn)
305{
306  tree saved_current_function_decl = current_function_decl;
307
308  current_function_decl = fn;
309  push_cfun (DECL_STRUCT_FUNCTION (fn));
310  tree_register_cfg_hooks ();
311  bitmap_obstack_initialize (NULL);
312  execute_pass_list (all_lowering_passes);
313  free_dominance_info (CDI_POST_DOMINATORS);
314  compact_blocks ();
315  current_function_decl = saved_current_function_decl;
316  bitmap_obstack_release (NULL);
317  pop_cfun ();
318}
319
320/* Update recursively all inlined_to pointers of functions
321   inlined into NODE to INLINED_TO.  */
322static void
323update_inlined_to_pointers (struct cgraph_node *node,
324			    struct cgraph_node *inlined_to)
325{
326  struct cgraph_edge *e;
327  for (e = node->callees; e; e = e->next_callee)
328    {
329      if (e->callee->global.inlined_to)
330	{
331	  e->callee->global.inlined_to = inlined_to;
332	  update_inlined_to_pointers (e->callee, inlined_to);
333	}
334    }
335}
336
337
338/* For functions-as-trees languages, this performs all optimization and
339   compilation for FNDECL.  */
340
341void
342tree_rest_of_compilation (tree fndecl)
343{
344  location_t saved_loc;
345  struct cgraph_node *saved_node = NULL, *node;
346
347  timevar_push (TV_EXPAND);
348
349  gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
350
351  /* Initialize the RTL code for the function.  */
352  current_function_decl = fndecl;
353  saved_loc = input_location;
354  input_location = DECL_SOURCE_LOCATION (fndecl);
355  init_function_start (fndecl);
356
357  /* Even though we're inside a function body, we still don't want to
358     call expand_expr to calculate the size of a variable-sized array.
359     We haven't necessarily assigned RTL to all variables yet, so it's
360     not safe to try to expand expressions involving them.  */
361  cfun->x_dont_save_pending_sizes_p = 1;
362  cfun->after_inlining = true;
363
364  node = cgraph_node (fndecl);
365
366  /* We might need the body of this function so that we can expand
367     it inline somewhere else.  This means not lowering some constructs
368     such as exception handling.  */
369  if (cgraph_preserve_function_body_p (fndecl))
370    {
371      if (!flag_unit_at_a_time)
372	{
373	  struct cgraph_edge *e;
374
375	  saved_node = cgraph_clone_node (node, node->count, 1, false);
376	  for (e = saved_node->callees; e; e = e->next_callee)
377	    if (!e->inline_failed)
378	      cgraph_clone_inlined_nodes (e, true, false);
379	}
380      cfun->saved_static_chain_decl = cfun->static_chain_decl;
381      save_body (fndecl, &cfun->saved_args, &cfun->saved_static_chain_decl);
382    }
383
384  if (flag_inline_trees)
385    {
386      struct cgraph_edge *e;
387      for (e = node->callees; e; e = e->next_callee)
388	if (!e->inline_failed || warn_inline)
389	  break;
390      if (e)
391	{
392	  timevar_push (TV_INTEGRATION);
393	  optimize_inline_calls (fndecl);
394	  timevar_pop (TV_INTEGRATION);
395	}
396    }
397  /* We are not going to maintain the cgraph edges up to date.
398     Kill it so it won't confuse us.  */
399  while (node->callees)
400    {
401      /* In non-unit-at-a-time we must mark all referenced functions as needed.
402         */
403      if (node->callees->callee->analyzed && !flag_unit_at_a_time)
404        cgraph_mark_needed_node (node->callees->callee);
405      cgraph_remove_edge (node->callees);
406    }
407
408  /* We are not going to maintain the cgraph edges up to date.
409     Kill it so it won't confuse us.  */
410  cgraph_node_remove_callees (node);
411
412
413  /* Initialize the default bitmap obstack.  */
414  bitmap_obstack_initialize (NULL);
415  bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
416
417  tree_register_cfg_hooks ();
418  /* Perform all tree transforms and optimizations.  */
419  execute_pass_list (all_passes);
420
421  bitmap_obstack_release (&reg_obstack);
422
423  /* Release the default bitmap obstack.  */
424  bitmap_obstack_release (NULL);
425
426  /* Restore original body if still needed.  */
427  if (cfun->saved_cfg)
428    {
429      DECL_ARGUMENTS (fndecl) = cfun->saved_args;
430      cfun->cfg = cfun->saved_cfg;
431      cfun->eh = cfun->saved_eh;
432      DECL_INITIAL (fndecl) = cfun->saved_blocks;
433      cfun->unexpanded_var_list = cfun->saved_unexpanded_var_list;
434      cfun->saved_cfg = NULL;
435      cfun->saved_eh = NULL;
436      cfun->saved_args = NULL_TREE;
437      cfun->saved_blocks = NULL_TREE;
438      cfun->saved_unexpanded_var_list = NULL_TREE;
439      cfun->static_chain_decl = cfun->saved_static_chain_decl;
440      cfun->saved_static_chain_decl = NULL;
441      /* When not in unit-at-a-time mode, we must preserve out of line copy
442	 representing node before inlining.  Restore original outgoing edges
443	 using clone we created earlier.  */
444      if (!flag_unit_at_a_time)
445	{
446	  struct cgraph_edge *e;
447
448	  node = cgraph_node (current_function_decl);
449	  cgraph_node_remove_callees (node);
450	  node->callees = saved_node->callees;
451	  saved_node->callees = NULL;
452	  update_inlined_to_pointers (node, node);
453	  for (e = node->callees; e; e = e->next_callee)
454	    e->caller = node;
455	  cgraph_remove_node (saved_node);
456	}
457    }
458  else
459    DECL_SAVED_TREE (fndecl) = NULL;
460  cfun = 0;
461
462  /* If requested, warn about function definitions where the function will
463     return a value (usually of some struct or union type) which itself will
464     take up a lot of stack space.  */
465  if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
466    {
467      tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
468
469      if (ret_type && TYPE_SIZE_UNIT (ret_type)
470	  && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
471	  && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
472				   larger_than_size))
473	{
474	  unsigned int size_as_int
475	    = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
476
477	  if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
478	    warning (0, "size of return value of %q+D is %u bytes",
479                     fndecl, size_as_int);
480	  else
481	    warning (0, "size of return value of %q+D is larger than %wd bytes",
482                     fndecl, larger_than_size);
483	}
484    }
485
486  if (!flag_inline_trees)
487    {
488      DECL_SAVED_TREE (fndecl) = NULL;
489      if (DECL_STRUCT_FUNCTION (fndecl) == 0
490	  && !cgraph_node (fndecl)->origin)
491	{
492	  /* Stop pointing to the local nodes about to be freed.
493	     But DECL_INITIAL must remain nonzero so we know this
494	     was an actual function definition.
495	     For a nested function, this is done in c_pop_function_context.
496	     If rest_of_compilation set this to 0, leave it 0.  */
497	  if (DECL_INITIAL (fndecl) != 0)
498	    DECL_INITIAL (fndecl) = error_mark_node;
499	}
500    }
501
502  input_location = saved_loc;
503
504  ggc_collect ();
505  timevar_pop (TV_EXPAND);
506}
507