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