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     fprintf (file, ", call clobbered");
 367
 368   if (default_def (var))
 369     {
 370       fprintf (file, ", default def: ");
 371       print_generic_expr (file, default_def (var), dump_flags);
 372     }
 373
 374   if (may_aliases (var))
 375     {
 376       fprintf (file, ", may aliases: ");
 377       dump_may_aliases_for (file, var);
 378     }
 379
 380   if (get_subvars_for_var (var))
 381     {
 382       fprintf (file, ", sub-vars: ");
 383       dump_subvars_for (file, var);
 384     }
 385
 386   fprintf (file, "\n");
 387 }
 388
 389
 390 /* Dump variable VAR and its may-aliases to stderr.  */
 391
 392 void
 393 debug_variable (tree var)
 394 {
 395   dump_variable (stderr, var);
 396 }
 397
 398
 399 /* Dump various DFA statistics to FILE.  */
 400
 401 void
 402 dump_dfa_stats (FILE *file)
 403 {
 404   struct dfa_stats_d dfa_stats;
 405
 406   unsigned long size, total = 0;
 407   const char * const fmt_str   = "%-30s%-13s%12s\n";
 408   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 409   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 410   const char *funcname
 411     = lang_hooks.decl_printable_name (current_function_decl, 2);
 412
 413   collect_dfa_stats (&dfa_stats);
 414
 415   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 416
 417   fprintf (file, "---------------------------------------------------------\n");
 418   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 419   fprintf (file, fmt_str, "", "  instances  ", "used ");
 420   fprintf (file, "---------------------------------------------------------\n");
 421
 422   size = num_referenced_vars * sizeof (tree);
 423   total += size;
 424   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 425            SCALE (size), LABEL (size));
 426
 427   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 428   total += size;
 429   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 430            SCALE (size), LABEL (size));
 431
 432   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 433   total += size;
 434   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 435            SCALE (size), LABEL (size));
 436
 437   size = dfa_stats.num_uses * sizeof (tree *);
 438   total += size;
 439   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 440            SCALE (size), LABEL (size));
 441
 442   size = dfa_stats.num_defs * sizeof (tree *);
 443   total += size;
 444   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 445            SCALE (size), LABEL (size));
 446
 447   size = dfa_stats.num_vuses * sizeof (tree *);
 448   total += size;
 449   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 450            SCALE (size), LABEL (size));
 451
 452   size = dfa_stats.num_v_may_defs * sizeof (tree *);
 453   total += size;
 454   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
 455            SCALE (size), LABEL (size));
 456
 457   size = dfa_stats.num_v_must_defs * sizeof (tree *);
 458   total += size;
 459   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
 460            SCALE (size), LABEL (size));
 461
 462   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 463   total += size;
 464   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 465            SCALE (size), LABEL (size));
 466
 467   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 468   total += size;
 469   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 470            SCALE (size), LABEL (size));
 471
 472   fprintf (file, "---------------------------------------------------------\n");
 473   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 474            LABEL (total));
 475   fprintf (file, "---------------------------------------------------------\n");
 476   fprintf (file, "\n");
 477
 478   if (dfa_stats.num_phis)
 479     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 480              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 481              dfa_stats.max_num_phi_args);
 482
 483   fprintf (file, "\n");
 484 }
 485
 486
 487 /* Dump DFA statistics on stderr.  */
 488
 489 void
 490 debug_dfa_stats (void)
 491 {
 492   dump_dfa_stats (stderr);
 493 }
 494
 495
 496 /* Collect DFA statistics and store them in the structure pointed to by
 497    DFA_STATS_P.  */
 498
 499 static void
 500 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 501 {
 502   struct pointer_set_t *pset;
 503   basic_block bb;
 504   block_stmt_iterator i;
 505
 506   gcc_assert (dfa_stats_p);
 507
 508   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 509
 510   /* Walk all the trees in the function counting references.  Start at
 511      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 512   pset = pointer_set_create ();
 513
 514   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 515        !bsi_end_p (i); bsi_next (&i))
 516     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 517                pset);
 518
 519   pointer_set_destroy (pset);
 520
 521   FOR_EACH_BB (bb)
 522     {
 523       tree phi;
 524       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 525         {
 526           dfa_stats_p->num_phis++;
 527           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 528           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 529             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 530         }
 531     }
 532 }
 533
 534
 535 /* Callback for walk_tree to collect DFA statistics for a tree and its
 536    children.  */
 537
 538 static tree
 539 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 540                      void *data)
 541 {
 542   tree t = *tp;
 543   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 544
 545   if (t->common.ann)
 546     {
 547       switch (ann_type (t->common.ann))
 548         {
 549         case STMT_ANN:
 550           {
 551             dfa_stats_p->num_stmt_anns++;
 552             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 553             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 554             dfa_stats_p->num_v_may_defs += NUM_SSA_OPERANDS (t, SSA_OP_VMAYDEF);
 555             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 556             dfa_stats_p->num_v_must_defs +=
 557                                   NUM_SSA_OPERANDS (t, SSA_OP_VMUSTDEF);
 558             break;
 559           }
 560
 561         case VAR_ANN:
 562           dfa_stats_p->num_var_anns++;
 563           break;
 564
 565         default:
 566           break;
 567         }
 568     }
 569
 570   return NULL;
 571 }
 572
 573
 574 /*---------------------------------------------------------------------------
 575                              Miscellaneous helpers
 576 ---------------------------------------------------------------------------*/
 577 /* Callback for walk_tree.  Used to collect variables referenced in
 578    the function.  */
 579
 580 static tree
 581 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 582 {
 583   struct walk_state *walk_state = (struct walk_state *) data;
 584
 585   /* If T is a regular variable that the optimizers are interested
 586      in, add it to the list of variables.  */
 587   if (SSA_VAR_P (*tp))
 588     add_referenced_var (*tp, walk_state);
 589
 590   /* Type, _DECL and constant nodes have no interesting children.
 591      Ignore them.  */
 592   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 593     *walk_subtrees = 0;
 594
 595   return NULL_TREE;
 596 }
 597
 598
 599 /* Lookup UID in the referenced_vars hashtable and return the associated
 600    variable or NULL if it is not there.  */
 601
 602 tree
 603 referenced_var_lookup_if_exists (unsigned int uid)
 604 {
 605   struct int_tree_map *h, in;
 606   in.uid = uid;
 607   h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
 608   if (h)
 609     return h->to;
 610   return NULL_TREE;
 611 }
 612
 613 /* Lookup UID in the referenced_vars hashtable and return the associated
 614    variable.  */
 615
 616 tree
 617 referenced_var_lookup (unsigned int uid)
 618 {
 619   struct int_tree_map *h, in;
 620   in.uid = uid;
 621   h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
 622   gcc_assert (h || uid == 0);
 623   if (h)
 624     return h->to;
 625   return NULL_TREE;
 626 }
 627
 628 /* Insert the pair UID, TO into the referenced_vars hashtable.  */
 629
 630 static void
 631 referenced_var_insert (unsigned int uid, tree to)
 632 {
 633   struct int_tree_map *h;
 634   void **loc;
 635
 636   h = GGC_NEW (struct int_tree_map);
 637   h->uid = uid;
 638   h->to = to;
 639   loc = htab_find_slot_with_hash (referenced_vars, h, uid, INSERT);
 640   *(struct int_tree_map **)  loc = h;
 641 }
 642
 643 /* Lookup VAR UID in the default_defs hashtable and return the associated
 644    variable.  */
 645
 646 tree
 647 default_def (tree var)
 648 {
 649   struct int_tree_map *h, in;
 650   gcc_assert (SSA_VAR_P (var));
 651   in.uid = DECL_UID (var);
 652   h = (struct int_tree_map *) htab_find_with_hash (default_defs, &in,
 653                                                    DECL_UID (var));
 654   if (h)
 655     return h->to;
 656   return NULL_TREE;
 657 }
 658
 659 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 660
 661 void
 662 set_default_def (tree var, tree def)
 663 {
 664   struct int_tree_map in;
 665   struct int_tree_map *h;
 666   void **loc;
 667
 668   gcc_assert (SSA_VAR_P (var));
 669   in.uid = DECL_UID (var);
 670   if (!def && default_def (var))
 671     {
 672       loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
 673       htab_remove_elt (default_defs, *loc);
 674       return;
 675     }
 676   gcc_assert (TREE_CODE (def) == SSA_NAME);
 677   loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
 678   /* Default definition might be changed by tail call optimization.  */
 679   if (!*loc)
 680     {
 681       h = GGC_NEW (struct int_tree_map);
 682       h->uid = DECL_UID (var);
 683       h->to = def;
 684       *(struct int_tree_map **)  loc = h;
 685     }
 686    else
 687     {
 688       h = (struct int_tree_map *) *loc;
 689       h->to = def;
 690     }
 691 }
 692
 693 /* Add VAR to the list of dereferenced variables.
 694
 695    WALK_STATE contains a hash table used to avoid adding the same
 696       variable more than once. Note that this function assumes that
 697       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 698       duplicate checking is done.  */
 699
 700 static void
 701 add_referenced_var (tree var, struct walk_state *walk_state)
 702 {
 703   void **slot;
 704   var_ann_t v_ann;
 705
 706   v_ann = get_var_ann (var);
 707
 708   if (walk_state)
 709     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 710   else
 711     slot = NULL;
 712
 713   if (slot == NULL || *slot == NULL)
 714     {
 715       /* This is the first time we find this variable, add it to the
 716          REFERENCED_VARS array and annotate it with attributes that are
 717          intrinsic to the variable.  */
 718       if (slot)
 719         *slot = (void *) var;
 720
 721       referenced_var_insert (DECL_UID (var), var);
 722
 723       /* Global variables are always call-clobbered.  */
 724       if (is_global_var (var))
 725         mark_call_clobbered (var);
 726
 727       /* Tag's don't have DECL_INITIAL.  */
 728       if (MTAG_P (var))
 729         return;
 730
 731       /* Scan DECL_INITIAL for pointer variables as they may contain
 732          address arithmetic referencing the address of other
 733          variables.  */
 734       if (DECL_INITIAL (var)
 735           /* Initializers of external variables are not useful to the
 736              optimizers.  */
 737           && !DECL_EXTERNAL (var)
 738           /* It's not necessary to walk the initial value of non-constant
 739              variables because it cannot be propagated by the
 740              optimizers.  */
 741           && (TREE_CONSTANT (var) || TREE_READONLY (var)))
 742         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
 743     }
 744 }
 745
 746
 747 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 748
 749 tree
 750 get_virtual_var (tree var)
 751 {
 752   STRIP_NOPS (var);
 753
 754   if (TREE_CODE (var) == SSA_NAME)
 755     var = SSA_NAME_VAR (var);
 756
 757   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 758          || handled_component_p (var))
 759     var = TREE_OPERAND (var, 0);
 760
 761   /* Treating GIMPLE registers as virtual variables makes no sense.
 762      Also complain if we couldn't extract a _DECL out of the original
 763      expression.  */
 764   gcc_assert (SSA_VAR_P (var));
 765   gcc_assert (!is_gimple_reg (var));
 766
 767   return var;
 768 }
 769
 770 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
 771    add_referenced_var, but is used by passes that need to add new temps to
 772    the REFERENCED_VARS array after the program has been scanned for
 773    variables.  The variable will just receive a new UID and be added
 774    to the REFERENCED_VARS array without checking for duplicates.  */
 775
 776 void
 777 add_referenced_tmp_var (tree var)
 778 {
 779   add_referenced_var (var, NULL);
 780 }
 781
 782
 783 /* Mark all the non-SSA variables found in STMT's operands to be
 784    processed by update_ssa.  */
 785
 786 void
 787 mark_new_vars_to_rename (tree stmt)
 788 {
 789   ssa_op_iter iter;
 790   tree val;
 791   bitmap vars_in_vops_to_rename;
 792   bool found_exposed_symbol = false;
 793   int v_may_defs_before, v_may_defs_after;
 794   int v_must_defs_before, v_must_defs_after;
 795
 796   if (TREE_CODE (stmt) == PHI_NODE)
 797     return;
 798
 799   vars_in_vops_to_rename = BITMAP_ALLOC (NULL);
 800
 801   /* Before re-scanning the statement for operands, mark the existing
 802      virtual operands to be renamed again.  We do this because when new
 803      symbols are exposed, the virtual operands that were here before due to
 804      aliasing will probably be removed by the call to get_stmt_operand.
 805      Therefore, we need to flag them to be renamed beforehand.
 806
 807      We flag them in a separate bitmap because we don't really want to
 808      rename them if there are not any newly exposed symbols in the
 809      statement operands.  */
 810   v_may_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
 811   v_must_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
 812
 813   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
 814                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
 815     {
 816       if (!DECL_P (val))
 817         val = SSA_NAME_VAR (val);
 818       bitmap_set_bit (vars_in_vops_to_rename, DECL_UID (val));
 819     }
 820
 821   /* Now force an operand re-scan on the statement and mark any newly
 822      exposed variables.  */
 823   update_stmt (stmt);
 824
 825   v_may_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
 826   v_must_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
 827
 828   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS)
 829     if (DECL_P (val))
 830       {
 831         found_exposed_symbol = true;
 832         mark_sym_for_renaming (val);
 833       }
 834
 835   /* If we found any newly exposed symbols, or if there are fewer VDEF
 836      operands in the statement, add the variables we had set in
 837      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
 838      vanishing VDEFs because in those cases, the names that were formerly
 839      generated by this statement are not going to be available anymore.  */
 840   if (found_exposed_symbol
 841       || v_may_defs_before > v_may_defs_after
 842       || v_must_defs_before > v_must_defs_after)
 843     mark_set_for_renaming (vars_in_vops_to_rename);
 844
 845   BITMAP_FREE (vars_in_vops_to_rename);
 846 }
 847
 848 /* Find all variables within the gimplified statement that were not previously
 849    visible to the function and add them to the referenced variables list.  */
 850
 851 static tree
 852 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 853                             void *data ATTRIBUTE_UNUSED)
 854 {
 855   tree t = *tp;
 856
 857   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 858     {
 859       add_referenced_tmp_var (t);
 860       mark_sym_for_renaming (t);
 861     }
 862
 863   if (IS_TYPE_OR_DECL_P (t))
 864     *walk_subtrees = 0;
 865
 866   return NULL;
 867 }
 868
 869 void
 870 find_new_referenced_vars (tree *stmt_p)
 871 {
 872   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 873 }
 874
 875
 876 /* If REF is a handled component reference for a structure, return the
 877    base variable.  The access range is delimited by bit positions *POFFSET and
 878    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 879    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 880    and *PMAX_SIZE are equal, the access is non-variable.  */
 881
 882 tree
 883 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 884                          HOST_WIDE_INT *psize,
 885                          HOST_WIDE_INT *pmax_size)
 886 {
 887   HOST_WIDE_INT bitsize = -1;
 888   HOST_WIDE_INT maxsize = -1;
 889   tree size_tree = NULL_TREE;
 890   tree bit_offset = bitsize_zero_node;
 891
 892   gcc_assert (!SSA_VAR_P (exp));
 893
 894   /* First get the final access size from just the outermost expression.  */
 895   if (TREE_CODE (exp) == COMPONENT_REF)
 896     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 897   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 898     size_tree = TREE_OPERAND (exp, 1);
 899   else
 900     {
 901       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 902       if (mode == BLKmode)
 903         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 904       else
 905         bitsize = GET_MODE_BITSIZE (mode);
 906     }
 907   if (size_tree != NULL_TREE)
 908     {
 909       if (! host_integerp (size_tree, 1))
 910         bitsize = -1;
 911       else
 912         bitsize = TREE_INT_CST_LOW (size_tree);
 913     }
 914
 915   /* Initially, maxsize is the same as the accessed element size.
 916      In the following it will only grow (or become -1).  */
 917   maxsize = bitsize;
 918
 919   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 920      and find the ultimate containing object.  */
 921   while (1)
 922     {
 923       switch (TREE_CODE (exp))
 924         {
 925         case BIT_FIELD_REF:
 926           bit_offset = size_binop (PLUS_EXPR, bit_offset,
 927                                    TREE_OPERAND (exp, 2));
 928           break;
 929
 930         case COMPONENT_REF:
 931           {
 932             tree field = TREE_OPERAND (exp, 1);
 933             tree this_offset = component_ref_field_offset (exp);
 934
 935             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 936               {
 937                 this_offset = size_binop (MULT_EXPR,
 938                                           fold_convert (bitsizetype,
 939                                                         this_offset),
 940                                           bitsize_unit_node);
 941                 bit_offset = size_binop (PLUS_EXPR,
 942                                          bit_offset, this_offset);
 943                 bit_offset = size_binop (PLUS_EXPR, bit_offset,
 944                                          DECL_FIELD_BIT_OFFSET (field));
 945               }
 946             else
 947               {
 948                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 949                 /* We need to adjust maxsize to the whole structure bitsize.
 950                    But we can subtract any constant offset seen sofar,
 951                    because that would get us out of the structure otherwise.  */
 952                 if (maxsize != -1
 953                     && csize && host_integerp (csize, 1))
 954                   {
 955                     maxsize = (TREE_INT_CST_LOW (csize)
 956                                - TREE_INT_CST_LOW (bit_offset));
 957                   }
 958                 else
 959                   maxsize = -1;
 960               }
 961           }
 962           break;
 963
 964         case ARRAY_REF:
 965         case ARRAY_RANGE_REF:
 966           {
 967             tree index = TREE_OPERAND (exp, 1);
 968             tree low_bound = array_ref_low_bound (exp);
 969             tree unit_size = array_ref_element_size (exp);
 970
 971             if (! integer_zerop (low_bound))
 972               index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
 973                                    index, low_bound);
 974             index = size_binop (MULT_EXPR,
 975                                 fold_convert (sizetype, index), unit_size);
 976             if (TREE_CODE (index) == INTEGER_CST)
 977               {
 978                 index = size_binop (MULT_EXPR,
 979                                     fold_convert (bitsizetype, index),
 980                                     bitsize_unit_node);
 981                 bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
 982               }
 983             else
 984               {
 985                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 986                 /* We need to adjust maxsize to the whole array bitsize.
 987                    But we can subtract any constant offset seen sofar,
 988                    because that would get us outside of the array otherwise.  */
 989                 if (maxsize != -1
 990                     && asize && host_integerp (asize, 1))
 991                   {
 992                     maxsize = (TREE_INT_CST_LOW (asize)
 993                                - TREE_INT_CST_LOW (bit_offset));
 994                   }
 995                 else
 996                   maxsize = -1;
 997               }
 998           }
 999           break;
1000
1001         case REALPART_EXPR:
1002           break;
1003
1004         case IMAGPART_EXPR:
1005           bit_offset = size_binop (PLUS_EXPR, bit_offset,
1006                                    bitsize_int (bitsize));
1007           break;
1008
1009         case VIEW_CONVERT_EXPR:
1010           /* ???  We probably should give up here and bail out.  */
1011           break;
1012
1013         default:
1014           goto done;
1015         }
1016
1017       exp = TREE_OPERAND (exp, 0);
1018     }
1019  done:
1020
1021   /* ???  Due to negative offsets in ARRAY_REF we can end up with
1022      negative bit_offset here.  We might want to store a zero offset
1023      in this case.  */
1024   *poffset = TREE_INT_CST_LOW (bit_offset);
1025   *psize = bitsize;
1026   *pmax_size = maxsize;
1027
1028   return exp;
1029 }