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