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   cleanup_dead_labels ();
 163   group_case_labels ();
 164   if ((flag_compare_debug_opt || flag_compare_debug)
 165       && flag_dump_final_insns)
 166     {
 167       FILE *final_output = fopen (flag_dump_final_insns, "a");
 168
 169       if (!final_output)
 170         {
 171           error ("could not open final insn dump file %qs: %m",
 172                  flag_dump_final_insns);
 173           flag_dump_final_insns = NULL;
 174         }
 175       else
 176         {
 177           int save_unnumbered = flag_dump_unnumbered;
 178           int save_noaddr = flag_dump_noaddr;
 179
 180           flag_dump_noaddr = flag_dump_unnumbered = 1;
 181           fprintf (final_output, "\n");
 182           dump_enumerated_decls (final_output, dump_flags | TDF_NOUID);
 183           flag_dump_noaddr = save_noaddr;
 184           flag_dump_unnumbered = save_unnumbered;
 185           if (fclose (final_output))
 186             {
 187               error ("could not close final insn dump file %qs: %m",
 188                      flag_dump_final_insns);
 189               flag_dump_final_insns = NULL;
 190             }
 191         }
 192     }
 193   return 0;
 194 }
 195
 196 struct gimple_opt_pass pass_cleanup_cfg_post_optimizing =
 197 {
 198  {
 199   GIMPLE_PASS,
 200   "optimized",                          /* name */
 201   NULL,                                 /* gate */
 202   execute_cleanup_cfg_post_optimizing,  /* execute */
 203   NULL,                                 /* sub */
 204   NULL,                                 /* next */
 205   0,                                    /* static_pass_number */
 206   TV_TREE_CLEANUP_CFG,                  /* tv_id */
 207   PROP_cfg,                             /* properties_required */
 208   0,                                    /* properties_provided */
 209   0,                                    /* properties_destroyed */
 210   0,                                    /* todo_flags_start */
 211   TODO_dump_func                        /* todo_flags_finish */
 212     | TODO_remove_unused_locals
 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_node (current_function_decl)->count * REG_BR_PROB_BASE
 251                    + ENTRY_BLOCK_PTR->count / 2) / ENTRY_BLOCK_PTR->count;
 252   else
 253     count_scale = REG_BR_PROB_BASE;
 254
 255   ENTRY_BLOCK_PTR->count = cgraph_node (current_function_decl)->count;
 256   EXIT_BLOCK_PTR->count = (EXIT_BLOCK_PTR->count * count_scale
 257                            + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 258
 259   FOR_EACH_BB (bb)
 260     {
 261       bb->count = (bb->count * count_scale
 262                    + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 263       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 264         {
 265           gimple stmt = gsi_stmt (gsi);
 266           tree decl = is_gimple_call (stmt)
 267                       ? gimple_call_fndecl (stmt)
 268                       : NULL;
 269           if (decl)
 270             {
 271               int flags = gimple_call_flags (stmt);
 272               if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
 273                 {
 274                   if (gimple_purge_dead_abnormal_call_edges (bb))
 275                     todo |= TODO_cleanup_cfg;
 276
 277                   if (gimple_in_ssa_p (cfun))
 278                     {
 279                       todo |= TODO_update_ssa | TODO_cleanup_cfg;
 280                       update_stmt (stmt);
 281                     }
 282                 }
 283
 284               if (flags & ECF_NORETURN
 285                   && fixup_noreturn_call (stmt))
 286                 todo |= TODO_cleanup_cfg;
 287              }
 288
 289           if (maybe_clean_eh_stmt (stmt)
 290               && gimple_purge_dead_eh_edges (bb))
 291             todo |= TODO_cleanup_cfg;
 292         }
 293
 294       FOR_EACH_EDGE (e, ei, bb->succs)
 295         e->count = (e->count * count_scale
 296                     + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 297     }
 298   if (count_scale != REG_BR_PROB_BASE)
 299     compute_function_frequency ();
 300
 301   /* We just processed all calls.  */
 302   if (cfun->gimple_df)
 303     {
 304       VEC_free (gimple, gc, MODIFIED_NORETURN_CALLS (cfun));
 305       MODIFIED_NORETURN_CALLS (cfun) = NULL;
 306     }
 307
 308   /* Dump a textual representation of the flowgraph.  */
 309   if (dump_file)
 310     gimple_dump_cfg (dump_file, dump_flags);
 311
 312   return todo;
 313 }
 314
 315 struct gimple_opt_pass pass_fixup_cfg =
 316 {
 317  {
 318   GIMPLE_PASS,
 319   "*free_cfg_annotations",              /* name */
 320   NULL,                                 /* gate */
 321   execute_fixup_cfg,                    /* execute */
 322   NULL,                                 /* sub */
 323   NULL,                                 /* next */
 324   0,                                    /* static_pass_number */
 325   TV_NONE,                              /* tv_id */
 326   PROP_cfg,                             /* properties_required */
 327   0,                                    /* properties_provided */
 328   0,                                    /* properties_destroyed */
 329   0,                                    /* todo_flags_start */
 330   0                                     /* todo_flags_finish */
 331  }
 332 };
 333
 334 /* Do the actions required to initialize internal data structures used
 335    in tree-ssa optimization passes.  */
 336
 337 static unsigned int
 338 execute_init_datastructures (void)
 339 {
 340   /* Allocate hash tables, arrays and other structures.  */
 341   init_tree_ssa (cfun);
 342   return 0;
 343 }
 344
 345 struct gimple_opt_pass pass_init_datastructures =
 346 {
 347  {
 348   GIMPLE_PASS,
 349   "*init_datastructures",               /* name */
 350   NULL,                                 /* gate */
 351   execute_init_datastructures,          /* 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 void
 365 tree_lowering_passes (tree fn)
 366 {
 367   tree saved_current_function_decl = current_function_decl;
 368
 369   current_function_decl = fn;
 370   push_cfun (DECL_STRUCT_FUNCTION (fn));
 371   gimple_register_cfg_hooks ();
 372   bitmap_obstack_initialize (NULL);
 373   execute_pass_list (all_lowering_passes);
 374   if (optimize && cgraph_global_info_ready)
 375     execute_pass_list (pass_early_local_passes.pass.sub);
 376   free_dominance_info (CDI_POST_DOMINATORS);
 377   free_dominance_info (CDI_DOMINATORS);
 378   compact_blocks ();
 379   current_function_decl = saved_current_function_decl;
 380   bitmap_obstack_release (NULL);
 381   pop_cfun ();
 382 }
 383 \f
 384 /* For functions-as-trees languages, this performs all optimization and
 385    compilation for FNDECL.  */
 386
 387 void
 388 tree_rest_of_compilation (tree fndecl)
 389 {
 390   location_t saved_loc;
 391
 392   timevar_push (TV_REST_OF_COMPILATION);
 393
 394   gcc_assert (cgraph_global_info_ready);
 395
 396   /* Initialize the default bitmap obstack.  */
 397   bitmap_obstack_initialize (NULL);
 398
 399   /* Initialize the RTL code for the function.  */
 400   current_function_decl = fndecl;
 401   saved_loc = input_location;
 402   input_location = DECL_SOURCE_LOCATION (fndecl);
 403   init_function_start (fndecl);
 404
 405   /* Even though we're inside a function body, we still don't want to
 406      call expand_expr to calculate the size of a variable-sized array.
 407      We haven't necessarily assigned RTL to all variables yet, so it's
 408      not safe to try to expand expressions involving them.  */
 409   cfun->dont_save_pending_sizes_p = 1;
 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_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 }