gcc/tree-ssa-operands.c

   1 /* SSA operands management for trees.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "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 #include "toplev.h"
  35 #include "langhooks.h"
  36 #include "ipa-reference.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    The operand tree is the parsed by the various get_* routines which look
  54    through the stmt tree for the occurrence of operands which may be of
  55    interest, and calls are made to the append_* routines whenever one is
  56    found.  There are 4 of these routines, each representing one of the
  57    4 types of operands. Defs, Uses, Virtual Uses, and Virtual May Defs.
  58
  59    The append_* routines check for duplication, and simply keep a list of
  60    unique objects for each operand type in the build_* extendable vectors.
  61
  62    Once the stmt tree is completely parsed, the finalize_ssa_operands()
  63    routine is called, which proceeds to perform the finalization routine
  64    on each of the 4 operand vectors which have been built up.
  65
  66    If the stmt had a previous operand cache, the finalization routines
  67    attempt to match up the new operands with the old ones.  If it's a perfect
  68    match, the old vector is simply reused.  If it isn't a perfect match, then
  69    a new vector is created and the new operands are placed there.  For
  70    virtual operands, if the previous cache had SSA_NAME version of a
  71    variable, and that same variable occurs in the same operands cache, then
  72    the new cache vector will also get the same SSA_NAME.
  73
  74    i.e., if a stmt had a VUSE of 'a_5', and 'a' occurs in the new
  75    operand vector for VUSE, then the new vector will also be modified
  76    such that it contains 'a_5' rather than 'a'.  */
  77
  78 /* Structure storing statistics on how many call clobbers we have, and
  79    how many where avoided.  */
  80
  81 static struct
  82 {
  83   /* Number of call-clobbered ops we attempt to add to calls in
  84      add_call_clobbered_mem_symbols.  */
  85   unsigned int clobbered_vars;
  86
  87   /* Number of write-clobbers (VDEFs) avoided by using
  88      not_written information.  */
  89   unsigned int static_write_clobbers_avoided;
  90
  91   /* Number of reads (VUSEs) avoided by using not_read information.  */
  92   unsigned int static_read_clobbers_avoided;
  93
  94   /* Number of write-clobbers avoided because the variable can't escape to
  95      this call.  */
  96   unsigned int unescapable_clobbers_avoided;
  97
  98   /* Number of read-only uses we attempt to add to calls in
  99      add_call_read_mem_symbols.  */
 100   unsigned int readonly_clobbers;
 101
 102   /* Number of read-only uses we avoid using not_read information.  */
 103   unsigned int static_readonly_clobbers_avoided;
 104 } clobber_stats;
 105
 106
 107 /* Flags to describe operand properties in helpers.  */
 108
 109 /* By default, operands are loaded.  */
 110 #define opf_use         0
 111
 112 /* Operand is the target of an assignment expression or a
 113    call-clobbered variable.  */
 114 #define opf_def         (1 << 0)
 115
 116 /* No virtual operands should be created in the expression.  This is used
 117    when traversing ADDR_EXPR nodes which have different semantics than
 118    other expressions.  Inside an ADDR_EXPR node, the only operands that we
 119    need to consider are indices into arrays.  For instance, &a.b[i] should
 120    generate a USE of 'i' but it should not generate a VUSE for 'a' nor a
 121    VUSE for 'b'.  */
 122 #define opf_no_vops     (1 << 1)
 123
 124 /* Operand is an implicit reference.  This is used to distinguish
 125    explicit assignments in the form of MODIFY_EXPR from
 126    clobbering sites like function calls or ASM_EXPRs.  */
 127 #define opf_implicit    (1 << 2)
 128
 129 /* Array for building all the def operands.  */
 130 static VEC(tree,heap) *build_defs;
 131
 132 /* Array for building all the use operands.  */
 133 static VEC(tree,heap) *build_uses;
 134
 135 /* The built VDEF operand.  */
 136 static tree build_vdef;
 137
 138 /* The built VUSE operand.  */
 139 static tree build_vuse;
 140
 141 /* Bitmap obstack for our datastructures that needs to survive across
 142    compilations of multiple functions.  */
 143 static bitmap_obstack operands_bitmap_obstack;
 144
 145 static void get_expr_operands (gimple, tree *, int);
 146
 147 /* Number of functions with initialized ssa_operands.  */
 148 static int n_initialized = 0;
 149
 150 /* Return the DECL_UID of the base variable of T.  */
 151
 152 static inline unsigned
 153 get_name_decl (const_tree t)
 154 {
 155   if (TREE_CODE (t) != SSA_NAME)
 156     return DECL_UID (t);
 157   else
 158     return DECL_UID (SSA_NAME_VAR (t));
 159 }
 160
 161
 162 /*  Return true if the SSA operands cache is active.  */
 163
 164 bool
 165 ssa_operands_active (void)
 166 {
 167   /* This function may be invoked from contexts where CFUN is NULL
 168      (IPA passes), return false for now.  FIXME: operands may be
 169      active in each individual function, maybe this function should
 170      take CFUN as a parameter.  */
 171   if (cfun == NULL)
 172     return false;
 173
 174   return cfun->gimple_df && gimple_ssa_operands (cfun)->ops_active;
 175 }
 176
 177
 178 /* Create the VOP variable, an artificial global variable to act as a
 179    representative of all of the virtual operands FUD chain.  */
 180
 181 static void
 182 create_vop_var (void)
 183 {
 184   tree global_var;
 185
 186   gcc_assert (cfun->gimple_df->vop == NULL_TREE);
 187
 188   global_var = build_decl (VAR_DECL, get_identifier (".MEM"),
 189                            void_type_node);
 190   DECL_ARTIFICIAL (global_var) = 1;
 191   TREE_READONLY (global_var) = 0;
 192   DECL_EXTERNAL (global_var) = 1;
 193   TREE_STATIC (global_var) = 1;
 194   TREE_USED (global_var) = 1;
 195   DECL_CONTEXT (global_var) = NULL_TREE;
 196   TREE_THIS_VOLATILE (global_var) = 0;
 197   TREE_ADDRESSABLE (global_var) = 0;
 198
 199   create_var_ann (global_var);
 200   add_referenced_var (global_var);
 201   cfun->gimple_df->vop = global_var;
 202 }
 203
 204 /* These are the sizes of the operand memory buffer in bytes which gets
 205    allocated each time more operands space is required.  The final value is
 206    the amount that is allocated every time after that.
 207    In 1k we can fit 25 use operands (or 63 def operands) on a host with
 208    8 byte pointers, that would be 10 statements each with 1 def and 2
 209    uses.  */
 210
 211 #define OP_SIZE_INIT    0
 212 #define OP_SIZE_1       (1024 - sizeof (void *))
 213 #define OP_SIZE_2       (1024 * 4 - sizeof (void *))
 214 #define OP_SIZE_3       (1024 * 16 - sizeof (void *))
 215
 216 /* Initialize the operand cache routines.  */
 217
 218 void
 219 init_ssa_operands (void)
 220 {
 221   if (!n_initialized++)
 222     {
 223       build_defs = VEC_alloc (tree, heap, 5);
 224       build_uses = VEC_alloc (tree, heap, 10);
 225       build_vuse = NULL_TREE;
 226       build_vdef = NULL_TREE;
 227       bitmap_obstack_initialize (&operands_bitmap_obstack);
 228     }
 229
 230   gcc_assert (gimple_ssa_operands (cfun)->operand_memory == NULL);
 231   gimple_ssa_operands (cfun)->operand_memory_index
 232      = gimple_ssa_operands (cfun)->ssa_operand_mem_size;
 233   gimple_ssa_operands (cfun)->ops_active = true;
 234   memset (&clobber_stats, 0, sizeof (clobber_stats));
 235   gimple_ssa_operands (cfun)->ssa_operand_mem_size = OP_SIZE_INIT;
 236   create_vop_var ();
 237 }
 238
 239
 240 /* Dispose of anything required by the operand routines.  */
 241
 242 void
 243 fini_ssa_operands (void)
 244 {
 245   struct ssa_operand_memory_d *ptr;
 246
 247   if (!--n_initialized)
 248     {
 249       VEC_free (tree, heap, build_defs);
 250       VEC_free (tree, heap, build_uses);
 251       build_vdef = NULL_TREE;
 252       build_vuse = NULL_TREE;
 253     }
 254
 255   gimple_ssa_operands (cfun)->free_defs = NULL;
 256   gimple_ssa_operands (cfun)->free_uses = NULL;
 257
 258   while ((ptr = gimple_ssa_operands (cfun)->operand_memory) != NULL)
 259     {
 260       gimple_ssa_operands (cfun)->operand_memory
 261         = gimple_ssa_operands (cfun)->operand_memory->next;
 262       ggc_free (ptr);
 263     }
 264
 265   gimple_ssa_operands (cfun)->ops_active = false;
 266
 267   if (!n_initialized)
 268     bitmap_obstack_release (&operands_bitmap_obstack);
 269
 270   cfun->gimple_df->vop = NULL_TREE;
 271
 272   if (dump_file && (dump_flags & TDF_STATS))
 273     {
 274       fprintf (dump_file, "Original clobbered vars:           %d\n",
 275                clobber_stats.clobbered_vars);
 276       fprintf (dump_file, "Static write clobbers avoided:     %d\n",
 277                clobber_stats.static_write_clobbers_avoided);
 278       fprintf (dump_file, "Static read clobbers avoided:      %d\n",
 279                clobber_stats.static_read_clobbers_avoided);
 280       fprintf (dump_file, "Unescapable clobbers avoided:      %d\n",
 281                clobber_stats.unescapable_clobbers_avoided);
 282       fprintf (dump_file, "Original read-only clobbers:       %d\n",
 283                clobber_stats.readonly_clobbers);
 284       fprintf (dump_file, "Static read-only clobbers avoided: %d\n",
 285                clobber_stats.static_readonly_clobbers_avoided);
 286     }
 287 }
 288
 289
 290 /* Return memory for an operand of size SIZE.  */
 291
 292 static inline void *
 293 ssa_operand_alloc (unsigned size)
 294 {
 295   char *ptr;
 296
 297   gcc_assert (size == sizeof (struct use_optype_d)
 298               || size == sizeof (struct def_optype_d));
 299
 300   if (gimple_ssa_operands (cfun)->operand_memory_index + size
 301       >= gimple_ssa_operands (cfun)->ssa_operand_mem_size)
 302     {
 303       struct ssa_operand_memory_d *ptr;
 304
 305       switch (gimple_ssa_operands (cfun)->ssa_operand_mem_size)
 306         {
 307         case OP_SIZE_INIT:
 308           gimple_ssa_operands (cfun)->ssa_operand_mem_size = OP_SIZE_1;
 309           break;
 310         case OP_SIZE_1:
 311           gimple_ssa_operands (cfun)->ssa_operand_mem_size = OP_SIZE_2;
 312           break;
 313         case OP_SIZE_2:
 314         case OP_SIZE_3:
 315           gimple_ssa_operands (cfun)->ssa_operand_mem_size = OP_SIZE_3;
 316           break;
 317         default:
 318           gcc_unreachable ();
 319         }
 320
 321       ptr = (struct ssa_operand_memory_d *)
 322               ggc_alloc (sizeof (void *)
 323                          + gimple_ssa_operands (cfun)->ssa_operand_mem_size);
 324       ptr->next = gimple_ssa_operands (cfun)->operand_memory;
 325       gimple_ssa_operands (cfun)->operand_memory = ptr;
 326       gimple_ssa_operands (cfun)->operand_memory_index = 0;
 327     }
 328
 329   ptr = &(gimple_ssa_operands (cfun)->operand_memory
 330           ->mem[gimple_ssa_operands (cfun)->operand_memory_index]);
 331   gimple_ssa_operands (cfun)->operand_memory_index += size;
 332   return ptr;
 333 }
 334
 335
 336 /* Allocate a DEF operand.  */
 337
 338 static inline struct def_optype_d *
 339 alloc_def (void)
 340 {
 341   struct def_optype_d *ret;
 342   if (gimple_ssa_operands (cfun)->free_defs)
 343     {
 344       ret = gimple_ssa_operands (cfun)->free_defs;
 345       gimple_ssa_operands (cfun)->free_defs
 346         = gimple_ssa_operands (cfun)->free_defs->next;
 347     }
 348   else
 349     ret = (struct def_optype_d *)
 350           ssa_operand_alloc (sizeof (struct def_optype_d));
 351   return ret;
 352 }
 353
 354
 355 /* Allocate a USE operand.  */
 356
 357 static inline struct use_optype_d *
 358 alloc_use (void)
 359 {
 360   struct use_optype_d *ret;
 361   if (gimple_ssa_operands (cfun)->free_uses)
 362     {
 363       ret = gimple_ssa_operands (cfun)->free_uses;
 364       gimple_ssa_operands (cfun)->free_uses
 365         = gimple_ssa_operands (cfun)->free_uses->next;
 366     }
 367   else
 368     ret = (struct use_optype_d *)
 369           ssa_operand_alloc (sizeof (struct use_optype_d));
 370   return ret;
 371 }
 372
 373
 374 /* Adds OP to the list of defs after LAST.  */
 375
 376 static inline def_optype_p
 377 add_def_op (tree *op, def_optype_p last)
 378 {
 379   def_optype_p new_def;
 380
 381   new_def = alloc_def ();
 382   DEF_OP_PTR (new_def) = op;
 383   last->next = new_def;
 384   new_def->next = NULL;
 385   return new_def;
 386 }
 387
 388
 389 /* Adds OP to the list of uses of statement STMT after LAST.  */
 390
 391 static inline use_optype_p
 392 add_use_op (gimple stmt, tree *op, use_optype_p last)
 393 {
 394   use_optype_p new_use;
 395
 396   new_use = alloc_use ();
 397   USE_OP_PTR (new_use)->use = op;
 398   link_imm_use_stmt (USE_OP_PTR (new_use), *op, stmt);
 399   last->next = new_use;
 400   new_use->next = NULL;
 401   return new_use;
 402 }
 403
 404
 405
 406 /* Takes elements from build_defs and turns them into def operands of STMT.
 407    TODO -- Make build_defs VEC of tree *.  */
 408
 409 static inline void
 410 finalize_ssa_defs (gimple stmt)
 411 {
 412   unsigned new_i;
 413   struct def_optype_d new_list;
 414   def_optype_p old_ops, last;
 415   unsigned int num = VEC_length (tree, build_defs);
 416
 417   /* There should only be a single real definition per assignment.  */
 418   gcc_assert ((stmt && gimple_code (stmt) != GIMPLE_ASSIGN) || num <= 1);
 419
 420   /* Pre-pend the vdef we may have built.  */
 421   if (build_vdef != NULL_TREE)
 422     {
 423       tree oldvdef = gimple_vdef (stmt);
 424       if (oldvdef
 425           && TREE_CODE (oldvdef) == SSA_NAME)
 426         oldvdef = SSA_NAME_VAR (oldvdef);
 427       if (oldvdef != build_vdef)
 428         gimple_set_vdef (stmt, build_vdef);
 429       VEC_safe_insert (tree, heap, build_defs, 0, (tree)gimple_vdef_ptr (stmt));
 430       ++num;
 431     }
 432
 433   new_list.next = NULL;
 434   last = &new_list;
 435
 436   old_ops = gimple_def_ops (stmt);
 437
 438   new_i = 0;
 439
 440   /* Clear and unlink a no longer necessary VDEF.  */
 441   if (build_vdef == NULL_TREE
 442       && gimple_vdef (stmt) != NULL_TREE)
 443     {
 444       if (TREE_CODE (gimple_vdef (stmt)) == SSA_NAME)
 445         {
 446           unlink_stmt_vdef (stmt);
 447           release_ssa_name (gimple_vdef (stmt));
 448         }
 449       gimple_set_vdef (stmt, NULL_TREE);
 450     }
 451
 452   /* If we have a non-SSA_NAME VDEF, mark it for renaming.  */
 453   if (gimple_vdef (stmt)
 454       && TREE_CODE (gimple_vdef (stmt)) != SSA_NAME)
 455     mark_sym_for_renaming (gimple_vdef (stmt));
 456
 457   /* Check for the common case of 1 def that hasn't changed.  */
 458   if (old_ops && old_ops->next == NULL && num == 1
 459       && (tree *) VEC_index (tree, build_defs, 0) == DEF_OP_PTR (old_ops))
 460     return;
 461
 462   /* If there is anything in the old list, free it.  */
 463   if (old_ops)
 464     {
 465       old_ops->next = gimple_ssa_operands (cfun)->free_defs;
 466       gimple_ssa_operands (cfun)->free_defs = old_ops;
 467     }
 468
 469   /* If there is anything remaining in the build_defs list, simply emit it.  */
 470   for ( ; new_i < num; new_i++)
 471     last = add_def_op ((tree *) VEC_index (tree, build_defs, new_i), last);
 472
 473   /* Now set the stmt's operands.  */
 474   gimple_set_def_ops (stmt, new_list.next);
 475 }
 476
 477
 478 /* Takes elements from build_uses and turns them into use operands of STMT.
 479    TODO -- Make build_uses VEC of tree *.  */
 480
 481 static inline void
 482 finalize_ssa_uses (gimple stmt)
 483 {
 484   unsigned new_i;
 485   struct use_optype_d new_list;
 486   use_optype_p old_ops, ptr, last;
 487
 488   /* Pre-pend the VUSE we may have built.  */
 489   if (build_vuse != NULL_TREE)
 490     {
 491       tree oldvuse = gimple_vuse (stmt);
 492       if (oldvuse
 493           && TREE_CODE (oldvuse) == SSA_NAME)
 494         oldvuse = SSA_NAME_VAR (oldvuse);
 495       if (oldvuse != (build_vuse != NULL_TREE
 496                       ? build_vuse : build_vdef))
 497         gimple_set_vuse (stmt, NULL_TREE);
 498       VEC_safe_insert (tree, heap, build_uses, 0, (tree)gimple_vuse_ptr (stmt));
 499     }
 500
 501   new_list.next = NULL;
 502   last = &new_list;
 503
 504   old_ops = gimple_use_ops (stmt);
 505
 506   /* Clear a no longer necessary VUSE.  */
 507   if (build_vuse == NULL_TREE
 508       && gimple_vuse (stmt) != NULL_TREE)
 509     gimple_set_vuse (stmt, NULL_TREE);
 510
 511   /* If there is anything in the old list, free it.  */
 512   if (old_ops)
 513     {
 514       for (ptr = old_ops; ptr; ptr = ptr->next)
 515         delink_imm_use (USE_OP_PTR (ptr));
 516       old_ops->next = gimple_ssa_operands (cfun)->free_uses;
 517       gimple_ssa_operands (cfun)->free_uses = old_ops;
 518     }
 519
 520   /* If we added a VUSE, make sure to set the operand if it is not already
 521      present and mark it for renaming.  */
 522   if (build_vuse != NULL_TREE
 523       && gimple_vuse (stmt) == NULL_TREE)
 524     {
 525       gimple_set_vuse (stmt, gimple_vop (cfun));
 526       mark_sym_for_renaming (gimple_vop (cfun));
 527     }
 528
 529   /* Now create nodes for all the new nodes.  */
 530   for (new_i = 0; new_i < VEC_length (tree, build_uses); new_i++)
 531     last = add_use_op (stmt,
 532                        (tree *) VEC_index (tree, build_uses, new_i),
 533                        last);
 534
 535   /* Now set the stmt's operands.  */
 536   gimple_set_use_ops (stmt, new_list.next);
 537 }
 538
 539
 540 /* Clear the in_list bits and empty the build array for VDEFs and
 541    VUSEs.  */
 542
 543 static inline void
 544 cleanup_build_arrays (void)
 545 {
 546   build_vdef = NULL_TREE;
 547   build_vuse = NULL_TREE;
 548   VEC_truncate (tree, build_defs, 0);
 549   VEC_truncate (tree, build_uses, 0);
 550 }
 551
 552
 553 /* Finalize all the build vectors, fill the new ones into INFO.  */
 554
 555 static inline void
 556 finalize_ssa_stmt_operands (gimple stmt)
 557 {
 558   finalize_ssa_defs (stmt);
 559   finalize_ssa_uses (stmt);
 560   cleanup_build_arrays ();
 561 }
 562
 563
 564 /* Start the process of building up operands vectors in INFO.  */
 565
 566 static inline void
 567 start_ssa_stmt_operands (void)
 568 {
 569   gcc_assert (VEC_length (tree, build_defs) == 0);
 570   gcc_assert (VEC_length (tree, build_uses) == 0);
 571   gcc_assert (build_vuse == NULL_TREE);
 572   gcc_assert (build_vdef == NULL_TREE);
 573 }
 574
 575
 576 /* Add DEF_P to the list of pointers to operands.  */
 577
 578 static inline void
 579 append_def (tree *def_p)
 580 {
 581   VEC_safe_push (tree, heap, build_defs, (tree) def_p);
 582 }
 583
 584
 585 /* Add USE_P to the list of pointers to operands.  */
 586
 587 static inline void
 588 append_use (tree *use_p)
 589 {
 590   VEC_safe_push (tree, heap, build_uses, (tree) use_p);
 591 }
 592
 593
 594 /* Add VAR to the set of variables that require a VDEF operator.  */
 595
 596 static inline void
 597 append_vdef (tree var)
 598 {
 599   if (!optimize)
 600     return;
 601
 602   gcc_assert ((build_vdef == NULL_TREE
 603                || build_vdef == var)
 604               && (build_vuse == NULL_TREE
 605                   || build_vuse == var));
 606
 607   build_vdef = var;
 608   build_vuse = var;
 609 }
 610
 611
 612 /* Add VAR to the set of variables that require a VUSE operator.  */
 613
 614 static inline void
 615 append_vuse (tree var)
 616 {
 617   if (!optimize)
 618     return;
 619
 620   gcc_assert (build_vuse == NULL_TREE
 621               || build_vuse == var);
 622
 623   build_vuse = var;
 624 }
 625
 626 /* Add virtual operands for STMT.  FLAGS is as in get_expr_operands.  */
 627
 628 static void
 629 add_virtual_operand (gimple stmt ATTRIBUTE_UNUSED, int flags)
 630 {
 631   /* Add virtual operands to the stmt, unless the caller has specifically
 632      requested not to do that (used when adding operands inside an
 633      ADDR_EXPR expression).  */
 634   if (flags & opf_no_vops)
 635     return;
 636
 637   if (flags & opf_def)
 638     append_vdef (gimple_vop (cfun));
 639   else
 640     append_vuse (gimple_vop (cfun));
 641 }
 642
 643
 644 /* Add *VAR_P to the appropriate operand array for statement STMT.
 645    FLAGS is as in get_expr_operands.  If *VAR_P is a GIMPLE register,
 646    it will be added to the statement's real operands, otherwise it is
 647    added to virtual operands.  */
 648
 649 static void
 650 add_stmt_operand (tree *var_p, gimple stmt, int flags)
 651 {
 652   tree var, sym;
 653   var_ann_t v_ann;
 654
 655   gcc_assert (SSA_VAR_P (*var_p));
 656
 657   var = *var_p;
 658   sym = (TREE_CODE (var) == SSA_NAME ? SSA_NAME_VAR (var) : var);
 659   v_ann = var_ann (sym);
 660
 661   /* Mark statements with volatile operands.  */
 662   if (TREE_THIS_VOLATILE (sym))
 663     gimple_set_has_volatile_ops (stmt, true);
 664
 665   if (is_gimple_reg (sym))
 666     {
 667       /* The variable is a GIMPLE register.  Add it to real operands.  */
 668       if (flags & opf_def)
 669         append_def (var_p);
 670       else
 671         append_use (var_p);
 672     }
 673   else
 674     add_virtual_operand (stmt, flags);
 675 }
 676
 677 /* Mark the base address of REF as having its address taken.
 678    REF may be a single variable whose address has been taken or any
 679    other valid GIMPLE memory reference (structure reference, array,
 680    etc).  */
 681
 682 static void
 683 mark_address_taken (tree ref)
 684 {
 685   tree var;
 686
 687   /* Note that it is *NOT OKAY* to use the target of a COMPONENT_REF
 688      as the only thing we take the address of.  If VAR is a structure,
 689      taking the address of a field means that the whole structure may
 690      be referenced using pointer arithmetic.  See PR 21407 and the
 691      ensuing mailing list discussion.  */
 692   var = get_base_address (ref);
 693   if (var && DECL_P (var))
 694     TREE_ADDRESSABLE (var) = 1;
 695 }
 696
 697
 698 /* A subroutine of get_expr_operands to handle INDIRECT_REF,
 699    ALIGN_INDIRECT_REF and MISALIGNED_INDIRECT_REF.
 700
 701    STMT is the statement being processed, EXPR is the INDIRECT_REF
 702       that got us here.
 703
 704    FLAGS is as in get_expr_operands.
 705
 706    RECURSE_ON_BASE should be set to true if we want to continue
 707       calling get_expr_operands on the base pointer, and false if
 708       something else will do it for us.  */
 709
 710 static void
 711 get_indirect_ref_operands (gimple stmt, tree expr, int flags,
 712                            bool recurse_on_base)
 713 {
 714   tree *pptr = &TREE_OPERAND (expr, 0);
 715
 716   if (TREE_THIS_VOLATILE (expr))
 717     gimple_set_has_volatile_ops (stmt, true);
 718
 719   /* Add the VOP.  */
 720   add_virtual_operand (stmt, flags);
 721
 722   /* If requested, add a USE operand for the base pointer.  */
 723   if (recurse_on_base)
 724     get_expr_operands (stmt, pptr, opf_use);
 725 }
 726
 727
 728 /* A subroutine of get_expr_operands to handle TARGET_MEM_REF.  */
 729
 730 static void
 731 get_tmr_operands (gimple stmt, tree expr, int flags)
 732 {
 733   /* First record the real operands.  */
 734   get_expr_operands (stmt, &TMR_BASE (expr), opf_use);
 735   get_expr_operands (stmt, &TMR_INDEX (expr), opf_use);
 736
 737   if (TMR_SYMBOL (expr))
 738     mark_address_taken (TMR_SYMBOL (expr));
 739
 740   add_virtual_operand (stmt, flags);
 741 }
 742
 743
 744 /* If STMT is a call that may clobber globals and other symbols that
 745    escape, add them to the VDEF/VUSE lists for it.  */
 746
 747 static void
 748 maybe_add_call_vops (gimple stmt)
 749 {
 750   int call_flags = gimple_call_flags (stmt);
 751
 752   /* If aliases have been computed already, add VDEF or VUSE
 753      operands for all the symbols that have been found to be
 754      call-clobbered.  */
 755   if (!(call_flags & ECF_NOVOPS))
 756     {
 757       /* A 'pure' or a 'const' function never call-clobbers anything.
 758          A 'noreturn' function might, but since we don't return anyway
 759          there is no point in recording that.  */
 760       if (!(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
 761         add_virtual_operand (stmt, opf_def);
 762       else if (!(call_flags & ECF_CONST))
 763         add_virtual_operand (stmt, opf_use);
 764     }
 765 }
 766
 767
 768 /* Scan operands in the ASM_EXPR stmt referred to in INFO.  */
 769
 770 static void
 771 get_asm_expr_operands (gimple stmt)
 772 {
 773   size_t i, noutputs;
 774   const char **oconstraints;
 775   const char *constraint;
 776   bool allows_mem, allows_reg, is_inout;
 777
 778   noutputs = gimple_asm_noutputs (stmt);
 779   oconstraints = (const char **) alloca ((noutputs) * sizeof (const char *));
 780
 781   /* Gather all output operands.  */
 782   for (i = 0; i < gimple_asm_noutputs (stmt); i++)
 783     {
 784       tree link = gimple_asm_output_op (stmt, i);
 785       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 786       oconstraints[i] = constraint;
 787       parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
 788                                &allows_reg, &is_inout);
 789
 790       /* This should have been split in gimplify_asm_expr.  */
 791       gcc_assert (!allows_reg || !is_inout);
 792
 793       /* Memory operands are addressable.  Note that STMT needs the
 794          address of this operand.  */
 795       if (!allows_reg && allows_mem)
 796         {
 797           tree t = get_base_address (TREE_VALUE (link));
 798           if (t && DECL_P (t))
 799             mark_address_taken (t);
 800         }
 801
 802       get_expr_operands (stmt, &TREE_VALUE (link), opf_def);
 803     }
 804
 805   /* Gather all input operands.  */
 806   for (i = 0; i < gimple_asm_ninputs (stmt); i++)
 807     {
 808       tree link = gimple_asm_input_op (stmt, i);
 809       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 810       parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints,
 811                               &allows_mem, &allows_reg);
 812
 813       /* Memory operands are addressable.  Note that STMT needs the
 814          address of this operand.  */
 815       if (!allows_reg && allows_mem)
 816         {
 817           tree t = get_base_address (TREE_VALUE (link));
 818           if (t && DECL_P (t))
 819             mark_address_taken (t);
 820         }
 821
 822       get_expr_operands (stmt, &TREE_VALUE (link), 0);
 823     }
 824
 825   /* Clobber all memory and addressable symbols for asm ("" : : : "memory");  */
 826   for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
 827     {
 828       tree link = gimple_asm_clobber_op (stmt, i);
 829       if (strcmp (TREE_STRING_POINTER (TREE_VALUE (link)), "memory") == 0)
 830         {
 831           add_virtual_operand (stmt, opf_def);
 832           break;
 833         }
 834     }
 835 }
 836
 837
 838 /* Recursively scan the expression pointed to by EXPR_P in statement
 839    STMT.  FLAGS is one of the OPF_* constants modifying how to
 840    interpret the operands found.  */
 841
 842 static void
 843 get_expr_operands (gimple stmt, tree *expr_p, int flags)
 844 {
 845   enum tree_code code;
 846   enum tree_code_class codeclass;
 847   tree expr = *expr_p;
 848
 849   if (expr == NULL)
 850     return;
 851
 852   code = TREE_CODE (expr);
 853   codeclass = TREE_CODE_CLASS (code);
 854
 855   switch (code)
 856     {
 857     case ADDR_EXPR:
 858       /* Taking the address of a variable does not represent a
 859          reference to it, but the fact that the statement takes its
 860          address will be of interest to some passes (e.g. alias
 861          resolution).  */
 862       mark_address_taken (TREE_OPERAND (expr, 0));
 863
 864       /* If the address is invariant, there may be no interesting
 865          variable references inside.  */
 866       if (is_gimple_min_invariant (expr))
 867         return;
 868
 869       /* Otherwise, there may be variables referenced inside but there
 870          should be no VUSEs created, since the referenced objects are
 871          not really accessed.  The only operands that we should find
 872          here are ARRAY_REF indices which will always be real operands
 873          (GIMPLE does not allow non-registers as array indices).  */
 874       flags |= opf_no_vops;
 875       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
 876       return;
 877
 878     case SSA_NAME:
 879      add_stmt_operand (expr_p, stmt, flags);
 880      return;
 881
 882     case VAR_DECL:
 883     case PARM_DECL:
 884     case RESULT_DECL:
 885       add_stmt_operand (expr_p, stmt, flags);
 886       return;
 887
 888     case MISALIGNED_INDIRECT_REF:
 889       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
 890       /* fall through */
 891
 892     case ALIGN_INDIRECT_REF:
 893     case INDIRECT_REF:
 894       get_indirect_ref_operands (stmt, expr, flags, true);
 895       return;
 896
 897     case TARGET_MEM_REF:
 898       get_tmr_operands (stmt, expr, flags);
 899       return;
 900
 901     case ARRAY_REF:
 902     case ARRAY_RANGE_REF:
 903     case COMPONENT_REF:
 904     case REALPART_EXPR:
 905     case IMAGPART_EXPR:
 906       {
 907         tree ref;
 908         HOST_WIDE_INT offset, size, maxsize;
 909
 910         if (TREE_THIS_VOLATILE (expr))
 911           gimple_set_has_volatile_ops (stmt, true);
 912
 913         ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
 914         if (TREE_CODE (ref) == INDIRECT_REF)
 915           {
 916             get_indirect_ref_operands (stmt, ref, flags, false);
 917             flags |= opf_no_vops;
 918           }
 919
 920         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
 921
 922         if (code == COMPONENT_REF)
 923           {
 924             if (TREE_THIS_VOLATILE (TREE_OPERAND (expr, 1)))
 925               gimple_set_has_volatile_ops (stmt, true);
 926             get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
 927           }
 928         else if (code == ARRAY_REF || code == ARRAY_RANGE_REF)
 929           {
 930             get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
 931             get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
 932             get_expr_operands (stmt, &TREE_OPERAND (expr, 3), opf_use);
 933           }
 934
 935         return;
 936       }
 937
 938     case WITH_SIZE_EXPR:
 939       /* WITH_SIZE_EXPR is a pass-through reference to its first argument,
 940          and an rvalue reference to its second argument.  */
 941       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
 942       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
 943       return;
 944
 945     case COND_EXPR:
 946     case VEC_COND_EXPR:
 947       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_use);
 948       get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_use);
 949       get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_use);
 950       return;
 951
 952     case CONSTRUCTOR:
 953       {
 954         /* General aggregate CONSTRUCTORs have been decomposed, but they
 955            are still in use as the COMPLEX_EXPR equivalent for vectors.  */
 956         constructor_elt *ce;
 957         unsigned HOST_WIDE_INT idx;
 958
 959         for (idx = 0;
 960              VEC_iterate (constructor_elt, CONSTRUCTOR_ELTS (expr), idx, ce);
 961              idx++)
 962           get_expr_operands (stmt, &ce->value, opf_use);
 963
 964         return;
 965       }
 966
 967     case BIT_FIELD_REF:
 968       if (TREE_THIS_VOLATILE (expr))
 969         gimple_set_has_volatile_ops (stmt, true);
 970       /* FALLTHRU */
 971
 972     case TRUTH_NOT_EXPR:
 973     case VIEW_CONVERT_EXPR:
 974     do_unary:
 975       get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
 976       return;
 977
 978     case TRUTH_AND_EXPR:
 979     case TRUTH_OR_EXPR:
 980     case TRUTH_XOR_EXPR:
 981     case COMPOUND_EXPR:
 982     case OBJ_TYPE_REF:
 983     case ASSERT_EXPR:
 984     do_binary:
 985       {
 986         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
 987         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
 988         return;
 989       }
 990
 991     case DOT_PROD_EXPR:
 992     case REALIGN_LOAD_EXPR:
 993       {
 994         get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
 995         get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
 996         get_expr_operands (stmt, &TREE_OPERAND (expr, 2), flags);
 997         return;
 998       }
 999
