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_remove_unused_locals             /* todo_flags_finish */
 212  }
 213 };
 214
 215 /* Pass: do the actions required to finish with tree-ssa optimization
 216    passes.  */
 217
 218 unsigned int
 219 execute_free_datastructures (void)
 220 {
 221   free_dominance_info (CDI_DOMINATORS);
 222   free_dominance_info (CDI_POST_DOMINATORS);
 223
 224   /* And get rid of annotations we no longer need.  */
 225   delete_tree_cfg_annotations ();
 226
 227   return 0;
 228 }
 229
 230 /* IPA passes, compilation of earlier functions or inlining
 231    might have changed some properties, such as marked functions nothrow,
 232    pure, const or noreturn.
 233    Remove redundant edges and basic blocks, and create new ones if necessary.
 234
 235    This pass can't be executed as stand alone pass from pass manager, because
 236    in between inlining and this fixup the verify_flow_info would fail.  */
 237
 238 unsigned int
 239 execute_fixup_cfg (void)
 240 {
 241   basic_block bb;
 242   gimple_stmt_iterator gsi;
 243   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 244   gcov_type count_scale;
 245   edge e;
 246   edge_iterator ei;
 247
 248   if (ENTRY_BLOCK_PTR->count)
 249     count_scale = ((cgraph_get_node (current_function_decl)->count
 250                     * REG_BR_PROB_BASE + ENTRY_BLOCK_PTR->count / 2)
 251                    / ENTRY_BLOCK_PTR->count);
 252   else
 253     count_scale = REG_BR_PROB_BASE;
 254
 255   ENTRY_BLOCK_PTR->count = cgraph_get_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_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 260     e->count = (e->count * count_scale
 261        + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 262
 263   FOR_EACH_BB (bb)
 264     {
 265       bb->count = (bb->count * count_scale
 266                    + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 267       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 268         {
 269           gimple stmt = gsi_stmt (gsi);
 270           tree decl = is_gimple_call (stmt)
 271                       ? gimple_call_fndecl (stmt)
 272                       : NULL;
 273           if (decl)
 274             {
 275               int flags = gimple_call_flags (stmt);
 276               if (flags & (ECF_CONST | ECF_PURE | ECF_LOOPING_CONST_OR_PURE))
 277                 {
 278                   if (gimple_purge_dead_abnormal_call_edges (bb))
 279                     todo |= TODO_cleanup_cfg;
 280
 281                   if (gimple_in_ssa_p (cfun))
 282                     {
 283                       todo |= TODO_update_ssa | TODO_cleanup_cfg;
 284                       update_stmt (stmt);
 285                     }
 286                 }
 287
 288               if (flags & ECF_NORETURN
 289                   && fixup_noreturn_call (stmt))
 290                 todo |= TODO_cleanup_cfg;
 291              }
 292
 293           if (maybe_clean_eh_stmt (stmt)
 294               && gimple_purge_dead_eh_edges (bb))
 295             todo |= TODO_cleanup_cfg;
 296         }
 297
 298       FOR_EACH_EDGE (e, ei, bb->succs)
 299         e->count = (e->count * count_scale
 300                     + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
 301     }
 302   if (count_scale != REG_BR_PROB_BASE)
 303     compute_function_frequency ();
 304
 305   /* We just processed all calls.  */
 306   if (cfun->gimple_df)
 307     {
 308       VEC_free (gimple, gc, MODIFIED_NORETURN_CALLS (cfun));
 309       MODIFIED_NORETURN_CALLS (cfun) = NULL;
 310     }
 311
 312   /* Dump a textual representation of the flowgraph.  */
 313   if (dump_file)
 314     gimple_dump_cfg (dump_file, dump_flags);
 315
 316   return todo;
 317 }
 318
 319 struct gimple_opt_pass pass_fixup_cfg =
 320 {
 321  {
 322   GIMPLE_PASS,
 323   "*free_cfg_annotations",              /* name */
 324   NULL,                                 /* gate */
 325   execute_fixup_cfg,                    /* execute */
 326   NULL,                                 /* sub */
 327   NULL,                                 /* next */
 328   0,                                    /* static_pass_number */
 329   TV_NONE,                              /* tv_id */
 330   PROP_cfg,                             /* properties_required */
 331   0,                                    /* properties_provided */
 332   0,                                    /* properties_destroyed */
 333   0,                                    /* todo_flags_start */
 334   0                                     /* todo_flags_finish */
 335  }
 336 };
 337
 338 /* Do the actions required to initialize internal data structures used
 339    in tree-ssa optimization passes.  */
 340
 341 static unsigned int
 342 execute_init_datastructures (void)
 343 {
 344   /* Allocate hash tables, arrays and other structures.  */
 345   init_tree_ssa (cfun);
 346   return 0;
 347 }
 348
 349 struct gimple_opt_pass pass_init_datastructures =
 350 {
 351  {
 352   GIMPLE_PASS,
 353   "*init_datastructures",               /* name */
 354   NULL,                                 /* gate */
 355   execute_init_datastructures,          /* execute */
 356   NULL,                                 /* sub */
 357   NULL,                                 /* next */
 358   0,                                    /* static_pass_number */
 359   TV_NONE,                              /* tv_id */
 360   PROP_cfg,                             /* properties_required */
 361   0,                                    /* properties_provided */
 362   0,                                    /* properties_destroyed */
 363   0,                                    /* todo_flags_start */
 364   0                                     /* todo_flags_finish */
 365  }
 366 };
 367
 368 void
 369 tree_lowering_passes (tree fn)
 370 {
 371   tree saved_current_function_decl = current_function_decl;
 372
 373   current_function_decl = fn;
 374   push_cfun (DECL_STRUCT_FUNCTION (fn));
 375   gimple_register_cfg_hooks ();
 376   bitmap_obstack_initialize (NULL);
 377   execute_pass_list (all_lowering_passes);
 378   if (optimize && cgraph_global_info_ready)
 379     execute_pass_list (pass_early_local_passes.pass.sub);
 380   free_dominance_info (CDI_POST_DOMINATORS);
 381   free_dominance_info (CDI_DOMINATORS);
 382   compact_blocks ();
 383   current_function_decl = saved_current_function_decl;
 384   bitmap_obstack_release (NULL);
 385   pop_cfun ();
 386 }
 387 \f
 388 /* For functions-as-trees languages, this performs all optimization and
 389    compilation for FNDECL.  */
 390
 391 void
 392 tree_rest_of_compilation (tree fndecl)
 393 {
 394   location_t saved_loc;
 395
 396   timevar_push (TV_REST_OF_COMPILATION);
 397
 398   gcc_assert (cgraph_global_info_ready);
 399
 400   /* Initialize the default bitmap obstack.  */
 401   bitmap_obstack_initialize (NULL);
 402
 403   /* Initialize the RTL code for the function.  */
 404   current_function_decl = fndecl;
 405   saved_loc = input_location;
 406   input_location = DECL_SOURCE_LOCATION (fndecl);
 407   init_function_start (fndecl);
 408
 409   gimple_register_cfg_hooks ();
 410
 411   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 412
 413   execute_all_ipa_transforms ();
 414
 415   /* Perform all tree transforms and optimizations.  */
 416
 417   /* Signal the start of passes.  */
 418   invoke_plugin_callbacks (PLUGIN_ALL_PASSES_START, NULL);
 419
 420   execute_pass_list (all_passes);
 421
 422   /* Signal the end of passes.  */
 423   invoke_plugin_callbacks (PLUGIN_ALL_PASSES_END, NULL);
 424
 425   bitmap_obstack_release (&reg_obstack);
 426
 427   /* Release the default bitmap obstack.  */
 428   bitmap_obstack_release (NULL);
 429
 430   set_cfun (NULL);
 431
 432   /* If requested, warn about function definitions where the function will
 433      return a value (usually of some struct or union type) which itself will
 434      take up a lot of stack space.  */
 435   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 436     {
 437       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 438
 439       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 440           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 441           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 442                                    larger_than_size))
 443         {
 444           unsigned int size_as_int
 445             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 446
 447           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 448             warning (OPT_Wlarger_than_, "size of return value of %q+D is %u bytes",
 449                      fndecl, size_as_int);
 450           else
 451             warning (OPT_Wlarger_than_, "size of return value of %q+D is larger than %wd bytes",
 452                      fndecl, larger_than_size);
 453         }
 454     }
 455
 456   gimple_set_body (fndecl, NULL);
 457   if (DECL_STRUCT_FUNCTION (fndecl) == 0
 458       && !cgraph_get_node (fndecl)->origin)
 459     {
 460       /* Stop pointing to the local nodes about to be freed.
 461          But DECL_INITIAL must remain nonzero so we know this
 462          was an actual function definition.
 463          For a nested function, this is done in c_pop_function_context.
 464          If rest_of_compilation set this to 0, leave it 0.  */
 465       if (DECL_INITIAL (fndecl) != 0)
 466         DECL_INITIAL (fndecl) = error_mark_node;
 467     }
 468
 469   input_location = saved_loc;
 470
 471   ggc_collect ();
 472   timevar_pop (TV_REST_OF_COMPILATION);
 473 }