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