gcc/tree-optimize.c

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