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 /* State information for find_vars_r.  */
  69 struct walk_state
  70 {
  71   /* Hash table used to avoid adding the same variable more than once.  */
  72   htab_t vars_found;
  73 };
  74
  75
  76 /* Local functions.  */
  77 static void collect_dfa_stats (struct dfa_stats_d *);
  78 static tree collect_dfa_stats_r (tree *, int *, void *);
  79 static tree find_vars_r (tree *, int *, void *);
  80 static void add_referenced_var (tree, struct walk_state *);
  81
  82
  83 /* Global declarations.  */
  84
  85 /* Array of all variables referenced in the function.  */
  86 htab_t referenced_vars;
  87
  88 /* Default definition for this symbols.  If set for symbol, it
  89    means that the first reference to this variable in the function is a
  90    USE or a VUSE.  In those cases, the SSA renamer creates an SSA name
  91    for this variable with an empty defining statement.  */
  92 htab_t default_defs;
  93
  94
  95 /*---------------------------------------------------------------------------
  96                         Dataflow analysis (DFA) routines
  97 ---------------------------------------------------------------------------*/
  98 /* Find all the variables referenced in the function.  This function
  99    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
 100
 101    Note that this function does not look for statement operands, it simply
 102    determines what variables are referenced in the program and detects
 103    various attributes for each variable used by alias analysis and the
 104    optimizer.  */
 105
 106 static void
 107 find_referenced_vars (void)
 108 {
 109   htab_t vars_found;
 110   basic_block bb;
 111   block_stmt_iterator si;
 112   struct walk_state walk_state;
 113
 114   vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
 115   memset (&walk_state, 0, sizeof (walk_state));
 116   walk_state.vars_found = vars_found;
 117
 118   FOR_EACH_BB (bb)
 119     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 120       {
 121         tree *stmt_p = bsi_stmt_ptr (si);
 122         walk_tree (stmt_p, find_vars_r, &walk_state, NULL);
 123       }
 124
 125   htab_delete (vars_found);
 126 }
 127
 128 struct tree_opt_pass pass_referenced_vars =
 129 {
 130   NULL,                                 /* name */
 131   NULL,                                 /* gate */
 132   find_referenced_vars,                 /* execute */
 133   NULL,                                 /* sub */
 134   NULL,                                 /* next */
 135   0,                                    /* static_pass_number */
 136   TV_FIND_REFERENCED_VARS,              /* tv_id */
 137   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 138   PROP_referenced_vars,                 /* properties_provided */
 139   0,                                    /* properties_destroyed */
 140   0,                                    /* todo_flags_start */
 141   0,                                    /* todo_flags_finish */
 142   0                                     /* letter */
 143 };
 144
 145
 146 /*---------------------------------------------------------------------------
 147                             Manage annotations
 148 ---------------------------------------------------------------------------*/
 149 /* Create a new annotation for a _DECL node T.  */
 150
 151 var_ann_t
 152 create_var_ann (tree t)
 153 {
 154   var_ann_t ann;
 155
 156   gcc_assert (t);
 157   gcc_assert (DECL_P (t));
 158   gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
 159
 160   ann = GGC_NEW (struct var_ann_d);
 161   memset ((void *) ann, 0, sizeof (*ann));
 162
 163   ann->common.type = VAR_ANN;
 164
 165   t->common.ann = (tree_ann_t) ann;
 166
 167   return ann;
 168 }
 169
 170
 171 /* Create a new annotation for a statement node T.  */
 172
 173 stmt_ann_t
 174 create_stmt_ann (tree t)
 175 {
 176   stmt_ann_t ann;
 177
 178   gcc_assert (is_gimple_stmt (t));
 179   gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN);
 180
 181   ann = GGC_NEW (struct stmt_ann_d);
 182   memset ((void *) ann, 0, sizeof (*ann));
 183
 184   ann->common.type = STMT_ANN;
 185
 186   /* Since we just created the annotation, mark the statement modified.  */
 187   ann->modified = true;
 188
 189   t->common.ann = (tree_ann_t) ann;
 190
 191   return ann;
 192 }
 193
 194 /* Create a new annotation for a tree T.  */
 195
 196 tree_ann_t
 197 create_tree_ann (tree t)
 198 {
 199   tree_ann_t ann;
 200
 201   gcc_assert (t);
 202   gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON);
 203
 204   ann = GGC_NEW (union tree_ann_d);
 205   memset ((void *) ann, 0, sizeof (*ann));
 206
 207   ann->common.type = TREE_ANN_COMMON;
 208   t->common.ann = ann;
 209
 210   return ann;
 211 }
 212
 213 /* Build a temporary.  Make sure and register it to be renamed.  */
 214
 215 tree
 216 make_rename_temp (tree type, const char *prefix)
 217 {
 218   tree t = create_tmp_var (type, prefix);
 219   if (referenced_vars)
 220     {
 221       add_referenced_tmp_var (t);
 222       mark_sym_for_renaming (t);
 223     }
 224
 225   return t;
 226 }
 227
 228
 229
 230 /*---------------------------------------------------------------------------
 231                               Debugging functions
 232 ---------------------------------------------------------------------------*/
 233 /* Dump the list of all the referenced variables in the current function to
 234    FILE.  */
 235
 236 void
 237 dump_referenced_vars (FILE *file)
 238 {
 239   tree var;
 240   referenced_var_iterator rvi;
 241
 242   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 243            get_name (current_function_decl), (unsigned) num_referenced_vars);
 244
 245   FOR_EACH_REFERENCED_VAR (var, rvi)
 246     {
 247       fprintf (file, "Variable: ");
 248       dump_variable (file, var);
 249       fprintf (file, "\n");
 250     }
 251 }
 252
 253
 254 /* Dump the list of all the referenced variables to stderr.  */
 255
 256 void
 257 debug_referenced_vars (void)
 258 {
 259   dump_referenced_vars (stderr);
 260 }
 261
 262
 263 /* Dump sub-variables for VAR to FILE.  */
 264
 265 void
 266 dump_subvars_for (FILE *file, tree var)
 267 {
 268   subvar_t sv = get_subvars_for_var (var);
 269
 270   if (!sv)
 271     return;
 272
 273   fprintf (file, "{ ");
 274
 275   for (; sv; sv = sv->next)
 276     {
 277       print_generic_expr (file, sv->var, dump_flags);
 278       fprintf (file, " ");
 279     }
 280
 281   fprintf (file, "}");
 282 }
 283
 284
 285 /* Dumb sub-variables for VAR to stderr.  */
 286
 287 void
 288 debug_subvars_for (tree var)
 289 {
 290   dump_subvars_for (stderr, var);
 291 }
 292
 293
 294 /* Dump variable VAR and its may-aliases to FILE.  */
 295
 296 void
 297 dump_variable (FILE *file, tree var)
 298 {
 299   var_ann_t ann;
 300
 301   if (TREE_CODE (var) == SSA_NAME)
 302     {
 303       if (POINTER_TYPE_P (TREE_TYPE (var)))
 304         dump_points_to_info_for (file, var);
 305       var = SSA_NAME_VAR (var);
 306     }
 307
 308   if (var == NULL_TREE)
 309     {
 310       fprintf (file, "<nil>");
 311       return;
 312     }
 313
 314   print_generic_expr (file, var, dump_flags);
 315
 316   ann = var_ann (var);
 317
 318   fprintf (file, ", UID %u", (unsigned) DECL_UID (var));
 319
 320   fprintf (file, ", ");
 321   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 322
 323   if (ann && ann->type_mem_tag)
 324     {
 325       fprintf (file, ", type memory tag: ");
 326       print_generic_expr (file, ann->type_mem_tag, dump_flags);
 327     }
 328
 329   if (ann && ann->is_alias_tag)
 330     fprintf (file, ", is an alias tag");
 331
 332   if (TREE_ADDRESSABLE (var))
 333     fprintf (file, ", is addressable");
 334
 335   if (is_global_var (var))
 336     fprintf (file, ", is global");
 337
 338   if (TREE_THIS_VOLATILE (var))
 339     fprintf (file, ", is volatile");
 340
 341   if (is_call_clobbered (var))
 342     fprintf (file, ", call clobbered");
 343
 344   if (default_def (var))
 345     {
 346       fprintf (file, ", default def: ");
 347       print_generic_expr (file, default_def (var), dump_flags);
 348     }
 349
 350   if (may_aliases (var))
 351     {
 352       fprintf (file, ", may aliases: ");
 353       dump_may_aliases_for (file, var);
 354     }
 355
 356   if (get_subvars_for_var (var))
 357     {
 358       fprintf (file, ", sub-vars: ");
 359       dump_subvars_for (file, var);
 360     }
 361
 362   fprintf (file, "\n");
 363 }
 364
 365
 366 /* Dump variable VAR and its may-aliases to stderr.  */
 367
 368 void
 369 debug_variable (tree var)
 370 {
 371   dump_variable (stderr, var);
 372 }
 373
 374
 375 /* Dump various DFA statistics to FILE.  */
 376
 377 void
 378 dump_dfa_stats (FILE *file)
 379 {
 380   struct dfa_stats_d dfa_stats;
 381
 382   unsigned long size, total = 0;
 383   const char * const fmt_str   = "%-30s%-13s%12s\n";
 384   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 385   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 386   const char *funcname
 387     = lang_hooks.decl_printable_name (current_function_decl, 2);
 388
 389   collect_dfa_stats (&dfa_stats);
 390
 391   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 392
 393   fprintf (file, "---------------------------------------------------------\n");
 394   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 395   fprintf (file, fmt_str, "", "  instances  ", "used ");
 396   fprintf (file, "---------------------------------------------------------\n");
 397
 398   size = num_referenced_vars * sizeof (tree);
 399   total += size;
 400   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 401            SCALE (size), LABEL (size));
 402
 403   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 404   total += size;
 405   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 406            SCALE (size), LABEL (size));
 407
 408   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 409   total += size;
 410   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 411            SCALE (size), LABEL (size));
 412
 413   size = dfa_stats.num_uses * sizeof (tree *);
 414   total += size;
 415   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 416            SCALE (size), LABEL (size));
 417
 418   size = dfa_stats.num_defs * sizeof (tree *);
 419   total += size;
 420   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 421            SCALE (size), LABEL (size));
 422
 423   size = dfa_stats.num_vuses * sizeof (tree *);
 424   total += size;
 425   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 426            SCALE (size), LABEL (size));
 427
 428   size = dfa_stats.num_v_may_defs * sizeof (tree *);
 429   total += size;
 430   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
 431            SCALE (size), LABEL (size));
 432
 433   size = dfa_stats.num_v_must_defs * sizeof (tree *);
 434   total += size;
 435   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
 436            SCALE (size), LABEL (size));
 437
 438   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 439   total += size;
 440   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 441            SCALE (size), LABEL (size));
 442
 443   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 444   total += size;
 445   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 446            SCALE (size), LABEL (size));
 447
 448   fprintf (file, "---------------------------------------------------------\n");
 449   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 450            LABEL (total));
 451   fprintf (file, "---------------------------------------------------------\n");
 452   fprintf (file, "\n");
 453
 454   if (dfa_stats.num_phis)
 455     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 456              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 457              dfa_stats.max_num_phi_args);
 458
 459   fprintf (file, "\n");
 460 }
 461
 462
 463 /* Dump DFA statistics on stderr.  */
 464
 465 void
 466 debug_dfa_stats (void)
 467 {
 468   dump_dfa_stats (stderr);
 469 }
 470
 471
 472 /* Collect DFA statistics and store them in the structure pointed to by
 473    DFA_STATS_P.  */
 474
 475 static void
 476 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 477 {
 478   struct pointer_set_t *pset;
 479   basic_block bb;
 480   block_stmt_iterator i;
 481
 482   gcc_assert (dfa_stats_p);
 483
 484   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 485
 486   /* Walk all the trees in the function counting references.  Start at
 487      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 488   pset = pointer_set_create ();
 489
 490   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 491        !bsi_end_p (i); bsi_next (&i))
 492     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 493                pset);
 494
 495   pointer_set_destroy (pset);
 496
 497   FOR_EACH_BB (bb)
 498     {
 499       tree phi;
 500       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 501         {
 502           dfa_stats_p->num_phis++;
 503           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 504           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 505             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 506         }
 507     }
 508 }
 509
 510
 511 /* Callback for walk_tree to collect DFA statistics for a tree and its
 512    children.  */
 513
 514 static tree
 515 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 516                      void *data)
 517 {
 518   tree t = *tp;
 519   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 520
 521   if (t->common.ann)
 522     {
 523       switch (ann_type (t->common.ann))
 524         {
 525         case STMT_ANN:
 526           {
 527             dfa_stats_p->num_stmt_anns++;
 528             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 529             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 530             dfa_stats_p->num_v_may_defs += NUM_SSA_OPERANDS (t, SSA_OP_VMAYDEF);
 531             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 532             dfa_stats_p->num_v_must_defs +=
 533                                   NUM_SSA_OPERANDS (t, SSA_OP_VMUSTDEF);
 534             break;
 535           }
 536
 537         case VAR_ANN:
 538           dfa_stats_p->num_var_anns++;
 539           break;
 540
 541         default:
 542           break;
 543         }
 544     }
 545
 546   return NULL;
 547 }
 548
 549
 550 /*---------------------------------------------------------------------------
 551                              Miscellaneous helpers
 552 ---------------------------------------------------------------------------*/
 553 /* Callback for walk_tree.  Used to collect variables referenced in
 554    the function.  */
 555
 556 static tree
 557 find_vars_r (tree *tp, int *walk_subtrees, void *data)
 558 {
 559   struct walk_state *walk_state = (struct walk_state *) data;
 560
 561   /* If T is a regular variable that the optimizers are interested
 562      in, add it to the list of variables.  */
 563   if (SSA_VAR_P (*tp))
 564     add_referenced_var (*tp, walk_state);
 565
 566   /* Type, _DECL and constant nodes have no interesting children.
 567      Ignore them.  */
 568   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 569     *walk_subtrees = 0;
 570
 571   return NULL_TREE;
 572 }
 573
 574
 575 /* Lookup UID in the referenced_vars hashtable and return the associated
 576    variable or NULL if it is not there.  */
 577
 578 tree
 579 referenced_var_lookup_if_exists (unsigned int uid)
 580 {
 581   struct int_tree_map *h, in;
 582   in.uid = uid;
 583   h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
 584   if (h)
 585     return h->to;
 586   return NULL_TREE;
 587 }
 588
 589 /* Lookup UID in the referenced_vars hashtable and return the associated
 590    variable.  */
 591
 592 tree
 593 referenced_var_lookup (unsigned int uid)
 594 {
 595   struct int_tree_map *h, in;
 596   in.uid = uid;
 597   h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
 598   gcc_assert (h || uid == 0);
 599   if (h)
 600     return h->to;
 601   return NULL_TREE;
 602 }
 603
 604 /* Insert the pair UID, TO into the referenced_vars hashtable.  */
 605
 606 static void
 607 referenced_var_insert (unsigned int uid, tree to)
 608 {
 609   struct int_tree_map *h;
 610   void **loc;
 611
 612   h = GGC_NEW (struct int_tree_map);
 613   h->uid = uid;
 614   h->to = to;
 615   loc = htab_find_slot_with_hash (referenced_vars, h, uid, INSERT);
 616   *(struct int_tree_map **)  loc = h;
 617 }
 618
 619 /* Lookup VAR UID in the default_defs hashtable and return the associated
 620    variable.  */
 621
 622 tree
 623 default_def (tree var)
 624 {
 625   struct int_tree_map *h, in;
 626   gcc_assert (SSA_VAR_P (var));
 627   in.uid = DECL_UID (var);
 628   h = (struct int_tree_map *) htab_find_with_hash (default_defs, &in,
 629                                                    DECL_UID (var));
 630   if (h)
 631     return h->to;
 632   return NULL_TREE;
 633 }
 634
 635 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 636
 637 void
 638 set_default_def (tree var, tree def)
 639 {
 640   struct int_tree_map in;
 641   struct int_tree_map *h;
 642   void **loc;
 643
 644   gcc_assert (SSA_VAR_P (var));
 645   in.uid = DECL_UID (var);
 646   if (!def && default_def (var))
 647     {
 648       loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
 649       htab_remove_elt (default_defs, *loc);
 650       return;
 651     }
 652   gcc_assert (TREE_CODE (def) == SSA_NAME);
 653   loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
 654   /* Default definition might be changed by tail call optimization.  */
 655   if (!*loc)
 656     {
 657       h = GGC_NEW (struct int_tree_map);
 658       h->uid = DECL_UID (var);
 659       h->to = def;
 660       *(struct int_tree_map **)  loc = h;
 661     }
 662    else
 663     {
 664       h = (struct int_tree_map *) *loc;
 665       h->to = def;
 666     }
 667 }
 668
 669 /* Add VAR to the list of dereferenced variables.
 670
 671    WALK_STATE contains a hash table used to avoid adding the same
 672       variable more than once. Note that this function assumes that
 673       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
 674       duplicate checking is done.  */
 675
 676 static void
 677 add_referenced_var (tree var, struct walk_state *walk_state)
 678 {
 679   void **slot;
 680   var_ann_t v_ann;
 681
 682   v_ann = get_var_ann (var);
 683
 684   if (walk_state)
 685     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
 686   else
 687     slot = NULL;
 688
 689   if (slot == NULL || *slot == NULL)
 690     {
 691       /* This is the first time we find this variable, add it to the
 692          REFERENCED_VARS array and annotate it with attributes that are
 693          intrinsic to the variable.  */
 694       if (slot)
 695         *slot = (void *) var;
 696
 697       referenced_var_insert (DECL_UID (var), var);
 698
 699       /* Global variables are always call-clobbered.  */
 700       if (is_global_var (var))
 701         mark_call_clobbered (var);
 702
 703       /* Tag's don't have DECL_INITIAL.  */
 704       if (MTAG_P (var))
 705         return;
 706
 707       /* Scan DECL_INITIAL for pointer variables as they may contain
 708          address arithmetic referencing the address of other
 709          variables.  */
 710       if (DECL_INITIAL (var)
 711           /* Initializers of external variables are not useful to the
 712              optimizers.  */
 713           && !DECL_EXTERNAL (var)
 714           /* It's not necessary to walk the initial value of non-constant
 715              variables because it cannot be propagated by the
 716              optimizers.  */
 717           && (TREE_CONSTANT (var) || TREE_READONLY (var)))
 718         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
 719     }
 720 }
 721
 722
 723 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 724
 725 tree
 726 get_virtual_var (tree var)
 727 {
 728   STRIP_NOPS (var);
 729
 730   if (TREE_CODE (var) == SSA_NAME)
 731     var = SSA_NAME_VAR (var);
 732
 733   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 734          || handled_component_p (var))
 735     var = TREE_OPERAND (var, 0);
 736
 737   /* Treating GIMPLE registers as virtual variables makes no sense.
 738      Also complain if we couldn't extract a _DECL out of the original
 739      expression.  */
 740   gcc_assert (SSA_VAR_P (var));
 741   gcc_assert (!is_gimple_reg (var));
 742
 743   return var;
 744 }
 745
 746 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
 747    add_referenced_var, but is used by passes that need to add new temps to
 748    the REFERENCED_VARS array after the program has been scanned for
 749    variables.  The variable will just receive a new UID and be added
 750    to the REFERENCED_VARS array without checking for duplicates.  */
 751
 752 void
 753 add_referenced_tmp_var (tree var)
 754 {
 755   add_referenced_var (var, NULL);
 756 }
 757
 758
 759 /* Mark all the non-SSA variables found in STMT's operands to be
 760    processed by update_ssa.  */
 761
 762 void
 763 mark_new_vars_to_rename (tree stmt)
 764 {
 765   ssa_op_iter iter;
 766   tree val;
 767   bitmap vars_in_vops_to_rename;
 768   bool found_exposed_symbol = false;
 769   int v_may_defs_before, v_may_defs_after;
 770   int v_must_defs_before, v_must_defs_after;
 771
 772   if (TREE_CODE (stmt) == PHI_NODE)
 773     return;
 774
 775   vars_in_vops_to_rename = BITMAP_ALLOC (NULL);
 776
 777   /* Before re-scanning the statement for operands, mark the existing
 778      virtual operands to be renamed again.  We do this because when new
 779      symbols are exposed, the virtual operands that were here before due to
 780      aliasing will probably be removed by the call to get_stmt_operand.
 781      Therefore, we need to flag them to be renamed beforehand.
 782
 783      We flag them in a separate bitmap because we don't really want to
 784      rename them if there are not any newly exposed symbols in the
 785      statement operands.  */
 786   v_may_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
 787   v_must_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
 788
 789   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
 790                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
 791     {
 792       if (!DECL_P (val))
 793         val = SSA_NAME_VAR (val);
 794       bitmap_set_bit (vars_in_vops_to_rename, DECL_UID (val));
 795     }
 796
 797   /* Now force an operand re-scan on the statement and mark any newly
 798      exposed variables.  */
 799   update_stmt (stmt);
 800
 801   v_may_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
 802   v_must_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
 803
 804   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS)
 805     if (DECL_P (val))
 806       {
 807         found_exposed_symbol = true;
 808         mark_sym_for_renaming (val);
 809       }
 810
 811   /* If we found any newly exposed symbols, or if there are fewer VDEF
 812      operands in the statement, add the variables we had set in
 813      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
 814      vanishing VDEFs because in those cases, the names that were formerly
 815      generated by this statement are not going to be available anymore.  */
 816   if (found_exposed_symbol
 817       || v_may_defs_before > v_may_defs_after
 818       || v_must_defs_before > v_must_defs_after)
 819     mark_set_for_renaming (vars_in_vops_to_rename);
 820
 821   BITMAP_FREE (vars_in_vops_to_rename);
 822 }
 823
 824 /* Find all variables within the gimplified statement that were not previously
 825    visible to the function and add them to the referenced variables list.  */
 826
 827 static tree
 828 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 829                             void *data ATTRIBUTE_UNUSED)
 830 {
 831   tree t = *tp;
 832
 833   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 834     {
 835       add_referenced_tmp_var (t);
 836       mark_sym_for_renaming (t);
 837     }
 838
 839   if (IS_TYPE_OR_DECL_P (t))
 840     *walk_subtrees = 0;
 841
 842   return NULL;
 843 }
 844
 845 void
 846 find_new_referenced_vars (tree *stmt_p)
 847 {
 848   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 849 }
 850
 851
 852 /* If REF is a handled component reference for a structure, return the
 853    base variable.  The access range is delimited by bit positions *POFFSET and
 854    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 855    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 856    and *PMAX_SIZE are equal, the access is non-variable.  */
 857
 858 tree
 859 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 860                          HOST_WIDE_INT *psize,
 861                          HOST_WIDE_INT *pmax_size)
 862 {
 863   HOST_WIDE_INT bitsize = -1;
 864   HOST_WIDE_INT maxsize = -1;
 865   tree size_tree = NULL_TREE;
 866   tree bit_offset = bitsize_zero_node;
 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             else
 960               {
 961                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 962                 /* We need to adjust maxsize to the whole array bitsize.
 963                    But we can subtract any constant offset seen sofar,
 964                    because that would get us outside of the array otherwise.  */
 965                 if (maxsize != -1
 966                     && asize && host_integerp (asize, 1))
 967                   {
 968                     maxsize = (TREE_INT_CST_LOW (asize)
 969                                - TREE_INT_CST_LOW (bit_offset));
 970                   }
 971                 else
 972                   maxsize = -1;
 973               }
 974           }
 975           break;
 976
 977         case REALPART_EXPR:
 978           break;
 979
 980         case IMAGPART_EXPR:
 981           bit_offset = size_binop (PLUS_EXPR, bit_offset,
 982                                    bitsize_int (bitsize));
 983           break;
 984
 985         case VIEW_CONVERT_EXPR:
 986           /* ???  We probably should give up here and bail out.  */
 987           break;
 988
 989         default:
 990           goto done;
 991         }
 992
 993       exp = TREE_OPERAND (exp, 0);
 994     }
 995  done:
 996
 997   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 998      negative bit_offset here.  We might want to store a zero offset
 999      in this case.  */
1000   *poffset = TREE_INT_CST_LOW (bit_offset);
1001   *psize = bitsize;
1002   *pmax_size = maxsize;
1003
1004   return exp;
1005 }