gcc/tree-ssa-ter.c

   1 /* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
   2    Copyright (C) 2003-2019 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 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
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "backend.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "ssa.h"
  29 #include "gimple-pretty-print.h"
  30 #include "gimple-iterator.h"
  31 #include "dumpfile.h"
  32 #include "tree-ssa-live.h"
  33 #include "tree-ssa-ter.h"
  34 #include "tree-outof-ssa.h"
  35 #include "gimple-walk.h"
  36
  37
  38 /* Temporary Expression Replacement (TER)
  39
  40    Replace SSA version variables during out-of-ssa with their defining
  41    expression if there is only one use of the variable.
  42
  43    This pass is required in order for the RTL expansion pass to see larger
  44    chunks of code.  This allows it to make better choices on RTL pattern
  45    selection.  When expand is rewritten and merged with out-of-ssa, and
  46    understands SSA, this should be eliminated.
  47
  48    A pass is made through the function, one block at a time.  No cross block
  49    information is tracked.
  50
  51    Variables which only have one use, and whose defining stmt is considered
  52    a replaceable expression (see ssa_is_replaceable_p) are tracked to see whether
  53    they can be replaced at their use location.
  54
  55    n_12 = C * 10
  56    a_2 = b_5 + 6
  57    v_9 = a_2 * n_12
  58
  59    if there are the only use of n_12 and a_2, TER will substitute in their
  60    expressions in v_9, and end up with:
  61
  62    v_9 = (b_5 + 6) * (C * 10)
  63
  64    which will then have the ssa_name assigned to regular variables, and the
  65    resulting code which will be passed to the expander looks something like:
  66
  67    v = (b + 6) * (C * 10)
  68
  69
  70    This requires ensuring that none of the variables used by the expression
  71    change between the def point and where it is used.  Furthermore, if any
  72    of the ssa_names used in this expression are themselves replaceable, we
  73    have to ensure none of that expressions' arguments change either.
  74    Although SSA_NAMES themselves don't change, this pass is performed after
  75    coalescing has coalesced different SSA_NAMES together, so there could be a
  76    definition of an SSA_NAME which is coalesced with a use that causes a
  77    problem, i.e.,
  78
  79    PHI b_5 = <b_8(2), b_14(1)>
  80    <...>
  81    a_2 = b_5 + 6
  82    b_8 = c_4 + 4
  83    v_9 = a_2 * n_12
  84    <...>
  85
  86    If b_5, b_8 and b_14 are all coalesced together...
  87    The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
  88    because b_8 is in fact killing the value of b_5 since they share a partition
  89    and will be assigned the same memory or register location.
  90
  91    TER implements this but stepping through the instructions in a block and
  92    tracking potential expressions for replacement, and the partitions they are
  93    dependent on.  Expressions are represented by the SSA_NAME_VERSION of the
  94    DEF on the LHS of a GIMPLE_ASSIGN and the expression is the RHS.
  95
  96    When a stmt is determined to be a possible replacement expression, the
  97    following steps are taken:
  98
  99    EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the
 100    def and any uses in the expression.  non-NULL means the expression is being
 101    tracked.  The UID's themselves are used to prevent TER substitution into
 102    accumulating sequences, i.e.,
 103
 104    x = x + y
 105    x = x + z
 106    x = x + w
 107    etc.
 108    this can result in very large expressions which don't accomplish anything
 109    see PR tree-optimization/17549.
 110
 111    PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any
 112    partition which is used in the expression.  This is primarily used to remove
 113    an expression from the partition kill lists when a decision is made whether
 114    to replace it or not.  This is indexed by ssa version number as well, and
 115    indicates a partition number.  virtual operands are not tracked individually,
 116    but they are summarized by an artificial partition called VIRTUAL_PARTITION.
 117    This means a MAY or MUST def will kill *ALL* expressions that are dependent
 118    on a virtual operand.
 119    Note that the EXPR_DECL_UID and this bitmap represent very similar
 120    information, but the info in one is not easy to obtain from the other.
 121
 122    KILL_LIST is yet another bitmap array, this time it is indexed by partition
 123    number, and represents a list of active expressions which will no
 124    longer be valid if a definition into this partition takes place.
 125
 126    PARTITION_IN_USE is simply a bitmap which is used to track which partitions
 127    currently have something in their kill list.  This is used at the end of
 128    a block to clear out the KILL_LIST bitmaps at the end of each block.
 129
 130    NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store
 131    dependencies which will be reused by the current definition. All the uses
 132    on an expression are processed before anything else is done. If a use is
 133    determined to be a replaceable expression AND the current stmt is also going
 134    to be replaceable, all the dependencies of this replaceable use will be
 135    picked up by the current stmt's expression. Rather than recreate them, they
 136    are simply copied here and then copied into the new expression when it is
 137    processed.
 138
 139    a_2 = b_5 + 6
 140    v_8 = a_2 + c_4
 141
 142    a_2's expression 'b_5 + 6' is determined to be replaceable at the use
 143    location. It is dependent on the partition 'b_5' is in. This is cached into
 144    the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for
 145    replaceability, it is a candidate, and it is dependent on the partition
 146    b_5 is in *NOT* a_2, as well as c_4's partition.
 147
 148    if v_8 is also replaceable:
 149
 150    x_9 = v_8 * 5
 151
 152    x_9 is dependent on partitions b_5, and c_4
 153
 154    if a statement is found which has either of those partitions written to
 155    before x_9 is used, then x_9 itself is NOT replaceable.  */
 156
 157
 158 /* Temporary Expression Replacement (TER) table information.  */
 159
 160 struct temp_expr_table
 161 {
 162   var_map map;
 163   bitmap *partition_dependencies;       /* Partitions expr is dependent on.  */
 164   bitmap replaceable_expressions;       /* Replacement expression table.  */
 165   bitmap *expr_decl_uids;               /* Base uids of exprs.  */
 166   bitmap *kill_list;                    /* Expr's killed by a partition.  */
 167   int virtual_partition;                /* Pseudo partition for virtual ops.  */
 168   bitmap partition_in_use;              /* Partitions with kill entries.  */
 169   bitmap new_replaceable_dependencies;  /* Holding place for pending dep's.  */
 170   int *num_in_part;                     /* # of ssa_names in a partition.  */
 171   int *call_cnt;                        /* Call count at definition.  */
 172   int *reg_vars_cnt;                    /* Number of register variable
 173                                            definitions encountered.  */
 174 };
 175
 176 /* Used to indicate a dependency on VDEFs.  */
 177 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
 178
 179 /* A place for the many, many bitmaps we create.  */
 180 static bitmap_obstack ter_bitmap_obstack;
 181
 182 extern void debug_ter (FILE *, temp_expr_table *);
 183
 184
 185 /* Create a new TER table for MAP.  */
 186
 187 static temp_expr_table *
 188 new_temp_expr_table (var_map map)
 189 {
 190   temp_expr_table *t = XNEW (struct temp_expr_table);
 191   t->map = map;
 192
 193   t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
 194   t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
 195   t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
 196
 197   t->partition_in_use = BITMAP_ALLOC (&ter_bitmap_obstack);
 198
 199   t->virtual_partition = num_var_partitions (map);
 200   t->new_replaceable_dependencies = BITMAP_ALLOC (&ter_bitmap_obstack);
 201
 202   t->replaceable_expressions = NULL;
 203   t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
 204
 205   unsigned x;
 206   tree name;
 207
 208   FOR_EACH_SSA_NAME (x, name, cfun)
 209     {
 210       int p;
 211       p = var_to_partition (map, name);
 212       if (p != NO_PARTITION)
 213         t->num_in_part[p]++;
 214     }
 215   t->call_cnt = XCNEWVEC (int, num_ssa_names + 1);
 216   t->reg_vars_cnt = XCNEWVEC (int, num_ssa_names + 1);
 217
 218   return t;
 219 }
 220
 221
 222 /* Free TER table T.  If there are valid replacements, return the expression
 223    vector.  */
 224
 225 static bitmap
 226 free_temp_expr_table (temp_expr_table *t)
 227 {
 228   bitmap ret = NULL;
 229
 230   if (flag_checking)
 231     {
 232       for (unsigned x = 0; x <= num_var_partitions (t->map); x++)
 233         gcc_assert (!t->kill_list[x]);
 234       for (unsigned x = 0; x < num_ssa_names; x++)
 235         {
 236           gcc_assert (t->expr_decl_uids[x] == NULL);
 237           gcc_assert (t->partition_dependencies[x] == NULL);
 238         }
 239     }
 240
 241   BITMAP_FREE (t->partition_in_use);
 242   BITMAP_FREE (t->new_replaceable_dependencies);
 243
 244   free (t->expr_decl_uids);
 245   free (t->kill_list);
 246   free (t->partition_dependencies);
 247   free (t->num_in_part);
 248   free (t->call_cnt);
 249   free (t->reg_vars_cnt);
 250
 251   if (t->replaceable_expressions)
 252     ret = t->replaceable_expressions;
 253
 254   free (t);
 255   return ret;
 256 }
 257
 258
 259 /* Return TRUE if VERSION is to be replaced by an expression in TAB.  */
 260
 261 static inline bool
 262 version_to_be_replaced_p (temp_expr_table *tab, int version)
 263 {
 264   if (!tab->replaceable_expressions)
 265     return false;
 266   return bitmap_bit_p (tab->replaceable_expressions, version);
 267 }
 268
 269
 270 /* Add partition P to the list if partitions VERSION is dependent on.  TAB is
 271    the expression table */
 272
 273 static inline void
 274 make_dependent_on_partition (temp_expr_table *tab, int version, int p)
 275 {
 276   if (!tab->partition_dependencies[version])
 277     tab->partition_dependencies[version] = BITMAP_ALLOC (&ter_bitmap_obstack);
 278
 279   bitmap_set_bit (tab->partition_dependencies[version], p);
 280 }
 281
 282
 283 /* Add VER to the kill list for P.  TAB is the expression table */
 284
 285 static inline void
 286 add_to_partition_kill_list (temp_expr_table *tab, int p, int ver)
 287 {
 288   if (!tab->kill_list[p])
 289     {
 290       tab->kill_list[p] = BITMAP_ALLOC (&ter_bitmap_obstack);
 291       bitmap_set_bit (tab->partition_in_use, p);
 292     }
 293   bitmap_set_bit (tab->kill_list[p], ver);
 294 }
 295
 296
 297 /* Remove VER from the partition kill list for P.  TAB is the expression
 298    table.  */
 299
 300 static inline void
 301 remove_from_partition_kill_list (temp_expr_table *tab, int p, int version)
 302 {
 303   gcc_checking_assert (tab->kill_list[p]);
 304   bitmap_clear_bit (tab->kill_list[p], version);
 305   if (bitmap_empty_p (tab->kill_list[p]))
 306     {
 307       bitmap_clear_bit (tab->partition_in_use, p);
 308       BITMAP_FREE (tab->kill_list[p]);
 309     }
 310 }
 311
 312
 313 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
 314    replaceable by an expression, add a dependence each of the elements of the
 315    expression.  These are contained in the new_replaceable list.  TAB is the
 316    expression table.  */
 317
 318 static void
 319 add_dependence (temp_expr_table *tab, int version, tree var)
 320 {
 321   int i;
 322   bitmap_iterator bi;
 323   unsigned x;
 324
 325   i = SSA_NAME_VERSION (var);
 326   if (version_to_be_replaced_p (tab, i))
 327     {
 328       if (!bitmap_empty_p (tab->new_replaceable_dependencies))
 329         {
 330           /* Version will now be killed by a write to any partition the
 331              substituted expression would have been killed by.  */
 332           EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
 333             add_to_partition_kill_list (tab, x, version);
 334
 335           /* Rather than set partition_dependencies and in_use lists bit by
 336              bit, simply OR in the new_replaceable_dependencies bits.  */
 337           if (!tab->partition_dependencies[version])
 338             tab->partition_dependencies[version] =
 339               BITMAP_ALLOC (&ter_bitmap_obstack);
 340           bitmap_ior_into (tab->partition_dependencies[version],
 341                            tab->new_replaceable_dependencies);
 342           bitmap_ior_into (tab->partition_in_use,
 343                            tab->new_replaceable_dependencies);
 344           /* It is only necessary to add these once.  */
 345           bitmap_clear (tab->new_replaceable_dependencies);
 346         }
 347     }
 348   else
 349     {
 350       i = var_to_partition (tab->map, var);
 351       gcc_checking_assert (i != NO_PARTITION);
 352       gcc_checking_assert (tab->num_in_part[i] != 0);
 353       /* Only dependencies on ssa_names which are coalesced with something need
 354          to be tracked.  Partitions with containing only a single SSA_NAME
 355          *cannot* have their value changed.  */
 356       if (tab->num_in_part[i] > 1)
 357         {
 358           add_to_partition_kill_list (tab, i, version);
 359           make_dependent_on_partition (tab, version, i);
 360         }
 361     }
 362 }
 363
 364
 365 /* This function will remove the expression for VERSION from replacement
 366    consideration in table TAB.  If FREE_EXPR is true, then remove the
 367    expression from consideration as well by freeing the decl uid bitmap.  */
 368
 369 static void
 370 finished_with_expr (temp_expr_table *tab, int version, bool free_expr)
 371 {
 372   unsigned i;
 373   bitmap_iterator bi;
 374
 375   /* Remove this expression from its dependent lists.  The partition dependence
 376      list is retained and transferred later to whomever uses this version.  */
 377   if (tab->partition_dependencies[version])
 378     {
 379       EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
 380         remove_from_partition_kill_list (tab, i, version);
 381       BITMAP_FREE (tab->partition_dependencies[version]);
 382     }
 383   if (free_expr)
 384     BITMAP_FREE (tab->expr_decl_uids[version]);
 385 }
 386
 387
 388 /* Return TRUE if expression STMT is suitable for replacement.
 389    In addition to ssa_is_replaceable_p, require the same bb, and for -O0
 390    same locus and same BLOCK), Considers memory loads as replaceable if aliasing
 391    is available.  */
 392
 393 static inline bool
 394 ter_is_replaceable_p (gimple *stmt)
 395 {
 396
 397   if (ssa_is_replaceable_p (stmt))
 398     {
 399       use_operand_p use_p;
 400       tree def;
 401       gimple *use_stmt;
 402       location_t locus1, locus2;
 403       tree block1, block2;
 404
 405       /* Only consider definitions which have a single use.  ssa_is_replaceable_p
 406          already performed this check, but the use stmt pointer is required for
 407          further checks.  */
 408       def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
 409       if (!single_imm_use (def, &use_p, &use_stmt))
 410           return false;
 411
 412       /* If the use isn't in this block, it wont be replaced either.  */
 413       if (gimple_bb (use_stmt) != gimple_bb (stmt))
 414         return false;
 415
 416       locus1 = gimple_location (stmt);
 417       block1 = LOCATION_BLOCK (locus1);
 418       locus1 = LOCATION_LOCUS (locus1);
 419
 420       if (gphi *phi = dyn_cast <gphi *> (use_stmt))
 421         locus2 = gimple_phi_arg_location (phi,
 422                                           PHI_ARG_INDEX_FROM_USE (use_p));
 423       else
 424         locus2 = gimple_location (use_stmt);
 425       block2 = LOCATION_BLOCK (locus2);
 426       locus2 = LOCATION_LOCUS (locus2);
 427
 428       if ((!optimize || optimize_debug)
 429           && ((locus1 != UNKNOWN_LOCATION && locus1 != locus2)
 430               || (block1 != NULL_TREE && block1 != block2)))
 431         return false;
 432
 433       return true;
 434     }
 435   return false;
 436 }
 437
 438
 439 /* Create an expression entry for a replaceable expression.  */
 440
 441 static void
 442 process_replaceable (temp_expr_table *tab, gimple *stmt, int call_cnt,
 443                      int reg_vars_cnt)
 444 {
 445   tree var, def, basevar;
 446   int version;
 447   ssa_op_iter iter;
 448   bitmap def_vars, use_vars;
 449
 450   gcc_checking_assert (ter_is_replaceable_p (stmt));
 451
 452   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
 453   version = SSA_NAME_VERSION (def);
 454   def_vars = BITMAP_ALLOC (&ter_bitmap_obstack);
 455
 456   basevar = SSA_NAME_VAR (def);
 457   if (basevar)
 458     bitmap_set_bit (def_vars, DECL_UID (basevar));
 459
 460   /* Add this expression to the dependency list for each use partition.  */
 461   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
 462     {
 463       int var_version = SSA_NAME_VERSION (var);
 464
 465       use_vars = tab->expr_decl_uids[var_version];
 466       add_dependence (tab, version, var);
 467       if (use_vars)
 468         {
 469           bitmap_ior_into (def_vars, use_vars);
 470           BITMAP_FREE (tab->expr_decl_uids[var_version]);
 471         }
 472       else if (SSA_NAME_VAR (var))
 473         bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
 474     }
 475   tab->expr_decl_uids[version] = def_vars;
 476
 477   /* If there are VUSES, add a dependence on virtual defs.  */
 478   if (gimple_vuse (stmt))
 479     {
 480       make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
 481       add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
 482     }
 483
 484   tab->call_cnt[version] = call_cnt;
 485   tab->reg_vars_cnt[version] = reg_vars_cnt;
 486 }
 487
 488
 489 /* This function removes any expression in TAB which is dependent on PARTITION
 490    from consideration, making it not replaceable.  */
 491
 492 static inline void
 493 kill_expr (temp_expr_table *tab, int partition)
 494 {
 495   unsigned version;
 496
 497   /* Mark every active expr dependent on this var as not replaceable.
 498      finished_with_expr can modify the bitmap, so we can't execute over it.  */
 499   while (tab->kill_list[partition])
 500     {
 501       version = bitmap_first_set_bit (tab->kill_list[partition]);
 502       finished_with_expr (tab, version, true);
 503     }
 504
 505   gcc_checking_assert (!tab->kill_list[partition]);
 506 }
 507
 508
 509 /* This function kills all expressions in TAB which are dependent on virtual
 510    partitions.  */
 511
 512 static inline void
 513 kill_virtual_exprs (temp_expr_table *tab)
 514 {
 515   kill_expr (tab, VIRTUAL_PARTITION (tab));
 516 }
 517
 518
 519 /* Mark the expression associated with VAR as replaceable, and enter
 520    the defining stmt into the partition_dependencies table TAB.  If
 521    MORE_REPLACING is true, accumulate the pending partition dependencies.  */
 522
 523 static void
 524 mark_replaceable (temp_expr_table *tab, tree var, bool more_replacing)
 525 {
 526   int version = SSA_NAME_VERSION (var);
 527
 528   /* Move the dependence list to the pending listpending.  */
 529   if (more_replacing && tab->partition_dependencies[version])
 530     bitmap_ior_into (tab->new_replaceable_dependencies,
 531                      tab->partition_dependencies[version]);
 532
 533   finished_with_expr (tab, version, !more_replacing);
 534
 535   /* Set the replaceable expression.
 536      The bitmap for this "escapes" from this file so it's allocated
 537      on the default obstack.  */
 538   if (!tab->replaceable_expressions)
 539     tab->replaceable_expressions = BITMAP_ALLOC (NULL);
 540   bitmap_set_bit (tab->replaceable_expressions, version);
 541 }
 542
 543
 544 /* Helper function for find_ssaname_in_stores.  Called via walk_tree to
 545    find a SSA_NAME DATA somewhere in *TP.  */
 546
 547 static tree
 548 find_ssaname (tree *tp, int *walk_subtrees, void *data)
 549 {
 550   tree var = (tree) data;
 551   if (*tp == var)
 552     return var;
 553   else if (IS_TYPE_OR_DECL_P (*tp))
 554     *walk_subtrees = 0;
 555   return NULL_TREE;
 556 }
 557
 558 /* Helper function for find_replaceable_in_bb.  Return true if SSA_NAME DATA
 559    is used somewhere in T, which is a store in the statement.  Called via
 560    walk_stmt_load_store_addr_ops.  */
 561
 562 static bool
 563 find_ssaname_in_store (gimple *, tree, tree t, void *data)
 564 {
 565   return walk_tree (&t, find_ssaname, data, NULL) != NULL_TREE;
 566 }
 567
 568 /* This function processes basic block BB, and looks for variables which can
 569    be replaced by their expressions.  Results are stored in the table TAB.  */
 570
 571 static void
 572 find_replaceable_in_bb (temp_expr_table *tab, basic_block bb)
 573 {
 574   gimple_stmt_iterator bsi;
 575   gimple *stmt;
 576   tree def, use, fndecl;
 577   int partition;
 578   var_map map = tab->map;
 579   ssa_op_iter iter;
 580   bool stmt_replaceable;
 581   int cur_call_cnt = 0;
 582   int cur_reg_vars_cnt = 0;
 583
 584   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 585     {
 586       stmt = gsi_stmt (bsi);
 587
 588       if (is_gimple_debug (stmt))
 589         continue;
 590
 591       stmt_replaceable = ter_is_replaceable_p (stmt);
 592
 593       /* Determine if this stmt finishes an existing expression.  */
 594       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
 595         {
 596           unsigned ver = SSA_NAME_VERSION (use);
 597
 598           /* If this use is a potential replacement variable, process it.  */
 599           if (tab->expr_decl_uids[ver])
 600             {
 601               bool same_root_var = false;
 602               ssa_op_iter iter2;
 603               bitmap vars = tab->expr_decl_uids[ver];
 604
 605               /* See if the root variables are the same.  If they are, we
 606                  do not want to do the replacement to avoid problems with
 607                  code size, see PR tree-optimization/17549.  */
 608               if (!bitmap_empty_p (vars))
 609                 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
 610                   {
 611                     if (SSA_NAME_VAR (def)
 612                         && bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
 613                       {
 614                         same_root_var = true;
 615                         break;
 616                       }
 617                   }
 618
 619               /* If the stmt does a memory store and the replacement
 620                  is a load aliasing it avoid creating overlapping
 621                  assignments which we cannot expand correctly.  */
 622               if (gimple_vdef (stmt))
 623                 {
 624                   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
 625                   while (is_gimple_assign (def_stmt)
 626                          && gimple_assign_rhs_code (def_stmt) == SSA_NAME)
 627                     def_stmt
 628                       = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
 629                   if (gimple_vuse (def_stmt)
 630                       && gimple_assign_single_p (def_stmt)
 631                       && stmt_may_clobber_ref_p (stmt,
 632                                                  gimple_assign_rhs1 (def_stmt)))
 633                     {
 634                       /* For calls, it is not a problem if USE is among
 635                          call's arguments or say OBJ_TYPE_REF argument,
 636                          all those necessarily need to be evaluated before
 637                          the call that may clobber the memory.  But if
 638                          LHS of the call refers to USE, expansion might
 639                          evaluate it after the call, prevent TER in that
 640                          case.
 641                          For inline asm, allow TER of loads into input
 642                          arguments, but disallow TER for USEs that occur
 643                          somewhere in outputs.  */
 644                       if (is_gimple_call (stmt)
 645                           || gimple_code (stmt) == GIMPLE_ASM)
 646                         {
 647                           if (walk_stmt_load_store_ops (stmt, use, NULL,
 648                                                         find_ssaname_in_store))
 649                             same_root_var = true;
 650                         }
 651                       else
 652                         same_root_var = true;
 653                     }
 654                 }
 655
 656               /* Mark expression as replaceable unless stmt is volatile, or the
 657                  def variable has the same root variable as something in the
 658                  substitution list, or the def and use span a call such that
 659                  we'll expand lifetimes across a call.  We also don't want to
 660                  replace across these expressions that may call libcalls that
 661                  clobber the register involved.  See PR 70184.  */
 662               if (gimple_has_volatile_ops (stmt) || same_root_var
 663                   || (tab->call_cnt[ver] != cur_call_cnt
 664                       && SINGLE_SSA_USE_OPERAND (SSA_NAME_DEF_STMT (use), SSA_OP_USE)
 665                          == NULL_USE_OPERAND_P)
 666                   || tab->reg_vars_cnt[ver] != cur_reg_vars_cnt)
 667                 finished_with_expr (tab, ver, true);
 668               else
 669                 mark_replaceable (tab, use, stmt_replaceable);
 670             }
 671         }
 672
 673       /* Next, see if this stmt kills off an active expression.  */
 674       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
 675         {
 676           partition = var_to_partition (map, def);
 677           if (partition != NO_PARTITION && tab->kill_list[partition])
 678             kill_expr (tab, partition);
 679         }
 680
 681       /* Increment counter if this is a non BUILT_IN call. We allow
 682          replacement over BUILT_IN calls since many will expand to inline
 683          insns instead of a true call.  */
 684       if (is_gimple_call (stmt)
 685           && !((fndecl = gimple_call_fndecl (stmt))
 686                && fndecl_built_in_p (fndecl)))
 687         cur_call_cnt++;
 688
 689       /* Increment counter if this statement sets a local
 690          register variable.  */
 691       if (gimple_assign_single_p (stmt)
 692           && (TREE_CODE (gimple_assign_lhs (stmt)) == VAR_DECL
 693           && DECL_HARD_REGISTER (gimple_assign_lhs (stmt))))
 694         cur_reg_vars_cnt++;
 695
 696       /* Now see if we are creating a new expression or not.  */
 697       if (stmt_replaceable)
 698         process_replaceable (tab, stmt, cur_call_cnt, cur_reg_vars_cnt);
 699
 700       /* Free any unused dependency lists.  */
 701       bitmap_clear (tab->new_replaceable_dependencies);
 702
 703       /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
 704          including the current stmt.  */
 705       if (gimple_vdef (stmt))
 706         kill_virtual_exprs (tab);
 707     }
 708 }
 709
 710
 711 /* This function is the driver routine for replacement of temporary expressions
 712    in the SSA->normal phase, operating on MAP.  If there are replaceable
 713    expressions, a table is returned which maps SSA versions to the
 714    expressions they should be replaced with.  A NULL_TREE indicates no
 715    replacement should take place.  If there are no replacements at all,
 716    NULL is returned by the function, otherwise an expression vector indexed
 717    by SSA_NAME version numbers.  */
 718
 719 bitmap
 720 find_replaceable_exprs (var_map map)
 721 {
 722   basic_block bb;
 723   temp_expr_table *table;
 724   bitmap ret;
 725
 726   bitmap_obstack_initialize (&ter_bitmap_obstack);
 727   table = new_temp_expr_table (map);
 728   FOR_EACH_BB_FN (bb, cfun)
 729     {
 730       find_replaceable_in_bb (table, bb);
 731       gcc_checking_assert (bitmap_empty_p (table->partition_in_use));
 732     }
 733   ret = free_temp_expr_table (table);
 734   bitmap_obstack_release (&ter_bitmap_obstack);
 735   return ret;
 736 }
 737
 738 /* Dump TER expression table EXPR to file F.  */
 739
 740 void
 741 dump_replaceable_exprs (FILE *f, bitmap expr)
 742 {
 743   tree var;
 744   unsigned x;
 745
 746   fprintf (f, "\nReplacing Expressions\n");
 747   for (x = 0; x < num_ssa_names; x++)
 748     if (bitmap_bit_p (expr, x))
 749       {
 750         var = ssa_name (x);
 751         print_generic_expr (f, var, TDF_SLIM);
 752         fprintf (f, " replace with --> ");
 753         print_gimple_stmt (f, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
 754         fprintf (f, "\n");
 755       }
 756   fprintf (f, "\n");
 757 }
 758
 759
 760 /* Dump the status of the various tables in the expression table.  This is used
 761    exclusively to debug TER.  F is the place to send debug info and T is the
 762    table being debugged.  */
 763
 764 DEBUG_FUNCTION void
 765 debug_ter (FILE *f, temp_expr_table *t)
 766 {
 767   unsigned x, y;
 768   bitmap_iterator bi;
 769
 770   fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n",
 771            VIRTUAL_PARTITION (t));
 772   if (t->replaceable_expressions)
 773     dump_replaceable_exprs (f, t->replaceable_expressions);
 774   fprintf (f, "Currently tracking the following expressions:\n");
 775
 776   for (x = 1; x < num_ssa_names; x++)
 777     if (t->expr_decl_uids[x])
 778       {
 779         print_generic_expr (f, ssa_name (x), TDF_SLIM);
 780         fprintf (f, " dep-parts : ");
 781         if (t->partition_dependencies[x]
 782             && !bitmap_empty_p (t->partition_dependencies[x]))
 783           {
 784             EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
 785               fprintf (f, "P%d ",y);
 786           }
 787         fprintf (f, "   basedecls: ");
 788         EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
 789           fprintf (f, "%d ",y);
 790         fprintf (f, "   call_cnt : %d",t->call_cnt[x]);
 791         fprintf (f, "\n");
 792       }
 793
 794   bitmap_print (f, t->partition_in_use, "Partitions in use ",
 795                 "\npartition KILL lists:\n");
 796
 797   for (x = 0; x <= num_var_partitions (t->map); x++)
 798     if (t->kill_list[x])
 799       {
 800         fprintf (f, "Partition %d : ", x);
 801         EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
 802           fprintf (f, "_%d ",y);
 803       }
 804
 805   fprintf (f, "\n----------\n");
 806 }