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   if (vars_to_rename)
 505     {
 506       add_referenced_tmp_var (t);
 507       bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
 508     }
 509   return t;
 510 }
 511
 512
 513
 514 /*---------------------------------------------------------------------------
 515                               Debugging functions
 516 ---------------------------------------------------------------------------*/
 517 /* Dump the list of all the referenced variables in the current function to
 518    FILE.  */
 519
 520 void
 521 dump_referenced_vars (FILE *file)
 522 {
 523   size_t i;
 524
 525   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 526            get_name (current_function_decl), (unsigned) num_referenced_vars);
 527
 528   for (i = 0; i < num_referenced_vars; i++)
 529     {
 530       tree var = referenced_var (i);
 531       fprintf (file, "Variable: ");
 532       dump_variable (file, var);
 533       fprintf (file, "\n");
 534     }
 535 }
 536
 537
 538 /* Dump the list of all the referenced variables to stderr.  */
 539
 540 void
 541 debug_referenced_vars (void)
 542 {
 543   dump_referenced_vars (stderr);
 544 }
 545
 546
 547 /* Dump variable VAR and its may-aliases to FILE.  */
 548
 549 void
 550 dump_variable (FILE *file, tree var)
 551 {
 552   var_ann_t ann;
 553
 554   if (TREE_CODE (var) == SSA_NAME)
 555     {
 556       if (POINTER_TYPE_P (TREE_TYPE (var)))
 557         dump_points_to_info_for (file, var);
 558       var = SSA_NAME_VAR (var);
 559     }
 560
 561   if (var == NULL_TREE)
 562     {
 563       fprintf (file, "<nil>");
 564       return;
 565     }
 566
 567   print_generic_expr (file, var, dump_flags);
 568
 569   ann = var_ann (var);
 570
 571   fprintf (file, ", UID %u", (unsigned) ann->uid);
 572
 573   if (ann->has_hidden_use)
 574     fprintf (file, ", has hidden uses");
 575
 576   if (ann->type_mem_tag)
 577     {
 578       fprintf (file, ", type memory tag: ");
 579       print_generic_expr (file, ann->type_mem_tag, dump_flags);
 580     }
 581
 582   if (ann->is_alias_tag)
 583     fprintf (file, ", is an alias tag");
 584
 585   if (needs_to_live_in_memory (var))
 586     fprintf (file, ", is %s", TREE_STATIC (var) ? "static" : "global");
 587
 588   if (is_call_clobbered (var))
 589     fprintf (file, ", call clobbered");
 590
 591   if (ann->default_def)
 592     {
 593       fprintf (file, ", default def: ");
 594       print_generic_expr (file, ann->default_def, dump_flags);
 595     }
 596
 597   if (ann->may_aliases)
 598     {
 599       fprintf (file, ", may aliases: ");
 600       dump_may_aliases_for (file, var);
 601     }
 602
 603   fprintf (file, "\n");
 604 }
 605
 606
 607 /* Dump variable VAR and its may-aliases to stderr.  */
 608
 609 void
 610 debug_variable (tree var)
 611 {
 612   dump_variable (stderr, var);
 613 }
 614
 615
 616 /* Dump def-use edges on FILE.  */
 617
 618 void
 619 dump_immediate_uses (FILE *file)
 620 {
 621   basic_block bb;
 622   block_stmt_iterator si;
 623   const char *funcname
 624     = lang_hooks.decl_printable_name (current_function_decl, 2);
 625
 626   fprintf (file, "\nDef-use edges for function %s\n", funcname);
 627
 628   FOR_EACH_BB (bb)
 629     {
 630       tree phi;
 631
 632       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 633         dump_immediate_uses_for (file, phi);
 634
 635       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 636         dump_immediate_uses_for (file, bsi_stmt (si));
 637     }
 638
 639   fprintf (file, "\n");
 640 }
 641
 642
 643 /* Dump def-use edges on stderr.  */
 644
 645 void
 646 debug_immediate_uses (void)
 647 {
 648   dump_immediate_uses (stderr);
 649 }
 650
 651
 652 /* Dump all immediate uses for STMT on FILE.  */
 653
 654 void
 655 dump_immediate_uses_for (FILE *file, tree stmt)
 656 {
 657   dataflow_t df = get_immediate_uses (stmt);
 658   int num_imm_uses = num_immediate_uses (df);
 659
 660   if (num_imm_uses > 0)
 661     {
 662       int i;
 663
 664       fprintf (file, "-> ");
 665       print_generic_stmt (file, stmt, TDF_SLIM);
 666       fprintf (file, "\n");
 667
 668       for (i = 0; i < num_imm_uses; i++)
 669         {
 670           fprintf (file, "\t");
 671           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
 672           fprintf (file, "\n");
 673         }
 674
 675       fprintf (file, "\n");
 676     }
 677 }
 678
 679
 680 /* Dump immediate uses for STMT on stderr.  */
 681
 682 void
 683 debug_immediate_uses_for (tree stmt)
 684 {
 685   dump_immediate_uses_for (stderr, stmt);
 686 }
 687
 688
 689 /* Dump various DFA statistics to FILE.  */
 690
 691 void
 692 dump_dfa_stats (FILE *file)
 693 {
 694   struct dfa_stats_d dfa_stats;
 695
 696   unsigned long size, total = 0;
 697   const char * const fmt_str   = "%-30s%-13s%12s\n";
 698   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 699   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 700   const char *funcname
 701     = lang_hooks.decl_printable_name (current_function_decl, 2);
 702
 703   collect_dfa_stats (&dfa_stats);
 704
 705   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 706
 707   fprintf (file, "---------------------------------------------------------\n");
 708   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 709   fprintf (file, fmt_str, "", "  instances  ", "used ");
 710   fprintf (file, "---------------------------------------------------------\n");
 711
 712   size = num_referenced_vars * sizeof (tree);
 713   total += size;
 714   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
 715            SCALE (size), LABEL (size));
 716
 717   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 718   total += size;
 719   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 720            SCALE (size), LABEL (size));
 721
 722   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 723   total += size;
 724   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 725            SCALE (size), LABEL (size));
 726
 727   size = dfa_stats.num_uses * sizeof (tree *);
 728   total += size;
 729   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 730            SCALE (size), LABEL (size));
 731
 732   size = dfa_stats.num_defs * sizeof (tree *);
 733   total += size;
 734   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 735            SCALE (size), LABEL (size));
 736
 737   size = dfa_stats.num_vuses * sizeof (tree *);
 738   total += size;
 739   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 740            SCALE (size), LABEL (size));
 741
 742   size = dfa_stats.num_v_may_defs * sizeof (tree *);
 743   total += size;
 744   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
 745            SCALE (size), LABEL (size));
 746
 747   size = dfa_stats.num_v_must_defs * sizeof (tree *);
 748   total += size;
 749   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
 750            SCALE (size), LABEL (size));
 751
 752   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 753   total += size;
 754   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 755            SCALE (size), LABEL (size));
 756
 757   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 758   total += size;
 759   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 760            SCALE (size), LABEL (size));
 761
 762   fprintf (file, "---------------------------------------------------------\n");
 763   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 764            LABEL (total));
 765   fprintf (file, "---------------------------------------------------------\n");
 766   fprintf (file, "\n");
 767
 768   if (dfa_stats.num_phis)
 769     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 770              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 771              dfa_stats.max_num_phi_args);
 772
 773   fprintf (file, "\n");
 774 }
 775
 776
 777 /* Dump DFA statistics on stderr.  */
 778
 779 void
 780 debug_dfa_stats (void)
 781 {
 782   dump_dfa_stats (stderr);
 783 }
 784
 785
 786 /* Collect DFA statistics and store them in the structure pointed by
 787    DFA_STATS_P.  */
 788
 789 static void
 790 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 791 {
 792   htab_t htab;
 793   basic_block bb;
 794   block_stmt_iterator i;
 795
 796   if (dfa_stats_p == NULL)
 797     abort ();
 798
 799   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 800
 801   /* Walk all the trees in the function counting references.  Start at
 802      basic block 0, but don't stop at block boundaries.  */
 803   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
 804
 805   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
 806     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 807                (void *) htab);
 808
 809   htab_delete (htab);
 810
 811   FOR_EACH_BB (bb)
 812     {
 813       tree phi;
 814       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 815         {
 816           dfa_stats_p->num_phis++;
 817           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 818           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 819             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 820         }
 821     }
 822 }
 823
 824
 825 /* Callback for walk_tree to collect DFA statistics for a tree and its
 826    children.  */
 827
 828 static tree
 829 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 830                      void *data)
 831 {
 832   tree t = *tp;
 833   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 834
 835   if (t->common.ann)
 836     {
 837       switch (ann_type (t->common.ann))
 838         {
 839         case STMT_ANN:
 840           {
 841             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
 842             dfa_stats_p->num_stmt_anns++;
 843             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
 844             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
 845             dfa_stats_p->num_v_may_defs +=
 846                          NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann));
 847             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
 848             dfa_stats_p->num_v_must_defs +=
 849                          NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann));
 850             break;
 851           }
 852
 853         case VAR_ANN:
 854           dfa_stats_p->num_var_anns++;
 855           break;
 856
 857         default:
 858           break;
 859         }
 860     }
 861
 862   return NULL;
 863 }
 864
 865
 866 /*---------------------------------------------------------------------------
 867                              Miscellaneous helpers
 868 ---------------------------------------------------------------------------*/
 869 /* Callback for walk_tree.  Used to collect variables referenced in
 870    the function.  */
 871
 872 static tree
 873 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 874 {
 875   struct walk_state *walk_state = (struct walk_state *) data;
 876
 877   /* If T is a regular variable that the optimizers are interested
 878      in, add it to the list of variables.  */
 879   if (SSA_VAR_P (*tp))
 880     add_referenced_var (*tp, walk_state);
 881
 882   /* Type, _DECL and constant nodes have no interesting children.
 883      Ignore them.  */
 884   else if (DECL_P (*tp)
 885            || TYPE_P (*tp)
 886            || TREE_CODE_CLASS (TREE_CODE (*tp)) == 'c')
 887     *walk_subtrees = 0;
 888
 889   return NULL_TREE;
 890 }
 891
 892
 893 /* Add VAR to the list of dereferenced variables.
 894
 895    WALK_STATE contains a hash table used to avoid adding the same
 896       variable more than once. Note that this function assumes that
 897       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 898       duplicate checking is done.  */
 899
 900 static void
 901 add_referenced_var (tree var, struct walk_state *walk_state)
 902 {
 903   void **slot;
 904   var_ann_t v_ann;
 905
 906   v_ann = get_var_ann (var);
 907
 908   if (walk_state)
 909     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 910   else
 911     slot = NULL;
 912
 913   if (slot == NULL || *slot == NULL)
 914     {
 915       /* This is the first time we find this variable, add it to the
 916          REFERENCED_VARS array and annotate it with attributes that are
 917          intrinsic to the variable.  */
 918       if (slot)
 919         *slot = (void *) var;
 920       v_ann->uid = num_referenced_vars;
 921       VARRAY_PUSH_TREE (referenced_vars, var);
 922
 923       /* Global and static variables are call-clobbered, always.  */
 924       if (needs_to_live_in_memory (var))
 925         mark_call_clobbered (var);
 926
 927       /* DECL_NONLOCAL variables should not be removed, as they are needed
 928          to emit nested functions.  */
 929       if (DECL_NONLOCAL (var))
 930         v_ann->used = 1;
 931     }
 932 }
 933
 934
 935 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 936
 937 tree
 938 get_virtual_var (tree var)
 939 {
 940   STRIP_NOPS (var);
 941
 942   if (TREE_CODE (var) == SSA_NAME)
 943     var = SSA_NAME_VAR (var);
 944
 945   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 946          || handled_component_p (var))
 947     var = TREE_OPERAND (var, 0);
 948
 949 #ifdef ENABLE_CHECKING
 950   /* Treating GIMPLE registers as virtual variables makes no sense.
 951      Also complain if we couldn't extract a _DECL out of the original
 952      expression.  */
 953   if (!SSA_VAR_P (var)
 954       || is_gimple_reg (var))
 955     abort ();
 956 #endif
 957
 958   return var;
 959 }
 960
 961
 962 /* Mark variables in BLOCK that have hidden uses.  A hidden use can
 963    occur due to VLA declarations or nested functions.  */
 964
 965 static void
 966 find_hidden_use_vars (tree block)
 967 {
 968   tree sub, decl, tem;
 969
 970   /* Check all the arrays declared in the block for VLAs.
 971      While scanning the block's variables, also see if there is
 972      a nested function at this scope.  */
 973   for (decl = BLOCK_VARS (block); decl; decl = TREE_CHAIN (decl))
 974     {
 975       int inside_vla = 0;
 976       walk_tree (&decl, find_hidden_use_vars_r, &inside_vla, NULL);
 977     }
 978
 979   /* Now repeat the search in any sub-blocks.  */
 980   for (sub = BLOCK_SUBBLOCKS (block); sub; sub = TREE_CHAIN (sub))
 981     find_hidden_use_vars (sub);
 982
 983   /* A VLA parameter may use a variable which as set from another
 984      parameter to declare the size of the VLA.  We need to mark the
 985      variable as having a hidden use since it is used to declare the
 986      VLA parameter and that declaration is not seen by the SSA code.
 987
 988      Note get_pending_sizes clears the PENDING_SIZES chain, so we
 989      must restore it.  */
 990   tem = get_pending_sizes ();
 991   put_pending_sizes (tem);
 992   for (; tem; tem = TREE_CHAIN (tem))
 993     {
 994       int inside_vla = 1;
 995       walk_tree (&TREE_VALUE (tem), find_hidden_use_vars_r, &inside_vla, NULL);
 996     }
 997 }
 998
 999
