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