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