gcc/tree-dfa.c

   1 /* Data flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "hashtab.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "output.h"
  33 #include "errors.h"
  34 #include "timevar.h"
  35 #include "expr.h"
  36 #include "ggc.h"
  37 #include "langhooks.h"
  38 #include "flags.h"
  39 #include "function.h"
  40 #include "diagnostic.h"
  41 #include "tree-dump.h"
  42 #include "tree-gimple.h"
  43 #include "tree-flow.h"
  44 #include "tree-inline.h"
  45 #include "tree-alias-common.h"
  46 #include "tree-pass.h"
  47 #include "convert.h"
  48 #include "params.h"
  49
  50 /* Build and maintain data flow information for trees.  */
  51
  52 /* Counters used to display DFA and SSA statistics.  */
  53 struct dfa_stats_d
  54 {
  55   long num_stmt_anns;
  56   long num_var_anns;
  57   long num_defs;
  58   long num_uses;
  59   long num_phis;
  60   long num_phi_args;
  61   int max_num_phi_args;
  62   long num_vdefs;
  63   long num_vuses;
  64 };
  65
  66
  67 /* State information for find_vars_r.  */
  68 struct walk_state
  69 {
  70   /* Hash table used to avoid adding the same variable more than once.  */
  71   htab_t vars_found;
  72 };
  73
  74
  75 /* Local functions.  */
  76 static void collect_dfa_stats (struct dfa_stats_d *);
  77 static tree collect_dfa_stats_r (tree *, int *, void *);
  78 static void add_immediate_use (tree, tree);
  79 static tree find_vars_r (tree *, int *, void *);
  80 static void add_referenced_var (tree, struct walk_state *);
  81 static void compute_immediate_uses_for_phi (tree, bool (*)(tree));
  82 static void compute_immediate_uses_for_stmt (tree, int, bool (*)(tree));
  83 static void find_hidden_use_vars (tree);
  84 static tree find_hidden_use_vars_r (tree *, int *, void *);
  85
  86
  87 /* Global declarations.  */
  88
  89 /* Array of all variables referenced in the function.  */
  90 varray_type referenced_vars;
  91
  92
  93 /*---------------------------------------------------------------------------
  94                         Dataflow analysis (DFA) routines
  95 ---------------------------------------------------------------------------*/
  96 /* Find all the variables referenced in the function.  This function
  97    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
  98
  99    Note that this function does not look for statement operands, it simply
 100    determines what variables are referenced in the program and detects
 101    various attributes for each variable used by alias analysis and the
 102    optimizer.  */
 103
 104 static void
 105 find_referenced_vars (void)
 106 {
 107   htab_t vars_found;
 108   basic_block bb;
 109   block_stmt_iterator si;
 110   struct walk_state walk_state;
 111   tree block;
 112
 113   /* This is the very first pass in preparation for building the SSA
 114      form of the function, so initialize internal data structures now.  */
 115   init_tree_ssa ();
 116
 117   /* Walk the lexical blocks in the function looking for variables that may
 118      have been used to declare VLAs and for nested functions.  Both
 119      constructs create hidden uses of variables.
 120
 121      Note that at this point we may have multiple blocks hung off
 122      DECL_INITIAL chained through the BLOCK_CHAIN field due to
 123      how inlining works.  Egad.  */
 124   block = DECL_INITIAL (current_function_decl);
 125   while (block)
 126     {
 127       find_hidden_use_vars (block);
 128       block = BLOCK_CHAIN (block);
 129     }
 130
 131   vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
 132   memset (&walk_state, 0, sizeof (walk_state));
 133   walk_state.vars_found = vars_found;
 134
 135   FOR_EACH_BB (bb)
 136     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 137       {
 138         tree *stmt_p = bsi_stmt_ptr (si);
 139         walk_tree (stmt_p, find_vars_r, &walk_state, NULL);
 140       }
 141
 142   htab_delete (vars_found);
 143 }
 144
 145 struct tree_opt_pass pass_referenced_vars =
 146 {
 147   NULL,                                 /* name */
 148   NULL,                                 /* gate */
 149   find_referenced_vars,                 /* execute */
 150   NULL,                                 /* sub */
 151   NULL,                                 /* next */
 152   0,                                    /* static_pass_number */
 153   0,                                    /* tv_id */
 154   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 155   PROP_referenced_vars,                 /* properties_provided */
 156   0,                                    /* properties_destroyed */
 157   0,                                    /* todo_flags_start */
 158   0,                                    /* todo_flags_finish */
 159 };
 160
 161
 162 /* Compute immediate uses.
 163
 164    CALC_FOR is an optional function pointer which indicates whether
 165       immediate uses information should be calculated for a given SSA
 166       variable.  If NULL, then information is computed for all
 167       variables.
 168
 169    FLAGS is one of {TDFA_USE_OPS, TDFA_USE_VOPS}.  It is used by
 170       compute_immediate_uses_for_stmt to determine whether to look at
 171       virtual and/or real operands while computing def-use chains.  */
 172
 173 void
 174 compute_immediate_uses (int flags, bool (*calc_for)(tree))
 175 {
 176   basic_block bb;
 177   block_stmt_iterator si;
 178
 179   FOR_EACH_BB (bb)
 180     {
 181       tree phi;
 182
 183       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 184         compute_immediate_uses_for_phi (phi, calc_for);
 185
 186       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 187         {
 188           tree stmt = bsi_stmt (si);
 189           get_stmt_operands (stmt);
 190           compute_immediate_uses_for_stmt (stmt, flags, calc_for);
 191         }
 192     }
 193 }
 194
 195
 196 /* Invalidates dataflow information for a statement STMT.  */
 197
 198 static void
 199 free_df_for_stmt (tree stmt)
 200 {
 201   stmt_ann_t ann = stmt_ann (stmt);
 202
 203   if (ann && ann->df)
 204     {
 205       /* If we have a varray of immediate uses, then go ahead and release
 206          it for re-use.  */
 207       if (ann->df->immediate_uses)
 208         ggc_free (ann->df->immediate_uses);
 209
 210       /* Similarly for the main dataflow structure.  */
 211       ggc_free (ann->df);
 212       ann->df = NULL;
 213     }
 214 }
 215
 216
 217 /* Invalidate dataflow information for the whole function.  */
 218
 219 void
 220 free_df (void)
 221 {
 222   basic_block bb;
 223   block_stmt_iterator si;
 224
 225   FOR_EACH_BB (bb)
 226     {
 227       tree phi;
 228
 229       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 230         free_df_for_stmt (phi);
 231
 232       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 233         {
 234           tree stmt = bsi_stmt (si);
 235           free_df_for_stmt (stmt);
 236         }
 237     }
 238 }
 239
 240
 241 /* Helper for compute_immediate_uses.  Check all the USE and/or VUSE
 242    operands in phi node PHI and add a def-use edge between their
 243    defining statement and PHI.  CALC_FOR is as in
 244    compute_immediate_uses.
 245
 246    PHI nodes are easy, we only need to look at their arguments.  */
 247
 248 static void
 249 compute_immediate_uses_for_phi (tree phi, bool (*calc_for)(tree))
 250 {
 251   int i;
 252
 253 #ifdef ENABLE_CHECKING
 254   if (TREE_CODE (phi) != PHI_NODE)
 255     abort ();
 256 #endif
 257
 258   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 259     {
 260       tree arg = PHI_ARG_DEF (phi, i);
 261
 262       if (TREE_CODE (arg) == SSA_NAME && (!calc_for || calc_for (arg)))
 263         {
 264           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF (phi, i));
 265           if (!IS_EMPTY_STMT (imm_rdef_stmt))
 266             add_immediate_use (imm_rdef_stmt, phi);
 267         }
 268     }
 269 }
 270
 271
 272 /* Another helper for compute_immediate_uses.  Depending on the value
 273    of FLAGS, check all the USE and/or VUSE operands in STMT and add a
 274    def-use edge between their defining statement and STMT.  CALC_FOR
 275    is as in compute_immediate_uses.  */
 276
 277 static void
 278 compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
 279 {
 280   size_t i;
 281   use_optype uses;
 282   vuse_optype vuses;
 283   vdef_optype vdefs;
 284   stmt_ann_t ann;
 285
 286 #ifdef ENABLE_CHECKING
 287   /* PHI nodes are handled elsewhere.  */
 288   if (TREE_CODE (stmt) == PHI_NODE)
 289     abort ();
 290 #endif
 291
 292   /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
 293   ann = stmt_ann (stmt);
 294   if (flags & TDFA_USE_OPS)
 295     {
 296       uses = USE_OPS (ann);
 297       for (i = 0; i < NUM_USES (uses); i++)
 298         {
 299           tree use = USE_OP (uses, i);
 300           tree imm_stmt = SSA_NAME_DEF_STMT (use);
 301           if (!IS_EMPTY_STMT (imm_stmt) && (!calc_for || calc_for (use)))
 302             add_immediate_use (imm_stmt, stmt);
 303         }
 304     }
 305
 306   if (flags & TDFA_USE_VOPS)
 307     {
 308       vuses = VUSE_OPS (ann);
 309       for (i = 0; i < NUM_VUSES (vuses); i++)
 310         {
 311           tree vuse = VUSE_OP (vuses, i);
 312           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
 313           if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
 314             add_immediate_use (imm_rdef_stmt, stmt);
 315         }
 316
 317       vdefs = VDEF_OPS (ann);
 318       for (i = 0; i < NUM_VDEFS (vdefs); i++)
 319         {
 320           tree vuse = VDEF_OP (vdefs, i);
 321           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
 322           if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
 323             add_immediate_use (imm_rdef_stmt, stmt);
 324         }
 325     }
 326 }
 327
 328
 329 /* Add statement USE_STMT to the list of statements that use definitions
 330     made by STMT.  */
 331
 332 static void
 333 add_immediate_use (tree stmt, tree use_stmt)
 334 {
 335   stmt_ann_t ann = get_stmt_ann (stmt);
 336   struct dataflow_d *df;
 337
 338   df = ann->df;
 339   if (df == NULL)
 340     {
 341       df = ann->df = ggc_alloc (sizeof (struct dataflow_d));
 342       memset ((void *) df, 0, sizeof (struct dataflow_d));
 343       df->uses[0] = use_stmt;
 344       return;
 345     }
 346
 347   if (!df->uses[1])
 348     {
 349       df->uses[1] = use_stmt;
 350       return;
 351     }
 352
 353   if (ann->df->immediate_uses == NULL)
 354     VARRAY_TREE_INIT (ann->df->immediate_uses, 4, "immediate_uses");
 355
 356   VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
 357 }
 358
 359
 360 /* If the immediate use of USE points to OLD, then redirect it to NEW.  */
 361
 362 static void
 363 redirect_immediate_use (tree use, tree old, tree new)
 364 {
 365   tree imm_stmt = SSA_NAME_DEF_STMT (use);
 366   struct dataflow_d *df = get_stmt_ann (imm_stmt)->df;
 367   unsigned int num_uses = num_immediate_uses (df);
 368   unsigned int i;
 369
 370   for (i = 0; i < num_uses; i++)
 371     {
 372       if (immediate_use (df, i) == old)
 373         {
 374           if (i == 0 || i == 1)
 375             df->uses[i] = new;
 376           else
 377             VARRAY_TREE (df->immediate_uses, i - 2) = new;
 378         }
 379     }
 380 }
 381
 382
 383 /* Redirect all immediate uses for operands in OLD so that they point
 384    to NEW.  This routine should have no knowledge of how immediate
 385    uses are stored.  */
 386
 387 void
 388 redirect_immediate_uses (tree old, tree new)
 389 {
 390   stmt_ann_t ann = get_stmt_ann (old);
 391   use_optype uses = USE_OPS (ann);
 392   vuse_optype vuses = VUSE_OPS (ann);
 393   vdef_optype vdefs = VDEF_OPS (ann);
 394   unsigned int i;
 395
 396   /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
 397   for (i = 0; i < NUM_USES (uses); i++)
 398     redirect_immediate_use (USE_OP (uses, i), old, new);
 399
 400   for (i = 0; i < NUM_VUSES (vuses); i++)
 401     redirect_immediate_use (VUSE_OP (vuses, i), old, new);
 402
 403   for (i = 0; i < NUM_VDEFS (vdefs); i++)
 404     redirect_immediate_use (VDEF_OP (vdefs, i), old, new);
 405 }
 406
 407
 408 /*---------------------------------------------------------------------------
 409                             Manage annotations
 410 ---------------------------------------------------------------------------*/
 411 /* Create a new annotation for a _DECL node T.  */
 412
 413 var_ann_t
 414 create_var_ann (tree t)
 415 {
 416   var_ann_t ann;
 417
 418 #if defined ENABLE_CHECKING
 419   if (t == NULL_TREE
 420       || !DECL_P (t)
 421       || (t->common.ann
 422           && t->common.ann->common.type != VAR_ANN))
 423     abort ();
 424 #endif
 425
 426   ann = ggc_alloc (sizeof (*ann));
 427   memset ((void *) ann, 0, sizeof (*ann));
 428
 429   ann->common.type = VAR_ANN;
 430
 431   t->common.ann = (tree_ann) ann;
 432
 433   return ann;
 434 }
 435
 436
 437 /* Create a new annotation for a statement node T.  */
 438
 439 stmt_ann_t
 440 create_stmt_ann (tree t)
 441 {
 442   stmt_ann_t ann;
 443
 444 #if defined ENABLE_CHECKING
 445   if ((!is_gimple_stmt (t) && !is_essa_node (t))
 446       || (t->common.ann
 447           && t->common.ann->common.type != STMT_ANN))
 448     abort ();
 449 #endif
 450
 451   ann = ggc_alloc (sizeof (*ann));
 452   memset ((void *) ann, 0, sizeof (*ann));
 453
 454   ann->common.type = STMT_ANN;
 455
 456   /* Since we just created the annotation, mark the statement modified.  */
 457   ann->modified = true;
 458
 459   t->common.ann = (tree_ann) ann;
 460
 461   return ann;
 462 }
 463
 464
 465 /* Build a temporary.  Make sure and register it to be renamed.  */
 466
 467 tree
 468 make_rename_temp (tree type, const char *prefix)
 469 {
 470   tree t = create_tmp_var (type, prefix);
 471   add_referenced_tmp_var (t);
 472   bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
 473   return t;
 474 }
 475
 476
 477
 478 /*---------------------------------------------------------------------------
 479                               Debugging functions
 480 ---------------------------------------------------------------------------*/
 481 /* Dump the list of all the referenced variables in the current function to
 482    FILE.  */
 483
 484 void
 485 dump_referenced_vars (FILE *file)
 486 {
 487   size_t i;
 488
 489   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 490            get_name (current_function_decl), (unsigned) num_referenced_vars);
 491
 492   for (i = 0; i < num_referenced_vars; i++)
 493     {
 494       tree var = referenced_var (i);
 495       fprintf (file, "Variable: ");
 496       dump_variable (file, var);
 497       fprintf (file, "\n");
 498     }
 499 }
 500
 501
 502 /* Dump the list of all the referenced variables to stderr.  */
 503
 504 void
 505 debug_referenced_vars (void)
 506 {
 507   dump_referenced_vars (stderr);
 508 }
 509
 510
 511 /* Dump variable VAR and its may-aliases to FILE.  */
 512
 513 void
 514 dump_variable (FILE *file, tree var)
 515 {
 516   var_ann_t ann;
 517
 518   if (var == NULL_TREE)
 519     {
 520       fprintf (file, "<nil>");
 521       return;
 522     }
 523
 524   print_generic_expr (file, var, dump_flags);
 525
 526   if (TREE_CODE (var) == SSA_NAME)
 527     var = SSA_NAME_VAR (var);
 528
 529   ann = var_ann (var);
 530
 531   fprintf (file, ", UID %u", (unsigned) ann->uid);
 532
 533   if (ann->has_hidden_use)
 534     fprintf (file, ", has hidden uses");
 535
 536   if (ann->type_mem_tag)
 537     {
 538       fprintf (file, ", type memory tag: ");
 539       print_generic_expr (file, ann->type_mem_tag, dump_flags);
 540     }
 541
 542   if (ann->is_alias_tag)
 543     fprintf (file, ", is an alias tag");
 544
 545   if (needs_to_live_in_memory (var))
 546     fprintf (file, ", is %s", TREE_STATIC (var) ? "static" : "global");
 547
 548   if (is_call_clobbered (var))
 549     fprintf (file, ", call clobbered");
 550
 551   if (ann->default_def)
 552     {
 553       fprintf (file, ", default def: ");
 554       print_generic_expr (file, ann->default_def, dump_flags);
 555     }
 556
 557   if (ann->may_aliases)
 558     {
 559       fprintf (file, ", may aliases: ");
 560       dump_may_aliases_for (file, var);
 561     }
 562
 563   fprintf (file, "\n");
 564 }
 565
 566
 567 /* Dump variable VAR and its may-aliases to stderr.  */
 568
 569 void
 570 debug_variable (tree var)
 571 {
 572   dump_variable (stderr, var);
 573 }
 574
 575
 576 /* Dump def-use edges on FILE.  */
 577
 578 void
 579 dump_immediate_uses (FILE *file)
 580 {
 581   basic_block bb;
 582   block_stmt_iterator si;
 583   const char *funcname
 584     = lang_hooks.decl_printable_name (current_function_decl, 2);
 585
 586   fprintf (file, "\nDef-use edges for function %s\n", funcname);
 587
 588   FOR_EACH_BB (bb)
 589     {
 590       tree phi;
 591
 592       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 593         dump_immediate_uses_for (file, phi);
 594
 595       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 596         dump_immediate_uses_for (file, bsi_stmt (si));
 597     }
 598
 599   fprintf (file, "\n");
 600 }
 601
 602
 603 /* Dump def-use edges on stderr.  */
 604
 605 void
 606 debug_immediate_uses (void)
 607 {
 608   dump_immediate_uses (stderr);
 609 }
 610
 611
 612 /* Dump all immediate uses for STMT on FILE.  */
 613
 614 void
 615 dump_immediate_uses_for (FILE *file, tree stmt)
 616 {
 617   dataflow_t df = get_immediate_uses (stmt);
 618   int num_imm_uses = num_immediate_uses (df);
 619
 620   if (num_imm_uses > 0)
 621     {
 622       int i;
 623
 624       fprintf (file, "-> ");
 625       print_generic_stmt (file, stmt, TDF_SLIM);
 626       fprintf (file, "\n");
 627
 628       for (i = 0; i < num_imm_uses; i++)
 629         {
 630           fprintf (file, "\t");
 631           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
 632           fprintf (file, "\n");
 633         }
 634
 635       fprintf (file, "\n");
 636     }
 637 }
 638
 639
 640 /* Dump immediate uses for STMT on stderr.  */
 641
 642 void
 643 debug_immediate_uses_for (tree stmt)
 644 {
 645   dump_immediate_uses_for (stderr, stmt);
 646 }
 647
 648
 649 /* Dump various DFA statistics to FILE.  */
 650
 651 void
 652 dump_dfa_stats (FILE *file)
 653 {
 654   struct dfa_stats_d dfa_stats;
 655
 656   unsigned long size, total = 0;
 657   const char * const fmt_str   = "%-30s%-13s%12s\n";
 658   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 659   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 660   const char *funcname
 661     = lang_hooks.decl_printable_name (current_function_decl, 2);
 662
 663   collect_dfa_stats (&dfa_stats);
 664
 665   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 666
 667   fprintf (file, "---------------------------------------------------------\n");
 668   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 669   fprintf (file, fmt_str, "", "  instances  ", "used ");
 670   fprintf (file, "---------------------------------------------------------\n");
 671
 672   size = num_referenced_vars * sizeof (tree);
 673   total += size;
 674   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
 675            SCALE (size), LABEL (size));
 676
 677   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 678   total += size;
 679   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 680            SCALE (size), LABEL (size));
 681
 682   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 683   total += size;
 684   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 685            SCALE (size), LABEL (size));
 686
 687   size = dfa_stats.num_uses * sizeof (tree *);
 688   total += size;
 689   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 690            SCALE (size), LABEL (size));
 691
 692   size = dfa_stats.num_defs * sizeof (tree *);
 693   total += size;
 694   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 695            SCALE (size), LABEL (size));
 696
 697   size = dfa_stats.num_vuses * sizeof (tree *);
 698   total += size;
 699   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 700            SCALE (size), LABEL (size));
 701
 702   size = dfa_stats.num_vdefs * sizeof (tree *);
 703   total += size;
 704   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 705            SCALE (size), LABEL (size));
 706
 707   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 708   total += size;
 709   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 710            SCALE (size), LABEL (size));
 711
 712   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 713   total += size;
 714   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 715            SCALE (size), LABEL (size));
 716
 717   fprintf (file, "---------------------------------------------------------\n");
 718   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 719            LABEL (total));
 720   fprintf (file, "---------------------------------------------------------\n");
 721   fprintf (file, "\n");
 722
 723   if (dfa_stats.num_phis)
 724     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 725              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 726              dfa_stats.max_num_phi_args);
 727
 728   fprintf (file, "\n");
 729 }
 730
 731
 732 /* Dump DFA statistics on stderr.  */
 733
 734 void
 735 debug_dfa_stats (void)
 736 {
 737   dump_dfa_stats (stderr);
 738 }
 739
 740
 741 /* Collect DFA statistics and store them in the structure pointed by
 742    DFA_STATS_P.  */
 743
 744 static void
 745 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 746 {
 747   htab_t htab;
 748   basic_block bb;
 749   block_stmt_iterator i;
 750
 751   if (dfa_stats_p == NULL)
 752     abort ();
 753
 754   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 755
 756   /* Walk all the trees in the function counting references.  Start at
 757      basic block 0, but don't stop at block boundaries.  */
 758   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
 759
 760   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
 761     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 762                (void *) htab);
 763
 764   htab_delete (htab);
 765
 766   FOR_EACH_BB (bb)
 767     {
 768       tree phi;
 769       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 770         {
 771           dfa_stats_p->num_phis++;
 772           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 773           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 774             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 775         }
 776     }
 777 }
 778
 779
 780 /* Callback for walk_tree to collect DFA statistics for a tree and its
 781    children.  */
 782
 783 static tree
 784 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 785                      void *data)
 786 {
 787   tree t = *tp;
 788   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 789
 790   if (t->common.ann)
 791     {
 792       switch (ann_type (t->common.ann))
 793         {
 794         case STMT_ANN:
 795           {
 796             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
 797             dfa_stats_p->num_stmt_anns++;
 798             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
 799             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
 800             dfa_stats_p->num_vdefs += NUM_VDEFS (VDEF_OPS (ann));
 801             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
 802             break;
 803           }
 804
 805         case VAR_ANN:
 806           dfa_stats_p->num_var_anns++;
 807           break;
 808
 809         default:
 810           break;
 811         }
 812     }
 813
 814   return NULL;
 815 }
 816
 817
 818 /*---------------------------------------------------------------------------
 819                              Miscellaneous helpers
 820 ---------------------------------------------------------------------------*/
 821 /* Callback for walk_tree.  Used to collect variables referenced in
 822    the function.  */
 823
 824 static tree
 825 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 826 {
 827   tree t = *tp;
 828   struct walk_state *walk_state = (struct walk_state *)data;
 829
 830   if (SSA_VAR_P (t))
 831     {
 832       /* If T is a regular variable that the optimizers are interested
 833          in, add it to the list of variables.  */
 834       add_referenced_var (t, walk_state);
 835     }
 836   else if (DECL_P (t)
 837            || TYPE_P (t)
 838            || TREE_CODE_CLASS (TREE_CODE (t)) == 'c')
 839     {
 840       /* Type, _DECL and constant nodes have no interesting children.
 841          Ignore them.  */
 842       *walk_subtrees = 0;
 843     }
 844
 845
 846   return NULL_TREE;
 847 }
 848
 849
 850 /* Add VAR to the list of dereferenced variables.
 851
 852    WALK_STATE contains a hash table used to avoid adding the same
 853       variable more than once. Note that this function assumes that
 854       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 855       duplicate checking is done.  */
 856
 857 static void
 858 add_referenced_var (tree var, struct walk_state *walk_state)
 859 {
 860   void **slot;
 861   var_ann_t v_ann;
 862
 863   v_ann = get_var_ann (var);
 864
 865   if (walk_state)
 866     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 867   else
 868     slot = NULL;
 869
 870   if (slot == NULL || *slot == NULL)
 871     {
 872       /* This is the first time we find this variable, add it to the
 873          REFERENCED_VARS array and annotate it with attributes that are
 874          intrinsic to the variable.  */
 875       if (slot)
 876         *slot = (void *) var;
 877       v_ann->uid = num_referenced_vars;
 878       VARRAY_PUSH_TREE (referenced_vars, var);
 879
 880       /* Global and static variables are call-clobbered, always.  */
 881       if (needs_to_live_in_memory (var))
 882         mark_call_clobbered (var);
 883
 884       /* DECL_NONLOCAL variables should not be removed, as they are needed
 885          to emit nested functions.  */
 886       if (DECL_NONLOCAL (var))
 887         v_ann->used = 1;
 888     }
 889 }
 890
 891
 892 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 893
 894 tree
 895 get_virtual_var (tree var)
 896 {
 897   enum tree_code code;
 898
 899   STRIP_NOPS (var);
 900
 901   if (TREE_CODE (var) == SSA_NAME)
 902     var = SSA_NAME_VAR (var);
 903
 904   code = TREE_CODE (var);
 905
 906   while (code == ARRAY_REF
 907          || code == COMPONENT_REF
 908          || code == REALPART_EXPR
 909          || code == IMAGPART_EXPR)
 910     {
 911       var = TREE_OPERAND (var, 0);
 912       code = TREE_CODE (var);
 913     }
 914
 915 #ifdef ENABLE_CHECKING
 916   /* Treating GIMPLE registers as virtual variables makes no sense.
 917      Also complain if we couldn't extract a _DECL out of the original
 918      expression.  */
 919   if (!SSA_VAR_P (var)
 920       || is_gimple_reg (var))
 921     abort ();
 922 #endif
 923
 924   return var;
 925 }
 926
 927
 928 /* Mark variables in BLOCK that have hidden uses.  A hidden use can
 929    occur due to VLA declarations or nested functions.  */
 930
 931 static void
 932 find_hidden_use_vars (tree block)
 933 {
 934   tree sub, decl, tem;
 935
 936   /* Check all the arrays declared in the block for VLAs.
 937      While scanning the block's variables, also see if there is
 938      a nested function at this scope.  */
 939   for (decl = BLOCK_VARS (block); decl; decl = TREE_CHAIN (decl))
 940     {
 941       int inside_vla = 0;
 942       walk_tree (&decl, find_hidden_use_vars_r, &inside_vla, NULL);
 943     }
 944
 945   /* Now repeat the search in any sub-blocks.  */
 946   for (sub = BLOCK_SUBBLOCKS (block); sub; sub = TREE_CHAIN (sub))
 947     find_hidden_use_vars (sub);
 948
 949   /* A VLA parameter may use a variable which as set from another
 950      parameter to declare the size of the VLA.  We need to mark the
 951      variable as having a hidden use since it is used to declare the
 952      VLA parameter and that declaration is not seen by the SSA code.
 953
 954      Note get_pending_sizes clears the PENDING_SIZES chain, so we
 955      must restore it.  */
 956   tem = get_pending_sizes ();
 957   put_pending_sizes (tem);
 958   for (; tem; tem = TREE_CHAIN (tem))
 959     {
 960       int inside_vla = 1;
 961       walk_tree (&TREE_VALUE (tem), find_hidden_use_vars_r, &inside_vla, NULL);
 962     }
 963 }
 964
 965
 966 /* Callback for walk_tree used by find_hidden_use_vars to analyze each
 967    variable in a lexical block.  If the variable's size has a variable
 968    size, then mark all objects needed to compute the variable's size
 969    as having hidden uses.  */
 970
 971 static tree
 972 find_hidden_use_vars_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 973                         void *data ATTRIBUTE_UNUSED)
 974 {
 975   int *inside_vla = (int *) data;
 976
 977   /* We need to look for hidden uses due to VLAs in variable
 978      definitions.  We originally used to look for these hidden
 979      uses in the variable's type, but that's unreliable if the
 980      type's size contains a SAVE_EXPR for a different function
 981      context than the variable is used within.  */
 982   if (SSA_VAR_P (*tp)
 983       && ((DECL_SIZE (*tp)
 984            && ! really_constant_p (DECL_SIZE (*tp)))
 985           || (DECL_SIZE_UNIT (*tp)
 986               && ! really_constant_p (DECL_SIZE_UNIT (*tp)))))
 987     {
 988       int save = *inside_vla;
 989
 990       *inside_vla = 1;
 991       walk_tree (&DECL_SIZE (*tp), find_hidden_use_vars_r, inside_vla, NULL);
 992       walk_tree (&DECL_SIZE_UNIT (*tp), find_hidden_use_vars_r,
 993                  inside_vla, NULL);
 994       *inside_vla = save;
 995     }
 996   else if (*inside_vla && SSA_VAR_P (*tp))
 997     set_has_hidden_use (*tp);
 998
 999   return NULL_TREE;
1000 }
1001
1002
1003 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
1004    add_referenced_var, but is used by passes that need to add new temps to
1005    the REFERENCED_VARS array after the program has been scanned for
1006    variables.  The variable will just receive a new UID and be added
1007    to the REFERENCED_VARS array without checking for duplicates.  */
1008
1009 void
1010 add_referenced_tmp_var (tree var)
1011 {
1012   add_referenced_var (var, NULL);
1013 }
1014
1015
1016 /* Return true if VDEFS_AFTER contains fewer entries than VDEFS_BEFORE.
1017    Note that this assumes that both varrays are VDEF operands for the same
1018    statement.  */
1019
1020 static inline bool
1021 vdefs_disappeared_p (vdef_optype vdefs_before, vdef_optype vdefs_after)
1022 {
1023   /* If there was nothing before, nothing could've disappeared.  */
1024   if (vdefs_before == NULL)
1025     return false;
1026
1027   /* All/some of them gone.  */
1028   if (vdefs_after == NULL
1029       || NUM_VDEFS (vdefs_before) > NUM_VDEFS (vdefs_after))
1030     return true;
1031
1032   return false;
1033 }
1034
1035
1036 /* Add all the non-SSA variables found in STMT's operands to the bitmap
1037    VARS_TO_RENAME.  */
1038
1039 void
1040 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
1041 {
1042   def_optype defs;
1043   use_optype uses;
1044   vdef_optype vdefs;
1045   vuse_optype vuses;
1046   size_t i;
1047   bitmap vars_in_vops_to_rename;
1048   bool found_exposed_symbol = false;
1049   vdef_optype vdefs_before, vdefs_after;
1050   stmt_ann_t ann;
1051
1052   vars_in_vops_to_rename = BITMAP_XMALLOC ();
1053
1054   /* Before re-scanning the statement for operands, mark the existing
1055      virtual operands to be renamed again.  We do this because when new
1056      symbols are exposed, the virtual operands that were here before due to
1057      aliasing will probably be removed by the call to get_stmt_operand.
1058      Therefore, we need to flag them to be renamed beforehand.
1059
1060      We flag them in a separate bitmap because we don't really want to
1061      rename them if there are not any newly exposed symbols in the
1062      statement operands.  */
1063   ann = stmt_ann (stmt);
1064   vdefs_before = vdefs = VDEF_OPS (ann);
1065   for (i = 0; i < NUM_VDEFS (vdefs); i++)
1066     {
1067       tree var = VDEF_RESULT (vdefs, i);
1068       if (!DECL_P (var))
1069         var = SSA_NAME_VAR (var);
1070       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1071     }
1072
1073   vuses = VUSE_OPS (ann);
1074   for (i = 0; i < NUM_VUSES (vuses); i++)
1075     {
1076       tree var = VUSE_OP (vuses, i);
1077       if (!DECL_P (var))
1078         var = SSA_NAME_VAR (var);
1079       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1080     }
1081
1082   /* Now force an operand re-scan on the statement and mark any newly
1083      exposed variables.  */
1084   modify_stmt (stmt);
1085   get_stmt_operands (stmt);
1086
1087   defs = DEF_OPS (ann);
1088   for (i = 0; i < NUM_DEFS (defs); i++)
1089     {
1090       tree var = DEF_OP (defs, i);
1091       if (DECL_P (var))
1092         {
1093           found_exposed_symbol = true;
1094           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1095         }
1096     }
1097
1098   uses = USE_OPS (ann);
1099   for (i = 0; i < NUM_USES (uses); i++)
1100     {
1101       tree var = USE_OP (uses, i);
1102       if (DECL_P (var))
1103         {
1104           found_exposed_symbol = true;
1105           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1106         }
1107     }
1108
1109   vdefs_after = vdefs = VDEF_OPS (ann);
1110   for (i = 0; i < NUM_VDEFS (vdefs); i++)
1111     {
1112       tree var = VDEF_RESULT (vdefs, i);
1113       if (DECL_P (var))
1114         {
1115           found_exposed_symbol = true;
1116           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1117         }
1118     }
1119
1120   vuses = VUSE_OPS (ann);
1121   for (i = 0; i < NUM_VUSES (vuses); i++)
1122     {
1123       tree var = VUSE_OP (vuses, i);
1124       if (DECL_P (var))
1125         {
1126           found_exposed_symbol = true;
1127           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1128         }
1129     }
1130
1131   /* If we found any newly exposed symbols, or if there are fewer VDEF
1132      operands in the statement, add the variables we had set in
1133      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
1134      vanishing VDEFs because in those cases, the names that were formerly
1135      generated by this statement are not going to be available anymore.  */
1136   if (found_exposed_symbol
1137       || vdefs_disappeared_p (vdefs_before, vdefs_after))
1138     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
1139
1140   BITMAP_XFREE (vars_in_vops_to_rename);
1141 }