gcc/tree-dfa.c

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