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 (TREE_ADDRESSABLE (var))
 566     fprintf (file, ", is addressable");
 567
 568   if (is_global_var (var))
 569     fprintf (file, ", is global");
 570
 571   if (is_call_clobbered (var))
 572     fprintf (file, ", call clobbered");
 573
 574   if (ann->default_def)
 575     {
 576       fprintf (file, ", default def: ");
 577       print_generic_expr (file, ann->default_def, dump_flags);
 578     }
 579
 580   if (ann->may_aliases)
 581     {
 582       fprintf (file, ", may aliases: ");
 583       dump_may_aliases_for (file, var);
 584     }
 585
 586   fprintf (file, "\n");
 587 }
 588
 589
 590 /* Dump variable VAR and its may-aliases to stderr.  */
 591
 592 void
 593 debug_variable (tree var)
 594 {
 595   dump_variable (stderr, var);
 596 }
 597
 598
 599 /* Dump def-use edges on FILE.  */
 600
 601 void
 602 dump_immediate_uses (FILE *file)
 603 {
 604   basic_block bb;
 605   block_stmt_iterator si;
 606   const char *funcname
 607     = lang_hooks.decl_printable_name (current_function_decl, 2);
 608
 609   fprintf (file, "\nDef-use edges for function %s\n", funcname);
 610
 611   FOR_EACH_BB (bb)
 612     {
 613       tree phi;
 614
 615       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 616         dump_immediate_uses_for (file, phi);
 617
 618       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 619         dump_immediate_uses_for (file, bsi_stmt (si));
 620     }
 621
 622   fprintf (file, "\n");
 623 }
 624
 625
 626 /* Dump def-use edges on stderr.  */
 627
 628 void
 629 debug_immediate_uses (void)
 630 {
 631   dump_immediate_uses (stderr);
 632 }
 633
 634
 635 /* Dump all immediate uses for STMT on FILE.  */
 636
 637 void
 638 dump_immediate_uses_for (FILE *file, tree stmt)
 639 {
 640   dataflow_t df = get_immediate_uses (stmt);
 641   int num_imm_uses = num_immediate_uses (df);
 642
 643   if (num_imm_uses > 0)
 644     {
 645       int i;
 646
 647       fprintf (file, "-> ");
 648       print_generic_stmt (file, stmt, TDF_SLIM);
 649       fprintf (file, "\n");
 650
 651       for (i = 0; i < num_imm_uses; i++)
 652         {
 653           fprintf (file, "\t");
 654           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
 655           fprintf (file, "\n");
 656         }
 657
 658       fprintf (file, "\n");
 659     }
 660 }
 661
 662
 663 /* Dump immediate uses for STMT on stderr.  */
 664
 665 void
 666 debug_immediate_uses_for (tree stmt)
 667 {
 668   dump_immediate_uses_for (stderr, stmt);
 669 }
 670
 671
 672 /* Dump various DFA statistics to FILE.  */
 673
 674 void
 675 dump_dfa_stats (FILE *file)
 676 {
 677   struct dfa_stats_d dfa_stats;
 678
 679   unsigned long size, total = 0;
 680   const char * const fmt_str   = "%-30s%-13s%12s\n";
 681   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 682   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 683   const char *funcname
 684     = lang_hooks.decl_printable_name (current_function_decl, 2);
 685
 686   collect_dfa_stats (&dfa_stats);
 687
 688   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 689
 690   fprintf (file, "---------------------------------------------------------\n");
 691   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 692   fprintf (file, fmt_str, "", "  instances  ", "used ");
 693   fprintf (file, "---------------------------------------------------------\n");
 694
 695   size = num_referenced_vars * sizeof (tree);
 696   total += size;
 697   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
 698            SCALE (size), LABEL (size));
 699
 700   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 701   total += size;
 702   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 703            SCALE (size), LABEL (size));
 704
 705   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 706   total += size;
 707   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 708            SCALE (size), LABEL (size));
 709
 710   size = dfa_stats.num_uses * sizeof (tree *);
 711   total += size;
 712   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 713            SCALE (size), LABEL (size));
 714
 715   size = dfa_stats.num_defs * sizeof (tree *);
 716   total += size;
 717   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 718            SCALE (size), LABEL (size));
 719
 720   size = dfa_stats.num_vuses * sizeof (tree *);
 721   total += size;
 722   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 723            SCALE (size), LABEL (size));
 724
 725   size = dfa_stats.num_v_may_defs * sizeof (tree *);
 726   total += size;
 727   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
 728            SCALE (size), LABEL (size));
 729
 730   size = dfa_stats.num_v_must_defs * sizeof (tree *);
 731   total += size;
 732   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
 733            SCALE (size), LABEL (size));
 734
 735   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 736   total += size;
 737   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 738            SCALE (size), LABEL (size));
 739
 740   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 741   total += size;
 742   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 743            SCALE (size), LABEL (size));
 744
 745   fprintf (file, "---------------------------------------------------------\n");
 746   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 747            LABEL (total));
 748   fprintf (file, "---------------------------------------------------------\n");
 749   fprintf (file, "\n");
 750
 751   if (dfa_stats.num_phis)
 752     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 753              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 754              dfa_stats.max_num_phi_args);
 755
 756   fprintf (file, "\n");
 757 }
 758
 759
 760 /* Dump DFA statistics on stderr.  */
 761
 762 void
 763 debug_dfa_stats (void)
 764 {
 765   dump_dfa_stats (stderr);
 766 }
 767
 768
 769 /* Collect DFA statistics and store them in the structure pointed by
 770    DFA_STATS_P.  */
 771
 772 static void
 773 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 774 {
 775   htab_t htab;
 776   basic_block bb;
 777   block_stmt_iterator i;
 778
 779   if (dfa_stats_p == NULL)
 780     abort ();
 781
 782   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 783
 784   /* Walk all the trees in the function counting references.  Start at
 785      basic block 0, but don't stop at block boundaries.  */
 786   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
 787
 788   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
 789     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 790                (void *) htab);
 791
 792   htab_delete (htab);
 793
 794   FOR_EACH_BB (bb)
 795     {
 796       tree phi;
 797       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 798         {
 799           dfa_stats_p->num_phis++;
 800           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 801           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 802             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 803         }
 804     }
 805 }
 806
 807
 808 /* Callback for walk_tree to collect DFA statistics for a tree and its
 809    children.  */
 810
 811 static tree
 812 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 813                      void *data)
 814 {
 815   tree t = *tp;
 816   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 817
 818   if (t->common.ann)
 819     {
 820       switch (ann_type (t->common.ann))
 821         {
 822         case STMT_ANN:
 823           {
 824             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
 825             dfa_stats_p->num_stmt_anns++;
 826             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
 827             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
 828             dfa_stats_p->num_v_may_defs +=
 829                          NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann));
 830             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
 831             dfa_stats_p->num_v_must_defs +=
 832                          NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann));
 833             break;
 834           }
 835
 836         case VAR_ANN:
 837           dfa_stats_p->num_var_anns++;
 838           break;
 839
 840         default:
 841           break;
 842         }
 843     }
 844
 845   return NULL;
 846 }
 847
 848
 849 /*---------------------------------------------------------------------------
 850                              Miscellaneous helpers
 851 ---------------------------------------------------------------------------*/
 852 /* Callback for walk_tree.  Used to collect variables referenced in
 853    the function.  */
 854
 855 static tree
 856 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 857 {
 858   struct walk_state *walk_state = (struct walk_state *) data;
 859
 860   /* If T is a regular variable that the optimizers are interested
 861      in, add it to the list of variables.  */
 862   if (SSA_VAR_P (*tp))
 863     add_referenced_var (*tp, walk_state);
 864
 865   /* Type, _DECL and constant nodes have no interesting children.
 866      Ignore them.  */
 867   else if (DECL_P (*tp)
 868            || TYPE_P (*tp)
 869            || TREE_CODE_CLASS (TREE_CODE (*tp)) == 'c')
 870     *walk_subtrees = 0;
 871
 872   return NULL_TREE;
 873 }
 874
 875
 876 /* Add VAR to the list of dereferenced variables.
 877
 878    WALK_STATE contains a hash table used to avoid adding the same
 879       variable more than once. Note that this function assumes that
 880       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 881       duplicate checking is done.  */
 882
 883 static void
 884 add_referenced_var (tree var, struct walk_state *walk_state)
 885 {
 886   void **slot;
 887   var_ann_t v_ann;
 888
 889   v_ann = get_var_ann (var);
 890
 891   if (walk_state)
 892     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 893   else
 894     slot = NULL;
 895
 896   if (slot == NULL || *slot == NULL)
 897     {
 898       /* This is the first time we find this variable, add it to the
 899          REFERENCED_VARS array and annotate it with attributes that are
 900          intrinsic to the variable.  */
 901       if (slot)
 902         *slot = (void *) var;
 903       v_ann->uid = num_referenced_vars;
 904       VARRAY_PUSH_TREE (referenced_vars, var);
 905
 906       /* Global variables are always call-clobbered.  */
 907       if (is_global_var (var))
 908         mark_call_clobbered (var);
 909
 910       /* If an initialized global variable then register the initializer
 911          as well.  */
 912       if (POINTER_TYPE_P (TREE_TYPE (var))
 913           && TREE_READONLY (var)
 914           && DECL_INITIAL (var)
 915           && TREE_CODE (DECL_INITIAL (var)) == ADDR_EXPR)
 916         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
 917     }
 918 }
 919
 920
 921 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 922
 923 tree
 924 get_virtual_var (tree var)
 925 {
 926   STRIP_NOPS (var);
 927
 928   if (TREE_CODE (var) == SSA_NAME)
 929     var = SSA_NAME_VAR (var);
 930
 931   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 932          || handled_component_p (var))
 933     var = TREE_OPERAND (var, 0);
 934
 935 #ifdef ENABLE_CHECKING
 936   /* Treating GIMPLE registers as virtual variables makes no sense.
 937      Also complain if we couldn't extract a _DECL out of the original
 938      expression.  */
 939   if (!SSA_VAR_P (var)
 940       || is_gimple_reg (var))
 941     abort ();
 942 #endif
 943
 944   return var;
 945 }
 946
 947 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
 948    add_referenced_var, but is used by passes that need to add new temps to
 949    the REFERENCED_VARS array after the program has been scanned for
 950    variables.  The variable will just receive a new UID and be added
 951    to the REFERENCED_VARS array without checking for duplicates.  */
 952
 953 void
 954 add_referenced_tmp_var (tree var)
 955 {
 956   add_referenced_var (var, NULL);
 957 }
 958
 959 /* Return true if V_MAY_DEFS_AFTER contains fewer entries than
 960    V_MAY_DEFS_BEFORE. Note that this assumes that both varrays
 961    are V_MAY_DEF operands for the same statement.  */
 962
 963 static inline bool
 964 v_may_defs_disappeared_p (v_may_def_optype v_may_defs_before,
 965                           v_may_def_optype v_may_defs_after)
 966 {
 967   /* If there was nothing before, nothing could've disappeared.  */
 968   if (v_may_defs_before == NULL)
 969     return false;
 970
 971   /* All/some of them gone.  */
 972   if (v_may_defs_after == NULL
 973       || NUM_V_MAY_DEFS (v_may_defs_before) >
 974          NUM_V_MAY_DEFS (v_may_defs_after))
 975     return true;
 976
 977   return false;
 978 }
 979
 980 /* Return true if V_MUST_DEFS_AFTER contains fewer entries than
 981    V_MUST_DEFS_BEFORE. Note that this assumes that both varrays
 982    are V_MUST_DEF operands for the same statement.  */
 983
 984 static inline bool
 985 v_must_defs_disappeared_p (v_must_def_optype v_must_defs_before,
 986                            v_must_def_optype v_must_defs_after)
 987 {
 988   /* If there was nothing before, nothing could've disappeared.  */
 989   if (v_must_defs_before == NULL)
 990     return false;
 991
 992   /* All/some of them gone.  */
 993   if (v_must_defs_after == NULL
 994       || NUM_V_MUST_DEFS (v_must_defs_before) >
 995          NUM_V_MUST_DEFS (v_must_defs_after))
 996     return true;
 997
 998   return false;
 999 }
