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