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

           Branch data     Line data    Source code
       1                 :            : /* SSA Dominator optimizations for trees
       2                 :            :    Copyright (C) 2001-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Diego Novillo <dnovillo@redhat.com>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify
       8                 :            : it under the terms of the GNU General Public License as published by
       9                 :            : the Free Software Foundation; either version 3, or (at your option)
      10                 :            : any later version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful,
      13                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            : GNU General Public License for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "gimple.h"
      27                 :            : #include "tree-pass.h"
      28                 :            : #include "ssa.h"
      29                 :            : #include "gimple-pretty-print.h"
      30                 :            : #include "fold-const.h"
      31                 :            : #include "cfganal.h"
      32                 :            : #include "cfgloop.h"
      33                 :            : #include "gimple-fold.h"
      34                 :            : #include "tree-eh.h"
      35                 :            : #include "tree-inline.h"
      36                 :            : #include "gimple-iterator.h"
      37                 :            : #include "tree-cfg.h"
      38                 :            : #include "tree-into-ssa.h"
      39                 :            : #include "domwalk.h"
      40                 :            : #include "tree-ssa-propagate.h"
      41                 :            : #include "tree-ssa-threadupdate.h"
      42                 :            : #include "tree-ssa-scopedtables.h"
      43                 :            : #include "tree-ssa-threadedge.h"
      44                 :            : #include "tree-ssa-dom.h"
      45                 :            : #include "gimplify.h"
      46                 :            : #include "tree-cfgcleanup.h"
      47                 :            : #include "dbgcnt.h"
      48                 :            : #include "alloc-pool.h"
      49                 :            : #include "tree-vrp.h"
      50                 :            : #include "vr-values.h"
      51                 :            : #include "gimple-ssa-evrp-analyze.h"
      52                 :            : #include "alias.h"
      53                 :            : 
      54                 :            : /* This file implements optimizations on the dominator tree.  */
      55                 :            : 
      56                 :            : /* Structure for recording edge equivalences.
      57                 :            : 
      58                 :            :    Computing and storing the edge equivalences instead of creating
      59                 :            :    them on-demand can save significant amounts of time, particularly
      60                 :            :    for pathological cases involving switch statements.
      61                 :            : 
      62                 :            :    These structures live for a single iteration of the dominator
      63                 :            :    optimizer in the edge's AUX field.  At the end of an iteration we
      64                 :            :    free each of these structures.  */
      65                 :            : class edge_info
      66                 :            : {
      67                 :            :  public:
      68                 :            :   typedef std::pair <tree, tree> equiv_pair;
      69                 :            :   edge_info (edge);
      70                 :            :   ~edge_info ();
      71                 :            : 
      72                 :            :   /* Record a simple LHS = RHS equivalence.  This may trigger
      73                 :            :      calls to derive_equivalences.  */
      74                 :            :   void record_simple_equiv (tree, tree);
      75                 :            : 
      76                 :            :   /* If traversing this edge creates simple equivalences, we store
      77                 :            :      them as LHS/RHS pairs within this vector.  */
      78                 :            :   vec<equiv_pair> simple_equivalences;
      79                 :            : 
      80                 :            :   /* Traversing an edge may also indicate one or more particular conditions
      81                 :            :      are true or false.  */
      82                 :            :   vec<cond_equivalence> cond_equivalences;
      83                 :            : 
      84                 :            :  private:
      85                 :            :   /* Derive equivalences by walking the use-def chains.  */
      86                 :            :   void derive_equivalences (tree, tree, int);
      87                 :            : };
      88                 :            : 
      89                 :            : /* Track whether or not we have changed the control flow graph.  */
      90                 :            : static bool cfg_altered;
      91                 :            : 
      92                 :            : /* Bitmap of blocks that have had EH statements cleaned.  We should
      93                 :            :    remove their dead edges eventually.  */
      94                 :            : static bitmap need_eh_cleanup;
      95                 :            : static vec<gimple *> need_noreturn_fixup;
      96                 :            : 
      97                 :            : /* Statistics for dominator optimizations.  */
      98                 :            : struct opt_stats_d
      99                 :            : {
     100                 :            :   long num_stmts;
     101                 :            :   long num_exprs_considered;
     102                 :            :   long num_re;
     103                 :            :   long num_const_prop;
     104                 :            :   long num_copy_prop;
     105                 :            : };
     106                 :            : 
     107                 :            : static struct opt_stats_d opt_stats;
     108                 :            : 
     109                 :            : /* Local functions.  */
     110                 :            : static void record_equality (tree, tree, class const_and_copies *);
     111                 :            : static void record_equivalences_from_phis (basic_block);
     112                 :            : static void record_equivalences_from_incoming_edge (basic_block,
     113                 :            :                                                     class const_and_copies *,
     114                 :            :                                                     class avail_exprs_stack *);
     115                 :            : static void eliminate_redundant_computations (gimple_stmt_iterator *,
     116                 :            :                                               class const_and_copies *,
     117                 :            :                                               class avail_exprs_stack *);
     118                 :            : static void record_equivalences_from_stmt (gimple *, int,
     119                 :            :                                            class avail_exprs_stack *);
     120                 :            : static void dump_dominator_optimization_stats (FILE *file,
     121                 :            :                                                hash_table<expr_elt_hasher> *);
     122                 :            : 
     123                 :            : /* Constructor for EDGE_INFO.  An EDGE_INFO instance is always
     124                 :            :    associated with an edge E.  */
     125                 :            : 
     126                 :   21946200 : edge_info::edge_info (edge e)
     127                 :            : {
     128                 :            :   /* Free the old one associated with E, if it exists and
     129                 :            :      associate our new object with E.  */
     130                 :   21946200 :   free_dom_edge_info (e);
     131                 :   21946200 :   e->aux = this;
     132                 :            : 
     133                 :            :   /* And initialize the embedded vectors.  */
     134                 :   21946200 :   simple_equivalences = vNULL;
     135                 :   21946200 :   cond_equivalences = vNULL;
     136                 :   21946200 : }
     137                 :            : 
     138                 :            : /* Destructor just needs to release the vectors.  */
     139                 :            : 
     140                 :   43892500 : edge_info::~edge_info (void)
     141                 :            : {
     142                 :   21946200 :   this->cond_equivalences.release ();
     143                 :   21946200 :   this->simple_equivalences.release ();
     144                 :   21946200 : }
     145                 :            : 
     146                 :            : /* NAME is known to have the value VALUE, which must be a constant.
     147                 :            : 
     148                 :            :    Walk through its use-def chain to see if there are other equivalences
     149                 :            :    we might be able to derive.
     150                 :            : 
     151                 :            :    RECURSION_LIMIT controls how far back we recurse through the use-def
     152                 :            :    chains.  */
     153                 :            : 
     154                 :            : void
     155                 :    9702320 : edge_info::derive_equivalences (tree name, tree value, int recursion_limit)
     156                 :            : {
     157                 :    9702320 :   if (TREE_CODE (name) != SSA_NAME || TREE_CODE (value) != INTEGER_CST)
     158                 :            :     return;
     159                 :            : 
     160                 :            :   /* This records the equivalence for the toplevel object.  Do
     161                 :            :      this before checking the recursion limit.  */
     162                 :    9702220 :   simple_equivalences.safe_push (equiv_pair (name, value));
     163                 :            : 
     164                 :            :   /* Limit how far up the use-def chains we are willing to walk.  */
     165                 :    9702220 :   if (recursion_limit == 0)
     166                 :            :     return;
     167                 :            : 
     168                 :            :   /* We can walk up the use-def chains to potentially find more
     169                 :            :      equivalences.  */
     170                 :    9693130 :   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
     171                 :    9693130 :   if (is_gimple_assign (def_stmt))
     172                 :            :     {
     173                 :    6789640 :       enum tree_code code = gimple_assign_rhs_code (def_stmt);
     174                 :    6789640 :       switch (code)
     175                 :            :         {
     176                 :            :         /* If the result of an OR is zero, then its operands are, too.  */
     177                 :     455247 :         case BIT_IOR_EXPR:
     178                 :     455247 :           if (integer_zerop (value))
     179                 :            :             {
     180                 :     237998 :               tree rhs1 = gimple_assign_rhs1 (def_stmt);
     181                 :     237998 :               tree rhs2 = gimple_assign_rhs2 (def_stmt);
     182                 :            : 
     183                 :     237998 :               value = build_zero_cst (TREE_TYPE (rhs1));
     184                 :     237998 :               derive_equivalences (rhs1, value, recursion_limit - 1);
     185                 :     237998 :               value = build_zero_cst (TREE_TYPE (rhs2));
     186                 :     237998 :               derive_equivalences (rhs2, value, recursion_limit - 1);
     187                 :            :             }
     188                 :            :           break;
     189                 :            : 
     190                 :            :         /* If the result of an AND is nonzero, then its operands are, too.  */
     191                 :     691052 :         case BIT_AND_EXPR:
     192                 :     691052 :           if (!integer_zerop (value))
     193                 :            :             {
     194                 :     283434 :               tree rhs1 = gimple_assign_rhs1 (def_stmt);
     195                 :     283434 :               tree rhs2 = gimple_assign_rhs2 (def_stmt);
     196                 :            : 
     197                 :            :               /* If either operand has a boolean range, then we
     198                 :            :                  know its value must be one, otherwise we just know it
     199                 :            :                  is nonzero.  The former is clearly useful, I haven't
     200                 :            :                  seen cases where the latter is helpful yet.  */
     201                 :     283434 :               if (TREE_CODE (rhs1) == SSA_NAME)
     202                 :            :                 {
     203                 :     283434 :                   if (ssa_name_has_boolean_range (rhs1))
     204                 :            :                     {
     205                 :     191214 :                       value = build_one_cst (TREE_TYPE (rhs1));
     206                 :     191214 :                       derive_equivalences (rhs1, value, recursion_limit - 1);
     207                 :            :                     }
     208                 :            :                 }
     209                 :     283434 :               if (TREE_CODE (rhs2) == SSA_NAME)
     210                 :            :                 {
     211                 :     192535 :                   if (ssa_name_has_boolean_range (rhs2))
     212                 :            :                     {
     213                 :     191035 :                       value = build_one_cst (TREE_TYPE (rhs2));
     214                 :     191035 :                       derive_equivalences (rhs2, value, recursion_limit - 1);
     215                 :            :                     }
     216                 :            :                 }
     217                 :            :             }
     218                 :            :           break;
     219                 :            : 
     220                 :            :         /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
     221                 :            :            set via a widening type conversion, then we may be able to record
     222                 :            :            additional equivalences.  */
     223                 :     219969 :         case NOP_EXPR:
     224                 :     219969 :         case CONVERT_EXPR:
     225                 :     219969 :           {
     226                 :     219969 :             tree rhs = gimple_assign_rhs1 (def_stmt);
     227                 :     219969 :             tree rhs_type = TREE_TYPE (rhs);
     228                 :     219969 :             if (INTEGRAL_TYPE_P (rhs_type)
     229                 :     219174 :                 && (TYPE_PRECISION (TREE_TYPE (name))
     230                 :     219174 :                     >= TYPE_PRECISION (rhs_type))
     231                 :     316775 :                 && int_fits_type_p (value, rhs_type))
     232                 :      95176 :               derive_equivalences (rhs,
     233                 :            :                                    fold_convert (rhs_type, value),
     234                 :            :                                    recursion_limit - 1);
     235                 :            :             break;
     236                 :            :           }
     237                 :            : 
     238                 :            :         /* We can invert the operation of these codes trivially if
     239                 :            :            one of the RHS operands is a constant to produce a known
     240                 :            :            value for the other RHS operand.  */
     241                 :     482963 :         case POINTER_PLUS_EXPR:
     242                 :     482963 :         case PLUS_EXPR:
     243                 :     482963 :           {
     244                 :     482963 :             tree rhs1 = gimple_assign_rhs1 (def_stmt);
     245                 :     482963 :             tree rhs2 = gimple_assign_rhs2 (def_stmt);
     246                 :            : 
     247                 :            :             /* If either argument is a constant, then we can compute
     248                 :            :                a constant value for the nonconstant argument.  */
     249                 :     482963 :             if (TREE_CODE (rhs1) == INTEGER_CST
     250                 :          0 :                 && TREE_CODE (rhs2) == SSA_NAME)
     251                 :          0 :               derive_equivalences (rhs2,
     252                 :          0 :                                    fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
     253                 :            :                                                 value, rhs1),
     254                 :            :                                    recursion_limit - 1);
     255                 :     482963 :             else if (TREE_CODE (rhs2) == INTEGER_CST
     256                 :     443800 :                      && TREE_CODE (rhs1) == SSA_NAME)
     257                 :     887584 :               derive_equivalences (rhs1,
     258                 :     443792 :                                    fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
     259                 :            :                                                 value, rhs2),
     260                 :            :                                    recursion_limit - 1);
     261                 :            :             break;
     262                 :            :           }
     263                 :            : 
     264                 :            :         /* If one of the operands is a constant, then we can compute
     265                 :            :            the value of the other operand.  If both operands are
     266                 :            :            SSA_NAMEs, then they must be equal if the result is zero.  */
     267                 :      44464 :         case MINUS_EXPR:
     268                 :      44464 :           {
     269                 :      44464 :             tree rhs1 = gimple_assign_rhs1 (def_stmt);
     270                 :      44464 :             tree rhs2 = gimple_assign_rhs2 (def_stmt);
     271                 :            : 
     272                 :            :             /* If either argument is a constant, then we can compute
     273                 :            :                a constant value for the nonconstant argument.  */
     274                 :      44464 :             if (TREE_CODE (rhs1) == INTEGER_CST
     275                 :       1370 :                 && TREE_CODE (rhs2) == SSA_NAME)
     276                 :       2740 :               derive_equivalences (rhs2,
     277                 :       1370 :                                    fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
     278                 :            :                                                 rhs1, value),
     279                 :            :                                    recursion_limit - 1);
     280                 :      43094 :             else if (TREE_CODE (rhs2) == INTEGER_CST
     281                 :      19132 :                      && TREE_CODE (rhs1) == SSA_NAME)
     282                 :      38264 :               derive_equivalences (rhs1,
     283                 :      19132 :                                    fold_binary (PLUS_EXPR, TREE_TYPE (rhs1),
     284                 :            :                                                 value, rhs2),
     285                 :            :                                    recursion_limit - 1);
     286                 :      23962 :             else if (integer_zerop (value))
     287                 :            :               {
     288                 :       8460 :                 tree cond = build2 (EQ_EXPR, boolean_type_node,
     289                 :            :                                     gimple_assign_rhs1 (def_stmt),
     290                 :            :                                     gimple_assign_rhs2 (def_stmt));
     291                 :       8460 :                 tree inverted = invert_truthvalue (cond);
     292                 :       8460 :                 record_conditions (&this->cond_equivalences, cond, inverted);
     293                 :            :               }
     294                 :            :             break;
     295                 :            :           }
     296                 :            : 
     297                 :     557305 :         case EQ_EXPR:
     298                 :     557305 :         case NE_EXPR:
     299                 :     557305 :           {
     300                 :     252657 :             if ((code == EQ_EXPR && integer_onep (value))
     301                 :     685143 :                 || (code == NE_EXPR && integer_zerop (value)))
     302                 :            :               {
     303                 :     334044 :                 tree rhs1 = gimple_assign_rhs1 (def_stmt);
     304                 :     334044 :                 tree rhs2 = gimple_assign_rhs2 (def_stmt);
     305                 :            : 
     306                 :            :                 /* If either argument is a constant, then record the
     307                 :            :                    other argument as being the same as that constant.
     308                 :            : 
     309                 :            :                    If neither operand is a constant, then we have a
     310                 :            :                    conditional name == name equivalence.  */
     311                 :     334044 :                 if (TREE_CODE (rhs1) == INTEGER_CST)
     312                 :          0 :                   derive_equivalences (rhs2, rhs1, recursion_limit - 1);
     313                 :     334044 :                 else if (TREE_CODE (rhs2) == INTEGER_CST)
     314                 :     149297 :                   derive_equivalences (rhs1, rhs2, recursion_limit - 1);
     315                 :            :               }
     316                 :            :             else
     317                 :            :               {
     318                 :     223261 :                 tree cond = build2 (code, boolean_type_node,
     319                 :            :                                     gimple_assign_rhs1 (def_stmt),
     320                 :     223261 :                                     gimple_assign_rhs2 (def_stmt));
     321                 :     223261 :                 tree inverted = invert_truthvalue (cond);
     322                 :     223261 :                 if (integer_zerop (value))
     323                 :     127838 :                   std::swap (cond, inverted);
     324                 :     223261 :                 record_conditions (&this->cond_equivalences, cond, inverted);
     325                 :            :               }
     326                 :            :             break;
     327                 :            :           }
     328                 :            : 
     329                 :            :         /* For BIT_NOT and NEGATE, we can just apply the operation to the
     330                 :            :            VALUE to get the new equivalence.  It will always be a constant
     331                 :            :            so we can recurse.  */
     332                 :      34543 :         case BIT_NOT_EXPR:
     333                 :      34543 :         case NEGATE_EXPR:
     334                 :      34543 :           {
     335                 :      34543 :             tree rhs = gimple_assign_rhs1 (def_stmt);
     336                 :      34543 :             tree res;
     337                 :            :             /* If this is a NOT and the operand has a boolean range, then we
     338                 :            :                know its value must be zero or one.  We are not supposed to
     339                 :            :                have a BIT_NOT_EXPR for boolean types with precision > 1 in
     340                 :            :                the general case, see e.g. the handling of TRUTH_NOT_EXPR in
     341                 :            :                the gimplifier, but it can be generated by match.pd out of
     342                 :            :                a BIT_XOR_EXPR wrapped in a BIT_AND_EXPR.  Now the handling
     343                 :            :                of BIT_AND_EXPR above already forces a specific semantics for
     344                 :            :                boolean types with precision > 1 so we must do the same here,
     345                 :            :                otherwise we could change the semantics of TRUTH_NOT_EXPR for
     346                 :            :                boolean types with precision > 1.  */
     347                 :      34543 :             if (code == BIT_NOT_EXPR
     348                 :      33979 :                 && TREE_CODE (rhs) == SSA_NAME
     349                 :      68522 :                 && ssa_name_has_boolean_range (rhs))
     350                 :            :               {
     351                 :      33676 :                 if ((TREE_INT_CST_LOW (value) & 1) == 0)
     352                 :      16397 :                   res = build_one_cst (TREE_TYPE (rhs));
     353                 :            :                 else
     354                 :      17279 :                   res = build_zero_cst (TREE_TYPE (rhs));
     355                 :            :               }
     356                 :            :             else
     357                 :        867 :               res = fold_build1 (code, TREE_TYPE (rhs), value);
     358                 :      34543 :             derive_equivalences (rhs, res, recursion_limit - 1);
     359                 :      34543 :             break;
     360                 :            :           }
     361                 :            : 
     362                 :    4304090 :         default:
     363                 :    4304090 :           {
     364                 :    4304090 :             if (TREE_CODE_CLASS (code) == tcc_comparison)
     365                 :            :               {
     366                 :     548650 :                 tree cond = build2 (code, boolean_type_node,
     367                 :            :                                     gimple_assign_rhs1 (def_stmt),
     368                 :     548650 :                                     gimple_assign_rhs2 (def_stmt));
     369                 :     548650 :                 tree inverted = invert_truthvalue (cond);
     370                 :     548650 :                 if (integer_zerop (value))
     371                 :     242156 :                   std::swap (cond, inverted);
     372                 :     548650 :                 record_conditions (&this->cond_equivalences, cond, inverted);
     373                 :     548650 :                 break;
     374                 :            :               }
     375                 :            :             break;
     376                 :            :           }
     377                 :            :         }
     378                 :            :     }
     379                 :            : }
     380                 :            : 
     381                 :            : void
     382                 :   10020200 : edge_info::record_simple_equiv (tree lhs, tree rhs)
     383                 :            : {
     384                 :            :   /* If the RHS is a constant, then we may be able to derive
     385                 :            :      further equivalences.  Else just record the name = name
     386                 :            :      equivalence.  */
     387                 :   10020200 :   if (TREE_CODE (rhs) == INTEGER_CST)
     388                 :    8100770 :     derive_equivalences (lhs, rhs, 4);
     389                 :            :   else
     390                 :    1919400 :     simple_equivalences.safe_push (equiv_pair (lhs, rhs));
     391                 :   10020200 : }
     392                 :            : 
     393                 :            : /* Free the edge_info data attached to E, if it exists.  */
     394                 :            : 
     395                 :            : void
     396                 :   42187900 : free_dom_edge_info (edge e)
     397                 :            : {
     398                 :   42187900 :   class edge_info *edge_info = (class edge_info *)e->aux;
     399                 :            : 
     400                 :   42187900 :   if (edge_info)
     401                 :   21946200 :     delete edge_info;
     402                 :   42187900 : }
     403                 :            : 
     404                 :            : /* Free all EDGE_INFO structures associated with edges in the CFG.
     405                 :            :    If a particular edge can be threaded, copy the redirection
     406                 :            :    target from the EDGE_INFO structure into the edge's AUX field
     407                 :            :    as required by code to update the CFG and SSA graph for
     408                 :            :    jump threading.  */
     409                 :            : 
     410                 :            : static void
     411                 :    1371790 : free_all_edge_infos (void)
     412                 :            : {
     413                 :    1371790 :   basic_block bb;
     414                 :    1371790 :   edge_iterator ei;
     415                 :    1371790 :   edge e;
     416                 :            : 
     417                 :   14895900 :   FOR_EACH_BB_FN (bb, cfun)
     418                 :            :     {
     419                 :   32635400 :       FOR_EACH_EDGE (e, ei, bb->preds)
     420                 :            :         {
     421                 :   19111400 :           free_dom_edge_info (e);
     422                 :   19111400 :           e->aux = NULL;
     423                 :            :         }
     424                 :            :     }
     425                 :    1371790 : }
     426                 :            : 
     427                 :            : /* We have finished optimizing BB, record any information implied by
     428                 :            :    taking a specific outgoing edge from BB.  */
     429                 :            : 
     430                 :            : static void
     431                 :   28400800 : record_edge_info (basic_block bb)
     432                 :            : {
     433                 :   28400800 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
     434                 :   28400800 :   class edge_info *edge_info;
     435                 :            : 
     436                 :   28400800 :   if (! gsi_end_p (gsi))
     437                 :            :     {
     438                 :   24674900 :       gimple *stmt = gsi_stmt (gsi);
     439                 :   24674900 :       location_t loc = gimple_location (stmt);
     440                 :            : 
     441                 :   24674900 :       if (gimple_code (stmt) == GIMPLE_SWITCH)
     442                 :            :         {
     443                 :      41388 :           gswitch *switch_stmt = as_a <gswitch *> (stmt);
     444                 :      41388 :           tree index = gimple_switch_index (switch_stmt);
     445                 :            : 
     446                 :      41388 :           if (TREE_CODE (index) == SSA_NAME)
     447                 :            :             {
     448                 :      41380 :               int i;
     449                 :      41380 :               int n_labels = gimple_switch_num_labels (switch_stmt);
     450                 :      41380 :               tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
     451                 :      41380 :               edge e;
     452                 :      41380 :               edge_iterator ei;
     453                 :            : 
     454                 :     285260 :               for (i = 0; i < n_labels; i++)
     455                 :            :                 {
     456                 :     243880 :                   tree label = gimple_switch_label (switch_stmt, i);
     457                 :     243880 :                   basic_block target_bb
     458                 :     243880 :                     = label_to_block (cfun, CASE_LABEL (label));
     459                 :     243880 :                   if (CASE_HIGH (label)
     460                 :     229990 :                       || !CASE_LOW (label)
     461                 :     432490 :                       || info[target_bb->index])
     462                 :      76918 :                     info[target_bb->index] = error_mark_node;
     463                 :            :                   else
     464                 :     166962 :                     info[target_bb->index] = label;
     465                 :            :                 }
     466                 :            : 
     467                 :     258920 :               FOR_EACH_EDGE (e, ei, bb->succs)
     468                 :            :                 {
     469                 :     217540 :                   basic_block target_bb = e->dest;
     470                 :     217540 :                   tree label = info[target_bb->index];
     471                 :            : 
     472                 :     217540 :                   if (label != NULL && label != error_mark_node)
     473                 :            :                     {
     474                 :     311124 :                       tree x = fold_convert_loc (loc, TREE_TYPE (index),
     475                 :     155562 :                                                  CASE_LOW (label));
     476                 :     155562 :                       edge_info = new class edge_info (e);
     477                 :     155562 :                       edge_info->record_simple_equiv (index, x);
     478                 :            :                     }
     479                 :            :                 }
     480                 :      41380 :               free (info);
     481                 :            :             }
     482                 :            :         }
     483                 :            : 
     484                 :            :       /* A COND_EXPR may create equivalences too.  */
     485                 :   24674900 :       if (gimple_code (stmt) == GIMPLE_COND)
     486                 :            :         {
     487                 :   10980400 :           edge true_edge;
     488                 :   10980400 :           edge false_edge;
     489                 :            : 
     490                 :   10980400 :           tree op0 = gimple_cond_lhs (stmt);
     491                 :   10980400 :           tree op1 = gimple_cond_rhs (stmt);
     492                 :   10980400 :           enum tree_code code = gimple_cond_code (stmt);
     493                 :            : 
     494                 :   10980400 :           extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
     495                 :            : 
     496                 :            :           /* Special case comparing booleans against a constant as we
     497                 :            :              know the value of OP0 on both arms of the branch.  i.e., we
     498                 :            :              can record an equivalence for OP0 rather than COND. 
     499                 :            : 
     500                 :            :              However, don't do this if the constant isn't zero or one.
     501                 :            :              Such conditionals will get optimized more thoroughly during
     502                 :            :              the domwalk.  */
     503                 :   10980400 :           if ((code == EQ_EXPR || code == NE_EXPR)
     504                 :    8615470 :               && TREE_CODE (op0) == SSA_NAME
     505                 :    8393580 :               && ssa_name_has_boolean_range (op0)
     506                 :    1534080 :               && is_gimple_min_invariant (op1)
     507                 :   12471800 :               && (integer_zerop (op1) || integer_onep (op1)))
     508                 :            :             {
     509                 :    1491430 :               tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
     510                 :    1491430 :               tree false_val = constant_boolean_node (false, TREE_TYPE (op0));
     511                 :            : 
     512                 :    1491430 :               if (code == EQ_EXPR)
     513                 :            :                 {
     514                 :      57797 :                   edge_info = new class edge_info (true_edge);
     515                 :      94210 :                   edge_info->record_simple_equiv (op0,
     516                 :      57797 :                                                   (integer_zerop (op1)
     517                 :            :                                                    ? false_val : true_val));
     518                 :      57797 :                   edge_info = new class edge_info (false_edge);
     519                 :      94210 :                   edge_info->record_simple_equiv (op0,
     520                 :      57797 :                                                   (integer_zerop (op1)
     521                 :            :                                                    ? true_val : false_val));
     522                 :            :                 }
     523                 :            :               else
     524                 :            :                 {
     525                 :    1433630 :                   edge_info = new class edge_info (true_edge);
     526                 :    1434760 :                   edge_info->record_simple_equiv (op0,
     527                 :    1433630 :                                                   (integer_zerop (op1)
     528                 :            :                                                    ? true_val : false_val));
     529                 :    1433630 :                   edge_info = new class edge_info (false_edge);
     530                 :    1434760 :                   edge_info->record_simple_equiv (op0,
     531                 :    1433630 :                                                   (integer_zerop (op1)
     532                 :            :                                                    ? false_val : true_val));
     533                 :            :                 }
     534                 :            :             }
     535                 :            :           /* This can show up in the IL as a result of copy propagation
     536                 :            :              it will eventually be canonicalized, but we have to cope
     537                 :            :              with this case within the pass.  */
     538                 :    9488970 :           else if (is_gimple_min_invariant (op0)
     539                 :    9488970 :                    && TREE_CODE (op1) == SSA_NAME)
     540                 :            :             {
     541                 :     137434 :               tree cond = build2 (code, boolean_type_node, op0, op1);
     542                 :     137434 :               tree inverted = invert_truthvalue_loc (loc, cond);
     543                 :     137434 :               bool can_infer_simple_equiv
     544                 :     137434 :                 = !(HONOR_SIGNED_ZEROS (op0)
     545                 :          0 :                     && real_zerop (op0));
     546                 :     137434 :               class edge_info *edge_info;
     547                 :            : 
     548                 :     137434 :               edge_info = new class edge_info (true_edge);
     549                 :     137434 :               record_conditions (&edge_info->cond_equivalences, cond, inverted);
     550                 :            : 
     551                 :     137434 :               if (can_infer_simple_equiv && code == EQ_EXPR)
     552                 :      26390 :                 edge_info->record_simple_equiv (op1, op0);
     553                 :            : 
     554                 :     137434 :               edge_info = new class edge_info (false_edge);
     555                 :     137434 :               record_conditions (&edge_info->cond_equivalences, inverted, cond);
     556                 :            : 
     557                 :     137434 :               if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
     558                 :     110586 :                 edge_info->record_simple_equiv (op1, op0);
     559                 :            :             }
     560                 :            : 
     561                 :    9351540 :           else if (TREE_CODE (op0) == SSA_NAME
     562                 :    9351540 :                    && (TREE_CODE (op1) == SSA_NAME
     563                 :    6639480 :                        || is_gimple_min_invariant (op1)))
     564                 :            :             {
     565                 :    9266480 :               tree cond = build2 (code, boolean_type_node, op0, op1);
     566                 :    9266480 :               tree inverted = invert_truthvalue_loc (loc, cond);
     567                 :    9266480 :               bool can_infer_simple_equiv
     568                 :    9266480 :                 = !(HONOR_SIGNED_ZEROS (op1)
     569                 :     574122 :                     && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1)));
     570                 :    9266480 :               class edge_info *edge_info;
     571                 :            : 
     572                 :    9266480 :               edge_info = new class edge_info (true_edge);
     573                 :    9266480 :               record_conditions (&edge_info->cond_equivalences, cond, inverted);
     574                 :            : 
     575                 :    9266480 :               if (can_infer_simple_equiv && code == EQ_EXPR)
     576                 :    3091140 :                 edge_info->record_simple_equiv (op0, op1);
     577                 :            : 
     578                 :    9266480 :               edge_info = new class edge_info (false_edge);
     579                 :    9266480 :               record_conditions (&edge_info->cond_equivalences, inverted, cond);
     580                 :            : 
     581                 :    9266480 :               if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
     582                 :    3653630 :                 edge_info->record_simple_equiv (op0, op1);
     583                 :            :             }
     584                 :            :         }
     585                 :            :     }
     586                 :   28400800 : }
     587                 :            : 
     588                 :            : 
     589                 :    1371790 : class dom_opt_dom_walker : public dom_walker
     590                 :            : {
     591                 :            : public:
     592                 :    1371790 :   dom_opt_dom_walker (cdi_direction direction,
     593                 :            :                       class const_and_copies *const_and_copies,
     594                 :            :                       class avail_exprs_stack *avail_exprs_stack,
     595                 :            :                       gcond *dummy_cond)
     596                 :    1371790 :     : dom_walker (direction, REACHABLE_BLOCKS),
     597                 :            :       m_const_and_copies (const_and_copies),
     598                 :            :       m_avail_exprs_stack (avail_exprs_stack),
     599                 :            :       evrp_range_analyzer (true),
     600                 :    1371790 :       m_dummy_cond (dummy_cond) { }
     601                 :            : 
     602                 :            :   virtual edge before_dom_children (basic_block);
     603                 :            :   virtual void after_dom_children (basic_block);
     604                 :            : 
     605                 :            : private:
     606                 :            : 
     607                 :            :   /* Unwindable equivalences, both const/copy and expression varieties.  */
     608                 :            :   class const_and_copies *m_const_and_copies;
     609                 :            :   class avail_exprs_stack *m_avail_exprs_stack;
     610                 :            : 
     611                 :            :   /* VRP data.  */
     612                 :            :   class evrp_range_analyzer evrp_range_analyzer;
     613                 :            : 
     614                 :            :   /* Dummy condition to avoid creating lots of throw away statements.  */
     615                 :            :   gcond *m_dummy_cond;
     616                 :            : 
     617                 :            :   /* Optimize a single statement within a basic block using the
     618                 :            :      various tables mantained by DOM.  Returns the taken edge if
     619                 :            :      the statement is a conditional with a statically determined
     620                 :            :      value.  */
     621                 :            :   edge optimize_stmt (basic_block, gimple_stmt_iterator *, bool *);
     622                 :            : };
     623                 :            : 
     624                 :            : /* Jump threading, redundancy elimination and const/copy propagation.
     625                 :            : 
     626                 :            :    This pass may expose new symbols that need to be renamed into SSA.  For
     627                 :            :    every new symbol exposed, its corresponding bit will be set in
     628                 :            :    VARS_TO_RENAME.  */
     629                 :            : 
     630                 :            : namespace {
     631                 :            : 
     632                 :            : const pass_data pass_data_dominator =
     633                 :            : {
     634                 :            :   GIMPLE_PASS, /* type */
     635                 :            :   "dom", /* name */
     636                 :            :   OPTGROUP_NONE, /* optinfo_flags */
     637                 :            :   TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
     638                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
     639                 :            :   0, /* properties_provided */
     640                 :            :   0, /* properties_destroyed */
     641                 :            :   0, /* todo_flags_start */
     642                 :            :   ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
     643                 :            : };
     644                 :            : 
     645                 :            : class pass_dominator : public gimple_opt_pass
     646                 :            : {
     647                 :            : public:
     648                 :     601620 :   pass_dominator (gcc::context *ctxt)
     649                 :     601620 :     : gimple_opt_pass (pass_data_dominator, ctxt),
     650                 :    1203240 :       may_peel_loop_headers_p (false)
     651                 :            :   {}
     652                 :            : 
     653                 :            :   /* opt_pass methods: */
     654                 :     401080 :   opt_pass * clone () { return new pass_dominator (m_ctxt); }
     655                 :     601620 :   void set_pass_param (unsigned int n, bool param)
     656                 :            :     {
     657                 :     601620 :       gcc_assert (n == 0);
     658                 :     601620 :       may_peel_loop_headers_p = param;
     659                 :     601620 :     }
     660                 :    1372200 :   virtual bool gate (function *) { return flag_tree_dom != 0; }
     661                 :            :   virtual unsigned int execute (function *);
     662                 :            : 
     663                 :            :  private:
     664                 :            :   /* This flag is used to prevent loops from being peeled repeatedly in jump
     665                 :            :      threading; it will be removed once we preserve loop structures throughout
     666                 :            :      the compilation -- we will be able to mark the affected loops directly in
     667                 :            :      jump threading, and avoid peeling them next time.  */
     668                 :            :   bool may_peel_loop_headers_p;
     669                 :            : }; // class pass_dominator
     670                 :            : 
     671                 :            : unsigned int
     672                 :    1371790 : pass_dominator::execute (function *fun)
     673                 :            : {
     674                 :    1371790 :   memset (&opt_stats, 0, sizeof (opt_stats));
     675                 :            : 
     676                 :            :   /* Create our hash tables.  */
     677                 :    1371790 :   hash_table<expr_elt_hasher> *avail_exprs
     678                 :    1371790 :     = new hash_table<expr_elt_hasher> (1024);
     679                 :    1371790 :   class avail_exprs_stack *avail_exprs_stack
     680                 :    1371790 :     = new class avail_exprs_stack (avail_exprs);
     681                 :    1371790 :   class const_and_copies *const_and_copies = new class const_and_copies ();
     682                 :    1371790 :   need_eh_cleanup = BITMAP_ALLOC (NULL);
     683                 :    1371790 :   need_noreturn_fixup.create (0);
     684                 :            : 
     685                 :    1371790 :   calculate_dominance_info (CDI_DOMINATORS);
     686                 :    1371790 :   cfg_altered = false;
     687                 :            : 
     688                 :            :   /* We need to know loop structures in order to avoid destroying them
     689                 :            :      in jump threading.  Note that we still can e.g. thread through loop
     690                 :            :      headers to an exit edge, or through loop header to the loop body, assuming
     691                 :            :      that we update the loop info.
     692                 :            : 
     693                 :            :      TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
     694                 :            :      to several overly conservative bail-outs in jump threading, case
     695                 :            :      gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
     696                 :            :      missing.  We should improve jump threading in future then
     697                 :            :      LOOPS_HAVE_PREHEADERS won't be needed here.  */
     698                 :    1371790 :   loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
     699                 :            : 
     700                 :            :   /* Initialize the value-handle array.  */
     701                 :    1371790 :   threadedge_initialize_values ();
     702                 :            : 
     703                 :            :   /* We need accurate information regarding back edges in the CFG
     704                 :            :      for jump threading; this may include back edges that are not part of
     705                 :            :      a single loop.  */
     706                 :    1371790 :   mark_dfs_back_edges ();
     707                 :            : 
     708                 :            :   /* We want to create the edge info structures before the dominator walk
     709                 :            :      so that they'll be in place for the jump threader, particularly when
     710                 :            :      threading through a join block.
     711                 :            : 
     712                 :            :      The conditions will be lazily updated with global equivalences as
     713                 :            :      we reach them during the dominator walk.  */
     714                 :    1371790 :   basic_block bb;
     715                 :   14895900 :   FOR_EACH_BB_FN (bb, fun)
     716                 :   13524100 :     record_edge_info (bb);
     717                 :            : 
     718                 :    1371790 :   gcond *dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
     719                 :            :                                          integer_zero_node, NULL, NULL);
     720                 :            : 
     721                 :            :   /* Recursively walk the dominator tree optimizing statements.  */
     722                 :    1371790 :   dom_opt_dom_walker walker (CDI_DOMINATORS, const_and_copies,
     723                 :    2743580 :                              avail_exprs_stack, dummy_cond);
     724                 :    1371790 :   walker.walk (fun->cfg->x_entry_block_ptr);
     725                 :            : 
     726                 :            :   /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
     727                 :            :      edge.  When found, remove jump threads which contain any outgoing
     728                 :            :      edge from the affected block.  */
     729                 :    1371790 :   if (cfg_altered)
     730                 :            :     {
     731                 :    1402560 :       FOR_EACH_BB_FN (bb, fun)
     732                 :            :         {
     733                 :    1378320 :           edge_iterator ei;
     734                 :    1378320 :           edge e;
     735                 :            : 
     736                 :            :           /* First see if there are any edges without EDGE_EXECUTABLE
     737                 :            :              set.  */
     738                 :    1378320 :           bool found = false;
     739                 :    3351650 :           FOR_EACH_EDGE (e, ei, bb->succs)
     740                 :            :             {
     741                 :    2029370 :               if ((e->flags & EDGE_EXECUTABLE) == 0)
     742                 :            :                 {
     743                 :            :                   found = true;
     744                 :            :                   break;
     745                 :            :                 }
     746                 :            :             }
     747                 :            : 
     748                 :            :           /* If there were any such edges found, then remove jump threads
     749                 :            :              containing any edge leaving BB.  */
     750                 :    1378320 :           if (found)
     751                 :     163259 :             FOR_EACH_EDGE (e, ei, bb->succs)
     752                 :     107224 :               remove_jump_threads_including (e);
     753                 :            :         }
     754                 :            :     }
     755                 :            : 
     756                 :    1371790 :   {
     757                 :    1371790 :     gimple_stmt_iterator gsi;
     758                 :    1371790 :     basic_block bb;
     759                 :   14895900 :     FOR_EACH_BB_FN (bb, fun)
     760                 :            :       {
     761                 :  135714000 :         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     762                 :  108666000 :           update_stmt_if_modified (gsi_stmt (gsi));
     763                 :            :       }
     764                 :            :   }
     765                 :            : 
     766                 :            :   /* If we exposed any new variables, go ahead and put them into
     767                 :            :      SSA form now, before we handle jump threading.  This simplifies
     768                 :            :      interactions between rewriting of _DECL nodes into SSA form
     769                 :            :      and rewriting SSA_NAME nodes into SSA form after block
     770                 :            :      duplication and CFG manipulation.  */
     771                 :    1371790 :   update_ssa (TODO_update_ssa);
     772                 :            : 
     773                 :    1371790 :   free_all_edge_infos ();
     774                 :            : 
     775                 :            :   /* Thread jumps, creating duplicate blocks as needed.  */
     776                 :    1371790 :   cfg_altered |= thread_through_all_blocks (may_peel_loop_headers_p);
     777                 :            : 
     778                 :    1371790 :   if (cfg_altered)
     779                 :      70716 :     free_dominance_info (CDI_DOMINATORS);
     780                 :            : 
     781                 :            :   /* Removal of statements may make some EH edges dead.  Purge
     782                 :            :      such edges from the CFG as needed.  */
     783                 :    1371790 :   if (!bitmap_empty_p (need_eh_cleanup))
     784                 :            :     {
     785                 :        483 :       unsigned i;
     786                 :        483 :       bitmap_iterator bi;
     787                 :            : 
     788                 :            :       /* Jump threading may have created forwarder blocks from blocks
     789                 :            :          needing EH cleanup; the new successor of these blocks, which
     790                 :            :          has inherited from the original block, needs the cleanup.
     791                 :            :          Don't clear bits in the bitmap, as that can break the bitmap
     792                 :            :          iterator.  */
     793                 :       1436 :       EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
     794                 :            :         {
     795                 :        953 :           basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
     796                 :        953 :           if (bb == NULL)
     797                 :          0 :             continue;
     798                 :        976 :           while (single_succ_p (bb)
     799                 :        976 :                  && (single_succ_edge (bb)->flags
     800                 :         28 :                      & (EDGE_EH|EDGE_DFS_BACK)) == 0)
     801                 :         23 :             bb = single_succ (bb);
     802                 :        953 :           if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
     803                 :         12 :             continue;
     804                 :        941 :           if ((unsigned) bb->index != i)
     805                 :          9 :             bitmap_set_bit (need_eh_cleanup, bb->index);
     806                 :            :         }
     807                 :            : 
     808                 :        483 :       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
     809                 :        483 :       bitmap_clear (need_eh_cleanup);
     810                 :            :     }
     811                 :            : 
     812                 :            :   /* Fixup stmts that became noreturn calls.  This may require splitting
     813                 :            :      blocks and thus isn't possible during the dominator walk or before
     814                 :            :      jump threading finished.  Do this in reverse order so we don't
     815                 :            :      inadvertedly remove a stmt we want to fixup by visiting a dominating
     816                 :            :      now noreturn call first.  */
     817                 :    1371800 :   while (!need_noreturn_fixup.is_empty ())
     818                 :            :     {
     819                 :          7 :       gimple *stmt = need_noreturn_fixup.pop ();
     820                 :          7 :       if (dump_file && dump_flags & TDF_DETAILS)
     821                 :            :         {
     822                 :          0 :           fprintf (dump_file, "Fixing up noreturn call ");
     823                 :          0 :           print_gimple_stmt (dump_file, stmt, 0);
     824                 :          0 :           fprintf (dump_file, "\n");
     825                 :            :         }
     826                 :          7 :       fixup_noreturn_call (stmt);
     827                 :            :     }
     828                 :            : 
     829                 :    1371790 :   statistics_counter_event (fun, "Redundant expressions eliminated",
     830                 :    1371790 :                             opt_stats.num_re);
     831                 :    1371790 :   statistics_counter_event (fun, "Constants propagated",
     832                 :    1371790 :                             opt_stats.num_const_prop);
     833                 :    1371790 :   statistics_counter_event (fun, "Copies propagated",
     834                 :    1371790 :                             opt_stats.num_copy_prop);
     835                 :            : 
     836                 :            :   /* Debugging dumps.  */
     837                 :    1371790 :   if (dump_file && (dump_flags & TDF_STATS))
     838                 :         34 :     dump_dominator_optimization_stats (dump_file, avail_exprs);
     839                 :            : 
     840                 :    1371790 :   loop_optimizer_finalize ();
     841                 :            : 
     842                 :            :   /* Delete our main hashtable.  */
     843                 :    1371790 :   delete avail_exprs;
     844                 :    1371790 :   avail_exprs = NULL;
     845                 :            : 
     846                 :            :   /* Free asserted bitmaps and stacks.  */
     847                 :    1371790 :   BITMAP_FREE (need_eh_cleanup);
     848                 :    1371790 :   need_noreturn_fixup.release ();
     849                 :    2743580 :   delete avail_exprs_stack;
     850                 :    2743580 :   delete const_and_copies;
     851                 :            : 
     852                 :            :   /* Free the value-handle array.  */
     853                 :    1371790 :   threadedge_finalize_values ();
     854                 :            : 
     855                 :    1371790 :   return 0;
     856                 :            : }
     857                 :            : 
     858                 :            : } // anon namespace
     859                 :            : 
     860                 :            : gimple_opt_pass *
     861                 :     200540 : make_pass_dominator (gcc::context *ctxt)
     862                 :            : {
     863                 :     200540 :   return new pass_dominator (ctxt);
     864                 :            : }
     865                 :            : 
     866                 :            : /* A hack until we remove threading from tree-vrp.c and bring the
     867                 :            :    simplification routine into the dom_opt_dom_walker class.  */
     868                 :            : static class vr_values *x_vr_values;
     869                 :            : 
     870                 :            : /* A trivial wrapper so that we can present the generic jump
     871                 :            :    threading code with a simple API for simplifying statements.  */
     872                 :            : static tree
     873                 :   21507800 : simplify_stmt_for_jump_threading (gimple *stmt,
     874                 :            :                                   gimple *within_stmt ATTRIBUTE_UNUSED,
     875                 :            :                                   class avail_exprs_stack *avail_exprs_stack,
     876                 :            :                                   basic_block bb ATTRIBUTE_UNUSED)
     877                 :            : {
     878                 :            :   /* First query our hash table to see if the expression is available
     879                 :            :      there.  A non-NULL return value will be either a constant or another
     880                 :            :      SSA_NAME.  */
     881                 :   21507800 :   tree cached_lhs =  avail_exprs_stack->lookup_avail_expr (stmt, false, true);
     882                 :   21507800 :   if (cached_lhs)
     883                 :            :     return cached_lhs;
     884                 :            : 
     885                 :            :   /* If the hash table query failed, query VRP information.  This is
     886                 :            :      essentially the same as tree-vrp's simplification routine.  The
     887                 :            :      copy in tree-vrp is scheduled for removal in gcc-9.  */
     888                 :   21021800 :   if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
     889                 :            :     {
     890                 :    6588730 :       cached_lhs
     891                 :    6588730 :         = x_vr_values->vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
     892                 :            :                                                  gimple_cond_lhs (cond_stmt),
     893                 :            :                                                  gimple_cond_rhs (cond_stmt),
     894                 :            :                                                  within_stmt);
     895                 :    6588730 :       return cached_lhs;
     896                 :            :     }
     897                 :            : 
     898                 :   14433100 :   if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
     899                 :            :     {
     900                 :      13853 :       tree op = gimple_switch_index (switch_stmt);
     901                 :      13853 :       if (TREE_CODE (op) != SSA_NAME)
     902                 :            :         return NULL_TREE;
     903                 :            : 
     904                 :      13853 :       const value_range_equiv *vr = x_vr_values->get_value_range (op);
     905                 :      13853 :       if (vr->undefined_p ()
     906                 :      13829 :           || vr->varying_p ()
     907                 :      17413 :           || vr->symbolic_p ())
     908                 :      10386 :         return NULL_TREE;
     909                 :            : 
     910                 :       3467 :       if (vr->kind () == VR_RANGE)
     911                 :            :         {
     912                 :       3083 :           size_t i, j;
     913                 :            : 
     914                 :       3083 :           find_case_label_range (switch_stmt, vr->min (), vr->max (), &i, &j);
     915                 :            : 
     916                 :            :           /* Is there only one such label?  */
     917                 :       3083 :           if (i == j)
     918                 :            :             {
     919                 :         52 :               tree label = gimple_switch_label (switch_stmt, i);
     920                 :         52 :               tree singleton;
     921                 :            : 
     922                 :            :               /* The i'th label will only be taken if the value range of the
     923                 :            :                  operand is entirely within the bounds of this label.  */
     924                 :         52 :               if (CASE_HIGH (label) != NULL_TREE
     925                 :         52 :                   ? (tree_int_cst_compare (CASE_LOW (label), vr->min ()) <= 0
     926                 :          0 :                      && tree_int_cst_compare (CASE_HIGH (label), vr->max ()) >= 0)
     927                 :         52 :                   : (vr->singleton_p (&singleton)
     928                 :         52 :                      && tree_int_cst_equal (CASE_LOW (label), singleton)))
     929                 :          0 :                 return label;
     930                 :            :             }
     931                 :            : 
     932                 :            :           /* If there are no such labels, then the default label
     933                 :            :              will be taken.  */
     934                 :       3083 :           if (i > j)
     935                 :         16 :             return gimple_switch_label (switch_stmt, 0);
     936                 :            :         }
     937                 :            : 
     938                 :       3451 :       if (vr->kind () == VR_ANTI_RANGE)
     939                 :            :           {
     940                 :        384 :             unsigned n = gimple_switch_num_labels (switch_stmt);
     941                 :        384 :             tree min_label = gimple_switch_label (switch_stmt, 1);
     942                 :        384 :             tree max_label = gimple_switch_label (switch_stmt, n - 1);
     943                 :            : 
     944                 :            :             /* The default label will be taken only if the anti-range of the
     945                 :            :                operand is entirely outside the bounds of all the (non-default)
     946                 :            :                case labels.  */
     947                 :        384 :             if (tree_int_cst_compare (vr->min (), CASE_LOW (min_label)) <= 0
     948                 :        582 :                 && (CASE_HIGH (max_label) != NULL_TREE
     949                 :        198 :                     ? tree_int_cst_compare (vr->max (), CASE_HIGH (max_label)) >= 0
     950                 :        198 :                     : tree_int_cst_compare (vr->max (), CASE_LOW (max_label)) >= 0))
     951                 :         12 :             return gimple_switch_label (switch_stmt, 0);
     952                 :            :           }
     953                 :       3439 :         return NULL_TREE;
     954                 :            :     }
     955                 :            : 
     956                 :   14419200 :   if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
     957                 :            :     {
     958                 :   13194700 :       tree lhs = gimple_assign_lhs (assign_stmt);
     959                 :   13194700 :       if (TREE_CODE (lhs) == SSA_NAME
     960                 :   13194700 :           && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
     961                 :    4449400 :               || POINTER_TYPE_P (TREE_TYPE (lhs)))
     962                 :   25470400 :           && stmt_interesting_for_vrp (stmt))
     963                 :            :         {
     964                 :    7095830 :           edge dummy_e;
     965                 :    7095830 :           tree dummy_tree;
     966                 :    7095830 :           value_range_equiv new_vr;
     967                 :    7095830 :           x_vr_values->extract_range_from_stmt (stmt, &dummy_e,
     968                 :            :                                                 &dummy_tree, &new_vr);
     969                 :    7095830 :           tree singleton;
     970                 :    7095830 :           if (new_vr.singleton_p (&singleton))
     971                 :       8438 :             return singleton;
     972                 :            :         }
     973                 :            :     }
     974                 :            :   return NULL;
     975                 :            : }
     976                 :            : 
     977                 :            : /* Valueize hook for gimple_fold_stmt_to_constant_1.  */
     978                 :            : 
     979                 :            : static tree
     980                 :   24124000 : dom_valueize (tree t)
     981                 :            : {
     982                 :   24124000 :   if (TREE_CODE (t) == SSA_NAME)
     983                 :            :     {
     984                 :   33757000 :       tree tem = SSA_NAME_VALUE (t);
     985                 :   12987600 :       if (tem)
     986                 :    2459830 :         return tem;
     987                 :            :     }
     988                 :            :   return t;
     989                 :            : }
     990                 :            : 
     991                 :            : /* We have just found an equivalence for LHS on an edge E.
     992                 :            :    Look backwards to other uses of LHS and see if we can derive
     993                 :            :    additional equivalences that are valid on edge E.  */
     994                 :            : static void
     995                 :    7993690 : back_propagate_equivalences (tree lhs, edge e,
     996                 :            :                              class const_and_copies *const_and_copies)
     997                 :            : {
     998                 :    7993690 :   use_operand_p use_p;
     999                 :    7993690 :   imm_use_iterator iter;
    1000                 :    7993690 :   bitmap domby = NULL;
    1001                 :    7993690 :   basic_block dest = e->dest;
    1002                 :            : 
    1003                 :            :   /* Iterate over the uses of LHS to see if any dominate E->dest.
    1004                 :            :      If so, they may create useful equivalences too.
    1005                 :            : 
    1006                 :            :      ???  If the code gets re-organized to a worklist to catch more
    1007                 :            :      indirect opportunities and it is made to handle PHIs then this
    1008                 :            :      should only consider use_stmts in basic-blocks we have already visited.  */
    1009                 :   30592400 :   FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
    1010                 :            :     {
    1011                 :   22598700 :       gimple *use_stmt = USE_STMT (use_p);
    1012                 :            : 
    1013                 :            :       /* Often the use is in DEST, which we trivially know we can't use.
    1014                 :            :          This is cheaper than the dominator set tests below.  */
    1015                 :   22598700 :       if (dest == gimple_bb (use_stmt))
    1016                 :     278162 :         continue;
    1017                 :            : 
    1018                 :            :       /* Filter out statements that can never produce a useful
    1019                 :            :          equivalence.  */
    1020                 :   22320600 :       tree lhs2 = gimple_get_lhs (use_stmt);
    1021                 :   22320600 :       if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME)
    1022                 :   16479000 :         continue;
    1023                 :            : 
    1024                 :            :       /* Profiling has shown the domination tests here can be fairly
    1025                 :            :          expensive.  We get significant improvements by building the
    1026                 :            :          set of blocks that dominate BB.  We can then just test
    1027                 :            :          for set membership below.
    1028                 :            : 
    1029                 :            :          We also initialize the set lazily since often the only uses
    1030                 :            :          are going to be in the same block as DEST.  */
    1031                 :    5841570 :       if (!domby)
    1032                 :            :         {
    1033                 :    3039840 :           domby = BITMAP_ALLOC (NULL);
    1034                 :    3039840 :           basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest);
    1035                 :   69514600 :           while (bb)
    1036                 :            :             {
    1037                 :   66474800 :               bitmap_set_bit (domby, bb->index);
    1038                 :   66474800 :               bb = get_immediate_dominator (CDI_DOMINATORS, bb);
    1039                 :            :             }
    1040                 :            :         }
    1041                 :            : 
    1042                 :            :       /* This tests if USE_STMT does not dominate DEST.  */
    1043                 :    5841570 :       if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index))
    1044                 :    3252980 :         continue;
    1045                 :            : 
    1046                 :            :       /* At this point USE_STMT dominates DEST and may result in a
    1047                 :            :          useful equivalence.  Try to simplify its RHS to a constant
    1048                 :            :          or SSA_NAME.  */
    1049                 :    2588590 :       tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize,
    1050                 :            :                                                  no_follow_ssa_edges);
    1051                 :    2588590 :       if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res)))
    1052                 :    1749630 :         record_equality (lhs2, res, const_and_copies);
    1053                 :            :     }
    1054                 :            : 
    1055                 :    7993690 :   if (domby)
    1056                 :    3039840 :     BITMAP_FREE (domby);
    1057                 :    7993690 : }
    1058                 :            : 
    1059                 :            : /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
    1060                 :            :    by traversing edge E (which are cached in E->aux).
    1061                 :            : 
    1062                 :            :    Callers are responsible for managing the unwinding markers.  */
    1063                 :            : void
    1064                 :   30192300 : record_temporary_equivalences (edge e,
    1065                 :            :                                class const_and_copies *const_and_copies,
    1066                 :            :                                class avail_exprs_stack *avail_exprs_stack)
    1067                 :            : {
    1068                 :   30192300 :   int i;
    1069                 :   30192300 :   class edge_info *edge_info = (class edge_info *) e->aux;
    1070                 :            : 
    1071                 :            :   /* If we have info associated with this edge, record it into
    1072                 :            :      our equivalence tables.  */
    1073                 :   30192300 :   if (edge_info)
    1074                 :            :     {
    1075                 :            :       cond_equivalence *eq;
    1076                 :            :       /* If we have 0 = COND or 1 = COND equivalences, record them
    1077                 :            :          into our expression hash tables.  */
    1078                 :   56834500 :       for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
    1079                 :   41914200 :         avail_exprs_stack->record_cond (eq);
    1080                 :            : 
    1081                 :            :       edge_info::equiv_pair *seq;
    1082                 :   22914000 :       for (i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i)
    1083                 :            :         {
    1084                 :    7993690 :           tree lhs = seq->first;
    1085                 :    7993690 :           if (!lhs || TREE_CODE (lhs) != SSA_NAME)
    1086                 :          0 :             continue;
    1087                 :            : 
    1088                 :            :           /* Record the simple NAME = VALUE equivalence.  */
    1089                 :    7993690 :           tree rhs = seq->second;
    1090                 :            : 
    1091                 :            :           /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is
    1092                 :            :              cheaper to compute than the other, then set up the equivalence
    1093                 :            :              such that we replace the expensive one with the cheap one.
    1094                 :            : 
    1095                 :            :              If they are the same cost to compute, then do not record
    1096                 :            :              anything.  */
    1097                 :    7993690 :           if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
    1098                 :            :             {
    1099                 :    1023630 :               gimple *rhs_def = SSA_NAME_DEF_STMT (rhs);
    1100                 :    1023630 :               int rhs_cost = estimate_num_insns (rhs_def, &eni_size_weights);
    1101                 :            : 
    1102                 :    1023630 :               gimple *lhs_def = SSA_NAME_DEF_STMT (lhs);
    1103                 :    1023630 :               int lhs_cost = estimate_num_insns (lhs_def, &eni_size_weights);
    1104                 :            : 
    1105                 :    1023630 :               if (rhs_cost > lhs_cost)
    1106                 :     102128 :                 record_equality (rhs, lhs, const_and_copies);
    1107                 :     921506 :               else if (rhs_cost < lhs_cost)
    1108                 :     250825 :                 record_equality (lhs, rhs, const_and_copies);
    1109                 :            :             }
    1110                 :            :           else
    1111                 :    6970060 :             record_equality (lhs, rhs, const_and_copies);
    1112                 :            : 
    1113                 :            : 
    1114                 :            :           /* Any equivalence found for LHS may result in additional
    1115                 :            :              equivalences for other uses of LHS that we have already
    1116                 :            :              processed.  */
    1117                 :    7993690 :           back_propagate_equivalences (lhs, e, const_and_copies);
    1118                 :            :         }
    1119                 :            :     }
    1120                 :   30192300 : }
    1121                 :            : 
    1122                 :            : /* PHI nodes can create equivalences too.
    1123                 :            : 
    1124                 :            :    Ignoring any alternatives which are the same as the result, if
    1125                 :            :    all the alternatives are equal, then the PHI node creates an
    1126                 :            :    equivalence.  */
    1127                 :            : 
    1128                 :            : static void
    1129                 :   14876800 : record_equivalences_from_phis (basic_block bb)
    1130                 :            : {
    1131                 :   14876800 :   gphi_iterator gsi;
    1132                 :            : 
    1133                 :   14876800 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
    1134                 :            :     {
    1135                 :    5344790 :       gphi *phi = gsi.phi ();
    1136                 :            : 
    1137                 :            :       /* We might eliminate the PHI, so advance GSI now.  */
    1138                 :    5344790 :       gsi_next (&gsi);
    1139                 :            : 
    1140                 :    5344790 :       tree lhs = gimple_phi_result (phi);
    1141                 :    5344790 :       tree rhs = NULL;
    1142                 :    5344790 :       size_t i;
    1143                 :            : 
    1144                 :   10904300 :       for (i = 0; i < gimple_phi_num_args (phi); i++)
    1145                 :            :         {
    1146                 :   10639700 :           tree t = gimple_phi_arg_def (phi, i);
    1147                 :            : 
    1148                 :            :           /* Ignore alternatives which are the same as our LHS.  Since
    1149                 :            :              LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
    1150                 :            :              can simply compare pointers.  */
    1151                 :   10639700 :           if (lhs == t)
    1152                 :      17691 :             continue;
    1153                 :            : 
    1154                 :            :           /* If the associated edge is not marked as executable, then it
    1155                 :            :              can be ignored.  */
    1156                 :   10622000 :           if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0)
    1157                 :      31810 :             continue;
    1158                 :            : 
    1159                 :   10590200 :           t = dom_valueize (t);
    1160                 :            : 
    1161                 :            :           /* If T is an SSA_NAME and its associated edge is a backedge,
    1162                 :            :              then quit as we cannot utilize this equivalence.  */
    1163                 :   10590200 :           if (TREE_CODE (t) == SSA_NAME
    1164                 :   10590200 :               && (gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK))
    1165                 :            :             break;
    1166                 :            : 
    1167                 :            :           /* If we have not processed an alternative yet, then set
    1168                 :            :              RHS to this alternative.  */
    1169                 :    8911000 :           if (rhs == NULL)
    1170                 :            :             rhs = t;
    1171                 :            :           /* If we have processed an alternative (stored in RHS), then
    1172                 :            :              see if it is equal to this one.  If it isn't, then stop
    1173                 :            :              the search.  */
    1174                 :    3669860 :           else if (! operand_equal_for_phi_arg_p (rhs, t))
    1175                 :            :             break;
    1176                 :            :         }
    1177                 :            : 
    1178                 :            :       /* If we had no interesting alternatives, then all the RHS alternatives
    1179                 :            :          must have been the same as LHS.  */
    1180                 :    5344790 :       if (!rhs)
    1181                 :     103649 :         rhs = lhs;
    1182                 :            : 
    1183                 :            :       /* If we managed to iterate through each PHI alternative without
    1184                 :            :          breaking out of the loop, then we have a PHI which may create
    1185                 :            :          a useful equivalence.  We do not need to record unwind data for
    1186                 :            :          this, since this is a true assignment and not an equivalence
    1187                 :            :          inferred from a comparison.  All uses of this ssa name are dominated
    1188                 :            :          by this assignment, so unwinding just costs time and space.  */
    1189                 :    5344790 :       if (i == gimple_phi_num_args (phi))
    1190                 :            :         {
    1191                 :     264587 :           if (may_propagate_copy (lhs, rhs))
    1192                 :     130638 :             set_ssa_name_value (lhs, rhs);
    1193                 :   20489500 :           else if (virtual_operand_p (lhs))
    1194                 :            :             {
    1195                 :     133747 :               gimple *use_stmt;
    1196                 :     133747 :               imm_use_iterator iter;
    1197                 :     133747 :               use_operand_p use_p;
    1198                 :            :               /* For virtual operands we have to propagate into all uses as
    1199                 :            :                  otherwise we will create overlapping life-ranges.  */
    1200                 :     426189 :               FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
    1201                 :     895088 :                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    1202                 :     301323 :                   SET_USE (use_p, rhs);
    1203                 :     133747 :               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
    1204                 :         25 :                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
    1205                 :     133747 :               gimple_stmt_iterator tmp_gsi = gsi_for_stmt (phi);
    1206                 :     133747 :               remove_phi_node (&tmp_gsi, true);
    1207                 :            :             }
    1208                 :            :         }
    1209                 :            :     }
    1210                 :   14876800 : }
    1211                 :            : 
    1212                 :            : /* Record any equivalences created by the incoming edge to BB into
    1213                 :            :    CONST_AND_COPIES and AVAIL_EXPRS_STACK.  If BB has more than one
    1214                 :            :    incoming edge, then no equivalence is created.  */
    1215                 :            : 
    1216                 :            : static void
    1217                 :   14876800 : record_equivalences_from_incoming_edge (basic_block bb,
    1218                 :            :     class const_and_copies *const_and_copies,
    1219                 :            :     class avail_exprs_stack *avail_exprs_stack)
    1220                 :            : {
    1221                 :   14876800 :   edge e;
    1222                 :   14876800 :   basic_block parent;
    1223                 :            : 
    1224                 :            :   /* If our parent block ended with a control statement, then we may be
    1225                 :            :      able to record some equivalences based on which outgoing edge from
    1226                 :            :      the parent was followed.  */
    1227                 :   14876800 :   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
    1228                 :            : 
    1229                 :   14876800 :   e = single_pred_edge_ignoring_loop_edges (bb, true);
    1230                 :            : 
    1231                 :            :   /* If we had a single incoming edge from our parent block, then enter
    1232                 :            :      any data associated with the edge into our tables.  */
    1233                 :   14876800 :   if (e && e->src == parent)
    1234                 :   10803000 :     record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
    1235                 :   14876800 : }
    1236                 :            : 
    1237                 :            : /* Dump statistics for the hash table HTAB.  */
    1238                 :            : 
    1239                 :            : static void
    1240                 :         34 : htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab)
    1241                 :            : {
    1242                 :         34 :   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
    1243                 :         34 :            (long) htab.size (),
    1244                 :         34 :            (long) htab.elements (),
    1245                 :            :            htab.collisions ());
    1246                 :         34 : }
    1247                 :            : 
    1248                 :            : /* Dump SSA statistics on FILE.  */
    1249                 :            : 
    1250                 :            : static void
    1251                 :         34 : dump_dominator_optimization_stats (FILE *file,
    1252                 :            :                                    hash_table<expr_elt_hasher> *avail_exprs)
    1253                 :            : {
    1254                 :         34 :   fprintf (file, "Total number of statements:                   %6ld\n\n",
    1255                 :            :            opt_stats.num_stmts);
    1256                 :         34 :   fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
    1257                 :            :            opt_stats.num_exprs_considered);
    1258                 :            : 
    1259                 :         34 :   fprintf (file, "\nHash table statistics:\n");
    1260                 :            : 
    1261                 :         34 :   fprintf (file, "    avail_exprs: ");
    1262                 :         34 :   htab_statistics (file, *avail_exprs);
    1263                 :         34 : }
    1264                 :            : 
    1265                 :            : 
    1266                 :            : /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
    1267                 :            :    This constrains the cases in which we may treat this as assignment.  */
    1268                 :            : 
    1269                 :            : static void
    1270                 :    9072640 : record_equality (tree x, tree y, class const_and_copies *const_and_copies)
    1271                 :            : {
    1272                 :    9072640 :   tree prev_x = NULL, prev_y = NULL;
    1273                 :            : 
    1274                 :    9072640 :   if (tree_swap_operands_p (x, y))
    1275                 :     751586 :     std::swap (x, y);
    1276                 :            : 
    1277                 :            :   /* Most of the time tree_swap_operands_p does what we want.  But there
    1278                 :            :      are cases where we know one operand is better for copy propagation than
    1279                 :            :      the other.  Given no other code cares about ordering of equality
    1280                 :            :      comparison operators for that purpose, we just handle the special cases
    1281                 :            :      here.  */
    1282                 :    9072640 :   if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME)
    1283                 :            :     {
    1284                 :            :       /* If one operand is a single use operand, then make it
    1285                 :            :          X.  This will preserve its single use properly and if this
    1286                 :            :          conditional is eliminated, the computation of X can be
    1287                 :            :          eliminated as well.  */
    1288                 :     900077 :       if (has_single_use (y) && ! has_single_use (x))
    1289                 :    9072640 :         std::swap (x, y);
    1290                 :            :     }
    1291                 :    9072640 :   if (TREE_CODE (x) == SSA_NAME)
    1292                 :   17905800 :     prev_x = SSA_NAME_VALUE (x);
    1293                 :    9072640 :   if (TREE_CODE (y) == SSA_NAME)
    1294                 :    2039610 :     prev_y = SSA_NAME_VALUE (y);
    1295                 :            : 
    1296                 :            :   /* If one of the previous values is invariant, or invariant in more loops
    1297                 :            :      (by depth), then use that.
    1298                 :            :      Otherwise it doesn't matter which value we choose, just so
    1299                 :            :      long as we canonicalize on one value.  */
    1300                 :    9072640 :   if (is_gimple_min_invariant (y))
    1301                 :            :     ;
    1302                 :    1019800 :   else if (is_gimple_min_invariant (x))
    1303                 :            :     prev_x = x, x = y, y = prev_x, prev_x = prev_y;
    1304                 :     900077 :   else if (prev_x && is_gimple_min_invariant (prev_x))
    1305                 :            :     x = y, y = prev_x, prev_x = prev_y;
    1306                 :     845929 :   else if (prev_y)
    1307                 :     517934 :     y = prev_y;
    1308                 :            : 
    1309                 :            :   /* After the swapping, we must have one SSA_NAME.  */
    1310                 :    9072640 :   if (TREE_CODE (x) != SSA_NAME)
    1311                 :            :     return;
    1312                 :            : 
    1313                 :            :   /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
    1314                 :            :      variable compared against zero.  If we're honoring signed zeros,
    1315                 :            :      then we cannot record this value unless we know that the value is
    1316                 :            :      nonzero.  */
    1317                 :    9072640 :   if (HONOR_SIGNED_ZEROS (x)
    1318                 :    9072640 :       && (TREE_CODE (y) != REAL_CST
    1319                 :     160337 :           || real_equal (&dconst0, &TREE_REAL_CST (y))))
    1320                 :        400 :     return;
    1321                 :            : 
    1322                 :    9072240 :   const_and_copies->record_const_or_copy (x, y, prev_x);
    1323                 :            : }
    1324                 :            : 
    1325                 :            : /* Returns true when STMT is a simple iv increment.  It detects the
    1326                 :            :    following situation:
    1327                 :            : 
    1328                 :            :    i_1 = phi (..., i_k)
    1329                 :            :    [...]
    1330                 :            :    i_j = i_{j-1}  for each j : 2 <= j <= k-1
    1331                 :            :    [...]
    1332                 :            :    i_k = i_{k-1} +/- ...  */
    1333                 :            : 
    1334                 :            : bool
    1335                 :   25311600 : simple_iv_increment_p (gimple *stmt)
    1336                 :            : {
    1337                 :   25311600 :   enum tree_code code;
    1338                 :   25311600 :   tree lhs, preinc;
    1339                 :   25311600 :   gimple *phi;
    1340                 :   25311600 :   size_t i;
    1341                 :            : 
    1342                 :   25311600 :   if (gimple_code (stmt) != GIMPLE_ASSIGN)
    1343                 :            :     return false;
    1344                 :            : 
    1345                 :   19497200 :   lhs = gimple_assign_lhs (stmt);
    1346                 :   19497200 :   if (TREE_CODE (lhs) != SSA_NAME)
    1347                 :            :     return false;
    1348                 :            : 
    1349                 :   19497200 :   code = gimple_assign_rhs_code (stmt);
    1350                 :   19497200 :   if (code != PLUS_EXPR
    1351                 :   19497200 :       && code != MINUS_EXPR
    1352                 :   19497200 :       && code != POINTER_PLUS_EXPR)
    1353                 :            :     return false;
    1354                 :            : 
    1355                 :    4247910 :   preinc = gimple_assign_rhs1 (stmt);
    1356                 :    4247910 :   if (TREE_CODE (preinc) != SSA_NAME)
    1357                 :            :     return false;
    1358                 :            : 
    1359                 :    4144700 :   phi = SSA_NAME_DEF_STMT (preinc);
    1360                 :    4156810 :   while (gimple_code (phi) != GIMPLE_PHI)
    1361                 :            :     {
    1362                 :            :       /* Follow trivial copies, but not the DEF used in a back edge,
    1363                 :            :          so that we don't prevent coalescing.  */
    1364                 :    2799870 :       if (!gimple_assign_ssa_name_copy_p (phi))
    1365                 :            :         return false;
    1366                 :      12105 :       preinc = gimple_assign_rhs1 (phi);
    1367                 :      12105 :       phi = SSA_NAME_DEF_STMT (preinc);
    1368                 :            :     }
    1369                 :            : 
    1370                 :    3225370 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    1371                 :    2749440 :     if (gimple_phi_arg_def (phi, i) == lhs)
    1372                 :            :       return true;
    1373                 :            : 
    1374                 :            :   return false;
    1375                 :            : }
    1376                 :            : 
    1377                 :            : /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
    1378                 :            :    successors of BB.  */
    1379                 :            : 
    1380                 :            : static void
    1381                 :   14876800 : cprop_into_successor_phis (basic_block bb,
    1382                 :            :                            class const_and_copies *const_and_copies)
    1383                 :            : {
    1384                 :   14876800 :   edge e;
    1385                 :   14876800 :   edge_iterator ei;
    1386                 :            : 
    1387                 :   35313100 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1388                 :            :     {
    1389                 :   20436300 :       int indx;
    1390                 :   20436300 :       gphi_iterator gsi;
    1391                 :            : 
    1392                 :            :       /* If this is an abnormal edge, then we do not want to copy propagate
    1393                 :            :          into the PHI alternative associated with this edge.  */
    1394                 :   20436300 :       if (e->flags & EDGE_ABNORMAL)
    1395                 :   12013500 :         continue;
    1396                 :            : 
    1397                 :   20425100 :       gsi = gsi_start_phis (e->dest);
    1398                 :   20425100 :       if (gsi_end_p (gsi))
    1399                 :   12002400 :         continue;
    1400                 :            : 
    1401                 :            :       /* We may have an equivalence associated with this edge.  While
    1402                 :            :          we cannot propagate it into non-dominated blocks, we can
    1403                 :            :          propagate them into PHIs in non-dominated blocks.  */
    1404                 :            : 
    1405                 :            :       /* Push the unwind marker so we can reset the const and copies
    1406                 :            :          table back to its original state after processing this edge.  */
    1407                 :    8422780 :       const_and_copies->push_marker ();
    1408                 :            : 
    1409                 :            :       /* Extract and record any simple NAME = VALUE equivalences.
    1410                 :            : 
    1411                 :            :          Don't bother with [01] = COND equivalences, they're not useful
    1412                 :            :          here.  */
    1413                 :    8422780 :       class edge_info *edge_info = (class edge_info *) e->aux;
    1414                 :            : 
    1415                 :    8422780 :       if (edge_info)
    1416                 :            :         {
    1417                 :            :           edge_info::equiv_pair *seq;
    1418                 :    4903140 :           for (int i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i)
    1419                 :            :             {
    1420                 :    1765450 :               tree lhs = seq->first;
    1421                 :    1765450 :               tree rhs = seq->second;
    1422                 :            : 
    1423                 :    1765450 :               if (lhs && TREE_CODE (lhs) == SSA_NAME)
    1424                 :    1765450 :                 const_and_copies->record_const_or_copy (lhs, rhs);
    1425                 :            :             }
    1426                 :            : 
    1427                 :            :         }
    1428                 :            : 
    1429                 :    8422780 :       indx = e->dest_idx;
    1430                 :   21653400 :       for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
    1431                 :            :         {
    1432                 :   13230600 :           tree new_val;
    1433                 :   13230600 :           use_operand_p orig_p;
    1434                 :   13230600 :           tree orig_val;
    1435                 :   13230600 :           gphi *phi = gsi.phi ();
    1436                 :            : 
    1437                 :            :           /* The alternative may be associated with a constant, so verify
    1438                 :            :              it is an SSA_NAME before doing anything with it.  */
    1439                 :   13230600 :           orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
    1440                 :   13230600 :           orig_val = get_use_from_ptr (orig_p);
    1441                 :   13230600 :           if (TREE_CODE (orig_val) != SSA_NAME)
    1442                 :    1561550 :             continue;
    1443                 :            : 
    1444                 :            :           /* If we have *ORIG_P in our constant/copy table, then replace
    1445                 :            :              ORIG_P with its value in our constant/copy table.  */
    1446                 :   23338200 :           new_val = SSA_NAME_VALUE (orig_val);
    1447                 :   11669100 :           if (new_val
    1448                 :   11669100 :               && new_val != orig_val
    1449                 :   11669100 :               && may_propagate_copy (orig_val, new_val))
    1450                 :     400091 :             propagate_value (orig_p, new_val);
    1451                 :            :         }
    1452                 :            : 
    1453                 :    8422780 :       const_and_copies->pop_to_marker ();
    1454                 :            :     }
    1455                 :   14876800 : }
    1456                 :            : 
    1457                 :            : edge
    1458                 :   14876800 : dom_opt_dom_walker::before_dom_children (basic_block bb)
    1459                 :            : {
    1460                 :   14876800 :   gimple_stmt_iterator gsi;
    1461                 :            : 
    1462                 :   14876800 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1463                 :        738 :     fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
    1464                 :            : 
    1465                 :   14876800 :   evrp_range_analyzer.enter (bb);
    1466                 :            : 
    1467                 :            :   /* Push a marker on the stacks of local information so that we know how
    1468                 :            :      far to unwind when we finalize this block.  */
    1469                 :   14876800 :   m_avail_exprs_stack->push_marker ();
    1470                 :   14876800 :   m_const_and_copies->push_marker ();
    1471                 :            : 
    1472                 :   14876800 :   record_equivalences_from_incoming_edge (bb, m_const_and_copies,
    1473                 :            :                                           m_avail_exprs_stack);
    1474                 :            : 
    1475                 :            :   /* PHI nodes can create equivalences too.  */
    1476                 :   14876800 :   record_equivalences_from_phis (bb);
    1477                 :            : 
    1478                 :            :   /* Create equivalences from redundant PHIs.  PHIs are only truly
    1479                 :            :      redundant when they exist in the same block, so push another
    1480                 :            :      marker and unwind right afterwards.  */
    1481                 :   14876800 :   m_avail_exprs_stack->push_marker ();
    1482                 :   20087800 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1483                 :    5211040 :     eliminate_redundant_computations (&gsi, m_const_and_copies,
    1484                 :            :                                       m_avail_exprs_stack);
    1485                 :   14876800 :   m_avail_exprs_stack->pop_to_marker ();
    1486                 :            : 
    1487                 :   14876800 :   edge taken_edge = NULL;
    1488                 :            :   /* Initialize visited flag ahead of us, it has undefined state on
    1489                 :            :      pass entry.  */
    1490                 :  138214000 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1491                 :  108460000 :     gimple_set_visited (gsi_stmt (gsi), false);
    1492                 :  231773000 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
    1493                 :            :     {
    1494                 :            :       /* Do not optimize a stmt twice, substitution might end up with
    1495                 :            :          _3 = _3 which is not valid.  */
    1496                 :  216896000 :       if (gimple_visited_p (gsi_stmt (gsi)))
    1497                 :            :         {
    1498                 :  108435000 :           gsi_next (&gsi);
    1499                 :  108435000 :           continue;
    1500                 :            :         }
    1501                 :            : 
    1502                 :            :       /* Compute range information and optimize the stmt.  */
    1503                 :  108460000 :       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
    1504                 :  108460000 :       bool removed_p = false;
    1505                 :  108460000 :       taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
    1506                 :  108460000 :       if (!removed_p)
    1507                 :  108435000 :         gimple_set_visited (gsi_stmt (gsi), true);
    1508                 :            : 
    1509                 :            :       /* Go back and visit stmts inserted by folding after substituting
    1510                 :            :          into the stmt at gsi.  */
    1511                 :  108460000 :       if (gsi_end_p (gsi))
    1512                 :            :         {
    1513                 :       1671 :           gcc_checking_assert (removed_p);
    1514                 :       3342 :           gsi = gsi_last_bb (bb);
    1515                 :       1398 :           while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi)))
    1516                 :       1671 :             gsi_prev (&gsi);
    1517                 :            :         }
    1518                 :            :       else
    1519                 :            :         {
    1520                 :  108459000 :           do
    1521                 :            :             {
    1522                 :  108459000 :               gsi_prev (&gsi);
    1523                 :            :             }
    1524                 :  108459000 :           while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi)));
    1525                 :            :         }
    1526                 :  108460000 :       if (gsi_end_p (gsi))
    1527                 :   24673700 :         gsi = gsi_start_bb (bb);
    1528                 :            :       else
    1529                 :   96123600 :         gsi_next (&gsi);
    1530                 :            :     }
    1531                 :            : 
    1532                 :            :   /* Now prepare to process dominated blocks.  */
    1533                 :   14876800 :   record_edge_info (bb);
    1534                 :   14876800 :   cprop_into_successor_phis (bb, m_const_and_copies);
    1535                 :   14876800 :   if (taken_edge && !dbg_cnt (dom_unreachable_edges))
    1536                 :          0 :     return NULL;
    1537                 :            : 
    1538                 :            :   return taken_edge;
    1539                 :            : }
    1540                 :            : 
    1541                 :            : /* We have finished processing the dominator children of BB, perform
    1542                 :            :    any finalization actions in preparation for leaving this node in
    1543                 :            :    the dominator tree.  */
    1544                 :            : 
    1545                 :            : void
    1546                 :   14876800 : dom_opt_dom_walker::after_dom_children (basic_block bb)
    1547                 :            : {
    1548                 :   14876800 :   x_vr_values = evrp_range_analyzer.get_vr_values ();
    1549                 :   14876800 :   thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
    1550                 :            :                          m_avail_exprs_stack,
    1551                 :            :                          &evrp_range_analyzer,
    1552                 :            :                          simplify_stmt_for_jump_threading);
    1553                 :   14876800 :   x_vr_values = NULL;
    1554                 :            : 
    1555                 :            :   /* These remove expressions local to BB from the tables.  */
    1556                 :   14876800 :   m_avail_exprs_stack->pop_to_marker ();
    1557                 :   14876800 :   m_const_and_copies->pop_to_marker ();
    1558                 :   14876800 :   evrp_range_analyzer.leave (bb);
    1559                 :   14876800 : }
    1560                 :            : 
    1561                 :            : /* Search for redundant computations in STMT.  If any are found, then
    1562                 :            :    replace them with the variable holding the result of the computation.
    1563                 :            : 
    1564                 :            :    If safe, record this expression into AVAIL_EXPRS_STACK and
    1565                 :            :    CONST_AND_COPIES.  */
    1566                 :            : 
    1567                 :            : static void
    1568                 :   39556600 : eliminate_redundant_computations (gimple_stmt_iterator* gsi,
    1569                 :            :                                   class const_and_copies *const_and_copies,
    1570                 :            :                                   class avail_exprs_stack *avail_exprs_stack)
    1571                 :            : {
    1572                 :   39556600 :   tree expr_type;
    1573                 :   39556600 :   tree cached_lhs;
    1574                 :   39556600 :   tree def;
    1575                 :   39556600 :   bool insert = true;
    1576                 :   39556600 :   bool assigns_var_p = false;
    1577                 :            : 
    1578                 :   39556600 :   gimple *stmt = gsi_stmt (*gsi);
    1579                 :            : 
    1580                 :   39556600 :   if (gimple_code (stmt) == GIMPLE_PHI)
    1581                 :    5211040 :     def = gimple_phi_result (stmt);
    1582                 :            :   else
    1583                 :   34345600 :     def = gimple_get_lhs (stmt);
    1584                 :            : 
    1585                 :            :   /* Certain expressions on the RHS can be optimized away, but cannot
    1586                 :            :      themselves be entered into the hash tables.  */
    1587                 :   39556600 :   if (! def
    1588                 :   34065100 :       || TREE_CODE (def) != SSA_NAME
    1589                 :   24700400 :       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
    1590                 :   19488300 :       || gimple_vdef (stmt)
    1591                 :            :       /* Do not record equivalences for increments of ivs.  This would create
    1592                 :            :          overlapping live ranges for a very questionable gain.  */
    1593                 :   64249600 :       || simple_iv_increment_p (stmt))
    1594                 :            :     insert = false;
    1595                 :            : 
    1596                 :            :   /* Check if the expression has been computed before.  */
    1597                 :   39556600 :   cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, insert, true);
    1598                 :            : 
    1599                 :   39556600 :   opt_stats.num_exprs_considered++;
    1600                 :            : 
    1601                 :            :   /* Get the type of the expression we are trying to optimize.  */
    1602                 :   39556600 :   if (is_gimple_assign (stmt))
    1603                 :            :     {
    1604                 :   28238900 :       expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
    1605                 :   28238900 :       assigns_var_p = true;
    1606                 :            :     }
    1607                 :   11317700 :   else if (gimple_code (stmt) == GIMPLE_COND)
    1608                 :    5470840 :     expr_type = boolean_type_node;
    1609                 :    5846890 :   else if (is_gimple_call (stmt))
    1610                 :            :     {
    1611                 :     615150 :       gcc_assert (gimple_call_lhs (stmt));
    1612                 :     615150 :       expr_type = TREE_TYPE (gimple_call_lhs (stmt));
    1613                 :     615150 :       assigns_var_p = true;
    1614                 :            :     }
    1615                 :    5231740 :   else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
    1616                 :      20694 :     expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt));
    1617                 :    5211040 :   else if (gimple_code (stmt) == GIMPLE_PHI)
    1618                 :            :     /* We can't propagate into a phi, so the logic below doesn't apply.
    1619                 :            :        Instead record an equivalence between the cached LHS and the
    1620                 :            :        PHI result of this statement, provided they are in the same block.
    1621                 :            :        This should be sufficient to kill the redundant phi.  */
    1622                 :            :     {
    1623                 :    5211040 :       if (def && cached_lhs)
    1624                 :       4506 :         const_and_copies->record_const_or_copy (def, cached_lhs);
    1625                 :    5211040 :       return;
    1626                 :            :     }
    1627                 :            :   else
    1628                 :          0 :     gcc_unreachable ();
    1629                 :            : 
    1630                 :   34345600 :   if (!cached_lhs)
    1631                 :            :     return;
    1632                 :            : 
    1633                 :            :   /* It is safe to ignore types here since we have already done
    1634                 :            :      type checking in the hashing and equality routines.  In fact
    1635                 :            :      type checking here merely gets in the way of constant
    1636                 :            :      propagation.  Also, make sure that it is safe to propagate
    1637                 :            :      CACHED_LHS into the expression in STMT.  */
    1638                 :     185858 :   if ((TREE_CODE (cached_lhs) != SSA_NAME
    1639                 :      18253 :        && (assigns_var_p
    1640                 :       3664 :            || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
    1641                 :     185858 :       || may_propagate_copy_into_stmt (stmt, cached_lhs))
    1642                 :            :   {
    1643                 :     185848 :       gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
    1644                 :            :                            || is_gimple_min_invariant (cached_lhs));
    1645                 :            : 
    1646                 :     185848 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1647                 :            :         {
    1648                 :         21 :           fprintf (dump_file, "  Replaced redundant expr '");
    1649                 :         21 :           print_gimple_expr (dump_file, stmt, 0, dump_flags);
    1650                 :         21 :           fprintf (dump_file, "' with '");
    1651                 :         21 :           print_generic_expr (dump_file, cached_lhs, dump_flags);
    1652                 :         21 :           fprintf (dump_file, "'\n");
    1653                 :            :         }
    1654                 :            : 
    1655                 :     185848 :       opt_stats.num_re++;
    1656                 :            : 
    1657                 :     185848 :       if (assigns_var_p
    1658                 :     343538 :           && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
    1659                 :          0 :         cached_lhs = fold_convert (expr_type, cached_lhs);
    1660                 :            : 
    1661                 :     185848 :       propagate_tree_value_into_stmt (gsi, cached_lhs);
    1662                 :            : 
    1663                 :            :       /* Since it is always necessary to mark the result as modified,
    1664                 :            :          perhaps we should move this into propagate_tree_value_into_stmt
    1665                 :            :          itself.  */
    1666                 :     185848 :       gimple_set_modified (gsi_stmt (*gsi), true);
    1667                 :            :   }
    1668                 :            : }
    1669                 :            : 
    1670                 :            : /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
    1671                 :            :    the available expressions table or the const_and_copies table.
    1672                 :            :    Detect and record those equivalences into AVAIL_EXPRS_STACK. 
    1673                 :            : 
    1674                 :            :    We handle only very simple copy equivalences here.  The heavy
    1675                 :            :    lifing is done by eliminate_redundant_computations.  */
    1676                 :            : 
    1677                 :            : static void
    1678                 :   31311700 : record_equivalences_from_stmt (gimple *stmt, int may_optimize_p,
    1679                 :            :                                class avail_exprs_stack *avail_exprs_stack)
    1680                 :            : {
    1681                 :   31311700 :   tree lhs;
    1682                 :   31311700 :   enum tree_code lhs_code;
    1683                 :            : 
    1684                 :   31311700 :   gcc_assert (is_gimple_assign (stmt));
    1685                 :            : 
    1686                 :   31311700 :   lhs = gimple_assign_lhs (stmt);
    1687                 :   31311700 :   lhs_code = TREE_CODE (lhs);
    1688                 :            : 
    1689                 :   31311700 :   if (lhs_code == SSA_NAME
    1690                 :   31311700 :       && gimple_assign_single_p (stmt))
    1691                 :            :     {
    1692                 :    9657020 :       tree rhs = gimple_assign_rhs1 (stmt);
    1693                 :            : 
    1694                 :            :       /* If the RHS of the assignment is a constant or another variable that
    1695                 :            :          may be propagated, register it in the CONST_AND_COPIES table.  We
    1696                 :            :          do not need to record unwind data for this, since this is a true
    1697                 :            :          assignment and not an equivalence inferred from a comparison.  All
    1698                 :            :          uses of this ssa name are dominated by this assignment, so unwinding
    1699                 :            :          just costs time and space.  */
    1700                 :    9657020 :       if (may_optimize_p
    1701                 :    9657020 :           && (TREE_CODE (rhs) == SSA_NAME
    1702                 :    8318690 :               || is_gimple_min_invariant (rhs)))
    1703                 :            :         {
    1704                 :    1030070 :           rhs = dom_valueize (rhs);
    1705                 :            : 
    1706                 :    1030070 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1707                 :            :             {
    1708                 :         26 :               fprintf (dump_file, "==== ASGN ");
    1709                 :         26 :               print_generic_expr (dump_file, lhs);
    1710                 :         26 :               fprintf (dump_file, " = ");
    1711                 :         26 :               print_generic_expr (dump_file, rhs);
    1712                 :         26 :               fprintf (dump_file, "\n");
    1713                 :            :             }
    1714                 :            : 
    1715                 :    1030070 :           set_ssa_name_value (lhs, rhs);
    1716                 :            :         }
    1717                 :            :     }
    1718                 :            : 
    1719                 :            :   /* Make sure we can propagate &x + CST.  */
    1720                 :   31311700 :   if (lhs_code == SSA_NAME
    1721                 :   19419800 :       && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
    1722                 :     876960 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR
    1723                 :   31370200 :       && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST)
    1724                 :            :     {
    1725                 :       2158 :       tree op0 = gimple_assign_rhs1 (stmt);
    1726                 :       2158 :       tree op1 = gimple_assign_rhs2 (stmt);
    1727                 :       2158 :       tree new_rhs
    1728                 :       4316 :         = build1 (ADDR_EXPR, TREE_TYPE (op0),
    1729                 :       2158 :                   fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (op0)),
    1730                 :            :                                unshare_expr (op0), fold_convert (ptr_type_node,
    1731                 :            :                                                                  op1)));
    1732                 :       2158 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1733                 :            :         {
    1734                 :          0 :           fprintf (dump_file, "==== ASGN ");
    1735                 :          0 :           print_generic_expr (dump_file, lhs);
    1736                 :          0 :           fprintf (dump_file, " = ");
    1737                 :          0 :           print_generic_expr (dump_file, new_rhs);
    1738                 :          0 :           fprintf (dump_file, "\n");
    1739                 :            :         }
    1740                 :            : 
    1741                 :       2158 :       set_ssa_name_value (lhs, new_rhs);
    1742                 :            :     }
    1743                 :            : 
    1744                 :            :   /* A memory store, even an aliased store, creates a useful
    1745                 :            :      equivalence.  By exchanging the LHS and RHS, creating suitable
    1746                 :            :      vops and recording the result in the available expression table,
    1747                 :            :      we may be able to expose more redundant loads.  */
    1748                 :   59526000 :   if (!gimple_has_volatile_ops (stmt)
    1749                 :   16495900 :       && gimple_references_memory_p (stmt)
    1750                 :   16495900 :       && gimple_assign_single_p (stmt)
    1751                 :   16495900 :       && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
    1752                 :   12771300 :           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
    1753                 :   39837600 :       && !is_gimple_reg (lhs))
    1754                 :            :     {
    1755                 :    8438420 :       tree rhs = gimple_assign_rhs1 (stmt);
    1756                 :    8438420 :       gassign *new_stmt;
    1757                 :            : 
    1758                 :            :       /* Build a new statement with the RHS and LHS exchanged.  */
    1759                 :    8438420 :       if (TREE_CODE (rhs) == SSA_NAME)
    1760                 :            :         {
    1761                 :            :           /* NOTE tuples.  The call to gimple_build_assign below replaced
    1762                 :            :              a call to build_gimple_modify_stmt, which did not set the
    1763                 :            :              SSA_NAME_DEF_STMT on the LHS of the assignment.  Doing so
    1764                 :            :              may cause an SSA validation failure, as the LHS may be a
    1765                 :            :              default-initialized name and should have no definition.  I'm
    1766                 :            :              a bit dubious of this, as the artificial statement that we
    1767                 :            :              generate here may in fact be ill-formed, but it is simply
    1768                 :            :              used as an internal device in this pass, and never becomes
    1769                 :            :              part of the CFG.  */
    1770                 :    3647440 :           gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
    1771                 :    3647440 :           new_stmt = gimple_build_assign (rhs, lhs);
    1772                 :    3647440 :           SSA_NAME_DEF_STMT (rhs) = defstmt;
    1773                 :            :         }
    1774                 :            :       else
    1775                 :    4790980 :         new_stmt = gimple_build_assign (rhs, lhs);
    1776                 :            : 
    1777                 :   16876800 :       gimple_set_vuse (new_stmt, gimple_vdef (stmt));
    1778                 :            : 
    1779                 :            :       /* Finally enter the statement into the available expression
    1780                 :            :          table.  */
    1781                 :    8438420 :       avail_exprs_stack->lookup_avail_expr (new_stmt, true, true);
    1782                 :            :     }
    1783                 :   31311700 : }
    1784                 :            : 
    1785                 :            : /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
    1786                 :            :    CONST_AND_COPIES.  */
    1787                 :            : 
    1788                 :            : static void
    1789                 :   48056200 : cprop_operand (gimple *stmt, use_operand_p op_p, vr_values *vr_values)
    1790                 :            : {
    1791                 :   48056200 :   tree val;
    1792                 :   48056200 :   tree op = USE_FROM_PTR (op_p);
    1793                 :            : 
    1794                 :            :   /* If the operand has a known constant value or it is known to be a
    1795                 :            :      copy of some other variable, use the value or copy stored in
    1796                 :            :      CONST_AND_COPIES.  */
    1797                 :   96112300 :   val = SSA_NAME_VALUE (op);
    1798                 :   31383400 :   if (!val)
    1799                 :   46211200 :     val = vr_values->op_with_constant_singleton_value_range (op);
    1800                 :            : 
    1801                 :   48056200 :   if (val && val != op)
    1802                 :            :     {
    1803                 :            :       /* Do not replace hard register operands in asm statements.  */
    1804                 :    1847570 :       if (gimple_code (stmt) == GIMPLE_ASM
    1805                 :    1847570 :           && !may_propagate_copy_into_asm (op))
    1806                 :            :         return;
    1807                 :            : 
    1808                 :            :       /* Certain operands are not allowed to be copy propagated due
    1809                 :            :          to their interaction with exception handling and some GCC
    1810                 :            :          extensions.  */
    1811                 :    1847570 :       if (!may_propagate_copy (op, val))
    1812                 :            :         return;
    1813                 :            : 
    1814                 :            :       /* Do not propagate copies into BIVs.
    1815                 :            :          See PR23821 and PR62217 for how this can disturb IV and
    1816                 :            :          number of iteration analysis.  */
    1817                 :    1846130 :       if (TREE_CODE (val) != INTEGER_CST)
    1818                 :            :         {
    1819                 :    1587380 :           gimple *def = SSA_NAME_DEF_STMT (op);
    1820                 :    1587380 :           if (gimple_code (def) == GIMPLE_PHI
    1821                 :    1587380 :               && gimple_bb (def)->loop_father->header == gimple_bb (def))
    1822                 :            :             return;
    1823                 :            :         }
    1824                 :            : 
    1825                 :            :       /* Dump details.  */
    1826                 :    1840790 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1827                 :            :         {
    1828                 :         31 :           fprintf (dump_file, "  Replaced '");
    1829                 :         31 :           print_generic_expr (dump_file, op, dump_flags);
    1830                 :         31 :           fprintf (dump_file, "' with %s '",
    1831                 :         31 :                    (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
    1832                 :         31 :           print_generic_expr (dump_file, val, dump_flags);
    1833                 :         31 :           fprintf (dump_file, "'\n");
    1834                 :            :         }
    1835                 :            : 
    1836                 :    1840790 :       if (TREE_CODE (val) != SSA_NAME)
    1837                 :     308794 :         opt_stats.num_const_prop++;
    1838                 :            :       else
    1839                 :    1531990 :         opt_stats.num_copy_prop++;
    1840                 :            : 
    1841                 :    1840790 :       propagate_value (op_p, val);
    1842                 :            : 
    1843                 :            :       /* And note that we modified this statement.  This is now
    1844                 :            :          safe, even if we changed virtual operands since we will
    1845                 :            :          rescan the statement and rewrite its operands again.  */
    1846                 :    1840790 :       gimple_set_modified (stmt, true);
    1847                 :            :     }
    1848                 :            : }
    1849                 :            : 
    1850                 :            : /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
    1851                 :            :    known value for that SSA_NAME (or NULL if no value is known).
    1852                 :            : 
    1853                 :            :    Propagate values from CONST_AND_COPIES into the uses, vuses and
    1854                 :            :    vdef_ops of STMT.  */
    1855                 :            : 
    1856                 :            : static void
    1857                 :  108460000 : cprop_into_stmt (gimple *stmt, vr_values *vr_values)
    1858                 :            : {
    1859                 :  108460000 :   use_operand_p op_p;
    1860                 :  108460000 :   ssa_op_iter iter;
    1861                 :  108460000 :   tree last_copy_propagated_op = NULL;
    1862                 :            : 
    1863                 :  156517000 :   FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE)
    1864                 :            :     {
    1865                 :   48056600 :       tree old_op = USE_FROM_PTR (op_p);
    1866                 :            : 
    1867                 :            :       /* If we have A = B and B = A in the copy propagation tables
    1868                 :            :          (due to an equality comparison), avoid substituting B for A
    1869                 :            :          then A for B in the trivially discovered cases.   This allows
    1870                 :            :          optimization of statements were A and B appear as input
    1871                 :            :          operands.  */
    1872                 :   48056600 :       if (old_op != last_copy_propagated_op)
    1873                 :            :         {
    1874                 :   48056200 :           cprop_operand (stmt, op_p, vr_values);
    1875                 :            : 
    1876                 :   48056200 :           tree new_op = USE_FROM_PTR (op_p);
    1877                 :   48056200 :           if (new_op != old_op && TREE_CODE (new_op) == SSA_NAME)
    1878                 :    1531990 :             last_copy_propagated_op = new_op;
    1879                 :            :         }
    1880                 :            :     }
    1881                 :  108460000 : }
    1882                 :            : 
    1883                 :            : /* If STMT contains a relational test, try to convert it into an
    1884                 :            :    equality test if there is only a single value which can ever
    1885                 :            :    make the test true.
    1886                 :            : 
    1887                 :            :    For example, if the expression hash table contains:
    1888                 :            : 
    1889                 :            :     TRUE = (i <= 1)
    1890                 :            : 
    1891                 :            :    And we have a test within statement of i >= 1, then we can safely
    1892                 :            :    rewrite the test as i == 1 since there only a single value where
    1893                 :            :    the test is true.
    1894                 :            : 
    1895                 :            :    This is similar to code in VRP.  */
    1896                 :            : 
    1897                 :            : static void
    1898                 :   34320400 : test_for_singularity (gimple *stmt, gcond *dummy_cond,
    1899                 :            :                       avail_exprs_stack *avail_exprs_stack)
    1900                 :            : {
    1901                 :            :   /* We want to support gimple conditionals as well as assignments
    1902                 :            :      where the RHS contains a conditional.  */
    1903                 :   34320400 :   if (is_gimple_assign (stmt) || gimple_code (stmt) == GIMPLE_COND)
    1904                 :            :     {
    1905                 :   33685200 :       enum tree_code code = ERROR_MARK;
    1906                 :   33685200 :       tree lhs, rhs;
    1907                 :            : 
    1908                 :            :       /* Extract the condition of interest from both forms we support.  */
    1909                 :   33685200 :       if (is_gimple_assign (stmt))
    1910                 :            :         {
    1911                 :   28214400 :           code = gimple_assign_rhs_code (stmt);
    1912                 :   28214400 :           lhs = gimple_assign_rhs1 (stmt);
    1913                 :   28214400 :           rhs = gimple_assign_rhs2 (stmt);
    1914                 :            :         }
    1915                 :    5470840 :       else if (gimple_code (stmt) == GIMPLE_COND)
    1916                 :            :         {
    1917                 :    5470840 :           code = gimple_cond_code (as_a <gcond *> (stmt));
    1918                 :    5470840 :           lhs = gimple_cond_lhs (as_a <gcond *> (stmt));
    1919                 :    5470840 :           rhs = gimple_cond_rhs (as_a <gcond *> (stmt));
    1920                 :            :         }
    1921                 :            : 
    1922                 :            :       /* We're looking for a relational test using LE/GE.  Also note we can
    1923                 :            :          canonicalize LT/GT tests against constants into LE/GT tests.  */
    1924                 :   33685200 :       if (code == LE_EXPR || code == GE_EXPR
    1925                 :   33216600 :           || ((code == LT_EXPR || code == GT_EXPR)
    1926                 :     925850 :                && TREE_CODE (rhs) == INTEGER_CST))
    1927                 :            :         {
    1928                 :            :           /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR.  */
    1929                 :     851339 :           if (code == LT_EXPR)
    1930                 :      65446 :             rhs = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs),
    1931                 :            :                                rhs, build_int_cst (TREE_TYPE (rhs), 1));
    1932                 :            : 
    1933                 :     851339 :           if (code == GT_EXPR)
    1934                 :     317301 :             rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs),
    1935                 :            :                                rhs, build_int_cst (TREE_TYPE (rhs), 1));
    1936                 :            : 
    1937                 :            :           /* Determine the code we want to check for in the hash table.  */
    1938                 :     851339 :           enum tree_code test_code;
    1939                 :     851339 :           if (code == GE_EXPR || code == GT_EXPR)
    1940                 :            :             test_code = LE_EXPR;
    1941                 :            :           else
    1942                 :     335588 :             test_code = GE_EXPR;
    1943                 :            : 
    1944                 :            :           /* Update the dummy statement so we can query the hash tables.  */
    1945                 :     851339 :           gimple_cond_set_code (dummy_cond, test_code);
    1946                 :     851339 :           gimple_cond_set_lhs (dummy_cond, lhs);
    1947                 :     851339 :           gimple_cond_set_rhs (dummy_cond, rhs);
    1948                 :     851339 :           tree cached_lhs
    1949                 :     851339 :             = avail_exprs_stack->lookup_avail_expr (dummy_cond, false, false);
    1950                 :            : 
    1951                 :            :           /* If the lookup returned 1 (true), then the expression we
    1952                 :            :              queried was in the hash table.  As a result there is only
    1953                 :            :              one value that makes the original conditional true.  Update
    1954                 :            :              STMT accordingly.  */
    1955                 :     851339 :           if (cached_lhs && integer_onep (cached_lhs))
    1956                 :            :             {
    1957                 :        920 :               if (is_gimple_assign (stmt))
    1958                 :            :                 {
    1959                 :         92 :                   gimple_assign_set_rhs_code (stmt, EQ_EXPR);
    1960                 :         92 :                   gimple_assign_set_rhs2 (stmt, rhs);
    1961                 :         92 :                   gimple_set_modified (stmt, true);
    1962                 :            :                 }
    1963                 :            :               else
    1964                 :            :                 {
    1965                 :        828 :                   gimple_set_modified (stmt, true);
    1966                 :        828 :                   gimple_cond_set_code (as_a <gcond *> (stmt), EQ_EXPR);
    1967                 :        828 :                   gimple_cond_set_rhs (as_a <gcond *> (stmt), rhs);
    1968                 :        828 :                   gimple_set_modified (stmt, true);
    1969                 :            :                 }
    1970                 :            :             }
    1971                 :            :         }
    1972                 :            :     }
    1973                 :   34320400 : }
    1974                 :            : 
    1975                 :            : /* Optimize the statement in block BB pointed to by iterator SI.
    1976                 :            : 
    1977                 :            :    We try to perform some simplistic global redundancy elimination and
    1978                 :            :    constant propagation:
    1979                 :            : 
    1980                 :            :    1- To detect global redundancy, we keep track of expressions that have
    1981                 :            :       been computed in this block and its dominators.  If we find that the
    1982                 :            :       same expression is computed more than once, we eliminate repeated
    1983                 :            :       computations by using the target of the first one.
    1984                 :            : 
    1985                 :            :    2- Constant values and copy assignments.  This is used to do very
    1986                 :            :       simplistic constant and copy propagation.  When a constant or copy
    1987                 :            :       assignment is found, we map the value on the RHS of the assignment to
    1988                 :            :       the variable in the LHS in the CONST_AND_COPIES table.
    1989                 :            : 
    1990                 :            :    3- Very simple redundant store elimination is performed.
    1991                 :            : 
    1992                 :            :    4- We can simplify a condition to a constant or from a relational
    1993                 :            :       condition to an equality condition.  */
    1994                 :            : 
    1995                 :            : edge
    1996                 :  108460000 : dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator *si,
    1997                 :            :                                    bool *removed_p)
    1998                 :            : {
    1999                 :  108460000 :   gimple *stmt, *old_stmt;
    2000                 :  108460000 :   bool may_optimize_p;
    2001                 :  108460000 :   bool modified_p = false;
    2002                 :  108460000 :   bool was_noreturn;
    2003                 :  108460000 :   edge retval = NULL;
    2004                 :            : 
    2005                 :  108460000 :   old_stmt = stmt = gsi_stmt (*si);
    2006                 :  108460000 :   was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt);
    2007                 :            : 
    2008                 :  108460000 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2009                 :            :     {
    2010                 :       1485 :       fprintf (dump_file, "Optimizing statement ");
    2011                 :       1485 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2012                 :            :     }
    2013                 :            : 
    2014                 :  108460000 :   update_stmt_if_modified (stmt);
    2015                 :  108460000 :   opt_stats.num_stmts++;
    2016                 :            : 
    2017                 :            :   /* Const/copy propagate into USES, VUSES and the RHS of VDEFs.  */
    2018                 :  108460000 :   cprop_into_stmt (stmt, evrp_range_analyzer.get_vr_values ());
    2019                 :            : 
    2020                 :            :   /* If the statement has been modified with constant replacements,
    2021                 :            :      fold its RHS before checking for redundant computations.  */
    2022                 :  216713000 :   if (gimple_modified_p (stmt))
    2023                 :            :     {
    2024                 :    1785900 :       tree rhs = NULL;
    2025                 :            : 
    2026                 :            :       /* Try to fold the statement making sure that STMT is kept
    2027                 :            :          up to date.  */
    2028                 :    1785900 :       if (fold_stmt (si))
    2029                 :            :         {
    2030                 :     179376 :           stmt = gsi_stmt (*si);
    2031                 :     179376 :           gimple_set_modified (stmt, true);
    2032                 :            : 
    2033                 :     179376 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2034                 :            :             {
    2035                 :         20 :               fprintf (dump_file, "  Folded to: ");
    2036                 :         20 :               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2037                 :            :             }
    2038                 :            :         }
    2039                 :            : 
    2040                 :            :       /* We only need to consider cases that can yield a gimple operand.  */
    2041                 :    1785900 :       if (gimple_assign_single_p (stmt))
    2042                 :     716362 :         rhs = gimple_assign_rhs1 (stmt);
    2043                 :    1069540 :       else if (gimple_code (stmt) == GIMPLE_GOTO)
    2044                 :          1 :         rhs = gimple_goto_dest (stmt);
    2045                 :  108462000 :       else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
    2046                 :            :         /* This should never be an ADDR_EXPR.  */
    2047                 :       1099 :         rhs = gimple_switch_index (swtch_stmt);
    2048                 :            : 
    2049                 :     717462 :       if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
    2050                 :      28426 :         recompute_tree_invariant_for_addr_expr (rhs);
    2051                 :            : 
    2052                 :            :       /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
    2053                 :            :          even if fold_stmt updated the stmt already and thus cleared
    2054                 :            :          gimple_modified_p flag on it.  */
    2055                 :            :       modified_p = true;
    2056                 :            :     }
    2057                 :            : 
    2058                 :            :   /* Check for redundant computations.  Do this optimization only
    2059                 :            :      for assignments that have no volatile ops and conditionals.  */
    2060                 :  108460000 :   may_optimize_p = (!gimple_has_side_effects (stmt)
    2061                 :  108460000 :                     && (is_gimple_assign (stmt)
    2062                 :   70594300 :                         || (is_gimple_call (stmt)
    2063                 :     615321 :                             && gimple_call_lhs (stmt) != NULL_TREE)
    2064                 :   69979100 :                         || gimple_code (stmt) == GIMPLE_COND
    2065                 :   64490600 :                         || gimple_code (stmt) == GIMPLE_SWITCH));
    2066                 :            : 
    2067                 :   34363300 :   if (may_optimize_p)
    2068                 :            :     {
    2069                 :   34363300 :       if (gimple_code (stmt) == GIMPLE_CALL)
    2070                 :            :         {
    2071                 :            :           /* Resolve __builtin_constant_p.  If it hasn't been
    2072                 :            :              folded to integer_one_node by now, it's fairly
    2073                 :            :              certain that the value simply isn't constant.  */
    2074                 :     615178 :           tree callee = gimple_call_fndecl (stmt);
    2075                 :     615178 :           if (callee
    2076                 :     615178 :               && fndecl_built_in_p (callee, BUILT_IN_CONSTANT_P))
    2077                 :            :             {
    2078                 :         28 :               propagate_tree_value_into_stmt (si, integer_zero_node);
    2079                 :         28 :               stmt = gsi_stmt (*si);
    2080                 :            :             }
    2081                 :            :         }
    2082                 :            : 
    2083                 :   34363300 :       if (gimple_code (stmt) == GIMPLE_COND)
    2084                 :            :         {
    2085                 :    5488530 :           tree lhs = gimple_cond_lhs (stmt);
    2086                 :    5488530 :           tree rhs = gimple_cond_rhs (stmt);
    2087                 :            : 
    2088                 :            :           /* If the LHS has a range [0..1] and the RHS has a range ~[0..1],
    2089                 :            :              then this conditional is computable at compile time.  We can just
    2090                 :            :              shove either 0 or 1 into the LHS, mark the statement as modified
    2091                 :            :              and all the right things will just happen below.
    2092                 :            : 
    2093                 :            :              Note this would apply to any case where LHS has a range
    2094                 :            :              narrower than its type implies and RHS is outside that
    2095                 :            :              narrower range.  Future work.  */
    2096                 :    5488530 :           if (TREE_CODE (lhs) == SSA_NAME
    2097                 :    5374830 :               && ssa_name_has_boolean_range (lhs)
    2098                 :     748811 :               && TREE_CODE (rhs) == INTEGER_CST
    2099                 :    6215650 :               && ! (integer_zerop (rhs) || integer_onep (rhs)))
    2100                 :            :             {
    2101                 :         22 :               gimple_cond_set_lhs (as_a <gcond *> (stmt),
    2102                 :         11 :                                    fold_convert (TREE_TYPE (lhs),
    2103                 :            :                                                  integer_zero_node));
    2104                 :         11 :               gimple_set_modified (stmt, true);
    2105                 :            :             }
    2106                 :    5488520 :           else if (TREE_CODE (lhs) == SSA_NAME)
    2107                 :            :             {
    2108                 :            :               /* Exploiting EVRP data is not yet fully integrated into DOM
    2109                 :            :                  but we need to do something for this case to avoid regressing
    2110                 :            :                  udr4.f90 and new1.C which have unexecutable blocks with
    2111                 :            :                  undefined behavior that get diagnosed if they're left in the
    2112                 :            :                  IL because we've attached range information to new
    2113                 :            :                  SSA_NAMES.  */
    2114                 :    5374820 :               update_stmt_if_modified (stmt);
    2115                 :    5374820 :               edge taken_edge = NULL;
    2116                 :    5374820 :               evrp_range_analyzer.vrp_visit_cond_stmt (as_a <gcond *> (stmt),
    2117                 :            :                                                        &taken_edge);
    2118                 :    5374820 :               if (taken_edge)
    2119                 :            :                 {
    2120                 :      17693 :                   if (taken_edge->flags & EDGE_TRUE_VALUE)
    2121                 :       8847 :                     gimple_cond_make_true (as_a <gcond *> (stmt));
    2122                 :       8846 :                   else if (taken_edge->flags & EDGE_FALSE_VALUE)
    2123                 :       8846 :                     gimple_cond_make_false (as_a <gcond *> (stmt));
    2124                 :            :                   else
    2125                 :          0 :                     gcc_unreachable ();
    2126                 :      17693 :                   gimple_set_modified (stmt, true);
    2127                 :      17693 :                   update_stmt (stmt);
    2128                 :      17693 :                   cfg_altered = true;
    2129                 :      17693 :                   return taken_edge;
    2130                 :            :                 }
    2131                 :            :             }
    2132                 :            :         }
    2133                 :            : 
    2134                 :   34345600 :       update_stmt_if_modified (stmt);
    2135                 :   34345600 :       eliminate_redundant_computations (si, m_const_and_copies,
    2136                 :            :                                         m_avail_exprs_stack);
    2137                 :   34345600 :       stmt = gsi_stmt (*si);
    2138                 :            : 
    2139                 :            :       /* Perform simple redundant store elimination.  */
    2140                 :   34345600 :       if (gimple_assign_single_p (stmt)
    2141                 :   18476700 :           && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
    2142                 :            :         {
    2143                 :    9359390 :           tree lhs = gimple_assign_lhs (stmt);
    2144                 :    9359390 :           tree rhs = gimple_assign_rhs1 (stmt);
    2145                 :    9359390 :           tree cached_lhs;
    2146                 :    9359390 :           gassign *new_stmt;
    2147                 :    9359390 :           rhs = dom_valueize (rhs);
    2148                 :            :           /* Build a new statement with the RHS and LHS exchanged.  */
    2149                 :    9359390 :           if (TREE_CODE (rhs) == SSA_NAME)
    2150                 :            :             {
    2151                 :    3669960 :               gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
    2152                 :    3669960 :               new_stmt = gimple_build_assign (rhs, lhs);
    2153                 :    3669960 :               SSA_NAME_DEF_STMT (rhs) = defstmt;
    2154                 :            :             }
    2155                 :            :           else
    2156                 :    5689430 :             new_stmt = gimple_build_assign (rhs, lhs);
    2157                 :   18718800 :           gimple_set_vuse (new_stmt, gimple_vuse (stmt));
    2158                 :    9359390 :           expr_hash_elt *elt = NULL;
    2159                 :    9359390 :           cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false,
    2160                 :            :                                                                false, &elt);
    2161                 :    9359390 :           if (cached_lhs
    2162                 :     488474 :               && operand_equal_p (rhs, cached_lhs, 0)
    2163                 :    9385800 :               && refs_same_for_tbaa_p (elt->expr ()->kind == EXPR_SINGLE
    2164                 :      26416 :                                        ? elt->expr ()->ops.single.rhs
    2165                 :            :                                        : NULL_TREE, lhs))
    2166                 :            :             {
    2167                 :      25178 :               basic_block bb = gimple_bb (stmt);
    2168                 :      25178 :               unlink_stmt_vdef (stmt);
    2169                 :      25178 :               if (gsi_remove (si, true))
    2170                 :            :                 {
    2171                 :          0 :                   bitmap_set_bit (need_eh_cleanup, bb->index);
    2172                 :          0 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    2173                 :          0 :                     fprintf (dump_file, "  Flagged to clear EH edges.\n");
    2174                 :            :                 }
    2175                 :      25178 :               release_defs (stmt);
    2176                 :      25178 :               *removed_p = true;
    2177                 :      25178 :               return retval;
    2178                 :            :             }
    2179                 :            :         }
    2180                 :            : 
    2181                 :            :       /* If this statement was not redundant, we may still be able to simplify
    2182                 :            :          it, which may in turn allow other part of DOM or other passes to do
    2183                 :            :          a better job.  */
    2184                 :   34320400 :       test_for_singularity (stmt, m_dummy_cond, m_avail_exprs_stack);
    2185                 :            :     }
    2186                 :            : 
    2187                 :            :   /* Record any additional equivalences created by this statement.  */
    2188                 :  108418000 :   if (is_gimple_assign (stmt))
    2189                 :   31311700 :     record_equivalences_from_stmt (stmt, may_optimize_p, m_avail_exprs_stack);
    2190                 :            : 
    2191                 :            :   /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
    2192                 :            :      know where it goes.  */
    2193                 :  216835000 :   if (gimple_modified_p (stmt) || modified_p)
    2194                 :            :     {
    2195                 :    1910290 :       tree val = NULL;
    2196                 :            : 
    2197                 :    1910290 :       if (gimple_code (stmt) == GIMPLE_COND)
    2198                 :     237331 :         val = fold_binary_loc (gimple_location (stmt),
    2199                 :            :                                gimple_cond_code (stmt), boolean_type_node,
    2200                 :            :                                gimple_cond_lhs (stmt),
    2201                 :            :                                gimple_cond_rhs (stmt));
    2202                 :    1672960 :       else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
    2203                 :       1099 :         val = gimple_switch_index (swtch_stmt);
    2204                 :            : 
    2205                 :     238430 :       if (val && TREE_CODE (val) == INTEGER_CST)
    2206                 :            :         {
    2207                 :      29913 :           retval = find_taken_edge (bb, val);
    2208                 :      29913 :           if (retval)
    2209                 :            :             {
    2210                 :            :               /* Fix the condition to be either true or false.  */
    2211                 :      29913 :               if (gimple_code (stmt) == GIMPLE_COND)
    2212                 :            :                 {
    2213                 :      29905 :                   if (integer_zerop (val))
    2214                 :      16236 :                     gimple_cond_make_false (as_a <gcond *> (stmt));
    2215                 :      13669 :                   else if (integer_onep (val))
    2216                 :      13669 :                     gimple_cond_make_true (as_a <gcond *> (stmt));
    2217                 :            :                   else
    2218                 :          0 :                     gcc_unreachable ();
    2219                 :            : 
    2220                 :      29905 :                   gimple_set_modified (stmt, true);
    2221                 :            :                 }
    2222                 :            : 
    2223                 :            :               /* Further simplifications may be possible.  */
    2224                 :      29913 :               cfg_altered = true;
    2225                 :            :             }
    2226                 :            :         }
    2227                 :            : 
    2228                 :    1910290 :       update_stmt_if_modified (stmt);
    2229                 :            : 
    2230                 :            :       /* If we simplified a statement in such a way as to be shown that it
    2231                 :            :          cannot trap, update the eh information and the cfg to match.  */
    2232                 :    1910290 :       if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
    2233                 :            :         {
    2234                 :       1013 :           bitmap_set_bit (need_eh_cleanup, bb->index);
    2235                 :       1013 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2236                 :          0 :             fprintf (dump_file, "  Flagged to clear EH edges.\n");
    2237                 :            :         }
    2238                 :            : 
    2239                 :    1910290 :       if (!was_noreturn
    2240                 :    1910290 :           && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
    2241                 :          7 :         need_noreturn_fixup.safe_push (stmt);
    2242                 :            :     }
    2243                 :            :   return retval;
    2244                 :            : }

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.