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