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   if ((flag_compare_debug_opt || flag_compare_debug)
 195       && flag_dump_final_insns)
 196     {
 197       FILE *final_output = fopen (flag_dump_final_insns, "a");
 198
 199       if (!final_output)
 200         {
 201           error ("could not open final insn dump file %qs: %m",
 202                  flag_dump_final_insns);
 203           flag_dump_final_insns = NULL;
 204         }
 205       else
 206         {
 207           int save_unnumbered = flag_dump_unnumbered;
 208           int save_noaddr = flag_dump_noaddr;
 209
 210           flag_dump_noaddr = flag_dump_unnumbered = 1;
 211           fprintf (final_output, "\n");
 212           dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
 213           flag_dump_noaddr = save_noaddr;
 214           flag_dump_unnumbered = save_unnumbered;
 215           if (fclose (final_output))
 216             {
 217               error ("could not close final insn dump file %qs: %m",
 218                      flag_dump_final_insns);
 219               flag_dump_final_insns = NULL;
 220             }
 221         }
 222     }
 223   return 0;
 224 }
 225
 226 struct gimple_opt_pass pass_cleanup_cfg_post_optimizing =
 227 {
 228  {
 229   GIMPLE_PASS,
 230   "optimized",                          /* name */
 231   NULL,                                 /* gate */
 232   execute_cleanup_cfg_post_optimizing,  /* execute */
 233   NULL,                                 /* sub */
 234   NULL,                                 /* next */
 235   0,                                    /* static_pass_number */
 236   TV_NONE,                              /* tv_id */
 237   PROP_cfg,                             /* properties_required */
 238   0,                                    /* properties_provided */
 239   0,                                    /* properties_destroyed */
 240   0,                                    /* todo_flags_start */
 241   TODO_dump_func                        /* todo_flags_finish */
 242     | TODO_remove_unused_locals
 243  }
 244 };
 245
 246 /* Pass: do the actions required to finish with tree-ssa optimization
 247    passes.  */
 248
 249 unsigned int
 250 execute_free_datastructures (void)
 251 {
 252   free_dominance_info (CDI_DOMINATORS);
 253   free_dominance_info (CDI_POST_DOMINATORS);
 254
 255   /* And get rid of annotations we no longer need.  */
 256   delete_tree_cfg_annotations ();
 257
 258   return 0;
 259 }
 260
 261 /* Pass: fixup_cfg.  IPA passes, compilation of earlier functions or inlining
 262    might have changed some properties, such as marked functions nothrow,
 263    pure, const or noreturn.
 264    Remove redundant edges and basic blocks, and create new ones if necessary.
 265
 266    This pass can't be executed as stand alone pass from pass manager, because
 267    in between inlining and this fixup the verify_flow_info would fail.  */
 268
 269 unsigned int
 270 execute_fixup_cfg (void)
 271 {
 272   basic_block bb;
 273   gimple_stmt_iterator gsi;
 274   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 275   gcov_type count_scale;
 276   edge e;
 277   edge_iterator ei;
 278
 279   if (ENTRY_BLOCK_PTR->count)
 280     count_scale = (cgraph_node (current_function_decl)->count * REG_BR_PROB_BASE
 281                    + ENTRY_BLOCK_PTR->count / 2) / ENTRY_BLOCK_PTR->count;
 282   else
 283     count_scale = REG_BR_PROB_BASE;
 284
 285   ENTRY_BLOCK_PTR->count = cgraph_node (current_function_decl)->count;
 286   EXIT_BLOCK_PTR->count = (EXIT_BLOCK_PTR->count * count_scale
 287                            + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 288
 289   FOR_EACH_BB (bb)
 290     {
 291       bb->count = (bb->count * count_scale
 292                    + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 293       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 294         {
 295           gimple stmt = gsi_stmt (gsi);
 296           tree decl = is_gimple_call (stmt)
 297                       ? gimple_call_fndecl (stmt)
 298                       : NULL;
 299           if (decl)
 300             {
 301               int flags = gimple_call_flags (stmt);
 302               if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
 303                 {
 304                   if (gimple_in_ssa_p (cfun))
 305                     {
 306                       todo |= TODO_update_ssa | TODO_cleanup_cfg;
 307                       mark_symbols_for_renaming (stmt);
 308                       update_stmt (stmt);
 309                     }
 310                 }
 311
 312               if (flags & ECF_NORETURN
 313                   && fixup_noreturn_call (stmt))
 314                 todo |= TODO_cleanup_cfg;
 315              }
 316
 317           maybe_clean_eh_stmt (stmt);
 318         }
 319
 320       if (gimple_purge_dead_eh_edges (bb))
 321         todo |= TODO_cleanup_cfg;
 322       FOR_EACH_EDGE (e, ei, bb->succs)
 323         e->count = (e->count * count_scale
 324                     + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 325     }
 326   if (count_scale != REG_BR_PROB_BASE)
 327     compute_function_frequency ();
 328
 329   /* We just processed all calls.  */
 330   if (cfun->gimple_df)
 331     {
 332       VEC_free (gimple, gc, MODIFIED_NORETURN_CALLS (cfun));
 333       MODIFIED_NORETURN_CALLS (cfun) = NULL;
 334     }
 335
 336   /* Dump a textual representation of the flowgraph.  */
 337   if (dump_file)
 338     gimple_dump_cfg (dump_file, dump_flags);
 339
 340   return todo;
 341 }
 342
 343 struct gimple_opt_pass pass_fixup_cfg =
 344 {
 345  {
 346   GIMPLE_PASS,
 347   "*free_cfg_annotations",              /* name */
 348   NULL,                                 /* gate */
 349   execute_fixup_cfg,                    /* execute */
 350   NULL,                                 /* sub */
 351   NULL,                                 /* next */
 352   0,                                    /* static_pass_number */
 353   TV_NONE,                              /* tv_id */
 354   PROP_cfg,                             /* properties_required */
 355   0,                                    /* properties_provided */
 356   0,                                    /* properties_destroyed */
 357   0,                                    /* todo_flags_start */
 358   0                                     /* todo_flags_finish */
 359  }
 360 };
 361
 362 /* Do the actions required to initialize internal data structures used
 363    in tree-ssa optimization passes.  */
 364
 365 static unsigned int
 366 execute_init_datastructures (void)
 367 {
 368   /* Allocate hash tables, arrays and other structures.  */
 369   init_tree_ssa (cfun);
 370   return 0;
 371 }
 372
 373 struct gimple_opt_pass pass_init_datastructures =
 374 {
 375  {
 376   GIMPLE_PASS,
 377   "*init_datastructures",               /* name */
 378   NULL,                                 /* gate */
 379   execute_init_datastructures,          /* execute */
 380   NULL,                                 /* sub */
 381   NULL,                                 /* next */
 382   0,                                    /* static_pass_number */
 383   TV_NONE,                              /* tv_id */
 384   PROP_cfg,                             /* properties_required */
 385   0,                                    /* properties_provided */
 386   0,                                    /* properties_destroyed */
 387   0,                                    /* todo_flags_start */
 388   0                                     /* todo_flags_finish */
 389  }
 390 };
 391
 392 void
 393 tree_lowering_passes (tree fn)
 394 {
 395   tree saved_current_function_decl = current_function_decl;
 396
 397   current_function_decl = fn;
 398   push_cfun (DECL_STRUCT_FUNCTION (fn));
 399   gimple_register_cfg_hooks ();
 400   bitmap_obstack_initialize (NULL);
 401   execute_pass_list (all_lowering_passes);
 402   if (optimize && cgraph_global_info_ready)
 403     execute_pass_list (pass_early_local_passes.pass.sub);
 404   free_dominance_info (CDI_POST_DOMINATORS);
 405   free_dominance_info (CDI_DOMINATORS);
 406   compact_blocks ();
 407   current_function_decl = saved_current_function_decl;
 408   bitmap_obstack_release (NULL);
 409   pop_cfun ();
 410 }
 411 \f
 412 /* For functions-as-trees languages, this performs all optimization and
 413    compilation for FNDECL.  */
 414
 415 void
 416 tree_rest_of_compilation (tree fndecl)
 417 {
 418   location_t saved_loc;
 419
 420   timevar_push (TV_EXPAND);
 421
 422   gcc_assert (cgraph_global_info_ready);
 423
 424   /* Initialize the default bitmap obstack.  */
 425   bitmap_obstack_initialize (NULL);
 426
 427   /* Initialize the RTL code for the function.  */
 428   current_function_decl = fndecl;
 429   saved_loc = input_location;
 430   input_location = DECL_SOURCE_LOCATION (fndecl);
 431   init_function_start (fndecl);
 432
 433   /* Even though we're inside a function body, we still don't want to
 434      call expand_expr to calculate the size of a variable-sized array.
 435      We haven't necessarily assigned RTL to all variables yet, so it's
 436      not safe to try to expand expressions involving them.  */
 437   cfun->dont_save_pending_sizes_p = 1;
 438
 439   gimple_register_cfg_hooks ();
 440
 441   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 442
 443   execute_all_ipa_transforms ();
 444
 445   /* Perform all tree transforms and optimizations.  */
 446
 447   /* Signal the start of passes.  */
 448   invoke_plugin_callbacks (PLUGIN_ALL_PASSES_START, NULL);
 449
 450   execute_pass_list (all_passes);
 451
 452   /* Signal the end of passes.  */
 453   invoke_plugin_callbacks (PLUGIN_ALL_PASSES_END, NULL);
 454
 455   bitmap_obstack_release (&reg_obstack);
 456
 457   /* Release the default bitmap obstack.  */
 458   bitmap_obstack_release (NULL);
 459
 460   set_cfun (NULL);
 461
 462   /* If requested, warn about function definitions where the function will
 463      return a value (usually of some struct or union type) which itself will
 464      take up a lot of stack space.  */
 465   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 466     {
 467       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 468
 469       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 470           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 471           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 472                                    larger_than_size))
 473         {
 474           unsigned int size_as_int
 475             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 476
 477           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 478             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is %u bytes",
 479                      fndecl, size_as_int);
 480           else
 481             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is larger than %wd bytes",
 482                      fndecl, larger_than_size);
 483         }
 484     }
 485
 486   gimple_set_body (fndecl, NULL);
 487   if (DECL_STRUCT_FUNCTION (fndecl) == 0
 488       && !cgraph_node (fndecl)->origin)
 489     {
 490       /* Stop pointing to the local nodes about to be freed.
 491          But DECL_INITIAL must remain nonzero so we know this
 492          was an actual function definition.
 493          For a nested function, this is done in c_pop_function_context.
 494          If rest_of_compilation set this to 0, leave it 0.  */
 495       if (DECL_INITIAL (fndecl) != 0)
 496         DECL_INITIAL (fndecl) = error_mark_node;
 497     }
 498
 499   input_location = saved_loc;
 500
 501   ggc_collect ();
 502   timevar_pop (TV_EXPAND);
 503 }