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   /* ??? This isn't the right place for this.  Worse, it got computed
 212      more or less at random in various passes.  */
 213   free_dominance_info (CDI_DOMINATORS);
 214   free_dominance_info (CDI_POST_DOMINATORS);
 215
 216   /* Remove the ssa structures.  Do it here since this includes statement
 217      annotations that need to be intact during disband_implicit_edges.  */
 218   if (cfun->gimple_df)
 219     delete_tree_ssa ();
 220   return 0;
 221 }
 222
 223 struct tree_opt_pass pass_free_datastructures =
 224 {
 225   NULL,                                 /* name */
 226   NULL,                                 /* gate */
 227   execute_free_datastructures,                  /* execute */
 228   NULL,                                 /* sub */
 229   NULL,                                 /* next */
 230   0,                                    /* static_pass_number */
 231   0,                                    /* tv_id */
 232   PROP_cfg,                             /* properties_required */
 233   0,                                    /* properties_provided */
 234   0,                                    /* properties_destroyed */
 235   0,                                    /* todo_flags_start */
 236   0,                                    /* todo_flags_finish */
 237   0                                     /* letter */
 238 };
 239 /* Pass: free cfg annotations.  */
 240
 241 static unsigned int
 242 execute_free_cfg_annotations (void)
 243 {
 244   /* Emit gotos for implicit jumps.  */
 245   disband_implicit_edges ();
 246
 247   /* And get rid of annotations we no longer need.  */
 248   delete_tree_cfg_annotations ();
 249
 250   return 0;
 251 }
 252
 253 struct tree_opt_pass pass_free_cfg_annotations =
 254 {
 255   NULL,                                 /* name */
 256   NULL,                                 /* gate */
 257   execute_free_cfg_annotations,         /* execute */
 258   NULL,                                 /* sub */
 259   NULL,                                 /* next */
 260   0,                                    /* static_pass_number */
 261   0,                                    /* tv_id */
 262   PROP_cfg,                             /* properties_required */
 263   0,                                    /* properties_provided */
 264   0,                                    /* properties_destroyed */
 265   0,                                    /* todo_flags_start */
 266   0,                                    /* todo_flags_finish */
 267   0                                     /* letter */
 268 };
 269
 270 /* Return true if BB has at least one abnormal outgoing edge.  */
 271
 272 static inline bool
 273 has_abnormal_outgoing_edge_p (basic_block bb)
 274 {
 275   edge e;
 276   edge_iterator ei;
 277
 278   FOR_EACH_EDGE (e, ei, bb->succs)
 279     if (e->flags & EDGE_ABNORMAL)
 280       return true;
 281
 282   return false;
 283 }
 284
 285 /* Pass: fixup_cfg.  IPA passes, compilation of earlier functions or inlining
 286    might have changed some properties, such as marked functions nothrow or
 287    added calls that can potentially go to non-local labels.  Remove redundant
 288    edges and basic blocks, and create new ones if necessary.
 289
 290    This pass can't be executed as stand alone pass from pass manager, because
 291    in between inlining and this fixup the verify_flow_info would fail.  */
 292
 293 unsigned int
 294 execute_fixup_cfg (void)
 295 {
 296   basic_block bb;
 297   block_stmt_iterator bsi;
 298   int todo = gimple_in_ssa_p (cfun) ? TODO_verify_ssa : 0;
 299
 300   cfun->after_inlining = true;
 301
 302   if (cfun->eh)
 303     FOR_EACH_BB (bb)
 304       {
 305         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 306           {
 307             tree stmt = bsi_stmt (bsi);
 308             tree call = get_call_expr_in (stmt);
 309             tree decl = call ? get_callee_fndecl (call) : NULL;
 310
 311             if (decl && call_expr_flags (call) & (ECF_CONST | ECF_PURE)
 312                 && TREE_SIDE_EFFECTS (call))
 313               {
 314                 if (gimple_in_ssa_p (cfun))
 315                   {
 316                     todo |= TODO_update_ssa | TODO_cleanup_cfg;
 317                     update_stmt (stmt);
 318                   }
 319                 TREE_SIDE_EFFECTS (call) = 0;
 320               }
 321             if (decl && TREE_NOTHROW (decl))
 322               TREE_NOTHROW (call) = 1;
 323             if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 324               remove_stmt_from_eh_region (stmt);
 325           }
 326         if (tree_purge_dead_eh_edges (bb))
 327           todo |= TODO_cleanup_cfg;
 328       }
 329
 330   if (current_function_has_nonlocal_label)
 331     {
 332       FOR_EACH_BB (bb)
 333         {
 334           for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 335             {
 336               tree stmt = bsi_stmt (bsi);
 337               if (tree_can_make_abnormal_goto (stmt))
 338                 {
 339                   if (stmt == bsi_stmt (bsi_last (bb)))
 340                     {
 341                       if (!has_abnormal_outgoing_edge_p (bb))
 342                         make_abnormal_goto_edges (bb, true);
 343                     }
 344                   else
 345                     {
 346                       edge e = split_block (bb, stmt);
 347                       bb = e->src;
 348                       make_abnormal_goto_edges (bb, true);
 349                     }
 350                   break;
 351                 }
 352
 353               /* Update PHIs on nonlocal goto receivers we (possibly)
 354                  just created new edges into.  */
 355               if (TREE_CODE (stmt) == LABEL_EXPR
 356                   && gimple_in_ssa_p (cfun))
 357                 {
 358                   tree target = LABEL_EXPR_LABEL (stmt);
 359                   if (DECL_NONLOCAL (target))
 360                     {
 361                       tree phi;
 362
 363                       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 364                         {
 365                           todo |= TODO_update_ssa | TODO_cleanup_cfg;
 366                           gcc_assert (SSA_NAME_OCCURS_IN_ABNORMAL_PHI
 367                                       (PHI_RESULT (phi)));
 368                           mark_sym_for_renaming
 369                             (SSA_NAME_VAR (PHI_RESULT (phi)));
 370                         }
 371                     }
 372                 }
 373             }
 374         }
 375     }
 376
 377   /* Dump a textual representation of the flowgraph.  */
 378   if (dump_file)
 379     dump_tree_cfg (dump_file, dump_flags);
 380
 381   return todo;
 382 }
 383
 384 /* Do the actions required to initialize internal data structures used
 385    in tree-ssa optimization passes.  */
 386
 387 static unsigned int
 388 execute_init_datastructures (void)
 389 {
 390   /* Allocate hash tables, arrays and other structures.  */
 391   init_tree_ssa ();
 392   return 0;
 393 }
 394
 395 /* Gate: initialize or not the SSA datastructures.  */
 396
 397 static bool
 398 gate_init_datastructures (void)
 399 {
 400   return (optimize >= 1);
 401 }
 402
 403 struct tree_opt_pass pass_init_datastructures =
 404 {
 405   NULL,                                 /* name */
 406   gate_init_datastructures,             /* gate */
 407   execute_init_datastructures,          /* execute */
 408   NULL,                                 /* sub */
 409   NULL,                                 /* next */
 410   0,                                    /* static_pass_number */
 411   0,                                    /* tv_id */
 412   PROP_cfg,                             /* properties_required */
 413   0,                                    /* properties_provided */
 414   0,                                    /* properties_destroyed */
 415   0,                                    /* todo_flags_start */
 416   0,                                    /* todo_flags_finish */
 417   0                                     /* letter */
 418 };
 419
 420 void
 421 tree_lowering_passes (tree fn)
 422 {
 423   tree saved_current_function_decl = current_function_decl;
 424
 425   current_function_decl = fn;
 426   push_cfun (DECL_STRUCT_FUNCTION (fn));
 427   tree_register_cfg_hooks ();
 428   bitmap_obstack_initialize (NULL);
 429   execute_pass_list (all_lowering_passes);
 430   if (optimize && cgraph_global_info_ready)
 431     execute_pass_list (pass_early_local_passes.sub);
 432   free_dominance_info (CDI_POST_DOMINATORS);
 433   free_dominance_info (CDI_DOMINATORS);
 434   compact_blocks ();
 435   current_function_decl = saved_current_function_decl;
 436   bitmap_obstack_release (NULL);
 437   pop_cfun ();
 438 }
 439 \f
 440 /* For functions-as-trees languages, this performs all optimization and
 441    compilation for FNDECL.  */
 442
 443 void
 444 tree_rest_of_compilation (tree fndecl)
 445 {
 446   location_t saved_loc;
 447   struct cgraph_node *node;
 448
 449   timevar_push (TV_EXPAND);
 450
 451   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 452
 453   node = cgraph_node (fndecl);
 454
 455   /* Initialize the default bitmap obstack.  */
 456   bitmap_obstack_initialize (NULL);
 457
 458   /* Initialize the RTL code for the function.  */
 459   current_function_decl = fndecl;
 460   cfun = DECL_STRUCT_FUNCTION (fndecl);
 461   saved_loc = input_location;
 462   input_location = DECL_SOURCE_LOCATION (fndecl);
 463   init_function_start (fndecl);
 464
 465   /* Even though we're inside a function body, we still don't want to
 466      call expand_expr to calculate the size of a variable-sized array.
 467      We haven't necessarily assigned RTL to all variables yet, so it's
 468      not safe to try to expand expressions involving them.  */
 469   cfun->x_dont_save_pending_sizes_p = 1;
 470
 471   tree_register_cfg_hooks ();
 472
 473   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 474   /* Perform all tree transforms and optimizations.  */
 475   execute_pass_list (all_passes);
 476
 477   bitmap_obstack_release (&reg_obstack);
 478
 479   /* Release the default bitmap obstack.  */
 480   bitmap_obstack_release (NULL);
 481
 482   DECL_SAVED_TREE (fndecl) = NULL;
 483   cfun = 0;
 484
 485   /* If requested, warn about function definitions where the function will
 486      return a value (usually of some struct or union type) which itself will
 487      take up a lot of stack space.  */
 488   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 489     {
 490       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 491
 492       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 493           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 494           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 495                                    larger_than_size))
 496         {
 497           unsigned int size_as_int
 498             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 499
 500           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 501             warning (0, "size of return value of %q+D is %u bytes",
 502                      fndecl, size_as_int);
 503           else
 504             warning (0, "size of return value of %q+D is larger than %wd bytes",
 505                      fndecl, larger_than_size);
 506         }
 507     }
 508
 509   if (!flag_inline_trees)
 510     {
 511       DECL_SAVED_TREE (fndecl) = NULL;
 512       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 513           && !cgraph_node (fndecl)->origin)
 514         {
 515           /* Stop pointing to the local nodes about to be freed.
 516              But DECL_INITIAL must remain nonzero so we know this
 517              was an actual function definition.
 518              For a nested function, this is done in c_pop_function_context.
 519              If rest_of_compilation set this to 0, leave it 0.  */
 520           if (DECL_INITIAL (fndecl) != 0)
 521             DECL_INITIAL (fndecl) = error_mark_node;
 522         }
 523     }
 524
 525   input_location = saved_loc;
 526
 527   ggc_collect ();
 528   timevar_pop (TV_EXPAND);
 529 }