gcc/tree-dfa.c

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