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_matrix_reorg);
 510   NEXT_PASS (pass_ipa_cp);
 511   NEXT_PASS (pass_ipa_inline);
 512   NEXT_PASS (pass_ipa_reference);
 513   NEXT_PASS (pass_ipa_pure_const);
 514   NEXT_PASS (pass_ipa_type_escape);
 515   NEXT_PASS (pass_ipa_pta);
 516   *p = NULL;
 517
 518   /* These passes are run after IPA passes on every function that is being
 519      output to the assembler file.  */
 520   p = &all_passes;
 521   NEXT_PASS (pass_apply_inline);
 522   NEXT_PASS (pass_all_optimizations);
 523     {
 524       struct tree_opt_pass **p = &pass_all_optimizations.sub;
 525       NEXT_PASS (pass_create_structure_vars);
 526       NEXT_PASS (pass_may_alias);
 527       NEXT_PASS (pass_return_slot);
 528       NEXT_PASS (pass_rename_ssa_copies);
 529
 530       /* Initial scalar cleanups.  */
 531       NEXT_PASS (pass_ccp);
 532       NEXT_PASS (pass_phiprop);
 533       NEXT_PASS (pass_fre);
 534       NEXT_PASS (pass_dce);
 535       NEXT_PASS (pass_forwprop);
 536       NEXT_PASS (pass_copy_prop);
 537       NEXT_PASS (pass_merge_phi);
 538       NEXT_PASS (pass_vrp);
 539       NEXT_PASS (pass_dce);
 540       NEXT_PASS (pass_dominator);
 541
 542       /* The only const/copy propagation opportunities left after
 543          DOM should be due to degenerate PHI nodes.  So rather than
 544          run the full propagators, run a specialized pass which
 545          only examines PHIs to discover const/copy propagation
 546          opportunities.  */
 547       NEXT_PASS (pass_phi_only_cprop);
 548
 549       NEXT_PASS (pass_phiopt);
 550       NEXT_PASS (pass_may_alias);
 551       NEXT_PASS (pass_tail_recursion);
 552       NEXT_PASS (pass_ch);
 553       NEXT_PASS (pass_stdarg);
 554       NEXT_PASS (pass_lower_complex);
 555       NEXT_PASS (pass_sra);
 556       /* FIXME: SRA may generate arbitrary gimple code, exposing new
 557          aliased and call-clobbered variables.  As mentioned below,
 558          pass_may_alias should be a TODO item.  */
 559       NEXT_PASS (pass_may_alias);
 560       NEXT_PASS (pass_rename_ssa_copies);
 561       NEXT_PASS (pass_dominator);
 562
 563       /* The only const/copy propagation opportunities left after
 564          DOM should be due to degenerate PHI nodes.  So rather than
 565          run the full propagators, run a specialized pass which
 566          only examines PHIs to discover const/copy propagation
 567          opportunities.  */
 568       NEXT_PASS (pass_phi_only_cprop);
 569
 570       NEXT_PASS (pass_reassoc);
 571       NEXT_PASS (pass_dce);
 572       NEXT_PASS (pass_dse);
 573       NEXT_PASS (pass_may_alias);
 574       NEXT_PASS (pass_forwprop);
 575       NEXT_PASS (pass_phiopt);
 576       NEXT_PASS (pass_object_sizes);
 577       NEXT_PASS (pass_store_ccp);
 578       NEXT_PASS (pass_store_copy_prop);
 579       NEXT_PASS (pass_fold_builtins);
 580       NEXT_PASS (pass_cse_sincos);
 581       /* FIXME: May alias should a TODO but for 4.0.0,
 582          we add may_alias right after fold builtins
 583          which can create arbitrary GIMPLE.  */
 584       NEXT_PASS (pass_may_alias);
 585       NEXT_PASS (pass_split_crit_edges);
 586       NEXT_PASS (pass_pre);
 587       NEXT_PASS (pass_may_alias);
 588       NEXT_PASS (pass_sink_code);
 589       NEXT_PASS (pass_tree_loop);
 590         {
 591           struct tree_opt_pass **p = &pass_tree_loop.sub;
 592           NEXT_PASS (pass_tree_loop_init);
 593           NEXT_PASS (pass_copy_prop);
 594           NEXT_PASS (pass_dce_loop);
 595           NEXT_PASS (pass_lim);
 596           NEXT_PASS (pass_predcom);
 597           NEXT_PASS (pass_tree_unswitch);
 598           NEXT_PASS (pass_scev_cprop);
 599           NEXT_PASS (pass_empty_loop);
 600           NEXT_PASS (pass_record_bounds);
 601           NEXT_PASS (pass_check_data_deps);
 602           NEXT_PASS (pass_linear_transform);
 603           NEXT_PASS (pass_iv_canon);
 604           NEXT_PASS (pass_if_conversion);
 605           NEXT_PASS (pass_vectorize);
 606             {
 607               struct tree_opt_pass **p = &pass_vectorize.sub;
 608               NEXT_PASS (pass_lower_vector_ssa);
 609               NEXT_PASS (pass_dce_loop);
 610             }
 611           /* NEXT_PASS (pass_may_alias) cannot be done again because the
 612              vectorizer creates alias relations that are not supported by
 613              pass_may_alias.  */
 614           NEXT_PASS (pass_complete_unroll);
 615           NEXT_PASS (pass_loop_prefetch);
 616           NEXT_PASS (pass_iv_optimize);
 617           NEXT_PASS (pass_tree_loop_done);
 618         }
 619       NEXT_PASS (pass_cse_reciprocals);
 620       NEXT_PASS (pass_reassoc);
 621       NEXT_PASS (pass_vrp);
 622       NEXT_PASS (pass_dominator);
 623
 624       /* The only const/copy propagation opportunities left after
 625          DOM should be due to degenerate PHI nodes.  So rather than
 626          run the full propagators, run a specialized pass which
 627          only examines PHIs to discover const/copy propagation
 628          opportunities.  */
 629       NEXT_PASS (pass_phi_only_cprop);
 630
 631       NEXT_PASS (pass_cd_dce);
 632
 633       /* FIXME: If DCE is not run before checking for uninitialized uses,
 634          we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c).
 635          However, this also causes us to misdiagnose cases that should be
 636          real warnings (e.g., testsuite/gcc.dg/pr18501.c).
 637
 638          To fix the false positives in uninit-5.c, we would have to
 639          account for the predicates protecting the set and the use of each
 640          variable.  Using a representation like Gated Single Assignment
 641          may help.  */
 642       NEXT_PASS (pass_late_warn_uninitialized);
 643       NEXT_PASS (pass_dse);
 644       NEXT_PASS (pass_forwprop);
 645       NEXT_PASS (pass_phiopt);
 646       NEXT_PASS (pass_tail_calls);
 647       NEXT_PASS (pass_rename_ssa_copies);
 648       NEXT_PASS (pass_uncprop);
 649       NEXT_PASS (pass_del_ssa);
 650       NEXT_PASS (pass_nrv);
 651       NEXT_PASS (pass_mark_used_blocks);
 652       NEXT_PASS (pass_cleanup_cfg_post_optimizing);
 653     }
 654   NEXT_PASS (pass_warn_function_noreturn);
 655   NEXT_PASS (pass_free_datastructures);
 656   NEXT_PASS (pass_mudflap_2);
 657   NEXT_PASS (pass_free_cfg_annotations);
 658   NEXT_PASS (pass_expand);
 659   NEXT_PASS (pass_rest_of_compilation);
 660     {
 661       struct tree_opt_pass **p = &pass_rest_of_compilation.sub;
 662       NEXT_PASS (pass_init_function);
 663       NEXT_PASS (pass_jump);
 664       NEXT_PASS (pass_rtl_eh);
 665       NEXT_PASS (pass_initial_value_sets);
 666       NEXT_PASS (pass_unshare_all_rtl);
 667       NEXT_PASS (pass_instantiate_virtual_regs);
 668       NEXT_PASS (pass_into_cfg_layout_mode);
 669       NEXT_PASS (pass_jump2);
 670       NEXT_PASS (pass_lower_subreg);
 671       NEXT_PASS (pass_cse);
 672       NEXT_PASS (pass_rtl_fwprop);
 673       NEXT_PASS (pass_gcse);
 674       NEXT_PASS (pass_rtl_ifcvt);
 675       NEXT_PASS (pass_tracer);
 676       /* Perform loop optimizations.  It might be better to do them a bit
 677          sooner, but we want the profile feedback to work more
 678          efficiently.  */
 679       NEXT_PASS (pass_loop2);
 680         {
 681           struct tree_opt_pass **p = &pass_loop2.sub;
 682           NEXT_PASS (pass_rtl_loop_init);
 683           NEXT_PASS (pass_rtl_move_loop_invariants);
 684           NEXT_PASS (pass_rtl_unswitch);
 685           NEXT_PASS (pass_rtl_unroll_and_peel_loops);
 686           NEXT_PASS (pass_rtl_doloop);
 687           NEXT_PASS (pass_rtl_loop_done);
 688           *p = NULL;
 689         }
 690       NEXT_PASS (pass_web);
 691       NEXT_PASS (pass_jump_bypass);
 692       NEXT_PASS (pass_cse2);
 693       NEXT_PASS (pass_rtl_fwprop_addr);
 694       NEXT_PASS (pass_outof_cfg_layout_mode);
 695       NEXT_PASS (pass_life);
 696       NEXT_PASS (pass_combine);
 697       NEXT_PASS (pass_if_after_combine);
 698       NEXT_PASS (pass_partition_blocks);
 699       NEXT_PASS (pass_regmove);
 700       NEXT_PASS (pass_split_all_insns);
 701       NEXT_PASS (pass_lower_subreg2);
 702       NEXT_PASS (pass_mode_switching);
 703       NEXT_PASS (pass_see);
 704       NEXT_PASS (pass_recompute_reg_usage);
 705       NEXT_PASS (pass_sms);
 706       NEXT_PASS (pass_sched);
 707       NEXT_PASS (pass_local_alloc);
 708       NEXT_PASS (pass_global_alloc);
 709       NEXT_PASS (pass_postreload);
 710         {
 711           struct tree_opt_pass **p = &pass_postreload.sub;
 712           NEXT_PASS (pass_postreload_cse);
 713           NEXT_PASS (pass_gcse2);
 714           NEXT_PASS (pass_flow2);
 715           NEXT_PASS (pass_rtl_seqabstr);
 716           NEXT_PASS (pass_stack_adjustments);
 717           NEXT_PASS (pass_peephole2);
 718           NEXT_PASS (pass_if_after_reload);
 719           NEXT_PASS (pass_regrename);
 720           NEXT_PASS (pass_reorder_blocks);
 721           NEXT_PASS (pass_branch_target_load_optimize);
 722           NEXT_PASS (pass_leaf_regs);
 723           NEXT_PASS (pass_sched2);
 724           NEXT_PASS (pass_split_before_regstack);
 725           NEXT_PASS (pass_stack_regs);
 726           NEXT_PASS (pass_compute_alignments);
 727           NEXT_PASS (pass_duplicate_computed_gotos);
 728           NEXT_PASS (pass_variable_tracking);
 729           NEXT_PASS (pass_free_cfg);
 730           NEXT_PASS (pass_machine_reorg);
 731           NEXT_PASS (pass_cleanup_barriers);
 732           NEXT_PASS (pass_delay_slots);
 733           NEXT_PASS (pass_split_for_shorten_branches);
 734           NEXT_PASS (pass_convert_to_eh_region_ranges);
 735           NEXT_PASS (pass_shorten_branches);
 736           NEXT_PASS (pass_set_nothrow_function_flags);
 737           NEXT_PASS (pass_final);
 738         }
 739     }
 740   NEXT_PASS (pass_clean_state);
 741   *p = NULL;
 742
 743 #undef NEXT_PASS
 744
 745   /* Register the passes with the tree dump code.  */
 746   register_dump_files (all_lowering_passes, false, PROP_gimple_any);
 747   all_lowering_passes->todo_flags_start |= TODO_set_props;
 748   register_dump_files (all_ipa_passes, true,
 749                        PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh
 750                        | PROP_cfg);
 751   register_dump_files (all_passes, false,
 752                        PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh
 753                        | PROP_cfg);
 754 }
 755
 756 /* If we are in IPA mode (i.e., current_function_decl is NULL), call
 757    function CALLBACK for every function in the call graph.  Otherwise,
 758    call CALLBACK on the current function.  */
 759
 760 static void
 761 do_per_function (void (*callback) (void *data), void *data)
 762 {
 763   if (current_function_decl)
 764     callback (data);
 765   else
 766     {
 767       struct cgraph_node *node;
 768       for (node = cgraph_nodes; node; node = node->next)
 769         if (node->analyzed)
 770           {
 771             push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 772             current_function_decl = node->decl;
 773             callback (data);
 774             free_dominance_info (CDI_DOMINATORS);
 775             free_dominance_info (CDI_POST_DOMINATORS);
 776             current_function_decl = NULL;
 777             pop_cfun ();
 778             ggc_collect ();
 779           }
 780     }
 781 }
 782
 783 /* Because inlining might remove no-longer reachable nodes, we need to
 784    keep the array visible to garbage collector to avoid reading collected
 785    out nodes.  */
 786 static int nnodes;
 787 static GTY ((length ("nnodes"))) struct cgraph_node **order;
 788
 789 /* If we are in IPA mode (i.e., current_function_decl is NULL), call
 790    function CALLBACK for every function in the call graph.  Otherwise,
 791    call CALLBACK on the current function.  */
 792
 793 static void
 794 do_per_function_toporder (void (*callback) (void *data), void *data)
 795 {
 796   int i;
 797
 798   if (current_function_decl)
 799     callback (data);
 800   else
 801     {
 802       gcc_assert (!order);
 803       order = ggc_alloc (sizeof (*order) * cgraph_n_nodes);
 804       nnodes = cgraph_postorder (order);
 805       for (i = nnodes - 1; i >= 0; i--)
 806         {
 807           struct cgraph_node *node = order[i];
 808
 809           /* Allow possibly removed nodes to be garbage collected.  */
 810           order[i] = NULL;
 811           if (node->analyzed && (node->needed || node->reachable))
 812             {
 813               push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 814               current_function_decl = node->decl;
 815               callback (data);
 816               free_dominance_info (CDI_DOMINATORS);
 817               free_dominance_info (CDI_POST_DOMINATORS);
 818               current_function_decl = NULL;
 819               pop_cfun ();
 820               ggc_collect ();
 821             }
 822         }
 823     }
 824   ggc_free (order);
 825   order = NULL;
 826   nnodes = 0;
 827 }
 828
 829 /* Perform all TODO actions that ought to be done on each function.  */
 830
 831 static void
 832 execute_function_todo (void *data)
 833 {
 834   unsigned int flags = (size_t)data;
 835   if (cfun->curr_properties & PROP_ssa)
 836     flags |= TODO_verify_ssa;
 837   flags &= ~cfun->last_verified;
 838   if (!flags)
 839     return;
 840
 841   /* Always cleanup the CFG before trying to update SSA.  */
 842   if (flags & TODO_cleanup_cfg)
 843     {
 844       bool cleanup;
 845
 846       if (current_loops)
 847         cleanup = cleanup_tree_cfg_loop ();
 848       else
 849         cleanup = cleanup_tree_cfg ();
 850
 851       if (cleanup && (cfun->curr_properties & PROP_ssa))
 852         flags |= TODO_remove_unused_locals;
 853
 854       /* When cleanup_tree_cfg merges consecutive blocks, it may
 855          perform some simplistic propagation when removing single
 856          valued PHI nodes.  This propagation may, in turn, cause the
 857          SSA form to become out-of-date (see PR 22037).  So, even
 858          if the parent pass had not scheduled an SSA update, we may
 859          still need to do one.  */
 860       if (!(flags & TODO_update_ssa_any) && need_ssa_update_p ())
 861         flags |= TODO_update_ssa;
 862     }
 863
 864   if (flags & TODO_update_ssa_any)
 865     {
 866       unsigned update_flags = flags & TODO_update_ssa_any;
 867       update_ssa (update_flags);
 868       cfun->last_verified &= ~TODO_verify_ssa;
 869     }
 870
 871   if (flags & TODO_remove_unused_locals)
 872     remove_unused_locals ();
 873
 874   if ((flags & TODO_dump_func)
 875       && dump_file && current_function_decl)
 876     {
 877       if (cfun->curr_properties & PROP_trees)
 878         dump_function_to_file (current_function_decl,
 879                                dump_file, dump_flags);
 880       else
 881         {
 882           if (dump_flags & TDF_SLIM)
 883             print_rtl_slim_with_bb (dump_file, get_insns (), dump_flags);
 884           else if ((cfun->curr_properties & PROP_cfg)
 885                    && (dump_flags & TDF_BLOCKS))
 886             print_rtl_with_bb (dump_file, get_insns ());
 887           else
 888             print_rtl (dump_file, get_insns ());
 889
 890           if (cfun->curr_properties & PROP_cfg
 891               && graph_dump_format != no_graph
 892               && (dump_flags & TDF_GRAPH))
 893             print_rtl_graph_with_bb (dump_file_name, get_insns ());
 894         }
 895
 896       /* Flush the file.  If verification fails, we won't be able to
 897          close the file before aborting.  */
 898       fflush (dump_file);
 899     }
 900
 901   if (flags & TODO_rebuild_frequencies)
 902     {
 903       if (profile_status == PROFILE_GUESSED)
 904         {
 905           loop_optimizer_init (0);
 906           add_noreturn_fake_exit_edges ();
 907           mark_irreducible_loops ();
 908           connect_infinite_loops_to_exit ();
 909           estimate_bb_frequencies ();
 910           remove_fake_exit_edges ();
 911           loop_optimizer_finalize ();
 912         }
 913       else if (profile_status == PROFILE_READ)
 914         counts_to_freqs ();
 915       else
 916         gcc_unreachable ();
 917     }
 918
 919 #if defined ENABLE_CHECKING
 920   if (flags & TODO_verify_ssa)
 921     verify_ssa (true);
 922   if (flags & TODO_verify_flow)
 923     verify_flow_info ();
 924   if (flags & TODO_verify_stmts)
 925     verify_stmts ();
 926   if (flags & TODO_verify_loops)
 927     verify_loop_closed_ssa ();
 928 #endif
 929
 930   cfun->last_verified = flags & TODO_verify_all;
 931 }
 932
 933 /* Perform all TODO actions.  */
 934 static void
 935 execute_todo (unsigned int flags)
 936 {
 937 #if defined ENABLE_CHECKING
 938   if (need_ssa_update_p ())
 939     gcc_assert (flags & TODO_update_ssa_any);
 940 #endif
 941
 942   /* Inform the pass whether it is the first time it is run.  */
 943   first_pass_instance = (flags & TODO_mark_first_instance) != 0;
 944
 945   do_per_function (execute_function_todo, (void *)(size_t) flags);
 946
 947   /* Always remove functions just as before inlining: IPA passes might be
 948      interested to see bodies of extern inline functions that are not inlined
 949      to analyze side effects.  The full removal is done just at the end
 950      of IPA pass queue.  */
 951   if (flags & TODO_remove_functions)
 952     cgraph_remove_unreachable_nodes (true, dump_file);
 953
 954   if ((flags & TODO_dump_cgraph)
 955       && dump_file && !current_function_decl)
 956     {
 957       dump_cgraph (dump_file);
 958       /* Flush the file.  If verification fails, we won't be able to
 959          close the file before aborting.  */
 960       fflush (dump_file);
 961     }
 962
 963   if (flags & TODO_ggc_collect)
 964     {
 965       ggc_collect ();
 966     }
 967 }
 968
 969 /* Verify invariants that should hold between passes.  This is a place
 970    to put simple sanity checks.  */
 971
 972 static void
 973 verify_interpass_invariants (void)
 974 {
 975 #ifdef ENABLE_CHECKING
 976   gcc_assert (!fold_deferring_overflow_warnings_p ());
 977 #endif
 978 }
 979
 980 /* Clear the last verified flag.  */
 981
 982 static void
 983 clear_last_verified (void *data ATTRIBUTE_UNUSED)
 984 {
 985   cfun->last_verified = 0;
 986 }
 987
 988 /* Helper function. Verify that the properties has been turn into the
 989    properties expected by the pass.  */
 990
 991 #ifdef ENABLE_CHECKING
 992 static void
 993 verify_curr_properties (void *data)
 994 {
 995   unsigned int props = (size_t)data;
 996   gcc_assert ((cfun->curr_properties & props) == props);
 997 }
 998 #endif
 999
