gcc/tree-ssa-operands.c

   1 /* SSA operands management for trees.
   2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "function.h"
  28 #include "diagnostic.h"
  29 #include "errors.h"
  30 #include "tree-flow.h"
  31 #include "tree-inline.h"
  32 #include "tree-pass.h"
  33 #include "ggc.h"
  34 #include "timevar.h"
  35
  36 #include "langhooks.h"
  37
  38 /* This file contains the code required to manage the operands cache of the
  39    SSA optimizer.  For every stmt, we maintain an operand cache in the stmt
  40    annotation.  This cache contains operands that will be of interest to
  41    optimizers and other passes wishing to manipulate the IL.
  42
  43    The operand type are broken up into REAL and VIRTUAL operands.  The real
  44    operands are represented as pointers into the stmt's operand tree.  Thus
  45    any manipulation of the real operands will be reflected in the actual tree.
  46    Virtual operands are represented solely in the cache, although the base
  47    variable for the SSA_NAME may, or may not occur in the stmt's tree.
  48    Manipulation of the virtual operands will not be reflected in the stmt tree.
  49
  50    The routines in this file are concerned with creating this operand cache
  51    from a stmt tree.
  52
  53    get_stmt_operands() in the primary entry point.
  54
  55    The operand tree is the parsed by the various get_* routines which look
  56    through the stmt tree for the occurrence of operands which may be of
  57    interest, and calls are made to the append_* routines whenever one is
  58    found.  There are 5 of these routines, each representing one of the
  59    5 types of operands. Defs, Uses, Virtual Uses, Virtual May Defs, and
  60    Virtual Must Defs.
  61
  62    The append_* routines check for duplication, and simply keep a list of
  63    unique objects for each operand type in the build_* extendable vectors.
  64
  65    Once the stmt tree is completely parsed, the finalize_ssa_operands()
  66    routine is called, which proceeds to perform the finalization routine
  67    on each of the 5 operand vectors which have been built up.
  68
  69    If the stmt had a previous operand cache, the finalization routines
  70    attempt to match up the new operands with the old ones.  If its a perfect
  71    match, the old vector is simply reused.  If it isn't a perfect match, then
  72    a new vector is created and the new operands are placed there.  For
  73    virtual operands, if the previous cache had SSA_NAME version of a
  74    variable, and that same variable occurs in the same operands cache, then
  75    the new cache vector will also get the same SSA_NAME.
  76
  77   i.e., if a stmt had a VUSE of 'a_5', and 'a' occurs in the new operand
  78   vector for VUSE, then the new vector will also be modified such that
  79   it contains 'a_5' rather than 'a'.
  80
  81 */
  82
  83
  84 /* Flags to describe operand properties in get_stmt_operands and helpers.  */
  85
  86 /* By default, operands are loaded.  */
  87 #define opf_none        0
  88
  89 /* Operand is the target of an assignment expression or a
  90    call-clobbered variable  */
  91 #define opf_is_def      (1 << 0)
  92
  93 /* Operand is the target of an assignment expression.  */
  94 #define opf_kill_def    (1 << 1)
  95
  96 /* No virtual operands should be created in the expression.  This is used
  97    when traversing ADDR_EXPR nodes which have different semantics than
  98    other expressions.  Inside an ADDR_EXPR node, the only operands that we
  99    need to consider are indices into arrays.  For instance, &a.b[i] should
 100    generate a USE of 'i' but it should not generate a VUSE for 'a' nor a
 101    VUSE for 'b'.  */
 102 #define opf_no_vops     (1 << 2)
 103
 104 /* Array for building all the def operands.  */
 105 static GTY (()) varray_type build_defs;
 106
 107 /* Array for building all the use operands.  */
 108 static GTY (()) varray_type build_uses;
 109
 110 /* Array for building all the v_may_def operands.  */
 111 static GTY (()) varray_type build_v_may_defs;
 112
 113 /* Array for building all the vuse operands.  */
 114 static GTY (()) varray_type build_vuses;
 115
 116 /* Array for building all the v_must_def operands.  */
 117 static GTY (()) varray_type build_v_must_defs;
 118
 119 /* True if the operands for call clobbered vars are cached and valid.  */
 120 bool ssa_call_clobbered_cache_valid;
 121 bool ssa_ro_call_cache_valid;
 122
 123 /* These arrays are the cached operand vectors for call clobbered calls.  */
 124 static GTY (()) varray_type clobbered_v_may_defs;
 125 static GTY (()) varray_type clobbered_vuses;
 126 static GTY (()) varray_type ro_call_vuses;
 127 static bool clobbered_aliased_loads;
 128 static bool clobbered_aliased_stores;
 129 static bool ro_call_aliased_loads;
 130 static stmt_operands_p parse_old_ops = NULL;
 131
 132 def_operand_p NULL_DEF_OPERAND_P = { NULL };
 133
 134 static void note_addressable (tree, stmt_ann_t);
 135 static void get_expr_operands (tree, tree *, int);
 136 static void get_asm_expr_operands (tree);
 137 static void get_indirect_ref_operands (tree, tree, int);
 138 static void get_call_expr_operands (tree, tree);
 139 static inline void append_def (tree *);
 140 static inline void append_use (tree *);
 141 static void append_v_may_def (tree);
 142 static void append_v_must_def (tree);
 143 static void add_call_clobber_ops (tree);
 144 static void add_call_read_ops (tree);
 145 static void add_stmt_operand (tree *, stmt_ann_t, int);
 146
 147 /* Return a vector of contiguous memory for NUM def operands.  */
 148
 149 static inline def_optype
 150 allocate_def_optype (unsigned num)
 151 {
 152   def_optype def_ops;
 153   unsigned size;
 154   size = sizeof (struct def_optype_d) + sizeof (tree *) * (num - 1);
 155   def_ops =  ggc_alloc (size);
 156   def_ops->num_defs = num;
 157   return def_ops;
 158 }
 159
 160
 161 /* Return a vector of contiguous memory for NUM use operands.  */
 162
 163 static inline use_optype
 164 allocate_use_optype (unsigned num)
 165 {
 166   use_optype use_ops;
 167   unsigned size;
 168   size = sizeof (struct use_optype_d) + sizeof (use_operand_type_t) * (num - 1);
 169   use_ops =  ggc_alloc (size);
 170   use_ops->num_uses = num;
 171   return use_ops;
 172 }
 173
 174
 175 /* Return a vector of contiguous memory for NUM v_may_def operands.  */
 176
 177 static inline v_may_def_optype
 178 allocate_v_may_def_optype (unsigned num)
 179 {
 180   v_may_def_optype v_may_def_ops;
 181   unsigned size;
 182   size = sizeof (struct v_may_def_optype_d)
 183            + sizeof (v_def_use_operand_type_t) * (num - 1);
 184   v_may_def_ops =  ggc_alloc (size);
 185   v_may_def_ops->num_v_may_defs = num;
 186   return v_may_def_ops;
 187 }
 188
 189
 190 /* Return a vector of contiguous memory for NUM v_use operands.  */
 191
 192 static inline vuse_optype
 193 allocate_vuse_optype (unsigned num)
 194 {
 195   vuse_optype vuse_ops;
 196   unsigned size;
 197   size = sizeof (struct vuse_optype_d)
 198        + sizeof (vuse_operand_type_t) * (num - 1);
 199   vuse_ops =  ggc_alloc (size);
 200   vuse_ops->num_vuses = num;
 201   return vuse_ops;
 202 }
 203
 204
 205 /* Return a vector of contiguous memory for NUM v_must_def operands.  */
 206
 207 static inline v_must_def_optype
 208 allocate_v_must_def_optype (unsigned num)
 209 {
 210   v_must_def_optype v_must_def_ops;
 211   unsigned size;
 212   size = sizeof (struct v_must_def_optype_d) + sizeof (v_def_use_operand_type_t) * (num - 1);
 213   v_must_def_ops =  ggc_alloc (size);
 214   v_must_def_ops->num_v_must_defs = num;
 215   return v_must_def_ops;
 216 }
 217
 218
 219 /* Free memory for USES.  */
 220
 221 static inline void
 222 free_uses (use_optype *uses)
 223 {
 224   if (*uses)
 225     {
 226       unsigned int x;
 227       use_optype use = *uses;
 228       for (x = 0; x < use->num_uses; x++)
 229         delink_imm_use (&(use->uses[x]));
 230       ggc_free (*uses);
 231       *uses = NULL;
 232     }
 233 }
 234
 235
 236 /* Free memory for DEFS.  */
 237
 238 static inline void
 239 free_defs (def_optype *defs)
 240 {
 241   if (*defs)
 242     {
 243       ggc_free (*defs);
 244       *defs = NULL;
 245     }
 246 }
 247
 248
 249 /* Free memory for VUSES.  */
 250
 251 static inline void
 252 free_vuses (vuse_optype *vuses)
 253 {
 254   if (*vuses)
 255     {
 256       unsigned int x;
 257       vuse_optype vuse = *vuses;
 258       for (x = 0; x < vuse->num_vuses; x++)
 259         delink_imm_use (&(vuse->vuses[x].imm_use));
 260       ggc_free (*vuses);
 261       *vuses = NULL;
 262     }
 263 }
 264
 265
 266 /* Free memory for V_MAY_DEFS.  */
 267
 268 static inline void
 269 free_v_may_defs (v_may_def_optype *v_may_defs)
 270 {
 271   if (*v_may_defs)
 272     {
 273       unsigned int x;
 274       v_may_def_optype v_may_def = *v_may_defs;
 275       for (x = 0; x < v_may_def->num_v_may_defs; x++)
 276         delink_imm_use (&(v_may_def->v_may_defs[x].imm_use));
 277       ggc_free (*v_may_defs);
 278       *v_may_defs = NULL;
 279     }
 280 }
 281
 282
 283 /* Free memory for V_MUST_DEFS.  */
 284
 285 static inline void
 286 free_v_must_defs (v_must_def_optype *v_must_defs)
 287 {
 288   if (*v_must_defs)
 289     {
 290       unsigned int x;
 291       v_must_def_optype v_must_def = *v_must_defs;
 292       for (x = 0; x < v_must_def->num_v_must_defs; x++)
 293         delink_imm_use (&(v_must_def->v_must_defs[x].imm_use));
 294       ggc_free (*v_must_defs);
 295       *v_must_defs = NULL;
 296     }
 297 }
 298
 299
 300 /* Initialize the operand cache routines.  */
 301
 302 void
 303 init_ssa_operands (void)
 304 {
 305   VARRAY_TREE_PTR_INIT (build_defs, 5, "build defs");
 306   VARRAY_TREE_PTR_INIT (build_uses, 10, "build uses");
 307   VARRAY_TREE_INIT (build_v_may_defs, 10, "build v_may_defs");
 308   VARRAY_TREE_INIT (build_vuses, 10, "build vuses");
 309   VARRAY_TREE_INIT (build_v_must_defs, 10, "build v_must_defs");
 310 }
 311
 312
 313 /* Dispose of anything required by the operand routines.  */
 314
 315 void
 316 fini_ssa_operands (void)
 317 {
 318   ggc_free (build_defs);
 319   ggc_free (build_uses);
 320   ggc_free (build_v_may_defs);
 321   ggc_free (build_vuses);
 322   ggc_free (build_v_must_defs);
 323   build_defs = NULL;
 324   build_uses = NULL;
 325   build_v_may_defs = NULL;
 326   build_vuses = NULL;
 327   build_v_must_defs = NULL;
 328   if (clobbered_v_may_defs)
 329     {
 330       ggc_free (clobbered_v_may_defs);
 331       ggc_free (clobbered_vuses);
 332       clobbered_v_may_defs = NULL;
 333       clobbered_vuses = NULL;
 334     }
 335   if (ro_call_vuses)
 336     {
 337       ggc_free (ro_call_vuses);
 338       ro_call_vuses = NULL;
 339     }
 340 }
 341
 342 /* Initialize V_USES index INDEX to VAL for STMT.  If OLD is present, preserve
 343    the position of the may-def in the immediate_use list.  */
 344
 345 static inline void
 346 initialize_vuse_operand (vuse_optype vuses, unsigned int index, tree val,
 347                          tree stmt, ssa_imm_use_t *old)
 348 {
 349   vuse_operand_type_t *ptr;
 350   ptr = &(vuses->vuses[index]);
 351   ptr->use = val;
 352   ptr->imm_use.use = &(ptr->use);
 353   if (old)
 354     relink_imm_use_stmt (&(ptr->imm_use), old, stmt);
 355   else
 356     link_imm_use_stmt (&(ptr->imm_use), ptr->use, stmt);
 357 }
 358
 359
 360 /* Initialize V_MAY_DEF_OPS index X to be DEF = MAY_DEF <USE> for STMT.  If
 361    OLD is present, preserve the position of the may-def in the immediate_use
 362    list.  */
 363
 364 static inline void
 365 initialize_v_may_def_operand (v_may_def_optype v_may_def_ops, unsigned int x,
 366                               tree def, tree use, tree stmt, ssa_imm_use_t *old)
 367 {
 368   v_def_use_operand_type_t *ptr;
 369   ptr = &(v_may_def_ops->v_may_defs[x]);
 370   ptr->def = def;
 371   ptr->use = use;
 372   ptr->imm_use.use = &(ptr->use);
 373   if (old)
 374     relink_imm_use_stmt (&(ptr->imm_use), old, stmt);
 375   else
 376     link_imm_use_stmt (&(ptr->imm_use), ptr->use, stmt);
 377 }
 378
 379
 380 /* Initialize V_MUST_DEF_OPS index X to be DEF = MUST_DEF <USE> for STMT.  If
 381    OLD is present, preserve the position of the may-def in the immediate_use
 382    list.  */
 383
 384 static inline void
 385 initialize_v_must_def_operand (v_must_def_optype v_must_def_ops, unsigned int x,
 386                               tree def, tree use, tree stmt, ssa_imm_use_t *old)
 387 {
 388   v_def_use_operand_type_t *ptr;
 389   ptr = &(v_must_def_ops->v_must_defs[x]);
 390   ptr->def = def;
 391   ptr->use = use;
 392   ptr->imm_use.use = &(ptr->use);
 393   if (old)
 394     relink_imm_use_stmt (&(ptr->imm_use), old, stmt);
 395   else
 396     link_imm_use_stmt (&(ptr->imm_use), ptr->use, stmt);
 397 }
 398
 399 /* All the finalize_ssa_* routines do the work required to turn the build_
 400    VARRAY into an operand_vector of the appropriate type.  The original vector,
 401    if any, is passed in for comparison and virtual SSA_NAME reuse.  If the
 402    old vector is reused, the pointer passed in is set to NULL so that
 403    the memory is not freed when the old operands are freed.  */
 404
 405 /* Return a new def operand vector for STMT, comparing to OLD_OPS_P.  */
 406
 407 static def_optype
 408 finalize_ssa_defs (def_optype *old_ops_p, tree stmt)
 409 {
 410   unsigned num, x;
 411   def_optype def_ops, old_ops;
 412   bool build_diff;
 413
 414   num = VARRAY_ACTIVE_SIZE (build_defs);
 415   if (num == 0)
 416     return NULL;
 417
 418   /* There should only be a single real definition per assignment.  */
 419   gcc_assert ((stmt && TREE_CODE (stmt) != MODIFY_EXPR) || num <= 1);
 420
 421   old_ops = *old_ops_p;
 422
 423   /* Compare old vector and new array.  */
 424   build_diff = true;
 425   if (stmt && old_ops && old_ops->num_defs == num)
 426     {
 427       build_diff = false;
 428       for (x = 0; x < num; x++)
 429         if (old_ops->defs[x].def != VARRAY_TREE_PTR (build_defs, x))
 430           {
 431             build_diff = true;
 432             break;
 433           }
 434     }
 435
 436   if (!build_diff)
 437     {
 438       def_ops = old_ops;
 439       *old_ops_p = NULL;
 440     }
 441   else
 442     {
 443       def_ops = allocate_def_optype (num);
 444       for (x = 0; x < num ; x++)
 445         def_ops->defs[x].def = VARRAY_TREE_PTR (build_defs, x);
 446     }
 447
 448   VARRAY_POP_ALL (build_defs);
 449
 450   return def_ops;
 451 }
 452
 453
 454 /* Make sure PTR is inn the correct immediate use list.  Since uses are simply
 455    pointers into the stmt TREE, there is no way of telling if anyone has
 456    changed what this pointer points to via TREE_OPERANDS (exp, 0) = <...>.
 457    THe contents are different, but the the pointer is still the same.  This
 458    routine will check to make sure PTR is in the correct list, and if it isn't
 459    put it in the correct list.  */
 460
 461 static inline void
 462 correct_use_link (ssa_imm_use_t *ptr, tree stmt)
 463 {
 464   ssa_imm_use_t *prev;
 465   tree root;
 466
 467   /*  Fold_stmt () may have changed the stmt pointers.  */
 468   if (ptr->stmt != stmt)
 469     ptr->stmt = stmt;
 470
 471   prev = ptr->prev;
 472   if (prev)
 473     {
 474       /* find the root, which has a non-NULL stmt, and a NULL use.  */
 475       while (prev->stmt == NULL || prev->use != NULL)
 476         prev = prev->prev;
 477       root = prev->stmt;
 478       if (root == *(ptr->use))
 479         return;
 480     }
 481   /* Its in the wrong list if we reach here.  */
 482   delink_imm_use (ptr);
 483   link_imm_use (ptr, *(ptr->use));
 484 }
 485
 486
 487 /* Return a new use operand vector for STMT, comparing to OLD_OPS_P.  */
 488
 489 static use_optype
 490 finalize_ssa_uses (use_optype *old_ops_p, tree stmt)
 491 {
 492   unsigned num, x, num_old, i;
 493   use_optype use_ops, old_ops;
 494   bool build_diff;
 495
 496   num = VARRAY_ACTIVE_SIZE (build_uses);
 497   if (num == 0)
 498     return NULL;
 499
 500 #ifdef ENABLE_CHECKING
 501   {
 502     unsigned x;
 503     /* If the pointer to the operand is the statement itself, something is
 504        wrong.  It means that we are pointing to a local variable (the
 505        initial call to get_stmt_operands does not pass a pointer to a
 506        statement).  */
 507     for (x = 0; x < num; x++)
 508       gcc_assert (*(VARRAY_TREE_PTR (build_uses, x)) != stmt);
 509   }
 510 #endif
 511   old_ops = *old_ops_p;
 512   num_old = ((stmt && old_ops) ? old_ops->num_uses : 0);
 513
 514   /* Check if the old vector and the new array are the same.  */
 515   build_diff = true;
 516   if (stmt && old_ops && num_old == num)
 517     {
 518       build_diff = false;
 519       for (x = 0; x < num; x++)
 520         {
 521           tree *var_p = VARRAY_TREE_PTR (build_uses, x);
 522           tree *node = old_ops->uses[x].use;
 523           /* Check the pointer values to see if they are the same. */
 524           if (node != var_p)
 525             {
 526               build_diff = true;
 527               break;
 528             }
 529         }
 530     }
 531
 532   if (!build_diff)
 533     {
 534       use_ops = old_ops;
 535       *old_ops_p = NULL;
 536       for (i = 0; i < num_old; i++)
 537         correct_use_link (&(use_ops->uses[i]), stmt);
 538     }
 539   else
 540     {
 541       use_ops = allocate_use_optype (num);
 542       for (x = 0; x < num ; x++)
 543         {
 544           tree *var = VARRAY_TREE_PTR (build_uses, x);
 545           use_ops->uses[x].use = var;
 546           for (i = 0; i < num_old; i++)
 547             {
 548               ssa_imm_use_t *ptr = &(old_ops->uses[i]);
 549               if (ptr->use == var)
 550                 {
 551                   relink_imm_use_stmt (&(use_ops->uses[x]), ptr, stmt);
 552                   correct_use_link (&(use_ops->uses[x]), stmt);
 553                   break;
 554                 }
 555             }
 556           if (i == num_old)
 557             link_imm_use_stmt (&(use_ops->uses[x]), *var, stmt);
 558         }
 559     }
 560   VARRAY_POP_ALL (build_uses);
 561
 562   return use_ops;
 563 }
 564
 565
 566 /* Return a new v_may_def operand vector for STMT, comparing to OLD_OPS_P.  */
 567
 568 static v_may_def_optype
 569 finalize_ssa_v_may_defs (v_may_def_optype *old_ops_p, tree stmt)
 570 {
 571   unsigned num, x, i, old_num;
 572   v_may_def_optype v_may_def_ops, old_ops;
 573   tree result, var;
 574   bool build_diff;
 575
 576   num = VARRAY_ACTIVE_SIZE (build_v_may_defs);
 577   if (num == 0)
 578     return NULL;
 579
 580   old_ops = *old_ops_p;
 581
 582   /* Check if the old vector and the new array are the same.  */
 583   build_diff = true;
 584   if (stmt && old_ops && old_ops->num_v_may_defs == num)
 585     {
 586       old_num = num;
 587       build_diff = false;
 588       for (x = 0; x < num; x++)
 589         {
 590           var = old_ops->v_may_defs[x].def;
 591           if (TREE_CODE (var) == SSA_NAME)
 592             var = SSA_NAME_VAR (var);
 593           if (var != VARRAY_TREE (build_v_may_defs, x))
 594             {
 595               build_diff = true;
 596               break;
 597             }
 598         }
 599     }
 600   else
 601     old_num = (old_ops ? old_ops->num_v_may_defs : 0);
 602
 603   if (!build_diff)
 604     {
 605       v_may_def_ops = old_ops;
 606       *old_ops_p = NULL;
 607       for (x = 0; x < num; x++)
 608         correct_use_link (&(v_may_def_ops->v_may_defs[x].imm_use), stmt);
 609     }
 610   else
 611     {
 612       v_may_def_ops = allocate_v_may_def_optype (num);
 613       for (x = 0; x < num; x++)
 614         {
 615           var = VARRAY_TREE (build_v_may_defs, x);
 616           /* Look for VAR in the old operands vector.  */
 617           for (i = 0; i < old_num; i++)
 618             {
 619               result = old_ops->v_may_defs[i].def;
 620               if (TREE_CODE (result) == SSA_NAME)
 621                 result = SSA_NAME_VAR (result);
 622               if (result == var)
 623                 {
 624                   initialize_v_may_def_operand (v_may_def_ops, x,
 625                                                 old_ops->v_may_defs[i].def,
 626                                                 old_ops->v_may_defs[i].use,
 627                                                 stmt,
 628                                                 &(old_ops->v_may_defs[i].imm_use));
 629                   break;
 630                 }
 631             }
 632           if (i == old_num)
 633             {
 634               initialize_v_may_def_operand (v_may_def_ops, x, var, var, stmt,
 635                                             NULL);
 636             }
 637         }
 638     }
 639
 640   /* Empty the V_MAY_DEF build vector after VUSES have been processed.  */
 641
 642   return v_may_def_ops;
 643 }
 644
 645
 646 /* Clear the in_list bits and empty the build array for v_may_defs.  */
 647
 648 static inline void
 649 cleanup_v_may_defs (void)
 650 {
 651   unsigned x, num;
 652   num = VARRAY_ACTIVE_SIZE (build_v_may_defs);
 653
 654   for (x = 0; x < num; x++)
 655     {
 656       tree t = VARRAY_TREE (build_v_may_defs, x);
 657       var_ann_t ann = var_ann (t);
 658       ann->in_v_may_def_list = 0;
 659     }
 660   VARRAY_POP_ALL (build_v_may_defs);
 661 }
 662
 663 /* Return a new vuse operand vector, comparing to OLD_OPS_P.  */
 664
 665 static vuse_optype
 666 finalize_ssa_vuses (vuse_optype *old_ops_p, tree stmt)
 667 {
 668   unsigned num, x, i, num_v_may_defs, old_num;
 669   vuse_optype vuse_ops, old_ops;
 670   bool build_diff;
 671
 672   num = VARRAY_ACTIVE_SIZE (build_vuses);
 673   if (num == 0)
 674     {
 675       cleanup_v_may_defs ();
 676       return NULL;
 677     }
 678
 679   /* Remove superfluous VUSE operands.  If the statement already has a
 680    V_MAY_DEF operation for a variable 'a', then a VUSE for 'a' is not
 681    needed because V_MAY_DEFs imply a VUSE of the variable.  For instance,
 682    suppose that variable 'a' is aliased:
 683
 684               # VUSE <a_2>
 685               # a_3 = V_MAY_DEF <a_2>
 686               a = a + 1;
 687
 688   The VUSE <a_2> is superfluous because it is implied by the V_MAY_DEF
 689   operation.  */
 690
 691   num_v_may_defs = VARRAY_ACTIVE_SIZE (build_v_may_defs);
 692
 693   if (num_v_may_defs > 0)
 694     {
 695       size_t i;
 696       tree vuse;
 697       for (i = 0; i < VARRAY_ACTIVE_SIZE (build_vuses); i++)
 698         {
 699           vuse = VARRAY_TREE (build_vuses, i);
 700           if (TREE_CODE (vuse) != SSA_NAME)
 701             {
 702               var_ann_t ann = var_ann (vuse);
 703               ann->in_vuse_list = 0;
 704               if (ann->in_v_may_def_list)
 705                 {
 706                   /* If we found a useless VUSE operand, remove it from the
 707                      operand array by replacing it with the last active element
 708                      in the operand array (unless the useless VUSE was the
 709                      last operand, in which case we simply remove it.  */
 710                   if (i != VARRAY_ACTIVE_SIZE (build_vuses) - 1)
 711                     {
 712                       VARRAY_TREE (build_vuses, i)
 713                         = VARRAY_TREE (build_vuses,
 714                                        VARRAY_ACTIVE_SIZE (build_vuses) - 1);
 715                     }
 716                   VARRAY_POP (build_vuses);
 717
 718                   /* We want to rescan the element at this index, unless
 719                      this was the last element, in which case the loop
 720                      terminates.  */
 721                   i--;
 722                 }
 723             }
 724         }
 725     }
 726   else
 727     /* Clear out the in_list bits.  */
 728     for (x = 0; x < num; x++)
 729       {
 730         tree t = VARRAY_TREE (build_vuses, x);
 731         if (TREE_CODE (t) != SSA_NAME)
 732           {
 733             var_ann_t ann = var_ann (t);
 734             ann->in_vuse_list = 0;
 735           }
 736       }
 737
 738
 739   num = VARRAY_ACTIVE_SIZE (build_vuses);
 740   /* We could have reduced the size to zero now, however.  */
 741   if (num == 0)
 742     {
 743       cleanup_v_may_defs ();
 744       return NULL;
 745     }
 746
 747   old_ops = *old_ops_p;
 748
 749   /* Determine whether vuses is the same as the old vector.  */
 750   build_diff = true;
 751   if (stmt && old_ops && old_ops->num_vuses == num)
 752     {
 753       old_num = num;
 754       build_diff = false;
 755       for (x = 0; x < num ; x++)
 756         {
 757           tree v;
 758           v = old_ops->vuses[x].use;
 759           if (TREE_CODE (v) == SSA_NAME)
 760             v = SSA_NAME_VAR (v);
 761           if (v != VARRAY_TREE (build_vuses, x))
 762             {
 763               build_diff = true;
 764               break;
 765             }
 766         }
 767     }
 768   else
 769     old_num = (old_ops ? old_ops->num_vuses : 0);
 770
 771   if (!build_diff)
 772     {
 773       vuse_ops = old_ops;
 774       *old_ops_p = NULL;
 775       for (x = 0; x < num; x++)
 776         correct_use_link (&(vuse_ops->vuses[x].imm_use), stmt);
 777     }
 778   else
 779     {
 780       vuse_ops = allocate_vuse_optype (num);
 781       for (x = 0; x < num; x++)
 782         {
 783           tree result, var = VARRAY_TREE (build_vuses, x);
 784           /* Look for VAR in the old vector, and use that SSA_NAME.  */
 785           for (i = 0; i < old_num; i++)
 786             {
 787               result = old_ops->vuses[i].use;
 788               if (TREE_CODE (result) == SSA_NAME)
 789                 result = SSA_NAME_VAR (result);
 790               if (result == var)
 791                 {
 792                   initialize_vuse_operand (vuse_ops, x, old_ops->vuses[i].use,
 793                                            stmt, &(old_ops->vuses[i].imm_use));
 794                   break;
 795                 }
 796             }
 797           if (i == old_num)
 798             initialize_vuse_operand (vuse_ops, x, var, stmt, NULL);
 799         }
 800     }
 801
 802   /* The v_may_def build vector wasn't freed because we needed it here.
 803      Free it now with the vuses build vector.  */
 804   VARRAY_POP_ALL (build_vuses);
 805   cleanup_v_may_defs ();
 806
 807   return vuse_ops;
 808 }
 809
 810 /* Return a new v_must_def operand vector for STMT, comparing to OLD_OPS_P.  */
 811
 812 static v_must_def_optype
 813 finalize_ssa_v_must_defs (v_must_def_optype *old_ops_p, tree stmt)
 814 {
 815   unsigned num, x, i, old_num = 0;
 816   v_must_def_optype v_must_def_ops, old_ops;
 817   tree result, var;
 818   bool build_diff;
 819
 820   num = VARRAY_ACTIVE_SIZE (build_v_must_defs);
 821   if (num == 0)
 822     return NULL;
 823
 824   /* In the presence of subvars, there may be more than one V_MUST_DEF per
 825      statement (one for each subvar).  It is a bit expensive to verify that
 826      all must-defs in a statement belong to subvars if there is more than one
 827      MUST-def, so we don't do it.  Suffice to say, if you reach here without
 828      having subvars, and have num >1, you have hit a bug. */
 829
 830
 831   old_ops = *old_ops_p;
 832
 833   /* Check if the old vector and the new array are the same.  */
 834   build_diff = true;
 835   if (stmt && old_ops && old_ops->num_v_must_defs == num)
 836     {
 837       old_num = num;
 838       build_diff = false;
 839       for (x = 0; x < num; x++)
 840         {
 841           tree var = old_ops->v_must_defs[x].def;
 842           if (TREE_CODE (var) == SSA_NAME)
 843             var = SSA_NAME_VAR (var);
 844           if (var != VARRAY_TREE (build_v_must_defs, x))
 845             {
 846               build_diff = true;
 847               break;
 848             }
 849         }
 850     }
 851   else
 852     old_num = (old_ops ? old_ops->num_v_must_defs : 0);
 853
 854   if (!build_diff)
 855     {
 856       v_must_def_ops = old_ops;
 857       *old_ops_p = NULL;
 858       for (x = 0; x < num; x++)
 859         correct_use_link (&(v_must_def_ops->v_must_defs[x].imm_use), stmt);
 860     }
 861   else
 862     {
 863       v_must_def_ops = allocate_v_must_def_optype (num);
 864       for (x = 0; x < num ; x++)
 865         {
 866           var = VARRAY_TREE (build_v_must_defs, x);
 867           /* Look for VAR in the original vector.  */
 868           for (i = 0; i < old_num; i++)
 869             {
 870               result = old_ops->v_must_defs[i].def;
 871               if (TREE_CODE (result) == SSA_NAME)
 872                 result = SSA_NAME_VAR (result);
 873               if (result == var)
 874                 {
 875                   initialize_v_must_def_operand (v_must_def_ops, x,
 876                                                  old_ops->v_must_defs[i].def,
 877                                                  old_ops->v_must_defs[i].use,
 878                                                  stmt,
 879                                                  &(old_ops->v_must_defs[i].imm_use));
 880                   break;
 881                 }
 882             }
 883           if (i == old_num)
 884             {
 885               initialize_v_must_def_operand (v_must_def_ops, x, var, var, stmt,
 886                                              NULL);
 887             }
 888         }
 889     }
 890   VARRAY_POP_ALL (build_v_must_defs);
 891
 892   return v_must_def_ops;
 893 }
 894
 895
 896 /* Finalize all the build vectors, fill the new ones into INFO.  */
 897
 898 static inline void
 899 finalize_ssa_stmt_operands (tree stmt, stmt_operands_p old_ops,
 900                             stmt_operands_p new_ops)
 901 {
 902   new_ops->def_ops = finalize_ssa_defs (&(old_ops->def_ops), stmt);
 903   new_ops->use_ops = finalize_ssa_uses (&(old_ops->use_ops), stmt);
 904   new_ops->v_must_def_ops
 905     = finalize_ssa_v_must_defs (&(old_ops->v_must_def_ops), stmt);
 906   new_ops->v_may_def_ops
 907     = finalize_ssa_v_may_defs (&(old_ops->v_may_def_ops), stmt);
 908   new_ops->vuse_ops = finalize_ssa_vuses (&(old_ops->vuse_ops), stmt);
 909 }
 910
 911
 912 /* Start the process of building up operands vectors in INFO.  */
 913
 914 static inline void
 915 start_ssa_stmt_operands (void)
 916 {
 917   gcc_assert (VARRAY_ACTIVE_SIZE (build_defs) == 0);
 918   gcc_assert (VARRAY_ACTIVE_SIZE (build_uses) == 0);
 919   gcc_assert (VARRAY_ACTIVE_SIZE (build_vuses) == 0);
 920   gcc_assert (VARRAY_ACTIVE_SIZE (build_v_may_defs) == 0);
 921   gcc_assert (VARRAY_ACTIVE_SIZE (build_v_must_defs) == 0);
 922 }
 923
 924
 925 /* Add DEF_P to the list of pointers to operands.  */
 926
 927 static inline void
 928 append_def (tree *def_p)
 929 {
 930   VARRAY_PUSH_TREE_PTR (build_defs, def_p);
 931 }
 932
 933
 934 /* Add USE_P to the list of pointers to operands.  */
 935
 936 static inline void
 937 append_use (tree *use_p)
 938 {
 939   VARRAY_PUSH_TREE_PTR (build_uses, use_p);
 940 }
 941
 942
 943 /* Add a new virtual may def for variable VAR to the build array.  */
 944
 945 static inline void
 946 append_v_may_def (tree var)
 947 {
 948   var_ann_t ann = get_var_ann (var);
 949
 950   /* Don't allow duplicate entries.  */
 951   if (ann->in_v_may_def_list)
 952     return;
 953   ann->in_v_may_def_list = 1;
 954
 955   VARRAY_PUSH_TREE (build_v_may_defs, var);
 956 }
 957
 958
 959 /* Add VAR to the list of virtual uses.  */
 960
 961 static inline void
 962 append_vuse (tree var)
 963 {
 964
 965   /* Don't allow duplicate entries.  */
 966   if (TREE_CODE (var) != SSA_NAME)
 967     {
 968       var_ann_t ann = get_var_ann (var);
 969
 970       if (ann->in_vuse_list || ann->in_v_may_def_list)
 971         return;
 972       ann->in_vuse_list = 1;
 973     }
 974
 975   VARRAY_PUSH_TREE (build_vuses, var);
 976 }
 977
 978
 979 /* Add VAR to the list of virtual must definitions for INFO.  */
 980
 981 static inline void
 982 append_v_must_def (tree var)
 983 {
 984   unsigned i;
 985
 986   /* Don't allow duplicate entries.  */
 987   for (i = 0; i < VARRAY_ACTIVE_SIZE (build_v_must_defs); i++)
 988     if (var == VARRAY_TREE (build_v_must_defs, i))
 989       return;
 990
 991   VARRAY_PUSH_TREE (build_v_must_defs, var);
 992 }
 993
 994
 995 /* Parse STMT looking for operands.  OLD_OPS is the original stmt operand
 996    cache for STMT, if it exested before.  When fniished, the various build_*
 997    operand vectors will have potential operands. in them.  */
 998
 999 static void
