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
  49 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  50
  51 static bool
  52 gate_all_optimizations (void)
  53 {
  54   return (optimize >= 1
  55           /* Don't bother doing anything if the program has errors.
  56              We have to pass down the queue if we already went into SSA */
  57           && (!seen_error () || gimple_in_ssa_p (cfun)));
  58 }
  59
  60 struct gimple_opt_pass pass_all_optimizations =
  61 {
  62  {
  63   GIMPLE_PASS,
  64   "*all_optimizations",                 /* name */
  65   gate_all_optimizations,               /* gate */
  66   NULL,                                 /* execute */
  67   NULL,                                 /* sub */
  68   NULL,                                 /* next */
  69   0,                                    /* static_pass_number */
  70   TV_OPTIMIZE,                          /* tv_id */
  71   0,                                    /* properties_required */
  72   0,                                    /* properties_provided */
  73   0,                                    /* properties_destroyed */
  74   0,                                    /* todo_flags_start */
  75   0                                     /* todo_flags_finish */
  76  }
  77 };
  78
  79 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  80
  81 static bool
  82 gate_all_early_local_passes (void)
  83 {
  84           /* Don't bother doing anything if the program has errors.  */
  85   return (!seen_error () && !in_lto_p);
  86 }
  87
  88 static unsigned int
  89 execute_all_early_local_passes (void)
  90 {
  91   /* Once this pass (and its sub-passes) are complete, all functions
  92      will be in SSA form.  Technically this state change is happening
  93      a tad early, since the sub-passes have not yet run, but since
  94      none of the sub-passes are IPA passes and do not create new
  95      functions, this is ok.  We're setting this value for the benefit
  96      of IPA passes that follow.  */
  97   if (cgraph_state < CGRAPH_STATE_IPA_SSA)
  98     cgraph_state = CGRAPH_STATE_IPA_SSA;
  99   return 0;
 100 }
 101
 102 struct simple_ipa_opt_pass pass_early_local_passes =
 103 {
 104  {
 105   SIMPLE_IPA_PASS,
 106   "early_local_cleanups",               /* name */
 107   gate_all_early_local_passes,          /* gate */
 108   execute_all_early_local_passes,       /* execute */
 109   NULL,                                 /* sub */
 110   NULL,                                 /* next */
 111   0,                                    /* static_pass_number */
 112   TV_EARLY_LOCAL,                       /* tv_id */
 113   0,                                    /* properties_required */
 114   0,                                    /* properties_provided */
 115   0,                                    /* properties_destroyed */
 116   0,                                    /* todo_flags_start */
 117   TODO_remove_functions                 /* todo_flags_finish */
 118  }
 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   NULL,                                 /* 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
 151 /* Pass: cleanup the CFG just before expanding trees to RTL.
 152    This is just a round of label cleanups and case node grouping
 153    because after the tree optimizers have run such cleanups may
 154    be necessary.  */
 155
 156 static unsigned int
 157 execute_cleanup_cfg_post_optimizing (void)
 158 {
 159   unsigned int todo = 0;
 160   if (cleanup_tree_cfg ())
 161     todo |= TODO_update_ssa;
 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 todo;
 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 };