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 /* Create a new annotation for an SSA name T.  */
 466
 467 ssa_name_ann_t
 468 create_ssa_name_ann (tree t)
 469 {
 470   ssa_name_ann_t ann;
 471
 472 #if defined ENABLE_CHECKING
 473   if (t == NULL_TREE
 474       || (t->common.ann
 475           && t->common.ann->common.type != SSA_NAME_ANN))
 476     abort ();
 477 #endif
 478
 479   ann = ggc_alloc (sizeof (*ann));
 480   memset ((void *) ann, 0, sizeof (*ann));
 481
 482   ann->common.type = SSA_NAME_ANN;
 483   t->common.ann = (tree_ann) ann;
 484
 485   return ann;
 486 }
 487
 488
 489 /* Build a temporary.  Make sure and register it to be renamed.  */
 490
 491 tree
 492 make_rename_temp (tree type, const char *prefix)
 493 {
 494   tree t = create_tmp_var (type, prefix);
 495   add_referenced_tmp_var (t);
 496   bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
 497   return t;
 498 }
 499
 500
 501
 502 /*---------------------------------------------------------------------------
 503                               Debugging functions
 504 ---------------------------------------------------------------------------*/
 505 /* Dump the list of all the referenced variables in the current function to
 506    FILE.  */
 507
 508 void
 509 dump_referenced_vars (FILE *file)
 510 {
 511   size_t i;
 512
 513   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 514            get_name (current_function_decl), (unsigned) num_referenced_vars);
 515
 516   for (i = 0; i < num_referenced_vars; i++)
 517     {
 518       tree var = referenced_var (i);
 519       fprintf (file, "Variable: ");
 520       dump_variable (file, var);
 521       fprintf (file, "\n");
 522     }
 523 }
 524
 525
 526 /* Dump the list of all the referenced variables to stderr.  */
 527
 528 void
 529 debug_referenced_vars (void)
 530 {
 531   dump_referenced_vars (stderr);
 532 }
 533
 534
 535 /* Dump variable VAR and its may-aliases to FILE.  */
 536
 537 void
 538 dump_variable (FILE *file, tree var)
 539 {
 540   var_ann_t ann;
 541
 542   if (var == NULL_TREE)
 543     {
 544       fprintf (file, "<nil>");
 545       return;
 546     }
 547
 548   print_generic_expr (file, var, dump_flags);
 549
 550   if (TREE_CODE (var) == SSA_NAME)
 551     var = SSA_NAME_VAR (var);
 552
 553   ann = var_ann (var);
 554
 555   fprintf (file, ", UID %u", (unsigned) ann->uid);
 556
 557   if (ann->has_hidden_use)
 558     fprintf (file, ", has hidden uses");
 559
 560   if (ann->type_mem_tag)
 561     {
 562       fprintf (file, ", type memory tag: ");
 563       print_generic_expr (file, ann->type_mem_tag, dump_flags);
 564     }
 565
 566   if (ann->is_alias_tag)
 567     fprintf (file, ", is an alias tag");
 568
 569   if (needs_to_live_in_memory (var))
 570     fprintf (file, ", is %s", TREE_STATIC (var) ? "static" : "global");
 571
 572   if (is_call_clobbered (var))
 573     fprintf (file, ", call clobbered");
 574
 575   if (ann->default_def)
 576     {
 577       fprintf (file, ", default def: ");
 578       print_generic_expr (file, ann->default_def, dump_flags);
 579     }
 580
 581   if (ann->may_aliases)
 582     {
 583       fprintf (file, ", may aliases: ");
 584       dump_may_aliases_for (file, var);
 585     }
 586
 587   fprintf (file, "\n");
 588 }
 589
 590
 591 /* Dump variable VAR and its may-aliases to stderr.  */
 592
 593 void
 594 debug_variable (tree var)
 595 {
 596   dump_variable (stderr, var);
 597 }
 598
 599
 600 /* Dump def-use edges on FILE.  */
 601
 602 void
 603 dump_immediate_uses (FILE *file)
 604 {
 605   basic_block bb;
 606   block_stmt_iterator si;
 607   const char *funcname
 608     = lang_hooks.decl_printable_name (current_function_decl, 2);
 609
 610   fprintf (file, "\nDef-use edges for function %s\n", funcname);
 611
 612   FOR_EACH_BB (bb)
 613     {
 614       tree phi;
 615
 616       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 617         dump_immediate_uses_for (file, phi);
 618
 619       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 620         dump_immediate_uses_for (file, bsi_stmt (si));
 621     }
 622
 623   fprintf (file, "\n");
 624 }
 625
 626
 627 /* Dump def-use edges on stderr.  */
 628
 629 void
 630 debug_immediate_uses (void)
 631 {
 632   dump_immediate_uses (stderr);
 633 }
 634
 635
 636 /* Dump all immediate uses for STMT on FILE.  */
 637
 638 void
 639 dump_immediate_uses_for (FILE *file, tree stmt)
 640 {
 641   dataflow_t df = get_immediate_uses (stmt);
 642   int num_imm_uses = num_immediate_uses (df);
 643
 644   if (num_imm_uses > 0)
 645     {
 646       int i;
 647
 648       fprintf (file, "-> ");
 649       print_generic_stmt (file, stmt, TDF_SLIM);
 650       fprintf (file, "\n");
 651
 652       for (i = 0; i < num_imm_uses; i++)
 653         {
 654           fprintf (file, "\t");
 655           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
 656           fprintf (file, "\n");
 657         }
 658
 659       fprintf (file, "\n");
 660     }
 661 }
 662
 663
 664 /* Dump immediate uses for STMT on stderr.  */
 665
 666 void
 667 debug_immediate_uses_for (tree stmt)
 668 {
 669   dump_immediate_uses_for (stderr, stmt);
 670 }
 671
 672
 673 /* Dump various DFA statistics to FILE.  */
 674
 675 void
 676 dump_dfa_stats (FILE *file)
 677 {
 678   struct dfa_stats_d dfa_stats;
 679
 680   unsigned long size, total = 0;
 681   const char * const fmt_str   = "%-30s%-13s%12s\n";
 682   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 683   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 684   const char *funcname
 685     = lang_hooks.decl_printable_name (current_function_decl, 2);
 686
 687   collect_dfa_stats (&dfa_stats);
 688
 689   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 690
 691   fprintf (file, "---------------------------------------------------------\n");
 692   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 693   fprintf (file, fmt_str, "", "  instances  ", "used ");
 694   fprintf (file, "---------------------------------------------------------\n");
 695
 696   size = num_referenced_vars * sizeof (tree);
 697   total += size;
 698   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
 699            SCALE (size), LABEL (size));
 700
 701   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 702   total += size;
 703   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 704            SCALE (size), LABEL (size));
 705
 706   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 707   total += size;
 708   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 709            SCALE (size), LABEL (size));
 710
 711   size = dfa_stats.num_uses * sizeof (tree *);
 712   total += size;
 713   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 714            SCALE (size), LABEL (size));
 715
 716   size = dfa_stats.num_defs * sizeof (tree *);
 717   total += size;
 718   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 719            SCALE (size), LABEL (size));
 720
 721   size = dfa_stats.num_vuses * sizeof (tree *);
 722   total += size;
 723   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 724            SCALE (size), LABEL (size));
 725
 726   size = dfa_stats.num_vdefs * sizeof (tree *);
 727   total += size;
 728   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 729            SCALE (size), LABEL (size));
 730
 731   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 732   total += size;
 733   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 734            SCALE (size), LABEL (size));
 735
 736   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 737   total += size;
 738   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 739            SCALE (size), LABEL (size));
 740
 741   fprintf (file, "---------------------------------------------------------\n");
 742   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 743            LABEL (total));
 744   fprintf (file, "---------------------------------------------------------\n");
 745   fprintf (file, "\n");
 746
 747   if (dfa_stats.num_phis)
 748     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 749              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 750              dfa_stats.max_num_phi_args);
 751
 752   fprintf (file, "\n");
 753 }
 754
 755
 756 /* Dump DFA statistics on stderr.  */
 757
 758 void
 759 debug_dfa_stats (void)
 760 {
 761   dump_dfa_stats (stderr);
 762 }
 763
 764
 765 /* Collect DFA statistics and store them in the structure pointed by
 766    DFA_STATS_P.  */
 767
 768 static void
 769 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 770 {
 771   htab_t htab;
 772   basic_block bb;
 773   block_stmt_iterator i;
 774
 775   if (dfa_stats_p == NULL)
 776     abort ();
 777
 778   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 779
 780   /* Walk all the trees in the function counting references.  Start at
 781      basic block 0, but don't stop at block boundaries.  */
 782   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
 783
 784   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
 785     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 786                (void *) htab);
 787
 788   htab_delete (htab);
 789
 790   FOR_EACH_BB (bb)
 791     {
 792       tree phi;
 793       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 794         {
 795           dfa_stats_p->num_phis++;
 796           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 797           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 798             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 799         }
 800     }
 801 }
 802
 803
 804 /* Callback for walk_tree to collect DFA statistics for a tree and its
 805    children.  */
 806
 807 static tree
 808 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 809                      void *data)
 810 {
 811   tree t = *tp;
 812   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 813
 814   if (t->common.ann)
 815     {
 816       switch (ann_type (t->common.ann))
 817         {
 818         case STMT_ANN:
 819           {
 820             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
 821             dfa_stats_p->num_stmt_anns++;
 822             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
 823             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
 824             dfa_stats_p->num_vdefs += NUM_VDEFS (VDEF_OPS (ann));
 825             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
 826             break;
 827           }
 828
 829         case VAR_ANN:
 830           dfa_stats_p->num_var_anns++;
 831           break;
 832
 833         default:
 834           break;
 835         }
 836     }
 837
 838   return NULL;
 839 }
 840
 841
 842 /*---------------------------------------------------------------------------
 843                              Miscellaneous helpers
 844 ---------------------------------------------------------------------------*/
 845 /* Callback for walk_tree.  Used to collect variables referenced in
 846    the function.  */
 847
 848 static tree
 849 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 850 {
 851   tree t = *tp;
 852   struct walk_state *walk_state = (struct walk_state *)data;
 853
 854   if (SSA_VAR_P (t))
 855     {
 856       /* If T is a regular variable that the optimizers are interested
 857          in, add it to the list of variables.  */
 858       add_referenced_var (t, walk_state);
 859     }
 860   else if (DECL_P (t)
 861            || TYPE_P (t)
 862            || TREE_CODE_CLASS (TREE_CODE (t)) == 'c')
 863     {
 864       /* Type, _DECL and constant nodes have no interesting children.
 865          Ignore them.  */
 866       *walk_subtrees = 0;
 867     }
 868
 869
 870   return NULL_TREE;
 871 }
 872
 873
 874 /* Add VAR to the list of dereferenced variables.
 875
 876    WALK_STATE contains a hash table used to avoid adding the same
 877       variable more than once. Note that this function assumes that
 878       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 879       duplicate checking is done.  */
 880
 881 static void
 882 add_referenced_var (tree var, struct walk_state *walk_state)
 883 {
 884   void **slot;
 885   var_ann_t v_ann;
 886
 887   v_ann = get_var_ann (var);
 888
 889   if (walk_state)
 890     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 891   else
 892     slot = NULL;
 893
 894   if (slot == NULL || *slot == NULL)
 895     {
 896       /* This is the first time we find this variable, add it to the
 897          REFERENCED_VARS array and annotate it with attributes that are
 898          intrinsic to the variable.  */
 899       if (slot)
 900         *slot = (void *) var;
 901       v_ann->uid = num_referenced_vars;
 902       VARRAY_PUSH_TREE (referenced_vars, var);
 903
 904       /* Global and static variables are call-clobbered, always.  */
 905       if (needs_to_live_in_memory (var))
 906         mark_call_clobbered (var);
 907
 908       /* DECL_NONLOCAL variables should not be removed, as they are needed
 909          to emit nested functions.  */
 910       if (DECL_NONLOCAL (var))
 911         v_ann->used = 1;
 912     }
 913 }
 914
 915
 916 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 917
 918 tree
 919 get_virtual_var (tree var)
 920 {
 921   enum tree_code code;
 922
 923   STRIP_NOPS (var);
 924
 925   if (TREE_CODE (var) == SSA_NAME)
 926     var = SSA_NAME_VAR (var);
 927
 928   code = TREE_CODE (var);
 929
 930   while (code == ARRAY_REF
 931          || code == COMPONENT_REF
 932          || code == REALPART_EXPR
 933          || code == IMAGPART_EXPR)
 934     {
 935       var = TREE_OPERAND (var, 0);
 936       code = TREE_CODE (var);
 937     }
 938
 939 #ifdef ENABLE_CHECKING
 940   /* Treating GIMPLE registers as virtual variables makes no sense.
 941      Also complain if we couldn't extract a _DECL out of the original
 942      expression.  */
 943   if (!SSA_VAR_P (var)
 944       || is_gimple_reg (var))
 945     abort ();
 946 #endif
 947
 948   return var;
 949 }
 950
 951
 952 /* Mark variables in BLOCK that have hidden uses.  A hidden use can
 953    occur due to VLA declarations or nested functions.   */
 954
 955 static void
 956 find_hidden_use_vars (tree block)
 957 {
 958   tree sub, decl, tem;
 959
 960   /* Check all the arrays declared in the block for VLAs.
 961      While scanning the block's variables, also see if there is
 962      a nested function at this scope.  */
 963   for (decl = BLOCK_VARS (block); decl; decl = TREE_CHAIN (decl))
 964     {
 965       int inside_vla = 0;
 966       walk_tree (&decl, find_hidden_use_vars_r, &inside_vla, NULL);
 967     }
 968
 969   /* Now repeat the search in any sub-blocks.  */
 970   for (sub = BLOCK_SUBBLOCKS (block); sub; sub = TREE_CHAIN (sub))
 971     find_hidden_use_vars (sub);
 972
 973   /* A VLA parameter may use a variable which as set from another
 974      parameter to declare the size of the VLA.  We need to mark the
 975      variable as having a hidden use since it is used to declare the
 976      VLA parameter and that declaration is not seen by the SSA code.
 977
 978      Note get_pending_sizes clears the PENDING_SIZES chain, so we
 979      must restore it. */
 980   tem = get_pending_sizes ();
 981   put_pending_sizes (tem);
 982   for (; tem; tem = TREE_CHAIN (tem))
 983     {
 984       int inside_vla = 1;
 985       walk_tree (&TREE_VALUE (tem), find_hidden_use_vars_r, &inside_vla, NULL);
 986     }
 987 }
 988
 989
 990 /* Callback for walk_tree used by find_hidden_use_vars to analyze each
 991    variable in a lexical block.  If the variable's size has a variable
 992    size, then mark all objects needed to compute the variable's size
 993    as having hidden uses.  */
 994
 995 static tree
 996 find_hidden_use_vars_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 997                         void *data ATTRIBUTE_UNUSED)
 998 {
 999   int *inside_vla = (int *) data;
1000
1001   /* We need to look for hidden uses due to VLAs in variable
1002      definitions.  We originally used to look for these hidden
1003      uses in the variable's type, but that's unreliable if the
1004      type's size contains a SAVE_EXPR for a different function
1005      context than the variable is used within.  */
1006   if (SSA_VAR_P (*tp)
1007       && ((DECL_SIZE (*tp)
1008            && ! really_constant_p (DECL_SIZE (*tp)))
1009           || (DECL_SIZE_UNIT (*tp)
1010               && ! really_constant_p (DECL_SIZE_UNIT (*tp)))))
1011     {
1012       int save = *inside_vla;
1013
1014       *inside_vla = 1;
1015       walk_tree (&DECL_SIZE (*tp), find_hidden_use_vars_r, inside_vla, NULL);
1016       walk_tree (&DECL_SIZE_UNIT (*tp), find_hidden_use_vars_r,
1017                  inside_vla, NULL);
1018       *inside_vla = save;
1019     }
1020   else if (*inside_vla && SSA_VAR_P (*tp))
1021     set_has_hidden_use (*tp);
1022
1023   return NULL_TREE;
1024 }
1025
1026
1027 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
1028    add_referenced_var, but is used by passes that need to add new temps to
1029    the REFERENCED_VARS array after the program has been scanned for
1030    variables.  The variable will just receive a new UID and be added
1031    to the REFERENCED_VARS array without checking for duplicates.  */
1032
1033 void
1034 add_referenced_tmp_var (tree var)
1035 {
1036   add_referenced_var (var, NULL);
1037 }
1038
1039
1040 /* Return true if VDEFS_AFTER contains fewer entries than VDEFS_BEFORE.
1041    Note that this assumes that both varrays are VDEF operands for the same
1042    statement.  */
1043
1044 static inline bool
1045 vdefs_disappeared_p (vdef_optype vdefs_before, vdef_optype vdefs_after)
1046 {
1047   /* If there was nothing before, nothing could've disappeared.  */
1048   if (vdefs_before == NULL)
1049     return false;
1050
1051   /* All/some of them gone.  */
1052   if (vdefs_after == NULL
1053       || NUM_VDEFS (vdefs_before) > NUM_VDEFS (vdefs_after))
1054     return true;
1055
1056   return false;
1057 }
1058
1059
1060 /* Add all the non-SSA variables found in STMT's operands to the bitmap
1061    VARS_TO_RENAME.  */
1062
1063 void
1064 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
1065 {
1066   def_optype defs;
1067   use_optype uses;
1068   vdef_optype vdefs;
1069   vuse_optype vuses;
1070   size_t i;
1071   bitmap vars_in_vops_to_rename;
1072   bool found_exposed_symbol = false;
1073   vdef_optype vdefs_before, vdefs_after;
1074   stmt_ann_t ann;
1075
1076   vars_in_vops_to_rename = BITMAP_XMALLOC ();
1077
1078   /* Before re-scanning the statement for operands, mark the existing
1079      virtual operands to be renamed again.  We do this because when new
1080      symbols are exposed, the virtual operands that were here before due to
1081      aliasing will probably be removed by the call to get_stmt_operand.
1082      Therefore, we need to flag them to be renamed beforehand.
1083
1084      We flag them in a separate bitmap because we don't really want to
1085      rename them if there are not any newly exposed symbols in the
1086      statement operands.  */
1087   ann = stmt_ann (stmt);
1088   vdefs_before = vdefs = VDEF_OPS (ann);
1089   for (i = 0; i < NUM_VDEFS (vdefs); i++)
1090     {
1091       tree var = VDEF_RESULT (vdefs, i);
1092       if (!DECL_P (var))
1093         var = SSA_NAME_VAR (var);
1094       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1095     }
1096
1097   vuses = VUSE_OPS (ann);
1098   for (i = 0; i < NUM_VUSES (vuses); i++)
1099     {
1100       tree var = VUSE_OP (vuses, i);
1101       if (!DECL_P (var))
1102         var = SSA_NAME_VAR (var);
1103       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1104     }
1105
1106   /* Now force an operand re-scan on the statement and mark any newly
1107      exposed variables.  */
1108   modify_stmt (stmt);
1109   get_stmt_operands (stmt);
1110
1111   defs = DEF_OPS (ann);
1112   for (i = 0; i < NUM_DEFS (defs); i++)
1113     {
1114       tree var = DEF_OP (defs, i);
1115       if (DECL_P (var))
1116         {
1117           found_exposed_symbol = true;
1118           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1119         }
1120     }
1121
1122   uses = USE_OPS (ann);
1123   for (i = 0; i < NUM_USES (uses); i++)
1124     {
1125       tree var = USE_OP (uses, i);
1126       if (DECL_P (var))
1127         {
1128           found_exposed_symbol = true;
1129           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1130         }
1131     }
1132
1133   vdefs_after = vdefs = VDEF_OPS (ann);
1134   for (i = 0; i < NUM_VDEFS (vdefs); i++)
1135     {
1136       tree var = VDEF_RESULT (vdefs, i);
1137       if (DECL_P (var))
1138         {
1139           found_exposed_symbol = true;
1140           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1141         }
1142     }
1143
1144   vuses = VUSE_OPS (ann);
1145   for (i = 0; i < NUM_VUSES (vuses); i++)
1146     {
1147       tree var = VUSE_OP (vuses, i);
1148       if (DECL_P (var))
1149         {
1150           found_exposed_symbol = true;
1151           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1152         }
1153     }
1154
1155   /* If we found any newly exposed symbols, or if there are fewer VDEF
1156      operands in the statement, add the variables we had set in
1157      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
1158      vanishing VDEFs because in those cases, the names that were formerly
1159      generated by this statement are not going to be available anymore.  */
1160   if (found_exposed_symbol
1161       || vdefs_disappeared_p (vdefs_before, vdefs_after))
1162     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
1163
1164   BITMAP_XFREE (vars_in_vops_to_rename);
1165 }