LCOV - code coverage report
Current view: top level - gcc - tree-ssa-pre.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 93.9 % 2138 2007
Test Date: 2026-11-14 16:39:50 Functions: 92.4 % 66 61
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
       2              :    Copyright (C) 2001-2026 Free Software Foundation, Inc.
       3              :    Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
       4              :    <stevenb@suse.de>
       5              : 
       6              : This file is part of GCC.
       7              : 
       8              : GCC is free software; you can redistribute it and/or modify
       9              : it under the terms of the GNU General Public License as published by
      10              : the Free Software Foundation; either version 3, or (at your option)
      11              : any later version.
      12              : 
      13              : GCC is distributed in the hope that it will be useful,
      14              : but WITHOUT ANY WARRANTY; without even the implied warranty of
      15              : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      16              : GNU General Public License for more details.
      17              : 
      18              : You should have received a copy of the GNU General Public License
      19              : along with GCC; see the file COPYING3.  If not see
      20              : <http://www.gnu.org/licenses/>.  */
      21              : 
      22              : #include "config.h"
      23              : #include "system.h"
      24              : #include "coretypes.h"
      25              : #include "backend.h"
      26              : #include "rtl.h"
      27              : #include "tree.h"
      28              : #include "gimple.h"
      29              : #include "predict.h"
      30              : #include "alloc-pool.h"
      31              : #include "tree-pass.h"
      32              : #include "ssa.h"
      33              : #include "cgraph.h"
      34              : #include "gimple-pretty-print.h"
      35              : #include "fold-const.h"
      36              : #include "cfganal.h"
      37              : #include "gimple-iterator.h"
      38              : #include "gimple-fold.h"
      39              : #include "tree-eh.h"
      40              : #include "tree-cfg.h"
      41              : #include "tree-into-ssa.h"
      42              : #include "tree-dfa.h"
      43              : #include "tree-ssa.h"
      44              : #include "cfgloop.h"
      45              : #include "tree-ssa-sccvn.h"
      46              : #include "tree-scalar-evolution.h"
      47              : #include "dbgcnt.h"
      48              : #include "domwalk.h"
      49              : #include "tree-ssa-propagate.h"
      50              : #include "tree-ssa-dce.h"
      51              : #include "tree-cfgcleanup.h"
      52              : #include "alias.h"
      53              : #include "gimple-range.h"
      54              : 
      55              : /* Even though this file is called tree-ssa-pre.cc, we actually
      56              :    implement a bit more than just PRE here.  All of them piggy-back
      57              :    on GVN which is implemented in tree-ssa-sccvn.cc.
      58              : 
      59              :      1. Full Redundancy Elimination (FRE)
      60              :         This is the elimination phase of GVN.
      61              : 
      62              :      2. Partial Redundancy Elimination (PRE)
      63              :         This is adds computation of AVAIL_OUT and ANTIC_IN and
      64              :         doing expression insertion to form GVN-PRE.
      65              : 
      66              :      3. Code hoisting
      67              :         This optimization uses the ANTIC_IN sets computed for PRE
      68              :         to move expressions further up than PRE would do, to make
      69              :         multiple computations of the same value fully redundant.
      70              :         This pass is explained below (after the explanation of the
      71              :         basic algorithm for PRE).
      72              : */
      73              : 
      74              : /* TODO:
      75              : 
      76              :    1. Avail sets can be shared by making an avail_find_leader that
      77              :       walks up the dominator tree and looks in those avail sets.
      78              :       This might affect code optimality, it's unclear right now.
      79              :       Currently the AVAIL_OUT sets are the remaining quadraticness in
      80              :       memory of GVN-PRE.
      81              :    2. Strength reduction can be performed by anticipating expressions
      82              :       we can repair later on.
      83              :    3. We can do back-substitution or smarter value numbering to catch
      84              :       commutative expressions split up over multiple statements.
      85              : */
      86              : 
      87              : /* For ease of terminology, "expression node" in the below refers to
      88              :    every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
      89              :    represent the actual statement containing the expressions we care about,
      90              :    and we cache the value number by putting it in the expression.  */
      91              : 
      92              : /* Basic algorithm for Partial Redundancy Elimination:
      93              : 
      94              :    First we walk the statements to generate the AVAIL sets, the
      95              :    EXP_GEN sets, and the tmp_gen sets.  EXP_GEN sets represent the
      96              :    generation of values/expressions by a given block.  We use them
      97              :    when computing the ANTIC sets.  The AVAIL sets consist of
      98              :    SSA_NAME's that represent values, so we know what values are
      99              :    available in what blocks.  AVAIL is a forward dataflow problem.  In
     100              :    SSA, values are never killed, so we don't need a kill set, or a
     101              :    fixpoint iteration, in order to calculate the AVAIL sets.  In
     102              :    traditional parlance, AVAIL sets tell us the downsafety of the
     103              :    expressions/values.
     104              : 
     105              :    Next, we generate the ANTIC sets.  These sets represent the
     106              :    anticipatable expressions.  ANTIC is a backwards dataflow
     107              :    problem.  An expression is anticipatable in a given block if it could
     108              :    be generated in that block.  This means that if we had to perform
     109              :    an insertion in that block, of the value of that expression, we
     110              :    could.  Calculating the ANTIC sets requires phi translation of
     111              :    expressions, because the flow goes backwards through phis.  We must
     112              :    iterate to a fixpoint of the ANTIC sets, because we have a kill
     113              :    set.  Even in SSA form, values are not live over the entire
     114              :    function, only from their definition point onwards.  So we have to
     115              :    remove values from the ANTIC set once we go past the definition
     116              :    point of the leaders that make them up.
     117              :    compute_antic/compute_antic_aux performs this computation.
     118              : 
     119              :    Third, we perform insertions to make partially redundant
     120              :    expressions fully redundant.
     121              : 
     122              :    An expression is partially redundant (excluding partial
     123              :    anticipation) if:
     124              : 
     125              :    1. It is AVAIL in some, but not all, of the predecessors of a
     126              :       given block.
     127              :    2. It is ANTIC in all the predecessors.
     128              : 
     129              :    In order to make it fully redundant, we insert the expression into
     130              :    the predecessors where it is not available, but is ANTIC.
     131              : 
     132              :    When optimizing for size, we only eliminate the partial redundancy
     133              :    if we need to insert in only one predecessor.  This avoids almost
     134              :    completely the code size increase that PRE usually causes.
     135              : 
     136              :    For the partial anticipation case, we only perform insertion if it
     137              :    is partially anticipated in some block, and fully available in all
     138              :    of the predecessors.
     139              : 
     140              :    do_pre_regular_insertion/do_pre_partial_partial_insertion
     141              :    performs these steps, driven by insert/insert_aux.
     142              : 
     143              :    Fourth, we eliminate fully redundant expressions.
     144              :    This is a simple statement walk that replaces redundant
     145              :    calculations with the now available values.  */
     146              : 
     147              : /* Basic algorithm for Code Hoisting:
     148              : 
     149              :    Code hoisting is: Moving value computations up in the control flow
     150              :    graph to make multiple copies redundant.  Typically this is a size
     151              :    optimization, but there are cases where it also is helpful for speed.
     152              : 
     153              :    A simple code hoisting algorithm is implemented that piggy-backs on
     154              :    the PRE infrastructure.  For code hoisting, we have to know ANTIC_OUT
     155              :    which is effectively ANTIC_IN - AVAIL_OUT.  The latter two have to be
     156              :    computed for PRE, and we can use them to perform a limited version of
     157              :    code hoisting, too.
     158              : 
     159              :    For the purpose of this implementation, a value is hoistable to a basic
     160              :    block B if the following properties are met:
     161              : 
     162              :    1. The value is in ANTIC_IN(B) -- the value will be computed on all
     163              :       paths from B to function exit and it can be computed in B);
     164              : 
     165              :    2. The value is not in AVAIL_OUT(B) -- there would be no need to
     166              :       compute the value again and make it available twice;
     167              : 
     168              :    3. All successors of B are dominated by B -- makes sure that inserting
     169              :       a computation of the value in B will make the remaining
     170              :       computations fully redundant;
     171              : 
     172              :    4. At least one successor has the value in AVAIL_OUT -- to avoid
     173              :       hoisting values up too far;
     174              : 
     175              :    5. There are at least two successors of B -- hoisting in straight
     176              :       line code is pointless.
     177              : 
     178              :    The third condition is not strictly necessary, but it would complicate
     179              :    the hoisting pass a lot.  In fact, I don't know of any code hoisting
     180              :    algorithm that does not have this requirement.  Fortunately, experiments
     181              :    have show that most candidate hoistable values are in regions that meet
     182              :    this condition (e.g. diamond-shape regions).
     183              : 
     184              :    The forth condition is necessary to avoid hoisting things up too far
     185              :    away from the uses of the value.  Nothing else limits the algorithm
     186              :    from hoisting everything up as far as ANTIC_IN allows.  Experiments
     187              :    with SPEC and CSiBE have shown that hoisting up too far results in more
     188              :    spilling, less benefits for code size, and worse benchmark scores.
     189              :    Fortunately, in practice most of the interesting hoisting opportunities
     190              :    are caught despite this limitation.
     191              : 
     192              :    For hoistable values that meet all conditions, expressions are inserted
     193              :    to make the calculation of the hoistable value fully redundant.  We
     194              :    perform code hoisting insertions after each round of PRE insertions,
     195              :    because code hoisting never exposes new PRE opportunities, but PRE can
     196              :    create new code hoisting opportunities.
     197              : 
     198              :    The code hoisting algorithm is implemented in do_hoist_insert, driven
     199              :    by insert/insert_aux.  */
     200              : 
     201              : /* Representations of value numbers:
     202              : 
     203              :    Value numbers are represented by a representative SSA_NAME.  We
     204              :    will create fake SSA_NAME's in situations where we need a
     205              :    representative but do not have one (because it is a complex
     206              :    expression).  In order to facilitate storing the value numbers in
     207              :    bitmaps, and keep the number of wasted SSA_NAME's down, we also
     208              :    associate a value_id with each value number, and create full blown
     209              :    ssa_name's only where we actually need them (IE in operands of
     210              :    existing expressions).
     211              : 
     212              :    Theoretically you could replace all the value_id's with
     213              :    SSA_NAME_VERSION, but this would allocate a large number of
     214              :    SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
     215              :    It would also require an additional indirection at each point we
     216              :    use the value id.  */
     217              : 
     218              : /* Representation of expressions on value numbers:
     219              : 
     220              :    Expressions consisting of value numbers are represented the same
     221              :    way as our VN internally represents them, with an additional
     222              :    "pre_expr" wrapping around them in order to facilitate storing all
     223              :    of the expressions in the same sets.  */
     224              : 
     225              : /* Representation of sets:
     226              : 
     227              :    The dataflow sets do not need to be sorted in any particular order
     228              :    for the majority of their lifetime, are simply represented as two
     229              :    bitmaps, one that keeps track of values present in the set, and one
     230              :    that keeps track of expressions present in the set.
     231              : 
     232              :    When we need them in topological order, we produce it on demand by
     233              :    transforming the bitmap into an array and sorting it into topo
     234              :    order.  */
     235              : 
     236              : /* Type of expression, used to know which member of the PRE_EXPR union
     237              :    is valid.  */
     238              : 
     239              : enum pre_expr_kind
     240              : {
     241              :     NAME,
     242              :     NARY,
     243              :     REFERENCE,
     244              :     CONSTANT
     245              : };
     246              : 
     247              : union pre_expr_union
     248              : {
     249              :   tree name;
     250              :   tree constant;
     251              :   vn_nary_op_t nary;
     252              :   vn_reference_t reference;
     253              : };
     254              : 
     255              : typedef struct pre_expr_d : nofree_ptr_hash <pre_expr_d>
     256              : {
     257              :   enum pre_expr_kind kind;
     258              :   unsigned int id;
     259              :   unsigned value_id;
     260              :   location_t loc;
     261              :   pre_expr_union u;
     262              : 
     263              :   /* hash_table support.  */
     264              :   static inline hashval_t hash (const pre_expr_d *);
     265              :   static inline int equal (const pre_expr_d *, const pre_expr_d *);
     266              : } *pre_expr;
     267              : 
     268              : #define PRE_EXPR_NAME(e) (e)->u.name
     269              : #define PRE_EXPR_NARY(e) (e)->u.nary
     270              : #define PRE_EXPR_REFERENCE(e) (e)->u.reference
     271              : #define PRE_EXPR_CONSTANT(e) (e)->u.constant
     272              : 
     273              : /* Compare E1 and E1 for equality.  */
     274              : 
     275              : inline int
     276     58438024 : pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2)
     277              : {
     278     58438024 :   if (e1->kind != e2->kind)
     279              :     return false;
     280              : 
     281     37005684 :   switch (e1->kind)
     282              :     {
     283      4819268 :     case CONSTANT:
     284      4819268 :       return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
     285      4819268 :                                        PRE_EXPR_CONSTANT (e2));
     286       158017 :     case NAME:
     287       158017 :       return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
     288     23515737 :     case NARY:
     289     23515737 :       return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
     290      8512662 :     case REFERENCE:
     291      8512662 :       return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
     292      8512662 :                               PRE_EXPR_REFERENCE (e2), true);
     293            0 :     default:
     294            0 :       gcc_unreachable ();
     295              :     }
     296              : }
     297              : 
     298              : /* Hash E.  */
     299              : 
     300              : inline hashval_t
     301     93177564 : pre_expr_d::hash (const pre_expr_d *e)
     302              : {
     303     93177564 :   switch (e->kind)
     304              :     {
     305      7370647 :     case CONSTANT:
     306      7370647 :       return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
     307            0 :     case NAME:
     308            0 :       return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
     309     58219037 :     case NARY:
     310     58219037 :       return PRE_EXPR_NARY (e)->hashcode;
     311     27587880 :     case REFERENCE:
     312     27587880 :       return PRE_EXPR_REFERENCE (e)->hashcode;
     313            0 :     default:
     314            0 :       gcc_unreachable ();
     315              :     }
     316              : }
     317              : 
     318              : /* Next global expression id number.  */
     319              : static unsigned int next_expression_id;
     320              : 
     321              : /* Mapping from expression to id number we can use in bitmap sets.  */
     322              : static vec<pre_expr> expressions;
     323              : static hash_table<pre_expr_d> *expression_to_id;
     324              : static vec<unsigned> name_to_id;
     325              : static obstack pre_expr_obstack;
     326              : 
     327              : /* Allocate an expression id for EXPR.  */
     328              : 
     329              : static inline unsigned int
     330     44353271 : alloc_expression_id (pre_expr expr)
     331              : {
     332     44353271 :   struct pre_expr_d **slot;
     333              :   /* Make sure we won't overflow. */
     334     44353271 :   gcc_assert (next_expression_id + 1 > next_expression_id);
     335     44353271 :   expr->id = next_expression_id++;
     336     44353271 :   expressions.safe_push (expr);
     337     44353271 :   if (expr->kind == NAME)
     338              :     {
     339     24201817 :       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
     340              :       /* vec::safe_grow_cleared allocates no headroom.  Avoid frequent
     341              :          re-allocations by using vec::reserve upfront.  */
     342     24201817 :       unsigned old_len = name_to_id.length ();
     343     48403634 :       name_to_id.reserve (num_ssa_names - old_len);
     344     48403634 :       name_to_id.quick_grow_cleared (num_ssa_names);
     345     24201817 :       gcc_assert (name_to_id[version] == 0);
     346     24201817 :       name_to_id[version] = expr->id;
     347              :     }
     348              :   else
     349              :     {
     350     20151454 :       slot = expression_to_id->find_slot (expr, INSERT);
     351     20151454 :       gcc_assert (!*slot);
     352     20151454 :       *slot = expr;
     353              :     }
     354     44353271 :   return next_expression_id - 1;
     355              : }
     356              : 
     357              : /* Return the expression id for tree EXPR.  */
     358              : 
     359              : static inline unsigned int
     360    260445603 : get_expression_id (const pre_expr expr)
     361              : {
     362    260445603 :   return expr->id;
     363              : }
     364              : 
     365              : static inline unsigned int
     366     79845647 : lookup_expression_id (const pre_expr expr)
     367              : {
     368     79845647 :   struct pre_expr_d **slot;
     369              : 
     370     79845647 :   if (expr->kind == NAME)
     371              :     {
     372     53677855 :       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
     373     53677855 :       if (name_to_id.length () <= version)
     374              :         return 0;
     375     50623041 :       return name_to_id[version];
     376              :     }
     377              :   else
     378              :     {
     379     26167792 :       slot = expression_to_id->find_slot (expr, NO_INSERT);
     380     26167792 :       if (!slot)
     381              :         return 0;
     382      6016338 :       return ((pre_expr)*slot)->id;
     383              :     }
     384              : }
     385              : 
     386              : /* Return the expression that has expression id ID */
     387              : 
     388              : static inline pre_expr
     389    636772808 : expression_for_id (unsigned int id)
     390              : {
     391   1273545616 :   return expressions[id];
     392              : }
     393              : 
     394              : static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
     395              : 
     396              : /* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */
     397              : 
     398              : static pre_expr
     399     53677855 : get_or_alloc_expr_for_name (tree name)
     400              : {
     401     53677855 :   struct pre_expr_d expr;
     402     53677855 :   pre_expr result;
     403     53677855 :   unsigned int result_id;
     404              : 
     405     53677855 :   expr.kind = NAME;
     406     53677855 :   expr.id = 0;
     407     53677855 :   PRE_EXPR_NAME (&expr) = name;
     408     53677855 :   result_id = lookup_expression_id (&expr);
     409     53677855 :   if (result_id != 0)
     410     29476038 :     return expression_for_id (result_id);
     411              : 
     412     24201817 :   result = pre_expr_pool.allocate ();
     413     24201817 :   result->kind = NAME;
     414     24201817 :   result->loc = UNKNOWN_LOCATION;
     415     24201817 :   result->value_id = VN_INFO (name)->value_id;
     416     24201817 :   PRE_EXPR_NAME (result) = name;
     417     24201817 :   alloc_expression_id (result);
     418     24201817 :   return result;
     419              : }
     420              : 
     421              : /* Given an NARY, get or create a pre_expr to represent it.  Assign
     422              :    VALUE_ID to it or allocate a new value-id if it is zero.  Record
     423              :    LOC as the original location of the expression.  */
     424              : 
     425              : static pre_expr
     426     13822277 : get_or_alloc_expr_for_nary (vn_nary_op_t nary, unsigned value_id,
     427              :                             location_t loc = UNKNOWN_LOCATION)
     428              : {
     429     13822277 :   struct pre_expr_d expr;
     430     13822277 :   pre_expr result;
     431     13822277 :   unsigned int result_id;
     432              : 
     433     13822277 :   gcc_assert (value_id == 0 || !value_id_constant_p (value_id));
     434     13822277 :   gcc_assert (nary->opcode != SSA_NAME
     435              :               && TREE_CODE_CLASS (nary->opcode) != tcc_constant);
     436              : 
     437     13822277 :   expr.kind = NARY;
     438     13822277 :   expr.id = 0;
     439     13822277 :   nary->hashcode = vn_nary_op_compute_hash (nary);
     440     13822277 :   PRE_EXPR_NARY (&expr) = nary;
     441     13822277 :   result_id = lookup_expression_id (&expr);
     442     13822277 :   if (result_id != 0)
     443       999113 :     return expression_for_id (result_id);
     444              : 
     445     12823164 :   result = pre_expr_pool.allocate ();
     446     12823164 :   result->kind = NARY;
     447     12823164 :   result->loc = loc;
     448     12823164 :   result->value_id = value_id ? value_id : get_next_value_id ();
     449     12823164 :   PRE_EXPR_NARY (result)
     450     12823164 :     = alloc_vn_nary_op_noinit (nary->length, &pre_expr_obstack);
     451     12823164 :   memcpy (PRE_EXPR_NARY (result), nary, sizeof_vn_nary_op (nary->length));
     452     12823164 :   alloc_expression_id (result);
     453     12823164 :   return result;
     454              : }
     455              : 
     456              : /* Given an REFERENCE, get or create a pre_expr to represent it.  Assign
     457              :    VALUE_ID to it or allocate a new value-id if it is zero.  Record
     458              :    LOC as the original location of the expression.  If MOVE_OPERANDS
     459              :    is true then ownership of REFERENCE->operands is transferred, otherwise
     460              :    a copy is made if necessary.  */
     461              : 
     462              : static pre_expr
     463      7214330 : get_or_alloc_expr_for_reference (vn_reference_t reference,
     464              :                                  unsigned value_id,
     465              :                                  location_t loc = UNKNOWN_LOCATION,
     466              :                                  bool move_operands = false)
     467              : {
     468      7214330 :   struct pre_expr_d expr;
     469      7214330 :   pre_expr result;
     470      7214330 :   unsigned int result_id;
     471              : 
     472      7214330 :   expr.kind = REFERENCE;
     473      7214330 :   expr.id = 0;
     474      7214330 :   PRE_EXPR_REFERENCE (&expr) = reference;
     475      7214330 :   result_id = lookup_expression_id (&expr);
     476      7214330 :   if (result_id != 0)
     477              :     {
     478       752075 :       if (move_operands)
     479       739539 :         reference->operands.release ();
     480       752075 :       return expression_for_id (result_id);
     481              :     }
     482              : 
     483      6462255 :   result = pre_expr_pool.allocate ();
     484      6462255 :   result->kind = REFERENCE;
     485      6462255 :   result->loc = loc;
     486      6462255 :   result->value_id = value_id ? value_id : get_next_value_id ();
     487      6462255 :   vn_reference_t ref = XOBNEW (&pre_expr_obstack, struct vn_reference_s);
     488      6462255 :   *ref = *reference;
     489      6462255 :   if (!move_operands)
     490       453490 :     ref->operands = ref->operands.copy ();
     491      6462255 :   PRE_EXPR_REFERENCE (result) = ref;
     492      6462255 :   alloc_expression_id (result);
     493      6462255 :   return result;
     494              : }
     495              : 
     496              : 
     497              : /* An unordered bitmap set.  One bitmap tracks values, the other,
     498              :    expressions.  */
     499    148229494 : typedef class bitmap_set
     500              : {
     501              : public:
     502              :   bitmap_head expressions;
     503              :   bitmap_head values;
     504              : } *bitmap_set_t;
     505              : 
     506              : #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi)            \
     507              :   EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
     508              : 
     509              : #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi)           \
     510              :   EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
     511              : 
     512              : /* Mapping from value id to expressions with that value_id.  */
     513              : static vec<bitmap> value_expressions;
     514              : /* We just record a single expression for each constant value,
     515              :    one of kind CONSTANT.  */
     516              : static vec<pre_expr> constant_value_expressions;
     517              : 
     518              : 
     519              : /* This structure is used to keep track of statistics on what
     520              :    optimization PRE was able to perform.  */
     521              : static struct
     522              : {
     523              :   /* The number of new expressions/temporaries generated by PRE.  */
     524              :   int insertions;
     525              : 
     526              :   /* The number of inserts found due to partial anticipation  */
     527              :   int pa_insert;
     528              : 
     529              :   /* The number of inserts made for code hoisting.  */
     530              :   int hoist_insert;
     531              : 
     532              :   /* The number of new PHI nodes added by PRE.  */
     533              :   int phis;
     534              : } pre_stats;
     535              : 
     536              : static bool do_partial_partial;
     537              : static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
     538              : static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
     539              : static bool bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
     540              : static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
     541              : static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
     542              : static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
     543              : static bitmap_set_t bitmap_set_new (void);
     544              : static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
     545              :                                          tree);
     546              : static tree find_or_generate_expression (basic_block, tree, gimple_seq *);
     547              : static unsigned int get_expr_value_id (pre_expr);
     548              : 
     549              : /* We can add and remove elements and entries to and from sets
     550              :    and hash tables, so we use alloc pools for them.  */
     551              : 
     552              : static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets");
     553              : static bitmap_obstack grand_bitmap_obstack;
     554              : 
     555              : /* A three tuple {e, pred, v} used to cache phi translations in the
     556              :    phi_translate_table.  */
     557              : 
     558              : typedef struct expr_pred_trans_d : public typed_noop_remove <expr_pred_trans_d>
     559              : {
     560              :   typedef expr_pred_trans_d value_type;
     561              :   typedef expr_pred_trans_d compare_type;
     562              : 
     563              :   /* The expression ID.  */
     564              :   unsigned e;
     565              : 
     566              :   /* The value expression ID that resulted from the translation.  */
     567              :   unsigned v;
     568              : 
     569              :   /* hash_table support.  */
     570              :   static inline void mark_empty (expr_pred_trans_d &);
     571              :   static inline bool is_empty (const expr_pred_trans_d &);
     572              :   static inline void mark_deleted (expr_pred_trans_d &);
     573              :   static inline bool is_deleted (const expr_pred_trans_d &);
     574              :   static const bool empty_zero_p = true;
     575              :   static inline hashval_t hash (const expr_pred_trans_d &);
     576              :   static inline int equal (const expr_pred_trans_d &, const expr_pred_trans_d &);
     577              : } *expr_pred_trans_t;
     578              : typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
     579              : 
     580              : inline bool
     581   1406759242 : expr_pred_trans_d::is_empty (const expr_pred_trans_d &e)
     582              : {
     583   1406759242 :   return e.e == 0;
     584              : }
     585              : 
     586              : inline bool
     587    282394853 : expr_pred_trans_d::is_deleted (const expr_pred_trans_d &e)
     588              : {
     589    282394853 :   return e.e == -1u;
     590              : }
     591              : 
     592              : inline void
     593      2307900 : expr_pred_trans_d::mark_empty (expr_pred_trans_d &e)
     594              : {
     595      2307900 :   e.e = 0;
     596              : }
     597              : 
     598              : inline void
     599      3936910 : expr_pred_trans_d::mark_deleted (expr_pred_trans_d &e)
     600              : {
     601      3936910 :   e.e = -1u;
     602              : }
     603              : 
     604              : inline hashval_t
     605              : expr_pred_trans_d::hash (const expr_pred_trans_d &e)
     606              : {
     607              :   return e.e;
     608              : }
     609              : 
     610              : inline int
     611    220829063 : expr_pred_trans_d::equal (const expr_pred_trans_d &ve1,
     612              :                           const expr_pred_trans_d &ve2)
     613              : {
     614    220829063 :   return ve1.e == ve2.e;
     615              : }
     616              : 
     617              : /* Sets that we need to keep track of.  */
     618              : typedef struct bb_bitmap_sets
     619              : {
     620              :   /* The EXP_GEN set, which represents expressions/values generated in
     621              :      a basic block.  */
     622              :   bitmap_set_t exp_gen;
     623              : 
     624              :   /* The PHI_GEN set, which represents PHI results generated in a
     625              :      basic block.  */
     626              :   bitmap_set_t phi_gen;
     627              : 
     628              :   /* The TMP_GEN set, which represents results/temporaries generated
     629              :      in a basic block. IE the LHS of an expression.  */
     630              :   bitmap_set_t tmp_gen;
     631              : 
     632              :   /* The AVAIL_OUT set, which represents which values are available in
     633              :      a given basic block.  */
     634              :   bitmap_set_t avail_out;
     635              : 
     636              :   /* The ANTIC_IN set, which represents which values are anticipatable
     637              :      in a given basic block.  */
     638              :   bitmap_set_t antic_in;
     639              : 
     640              :   /* The PA_IN set, which represents which values are
     641              :      partially anticipatable in a given basic block.  */
     642              :   bitmap_set_t pa_in;
     643              : 
     644              :   /* The NEW_SETS set, which is used during insertion to augment the
     645              :      AVAIL_OUT set of blocks with the new insertions performed during
     646              :      the current iteration.  */
     647              :   bitmap_set_t new_sets;
     648              : 
     649              :   /* A cache for value_dies_in_block_x.  */
     650              :   bitmap expr_dies;
     651              : 
     652              :   /* The live virtual operand on successor edges.  */
     653              :   tree vop_on_exit;
     654              : 
     655              :   /* PHI translate cache for the single successor edge.  */
     656              :   hash_table<expr_pred_trans_d> *phi_translate_table;
     657              : 
     658              :   /* True if we have visited this block during ANTIC calculation.  */
     659              :   unsigned int visited : 1;
     660              : 
     661              :   /* True when the block contains a call that might not return.  */
     662              :   unsigned int contains_may_not_return_call : 1;
     663              : } *bb_value_sets_t;
     664              : 
     665              : #define EXP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->exp_gen
     666              : #define PHI_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->phi_gen
     667              : #define TMP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->tmp_gen
     668              : #define AVAIL_OUT(BB)   ((bb_value_sets_t) ((BB)->aux))->avail_out
     669              : #define ANTIC_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->antic_in
     670              : #define PA_IN(BB)       ((bb_value_sets_t) ((BB)->aux))->pa_in
     671              : #define NEW_SETS(BB)    ((bb_value_sets_t) ((BB)->aux))->new_sets
     672              : #define EXPR_DIES(BB)   ((bb_value_sets_t) ((BB)->aux))->expr_dies
     673              : #define PHI_TRANS_TABLE(BB) ((bb_value_sets_t) ((BB)->aux))->phi_translate_table
     674              : #define BB_VISITED(BB)  ((bb_value_sets_t) ((BB)->aux))->visited
     675              : #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
     676              : #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
     677              : 
     678              : 
     679              : /* Add the tuple mapping from {expression E, basic block PRED} to
     680              :    the phi translation table and return whether it pre-existed.  */
     681              : 
     682              : static inline bool
     683     87131990 : phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
     684              : {
     685     87131990 :   if (!PHI_TRANS_TABLE (pred))
     686       198245 :     PHI_TRANS_TABLE (pred) = new hash_table<expr_pred_trans_d> (11);
     687              : 
     688     87131990 :   expr_pred_trans_t slot;
     689     87131990 :   expr_pred_trans_d tem;
     690     87131990 :   unsigned id = get_expression_id (e);
     691     87131990 :   tem.e = id;
     692     87131990 :   slot = PHI_TRANS_TABLE (pred)->find_slot_with_hash (tem, id, INSERT);
     693     87131990 :   if (slot->e)
     694              :     {
     695     63339197 :       *entry = slot;
     696     63339197 :       return true;
     697              :     }
     698              : 
     699     23792793 :   *entry = slot;
     700     23792793 :   slot->e = id;
     701     23792793 :   return false;
     702              : }
     703              : 
     704              : 
     705              : /* Add expression E to the expression set of value id V.  */
     706              : 
     707              : static void
     708     46104459 : add_to_value (unsigned int v, pre_expr e)
     709              : {
     710            0 :   gcc_checking_assert (get_expr_value_id (e) == v);
     711              : 
     712     46104459 :   if (value_id_constant_p (v))
     713              :     {
     714       912163 :       if (e->kind != CONSTANT)
     715              :         return;
     716              : 
     717       866035 :       if (-v >= constant_value_expressions.length ())
     718       518672 :         constant_value_expressions.safe_grow_cleared (-v + 1);
     719              : 
     720       866035 :       pre_expr leader = constant_value_expressions[-v];
     721       866035 :       if (!leader)
     722       866035 :         constant_value_expressions[-v] = e;
     723              :     }
     724              :   else
     725              :     {
     726     45192296 :       if (v >= value_expressions.length ())
     727      7132601 :         value_expressions.safe_grow_cleared (v + 1);
     728              : 
     729     45192296 :       bitmap set = value_expressions[v];
     730     45192296 :       if (!set)
     731              :         {
     732     25266023 :           set = BITMAP_ALLOC (&grand_bitmap_obstack);
     733     25266023 :           value_expressions[v] = set;
     734              :         }
     735     45192296 :       bitmap_set_bit (set, get_expression_id (e));
     736              :     }
     737              : }
     738              : 
     739              : /* Create a new bitmap set and return it.  */
     740              : 
     741              : static bitmap_set_t
     742    148229494 : bitmap_set_new (void)
     743              : {
     744    148229494 :   bitmap_set_t ret = bitmap_set_pool.allocate ();
     745    148229494 :   bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
     746    148229494 :   bitmap_initialize (&ret->values, &grand_bitmap_obstack);
     747    148229494 :   return ret;
     748              : }
     749              : 
     750              : /* Return the value id for a PRE expression EXPR.  */
     751              : 
     752              : static unsigned int
     753    533649802 : get_expr_value_id (pre_expr expr)
     754              : {
     755              :   /* ???  We cannot assert that expr has a value-id (it can be 0), because
     756              :      we assign value-ids only to expressions that have a result
     757              :      in set_hashtable_value_ids.  */
     758     46104459 :   return expr->value_id;
     759              : }
     760              : 
     761              : /* Return a VN valnum (SSA name or constant) for the PRE value-id VAL.  */
     762              : 
     763              : static tree
     764      1268919 : vn_valnum_from_value_id (unsigned int val)
     765              : {
     766      1268919 :   if (value_id_constant_p (val))
     767              :     {
     768            0 :       pre_expr vexpr = constant_value_expressions[-val];
     769            0 :       if (vexpr)
     770            0 :         return PRE_EXPR_CONSTANT (vexpr);
     771              :       return NULL_TREE;
     772              :     }
     773              : 
     774      1268919 :   bitmap exprset = value_expressions[val];
     775      1268919 :   bitmap_iterator bi;
     776      1268919 :   unsigned int i;
     777      1882011 :   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
     778              :     {
     779      1539931 :       pre_expr vexpr = expression_for_id (i);
     780      1539931 :       if (vexpr->kind == NAME)
     781       926839 :         return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
     782              :     }
     783              :   return NULL_TREE;
     784              : }
     785              : 
     786              : /* Insert an expression EXPR into a bitmapped set.  */
     787              : 
     788              : static void
     789     76296871 : bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
     790              : {
     791     76296871 :   unsigned int val = get_expr_value_id (expr);
     792     76296871 :   if (! value_id_constant_p (val))
     793              :     {
     794              :       /* Note this is the only function causing multiple expressions
     795              :          for the same value to appear in a set.  This is needed for
     796              :          TMP_GEN, PHI_GEN and NEW_SETs.  */
     797     73306749 :       bitmap_set_bit (&set->values, val);
     798     73306749 :       bitmap_set_bit (&set->expressions, get_expression_id (expr));
     799              :     }
     800     76296871 : }
     801              : 
     802              : /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
     803              : 
     804              : static void
     805     27330302 : bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
     806              : {
     807     27330302 :   bitmap_copy (&dest->expressions, &orig->expressions);
     808     27330302 :   bitmap_copy (&dest->values, &orig->values);
     809     27330302 : }
     810              : 
     811              : 
     812              : /* Free memory used up by SET.  */
     813              : static void
     814     74147802 : bitmap_set_free (bitmap_set_t set)
     815              : {
     816            0 :   bitmap_clear (&set->expressions);
     817     19757881 :   bitmap_clear (&set->values);
     818            0 : }
     819              : 
     820              : 
     821              : /* Sort pre_expr after their value-id.  */
     822              : 
     823              : static int
     824    436068068 : expr_cmp (const void *a_, const void *b_, void *)
     825              : {
     826    436068068 :   pre_expr a = *(pre_expr const *) a_;
     827    436068068 :   pre_expr b = *(pre_expr const *) b_;
     828    436068068 :   return a->value_id - b->value_id;
     829              : }
     830              : 
     831              : /* Return an expression that is a valid representation to insert for
     832              :    both A and B reaching expressions.  Return NULL if neither works,
     833              :    in this case all expressions of the value will be elided.  */
     834              : 
     835              : static pre_expr
     836       254008 : prefer (pre_expr a, pre_expr b)
     837              : {
     838       254008 :   if (a->kind == REFERENCE && b->kind == REFERENCE)
     839              :     {
     840        57429 :       auto refa = PRE_EXPR_REFERENCE (a);
     841        57429 :       auto refb = PRE_EXPR_REFERENCE (b);
     842        57429 :       auto &oprsa = refa->operands;
     843        57429 :       auto &oprsb = refb->operands;
     844        57429 :       pre_expr palias = NULL;
     845        57429 :       if (refa->set == refb->set
     846        54335 :           && refa->base_set == refb->base_set)
     847              :         ;
     848        11469 :       else if ((refb->set == refa->set
     849         3094 :                 || alias_set_subset_of (refb->set, refa->set))
     850        12902 :                && (refb->base_set == refa->base_set
     851         9051 :                    || alias_set_subset_of (refb->base_set, refa->base_set)))
     852              :         palias = a;
     853         4264 :       else if ((refa->set == refb->set
     854         1734 :                 || alias_set_subset_of (refa->set, refb->set))
     855         5805 :                && (refa->base_set == refb->base_set
     856         3287 :                    || alias_set_subset_of (refa->base_set, refb->base_set)))
     857              :         palias = b;
     858              :       else
     859              :         /* We have to chose an expression representation that can stand
     860              :            in for all others - there can be none, in which case we have
     861              :            to drop this PRE/hoisting opportunity.
     862              :            ???  Previously we've arranged for alias-set zero being used
     863              :            as fallback, but we do not really want to allocate a new expression
     864              :            here unless it proves to be absolutely necessary.  */
     865              :         return NULL;
     866        57130 :       pre_expr p = palias;
     867       114260 :       if (oprsa.length () > 1 && oprsb.length () > 1)
     868              :         {
     869        57130 :           vn_reference_op_t vroa = &oprsa[oprsa.length () - 2];
     870        57130 :           vn_reference_op_t vrob = &oprsb[oprsb.length () - 2];
     871        57130 :           if (vroa->opcode == MEM_REF && vrob->opcode == MEM_REF)
     872              :             {
     873              :               /* We have to canonicalize to the more conservative alignment.
     874              :                  gcc.dg/torture/pr65270-?.c.*/
     875        57105 :               pre_expr palign = NULL;
     876        57105 :               if (TYPE_ALIGN (vroa->type) < TYPE_ALIGN (vrob->type))
     877              :                 palign = a;
     878        56871 :               else if (TYPE_ALIGN (vroa->type) > TYPE_ALIGN (vrob->type))
     879              :                 palign = b;
     880          496 :               if (palign)
     881              :                 {
     882          496 :                   if (p && p != palign)
     883              :                     return NULL;
     884              :                   p = palign;
     885              :                 }
     886              :               /* We have to canonicalize to the more conservative (smaller)
     887              :                  innermost object access size.  gcc.dg/torture/pr110799.c.  */
     888        56707 :               if (TYPE_SIZE (vroa->type) != TYPE_SIZE (vrob->type))
     889              :                 {
     890         4992 :                   pre_expr psize = NULL;
     891         4992 :                   if (!TYPE_SIZE (vroa->type))
     892              :                     psize = a;
     893         4992 :                   else if (!TYPE_SIZE (vrob->type))
     894              :                     psize = b;
     895         4992 :                   else if (TREE_CODE (TYPE_SIZE (vroa->type)) == INTEGER_CST
     896         4992 :                            && TREE_CODE (TYPE_SIZE (vrob->type)) == INTEGER_CST)
     897              :                     {
     898         4986 :                       int cmp = tree_int_cst_compare (TYPE_SIZE (vroa->type),
     899         4986 :                                                       TYPE_SIZE (vrob->type));
     900         4986 :                       if (cmp < 0)
     901              :                         psize = a;
     902         2837 :                       else if (cmp > 0)
     903              :                         psize = b;
     904              :                     }
     905              :                   /* ???  What about non-constant sizes?  */
     906         4986 :                   if (psize)
     907              :                     {
     908         4986 :                       if (p && p != psize)
     909              :                         return NULL;
     910              :                       p = psize;
     911              :                     }
     912              :                 }
     913              :             }
     914              :         }
     915              :       /* Note we cannot leave it undecided because when having
     916              :          more than two expressions we have to keep doing
     917              :          pariwise reduction.  */
     918        52882 :       return p ? p : b;
     919              :     }
     920              :   /* Always prefer an non-REFERENCE, avoiding the above mess.  */
     921       196579 :   else if (a->kind == REFERENCE)
     922              :     return b;
     923       193159 :   else if (b->kind == REFERENCE)
     924              :     return a;
     925       162205 :   else if (a->kind == b->kind)
     926              :     ;
     927              :   /* And prefer NAME over anything else.  */
     928        10933 :   else if (b->kind == NAME)
     929              :     return b;
     930         8569 :   else if (a->kind == NAME)
     931         8569 :     return a;
     932              :   return b;
     933              : }
     934              : 
     935              : static void
     936              : pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap exclusions,
     937              :               bitmap val_visited, vec<pre_expr> &post);
     938              : 
     939              : /* DFS walk leaders of VAL to their operands with leaders in SET, collecting
     940              :    expressions in SET in postorder into POST.  */
     941              : 
     942              : static void
     943    192229665 : pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap exclusions,
     944              :               bitmap val_visited, vec<pre_expr> &post)
     945              : {
     946    192229665 :   unsigned int i;
     947    192229665 :   bitmap_iterator bi;
     948              : 
     949              :   /* Iterate over all leaders and DFS recurse.  Borrowed from
     950              :      bitmap_find_leader.  */
     951    192229665 :   bitmap exprset = value_expressions[val];
     952    192229665 :   if (!exprset->first->next)
     953              :     {
     954    453416897 :       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
     955    288983893 :         if (bitmap_bit_p (&set->expressions, i)
     956    288983893 :             && !bitmap_bit_p (exclusions, i))
     957    164713124 :           pre_expr_DFS (expression_for_id (i), set, exclusions,
     958              :                         val_visited, post);
     959    164433004 :       return;
     960              :     }
     961              : 
     962     56302655 :   EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
     963     28505994 :     if (!bitmap_bit_p (exclusions, i))
     964     28163205 :       pre_expr_DFS (expression_for_id (i), set, exclusions,
     965              :                     val_visited, post);
     966              : }
     967              : 
     968              : /* DFS walk EXPR to its operands with leaders in SET, collecting
     969              :    expressions in SET in postorder into POST.  */
     970              : 
     971              : static void
     972    192876329 : pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap exclusions,
     973              :               bitmap val_visited, vec<pre_expr> &post)
     974              : {
     975    192876329 :   switch (expr->kind)
     976              :     {
     977     88907733 :     case NARY:
     978     88907733 :       {
     979     88907733 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
     980    238324862 :         for (unsigned i = 0; i < nary->length; i++)
     981              :           {
     982    149417129 :             if (TREE_CODE (nary->op[i]) != SSA_NAME)
     983     47407302 :               continue;
     984    102009827 :             unsigned int op_val_id = VN_INFO (nary->op[i])->value_id;
     985              :             /* If we already found a leader for the value we've
     986              :                recursed already.  Avoid the costly bitmap_find_leader.  */
     987    102009827 :             if (bitmap_bit_p (&set->values, op_val_id)
     988    102009827 :                 && bitmap_set_bit (val_visited, op_val_id))
     989     64383579 :               pre_expr_DFS (op_val_id, set, exclusions, val_visited, post);
     990              :           }
     991              :         break;
     992              :       }
     993     30053349 :     case REFERENCE:
     994     30053349 :       {
     995     30053349 :         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
     996     30053349 :         vec<vn_reference_op_s> operands = ref->operands;
     997     30053349 :         vn_reference_op_t operand;
     998    118779515 :         for (unsigned i = 0; operands.iterate (i, &operand); i++)
     999              :           {
    1000     88726166 :             tree op[3];
    1001     88726166 :             op[0] = operand->op0;
    1002     88726166 :             op[1] = operand->op1;
    1003     88726166 :             op[2] = operand->op2;
    1004    354904664 :             for (unsigned n = 0; n < 3; ++n)
    1005              :               {
    1006    266178498 :                 if (!op[n] || TREE_CODE (op[n]) != SSA_NAME)
    1007    244470750 :                   continue;
    1008     21707748 :                 unsigned op_val_id = VN_INFO (op[n])->value_id;
    1009     21707748 :                 if (bitmap_bit_p (&set->values, op_val_id)
    1010     21707748 :                     && bitmap_set_bit (val_visited, op_val_id))
    1011     11314267 :                   pre_expr_DFS (op_val_id, set, exclusions, val_visited, post);
    1012              :               }
    1013              :           }
    1014              :         break;
    1015              :       }
    1016    192876329 :     default:;
    1017              :     }
    1018    192876329 :   post.quick_push (expr);
    1019    192876329 : }
    1020              : 
    1021              : /* Generate an topological-ordered array of bitmap set SET.  If FOR_INSERTION
    1022              :    is true then perform canonexpr on the set.  */
    1023              : 
    1024              : static vec<pre_expr>
    1025     18632338 : sorted_array_from_bitmap_set (bitmap_set_t set, bool for_insertion)
    1026              : {
    1027     18632338 :   unsigned int i;
    1028     18632338 :   bitmap_iterator bi;
    1029     18632338 :   vec<pre_expr> result;
    1030              : 
    1031              :   /* Pre-allocate enough space for the array.  */
    1032     18632338 :   unsigned cnt = bitmap_count_bits (&set->expressions);
    1033     18632338 :   result.create (cnt);
    1034              : 
    1035              :   /* For expressions with the same value from EXPRESSIONS retain only
    1036              :      expressions that can be inserted in place of all others.  */
    1037     18632338 :   auto_bitmap exclusions;
    1038     18632338 :   bitmap_tree_view (exclusions);
    1039     18632338 :   if (for_insertion && cnt > 1)
    1040              :     {
    1041     26787114 :       EXECUTE_IF_SET_IN_BITMAP (&set->expressions, 0, i, bi)
    1042     24142204 :         result.safe_push (expression_for_id (i));
    1043      2644910 :       result.sort (expr_cmp, NULL);
    1044     48276766 :       for (unsigned i = 0; i < result.length () - 1; ++i)
    1045     21493473 :         if (result[i]->value_id == result[i+1]->value_id)
    1046              :           {
    1047       254008 :             if (pre_expr p = prefer (result[i], result[i+1]))
    1048              :               {
    1049              :                 /* We retain and iterate on exprs[i+1], if we want to
    1050              :                    retain exprs[i], swap both.  */
    1051       249461 :                 if (p == result[i])
    1052        44292 :                   std::swap (result[i], result[i+1]);
    1053       249461 :                 bitmap_set_bit (exclusions, get_expression_id (result[i]));
    1054              :               }
    1055              :             else
    1056              :               {
    1057              :                 /* If neither works for pairwise choosing a conservative
    1058              :                    alternative, drop all REFERENCE expressions for this value.
    1059              :                    REFERENCE are always toplevel, so no chain should be
    1060              :                    interrupted by pruning them.  */
    1061              :                 unsigned j, k;
    1062            6 :                 for (j = i;; --j)
    1063         4553 :                   if (j == 0
    1064         4553 :                       || result[j - 1]->value_id != result[i]->value_id)
    1065              :                     break;
    1066              :                 for (k = j;; ++k)
    1067              :                   {
    1068         9149 :                     if (result[k]->kind == REFERENCE)
    1069         9149 :                       bitmap_set_bit (exclusions,
    1070         9149 :                                       get_expression_id (result[k]));
    1071         9149 :                     if (k == result.length () - 1
    1072         9149 :                         || result[k + 1]->value_id != result[i]->value_id)
    1073              :                       break;
    1074              :                   }
    1075              :                 i = k;
    1076              :               }
    1077              :           }
    1078      2644910 :       result.truncate (0);
    1079              :     }
    1080              : 
    1081     18632338 :   bool single_p = true;
    1082     18632338 :   auto_bitmap val_visited (&grand_bitmap_obstack);
    1083     18632338 :   bitmap_tree_view (val_visited);
    1084    102442885 :   FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
    1085     83810547 :     if (bitmap_set_bit (val_visited, i))
    1086              :       {
    1087     74046539 :         if (!result.is_empty ())
    1088              :           {
    1089     61173373 :             single_p = false;
    1090     61173373 :             result.truncate (0);
    1091              :           }
    1092     74046539 :         pre_expr_DFS (i, set, exclusions, val_visited, result);
    1093              :         /* Mark i as entry that is not forward reachable.  Note we do
    1094              :            have cycles in the value graph so eventually i reaches itself.  */
    1095     74046539 :         bitmap_clear_bit (val_visited, i);
    1096              :       }
    1097              :   /* If we didn't by luck visit only a single entry to the value
    1098              :      graph visit now all not forward reachable values.  */
    1099     18632338 :   if (!single_p)
    1100              :     {
    1101      9670553 :       result.truncate (0);
    1102      9670553 :       auto_bitmap val_visited2 (&grand_bitmap_obstack);
    1103      9670553 :       bitmap_tree_view (val_visited2);
    1104     89729461 :       FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
    1105     80058908 :         if (!bitmap_bit_p (val_visited, i))
    1106              :           {
    1107     42485280 :             if (bitmap_set_bit (val_visited2, i))
    1108     42485280 :               pre_expr_DFS (i, set, exclusions, val_visited2, result);
    1109              :             else
    1110            0 :               gcc_unreachable ();
    1111              :           }
    1112      9670553 :       if (flag_checking)
    1113              :         {
    1114      9670502 :           bitmap_list_view (val_visited2);
    1115      9670502 :           gcc_assert (bitmap_equal_p (&set->values, val_visited2));
    1116              :         }
    1117      9670553 :     }
    1118              : 
    1119     18632338 :   return result;
    1120     18632338 : }
    1121              : 
    1122              : /* Subtract all expressions contained in ORIG from DEST.  */
    1123              : 
    1124              : static bitmap_set_t
    1125     33029103 : bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig,
    1126              :                                  bool copy_values = false)
    1127              : {
    1128     33029103 :   bitmap_set_t result = bitmap_set_new ();
    1129     33029103 :   bitmap_iterator bi;
    1130     33029103 :   unsigned int i;
    1131              : 
    1132     33029103 :   bitmap_and_compl (&result->expressions, &dest->expressions,
    1133     33029103 :                     &orig->expressions);
    1134              : 
    1135     33029103 :   if (copy_values)
    1136       665534 :     bitmap_copy (&result->values, &dest->values);
    1137              :   else
    1138    109519501 :     FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
    1139              :       {
    1140     77155932 :         pre_expr expr = expression_for_id (i);
    1141     77155932 :         unsigned int value_id = get_expr_value_id (expr);
    1142     77155932 :         bitmap_set_bit (&result->values, value_id);
    1143              :       }
    1144              : 
    1145     33029103 :   return result;
    1146              : }
    1147              : 
    1148              : /* Subtract all values in bitmap set B from bitmap set A.  */
    1149              : 
    1150              : static void
    1151      1258415 : bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
    1152              : {
    1153      1258415 :   unsigned int i;
    1154      1258415 :   bitmap_iterator bi;
    1155      1258415 :   unsigned to_remove = -1U;
    1156      1258415 :   bitmap_and_compl_into (&a->values, &b->values);
    1157      9009172 :   FOR_EACH_EXPR_ID_IN_SET (a, i, bi)
    1158              :     {
    1159      7750757 :       if (to_remove != -1U)
    1160              :         {
    1161      1468212 :           bitmap_clear_bit (&a->expressions, to_remove);
    1162      1468212 :           to_remove = -1U;
    1163              :         }
    1164      7750757 :       pre_expr expr = expression_for_id (i);
    1165      7750757 :       if (! bitmap_bit_p (&a->values, get_expr_value_id (expr)))
    1166      1526128 :         to_remove = i;
    1167              :     }
    1168      1258415 :   if (to_remove != -1U)
    1169        57916 :     bitmap_clear_bit (&a->expressions, to_remove);
    1170      1258415 : }
    1171              : 
    1172              : 
    1173              : /* Return true if bitmapped set SET contains the value VALUE_ID.  */
    1174              : 
    1175              : static bool
    1176    192779463 : bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
    1177              : {
    1178            0 :   if (value_id_constant_p (value_id))
    1179              :     return true;
    1180              : 
    1181     89206651 :   return bitmap_bit_p (&set->values, value_id);
    1182              : }
    1183              : 
    1184              : /* Return true if two bitmap sets are equal.  */
    1185              : 
    1186              : static bool
    1187     15885344 : bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
    1188              : {
    1189            0 :   return bitmap_equal_p (&a->values, &b->values);
    1190              : }
    1191              : 
    1192              : /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
    1193              :    and add it otherwise.  Return true if any changes were made.  */
    1194              : 
    1195              : static bool
    1196     33810329 : bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
    1197              : {
    1198     33810329 :   unsigned int val = get_expr_value_id (expr);
    1199     33810329 :   if (value_id_constant_p (val))
    1200              :     return false;
    1201              : 
    1202     33810329 :   if (bitmap_set_contains_value (set, val))
    1203              :     {
    1204              :       /* The number of expressions having a given value is usually
    1205              :          significantly less than the total number of expressions in SET.
    1206              :          Thus, rather than check, for each expression in SET, whether it
    1207              :          has the value LOOKFOR, we walk the reverse mapping that tells us
    1208              :          what expressions have a given value, and see if any of those
    1209              :          expressions are in our set.  For large testcases, this is about
    1210              :          5-10x faster than walking the bitmap.  If this is somehow a
    1211              :          significant lose for some cases, we can choose which set to walk
    1212              :          based on the set size.  */
    1213     14407358 :       unsigned int i;
    1214     14407358 :       bitmap_iterator bi;
    1215     14407358 :       bitmap exprset = value_expressions[val];
    1216     16792741 :       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
    1217              :         {
    1218     16792741 :           if (bitmap_clear_bit (&set->expressions, i))
    1219              :             {
    1220     14407358 :               bitmap_set_bit (&set->expressions, get_expression_id (expr));
    1221     14407358 :               return i != get_expression_id (expr);
    1222              :             }
    1223              :         }
    1224            0 :       gcc_unreachable ();
    1225              :     }
    1226              : 
    1227     19402971 :   bitmap_insert_into_set (set, expr);
    1228     19402971 :   return true;
    1229              : }
    1230              : 
    1231              : /* Insert EXPR into SET if EXPR's value is not already present in
    1232              :    SET.  */
    1233              : 
    1234              : static void
    1235     61391803 : bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
    1236              : {
    1237     61391803 :   unsigned int val = get_expr_value_id (expr);
    1238              : 
    1239     61391803 :   gcc_checking_assert (expr->id == get_expression_id (expr));
    1240              : 
    1241              :   /* Constant values are always considered to be part of the set.  */
    1242     61391803 :   if (value_id_constant_p (val))
    1243              :     return;
    1244              : 
    1245              :   /* If the value membership changed, add the expression.  */
    1246     61332616 :   if (bitmap_set_bit (&set->values, val))
    1247     46783145 :     bitmap_set_bit (&set->expressions, expr->id);
    1248              : }
    1249              : 
    1250              : /* Print out EXPR to outfile.  */
    1251              : 
    1252              : static void
    1253         4573 : print_pre_expr (FILE *outfile, const pre_expr expr)
    1254              : {
    1255         4573 :   if (! expr)
    1256              :     {
    1257            0 :       fprintf (outfile, "NULL");
    1258            0 :       return;
    1259              :     }
    1260         4573 :   switch (expr->kind)
    1261              :     {
    1262            0 :     case CONSTANT:
    1263            0 :       print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr));
    1264            0 :       break;
    1265         3214 :     case NAME:
    1266         3214 :       print_generic_expr (outfile, PRE_EXPR_NAME (expr));
    1267         3214 :       break;
    1268         1072 :     case NARY:
    1269         1072 :       {
    1270         1072 :         unsigned int i;
    1271         1072 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    1272         1072 :         fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode));
    1273         4103 :         for (i = 0; i < nary->length; i++)
    1274              :           {
    1275         1959 :             print_generic_expr (outfile, nary->op[i]);
    1276         1959 :             if (i != (unsigned) nary->length - 1)
    1277          887 :               fprintf (outfile, ",");
    1278              :           }
    1279         1072 :         fprintf (outfile, "}");
    1280              :       }
    1281         1072 :       break;
    1282              : 
    1283          287 :     case REFERENCE:
    1284          287 :       {
    1285          287 :         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    1286          287 :         print_vn_reference_ops (outfile, ref->operands);
    1287          287 :         if (ref->vuse)
    1288              :           {
    1289          275 :             fprintf (outfile, "@");
    1290          275 :             print_generic_expr (outfile, ref->vuse);
    1291              :           }
    1292              :       }
    1293              :       break;
    1294              :     }
    1295              : }
    1296              : void debug_pre_expr (pre_expr);
    1297              : 
    1298              : /* Like print_pre_expr but always prints to stderr.  */
    1299              : DEBUG_FUNCTION void
    1300            0 : debug_pre_expr (pre_expr e)
    1301              : {
    1302            0 :   print_pre_expr (stderr, e);
    1303            0 :   fprintf (stderr, "\n");
    1304            0 : }
    1305              : 
    1306              : /* Print out SET to OUTFILE.  */
    1307              : 
    1308              : static void
    1309          913 : print_bitmap_set (FILE *outfile, bitmap_set_t set,
    1310              :                   const char *setname, int blockindex)
    1311              : {
    1312          913 :   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
    1313          913 :   if (set)
    1314              :     {
    1315          913 :       bool first = true;
    1316          913 :       unsigned i;
    1317          913 :       bitmap_iterator bi;
    1318              : 
    1319         5345 :       FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
    1320              :         {
    1321         4432 :           const pre_expr expr = expression_for_id (i);
    1322              : 
    1323         4432 :           if (!first)
    1324         3806 :             fprintf (outfile, ", ");
    1325         4432 :           first = false;
    1326         4432 :           print_pre_expr (outfile, expr);
    1327              : 
    1328         4432 :           fprintf (outfile, " (%04d)", get_expr_value_id (expr));
    1329              :         }
    1330              :     }
    1331          913 :   fprintf (outfile, " }\n");
    1332          913 : }
    1333              : 
    1334              : void debug_bitmap_set (bitmap_set_t);
    1335              : 
    1336              : DEBUG_FUNCTION void
    1337            0 : debug_bitmap_set (bitmap_set_t set)
    1338              : {
    1339            0 :   print_bitmap_set (stderr, set, "debug", 0);
    1340            0 : }
    1341              : 
    1342              : void debug_bitmap_sets_for (basic_block);
    1343              : 
    1344              : DEBUG_FUNCTION void
    1345            0 : debug_bitmap_sets_for (basic_block bb)
    1346              : {
    1347            0 :   print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
    1348            0 :   print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
    1349            0 :   print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
    1350            0 :   print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
    1351            0 :   print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
    1352            0 :   if (do_partial_partial)
    1353            0 :     print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
    1354            0 :   print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
    1355            0 : }
    1356              : 
    1357              : /* Print out the expressions that have VAL to OUTFILE.  */
    1358              : 
    1359              : static void
    1360            0 : print_value_expressions (FILE *outfile, unsigned int val)
    1361              : {
    1362            0 :   bitmap set = value_expressions[val];
    1363            0 :   if (set)
    1364              :     {
    1365            0 :       bitmap_set x;
    1366            0 :       char s[10];
    1367            0 :       sprintf (s, "%04d", val);
    1368            0 :       x.expressions = *set;
    1369            0 :       print_bitmap_set (outfile, &x, s, 0);
    1370              :     }
    1371            0 : }
    1372              : 
    1373              : 
    1374              : DEBUG_FUNCTION void
    1375            0 : debug_value_expressions (unsigned int val)
    1376              : {
    1377            0 :   print_value_expressions (stderr, val);
    1378            0 : }
    1379              : 
    1380              : /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
    1381              :    represent it.  */
    1382              : 
    1383              : static pre_expr
    1384      5131185 : get_or_alloc_expr_for_constant (tree constant)
    1385              : {
    1386      5131185 :   unsigned int result_id;
    1387      5131185 :   struct pre_expr_d expr;
    1388      5131185 :   pre_expr newexpr;
    1389              : 
    1390      5131185 :   expr.kind = CONSTANT;
    1391      5131185 :   PRE_EXPR_CONSTANT (&expr) = constant;
    1392      5131185 :   result_id = lookup_expression_id (&expr);
    1393      5131185 :   if (result_id != 0)
    1394      4265150 :     return expression_for_id (result_id);
    1395              : 
    1396       866035 :   newexpr = pre_expr_pool.allocate ();
    1397       866035 :   newexpr->kind = CONSTANT;
    1398       866035 :   newexpr->loc = UNKNOWN_LOCATION;
    1399       866035 :   PRE_EXPR_CONSTANT (newexpr) = constant;
    1400       866035 :   alloc_expression_id (newexpr);
    1401       866035 :   newexpr->value_id = get_or_alloc_constant_value_id (constant);
    1402       866035 :   add_to_value (newexpr->value_id, newexpr);
    1403       866035 :   return newexpr;
    1404              : }
    1405              : 
    1406              : /* Translate the VUSE backwards through phi nodes in E->dest, so that
    1407              :    it has the value it would have in E->src.  Set *SAME_VALID to true
    1408              :    in case the new vuse doesn't change the value id of the OPERANDS.  */
    1409              : 
    1410              : static tree
    1411      4537265 : translate_vuse_through_block (vec<vn_reference_op_s> operands,
    1412              :                               alias_set_type set, alias_set_type base_set,
    1413              :                               tree type, tree vuse, edge e, bool *same_valid)
    1414              : {
    1415      4537265 :   basic_block phiblock = e->dest;
    1416      4537265 :   gimple *def = SSA_NAME_DEF_STMT (vuse);
    1417      4537265 :   ao_ref ref;
    1418              : 
    1419      4537265 :   if (same_valid)
    1420      3254900 :     *same_valid = true;
    1421              : 
    1422              :   /* If value-numbering provided a memory state for this
    1423              :      that dominates PHIBLOCK we can just use that.  */
    1424      4537265 :   if (gimple_nop_p (def)
    1425      4537265 :       || (gimple_bb (def) != phiblock
    1426      1192139 :           && dominated_by_p (CDI_DOMINATORS, phiblock, gimple_bb (def))))
    1427              :     return vuse;
    1428              : 
    1429              :   /* We have pruned expressions that are killed in PHIBLOCK via
    1430              :      prune_clobbered_mems but we have not rewritten the VUSE to the one
    1431              :      live at the start of the block.  If there is no virtual PHI to translate
    1432              :      through return the VUSE live at entry.  Otherwise the VUSE to translate
    1433              :      is the def of the virtual PHI node.  */
    1434      2644432 :   gphi *phi = get_virtual_phi (phiblock);
    1435      2644432 :   if (!phi)
    1436        95155 :     return BB_LIVE_VOP_ON_EXIT
    1437              :              (get_immediate_dominator (CDI_DOMINATORS, phiblock));
    1438              : 
    1439      2549277 :   if (same_valid
    1440      2549277 :       && ao_ref_init_from_vn_reference (&ref, set, base_set, type, operands))
    1441              :     {
    1442      1856865 :       bitmap visited = NULL;
    1443              :       /* Try to find a vuse that dominates this phi node by skipping
    1444              :          non-clobbering statements.  */
    1445      1856865 :       unsigned int cnt = param_sccvn_max_alias_queries_per_access;
    1446      1856865 :       vuse = get_continuation_for_phi (phi, &ref, true,
    1447              :                                        cnt, &visited, NULL, NULL);
    1448      1856865 :       if (visited)
    1449      1845181 :         BITMAP_FREE (visited);
    1450              :     }
    1451              :   else
    1452              :     vuse = NULL_TREE;
    1453              :   /* If we didn't find any, the value ID can't stay the same.  */
    1454      2549277 :   if (!vuse && same_valid)
    1455      1612861 :     *same_valid = false;
    1456              : 
    1457              :   /* ??? We would like to return vuse here as this is the canonical
    1458              :      upmost vdef that this reference is associated with.  But during
    1459              :      insertion of the references into the hash tables we only ever
    1460              :      directly insert with their direct gimple_vuse, hence returning
    1461              :      something else would make us not find the other expression.  */
    1462      2549277 :   return PHI_ARG_DEF (phi, e->dest_idx);
    1463              : }
    1464              : 
    1465              : /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
    1466              :    SET2 *or* SET3.  This is used to avoid making a set consisting of the union
    1467              :    of PA_IN and ANTIC_IN during insert and phi-translation.  */
    1468              : 
    1469              : static inline pre_expr
    1470     24751917 : find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2,
    1471              :                      bitmap_set_t set3 = NULL)
    1472              : {
    1473     24751917 :   pre_expr result = NULL;
    1474              : 
    1475     24751917 :   if (set1)
    1476     24623898 :     result = bitmap_find_leader (set1, val);
    1477     24751917 :   if (!result && set2)
    1478      1614276 :     result = bitmap_find_leader (set2, val);
    1479     24751917 :   if (!result && set3)
    1480            0 :     result = bitmap_find_leader (set3, val);
    1481     24751917 :   return result;
    1482              : }
    1483              : 
    1484              : /* Get the tree type for our PRE expression e.  */
    1485              : 
    1486              : static tree
    1487      7529968 : get_expr_type (const pre_expr e)
    1488              : {
    1489      7529968 :   switch (e->kind)
    1490              :     {
    1491      1003313 :     case NAME:
    1492      1003313 :       return TREE_TYPE (PRE_EXPR_NAME (e));
    1493       191706 :     case CONSTANT:
    1494       191706 :       return TREE_TYPE (PRE_EXPR_CONSTANT (e));
    1495      1356656 :     case REFERENCE:
    1496      1356656 :       return PRE_EXPR_REFERENCE (e)->type;
    1497      4978293 :     case NARY:
    1498      4978293 :       return PRE_EXPR_NARY (e)->type;
    1499              :     }
    1500            0 :   gcc_unreachable ();
    1501              : }
    1502              : 
    1503              : /* Get a representative SSA_NAME for a given expression that is available in B.
    1504              :    Since all of our sub-expressions are treated as values, we require
    1505              :    them to be SSA_NAME's for simplicity.
    1506              :    Prior versions of GVNPRE used to use "value handles" here, so that
    1507              :    an expression would be VH.11 + VH.10 instead of d_3 + e_6.  In
    1508              :    either case, the operands are really values (IE we do not expect
    1509              :    them to be usable without finding leaders).  */
    1510              : 
    1511              : static tree
    1512     19709702 : get_representative_for (const pre_expr e, basic_block b = NULL)
    1513              : {
    1514     19709702 :   tree name, valnum = NULL_TREE;
    1515     19709702 :   unsigned int value_id = get_expr_value_id (e);
    1516              : 
    1517     19709702 :   switch (e->kind)
    1518              :     {
    1519      9039983 :     case NAME:
    1520      9039983 :       return PRE_EXPR_NAME (e);
    1521      1939191 :     case CONSTANT:
    1522      1939191 :       return PRE_EXPR_CONSTANT (e);
    1523      8730528 :     case NARY:
    1524      8730528 :     case REFERENCE:
    1525      8730528 :       {
    1526              :         /* Go through all of the expressions representing this value
    1527              :            and pick out an SSA_NAME.  */
    1528      8730528 :         unsigned int i;
    1529      8730528 :         bitmap_iterator bi;
    1530      8730528 :         bitmap exprs = value_expressions[value_id];
    1531     22441535 :         EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi)
    1532              :           {
    1533     18317894 :             pre_expr rep = expression_for_id (i);
    1534     18317894 :             if (rep->kind == NAME)
    1535              :               {
    1536      8298584 :                 tree name = PRE_EXPR_NAME (rep);
    1537      8298584 :                 valnum = VN_INFO (name)->valnum;
    1538      8298584 :                 gimple *def = SSA_NAME_DEF_STMT (name);
    1539              :                 /* We have to return either a new representative or one
    1540              :                    that can be used for expression simplification and thus
    1541              :                    is available in B.  */
    1542      8298584 :                 if (! b
    1543      7972390 :                     || gimple_nop_p (def)
    1544     12257615 :                     || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
    1545      4606887 :                   return name;
    1546              :               }
    1547     10019310 :             else if (rep->kind == CONSTANT)
    1548            0 :               return PRE_EXPR_CONSTANT (rep);
    1549              :           }
    1550              :       }
    1551      4123641 :       break;
    1552              :     }
    1553              : 
    1554              :   /* If we reached here we couldn't find an SSA_NAME.  This can
    1555              :      happen when we've discovered a value that has never appeared in
    1556              :      the program as set to an SSA_NAME, as the result of phi translation.
    1557              :      Create one here.
    1558              :      ???  We should be able to re-use this when we insert the statement
    1559              :      to compute it.  */
    1560      4123641 :   name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
    1561      4123641 :   vn_ssa_aux_t vn_info = VN_INFO (name);
    1562      4123641 :   vn_info->value_id = value_id;
    1563      4123641 :   vn_info->valnum = valnum ? valnum : name;
    1564      4123641 :   vn_info->visited = true;
    1565              :   /* ???  For now mark this SSA name for release by VN.  */
    1566      4123641 :   vn_info->needs_insertion = true;
    1567      4123641 :   add_to_value (value_id, get_or_alloc_expr_for_name (name));
    1568      4123641 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1569              :     {
    1570           47 :       fprintf (dump_file, "Created SSA_NAME representative ");
    1571           47 :       print_generic_expr (dump_file, name);
    1572           47 :       fprintf (dump_file, " for expression:");
    1573           47 :       print_pre_expr (dump_file, e);
    1574           47 :       fprintf (dump_file, " (%04d)\n", value_id);
    1575              :     }
    1576              : 
    1577              :   return name;
    1578              : }
    1579              : 
    1580              : 
    1581              : static pre_expr
    1582              : phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge);
    1583              : 
    1584              : /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
    1585              :    the phis in PRED.  Return NULL if we can't find a leader for each part
    1586              :    of the translated expression.  */
    1587              : 
    1588              : static pre_expr
    1589     49557360 : phi_translate_1 (bitmap_set_t dest,
    1590              :                  pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e)
    1591              : {
    1592     49557360 :   basic_block pred = e->src;
    1593     49557360 :   basic_block phiblock = e->dest;
    1594     49557360 :   location_t expr_loc = expr->loc;
    1595     49557360 :   switch (expr->kind)
    1596              :     {
    1597     18763321 :     case NARY:
    1598     18763321 :       {
    1599     18763321 :         unsigned int i;
    1600     18763321 :         bool changed = false;
    1601     18763321 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    1602     18763321 :         vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,
    1603              :                                            sizeof_vn_nary_op (nary->length));
    1604     18763321 :         memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
    1605              : 
    1606     44396106 :         for (i = 0; i < newnary->length; i++)
    1607              :           {
    1608     29189630 :             if (TREE_CODE (newnary->op[i]) != SSA_NAME)
    1609      9076107 :               continue;
    1610              :             else
    1611              :               {
    1612     20113523 :                 pre_expr leader, result;
    1613     20113523 :                 unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
    1614     20113523 :                 leader = find_leader_in_sets (op_val_id, set1, set2);
    1615     20113523 :                 result = phi_translate (dest, leader, set1, set2, e);
    1616     20113523 :                 if (result)
    1617              :                   /* If op has a leader in the sets we translate make
    1618              :                      sure to use the value of the translated expression.
    1619              :                      We might need a new representative for that.  */
    1620     16556678 :                   newnary->op[i] = get_representative_for (result, pred);
    1621              :                 else if (!result)
    1622              :                   return NULL;
    1623              : 
    1624     16556678 :                 changed |= newnary->op[i] != nary->op[i];
    1625              :               }
    1626              :           }
    1627     15206476 :         if (changed)
    1628              :           {
    1629      7689644 :             unsigned int new_val_id;
    1630              : 
    1631      7689644 :             vn_nary_op_t saved_newnary
    1632      7689644 :               = XALLOCAVAR (struct vn_nary_op_s,
    1633              :                             sizeof_vn_nary_op (newnary->length));
    1634      7689644 :             memcpy (saved_newnary, newnary,
    1635              :                     sizeof_vn_nary_op (newnary->length));
    1636              : 
    1637              :             /* Try to simplify the new NARY.  */
    1638      7689644 :             tree res = vn_nary_simplify (newnary);
    1639      7689644 :             if (res)
    1640              :               {
    1641      2455439 :                 if (is_gimple_min_invariant (res))
    1642      1267940 :                   return get_or_alloc_expr_for_constant (res);
    1643              : 
    1644              :                 /* For non-CONSTANTs we have to make sure we can eventually
    1645              :                    insert the expression.  Which means we need to have a
    1646              :                    leader for it.  */
    1647      1187499 :                 gcc_assert (TREE_CODE (res) == SSA_NAME);
    1648              : 
    1649              :                 /* Do not allow simplifications to non-constants over
    1650              :                    backedges as this will likely result in a loop PHI node
    1651              :                    to be inserted and increased register pressure.
    1652              :                    See PR77498 - this avoids doing predcoms work in
    1653              :                    a less efficient way.  */
    1654      1187499 :                 if (e->flags & EDGE_DFS_BACK)
    1655              :                   ;
    1656              :                 else
    1657              :                   {
    1658      1106317 :                     unsigned value_id = VN_INFO (res)->value_id;
    1659              :                     /* We want a leader in ANTIC_OUT or AVAIL_OUT here.
    1660              :                        dest has what we computed into ANTIC_OUT sofar
    1661              :                        so pick from that - since topological sorting
    1662              :                        by sorted_array_from_bitmap_set isn't perfect
    1663              :                        we may lose some cases here.  */
    1664      2212634 :                     pre_expr constant = find_leader_in_sets (value_id, dest,
    1665      1106317 :                                                              AVAIL_OUT (pred));
    1666      1106317 :                     if (constant)
    1667              :                       {
    1668       337857 :                         if (dump_file && (dump_flags & TDF_DETAILS))
    1669              :                           {
    1670            7 :                             fprintf (dump_file, "simplifying ");
    1671            7 :                             print_pre_expr (dump_file, expr);
    1672            7 :                             fprintf (dump_file, " translated %d -> %d to ",
    1673              :                                      phiblock->index, pred->index);
    1674            7 :                             PRE_EXPR_NARY (expr) = newnary;
    1675            7 :                             print_pre_expr (dump_file, expr);
    1676            7 :                             PRE_EXPR_NARY (expr) = nary;
    1677            7 :                             fprintf (dump_file, " to ");
    1678            7 :                             print_pre_expr (dump_file, constant);
    1679            7 :                             fprintf (dump_file, "\n");
    1680              :                           }
    1681              :                         return constant;
    1682              :                       }
    1683              :                   }
    1684              :                 /* Restore the unsimplified newnary, it was simplified
    1685              :                    to a NAME that we do not want (not as NARY anyway).  */
    1686       849642 :                 memcpy (newnary, saved_newnary,
    1687       849642 :                         sizeof_vn_nary_op (saved_newnary->length));
    1688              :               }
    1689              : 
    1690     12167694 :             tree result = vn_nary_op_lookup_pieces (newnary->length,
    1691      6083847 :                                                     newnary->opcode,
    1692              :                                                     newnary->type,
    1693              :                                                     &newnary->op[0],
    1694              :                                                     &nary);
    1695      6083847 :             if (result && is_gimple_min_invariant (result))
    1696            0 :               return get_or_alloc_expr_for_constant (result);
    1697              : 
    1698      6083847 :             if (!nary || nary->predicated_values)
    1699              :               new_val_id = 0;
    1700              :             else
    1701       812416 :               new_val_id = nary->value_id;
    1702      6083847 :             expr = get_or_alloc_expr_for_nary (newnary, new_val_id, expr_loc);
    1703      6083847 :             add_to_value (get_expr_value_id (expr), expr);
    1704              :           }
    1705              :         return expr;
    1706              :       }
    1707      5029472 :       break;
    1708              : 
    1709      5029472 :     case REFERENCE:
    1710      5029472 :       {
    1711      5029472 :         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    1712      5029472 :         vec<vn_reference_op_s> operands = ref->operands;
    1713      5029472 :         tree vuse = ref->vuse;
    1714      5029472 :         tree newvuse = vuse;
    1715      5029472 :         vec<vn_reference_op_s> newoperands = vNULL;
    1716      5029472 :         bool changed = false, same_valid = true;
    1717      5029472 :         unsigned int i, n;
    1718      5029472 :         vn_reference_op_t operand;
    1719      5029472 :         vn_reference_t newref;
    1720              : 
    1721     19093400 :         for (i = 0; operands.iterate (i, &operand); i++)
    1722              :           {
    1723     14442981 :             pre_expr opresult;
    1724     14442981 :             pre_expr leader;
    1725     14442981 :             tree op[3];
    1726     14442981 :             tree type = operand->type;
    1727     14442981 :             vn_reference_op_s newop = *operand;
    1728     14442981 :             op[0] = operand->op0;
    1729     14442981 :             op[1] = operand->op1;
    1730     14442981 :             op[2] = operand->op2;
    1731     56634837 :             for (n = 0; n < 3; ++n)
    1732              :               {
    1733     42570909 :                 unsigned int op_val_id;
    1734     42570909 :                 if (!op[n])
    1735     25772680 :                   continue;
    1736     16798229 :                 if (TREE_CODE (op[n]) != SSA_NAME)
    1737              :                   {
    1738              :                     /* We can't possibly insert these.  */
    1739     13266152 :                     if (n != 0
    1740     13266152 :                         && !is_gimple_min_invariant (op[n]))
    1741              :                       break;
    1742     13266152 :                     continue;
    1743              :                   }
    1744      3532077 :                 op_val_id = VN_INFO (op[n])->value_id;
    1745      3532077 :                 leader = find_leader_in_sets (op_val_id, set1, set2);
    1746      3532077 :                 opresult = phi_translate (dest, leader, set1, set2, e);
    1747      3532077 :                 if (opresult)
    1748              :                   {
    1749      3153024 :                     tree name = get_representative_for (opresult);
    1750      3153024 :                     changed |= name != op[n];
    1751      3153024 :                     op[n] = name;
    1752              :                   }
    1753              :                 else if (!opresult)
    1754              :                   break;
    1755              :               }
    1756     14442981 :             if (n != 3)
    1757              :               {
    1758       379053 :                 newoperands.release ();
    1759       379053 :                 return NULL;
    1760              :               }
    1761              :             /* When we translate a MEM_REF across a backedge and we have
    1762              :                restrict info that's not from our functions parameters
    1763              :                we have to remap it since we now may deal with a different
    1764              :                instance where the dependence info is no longer valid.
    1765              :                See PR102970.  Note instead of keeping a remapping table
    1766              :                per backedge we simply throw away restrict info.  */
    1767     14063928 :             if ((newop.opcode == MEM_REF
    1768     14063928 :                  || newop.opcode == TARGET_MEM_REF)
    1769      4757224 :                 && newop.clique > 1
    1770       154143 :                 && (e->flags & EDGE_DFS_BACK))
    1771              :               {
    1772              :                 newop.clique = 0;
    1773              :                 newop.base = 0;
    1774              :                 changed = true;
    1775              :               }
    1776     14042897 :             if (!changed)
    1777     11506640 :               continue;
    1778      2557288 :             if (!newoperands.exists ())
    1779      1315528 :               newoperands = operands.copy ();
    1780              :             /* We may have changed from an SSA_NAME to a constant */
    1781      2557288 :             if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
    1782              :               newop.opcode = TREE_CODE (op[0]);
    1783      2557288 :             newop.type = type;
    1784      2557288 :             newop.op0 = op[0];
    1785      2557288 :             newop.op1 = op[1];
    1786      2557288 :             newop.op2 = op[2];
    1787      2557288 :             newoperands[i] = newop;
    1788              :           }
    1789      9300838 :         gcc_checking_assert (i == operands.length ());
    1790              : 
    1791      4650419 :         if (vuse)
    1792              :           {
    1793     11047065 :             newvuse = translate_vuse_through_block (newoperands.exists ()
    1794      4537265 :                                                     ? newoperands : operands,
    1795              :                                                     ref->set, ref->base_set,
    1796              :                                                     ref->type, vuse, e,
    1797              :                                                     changed
    1798              :                                                     ? NULL : &same_valid);
    1799      4537265 :             if (newvuse == NULL_TREE)
    1800              :               {
    1801            0 :                 newoperands.release ();
    1802            0 :                 return NULL;
    1803              :               }
    1804              :           }
    1805              : 
    1806      4650419 :         if (changed || newvuse != vuse)
    1807              :           {
    1808      3281821 :             unsigned int new_val_id;
    1809              : 
    1810      5249625 :             tree result = vn_reference_lookup_pieces (newvuse, ref->set,
    1811              :                                                       ref->base_set,
    1812              :                                                       ref->type,
    1813      3281821 :                                                       newoperands.exists ()
    1814      3281821 :                                                       ? newoperands : operands,
    1815              :                                                       &newref, VN_WALK);
    1816              : 
    1817              :             /* We can always insert constants, so if we have a partial
    1818              :                redundant constant load of another type try to translate it
    1819              :                to a constant of appropriate type.  */
    1820      3281821 :             if (result && is_gimple_min_invariant (result))
    1821              :               {
    1822        78639 :                 tree tem = result;
    1823        78639 :                 if (!useless_type_conversion_p (ref->type, TREE_TYPE (result)))
    1824              :                   {
    1825           85 :                     tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result);
    1826           85 :                     if (tem && !is_gimple_min_invariant (tem))
    1827              :                       tem = NULL_TREE;
    1828              :                   }
    1829        78639 :                 if (tem)
    1830              :                   {
    1831        78639 :                     newoperands.release ();
    1832        78639 :                     return get_or_alloc_expr_for_constant (tem);
    1833              :                   }
    1834              :               }
    1835              : 
    1836              :             /* If we'd have to convert things we would need to validate
    1837              :                if we can insert the translated expression.  So fail
    1838              :                here for now - we cannot insert an alias with a different
    1839              :                type in the VN tables either, as that would assert.  */
    1840      3203182 :             if (result
    1841      3203182 :                 && !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
    1842              :               {
    1843         1012 :                 newoperands.release ();
    1844         1012 :                 return NULL;
    1845              :               }
    1846      2638130 :             else if (!result && newref
    1847      3202170 :                      && !useless_type_conversion_p (ref->type, newref->type))
    1848              :               {
    1849            0 :                 newoperands.release ();
    1850            0 :                 return NULL;
    1851              :               }
    1852              : 
    1853      3202170 :             if (newref)
    1854              :               {
    1855       564040 :                 new_val_id = newref->value_id;
    1856       564040 :                 newvuse = newref->vuse;
    1857              :               }
    1858              :             else
    1859              :               {
    1860      2638130 :                 if (changed || !same_valid)
    1861              :                   new_val_id = 0;
    1862              :                 else
    1863       127488 :                   new_val_id = ref->value_id;
    1864              :               }
    1865      3202170 :             newref = XALLOCAVAR (struct vn_reference_s,
    1866              :                                  sizeof (vn_reference_s));
    1867      3202170 :             memcpy (newref, ref, sizeof (vn_reference_s));
    1868      3202170 :             newref->next = NULL;
    1869      3202170 :             newref->value_id = new_val_id;
    1870      3202170 :             newref->vuse = newvuse;
    1871      6404340 :             newref->operands
    1872      3202170 :               = newoperands.exists () ? newoperands : operands.copy ();
    1873      3202170 :             newoperands = vNULL;
    1874      3202170 :             newref->type = ref->type;
    1875      3202170 :             newref->result = result;
    1876      3202170 :             newref->hashcode = vn_reference_compute_hash (newref);
    1877      3202170 :             expr = get_or_alloc_expr_for_reference (newref, new_val_id,
    1878              :                                                     expr_loc, true);
    1879      3202170 :             add_to_value (get_expr_value_id (expr), expr);
    1880              :           }
    1881      4570768 :         newoperands.release ();
    1882      4570768 :         return expr;
    1883              :       }
    1884     25764567 :       break;
    1885              : 
    1886     25764567 :     case NAME:
    1887     25764567 :       {
    1888     25764567 :         tree name = PRE_EXPR_NAME (expr);
    1889     25764567 :         gimple *def_stmt = SSA_NAME_DEF_STMT (name);
    1890              :         /* If the SSA name is defined by a PHI node in this block,
    1891              :            translate it.  */
    1892     25764567 :         if (gimple_code (def_stmt) == GIMPLE_PHI
    1893     25764567 :             && gimple_bb (def_stmt) == phiblock)
    1894              :           {
    1895      8015012 :             tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
    1896              : 
    1897              :             /* Handle constant. */
    1898      8015012 :             if (is_gimple_min_invariant (def))
    1899      2359197 :               return get_or_alloc_expr_for_constant (def);
    1900              : 
    1901      5655815 :             return get_or_alloc_expr_for_name (def);
    1902              :           }
    1903              :         /* Otherwise return it unchanged - it will get removed if its
    1904              :            value is not available in PREDs AVAIL_OUT set of expressions
    1905              :            by the subtraction of TMP_GEN.  */
    1906              :         return expr;
    1907              :       }
    1908              : 
    1909            0 :     default:
    1910            0 :       gcc_unreachable ();
    1911              :     }
    1912              : }
    1913              : 
    1914              : /* Wrapper around phi_translate_1 providing caching functionality.  */
    1915              : 
    1916              : static pre_expr
    1917     91044972 : phi_translate (bitmap_set_t dest, pre_expr expr,
    1918              :                bitmap_set_t set1, bitmap_set_t set2, edge e)
    1919              : {
    1920     91044972 :   expr_pred_trans_t slot = NULL;
    1921     91044972 :   pre_expr phitrans;
    1922              : 
    1923     91044972 :   if (!expr)
    1924              :     return NULL;
    1925              : 
    1926              :   /* Constants contain no values that need translation.  */
    1927     89103988 :   if (expr->kind == CONSTANT)
    1928              :     return expr;
    1929              : 
    1930     89103764 :   if (value_id_constant_p (get_expr_value_id (expr)))
    1931              :     return expr;
    1932              : 
    1933              :   /* Don't add translations of NAMEs as those are cheap to translate.  */
    1934     89103764 :   if (expr->kind != NAME)
    1935              :     {
    1936     63339197 :       if (phi_trans_add (&slot, expr, e->src))
    1937     39546404 :         return slot->v == 0 ? NULL : expression_for_id (slot->v);
    1938              :       /* Store NULL for the value we want to return in the case of
    1939              :          recursing.  */
    1940     23792793 :       slot->v = 0;
    1941              :     }
    1942              : 
    1943              :   /* Translate.  */
    1944     49557360 :   basic_block saved_valueize_bb = vn_context_bb;
    1945     49557360 :   vn_context_bb = e->src;
    1946     49557360 :   phitrans = phi_translate_1 (dest, expr, set1, set2, e);
    1947     49557360 :   vn_context_bb = saved_valueize_bb;
    1948              : 
    1949     49557360 :   if (slot)
    1950              :     {
    1951              :       /* We may have reallocated.  */
    1952     23792793 :       phi_trans_add (&slot, expr, e->src);
    1953     23792793 :       if (phitrans)
    1954     19855883 :         slot->v = get_expression_id (phitrans);
    1955              :       else
    1956              :         /* Remove failed translations again, they cause insert
    1957              :            iteration to not pick up new opportunities reliably.  */
    1958      3936910 :         PHI_TRANS_TABLE (e->src)->clear_slot (slot);
    1959              :     }
    1960              : 
    1961              :   return phitrans;
    1962              : }
    1963              : 
    1964              : 
    1965              : /* For each expression in SET, translate the values through phi nodes
    1966              :    in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
    1967              :    expressions in DEST.  */
    1968              : 
    1969              : static void
    1970     20809633 : phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e)
    1971              : {
    1972     20809633 :   bitmap_iterator bi;
    1973     20809633 :   unsigned int i;
    1974              : 
    1975     20809633 :   if (gimple_seq_empty_p (phi_nodes (e->dest)))
    1976              :     {
    1977     13891425 :       bitmap_set_copy (dest, set);
    1978     13891425 :       return;
    1979              :     }
    1980              : 
    1981              :   /* Allocate the phi-translation cache where we have an idea about
    1982              :      its size.  hash-table implementation internals tell us that
    1983              :      allocating the table to fit twice the number of elements will
    1984              :      make sure we do not usually re-allocate.  */
    1985      6918208 :   if (!PHI_TRANS_TABLE (e->src))
    1986      6031483 :     PHI_TRANS_TABLE (e->src) = new hash_table<expr_pred_trans_d>
    1987      6031483 :                                    (2 * bitmap_count_bits (&set->expressions));
    1988     45956234 :   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
    1989              :     {
    1990     39038026 :       pre_expr expr = expression_for_id (i);
    1991     39038026 :       pre_expr translated = phi_translate (dest, expr, set, NULL, e);
    1992     39038026 :       if (!translated)
    1993      1941202 :         continue;
    1994              : 
    1995     37096824 :       bitmap_insert_into_set (dest, translated);
    1996              :     }
    1997              : }
    1998              : 
    1999              : /* Find the leader for a value (i.e., the name representing that
    2000              :    value) in a given set, and return it.  Return NULL if no leader
    2001              :    is found.  */
    2002              : 
    2003              : static pre_expr
    2004     57506990 : bitmap_find_leader (bitmap_set_t set, unsigned int val)
    2005              : {
    2006     57506990 :   if (value_id_constant_p (val))
    2007      1803642 :     return constant_value_expressions[-val];
    2008              : 
    2009     55703348 :   if (bitmap_set_contains_value (set, val))
    2010              :     {
    2011              :       /* Rather than walk the entire bitmap of expressions, and see
    2012              :          whether any of them has the value we are looking for, we look
    2013              :          at the reverse mapping, which tells us the set of expressions
    2014              :          that have a given value (IE value->expressions with that
    2015              :          value) and see if any of those expressions are in our set.
    2016              :          The number of expressions per value is usually significantly
    2017              :          less than the number of expressions in the set.  In fact, for
    2018              :          large testcases, doing it this way is roughly 5-10x faster
    2019              :          than walking the bitmap.
    2020              :          If this is somehow a significant lose for some cases, we can
    2021              :          choose which set to walk based on which set is smaller.  */
    2022     26067019 :       unsigned int i;
    2023     26067019 :       bitmap_iterator bi;
    2024     26067019 :       bitmap exprset = value_expressions[val];
    2025              : 
    2026     26067019 :       if (!exprset->first->next)
    2027     33093755 :         EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
    2028     30745501 :           if (bitmap_bit_p (&set->expressions, i))
    2029     23626601 :             return expression_for_id (i);
    2030              : 
    2031      6325568 :       EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
    2032      3885150 :         return expression_for_id (i);
    2033              :     }
    2034              :   return NULL;
    2035              : }
    2036              : 
    2037              : /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
    2038              :    BLOCK by seeing if it is not killed in the block.  Note that we are
    2039              :    only determining whether there is a store that kills it.  Because
    2040              :    of the order in which clean iterates over values, we are guaranteed
    2041              :    that altered operands will have caused us to be eliminated from the
    2042              :    ANTIC_IN set already.  */
    2043              : 
    2044              : static bool
    2045      1666916 : value_dies_in_block_x (pre_expr expr, basic_block block)
    2046              : {
    2047      1666916 :   tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
    2048      1666916 :   vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
    2049      1666916 :   gimple *def;
    2050      1666916 :   gimple_stmt_iterator gsi;
    2051      1666916 :   unsigned id = get_expression_id (expr);
    2052      1666916 :   bool res = false;
    2053      1666916 :   ao_ref ref;
    2054              : 
    2055      1666916 :   if (!vuse)
    2056              :     return false;
    2057              : 
    2058              :   /* Lookup a previously calculated result.  */
    2059      1666916 :   if (EXPR_DIES (block)
    2060      1666916 :       && bitmap_bit_p (EXPR_DIES (block), id * 2))
    2061       138405 :     return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
    2062              : 
    2063              :   /* A memory expression {e, VUSE} dies in the block if there is a
    2064              :      statement that may clobber e.  If, starting statement walk from the
    2065              :      top of the basic block, a statement uses VUSE there can be no kill
    2066              :      in between that use and the original statement that loaded {e, VUSE},
    2067              :      so we can stop walking.  */
    2068      1528511 :   ref.base = NULL_TREE;
    2069     13566358 :   for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
    2070              :     {
    2071     11554079 :       tree def_vuse, def_vdef;
    2072     11554079 :       def = gsi_stmt (gsi);
    2073     11554079 :       def_vuse = gimple_vuse (def);
    2074     11554079 :       def_vdef = gimple_vdef (def);
    2075              : 
    2076              :       /* Not a memory statement.  */
    2077     11554079 :       if (!def_vuse)
    2078      8238440 :         continue;
    2079              : 
    2080              :       /* Not a may-def.  */
    2081      3315639 :       if (!def_vdef)
    2082              :         {
    2083              :           /* A load with the same VUSE, we're done.  */
    2084       962066 :           if (def_vuse == vuse)
    2085              :             break;
    2086              : 
    2087       670974 :           continue;
    2088              :         }
    2089              : 
    2090              :       /* Init ref only if we really need it.  */
    2091      2353573 :       if (ref.base == NULL_TREE
    2092      3504698 :           && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->base_set,
    2093      1151125 :                                              refx->type, refx->operands))
    2094              :         {
    2095              :           res = true;
    2096              :           break;
    2097              :         }
    2098              :       /* If the statement may clobber expr, it dies.  */
    2099      2318425 :       if (stmt_may_clobber_ref_p_1 (def, &ref))
    2100              :         {
    2101              :           res = true;
    2102              :           break;
    2103              :         }
    2104              :     }
    2105              : 
    2106              :   /* Remember the result.  */
    2107      1528511 :   if (!EXPR_DIES (block))
    2108       719807 :     EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
    2109      1528511 :   bitmap_set_bit (EXPR_DIES (block), id * 2);
    2110      1528511 :   if (res)
    2111       753651 :     bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
    2112              : 
    2113              :   return res;
    2114              : }
    2115              : 
    2116              : 
    2117              : /* Determine if OP is valid in SET1 U SET2, which it is when the union
    2118              :    contains its value-id.  */
    2119              : 
    2120              : static bool
    2121    264963287 : op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
    2122              : {
    2123    264963287 :   if (op && TREE_CODE (op) == SSA_NAME)
    2124              :     {
    2125     71881377 :       unsigned int value_id = VN_INFO (op)->value_id;
    2126    143760413 :       if (!(bitmap_set_contains_value (set1, value_id)
    2127      2261974 :             || (set2 && bitmap_set_contains_value  (set2, value_id))))
    2128      2236341 :         return false;
    2129              :     }
    2130              :   return true;
    2131              : }
    2132              : 
    2133              : /* Determine if the expression EXPR is valid in SET1 U SET2.
    2134              :    ONLY SET2 CAN BE NULL.
    2135              :    This means that we have a leader for each part of the expression
    2136              :    (if it consists of values), or the expression is an SSA_NAME.
    2137              :    For loads/calls, we also see if the vuse is killed in this block.  */
    2138              : 
    2139              : static bool
    2140    125544062 : valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
    2141              : {
    2142    125544062 :   switch (expr->kind)
    2143              :     {
    2144              :     case NAME:
    2145              :       /* By construction all NAMEs are available.  Non-available
    2146              :          NAMEs are removed by subtracting TMP_GEN from the sets.  */
    2147              :       return true;
    2148     54455822 :     case NARY:
    2149     54455822 :       {
    2150     54455822 :         unsigned int i;
    2151     54455822 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    2152    140665775 :         for (i = 0; i < nary->length; i++)
    2153     88302593 :           if (!op_valid_in_sets (set1, set2, nary->op[i]))
    2154              :             return false;
    2155              :         return true;
    2156              :       }
    2157     20203470 :       break;
    2158     20203470 :     case REFERENCE:
    2159     20203470 :       {
    2160     20203470 :         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    2161     20203470 :         vn_reference_op_t vro;
    2162     20203470 :         unsigned int i;
    2163              : 
    2164     79042445 :         FOR_EACH_VEC_ELT (ref->operands, i, vro)
    2165              :           {
    2166     58982676 :             if (!op_valid_in_sets (set1, set2, vro->op0)
    2167     58839009 :                 || !op_valid_in_sets (set1, set2, vro->op1)
    2168    117821685 :                 || !op_valid_in_sets (set1, set2, vro->op2))
    2169              :               return false;
    2170              :           }
    2171              :         return true;
    2172              :       }
    2173            0 :     default:
    2174            0 :       gcc_unreachable ();
    2175              :     }
    2176              : }
    2177              : 
    2178              : /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
    2179              :    This means expressions that are made up of values we have no leaders for
    2180              :    in SET1 or SET2.  */
    2181              : 
    2182              : static void
    2183     14697292 : clean (bitmap_set_t set1, bitmap_set_t set2 = NULL)
    2184              : {
    2185     14697292 :   vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1, false);
    2186     15666546 :   bool changed;
    2187              : 
    2188     15666546 :   do
    2189              :     {
    2190     15666546 :       unsigned j = 0;
    2191     15666546 :       changed = false;
    2192     82212739 :       for (unsigned i = 0; i < exprs.length (); ++i)
    2193              :         {
    2194     66546193 :           pre_expr expr = exprs[i];
    2195     66546193 :           if (!valid_in_sets (set1, set2, expr))
    2196              :             {
    2197      2236331 :               unsigned int val = get_expr_value_id (expr);
    2198      2236331 :               bitmap_clear_bit (&set1->expressions, get_expression_id (expr));
    2199              :               /* We are entered with possibly multiple expressions for a value
    2200              :                  so before removing a value from the set see if there's an
    2201              :                  expression for it left.  */
    2202      2236331 :               if (! bitmap_find_leader (set1, val))
    2203              :                 {
    2204      2225402 :                   bitmap_clear_bit (&set1->values, val);
    2205      2225402 :                   changed = true;
    2206              :                 }
    2207              :             }
    2208              :           else
    2209              :             {
    2210     64309862 :               exprs[j] = expr;
    2211     64309862 :               ++j;
    2212              :             }
    2213              :         }
    2214     15666546 :       exprs.truncate (j);
    2215              :     }
    2216              :   /* As the value graph can have cycles we have to iterate here.  */
    2217              :   while (changed);
    2218     14697292 :   exprs.release ();
    2219              : 
    2220     14697292 :   if (flag_checking)
    2221              :     {
    2222     14697105 :       unsigned j;
    2223     14697105 :       bitmap_iterator bi;
    2224     73469181 :       FOR_EACH_EXPR_ID_IN_SET (set1, j, bi)
    2225     58772076 :         gcc_assert (valid_in_sets (set1, set2, expression_for_id (j)));
    2226              :     }
    2227     14697292 : }
    2228              : 
    2229              : /* Clean the set of expressions that are no longer valid in SET because
    2230              :    they are clobbered in BLOCK or because they trap and may not be executed.
    2231              :    When CLEAN_TRAPS is true remove all possibly trapping expressions.  */
    2232              : 
    2233              : static void
    2234     17143759 : prune_clobbered_mems (bitmap_set_t set, basic_block block, bool clean_traps)
    2235              : {
    2236     17143759 :   bitmap_iterator bi;
    2237     17143759 :   unsigned i;
    2238     17143759 :   unsigned to_remove = -1U;
    2239     17143759 :   bool any_removed = false;
    2240              : 
    2241     75300720 :   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
    2242              :     {
    2243              :       /* Remove queued expr.  */
    2244     58156961 :       if (to_remove != -1U)
    2245              :         {
    2246       598715 :           bitmap_clear_bit (&set->expressions, to_remove);
    2247       598715 :           any_removed = true;
    2248       598715 :           to_remove = -1U;
    2249              :         }
    2250              : 
    2251     58156961 :       pre_expr expr = expression_for_id (i);
    2252     58156961 :       if (expr->kind == REFERENCE)
    2253              :         {
    2254      8181800 :           vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    2255      8181800 :           if (ref->vuse)
    2256              :             {
    2257      7429766 :               gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
    2258      7429766 :               if (!gimple_nop_p (def_stmt)
    2259              :                   /* If value-numbering provided a memory state for this
    2260              :                      that dominates BLOCK we're done, otherwise we have
    2261              :                      to check if the value dies in BLOCK.  */
    2262      9144686 :                   && !(gimple_bb (def_stmt) != block
    2263      3851290 :                        && dominated_by_p (CDI_DOMINATORS,
    2264      3851290 :                                           block, gimple_bb (def_stmt)))
    2265      9096682 :                   && value_dies_in_block_x (expr, block))
    2266              :                 to_remove = i;
    2267              :             }
    2268              :           /* If the REFERENCE may trap make sure the block does not contain
    2269              :              a possible exit point.
    2270              :              ???  This is overly conservative if we translate AVAIL_OUT
    2271              :              as the available expression might be after the exit point.  */
    2272      7507115 :           if ((BB_MAY_NOTRETURN (block) || clean_traps)
    2273      8435601 :               && vn_reference_may_trap (ref))
    2274              :             to_remove = i;
    2275              :         }
    2276     49975161 :       else if (expr->kind == NARY)
    2277              :         {
    2278     25313517 :           vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    2279              :           /* If the NARY may trap make sure the block does not contain
    2280              :              a possible exit point.
    2281              :              ???  This is overly conservative if we translate AVAIL_OUT
    2282              :              as the available expression might be after the exit point.  */
    2283     21118998 :           if ((BB_MAY_NOTRETURN (block) || clean_traps)
    2284     26190406 :               && vn_nary_may_trap (nary))
    2285              :             to_remove = i;
    2286              :         }
    2287              :     }
    2288              : 
    2289              :   /* Remove queued expr.  */
    2290     17143759 :   if (to_remove != -1U)
    2291              :     {
    2292       429162 :       bitmap_clear_bit (&set->expressions, to_remove);
    2293       429162 :       any_removed = true;
    2294              :     }
    2295              : 
    2296              :   /* Above we only removed expressions, now clean the set of values
    2297              :      which no longer have any corresponding expression.  We cannot
    2298              :      clear the value at the time we remove an expression since there
    2299              :      may be multiple expressions per value.
    2300              :      If we'd queue possibly to be removed values we could use
    2301              :      the bitmap_find_leader way to see if there's still an expression
    2302              :      for it.  For some ratio of to be removed values and number of
    2303              :      values/expressions in the set this might be faster than rebuilding
    2304              :      the value-set.
    2305              :      Note when there's a MAX solution on one edge (clean_traps) do not
    2306              :      prune values as we need to consider the resulting expression set MAX
    2307              :      as well.  This avoids a later growing ANTIC_IN value-set during
    2308              :      iteration, when the explicitly represented expression set grows. */
    2309     17143759 :   if (any_removed && !clean_traps)
    2310              :     {
    2311       491465 :       bitmap_clear (&set->values);
    2312      2803089 :       FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
    2313              :         {
    2314      2311624 :           pre_expr expr = expression_for_id (i);
    2315      2311624 :           unsigned int value_id = get_expr_value_id (expr);
    2316      2311624 :           bitmap_set_bit (&set->values, value_id);
    2317              :         }
    2318              :     }
    2319     17143759 : }
    2320              : 
    2321              : /* Compute the ANTIC set for BLOCK.
    2322              : 
    2323              :    If succs(BLOCK) > 1 then
    2324              :      ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
    2325              :    else if succs(BLOCK) == 1 then
    2326              :      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
    2327              : 
    2328              :    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
    2329              : 
    2330              :    Note that clean() is deferred until after the iteration.  */
    2331              : 
    2332              : static bool
    2333     15889963 : compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
    2334              : {
    2335     15889963 :   bitmap_set_t S, old, ANTIC_OUT;
    2336     15889963 :   edge e;
    2337     15889963 :   edge_iterator ei;
    2338              : 
    2339     15889963 :   bool was_visited = BB_VISITED (block);
    2340     15889963 :   bool changed = ! BB_VISITED (block);
    2341     15889963 :   bool any_max_on_edge = false;
    2342              : 
    2343     15889963 :   BB_VISITED (block) = 1;
    2344     15889963 :   old = ANTIC_OUT = S = NULL;
    2345              : 
    2346              :   /* If any edges from predecessors are abnormal, antic_in is empty,
    2347              :      so do nothing.  */
    2348     15889963 :   if (block_has_abnormal_pred_edge)
    2349         4619 :     goto maybe_dump_sets;
    2350              : 
    2351     15885344 :   old = ANTIC_IN (block);
    2352     15885344 :   ANTIC_OUT = bitmap_set_new ();
    2353              : 
    2354              :   /* If the block has no successors, ANTIC_OUT is empty.  */
    2355     15885344 :   if (EDGE_COUNT (block->succs) == 0)
    2356              :     ;
    2357              :   /* If we have one successor, we could have some phi nodes to
    2358              :      translate through.  */
    2359     15885344 :   else if (single_succ_p (block))
    2360              :     {
    2361     10143763 :       e = single_succ_edge (block);
    2362     10143763 :       gcc_assert (BB_VISITED (e->dest));
    2363     10143763 :       phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
    2364              :     }
    2365              :   /* If we have multiple successors, we take the intersection of all of
    2366              :      them.  Note that in the case of loop exit phi nodes, we may have
    2367              :      phis to translate through.  */
    2368              :   else
    2369              :     {
    2370      5741581 :       size_t i;
    2371      5741581 :       edge first = NULL;
    2372              : 
    2373      5741581 :       auto_vec<edge> worklist (EDGE_COUNT (block->succs));
    2374     17339023 :       FOR_EACH_EDGE (e, ei, block->succs)
    2375              :         {
    2376     11597442 :           if (!first
    2377      6223704 :               && BB_VISITED (e->dest))
    2378              :             first = e;
    2379      5855861 :           else if (BB_VISITED (e->dest))
    2380      5186239 :             worklist.quick_push (e);
    2381              :           else
    2382              :             {
    2383              :               /* Unvisited successors get their ANTIC_IN replaced by the
    2384              :                  maximal set to arrive at a maximum ANTIC_IN solution.
    2385              :                  We can ignore them in the intersection operation and thus
    2386              :                  need not explicitly represent that maximum solution.  */
    2387       669622 :               any_max_on_edge = true;
    2388       669622 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2389           18 :                 fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
    2390           18 :                          e->src->index, e->dest->index);
    2391              :             }
    2392              :         }
    2393              : 
    2394              :       /* Of multiple successors we have to have visited one already
    2395              :          which is guaranteed by iteration order.  */
    2396      5741581 :       gcc_assert (first != NULL);
    2397              : 
    2398      5741581 :       phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest), first);
    2399              : 
    2400              :       /* If we have multiple successors we need to intersect the ANTIC_OUT
    2401              :          sets.  For values that's a simple intersection but for
    2402              :          expressions it is a union.  Given we want to have a single
    2403              :          expression per value in our sets we have to canonicalize.
    2404              :          Avoid randomness and running into cycles like for PR82129 and
    2405              :          canonicalize the expression we choose to the one with the
    2406              :          lowest id.  This requires we actually compute the union first.  */
    2407     22410982 :       FOR_EACH_VEC_ELT (worklist, i, e)
    2408              :         {
    2409      5186239 :           if (!gimple_seq_empty_p (phi_nodes (e->dest)))
    2410              :             {
    2411         2237 :               bitmap_set_t tmp = bitmap_set_new ();
    2412         2237 :               phi_translate_set (tmp, ANTIC_IN (e->dest), e);
    2413         2237 :               bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
    2414         2237 :               bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
    2415         2237 :               bitmap_set_free (tmp);
    2416              :             }
    2417              :           else
    2418              :             {
    2419      5184002 :               bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
    2420      5184002 :               bitmap_ior_into (&ANTIC_OUT->expressions,
    2421      5184002 :                                &ANTIC_IN (e->dest)->expressions);
    2422              :             }
    2423              :         }
    2424     11483162 :       if (! worklist.is_empty ())
    2425              :         {
    2426              :           /* Prune expressions not in the value set.  */
    2427      5077219 :           bitmap_iterator bi;
    2428      5077219 :           unsigned int i;
    2429      5077219 :           unsigned int to_clear = -1U;
    2430     36802266 :           FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)
    2431              :             {
    2432     31725047 :               if (to_clear != -1U)
    2433              :                 {
    2434     16696992 :                   bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
    2435     16696992 :                   to_clear = -1U;
    2436              :                 }
    2437     31725047 :               pre_expr expr = expression_for_id (i);
    2438     31725047 :               unsigned int value_id = get_expr_value_id (expr);
    2439     31725047 :               if (!bitmap_bit_p (&ANTIC_OUT->values, value_id))
    2440     20448597 :                 to_clear = i;
    2441              :             }
    2442      5077219 :           if (to_clear != -1U)
    2443      3751605 :             bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
    2444              :         }
    2445      5741581 :     }
    2446              : 
    2447              :   /* Dump ANTIC_OUT before it's pruned.  */
    2448     15885344 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2449          151 :     print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
    2450              : 
    2451              :   /* Prune expressions that are clobbered in block and thus become
    2452              :      invalid if translated from ANTIC_OUT to ANTIC_IN.  */
    2453     15885344 :   prune_clobbered_mems (ANTIC_OUT, block, any_max_on_edge);
    2454              : 
    2455              :   /* Generate ANTIC_OUT - TMP_GEN.  Note when there's a MAX solution
    2456              :      on one edge do not prune values as we need to consider the resulting
    2457              :      expression set MAX as well.  This avoids a later growing ANTIC_IN
    2458              :      value-set during iteration, when the explicitly represented
    2459              :      expression set grows.  */
    2460     15885344 :   S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block),
    2461              :                                        any_max_on_edge);
    2462              : 
    2463              :   /* Start ANTIC_IN with EXP_GEN - TMP_GEN.  */
    2464     31770688 :   ANTIC_IN (block) = bitmap_set_subtract_expressions (EXP_GEN (block),
    2465     15885344 :                                                       TMP_GEN (block));
    2466              : 
    2467              :   /* Then union in the ANTIC_OUT - TMP_GEN values,
    2468              :      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
    2469     15885344 :   bitmap_ior_into (&ANTIC_IN (block)->values, &S->values);
    2470     15885344 :   bitmap_ior_into (&ANTIC_IN (block)->expressions, &S->expressions);
    2471              : 
    2472              :   /* clean (ANTIC_IN (block)) is deferred to after the iteration converged
    2473              :      because it can cause non-convergence, see for example PR81181.  */
    2474              : 
    2475     15885344 :   if (was_visited
    2476     15885344 :       && bitmap_and_into (&ANTIC_IN (block)->values, &old->values))
    2477              :     {
    2478         2100 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2479            0 :         fprintf (dump_file, "warning: intersecting with old ANTIC_IN "
    2480              :                  "shrinks the set\n");
    2481              :       /* Prune expressions not in the value set.  */
    2482         2100 :       bitmap_iterator bi;
    2483         2100 :       unsigned int i;
    2484         2100 :       unsigned int to_clear = -1U;
    2485        22354 :       FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi)
    2486              :         {
    2487        20254 :           if (to_clear != -1U)
    2488              :             {
    2489         1667 :               bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
    2490         1667 :               to_clear = -1U;
    2491              :             }
    2492        20254 :           pre_expr expr = expression_for_id (i);
    2493        20254 :           unsigned int value_id = get_expr_value_id (expr);
    2494        20254 :           if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id))
    2495         3180 :             to_clear = i;
    2496              :         }
    2497         2100 :       if (to_clear != -1U)
    2498         1513 :         bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
    2499              :     }
    2500              : 
    2501     15885344 :   if (!bitmap_set_equal (old, ANTIC_IN (block)))
    2502     10322972 :     changed = true;
    2503              : 
    2504      5562372 :  maybe_dump_sets:
    2505     15889963 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2506              :     {
    2507          151 :       if (changed)
    2508          129 :         fprintf (dump_file, "[changed] ");
    2509          151 :       print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
    2510              :                         block->index);
    2511              : 
    2512          151 :       if (S)
    2513          151 :         print_bitmap_set (dump_file, S, "S", block->index);
    2514              :     }
    2515     15889963 :   if (old)
    2516     15885344 :     bitmap_set_free (old);
    2517     15889963 :   if (S)
    2518     15885344 :     bitmap_set_free (S);
    2519     15889963 :   if (ANTIC_OUT)
    2520     15885344 :     bitmap_set_free (ANTIC_OUT);
    2521     15889963 :   return changed;
    2522              : }
    2523              : 
    2524              : /* Compute PARTIAL_ANTIC for BLOCK.
    2525              : 
    2526              :    If succs(BLOCK) > 1 then
    2527              :      PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
    2528              :      in ANTIC_OUT for all succ(BLOCK)
    2529              :    else if succs(BLOCK) == 1 then
    2530              :      PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
    2531              : 
    2532              :    PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
    2533              : 
    2534              : */
    2535              : static void
    2536      1259744 : compute_partial_antic_aux (basic_block block,
    2537              :                            bool block_has_abnormal_pred_edge)
    2538              : {
    2539      1259744 :   bitmap_set_t old_PA_IN;
    2540      1259744 :   bitmap_set_t PA_OUT;
    2541      1259744 :   edge e;
    2542      1259744 :   edge_iterator ei;
    2543      1259744 :   unsigned long max_pa = param_max_partial_antic_length;
    2544              : 
    2545      1259744 :   old_PA_IN = PA_OUT = NULL;
    2546              : 
    2547              :   /* If any edges from predecessors are abnormal, antic_in is empty,
    2548              :      so do nothing.  */
    2549      1259744 :   if (block_has_abnormal_pred_edge)
    2550          782 :     goto maybe_dump_sets;
    2551              : 
    2552              :   /* If there are too many partially anticipatable values in the
    2553              :      block, phi_translate_set can take an exponential time: stop
    2554              :      before the translation starts.  */
    2555      1258962 :   if (max_pa
    2556      1165315 :       && single_succ_p (block)
    2557      2047482 :       && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
    2558          547 :     goto maybe_dump_sets;
    2559              : 
    2560      1258415 :   old_PA_IN = PA_IN (block);
    2561      1258415 :   PA_OUT = bitmap_set_new ();
    2562              : 
    2563              :   /* If the block has no successors, ANTIC_OUT is empty.  */
    2564      1258415 :   if (EDGE_COUNT (block->succs) == 0)
    2565              :     ;
    2566              :   /* If we have one successor, we could have some phi nodes to
    2567              :      translate through.  Note that we can't phi translate across DFS
    2568              :      back edges in partial antic, because it uses a union operation on
    2569              :      the successors.  For recurrences like IV's, we will end up
    2570              :      generating a new value in the set on each go around (i + 3 (VH.1)
    2571              :      VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
    2572      1164770 :   else if (single_succ_p (block))
    2573              :     {
    2574       787975 :       e = single_succ_edge (block);
    2575       787975 :       if (!(e->flags & EDGE_DFS_BACK))
    2576       706475 :         phi_translate_set (PA_OUT, PA_IN (e->dest), e);
    2577              :     }
    2578              :   /* If we have multiple successors, we take the union of all of
    2579              :      them.  */
    2580              :   else
    2581              :     {
    2582       376795 :       size_t i;
    2583              : 
    2584       376795 :       auto_vec<edge> worklist (EDGE_COUNT (block->succs));
    2585      1136094 :       FOR_EACH_EDGE (e, ei, block->succs)
    2586              :         {
    2587       759299 :           if (e->flags & EDGE_DFS_BACK)
    2588          311 :             continue;
    2589       758988 :           worklist.quick_push (e);
    2590              :         }
    2591       376795 :       if (worklist.length () > 0)
    2592              :         {
    2593      1135783 :           FOR_EACH_VEC_ELT (worklist, i, e)
    2594              :             {
    2595       758988 :               unsigned int i;
    2596       758988 :               bitmap_iterator bi;
    2597              : 
    2598       758988 :               if (!gimple_seq_empty_p (phi_nodes (e->dest)))
    2599              :                 {
    2600          755 :                   bitmap_set_t antic_in = bitmap_set_new ();
    2601          755 :                   phi_translate_set (antic_in, ANTIC_IN (e->dest), e);
    2602         1530 :                   FOR_EACH_EXPR_ID_IN_SET (antic_in, i, bi)
    2603          775 :                     bitmap_value_insert_into_set (PA_OUT,
    2604              :                                                   expression_for_id (i));
    2605          755 :                   bitmap_set_free (antic_in);
    2606          755 :                   bitmap_set_t pa_in = bitmap_set_new ();
    2607          755 :                   phi_translate_set (pa_in, PA_IN (e->dest), e);
    2608          755 :                   FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
    2609            0 :                     bitmap_value_insert_into_set (PA_OUT,
    2610              :                                                   expression_for_id (i));
    2611          755 :                   bitmap_set_free (pa_in);
    2612              :                 }
    2613              :               else
    2614              :                 {
    2615      4914176 :                   FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi)
    2616      4155943 :                     bitmap_value_insert_into_set (PA_OUT,
    2617              :                                                   expression_for_id (i));
    2618      4872842 :                   FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi)
    2619      4114609 :                     bitmap_value_insert_into_set (PA_OUT,
    2620              :                                                   expression_for_id (i));
    2621              :                 }
    2622              :             }
    2623              :         }
    2624       376795 :     }
    2625              : 
    2626              :   /* Prune expressions that are clobbered in block and thus become
    2627              :      invalid if translated from PA_OUT to PA_IN.  */
    2628      1258415 :   prune_clobbered_mems (PA_OUT, block, false);
    2629              : 
    2630              :   /* PA_IN starts with PA_OUT - TMP_GEN.
    2631              :      Then we subtract things from ANTIC_IN.  */
    2632      1258415 :   PA_IN (block) = bitmap_set_subtract_expressions (PA_OUT, TMP_GEN (block));
    2633              : 
    2634              :   /* For partial antic, we want to put back in the phi results, since
    2635              :      we will properly avoid making them partially antic over backedges.  */
    2636      1258415 :   bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
    2637      1258415 :   bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
    2638              : 
    2639              :   /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
    2640      1258415 :   bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
    2641              : 
    2642      1258415 :   clean (PA_IN (block), ANTIC_IN (block));
    2643              : 
    2644      1259744 :  maybe_dump_sets:
    2645      1259744 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2646              :     {
    2647            0 :       if (PA_OUT)
    2648            0 :         print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
    2649              : 
    2650            0 :       print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
    2651              :     }
    2652      1259744 :   if (old_PA_IN)
    2653      1258415 :     bitmap_set_free (old_PA_IN);
    2654      1259744 :   if (PA_OUT)
    2655      1258415 :     bitmap_set_free (PA_OUT);
    2656      1259744 : }
    2657              : 
    2658              : /* Compute ANTIC and partial ANTIC sets.  */
    2659              : 
    2660              : static void
    2661       982963 : compute_antic (void)
    2662              : {
    2663       982963 :   bool changed = true;
    2664       982963 :   int num_iterations = 0;
    2665       982963 :   basic_block block;
    2666       982963 :   int i;
    2667       982963 :   edge_iterator ei;
    2668       982963 :   edge e;
    2669              : 
    2670              :   /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
    2671              :      We pre-build the map of blocks with incoming abnormal edges here.  */
    2672       982963 :   auto_sbitmap has_abnormal_preds (last_basic_block_for_fn (cfun));
    2673       982963 :   bitmap_clear (has_abnormal_preds);
    2674              : 
    2675     16387766 :   FOR_ALL_BB_FN (block, cfun)
    2676              :     {
    2677     15404803 :       BB_VISITED (block) = 0;
    2678              : 
    2679     34747700 :       FOR_EACH_EDGE (e, ei, block->preds)
    2680     19346468 :         if (e->flags & EDGE_ABNORMAL)
    2681              :           {
    2682         3571 :             bitmap_set_bit (has_abnormal_preds, block->index);
    2683         3571 :             break;
    2684              :           }
    2685              : 
    2686              :       /* While we are here, give empty ANTIC_IN sets to each block.  */
    2687     15404803 :       ANTIC_IN (block) = bitmap_set_new ();
    2688     15404803 :       if (do_partial_partial)
    2689      1259744 :         PA_IN (block) = bitmap_set_new ();
    2690              :     }
    2691              : 
    2692              :   /* At the exit block we anticipate nothing.  */
    2693       982963 :   BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
    2694              : 
    2695              :   /* For ANTIC computation we need a postorder that also guarantees that
    2696              :      a block with a single successor is visited after its successor.
    2697              :      RPO on the inverted CFG has this property.  */
    2698       982963 :   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
    2699       982963 :   int n = inverted_rev_post_order_compute (cfun, rpo);
    2700              : 
    2701       982963 :   auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
    2702       982963 :   bitmap_clear (worklist);
    2703      2844233 :   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
    2704      1861270 :     bitmap_set_bit (worklist, e->src->index);
    2705      3041675 :   while (changed)
    2706              :     {
    2707      2058712 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2708           35 :         fprintf (dump_file, "Starting iteration %d\n", num_iterations);
    2709              :       /* ???  We need to clear our PHI translation cache here as the
    2710              :          ANTIC sets shrink and we restrict valid translations to
    2711              :          those having operands with leaders in ANTIC.  Same below
    2712              :          for PA ANTIC computation.  */
    2713      2058712 :       num_iterations++;
    2714      2058712 :       changed = false;
    2715     38942309 :       for (i = 0; i < n; ++i)
    2716              :         {
    2717     36883597 :           if (bitmap_bit_p (worklist, rpo[i]))
    2718              :             {
    2719     15889963 :               basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
    2720     15889963 :               bitmap_clear_bit (worklist, block->index);
    2721     15889963 :               if (compute_antic_aux (block,
    2722     15889963 :                                      bitmap_bit_p (has_abnormal_preds,
    2723              :                                                    block->index)))
    2724              :                 {
    2725     33447361 :                   FOR_EACH_EDGE (e, ei, block->preds)
    2726     18405604 :                     bitmap_set_bit (worklist, e->src->index);
    2727              :                   changed = true;
    2728              :                 }
    2729              :             }
    2730              :         }
    2731              :       /* Theoretically possible, but *highly* unlikely.  */
    2732      2058712 :       gcc_checking_assert (num_iterations < 500);
    2733              :     }
    2734              : 
    2735              :   /* We have to clean after the dataflow problem converged as cleaning
    2736              :      can cause non-convergence because it is based on expressions
    2737              :      rather than values.  */
    2738     14421840 :   FOR_EACH_BB_FN (block, cfun)
    2739     13438877 :     clean (ANTIC_IN (block));
    2740              : 
    2741       982963 :   statistics_histogram_event (cfun, "compute_antic iterations",
    2742              :                               num_iterations);
    2743              : 
    2744       982963 :   if (do_partial_partial)
    2745              :     {
    2746              :       /* For partial antic we ignore backedges and thus we do not need
    2747              :          to perform any iteration when we process blocks in rpo.  */
    2748      1353389 :       for (i = 0; i < n; ++i)
    2749              :         {
    2750      1259744 :           basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
    2751      1259744 :           compute_partial_antic_aux (block,
    2752      1259744 :                                      bitmap_bit_p (has_abnormal_preds,
    2753              :                                                    block->index));
    2754              :         }
    2755              :     }
    2756              : 
    2757       982963 :   free (rpo);
    2758       982963 : }
    2759              : 
    2760              : 
    2761              : /* Inserted expressions are placed onto this worklist, which is used
    2762              :    for performing quick dead code elimination of insertions we made
    2763              :    that didn't turn out to be necessary.   */
    2764              : static bitmap inserted_exprs;
    2765              : 
    2766              : /* The actual worker for create_component_ref_by_pieces.  */
    2767              : 
    2768              : static tree
    2769      1139059 : create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
    2770              :                                   unsigned int *operand, gimple_seq *stmts)
    2771              : {
    2772      1139059 :   vn_reference_op_t currop = &ref->operands[*operand];
    2773      1139059 :   tree genop;
    2774      1139059 :   ++*operand;
    2775      1139059 :   switch (currop->opcode)
    2776              :     {
    2777            0 :     case CALL_EXPR:
    2778            0 :       gcc_unreachable ();
    2779              : 
    2780       395161 :     case MEM_REF:
    2781       395161 :       {
    2782       395161 :         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
    2783              :                                                         stmts);
    2784       395161 :         if (!baseop)
    2785              :           return NULL_TREE;
    2786       395157 :         tree offset = currop->op0;
    2787       395157 :         if (TREE_CODE (baseop) == ADDR_EXPR
    2788       395157 :             && handled_component_p (TREE_OPERAND (baseop, 0)))
    2789              :           {
    2790           96 :             poly_int64 off;
    2791           96 :             tree base;
    2792           96 :             base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
    2793              :                                                   &off);
    2794           96 :             gcc_assert (base);
    2795           96 :             offset = int_const_binop (PLUS_EXPR, offset,
    2796           96 :                                       build_int_cst (TREE_TYPE (offset),
    2797              :                                                      off));
    2798           96 :             baseop = build_fold_addr_expr (base);
    2799              :           }
    2800       395157 :         genop = build2 (MEM_REF, currop->type, baseop, offset);
    2801       395157 :         MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
    2802       395157 :         MR_DEPENDENCE_BASE (genop) = currop->base;
    2803       395157 :         REF_REVERSE_STORAGE_ORDER (genop) = currop->reverse;
    2804       395157 :         return genop;
    2805              :       }
    2806              : 
    2807            0 :     case TARGET_MEM_REF:
    2808            0 :       {
    2809            0 :         tree genop0 = NULL_TREE, genop1 = NULL_TREE;
    2810            0 :         vn_reference_op_t nextop = &ref->operands[(*operand)++];
    2811            0 :         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
    2812              :                                                         stmts);
    2813            0 :         if (!baseop)
    2814              :           return NULL_TREE;
    2815            0 :         if (currop->op0)
    2816              :           {
    2817            0 :             genop0 = find_or_generate_expression (block, currop->op0, stmts);
    2818            0 :             if (!genop0)
    2819              :               return NULL_TREE;
    2820              :           }
    2821            0 :         if (nextop->op0)
    2822              :           {
    2823            0 :             genop1 = find_or_generate_expression (block, nextop->op0, stmts);
    2824            0 :             if (!genop1)
    2825              :               return NULL_TREE;
    2826              :           }
    2827            0 :         genop = build5 (TARGET_MEM_REF, currop->type,
    2828              :                         baseop, currop->op2, genop0, currop->op1, genop1);
    2829              : 
    2830            0 :         MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
    2831            0 :         MR_DEPENDENCE_BASE (genop) = currop->base;
    2832            0 :         return genop;
    2833              :       }
    2834              : 
    2835       241586 :     case ADDR_EXPR:
    2836       241586 :       if (currop->op0)
    2837              :         {
    2838       239250 :           gcc_assert (is_gimple_min_invariant (currop->op0));
    2839       239250 :           return currop->op0;
    2840              :         }
    2841              :       /* Fallthrough.  */
    2842         6733 :     case REALPART_EXPR:
    2843         6733 :     case IMAGPART_EXPR:
    2844         6733 :     case VIEW_CONVERT_EXPR:
    2845         6733 :       {
    2846         6733 :         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2847              :                                                         stmts);
    2848         6733 :         if (!genop0)
    2849              :           return NULL_TREE;
    2850         6733 :         return build1 (currop->opcode, currop->type, genop0);
    2851              :       }
    2852              : 
    2853            4 :     case WITH_SIZE_EXPR:
    2854            4 :       {
    2855            4 :         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2856              :                                                         stmts);
    2857            4 :         if (!genop0)
    2858              :           return NULL_TREE;
    2859            4 :         tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
    2860            4 :         if (!genop1)
    2861              :           return NULL_TREE;
    2862            4 :         return build2 (currop->opcode, currop->type, genop0, genop1);
    2863              :       }
    2864              : 
    2865         2874 :     case BIT_FIELD_REF:
    2866         2874 :       {
    2867         2874 :         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2868              :                                                         stmts);
    2869         2874 :         if (!genop0)
    2870              :           return NULL_TREE;
    2871         2874 :         tree op1 = currop->op0;
    2872         2874 :         tree op2 = currop->op1;
    2873         2874 :         tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
    2874         2874 :         REF_REVERSE_STORAGE_ORDER (t) = currop->reverse;
    2875         2874 :         return t;
    2876              :       }
    2877              : 
    2878              :       /* For array ref vn_reference_op's, operand 1 of the array ref
    2879              :          is op0 of the reference op and operand 3 of the array ref is
    2880              :          op1.  */
    2881        60959 :     case ARRAY_RANGE_REF:
    2882        60959 :     case ARRAY_REF:
    2883        60959 :       {
    2884        60959 :         tree genop0;
    2885        60959 :         tree genop1 = currop->op0;
    2886        60959 :         tree genop2 = currop->op1;
    2887        60959 :         tree genop3 = currop->op2;
    2888        60959 :         genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2889              :                                                    stmts);
    2890        60959 :         if (!genop0)
    2891              :           return NULL_TREE;
    2892        60959 :         genop1 = find_or_generate_expression (block, genop1, stmts);
    2893        60959 :         if (!genop1)
    2894              :           return NULL_TREE;
    2895        60959 :         if (genop2)
    2896              :           {
    2897        60959 :             tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
    2898              :             /* Drop zero minimum index if redundant.  */
    2899        60959 :             if (integer_zerop (genop2)
    2900        60959 :                 && (!domain_type
    2901        59918 :                     || integer_zerop (TYPE_MIN_VALUE (domain_type))))
    2902              :               genop2 = NULL_TREE;
    2903              :             else
    2904              :               {
    2905          614 :                 genop2 = find_or_generate_expression (block, genop2, stmts);
    2906          614 :                 if (!genop2)
    2907              :                   return NULL_TREE;
    2908              :               }
    2909              :           }
    2910        60959 :         if (genop3)
    2911              :           {
    2912        60959 :             tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
    2913              :             /* We can't always put a size in units of the element alignment
    2914              :                here as the element alignment may be not visible.  See
    2915              :                PR43783.  Simply drop the element size for constant
    2916              :                sizes.  */
    2917        60959 :             if ((TREE_CODE (genop3) == INTEGER_CST
    2918        60955 :                 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type)) == INTEGER_CST
    2919        60955 :                 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)),
    2920        60955 :                              (wi::to_offset (genop3) * vn_ref_op_align_unit (currop))))
    2921        60959 :               || (TREE_CODE (genop3) == EXACT_DIV_EXPR
    2922            0 :                 && TREE_CODE (TREE_OPERAND (genop3, 1)) == INTEGER_CST
    2923            0 :                 && operand_equal_p (TREE_OPERAND (genop3, 0), TYPE_SIZE_UNIT (elmt_type))
    2924            0 :                 && wi::eq_p (wi::to_offset (TREE_OPERAND (genop3, 1)),
    2925        60955 :                              vn_ref_op_align_unit (currop))))
    2926              :               genop3 = NULL_TREE;
    2927              :             else
    2928              :               {
    2929            4 :                 genop3 = find_or_generate_expression (block, genop3, stmts);
    2930            4 :                 if (!genop3)
    2931              :                   return NULL_TREE;
    2932              :               }
    2933              :           }
    2934        60959 :         return build4 (currop->opcode, currop->type, genop0, genop1,
    2935        60959 :                        genop2, genop3);
    2936              :       }
    2937       273671 :     case COMPONENT_REF:
    2938       273671 :       {
    2939       273671 :         tree op0;
    2940       273671 :         tree op1;
    2941       273671 :         tree genop2 = currop->op1;
    2942       273671 :         op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
    2943       273671 :         if (!op0)
    2944              :           return NULL_TREE;
    2945              :         /* op1 should be a FIELD_DECL, which are represented by themselves.  */
    2946       273663 :         op1 = currop->op0;
    2947       273663 :         if (genop2)
    2948              :           {
    2949            0 :             genop2 = find_or_generate_expression (block, genop2, stmts);
    2950            0 :             if (!genop2)
    2951              :               return NULL_TREE;
    2952              :           }
    2953       273663 :         return build3 (COMPONENT_REF, currop->type, op0, op1, genop2);
    2954              :       }
    2955              : 
    2956       158435 :     case SSA_NAME:
    2957       158435 :       {
    2958       158435 :         genop = find_or_generate_expression (block, currop->op0, stmts);
    2959       158435 :         return genop;
    2960              :       }
    2961         1972 :     case STRING_CST:
    2962         1972 :     case INTEGER_CST:
    2963         1972 :     case POLY_INT_CST:
    2964         1972 :     case COMPLEX_CST:
    2965         1972 :     case VECTOR_CST:
    2966         1972 :     case REAL_CST:
    2967         1972 :     case CONSTRUCTOR:
    2968         1972 :     case VAR_DECL:
    2969         1972 :     case PARM_DECL:
    2970         1972 :     case CONST_DECL:
    2971         1972 :     case RESULT_DECL:
    2972         1972 :     case FUNCTION_DECL:
    2973         1972 :       return currop->op0;
    2974              : 
    2975            0 :     default:
    2976            0 :       gcc_unreachable ();
    2977              :     }
    2978              : }
    2979              : 
    2980              : /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
    2981              :    COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
    2982              :    trying to rename aggregates into ssa form directly, which is a no no.
    2983              : 
    2984              :    Thus, this routine doesn't create temporaries, it just builds a
    2985              :    single access expression for the array, calling
    2986              :    find_or_generate_expression to build the innermost pieces.
    2987              : 
    2988              :    This function is a subroutine of create_expression_by_pieces, and
    2989              :    should not be called on it's own unless you really know what you
    2990              :    are doing.  */
    2991              : 
    2992              : static tree
    2993       395188 : create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
    2994              :                                 gimple_seq *stmts)
    2995              : {
    2996       395188 :   unsigned int op = 0;
    2997       395188 :   return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
    2998              : }
    2999              : 
    3000              : /* Find a simple leader for an expression, or generate one using
    3001              :    create_expression_by_pieces from a NARY expression for the value.
    3002              :    BLOCK is the basic_block we are looking for leaders in.
    3003              :    OP is the tree expression to find a leader for or generate.
    3004              :    Returns the leader or NULL_TREE on failure.  */
    3005              : 
    3006              : static tree
    3007       877765 : find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
    3008              : {
    3009              :   /* Constants are always leaders.  */
    3010       877765 :   if (is_gimple_min_invariant (op))
    3011              :     return op;
    3012              : 
    3013       671933 :   gcc_assert (TREE_CODE (op) == SSA_NAME);
    3014       671933 :   vn_ssa_aux_t info = VN_INFO (op);
    3015       671933 :   unsigned int lookfor = info->value_id;
    3016       671933 :   if (value_id_constant_p (lookfor))
    3017            0 :     return info->valnum;
    3018              : 
    3019       671933 :   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
    3020       671933 :   if (leader)
    3021              :     {
    3022       634689 :       if (leader->kind == NAME)
    3023              :         {
    3024       634689 :           tree name = PRE_EXPR_NAME (leader);
    3025       634689 :           if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
    3026              :             return NULL_TREE;
    3027       634661 :           return name;
    3028              :         }
    3029            0 :       else if (leader->kind == CONSTANT)
    3030            0 :         return PRE_EXPR_CONSTANT (leader);
    3031              : 
    3032              :       /* Defer.  */
    3033              :       return NULL_TREE;
    3034              :     }
    3035        37244 :   gcc_assert (!value_id_constant_p (lookfor));
    3036              : 
    3037              :   /* It must be a complex expression, so generate it recursively.  Note
    3038              :      that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre-28.c
    3039              :      where the insert algorithm fails to insert a required expression.  */
    3040        37244 :   bitmap exprset = value_expressions[lookfor];
    3041        37244 :   bitmap_iterator bi;
    3042        37244 :   unsigned int i;
    3043        37244 :   if (exprset)
    3044        50003 :     EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
    3045              :       {
    3046        46815 :         pre_expr temp = expression_for_id (i);
    3047              :         /* We cannot insert random REFERENCE expressions at arbitrary
    3048              :            places.  We can insert NARYs which eventually re-materializes
    3049              :            its operand values.  */
    3050        46815 :         if (temp->kind == NARY)
    3051              :           {
    3052        34056 :             static int depth;
    3053        34056 :             if (depth > 8)
    3054              :               return NULL_TREE;
    3055              : 
    3056        34041 :             depth++;
    3057        34041 :             tree res = create_expression_by_pieces (block, temp, stmts,
    3058        34041 :                                                     TREE_TYPE (op));
    3059        34041 :             depth--;
    3060        34041 :             return res;
    3061              :           }
    3062              :       }
    3063              : 
    3064              :   /* Defer.  */
    3065              :   return NULL_TREE;
    3066              : }
    3067              : 
    3068              : /* Create an expression in pieces, so that we can handle very complex
    3069              :    expressions that may be ANTIC, but not necessary GIMPLE.
    3070              :    BLOCK is the basic block the expression will be inserted into,
    3071              :    EXPR is the expression to insert (in value form)
    3072              :    STMTS is a statement list to append the necessary insertions into.
    3073              : 
    3074              :    This function will die if we hit some value that shouldn't be
    3075              :    ANTIC but is (IE there is no leader for it, or its components).
    3076              :    The function returns NULL_TREE in case a different antic expression
    3077              :    has to be inserted first.
    3078              :    This function may also generate expressions that are themselves
    3079              :    partially or fully redundant.  Those that are will be either made
    3080              :    fully redundant during the next iteration of insert (for partially
    3081              :    redundant ones), or eliminated by eliminate (for fully redundant
    3082              :    ones).  */
    3083              : 
    3084              : static tree
    3085      2947540 : create_expression_by_pieces (basic_block block, pre_expr expr,
    3086              :                              gimple_seq *stmts, tree type)
    3087              : {
    3088      2947540 :   tree name;
    3089      2947540 :   tree folded;
    3090      2947540 :   gimple_seq forced_stmts = NULL;
    3091      2947540 :   unsigned int value_id;
    3092      2947540 :   gimple_stmt_iterator gsi;
    3093      2947540 :   tree exprtype = type ? type : get_expr_type (expr);
    3094      2947540 :   pre_expr nameexpr;
    3095      2947540 :   gassign *newstmt;
    3096              : 
    3097      2947540 :   switch (expr->kind)
    3098              :     {
    3099              :     /* We may hit the NAME/CONSTANT case if we have to convert types
    3100              :        that value numbering saw through.  */
    3101       736943 :     case NAME:
    3102       736943 :       folded = PRE_EXPR_NAME (expr);
    3103       736943 :       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded))
    3104              :         return NULL_TREE;
    3105       736938 :       if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
    3106              :         return folded;
    3107              :       break;
    3108      1425358 :     case CONSTANT:
    3109      1425358 :       {
    3110      1425358 :         folded = PRE_EXPR_CONSTANT (expr);
    3111      1425358 :         tree tem = fold_convert (exprtype, folded);
    3112      1425358 :         if (is_gimple_min_invariant (tem))
    3113              :           return tem;
    3114              :         break;
    3115              :       }
    3116       398306 :     case REFERENCE:
    3117       398306 :       if (PRE_EXPR_REFERENCE (expr)->operands[0].opcode == CALL_EXPR)
    3118              :         {
    3119         3118 :           vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    3120         3118 :           unsigned int operand = 1;
    3121         3118 :           vn_reference_op_t currop = &ref->operands[0];
    3122         3118 :           tree sc = NULL_TREE;
    3123         3118 :           tree fn = NULL_TREE;
    3124         3118 :           if (currop->op0)
    3125              :             {
    3126         2976 :               fn = find_or_generate_expression (block, currop->op0, stmts);
    3127         2976 :               if (!fn)
    3128            6 :                 return NULL_TREE;
    3129              :             }
    3130         3118 :           if (currop->op1)
    3131              :             {
    3132            0 :               sc = find_or_generate_expression (block, currop->op1, stmts);
    3133            0 :               if (!sc)
    3134              :                 return NULL_TREE;
    3135              :             }
    3136         6236 :           auto_vec<tree> args (ref->operands.length () - 1);
    3137        10699 :           while (operand < ref->operands.length ())
    3138              :             {
    3139         4469 :               tree arg = create_component_ref_by_pieces_1 (block, ref,
    3140         4469 :                                                            &operand, stmts);
    3141         4469 :               if (!arg)
    3142            6 :                 return NULL_TREE;
    3143         4463 :               args.quick_push (arg);
    3144              :             }
    3145         3112 :           gcall *call;
    3146         3112 :           if (currop->op0)
    3147              :             {
    3148         2970 :               call = gimple_build_call_vec (fn, args);
    3149         2970 :               gimple_call_set_fntype (call, currop->type);
    3150              :             }
    3151              :           else
    3152          142 :             call = gimple_build_call_internal_vec ((internal_fn)currop->clique,
    3153              :                                                    args);
    3154         3112 :           gimple_set_location (call, expr->loc);
    3155         3112 :           if (sc)
    3156            0 :             gimple_call_set_chain (call, sc);
    3157         3112 :           tree forcedname = make_ssa_name (ref->type);
    3158         3112 :           gimple_call_set_lhs (call, forcedname);
    3159              :           /* There's no CCP pass after PRE which would re-compute alignment
    3160              :              information so make sure we re-materialize this here.  */
    3161         3112 :           if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED)
    3162            0 :               && args.length () - 2 <= 1
    3163            0 :               && tree_fits_uhwi_p (args[1])
    3164         3112 :               && (args.length () != 3 || tree_fits_uhwi_p (args[2])))
    3165              :             {
    3166            0 :               unsigned HOST_WIDE_INT halign = tree_to_uhwi (args[1]);
    3167            0 :               unsigned HOST_WIDE_INT hmisalign
    3168            0 :                 = args.length () == 3 ? tree_to_uhwi (args[2]) : 0;
    3169            0 :               if ((halign & (halign - 1)) == 0
    3170            0 :                   && (hmisalign & ~(halign - 1)) == 0
    3171            0 :                   && (unsigned int)halign != 0)
    3172            0 :                 set_ssa_name_alignment (forcedname, halign, hmisalign);
    3173              :             }
    3174         3112 :           gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block));
    3175         3112 :           gimple_seq_add_stmt_without_update (&forced_stmts, call);
    3176         3112 :           folded = forcedname;
    3177         3118 :         }
    3178              :       else
    3179              :         {
    3180       395188 :           folded = create_component_ref_by_pieces (block,
    3181              :                                                    PRE_EXPR_REFERENCE (expr),
    3182              :                                                    stmts);
    3183       395188 :           if (!folded)
    3184              :             return NULL_TREE;
    3185       395184 :           name = make_temp_ssa_name (exprtype, NULL, "pretmp");
    3186       395184 :           newstmt = gimple_build_assign (name, folded);
    3187       395184 :           gimple_set_location (newstmt, expr->loc);
    3188       395184 :           gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
    3189       395184 :           gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block));
    3190       395184 :           folded = name;
    3191              :         }
    3192              :       break;
    3193       386933 :     case NARY:
    3194       386933 :       {
    3195       386933 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    3196       386933 :         tree *genop = XALLOCAVEC (tree, nary->length);
    3197       386933 :         unsigned i;
    3198      1031325 :         for (i = 0; i < nary->length; ++i)
    3199              :           {
    3200       654773 :             genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
    3201       654773 :             if (!genop[i])
    3202              :               return NULL_TREE;
    3203              :             /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR.  It
    3204              :                may have conversions stripped.  */
    3205       644392 :             if (nary->opcode == POINTER_PLUS_EXPR)
    3206              :               {
    3207       106846 :                 if (i == 0)
    3208        53455 :                   genop[i] = gimple_convert (&forced_stmts,
    3209              :                                              nary->type, genop[i]);
    3210        53391 :                 else if (i == 1)
    3211        53391 :                   genop[i] = gimple_convert (&forced_stmts,
    3212              :                                              sizetype, genop[i]);
    3213              :               }
    3214              :             else
    3215       537546 :               genop[i] = gimple_convert (&forced_stmts,
    3216       537546 :                                          TREE_TYPE (nary->op[i]), genop[i]);
    3217              :           }
    3218       376552 :         if (nary->opcode == CONSTRUCTOR)
    3219              :           {
    3220            8 :             vec<constructor_elt, va_gc> *elts = NULL;
    3221           40 :             for (i = 0; i < nary->length; ++i)
    3222           32 :               CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
    3223            8 :             folded = build_constructor (nary->type, elts);
    3224            8 :             name = make_temp_ssa_name (exprtype, NULL, "pretmp");
    3225            8 :             newstmt = gimple_build_assign (name, folded);
    3226            8 :             gimple_set_location (newstmt, expr->loc);
    3227            8 :             gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
    3228            8 :             folded = name;
    3229              :           }
    3230              :         else
    3231              :           {
    3232       376544 :             switch (nary->length)
    3233              :               {
    3234       110244 :               case 1:
    3235       110244 :                 folded = gimple_build (&forced_stmts, expr->loc,
    3236              :                                        nary->opcode, nary->type, genop[0]);
    3237       110244 :                 break;
    3238       266083 :               case 2:
    3239       266083 :                 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
    3240              :                                        nary->type, genop[0], genop[1]);
    3241       266083 :                 break;
    3242          217 :               case 3:
    3243          217 :                 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
    3244              :                                        nary->type, genop[0], genop[1],
    3245              :                                        genop[2]);
    3246          217 :                 break;
    3247            0 :               default:
    3248            0 :                 gcc_unreachable ();
    3249              :               }
    3250              :           }
    3251              :       }
    3252              :       break;
    3253            0 :     default:
    3254            0 :       gcc_unreachable ();
    3255              :     }
    3256              : 
    3257       870185 :   folded = gimple_convert (&forced_stmts, exprtype, folded);
    3258              : 
    3259              :   /* If there is nothing to insert, return the simplified result.  */
    3260       870185 :   if (gimple_seq_empty_p (forced_stmts))
    3261              :     return folded;
    3262              :   /* If we simplified to a constant return it and discard eventually
    3263              :      built stmts.  */
    3264       774761 :   if (is_gimple_min_invariant (folded))
    3265              :     {
    3266            0 :       gimple_seq_discard (forced_stmts);
    3267            0 :       return folded;
    3268              :     }
    3269              :   /* Likewise if we simplified to sth not queued for insertion.  */
    3270       774761 :   bool found = false;
    3271       774761 :   gsi = gsi_last (forced_stmts);
    3272       774761 :   for (; !gsi_end_p (gsi); gsi_prev (&gsi))
    3273              :     {
    3274       774761 :       gimple *stmt = gsi_stmt (gsi);
    3275       774761 :       tree forcedname = gimple_get_lhs (stmt);
    3276       774761 :       if (forcedname == folded)
    3277              :         {
    3278              :           found = true;
    3279              :           break;
    3280              :         }
    3281              :     }
    3282       774761 :   if (! found)
    3283              :     {
    3284            0 :       gimple_seq_discard (forced_stmts);
    3285            0 :       return folded;
    3286              :     }
    3287       774761 :   gcc_assert (TREE_CODE (folded) == SSA_NAME);
    3288              : 
    3289              :   /* If we have any intermediate expressions to the value sets, add them
    3290              :      to the value sets and chain them in the instruction stream.  */
    3291       774761 :   if (forced_stmts)
    3292              :     {
    3293       774761 :       gsi = gsi_start (forced_stmts);
    3294      1550019 :       for (; !gsi_end_p (gsi); gsi_next (&gsi))
    3295              :         {
    3296       775258 :           gimple *stmt = gsi_stmt (gsi);
    3297       775258 :           tree forcedname = gimple_get_lhs (stmt);
    3298       775258 :           pre_expr nameexpr;
    3299              : 
    3300       775258 :           if (forcedname != folded)
    3301              :             {
    3302          497 :               vn_ssa_aux_t vn_info = VN_INFO (forcedname);
    3303          497 :               vn_info->valnum = forcedname;
    3304          497 :               vn_info->value_id = get_next_value_id ();
    3305          497 :               nameexpr = get_or_alloc_expr_for_name (forcedname);
    3306          497 :               add_to_value (vn_info->value_id, nameexpr);
    3307          497 :               if (NEW_SETS (block))
    3308          497 :                 bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
    3309          497 :               bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
    3310              :             }
    3311              : 
    3312       775258 :           bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
    3313              :         }
    3314       774761 :       gimple_seq_add_seq (stmts, forced_stmts);
    3315              :     }
    3316              : 
    3317       774761 :   name = folded;
    3318              : 
    3319              :   /* Fold the last statement.  */
    3320       774761 :   gsi = gsi_last (*stmts);
    3321       774761 :   if (fold_stmt_inplace (&gsi))
    3322       207243 :     update_stmt (gsi_stmt (gsi));
    3323              : 
    3324              :   /* Add a value number to the temporary.
    3325              :      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
    3326              :      we are creating the expression by pieces, and this particular piece of
    3327              :      the expression may have been represented.  There is no harm in replacing
    3328              :      here.  */
    3329       774761 :   value_id = get_expr_value_id (expr);
    3330       774761 :   vn_ssa_aux_t vn_info = VN_INFO (name);
    3331       774761 :   vn_info->value_id = value_id;
    3332       774761 :   vn_info->valnum = vn_valnum_from_value_id (value_id);
    3333       774761 :   if (vn_info->valnum == NULL_TREE)
    3334       241842 :     vn_info->valnum = name;
    3335       774761 :   gcc_assert (vn_info->valnum != NULL_TREE);
    3336       774761 :   nameexpr = get_or_alloc_expr_for_name (name);
    3337       774761 :   add_to_value (value_id, nameexpr);
    3338       774761 :   if (NEW_SETS (block))
    3339       549004 :     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
    3340       774761 :   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
    3341              : 
    3342       774761 :   pre_stats.insertions++;
    3343       774761 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3344              :     {
    3345           18 :       fprintf (dump_file, "Inserted ");
    3346           36 :       print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)), 0);
    3347           18 :       fprintf (dump_file, " in predecessor %d (%04d)\n",
    3348              :                block->index, value_id);
    3349              :     }
    3350              : 
    3351              :   return name;
    3352              : }
    3353              : 
    3354              : 
    3355              : /* Insert the to-be-made-available values of expression EXPRNUM for each
    3356              :    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
    3357              :    merge the result with a phi node, given the same value number as
    3358              :    NODE.  Return true if we have inserted new stuff.  */
    3359              : 
    3360              : static bool
    3361      1982112 : insert_into_preds_of_block (basic_block block, unsigned int exprnum,
    3362              :                             vec<pre_expr> &avail)
    3363              : {
    3364      1982112 :   pre_expr expr = expression_for_id (exprnum);
    3365      1982112 :   pre_expr newphi;
    3366      1982112 :   unsigned int val = get_expr_value_id (expr);
    3367      1982112 :   edge pred;
    3368      1982112 :   bool insertions = false;
    3369      1982112 :   bool nophi = false;
    3370      1982112 :   basic_block bprime;
    3371      1982112 :   pre_expr eprime;
    3372      1982112 :   edge_iterator ei;
    3373      1982112 :   tree type = get_expr_type (expr);
    3374      1982112 :   tree temp;
    3375      1982112 :   gphi *phi;
    3376              : 
    3377              :   /* Make sure we aren't creating an induction variable.  */
    3378      1982112 :   if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2)
    3379              :     {
    3380      1646803 :       bool firstinsideloop = false;
    3381      1646803 :       bool secondinsideloop = false;
    3382      4940409 :       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
    3383      1646803 :                                                EDGE_PRED (block, 0)->src);
    3384      4940409 :       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
    3385      1646803 :                                                 EDGE_PRED (block, 1)->src);
    3386              :       /* Induction variables only have one edge inside the loop.  */
    3387      1646803 :       if ((firstinsideloop ^ secondinsideloop)
    3388      1569506 :           && expr->kind != REFERENCE)
    3389              :         {
    3390      1488163 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3391           56 :             fprintf (dump_file, "Skipping insertion of phi for partial "
    3392              :                      "redundancy: Looks like an induction variable\n");
    3393              :           nophi = true;
    3394              :         }
    3395              :     }
    3396              : 
    3397              :   /* Make the necessary insertions.  */
    3398      6168481 :   FOR_EACH_EDGE (pred, ei, block->preds)
    3399              :     {
    3400              :       /* When we are not inserting a PHI node do not bother inserting
    3401              :          into places that do not dominate the anticipated computations.  */
    3402      4186369 :       if (nophi && !dominated_by_p (CDI_DOMINATORS, block, pred->src))
    3403      1501863 :         continue;
    3404      2687716 :       gimple_seq stmts = NULL;
    3405      2687716 :       tree builtexpr;
    3406      2687716 :       bprime = pred->src;
    3407      2687716 :       eprime = avail[pred->dest_idx];
    3408      2687716 :       builtexpr = create_expression_by_pieces (bprime, eprime,
    3409              :                                                &stmts, type);
    3410      2687716 :       gcc_assert (!(pred->flags & EDGE_ABNORMAL));
    3411      2687716 :       if (!gimple_seq_empty_p (stmts))
    3412              :         {
    3413       522157 :           basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
    3414       522157 :           gcc_assert (! new_bb);
    3415              :           insertions = true;
    3416              :         }
    3417      2687716 :       if (!builtexpr)
    3418              :         {
    3419              :           /* We cannot insert a PHI node if we failed to insert
    3420              :              on one edge.  */
    3421         3210 :           nophi = true;
    3422         3210 :           continue;
    3423              :         }
    3424      2684506 :       if (is_gimple_min_invariant (builtexpr))
    3425      1425409 :         avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr);
    3426              :       else
    3427      1259097 :         avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
    3428              :     }
    3429              :   /* If we didn't want a phi node, and we made insertions, we still have
    3430              :      inserted new stuff, and thus return true.  If we didn't want a phi node,
    3431              :      and didn't make insertions, we haven't added anything new, so return
    3432              :      false.  */
    3433      1982112 :   if (nophi && insertions)
    3434              :     return true;
    3435      1973367 :   else if (nophi && !insertions)
    3436              :     return false;
    3437              : 
    3438              :   /* Now build a phi for the new variable.  */
    3439       490745 :   temp = make_temp_ssa_name (type, NULL, "prephitmp");
    3440       490745 :   phi = create_phi_node (temp, block);
    3441              : 
    3442       490745 :   vn_ssa_aux_t vn_info = VN_INFO (temp);
    3443       490745 :   vn_info->value_id = val;
    3444       490745 :   vn_info->valnum = vn_valnum_from_value_id (val);
    3445       490745 :   if (vn_info->valnum == NULL_TREE)
    3446        99655 :     vn_info->valnum = temp;
    3447       490745 :   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
    3448      1685764 :   FOR_EACH_EDGE (pred, ei, block->preds)
    3449              :     {
    3450      1195019 :       pre_expr ae = avail[pred->dest_idx];
    3451      1195019 :       gcc_assert (get_expr_type (ae) == type
    3452              :                   || useless_type_conversion_p (type, get_expr_type (ae)));
    3453      1195019 :       if (ae->kind == CONSTANT)
    3454       191706 :         add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)),
    3455              :                      pred, UNKNOWN_LOCATION);
    3456              :       else
    3457      1003313 :         add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
    3458              :     }
    3459              : 
    3460       490745 :   newphi = get_or_alloc_expr_for_name (temp);
    3461       490745 :   add_to_value (val, newphi);
    3462              : 
    3463              :   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
    3464              :      this insertion, since we test for the existence of this value in PHI_GEN
    3465              :      before proceeding with the partial redundancy checks in insert_aux.
    3466              : 
    3467              :      The value may exist in AVAIL_OUT, in particular, it could be represented
    3468              :      by the expression we are trying to eliminate, in which case we want the
    3469              :      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
    3470              :      inserted there.
    3471              : 
    3472              :      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
    3473              :      this block, because if it did, it would have existed in our dominator's
    3474              :      AVAIL_OUT, and would have been skipped due to the full redundancy check.
    3475              :   */
    3476              : 
    3477       490745 :   bitmap_insert_into_set (PHI_GEN (block), newphi);
    3478       490745 :   bitmap_value_replace_in_set (AVAIL_OUT (block),
    3479              :                                newphi);
    3480       490745 :   if (NEW_SETS (block))
    3481       490745 :     bitmap_insert_into_set (NEW_SETS (block), newphi);
    3482              : 
    3483              :   /* If we insert a PHI node for a conversion of another PHI node
    3484              :      in the same basic-block try to preserve range information.
    3485              :      This is important so that followup loop passes receive optimal
    3486              :      number of iteration analysis results.  See PR61743.  */
    3487       490745 :   if (expr->kind == NARY
    3488       190138 :       && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)
    3489        56923 :       && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME
    3490        56748 :       && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block
    3491        46699 :       && INTEGRAL_TYPE_P (type)
    3492        45864 :       && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))
    3493        44790 :       && (TYPE_PRECISION (type)
    3494        44790 :           >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0])))
    3495       527638 :       && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
    3496              :     {
    3497        23121 :       int_range_max r;
    3498        46242 :       if (get_range_query (cfun)->range_of_expr (r, expr->u.nary->op[0])
    3499        23121 :           && !r.undefined_p ()
    3500        23121 :           && !r.varying_p ()
    3501        46242 :           && !wi::neg_p (r.lower_bound (), SIGNED)
    3502        63276 :           && !wi::neg_p (r.upper_bound (), SIGNED))
    3503              :         {
    3504              :           /* Just handle extension and sign-changes of all-positive ranges.  */
    3505        16310 :           range_cast (r, type);
    3506        16310 :           set_range_info (temp, r);
    3507              :         }
    3508        23121 :     }
    3509              : 
    3510       490745 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3511              :     {
    3512            8 :       fprintf (dump_file, "Created phi ");
    3513            8 :       print_gimple_stmt (dump_file, phi, 0);
    3514            8 :       fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
    3515              :     }
    3516       490745 :   pre_stats.phis++;
    3517       490745 :   return true;
    3518              : }
    3519              : 
    3520              : 
    3521              : 
    3522              : /* Perform insertion of partially redundant or hoistable values.
    3523              :    For BLOCK, do the following:
    3524              :    1.  Propagate the NEW_SETS of the dominator into the current block.
    3525              :    If the block has multiple predecessors,
    3526              :        2a. Iterate over the ANTIC expressions for the block to see if
    3527              :            any of them are partially redundant.
    3528              :        2b. If so, insert them into the necessary predecessors to make
    3529              :            the expression fully redundant.
    3530              :        2c. Insert a new PHI merging the values of the predecessors.
    3531              :        2d. Insert the new PHI, and the new expressions, into the
    3532              :            NEW_SETS set.
    3533              :    If the block has multiple successors,
    3534              :        3a. Iterate over the ANTIC values for the block to see if
    3535              :            any of them are good candidates for hoisting.
    3536              :        3b. If so, insert expressions computing the values in BLOCK,
    3537              :            and add the new expressions into the NEW_SETS set.
    3538              :    4. Recursively call ourselves on the dominator children of BLOCK.
    3539              : 
    3540              :    Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
    3541              :    do_pre_regular_insertion and do_partial_insertion.  3a and 3b are
    3542              :    done in do_hoist_insertion.
    3543              : */
    3544              : 
    3545              : static bool
    3546      3727351 : do_pre_regular_insertion (basic_block block, basic_block dom,
    3547              :                           vec<pre_expr> exprs)
    3548              : {
    3549      3727351 :   bool new_stuff = false;
    3550      3727351 :   pre_expr expr;
    3551      3727351 :   auto_vec<pre_expr, 2> avail;
    3552      3727351 :   int i;
    3553              : 
    3554      3727351 :   avail.safe_grow (EDGE_COUNT (block->preds), true);
    3555              : 
    3556     29744588 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    3557              :     {
    3558     22289886 :       if (expr->kind == NARY
    3559     22289886 :           || expr->kind == REFERENCE)
    3560              :         {
    3561     12611201 :           unsigned int val;
    3562     12611201 :           bool by_some = false;
    3563     12611201 :           bool cant_insert = false;
    3564     12611201 :           bool all_same = true;
    3565     12611201 :           unsigned num_inserts = 0;
    3566     12611201 :           unsigned num_const = 0;
    3567     12611201 :           pre_expr first_s = NULL;
    3568     12611201 :           edge pred;
    3569     12611201 :           basic_block bprime;
    3570     12611201 :           pre_expr eprime = NULL;
    3571     12611201 :           edge_iterator ei;
    3572     12611201 :           pre_expr edoubleprime = NULL;
    3573     12611201 :           bool do_insertion = false;
    3574              : 
    3575     12611201 :           val = get_expr_value_id (expr);
    3576     25222402 :           if (bitmap_set_contains_value (PHI_GEN (block), val))
    3577      1068084 :             continue;
    3578     11806234 :           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
    3579              :             {
    3580       263117 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3581              :                 {
    3582            7 :                   fprintf (dump_file, "Found fully redundant value: ");
    3583            7 :                   print_pre_expr (dump_file, expr);
    3584            7 :                   fprintf (dump_file, "\n");
    3585              :                 }
    3586       263117 :               continue;
    3587              :             }
    3588              : 
    3589     37666656 :           FOR_EACH_EDGE (pred, ei, block->preds)
    3590              :             {
    3591     26124311 :               unsigned int vprime;
    3592              : 
    3593              :               /* We should never run insertion for the exit block
    3594              :                  and so not come across fake pred edges.  */
    3595     26124311 :               gcc_assert (!(pred->flags & EDGE_FAKE));
    3596     26124311 :               bprime = pred->src;
    3597              :               /* We are looking at ANTIC_OUT of bprime.  */
    3598     26124311 :               eprime = phi_translate (NULL, expr, ANTIC_IN (block), NULL, pred);
    3599              : 
    3600              :               /* eprime will generally only be NULL if the
    3601              :                  value of the expression, translated
    3602              :                  through the PHI for this predecessor, is
    3603              :                  undefined.  If that is the case, we can't
    3604              :                  make the expression fully redundant,
    3605              :                  because its value is undefined along a
    3606              :                  predecessor path.  We can thus break out
    3607              :                  early because it doesn't matter what the
    3608              :                  rest of the results are.  */
    3609     26124311 :               if (eprime == NULL)
    3610              :                 {
    3611          772 :                   avail[pred->dest_idx] = NULL;
    3612          772 :                   cant_insert = true;
    3613          772 :                   break;
    3614              :                 }
    3615              : 
    3616     26123539 :               vprime = get_expr_value_id (eprime);
    3617     26123539 :               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
    3618              :                                                  vprime);
    3619     26123539 :               if (edoubleprime == NULL)
    3620              :                 {
    3621     23458834 :                   avail[pred->dest_idx] = eprime;
    3622     23458834 :                   all_same = false;
    3623     23458834 :                   num_inserts++;
    3624              :                 }
    3625              :               else
    3626              :                 {
    3627      2664705 :                   avail[pred->dest_idx] = edoubleprime;
    3628      2664705 :                   by_some = true;
    3629      2664705 :                   if (edoubleprime->kind == CONSTANT)
    3630      1771006 :                     num_const++;
    3631              :                   /* We want to perform insertions to remove a redundancy on
    3632              :                      a path in the CFG we want to optimize for speed.  */
    3633      2664705 :                   if (optimize_edge_for_speed_p (pred))
    3634      2228333 :                     do_insertion = true;
    3635      2664705 :                   if (first_s == NULL)
    3636              :                     first_s = edoubleprime;
    3637       297907 :                   else if (!pre_expr_d::equal (first_s, edoubleprime))
    3638       228737 :                     all_same = false;
    3639              :                 }
    3640              :             }
    3641              :           /* If we can insert it, it's not the same value
    3642              :              already existing along every predecessor, and
    3643              :              it's defined by some predecessor, it is
    3644              :              partially redundant.  */
    3645     11543117 :           if (!cant_insert && !all_same && by_some)
    3646              :             {
    3647              :               /* If the expression is redundant on all edges and we need
    3648              :                  to at most insert one copy from a constant do the PHI
    3649              :                  insertion even when not optimizing a path that's to be
    3650              :                  optimized for speed.  */
    3651      2363359 :               if (num_inserts == 0 && num_const <= 1)
    3652              :                 do_insertion = true;
    3653      2213538 :               if (!do_insertion)
    3654              :                 {
    3655       387601 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3656              :                     {
    3657            0 :                       fprintf (dump_file, "Skipping partial redundancy for "
    3658              :                                "expression ");
    3659            0 :                       print_pre_expr (dump_file, expr);
    3660            0 :                       fprintf (dump_file, " (%04d), no redundancy on to be "
    3661              :                                "optimized for speed edge\n", val);
    3662              :                     }
    3663              :                 }
    3664      1975758 :               else if (dbg_cnt (treepre_insert))
    3665              :                 {
    3666      1975758 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3667              :                     {
    3668           64 :                       fprintf (dump_file, "Found partial redundancy for "
    3669              :                                "expression ");
    3670           64 :                       print_pre_expr (dump_file, expr);
    3671           64 :                       fprintf (dump_file, " (%04d)\n",
    3672              :                                get_expr_value_id (expr));
    3673              :                     }
    3674      1975758 :                   if (insert_into_preds_of_block (block,
    3675              :                                                   get_expression_id (expr),
    3676              :                                                   avail))
    3677     11543117 :                     new_stuff = true;
    3678              :                 }
    3679              :             }
    3680              :           /* If all edges produce the same value and that value is
    3681              :              an invariant, then the PHI has the same value on all
    3682              :              edges.  Note this.  */
    3683      9179758 :           else if (!cant_insert
    3684      9179758 :                    && all_same
    3685      9179758 :                    && (edoubleprime->kind != NAME
    3686         1781 :                        || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
    3687              :                              (PRE_EXPR_NAME (edoubleprime))))
    3688              :             {
    3689         3413 :               gcc_assert (edoubleprime->kind == CONSTANT
    3690              :                           || edoubleprime->kind == NAME);
    3691              : 
    3692         3413 :               tree temp = make_temp_ssa_name (get_expr_type (expr),
    3693              :                                               NULL, "pretmp");
    3694         3413 :               gassign *assign
    3695         3413 :                 = gimple_build_assign (temp,
    3696         3413 :                                        edoubleprime->kind == CONSTANT ?
    3697              :                                        PRE_EXPR_CONSTANT (edoubleprime) :
    3698              :                                        PRE_EXPR_NAME (edoubleprime));
    3699         3413 :               gimple_stmt_iterator gsi = gsi_after_labels (block);
    3700         3413 :               gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
    3701              : 
    3702         3413 :               vn_ssa_aux_t vn_info = VN_INFO (temp);
    3703         3413 :               vn_info->value_id = val;
    3704         3413 :               vn_info->valnum = vn_valnum_from_value_id (val);
    3705         3413 :               if (vn_info->valnum == NULL_TREE)
    3706          583 :                 vn_info->valnum = temp;
    3707         3413 :               bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
    3708         3413 :               pre_expr newe = get_or_alloc_expr_for_name (temp);
    3709         3413 :               add_to_value (val, newe);
    3710         3413 :               bitmap_value_replace_in_set (AVAIL_OUT (block), newe);
    3711         3413 :               bitmap_insert_into_set (NEW_SETS (block), newe);
    3712         3413 :               bitmap_insert_into_set (PHI_GEN (block), newe);
    3713              :             }
    3714              :         }
    3715              :     }
    3716              : 
    3717      3727351 :   return new_stuff;
    3718      3727351 : }
    3719              : 
    3720              : 
    3721              : /* Perform insertion for partially anticipatable expressions.  There
    3722              :    is only one case we will perform insertion for these.  This case is
    3723              :    if the expression is partially anticipatable, and fully available.
    3724              :    In this case, we know that putting it earlier will enable us to
    3725              :    remove the later computation.  */
    3726              : 
    3727              : static bool
    3728       339201 : do_pre_partial_partial_insertion (basic_block block, basic_block dom,
    3729              :                                   vec<pre_expr> exprs)
    3730              : {
    3731       339201 :   bool new_stuff = false;
    3732       339201 :   pre_expr expr;
    3733       339201 :   auto_vec<pre_expr, 2> avail;
    3734       339201 :   int i;
    3735              : 
    3736       339201 :   avail.safe_grow (EDGE_COUNT (block->preds), true);
    3737              : 
    3738      3606632 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    3739              :     {
    3740      2928230 :       if (expr->kind == NARY
    3741      2928230 :           || expr->kind == REFERENCE)
    3742              :         {
    3743      2228647 :           unsigned int val;
    3744      2228647 :           bool by_all = true;
    3745      2228647 :           bool cant_insert = false;
    3746      2228647 :           edge pred;
    3747      2228647 :           basic_block bprime;
    3748      2228647 :           pre_expr eprime = NULL;
    3749      2228647 :           edge_iterator ei;
    3750              : 
    3751      2228647 :           val = get_expr_value_id (expr);
    3752      4457294 :           if (bitmap_set_contains_value (PHI_GEN (block), val))
    3753        58150 :             continue;
    3754      2219191 :           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
    3755        48694 :             continue;
    3756              : 
    3757      2247119 :           FOR_EACH_EDGE (pred, ei, block->preds)
    3758              :             {
    3759      2237035 :               unsigned int vprime;
    3760      2237035 :               pre_expr edoubleprime;
    3761              : 
    3762              :               /* We should never run insertion for the exit block
    3763              :                  and so not come across fake pred edges.  */
    3764      2237035 :               gcc_assert (!(pred->flags & EDGE_FAKE));
    3765      2237035 :               bprime = pred->src;
    3766      4474070 :               eprime = phi_translate (NULL, expr, ANTIC_IN (block),
    3767      2237035 :                                       PA_IN (block), pred);
    3768              : 
    3769              :               /* eprime will generally only be NULL if the
    3770              :                  value of the expression, translated
    3771              :                  through the PHI for this predecessor, is
    3772              :                  undefined.  If that is the case, we can't
    3773              :                  make the expression fully redundant,
    3774              :                  because its value is undefined along a
    3775              :                  predecessor path.  We can thus break out
    3776              :                  early because it doesn't matter what the
    3777              :                  rest of the results are.  */
    3778      2237035 :               if (eprime == NULL)
    3779              :                 {
    3780           22 :                   avail[pred->dest_idx] = NULL;
    3781           22 :                   cant_insert = true;
    3782           22 :                   break;
    3783              :                 }
    3784              : 
    3785      2237013 :               vprime = get_expr_value_id (eprime);
    3786      2237013 :               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
    3787      2237013 :               avail[pred->dest_idx] = edoubleprime;
    3788      2237013 :               if (edoubleprime == NULL)
    3789              :                 {
    3790              :                   by_all = false;
    3791              :                   break;
    3792              :                 }
    3793              :             }
    3794              : 
    3795              :           /* If we can insert it, it's not the same value
    3796              :              already existing along every predecessor, and
    3797              :              it's defined by some predecessor, it is
    3798              :              partially redundant.  */
    3799      2170497 :           if (!cant_insert && by_all)
    3800              :             {
    3801        10084 :               edge succ;
    3802        10084 :               bool do_insertion = false;
    3803              : 
    3804              :               /* Insert only if we can remove a later expression on a path
    3805              :                  that we want to optimize for speed.
    3806              :                  The phi node that we will be inserting in BLOCK is not free,
    3807              :                  and inserting it for the sake of !optimize_for_speed successor
    3808              :                  may cause regressions on the speed path.  */
    3809        27896 :               FOR_EACH_EDGE (succ, ei, block->succs)
    3810              :                 {
    3811        17812 :                   if (bitmap_set_contains_value (PA_IN (succ->dest), val)
    3812        17812 :                       || bitmap_set_contains_value (ANTIC_IN (succ->dest), val))
    3813              :                     {
    3814         9356 :                       if (optimize_edge_for_speed_p (succ))
    3815        17812 :                         do_insertion = true;
    3816              :                     }
    3817              :                 }
    3818              : 
    3819        10084 :               if (!do_insertion)
    3820              :                 {
    3821         3730 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3822              :                     {
    3823            0 :                       fprintf (dump_file, "Skipping partial partial redundancy "
    3824              :                                "for expression ");
    3825            0 :                       print_pre_expr (dump_file, expr);
    3826            0 :                       fprintf (dump_file, " (%04d), not (partially) anticipated "
    3827              :                                "on any to be optimized for speed edges\n", val);
    3828              :                     }
    3829              :                 }
    3830         6354 :               else if (dbg_cnt (treepre_insert))
    3831              :                 {
    3832         6354 :                   pre_stats.pa_insert++;
    3833         6354 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3834              :                     {
    3835            0 :                       fprintf (dump_file, "Found partial partial redundancy "
    3836              :                                "for expression ");
    3837            0 :                       print_pre_expr (dump_file, expr);
    3838            0 :                       fprintf (dump_file, " (%04d)\n",
    3839              :                                get_expr_value_id (expr));
    3840              :                     }
    3841         6354 :                   if (insert_into_preds_of_block (block,
    3842              :                                                   get_expression_id (expr),
    3843              :                                                   avail))
    3844        10084 :                     new_stuff = true;
    3845              :                 }
    3846              :             }
    3847              :         }
    3848              :     }
    3849              : 
    3850       339201 :   return new_stuff;
    3851       339201 : }
    3852              : 
    3853              : /* Insert expressions in BLOCK to compute hoistable values up.
    3854              :    Return TRUE if something was inserted, otherwise return FALSE.
    3855              :    The caller has to make sure that BLOCK has at least two successors.  */
    3856              : 
    3857              : static bool
    3858      4823113 : do_hoist_insertion (basic_block block)
    3859              : {
    3860      4823113 :   edge e;
    3861      4823113 :   edge_iterator ei;
    3862      4823113 :   bool new_stuff = false;
    3863      4823113 :   unsigned i;
    3864      4823113 :   gimple_stmt_iterator last;
    3865              : 
    3866              :   /* At least two successors, or else...  */
    3867      4823113 :   gcc_assert (EDGE_COUNT (block->succs) >= 2);
    3868              : 
    3869              :   /* Check that all successors of BLOCK are dominated by block.
    3870              :      We could use dominated_by_p() for this, but actually there is a much
    3871              :      quicker check: any successor that is dominated by BLOCK can't have
    3872              :      more than one predecessor edge.  */
    3873     14563854 :   FOR_EACH_EDGE (e, ei, block->succs)
    3874      9748315 :     if (! single_pred_p (e->dest))
    3875              :       return false;
    3876              : 
    3877              :   /* Determine the insertion point.  If we cannot safely insert before
    3878              :      the last stmt if we'd have to, bail out.  */
    3879      4815539 :   last = gsi_last_bb (block);
    3880      4815539 :   if (!gsi_end_p (last)
    3881      4815082 :       && !is_ctrl_stmt (gsi_stmt (last))
    3882      5417597 :       && stmt_ends_bb_p (gsi_stmt (last)))
    3883              :     return false;
    3884              : 
    3885              :   /* We have multiple successors, compute ANTIC_OUT by taking the intersection
    3886              :      of all of ANTIC_IN translating through PHI nodes.  Track the union
    3887              :      of the expression sets so we can pick a representative that is
    3888              :      fully generatable out of hoistable expressions.  */
    3889      4214060 :   bitmap_set_t ANTIC_OUT = bitmap_set_new ();
    3890      4214060 :   bool first = true;
    3891     12745665 :   FOR_EACH_EDGE (e, ei, block->succs)
    3892              :     {
    3893      8531605 :       if (first)
    3894              :         {
    3895      4214060 :           phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
    3896      4214060 :           first = false;
    3897              :         }
    3898      4317545 :       else if (!gimple_seq_empty_p (phi_nodes (e->dest)))
    3899              :         {
    3900            7 :           bitmap_set_t tmp = bitmap_set_new ();
    3901            7 :           phi_translate_set (tmp, ANTIC_IN (e->dest), e);
    3902            7 :           bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
    3903            7 :           bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
    3904            7 :           bitmap_set_free (tmp);
    3905              :         }
    3906              :       else
    3907              :         {
    3908      4317538 :           bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
    3909      4317538 :           bitmap_ior_into (&ANTIC_OUT->expressions,
    3910      4317538 :                            &ANTIC_IN (e->dest)->expressions);
    3911              :         }
    3912              :     }
    3913              : 
    3914              :   /* Compute the set of hoistable expressions from ANTIC_OUT.  First compute
    3915              :      hoistable values.  */
    3916      4214060 :   bitmap_set hoistable_set;
    3917              : 
    3918              :   /* A hoistable value must be in ANTIC_OUT(block)
    3919              :      but not in AVAIL_OUT(BLOCK).  */
    3920      4214060 :   bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack);
    3921      4214060 :   bitmap_and_compl (&hoistable_set.values,
    3922      4214060 :                     &ANTIC_OUT->values, &AVAIL_OUT (block)->values);
    3923              : 
    3924              :   /* Short-cut for a common case: hoistable_set is empty.  */
    3925      4214060 :   if (bitmap_empty_p (&hoistable_set.values))
    3926              :     {
    3927      3451979 :       bitmap_set_free (ANTIC_OUT);
    3928      3451979 :       return false;
    3929              :     }
    3930              : 
    3931              :   /* Compute which of the hoistable values is in AVAIL_OUT of
    3932              :      at least one of the successors of BLOCK.  */
    3933       762081 :   bitmap_head availout_in_some;
    3934       762081 :   bitmap_initialize (&availout_in_some, &grand_bitmap_obstack);
    3935      2303137 :   FOR_EACH_EDGE (e, ei, block->succs)
    3936              :     /* Do not consider expressions solely because their availability
    3937              :        on loop exits.  They'd be ANTIC-IN throughout the whole loop
    3938              :        and thus effectively hoisted across loops by combination of
    3939              :        PRE and hoisting.  */
    3940      1541056 :     if (! loop_exit_edge_p (block->loop_father, e))
    3941      1370471 :       bitmap_ior_and_into (&availout_in_some, &hoistable_set.values,
    3942      1370471 :                            &AVAIL_OUT (e->dest)->values);
    3943       762081 :   bitmap_clear (&hoistable_set.values);
    3944              : 
    3945              :   /* Short-cut for a common case: availout_in_some is empty.  */
    3946       762081 :   if (bitmap_empty_p (&availout_in_some))
    3947              :     {
    3948       618618 :       bitmap_set_free (ANTIC_OUT);
    3949       618618 :       return false;
    3950              :     }
    3951              : 
    3952              :   /* Hack hoistable_set in-place so we can use sorted_array_from_bitmap_set.  */
    3953       143463 :   bitmap_move (&hoistable_set.values, &availout_in_some);
    3954       143463 :   hoistable_set.expressions = ANTIC_OUT->expressions;
    3955              : 
    3956              :   /* Now finally construct the topological-ordered expression set.  */
    3957       143463 :   vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set, true);
    3958              : 
    3959              :   /* If there are candidate values for hoisting, insert expressions
    3960              :      strategically to make the hoistable expressions fully redundant.  */
    3961       143463 :   pre_expr expr;
    3962       512719 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    3963              :     {
    3964              :       /* While we try to sort expressions topologically above the
    3965              :          sorting doesn't work out perfectly.  Catch expressions we
    3966              :          already inserted.  */
    3967       225793 :       unsigned int value_id = get_expr_value_id (expr);
    3968       451586 :       if (bitmap_set_contains_value (AVAIL_OUT (block), value_id))
    3969              :         {
    3970            0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3971              :             {
    3972            0 :               fprintf (dump_file,
    3973              :                        "Already inserted expression for ");
    3974            0 :               print_pre_expr (dump_file, expr);
    3975            0 :               fprintf (dump_file, " (%04d)\n", value_id);
    3976              :             }
    3977           36 :           continue;
    3978              :         }
    3979              : 
    3980              :       /* If we end up with a punned expression representation and this
    3981              :          happens to be a float typed one give up - we can't know for
    3982              :          sure whether all paths perform the floating-point load we are
    3983              :          about to insert and on some targets this can cause correctness
    3984              :          issues.  See PR88240.  */
    3985       225793 :       if (expr->kind == REFERENCE
    3986        99774 :           && PRE_EXPR_REFERENCE (expr)->punned
    3987       225793 :           && FLOAT_TYPE_P (get_expr_type (expr)))
    3988            0 :         continue;
    3989              : 
    3990              :       /* Only hoist if the full expression is available for hoisting.
    3991              :          This avoids hoisting values that are not common and for
    3992              :          example evaluate an expression that's not valid to evaluate
    3993              :          unconditionally (PR112310).  */
    3994       225793 :       if (!valid_in_sets (&hoistable_set, AVAIL_OUT (block), expr))
    3995           10 :         continue;
    3996              : 
    3997              :       /* OK, we should hoist this value.  Perform the transformation.  */
    3998       225783 :       pre_stats.hoist_insert++;
    3999       225783 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4000              :         {
    4001            2 :           fprintf (dump_file,
    4002              :                    "Inserting expression in block %d for code hoisting: ",
    4003              :                    block->index);
    4004            2 :           print_pre_expr (dump_file, expr);
    4005            2 :           fprintf (dump_file, " (%04d)\n", value_id);
    4006              :         }
    4007              : 
    4008       225783 :       gimple_seq stmts = NULL;
    4009       225783 :       tree res = create_expression_by_pieces (block, expr, &stmts,
    4010              :                                               get_expr_type (expr));
    4011              : 
    4012              :       /* Do not return true if expression creation ultimately
    4013              :          did not insert any statements.  */
    4014       225783 :       if (gimple_seq_empty_p (stmts))
    4015              :         res = NULL_TREE;
    4016              :       else
    4017              :         {
    4018       225757 :           if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
    4019       225757 :             gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
    4020              :           else
    4021            0 :             gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT);
    4022              :         }
    4023              : 
    4024              :       /* Make sure to not return true if expression creation ultimately
    4025              :          failed but also make sure to insert any stmts produced as they
    4026              :          are tracked in inserted_exprs.  */
    4027       225757 :       if (! res)
    4028           26 :         continue;
    4029              : 
    4030       225757 :       new_stuff = true;
    4031              :     }
    4032              : 
    4033       143463 :   exprs.release ();
    4034       143463 :   bitmap_clear (&hoistable_set.values);
    4035       143463 :   bitmap_set_free (ANTIC_OUT);
    4036              : 
    4037       143463 :   return new_stuff;
    4038              : }
    4039              : 
    4040              : /* Perform insertion of partially redundant and hoistable values.  */
    4041              : 
    4042              : static void
    4043       982963 : insert (void)
    4044              : {
    4045       982963 :   basic_block bb;
    4046              : 
    4047     16387766 :   FOR_ALL_BB_FN (bb, cfun)
    4048     15404803 :     NEW_SETS (bb) = bitmap_set_new ();
    4049              : 
    4050       982963 :   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
    4051       982963 :   int *bb_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
    4052       982963 :   int rpo_num = pre_and_rev_post_order_compute (NULL, rpo, false);
    4053     15404803 :   for (int i = 0; i < rpo_num; ++i)
    4054     13438877 :     bb_rpo[rpo[i]] = i;
    4055              : 
    4056              :   int num_iterations = 0;
    4057      1035677 :   bool changed;
    4058      1035677 :   do
    4059              :     {
    4060      1035677 :       num_iterations++;
    4061      1035677 :       if (dump_file && dump_flags & TDF_DETAILS)
    4062           18 :         fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
    4063              : 
    4064      1035677 :       changed = false;
    4065     18721449 :       for (int idx = 0; idx < rpo_num; ++idx)
    4066              :         {
    4067     17685772 :           basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
    4068     17685772 :           basic_block dom = get_immediate_dominator (CDI_DOMINATORS, block);
    4069     17685772 :           if (dom)
    4070              :             {
    4071     17685772 :               unsigned i;
    4072     17685772 :               bitmap_iterator bi;
    4073     17685772 :               bitmap_set_t newset;
    4074              : 
    4075              :               /* First, update the AVAIL_OUT set with anything we may have
    4076              :                  inserted higher up in the dominator tree.  */
    4077     17685772 :               newset = NEW_SETS (dom);
    4078              : 
    4079              :               /* Note that we need to value_replace both NEW_SETS, and
    4080              :                  AVAIL_OUT. For both the case of NEW_SETS, the value may be
    4081              :                  represented by some non-simple expression here that we want
    4082              :                  to replace it with.  */
    4083     17685772 :               bool avail_out_changed = false;
    4084     33681478 :               FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
    4085              :                 {
    4086     15995706 :                   pre_expr expr = expression_for_id (i);
    4087     15995706 :                   bitmap_value_replace_in_set (NEW_SETS (block), expr);
    4088     15995706 :                   avail_out_changed
    4089     15995706 :                     |= bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
    4090              :                 }
    4091              :               /* We need to iterate if AVAIL_OUT of an already processed
    4092              :                  block source changed.  */
    4093     17685772 :               if (avail_out_changed && !changed)
    4094              :                 {
    4095      1754677 :                   edge_iterator ei;
    4096      1754677 :                   edge e;
    4097      4180946 :                   FOR_EACH_EDGE (e, ei, block->succs)
    4098      2426269 :                     if (e->dest->index != EXIT_BLOCK
    4099      2317036 :                         && bb_rpo[e->dest->index] < idx)
    4100      2426269 :                       changed = true;
    4101              :                 }
    4102              : 
    4103              :               /* Insert expressions for partial redundancies.  */
    4104     35370626 :               if (flag_tree_pre && !single_pred_p (block))
    4105              :                 {
    4106      3455412 :                   vec<pre_expr> exprs
    4107      3455412 :                     = sorted_array_from_bitmap_set (ANTIC_IN (block), true);
    4108              :                   /* Sorting is not perfect, iterate locally.  */
    4109      7182763 :                   while (do_pre_regular_insertion (block, dom, exprs))
    4110              :                     ;
    4111      3455412 :                   exprs.release ();
    4112      3455412 :                   if (do_partial_partial)
    4113              :                     {
    4114       336171 :                       exprs = sorted_array_from_bitmap_set (PA_IN (block),
    4115              :                                                             true);
    4116       675372 :                       while (do_pre_partial_partial_insertion (block, dom,
    4117              :                                                                exprs))
    4118              :                         ;
    4119       336171 :                       exprs.release ();
    4120              :                     }
    4121              :                 }
    4122              :             }
    4123              :         }
    4124              : 
    4125              :       /* Clear the NEW sets before the next iteration.  We have already
    4126              :          fully propagated its contents.  */
    4127      1035677 :       if (changed)
    4128      4405037 :         FOR_ALL_BB_FN (bb, cfun)
    4129      8704646 :           bitmap_set_free (NEW_SETS (bb));
    4130              :     }
    4131              :   while (changed);
    4132              : 
    4133       982963 :   statistics_histogram_event (cfun, "insert iterations", num_iterations);
    4134              : 
    4135              :   /* AVAIL_OUT is not needed after insertion so we don't have to
    4136              :      propagate NEW_SETS from hoist insertion.  */
    4137     16387766 :   FOR_ALL_BB_FN (bb, cfun)
    4138              :     {
    4139     15404803 :       bitmap_set_free (NEW_SETS (bb));
    4140     15404803 :       bitmap_set_pool.remove (NEW_SETS (bb));
    4141     15404803 :       NEW_SETS (bb) = NULL;
    4142              :     }
    4143              : 
    4144              :   /* Insert expressions for hoisting.  Do a backward walk here since
    4145              :      inserting into BLOCK exposes new opportunities in its predecessors.
    4146              :      Since PRE and hoist insertions can cause back-to-back iteration
    4147              :      and we are interested in PRE insertion exposed hoisting opportunities
    4148              :      but not in hoisting exposed PRE ones do hoist insertion only after
    4149              :      PRE insertion iteration finished and do not iterate it.  */
    4150       982963 :   if (flag_code_hoisting)
    4151     14421291 :     for (int idx = rpo_num - 1; idx >= 0; --idx)
    4152              :       {
    4153     13438381 :         basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
    4154     18261494 :         if (EDGE_COUNT (block->succs) >= 2)
    4155      4823113 :           changed |= do_hoist_insertion (block);
    4156              :       }
    4157              : 
    4158       982963 :   free (rpo);
    4159       982963 :   free (bb_rpo);
    4160       982963 : }
    4161              : 
    4162              : 
    4163              : /* Compute the AVAIL set for all basic blocks.
    4164              : 
    4165              :    This function performs value numbering of the statements in each basic
    4166              :    block.  The AVAIL sets are built from information we glean while doing
    4167              :    this value numbering, since the AVAIL sets contain only one entry per
    4168              :    value.
    4169              : 
    4170              :    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
    4171              :    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
    4172              : 
    4173              : static void
    4174       982963 : compute_avail (function *fun)
    4175              : {
    4176              : 
    4177       982963 :   basic_block block, son;
    4178       982963 :   basic_block *worklist;
    4179       982963 :   size_t sp = 0;
    4180       982963 :   unsigned i;
    4181       982963 :   tree name;
    4182              : 
    4183              :   /* We pretend that default definitions are defined in the entry block.
    4184              :      This includes function arguments and the static chain decl.  */
    4185     48233461 :   FOR_EACH_SSA_NAME (i, name, fun)
    4186              :     {
    4187     34446058 :       pre_expr e;
    4188     34446058 :       if (!SSA_NAME_IS_DEFAULT_DEF (name)
    4189      2967436 :           || has_zero_uses (name)
    4190     36871777 :           || virtual_operand_p (name))
    4191     33002492 :         continue;
    4192              : 
    4193      1443566 :       e = get_or_alloc_expr_for_name (name);
    4194      1443566 :       add_to_value (get_expr_value_id (e), e);
    4195      1443566 :       bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)), e);
    4196      1443566 :       bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
    4197              :                                     e);
    4198              :     }
    4199              : 
    4200       982963 :   if (dump_file && (dump_flags & TDF_DETAILS))
    4201              :     {
    4202           14 :       print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)),
    4203              :                         "tmp_gen", ENTRY_BLOCK);
    4204           14 :       print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
    4205              :                         "avail_out", ENTRY_BLOCK);
    4206              :     }
    4207              : 
    4208              :   /* Allocate the worklist.  */
    4209       982963 :   worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
    4210              : 
    4211              :   /* Seed the algorithm by putting the dominator children of the entry
    4212              :      block on the worklist.  */
    4213       982963 :   for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (fun));
    4214      1965926 :        son;
    4215       982963 :        son = next_dom_son (CDI_DOMINATORS, son))
    4216       982963 :     worklist[sp++] = son;
    4217              : 
    4218      1965926 :   BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (fun))
    4219       982963 :     = ssa_default_def (fun, gimple_vop (fun));
    4220              : 
    4221              :   /* Loop until the worklist is empty.  */
    4222     14421840 :   while (sp)
    4223              :     {
    4224     13438877 :       gimple *stmt;
    4225     13438877 :       basic_block dom;
    4226              : 
    4227              :       /* Pick a block from the worklist.  */
    4228     13438877 :       block = worklist[--sp];
    4229     13438877 :       vn_context_bb = block;
    4230              : 
    4231              :       /* Initially, the set of available values in BLOCK is that of
    4232              :          its immediate dominator.  */
    4233     13438877 :       dom = get_immediate_dominator (CDI_DOMINATORS, block);
    4234     13438877 :       if (dom)
    4235              :         {
    4236     13438877 :           bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
    4237     13438877 :           BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom);
    4238              :         }
    4239              : 
    4240              :       /* Generate values for PHI nodes.  */
    4241     17345787 :       for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
    4242      3906910 :            gsi_next (&gsi))
    4243              :         {
    4244      3906910 :           tree result = gimple_phi_result (gsi.phi ());
    4245              : 
    4246              :           /* We have no need for virtual phis, as they don't represent
    4247              :              actual computations.  */
    4248      7813820 :           if (virtual_operand_p (result))
    4249              :             {
    4250      1773763 :               BB_LIVE_VOP_ON_EXIT (block) = result;
    4251      1773763 :               continue;
    4252              :             }
    4253              : 
    4254      2133147 :           pre_expr e = get_or_alloc_expr_for_name (result);
    4255      2133147 :           add_to_value (get_expr_value_id (e), e);
    4256      2133147 :           bitmap_value_insert_into_set (AVAIL_OUT (block), e);
    4257      2133147 :           bitmap_insert_into_set (PHI_GEN (block), e);
    4258              :         }
    4259              : 
    4260     13438877 :       BB_MAY_NOTRETURN (block) = 0;
    4261              : 
    4262              :       /* Now compute value numbers and populate value sets with all
    4263              :          the expressions computed in BLOCK.  */
    4264     13438877 :       bool set_bb_may_notreturn = false;
    4265    112729643 :       for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
    4266     85851889 :            gsi_next (&gsi))
    4267              :         {
    4268     85851889 :           ssa_op_iter iter;
    4269     85851889 :           tree op;
    4270              : 
    4271     85851889 :           stmt = gsi_stmt (gsi);
    4272              : 
    4273     85851889 :           if (set_bb_may_notreturn)
    4274              :             {
    4275      2781327 :               BB_MAY_NOTRETURN (block) = 1;
    4276      2781327 :               set_bb_may_notreturn = false;
    4277              :             }
    4278              : 
    4279              :           /* Cache whether the basic-block has any non-visible side-effect
    4280              :              or control flow.
    4281              :              If this isn't a call or it is the last stmt in the
    4282              :              basic-block then the CFG represents things correctly.  */
    4283     85851889 :           if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
    4284              :             {
    4285              :               /* Non-looping const functions always return normally.
    4286              :                  Otherwise the call might not return or have side-effects
    4287              :                  that forbids hoisting possibly trapping expressions
    4288              :                  before it.  */
    4289      3913927 :               int flags = gimple_call_flags (stmt);
    4290      3913927 :               if (!(flags & (ECF_CONST|ECF_PURE))
    4291       594017 :                   || (flags & ECF_LOOPING_CONST_OR_PURE)
    4292      4480811 :                   || stmt_can_throw_external (fun, stmt))
    4293              :                 /* Defer setting of BB_MAY_NOTRETURN to avoid it
    4294              :                    influencing the processing of the call itself.  */
    4295              :                 set_bb_may_notreturn = true;
    4296              :             }
    4297              : 
    4298    101083936 :           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
    4299              :             {
    4300     15232047 :               pre_expr e = get_or_alloc_expr_for_name (op);
    4301     15232047 :               add_to_value (get_expr_value_id (e), e);
    4302     15232047 :               bitmap_insert_into_set (TMP_GEN (block), e);
    4303     15232047 :               bitmap_value_insert_into_set (AVAIL_OUT (block), e);
    4304              :             }
    4305              : 
    4306    113381510 :           if (gimple_vdef (stmt))
    4307     12248839 :             BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
    4308              : 
    4309     85851889 :           if (gimple_has_side_effects (stmt)
    4310     79380728 :               || stmt_could_throw_p (fun, stmt)
    4311    164066842 :               || is_gimple_debug (stmt))
    4312     80499913 :             continue;
    4313              : 
    4314     48014460 :           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
    4315              :             {
    4316     22617980 :               if (ssa_undefined_value_p (op))
    4317        56854 :                 continue;
    4318     22561126 :               pre_expr e = get_or_alloc_expr_for_name (op);
    4319     22561126 :               bitmap_value_insert_into_set (EXP_GEN (block), e);
    4320              :             }
    4321              : 
    4322     25396480 :           switch (gimple_code (stmt))
    4323              :             {
    4324       957898 :             case GIMPLE_RETURN:
    4325       957898 :               continue;
    4326              : 
    4327       564887 :             case GIMPLE_CALL:
    4328       564887 :               {
    4329       564887 :                 vn_reference_t ref;
    4330       564887 :                 vn_reference_s ref1;
    4331       564887 :                 pre_expr result = NULL;
    4332              : 
    4333       564887 :                 vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
    4334              :                 /* There is no point to PRE a call without a value.  */
    4335       564887 :                 if (!ref || !ref->result)
    4336        31666 :                   continue;
    4337              : 
    4338              :                 /* If the value of the call is not invalidated in
    4339              :                    this block until it is computed, add the expression
    4340              :                    to EXP_GEN.  */
    4341       533221 :                 if ((!gimple_vuse (stmt)
    4342       305268 :                      || gimple_code
    4343       305268 :                           (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI
    4344       277127 :                      || gimple_bb (SSA_NAME_DEF_STMT
    4345              :                                    (gimple_vuse (stmt))) != block)
    4346              :                     /* If the REFERENCE traps and there was a preceding
    4347              :                        point in the block that might not return avoid
    4348              :                        adding the reference to EXP_GEN.  */
    4349       781598 :                     && (!BB_MAY_NOTRETURN (block)
    4350        10304 :                         || !vn_reference_may_trap (ref)))
    4351              :                   {
    4352       466026 :                     result = get_or_alloc_expr_for_reference
    4353       466026 :                                (ref, ref->value_id, gimple_location (stmt));
    4354       466026 :                     add_to_value (get_expr_value_id (result), result);
    4355       466026 :                     bitmap_value_insert_into_set (EXP_GEN (block), result);
    4356              :                   }
    4357       533221 :                 continue;
    4358       533221 :               }
    4359              : 
    4360     18521719 :             case GIMPLE_ASSIGN:
    4361     18521719 :               {
    4362     18521719 :                 pre_expr result = NULL;
    4363     18521719 :                 switch (vn_get_stmt_kind (stmt))
    4364              :                   {
    4365      7714753 :                   case VN_NARY:
    4366      7714753 :                     {
    4367      7714753 :                       enum tree_code code = gimple_assign_rhs_code (stmt);
    4368      7714753 :                       vn_nary_op_t nary;
    4369              : 
    4370              :                       /* COND_EXPR is awkward in that it contains an
    4371              :                          embedded complex expression.
    4372              :                          Don't even try to shove it through PRE.  */
    4373      7714753 :                       if (code == COND_EXPR)
    4374       149450 :                         continue;
    4375              : 
    4376      7710463 :                       vn_nary_op_lookup_stmt (stmt, &nary);
    4377      7710463 :                       if (!nary || nary->predicated_values)
    4378       113037 :                         continue;
    4379              : 
    4380      7597426 :                       unsigned value_id = nary->value_id;
    4381      7597426 :                       if (value_id_constant_p (value_id))
    4382            0 :                         continue;
    4383              : 
    4384              :                       /* Record the un-valueized expression for EXP_GEN.  */
    4385      7597426 :                       nary = XALLOCAVAR (struct vn_nary_op_s,
    4386              :                                          sizeof_vn_nary_op
    4387              :                                            (vn_nary_length_from_stmt (stmt)));
    4388      7597426 :                       init_vn_nary_op_from_stmt (nary, as_a <gassign *> (stmt));
    4389              : 
    4390              :                       /* If the NARY traps and there was a preceding
    4391              :                          point in the block that might not return avoid
    4392              :                          adding the nary to EXP_GEN.  */
    4393      7629549 :                       if (BB_MAY_NOTRETURN (block)
    4394      7597426 :                           && vn_nary_may_trap (nary))
    4395        32123 :                         continue;
    4396              : 
    4397      7565303 :                       result = get_or_alloc_expr_for_nary
    4398      7565303 :                                  (nary, value_id, gimple_location (stmt));
    4399      7565303 :                       break;
    4400              :                     }
    4401              : 
    4402      5212524 :                   case VN_REFERENCE:
    4403      5212524 :                     {
    4404      5212524 :                       tree rhs1 = gimple_assign_rhs1 (stmt);
    4405              :                       /* There is no point in trying to handle aggregates,
    4406              :                          even when via punning we might get a value number
    4407              :                          corresponding to a register typed load.  */
    4408      5212524 :                       if (!is_gimple_reg_type (TREE_TYPE (rhs1)))
    4409      1493263 :                         continue;
    4410      4844072 :                       ao_ref rhs1_ref;
    4411      4844072 :                       ao_ref_init (&rhs1_ref, rhs1);
    4412      4844072 :                       alias_set_type set = ao_ref_alias_set (&rhs1_ref);
    4413      4844072 :                       alias_set_type base_set
    4414      4844072 :                         = ao_ref_base_alias_set (&rhs1_ref);
    4415      4844072 :                       vec<vn_reference_op_s> operands
    4416      4844072 :                         = vn_reference_operands_for_lookup (rhs1);
    4417      4844072 :                       vn_reference_t ref;
    4418              : 
    4419              :                       /* We handle &MEM[ptr + 5].b[1].c as
    4420              :                          POINTER_PLUS_EXPR.  */
    4421      4844072 :                       if (operands[0].opcode == ADDR_EXPR
    4422      5104205 :                           && operands.last ().opcode == SSA_NAME)
    4423              :                         {
    4424       260122 :                           tree ops[2];
    4425       260122 :                           if (vn_pp_nary_for_addr (operands, ops))
    4426              :                             {
    4427       173129 :                               vn_nary_op_t nary;
    4428       173129 :                               vn_nary_op_lookup_pieces (2, POINTER_PLUS_EXPR,
    4429       173129 :                                                         TREE_TYPE (rhs1), ops,
    4430              :                                                         &nary);
    4431       173129 :                               operands.release ();
    4432       173129 :                               if (nary && !nary->predicated_values)
    4433              :                                 {
    4434       173127 :                                   unsigned value_id = nary->value_id;
    4435       173127 :                                   if (value_id_constant_p (value_id))
    4436            2 :                                     continue;
    4437       173127 :                                   result = get_or_alloc_expr_for_nary
    4438       173127 :                                       (nary, value_id, gimple_location (stmt));
    4439       173127 :                                   break;
    4440              :                                 }
    4441            2 :                               continue;
    4442            2 :                             }
    4443              :                         }
    4444              : 
    4445      9341886 :                       vn_reference_lookup_pieces (gimple_vuse (stmt), set,
    4446      4670943 :                                                   base_set, TREE_TYPE (rhs1),
    4447              :                                                   operands, &ref, VN_WALK);
    4448              :                       /* When there is no value recorded or the value was
    4449              :                          recorded for a different type, fail, similar as
    4450              :                          how we do during PHI translation.  */
    4451      4673987 :                       if (!ref
    4452      4670943 :                           || !useless_type_conversion_p (TREE_TYPE (rhs1),
    4453              :                                                          ref->type))
    4454              :                         {
    4455         3044 :                           operands.release ();
    4456         3044 :                           continue;
    4457              :                         }
    4458      4667899 :                       operands.release ();
    4459              : 
    4460              :                       /* If the REFERENCE traps and there was a preceding
    4461              :                          point in the block that might not return avoid
    4462              :                          adding the reference to EXP_GEN.  */
    4463      4806591 :                       if (BB_MAY_NOTRETURN (block)
    4464      4667899 :                           && gimple_could_trap_p_1 (stmt, true, false))
    4465       138692 :                         continue;
    4466              : 
    4467              :                       /* If the value of the reference is not invalidated in
    4468              :                          this block until it is computed, add the expression
    4469              :                          to EXP_GEN.  */
    4470      9058414 :                       if (gimple_vuse (stmt))
    4471              :                         {
    4472      4442219 :                           gimple *def_stmt;
    4473      4442219 :                           bool ok = true;
    4474      4442219 :                           def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt));
    4475      7184241 :                           while (!gimple_nop_p (def_stmt)
    4476      6187263 :                                  && gimple_code (def_stmt) != GIMPLE_PHI
    4477     12159187 :                                  && gimple_bb (def_stmt) == block)
    4478              :                             {
    4479      3725095 :                               if (stmt_may_clobber_ref_p
    4480      3725095 :                                     (def_stmt, gimple_assign_rhs1 (stmt)))
    4481              :                                 {
    4482              :                                   ok = false;
    4483              :                                   break;
    4484              :                                 }
    4485      2742022 :                               def_stmt
    4486      2742022 :                                 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt));
    4487              :                             }
    4488      4442219 :                           if (!ok)
    4489       983073 :                             continue;
    4490              :                         }
    4491              : 
    4492              :                       /* Record the un-valueized expression for EXP_GEN.  */
    4493      3546134 :                       copy_reference_ops_from_ref (rhs1, &operands);
    4494      3546134 :                       vn_reference_t newref
    4495      3546134 :                         = XALLOCAVAR (struct vn_reference_s,
    4496              :                                       sizeof (vn_reference_s));
    4497      3546134 :                       memset (newref, 0, sizeof (vn_reference_s));
    4498      3546134 :                       newref->value_id = ref->value_id;
    4499      3546134 :                       newref->vuse = ref->vuse;
    4500      3546134 :                       newref->operands = operands;
    4501      3546134 :                       newref->type = TREE_TYPE (rhs1);
    4502      3546134 :                       newref->set = set;
    4503      3546134 :                       newref->base_set = base_set;
    4504      3546134 :                       newref->offset = 0;
    4505      3546134 :                       newref->max_size = -1;
    4506      3546134 :                       newref->result = ref->result;
    4507      3546134 :                       newref->hashcode = vn_reference_compute_hash (newref);
    4508              : 
    4509      3546134 :                       result = get_or_alloc_expr_for_reference
    4510      3546134 :                                  (newref, newref->value_id,
    4511              :                                   gimple_location (stmt), true);
    4512      3546134 :                       break;
    4513              :                     }
    4514              : 
    4515      5594442 :                   default:
    4516      5594442 :                     continue;
    4517      5594442 :                   }
    4518              : 
    4519     11284564 :                 add_to_value (get_expr_value_id (result), result);
    4520     11284564 :                 bitmap_value_insert_into_set (EXP_GEN (block), result);
    4521     11284564 :                 continue;
    4522     11284564 :               }
    4523      5351976 :             default:
    4524      5351976 :               break;
    4525       957898 :             }
    4526              :         }
    4527     13438877 :       if (set_bb_may_notreturn)
    4528              :         {
    4529       567711 :           BB_MAY_NOTRETURN (block) = 1;
    4530       567711 :           set_bb_may_notreturn = false;
    4531              :         }
    4532              : 
    4533     13438877 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4534              :         {
    4535          108 :           print_bitmap_set (dump_file, EXP_GEN (block),
    4536              :                             "exp_gen", block->index);
    4537          108 :           print_bitmap_set (dump_file, PHI_GEN (block),
    4538              :                             "phi_gen", block->index);
    4539          108 :           print_bitmap_set (dump_file, TMP_GEN (block),
    4540              :                             "tmp_gen", block->index);
    4541          108 :           print_bitmap_set (dump_file, AVAIL_OUT (block),
    4542              :                             "avail_out", block->index);
    4543              :         }
    4544              : 
    4545              :       /* Put the dominator children of BLOCK on the worklist of blocks
    4546              :          to compute available sets for.  */
    4547     13438877 :       for (son = first_dom_son (CDI_DOMINATORS, block);
    4548     25894791 :            son;
    4549     12455914 :            son = next_dom_son (CDI_DOMINATORS, son))
    4550     12455914 :         worklist[sp++] = son;
    4551              :     }
    4552       982963 :   vn_context_bb = NULL;
    4553              : 
    4554       982963 :   free (worklist);
    4555       982963 : }
    4556              : 
    4557              : 
    4558              : /* Initialize data structures used by PRE.  */
    4559              : 
    4560              : static void
    4561       982970 : init_pre (void)
    4562              : {
    4563       982970 :   basic_block bb;
    4564              : 
    4565       982970 :   next_expression_id = 1;
    4566       982970 :   expressions.create (0);
    4567       982970 :   expressions.safe_push (NULL);
    4568       982970 :   value_expressions.create (get_max_value_id () + 1);
    4569       982970 :   value_expressions.quick_grow_cleared (get_max_value_id () + 1);
    4570       982970 :   constant_value_expressions.create (get_max_constant_value_id () + 1);
    4571       982970 :   constant_value_expressions.quick_grow_cleared (get_max_constant_value_id () + 1);
    4572       982970 :   name_to_id.create (0);
    4573       982970 :   gcc_obstack_init (&pre_expr_obstack);
    4574              : 
    4575       982970 :   inserted_exprs = BITMAP_ALLOC (NULL);
    4576              : 
    4577       982970 :   connect_infinite_loops_to_exit ();
    4578       982970 :   memset (&pre_stats, 0, sizeof (pre_stats));
    4579              : 
    4580       982970 :   alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
    4581              : 
    4582       982970 :   calculate_dominance_info (CDI_DOMINATORS);
    4583              : 
    4584       982970 :   bitmap_obstack_initialize (&grand_bitmap_obstack);
    4585      1965940 :   expression_to_id = new hash_table<pre_expr_d> (num_ssa_names * 3);
    4586     16425337 :   FOR_ALL_BB_FN (bb, cfun)
    4587              :     {
    4588     15442367 :       EXP_GEN (bb) = bitmap_set_new ();
    4589     15442367 :       PHI_GEN (bb) = bitmap_set_new ();
    4590     15442367 :       TMP_GEN (bb) = bitmap_set_new ();
    4591     15442367 :       AVAIL_OUT (bb) = bitmap_set_new ();
    4592     15442367 :       PHI_TRANS_TABLE (bb) = NULL;
    4593              :     }
    4594       982970 : }
    4595              : 
    4596              : 
    4597              : /* Deallocate data structures used by PRE.  */
    4598              : 
    4599              : static void
    4600       982970 : fini_pre ()
    4601              : {
    4602       982970 :   value_expressions.release ();
    4603       982970 :   constant_value_expressions.release ();
    4604     46319211 :   for (unsigned i = 1; i < expressions.length (); ++i)
    4605     44353271 :     if (expressions[i]->kind == REFERENCE)
    4606      6462255 :       PRE_EXPR_REFERENCE (expressions[i])->operands.release ();
    4607       982970 :   expressions.release ();
    4608       982970 :   bitmap_obstack_release (&grand_bitmap_obstack);
    4609       982970 :   bitmap_set_pool.release ();
    4610       982970 :   pre_expr_pool.release ();
    4611       982970 :   delete expression_to_id;
    4612       982970 :   expression_to_id = NULL;
    4613       982970 :   name_to_id.release ();
    4614       982970 :   obstack_free (&pre_expr_obstack, NULL);
    4615              : 
    4616       982970 :   basic_block bb;
    4617     16425023 :   FOR_ALL_BB_FN (bb, cfun)
    4618     15442053 :     if (bb->aux && PHI_TRANS_TABLE (bb))
    4619      6229418 :       delete PHI_TRANS_TABLE (bb);
    4620       982970 :   free_aux_for_blocks ();
    4621       982970 : }
    4622              : 
    4623              : namespace {
    4624              : 
    4625              : const pass_data pass_data_pre =
    4626              : {
    4627              :   GIMPLE_PASS, /* type */
    4628              :   "pre", /* name */
    4629              :   OPTGROUP_NONE, /* optinfo_flags */
    4630              :   TV_TREE_PRE, /* tv_id */
    4631              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    4632              :   0, /* properties_provided */
    4633              :   0, /* properties_destroyed */
    4634              :   TODO_rebuild_alias, /* todo_flags_start */
    4635              :   0, /* todo_flags_finish */
    4636              : };
    4637              : 
    4638              : class pass_pre : public gimple_opt_pass
    4639              : {
    4640              : public:
    4641       297180 :   pass_pre (gcc::context *ctxt)
    4642       594360 :     : gimple_opt_pass (pass_data_pre, ctxt)
    4643              :   {}
    4644              : 
    4645              :   /* opt_pass methods: */
    4646      1063018 :   bool gate (function *) final override
    4647      1063018 :     { return flag_tree_pre != 0 || flag_code_hoisting != 0; }
    4648              :   unsigned int execute (function *) final override;
    4649              : 
    4650              : }; // class pass_pre
    4651              : 
    4652              : /* Valueization hook for RPO VN when we are calling back to it
    4653              :    at ANTIC compute time.  */
    4654              : 
    4655              : static tree
    4656    127101893 : pre_valueize (tree name)
    4657              : {
    4658    127101893 :   if (TREE_CODE (name) == SSA_NAME)
    4659              :     {
    4660    126830806 :       tree tem = VN_INFO (name)->valnum;
    4661    126830806 :       if (tem != VN_TOP && tem != name)
    4662              :         {
    4663     16829415 :           if (TREE_CODE (tem) != SSA_NAME
    4664     16829415 :               || SSA_NAME_IS_DEFAULT_DEF (tem))
    4665              :             return tem;
    4666              :           /* We create temporary SSA names for representatives that
    4667              :              do not have a definition (yet) but are not default defs either
    4668              :              assume they are fine to use.  */
    4669     16824385 :           basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem));
    4670     16824385 :           if (! def_bb
    4671     16824385 :               || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
    4672       139256 :             return tem;
    4673              :           /* ??? Now we could look for a leader.  Ideally we'd somehow
    4674              :              expose RPO VN leaders and get rid of AVAIL_OUT as well...  */
    4675              :         }
    4676              :     }
    4677              :   return name;
    4678              : }
    4679              : 
    4680              : unsigned int
    4681       982970 : pass_pre::execute (function *fun)
    4682              : {
    4683       982970 :   unsigned int todo = 0;
    4684              : 
    4685      1965940 :   do_partial_partial =
    4686       982970 :     flag_tree_partial_pre && optimize_function_for_speed_p (fun);
    4687              : 
    4688              :   /* This has to happen before VN runs because
    4689              :      loop_optimizer_init may create new phis, etc.  */
    4690       982970 :   loop_optimizer_init (LOOPS_NORMAL);
    4691       982970 :   split_edges_for_insertion ();
    4692       982970 :   scev_initialize ();
    4693       982970 :   calculate_dominance_info (CDI_DOMINATORS);
    4694              : 
    4695       982970 :   vn_driver *vn = new vn_driver (fun, true, false, true, VN_WALK);
    4696              : 
    4697       982970 :   init_pre ();
    4698              : 
    4699       982970 :   vn_valueize = pre_valueize;
    4700              : 
    4701              :   /* Insert can get quite slow on an incredibly large number of basic
    4702              :      blocks due to some quadratic behavior.  Until this behavior is
    4703              :      fixed, don't run it when he have an incredibly large number of
    4704              :      bb's.  If we aren't going to run insert, there is no point in
    4705              :      computing ANTIC, either, even though it's plenty fast nor do
    4706              :      we require AVAIL.  */
    4707       982970 :   if (n_basic_blocks_for_fn (fun) < 4000)
    4708              :     {
    4709       982963 :       compute_avail (fun);
    4710       982963 :       compute_antic ();
    4711       982963 :       insert ();
    4712              :     }
    4713              : 
    4714              :   /* Make sure to remove fake edges before committing our inserts.
    4715              :      This makes sure we don't end up with extra critical edges that
    4716              :      we would need to split.  */
    4717       982970 :   remove_fake_exit_edges ();
    4718       982970 :   gsi_commit_edge_inserts ();
    4719              : 
    4720              :   /* Eliminate folds statements which might (should not...) end up
    4721              :      not keeping virtual operands up-to-date.  */
    4722       982970 :   gcc_assert (!need_ssa_update_p (fun));
    4723              : 
    4724       982970 :   statistics_counter_event (fun, "Insertions", pre_stats.insertions);
    4725       982970 :   statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
    4726       982970 :   statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
    4727       982970 :   statistics_counter_event (fun, "New PHIs", pre_stats.phis);
    4728              : 
    4729       982970 :   todo |= vn->finalize (inserted_exprs);
    4730              : 
    4731       982970 :   vn_valueize = NULL;
    4732              : 
    4733       982970 :   fini_pre ();
    4734              : 
    4735       982970 :   scev_finalize ();
    4736       982970 :   loop_optimizer_finalize ();
    4737              : 
    4738              :   /* Perform a CFG cleanup before we run simple_dce_from_worklist since
    4739              :      unreachable code regions will have not up-to-date SSA form which
    4740              :      confuses it.  */
    4741       982970 :   bool need_crit_edge_split = false;
    4742       982970 :   if (todo & TODO_cleanup_cfg)
    4743              :     {
    4744       140678 :       cleanup_tree_cfg ();
    4745       140678 :       need_crit_edge_split = true;
    4746              :     }
    4747              : 
    4748              :   /* Because we don't follow exactly the standard PRE algorithm, and decide not
    4749              :      to insert PHI nodes sometimes, and because value numbering of casts isn't
    4750              :      perfect, we sometimes end up inserting dead code.   This simple DCE-like
    4751              :      pass removes any insertions we made that weren't actually used.  */
    4752       982970 :   simple_dce_from_worklist (inserted_exprs);
    4753       982970 :   BITMAP_FREE (inserted_exprs);
    4754              : 
    4755              :   /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
    4756              :      case we can merge the block with the remaining predecessor of the block.
    4757              :      It should either:
    4758              :      - call merge_blocks after each tail merge iteration
    4759              :      - call merge_blocks after all tail merge iterations
    4760              :      - mark TODO_cleanup_cfg when necessary.  */
    4761       982970 :   todo |= tail_merge_optimize (need_crit_edge_split);
    4762              : 
    4763       982970 :   delete vn;
    4764              : 
    4765              :   /* Tail merging invalidates the virtual SSA web, together with
    4766              :      cfg-cleanup opportunities exposed by PRE this will wreck the
    4767              :      SSA updating machinery.  So make sure to run update-ssa
    4768              :      manually, before eventually scheduling cfg-cleanup as part of
    4769              :      the todo.  */
    4770       982970 :   update_ssa (TODO_update_ssa_only_virtuals);
    4771              : 
    4772       982970 :   return todo;
    4773              : }
    4774              : 
    4775              : } // anon namespace
    4776              : 
    4777              : gimple_opt_pass *
    4778       297180 : make_pass_pre (gcc::context *ctxt)
    4779              : {
    4780       297180 :   return new pass_pre (ctxt);
    4781              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.