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   saved_loc = input_location;
 391   input_location = DECL_SOURCE_LOCATION (fndecl);
 392   init_function_start (fndecl);
 393
 394   /* Even though we're inside a function body, we still don't want to
 395      call expand_expr to calculate the size of a variable-sized array.
 396      We haven't necessarily assigned RTL to all variables yet, so it's
 397      not safe to try to expand expressions involving them.  */
 398   cfun->x_dont_save_pending_sizes_p = 1;
 399
 400   tree_register_cfg_hooks ();
 401
 402   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 403   /* Perform all tree transforms and optimizations.  */
 404   execute_pass_list (all_passes);
 405
 406   bitmap_obstack_release (&reg_obstack);
 407
 408   /* Release the default bitmap obstack.  */
 409   bitmap_obstack_release (NULL);
 410
 411   DECL_SAVED_TREE (fndecl) = NULL;
 412   set_cfun (NULL);
 413
 414   /* If requested, warn about function definitions where the function will
 415      return a value (usually of some struct or union type) which itself will
 416      take up a lot of stack space.  */
 417   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 418     {
 419       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 420
 421       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 422           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 423           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 424                                    larger_than_size))
 425         {
 426           unsigned int size_as_int
 427             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 428
 429           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 430             warning (0, "size of return value of %q+D is %u bytes",
 431                      fndecl, size_as_int);
 432           else
 433             warning (0, "size of return value of %q+D is larger than %wd bytes",
 434                      fndecl, larger_than_size);
 435         }
 436     }
 437
 438   if (!flag_inline_trees)
 439     {
 440       DECL_SAVED_TREE (fndecl) = NULL;
 441       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 442           && !cgraph_node (fndecl)->origin)
 443         {
 444           /* Stop pointing to the local nodes about to be freed.
 445              But DECL_INITIAL must remain nonzero so we know this
 446              was an actual function definition.
 447              For a nested function, this is done in c_pop_function_context.
 448              If rest_of_compilation set this to 0, leave it 0.  */
 449           if (DECL_INITIAL (fndecl) != 0)
 450             DECL_INITIAL (fndecl) = error_mark_node;
 451         }
 452     }
 453
 454   input_location = saved_loc;
 455
 456   ggc_collect ();
 457   timevar_pop (TV_EXPAND);
 458 }