gcc/tree-optimize.c

   1 /* Top-level control of tree optimizations.
   2    Copyright 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "expr.h"
  32 #include "diagnostic.h"
  33 #include "basic-block.h"
  34 #include "flags.h"
  35 #include "tree-flow.h"
  36 #include "tree-dump.h"
  37 #include "timevar.h"
  38 #include "function.h"
  39 #include "langhooks.h"
  40 #include "toplev.h"
  41 #include "flags.h"
  42 #include "cgraph.h"
  43 #include "tree-inline.h"
  44 #include "tree-mudflap.h"
  45 #include "tree-pass.h"
  46 #include "ggc.h"
  47 #include "cgraph.h"
  48 #include "graph.h"
  49 #include "cfgloop.h"
  50 #include "except.h"
  51
  52
  53 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  54
  55 static bool
  56 gate_all_optimizations (void)
  57 {
  58   return (optimize >= 1
  59           /* Don't bother doing anything if the program has errors.
  60              We have to pass down the queue if we already went into SSA */
  61           && (!(errorcount || sorrycount) || gimple_in_ssa_p (cfun)));
  62 }
  63
  64 struct gimple_opt_pass pass_all_optimizations =
  65 {
  66  {
  67   GIMPLE_PASS,
  68   NULL,                                 /* name */
  69   gate_all_optimizations,               /* gate */
  70   NULL,                                 /* execute */
  71   NULL,                                 /* sub */
  72   NULL,                                 /* next */
  73   0,                                    /* static_pass_number */
  74   0,                                    /* tv_id */
  75   0,                                    /* properties_required */
  76   0,                                    /* properties_provided */
  77   0,                                    /* properties_destroyed */
  78   0,                                    /* todo_flags_start */
  79   0                                     /* todo_flags_finish */
  80  }
  81 };
  82
  83 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  84
  85 static bool
  86 gate_all_early_local_passes (void)
  87 {
  88           /* Don't bother doing anything if the program has errors.  */
  89   return (!errorcount && !sorrycount);
  90 }
  91
  92 struct simple_ipa_opt_pass pass_early_local_passes =
  93 {
  94  {
  95   SIMPLE_IPA_PASS,
  96   "early_local_cleanups",               /* name */
  97   gate_all_early_local_passes,          /* gate */
  98   NULL,                                 /* execute */
  99   NULL,                                 /* sub */
 100   NULL,                                 /* next */
 101   0,                                    /* static_pass_number */
 102   0,                                    /* tv_id */
 103   0,                                    /* properties_required */
 104   0,                                    /* properties_provided */
 105   0,                                    /* properties_destroyed */
 106   0,                                    /* todo_flags_start */
 107   TODO_remove_functions                 /* todo_flags_finish */
 108  }
 109 };
 110
 111 static unsigned int
 112 execute_early_local_optimizations (void)
 113 {
 114   /* First time we start with early optimization we need to advance
 115      cgraph state so newly inserted functions are also early optimized.
 116      However we execute early local optimizations for lately inserted
 117      functions, in that case don't reset cgraph state back to IPA_SSA.  */
 118   if (flag_unit_at_a_time && cgraph_state < CGRAPH_STATE_IPA_SSA)
 119     cgraph_state = CGRAPH_STATE_IPA_SSA;
 120   return 0;
 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           && !(errorcount || sorrycount));
 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   execute_early_local_optimizations,    /* execute */
 140   NULL,                                 /* sub */
 141   NULL,                                 /* next */
 142   0,                                    /* static_pass_number */
 143   0,                                    /* 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 /* 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_pre_ipa (void)
 159 {
 160   cleanup_tree_cfg ();
 161   return 0;
 162 }
 163
 164 struct gimple_opt_pass pass_cleanup_cfg =
 165 {
 166  {
 167   GIMPLE_PASS,
 168   "cleanup_cfg",                        /* name */
 169   NULL,                                 /* gate */
 170   execute_cleanup_cfg_pre_ipa,          /* execute */
 171   NULL,                                 /* sub */
 172   NULL,                                 /* next */
 173   0,                                    /* static_pass_number */
 174   0,                                    /* tv_id */
 175   PROP_cfg,                             /* properties_required */
 176   0,                                    /* properties_provided */
 177   0,                                    /* properties_destroyed */
 178   0,                                    /* todo_flags_start */
 179   TODO_dump_func                        /* todo_flags_finish */
 180  }
 181 };
 182
 183
 184 /* Pass: cleanup the CFG just before expanding trees to RTL.
 185    This is just a round of label cleanups and case node grouping
 186    because after the tree optimizers have run such cleanups may
 187    be necessary.  */
 188
 189 static unsigned int
 190 execute_cleanup_cfg_post_optimizing (void)
 191 {
 192   fold_cond_expr_cond ();
 193   cleanup_tree_cfg ();
 194   cleanup_dead_labels ();
 195   group_case_labels ();
 196   return 0;
 197 }
 198
 199 struct gimple_opt_pass pass_cleanup_cfg_post_optimizing =
 200 {
 201  {
 202   GIMPLE_PASS,
 203   "final_cleanup",                      /* name */
 204   NULL,                                 /* gate */
 205   execute_cleanup_cfg_post_optimizing,  /* execute */
 206   NULL,                                 /* sub */
 207   NULL,                                 /* next */
 208   0,                                    /* static_pass_number */
 209   0,                                    /* tv_id */
 210   PROP_cfg,                             /* properties_required */
 211   0,                                    /* properties_provided */
 212   0,                                    /* properties_destroyed */
 213   0,                                    /* todo_flags_start */
 214   TODO_dump_func                        /* todo_flags_finish */
 215  }
 216 };
 217
 218 /* Pass: do the actions required to finish with tree-ssa optimization
 219    passes.  */
 220
 221 static unsigned int
 222 execute_free_datastructures (void)
 223 {
 224   free_dominance_info (CDI_DOMINATORS);
 225   free_dominance_info (CDI_POST_DOMINATORS);
 226
 227   /* Remove the ssa structures.  */
 228   if (cfun->gimple_df)
 229     delete_tree_ssa ();
 230   return 0;
 231 }
 232
 233 struct gimple_opt_pass pass_free_datastructures =
 234 {
 235  {
 236   GIMPLE_PASS,
 237   NULL,                                 /* name */
 238   NULL,                                 /* gate */
 239   execute_free_datastructures,                  /* execute */
 240   NULL,                                 /* sub */
 241   NULL,                                 /* next */
 242   0,                                    /* static_pass_number */
 243   0,                                    /* tv_id */
 244   PROP_cfg,                             /* properties_required */
 245   0,                                    /* properties_provided */
 246   0,                                    /* properties_destroyed */
 247   0,                                    /* todo_flags_start */
 248   0                                     /* todo_flags_finish */
 249  }
 250 };
 251 /* Pass: free cfg annotations.  */
 252
 253 static unsigned int
 254 execute_free_cfg_annotations (void)
 255 {
 256   /* And get rid of annotations we no longer need.  */
 257   delete_tree_cfg_annotations ();
 258
 259   return 0;
 260 }
 261
 262 struct gimple_opt_pass pass_free_cfg_annotations =
 263 {
 264  {
 265   GIMPLE_PASS,
 266   NULL,                                 /* name */
 267   NULL,                                 /* gate */
 268   execute_free_cfg_annotations,         /* execute */
 269   NULL,                                 /* sub */
 270   NULL,                                 /* next */
 271   0,                                    /* static_pass_number */
 272   0,                                    /* tv_id */
 273   PROP_cfg,                             /* properties_required */
 274   0,                                    /* properties_provided */
 275   0,                                    /* properties_destroyed */
 276   0,                                    /* todo_flags_start */
 277   0                                     /* todo_flags_finish */
 278  }
 279 };
 280
 281 /* Pass: fixup_cfg.  IPA passes, compilation of earlier functions or inlining
 282    might have changed some properties, such as marked functions nothrow.
 283    Remove redundant edges and basic blocks, and create new ones if necessary.
 284
 285    This pass can't be executed as stand alone pass from pass manager, because
 286    in between inlining and this fixup the verify_flow_info would fail.  */
 287
 288 unsigned int
 289 execute_fixup_cfg (void)
 290 {
 291   basic_block bb;
 292   block_stmt_iterator bsi;
 293   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 294
 295   cfun->after_inlining = true;
 296
 297   if (cfun->eh)
 298     FOR_EACH_BB (bb)
 299       {
 300         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 301           {
 302             tree stmt = bsi_stmt (bsi);
 303             tree call = get_call_expr_in (stmt);
 304             tree decl = call ? get_callee_fndecl (call) : NULL;
 305
 306             if (decl && call_expr_flags (call) & (ECF_CONST | ECF_PURE
 307                                                   | ECF_LOOPING_CONST_OR_PURE)
 308                 && TREE_SIDE_EFFECTS (call))
 309               {
 310                 if (gimple_in_ssa_p (cfun))
 311                   {
 312                     todo |= TODO_update_ssa | TODO_cleanup_cfg;
 313                     update_stmt (stmt);
 314                   }
 315                 TREE_SIDE_EFFECTS (call) = 0;
 316               }
 317             if (decl && TREE_NOTHROW (decl))
 318               TREE_NOTHROW (call) = 1;
 319             if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 320               remove_stmt_from_eh_region (stmt);
 321           }
 322         if (tree_purge_dead_eh_edges (bb))
 323           todo |= TODO_cleanup_cfg;
 324       }
 325
 326   /* Dump a textual representation of the flowgraph.  */
 327   if (dump_file)
 328     dump_tree_cfg (dump_file, dump_flags);
 329
 330   return todo;
 331 }
 332
 333 /* Do the actions required to initialize internal data structures used
 334    in tree-ssa optimization passes.  */
 335
 336 static unsigned int
 337 execute_init_datastructures (void)
 338 {
 339   /* Allocate hash tables, arrays and other structures.  */
 340   init_tree_ssa (cfun);
 341   return 0;
 342 }
 343
 344 /* Gate: initialize or not the SSA datastructures.  */
 345
 346 static bool
 347 gate_init_datastructures (void)
 348 {
 349   return (optimize >= 1);
 350 }
 351
 352 struct gimple_opt_pass pass_init_datastructures =
 353 {
 354  {
 355   GIMPLE_PASS,
 356   NULL,                                 /* name */
 357   gate_init_datastructures,             /* gate */
 358   execute_init_datastructures,          /* execute */
 359   NULL,                                 /* sub */
 360   NULL,                                 /* next */
 361   0,                                    /* static_pass_number */
 362   0,                                    /* tv_id */
 363   PROP_cfg,                             /* properties_required */
 364   0,                                    /* properties_provided */
 365   0,                                    /* properties_destroyed */
 366   0,                                    /* todo_flags_start */
 367   0                                     /* todo_flags_finish */
 368  }
 369 };
 370
 371 void
 372 tree_lowering_passes (tree fn)
 373 {
 374   tree saved_current_function_decl = current_function_decl;
 375
 376   current_function_decl = fn;
 377   push_cfun (DECL_STRUCT_FUNCTION (fn));
 378   tree_register_cfg_hooks ();
 379   bitmap_obstack_initialize (NULL);
 380   execute_pass_list (all_lowering_passes);
 381   if (optimize && cgraph_global_info_ready)
 382     execute_pass_list (pass_early_local_passes.pass.sub);
 383   free_dominance_info (CDI_POST_DOMINATORS);
 384   free_dominance_info (CDI_DOMINATORS);
 385   compact_blocks ();
 386   current_function_decl = saved_current_function_decl;
 387   bitmap_obstack_release (NULL);
 388   pop_cfun ();
 389 }
 390 \f
 391 /* For functions-as-trees languages, this performs all optimization and
 392    compilation for FNDECL.  */
 393
 394 void
 395 tree_rest_of_compilation (tree fndecl)
 396 {
 397   location_t saved_loc;
 398   struct cgraph_node *node;
 399
 400   timevar_push (TV_EXPAND);
 401
 402   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 403
 404   node = cgraph_node (fndecl);
 405
 406   /* Initialize the default bitmap obstack.  */
 407   bitmap_obstack_initialize (NULL);
 408
 409   /* Initialize the RTL code for the function.  */
 410   current_function_decl = fndecl;
 411   saved_loc = input_location;
 412   input_location = DECL_SOURCE_LOCATION (fndecl);
 413   init_function_start (fndecl);
 414
 415   /* Even though we're inside a function body, we still don't want to
 416      call expand_expr to calculate the size of a variable-sized array.
 417      We haven't necessarily assigned RTL to all variables yet, so it's
 418      not safe to try to expand expressions involving them.  */
 419   cfun->dont_save_pending_sizes_p = 1;
 420
 421   tree_register_cfg_hooks ();
 422
 423   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 424   /* Perform all tree transforms and optimizations.  */
 425   execute_pass_list (all_passes);
 426
 427   bitmap_obstack_release (&reg_obstack);
 428
 429   /* Release the default bitmap obstack.  */
 430   bitmap_obstack_release (NULL);
 431
 432   DECL_SAVED_TREE (fndecl) = NULL;
 433   set_cfun (NULL);
 434
 435   /* If requested, warn about function definitions where the function will
 436      return a value (usually of some struct or union type) which itself will
 437      take up a lot of stack space.  */
 438   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 439     {
 440       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 441
 442       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 443           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 444           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 445                                    larger_than_size))
 446         {
 447           unsigned int size_as_int
 448             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 449
 450           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 451             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is %u bytes",
 452                      fndecl, size_as_int);
 453           else
 454             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is larger than %wd bytes",
 455                      fndecl, larger_than_size);
 456         }
 457     }
 458
 459   if (!flag_inline_trees)
 460     {
 461       DECL_SAVED_TREE (fndecl) = NULL;
 462       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 463           && !cgraph_node (fndecl)->origin)
 464         {
 465           /* Stop pointing to the local nodes about to be freed.
 466              But DECL_INITIAL must remain nonzero so we know this
 467              was an actual function definition.
 468              For a nested function, this is done in c_pop_function_context.
 469              If rest_of_compilation set this to 0, leave it 0.  */
 470           if (DECL_INITIAL (fndecl) != 0)
 471             DECL_INITIAL (fndecl) = error_mark_node;
 472         }
 473     }
 474
 475   input_location = saved_loc;
 476
 477   ggc_collect ();
 478   timevar_pop (TV_EXPAND);
 479 }