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   if (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR)
 926     var = TREE_OPERAND (var, 0);
 927   else
 928     while (handled_component_p (var))
 929       var = TREE_OPERAND (var, 0);
 930
 931 #ifdef ENABLE_CHECKING
 932   /* Treating GIMPLE registers as virtual variables makes no sense.
 933      Also complain if we couldn't extract a _DECL out of the original
 934      expression.  */
 935   if (!SSA_VAR_P (var)
 936       || is_gimple_reg (var))
 937     abort ();
 938 #endif
 939
 940   return var;
 941 }
 942
 943
 944 /* Mark variables in BLOCK that have hidden uses.  A hidden use can
 945    occur due to VLA declarations or nested functions.  */
 946
 947 static void
 948 find_hidden_use_vars (tree block)
 949 {
 950   tree sub, decl, tem;
 951
 952   /* Check all the arrays declared in the block for VLAs.
 953      While scanning the block's variables, also see if there is
 954      a nested function at this scope.  */
 955   for (decl = BLOCK_VARS (block); decl; decl = TREE_CHAIN (decl))
 956     {
 957       int inside_vla = 0;
 958       walk_tree (&decl, find_hidden_use_vars_r, &inside_vla, NULL);
 959     }
 960
 961   /* Now repeat the search in any sub-blocks.  */
 962   for (sub = BLOCK_SUBBLOCKS (block); sub; sub = TREE_CHAIN (sub))
 963     find_hidden_use_vars (sub);
 964
 965   /* A VLA parameter may use a variable which as set from another
 966      parameter to declare the size of the VLA.  We need to mark the
 967      variable as having a hidden use since it is used to declare the
 968      VLA parameter and that declaration is not seen by the SSA code.
 969
 970      Note get_pending_sizes clears the PENDING_SIZES chain, so we
 971      must restore it.  */
 972   tem = get_pending_sizes ();
 973   put_pending_sizes (tem);
 974   for (; tem; tem = TREE_CHAIN (tem))
 975     {
 976       int inside_vla = 1;
 977       walk_tree (&TREE_VALUE (tem), find_hidden_use_vars_r, &inside_vla, NULL);
 978     }
 979 }
 980
 981
 982 /* Callback for walk_tree used by find_hidden_use_vars to analyze each
 983    variable in a lexical block.  If the variable's size has a variable
 984    size, then mark all objects needed to compute the variable's size
 985    as having hidden uses.  */
 986
 987 static tree
 988 find_hidden_use_vars_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 989                         void *data ATTRIBUTE_UNUSED)
 990 {
 991   int *inside_vla = (int *) data;
 992
 993   /* We need to look for hidden uses due to VLAs in variable
 994      definitions.  We originally used to look for these hidden
 995      uses in the variable's type, but that's unreliable if the
 996      type's size contains a SAVE_EXPR for a different function
 997      context than the variable is used within.  */
 998   if (SSA_VAR_P (*tp)
 999       && ((DECL_SIZE (*tp)
1000            && ! really_constant_p (DECL_SIZE (*tp)))
1001           || (DECL_SIZE_UNIT (*tp)
1002               && ! really_constant_p (DECL_SIZE_UNIT (*tp)))))
1003     {
1004       int save = *inside_vla;
1005
1006       *inside_vla = 1;
1007       walk_tree (&DECL_SIZE (*tp), find_hidden_use_vars_r, inside_vla, NULL);
1008       walk_tree (&DECL_SIZE_UNIT (*tp), find_hidden_use_vars_r,
1009                  inside_vla, NULL);
1010       *inside_vla = save;
1011     }
1012   else if (*inside_vla && SSA_VAR_P (*tp))
1013     set_has_hidden_use (*tp);
1014
1015   return NULL_TREE;
1016 }
1017
1018
1019 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
1020    add_referenced_var, but is used by passes that need to add new temps to
1021    the REFERENCED_VARS array after the program has been scanned for
1022    variables.  The variable will just receive a new UID and be added
1023    to the REFERENCED_VARS array without checking for duplicates.  */
1024
1025 void
1026 add_referenced_tmp_var (tree var)
1027 {
1028   add_referenced_var (var, NULL);
1029 }
1030
1031 /* Return true if V_MAY_DEFS_AFTER contains fewer entries than
1032    V_MAY_DEFS_BEFORE. Note that this assumes that both varrays
1033    are V_MAY_DEF operands for the same statement.  */
1034
1035 static inline bool
1036 v_may_defs_disappeared_p (v_may_def_optype v_may_defs_before,
1037                           v_may_def_optype v_may_defs_after)
1038 {
1039   /* If there was nothing before, nothing could've disappeared.  */
1040   if (v_may_defs_before == NULL)
1041     return false;
1042
1043   /* All/some of them gone.  */
1044   if (v_may_defs_after == NULL
1045       || NUM_V_MAY_DEFS (v_may_defs_before) >
1046          NUM_V_MAY_DEFS (v_may_defs_after))
1047     return true;
1048
1049   return false;
1050 }
1051
1052 /* Return true if V_MUST_DEFS_AFTER contains fewer entries than
1053    V_MUST_DEFS_BEFORE. Note that this assumes that both varrays
1054    are V_MUST_DEF operands for the same statement.  */
1055
1056 static inline bool
1057 v_must_defs_disappeared_p (v_must_def_optype v_must_defs_before,
1058                            v_must_def_optype v_must_defs_after)
1059 {
1060   /* If there was nothing before, nothing could've disappeared.  */
1061   if (v_must_defs_before == NULL)
1062     return false;
1063
1064   /* All/some of them gone.  */
1065   if (v_must_defs_after == NULL
1066       || NUM_V_MUST_DEFS (v_must_defs_before) >
1067          NUM_V_MUST_DEFS (v_must_defs_after))
1068     return true;
1069
1070   return false;
1071 }
1072
1073
1074 /* Add all the non-SSA variables found in STMT's operands to the bitmap
1075    VARS_TO_RENAME.  */
1076
1077 void
1078 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
1079 {
1080   def_optype defs;
1081   use_optype uses;
1082   v_may_def_optype v_may_defs;
1083   vuse_optype vuses;
1084   v_must_def_optype v_must_defs;
1085   size_t i;
1086   bitmap vars_in_vops_to_rename;
1087   bool found_exposed_symbol = false;
1088   v_may_def_optype v_may_defs_before, v_may_defs_after;
1089   v_must_def_optype v_must_defs_before, v_must_defs_after;
1090   stmt_ann_t ann;
1091
1092   vars_in_vops_to_rename = BITMAP_XMALLOC ();
1093
1094   /* Before re-scanning the statement for operands, mark the existing
1095      virtual operands to be renamed again.  We do this because when new
1096      symbols are exposed, the virtual operands that were here before due to
1097      aliasing will probably be removed by the call to get_stmt_operand.
1098      Therefore, we need to flag them to be renamed beforehand.
1099
1100      We flag them in a separate bitmap because we don't really want to
1101      rename them if there are not any newly exposed symbols in the
1102      statement operands.  */
1103   ann = stmt_ann (stmt);
1104   v_may_defs_before = v_may_defs = V_MAY_DEF_OPS (ann);
1105   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1106     {
1107       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1108       if (!DECL_P (var))
1109         var = SSA_NAME_VAR (var);
1110       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1111     }
1112
1113   vuses = VUSE_OPS (ann);
1114   for (i = 0; i < NUM_VUSES (vuses); i++)
1115     {
1116       tree var = VUSE_OP (vuses, i);
1117       if (!DECL_P (var))
1118         var = SSA_NAME_VAR (var);
1119       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1120     }
1121
1122   v_must_defs_before = v_must_defs = V_MUST_DEF_OPS (ann);
1123   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1124     {
1125       tree var = V_MUST_DEF_OP (v_must_defs, i);
1126       if (!DECL_P (var))
1127         var = SSA_NAME_VAR (var);
1128       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1129     }
1130
1131   /* Now force an operand re-scan on the statement and mark any newly
1132      exposed variables.  */
1133   modify_stmt (stmt);
1134   get_stmt_operands (stmt);
1135
1136   defs = DEF_OPS (ann);
1137   for (i = 0; i < NUM_DEFS (defs); i++)
1138     {
1139       tree var = DEF_OP (defs, i);
1140       if (DECL_P (var))
1141         {
1142           found_exposed_symbol = true;
1143           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1144         }
1145     }
1146
1147   uses = USE_OPS (ann);
1148   for (i = 0; i < NUM_USES (uses); i++)
1149     {
1150       tree var = USE_OP (uses, i);
1151       if (DECL_P (var))
1152         {
1153           found_exposed_symbol = true;
1154           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1155         }
1156     }
1157
1158   v_may_defs_after = v_may_defs = V_MAY_DEF_OPS (ann);
1159   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1160     {
1161       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1162       if (DECL_P (var))
1163         {
1164           found_exposed_symbol = true;
1165           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1166         }
1167     }
1168
1169   vuses = VUSE_OPS (ann);
1170   for (i = 0; i < NUM_VUSES (vuses); i++)
1171     {
1172       tree var = VUSE_OP (vuses, i);
1173       if (DECL_P (var))
1174         {
1175           found_exposed_symbol = true;
1176           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1177         }
1178     }
1179
1180   v_must_defs_after = v_must_defs = V_MUST_DEF_OPS (ann);
1181   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1182     {
1183       tree var = V_MUST_DEF_OP (v_must_defs, i);
1184       if (DECL_P (var))
1185         {
1186           found_exposed_symbol = true;
1187           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1188         }
1189     }
1190
1191   /* If we found any newly exposed symbols, or if there are fewer VDEF
1192      operands in the statement, add the variables we had set in
1193      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
1194      vanishing VDEFs because in those cases, the names that were formerly
1195      generated by this statement are not going to be available anymore.  */
1196   if (found_exposed_symbol
1197       || v_may_defs_disappeared_p (v_may_defs_before, v_may_defs_after)
1198       || v_must_defs_disappeared_p (v_must_defs_before, v_must_defs_after))
1199     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
1200
1201   BITMAP_XFREE (vars_in_vops_to_rename);
1202 }