gcc/tree-dfa.c

   1 /* Data flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "hashtab.h"
  27 #include "pointer-set.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.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-pass.h"
  46 #include "convert.h"
  47 #include "params.h"
  48 #include "cgraph.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 tree find_vars_r (tree *, int *, void *);
  80 static void add_referenced_var (tree, struct walk_state *);
  81
  82
  83 /* Global declarations.  */
  84
  85 /* Array of all variables referenced in the function.  */
  86 htab_t referenced_vars;
  87
  88 /* Default definition for this symbols.  If set for symbol, it
  89    means that the first reference to this variable in the function is a
  90    USE or a VUSE.  In those cases, the SSA renamer creates an SSA name
  91    for this variable with an empty defining statement.  */
  92 htab_t default_defs;
  93
  94
  95 /*---------------------------------------------------------------------------
  96                         Dataflow analysis (DFA) routines
  97 ---------------------------------------------------------------------------*/
  98 /* Find all the variables referenced in the function.  This function
  99    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
 100
 101    Note that this function does not look for statement operands, it simply
 102    determines what variables are referenced in the program and detects
 103    various attributes for each variable used by alias analysis and the
 104    optimizer.  */
 105
 106 static void
 107 find_referenced_vars (void)
 108 {
 109   htab_t vars_found;
 110   basic_block bb;
 111   block_stmt_iterator si;
 112   struct walk_state walk_state;
 113
 114   vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
 115   memset (&walk_state, 0, sizeof (walk_state));
 116   walk_state.vars_found = vars_found;
 117
 118   FOR_EACH_BB (bb)
 119     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 120       {
 121         tree *stmt_p = bsi_stmt_ptr (si);
 122         walk_tree (stmt_p, find_vars_r, &walk_state, NULL);
 123       }
 124
 125   htab_delete (vars_found);
 126 }
 127
 128 struct tree_opt_pass pass_referenced_vars =
 129 {
 130   NULL,                                 /* name */
 131   NULL,                                 /* gate */
 132   find_referenced_vars,                 /* execute */
 133   NULL,                                 /* sub */
 134   NULL,                                 /* next */
 135   0,                                    /* static_pass_number */
 136   TV_FIND_REFERENCED_VARS,              /* tv_id */
 137   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 138   PROP_referenced_vars,                 /* properties_provided */
 139   0,                                    /* properties_destroyed */
 140   0,                                    /* todo_flags_start */
 141   0,                                    /* todo_flags_finish */
 142   0                                     /* letter */
 143 };
 144
 145
 146 /*---------------------------------------------------------------------------
 147                             Manage annotations
 148 ---------------------------------------------------------------------------*/
 149 /* Create a new annotation for a _DECL node T.  */
 150
 151 var_ann_t
 152 create_var_ann (tree t)
 153 {
 154   var_ann_t ann;
 155
 156   gcc_assert (t);
 157   gcc_assert (DECL_P (t));
 158   gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
 159
 160   ann = GGC_NEW (struct var_ann_d);
 161   memset ((void *) ann, 0, sizeof (*ann));
 162
 163   ann->common.type = VAR_ANN;
 164
 165   t->common.ann = (tree_ann_t) ann;
 166
 167   return ann;
 168 }
 169
 170 /* Create a new annotation for a FUNCTION_DECL node T.  */
 171
 172 function_ann_t
 173 create_function_ann (tree t)
 174 {
 175   function_ann_t ann;
 176
 177   gcc_assert (t);
 178   gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
 179   gcc_assert (!t->common.ann || t->common.ann->common.type == FUNCTION_ANN);
 180
 181   ann = ggc_alloc (sizeof (*ann));
 182   memset ((void *) ann, 0, sizeof (*ann));
 183
 184   ann->common.type = FUNCTION_ANN;
 185
 186   t->common.ann = (tree_ann_t) ann;
 187
 188   return ann;
 189 }
 190
 191 /* Create a new annotation for a statement node T.  */
 192
 193 stmt_ann_t
 194 create_stmt_ann (tree t)
 195 {
 196   stmt_ann_t ann;
 197
 198   gcc_assert (is_gimple_stmt (t));
 199   gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN);
 200
 201   ann = GGC_NEW (struct stmt_ann_d);
 202   memset ((void *) ann, 0, sizeof (*ann));
 203
 204   ann->common.type = STMT_ANN;
 205
 206   /* Since we just created the annotation, mark the statement modified.  */
 207   ann->modified = true;
 208
 209   t->common.ann = (tree_ann_t) ann;
 210
 211   return ann;
 212 }
 213
 214 /* Create a new annotation for a tree T.  */
 215
 216 tree_ann_t
 217 create_tree_ann (tree t)
 218 {
 219   tree_ann_t ann;
 220
 221   gcc_assert (t);
 222   gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON);
 223
 224   ann = GGC_NEW (union tree_ann_d);
 225   memset ((void *) ann, 0, sizeof (*ann));
 226
 227   ann->common.type = TREE_ANN_COMMON;
 228   t->common.ann = ann;
 229
 230   return ann;
 231 }
 232
 233 /* Build a temporary.  Make sure and register it to be renamed.  */
 234
 235 tree
 236 make_rename_temp (tree type, const char *prefix)
 237 {
 238   tree t = create_tmp_var (type, prefix);
 239
 240   if (TREE_CODE (type) == COMPLEX_TYPE)
 241     DECL_COMPLEX_GIMPLE_REG_P (t) = 1;
 242
 243   if (referenced_vars)
 244     {
 245       add_referenced_tmp_var (t);
 246       mark_sym_for_renaming (t);
 247     }
 248
 249   return t;
 250 }
 251
 252
 253
 254 /*---------------------------------------------------------------------------
 255                               Debugging functions
 256 ---------------------------------------------------------------------------*/
 257 /* Dump the list of all the referenced variables in the current function to
 258    FILE.  */
 259
 260 void
 261 dump_referenced_vars (FILE *file)
 262 {
 263   tree var;
 264   referenced_var_iterator rvi;
 265
 266   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 267            get_name (current_function_decl), (unsigned) num_referenced_vars);
 268
 269   FOR_EACH_REFERENCED_VAR (var, rvi)
 270     {
 271       fprintf (file, "Variable: ");
 272       dump_variable (file, var);
 273       fprintf (file, "\n");
 274     }
 275 }
 276
 277
 278 /* Dump the list of all the referenced variables to stderr.  */
 279
 280 void
 281 debug_referenced_vars (void)
 282 {
 283   dump_referenced_vars (stderr);
 284 }
 285
 286
 287 /* Dump sub-variables for VAR to FILE.  */
 288
 289 void
 290 dump_subvars_for (FILE *file, tree var)
 291 {
 292   subvar_t sv = get_subvars_for_var (var);
 293
 294   if (!sv)
 295     return;
 296
 297   fprintf (file, "{ ");
 298
 299   for (; sv; sv = sv->next)
 300     {
 301       print_generic_expr (file, sv->var, dump_flags);
 302       fprintf (file, " ");
 303     }
 304
 305   fprintf (file, "}");
 306 }
 307
 308
 309 /* Dumb sub-variables for VAR to stderr.  */
 310
 311 void
 312 debug_subvars_for (tree var)
 313 {
 314   dump_subvars_for (stderr, var);
 315 }
 316
 317
 318 /* Dump variable VAR and its may-aliases to FILE.  */
 319
 320 void
 321 dump_variable (FILE *file, tree var)
 322 {
 323   var_ann_t ann;
 324
 325   if (TREE_CODE (var) == SSA_NAME)
 326     {
 327       if (POINTER_TYPE_P (TREE_TYPE (var)))
 328         dump_points_to_info_for (file, var);
 329       var = SSA_NAME_VAR (var);
 330     }
 331
 332   if (var == NULL_TREE)
 333     {
 334       fprintf (file, "<nil>");
 335       return;
 336     }
 337
 338   print_generic_expr (file, var, dump_flags);
 339
 340   ann = var_ann (var);
 341
 342   fprintf (file, ", UID %u", (unsigned) DECL_UID (var));
 343
 344   fprintf (file, ", ");
 345   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 346
 347   if (ann && ann->type_mem_tag)
 348     {
 349       fprintf (file, ", type memory tag: ");
 350       print_generic_expr (file, ann->type_mem_tag, dump_flags);
 351     }
 352
 353   if (ann && ann->is_alias_tag)
 354     fprintf (file, ", is an alias tag");
 355
 356   if (TREE_ADDRESSABLE (var))
 357     fprintf (file, ", is addressable");
 358
 359   if (is_global_var (var))
 360     fprintf (file, ", is global");
 361
 362   if (TREE_THIS_VOLATILE (var))
 363     fprintf (file, ", is volatile");
 364
 365   if (is_call_clobbered (var))
 366     {
 367       fprintf (file, ", call clobbered");
 368       if (dump_flags & TDF_DETAILS)
 369         {
 370           var_ann_t va = var_ann (var);
 371           unsigned int escape_mask = va->escape_mask;
 372
 373           fprintf (file, " (");
 374           if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
 375             fprintf (file, ", stored in global");
 376           if (escape_mask & ESCAPE_TO_ASM)
 377             fprintf (file, ", goes through ASM");
 378           if (escape_mask & ESCAPE_TO_CALL)
 379             fprintf (file, ", passed to call");
 380           if (escape_mask & ESCAPE_BAD_CAST)
 381             fprintf (file, ", bad cast");
 382           if (escape_mask & ESCAPE_TO_RETURN)
 383             fprintf (file, ", returned from func");
 384           if (escape_mask & ESCAPE_TO_PURE_CONST)
 385             fprintf (file, ", passed to pure/const");
 386           if (escape_mask & ESCAPE_IS_GLOBAL)
 387             fprintf (file, ", is global var");
 388           if (escape_mask & ESCAPE_IS_PARM)
 389             fprintf (file, ", is incoming pointer");
 390           if (escape_mask & ESCAPE_UNKNOWN)
 391             fprintf (file, ", unknown escape");
 392           fprintf (file, " )");
 393         }
 394     }
 395
 396   if (default_def (var))
 397     {
 398       fprintf (file, ", default def: ");
 399       print_generic_expr (file, default_def (var), dump_flags);
 400     }
 401
 402   if (may_aliases (var))
 403     {
 404       fprintf (file, ", may aliases: ");
 405       dump_may_aliases_for (file, var);
 406     }
 407
 408   if (get_subvars_for_var (var))
 409     {
 410       fprintf (file, ", sub-vars: ");
 411       dump_subvars_for (file, var);
 412     }
 413
 414   fprintf (file, "\n");
 415 }
 416
 417
 418 /* Dump variable VAR and its may-aliases to stderr.  */
 419
 420 void
 421 debug_variable (tree var)
 422 {
 423   dump_variable (stderr, var);
 424 }
 425
 426
 427 /* Dump various DFA statistics to FILE.  */
 428
 429 void
 430 dump_dfa_stats (FILE *file)
 431 {
 432   struct dfa_stats_d dfa_stats;
 433
 434   unsigned long size, total = 0;
 435   const char * const fmt_str   = "%-30s%-13s%12s\n";
 436   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 437   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 438   const char *funcname
 439     = lang_hooks.decl_printable_name (current_function_decl, 2);
 440
 441   collect_dfa_stats (&dfa_stats);
 442
 443   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 444
 445   fprintf (file, "---------------------------------------------------------\n");
 446   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 447   fprintf (file, fmt_str, "", "  instances  ", "used ");
 448   fprintf (file, "---------------------------------------------------------\n");
 449
 450   size = num_referenced_vars * sizeof (tree);
 451   total += size;
 452   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 453            SCALE (size), LABEL (size));
 454
 455   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 456   total += size;
 457   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 458            SCALE (size), LABEL (size));
 459
 460   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 461   total += size;
 462   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 463            SCALE (size), LABEL (size));
 464
 465   size = dfa_stats.num_uses * sizeof (tree *);
 466   total += size;
 467   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 468            SCALE (size), LABEL (size));
 469
 470   size = dfa_stats.num_defs * sizeof (tree *);
 471   total += size;
 472   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 473            SCALE (size), LABEL (size));
 474
 475   size = dfa_stats.num_vuses * sizeof (tree *);
 476   total += size;
 477   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 478            SCALE (size), LABEL (size));
 479
 480   size = dfa_stats.num_v_may_defs * sizeof (tree *);
 481   total += size;
 482   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
 483            SCALE (size), LABEL (size));
 484
 485   size = dfa_stats.num_v_must_defs * sizeof (tree *);
 486   total += size;
 487   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
 488            SCALE (size), LABEL (size));
 489
 490   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 491   total += size;
 492   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 493            SCALE (size), LABEL (size));
 494
 495   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 496   total += size;
 497   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 498            SCALE (size), LABEL (size));
 499
 500   fprintf (file, "---------------------------------------------------------\n");
 501   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 502            LABEL (total));
 503   fprintf (file, "---------------------------------------------------------\n");
 504   fprintf (file, "\n");
 505
 506   if (dfa_stats.num_phis)
 507     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 508              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 509              dfa_stats.max_num_phi_args);
 510
 511   fprintf (file, "\n");
 512 }
 513
 514
 515 /* Dump DFA statistics on stderr.  */
 516
 517 void
 518 debug_dfa_stats (void)
 519 {
 520   dump_dfa_stats (stderr);
 521 }
 522
 523
 524 /* Collect DFA statistics and store them in the structure pointed to by
 525    DFA_STATS_P.  */
 526
 527 static void
 528 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 529 {
 530   struct pointer_set_t *pset;
 531   basic_block bb;
 532   block_stmt_iterator i;
 533
 534   gcc_assert (dfa_stats_p);
 535
 536   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 537
 538   /* Walk all the trees in the function counting references.  Start at
 539      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 540   pset = pointer_set_create ();
 541
 542   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 543        !bsi_end_p (i); bsi_next (&i))
 544     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 545                pset);
 546
 547   pointer_set_destroy (pset);
 548
 549   FOR_EACH_BB (bb)
 550     {
 551       tree phi;
 552       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 553         {
 554           dfa_stats_p->num_phis++;
 555           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 556           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 557             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 558         }
 559     }
 560 }
 561
 562
 563 /* Callback for walk_tree to collect DFA statistics for a tree and its
 564    children.  */
 565
 566 static tree
 567 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 568                      void *data)
 569 {
 570   tree t = *tp;
 571   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 572
 573   if (t->common.ann)
 574     {
 575       switch (ann_type (t->common.ann))
 576         {
 577         case STMT_ANN:
 578           {
 579             dfa_stats_p->num_stmt_anns++;
 580             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 581             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 582             dfa_stats_p->num_v_may_defs += NUM_SSA_OPERANDS (t, SSA_OP_VMAYDEF);
 583             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 584             dfa_stats_p->num_v_must_defs +=
 585                                   NUM_SSA_OPERANDS (t, SSA_OP_VMUSTDEF);
 586             break;
 587           }
 588
 589         case VAR_ANN:
 590           dfa_stats_p->num_var_anns++;
 591           break;
 592
 593         default:
 594           break;
 595         }
 596     }
 597
 598   return NULL;
 599 }
 600
 601
 602 /*---------------------------------------------------------------------------
 603                              Miscellaneous helpers
 604 ---------------------------------------------------------------------------*/
 605 /* Callback for walk_tree.  Used to collect variables referenced in
 606    the function.  */
 607
 608 static tree
 609 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 610 {
 611   struct walk_state *walk_state = (struct walk_state *) data;
 612
 613   /* If T is a regular variable that the optimizers are interested
 614      in, add it to the list of variables.  */
 615   if (SSA_VAR_P (*tp))
 616     add_referenced_var (*tp, walk_state);
 617
 618   /* Type, _DECL and constant nodes have no interesting children.
 619      Ignore them.  */
 620   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 621     *walk_subtrees = 0;
 622
 623   return NULL_TREE;
 624 }
 625
 626
 627 /* Lookup UID in the referenced_vars hashtable and return the associated
 628    variable or NULL if it is not there.  */
 629
 630 tree
 631 referenced_var_lookup_if_exists (unsigned int uid)
 632 {
 633   struct int_tree_map *h, in;
 634   in.uid = uid;
 635   h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
 636   if (h)
 637     return h->to;
 638   return NULL_TREE;
 639 }
 640
 641 /* Lookup UID in the referenced_vars hashtable and return the associated
 642    variable.  */
 643
 644 tree
 645 referenced_var_lookup (unsigned int uid)
 646 {
 647   struct int_tree_map *h, in;
 648   in.uid = uid;
 649   h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
 650   gcc_assert (h || uid == 0);
 651   if (h)
 652     return h->to;
 653   return NULL_TREE;
 654 }
 655
 656 /* Insert the pair UID, TO into the referenced_vars hashtable.  */
 657
 658 static void
 659 referenced_var_insert (unsigned int uid, tree to)
 660 {
 661   struct int_tree_map *h;
 662   void **loc;
 663
 664   h = GGC_NEW (struct int_tree_map);
 665   h->uid = uid;
 666   h->to = to;
 667   loc = htab_find_slot_with_hash (referenced_vars, h, uid, INSERT);
 668   *(struct int_tree_map **)  loc = h;
 669 }
 670
 671 /* Lookup VAR UID in the default_defs hashtable and return the associated
 672    variable.  */
 673
 674 tree
 675 default_def (tree var)
 676 {
 677   struct int_tree_map *h, in;
 678   gcc_assert (SSA_VAR_P (var));
 679   in.uid = DECL_UID (var);
 680   h = (struct int_tree_map *) htab_find_with_hash (default_defs, &in,
 681                                                    DECL_UID (var));
 682   if (h)
 683     return h->to;
 684   return NULL_TREE;
 685 }
 686
 687 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 688
 689 void
 690 set_default_def (tree var, tree def)
 691 {
 692   struct int_tree_map in;
 693   struct int_tree_map *h;
 694   void **loc;
 695
 696   gcc_assert (SSA_VAR_P (var));
 697   in.uid = DECL_UID (var);
 698   if (!def && default_def (var))
 699     {
 700       loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
 701       htab_remove_elt (default_defs, *loc);
 702       return;
 703     }
 704   gcc_assert (TREE_CODE (def) == SSA_NAME);
 705   loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
 706   /* Default definition might be changed by tail call optimization.  */
 707   if (!*loc)
 708     {
 709       h = GGC_NEW (struct int_tree_map);
 710       h->uid = DECL_UID (var);
 711       h->to = def;
 712       *(struct int_tree_map **)  loc = h;
 713     }
 714    else
 715     {
 716       h = (struct int_tree_map *) *loc;
 717       h->to = def;
 718     }
 719 }
 720
 721 /* Add VAR to the list of dereferenced variables.
 722
 723    WALK_STATE contains a hash table used to avoid adding the same
 724       variable more than once. Note that this function assumes that
 725       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 726       duplicate checking is done.  */
 727
 728 static void
 729 add_referenced_var (tree var, struct walk_state *walk_state)
 730 {
 731   void **slot;
 732   var_ann_t v_ann;
 733
 734   v_ann = get_var_ann (var);
 735
 736   if (walk_state)
 737     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 738   else
 739     slot = NULL;
 740
 741   if (slot == NULL || *slot == NULL)
 742     {
 743       /* This is the first time we find this variable, add it to the
 744          REFERENCED_VARS array and annotate it with attributes that are
 745          intrinsic to the variable.  */
 746       if (slot)
 747         *slot = (void *) var;
 748
 749       referenced_var_insert (DECL_UID (var), var);
 750
 751       /* Tag's don't have DECL_INITIAL.  */
 752       if (MTAG_P (var))
 753         return;
 754
 755       /* Scan DECL_INITIAL for pointer variables as they may contain
 756          address arithmetic referencing the address of other
 757          variables.  */
 758       if (DECL_INITIAL (var)
 759           /* Initializers of external variables are not useful to the
 760              optimizers.  */
 761           && !DECL_EXTERNAL (var)
 762           /* It's not necessary to walk the initial value of non-constant
 763              variables because it cannot be propagated by the
 764              optimizers.  */
 765           && (TREE_CONSTANT (var) || TREE_READONLY (var)))
 766         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
 767     }
 768 }
 769
 770
 771 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 772
 773 tree
 774 get_virtual_var (tree var)
 775 {
 776   STRIP_NOPS (var);
 777
 778   if (TREE_CODE (var) == SSA_NAME)
 779     var = SSA_NAME_VAR (var);
 780
 781   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 782          || handled_component_p (var))
 783     var = TREE_OPERAND (var, 0);
 784
 785   /* Treating GIMPLE registers as virtual variables makes no sense.
 786      Also complain if we couldn't extract a _DECL out of the original
 787      expression.  */
 788   gcc_assert (SSA_VAR_P (var));
 789   gcc_assert (!is_gimple_reg (var));
 790
 791   return var;
 792 }
 793
 794 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
 795    add_referenced_var, but is used by passes that need to add new temps to
 796    the REFERENCED_VARS array after the program has been scanned for
 797    variables.  The variable will just receive a new UID and be added
 798    to the REFERENCED_VARS array without checking for duplicates.  */
 799
 800 void
 801 add_referenced_tmp_var (tree var)
 802 {
 803   add_referenced_var (var, NULL);
 804 }
 805
 806
 807 /* Mark all the non-SSA variables found in STMT's operands to be
 808    processed by update_ssa.  */
 809
 810 void
 811 mark_new_vars_to_rename (tree stmt)
 812 {
 813   ssa_op_iter iter;
 814   tree val;
 815   bitmap vars_in_vops_to_rename;
 816   bool found_exposed_symbol = false;
 817   int v_may_defs_before, v_may_defs_after;
 818   int v_must_defs_before, v_must_defs_after;
 819
 820   if (TREE_CODE (stmt) == PHI_NODE)
 821     return;
 822
 823   get_stmt_ann (stmt);
 824   vars_in_vops_to_rename = BITMAP_ALLOC (NULL);
 825
 826   /* Before re-scanning the statement for operands, mark the existing
 827      virtual operands to be renamed again.  We do this because when new
 828      symbols are exposed, the virtual operands that were here before due to
 829      aliasing will probably be removed by the call to get_stmt_operand.
 830      Therefore, we need to flag them to be renamed beforehand.
 831
 832      We flag them in a separate bitmap because we don't really want to
 833      rename them if there are not any newly exposed symbols in the
 834      statement operands.  */
 835   v_may_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
 836   v_must_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
 837
 838   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
 839                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
 840     {
 841       if (!DECL_P (val))
 842         val = SSA_NAME_VAR (val);
 843       bitmap_set_bit (vars_in_vops_to_rename, DECL_UID (val));
 844     }
 845
 846   /* Now force an operand re-scan on the statement and mark any newly
 847      exposed variables.  */
 848   update_stmt (stmt);
 849
 850   v_may_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
 851   v_must_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
 852
 853   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS)
 854     if (DECL_P (val))
 855       {
 856         found_exposed_symbol = true;
 857         mark_sym_for_renaming (val);
 858       }
 859
 860   /* If we found any newly exposed symbols, or if there are fewer VDEF
 861      operands in the statement, add the variables we had set in
 862      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
 863      vanishing VDEFs because in those cases, the names that were formerly
 864      generated by this statement are not going to be available anymore.  */
 865   if (found_exposed_symbol
 866       || v_may_defs_before > v_may_defs_after
 867       || v_must_defs_before > v_must_defs_after)
 868     mark_set_for_renaming (vars_in_vops_to_rename);
 869
 870   BITMAP_FREE (vars_in_vops_to_rename);
 871 }
 872
 873 /* Find all variables within the gimplified statement that were not previously
 874    visible to the function and add them to the referenced variables list.  */
 875
 876 static tree
 877 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 878                             void *data ATTRIBUTE_UNUSED)
 879 {
 880   tree t = *tp;
 881
 882   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 883     {
 884       add_referenced_tmp_var (t);
 885       mark_sym_for_renaming (t);
 886     }
 887
 888   if (IS_TYPE_OR_DECL_P (t))
 889     *walk_subtrees = 0;
 890
 891   return NULL;
 892 }
 893
 894 void
 895 find_new_referenced_vars (tree *stmt_p)
 896 {
 897   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 898 }
 899
 900
 901 /* If REF is a handled component reference for a structure, return the
 902    base variable.  The access range is delimited by bit positions *POFFSET and
 903    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 904    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 905    and *PMAX_SIZE are equal, the access is non-variable.  */
 906
 907 tree
 908 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 909                          HOST_WIDE_INT *psize,
 910                          HOST_WIDE_INT *pmax_size)
 911 {
 912   HOST_WIDE_INT bitsize = -1;
 913   HOST_WIDE_INT maxsize = -1;
 914   tree size_tree = NULL_TREE;
 915   tree bit_offset = bitsize_zero_node;
 916
 917   gcc_assert (!SSA_VAR_P (exp));
 918
 919   /* First get the final access size from just the outermost expression.  */
 920   if (TREE_CODE (exp) == COMPONENT_REF)
 921     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 922   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 923     size_tree = TREE_OPERAND (exp, 1);
 924   else
 925     {
 926       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 927       if (mode == BLKmode)
 928         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 929       else
 930         bitsize = GET_MODE_BITSIZE (mode);
 931     }
 932   if (size_tree != NULL_TREE)
 933     {
 934       if (! host_integerp (size_tree, 1))
 935         bitsize = -1;
 936       else
 937         bitsize = TREE_INT_CST_LOW (size_tree);
 938     }
 939
 940   /* Initially, maxsize is the same as the accessed element size.
 941      In the following it will only grow (or become -1).  */
 942   maxsize = bitsize;
 943
 944   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 945      and find the ultimate containing object.  */
 946   while (1)
 947     {
 948       switch (TREE_CODE (exp))
 949         {
 950         case BIT_FIELD_REF:
 951           bit_offset = size_binop (PLUS_EXPR, bit_offset,
 952                                    TREE_OPERAND (exp, 2));
 953           break;
 954
 955         case COMPONENT_REF:
 956           {
 957             tree field = TREE_OPERAND (exp, 1);
 958             tree this_offset = component_ref_field_offset (exp);
 959
 960             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 961               {
 962                 this_offset = size_binop (MULT_EXPR,
 963                                           fold_convert (bitsizetype,
 964                                                         this_offset),
 965                                           bitsize_unit_node);
 966                 bit_offset = size_binop (PLUS_EXPR,
 967                                          bit_offset, this_offset);
 968                 bit_offset = size_binop (PLUS_EXPR, bit_offset,
 969                                          DECL_FIELD_BIT_OFFSET (field));
 970               }
 971             else
 972               {
 973                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 974                 /* We need to adjust maxsize to the whole structure bitsize.
 975                    But we can subtract any constant offset seen sofar,
 976                    because that would get us out of the structure otherwise.  */
 977                 if (maxsize != -1
 978                     && csize && host_integerp (csize, 1))
 979                   {
 980                     maxsize = (TREE_INT_CST_LOW (csize)
 981                                - TREE_INT_CST_LOW (bit_offset));
 982                   }
 983                 else
 984                   maxsize = -1;
 985               }
 986           }
 987           break;
 988
 989         case ARRAY_REF:
 990         case ARRAY_RANGE_REF:
 991           {
 992             tree index = TREE_OPERAND (exp, 1);
 993             tree low_bound = array_ref_low_bound (exp);
 994             tree unit_size = array_ref_element_size (exp);
 995
 996             if (! integer_zerop (low_bound))
 997               index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
 998                                    index, low_bound);
 999             index = size_binop (MULT_EXPR,
1000                                 fold_convert (sizetype, index), unit_size);
1001             if (TREE_CODE (index) == INTEGER_CST)
1002               {
1003                 index = size_binop (MULT_EXPR,
1004                                     fold_convert (bitsizetype, index),
1005                                     bitsize_unit_node);
1006                 bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
1007               }
1008             else
1009               {
1010                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
1011                 /* We need to adjust maxsize to the whole array bitsize.
1012                    But we can subtract any constant offset seen sofar,
1013                    because that would get us outside of the array otherwise.  */
1014                 if (maxsize != -1
1015                     && asize && host_integerp (asize, 1))
1016                   {
1017                     maxsize = (TREE_INT_CST_LOW (asize)
1018                                - TREE_INT_CST_LOW (bit_offset));
1019                   }
1020                 else
1021                   maxsize = -1;
1022               }
1023           }
1024           break;
1025
1026         case REALPART_EXPR:
1027           break;
1028
1029         case IMAGPART_EXPR:
1030           bit_offset = size_binop (PLUS_EXPR, bit_offset,
1031                                    bitsize_int (bitsize));
1032           break;
1033
1034         case VIEW_CONVERT_EXPR:
1035           /* ???  We probably should give up here and bail out.  */
1036           break;
1037
1038         default:
1039           goto done;
1040         }
1041
1042       exp = TREE_OPERAND (exp, 0);
1043     }
1044  done:
1045
1046   /* ???  Due to negative offsets in ARRAY_REF we can end up with
1047      negative bit_offset here.  We might want to store a zero offset
1048      in this case.  */
1049   *poffset = TREE_INT_CST_LOW (bit_offset);
1050   *psize = bitsize;
1051   *pmax_size = maxsize;
1052
1053   return exp;
1054 }