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