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