1000 /* After executing the pass, apply expected changes to the function
1001    properties. */
1002 static void
1003 update_properties_after_pass (void *data)
1004 {
1005   struct tree_opt_pass *pass = data;
1006   cfun->curr_properties = (cfun->curr_properties | pass->properties_provided)
1007                            & ~pass->properties_destroyed;
1008 }
1009
1010 static bool
1011 execute_one_pass (struct tree_opt_pass *pass)
1012 {
1013   bool initializing_dump;
1014   unsigned int todo_after = 0;
1015
1016   /* See if we're supposed to run this pass.  */
1017   if (pass->gate && !pass->gate ())
1018     return false;
1019
1020   if (!quiet_flag && !cfun)
1021     fprintf (stderr, " <%s>", pass->name ? pass->name : "");
1022
1023   if (pass->todo_flags_start & TODO_set_props)
1024     cfun->curr_properties = pass->properties_required;
1025
1026   /* Note that the folders should only create gimple expressions.
1027      This is a hack until the new folder is ready.  */
1028   in_gimple_form = (cfun && (cfun->curr_properties & PROP_trees)) != 0;
1029
1030   /* Run pre-pass verification.  */
1031   execute_todo (pass->todo_flags_start);
1032
1033 #ifdef ENABLE_CHECKING
1034   do_per_function (verify_curr_properties,
1035                    (void *)(size_t)pass->properties_required);
1036 #endif
1037
1038   /* If a dump file name is present, open it if enabled.  */
1039   if (pass->static_pass_number != -1)
1040     {
1041       initializing_dump = !dump_initialized_p (pass->static_pass_number);
1042       dump_file_name = get_dump_file_name (pass->static_pass_number);
1043       dump_file = dump_begin (pass->static_pass_number, &dump_flags);
1044       if (dump_file && current_function_decl)
1045         {
1046           const char *dname, *aname;
1047           dname = lang_hooks.decl_printable_name (current_function_decl, 2);
1048           aname = (IDENTIFIER_POINTER
1049                    (DECL_ASSEMBLER_NAME (current_function_decl)));
1050           fprintf (dump_file, "\n;; Function %s (%s)%s\n\n", dname, aname,
1051              cfun->function_frequency == FUNCTION_FREQUENCY_HOT
1052              ? " (hot)"
1053              : cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
1054              ? " (unlikely executed)"
1055              : "");
1056         }
1057     }
1058   else
1059     initializing_dump = false;
1060
1061   /* If a timevar is present, start it.  */
1062   if (pass->tv_id)
1063     timevar_push (pass->tv_id);
1064
1065   /* Do it!  */
1066   if (pass->execute)
1067     {
1068       todo_after = pass->execute ();
1069       do_per_function (clear_last_verified, NULL);
1070     }
1071
1072   /* Stop timevar.  */
1073   if (pass->tv_id)
1074     timevar_pop (pass->tv_id);
1075
1076   do_per_function (update_properties_after_pass, pass);
1077
1078   if (initializing_dump
1079       && dump_file
1080       && graph_dump_format != no_graph
1081       && (cfun->curr_properties & (PROP_cfg | PROP_rtl))
1082           == (PROP_cfg | PROP_rtl))
1083     {
1084       get_dump_file_info (pass->static_pass_number)->flags |= TDF_GRAPH;
1085       dump_flags |= TDF_GRAPH;
1086       clean_graph_dump_file (dump_file_name);
1087     }
1088
1089   /* Run post-pass cleanup and verification.  */
1090   execute_todo (todo_after | pass->todo_flags_finish);
1091   verify_interpass_invariants ();
1092
1093   if (!current_function_decl)
1094     cgraph_process_new_functions ();
1095
1096   /* Flush and close dump file.  */
1097   if (dump_file_name)
1098     {
1099       free ((char *) dump_file_name);
1100       dump_file_name = NULL;
1101     }
1102
1103   if (dump_file)
1104     {
1105       dump_end (pass->static_pass_number, dump_file);
1106       dump_file = NULL;
1107     }
1108
1109   /* Reset in_gimple_form to not break non-unit-at-a-time mode.  */
1110   in_gimple_form = false;
1111
1112   return true;
1113 }
1114
1115 void
1116 execute_pass_list (struct tree_opt_pass *pass)
1117 {
1118   do
1119     {
1120       if (execute_one_pass (pass) && pass->sub)
1121         execute_pass_list (pass->sub);
1122       pass = pass->next;
1123     }
1124   while (pass);
1125 }
1126
1127 /* Same as execute_pass_list but assume that subpasses of IPA passes
1128    are local passes.  */
1129 void
1130 execute_ipa_pass_list (struct tree_opt_pass *pass)
1131 {
1132   do
1133     {
1134       gcc_assert (!current_function_decl);
1135       gcc_assert (!cfun);
1136       if (execute_one_pass (pass) && pass->sub)
1137         do_per_function_toporder ((void (*)(void *))execute_pass_list,
1138                                   pass->sub);
1139       if (!current_function_decl)
1140         cgraph_process_new_functions ();
1141       pass = pass->next;
1142     }
1143   while (pass);
1144 }
1145 #include "gt-passes.h"