gcc/tree-ssa-ter.c

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