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   tree phi;
  89
  90   FOR_EACH_BB (bb)
  91     {
  92       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
  93         {
  94           tree *stmt_p = bsi_stmt_ptr (si);
  95           walk_tree (stmt_p, find_vars_r, NULL, NULL);
  96         }
  97
  98       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
  99         {
 100           int len = PHI_NUM_ARGS (phi);
 101           int i;
 102
 103           walk_tree (&phi, find_vars_r, NULL, NULL);
 104
 105           for (i = 0; i < len; i++)
 106             {
 107               tree arg = PHI_ARG_DEF (phi, i);
 108               walk_tree (&arg, find_vars_r, NULL, NULL);
 109             }
 110         }
 111     }
 112
 113   return 0;
 114 }
 115
 116 struct gimple_opt_pass pass_referenced_vars =
 117 {
 118  {
 119   GIMPLE_PASS,
 120   NULL,                                 /* name */
 121   NULL,                                 /* gate */
 122   find_referenced_vars,                 /* execute */
 123   NULL,                                 /* sub */
 124   NULL,                                 /* next */
 125   0,                                    /* static_pass_number */
 126   TV_FIND_REFERENCED_VARS,              /* tv_id */
 127   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 128   PROP_referenced_vars,                 /* properties_provided */
 129   0,                                    /* properties_destroyed */
 130   TODO_dump_func,                       /* todo_flags_start */
 131   TODO_dump_func                        /* todo_flags_finish */
 132  }
 133 };
 134
 135
 136 /*---------------------------------------------------------------------------
 137                             Manage annotations
 138 ---------------------------------------------------------------------------*/
 139 /* Create a new annotation for a _DECL node T.  */
 140
 141 var_ann_t
 142 create_var_ann (tree t)
 143 {
 144   var_ann_t ann;
 145
 146   gcc_assert (t);
 147   gcc_assert (DECL_P (t));
 148   gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
 149
 150   ann = GGC_CNEW (struct var_ann_d);
 151   ann->common.type = VAR_ANN;
 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   ann->uid = inc_gimple_stmt_max_uid (cfun);
 196   t->base.ann = (tree_ann_t) ann;
 197
 198   return ann;
 199 }
 200
 201 /* Renumber all of the gimple stmt uids.  */
 202
 203 void
 204 renumber_gimple_stmt_uids (void)
 205 {
 206   basic_block bb;
 207
 208   set_gimple_stmt_max_uid (cfun, 0);
 209   FOR_ALL_BB (bb)
 210     {
 211       block_stmt_iterator bsi;
 212       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 213         {
 214           tree stmt = bsi_stmt (bsi);
 215           /* If the stmt has an annotation, then overwrite it, if not,
 216              the process of getting it will set the number
 217              properly.  */
 218           if (has_stmt_ann (stmt))
 219             set_gimple_stmt_uid (stmt, inc_gimple_stmt_max_uid (cfun));
 220           else
 221             get_stmt_ann (stmt);
 222         }
 223     }
 224 }
 225
 226 /* Create a new annotation for a tree T.  */
 227
 228 tree_ann_common_t
 229 create_tree_common_ann (tree t)
 230 {
 231   tree_ann_common_t ann;
 232
 233   gcc_assert (t);
 234   gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
 235
 236   ann = GGC_CNEW (struct tree_ann_common_d);
 237
 238   ann->type = TREE_ANN_COMMON;
 239   t->base.ann = (tree_ann_t) ann;
 240
 241   return ann;
 242 }
 243
 244 /* Build a temporary.  Make sure and register it to be renamed.  */
 245
 246 tree
 247 make_rename_temp (tree type, const char *prefix)
 248 {
 249   tree t = create_tmp_var (type, prefix);
 250
 251   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 252       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 253     DECL_GIMPLE_REG_P (t) = 1;
 254
 255   if (gimple_referenced_vars (cfun))
 256     {
 257       add_referenced_var (t);
 258       mark_sym_for_renaming (t);
 259     }
 260
 261   return t;
 262 }
 263
 264
 265
 266 /*---------------------------------------------------------------------------
 267                               Debugging functions
 268 ---------------------------------------------------------------------------*/
 269 /* Dump the list of all the referenced variables in the current function to
 270    FILE.  */
 271
 272 void
 273 dump_referenced_vars (FILE *file)
 274 {
 275   tree var;
 276   referenced_var_iterator rvi;
 277
 278   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 279            get_name (current_function_decl), (unsigned) num_referenced_vars);
 280
 281   FOR_EACH_REFERENCED_VAR (var, rvi)
 282     {
 283       fprintf (file, "Variable: ");
 284       dump_variable (file, var);
 285       fprintf (file, "\n");
 286     }
 287 }
 288
 289
 290 /* Dump the list of all the referenced variables to stderr.  */
 291
 292 void
 293 debug_referenced_vars (void)
 294 {
 295   dump_referenced_vars (stderr);
 296 }
 297
 298
 299 /* Dump variable VAR and its may-aliases to FILE.  */
 300
 301 void
 302 dump_variable (FILE *file, tree var)
 303 {
 304   var_ann_t ann;
 305
 306   if (TREE_CODE (var) == SSA_NAME)
 307     {
 308       if (POINTER_TYPE_P (TREE_TYPE (var)))
 309         dump_points_to_info_for (file, var);
 310       var = SSA_NAME_VAR (var);
 311     }
 312
 313   if (var == NULL_TREE)
 314     {
 315       fprintf (file, "<nil>");
 316       return;
 317     }
 318
 319   print_generic_expr (file, var, dump_flags);
 320
 321   ann = var_ann (var);
 322
 323   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 324
 325   fprintf (file, ", ");
 326   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 327
 328   if (ann && ann->symbol_mem_tag)
 329     {
 330       fprintf (file, ", symbol memory tag: ");
 331       print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
 332     }
 333
 334   if (TREE_ADDRESSABLE (var))
 335     fprintf (file, ", is addressable");
 336
 337   if (is_global_var (var))
 338     fprintf (file, ", is global");
 339
 340   if (TREE_THIS_VOLATILE (var))
 341     fprintf (file, ", is volatile");
 342
 343   dump_mem_sym_stats_for_var (file, var);
 344
 345   if (is_call_clobbered (var))
 346     {
 347       const char *s = "";
 348       var_ann_t va = var_ann (var);
 349       unsigned int escape_mask = va->escape_mask;
 350
 351       fprintf (file, ", call clobbered");
 352       fprintf (file, " (");
 353       if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
 354         { fprintf (file, "%sstored in global", s); s = ", "; }
 355       if (escape_mask & ESCAPE_TO_ASM)
 356         { fprintf (file, "%sgoes through ASM", s); s = ", "; }
 357       if (escape_mask & ESCAPE_TO_CALL)
 358         { fprintf (file, "%spassed to call", s); s = ", "; }
 359       if (escape_mask & ESCAPE_BAD_CAST)
 360         { fprintf (file, "%sbad cast", s); s = ", "; }
 361       if (escape_mask & ESCAPE_TO_RETURN)
 362         { fprintf (file, "%sreturned from func", s); s = ", "; }
 363       if (escape_mask & ESCAPE_TO_PURE_CONST)
 364         { fprintf (file, "%spassed to pure/const", s); s = ", "; }
 365       if (escape_mask & ESCAPE_IS_GLOBAL)
 366         { fprintf (file, "%sis global var", s); s = ", "; }
 367       if (escape_mask & ESCAPE_IS_PARM)
 368         { fprintf (file, "%sis incoming pointer", s); s = ", "; }
 369       if (escape_mask & ESCAPE_UNKNOWN)
 370         { fprintf (file, "%sunknown escape", s); s = ", "; }
 371       fprintf (file, ")");
 372     }
 373
 374   if (ann->noalias_state == NO_ALIAS)
 375     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
 376   else if (ann->noalias_state == NO_ALIAS_GLOBAL)
 377     fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
 378                    " and global vars)");
 379   else if (ann->noalias_state == NO_ALIAS_ANYTHING)
 380     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
 381
 382   if (gimple_default_def (cfun, var))
 383     {
 384       fprintf (file, ", default def: ");
 385       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 386     }
 387
 388   if (MTAG_P (var) && may_aliases (var))
 389     {
 390       fprintf (file, ", may aliases: ");
 391       dump_may_aliases_for (file, var);
 392     }
 393
 394   if (!is_gimple_reg (var))
 395     {
 396       if (memory_partition (var))
 397         {
 398           fprintf (file, ", belongs to partition: ");
 399           print_generic_expr (file, memory_partition (var), dump_flags);
 400         }
 401
 402       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
 403         {
 404           fprintf (file, ", partition symbols: ");
 405           dump_decl_set (file, MPT_SYMBOLS (var));
 406         }
 407     }
 408
 409   fprintf (file, "\n");
 410 }
 411
 412
 413 /* Dump variable VAR and its may-aliases to stderr.  */
 414
 415 void
 416 debug_variable (tree var)
 417 {
 418   dump_variable (stderr, var);
 419 }
 420
 421
 422 /* Dump various DFA statistics to FILE.  */
 423
 424 void
 425 dump_dfa_stats (FILE *file)
 426 {
 427   struct dfa_stats_d dfa_stats;
 428
 429   unsigned long size, total = 0;
 430   const char * const fmt_str   = "%-30s%-13s%12s\n";
 431   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 432   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 433   const char *funcname
 434     = lang_hooks.decl_printable_name (current_function_decl, 2);
 435
 436   collect_dfa_stats (&dfa_stats);
 437
 438   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 439
 440   fprintf (file, "---------------------------------------------------------\n");
 441   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 442   fprintf (file, fmt_str, "", "  instances  ", "used ");
 443   fprintf (file, "---------------------------------------------------------\n");
 444
 445   size = num_referenced_vars * sizeof (tree);
 446   total += size;
 447   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 448            SCALE (size), LABEL (size));
 449
 450   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 451   total += size;
 452   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 453            SCALE (size), LABEL (size));
 454
 455   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 456   total += size;
 457   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 458            SCALE (size), LABEL (size));
 459
 460   size = dfa_stats.num_uses * sizeof (tree *);
 461   total += size;
 462   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 463            SCALE (size), LABEL (size));
 464
 465   size = dfa_stats.num_defs * sizeof (tree *);
 466   total += size;
 467   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 468            SCALE (size), LABEL (size));
 469
 470   size = dfa_stats.num_vuses * sizeof (tree *);
 471   total += size;
 472   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 473            SCALE (size), LABEL (size));
 474
 475   size = dfa_stats.num_vdefs * sizeof (tree *);
 476   total += size;
 477   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 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 NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 530   pset = pointer_set_create ();
 531
 532   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 533        !bsi_end_p (i); bsi_next (&i))
 534     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 535                pset);
 536
 537   pointer_set_destroy (pset);
 538
 539   FOR_EACH_BB (bb)
 540     {
 541       tree phi;
 542       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 543         {
 544           dfa_stats_p->num_phis++;
 545           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 546           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 547             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 548         }
 549     }
 550 }
 551
 552
 553 /* Callback for walk_tree to collect DFA statistics for a tree and its
 554    children.  */
 555
 556 static tree
 557 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 558                      void *data)
 559 {
 560   tree t = *tp;
 561   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 562
 563   if (t->base.ann)
 564     {
 565       switch (ann_type (t->base.ann))
 566         {
 567         case STMT_ANN:
 568           {
 569             dfa_stats_p->num_stmt_anns++;
 570             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 571             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 572             dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (t, SSA_OP_VDEF);
 573             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 574             break;
 575           }
 576
 577         case VAR_ANN:
 578           dfa_stats_p->num_var_anns++;
 579           break;
 580
 581         default:
 582           break;
 583         }
 584     }
 585
 586   return NULL;
 587 }
 588
 589
 590 /*---------------------------------------------------------------------------
 591                              Miscellaneous helpers
 592 ---------------------------------------------------------------------------*/
 593 /* Callback for walk_tree.  Used to collect variables referenced in
 594    the function.  */
 595
 596 static tree
 597 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 598 {
 599   /* If we are reading the lto info back in, we need to rescan the
 600      referenced vars.  */
 601   if (TREE_CODE (*tp) == SSA_NAME)
 602     add_referenced_var (SSA_NAME_VAR (*tp));
 603
 604   /* If T is a regular variable that the optimizers are interested
 605      in, add it to the list of variables.  */
 606   else if (SSA_VAR_P (*tp))
 607     add_referenced_var (*tp);
 608
 609   /* Type, _DECL and constant nodes have no interesting children.
 610      Ignore them.  */
 611   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 612     *walk_subtrees = 0;
 613
 614   return NULL_TREE;
 615 }
 616
 617 /* Lookup UID in the referenced_vars hashtable and return the associated
 618    variable.  */
 619
 620 tree
 621 referenced_var_lookup (unsigned int uid)
 622 {
 623   tree h;
 624   struct tree_decl_minimal in;
 625   in.uid = uid;
 626   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 627   gcc_assert (h || uid == 0);
 628   return h;
 629 }
 630
 631 /* Check if TO is in the referenced_vars hash table and insert it if not.
 632    Return true if it required insertion.  */
 633
 634 bool
 635 referenced_var_check_and_insert (tree to)
 636 {
 637   tree h, *loc;
 638   struct tree_decl_minimal in;
 639   unsigned int uid = DECL_UID (to);
 640
 641   in.uid = uid;
 642   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 643   if (h)
 644     {
 645       /* DECL_UID has already been entered in the table.  Verify that it is
 646          the same entry as TO.  See PR 27793.  */
 647       gcc_assert (h == to);
 648       return false;
 649     }
 650
 651   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 652                                            &in, uid, INSERT);
 653   *loc = to;
 654   return true;
 655 }
 656
 657 /* Lookup VAR UID in the default_defs hashtable and return the associated
 658    variable.  */
 659
 660 tree
 661 gimple_default_def (struct function *fn, tree var)
 662 {
 663   struct tree_decl_minimal ind;
 664   struct tree_ssa_name in;
 665   gcc_assert (SSA_VAR_P (var));
 666   in.var = (tree)&ind;
 667   ind.uid = DECL_UID (var);
 668   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 669 }
 670
 671 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 672
 673 void
 674 set_default_def (tree var, tree def)
 675 {
 676   struct tree_decl_minimal ind;
 677   struct tree_ssa_name in;
 678   void **loc;
 679
 680   gcc_assert (SSA_VAR_P (var));
 681   in.var = (tree)&ind;
 682   ind.uid = DECL_UID (var);
 683   if (!def)
 684     {
 685       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 686             DECL_UID (var), INSERT);
 687       gcc_assert (*loc);
 688       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 689       return;
 690     }
 691   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 692   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 693                                   DECL_UID (var), INSERT);
 694
 695   /* Default definition might be changed by tail call optimization.  */
 696   if (*loc)
 697     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 698   *(tree *) loc = def;
 699
 700    /* Mark DEF as the default definition for VAR.  */
 701    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 702 }
 703
 704 /* Add VAR to the list of referenced variables if it isn't already there.  */
 705
 706 void
 707 add_referenced_var (tree var)
 708 {
 709   var_ann_t v_ann;
 710
 711   v_ann = get_var_ann (var);
 712   gcc_assert (DECL_P (var));
 713
 714   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 715   if (referenced_var_check_and_insert (var))
 716     {
 717       /* This is the first time we found this variable, annotate it with
 718          attributes that are intrinsic to the variable.  */
 719
 720       /* Tag's don't have DECL_INITIAL.  */
 721       if (MTAG_P (var))
 722         return;
 723
 724       /* Scan DECL_INITIAL for pointer variables as they may contain
 725          address arithmetic referencing the address of other
 726          variables.
 727          Even non-constant intializers need to be walked, because
 728          IPA passes might prove that their are invariant later on.  */
 729       if (DECL_INITIAL (var)
 730           /* Initializers of external variables are not useful to the
 731              optimizers.  */
 732           && !DECL_EXTERNAL (var))
 733         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 734     }
 735 }
 736
 737 /* Remove VAR from the list.  */
 738
 739 void
 740 remove_referenced_var (tree var)
 741 {
 742   var_ann_t v_ann;
 743   struct tree_decl_minimal in;
 744   void **loc;
 745   unsigned int uid = DECL_UID (var);
 746
 747   clear_call_clobbered (var);
 748   if ((v_ann = var_ann (var)))
 749     {
 750       /* Preserve var_anns of globals, but clear their alias info.  */
 751       if (MTAG_P (var)
 752           || (!TREE_STATIC (var) && !DECL_EXTERNAL (var)))
 753         {
 754           ggc_free (v_ann);
 755           var->base.ann = NULL;
 756         }
 757       else
 758         {
 759           v_ann->mpt = NULL_TREE;
 760           v_ann->symbol_mem_tag = NULL_TREE;
 761         }
 762     }
 763   gcc_assert (DECL_P (var));
 764   in.uid = uid;
 765   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 766                                   NO_INSERT);
 767   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 768 }
 769
 770
 771 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 772
 773 tree
 774 get_virtual_var (tree var)
 775 {
 776   STRIP_NOPS (var);
 777
 778   if (TREE_CODE (var) == SSA_NAME)
 779     var = SSA_NAME_VAR (var);
 780
 781   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 782          || handled_component_p (var))
 783     var = TREE_OPERAND (var, 0);
 784
 785   /* Treating GIMPLE registers as virtual variables makes no sense.
 786      Also complain if we couldn't extract a _DECL out of the original
 787      expression.  */
 788   gcc_assert (SSA_VAR_P (var));
 789   gcc_assert (!is_gimple_reg (var));
 790
 791   return var;
 792 }
 793
 794 /* Mark all the naked symbols in STMT for SSA renaming.
 795
 796    NOTE: This function should only be used for brand new statements.
 797    If the caller is modifying an existing statement, it should use the
 798    combination push_stmt_changes/pop_stmt_changes.  */
 799
 800 void
 801 mark_symbols_for_renaming (tree stmt)
 802 {
 803   tree op;
 804   ssa_op_iter iter;
 805
 806   update_stmt (stmt);
 807
 808   /* Mark all the operands for renaming.  */
 809   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 810     if (DECL_P (op))
 811       mark_sym_for_renaming (op);
 812 }
 813
 814
 815 /* Find all variables within the gimplified statement that were not previously
 816    visible to the function and add them to the referenced variables list.  */
 817
 818 static tree
 819 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 820                             void *data ATTRIBUTE_UNUSED)
 821 {
 822   tree t = *tp;
 823
 824   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 825     {
 826       add_referenced_var (t);
 827       mark_sym_for_renaming (t);
 828     }
 829
 830   if (IS_TYPE_OR_DECL_P (t))
 831     *walk_subtrees = 0;
 832
 833   return NULL;
 834 }
 835
 836 void
 837 find_new_referenced_vars (tree *stmt_p)
 838 {
 839   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 840 }
 841
 842
 843 /* If EXP is a handled component reference for a structure, return the
 844    base variable.  The access range is delimited by bit positions *POFFSET and
 845    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 846    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 847    and *PMAX_SIZE are equal, the access is non-variable.  */
 848
 849 tree
 850 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 851                          HOST_WIDE_INT *psize,
 852                          HOST_WIDE_INT *pmax_size)
 853 {
 854   HOST_WIDE_INT bitsize = -1;
 855   HOST_WIDE_INT maxsize = -1;
 856   tree size_tree = NULL_TREE;
 857   HOST_WIDE_INT bit_offset = 0;
 858   bool seen_variable_array_ref = false;
 859
 860   gcc_assert (!SSA_VAR_P (exp));
 861
 862   /* First get the final access size from just the outermost expression.  */
 863   if (TREE_CODE (exp) == COMPONENT_REF)
 864     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 865   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 866     size_tree = TREE_OPERAND (exp, 1);
 867   else
 868     {
 869       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 870       if (mode == BLKmode)
 871         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 872       else
 873         bitsize = GET_MODE_BITSIZE (mode);
 874     }
 875   if (size_tree != NULL_TREE)
 876     {
 877       if (! host_integerp (size_tree, 1))
 878         bitsize = -1;
 879       else
 880         bitsize = TREE_INT_CST_LOW (size_tree);
 881     }
 882
 883   /* Initially, maxsize is the same as the accessed element size.
 884      In the following it will only grow (or become -1).  */
 885   maxsize = bitsize;
 886
 887   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 888      and find the ultimate containing object.  */
 889   while (1)
 890     {
 891       switch (TREE_CODE (exp))
 892         {
 893         case BIT_FIELD_REF:
 894           bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
 895           break;
 896
 897         case COMPONENT_REF:
 898           {
 899             tree field = TREE_OPERAND (exp, 1);
 900             tree this_offset = component_ref_field_offset (exp);
 901
 902             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 903               {
 904                 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
 905
 906                 hthis_offset *= BITS_PER_UNIT;
 907                 bit_offset += hthis_offset;
 908                 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
 909               }
 910             else
 911               {
 912                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 913                 /* We need to adjust maxsize to the whole structure bitsize.
 914                    But we can subtract any constant offset seen sofar,
 915                    because that would get us out of the structure otherwise.  */
 916                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 917                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 918                 else
 919                   maxsize = -1;
 920               }
 921           }
 922           break;
 923
 924         case ARRAY_REF:
 925         case ARRAY_RANGE_REF:
 926           {
 927             tree index = TREE_OPERAND (exp, 1);
 928             tree low_bound = array_ref_low_bound (exp);
 929             tree unit_size = array_ref_element_size (exp);
 930
 931             /* If the resulting bit-offset is constant, track it.  */
 932             if (host_integerp (index, 0)
 933                 && host_integerp (low_bound, 0)
 934                 && host_integerp (unit_size, 1))
 935               {
 936                 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
 937
 938                 hindex -= tree_low_cst (low_bound, 0);
 939                 hindex *= tree_low_cst (unit_size, 1);
 940                 hindex *= BITS_PER_UNIT;
 941                 bit_offset += hindex;
 942
 943                 /* An array ref with a constant index up in the structure
 944                    hierarchy will constrain the size of any variable array ref
 945                    lower in the access hierarchy.  */
 946                 seen_variable_array_ref = false;
 947               }
 948             else
 949               {
 950                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 951                 /* We need to adjust maxsize to the whole array bitsize.
 952                    But we can subtract any constant offset seen sofar,
 953                    because that would get us outside of the array otherwise.  */
 954                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 955                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 956                 else
 957                   maxsize = -1;
 958
 959                 /* Remember that we have seen an array ref with a variable
 960                    index.  */
 961                 seen_variable_array_ref = true;
 962               }
 963           }
 964           break;
 965
 966         case REALPART_EXPR:
 967           break;
 968
 969         case IMAGPART_EXPR:
 970           bit_offset += bitsize;
 971           break;
 972
 973         case VIEW_CONVERT_EXPR:
 974           /* ???  We probably should give up here and bail out.  */
 975           break;
 976
 977         default:
 978           goto done;
 979         }
 980
 981       exp = TREE_OPERAND (exp, 0);
 982     }
 983  done:
 984
 985   /* We need to deal with variable arrays ending structures such as
 986        struct { int length; int a[1]; } x;           x.a[d]
 987        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 988        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 989      where we do not know maxsize for variable index accesses to
 990      the array.  The simplest way to conservatively deal with this
 991      is to punt in the case that offset + maxsize reaches the
 992      base type boundary.  */
 993   if (seen_variable_array_ref
 994       && maxsize != -1
 995       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 996       && bit_offset + maxsize
 997            == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
 998     maxsize = -1;
 999
1000   /* ???  Due to negative offsets in ARRAY_REF we can end up with
1001      negative bit_offset here.  We might want to store a zero offset
1002      in this case.  */
1003   *poffset = bit_offset;
1004   *psize = bitsize;
1005   *pmax_size = maxsize;
1006
1007   return exp;
1008 }
1009
1010 /* Returns true if STMT references an SSA_NAME that has
1011    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
1012
1013 bool
1014 stmt_references_abnormal_ssa_name (tree stmt)
1015 {
1016   ssa_op_iter oi;
1017   use_operand_p use_p;
1018
1019   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
1020     {
1021       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
1022         return true;
1023     }
1024
1025   return false;
1026 }
1027
1028 /* Return true, if the two memory references REF1 and REF2 may alias.  */
1029
1030 bool
1031 refs_may_alias_p (tree ref1, tree ref2)
1032 {
1033   tree base1, base2;
1034   HOST_WIDE_INT offset1 = 0, offset2 = 0;
1035   HOST_WIDE_INT size1 = -1, size2 = -1;
1036   HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
1037   bool strict_aliasing_applies;
1038
1039   gcc_assert ((SSA_VAR_P (ref1)
1040                || handled_component_p (ref1)
1041                || INDIRECT_REF_P (ref1)
1042                || TREE_CODE (ref1) == TARGET_MEM_REF)
1043               && (SSA_VAR_P (ref2)
1044                   || handled_component_p (ref2)
1045                   || INDIRECT_REF_P (ref2)
1046                   || TREE_CODE (ref2) == TARGET_MEM_REF));
1047
1048   /* Defer to TBAA if possible.  */
1049   if (flag_strict_aliasing
1050       && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
1051     return false;
1052
1053   /* Decompose the references into their base objects and the access.  */
1054   base1 = ref1;
1055   if (handled_component_p (ref1))
1056     base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
1057   base2 = ref2;
1058   if (handled_component_p (ref2))
1059     base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
1060
1061   /* If both references are based on different variables, they cannot alias.
1062      If both references are based on the same variable, they cannot alias if
1063      if the accesses do not overlap.  */
1064   if (SSA_VAR_P (base1)
1065       && SSA_VAR_P (base2))
1066     {
1067       if (!operand_equal_p (base1, base2, 0))
1068         return false;
1069       return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1070     }
1071
1072   /* If one base is a ref-all pointer weird things are allowed.  */
1073   strict_aliasing_applies = (flag_strict_aliasing
1074                              && (!INDIRECT_REF_P (base1)
1075                                  || get_alias_set (base1) != 0)
1076                              && (!INDIRECT_REF_P (base2)
1077                                  || get_alias_set (base2) != 0));
1078
1079   /* If strict aliasing applies the only way to access a scalar variable
1080      is through a pointer dereference or through a union (gcc extension).  */
1081   if (strict_aliasing_applies
1082       && ((SSA_VAR_P (ref2)
1083            && !AGGREGATE_TYPE_P (TREE_TYPE (ref2))
1084            && !INDIRECT_REF_P (ref1)
1085            && TREE_CODE (TREE_TYPE (base1)) != UNION_TYPE)
1086           || (SSA_VAR_P (ref1)
1087               && !AGGREGATE_TYPE_P (TREE_TYPE (ref1))
1088               && !INDIRECT_REF_P (ref2)
1089               && TREE_CODE (TREE_TYPE (base2)) != UNION_TYPE)))
1090     return false;
1091
1092   /* If both references are through the same type, or if strict aliasing
1093      doesn't apply they are through two same pointers, they do not alias
1094      if the accesses do not overlap.  */
1095   if ((strict_aliasing_applies
1096        && (TYPE_MAIN_VARIANT (TREE_TYPE (base1))
1097            == TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1098       || (TREE_CODE (base1) == INDIRECT_REF
1099           && TREE_CODE (base2) == INDIRECT_REF
1100           && operand_equal_p (TREE_OPERAND (base1, 0),
1101                               TREE_OPERAND (base2, 0), 0)))
1102     return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1103
1104   /* If both are component references through pointers try to find a
1105      common base and apply offset based disambiguation.  This handles
1106      for example
1107        struct A { int i; int j; } *q;
1108        struct B { struct A a; int k; } *p;
1109      disambiguating q->i and p->a.j.  */
1110   if (strict_aliasing_applies
1111       && (TREE_CODE (base1) == INDIRECT_REF
1112           || TREE_CODE (base2) == INDIRECT_REF)
1113       && handled_component_p (ref1)
1114       && handled_component_p (ref2))
1115     {
1116       tree *refp;
1117       /* Now search for the type of base1 in the access path of ref2.  This
1118          would be a common base for doing offset based disambiguation on.  */
1119       refp = &ref2;
1120       while (handled_component_p (*refp)
1121              /* Note that the following is only conservative if there are
1122                 never copies of types appearing as sub-structures.  */
1123              && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1124                  != TYPE_MAIN_VARIANT (TREE_TYPE (base1))))
1125         refp = &TREE_OPERAND (*refp, 0);
1126       if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1127           == TYPE_MAIN_VARIANT (TREE_TYPE (base1)))
1128         {
1129           HOST_WIDE_INT offadj, sztmp, msztmp;
1130           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1131           offset2 -= offadj;
1132           return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1133         }
1134       /* The other way around.  */
1135       refp = &ref1;
1136       while (handled_component_p (*refp)
1137              && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1138                  != TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1139         refp = &TREE_OPERAND (*refp, 0);
1140       if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1141           == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))
1142         {
1143           HOST_WIDE_INT offadj, sztmp, msztmp;
1144           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1145           offset1 -= offadj;
1146           return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1147         }
1148       /* If we can be sure to catch all equivalent types in the search
1149          for the common base then we could return false here.  In that
1150          case we would be able to disambiguate q->i and p->k.  */
1151     }
1152
1153   return true;
1154 }
1155
1156 /* Given a stmt STMT that references memory, return the single stmt
1157    that is reached by following the VUSE -> VDEF link.  Returns
1158    NULL_TREE, if there is no single stmt that defines all VUSEs of
1159    STMT.
1160    Note that for a stmt with a single virtual operand this may return
1161    a PHI node as well.  Note that if all VUSEs are default definitions
1162    this function will return an empty statement.  */
1163
1164 tree
1165 get_single_def_stmt (tree stmt)
1166 {
1167   tree def_stmt = NULL_TREE;
1168   tree use;
1169   ssa_op_iter iter;
1170
1171   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
1172     {
1173       tree tmp = SSA_NAME_DEF_STMT (use);
1174
1175       /* ???  This is too simplistic for multiple virtual operands
1176          reaching different PHI nodes of the same basic blocks or for
1177          reaching all default definitions.  */
1178       if (def_stmt
1179           && def_stmt != tmp
1180           && !(IS_EMPTY_STMT (def_stmt)
1181                && IS_EMPTY_STMT (tmp)))
1182         return NULL_TREE;
1183
1184       def_stmt = tmp;
1185     }
1186
1187   return def_stmt;
1188 }
1189
1190 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1191    reached definitions if they do not alias REF and returns the
1192    defining statement of the single virtual operand that flows in
1193    from a non-backedge.  Returns NULL_TREE if such statement within
1194    the above conditions cannot be found.  */
1195
1196 tree
1197 get_single_def_stmt_from_phi (tree ref, tree phi)
1198 {
1199   tree def_arg = NULL_TREE;
1200   int i;
1201
1202   /* Find the single PHI argument that is not flowing in from a
1203      back edge and verify that the loop-carried definitions do
1204      not alias the reference we look for.  */
1205   for (i = 0; i < PHI_NUM_ARGS (phi); ++i)
1206     {
1207       tree arg = PHI_ARG_DEF (phi, i);
1208       tree def_stmt;
1209
1210       if (!(PHI_ARG_EDGE (phi, i)->flags & EDGE_DFS_BACK))
1211         {
1212           /* Multiple non-back edges?  Do not try to handle this.  */
1213           if (def_arg)
1214             return NULL_TREE;
1215           def_arg = arg;
1216           continue;
1217         }
1218
1219       /* Follow the definitions back to the original PHI node.  Bail
1220          out once a definition is found that may alias REF.  */
1221       def_stmt = SSA_NAME_DEF_STMT (arg);
1222       do
1223         {
1224           if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
1225               || refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
1226             return NULL_TREE;
1227           /* ???  This will only work, reaching the PHI node again if
1228              there is a single virtual operand on def_stmt.  */
1229           def_stmt = get_single_def_stmt (def_stmt);
1230           if (!def_stmt)
1231             return NULL_TREE;
1232         }
1233       while (def_stmt != phi);
1234     }
1235
1236   return SSA_NAME_DEF_STMT (def_arg);
1237 }
1238
1239 /* Return the single reference statement defining all virtual uses
1240    on STMT or NULL_TREE, if there are multiple defining statements.
1241    Take into account only definitions that alias REF if following
1242    back-edges when looking through a loop PHI node.  */
1243
1244 tree
1245 get_single_def_stmt_with_phi (tree ref, tree stmt)
1246 {
1247   switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
1248     {
1249     case 0:
1250       gcc_unreachable ();
1251
1252     case 1:
1253       {
1254         tree def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1255                                              (stmt, SSA_OP_VIRTUAL_USES));
1256         /* We can handle lookups over PHI nodes only for a single
1257            virtual operand.  */
1258         if (TREE_CODE (def_stmt) == PHI_NODE)
1259           return get_single_def_stmt_from_phi (ref, def_stmt);
1260         return def_stmt;
1261       }
1262
1263     default:
1264       return get_single_def_stmt (stmt);
1265     }
1266 }