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