gcc/tree-ssa-operands.c

   1 /* SSA operands management for trees.
   2    Copyright (C) 2003 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 "tree-flow.h"
  30 #include "tree-inline.h"
  31 #include "tree-pass.h"
  32 #include "ggc.h"
  33 #include "timevar.h"
  34
  35 /* Flags to describe operand properties in get_stmt_operands and helpers.  */
  36
  37 /* By default, operands are loaded.  */
  38 #define opf_none        0
  39
  40 /* Operand is the target of an assignment expression.  */
  41 #define opf_is_def      (1 << 0)
  42
  43 /* No virtual operands should be created in the expression.  This is used
  44    when traversing ADDR_EXPR nodes which have different semantics than
  45    other expressions.  Inside an ADDR_EXPR node, the only operands that we
  46    need to consider are indices into arrays.  For instance, &a.b[i] should
  47    generate a USE of 'i' but it should not generate a VUSE for 'a' nor a
  48    VUSE for 'b'.  */
  49 #define opf_no_vops     (1 << 1)
  50
  51 /* Array for building all the def operands.  */
  52 static GTY (()) varray_type build_defs;
  53
  54 /* Array for building all the use operands.  */
  55 static GTY (()) varray_type build_uses;
  56
  57 /* Array for building all the vdef operands.  */
  58 static GTY (()) varray_type build_vdefs;
  59
  60 /* Array for building all the vuse operands.  */
  61 static GTY (()) varray_type build_vuses;
  62
  63 #ifdef ENABLE_CHECKING
  64 tree check_build_stmt;
  65 #endif
  66
  67 typedef struct voperands_d
  68 {
  69   vdef_optype vdef_ops;
  70   vuse_optype vuse_ops;
  71 } *voperands_t;
  72
  73 static void note_addressable (tree, stmt_ann_t);
  74 static void get_expr_operands (tree, tree *, int, voperands_t);
  75 static inline void append_def (tree *, tree);
  76 static inline void append_use (tree *, tree);
  77 static void append_vdef (tree, tree, voperands_t);
  78 static void add_call_clobber_ops (tree, voperands_t);
  79 static void add_call_read_ops (tree, voperands_t);
  80 static void add_stmt_operand (tree *, tree, int, voperands_t);
  81
  82
  83 struct freelist_d GTY((chain_next ("%h.next")))
  84 {
  85    struct freelist_d *next;
  86 };
  87
  88 #define NUM_FREE        4
  89 static GTY ((length ("NUM_FREE"))) struct freelist_d optype_freelist[NUM_FREE] = { {0}, {0}, {0}, {0} };
  90
  91
  92 static inline void *
  93 check_optype_freelist (size_t num ATTRIBUTE_UNUSED)
  94 {
  95   return NULL;
  96 #if 0
  97   void *vec = NULL;
  98
  99   if (num <= NUM_FREE && optype_freelist[num - 1].next)
 100     {
 101       vec = (void *)optype_freelist[num - 1].next;
 102       optype_freelist[num - 1].next = optype_freelist[num - 1].next->next;
 103     }
 104   return vec;
 105 #endif
 106 }
 107 /* Return a vector of contiguous memory of a specified size.  */
 108
 109
 110 static inline void
 111 add_optype_freelist (void *vec ATTRIBUTE_UNUSED, size_t size ATTRIBUTE_UNUSED)
 112 {
 113 #if 0
 114   struct freelist_d *ptr;
 115 #ifdef ENABLE_CHECKING
 116   if (size == 0)
 117     abort ();
 118 #endif
 119
 120   /* if its bigger than one of our lists, simply let it go and let GC
 121      collect it.  */
 122   if (size > NUM_FREE)
 123     return;
 124
 125   ptr = vec;
 126   ptr->next = optype_freelist[size - 1].next;;
 127   optype_freelist[size - 1].next = ptr;
 128 #endif
 129 }
 130
 131
 132 static inline def_optype
 133 allocate_def_optype (unsigned num)
 134 {
 135   def_optype def_ops;
 136   unsigned size;
 137   size = sizeof (struct def_optype_d) + sizeof (tree *) * (num - 1);
 138   def_ops = check_optype_freelist (num);
 139   if (!def_ops)
 140     def_ops =  ggc_alloc (size);
 141   def_ops->num_defs = num;
 142   return def_ops;
 143 }
 144
 145 static inline use_optype
 146 allocate_use_optype (unsigned num)
 147 {
 148   use_optype use_ops;
 149   unsigned size;
 150   size = sizeof (struct use_optype_d) + sizeof (tree *) * (num - 1);
 151   use_ops = check_optype_freelist (num);
 152   if (!use_ops)
 153     use_ops =  ggc_alloc (size);
 154   use_ops->num_uses = num;
 155   return use_ops;
 156 }
 157
 158 static inline vdef_optype
 159 allocate_vdef_optype (unsigned num)
 160 {
 161   vdef_optype vdef_ops;
 162   unsigned size;
 163   size = sizeof (struct vdef_optype_d) + sizeof (tree) * ((num * 2) - 1);
 164   vdef_ops = check_optype_freelist (num * 2);
 165   if (!vdef_ops)
 166     vdef_ops =  ggc_alloc (size);
 167   vdef_ops->num_vdefs = num;
 168   return vdef_ops;
 169 }
 170
 171 static inline vuse_optype
 172 allocate_vuse_optype (unsigned num)
 173 {
 174   vuse_optype vuse_ops;
 175   unsigned size;
 176   size = sizeof (struct vuse_optype_d) + sizeof (tree) * (num - 1);
 177   vuse_ops = check_optype_freelist (num);
 178   if (!vuse_ops)
 179     vuse_ops =  ggc_alloc (size);
 180   vuse_ops->num_vuses = num;
 181   return vuse_ops;
 182 }
 183
 184 static inline void
 185 free_uses (use_optype *uses, bool dealloc)
 186 {
 187   if (*uses)
 188     {
 189       if (dealloc)
 190         add_optype_freelist (*uses, (*uses)->num_uses);
 191       *uses = NULL;
 192     }
 193 }
 194
 195 static inline void
 196 free_defs (def_optype *defs, bool dealloc)
 197 {
 198   if (*defs)
 199     {
 200       if (dealloc)
 201         add_optype_freelist (*defs, (*defs)->num_defs);
 202       *defs = NULL;
 203     }
 204 }
 205
 206 static inline void
 207 free_vuses (vuse_optype *vuses, bool dealloc)
 208 {
 209   if (*vuses)
 210     {
 211       if (dealloc)
 212         add_optype_freelist (*vuses, (*vuses)->num_vuses);
 213       *vuses = NULL;
 214     }
 215 }
 216
 217 static inline void
 218 free_vdefs (vdef_optype *vdefs, bool dealloc)
 219 {
 220   if (*vdefs)
 221     {
 222       if (dealloc)
 223         add_optype_freelist (*vdefs, (*vdefs)->num_vdefs);
 224       *vdefs = NULL;
 225     }
 226 }
 227
 228 void
 229 remove_vuses (tree stmt)
 230 {
 231   stmt_ann_t ann;
 232
 233   ann = stmt_ann (stmt);
 234   if (ann)
 235     free_vuses (&(ann->vuse_ops), true);
 236 }
 237
 238 void
 239 remove_vdefs (tree stmt)
 240 {
 241   stmt_ann_t ann;
 242
 243   ann = stmt_ann (stmt);
 244   if (ann)
 245     free_vdefs (&(ann->vdef_ops), true);
 246 }
 247
 248
 249 void
 250 init_ssa_operands (void)
 251 {
 252   int x;
 253
 254   VARRAY_TREE_PTR_INIT (build_defs, 5, "build defs");
 255   VARRAY_TREE_PTR_INIT (build_uses, 10, "build uses");
 256   VARRAY_TREE_INIT (build_vdefs, 10, "build vdefs");
 257   VARRAY_TREE_INIT (build_vuses, 10, "build vuses");
 258
 259   for (x = 0; x < NUM_FREE; x++)
 260     optype_freelist[x].next = NULL;
 261 }
 262
 263 void
 264 fini_ssa_operands (void)
 265 {
 266   int x;
 267   for (x = 0; x < NUM_FREE; x++)
 268     optype_freelist[x].next = NULL;
 269 }
 270
 271 static void
 272 finalize_ssa_defs (tree stmt)
 273 {
 274   unsigned num, x;
 275   stmt_ann_t ann;
 276   def_optype def_ops;
 277
 278   num = VARRAY_ACTIVE_SIZE (build_defs);
 279   if (num == 0)
 280     return;
 281
 282 #ifdef ENABLE_CHECKING
 283   /* There should only be a single real definition per assignment.  */
 284   if (TREE_CODE (stmt) == MODIFY_EXPR && num > 1)
 285     abort ();
 286 #endif
 287
 288   def_ops = allocate_def_optype (num);
 289   for (x = 0; x < num ; x++)
 290     def_ops->defs[x] = VARRAY_TREE_PTR (build_defs, x);
 291   VARRAY_POP_ALL (build_defs);
 292
 293   ann = stmt_ann (stmt);
 294   ann->def_ops = def_ops;
 295 }
 296
 297 static void
 298 finalize_ssa_uses (tree stmt)
 299 {
 300   unsigned num, x;
 301   use_optype use_ops;
 302   stmt_ann_t ann;
 303
 304   num = VARRAY_ACTIVE_SIZE (build_uses);
 305   if (num == 0)
 306     return;
 307
 308 #ifdef ENABLE_CHECKING
 309   {
 310     unsigned x;
 311     /* If the pointer to the operand is the statement itself, something is
 312        wrong.  It means that we are pointing to a local variable (the
 313        initial call to get_stmt_operands does not pass a pointer to a
 314        statement).  */
 315     for (x = 0; x < num; x++)
 316       if (*(VARRAY_TREE_PTR (build_uses, x)) == stmt)
 317         abort ();
 318   }
 319 #endif
 320
 321   use_ops = allocate_use_optype (num);
 322   for (x = 0; x < num ; x++)
 323     use_ops->uses[x] = VARRAY_TREE_PTR (build_uses, x);
 324   VARRAY_POP_ALL (build_uses);
 325
 326   ann = stmt_ann (stmt);
 327   ann->use_ops = use_ops;
 328 }
 329
 330 static void
 331 finalize_ssa_vdefs (tree stmt)
 332 {
 333   unsigned num, x;
 334   vdef_optype vdef_ops;
 335   stmt_ann_t ann;
 336
 337   num = VARRAY_ACTIVE_SIZE (build_vdefs);
 338   if (num == 0)
 339     return;
 340
 341 #ifdef ENABLE_CHECKING
 342   /* VDEFs must be entered in pairs of result/uses.  */
 343   if (num % 2 != 0)
 344     abort();
 345 #endif
 346
 347   vdef_ops = allocate_vdef_optype (num / 2);
 348   for (x = 0; x < num; x++)
 349     vdef_ops->vdefs[x] = VARRAY_TREE (build_vdefs, x);
 350   VARRAY_CLEAR (build_vdefs);
 351
 352   ann = stmt_ann (stmt);
 353   ann->vdef_ops = vdef_ops;
 354 }
 355
 356 static inline void
 357 finalize_ssa_vuses (tree stmt)
 358 {
 359   unsigned num, x;
 360   stmt_ann_t ann;
 361   vuse_optype vuse_ops;
 362   vdef_optype vdefs;
 363
 364 #ifdef ENABLE_CHECKING
 365   if (VARRAY_ACTIVE_SIZE (build_vdefs) > 0)
 366     {
 367       fprintf (stderr, "Please finalize VDEFs before finalize VUSES.\n");
 368       abort ();
 369     }
 370 #endif
 371
 372   num = VARRAY_ACTIVE_SIZE (build_vuses);
 373   if (num == 0)
 374     return;
 375
 376   /* Remove superfluous VUSE operands.  If the statement already has a
 377    VDEF operation for a variable 'a', then a VUSE for 'a' is not
 378    needed because VDEFs imply a VUSE of the variable.  For instance,
 379    suppose that variable 'a' is aliased:
 380
 381               # VUSE <a_2>
 382               # a_3 = VDEF <a_2>
 383               a = a + 1;
 384
 385   The VUSE <a_2> is superfluous because it is implied by the VDEF
 386   operation.  */
 387
 388   ann = stmt_ann (stmt);
 389   vdefs = VDEF_OPS (ann);
 390   if (NUM_VDEFS (vdefs) > 0)
 391     {
 392       size_t i, j;
 393       for (i = 0; i < VARRAY_ACTIVE_SIZE (build_vuses); i++)
 394         {
 395           bool found = false;
 396           for (j = 0; j < NUM_VDEFS (vdefs); j++)
 397             {
 398               tree vuse_var, vdef_var;
 399               tree vuse = VARRAY_TREE (build_vuses, i);
 400               tree vdef = VDEF_OP (vdefs, j);
 401
 402               if (TREE_CODE (vuse) == SSA_NAME)
 403                 vuse_var = SSA_NAME_VAR (vuse);
 404               else
 405                 vuse_var = vuse;
 406
 407               if (TREE_CODE (vdef) == SSA_NAME)
 408                 vdef_var = SSA_NAME_VAR (vdef);
 409               else
 410                 vdef_var = vdef;
 411
 412             if (vuse_var == vdef_var)
 413               {
 414                 found = true;
 415                 break;
 416               }
 417             }
 418
 419           /* If we found a useless VUSE operand, remove it from the
 420              operand array by replacing it with the last active element
 421              in the operand array (unless the useless VUSE was the
 422              last operand, in which case we simply remove it.  */
 423           if (found)
 424             {
 425               if (i != VARRAY_ACTIVE_SIZE (build_vuses) - 1)
 426                 {
 427                   VARRAY_TREE (build_vuses, i)
 428                     = VARRAY_TREE (build_vuses,
 429                                    VARRAY_ACTIVE_SIZE (build_vuses) - 1);
 430                 }
 431               VARRAY_POP (build_vuses);
 432
 433               /* We want to rescan the element at this index, unless
 434                  this was the last element, in which case the loop
 435                  terminates.  */
 436               i--;
 437             }
 438         }
 439     }
 440
 441   num = VARRAY_ACTIVE_SIZE (build_vuses);
 442   /* We could have reduced the size to zero now, however.  */
 443   if (num == 0)
 444     return;
 445
 446   vuse_ops = allocate_vuse_optype (num);
 447   for (x = 0; x < num; x++)
 448     vuse_ops->vuses[x] = VARRAY_TREE (build_vuses, x);
 449   VARRAY_CLEAR (build_vuses);
 450   ann->vuse_ops = vuse_ops;
 451 }
 452
 453 extern void
 454 finalize_ssa_stmt_operands (tree stmt)
 455 {
 456 #ifdef ENABLE_CHECKING
 457   if (check_build_stmt == NULL)
 458     abort();
 459 #endif
 460
 461   finalize_ssa_defs (stmt);
 462   finalize_ssa_uses (stmt);
 463   finalize_ssa_vdefs (stmt);
 464   finalize_ssa_vuses (stmt);
 465
 466 #ifdef ENABLE_CHECKING
 467   check_build_stmt = NULL;
 468 #endif
 469 }
 470
 471
 472 extern void
 473 verify_start_operands (tree stmt ATTRIBUTE_UNUSED)
 474 {
 475 #ifdef ENABLE_CHECKING
 476   if (VARRAY_ACTIVE_SIZE (build_defs) > 0
 477       || VARRAY_ACTIVE_SIZE (build_uses) > 0
 478       || VARRAY_ACTIVE_SIZE (build_vuses) > 0
 479       || VARRAY_ACTIVE_SIZE (build_vdefs) > 0)
 480     abort ();
 481   if (check_build_stmt != NULL)
 482     abort();
 483   check_build_stmt = stmt;
 484 #endif
 485 }
 486
 487
 488 /* Add DEF_P to the list of pointers to operands defined by STMT.  */
 489
 490 static inline void
 491 append_def (tree *def_p, tree stmt ATTRIBUTE_UNUSED)
 492 {
 493 #ifdef ENABLE_CHECKING
 494   if (check_build_stmt != stmt)
 495     abort();
 496 #endif
 497   VARRAY_PUSH_TREE_PTR (build_defs, def_p);
 498 }
 499
 500
 501 /* Add USE_P to the list of pointers to operands used by STMT.  */
 502
 503 static inline void
 504 append_use (tree *use_p, tree stmt ATTRIBUTE_UNUSED)
 505 {
 506 #ifdef ENABLE_CHECKING
 507   if (check_build_stmt != stmt)
 508     abort();
 509 #endif
 510   VARRAY_PUSH_TREE_PTR (build_uses, use_p);
 511 }
 512
 513
 514 /* Add a new virtual def for variable VAR to statement STMT.  If PREV_VOPS
 515    is not NULL, the existing entries are preserved and no new entries are
 516    added here.  This is done to preserve the SSA numbering of virtual
 517    operands.  */
 518
 519 static void
 520 append_vdef (tree var, tree stmt, voperands_t prev_vops)
 521 {
 522   stmt_ann_t ann;
 523   size_t i;
 524   tree result, source;
 525
 526 #ifdef ENABLE_CHECKING
 527   if (check_build_stmt != stmt)
 528     abort();
 529 #endif
 530
 531   ann = stmt_ann (stmt);
 532
 533   /* Don't allow duplicate entries.  */
 534
 535   for (i = 0; i < VARRAY_ACTIVE_SIZE (build_vdefs); i += 2)
 536     {
 537       tree result = VARRAY_TREE (build_vdefs, i);
 538       if (var == result
 539           || (TREE_CODE (result) == SSA_NAME
 540               && var == SSA_NAME_VAR (result)))
 541         return;
 542     }
 543
 544   /* If the statement already had virtual definitions, see if any of the
 545      existing VDEFs matches VAR.  If so, re-use it, otherwise add a new
 546      VDEF for VAR.  */
 547   result = NULL_TREE;
 548   source = NULL_TREE;
 549   if (prev_vops)
 550     for (i = 0; i < NUM_VDEFS (prev_vops->vdef_ops); i++)
 551       {
 552         result = VDEF_RESULT (prev_vops->vdef_ops, i);
 553         if (result == var
 554             || (TREE_CODE (result) == SSA_NAME
 555                 && SSA_NAME_VAR (result) == var))
 556           {
 557             source = VDEF_OP (prev_vops->vdef_ops, i);
 558             break;
 559           }
 560       }
 561
 562   /* If no previous VDEF operand was found for VAR, create one now.  */
 563   if (source == NULL_TREE)
 564     {
 565       result = var;
 566       source = var;
 567     }
 568
 569   VARRAY_PUSH_TREE (build_vdefs, result);
 570   VARRAY_PUSH_TREE (build_vdefs, source);
 571 }
 572
 573
 574 /* Add VAR to the list of virtual uses for STMT.  If PREV_VOPS
 575    is not NULL, the existing entries are preserved and no new entries are
 576    added here.  This is done to preserve the SSA numbering of virtual
 577    operands.  */
 578
 579 static void
 580 append_vuse (tree var, tree stmt, voperands_t prev_vops)
 581 {
 582   stmt_ann_t ann;
 583   size_t i;
 584   bool found;
 585   tree vuse;
 586
 587 #ifdef ENABLE_CHECKING
 588   if (check_build_stmt != stmt)
 589     abort();
 590 #endif
 591
 592   ann = stmt_ann (stmt);
 593
 594   /* Don't allow duplicate entries.  */
 595   for (i = 0; i < VARRAY_ACTIVE_SIZE (build_vuses); i++)
 596     {
 597       tree vuse_var = VARRAY_TREE (build_vuses, i);
 598       if (var == vuse_var
 599           || (TREE_CODE (vuse_var) == SSA_NAME
 600               && var == SSA_NAME_VAR (vuse_var)))
 601         return;
 602     }
 603
 604   /* If the statement already had virtual uses, see if any of the
 605      existing VUSEs matches VAR.  If so, re-use it, otherwise add a new
 606      VUSE for VAR.  */
 607   found = false;
 608   vuse = NULL_TREE;
 609   if (prev_vops)
 610     for (i = 0; i < NUM_VUSES (prev_vops->vuse_ops); i++)
 611       {
 612         vuse = VUSE_OP (prev_vops->vuse_ops, i);
 613         if (vuse == var
 614             || (TREE_CODE (vuse) == SSA_NAME
 615                 && SSA_NAME_VAR (vuse) == var))
 616           {
 617             found = true;
 618             break;
 619           }
 620       }
 621
 622   /* If VAR existed already in PREV_VOPS, re-use it.  */
 623   if (found)
 624     var = vuse;
 625
 626   VARRAY_PUSH_TREE (build_vuses, var);
 627 }
 628
 629
 630 /* External entry point which by-passes the previous vops mechanism.  */
 631 void
 632 add_vuse (tree var, tree stmt)
 633 {
 634   append_vuse (var, stmt, NULL);
 635 }
 636
 637
 638 /* Get the operands of statement STMT.  Note that repeated calls to
 639    get_stmt_operands for the same statement will do nothing until the
 640    statement is marked modified by a call to modify_stmt().  */
 641
 642 void
 643 get_stmt_operands (tree stmt)
 644 {
 645   enum tree_code code;
 646   stmt_ann_t ann;
 647   struct voperands_d prev_vops;
 648
 649 #if defined ENABLE_CHECKING
 650   /* The optimizers cannot handle statements that are nothing but a
 651      _DECL.  This indicates a bug in the gimplifier.  */
 652   if (SSA_VAR_P (stmt))
 653     abort ();
 654 #endif
 655
 656   /* Ignore error statements.  */
 657   if (TREE_CODE (stmt) == ERROR_MARK)
 658     return;
 659
 660   ann = get_stmt_ann (stmt);
 661
 662   /* If the statement has not been modified, the operands are still valid.  */
 663   if (!ann->modified)
 664     return;
 665
 666   timevar_push (TV_TREE_OPS);
 667
 668   /* Initially assume that the statement has no volatile operands.
 669      Statements marked with 'has_volatile_ops' are not processed by the
 670      optimizers.  */
 671   ann->has_volatile_ops = false;
 672
 673   /* Remove any existing operands as they will be scanned again.  */
 674   free_defs (&(ann->def_ops), true);
 675   free_uses (&(ann->use_ops), true);
 676
 677   /* Before removing existing virtual operands, save them in PREV_VOPS so
 678      that we can re-use their SSA versions.  */
 679   prev_vops.vdef_ops = VDEF_OPS (ann);
 680   prev_vops.vuse_ops = VUSE_OPS (ann);
 681
 682   /* Dont free the previous values to memory since we're still using them.  */
 683   free_vdefs (&(ann->vdef_ops), false);
 684   free_vuses (&(ann->vuse_ops), false);
 685
 686   start_ssa_stmt_operands (stmt);
 687
 688   code = TREE_CODE (stmt);
 689   switch (code)
 690     {
 691     case MODIFY_EXPR:
 692       get_expr_operands (stmt, &TREE_OPERAND (stmt, 1), opf_none, &prev_vops);
 693       get_expr_operands (stmt, &TREE_OPERAND (stmt, 0), opf_is_def, &prev_vops);
 694       break;
 695
 696     case COND_EXPR:
 697       get_expr_operands (stmt, &COND_EXPR_COND (stmt), opf_none, &prev_vops);
 698       break;
 699
 700     case SWITCH_EXPR:
 701       get_expr_operands (stmt, &SWITCH_COND (stmt), opf_none, &prev_vops);
 702       break;
 703
 704     case ASM_EXPR:
 705       {
 706         int noutputs = list_length (ASM_OUTPUTS (stmt));
 707         const char **oconstraints
 708           = (const char **) alloca ((noutputs) * sizeof (const char *));
 709         int i;
 710         tree link;
 711         const char *constraint;
 712         bool allows_mem, allows_reg, is_inout;
 713
 714         for (i=0, link = ASM_OUTPUTS (stmt); link;
 715              ++i, link = TREE_CHAIN (link))
 716           {
 717             oconstraints[i] = constraint
 718               = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 719             parse_output_constraint (&constraint, i, 0, 0,
 720                                      &allows_mem, &allows_reg, &is_inout);
 721             if (allows_reg && is_inout)
 722               /* This should have been split in gimplify_asm_expr.  */
 723               abort ();
 724
 725             if (!allows_reg && allows_mem)
 726               {
 727                 tree t = get_base_address (TREE_VALUE (link));
 728                 if (t && DECL_P (t))
 729                   mark_call_clobbered (t);
 730               }
 731
 732             get_expr_operands (stmt, &TREE_VALUE (link), opf_is_def,
 733                                &prev_vops);
 734           }
 735
 736         for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
 737           {
 738             constraint
 739               = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 740             parse_input_constraint (&constraint, 0, 0, noutputs, 0,
 741                                     oconstraints, &allows_mem, &allows_reg);
 742
 743             if (!allows_reg && allows_mem)
 744               {
 745                 tree t = get_base_address (TREE_VALUE (link));
 746                 if (t && DECL_P (t))
 747                   mark_call_clobbered (t);
 748               }
 749
 750             get_expr_operands (stmt, &TREE_VALUE (link), 0, &prev_vops);
 751           }
 752
 753         /* Clobber memory for asm ("" : : : "memory");  */
 754         for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
 755           if (!strcmp (TREE_STRING_POINTER (TREE_VALUE (link)), "memory"))
 756             add_call_clobber_ops (stmt, &prev_vops);
 757       }
 758       break;
 759
 760     case RETURN_EXPR:
 761       get_expr_operands (stmt, &TREE_OPERAND (stmt, 0), opf_none, &prev_vops);
 762       break;
 763
 764     case GOTO_EXPR:
 765       get_expr_operands (stmt, &GOTO_DESTINATION (stmt), opf_none, &prev_vops);
 766       break;
 767
 768     case LABEL_EXPR:
 769       get_expr_operands (stmt, &LABEL_EXPR_LABEL (stmt), opf_none, &prev_vops);
 770       break;
 771
 772       /* These nodes contain no variable references.  */
 773     case BIND_EXPR:
 774     case CASE_LABEL_EXPR:
 775     case TRY_CATCH_EXPR:
 776     case TRY_FINALLY_EXPR:
 777     case EH_FILTER_EXPR:
 778     case CATCH_EXPR:
 779     case RESX_EXPR:
 780       break;
 781
 782     default:
 783       /* Notice that if get_expr_operands tries to use &STMT as the operand
 784          pointer (which may only happen for USE operands), we will abort in
 785          append_use.  This default will handle statements like empty statements,
 786          CALL_EXPRs or VA_ARG_EXPRs that may appear on the RHS of a statement
 787          or as statements themselves.  */
 788       get_expr_operands (stmt, &stmt, opf_none, &prev_vops);
 789       break;
 790     }
 791
 792   finalize_ssa_stmt_operands (stmt);
 793
 794   /* Now free the previous virtual ops to memory.  */
 795   free_vdefs (&(prev_vops.vdef_ops), true);
 796   free_vuses (&(prev_vops.vuse_ops), true);
 797
 798   /* Clear the modified bit for STMT.  Subsequent calls to
 799      get_stmt_operands for this statement will do nothing until the
 800      statement is marked modified by a call to modify_stmt().  */
 801   ann->modified = 0;
 802
 803   timevar_pop (TV_TREE_OPS);
 804 }
 805
 806
 807 /* Recursively scan the expression pointed by EXPR_P in statement STMT.
 808    FLAGS is one of the OPF_* constants modifying how to interpret the
 809    operands found.  PREV_VOPS is as in append_vdef and append_vuse.  */
 810
 811 static void
 812 get_expr_operands (tree stmt, tree *expr_p, int flags, voperands_t prev_vops)
 813 {
 814   enum tree_code code;
 815   char class;
 816   tree expr = *expr_p;
 817
 818   if (expr == NULL || expr == error_mark_node)
 819     return;
 820
 821   code = TREE_CODE (expr);
 822   class = TREE_CODE_CLASS (code);
 823
 824   /* Expressions that make no memory references.  */
 825   if (class == 'c'
 826       || class == 't'
 827       || class == 'b'
 828       || code == FUNCTION_DECL
 829       || code == EXC_PTR_EXPR
 830       || code == FILTER_EXPR
 831       || code == LABEL_DECL)
 832     return;
 833
 834   /* We could have the address of a component, array member, etc which
 835      has interesting variable references.  */
 836   if (code == ADDR_EXPR)
 837     {
 838       enum tree_code subcode = TREE_CODE (TREE_OPERAND (expr, 0));
 839
 840       /* Taking the address of a variable does not represent a
 841          reference to it, but the fact that STMT takes its address will be
 842          of interest to some passes (e.g. alias resolution).  */
 843       add_stmt_operand (expr_p, stmt, 0, NULL);
 844
 845       /* If the address is invariant, there may be no interesting variable
 846          references inside.  */
 847       if (is_gimple_min_invariant (expr))
 848         return;
 849
 850       /* There should be no VUSEs created, since the referenced objects are
 851          not really accessed.  The only operands that we should find here
 852          are ARRAY_REF indices which will always be real operands (GIMPLE
 853          does not allow non-registers as array indices).  */
 854       flags |= opf_no_vops;
 855
 856       /* Avoid recursion.  */
 857       code = subcode;
 858       class = TREE_CODE_CLASS (code);
 859       expr_p = &TREE_OPERAND (expr, 0);
 860       expr = *expr_p;
 861     }
 862
 863   /* If we found a variable, add it to DEFS or USES depending on the
 864      operand flags.  */
 865   if (SSA_VAR_P (expr))
 866     {
 867       add_stmt_operand (expr_p, stmt, flags, prev_vops);
 868       return;
 869     }
 870
 871   /* Pointer dereferences always represent a use of the base pointer.  */
 872   if (code == INDIRECT_REF)
 873     {
 874       tree *pptr = &TREE_OPERAND (expr, 0);
 875       tree ptr = *pptr;
 876
 877       if (SSA_VAR_P (ptr))
 878         {
 879           if (!aliases_computed_p)
 880             {
 881               /* If the pointer does not have a memory tag and aliases have not
 882                  been computed yet, mark the statement as having volatile
 883                  operands to prevent DOM from entering it in equivalence tables
 884                  and DCE from killing it.  */
 885               stmt_ann (stmt)->has_volatile_ops = true;
 886             }
 887           else
 888             {
 889               ssa_name_ann_t ptr_ann = NULL;
 890
 891               /* If we have computed aliasing already, check if PTR has
 892                  flow-sensitive points-to information.  */
 893               if (TREE_CODE (ptr) == SSA_NAME
 894                   && (ptr_ann = ssa_name_ann (ptr)) != NULL
 895                   && ptr_ann->name_mem_tag)
 896                 {
 897                   /* PTR has its own memory tag.  Use it.  */
 898                   add_stmt_operand (&ptr_ann->name_mem_tag, stmt, flags,
 899                                     prev_vops);
 900                 }
 901               else
 902                 {
 903                   /* If PTR is not an SSA_NAME or it doesn't have a name
 904                      tag, use its type memory tag.  */
 905                   var_ann_t ann;
 906
 907                   /* If we are emitting debugging dumps, display a warning if
 908                      PTR is an SSA_NAME with no flow-sensitive alias
 909                      information.  That means that we may need to compute
 910                      aliasing again.  */
 911                   if (dump_file
 912                       && TREE_CODE (ptr) == SSA_NAME
 913                       && ptr_ann == NULL)
 914                     {
 915                       fprintf (dump_file,
 916                           "NOTE: no flow-sensitive alias info for ");
 917                       print_generic_expr (dump_file, ptr, dump_flags);
 918                       fprintf (dump_file, " in ");
 919                       print_generic_stmt (dump_file, stmt, dump_flags);
 920                     }
 921
 922                   if (TREE_CODE (ptr) == SSA_NAME)
 923                     ptr = SSA_NAME_VAR (ptr);
 924                   ann = var_ann (ptr);
 925                   add_stmt_operand (&ann->type_mem_tag, stmt, flags, prev_vops);
 926                 }
 927             }
 928         }
 929
 930       /* If a constant is used as a pointer, we can't generate a real
 931          operand for it but we mark the statement volatile to prevent
 932          optimizations from messing things up.  */
 933       else if (TREE_CODE (ptr) == INTEGER_CST)
 934         {
 935           stmt_ann (stmt)->has_volatile_ops = true;
 936           return;
 937         }
 938
 939       /* Everything else *should* have been folded elsewhere, but users
 940          are smarter than we in finding ways to write invalid code.  We
 941          cannot just abort here.  If we were absolutely certain that we
 942          do handle all valid cases, then we could just do nothing here.
 943          That seems optimistic, so attempt to do something logical... */
 944       else if ((TREE_CODE (ptr) == PLUS_EXPR || TREE_CODE (ptr) == MINUS_EXPR)
 945                && TREE_CODE (TREE_OPERAND (ptr, 0)) == ADDR_EXPR
 946                && TREE_CODE (TREE_OPERAND (ptr, 1)) == INTEGER_CST)
 947         {
 948           /* Make sure we know the object is addressable.  */
 949           pptr = &TREE_OPERAND (ptr, 0);
 950           add_stmt_operand (pptr, stmt, 0, NULL);
 951
 952           /* Mark the object itself with a VUSE.  */
 953           pptr = &TREE_OPERAND (*pptr, 0);
 954           get_expr_operands (stmt, pptr, flags, prev_vops);
 955           return;
 956         }
 957
 958       /* Ok, this isn't even is_gimple_min_invariant.  Something's broke.  */
 959       else
 960         abort ();
 961
 962       /* Add a USE operand for the base pointer.  */
 963       get_expr_operands (stmt, pptr, opf_none, prev_vops);
 964       return;
 965     }
 966
 967   /* Treat array references as references to the virtual variable
 968      representing the array.  The virtual variable for an ARRAY_REF
 969      is the VAR_DECL for the array.  */
 970   if (code == ARRAY_REF)
 971     {
 972       /* Add the virtual variable for the ARRAY_REF to VDEFS or VUSES
 973          according to the value of IS_DEF.  Recurse if the LHS of the
 974          ARRAY_REF node is not a regular variable.  */
 975       if (SSA_VAR_P (TREE_OPERAND (expr, 0)))
 976         add_stmt_operand (expr_p, stmt, flags, prev_vops);
 977       else
 978         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags, prev_vops);
 979
 980       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none, prev_vops);
 981       return;
 982     }
 983
 984   /* Similarly to arrays, references to compound variables (complex types
 985      and structures/unions) are globbed.
 986
 987      FIXME: This means that
 988
 989                         a.x = 6;
 990                         a.y = 7;
 991                         foo (a.x, a.y);
 992
 993            will not be constant propagated because the two partial
 994            definitions to 'a' will kill each other.  Note that SRA may be
 995            able to fix this problem if 'a' can be scalarized.  */
 996   if (code == IMAGPART_EXPR || code == REALPART_EXPR || code == COMPONENT_REF)
 997     {
 998       /* If the LHS of the compound reference is not a regular variable,
 999          recurse to keep looking for more operands in the subexpression.  */
1000       if (SSA_VAR_P (TREE_OPERAND (expr, 0)))
1001         add_stmt_operand (expr_p, stmt, flags, prev_vops);
1002       else
1003         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags, prev_vops);
1004
1005       return;
1006     }
1007
1008   /* Function calls.  Add every argument to USES.  If the callee is
1009      neither pure nor const, create a VDEF reference for GLOBAL_VAR
1010      (See find_vars_r).  */
1011   if (code == CALL_EXPR)
1012     {
1013       tree op;
1014       int call_flags = call_expr_flags (expr);
1015
1016       /* Find uses in the called function.  */
1017       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none, prev_vops);
1018
1019       for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
1020         get_expr_operands (stmt, &TREE_VALUE (op), opf_none, prev_vops);
1021
1022       get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none, prev_vops);
1023
1024       if (bitmap_first_set_bit (call_clobbered_vars) >= 0)
1025         {
1026           if (!(call_flags
1027                 & (ECF_PURE
1028                    | ECF_CONST
1029                    | ECF_NORETURN
1030                    | ECF_MALLOC
1031                    | ECF_MAY_BE_ALLOCA)))
1032             add_call_clobber_ops (stmt, prev_vops);
1033           else if (!(call_flags & (ECF_CONST | ECF_NORETURN)))
1034             add_call_read_ops (stmt, prev_vops);
1035         }
1036       else if (!aliases_computed_p)
1037         stmt_ann (stmt)->has_volatile_ops = true;
1038
1039       return;
1040     }
1041
1042   /* Lists.  */
1043   if (code == TREE_LIST)
1044     {
1045       tree op;
1046
1047       for (op = expr; op; op = TREE_CHAIN (op))
1048         get_expr_operands (stmt, &TREE_VALUE (op), flags, prev_vops);
1049
1050       return;
1051     }
1052
1053   /* Assignments.  */
1054   if (code == MODIFY_EXPR)
1055     {
1056       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none, prev_vops);
1057       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_is_def, prev_vops);
1058       return;
1059     }
1060
1061
1062   /* Mark VA_ARG_EXPR nodes as making volatile references.  FIXME,
1063      this is needed because we currently do not gimplify VA_ARG_EXPR
1064      properly.  */
1065   if (code == VA_ARG_EXPR)
1066     {
1067       stmt_ann (stmt)->has_volatile_ops = true;
1068       return;
1069     }
1070
1071   /* Unary expressions.  */
1072   if (class == '1'
1073       || code == TRUTH_NOT_EXPR
1074       || code == BIT_FIELD_REF
1075       || code == CONSTRUCTOR)
1076     {
1077       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags, prev_vops);
1078       return;
1079     }
1080
1081   /* Binary expressions.  */
1082   if (class == '2'
1083       || class == '<'
1084       || code == TRUTH_AND_EXPR
1085       || code == TRUTH_OR_EXPR
1086       || code == TRUTH_XOR_EXPR
1087       || code == COMPOUND_EXPR)
1088     {
1089       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags, prev_vops);
1090       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags, prev_vops);
1091       return;
1092     }
1093
1094   /* If we get here, something has gone wrong.  */
1095   fprintf (stderr, "unhandled expression in get_expr_operands():\n");
1096   debug_tree (expr);
1097   fputs ("\n", stderr);
1098   abort ();
1099 }
1100
1101
1102 /* Add *VAR_P to the appropriate operand array of STMT.  FLAGS is as in
1103    get_expr_operands.  If *VAR_P is a GIMPLE register, it will be added to
1104    the statement's real operands, otherwise it is added to virtual
1105    operands.
1106
1107    PREV_VOPS is used when adding virtual operands to statements that
1108       already had them (See append_vdef and append_vuse).  */
1109
1110 static void
1111 add_stmt_operand (tree *var_p, tree stmt, int flags, voperands_t prev_vops)
1112 {
1113   bool is_real_op;
1114   tree var, sym;
1115   stmt_ann_t s_ann;
1116   var_ann_t v_ann;
1117
1118   var = *var_p;
1119   STRIP_NOPS (var);
1120
1121   s_ann = stmt_ann (stmt);
1122
1123   /* If the operand is an ADDR_EXPR, add its operand to the list of
1124      variables that have had their address taken in this statement.  */
1125   if (TREE_CODE (var) == ADDR_EXPR)
1126     {
1127       note_addressable (TREE_OPERAND (var, 0), s_ann);
1128       return;
1129     }
1130
1131   /* If the original variable is not a scalar, it will be added to the list
1132      of virtual operands.  In that case, use its base symbol as the virtual
1133      variable representing it.  */
1134   is_real_op = is_gimple_reg (var);
1135   if (!is_real_op && !DECL_P (var))
1136     var = get_virtual_var (var);
1137
1138   /* If VAR is not a variable that we care to optimize, do nothing.  */
1139   if (var == NULL_TREE || !SSA_VAR_P (var))
1140     return;
1141
1142   sym = (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
1143   v_ann = var_ann (sym);
1144
1145   /* FIXME: We currently refuse to optimize variables that have hidden uses
1146      (variables used in VLA declarations, MD builtin calls and variables
1147      from the parent function in nested functions).  This is because not
1148      all uses of these variables are exposed in the IL or the statements
1149      that reference them are not in GIMPLE form.  If that's the case, mark
1150      the statement as having volatile operands and return.  */
1151   if (v_ann->has_hidden_use)
1152     {
1153       s_ann->has_volatile_ops = true;
1154       return;
1155     }
1156
1157   /* Don't expose volatile variables to the optimizers.  */
1158   if (TREE_THIS_VOLATILE (sym))
1159     {
1160       s_ann->has_volatile_ops = true;
1161       return;
1162     }
1163
1164   if (is_real_op)
1165     {
1166       /* The variable is a GIMPLE register.  Add it to real operands.  */
1167       if (flags & opf_is_def)
1168         append_def (var_p, stmt);
1169       else
1170         append_use (var_p, stmt);
1171     }
1172   else
1173     {
1174       varray_type aliases;
1175
1176       /* The variable is not a GIMPLE register.  Add it (or its aliases) to
1177          virtual operands, unless the caller has specifically requested
1178          not to add virtual operands (used when adding operands inside an
1179          ADDR_EXPR expression).  */
1180       if (flags & opf_no_vops)
1181         return;
1182
1183       aliases = v_ann->may_aliases;
1184
1185       /* If alias information hasn't been computed yet, then
1186          addressable variables will not be an alias tag nor will they
1187          have aliases.  In this case, mark the statement as having
1188          volatile operands.  */
1189       if (!aliases_computed_p && may_be_aliased (var))
1190         s_ann->has_volatile_ops = true;
1191
1192       if (aliases == NULL)
1193         {
1194           /* The variable is not aliased or it is an alias tag.  */
1195           if (flags & opf_is_def)
1196             {
1197               append_vdef (var, stmt, prev_vops);
1198               if (v_ann->is_alias_tag)
1199                 s_ann->makes_aliased_stores = 1;
1200             }
1201           else
1202             {
1203               append_vuse (var, stmt, prev_vops);
1204               if (v_ann->is_alias_tag)
1205                 s_ann->makes_aliased_loads = 1;
1206             }
1207         }
1208       else
1209         {
1210           size_t i;
1211
1212           /* The variable is aliased.  Add its aliases to the virtual
1213              operands.  */
1214           if (VARRAY_ACTIVE_SIZE (aliases) == 0)
1215             abort ();
1216
1217           if (flags & opf_is_def)
1218             {
1219               /* If the variable is also an alias tag, add a virtual
1220                  operand for it, otherwise we will miss representing
1221                  references to the members of the variable's alias set.
1222                  This fixes the bug in gcc.c-torture/execute/20020503-1.c.  */
1223               if (v_ann->is_alias_tag)
1224                 append_vdef (var, stmt, prev_vops);
1225
1226               for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
1227                 append_vdef (VARRAY_TREE (aliases, i), stmt, prev_vops);
1228
1229               s_ann->makes_aliased_stores = 1;
1230             }
1231           else
1232             {
1233               if (v_ann->is_alias_tag)
1234                 append_vuse (var, stmt, prev_vops);
1235
1236               for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
1237                 append_vuse (VARRAY_TREE (aliases, i), stmt, prev_vops);
1238
1239               s_ann->makes_aliased_loads = 1;
1240             }
1241         }
1242     }
1243 }
1244
1245 /* Record that VAR had its address taken in the statement with annotations
1246    S_ANN.  */
1247
1248 static void
1249 note_addressable (tree var, stmt_ann_t s_ann)
1250 {
1251   var = get_base_address (var);
1252   if (var && SSA_VAR_P (var))
1253     {
1254       if (s_ann->addresses_taken == NULL)
1255         s_ann->addresses_taken = BITMAP_GGC_ALLOC ();
1256       bitmap_set_bit (s_ann->addresses_taken, var_ann (var)->uid);
1257     }
1258 }
1259
1260
1261 /* Add clobbering definitions for .GLOBAL_VAR or for each of the call
1262    clobbered variables in the function.  */
1263
1264 static void
1265 add_call_clobber_ops (tree stmt, voperands_t prev_vops)
1266 {
1267   /* Functions that are not const, pure or never return may clobber
1268      call-clobbered variables.  */
1269   stmt_ann (stmt)->makes_clobbering_call = true;
1270
1271   /* If we had created .GLOBAL_VAR earlier, use it.  Otherwise, add a VDEF
1272      operand for every call clobbered variable.  See compute_may_aliases for
1273      the heuristic used to decide whether to create .GLOBAL_VAR or not.  */
1274   if (global_var)
1275     add_stmt_operand (&global_var, stmt, opf_is_def, prev_vops);
1276   else
1277     {
1278       size_t i;
1279
1280       EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i,
1281         {
1282           tree var = referenced_var (i);
1283
1284           /* If VAR is read-only, don't add a VDEF, just a VUSE operand.  */
1285           if (!TREE_READONLY (var))
1286             add_stmt_operand (&var, stmt, opf_is_def, prev_vops);
1287           else
1288             add_stmt_operand (&var, stmt, opf_none, prev_vops);
1289         });
1290     }
1291 }
1292
1293
1294 /* Add VUSE operands for .GLOBAL_VAR or all call clobbered variables in the
1295    function.  */
1296
1297 static void
1298 add_call_read_ops (tree stmt, voperands_t prev_vops)
1299 {
1300   /* Otherwise, if the function is not pure, it may reference memory.  Add
1301      a VUSE for .GLOBAL_VAR if it has been created.  Otherwise, add a VUSE
1302      for each call-clobbered variable.  See add_referenced_var for the
1303      heuristic used to decide whether to create .GLOBAL_VAR.  */
1304   if (global_var)
1305     add_stmt_operand (&global_var, stmt, opf_none, prev_vops);
1306   else
1307     {
1308       size_t i;
1309
1310       EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i,
1311         {
1312           tree var = referenced_var (i);
1313           add_stmt_operand (&var, stmt, opf_none, prev_vops);
1314         });
1315     }
1316 }
1317
1318 #include "gt-tree-ssa-operands.h"