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
 440 /* Update recursively all inlined_to pointers of functions
 441    inlined into NODE to INLINED_TO.  */
 442 static void
 443 update_inlined_to_pointers (struct cgraph_node *node,
 444                             struct cgraph_node *inlined_to)
 445 {
 446   struct cgraph_edge *e;
 447   for (e = node->callees; e; e = e->next_callee)
 448     {
 449       if (e->callee->global.inlined_to)
 450         {
 451           e->callee->global.inlined_to = inlined_to;
 452           update_inlined_to_pointers (e->callee, inlined_to);
 453         }
 454     }
 455 }
 456
 457 \f
 458 /* For functions-as-trees languages, this performs all optimization and
 459    compilation for FNDECL.  */
 460
 461 void
 462 tree_rest_of_compilation (tree fndecl)
 463 {
 464   location_t saved_loc;
 465   struct cgraph_node *node;
 466
 467   timevar_push (TV_EXPAND);
 468
 469   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 470
 471   node = cgraph_node (fndecl);
 472
 473   /* Initialize the default bitmap obstack.  */
 474   bitmap_obstack_initialize (NULL);
 475
 476   /* Initialize the RTL code for the function.  */
 477   current_function_decl = fndecl;
 478   cfun = DECL_STRUCT_FUNCTION (fndecl);
 479   saved_loc = input_location;
 480   input_location = DECL_SOURCE_LOCATION (fndecl);
 481   init_function_start (fndecl);
 482
 483   /* Even though we're inside a function body, we still don't want to
 484      call expand_expr to calculate the size of a variable-sized array.
 485      We haven't necessarily assigned RTL to all variables yet, so it's
 486      not safe to try to expand expressions involving them.  */
 487   cfun->x_dont_save_pending_sizes_p = 1;
 488
 489   tree_register_cfg_hooks ();
 490
 491   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 492   /* Perform all tree transforms and optimizations.  */
 493   execute_pass_list (all_passes);
 494
 495   bitmap_obstack_release (&reg_obstack);
 496
 497   /* Release the default bitmap obstack.  */
 498   bitmap_obstack_release (NULL);
 499
 500   DECL_SAVED_TREE (fndecl) = NULL;
 501   cfun = 0;
 502
 503   /* If requested, warn about function definitions where the function will
 504      return a value (usually of some struct or union type) which itself will
 505      take up a lot of stack space.  */
 506   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 507     {
 508       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 509
 510       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 511           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 512           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 513                                    larger_than_size))
 514         {
 515           unsigned int size_as_int
 516             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 517
 518           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 519             warning (0, "size of return value of %q+D is %u bytes",
 520                      fndecl, size_as_int);
 521           else
 522             warning (0, "size of return value of %q+D is larger than %wd bytes",
 523                      fndecl, larger_than_size);
 524         }
 525     }
 526
 527   if (!flag_inline_trees)
 528     {
 529       DECL_SAVED_TREE (fndecl) = NULL;
 530       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 531           && !cgraph_node (fndecl)->origin)
 532         {
 533           /* Stop pointing to the local nodes about to be freed.
 534              But DECL_INITIAL must remain nonzero so we know this
 535              was an actual function definition.
 536              For a nested function, this is done in c_pop_function_context.
 537              If rest_of_compilation set this to 0, leave it 0.  */
 538           if (DECL_INITIAL (fndecl) != 0)
 539             DECL_INITIAL (fndecl) = error_mark_node;
 540         }
 541     }
 542
 543   input_location = saved_loc;
 544
 545   ggc_collect ();
 546   timevar_pop (TV_EXPAND);
 547 }