gcc/tree-ssa-ter.c

   1 /* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
   3    Inc.
   4    Contributed by Andrew MacLeod  <amacleod@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "diagnostic.h"
  29 #include "bitmap.h"
  30 #include "tree-flow.h"
  31 #include "tree-dump.h"
  32 #include "tree-ssa-live.h"
  33
  34
  35 /* Temporary Expression Replacement (TER)
  36
  37    Replace SSA version variables during out-of-ssa with their defining
  38    expression if there is only one use of the variable.
  39
  40    This pass is required in order for the RTL expansion pass to see larger
  41    chunks of code.  This allows it to make better choices on RTL pattern
  42    selection.  When expand is rewritten and merged with out-of-ssa, and
  43    understands SSA, this should be eliminated.
  44
  45    A pass is made through the function, one block at a time.  No cross block
  46    information is tracked.
  47
  48    Variables which only have one use, and whose defining stmt is considered
  49    a replaceable expression (see is_replaceable_p) are tracked to see whether
  50    they can be replaced at their use location.
  51
  52    n_12 = C * 10
  53    a_2 = b_5 + 6
  54    v_9 = a_2 * n_12
  55
  56    if there are the only use of n_12 and a_2, TER will substitute in their
  57    expressions in v_9, and end up with:
  58
  59    v_9 = (b_5 + 6) * (C * 10)
  60
  61    which will then have the ssa_name assigned to regular variables, and the
  62    resulting code which will be passed to the expander looks something like:
  63
  64    v = (b + 6) * (C * 10)
  65
  66
  67    This requires ensuring that none of the variables used by the expression
  68    change between the def point and where it is used.  Furthermore, if any
  69    of the ssa_names used in this expression are themselves replaceable, we
  70    have to ensure none of that expressions' arguments change either.
  71    Although SSA_NAMES themselves don't change, this pass is performed after
  72    coalescing has coalesced different SSA_NAMES together, so there could be a
  73    definition of an SSA_NAME which is coalesced with a use that causes a
  74    problem, i.e.,
  75
  76    PHI b_5 = <b_8(2), b_14(1)>
  77    <...>
  78    a_2 = b_5 + 6
  79    b_8 = c_4 + 4
  80    v_9 = a_2 * n_12
  81    <...>
  82
  83    If b_5, b_8 and b_14 are all coalesced together...
  84    The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
  85    because b_8 is in fact killing the value of b_5 since they share a partition
  86    and will be assigned the same memory or register location.
  87
  88    TER implements this but stepping through the instructions in a block and
  89    tracking potential expressions for replacement, and the partitions they are
  90    dependent on.  Expressions are represented by the SSA_NAME_VERSION of the
  91    DEF on the LHS of a GIMPLE_MODIFY_STMT and the expression is the RHS.
  92
  93    When a stmt is determined to be a possible replacement expression, the
  94    following steps are taken:
  95
  96    EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the
  97    def and any uses in the expression.  non-NULL means the expression is being
  98    tracked.  The UID's themselves are used to prevent TER substitution into
  99    accumulating sequences, i.e.,
 100
 101    x = x + y
 102    x = x + z
 103    x = x + w
 104    etc.
 105    this can result in very large expressions which don't accomplish anything
 106    see PR tree-optimization/17549.
 107
 108    PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any
 109    partition which is used in the expression.  This is primarily used to remove
 110    an expression from the partition kill lists when a decision is made whether
 111    to replace it or not.  This is indexed by ssa version number as well, and
 112    indicates a partition number.  virtual operands are not tracked individually,
 113    but they are summarized by an artificial partition called VIRTUAL_PARTITION.
 114    This means a MAY or MUST def will kill *ALL* expressions that are dependent
 115    on a virtual operand.
 116    Note that the EXPR_DECL_UID and this bitmap represent very similar
 117    information, but the info in one is not easy to obtain from the other.
 118
 119    KILL_LIST is yet another bitmap array, this time it is indexed by partition
 120    number, and represents a list of active expressions which will will no
 121    longer be valid if a definition into this partition takes place.
 122
 123    PARTITION_IN_USE is simply a bitmap which is used to track which partitions
 124    currently have something in their kill list.  This is used at the end of
 125    a block to clear out the KILL_LIST bitmaps at the end of each block.
 126
 127    NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store
 128    dependencies which will be reused by the current definition. All the uses
 129    on an expression are processed before anything else is done. If a use is
 130    determined to be a replaceable expression AND the current stmt is also going
 131    to be replaceable, all the dependencies of this replaceable use will be
 132    picked up by the current stmt's expression. Rather than recreate them, they
 133    are simply copied here and then copied into the new expression when it is
 134    processed.
 135
 136    a_2 = b_5 + 6
 137    v_8 = a_2 + c_4
 138
 139    a_2's expression 'b_5 + 6' is determined to be replaceable at the use
 140    location. It is dependent on the partition 'b_5' is in. This is cached into
 141    the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for
 142    replaceability, it is a candidate, and it is dependent on the partition
 143    b_5 is in *NOT* a_2, as well as c_4's partition.
 144
 145    if v_8 is also replaceable:
 146
 147    x_9 = v_8 * 5
 148
 149    x_9 is dependent on partitions b_5, and c_4
 150
 151    if a statement is found which has either of those partitions written to
 152    before x_9 is used, then x_9 itself is NOT replaceable.  */
 153
 154
 155 /* Temporary Expression Replacement (TER) table information.  */
 156
 157 typedef struct temp_expr_table_d
 158 {
 159   var_map map;
 160   bitmap *partition_dependencies;       /* Partitions expr is dependent on.  */
 161   tree *replaceable_expressions;        /* Replacement expression table.  */
 162   bitmap *expr_decl_uids;               /* Base uids of exprs.  */
 163   bitmap *kill_list;                    /* Expr's killed by a partition.  */
 164   int virtual_partition;                /* Pseudo partition for virtual ops.  */
 165   bitmap partition_in_use;              /* Partitions with kill entries.  */
 166   bitmap new_replaceable_dependencies;  /* Holding place for pending dep's.  */
 167   int *num_in_part;                     /* # of ssa_names in a partition.  */
 168 } *temp_expr_table_p;
 169
 170 /* Used to indicate a dependency on VDEFs.  */
 171 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
 172
 173 #ifdef ENABLE_CHECKING
 174 extern void debug_ter (FILE *, temp_expr_table_p);
 175 #endif
 176
 177
 178 /* Create a new TER table for MAP.  */
 179
 180 static temp_expr_table_p
 181 new_temp_expr_table (var_map map)
 182 {
 183   temp_expr_table_p t;
 184   unsigned x;
 185
 186   t = XNEW (struct temp_expr_table_d);
 187   t->map = map;
 188
 189   t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
 190   t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
 191   t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
 192
 193   t->partition_in_use = BITMAP_ALLOC (NULL);
 194
 195   t->virtual_partition = num_var_partitions (map);
 196   t->new_replaceable_dependencies = BITMAP_ALLOC (NULL);
 197
 198   t->replaceable_expressions = NULL;
 199   t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
 200   for (x = 1; x < num_ssa_names; x++)
 201     {
 202       int p;
 203       tree name = ssa_name (x);
 204       if (!name)
 205         continue;
 206       p = var_to_partition (map, name);
 207       if (p != NO_PARTITION)
 208         t->num_in_part[p]++;
 209     }
 210
 211   return t;
 212 }
 213
 214
 215 /* Free TER table T.  If there are valid replacements, return the expression
 216    vector.  */
 217
 218 static tree *
 219 free_temp_expr_table (temp_expr_table_p t)
 220 {
 221   tree *ret = NULL;
 222   unsigned i;
 223
 224 #ifdef ENABLE_CHECKING
 225   unsigned x;
 226   for (x = 0; x <= num_var_partitions (t->map); x++)
 227     gcc_assert (!t->kill_list[x]);
 228 #endif
 229
 230   BITMAP_FREE (t->partition_in_use);
 231   BITMAP_FREE (t->new_replaceable_dependencies);
 232
 233   for (i = 0; i <= num_ssa_names; i++)
 234     if (t->expr_decl_uids[i])
 235       BITMAP_FREE (t->expr_decl_uids[i]);
 236   free (t->expr_decl_uids);
 237
 238   free (t->kill_list);
 239   free (t->partition_dependencies);
 240   free (t->num_in_part);
 241
 242   if (t->replaceable_expressions)
 243     ret = t->replaceable_expressions;
 244
 245   free (t);
 246   return ret;
 247 }
 248
 249
 250 /* Return TRUE if VERSION is to be replaced by an expression in TAB.  */
 251
 252 static inline bool
 253 version_to_be_replaced_p (temp_expr_table_p tab, int version)
 254 {
 255   if (!tab->replaceable_expressions)
 256     return false;
 257   return tab->replaceable_expressions[version] != NULL_TREE;
 258 }
 259
 260
 261 /* Add partition P to the list if partitions VERSION is dependent on.  TAB is
 262    the expression table */
 263
 264 static inline void
 265 make_dependent_on_partition (temp_expr_table_p tab, int version, int p)
 266 {
 267   if (!tab->partition_dependencies[version])
 268     tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
 269
 270   bitmap_set_bit (tab->partition_dependencies[version], p);
 271 }
 272
 273
 274 /* Add VER to the kill list for P.  TAB is the expression table */
 275
 276 static inline void
 277 add_to_partition_kill_list (temp_expr_table_p tab, int p, int ver)
 278 {
 279   if (!tab->kill_list[p])
 280     {
 281       tab->kill_list[p] = BITMAP_ALLOC (NULL);
 282       bitmap_set_bit (tab->partition_in_use, p);
 283     }
 284   bitmap_set_bit (tab->kill_list[p], ver);
 285 }
 286
 287
 288 /* Remove VER from the partition kill list for P.  TAB is the expression
 289    table.  */
 290
 291 static inline void
 292 remove_from_partition_kill_list (temp_expr_table_p tab, int p, int version)
 293 {
 294 #ifdef ENABLE_CHECKING
 295   gcc_assert (tab->kill_list[p]);
 296 #endif
 297   bitmap_clear_bit (tab->kill_list[p], version);
 298   if (bitmap_empty_p (tab->kill_list[p]))
 299     {
 300       bitmap_clear_bit (tab->partition_in_use, p);
 301       BITMAP_FREE (tab->kill_list[p]);
 302     }
 303 }
 304
 305
 306 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
 307    replaceable by an expression, add a dependence each of the elements of the
 308    expression.  These are contained in the new_replaceable list.  TAB is the
 309    expression table.  */
 310
 311 static void
 312 add_dependence (temp_expr_table_p tab, int version, tree var)
 313 {
 314   int i;
 315   bitmap_iterator bi;
 316   unsigned x;
 317
 318   i = SSA_NAME_VERSION (var);
 319   if (version_to_be_replaced_p (tab, i))
 320     {
 321       if (!bitmap_empty_p (tab->new_replaceable_dependencies))
 322         {
 323           /* Version will now be killed by a write to any partition the
 324              substituted expression would have been killed by.  */
 325           EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
 326             add_to_partition_kill_list (tab, x, version);
 327
 328           /* Rather than set partition_dependencies and in_use lists bit by
 329              bit, simply OR in the new_replaceable_dependencies bits.  */
 330           if (!tab->partition_dependencies[version])
 331             tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
 332           bitmap_ior_into (tab->partition_dependencies[version],
 333                            tab->new_replaceable_dependencies);
 334           bitmap_ior_into (tab->partition_in_use,
 335                            tab->new_replaceable_dependencies);
 336           /* It is only necessary to add these once.  */
 337           bitmap_clear (tab->new_replaceable_dependencies);
 338         }
 339     }
 340   else
 341     {
 342       i = var_to_partition (tab->map, var);
 343 #ifdef ENABLE_CHECKING
 344       gcc_assert (i != NO_PARTITION);
 345       gcc_assert (tab->num_in_part[i] != 0);
 346 #endif
 347       /* Only dependencies on ssa_names which are coalesced with something need
 348          to be tracked.  Partitions with containing only a single SSA_NAME
 349          *cannot* have their value changed.  */
 350       if (tab->num_in_part[i] > 1)
 351         {
 352           add_to_partition_kill_list (tab, i, version);
 353           make_dependent_on_partition (tab, version, i);
 354         }
 355     }
 356 }
 357
 358
 359 /* Return TRUE if expression STMT is suitable for replacement.  */
 360
 361 static inline bool
 362 is_replaceable_p (tree stmt)
 363 {
 364   tree call_expr;
 365   use_operand_p use_p;
 366   tree def, use_stmt;
 367
 368   /* Only consider modify stmts.  */
 369   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 370     return false;
 371
 372   /* If the statement may throw an exception, it cannot be replaced.  */
 373   if (tree_could_throw_p (stmt))
 374     return false;
 375
 376   /* Punt if there is more than 1 def.  */
 377   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
 378   if (!def)
 379     return false;
 380
 381   /* Only consider definitions which have a single use.  */
 382   if (!single_imm_use (def, &use_p, &use_stmt))
 383     return false;
 384
 385   /* If the use isn't in this block, it wont be replaced either.  */
 386   if (bb_for_stmt (use_stmt) != bb_for_stmt (stmt))
 387     return false;
 388
 389   /* Used in this block, but at the TOP of the block, not the end.  */
 390   if (TREE_CODE (use_stmt) == PHI_NODE)
 391     return false;
 392
 393   /* There must be no VDEFs.  */
 394   if (!(ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF)))
 395     return false;
 396
 397   /* Float expressions must go through memory if float-store is on.  */
 398   if (flag_float_store
 399       && FLOAT_TYPE_P (TREE_TYPE (GENERIC_TREE_OPERAND (stmt, 1))))
 400     return false;
 401
 402   /* An assignment with a register variable on the RHS is not
 403      replaceable.  */
 404   if (TREE_CODE (GENERIC_TREE_OPERAND (stmt, 1)) == VAR_DECL
 405       && DECL_HARD_REGISTER (GENERIC_TREE_OPERAND (stmt, 1)))
 406     return false;
 407
 408   /* No function calls can be replaced.  */
 409   if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
 410     return false;
 411
 412   /* Leave any stmt with volatile operands alone as well.  */
 413   if (stmt_ann (stmt)->has_volatile_ops)
 414     return false;
 415
 416
 417   return true;
 418 }
 419
 420
 421 /* This function will remove the expression for VERSION from replacement
 422    consideration in table TAB.  If FREE_EXPR is true, then remove the
 423    expression from consideration as well by freeing the decl uid bitmap.  */
 424
 425 static void
 426 finished_with_expr (temp_expr_table_p tab, int version, bool free_expr)
 427 {
 428   unsigned i;
 429   bitmap_iterator bi;
 430
 431   /* Remove this expression from its dependent lists.  The partition dependence
 432      list is retained and transfered later to whomever uses this version.  */
 433   if (tab->partition_dependencies[version])
 434     {
 435       EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
 436         remove_from_partition_kill_list (tab, i, version);
 437       BITMAP_FREE (tab->partition_dependencies[version]);
 438     }
 439   if (free_expr)
 440     BITMAP_FREE (tab->expr_decl_uids[version]);
 441 }
 442
 443
 444 /* Create an expression entry for a replaceable expression.  */
 445
 446 static void
 447 process_replaceable (temp_expr_table_p tab, tree stmt)
 448 {
 449   tree var, def, basevar;
 450   int version;
 451   ssa_op_iter iter;
 452   bitmap def_vars, use_vars;
 453
 454 #ifdef ENABLE_CHECKING
 455   gcc_assert (is_replaceable_p (stmt));
 456 #endif
 457
 458   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
 459   version = SSA_NAME_VERSION (def);
 460   basevar = SSA_NAME_VAR (def);
 461   def_vars = BITMAP_ALLOC (NULL);
 462
 463   bitmap_set_bit (def_vars, DECL_UID (basevar));
 464
 465   /* Add this expression to the dependency list for each use partition.  */
 466   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
 467     {
 468       int var_version = SSA_NAME_VERSION (var);
 469
 470       use_vars = tab->expr_decl_uids[var_version];
 471       add_dependence (tab, version, var);
 472       if (use_vars)
 473         {
 474           bitmap_ior_into (def_vars, use_vars);
 475           BITMAP_FREE (tab->expr_decl_uids[var_version]);
 476         }
 477       else
 478         bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
 479     }
 480   tab->expr_decl_uids[version] = def_vars;
 481
 482   /* If there are VUSES, add a dependence on virtual defs.  */
 483   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
 484     {
 485       make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
 486       add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
 487     }
 488 }
 489
 490
 491 /* This function removes any expression in TAB which is dependent on PARTITION
 492    from consideration, making it not replaceable.  */
 493
 494 static inline void
 495 kill_expr (temp_expr_table_p tab, int partition)
 496 {
 497   unsigned version;
 498
 499   /* Mark every active expr dependent on this var as not replaceable.
 500      finished_with_expr can modify the bitmap, so we can't execute over it.  */
 501   while (tab->kill_list[partition])
 502     {
 503       version = bitmap_first_set_bit (tab->kill_list[partition]);
 504       finished_with_expr (tab, version, true);
 505     }
 506
 507 #ifdef ENABLE_CHECKING
 508   gcc_assert (!tab->kill_list[partition]);
 509 #endif
 510 }
 511
 512
 513 /* This function kills all expressions in TAB which are dependent on virtual
 514    partitions.  */
 515
 516 static inline void
 517 kill_virtual_exprs (temp_expr_table_p tab)
 518 {
 519   kill_expr (tab, VIRTUAL_PARTITION (tab));
 520 }
 521
 522
 523 /* Mark the expression associated with VAR as replaceable, and enter
 524    the defining stmt into the partition_dependencies table TAB.  If
 525    MORE_REPLACING is true, accumulate the pending partition dependencies.  */
 526
 527 static void
 528 mark_replaceable (temp_expr_table_p tab, tree var, bool more_replacing)
 529 {
 530   int version = SSA_NAME_VERSION (var);
 531
 532   /* Move the dependence list to the pending listpending.  */
 533   if (more_replacing && tab->partition_dependencies[version])
 534     bitmap_ior_into (tab->new_replaceable_dependencies,
 535                      tab->partition_dependencies[version]);
 536
 537   finished_with_expr (tab, version, !more_replacing);
 538
 539   /* Set the replaceable expression.  */
 540   if (!tab->replaceable_expressions)
 541     tab->replaceable_expressions = XCNEWVEC (tree, num_ssa_names + 1);
 542   tab->replaceable_expressions[version] = SSA_NAME_DEF_STMT (var);
 543 }
 544
 545
 546 /* This function processes basic block BB, and looks for variables which can
 547    be replaced by their expressions.  Results are stored in the table TAB.  */
 548
 549 static void
 550 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
 551 {
 552   block_stmt_iterator bsi;
 553   tree stmt, def, use;
 554   stmt_ann_t ann;
 555   int partition;
 556   var_map map = tab->map;
 557   ssa_op_iter iter;
 558   bool stmt_replaceable;
 559
 560   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 561     {
 562       stmt = bsi_stmt (bsi);
 563       ann = stmt_ann (stmt);
 564
 565       stmt_replaceable = is_replaceable_p (stmt);
 566       /* Determine if this stmt finishes an existing expression.  */
 567       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 568         {
 569           unsigned ver = SSA_NAME_VERSION (use);
 570
 571           /* If this use is a potential replacement variable, process it.  */
 572           if (tab->expr_decl_uids[ver])
 573             {
 574               bool same_root_var = false;
 575               ssa_op_iter iter2;
 576               bitmap vars = tab->expr_decl_uids[ver];
 577
 578               /* See if the root variables are the same.  If they are, we
 579                  do not want to do the replacement to avoid problems with
 580                  code size, see PR tree-optimization/17549.  */
 581               if (!bitmap_empty_p (vars))
 582                 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
 583                   {
 584                     if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
 585                       {
 586                         same_root_var = true;
 587                         break;
 588                       }
 589                   }
 590
 591               /* Mark expression as replaceable unless stmt is volatile or the
 592                  def variable has the same root variable as something in the
 593                  substitution list.  */
 594               if (ann->has_volatile_ops || same_root_var)
 595                 finished_with_expr (tab, ver, true);
 596               else
 597                 mark_replaceable (tab, use, stmt_replaceable);
 598             }
 599         }
 600
 601       /* Next, see if this stmt kills off an active expression.  */
 602       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
 603         {
 604           partition = var_to_partition (map, def);
 605           if (partition != NO_PARTITION && tab->kill_list[partition])
 606             kill_expr (tab, partition);
 607         }
 608
 609       /* Now see if we are creating a new expression or not.  */
 610       if (stmt_replaceable)
 611         process_replaceable (tab, stmt);
 612
 613       /* Free any unused dependency lists.  */
 614       bitmap_clear (tab->new_replaceable_dependencies);
 615
 616       /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
 617          including the current stmt.  */
 618       if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 619         kill_virtual_exprs (tab);
 620     }
 621 }
 622
 623
 624 /* This function is the driver routine for replacement of temporary expressions
 625    in the SSA->normal phase, operating on MAP.  If there are replaceable
 626    expressions, a table is returned which maps SSA versions to the
 627    expressions they should be replaced with.  A NULL_TREE indicates no
 628    replacement should take place.  If there are no replacements at all,
 629    NULL is returned by the function, otherwise an expression vector indexed
 630    by SSA_NAME version numbers.  */
 631
 632 extern tree *
 633 find_replaceable_exprs (var_map map)
 634 {
 635   basic_block bb;
 636   temp_expr_table_p table;
 637   tree *ret;
 638
 639   table = new_temp_expr_table (map);
 640   FOR_EACH_BB (bb)
 641     {
 642       find_replaceable_in_bb (table, bb);
 643       gcc_assert (bitmap_empty_p (table->partition_in_use));
 644
 645 #ifdef ENABLE_CHECKING
 646       {
 647         unsigned i;
 648         /* Make sure all the tables have been cleared out.  */
 649         for (i = 0; i < num_ssa_names + 1; i++)
 650           {
 651             gcc_assert (table->partition_dependencies[i] == NULL);
 652             gcc_assert (table->expr_decl_uids[i] == NULL);
 653             if (i < num_var_partitions (map))
 654               gcc_assert (table->kill_list[i] == NULL);
 655           }
 656       }
 657 #endif
 658     }
 659
 660   ret = free_temp_expr_table (table);
 661   return ret;
 662 }
 663
 664
 665 /* Dump TER expression table EXPR to file F.  */
 666
 667 extern void
 668 dump_replaceable_exprs (FILE *f, tree *expr)
 669 {
 670   tree stmt, var;
 671   int x;
 672
 673   fprintf (f, "\nReplacing Expressions\n");
 674   for (x = 0; x < (int)num_ssa_names; x++)
 675     if (expr[x])
 676       {
 677         stmt = expr[x];
 678         var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
 679         gcc_assert (var != NULL_TREE);
 680         print_generic_expr (f, var, TDF_SLIM);
 681         fprintf (f, " replace with --> ");
 682         print_generic_expr (f, GENERIC_TREE_OPERAND (stmt, 1),
 683                             TDF_SLIM);
 684         fprintf (f, "\n");
 685       }
 686   fprintf (f, "\n");
 687 }
 688
 689
 690 #ifdef ENABLE_CHECKING
 691 /* Dump the status of the various tables in the expression table.  This is used
 692    exclusively to debug TER.  F is the place to send debug info and T is the
 693    table being debugged.  */
 694
 695 extern void
 696 debug_ter (FILE *f, temp_expr_table_p t)
 697 {
 698   unsigned x, y;
 699   bitmap_iterator bi;
 700
 701   fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n",
 702            VIRTUAL_PARTITION (t));
 703   if (t->replaceable_expressions)
 704     dump_replaceable_exprs (f, t->replaceable_expressions);
 705   fprintf (f, "Currently tracking the following expressions:\n");
 706
 707   for (x = 1; x < num_ssa_names; x++)
 708     if (t->expr_decl_uids[x])
 709       {
 710         print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
 711         fprintf (f, " dep-parts : ");
 712         if (t->partition_dependencies[x]
 713             && !bitmap_empty_p (t->partition_dependencies[x]))
 714           {
 715             EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
 716               fprintf (f, "P%d ",y);
 717           }
 718         fprintf (stderr, "   basedecls: ");
 719         EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
 720           fprintf (f, "%d ",y);
 721         fprintf (stderr, "\n");
 722       }
 723
 724   bitmap_print (f, t->partition_in_use, "Partitions in use ",
 725                 "\npartition KILL lists:\n");
 726
 727   for (x = 0; x <= num_var_partitions (t->map); x++)
 728     if (t->kill_list[x])
 729       {
 730         fprintf (f, "Partition %d : ", x);
 731         EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
 732           fprintf (f, "_%d ",y);
 733       }
 734
 735   fprintf (f, "\n----------\n");
 736 }
 737 #endif