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