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   struct static_var_ann_d *sann = NULL;
 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   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 134     {
 135       sann = GGC_CNEW (struct static_var_ann_d);
 136       ann = &sann->ann;
 137     }
 138   else
 139     ann = GGC_CNEW (struct var_ann_d);
 140
 141   ann->common.type = VAR_ANN;
 142
 143   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 144     {
 145        void **slot;
 146        sann->uid = DECL_UID (t);
 147        slot = htab_find_slot_with_hash (gimple_var_anns (cfun),
 148                                         t, DECL_UID (t), INSERT);
 149        gcc_assert (!*slot);
 150        *slot = sann;
 151     }
 152   else
 153     t->base.ann = (tree_ann_t) ann;
 154
 155   return ann;
 156 }
 157
 158 /* Create a new annotation for a FUNCTION_DECL node T.  */
 159
 160 function_ann_t
 161 create_function_ann (tree t)
 162 {
 163   function_ann_t ann;
 164
 165   gcc_assert (t);
 166   gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
 167   gcc_assert (!t->base.ann || t->base.ann->common.type == FUNCTION_ANN);
 168
 169   ann = ggc_alloc (sizeof (*ann));
 170   memset ((void *) ann, 0, sizeof (*ann));
 171
 172   ann->common.type = FUNCTION_ANN;
 173
 174   t->base.ann = (tree_ann_t) ann;
 175
 176   return ann;
 177 }
 178
 179 /* Create a new annotation for a statement node T.  */
 180
 181 stmt_ann_t
 182 create_stmt_ann (tree t)
 183 {
 184   stmt_ann_t ann;
 185
 186   gcc_assert (is_gimple_stmt (t));
 187   gcc_assert (!t->base.ann || t->base.ann->common.type == STMT_ANN);
 188
 189   ann = GGC_CNEW (struct stmt_ann_d);
 190
 191   ann->common.type = STMT_ANN;
 192
 193   /* Since we just created the annotation, mark the statement modified.  */
 194   ann->modified = true;
 195
 196   t->base.ann = (tree_ann_t) ann;
 197
 198   return ann;
 199 }
 200
 201 /* Create a new annotation for a tree T.  */
 202
 203 tree_ann_common_t
 204 create_tree_common_ann (tree t)
 205 {
 206   tree_ann_common_t ann;
 207
 208   gcc_assert (t);
 209   gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
 210
 211   ann = GGC_CNEW (struct tree_ann_common_d);
 212
 213   ann->type = TREE_ANN_COMMON;
 214   t->base.ann = (tree_ann_t) ann;
 215
 216   return ann;
 217 }
 218
 219 /* Build a temporary.  Make sure and register it to be renamed.  */
 220
 221 tree
 222 make_rename_temp (tree type, const char *prefix)
 223 {
 224   tree t = create_tmp_var (type, prefix);
 225
 226   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 227       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 228     DECL_GIMPLE_REG_P (t) = 1;
 229
 230   if (gimple_referenced_vars (cfun))
 231     {
 232       add_referenced_var (t);
 233       mark_sym_for_renaming (t);
 234     }
 235
 236   return t;
 237 }
 238
 239
 240
 241 /*---------------------------------------------------------------------------
 242                               Debugging functions
 243 ---------------------------------------------------------------------------*/
 244 /* Dump the list of all the referenced variables in the current function to
 245    FILE.  */
 246
 247 void
 248 dump_referenced_vars (FILE *file)
 249 {
 250   tree var;
 251   referenced_var_iterator rvi;
 252
 253   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 254            get_name (current_function_decl), (unsigned) num_referenced_vars);
 255
 256   FOR_EACH_REFERENCED_VAR (var, rvi)
 257     {
 258       fprintf (file, "Variable: ");
 259       dump_variable (file, var);
 260       fprintf (file, "\n");
 261     }
 262 }
 263
 264
 265 /* Dump the list of all the referenced variables to stderr.  */
 266
 267 void
 268 debug_referenced_vars (void)
 269 {
 270   dump_referenced_vars (stderr);
 271 }
 272
 273
 274 /* Dump sub-variables for VAR to FILE.  */
 275
 276 void
 277 dump_subvars_for (FILE *file, tree var)
 278 {
 279   subvar_t sv = get_subvars_for_var (var);
 280
 281   if (!sv)
 282     return;
 283
 284   fprintf (file, "{ ");
 285
 286   for (; sv; sv = sv->next)
 287     {
 288       print_generic_expr (file, sv->var, dump_flags);
 289       fprintf (file, " ");
 290     }
 291
 292   fprintf (file, "}");
 293 }
 294
 295
 296 /* Dumb sub-variables for VAR to stderr.  */
 297
 298 void
 299 debug_subvars_for (tree var)
 300 {
 301   dump_subvars_for (stderr, var);
 302 }
 303
 304
 305 /* Dump variable VAR and its may-aliases to FILE.  */
 306
 307 void
 308 dump_variable (FILE *file, tree var)
 309 {
 310   var_ann_t ann;
 311
 312   if (TREE_CODE (var) == SSA_NAME)
 313     {
 314       if (POINTER_TYPE_P (TREE_TYPE (var)))
 315         dump_points_to_info_for (file, var);
 316       var = SSA_NAME_VAR (var);
 317     }
 318
 319   if (var == NULL_TREE)
 320     {
 321       fprintf (file, "<nil>");
 322       return;
 323     }
 324
 325   print_generic_expr (file, var, dump_flags);
 326
 327   ann = var_ann (var);
 328
 329   fprintf (file, ", UID %u", (unsigned) DECL_UID (var));
 330
 331   fprintf (file, ", ");
 332   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 333
 334   if (ann && ann->symbol_mem_tag)
 335     {
 336       fprintf (file, ", symbol memory tag: ");
 337       print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
 338     }
 339
 340   if (TREE_ADDRESSABLE (var))
 341     fprintf (file, ", is addressable");
 342
 343   if (is_global_var (var))
 344     fprintf (file, ", is global");
 345
 346   if (TREE_THIS_VOLATILE (var))
 347     fprintf (file, ", is volatile");
 348
 349   if (is_call_clobbered (var))
 350     {
 351       var_ann_t va = var_ann (var);
 352       unsigned int escape_mask = va->escape_mask;
 353
 354       fprintf (file, ", call clobbered");
 355       fprintf (file, " (");
 356       if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
 357         fprintf (file, ", stored in global");
 358       if (escape_mask & ESCAPE_TO_ASM)
 359         fprintf (file, ", goes through ASM");
 360       if (escape_mask & ESCAPE_TO_CALL)
 361         fprintf (file, ", passed to call");
 362       if (escape_mask & ESCAPE_BAD_CAST)
 363         fprintf (file, ", bad cast");
 364       if (escape_mask & ESCAPE_TO_RETURN)
 365         fprintf (file, ", returned from func");
 366       if (escape_mask & ESCAPE_TO_PURE_CONST)
 367         fprintf (file, ", passed to pure/const");
 368       if (escape_mask & ESCAPE_IS_GLOBAL)
 369         fprintf (file, ", is global var");
 370       if (escape_mask & ESCAPE_IS_PARM)
 371         fprintf (file, ", is incoming pointer");
 372       if (escape_mask & ESCAPE_UNKNOWN)
 373         fprintf (file, ", unknown escape");
 374       fprintf (file, " )");
 375     }
 376
 377   if (gimple_default_def (cfun, var))
 378     {
 379       fprintf (file, ", default def: ");
 380       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 381     }
 382
 383   if (MTAG_P (var) && may_aliases (var))
 384     {
 385       fprintf (file, ", may aliases: ");
 386       dump_may_aliases_for (file, var);
 387     }
 388
 389   if (get_subvars_for_var (var))
 390     {
 391       fprintf (file, ", sub-vars: ");
 392       dump_subvars_for (file, var);
 393     }
 394
 395   if (!is_gimple_reg (var))
 396     {
 397       if (memory_partition (var))
 398         {
 399           fprintf (file, ", belongs to partition: ");
 400           print_generic_expr (file, memory_partition (var), dump_flags);
 401         }
 402
 403       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
 404         {
 405           fprintf (file, ", partition symbols: ");
 406           dump_decl_set (file, MPT_SYMBOLS (var));
 407         }
 408     }
 409
 410   fprintf (file, "\n");
 411 }
 412
 413
 414 /* Dump variable VAR and its may-aliases to stderr.  */
 415
 416 void
 417 debug_variable (tree var)
 418 {
 419   dump_variable (stderr, var);
 420 }
 421
 422
 423 /* Dump various DFA statistics to FILE.  */
 424
 425 void
 426 dump_dfa_stats (FILE *file)
 427 {
 428   struct dfa_stats_d dfa_stats;
 429
 430   unsigned long size, total = 0;
 431   const char * const fmt_str   = "%-30s%-13s%12s\n";
 432   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 433   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 434   const char *funcname
 435     = lang_hooks.decl_printable_name (current_function_decl, 2);
 436
 437   collect_dfa_stats (&dfa_stats);
 438
 439   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 440
 441   fprintf (file, "---------------------------------------------------------\n");
 442   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 443   fprintf (file, fmt_str, "", "  instances  ", "used ");
 444   fprintf (file, "---------------------------------------------------------\n");
 445
 446   size = num_referenced_vars * sizeof (tree);
 447   total += size;
 448   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 449            SCALE (size), LABEL (size));
 450
 451   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 452   total += size;
 453   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 454            SCALE (size), LABEL (size));
 455
 456   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 457   total += size;
 458   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 459            SCALE (size), LABEL (size));
 460
 461   size = dfa_stats.num_uses * sizeof (tree *);
 462   total += size;
 463   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 464            SCALE (size), LABEL (size));
 465
 466   size = dfa_stats.num_defs * sizeof (tree *);
 467   total += size;
 468   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 469            SCALE (size), LABEL (size));
 470
 471   size = dfa_stats.num_vuses * sizeof (tree *);
 472   total += size;
 473   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 474            SCALE (size), LABEL (size));
 475
 476   size = dfa_stats.num_vdefs * sizeof (tree *);
 477   total += size;
 478   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 479            SCALE (size), LABEL (size));
 480
 481   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 482   total += size;
 483   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 484            SCALE (size), LABEL (size));
 485
 486   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 487   total += size;
 488   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 489            SCALE (size), LABEL (size));
 490
 491   fprintf (file, "---------------------------------------------------------\n");
 492   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 493            LABEL (total));
 494   fprintf (file, "---------------------------------------------------------\n");
 495   fprintf (file, "\n");
 496
 497   if (dfa_stats.num_phis)
 498     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 499              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 500              dfa_stats.max_num_phi_args);
 501
 502   fprintf (file, "\n");
 503 }
 504
 505
 506 /* Dump DFA statistics on stderr.  */
 507
 508 void
 509 debug_dfa_stats (void)
 510 {
 511   dump_dfa_stats (stderr);
 512 }
 513
 514
 515 /* Collect DFA statistics and store them in the structure pointed to by
 516    DFA_STATS_P.  */
 517
 518 static void
 519 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 520 {
 521   struct pointer_set_t *pset;
 522   basic_block bb;
 523   block_stmt_iterator i;
 524
 525   gcc_assert (dfa_stats_p);
 526
 527   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 528
 529   /* Walk all the trees in the function counting references.  Start at
 530      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 531   pset = pointer_set_create ();
 532
 533   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 534        !bsi_end_p (i); bsi_next (&i))
 535     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 536                pset);
 537
 538   pointer_set_destroy (pset);
 539
 540   FOR_EACH_BB (bb)
 541     {
 542       tree phi;
 543       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 544         {
 545           dfa_stats_p->num_phis++;
 546           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 547           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 548             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 549         }
 550     }
 551 }
 552
 553
 554 /* Callback for walk_tree to collect DFA statistics for a tree and its
 555    children.  */
 556
 557 static tree
 558 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 559                      void *data)
 560 {
 561   tree t = *tp;
 562   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 563
 564   if (t->base.ann)
 565     {
 566       switch (ann_type (t->base.ann))
 567         {
 568         case STMT_ANN:
 569           {
 570             dfa_stats_p->num_stmt_anns++;
 571             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 572             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 573             dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (t, SSA_OP_VDEF);
 574             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 575             break;
 576           }
 577
 578         case VAR_ANN:
 579           dfa_stats_p->num_var_anns++;
 580           break;
 581
 582         default:
 583           break;
 584         }
 585     }
 586
 587   return NULL;
 588 }
 589
 590
 591 /*---------------------------------------------------------------------------
 592                              Miscellaneous helpers
 593 ---------------------------------------------------------------------------*/
 594 /* Callback for walk_tree.  Used to collect variables referenced in
 595    the function.  */
 596
 597 static tree
 598 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 599 {
 600   /* If T is a regular variable that the optimizers are interested
 601      in, add it to the list of variables.  */
 602   if (SSA_VAR_P (*tp))
 603     add_referenced_var (*tp);
 604
 605   /* Type, _DECL and constant nodes have no interesting children.
 606      Ignore them.  */
 607   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 608     *walk_subtrees = 0;
 609
 610   return NULL_TREE;
 611 }
 612
 613 /* Lookup UID in the referenced_vars hashtable and return the associated
 614    variable.  */
 615
 616 tree
 617 referenced_var_lookup (unsigned int uid)
 618 {
 619   struct int_tree_map *h, in;
 620   in.uid = uid;
 621   h = (struct int_tree_map *) htab_find_with_hash (gimple_referenced_vars (cfun),
 622                                                    &in, uid);
 623   gcc_assert (h || uid == 0);
 624   if (h)
 625     return h->to;
 626   return NULL_TREE;
 627 }
 628
 629 /* Check if TO is in the referenced_vars hash table and insert it if not.
 630    Return true if it required insertion.  */
 631
 632 bool
 633 referenced_var_check_and_insert (tree to)
 634 {
 635   struct int_tree_map *h, in;
 636   void **loc;
 637   unsigned int uid = DECL_UID (to);
 638
 639   in.uid = uid;
 640   in.to = to;
 641   h = (struct int_tree_map *) htab_find_with_hash (gimple_referenced_vars (cfun),
 642                                                    &in, uid);
 643
 644   if (h)
 645     {
 646       /* DECL_UID has already been entered in the table.  Verify that it is
 647          the same entry as TO.  See PR 27793.  */
 648       gcc_assert (h->to == to);
 649       return false;
 650     }
 651
 652   h = GGC_NEW (struct int_tree_map);
 653   h->uid = uid;
 654   h->to = to;
 655   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 656                                   h, uid, INSERT);
 657   *(struct int_tree_map **)  loc = h;
 658   return true;
 659 }
 660
 661 /* Lookup VAR UID in the default_defs hashtable and return the associated
 662    variable.  */
 663
 664 tree
 665 gimple_default_def (struct function *fn, tree var)
 666 {
 667   struct int_tree_map *h, in;
 668   gcc_assert (SSA_VAR_P (var));
 669   in.uid = DECL_UID (var);
 670   h = (struct int_tree_map *) htab_find_with_hash (DEFAULT_DEFS (fn),
 671                                                    &in,
 672                                                    DECL_UID (var));
 673   if (h)
 674     return h->to;
 675   return NULL_TREE;
 676 }
 677
 678 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 679
 680 void
 681 set_default_def (tree var, tree def)
 682 {
 683   struct int_tree_map in;
 684   struct int_tree_map *h;
 685   void **loc;
 686
 687   gcc_assert (SSA_VAR_P (var));
 688   in.uid = DECL_UID (var);
 689   if (!def && gimple_default_def (cfun, var))
 690     {
 691       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 692             DECL_UID (var), INSERT);
 693       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 694       return;
 695     }
 696   gcc_assert (!def || TREE_CODE (def) == SSA_NAME);
 697   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 698                                   DECL_UID (var), INSERT);
 699
 700   /* Default definition might be changed by tail call optimization.  */
 701   if (!*loc)
 702     {
 703       h = GGC_NEW (struct int_tree_map);
 704       h->uid = DECL_UID (var);
 705       h->to = def;
 706       *(struct int_tree_map **)  loc = h;
 707     }
 708    else
 709     {
 710       h = (struct int_tree_map *) *loc;
 711       SSA_NAME_IS_DEFAULT_DEF (h->to) = false;
 712       h->to = def;
 713     }
 714
 715    /* Mark DEF as the default definition for VAR.  */
 716    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 717 }
 718
 719 /* Add VAR to the list of referenced variables if it isn't already there.  */
 720
 721 void
 722 add_referenced_var (tree var)
 723 {
 724   var_ann_t v_ann;
 725
 726   v_ann = get_var_ann (var);
 727   gcc_assert (DECL_P (var));
 728
 729   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 730   if (referenced_var_check_and_insert (var))
 731     {
 732       /* This is the first time we found this variable, annotate it with
 733          attributes that are intrinsic to the variable.  */
 734
 735       /* Tag's don't have DECL_INITIAL.  */
 736       if (MTAG_P (var))
 737         return;
 738
 739       /* Scan DECL_INITIAL for pointer variables as they may contain
 740          address arithmetic referencing the address of other
 741          variables.
 742          Even non-constant intializers need to be walked, because
 743          IPA passes might prove that their are invariant later on.  */
 744       if (DECL_INITIAL (var)
 745           /* Initializers of external variables are not useful to the
 746              optimizers.  */
 747           && !DECL_EXTERNAL (var))
 748         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 749     }
 750 }
 751
 752 /* Remove VAR from the list.  */
 753
 754 void
 755 remove_referenced_var (tree var)
 756 {
 757   var_ann_t v_ann;
 758   struct int_tree_map in;
 759   void **loc;
 760   unsigned int uid = DECL_UID (var);
 761
 762   clear_call_clobbered (var);
 763   v_ann = get_var_ann (var);
 764   ggc_free (v_ann);
 765   var->base.ann = NULL;
 766   gcc_assert (DECL_P (var));
 767   in.uid = uid;
 768   in.to = var;
 769   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 770                                   NO_INSERT);
 771   ggc_free (*loc);
 772   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 773 }
 774
 775
 776 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 777
 778 tree
 779 get_virtual_var (tree var)
 780 {
 781   STRIP_NOPS (var);
 782
 783   if (TREE_CODE (var) == SSA_NAME)
 784     var = SSA_NAME_VAR (var);
 785
 786   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 787          || handled_component_p (var))
 788     var = TREE_OPERAND (var, 0);
 789
 790   /* Treating GIMPLE registers as virtual variables makes no sense.
 791      Also complain if we couldn't extract a _DECL out of the original
 792      expression.  */
 793   gcc_assert (SSA_VAR_P (var));
 794   gcc_assert (!is_gimple_reg (var));
 795
 796   return var;
 797 }
 798
 799 /* Mark all the naked symbols in STMT for SSA renaming.
 800
 801    NOTE: This function should only be used for brand new statements.
 802    If the caller is modifying an existing statement, it should use the
 803    combination push_stmt_changes/pop_stmt_changes.  */
 804
 805 void
 806 mark_symbols_for_renaming (tree stmt)
 807 {
 808   tree op;
 809   ssa_op_iter iter;
 810
 811   update_stmt (stmt);
 812
 813   /* Mark all the operands for renaming.  */
 814   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 815     if (DECL_P (op))
 816       mark_sym_for_renaming (op);
 817 }
 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 EXP 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 }