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