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