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   0,                                    /* 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   basic_block bb;
 245   block_stmt_iterator bsi;
 246
 247   /* Emit gotos for implicit jumps.  */
 248   disband_implicit_edges ();
 249
 250   /* Remove annotations from every tree in the function.  */
 251   FOR_EACH_BB (bb)
 252     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 253       {
 254         tree stmt = bsi_stmt (bsi);
 255         ggc_free (stmt->base.ann);
 256         stmt->base.ann = NULL;
 257       }
 258
 259   /* And get rid of annotations we no longer need.  */
 260   delete_tree_cfg_annotations ();
 261
 262 #ifdef ENABLE_CHECKING
 263   /* Once the statement annotations have been removed, we can verify
 264      the integrity of statements in the EH throw table.  */
 265   verify_eh_throw_table_statements ();
 266 #endif
 267   return 0;
 268 }
 269
 270 struct tree_opt_pass pass_free_cfg_annotations =
 271 {
 272   NULL,                                 /* name */
 273   NULL,                                 /* gate */
 274   execute_free_cfg_annotations,         /* execute */
 275   NULL,                                 /* sub */
 276   NULL,                                 /* next */
 277   0,                                    /* static_pass_number */
 278   0,                                    /* tv_id */
 279   PROP_cfg,                             /* properties_required */
 280   0,                                    /* properties_provided */
 281   0,                                    /* properties_destroyed */
 282   0,                                    /* todo_flags_start */
 283   0,                                    /* todo_flags_finish */
 284   0                                     /* letter */
 285 };
 286
 287 /* Return true if BB has at least one abnormal outgoing edge.  */
 288
 289 static inline bool
 290 has_abnormal_outgoing_edge_p (basic_block bb)
 291 {
 292   edge e;
 293   edge_iterator ei;
 294
 295   FOR_EACH_EDGE (e, ei, bb->succs)
 296     if (e->flags & EDGE_ABNORMAL)
 297       return true;
 298
 299   return false;
 300 }
 301
 302 /* Pass: fixup_cfg.  IPA passes, compilation of earlier functions or inlining
 303    might have changed some properties, such as marked functions nothrow or
 304    added calls that can potentially go to non-local labels.  Remove redundant
 305    edges and basic blocks, and create new ones if necessary.  */
 306
 307 static unsigned int
 308 execute_fixup_cfg (void)
 309 {
 310   basic_block bb;
 311   block_stmt_iterator bsi;
 312
 313   cfun->after_inlining = true;
 314
 315   if (cfun->eh)
 316     FOR_EACH_BB (bb)
 317       {
 318         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 319           {
 320             tree stmt = bsi_stmt (bsi);
 321             tree call = get_call_expr_in (stmt);
 322             tree decl = call ? get_callee_fndecl (call) : NULL;
 323
 324             if (decl && call_expr_flags (call) & (ECF_CONST | ECF_PURE)
 325                 && TREE_SIDE_EFFECTS (call))
 326               {
 327                 update_stmt (stmt);
 328                 TREE_SIDE_EFFECTS (call) = 0;
 329               }
 330             if (decl && TREE_NOTHROW (decl))
 331               TREE_NOTHROW (call) = 1;
 332             if (!tree_could_throw_p (stmt) && lookup_stmt_eh_region (stmt))
 333               remove_stmt_from_eh_region (stmt);
 334           }
 335         tree_purge_dead_eh_edges (bb);
 336       }
 337
 338   if (current_function_has_nonlocal_label)
 339     {
 340       FOR_EACH_BB (bb)
 341         {
 342           for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 343             {
 344               tree stmt = bsi_stmt (bsi);
 345               if (tree_can_make_abnormal_goto (stmt))
 346                 {
 347                   if (stmt == bsi_stmt (bsi_last (bb)))
 348                     {
 349                       if (!has_abnormal_outgoing_edge_p (bb))
 350                         make_abnormal_goto_edges (bb, true);
 351                     }
 352                   else
 353                     {
 354                       edge e = split_block (bb, stmt);
 355                       bb = e->src;
 356                       make_abnormal_goto_edges (bb, true);
 357                     }
 358                   break;
 359                 }
 360
 361               /* Update PHIs on nonlocal goto receivers we (possibly)
 362                  just created new edges into.  */
 363               if (TREE_CODE (stmt) == LABEL_EXPR
 364                   && gimple_in_ssa_p (cfun))
 365                 {
 366                   tree target = LABEL_EXPR_LABEL (stmt);
 367                   if (DECL_NONLOCAL (target))
 368                     {
 369                       tree phi;
 370                       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 371                         {
 372                           gcc_assert (SSA_NAME_OCCURS_IN_ABNORMAL_PHI
 373                                       (PHI_RESULT (phi)));
 374                           mark_sym_for_renaming
 375                             (SSA_NAME_VAR (PHI_RESULT (phi)));
 376                         }
 377                     }
 378                 }
 379             }
 380         }
 381     }
 382
 383   if (gimple_in_ssa_p (cfun))
 384     {
 385       delete_unreachable_blocks ();
 386       update_ssa (TODO_update_ssa);
 387     }
 388   cleanup_tree_cfg ();
 389
 390   /* Dump a textual representation of the flowgraph.  */
 391   if (dump_file)
 392     dump_tree_cfg (dump_file, dump_flags);
 393
 394   return 0;
 395 }
 396
 397 struct tree_opt_pass pass_fixup_cfg =
 398 {
 399   "fixupcfg",                           /* name */
 400   NULL,                                 /* gate */
 401   execute_fixup_cfg,                    /* execute */
 402   NULL,                                 /* sub */
 403   NULL,                                 /* next */
 404   0,                                    /* static_pass_number */
 405   0,                                    /* tv_id */
 406   PROP_cfg,                             /* properties_required */
 407   0,                                    /* properties_provided */
 408   0,                                    /* properties_destroyed */
 409   0,                                    /* todo_flags_start */
 410   0,                                    /* todo_flags_finish */
 411   0                                     /* letter */
 412 };
 413
 414 /* Do the actions required to initialize internal data structures used
 415    in tree-ssa optimization passes.  */
 416
 417 static unsigned int
 418 execute_init_datastructures (void)
 419 {
 420   /* Allocate hash tables, arrays and other structures.  */
 421   init_tree_ssa ();
 422   return 0;
 423 }
 424
 425 /* Gate: initialize or not the SSA datastructures.  */
 426
 427 static bool
 428 gate_init_datastructures (void)
 429 {
 430   return (optimize >= 1);
 431 }
 432
 433 struct tree_opt_pass pass_init_datastructures =
 434 {
 435   NULL,                                 /* name */
 436   gate_init_datastructures,             /* gate */
 437   execute_init_datastructures,          /* execute */
 438   NULL,                                 /* sub */
 439   NULL,                                 /* next */
 440   0,                                    /* static_pass_number */
 441   0,                                    /* tv_id */
 442   PROP_cfg,                             /* properties_required */
 443   0,                                    /* properties_provided */
 444   0,                                    /* properties_destroyed */
 445   0,                                    /* todo_flags_start */
 446   0,                                    /* todo_flags_finish */
 447   0                                     /* letter */
 448 };
 449
 450 void
 451 tree_lowering_passes (tree fn)
 452 {
 453   tree saved_current_function_decl = current_function_decl;
 454
 455   current_function_decl = fn;
 456   push_cfun (DECL_STRUCT_FUNCTION (fn));
 457   tree_register_cfg_hooks ();
 458   bitmap_obstack_initialize (NULL);
 459   execute_pass_list (all_lowering_passes);
 460   if (optimize && cgraph_global_info_ready)
 461     execute_pass_list (pass_early_local_passes.sub);
 462   free_dominance_info (CDI_POST_DOMINATORS);
 463   free_dominance_info (CDI_DOMINATORS);
 464   compact_blocks ();
 465   current_function_decl = saved_current_function_decl;
 466   bitmap_obstack_release (NULL);
 467   pop_cfun ();
 468 }
 469
 470 /* Update recursively all inlined_to pointers of functions
 471    inlined into NODE to INLINED_TO.  */
 472 static void
 473 update_inlined_to_pointers (struct cgraph_node *node,
 474                             struct cgraph_node *inlined_to)
 475 {
 476   struct cgraph_edge *e;
 477   for (e = node->callees; e; e = e->next_callee)
 478     {
 479       if (e->callee->global.inlined_to)
 480         {
 481           e->callee->global.inlined_to = inlined_to;
 482           update_inlined_to_pointers (e->callee, inlined_to);
 483         }
 484     }
 485 }
 486
 487 \f
 488 /* For functions-as-trees languages, this performs all optimization and
 489    compilation for FNDECL.  */
 490
 491 void
 492 tree_rest_of_compilation (tree fndecl)
 493 {
 494   location_t saved_loc;
 495   struct cgraph_node *node;
 496
 497   timevar_push (TV_EXPAND);
 498
 499   gcc_assert (!flag_unit_at_a_time || cgraph_global_info_ready);
 500
 501   node = cgraph_node (fndecl);
 502
 503   /* Initialize the default bitmap obstack.  */
 504   bitmap_obstack_initialize (NULL);
 505
 506   /* We might need the body of this function so that we can expand
 507      it inline somewhere else.  */
 508   if (cgraph_preserve_function_body_p (fndecl))
 509     save_inline_function_body (node);
 510
 511   /* Initialize the RTL code for the function.  */
 512   current_function_decl = fndecl;
 513   saved_loc = input_location;
 514   input_location = DECL_SOURCE_LOCATION (fndecl);
 515   init_function_start (fndecl);
 516
 517   /* Even though we're inside a function body, we still don't want to
 518      call expand_expr to calculate the size of a variable-sized array.
 519      We haven't necessarily assigned RTL to all variables yet, so it's
 520      not safe to try to expand expressions involving them.  */
 521   cfun->x_dont_save_pending_sizes_p = 1;
 522
 523   tree_register_cfg_hooks ();
 524
 525   if (flag_inline_trees)
 526     {
 527       struct cgraph_edge *e;
 528       for (e = node->callees; e; e = e->next_callee)
 529         if (!e->inline_failed || warn_inline)
 530           break;
 531       if (e)
 532         {
 533           timevar_push (TV_INTEGRATION);
 534           optimize_inline_calls (fndecl);
 535           timevar_pop (TV_INTEGRATION);
 536         }
 537     }
 538   /* In non-unit-at-a-time we must mark all referenced functions as needed.
 539      */
 540   if (!flag_unit_at_a_time)
 541     {
 542       struct cgraph_edge *e;
 543       for (e = node->callees; e; e = e->next_callee)
 544         if (e->callee->analyzed)
 545           cgraph_mark_needed_node (e->callee);
 546     }
 547
 548   /* We are not going to maintain the cgraph edges up to date.
 549      Kill it so it won't confuse us.  */
 550   cgraph_node_remove_callees (node);
 551
 552   bitmap_obstack_initialize (&reg_obstack); /* FIXME, only at RTL generation*/
 553   /* Perform all tree transforms and optimizations.  */
 554   execute_pass_list (all_passes);
 555
 556   bitmap_obstack_release (&reg_obstack);
 557
 558   /* Release the default bitmap obstack.  */
 559   bitmap_obstack_release (NULL);
 560
 561   DECL_SAVED_TREE (fndecl) = NULL;
 562   cfun = 0;
 563
 564   /* If requested, warn about function definitions where the function will
 565      return a value (usually of some struct or union type) which itself will
 566      take up a lot of stack space.  */
 567   if (warn_larger_than && !DECL_EXTERNAL (fndecl) && TREE_TYPE (fndecl))
 568     {
 569       tree ret_type = TREE_TYPE (TREE_TYPE (fndecl));
 570
 571       if (ret_type && TYPE_SIZE_UNIT (ret_type)
 572           && TREE_CODE (TYPE_SIZE_UNIT (ret_type)) == INTEGER_CST
 573           && 0 < compare_tree_int (TYPE_SIZE_UNIT (ret_type),
 574                                    larger_than_size))
 575         {
 576           unsigned int size_as_int
 577             = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (ret_type));
 578
 579           if (compare_tree_int (TYPE_SIZE_UNIT (ret_type), size_as_int) == 0)
 580             warning (0, "size of return value of %q+D is %u bytes",
 581                      fndecl, size_as_int);
 582           else
 583             warning (0, "size of return value of %q+D is larger than %wd bytes",
 584                      fndecl, larger_than_size);
 585         }
 586     }
 587
 588   if (!flag_inline_trees)
 589     {
 590       DECL_SAVED_TREE (fndecl) = NULL;
 591       if (DECL_STRUCT_FUNCTION (fndecl) == 0
 592           && !cgraph_node (fndecl)->origin)
 593         {
 594           /* Stop pointing to the local nodes about to be freed.
 595              But DECL_INITIAL must remain nonzero so we know this
 596              was an actual function definition.
 597              For a nested function, this is done in c_pop_function_context.
 598              If rest_of_compilation set this to 0, leave it 0.  */
 599           if (DECL_INITIAL (fndecl) != 0)
 600             DECL_INITIAL (fndecl) = error_mark_node;
 601         }
 602     }
 603
 604   input_location = saved_loc;
 605
 606   ggc_collect ();
 607   timevar_pop (TV_EXPAND);
 608 }