gcc/tree-optimize.c

   1 /* Top-level control of tree optimizations.
   2    Copyright 2001, 2002, 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  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) || in_ssa_p));
  63 }
  64
  65 struct tree_opt_pass pass_all_optimizations =
  66 {
  67   NULL,                                 /* name */
  68   gate_all_optimizations,               /* gate */
  69   NULL,                                 /* execute */
  70   NULL,                                 /* sub */
  71   NULL,                                 /* next */
  72   0,                                    /* static_pass_number */
  73   0,                                    /* tv_id */
  74   0,                                    /* properties_required */
  75   0,                                    /* properties_provided */
  76   0,                                    /* properties_destroyed */
  77   0,                                    /* todo_flags_start */
  78   0,                                    /* todo_flags_finish */
  79   0                                     /* letter */
  80 };
  81
  82 /* Gate: execute, or not, all of the non-trivial optimizations.  */
  83
  84 static bool
  85 gate_all_early_local_passes (void)
  86 {
  87   return (optimize >= 1
  88           /* Don't bother doing anything if the program has errors.  */
  89           && !(errorcount || sorrycount));
  90 }
  91
  92 struct tree_opt_pass pass_early_local_passes =
  93 {
  94   NULL,                                 /* name */
  95   gate_all_early_local_passes,          /* gate */
  96   NULL,                                 /* execute */
  97   NULL,                                 /* sub */
  98   NULL,                                 /* next */
  99   0,                                    /* static_pass_number */
 100   0,                                    /* tv_id */
 101   0,                                    /* properties_required */
 102   0,                                    /* properties_provided */
 103   0,                                    /* properties_destroyed */
 104   0,                                    /* todo_flags_start */
 105   0,                                    /* todo_flags_finish */
 106   0                                     /* letter */
 107 };
 108 /* Gate: execute, or not, all of the non-trivial optimizations.  */
 109
 110 static bool
 111 gate_all_early_optimizations (void)
 112 {
 113   return (optimize >= 1
 114           /* Sort of Hack: In non-unit-at-a-time we need to run the early
 115              optimizations anyway.  The early optimization pass is run once
 116              in IPA queue and once in late local passes.  In unit-at-a-time
 117              the second invocation will get cgraph_global_info_ready.  */
 118           && !cgraph_global_info_ready
 119           /* Don't bother doing anything if the program has errors.  */
 120           && !(errorcount || sorrycount));
 121 }
 122
 123 struct tree_opt_pass pass_all_early_optimizations =
 124 {
 125   NULL,                                 /* name */
 126   gate_all_early_optimizations,         /* gate */
 127   NULL,                                 /* execute */
 128   NULL,                                 /* sub */
 129   NULL,                                 /* next */
 130   0,                                    /* static_pass_number */
 131   0,                                    /* tv_id */
 132   0,                                    /* properties_required */
 133   0,                                    /* properties_provided */
 134   0,                                    /* properties_destroyed */
 135   0,                                    /* todo_flags_start */
 136   0,                                    /* todo_flags_finish */
 137   0                                     /* letter */
 138 };
 139
 140 /* Pass: cleanup the CFG just before expanding trees to RTL.
 141    This is just a round of label cleanups and case node grouping
 142    because after the tree optimizers have run such cleanups may
 143    be necessary.  */
 144
 145 static void
 146 execute_cleanup_cfg_pre_ipa (void)
 147 {
 148   cleanup_tree_cfg ();
 149 }
 150
 151 struct tree_opt_pass pass_cleanup_cfg =
 152 {
 153   "cleanup_cfg",                        /* name */
 154   NULL,                                 /* gate */
 155   execute_cleanup_cfg_pre_ipa,          /* execute */
 156   NULL,                                 /* sub */
 157   NULL,                                 /* next */
 158   0,                                    /* static_pass_number */
 159   0,                                    /* tv_id */
 160   PROP_cfg,                             /* properties_required */
 161   0,                                    /* properties_provided */
 162   0,                                    /* properties_destroyed */
 163   0,                                    /* todo_flags_start */
 164   TODO_dump_func,                                       /* todo_flags_finish */
 165   0                                     /* letter */
 166 };
 167
 168
 169 /* Pass: cleanup the CFG just before expanding trees to RTL.
 170    This is just a round of label cleanups and case node grouping
 171    because after the tree optimizers have run such cleanups may
 172    be necessary.  */
 173
 174 static void
 175 execute_cleanup_cfg_post_optimizing (void)
 176 {
 177   fold_cond_expr_cond ();
 178   cleanup_tree_cfg ();
 179   cleanup_dead_labels ();
 180   group_case_labels ();
 181 }
 182
 183 struct tree_opt_pass pass_cleanup_cfg_post_optimizing =
 184 {
 185   "final_cleanup",                      /* name */
 186   NULL,                                 /* gate */
 187   execute_cleanup_cfg_post_optimizing,  /* execute */
 188   NULL,                                 /* sub */
 189   NULL,                                 /* next */
 190   0,                                    /* static_pass_number */
 191   0,                                    /* tv_id */
 192   PROP_cfg,                             /* properties_required */
 193   0,                                    /* properties_provided */
 194   0,                                    /* properties_destroyed */
 195   0,                                    /* todo_flags_start */
 196   TODO_dump_func,                                       /* todo_flags_finish */
 197   0                                     /* letter */
 198 };
 199
 200 /* Pass: do the actions required to finish with tree-ssa optimization
 201    passes.  */
 202
 203 static void
 204 execute_free_datastructures (void)
 205 {
 206   /* ??? This isn't the right place for this.  Worse, it got computed
 207      more or less at random in various passes.  */
 208   free_dominance_info (CDI_DOMINATORS);
 209   free_dominance_info (CDI_POST_DOMINATORS);
 210
 211   /* Remove the ssa structures.  Do it here since this includes statement
 212      annotations that need to be intact during disband_implicit_edges.  */
 213   if (cfun->ssa)
 214     delete_tree_ssa ();
 215 }
 216
 217 struct tree_opt_pass pass_free_datastructures =
 218 {
 219   NULL,                                 /* name */
 220   NULL,                                 /* gate */
 221   execute_free_datastructures,                  /* execute */
 222   NULL,                                 /* sub */
 223   NULL,                                 /* next */
 224   0,                                    /* static_pass_number */
 225   0,                                    /* tv_id */
 226   PROP_cfg,                             /* properties_required */
 227   0,                                    /* properties_provided */
 228   0,                                    /* properties_destroyed */
 229   0,                                    /* todo_flags_start */
 230   0,                                    /* todo_flags_finish */
 231   0                                     /* letter */
 232 };
 233 /* Pass: free cfg annotations.  */
 234
 235 static void
 236 execute_free_cfg_annotations (void)
 237 {
 238   basic_block bb;
 239   block_stmt_iterator bsi;
 240
 241   /* Emit gotos for implicit jumps.  */
 242   disband_implicit_edges ();
 243
 244   /* Remove annotations from every tree in the function.  */
 245   FOR_EACH_BB (bb)
 246     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 247       {
 248         tree stmt = bsi_stmt (bsi);
 249         ggc_free (stmt->common.ann);
 250         stmt->common.ann = NULL;
 251       }
 252
 253   /* And get rid of annotations we no longer need.  */
 254   delete_tree_cfg_annotations ();
 255 }
 256
 257 struct tree_opt_pass pass_free_cfg_annotations =
 258 {
 259   NULL,                                 /* name */
 260   NULL,                                 /* gate */
 261   execute_free_cfg_annotations,         /* execute */
 262   NULL,                                 /* sub */
 263   NULL,                                 /* next */
 264   0,                                    /* static_pass_number */
 265   0,                                    /* tv_id */
 266   PROP_cfg,                             /* properties_required */
 267   0,                                    /* properties_provided */
 268   0,                                    /* properties_destroyed */
 269   0,                                    /* todo_flags_start */
 270   0,                                    /* todo_flags_finish */
 271   0                                     /* letter */
 272 };
 273 /* Pass: fixup_cfg - IPA passes or compilation of earlier functions might've
 274    changed some properties - such as marked functions nothrow.  Remove now
 275    redundant edges and basic blocks.  */
 276
 277 static void
 278 execute_fixup_cfg (void)
 279 {
 280   basic_block bb;
 281   block_stmt_iterator bsi;
 282
 283   if (cfun->eh)
 284     FOR_EACH_BB (bb)
 285       {
 286         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 287           {
 288             tree stmt = bsi_stmt (bsi);
 289             tree call = get_call_expr_in (stmt);
 290
 291             if (call && call_expr_flags (call) & (ECF_CONST | ECF_PURE))
 292               TREE_SIDE_EFFECTS (call) = 0;
 293             if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 294               remove_stmt_from_eh_region (stmt);
 295           }
 296         tree_purge_dead_eh_edges (bb);
 297       }
 298
 299   cleanup_tree_cfg ();
 300 }
 301
 302 struct tree_opt_pass pass_fixup_cfg =
 303 {
 304   NULL,                                 /* name */
 305   NULL,                                 /* gate */
 306   execute_fixup_cfg,                    /* execute */
 307   NULL,                                 /* sub */
 308   NULL,                                 /* next */
 309   0,                                    /* static_pass_number */
 310   0,                                    /* tv_id */
 311   PROP_cfg,                             /* properties_required */
 312   0,                                    /* properties_provided */
 313   0,                                    /* properties_destroyed */
 314   0,                                    /* todo_flags_start */
 315   0,                                    /* todo_flags_finish */
 316   0                                     /* letter */
 317 };
 318
 319 /* Do the actions required to initialize internal data structures used
 320    in tree-ssa optimization passes.  */
 321
 322 static void
 323 execute_init_datastructures (void)
 324 {
 325   /* Allocate hash tables, arrays and other structures.  */
 326   init_tree_ssa ();
 327 }
 328
 329 struct tree_opt_pass pass_init_datastructures =
 330 {
 331   NULL,                                 /* name */
 332   NULL,                                 /* gate */
 333   execute_init_datastructures,          /* execute */
 334   NULL,                                 /* sub */
 335   NULL,                                 /* next */
 336   0,                                    /* static_pass_number */
 337   0,                                    /* tv_id */
 338   PROP_cfg,                             /* properties_required */
 339   0,                                    /* properties_provided */
 340   0,                                    /* properties_destroyed */
 341   0,                                    /* todo_flags_start */
 342   0,                                    /* todo_flags_finish */
 343   0                                     /* letter */
 344 };
 345
 346 void
 347 tree_lowering_passes (tree fn)
 348 {
 349   tree saved_current_function_decl = current_function_decl;
 350
 351   current_function_decl = fn;
 352   push_cfun (DECL_STRUCT_FUNCTION (fn));
 353   tree_register_cfg_hooks ();
 354   bitmap_obstack_initialize (NULL);
 355   execute_pass_list (all_lowering_passes);
 356   if (cgraph_global_info_ready && optimize)
 357     execute_pass_list (pass_all_early_optimizations.sub);
 358   free_dominance_info (CDI_POST_DOMINATORS);
 359   free_dominance_info (CDI_DOMINATORS);
 360   current_function_decl = saved_current_function_decl;
 361   bitmap_obstack_release (NULL);
 362   pop_cfun ();
 363 }
 364 \f
 365 /* For functions-as-trees languages, this performs all optimization and
 366    compilation for FNDECL.  */
 367
 368 void
 369 tree_rest_of_compilation (tree fndecl)
 370 {
 371   location_t saved_loc;
 372   struct cgraph_node *node;
 373
 374   timevar_push (TV_EXPAND);
 375
 376   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 377
 378   node = cgraph_node (fndecl);
 379
 380   /* Initialize the RTL code for the function.  */
 381   current_function_decl = fndecl;
 382   saved_loc = input_location;
 383   input_location = DECL_SOURCE_LOCATION (fndecl);
 384   init_function_start (fndecl);
 385
 386   /* Even though we're inside a function body, we still don't want to
 387      call expand_expr to calculate the size of a variable-sized array.
 388      We haven't necessarily assigned RTL to all variables yet, so it's
 389      not safe to try to expand expressions involving them.  */
 390   cfun->x_dont_save_pending_sizes_p = 1;
 391   cfun->after_inlining = true;
 392
 393   /* We are not going to maintain the cgraph edges up to date.
 394      Kill it so it won't confuse us.  */
 395   while (node->callees)
 396     {
 397       /* In non-unit-at-a-time we must mark all referenced functions as needed.
 398          */
 399       if (node->callees->callee->analyzed && !flag_unit_at_a_time)
 400         cgraph_mark_needed_node (node->callees->callee);
 401       cgraph_remove_edge (node->callees);
 402     }
 403
 404   /* We are not going to maintain the cgraph edges up to date.
 405      Kill it so it won't confuse us.  */
 406   cgraph_node_remove_callees (node);
 407
 408   bitmap_obstack_initialize (NULL);
 409   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 410
 411   tree_register_cfg_hooks ();
 412   /* Perform all tree transforms and optimizations.  */
 413   execute_pass_list (all_passes);
 414
 415   bitmap_obstack_release (&reg_obstack);
 416
 417   /* Release the default bitmap obstack.  */
 418   bitmap_obstack_release (NULL);
 419
 420   DECL_SAVED_TREE (fndecl) = NULL;
 421   cfun = 0;
 422
 423   /* If requested, warn about function definitions where the function will
 424      return a value (usually of some struct or union type) which itself will
 425      take up a lot of stack space.  */
 426   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 427     {
 428       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 429
 430       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 431           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 432           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 433                                    larger_than_size))
 434         {
 435           unsigned int size_as_int
 436             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 437
 438           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 439             warning (0, "size of return value of %q+D is %u bytes",
 440                      fndecl, size_as_int);
 441           else
 442             warning (0, "size of return value of %q+D is larger than %wd bytes",
 443                      fndecl, larger_than_size);
 444         }
 445     }
 446
 447   DECL_SAVED_TREE (fndecl) = NULL;
 448   if (DECL_STRUCT_FUNCTION (fndecl) == 0
 449       && !cgraph_node (fndecl)->origin)
 450     {
 451       /* Stop pointing to the local nodes about to be freed.
 452          But DECL_INITIAL must remain nonzero so we know this
 453          was an actual function definition.
 454          For a nested function, this is done in c_pop_function_context.
 455          If rest_of_compilation set this to 0, leave it 0.  */
 456       if (DECL_INITIAL (fndecl) != 0)
 457         DECL_INITIAL (fndecl) = error_mark_node;
 458     }
 459
 460   input_location = saved_loc;
 461
 462   ggc_collect ();
 463   timevar_pop (TV_EXPAND);
 464 }