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