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 "pointer-set.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.h"
  34 #include "errors.h"
  35 #include "timevar.h"
  36 #include "expr.h"
  37 #include "ggc.h"
  38 #include "langhooks.h"
  39 #include "flags.h"
  40 #include "function.h"
  41 #include "diagnostic.h"
  42 #include "tree-dump.h"
  43 #include "tree-gimple.h"
  44 #include "tree-flow.h"
  45 #include "tree-inline.h"
  46 #include "tree-pass.h"
  47 #include "convert.h"
  48 #include "params.h"
  49 #include "cgraph.h"
  50
  51 /* Build and maintain data flow information for trees.  */
  52
  53 /* Counters used to display DFA and SSA statistics.  */
  54 struct dfa_stats_d
  55 {
  56   long num_stmt_anns;
  57   long num_var_anns;
  58   long num_defs;
  59   long num_uses;
  60   long num_phis;
  61   long num_phi_args;
  62   int max_num_phi_args;
  63   long num_v_may_defs;
  64   long num_vuses;
  65   long num_v_must_defs;
  66 };
  67
  68
  69 /* State information for find_vars_r.  */
  70 struct walk_state
  71 {
  72   /* Hash table used to avoid adding the same variable more than once.  */
  73   htab_t vars_found;
  74 };
  75
  76
  77 /* Local functions.  */
  78 static void collect_dfa_stats (struct dfa_stats_d *);
  79 static tree collect_dfa_stats_r (tree *, int *, void *);
  80 static void add_immediate_use (tree, tree);
  81 static tree find_vars_r (tree *, int *, void *);
  82 static void add_referenced_var (tree, struct walk_state *);
  83 static void compute_immediate_uses_for_phi (tree, bool (*)(tree));
  84 static void compute_immediate_uses_for_stmt (tree, int, bool (*)(tree));
  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
 112   cgraph_reset_static_var_maps ();
 113   vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
 114   memset (&walk_state, 0, sizeof (walk_state));
 115   walk_state.vars_found = vars_found;
 116
 117   FOR_EACH_BB (bb)
 118     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 119       {
 120         tree *stmt_p = bsi_stmt_ptr (si);
 121         walk_tree (stmt_p, find_vars_r, &walk_state, NULL);
 122       }
 123
 124   htab_delete (vars_found);
 125 }
 126
 127 struct tree_opt_pass pass_referenced_vars =
 128 {
 129   NULL,                                 /* name */
 130   NULL,                                 /* gate */
 131   find_referenced_vars,                 /* execute */
 132   NULL,                                 /* sub */
 133   NULL,                                 /* next */
 134   0,                                    /* static_pass_number */
 135   0,                                    /* tv_id */
 136   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 137   PROP_referenced_vars,                 /* properties_provided */
 138   0,                                    /* properties_destroyed */
 139   0,                                    /* todo_flags_start */
 140   0,                                    /* todo_flags_finish */
 141   0                                     /* letter */
 142 };
 143
 144
 145 /* Compute immediate uses.
 146
 147    CALC_FOR is an optional function pointer which indicates whether
 148       immediate uses information should be calculated for a given SSA
 149       variable.  If NULL, then information is computed for all
 150       variables.
 151
 152    FLAGS is one of {TDFA_USE_OPS, TDFA_USE_VOPS}.  It is used by
 153       compute_immediate_uses_for_stmt to determine whether to look at
 154       virtual and/or real operands while computing def-use chains.  */
 155
 156 void
 157 compute_immediate_uses (int flags, bool (*calc_for)(tree))
 158 {
 159   basic_block bb;
 160   block_stmt_iterator si;
 161
 162   FOR_EACH_BB (bb)
 163     {
 164       tree phi;
 165
 166       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 167         {
 168           if (is_gimple_reg (PHI_RESULT (phi)))
 169             {
 170               if (!(flags & TDFA_USE_OPS))
 171                 continue;
 172             }
 173           else
 174             {
 175               if (!(flags & TDFA_USE_VOPS))
 176                 continue;
 177             }
 178
 179           compute_immediate_uses_for_phi (phi, calc_for);
 180         }
 181
 182       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 183         {
 184           tree stmt = bsi_stmt (si);
 185           get_stmt_operands (stmt);
 186           compute_immediate_uses_for_stmt (stmt, flags, calc_for);
 187         }
 188     }
 189 }
 190
 191
 192 /* Invalidates dataflow information for a statement STMT.  */
 193
 194 void
 195 free_df_for_stmt (tree stmt)
 196 {
 197   dataflow_t *df;
 198
 199   if (TREE_CODE (stmt) == PHI_NODE)
 200     df = &PHI_DF (stmt);
 201   else
 202     {
 203       stmt_ann_t ann = stmt_ann (stmt);
 204
 205       if (!ann)
 206         return;
 207
 208       df = &ann->df;
 209     }
 210
 211   if (!*df)
 212     return;
 213
 214   /* If we have a varray of immediate uses, then go ahead and release
 215      it for re-use.  */
 216   if ((*df)->immediate_uses)
 217     ggc_free ((*df)->immediate_uses);
 218
 219   /* Similarly for the main dataflow structure.  */
 220   ggc_free (*df);
 221   *df = NULL;
 222 }
 223
 224
 225 /* Invalidate dataflow information for the whole function.
 226
 227    Note this only invalidates dataflow information on statements and
 228    PHI nodes which are reachable.
 229
 230    A deleted statement may still have attached dataflow information
 231    on it.  */
 232
 233 void
 234 free_df (void)
 235 {
 236   basic_block bb;
 237   block_stmt_iterator si;
 238
 239   FOR_EACH_BB (bb)
 240     {
 241       tree phi;
 242
 243       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 244         free_df_for_stmt (phi);
 245
 246       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 247         {
 248           tree stmt = bsi_stmt (si);
 249           free_df_for_stmt (stmt);
 250         }
 251     }
 252 }
 253
 254
 255 /* Helper for compute_immediate_uses.  Check all the USE and/or VUSE
 256    operands in phi node PHI and add a def-use edge between their
 257    defining statement and PHI.  CALC_FOR is as in
 258    compute_immediate_uses.
 259
 260    PHI nodes are easy, we only need to look at their arguments.  */
 261
 262 static void
 263 compute_immediate_uses_for_phi (tree phi, bool (*calc_for)(tree))
 264 {
 265   int i;
 266
 267   gcc_assert (TREE_CODE (phi) == PHI_NODE);
 268
 269   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 270     {
 271       tree arg = PHI_ARG_DEF (phi, i);
 272
 273       if (TREE_CODE (arg) == SSA_NAME && (!calc_for || calc_for (arg)))
 274         {
 275           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF (phi, i));
 276           if (!IS_EMPTY_STMT (imm_rdef_stmt))
 277             add_immediate_use (imm_rdef_stmt, phi);
 278         }
 279     }
 280 }
 281
 282
 283 /* Another helper for compute_immediate_uses.  Depending on the value
 284    of FLAGS, check all the USE and/or VUSE operands in STMT and add a
 285    def-use edge between their defining statement and STMT.  CALC_FOR
 286    is as in compute_immediate_uses.  */
 287
 288 static void
 289 compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
 290 {
 291   tree use;
 292   ssa_op_iter iter;
 293
 294   /* PHI nodes are handled elsewhere.  */
 295   gcc_assert (TREE_CODE (stmt) != PHI_NODE);
 296
 297   /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
 298   if (flags & TDFA_USE_OPS)
 299     {
 300       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 301         {
 302           tree imm_stmt = SSA_NAME_DEF_STMT (use);
 303           if (!IS_EMPTY_STMT (imm_stmt) && (!calc_for || calc_for (use)))
 304             add_immediate_use (imm_stmt, stmt);
 305         }
 306     }
 307
 308   if (flags & TDFA_USE_VOPS)
 309     {
 310       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
 311         {
 312           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (use);
 313           if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (use)))
 314             add_immediate_use (imm_rdef_stmt, stmt);
 315         }
 316     }
 317 }
 318
 319
 320 /* Add statement USE_STMT to the list of statements that use definitions
 321     made by STMT.  */
 322
 323 static void
 324 add_immediate_use (tree stmt, tree use_stmt)
 325 {
 326   struct dataflow_d **df;
 327
 328   if (TREE_CODE (stmt) == PHI_NODE)
 329     df = &PHI_DF (stmt);
 330   else
 331     {
 332       stmt_ann_t ann = get_stmt_ann (stmt);
 333       df = &ann->df;
 334     }
 335
 336   if (*df == NULL)
 337     {
 338       *df = ggc_alloc (sizeof (struct dataflow_d));
 339       memset ((void *) *df, 0, sizeof (struct dataflow_d));
 340       (*df)->uses[0] = use_stmt;
 341       return;
 342     }
 343
 344   if (!(*df)->uses[1])
 345     {
 346       (*df)->uses[1] = use_stmt;
 347       return;
 348     }
 349
 350   if ((*df)->immediate_uses == NULL)
 351     VARRAY_TREE_INIT ((*df)->immediate_uses, 4, "immediate_uses");
 352
 353   VARRAY_PUSH_TREE ((*df)->immediate_uses, use_stmt);
 354 }
 355
 356
 357 /* If the immediate use of USE points to OLD, then redirect it to NEW.  */
 358
 359 static void
 360 redirect_immediate_use (tree use, tree old, tree new)
 361 {
 362   tree imm_stmt = SSA_NAME_DEF_STMT (use);
 363   struct dataflow_d *df = get_immediate_uses (imm_stmt);
 364   unsigned int num_uses = num_immediate_uses (df);
 365   unsigned int i;
 366
 367   for (i = 0; i < num_uses; i++)
 368     {
 369       if (immediate_use (df, i) == old)
 370         {
 371           if (i == 0 || i == 1)
 372             df->uses[i] = new;
 373           else
 374             VARRAY_TREE (df->immediate_uses, i - 2) = new;
 375         }
 376     }
 377 }
 378
 379
 380 /* Redirect all immediate uses for operands in OLD so that they point
 381    to NEW.  This routine should have no knowledge of how immediate
 382    uses are stored.  */
 383
 384 void
 385 redirect_immediate_uses (tree old, tree new)
 386 {
 387   ssa_op_iter iter;
 388   tree val;
 389
 390   FOR_EACH_SSA_TREE_OPERAND (val, old, iter, SSA_OP_ALL_USES)
 391     redirect_immediate_use (val, old, new);
 392 }
 393
 394
 395 /*---------------------------------------------------------------------------
 396                             Manage annotations
 397 ---------------------------------------------------------------------------*/
 398 /* Create a new annotation for a _DECL node T.  */
 399
 400 var_ann_t
 401 create_var_ann (tree t)
 402 {
 403   var_ann_t ann;
 404
 405   gcc_assert (t);
 406   gcc_assert (DECL_P (t));
 407   gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
 408
 409   ann = ggc_alloc (sizeof (*ann));
 410   memset ((void *) ann, 0, sizeof (*ann));
 411
 412   ann->common.type = VAR_ANN;
 413
 414   t->common.ann = (tree_ann_t) ann;
 415
 416   return ann;
 417 }
 418
 419
 420 /* Create a new annotation for a statement node T.  */
 421
 422 stmt_ann_t
 423 create_stmt_ann (tree t)
 424 {
 425   stmt_ann_t ann;
 426
 427   gcc_assert (is_gimple_stmt (t));
 428   gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN);
 429
 430   ann = ggc_alloc (sizeof (*ann));
 431   memset ((void *) ann, 0, sizeof (*ann));
 432
 433   ann->common.type = STMT_ANN;
 434
 435   /* Since we just created the annotation, mark the statement modified.  */
 436   ann->modified = true;
 437
 438   t->common.ann = (tree_ann_t) ann;
 439
 440   return ann;
 441 }
 442
 443
 444 /* Create a new annotation for a tree T.  */
 445
 446 tree_ann_t
 447 create_tree_ann (tree t)
 448 {
 449   tree_ann_t ann;
 450
 451   gcc_assert (t);
 452   gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON);
 453
 454   ann = ggc_alloc (sizeof (*ann));
 455   memset ((void *) ann, 0, sizeof (*ann));
 456
 457   ann->common.type = TREE_ANN_COMMON;
 458   t->common.ann = ann;
 459
 460   return ann;
 461 }
 462
 463 /* Build a temporary.  Make sure and register it to be renamed.  */
 464
 465 tree
 466 make_rename_temp (tree type, const char *prefix)
 467 {
 468   tree t = create_tmp_var (type, prefix);
 469   if (referenced_vars)
 470     {
 471       add_referenced_tmp_var (t);
 472       bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
 473     }
 474   return t;
 475 }
 476
 477
 478
 479 /*---------------------------------------------------------------------------
 480                               Debugging functions
 481 ---------------------------------------------------------------------------*/
 482 /* Dump the list of all the referenced variables in the current function to
 483    FILE.  */
 484
 485 void
 486 dump_referenced_vars (FILE *file)
 487 {
 488   size_t i;
 489
 490   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 491            get_name (current_function_decl), (unsigned) num_referenced_vars);
 492
 493   for (i = 0; i < num_referenced_vars; i++)
 494     {
 495       tree var = referenced_var (i);
 496       fprintf (file, "Variable: ");
 497       dump_variable (file, var);
 498       fprintf (file, "\n");
 499     }
 500 }
 501
 502
 503 /* Dump the list of all the referenced variables to stderr.  */
 504
 505 void
 506 debug_referenced_vars (void)
 507 {
 508   dump_referenced_vars (stderr);
 509 }
 510
 511
 512 /* Dump variable VAR and its may-aliases to FILE.  */
 513
 514 void
 515 dump_variable (FILE *file, tree var)
 516 {
 517   var_ann_t ann;
 518
 519   if (TREE_CODE (var) == SSA_NAME)
 520     {
 521       if (POINTER_TYPE_P (TREE_TYPE (var)))
 522         dump_points_to_info_for (file, var);
 523       var = SSA_NAME_VAR (var);
 524     }
 525
 526   if (var == NULL_TREE)
 527     {
 528       fprintf (file, "<nil>");
 529       return;
 530     }
 531
 532   print_generic_expr (file, var, dump_flags);
 533
 534   ann = var_ann (var);
 535
 536   fprintf (file, ", UID %u", (unsigned) ann->uid);
 537
 538   fprintf (file, ", ");
 539   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 540
 541   if (ann->type_mem_tag)
 542     {
 543       fprintf (file, ", type memory tag: ");
 544       print_generic_expr (file, ann->type_mem_tag, dump_flags);
 545     }
 546
 547   if (ann->is_alias_tag)
 548     fprintf (file, ", is an alias tag");
 549
 550   if (TREE_ADDRESSABLE (var))
 551     fprintf (file, ", is addressable");
 552
 553   if (is_global_var (var))
 554     fprintf (file, ", is global");
 555
 556   if (TREE_THIS_VOLATILE (var))
 557     fprintf (file, ", is volatile");
 558
 559   if (is_call_clobbered (var))
 560     fprintf (file, ", call clobbered");
 561
 562   if (ann->default_def)
 563     {
 564       fprintf (file, ", default def: ");
 565       print_generic_expr (file, ann->default_def, dump_flags);
 566     }
 567
 568   if (ann->may_aliases)
 569     {
 570       fprintf (file, ", may aliases: ");
 571       dump_may_aliases_for (file, var);
 572     }
 573
 574   fprintf (file, "\n");
 575 }
 576
 577
 578 /* Dump variable VAR and its may-aliases to stderr.  */
 579
 580 void
 581 debug_variable (tree var)
 582 {
 583   dump_variable (stderr, var);
 584 }
 585
 586
 587 /* Dump def-use edges on FILE.  */
 588
 589 void
 590 dump_immediate_uses (FILE *file)
 591 {
 592   basic_block bb;
 593   block_stmt_iterator si;
 594   const char *funcname
 595     = lang_hooks.decl_printable_name (current_function_decl, 2);
 596
 597   fprintf (file, "\nDef-use edges for function %s\n", funcname);
 598
 599   FOR_EACH_BB (bb)
 600     {
 601       tree phi;
 602
 603       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 604         dump_immediate_uses_for (file, phi);
 605
 606       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 607         dump_immediate_uses_for (file, bsi_stmt (si));
 608     }
 609
 610   fprintf (file, "\n");
 611 }
 612
 613
 614 /* Dump def-use edges on stderr.  */
 615
 616 void
 617 debug_immediate_uses (void)
 618 {
 619   dump_immediate_uses (stderr);
 620 }
 621
 622
 623 /* Dump all immediate uses for STMT on FILE.  */
 624
 625 void
 626 dump_immediate_uses_for (FILE *file, tree stmt)
 627 {
 628   dataflow_t df = get_immediate_uses (stmt);
 629   int num_imm_uses = num_immediate_uses (df);
 630
 631   if (num_imm_uses > 0)
 632     {
 633       int i;
 634
 635       fprintf (file, "-> ");
 636       print_generic_stmt (file, stmt, TDF_SLIM);
 637       fprintf (file, "\n");
 638
 639       for (i = 0; i < num_imm_uses; i++)
 640         {
 641           fprintf (file, "\t");
 642           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
 643           fprintf (file, "\n");
 644         }
 645
 646       fprintf (file, "\n");
 647     }
 648 }
 649
 650
 651 /* Dump immediate uses for STMT on stderr.  */
 652
 653 void
 654 debug_immediate_uses_for (tree stmt)
 655 {
 656   dump_immediate_uses_for (stderr, stmt);
 657 }
 658
 659
 660 /* Dump various DFA statistics to FILE.  */
 661
 662 void
 663 dump_dfa_stats (FILE *file)
 664 {
 665   struct dfa_stats_d dfa_stats;
 666
 667   unsigned long size, total = 0;
 668   const char * const fmt_str   = "%-30s%-13s%12s\n";
 669   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 670   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 671   const char *funcname
 672     = lang_hooks.decl_printable_name (current_function_decl, 2);
 673
 674   collect_dfa_stats (&dfa_stats);
 675
 676   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 677
 678   fprintf (file, "---------------------------------------------------------\n");
 679   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 680   fprintf (file, fmt_str, "", "  instances  ", "used ");
 681   fprintf (file, "---------------------------------------------------------\n");
 682
 683   size = num_referenced_vars * sizeof (tree);
 684   total += size;
 685   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
 686            SCALE (size), LABEL (size));
 687
 688   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 689   total += size;
 690   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 691            SCALE (size), LABEL (size));
 692
 693   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 694   total += size;
 695   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 696            SCALE (size), LABEL (size));
 697
 698   size = dfa_stats.num_uses * sizeof (tree *);
 699   total += size;
 700   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 701            SCALE (size), LABEL (size));
 702
 703   size = dfa_stats.num_defs * sizeof (tree *);
 704   total += size;
 705   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 706            SCALE (size), LABEL (size));
 707
 708   size = dfa_stats.num_vuses * sizeof (tree *);
 709   total += size;
 710   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 711            SCALE (size), LABEL (size));
 712
 713   size = dfa_stats.num_v_may_defs * sizeof (tree *);
 714   total += size;
 715   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
 716            SCALE (size), LABEL (size));
 717
 718   size = dfa_stats.num_v_must_defs * sizeof (tree *);
 719   total += size;
 720   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
 721            SCALE (size), LABEL (size));
 722
 723   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 724   total += size;
 725   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 726            SCALE (size), LABEL (size));
 727
 728   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 729   total += size;
 730   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 731            SCALE (size), LABEL (size));
 732
 733   fprintf (file, "---------------------------------------------------------\n");
 734   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 735            LABEL (total));
 736   fprintf (file, "---------------------------------------------------------\n");
 737   fprintf (file, "\n");
 738
 739   if (dfa_stats.num_phis)
 740     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 741              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 742              dfa_stats.max_num_phi_args);
 743
 744   fprintf (file, "\n");
 745 }
 746
 747
 748 /* Dump DFA statistics on stderr.  */
 749
 750 void
 751 debug_dfa_stats (void)
 752 {
 753   dump_dfa_stats (stderr);
 754 }
 755
 756
 757 /* Collect DFA statistics and store them in the structure pointed by
 758    DFA_STATS_P.  */
 759
 760 static void
 761 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 762 {
 763   struct pointer_set_t *pset;
 764   basic_block bb;
 765   block_stmt_iterator i;
 766
 767   gcc_assert (dfa_stats_p);
 768
 769   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 770
 771   /* Walk all the trees in the function counting references.  Start at
 772      basic block 0, but don't stop at block boundaries.  */
 773   pset = pointer_set_create ();
 774
 775   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
 776     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 777                pset);
 778
 779   pointer_set_destroy (pset);
 780
 781   FOR_EACH_BB (bb)
 782     {
 783       tree phi;
 784       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 785         {
 786           dfa_stats_p->num_phis++;
 787           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 788           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 789             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 790         }
 791     }
 792 }
 793
 794
 795 /* Callback for walk_tree to collect DFA statistics for a tree and its
 796    children.  */
 797
 798 static tree
 799 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 800                      void *data)
 801 {
 802   tree t = *tp;
 803   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 804
 805   if (t->common.ann)
 806     {
 807       switch (ann_type (t->common.ann))
 808         {
 809         case STMT_ANN:
 810           {
 811             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
 812             dfa_stats_p->num_stmt_anns++;
 813             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
 814             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
 815             dfa_stats_p->num_v_may_defs +=
 816                          NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann));
 817             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
 818             dfa_stats_p->num_v_must_defs +=
 819                          NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann));
 820             break;
 821           }
 822
 823         case VAR_ANN:
 824           dfa_stats_p->num_var_anns++;
 825           break;
 826
 827         default:
 828           break;
 829         }
 830     }
 831
 832   return NULL;
 833 }
 834
 835
 836 /*---------------------------------------------------------------------------
 837                              Miscellaneous helpers
 838 ---------------------------------------------------------------------------*/
 839 /* Callback for walk_tree.  Used to collect variables referenced in
 840    the function.  */
 841
 842 static tree
 843 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 844 {
 845   struct walk_state *walk_state = (struct walk_state *) data;
 846
 847   /* If T is a regular variable that the optimizers are interested
 848      in, add it to the list of variables.  */
 849   if (SSA_VAR_P (*tp))
 850     add_referenced_var (*tp, walk_state);
 851
 852   /* Type, _DECL and constant nodes have no interesting children.
 853      Ignore them.  */
 854   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 855     *walk_subtrees = 0;
 856
 857   return NULL_TREE;
 858 }
 859
 860
 861 /* Add VAR to the list of dereferenced variables.
 862
 863    WALK_STATE contains a hash table used to avoid adding the same
 864       variable more than once. Note that this function assumes that
 865       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 866       duplicate checking is done.  */
 867
 868 static void
 869 add_referenced_var (tree var, struct walk_state *walk_state)
 870 {
 871   void **slot;
 872   var_ann_t v_ann;
 873
 874   v_ann = get_var_ann (var);
 875
 876   if (walk_state)
 877     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 878   else
 879     slot = NULL;
 880
 881   if (slot == NULL || *slot == NULL)
 882     {
 883       /* This is the first time we find this variable, add it to the
 884          REFERENCED_VARS array and annotate it with attributes that are
 885          intrinsic to the variable.  */
 886       if (slot)
 887         *slot = (void *) var;
 888       v_ann->uid = num_referenced_vars;
 889       VARRAY_PUSH_TREE (referenced_vars, var);
 890
 891       /* Global variables are always call-clobbered.  */
 892       if (is_global_var (var))
 893         mark_call_clobbered (var);
 894
 895       /* Scan DECL_INITIAL for pointer variables as they may contain
 896          address arithmetic referencing the address of other
 897          variables.  */
 898       if (DECL_INITIAL (var)
 899           && POINTER_TYPE_P (TREE_TYPE (var)))
 900         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
 901     }
 902 }
 903
 904
 905 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 906
 907 tree
 908 get_virtual_var (tree var)
 909 {
 910   STRIP_NOPS (var);
 911
 912   if (TREE_CODE (var) == SSA_NAME)
 913     var = SSA_NAME_VAR (var);
 914
 915   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 916          || handled_component_p (var))
 917     var = TREE_OPERAND (var, 0);
 918
 919   /* Treating GIMPLE registers as virtual variables makes no sense.
 920      Also complain if we couldn't extract a _DECL out of the original
 921      expression.  */
 922   gcc_assert (SSA_VAR_P (var));
 923   gcc_assert (!is_gimple_reg (var));
 924
 925   return var;
 926 }
 927
 928 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
 929    add_referenced_var, but is used by passes that need to add new temps to
 930    the REFERENCED_VARS array after the program has been scanned for
 931    variables.  The variable will just receive a new UID and be added
 932    to the REFERENCED_VARS array without checking for duplicates.  */
 933
 934 void
 935 add_referenced_tmp_var (tree var)
 936 {
 937   add_referenced_var (var, NULL);
 938 }
 939
 940
 941 /* Add all the non-SSA variables found in STMT's operands to the bitmap
 942    VARS_TO_RENAME.  */
 943
 944 void
 945 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
 946 {
 947   ssa_op_iter iter;
 948   tree val;
 949   bitmap vars_in_vops_to_rename;
 950   bool found_exposed_symbol = false;
 951   int v_may_defs_before, v_may_defs_after;
 952   int v_must_defs_before, v_must_defs_after;
 953
 954   vars_in_vops_to_rename = BITMAP_XMALLOC ();
 955
 956   /* Before re-scanning the statement for operands, mark the existing
 957      virtual operands to be renamed again.  We do this because when new
 958      symbols are exposed, the virtual operands that were here before due to
 959      aliasing will probably be removed by the call to get_stmt_operand.
 960      Therefore, we need to flag them to be renamed beforehand.
 961
 962      We flag them in a separate bitmap because we don't really want to
 963      rename them if there are not any newly exposed symbols in the
 964      statement operands.  */
 965   v_may_defs_before = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
 966   v_must_defs_before = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
 967
 968   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
 969                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
 970     {
 971       if (!DECL_P (val))
 972         val = SSA_NAME_VAR (val);
 973       bitmap_set_bit (vars_in_vops_to_rename, var_ann (val)->uid);
 974     }
 975
 976   /* Now force an operand re-scan on the statement and mark any newly
 977      exposed variables.  */
 978   modify_stmt (stmt);
 979   get_stmt_operands (stmt);
 980
 981   v_may_defs_after = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
 982   v_must_defs_after = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
 983
 984   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS)
 985     {
 986       if (DECL_P (val))
 987         {
 988           found_exposed_symbol = true;
 989           bitmap_set_bit (vars_to_rename, var_ann (val)->uid);
 990         }
 991     }
 992
 993   /* If we found any newly exposed symbols, or if there are fewer VDEF
 994      operands in the statement, add the variables we had set in
 995      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
 996      vanishing VDEFs because in those cases, the names that were formerly
 997      generated by this statement are not going to be available anymore.  */
 998   if (found_exposed_symbol
 999       || v_may_defs_before > v_may_defs_after
1000       || v_must_defs_before > v_must_defs_after)
1001     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
1002
1003   BITMAP_XFREE (vars_in_vops_to_rename);
1004 }
1005
1006 /* Find all variables within the gimplified statement that were not previously
1007    visible to the function and add them to the referenced variables list.  */
1008
1009 static tree
1010 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
1011                             void *data ATTRIBUTE_UNUSED)
1012 {
1013   tree t = *tp;
1014
1015   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
1016     add_referenced_tmp_var (t);
1017
1018   if (IS_TYPE_OR_DECL_P (t))
1019     *walk_subtrees = 0;
1020
1021   return NULL;
1022 }
1023
1024 void
1025 find_new_referenced_vars (tree *stmt_p)
1026 {
1027   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
1028 }