gcc/tree-optimize.c

   1 /* Top-level control of tree optimizations.
   2    Copyright 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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              We have to pass down the queue if we already went into SSA */
  62           && (!(errorcount || sorrycount) || gimple_in_ssa_p (cfun)));
  63 }
  64
  65 struct gimple_opt_pass pass_all_optimizations =
  66 {
  67  {
  68   GIMPLE_PASS,
  69   "*all_optimizations",                 /* name */
  70   gate_all_optimizations,               /* gate */
  71   NULL,                                 /* execute */
  72   NULL,                                 /* sub */
  73   NULL,                                 /* next */
  74   0,                                    /* static_pass_number */
  75   TV_NONE,                              /* tv_id */
  76   0,                                    /* properties_required */
  77   0,                                    /* properties_provided */
  78   0,                                    /* properties_destroyed */
  79   0,                                    /* todo_flags_start */
  80   0                                     /* todo_flags_finish */
  81  }
  82 };
  83
  84 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  85
  86 static bool
  87 gate_all_early_local_passes (void)
  88 {
  89           /* Don't bother doing anything if the program has errors.  */
  90   return (!errorcount && !sorrycount && !in_lto_p);
  91 }
  92
  93 struct simple_ipa_opt_pass pass_early_local_passes =
  94 {
  95  {
  96   SIMPLE_IPA_PASS,
  97   "early_local_cleanups",               /* name */
  98   gate_all_early_local_passes,          /* gate */
  99   NULL,                                 /* execute */
 100   NULL,                                 /* sub */
 101   NULL,                                 /* next */
 102   0,                                    /* static_pass_number */
 103   TV_NONE,                              /* tv_id */
 104   0,                                    /* properties_required */
 105   0,                                    /* properties_provided */
 106   0,                                    /* properties_destroyed */
 107   0,                                    /* todo_flags_start */
 108   TODO_remove_functions                 /* todo_flags_finish */
 109  }
 110 };
 111
 112 static unsigned int
 113 execute_early_local_optimizations (void)
 114 {
 115   /* First time we start with early optimization we need to advance
 116      cgraph state so newly inserted functions are also early optimized.
 117      However we execute early local optimizations for lately inserted
 118      functions, in that case don't reset cgraph state back to IPA_SSA.  */
 119   if (cgraph_state < CGRAPH_STATE_IPA_SSA)
 120     cgraph_state = CGRAPH_STATE_IPA_SSA;
 121   return 0;
 122 }
 123
 124 /* Gate: execute, or not, all of the non-trivial optimizations.  */
 125
 126 static bool
 127 gate_all_early_optimizations (void)
 128 {
 129   return (optimize >= 1
 130           /* Don't bother doing anything if the program has errors.  */
 131           && !(errorcount || sorrycount));
 132 }
 133
 134 struct gimple_opt_pass pass_all_early_optimizations =
 135 {
 136  {
 137   GIMPLE_PASS,
 138   "early_optimizations",                /* name */
 139   gate_all_early_optimizations,         /* gate */
 140   execute_early_local_optimizations,    /* execute */
 141   NULL,                                 /* sub */
 142   NULL,                                 /* next */
 143   0,                                    /* static_pass_number */
 144   TV_NONE,                              /* tv_id */
 145   0,                                    /* properties_required */
 146   0,                                    /* properties_provided */
 147   0,                                    /* properties_destroyed */
 148   0,                                    /* todo_flags_start */
 149   0                                     /* todo_flags_finish */
 150  }
 151 };
 152
 153 /* Pass: cleanup the CFG just before expanding trees to RTL.
 154    This is just a round of label cleanups and case node grouping
 155    because after the tree optimizers have run such cleanups may
 156    be necessary.  */
 157
 158 static unsigned int
 159 execute_cleanup_cfg_pre_ipa (void)
 160 {
 161   cleanup_tree_cfg ();
 162   return 0;
 163 }
 164
 165 struct gimple_opt_pass pass_cleanup_cfg =
 166 {
 167  {
 168   GIMPLE_PASS,
 169   "cleanup_cfg",                        /* name */
 170   NULL,                                 /* gate */
 171   execute_cleanup_cfg_pre_ipa,          /* execute */
 172   NULL,                                 /* sub */
 173   NULL,                                 /* next */
 174   0,                                    /* static_pass_number */
 175   TV_NONE,                              /* tv_id */
 176   PROP_cfg,                             /* properties_required */
 177   0,                                    /* properties_provided */
 178   0,                                    /* properties_destroyed */
 179   0,                                    /* todo_flags_start */
 180   TODO_dump_func                        /* todo_flags_finish */
 181  }
 182 };
 183
 184
 185 /* Pass: cleanup the CFG just before expanding trees to RTL.
 186    This is just a round of label cleanups and case node grouping
 187    because after the tree optimizers have run such cleanups may
 188    be necessary.  */
 189
 190 static unsigned int
 191 execute_cleanup_cfg_post_optimizing (void)
 192 {
 193   fold_cond_expr_cond ();
 194   cleanup_tree_cfg ();
 195   cleanup_dead_labels ();
 196   group_case_labels ();
 197   return 0;
 198 }
 199
 200 struct gimple_opt_pass pass_cleanup_cfg_post_optimizing =
 201 {
 202  {
 203   GIMPLE_PASS,
 204   "optimized",                          /* name */
 205   NULL,                                 /* gate */
 206   execute_cleanup_cfg_post_optimizing,  /* execute */
 207   NULL,                                 /* sub */
 208   NULL,                                 /* next */
 209   0,                                    /* static_pass_number */
 210   TV_NONE,                              /* tv_id */
 211   PROP_cfg,                             /* properties_required */
 212   0,                                    /* properties_provided */
 213   0,                                    /* properties_destroyed */
 214   0,                                    /* todo_flags_start */
 215   TODO_dump_func                        /* todo_flags_finish */
 216     | TODO_remove_unused_locals
 217  }
 218 };
 219
 220 /* Pass: do the actions required to finish with tree-ssa optimization
 221    passes.  */
 222
 223 unsigned int
 224 execute_free_datastructures (void)
 225 {
 226   free_dominance_info (CDI_DOMINATORS);
 227   free_dominance_info (CDI_POST_DOMINATORS);
 228
 229   /* And get rid of annotations we no longer need.  */
 230   delete_tree_cfg_annotations ();
 231
 232   return 0;
 233 }
 234
 235 /* Pass: fixup_cfg.  IPA passes, compilation of earlier functions or inlining
 236    might have changed some properties, such as marked functions nothrow.
 237    Remove redundant edges and basic blocks, and create new ones if necessary.
 238
 239    This pass can't be executed as stand alone pass from pass manager, because
 240    in between inlining and this fixup the verify_flow_info would fail.  */
 241
 242 unsigned int
 243 execute_fixup_cfg (void)
 244 {
 245   basic_block bb;
 246   gimple_stmt_iterator gsi;
 247   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 248   gcov_type count_scale;
 249   edge e;
 250   edge_iterator ei;
 251
 252   if (ENTRY_BLOCK_PTR->count)
 253     count_scale = (cgraph_node (current_function_decl)->count * REG_BR_PROB_BASE
 254                    + ENTRY_BLOCK_PTR->count / 2) / ENTRY_BLOCK_PTR->count;
 255   else
 256     count_scale = REG_BR_PROB_BASE;
 257
 258   ENTRY_BLOCK_PTR->count = cgraph_node (current_function_decl)->count;
 259   EXIT_BLOCK_PTR->count = (EXIT_BLOCK_PTR->count * count_scale
 260                            + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 261
 262   FOR_EACH_BB (bb)
 263     {
 264       bb->count = (bb->count * count_scale
 265                    + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 266       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 267         {
 268           gimple stmt = gsi_stmt (gsi);
 269           tree decl = is_gimple_call (stmt)
 270                       ? gimple_call_fndecl (stmt)
 271                       : NULL;
 272
 273           if (decl
 274               && gimple_call_flags (stmt) & (ECF_CONST
 275                                              | ECF_PURE
 276                                              | ECF_LOOPING_CONST_OR_PURE))
 277             {
 278               if (gimple_in_ssa_p (cfun))
 279                 {
 280                   todo |= TODO_update_ssa | TODO_cleanup_cfg;
 281                   mark_symbols_for_renaming (stmt);
 282                   update_stmt (stmt);
 283                 }
 284             }
 285
 286           maybe_clean_eh_stmt (stmt);
 287         }
 288
 289       if (gimple_purge_dead_eh_edges (bb))
 290         todo |= TODO_cleanup_cfg;
 291       FOR_EACH_EDGE (e, ei, bb->succs)
 292         e->count = (e->count * count_scale
 293                     + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 294     }
 295   if (count_scale != REG_BR_PROB_BASE)
 296     compute_function_frequency ();
 297
 298   /* Dump a textual representation of the flowgraph.  */
 299   if (dump_file)
 300     gimple_dump_cfg (dump_file, dump_flags);
 301
 302   return todo;
 303 }
 304
 305 struct gimple_opt_pass pass_fixup_cfg =
 306 {
 307  {
 308   GIMPLE_PASS,
 309   "*free_cfg_annotations",              /* name */
 310   NULL,                                 /* gate */
 311   execute_fixup_cfg,                    /* execute */
 312   NULL,                                 /* sub */
 313   NULL,                                 /* next */
 314   0,                                    /* static_pass_number */
 315   TV_NONE,                              /* tv_id */
 316   PROP_cfg,                             /* properties_required */
 317   0,                                    /* properties_provided */
 318   0,                                    /* properties_destroyed */
 319   0,                                    /* todo_flags_start */
 320   0                                     /* todo_flags_finish */
 321  }
 322 };
 323
 324 /* Do the actions required to initialize internal data structures used
 325    in tree-ssa optimization passes.  */
 326
 327 static unsigned int
 328 execute_init_datastructures (void)
 329 {
 330   /* Allocate hash tables, arrays and other structures.  */
 331   init_tree_ssa (cfun);
 332   return 0;
 333 }
 334
 335 struct gimple_opt_pass pass_init_datastructures =
 336 {
 337  {
 338   GIMPLE_PASS,
 339   "*init_datastructures",               /* name */
 340   NULL,                                 /* gate */
 341   execute_init_datastructures,          /* execute */
 342   NULL,                                 /* sub */
 343   NULL,                                 /* next */
 344   0,                                    /* static_pass_number */
 345   TV_NONE,                              /* tv_id */
 346   PROP_cfg,                             /* properties_required */
 347   0,                                    /* properties_provided */
 348   0,                                    /* properties_destroyed */
 349   0,                                    /* todo_flags_start */
 350   0                                     /* todo_flags_finish */
 351  }
 352 };
 353
 354 void
 355 tree_lowering_passes (tree fn)
 356 {
 357   tree saved_current_function_decl = current_function_decl;
 358
 359   current_function_decl = fn;
 360   push_cfun (DECL_STRUCT_FUNCTION (fn));
 361   gimple_register_cfg_hooks ();
 362   bitmap_obstack_initialize (NULL);
 363   execute_pass_list (all_lowering_passes);
 364   if (optimize && cgraph_global_info_ready)
 365     execute_pass_list (pass_early_local_passes.pass.sub);
 366   free_dominance_info (CDI_POST_DOMINATORS);
 367   free_dominance_info (CDI_DOMINATORS);
 368   compact_blocks ();
 369   current_function_decl = saved_current_function_decl;
 370   bitmap_obstack_release (NULL);
 371   pop_cfun ();
 372 }
 373 \f
 374 /* For functions-as-trees languages, this performs all optimization and
 375    compilation for FNDECL.  */
 376
 377 void
 378 tree_rest_of_compilation (tree fndecl)
 379 {
 380   location_t saved_loc;
 381   struct cgraph_node *node;
 382
 383   timevar_push (TV_EXPAND);
 384
 385   gcc_assert (cgraph_global_info_ready);
 386
 387   node = cgraph_node (fndecl);
 388
 389   /* Initialize the default bitmap obstack.  */
 390   bitmap_obstack_initialize (NULL);
 391
 392   /* Initialize the RTL code for the function.  */
 393   current_function_decl = fndecl;
 394   saved_loc = input_location;
 395   input_location = DECL_SOURCE_LOCATION (fndecl);
 396   init_function_start (fndecl);
 397
 398   /* Even though we're inside a function body, we still don't want to
 399      call expand_expr to calculate the size of a variable-sized array.
 400      We haven't necessarily assigned RTL to all variables yet, so it's
 401      not safe to try to expand expressions involving them.  */
 402   cfun->dont_save_pending_sizes_p = 1;
 403
 404   gimple_register_cfg_hooks ();
 405
 406   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 407
 408   execute_all_ipa_transforms ();
 409
 410   /* Perform all tree transforms and optimizations.  */
 411   execute_pass_list (all_passes);
 412
 413   bitmap_obstack_release (&reg_obstack);
 414
 415   /* Release the default bitmap obstack.  */
 416   bitmap_obstack_release (NULL);
 417
 418   set_cfun (NULL);
 419
 420   /* If requested, warn about function definitions where the function will
 421      return a value (usually of some struct or union type) which itself will
 422      take up a lot of stack space.  */
 423   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 424     {
 425       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 426
 427       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 428           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 429           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 430                                    larger_than_size))
 431         {
 432           unsigned int size_as_int
 433             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 434
 435           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 436             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is %u bytes",
 437                      fndecl, size_as_int);
 438           else
 439             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is larger than %wd bytes",
 440                      fndecl, larger_than_size);
 441         }
 442     }
 443
 444   gimple_set_body (fndecl, NULL);
 445   if (DECL_STRUCT_FUNCTION (fndecl) == 0
 446       && !cgraph_node (fndecl)->origin)
 447     {
 448       /* Stop pointing to the local nodes about to be freed.
 449          But DECL_INITIAL must remain nonzero so we know this
 450          was an actual function definition.
 451          For a nested function, this is done in c_pop_function_context.
 452          If rest_of_compilation set this to 0, leave it 0.  */
 453       if (DECL_INITIAL (fndecl) != 0)
 454         DECL_INITIAL (fndecl) = error_mark_node;
 455     }
 456
 457   input_location = saved_loc;
 458
 459   ggc_collect ();
 460   timevar_pop (TV_EXPAND);
 461 }