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-pass.h"
  42 #include "ggc.h"
  43 #include "cgraph.h"
  44 #include "graph.h"
  45 #include "cfgloop.h"
  46 #include "except.h"
  47 #include "plugin.h"
  48 #include "regset.h"     /* FIXME: For reg_obstack.  */
  49
  50 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  51
  52 static bool
  53 gate_all_optimizations (void)
  54 {
  55   return (optimize >= 1
  56           /* Don't bother doing anything if the program has errors.
  57              We have to pass down the queue if we already went into SSA */
  58           && (!seen_error () || gimple_in_ssa_p (cfun)));
  59 }
  60
  61 struct gimple_opt_pass pass_all_optimizations =
  62 {
  63  {
  64   GIMPLE_PASS,
  65   "*all_optimizations",                 /* name */
  66   gate_all_optimizations,               /* gate */
  67   NULL,                                 /* execute */
  68   NULL,                                 /* sub */
  69   NULL,                                 /* next */
  70   0,                                    /* static_pass_number */
  71   TV_OPTIMIZE,                          /* tv_id */
  72   0,                                    /* properties_required */
  73   0,                                    /* properties_provided */
  74   0,                                    /* properties_destroyed */
  75   0,                                    /* todo_flags_start */
  76   0                                     /* todo_flags_finish */
  77  }
  78 };
  79
  80 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  81
  82 static bool
  83 gate_all_early_local_passes (void)
  84 {
  85           /* Don't bother doing anything if the program has errors.  */
  86   return (!seen_error () && !in_lto_p);
  87 }
  88
  89 static unsigned int
  90 execute_all_early_local_passes (void)
  91 {
  92   /* Once this pass (and its sub-passes) are complete, all functions
  93      will be in SSA form.  Technically this state change is happening
  94      a tad early, since the sub-passes have not yet run, but since
  95      none of the sub-passes are IPA passes and do not create new
  96      functions, this is ok.  We're setting this value for the benefit
  97      of IPA passes that follow.  */
  98   if (cgraph_state < CGRAPH_STATE_IPA_SSA)
  99     cgraph_state = CGRAPH_STATE_IPA_SSA;
 100   return 0;
 101 }
 102
 103 struct simple_ipa_opt_pass pass_early_local_passes =
 104 {
 105  {
 106   SIMPLE_IPA_PASS,
 107   "early_local_cleanups",               /* name */
 108   gate_all_early_local_passes,          /* gate */
 109   execute_all_early_local_passes,       /* execute */
 110   NULL,                                 /* sub */
 111   NULL,                                 /* next */
 112   0,                                    /* static_pass_number */
 113   TV_EARLY_LOCAL,                       /* tv_id */
 114   0,                                    /* properties_required */
 115   0,                                    /* properties_provided */
 116   0,                                    /* properties_destroyed */
 117   0,                                    /* todo_flags_start */
 118   TODO_remove_functions                 /* todo_flags_finish */
 119  }
 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   NULL,                                 /* 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
 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_post_optimizing (void)
 159 {
 160   unsigned int todo = 0;
 161   if (cleanup_tree_cfg ())
 162     todo |= TODO_update_ssa;
 163   maybe_remove_unreachable_handlers ();
 164   cleanup_dead_labels ();
 165   group_case_labels ();
 166   if ((flag_compare_debug_opt || flag_compare_debug)
 167       && flag_dump_final_insns)
 168     {
 169       FILE *final_output = fopen (flag_dump_final_insns, "a");
 170
 171       if (!final_output)
 172         {
 173           error ("could not open final insn dump file %qs: %m",
 174                  flag_dump_final_insns);
 175           flag_dump_final_insns = NULL;
 176         }
 177       else
 178         {
 179           int save_unnumbered = flag_dump_unnumbered;
 180           int save_noaddr = flag_dump_noaddr;
 181
 182           flag_dump_noaddr = flag_dump_unnumbered = 1;
 183           fprintf (final_output, "\n");
 184           dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
 185           flag_dump_noaddr = save_noaddr;
 186           flag_dump_unnumbered = save_unnumbered;
 187           if (fclose (final_output))
 188             {
 189               error ("could not close final insn dump file %qs: %m",
 190                      flag_dump_final_insns);
 191               flag_dump_final_insns = NULL;
 192             }
 193         }
 194     }
 195   return todo;
 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_TREE_CLEANUP_CFG,                  /* tv_id */
 209   PROP_cfg,                             /* properties_required */
 210   0,                                    /* properties_provided */
 211   0,                                    /* properties_destroyed */
 212   0,                                    /* todo_flags_start */
 213   TODO_remove_unused_locals             /* todo_flags_finish */
 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 /* 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_get_node (current_function_decl)->count
 252                     * REG_BR_PROB_BASE + ENTRY_BLOCK_PTR->count / 2)
 253                    / ENTRY_BLOCK_PTR->count);
 254   else
 255     count_scale = REG_BR_PROB_BASE;
 256
 257   ENTRY_BLOCK_PTR->count = cgraph_get_node (current_function_decl)->count;
 258   EXIT_BLOCK_PTR->count = (EXIT_BLOCK_PTR->count * count_scale
 259                            + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 260
 261   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 262     e->count = (e->count * count_scale
 263        + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 264
 265   FOR_EACH_BB (bb)
 266     {
 267       bb->count = (bb->count * count_scale
 268                    + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 269       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 270         {
 271           gimple stmt = gsi_stmt (gsi);
 272           tree decl = is_gimple_call (stmt)
 273                       ? gimple_call_fndecl (stmt)
 274                       : NULL;
 275           if (decl)
 276             {
 277               int flags = gimple_call_flags (stmt);
 278               if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
 279                 {
 280                   if (gimple_purge_dead_abnormal_call_edges (bb))
 281                     todo |= TODO_cleanup_cfg;
 282
 283                   if (gimple_in_ssa_p (cfun))
 284                     {
 285                       todo |= TODO_update_ssa | TODO_cleanup_cfg;
 286                       update_stmt (stmt);
 287                     }
 288                 }
 289
 290               if (flags & ECF_NORETURN
 291                   && fixup_noreturn_call (stmt))
 292                 todo |= TODO_cleanup_cfg;
 293              }
 294
 295           if (maybe_clean_eh_stmt (stmt)
 296               && gimple_purge_dead_eh_edges (bb))
 297             todo |= TODO_cleanup_cfg;
 298         }
 299
 300       FOR_EACH_EDGE (e, ei, bb->succs)
 301         e->count = (e->count * count_scale
 302                     + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 303     }
 304   if (count_scale != REG_BR_PROB_BASE)
 305     compute_function_frequency ();
 306
 307   /* We just processed all calls.  */
 308   if (cfun->gimple_df)
 309     {
 310       VEC_free (gimple, gc, MODIFIED_NORETURN_CALLS (cfun));
 311       MODIFIED_NORETURN_CALLS (cfun) = NULL;
 312     }
 313
 314   /* Dump a textual representation of the flowgraph.  */
 315   if (dump_file)
 316     gimple_dump_cfg (dump_file, dump_flags);
 317
 318   return todo;
 319 }
 320
 321 struct gimple_opt_pass pass_fixup_cfg =
 322 {
 323  {
 324   GIMPLE_PASS,
 325   "*free_cfg_annotations",              /* name */
 326   NULL,                                 /* gate */
 327   execute_fixup_cfg,                    /* execute */
 328   NULL,                                 /* sub */
 329   NULL,                                 /* next */
 330   0,                                    /* static_pass_number */
 331   TV_NONE,                              /* tv_id */
 332   PROP_cfg,                             /* properties_required */
 333   0,                                    /* properties_provided */
 334   0,                                    /* properties_destroyed */
 335   0,                                    /* todo_flags_start */
 336   0                                     /* todo_flags_finish */
 337  }
 338 };
 339
 340 /* Do the actions required to initialize internal data structures used
 341    in tree-ssa optimization passes.  */
 342
 343 static unsigned int
 344 execute_init_datastructures (void)
 345 {
 346   /* Allocate hash tables, arrays and other structures.  */
 347   init_tree_ssa (cfun);
 348   return 0;
 349 }
 350
 351 struct gimple_opt_pass pass_init_datastructures =
 352 {
 353  {
 354   GIMPLE_PASS,
 355   "*init_datastructures",               /* name */
 356   NULL,                                 /* gate */
 357   execute_init_datastructures,          /* execute */
 358   NULL,                                 /* sub */
 359   NULL,                                 /* next */
 360   0,                                    /* static_pass_number */
 361   TV_NONE,                              /* tv_id */
 362   PROP_cfg,                             /* properties_required */
 363   0,                                    /* properties_provided */
 364   0,                                    /* properties_destroyed */
 365   0,                                    /* todo_flags_start */
 366   0                                     /* todo_flags_finish */
 367  }
 368 };
 369
 370 void
 371 tree_lowering_passes (tree fn)
 372 {
 373   tree saved_current_function_decl = current_function_decl;
 374
 375   current_function_decl = fn;
 376   push_cfun (DECL_STRUCT_FUNCTION (fn));
 377   gimple_register_cfg_hooks ();
 378   bitmap_obstack_initialize (NULL);
 379   execute_pass_list (all_lowering_passes);
 380   if (optimize && cgraph_global_info_ready)
 381     execute_pass_list (pass_early_local_passes.pass.sub);
 382   free_dominance_info (CDI_POST_DOMINATORS);
 383   free_dominance_info (CDI_DOMINATORS);
 384   compact_blocks ();
 385   current_function_decl = saved_current_function_decl;
 386   bitmap_obstack_release (NULL);
 387   pop_cfun ();
 388 }
 389 \f
 390 /* For functions-as-trees languages, this performs all optimization and
 391    compilation for FNDECL.  */
 392
 393 void
 394 tree_rest_of_compilation (tree fndecl)
 395 {
 396   location_t saved_loc;
 397
 398   timevar_push (TV_REST_OF_COMPILATION);
 399
 400   gcc_assert (cgraph_global_info_ready);
 401
 402   /* Initialize the default bitmap obstack.  */
 403   bitmap_obstack_initialize (NULL);
 404
 405   /* Initialize the RTL code for the function.  */
 406   current_function_decl = fndecl;
 407   saved_loc = input_location;
 408   input_location = DECL_SOURCE_LOCATION (fndecl);
 409   init_function_start (fndecl);
 410
 411   gimple_register_cfg_hooks ();
 412
 413   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 414
 415   execute_all_ipa_transforms ();
 416
 417   /* Perform all tree transforms and optimizations.  */
 418
 419   /* Signal the start of passes.  */
 420   invoke_plugin_callbacks (PLUGIN_ALL_PASSES_START, NULL);
 421
 422   execute_pass_list (all_passes);
 423
 424   /* Signal the end of passes.  */
 425   invoke_plugin_callbacks (PLUGIN_ALL_PASSES_END, NULL);
 426
 427   bitmap_obstack_release (&reg_obstack);
 428
 429   /* Release the default bitmap obstack.  */
 430   bitmap_obstack_release (NULL);
 431
 432   set_cfun (NULL);
 433
 434   /* If requested, warn about function definitions where the function will
 435      return a value (usually of some struct or union type) which itself will
 436      take up a lot of stack space.  */
 437   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 438     {
 439       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 440
 441       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 442           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 443           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 444                                    larger_than_size))
 445         {
 446           unsigned int size_as_int
 447             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 448
 449           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 450             warning (OPT_Wlarger_than_, "size of return value of %q+D is %u bytes",
 451                      fndecl, size_as_int);
 452           else
 453             warning (OPT_Wlarger_than_, "size of return value of %q+D is larger than %wd bytes",
 454                      fndecl, larger_than_size);
 455         }
 456     }
 457
 458   gimple_set_body (fndecl, NULL);
 459   if (DECL_STRUCT_FUNCTION (fndecl) == 0
 460       && !cgraph_get_node (fndecl)->origin)
 461     {
 462       /* Stop pointing to the local nodes about to be freed.
 463          But DECL_INITIAL must remain nonzero so we know this
 464          was an actual function definition.
 465          For a nested function, this is done in c_pop_function_context.
 466          If rest_of_compilation set this to 0, leave it 0.  */
 467       if (DECL_INITIAL (fndecl) != 0)
 468         DECL_INITIAL (fndecl) = error_mark_node;
 469     }
 470
 471   input_location = saved_loc;
 472
 473   ggc_collect ();
 474   timevar_pop (TV_REST_OF_COMPILATION);
 475 }