gcc/tree-optimize.c

   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
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, 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
  56 static bool
  57 gate_all_optimizations (void)
  58 {
  59   return (optimize >= 1
  60           /* Don't bother doing anything if the program has errors.  */
  61           && !(errorcount || sorrycount));
  62 }
  63
  64 struct 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
  81 struct 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
 103 static unsigned int
 104 execute_cleanup_cfg_pre_ipa (void)
 105 {
 106   cleanup_tree_cfg ();
 107   return 0;
 108 }
 109
 110 struct 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
 133 static unsigned int
 134 execute_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
 143 struct 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
 163 static unsigned int
 164 execute_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
 177 struct 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
 195 static unsigned int
 196 execute_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
 224 struct 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 /* Pass: fixup_cfg - IPA passes or compilation of earlier functions might've
 241    changed some properties - such as marked functions nothrow.  Remove now
 242    redundant edges and basic blocks.  */
 243
 244 static unsigned int
 245 execute_fixup_cfg (void)
 246 {
 247   basic_block bb;
 248   block_stmt_iterator bsi;
 249
 250   if (cfun->eh)
 251     FOR_EACH_BB (bb)
 252       {
 253         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 254           {
 255             tree stmt = bsi_stmt (bsi);
 256             tree call = get_call_expr_in (stmt);
 257
 258             if (call && call_expr_flags (call) & (ECF_CONST | ECF_PURE))
 259               TREE_SIDE_EFFECTS (call) = 0;
 260             if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 261               remove_stmt_from_eh_region (stmt);
 262           }
 263         tree_purge_dead_eh_edges (bb);
 264       }
 265
 266   cleanup_tree_cfg ();
 267   return 0;
 268 }
 269
 270 struct tree_opt_pass pass_fixup_cfg =
 271 {
 272   "fixupcfg",                           /* name */
 273   NULL,                                 /* gate */
 274   execute_fixup_cfg,                    /* execute */
 275   NULL,                                 /* sub */
 276   NULL,                                 /* next */
 277   0,                                    /* static_pass_number */
 278   0,                                    /* tv_id */
 279   PROP_cfg,                             /* properties_required */
 280   0,                                    /* properties_provided */
 281   0,                                    /* properties_destroyed */
 282   0,                                    /* todo_flags_start */
 283   TODO_dump_func,                       /* todo_flags_finish */
 284   0                                     /* letter */
 285 };
 286
 287 /* Do the actions required to initialize internal data structures used
 288    in tree-ssa optimization passes.  */
 289
 290 static unsigned int
 291 execute_init_datastructures (void)
 292 {
 293   /* Allocate hash tables, arrays and other structures.  */
 294   init_tree_ssa ();
 295   return 0;
 296 }
 297
 298 struct tree_opt_pass pass_init_datastructures =
 299 {
 300   NULL,                                 /* name */
 301   NULL,                                 /* gate */
 302   execute_init_datastructures,          /* execute */
 303   NULL,                                 /* sub */
 304   NULL,                                 /* next */
 305   0,                                    /* static_pass_number */
 306   0,                                    /* tv_id */
 307   PROP_cfg,                             /* properties_required */
 308   0,                                    /* properties_provided */
 309   0,                                    /* properties_destroyed */
 310   0,                                    /* todo_flags_start */
 311   0,                                    /* todo_flags_finish */
 312   0                                     /* letter */
 313 };
 314
 315 void
 316 tree_lowering_passes (tree fn)
 317 {
 318   tree saved_current_function_decl = current_function_decl;
 319
 320   current_function_decl = fn;
 321   push_cfun (DECL_STRUCT_FUNCTION (fn));
 322   tree_register_cfg_hooks ();
 323   bitmap_obstack_initialize (NULL);
 324   execute_pass_list (all_lowering_passes);
 325   free_dominance_info (CDI_POST_DOMINATORS);
 326   compact_blocks ();
 327   current_function_decl = saved_current_function_decl;
 328   bitmap_obstack_release (NULL);
 329   pop_cfun ();
 330 }
 331
 332 /* Update recursively all inlined_to pointers of functions
 333    inlined into NODE to INLINED_TO.  */
 334 static void
 335 update_inlined_to_pointers (struct cgraph_node *node,
 336                             struct cgraph_node *inlined_to)
 337 {
 338   struct cgraph_edge *e;
 339   for (e = node->callees; e; e = e->next_callee)
 340     {
 341       if (e->callee->global.inlined_to)
 342         {
 343           e->callee->global.inlined_to = inlined_to;
 344           update_inlined_to_pointers (e->callee, inlined_to);
 345         }
 346     }
 347 }
 348
 349 \f
 350 /* For functions-as-trees languages, this performs all optimization and
 351    compilation for FNDECL.  */
 352
 353 void
 354 tree_rest_of_compilation (tree fndecl)
 355 {
 356   location_t saved_loc;
 357   struct cgraph_node *node;
 358
 359   timevar_push (TV_EXPAND);
 360
 361   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 362
 363   node = cgraph_node (fndecl);
 364
 365   /* We might need the body of this function so that we can expand
 366      it inline somewhere else.  */
 367   if (cgraph_preserve_function_body_p (fndecl))
 368     save_inline_function_body (node);
 369
 370   /* Initialize the RTL code for the function.  */
 371   current_function_decl = fndecl;
 372   saved_loc = input_location;
 373   input_location = DECL_SOURCE_LOCATION (fndecl);
 374   init_function_start (fndecl);
 375
 376   /* Even though we're inside a function body, we still don't want to
 377      call expand_expr to calculate the size of a variable-sized array.
 378      We haven't necessarily assigned RTL to all variables yet, so it's
 379      not safe to try to expand expressions involving them.  */
 380   cfun->x_dont_save_pending_sizes_p = 1;
 381   cfun->after_inlining = true;
 382
 383   if (flag_inline_trees)
 384     {
 385       struct cgraph_edge *e;
 386       for (e = node->callees; e; e = e->next_callee)
 387         if (!e->inline_failed || warn_inline)
 388           break;
 389       if (e)
 390         {
 391           timevar_push (TV_INTEGRATION);
 392           optimize_inline_calls (fndecl);
 393           timevar_pop (TV_INTEGRATION);
 394         }
 395     }
 396   /* We are not going to maintain the cgraph edges up to date.
 397      Kill it so it won't confuse us.  */
 398   while (node->callees)
 399     {
 400       /* In non-unit-at-a-time we must mark all referenced functions as needed.
 401          */
 402       if (node->callees->callee->analyzed && !flag_unit_at_a_time)
 403         cgraph_mark_needed_node (node->callees->callee);
 404       cgraph_remove_edge (node->callees);
 405     }
 406
 407   /* We are not going to maintain the cgraph edges up to date.
 408      Kill it so it won't confuse us.  */
 409   cgraph_node_remove_callees (node);
 410
 411
 412   /* Initialize the default bitmap obstack.  */
 413   bitmap_obstack_initialize (NULL);
 414   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 415
 416   tree_register_cfg_hooks ();
 417   /* Perform all tree transforms and optimizations.  */
 418   execute_pass_list (all_passes);
 419
 420   bitmap_obstack_release (&reg_obstack);
 421
 422   /* Release the default bitmap obstack.  */
 423   bitmap_obstack_release (NULL);
 424
 425   DECL_SAVED_TREE (fndecl) = NULL;
 426   cfun = 0;
 427
 428   /* If requested, warn about function definitions where the function will
 429      return a value (usually of some struct or union type) which itself will
 430      take up a lot of stack space.  */
 431   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 432     {
 433       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 434
 435       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 436           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 437           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 438                                    larger_than_size))
 439         {
 440           unsigned int size_as_int
 441             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 442
 443           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 444             warning (0, "size of return value of %q+D is %u bytes",
 445                      fndecl, size_as_int);
 446           else
 447             warning (0, "size of return value of %q+D is larger than %wd bytes",
 448                      fndecl, larger_than_size);
 449         }
 450     }
 451
 452   if (!flag_inline_trees)
 453     {
 454       DECL_SAVED_TREE (fndecl) = NULL;
 455       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 456           && !cgraph_node (fndecl)->origin)
 457         {
 458           /* Stop pointing to the local nodes about to be freed.
 459              But DECL_INITIAL must remain nonzero so we know this
 460              was an actual function definition.
 461              For a nested function, this is done in c_pop_function_context.
 462              If rest_of_compilation set this to 0, leave it 0.  */
 463           if (DECL_INITIAL (fndecl) != 0)
 464             DECL_INITIAL (fndecl) = error_mark_node;
 465         }
 466     }
 467
 468   input_location = saved_loc;
 469
 470   ggc_collect ();
 471   timevar_pop (TV_EXPAND);
 472 }