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