1000 parse_ssa_operands (tree stmt)
1001 {
1002   enum tree_code code;
1003
1004   code = TREE_CODE (stmt);
1005   switch (code)
1006     {
1007     case MODIFY_EXPR:
1008       /* First get operands from the RHS.  For the LHS, we use a V_MAY_DEF if
1009          either only part of LHS is modified or if the RHS might throw,
1010          otherwise, use V_MUST_DEF.
1011
1012          ??? If it might throw, we should represent somehow that it is killed
1013          on the fallthrough path.  */
1014       {
1015         tree lhs = TREE_OPERAND (stmt, 0);
1016         int lhs_flags = opf_is_def;
1017
1018         get_expr_operands (stmt, &TREE_OPERAND (stmt, 1), opf_none);
1019
1020         /* If the LHS is a VIEW_CONVERT_EXPR, it isn't changing whether
1021            or not the entire LHS is modified; that depends on what's
1022            inside the VIEW_CONVERT_EXPR.  */
1023         if (TREE_CODE (lhs) == VIEW_CONVERT_EXPR)
1024           lhs = TREE_OPERAND (lhs, 0);
1025
1026         if (TREE_CODE (lhs) != ARRAY_REF && TREE_CODE (lhs) != ARRAY_RANGE_REF
1027             && TREE_CODE (lhs) != BIT_FIELD_REF
1028             && TREE_CODE (lhs) != REALPART_EXPR
1029             && TREE_CODE (lhs) != IMAGPART_EXPR)
1030           lhs_flags |= opf_kill_def;
1031
1032         get_expr_operands (stmt, &TREE_OPERAND (stmt, 0), lhs_flags);
1033       }
1034       break;
1035
1036     case COND_EXPR:
1037       get_expr_operands (stmt, &COND_EXPR_COND (stmt), opf_none);
1038       break;
1039
1040     case SWITCH_EXPR:
1041       get_expr_operands (stmt, &SWITCH_COND (stmt), opf_none);
1042       break;
1043
1044     case ASM_EXPR:
1045       get_asm_expr_operands (stmt);
1046       break;
1047
1048     case RETURN_EXPR:
1049       get_expr_operands (stmt, &TREE_OPERAND (stmt, 0), opf_none);
1050       break;
1051
1052     case GOTO_EXPR:
1053       get_expr_operands (stmt, &GOTO_DESTINATION (stmt), opf_none);
1054       break;
1055
1056     case LABEL_EXPR:
1057       get_expr_operands (stmt, &LABEL_EXPR_LABEL (stmt), opf_none);
1058       break;
1059
1060       /* These nodes contain no variable references.  */
1061     case BIND_EXPR:
1062     case CASE_LABEL_EXPR:
1063     case TRY_CATCH_EXPR:
1064     case TRY_FINALLY_EXPR:
1065     case EH_FILTER_EXPR:
1066     case CATCH_EXPR:
1067     case RESX_EXPR:
1068       break;
1069
1070     default:
1071       /* Notice that if get_expr_operands tries to use &STMT as the operand
1072          pointer (which may only happen for USE operands), we will abort in
1073          append_use.  This default will handle statements like empty
1074          statements, or CALL_EXPRs that may appear on the RHS of a statement
1075          or as statements themselves.  */
1076       get_expr_operands (stmt, &stmt, opf_none);
1077       break;
1078     }
1079 }
1080
1081 /* Create an operands cache for STMT, returning it in NEW_OPS. OLD_OPS are the
1082    original operands, and if ANN is non-null, appropriate stmt flags are set
1083    in the stmt's annotation.  If ANN is NULL, this is not considered a "real"
1084    stmt, and none of the operands will be entered into their respective
1085    immediate uses tables.  This is to allow stmts to be processed when they
1086    are not actually in the CFG.
1087
1088    Note that some fields in old_ops may change to NULL, although none of the
1089    memory they originally pointed to will be destroyed.  It is appropriate
1090    to call free_stmt_operands() on the value returned in old_ops.
1091
1092    The rationale for this: Certain optimizations wish to examine the difference
1093    between new_ops and old_ops after processing.  If a set of operands don't
1094    change, new_ops will simply assume the pointer in old_ops, and the old_ops
1095    pointer will be set to NULL, indicating no memory needs to be cleared.
1096    Usage might appear something like:
1097
1098        old_ops_copy = old_ops = stmt_ann(stmt)->operands;
1099        build_ssa_operands (stmt, NULL, &old_ops, &new_ops);
1100           <* compare old_ops_copy and new_ops *>
1101        free_ssa_operands (old_ops);                                     */
1102
1103 static void
1104 build_ssa_operands (tree stmt, stmt_ann_t ann, stmt_operands_p old_ops,
1105                     stmt_operands_p new_ops)
1106 {
1107   tree_ann_t saved_ann = stmt->common.ann;
1108
1109   /* Replace stmt's annotation with the one passed in for the duration
1110      of the operand building process.  This allows "fake" stmts to be built
1111      and not be included in other data structures which can be built here.  */
1112   stmt->common.ann = (tree_ann_t) ann;
1113
1114   parse_old_ops = old_ops;
1115
1116   /* Initially assume that the statement has no volatile operands, nor
1117      makes aliased loads or stores.  */
1118   if (ann)
1119     {
1120       ann->has_volatile_ops = false;
1121       ann->makes_aliased_stores = false;
1122       ann->makes_aliased_loads = false;
1123     }
1124
1125   start_ssa_stmt_operands ();
1126
1127   parse_ssa_operands (stmt);
1128
1129   parse_old_ops = NULL;
1130
1131   if (ann)
1132     finalize_ssa_stmt_operands (stmt, old_ops, new_ops);
1133   else
1134     finalize_ssa_stmt_operands (NULL, old_ops, new_ops);
1135   stmt->common.ann = saved_ann;
1136 }
1137
1138
1139 /* Free any operands vectors in OPS.  */
1140
1141 static void
1142 free_ssa_operands (stmt_operands_p ops)
1143 {
1144   if (ops->def_ops)
1145     free_defs (&(ops->def_ops));
1146   if (ops->use_ops)
1147     free_uses (&(ops->use_ops));
1148   if (ops->vuse_ops)
1149     free_vuses (&(ops->vuse_ops));
1150   if (ops->v_may_def_ops)
1151     free_v_may_defs (&(ops->v_may_def_ops));
1152   if (ops->v_must_def_ops)
1153     free_v_must_defs (&(ops->v_must_def_ops));
1154 }
1155
1156
1157 /* Swap operands EXP0 and EXP1 in STMT.  */
1158
1159 static void
1160 swap_tree_operands (tree *exp0, tree *exp1)
1161 {
1162   tree op0, op1;
1163   op0 = *exp0;
1164   op1 = *exp1;
1165
1166   /* If the operand cache is active, attempt to preserve the relative positions
1167      of these two operands in their respective immediate use lists.  */
1168   if (build_defs != NULL && op0 != op1 && parse_old_ops != NULL)
1169     {
1170       unsigned x, use0, use1;
1171       use_optype uses = parse_old_ops->use_ops;
1172       use0 = use1 = NUM_USES (uses);
1173       /* Find the 2 operands in the cache, if they are there.  */
1174       for (x = 0; x < NUM_USES (uses); x++)
1175         if (USE_OP_PTR (uses, x)->use == exp0)
1176           {
1177             use0 = x;
1178             break;
1179           }
1180       for (x = 0; x < NUM_USES (uses); x++)
1181         if (USE_OP_PTR (uses, x)->use == exp1)
1182           {
1183             use1 = x;
1184             break;
1185           }
1186       /* If both uses don't have operand entries, there isnt much we can do
1187          at this point. Presumably we dont need to worry about it.  */
1188       if (use0 != NUM_USES (uses) && use1 != NUM_USES (uses))
1189         {
1190           tree *tmp = USE_OP_PTR (uses, use1)->use;
1191           gcc_assert (use0 != use1);
1192
1193           USE_OP_PTR (uses, use1)->use = USE_OP_PTR (uses, use0)->use;
1194           USE_OP_PTR (uses, use0)->use = tmp;
1195         }
1196     }
1197
1198   /* Now swap the data.  */
1199   *exp0 = op1;
1200   *exp1 = op0;
1201 }
1202
1203 /* Get the operands of statement STMT.  Note that repeated calls to
1204    get_stmt_operands for the same statement will do nothing until the
1205    statement is marked modified by a call to mark_stmt_modified().  */
1206
1207 void
1208 update_stmt_operands (tree stmt)
1209 {
1210   stmt_ann_t ann;
1211   stmt_operands_t old_operands;
1212
1213   /* If get_stmt_operands is called before SSA is initialized, dont
1214   do anything.  */
1215   if (build_defs == NULL)
1216     return;
1217   /* The optimizers cannot handle statements that are nothing but a
1218      _DECL.  This indicates a bug in the gimplifier.  */
1219   gcc_assert (!SSA_VAR_P (stmt));
1220
1221   ann = get_stmt_ann (stmt);
1222
1223   gcc_assert (ann->modified);
1224
1225   timevar_push (TV_TREE_OPS);
1226
1227   old_operands = ann->operands;
1228   memset (&(ann->operands), 0, sizeof (stmt_operands_t));
1229
1230   build_ssa_operands (stmt, ann, &old_operands, &(ann->operands));
1231   free_ssa_operands (&old_operands);
1232
1233   /* Clear the modified bit for STMT.  Subsequent calls to
1234      get_stmt_operands for this statement will do nothing until the
1235      statement is marked modified by a call to mark_stmt_modified().  */
1236   ann->modified = 0;
1237
1238   timevar_pop (TV_TREE_OPS);
1239 }
1240
1241
1242 /* Recursively scan the expression pointed by EXPR_P in statement referred to
1243    by INFO.  FLAGS is one of the OPF_* constants modifying how to interpret the
1244    operands found.  */
1245
1246 static void
1247 get_expr_operands (tree stmt, tree *expr_p, int flags)
1248 {
1249   enum tree_code code;
1250   enum tree_code_class class;
1251   tree expr = *expr_p;
1252   stmt_ann_t s_ann = stmt_ann (stmt);
1253
1254   if (expr == NULL)
1255     return;
1256
1257   code = TREE_CODE (expr);
1258   class = TREE_CODE_CLASS (code);
1259
1260   switch (code)
1261     {
1262     case ADDR_EXPR:
1263       /* We could have the address of a component, array member,
1264          etc which has interesting variable references.  */
1265       /* Taking the address of a variable does not represent a
1266          reference to it, but the fact that the stmt takes its address will be
1267          of interest to some passes (e.g. alias resolution).  */
1268       add_stmt_operand (expr_p, s_ann, 0);
1269
1270       /* If the address is invariant, there may be no interesting variable
1271          references inside.  */
1272       if (is_gimple_min_invariant (expr))
1273         return;
1274
1275       /* There should be no VUSEs created, since the referenced objects are
1276          not really accessed.  The only operands that we should find here
1277          are ARRAY_REF indices which will always be real operands (GIMPLE
1278          does not allow non-registers as array indices).  */
1279       flags |= opf_no_vops;
1280
1281       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
1282       return;
1283
1284     case SSA_NAME:
1285     case VAR_DECL:
1286     case PARM_DECL:
1287     case RESULT_DECL:
1288     case CONST_DECL:
1289       {
1290         subvar_t svars;
1291
1292         /* Add the subvars for a variable if it has subvars, to DEFS or USES.
1293            Otherwise, add the variable itself.
1294            Whether it goes to USES or DEFS depends on the operand flags.  */
1295         if (var_can_have_subvars (expr)
1296             && (svars = get_subvars_for_var (expr)))
1297           {
1298             subvar_t sv;
1299             for (sv = svars; sv; sv = sv->next)
1300               add_stmt_operand (&sv->var, s_ann, flags);
1301           }
1302         else
1303           {
1304             add_stmt_operand (expr_p, s_ann, flags);
1305           }
1306         return;
1307       }
1308     case MISALIGNED_INDIRECT_REF:
1309       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
1310       /* fall through */
1311
1312     case ALIGN_INDIRECT_REF:
1313     case INDIRECT_REF:
1314       get_indirect_ref_operands (stmt, expr, flags);
1315       return;
1316
1317     case ARRAY_REF:
1318     case ARRAY_RANGE_REF:
1319       /* Treat array references as references to the virtual variable
1320          representing the array.  The virtual variable for an ARRAY_REF
1321          is the VAR_DECL for the array.  */
1322
1323       /* Add the virtual variable for the ARRAY_REF to VDEFS or VUSES
1324          according to the value of IS_DEF.  Recurse if the LHS of the
1325          ARRAY_REF node is not a regular variable.  */
1326       if (SSA_VAR_P (TREE_OPERAND (expr, 0)))
1327         add_stmt_operand (expr_p, s_ann, flags);
1328       else
1329         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
1330
1331       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none);
1332       get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
1333       get_expr_operands (stmt, &TREE_OPERAND (expr, 3), opf_none);
1334       return;
1335
1336     case COMPONENT_REF:
1337     case REALPART_EXPR:
1338     case IMAGPART_EXPR:
1339       {
1340         tree ref;
1341         HOST_WIDE_INT offset, size;
1342         /* This component ref becomes an access to all of the subvariables
1343            it can touch,  if we can determine that, but *NOT* the real one.
1344            If we can't determine which fields we could touch, the recursion
1345            will eventually get to a variable and add *all* of its subvars, or
1346            whatever is the minimum correct subset.  */
1347
1348         ref = okay_component_ref_for_subvars (expr, &offset, &size);
1349         if (ref)
1350           {
1351             subvar_t svars = get_subvars_for_var (ref);
1352             subvar_t sv;
1353             for (sv = svars; sv; sv = sv->next)
1354               {
1355                 bool exact;
1356                 if (overlap_subvar (offset, size, sv, &exact))
1357                   {
1358                     if (exact)
1359                       flags &= ~opf_kill_def;
1360                     add_stmt_operand (&sv->var, s_ann, flags);
1361                   }
1362               }
1363           }
1364         else
1365           get_expr_operands (stmt, &TREE_OPERAND (expr, 0),
1366                              flags & ~opf_kill_def);
1367
1368         if (code == COMPONENT_REF)
1369           get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
1370         return;
1371       }
1372     case WITH_SIZE_EXPR:
1373       /* WITH_SIZE_EXPR is a pass-through reference to its first argument,
1374          and an rvalue reference to its second argument.  */
1375       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none);
1376       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
1377       return;
1378
1379     case CALL_EXPR:
1380       get_call_expr_operands (stmt, expr);
1381       return;
1382
1383     case COND_EXPR:
1384     case VEC_COND_EXPR:
1385       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none);
1386       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none);
1387       get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
1388       return;
1389
1390     case MODIFY_EXPR:
1391       {
1392         int subflags;
1393         tree op;
1394
1395         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none);
1396
1397         op = TREE_OPERAND (expr, 0);
1398         if (TREE_CODE (op) == WITH_SIZE_EXPR)
1399           op = TREE_OPERAND (expr, 0);
1400         if (TREE_CODE (op) == ARRAY_REF
1401             || TREE_CODE (op) == ARRAY_RANGE_REF
1402             || TREE_CODE (op) == REALPART_EXPR
1403             || TREE_CODE (op) == IMAGPART_EXPR)
1404           subflags = opf_is_def;
1405         else
1406           subflags = opf_is_def | opf_kill_def;
1407
1408         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), subflags);
1409         return;
1410       }
1411
1412     case CONSTRUCTOR:
1413       {
1414         /* General aggregate CONSTRUCTORs have been decomposed, but they
1415            are still in use as the COMPLEX_EXPR equivalent for vectors.  */
1416
1417         tree t;
1418         for (t = TREE_OPERAND (expr, 0); t ; t = TREE_CHAIN (t))
1419           get_expr_operands (stmt, &TREE_VALUE (t), opf_none);
1420
1421         return;
1422       }
1423
1424     case TRUTH_NOT_EXPR:
1425     case BIT_FIELD_REF:
1426     case VIEW_CONVERT_EXPR:
1427     do_unary:
1428       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
1429       return;
1430
1431     case TRUTH_AND_EXPR:
1432     case TRUTH_OR_EXPR:
1433     case TRUTH_XOR_EXPR:
1434     case COMPOUND_EXPR:
1435     case OBJ_TYPE_REF:
1436     do_binary:
1437       {
1438         tree op0 = TREE_OPERAND (expr, 0);
1439         tree op1 = TREE_OPERAND (expr, 1);
1440
1441         /* If it would be profitable to swap the operands, then do so to
1442            canonicalize the statement, enabling better optimization.
1443
1444            By placing canonicalization of such expressions here we
1445            transparently keep statements in canonical form, even
1446            when the statement is modified.  */
1447         if (tree_swap_operands_p (op0, op1, false))
1448           {
1449             /* For relationals we need to swap the operands
1450                and change the code.  */
1451             if (code == LT_EXPR
1452                 || code == GT_EXPR
1453                 || code == LE_EXPR
1454                 || code == GE_EXPR)
1455               {
1456                 TREE_SET_CODE (expr, swap_tree_comparison (code));
1457                 swap_tree_operands (&TREE_OPERAND (expr, 0),
1458                                     &TREE_OPERAND (expr, 1));
1459               }
1460
1461             /* For a commutative operator we can just swap the operands.  */
1462             else if (commutative_tree_code (code))
1463               {
1464                 swap_tree_operands (&TREE_OPERAND (expr, 0),
1465                                     &TREE_OPERAND (expr, 1));
1466               }
1467           }
1468
1469         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
1470         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
1471         return;
1472       }
1473
1474     case REALIGN_LOAD_EXPR:
1475       {
1476         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
1477         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
1478         get_expr_operands (stmt, &TREE_OPERAND (expr, 2), flags);
1479         return;
1480       }
1481
1482     case BLOCK:
1483     case FUNCTION_DECL:
1484     case EXC_PTR_EXPR:
1485     case FILTER_EXPR:
1486     case LABEL_DECL:
1487       /* Expressions that make no memory references.  */
1488       return;
1489
1490     default:
1491       if (class == tcc_unary)
1492         goto do_unary;
1493       if (class == tcc_binary || class == tcc_comparison)
1494         goto do_binary;
1495       if (class == tcc_constant || class == tcc_type)
1496         return;
1497     }
1498
1499   /* If we get here, something has gone wrong.  */
1500 #ifdef ENABLE_CHECKING
1501   fprintf (stderr, "unhandled expression in get_expr_operands():\n");
1502   debug_tree (expr);
1503   fputs ("\n", stderr);
1504   internal_error ("internal error");
1505 #endif
1506   gcc_unreachable ();
1507 }
1508
1509
1510 /* Scan operands in the ASM_EXPR stmt referred to in INFO.  */
1511
1512 static void
1513 get_asm_expr_operands (tree stmt)
1514 {
1515   stmt_ann_t s_ann = stmt_ann (stmt);
1516   int noutputs = list_length (ASM_OUTPUTS (stmt));
1517   const char **oconstraints
1518     = (const char **) alloca ((noutputs) * sizeof (const char *));
1519   int i;
1520   tree link;
1521   const char *constraint;
1522   bool allows_mem, allows_reg, is_inout;
1523
1524   for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
1525     {
1526       oconstraints[i] = constraint
1527         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1528       parse_output_constraint (&constraint, i, 0, 0,
1529           &allows_mem, &allows_reg, &is_inout);
1530
1531       /* This should have been split in gimplify_asm_expr.  */
1532       gcc_assert (!allows_reg || !is_inout);
1533
1534       /* Memory operands are addressable.  Note that STMT needs the
1535          address of this operand.  */
1536       if (!allows_reg && allows_mem)
1537         {
1538           tree t = get_base_address (TREE_VALUE (link));
1539           if (t && DECL_P (t))
1540             note_addressable (t, s_ann);
1541         }
1542
1543       get_expr_operands (stmt, &TREE_VALUE (link), opf_is_def);
1544     }
1545
1546   for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
1547     {
1548       constraint
1549         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1550       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1551           oconstraints, &allows_mem, &allows_reg);
1552
1553       /* Memory operands are addressable.  Note that STMT needs the
1554          address of this operand.  */
1555       if (!allows_reg && allows_mem)
1556         {
1557           tree t = get_base_address (TREE_VALUE (link));
1558           if (t && DECL_P (t))
1559             note_addressable (t, s_ann);
1560         }
1561
1562       get_expr_operands (stmt, &TREE_VALUE (link), 0);
1563     }
1564
1565
1566   /* Clobber memory for asm ("" : : : "memory");  */
1567   for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
1568     if (strcmp (TREE_STRING_POINTER (TREE_VALUE (link)), "memory") == 0)
1569       {
1570         unsigned i;
1571         bitmap_iterator bi;
1572
1573         /* Clobber all call-clobbered variables (or .GLOBAL_VAR if we
1574            decided to group them).  */
1575         if (global_var)
1576           add_stmt_operand (&global_var, s_ann, opf_is_def);
1577         else
1578           EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
1579               {
1580                 tree var = referenced_var (i);
1581                 add_stmt_operand (&var, s_ann, opf_is_def);
1582               }
1583
1584         /* Now clobber all addressables.  */
1585         EXECUTE_IF_SET_IN_BITMAP (addressable_vars, 0, i, bi)
1586             {
1587               tree var = referenced_var (i);
1588
1589               /* Subvars are explicitly represented in this list, so
1590                  we don't need the original to be added to the clobber
1591                  ops, but the original *will* be in this list because
1592                  we keep the addressability of the original
1593                  variable up-to-date so we don't screw up the rest of
1594                  the backend.  */
1595               if (var_can_have_subvars (var)
1596                   && get_subvars_for_var (var) != NULL)
1597                 continue;
1598
1599               add_stmt_operand (&var, s_ann, opf_is_def);
1600             }
1601
1602         break;
1603       }
1604 }
1605
1606 /* A subroutine of get_expr_operands to handle INDIRECT_REF,
1607    ALIGN_INDIRECT_REF and MISALIGNED_INDIRECT_REF.  */
1608
1609 static void
1610 get_indirect_ref_operands (tree stmt, tree expr, int flags)
1611 {
1612   tree *pptr = &TREE_OPERAND (expr, 0);
1613   tree ptr = *pptr;
1614   stmt_ann_t s_ann = stmt_ann (stmt);
1615
1616   /* Stores into INDIRECT_REF operands are never killing definitions.  */
1617   flags &= ~opf_kill_def;
1618
1619   if (SSA_VAR_P (ptr))
1620     {
1621       struct ptr_info_def *pi = NULL;
1622
1623       /* If PTR has flow-sensitive points-to information, use it.  */
1624       if (TREE_CODE (ptr) == SSA_NAME
1625           && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1626           && pi->name_mem_tag)
1627         {
1628           /* PTR has its own memory tag.  Use it.  */
1629           add_stmt_operand (&pi->name_mem_tag, s_ann, flags);
1630         }
1631       else
1632         {
1633           /* If PTR is not an SSA_NAME or it doesn't have a name
1634              tag, use its type memory tag.  */
1635           var_ann_t v_ann;
1636
1637           /* If we are emitting debugging dumps, display a warning if
1638              PTR is an SSA_NAME with no flow-sensitive alias
1639              information.  That means that we may need to compute
1640              aliasing again.  */
1641           if (dump_file
1642               && TREE_CODE (ptr) == SSA_NAME
1643               && pi == NULL)
1644             {
1645               fprintf (dump_file,
1646                   "NOTE: no flow-sensitive alias info for ");
1647               print_generic_expr (dump_file, ptr, dump_flags);
1648               fprintf (dump_file, " in ");
1649               print_generic_stmt (dump_file, stmt, dump_flags);
1650             }
1651
1652           if (TREE_CODE (ptr) == SSA_NAME)
1653             ptr = SSA_NAME_VAR (ptr);
1654           v_ann = var_ann (ptr);
1655           if (v_ann->type_mem_tag)
1656             add_stmt_operand (&v_ann->type_mem_tag, s_ann, flags);
1657         }
1658     }
1659
1660   /* If a constant is used as a pointer, we can't generate a real
1661      operand for it but we mark the statement volatile to prevent
1662      optimizations from messing things up.  */
1663   else if (TREE_CODE (ptr) == INTEGER_CST)
1664     {
1665       if (s_ann)
1666         s_ann->has_volatile_ops = true;
1667       return;
1668     }
1669
1670   /* Everything else *should* have been folded elsewhere, but users
1671      are smarter than we in finding ways to write invalid code.  We
1672      cannot just abort here.  If we were absolutely certain that we
1673      do handle all valid cases, then we could just do nothing here.
1674      That seems optimistic, so attempt to do something logical... */
1675   else if ((TREE_CODE (ptr) == PLUS_EXPR || TREE_CODE (ptr) == MINUS_EXPR)
1676            && TREE_CODE (TREE_OPERAND (ptr, 0)) == ADDR_EXPR
1677            && TREE_CODE (TREE_OPERAND (ptr, 1)) == INTEGER_CST)
1678     {
1679       /* Make sure we know the object is addressable.  */
1680       pptr = &TREE_OPERAND (ptr, 0);
1681       add_stmt_operand (pptr, s_ann, 0);
1682
1683       /* Mark the object itself with a VUSE.  */
1684       pptr = &TREE_OPERAND (*pptr, 0);
1685       get_expr_operands (stmt, pptr, flags);
1686       return;
1687     }
1688
1689   /* Ok, this isn't even is_gimple_min_invariant.  Something's broke.  */
1690   else
1691     gcc_unreachable ();
1692
1693   /* Add a USE operand for the base pointer.  */
1694   get_expr_operands (stmt, pptr, opf_none);
1695 }
1696
1697 /* A subroutine of get_expr_operands to handle CALL_EXPR.  */
1698
1699 static void
1700 get_call_expr_operands (tree stmt, tree expr)
1701 {
1702   tree op;
1703   int call_flags = call_expr_flags (expr);
1704
1705   /* If aliases have been computed already, add V_MAY_DEF or V_USE
1706      operands for all the symbols that have been found to be
1707      call-clobbered.
1708
1709      Note that if aliases have not been computed, the global effects
1710      of calls will not be included in the SSA web. This is fine
1711      because no optimizer should run before aliases have been
1712      computed.  By not bothering with virtual operands for CALL_EXPRs
1713      we avoid adding superfluous virtual operands, which can be a
1714      significant compile time sink (See PR 15855).  */
1715   if (aliases_computed_p
1716       && !bitmap_empty_p (call_clobbered_vars)
1717       && !(call_flags & ECF_NOVOPS))
1718     {
1719       /* A 'pure' or a 'const' functions never call clobber anything.
1720          A 'noreturn' function might, but since we don't return anyway
1721          there is no point in recording that.  */
1722       if (TREE_SIDE_EFFECTS (expr)
1723           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1724         add_call_clobber_ops (stmt);
1725       else if (!(call_flags & ECF_CONST))
1726         add_call_read_ops (stmt);
1727     }
1728
1729   /* Find uses in the called function.  */
1730   get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none);
1731
1732   for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
1733     get_expr_operands (stmt, &TREE_VALUE (op), opf_none);
1734
1735   get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
1736
1737 }
1738
1739
1740 /* Add *VAR_P to the appropriate operand array for INFO.  FLAGS is as in
1741    get_expr_operands.  If *VAR_P is a GIMPLE register, it will be added to
1742    the statement's real operands, otherwise it is added to virtual
1743    operands.  */
1744
1745 static void
1746 add_stmt_operand (tree *var_p, stmt_ann_t s_ann, int flags)
1747 {
1748   bool is_real_op;
1749   tree var, sym;
1750   var_ann_t v_ann;
1751
1752   var = *var_p;
1753   STRIP_NOPS (var);
1754
1755   /* If the operand is an ADDR_EXPR, add its operand to the list of
1756      variables that have had their address taken in this statement.  */
1757   if (TREE_CODE (var) == ADDR_EXPR)
1758     {
1759       note_addressable (TREE_OPERAND (var, 0), s_ann);
1760       return;
1761     }
1762
1763   /* If the original variable is not a scalar, it will be added to the list
1764      of virtual operands.  In that case, use its base symbol as the virtual
1765      variable representing it.  */
1766   is_real_op = is_gimple_reg (var);
1767   if (!is_real_op && !DECL_P (var))
1768     var = get_virtual_var (var);
1769
1770   /* If VAR is not a variable that we care to optimize, do nothing.  */
1771   if (var == NULL_TREE || !SSA_VAR_P (var))
1772     return;
1773
1774   sym = (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
1775   v_ann = var_ann (sym);
1776
1777   /* Mark statements with volatile operands.  Optimizers should back
1778      off from statements having volatile operands.  */
1779   if (TREE_THIS_VOLATILE (sym) && s_ann)
1780     s_ann->has_volatile_ops = true;
1781
1782   if (is_real_op)
1783     {
1784       /* The variable is a GIMPLE register.  Add it to real operands.  */
1785       if (flags & opf_is_def)
1786         append_def (var_p);
1787       else
1788         append_use (var_p);
1789     }
1790   else
1791     {
1792       varray_type aliases;
1793
1794       /* The variable is not a GIMPLE register.  Add it (or its aliases) to
1795          virtual operands, unless the caller has specifically requested
1796          not to add virtual operands (used when adding operands inside an
1797          ADDR_EXPR expression).  */
1798       if (flags & opf_no_vops)
1799         return;
1800
1801       aliases = v_ann->may_aliases;
1802
1803       if (aliases == NULL)
1804         {
1805           /* The variable is not aliased or it is an alias tag.  */
1806           if (flags & opf_is_def)
1807             {
1808               if (flags & opf_kill_def)
1809                 {
1810                   /* Only regular variables or struct fields may get a
1811                      V_MUST_DEF operand.  */
1812                   gcc_assert (v_ann->mem_tag_kind == NOT_A_TAG
1813                               || v_ann->mem_tag_kind == STRUCT_FIELD);
1814                   /* V_MUST_DEF for non-aliased, non-GIMPLE register
1815                     variable definitions.  */
1816                   append_v_must_def (var);
1817                 }
1818               else
1819                 {
1820                   /* Add a V_MAY_DEF for call-clobbered variables and
1821                      memory tags.  */
1822                   append_v_may_def (var);
1823                 }
1824             }
1825           else
1826             {
1827               append_vuse (var);
1828               if (s_ann && v_ann->is_alias_tag)
1829                 s_ann->makes_aliased_loads = 1;
1830             }
1831         }
1832       else
1833         {
1834           size_t i;
1835
1836           /* The variable is aliased.  Add its aliases to the virtual
1837              operands.  */
1838           gcc_assert (VARRAY_ACTIVE_SIZE (aliases) != 0);
1839
1840           if (flags & opf_is_def)
1841             {
1842               /* If the variable is also an alias tag, add a virtual
1843                  operand for it, otherwise we will miss representing
1844                  references to the members of the variable's alias set.
1845                  This fixes the bug in gcc.c-torture/execute/20020503-1.c.  */
1846               if (v_ann->is_alias_tag)
1847                 append_v_may_def (var);
1848
1849               for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
1850                 append_v_may_def (VARRAY_TREE (aliases, i));
1851
1852               if (s_ann)
1853                 s_ann->makes_aliased_stores = 1;
1854             }
1855           else
1856             {
1857               /* Similarly, append a virtual uses for VAR itself, when
1858                  it is an alias tag.  */
1859               if (v_ann->is_alias_tag)
1860                 append_vuse (var);
1861
1862               for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
1863                 append_vuse (VARRAY_TREE (aliases, i));
1864
1865               if (s_ann)
1866                 s_ann->makes_aliased_loads = 1;
1867             }
1868         }
1869     }
1870 }
1871
1872
1873 /* Record that VAR had its address taken in the statement with annotations
1874    S_ANN.  */
1875
1876 static void
1877 note_addressable (tree var, stmt_ann_t s_ann)
1878 {
1879   tree ref;
1880   subvar_t svars;
1881   HOST_WIDE_INT offset;
1882   HOST_WIDE_INT size;
1883
1884   if (!s_ann)
1885     return;
1886
1887   /* If this is a COMPONENT_REF, and we know exactly what it touches, we only
1888      take the address of the subvariables it will touch.
1889      Otherwise, we take the address of all the subvariables, plus the real
1890      ones.  */
1891
1892   if (var && TREE_CODE (var) == COMPONENT_REF
1893       && (ref = okay_component_ref_for_subvars (var, &offset, &size)))
1894     {
1895       subvar_t sv;
1896       svars = get_subvars_for_var (ref);
1897
1898       if (s_ann->addresses_taken == NULL)
1899         s_ann->addresses_taken = BITMAP_GGC_ALLOC ();
1900
1901       for (sv = svars; sv; sv = sv->next)
1902         {
1903           if (overlap_subvar (offset, size, sv, NULL))
1904             bitmap_set_bit (s_ann->addresses_taken, var_ann (sv->var)->uid);
1905         }
1906       return;
1907     }
1908
1909   var = get_base_address (var);
1910   if (var && SSA_VAR_P (var))
1911     {
1912       if (s_ann->addresses_taken == NULL)
1913         s_ann->addresses_taken = BITMAP_GGC_ALLOC ();
1914
1915
1916       if (var_can_have_subvars (var)
1917           && (svars = get_subvars_for_var (var)))
1918         {
1919           subvar_t sv;
1920           for (sv = svars; sv; sv = sv->next)
1921             bitmap_set_bit (s_ann->addresses_taken, var_ann (sv->var)->uid);
1922         }
1923       else
1924         bitmap_set_bit (s_ann->addresses_taken, var_ann (var)->uid);
1925     }
1926 }
1927
1928 /* Add clobbering definitions for .GLOBAL_VAR or for each of the call
1929    clobbered variables in the function.  */
1930
1931 static void
1932 add_call_clobber_ops (tree stmt)
1933 {
1934   unsigned i;
1935   tree t;
1936   bitmap_iterator bi;
1937   stmt_ann_t s_ann = stmt_ann (stmt);
1938   struct stmt_ann_d empty_ann;
1939
1940   /* Functions that are not const, pure or never return may clobber
1941      call-clobbered variables.  */
1942   if (s_ann)
1943     s_ann->makes_clobbering_call = true;
1944
1945   /* If we created .GLOBAL_VAR earlier, just use it.  See compute_may_aliases
1946      for the heuristic used to decide whether to create .GLOBAL_VAR or not.  */
1947   if (global_var)
1948     {
1949       add_stmt_operand (&global_var, s_ann, opf_is_def);
1950       return;
1951     }
1952
1953   /* If cache is valid, copy the elements into the build vectors.  */
1954   if (ssa_call_clobbered_cache_valid)
1955     {
1956       for (i = 0; i < VARRAY_ACTIVE_SIZE (clobbered_vuses); i++)
1957         {
1958           t = VARRAY_TREE (clobbered_vuses, i);
1959           gcc_assert (TREE_CODE (t) != SSA_NAME);
1960           var_ann (t)->in_vuse_list = 1;
1961           VARRAY_PUSH_TREE (build_vuses, t);
1962         }
1963       for (i = 0; i < VARRAY_ACTIVE_SIZE (clobbered_v_may_defs); i++)
1964         {
1965           t = VARRAY_TREE (clobbered_v_may_defs, i);
1966           gcc_assert (TREE_CODE (t) != SSA_NAME);
1967           var_ann (t)->in_v_may_def_list = 1;
1968           VARRAY_PUSH_TREE (build_v_may_defs, t);
1969         }
1970       if (s_ann)
1971         {
1972           s_ann->makes_aliased_loads = clobbered_aliased_loads;
1973           s_ann->makes_aliased_stores = clobbered_aliased_stores;
1974         }
1975       return;
1976     }
1977
1978   memset (&empty_ann, 0, sizeof (struct stmt_ann_d));
1979
1980   /* Add a V_MAY_DEF operand for every call clobbered variable.  */
1981   EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
1982     {
1983       tree var = referenced_var (i);
1984       if (TREE_READONLY (var)
1985           && (TREE_STATIC (var) || DECL_EXTERNAL (var)))
1986         add_stmt_operand (&var, &empty_ann, opf_none);
1987       else
1988         add_stmt_operand (&var, &empty_ann, opf_is_def);
1989     }
1990
1991   clobbered_aliased_loads = empty_ann.makes_aliased_loads;
1992   clobbered_aliased_stores = empty_ann.makes_aliased_stores;
1993
1994   /* Set the flags for a stmt's annotation.  */
1995   if (s_ann)
1996     {
1997       s_ann->makes_aliased_loads = empty_ann.makes_aliased_loads;
1998       s_ann->makes_aliased_stores = empty_ann.makes_aliased_stores;
1999     }
2000
2001   /* Prepare empty cache vectors.  */
2002   if (clobbered_v_may_defs)
2003     {
2004       VARRAY_POP_ALL (clobbered_vuses);
2005       VARRAY_POP_ALL (clobbered_v_may_defs);
2006     }
2007   else
2008     {
2009       VARRAY_TREE_INIT (clobbered_v_may_defs, 10, "clobbered_v_may_defs");
2010       VARRAY_TREE_INIT (clobbered_vuses, 10, "clobbered_vuses");
2011     }
2012
2013   /* Now fill the clobbered cache with the values that have been found.  */
2014   for (i = 0; i < VARRAY_ACTIVE_SIZE (build_vuses); i++)
2015     VARRAY_PUSH_TREE (clobbered_vuses, VARRAY_TREE (build_vuses, i));
2016   for (i = 0; i < VARRAY_ACTIVE_SIZE (build_v_may_defs); i++)
2017     VARRAY_PUSH_TREE (clobbered_v_may_defs, VARRAY_TREE (build_v_may_defs, i));
2018
2019   ssa_call_clobbered_cache_valid = true;
2020 }
2021
2022
2023 /* Add VUSE operands for .GLOBAL_VAR or all call clobbered variables in the
2024    function.  */
2025
2026 static void
2027 add_call_read_ops (tree stmt)
2028 {
2029   unsigned i;
2030   tree t;
2031   bitmap_iterator bi;
2032   stmt_ann_t s_ann = stmt_ann (stmt);
2033   struct stmt_ann_d empty_ann;
2034
2035   /* if the function is not pure, it may reference memory.  Add
2036      a VUSE for .GLOBAL_VAR if it has been created.  See add_referenced_var
2037      for the heuristic used to decide whether to create .GLOBAL_VAR.  */
2038   if (global_var)
2039     {
2040       add_stmt_operand (&global_var, s_ann, opf_none);
2041       return;
2042     }
2043
2044   /* If cache is valid, copy the elements into the build vector.  */
2045   if (ssa_ro_call_cache_valid)
2046     {
2047       for (i = 0; i < VARRAY_ACTIVE_SIZE (ro_call_vuses); i++)
2048         {
2049           t = VARRAY_TREE (ro_call_vuses, i);
2050           gcc_assert (TREE_CODE (t) != SSA_NAME);
2051           var_ann (t)->in_vuse_list = 1;
2052           VARRAY_PUSH_TREE (build_vuses, t);
2053         }
2054       if (s_ann)
2055         s_ann->makes_aliased_loads = ro_call_aliased_loads;
2056       return;
2057     }
2058
2059   memset (&empty_ann, 0, sizeof (struct stmt_ann_d));
2060
2061   /* Add a VUSE for each call-clobbered variable.  */
2062   EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
2063     {
2064       tree var = referenced_var (i);
2065       add_stmt_operand (&var, &empty_ann, opf_none);
2066     }
2067
2068   ro_call_aliased_loads = empty_ann.makes_aliased_loads;
2069   if (s_ann)
2070     s_ann->makes_aliased_loads = empty_ann.makes_aliased_loads;
2071
2072   /* Prepare empty cache vectors.  */
2073   if (ro_call_vuses)
2074     VARRAY_POP_ALL (ro_call_vuses);
2075   else
2076     VARRAY_TREE_INIT (ro_call_vuses, 10, "ro_call_vuses");
2077
2078   /* Now fill the clobbered cache with the values that have been found.  */
2079   for (i = 0; i < VARRAY_ACTIVE_SIZE (build_vuses); i++)
2080     VARRAY_PUSH_TREE (ro_call_vuses, VARRAY_TREE (build_vuses, i));
2081
2082   ssa_ro_call_cache_valid = true;
2083 }
2084
2085 /* Copies virtual operands from SRC to DST.  */
2086
2087 void
2088 copy_virtual_operands (tree dst, tree src)
2089 {
2090   unsigned i;
2091   vuse_optype vuses = STMT_VUSE_OPS (src);
2092   v_may_def_optype v_may_defs = STMT_V_MAY_DEF_OPS (src);
2093   v_must_def_optype v_must_defs = STMT_V_MUST_DEF_OPS (src);
2094   vuse_optype *vuses_new = &stmt_ann (dst)->operands.vuse_ops;
2095   v_may_def_optype *v_may_defs_new = &stmt_ann (dst)->operands.v_may_def_ops;
2096   v_must_def_optype *v_must_defs_new = &stmt_ann (dst)->operands.v_must_def_ops;
2097
2098   if (vuses)
2099     {
2100       *vuses_new = allocate_vuse_optype (NUM_VUSES (vuses));
2101       for (i = 0; i < NUM_VUSES (vuses); i++)
2102         initialize_vuse_operand (*vuses_new, i, VUSE_OP (vuses, i), dst, NULL);
2103     }
2104
2105   if (v_may_defs)
2106     {
2107       *v_may_defs_new = allocate_v_may_def_optype (NUM_V_MAY_DEFS (v_may_defs));
2108       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
2109         {
2110           initialize_v_may_def_operand (*v_may_defs_new, i,
2111                                         V_MAY_DEF_RESULT (v_may_defs, i),
2112                                         V_MAY_DEF_OP (v_may_defs, i), dst,
2113                                         NULL);
2114         }
2115     }
2116
2117   if (v_must_defs)
2118     {
2119       *v_must_defs_new
2120          = allocate_v_must_def_optype (NUM_V_MUST_DEFS (v_must_defs));
2121       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
2122         {
2123           initialize_v_must_def_operand (*v_must_defs_new, i,
2124                                          V_MUST_DEF_RESULT (v_must_defs, i),
2125                                          V_MUST_DEF_KILL (v_must_defs, i), dst,
2126                                          NULL);
2127         }
2128     }
2129 }
2130
2131
2132 /* Specifically for use in DOM's expression analysis.  Given a store, we
2133    create an artificial stmt which looks like a load from the store, this can
2134    be used to eliminate redundant loads.  OLD_OPS are the operands from the
2135    store stmt, and NEW_STMT is the new load which represents a load of the
2136    values stored.  */
2137
2138 void
2139 create_ssa_artficial_load_stmt (stmt_operands_p old_ops, tree new_stmt)
2140 {
2141   stmt_ann_t ann;
2142   tree op;
2143   stmt_operands_t tmp;
2144   unsigned j;
2145
2146   memset (&tmp, 0, sizeof (stmt_operands_t));
2147   ann = get_stmt_ann (new_stmt);
2148
2149   /* Free operands just in case is was an existing stmt.  */
2150   free_ssa_operands (&(ann->operands));
2151
2152   build_ssa_operands (new_stmt, NULL, &tmp, &(ann->operands));
2153   free_vuses (&(ann->operands.vuse_ops));
2154   free_v_may_defs (&(ann->operands.v_may_def_ops));
2155   free_v_must_defs (&(ann->operands.v_must_def_ops));
2156
2157   /* For each VDEF on the original statement, we want to create a
2158      VUSE of the V_MAY_DEF result or V_MUST_DEF op on the new
2159      statement.  */
2160   for (j = 0; j < NUM_V_MAY_DEFS (old_ops->v_may_def_ops); j++)
2161     {
2162       op = V_MAY_DEF_RESULT (old_ops->v_may_def_ops, j);
2163       append_vuse (op);
2164     }
2165
2166   for (j = 0; j < NUM_V_MUST_DEFS (old_ops->v_must_def_ops); j++)
2167     {
2168       op = V_MUST_DEF_RESULT (old_ops->v_must_def_ops, j);
2169       append_vuse (op);
2170     }
2171
2172   /* Now set the vuses for this new stmt.  */
2173   ann->operands.vuse_ops = finalize_ssa_vuses (&(tmp.vuse_ops), NULL);
2174 }
2175
2176
2177
2178 /* Issue immediate use error for VAR to debug file F.  */
2179 static void
2180 verify_abort (FILE *f, ssa_imm_use_t *var)
2181 {
2182   tree stmt;
2183   stmt = var->stmt;
2184   if (stmt)
2185     {
2186       if (stmt_modified_p(stmt))
2187         {
2188           fprintf (f, " STMT MODIFIED. - <%p> ", (void *)stmt);
2189           print_generic_stmt (f, stmt, TDF_SLIM);
2190         }
2191     }
2192   fprintf (f, " IMM ERROR : (use_p : tree - %p:%p)", (void *)var,
2193            (void *)var->use);
2194   print_generic_expr (f, USE_FROM_PTR (var), TDF_SLIM);
2195   fprintf(f, "\n");
2196 }
2197
2198
2199 /* Scan the immediate_use list for VAR making sure its linked properly.
2200    return RTUE iof there is a problem.  */
2201
2202 bool
2203 verify_imm_links (FILE *f, tree var)
2204 {
2205   ssa_imm_use_t *ptr, *prev;
2206   ssa_imm_use_t *list;
2207   int count;
2208
2209   gcc_assert (TREE_CODE (var) == SSA_NAME);
2210
2211   list = &(SSA_NAME_IMM_USE_NODE (var));
2212   gcc_assert (list->use == NULL);
2213
2214   if (list->prev == NULL)
2215     {
2216       gcc_assert (list->next == NULL);
2217       return false;
2218     }
2219
2220   prev = list;
2221   count = 0;
2222   for (ptr = list->next; ptr != list; )
2223     {
2224       if (prev != ptr->prev)
2225         {
2226           verify_abort (f, ptr);
2227           return true;
2228         }
2229
2230       if (ptr->use == NULL)
2231         {
2232           verify_abort (f, ptr);        /* 2 roots, or SAFE guard node.  */
2233           return true;
2234         }
2235       else
2236         if (*(ptr->use) != var)
2237           {
2238             verify_abort (f, ptr);
2239             return true;
2240           }
2241
2242       prev = ptr;
2243       ptr = ptr->next;
2244       /* Avoid infinite loops.  */
2245       if (count++ > 30000)
2246         {
2247           verify_abort (f, ptr);
2248           return true;
2249         }
2250     }
2251
2252   /* Verify list in the other direction.  */
2253   prev = list;
2254   for (ptr = list->prev; ptr != list; )
2255     {
2256       if (prev != ptr->next)
2257         {
2258           verify_abort (f, ptr);
2259           return true;
2260         }
2261       prev = ptr;
2262       ptr = ptr->prev;
2263       if (count-- < 0)
2264         {
2265           verify_abort (f, ptr);
2266           return true;
2267         }
2268     }
2269
2270   if (count != 0)
2271     {
2272       verify_abort (f, ptr);
2273       return true;
2274     }
2275
2276   return false;
2277 }
2278
2279
2280 /* Dump all the immediate uses to FILE.  */
2281
2282 void
2283 dump_immediate_uses_for (FILE *file, tree var)
2284 {
2285   imm_use_iterator iter;
2286   use_operand_p use_p;
2287
2288   gcc_assert (var && TREE_CODE (var) == SSA_NAME);
2289
2290   print_generic_expr (file, var, TDF_SLIM);
2291   fprintf (file, " : -->");
2292   if (has_zero_uses (var))
2293     fprintf (file, " no uses.\n");
2294   else
2295     if (has_single_use (var))
2296       fprintf (file, " single use.\n");
2297     else
2298       fprintf (file, "%d uses.\n", num_imm_uses (var));
2299
2300   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
2301     {
2302       print_generic_stmt (file, USE_STMT (use_p), TDF_SLIM);
2303     }
2304   fprintf(file, "\n");
2305 }
2306
2307 /* Dump all the immediate uses to FILE.  */
2308
2309 void
2310 dump_immediate_uses (FILE *file)
2311 {
2312   tree var;
2313   unsigned int x;
2314
2315   fprintf (file, "Immediate_uses: \n\n");
2316   for (x = 1; x < num_ssa_names; x++)
2317     {
2318       var = ssa_name(x);
2319       if (!var)
2320         continue;
2321       dump_immediate_uses_for (file, var);
2322     }
2323 }
2324
2325
2326 /* Dump def-use edges on stderr.  */
2327
2328 void
2329 debug_immediate_uses (void)
2330 {
2331   dump_immediate_uses (stderr);
2332 }
2333
2334 /* Dump def-use edges on stderr.  */
2335
2336 void
2337 debug_immediate_uses_for (tree var)
2338 {
2339   dump_immediate_uses_for (stderr, var);
2340 }
2341
2342 #include "gt-tree-ssa-operands.h"