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 static void find_hidden_use_vars (tree);
  85 static tree find_hidden_use_vars_r (tree *, int *, void *);
  86
  87
  88 /* Global declarations.  */
  89
  90 /* Array of all variables referenced in the function.  */
  91 varray_type referenced_vars;
  92
  93
  94 /*---------------------------------------------------------------------------
  95                         Dataflow analysis (DFA) routines
  96 ---------------------------------------------------------------------------*/
  97 /* Find all the variables referenced in the function.  This function
  98    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
  99
 100    Note that this function does not look for statement operands, it simply
 101    determines what variables are referenced in the program and detects
 102    various attributes for each variable used by alias analysis and the
 103    optimizer.  */
 104
 105 static void
 106 find_referenced_vars (void)
 107 {
 108   htab_t vars_found;
 109   basic_block bb;
 110   block_stmt_iterator si;
 111   struct walk_state walk_state;
 112   tree block;
 113
 114   /* Walk the lexical blocks in the function looking for variables that may
 115      have been used to declare VLAs and for nested functions.  Both
 116      constructs create hidden uses of variables.
 117
 118      Note that at this point we may have multiple blocks hung off
 119      DECL_INITIAL chained through the BLOCK_CHAIN field due to
 120      how inlining works.  Egad.  */
 121   block = DECL_INITIAL (current_function_decl);
 122   while (block)
 123     {
 124       find_hidden_use_vars (block);
 125       block = BLOCK_CHAIN (block);
 126     }
 127
 128   vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
 129   memset (&walk_state, 0, sizeof (walk_state));
 130   walk_state.vars_found = vars_found;
 131
 132   FOR_EACH_BB (bb)
 133     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 134       {
 135         tree *stmt_p = bsi_stmt_ptr (si);
 136         walk_tree (stmt_p, find_vars_r, &walk_state, NULL);
 137       }
 138
 139   htab_delete (vars_found);
 140 }
 141
 142 struct tree_opt_pass pass_referenced_vars =
 143 {
 144   NULL,                                 /* name */
 145   NULL,                                 /* gate */
 146   find_referenced_vars,                 /* execute */
 147   NULL,                                 /* sub */
 148   NULL,                                 /* next */
 149   0,                                    /* static_pass_number */
 150   0,                                    /* tv_id */
 151   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 152   PROP_referenced_vars,                 /* properties_provided */
 153   0,                                    /* properties_destroyed */
 154   0,                                    /* todo_flags_start */
 155   0,                                    /* todo_flags_finish */
 156 };
 157
 158
 159 /* Compute immediate uses.
 160
 161    CALC_FOR is an optional function pointer which indicates whether
 162       immediate uses information should be calculated for a given SSA
 163       variable.  If NULL, then information is computed for all
 164       variables.
 165
 166    FLAGS is one of {TDFA_USE_OPS, TDFA_USE_VOPS}.  It is used by
 167       compute_immediate_uses_for_stmt to determine whether to look at
 168       virtual and/or real operands while computing def-use chains.  */
 169
 170 void
 171 compute_immediate_uses (int flags, bool (*calc_for)(tree))
 172 {
 173   basic_block bb;
 174   block_stmt_iterator si;
 175
 176   FOR_EACH_BB (bb)
 177     {
 178       tree phi;
 179
 180       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 181         compute_immediate_uses_for_phi (phi, calc_for);
 182
 183       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 184         {
 185           tree stmt = bsi_stmt (si);
 186           get_stmt_operands (stmt);
 187           compute_immediate_uses_for_stmt (stmt, flags, calc_for);
 188         }
 189     }
 190 }
 191
 192
 193 /* Invalidates dataflow information for a statement STMT.  */
 194
 195 static void
 196 free_df_for_stmt (tree stmt)
 197 {
 198   stmt_ann_t ann = stmt_ann (stmt);
 199
 200   if (ann && ann->df)
 201     {
 202       /* If we have a varray of immediate uses, then go ahead and release
 203          it for re-use.  */
 204       if (ann->df->immediate_uses)
 205         ggc_free (ann->df->immediate_uses);
 206
 207       /* Similarly for the main dataflow structure.  */
 208       ggc_free (ann->df);
 209       ann->df = NULL;
 210     }
 211 }
 212
 213
 214 /* Invalidate dataflow information for the whole function.  */
 215
 216 void
 217 free_df (void)
 218 {
 219   basic_block bb;
 220   block_stmt_iterator si;
 221
 222   FOR_EACH_BB (bb)
 223     {
 224       tree phi;
 225
 226       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 227         free_df_for_stmt (phi);
 228
 229       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 230         {
 231           tree stmt = bsi_stmt (si);
 232           free_df_for_stmt (stmt);
 233         }
 234     }
 235 }
 236
 237
 238 /* Helper for compute_immediate_uses.  Check all the USE and/or VUSE
 239    operands in phi node PHI and add a def-use edge between their
 240    defining statement and PHI.  CALC_FOR is as in
 241    compute_immediate_uses.
 242
 243    PHI nodes are easy, we only need to look at their arguments.  */
 244
 245 static void
 246 compute_immediate_uses_for_phi (tree phi, bool (*calc_for)(tree))
 247 {
 248   int i;
 249
 250 #ifdef ENABLE_CHECKING
 251   if (TREE_CODE (phi) != PHI_NODE)
 252     abort ();
 253 #endif
 254
 255   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 256     {
 257       tree arg = PHI_ARG_DEF (phi, i);
 258
 259       if (TREE_CODE (arg) == SSA_NAME && (!calc_for || calc_for (arg)))
 260         {
 261           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF (phi, i));
 262           if (!IS_EMPTY_STMT (imm_rdef_stmt))
 263             add_immediate_use (imm_rdef_stmt, phi);
 264         }
 265     }
 266 }
 267
 268
 269 /* Another helper for compute_immediate_uses.  Depending on the value
 270    of FLAGS, check all the USE and/or VUSE operands in STMT and add a
 271    def-use edge between their defining statement and STMT.  CALC_FOR
 272    is as in compute_immediate_uses.  */
 273
 274 static void
 275 compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
 276 {
 277   size_t i;
 278   use_optype uses;
 279   vuse_optype vuses;
 280   v_may_def_optype v_may_defs;
 281   stmt_ann_t ann;
 282
 283 #ifdef ENABLE_CHECKING
 284   /* PHI nodes are handled elsewhere.  */
 285   if (TREE_CODE (stmt) == PHI_NODE)
 286     abort ();
 287 #endif
 288
 289   /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
 290   ann = stmt_ann (stmt);
 291   if (flags & TDFA_USE_OPS)
 292     {
 293       uses = USE_OPS (ann);
 294       for (i = 0; i < NUM_USES (uses); i++)
 295         {
 296           tree use = USE_OP (uses, i);
 297           tree imm_stmt = SSA_NAME_DEF_STMT (use);
 298           if (!IS_EMPTY_STMT (imm_stmt) && (!calc_for || calc_for (use)))
 299             add_immediate_use (imm_stmt, stmt);
 300         }
 301     }
 302
 303   if (flags & TDFA_USE_VOPS)
 304     {
 305       vuses = VUSE_OPS (ann);
 306       for (i = 0; i < NUM_VUSES (vuses); i++)
 307         {
 308           tree vuse = VUSE_OP (vuses, i);
 309           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
 310           if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
 311             add_immediate_use (imm_rdef_stmt, stmt);
 312         }
 313
 314       v_may_defs = V_MAY_DEF_OPS (ann);
 315       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 316         {
 317           tree vuse = V_MAY_DEF_OP (v_may_defs, i);
 318           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (vuse);
 319           if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (vuse)))
 320             add_immediate_use (imm_rdef_stmt, stmt);
 321         }
 322     }
 323 }
 324
 325
 326 /* Add statement USE_STMT to the list of statements that use definitions
 327     made by STMT.  */
 328
 329 static void
 330 add_immediate_use (tree stmt, tree use_stmt)
 331 {
 332   stmt_ann_t ann = get_stmt_ann (stmt);
 333   struct dataflow_d *df;
 334
 335   df = ann->df;
 336   if (df == NULL)
 337     {
 338       df = ann->df = ggc_alloc (sizeof (struct dataflow_d));
 339       memset ((void *) df, 0, sizeof (struct dataflow_d));
 340       df->uses[0] = use_stmt;
 341       return;
 342     }
 343
 344   if (!df->uses[1])
 345     {
 346       df->uses[1] = use_stmt;
 347       return;
 348     }
 349
 350   if (ann->df->immediate_uses == NULL)
 351     VARRAY_TREE_INIT (ann->df->immediate_uses, 4, "immediate_uses");
 352
 353   VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
 354 }
 355
 356
 357 /* If the immediate use of USE points to OLD, then redirect it to NEW.  */
 358
 359 static void
 360 redirect_immediate_use (tree use, tree old, tree new)
 361 {
 362   tree imm_stmt = SSA_NAME_DEF_STMT (use);
 363   struct dataflow_d *df = get_stmt_ann (imm_stmt)->df;
 364   unsigned int num_uses = num_immediate_uses (df);
 365   unsigned int i;
 366
 367   for (i = 0; i < num_uses; i++)
 368     {
 369       if (immediate_use (df, i) == old)
 370         {
 371           if (i == 0 || i == 1)
 372             df->uses[i] = new;
 373           else
 374             VARRAY_TREE (df->immediate_uses, i - 2) = new;
 375         }
 376     }
 377 }
 378
 379
 380 /* Redirect all immediate uses for operands in OLD so that they point
 381    to NEW.  This routine should have no knowledge of how immediate
 382    uses are stored.  */
 383
 384 void
 385 redirect_immediate_uses (tree old, tree new)
 386 {
 387   stmt_ann_t ann = get_stmt_ann (old);
 388   use_optype uses = USE_OPS (ann);
 389   vuse_optype vuses = VUSE_OPS (ann);
 390   v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
 391   unsigned int i;
 392
 393   /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
 394   for (i = 0; i < NUM_USES (uses); i++)
 395     redirect_immediate_use (USE_OP (uses, i), old, new);
 396
 397   for (i = 0; i < NUM_VUSES (vuses); i++)
 398     redirect_immediate_use (VUSE_OP (vuses, i), old, new);
 399
 400   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 401     redirect_immediate_use (V_MAY_DEF_OP (v_may_defs, i), old, new);
 402 }
 403
 404
 405 /*---------------------------------------------------------------------------
 406                             Manage annotations
 407 ---------------------------------------------------------------------------*/
 408 /* Create a new annotation for a _DECL node T.  */
 409
 410 var_ann_t
 411 create_var_ann (tree t)
 412 {
 413   var_ann_t ann;
 414
 415 #if defined ENABLE_CHECKING
 416   if (t == NULL_TREE
 417       || !DECL_P (t)
 418       || (t->common.ann
 419           && t->common.ann->common.type != VAR_ANN))
 420     abort ();
 421 #endif
 422
 423   ann = ggc_alloc (sizeof (*ann));
 424   memset ((void *) ann, 0, sizeof (*ann));
 425
 426   ann->common.type = VAR_ANN;
 427
 428   t->common.ann = (tree_ann_t) ann;
 429
 430   return ann;
 431 }
 432
 433
 434 /* Create a new annotation for a statement node T.  */
 435
 436 stmt_ann_t
 437 create_stmt_ann (tree t)
 438 {
 439   stmt_ann_t ann;
 440
 441 #if defined ENABLE_CHECKING
 442   if ((!is_gimple_stmt (t))
 443       || (t->common.ann
 444           && t->common.ann->common.type != STMT_ANN))
 445     abort ();
 446 #endif
 447
 448   ann = ggc_alloc (sizeof (*ann));
 449   memset ((void *) ann, 0, sizeof (*ann));
 450
 451   ann->common.type = STMT_ANN;
 452
 453   /* Since we just created the annotation, mark the statement modified.  */
 454   ann->modified = true;
 455
 456   t->common.ann = (tree_ann_t) ann;
 457
 458   return ann;
 459 }
 460
 461
 462 /* Create a new annotation for a tree T.  */
 463
 464 tree_ann_t
 465 create_tree_ann (tree t)
 466 {
 467   tree_ann_t ann;
 468
 469 #if defined ENABLE_CHECKING
 470   if (t == NULL_TREE
 471       || (t->common.ann
 472           && t->common.ann->common.type != TREE_ANN_COMMON))
 473     abort ();
 474 #endif
 475
 476   ann = ggc_alloc (sizeof (*ann));
 477   memset ((void *) ann, 0, sizeof (*ann));
 478
 479   ann->common.type = TREE_ANN_COMMON;
 480   t->common.ann = ann;
 481
 482   return ann;
 483 }
 484
 485 /* Build a temporary.  Make sure and register it to be renamed.  */
 486
 487 tree
 488 make_rename_temp (tree type, const char *prefix)
 489 {
 490   tree t = create_tmp_var (type, prefix);
 491   add_referenced_tmp_var (t);
 492   bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
 493   return t;
 494 }
 495
 496
 497
 498 /*---------------------------------------------------------------------------
 499                               Debugging functions
 500 ---------------------------------------------------------------------------*/
 501 /* Dump the list of all the referenced variables in the current function to
 502    FILE.  */
 503
 504 void
 505 dump_referenced_vars (FILE *file)
 506 {
 507   size_t i;
 508
 509   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 510            get_name (current_function_decl), (unsigned) num_referenced_vars);
 511
 512   for (i = 0; i < num_referenced_vars; i++)
 513     {
 514       tree var = referenced_var (i);
 515       fprintf (file, "Variable: ");
 516       dump_variable (file, var);
 517       fprintf (file, "\n");
 518     }
 519 }
 520
 521
 522 /* Dump the list of all the referenced variables to stderr.  */
 523
 524 void
 525 debug_referenced_vars (void)
 526 {
 527   dump_referenced_vars (stderr);
 528 }
 529
 530
 531 /* Dump variable VAR and its may-aliases to FILE.  */
 532
 533 void
 534 dump_variable (FILE *file, tree var)
 535 {
 536   var_ann_t ann;
 537
 538   if (var == NULL_TREE)
 539     {
 540       fprintf (file, "<nil>");
 541       return;
 542     }
 543
 544   print_generic_expr (file, var, dump_flags);
 545
 546   if (TREE_CODE (var) == SSA_NAME)
 547     var = SSA_NAME_VAR (var);
 548
 549   ann = var_ann (var);
 550
 551   fprintf (file, ", UID %u", (unsigned) ann->uid);
 552
 553   if (ann->has_hidden_use)
 554     fprintf (file, ", has hidden uses");
 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
 942 /* Mark variables in BLOCK that have hidden uses.  A hidden use can
 943    occur due to VLA declarations or nested functions.  */
 944
 945 static void
 946 find_hidden_use_vars (tree block)
 947 {
 948   tree sub, decl, tem;
 949
 950   /* Check all the arrays declared in the block for VLAs.
 951      While scanning the block's variables, also see if there is
 952      a nested function at this scope.  */
 953   for (decl = BLOCK_VARS (block); decl; decl = TREE_CHAIN (decl))
 954     {
 955       int inside_vla = 0;
 956       walk_tree (&decl, find_hidden_use_vars_r, &inside_vla, NULL);
 957     }
 958
 959   /* Now repeat the search in any sub-blocks.  */
 960   for (sub = BLOCK_SUBBLOCKS (block); sub; sub = TREE_CHAIN (sub))
 961     find_hidden_use_vars (sub);
 962
 963   /* A VLA parameter may use a variable which as set from another
 964      parameter to declare the size of the VLA.  We need to mark the
 965      variable as having a hidden use since it is used to declare the
 966      VLA parameter and that declaration is not seen by the SSA code.
 967
 968      Note get_pending_sizes clears the PENDING_SIZES chain, so we
 969      must restore it.  */
 970   tem = get_pending_sizes ();
 971   put_pending_sizes (tem);
 972   for (; tem; tem = TREE_CHAIN (tem))
 973     {
 974       int inside_vla = 1;
 975       walk_tree (&TREE_VALUE (tem), find_hidden_use_vars_r, &inside_vla, NULL);
 976     }
 977 }
 978
 979
 980 /* Callback for walk_tree used by find_hidden_use_vars to analyze each
 981    variable in a lexical block.  If the variable's size has a variable
 982    size, then mark all objects needed to compute the variable's size
 983    as having hidden uses.  */
 984
 985 static tree
 986 find_hidden_use_vars_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 987                         void *data ATTRIBUTE_UNUSED)
 988 {
 989   int *inside_vla = (int *) data;
 990
 991   /* We need to look for hidden uses due to VLAs in variable
 992      definitions.  We originally used to look for these hidden
 993      uses in the variable's type, but that's unreliable if the
 994      type's size contains a SAVE_EXPR for a different function
 995      context than the variable is used within.  */
 996   if (SSA_VAR_P (*tp)
 997       && ((DECL_SIZE (*tp)
 998            && ! really_constant_p (DECL_SIZE (*tp)))
 999           || (DECL_SIZE_UNIT (*tp)
1000               && ! really_constant_p (DECL_SIZE_UNIT (*tp)))))
1001     {
1002       int save = *inside_vla;
1003
1004       *inside_vla = 1;
1005       walk_tree (&DECL_SIZE (*tp), find_hidden_use_vars_r, inside_vla, NULL);
1006       walk_tree (&DECL_SIZE_UNIT (*tp), find_hidden_use_vars_r,
1007                  inside_vla, NULL);
1008       *inside_vla = save;
1009     }
1010   else if (*inside_vla && SSA_VAR_P (*tp))
1011     set_has_hidden_use (*tp);
1012
1013   return NULL_TREE;
1014 }
1015
1016
1017 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
1018    add_referenced_var, but is used by passes that need to add new temps to
1019    the REFERENCED_VARS array after the program has been scanned for
1020    variables.  The variable will just receive a new UID and be added
1021    to the REFERENCED_VARS array without checking for duplicates.  */
1022
1023 void
1024 add_referenced_tmp_var (tree var)
1025 {
1026   add_referenced_var (var, NULL);
1027 }
1028
1029 /* Return true if V_MAY_DEFS_AFTER contains fewer entries than
1030    V_MAY_DEFS_BEFORE. Note that this assumes that both varrays
1031    are V_MAY_DEF operands for the same statement.  */
1032
1033 static inline bool
1034 v_may_defs_disappeared_p (v_may_def_optype v_may_defs_before,
1035                           v_may_def_optype v_may_defs_after)
1036 {
1037   /* If there was nothing before, nothing could've disappeared.  */
1038   if (v_may_defs_before == NULL)
1039     return false;
1040
1041   /* All/some of them gone.  */
1042   if (v_may_defs_after == NULL
1043       || NUM_V_MAY_DEFS (v_may_defs_before) >
1044          NUM_V_MAY_DEFS (v_may_defs_after))
1045     return true;
1046
1047   return false;
1048 }
1049
1050 /* Return true if V_MUST_DEFS_AFTER contains fewer entries than
1051    V_MUST_DEFS_BEFORE. Note that this assumes that both varrays
1052    are V_MUST_DEF operands for the same statement.  */
1053
1054 static inline bool
1055 v_must_defs_disappeared_p (v_must_def_optype v_must_defs_before,
1056                            v_must_def_optype v_must_defs_after)
1057 {
1058   /* If there was nothing before, nothing could've disappeared.  */
1059   if (v_must_defs_before == NULL)
1060     return false;
1061
1062   /* All/some of them gone.  */
1063   if (v_must_defs_after == NULL
1064       || NUM_V_MUST_DEFS (v_must_defs_before) >
1065          NUM_V_MUST_DEFS (v_must_defs_after))
1066     return true;
1067
1068   return false;
1069 }
1070
1071
1072 /* Add all the non-SSA variables found in STMT's operands to the bitmap
1073    VARS_TO_RENAME.  */
1074
1075 void
1076 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
1077 {
1078   def_optype defs;
1079   use_optype uses;
1080   v_may_def_optype v_may_defs;
1081   vuse_optype vuses;
1082   v_must_def_optype v_must_defs;
1083   size_t i;
1084   bitmap vars_in_vops_to_rename;
1085   bool found_exposed_symbol = false;
1086   v_may_def_optype v_may_defs_before, v_may_defs_after;
1087   v_must_def_optype v_must_defs_before, v_must_defs_after;
1088   stmt_ann_t ann;
1089
1090   vars_in_vops_to_rename = BITMAP_XMALLOC ();
1091
1092   /* Before re-scanning the statement for operands, mark the existing
1093      virtual operands to be renamed again.  We do this because when new
1094      symbols are exposed, the virtual operands that were here before due to
1095      aliasing will probably be removed by the call to get_stmt_operand.
1096      Therefore, we need to flag them to be renamed beforehand.
1097
1098      We flag them in a separate bitmap because we don't really want to
1099      rename them if there are not any newly exposed symbols in the
1100      statement operands.  */
1101   ann = stmt_ann (stmt);
1102   v_may_defs_before = v_may_defs = V_MAY_DEF_OPS (ann);
1103   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1104     {
1105       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1106       if (!DECL_P (var))
1107         var = SSA_NAME_VAR (var);
1108       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1109     }
1110
1111   vuses = VUSE_OPS (ann);
1112   for (i = 0; i < NUM_VUSES (vuses); i++)
1113     {
1114       tree var = VUSE_OP (vuses, i);
1115       if (!DECL_P (var))
1116         var = SSA_NAME_VAR (var);
1117       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1118     }
1119
1120   v_must_defs_before = v_must_defs = V_MUST_DEF_OPS (ann);
1121   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1122     {
1123       tree var = V_MUST_DEF_OP (v_must_defs, i);
1124       if (!DECL_P (var))
1125         var = SSA_NAME_VAR (var);
1126       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1127     }
1128
1129   /* Now force an operand re-scan on the statement and mark any newly
1130      exposed variables.  */
1131   modify_stmt (stmt);
1132   get_stmt_operands (stmt);
1133
1134   defs = DEF_OPS (ann);
1135   for (i = 0; i < NUM_DEFS (defs); i++)
1136     {
1137       tree var = DEF_OP (defs, i);
1138       if (DECL_P (var))
1139         {
1140           found_exposed_symbol = true;
1141           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1142         }
1143     }
1144
1145   uses = USE_OPS (ann);
1146   for (i = 0; i < NUM_USES (uses); i++)
1147     {
1148       tree var = USE_OP (uses, i);
1149       if (DECL_P (var))
1150         {
1151           found_exposed_symbol = true;
1152           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1153         }
1154     }
1155
1156   v_may_defs_after = v_may_defs = V_MAY_DEF_OPS (ann);
1157   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1158     {
1159       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1160       if (DECL_P (var))
1161         {
1162           found_exposed_symbol = true;
1163           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1164         }
1165     }
1166
1167   vuses = VUSE_OPS (ann);
1168   for (i = 0; i < NUM_VUSES (vuses); i++)
1169     {
1170       tree var = VUSE_OP (vuses, i);
1171       if (DECL_P (var))
1172         {
1173           found_exposed_symbol = true;
1174           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1175         }
1176     }
1177
1178   v_must_defs_after = v_must_defs = V_MUST_DEF_OPS (ann);
1179   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1180     {
1181       tree var = V_MUST_DEF_OP (v_must_defs, i);
1182       if (DECL_P (var))
1183         {
1184           found_exposed_symbol = true;
1185           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1186         }
1187     }
1188
1189   /* If we found any newly exposed symbols, or if there are fewer VDEF
1190      operands in the statement, add the variables we had set in
1191      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
1192      vanishing VDEFs because in those cases, the names that were formerly
1193      generated by this statement are not going to be available anymore.  */
1194   if (found_exposed_symbol
1195       || v_may_defs_disappeared_p (v_may_defs_before, v_may_defs_after)
1196       || v_must_defs_disappeared_p (v_must_defs_before, v_must_defs_after))
1197     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
1198
1199   BITMAP_XFREE (vars_in_vops_to_rename);
1200 }