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