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   if (ann->type_mem_tag)
 532     {
 533       fprintf (file, ", type memory tag: ");
 534       print_generic_expr (file, ann->type_mem_tag, dump_flags);
 535     }
 536
 537   if (ann->is_alias_tag)
 538     fprintf (file, ", is an alias tag");
 539
 540   if (TREE_ADDRESSABLE (var))
 541     fprintf (file, ", is addressable");
 542
 543   if (is_global_var (var))
 544     fprintf (file, ", is global");
 545
 546   if (is_call_clobbered (var))
 547     fprintf (file, ", call clobbered");
 548
 549   if (ann->default_def)
 550     {
 551       fprintf (file, ", default def: ");
 552       print_generic_expr (file, ann->default_def, dump_flags);
 553     }
 554
 555   if (ann->may_aliases)
 556     {
 557       fprintf (file, ", may aliases: ");
 558       dump_may_aliases_for (file, var);
 559     }
 560
 561   fprintf (file, "\n");
 562 }
 563
 564
 565 /* Dump variable VAR and its may-aliases to stderr.  */
 566
 567 void
 568 debug_variable (tree var)
 569 {
 570   dump_variable (stderr, var);
 571 }
 572
 573
 574 /* Dump def-use edges on FILE.  */
 575
 576 void
 577 dump_immediate_uses (FILE *file)
 578 {
 579   basic_block bb;
 580   block_stmt_iterator si;
 581   const char *funcname
 582     = lang_hooks.decl_printable_name (current_function_decl, 2);
 583
 584   fprintf (file, "\nDef-use edges for function %s\n", funcname);
 585
 586   FOR_EACH_BB (bb)
 587     {
 588       tree phi;
 589
 590       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 591         dump_immediate_uses_for (file, phi);
 592
 593       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 594         dump_immediate_uses_for (file, bsi_stmt (si));
 595     }
 596
 597   fprintf (file, "\n");
 598 }
 599
 600
 601 /* Dump def-use edges on stderr.  */
 602
 603 void
 604 debug_immediate_uses (void)
 605 {
 606   dump_immediate_uses (stderr);
 607 }
 608
 609
 610 /* Dump all immediate uses for STMT on FILE.  */
 611
 612 void
 613 dump_immediate_uses_for (FILE *file, tree stmt)
 614 {
 615   dataflow_t df = get_immediate_uses (stmt);
 616   int num_imm_uses = num_immediate_uses (df);
 617
 618   if (num_imm_uses > 0)
 619     {
 620       int i;
 621
 622       fprintf (file, "-> ");
 623       print_generic_stmt (file, stmt, TDF_SLIM);
 624       fprintf (file, "\n");
 625
 626       for (i = 0; i < num_imm_uses; i++)
 627         {
 628           fprintf (file, "\t");
 629           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
 630           fprintf (file, "\n");
 631         }
 632
 633       fprintf (file, "\n");
 634     }
 635 }
 636
 637
 638 /* Dump immediate uses for STMT on stderr.  */
 639
 640 void
 641 debug_immediate_uses_for (tree stmt)
 642 {
 643   dump_immediate_uses_for (stderr, stmt);
 644 }
 645
 646
 647 /* Dump various DFA statistics to FILE.  */
 648
 649 void
 650 dump_dfa_stats (FILE *file)
 651 {
 652   struct dfa_stats_d dfa_stats;
 653
 654   unsigned long size, total = 0;
 655   const char * const fmt_str   = "%-30s%-13s%12s\n";
 656   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 657   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 658   const char *funcname
 659     = lang_hooks.decl_printable_name (current_function_decl, 2);
 660
 661   collect_dfa_stats (&dfa_stats);
 662
 663   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 664
 665   fprintf (file, "---------------------------------------------------------\n");
 666   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 667   fprintf (file, fmt_str, "", "  instances  ", "used ");
 668   fprintf (file, "---------------------------------------------------------\n");
 669
 670   size = num_referenced_vars * sizeof (tree);
 671   total += size;
 672   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
 673            SCALE (size), LABEL (size));
 674
 675   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 676   total += size;
 677   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 678            SCALE (size), LABEL (size));
 679
 680   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 681   total += size;
 682   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 683            SCALE (size), LABEL (size));
 684
 685   size = dfa_stats.num_uses * sizeof (tree *);
 686   total += size;
 687   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 688            SCALE (size), LABEL (size));
 689
 690   size = dfa_stats.num_defs * sizeof (tree *);
 691   total += size;
 692   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 693            SCALE (size), LABEL (size));
 694
 695   size = dfa_stats.num_vuses * sizeof (tree *);
 696   total += size;
 697   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 698            SCALE (size), LABEL (size));
 699
 700   size = dfa_stats.num_v_may_defs * sizeof (tree *);
 701   total += size;
 702   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
 703            SCALE (size), LABEL (size));
 704
 705   size = dfa_stats.num_v_must_defs * sizeof (tree *);
 706   total += size;
 707   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
 708            SCALE (size), LABEL (size));
 709
 710   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 711   total += size;
 712   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 713            SCALE (size), LABEL (size));
 714
 715   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 716   total += size;
 717   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 718            SCALE (size), LABEL (size));
 719
 720   fprintf (file, "---------------------------------------------------------\n");
 721   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 722            LABEL (total));
 723   fprintf (file, "---------------------------------------------------------\n");
 724   fprintf (file, "\n");
 725
 726   if (dfa_stats.num_phis)
 727     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 728              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 729              dfa_stats.max_num_phi_args);
 730
 731   fprintf (file, "\n");
 732 }
 733
 734
 735 /* Dump DFA statistics on stderr.  */
 736
 737 void
 738 debug_dfa_stats (void)
 739 {
 740   dump_dfa_stats (stderr);
 741 }
 742
 743
 744 /* Collect DFA statistics and store them in the structure pointed by
 745    DFA_STATS_P.  */
 746
 747 static void
 748 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 749 {
 750   htab_t htab;
 751   basic_block bb;
 752   block_stmt_iterator i;
 753
 754   gcc_assert (dfa_stats_p);
 755
 756   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 757
 758   /* Walk all the trees in the function counting references.  Start at
 759      basic block 0, but don't stop at block boundaries.  */
 760   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
 761
 762   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
 763     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 764                (void *) htab);
 765
 766   htab_delete (htab);
 767
 768   FOR_EACH_BB (bb)
 769     {
 770       tree phi;
 771       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 772         {
 773           dfa_stats_p->num_phis++;
 774           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 775           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 776             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 777         }
 778     }
 779 }
 780
 781
 782 /* Callback for walk_tree to collect DFA statistics for a tree and its
 783    children.  */
 784
 785 static tree
 786 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 787                      void *data)
 788 {
 789   tree t = *tp;
 790   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 791
 792   if (t->common.ann)
 793     {
 794       switch (ann_type (t->common.ann))
 795         {
 796         case STMT_ANN:
 797           {
 798             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
 799             dfa_stats_p->num_stmt_anns++;
 800             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
 801             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
 802             dfa_stats_p->num_v_may_defs +=
 803                          NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann));
 804             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
 805             dfa_stats_p->num_v_must_defs +=
 806                          NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann));
 807             break;
 808           }
 809
 810         case VAR_ANN:
 811           dfa_stats_p->num_var_anns++;
 812           break;
 813
 814         default:
 815           break;
 816         }
 817     }
 818
 819   return NULL;
 820 }
 821
 822
 823 /*---------------------------------------------------------------------------
 824                              Miscellaneous helpers
 825 ---------------------------------------------------------------------------*/
 826 /* Callback for walk_tree.  Used to collect variables referenced in
 827    the function.  */
 828
 829 static tree
 830 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 831 {
 832   struct walk_state *walk_state = (struct walk_state *) data;
 833
 834   /* If T is a regular variable that the optimizers are interested
 835      in, add it to the list of variables.  */
 836   if (SSA_VAR_P (*tp))
 837     add_referenced_var (*tp, walk_state);
 838
 839   /* Type, _DECL and constant nodes have no interesting children.
 840      Ignore them.  */
 841   else if (DECL_P (*tp)
 842            || TYPE_P (*tp)
 843            || TREE_CODE_CLASS (TREE_CODE (*tp)) == 'c')
 844     *walk_subtrees = 0;
 845
 846   return NULL_TREE;
 847 }
 848
 849
 850 /* Add VAR to the list of dereferenced variables.
 851
 852    WALK_STATE contains a hash table used to avoid adding the same
 853       variable more than once. Note that this function assumes that
 854       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 855       duplicate checking is done.  */
 856
 857 static void
 858 add_referenced_var (tree var, struct walk_state *walk_state)
 859 {
 860   void **slot;
 861   var_ann_t v_ann;
 862
 863   v_ann = get_var_ann (var);
 864
 865   if (walk_state)
 866     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 867   else
 868     slot = NULL;
 869
 870   if (slot == NULL || *slot == NULL)
 871     {
 872       /* This is the first time we find this variable, add it to the
 873          REFERENCED_VARS array and annotate it with attributes that are
 874          intrinsic to the variable.  */
 875       if (slot)
 876         *slot = (void *) var;
 877       v_ann->uid = num_referenced_vars;
 878       VARRAY_PUSH_TREE (referenced_vars, var);
 879
 880       /* Global variables are always call-clobbered.  */
 881       if (is_global_var (var))
 882         mark_call_clobbered (var);
 883
 884       /* If an initialized global variable then register the initializer
 885          as well.  */
 886       if (POINTER_TYPE_P (TREE_TYPE (var))
 887           && TREE_READONLY (var)
 888           && DECL_INITIAL (var)
 889           && TREE_CODE (DECL_INITIAL (var)) == ADDR_EXPR)
 890         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
 891     }
 892 }
 893
 894
 895 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 896
 897 tree
 898 get_virtual_var (tree var)
 899 {
 900   STRIP_NOPS (var);
 901
 902   if (TREE_CODE (var) == SSA_NAME)
 903     var = SSA_NAME_VAR (var);
 904
 905   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 906          || handled_component_p (var))
 907     var = TREE_OPERAND (var, 0);
 908
 909   /* Treating GIMPLE registers as virtual variables makes no sense.
 910      Also complain if we couldn't extract a _DECL out of the original
 911      expression.  */
 912   gcc_assert (SSA_VAR_P (var));
 913   gcc_assert (!is_gimple_reg (var));
 914
 915   return var;
 916 }
 917
 918 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
 919    add_referenced_var, but is used by passes that need to add new temps to
 920    the REFERENCED_VARS array after the program has been scanned for
 921    variables.  The variable will just receive a new UID and be added
 922    to the REFERENCED_VARS array without checking for duplicates.  */
 923
 924 void
 925 add_referenced_tmp_var (tree var)
 926 {
 927   add_referenced_var (var, NULL);
 928 }
 929
 930
 931 /* Add all the non-SSA variables found in STMT's operands to the bitmap
 932    VARS_TO_RENAME.  */
 933
 934 void
 935 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
 936 {
 937   ssa_op_iter iter;
 938   tree val;
 939   bitmap vars_in_vops_to_rename;
 940   bool found_exposed_symbol = false;
 941   int v_may_defs_before, v_may_defs_after;
 942   int v_must_defs_before, v_must_defs_after;
 943
 944   vars_in_vops_to_rename = BITMAP_XMALLOC ();
 945
 946   /* Before re-scanning the statement for operands, mark the existing
 947      virtual operands to be renamed again.  We do this because when new
 948      symbols are exposed, the virtual operands that were here before due to
 949      aliasing will probably be removed by the call to get_stmt_operand.
 950      Therefore, we need to flag them to be renamed beforehand.
 951
 952      We flag them in a separate bitmap because we don't really want to
 953      rename them if there are not any newly exposed symbols in the
 954      statement operands.  */
 955   v_may_defs_before = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
 956   v_must_defs_before = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
 957
 958   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
 959                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
 960     {
 961       if (!DECL_P (val))
 962         val = SSA_NAME_VAR (val);
 963       bitmap_set_bit (vars_in_vops_to_rename, var_ann (val)->uid);
 964     }
 965
 966   /* Now force an operand re-scan on the statement and mark any newly
 967      exposed variables.  */
 968   modify_stmt (stmt);
 969   get_stmt_operands (stmt);
 970
 971   v_may_defs_after = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
 972   v_must_defs_after = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
 973
 974   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
 975                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
 976
 977     {
 978       if (DECL_P (val))
 979         {
 980           found_exposed_symbol = true;
 981           bitmap_set_bit (vars_to_rename, var_ann (val)->uid);
 982         }
 983     }
 984
 985   /* If we found any newly exposed symbols, or if there are fewer VDEF
 986      operands in the statement, add the variables we had set in
 987      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
 988      vanishing VDEFs because in those cases, the names that were formerly
 989      generated by this statement are not going to be available anymore.  */
 990   if (found_exposed_symbol
 991       || v_may_defs_before > v_may_defs_after
 992       || v_must_defs_before > v_must_defs_after)
 993     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
 994
 995   BITMAP_XFREE (vars_in_vops_to_rename);
 996 }