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 (TREE_TYPE (t)) == COMPLEX_TYPE
 210       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 211     DECL_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       var_ann_t va = var_ann (var);
 338       unsigned int escape_mask = va->escape_mask;
 339
 340       fprintf (file, ", call clobbered");
 341       fprintf (file, " (");
 342       if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
 343         fprintf (file, ", stored in global");
 344       if (escape_mask & ESCAPE_TO_ASM)
 345         fprintf (file, ", goes through ASM");
 346       if (escape_mask & ESCAPE_TO_CALL)
 347         fprintf (file, ", passed to call");
 348       if (escape_mask & ESCAPE_BAD_CAST)
 349         fprintf (file, ", bad cast");
 350       if (escape_mask & ESCAPE_TO_RETURN)
 351         fprintf (file, ", returned from func");
 352       if (escape_mask & ESCAPE_TO_PURE_CONST)
 353         fprintf (file, ", passed to pure/const");
 354       if (escape_mask & ESCAPE_IS_GLOBAL)
 355         fprintf (file, ", is global var");
 356       if (escape_mask & ESCAPE_IS_PARM)
 357         fprintf (file, ", is incoming pointer");
 358       if (escape_mask & ESCAPE_UNKNOWN)
 359         fprintf (file, ", unknown escape");
 360       fprintf (file, " )");
 361     }
 362
 363   if (gimple_default_def (cfun, var))
 364     {
 365       fprintf (file, ", default def: ");
 366       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 367     }
 368
 369   if (may_aliases (var))
 370     {
 371       fprintf (file, ", may aliases: ");
 372       dump_may_aliases_for (file, var);
 373     }
 374
 375   if (get_subvars_for_var (var))
 376     {
 377       fprintf (file, ", sub-vars: ");
 378       dump_subvars_for (file, var);
 379     }
 380
 381   if (!is_gimple_reg (var))
 382     {
 383       if (memory_partition (var))
 384         {
 385           fprintf (file, ", belongs to partition: ");
 386           print_generic_expr (file, memory_partition (var), dump_flags);
 387         }
 388
 389       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
 390         {
 391           fprintf (file, ", partition symbols: ");
 392           dump_decl_set (file, MPT_SYMBOLS (var));
 393         }
 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_vdefs * sizeof (tree *);
 463   total += size;
 464   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 465            SCALE (size), LABEL (size));
 466
 467   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 468   total += size;
 469   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 470            SCALE (size), LABEL (size));
 471
 472   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 473   total += size;
 474   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 475            SCALE (size), LABEL (size));
 476
 477   fprintf (file, "---------------------------------------------------------\n");
 478   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 479            LABEL (total));
 480   fprintf (file, "---------------------------------------------------------\n");
 481   fprintf (file, "\n");
 482
 483   if (dfa_stats.num_phis)
 484     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 485              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 486              dfa_stats.max_num_phi_args);
 487
 488   fprintf (file, "\n");
 489 }
 490
 491
 492 /* Dump DFA statistics on stderr.  */
 493
 494 void
 495 debug_dfa_stats (void)
 496 {
 497   dump_dfa_stats (stderr);
 498 }
 499
 500
 501 /* Collect DFA statistics and store them in the structure pointed to by
 502    DFA_STATS_P.  */
 503
 504 static void
 505 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 506 {
 507   struct pointer_set_t *pset;
 508   basic_block bb;
 509   block_stmt_iterator i;
 510
 511   gcc_assert (dfa_stats_p);
 512
 513   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 514
 515   /* Walk all the trees in the function counting references.  Start at
 516      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 517   pset = pointer_set_create ();
 518
 519   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 520        !bsi_end_p (i); bsi_next (&i))
 521     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 522                pset);
 523
 524   pointer_set_destroy (pset);
 525
 526   FOR_EACH_BB (bb)
 527     {
 528       tree phi;
 529       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 530         {
 531           dfa_stats_p->num_phis++;
 532           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 533           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 534             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 535         }
 536     }
 537 }
 538
 539
 540 /* Callback for walk_tree to collect DFA statistics for a tree and its
 541    children.  */
 542
 543 static tree
 544 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 545                      void *data)
 546 {
 547   tree t = *tp;
 548   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 549
 550   if (t->base.ann)
 551     {
 552       switch (ann_type (t->base.ann))
 553         {
 554         case STMT_ANN:
 555           {
 556             dfa_stats_p->num_stmt_anns++;
 557             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 558             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 559             dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (t, SSA_OP_VDEF);
 560             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 561             break;
 562           }
 563
 564         case VAR_ANN:
 565           dfa_stats_p->num_var_anns++;
 566           break;
 567
 568         default:
 569           break;
 570         }
 571     }
 572
 573   return NULL;
 574 }
 575
 576
 577 /*---------------------------------------------------------------------------
 578                              Miscellaneous helpers
 579 ---------------------------------------------------------------------------*/
 580 /* Callback for walk_tree.  Used to collect variables referenced in
 581    the function.  */
 582
 583 static tree
 584 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 585 {
 586   /* If T is a regular variable that the optimizers are interested
 587      in, add it to the list of variables.  */
 588   if (SSA_VAR_P (*tp))
 589     add_referenced_var (*tp);
 590
 591   /* Type, _DECL and constant nodes have no interesting children.
 592      Ignore them.  */
 593   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 594     *walk_subtrees = 0;
 595
 596   return NULL_TREE;
 597 }
 598
 599 /* Lookup UID in the referenced_vars hashtable and return the associated
 600    variable.  */
 601
 602 tree
 603 referenced_var_lookup (unsigned int uid)
 604 {
 605   struct int_tree_map *h, in;
 606   in.uid = uid;
 607   h = (struct int_tree_map *) htab_find_with_hash (gimple_referenced_vars (cfun),
 608                                                    &in, uid);
 609   gcc_assert (h || uid == 0);
 610   if (h)
 611     return h->to;
 612   return NULL_TREE;
 613 }
 614
 615 /* Check if TO is in the referenced_vars hash table and insert it if not.
 616    Return true if it required insertion.  */
 617
 618 bool
 619 referenced_var_check_and_insert (tree to)
 620 {
 621   struct int_tree_map *h, in;
 622   void **loc;
 623   unsigned int uid = DECL_UID (to);
 624
 625   in.uid = uid;
 626   in.to = to;
 627   h = (struct int_tree_map *) htab_find_with_hash (gimple_referenced_vars (cfun),
 628                                                    &in, uid);
 629
 630   if (h)
 631     {
 632       /* DECL_UID has already been entered in the table.  Verify that it is
 633          the same entry as TO.  See PR 27793.  */
 634       gcc_assert (h->to == to);
 635       return false;
 636     }
 637
 638   h = GGC_NEW (struct int_tree_map);
 639   h->uid = uid;
 640   h->to = to;
 641   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 642                                   h, uid, INSERT);
 643   *(struct int_tree_map **)  loc = h;
 644   return true;
 645 }
 646
 647 /* Lookup VAR UID in the default_defs hashtable and return the associated
 648    variable.  */
 649
 650 tree
 651 gimple_default_def (struct function *fn, tree var)
 652 {
 653   struct int_tree_map *h, in;
 654   gcc_assert (SSA_VAR_P (var));
 655   in.uid = DECL_UID (var);
 656   h = (struct int_tree_map *) htab_find_with_hash (DEFAULT_DEFS (fn),
 657                                                    &in,
 658                                                    DECL_UID (var));
 659   if (h)
 660     return h->to;
 661   return NULL_TREE;
 662 }
 663
 664 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 665
 666 void
 667 set_default_def (tree var, tree def)
 668 {
 669   struct int_tree_map in;
 670   struct int_tree_map *h;
 671   void **loc;
 672
 673   gcc_assert (SSA_VAR_P (var));
 674   in.uid = DECL_UID (var);
 675   if (!def && gimple_default_def (cfun, var))
 676     {
 677       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 678             DECL_UID (var), INSERT);
 679       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 680       return;
 681     }
 682   gcc_assert (TREE_CODE (def) == SSA_NAME);
 683   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 684                                   DECL_UID (var), INSERT);
 685
 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       SSA_NAME_IS_DEFAULT_DEF (h->to) = false;
 698       h->to = def;
 699     }
 700
 701    /* Mark DEF as the default definition for VAR.  */
 702    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 703 }
 704
 705 /* Add VAR to the list of referenced variables if it isn't already there.  */
 706
 707 void
 708 add_referenced_var (tree var)
 709 {
 710   var_ann_t v_ann;
 711
 712   v_ann = get_var_ann (var);
 713   gcc_assert (DECL_P (var));
 714
 715   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 716   if (referenced_var_check_and_insert (var))
 717     {
 718       /* This is the first time we found this variable, annotate it with
 719          attributes that are intrinsic to the variable.  */
 720
 721       /* Tag's don't have DECL_INITIAL.  */
 722       if (MTAG_P (var))
 723         return;
 724
 725       /* Scan DECL_INITIAL for pointer variables as they may contain
 726          address arithmetic referencing the address of other
 727          variables.  */
 728       if (DECL_INITIAL (var)
 729           /* Initializers of external variables are not useful to the
 730              optimizers.  */
 731           && !DECL_EXTERNAL (var)
 732           /* It's not necessary to walk the initial value of non-constant
 733              variables because it cannot be propagated by the
 734              optimizers.  */
 735           && (TREE_CONSTANT (var) || TREE_READONLY (var)))
 736         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 737     }
 738 }
 739
 740
 741 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 742
 743 tree
 744 get_virtual_var (tree var)
 745 {
 746   STRIP_NOPS (var);
 747
 748   if (TREE_CODE (var) == SSA_NAME)
 749     var = SSA_NAME_VAR (var);
 750
 751   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 752          || handled_component_p (var))
 753     var = TREE_OPERAND (var, 0);
 754
 755   /* Treating GIMPLE registers as virtual variables makes no sense.
 756      Also complain if we couldn't extract a _DECL out of the original
 757      expression.  */
 758   gcc_assert (SSA_VAR_P (var));
 759   gcc_assert (!is_gimple_reg (var));
 760
 761   return var;
 762 }
 763
 764 /* Mark all the naked symbols in STMT for SSA renaming.
 765
 766    NOTE: This function should only be used for brand new statements.
 767    If the caller is modifying an existing statement, it should use the
 768    combination push_stmt_changes/pop_stmt_changes.  */
 769
 770 void
 771 mark_symbols_for_renaming (tree stmt)
 772 {
 773   tree op;
 774   ssa_op_iter iter;
 775
 776   update_stmt (stmt);
 777
 778   /* Mark all the operands for renaming.  */
 779   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 780     if (DECL_P (op))
 781       mark_sym_for_renaming (op);
 782 }
 783
 784
 785 /* Find all variables within the gimplified statement that were not previously
 786    visible to the function and add them to the referenced variables list.  */
 787
 788 static tree
 789 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 790                             void *data ATTRIBUTE_UNUSED)
 791 {
 792   tree t = *tp;
 793
 794   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 795     {
 796       add_referenced_var (t);
 797       mark_sym_for_renaming (t);
 798     }
 799
 800   if (IS_TYPE_OR_DECL_P (t))
 801     *walk_subtrees = 0;
 802
 803   return NULL;
 804 }
 805
 806 void
 807 find_new_referenced_vars (tree *stmt_p)
 808 {
 809   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 810 }
 811
 812
 813 /* If EXP is a handled component reference for a structure, return the
 814    base variable.  The access range is delimited by bit positions *POFFSET and
 815    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 816    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 817    and *PMAX_SIZE are equal, the access is non-variable.  */
 818
 819 tree
 820 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 821                          HOST_WIDE_INT *psize,
 822                          HOST_WIDE_INT *pmax_size)
 823 {
 824   HOST_WIDE_INT bitsize = -1;
 825   HOST_WIDE_INT maxsize = -1;
 826   tree size_tree = NULL_TREE;
 827   tree bit_offset = bitsize_zero_node;
 828   bool seen_variable_array_ref = false;
 829
 830   gcc_assert (!SSA_VAR_P (exp));
 831
 832   /* First get the final access size from just the outermost expression.  */
 833   if (TREE_CODE (exp) == COMPONENT_REF)
 834     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 835   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 836     size_tree = TREE_OPERAND (exp, 1);
 837   else
 838     {
 839       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 840       if (mode == BLKmode)
 841         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 842       else
 843         bitsize = GET_MODE_BITSIZE (mode);
 844     }
 845   if (size_tree != NULL_TREE)
 846     {
 847       if (! host_integerp (size_tree, 1))
 848         bitsize = -1;
 849       else
 850         bitsize = TREE_INT_CST_LOW (size_tree);
 851     }
 852
 853   /* Initially, maxsize is the same as the accessed element size.
 854      In the following it will only grow (or become -1).  */
 855   maxsize = bitsize;
 856
 857   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 858      and find the ultimate containing object.  */
 859   while (1)
 860     {
 861       switch (TREE_CODE (exp))
 862         {
 863         case BIT_FIELD_REF:
 864           bit_offset = size_binop (PLUS_EXPR, bit_offset,
 865                                    TREE_OPERAND (exp, 2));
 866           break;
 867
 868         case COMPONENT_REF:
 869           {
 870             tree field = TREE_OPERAND (exp, 1);
 871             tree this_offset = component_ref_field_offset (exp);
 872
 873             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 874               {
 875                 this_offset = size_binop (MULT_EXPR,
 876                                           fold_convert (bitsizetype,
 877                                                         this_offset),
 878                                           bitsize_unit_node);
 879                 bit_offset = size_binop (PLUS_EXPR,
 880                                          bit_offset, this_offset);
 881                 bit_offset = size_binop (PLUS_EXPR, bit_offset,
 882                                          DECL_FIELD_BIT_OFFSET (field));
 883               }
 884             else
 885               {
 886                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 887                 /* We need to adjust maxsize to the whole structure bitsize.
 888                    But we can subtract any constant offset seen sofar,
 889                    because that would get us out of the structure otherwise.  */
 890                 if (maxsize != -1
 891                     && csize && host_integerp (csize, 1))
 892                   {
 893                     maxsize = (TREE_INT_CST_LOW (csize)
 894                                - TREE_INT_CST_LOW (bit_offset));
 895                   }
 896                 else
 897                   maxsize = -1;
 898               }
 899           }
 900           break;
 901
 902         case ARRAY_REF:
 903         case ARRAY_RANGE_REF:
 904           {
 905             tree index = TREE_OPERAND (exp, 1);
 906             tree low_bound = array_ref_low_bound (exp);
 907             tree unit_size = array_ref_element_size (exp);
 908
 909             if (! integer_zerop (low_bound))
 910               index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
 911                                    index, low_bound);
 912             index = size_binop (MULT_EXPR,
 913                                 fold_convert (sizetype, index), unit_size);
 914             if (TREE_CODE (index) == INTEGER_CST)
 915               {
 916                 index = size_binop (MULT_EXPR,
 917                                     fold_convert (bitsizetype, index),
 918                                     bitsize_unit_node);
 919                 bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
 920
 921                 /* An array ref with a constant index up in the structure
 922                    hierarchy will constrain the size of any variable array ref
 923                    lower in the access hierarchy.  */
 924                 seen_variable_array_ref = false;
 925               }
 926             else
 927               {
 928                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 929                 /* We need to adjust maxsize to the whole array bitsize.
 930                    But we can subtract any constant offset seen sofar,
 931                    because that would get us outside of the array otherwise.  */
 932                 if (maxsize != -1
 933                     && asize && host_integerp (asize, 1))
 934                   {
 935                     maxsize = (TREE_INT_CST_LOW (asize)
 936                                - TREE_INT_CST_LOW (bit_offset));
 937                   }
 938                 else
 939                   maxsize = -1;
 940
 941                 /* Remember that we have seen an array ref with a variable
 942                    index.  */
 943                 seen_variable_array_ref = true;
 944               }
 945           }
 946           break;
 947
 948         case REALPART_EXPR:
 949           break;
 950
 951         case IMAGPART_EXPR:
 952           bit_offset = size_binop (PLUS_EXPR, bit_offset,
 953                                    bitsize_int (bitsize));
 954           break;
 955
 956         case VIEW_CONVERT_EXPR:
 957           /* ???  We probably should give up here and bail out.  */
 958           break;
 959
 960         default:
 961           goto done;
 962         }
 963
 964       exp = TREE_OPERAND (exp, 0);
 965     }
 966  done:
 967
 968   /* We need to deal with variable arrays ending structures such as
 969        struct { int length; int a[1]; } x;           x.a[d]
 970        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 971        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 972      where we do not know maxsize for variable index accesses to
 973      the array.  The simplest way to conservatively deal with this
 974      is to punt in the case that offset + maxsize reaches the
 975      base type boundary.  */
 976   if (seen_variable_array_ref
 977       && maxsize != -1
 978       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 979       && TREE_INT_CST_LOW (bit_offset) + maxsize
 980          == TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
 981     maxsize = -1;
 982
 983   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 984      negative bit_offset here.  We might want to store a zero offset
 985      in this case.  */
 986   *poffset = TREE_INT_CST_LOW (bit_offset);
 987   *psize = bitsize;
 988   *pmax_size = maxsize;
 989
 990   return exp;
 991 }