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