gcc/passes.c

   1 /* Top level of GCC compilers (cc1, cc1plus, etc.)
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 /* This is the top level of cc1/c++.
  24    It parses command args, opens files, invokes the various passes
  25    in the proper order, and counts the time used by each.
  26    Error messages and low-level interface to malloc also handled here.  */
  27
  28 #include "config.h"
  29 #undef FLOAT /* This is for hpux. They should change hpux.  */
  30 #undef FFS  /* Some systems define this in param.h.  */
  31 #include "system.h"
  32 #include "coretypes.h"
  33 #include "tm.h"
  34 #include <signal.h>
  35
  36 #ifdef HAVE_SYS_RESOURCE_H
  37 # include <sys/resource.h>
  38 #endif
  39
  40 #ifdef HAVE_SYS_TIMES_H
  41 # include <sys/times.h>
  42 #endif
  43
  44 #include "line-map.h"
  45 #include "input.h"
  46 #include "tree.h"
  47 #include "rtl.h"
  48 #include "tm_p.h"
  49 #include "flags.h"
  50 #include "insn-attr.h"
  51 #include "insn-config.h"
  52 #include "insn-flags.h"
  53 #include "hard-reg-set.h"
  54 #include "recog.h"
  55 #include "output.h"
  56 #include "except.h"
  57 #include "function.h"
  58 #include "toplev.h"
  59 #include "expr.h"
  60 #include "basic-block.h"
  61 #include "intl.h"
  62 #include "ggc.h"
  63 #include "graph.h"
  64 #include "regs.h"
  65 #include "timevar.h"
  66 #include "diagnostic.h"
  67 #include "params.h"
  68 #include "reload.h"
  69 #include "dwarf2asm.h"
  70 #include "integrate.h"
  71 #include "real.h"
  72 #include "debug.h"
  73 #include "target.h"
  74 #include "langhooks.h"
  75 #include "cfglayout.h"
  76 #include "cfgloop.h"
  77 #include "hosthooks.h"
  78 #include "cgraph.h"
  79 #include "opts.h"
  80 #include "coverage.h"
  81 #include "value-prof.h"
  82 #include "tree-inline.h"
  83 #include "tree-flow.h"
  84 #include "tree-pass.h"
  85 #include "tree-dump.h"
  86 #include "predict.h"
  87
  88 #if defined (DWARF2_UNWIND_INFO) || defined (DWARF2_DEBUGGING_INFO)
  89 #include "dwarf2out.h"
  90 #endif
  91
  92 #if defined (DBX_DEBUGGING_INFO) || defined (XCOFF_DEBUGGING_INFO)
  93 #include "dbxout.h"
  94 #endif
  95
  96 #ifdef SDB_DEBUGGING_INFO
  97 #include "sdbout.h"
  98 #endif
  99
 100 #ifdef XCOFF_DEBUGGING_INFO
 101 #include "xcoffout.h"           /* Needed for external data
 102                                    declarations for e.g. AIX 4.x.  */
 103 #endif
 104
 105 /* Global variables used to communicate with passes.  */
 106 int dump_flags;
 107 bool in_gimple_form;
 108 bool first_pass_instance;
 109
 110
 111 /* This is called from various places for FUNCTION_DECL, VAR_DECL,
 112    and TYPE_DECL nodes.
 113
 114    This does nothing for local (non-static) variables, unless the
 115    variable is a register variable with DECL_ASSEMBLER_NAME set.  In
 116    that case, or if the variable is not an automatic, it sets up the
 117    RTL and outputs any assembler code (label definition, storage
 118    allocation and initialization).
 119
 120    DECL is the declaration.  TOP_LEVEL is nonzero
 121    if this declaration is not within a function.  */
 122
 123 void
 124 rest_of_decl_compilation (tree decl,
 125                           int top_level,
 126                           int at_end)
 127 {
 128   /* We deferred calling assemble_alias so that we could collect
 129      other attributes such as visibility.  Emit the alias now.  */
 130   {
 131     tree alias;
 132     alias = lookup_attribute ("alias", DECL_ATTRIBUTES (decl));
 133     if (alias)
 134       {
 135         alias = TREE_VALUE (TREE_VALUE (alias));
 136         alias = get_identifier (TREE_STRING_POINTER (alias));
 137         assemble_alias (decl, alias);
 138       }
 139   }
 140
 141   /* Can't defer this, because it needs to happen before any
 142      later function definitions are processed.  */
 143   if (DECL_ASSEMBLER_NAME_SET_P (decl) && DECL_REGISTER (decl))
 144     make_decl_rtl (decl);
 145
 146   /* Forward declarations for nested functions are not "external",
 147      but we need to treat them as if they were.  */
 148   if (TREE_STATIC (decl) || DECL_EXTERNAL (decl)
 149       || TREE_CODE (decl) == FUNCTION_DECL)
 150     {
 151       timevar_push (TV_VARCONST);
 152
 153       /* Don't output anything when a tentative file-scope definition
 154          is seen.  But at end of compilation, do output code for them.
 155
 156          We do output all variables when unit-at-a-time is active and rely on
 157          callgraph code to defer them except for forward declarations
 158          (see gcc.c-torture/compile/920624-1.c) */
 159       if ((at_end
 160            || !DECL_DEFER_OUTPUT (decl)
 161            || DECL_INITIAL (decl))
 162           && !DECL_EXTERNAL (decl))
 163         {
 164           if (TREE_CODE (decl) != FUNCTION_DECL)
 165             varpool_finalize_decl (decl);
 166           else
 167             assemble_variable (decl, top_level, at_end, 0);
 168         }
 169
 170 #ifdef ASM_FINISH_DECLARE_OBJECT
 171       if (decl == last_assemble_variable_decl)
 172         {
 173           ASM_FINISH_DECLARE_OBJECT (asm_out_file, decl,
 174                                      top_level, at_end);
 175         }
 176 #endif
 177
 178       timevar_pop (TV_VARCONST);
 179     }
 180   else if (TREE_CODE (decl) == TYPE_DECL
 181            /* Like in rest_of_type_compilation, avoid confusing the debug
 182               information machinery when there are errors.  */
 183            && !(sorrycount || errorcount))
 184     {
 185       timevar_push (TV_SYMOUT);
 186       debug_hooks->type_decl (decl, !top_level);
 187       timevar_pop (TV_SYMOUT);
 188     }
 189
 190   /* Let cgraph know about the existence of variables.  */
 191   if (TREE_CODE (decl) == VAR_DECL && !DECL_EXTERNAL (decl))
 192     varpool_node (decl);
 193 }
 194
 195 /* Called after finishing a record, union or enumeral type.  */
 196
 197 void
 198 rest_of_type_compilation (tree type, int toplev)
 199 {
 200   /* Avoid confusing the debug information machinery when there are
 201      errors.  */
 202   if (errorcount != 0 || sorrycount != 0)
 203     return;
 204
 205   timevar_push (TV_SYMOUT);
 206   debug_hooks->type_decl (TYPE_STUB_DECL (type), !toplev);
 207   timevar_pop (TV_SYMOUT);
 208 }
 209
 210 \f
 211
 212 void
 213 finish_optimization_passes (void)
 214 {
 215   enum tree_dump_index i;
 216   struct dump_file_info *dfi;
 217   char *name;
 218
 219   timevar_push (TV_DUMP);
 220   if (profile_arc_flag || flag_test_coverage || flag_branch_probabilities)
 221     {
 222       dump_file = dump_begin (pass_profile.static_pass_number, NULL);
 223       end_branch_prob ();
 224       if (dump_file)
 225         dump_end (pass_profile.static_pass_number, dump_file);
 226     }
 227
 228   if (optimize > 0)
 229     {
 230       dump_file = dump_begin (pass_combine.static_pass_number, NULL);
 231       if (dump_file)
 232         {
 233           dump_combine_total_stats (dump_file);
 234           dump_end (pass_combine.static_pass_number, dump_file);
 235         }
 236     }
 237
 238   /* Do whatever is necessary to finish printing the graphs.  */
 239   if (graph_dump_format != no_graph)
 240     for (i = TDI_end; (dfi = get_dump_file_info (i)) != NULL; ++i)
 241       if (dump_initialized_p (i)
 242           && (dfi->flags & TDF_GRAPH) != 0
 243           && (name = get_dump_file_name (i)) != NULL)
 244         {
 245           finish_graph_dump_file (name);
 246           free (name);
 247         }
 248
 249   timevar_pop (TV_DUMP);
 250 }
 251
 252 static bool
 253 gate_rest_of_compilation (void)
 254 {
 255   /* Early return if there were errors.  We can run afoul of our
 256      consistency checks, and there's not really much point in fixing them.  */
 257   return !(rtl_dump_and_exit || flag_syntax_only || errorcount || sorrycount);
 258 }
 259
 260 struct tree_opt_pass pass_rest_of_compilation =
 261 {
 262   NULL,                                 /* name */
 263   gate_rest_of_compilation,             /* gate */
 264   NULL,                                 /* execute */
 265   NULL,                                 /* sub */
 266   NULL,                                 /* next */
 267   0,                                    /* static_pass_number */
 268   TV_REST_OF_COMPILATION,               /* tv_id */
 269   PROP_rtl,                             /* properties_required */
 270   0,                                    /* properties_provided */
 271   0,                                    /* properties_destroyed */
 272   0,                                    /* todo_flags_start */
 273   TODO_ggc_collect,                     /* todo_flags_finish */
 274   0                                     /* letter */
 275 };
 276
 277 static bool
 278 gate_postreload (void)
 279 {
 280   return reload_completed;
 281 }
 282
 283 struct tree_opt_pass pass_postreload =
 284 {
 285   NULL,                                 /* name */
 286   gate_postreload,                      /* gate */
 287   NULL,                                 /* execute */
 288   NULL,                                 /* sub */
 289   NULL,                                 /* next */
 290   0,                                    /* static_pass_number */
 291   0,                                    /* tv_id */
 292   PROP_rtl,                             /* properties_required */
 293   0,                                    /* properties_provided */
 294   0,                                    /* properties_destroyed */
 295   0,                                    /* todo_flags_start */
 296   TODO_ggc_collect,                     /* todo_flags_finish */
 297   0                                     /* letter */
 298 };
 299
 300
 301
 302 /* The root of the compilation pass tree, once constructed.  */
 303 struct tree_opt_pass *all_passes, *all_ipa_passes, *all_lowering_passes;
 304
 305 /* Iterate over the pass tree allocating dump file numbers.  We want
 306    to do this depth first, and independent of whether the pass is
 307    enabled or not.  */
 308
 309 static void
 310 register_one_dump_file (struct tree_opt_pass *pass, bool ipa, int properties)
 311 {
 312   char *dot_name, *flag_name, *glob_name;
 313   const char *prefix;
 314   char num[10];
 315   int flags;
 316
 317   /* See below in next_pass_1.  */
 318   num[0] = '\0';
 319   if (pass->static_pass_number != -1)
 320     sprintf (num, "%d", ((int) pass->static_pass_number < 0
 321                          ? 1 : pass->static_pass_number));
 322
 323   dot_name = concat (".", pass->name, num, NULL);
 324   if (ipa)
 325     prefix = "ipa-", flags = TDF_IPA;
 326   else if (properties & PROP_trees)
 327     prefix = "tree-", flags = TDF_TREE;
 328   else
 329     prefix = "rtl-", flags = TDF_RTL;
 330
 331   flag_name = concat (prefix, pass->name, num, NULL);
 332   glob_name = concat (prefix, pass->name, NULL);
 333   pass->static_pass_number = dump_register (dot_name, flag_name, glob_name,
 334                                             flags, pass->letter);
 335 }
 336
 337 /* Recursive worker function for register_dump_files.  */
 338
 339 static int
 340 register_dump_files_1 (struct tree_opt_pass *pass, bool ipa, int properties)
 341 {
 342   do
 343     {
 344       int new_properties = (properties | pass->properties_provided)
 345                            & ~pass->properties_destroyed;
 346
 347       if (pass->name)
 348         register_one_dump_file (pass, ipa, new_properties);
 349
 350       if (pass->sub)
 351         new_properties = register_dump_files_1 (pass->sub, false,
 352                                                 new_properties);
 353
 354       /* If we have a gate, combine the properties that we could have with
 355          and without the pass being examined.  */
 356       if (pass->gate)
 357         properties &= new_properties;
 358       else
 359         properties = new_properties;
 360
 361       pass = pass->next;
 362     }
 363   while (pass);
 364
 365   return properties;
 366 }
 367
 368 /* Register the dump files for the pipeline starting at PASS.  IPA is
 369    true if the pass is inter-procedural, and PROPERTIES reflects the
 370    properties that are guaranteed to be available at the beginning of
 371    the pipeline.  */
 372
 373 static void
 374 register_dump_files (struct tree_opt_pass *pass, bool ipa, int properties)
 375 {
 376   pass->properties_required |= properties;
 377   register_dump_files_1 (pass, ipa, properties);
 378 }
 379
 380 /* Add a pass to the pass list. Duplicate the pass if it's already
 381    in the list.  */
 382
 383 static struct tree_opt_pass **
 384 next_pass_1 (struct tree_opt_pass **list, struct tree_opt_pass *pass)
 385 {
 386   /* A nonzero static_pass_number indicates that the
 387      pass is already in the list.  */
 388   if (pass->static_pass_number)
 389     {
 390       struct tree_opt_pass *new;
 391
 392       new = xmalloc (sizeof (*new));
 393       memcpy (new, pass, sizeof (*new));
 394       new->next = NULL;
 395
 396       new->todo_flags_start &= ~TODO_mark_first_instance;
 397
 398       /* Indicate to register_dump_files that this pass has duplicates,
 399          and so it should rename the dump file.  The first instance will
 400          be -1, and be number of duplicates = -static_pass_number - 1.
 401          Subsequent instances will be > 0 and just the duplicate number.  */
 402       if (pass->name)
 403         {
 404           pass->static_pass_number -= 1;
 405           new->static_pass_number = -pass->static_pass_number;
 406         }
 407
 408       *list = new;
 409     }
 410   else
 411     {
 412       pass->todo_flags_start |= TODO_mark_first_instance;
 413       pass->static_pass_number = -1;
 414       *list = pass;
 415     }
 416
 417   return &(*list)->next;
 418
 419 }
 420
 421 /* Construct the pass tree.  The sequencing of passes is driven by
 422    the cgraph routines:
 423
 424    cgraph_finalize_compilation_unit ()
 425        for each node N in the cgraph
 426            cgraph_analyze_function (N)
 427                cgraph_lower_function (N) -> all_lowering_passes
 428
 429    If we are optimizing, cgraph_optimize is then invoked:
 430
 431    cgraph_optimize ()
 432        ipa_passes ()                    -> all_ipa_passes
 433        cgraph_expand_all_functions ()
 434            for each node N in the cgraph
 435                cgraph_expand_function (N)
 436                    lang_hooks.callgraph.expand_function (DECL (N))
 437                         tree_rest_of_compilation (DECL (N))  -> all_passes
 438 */
 439
 440 void
 441 init_optimization_passes (void)
 442 {
 443   struct tree_opt_pass **p;
 444
 445 #define NEXT_PASS(PASS)  (p = next_pass_1 (p, &PASS))
 446
 447  /* All passes needed to lower the function into shape optimizers can
 448     operate on.  These passes are always run first on the function, but
 449     backend might produce already lowered functions that are not processed
 450     by these passes.  */
 451   p = &all_lowering_passes;
 452   NEXT_PASS (pass_remove_useless_stmts);
 453   NEXT_PASS (pass_mudflap_1);
 454   NEXT_PASS (pass_lower_omp);
 455   NEXT_PASS (pass_lower_cf);
 456   NEXT_PASS (pass_lower_eh);
 457   NEXT_PASS (pass_build_cfg);
 458   NEXT_PASS (pass_lower_complex_O0);
 459   NEXT_PASS (pass_lower_vector);
 460   NEXT_PASS (pass_warn_function_return);
 461   NEXT_PASS (pass_build_cgraph_edges);
 462   NEXT_PASS (pass_inline_parameters);
 463   *p = NULL;
 464
 465   /* Interprocedural optimization passes.
 466      All these passes are ignored in -fno-unit-at-a-time
 467      except for subpasses of early_local_passes.  */
 468   p = &all_ipa_passes;
 469   NEXT_PASS (pass_ipa_function_and_variable_visibility);
 470   NEXT_PASS (pass_ipa_early_inline);
 471     {
 472       struct tree_opt_pass **p = &pass_ipa_early_inline.sub;
 473       NEXT_PASS (pass_early_inline);
 474       NEXT_PASS (pass_inline_parameters);
 475       NEXT_PASS (pass_rebuild_cgraph_edges);
 476     }
 477   NEXT_PASS (pass_early_local_passes);
 478     {
 479       struct tree_opt_pass **p = &pass_early_local_passes.sub;
 480       NEXT_PASS (pass_tree_profile);
 481       NEXT_PASS (pass_cleanup_cfg);
 482       NEXT_PASS (pass_init_datastructures);
 483       NEXT_PASS (pass_expand_omp);
 484       NEXT_PASS (pass_all_early_optimizations);
 485         {
 486           struct tree_opt_pass **p = &pass_all_early_optimizations.sub;
 487           NEXT_PASS (pass_referenced_vars);
 488           NEXT_PASS (pass_reset_cc_flags);
 489           NEXT_PASS (pass_build_ssa);
 490           NEXT_PASS (pass_early_warn_uninitialized);
 491           NEXT_PASS (pass_rebuild_cgraph_edges);
 492           NEXT_PASS (pass_early_inline);
 493           NEXT_PASS (pass_cleanup_cfg);
 494           NEXT_PASS (pass_rename_ssa_copies);
 495           NEXT_PASS (pass_ccp);
 496           NEXT_PASS (pass_forwprop);
 497           NEXT_PASS (pass_sra_early);
 498           NEXT_PASS (pass_copy_prop);
 499           NEXT_PASS (pass_merge_phi);
 500           NEXT_PASS (pass_dce);
 501           NEXT_PASS (pass_tail_recursion);
 502           NEXT_PASS (pass_profile);
 503           NEXT_PASS (pass_release_ssa_names);
 504         }
 505       NEXT_PASS (pass_rebuild_cgraph_edges);
 506       NEXT_PASS (pass_inline_parameters);
 507     }
 508   NEXT_PASS (pass_ipa_increase_alignment);
 509   NEXT_PASS (pass_ipa_cp);
 510   NEXT_PASS (pass_ipa_inline);
 511   NEXT_PASS (pass_ipa_reference);
 512   NEXT_PASS (pass_ipa_pure_const);
 513   NEXT_PASS (pass_ipa_type_escape);
 514   NEXT_PASS (pass_ipa_pta);
 515   *p = NULL;
 516
 517   /* These passes are run after IPA passes on every function that is being
 518      output to the assembler file.  */
 519   p = &all_passes;
 520   NEXT_PASS (pass_apply_inline);
 521   NEXT_PASS (pass_all_optimizations);
 522     {
 523       struct tree_opt_pass **p = &pass_all_optimizations.sub;
 524       NEXT_PASS (pass_create_structure_vars);
 525       NEXT_PASS (pass_may_alias);
 526       NEXT_PASS (pass_return_slot);
 527       NEXT_PASS (pass_rename_ssa_copies);
 528
 529       /* Initial scalar cleanups.  */
 530       NEXT_PASS (pass_ccp);
 531       NEXT_PASS (pass_phiprop);
 532       NEXT_PASS (pass_fre);
 533       NEXT_PASS (pass_dce);
 534       NEXT_PASS (pass_forwprop);
 535       NEXT_PASS (pass_copy_prop);
 536       NEXT_PASS (pass_merge_phi);
 537       NEXT_PASS (pass_vrp);
 538       NEXT_PASS (pass_dce);
 539       NEXT_PASS (pass_dominator);
 540
 541       /* The only const/copy propagation opportunities left after
 542          DOM should be due to degenerate PHI nodes.  So rather than
 543          run the full propagators, run a specialized pass which
 544          only examines PHIs to discover const/copy propagation
 545          opportunities.  */
 546       NEXT_PASS (pass_phi_only_cprop);
 547
 548       NEXT_PASS (pass_phiopt);
 549       NEXT_PASS (pass_may_alias);
 550       NEXT_PASS (pass_tail_recursion);
 551       NEXT_PASS (pass_ch);
 552       NEXT_PASS (pass_stdarg);
 553       NEXT_PASS (pass_lower_complex);
 554       NEXT_PASS (pass_sra);
 555       /* FIXME: SRA may generate arbitrary gimple code, exposing new
 556          aliased and call-clobbered variables.  As mentioned below,
 557          pass_may_alias should be a TODO item.  */
 558       NEXT_PASS (pass_may_alias);
 559       NEXT_PASS (pass_rename_ssa_copies);
 560       NEXT_PASS (pass_dominator);
 561
 562       /* The only const/copy propagation opportunities left after
 563          DOM should be due to degenerate PHI nodes.  So rather than
 564          run the full propagators, run a specialized pass which
 565          only examines PHIs to discover const/copy propagation
 566          opportunities.  */
 567       NEXT_PASS (pass_phi_only_cprop);
 568
 569       NEXT_PASS (pass_reassoc);
 570       NEXT_PASS (pass_dce);
 571       NEXT_PASS (pass_dse);
 572       NEXT_PASS (pass_may_alias);
 573       NEXT_PASS (pass_forwprop);
 574       NEXT_PASS (pass_phiopt);
 575       NEXT_PASS (pass_object_sizes);
 576       NEXT_PASS (pass_store_ccp);
 577       NEXT_PASS (pass_store_copy_prop);
 578       NEXT_PASS (pass_fold_builtins);
 579       NEXT_PASS (pass_cse_sincos);
 580       /* FIXME: May alias should a TODO but for 4.0.0,
 581          we add may_alias right after fold builtins
 582          which can create arbitrary GIMPLE.  */
 583       NEXT_PASS (pass_may_alias);
 584       NEXT_PASS (pass_split_crit_edges);
 585       NEXT_PASS (pass_pre);
 586       NEXT_PASS (pass_may_alias);
 587       NEXT_PASS (pass_sink_code);
 588       NEXT_PASS (pass_tree_loop);
 589         {
 590           struct tree_opt_pass **p = &pass_tree_loop.sub;
 591           NEXT_PASS (pass_tree_loop_init);
 592           NEXT_PASS (pass_copy_prop);
 593           NEXT_PASS (pass_lim);
 594           NEXT_PASS (pass_tree_unswitch);
 595           NEXT_PASS (pass_scev_cprop);
 596           NEXT_PASS (pass_empty_loop);
 597           NEXT_PASS (pass_record_bounds);
 598           NEXT_PASS (pass_check_data_deps);
 599           NEXT_PASS (pass_linear_transform);
 600           NEXT_PASS (pass_iv_canon);
 601           NEXT_PASS (pass_if_conversion);
 602           NEXT_PASS (pass_vectorize);
 603             {
 604               struct tree_opt_pass **p = &pass_vectorize.sub;
 605               NEXT_PASS (pass_lower_vector_ssa);
 606               NEXT_PASS (pass_dce_loop);
 607             }
 608           /* NEXT_PASS (pass_may_alias) cannot be done again because the
 609              vectorizer creates alias relations that are not supported by
 610              pass_may_alias.  */
 611           NEXT_PASS (pass_complete_unroll);
 612           NEXT_PASS (pass_loop_prefetch);
 613           NEXT_PASS (pass_iv_optimize);
 614           NEXT_PASS (pass_tree_loop_done);
 615         }
 616       NEXT_PASS (pass_cse_reciprocals);
 617       NEXT_PASS (pass_reassoc);
 618       NEXT_PASS (pass_vrp);
 619       NEXT_PASS (pass_dominator);
 620
 621       /* The only const/copy propagation opportunities left after
 622          DOM should be due to degenerate PHI nodes.  So rather than
 623          run the full propagators, run a specialized pass which
 624          only examines PHIs to discover const/copy propagation
 625          opportunities.  */
 626       NEXT_PASS (pass_phi_only_cprop);
 627
 628       NEXT_PASS (pass_cd_dce);
 629
 630       /* FIXME: If DCE is not run before checking for uninitialized uses,
 631          we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c).
 632          However, this also causes us to misdiagnose cases that should be
 633          real warnings (e.g., testsuite/gcc.dg/pr18501.c).
 634
 635          To fix the false positives in uninit-5.c, we would have to
 636          account for the predicates protecting the set and the use of each
 637          variable.  Using a representation like Gated Single Assignment
 638          may help.  */
 639       NEXT_PASS (pass_late_warn_uninitialized);
 640       NEXT_PASS (pass_dse);
 641       NEXT_PASS (pass_forwprop);
 642       NEXT_PASS (pass_phiopt);
 643       NEXT_PASS (pass_tail_calls);
 644       NEXT_PASS (pass_rename_ssa_copies);
 645       NEXT_PASS (pass_uncprop);
 646       NEXT_PASS (pass_del_ssa);
 647       NEXT_PASS (pass_nrv);
 648       NEXT_PASS (pass_mark_used_blocks);
 649       NEXT_PASS (pass_cleanup_cfg_post_optimizing);
 650     }
 651   NEXT_PASS (pass_warn_function_noreturn);
 652   NEXT_PASS (pass_free_datastructures);
 653   NEXT_PASS (pass_mudflap_2);
 654   NEXT_PASS (pass_free_cfg_annotations);
 655   NEXT_PASS (pass_expand);
 656   NEXT_PASS (pass_rest_of_compilation);
 657     {
 658       struct tree_opt_pass **p = &pass_rest_of_compilation.sub;
 659       NEXT_PASS (pass_init_function);
 660       NEXT_PASS (pass_jump);
 661       NEXT_PASS (pass_rtl_eh);
 662       NEXT_PASS (pass_initial_value_sets);
 663       NEXT_PASS (pass_unshare_all_rtl);
 664       NEXT_PASS (pass_instantiate_virtual_regs);
 665       NEXT_PASS (pass_into_cfg_layout_mode);
 666       NEXT_PASS (pass_jump2);
 667       NEXT_PASS (pass_lower_subreg);
 668       NEXT_PASS (pass_cse);
 669       NEXT_PASS (pass_rtl_fwprop);
 670       NEXT_PASS (pass_gcse);
 671       NEXT_PASS (pass_rtl_ifcvt);
 672       NEXT_PASS (pass_tracer);
 673       /* Perform loop optimizations.  It might be better to do them a bit
 674          sooner, but we want the profile feedback to work more
 675          efficiently.  */
 676       NEXT_PASS (pass_loop2);
 677         {
 678           struct tree_opt_pass **p = &pass_loop2.sub;
 679           NEXT_PASS (pass_rtl_loop_init);
 680           NEXT_PASS (pass_rtl_move_loop_invariants);
 681           NEXT_PASS (pass_rtl_unswitch);
 682           NEXT_PASS (pass_rtl_unroll_and_peel_loops);
 683           NEXT_PASS (pass_rtl_doloop);
 684           NEXT_PASS (pass_rtl_loop_done);
 685           *p = NULL;
 686         }
 687       NEXT_PASS (pass_web);
 688       NEXT_PASS (pass_jump_bypass);
 689       NEXT_PASS (pass_cse2);
 690       NEXT_PASS (pass_rtl_fwprop_addr);
 691       NEXT_PASS (pass_outof_cfg_layout_mode);
 692       NEXT_PASS (pass_life);
 693       NEXT_PASS (pass_combine);
 694       NEXT_PASS (pass_if_after_combine);
 695       NEXT_PASS (pass_partition_blocks);
 696       NEXT_PASS (pass_regmove);
 697       NEXT_PASS (pass_split_all_insns);
 698       NEXT_PASS (pass_lower_subreg2);
 699       NEXT_PASS (pass_mode_switching);
 700       NEXT_PASS (pass_see);
 701       NEXT_PASS (pass_recompute_reg_usage);
 702       NEXT_PASS (pass_sms);
 703       NEXT_PASS (pass_sched);
 704       NEXT_PASS (pass_local_alloc);
 705       NEXT_PASS (pass_global_alloc);
 706       NEXT_PASS (pass_postreload);
 707         {
 708           struct tree_opt_pass **p = &pass_postreload.sub;
 709           NEXT_PASS (pass_postreload_cse);
 710           NEXT_PASS (pass_gcse2);
 711           NEXT_PASS (pass_flow2);
 712           NEXT_PASS (pass_rtl_seqabstr);
 713           NEXT_PASS (pass_stack_adjustments);
 714           NEXT_PASS (pass_peephole2);
 715           NEXT_PASS (pass_if_after_reload);
 716           NEXT_PASS (pass_regrename);
 717           NEXT_PASS (pass_reorder_blocks);
 718           NEXT_PASS (pass_branch_target_load_optimize);
 719           NEXT_PASS (pass_leaf_regs);
 720           NEXT_PASS (pass_sched2);
 721           NEXT_PASS (pass_split_before_regstack);
 722           NEXT_PASS (pass_stack_regs);
 723           NEXT_PASS (pass_compute_alignments);
 724           NEXT_PASS (pass_duplicate_computed_gotos);
 725           NEXT_PASS (pass_variable_tracking);
 726           NEXT_PASS (pass_free_cfg);
 727           NEXT_PASS (pass_machine_reorg);
 728           NEXT_PASS (pass_cleanup_barriers);
 729           NEXT_PASS (pass_delay_slots);
 730           NEXT_PASS (pass_split_for_shorten_branches);
 731           NEXT_PASS (pass_convert_to_eh_region_ranges);
 732           NEXT_PASS (pass_shorten_branches);
 733           NEXT_PASS (pass_set_nothrow_function_flags);
 734           NEXT_PASS (pass_final);
 735         }
 736     }
 737   NEXT_PASS (pass_clean_state);
 738   *p = NULL;
 739
 740 #undef NEXT_PASS
 741
 742   /* Register the passes with the tree dump code.  */
 743   register_dump_files (all_lowering_passes, false, PROP_gimple_any);
 744   all_lowering_passes->todo_flags_start |= TODO_set_props;
 745   register_dump_files (all_ipa_passes, true,
 746                        PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh
 747                        | PROP_cfg);
 748   register_dump_files (all_passes, false,
 749                        PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh
 750                        | PROP_cfg);
 751 }
 752
 753 /* If we are in IPA mode (i.e., current_function_decl is NULL), call
 754    function CALLBACK for every function in the call graph.  Otherwise,
 755    call CALLBACK on the current function.  */
 756
 757 static void
 758 do_per_function (void (*callback) (void *data), void *data)
 759 {
 760   if (current_function_decl)
 761     callback (data);
 762   else
 763     {
 764       struct cgraph_node *node;
 765       for (node = cgraph_nodes; node; node = node->next)
 766         if (node->analyzed)
 767           {
 768             push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 769             current_function_decl = node->decl;
 770             callback (data);
 771             free_dominance_info (CDI_DOMINATORS);
 772             free_dominance_info (CDI_POST_DOMINATORS);
 773             current_function_decl = NULL;
 774             pop_cfun ();
 775             ggc_collect ();
 776           }
 777     }
 778 }
 779
 780 /* Because inlining might remove no-longer reachable nodes, we need to
 781    keep the array visible to garbage collector to avoid reading collected
 782    out nodes.  */
 783 static int nnodes;
 784 static GTY ((length ("nnodes"))) struct cgraph_node **order;
 785
 786 /* If we are in IPA mode (i.e., current_function_decl is NULL), call
 787    function CALLBACK for every function in the call graph.  Otherwise,
 788    call CALLBACK on the current function.  */
 789
 790 static void
 791 do_per_function_toporder (void (*callback) (void *data), void *data)
 792 {
 793   int i;
 794
 795   if (current_function_decl)
 796     callback (data);
 797   else
 798     {
 799       gcc_assert (!order);
 800       order = ggc_alloc (sizeof (*order) * cgraph_n_nodes);
 801       nnodes = cgraph_postorder (order);
 802       for (i = nnodes - 1; i >= 0; i--)
 803         {
 804           struct cgraph_node *node = order[i];
 805
 806           /* Allow possibly removed nodes to be garbage collected.  */
 807           order[i] = NULL;
 808           if (node->analyzed && (node->needed || node->reachable))
 809             {
 810               push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 811               current_function_decl = node->decl;
 812               callback (data);
 813               free_dominance_info (CDI_DOMINATORS);
 814               free_dominance_info (CDI_POST_DOMINATORS);
 815               current_function_decl = NULL;
 816               pop_cfun ();
 817               ggc_collect ();
 818             }
 819         }
 820     }
 821   ggc_free (order);
 822   order = NULL;
 823   nnodes = 0;
 824 }
 825
 826 /* Perform all TODO actions that ought to be done on each function.  */
 827
 828 static void
 829 execute_function_todo (void *data)
 830 {
 831   unsigned int flags = (size_t)data;
 832   if (cfun->curr_properties & PROP_ssa)
 833     flags |= TODO_verify_ssa;
 834   flags &= ~cfun->last_verified;
 835   if (!flags)
 836     return;
 837
 838   /* Always cleanup the CFG before trying to update SSA.  */
 839   if (flags & TODO_cleanup_cfg)
 840     {
 841       bool cleanup;
 842
 843       if (current_loops)
 844         cleanup = cleanup_tree_cfg_loop ();
 845       else
 846         cleanup = cleanup_tree_cfg ();
 847
 848       if (cleanup && (cfun->curr_properties & PROP_ssa))
 849         flags |= TODO_remove_unused_locals;
 850
 851       /* When cleanup_tree_cfg merges consecutive blocks, it may
 852          perform some simplistic propagation when removing single
 853          valued PHI nodes.  This propagation may, in turn, cause the
 854          SSA form to become out-of-date (see PR 22037).  So, even
 855          if the parent pass had not scheduled an SSA update, we may
 856          still need to do one.  */
 857       if (!(flags & TODO_update_ssa_any) && need_ssa_update_p ())
 858         flags |= TODO_update_ssa;
 859     }
 860
 861   if (flags & TODO_update_ssa_any)
 862     {
 863       unsigned update_flags = flags & TODO_update_ssa_any;
 864       update_ssa (update_flags);
 865       cfun->last_verified &= ~TODO_verify_ssa;
 866     }
 867
 868   if (flags & TODO_remove_unused_locals)
 869     remove_unused_locals ();
 870
 871   if ((flags & TODO_dump_func)
 872       && dump_file && current_function_decl)
 873     {
 874       if (cfun->curr_properties & PROP_trees)
 875         dump_function_to_file (current_function_decl,
 876                                dump_file, dump_flags);
 877       else
 878         {
 879           if (dump_flags & TDF_SLIM)
 880             print_rtl_slim_with_bb (dump_file, get_insns (), dump_flags);
 881           else if ((cfun->curr_properties & PROP_cfg)
 882                    && (dump_flags & TDF_BLOCKS))
 883             print_rtl_with_bb (dump_file, get_insns ());
 884           else
 885             print_rtl (dump_file, get_insns ());
 886
 887           if (cfun->curr_properties & PROP_cfg
 888               && graph_dump_format != no_graph
 889               && (dump_flags & TDF_GRAPH))
 890             print_rtl_graph_with_bb (dump_file_name, get_insns ());
 891         }
 892
 893       /* Flush the file.  If verification fails, we won't be able to
 894          close the file before aborting.  */
 895       fflush (dump_file);
 896     }
 897
 898   if (flags & TODO_rebuild_frequencies)
 899     {
 900       if (profile_status == PROFILE_GUESSED)
 901         {
 902           loop_optimizer_init (0);
 903           add_noreturn_fake_exit_edges ();
 904           mark_irreducible_loops ();
 905           connect_infinite_loops_to_exit ();
 906           estimate_bb_frequencies ();
 907           remove_fake_exit_edges ();
 908           loop_optimizer_finalize ();
 909         }
 910       else if (profile_status == PROFILE_READ)
 911         counts_to_freqs ();
 912       else
 913         gcc_unreachable ();
 914     }
 915
 916 #if defined ENABLE_CHECKING
 917   if (flags & TODO_verify_ssa)
 918     verify_ssa (true);
 919   if (flags & TODO_verify_flow)
 920     verify_flow_info ();
 921   if (flags & TODO_verify_stmts)
 922     verify_stmts ();
 923   if (flags & TODO_verify_loops)
 924     verify_loop_closed_ssa ();
 925 #endif
 926
 927   cfun->last_verified = flags & TODO_verify_all;
 928 }
 929
 930 /* Perform all TODO actions.  */
 931 static void
 932 execute_todo (unsigned int flags)
 933 {
 934 #if defined ENABLE_CHECKING
 935   if (need_ssa_update_p ())
 936     gcc_assert (flags & TODO_update_ssa_any);
 937 #endif
 938
 939   /* Inform the pass whether it is the first time it is run.  */
 940   first_pass_instance = (flags & TODO_mark_first_instance) != 0;
 941
 942   do_per_function (execute_function_todo, (void *)(size_t) flags);
 943
 944   /* Always remove functions just as before inlining: IPA passes might be
 945      interested to see bodies of extern inline functions that are not inlined
 946      to analyze side effects.  The full removal is done just at the end
 947      of IPA pass queue.  */
 948   if (flags & TODO_remove_functions)
 949     cgraph_remove_unreachable_nodes (true, dump_file);
 950
 951   if ((flags & TODO_dump_cgraph)
 952       && dump_file && !current_function_decl)
 953     {
 954       dump_cgraph (dump_file);
 955       /* Flush the file.  If verification fails, we won't be able to
 956          close the file before aborting.  */
 957       fflush (dump_file);
 958     }
 959
 960   if (flags & TODO_ggc_collect)
 961     {
 962       ggc_collect ();
 963     }
 964 }
 965
 966 /* Verify invariants that should hold between passes.  This is a place
 967    to put simple sanity checks.  */
 968
 969 static void
 970 verify_interpass_invariants (void)
 971 {
 972 #ifdef ENABLE_CHECKING
 973   gcc_assert (!fold_deferring_overflow_warnings_p ());
 974 #endif
 975 }
 976
 977 /* Clear the last verified flag.  */
 978
 979 static void
 980 clear_last_verified (void *data ATTRIBUTE_UNUSED)
 981 {
 982   cfun->last_verified = 0;
 983 }
 984
 985 /* Helper function. Verify that the properties has been turn into the
 986    properties expected by the pass.  */
 987
 988 #ifdef ENABLE_CHECKING
 989 static void
 990 verify_curr_properties (void *data)
 991 {
 992   unsigned int props = (size_t)data;
 993   gcc_assert ((cfun->curr_properties & props) == props);
 994 }
 995 #endif
 996
 997 /* After executing the pass, apply expected changes to the function
 998    properties. */
 999 static void
