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