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