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