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 unsigned int
104execute_cleanup_cfg_pre_ipa (void)
105{
106  cleanup_tree_cfg ();
107  return 0;
108}
109
110struct tree_opt_pass pass_cleanup_cfg =
111{
112  "cleanup_cfg",			/* name */
113  NULL,					/* gate */
114  execute_cleanup_cfg_pre_ipa,		/* execute */
115  NULL,					/* sub */
116  NULL,					/* next */
117  0,					/* static_pass_number */
118  0,					/* tv_id */
119  PROP_cfg,				/* properties_required */
120  0,					/* properties_provided */
121  0,					/* properties_destroyed */
122  0,					/* todo_flags_start */
123  TODO_dump_func,					/* todo_flags_finish */
124  0					/* letter */
125};
126
127
128/* Pass: cleanup the CFG just before expanding trees to RTL.
129   This is just a round of label cleanups and case node grouping
130   because after the tree optimizers have run such cleanups may
131   be necessary.  */
132
133static unsigned int
134execute_cleanup_cfg_post_optimizing (void)
135{
136  fold_cond_expr_cond ();
137  cleanup_tree_cfg ();
138  cleanup_dead_labels ();
139  group_case_labels ();
140  return 0;
141}
142
143struct tree_opt_pass pass_cleanup_cfg_post_optimizing =
144{
145  "final_cleanup",			/* name */
146  NULL,					/* gate */
147  execute_cleanup_cfg_post_optimizing,	/* execute */
148  NULL,					/* sub */
149  NULL,					/* next */
150  0,					/* static_pass_number */
151  0,					/* tv_id */
152  PROP_cfg,				/* properties_required */
153  0,					/* properties_provided */
154  0,					/* properties_destroyed */
155  0,					/* todo_flags_start */
156  TODO_dump_func,					/* todo_flags_finish */
157  0					/* letter */
158};
159
160/* Pass: do the actions required to finish with tree-ssa optimization
161   passes.  */
162
163static unsigned int
164execute_free_datastructures (void)
165{
166  /* ??? This isn't the right place for this.  Worse, it got computed
167     more or less at random in various passes.  */
168  free_dominance_info (CDI_DOMINATORS);
169  free_dominance_info (CDI_POST_DOMINATORS);
170
171  /* Remove the ssa structures.  Do it here since this includes statement
172     annotations that need to be intact during disband_implicit_edges.  */
173  delete_tree_ssa ();
174  return 0;
175}
176
177struct tree_opt_pass pass_free_datastructures =
178{
179  NULL,					/* name */
180  NULL,					/* gate */
181  execute_free_datastructures,			/* execute */
182  NULL,					/* sub */
183  NULL,					/* next */
184  0,					/* static_pass_number */
185  0,					/* tv_id */
186  PROP_cfg,				/* properties_required */
187  0,					/* properties_provided */
188  0,					/* properties_destroyed */
189  0,					/* todo_flags_start */
190  0,					/* todo_flags_finish */
191  0					/* letter */
192};
193/* Pass: free cfg annotations.  */
194
195static unsigned int
196execute_free_cfg_annotations (void)
197{
198  basic_block bb;
199  block_stmt_iterator bsi;
200
201  /* Emit gotos for implicit jumps.  */
202  disband_implicit_edges ();
203
204  /* Remove annotations from every tree in the function.  */
205  FOR_EACH_BB (bb)
206    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
207      {
208	tree stmt = bsi_stmt (bsi);
209	ggc_free (stmt->common.ann);
210	stmt->common.ann = NULL;
211      }
212
213  /* And get rid of annotations we no longer need.  */
214  delete_tree_cfg_annotations ();
215
216#ifdef ENABLE_CHECKING
217  /* Once the statement annotations have been removed, we can verify
218     the integrity of statements in the EH throw table.  */
219  verify_eh_throw_table_statements ();
220#endif
221  return 0;
222}
223
224struct tree_opt_pass pass_free_cfg_annotations =
225{
226  NULL,					/* name */
227  NULL,					/* gate */
228  execute_free_cfg_annotations,		/* execute */
229  NULL,					/* sub */
230  NULL,					/* next */
231  0,					/* static_pass_number */
232  0,					/* tv_id */
233  PROP_cfg,				/* properties_required */
234  0,					/* properties_provided */
235  0,					/* properties_destroyed */
236  0,					/* todo_flags_start */
237  0,					/* todo_flags_finish */
238  0					/* letter */
239};
240
241/* Return true if BB has at least one abnormal outgoing edge.  */
242
243static inline bool
244has_abnormal_outgoing_edge_p (basic_block bb)
245{
246  edge e;
247  edge_iterator ei;
248
249  FOR_EACH_EDGE (e, ei, bb->succs)
250    if (e->flags & EDGE_ABNORMAL)
251      return true;
252
253  return false;
254}
255
256/* Pass: fixup_cfg.  IPA passes, compilation of earlier functions or inlining
257   might have changed some properties, such as marked functions nothrow or
258   added calls that can potentially go to non-local labels.  Remove redundant
259   edges and basic blocks, and create new ones if necessary.  */
260
261static unsigned int
262execute_fixup_cfg (void)
263{
264  basic_block bb;
265  block_stmt_iterator bsi;
266
267  if (cfun->eh)
268    FOR_EACH_BB (bb)
269      {
270	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
271	  {
272	    tree stmt = bsi_stmt (bsi);
273	    tree call = get_call_expr_in (stmt);
274
275	    if (call && call_expr_flags (call) & (ECF_CONST | ECF_PURE))
276	      TREE_SIDE_EFFECTS (call) = 0;
277	    if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
278	      remove_stmt_from_eh_region (stmt);
279	  }
280	tree_purge_dead_eh_edges (bb);
281      }
282
283  if (current_function_has_nonlocal_label)
284    FOR_EACH_BB (bb)
285      {
286	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
287	  {
288	    tree stmt = bsi_stmt (bsi);
289	    if (tree_can_make_abnormal_goto (stmt))
290	      {
291		if (stmt == bsi_stmt (bsi_last (bb)))
292		  {
293		    if (!has_abnormal_outgoing_edge_p (bb))
294		      make_abnormal_goto_edges (bb, true);
295		  }
296		else
297		  {
298		    edge e = split_block (bb, stmt);
299		    bb = e->src;
300		    make_abnormal_goto_edges (bb, true);
301		  }
302		break;
303	      }
304	  }
305      }
306
307  cleanup_tree_cfg ();
308
309  /* Dump a textual representation of the flowgraph.  */
310  if (dump_file)
311    dump_tree_cfg (dump_file, dump_flags);
312
313  return 0;
314}
315
316struct tree_opt_pass pass_fixup_cfg =
317{
318  "fixupcfg",				/* name */
319  NULL,					/* gate */
320  execute_fixup_cfg,			/* execute */
321  NULL,					/* sub */
322  NULL,					/* next */
323  0,					/* static_pass_number */
324  0,					/* tv_id */
325  PROP_cfg,				/* properties_required */
326  0,					/* properties_provided */
327  0,					/* properties_destroyed */
328  0,					/* todo_flags_start */
329  0,					/* todo_flags_finish */
330  0					/* letter */
331};
332
333/* Do the actions required to initialize internal data structures used
334   in tree-ssa optimization passes.  */
335
336static unsigned int
337execute_init_datastructures (void)
338{
339  /* Allocate hash tables, arrays and other structures.  */
340  init_tree_ssa ();
341  return 0;
342}
343
344struct tree_opt_pass pass_init_datastructures =
345{
346  NULL,					/* name */
347  NULL,					/* gate */
348  execute_init_datastructures,		/* execute */
349  NULL,					/* sub */
350  NULL,					/* next */
351  0,					/* static_pass_number */
352  0,					/* tv_id */
353  PROP_cfg,				/* properties_required */
354  0,					/* properties_provided */
355  0,					/* properties_destroyed */
356  0,					/* todo_flags_start */
357  0,					/* todo_flags_finish */
358  0					/* letter */
359};
360
361void
362tree_lowering_passes (tree fn)
363{
364  tree saved_current_function_decl = current_function_decl;
365
366  current_function_decl = fn;
367  push_cfun (DECL_STRUCT_FUNCTION (fn));
368  tree_register_cfg_hooks ();
369  bitmap_obstack_initialize (NULL);
370  execute_pass_list (all_lowering_passes);
371  free_dominance_info (CDI_POST_DOMINATORS);
372  compact_blocks ();
373  current_function_decl = saved_current_function_decl;
374  bitmap_obstack_release (NULL);
375  pop_cfun ();
376}
377
378/* Update recursively all inlined_to pointers of functions
379   inlined into NODE to INLINED_TO.  */
380static void
381update_inlined_to_pointers (struct cgraph_node *node,
382			    struct cgraph_node *inlined_to)
383{
384  struct cgraph_edge *e;
385  for (e = node->callees; e; e = e->next_callee)
386    {
387      if (e->callee->global.inlined_to)
388	{
389	  e->callee->global.inlined_to = inlined_to;
390	  update_inlined_to_pointers (e->callee, inlined_to);
391	}
392    }
393}
394
395
396/* For functions-as-trees languages, this performs all optimization and
397   compilation for FNDECL.  */
398
399void
400tree_rest_of_compilation (tree fndecl)
401{
402  location_t saved_loc;
403  struct cgraph_node *node;
404
405  timevar_push (TV_EXPAND);
406
407  gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
408
409  node = cgraph_node (fndecl);
410
411  /* We might need the body of this function so that we can expand
412     it inline somewhere else.  */
413  if (cgraph_preserve_function_body_p (fndecl))
414    save_inline_function_body (node);
415
416  /* Initialize the RTL code for the function.  */
417  current_function_decl = fndecl;
418  saved_loc = input_location;
419  input_location = DECL_SOURCE_LOCATION (fndecl);
420  init_function_start (fndecl);
421
422  /* Even though we're inside a function body, we still don't want to
423     call expand_expr to calculate the size of a variable-sized array.
424     We haven't necessarily assigned RTL to all variables yet, so it's
425     not safe to try to expand expressions involving them.  */
426  cfun->x_dont_save_pending_sizes_p = 1;
427  cfun->after_inlining = true;
428
429  if (flag_inline_trees)
430    {
431      struct cgraph_edge *e;
432      for (e = node->callees; e; e = e->next_callee)
433	if (!e->inline_failed || warn_inline)
434	  break;
435      if (e)
436	{
437	  timevar_push (TV_INTEGRATION);
438	  optimize_inline_calls (fndecl);
439	  timevar_pop (TV_INTEGRATION);
440	}
441    }
442  /* In non-unit-at-a-time we must mark all referenced functions as needed.
443     */
444  if (!flag_unit_at_a_time)
445    {
446      struct cgraph_edge *e;
447      for (e = node->callees; e; e = e->next_callee)
448	if (e->callee->analyzed)
449          cgraph_mark_needed_node (e->callee);
450    }
451
452  /* We are not going to maintain the cgraph edges up to date.
453     Kill it so it won't confuse us.  */
454  cgraph_node_remove_callees (node);
455
456
457  /* Initialize the default bitmap obstack.  */
458  bitmap_obstack_initialize (NULL);
459  bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
460
461  tree_register_cfg_hooks ();
462  /* Perform all tree transforms and optimizations.  */
463  execute_pass_list (all_passes);
464
465  bitmap_obstack_release (&reg_obstack);
466
467  /* Release the default bitmap obstack.  */
468  bitmap_obstack_release (NULL);
469
470  DECL_SAVED_TREE (fndecl) = NULL;
471  cfun = 0;
472
473  /* If requested, warn about function definitions where the function will
474     return a value (usually of some struct or union type) which itself will
475     take up a lot of stack space.  */
476  if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
477    {
478      tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
479
480      if (ret_type && TYPE_SIZE_UNIT (ret_type)
481	  && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
482	  && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
483				   larger_than_size))
484	{
485	  unsigned int size_as_int
486	    = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
487
488	  if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
489	    warning (0, "size of return value of %q+D is %u bytes",
490                     fndecl, size_as_int);
491	  else
492	    warning (0, "size of return value of %q+D is larger than %wd bytes",
493                     fndecl, larger_than_size);
494	}
495    }
496
497  if (!flag_inline_trees)
498    {
499      DECL_SAVED_TREE (fndecl) = NULL;
500      if (DECL_STRUCT_FUNCTION (fndecl) == 0
501	  && !cgraph_node (fndecl)->origin)
502	{
503	  /* Stop pointing to the local nodes about to be freed.
504	     But DECL_INITIAL must remain nonzero so we know this
505	     was an actual function definition.
506	     For a nested function, this is done in c_pop_function_context.
507	     If rest_of_compilation set this to 0, leave it 0.  */
508	  if (DECL_INITIAL (fndecl) != 0)
509	    DECL_INITIAL (fndecl) = error_mark_node;
510	}
511    }
512
513  input_location = saved_loc;
514
515  ggc_collect ();
516  timevar_pop (TV_EXPAND);
517}
518