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 /* Remove VAR from the list.  */
 756
 757 void
 758 remove_referenced_var (tree var)
 759 {
 760   var_ann_t v_ann;
 761   struct int_tree_map in;
 762   void **loc;
 763   unsigned int uid = DECL_UID (var);
 764
 765   clear_call_clobbered (var);
 766   v_ann = get_var_ann (var);
 767   ggc_free (v_ann);
 768   var->base.ann = NULL;
 769   gcc_assert (DECL_P (var));
 770   in.uid = uid;
 771   in.to = var;
 772   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 773                                   NO_INSERT);
 774   ggc_free (*loc);
 775   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 776 }
 777
 778
 779 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 780
 781 tree
 782 get_virtual_var (tree var)
 783 {
 784   STRIP_NOPS (var);
 785
 786   if (TREE_CODE (var) == SSA_NAME)
 787     var = SSA_NAME_VAR (var);
 788
 789   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 790          || handled_component_p (var))
 791     var = TREE_OPERAND (var, 0);
 792
 793   /* Treating GIMPLE registers as virtual variables makes no sense.
 794      Also complain if we couldn't extract a _DECL out of the original
 795      expression.  */
 796   gcc_assert (SSA_VAR_P (var));
 797   gcc_assert (!is_gimple_reg (var));
 798
 799   return var;
 800 }
 801
 802 /* Mark all the naked symbols in STMT for SSA renaming.
 803
 804    NOTE: This function should only be used for brand new statements.
 805    If the caller is modifying an existing statement, it should use the
 806    combination push_stmt_changes/pop_stmt_changes.  */
 807
 808 void
 809 mark_symbols_for_renaming (tree stmt)
 810 {
 811   tree op;
 812   ssa_op_iter iter;
 813
 814   update_stmt (stmt);
 815
 816   /* Mark all the operands for renaming.  */
 817   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 818     if (DECL_P (op))
 819       mark_sym_for_renaming (op);
 820 }
 821
 822
 823 /* Find all variables within the gimplified statement that were not previously
 824    visible to the function and add them to the referenced variables list.  */
 825
 826 static tree
 827 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 828                             void *data ATTRIBUTE_UNUSED)
 829 {
 830   tree t = *tp;
 831
 832   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 833     {
 834       add_referenced_var (t);
 835       mark_sym_for_renaming (t);
 836     }
 837
 838   if (IS_TYPE_OR_DECL_P (t))
 839     *walk_subtrees = 0;
 840
 841   return NULL;
 842 }
 843
 844 void
 845 find_new_referenced_vars (tree *stmt_p)
 846 {
 847   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 848 }
 849
 850
 851 /* If EXP is a handled component reference for a structure, return the
 852    base variable.  The access range is delimited by bit positions *POFFSET and
 853    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 854    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 855    and *PMAX_SIZE are equal, the access is non-variable.  */
 856
 857 tree
 858 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 859                          HOST_WIDE_INT *psize,
 860                          HOST_WIDE_INT *pmax_size)
 861 {
 862   HOST_WIDE_INT bitsize = -1;
 863   HOST_WIDE_INT maxsize = -1;
 864   tree size_tree = NULL_TREE;
 865   tree bit_offset = bitsize_zero_node;
 866   bool seen_variable_array_ref = false;
 867
 868   gcc_assert (!SSA_VAR_P (exp));
 869
 870   /* First get the final access size from just the outermost expression.  */
 871   if (TREE_CODE (exp) == COMPONENT_REF)
 872     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 873   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 874     size_tree = TREE_OPERAND (exp, 1);
 875   else
 876     {
 877       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 878       if (mode == BLKmode)
 879         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 880       else
 881         bitsize = GET_MODE_BITSIZE (mode);
 882     }
 883   if (size_tree != NULL_TREE)
 884     {
 885       if (! host_integerp (size_tree, 1))
 886         bitsize = -1;
 887       else
 888         bitsize = TREE_INT_CST_LOW (size_tree);
 889     }
 890
 891   /* Initially, maxsize is the same as the accessed element size.
 892      In the following it will only grow (or become -1).  */
 893   maxsize = bitsize;
 894
 895   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 896      and find the ultimate containing object.  */
 897   while (1)
 898     {
 899       switch (TREE_CODE (exp))
 900         {
 901         case BIT_FIELD_REF:
 902           bit_offset = size_binop (PLUS_EXPR, bit_offset,
 903                                    TREE_OPERAND (exp, 2));
 904           break;
 905
 906         case COMPONENT_REF:
 907           {
 908             tree field = TREE_OPERAND (exp, 1);
 909             tree this_offset = component_ref_field_offset (exp);
 910
 911             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 912               {
 913                 this_offset = size_binop (MULT_EXPR,
 914                                           fold_convert (bitsizetype,
 915                                                         this_offset),
 916                                           bitsize_unit_node);
 917                 bit_offset = size_binop (PLUS_EXPR,
 918                                          bit_offset, this_offset);
 919                 bit_offset = size_binop (PLUS_EXPR, bit_offset,
 920                                          DECL_FIELD_BIT_OFFSET (field));
 921               }
 922             else
 923               {
 924                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 925                 /* We need to adjust maxsize to the whole structure bitsize.
 926                    But we can subtract any constant offset seen sofar,
 927                    because that would get us out of the structure otherwise.  */
 928                 if (maxsize != -1
 929                     && csize && host_integerp (csize, 1))
 930                   {
 931                     maxsize = (TREE_INT_CST_LOW (csize)
 932                                - TREE_INT_CST_LOW (bit_offset));
 933                   }
 934                 else
 935                   maxsize = -1;
 936               }
 937           }
 938           break;
 939
 940         case ARRAY_REF:
 941         case ARRAY_RANGE_REF:
 942           {
 943             tree index = TREE_OPERAND (exp, 1);
 944             tree low_bound = array_ref_low_bound (exp);
 945             tree unit_size = array_ref_element_size (exp);
 946
 947             if (! integer_zerop (low_bound))
 948               index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
 949                                    index, low_bound);
 950             index = size_binop (MULT_EXPR,
 951                                 fold_convert (sizetype, index), unit_size);
 952             if (TREE_CODE (index) == INTEGER_CST)
 953               {
 954                 index = size_binop (MULT_EXPR,
 955                                     fold_convert (bitsizetype, index),
 956                                     bitsize_unit_node);
 957                 bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
 958
 959                 /* An array ref with a constant index up in the structure
 960                    hierarchy will constrain the size of any variable array ref
 961                    lower in the access hierarchy.  */
 962                 seen_variable_array_ref = false;
 963               }
 964             else
 965               {
 966                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 967                 /* We need to adjust maxsize to the whole array bitsize.
 968                    But we can subtract any constant offset seen sofar,
 969                    because that would get us outside of the array otherwise.  */
 970                 if (maxsize != -1
 971                     && asize && host_integerp (asize, 1))
 972                   {
 973                     maxsize = (TREE_INT_CST_LOW (asize)
 974                                - TREE_INT_CST_LOW (bit_offset));
 975                   }
 976                 else
 977                   maxsize = -1;
 978
 979                 /* Remember that we have seen an array ref with a variable
 980                    index.  */
 981                 seen_variable_array_ref = true;
 982               }
 983           }
 984           break;
 985
 986         case REALPART_EXPR:
 987           break;
 988
 989         case IMAGPART_EXPR:
 990           bit_offset = size_binop (PLUS_EXPR, bit_offset,
 991                                    bitsize_int (bitsize));
 992           break;
 993
 994         case VIEW_CONVERT_EXPR:
 995           /* ???  We probably should give up here and bail out.  */
 996           break;
 997
 998         default:
 999           goto done;
1000         }
1001
1002       exp = TREE_OPERAND (exp, 0);
1003     }
1004  done:
1005
1006   /* We need to deal with variable arrays ending structures such as
1007        struct { int length; int a[1]; } x;           x.a[d]
1008        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
1009        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
1010      where we do not know maxsize for variable index accesses to
1011      the array.  The simplest way to conservatively deal with this
1012      is to punt in the case that offset + maxsize reaches the
1013      base type boundary.  */
1014   if (seen_variable_array_ref
1015       && maxsize != -1
1016       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
1017       && TREE_INT_CST_LOW (bit_offset) + maxsize
1018          == TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
1019     maxsize = -1;
1020
1021   /* ???  Due to negative offsets in ARRAY_REF we can end up with
1022      negative bit_offset here.  We might want to store a zero offset
1023      in this case.  */
1024   *poffset = TREE_INT_CST_LOW (bit_offset);
1025   *psize = bitsize;
1026   *pmax_size = maxsize;
1027
1028   return exp;
1029 }