1000     case FUNCTION_DECL:
1001     case LABEL_DECL:
1002     case CONST_DECL:
1003     case CASE_LABEL_EXPR:
1004     case FILTER_EXPR:
1005     case EXC_PTR_EXPR:
1006       /* Expressions that make no memory references.  */
1007       return;
1008
1009     default:
1010       if (codeclass == tcc_unary)
1011         goto do_unary;
1012       if (codeclass == tcc_binary || codeclass == tcc_comparison)
1013         goto do_binary;
1014       if (codeclass == tcc_constant || codeclass == tcc_type)
1015         return;
1016     }
1017
1018   /* If we get here, something has gone wrong.  */
1019 #ifdef ENABLE_CHECKING
1020   fprintf (stderr, "unhandled expression in get_expr_operands():\n");
1021   debug_tree (expr);
1022   fputs ("\n", stderr);
1023 #endif
1024   gcc_unreachable ();
1025 }
1026
1027
1028 /* Parse STMT looking for operands.  When finished, the various
1029    build_* operand vectors will have potential operands in them.  */
1030
1031 static void
1032 parse_ssa_operands (gimple stmt)
1033 {
1034   enum gimple_code code = gimple_code (stmt);
1035
1036   if (code == GIMPLE_ASM)
1037     get_asm_expr_operands (stmt);
1038   else
1039     {
1040       size_t i, start = 0;
1041
1042       if (code == GIMPLE_ASSIGN || code == GIMPLE_CALL)
1043         {
1044           get_expr_operands (stmt, gimple_op_ptr (stmt, 0), opf_def);
1045           start = 1;
1046         }
1047
1048       for (i = start; i < gimple_num_ops (stmt); i++)
1049         get_expr_operands (stmt, gimple_op_ptr (stmt, i), opf_use);
1050
1051       /* Add call-clobbered operands, if needed.  */
1052       if (code == GIMPLE_CALL)
1053         maybe_add_call_vops (stmt);
1054     }
1055 }
1056
1057
1058 /* Create an operands cache for STMT.  */
1059
1060 static void
1061 build_ssa_operands (gimple stmt)
1062 {
1063   /* Initially assume that the statement has no volatile operands.  */
1064   gimple_set_has_volatile_ops (stmt, false);
1065
1066   start_ssa_stmt_operands ();
1067   parse_ssa_operands (stmt);
1068   finalize_ssa_stmt_operands (stmt);
1069 }
1070
1071
1072 /* Releases the operands of STMT back to their freelists, and clears
1073    the stmt operand lists.  */
1074
1075 void
1076 free_stmt_operands (gimple stmt)
1077 {
1078   def_optype_p defs = gimple_def_ops (stmt), last_def;
1079   use_optype_p uses = gimple_use_ops (stmt), last_use;
1080
1081   if (defs)
1082     {
1083       for (last_def = defs; last_def->next; last_def = last_def->next)
1084         continue;
1085       last_def->next = gimple_ssa_operands (cfun)->free_defs;
1086       gimple_ssa_operands (cfun)->free_defs = defs;
1087       gimple_set_def_ops (stmt, NULL);
1088     }
1089
1090   if (uses)
1091     {
1092       for (last_use = uses; last_use->next; last_use = last_use->next)
1093         delink_imm_use (USE_OP_PTR (last_use));
1094       delink_imm_use (USE_OP_PTR (last_use));
1095       last_use->next = gimple_ssa_operands (cfun)->free_uses;
1096       gimple_ssa_operands (cfun)->free_uses = uses;
1097       gimple_set_use_ops (stmt, NULL);
1098     }
1099
1100   if (gimple_has_mem_ops (stmt))
1101     {
1102       gimple_set_vuse (stmt, NULL_TREE);
1103       gimple_set_vdef (stmt, NULL_TREE);
1104     }
1105 }
1106
1107
1108 /* Get the operands of statement STMT.  */
1109
1110 void
1111 update_stmt_operands (gimple stmt)
1112 {
1113   /* If update_stmt_operands is called before SSA is initialized, do
1114      nothing.  */
1115   if (!ssa_operands_active ())
1116     return;
1117
1118   timevar_push (TV_TREE_OPS);
1119
1120   gcc_assert (gimple_modified_p (stmt));
1121   build_ssa_operands (stmt);
1122   gimple_set_modified (stmt, false);
1123
1124   timevar_pop (TV_TREE_OPS);
1125 }
1126
1127
1128 /* Swap operands EXP0 and EXP1 in statement STMT.  No attempt is done
1129    to test the validity of the swap operation.  */
1130
1131 void
1132 swap_tree_operands (gimple stmt, tree *exp0, tree *exp1)
1133 {
1134   tree op0, op1;
1135   op0 = *exp0;
1136   op1 = *exp1;
1137
1138   /* If the operand cache is active, attempt to preserve the relative
1139      positions of these two operands in their respective immediate use
1140      lists.  */
1141   if (ssa_operands_active () && op0 != op1)
1142     {
1143       use_optype_p use0, use1, ptr;
1144       use0 = use1 = NULL;
1145
1146       /* Find the 2 operands in the cache, if they are there.  */
1147       for (ptr = gimple_use_ops (stmt); ptr; ptr = ptr->next)
1148         if (USE_OP_PTR (ptr)->use == exp0)
1149           {
1150             use0 = ptr;
1151             break;
1152           }
1153
1154       for (ptr = gimple_use_ops (stmt); ptr; ptr = ptr->next)
1155         if (USE_OP_PTR (ptr)->use == exp1)
1156           {
1157             use1 = ptr;
1158             break;
1159           }
1160
1161       /* If both uses don't have operand entries, there isn't much we can do
1162          at this point.  Presumably we don't need to worry about it.  */
1163       if (use0 && use1)
1164         {
1165           tree *tmp = USE_OP_PTR (use1)->use;
1166           USE_OP_PTR (use1)->use = USE_OP_PTR (use0)->use;
1167           USE_OP_PTR (use0)->use = tmp;
1168         }
1169     }
1170
1171   /* Now swap the data.  */
1172   *exp0 = op1;
1173   *exp1 = op0;
1174 }
1175
1176
1177 /* Scan the immediate_use list for VAR making sure its linked properly.
1178    Return TRUE if there is a problem and emit an error message to F.  */
1179
1180 bool
1181 verify_imm_links (FILE *f, tree var)
1182 {
1183   use_operand_p ptr, prev, list;
1184   int count;
1185
1186   gcc_assert (TREE_CODE (var) == SSA_NAME);
1187
1188   list = &(SSA_NAME_IMM_USE_NODE (var));
1189   gcc_assert (list->use == NULL);
1190
1191   if (list->prev == NULL)
1192     {
1193       gcc_assert (list->next == NULL);
1194       return false;
1195     }
1196
1197   prev = list;
1198   count = 0;
1199   for (ptr = list->next; ptr != list; )
1200     {
1201       if (prev != ptr->prev)
1202         goto error;
1203
1204       if (ptr->use == NULL)
1205         goto error; /* 2 roots, or SAFE guard node.  */
1206       else if (*(ptr->use) != var)
1207         goto error;
1208
1209       prev = ptr;
1210       ptr = ptr->next;
1211
1212       /* Avoid infinite loops.  50,000,000 uses probably indicates a
1213          problem.  */
1214       if (count++ > 50000000)
1215         goto error;
1216     }
1217
1218   /* Verify list in the other direction.  */
1219   prev = list;
1220   for (ptr = list->prev; ptr != list; )
1221     {
1222       if (prev != ptr->next)
1223         goto error;
1224       prev = ptr;
1225       ptr = ptr->prev;
1226       if (count-- < 0)
1227         goto error;
1228     }
1229
1230   if (count != 0)
1231     goto error;
1232
1233   return false;
1234
1235  error:
1236   if (ptr->loc.stmt && gimple_modified_p (ptr->loc.stmt))
1237     {
1238       fprintf (f, " STMT MODIFIED. - <%p> ", (void *)ptr->loc.stmt);
1239       print_gimple_stmt (f, ptr->loc.stmt, 0, TDF_SLIM);
1240     }
1241   fprintf (f, " IMM ERROR : (use_p : tree - %p:%p)", (void *)ptr,
1242            (void *)ptr->use);
1243   print_generic_expr (f, USE_FROM_PTR (ptr), TDF_SLIM);
1244   fprintf(f, "\n");
1245   return true;
1246 }
1247
1248
1249 /* Dump all the immediate uses to FILE.  */
1250
1251 void
1252 dump_immediate_uses_for (FILE *file, tree var)
1253 {
1254   imm_use_iterator iter;
1255   use_operand_p use_p;
1256
1257   gcc_assert (var && TREE_CODE (var) == SSA_NAME);
1258
1259   print_generic_expr (file, var, TDF_SLIM);
1260   fprintf (file, " : -->");
1261   if (has_zero_uses (var))
1262     fprintf (file, " no uses.\n");
1263   else
1264     if (has_single_use (var))
1265       fprintf (file, " single use.\n");
1266     else
1267       fprintf (file, "%d uses.\n", num_imm_uses (var));
1268
1269   FOR_EACH_IMM_USE_FAST (use_p, iter, var)
1270     {
1271       if (use_p->loc.stmt == NULL && use_p->use == NULL)
1272         fprintf (file, "***end of stmt iterator marker***\n");
1273       else
1274         if (!is_gimple_reg (USE_FROM_PTR (use_p)))
1275           print_gimple_stmt (file, USE_STMT (use_p), 0, TDF_VOPS|TDF_MEMSYMS);
1276         else
1277           print_gimple_stmt (file, USE_STMT (use_p), 0, TDF_SLIM);
1278     }
1279   fprintf(file, "\n");
1280 }
1281
1282
1283 /* Dump all the immediate uses to FILE.  */
1284
1285 void
1286 dump_immediate_uses (FILE *file)
1287 {
1288   tree var;
1289   unsigned int x;
1290
1291   fprintf (file, "Immediate_uses: \n\n");
1292   for (x = 1; x < num_ssa_names; x++)
1293     {
1294       var = ssa_name(x);
1295       if (!var)
1296         continue;
1297       dump_immediate_uses_for (file, var);
1298     }
1299 }
1300
1301
1302 /* Dump def-use edges on stderr.  */
1303
1304 void
1305 debug_immediate_uses (void)
1306 {
1307   dump_immediate_uses (stderr);
1308 }
1309
1310
1311 /* Dump def-use edges on stderr.  */
1312
1313 void
1314 debug_immediate_uses_for (tree var)
1315 {
1316   dump_immediate_uses_for (stderr, var);
1317 }
1318
1319
1320 /* Unlink STMTs virtual definition from the IL by propagating its use.  */
1321
1322 void
1323 unlink_stmt_vdef (gimple stmt)
1324 {
1325   use_operand_p use_p;
1326   imm_use_iterator iter;
1327   gimple use_stmt;
1328   tree vdef = gimple_vdef (stmt);
1329
1330   if (!vdef
1331       || TREE_CODE (vdef) != SSA_NAME)
1332     return;
1333
1334   FOR_EACH_IMM_USE_STMT (use_stmt, iter, gimple_vdef (stmt))
1335     {
1336       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1337         SET_USE (use_p, gimple_vuse (stmt));
1338     }
1339
1340   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_vdef (stmt)))
1341     SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_vuse (stmt)) = 1;
1342 }
1343