1000 /* Callback for walk_tree used by find_hidden_use_vars to analyze each
1001    variable in a lexical block.  If the variable's size has a variable
1002    size, then mark all objects needed to compute the variable's size
1003    as having hidden uses.  */
1004
1005 static tree
1006 find_hidden_use_vars_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
1007                         void *data ATTRIBUTE_UNUSED)
1008 {
1009   int *inside_vla = (int *) data;
1010
1011   /* We need to look for hidden uses due to VLAs in variable
1012      definitions.  We originally used to look for these hidden
1013      uses in the variable's type, but that's unreliable if the
1014      type's size contains a SAVE_EXPR for a different function
1015      context than the variable is used within.  */
1016   if (SSA_VAR_P (*tp)
1017       && ((DECL_SIZE (*tp)
1018            && ! really_constant_p (DECL_SIZE (*tp)))
1019           || (DECL_SIZE_UNIT (*tp)
1020               && ! really_constant_p (DECL_SIZE_UNIT (*tp)))))
1021     {
1022       int save = *inside_vla;
1023
1024       *inside_vla = 1;
1025       walk_tree (&DECL_SIZE (*tp), find_hidden_use_vars_r, inside_vla, NULL);
1026       walk_tree (&DECL_SIZE_UNIT (*tp), find_hidden_use_vars_r,
1027                  inside_vla, NULL);
1028       *inside_vla = save;
1029     }
1030   else if (*inside_vla && SSA_VAR_P (*tp))
1031     set_has_hidden_use (*tp);
1032
1033   return NULL_TREE;
1034 }
1035
1036
1037 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
1038    add_referenced_var, but is used by passes that need to add new temps to
1039    the REFERENCED_VARS array after the program has been scanned for
1040    variables.  The variable will just receive a new UID and be added
1041    to the REFERENCED_VARS array without checking for duplicates.  */
1042
1043 void
1044 add_referenced_tmp_var (tree var)
1045 {
1046   add_referenced_var (var, NULL);
1047 }
1048
1049 /* Return true if V_MAY_DEFS_AFTER contains fewer entries than
1050    V_MAY_DEFS_BEFORE. Note that this assumes that both varrays
1051    are V_MAY_DEF operands for the same statement.  */
1052
1053 static inline bool
1054 v_may_defs_disappeared_p (v_may_def_optype v_may_defs_before,
1055                           v_may_def_optype v_may_defs_after)
1056 {
1057   /* If there was nothing before, nothing could've disappeared.  */
1058   if (v_may_defs_before == NULL)
1059     return false;
1060
1061   /* All/some of them gone.  */
1062   if (v_may_defs_after == NULL
1063       || NUM_V_MAY_DEFS (v_may_defs_before) >
1064          NUM_V_MAY_DEFS (v_may_defs_after))
1065     return true;
1066
1067   return false;
1068 }
1069
1070 /* Return true if V_MUST_DEFS_AFTER contains fewer entries than
1071    V_MUST_DEFS_BEFORE. Note that this assumes that both varrays
1072    are V_MUST_DEF operands for the same statement.  */
1073
1074 static inline bool
1075 v_must_defs_disappeared_p (v_must_def_optype v_must_defs_before,
1076                            v_must_def_optype v_must_defs_after)
1077 {
1078   /* If there was nothing before, nothing could've disappeared.  */
1079   if (v_must_defs_before == NULL)
1080     return false;
1081
1082   /* All/some of them gone.  */
1083   if (v_must_defs_after == NULL
1084       || NUM_V_MUST_DEFS (v_must_defs_before) >
1085          NUM_V_MUST_DEFS (v_must_defs_after))
1086     return true;
1087
1088   return false;
1089 }
1090
1091
1092 /* Add all the non-SSA variables found in STMT's operands to the bitmap
1093    VARS_TO_RENAME.  */
1094
1095 void
1096 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
1097 {
1098   def_optype defs;
1099   use_optype uses;
1100   v_may_def_optype v_may_defs;
1101   vuse_optype vuses;
1102   v_must_def_optype v_must_defs;
1103   size_t i;
1104   bitmap vars_in_vops_to_rename;
1105   bool found_exposed_symbol = false;
1106   v_may_def_optype v_may_defs_before, v_may_defs_after;
1107   v_must_def_optype v_must_defs_before, v_must_defs_after;
1108   stmt_ann_t ann;
1109
1110   vars_in_vops_to_rename = BITMAP_XMALLOC ();
1111
1112   /* Before re-scanning the statement for operands, mark the existing
1113      virtual operands to be renamed again.  We do this because when new
1114      symbols are exposed, the virtual operands that were here before due to
1115      aliasing will probably be removed by the call to get_stmt_operand.
1116      Therefore, we need to flag them to be renamed beforehand.
1117
1118      We flag them in a separate bitmap because we don't really want to
1119      rename them if there are not any newly exposed symbols in the
1120      statement operands.  */
1121   ann = stmt_ann (stmt);
1122   v_may_defs_before = v_may_defs = V_MAY_DEF_OPS (ann);
1123   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1124     {
1125       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1126       if (!DECL_P (var))
1127         var = SSA_NAME_VAR (var);
1128       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1129     }
1130
1131   vuses = VUSE_OPS (ann);
1132   for (i = 0; i < NUM_VUSES (vuses); i++)
1133     {
1134       tree var = VUSE_OP (vuses, 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   v_must_defs_before = v_must_defs = V_MUST_DEF_OPS (ann);
1141   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1142     {
1143       tree var = V_MUST_DEF_OP (v_must_defs, i);
1144       if (!DECL_P (var))
1145         var = SSA_NAME_VAR (var);
1146       bitmap_set_bit (vars_in_vops_to_rename, var_ann (var)->uid);
1147     }
1148
1149   /* Now force an operand re-scan on the statement and mark any newly
1150      exposed variables.  */
1151   modify_stmt (stmt);
1152   get_stmt_operands (stmt);
1153
1154   defs = DEF_OPS (ann);
1155   for (i = 0; i < NUM_DEFS (defs); i++)
1156     {
1157       tree var = DEF_OP (defs, i);
1158       if (DECL_P (var))
1159         {
1160           found_exposed_symbol = true;
1161           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1162         }
1163     }
1164
1165   uses = USE_OPS (ann);
1166   for (i = 0; i < NUM_USES (uses); i++)
1167     {
1168       tree var = USE_OP (uses, i);
1169       if (DECL_P (var))
1170         {
1171           found_exposed_symbol = true;
1172           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1173         }
1174     }
1175
1176   v_may_defs_after = v_may_defs = V_MAY_DEF_OPS (ann);
1177   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
1178     {
1179       tree var = V_MAY_DEF_RESULT (v_may_defs, i);
1180       if (DECL_P (var))
1181         {
1182           found_exposed_symbol = true;
1183           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1184         }
1185     }
1186
1187   vuses = VUSE_OPS (ann);
1188   for (i = 0; i < NUM_VUSES (vuses); i++)
1189     {
1190       tree var = VUSE_OP (vuses, i);
1191       if (DECL_P (var))
1192         {
1193           found_exposed_symbol = true;
1194           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1195         }
1196     }
1197
1198   v_must_defs_after = v_must_defs = V_MUST_DEF_OPS (ann);
1199   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
1200     {
1201       tree var = V_MUST_DEF_OP (v_must_defs, i);
1202       if (DECL_P (var))
1203         {
1204           found_exposed_symbol = true;
1205           bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1206         }
1207     }
1208
1209   /* If we found any newly exposed symbols, or if there are fewer VDEF
1210      operands in the statement, add the variables we had set in
1211      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
1212      vanishing VDEFs because in those cases, the names that were formerly
1213      generated by this statement are not going to be available anymore.  */
1214   if (found_exposed_symbol
1215       || v_may_defs_disappeared_p (v_may_defs_before, v_may_defs_after)
1216       || v_must_defs_disappeared_p (v_must_defs_before, v_must_defs_after))
1217     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
1218
1219   BITMAP_XFREE (vars_in_vops_to_rename);
1220 }