gcc/tree-optimize.c

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