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