gcc/tree-ssa-pre.c

   1 /* SSA-PRE for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>
   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, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28
  29 /* These RTL headers are needed for basic-block.h.  */
  30 #include "rtl.h"
  31 #include "tm_p.h"
  32 #include "hard-reg-set.h"
  33 #include "basic-block.h"
  34 #include "diagnostic.h"
  35 #include "tree-inline.h"
  36 #include "tree-flow.h"
  37 #include "tree-gimple.h"
  38 #include "tree-dump.h"
  39 #include "timevar.h"
  40 #include "fibheap.h"
  41 #include "hashtab.h"
  42 #include "tree-iterator.h"
  43 #include "real.h"
  44 #include "alloc-pool.h"
  45 #include "tree-pass.h"
  46 #include "flags.h"
  47
  48
  49 /*
  50
  51    Some of the algorithms are also based on Open64's SSAPRE implementation.
  52
  53    Since the papers are a bit dense to read, take a while to grasp,
  54    and have a few bugs, i'll give a quick rundown:
  55
  56    Normally, in non-SSA form, one performs PRE on expressions using
  57    bit vectors, determining properties for all expressions at once
  58    through bitmap operations and iterative dataflow.
  59
  60    SSAPRE, like most non-SSA->SSA algorithm conversions, operates one
  61    expression at a time, and doesn't use bitvectors or iterative
  62    dataflow.
  63
  64    It answers the question "Given a single hypothetical temporary
  65    variable, what expressions could we eliminate.
  66
  67    To be able to do this, we need an SSA form for expressions.
  68    If you are already confused, you likely think an expression, as
  69    used here, is something like "b_3 = a_2 + 5".  It's not. It's "a +
  70    5". "a_2 + 5" is an *occurrence* of the expression "a + 5".  Just
  71    like PRE, it's lexical equivalence that matters.
  72    Compilers generally give you an SSA form for variables, and maybe
  73    arrays (and/or conditionals).  But not for expressions.
  74
  75    GCC doesn't give you one either, so we have to build it.
  76    Thus, the first steps of SSAPRE are to do just these things.
  77
  78    First we collect lists of occurrences of expressions we are going
  79    to operate on.
  80    Note that:
  81    Unlike the paper, we don't have to ever add newly formed
  82    expressions to the list (for normal SSAPRE, anyway), because we
  83    don't have expressions with more than two operators, and each
  84    operator is either a constant or a variable.  Thus, no second
  85    order effects.
  86
  87    Once we have the lists of occurrences, we process one expression
  88    at a time, doing the following:
  89    1. Using a slightly modified SSA phi placement algorithm, place
  90    expression PHI's for expressions.
  91    2. Using a two step optimistic SSA renaming algorithm, version the
  92    nodes and link phi operands to their real occurrences, if they
  93    exist.  This creates a factored graph of our expression SSA occurrences.
  94    3. Using the factored graph, compute downsafe, avail, and later for
  95    EPHIs (which are SSA versions of the same named bitvector PRE
  96    problems)
  97    4. Using EPHI availability information and versions, compute what
  98    occurrences need to have saves, and what occurrences can be
  99    reloaded from an already saved value.
 100    5. Insert the saves and reloads, and transform EPHIs into regular
 101    phis of the temporary we use for insertion/saving.
 102
 103    See http://citeseer.nj.nec.com/chow97new.html, and
 104    http://citeseer.nj.nec.com/kennedy99partial.html for details of the
 105    algorithm.
 106
 107    kennedy99partial is newer, and is what this implementation is based
 108    on.
 109
 110    For strength reduction addition, see
 111    http://citeseer.nj.nec.com/kennedy98strength.html.
 112
 113    There is also a paper on sparse register promotion using PRE that
 114    contains the basic algorithm for load PRE.  The exact title/url of
 115    the paper escapes me.
 116
 117    Lastly, there is a code hoisting extension that open64 performs
 118    (see opt_ehoist.cxx), but we don't. It's not documented in any
 119    papers, but not that difficult to understand of implement.  */
 120
 121
 122 /* TODOS:
 123    Do strength reduction on a +-b and -a, not just a * <constant>.
 124    */
 125
 126 struct expr_info;
 127 static void clear_all_eref_arrays (void);
 128 static inline bool expr_lexically_eq (const tree, const tree);
 129 static void free_expr_info (struct expr_info *);
 130 static bitmap compute_idfs (bitmap *, tree);
 131 static void set_var_phis (struct expr_info *, tree);
 132 static inline bool names_match_p (const tree, const tree);
 133 static bool is_strred_cand (const tree);
 134 static int pre_expression (struct expr_info *, void *, bitmap);
 135 static bool is_injuring_def (struct expr_info *, tree);
 136 static inline bool okay_injuring_def (tree, tree);
 137 static bool expr_phi_insertion (bitmap *, struct expr_info *);
 138 static tree factor_through_injuries (struct expr_info *, tree, tree, bool *);
 139 static inline tree maybe_find_rhs_use_for_var (tree, tree, unsigned int);
 140 static inline tree find_rhs_use_for_var (tree, tree);
 141 static tree create_ephi_node (basic_block, unsigned int);
 142 static inline int opnum_of_phi (tree, int);
 143 static inline int opnum_of_ephi (const tree, const edge);
 144 static tree subst_phis (struct expr_info *, tree, basic_block, basic_block);
 145 static void generate_expr_as_of_bb (tree, basic_block, basic_block);
 146 static void generate_vops_as_of_bb (tree, basic_block, basic_block);
 147 static void rename_1 (struct expr_info *);
 148 static void process_delayed_rename (struct expr_info *, tree, tree);
 149 static void assign_new_class (tree, varray_type *, varray_type *);
 150 static void create_and_insert_occ_in_preorder_dt_order (struct expr_info *);
 151 static void insert_euse_in_preorder_dt_order (struct expr_info *);
 152 static bool ephi_has_unsafe_arg (tree);
 153 static void reset_down_safe (tree, int);
 154 static void compute_down_safety (struct expr_info *);
 155 static void compute_will_be_avail (struct expr_info *);
 156 static void compute_stops (struct expr_info *);
 157 static bool finalize_1 (struct expr_info *);
 158 static void finalize_2 (struct expr_info *);
 159 static tree occ_identical_to (tree);
 160 static void require_phi (struct expr_info *, basic_block);
 161 static bool really_available_def (tree node);
 162
 163 /* Functions used for an EPHI based depth first search.  */
 164 struct ephi_df_search
 165 {
 166   /* Return true if the ephi has been seen.  */
 167   bool (*seen) (tree);
 168   /* Mark the ephi as seen.  */
 169   void (*set_seen) (tree);
 170   /* Note that the search reaches from one ephi to it's use.  */
 171   void (*reach_from_to) (tree, int, tree);
 172   /* Return true if we should start a search from this PHI.  */
 173   bool (*start_from) (tree);
 174   /* Return true if we should continue the search to this use.  */
 175   bool (*continue_from_to) (tree, int, tree);
 176 };
 177 static bool repl_search_seen (tree);
 178 static void repl_search_set_seen (tree);
 179 static void repl_search_reach_from_to (tree, int, tree);
 180 static bool repl_search_start_from (tree);
 181 static bool repl_search_continue_from_to (tree, int, tree);
 182 static bool stops_search_seen (tree);
 183 static void stops_search_set_seen (tree);
 184 static void stops_search_reach_from_to (tree, int, tree);
 185 static bool stops_search_start_from (tree);
 186 static bool stops_search_continue_from_to (tree, int, tree);
 187 static bool cba_search_seen (tree);
 188 static void cba_search_set_seen (tree);
 189 static bool cba_search_start_from (tree);
 190 static bool cba_search_continue_from_to (tree, int, tree);
 191 struct ephi_df_search cant_be_avail_search = {
 192   cba_search_seen,
 193   cba_search_set_seen,
 194   NULL,
 195   cba_search_start_from,
 196   cba_search_continue_from_to
 197 };
 198
 199 struct ephi_df_search stops_search = {
 200   stops_search_seen,
 201   stops_search_set_seen,
 202   stops_search_reach_from_to,
 203   stops_search_start_from,
 204   stops_search_continue_from_to
 205 };
 206
 207
 208 /* depth-first replacement search used during temp ESSA minimization.  */
 209 struct ephi_df_search replacing_search = {
 210   repl_search_seen,
 211   repl_search_set_seen,
 212   repl_search_reach_from_to,
 213   repl_search_start_from,
 214   repl_search_continue_from_to
 215 };
 216
 217 static void do_ephi_df_search_1 (struct ephi_df_search, tree);
 218 static void do_ephi_df_search (struct expr_info *, struct ephi_df_search);
 219
 220 static inline bool any_operand_injured (tree);
 221 static void code_motion (struct expr_info *);
 222 static tree pick_ssa_name (tree stmt);
 223 #if 0
 224 static tree calculate_increment (struct expr_info *, tree);
 225 #endif
 226 static bool can_insert (tree, int);
 227 static void set_save (struct expr_info *, tree);
 228 static tree reaching_def (tree, tree, basic_block, tree);
 229 static tree do_proper_save (tree , tree, int);
 230 static void process_left_occs_and_kills (varray_type, tree);
 231 static tree create_expr_ref (struct expr_info *, tree, enum tree_code,
 232                              basic_block, tree);
 233 static inline bool ephi_will_be_avail (tree);
 234 static inline tree ephi_at_block (basic_block);
 235 static tree get_default_def (tree, htab_t);
 236 static inline bool same_e_version_real_occ_real_occ (struct expr_info *,
 237                                                      const tree,
 238                                                      const tree);
 239 static inline bool load_modified_phi_result (basic_block, tree);
 240 static inline bool same_e_version_phi_result (struct expr_info *,
 241                                               tree, tree, tree);
 242 static inline bool load_modified_real_occ_real_occ (tree, tree);
 243 static inline bool same_e_version_real_occ_phi_opnd (struct expr_info *,
 244                                                      tree, basic_block,
 245                                                      int, tree, bool *);
 246 static inline bool injured_real_occ_real_occ (struct expr_info *,
 247                                               tree, tree);
 248 static inline bool injured_phi_result_real_occ (struct expr_info *,
 249                                                 tree, tree, basic_block);
 250 static inline bool injured_real_occ_phi_opnd (struct expr_info *,
 251                                               tree, basic_block, int);
 252 static void compute_du_info (struct expr_info *);
 253 static void add_ephi_use (tree, tree, int);
 254 static void insert_one_operand (struct expr_info *, tree, int, tree, edge,
 255                                 tree **);
 256 static void collect_expressions (basic_block, varray_type *);
 257 static int build_dfn_array (basic_block, int);
 258 static int eref_compare (const void *, const void *);
 259
 260
 261 /* Bitmap of E-PHI predecessor operands have already been created.
 262    We only create one phi-pred per block.  */
 263 static bitmap created_phi_preds;
 264
 265 /* PRE dominance frontiers.  */
 266 static bitmap *pre_dfs;
 267
 268 /* Number of redundancy classes.  */
 269 static int class_count = 0;
 270
 271
 272 /* Iterated dominance frontiers cache.  */
 273 static bitmap *idfs_cache;
 274
 275 /* Partial redundancies statistics.  */
 276 static struct pre_stats_d
 277 {
 278   int reloads;
 279   int saves;
 280   int repairs;
 281   int newphis;
 282   int ephi_allocated;
 283   int ephis_current;
 284   int eref_allocated;
 285   int exprs_generated;
 286 } pre_stats = {0, 0, 0, 0, 0, 0, 0, 0};
 287
 288
 289 /* USE entry in list of uses of ephi's.  */
 290 struct ephi_use_entry
 291 {
 292   tree phi;
 293   int opnd_indx;
 294 };
 295
 296 /* PRE Expression specific info.  */
 297 struct expr_info
 298 {
 299   /* The actual expression.  */
 300   tree expr;
 301   /* The occurrences.  */
 302   varray_type occurs;
 303   /* The kills.  */
 304   varray_type kills;
 305   /* The left occurrences.  */
 306   varray_type lefts;
 307   /* An array of real occurrences.  */
 308   varray_type reals;
 309   /* True if it's a strength reduction candidate.  */
 310   bool strred_cand;
 311   /* True if it's a load PRE candidate.  */
 312   bool loadpre_cand;
 313   /* The euses/ephis in preorder dt order.  */
 314   varray_type euses_dt_order;
 315   /* The name of the temporary for this expression.  */
 316   tree temp;
 317 };
 318
 319
 320 /* Cache of expressions generated for given phi operand, to avoid
 321    recomputation and wasting memory.  */
 322 static tree *phi_pred_cache;
 323 static int n_phi_preds;
 324
 325 /* Trying to lookup ephi pred operand indexes takes forever on graphs
 326    that have high connectivity because it's an O(n) linked list
 327    traversal.  Thus, we set up a hashtable that tells us the operand
 328    index for a given edge.  */
 329
 330 typedef struct ephi_pred_index_elt
 331 {
 332   tree ephi;
 333   edge edge;
 334   int opnd;
 335 } ephi_pindex_t;
 336
 337 /* Hash an (ephi, edge, opnd) tuple.  */
 338
 339 static hashval_t
 340 ephi_pindex_hash (const void *p)
 341 {
 342   const ephi_pindex_t *ep = (const ephi_pindex_t *)p;
 343   return htab_hash_pointer (ep->ephi) + htab_hash_pointer (ep->edge);
 344 }
 345
 346 /* Determine equality of an (ephi, edge, opnd) tuple.  */
 347
 348 static int
 349 ephi_pindex_eq (const void *p1, const void *p2)
 350 {
 351   const ephi_pindex_t *ep1 = (const ephi_pindex_t *)p1;
 352   const ephi_pindex_t *ep2 = (const ephi_pindex_t *)p2;
 353
 354   return ep1->ephi == ep2->ephi && ep1->edge == ep2->edge;
 355 }
 356
 357 /* The (ephi, edge) => opnd mapping hashtable.  */
 358 static htab_t ephi_pindex_htab;
 359
 360 /* Add an ephi predecessor to a PHI.  */
 361
 362 static int
 363 add_ephi_pred (tree phi, tree def, edge e)
 364 {
 365   int i = EPHI_NUM_ARGS (phi);
 366   void **slot;
 367   ephi_pindex_t ep, *epp;
 368
 369   EPHI_ARG_PRED (phi, i) = def;
 370   EPHI_ARG_EDGE (phi, i) = e;
 371
 372   ep.ephi = phi;
 373   ep.edge = e;
 374   slot = htab_find_slot (ephi_pindex_htab, (void *)&ep, INSERT);
 375   if (*slot == NULL)
 376     {
 377       epp = xmalloc (sizeof (*epp));
 378       epp->ephi = phi;
 379       epp->edge = e;
 380       epp->opnd = i;
 381       *slot = (void *)epp;
 382     }
 383   else
 384     abort ();
 385
 386   EPHI_NUM_ARGS (phi)++;
 387   return i;
 388 }
 389
 390 /* Create a new EPHI node at basic block BB.  */
 391
 392 static tree
 393 create_ephi_node (basic_block bb, unsigned int add)
 394 {
 395   tree phi;
 396   int len;
 397   edge e;
 398   size_t size;
 399   bb_ann_t ann;
 400
 401   for (len = 0, e = bb->pred; e; e = e->pred_next)
 402     len++;
 403   size = (sizeof (struct tree_ephi_node)
 404           + ((len - 1) * sizeof (struct ephi_arg_d)));
 405
 406   phi = xmalloc (size);
 407   memset (phi, 0, size);
 408   if (add)
 409     {
 410       ann = bb_ann (bb);
 411       if (ann->ephi_nodes == NULL)
 412         ann->ephi_nodes = phi;
 413       else
 414         chainon (ann->ephi_nodes, phi);
 415     }
 416   pre_stats.ephi_allocated += size;
 417   pre_stats.ephis_current += 1;
 418   TREE_SET_CODE (phi, EPHI_NODE);
 419   EPHI_NUM_ARGS (phi) = 0;
 420   EPHI_ARG_CAPACITY (phi) = len;
 421
 422   /* Associate BB to the PHI node.  */
 423   set_bb_for_stmt (phi, bb);
 424
 425   return phi;
 426 }
 427
 428 /* Given DEF (which can be an SSA_NAME or entire statement), and VAR,
 429    find a use of VAR on the RHS of DEF, if one exists. Abort if we
 430    can't find one.  */
 431
 432 static inline tree
 433 find_rhs_use_for_var (tree def, tree var)
 434 {
 435   tree ret = maybe_find_rhs_use_for_var (def, var, 0);
 436   if (!ret)
 437     abort ();
 438   return ret;
 439 }
 440
 441 /* Determine if two trees are referring to the same variable.
 442    Handles SSA_NAME vs non SSA_NAME, etc.  Uses operand_equal_p for
 443    non-trivial cases (INDIRECT_REF and friends).  */
 444
 445 static inline bool
 446 names_match_p (const tree t1, const tree t2)
 447 {
 448   tree name1, name2;
 449
 450   if (t1 == t2)
 451     return true;
 452
 453   if (TREE_CODE (t1) == INDIRECT_REF)
 454     return names_match_p (TREE_OPERAND (t1, 0), t2);
 455
 456   if (TREE_CODE (t2) == INDIRECT_REF)
 457     return names_match_p (t1, TREE_OPERAND (t2, 0));
 458
 459   if (TREE_CODE (t1) == SSA_NAME)
 460     name1 = SSA_NAME_VAR (t1);
 461   else if (DECL_P (t1))
 462     name1 = t1;
 463   else
 464     name1 = NULL_TREE;
 465
 466   if (TREE_CODE (t2) == SSA_NAME)
 467     name2 = SSA_NAME_VAR (t2);
 468   else if (DECL_P (t2))
 469     name2 = t2;
 470   else
 471     name2 = NULL_TREE;
 472
 473   if (name1 == NULL_TREE && name2 != NULL_TREE)
 474     return false;
 475   if (name2 == NULL_TREE && name1 != NULL_TREE)
 476     return false;
 477   if (name1 == NULL_TREE && name2 == NULL_TREE)
 478     return operand_equal_p (t1, t2, 0);
 479
 480   return name1 == name2;
 481 }
 482
 483 /* Given DEF (which can be an SSA_NAME or entire statement), and VAR,
 484    find a use of VAR on the RHS of DEF, if one exists.  Return NULL if
 485    we cannot find one.  */
 486
 487 static inline tree
 488 maybe_find_rhs_use_for_var (tree def, tree var, unsigned int startpos)
 489 {
 490   use_optype uses;
 491   size_t i;
 492
 493   if (SSA_VAR_P (def))
 494     {
 495       if (names_match_p (var, def))
 496         return def;
 497       return NULL_TREE;
 498     }
 499   get_stmt_operands (def);
 500   uses = STMT_USE_OPS (def);
 501
 502   for (i = startpos; i < NUM_USES (uses); i++)
 503     {
 504       tree use = USE_OP (uses, i);
 505       if (names_match_p (use, var))
 506         return use;
 507     }
 508   return NULL_TREE;
 509 }
 510
 511 /* Determine if an injuring def is one which we can repair, and thus,
 512    ignore for purposes of determining the version of a variable.  */
 513
 514 static inline bool
 515 okay_injuring_def (tree inj, tree var)
 516 {
 517   /* Acceptable injuries are those which
 518      1. aren't empty statements.
 519      2. aren't phi nodes.
 520      3. contain a use of VAR on the RHS.  */
 521   if (!inj || IS_EMPTY_STMT (inj)
 522       || TREE_CODE (inj) == PHI_NODE
 523       || !maybe_find_rhs_use_for_var (inj, var, 0))
 524     return false;
 525   return true;
 526 }
 527
 528 /* Return true if INJ is an injuring definition */
 529
 530 static bool
 531 is_injuring_def (struct expr_info *ei, tree inj)
 532 {
 533   /* Things that are never injuring definitions.  */
 534   if (!inj || IS_EMPTY_STMT (inj) || TREE_CODE (inj) == PHI_NODE)
 535     return false;
 536
 537   /* Things we can't handle.  */
 538   if (TREE_CODE (TREE_OPERAND (inj, 1)) != PLUS_EXPR
 539       && TREE_CODE (TREE_OPERAND (inj, 1)) != MINUS_EXPR)
 540     return false;
 541
 542   /* given inj: a1 = a2 + 5
 543      expr: a3 * c
 544      we are testing:
 545      if (a1 != a3
 546      || ! (a2 exists)
 547      || a2 != a3)
 548      return false
 549
 550      Or, in English,  if either the assigned-to variable in
 551      the injury is different from the first variable in the
 552      expression, or the incremented variable is different from the
 553      first variable in the expression, punt.
 554
 555      This makes sure we have something of the form
 556
 557      a = a {+,-} {expr}
 558      for an expression like "a * 5".
 559
 560      This limitation only exists because we don't know how to repair
 561      other forms of increments/decrements.  */
 562   if (!names_match_p (TREE_OPERAND (inj, 0), TREE_OPERAND (ei->expr, 0))
 563       || !TREE_OPERAND (TREE_OPERAND (inj, 1), 0)
 564       || !names_match_p (TREE_OPERAND (TREE_OPERAND (inj, 1), 0),
 565                          TREE_OPERAND (ei->expr, 0)))
 566     return false;
 567
 568   /* If we are strength reducing a multiply, we have the additional
 569      constraints that
 570      1. {expr} is 1
 571      2. {expr} and the RHS of the expression are constants.  */
 572   if (TREE_CODE (ei->expr) == MULT_EXPR)
 573     {
 574       tree irhs1;
 575       tree irhs2;
 576       tree irhs;
 577       irhs = TREE_OPERAND (inj, 1);
 578       irhs1 = TREE_OPERAND (irhs, 0);
 579       irhs2 = TREE_OPERAND (irhs, 1);
 580
 581       if (TREE_CODE (irhs2) != INTEGER_CST)
 582         return false;
 583       if (tree_low_cst (irhs2, 0) == 1)
 584         return true;
 585       if (really_constant_p (irhs2)
 586           && really_constant_p (TREE_OPERAND (ei->expr, 1)))
 587         return true;
 588       /* We don't currently support "the injury is inside a loop,expr is
 589          loop-invariant, and b is either loop-invariant or is
 590          another induction variable with respect to the loop." */
 591       return false;
 592     }
 593   return true;
 594 }
 595
 596 /* Find the statement defining VAR, ignoring injuries we can repair.
 597    START is the first potential injuring def.  */
 598
 599 static tree
 600 factor_through_injuries (struct expr_info *ei, tree start, tree var,
 601                          bool *injured)
 602 {
 603   tree end = start;
 604
 605   while (is_injuring_def (ei, SSA_NAME_DEF_STMT (end)))
 606     {
 607       if (injured)
 608         *injured = true;
 609       end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var);
 610       if (!okay_injuring_def (SSA_NAME_DEF_STMT (end), var))
 611         break;
 612       if (dump_file)
 613         {
 614           fprintf (dump_file, "Found a real injury:");
 615           print_generic_stmt (dump_file, SSA_NAME_DEF_STMT (end), dump_flags);
 616           fprintf (dump_file, "\n");
 617         }
 618       if (injured)
 619         *injured = true;
 620       end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var);
 621     }
 622   return end;
 623 }
 624
 625 /* Return true if the result of the EPHI, when transformed into a phi,
 626    will be available.  */
 627
 628 static inline bool
 629 ephi_will_be_avail (tree ephi)
 630 {
 631   if (!EPHI_CANT_BE_AVAIL (ephi))
 632     if (EPHI_STOPS (ephi))
 633       return true;
 634
 635   return false;
 636 }
 637
 638 /* EUSE node pool.  We allocate EUSE nodes out of this*/
 639 static alloc_pool euse_node_pool;
 640
 641 /* EREF node pool.  We allocate regular EREF nodes (like EEXIT_NODE)
 642    out of this.  */
 643 static alloc_pool eref_node_pool;
 644
 645
 646 /* To order EREF's in a given block, we assign them each an ID based
 647    on when we see them.  */
 648 static int eref_id_counter = 0;
 649
 650 /* Creation an expression reference of TYPE.  */
 651
 652 static tree
 653 create_expr_ref (struct expr_info *ei, tree expr, enum tree_code type,
 654                  basic_block bb, tree parent)
 655 {
 656   tree ret;
 657   if (type == EPHI_NODE)
 658     {
 659       int len;
 660       edge e;
 661
 662       ret = create_ephi_node (bb, 1);
 663       for (len = 0, e = bb->pred; e; e = e->pred_next)
 664         len++;
 665
 666       EREF_TEMP (ret) = make_phi_node (ei->temp, len);
 667     }
 668   else
 669     {
 670       if (type == EUSE_NODE)
 671         ret = (tree) pool_alloc (euse_node_pool);
 672       else
 673         ret = (tree) pool_alloc (eref_node_pool);
 674       TREE_SET_CODE (ret, type);
 675       memset (ret, 0, tree_size (ret));
 676       TREE_SET_CODE (ret, type);
 677       pre_stats.eref_allocated += tree_size (ret);
 678     }
 679
 680   EREF_NAME (ret) = expr;
 681   set_bb_for_stmt (ret, bb);
 682   EREF_STMT (ret) = parent;
 683   EREF_SAVE (ret) = false;
 684   EREF_ID (ret) = eref_id_counter++;
 685
 686   return ret;
 687 }
 688
 689
 690 /* dfphis is a bitmap of where we need to insert ephis due to the
 691    iterated dominance frontier of an expression.  */
 692
 693 static bitmap dfphis;
 694
 695 /* varphis is a bitmap of where we need to insert ephis due to the
 696    presence of phis for a variable.  */
 697
 698 static bitmap varphis;
 699
 700
 701 /* Function to recursively figure out where EPHI's need to be placed
 702    because of PHI's.
 703    We always place EPHI's where we place PHI's because they are also
 704    partially anticipated expression points (because some expression
 705    alteration reaches that merge point).
 706
 707    We do this recursively, because we have to figure out
 708    EPHI's for the variables in the PHI as well.  */
 709
 710 static void
 711 set_var_phis (struct expr_info *ei, tree phi)
 712 {
 713   basic_block bb = bb_for_stmt (phi);
 714   /* If we've already got an EPHI set to be placed in PHI's BB, we
 715      don't need to do this again.  */
 716   if (!bitmap_bit_p (varphis, bb->index)
 717         && !bitmap_bit_p (dfphis, bb->index))
 718     {
 719       tree phi_operand;
 720       int curr_phi_operand;
 721       bitmap_set_bit (varphis, bb->index);
 722       for (curr_phi_operand = 0;
 723            curr_phi_operand < PHI_NUM_ARGS (phi);
 724            curr_phi_operand++)
 725         {
 726           phi_operand = PHI_ARG_DEF (phi, curr_phi_operand);
 727           /* For strength reduction, factor through injuries we can
 728              repair.  */
 729           if (ei->strred_cand && TREE_CODE (phi_operand) != PHI_NODE)
 730             {
 731               phi_operand = factor_through_injuries (ei, phi_operand,
 732                                                      SSA_NAME_VAR (phi_operand),
 733                                                      NULL);
 734               phi_operand = SSA_NAME_DEF_STMT (phi_operand);
 735               if (dump_file)
 736                 {
 737                   fprintf (dump_file, "After factoring through injuries:");
 738                   print_generic_stmt (dump_file, phi_operand, dump_flags);
 739                   fprintf (dump_file, "\n");
 740                 }
 741             }
 742
 743           /* If our phi operand is defined by a phi, we need to
 744              record where the phi operands alter the expression as
 745              well, and place EPHI's at each point.  */
 746           if (TREE_CODE (phi_operand) == PHI_NODE)
 747             set_var_phis (ei, phi_operand);
 748         }
 749     }
 750 }
 751
 752
 753 /* Clear all the expression reference arrays.  */
 754
 755 static void
 756 clear_all_eref_arrays (void)
 757 {
 758   basic_block bb;
 759   bb_ann_t ann;
 760
 761   FOR_ALL_BB (bb)
 762     {
 763       ann = bb_ann (bb);
 764       if (ann->ephi_nodes)
 765         {
 766           free (ann->ephi_nodes);
 767           pre_stats.ephis_current -= 1;
 768         }
 769       ann->ephi_nodes = NULL;
 770     }
 771 }
 772
 773 /* EPHI insertion algorithm.  */
 774
 775 static bool
 776 expr_phi_insertion (bitmap *dfs, struct expr_info *ei)
 777 {
 778   size_t i, j;
 779   vuse_optype vuses;
 780   use_optype uses;
 781   bool retval = true;
 782
 783   dfphis = BITMAP_XMALLOC ();
 784   bitmap_zero (dfphis);
 785   varphis = BITMAP_XMALLOC ();
 786   bitmap_zero (varphis);
 787
 788   /*  Compute where we need to place EPHIS. There are two types of
 789       places we need EPHI's: Those places we would normally place a
 790       PHI for the occurrence (calculated by determining the IDF+ of
 791       the statement), and those places we need an EPHI due to partial
 792       anticipation.  */
 793   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++)
 794     {
 795       tree occurp = VARRAY_TREE (ei->occurs, i);
 796       tree occur = occurp ? occurp : NULL;
 797       tree killp = VARRAY_TREE (ei->kills, i);
 798       tree kill = killp ? killp : NULL;
 799       tree leftp = VARRAY_TREE (ei->lefts, i);
 800       tree left = leftp ? leftp : NULL;
 801       bitmap temp;
 802       stmt_ann_t ann;
 803
 804 #ifdef ENABLE_CHECKING
 805       if ((kill && occur) || (left && occur) || (kill && left))
 806         abort();
 807 #endif
 808       occurp = occur ? occurp : kill ? killp : leftp;
 809       occur = occur ? occur : kill ? kill : left;
 810       temp = compute_idfs (dfs, occur);
 811       bitmap_a_or_b (dfphis, dfphis, temp);
 812       if (kill != NULL)
 813         continue;
 814       get_stmt_operands (occurp);
 815       ann = stmt_ann (occurp);
 816       uses = USE_OPS (ann);
 817       for (j = 0; j < NUM_USES (uses); j ++)
 818         {
 819           tree use = USE_OP (uses, j);
 820           if (ei->strred_cand)
 821             use = factor_through_injuries (ei, use, SSA_NAME_VAR (use),
 822                                            NULL);
 823           if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE)
 824             continue;
 825           set_var_phis (ei, SSA_NAME_DEF_STMT (use));
 826         }
 827       if (ei->loadpre_cand && TREE_CODE (ei->expr) == INDIRECT_REF)
 828         {
 829           vuses = VUSE_OPS (ann);
 830           for (j = 0; j < NUM_VUSES (vuses); j ++)
 831             {
 832               tree use = VUSE_OP (vuses, j);
 833               if (ei->strred_cand)
 834                 use = factor_through_injuries (ei, use, SSA_NAME_VAR (use),
 835                                                NULL);
 836               if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE)
 837                 continue;
 838               set_var_phis (ei, SSA_NAME_DEF_STMT (use));
 839             }
 840         }
 841     }
 842   /* Union the results of the dfphis and the varphis to get the
 843      answer to everywhere we need EPHIS.  */
 844   bitmap_a_or_b (dfphis, dfphis, varphis);
 845
 846   /* Now create the EPHI's in each of these blocks.  */
 847   EXECUTE_IF_SET_IN_BITMAP(dfphis, 0, i,
 848   {
 849     tree ref = create_expr_ref (ei, ei->expr, EPHI_NODE, BASIC_BLOCK (i),
 850                                 NULL);
 851     EREF_PROCESSED (ref) = false;
 852     EPHI_DOWNSAFE (ref) = true;
 853     EPHI_DEAD (ref) = true;
 854   });
 855 #if 0
 856   /* If there are no phis, we don't have anything to optimize,
 857      assuming the dominator optimizer took care of it all.  */
 858   if (bitmap_first_set_bit (dfphis) == -1)
 859     retval = false;
 860 #endif
 861   BITMAP_XFREE (dfphis);
 862   BITMAP_XFREE (varphis);
 863   return retval;
 864
 865 }
 866
 867 /* Return the EPHI at block BB, if one exists.  */
 868
 869 static inline tree
 870 ephi_at_block (basic_block bb)
 871 {
 872   bb_ann_t ann = bb_ann (bb);
 873   if (ann->ephi_nodes)
 874     return ann->ephi_nodes;
 875   else
 876     return NULL_TREE;
 877 }
 878
 879 /* Depth first numbering array.  */
 880 static int *dfn;
 881
 882 /* Build a depth first numbering array to be used in sorting in
 883    dominator order.  */
 884
 885 static int
 886 build_dfn_array (basic_block bb, int num)
 887 {
 888   basic_block son;
 889
 890   if (bb->index >= 0)
 891     dfn[bb->index] = num;
 892
 893   for (son = first_dom_son (CDI_DOMINATORS, bb);
 894        son;
 895        son = next_dom_son (CDI_DOMINATORS, son))
 896     num = build_dfn_array (son, ++num);
 897   return num;
 898 }
 899
 900
 901 /* Compare two EREF's in terms of dominator preorder.  Return -1 if
 902    ELEM1 goes before ELEM2, 1 if ELEM1 goes after ELEM2, and 0 if they
 903    are equal.  */
 904
 905 static int
 906 eref_compare (const void *elem1, const void *elem2)
 907 {
 908   tree t1 = *(tree *)elem1;
 909   tree t2 = *(tree *)elem2;
 910   basic_block bb1, bb2;
 911   if (t1 == t2)
 912     return 0;
 913   bb1 = bb_for_stmt (t1);
 914   bb2 = bb_for_stmt (t2);
 915   if (bb1 == bb2)
 916     {
 917       if (TREE_CODE (t1) == EEXIT_NODE)
 918         return 1;
 919       if (TREE_CODE (t2) == EEXIT_NODE)
 920         return -1;
 921       if (TREE_CODE (t1) == EPHI_NODE)
 922         return -1;
 923       if (TREE_CODE (t2) == EPHI_NODE)
 924         return 1;
 925       if ((TREE_CODE (t1) == EUSE_NODE && EUSE_PHIOP (t1))
 926           && (TREE_CODE (t2) == EUSE_NODE && !EUSE_PHIOP (t2)))
 927         return 1;
 928       if ((TREE_CODE (t1) == EUSE_NODE && !EUSE_PHIOP (t1))
 929           && (TREE_CODE (t2) == EUSE_NODE && EUSE_PHIOP (t2)))
 930         return -1;
 931       if (TREE_CODE (t1) == EUSE_NODE && TREE_CODE (t2) == EUSE_NODE)
 932         return EREF_ID (t1) - EREF_ID (t2);
 933       if (TREE_CODE (t1) == EPHI_NODE && TREE_CODE (t2) == EPHI_NODE)
 934         abort ();
 935
 936     }
 937   else
 938     {
 939       if (dfn[bb1->index] == dfn[bb2->index])
 940         {
 941           if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
 942             return 1;
 943           else
 944             return -1;
 945         }
 946       else
 947         return (dfn[bb1->index] < dfn[bb2->index]) ? -1 : 1;
 948     }
 949
 950   abort ();
 951 }
 952
 953 /* Create expression references for occurrences, kills, phi operands,
 954    and the like.  At the same time,  insert the occurrences into the
 955    ei->euses_dt_order array in the proper order.  If this function had
 956    any use outside of rename_1, you could split it into two
 957    functions, one creating, one inserting.  */
 958
 959 static void
 960 create_and_insert_occ_in_preorder_dt_order (struct expr_info *ei)
 961 {
 962   size_t i;
 963   edge succ;
 964   tree curr_phi_pred = NULL_TREE;
 965   basic_block block;
 966
 967   /* The ephis references were already created, so just push them into
 968      the euses_dt_order list.  */
 969   FOR_EACH_BB (block)
 970   {
 971     tree ephi = ephi_at_block (block);
 972     /* The ordering for a given BB is EPHI's, real/left/kill
 973        occurrences, phi preds, exit occurrences.  */
 974     if (ephi != NULL_TREE)
 975       VARRAY_PUSH_TREE (ei->euses_dt_order, ephi);
 976   }
 977
 978   /* The non-ephis have to actually be created, so do that, then push
 979      them into the list.  */
 980
 981   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++)
 982       {
 983         tree newref;
 984         tree current;
 985         current = VARRAY_TREE (ei->occurs, i);
 986         current = current ? current : VARRAY_TREE (ei->kills, i);
 987         current = current ? current : VARRAY_TREE (ei->lefts, i);
 988         block = bb_for_stmt (current);
 989         if (VARRAY_TREE (ei->kills, i) != NULL)
 990           {
 991             tree killexpr  = VARRAY_TREE (ei->kills, i);
 992             tree killname = ei->expr;
 993             newref = create_expr_ref (ei, killname, EKILL_NODE, block, killexpr);
 994             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
 995           }
 996         else if (VARRAY_TREE (ei->lefts, i) != NULL)
 997           {
 998             tree occurexpr = VARRAY_TREE (ei->lefts, i);
 999             tree occurname;
1000             occurname = ei->expr;
1001             newref = create_expr_ref (ei, occurname, EUSE_NODE, block,
1002                                       occurexpr);
1003             EUSE_DEF (newref) = NULL_TREE;
1004             EUSE_LVAL (newref) = true;
1005             EREF_CLASS (newref) = -1;
1006             EUSE_PHIOP (newref) = false;
1007             EREF_PROCESSED (newref) = false;
1008             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1009           }
1010         else
1011           {
1012             tree occurexpr = VARRAY_TREE (ei->occurs, i);
1013             tree occurname;
1014             occurname = ei->expr;
1015             newref = create_expr_ref (ei, occurname, EUSE_NODE, block,
1016                                       occurexpr);
1017             EUSE_DEF (newref) = NULL_TREE;
1018             EREF_CLASS (newref) = -1;
1019             EUSE_PHIOP (newref) = false;
1020             EREF_PROCESSED (newref) = false;
1021             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1022           }
1023       }
1024
1025   /* Lastly, we need to create and insert the ephi operand occurrences
1026      into the list.  */
1027   FOR_ALL_BB (block)
1028   {
1029     /* Insert the phi operand occurrences into the list at the
1030        successors.*/
1031     for (succ = block->succ; succ; succ = succ->succ_next)
1032       {
1033         if (succ->dest != EXIT_BLOCK_PTR)
1034           {
1035             tree ephi = ephi_at_block (succ->dest);
1036             if (ephi != NULL
1037                 && !bitmap_bit_p (created_phi_preds, block->index))
1038               {
1039                 tree newref = create_expr_ref (ei, 0, EUSE_NODE, block, NULL);
1040                 curr_phi_pred = newref;
1041                 VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1042                 EUSE_DEF (newref) = NULL_TREE;
1043                 EREF_CLASS (newref) = -1;
1044                 EUSE_PHIOP (newref) = true;
1045                 EREF_SAVE (newref) = false;
1046                 EREF_RELOAD (newref) = false;
1047                 EUSE_INSERTED (newref) = false;
1048                 EREF_PROCESSED (newref) = false;
1049                 bitmap_set_bit (created_phi_preds, block->index);
1050                 add_ephi_pred (ephi, newref, succ);
1051               }
1052             else if (ephi != NULL)
1053               {
1054 #ifdef ENABLE_CHECKING
1055                 if (curr_phi_pred == NULL_TREE)
1056                   abort();
1057 #endif
1058                 add_ephi_pred (ephi, curr_phi_pred, succ);
1059               }
1060           }
1061         else if (succ->dest == EXIT_BLOCK_PTR && !(succ->flags & EDGE_FAKE))
1062           {
1063             /* No point in inserting exit blocks into heap first, since
1064                they'll never be anything on the stack.  */
1065             tree newref;
1066             newref = create_expr_ref (ei, ei->expr, EEXIT_NODE,
1067                                       block,
1068                                       NULL);
1069             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1070           }
1071       }
1072   }
1073   qsort (ei->euses_dt_order->data.tree,
1074          VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
1075          sizeof (tree),
1076          eref_compare);
1077 }
1078
1079
1080 /* Assign a new redundancy class to the occurrence, and push it on the
1081    renaming stack.  */
1082
1083 static void
1084 assign_new_class (tree occ, varray_type * stack, varray_type * stack2)
1085 {
1086   /* class(occ) <- count
1087      Push(occ, stack)
1088      count <- count + 1
1089   */
1090   EREF_CLASS (occ) = class_count;
1091   VARRAY_PUSH_TREE (*stack, occ);
1092   if (stack2)
1093     VARRAY_PUSH_TREE (*stack2, occ);
1094   class_count++;
1095 }
1096
1097 /* Determine if two real occurrences have the same ESSA version.
1098    We do this by hashing the expressions and comparing the hash
1099    values.  Even if they don't match, we then see if this is a
1100    strength reduction candidate, and if so, if the use is simply
1101    injured.  */
1102
1103 static inline bool
1104 same_e_version_real_occ_real_occ (struct expr_info *ei,
1105                                   const tree def, const tree use)
1106 {
1107   hashval_t expr1val;
1108   hashval_t expr2val;
1109   vuse_optype vuses;
1110   size_t i;
1111   const tree t1 = EREF_STMT (def);
1112   const tree t2 = EREF_STMT (use);
1113
1114   expr1val = iterative_hash_expr (TREE_OPERAND (t1, 1), 0);
1115   expr2val = iterative_hash_expr (TREE_OPERAND (t2, 1), 0);
1116
1117   if (expr1val == expr2val)
1118     {
1119       vuses = STMT_VUSE_OPS (t1);
1120       for (i = 0; i < NUM_VUSES (vuses); i++)
1121         expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val);
1122       vuses = STMT_VUSE_OPS (t2);
1123       for (i = 0; i < NUM_VUSES (vuses); i++)
1124         expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val);
1125       if (expr1val != expr2val)
1126         return false;
1127     }
1128
1129   /* If the def is injured, and the expressions have the same value,
1130      then the use is injured.  */
1131   if (expr1val == expr2val)
1132     {
1133       if (EREF_INJURED (def))
1134         EREF_INJURED (use) = true;
1135       return true;
1136     }
1137
1138   /* Even if the expressions don't have the same value, it might be
1139      the case that the use is simply injured, in which case, it's
1140      still okay.  */
1141   if (expr1val != expr2val && ei->strred_cand)
1142     {
1143       if (injured_real_occ_real_occ (ei, def, use))
1144         {
1145           EREF_INJURED (use) = true;
1146           return true;
1147         }
1148     }
1149   return false;
1150 }
1151
1152 /* Determine if the use occurrence is injured.
1153    TODO: Finish actually implementing this.  */
1154
1155 static inline bool
1156 injured_real_occ_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED,
1157                            tree def ATTRIBUTE_UNUSED,
1158                            tree use ATTRIBUTE_UNUSED)
1159 {
1160   tree defstmt;
1161   tree defvar;
1162
1163   defstmt = EREF_STMT (def);
1164   if (TREE_CODE (TREE_OPERAND (defstmt, 0)) != SSA_NAME)
1165     return false;
1166
1167   defvar = TREE_OPERAND (defstmt, 0);
1168   /* XXX: Implement.  */
1169   return false;
1170
1171 }
1172
1173 /* Determine the operand number of edge E in EPHI.  */
1174
1175 static inline int
1176 opnum_of_ephi (const tree ephi, const edge e)
1177 {
1178   ephi_pindex_t ep, *epp;
1179
1180   ep.ephi = ephi;
1181   ep.edge = e;
1182   epp = htab_find (ephi_pindex_htab, &ep);
1183   if (epp == NULL)
1184     abort ();
1185   return epp->opnd;
1186 }
1187
1188 /* Determine the phi operand index for J in PHI.  */
1189
1190 static inline int
1191 opnum_of_phi (tree phi, int j)
1192 {
1193   int i;
1194   /* We can't just count predecessors, since tree-ssa.c generates them
1195      when it sees a phi in the successor during it's traversal.  So the
1196      order is dependent on the traversal order.  */
1197   for (i = 0 ; i < PHI_NUM_ARGS (phi); i++)
1198     if (PHI_ARG_EDGE (phi, i)->src->index == j)
1199       return i;
1200
1201   abort();
1202 }
1203
1204 /* Generate EXPR as it would look in basic block PRED (using the phi in
1205    block BB).  We do this by replacing the variables with the phi
1206    argument definitions for block J if they are defined by a phi in
1207    block BB.  */
1208
1209 static void
1210 generate_expr_as_of_bb (tree expr, basic_block pred, basic_block bb)
1211 {
1212   use_optype uses = STMT_USE_OPS (expr);
1213   bool replaced_constants = false;
1214   size_t k;
1215
1216   for (k = 0; k < NUM_USES (uses); k++)
1217     {
1218       tree *vp = USE_OP_PTR (uses, k);
1219       tree v = *vp;
1220       tree phi;
1221
1222       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1223         {
1224           if (PHI_RESULT (phi) ==  v)
1225             {
1226               int opnum = opnum_of_phi (phi, pred->index);
1227               tree p = PHI_ARG_DEF (phi, opnum);
1228               replace_exp (vp, p);
1229               if (!phi_ssa_name_p (p))
1230                 replaced_constants = true;
1231               break;
1232             }
1233         }
1234     }
1235
1236   /* If we've substituted in new constants, we must be sure to
1237      simplify the result lest we crash in get_expr_operands.  */
1238   if (replaced_constants)
1239     fold_stmt (&expr);
1240 }
1241
1242 /* Generate VUSE ops as they would look in basic block PRED (using the
1243    phi in block BB).  Done the same way as we do generation of regular
1244    ops for the bb.  */
1245
1246 static void
1247 generate_vops_as_of_bb (tree expr, basic_block pred, basic_block bb)
1248 {
1249   vuse_optype vuses = STMT_VUSE_OPS (expr);
1250   size_t i;
1251
1252   for (i = 0; i < NUM_VUSES (vuses); i++)
1253     {
1254       tree v = VUSE_OP (vuses, i);
1255       tree phi;
1256
1257       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1258         {
1259           if (PHI_RESULT (phi) == v)
1260             {
1261               int opnum = opnum_of_phi (phi, pred->index);
1262               tree p = PHI_ARG_DEF (phi, opnum);
1263               replace_exp (VUSE_OP_PTR (vuses, i), p);
1264               break;
1265             }
1266         }
1267     }
1268 }
1269
1270 /* Make a copy of Z as it would look in basic block PRED, using the PHIs
1271    in BB.  */
1272
1273 static tree
1274 subst_phis (struct expr_info *ei, tree Z, basic_block pred, basic_block bb)
1275 {
1276   tree stmt_copy;
1277   size_t i;
1278
1279   /* Return the cached version, if we have one.  */
1280   if (pred->index < n_phi_preds
1281       && phi_pred_cache[pred->index] != NULL_TREE)
1282     return phi_pred_cache[pred->index];
1283
1284   /* Otherwise, generate a new expression.  */
1285   pre_stats.exprs_generated++;
1286   stmt_copy = unshare_expr (Z);
1287   create_stmt_ann (stmt_copy);
1288   modify_stmt (stmt_copy);
1289   get_stmt_operands (stmt_copy);
1290   generate_expr_as_of_bb (stmt_copy, pred, bb);
1291   set_bb_for_stmt (stmt_copy, bb);
1292   modify_stmt (stmt_copy);
1293   get_stmt_operands (stmt_copy);
1294
1295   /* If we have vuses on the original statement, and we still have
1296      use_ops on the generated expr, we need to copy the vuses.  */
1297
1298   if (ei->loadpre_cand
1299       && NUM_VUSES (STMT_VUSE_OPS (Z)) != 0
1300       && NUM_USES (STMT_USE_OPS (stmt_copy)) != 0)
1301     {
1302       vuse_optype vuses = STMT_VUSE_OPS (Z);
1303       remove_vuses (stmt_copy);
1304
1305       start_ssa_stmt_operands (stmt_copy);
1306       for (i = 0; i < NUM_VUSES (vuses); i++)
1307         add_vuse (VUSE_OP (vuses, i), stmt_copy);
1308       finalize_ssa_stmt_operands (stmt_copy);
1309
1310       generate_vops_as_of_bb (stmt_copy, pred, bb);
1311     }
1312   else
1313     {
1314       remove_vuses (stmt_copy);
1315       remove_v_may_defs (stmt_copy);
1316       remove_v_must_defs (stmt_copy);
1317     }
1318
1319   if (pred->index < n_phi_preds)
1320     phi_pred_cache[pred->index] = stmt_copy;
1321   return stmt_copy;
1322 }
1323
1324 /* Determine if def and use_tree should have the same e-version.  We do
1325    this by simply determining if something modifies the expression
1326    between DEF and USE_TREE.  USE_TREE was generated from the OPND_NUM'th
1327    operand of the EPHI in USE_BB.  If it is modified, we determine if
1328    it is simply injured, and thus, okay.  */
1329
1330 static inline bool
1331 same_e_version_real_occ_phi_opnd (struct expr_info *ei, tree def,
1332                                        basic_block use_bb, int opnd_num,
1333                                        tree use_tree, bool *injured)
1334 {
1335   bool not_mod = true;
1336   *injured = false;
1337
1338   if (load_modified_real_occ_real_occ (EREF_STMT (def),
1339                                        use_tree))
1340     not_mod = false;
1341
1342   if (not_mod)
1343     return true;
1344   else if (ei->strred_cand)
1345     {
1346       if (injured_real_occ_phi_opnd (ei, def, use_bb, opnd_num))
1347         return true;
1348     }
1349   return false;
1350 }
1351
1352 /* Determine whether the OPND_NUM'th operand of USE_BB's EPHI is an
1353    injured version of DEF.  */
1354 static inline bool
1355 injured_real_occ_phi_opnd (struct expr_info *ei ATTRIBUTE_UNUSED,
1356                                 tree def ATTRIBUTE_UNUSED,
1357                                 basic_block use_bb ATTRIBUTE_UNUSED,
1358                                 int opnd_num ATTRIBUTE_UNUSED)
1359 {
1360   /* XXX: Implement.  */
1361   return false;
1362 }
1363
1364 /* Determine whether the expression is modified between DEF and USE,
1365    by comparing the hash values of the two expressions.  */
1366 static inline bool
1367 load_modified_real_occ_real_occ (tree def, tree use)
1368 {
1369   hashval_t expr1val;
1370   hashval_t expr2val;
1371   vuse_optype vuses;
1372   size_t i;
1373
1374   if (TREE_CODE (def) == VA_ARG_EXPR)
1375     expr1val = iterative_hash_expr (def, 0);
1376   else
1377     expr1val = iterative_hash_expr (TREE_OPERAND (def, 1), 0);
1378
1379   if (TREE_CODE (use) == VA_ARG_EXPR)
1380     expr2val = iterative_hash_expr (use, 0);
1381   else
1382     expr2val = iterative_hash_expr (TREE_OPERAND (use, 1), 0);
1383
1384   if (expr1val == expr2val)
1385     {
1386       vuses = STMT_VUSE_OPS (def);
1387       for (i = 0; i < NUM_VUSES (vuses); i++)
1388         expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val);
1389       vuses = STMT_VUSE_OPS (use);
1390       for (i = 0; i < NUM_VUSES (vuses); i++)
1391         expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val);
1392       if (expr1val != expr2val)
1393         return false;
1394     }
1395   return expr1val != expr2val;
1396 }
1397
1398 /* Determine if the expression is modified between the start of BB,
1399    and the use at USE, ignoring phis.  We do this by simple
1400    domination, because of the properties of SSA.  */
1401 static bool
1402 load_modified_phi_result (basic_block bb, tree use)
1403 {
1404   basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
1405   if (defbb != bb)
1406     {
1407       /* This guards against moving around undefined variables.
1408          However, PARM_DECL is special because it *IS* live on entry,
1409          so it's not really undefined.  */
1410       if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) != PARM_DECL)
1411         return true;
1412       else if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) == PARM_DECL)
1413         return false;
1414       if (dominated_by_p (CDI_DOMINATORS, bb, defbb))
1415         return false;
1416     }
1417   else
1418     {
1419       if (TREE_CODE (SSA_NAME_DEF_STMT (use)) == PHI_NODE)
1420         return false;
1421     }
1422   return true;
1423 }
1424
1425 /* Determine if the variables in EXP are modified between DEF and
1426    USE.  If they are, we have to give a new e-version to the result.
1427    For load PRE, we have to check the vuses too.  For strength
1428    reduction, we need to check whether the modification is a simple
1429    injury.  */
1430
1431 static bool
1432 same_e_version_phi_result (struct expr_info *ei, tree def, tree exp,
1433                                 tree use)
1434 {
1435   stmt_ann_t ann = stmt_ann (exp);
1436   bool not_mod = true;
1437   size_t i;
1438   use_optype real_expuses = USE_OPS (ann);
1439   vuse_optype expuses;
1440
1441
1442   if (NUM_USES (real_expuses) == 0)
1443     return false;
1444
1445   for (i = 0; i < NUM_USES (real_expuses) && not_mod; i++)
1446     {
1447       tree *use1p = USE_OP_PTR (real_expuses, i);
1448       tree use1;
1449       if (!use1p)
1450         continue;
1451       use1 = *use1p;
1452       if (load_modified_phi_result (bb_for_stmt (def), use1))
1453         not_mod = false;
1454     }
1455
1456   if (not_mod && ei->loadpre_cand)
1457     {
1458       expuses = VUSE_OPS (ann);
1459
1460       for (i = 0; i < NUM_VUSES (expuses) && not_mod; i++)
1461         {
1462           tree use1 = VUSE_OP (expuses, i);
1463           if (load_modified_phi_result (bb_for_stmt (def), use1))
1464             not_mod = false;
1465         }
1466     }
1467
1468   if (not_mod)
1469     return true;
1470   else if (ei->strred_cand)
1471     {
1472       if (injured_phi_result_real_occ (ei, def, exp, bb_for_stmt (use)))
1473         {
1474           EREF_INJURED (use) = true;
1475           return true;
1476         }
1477     }
1478
1479   return false;
1480 }
1481
1482 /* Determine whether USE_TREE is an injured version of DEF.  */
1483
1484 static inline bool
1485 injured_phi_result_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED,
1486                              tree def ATTRIBUTE_UNUSED,
1487                              tree use_tree ATTRIBUTE_UNUSED,
1488                              basic_block use_bb ATTRIBUTE_UNUSED)
1489 {
1490   /* XXX: Implement.  */
1491   return false;
1492 }
1493
1494 /* Delayed renaming checks to make sure the optimistic assumptions
1495    about ephi operand versions in rename_1 actually turned out to be
1496    true.  This requires generating the expressions for each ephi
1497    operand, and comparing them to the versions of the occurrence it is
1498    defined by.
1499    Delayed rename handling is done like open64 does it.  Basically,
1500    like the delayed renaming is described in the paper, with
1501    extensions for strength reduction.  */
1502
1503 static void
1504 process_delayed_rename (struct expr_info *ei, tree use, tree real_occ)
1505 {
1506   tree exp_phi = use;
1507   int opnd_num = 0;
1508
1509   /* We only care about operands we actually have DELAYED_RENAME set
1510      on.  */
1511   for (opnd_num = 0; opnd_num < EPHI_NUM_ARGS (exp_phi); opnd_num++)
1512     {
1513       tree opnd = EPHI_ARG_DEF (exp_phi, opnd_num);
1514       if (EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num))
1515         {
1516           tree def;
1517           tree newexp;
1518
1519           /* Mark it as being processed, then generate the ephi
1520              operand expression.  */
1521           EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num) = false;
1522           def = opnd;
1523           newexp = subst_phis (ei, real_occ,
1524                               EPHI_ARG_EDGE (exp_phi, opnd_num)->src,
1525                               bb_for_stmt (exp_phi));
1526
1527           /* For operands defined by EPHIs, we need to compare the
1528              generated expression and the phi result.
1529              For operands defined by real occurrences, we simply compare
1530              the phi operand and the real occurrence.  */
1531           if (TREE_CODE (def) == EPHI_NODE)
1532             {
1533               tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num);
1534               EREF_STMT (tmp_use) = newexp;
1535               if (same_e_version_phi_result (ei, def, newexp,
1536                                              tmp_use))
1537                 {
1538
1539                   if (EREF_INJURED (tmp_use))
1540                     {
1541                       EREF_INJURED (tmp_use) = false;
1542                       EPHI_ARG_INJURED (exp_phi, opnd_num) = true;
1543                     }
1544                   if (EREF_STMT (def) == NULL)
1545                     {
1546                       /* If it was injured, we need to make up a new
1547                          phi result with the actually injured
1548                          version.  */
1549                       if (EPHI_ARG_INJURED (exp_phi, opnd_num))
1550                         {
1551                           /* XXX: Allocate phi result with correct version.  */
1552
1553                         }
1554                       EREF_STMT (def) = newexp;
1555                       process_delayed_rename (ei, def, newexp);
1556                     }
1557                 }
1558               /* If it's not the same version, the defining ephi can't
1559                  be downsafe, and the operand is not really defined by
1560                  anything.  */
1561               else
1562                 {
1563                   EPHI_DOWNSAFE (def) = false;
1564                   EPHI_ARG_DEF (exp_phi, opnd_num) = NULL;
1565                 }
1566             }
1567           else if (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def))
1568             {
1569               bool injured = false;
1570               if (same_e_version_real_occ_phi_opnd (ei, def,
1571                                                     bb_for_stmt (use),
1572                                                     opnd_num, newexp, &injured))
1573                 {
1574                   tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num);
1575                   EPHI_ARG_HAS_REAL_USE (exp_phi, opnd_num) = true;
1576                   /*              EREF_STMT (opnd) = EREF_STMT (def); */
1577                   if (injured || EREF_INJURED (def))
1578                     EREF_INJURED (def) = true;
1579                   if (injured || EREF_INJURED (def))
1580                     EREF_INJURED (opnd) = true;
1581                   else
1582                     EREF_STMT (tmp_use) = EREF_STMT (def);
1583                   if (EUSE_DEF (def) != NULL)
1584                     EPHI_ARG_DEF (exp_phi, opnd_num) = EUSE_DEF (def);
1585                   else
1586                     EPHI_ARG_DEF (exp_phi, opnd_num) = def;
1587                 }
1588               else
1589                 {
1590                   EPHI_ARG_DEF (exp_phi, opnd_num) = NULL;
1591                 }
1592             }
1593         }
1594     }
1595 }
1596
1597 /* For the uninitiated, the algorithm is a modified SSA renaming
1598    algorithm (working on expressions rather than variables) .  We
1599    attempt to determine which expression occurrences have the same
1600    ESSA version (we call it class, for equivalence/redundancy class,
1601    which is what the papers call it.  Open64 calls it e-version), and
1602    which occurrences are actually operands for an EPHI (since this has
1603    to be discovered from the program).
1604
1605    Renaming is done like Open64 does it.  Basically as the paper says,
1606    except that we try to use earlier defined occurrences if they are
1607    available in order to keep the number of saves down.  */
1608
1609 static void
1610 rename_1 (struct expr_info *ei)
1611 {
1612   tree occur;
1613   basic_block phi_bb;
1614   size_t i;
1615   varray_type stack;
1616
1617   VARRAY_GENERIC_PTR_NOGC_INIT (stack, 1, "Stack for renaming");
1618
1619   /* Start by creating and inserting the occurrences in preorder,
1620      dominator tree into a list.  */
1621   create_and_insert_occ_in_preorder_dt_order (ei);
1622
1623   /* Walk the occurrences.  */
1624   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1625     {
1626       occur = VARRAY_TREE (ei->euses_dt_order, i);
1627
1628       /* The current occurrence can't have the same version as
1629          something on the top of the stack unless it is in a basic
1630          block dominated by the basic block of the occurrence on the
1631          top of the stack.  */
1632       while (VARRAY_ACTIVE_SIZE (stack) > 0
1633              && !dominated_by_p (CDI_DOMINATORS,
1634                                  bb_for_stmt (occur),
1635                                  bb_for_stmt (VARRAY_TOP_TREE (stack))))
1636
1637         VARRAY_POP (stack);
1638
1639       /* If the stack is empty, we assign a new version since it isn't
1640          dominated by any other version.  */
1641       if (VARRAY_ACTIVE_SIZE (stack) == 0 || VARRAY_TOP_TREE (stack) == NULL)
1642         {
1643           if (TREE_CODE (occur) == EPHI_NODE)
1644             assign_new_class (occur, &stack, NULL);
1645           else if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur))
1646             assign_new_class (occur, &stack, NULL);
1647         }
1648       else
1649         {
1650           if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur))
1651             {
1652               tree tos = VARRAY_TOP_TREE (stack);
1653
1654               if (TREE_CODE (tos) == EUSE_NODE && !EUSE_PHIOP (tos))
1655                 {
1656                   /* If two real occurrences have the same
1657                      e-version/class, then this occurrence can be
1658                      defined by the prior occurrence (or whatever
1659                      the prior occurrence is defined by, if
1660                      anything).
1661                      Otherwise, we have to assign a new version.
1662                      lvalue occurrences always need a new version,
1663                      since they are definitions.  */
1664                   if (!EUSE_LVAL (occur)
1665                       && same_e_version_real_occ_real_occ (ei, tos, occur))
1666                     {
1667
1668
1669                       tree newdef;
1670                       EREF_CLASS (occur) = EREF_CLASS (tos);
1671                       newdef = EUSE_DEF (tos) != NULL ? EUSE_DEF (tos) : tos;
1672                       EUSE_DEF (occur) = newdef;
1673                     }
1674                   else
1675                     assign_new_class (occur, &stack, NULL);
1676                 }
1677               else if (TREE_CODE (tos) == EPHI_NODE)
1678                 {
1679                   /* Here we have an ephi occurrence at the top of the
1680                      stack, and the current occurrence is a real
1681                      occurrence.  So determine if the real occurrence
1682                      has the same version as the result of the phi.
1683                      If so, then this real occurrence is defined by the
1684                      EPHI at the top of the stack.
1685                      If not, the EPHI isn't downsafe (because something
1686                      must change in between the ephi result and the next
1687                      occurrence), and we need a new version for the real
1688                      occurrence.
1689                      lvalues always need a new version.  */
1690                   if (!EUSE_LVAL (occur)
1691                       && same_e_version_phi_result (ei, tos, EREF_STMT (occur),
1692                                                     occur))
1693                     {
1694                       EREF_CLASS (occur) = EREF_CLASS (tos);
1695                       EUSE_DEF (occur) = tos;
1696                       EREF_STMT (tos) = EREF_STMT (occur);
1697
1698                       VARRAY_PUSH_TREE (stack, occur);
1699                     }
1700                   else
1701                     {
1702                       EPHI_DOWNSAFE (tos) = false;
1703                       assign_new_class (occur, &stack, NULL);
1704                     }
1705                 }
1706             }
1707           /* EPHI occurrences always get new versions.  */
1708           else if (TREE_CODE (occur) == EPHI_NODE)
1709             {
1710               assign_new_class (occur, &stack, NULL);
1711             }
1712           /* EPHI operands are optimistcally assumed to be whatever is
1713              at the top of the stack at the time we hit the ephi
1714              operand occurrence.  The delayed renaming checks this
1715              optimistic assumption for validity.  */
1716           else if (TREE_CODE (occur) == EUSE_NODE && EUSE_PHIOP (occur))
1717             {
1718               basic_block pred_bb = bb_for_stmt (occur);
1719               edge e;
1720               tree tos = VARRAY_TOP_TREE (stack);
1721               for (e = pred_bb->succ; e; e = e->succ_next)
1722                 {
1723                   tree ephi = ephi_at_block (e->dest);
1724                   if (ephi != NULL_TREE)
1725                     {
1726                       int opnum = opnum_of_ephi (ephi, e);
1727
1728                       EPHI_ARG_DELAYED_RENAME (ephi, opnum) = true;
1729                       EPHI_ARG_DEF (ephi, opnum) = tos;
1730                     }
1731                 }
1732             }
1733           /* No EPHI can be downsafe past an exit node.  */
1734           else if (TREE_CODE (occur) == EEXIT_NODE)
1735             {
1736               if (VARRAY_ACTIVE_SIZE (stack) > 0
1737                   && TREE_CODE (VARRAY_TOP_TREE (stack)) == EPHI_NODE)
1738                 EPHI_DOWNSAFE (VARRAY_TOP_TREE (stack)) = false;
1739             }
1740         }
1741     }
1742   if (dump_file && (dump_flags & TDF_DETAILS))
1743     {
1744       size_t i;
1745       fprintf (dump_file, "Occurrences for expression ");
1746       print_generic_expr (dump_file, ei->expr, dump_flags);
1747       fprintf (dump_file, " after Rename 1\n");
1748       for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1749         {
1750           print_generic_expr (dump_file,
1751                               VARRAY_TREE (ei->euses_dt_order, i), 1);
1752           fprintf (dump_file, "\n");
1753         }
1754     }
1755
1756   /* Now process the renames for EPHI's that actually have the result
1757      valid and used.  These will be the EPHI's that have the statement
1758      set above.  */
1759   FOR_EACH_BB (phi_bb)
1760   {
1761     tree ephi = ephi_at_block (phi_bb);
1762     if (ephi != NULL && EREF_STMT (ephi) != NULL)
1763       process_delayed_rename (ei, ephi, EREF_STMT (ephi));
1764   }
1765
1766   /* If we didn't process the delayed rename for an ephi argument,
1767      but thought we needed to, mark the operand as NULL.  Also, if the
1768      operand was defined by an  EPHI, we can mark it not downsafe
1769      because there can't have been a real occurrence (or else we would
1770      have processed a rename for it).  */
1771   FOR_EACH_BB (phi_bb)
1772   {
1773     tree ephi = ephi_at_block (phi_bb);
1774     if (ephi != NULL)
1775       {
1776         int j;
1777         for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1778           {
1779             if (EPHI_ARG_DELAYED_RENAME (ephi, j))
1780               {
1781                 tree def = EPHI_ARG_DEF (ephi, j);
1782                 if (def && TREE_CODE (def) == EPHI_NODE)
1783                   EPHI_DOWNSAFE (def) = false;
1784                 EPHI_ARG_DEF (ephi, j) = NULL;
1785               }
1786           }
1787       }
1788   }
1789   VARRAY_FREE (stack);
1790 }
1791
1792 /* Determine if the EPHI has an argument we could never insert
1793    or extend the lifetime of, such as an argument occurring on
1794    an abnormal edge.  */
1795
1796 static bool
1797 ephi_has_unsafe_arg (tree ephi)
1798 {
1799   int i;
1800   for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
1801     if (EPHI_ARG_EDGE (ephi, i)->flags & EDGE_ABNORMAL)
1802       return true;
1803   return false;
1804 }
1805
1806 /* Reset down safety flags for non-downsafe ephis. Uses depth first
1807    search.  */
1808
1809 static void
1810 reset_down_safe (tree currphi, int opnum)
1811 {
1812   tree ephi;
1813   int i;
1814
1815   if (EPHI_ARG_HAS_REAL_USE (currphi, opnum))
1816     return;
1817   ephi = EPHI_ARG_DEF (currphi, opnum);
1818   if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
1819     return;
1820   if (!EPHI_DOWNSAFE (ephi))
1821     return;
1822   EPHI_DOWNSAFE (ephi) = false;
1823   for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
1824     reset_down_safe (ephi, i);
1825 }
1826
1827 /* Compute down_safety using a depth first search.
1828    This propagates not fully anticipated phi assignments upwards.  */
1829
1830 static void
1831 compute_down_safety (struct expr_info *ei)
1832 {
1833   size_t i;
1834   basic_block bb;
1835   FOR_EACH_BB (bb)
1836   {
1837     tree ephi = ephi_at_block (bb);
1838     if (ephi == NULL_TREE)
1839       continue;
1840     if (ephi_has_unsafe_arg (ephi))
1841       EPHI_DOWNSAFE (ephi) = false;
1842   }
1843   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1844     {
1845       int j;
1846       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1847       if (TREE_CODE (ephi) != EPHI_NODE)
1848         continue;
1849
1850       if (!EPHI_DOWNSAFE (ephi))
1851         for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1852           reset_down_safe (ephi, j);
1853
1854     }
1855 }
1856
1857 /* EPHI use node pool. We allocate ephi_use_node's out of this.  */
1858 static alloc_pool ephi_use_pool;
1859
1860 /* Add a use of DEF to it's use list. The use is at operand OPND_INDX
1861    of USE.  */
1862
1863 static void
1864 add_ephi_use (tree def, tree use, int opnd_indx)
1865 {
1866   struct ephi_use_entry *entry;
1867   if (EPHI_USES (def) == NULL)
1868     VARRAY_GENERIC_PTR_INIT (EPHI_USES (def), 1, "EPHI uses");
1869   entry = (struct ephi_use_entry *) pool_alloc (ephi_use_pool);
1870   entry->phi = use;
1871   entry->opnd_indx = opnd_indx;
1872   VARRAY_PUSH_GENERIC_PTR (EPHI_USES (def), entry);
1873 }
1874
1875 /* Compute def-uses of ephis.  */
1876
1877 static void
1878 compute_du_info (struct expr_info *ei)
1879 {
1880   size_t i;
1881   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1882     {
1883       int j;
1884       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1885       if (TREE_CODE (ephi) != EPHI_NODE)
1886         continue;
1887       for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1888         {
1889           tree def = EPHI_ARG_DEF (ephi, j);
1890           if (def != NULL_TREE)
1891             {
1892               if (TREE_CODE (def) == EPHI_NODE)
1893                 add_ephi_use (def, ephi, j);
1894 #ifdef ENABLE_CHECKING
1895               else
1896                 if (! (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def)))
1897                   abort();
1898 #endif
1899             }
1900         }
1901     }
1902 }
1903
1904 /* STOPS marks what EPHI's/operands stop forward movement. (IE where
1905    we can't insert past).  */
1906
1907 static void
1908 compute_stops (struct expr_info *ei)
1909 {
1910   size_t i;
1911
1912   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1913     {
1914       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1915       int j;
1916
1917       if (TREE_CODE (ephi) != EPHI_NODE)
1918         continue;
1919       if (EPHI_CANT_BE_AVAIL (ephi))
1920         EPHI_STOPS (ephi) = true;
1921       for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1922         if (EPHI_ARG_HAS_REAL_USE (ephi, j))
1923           EPHI_ARG_STOPS (ephi, j) = true;
1924     }
1925   do_ephi_df_search (ei, stops_search);
1926 }
1927
1928 /* Compute will_be_avail property, which consists of cant_be_avail and
1929    stops properties.  */
1930
1931 static void
1932 compute_will_be_avail (struct expr_info *ei)
1933 {
1934   do_ephi_df_search (ei, cant_be_avail_search);
1935   compute_stops (ei);
1936 }
1937
1938 /* Insert the expressions into ei->euses_dt_order in preorder dt order.  */
1939
1940 static void
1941 insert_euse_in_preorder_dt_order (struct expr_info *ei)
1942 {
1943   varray_type new_euses_dt_order;
1944   size_t i;
1945   VARRAY_GENERIC_PTR_NOGC_INIT (new_euses_dt_order, 1, "EUSEs");
1946
1947   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1948     {
1949       tree ref = VARRAY_TREE (ei->euses_dt_order, i);
1950       if (TREE_CODE (ref) == EUSE_NODE || TREE_CODE (ref) == EPHI_NODE)
1951         VARRAY_PUSH_TREE (new_euses_dt_order, ref);
1952     }
1953   VARRAY_FREE (ei->euses_dt_order);
1954   ei->euses_dt_order = new_euses_dt_order;
1955   qsort (ei->euses_dt_order->data.tree,
1956          VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
1957          sizeof (tree),
1958          eref_compare);
1959
1960 }
1961
1962 /* Determine if we can insert operand OPND_INDX of EPHI.  */
1963
1964 static bool
1965 can_insert (tree ephi, int opnd_indx)
1966 {
1967   tree def;
1968
1969   if (EPHI_ARG_DEF (ephi, opnd_indx) == NULL_TREE)
1970     return true;
1971   def = EPHI_ARG_DEF (ephi, opnd_indx);
1972   if (!EPHI_ARG_HAS_REAL_USE (ephi, opnd_indx))
1973     if (TREE_CODE (def) == EPHI_NODE && !(ephi_will_be_avail (def)))
1974       return true;
1975   return false;
1976 }
1977
1978 /* Find the default definition of VAR.
1979    This is incredibly ugly, since we have to walk back through all
1980    the definitions to find the one defined by the empty statement.  */
1981
1982 static tree
1983 get_default_def (tree var, htab_t seen)
1984 {
1985   def_optype defs;
1986   size_t i;
1987   tree defstmt = SSA_NAME_DEF_STMT (var);
1988
1989   if (IS_EMPTY_STMT (defstmt))
1990     return var;
1991   *(htab_find_slot (seen, var, INSERT)) = var;
1992   if (TREE_CODE (defstmt) == PHI_NODE)
1993     {
1994       int j;
1995       for (j = 0; j < PHI_NUM_ARGS (defstmt); j++)
1996         if (htab_find (seen, PHI_ARG_DEF (defstmt, j)) == NULL)
1997           {
1998             if (TREE_CODE (PHI_ARG_DEF (defstmt, j)) == SSA_NAME)
1999               {
2000                 tree temp = get_default_def (PHI_ARG_DEF (defstmt, j), seen);
2001                 if (temp != NULL_TREE)
2002                   return temp;
2003               }
2004           }
2005     }
2006
2007
2008   defs = STMT_DEF_OPS (defstmt);
2009   for (i = 0; i < NUM_DEFS (defs); i++)
2010     {
2011       tree def = DEF_OP (defs, i);
2012       if (SSA_NAME_VAR (def) == SSA_NAME_VAR (var))
2013         {
2014           if (htab_find (seen, def) != NULL)
2015             return NULL;
2016           return get_default_def (def, seen);
2017         }
2018     }
2019
2020   /* We should never get here.  */
2021   abort ();
2022 }
2023
2024 /* Hunt down the right reaching def for VAR, starting with BB.  Ignore
2025    defs in statement IGNORE, and stop if we hit CURRSTMT.  */
2026
2027 static tree
2028 reaching_def (tree var, tree currstmt, basic_block bb, tree ignore)
2029 {
2030   tree curruse = NULL_TREE;
2031   block_stmt_iterator bsi;
2032   basic_block dom;
2033   tree phi;
2034
2035   /* Check phis first.  */
2036   for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
2037     {
2038       if (phi == currstmt)
2039         break;
2040       if (phi == ignore)
2041         continue;
2042       if (names_match_p (var, PHI_RESULT (phi)))
2043         curruse = PHI_RESULT (phi);
2044     }
2045
2046   /* We can't walk BB's backwards right now, so we have to walk *all*
2047      the statements, and choose the last name we find.  */
2048   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2049     {
2050       tree stmt = bsi_stmt (bsi);
2051       tree *def;
2052       def_optype defs;
2053       size_t i;
2054
2055       if (stmt == currstmt)
2056         break;
2057
2058       get_stmt_operands (stmt);
2059       defs = STMT_DEF_OPS (stmt);
2060       for (i = 0; i < NUM_DEFS (defs); i++)
2061         {
2062           def = DEF_OP_PTR (defs, i);
2063           if (def && *def != ignore && names_match_p (var, *def))
2064             {
2065               curruse = *def;
2066               break;
2067             }
2068         }
2069     }
2070   if (curruse != NULL_TREE)
2071     return curruse;
2072   dom = get_immediate_dominator (CDI_DOMINATORS, bb);
2073   if (bb == ENTRY_BLOCK_PTR)
2074     {
2075       htab_t temp;
2076       temp = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
2077       curruse = get_default_def (var, temp);
2078       htab_delete (temp);
2079     }
2080   if (!dom)
2081     return curruse;
2082   return reaching_def (var, currstmt, dom, ignore);
2083 }
2084
2085 /* Insert one ephi operand that doesn't currently exist as a use.  */
2086
2087 static void
2088 insert_one_operand (struct expr_info *ei, tree ephi, int opnd_indx,
2089                     tree x, edge succ, tree **avdefsp)
2090 {
2091   /* FIXME.  pre_insert_on_edge should probably disappear.  */
2092   extern void pre_insert_on_edge (edge, tree);
2093   tree expr;
2094   tree temp = ei->temp;
2095   tree copy;
2096   tree newtemp;
2097   basic_block bb = bb_for_stmt (x);
2098
2099   /* Insert definition of expr at end of BB containing x.  */
2100   copy = TREE_OPERAND (EREF_STMT (ephi), 1);
2101   copy = unshare_expr (copy);
2102   expr = build (MODIFY_EXPR, TREE_TYPE (ei->expr),
2103                 temp, copy);
2104   expr = subst_phis (ei, expr, bb, bb_for_stmt (ephi));
2105   newtemp = make_ssa_name (temp, expr);
2106   TREE_OPERAND (expr, 0) = newtemp;
2107   copy = TREE_OPERAND (expr, 1);
2108   if (dump_file)
2109     {
2110       fprintf (dump_file, "In BB %d, insert save of ", bb->index);
2111       print_generic_expr (dump_file, expr, dump_flags);
2112       fprintf (dump_file, " to ");
2113       print_generic_expr (dump_file, newtemp, dump_flags);
2114       fprintf (dump_file, " after ");
2115       print_generic_stmt (dump_file, last_stmt (bb), dump_flags);
2116       fprintf (dump_file, " (on edge), because of EPHI");
2117       fprintf (dump_file, " in BB %d\n", bb_for_stmt (ephi)->index);
2118     }
2119
2120   /* Do the insertion.  */
2121   /* ??? Previously we did bizarre searching, presumably to get
2122      around bugs elsewhere in the infrastructure.  I'm not sure
2123      if we really should be using pre_insert_on_edge
2124      or just bsi_insert_after at the end of BB.  */
2125   pre_insert_on_edge (succ, expr);
2126
2127   EPHI_ARG_DEF (ephi, opnd_indx)
2128     = create_expr_ref (ei, ei->expr, EUSE_NODE, bb, 0);
2129   EUSE_DEF (x) = EPHI_ARG_DEF (ephi, opnd_indx);
2130   VARRAY_PUSH_TREE (ei->euses_dt_order, EPHI_ARG_DEF (ephi, opnd_indx));
2131   qsort (ei->euses_dt_order->data.tree,
2132          VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
2133          sizeof (tree),
2134          eref_compare);
2135   EREF_TEMP (EUSE_DEF (x)) = newtemp;
2136   EREF_RELOAD (EUSE_DEF (x)) = false;
2137   EREF_SAVE (EUSE_DEF (x)) = false;
2138   EUSE_INSERTED (EUSE_DEF (x)) = true;
2139   EUSE_PHIOP (EUSE_DEF (x)) = false;
2140   EREF_SAVE (x) = false;
2141   EREF_RELOAD (x) = false;
2142   EUSE_INSERTED (x) = true;
2143   EREF_CLASS (x) = class_count++;
2144   EREF_CLASS (EUSE_DEF (x)) = class_count++;
2145   *avdefsp = xrealloc (*avdefsp, sizeof (tree) * (class_count + 1));
2146   (*avdefsp)[class_count - 2] = x;
2147   (*avdefsp)[class_count - 1] = EUSE_DEF (x);
2148   pre_stats.saves++;
2149 }
2150
2151 /* First step of finalization.  Determine which expressions are being
2152    saved and which are being deleted.
2153    This is done as a simple dominator based availability calculation,
2154    using the e-versions/redundancy classes.  */
2155
2156 static bool
2157 finalize_1 (struct expr_info *ei)
2158 {
2159   tree x;
2160   int nx;
2161   bool made_a_reload = false;
2162   size_t i;
2163   tree *avdefs;
2164
2165   avdefs = xcalloc (class_count + 1, sizeof (tree));
2166
2167   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2168     {
2169       x = VARRAY_TREE (ei->euses_dt_order, i);
2170       nx = EREF_CLASS (x);
2171
2172       if (TREE_CODE (x) == EPHI_NODE)
2173         {
2174           if (ephi_will_be_avail (x))
2175             avdefs[nx] = x;
2176         }
2177       else if (TREE_CODE (x) == EUSE_NODE && EUSE_LVAL (x))
2178         {
2179           avdefs[nx] = x;
2180         }
2181       else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x))
2182         {
2183           if (avdefs[nx] == NULL
2184               || !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (x),
2185                                   bb_for_stmt (avdefs[nx])))
2186             {
2187               EREF_RELOAD (x) = false;
2188               avdefs[nx] = x;
2189               EUSE_DEF (x) = NULL;
2190             }
2191           else
2192             {
2193               EREF_RELOAD (x) = true;
2194               made_a_reload = true;
2195               EUSE_DEF (x) = avdefs[nx];
2196 #ifdef ENABLE_CHECKING
2197               if (EREF_CLASS (x) != EREF_CLASS (avdefs[nx]))
2198                 abort ();
2199 #endif
2200             }
2201         }
2202       else
2203         {
2204           edge succ;
2205           basic_block bb = bb_for_stmt (x);
2206           /* For each ephi in the successor blocks.  */
2207           for (succ = bb->succ; succ; succ = succ->succ_next)
2208             {
2209               tree ephi = ephi_at_block (succ->dest);
2210               if (ephi == NULL_TREE)
2211                 continue;
2212               if (ephi_will_be_avail (ephi))
2213                 {
2214                   int opnd_indx = opnum_of_ephi (ephi, succ);
2215 #ifdef ENABLE_CHECKING
2216                   if (EPHI_ARG_PRED (ephi, opnd_indx) != x)
2217                     abort ();
2218 #endif
2219                   if (can_insert (ephi, opnd_indx))
2220                     {
2221                       insert_one_operand (ei, ephi, opnd_indx, x, succ,
2222                                           &avdefs);
2223                     }
2224                   else
2225                     {
2226                       nx = EREF_CLASS (EPHI_ARG_DEF (ephi,opnd_indx));
2227                       EPHI_ARG_DEF (ephi, opnd_indx) = avdefs[nx];
2228                     }
2229                 }
2230             }
2231         }
2232     }
2233   free (avdefs);
2234   return made_a_reload;
2235 }
2236
2237 /* Mark the necessary SAVE bits on X.  */
2238
2239 static void
2240 set_save (struct expr_info *ei, tree X)
2241 {
2242   if (TREE_CODE (X) == EUSE_NODE && !EUSE_PHIOP (X))
2243     EREF_SAVE (X) = true;
2244   else if (TREE_CODE (X) == EPHI_NODE)
2245     {
2246       int curr_phiop;
2247       for (curr_phiop = 0; curr_phiop < EPHI_NUM_ARGS (X); curr_phiop++)
2248         {
2249           tree w = EPHI_ARG_DEF (X, curr_phiop);
2250           if (!EPHI_ARG_PROCESSED2 (X, curr_phiop))
2251             {
2252               EPHI_ARG_PROCESSED2 (X, curr_phiop) = true;
2253               if (w)
2254                 set_save (ei, w);
2255             }
2256         }
2257     }
2258 }
2259
2260 /* DFS Search function: Return true if PHI is can't be available.  */
2261
2262 static bool
2263 cba_search_seen (tree phi)
2264 {
2265   return EPHI_CANT_BE_AVAIL (phi);
2266 }
2267
2268 /* DFS Search function: Mark PHI as can't be available when seen.  */
2269
2270 static void
2271 cba_search_set_seen (tree phi)
2272 {
2273   EPHI_CANT_BE_AVAIL (phi) = true;
2274 }
2275
2276 /* DFS Search function: Return true if PHI should be marked can't be
2277    available due to a NULL operand.  */
2278
2279 static bool
2280 cba_search_start_from (tree phi)
2281 {
2282   if (!EPHI_DOWNSAFE (phi))
2283     {
2284       int i;
2285       for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2286         if (EPHI_ARG_DEF (phi, i) == NULL_TREE
2287             || EPHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
2288           return true;
2289     }
2290   return false;
2291 }
2292
2293 /* DFS Search function: Return true if the used PHI is not downsafe,
2294    unless we have a real use for the operand.  */
2295
2296 static bool
2297 cba_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2298                              int opnd_indx,
2299                              tree use_phi)
2300 {
2301   if (EPHI_ARG_HAS_REAL_USE (use_phi, opnd_indx) &&
2302       !(EPHI_ARG_EDGE (use_phi, opnd_indx)->flags & EDGE_ABNORMAL))
2303     return false;
2304   if (!EPHI_DOWNSAFE (use_phi))
2305     return true;
2306   return false;
2307 }
2308
2309 /* DFS Search function: Return true if this PHI stops forward
2310    movement.  */
2311
2312 static bool
2313 stops_search_seen (tree phi)
2314 {
2315   return EPHI_STOPS (phi);
2316 }
2317
2318 /* DFS Search function:  Mark the PHI as stopping forward movement.  */
2319
2320 static void
2321 stops_search_set_seen (tree phi)
2322 {
2323   EPHI_STOPS (phi) = true;
2324 }
2325
2326 /* DFS Search function:  Note that the used phi argument stops forward
2327    movement.  */
2328
2329 static void
2330 stops_search_reach_from_to (tree def_phi ATTRIBUTE_UNUSED,
2331                             int opnd_indx,
2332                             tree use_phi)
2333 {
2334   EPHI_ARG_STOPS (use_phi, opnd_indx) = true;
2335 }
2336
2337 /* DFS Search function: Return true if the PHI has any arguments
2338    stopping forward movement.  */
2339
2340 static bool
2341 stops_search_start_from (tree phi)
2342 {
2343   int i;
2344   for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2345     if (EPHI_ARG_STOPS (phi, i))
2346       return true;
2347   return false;
2348 }
2349
2350 /* DFS Search function:  Return true if the PHI has any arguments
2351    stopping forward movement.  */
2352
2353 static bool
2354 stops_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2355                                int opnd_indx ATTRIBUTE_UNUSED,
2356                                tree use_phi)
2357 {
2358   return stops_search_start_from (use_phi);
2359 }
2360
2361 /* DFS Search function:  Return true if the replacing occurrence is
2362    known.  */
2363
2364 static bool
2365 repl_search_seen (tree phi)
2366 {
2367   return EPHI_REP_OCCUR_KNOWN (phi);
2368 }
2369
2370 /* DFS Search function:  Set the identical_to field and note the
2371    replacing occurrence is now known.  */
2372
2373 static void
2374 repl_search_set_seen (tree phi)
2375 {
2376   int i;
2377
2378 #ifdef ENABLE_CHECKING
2379   if (!ephi_will_be_avail (phi))
2380     abort ();
2381 #endif
2382
2383   if (EPHI_IDENTICAL_TO (phi) == NULL_TREE)
2384     {
2385       for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2386         {
2387           tree identical_to = occ_identical_to (EPHI_ARG_DEF (phi, i));
2388           if (identical_to != NULL_TREE)
2389             {
2390               if (EPHI_IDENTICAL_TO (phi) == NULL)
2391                 EPHI_IDENTICAL_TO (phi) = identical_to;
2392               if (EPHI_ARG_INJURED (phi, i))
2393                 EPHI_IDENT_INJURED (phi) = true;
2394             }
2395         }
2396     }
2397   EPHI_REP_OCCUR_KNOWN (phi) = true;
2398 }
2399
2400 /* Helper function.  Return true if any argument in the PHI is
2401    injured.  */
2402
2403 static inline bool
2404 any_operand_injured (tree ephi)
2405 {
2406   int i;
2407   for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
2408     if (EPHI_ARG_INJURED (ephi, i))
2409       return true;
2410   return false;
2411
2412 }
2413
2414 /* DFS Search function:  Note the identity of the used phi operand is
2415    the same as it's defining phi operand, if that phi will be
2416    available, and it's known.  */
2417
2418 static void
2419 repl_search_reach_from_to (tree def_phi, int opnd_indx ATTRIBUTE_UNUSED,
2420                            tree use_phi)
2421 {
2422   if (ephi_will_be_avail (use_phi)
2423       && EPHI_IDENTITY (use_phi)
2424       && EPHI_IDENTICAL_TO (use_phi) == NULL_TREE)
2425     {
2426       EPHI_IDENTICAL_TO (use_phi) = EPHI_IDENTICAL_TO (def_phi);
2427
2428       if (EPHI_IDENT_INJURED (def_phi)
2429           || any_operand_injured (use_phi))
2430         EPHI_IDENT_INJURED (use_phi) = true;
2431     }
2432 }
2433
2434 /* DFS Search function:  Return true if the PHI will be available,
2435    it's an identity PHI, and it's arguments are identical to
2436    something.  */
2437
2438 static bool
2439 repl_search_start_from (tree phi)
2440 {
2441   if (ephi_will_be_avail (phi) && EPHI_IDENTITY (phi))
2442     {
2443       int i;
2444       for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2445         if (occ_identical_to (EPHI_ARG_DEF (phi, i)) != NULL_TREE)
2446           return true;
2447     }
2448   return false;
2449 }
2450
2451 /* DFS Search function:  Return true if the using PHI is will be available,
2452    and identity.  */
2453
2454 static bool
2455 repl_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2456                               int opnd_indx ATTRIBUTE_UNUSED,
2457                               tree use_phi)
2458 {
2459   return ephi_will_be_avail (use_phi) && EPHI_IDENTITY (use_phi);
2460 }
2461
2462 /* Mark all will-be-avail ephi's in the dominance frontier of BB as
2463    required.  */
2464
2465 static void
2466 require_phi (struct expr_info *ei, basic_block bb)
2467 {
2468   size_t i;
2469   EXECUTE_IF_SET_IN_BITMAP (pre_dfs[bb->index], 0, i,
2470   {
2471     tree ephi;
2472     ephi = ephi_at_block (BASIC_BLOCK (i));
2473     if (ephi != NULL_TREE
2474         && ephi_will_be_avail (ephi)
2475         && EPHI_IDENTITY (ephi))
2476       {
2477         EPHI_IDENTITY (ephi) = false;
2478         require_phi (ei, BASIC_BLOCK (i));
2479       }
2480   });
2481 }
2482
2483 /* Return the occurrence this occurrence is identical to, if one exists.  */
2484
2485 static tree
2486 occ_identical_to (tree t)
2487 {
2488   if (TREE_CODE (t) == EUSE_NODE && !EUSE_PHIOP (t))
2489     return t;
2490   else if (TREE_CODE (t) == EUSE_NODE && EUSE_PHIOP (t))
2491     return t;
2492   else if (TREE_CODE (t) == EPHI_NODE)
2493     {
2494       if (EPHI_IDENTITY (t) && EPHI_REP_OCCUR_KNOWN (t))
2495         return EPHI_IDENTICAL_TO (t);
2496       else if (!EPHI_IDENTITY (t))
2497         return t;
2498     }
2499   return NULL_TREE;
2500 }
2501
2502 /* Return true if NODE was or is going to be saved.  */
2503 static bool
2504 really_available_def (tree node)
2505 {
2506   if (TREE_CODE (node) == EUSE_NODE
2507       && EUSE_PHIOP (node)
2508       && EUSE_INSERTED (node))
2509     return true;
2510   if (TREE_CODE (node) == EUSE_NODE
2511       && EUSE_DEF (node) == NULL_TREE)
2512     return true;
2513   return false;
2514 }
2515
2516
2517 /* Second part of the finalize step.  Performs save bit setting, and
2518    ESSA minimization.  */
2519
2520 static void
2521 finalize_2 (struct expr_info *ei)
2522 {
2523   size_t i;
2524
2525   insert_euse_in_preorder_dt_order (ei);
2526   /* Note which uses need to be saved to a temporary.  */
2527   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2528     {
2529       tree ref = VARRAY_TREE (ei->euses_dt_order, i);
2530       if (TREE_CODE (ref) == EUSE_NODE
2531           && !EUSE_PHIOP (ref)
2532           && EREF_RELOAD (ref))
2533         {
2534           set_save (ei, EUSE_DEF (ref));
2535         }
2536     }
2537
2538   /* ESSA Minimization.  Determines which phis are identical to other
2539      phis, and not strictly necessary.  */
2540
2541   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2542     {
2543       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2544       if (TREE_CODE (ephi) != EPHI_NODE)
2545         continue;
2546       EPHI_IDENTITY (ephi) = true;
2547       EPHI_IDENTICAL_TO (ephi) = NULL;
2548     }
2549
2550   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2551     {
2552       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2553       if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
2554         continue;
2555       if (ephi_will_be_avail (ephi))
2556         {
2557           int k;
2558           for (k = 0; k < EPHI_NUM_ARGS (ephi); k++)
2559             {
2560               if (EPHI_ARG_INJURED (ephi, k))
2561                 require_phi (ei, EPHI_ARG_EDGE (ephi, k)->src);
2562               else if (EPHI_ARG_DEF (ephi, k)
2563                        && TREE_CODE (EPHI_ARG_DEF (ephi, k)) == EUSE_NODE
2564                        && really_available_def (EPHI_ARG_DEF (ephi, k)))
2565                 require_phi (ei, bb_for_stmt (EPHI_ARG_DEF (ephi, k)));
2566             }
2567         }
2568     }
2569   do_ephi_df_search (ei, replacing_search);
2570 }
2571
2572 /* Perform a DFS on EPHI using the functions in SEARCH.  */
2573
2574 static void
2575 do_ephi_df_search_1 (struct ephi_df_search search, tree ephi)
2576 {
2577   varray_type uses;
2578   size_t i;
2579   search.set_seen (ephi);
2580
2581   uses = EPHI_USES (ephi);
2582   if (!uses)
2583     return;
2584   for (i = 0; i < VARRAY_ACTIVE_SIZE (uses); i++)
2585     {
2586       struct ephi_use_entry *use = VARRAY_GENERIC_PTR (uses, i);
2587       if (search.reach_from_to)
2588         search.reach_from_to (ephi, use->opnd_indx, use->phi);
2589       if (!search.seen (use->phi) &&
2590           search.continue_from_to (ephi, use->opnd_indx, use->phi))
2591         {
2592           do_ephi_df_search_1 (search, use->phi);
2593         }
2594     }
2595 }
2596
2597 /* Perform a DFS on the EPHI's, using the functions in SEARCH.  */
2598
2599 static void
2600 do_ephi_df_search (struct expr_info *ei, struct ephi_df_search search)
2601 {
2602   size_t i;
2603   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2604     {
2605       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2606       if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
2607         continue;
2608       if (!search.seen (ephi)
2609           && search.start_from (ephi))
2610         do_ephi_df_search_1 (search, ephi);
2611     }
2612 }
2613
2614 #if 0
2615 /* Calculate the increment necessary due to EXPR for the temporary.  */
2616 static tree
2617 calculate_increment (struct expr_info *ei, tree expr)
2618 {
2619   tree incr;
2620
2621   /*XXX: Currently assume it's like a = a + 5, thus, this will give us the 5.
2622    */
2623   incr = TREE_OPERAND (TREE_OPERAND (expr, 1), 1);
2624   if (TREE_CODE (incr) != INTEGER_CST)
2625     abort();
2626   if (TREE_CODE (ei->expr) == MULT_EXPR)
2627     incr = fold (build (MULT_EXPR, TREE_TYPE (ei->expr),
2628                         incr, TREE_OPERAND (ei->expr, 1)));
2629 #if DEBUGGING_STRRED
2630   if (dump_file)
2631     {
2632       fprintf (dump_file, "Increment calculated to be: ");
2633       print_generic_expr (dump_file, incr, 0);
2634       fprintf (dump_file, "\n");
2635     }
2636 #endif
2637   return incr;
2638 }
2639 #endif
2640
2641
2642 /* Perform an insertion of EXPR before/after USE, depending on the
2643    value of BEFORE.  */
2644
2645 static tree
2646 do_proper_save (tree use, tree expr, int before)
2647 {
2648   basic_block bb = bb_for_stmt (use);
2649   block_stmt_iterator bsi;
2650
2651   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2652     {
2653       if (bsi_stmt (bsi) == use)
2654         {
2655           if (before)
2656             bsi_insert_before (&bsi, expr, BSI_SAME_STMT);
2657           else
2658             bsi_insert_after (&bsi, expr, BSI_SAME_STMT);
2659           return use;
2660         }
2661     }
2662   abort ();
2663 }
2664
2665 /* Get the temporary for ESSA node USE.
2666    Takes into account minimized ESSA.  */
2667 static tree
2668 get_temp (tree use)
2669 {
2670   tree newtemp;
2671   if (TREE_CODE (use) == EPHI_NODE && EPHI_IDENTITY (use))
2672     {
2673       tree newuse = use;
2674       while  (TREE_CODE (newuse) == EPHI_NODE
2675               && EPHI_IDENTITY (newuse))
2676         {
2677 #ifdef ENABLE_CHECKING
2678           if (!EPHI_IDENTICAL_TO (newuse))
2679             abort ();
2680 #endif
2681           newuse = EPHI_IDENTICAL_TO (newuse);
2682           if (TREE_CODE (newuse) != EPHI_NODE)
2683             break;
2684         }
2685       if (TREE_CODE (EREF_TEMP (newuse)) == PHI_NODE)
2686         newtemp = PHI_RESULT (EREF_TEMP (newuse));
2687       else
2688         newtemp = EREF_TEMP (newuse);
2689     }
2690   else
2691     {
2692       if (TREE_CODE (EREF_TEMP (use)) == PHI_NODE)
2693         newtemp = PHI_RESULT (EREF_TEMP (use));
2694       else
2695         newtemp = EREF_TEMP (use);
2696     }
2697   return newtemp;
2698 }
2699
2700 /* Return the side of the statement that contains an SSA name.  */
2701
2702 static tree
2703 pick_ssa_name (tree stmt)
2704 {
2705   if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
2706     return TREE_OPERAND (stmt, 0);
2707   else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
2708     return TREE_OPERAND (stmt, 1);
2709   else
2710     abort ();
2711 }
2712
2713 /* Code motion step of SSAPRE.  Take the save bits, and reload bits,
2714    and perform the saves and reloads.  Also insert new phis where
2715    necessary.  */
2716
2717 static void
2718 code_motion (struct expr_info *ei)
2719 {
2720   tree use;
2721   tree newtemp;
2722   size_t euse_iter;
2723   tree temp = ei->temp;
2724   basic_block bb;
2725
2726   /* First, add the phi node temporaries so the reaching defs are
2727      always right.  */
2728   for (euse_iter = 0;
2729        euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2730        euse_iter++)
2731     {
2732
2733       use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2734       if (TREE_CODE (use) != EPHI_NODE)
2735         continue;
2736       if (ephi_will_be_avail (use) && !EPHI_IDENTITY (use))
2737         {
2738           bb = bb_for_stmt (use);
2739           /* Add the new PHI node to the list of PHI nodes for block BB.  */
2740           bb_ann (bb)->phi_nodes = chainon (phi_nodes (bb), EREF_TEMP (use));
2741         }
2742       else if (EPHI_IDENTITY (use))
2743         {
2744           if (dump_file && (dump_flags & TDF_DETAILS))
2745             {
2746               fprintf (dump_file, "Pointless EPHI in block %d\n",
2747                        bb_for_stmt (use)->index);
2748             }
2749         }
2750     }
2751   /* Now do the actual saves and reloads, plus repairs.  */
2752   for (euse_iter = 0;
2753        euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2754        euse_iter++)
2755     {
2756       use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2757 #ifdef ENABLE_CHECKING
2758       if (TREE_CODE (use) == EUSE_NODE && EUSE_PHIOP (use)
2759           && (EREF_RELOAD (use) || EREF_SAVE (use)))
2760         abort ();
2761 #endif
2762       if (EREF_SAVE (use) && !EUSE_INSERTED (use))
2763         {
2764           tree newexpr;
2765           tree use_stmt;
2766           tree copy;
2767           basic_block usebb = bb_for_stmt (use);
2768           use_stmt = EREF_STMT (use);
2769
2770           copy = TREE_OPERAND (use_stmt, 1);
2771           copy = unshare_expr (copy);
2772           newexpr = build (MODIFY_EXPR, TREE_TYPE (temp), temp, copy);
2773           newtemp = make_ssa_name (temp, newexpr);
2774           EREF_TEMP (use) = newtemp;
2775           TREE_OPERAND (newexpr, 0) = newtemp;
2776           TREE_OPERAND (use_stmt, 1) = newtemp;
2777
2778           if (dump_file)
2779             {
2780               fprintf (dump_file, "In BB %d, insert save of ",
2781                        usebb->index);
2782               print_generic_expr (dump_file, copy, dump_flags);
2783               fprintf (dump_file, " to ");
2784               print_generic_expr (dump_file, newtemp, dump_flags);
2785               fprintf (dump_file, " before statement ");
2786               print_generic_expr (dump_file, use_stmt, dump_flags);
2787               fprintf (dump_file, "\n");
2788               if (EXPR_HAS_LOCATION (use_stmt))
2789                 fprintf (dump_file, " on line %d\n",
2790                          EXPR_LINENO (use_stmt));
2791             }
2792           modify_stmt (newexpr);
2793           modify_stmt (use_stmt);
2794           set_bb_for_stmt (newexpr, usebb);
2795           EREF_STMT (use) = do_proper_save (use_stmt, newexpr, true);
2796           pre_stats.saves++;
2797         }
2798       else if (EREF_RELOAD (use))
2799         {
2800           tree use_stmt;
2801           tree newtemp;
2802
2803           use_stmt = EREF_STMT (use);
2804           bb = bb_for_stmt (use_stmt);
2805
2806           newtemp = get_temp (EUSE_DEF (use));
2807           if (!newtemp)
2808             abort ();
2809           if (dump_file)
2810             {
2811               fprintf (dump_file, "In BB %d, insert reload of ",
2812                        bb->index);
2813               print_generic_expr (dump_file,
2814                                   TREE_OPERAND (use_stmt, 1), 0);
2815               fprintf (dump_file, " from ");
2816               print_generic_expr (dump_file, newtemp, dump_flags);
2817               fprintf (dump_file, " in statement ");
2818               print_generic_stmt (dump_file, use_stmt, dump_flags);
2819               fprintf (dump_file, "\n");
2820               if (EXPR_HAS_LOCATION (use_stmt))
2821                 fprintf (dump_file, " on line %d\n",
2822                          EXPR_LINENO (use_stmt));
2823             }
2824           TREE_OPERAND (use_stmt, 1) = newtemp;
2825           EREF_TEMP (use) = newtemp;
2826           modify_stmt (use_stmt);
2827           pre_stats.reloads++;
2828         }
2829     }
2830
2831   /* Now do the phi nodes.  */
2832   for (euse_iter = 0;
2833        euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2834        euse_iter++)
2835     {
2836       use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2837       if (TREE_CODE (use) == EPHI_NODE
2838           && ephi_will_be_avail (use)
2839           && !EPHI_IDENTITY (use))
2840         {
2841           int i;
2842           tree argdef;
2843           bb = bb_for_stmt (use);
2844           if (dump_file)
2845             {
2846               fprintf (dump_file,
2847                        "In BB %d, insert PHI to replace EPHI\n", bb->index);
2848             }
2849           newtemp = EREF_TEMP (use);
2850           for (i = 0; i < EPHI_NUM_ARGS (use); i++)
2851             {
2852               tree rdef;
2853               argdef = EPHI_ARG_DEF (use, i);
2854               if (argdef == use)
2855                 rdef = get_temp (use);
2856               else if (EREF_RELOAD (argdef) || EREF_SAVE (argdef))
2857                 rdef = get_temp (argdef);
2858               else if (TREE_CODE (argdef) == EPHI_NODE)
2859                 rdef = get_temp (argdef);
2860               else if (argdef
2861                   && EPHI_ARG_HAS_REAL_USE (use, i)
2862                   && EREF_STMT (argdef)
2863                   && !EPHI_ARG_INJURED (use, i))
2864                 rdef = pick_ssa_name (EREF_STMT (argdef));
2865               else
2866                 abort ();
2867
2868               if (!rdef)
2869                 abort();
2870               add_phi_arg (&newtemp, rdef, EPHI_ARG_EDGE (use, i));
2871             }
2872
2873           /* Associate BB to the PHI node.  */
2874           set_bb_for_stmt (EREF_TEMP (use), bb);
2875           pre_stats.newphis++;
2876
2877         }
2878     }
2879 }
2880
2881 /* Compute the iterated dominance frontier of a statement.  */
2882
2883 static bitmap
2884 compute_idfs (bitmap * dfs, tree stmt)
2885 {
2886   fibheap_t worklist;
2887   sbitmap inworklist, done;
2888   bitmap idf;
2889   size_t i;
2890   basic_block block;
2891
2892   block = bb_for_stmt (stmt);
2893   if (idfs_cache[block->index] != NULL)
2894     return idfs_cache[block->index];
2895
2896   inworklist = sbitmap_alloc (last_basic_block);
2897   done = sbitmap_alloc (last_basic_block);
2898   worklist = fibheap_new ();
2899   sbitmap_zero (inworklist);
2900   sbitmap_zero (done);
2901
2902   idf = BITMAP_XMALLOC ();
2903   bitmap_zero (idf);
2904
2905   block = bb_for_stmt (stmt);
2906   fibheap_insert (worklist, block->index, (void *)(size_t)block->index);
2907   SET_BIT (inworklist, block->index);
2908
2909   while (!fibheap_empty (worklist))
2910     {
2911       int a = (size_t) fibheap_extract_min (worklist);
2912       if (TEST_BIT (done, a))
2913         continue;
2914       SET_BIT (done, a);
2915       if (idfs_cache[a])
2916         {
2917           bitmap_a_or_b (idf, idf, idfs_cache[a]);
2918           EXECUTE_IF_SET_IN_BITMAP (idfs_cache[a], 0, i,
2919           {
2920             SET_BIT (inworklist, i);
2921             SET_BIT (done, i);
2922           });
2923         }
2924       else
2925         {
2926           bitmap_a_or_b (idf, idf, dfs[a]);
2927           EXECUTE_IF_SET_IN_BITMAP (dfs[a], 0, i,
2928           {
2929             if (!TEST_BIT (inworklist, i))
2930               {
2931                 SET_BIT (inworklist, i);
2932                 fibheap_insert (worklist, i, (void *)i);
2933               }
2934           });
2935         }
2936
2937     }
2938   fibheap_delete (worklist);
2939   sbitmap_free (inworklist);
2940   sbitmap_free (done);
2941   idfs_cache[block->index] = idf;
2942   return idf;
2943
2944 }
2945
2946 /* Return true if EXPR is a strength reduction candidate.  */
2947 static bool
2948 is_strred_cand (const tree expr ATTRIBUTE_UNUSED)
2949 {
2950 #if 0
2951         if (TREE_CODE (TREE_OPERAND (expr, 1)) != MULT_EXPR
2952       && TREE_CODE (TREE_OPERAND (expr, 1)) != MINUS_EXPR
2953       && TREE_CODE (TREE_OPERAND (expr, 1)) != NEGATE_EXPR
2954       && TREE_CODE (TREE_OPERAND (expr, 1)) != PLUS_EXPR)
2955     return false;
2956   return true;
2957 #endif
2958   return false;
2959 }
2960
2961
2962
2963 /* Determine if two expressions are lexically equivalent.  */
2964
2965 static inline bool
2966 expr_lexically_eq (const tree v1, const tree v2)
2967 {
2968   if (TREE_CODE_CLASS (TREE_CODE (v1)) != TREE_CODE_CLASS (TREE_CODE (v2)))
2969     return false;
2970   if (TREE_CODE (v1) != TREE_CODE (v2))
2971     return false;
2972   switch (TREE_CODE_CLASS (TREE_CODE (v1)))
2973     {
2974     case 'r':
2975     case '1':
2976       return names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0));
2977     case 'x':
2978     case 'd':
2979       return names_match_p (v1, v2);
2980     case '2':
2981       {
2982         bool match;
2983         match = names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0));
2984         if (!match)
2985           return false;
2986         match = names_match_p (TREE_OPERAND (v1, 1), TREE_OPERAND (v2, 1));
2987         if (!match)
2988           return false;
2989         return true;
2990       }
2991     default:
2992       return false;
2993     }
2994
2995 }
2996
2997 /* Free an expression info structure.  */
2998
2999 static void
3000 free_expr_info (struct expr_info *v1)
3001 {
3002   struct expr_info *e1 = (struct expr_info *)v1;
3003   VARRAY_FREE (e1->occurs);
3004   VARRAY_FREE (e1->kills);
3005   VARRAY_FREE (e1->lefts);
3006   VARRAY_FREE (e1->reals);
3007   VARRAY_FREE (e1->euses_dt_order);
3008 }
3009
3010 /* Process left occurrences and kills due to EXPR.
3011    A left occurrence occurs wherever a variable in an expression we
3012    are PRE'ing is stored to directly in a def, or indirectly because
3013    of a VDEF of an expression that we VUSE.  */
3014
3015 static void
3016 process_left_occs_and_kills (varray_type bexprs, tree expr)
3017 {
3018   size_t i, j, k;
3019
3020   v_may_def_optype v_may_defs;
3021   v_must_def_optype v_must_defs;
3022   vuse_optype vuses;
3023   def_optype defs;
3024   defs = STMT_DEF_OPS (expr);
3025   v_may_defs = STMT_V_MAY_DEF_OPS (expr);
3026   v_must_defs = STMT_V_MUST_DEF_OPS (expr);
3027   if (NUM_DEFS (defs) == 0
3028       && NUM_V_MAY_DEFS (v_may_defs) == 0
3029       && NUM_V_MUST_DEFS (v_must_defs) == 0)
3030     return;
3031
3032   for (j = 0; j < VARRAY_ACTIVE_SIZE (bexprs); j++)
3033     {
3034       struct expr_info *ei = VARRAY_GENERIC_PTR (bexprs, j);
3035       tree vuse_name;
3036       tree random_occur;
3037       stmt_ann_t ann;
3038
3039       if (!ei->loadpre_cand)
3040         continue;
3041
3042       /* If we define the variable itself (IE a in *a, or a in a),
3043          it's a left occurrence.  */
3044       for (i = 0; i < NUM_DEFS (defs); i++)
3045         {
3046           if (names_match_p (DEF_OP (defs, i), ei->expr))
3047             {
3048               if (TREE_CODE (expr) == ASM_EXPR)
3049                 {
3050                   ei->loadpre_cand = false;
3051                   continue;
3052                 }
3053               VARRAY_PUSH_TREE (ei->lefts, expr);
3054               VARRAY_PUSH_TREE (ei->occurs, NULL);
3055               VARRAY_PUSH_TREE (ei->kills, NULL);
3056             }
3057         }
3058
3059       /* If we virtually define the variable itself,
3060          it's a left occurrence.  */
3061       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
3062         {
3063           if (names_match_p (V_MUST_DEF_OP (v_must_defs, i), ei->expr))
3064             {
3065               if (TREE_CODE (expr) == ASM_EXPR)
3066                 {
3067                   ei->loadpre_cand = false;
3068                   continue;
3069                 }
3070               VARRAY_PUSH_TREE (ei->lefts, expr);
3071               VARRAY_PUSH_TREE (ei->occurs, NULL);
3072               VARRAY_PUSH_TREE (ei->kills, NULL);
3073             }
3074         }
3075
3076       /* If we V_MAY_DEF the VUSE of the expression, it's also a left
3077          occurrence.  */
3078       random_occur = VARRAY_TREE (ei->occurs, 0);
3079       ann = stmt_ann (random_occur);
3080       vuses = VUSE_OPS (ann);
3081       if (NUM_V_MAY_DEFS (v_may_defs) != 0)
3082         {
3083           for (k = 0; k < NUM_VUSES (vuses); k++)
3084             {
3085               vuse_name = VUSE_OP (vuses, k);
3086               for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
3087                 {
3088                   if (names_match_p (V_MAY_DEF_OP (v_may_defs, i), vuse_name))
3089                     {
3090                       VARRAY_PUSH_TREE (ei->lefts, expr);
3091                       VARRAY_PUSH_TREE (ei->occurs, NULL);
3092                       VARRAY_PUSH_TREE (ei->kills, NULL);
3093                     }
3094                 }
3095             }
3096         }
3097     }
3098 }
3099
3100 /* Perform SSAPRE on an expression.  */
3101
3102 static int
3103 pre_expression (struct expr_info *slot, void *data, bitmap vars_to_rename)
3104 {
3105   struct expr_info *ei = (struct expr_info *) slot;
3106   basic_block bb;
3107
3108   class_count = 0;
3109   eref_id_counter = 0;
3110
3111   /* If we don't have two occurrences along any dominated path, and
3112      it's not load PRE, this is a waste of time.  */
3113
3114   if (VARRAY_ACTIVE_SIZE (ei->reals) < 2)
3115     return 1;
3116
3117   memset (&pre_stats, 0, sizeof (struct pre_stats_d));
3118
3119   ei->temp = create_tmp_var (TREE_TYPE (ei->expr), "pretmp");
3120   add_referenced_tmp_var (ei->temp);
3121
3122   bitmap_clear (created_phi_preds);
3123   ephi_pindex_htab = htab_create (500, ephi_pindex_hash, ephi_pindex_eq, free);
3124   phi_pred_cache = xcalloc (last_basic_block, sizeof (tree));
3125   n_phi_preds = last_basic_block;
3126
3127   if (!expr_phi_insertion ((bitmap *)data, ei))
3128     goto cleanup;
3129   rename_1 (ei);
3130   if (dump_file && (dump_flags & TDF_DETAILS))
3131     {
3132       size_t i;
3133       fprintf (dump_file, "Occurrences for expression ");
3134       print_generic_expr (dump_file, ei->expr, dump_flags);
3135       fprintf (dump_file, " after Rename 2\n");
3136       for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
3137         {
3138           print_generic_expr (dump_file,
3139                               VARRAY_TREE (ei->euses_dt_order, i), 1);
3140           fprintf (dump_file, "\n");
3141         }
3142     }
3143   compute_down_safety (ei);
3144   compute_du_info (ei);
3145   compute_will_be_avail (ei);
3146
3147   if (dump_file && (dump_flags & TDF_DETAILS))
3148     {
3149       fprintf (dump_file, "EPHI's for expression ");
3150       print_generic_expr (dump_file, ei->expr, dump_flags);
3151       fprintf (dump_file,
3152                " after down safety and will_be_avail computation\n");
3153       FOR_EACH_BB (bb)
3154       {
3155         tree ephi = ephi_at_block (bb);
3156         if (ephi != NULL)
3157           {
3158             print_generic_expr (dump_file, ephi, 1);
3159             fprintf (dump_file, "\n");
3160           }
3161       }
3162     }
3163
3164   if (finalize_1 (ei))
3165     {
3166       finalize_2 (ei);
3167       code_motion (ei);
3168       if (ei->loadpre_cand)
3169         bitmap_set_bit (vars_to_rename, var_ann (ei->temp)->uid);
3170     }
3171
3172   clear_all_eref_arrays ();
3173   if (dump_file)
3174     if (dump_flags & TDF_STATS)
3175       {
3176         fprintf (dump_file, "PRE stats:\n");
3177         fprintf (dump_file, "Reloads:%d\n", pre_stats.reloads);
3178         fprintf (dump_file, "Saves:%d\n", pre_stats.saves);
3179         fprintf (dump_file, "Repairs:%d\n", pre_stats.repairs);
3180         fprintf (dump_file, "New phis:%d\n", pre_stats.newphis);
3181         fprintf (dump_file, "EPHI memory allocated:%d\n",
3182                  pre_stats.ephi_allocated);
3183         fprintf (dump_file, "EREF memory allocated:%d\n",
3184                  pre_stats.eref_allocated);
3185         fprintf (dump_file, "Expressions generated for rename2:%d\n",
3186                  pre_stats.exprs_generated);
3187       }
3188  cleanup:
3189   free (phi_pred_cache);
3190   if (ephi_pindex_htab)
3191     {
3192       htab_delete (ephi_pindex_htab);
3193       ephi_pindex_htab = NULL;
3194     }
3195
3196
3197   return 0;
3198 }
3199
3200
3201 /* Step 1 - Collect the expressions to perform PRE on.  */
3202
3203 static void
3204 collect_expressions (basic_block block, varray_type *bexprsp)
3205 {
3206   size_t k;
3207   block_stmt_iterator j;
3208   basic_block son;
3209
3210   varray_type bexprs = *bexprsp;
3211
3212   for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
3213     {
3214       tree stmt = bsi_stmt (j);
3215       tree expr = stmt;
3216       tree orig_expr = expr;
3217       stmt_ann_t ann;
3218       struct expr_info *slot = NULL;
3219
3220       get_stmt_operands (expr);
3221       ann = stmt_ann (expr);
3222
3223       if (NUM_USES (USE_OPS (ann)) == 0)
3224         {
3225           process_left_occs_and_kills (bexprs, expr);
3226           continue;
3227         }
3228
3229       if (TREE_CODE (expr) == MODIFY_EXPR)
3230         expr = TREE_OPERAND (expr, 1);
3231       if ((TREE_CODE_CLASS (TREE_CODE (expr)) == '2'
3232            || TREE_CODE_CLASS (TREE_CODE (expr)) == '<'
3233            /*|| TREE_CODE_CLASS (TREE_CODE (expr)) == '1'*/
3234            || TREE_CODE (expr) == SSA_NAME
3235            || TREE_CODE (expr) == INDIRECT_REF)
3236           && !ann->makes_aliased_stores
3237           && !ann->has_volatile_ops)
3238         {
3239           bool is_scalar = true;
3240           tree origop0 = TREE_OPERAND (orig_expr, 0);
3241
3242           if (AGGREGATE_TYPE_P (TREE_TYPE (origop0))
3243               || TREE_CODE (TREE_TYPE (origop0)) == COMPLEX_TYPE)
3244             is_scalar = false;
3245
3246           if (is_scalar
3247               && (TREE_CODE (expr) == SSA_NAME
3248                   || (TREE_CODE (expr) == INDIRECT_REF
3249                       && !DECL_P (TREE_OPERAND (expr, 0)))
3250                   ||(!DECL_P (TREE_OPERAND (expr, 0))
3251                      && (!TREE_OPERAND (expr, 1)
3252                          || !DECL_P (TREE_OPERAND (expr, 1))))))
3253             {
3254               for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++)
3255                 {
3256                   slot = VARRAY_GENERIC_PTR (bexprs, k);
3257                   if (expr_lexically_eq (slot->expr, expr))
3258                     break;
3259                 }
3260               if (k >= VARRAY_ACTIVE_SIZE (bexprs))
3261                 slot = NULL;
3262               if (slot)
3263                 {
3264                   VARRAY_PUSH_TREE (slot->occurs, orig_expr);
3265                   VARRAY_PUSH_TREE (slot->kills, NULL);
3266                   VARRAY_PUSH_TREE (slot->lefts, NULL);
3267                   VARRAY_PUSH_TREE (slot->reals, stmt);
3268                   slot->strred_cand &= is_strred_cand (orig_expr);
3269                 }
3270               else
3271                 {
3272                   slot = ggc_alloc (sizeof (struct expr_info));
3273                   slot->expr = expr;
3274                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->occurs, 1, "Occurrence");
3275                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->kills, 1, "Kills");
3276                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->lefts, 1, "Left occurrences");
3277                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->reals, 1, "Real occurrences");
3278                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->euses_dt_order, 1, "EUSEs");
3279
3280                   VARRAY_PUSH_TREE (slot->occurs, orig_expr);
3281                   VARRAY_PUSH_TREE (slot->kills, NULL);
3282                   VARRAY_PUSH_TREE (slot->lefts, NULL);
3283                   VARRAY_PUSH_TREE (slot->reals, stmt);
3284                   VARRAY_PUSH_GENERIC_PTR (bexprs, slot);
3285                   slot->strred_cand = is_strred_cand (orig_expr);
3286                   slot->loadpre_cand = false;
3287                   if (TREE_CODE (expr) == SSA_NAME
3288                       || TREE_CODE (expr) == INDIRECT_REF)
3289                     slot->loadpre_cand = true;
3290                 }
3291             }
3292         }
3293       process_left_occs_and_kills (bexprs, orig_expr);
3294     }
3295   *bexprsp = bexprs;
3296
3297   for (son = first_dom_son (CDI_DOMINATORS, block);
3298        son;
3299        son = next_dom_son (CDI_DOMINATORS, son))
3300     collect_expressions (son, bexprsp);
3301 }
3302
3303 /* Main entry point to the SSA-PRE pass.
3304
3305    PHASE indicates which dump file from the DUMP_FILES array to use when
3306    dumping debugging information.  */
3307
3308 static void
3309 execute_pre (void)
3310 {
3311   int currbbs;
3312   varray_type bexprs;
3313   size_t k;
3314   int i;
3315
3316   if (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next)
3317     if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL))
3318       split_edge (ENTRY_BLOCK_PTR->succ);
3319
3320   euse_node_pool = create_alloc_pool ("EUSE node pool",
3321                                       sizeof (struct tree_euse_node), 30);
3322   eref_node_pool = create_alloc_pool ("EREF node pool",
3323                                       sizeof (struct tree_eref_common), 30);
3324   ephi_use_pool = create_alloc_pool ("EPHI use node pool",
3325               sizeof (struct ephi_use_entry), 30);
3326   VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs");
3327   /* Compute immediate dominators.  */
3328   calculate_dominance_info (CDI_DOMINATORS);
3329
3330   /* DCE screws the dom_children up, without bothering to fix it. So fix it.  */
3331   currbbs = n_basic_blocks;
3332   dfn = xcalloc (last_basic_block + 1, sizeof (int));
3333   build_dfn_array (ENTRY_BLOCK_PTR, 0);
3334
3335   /* Initialize IDFS cache.  */
3336   idfs_cache = xcalloc (currbbs, sizeof (bitmap));
3337
3338   /* Compute dominance frontiers.  */
3339   pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs);
3340   for (i = 0; i < currbbs; i++)
3341      pre_dfs[i] = BITMAP_XMALLOC ();
3342   compute_dominance_frontiers (pre_dfs);
3343
3344   created_phi_preds = BITMAP_XMALLOC ();
3345
3346   collect_expressions (ENTRY_BLOCK_PTR, &bexprs);
3347
3348   ggc_push_context ();
3349
3350   for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++)
3351     {
3352       pre_expression (VARRAY_GENERIC_PTR (bexprs, k), pre_dfs, vars_to_rename);
3353       free_alloc_pool (euse_node_pool);
3354       free_alloc_pool (eref_node_pool);
3355       free_alloc_pool (ephi_use_pool);
3356       euse_node_pool = create_alloc_pool ("EUSE node pool",
3357                                           sizeof (struct tree_euse_node), 30);
3358       eref_node_pool = create_alloc_pool ("EREF node pool",
3359                                           sizeof (struct tree_eref_common), 30);
3360       ephi_use_pool = create_alloc_pool ("EPHI use node pool",
3361             sizeof (struct ephi_use_entry), 30);
3362       free_expr_info (VARRAY_GENERIC_PTR (bexprs, k));
3363 #ifdef ENABLE_CHECKING
3364       if (pre_stats.ephis_current != 0)
3365         abort ();
3366 #endif
3367       ggc_collect ();
3368     }
3369
3370   ggc_pop_context ();
3371
3372   /* Clean up after PRE.  */
3373   memset (&pre_stats, 0, sizeof (struct pre_stats_d));
3374   free_alloc_pool (euse_node_pool);
3375   free_alloc_pool (eref_node_pool);
3376   free_alloc_pool (ephi_use_pool);
3377   VARRAY_CLEAR (bexprs);
3378   for (i = 0; i < currbbs; i++)
3379     BITMAP_XFREE (pre_dfs[i]);
3380   free (pre_dfs);
3381   BITMAP_XFREE (created_phi_preds);
3382   for (i = 0; i < currbbs; i++)
3383     if (idfs_cache[i] != NULL)
3384       BITMAP_XFREE (idfs_cache[i]);
3385
3386   free (dfn);
3387   free (idfs_cache);
3388 }
3389
3390 static bool
3391 gate_pre (void)
3392 {
3393   return flag_tree_pre != 0;
3394 }
3395
3396 struct tree_opt_pass pass_pre =
3397 {
3398   "pre",                                /* name */
3399   gate_pre,                             /* gate */
3400   execute_pre,                          /* execute */
3401   NULL,                                 /* sub */
3402   NULL,                                 /* next */
3403   0,                                    /* static_pass_number */
3404   TV_TREE_PRE,                          /* tv_id */
3405   PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
3406   0,                                    /* properties_provided */
3407   0,                                    /* properties_destroyed */
3408   0,                                    /* todo_flags_start */
3409   TODO_dump_func | TODO_rename_vars
3410     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
3411 };