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