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