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