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