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_OPTIMIZE,                          /* 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_EARLY_LOCAL,                       /* 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
 153 /* Pass: cleanup the CFG just before expanding trees to RTL.
 154    This is just a round of label cleanups and case node grouping
 155    because after the tree optimizers have run such cleanups may
 156    be necessary.  */
 157
 158 static unsigned int
 159 execute_cleanup_cfg_post_optimizing (void)
 160 {
 161   cleanup_tree_cfg ();
 162   maybe_remove_unreachable_handlers ();
 163   cleanup_dead_labels ();
 164   group_case_labels ();
 165   if ((flag_compare_debug_opt || flag_compare_debug)
 166       && flag_dump_final_insns)
 167     {
 168       FILE *final_output = fopen (flag_dump_final_insns, "a");
 169
 170       if (!final_output)
 171         {
 172           error ("could not open final insn dump file %qs: %m",
 173                  flag_dump_final_insns);
 174           flag_dump_final_insns = NULL;
 175         }
 176       else
 177         {
 178           int save_unnumbered = flag_dump_unnumbered;
 179           int save_noaddr = flag_dump_noaddr;
 180
 181           flag_dump_noaddr = flag_dump_unnumbered = 1;
 182           fprintf (final_output, "\n");
 183           dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
 184           flag_dump_noaddr = save_noaddr;
 185           flag_dump_unnumbered = save_unnumbered;
 186           if (fclose (final_output))
 187             {
 188               error ("could not close final insn dump file %qs: %m",
 189                      flag_dump_final_insns);
 190               flag_dump_final_insns = NULL;
 191             }
 192         }
 193     }
 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_TREE_CLEANUP_CFG,                  /* tv_id */
 208   PROP_cfg,                             /* properties_required */
 209   0,                                    /* properties_provided */
 210   0,                                    /* properties_destroyed */
 211   0,                                    /* todo_flags_start */
 212   TODO_remove_unused_locals             /* todo_flags_finish */
 213  }
 214 };
 215
 216 /* Pass: do the actions required to finish with tree-ssa optimization
 217    passes.  */
 218
 219 unsigned int
 220 execute_free_datastructures (void)
 221 {
 222   free_dominance_info (CDI_DOMINATORS);
 223   free_dominance_info (CDI_POST_DOMINATORS);
 224
 225   /* And get rid of annotations we no longer need.  */
 226   delete_tree_cfg_annotations ();
 227
 228   return 0;
 229 }
 230
 231 /* IPA passes, compilation of earlier functions or inlining
 232    might have changed some properties, such as marked functions nothrow,
 233    pure, const or noreturn.
 234    Remove redundant edges and basic blocks, and create new ones if necessary.
 235
 236    This pass can't be executed as stand alone pass from pass manager, because
 237    in between inlining and this fixup the verify_flow_info would fail.  */
 238
 239 unsigned int
 240 execute_fixup_cfg (void)
 241 {
 242   basic_block bb;
 243   gimple_stmt_iterator gsi;
 244   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 245   gcov_type count_scale;
 246   edge e;
 247   edge_iterator ei;
 248
 249   if (ENTRY_BLOCK_PTR->count)
 250     count_scale = ((cgraph_get_node (current_function_decl)->count
 251                     * REG_BR_PROB_BASE + ENTRY_BLOCK_PTR->count / 2)
 252                    / ENTRY_BLOCK_PTR->count);
 253   else
 254     count_scale = REG_BR_PROB_BASE;
 255
 256   ENTRY_BLOCK_PTR->count = cgraph_get_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_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 261     e->count = (e->count * count_scale
 262        + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 263
 264   FOR_EACH_BB (bb)
 265     {
 266       bb->count = (bb->count * count_scale
 267                    + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 268       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 269         {
 270           gimple stmt = gsi_stmt (gsi);
 271           tree decl = is_gimple_call (stmt)
 272                       ? gimple_call_fndecl (stmt)
 273                       : NULL;
 274           if (decl)
 275             {
 276               int flags = gimple_call_flags (stmt);
 277               if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
 278                 {
 279                   if (gimple_purge_dead_abnormal_call_edges (bb))
 280                     todo |= TODO_cleanup_cfg;
 281
 282                   if (gimple_in_ssa_p (cfun))
 283                     {
 284                       todo |= TODO_update_ssa | TODO_cleanup_cfg;
 285                       update_stmt (stmt);
 286                     }
 287                 }
 288
 289               if (flags & ECF_NORETURN
 290                   && fixup_noreturn_call (stmt))
 291                 todo |= TODO_cleanup_cfg;
 292              }
 293
 294           if (maybe_clean_eh_stmt (stmt)
 295               && gimple_purge_dead_eh_edges (bb))
 296             todo |= TODO_cleanup_cfg;
 297         }
 298
 299       FOR_EACH_EDGE (e, ei, bb->succs)
 300         e->count = (e->count * count_scale
 301                     + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 302     }
 303   if (count_scale != REG_BR_PROB_BASE)
 304     compute_function_frequency ();
 305
 306   /* We just processed all calls.  */
 307   if (cfun->gimple_df)
 308     {
 309       VEC_free (gimple, gc, MODIFIED_NORETURN_CALLS (cfun));
 310       MODIFIED_NORETURN_CALLS (cfun) = NULL;
 311     }
 312
 313   /* Dump a textual representation of the flowgraph.  */
 314   if (dump_file)
 315     gimple_dump_cfg (dump_file, dump_flags);
 316
 317   return todo;
 318 }
 319
 320 struct gimple_opt_pass pass_fixup_cfg =
 321 {
 322  {
 323   GIMPLE_PASS,
 324   "*free_cfg_annotations",              /* name */
 325   NULL,                                 /* gate */
 326   execute_fixup_cfg,                    /* execute */
 327   NULL,                                 /* sub */
 328   NULL,                                 /* next */
 329   0,                                    /* static_pass_number */
 330   TV_NONE,                              /* tv_id */
 331   PROP_cfg,                             /* properties_required */
 332   0,                                    /* properties_provided */
 333   0,                                    /* properties_destroyed */
 334   0,                                    /* todo_flags_start */
 335   0                                     /* todo_flags_finish */
 336  }
 337 };
 338
 339 /* Do the actions required to initialize internal data structures used
 340    in tree-ssa optimization passes.  */
 341
 342 static unsigned int
 343 execute_init_datastructures (void)
 344 {
 345   /* Allocate hash tables, arrays and other structures.  */
 346   init_tree_ssa (cfun);
 347   return 0;
 348 }
 349
 350 struct gimple_opt_pass pass_init_datastructures =
 351 {
 352  {
 353   GIMPLE_PASS,
 354   "*init_datastructures",               /* name */
 355   NULL,                                 /* gate */
 356   execute_init_datastructures,          /* execute */
 357   NULL,                                 /* sub */
 358   NULL,                                 /* next */
 359   0,                                    /* static_pass_number */
 360   TV_NONE,                              /* tv_id */
 361   PROP_cfg,                             /* properties_required */
 362   0,                                    /* properties_provided */
 363   0,                                    /* properties_destroyed */
 364   0,                                    /* todo_flags_start */
 365   0                                     /* todo_flags_finish */
 366  }
 367 };
 368
 369 void
 370 tree_lowering_passes (tree fn)
 371 {
 372   tree saved_current_function_decl = current_function_decl;
 373
 374   current_function_decl = fn;
 375   push_cfun (DECL_STRUCT_FUNCTION (fn));
 376   gimple_register_cfg_hooks ();
 377   bitmap_obstack_initialize (NULL);
 378   execute_pass_list (all_lowering_passes);
 379   if (optimize && cgraph_global_info_ready)
 380     execute_pass_list (pass_early_local_passes.pass.sub);
 381   free_dominance_info (CDI_POST_DOMINATORS);
 382   free_dominance_info (CDI_DOMINATORS);
 383   compact_blocks ();
 384   current_function_decl = saved_current_function_decl;
 385   bitmap_obstack_release (NULL);
 386   pop_cfun ();
 387 }
 388 \f
 389 /* For functions-as-trees languages, this performs all optimization and
 390    compilation for FNDECL.  */
 391
 392 void
 393 tree_rest_of_compilation (tree fndecl)
 394 {
 395   location_t saved_loc;
 396
 397   timevar_push (TV_REST_OF_COMPILATION);
 398
 399   gcc_assert (cgraph_global_info_ready);
 400
 401   /* Initialize the default bitmap obstack.  */
 402   bitmap_obstack_initialize (NULL);
 403
 404   /* Initialize the RTL code for the function.  */
 405   current_function_decl = fndecl;
 406   saved_loc = input_location;
 407   input_location = DECL_SOURCE_LOCATION (fndecl);
 408   init_function_start (fndecl);
 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_, "size of return value of %q+D is %u bytes",
 450                      fndecl, size_as_int);
 451           else
 452             warning (OPT_Wlarger_than_, "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_get_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_REST_OF_COMPILATION);
 474 }