1000
1001
1002 /* Add all the non-SSA variables found in STMT's operands to the bitmap
1003    VARS_TO_RENAME.  */
1004
1005 void
1006 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
1007 {
1008   def_optype defs;
1009   use_optype uses;
1010   v_may_def_optype v_may_defs;
1011   vuse_optype vuses;
1012   v_must_def_optype v_must_defs;
1013   size_t i;
1014   bitmap vars_in_vops_to_rename;
1015   bool found_exposed_symbol = false;
1016   v_may_def_optype v_may_defs_before, v_may_defs_after;
1017   v_must_def_optype v_must_defs_before, v_must_defs_after;
1018   stmt_ann_t ann;
1019
1020   vars_in_vops_to_rename = BITMAP_XMALLOC ();
1021
1022   /* Before re-scanning the statement for operands, mark the existing
1023      virtual operands to be renamed again.  We do this because when new
1024      symbols are exposed, the virtual operands that were here before due to
1025      aliasing will probably be removed by the call to get_stmt_operand.
1026      Therefore, we need to flag them to be renamed beforehand.
1027
1028      We flag them in a separate bitmap because we don't really want to
1029      rename them if there are not any newly exposed symbols in the
1030      statement operands.  */
1031   ann = stmt_ann (stmt);
1032   v_may_defs_before = v_may_defs = V_MAY_DEF_OPS (ann);
1033   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1034     {
1035       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1036       if (!DECL_P (var))
1037         var = SSA_NAME_VAR (var);
1038       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1039     }
1040
1041   vuses = VUSE_OPS (ann);
1042   for (i = 0; i < NUM_VUSES (vuses); i++)
1043     {
1044       tree var = VUSE_OP (vuses, i);
1045       if (!DECL_P (var))
1046         var = SSA_NAME_VAR (var);
1047       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1048     }
1049
1050   v_must_defs_before = v_must_defs = V_MUST_DEF_OPS (ann);
1051   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1052     {
1053       tree var = V_MUST_DEF_OP (v_must_defs, i);
1054       if (!DECL_P (var))
1055         var = SSA_NAME_VAR (var);
1056       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1057     }
1058
1059   /* Now force an operand re-scan on the statement and mark any newly
1060      exposed variables.  */
1061   modify_stmt (stmt);
1062   get_stmt_operands (stmt);
1063
1064   defs = DEF_OPS (ann);
1065   for (i = 0; i < NUM_DEFS (defs); i++)
1066     {
1067       tree var = DEF_OP (defs, i);
1068       if (DECL_P (var))
1069         {
1070           found_exposed_symbol = true;
1071           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1072         }
1073     }
1074
1075   uses = USE_OPS (ann);
1076   for (i = 0; i < NUM_USES (uses); i++)
1077     {
1078       tree var = USE_OP (uses, i);
1079       if (DECL_P (var))
1080         {
1081           found_exposed_symbol = true;
1082           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1083         }
1084     }
1085
1086   v_may_defs_after = v_may_defs = V_MAY_DEF_OPS (ann);
1087   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1088     {
1089       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1090       if (DECL_P (var))
1091         {
1092           found_exposed_symbol = true;
1093           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1094         }
1095     }
1096
1097   vuses = VUSE_OPS (ann);
1098   for (i = 0; i < NUM_VUSES (vuses); i++)
1099     {
1100       tree var = VUSE_OP (vuses, i);
1101       if (DECL_P (var))
1102         {
1103           found_exposed_symbol = true;
1104           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1105         }
1106     }
1107
1108   v_must_defs_after = v_must_defs = V_MUST_DEF_OPS (ann);
1109   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1110     {
1111       tree var = V_MUST_DEF_OP (v_must_defs, i);
1112       if (DECL_P (var))
1113         {
1114           found_exposed_symbol = true;
1115           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1116         }
1117     }
1118
1119   /* If we found any newly exposed symbols, or if there are fewer VDEF
1120      operands in the statement, add the variables we had set in
1121      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
1122      vanishing VDEFs because in those cases, the names that were formerly
1123      generated by this statement are not going to be available anymore.  */
1124   if (found_exposed_symbol
1125       || v_may_defs_disappeared_p (v_may_defs_before, v_may_defs_after)
1126       || v_must_defs_disappeared_p (v_must_defs_before, v_must_defs_after))
1127     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
1128
1129   BITMAP_XFREE (vars_in_vops_to_rename);
1130 }