LCOV - code coverage report
Current view: top level - gcc - tree-ssa-scopedtables.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 580 607 95.6 %
Date: 2020-03-28 11:57:23 Functions: 24 24 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Header file for SSA dominator optimizations.
       2                 :            :    Copyright (C) 2013-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it under
       7                 :            : the terms of the GNU General Public License as published by the Free
       8                 :            : Software Foundation; either version 3, or (at your option) any later
       9                 :            : version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            :  for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "function.h"
      24                 :            : #include "basic-block.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "gimple.h"
      27                 :            : #include "tree-pass.h"
      28                 :            : #include "tree-pretty-print.h"
      29                 :            : #include "tree-ssa-scopedtables.h"
      30                 :            : #include "tree-ssa-threadedge.h"
      31                 :            : #include "stor-layout.h"
      32                 :            : #include "fold-const.h"
      33                 :            : #include "tree-eh.h"
      34                 :            : #include "internal-fn.h"
      35                 :            : #include "tree-dfa.h"
      36                 :            : #include "options.h"
      37                 :            : 
      38                 :            : static bool hashable_expr_equal_p (const struct hashable_expr *,
      39                 :            :                                    const struct hashable_expr *);
      40                 :            : 
      41                 :            : /* Initialize local stacks for this optimizer and record equivalences
      42                 :            :    upon entry to BB.  Equivalences can come from the edge traversed to
      43                 :            :    reach BB or they may come from PHI nodes at the start of BB.  */
      44                 :            : 
      45                 :            : /* Pop items off the unwinding stack, removing each from the hash table
      46                 :            :    until a marker is encountered.  */
      47                 :            : 
      48                 :            : void
      49                 :   65375600 : avail_exprs_stack::pop_to_marker ()
      50                 :            : {
      51                 :            :   /* Remove all the expressions made available in this block.  */
      52                 :  149230000 :   while (m_stack.length () > 0)
      53                 :            :     {
      54                 :  149230000 :       std::pair<expr_hash_elt_t, expr_hash_elt_t> victim = m_stack.pop ();
      55                 :  149230000 :       expr_hash_elt **slot;
      56                 :            : 
      57                 :  149230000 :       if (victim.first == NULL)
      58                 :            :         break;
      59                 :            : 
      60                 :            :       /* This must precede the actual removal from the hash table,
      61                 :            :          as ELEMENT and the table entry may share a call argument
      62                 :            :          vector which will be freed during removal.  */
      63                 :   83854300 :       if (dump_file && (dump_flags & TDF_DETAILS))
      64                 :            :         {
      65                 :       3661 :           fprintf (dump_file, "<<<< ");
      66                 :       3661 :           victim.first->print (dump_file);
      67                 :            :         }
      68                 :            : 
      69                 :   83854300 :       slot = m_avail_exprs->find_slot (victim.first, NO_INSERT);
      70                 :   83854300 :       gcc_assert (slot && *slot == victim.first);
      71                 :   83854300 :       if (victim.second != NULL)
      72                 :            :         {
      73                 :    2819800 :           delete *slot;
      74                 :    2819800 :           *slot = victim.second;
      75                 :            :         }
      76                 :            :       else
      77                 :   81034500 :         m_avail_exprs->clear_slot (slot);
      78                 :            :     }
      79                 :   65375600 : }
      80                 :            : 
      81                 :            : /* Add <ELT1,ELT2> to the unwinding stack so they can be later removed
      82                 :            :    from the hash table.  */
      83                 :            : 
      84                 :            : void
      85                 :  149230000 : avail_exprs_stack::record_expr (class expr_hash_elt *elt1,
      86                 :            :                                 class expr_hash_elt *elt2,
      87                 :            :                                 char type)
      88                 :            : {
      89                 :  149230000 :   if (elt1 && dump_file && (dump_flags & TDF_DETAILS))
      90                 :            :     {
      91                 :       3661 :       fprintf (dump_file, "%c>>> ", type);
      92                 :       3661 :       elt1->print (dump_file);
      93                 :            :     }
      94                 :            : 
      95                 :  149230000 :   m_stack.safe_push (std::pair<expr_hash_elt_t, expr_hash_elt_t> (elt1, elt2));
      96                 :  149230000 : }
      97                 :            : 
      98                 :            : /* Helper for walk_non_aliased_vuses.  Determine if we arrived at
      99                 :            :    the desired memory state.  */
     100                 :            : 
     101                 :            : static void *
     102                 :   13660800 : vuse_eq (ao_ref *, tree vuse1, void *data)
     103                 :            : {
     104                 :   13660800 :   tree vuse2 = (tree) data;
     105                 :   13660800 :   if (vuse1 == vuse2)
     106                 :     244174 :     return data;
     107                 :            : 
     108                 :            :   return NULL;
     109                 :            : }
     110                 :            : 
     111                 :            : /* We looked for STMT in the hash table, but did not find it.
     112                 :            : 
     113                 :            :    If STMT is an assignment from a binary operator, we may know something
     114                 :            :    about the operands relationship to each other which would allow
     115                 :            :    us to derive a constant value for the RHS of STMT.  */
     116                 :            : 
     117                 :            : tree
     118                 :   28567600 : avail_exprs_stack::simplify_binary_operation (gimple *stmt,
     119                 :            :                                               class expr_hash_elt element)
     120                 :            : {
     121                 :   28567600 :   if (is_gimple_assign (stmt))
     122                 :            :     {
     123                 :   22824800 :       struct hashable_expr *expr = element.expr ();
     124                 :   22824800 :       if (expr->kind == EXPR_BINARY)
     125                 :            :         {
     126                 :    5910160 :           enum tree_code code = expr->ops.binary.op;
     127                 :            : 
     128                 :    5910160 :           switch (code)
     129                 :            :             {
     130                 :            :             /* For these cases, if we know the operands
     131                 :            :                are equal, then we know the result.  */
     132                 :    1313220 :             case MIN_EXPR:
     133                 :    1313220 :             case MAX_EXPR:
     134                 :    1313220 :             case BIT_IOR_EXPR:
     135                 :    1313220 :             case BIT_AND_EXPR:
     136                 :    1313220 :             case BIT_XOR_EXPR:
     137                 :    1313220 :             case MINUS_EXPR:
     138                 :    1313220 :             case TRUNC_DIV_EXPR:
     139                 :    1313220 :             case CEIL_DIV_EXPR:
     140                 :    1313220 :             case FLOOR_DIV_EXPR:
     141                 :    1313220 :             case ROUND_DIV_EXPR:
     142                 :    1313220 :             case EXACT_DIV_EXPR:
     143                 :    1313220 :             case TRUNC_MOD_EXPR:
     144                 :    1313220 :             case CEIL_MOD_EXPR:
     145                 :    1313220 :             case FLOOR_MOD_EXPR:
     146                 :    1313220 :             case ROUND_MOD_EXPR:
     147                 :    1313220 :               {
     148                 :            :                 /* Build a simple equality expr and query the hash table
     149                 :            :                    for it.  */
     150                 :    1313220 :                 struct hashable_expr expr;
     151                 :    1313220 :                 expr.type = boolean_type_node;
     152                 :    1313220 :                 expr.kind = EXPR_BINARY;
     153                 :    1313220 :                 expr.ops.binary.op = EQ_EXPR;
     154                 :    1313220 :                 expr.ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
     155                 :    1313220 :                 expr.ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
     156                 :    1313220 :                 class expr_hash_elt element2 (&expr, NULL_TREE);
     157                 :    1313220 :                 expr_hash_elt **slot
     158                 :    1313220 :                   = m_avail_exprs->find_slot (&element2, NO_INSERT);
     159                 :    1313220 :                 tree result_type = TREE_TYPE (gimple_assign_lhs (stmt));
     160                 :            : 
     161                 :            :                 /* If the query was successful and returned a nonzero
     162                 :            :                    result, then we know that the operands of the binary
     163                 :            :                    expression are the same.  In many cases this allows
     164                 :            :                    us to compute a constant result of the expression
     165                 :            :                    at compile time, even if we do not know the exact
     166                 :            :                    values of the operands.  */
     167                 :    1313220 :                 if (slot && *slot && integer_onep ((*slot)->lhs ()))
     168                 :            :                   {
     169                 :         68 :                     switch (code)
     170                 :            :                       {
     171                 :          1 :                       case MIN_EXPR:
     172                 :          1 :                       case MAX_EXPR:
     173                 :          1 :                       case BIT_IOR_EXPR:
     174                 :          1 :                       case BIT_AND_EXPR:
     175                 :         52 :                         return gimple_assign_rhs1 (stmt);
     176                 :            : 
     177                 :         51 :                       case MINUS_EXPR:
     178                 :            :                         /* This is unsafe for certain floats even in non-IEEE
     179                 :            :                            formats.  In IEEE, it is unsafe because it does
     180                 :            :                            wrong for NaNs.  */
     181                 :         35 :                         if (FLOAT_TYPE_P (result_type)
     182                 :         51 :                             && HONOR_NANS (result_type))
     183                 :            :                           break;
     184                 :            :                         /* FALLTHRU */
     185                 :         50 :                       case BIT_XOR_EXPR:
     186                 :         50 :                       case TRUNC_MOD_EXPR:
     187                 :         50 :                       case CEIL_MOD_EXPR:
     188                 :         50 :                       case FLOOR_MOD_EXPR:
     189                 :         50 :                       case ROUND_MOD_EXPR:
     190                 :         50 :                         return build_zero_cst (result_type);
     191                 :            : 
     192                 :          1 :                       case TRUNC_DIV_EXPR:
     193                 :          1 :                       case CEIL_DIV_EXPR:
     194                 :          1 :                       case FLOOR_DIV_EXPR:
     195                 :          1 :                       case ROUND_DIV_EXPR:
     196                 :          1 :                       case EXACT_DIV_EXPR:
     197                 :            :                         /* Avoid _Fract types where we can't build 1.  */
     198                 :          4 :                         if (ALL_FRACT_MODE_P (TYPE_MODE (result_type)))
     199                 :            :                           break;
     200                 :          1 :                         return build_one_cst (result_type);
     201                 :            : 
     202                 :          0 :                       default:
     203                 :          0 :                         gcc_unreachable ();
     204                 :            :                       }
     205                 :            :                   }
     206                 :    1313160 :                 break;
     207                 :            :               }
     208                 :            : 
     209                 :            :             default:
     210                 :            :               break;
     211                 :            :             }
     212                 :            :         }
     213                 :            :     }
     214                 :            :   return NULL_TREE;
     215                 :            : }
     216                 :            : 
     217                 :            : /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table.
     218                 :            :    If found, return its LHS. Otherwise insert STMT in the table and
     219                 :            :    return NULL_TREE.
     220                 :            : 
     221                 :            :    Also, when an expression is first inserted in the  table, it is also
     222                 :            :    is also added to AVAIL_EXPRS_STACK, so that it can be removed when
     223                 :            :    we finish processing this block and its children.  */
     224                 :            : 
     225                 :            : tree
     226                 :   96459800 : avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p,
     227                 :            :                                       expr_hash_elt **elt)
     228                 :            : {
     229                 :   96459800 :   expr_hash_elt **slot;
     230                 :   96459800 :   tree lhs;
     231                 :            : 
     232                 :            :   /* Get LHS of phi, assignment, or call; else NULL_TREE.  */
     233                 :   96459800 :   if (gimple_code (stmt) == GIMPLE_PHI)
     234                 :    5211040 :     lhs = gimple_phi_result (stmt);
     235                 :            :   else
     236                 :   91248700 :     lhs = gimple_get_lhs (stmt);
     237                 :            : 
     238                 :  192920000 :   class expr_hash_elt element (stmt, lhs);
     239                 :            : 
     240                 :   96459800 :   if (dump_file && (dump_flags & TDF_DETAILS))
     241                 :            :     {
     242                 :       3660 :       fprintf (dump_file, "LKUP ");
     243                 :       3660 :       element.print (dump_file);
     244                 :            :     }
     245                 :            : 
     246                 :            :   /* Don't bother remembering constant assignments and copy operations.
     247                 :            :      Constants and copy operations are handled by the constant/copy propagator
     248                 :            :      in optimize_stmt.  */
     249                 :   96459800 :   if (element.expr()->kind == EXPR_SINGLE
     250                 :   96459800 :       && (TREE_CODE (element.expr()->ops.single.rhs) == SSA_NAME
     251                 :   42907900 :           || is_gimple_min_invariant (element.expr()->ops.single.rhs)))
     252                 :    9382240 :     return NULL_TREE;
     253                 :            : 
     254                 :            :   /* Finally try to find the expression in the main expression hash table.  */
     255                 :  142606000 :   slot = m_avail_exprs->find_slot (&element, (insert ? INSERT : NO_INSERT));
     256                 :   87077500 :   if (slot == NULL)
     257                 :            :     {
     258                 :            :       return NULL_TREE;
     259                 :            :     }
     260                 :   34833500 :   else if (*slot == NULL)
     261                 :            :     {
     262                 :            :       /* If we did not find the expression in the hash table, we may still
     263                 :            :          be able to produce a result for some expressions.  */
     264                 :   28567600 :       tree retval = avail_exprs_stack::simplify_binary_operation (stmt,
     265                 :            :                                                                   element);
     266                 :            : 
     267                 :            :       /* We have, in effect, allocated *SLOT for ELEMENT at this point.
     268                 :            :          We must initialize *SLOT to a real entry, even if we found a
     269                 :            :          way to prove ELEMENT was a constant after not finding ELEMENT
     270                 :            :          in the hash table.
     271                 :            : 
     272                 :            :          An uninitialized or empty slot is an indication no prior objects
     273                 :            :          entered into the hash table had a hash collection with ELEMENT.
     274                 :            : 
     275                 :            :          If we fail to do so and had such entries in the table, they
     276                 :            :          would become unreachable.  */
     277                 :   28567600 :       class expr_hash_elt *element2 = new expr_hash_elt (element);
     278                 :   28567600 :       *slot = element2;
     279                 :            : 
     280                 :   28567600 :       record_expr (element2, NULL, '2');
     281                 :   28567600 :       return retval;
     282                 :            :     }
     283                 :            : 
     284                 :            :   /* If we found a redundant memory operation do an alias walk to
     285                 :            :      check if we can re-use it.  */
     286                 :   12282500 :   if (gimple_vuse (stmt) != (*slot)->vop ())
     287                 :            :     {
     288                 :    5240650 :       tree vuse1 = (*slot)->vop ();
     289                 :    5240650 :       tree vuse2 = gimple_vuse (stmt);
     290                 :            :       /* If we have a load of a register and a candidate in the
     291                 :            :          hash with vuse1 then try to reach its stmt by walking
     292                 :            :          up the virtual use-def chain using walk_non_aliased_vuses.
     293                 :            :          But don't do this when removing expressions from the hash.  */
     294                 :    5240650 :       ao_ref ref;
     295                 :    5240650 :       unsigned limit = param_sccvn_max_alias_queries_per_access;
     296                 :    9783720 :       if (!(vuse1 && vuse2
     297                 :    5151560 :             && gimple_assign_single_p (stmt)
     298                 :    5151560 :             && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
     299                 :    4543070 :             && (ao_ref_init (&ref, gimple_assign_rhs1 (stmt)),
     300                 :    4543070 :                 ref.base_alias_set = ref.ref_alias_set = tbaa_p ? -1 : 0, true)
     301                 :    4543070 :             && walk_non_aliased_vuses (&ref, vuse2, true, vuse_eq, NULL, NULL,
     302                 :            :                                        limit, vuse1) != NULL))
     303                 :            :         {
     304                 :    4996480 :           if (insert)
     305                 :            :             {
     306                 :    2819800 :               class expr_hash_elt *element2 = new expr_hash_elt (element);
     307                 :            : 
     308                 :            :               /* Insert the expr into the hash by replacing the current
     309                 :            :                  entry and recording the value to restore in the
     310                 :            :                  avail_exprs_stack.  */
     311                 :    2819800 :               record_expr (element2, *slot, '2');
     312                 :    2819800 :               *slot = element2;
     313                 :            :             }
     314                 :    4996480 :           return NULL_TREE;
     315                 :            :         }
     316                 :            :     }
     317                 :            : 
     318                 :            :   /* Extract the LHS of the assignment so that it can be used as the current
     319                 :            :      definition of another variable.  */
     320                 :    1269420 :   lhs = (*slot)->lhs ();
     321                 :    1269420 :   if (elt)
     322                 :     488474 :     *elt = *slot;
     323                 :            : 
     324                 :            :   /* Valueize the result.  */
     325                 :    1269420 :   if (TREE_CODE (lhs) == SSA_NAME)
     326                 :            :     {
     327                 :    2047500 :       tree tem = SSA_NAME_VALUE (lhs);
     328                 :     859637 :       if (tem)
     329                 :      81718 :         lhs = tem;
     330                 :            :     }
     331                 :            : 
     332                 :    1269420 :   if (dump_file && (dump_flags & TDF_DETAILS))
     333                 :            :     {
     334                 :        228 :       fprintf (dump_file, "FIND: ");
     335                 :        228 :       print_generic_expr (dump_file, lhs);
     336                 :        228 :       fprintf (dump_file, "\n");
     337                 :            :     }
     338                 :            : 
     339                 :            :   return lhs;
     340                 :            : }
     341                 :            : 
     342                 :            : /* Enter condition equivalence P into the hash table.
     343                 :            : 
     344                 :            :    This indicates that a conditional expression has a known
     345                 :            :    boolean value.  */
     346                 :            : 
     347                 :            : void
     348                 :   52911000 : avail_exprs_stack::record_cond (cond_equivalence *p)
     349                 :            : {
     350                 :   52911000 :   class expr_hash_elt *element = new expr_hash_elt (&p->cond, p->value);
     351                 :   52911000 :   expr_hash_elt **slot;
     352                 :            : 
     353                 :   52911000 :   slot = m_avail_exprs->find_slot_with_hash (element, element->hash (), INSERT);
     354                 :   52911000 :   if (*slot == NULL)
     355                 :            :     {
     356                 :   52466900 :       *slot = element;
     357                 :   52466900 :       record_expr (element, NULL, '1');
     358                 :            :     }
     359                 :            :   else
     360                 :     444093 :     delete element;
     361                 :   52911000 : }
     362                 :            : 
     363                 :            : /* Generate a hash value for a pair of expressions.  This can be used
     364                 :            :    iteratively by passing a previous result in HSTATE.
     365                 :            : 
     366                 :            :    The same hash value is always returned for a given pair of expressions,
     367                 :            :    regardless of the order in which they are presented.  This is useful in
     368                 :            :    hashing the operands of commutative functions.  */
     369                 :            : 
     370                 :            : namespace inchash
     371                 :            : {
     372                 :            : 
     373                 :            : static void
     374                 :   54301000 : add_expr_commutative (const_tree t1, const_tree t2, hash &hstate)
     375                 :            : {
     376                 :   54301000 :   hash one, two;
     377                 :            : 
     378                 :   54301000 :   inchash::add_expr (t1, one);
     379                 :   54301000 :   inchash::add_expr (t2, two);
     380                 :   54301000 :   hstate.add_commutative (one, two);
     381                 :   54301000 : }
     382                 :            : 
     383                 :            : /* Compute a hash value for a hashable_expr value EXPR and a
     384                 :            :    previously accumulated hash value VAL.  If two hashable_expr
     385                 :            :    values compare equal with hashable_expr_equal_p, they must
     386                 :            :    hash to the same value, given an identical value of VAL.
     387                 :            :    The logic is intended to follow inchash::add_expr in tree.c.  */
     388                 :            : 
     389                 :            : static void
     390                 :  119315000 : add_hashable_expr (const struct hashable_expr *expr, hash &hstate)
     391                 :            : {
     392                 :  119315000 :   switch (expr->kind)
     393                 :            :     {
     394                 :   15910800 :     case EXPR_SINGLE:
     395                 :   15910800 :       inchash::add_expr (expr->ops.single.rhs, hstate);
     396                 :   15910800 :       break;
     397                 :            : 
     398                 :    6753540 :     case EXPR_UNARY:
     399                 :    6753540 :       hstate.add_object (expr->ops.unary.op);
     400                 :            : 
     401                 :            :       /* Make sure to include signedness in the hash computation.
     402                 :            :          Don't hash the type, that can lead to having nodes which
     403                 :            :          compare equal according to operand_equal_p, but which
     404                 :            :          have different hash codes.  */
     405                 :    6753540 :       if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
     406                 :     841174 :           || expr->ops.unary.op == NON_LVALUE_EXPR)
     407                 :    5912370 :         hstate.add_int (TYPE_UNSIGNED (expr->type));
     408                 :            : 
     409                 :    6753540 :       inchash::add_expr (expr->ops.unary.opnd, hstate);
     410                 :    6753540 :       break;
     411                 :            : 
     412                 :   88389000 :     case EXPR_BINARY:
     413                 :   88389000 :       hstate.add_object (expr->ops.binary.op);
     414                 :   88389000 :       if (commutative_tree_code (expr->ops.binary.op))
     415                 :   54300900 :         inchash::add_expr_commutative (expr->ops.binary.opnd0,
     416                 :   54300900 :                                           expr->ops.binary.opnd1, hstate);
     417                 :            :       else
     418                 :            :         {
     419                 :   34088100 :           inchash::add_expr (expr->ops.binary.opnd0, hstate);
     420                 :   34088100 :           inchash::add_expr (expr->ops.binary.opnd1, hstate);
     421                 :            :         }
     422                 :            :       break;
     423                 :            : 
     424                 :     133203 :     case EXPR_TERNARY:
     425                 :     133203 :       hstate.add_object (expr->ops.ternary.op);
     426                 :     133203 :       if (commutative_ternary_tree_code (expr->ops.ternary.op))
     427                 :         92 :         inchash::add_expr_commutative (expr->ops.ternary.opnd0,
     428                 :         92 :                                           expr->ops.ternary.opnd1, hstate);
     429                 :            :       else
     430                 :            :         {
     431                 :     133111 :           inchash::add_expr (expr->ops.ternary.opnd0, hstate);
     432                 :     133111 :           inchash::add_expr (expr->ops.ternary.opnd1, hstate);
     433                 :            :         }
     434                 :     133203 :       inchash::add_expr (expr->ops.ternary.opnd2, hstate);
     435                 :     133203 :       break;
     436                 :            : 
     437                 :    2917480 :     case EXPR_CALL:
     438                 :    2917480 :       {
     439                 :    2917480 :         size_t i;
     440                 :    2917480 :         enum tree_code code = CALL_EXPR;
     441                 :    2917480 :         gcall *fn_from;
     442                 :            : 
     443                 :    2917480 :         hstate.add_object (code);
     444                 :    2917480 :         fn_from = expr->ops.call.fn_from;
     445                 :    2917480 :         if (gimple_call_internal_p (fn_from))
     446                 :     152825 :           hstate.merge_hash ((hashval_t) gimple_call_internal_fn (fn_from));
     447                 :            :         else
     448                 :    2764650 :           inchash::add_expr (gimple_call_fn (fn_from), hstate);
     449                 :    7943070 :         for (i = 0; i < expr->ops.call.nargs; i++)
     450                 :    5025600 :           inchash::add_expr (expr->ops.call.args[i], hstate);
     451                 :            :       }
     452                 :    2917480 :       break;
     453                 :            : 
     454                 :            :     case EXPR_PHI:
     455                 :            :       {
     456                 :            :         size_t i;
     457                 :            : 
     458                 :   18263500 :         for (i = 0; i < expr->ops.phi.nargs; i++)
     459                 :   13052500 :           inchash::add_expr (expr->ops.phi.args[i], hstate);
     460                 :            :       }
     461                 :            :       break;
     462                 :            : 
     463                 :          0 :     default:
     464                 :          0 :       gcc_unreachable ();
     465                 :            :     }
     466                 :  119315000 : }
     467                 :            : 
     468                 :            : }
     469                 :            : 
     470                 :            : /* Hashing and equality functions.  We compute a value number for expressions
     471                 :            :    using the code of the expression and the SSA numbers of its operands.  */
     472                 :            : 
     473                 :            : static hashval_t
     474                 :  150684000 : avail_expr_hash (class expr_hash_elt *p)
     475                 :            : {
     476                 :  150684000 :   const struct hashable_expr *expr = p->expr ();
     477                 :  150684000 :   inchash::hash hstate;
     478                 :            : 
     479                 :  150684000 :   if (expr->kind == EXPR_SINGLE)
     480                 :            :     {
     481                 :            :       /* T could potentially be a switch index or a goto dest.  */
     482                 :   47279700 :       tree t = expr->ops.single.rhs;
     483                 :   47279700 :       if (TREE_CODE (t) == MEM_REF || handled_component_p (t))
     484                 :            :         {
     485                 :            :           /* Make equivalent statements of both these kinds hash together.
     486                 :            :              Dealing with both MEM_REF and ARRAY_REF allows us not to care
     487                 :            :              about equivalence with other statements not considered here.  */
     488                 :   32341700 :           bool reverse;
     489                 :   32341700 :           poly_int64 offset, size, max_size;
     490                 :   32341700 :           tree base = get_ref_base_and_extent (t, &offset, &size, &max_size,
     491                 :            :                                                &reverse);
     492                 :            :           /* Strictly, we could try to normalize variable-sized accesses too,
     493                 :            :             but here we just deal with the common case.  */
     494                 :   32341700 :           if (known_size_p (max_size)
     495                 :   32341700 :               && known_eq (size, max_size))
     496                 :            :             {
     497                 :   31368900 :               enum tree_code code = MEM_REF;
     498                 :   31368900 :               hstate.add_object (code);
     499                 :   31368900 :               inchash::add_expr (base, hstate,
     500                 :   31368900 :                                  TREE_CODE (base) == MEM_REF 
     501                 :            :                                  ? OEP_ADDRESS_OF : 0);
     502                 :   31368900 :               hstate.add_object (offset);
     503                 :   31368900 :               hstate.add_object (size);
     504                 :   31368900 :               return hstate.end ();
     505                 :            :             }
     506                 :            :         }
     507                 :            :     }
     508                 :            : 
     509                 :  119315000 :   inchash::add_hashable_expr (expr, hstate);
     510                 :            : 
     511                 :  119315000 :   return hstate.end ();
     512                 :            : }
     513                 :            : 
     514                 :            : /* Compares trees T0 and T1 to see if they are MEM_REF or ARRAY_REFs equivalent
     515                 :            :    to each other.  (That is, they return the value of the same bit of memory.)
     516                 :            : 
     517                 :            :    Return TRUE if the two are so equivalent; FALSE if not (which could still
     518                 :            :    mean the two are equivalent by other means).  */
     519                 :            : 
     520                 :            : static bool
     521                 :    5712120 : equal_mem_array_ref_p (tree t0, tree t1)
     522                 :            : {
     523                 :    5712120 :   if (TREE_CODE (t0) != MEM_REF && ! handled_component_p (t0))
     524                 :            :     return false;
     525                 :    4982610 :   if (TREE_CODE (t1) != MEM_REF && ! handled_component_p (t1))
     526                 :            :     return false;
     527                 :            : 
     528                 :    4982610 :   if (!types_compatible_p (TREE_TYPE (t0), TREE_TYPE (t1)))
     529                 :            :     return false;
     530                 :    4980640 :   bool rev0;
     531                 :    4980640 :   poly_int64 off0, sz0, max0;
     532                 :    4980640 :   tree base0 = get_ref_base_and_extent (t0, &off0, &sz0, &max0, &rev0);
     533                 :    4980640 :   if (!known_size_p (max0)
     534                 :    4980640 :       || maybe_ne (sz0, max0))
     535                 :            :     return false;
     536                 :            : 
     537                 :    4864730 :   bool rev1;
     538                 :    4864730 :   poly_int64 off1, sz1, max1;
     539                 :    4864730 :   tree base1 = get_ref_base_and_extent (t1, &off1, &sz1, &max1, &rev1);
     540                 :    4864730 :   if (!known_size_p (max1)
     541                 :    4864730 :       || maybe_ne (sz1, max1))
     542                 :            :     return false;
     543                 :            : 
     544                 :    4864730 :   if (rev0 != rev1 || maybe_ne (sz0, sz1) || maybe_ne (off0, off1))
     545                 :            :     return false;
     546                 :            : 
     547                 :    4864720 :   return operand_equal_p (base0, base1,
     548                 :    4864720 :                           (TREE_CODE (base0) == MEM_REF
     549                 :    4864720 :                            || TREE_CODE (base0) == TARGET_MEM_REF)
     550                 :    1755420 :                           && (TREE_CODE (base1) == MEM_REF
     551                 :    1755420 :                               || TREE_CODE (base1) == TARGET_MEM_REF)
     552                 :    4864720 :                           ? OEP_ADDRESS_OF : 0);
     553                 :            : }
     554                 :            : 
     555                 :            : /* Compare two hashable_expr structures for equivalence.  They are
     556                 :            :    considered equivalent when the expressions they denote must
     557                 :            :    necessarily be equal.  The logic is intended to follow that of
     558                 :            :    operand_equal_p in fold-const.c */
     559                 :            : 
     560                 :            : static bool
     561                 :    6906590 : hashable_expr_equal_p (const struct hashable_expr *expr0,
     562                 :            :                        const struct hashable_expr *expr1)
     563                 :            : {
     564                 :    6906590 :   tree type0 = expr0->type;
     565                 :    6906590 :   tree type1 = expr1->type;
     566                 :            : 
     567                 :            :   /* If either type is NULL, there is nothing to check.  */
     568                 :    6906590 :   if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
     569                 :            :     return false;
     570                 :            : 
     571                 :            :   /* If both types don't have the same signedness, precision, and mode,
     572                 :            :      then we can't consider  them equal.  */
     573                 :    6906590 :   if (type0 != type1
     574                 :    6906590 :       && (TREE_CODE (type0) == ERROR_MARK
     575                 :     701661 :           || TREE_CODE (type1) == ERROR_MARK
     576                 :     701661 :           || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
     577                 :     688541 :           || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
     578                 :    1246940 :           || TYPE_MODE (type0) != TYPE_MODE (type1)))
     579                 :     137181 :     return false;
     580                 :            : 
     581                 :    6769400 :   if (expr0->kind != expr1->kind)
     582                 :            :     return false;
     583                 :            : 
     584                 :    6769400 :   switch (expr0->kind)
     585                 :            :     {
     586                 :    5712120 :     case EXPR_SINGLE:
     587                 :    5712120 :       return equal_mem_array_ref_p (expr0->ops.single.rhs,
     588                 :    5712120 :                                     expr1->ops.single.rhs)
     589                 :    6559890 :              || operand_equal_p (expr0->ops.single.rhs,
     590                 :     847772 :                                  expr1->ops.single.rhs, 0);
     591                 :     110314 :     case EXPR_UNARY:
     592                 :     110314 :       if (expr0->ops.unary.op != expr1->ops.unary.op)
     593                 :            :         return false;
     594                 :            : 
     595                 :       3781 :       if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
     596                 :       3781 :            || expr0->ops.unary.op == NON_LVALUE_EXPR)
     597                 :     110314 :           && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
     598                 :            :         return false;
     599                 :            : 
     600                 :     110314 :       return operand_equal_p (expr0->ops.unary.opnd,
     601                 :     110314 :                               expr1->ops.unary.opnd, 0);
     602                 :            : 
     603                 :     850302 :     case EXPR_BINARY:
     604                 :     850302 :       if (expr0->ops.binary.op != expr1->ops.binary.op)
     605                 :            :         return false;
     606                 :            : 
     607                 :     850302 :       if (operand_equal_p (expr0->ops.binary.opnd0,
     608                 :     850302 :                            expr1->ops.binary.opnd0, 0)
     609                 :    1682560 :           && operand_equal_p (expr0->ops.binary.opnd1,
     610                 :     832256 :                               expr1->ops.binary.opnd1, 0))
     611                 :            :         return true;
     612                 :            : 
     613                 :            :       /* For commutative ops, allow the other order.  */
     614                 :      19680 :       return (commutative_tree_code (expr0->ops.binary.op)
     615                 :      18436 :               && operand_equal_p (expr0->ops.binary.opnd0,
     616                 :      18436 :                                   expr1->ops.binary.opnd1, 0)
     617                 :      31987 :               && operand_equal_p (expr0->ops.binary.opnd1,
     618                 :      12307 :                                   expr1->ops.binary.opnd0, 0));
     619                 :            : 
     620                 :        123 :     case EXPR_TERNARY:
     621                 :        123 :       if (expr0->ops.ternary.op != expr1->ops.ternary.op
     622                 :        246 :           || !operand_equal_p (expr0->ops.ternary.opnd2,
     623                 :        123 :                                expr1->ops.ternary.opnd2, 0))
     624                 :          0 :         return false;
     625                 :            : 
     626                 :            :       /* BIT_INSERT_EXPR has an implict operand as the type precision
     627                 :            :          of op1.  Need to check to make sure they are the same.  */
     628                 :        123 :       if (expr0->ops.ternary.op == BIT_INSERT_EXPR
     629                 :          4 :           && TREE_CODE (expr0->ops.ternary.opnd1) == INTEGER_CST
     630                 :          4 :           && TREE_CODE (expr1->ops.ternary.opnd1) == INTEGER_CST
     631                 :        127 :           && TYPE_PRECISION (TREE_TYPE (expr0->ops.ternary.opnd1))
     632                 :          4 :               != TYPE_PRECISION (TREE_TYPE (expr1->ops.ternary.opnd1)))
     633                 :            :         return false;
     634                 :            : 
     635                 :        123 :       if (operand_equal_p (expr0->ops.ternary.opnd0,
     636                 :        123 :                            expr1->ops.ternary.opnd0, 0)
     637                 :        246 :           && operand_equal_p (expr0->ops.ternary.opnd1,
     638                 :        123 :                               expr1->ops.ternary.opnd1, 0))
     639                 :            :         return true;
     640                 :            : 
     641                 :            :       /* For commutative ops, allow the other order.  */
     642                 :          0 :       return (commutative_ternary_tree_code (expr0->ops.ternary.op)
     643                 :          0 :               && operand_equal_p (expr0->ops.ternary.opnd0,
     644                 :          0 :                                   expr1->ops.ternary.opnd1, 0)
     645                 :          0 :               && operand_equal_p (expr0->ops.ternary.opnd1,
     646                 :          0 :                                   expr1->ops.ternary.opnd0, 0));
     647                 :            : 
     648                 :      91427 :     case EXPR_CALL:
     649                 :      91427 :       {
     650                 :      91427 :         size_t i;
     651                 :            : 
     652                 :            :         /* If the calls are to different functions, then they
     653                 :            :            clearly cannot be equal.  */
     654                 :      91427 :         if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
     655                 :      91427 :                                         expr1->ops.call.fn_from))
     656                 :            :           return false;
     657                 :            : 
     658                 :      90806 :         if (! expr0->ops.call.pure)
     659                 :            :           return false;
     660                 :            : 
     661                 :      90806 :         if (expr0->ops.call.nargs !=  expr1->ops.call.nargs)
     662                 :            :           return false;
     663                 :            : 
     664                 :     240395 :         for (i = 0; i < expr0->ops.call.nargs; i++)
     665                 :     149611 :           if (! operand_equal_p (expr0->ops.call.args[i],
     666                 :     149611 :                                  expr1->ops.call.args[i], 0))
     667                 :            :             return false;
     668                 :            : 
     669                 :      90784 :         if (stmt_could_throw_p (cfun, expr0->ops.call.fn_from))
     670                 :            :           {
     671                 :         24 :             int lp0 = lookup_stmt_eh_lp (expr0->ops.call.fn_from);
     672                 :         24 :             int lp1 = lookup_stmt_eh_lp (expr1->ops.call.fn_from);
     673                 :         24 :             if ((lp0 > 0 || lp1 > 0) && lp0 != lp1)
     674                 :          0 :               return false;
     675                 :            :           }
     676                 :            : 
     677                 :            :         return true;
     678                 :            :       }
     679                 :            : 
     680                 :       5117 :     case EXPR_PHI:
     681                 :       5117 :       {
     682                 :       5117 :         size_t i;
     683                 :            : 
     684                 :       5117 :         if (expr0->ops.phi.nargs !=  expr1->ops.phi.nargs)
     685                 :            :           return false;
     686                 :            : 
     687                 :      13142 :         for (i = 0; i < expr0->ops.phi.nargs; i++)
     688                 :       8087 :           if (! operand_equal_p (expr0->ops.phi.args[i],
     689                 :       8087 :                                  expr1->ops.phi.args[i], 0))
     690                 :            :             return false;
     691                 :            : 
     692                 :            :         return true;
     693                 :            :       }
     694                 :            : 
     695                 :          0 :     default:
     696                 :          0 :       gcc_unreachable ();
     697                 :            :     }
     698                 :            : }
     699                 :            : 
     700                 :            : /* Given a statement STMT, construct a hash table element.  */
     701                 :            : 
     702                 :   96459800 : expr_hash_elt::expr_hash_elt (gimple *stmt, tree orig_lhs)
     703                 :            : {
     704                 :   96459800 :   enum gimple_code code = gimple_code (stmt);
     705                 :   96459800 :   struct hashable_expr *expr = this->expr ();
     706                 :            : 
     707                 :   96459800 :   if (code == GIMPLE_ASSIGN)
     708                 :            :     {
     709                 :   69992700 :       enum tree_code subcode = gimple_assign_rhs_code (stmt);
     710                 :            : 
     711                 :   69992700 :       switch (get_gimple_rhs_class (subcode))
     712                 :            :         {
     713                 :   47233400 :         case GIMPLE_SINGLE_RHS:
     714                 :   47233400 :           expr->kind = EXPR_SINGLE;
     715                 :   47233400 :           expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
     716                 :   47233400 :           expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
     717                 :   47233400 :           break;
     718                 :    6663180 :         case GIMPLE_UNARY_RHS:
     719                 :    6663180 :           expr->kind = EXPR_UNARY;
     720                 :    6663180 :           expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
     721                 :    6663180 :           if (CONVERT_EXPR_CODE_P (subcode))
     722                 :    5912370 :             subcode = NOP_EXPR;
     723                 :    6663180 :           expr->ops.unary.op = subcode;
     724                 :    6663180 :           expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
     725                 :    6663180 :           break;
     726                 :   15962900 :         case GIMPLE_BINARY_RHS:
     727                 :   15962900 :           expr->kind = EXPR_BINARY;
     728                 :   15962900 :           expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
     729                 :   15962900 :           expr->ops.binary.op = subcode;
     730                 :   15962900 :           expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
     731                 :   15962900 :           expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
     732                 :   15962900 :           break;
     733                 :     133203 :         case GIMPLE_TERNARY_RHS:
     734                 :     133203 :           expr->kind = EXPR_TERNARY;
     735                 :     133203 :           expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
     736                 :     133203 :           expr->ops.ternary.op = subcode;
     737                 :     133203 :           expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
     738                 :     133203 :           expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
     739                 :     133203 :           expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
     740                 :     133203 :           break;
     741                 :          0 :         default:
     742                 :          0 :           gcc_unreachable ();
     743                 :            :         }
     744                 :            :     }
     745                 :   26467000 :   else if (code == GIMPLE_COND)
     746                 :            :     {
     747                 :   18292300 :       expr->type = boolean_type_node;
     748                 :   18292300 :       expr->kind = EXPR_BINARY;
     749                 :   18292300 :       expr->ops.binary.op = gimple_cond_code (stmt);
     750                 :   18292300 :       expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
     751                 :   18292300 :       expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
     752                 :            :     }
     753                 :    8174790 :   else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
     754                 :            :     {
     755                 :    2917480 :       size_t nargs = gimple_call_num_args (call_stmt);
     756                 :    2917480 :       size_t i;
     757                 :            : 
     758                 :    2917480 :       gcc_assert (gimple_call_lhs (call_stmt));
     759                 :            : 
     760                 :    2917480 :       expr->type = TREE_TYPE (gimple_call_lhs (call_stmt));
     761                 :    2917480 :       expr->kind = EXPR_CALL;
     762                 :    2917480 :       expr->ops.call.fn_from = call_stmt;
     763                 :            : 
     764                 :    2917480 :       if (gimple_call_flags (call_stmt) & (ECF_CONST | ECF_PURE))
     765                 :     928751 :         expr->ops.call.pure = true;
     766                 :            :       else
     767                 :    1988730 :         expr->ops.call.pure = false;
     768                 :            : 
     769                 :    2917480 :       expr->ops.call.nargs = nargs;
     770                 :    2917480 :       expr->ops.call.args = XCNEWVEC (tree, nargs);
     771                 :    7943070 :       for (i = 0; i < nargs; i++)
     772                 :    5025600 :         expr->ops.call.args[i] = gimple_call_arg (call_stmt, i);
     773                 :            :     }
     774                 :    5257310 :   else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
     775                 :            :     {
     776                 :      45846 :       expr->type = TREE_TYPE (gimple_switch_index (swtch_stmt));
     777                 :      45846 :       expr->kind = EXPR_SINGLE;
     778                 :      45846 :       expr->ops.single.rhs = gimple_switch_index (swtch_stmt);
     779                 :            :     }
     780                 :    5211470 :   else if (code == GIMPLE_GOTO)
     781                 :            :     {
     782                 :        423 :       expr->type = TREE_TYPE (gimple_goto_dest (stmt));
     783                 :        423 :       expr->kind = EXPR_SINGLE;
     784                 :        423 :       expr->ops.single.rhs = gimple_goto_dest (stmt);
     785                 :            :     }
     786                 :    5211040 :   else if (code == GIMPLE_PHI)
     787                 :            :     {
     788                 :    5211040 :       size_t nargs = gimple_phi_num_args (stmt);
     789                 :    5211040 :       size_t i;
     790                 :            : 
     791                 :    5211040 :       expr->type = TREE_TYPE (gimple_phi_result (stmt));
     792                 :    5211040 :       expr->kind = EXPR_PHI;
     793                 :    5211040 :       expr->ops.phi.nargs = nargs;
     794                 :    5211040 :       expr->ops.phi.args = XCNEWVEC (tree, nargs);
     795                 :   18263500 :       for (i = 0; i < nargs; i++)
     796                 :   13052500 :         expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
     797                 :            :     }
     798                 :            :   else
     799                 :          0 :     gcc_unreachable ();
     800                 :            : 
     801                 :   96459800 :   m_lhs = orig_lhs;
     802                 :   96459800 :   m_vop = gimple_vuse (stmt);
     803                 :   96459800 :   m_hash = avail_expr_hash (this);
     804                 :   96459800 :   m_stamp = this;
     805                 :   96459800 : }
     806                 :            : 
     807                 :            : /* Given a hashable_expr expression ORIG and an ORIG_LHS,
     808                 :            :    construct a hash table element.  */
     809                 :            : 
     810                 :   54224200 : expr_hash_elt::expr_hash_elt (struct hashable_expr *orig, tree orig_lhs)
     811                 :            : {
     812                 :   54224200 :   m_expr = *orig;
     813                 :   54224200 :   m_lhs = orig_lhs;
     814                 :   54224200 :   m_vop = NULL_TREE;
     815                 :   54224200 :   m_hash = avail_expr_hash (this);
     816                 :   54224200 :   m_stamp = this;
     817                 :   54224200 : }
     818                 :            : 
     819                 :            : /* Copy constructor for a hash table element.  */
     820                 :            : 
     821                 :   59955100 : expr_hash_elt::expr_hash_elt (class expr_hash_elt &old_elt)
     822                 :            : {
     823                 :   59955100 :   m_expr = old_elt.m_expr;
     824                 :   59955100 :   m_lhs = old_elt.m_lhs;
     825                 :   59955100 :   m_vop = old_elt.m_vop;
     826                 :   59955100 :   m_hash = old_elt.m_hash;
     827                 :   59955100 :   m_stamp = this;
     828                 :            : 
     829                 :            :   /* Now deep copy the malloc'd space for CALL and PHI args.  */
     830                 :   59955100 :   if (old_elt.m_expr.kind == EXPR_CALL)
     831                 :            :     {
     832                 :    1151880 :       size_t nargs = old_elt.m_expr.ops.call.nargs;
     833                 :    1151880 :       size_t i;
     834                 :            : 
     835                 :    1151880 :       m_expr.ops.call.args = XCNEWVEC (tree, nargs);
     836                 :    3445300 :       for (i = 0; i < nargs; i++)
     837                 :    2293420 :         m_expr.ops.call.args[i] = old_elt.m_expr.ops.call.args[i];
     838                 :            :     }
     839                 :   58803200 :   else if (old_elt.m_expr.kind == EXPR_PHI)
     840                 :            :     {
     841                 :   10400300 :       size_t nargs = old_elt.m_expr.ops.phi.nargs;
     842                 :   10400300 :       size_t i;
     843                 :            : 
     844                 :   10400300 :       m_expr.ops.phi.args = XCNEWVEC (tree, nargs);
     845                 :   36457600 :       for (i = 0; i < nargs; i++)
     846                 :   26057300 :         m_expr.ops.phi.args[i] = old_elt.m_expr.ops.phi.args[i];
     847                 :            :     }
     848                 :   59955100 : }
     849                 :            : 
     850                 :            : /* Calls and PHIs have a variable number of arguments that are allocated
     851                 :            :    on the heap.  Thus we have to have a special dtor to release them.  */
     852                 :            : 
     853                 :  421278000 : expr_hash_elt::~expr_hash_elt ()
     854                 :            : {
     855                 :  210639000 :   if (m_expr.kind == EXPR_CALL)
     856                 :    4069360 :     free (m_expr.ops.call.args);
     857                 :  206570000 :   else if (m_expr.kind == EXPR_PHI)
     858                 :   15611300 :     free (m_expr.ops.phi.args);
     859                 :  210639000 : }
     860                 :            : 
     861                 :            : /* Print a diagnostic dump of an expression hash table entry.  */
     862                 :            : 
     863                 :            : void
     864                 :      10982 : expr_hash_elt::print (FILE *stream)
     865                 :            : {
     866                 :      10982 :   fprintf (stream, "STMT ");
     867                 :            : 
     868                 :      10982 :   if (m_lhs)
     869                 :            :     {
     870                 :      10056 :       print_generic_expr (stream, m_lhs);
     871                 :      10056 :       fprintf (stream, " = ");
     872                 :            :     }
     873                 :            : 
     874                 :      10982 :   switch (m_expr.kind)
     875                 :            :     {
     876                 :       2560 :       case EXPR_SINGLE:
     877                 :       2560 :         print_generic_expr (stream, m_expr.ops.single.rhs);
     878                 :       2560 :         break;
     879                 :            : 
     880                 :        333 :       case EXPR_UNARY:
     881                 :        333 :         fprintf (stream, "%s ", get_tree_code_name (m_expr.ops.unary.op));
     882                 :        333 :         print_generic_expr (stream, m_expr.ops.unary.opnd);
     883                 :        333 :         break;
     884                 :            : 
     885                 :       7309 :       case EXPR_BINARY:
     886                 :       7309 :         print_generic_expr (stream, m_expr.ops.binary.opnd0);
     887                 :       7309 :         fprintf (stream, " %s ", get_tree_code_name (m_expr.ops.binary.op));
     888                 :       7309 :         print_generic_expr (stream, m_expr.ops.binary.opnd1);
     889                 :       7309 :         break;
     890                 :            : 
     891                 :          0 :       case EXPR_TERNARY:
     892                 :          0 :         fprintf (stream, " %s <", get_tree_code_name (m_expr.ops.ternary.op));
     893                 :          0 :         print_generic_expr (stream, m_expr.ops.ternary.opnd0);
     894                 :          0 :         fputs (", ", stream);
     895                 :          0 :         print_generic_expr (stream, m_expr.ops.ternary.opnd1);
     896                 :          0 :         fputs (", ", stream);
     897                 :          0 :         print_generic_expr (stream, m_expr.ops.ternary.opnd2);
     898                 :          0 :         fputs (">", stream);
     899                 :          0 :         break;
     900                 :            : 
     901                 :         23 :       case EXPR_CALL:
     902                 :         23 :         {
     903                 :         23 :           size_t i;
     904                 :         23 :           size_t nargs = m_expr.ops.call.nargs;
     905                 :         23 :           gcall *fn_from;
     906                 :            : 
     907                 :         23 :           fn_from = m_expr.ops.call.fn_from;
     908                 :         23 :           if (gimple_call_internal_p (fn_from))
     909                 :          0 :             fprintf (stream, ".%s",
     910                 :            :                      internal_fn_name (gimple_call_internal_fn (fn_from)));
     911                 :            :           else
     912                 :         23 :             print_generic_expr (stream, gimple_call_fn (fn_from));
     913                 :         23 :           fprintf (stream, " (");
     914                 :         58 :           for (i = 0; i < nargs; i++)
     915                 :            :             {
     916                 :         35 :               print_generic_expr (stream, m_expr.ops.call.args[i]);
     917                 :         35 :               if (i + 1 < nargs)
     918                 :         12 :                 fprintf (stream, ", ");
     919                 :            :             }
     920                 :         23 :           fprintf (stream, ")");
     921                 :            :         }
     922                 :         23 :         break;
     923                 :            : 
     924                 :        757 :       case EXPR_PHI:
     925                 :        757 :         {
     926                 :        757 :           size_t i;
     927                 :        757 :           size_t nargs = m_expr.ops.phi.nargs;
     928                 :            : 
     929                 :        757 :           fprintf (stream, "PHI <");
     930                 :       2481 :           for (i = 0; i < nargs; i++)
     931                 :            :             {
     932                 :       1724 :               print_generic_expr (stream, m_expr.ops.phi.args[i]);
     933                 :       1724 :               if (i + 1 < nargs)
     934                 :        967 :                 fprintf (stream, ", ");
     935                 :            :             }
     936                 :        757 :           fprintf (stream, ">");
     937                 :            :         }
     938                 :        757 :         break;
     939                 :            :     }
     940                 :            : 
     941                 :      10982 :   if (m_vop)
     942                 :            :     {
     943                 :       2372 :       fprintf (stream, " with ");
     944                 :       2372 :       print_generic_expr (stream, m_vop);
     945                 :            :     }
     946                 :            : 
     947                 :      10982 :   fprintf (stream, "\n");
     948                 :      10982 : }
     949                 :            : 
     950                 :            : /* Pop entries off the stack until we hit the NULL marker.
     951                 :            :    For each entry popped, use the SRC/DEST pair to restore
     952                 :            :    SRC to its prior value.  */
     953                 :            : 
     954                 :            : void
     955                 :   58921600 : const_and_copies::pop_to_marker (void)
     956                 :            : {
     957                 :   98263500 :   while (m_stack.length () > 0)
     958                 :            :     {
     959                 :   98263500 :       tree prev_value, dest;
     960                 :            : 
     961                 :   98263500 :       dest = m_stack.pop ();
     962                 :            : 
     963                 :            :       /* A NULL value indicates we should stop unwinding, otherwise
     964                 :            :          pop off the next entry as they're recorded in pairs.  */
     965                 :   98263500 :       if (dest == NULL)
     966                 :            :         break;
     967                 :            : 
     968                 :   39341900 :       if (dump_file && (dump_flags & TDF_DETAILS))
     969                 :            :         {
     970                 :       1859 :           fprintf (dump_file, "<<<< COPY ");
     971                 :       1859 :           print_generic_expr (dump_file, dest);
     972                 :       1859 :           fprintf (dump_file, " = ");
     973                 :       3718 :           print_generic_expr (dump_file, SSA_NAME_VALUE (dest));
     974                 :       1859 :           fprintf (dump_file, "\n");
     975                 :            :         }
     976                 :            : 
     977                 :   39341900 :       prev_value = m_stack.pop ();
     978                 :   39341900 :       set_ssa_name_value (dest, prev_value);
     979                 :            :     }
     980                 :   58921600 : }
     981                 :            : 
     982                 :            : /* Record that X has the value Y and that X's previous value is PREV_X. 
     983                 :            : 
     984                 :            :    This variant does not follow the value chain for Y.  */
     985                 :            : 
     986                 :            : void
     987                 :   39341900 : const_and_copies::record_const_or_copy_raw (tree x, tree y, tree prev_x)
     988                 :            : {
     989                 :   39341900 :   if (dump_file && (dump_flags & TDF_DETAILS))
     990                 :            :     {
     991                 :       1859 :       fprintf (dump_file, "0>>> COPY ");
     992                 :       1859 :       print_generic_expr (dump_file, x);
     993                 :       1859 :       fprintf (dump_file, " = ");
     994                 :       1859 :       print_generic_expr (dump_file, y);
     995                 :       1859 :       fprintf (dump_file, "\n");
     996                 :            :     }
     997                 :            : 
     998                 :   39341900 :   set_ssa_name_value (x, y);
     999                 :   39341900 :   m_stack.reserve (2);
    1000                 :   39341900 :   m_stack.quick_push (prev_x);
    1001                 :   39341900 :   m_stack.quick_push (x);
    1002                 :   39341900 : }
    1003                 :            : 
    1004                 :            : /* Record that X has the value Y.  */
    1005                 :            : 
    1006                 :            : void
    1007                 :   30269700 : const_and_copies::record_const_or_copy (tree x, tree y)
    1008                 :            : {
    1009                 :   60539300 :   record_const_or_copy (x, y, SSA_NAME_VALUE (x));
    1010                 :   30269700 : }
    1011                 :            : 
    1012                 :            : /* Record that X has the value Y and that X's previous value is PREV_X. 
    1013                 :            : 
    1014                 :            :    This variant follow's Y value chain.  */
    1015                 :            : 
    1016                 :            : void
    1017                 :   39341900 : const_and_copies::record_const_or_copy (tree x, tree y, tree prev_x)
    1018                 :            : {
    1019                 :            :   /* Y may be NULL if we are invalidating entries in the table.  */
    1020                 :   39341900 :   if (y && TREE_CODE (y) == SSA_NAME)
    1021                 :            :     {
    1022                 :   49378800 :       tree tmp = SSA_NAME_VALUE (y);
    1023                 :   22385100 :       y = tmp ? tmp : y;
    1024                 :            :     }
    1025                 :            : 
    1026                 :   39341900 :   record_const_or_copy_raw (x, y, prev_x);
    1027                 :   39341900 : }
    1028                 :            : 
    1029                 :            : bool
    1030                 :  186621000 : expr_elt_hasher::equal (const value_type &p1, const compare_type &p2)
    1031                 :            : {
    1032                 :  186621000 :   const struct hashable_expr *expr1 = p1->expr ();
    1033                 :  186621000 :   const class expr_hash_elt *stamp1 = p1->stamp ();
    1034                 :  186621000 :   const struct hashable_expr *expr2 = p2->expr ();
    1035                 :  186621000 :   const class expr_hash_elt *stamp2 = p2->stamp ();
    1036                 :            : 
    1037                 :            :   /* This case should apply only when removing entries from the table.  */
    1038                 :  186621000 :   if (stamp1 == stamp2)
    1039                 :            :     return true;
    1040                 :            : 
    1041                 :  102767000 :   if (p1->hash () != p2->hash ())
    1042                 :            :     return false;
    1043                 :            : 
    1044                 :            :   /* In case of a collision, both RHS have to be identical and have the
    1045                 :            :      same VUSE operands.  */
    1046                 :    6906590 :   if (hashable_expr_equal_p (expr1, expr2)
    1047                 :    6906590 :       && types_compatible_p (expr1->type, expr2->type))
    1048                 :    6722650 :     return true;
    1049                 :            : 
    1050                 :            :   return false;
    1051                 :            : }
    1052                 :            : 
    1053                 :            : /* Given a conditional expression COND as a tree, initialize
    1054                 :            :    a hashable_expr expression EXPR.  The conditional must be a
    1055                 :            :    comparison or logical negation.  A constant or a variable is
    1056                 :            :    not permitted.  */
    1057                 :            : 
    1058                 :            : void
    1059                 :   46533000 : initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
    1060                 :            : {
    1061                 :   46533000 :   expr->type = boolean_type_node;
    1062                 :            : 
    1063                 :   46533000 :   if (COMPARISON_CLASS_P (cond))
    1064                 :            :     {
    1065                 :   46396700 :       expr->kind = EXPR_BINARY;
    1066                 :   46396700 :       expr->ops.binary.op = TREE_CODE (cond);
    1067                 :   46396700 :       expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
    1068                 :   46396700 :       expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
    1069                 :            :     }
    1070                 :     136310 :   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
    1071                 :            :     {
    1072                 :     136310 :       expr->kind = EXPR_UNARY;
    1073                 :     136310 :       expr->ops.unary.op = TRUTH_NOT_EXPR;
    1074                 :     136310 :       expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
    1075                 :            :     }
    1076                 :            :   else
    1077                 :          0 :     gcc_unreachable ();
    1078                 :   46533000 : }
    1079                 :            : 
    1080                 :            : /* Build a cond_equivalence record indicating that the comparison
    1081                 :            :    CODE holds between operands OP0 and OP1 and push it to **P.  */
    1082                 :            : 
    1083                 :            : static void
    1084                 :   25378700 : build_and_record_new_cond (enum tree_code code,
    1085                 :            :                            tree op0, tree op1,
    1086                 :            :                            vec<cond_equivalence> *p,
    1087                 :            :                            bool val = true)
    1088                 :            : {
    1089                 :   25378700 :   cond_equivalence c;
    1090                 :   25378700 :   struct hashable_expr *cond = &c.cond;
    1091                 :            : 
    1092                 :   25378700 :   gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
    1093                 :            : 
    1094                 :   25378700 :   cond->type = boolean_type_node;
    1095                 :   25378700 :   cond->kind = EXPR_BINARY;
    1096                 :   25378700 :   cond->ops.binary.op = code;
    1097                 :   25378700 :   cond->ops.binary.opnd0 = op0;
    1098                 :   25378700 :   cond->ops.binary.opnd1 = op1;
    1099                 :            : 
    1100                 :   25378700 :   c.value = val ? boolean_true_node : boolean_false_node;
    1101                 :   25378700 :   p->safe_push (c);
    1102                 :   25378700 : }
    1103                 :            : 
    1104                 :            : /* Record that COND is true and INVERTED is false into the edge information
    1105                 :            :    structure.  Also record that any conditions dominated by COND are true
    1106                 :            :    as well.
    1107                 :            : 
    1108                 :            :    For example, if a < b is true, then a <= b must also be true.  */
    1109                 :            : 
    1110                 :            : void
    1111                 :   23505700 : record_conditions (vec<cond_equivalence> *p, tree cond, tree inverted)
    1112                 :            : {
    1113                 :   23505700 :   tree op0, op1;
    1114                 :   23505700 :   cond_equivalence c;
    1115                 :            : 
    1116                 :   23505700 :   if (!COMPARISON_CLASS_P (cond))
    1117                 :     239212 :     return;
    1118                 :            : 
    1119                 :   23266500 :   op0 = TREE_OPERAND (cond, 0);
    1120                 :   23266500 :   op1 = TREE_OPERAND (cond, 1);
    1121                 :            : 
    1122                 :   23266500 :   switch (TREE_CODE (cond))
    1123                 :            :     {
    1124                 :    3169820 :     case LT_EXPR:
    1125                 :    3169820 :     case GT_EXPR:
    1126                 :    3169820 :       if (FLOAT_TYPE_P (TREE_TYPE (op0)))
    1127                 :            :         {
    1128                 :      90193 :           build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
    1129                 :      90193 :           build_and_record_new_cond (LTGT_EXPR, op0, op1, p);
    1130                 :            :         }
    1131                 :            : 
    1132                 :    5223470 :       build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
    1133                 :            :                                   ? LE_EXPR : GE_EXPR),
    1134                 :            :                                  op0, op1, p);
    1135                 :    3169820 :       build_and_record_new_cond (NE_EXPR, op0, op1, p);
    1136                 :    3169820 :       build_and_record_new_cond (EQ_EXPR, op0, op1, p, false);
    1137                 :    3169820 :       break;
    1138                 :            : 
    1139                 :    3431160 :     case GE_EXPR:
    1140                 :    3431160 :     case LE_EXPR:
    1141                 :    3431160 :       if (FLOAT_TYPE_P (TREE_TYPE (op0)))
    1142                 :            :         {
    1143                 :      31710 :           build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
    1144                 :            :         }
    1145                 :            :       break;
    1146                 :            : 
    1147                 :    7547900 :     case EQ_EXPR:
    1148                 :    7547900 :       if (FLOAT_TYPE_P (TREE_TYPE (op0)))
    1149                 :            :         {
    1150                 :     427621 :           build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
    1151                 :            :         }
    1152                 :    7547900 :       build_and_record_new_cond (LE_EXPR, op0, op1, p);
    1153                 :    7547900 :       build_and_record_new_cond (GE_EXPR, op0, op1, p);
    1154                 :    7547900 :       break;
    1155                 :            : 
    1156                 :      19358 :     case UNORDERED_EXPR:
    1157                 :      19358 :       build_and_record_new_cond (NE_EXPR, op0, op1, p);
    1158                 :      19358 :       build_and_record_new_cond (UNLE_EXPR, op0, op1, p);
    1159                 :      19358 :       build_and_record_new_cond (UNGE_EXPR, op0, op1, p);
    1160                 :      19358 :       build_and_record_new_cond (UNEQ_EXPR, op0, op1, p);
    1161                 :      19358 :       build_and_record_new_cond (UNLT_EXPR, op0, op1, p);
    1162                 :      19358 :       build_and_record_new_cond (UNGT_EXPR, op0, op1, p);
    1163                 :      19358 :       break;
    1164                 :            : 
    1165                 :       7808 :     case UNLT_EXPR:
    1166                 :       7808 :     case UNGT_EXPR:
    1167                 :      12248 :       build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
    1168                 :            :                                   ? UNLE_EXPR : UNGE_EXPR),
    1169                 :            :                                  op0, op1, p);
    1170                 :       7808 :       build_and_record_new_cond (NE_EXPR, op0, op1, p);
    1171                 :       7808 :       break;
    1172                 :            : 
    1173                 :        962 :     case UNEQ_EXPR:
    1174                 :        962 :       build_and_record_new_cond (UNLE_EXPR, op0, op1, p);
    1175                 :        962 :       build_and_record_new_cond (UNGE_EXPR, op0, op1, p);
    1176                 :        962 :       break;
    1177                 :            : 
    1178                 :          8 :     case LTGT_EXPR:
    1179                 :          8 :       build_and_record_new_cond (NE_EXPR, op0, op1, p);
    1180                 :          8 :       build_and_record_new_cond (ORDERED_EXPR, op0, op1, p);
    1181                 :          8 :       break;
    1182                 :            : 
    1183                 :            :     default:
    1184                 :            :       break;
    1185                 :            :     }
    1186                 :            : 
    1187                 :            :   /* Now store the original true and false conditions into the first
    1188                 :            :      two slots.  */
    1189                 :   23266500 :   initialize_expr_from_cond (cond, &c.cond);
    1190                 :   23266500 :   c.value = boolean_true_node;
    1191                 :   23266500 :   p->safe_push (c);
    1192                 :            : 
    1193                 :            :   /* It is possible for INVERTED to be the negation of a comparison,
    1194                 :            :      and not a valid RHS or GIMPLE_COND condition.  This happens because
    1195                 :            :      invert_truthvalue may return such an expression when asked to invert
    1196                 :            :      a floating-point comparison.  These comparisons are not assumed to
    1197                 :            :      obey the trichotomy law.  */
    1198                 :   23266500 :   initialize_expr_from_cond (inverted, &c.cond);
    1199                 :   23266500 :   c.value = boolean_false_node;
    1200                 :   23266500 :   p->safe_push (c);
    1201                 :            : }

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.