1000 update_properties_after_pass (void *data)
1001 {
1002   struct tree_opt_pass *pass = data;
1003   cfun->curr_properties = (cfun->curr_properties | pass->properties_provided)
1004                            & ~pass->properties_destroyed;
1005 }
1006
1007 static bool
1008 execute_one_pass (struct tree_opt_pass *pass)
1009 {
1010   bool initializing_dump;
1011   unsigned int todo_after = 0;
1012
1013   /* See if we're supposed to run this pass.  */
1014   if (pass->gate && !pass->gate ())
1015     return false;
1016
1017   if (!quiet_flag && !cfun)
1018     fprintf (stderr, " <%s>", pass->name ? pass->name : "");
1019
1020   if (pass->todo_flags_start & TODO_set_props)
1021     cfun->curr_properties = pass->properties_required;
1022
1023   /* Note that the folders should only create gimple expressions.
1024      This is a hack until the new folder is ready.  */
1025   in_gimple_form = (cfun && (cfun->curr_properties & PROP_trees)) != 0;
1026
1027   /* Run pre-pass verification.  */
1028   execute_todo (pass->todo_flags_start);
1029
1030 #ifdef ENABLE_CHECKING
1031   do_per_function (verify_curr_properties,
1032                    (void *)(size_t)pass->properties_required);
1033 #endif
1034
1035   /* If a dump file name is present, open it if enabled.  */
1036   if (pass->static_pass_number != -1)
1037     {
1038       initializing_dump = !dump_initialized_p (pass->static_pass_number);
1039       dump_file_name = get_dump_file_name (pass->static_pass_number);
1040       dump_file = dump_begin (pass->static_pass_number, &dump_flags);
1041       if (dump_file && current_function_decl)
1042         {
1043           const char *dname, *aname;
1044           dname = lang_hooks.decl_printable_name (current_function_decl, 2);
1045           aname = (IDENTIFIER_POINTER
1046                    (DECL_ASSEMBLER_NAME (current_function_decl)));
1047           fprintf (dump_file, "\n;; Function %s (%s)%s\n\n", dname, aname,
1048              cfun->function_frequency == FUNCTION_FREQUENCY_HOT
1049              ? " (hot)"
1050              : cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
1051              ? " (unlikely executed)"
1052              : "");
1053         }
1054     }
1055   else
1056     initializing_dump = false;
1057
1058   /* If a timevar is present, start it.  */
1059   if (pass->tv_id)
1060     timevar_push (pass->tv_id);
1061
1062   /* Do it!  */
1063   if (pass->execute)
1064     {
1065       todo_after = pass->execute ();
1066       do_per_function (clear_last_verified, NULL);
1067     }
1068
1069   /* Stop timevar.  */
1070   if (pass->tv_id)
1071     timevar_pop (pass->tv_id);
1072
1073   do_per_function (update_properties_after_pass, pass);
1074
1075   if (initializing_dump
1076       && dump_file
1077       && graph_dump_format != no_graph
1078       && (cfun->curr_properties & (PROP_cfg | PROP_rtl))
1079           == (PROP_cfg | PROP_rtl))
1080     {
1081       get_dump_file_info (pass->static_pass_number)->flags |= TDF_GRAPH;
1082       dump_flags |= TDF_GRAPH;
1083       clean_graph_dump_file (dump_file_name);
1084     }
1085
1086   /* Run post-pass cleanup and verification.  */
1087   execute_todo (todo_after | pass->todo_flags_finish);
1088   verify_interpass_invariants ();
1089
1090   if (!current_function_decl)
1091     cgraph_process_new_functions ();
1092
1093   /* Flush and close dump file.  */
1094   if (dump_file_name)
1095     {
1096       free ((char *) dump_file_name);
1097       dump_file_name = NULL;
1098     }
1099
1100   if (dump_file)
1101     {
1102       dump_end (pass->static_pass_number, dump_file);
1103       dump_file = NULL;
1104     }
1105
1106   /* Reset in_gimple_form to not break non-unit-at-a-time mode.  */
1107   in_gimple_form = false;
1108
1109   return true;
1110 }
1111
1112 void
1113 execute_pass_list (struct tree_opt_pass *pass)
1114 {
1115   do
1116     {
1117       if (execute_one_pass (pass) && pass->sub)
1118         execute_pass_list (pass->sub);
1119       pass = pass->next;
1120     }
1121   while (pass);
1122 }
1123
1124 /* Same as execute_pass_list but assume that subpasses of IPA passes
1125    are local passes.  */
1126 void
1127 execute_ipa_pass_list (struct tree_opt_pass *pass)
1128 {
1129   do
1130     {
1131       gcc_assert (!current_function_decl);
1132       gcc_assert (!cfun);
1133       if (execute_one_pass (pass) && pass->sub)
1134         do_per_function_toporder ((void (*)(void *))execute_pass_list,
1135                                   pass->sub);
1136       if (!current_function_decl)
1137         cgraph_process_new_functions ();
1138       pass = pass->next;
1139     }
1140   while (pass);
1141 }
1142 #include "gt-passes.h"