contrib/gcc-4.0/gcc/tree-dfa.c

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