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   free_dominance_info (CDI_DOMINATORS);
 212   free_dominance_info (CDI_POST_DOMINATORS);
 213
 214   /* Remove the ssa structures.  */
 215   if (cfun->gimple_df)
 216     delete_tree_ssa ();
 217   return 0;
 218 }
 219
 220 struct tree_opt_pass pass_free_datastructures =
 221 {
 222   NULL,                                 /* name */
 223   NULL,                                 /* gate */
 224   execute_free_datastructures,                  /* 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: free cfg annotations.  */
 237
 238 static unsigned int
 239 execute_free_cfg_annotations (void)
 240 {
 241   /* And get rid of annotations we no longer need.  */
 242   delete_tree_cfg_annotations ();
 243
 244   return 0;
 245 }
 246
 247 struct tree_opt_pass pass_free_cfg_annotations =
 248 {
 249   NULL,                                 /* name */
 250   NULL,                                 /* gate */
 251   execute_free_cfg_annotations,         /* execute */
 252   NULL,                                 /* sub */
 253   NULL,                                 /* next */
 254   0,                                    /* static_pass_number */
 255   0,                                    /* tv_id */
 256   PROP_cfg,                             /* properties_required */
 257   0,                                    /* properties_provided */
 258   0,                                    /* properties_destroyed */
 259   0,                                    /* todo_flags_start */
 260   0,                                    /* todo_flags_finish */
 261   0                                     /* letter */
 262 };
 263
 264 /* Pass: fixup_cfg.  IPA passes, compilation of earlier functions or inlining
 265    might have changed some properties, such as marked functions nothrow.
 266    Remove redundant edges and basic blocks, and create new ones if necessary.
 267
 268    This pass can't be executed as stand alone pass from pass manager, because
 269    in between inlining and this fixup the verify_flow_info would fail.  */
 270
 271 unsigned int
 272 execute_fixup_cfg (void)
 273 {
 274   basic_block bb;
 275   block_stmt_iterator bsi;
 276   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 277
 278   cfun->after_inlining = true;
 279
 280   if (cfun->eh)
 281     FOR_EACH_BB (bb)
 282       {
 283         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 284           {
 285             tree stmt = bsi_stmt (bsi);
 286             tree call = get_call_expr_in (stmt);
 287             tree decl = call ? get_callee_fndecl (call) : NULL;
 288
 289             if (decl && call_expr_flags (call) & (ECF_CONST | ECF_PURE)
 290                 && TREE_SIDE_EFFECTS (call))
 291               {
 292                 if (gimple_in_ssa_p (cfun))
 293                   {
 294                     todo |= TODO_update_ssa | TODO_cleanup_cfg;
 295                     update_stmt (stmt);
 296                   }
 297                 TREE_SIDE_EFFECTS (call) = 0;
 298               }
 299             if (decl && TREE_NOTHROW (decl))
 300               TREE_NOTHROW (call) = 1;
 301             if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 302               remove_stmt_from_eh_region (stmt);
 303           }
 304         if (tree_purge_dead_eh_edges (bb))
 305           todo |= TODO_cleanup_cfg;
 306       }
 307
 308   /* Dump a textual representation of the flowgraph.  */
 309   if (dump_file)
 310     dump_tree_cfg (dump_file, dump_flags);
 311
 312   return todo;
 313 }
 314
 315 /* Do the actions required to initialize internal data structures used
 316    in tree-ssa optimization passes.  */
 317
 318 static unsigned int
 319 execute_init_datastructures (void)
 320 {
 321   /* Allocate hash tables, arrays and other structures.  */
 322   init_tree_ssa ();
 323   return 0;
 324 }
 325
 326 /* Gate: initialize or not the SSA datastructures.  */
 327
 328 static bool
 329 gate_init_datastructures (void)
 330 {
 331   return (optimize >= 1);
 332 }
 333
 334 struct tree_opt_pass pass_init_datastructures =
 335 {
 336   NULL,                                 /* name */
 337   gate_init_datastructures,             /* gate */
 338   execute_init_datastructures,          /* execute */
 339   NULL,                                 /* sub */
 340   NULL,                                 /* next */
 341   0,                                    /* static_pass_number */
 342   0,                                    /* tv_id */
 343   PROP_cfg,                             /* properties_required */
 344   0,                                    /* properties_provided */
 345   0,                                    /* properties_destroyed */
 346   0,                                    /* todo_flags_start */
 347   0,                                    /* todo_flags_finish */
 348   0                                     /* letter */
 349 };
 350
 351 void
 352 tree_lowering_passes (tree fn)
 353 {
 354   tree saved_current_function_decl = current_function_decl;
 355
 356   current_function_decl = fn;
 357   push_cfun (DECL_STRUCT_FUNCTION (fn));
 358   tree_register_cfg_hooks ();
 359   bitmap_obstack_initialize (NULL);
 360   execute_pass_list (all_lowering_passes);
 361   if (optimize && cgraph_global_info_ready)
 362     execute_pass_list (pass_early_local_passes.sub);
 363   free_dominance_info (CDI_POST_DOMINATORS);
 364   free_dominance_info (CDI_DOMINATORS);
 365   compact_blocks ();
 366   current_function_decl = saved_current_function_decl;
 367   bitmap_obstack_release (NULL);
 368   pop_cfun ();
 369 }
 370 \f
 371 /* For functions-as-trees languages, this performs all optimization and
 372    compilation for FNDECL.  */
 373
 374 void
 375 tree_rest_of_compilation (tree fndecl)
 376 {
 377   location_t saved_loc;
 378   struct cgraph_node *node;
 379
 380   timevar_push (TV_EXPAND);
 381
 382   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 383
 384   node = cgraph_node (fndecl);
 385
 386   /* Initialize the default bitmap obstack.  */
 387   bitmap_obstack_initialize (NULL);
 388
 389   /* Initialize the RTL code for the function.  */
 390   current_function_decl = fndecl;
 391   cfun = DECL_STRUCT_FUNCTION (fndecl);
 392   saved_loc = input_location;
 393   input_location = DECL_SOURCE_LOCATION (fndecl);
 394   init_function_start (fndecl);
 395
 396   /* Even though we're inside a function body, we still don't want to
 397      call expand_expr to calculate the size of a variable-sized array.
 398      We haven't necessarily assigned RTL to all variables yet, so it's
 399      not safe to try to expand expressions involving them.  */
 400   cfun->x_dont_save_pending_sizes_p = 1;
 401
 402   tree_register_cfg_hooks ();
 403
 404   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 405   /* Perform all tree transforms and optimizations.  */
 406   execute_pass_list (all_passes);
 407
 408   bitmap_obstack_release (&reg_obstack);
 409
 410   /* Release the default bitmap obstack.  */
 411   bitmap_obstack_release (NULL);
 412
 413   DECL_SAVED_TREE (fndecl) = NULL;
 414   cfun = 0;
 415
 416   /* If requested, warn about function definitions where the function will
 417      return a value (usually of some struct or union type) which itself will
 418      take up a lot of stack space.  */
 419   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 420     {
 421       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 422
 423       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 424           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 425           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 426                                    larger_than_size))
 427         {
 428           unsigned int size_as_int
 429             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 430
 431           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 432             warning (0, "size of return value of %q+D is %u bytes",
 433                      fndecl, size_as_int);
 434           else
 435             warning (0, "size of return value of %q+D is larger than %wd bytes",
 436                      fndecl, larger_than_size);
 437         }
 438     }
 439
 440   if (!flag_inline_trees)
 441     {
 442       DECL_SAVED_TREE (fndecl) = NULL;
 443       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 444           && !cgraph_node (fndecl)->origin)
 445         {
 446           /* Stop pointing to the local nodes about to be freed.
 447              But DECL_INITIAL must remain nonzero so we know this
 448              was an actual function definition.
 449              For a nested function, this is done in c_pop_function_context.
 450              If rest_of_compilation set this to 0, leave it 0.  */
 451           if (DECL_INITIAL (fndecl) != 0)
 452             DECL_INITIAL (fndecl) = error_mark_node;
 453         }
 454     }
 455
 456   input_location = saved_loc;
 457
 458   ggc_collect ();
 459   timevar_pop (TV_EXPAND);
 460 }