LCOV - code coverage report
Current view: top level - gcc - tree-ssa-pre.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1773 1909 92.9 %
Date: 2020-04-04 11:58:09 Functions: 55 63 87.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
       2                 :            :    Copyright (C) 2001-2020 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-fold.h"
      38                 :            : #include "tree-eh.h"
      39                 :            : #include "gimplify.h"
      40                 :            : #include "gimple-iterator.h"
      41                 :            : #include "tree-cfg.h"
      42                 :            : #include "tree-into-ssa.h"
      43                 :            : #include "tree-dfa.h"
      44                 :            : #include "tree-ssa.h"
      45                 :            : #include "cfgloop.h"
      46                 :            : #include "tree-ssa-sccvn.h"
      47                 :            : #include "tree-scalar-evolution.h"
      48                 :            : #include "dbgcnt.h"
      49                 :            : #include "domwalk.h"
      50                 :            : #include "tree-ssa-propagate.h"
      51                 :            : #include "tree-ssa-dce.h"
      52                 :            : #include "tree-cfgcleanup.h"
      53                 :            : #include "alias.h"
      54                 :            : 
      55                 :            : /* Even though this file is called tree-ssa-pre.c, 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.c.
      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                 :            :   location_t loc;
     260                 :            :   pre_expr_union u;
     261                 :            : 
     262                 :            :   /* hash_table support.  */
     263                 :            :   static inline hashval_t hash (const pre_expr_d *);
     264                 :            :   static inline int equal (const pre_expr_d *, const pre_expr_d *);
     265                 :            : } *pre_expr;
     266                 :            : 
     267                 :            : #define PRE_EXPR_NAME(e) (e)->u.name
     268                 :            : #define PRE_EXPR_NARY(e) (e)->u.nary
     269                 :            : #define PRE_EXPR_REFERENCE(e) (e)->u.reference
     270                 :            : #define PRE_EXPR_CONSTANT(e) (e)->u.constant
     271                 :            : 
     272                 :            : /* Compare E1 and E1 for equality.  */
     273                 :            : 
     274                 :            : inline int
     275                 :  150776000 : pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2)
     276                 :            : {
     277                 :  150776000 :   if (e1->kind != e2->kind)
     278                 :            :     return false;
     279                 :            : 
     280                 :  124123000 :   switch (e1->kind)
     281                 :            :     {
     282                 :    3631880 :     case CONSTANT:
     283                 :    3631880 :       return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
     284                 :    3631880 :                                        PRE_EXPR_CONSTANT (e2));
     285                 :     209007 :     case NAME:
     286                 :     209007 :       return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
     287                 :   86645700 :     case NARY:
     288                 :   86645700 :       return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
     289                 :   33636400 :     case REFERENCE:
     290                 :   33636400 :       return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
     291                 :   33636400 :                               PRE_EXPR_REFERENCE (e2));
     292                 :          0 :     default:
     293                 :          0 :       gcc_unreachable ();
     294                 :            :     }
     295                 :            : }
     296                 :            : 
     297                 :            : /* Hash E.  */
     298                 :            : 
     299                 :            : inline hashval_t
     300                 :  176741000 : pre_expr_d::hash (const pre_expr_d *e)
     301                 :            : {
     302                 :  176741000 :   switch (e->kind)
     303                 :            :     {
     304                 :    5954040 :     case CONSTANT:
     305                 :    5954040 :       return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
     306                 :          0 :     case NAME:
     307                 :          0 :       return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
     308                 :  117361000 :     case NARY:
     309                 :  117361000 :       return PRE_EXPR_NARY (e)->hashcode;
     310                 :   53426700 :     case REFERENCE:
     311                 :   53426700 :       return PRE_EXPR_REFERENCE (e)->hashcode;
     312                 :          0 :     default:
     313                 :          0 :       gcc_unreachable ();
     314                 :            :     }
     315                 :            : }
     316                 :            : 
     317                 :            : /* Next global expression id number.  */
     318                 :            : static unsigned int next_expression_id;
     319                 :            : 
     320                 :            : /* Mapping from expression to id number we can use in bitmap sets.  */
     321                 :            : static vec<pre_expr> expressions;
     322                 :            : static hash_table<pre_expr_d> *expression_to_id;
     323                 :            : static vec<unsigned> name_to_id;
     324                 :            : 
     325                 :            : /* Allocate an expression id for EXPR.  */
     326                 :            : 
     327                 :            : static inline unsigned int
     328                 :   26275700 : alloc_expression_id (pre_expr expr)
     329                 :            : {
     330                 :   26275700 :   struct pre_expr_d **slot;
     331                 :            :   /* Make sure we won't overflow. */
     332                 :   26275700 :   gcc_assert (next_expression_id + 1 > next_expression_id);
     333                 :   26275700 :   expr->id = next_expression_id++;
     334                 :   26275700 :   expressions.safe_push (expr);
     335                 :   26275700 :   if (expr->kind == NAME)
     336                 :            :     {
     337                 :   14768100 :       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
     338                 :            :       /* vec::safe_grow_cleared allocates no headroom.  Avoid frequent
     339                 :            :          re-allocations by using vec::reserve upfront.  */
     340                 :   14768100 :       unsigned old_len = name_to_id.length ();
     341                 :   29536200 :       name_to_id.reserve (num_ssa_names - old_len);
     342                 :   29536200 :       name_to_id.quick_grow_cleared (num_ssa_names);
     343                 :   14768100 :       gcc_assert (name_to_id[version] == 0);
     344                 :   14768100 :       name_to_id[version] = expr->id;
     345                 :            :     }
     346                 :            :   else
     347                 :            :     {
     348                 :   11507500 :       slot = expression_to_id->find_slot (expr, INSERT);
     349                 :   11507500 :       gcc_assert (!*slot);
     350                 :   11507500 :       *slot = expr;
     351                 :            :     }
     352                 :   26275700 :   return next_expression_id - 1;
     353                 :            : }
     354                 :            : 
     355                 :            : /* Return the expression id for tree EXPR.  */
     356                 :            : 
     357                 :            : static inline unsigned int
     358                 :   12821500 : get_expression_id (const pre_expr expr)
     359                 :            : {
     360                 :   12821500 :   return expr->id;
     361                 :            : }
     362                 :            : 
     363                 :            : static inline unsigned int
     364                 :  164159000 : lookup_expression_id (const pre_expr expr)
     365                 :            : {
     366                 :  164159000 :   struct pre_expr_d **slot;
     367                 :            : 
     368                 :  164159000 :   if (expr->kind == NAME)
     369                 :            :     {
     370                 :  115654000 :       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
     371                 :  230741000 :       if (name_to_id.length () <= version)
     372                 :            :         return 0;
     373                 :  113630000 :       return name_to_id[version];
     374                 :            :     }
     375                 :            :   else
     376                 :            :     {
     377                 :   48505100 :       slot = expression_to_id->find_slot (expr, NO_INSERT);
     378                 :   48505100 :       if (!slot)
     379                 :            :         return 0;
     380                 :   36997600 :       return ((pre_expr)*slot)->id;
     381                 :            :     }
     382                 :            : }
     383                 :            : 
     384                 :            : /* Return the existing expression id for EXPR, or create one if one
     385                 :            :    does not exist yet.  */
     386                 :            : 
     387                 :            : static inline unsigned int
     388                 :  126641000 : get_or_alloc_expression_id (pre_expr expr)
     389                 :            : {
     390                 :  126641000 :   unsigned int id = lookup_expression_id (expr);
     391                 :  126641000 :   if (id == 0)
     392                 :   10932700 :     return alloc_expression_id (expr);
     393                 :  115708000 :   return expr->id = id;
     394                 :            : }
     395                 :            : 
     396                 :            : /* Return the expression that has expression id ID */
     397                 :            : 
     398                 :            : static inline pre_expr
     399                 :  258831000 : expression_for_id (unsigned int id)
     400                 :            : {
     401                 :  517661000 :   return expressions[id];
     402                 :            : }
     403                 :            : 
     404                 :            : static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
     405                 :            : 
     406                 :            : /* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */
     407                 :            : 
     408                 :            : static pre_expr
     409                 :   34403400 : get_or_alloc_expr_for_name (tree name)
     410                 :            : {
     411                 :   34403400 :   struct pre_expr_d expr;
     412                 :   34403400 :   pre_expr result;
     413                 :   34403400 :   unsigned int result_id;
     414                 :            : 
     415                 :   34403400 :   expr.kind = NAME;
     416                 :   34403400 :   expr.id = 0;
     417                 :   34403400 :   PRE_EXPR_NAME (&expr) = name;
     418                 :   34403400 :   result_id = lookup_expression_id (&expr);
     419                 :   34403400 :   if (result_id != 0)
     420                 :   19635300 :     return expression_for_id (result_id);
     421                 :            : 
     422                 :   14768100 :   result = pre_expr_pool.allocate ();
     423                 :   14768100 :   result->kind = NAME;
     424                 :   14768100 :   result->loc = UNKNOWN_LOCATION;
     425                 :   14768100 :   PRE_EXPR_NAME (result) = name;
     426                 :   14768100 :   alloc_expression_id (result);
     427                 :   14768100 :   return result;
     428                 :            : }
     429                 :            : 
     430                 :            : /* An unordered bitmap set.  One bitmap tracks values, the other,
     431                 :            :    expressions.  */
     432                 :   89993700 : typedef class bitmap_set
     433                 :            : {
     434                 :            : public:
     435                 :            :   bitmap_head expressions;
     436                 :            :   bitmap_head values;
     437                 :            : } *bitmap_set_t;
     438                 :            : 
     439                 :            : #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi)            \
     440                 :            :   EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
     441                 :            : 
     442                 :            : #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi)           \
     443                 :            :   EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
     444                 :            : 
     445                 :            : /* Mapping from value id to expressions with that value_id.  */
     446                 :            : static vec<bitmap> value_expressions;
     447                 :            : 
     448                 :            : /* Sets that we need to keep track of.  */
     449                 :            : typedef struct bb_bitmap_sets
     450                 :            : {
     451                 :            :   /* The EXP_GEN set, which represents expressions/values generated in
     452                 :            :      a basic block.  */
     453                 :            :   bitmap_set_t exp_gen;
     454                 :            : 
     455                 :            :   /* The PHI_GEN set, which represents PHI results generated in a
     456                 :            :      basic block.  */
     457                 :            :   bitmap_set_t phi_gen;
     458                 :            : 
     459                 :            :   /* The TMP_GEN set, which represents results/temporaries generated
     460                 :            :      in a basic block. IE the LHS of an expression.  */
     461                 :            :   bitmap_set_t tmp_gen;
     462                 :            : 
     463                 :            :   /* The AVAIL_OUT set, which represents which values are available in
     464                 :            :      a given basic block.  */
     465                 :            :   bitmap_set_t avail_out;
     466                 :            : 
     467                 :            :   /* The ANTIC_IN set, which represents which values are anticipatable
     468                 :            :      in a given basic block.  */
     469                 :            :   bitmap_set_t antic_in;
     470                 :            : 
     471                 :            :   /* The PA_IN set, which represents which values are
     472                 :            :      partially anticipatable in a given basic block.  */
     473                 :            :   bitmap_set_t pa_in;
     474                 :            : 
     475                 :            :   /* The NEW_SETS set, which is used during insertion to augment the
     476                 :            :      AVAIL_OUT set of blocks with the new insertions performed during
     477                 :            :      the current iteration.  */
     478                 :            :   bitmap_set_t new_sets;
     479                 :            : 
     480                 :            :   /* A cache for value_dies_in_block_x.  */
     481                 :            :   bitmap expr_dies;
     482                 :            : 
     483                 :            :   /* The live virtual operand on successor edges.  */
     484                 :            :   tree vop_on_exit;
     485                 :            : 
     486                 :            :   /* True if we have visited this block during ANTIC calculation.  */
     487                 :            :   unsigned int visited : 1;
     488                 :            : 
     489                 :            :   /* True when the block contains a call that might not return.  */
     490                 :            :   unsigned int contains_may_not_return_call : 1;
     491                 :            : } *bb_value_sets_t;
     492                 :            : 
     493                 :            : #define EXP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->exp_gen
     494                 :            : #define PHI_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->phi_gen
     495                 :            : #define TMP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->tmp_gen
     496                 :            : #define AVAIL_OUT(BB)   ((bb_value_sets_t) ((BB)->aux))->avail_out
     497                 :            : #define ANTIC_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->antic_in
     498                 :            : #define PA_IN(BB)       ((bb_value_sets_t) ((BB)->aux))->pa_in
     499                 :            : #define NEW_SETS(BB)    ((bb_value_sets_t) ((BB)->aux))->new_sets
     500                 :            : #define EXPR_DIES(BB)   ((bb_value_sets_t) ((BB)->aux))->expr_dies
     501                 :            : #define BB_VISITED(BB)  ((bb_value_sets_t) ((BB)->aux))->visited
     502                 :            : #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
     503                 :            : #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
     504                 :            : 
     505                 :            : 
     506                 :            : /* This structure is used to keep track of statistics on what
     507                 :            :    optimization PRE was able to perform.  */
     508                 :            : static struct
     509                 :            : {
     510                 :            :   /* The number of new expressions/temporaries generated by PRE.  */
     511                 :            :   int insertions;
     512                 :            : 
     513                 :            :   /* The number of inserts found due to partial anticipation  */
     514                 :            :   int pa_insert;
     515                 :            : 
     516                 :            :   /* The number of inserts made for code hoisting.  */
     517                 :            :   int hoist_insert;
     518                 :            : 
     519                 :            :   /* The number of new PHI nodes added by PRE.  */
     520                 :            :   int phis;
     521                 :            : } pre_stats;
     522                 :            : 
     523                 :            : static bool do_partial_partial;
     524                 :            : static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
     525                 :            : static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
     526                 :            : static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
     527                 :            : static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
     528                 :            : static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
     529                 :            : static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
     530                 :            : static bitmap_set_t bitmap_set_new (void);
     531                 :            : static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
     532                 :            :                                          tree);
     533                 :            : static tree find_or_generate_expression (basic_block, tree, gimple_seq *);
     534                 :            : static unsigned int get_expr_value_id (pre_expr);
     535                 :            : 
     536                 :            : /* We can add and remove elements and entries to and from sets
     537                 :            :    and hash tables, so we use alloc pools for them.  */
     538                 :            : 
     539                 :            : static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets");
     540                 :            : static bitmap_obstack grand_bitmap_obstack;
     541                 :            : 
     542                 :            : /* A three tuple {e, pred, v} used to cache phi translations in the
     543                 :            :    phi_translate_table.  */
     544                 :            : 
     545                 :            : typedef struct expr_pred_trans_d : free_ptr_hash<expr_pred_trans_d>
     546                 :            : {
     547                 :            :   /* The expression.  */
     548                 :            :   pre_expr e;
     549                 :            : 
     550                 :            :   /* The predecessor block along which we translated the expression.  */
     551                 :            :   basic_block pred;
     552                 :            : 
     553                 :            :   /* The value that resulted from the translation.  */
     554                 :            :   pre_expr v;
     555                 :            : 
     556                 :            :   /* The hashcode for the expression, pred pair. This is cached for
     557                 :            :      speed reasons.  */
     558                 :            :   hashval_t hashcode;
     559                 :            : 
     560                 :            :   /* hash_table support.  */
     561                 :            :   static inline hashval_t hash (const expr_pred_trans_d *);
     562                 :            :   static inline int equal (const expr_pred_trans_d *, const expr_pred_trans_d *);
     563                 :            : } *expr_pred_trans_t;
     564                 :            : typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
     565                 :            : 
     566                 :            : inline hashval_t
     567                 :  104777000 : expr_pred_trans_d::hash (const expr_pred_trans_d *e)
     568                 :            : {
     569                 :  104777000 :   return e->hashcode;
     570                 :            : }
     571                 :            : 
     572                 :            : inline int
     573                 :  152395000 : expr_pred_trans_d::equal (const expr_pred_trans_d *ve1,
     574                 :            :                           const expr_pred_trans_d *ve2)
     575                 :            : {
     576                 :  152395000 :   basic_block b1 = ve1->pred;
     577                 :  152395000 :   basic_block b2 = ve2->pred;
     578                 :            : 
     579                 :            :   /* If they are not translations for the same basic block, they can't
     580                 :            :      be equal.  */
     581                 :  152395000 :   if (b1 != b2)
     582                 :            :     return false;
     583                 :   39024500 :   return pre_expr_d::equal (ve1->e, ve2->e);
     584                 :            : }
     585                 :            : 
     586                 :            : /* The phi_translate_table caches phi translations for a given
     587                 :            :    expression and predecessor.  */
     588                 :            : static hash_table<expr_pred_trans_d> *phi_translate_table;
     589                 :            : 
     590                 :            : /* Add the tuple mapping from {expression E, basic block PRED} to
     591                 :            :    the phi translation table and return whether it pre-existed.  */
     592                 :            : 
     593                 :            : static inline bool
     594                 :   49070500 : phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
     595                 :            : {
     596                 :   49070500 :   expr_pred_trans_t *slot;
     597                 :   49070500 :   expr_pred_trans_d tem;
     598                 :   98141000 :   hashval_t hash = iterative_hash_hashval_t (pre_expr_d::hash (e),
     599                 :   49070500 :                                              pred->index);
     600                 :   49070500 :   tem.e = e;
     601                 :   49070500 :   tem.pred = pred;
     602                 :   49070500 :   tem.hashcode = hash;
     603                 :   49070500 :   slot = phi_translate_table->find_slot_with_hash (&tem, hash, INSERT);
     604                 :   49070500 :   if (*slot)
     605                 :            :     {
     606                 :   35310200 :       *entry = *slot;
     607                 :   35310200 :       return true;
     608                 :            :     }
     609                 :            : 
     610                 :   13760300 :   *entry = *slot = XNEW (struct expr_pred_trans_d);
     611                 :   13760300 :   (*entry)->e = e;
     612                 :   13760300 :   (*entry)->pred = pred;
     613                 :   13760300 :   (*entry)->hashcode = hash;
     614                 :   13760300 :   return false;
     615                 :            : }
     616                 :            : 
     617                 :            : 
     618                 :            : /* Add expression E to the expression set of value id V.  */
     619                 :            : 
     620                 :            : static void
     621                 :   27024900 : add_to_value (unsigned int v, pre_expr e)
     622                 :            : {
     623                 :   27024900 :   bitmap set;
     624                 :            : 
     625                 :   27024900 :   gcc_checking_assert (get_expr_value_id (e) == v);
     626                 :            : 
     627                 :   54049800 :   if (v >= value_expressions.length ())
     628                 :            :     {
     629                 :     209358 :       value_expressions.safe_grow_cleared (v + 1);
     630                 :            :     }
     631                 :            : 
     632                 :   27024900 :   set = value_expressions[v];
     633                 :   27024900 :   if (!set)
     634                 :            :     {
     635                 :   15870800 :       set = BITMAP_ALLOC (&grand_bitmap_obstack);
     636                 :   15870800 :       value_expressions[v] = set;
     637                 :            :     }
     638                 :            : 
     639                 :   27024900 :   bitmap_set_bit (set, get_or_alloc_expression_id (e));
     640                 :   27024900 : }
     641                 :            : 
     642                 :            : /* Create a new bitmap set and return it.  */
     643                 :            : 
     644                 :            : static bitmap_set_t
     645                 :   89993700 : bitmap_set_new (void)
     646                 :            : {
     647                 :   89993700 :   bitmap_set_t ret = bitmap_set_pool.allocate ();
     648                 :   89993700 :   bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
     649                 :   89993700 :   bitmap_initialize (&ret->values, &grand_bitmap_obstack);
     650                 :   89993700 :   return ret;
     651                 :            : }
     652                 :            : 
     653                 :            : /* Return the value id for a PRE expression EXPR.  */
     654                 :            : 
     655                 :            : static unsigned int
     656                 :  353562000 : get_expr_value_id (pre_expr expr)
     657                 :            : {
     658                 :  353562000 :   unsigned int id;
     659                 :  353562000 :   switch (expr->kind)
     660                 :            :     {
     661                 :    4495620 :     case CONSTANT:
     662                 :    4495620 :       id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
     663                 :    4495620 :       break;
     664                 :  170596000 :     case NAME:
     665                 :  170596000 :       id = VN_INFO (PRE_EXPR_NAME (expr))->value_id;
     666                 :  170596000 :       break;
     667                 :  129828000 :     case NARY:
     668                 :  129828000 :       gcc_assert (!PRE_EXPR_NARY (expr)->predicated_values);
     669                 :  129828000 :       id = PRE_EXPR_NARY (expr)->value_id;
     670                 :  129828000 :       break;
     671                 :   48642800 :     case REFERENCE:
     672                 :   48642800 :       id = PRE_EXPR_REFERENCE (expr)->value_id;
     673                 :   48642800 :       break;
     674                 :          0 :     default:
     675                 :          0 :       gcc_unreachable ();
     676                 :            :     }
     677                 :            :   /* ???  We cannot assert that expr has a value-id (it can be 0), because
     678                 :            :      we assign value-ids only to expressions that have a result
     679                 :            :      in set_hashtable_value_ids.  */
     680                 :  353562000 :   return id;
     681                 :            : }
     682                 :            : 
     683                 :            : /* Return a VN valnum (SSA name or constant) for the PRE value-id VAL.  */
     684                 :            : 
     685                 :            : static tree
     686                 :    1268180 : vn_valnum_from_value_id (unsigned int val)
     687                 :            : {
     688                 :    1268180 :   bitmap_iterator bi;
     689                 :    1268180 :   unsigned int i;
     690                 :    1268180 :   bitmap exprset = value_expressions[val];
     691                 :    2148150 :   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
     692                 :            :     {
     693                 :    1690120 :       pre_expr vexpr = expression_for_id (i);
     694                 :    1690120 :       if (vexpr->kind == NAME)
     695                 :     810147 :         return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
     696                 :     879973 :       else if (vexpr->kind == CONSTANT)
     697                 :          0 :         return PRE_EXPR_CONSTANT (vexpr);
     698                 :            :     }
     699                 :            :   return NULL_TREE;
     700                 :            : }
     701                 :            : 
     702                 :            : /* Insert an expression EXPR into a bitmapped set.  */
     703                 :            : 
     704                 :            : static void
     705                 :   52991200 : bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
     706                 :            : {
     707                 :   52991200 :   unsigned int val = get_expr_value_id (expr);
     708                 :   52991200 :   if (! value_id_constant_p (val))
     709                 :            :     {
     710                 :            :       /* Note this is the only function causing multiple expressions
     711                 :            :          for the same value to appear in a set.  This is needed for
     712                 :            :          TMP_GEN, PHI_GEN and NEW_SETs.  */
     713                 :   51684300 :       bitmap_set_bit (&set->values, val);
     714                 :   51684300 :       bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
     715                 :            :     }
     716                 :   52991200 : }
     717                 :            : 
     718                 :            : /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
     719                 :            : 
     720                 :            : static void
     721                 :   14331800 : bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
     722                 :            : {
     723                 :          0 :   bitmap_copy (&dest->expressions, &orig->expressions);
     724                 :    8377480 :   bitmap_copy (&dest->values, &orig->values);
     725                 :          0 : }
     726                 :            : 
     727                 :            : 
     728                 :            : /* Free memory used up by SET.  */
     729                 :            : static void
     730                 :   37766600 : bitmap_set_free (bitmap_set_t set)
     731                 :            : {
     732                 :          0 :   bitmap_clear (&set->expressions);
     733                 :   37766600 :   bitmap_clear (&set->values);
     734                 :   30951000 : }
     735                 :            : 
     736                 :            : 
     737                 :            : /* Generate an topological-ordered array of bitmap set SET.  */
     738                 :            : 
     739                 :            : static vec<pre_expr> 
     740                 :   16739800 : sorted_array_from_bitmap_set (bitmap_set_t set)
     741                 :            : {
     742                 :   16739800 :   unsigned int i, j;
     743                 :   16739800 :   bitmap_iterator bi, bj;
     744                 :   16739800 :   vec<pre_expr> result;
     745                 :            : 
     746                 :            :   /* Pre-allocate enough space for the array.  */
     747                 :   16739800 :   result.create (bitmap_count_bits (&set->expressions));
     748                 :            : 
     749                 :  100967000 :   FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
     750                 :            :     {
     751                 :            :       /* The number of expressions having a given value is usually
     752                 :            :          relatively small.  Thus, rather than making a vector of all
     753                 :            :          the expressions and sorting it by value-id, we walk the values
     754                 :            :          and check in the reverse mapping that tells us what expressions
     755                 :            :          have a given value, to filter those in our set.  As a result,
     756                 :            :          the expressions are inserted in value-id order, which means
     757                 :            :          topological order.
     758                 :            : 
     759                 :            :          If this is somehow a significant lose for some cases, we can
     760                 :            :          choose which set to walk based on the set size.  */
     761                 :   84226900 :       bitmap exprset = value_expressions[i];
     762                 :  243583000 :       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj)
     763                 :            :         {
     764                 :  159356000 :           if (bitmap_bit_p (&set->expressions, j))
     765                 :   84464500 :             result.quick_push (expression_for_id (j));
     766                 :            :         }
     767                 :            :     }
     768                 :            : 
     769                 :   16739800 :   return result;
     770                 :            : }
     771                 :            : 
     772                 :            : /* Subtract all expressions contained in ORIG from DEST.  */
     773                 :            : 
     774                 :            : static bitmap_set_t
     775                 :   20397800 : bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig)
     776                 :            : {
     777                 :   20397800 :   bitmap_set_t result = bitmap_set_new ();
     778                 :   20397800 :   bitmap_iterator bi;
     779                 :   20397800 :   unsigned int i;
     780                 :            : 
     781                 :   20397800 :   bitmap_and_compl (&result->expressions, &dest->expressions,
     782                 :   20397800 :                     &orig->expressions);
     783                 :            : 
     784                 :   68683300 :   FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
     785                 :            :     {
     786                 :   48285500 :       pre_expr expr = expression_for_id (i);
     787                 :   48285500 :       unsigned int value_id = get_expr_value_id (expr);
     788                 :   48285500 :       bitmap_set_bit (&result->values, value_id);
     789                 :            :     }
     790                 :            : 
     791                 :   20397800 :   return result;
     792                 :            : }
     793                 :            : 
     794                 :            : /* Subtract all values in bitmap set B from bitmap set A.  */
     795                 :            : 
     796                 :            : static void
     797                 :     703554 : bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
     798                 :            : {
     799                 :     703554 :   unsigned int i;
     800                 :     703554 :   bitmap_iterator bi;
     801                 :     703554 :   unsigned to_remove = -1U;
     802                 :     703554 :   bitmap_and_compl_into (&a->values, &b->values);
     803                 :    4878650 :   FOR_EACH_EXPR_ID_IN_SET (a, i, bi)
     804                 :            :     {
     805                 :    4175100 :       if (to_remove != -1U)
     806                 :            :         {
     807                 :    1119040 :           bitmap_clear_bit (&a->expressions, to_remove);
     808                 :    1119040 :           to_remove = -1U;
     809                 :            :         }
     810                 :    4175100 :       pre_expr expr = expression_for_id (i);
     811                 :    4175100 :       if (! bitmap_bit_p (&a->values, get_expr_value_id (expr)))
     812                 :    1147010 :         to_remove = i;
     813                 :            :     }
     814                 :     703554 :   if (to_remove != -1U)
     815                 :      27967 :     bitmap_clear_bit (&a->expressions, to_remove);
     816                 :     703554 : }
     817                 :            : 
     818                 :            : 
     819                 :            : /* Return true if bitmapped set SET contains the value VALUE_ID.  */
     820                 :            : 
     821                 :            : static bool
     822                 :  124008000 : bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
     823                 :            : {
     824                 :  124008000 :   if (value_id_constant_p (value_id))
     825                 :            :     return true;
     826                 :            : 
     827                 :  124008000 :   return bitmap_bit_p (&set->values, value_id);
     828                 :            : }
     829                 :            : 
     830                 :            : /* Return true if two bitmap sets are equal.  */
     831                 :            : 
     832                 :            : static bool
     833                 :    9847110 : bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
     834                 :            : {
     835                 :          0 :   return bitmap_equal_p (&a->values, &b->values);
     836                 :            : }
     837                 :            : 
     838                 :            : /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
     839                 :            :    and add it otherwise.  */
     840                 :            : 
     841                 :            : static void
     842                 :   27612800 : bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
     843                 :            : {
     844                 :   27612800 :   unsigned int val = get_expr_value_id (expr);
     845                 :   27612800 :   if (value_id_constant_p (val))
     846                 :            :     return;
     847                 :            : 
     848                 :   27612800 :   if (bitmap_set_contains_value (set, val))
     849                 :            :     {
     850                 :            :       /* The number of expressions having a given value is usually
     851                 :            :          significantly less than the total number of expressions in SET.
     852                 :            :          Thus, rather than check, for each expression in SET, whether it
     853                 :            :          has the value LOOKFOR, we walk the reverse mapping that tells us
     854                 :            :          what expressions have a given value, and see if any of those
     855                 :            :          expressions are in our set.  For large testcases, this is about
     856                 :            :          5-10x faster than walking the bitmap.  If this is somehow a
     857                 :            :          significant lose for some cases, we can choose which set to walk
     858                 :            :          based on the set size.  */
     859                 :    9351540 :       unsigned int i;
     860                 :    9351540 :       bitmap_iterator bi;
     861                 :    9351540 :       bitmap exprset = value_expressions[val];
     862                 :   16283500 :       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
     863                 :            :         {
     864                 :   16283500 :           if (bitmap_clear_bit (&set->expressions, i))
     865                 :            :             {
     866                 :    9351540 :               bitmap_set_bit (&set->expressions, get_expression_id (expr));
     867                 :    9351540 :               return;
     868                 :            :             }
     869                 :            :         }
     870                 :          0 :       gcc_unreachable ();
     871                 :            :     }
     872                 :            :   else
     873                 :   18261300 :     bitmap_insert_into_set (set, expr);
     874                 :            : }
     875                 :            : 
     876                 :            : /* Insert EXPR into SET if EXPR's value is not already present in
     877                 :            :    SET.  */
     878                 :            : 
     879                 :            : static void
     880                 :   36249600 : bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
     881                 :            : {
     882                 :   36249600 :   unsigned int val = get_expr_value_id (expr);
     883                 :            : 
     884                 :   36249600 :   gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr));
     885                 :            : 
     886                 :            :   /* Constant values are always considered to be part of the set.  */
     887                 :   36249600 :   if (value_id_constant_p (val))
     888                 :            :     return;
     889                 :            : 
     890                 :            :   /* If the value membership changed, add the expression.  */
     891                 :   36204900 :   if (bitmap_set_bit (&set->values, val))
     892                 :   27538700 :     bitmap_set_bit (&set->expressions, expr->id);
     893                 :            : }
     894                 :            : 
     895                 :            : /* Print out EXPR to outfile.  */
     896                 :            : 
     897                 :            : static void
     898                 :       7647 : print_pre_expr (FILE *outfile, const pre_expr expr)
     899                 :            : {
     900                 :       7647 :   if (! expr)
     901                 :            :     {
     902                 :          0 :       fprintf (outfile, "NULL");
     903                 :          0 :       return;
     904                 :            :     }
     905                 :       7647 :   switch (expr->kind)
     906                 :            :     {
     907                 :          0 :     case CONSTANT:
     908                 :          0 :       print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr));
     909                 :          0 :       break;
     910                 :       3787 :     case NAME:
     911                 :       3787 :       print_generic_expr (outfile, PRE_EXPR_NAME (expr));
     912                 :       3787 :       break;
     913                 :       2385 :     case NARY:
     914                 :       2385 :       {
     915                 :       2385 :         unsigned int i;
     916                 :       2385 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
     917                 :       2385 :         fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode));
     918                 :       6720 :         for (i = 0; i < nary->length; i++)
     919                 :            :           {
     920                 :       4335 :             print_generic_expr (outfile, nary->op[i]);
     921                 :       4335 :             if (i != (unsigned) nary->length - 1)
     922                 :       1950 :               fprintf (outfile, ",");
     923                 :            :           }
     924                 :       2385 :         fprintf (outfile, "}");
     925                 :            :       }
     926                 :       2385 :       break;
     927                 :            : 
     928                 :       1475 :     case REFERENCE:
     929                 :       1475 :       {
     930                 :       1475 :         vn_reference_op_t vro;
     931                 :       1475 :         unsigned int i;
     932                 :       1475 :         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
     933                 :       1475 :         fprintf (outfile, "{");
     934                 :       7767 :         for (i = 0;
     935                 :       7767 :              ref->operands.iterate (i, &vro);
     936                 :            :              i++)
     937                 :            :           {
     938                 :       6292 :             bool closebrace = false;
     939                 :       6292 :             if (vro->opcode != SSA_NAME
     940                 :       4946 :                 && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
     941                 :            :               {
     942                 :       4946 :                 fprintf (outfile, "%s", get_tree_code_name (vro->opcode));
     943                 :       4946 :                 if (vro->op0)
     944                 :            :                   {
     945                 :       4946 :                     fprintf (outfile, "<");
     946                 :       4946 :                     closebrace = true;
     947                 :            :                   }
     948                 :            :               }
     949                 :       6292 :             if (vro->op0)
     950                 :            :               {
     951                 :       6292 :                 print_generic_expr (outfile, vro->op0);
     952                 :       6292 :                 if (vro->op1)
     953                 :            :                   {
     954                 :       1062 :                     fprintf (outfile, ",");
     955                 :       1062 :                     print_generic_expr (outfile, vro->op1);
     956                 :            :                   }
     957                 :       6292 :                 if (vro->op2)
     958                 :            :                   {
     959                 :       1062 :                     fprintf (outfile, ",");
     960                 :       1062 :                     print_generic_expr (outfile, vro->op2);
     961                 :            :                   }
     962                 :            :               }
     963                 :       6292 :             if (closebrace)
     964                 :       4946 :                 fprintf (outfile, ">");
     965                 :      12584 :             if (i != ref->operands.length () - 1)
     966                 :       4817 :               fprintf (outfile, ",");
     967                 :            :           }
     968                 :       1475 :         fprintf (outfile, "}");
     969                 :       1475 :         if (ref->vuse)
     970                 :            :           {
     971                 :       1453 :             fprintf (outfile, "@");
     972                 :       1453 :             print_generic_expr (outfile, ref->vuse);
     973                 :            :           }
     974                 :            :       }
     975                 :            :       break;
     976                 :            :     }
     977                 :            : }
     978                 :            : void debug_pre_expr (pre_expr);
     979                 :            : 
     980                 :            : /* Like print_pre_expr but always prints to stderr.  */
     981                 :            : DEBUG_FUNCTION void
     982                 :          0 : debug_pre_expr (pre_expr e)
     983                 :            : {
     984                 :          0 :   print_pre_expr (stderr, e);
     985                 :          0 :   fprintf (stderr, "\n");
     986                 :          0 : }
     987                 :            : 
     988                 :            : /* Print out SET to OUTFILE.  */
     989                 :            : 
     990                 :            : static void
     991                 :       1090 : print_bitmap_set (FILE *outfile, bitmap_set_t set,
     992                 :            :                   const char *setname, int blockindex)
     993                 :            : {
     994                 :       1090 :   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
     995                 :       1090 :   if (set)
     996                 :            :     {
     997                 :       1090 :       bool first = true;
     998                 :       1090 :       unsigned i;
     999                 :       1090 :       bitmap_iterator bi;
    1000                 :            : 
    1001                 :       8362 :       FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
    1002                 :            :         {
    1003                 :       7272 :           const pre_expr expr = expression_for_id (i);
    1004                 :            : 
    1005                 :       7272 :           if (!first)
    1006                 :       6483 :             fprintf (outfile, ", ");
    1007                 :       7272 :           first = false;
    1008                 :       7272 :           print_pre_expr (outfile, expr);
    1009                 :            : 
    1010                 :       7272 :           fprintf (outfile, " (%04d)", get_expr_value_id (expr));
    1011                 :            :         }
    1012                 :            :     }
    1013                 :       1090 :   fprintf (outfile, " }\n");
    1014                 :       1090 : }
    1015                 :            : 
    1016                 :            : void debug_bitmap_set (bitmap_set_t);
    1017                 :            : 
    1018                 :            : DEBUG_FUNCTION void
    1019                 :          0 : debug_bitmap_set (bitmap_set_t set)
    1020                 :            : {
    1021                 :          0 :   print_bitmap_set (stderr, set, "debug", 0);
    1022                 :          0 : }
    1023                 :            : 
    1024                 :            : void debug_bitmap_sets_for (basic_block);
    1025                 :            : 
    1026                 :            : DEBUG_FUNCTION void
    1027                 :          0 : debug_bitmap_sets_for (basic_block bb)
    1028                 :            : {
    1029                 :          0 :   print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
    1030                 :          0 :   print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
    1031                 :          0 :   print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
    1032                 :          0 :   print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
    1033                 :          0 :   print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
    1034                 :          0 :   if (do_partial_partial)
    1035                 :          0 :     print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
    1036                 :          0 :   print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
    1037                 :          0 : }
    1038                 :            : 
    1039                 :            : /* Print out the expressions that have VAL to OUTFILE.  */
    1040                 :            : 
    1041                 :            : static void
    1042                 :          0 : print_value_expressions (FILE *outfile, unsigned int val)
    1043                 :            : {
    1044                 :          0 :   bitmap set = value_expressions[val];
    1045                 :          0 :   if (set)
    1046                 :            :     {
    1047                 :          0 :       bitmap_set x;
    1048                 :          0 :       char s[10];
    1049                 :          0 :       sprintf (s, "%04d", val);
    1050                 :          0 :       x.expressions = *set;
    1051                 :          0 :       print_bitmap_set (outfile, &x, s, 0);
    1052                 :            :     }
    1053                 :          0 : }
    1054                 :            : 
    1055                 :            : 
    1056                 :            : DEBUG_FUNCTION void
    1057                 :          0 : debug_value_expressions (unsigned int val)
    1058                 :            : {
    1059                 :          0 :   print_value_expressions (stderr, val);
    1060                 :          0 : }
    1061                 :            : 
    1062                 :            : /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
    1063                 :            :    represent it.  */
    1064                 :            : 
    1065                 :            : static pre_expr
    1066                 :    3114710 : get_or_alloc_expr_for_constant (tree constant)
    1067                 :            : {
    1068                 :    3114710 :   unsigned int result_id;
    1069                 :    3114710 :   unsigned int value_id;
    1070                 :    3114710 :   struct pre_expr_d expr;
    1071                 :    3114710 :   pre_expr newexpr;
    1072                 :            : 
    1073                 :    3114710 :   expr.kind = CONSTANT;
    1074                 :    3114710 :   PRE_EXPR_CONSTANT (&expr) = constant;
    1075                 :    3114710 :   result_id = lookup_expression_id (&expr);
    1076                 :    3114710 :   if (result_id != 0)
    1077                 :    2539890 :     return expression_for_id (result_id);
    1078                 :            : 
    1079                 :     574822 :   newexpr = pre_expr_pool.allocate ();
    1080                 :     574822 :   newexpr->kind = CONSTANT;
    1081                 :     574822 :   newexpr->loc = UNKNOWN_LOCATION;
    1082                 :     574822 :   PRE_EXPR_CONSTANT (newexpr) = constant;
    1083                 :     574822 :   alloc_expression_id (newexpr);
    1084                 :     574822 :   value_id = get_or_alloc_constant_value_id (constant);
    1085                 :     574822 :   add_to_value (value_id, newexpr);
    1086                 :     574822 :   return newexpr;
    1087                 :            : }
    1088                 :            : 
    1089                 :            : /* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
    1090                 :            :    Currently only supports constants and SSA_NAMES.  */
    1091                 :            : static pre_expr
    1092                 :    1361350 : get_or_alloc_expr_for (tree t)
    1093                 :            : {
    1094                 :    1361350 :   if (TREE_CODE (t) == SSA_NAME)
    1095                 :     987896 :     return get_or_alloc_expr_for_name (t);
    1096                 :     373450 :   else if (is_gimple_min_invariant (t))
    1097                 :     373450 :     return get_or_alloc_expr_for_constant (t);
    1098                 :          0 :   gcc_unreachable ();
    1099                 :            : }
    1100                 :            : 
    1101                 :            : /* Return the folded version of T if T, when folded, is a gimple
    1102                 :            :    min_invariant or an SSA name.  Otherwise, return T.  */
    1103                 :            : 
    1104                 :            : static pre_expr
    1105                 :    3737440 : fully_constant_expression (pre_expr e)
    1106                 :            : {
    1107                 :    3737440 :   switch (e->kind)
    1108                 :            :     {
    1109                 :            :     case CONSTANT:
    1110                 :            :       return e;
    1111                 :    3737440 :     case NARY:
    1112                 :    3737440 :       {
    1113                 :    3737440 :         vn_nary_op_t nary = PRE_EXPR_NARY (e);
    1114                 :    3737440 :         tree res = vn_nary_simplify (nary);
    1115                 :    3737440 :         if (!res)
    1116                 :            :           return e;
    1117                 :     843388 :         if (is_gimple_min_invariant (res))
    1118                 :     596326 :           return get_or_alloc_expr_for_constant (res);
    1119                 :     247062 :         if (TREE_CODE (res) == SSA_NAME)
    1120                 :     247062 :           return get_or_alloc_expr_for_name (res);
    1121                 :            :         return e;
    1122                 :            :       }
    1123                 :          0 :     case REFERENCE:
    1124                 :          0 :       {
    1125                 :          0 :         vn_reference_t ref = PRE_EXPR_REFERENCE (e);
    1126                 :          0 :         tree folded;
    1127                 :          0 :         if ((folded = fully_constant_vn_reference_p (ref)))
    1128                 :          0 :           return get_or_alloc_expr_for_constant (folded);
    1129                 :            :         return e;
    1130                 :            :       }
    1131                 :            :     default:
    1132                 :            :       return e;
    1133                 :            :     }
    1134                 :            :   return e;
    1135                 :            : }
    1136                 :            : 
    1137                 :            : /* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
    1138                 :            :    it has the value it would have in BLOCK.  Set *SAME_VALID to true
    1139                 :            :    in case the new vuse doesn't change the value id of the OPERANDS.  */
    1140                 :            : 
    1141                 :            : static tree
    1142                 :    3179300 : translate_vuse_through_block (vec<vn_reference_op_s> operands,
    1143                 :            :                               alias_set_type set, alias_set_type base_set,
    1144                 :            :                               tree type, tree vuse,
    1145                 :            :                               basic_block phiblock,
    1146                 :            :                               basic_block block, bool *same_valid)
    1147                 :            : {
    1148                 :    3179300 :   gimple *phi = SSA_NAME_DEF_STMT (vuse);
    1149                 :    3179300 :   ao_ref ref;
    1150                 :    3179300 :   edge e = NULL;
    1151                 :    3179300 :   bool use_oracle;
    1152                 :            : 
    1153                 :    3179300 :   if (same_valid)
    1154                 :    2416660 :     *same_valid = true;
    1155                 :            : 
    1156                 :    3179300 :   if (gimple_bb (phi) != phiblock)
    1157                 :            :     return vuse;
    1158                 :            : 
    1159                 :    1513190 :   unsigned int cnt = param_sccvn_max_alias_queries_per_access;
    1160                 :    1513190 :   use_oracle = ao_ref_init_from_vn_reference (&ref, set, base_set,
    1161                 :            :                                               type, operands);
    1162                 :            : 
    1163                 :            :   /* Use the alias-oracle to find either the PHI node in this block,
    1164                 :            :      the first VUSE used in this block that is equivalent to vuse or
    1165                 :            :      the first VUSE which definition in this block kills the value.  */
    1166                 :    1513190 :   if (gimple_code (phi) == GIMPLE_PHI)
    1167                 :    1150810 :     e = find_edge (block, phiblock);
    1168                 :     362380 :   else if (use_oracle)
    1169                 :     444383 :     while (cnt > 0
    1170                 :     444383 :            && !stmt_may_clobber_ref_p_1 (phi, &ref))
    1171                 :            :       {
    1172                 :     444188 :         --cnt;
    1173                 :     444188 :         vuse = gimple_vuse (phi);
    1174                 :     444188 :         phi = SSA_NAME_DEF_STMT (vuse);
    1175                 :     444188 :         if (gimple_bb (phi) != phiblock)
    1176                 :       4459 :           return vuse;
    1177                 :     439729 :         if (gimple_code (phi) == GIMPLE_PHI)
    1178                 :            :           {
    1179                 :     357539 :             e = find_edge (block, phiblock);
    1180                 :     357539 :             break;
    1181                 :            :           }
    1182                 :            :       }
    1183                 :            :   else
    1184                 :            :     return NULL_TREE;
    1185                 :            : 
    1186                 :    1508540 :   if (e)
    1187                 :            :     {
    1188                 :    1508350 :       if (use_oracle && same_valid)
    1189                 :            :         {
    1190                 :    1175290 :           bitmap visited = NULL;
    1191                 :            :           /* Try to find a vuse that dominates this phi node by skipping
    1192                 :            :              non-clobbering statements.  */
    1193                 :    1175290 :           vuse = get_continuation_for_phi (phi, &ref, true,
    1194                 :            :                                            cnt, &visited, false, NULL, NULL);
    1195                 :    1175290 :           if (visited)
    1196                 :    1175280 :             BITMAP_FREE (visited);
    1197                 :            :         }
    1198                 :            :       else
    1199                 :            :         vuse = NULL_TREE;
    1200                 :            :       /* If we didn't find any, the value ID can't stay the same.  */
    1201                 :    1508350 :       if (!vuse && same_valid)
    1202                 :    1187170 :         *same_valid = false;
    1203                 :            :       /* ??? We would like to return vuse here as this is the canonical
    1204                 :            :          upmost vdef that this reference is associated with.  But during
    1205                 :            :          insertion of the references into the hash tables we only ever
    1206                 :            :          directly insert with their direct gimple_vuse, hence returning
    1207                 :            :          something else would make us not find the other expression.  */
    1208                 :    1508350 :       return PHI_ARG_DEF (phi, e->dest_idx);
    1209                 :            :     }
    1210                 :            : 
    1211                 :            :   return NULL_TREE;
    1212                 :            : }
    1213                 :            : 
    1214                 :            : /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
    1215                 :            :    SET2 *or* SET3.  This is used to avoid making a set consisting of the union
    1216                 :            :    of PA_IN and ANTIC_IN during insert and phi-translation.  */
    1217                 :            : 
    1218                 :            : static inline pre_expr
    1219                 :   15819400 : find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2,
    1220                 :            :                      bitmap_set_t set3 = NULL)
    1221                 :            : {
    1222                 :   15819400 :   pre_expr result = NULL;
    1223                 :            : 
    1224                 :   15819400 :   if (set1)
    1225                 :   15804600 :     result = bitmap_find_leader (set1, val);
    1226                 :   15819400 :   if (!result && set2)
    1227                 :     496598 :     result = bitmap_find_leader (set2, val);
    1228                 :   15819400 :   if (!result && set3)
    1229                 :          0 :     result = bitmap_find_leader (set3, val);
    1230                 :   15819400 :   return result;
    1231                 :            : }
    1232                 :            : 
    1233                 :            : /* Get the tree type for our PRE expression e.  */
    1234                 :            : 
    1235                 :            : static tree
    1236                 :    4585630 : get_expr_type (const pre_expr e)
    1237                 :            : {
    1238                 :    4585630 :   switch (e->kind)
    1239                 :            :     {
    1240                 :     756485 :     case NAME:
    1241                 :     756485 :       return TREE_TYPE (PRE_EXPR_NAME (e));
    1242                 :      91196 :     case CONSTANT:
    1243                 :      91196 :       return TREE_TYPE (PRE_EXPR_CONSTANT (e));
    1244                 :     841031 :     case REFERENCE:
    1245                 :     841031 :       return PRE_EXPR_REFERENCE (e)->type;
    1246                 :    2896920 :     case NARY:
    1247                 :    2896920 :       return PRE_EXPR_NARY (e)->type;
    1248                 :            :     }
    1249                 :          0 :   gcc_unreachable ();
    1250                 :            : }
    1251                 :            : 
    1252                 :            : /* Get a representative SSA_NAME for a given expression that is available in B.
    1253                 :            :    Since all of our sub-expressions are treated as values, we require
    1254                 :            :    them to be SSA_NAME's for simplicity.
    1255                 :            :    Prior versions of GVNPRE used to use "value handles" here, so that
    1256                 :            :    an expression would be VH.11 + VH.10 instead of d_3 + e_6.  In
    1257                 :            :    either case, the operands are really values (IE we do not expect
    1258                 :            :    them to be usable without finding leaders).  */
    1259                 :            : 
    1260                 :            : static tree
    1261                 :    5136950 : get_representative_for (const pre_expr e, basic_block b = NULL)
    1262                 :            : {
    1263                 :    5136950 :   tree name, valnum = NULL_TREE;
    1264                 :    5136950 :   unsigned int value_id = get_expr_value_id (e);
    1265                 :            : 
    1266                 :    5136950 :   switch (e->kind)
    1267                 :            :     {
    1268                 :    1398700 :     case NAME:
    1269                 :    1398700 :       return PRE_EXPR_NAME (e);
    1270                 :     966344 :     case CONSTANT:
    1271                 :     966344 :       return PRE_EXPR_CONSTANT (e);
    1272                 :    2771900 :     case NARY:
    1273                 :    2771900 :     case REFERENCE:
    1274                 :    2771900 :       {
    1275                 :            :         /* Go through all of the expressions representing this value
    1276                 :            :            and pick out an SSA_NAME.  */
    1277                 :    2771900 :         unsigned int i;
    1278                 :    2771900 :         bitmap_iterator bi;
    1279                 :    2771900 :         bitmap exprs = value_expressions[value_id];
    1280                 :    5523940 :         EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi)
    1281                 :            :           {
    1282                 :    3346630 :             pre_expr rep = expression_for_id (i);
    1283                 :    3346630 :             if (rep->kind == NAME)
    1284                 :            :               {
    1285                 :     665186 :                 tree name = PRE_EXPR_NAME (rep);
    1286                 :     665186 :                 valnum = VN_INFO (name)->valnum;
    1287                 :     665186 :                 gimple *def = SSA_NAME_DEF_STMT (name);
    1288                 :            :                 /* We have to return either a new representative or one
    1289                 :            :                    that can be used for expression simplification and thus
    1290                 :            :                    is available in B.  */
    1291                 :     665186 :                 if (! b 
    1292                 :     582991 :                     || gimple_nop_p (def)
    1293                 :     835307 :                     || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
    1294                 :     594600 :                   return name;
    1295                 :            :               }
    1296                 :    2681450 :             else if (rep->kind == CONSTANT)
    1297                 :          0 :               return PRE_EXPR_CONSTANT (rep);
    1298                 :            :           }
    1299                 :            :       }
    1300                 :    2177300 :       break;
    1301                 :            :     }
    1302                 :            : 
    1303                 :            :   /* If we reached here we couldn't find an SSA_NAME.  This can
    1304                 :            :      happen when we've discovered a value that has never appeared in
    1305                 :            :      the program as set to an SSA_NAME, as the result of phi translation.
    1306                 :            :      Create one here.
    1307                 :            :      ???  We should be able to re-use this when we insert the statement
    1308                 :            :      to compute it.  */
    1309                 :    2177300 :   name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
    1310                 :    2177300 :   VN_INFO (name)->value_id = value_id;
    1311                 :    4324060 :   VN_INFO (name)->valnum = valnum ? valnum : name;
    1312                 :            :   /* ???  For now mark this SSA name for release by VN.  */
    1313                 :    2177300 :   VN_INFO (name)->needs_insertion = true;
    1314                 :    2177300 :   add_to_value (value_id, get_or_alloc_expr_for_name (name));
    1315                 :    2177300 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1316                 :            :     {
    1317                 :         70 :       fprintf (dump_file, "Created SSA_NAME representative ");
    1318                 :         70 :       print_generic_expr (dump_file, name);
    1319                 :         70 :       fprintf (dump_file, " for expression:");
    1320                 :         70 :       print_pre_expr (dump_file, e);
    1321                 :         70 :       fprintf (dump_file, " (%04d)\n", value_id);
    1322                 :            :     }
    1323                 :            : 
    1324                 :            :   return name;
    1325                 :            : }
    1326                 :            : 
    1327                 :            : 
    1328                 :            : static pre_expr
    1329                 :            : phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge);
    1330                 :            : 
    1331                 :            : /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
    1332                 :            :    the phis in PRED.  Return NULL if we can't find a leader for each part
    1333                 :            :    of the translated expression.  */
    1334                 :            : 
    1335                 :            : static pre_expr
    1336                 :   30374900 : phi_translate_1 (bitmap_set_t dest,
    1337                 :            :                  pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e)
    1338                 :            : {
    1339                 :   30374900 :   basic_block pred = e->src;
    1340                 :   30374900 :   basic_block phiblock = e->dest;
    1341                 :   30374900 :   location_t expr_loc = expr->loc;
    1342                 :   30374900 :   switch (expr->kind)
    1343                 :            :     {
    1344                 :   10118800 :     case NARY:
    1345                 :   10118800 :       {
    1346                 :   10118800 :         unsigned int i;
    1347                 :   10118800 :         bool changed = false;
    1348                 :   10118800 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    1349                 :   10118800 :         vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,
    1350                 :            :                                            sizeof_vn_nary_op (nary->length));
    1351                 :   10118800 :         memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
    1352                 :            : 
    1353                 :   24088600 :         for (i = 0; i < newnary->length; i++)
    1354                 :            :           {
    1355                 :   16413500 :             if (TREE_CODE (newnary->op[i]) != SSA_NAME)
    1356                 :    3496430 :               continue;
    1357                 :            :             else
    1358                 :            :               {
    1359                 :   12917100 :                 pre_expr leader, result;
    1360                 :   12917100 :                 unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
    1361                 :   12917100 :                 leader = find_leader_in_sets (op_val_id, set1, set2);
    1362                 :   12917100 :                 result = phi_translate (dest, leader, set1, set2, e);
    1363                 :   12917100 :                 if (result && result != leader)
    1364                 :            :                   /* If op has a leader in the sets we translate make
    1365                 :            :                      sure to use the value of the translated expression.
    1366                 :            :                      We might need a new representative for that.  */
    1367                 :    4307470 :                   newnary->op[i] = get_representative_for (result, pred);
    1368                 :    8609580 :                 else if (!result)
    1369                 :            :                   return NULL;
    1370                 :            : 
    1371                 :   10473400 :                 changed |= newnary->op[i] != nary->op[i];
    1372                 :            :               }
    1373                 :            :           }
    1374                 :    7675160 :         if (changed)
    1375                 :            :           {
    1376                 :    3737440 :             pre_expr constant;
    1377                 :    3737440 :             unsigned int new_val_id;
    1378                 :            : 
    1379                 :    3737440 :             PRE_EXPR_NARY (expr) = newnary;
    1380                 :    3737440 :             constant = fully_constant_expression (expr);
    1381                 :    3737440 :             PRE_EXPR_NARY (expr) = nary;
    1382                 :    3737440 :             if (constant != expr)
    1383                 :            :               {
    1384                 :            :                 /* For non-CONSTANTs we have to make sure we can eventually
    1385                 :            :                    insert the expression.  Which means we need to have a
    1386                 :            :                    leader for it.  */
    1387                 :     843388 :                 if (constant->kind != CONSTANT)
    1388                 :            :                   {
    1389                 :            :                     /* Do not allow simplifications to non-constants over
    1390                 :            :                        backedges as this will likely result in a loop PHI node
    1391                 :            :                        to be inserted and increased register pressure.
    1392                 :            :                        See PR77498 - this avoids doing predcoms work in
    1393                 :            :                        a less efficient way.  */
    1394                 :     247062 :                     if (e->flags & EDGE_DFS_BACK)
    1395                 :            :                       ;
    1396                 :            :                     else
    1397                 :            :                       {
    1398                 :     211971 :                         unsigned value_id = get_expr_value_id (constant);
    1399                 :            :                         /* We want a leader in ANTIC_OUT or AVAIL_OUT here.
    1400                 :            :                            dest has what we computed into ANTIC_OUT sofar
    1401                 :            :                            so pick from that - since topological sorting
    1402                 :            :                            by sorted_array_from_bitmap_set isn't perfect
    1403                 :            :                            we may lose some cases here.  */
    1404                 :     423942 :                         constant = find_leader_in_sets (value_id, dest,
    1405                 :     211971 :                                                         AVAIL_OUT (pred));
    1406                 :     211971 :                         if (constant)
    1407                 :            :                           {
    1408                 :     183538 :                             if (dump_file && (dump_flags & TDF_DETAILS))
    1409                 :            :                               {
    1410                 :          5 :                                 fprintf (dump_file, "simplifying ");
    1411                 :          5 :                                 print_pre_expr (dump_file, expr);
    1412                 :          5 :                                 fprintf (dump_file, " translated %d -> %d to ",
    1413                 :            :                                          phiblock->index, pred->index);
    1414                 :          5 :                                 PRE_EXPR_NARY (expr) = newnary;
    1415                 :          5 :                                 print_pre_expr (dump_file, expr);
    1416                 :          5 :                                 PRE_EXPR_NARY (expr) = nary;
    1417                 :          5 :                                 fprintf (dump_file, " to ");
    1418                 :          5 :                                 print_pre_expr (dump_file, constant);
    1419                 :          5 :                                 fprintf (dump_file, "\n");
    1420                 :            :                               }
    1421                 :     183538 :                             return constant;
    1422                 :            :                           }
    1423                 :            :                       }
    1424                 :            :                   }
    1425                 :            :                 else
    1426                 :            :                   return constant;
    1427                 :            :               }
    1428                 :            : 
    1429                 :            :             /* vn_nary_* do not valueize operands.  */
    1430                 :    8218610 :             for (i = 0; i < newnary->length; ++i)
    1431                 :    5261040 :               if (TREE_CODE (newnary->op[i]) == SSA_NAME)
    1432                 :    3990120 :                 newnary->op[i] = VN_INFO (newnary->op[i])->valnum;
    1433                 :    5915150 :             tree result = vn_nary_op_lookup_pieces (newnary->length,
    1434                 :    2957570 :                                                     newnary->opcode,
    1435                 :            :                                                     newnary->type,
    1436                 :            :                                                     &newnary->op[0],
    1437                 :            :                                                     &nary);
    1438                 :    2957570 :             if (result && is_gimple_min_invariant (result))
    1439                 :          0 :               return get_or_alloc_expr_for_constant (result);
    1440                 :            : 
    1441                 :    2957570 :             expr = pre_expr_pool.allocate ();
    1442                 :    2957570 :             expr->kind = NARY;
    1443                 :    2957570 :             expr->id = 0;
    1444                 :    2957570 :             expr->loc = expr_loc;
    1445                 :    2957570 :             if (nary && !nary->predicated_values)
    1446                 :            :               {
    1447                 :     203573 :                 PRE_EXPR_NARY (expr) = nary;
    1448                 :     203573 :                 new_val_id = nary->value_id;
    1449                 :     203573 :                 get_or_alloc_expression_id (expr);
    1450                 :            :               }
    1451                 :            :             else
    1452                 :            :               {
    1453                 :    2754000 :                 new_val_id = get_next_value_id ();
    1454                 :    2754000 :                 value_expressions.safe_grow_cleared (get_max_value_id () + 1);
    1455                 :    5508000 :                 nary = vn_nary_op_insert_pieces (newnary->length,
    1456                 :    2754000 :                                                  newnary->opcode,
    1457                 :            :                                                  newnary->type,
    1458                 :            :                                                  &newnary->op[0],
    1459                 :            :                                                  result, new_val_id);
    1460                 :    2754000 :                 PRE_EXPR_NARY (expr) = nary;
    1461                 :    2754000 :                 get_or_alloc_expression_id (expr);
    1462                 :            :               }
    1463                 :    2957570 :             add_to_value (new_val_id, expr);
    1464                 :            :           }
    1465                 :            :         return expr;
    1466                 :            :       }
    1467                 :    3641490 :       break;
    1468                 :            : 
    1469                 :    3641490 :     case REFERENCE:
    1470                 :    3641490 :       {
    1471                 :    3641490 :         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    1472                 :    3641490 :         vec<vn_reference_op_s> operands = ref->operands;
    1473                 :    3641490 :         tree vuse = ref->vuse;
    1474                 :    3641490 :         tree newvuse = vuse;
    1475                 :    3641490 :         vec<vn_reference_op_s> newoperands = vNULL;
    1476                 :    3641490 :         bool changed = false, same_valid = true;
    1477                 :    3641490 :         unsigned int i, n;
    1478                 :    3641490 :         vn_reference_op_t operand;
    1479                 :    3641490 :         vn_reference_t newref;
    1480                 :            : 
    1481                 :   14280000 :         for (i = 0; operands.iterate (i, &operand); i++)
    1482                 :            :           {
    1483                 :   10835100 :             pre_expr opresult;
    1484                 :   10835100 :             pre_expr leader;
    1485                 :   10835100 :             tree op[3];
    1486                 :   10835100 :             tree type = operand->type;
    1487                 :   10835100 :             vn_reference_op_s newop = *operand;
    1488                 :   10835100 :             op[0] = operand->op0;
    1489                 :   10835100 :             op[1] = operand->op1;
    1490                 :   10835100 :             op[2] = operand->op2;
    1491                 :   42750700 :             for (n = 0; n < 3; ++n)
    1492                 :            :               {
    1493                 :   32112200 :                 unsigned int op_val_id;
    1494                 :   32112200 :                 if (!op[n])
    1495                 :   19715600 :                   continue;
    1496                 :   12396600 :                 if (TREE_CODE (op[n]) != SSA_NAME)
    1497                 :            :                   {
    1498                 :            :                     /* We can't possibly insert these.  */
    1499                 :    9706200 :                     if (n != 0
    1500                 :    9706200 :                         && !is_gimple_min_invariant (op[n]))
    1501                 :            :                       break;
    1502                 :    9706200 :                     continue;
    1503                 :            :                   }
    1504                 :    2690400 :                 op_val_id = VN_INFO (op[n])->value_id;
    1505                 :    2690400 :                 leader = find_leader_in_sets (op_val_id, set1, set2);
    1506                 :    2690400 :                 opresult = phi_translate (dest, leader, set1, set2, e);
    1507                 :    2690400 :                 if (opresult && opresult != leader)
    1508                 :            :                   {
    1509                 :     829475 :                     tree name = get_representative_for (opresult);
    1510                 :     829475 :                     changed |= name != op[n];
    1511                 :     829475 :                     op[n] = name;
    1512                 :            :                   }
    1513                 :    1860930 :                 else if (!opresult)
    1514                 :            :                   break;
    1515                 :            :               }
    1516                 :   10835100 :             if (n != 3)
    1517                 :            :               {
    1518                 :     196550 :                 newoperands.release ();
    1519                 :     196550 :                 return NULL;
    1520                 :            :               }
    1521                 :   10638500 :             if (!changed)
    1522                 :    9039890 :               continue;
    1523                 :    1598650 :             if (!newoperands.exists ())
    1524                 :    1616920 :               newoperands = operands.copy ();
    1525                 :            :             /* We may have changed from an SSA_NAME to a constant */
    1526                 :    1598650 :             if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
    1527                 :      21168 :               newop.opcode = TREE_CODE (op[0]);
    1528                 :    1598650 :             newop.type = type;
    1529                 :    1598650 :             newop.op0 = op[0];
    1530                 :    1598650 :             newop.op1 = op[1];
    1531                 :    1598650 :             newop.op2 = op[2];
    1532                 :    1598650 :             newoperands[i] = newop;
    1533                 :            :           }
    1534                 :    6889870 :         gcc_checking_assert (i == operands.length ());
    1535                 :            : 
    1536                 :    3444940 :         if (vuse)
    1537                 :            :           {
    1538                 :    8012620 :             newvuse = translate_vuse_through_block (newoperands.exists ()
    1539                 :    3179300 :                                                     ? newoperands : operands,
    1540                 :            :                                                     ref->set, ref->base_set,
    1541                 :            :                                                     ref->type,
    1542                 :            :                                                     vuse, phiblock, pred,
    1543                 :            :                                                     changed
    1544                 :            :                                                     ? NULL : &same_valid);
    1545                 :    3179300 :             if (newvuse == NULL_TREE)
    1546                 :            :               {
    1547                 :        382 :                 newoperands.release ();
    1548                 :        382 :                 return NULL;
    1549                 :            :               }
    1550                 :            :           }
    1551                 :            : 
    1552                 :    3444550 :         if (changed || newvuse != vuse)
    1553                 :            :           {
    1554                 :    2019470 :             unsigned int new_val_id;
    1555                 :            : 
    1556                 :    2019470 :             tree result = vn_reference_lookup_pieces (newvuse, ref->set,
    1557                 :            :                                                       ref->base_set,
    1558                 :            :                                                       ref->type,
    1559                 :    2019470 :                                                       newoperands.exists ()
    1560                 :    2019470 :                                                       ? newoperands : operands,
    1561                 :            :                                                       &newref, VN_WALK);
    1562                 :    2019470 :             if (result)
    1563                 :     223870 :               newoperands.release ();
    1564                 :            : 
    1565                 :            :             /* We can always insert constants, so if we have a partial
    1566                 :            :                redundant constant load of another type try to translate it
    1567                 :            :                to a constant of appropriate type.  */
    1568                 :    2019470 :             if (result && is_gimple_min_invariant (result))
    1569                 :            :               {
    1570                 :      38777 :                 tree tem = result;
    1571                 :      38777 :                 if (!useless_type_conversion_p (ref->type, TREE_TYPE (result)))
    1572                 :            :                   {
    1573                 :         58 :                     tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result);
    1574                 :         58 :                     if (tem && !is_gimple_min_invariant (tem))
    1575                 :            :                       tem = NULL_TREE;
    1576                 :            :                   }
    1577                 :      38767 :                 if (tem)
    1578                 :      38767 :                   return get_or_alloc_expr_for_constant (tem);
    1579                 :            :               }
    1580                 :            : 
    1581                 :            :             /* If we'd have to convert things we would need to validate
    1582                 :            :                if we can insert the translated expression.  So fail
    1583                 :            :                here for now - we cannot insert an alias with a different
    1584                 :            :                type in the VN tables either, as that would assert.  */
    1585                 :    1980700 :             if (result
    1586                 :    2165810 :                 && !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
    1587                 :            :               return NULL;
    1588                 :    1795600 :             else if (!result && newref
    1589                 :    2068330 :                      && !useless_type_conversion_p (ref->type, newref->type))
    1590                 :            :               {
    1591                 :        488 :                 newoperands.release ();
    1592                 :        488 :                 return NULL;
    1593                 :            :               }
    1594                 :            : 
    1595                 :    1979400 :             expr = pre_expr_pool.allocate ();
    1596                 :    1979400 :             expr->kind = REFERENCE;
    1597                 :    1979400 :             expr->id = 0;
    1598                 :    1979400 :             expr->loc = expr_loc;
    1599                 :            : 
    1600                 :    1979400 :             if (newref)
    1601                 :     272241 :               new_val_id = newref->value_id;
    1602                 :            :             else
    1603                 :            :               {
    1604                 :    1707160 :                 if (changed || !same_valid)
    1605                 :            :                   {
    1606                 :    1691900 :                     new_val_id = get_next_value_id ();
    1607                 :    1691900 :                     value_expressions.safe_grow_cleared
    1608                 :    1691900 :                       (get_max_value_id () + 1);
    1609                 :            :                   }
    1610                 :            :                 else
    1611                 :      15253 :                   new_val_id = ref->value_id;
    1612                 :    1707160 :                 if (!newoperands.exists ())
    1613                 :    1979340 :                   newoperands = operands.copy ();
    1614                 :    1707160 :                 newref = vn_reference_insert_pieces (newvuse, ref->set,
    1615                 :            :                                                      ref->base_set, ref->type,
    1616                 :            :                                                      newoperands,
    1617                 :            :                                                      result, new_val_id);
    1618                 :    1707160 :                 newoperands = vNULL;
    1619                 :            :               }
    1620                 :    1979400 :             PRE_EXPR_REFERENCE (expr) = newref;
    1621                 :    1979400 :             get_or_alloc_expression_id (expr);
    1622                 :    1979400 :             add_to_value (new_val_id, expr);
    1623                 :            :           }
    1624                 :    3669490 :         newoperands.release ();
    1625                 :            :         return expr;
    1626                 :            :       }
    1627                 :   16614600 :       break;
    1628                 :            : 
    1629                 :   16614600 :     case NAME:
    1630                 :   16614600 :       {
    1631                 :   16614600 :         tree name = PRE_EXPR_NAME (expr);
    1632                 :   16614600 :         gimple *def_stmt = SSA_NAME_DEF_STMT (name);
    1633                 :            :         /* If the SSA name is defined by a PHI node in this block,
    1634                 :            :            translate it.  */
    1635                 :   16614600 :         if (gimple_code (def_stmt) == GIMPLE_PHI
    1636                 :   16614600 :             && gimple_bb (def_stmt) == phiblock)
    1637                 :            :           {
    1638                 :    4037680 :             tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
    1639                 :            : 
    1640                 :            :             /* Handle constant. */
    1641                 :    4037680 :             if (is_gimple_min_invariant (def))
    1642                 :    1128440 :               return get_or_alloc_expr_for_constant (def);
    1643                 :            : 
    1644                 :    2909240 :             return get_or_alloc_expr_for_name (def);
    1645                 :            :           }
    1646                 :            :         /* Otherwise return it unchanged - it will get removed if its
    1647                 :            :            value is not available in PREDs AVAIL_OUT set of expressions
    1648                 :            :            by the subtraction of TMP_GEN.  */
    1649                 :            :         return expr;
    1650                 :            :       }
    1651                 :            : 
    1652                 :          0 :     default:
    1653                 :          0 :       gcc_unreachable ();
    1654                 :            :     }
    1655                 :            : }
    1656                 :            : 
    1657                 :            : /* Wrapper around phi_translate_1 providing caching functionality.  */
    1658                 :            : 
    1659                 :            : static pre_expr
    1660                 :   67000700 : phi_translate (bitmap_set_t dest, pre_expr expr,
    1661                 :            :                bitmap_set_t set1, bitmap_set_t set2, edge e)
    1662                 :            : {
    1663                 :   67000700 :   expr_pred_trans_t slot = NULL;
    1664                 :   67000700 :   pre_expr phitrans;
    1665                 :            : 
    1666                 :   67000700 :   if (!expr)
    1667                 :            :     return NULL;
    1668                 :            : 
    1669                 :            :   /* Constants contain no values that need translation.  */
    1670                 :   65685100 :   if (expr->kind == CONSTANT)
    1671                 :            :     return expr;
    1672                 :            : 
    1673                 :   65685100 :   if (value_id_constant_p (get_expr_value_id (expr)))
    1674                 :            :     return expr;
    1675                 :            : 
    1676                 :            :   /* Don't add translations of NAMEs as those are cheap to translate.  */
    1677                 :   65685100 :   if (expr->kind != NAME)
    1678                 :            :     {
    1679                 :   49070500 :       if (phi_trans_add (&slot, expr, e->src))
    1680                 :   35310200 :         return slot->v;
    1681                 :            :       /* Store NULL for the value we want to return in the case of
    1682                 :            :          recursing.  */
    1683                 :   13760300 :       slot->v = NULL;
    1684                 :            :     }
    1685                 :            : 
    1686                 :            :   /* Translate.  */
    1687                 :   30374900 :   basic_block saved_valueize_bb = vn_context_bb;
    1688                 :   30374900 :   vn_context_bb = e->src;
    1689                 :   30374900 :   phitrans = phi_translate_1 (dest, expr, set1, set2, e);
    1690                 :   30374900 :   vn_context_bb = saved_valueize_bb;
    1691                 :            : 
    1692                 :   30374900 :   if (slot)
    1693                 :            :     {
    1694                 :   13760300 :       if (phitrans)
    1695                 :   11118400 :         slot->v = phitrans;
    1696                 :            :       else
    1697                 :            :         /* Remove failed translations again, they cause insert
    1698                 :            :            iteration to not pick up new opportunities reliably.  */
    1699                 :    2641850 :         phi_translate_table->remove_elt_with_hash (slot, slot->hashcode);
    1700                 :            :     }
    1701                 :            : 
    1702                 :            :   return phitrans;
    1703                 :            : }
    1704                 :            : 
    1705                 :            : 
    1706                 :            : /* For each expression in SET, translate the values through phi nodes
    1707                 :            :    in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
    1708                 :            :    expressions in DEST.  */
    1709                 :            : 
    1710                 :            : static void
    1711                 :   10241100 : phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e)
    1712                 :            : {
    1713                 :   10241100 :   vec<pre_expr> exprs;
    1714                 :   10241100 :   pre_expr expr;
    1715                 :   10241100 :   int i;
    1716                 :            : 
    1717                 :   10241100 :   if (gimple_seq_empty_p (phi_nodes (e->dest)))
    1718                 :            :     {
    1719                 :    5954360 :       bitmap_set_copy (dest, set);
    1720                 :    5954360 :       return;
    1721                 :            :     }
    1722                 :            : 
    1723                 :    4286780 :   exprs = sorted_array_from_bitmap_set (set);
    1724                 :   28272100 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    1725                 :            :     {
    1726                 :   23985300 :       pre_expr translated;
    1727                 :   23985300 :       translated = phi_translate (dest, expr, set, NULL, e);
    1728                 :   23985300 :       if (!translated)
    1729                 :    1251690 :         continue;
    1730                 :            : 
    1731                 :   22733700 :       bitmap_insert_into_set (dest, translated);
    1732                 :            :     }
    1733                 :    4286780 :   exprs.release ();
    1734                 :            : }
    1735                 :            : 
    1736                 :            : /* Find the leader for a value (i.e., the name representing that
    1737                 :            :    value) in a given set, and return it.  Return NULL if no leader
    1738                 :            :    is found.  */
    1739                 :            : 
    1740                 :            : static pre_expr
    1741                 :   46151000 : bitmap_find_leader (bitmap_set_t set, unsigned int val)
    1742                 :            : {
    1743                 :   46151000 :   if (value_id_constant_p (val))
    1744                 :            :     {
    1745                 :    1691770 :       unsigned int i;
    1746                 :    1691770 :       bitmap_iterator bi;
    1747                 :    1691770 :       bitmap exprset = value_expressions[val];
    1748                 :            : 
    1749                 :    1713700 :       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
    1750                 :            :         {
    1751                 :    1713700 :           pre_expr expr = expression_for_id (i);
    1752                 :    1713700 :           if (expr->kind == CONSTANT)
    1753                 :    1691770 :             return expr;
    1754                 :            :         }
    1755                 :            :     }
    1756                 :   44459200 :   if (bitmap_set_contains_value (set, val))
    1757                 :            :     {
    1758                 :            :       /* Rather than walk the entire bitmap of expressions, and see
    1759                 :            :          whether any of them has the value we are looking for, we look
    1760                 :            :          at the reverse mapping, which tells us the set of expressions
    1761                 :            :          that have a given value (IE value->expressions with that
    1762                 :            :          value) and see if any of those expressions are in our set.
    1763                 :            :          The number of expressions per value is usually significantly
    1764                 :            :          less than the number of expressions in the set.  In fact, for
    1765                 :            :          large testcases, doing it this way is roughly 5-10x faster
    1766                 :            :          than walking the bitmap.
    1767                 :            :          If this is somehow a significant lose for some cases, we can
    1768                 :            :          choose which set to walk based on which set is smaller.  */
    1769                 :   17901700 :       unsigned int i;
    1770                 :   17901700 :       bitmap_iterator bi;
    1771                 :   17901700 :       bitmap exprset = value_expressions[val];
    1772                 :            : 
    1773                 :   17901700 :       EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
    1774                 :   16758300 :         return expression_for_id (i);
    1775                 :            :     }
    1776                 :            :   return NULL;
    1777                 :            : }
    1778                 :            : 
    1779                 :            : /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
    1780                 :            :    BLOCK by seeing if it is not killed in the block.  Note that we are
    1781                 :            :    only determining whether there is a store that kills it.  Because
    1782                 :            :    of the order in which clean iterates over values, we are guaranteed
    1783                 :            :    that altered operands will have caused us to be eliminated from the
    1784                 :            :    ANTIC_IN set already.  */
    1785                 :            : 
    1786                 :            : static bool
    1787                 :     868917 : value_dies_in_block_x (pre_expr expr, basic_block block)
    1788                 :            : {
    1789                 :     868917 :   tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
    1790                 :     868917 :   vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
    1791                 :     868917 :   gimple *def;
    1792                 :     868917 :   gimple_stmt_iterator gsi;
    1793                 :     868917 :   unsigned id = get_expression_id (expr);
    1794                 :     868917 :   bool res = false;
    1795                 :     868917 :   ao_ref ref;
    1796                 :            : 
    1797                 :     868917 :   if (!vuse)
    1798                 :            :     return false;
    1799                 :            : 
    1800                 :            :   /* Lookup a previously calculated result.  */
    1801                 :     868917 :   if (EXPR_DIES (block)
    1802                 :     868917 :       && bitmap_bit_p (EXPR_DIES (block), id * 2))
    1803                 :      66756 :     return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
    1804                 :            : 
    1805                 :            :   /* A memory expression {e, VUSE} dies in the block if there is a
    1806                 :            :      statement that may clobber e.  If, starting statement walk from the
    1807                 :            :      top of the basic block, a statement uses VUSE there can be no kill
    1808                 :            :      inbetween that use and the original statement that loaded {e, VUSE},
    1809                 :            :      so we can stop walking.  */
    1810                 :     802161 :   ref.base = NULL_TREE;
    1811                 :    7758940 :   for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
    1812                 :            :     {
    1813                 :    6823810 :       tree def_vuse, def_vdef;
    1814                 :    6823810 :       def = gsi_stmt (gsi);
    1815                 :    6823810 :       def_vuse = gimple_vuse (def);
    1816                 :    6823810 :       def_vdef = gimple_vdef (def);
    1817                 :            : 
    1818                 :            :       /* Not a memory statement.  */
    1819                 :    6823810 :       if (!def_vuse)
    1820                 :    5043190 :         continue;
    1821                 :            : 
    1822                 :            :       /* Not a may-def.  */
    1823                 :    1780620 :       if (!def_vdef)
    1824                 :            :         {
    1825                 :            :           /* A load with the same VUSE, we're done.  */
    1826                 :     489194 :           if (def_vuse == vuse)
    1827                 :            :             break;
    1828                 :            : 
    1829                 :     281182 :           continue;
    1830                 :            :         }
    1831                 :            : 
    1832                 :            :       /* Init ref only if we really need it.  */
    1833                 :    1291430 :       if (ref.base == NULL_TREE
    1834                 :    1291430 :           && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->base_set,
    1835                 :            :                                              refx->type, refx->operands))
    1836                 :            :         {
    1837                 :            :           res = true;
    1838                 :            :           break;
    1839                 :            :         }
    1840                 :            :       /* If the statement may clobber expr, it dies.  */
    1841                 :    1267310 :       if (stmt_may_clobber_ref_p_1 (def, &ref))
    1842                 :            :         {
    1843                 :            :           res = true;
    1844                 :            :           break;
    1845                 :            :         }
    1846                 :            :     }
    1847                 :            : 
    1848                 :            :   /* Remember the result.  */
    1849                 :     802161 :   if (!EXPR_DIES (block))
    1850                 :     382779 :     EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
    1851                 :     802161 :   bitmap_set_bit (EXPR_DIES (block), id * 2);
    1852                 :     802161 :   if (res)
    1853                 :     461176 :     bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
    1854                 :            : 
    1855                 :            :   return res;
    1856                 :            : }
    1857                 :            : 
    1858                 :            : 
    1859                 :            : /* Determine if OP is valid in SET1 U SET2, which it is when the union
    1860                 :            :    contains its value-id.  */
    1861                 :            : 
    1862                 :            : static bool
    1863                 :   81186800 : op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
    1864                 :            : {
    1865                 :   81186800 :   if (op && TREE_CODE (op) == SSA_NAME)
    1866                 :            :     {
    1867                 :   22335100 :       unsigned int value_id = VN_INFO (op)->value_id;
    1868                 :   22335100 :       if (!(bitmap_set_contains_value (set1, value_id)
    1869                 :     658559 :             || (set2 && bitmap_set_contains_value  (set2, value_id))))
    1870                 :    1146180 :         return false;
    1871                 :            :     }
    1872                 :            :   return true;
    1873                 :            : }
    1874                 :            : 
    1875                 :            : /* Determine if the expression EXPR is valid in SET1 U SET2.
    1876                 :            :    ONLY SET2 CAN BE NULL.
    1877                 :            :    This means that we have a leader for each part of the expression
    1878                 :            :    (if it consists of values), or the expression is an SSA_NAME.
    1879                 :            :    For loads/calls, we also see if the vuse is killed in this block.  */
    1880                 :            : 
    1881                 :            : static bool
    1882                 :   35388200 : valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
    1883                 :            : {
    1884                 :   35388200 :   switch (expr->kind)
    1885                 :            :     {
    1886                 :            :     case NAME:
    1887                 :            :       /* By construction all NAMEs are available.  Non-available
    1888                 :            :          NAMEs are removed by subtracting TMP_GEN from the sets.  */
    1889                 :            :       return true;
    1890                 :   13648400 :     case NARY:
    1891                 :   13648400 :       {
    1892                 :   13648400 :         unsigned int i;
    1893                 :   13648400 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    1894                 :   36028000 :         for (i = 0; i < nary->length; i++)
    1895                 :   23385300 :           if (!op_valid_in_sets (set1, set2, nary->op[i]))
    1896                 :            :             return false;
    1897                 :            :         return true;
    1898                 :            :       }
    1899                 :    6362070 :       break;
    1900                 :    6362070 :     case REFERENCE:
    1901                 :    6362070 :       {
    1902                 :    6362070 :         vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    1903                 :    6362070 :         vn_reference_op_t vro;
    1904                 :    6362070 :         unsigned int i;
    1905                 :            : 
    1906                 :   25582400 :         FOR_EACH_VEC_ELT (ref->operands, i, vro)
    1907                 :            :           {
    1908                 :   19360800 :             if (!op_valid_in_sets (set1, set2, vro->op0)
    1909                 :   19220400 :                 || !op_valid_in_sets (set1, set2, vro->op1)
    1910                 :   38581100 :                 || !op_valid_in_sets (set1, set2, vro->op2))
    1911                 :     140407 :               return false;
    1912                 :            :           }
    1913                 :            :         return true;
    1914                 :            :       }
    1915                 :          0 :     default:
    1916                 :          0 :       gcc_unreachable ();
    1917                 :            :     }
    1918                 :            : }
    1919                 :            : 
    1920                 :            : /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
    1921                 :            :    This means expressions that are made up of values we have no leaders for
    1922                 :            :    in SET1 or SET2.  */
    1923                 :            : 
    1924                 :            : static void
    1925                 :    9081030 : clean (bitmap_set_t set1, bitmap_set_t set2 = NULL)
    1926                 :            : {
    1927                 :    9081030 :   vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
    1928                 :    9081030 :   pre_expr expr;
    1929                 :    9081030 :   int i;
    1930                 :            : 
    1931                 :   44469200 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    1932                 :            :     {
    1933                 :   35388200 :       if (!valid_in_sets (set1, set2, expr))
    1934                 :            :         {
    1935                 :    1146180 :           unsigned int val  = get_expr_value_id (expr);
    1936                 :    1146180 :           bitmap_clear_bit (&set1->expressions, get_expression_id (expr));
    1937                 :            :           /* We are entered with possibly multiple expressions for a value
    1938                 :            :              so before removing a value from the set see if there's an
    1939                 :            :              expression for it left.  */
    1940                 :    1146180 :           if (! bitmap_find_leader (set1, val))
    1941                 :    1143420 :             bitmap_clear_bit (&set1->values, val);
    1942                 :            :         }
    1943                 :            :     }
    1944                 :    9081030 :   exprs.release ();
    1945                 :    9081030 : }
    1946                 :            : 
    1947                 :            : /* Clean the set of expressions that are no longer valid in SET because
    1948                 :            :    they are clobbered in BLOCK or because they trap and may not be executed.  */
    1949                 :            : 
    1950                 :            : static void
    1951                 :   10550700 : prune_clobbered_mems (bitmap_set_t set, basic_block block)
    1952                 :            : {
    1953                 :   10550700 :   bitmap_iterator bi;
    1954                 :   10550700 :   unsigned i;
    1955                 :   10550700 :   unsigned to_remove = -1U;
    1956                 :   10550700 :   bool any_removed = false;
    1957                 :            : 
    1958                 :   46643000 :   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
    1959                 :            :     {
    1960                 :            :       /* Remove queued expr.  */
    1961                 :   36092300 :       if (to_remove != -1U)
    1962                 :            :         {
    1963                 :     341066 :           bitmap_clear_bit (&set->expressions, to_remove);
    1964                 :     341066 :           any_removed = true;
    1965                 :     341066 :           to_remove = -1U;
    1966                 :            :         }
    1967                 :            : 
    1968                 :   36092300 :       pre_expr expr = expression_for_id (i);
    1969                 :   36092300 :       if (expr->kind == REFERENCE)
    1970                 :            :         {
    1971                 :    5730250 :           vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    1972                 :    5730250 :           if (ref->vuse)
    1973                 :            :             {
    1974                 :    5146310 :               gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
    1975                 :    5146310 :               if (!gimple_nop_p (def_stmt)
    1976                 :    5146310 :                   && ((gimple_bb (def_stmt) != block
    1977                 :    2572250 :                        && !dominated_by_p (CDI_DOMINATORS,
    1978                 :    2572250 :                                            block, gimple_bb (def_stmt)))
    1979                 :    3426430 :                       || (gimple_bb (def_stmt) == block
    1980                 :     868917 :                           && value_dies_in_block_x (expr, block))))
    1981                 :     512606 :                 to_remove = i;
    1982                 :            :             }
    1983                 :            :         }
    1984                 :   30362100 :       else if (expr->kind == NARY)
    1985                 :            :         {
    1986                 :   13959100 :           vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    1987                 :            :           /* If the NARY may trap make sure the block does not contain
    1988                 :            :              a possible exit point.
    1989                 :            :              ???  This is overly conservative if we translate AVAIL_OUT
    1990                 :            :              as the available expression might be after the exit point.  */
    1991                 :   13959100 :           if (BB_MAY_NOTRETURN (block)
    1992                 :   13959100 :               && vn_nary_may_trap (nary))
    1993                 :      42941 :             to_remove = i;
    1994                 :            :         }
    1995                 :            :     }
    1996                 :            : 
    1997                 :            :   /* Remove queued expr.  */
    1998                 :   10550700 :   if (to_remove != -1U)
    1999                 :            :     {
    2000                 :     214481 :       bitmap_clear_bit (&set->expressions, to_remove);
    2001                 :     214481 :       any_removed = true;
    2002                 :            :     }
    2003                 :            : 
    2004                 :            :   /* Above we only removed expressions, now clean the set of values
    2005                 :            :      which no longer have any corresponding expression.  We cannot
    2006                 :            :      clear the value at the time we remove an expression since there
    2007                 :            :      may be multiple expressions per value.
    2008                 :            :      If we'd queue possibly to be removed values we could use
    2009                 :            :      the bitmap_find_leader way to see if there's still an expression
    2010                 :            :      for it.  For some ratio of to be removed values and number of
    2011                 :            :      values/expressions in the set this might be faster than rebuilding
    2012                 :            :      the value-set.  */
    2013                 :   10550700 :   if (any_removed)
    2014                 :            :     {
    2015                 :     329398 :       bitmap_clear (&set->values);
    2016                 :    2063820 :       FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
    2017                 :            :         {
    2018                 :    1734420 :           pre_expr expr = expression_for_id (i);
    2019                 :    1734420 :           unsigned int value_id = get_expr_value_id (expr);
    2020                 :    1734420 :           bitmap_set_bit (&set->values, value_id);
    2021                 :            :         }
    2022                 :            :     }
    2023                 :   10550700 : }
    2024                 :            : 
    2025                 :            : /* Compute the ANTIC set for BLOCK.
    2026                 :            : 
    2027                 :            :    If succs(BLOCK) > 1 then
    2028                 :            :      ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
    2029                 :            :    else if succs(BLOCK) == 1 then
    2030                 :            :      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
    2031                 :            : 
    2032                 :            :    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
    2033                 :            : 
    2034                 :            :    Note that clean() is deferred until after the iteration.  */
    2035                 :            : 
    2036                 :            : static bool
    2037                 :    9850510 : compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
    2038                 :            : {
    2039                 :    9850510 :   bitmap_set_t S, old, ANTIC_OUT;
    2040                 :    9850510 :   edge e;
    2041                 :    9850510 :   edge_iterator ei;
    2042                 :            : 
    2043                 :    9850510 :   bool was_visited = BB_VISITED (block);
    2044                 :    9850510 :   bool changed = ! BB_VISITED (block);
    2045                 :    9850510 :   BB_VISITED (block) = 1;
    2046                 :    9850510 :   old = ANTIC_OUT = S = NULL;
    2047                 :            : 
    2048                 :            :   /* If any edges from predecessors are abnormal, antic_in is empty,
    2049                 :            :      so do nothing.  */
    2050                 :    9850510 :   if (block_has_abnormal_pred_edge)
    2051                 :       3398 :     goto maybe_dump_sets;
    2052                 :            : 
    2053                 :    9847110 :   old = ANTIC_IN (block);
    2054                 :    9847110 :   ANTIC_OUT = bitmap_set_new ();
    2055                 :            : 
    2056                 :            :   /* If the block has no successors, ANTIC_OUT is empty.  */
    2057                 :    9847110 :   if (EDGE_COUNT (block->succs) == 0)
    2058                 :            :     ;
    2059                 :            :   /* If we have one successor, we could have some phi nodes to
    2060                 :            :      translate through.  */
    2061                 :    9847110 :   else if (single_succ_p (block))
    2062                 :            :     {
    2063                 :    6320910 :       e = single_succ_edge (block);
    2064                 :    6320910 :       gcc_assert (BB_VISITED (e->dest));
    2065                 :    6320910 :       phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
    2066                 :            :     }
    2067                 :            :   /* If we have multiple successors, we take the intersection of all of
    2068                 :            :      them.  Note that in the case of loop exit phi nodes, we may have
    2069                 :            :      phis to translate through.  */
    2070                 :            :   else
    2071                 :            :     {
    2072                 :    3526200 :       size_t i;
    2073                 :    3526200 :       edge first = NULL;
    2074                 :            : 
    2075                 :    7052400 :       auto_vec<edge> worklist (EDGE_COUNT (block->succs));
    2076                 :   10628000 :       FOR_EACH_EDGE (e, ei, block->succs)
    2077                 :            :         {
    2078                 :    7101840 :           if (!first
    2079                 :    3732470 :               && BB_VISITED (e->dest))
    2080                 :            :             first = e;
    2081                 :    3575640 :           else if (BB_VISITED (e->dest))
    2082                 :   10308500 :             worklist.quick_push (e);
    2083                 :            :           else
    2084                 :            :             {
    2085                 :            :               /* Unvisited successors get their ANTIC_IN replaced by the
    2086                 :            :                  maximal set to arrive at a maximum ANTIC_IN solution.
    2087                 :            :                  We can ignore them in the intersection operation and thus
    2088                 :            :                  need not explicitely represent that maximum solution.  */
    2089                 :     369033 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2090                 :         22 :                 fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
    2091                 :         22 :                          e->src->index, e->dest->index);
    2092                 :            :             }
    2093                 :            :         }
    2094                 :            : 
    2095                 :            :       /* Of multiple successors we have to have visited one already
    2096                 :            :          which is guaranteed by iteration order.  */
    2097                 :    3526200 :       gcc_assert (first != NULL);
    2098                 :            : 
    2099                 :    3526200 :       phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest), first);
    2100                 :            : 
    2101                 :            :       /* If we have multiple successors we need to intersect the ANTIC_OUT
    2102                 :            :          sets.  For values that's a simple intersection but for
    2103                 :            :          expressions it is a union.  Given we want to have a single
    2104                 :            :          expression per value in our sets we have to canonicalize.
    2105                 :            :          Avoid randomness and running into cycles like for PR82129 and
    2106                 :            :          canonicalize the expression we choose to the one with the
    2107                 :            :          lowest id.  This requires we actually compute the union first.  */
    2108                 :   10259000 :       FOR_EACH_VEC_ELT (worklist, i, e)
    2109                 :            :         {
    2110                 :    3206610 :           if (!gimple_seq_empty_p (phi_nodes (e->dest)))
    2111                 :            :             {
    2112                 :       1933 :               bitmap_set_t tmp = bitmap_set_new ();
    2113                 :       1933 :               phi_translate_set (tmp, ANTIC_IN (e->dest), e);
    2114                 :       1933 :               bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
    2115                 :       1933 :               bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
    2116                 :    3208540 :               bitmap_set_free (tmp);
    2117                 :            :             }
    2118                 :            :           else
    2119                 :            :             {
    2120                 :    3204680 :               bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
    2121                 :    3204680 :               bitmap_ior_into (&ANTIC_OUT->expressions,
    2122                 :    3204680 :                                &ANTIC_IN (e->dest)->expressions);
    2123                 :            :             }
    2124                 :            :         }
    2125                 :    3526200 :       if (! worklist.is_empty ())
    2126                 :            :         {
    2127                 :            :           /* Prune expressions not in the value set.  */
    2128                 :    3161230 :           bitmap_iterator bi;
    2129                 :    3161230 :           unsigned int i;
    2130                 :    3161230 :           unsigned int to_clear = -1U;
    2131                 :   22547500 :           FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)
    2132                 :            :             {
    2133                 :   19386300 :               if (to_clear != -1U)
    2134                 :            :                 {
    2135                 :    9834510 :                   bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
    2136                 :    9834510 :                   to_clear = -1U;
    2137                 :            :                 }
    2138                 :   19386300 :               pre_expr expr = expression_for_id (i);
    2139                 :   19386300 :               unsigned int value_id = get_expr_value_id (expr);
    2140                 :   19386300 :               if (!bitmap_bit_p (&ANTIC_OUT->values, value_id))
    2141                 :   12043800 :                 to_clear = i;
    2142                 :            :             }
    2143                 :    3161230 :           if (to_clear != -1U)
    2144                 :    2209270 :             bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
    2145                 :            :         }
    2146                 :            :     }
    2147                 :            : 
    2148                 :            :   /* Prune expressions that are clobbered in block and thus become
    2149                 :            :      invalid if translated from ANTIC_OUT to ANTIC_IN.  */
    2150                 :    9847110 :   prune_clobbered_mems (ANTIC_OUT, block);
    2151                 :            : 
    2152                 :            :   /* Generate ANTIC_OUT - TMP_GEN.  */
    2153                 :    9847110 :   S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block));
    2154                 :            : 
    2155                 :            :   /* Start ANTIC_IN with EXP_GEN - TMP_GEN.  */
    2156                 :   19694200 :   ANTIC_IN (block) = bitmap_set_subtract_expressions (EXP_GEN (block),
    2157                 :    9847110 :                                                       TMP_GEN (block));
    2158                 :            : 
    2159                 :            :   /* Then union in the ANTIC_OUT - TMP_GEN values,
    2160                 :            :      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
    2161                 :    9847110 :   bitmap_ior_into (&ANTIC_IN (block)->values, &S->values);
    2162                 :    9847110 :   bitmap_ior_into (&ANTIC_IN (block)->expressions, &S->expressions);
    2163                 :            : 
    2164                 :            :   /* clean (ANTIC_IN (block)) is defered to after the iteration converged
    2165                 :            :      because it can cause non-convergence, see for example PR81181.  */
    2166                 :            : 
    2167                 :            :   /* Intersect ANTIC_IN with the old ANTIC_IN.  This is required until
    2168                 :            :      we properly represent the maximum expression set, thus not prune
    2169                 :            :      values without expressions during the iteration.  */
    2170                 :    9847110 :   if (was_visited
    2171                 :    9847110 :       && bitmap_and_into (&ANTIC_IN (block)->values, &old->values))
    2172                 :            :     {
    2173                 :         12 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2174                 :          0 :         fprintf (dump_file, "warning: intersecting with old ANTIC_IN "
    2175                 :            :                  "shrinks the set\n");
    2176                 :            :       /* Prune expressions not in the value set.  */
    2177                 :         12 :       bitmap_iterator bi;
    2178                 :         12 :       unsigned int i;
    2179                 :         12 :       unsigned int to_clear = -1U;
    2180                 :        102 :       FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi)
    2181                 :            :         {
    2182                 :         90 :           if (to_clear != -1U)
    2183                 :            :             {
    2184                 :          6 :               bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
    2185                 :          6 :               to_clear = -1U;
    2186                 :            :             }
    2187                 :         90 :           pre_expr expr = expression_for_id (i);
    2188                 :         90 :           unsigned int value_id = get_expr_value_id (expr);
    2189                 :         90 :           if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id))
    2190                 :         12 :             to_clear = i;
    2191                 :            :         }
    2192                 :         12 :       if (to_clear != -1U)
    2193                 :          6 :         bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
    2194                 :            :     }
    2195                 :            : 
    2196                 :    9847110 :   if (!bitmap_set_equal (old, ANTIC_IN (block)))
    2197                 :    6159940 :     changed = true;
    2198                 :            : 
    2199                 :    3687180 :  maybe_dump_sets:
    2200                 :    9850510 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2201                 :            :     {
    2202                 :        198 :       if (ANTIC_OUT)
    2203                 :        198 :         print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
    2204                 :            : 
    2205                 :        198 :       if (changed)
    2206                 :        175 :         fprintf (dump_file, "[changed] ");
    2207                 :        198 :       print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
    2208                 :            :                         block->index);
    2209                 :            : 
    2210                 :        198 :       if (S)
    2211                 :        198 :         print_bitmap_set (dump_file, S, "S", block->index);
    2212                 :            :     }
    2213                 :    9850510 :   if (old)
    2214                 :    9847110 :     bitmap_set_free (old);
    2215                 :    9850510 :   if (S)
    2216                 :    9847110 :     bitmap_set_free (S);
    2217                 :    9850510 :   if (ANTIC_OUT)
    2218                 :    9847110 :     bitmap_set_free (ANTIC_OUT);
    2219                 :    9850510 :   return changed;
    2220                 :            : }
    2221                 :            : 
    2222                 :            : /* Compute PARTIAL_ANTIC for BLOCK.
    2223                 :            : 
    2224                 :            :    If succs(BLOCK) > 1 then
    2225                 :            :      PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
    2226                 :            :      in ANTIC_OUT for all succ(BLOCK)
    2227                 :            :    else if succs(BLOCK) == 1 then
    2228                 :            :      PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
    2229                 :            : 
    2230                 :            :    PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
    2231                 :            : 
    2232                 :            : */
    2233                 :            : static void
    2234                 :     704606 : compute_partial_antic_aux (basic_block block,
    2235                 :            :                            bool block_has_abnormal_pred_edge)
    2236                 :            : {
    2237                 :     704606 :   bitmap_set_t old_PA_IN;
    2238                 :     704606 :   bitmap_set_t PA_OUT;
    2239                 :     704606 :   edge e;
    2240                 :     704606 :   edge_iterator ei;
    2241                 :     704606 :   unsigned long max_pa = param_max_partial_antic_length;
    2242                 :            : 
    2243                 :     704606 :   old_PA_IN = PA_OUT = NULL;
    2244                 :            : 
    2245                 :            :   /* If any edges from predecessors are abnormal, antic_in is empty,
    2246                 :            :      so do nothing.  */
    2247                 :     704606 :   if (block_has_abnormal_pred_edge)
    2248                 :        663 :     goto maybe_dump_sets;
    2249                 :            : 
    2250                 :            :   /* If there are too many partially anticipatable values in the
    2251                 :            :      block, phi_translate_set can take an exponential time: stop
    2252                 :            :      before the translation starts.  */
    2253                 :     703943 :   if (max_pa
    2254                 :     703940 :       && single_succ_p (block)
    2255                 :    1142060 :       && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
    2256                 :        389 :     goto maybe_dump_sets;
    2257                 :            : 
    2258                 :     703554 :   old_PA_IN = PA_IN (block);
    2259                 :     703554 :   PA_OUT = bitmap_set_new ();
    2260                 :            : 
    2261                 :            :   /* If the block has no successors, ANTIC_OUT is empty.  */
    2262                 :     703554 :   if (EDGE_COUNT (block->succs) == 0)
    2263                 :            :     ;
    2264                 :            :   /* If we have one successor, we could have some phi nodes to
    2265                 :            :      translate through.  Note that we can't phi translate across DFS
    2266                 :            :      back edges in partial antic, because it uses a union operation on
    2267                 :            :      the successors.  For recurrences like IV's, we will end up
    2268                 :            :      generating a new value in the set on each go around (i + 3 (VH.1)
    2269                 :            :      VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
    2270                 :     650864 :   else if (single_succ_p (block))
    2271                 :            :     {
    2272                 :     437729 :       e = single_succ_edge (block);
    2273                 :     437729 :       if (!(e->flags & EDGE_DFS_BACK))
    2274                 :     391509 :         phi_translate_set (PA_OUT, PA_IN (e->dest), e);
    2275                 :            :     }
    2276                 :            :   /* If we have multiple successors, we take the union of all of
    2277                 :            :      them.  */
    2278                 :            :   else
    2279                 :            :     {
    2280                 :     213135 :       size_t i;
    2281                 :            : 
    2282                 :     426270 :       auto_vec<edge> worklist (EDGE_COUNT (block->succs));
    2283                 :     641087 :       FOR_EACH_EDGE (e, ei, block->succs)
    2284                 :            :         {
    2285                 :     427952 :           if (e->flags & EDGE_DFS_BACK)
    2286                 :        191 :             continue;
    2287                 :     855713 :           worklist.quick_push (e);
    2288                 :            :         }
    2289                 :     213135 :       if (worklist.length () > 0)
    2290                 :            :         {
    2291                 :     854031 :           FOR_EACH_VEC_ELT (worklist, i, e)
    2292                 :            :             {
    2293                 :     427761 :               unsigned int i;
    2294                 :     427761 :               bitmap_iterator bi;
    2295                 :            : 
    2296                 :    3343990 :               FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi)
    2297                 :    2916230 :                 bitmap_value_insert_into_set (PA_OUT,
    2298                 :            :                                               expression_for_id (i));
    2299                 :     427761 :               if (!gimple_seq_empty_p (phi_nodes (e->dest)))
    2300                 :            :                 {
    2301                 :        582 :                   bitmap_set_t pa_in = bitmap_set_new ();
    2302                 :        582 :                   phi_translate_set (pa_in, PA_IN (e->dest), e);
    2303                 :        582 :                   FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
    2304                 :          0 :                     bitmap_value_insert_into_set (PA_OUT,
    2305                 :            :                                                   expression_for_id (i));
    2306                 :     428343 :                   bitmap_set_free (pa_in);
    2307                 :            :                 }
    2308                 :            :               else
    2309                 :    2232390 :                 FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi)
    2310                 :    1805210 :                   bitmap_value_insert_into_set (PA_OUT,
    2311                 :            :                                                 expression_for_id (i));
    2312                 :            :             }
    2313                 :            :         }
    2314                 :            :     }
    2315                 :            : 
    2316                 :            :   /* Prune expressions that are clobbered in block and thus become
    2317                 :            :      invalid if translated from PA_OUT to PA_IN.  */
    2318                 :     703554 :   prune_clobbered_mems (PA_OUT, block);
    2319                 :            : 
    2320                 :            :   /* PA_IN starts with PA_OUT - TMP_GEN.
    2321                 :            :      Then we subtract things from ANTIC_IN.  */
    2322                 :     703554 :   PA_IN (block) = bitmap_set_subtract_expressions (PA_OUT, TMP_GEN (block));
    2323                 :            : 
    2324                 :            :   /* For partial antic, we want to put back in the phi results, since
    2325                 :            :      we will properly avoid making them partially antic over backedges.  */
    2326                 :     703554 :   bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
    2327                 :     703554 :   bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
    2328                 :            : 
    2329                 :            :   /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
    2330                 :     703554 :   bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
    2331                 :            : 
    2332                 :     703554 :   clean (PA_IN (block), ANTIC_IN (block));
    2333                 :            : 
    2334                 :     704606 :  maybe_dump_sets:
    2335                 :     704606 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2336                 :            :     {
    2337                 :          0 :       if (PA_OUT)
    2338                 :          0 :         print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
    2339                 :            : 
    2340                 :          0 :       print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
    2341                 :            :     }
    2342                 :     704606 :   if (old_PA_IN)
    2343                 :     703554 :     bitmap_set_free (old_PA_IN);
    2344                 :     704606 :   if (PA_OUT)
    2345                 :     703554 :     bitmap_set_free (PA_OUT);
    2346                 :     704606 : }
    2347                 :            : 
    2348                 :            : /* Compute ANTIC and partial ANTIC sets.  */
    2349                 :            : 
    2350                 :            : static void
    2351                 :     645448 : compute_antic (void)
    2352                 :            : {
    2353                 :     645448 :   bool changed = true;
    2354                 :     645448 :   int num_iterations = 0;
    2355                 :     645448 :   basic_block block;
    2356                 :     645448 :   int i;
    2357                 :     645448 :   edge_iterator ei;
    2358                 :     645448 :   edge e;
    2359                 :            : 
    2360                 :            :   /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
    2361                 :            :      We pre-build the map of blocks with incoming abnormal edges here.  */
    2362                 :     645448 :   auto_sbitmap has_abnormal_preds (last_basic_block_for_fn (cfun));
    2363                 :     645448 :   bitmap_clear (has_abnormal_preds);
    2364                 :            : 
    2365                 :   10313800 :   FOR_ALL_BB_FN (block, cfun)
    2366                 :            :     {
    2367                 :    9668380 :       BB_VISITED (block) = 0;
    2368                 :            : 
    2369                 :   21711000 :       FOR_EACH_EDGE (e, ei, block->preds)
    2370                 :   12045300 :         if (e->flags & EDGE_ABNORMAL)
    2371                 :            :           {
    2372                 :       2728 :             bitmap_set_bit (has_abnormal_preds, block->index);
    2373                 :            :             break;
    2374                 :            :           }
    2375                 :            : 
    2376                 :            :       /* While we are here, give empty ANTIC_IN sets to each block.  */
    2377                 :    9668380 :       ANTIC_IN (block) = bitmap_set_new ();
    2378                 :    9668380 :       if (do_partial_partial)
    2379                 :     704606 :         PA_IN (block) = bitmap_set_new ();
    2380                 :            :     }
    2381                 :            : 
    2382                 :            :   /* At the exit block we anticipate nothing.  */
    2383                 :     645448 :   BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
    2384                 :            : 
    2385                 :            :   /* For ANTIC computation we need a postorder that also guarantees that
    2386                 :            :      a block with a single successor is visited after its successor.
    2387                 :            :      RPO on the inverted CFG has this property.  */
    2388                 :     645448 :   auto_vec<int, 20> postorder;
    2389                 :     645448 :   inverted_post_order_compute (&postorder);
    2390                 :            : 
    2391                 :    1290900 :   auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
    2392                 :     645448 :   bitmap_clear (worklist);
    2393                 :    1769800 :   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
    2394                 :    1124360 :     bitmap_set_bit (worklist, e->src->index);
    2395                 :    1986790 :   while (changed)
    2396                 :            :     {
    2397                 :    1341340 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2398                 :         37 :         fprintf (dump_file, "Starting iteration %d\n", num_iterations);
    2399                 :            :       /* ???  We need to clear our PHI translation cache here as the
    2400                 :            :          ANTIC sets shrink and we restrict valid translations to
    2401                 :            :          those having operands with leaders in ANTIC.  Same below
    2402                 :            :          for PA ANTIC computation.  */
    2403                 :    1341340 :       num_iterations++;
    2404                 :    1341340 :       changed = false;
    2405                 :   25309100 :       for (i = postorder.length () - 1; i >= 0; i--)
    2406                 :            :         {
    2407                 :   22626400 :           if (bitmap_bit_p (worklist, postorder[i]))
    2408                 :            :             {
    2409                 :    9850510 :               basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
    2410                 :    9850510 :               bitmap_clear_bit (worklist, block->index);
    2411                 :    9850510 :               if (compute_antic_aux (block,
    2412                 :    9850510 :                                      bitmap_bit_p (has_abnormal_preds,
    2413                 :    9850510 :                                                    block->index)))
    2414                 :            :                 {
    2415                 :   20879600 :                   FOR_EACH_EDGE (e, ei, block->preds)
    2416                 :   11465600 :                     bitmap_set_bit (worklist, e->src->index);
    2417                 :            :                   changed = true;
    2418                 :            :                 }
    2419                 :            :             }
    2420                 :            :         }
    2421                 :            :       /* Theoretically possible, but *highly* unlikely.  */
    2422                 :    1341340 :       gcc_checking_assert (num_iterations < 500);
    2423                 :            :     }
    2424                 :            : 
    2425                 :            :   /* We have to clean after the dataflow problem converged as cleaning
    2426                 :            :      can cause non-convergence because it is based on expressions
    2427                 :            :      rather than values.  */
    2428                 :    9022930 :   FOR_EACH_BB_FN (block, cfun)
    2429                 :    8377480 :     clean (ANTIC_IN (block));
    2430                 :            : 
    2431                 :     645448 :   statistics_histogram_event (cfun, "compute_antic iterations",
    2432                 :            :                               num_iterations);
    2433                 :            : 
    2434                 :     645448 :   if (do_partial_partial)
    2435                 :            :     {
    2436                 :            :       /* For partial antic we ignore backedges and thus we do not need
    2437                 :            :          to perform any iteration when we process blocks in postorder.  */
    2438                 :     809986 :       for (i = postorder.length () - 1; i >= 0; i--)
    2439                 :            :         {
    2440                 :     704606 :           basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
    2441                 :    1409210 :           compute_partial_antic_aux (block,
    2442                 :     704606 :                                      bitmap_bit_p (has_abnormal_preds,
    2443                 :     704606 :                                                    block->index));
    2444                 :            :         }
    2445                 :            :     }
    2446                 :     645448 : }
    2447                 :            : 
    2448                 :            : 
    2449                 :            : /* Inserted expressions are placed onto this worklist, which is used
    2450                 :            :    for performing quick dead code elimination of insertions we made
    2451                 :            :    that didn't turn out to be necessary.   */
    2452                 :            : static bitmap inserted_exprs;
    2453                 :            : 
    2454                 :            : /* The actual worker for create_component_ref_by_pieces.  */
    2455                 :            : 
    2456                 :            : static tree
    2457                 :     760922 : create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
    2458                 :            :                                   unsigned int *operand, gimple_seq *stmts)
    2459                 :            : {
    2460                 :     760922 :   vn_reference_op_t currop = &ref->operands[*operand];
    2461                 :     760922 :   tree genop;
    2462                 :     760922 :   ++*operand;
    2463                 :     760922 :   switch (currop->opcode)
    2464                 :            :     {
    2465                 :          0 :     case CALL_EXPR:
    2466                 :          0 :       gcc_unreachable ();
    2467                 :            : 
    2468                 :     260932 :     case MEM_REF:
    2469                 :     260932 :       {
    2470                 :     260932 :         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
    2471                 :            :                                                         stmts);
    2472                 :     260932 :         if (!baseop)
    2473                 :            :           return NULL_TREE;
    2474                 :     260727 :         tree offset = currop->op0;
    2475                 :     260727 :         if (TREE_CODE (baseop) == ADDR_EXPR
    2476                 :     260727 :             && handled_component_p (TREE_OPERAND (baseop, 0)))
    2477                 :            :           {
    2478                 :          0 :             poly_int64 off;
    2479                 :          0 :             tree base;
    2480                 :          0 :             base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
    2481                 :            :                                                   &off);
    2482                 :          0 :             gcc_assert (base);
    2483                 :          0 :             offset = int_const_binop (PLUS_EXPR, offset,
    2484                 :          0 :                                       build_int_cst (TREE_TYPE (offset),
    2485                 :            :                                                      off));
    2486                 :          0 :             baseop = build_fold_addr_expr (base);
    2487                 :            :           }
    2488                 :     260727 :         genop = build2 (MEM_REF, currop->type, baseop, offset);
    2489                 :     260727 :         MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
    2490                 :     260727 :         MR_DEPENDENCE_BASE (genop) = currop->base;
    2491                 :     260727 :         REF_REVERSE_STORAGE_ORDER (genop) = currop->reverse;
    2492                 :     260727 :         return genop;
    2493                 :            :       }
    2494                 :            : 
    2495                 :          0 :     case TARGET_MEM_REF:
    2496                 :          0 :       {
    2497                 :          0 :         tree genop0 = NULL_TREE, genop1 = NULL_TREE;
    2498                 :          0 :         vn_reference_op_t nextop = &ref->operands[(*operand)++];
    2499                 :          0 :         tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
    2500                 :            :                                                         stmts);
    2501                 :          0 :         if (!baseop)
    2502                 :            :           return NULL_TREE;
    2503                 :          0 :         if (currop->op0)
    2504                 :            :           {
    2505                 :          0 :             genop0 = find_or_generate_expression (block, currop->op0, stmts);
    2506                 :          0 :             if (!genop0)
    2507                 :            :               return NULL_TREE;
    2508                 :            :           }
    2509                 :          0 :         if (nextop->op0)
    2510                 :            :           {
    2511                 :          0 :             genop1 = find_or_generate_expression (block, nextop->op0, stmts);
    2512                 :          0 :             if (!genop1)
    2513                 :            :               return NULL_TREE;
    2514                 :            :           }
    2515                 :          0 :         genop = build5 (TARGET_MEM_REF, currop->type,
    2516                 :            :                         baseop, currop->op2, genop0, currop->op1, genop1);
    2517                 :            : 
    2518                 :          0 :         MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
    2519                 :          0 :         MR_DEPENDENCE_BASE (genop) = currop->base;
    2520                 :          0 :         return genop;
    2521                 :            :       }
    2522                 :            : 
    2523                 :     171895 :     case ADDR_EXPR:
    2524                 :     171895 :       if (currop->op0)
    2525                 :            :         {
    2526                 :     166184 :           gcc_assert (is_gimple_min_invariant (currop->op0));
    2527                 :     166184 :           return currop->op0;
    2528                 :            :         }
    2529                 :            :       /* Fallthrough.  */
    2530                 :       7586 :     case REALPART_EXPR:
    2531                 :       7586 :     case IMAGPART_EXPR:
    2532                 :       7586 :     case VIEW_CONVERT_EXPR:
    2533                 :       7586 :       {
    2534                 :       7586 :         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2535                 :            :                                                         stmts);
    2536                 :       7586 :         if (!genop0)
    2537                 :            :           return NULL_TREE;
    2538                 :       7586 :         return fold_build1 (currop->opcode, currop->type, genop0);
    2539                 :            :       }
    2540                 :            : 
    2541                 :          2 :     case WITH_SIZE_EXPR:
    2542                 :          2 :       {
    2543                 :          2 :         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2544                 :            :                                                         stmts);
    2545                 :          2 :         if (!genop0)
    2546                 :            :           return NULL_TREE;
    2547                 :          2 :         tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
    2548                 :          2 :         if (!genop1)
    2549                 :            :           return NULL_TREE;
    2550                 :          2 :         return fold_build2 (currop->opcode, currop->type, genop0, genop1);
    2551                 :            :       }
    2552                 :            : 
    2553                 :        384 :     case BIT_FIELD_REF:
    2554                 :        384 :       {
    2555                 :        384 :         tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2556                 :            :                                                         stmts);
    2557                 :        384 :         if (!genop0)
    2558                 :            :           return NULL_TREE;
    2559                 :        384 :         tree op1 = currop->op0;
    2560                 :        384 :         tree op2 = currop->op1;
    2561                 :        384 :         tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
    2562                 :        384 :         REF_REVERSE_STORAGE_ORDER (t) = currop->reverse;
    2563                 :        384 :         return fold (t);
    2564                 :            :       }
    2565                 :            : 
    2566                 :            :       /* For array ref vn_reference_op's, operand 1 of the array ref
    2567                 :            :          is op0 of the reference op and operand 3 of the array ref is
    2568                 :            :          op1.  */
    2569                 :      37497 :     case ARRAY_RANGE_REF:
    2570                 :      37497 :     case ARRAY_REF:
    2571                 :      37497 :       {
    2572                 :      37497 :         tree genop0;
    2573                 :      37497 :         tree genop1 = currop->op0;
    2574                 :      37497 :         tree genop2 = currop->op1;
    2575                 :      37497 :         tree genop3 = currop->op2;
    2576                 :      37497 :         genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
    2577                 :            :                                                    stmts);
    2578                 :      37497 :         if (!genop0)
    2579                 :            :           return NULL_TREE;
    2580                 :      37497 :         genop1 = find_or_generate_expression (block, genop1, stmts);
    2581                 :      37497 :         if (!genop1)
    2582                 :            :           return NULL_TREE;
    2583                 :      37497 :         if (genop2)
    2584                 :            :           {
    2585                 :      37497 :             tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
    2586                 :            :             /* Drop zero minimum index if redundant.  */
    2587                 :      37497 :             if (integer_zerop (genop2)
    2588                 :      37497 :                 && (!domain_type
    2589                 :      36781 :                     || integer_zerop (TYPE_MIN_VALUE (domain_type))))
    2590                 :            :               genop2 = NULL_TREE;
    2591                 :            :             else
    2592                 :            :               {
    2593                 :        396 :                 genop2 = find_or_generate_expression (block, genop2, stmts);
    2594                 :        396 :                 if (!genop2)
    2595                 :            :                   return NULL_TREE;
    2596                 :            :               }
    2597                 :            :           }
    2598                 :      37497 :         if (genop3)
    2599                 :            :           {
    2600                 :      37497 :             tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
    2601                 :            :             /* We can't always put a size in units of the element alignment
    2602                 :            :                here as the element alignment may be not visible.  See
    2603                 :            :                PR43783.  Simply drop the element size for constant
    2604                 :            :                sizes.  */
    2605                 :      37497 :             if (TREE_CODE (genop3) == INTEGER_CST
    2606                 :      37442 :                 && TREE_CODE (TYPE_SIZE_UNIT (elmt_type)) == INTEGER_CST
    2607                 :      74935 :                 && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)),
    2608                 :      37438 :                              (wi::to_offset (genop3)
    2609                 :     112298 :                               * vn_ref_op_align_unit (currop))))
    2610                 :            :               genop3 = NULL_TREE;
    2611                 :            :             else
    2612                 :            :               {
    2613                 :         75 :                 genop3 = find_or_generate_expression (block, genop3, stmts);
    2614                 :         75 :                 if (!genop3)
    2615                 :            :                   return NULL_TREE;
    2616                 :            :               }
    2617                 :            :           }
    2618                 :      37497 :         return build4 (currop->opcode, currop->type, genop0, genop1,
    2619                 :      37497 :                        genop2, genop3);
    2620                 :            :       }
    2621                 :     192108 :     case COMPONENT_REF:
    2622                 :     192108 :       {
    2623                 :     192108 :         tree op0;
    2624                 :     192108 :         tree op1;
    2625                 :     192108 :         tree genop2 = currop->op1;
    2626                 :     192108 :         op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
    2627                 :     192108 :         if (!op0)
    2628                 :            :           return NULL_TREE;
    2629                 :            :         /* op1 should be a FIELD_DECL, which are represented by themselves.  */
    2630                 :     191647 :         op1 = currop->op0;
    2631                 :     191647 :         if (genop2)
    2632                 :            :           {
    2633                 :          0 :             genop2 = find_or_generate_expression (block, genop2, stmts);
    2634                 :          0 :             if (!genop2)
    2635                 :            :               return NULL_TREE;
    2636                 :            :           }
    2637                 :     191647 :         return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2);
    2638                 :            :       }
    2639                 :            : 
    2640                 :      95519 :     case SSA_NAME:
    2641                 :      95519 :       {
    2642                 :      95519 :         genop = find_or_generate_expression (block, currop->op0, stmts);
    2643                 :      95519 :         return genop;
    2644                 :            :       }
    2645                 :        710 :     case STRING_CST:
    2646                 :        710 :     case INTEGER_CST:
    2647                 :        710 :     case COMPLEX_CST:
    2648                 :        710 :     case VECTOR_CST:
    2649                 :        710 :     case REAL_CST:
    2650                 :        710 :     case CONSTRUCTOR:
    2651                 :        710 :     case VAR_DECL:
    2652                 :        710 :     case PARM_DECL:
    2653                 :        710 :     case CONST_DECL:
    2654                 :        710 :     case RESULT_DECL:
    2655                 :        710 :     case FUNCTION_DECL:
    2656                 :        710 :       return currop->op0;
    2657                 :            : 
    2658                 :          0 :     default:
    2659                 :          0 :       gcc_unreachable ();
    2660                 :            :     }
    2661                 :            : }
    2662                 :            : 
    2663                 :            : /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
    2664                 :            :    COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
    2665                 :            :    trying to rename aggregates into ssa form directly, which is a no no.
    2666                 :            : 
    2667                 :            :    Thus, this routine doesn't create temporaries, it just builds a
    2668                 :            :    single access expression for the array, calling
    2669                 :            :    find_or_generate_expression to build the innermost pieces.
    2670                 :            : 
    2671                 :            :    This function is a subroutine of create_expression_by_pieces, and
    2672                 :            :    should not be called on it's own unless you really know what you
    2673                 :            :    are doing.  */
    2674                 :            : 
    2675                 :            : static tree
    2676                 :     260940 : create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
    2677                 :            :                                 gimple_seq *stmts)
    2678                 :            : {
    2679                 :     260940 :   unsigned int op = 0;
    2680                 :     260940 :   return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
    2681                 :            : }
    2682                 :            : 
    2683                 :            : /* Find a simple leader for an expression, or generate one using
    2684                 :            :    create_expression_by_pieces from a NARY expression for the value.
    2685                 :            :    BLOCK is the basic_block we are looking for leaders in.
    2686                 :            :    OP is the tree expression to find a leader for or generate.
    2687                 :            :    Returns the leader or NULL_TREE on failure.  */
    2688                 :            : 
    2689                 :            : static tree
    2690                 :    1361350 : find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
    2691                 :            : {
    2692                 :    1361350 :   pre_expr expr = get_or_alloc_expr_for (op);
    2693                 :    1361350 :   unsigned int lookfor = get_expr_value_id (expr);
    2694                 :    1361350 :   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
    2695                 :    1361350 :   if (leader)
    2696                 :            :     {
    2697                 :    1276580 :       if (leader->kind == NAME)
    2698                 :     903128 :         return PRE_EXPR_NAME (leader);
    2699                 :     373450 :       else if (leader->kind == CONSTANT)
    2700                 :     373450 :         return PRE_EXPR_CONSTANT (leader);
    2701                 :            : 
    2702                 :            :       /* Defer.  */
    2703                 :            :       return NULL_TREE;
    2704                 :            :     }
    2705                 :            : 
    2706                 :            :   /* It must be a complex expression, so generate it recursively.  Note
    2707                 :            :      that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
    2708                 :            :      where the insert algorithm fails to insert a required expression.  */
    2709                 :      84768 :   bitmap exprset = value_expressions[lookfor];
    2710                 :      84768 :   bitmap_iterator bi;
    2711                 :      84768 :   unsigned int i;
    2712                 :     132343 :   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
    2713                 :            :     {
    2714                 :     118012 :       pre_expr temp = expression_for_id (i);
    2715                 :            :       /* We cannot insert random REFERENCE expressions at arbitrary
    2716                 :            :          places.  We can insert NARYs which eventually re-materializes
    2717                 :            :          its operand values.  */
    2718                 :     118012 :       if (temp->kind == NARY)
    2719                 :      70437 :         return create_expression_by_pieces (block, temp, stmts,
    2720                 :      70437 :                                             get_expr_type (expr));
    2721                 :            :     }
    2722                 :            : 
    2723                 :            :   /* Defer.  */
    2724                 :            :   return NULL_TREE;
    2725                 :            : }
    2726                 :            : 
    2727                 :            : /* Create an expression in pieces, so that we can handle very complex
    2728                 :            :    expressions that may be ANTIC, but not necessary GIMPLE.
    2729                 :            :    BLOCK is the basic block the expression will be inserted into,
    2730                 :            :    EXPR is the expression to insert (in value form)
    2731                 :            :    STMTS is a statement list to append the necessary insertions into.
    2732                 :            : 
    2733                 :            :    This function will die if we hit some value that shouldn't be
    2734                 :            :    ANTIC but is (IE there is no leader for it, or its components).
    2735                 :            :    The function returns NULL_TREE in case a different antic expression
    2736                 :            :    has to be inserted first.
    2737                 :            :    This function may also generate expressions that are themselves
    2738                 :            :    partially or fully redundant.  Those that are will be either made
    2739                 :            :    fully redundant during the next iteration of insert (for partially
    2740                 :            :    redundant ones), or eliminated by eliminate (for fully redundant
    2741                 :            :    ones).  */
    2742                 :            : 
    2743                 :            : static tree
    2744                 :    3195960 : create_expression_by_pieces (basic_block block, pre_expr expr,
    2745                 :            :                              gimple_seq *stmts, tree type)
    2746                 :            : {
    2747                 :    3195960 :   tree name;
    2748                 :    3195960 :   tree folded;
    2749                 :    3195960 :   gimple_seq forced_stmts = NULL;
    2750                 :    3195960 :   unsigned int value_id;
    2751                 :    3195960 :   gimple_stmt_iterator gsi;
    2752                 :    3195960 :   tree exprtype = type ? type : get_expr_type (expr);
    2753                 :    3195960 :   pre_expr nameexpr;
    2754                 :    3195960 :   gassign *newstmt;
    2755                 :            : 
    2756                 :    3195960 :   switch (expr->kind)
    2757                 :            :     {
    2758                 :            :     /* We may hit the NAME/CONSTANT case if we have to convert types
    2759                 :            :        that value numbering saw through.  */
    2760                 :    1240190 :     case NAME:
    2761                 :    1240190 :       folded = PRE_EXPR_NAME (expr);
    2762                 :    1240190 :       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded))
    2763                 :            :         return NULL_TREE;
    2764                 :    1240180 :       if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
    2765                 :            :         return folded;
    2766                 :            :       break;
    2767                 :     977729 :     case CONSTANT:
    2768                 :     977729 :       { 
    2769                 :     977729 :         folded = PRE_EXPR_CONSTANT (expr);
    2770                 :     977729 :         tree tem = fold_convert (exprtype, folded);
    2771                 :     977729 :         if (is_gimple_min_invariant (tem))
    2772                 :            :           return tem;
    2773                 :            :         break;
    2774                 :            :       }
    2775                 :     262143 :     case REFERENCE:
    2776                 :     262143 :       if (PRE_EXPR_REFERENCE (expr)->operands[0].opcode == CALL_EXPR)
    2777                 :            :         {
    2778                 :       1203 :           vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
    2779                 :       1203 :           unsigned int operand = 1;
    2780                 :       1203 :           vn_reference_op_t currop = &ref->operands[0];
    2781                 :       1203 :           tree sc = NULL_TREE;
    2782                 :       1203 :           tree fn  = find_or_generate_expression (block, currop->op0, stmts);
    2783                 :       1203 :           if (!fn)
    2784                 :          7 :             return NULL_TREE;
    2785                 :       1203 :           if (currop->op1)
    2786                 :            :             {
    2787                 :          0 :               sc = find_or_generate_expression (block, currop->op1, stmts);
    2788                 :          0 :               if (!sc)
    2789                 :            :                 return NULL_TREE;
    2790                 :            :             }
    2791                 :       3602 :           auto_vec<tree> args (ref->operands.length () - 1);
    2792                 :       5338 :           while (operand < ref->operands.length ())
    2793                 :            :             {
    2794                 :       1473 :               tree arg = create_component_ref_by_pieces_1 (block, ref,
    2795                 :       1473 :                                                            &operand, stmts);
    2796                 :       1473 :               if (!arg)
    2797                 :          7 :                 return NULL_TREE;
    2798                 :       1466 :               args.quick_push (arg);
    2799                 :            :             }
    2800                 :       1196 :           gcall *call = gimple_build_call_vec (fn, args);
    2801                 :       1196 :           gimple_set_location (call, expr->loc);
    2802                 :       1196 :           gimple_call_set_fntype (call, currop->type);
    2803                 :       1196 :           if (sc)
    2804                 :          0 :             gimple_call_set_chain (call, sc);
    2805                 :       1196 :           tree forcedname = make_ssa_name (TREE_TYPE (currop->type));
    2806                 :       1196 :           gimple_call_set_lhs (call, forcedname);
    2807                 :            :           /* There's no CCP pass after PRE which would re-compute alignment
    2808                 :            :              information so make sure we re-materialize this here.  */
    2809                 :       1196 :           if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED)
    2810                 :          0 :               && args.length () - 2 <= 1
    2811                 :          0 :               && tree_fits_uhwi_p (args[1])
    2812                 :       1196 :               && (args.length () != 3 || tree_fits_uhwi_p (args[2])))
    2813                 :            :             {
    2814                 :          0 :               unsigned HOST_WIDE_INT halign = tree_to_uhwi (args[1]);
    2815                 :          0 :               unsigned HOST_WIDE_INT hmisalign
    2816                 :          0 :                 = args.length () == 3 ? tree_to_uhwi (args[2]) : 0;
    2817                 :          0 :               if ((halign & (halign - 1)) == 0
    2818                 :          0 :                   && (hmisalign & ~(halign - 1)) == 0
    2819                 :          0 :                   && (unsigned int)halign != 0)
    2820                 :          0 :                 set_ptr_info_alignment (get_ptr_info (forcedname),
    2821                 :            :                                         halign, hmisalign);
    2822                 :            :             }
    2823                 :       1196 :           gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block));
    2824                 :       1196 :           gimple_seq_add_stmt_without_update (&forced_stmts, call);
    2825                 :       1196 :           folded = forcedname;
    2826                 :            :         }
    2827                 :            :       else
    2828                 :            :         {
    2829                 :     260940 :           folded = create_component_ref_by_pieces (block,
    2830                 :            :                                                    PRE_EXPR_REFERENCE (expr),
    2831                 :            :                                                    stmts);
    2832                 :     260940 :           if (!folded)
    2833                 :            :             return NULL_TREE;
    2834                 :     260735 :           name = make_temp_ssa_name (exprtype, NULL, "pretmp");
    2835                 :     260735 :           newstmt = gimple_build_assign (name, folded);
    2836                 :     260735 :           gimple_set_location (newstmt, expr->loc);
    2837                 :     260735 :           gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
    2838                 :     260735 :           gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block));
    2839                 :     260735 :           folded = name;
    2840                 :            :         }
    2841                 :            :       break;
    2842                 :     715895 :     case NARY:
    2843                 :     715895 :       {
    2844                 :     715895 :         vn_nary_op_t nary = PRE_EXPR_NARY (expr);
    2845                 :     715895 :         tree *genop = XALLOCAVEC (tree, nary->length);
    2846                 :     715895 :         unsigned i;
    2847                 :    1895510 :         for (i = 0; i < nary->length; ++i)
    2848                 :            :           {
    2849                 :    1226650 :             genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
    2850                 :    1226650 :             if (!genop[i])
    2851                 :            :               return NULL_TREE;
    2852                 :            :             /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR.  It
    2853                 :            :                may have conversions stripped.  */
    2854                 :    1179620 :             if (nary->opcode == POINTER_PLUS_EXPR)
    2855                 :            :               {
    2856                 :     182978 :                 if (i == 0)
    2857                 :      91918 :                   genop[i] = gimple_convert (&forced_stmts,
    2858                 :            :                                              nary->type, genop[i]);
    2859                 :      91060 :                 else if (i == 1)
    2860                 :      91060 :                   genop[i] = gimple_convert (&forced_stmts,
    2861                 :            :                                              sizetype, genop[i]);
    2862                 :            :               }
    2863                 :            :             else
    2864                 :     996640 :               genop[i] = gimple_convert (&forced_stmts,
    2865                 :     996640 :                                          TREE_TYPE (nary->op[i]), genop[i]);
    2866                 :            :           }
    2867                 :     668859 :         if (nary->opcode == CONSTRUCTOR)
    2868                 :            :           {
    2869                 :          8 :             vec<constructor_elt, va_gc> *elts = NULL;
    2870                 :         24 :             for (i = 0; i < nary->length; ++i)
    2871                 :         16 :               CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
    2872                 :          8 :             folded = build_constructor (nary->type, elts);
    2873                 :          8 :             name = make_temp_ssa_name (exprtype, NULL, "pretmp");
    2874                 :          8 :             newstmt = gimple_build_assign (name, folded);
    2875                 :          8 :             gimple_set_location (newstmt, expr->loc);
    2876                 :          8 :             gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
    2877                 :          8 :             folded = name;
    2878                 :            :           }
    2879                 :            :         else
    2880                 :            :           {
    2881                 :     668851 :             switch (nary->length)
    2882                 :            :               {
    2883                 :     163374 :               case 1:
    2884                 :     163374 :                 folded = gimple_build (&forced_stmts, expr->loc,
    2885                 :            :                                        nary->opcode, nary->type, genop[0]);
    2886                 :     163374 :                 break;
    2887                 :     505259 :               case 2:
    2888                 :     505259 :                 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
    2889                 :            :                                        nary->type, genop[0], genop[1]);
    2890                 :     505259 :                 break;
    2891                 :        218 :               case 3:
    2892                 :        218 :                 folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
    2893                 :            :                                        nary->type, genop[0], genop[1],
    2894                 :            :                                        genop[2]);
    2895                 :        218 :                 break;
    2896                 :          0 :               default:
    2897                 :          0 :                 gcc_unreachable ();
    2898                 :            :               }
    2899                 :            :           }
    2900                 :            :       }
    2901                 :            :       break;
    2902                 :          0 :     default:
    2903                 :          0 :       gcc_unreachable ();
    2904                 :            :     }
    2905                 :            : 
    2906                 :     938613 :   folded = gimple_convert (&forced_stmts, exprtype, folded);
    2907                 :            : 
    2908                 :            :   /* If there is nothing to insert, return the simplified result.  */
    2909                 :     938613 :   if (gimple_seq_empty_p (forced_stmts))
    2910                 :            :     return folded;
    2911                 :            :   /* If we simplified to a constant return it and discard eventually
    2912                 :            :      built stmts.  */
    2913                 :     930632 :   if (is_gimple_min_invariant (folded))
    2914                 :            :     {
    2915                 :          0 :       gimple_seq_discard (forced_stmts);
    2916                 :          0 :       return folded;
    2917                 :            :     }
    2918                 :            :   /* Likewise if we simplified to sth not queued for insertion.  */
    2919                 :     930632 :   bool found = false;
    2920                 :    1861260 :   gsi = gsi_last (forced_stmts);
    2921                 :     930632 :   for (; !gsi_end_p (gsi); gsi_prev (&gsi))
    2922                 :            :     {
    2923                 :     930632 :       gimple *stmt = gsi_stmt (gsi);
    2924                 :     930632 :       tree forcedname = gimple_get_lhs (stmt);
    2925                 :     930632 :       if (forcedname == folded)
    2926                 :            :         {
    2927                 :            :           found = true;
    2928                 :            :           break;
    2929                 :            :         }
    2930                 :            :     }
    2931                 :     930632 :   if (! found)
    2932                 :            :     {
    2933                 :          0 :       gimple_seq_discard (forced_stmts);
    2934                 :          0 :       return folded;
    2935                 :            :     }
    2936                 :     930632 :   gcc_assert (TREE_CODE (folded) == SSA_NAME);
    2937                 :            : 
    2938                 :            :   /* If we have any intermediate expressions to the value sets, add them
    2939                 :            :      to the value sets and chain them in the instruction stream.  */
    2940                 :     930632 :   if (forced_stmts)
    2941                 :            :     {
    2942                 :     930632 :       gsi = gsi_start (forced_stmts);
    2943                 :    1861440 :       for (; !gsi_end_p (gsi); gsi_next (&gsi))
    2944                 :            :         {
    2945                 :     930813 :           gimple *stmt = gsi_stmt (gsi);
    2946                 :     930813 :           tree forcedname = gimple_get_lhs (stmt);
    2947                 :     930813 :           pre_expr nameexpr;
    2948                 :            : 
    2949                 :     930813 :           if (forcedname != folded)
    2950                 :            :             {
    2951                 :        181 :               VN_INFO (forcedname)->valnum = forcedname;
    2952                 :        181 :               VN_INFO (forcedname)->value_id = get_next_value_id ();
    2953                 :        181 :               nameexpr = get_or_alloc_expr_for_name (forcedname);
    2954                 :        181 :               add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
    2955                 :        181 :               bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
    2956                 :        181 :               bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
    2957                 :            :             }
    2958                 :            : 
    2959                 :     930813 :           bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
    2960                 :            :         }
    2961                 :     930632 :       gimple_seq_add_seq (stmts, forced_stmts);
    2962                 :            :     }
    2963                 :            : 
    2964                 :     930632 :   name = folded;
    2965                 :            : 
    2966                 :            :   /* Fold the last statement.  */
    2967                 :     930632 :   gsi = gsi_last (*stmts);
    2968                 :     930632 :   if (fold_stmt_inplace (&gsi))
    2969                 :     147029 :     update_stmt (gsi_stmt (gsi));
    2970                 :            : 
    2971                 :            :   /* Add a value number to the temporary.
    2972                 :            :      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
    2973                 :            :      we are creating the expression by pieces, and this particular piece of
    2974                 :            :      the expression may have been represented.  There is no harm in replacing
    2975                 :            :      here.  */
    2976                 :     930632 :   value_id = get_expr_value_id (expr);
    2977                 :     930632 :   VN_INFO (name)->value_id = value_id;
    2978                 :     930632 :   VN_INFO (name)->valnum = vn_valnum_from_value_id (value_id);
    2979                 :     930632 :   if (VN_INFO (name)->valnum == NULL_TREE)
    2980                 :     370598 :     VN_INFO (name)->valnum = name;
    2981                 :     930632 :   gcc_assert (VN_INFO (name)->valnum != NULL_TREE);
    2982                 :     930632 :   nameexpr = get_or_alloc_expr_for_name (name);
    2983                 :     930632 :   add_to_value (value_id, nameexpr);
    2984                 :     930632 :   if (NEW_SETS (block))
    2985                 :     930632 :     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
    2986                 :     930632 :   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
    2987                 :            : 
    2988                 :     930632 :   pre_stats.insertions++;
    2989                 :     930632 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2990                 :            :     {
    2991                 :        123 :       fprintf (dump_file, "Inserted ");
    2992                 :        246 :       print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)), 0);
    2993                 :        123 :       fprintf (dump_file, " in predecessor %d (%04d)\n",
    2994                 :            :                block->index, value_id);
    2995                 :            :     }
    2996                 :            : 
    2997                 :            :   return name;
    2998                 :            : }
    2999                 :            : 
    3000                 :            : 
    3001                 :            : /* Insert the to-be-made-available values of expression EXPRNUM for each
    3002                 :            :    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
    3003                 :            :    merge the result with a phi node, given the same value number as
    3004                 :            :    NODE.  Return true if we have inserted new stuff.  */
    3005                 :            : 
    3006                 :            : static bool
    3007                 :    1454900 : insert_into_preds_of_block (basic_block block, unsigned int exprnum,
    3008                 :            :                             vec<pre_expr> avail)
    3009                 :            : {
    3010                 :    1454900 :   pre_expr expr = expression_for_id (exprnum);
    3011                 :    1454900 :   pre_expr newphi;
    3012                 :    1454900 :   unsigned int val = get_expr_value_id (expr);
    3013                 :    1454900 :   edge pred;
    3014                 :    1454900 :   bool insertions = false;
    3015                 :    1454900 :   bool nophi = false;
    3016                 :    1454900 :   basic_block bprime;
    3017                 :    1454900 :   pre_expr eprime;
    3018                 :    1454900 :   edge_iterator ei;
    3019                 :    1454900 :   tree type = get_expr_type (expr);
    3020                 :    1454900 :   tree temp;
    3021                 :    1454900 :   gphi *phi;
    3022                 :            : 
    3023                 :            :   /* Make sure we aren't creating an induction variable.  */
    3024                 :    1454900 :   if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2)
    3025                 :            :     {
    3026                 :    1207520 :       bool firstinsideloop = false;
    3027                 :    1207520 :       bool secondinsideloop = false;
    3028                 :    2415040 :       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
    3029                 :    1207520 :                                                EDGE_PRED (block, 0)->src);
    3030                 :    3622570 :       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
    3031                 :    1207520 :                                                 EDGE_PRED (block, 1)->src);
    3032                 :            :       /* Induction variables only have one edge inside the loop.  */
    3033                 :    1207520 :       if ((firstinsideloop ^ secondinsideloop)
    3034                 :    1161040 :           && expr->kind != REFERENCE)
    3035                 :            :         {
    3036                 :    1114960 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3037                 :        105 :             fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
    3038                 :            :           nophi = true;
    3039                 :            :         }
    3040                 :            :     }
    3041                 :            : 
    3042                 :            :   /* Make the necessary insertions.  */
    3043                 :    4475950 :   FOR_EACH_EDGE (pred, ei, block->preds)
    3044                 :            :     {
    3045                 :    3021050 :       gimple_seq stmts = NULL;
    3046                 :    3021050 :       tree builtexpr;
    3047                 :    3021050 :       bprime = pred->src;
    3048                 :    3021050 :       eprime = avail[pred->dest_idx];
    3049                 :    3021050 :       builtexpr = create_expression_by_pieces (bprime, eprime,
    3050                 :            :                                                &stmts, type);
    3051                 :    3021050 :       gcc_assert (!(pred->flags & EDGE_ABNORMAL));
    3052                 :    3021050 :       if (!gimple_seq_empty_p (stmts))
    3053                 :            :         {
    3054                 :     790082 :           basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
    3055                 :     790082 :           gcc_assert (! new_bb);
    3056                 :            :           insertions = true;
    3057                 :            :         }
    3058                 :    3021050 :       if (!builtexpr)
    3059                 :            :         {
    3060                 :            :           /* We cannot insert a PHI node if we failed to insert
    3061                 :            :              on one edge.  */
    3062                 :      12960 :           nophi = true;
    3063                 :      12960 :           continue;
    3064                 :            :         }
    3065                 :    3008090 :       if (is_gimple_min_invariant (builtexpr))
    3066                 :     977729 :         avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr);
    3067                 :            :       else
    3068                 :    2030360 :         avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
    3069                 :            :     }
    3070                 :            :   /* If we didn't want a phi node, and we made insertions, we still have
    3071                 :            :      inserted new stuff, and thus return true.  If we didn't want a phi node,
    3072                 :            :      and didn't make insertions, we haven't added anything new, so return
    3073                 :            :      false.  */
    3074                 :    1454900 :   if (nophi && insertions)
    3075                 :            :     return true;
    3076                 :     997202 :   else if (nophi && !insertions)
    3077                 :            :     return false;
    3078                 :            : 
    3079                 :            :   /* Now build a phi for the new variable.  */
    3080                 :     336269 :   temp = make_temp_ssa_name (type, NULL, "prephitmp");
    3081                 :     336269 :   phi = create_phi_node (temp, block);
    3082                 :            : 
    3083                 :     336269 :   VN_INFO (temp)->value_id = val;
    3084                 :     336269 :   VN_INFO (temp)->valnum = vn_valnum_from_value_id (val);
    3085                 :     336269 :   if (VN_INFO (temp)->valnum == NULL_TREE)
    3086                 :      87286 :     VN_INFO (temp)->valnum = temp;
    3087                 :     336269 :   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
    3088                 :    1113510 :   FOR_EACH_EDGE (pred, ei, block->preds)
    3089                 :            :     {
    3090                 :     777244 :       pre_expr ae = avail[pred->dest_idx];
    3091                 :     777244 :       gcc_assert (get_expr_type (ae) == type
    3092                 :            :                   || useless_type_conversion_p (type, get_expr_type (ae)));
    3093                 :     777244 :       if (ae->kind == CONSTANT)
    3094                 :      91196 :         add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)),
    3095                 :            :                      pred, UNKNOWN_LOCATION);
    3096                 :            :       else
    3097                 :     686048 :         add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
    3098                 :            :     }
    3099                 :            : 
    3100                 :     336269 :   newphi = get_or_alloc_expr_for_name (temp);
    3101                 :     336269 :   add_to_value (val, newphi);
    3102                 :            : 
    3103                 :            :   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
    3104                 :            :      this insertion, since we test for the existence of this value in PHI_GEN
    3105                 :            :      before proceeding with the partial redundancy checks in insert_aux.
    3106                 :            : 
    3107                 :            :      The value may exist in AVAIL_OUT, in particular, it could be represented
    3108                 :            :      by the expression we are trying to eliminate, in which case we want the
    3109                 :            :      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
    3110                 :            :      inserted there.
    3111                 :            : 
    3112                 :            :      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
    3113                 :            :      this block, because if it did, it would have existed in our dominator's
    3114                 :            :      AVAIL_OUT, and would have been skipped due to the full redundancy check.
    3115                 :            :   */
    3116                 :            : 
    3117                 :     336269 :   bitmap_insert_into_set (PHI_GEN (block), newphi);
    3118                 :     336269 :   bitmap_value_replace_in_set (AVAIL_OUT (block),
    3119                 :            :                                newphi);
    3120                 :     336269 :   bitmap_insert_into_set (NEW_SETS (block),
    3121                 :            :                           newphi);
    3122                 :            : 
    3123                 :            :   /* If we insert a PHI node for a conversion of another PHI node
    3124                 :            :      in the same basic-block try to preserve range information.
    3125                 :            :      This is important so that followup loop passes receive optimal
    3126                 :            :      number of iteration analysis results.  See PR61743.  */
    3127                 :     336269 :   if (expr->kind == NARY
    3128                 :     115947 :       && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)
    3129                 :      38289 :       && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME
    3130                 :      38240 :       && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block
    3131                 :      30828 :       && INTEGRAL_TYPE_P (type)
    3132                 :      30434 :       && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))
    3133                 :      58996 :       && (TYPE_PRECISION (type)
    3134                 :      29498 :           >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0])))
    3135                 :     362211 :       && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
    3136                 :            :     {
    3137                 :      12870 :       wide_int min, max;
    3138                 :      12870 :       if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE
    3139                 :      12467 :           && !wi::neg_p (min, SIGNED)
    3140                 :      23414 :           && !wi::neg_p (max, SIGNED))
    3141                 :            :         /* Just handle extension and sign-changes of all-positive ranges.  */
    3142                 :      30744 :         set_range_info (temp,
    3143                 :      10248 :                         SSA_NAME_RANGE_TYPE (expr->u.nary->op[0]),
    3144                 :      10248 :                         wide_int_storage::from (min, TYPE_PRECISION (type),
    3145                 :      10248 :                                                 TYPE_SIGN (type)),
    3146                 :      10248 :                         wide_int_storage::from (max, TYPE_PRECISION (type),
    3147                 :      20496 :                                                 TYPE_SIGN (type)));
    3148                 :            :     }
    3149                 :            : 
    3150                 :     336269 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3151                 :            :     {
    3152                 :         38 :       fprintf (dump_file, "Created phi ");
    3153                 :         38 :       print_gimple_stmt (dump_file, phi, 0);
    3154                 :         38 :       fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
    3155                 :            :     }
    3156                 :     336269 :   pre_stats.phis++;
    3157                 :     336269 :   return true;
    3158                 :            : }
    3159                 :            : 
    3160                 :            : 
    3161                 :            : 
    3162                 :            : /* Perform insertion of partially redundant or hoistable values.
    3163                 :            :    For BLOCK, do the following:
    3164                 :            :    1.  Propagate the NEW_SETS of the dominator into the current block.
    3165                 :            :    If the block has multiple predecessors,
    3166                 :            :        2a. Iterate over the ANTIC expressions for the block to see if
    3167                 :            :            any of them are partially redundant.
    3168                 :            :        2b. If so, insert them into the necessary predecessors to make
    3169                 :            :            the expression fully redundant.
    3170                 :            :        2c. Insert a new PHI merging the values of the predecessors.
    3171                 :            :        2d. Insert the new PHI, and the new expressions, into the
    3172                 :            :            NEW_SETS set.
    3173                 :            :    If the block has multiple successors,
    3174                 :            :        3a. Iterate over the ANTIC values for the block to see if
    3175                 :            :            any of them are good candidates for hoisting.
    3176                 :            :        3b. If so, insert expressions computing the values in BLOCK,
    3177                 :            :            and add the new expressions into the NEW_SETS set.
    3178                 :            :    4. Recursively call ourselves on the dominator children of BLOCK.
    3179                 :            : 
    3180                 :            :    Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
    3181                 :            :    do_pre_regular_insertion and do_partial_insertion.  3a and 3b are
    3182                 :            :    done in do_hoist_insertion.
    3183                 :            : */
    3184                 :            : 
    3185                 :            : static bool
    3186                 :    3035470 : do_pre_regular_insertion (basic_block block, basic_block dom)
    3187                 :            : {
    3188                 :    3035470 :   bool new_stuff = false;
    3189                 :    3035470 :   vec<pre_expr> exprs;
    3190                 :    3035470 :   pre_expr expr;
    3191                 :    3035470 :   auto_vec<pre_expr> avail;
    3192                 :    3035470 :   int i;
    3193                 :            : 
    3194                 :    3035470 :   exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
    3195                 :    3035470 :   avail.safe_grow (EDGE_COUNT (block->preds));
    3196                 :            : 
    3197                 :   24632700 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    3198                 :            :     {
    3199                 :   21597200 :       if (expr->kind == NARY
    3200                 :   21597200 :           || expr->kind == REFERENCE)
    3201                 :            :         {
    3202                 :   12069600 :           unsigned int val;
    3203                 :   12069600 :           bool by_some = false;
    3204                 :   12069600 :           bool cant_insert = false;
    3205                 :   12069600 :           bool all_same = true;
    3206                 :   12069600 :           pre_expr first_s = NULL;
    3207                 :   12069600 :           edge pred;
    3208                 :   12069600 :           basic_block bprime;
    3209                 :   12069600 :           pre_expr eprime = NULL;
    3210                 :   12069600 :           edge_iterator ei;
    3211                 :   12069600 :           pre_expr edoubleprime = NULL;
    3212                 :   12069600 :           bool do_insertion = false;
    3213                 :            : 
    3214                 :   12069600 :           val = get_expr_value_id (expr);
    3215                 :   12069600 :           if (bitmap_set_contains_value (PHI_GEN (block), val))
    3216                 :    1399630 :             continue;
    3217                 :   11589600 :           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
    3218                 :            :             {
    3219                 :     919688 :               if (dump_file && (dump_flags & TDF_DETAILS))
    3220                 :            :                 {
    3221                 :        143 :                   fprintf (dump_file, "Found fully redundant value: ");
    3222                 :        143 :                   print_pre_expr (dump_file, expr);
    3223                 :        143 :                   fprintf (dump_file, "\n");
    3224                 :            :                 }
    3225                 :     919688 :               continue;
    3226                 :            :             }
    3227                 :            : 
    3228                 :   35230900 :           FOR_EACH_EDGE (pred, ei, block->preds)
    3229                 :            :             {
    3230                 :   24623600 :               unsigned int vprime;
    3231                 :            : 
    3232                 :            :               /* We should never run insertion for the exit block
    3233                 :            :                  and so not come across fake pred edges.  */
    3234                 :   24623600 :               gcc_assert (!(pred->flags & EDGE_FAKE));
    3235                 :   24623600 :               bprime = pred->src;
    3236                 :            :               /* We are looking at ANTIC_OUT of bprime.  */
    3237                 :   24623600 :               eprime = phi_translate (NULL, expr, ANTIC_IN (block), NULL, pred);
    3238                 :            : 
    3239                 :            :               /* eprime will generally only be NULL if the
    3240                 :            :                  value of the expression, translated
    3241                 :            :                  through the PHI for this predecessor, is
    3242                 :            :                  undefined.  If that is the case, we can't
    3243                 :            :                  make the expression fully redundant,
    3244                 :            :                  because its value is undefined along a
    3245                 :            :                  predecessor path.  We can thus break out
    3246                 :            :                  early because it doesn't matter what the
    3247                 :            :                  rest of the results are.  */
    3248                 :   24623600 :               if (eprime == NULL)
    3249                 :            :                 {
    3250                 :      62587 :                   avail[pred->dest_idx] = NULL;
    3251                 :      62587 :                   cant_insert = true;
    3252                 :      62587 :                   break;
    3253                 :            :                 }
    3254                 :            : 
    3255                 :   24561000 :               vprime = get_expr_value_id (eprime);
    3256                 :   24561000 :               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
    3257                 :            :                                                  vprime);
    3258                 :   24561000 :               if (edoubleprime == NULL)
    3259                 :            :                 {
    3260                 :   22126700 :                   avail[pred->dest_idx] = eprime;
    3261                 :   22126700 :                   all_same = false;
    3262                 :            :                 }
    3263                 :            :               else
    3264                 :            :                 {
    3265                 :    2434320 :                   avail[pred->dest_idx] = edoubleprime;
    3266                 :    2434320 :                   by_some = true;
    3267                 :            :                   /* We want to perform insertions to remove a redundancy on
    3268                 :            :                      a path in the CFG we want to optimize for speed.  */
    3269                 :    2434320 :                   if (optimize_edge_for_speed_p (pred))
    3270                 :    2195420 :                     do_insertion = true;
    3271                 :    2434320 :                   if (first_s == NULL)
    3272                 :            :                     first_s = edoubleprime;
    3273                 :     789226 :                   else if (!pre_expr_d::equal (first_s, edoubleprime))
    3274                 :     752765 :                     all_same = false;
    3275                 :            :                 }
    3276                 :            :             }
    3277                 :            :           /* If we can insert it, it's not the same value
    3278                 :            :              already existing along every predecessor, and
    3279                 :            :              it's defined by some predecessor, it is
    3280                 :            :              partially redundant.  */
    3281                 :   10669900 :           if (!cant_insert && !all_same && by_some)
    3282                 :            :             {
    3283                 :    1643810 :               if (!do_insertion)
    3284                 :            :                 {
    3285                 :     194255 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3286                 :            :                     {
    3287                 :          0 :                       fprintf (dump_file, "Skipping partial redundancy for "
    3288                 :            :                                "expression ");
    3289                 :          0 :                       print_pre_expr (dump_file, expr);
    3290                 :          0 :                       fprintf (dump_file, " (%04d), no redundancy on to be "
    3291                 :            :                                "optimized for speed edge\n", val);
    3292                 :            :                     }
    3293                 :            :                 }
    3294                 :    1449550 :               else if (dbg_cnt (treepre_insert))
    3295                 :            :                 {
    3296                 :    1449550 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3297                 :            :                     {
    3298                 :        143 :                       fprintf (dump_file, "Found partial redundancy for "
    3299                 :            :                                "expression ");
    3300                 :        143 :                       print_pre_expr (dump_file, expr);
    3301                 :        143 :                       fprintf (dump_file, " (%04d)\n",
    3302                 :            :                                get_expr_value_id (expr));
    3303                 :            :                     }
    3304                 :    1449550 :                   if (insert_into_preds_of_block (block,
    3305                 :            :                                                   get_expression_id (expr),
    3306                 :            :                                                   avail))
    3307                 :     789544 :                     new_stuff = true;
    3308                 :            :                 }
    3309                 :            :             }
    3310                 :            :           /* If all edges produce the same value and that value is
    3311                 :            :              an invariant, then the PHI has the same value on all
    3312                 :            :              edges.  Note this.  */
    3313                 :    9026130 :           else if (!cant_insert && all_same)
    3314                 :            :             {
    3315                 :       1274 :               gcc_assert (edoubleprime->kind == CONSTANT
    3316                 :            :                           || edoubleprime->kind == NAME);
    3317                 :            : 
    3318                 :       1274 :               tree temp = make_temp_ssa_name (get_expr_type (expr),
    3319                 :            :                                               NULL, "pretmp");
    3320                 :       1274 :               gassign *assign
    3321                 :       1274 :                 = gimple_build_assign (temp,
    3322                 :       1274 :                                        edoubleprime->kind == CONSTANT ?
    3323                 :            :                                        PRE_EXPR_CONSTANT (edoubleprime) :
    3324                 :            :                                        PRE_EXPR_NAME (edoubleprime));
    3325                 :       1274 :               gimple_stmt_iterator gsi = gsi_after_labels (block);
    3326                 :       1274 :               gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
    3327                 :            : 
    3328                 :       1274 :               VN_INFO (temp)->value_id = val;
    3329                 :       1274 :               VN_INFO (temp)->valnum = vn_valnum_from_value_id (val);
    3330                 :       1274 :               if (VN_INFO (temp)->valnum == NULL_TREE)
    3331                 :        144 :                 VN_INFO (temp)->valnum = temp;
    3332                 :       1274 :               bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
    3333                 :       1274 :               pre_expr newe = get_or_alloc_expr_for_name (temp);
    3334                 :       1274 :               add_to_value (val, newe);
    3335                 :       1274 :               bitmap_value_replace_in_set (AVAIL_OUT (block), newe);
    3336                 :       1274 :               bitmap_insert_into_set (NEW_SETS (block), newe);
    3337                 :            :             }
    3338                 :            :         }
    3339                 :            :     }
    3340                 :            : 
    3341                 :    3035470 :   exprs.release ();
    3342                 :    3035470 :   return new_stuff;
    3343                 :            : }
    3344                 :            : 
    3345                 :            : 
    3346                 :            : /* Perform insertion for partially anticipatable expressions.  There
    3347                 :            :    is only one case we will perform insertion for these.  This case is
    3348                 :            :    if the expression is partially anticipatable, and fully available.
    3349                 :            :    In this case, we know that putting it earlier will enable us to
    3350                 :            :    remove the later computation.  */
    3351                 :            : 
    3352                 :            : static bool
    3353                 :     269076 : do_pre_partial_partial_insertion (basic_block block, basic_block dom)
    3354                 :            : {
    3355                 :     269076 :   bool new_stuff = false;
    3356                 :     269076 :   vec<pre_expr> exprs;
    3357                 :     269076 :   pre_expr expr;
    3358                 :     269076 :   auto_vec<pre_expr> avail;
    3359                 :     269076 :   int i;
    3360                 :            : 
    3361                 :     269076 :   exprs = sorted_array_from_bitmap_set (PA_IN (block));
    3362                 :     269076 :   avail.safe_grow (EDGE_COUNT (block->preds));
    3363                 :            : 
    3364                 :    3654360 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    3365                 :            :     {
    3366                 :    3385290 :       if (expr->kind == NARY
    3367                 :    3385290 :           || expr->kind == REFERENCE)
    3368                 :            :         {
    3369                 :    2579820 :           unsigned int val;
    3370                 :    2579820 :           bool by_all = true;
    3371                 :    2579820 :           bool cant_insert = false;
    3372                 :    2579820 :           edge pred;
    3373                 :    2579820 :           basic_block bprime;
    3374                 :    2579820 :           pre_expr eprime = NULL;
    3375                 :    2579820 :           edge_iterator ei;
    3376                 :            : 
    3377                 :    2579820 :           val = get_expr_value_id (expr);
    3378                 :    2579820 :           if (bitmap_set_contains_value (PHI_GEN (block), val))
    3379                 :      50468 :             continue;
    3380                 :    2573520 :           if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
    3381                 :      44165 :             continue;
    3382                 :            : 
    3383                 :    2790370 :           FOR_EACH_EDGE (pred, ei, block->preds)
    3384                 :            :             {
    3385                 :    2784350 :               unsigned int vprime;
    3386                 :    2784350 :               pre_expr edoubleprime;
    3387                 :            : 
    3388                 :            :               /* We should never run insertion for the exit block
    3389                 :            :                  and so not come across fake pred edges.  */
    3390                 :    2784350 :               gcc_assert (!(pred->flags & EDGE_FAKE));
    3391                 :    2784350 :               bprime = pred->src;
    3392                 :    5568700 :               eprime = phi_translate (NULL, expr, ANTIC_IN (block),
    3393                 :    2784350 :                                       PA_IN (block), pred);
    3394                 :            : 
    3395                 :            :               /* eprime will generally only be NULL if the
    3396                 :            :                  value of the expression, translated
    3397                 :            :                  through the PHI for this predecessor, is
    3398                 :            :                  undefined.  If that is the case, we can't
    3399                 :            :                  make the expression fully redundant,
    3400                 :            :                  because its value is undefined along a
    3401                 :            :                  predecessor path.  We can thus break out
    3402                 :            :                  early because it doesn't matter what the
    3403                 :            :                  rest of the results are.  */
    3404                 :    2784350 :               if (eprime == NULL)
    3405                 :            :                 {
    3406                 :       3050 :                   avail[pred->dest_idx] = NULL;
    3407                 :       3050 :                   cant_insert = true;
    3408                 :       3050 :                   break;
    3409                 :            :                 }
    3410                 :            : 
    3411                 :    2781300 :               vprime = get_expr_value_id (eprime);
    3412                 :    2781300 :               edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
    3413                 :    2781300 :               avail[pred->dest_idx] = edoubleprime;
    3414                 :    2781300 :               if (edoubleprime == NULL)
    3415                 :            :                 {
    3416                 :            :                   by_all = false;
    3417                 :            :                   break;
    3418                 :            :                 }
    3419                 :            :             }
    3420                 :            : 
    3421                 :            :           /* If we can insert it, it's not the same value
    3422                 :            :              already existing along every predecessor, and
    3423                 :            :              it's defined by some predecessor, it is
    3424                 :            :              partially redundant.  */
    3425                 :    2529350 :           if (!cant_insert && by_all)
    3426                 :            :             {
    3427                 :       6017 :               edge succ;
    3428                 :       6017 :               bool do_insertion = false;
    3429                 :            : 
    3430                 :            :               /* Insert only if we can remove a later expression on a path
    3431                 :            :                  that we want to optimize for speed.
    3432                 :            :                  The phi node that we will be inserting in BLOCK is not free,
    3433                 :            :                  and inserting it for the sake of !optimize_for_speed successor
    3434                 :            :                  may cause regressions on the speed path.  */
    3435                 :      17729 :               FOR_EACH_EDGE (succ, ei, block->succs)
    3436                 :            :                 {
    3437                 :      11712 :                   if (bitmap_set_contains_value (PA_IN (succ->dest), val)
    3438                 :      11712 :                       || bitmap_set_contains_value (ANTIC_IN (succ->dest), val))
    3439                 :            :                     {
    3440                 :       6167 :                       if (optimize_edge_for_speed_p (succ))
    3441                 :       5725 :                         do_insertion = true;
    3442                 :            :                     }
    3443                 :            :                 }
    3444                 :            : 
    3445                 :       6017 :               if (!do_insertion)
    3446                 :            :                 {
    3447                 :        665 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3448                 :            :                     {
    3449                 :          0 :                       fprintf (dump_file, "Skipping partial partial redundancy "
    3450                 :            :                                "for expression ");
    3451                 :          0 :                       print_pre_expr (dump_file, expr);
    3452                 :          0 :                       fprintf (dump_file, " (%04d), not (partially) anticipated "
    3453                 :            :                                "on any to be optimized for speed edges\n", val);
    3454                 :            :                     }
    3455                 :            :                 }
    3456                 :       5352 :               else if (dbg_cnt (treepre_insert))
    3457                 :            :                 {
    3458                 :       5352 :                   pre_stats.pa_insert++;
    3459                 :       5352 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3460                 :            :                     {
    3461                 :          0 :                       fprintf (dump_file, "Found partial partial redundancy "
    3462                 :            :                                "for expression ");
    3463                 :          0 :                       print_pre_expr (dump_file, expr);
    3464                 :          0 :                       fprintf (dump_file, " (%04d)\n",
    3465                 :            :                                get_expr_value_id (expr));
    3466                 :            :                     }
    3467                 :       5352 :                   if (insert_into_preds_of_block (block,
    3468                 :            :                                                   get_expression_id (expr),
    3469                 :            :                                                   avail))
    3470                 :       4428 :                     new_stuff = true;
    3471                 :            :                 }          
    3472                 :            :             } 
    3473                 :            :         }
    3474                 :            :     }
    3475                 :            : 
    3476                 :     269076 :   exprs.release ();
    3477                 :     269076 :   return new_stuff;
    3478                 :            : }
    3479                 :            : 
    3480                 :            : /* Insert expressions in BLOCK to compute hoistable values up.
    3481                 :            :    Return TRUE if something was inserted, otherwise return FALSE.
    3482                 :            :    The caller has to make sure that BLOCK has at least two successors.  */
    3483                 :            : 
    3484                 :            : static bool
    3485                 :    5415590 : do_hoist_insertion (basic_block block)
    3486                 :            : {
    3487                 :    5415590 :   edge e;
    3488                 :    5415590 :   edge_iterator ei;
    3489                 :    5415590 :   bool new_stuff = false;
    3490                 :    5415590 :   unsigned i;
    3491                 :    5415590 :   gimple_stmt_iterator last;
    3492                 :            : 
    3493                 :            :   /* At least two successors, or else...  */
    3494                 :    5415590 :   gcc_assert (EDGE_COUNT (block->succs) >= 2);
    3495                 :            : 
    3496                 :            :   /* Check that all successors of BLOCK are dominated by block.
    3497                 :            :      We could use dominated_by_p() for this, but actually there is a much
    3498                 :            :      quicker check: any successor that is dominated by BLOCK can't have
    3499                 :            :      more than one predecessor edge.  */
    3500                 :   16311500 :   FOR_EACH_EDGE (e, ei, block->succs)
    3501                 :   10902600 :     if (! single_pred_p (e->dest))
    3502                 :            :       return false;
    3503                 :            : 
    3504                 :            :   /* Determine the insertion point.  If we cannot safely insert before
    3505                 :            :      the last stmt if we'd have to, bail out.  */
    3506                 :    5408850 :   last = gsi_last_bb (block);
    3507                 :    5408850 :   if (!gsi_end_p (last)
    3508                 :    5408500 :       && !is_ctrl_stmt (gsi_stmt (last))
    3509                 :    6192280 :       && stmt_ends_bb_p (gsi_stmt (last)))
    3510                 :            :     return false;
    3511                 :            : 
    3512                 :            :   /* Compute the set of hoistable expressions from ANTIC_IN.  First compute
    3513                 :            :      hoistable values.  */
    3514                 :    4626030 :   bitmap_set hoistable_set;
    3515                 :            : 
    3516                 :            :   /* A hoistable value must be in ANTIC_IN(block)
    3517                 :            :      but not in AVAIL_OUT(BLOCK).  */
    3518                 :    4626030 :   bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack);
    3519                 :    4626030 :   bitmap_and_compl (&hoistable_set.values,
    3520                 :    4626030 :                     &ANTIC_IN (block)->values, &AVAIL_OUT (block)->values);
    3521                 :            : 
    3522                 :            :   /* Short-cut for a common case: hoistable_set is empty.  */
    3523                 :    4626030 :   if (bitmap_empty_p (&hoistable_set.values))
    3524                 :            :     return false;
    3525                 :            : 
    3526                 :            :   /* Compute which of the hoistable values is in AVAIL_OUT of
    3527                 :            :      at least one of the successors of BLOCK.  */
    3528                 :    1040330 :   bitmap_head availout_in_some;
    3529                 :    1040330 :   bitmap_initialize (&availout_in_some, &grand_bitmap_obstack);
    3530                 :    3129020 :   FOR_EACH_EDGE (e, ei, block->succs)
    3531                 :            :     /* Do not consider expressions solely because their availability
    3532                 :            :        on loop exits.  They'd be ANTIC-IN throughout the whole loop
    3533                 :            :        and thus effectively hoisted across loops by combination of
    3534                 :            :        PRE and hoisting.  */
    3535                 :    2088700 :     if (! loop_exit_edge_p (block->loop_father, e))
    3536                 :    1864040 :       bitmap_ior_and_into (&availout_in_some, &hoistable_set.values,
    3537                 :    1864040 :                            &AVAIL_OUT (e->dest)->values);
    3538                 :    1040330 :   bitmap_clear (&hoistable_set.values);
    3539                 :            : 
    3540                 :            :   /* Short-cut for a common case: availout_in_some is empty.  */
    3541                 :    1040330 :   if (bitmap_empty_p (&availout_in_some))
    3542                 :            :     return false;
    3543                 :            : 
    3544                 :            :   /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set.  */
    3545                 :      67427 :   bitmap_move (&hoistable_set.values, &availout_in_some);
    3546                 :      67427 :   hoistable_set.expressions = ANTIC_IN (block)->expressions;
    3547                 :            : 
    3548                 :            :   /* Now finally construct the topological-ordered expression set.  */
    3549                 :      67427 :   vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set);
    3550                 :            : 
    3551                 :      67427 :   bitmap_clear (&hoistable_set.values);
    3552                 :            : 
    3553                 :            :   /* If there are candidate values for hoisting, insert expressions
    3554                 :            :      strategically to make the hoistable expressions fully redundant.  */
    3555                 :      67427 :   pre_expr expr;
    3556                 :     175911 :   FOR_EACH_VEC_ELT (exprs, i, expr)
    3557                 :            :     {
    3558                 :            :       /* While we try to sort expressions topologically above the
    3559                 :            :          sorting doesn't work out perfectly.  Catch expressions we
    3560                 :            :          already inserted.  */
    3561                 :     108484 :       unsigned int value_id = get_expr_value_id (expr);
    3562                 :     108484 :       if (bitmap_set_contains_value (AVAIL_OUT (block), value_id))
    3563                 :            :         {
    3564                 :       4013 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3565                 :            :             {
    3566                 :          0 :               fprintf (dump_file,
    3567                 :            :                        "Already inserted expression for ");
    3568                 :          0 :               print_pre_expr (dump_file, expr);
    3569                 :          0 :               fprintf (dump_file, " (%04d)\n", value_id);
    3570                 :            :             }
    3571                 :       5392 :           continue;
    3572                 :            :         }
    3573                 :            : 
    3574                 :            :       /* OK, we should hoist this value.  Perform the transformation.  */
    3575                 :     104471 :       pre_stats.hoist_insert++;
    3576                 :     104471 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3577                 :            :         {
    3578                 :          4 :           fprintf (dump_file,
    3579                 :            :                    "Inserting expression in block %d for code hoisting: ",
    3580                 :            :                    block->index);
    3581                 :          4 :           print_pre_expr (dump_file, expr);
    3582                 :          4 :           fprintf (dump_file, " (%04d)\n", value_id);
    3583                 :            :         }
    3584                 :            : 
    3585                 :     104471 :       gimple_seq stmts = NULL;
    3586                 :     104471 :       tree res = create_expression_by_pieces (block, expr, &stmts,
    3587                 :            :                                               get_expr_type (expr));
    3588                 :            : 
    3589                 :            :       /* Do not return true if expression creation ultimately
    3590                 :            :          did not insert any statements.  */
    3591                 :     104471 :       if (gimple_seq_empty_p (stmts))
    3592                 :            :         res = NULL_TREE;
    3593                 :            :       else
    3594                 :            :         {
    3595                 :     103096 :           if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
    3596                 :     103096 :             gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
    3597                 :            :           else
    3598                 :          0 :             gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT);
    3599                 :            :         }
    3600                 :            : 
    3601                 :            :       /* Make sure to not return true if expression creation ultimately
    3602                 :            :          failed but also make sure to insert any stmts produced as they
    3603                 :            :          are tracked in inserted_exprs.  */
    3604                 :     103096 :       if (! res)
    3605                 :       1379 :         continue;
    3606                 :            : 
    3607                 :     103092 :       new_stuff = true;
    3608                 :            :     }
    3609                 :            : 
    3610                 :      67427 :   exprs.release ();
    3611                 :            : 
    3612                 :            :   return new_stuff;
    3613                 :            : }
    3614                 :            : 
    3615                 :            : /* Perform insertion of partially redundant and hoistable values.  */
    3616                 :            : 
    3617                 :            : static void
    3618                 :     645448 : insert (void)
    3619                 :            : {
    3620                 :     645448 :   basic_block bb;
    3621                 :            : 
    3622                 :   10313800 :   FOR_ALL_BB_FN (bb, cfun)
    3623                 :    9668380 :     NEW_SETS (bb) = bitmap_set_new ();
    3624                 :            : 
    3625                 :     645448 :   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
    3626                 :     645448 :   int rpo_num = pre_and_rev_post_order_compute (NULL, rpo, false);
    3627                 :            : 
    3628                 :     645448 :   int num_iterations = 0;
    3629                 :     779889 :   bool changed;
    3630                 :     779889 :   do
    3631                 :            :     {
    3632                 :     779889 :       num_iterations++;
    3633                 :     779889 :       if (dump_file && dump_flags & TDF_DETAILS)
    3634                 :         27 :         fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
    3635                 :            : 
    3636                 :            :       changed = false;
    3637                 :   15704100 :       for (int idx = 0; idx < rpo_num; ++idx)
    3638                 :            :         {
    3639                 :   14924200 :           basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
    3640                 :   14924200 :           basic_block dom = get_immediate_dominator (CDI_DOMINATORS, block);
    3641                 :   14924200 :           if (dom)
    3642                 :            :             {
    3643                 :   14924200 :               unsigned i;
    3644                 :   14924200 :               bitmap_iterator bi;
    3645                 :   14924200 :               bitmap_set_t newset;
    3646                 :            : 
    3647                 :            :               /* First, update the AVAIL_OUT set with anything we may have
    3648                 :            :                  inserted higher up in the dominator tree.  */
    3649                 :   14924200 :               newset = NEW_SETS (dom);
    3650                 :   14924200 :               if (newset)
    3651                 :            :                 {
    3652                 :            :                   /* Note that we need to value_replace both NEW_SETS, and
    3653                 :            :                      AVAIL_OUT. For both the case of NEW_SETS, the value may be
    3654                 :            :                      represented by some non-simple expression here that we want
    3655                 :            :                      to replace it with.  */
    3656                 :   27631100 :                   FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
    3657                 :            :                     {
    3658                 :   12706800 :                       pre_expr expr = expression_for_id (i);
    3659                 :   12706800 :                       bitmap_value_replace_in_set (NEW_SETS (block), expr);
    3660                 :   12706800 :                       bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
    3661                 :            :                     }
    3662                 :            :                 }
    3663                 :            : 
    3664                 :            :               /* Insert expressions for partial redundancies.  */
    3665                 :   14924200 :               if (flag_tree_pre && !single_pred_p (block))
    3666                 :            :                 {
    3667                 :    3035470 :                   changed |= do_pre_regular_insertion (block, dom);
    3668                 :    3035470 :                   if (do_partial_partial)
    3669                 :     269076 :                     changed |= do_pre_partial_partial_insertion (block, dom);
    3670                 :            :                 }
    3671                 :            : 
    3672                 :            :               /* Insert expressions for hoisting.  */
    3673                 :   20339800 :               if (flag_code_hoisting && EDGE_COUNT (block->succs) >= 2)
    3674                 :    5415590 :                 changed |= do_hoist_insertion (block);
    3675                 :            :             }
    3676                 :            :         }
    3677                 :            : 
    3678                 :            :       /* Clear the NEW sets before the next iteration.  We have already
    3679                 :            :          fully propagated its contents.  */
    3680                 :     779889 :       if (changed)
    3681                 :    6950070 :         FOR_ALL_BB_FN (bb, cfun)
    3682                 :   13631300 :           bitmap_set_free (NEW_SETS (bb));
    3683                 :            :     }
    3684                 :            :   while (changed);
    3685                 :            : 
    3686                 :     645448 :   statistics_histogram_event (cfun, "insert iterations", num_iterations);
    3687                 :            : 
    3688                 :     645448 :   free (rpo);
    3689                 :     645448 : }
    3690                 :            : 
    3691                 :            : 
    3692                 :            : /* Compute the AVAIL set for all basic blocks.
    3693                 :            : 
    3694                 :            :    This function performs value numbering of the statements in each basic
    3695                 :            :    block.  The AVAIL sets are built from information we glean while doing
    3696                 :            :    this value numbering, since the AVAIL sets contain only one entry per
    3697                 :            :    value.
    3698                 :            : 
    3699                 :            :    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
    3700                 :            :    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
    3701                 :            : 
    3702                 :            : static void
    3703                 :     645448 : compute_avail (void)
    3704                 :            : {
    3705                 :            : 
    3706                 :     645448 :   basic_block block, son;
    3707                 :     645448 :   basic_block *worklist;
    3708                 :     645448 :   size_t sp = 0;
    3709                 :     645448 :   unsigned i;
    3710                 :     645448 :   tree name;
    3711                 :            : 
    3712                 :            :   /* We pretend that default definitions are defined in the entry block.
    3713                 :            :      This includes function arguments and the static chain decl.  */
    3714                 :   29786100 :   FOR_EACH_SSA_NAME (i, name, cfun)
    3715                 :            :     {
    3716                 :   22115700 :       pre_expr e;
    3717                 :   22115700 :       if (!SSA_NAME_IS_DEFAULT_DEF (name)
    3718                 :    1812020 :           || has_zero_uses (name)
    3719                 :   23593700 :           || virtual_operand_p (name))
    3720                 :   21282600 :         continue;
    3721                 :            : 
    3722                 :     833096 :       e = get_or_alloc_expr_for_name (name);
    3723                 :     833096 :       add_to_value (get_expr_value_id (e), e);
    3724                 :     833096 :       bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun)), e);
    3725                 :     833096 :       bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
    3726                 :            :                                     e);
    3727                 :            :     }
    3728                 :            : 
    3729                 :     645448 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3730                 :            :     {
    3731                 :         16 :       print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
    3732                 :            :                         "tmp_gen", ENTRY_BLOCK);
    3733                 :         16 :       print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
    3734                 :            :                         "avail_out", ENTRY_BLOCK);
    3735                 :            :     }
    3736                 :            : 
    3737                 :            :   /* Allocate the worklist.  */
    3738                 :     645448 :   worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
    3739                 :            : 
    3740                 :            :   /* Seed the algorithm by putting the dominator children of the entry
    3741                 :            :      block on the worklist.  */
    3742                 :     645448 :   for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (cfun));
    3743                 :    1290900 :        son;
    3744                 :     645448 :        son = next_dom_son (CDI_DOMINATORS, son))
    3745                 :     645448 :     worklist[sp++] = son;
    3746                 :            : 
    3747                 :    1290900 :   BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun))
    3748                 :    1290900 :     = ssa_default_def (cfun, gimple_vop (cfun));
    3749                 :            : 
    3750                 :            :   /* Loop until the worklist is empty.  */
    3751                 :    9022930 :   while (sp)
    3752                 :            :     {
    3753                 :    8377480 :       gimple *stmt;
    3754                 :    8377480 :       basic_block dom;
    3755                 :            : 
    3756                 :            :       /* Pick a block from the worklist.  */
    3757                 :    8377480 :       block = worklist[--sp];
    3758                 :    8377480 :       vn_context_bb = block;
    3759                 :            : 
    3760                 :            :       /* Initially, the set of available values in BLOCK is that of
    3761                 :            :          its immediate dominator.  */
    3762                 :    8377480 :       dom = get_immediate_dominator (CDI_DOMINATORS, block);
    3763                 :    8377480 :       if (dom)
    3764                 :            :         {
    3765                 :    8377480 :           bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
    3766                 :    8377480 :           BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom);
    3767                 :            :         }
    3768                 :            : 
    3769                 :            :       /* Generate values for PHI nodes.  */
    3770                 :   10716200 :       for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
    3771                 :    2338680 :            gsi_next (&gsi))
    3772                 :            :         {
    3773                 :    2338680 :           tree result = gimple_phi_result (gsi.phi ());
    3774                 :            : 
    3775                 :            :           /* We have no need for virtual phis, as they don't represent
    3776                 :            :              actual computations.  */
    3777                 :    4677360 :           if (virtual_operand_p (result))
    3778                 :            :             {
    3779                 :    1222580 :               BB_LIVE_VOP_ON_EXIT (block) = result;
    3780                 :    1222580 :               continue;
    3781                 :            :             }
    3782                 :            : 
    3783                 :    1116100 :           pre_expr e = get_or_alloc_expr_for_name (result);
    3784                 :    1116100 :           add_to_value (get_expr_value_id (e), e);
    3785                 :    1116100 :           bitmap_value_insert_into_set (AVAIL_OUT (block), e);
    3786                 :    1116100 :           bitmap_insert_into_set (PHI_GEN (block), e);
    3787                 :            :         }
    3788                 :            : 
    3789                 :    8377480 :       BB_MAY_NOTRETURN (block) = 0;
    3790                 :            : 
    3791                 :            :       /* Now compute value numbers and populate value sets with all
    3792                 :            :          the expressions computed in BLOCK.  */
    3793                 :   68814600 :       for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
    3794                 :   52059700 :            gsi_next (&gsi))
    3795                 :            :         {
    3796                 :   52059700 :           ssa_op_iter iter;
    3797                 :   52059700 :           tree op;
    3798                 :            : 
    3799                 :   52059700 :           stmt = gsi_stmt (gsi);
    3800                 :            : 
    3801                 :            :           /* Cache whether the basic-block has any non-visible side-effect
    3802                 :            :              or control flow.
    3803                 :            :              If this isn't a call or it is the last stmt in the
    3804                 :            :              basic-block then the CFG represents things correctly.  */
    3805                 :   52059700 :           if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
    3806                 :            :             {
    3807                 :            :               /* Non-looping const functions always return normally.
    3808                 :            :                  Otherwise the call might not return or have side-effects
    3809                 :            :                  that forbids hoisting possibly trapping expressions
    3810                 :            :                  before it.  */
    3811                 :    2725290 :               int flags = gimple_call_flags (stmt);
    3812                 :    2725290 :               if (!(flags & ECF_CONST)
    3813                 :    2725290 :                   || (flags & ECF_LOOPING_CONST_OR_PURE))
    3814                 :    2546900 :                 BB_MAY_NOTRETURN (block) = 1;
    3815                 :            :             }
    3816                 :            : 
    3817                 :   61432900 :           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
    3818                 :            :             {
    3819                 :    9373230 :               pre_expr e = get_or_alloc_expr_for_name (op);
    3820                 :            : 
    3821                 :    9373230 :               add_to_value (get_expr_value_id (e), e);
    3822                 :    9373230 :               bitmap_insert_into_set (TMP_GEN (block), e);
    3823                 :    9373230 :               bitmap_value_insert_into_set (AVAIL_OUT (block), e);
    3824                 :            :             }
    3825                 :            : 
    3826                 :   69802800 :           if (gimple_vdef (stmt))
    3827                 :    8533610 :             BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
    3828                 :            : 
    3829                 :   52059700 :           if (gimple_has_side_effects (stmt)
    3830                 :   47570900 :               || stmt_could_throw_p (cfun, stmt)
    3831                 :   98790900 :               || is_gimple_debug (stmt))
    3832                 :   48783700 :             continue;
    3833                 :            : 
    3834                 :   29259000 :           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
    3835                 :            :             {
    3836                 :   13482700 :               if (ssa_undefined_value_p (op))
    3837                 :      21979 :                 continue;
    3838                 :   13460700 :               pre_expr e = get_or_alloc_expr_for_name (op);
    3839                 :   13460700 :               bitmap_value_insert_into_set (EXP_GEN (block), e);
    3840                 :            :             }
    3841                 :            : 
    3842                 :   15776300 :           switch (gimple_code (stmt))
    3843                 :            :             {
    3844                 :     628817 :             case GIMPLE_RETURN:
    3845                 :     628817 :               continue;
    3846                 :            : 
    3847                 :     265702 :             case GIMPLE_CALL:
    3848                 :     265702 :               {
    3849                 :     265702 :                 vn_reference_t ref;
    3850                 :     265702 :                 vn_reference_s ref1;
    3851                 :     265702 :                 pre_expr result = NULL;
    3852                 :            : 
    3853                 :            :                 /* We can value number only calls to real functions.  */
    3854                 :     265702 :                 if (gimple_call_internal_p (stmt))
    3855                 :      50275 :                   continue;
    3856                 :            : 
    3857                 :     215427 :                 vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
    3858                 :     215427 :                 if (!ref)
    3859                 :         66 :                   continue;
    3860                 :            : 
    3861                 :            :                 /* If the value of the call is not invalidated in
    3862                 :            :                    this block until it is computed, add the expression
    3863                 :            :                    to EXP_GEN.  */
    3864                 :     215361 :                 if (!gimple_vuse (stmt)
    3865                 :      90432 :                     || gimple_code
    3866                 :      90432 :                          (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI
    3867                 :     290973 :                     || gimple_bb (SSA_NAME_DEF_STMT
    3868                 :            :                                     (gimple_vuse (stmt))) != block)
    3869                 :            :                   {
    3870                 :     176849 :                     result = pre_expr_pool.allocate ();
    3871                 :     176849 :                     result->kind = REFERENCE;
    3872                 :     176849 :                     result->id = 0;
    3873                 :     176849 :                     result->loc = gimple_location (stmt);
    3874                 :     176849 :                     PRE_EXPR_REFERENCE (result) = ref;
    3875                 :            : 
    3876                 :     176849 :                     get_or_alloc_expression_id (result);
    3877                 :     176849 :                     add_to_value (get_expr_value_id (result), result);
    3878                 :     176849 :                     bitmap_value_insert_into_set (EXP_GEN (block), result);
    3879                 :            :                   }
    3880                 :     215361 :                 continue;
    3881                 :            :               }
    3882                 :            : 
    3883                 :   11605700 :             case GIMPLE_ASSIGN:
    3884                 :   11605700 :               {
    3885                 :   11605700 :                 pre_expr result = NULL;
    3886                 :   11605700 :                 switch (vn_get_stmt_kind (stmt))
    3887                 :            :                   {
    3888                 :    4490760 :                   case VN_NARY:
    3889                 :    4490760 :                     {
    3890                 :    4490760 :                       enum tree_code code = gimple_assign_rhs_code (stmt);
    3891                 :    4490760 :                       vn_nary_op_t nary;
    3892                 :            : 
    3893                 :            :                       /* COND_EXPR and VEC_COND_EXPR are awkward in
    3894                 :            :                          that they contain an embedded complex expression.
    3895                 :            :                          Don't even try to shove those through PRE.  */
    3896                 :    4498620 :                       if (code == COND_EXPR
    3897                 :    4490760 :                           || code == VEC_COND_EXPR)
    3898                 :      96131 :                         continue;
    3899                 :            : 
    3900                 :    4482900 :                       vn_nary_op_lookup_stmt (stmt, &nary);
    3901                 :    4482900 :                       if (!nary || nary->predicated_values)
    3902                 :      64272 :                         continue;
    3903                 :            : 
    3904                 :            :                       /* If the NARY traps and there was a preceding
    3905                 :            :                          point in the block that might not return avoid
    3906                 :            :                          adding the nary to EXP_GEN.  */
    3907                 :    4442630 :                       if (BB_MAY_NOTRETURN (block)
    3908                 :    4418630 :                           && vn_nary_may_trap (nary))
    3909                 :      24001 :                         continue;
    3910                 :            : 
    3911                 :    4394630 :                       result = pre_expr_pool.allocate ();
    3912                 :    4394630 :                       result->kind = NARY;
    3913                 :    4394630 :                       result->id = 0;
    3914                 :    4394630 :                       result->loc = gimple_location (stmt);
    3915                 :    4394630 :                       PRE_EXPR_NARY (result) = nary;
    3916                 :    4394630 :                       break;
    3917                 :            :                     }
    3918                 :            : 
    3919                 :    3288540 :                   case VN_REFERENCE:
    3920                 :    3288540 :                     {
    3921                 :    3288540 :                       tree rhs1 = gimple_assign_rhs1 (stmt);
    3922                 :    3288540 :                       ao_ref rhs1_ref;
    3923                 :    3288540 :                       ao_ref_init (&rhs1_ref, rhs1);
    3924                 :    3288540 :                       alias_set_type set = ao_ref_alias_set (&rhs1_ref);
    3925                 :    3288540 :                       alias_set_type base_set
    3926                 :    3288540 :                         = ao_ref_base_alias_set (&rhs1_ref);
    3927                 :    3288540 :                       vec<vn_reference_op_s> operands
    3928                 :    3288540 :                         = vn_reference_operands_for_lookup (rhs1);
    3929                 :    3288540 :                       vn_reference_t ref;
    3930                 :    6577080 :                       vn_reference_lookup_pieces (gimple_vuse (stmt), set,
    3931                 :    3288540 :                                                   base_set, TREE_TYPE (rhs1),
    3932                 :            :                                                   operands, &ref, VN_WALK);
    3933                 :    3288540 :                       if (!ref)
    3934                 :            :                         {
    3935                 :     300680 :                           operands.release ();
    3936                 :    1115000 :                           continue;
    3937                 :            :                         }
    3938                 :            : 
    3939                 :            :                       /* If the REFERENCE traps and there was a preceding
    3940                 :            :                          point in the block that might not return avoid
    3941                 :            :                          adding the reference to EXP_GEN.  */
    3942                 :    3119480 :                       if (BB_MAY_NOTRETURN (block)
    3943                 :    2987860 :                           && vn_reference_may_trap (ref))
    3944                 :     131622 :                         continue;
    3945                 :            : 
    3946                 :            :                       /* If the value of the reference is not invalidated in
    3947                 :            :                          this block until it is computed, add the expression
    3948                 :            :                          to EXP_GEN.  */
    3949                 :    5712480 :                       if (gimple_vuse (stmt))
    3950                 :            :                         {
    3951                 :    2653040 :                           gimple *def_stmt;
    3952                 :    2653040 :                           bool ok = true;
    3953                 :    2653040 :                           def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt));
    3954                 :    5254060 :                           while (!gimple_nop_p (def_stmt)
    3955                 :    4775300 :                                  && gimple_code (def_stmt) != GIMPLE_PHI
    3956                 :    9253660 :                                  && gimple_bb (def_stmt) == block)
    3957                 :            :                             {
    3958                 :    6567430 :                               if (stmt_may_clobber_ref_p
    3959                 :    3283710 :                                     (def_stmt, gimple_assign_rhs1 (stmt)))
    3960                 :            :                                 {
    3961                 :            :                                   ok = false;
    3962                 :            :                                   break;
    3963                 :            :                                 }
    3964                 :    2601020 :                               def_stmt
    3965                 :    2601020 :                                 = SSA_NAME_DEF_STMT (gimple_vuse (def_stmt));
    3966                 :            :                             }
    3967                 :    2653040 :                           if (!ok)
    3968                 :            :                             {
    3969                 :     682694 :                               operands.release ();
    3970                 :     682694 :                               continue;
    3971                 :            :                             }
    3972                 :            :                         }
    3973                 :            : 
    3974                 :            :                       /* If the load was value-numbered to another
    3975                 :            :                          load make sure we do not use its expression
    3976                 :            :                          for insertion if it wouldn't be a valid
    3977                 :            :                          replacement.  */
    3978                 :            :                       /* At the momemt we have a testcase
    3979                 :            :                          for hoist insertion of aligned vs. misaligned
    3980                 :            :                          variants in gcc.dg/torture/pr65270-1.c thus
    3981                 :            :                          with just alignment to be considered we can
    3982                 :            :                          simply replace the expression in the hashtable
    3983                 :            :                          with the most conservative one.  */
    3984                 :    2173540 :                       vn_reference_op_t ref1 = &ref->operands.last ();
    3985                 :    4347070 :                       while (ref1->opcode != TARGET_MEM_REF
    3986                 :    4347070 :                              && ref1->opcode != MEM_REF
    3987                 :    4347070 :                              && ref1 != &ref->operands[0])
    3988                 :    2173520 :                         --ref1;
    3989                 :    2173540 :                       vn_reference_op_t ref2 = &operands.last ();
    3990                 :    4347070 :                       while (ref2->opcode != TARGET_MEM_REF
    3991                 :    4347070 :                              && ref2->opcode != MEM_REF
    3992                 :    4347070 :                              && ref2 != &operands[0])
    3993                 :    2173520 :                         --ref2;
    3994                 :    2173540 :                       if ((ref1->opcode == TARGET_MEM_REF
    3995                 :            :                            || ref1->opcode == MEM_REF)
    3996                 :    4346840 :                           && (TYPE_ALIGN (ref1->type)
    3997                 :    2173300 :                               > TYPE_ALIGN (ref2->type)))
    3998                 :        186 :                         ref1->type
    3999                 :        186 :                           = build_aligned_type (ref1->type,
    4000                 :        186 :                                                 TYPE_ALIGN (ref2->type));
    4001                 :            :                       /* TBAA behavior is an obvious part so make sure
    4002                 :            :                          that the hashtable one covers this as well
    4003                 :            :                          by adjusting the ref alias set and its base.  */
    4004                 :    2173540 :                       if (ref->set == set
    4005                 :    2173540 :                           || alias_set_subset_of (set, ref->set))
    4006                 :            :                         ;
    4007                 :       2858 :                       else if (alias_set_subset_of (ref->set, set))
    4008                 :            :                         {
    4009                 :       2251 :                           ref->set = set;
    4010                 :       2251 :                           if (ref1->opcode == MEM_REF)
    4011                 :       2251 :                             ref1->op0
    4012                 :       2251 :                               = wide_int_to_tree (TREE_TYPE (ref2->op0),
    4013                 :       4502 :                                                   wi::to_wide (ref1->op0));
    4014                 :            :                           else
    4015                 :          0 :                             ref1->op2
    4016                 :          0 :                               = wide_int_to_tree (TREE_TYPE (ref2->op2),
    4017                 :          0 :                                                   wi::to_wide (ref1->op2));
    4018                 :            :                         }
    4019                 :            :                       else
    4020                 :            :                         {
    4021                 :        607 :                           ref->set = 0;
    4022                 :        607 :                           if (ref1->opcode == MEM_REF)
    4023                 :        607 :                             ref1->op0
    4024                 :        607 :                               = wide_int_to_tree (ptr_type_node,
    4025                 :        607 :                                                   wi::to_wide (ref1->op0));
    4026                 :            :                           else
    4027                 :          0 :                             ref1->op2
    4028                 :          0 :                               = wide_int_to_tree (ptr_type_node,
    4029                 :          0 :                                                   wi::to_wide (ref1->op2));
    4030                 :            :                         }
    4031                 :    2173540 :                       operands.release ();
    4032                 :            : 
    4033                 :    2173540 :                       result = pre_expr_pool.allocate ();
    4034                 :    2173540 :                       result->kind = REFERENCE;
    4035                 :    2173540 :                       result->id = 0;
    4036                 :    2173540 :                       result->loc = gimple_location (stmt);
    4037                 :    2173540 :                       PRE_EXPR_REFERENCE (result) = ref;
    4038                 :    2173540 :                       break;
    4039                 :            :                     }
    4040                 :            : 
    4041                 :    3826420 :                   default:
    4042                 :    3826420 :                     continue;
    4043                 :            :                   }
    4044                 :            : 
    4045                 :    6568170 :                 get_or_alloc_expression_id (result);
    4046                 :    6568170 :                 add_to_value (get_expr_value_id (result), result);
    4047                 :    6568170 :                 bitmap_value_insert_into_set (EXP_GEN (block), result);
    4048                 :    6568170 :                 continue;
    4049                 :            :               }
    4050                 :    3276020 :             default:
    4051                 :    3904840 :               break;
    4052                 :            :             }
    4053                 :            :         }
    4054                 :            : 
    4055                 :    8377480 :       if (dump_file && (dump_flags & TDF_DETAILS))
    4056                 :            :         {
    4057                 :        116 :           print_bitmap_set (dump_file, EXP_GEN (block),
    4058                 :            :                             "exp_gen", block->index);
    4059                 :        116 :           print_bitmap_set (dump_file, PHI_GEN (block),
    4060                 :            :                             "phi_gen", block->index);
    4061                 :        116 :           print_bitmap_set (dump_file, TMP_GEN (block),
    4062                 :            :                             "tmp_gen", block->index);
    4063                 :        116 :           print_bitmap_set (dump_file, AVAIL_OUT (block),
    4064                 :            :                             "avail_out", block->index);
    4065                 :            :         }
    4066                 :            : 
    4067                 :            :       /* Put the dominator children of BLOCK on the worklist of blocks
    4068                 :            :          to compute available sets for.  */
    4069                 :    8377480 :       for (son = first_dom_son (CDI_DOMINATORS, block);
    4070                 :   16109500 :            son;
    4071                 :    7732030 :            son = next_dom_son (CDI_DOMINATORS, son))
    4072                 :    7732030 :         worklist[sp++] = son;
    4073                 :            :     }
    4074                 :     645448 :   vn_context_bb = NULL;
    4075                 :            : 
    4076                 :     645448 :   free (worklist);
    4077                 :     645448 : }
    4078                 :            : 
    4079                 :            : 
    4080                 :            : /* Initialize data structures used by PRE.  */
    4081                 :            : 
    4082                 :            : static void
    4083                 :     645456 : init_pre (void)
    4084                 :            : {
    4085                 :     645456 :   basic_block bb;
    4086                 :            : 
    4087                 :     645456 :   next_expression_id = 1;
    4088                 :     645456 :   expressions.create (0);
    4089                 :     645456 :   expressions.safe_push (NULL);
    4090                 :     645456 :   value_expressions.create (get_max_value_id () + 1);
    4091                 :     645456 :   value_expressions.safe_grow_cleared (get_max_value_id () + 1);
    4092                 :     645456 :   name_to_id.create (0);
    4093                 :            : 
    4094                 :     645456 :   inserted_exprs = BITMAP_ALLOC (NULL);
    4095                 :            : 
    4096                 :     645456 :   connect_infinite_loops_to_exit ();
    4097                 :     645456 :   memset (&pre_stats, 0, sizeof (pre_stats));
    4098                 :            : 
    4099                 :     645456 :   alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
    4100                 :            : 
    4101                 :     645456 :   calculate_dominance_info (CDI_DOMINATORS);
    4102                 :            : 
    4103                 :     645456 :   bitmap_obstack_initialize (&grand_bitmap_obstack);
    4104                 :     645456 :   phi_translate_table = new hash_table<expr_pred_trans_d> (5110);
    4105                 :    1290910 :   expression_to_id = new hash_table<pre_expr_d> (num_ssa_names * 3);
    4106                 :   10395800 :   FOR_ALL_BB_FN (bb, cfun)
    4107                 :            :     {
    4108                 :    9750340 :       EXP_GEN (bb) = bitmap_set_new ();
    4109                 :    9750340 :       PHI_GEN (bb) = bitmap_set_new ();
    4110                 :    9750340 :       TMP_GEN (bb) = bitmap_set_new ();
    4111                 :    9750340 :       AVAIL_OUT (bb) = bitmap_set_new ();
    4112                 :            :     }
    4113                 :     645456 : }
    4114                 :            : 
    4115                 :            : 
    4116                 :            : /* Deallocate data structures used by PRE.  */
    4117                 :            : 
    4118                 :            : static void
    4119                 :     645456 : fini_pre ()
    4120                 :            : {
    4121                 :     645456 :   value_expressions.release ();
    4122                 :     645456 :   expressions.release ();
    4123                 :     645456 :   BITMAP_FREE (inserted_exprs);
    4124                 :     645456 :   bitmap_obstack_release (&grand_bitmap_obstack);
    4125                 :     645456 :   bitmap_set_pool.release ();
    4126                 :     645456 :   pre_expr_pool.release ();
    4127                 :     645456 :   delete phi_translate_table;
    4128                 :     645456 :   phi_translate_table = NULL;
    4129                 :     645456 :   delete expression_to_id;
    4130                 :     645456 :   expression_to_id = NULL;
    4131                 :     645456 :   name_to_id.release ();
    4132                 :            : 
    4133                 :     645456 :   free_aux_for_blocks ();
    4134                 :     645456 : }
    4135                 :            : 
    4136                 :            : namespace {
    4137                 :            : 
    4138                 :            : const pass_data pass_data_pre =
    4139                 :            : {
    4140                 :            :   GIMPLE_PASS, /* type */
    4141                 :            :   "pre", /* name */
    4142                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    4143                 :            :   TV_TREE_PRE, /* tv_id */
    4144                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    4145                 :            :   0, /* properties_provided */
    4146                 :            :   0, /* properties_destroyed */
    4147                 :            :   TODO_rebuild_alias, /* todo_flags_start */
    4148                 :            :   0, /* todo_flags_finish */
    4149                 :            : };
    4150                 :            : 
    4151                 :            : class pass_pre : public gimple_opt_pass
    4152                 :            : {
    4153                 :            : public:
    4154                 :     200773 :   pass_pre (gcc::context *ctxt)
    4155                 :     401546 :     : gimple_opt_pass (pass_data_pre, ctxt)
    4156                 :            :   {}
    4157                 :            : 
    4158                 :            :   /* opt_pass methods: */
    4159                 :     686787 :   virtual bool gate (function *)
    4160                 :     686787 :     { return flag_tree_pre != 0 || flag_code_hoisting != 0; }
    4161                 :            :   virtual unsigned int execute (function *);
    4162                 :            : 
    4163                 :            : }; // class pass_pre
    4164                 :            : 
    4165                 :            : /* Valueization hook for RPO VN when we are calling back to it
    4166                 :            :    at ANTIC compute time.  */
    4167                 :            : 
    4168                 :            : static tree
    4169                 :   36870700 : pre_valueize (tree name)
    4170                 :            : {
    4171                 :   36870700 :   if (TREE_CODE (name) == SSA_NAME)
    4172                 :            :     {
    4173                 :   36676600 :       tree tem = VN_INFO (name)->valnum;
    4174                 :   36676600 :       if (tem != VN_TOP && tem != name)
    4175                 :            :         {
    4176                 :     652464 :           if (TREE_CODE (tem) != SSA_NAME
    4177                 :     652464 :               || SSA_NAME_IS_DEFAULT_DEF (tem))
    4178                 :            :             return tem;
    4179                 :            :           /* We create temporary SSA names for representatives that
    4180                 :            :              do not have a definition (yet) but are not default defs either
    4181                 :            :              assume they are fine to use.  */
    4182                 :     649803 :           basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem));
    4183                 :     649803 :           if (! def_bb
    4184                 :     649803 :               || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
    4185                 :      61881 :             return tem;
    4186                 :            :           /* ??? Now we could look for a leader.  Ideally we'd somehow
    4187                 :            :              expose RPO VN leaders and get rid of AVAIL_OUT as well...  */
    4188                 :            :         }
    4189                 :            :     }
    4190                 :            :   return name;
    4191                 :            : }
    4192                 :            : 
    4193                 :            : unsigned int
    4194                 :     645456 : pass_pre::execute (function *fun)
    4195                 :            : {
    4196                 :     645456 :   unsigned int todo = 0;
    4197                 :            : 
    4198                 :    1290910 :   do_partial_partial =
    4199                 :     645456 :     flag_tree_partial_pre && optimize_function_for_speed_p (fun);
    4200                 :            : 
    4201                 :            :   /* This has to happen before VN runs because
    4202                 :            :      loop_optimizer_init may create new phis, etc.  */
    4203                 :     645456 :   loop_optimizer_init (LOOPS_NORMAL);
    4204                 :     645456 :   split_edges_for_insertion ();
    4205                 :     645456 :   scev_initialize ();
    4206                 :     645456 :   calculate_dominance_info (CDI_DOMINATORS);
    4207                 :            : 
    4208                 :     645456 :   run_rpo_vn (VN_WALK);
    4209                 :            : 
    4210                 :     645456 :   init_pre ();
    4211                 :            : 
    4212                 :     645456 :   vn_valueize = pre_valueize;
    4213                 :            : 
    4214                 :            :   /* Insert can get quite slow on an incredibly large number of basic
    4215                 :            :      blocks due to some quadratic behavior.  Until this behavior is
    4216                 :            :      fixed, don't run it when he have an incredibly large number of
    4217                 :            :      bb's.  If we aren't going to run insert, there is no point in
    4218                 :            :      computing ANTIC, either, even though it's plenty fast nor do
    4219                 :            :      we require AVAIL.  */
    4220                 :     645456 :   if (n_basic_blocks_for_fn (fun) < 4000)
    4221                 :            :     {
    4222                 :     645448 :       compute_avail ();
    4223                 :     645448 :       compute_antic ();
    4224                 :     645448 :       insert ();
    4225                 :            :     }
    4226                 :            : 
    4227                 :            :   /* Make sure to remove fake edges before committing our inserts.
    4228                 :            :      This makes sure we don't end up with extra critical edges that
    4229                 :            :      we would need to split.  */
    4230                 :     645456 :   remove_fake_exit_edges ();
    4231                 :     645456 :   gsi_commit_edge_inserts ();
    4232                 :            : 
    4233                 :            :   /* Eliminate folds statements which might (should not...) end up
    4234                 :            :      not keeping virtual operands up-to-date.  */
    4235                 :     645456 :   gcc_assert (!need_ssa_update_p (fun));
    4236                 :            : 
    4237                 :     645456 :   statistics_counter_event (fun, "Insertions", pre_stats.insertions);
    4238                 :     645456 :   statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
    4239                 :     645456 :   statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
    4240                 :     645456 :   statistics_counter_event (fun, "New PHIs", pre_stats.phis);
    4241                 :            : 
    4242                 :     645456 :   todo |= eliminate_with_rpo_vn (inserted_exprs);
    4243                 :            : 
    4244                 :     645456 :   vn_valueize = NULL;
    4245                 :            : 
    4246                 :            :   /* Because we don't follow exactly the standard PRE algorithm, and decide not
    4247                 :            :      to insert PHI nodes sometimes, and because value numbering of casts isn't
    4248                 :            :      perfect, we sometimes end up inserting dead code.   This simple DCE-like
    4249                 :            :      pass removes any insertions we made that weren't actually used.  */
    4250                 :     645456 :   simple_dce_from_worklist (inserted_exprs);
    4251                 :            : 
    4252                 :     645456 :   fini_pre ();
    4253                 :            : 
    4254                 :     645456 :   scev_finalize ();
    4255                 :     645456 :   loop_optimizer_finalize ();
    4256                 :            : 
    4257                 :            :   /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
    4258                 :            :      case we can merge the block with the remaining predecessor of the block.
    4259                 :            :      It should either:
    4260                 :            :      - call merge_blocks after each tail merge iteration
    4261                 :            :      - call merge_blocks after all tail merge iterations
    4262                 :            :      - mark TODO_cleanup_cfg when necessary
    4263                 :            :      - share the cfg cleanup with fini_pre.  */
    4264                 :     645456 :   todo |= tail_merge_optimize (todo);
    4265                 :            : 
    4266                 :     645456 :   free_rpo_vn ();
    4267                 :            : 
    4268                 :            :   /* Tail merging invalidates the virtual SSA web, together with
    4269                 :            :      cfg-cleanup opportunities exposed by PRE this will wreck the
    4270                 :            :      SSA updating machinery.  So make sure to run update-ssa
    4271                 :            :      manually, before eventually scheduling cfg-cleanup as part of
    4272                 :            :      the todo.  */
    4273                 :     645456 :   update_ssa (TODO_update_ssa_only_virtuals);
    4274                 :            : 
    4275                 :     645456 :   return todo;
    4276                 :            : }
    4277                 :            : 
    4278                 :            : } // anon namespace
    4279                 :            : 
    4280                 :            : gimple_opt_pass *
    4281                 :     200773 : make_pass_pre (gcc::context *ctxt)
    4282                 :            : {
    4283                 :     200773 :   return new pass_pre (ctxt);
    4284                 :            : }

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.