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 (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   gimple_stmt_iterator gsi;
 293   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 294
 295   cfun->after_inlining = true;
 296   cfun->always_inline_functions_inlined = true;
 297
 298   if (cfun->eh)
 299     FOR_EACH_BB (bb)
 300       {
 301         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 302           {
 303             gimple stmt = gsi_stmt (gsi);
 304             tree decl = is_gimple_call (stmt)
 305                         ? gimple_call_fndecl (stmt)
 306                         : NULL;
 307
 308             if (decl
 309                 && gimple_call_flags (stmt) & (ECF_CONST
 310                                                | ECF_PURE
 311                                                | ECF_LOOPING_CONST_OR_PURE))
 312               {
 313                 if (gimple_in_ssa_p (cfun))
 314                   {
 315                     todo |= TODO_update_ssa | TODO_cleanup_cfg;
 316                     update_stmt (stmt);
 317                   }
 318               }
 319
 320             if (!stmt_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 321               remove_stmt_from_eh_region (stmt);
 322           }
 323
 324         if (gimple_purge_dead_eh_edges (bb))
 325           todo |= TODO_cleanup_cfg;
 326       }
 327
 328   /* Dump a textual representation of the flowgraph.  */
 329   if (dump_file)
 330     gimple_dump_cfg (dump_file, dump_flags);
 331
 332   return todo;
 333 }
 334
 335 /* Do the actions required to initialize internal data structures used
 336    in tree-ssa optimization passes.  */
 337
 338 static unsigned int
 339 execute_init_datastructures (void)
 340 {
 341   /* Allocate hash tables, arrays and other structures.  */
 342   init_tree_ssa (cfun);
 343   return 0;
 344 }
 345
 346 struct gimple_opt_pass pass_init_datastructures =
 347 {
 348  {
 349   GIMPLE_PASS,
 350   NULL,                                 /* name */
 351   NULL,                                 /* gate */
 352   execute_init_datastructures,          /* execute */
 353   NULL,                                 /* sub */
 354   NULL,                                 /* next */
 355   0,                                    /* static_pass_number */
 356   0,                                    /* tv_id */
 357   PROP_cfg,                             /* properties_required */
 358   0,                                    /* properties_provided */
 359   0,                                    /* properties_destroyed */
 360   0,                                    /* todo_flags_start */
 361   0                                     /* todo_flags_finish */
 362  }
 363 };
 364
 365 void
 366 tree_lowering_passes (tree fn)
 367 {
 368   tree saved_current_function_decl = current_function_decl;
 369
 370   current_function_decl = fn;
 371   push_cfun (DECL_STRUCT_FUNCTION (fn));
 372   gimple_register_cfg_hooks ();
 373   bitmap_obstack_initialize (NULL);
 374   execute_pass_list (all_lowering_passes);
 375   if (optimize && cgraph_global_info_ready)
 376     execute_pass_list (pass_early_local_passes.pass.sub);
 377   free_dominance_info (CDI_POST_DOMINATORS);
 378   free_dominance_info (CDI_DOMINATORS);
 379   compact_blocks ();
 380   current_function_decl = saved_current_function_decl;
 381   bitmap_obstack_release (NULL);
 382   pop_cfun ();
 383 }
 384 \f
 385 /* For functions-as-trees languages, this performs all optimization and
 386    compilation for FNDECL.  */
 387
 388 void
 389 tree_rest_of_compilation (tree fndecl)
 390 {
 391   location_t saved_loc;
 392   struct cgraph_node *node;
 393
 394   timevar_push (TV_EXPAND);
 395
 396   gcc_assert (cgraph_global_info_ready);
 397
 398   node = cgraph_node (fndecl);
 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   /* Even though we're inside a function body, we still don't want to
 410      call expand_expr to calculate the size of a variable-sized array.
 411      We haven't necessarily assigned RTL to all variables yet, so it's
 412      not safe to try to expand expressions involving them.  */
 413   cfun->dont_save_pending_sizes_p = 1;
 414
 415   gimple_register_cfg_hooks ();
 416
 417   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 418   /* Perform all tree transforms and optimizations.  */
 419   execute_pass_list (all_passes);
 420
 421   bitmap_obstack_release (&reg_obstack);
 422
 423   /* Release the default bitmap obstack.  */
 424   bitmap_obstack_release (NULL);
 425
 426   set_cfun (NULL);
 427
 428   /* If requested, warn about function definitions where the function will
 429      return a value (usually of some struct or union type) which itself will
 430      take up a lot of stack space.  */
 431   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 432     {
 433       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 434
 435       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 436           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 437           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 438                                    larger_than_size))
 439         {
 440           unsigned int size_as_int
 441             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 442
 443           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 444             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is %u bytes",
 445                      fndecl, size_as_int);
 446           else
 447             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is larger than %wd bytes",
 448                      fndecl, larger_than_size);
 449         }
 450     }
 451
 452   gimple_set_body (fndecl, NULL);
 453   if (DECL_STRUCT_FUNCTION (fndecl) == 0
 454       && !cgraph_node (fndecl)->origin)
 455     {
 456       /* Stop pointing to the local nodes about to be freed.
 457          But DECL_INITIAL must remain nonzero so we know this
 458          was an actual function definition.
 459          For a nested function, this is done in c_pop_function_context.
 460          If rest_of_compilation set this to 0, leave it 0.  */
 461       if (DECL_INITIAL (fndecl) != 0)
 462         DECL_INITIAL (fndecl) = error_mark_node;
 463     }
 464
 465   input_location = saved_loc;
 466
 467   ggc_collect ();
 468   timevar_pop (TV_EXPAND);
 469 }