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                                                   | ECF_LOOPING_CONST_OR_PURE)
 304                 && TREE_SIDE_EFFECTS (call))
 305               {
 306                 if (gimple_in_ssa_p (cfun))
 307                   {
 308                     todo |= TODO_update_ssa | TODO_cleanup_cfg;
 309                     update_stmt (stmt);
 310                   }
 311                 TREE_SIDE_EFFECTS (call) = 0;
 312               }
 313             if (decl && TREE_NOTHROW (decl))
 314               TREE_NOTHROW (call) = 1;
 315             if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 316               remove_stmt_from_eh_region (stmt);
 317           }
 318         if (tree_purge_dead_eh_edges (bb))
 319           todo |= TODO_cleanup_cfg;
 320       }
 321
 322   /* Dump a textual representation of the flowgraph.  */
 323   if (dump_file)
 324     dump_tree_cfg (dump_file, dump_flags);
 325
 326   return todo;
 327 }
 328
 329 /* Do the actions required to initialize internal data structures used
 330    in tree-ssa optimization passes.  */
 331
 332 static unsigned int
 333 execute_init_datastructures (void)
 334 {
 335   /* Allocate hash tables, arrays and other structures.  */
 336   init_tree_ssa ();
 337   return 0;
 338 }
 339
 340 /* Gate: initialize or not the SSA datastructures.  */
 341
 342 static bool
 343 gate_init_datastructures (void)
 344 {
 345   return (optimize >= 1);
 346 }
 347
 348 struct gimple_opt_pass pass_init_datastructures =
 349 {
 350  {
 351   GIMPLE_PASS,
 352   NULL,                                 /* name */
 353   gate_init_datastructures,             /* gate */
 354   execute_init_datastructures,          /* execute */
 355   NULL,                                 /* sub */
 356   NULL,                                 /* next */
 357   0,                                    /* static_pass_number */
 358   0,                                    /* tv_id */
 359   PROP_cfg,                             /* properties_required */
 360   0,                                    /* properties_provided */
 361   0,                                    /* properties_destroyed */
 362   0,                                    /* todo_flags_start */
 363   0                                     /* todo_flags_finish */
 364  }
 365 };
 366
 367 void
 368 tree_lowering_passes (tree fn)
 369 {
 370   tree saved_current_function_decl = current_function_decl;
 371
 372   current_function_decl = fn;
 373   push_cfun (DECL_STRUCT_FUNCTION (fn));
 374   tree_register_cfg_hooks ();
 375   bitmap_obstack_initialize (NULL);
 376   execute_pass_list (all_lowering_passes);
 377   if (optimize && cgraph_global_info_ready)
 378     execute_pass_list (pass_early_local_passes.pass.sub);
 379   free_dominance_info (CDI_POST_DOMINATORS);
 380   free_dominance_info (CDI_DOMINATORS);
 381   compact_blocks ();
 382   current_function_decl = saved_current_function_decl;
 383   bitmap_obstack_release (NULL);
 384   pop_cfun ();
 385 }
 386 \f
 387 /* For functions-as-trees languages, this performs all optimization and
 388    compilation for FNDECL.  */
 389
 390 void
 391 tree_rest_of_compilation (tree fndecl)
 392 {
 393   location_t saved_loc;
 394   struct cgraph_node *node;
 395
 396   timevar_push (TV_EXPAND);
 397
 398   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 399
 400   node = cgraph_node (fndecl);
 401
 402   /* Initialize the default bitmap obstack.  */
 403   bitmap_obstack_initialize (NULL);
 404
 405   /* Initialize the RTL code for the function.  */
 406   current_function_decl = fndecl;
 407   saved_loc = input_location;
 408   input_location = DECL_SOURCE_LOCATION (fndecl);
 409   init_function_start (fndecl);
 410
 411   /* Even though we're inside a function body, we still don't want to
 412      call expand_expr to calculate the size of a variable-sized array.
 413      We haven't necessarily assigned RTL to all variables yet, so it's
 414      not safe to try to expand expressions involving them.  */
 415   cfun->dont_save_pending_sizes_p = 1;
 416
 417   tree_register_cfg_hooks ();
 418
 419   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 420   /* Perform all tree transforms and optimizations.  */
 421   execute_pass_list (all_passes);
 422
 423   bitmap_obstack_release (&reg_obstack);
 424
 425   /* Release the default bitmap obstack.  */
 426   bitmap_obstack_release (NULL);
 427
 428   DECL_SAVED_TREE (fndecl) = NULL;
 429   set_cfun (NULL);
 430
 431   /* If requested, warn about function definitions where the function will
 432      return a value (usually of some struct or union type) which itself will
 433      take up a lot of stack space.  */
 434   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 435     {
 436       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 437
 438       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 439           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 440           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 441                                    larger_than_size))
 442         {
 443           unsigned int size_as_int
 444             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 445
 446           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 447             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is %u bytes",
 448                      fndecl, size_as_int);
 449           else
 450             warning (OPT_Wlarger_than_eq, "size of return value of %q+D is larger than %wd bytes",
 451                      fndecl, larger_than_size);
 452         }
 453     }
 454
 455   if (!flag_inline_trees)
 456     {
 457       DECL_SAVED_TREE (fndecl) = NULL;
 458       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 459           && !cgraph_node (fndecl)->origin)
 460         {
 461           /* Stop pointing to the local nodes about to be freed.
 462              But DECL_INITIAL must remain nonzero so we know this
 463              was an actual function definition.
 464              For a nested function, this is done in c_pop_function_context.
 465              If rest_of_compilation set this to 0, leave it 0.  */
 466           if (DECL_INITIAL (fndecl) != 0)
 467             DECL_INITIAL (fndecl) = error_mark_node;
 468         }
 469     }
 470
 471   input_location = saved_loc;
 472
 473   ggc_collect ();
 474   timevar_pop (TV_EXPAND);
 475 }