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