gcc/tree-dfa.c

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