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