LCOV - code coverage report
Current view: top level - gcc - tree-ssa-dom.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.9 % 960 930
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 41 41
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* SSA Dominator optimizations for trees
       2              :    Copyright (C) 2001-2026 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-iterator.h"
      34              : #include "gimple-fold.h"
      35              : #include "tree-eh.h"
      36              : #include "tree-inline.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 "tree-cfgcleanup.h"
      46              : #include "dbgcnt.h"
      47              : #include "alloc-pool.h"
      48              : #include "tree-vrp.h"
      49              : #include "vr-values.h"
      50              : #include "gimple-range.h"
      51              : #include "gimple-range-path.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              : /* Bitmap of SSA names that have no use in an assignment or call that
      98              :    defines an SSA name, so back_propagate_equivalences has nothing to do
      99              :    for them.  A bit is cleared when DOM adds such a use.  */
     100              : static bitmap names_without_foldable_uses;
     101              : 
     102              : /* Statistics for dominator optimizations.  */
     103              : struct opt_stats_d
     104              : {
     105              :   long num_stmts;
     106              :   long num_exprs_considered;
     107              :   long num_re;
     108              :   long num_const_prop;
     109              :   long num_copy_prop;
     110              : };
     111              : 
     112              : static struct opt_stats_d opt_stats;
     113              : 
     114              : /* Local functions.  */
     115              : static void record_equality (tree, tree, class const_and_copies *);
     116              : static void record_equivalences_from_phis (basic_block);
     117              : static void dump_dominator_optimization_stats (FILE *file,
     118              :                                                hash_table<expr_elt_hasher> *);
     119              : static void record_temporary_equivalences (edge, class const_and_copies *,
     120              :                                            class avail_exprs_stack *, bitmap);
     121              : 
     122              : /* Constructor for EDGE_INFO.  An EDGE_INFO instance is always
     123              :    associated with an edge E.  */
     124              : 
     125     36924339 : edge_info::edge_info (edge e)
     126              : {
     127              :   /* Free the old one associated with E, if it exists and
     128              :      associate our new object with E.  */
     129     36924339 :   free_dom_edge_info (e);
     130     36924339 :   e->aux = this;
     131              : 
     132              :   /* And initialize the embedded vectors.  */
     133     36924339 :   simple_equivalences = vNULL;
     134     36924339 :   cond_equivalences = vNULL;
     135     36924339 : }
     136              : 
     137              : /* Destructor just needs to release the vectors.  */
     138              : 
     139     36924339 : edge_info::~edge_info (void)
     140              : {
     141     36924339 :   this->cond_equivalences.release ();
     142     36924339 :   this->simple_equivalences.release ();
     143     36924339 : }
     144              : 
     145              : /* NAME is known to have the value VALUE, which must be a constant.
     146              : 
     147              :    Walk through its use-def chain to see if there are other equivalences
     148              :    we might be able to derive.
     149              : 
     150              :    RECURSION_LIMIT controls how far back we recurse through the use-def
     151              :    chains.  */
     152              : 
     153              : void
     154     13488498 : edge_info::derive_equivalences (tree name, tree value, int recursion_limit)
     155              : {
     156     15637719 :   if (TREE_CODE (name) != SSA_NAME || TREE_CODE (value) != INTEGER_CST)
     157              :     return;
     158              : 
     159              :   /* This records the equivalence for the toplevel object.  Do
     160              :      this before checking the recursion limit.  */
     161     15637427 :   simple_equivalences.safe_push (equiv_pair (name, value));
     162              : 
     163              :   /* Limit how far up the use-def chains we are willing to walk.  */
     164     15637427 :   if (recursion_limit == 0)
     165              :     return;
     166              : 
     167              :   /* We can walk up the use-def chains to potentially find more
     168              :      equivalences.  */
     169     15624503 :   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
     170     15624503 :   if (is_gimple_assign (def_stmt))
     171              :     {
     172     10220721 :       enum tree_code code = gimple_assign_rhs_code (def_stmt);
     173     10220721 :       switch (code)
     174              :         {
     175              :         /* If the result of an OR is zero, then its operands are, too.  */
     176       588216 :         case BIT_IOR_EXPR:
     177       588216 :           if (integer_zerop (value))
     178              :             {
     179       322966 :               tree rhs1 = gimple_assign_rhs1 (def_stmt);
     180       322966 :               tree rhs2 = gimple_assign_rhs2 (def_stmt);
     181              : 
     182       322966 :               value = build_zero_cst (TREE_TYPE (rhs1));
     183       322966 :               derive_equivalences (rhs1, value, recursion_limit - 1);
     184       322966 :               value = build_zero_cst (TREE_TYPE (rhs2));
     185       322966 :               derive_equivalences (rhs2, value, recursion_limit - 1);
     186              :             }
     187              :           break;
     188              : 
     189              :         /* If the result of an AND is nonzero, then its operands are, too.  */
     190      1104107 :         case BIT_AND_EXPR:
     191      1104107 :           if (!integer_zerop (value))
     192              :             {
     193       466373 :               tree rhs1 = gimple_assign_rhs1 (def_stmt);
     194       466373 :               tree rhs2 = gimple_assign_rhs2 (def_stmt);
     195              : 
     196              :               /* If either operand has a boolean range, then we
     197              :                  know its value must be one, otherwise we just know it
     198              :                  is nonzero.  The former is clearly useful, I haven't
     199              :                  seen cases where the latter is helpful yet.  */
     200       466373 :               if (TREE_CODE (rhs1) == SSA_NAME)
     201              :                 {
     202       466373 :                   if (ssa_name_has_boolean_range (rhs1))
     203              :                     {
     204       291379 :                       value = build_one_cst (TREE_TYPE (rhs1));
     205       291379 :                       derive_equivalences (rhs1, value, recursion_limit - 1);
     206              :                     }
     207              :                 }
     208       466373 :               if (TREE_CODE (rhs2) == SSA_NAME)
     209              :                 {
     210       294064 :                   if (ssa_name_has_boolean_range (rhs2))
     211              :                     {
     212       291096 :                       value = build_one_cst (TREE_TYPE (rhs2));
     213       291096 :                       derive_equivalences (rhs2, value, recursion_limit - 1);
     214              :                     }
     215              :                 }
     216              :             }
     217              :           break;
     218              : 
     219              :         /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
     220              :            set via a widening type conversion, then we may be able to record
     221              :            additional equivalences.  */
     222       446836 :         CASE_CONVERT:
     223       446836 :           {
     224       446836 :             tree rhs = gimple_assign_rhs1 (def_stmt);
     225       446836 :             tree rhs_type = TREE_TYPE (rhs);
     226       446836 :             if (INTEGRAL_TYPE_P (rhs_type)
     227       443849 :                 && (TYPE_PRECISION (TREE_TYPE (name))
     228       443849 :                     >= TYPE_PRECISION (rhs_type))
     229       691969 :                 && int_fits_type_p (value, rhs_type))
     230       234648 :               derive_equivalences (rhs,
     231              :                                    fold_convert (rhs_type, value),
     232              :                                    recursion_limit - 1);
     233              :             break;
     234              :           }
     235              : 
     236              :         /* We can invert the operation of these codes trivially if
     237              :            one of the RHS operands is a constant to produce a known
     238              :            value for the other RHS operand.  */
     239      1065823 :         case POINTER_PLUS_EXPR:
     240      1065823 :         case PLUS_EXPR:
     241      1065823 :           {
     242      1065823 :             tree rhs1 = gimple_assign_rhs1 (def_stmt);
     243      1065823 :             tree rhs2 = gimple_assign_rhs2 (def_stmt);
     244              : 
     245              :             /* If the second argument is a constant, then we can compute
     246              :                a constant value for the first one.  */
     247      1065823 :             if (TREE_CODE (rhs2) == INTEGER_CST
     248      1011079 :                 && TREE_CODE (rhs1) == SSA_NAME)
     249      1011077 :               derive_equivalences (rhs1,
     250      1011077 :                                    fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
     251              :                                                 value, rhs2),
     252              :                                    recursion_limit - 1);
     253              :             break;
     254              :           }
     255              : 
     256              :         /* If one of the operands is a constant, then we can compute
     257              :            the value of the other operand.  If both operands are
     258              :            SSA_NAMEs, then they must be equal if the result is zero.  */
     259        75628 :         case MINUS_EXPR:
     260        75628 :           {
     261        75628 :             tree rhs1 = gimple_assign_rhs1 (def_stmt);
     262        75628 :             tree rhs2 = gimple_assign_rhs2 (def_stmt);
     263              : 
     264              :             /* If either argument is a constant, then we can compute
     265              :                a constant value for the nonconstant argument.  */
     266        75628 :             if (TREE_CODE (rhs1) == INTEGER_CST
     267          682 :                 && TREE_CODE (rhs2) == SSA_NAME)
     268          682 :               derive_equivalences (rhs2,
     269          682 :                                    fold_binary (MINUS_EXPR, TREE_TYPE (rhs1),
     270              :                                                 rhs1, value),
     271              :                                    recursion_limit - 1);
     272        74946 :             else if (TREE_CODE (rhs2) == INTEGER_CST
     273        30242 :                      && TREE_CODE (rhs1) == SSA_NAME)
     274        30242 :               derive_equivalences (rhs1,
     275        30242 :                                    fold_binary (PLUS_EXPR, TREE_TYPE (rhs1),
     276              :                                                 value, rhs2),
     277              :                                    recursion_limit - 1);
     278        44704 :             else if (integer_zerop (value))
     279              :               {
     280        16509 :                 tree cond = build2 (EQ_EXPR, boolean_type_node,
     281              :                                     gimple_assign_rhs1 (def_stmt),
     282              :                                     gimple_assign_rhs2 (def_stmt));
     283        16509 :                 tree inverted = invert_truthvalue (cond);
     284        16509 :                 record_conditions (&this->cond_equivalences, cond, inverted);
     285              :               }
     286              :             break;
     287              :           }
     288              : 
     289       759283 :         case EQ_EXPR:
     290       759283 :         case NE_EXPR:
     291       759283 :           {
     292       347413 :             if ((code == EQ_EXPR && integer_onep (value))
     293       902410 :                 || (code == NE_EXPR && integer_zerop (value)))
     294              :               {
     295       466381 :                 tree rhs1 = gimple_assign_rhs1 (def_stmt);
     296       466381 :                 tree rhs2 = gimple_assign_rhs2 (def_stmt);
     297              : 
     298              :                 /* If the second argument is a constant, then record the
     299              :                    first argument as being the same as that constant.
     300              : 
     301              :                    If neither operand is a constant, then we have a
     302              :                    conditional name == name equivalence.  */
     303       466381 :                 if (TREE_CODE (rhs2) == INTEGER_CST)
     304       244169 :                   derive_equivalences (rhs1, rhs2, recursion_limit - 1);
     305              :               }
     306              :             else
     307              :               {
     308       292902 :                 tree cond = build2 (code, boolean_type_node,
     309              :                                     gimple_assign_rhs1 (def_stmt),
     310       292902 :                                     gimple_assign_rhs2 (def_stmt));
     311       292902 :                 tree inverted = invert_truthvalue (cond);
     312       292902 :                 if (integer_zerop (value))
     313       143127 :                   std::swap (cond, inverted);
     314       292902 :                 record_conditions (&this->cond_equivalences, cond, inverted);
     315              :               }
     316              :             break;
     317              :           }
     318              : 
     319              :         /* For BIT_NOT and NEGATE, we can just apply the operation to the
     320              :            VALUE to get the new equivalence.  It will always be a constant
     321              :            so we can recurse.  */
     322        14341 :         case BIT_NOT_EXPR:
     323        14341 :         case NEGATE_EXPR:
     324        14341 :           {
     325        14341 :             tree rhs = gimple_assign_rhs1 (def_stmt);
     326        14341 :             tree res;
     327              :             /* If this is a NOT and the operand has a boolean range, then we
     328              :                know its value must be zero or one.  We are not supposed to
     329              :                have a BIT_NOT_EXPR for boolean types with precision > 1 in
     330              :                the general case, see e.g. the handling of TRUTH_NOT_EXPR in
     331              :                the gimplifier, but it can be generated by match.pd out of
     332              :                a BIT_XOR_EXPR wrapped in a BIT_AND_EXPR.  Now the handling
     333              :                of BIT_AND_EXPR above already forces a specific semantics for
     334              :                boolean types with precision > 1 so we must do the same here,
     335              :                otherwise we could change the semantics of TRUTH_NOT_EXPR for
     336              :                boolean types with precision > 1.  */
     337        14341 :             if (code == BIT_NOT_EXPR
     338        14086 :                 && TREE_CODE (rhs) == SSA_NAME
     339        28427 :                 && ssa_name_has_boolean_range (rhs))
     340              :               {
     341        13632 :                 if ((TREE_INT_CST_LOW (value) & 1) == 0)
     342         6194 :                   res = build_one_cst (TREE_TYPE (rhs));
     343              :                 else
     344         7438 :                   res = build_zero_cst (TREE_TYPE (rhs));
     345              :               }
     346              :             else
     347          709 :               res = fold_build1 (code, TREE_TYPE (rhs), value);
     348        14341 :             derive_equivalences (rhs, res, recursion_limit - 1);
     349        14341 :             break;
     350              :           }
     351              : 
     352      6166487 :         default:
     353      6166487 :           {
     354      6166487 :             if (TREE_CODE_CLASS (code) == tcc_comparison)
     355              :               {
     356       531379 :                 tree cond = build2 (code, boolean_type_node,
     357              :                                     gimple_assign_rhs1 (def_stmt),
     358       531379 :                                     gimple_assign_rhs2 (def_stmt));
     359       531379 :                 tree inverted = invert_truthvalue (cond);
     360       531379 :                 if (integer_zerop (value))
     361       225444 :                   std::swap (cond, inverted);
     362       531379 :                 record_conditions (&this->cond_equivalences, cond, inverted);
     363       531379 :                 break;
     364              :               }
     365              :             break;
     366              :           }
     367              :         }
     368              :     }
     369              : }
     370              : 
     371              : void
     372     16163625 : edge_info::record_simple_equiv (tree lhs, tree rhs)
     373              : {
     374              :   /* If the RHS is a constant, then we may be able to derive
     375              :      further equivalences.  Else just record the name = name
     376              :      equivalence.  */
     377     16163625 :   if (TREE_CODE (rhs) == INTEGER_CST)
     378     12874153 :     derive_equivalences (lhs, rhs, 4);
     379              :   else
     380      3289472 :     simple_equivalences.safe_push (equiv_pair (lhs, rhs));
     381     16163625 : }
     382              : 
     383              : /* Free the edge_info data attached to E, if it exists and
     384              :    clear e->aux.  */
     385              : 
     386              : void
     387    133690447 : free_dom_edge_info (edge e)
     388              : {
     389    133690447 :   class edge_info *edge_info = (class edge_info *)e->aux;
     390              : 
     391    133690447 :   if (edge_info)
     392     36924339 :     delete edge_info;
     393    133690447 :   e->aux = NULL;
     394    133690447 : }
     395              : 
     396              : /* Free all EDGE_INFO structures associated with edges in the CFG.
     397              :    If a particular edge can be threaded, copy the redirection
     398              :    target from the EDGE_INFO structure into the edge's AUX field
     399              :    as required by code to update the CFG and SSA graph for
     400              :    jump threading.  */
     401              : 
     402              : static void
     403      2126266 : free_all_edge_infos (void)
     404              : {
     405      2126266 :   basic_block bb;
     406      2126266 :   edge_iterator ei;
     407      2126266 :   edge e;
     408              : 
     409     24086462 :   FOR_EACH_BB_FN (bb, cfun)
     410              :     {
     411     52981038 :       FOR_EACH_EDGE (e, ei, bb->preds)
     412     31020842 :         free_dom_edge_info (e);
     413              :     }
     414      2126266 : }
     415              : 
     416              : /* We have finished optimizing BB, record any information implied by
     417              :    taking a specific outgoing edge from BB.  */
     418              : 
     419              : static void
     420     45965135 : record_edge_info (basic_block bb)
     421              : {
     422     45965135 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
     423     45965135 :   class edge_info *edge_info;
     424              : 
     425              :   /* Free all the outgoing edge info data associated with
     426              :      BB's outgoing edges.  */
     427     45965135 :   edge e;
     428     45965135 :   edge_iterator ei;
     429    109942146 :   FOR_EACH_EDGE (e, ei, bb->succs)
     430     63977011 :     free_dom_edge_info (e);
     431              : 
     432     45965135 :   if (! gsi_end_p (gsi))
     433              :     {
     434     39646045 :       gimple *stmt = gsi_stmt (gsi);
     435     39646045 :       location_t loc = gimple_location (stmt);
     436              : 
     437     39646045 :       if (gimple_code (stmt) == GIMPLE_SWITCH)
     438              :         {
     439        72601 :           gswitch *switch_stmt = as_a <gswitch *> (stmt);
     440        72601 :           tree index = gimple_switch_index (switch_stmt);
     441              : 
     442        72601 :           if (TREE_CODE (index) == SSA_NAME)
     443              :             {
     444        72586 :               int i;
     445        72586 :               int n_labels = gimple_switch_num_labels (switch_stmt);
     446              :               /* info contains NULL, error_mark_node or a value.
     447              :                  error_mark signifies there are multiple values already.
     448              :                  A NULL signifies there it is uninitialized.
     449              :                  A value signifies that is the only value on that edge
     450              :                  to that bb.  */
     451        72586 :               tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
     452              : 
     453       687320 :               for (i = 0; i < n_labels; i++)
     454              :                 {
     455       542148 :                   tree label = gimple_switch_label (switch_stmt, i);
     456       542148 :                   basic_block target_bb
     457       542148 :                     = label_to_block (cfun, CASE_LABEL (label));
     458              :                   /* The default case is a case with multiple values.
     459              :                      If the value is already set then it has multiple values.  */
     460       542148 :                   if (CASE_HIGH (label)
     461       517446 :                       || !CASE_LOW (label)
     462       987008 :                       || info[target_bb->index])
     463       146394 :                     info[target_bb->index] = error_mark_node;
     464              :                   else
     465              :                     /* Record the one value that can be on that edge to the
     466              :                        target_bb.  */
     467       395754 :                     info[target_bb->index] = CASE_LOW (label);
     468              :                 }
     469              : 
     470       558586 :               FOR_EACH_EDGE (e, ei, bb->succs)
     471              :                 {
     472       486000 :                   basic_block target_bb = e->dest;
     473       486000 :                   tree value = info[target_bb->index];
     474              : 
     475       486000 :                   if (value != NULL && value != error_mark_node)
     476              :                     {
     477       370527 :                       tree x = fold_convert_loc (loc, TREE_TYPE (index),
     478              :                                                  value);
     479       370527 :                       edge_info = new class edge_info (e);
     480       370527 :                       edge_info->record_simple_equiv (index, x);
     481              :                     }
     482              :                 }
     483        72586 :               free (info);
     484              :             }
     485              :         }
     486              : 
     487              :       /* A COND_EXPR may create equivalences too.  */
     488     39646045 :       if (gimple_code (stmt) == GIMPLE_COND)
     489              :         {
     490     18460875 :           edge true_edge;
     491     18460875 :           edge false_edge;
     492              : 
     493     18460875 :           tree op0 = gimple_cond_lhs (stmt);
     494     18460875 :           tree op1 = gimple_cond_rhs (stmt);
     495     18460875 :           enum tree_code code = gimple_cond_code (stmt);
     496              : 
     497     18460875 :           extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
     498              : 
     499              :           /* Special case comparing booleans against a constant as we
     500              :              know the value of OP0 on both arms of the branch.  i.e., we
     501              :              can record an equivalence for OP0 rather than COND.
     502              : 
     503              :              However, don't do this if the constant isn't zero or one.
     504              :              Such conditionals will get optimized more thoroughly during
     505              :              the domwalk.  */
     506     18460875 :           if ((code == EQ_EXPR || code == NE_EXPR)
     507     14180977 :               && TREE_CODE (op0) == SSA_NAME
     508     13997534 :               && ssa_name_has_boolean_range (op0)
     509      2070839 :               && is_gimple_min_invariant (op1)
     510     20466368 :               && (integer_zerop (op1) || integer_onep (op1)))
     511              :             {
     512      2005493 :               tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
     513      2005493 :               tree false_val = constant_boolean_node (false, TREE_TYPE (op0));
     514              : 
     515      2005493 :               if (code == EQ_EXPR)
     516              :                 {
     517        78030 :                   edge_info = new class edge_info (true_edge);
     518       116279 :                   edge_info->record_simple_equiv (op0,
     519        78030 :                                                   (integer_zerop (op1)
     520              :                                                    ? false_val : true_val));
     521        78030 :                   edge_info = new class edge_info (false_edge);
     522       116279 :                   edge_info->record_simple_equiv (op0,
     523        78030 :                                                   (integer_zerop (op1)
     524              :                                                    ? true_val : false_val));
     525              :                 }
     526              :               else
     527              :                 {
     528      1927463 :                   edge_info = new class edge_info (true_edge);
     529      1930828 :                   edge_info->record_simple_equiv (op0,
     530      1927463 :                                                   (integer_zerop (op1)
     531              :                                                    ? true_val : false_val));
     532      1927463 :                   edge_info = new class edge_info (false_edge);
     533      1930828 :                   edge_info->record_simple_equiv (op0,
     534      1927463 :                                                   (integer_zerop (op1)
     535              :                                                    ? false_val : true_val));
     536              :                 }
     537              :             }
     538     16455382 :           else if (TREE_CODE (op0) == SSA_NAME
     539     16455382 :                    && (TREE_CODE (op1) == SSA_NAME
     540     12106787 :                        || is_gimple_min_invariant (op1)))
     541              :             {
     542     16271413 :               tree cond = build2 (code, boolean_type_node, op0, op1);
     543     16271413 :               tree inverted = invert_truthvalue_loc (loc, cond);
     544     16271413 :               bool can_infer_simple_equiv
     545     16984069 :                 = !(HONOR_SIGNED_ZEROS (op1) && real_maybe_zerop (op1))
     546     16678502 :                   && !DECIMAL_FLOAT_MODE_P (element_mode (TREE_TYPE (op1)));
     547     16271413 :               class edge_info *edge_info;
     548              : 
     549     16271413 :               edge_info = new class edge_info (true_edge);
     550     16271413 :               record_conditions (&edge_info->cond_equivalences, cond, inverted);
     551              : 
     552     16271413 :               if (can_infer_simple_equiv && code == EQ_EXPR)
     553      5473979 :                 edge_info->record_simple_equiv (op0, op1);
     554              : 
     555     16271413 :               edge_info = new class edge_info (false_edge);
     556     16271413 :               record_conditions (&edge_info->cond_equivalences, inverted, cond);
     557              : 
     558     16271413 :               if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR)
     559      6308133 :                 edge_info->record_simple_equiv (op0, op1);
     560              :             }
     561              :         }
     562              :     }
     563     45965135 : }
     564              : 
     565              : class dom_jt_state : public jt_state
     566              : {
     567              : public:
     568      2126266 :   dom_jt_state (const_and_copies *copies, avail_exprs_stack *avails)
     569      2126266 :     : m_copies (copies), m_avails (avails)
     570              :   {
     571      2126266 :     bitmap_tree_view (m_blocks_on_stack);
     572      2126266 :   }
     573     17080188 :   void push (edge e) override
     574              :   {
     575     17080188 :     m_copies->push_marker ();
     576     17080188 :     m_avails->push_marker ();
     577     17080188 :     jt_state::push (e);
     578     17080188 :   }
     579     17080188 :   void pop () override
     580              :   {
     581     17080188 :     m_copies->pop_to_marker ();
     582     17080188 :     m_avails->pop_to_marker ();
     583     17080188 :     jt_state::pop ();
     584     17080188 :   }
     585     15808098 :   void register_equivs_edge (edge e) override
     586              :   {
     587     15808098 :     record_temporary_equivalences (e, m_copies, m_avails, m_blocks_on_stack);
     588     15808098 :   }
     589              :   void register_equiv (tree dest, tree src, bool update) override;
     590     65893022 :   bitmap get_blocks_on_stack () { return m_blocks_on_stack; }
     591              : private:
     592              :   const_and_copies *m_copies;
     593              :   avail_exprs_stack *m_avails;
     594              :   /* Set of blocks on the stack, to be used for medium-fast
     595              :      dominance queries in back_propagate_equivalences.  */
     596              :   auto_bitmap m_blocks_on_stack;
     597              : };
     598              : 
     599              : void
     600     21545044 : dom_jt_state::register_equiv (tree dest, tree src, bool)
     601              : {
     602     21545044 :   m_copies->record_const_or_copy (dest, src);
     603     21545044 : }
     604              : 
     605      2126266 : class dom_jt_simplifier : public hybrid_jt_simplifier
     606              : {
     607              : public:
     608      2126266 :   dom_jt_simplifier (avail_exprs_stack *avails, gimple_ranger *ranger,
     609              :                      path_range_query *query)
     610      4252532 :     : hybrid_jt_simplifier (ranger, query), m_avails (avails) { }
     611              : 
     612              : private:
     613              :   tree simplify (gimple *, gimple *, basic_block, jt_state *) override;
     614              :   avail_exprs_stack *m_avails;
     615              : };
     616              : 
     617              : tree
     618     31868546 : dom_jt_simplifier::simplify (gimple *stmt, gimple *within_stmt,
     619              :                              basic_block bb, jt_state *state)
     620              : {
     621              :   /* First see if the conditional is in the hash table.  */
     622     31868546 :   tree cached_lhs =  m_avails->lookup_avail_expr (stmt, false, true);
     623     31868546 :   if (cached_lhs)
     624              :     return cached_lhs;
     625              : 
     626              :   /* Otherwise call the ranger if possible.  */
     627     31043888 :   if (state)
     628      8744598 :     return hybrid_jt_simplifier::simplify (stmt, within_stmt, bb, state);
     629              : 
     630              :   return NULL;
     631              : }
     632              : 
     633      4252532 : class dom_opt_dom_walker : public dom_walker
     634              : {
     635              : public:
     636      2126266 :   dom_opt_dom_walker (cdi_direction direction,
     637              :                       jump_threader *threader,
     638              :                       dom_jt_state *state,
     639              :                       gimple_ranger *ranger,
     640              :                       const_and_copies *const_and_copies,
     641              :                       avail_exprs_stack *avail_exprs_stack)
     642      4252532 :     : dom_walker (direction, REACHABLE_BLOCKS)
     643              :     {
     644      2126266 :       m_ranger = ranger;
     645      2126266 :       m_state = state;
     646      2126266 :       m_const_and_copies = const_and_copies;
     647      2126266 :       m_avail_exprs_stack = avail_exprs_stack;
     648      2126266 :       m_threader = threader;
     649              :     }
     650              : 
     651              :   edge before_dom_children (basic_block) final override;
     652              :   void after_dom_children (basic_block) final override;
     653              : 
     654              : private:
     655              : 
     656              :   /* Unwindable equivalences, both const/copy and expression varieties.  */
     657              :   class const_and_copies *m_const_and_copies;
     658              :   class avail_exprs_stack *m_avail_exprs_stack;
     659              : 
     660              :   /* Optimize a single statement within a basic block using the
     661              :      various tables maintained by DOM.  Returns the taken edge if
     662              :      the statement is a conditional with a statically determined
     663              :      value.  */
     664              :   edge optimize_stmt (basic_block, gimple_stmt_iterator *, bool *);
     665              : 
     666              :   void set_global_ranges_from_unreachable_edges (basic_block);
     667              : 
     668              :   void fold_cond (gimple *);
     669              :   void record_equivalences_from_incoming_edge (basic_block);
     670              :   void eliminate_redundant_computations (gimple_stmt_iterator *);
     671              :   void record_equivalences_from_stmt (gimple *, int);
     672              :   tree const_or_copy_of_stmt (gimple *);
     673              : 
     674              :   jump_threader *m_threader;
     675              :   gimple_ranger *m_ranger;
     676              :   dom_jt_state *m_state;
     677              : };
     678              : 
     679              : /* Jump threading, redundancy elimination and const/copy propagation.
     680              : 
     681              :    This pass may expose new symbols that need to be renamed into SSA.  For
     682              :    every new symbol exposed, its corresponding bit will be set in
     683              :    VARS_TO_RENAME.  */
     684              : 
     685              : namespace {
     686              : 
     687              : const pass_data pass_data_dominator =
     688              : {
     689              :   GIMPLE_PASS, /* type */
     690              :   "dom", /* name */
     691              :   OPTGROUP_NONE, /* optinfo_flags */
     692              :   TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
     693              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
     694              :   0, /* properties_provided */
     695              :   0, /* properties_destroyed */
     696              :   0, /* todo_flags_start */
     697              :   ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
     698              : };
     699              : 
     700              : class pass_dominator : public gimple_opt_pass
     701              : {
     702              : public:
     703       891540 :   pass_dominator (gcc::context *ctxt)
     704              :     : gimple_opt_pass (pass_data_dominator, ctxt),
     705      1783080 :       may_peel_loop_headers_p (false)
     706              :   {}
     707              : 
     708              :   /* opt_pass methods: */
     709       594360 :   opt_pass * clone () final override { return new pass_dominator (m_ctxt); }
     710       891540 :   void set_pass_param (unsigned int n, bool param) final override
     711              :     {
     712       891540 :       gcc_assert (n == 0);
     713       891540 :       may_peel_loop_headers_p = param;
     714       891540 :     }
     715      2127077 :   bool gate (function *) final override { return flag_tree_dom != 0; }
     716              :   unsigned int execute (function *) final override;
     717              : 
     718              :  private:
     719              :   /* This flag is used to prevent loops from being peeled repeatedly in jump
     720              :      threading; it will be removed once we preserve loop structures throughout
     721              :      the compilation -- we will be able to mark the affected loops directly in
     722              :      jump threading, and avoid peeling them next time.  */
     723              :   bool may_peel_loop_headers_p;
     724              : }; // class pass_dominator
     725              : 
     726              : unsigned int
     727      2126266 : pass_dominator::execute (function *fun)
     728              : {
     729      2126266 :   memset (&opt_stats, 0, sizeof (opt_stats));
     730              : 
     731              :   /* Create our hash tables.  */
     732      2126266 :   hash_table<expr_elt_hasher> *avail_exprs
     733      2126266 :     = new hash_table<expr_elt_hasher> (1024);
     734      2126266 :   class avail_exprs_stack *avail_exprs_stack
     735      2126266 :     = new class avail_exprs_stack (avail_exprs);
     736      2126266 :   class const_and_copies *const_and_copies = new class const_and_copies ();
     737      2126266 :   need_eh_cleanup = BITMAP_ALLOC (NULL);
     738      2126266 :   need_noreturn_fixup.create (0);
     739      2126266 :   names_without_foldable_uses = BITMAP_ALLOC (NULL);
     740      2126266 :   bitmap_tree_view (names_without_foldable_uses);
     741              : 
     742      2126266 :   calculate_dominance_info (CDI_DOMINATORS);
     743      2126266 :   cfg_altered = false;
     744              : 
     745              :   /* We need to know loop structures in order to avoid destroying them
     746              :      in jump threading.  Note that we still can e.g. thread through loop
     747              :      headers to an exit edge, or through loop header to the loop body, assuming
     748              :      that we update the loop info.
     749              : 
     750              :      TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
     751              :      to several overly conservative bail-outs in jump threading, case
     752              :      gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
     753              :      missing.  We should improve jump threading in future then
     754              :      LOOPS_HAVE_PREHEADERS won't be needed here.  */
     755      2126266 :   loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES
     756              :                        | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
     757              : 
     758              :   /* We need accurate information regarding back edges in the CFG
     759              :      for jump threading; this may include back edges that are not part of
     760              :      a single loop.  */
     761      2126266 :   mark_dfs_back_edges ();
     762              : 
     763              :   /* We want to create the edge info structures before the dominator walk
     764              :      so that they'll be in place for the jump threader, particularly when
     765              :      threading through a join block.
     766              : 
     767              :      The conditions will be lazily updated with global equivalences as
     768              :      we reach them during the dominator walk.  */
     769      2126266 :   basic_block bb;
     770     24086462 :   FOR_EACH_BB_FN (bb, fun)
     771     21960196 :     record_edge_info (bb);
     772              : 
     773              :   /* Recursively walk the dominator tree optimizing statements.  */
     774      2126266 :   gimple_ranger *ranger = enable_ranger (fun);
     775      2126266 :   path_range_query path_query (*ranger);
     776      2126266 :   dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query);
     777      2126266 :   dom_jt_state state (const_and_copies, avail_exprs_stack);
     778      2126266 :   jump_threader threader (&simplifier, &state);
     779      2126266 :   dom_opt_dom_walker walker (CDI_DOMINATORS,
     780              :                              &threader,
     781              :                              &state,
     782              :                              ranger,
     783              :                              const_and_copies,
     784      2126266 :                              avail_exprs_stack);
     785      2126266 :   walker.walk (fun->cfg->x_entry_block_ptr);
     786              : 
     787      2126266 :   ranger->export_global_ranges ();
     788      2126266 :   disable_ranger (fun);
     789              : 
     790              :   /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
     791              :      edge.  When found, remove jump threads which contain any outgoing
     792              :      edge from the affected block.  */
     793      2126266 :   if (cfg_altered)
     794              :     {
     795      4895182 :       FOR_EACH_BB_FN (bb, fun)
     796              :         {
     797      4830973 :           edge_iterator ei;
     798      4830973 :           edge e;
     799              : 
     800              :           /* First see if there are any edges without EDGE_EXECUTABLE
     801              :              set.  */
     802      4830973 :           bool found = false;
     803     11596460 :           FOR_EACH_EDGE (e, ei, bb->succs)
     804              :             {
     805      6999069 :               if ((e->flags & EDGE_EXECUTABLE) == 0)
     806              :                 {
     807              :                   found = true;
     808              :                   break;
     809              :                 }
     810              :             }
     811              : 
     812              :           /* If there were any such edges found, then remove jump threads
     813              :              containing any edge leaving BB.  */
     814      4830973 :           if (found)
     815       681685 :             FOR_EACH_EDGE (e, ei, bb->succs)
     816       448103 :               threader.remove_jump_threads_including (e);
     817              :         }
     818              :     }
     819              : 
     820      2126266 :   {
     821      2126266 :     gimple_stmt_iterator gsi;
     822      2126266 :     basic_block bb;
     823     24086462 :     FOR_EACH_BB_FN (bb, fun)
     824              :       {
     825    226388779 :         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     826    182468387 :           update_stmt_if_modified (gsi_stmt (gsi));
     827              :       }
     828              :   }
     829              : 
     830              :   /* If we exposed any new variables, go ahead and put them into
     831              :      SSA form now, before we handle jump threading.  This simplifies
     832              :      interactions between rewriting of _DECL nodes into SSA form
     833              :      and rewriting SSA_NAME nodes into SSA form after block
     834              :      duplication and CFG manipulation.  */
     835      2126266 :   update_ssa (TODO_update_ssa);
     836              : 
     837      2126266 :   free_all_edge_infos ();
     838              : 
     839              :   /* Thread jumps, creating duplicate blocks as needed.  */
     840      2126266 :   cfg_altered |= threader.thread_through_all_blocks (may_peel_loop_headers_p);
     841              : 
     842      2126266 :   if (cfg_altered)
     843       123857 :     free_dominance_info (CDI_DOMINATORS);
     844              : 
     845              :   /* Removal of statements may make some EH edges dead.  Purge
     846              :      such edges from the CFG as needed.  */
     847      2126266 :   if (!bitmap_empty_p (need_eh_cleanup))
     848              :     {
     849          559 :       unsigned i;
     850          559 :       bitmap_iterator bi;
     851              : 
     852              :       /* Jump threading may have created forwarder blocks from blocks
     853              :          needing EH cleanup; the new successor of these blocks, which
     854              :          has inherited from the original block, needs the cleanup.
     855              :          Don't clear bits in the bitmap, as that can break the bitmap
     856              :          iterator.  */
     857         1803 :       EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
     858              :         {
     859         1244 :           basic_block bb = BASIC_BLOCK_FOR_FN (fun, i);
     860         1244 :           if (bb == NULL)
     861            0 :             continue;
     862         2567 :           while (single_succ_p (bb)
     863         1378 :                  && (single_succ_edge (bb)->flags
     864          151 :                      & (EDGE_EH|EDGE_DFS_BACK)) == 0)
     865          134 :             bb = single_succ (bb);
     866         1244 :           if (bb == EXIT_BLOCK_PTR_FOR_FN (fun))
     867           55 :             continue;
     868         1189 :           if ((unsigned) bb->index != i)
     869           59 :             bitmap_set_bit (need_eh_cleanup, bb->index);
     870              :         }
     871              : 
     872          559 :       gimple_purge_all_dead_eh_edges (need_eh_cleanup);
     873          559 :       bitmap_clear (need_eh_cleanup);
     874              :     }
     875              : 
     876              :   /* Fixup stmts that became noreturn calls.  This may require splitting
     877              :      blocks and thus isn't possible during the dominator walk or before
     878              :      jump threading finished.  Do this in reverse order so we don't
     879              :      inadvertently remove a stmt we want to fixup by visiting a dominating
     880              :      now noreturn call first.  */
     881      2126272 :   while (!need_noreturn_fixup.is_empty ())
     882              :     {
     883            6 :       gimple *stmt = need_noreturn_fixup.pop ();
     884              :       /* We might have elided the stmt and its BB above.  */
     885            6 :       if (!gimple_bb (stmt))
     886            1 :         continue;
     887            5 :       if (dump_file && dump_flags & TDF_DETAILS)
     888              :         {
     889            0 :           fprintf (dump_file, "Fixing up noreturn call ");
     890            0 :           print_gimple_stmt (dump_file, stmt, 0);
     891            0 :           fprintf (dump_file, "\n");
     892              :         }
     893            5 :       fixup_noreturn_call (stmt);
     894              :     }
     895              : 
     896      2126266 :   statistics_counter_event (fun, "Redundant expressions eliminated",
     897      2126266 :                             opt_stats.num_re);
     898      2126266 :   statistics_counter_event (fun, "Constants propagated",
     899      2126266 :                             opt_stats.num_const_prop);
     900      2126266 :   statistics_counter_event (fun, "Copies propagated",
     901      2126266 :                             opt_stats.num_copy_prop);
     902              : 
     903              :   /* Debugging dumps.  */
     904      2126266 :   if (dump_file && (dump_flags & TDF_STATS))
     905           36 :     dump_dominator_optimization_stats (dump_file, avail_exprs);
     906              : 
     907      2126266 :   loop_optimizer_finalize ();
     908              : 
     909              :   /* Delete our main hashtable.  */
     910      2126266 :   delete avail_exprs;
     911      2126266 :   avail_exprs = NULL;
     912              : 
     913              :   /* Free asserted bitmaps and stacks.  */
     914      2126266 :   BITMAP_FREE (need_eh_cleanup);
     915      2126266 :   need_noreturn_fixup.release ();
     916      2126266 :   BITMAP_FREE (names_without_foldable_uses);
     917      2126266 :   delete avail_exprs_stack;
     918      2126266 :   delete const_and_copies;
     919              : 
     920      2126266 :   return 0;
     921      2126266 : }
     922              : 
     923              : } // anon namespace
     924              : 
     925              : gimple_opt_pass *
     926       297180 : make_pass_dominator (gcc::context *ctxt)
     927              : {
     928       297180 :   return new pass_dominator (ctxt);
     929              : }
     930              : 
     931              : /* Valueize hook for gimple_fold_stmt_to_constant_1.  */
     932              : 
     933              : static tree
     934     35073876 : dom_valueize (tree t)
     935              : {
     936     35073876 :   if (TREE_CODE (t) == SSA_NAME)
     937              :     {
     938     25156288 :       tree tem = SSA_NAME_VALUE (t);
     939     19965359 :       if (tem)
     940      3176599 :         return tem;
     941              :     }
     942              :   return t;
     943              : }
     944              : 
     945              : /* We have just found an equivalence for LHS on an edge E.
     946              :    Look backwards to other uses of LHS and see if we can derive
     947              :    additional equivalences that are valid on edge E.  */
     948              : static void
     949     12281089 : back_propagate_equivalences (tree lhs, edge e,
     950              :                              class const_and_copies *const_and_copies,
     951              :                              bitmap domby)
     952              : {
     953     12281089 :   use_operand_p use_p;
     954     12281089 :   imm_use_iterator iter;
     955     12281089 :   basic_block dest = e->dest;
     956     12281089 :   bool domok = (dom_info_state (CDI_DOMINATORS) == DOM_OK);
     957     12281089 :   unsigned version = SSA_NAME_VERSION (lhs);
     958              : 
     959              :   /* If an earlier walk found no use of LHS that can produce an
     960              :      equivalence, there is nothing to do.  With checking enabled, walk
     961              :      the uses anyway to verify that no such use has been added.  */
     962     12281089 :   bool cached_p = bitmap_bit_p (names_without_foldable_uses, version);
     963     12281089 :   if (cached_p && !flag_checking)
     964           49 :     return;
     965              : 
     966              :   /* Iterate over the uses of LHS to see if any dominate E->dest.
     967              :      If so, they may create useful equivalences too.
     968              : 
     969              :      ???  If the code gets re-organized to a worklist to catch more
     970              :      indirect opportunities and it is made to handle PHIs then this
     971              :      should only consider use_stmts in basic-blocks we have already visited.  */
     972     12281040 :   bool foldable_use_p = false;
     973     52040190 :   FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
     974              :     {
     975     39759150 :       gimple *use_stmt = USE_STMT (use_p);
     976              : 
     977              :       /* Filter out statements that can never produce a useful
     978              :          equivalence.  gimple_fold_stmt_to_constant_1 does not fold
     979              :          PHI nodes.  */
     980     39759150 :       if (gimple_code (use_stmt) == GIMPLE_PHI)
     981      3189176 :         continue;
     982     36569974 :       tree lhs2 = gimple_get_lhs (use_stmt);
     983     36569974 :       if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME)
     984     29074541 :         continue;
     985              : 
     986      7495433 :       gcc_checking_assert (!cached_p);
     987      7495433 :       foldable_use_p = true;
     988              : 
     989              :       /* Often the use is in DEST, which we trivially know we can't use.
     990              :          This is cheaper than the dominator set tests below.  */
     991      7495433 :       if (dest == gimple_bb (use_stmt))
     992       109998 :         continue;
     993              : 
     994      7385435 :       if (domok)
     995              :         {
     996      4314724 :           if (!dominated_by_p (CDI_DOMINATORS, dest, gimple_bb (use_stmt)))
     997      2161296 :             continue;
     998              :         }
     999              :       else
    1000              :         {
    1001              :           /* We can use the set of BBs on the stack from a domwalk
    1002              :              for a medium fast way to query dominance.  Profiling
    1003              :              has shown non-fast query dominance tests here can be fairly
    1004              :              expensive.  */
    1005              :           /* This tests if USE_STMT does not dominate DEST.  */
    1006      3070711 :           if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index))
    1007      2101978 :             continue;
    1008              :         }
    1009              : 
    1010              :       /* At this point USE_STMT dominates DEST and may result in a
    1011              :          useful equivalence.  Try to simplify its RHS to a constant
    1012              :          or SSA_NAME.  */
    1013      3122161 :       tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize,
    1014              :                                                  no_follow_ssa_edges);
    1015      3122161 :       if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res)))
    1016      2463287 :         record_equality (lhs2, res, const_and_copies);
    1017     12281040 :     }
    1018              : 
    1019     12281040 :   if (!foldable_use_p)
    1020      8745571 :     bitmap_set_bit (names_without_foldable_uses, version);
    1021              : }
    1022              : 
    1023              : /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
    1024              :    by traversing edge E (which are cached in E->aux).
    1025              : 
    1026              :    Callers are responsible for managing the unwinding markers.  */
    1027              : static void
    1028     33691242 : record_temporary_equivalences (edge e,
    1029              :                                class const_and_copies *const_and_copies,
    1030              :                                class avail_exprs_stack *avail_exprs_stack,
    1031              :                                bitmap blocks_on_stack)
    1032              : {
    1033     33691242 :   int i;
    1034     33691242 :   class edge_info *edge_info = (class edge_info *) e->aux;
    1035              : 
    1036              :   /* If we have info associated with this edge, record it into
    1037              :      our equivalence tables.  */
    1038     33691242 :   if (edge_info)
    1039              :     {
    1040              :       cond_equivalence *eq;
    1041              :       /* If we have 0 = COND or 1 = COND equivalences, record them
    1042              :          into our expression hash tables.  */
    1043     67894786 :       for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
    1044     43669124 :         avail_exprs_stack->record_cond (eq);
    1045              : 
    1046              :       edge_info::equiv_pair *seq;
    1047     36506751 :       for (i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i)
    1048              :         {
    1049     12281089 :           tree lhs = seq->first;
    1050     12281089 :           if (!lhs || TREE_CODE (lhs) != SSA_NAME)
    1051            0 :             continue;
    1052              : 
    1053              :           /* Record the simple NAME = VALUE equivalence.  */
    1054     12281089 :           tree rhs = seq->second;
    1055              : 
    1056              :           /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is
    1057              :              cheaper to compute than the other, then set up the equivalence
    1058              :              such that we replace the expensive one with the cheap one.
    1059              : 
    1060              :              If they are the same cost to compute, then do not record
    1061              :              anything.  */
    1062     12281089 :           if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
    1063              :             {
    1064      1749659 :               gimple *rhs_def = SSA_NAME_DEF_STMT (rhs);
    1065      1749659 :               int rhs_cost = estimate_num_insns (rhs_def, &eni_size_weights);
    1066              : 
    1067      1749659 :               gimple *lhs_def = SSA_NAME_DEF_STMT (lhs);
    1068      1749659 :               int lhs_cost = estimate_num_insns (lhs_def, &eni_size_weights);
    1069              : 
    1070      1749659 :               if (rhs_cost > lhs_cost)
    1071       195994 :                 record_equality (rhs, lhs, const_and_copies);
    1072      1553665 :               else if (rhs_cost < lhs_cost)
    1073       454897 :                 record_equality (lhs, rhs, const_and_copies);
    1074              :             }
    1075              :           else
    1076     10531430 :             record_equality (lhs, rhs, const_and_copies);
    1077              : 
    1078              : 
    1079              :           /* Any equivalence found for LHS may result in additional
    1080              :              equivalences for other uses of LHS that we have already
    1081              :              processed.  */
    1082     12281089 :           back_propagate_equivalences (lhs, e, const_and_copies,
    1083              :                                        blocks_on_stack);
    1084              :         }
    1085              :     }
    1086     33691242 : }
    1087              : 
    1088              : /* PHI nodes can create equivalences too.
    1089              : 
    1090              :    Ignoring any alternatives which are the same as the result, if
    1091              :    all the alternatives are equal, then the PHI node creates an
    1092              :    equivalence.  */
    1093              : 
    1094              : static void
    1095     24004939 : record_equivalences_from_phis (basic_block bb)
    1096              : {
    1097     24004939 :   gphi_iterator gsi;
    1098              : 
    1099     33475035 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
    1100              :     {
    1101      9470096 :       gphi *phi = gsi.phi ();
    1102              : 
    1103              :       /* We might eliminate the PHI, so advance GSI now.  */
    1104      9470096 :       gsi_next (&gsi);
    1105              : 
    1106      9470096 :       tree lhs = gimple_phi_result (phi);
    1107      9470096 :       tree rhs = NULL;
    1108      9470096 :       size_t i;
    1109              : 
    1110     17060691 :       for (i = 0; i < gimple_phi_num_args (phi); i++)
    1111              :         {
    1112     15967780 :           tree t = gimple_phi_arg_def (phi, i);
    1113              : 
    1114              :           /* Ignore alternatives which are the same as our LHS.  Since
    1115              :              LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
    1116              :              can simply compare pointers.  */
    1117     15967780 :           if (lhs == t)
    1118        31628 :             continue;
    1119              : 
    1120              :           /* If the associated edge is not marked as executable, then it
    1121              :              can be ignored.  */
    1122     15936152 :           if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0)
    1123       127054 :             continue;
    1124              : 
    1125     15809098 :           t = dom_valueize (t);
    1126              : 
    1127              :           /* If T is an SSA_NAME and its associated edge is a backedge,
    1128              :              then quit as we cannot utilize this equivalence.  */
    1129     15809098 :           if (TREE_CODE (t) == SSA_NAME
    1130     15809098 :               && (gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK))
    1131              :             break;
    1132              : 
    1133              :           /* If we have not processed an alternative yet, then set
    1134              :              RHS to this alternative.  */
    1135     12692884 :           if (rhs == NULL)
    1136              :             rhs = t;
    1137              :           /* If we have processed an alternative (stored in RHS), then
    1138              :              see if it is equal to this one.  If it isn't, then stop
    1139              :              the search.  */
    1140      5823386 :           else if (! operand_equal_for_phi_arg_p (rhs, t))
    1141              :             break;
    1142              :         }
    1143              : 
    1144              :       /* If we had no interesting alternatives, then all the RHS alternatives
    1145              :          must have been the same as LHS.  */
    1146      9470096 :       if (!rhs)
    1147      2600598 :         rhs = lhs;
    1148              : 
    1149              :       /* If we managed to iterate through each PHI alternative without
    1150              :          breaking out of the loop, then we have a PHI which may create
    1151              :          a useful equivalence.  We do not need to record unwind data for
    1152              :          this, since this is a true assignment and not an equivalence
    1153              :          inferred from a comparison.  All uses of this ssa name are dominated
    1154              :          by this assignment, so unwinding just costs time and space.  */
    1155      9470096 :       if (i == gimple_phi_num_args (phi))
    1156              :         {
    1157      1092911 :           if (may_propagate_copy (lhs, rhs))
    1158       600105 :             set_ssa_name_value (lhs, rhs);
    1159       985612 :           else if (virtual_operand_p (lhs))
    1160              :             {
    1161       492364 :               gimple *use_stmt;
    1162       492364 :               imm_use_iterator iter;
    1163       492364 :               use_operand_p use_p;
    1164              :               /* For virtual operands we have to propagate into all uses as
    1165              :                  otherwise we will create overlapping life-ranges.  */
    1166      1480380 :               FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
    1167      2042874 :                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    1168      1021437 :                   SET_USE (use_p, rhs);
    1169       492364 :               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
    1170           72 :                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
    1171       492364 :               gimple_stmt_iterator tmp_gsi = gsi_for_stmt (phi);
    1172       492364 :               remove_phi_node (&tmp_gsi, true);
    1173              :             }
    1174              :         }
    1175              :     }
    1176     24004939 : }
    1177              : 
    1178              : /* Return true if all uses of NAME are dominated by STMT or feed STMT
    1179              :    via a chain of single immediate uses.  */
    1180              : 
    1181              : static bool
    1182       412056 : all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt)
    1183              : {
    1184       412056 :   use_operand_p use_p, use2_p;
    1185       412056 :   imm_use_iterator iter;
    1186       412056 :   basic_block stmt_bb = gimple_bb (stmt);
    1187              : 
    1188      1669355 :   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
    1189              :     {
    1190      1478617 :       gimple *use_stmt = USE_STMT (use_p), *use_stmt2;
    1191      2727427 :       if (use_stmt == stmt
    1192      1342004 :           || is_gimple_debug (use_stmt)
    1193      2208604 :           || (gimple_bb (use_stmt) != stmt_bb
    1194       567468 :               && dominated_by_p (CDI_DOMINATORS,
    1195       567468 :                                  gimple_bb (use_stmt), stmt_bb)))
    1196      1248810 :         continue;
    1197              :       while (use_stmt != stmt
    1198       434782 :              && is_gimple_assign (use_stmt)
    1199       381509 :              && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
    1200       810621 :              && single_imm_use (gimple_assign_lhs (use_stmt),
    1201              :                                 &use2_p, &use_stmt2))
    1202       213464 :         use_stmt = use_stmt2;
    1203       229807 :       if (use_stmt != stmt)
    1204       221318 :         return false;
    1205       221318 :     }
    1206       190738 :   return true;
    1207              : }
    1208              : 
    1209              : /* Handle
    1210              :    _4 = x_3 & 31;
    1211              :    if (_4 != 0)
    1212              :      goto <bb 6>;
    1213              :    else
    1214              :      goto <bb 7>;
    1215              :    <bb 6>:
    1216              :    __builtin_unreachable ();
    1217              :    <bb 7>:
    1218              : 
    1219              :    If x_3 has no other immediate uses (checked by caller), var is the
    1220              :    x_3 var, we can clear low 5 bits from the non-zero bitmask.  */
    1221              : 
    1222              : static void
    1223       171279 : maybe_set_nonzero_bits (edge e, tree var)
    1224              : {
    1225       171279 :   basic_block cond_bb = e->src;
    1226       342558 :   gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
    1227       171279 :   tree cst;
    1228              : 
    1229       171279 :   if (cond == NULL
    1230       171279 :       || gimple_cond_code (cond) != ((e->flags & EDGE_TRUE_VALUE)
    1231       171279 :                                      ? EQ_EXPR : NE_EXPR)
    1232        53104 :       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
    1233         2057 :       || !integer_zerop (gimple_cond_rhs (cond)))
    1234              :     return;
    1235              : 
    1236         1978 :   gimple *stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
    1237         1978 :   if (!is_gimple_assign (stmt)
    1238         1961 :       || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR
    1239         2003 :       || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
    1240              :     return;
    1241            3 :   if (gimple_assign_rhs1 (stmt) != var)
    1242              :     {
    1243            2 :       gimple *stmt2;
    1244              : 
    1245            2 :       if (TREE_CODE (gimple_assign_rhs1 (stmt)) != SSA_NAME)
    1246              :         return;
    1247            2 :       stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
    1248            2 :       if (!gimple_assign_cast_p (stmt2)
    1249            0 :           || gimple_assign_rhs1 (stmt2) != var
    1250            0 :           || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt2))
    1251            2 :           || (TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (stmt)))
    1252            0 :                               != TYPE_PRECISION (TREE_TYPE (var))))
    1253              :         return;
    1254              :     }
    1255            1 :   cst = gimple_assign_rhs2 (stmt);
    1256            1 :   set_nonzero_bits (var, wi::bit_and_not (get_nonzero_bits (var),
    1257            2 :                                             wi::to_wide (cst)));
    1258              : }
    1259              : 
    1260              : /* Set global ranges that can be determined from the C->M edge:
    1261              : 
    1262              :    <bb C>:
    1263              :    ...
    1264              :    if (something)
    1265              :      goto <bb N>;
    1266              :    else
    1267              :      goto <bb M>;
    1268              :    <bb N>:
    1269              :    __builtin_unreachable ();
    1270              :    <bb M>:
    1271              : */
    1272              : 
    1273              : void
    1274     24004939 : dom_opt_dom_walker::set_global_ranges_from_unreachable_edges (basic_block bb)
    1275              : {
    1276     24004939 :   edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
    1277     24004939 :   if (!pred_e)
    1278              :     return;
    1279              : 
    1280     17877598 :   gimple *stmt = *gsi_last_bb (pred_e->src);
    1281     17877598 :   if (!stmt
    1282     15038635 :       || gimple_code (stmt) != GIMPLE_COND
    1283     30235757 :       || !assert_unreachable_fallthru_edge_p (pred_e))
    1284              :     return;
    1285              : 
    1286              :   // Bail if the condition leading to the unreachable edge has 2 ssa-names.
    1287              :   // See PR 125501.
    1288       231624 :   if ((TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
    1289       231624 :       && TREE_CODE (gimple_cond_rhs (stmt)) == SSA_NAME))
    1290              :     return;
    1291              : 
    1292       229022 :   tree name;
    1293       641078 :   FOR_EACH_GORI_EXPORT_NAME (m_ranger->gori_ssa (), pred_e->src, name)
    1294       412056 :     if (all_uses_feed_or_dominated_by_stmt (name, stmt)
    1295              :         // The condition must post-dominate the definition point.
    1296       602794 :         && (SSA_NAME_IS_DEFAULT_DEF (name)
    1297       190599 :             || (gimple_bb (SSA_NAME_DEF_STMT (name))
    1298       190599 :                 == pred_e->src)))
    1299              :       {
    1300       184222 :         value_range r (TREE_TYPE (name));
    1301              : 
    1302       184222 :         if (m_ranger->range_on_edge (r, pred_e, name)
    1303       184222 :             && !r.varying_p ()
    1304       355570 :             && !r.undefined_p ())
    1305              :           {
    1306       171279 :             set_range_info (name, r);
    1307       171279 :             maybe_set_nonzero_bits (pred_e, name);
    1308              :           }
    1309       184222 :       }
    1310              : }
    1311              : 
    1312              : /* Record any equivalences created by the incoming edge to BB.  If BB
    1313              :    has more than one incoming edge, then no equivalence is created.  */
    1314              : 
    1315              : void
    1316     24004939 : dom_opt_dom_walker::record_equivalences_from_incoming_edge (basic_block bb)
    1317              : {
    1318     24004939 :   edge e;
    1319     24004939 :   basic_block parent;
    1320              : 
    1321              :   /* If our parent block ended with a control statement, then we may be
    1322              :      able to record some equivalences based on which outgoing edge from
    1323              :      the parent was followed.  */
    1324     24004939 :   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
    1325              : 
    1326     24004939 :   e = single_pred_edge_ignoring_loop_edges (bb, true);
    1327              : 
    1328              :   /* If we had a single incoming edge from our parent block, then enter
    1329              :      any data associated with the edge into our tables.  */
    1330     24004939 :   if (e && e->src == parent)
    1331     17883144 :     record_temporary_equivalences (e, m_const_and_copies, m_avail_exprs_stack,
    1332     17883144 :                                    m_state->get_blocks_on_stack ());
    1333     24004939 : }
    1334              : 
    1335              : /* Dump statistics for the hash table HTAB.  */
    1336              : 
    1337              : static void
    1338           36 : htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab)
    1339              : {
    1340           68 :   fprintf (file, "size " HOST_SIZE_T_PRINT_DEC ", " HOST_SIZE_T_PRINT_DEC
    1341              :            " elements, %f collision/search ratio\n",
    1342           36 :            (fmt_size_t) htab.size (),
    1343           36 :            (fmt_size_t) htab.elements (),
    1344              :            htab.collisions ());
    1345           36 : }
    1346              : 
    1347              : /* Dump SSA statistics on FILE.  */
    1348              : 
    1349              : static void
    1350           36 : dump_dominator_optimization_stats (FILE *file,
    1351              :                                    hash_table<expr_elt_hasher> *avail_exprs)
    1352              : {
    1353           36 :   fprintf (file, "Total number of statements:                   %6ld\n\n",
    1354              :            opt_stats.num_stmts);
    1355           36 :   fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
    1356              :            opt_stats.num_exprs_considered);
    1357              : 
    1358           36 :   fprintf (file, "\nHash table statistics:\n");
    1359              : 
    1360           36 :   fprintf (file, "    avail_exprs: ");
    1361           36 :   htab_statistics (file, *avail_exprs);
    1362           36 : }
    1363              : 
    1364              : 
    1365              : /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
    1366              :    This constrains the cases in which we may treat this as assignment.  */
    1367              : 
    1368              : static void
    1369     13645608 : record_equality (tree x, tree y, class const_and_copies *const_and_copies)
    1370              : {
    1371     13645608 :   tree prev_x = NULL, prev_y = NULL;
    1372              : 
    1373     13645608 :   if (tree_swap_operands_p (x, y))
    1374       611538 :     std::swap (x, y);
    1375              : 
    1376              :   /* Most of the time tree_swap_operands_p does what we want.  But there
    1377              :      are cases where we know one operand is better for copy propagation than
    1378              :      the other.  Given no other code cares about ordering of equality
    1379              :      comparison operators for that purpose, we just handle the special cases
    1380              :      here.  */
    1381     13645608 :   if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME)
    1382              :     {
    1383              :       /* If one operand is a single use operand, then make it
    1384              :          X.  This will preserve its single use properly and if this
    1385              :          conditional is eliminated, the computation of X can be
    1386              :          eliminated as well.  */
    1387      1120414 :       if (has_single_use (y) && ! has_single_use (x))
    1388              :         std::swap (x, y);
    1389              :     }
    1390     13645608 :   if (TREE_CODE (x) == SSA_NAME)
    1391     13645608 :     prev_x = SSA_NAME_VALUE (x);
    1392     13645608 :   if (TREE_CODE (y) == SSA_NAME)
    1393      1120414 :     prev_y = SSA_NAME_VALUE (y);
    1394              : 
    1395              :   /* If one of the previous values is invariant, or invariant in more loops
    1396              :      (by depth), then use that.
    1397              :      Otherwise it doesn't matter which value we choose, just so
    1398              :      long as we canonicalize on one value.  */
    1399     13645608 :   if (is_gimple_min_invariant (y))
    1400              :     ;
    1401      1120414 :   else if (is_gimple_min_invariant (x))
    1402              :     prev_x = x, x = y, y = prev_x, prev_x = prev_y;
    1403      1120414 :   else if (prev_x && is_gimple_min_invariant (prev_x))
    1404              :     x = y, y = prev_x, prev_x = prev_y;
    1405      1029471 :   else if (prev_y)
    1406     13645608 :     y = prev_y;
    1407              : 
    1408              :   /* After the swapping, we must have one SSA_NAME.  */
    1409     13645608 :   if (TREE_CODE (x) != SSA_NAME)
    1410              :     return;
    1411              : 
    1412              :   /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
    1413              :      variable compared against zero.  If we're honoring signed zeros,
    1414              :      then we cannot record this value unless we know that the value is
    1415              :      nonzero.  */
    1416     13645608 :   if (HONOR_SIGNED_ZEROS (x)
    1417     13645608 :       && (TREE_CODE (y) != REAL_CST
    1418       172560 :           || real_equal (&dconst0, &TREE_REAL_CST (y))))
    1419              :     return;
    1420              : 
    1421     13645271 :   const_and_copies->record_const_or_copy (x, y, prev_x);
    1422              : }
    1423              : 
    1424              : /* Returns true when STMT is a simple iv increment.  It detects the
    1425              :    following situation:
    1426              : 
    1427              :    i_1 = phi (..., i_k)
    1428              :    [...]
    1429              :    i_j = i_{j-1}  for each j : 2 <= j <= k-1
    1430              :    [...]
    1431              :    i_k = i_{k-1} +/- ...  */
    1432              : 
    1433              : bool
    1434     43939603 : simple_iv_increment_p (gimple *stmt)
    1435              : {
    1436     43939603 :   enum tree_code code;
    1437     43939603 :   tree lhs, preinc;
    1438     43939603 :   gimple *phi;
    1439     43939603 :   size_t i;
    1440              : 
    1441     43939603 :   if (gimple_code (stmt) != GIMPLE_ASSIGN)
    1442              :     return false;
    1443              : 
    1444     33761686 :   lhs = gimple_assign_lhs (stmt);
    1445     33761686 :   if (TREE_CODE (lhs) != SSA_NAME)
    1446              :     return false;
    1447              : 
    1448     33761686 :   code = gimple_assign_rhs_code (stmt);
    1449     33761686 :   if (code != PLUS_EXPR
    1450     33761686 :       && code != MINUS_EXPR
    1451     33761686 :       && code != POINTER_PLUS_EXPR)
    1452              :     return false;
    1453              : 
    1454      8092978 :   preinc = gimple_assign_rhs1 (stmt);
    1455      8092978 :   if (TREE_CODE (preinc) != SSA_NAME)
    1456              :     return false;
    1457              : 
    1458      7814485 :   phi = SSA_NAME_DEF_STMT (preinc);
    1459      7840524 :   while (gimple_code (phi) != GIMPLE_PHI)
    1460              :     {
    1461              :       /* Follow trivial copies, but not the DEF used in a back edge,
    1462              :          so that we don't prevent coalescing.  */
    1463      5292769 :       if (!gimple_assign_ssa_name_copy_p (phi))
    1464              :         return false;
    1465        26039 :       preinc = gimple_assign_rhs1 (phi);
    1466        26039 :       phi = SSA_NAME_DEF_STMT (preinc);
    1467              :     }
    1468              : 
    1469      4992149 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    1470      4043841 :     if (gimple_phi_arg_def (phi, i) == lhs)
    1471              :       return true;
    1472              : 
    1473              :   return false;
    1474              : }
    1475              : 
    1476              : /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the
    1477              :    successors of BB.  */
    1478              : 
    1479              : static void
    1480     24004939 : cprop_into_successor_phis (basic_block bb,
    1481              :                            class const_and_copies *const_and_copies)
    1482              : {
    1483     24004939 :   edge e;
    1484     24004939 :   edge_iterator ei;
    1485              : 
    1486     57014115 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1487              :     {
    1488     33009176 :       int indx;
    1489     33009176 :       gphi_iterator gsi;
    1490              : 
    1491              :       /* If this is an abnormal edge, then we do not want to copy propagate
    1492              :          into the PHI alternative associated with this edge.  */
    1493     33009176 :       if (e->flags & EDGE_ABNORMAL)
    1494     19422269 :         continue;
    1495              : 
    1496     32994681 :       gsi = gsi_start_phis (e->dest);
    1497     32994681 :       if (gsi_end_p (gsi))
    1498     19407774 :         continue;
    1499              : 
    1500              :       /* We may have an equivalence associated with this edge.  While
    1501              :          we cannot propagate it into non-dominated blocks, we can
    1502              :          propagate them into PHIs in non-dominated blocks.  */
    1503              : 
    1504              :       /* Push the unwind marker so we can reset the const and copies
    1505              :          table back to its original state after processing this edge.  */
    1506     13586907 :       const_and_copies->push_marker ();
    1507              : 
    1508              :       /* Extract and record any simple NAME = VALUE equivalences.
    1509              : 
    1510              :          Don't bother with [01] = COND equivalences, they're not useful
    1511              :          here.  */
    1512     13586907 :       class edge_info *edge_info = (class edge_info *) e->aux;
    1513              : 
    1514     13586907 :       if (edge_info)
    1515              :         {
    1516              :           edge_info::equiv_pair *seq;
    1517      8547923 :           for (int i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i)
    1518              :             {
    1519      3291530 :               tree lhs = seq->first;
    1520      3291530 :               tree rhs = seq->second;
    1521              : 
    1522      3291530 :               if (lhs && TREE_CODE (lhs) == SSA_NAME)
    1523      3291530 :                 const_and_copies->record_const_or_copy (lhs, rhs);
    1524              :             }
    1525              : 
    1526              :         }
    1527              : 
    1528     13586907 :       indx = e->dest_idx;
    1529     37206006 :       for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
    1530              :         {
    1531     23619099 :           tree new_val;
    1532     23619099 :           use_operand_p orig_p;
    1533     23619099 :           tree orig_val;
    1534     23619099 :           gphi *phi = gsi.phi ();
    1535              : 
    1536              :           /* The alternative may be associated with a constant, so verify
    1537              :              it is an SSA_NAME before doing anything with it.  */
    1538     23619099 :           orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
    1539     23619099 :           orig_val = get_use_from_ptr (orig_p);
    1540     23619099 :           if (TREE_CODE (orig_val) != SSA_NAME)
    1541      3254568 :             continue;
    1542              : 
    1543              :           /* If we have *ORIG_P in our constant/copy table, then replace
    1544              :              ORIG_P with its value in our constant/copy table.  */
    1545     20364531 :           new_val = SSA_NAME_VALUE (orig_val);
    1546     20364531 :           if (new_val
    1547     20364531 :               && new_val != orig_val
    1548     20364531 :               && may_propagate_copy (orig_val, new_val))
    1549      1169292 :             propagate_value (orig_p, new_val);
    1550              :         }
    1551              : 
    1552     13586907 :       const_and_copies->pop_to_marker ();
    1553              :     }
    1554     24004939 : }
    1555              : 
    1556              : edge
    1557     24004939 : dom_opt_dom_walker::before_dom_children (basic_block bb)
    1558              : {
    1559     24004939 :   gimple_stmt_iterator gsi;
    1560              : 
    1561     24004939 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1562          764 :     fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
    1563              : 
    1564              :   /* Push a marker on the stacks of local information so that we know how
    1565              :      far to unwind when we finalize this block.  */
    1566     24004939 :   m_avail_exprs_stack->push_marker ();
    1567     24004939 :   m_const_and_copies->push_marker ();
    1568     24004939 :   bitmap_set_bit (m_state->get_blocks_on_stack (), bb->index);
    1569              : 
    1570     24004939 :   record_equivalences_from_incoming_edge (bb);
    1571     24004939 :   set_global_ranges_from_unreachable_edges (bb);
    1572              : 
    1573              :   /* PHI nodes can create equivalences too.  */
    1574     24004939 :   record_equivalences_from_phis (bb);
    1575              : 
    1576              :   /* Create equivalences from redundant PHIs.  PHIs are only truly
    1577              :      redundant when they exist in the same block, so push another
    1578              :      marker and unwind right afterwards.  */
    1579     24004939 :   m_avail_exprs_stack->push_marker ();
    1580     32982671 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1581      8977732 :     eliminate_redundant_computations (&gsi);
    1582     24004939 :   m_avail_exprs_stack->pop_to_marker ();
    1583              : 
    1584     24004939 :   edge taken_edge = NULL;
    1585              :   /* Initialize visited flag ahead of us, it has undefined state on
    1586              :      pass entry.  */
    1587    229453981 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1588    181444103 :     gimple_set_visited (gsi_stmt (gsi), false);
    1589    386768715 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
    1590              :     {
    1591              :       /* Do not optimize a stmt twice, substitution might end up with
    1592              :          _3 = _3 which is not valid.  */
    1593    362763776 :       if (gimple_visited_p (gsi_stmt (gsi)))
    1594              :         {
    1595    181319514 :           gsi_next (&gsi);
    1596    181319514 :           continue;
    1597              :         }
    1598              : 
    1599    181444262 :       bool removed_p = false;
    1600    181444262 :       taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
    1601    181444262 :       if (!removed_p)
    1602              :         {
    1603    181319514 :           gimple *stmt = gsi_stmt (gsi);
    1604    181319514 :           gimple_set_visited (stmt, true);
    1605              : 
    1606              :           /* Propagation and folding may have added uses to STMT, which
    1607              :              back_propagate_equivalences has to consider.  */
    1608    181319514 :           tree lhs = gimple_get_lhs (stmt);
    1609    181319514 :           if (lhs && TREE_CODE (lhs) == SSA_NAME)
    1610              :             {
    1611     36703879 :               ssa_op_iter iter;
    1612     36703879 :               tree use;
    1613     72419238 :               FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
    1614     35715359 :                 bitmap_clear_bit (names_without_foldable_uses,
    1615     35715359 :                                   SSA_NAME_VERSION (use));
    1616              :             }
    1617              :         }
    1618              : 
    1619              :       /* Go back and visit stmts inserted by folding after substituting
    1620              :          into the stmt at gsi.  */
    1621    181444262 :       if (gsi_end_p (gsi))
    1622              :         {
    1623         2823 :           gcc_checking_assert (removed_p);
    1624         2823 :           gsi = gsi_last_bb (bb);
    1625         2823 :           while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi)))
    1626            0 :             gsi_prev (&gsi);
    1627              :         }
    1628              :       else
    1629              :         {
    1630    181441598 :           do
    1631              :             {
    1632    181441598 :               gsi_prev (&gsi);
    1633              :             }
    1634    362883037 :           while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi)));
    1635              :         }
    1636    181444262 :       if (gsi_end_p (gsi))
    1637     39600132 :         gsi = gsi_start_bb (bb);
    1638              :       else
    1639    161644196 :         gsi_next (&gsi);
    1640              :     }
    1641              : 
    1642              :   /* Now prepare to process dominated blocks.  */
    1643     24004939 :   record_edge_info (bb);
    1644     24004939 :   cprop_into_successor_phis (bb, m_const_and_copies);
    1645     24004939 :   if (taken_edge && !dbg_cnt (dom_unreachable_edges))
    1646            0 :     return NULL;
    1647              : 
    1648              :   return taken_edge;
    1649              : }
    1650              : 
    1651              : /* We have finished processing the dominator children of BB, perform
    1652              :    any finalization actions in preparation for leaving this node in
    1653              :    the dominator tree.  */
    1654              : 
    1655              : void
    1656     24004939 : dom_opt_dom_walker::after_dom_children (basic_block bb)
    1657              : {
    1658     24004939 :   if (param_dom_jump_threading)
    1659     24004190 :     m_threader->thread_outgoing_edges (bb);
    1660     24004939 :   bitmap_clear_bit (m_state->get_blocks_on_stack (), bb->index);
    1661     24004939 :   m_avail_exprs_stack->pop_to_marker ();
    1662     24004939 :   m_const_and_copies->pop_to_marker ();
    1663     24004939 : }
    1664              : 
    1665              : /* Return the constant STMT computes, and barring that, an operand its
    1666              :    result is equivalent to.  NULL if neither.  */
    1667              : 
    1668              : tree
    1669     64617251 : dom_opt_dom_walker::const_or_copy_of_stmt (gimple *stmt)
    1670              : {
    1671     64617251 :   if (tree val = m_ranger->value_of_stmt (stmt))
    1672              :     return val;
    1673              : 
    1674              :   /* We could remove this gate, but we'd end up with tons of useless
    1675              :      replacements (casts, copies, etc).  Best to keep it to binops, which is
    1676              :      what the original code did.  */
    1677     63897513 :   if (!is_gimple_assign (stmt)
    1678    108609737 :       || gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS)
    1679              :     return NULL_TREE;
    1680              : 
    1681     11913780 :   tree lhs = gimple_assign_lhs (stmt);
    1682     11913780 :   tree rhs1 = gimple_assign_rhs1 (stmt);
    1683     11913780 :   tree rhs2 = gimple_assign_rhs2 (stmt);
    1684     11913780 :   if (m_ranger->relation ().query (stmt, lhs, rhs1) == VREL_EQ)
    1685              :     return rhs1;
    1686     11910312 :   if (m_ranger->relation ().query (stmt, lhs, rhs2) == VREL_EQ)
    1687           43 :     return rhs2;
    1688              : 
    1689              :   return NULL_TREE;
    1690              : }
    1691              : 
    1692              : /* Search for redundant computations in STMT.  If any are found, then
    1693              :    replace them with the variable holding the result of the computation.
    1694              : 
    1695              :    If safe, record this expression into the tables.  */
    1696              : 
    1697              : void
    1698     65095110 : dom_opt_dom_walker::eliminate_redundant_computations (gimple_stmt_iterator *gsi)
    1699              : {
    1700     65095110 :   tree expr_type;
    1701     65095110 :   tree cached_lhs;
    1702     65095110 :   tree def;
    1703     65095110 :   bool insert = true;
    1704     65095110 :   bool assigns_var_p = false;
    1705              : 
    1706     65095110 :   gimple *stmt = gsi_stmt (*gsi);
    1707              : 
    1708     65095110 :   if (gimple_code (stmt) == GIMPLE_PHI)
    1709      8977732 :     def = gimple_phi_result (stmt);
    1710              :   else
    1711     56117378 :     def = gimple_get_lhs (stmt);
    1712              : 
    1713              :   /* Certain expressions on the RHS can be optimized away, but cannot
    1714              :      themselves be entered into the hash tables.  */
    1715     65095110 :   if (! def
    1716     55844379 :       || TREE_CODE (def) != SSA_NAME
    1717     42814227 :       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
    1718     33835081 :       || gimple_vdef (stmt)
    1719              :       /* Do not record equivalences for increments of ivs.  This would create
    1720              :          overlapping live ranges for a very questionable gain.  */
    1721    107898206 :       || simple_iv_increment_p (stmt))
    1722              :     insert = false;
    1723              : 
    1724              :   /* Check if the expression has been computed before.  */
    1725     65095110 :   cached_lhs = m_avail_exprs_stack->lookup_avail_expr (stmt, insert, true);
    1726              : 
    1727              :   /* Otherwise, ask the ranger.  */
    1728     65095110 :   if (!cached_lhs)
    1729     64617251 :     cached_lhs = const_or_copy_of_stmt (stmt);
    1730              : 
    1731     65095110 :   opt_stats.num_exprs_considered++;
    1732              : 
    1733              :   /* Get the type of the expression we are trying to optimize.  */
    1734     65095110 :   if (is_gimple_assign (stmt))
    1735              :     {
    1736     45596886 :       expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
    1737     45596886 :       assigns_var_p = true;
    1738              :     }
    1739     19498224 :   else if (gimple_code (stmt) == GIMPLE_COND)
    1740      9214438 :     expr_type = boolean_type_node;
    1741     10283786 :   else if (is_gimple_call (stmt))
    1742              :     {
    1743      1269761 :       gcc_assert (gimple_call_lhs (stmt));
    1744      1269761 :       expr_type = TREE_TYPE (gimple_call_lhs (stmt));
    1745      1269761 :       assigns_var_p = true;
    1746              :     }
    1747      9014025 :   else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
    1748        36293 :     expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt));
    1749      8977732 :   else if (gimple_code (stmt) == GIMPLE_PHI)
    1750              :     /* We can't propagate into a phi, so the logic below doesn't apply.
    1751              :        Instead record an equivalence between the cached LHS and the
    1752              :        PHI result of this statement, provided they are in the same block.
    1753              :        This should be sufficient to kill the redundant phi.  */
    1754              :     {
    1755      8977732 :       if (def && cached_lhs)
    1756       252896 :         m_const_and_copies->record_const_or_copy (def, cached_lhs);
    1757              :       return;
    1758              :     }
    1759              :   else
    1760            0 :     gcc_unreachable ();
    1761              : 
    1762     56117378 :   if (!cached_lhs)
    1763              :     return;
    1764              : 
    1765              :   /* It is safe to ignore types here since we have already done
    1766              :      type checking in the hashing and equality routines.  In fact
    1767              :      type checking here merely gets in the way of constant
    1768              :      propagation.  Also, make sure that it is safe to propagate
    1769              :      CACHED_LHS into the expression in STMT.  */
    1770       948212 :   if ((TREE_CODE (cached_lhs) != SSA_NAME
    1771       554606 :        && (assigns_var_p
    1772        30189 :            || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
    1773       948212 :       || may_propagate_copy_into_stmt (stmt, cached_lhs))
    1774              :   {
    1775       933422 :       gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
    1776              :                            || is_gimple_min_invariant (cached_lhs));
    1777              : 
    1778       933422 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1779              :         {
    1780           19 :           fprintf (dump_file, "  Replaced redundant expr '");
    1781           19 :           print_gimple_expr (dump_file, stmt, 0, dump_flags);
    1782           19 :           fprintf (dump_file, "' with '");
    1783           19 :           print_generic_expr (dump_file, cached_lhs, dump_flags);
    1784           19 :           fprintf (dump_file, "'\n");
    1785              :         }
    1786              : 
    1787       933422 :       opt_stats.num_re++;
    1788              : 
    1789       933422 :       if (assigns_var_p
    1790       933422 :           && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
    1791            0 :         cached_lhs = fold_convert (expr_type, cached_lhs);
    1792              : 
    1793       933422 :       propagate_tree_value_into_stmt (gsi, cached_lhs);
    1794              : 
    1795              :       /* Since it is always necessary to mark the result as modified,
    1796              :          perhaps we should move this into propagate_tree_value_into_stmt
    1797              :          itself.  */
    1798       933422 :       gimple_set_modified (gsi_stmt (*gsi), true);
    1799              :   }
    1800              : }
    1801              : 
    1802              : /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
    1803              :    the available expressions table or the const_and_copies table.
    1804              :    Detect and record those equivalences.
    1805              : 
    1806              :    We handle only very simple copy equivalences here.  The heavy
    1807              :    lifing is done by eliminate_redundant_computations.  */
    1808              : 
    1809              : void
    1810     49295261 : dom_opt_dom_walker::record_equivalences_from_stmt (gimple *stmt,
    1811              :                                                    int may_optimize_p)
    1812              : {
    1813     49295261 :   tree lhs;
    1814     49295261 :   enum tree_code lhs_code;
    1815              : 
    1816     49295261 :   gcc_assert (is_gimple_assign (stmt));
    1817              : 
    1818     49295261 :   lhs = gimple_assign_lhs (stmt);
    1819     49295261 :   lhs_code = TREE_CODE (lhs);
    1820              : 
    1821     49295261 :   if (lhs_code == SSA_NAME
    1822     49295261 :       && gimple_assign_single_p (stmt))
    1823              :     {
    1824     16121356 :       tree rhs = gimple_assign_rhs1 (stmt);
    1825              : 
    1826              :       /* If the RHS of the assignment is a constant or another variable that
    1827              :          may be propagated, register it in the CONST_AND_COPIES table.  We
    1828              :          do not need to record unwind data for this, since this is a true
    1829              :          assignment and not an equivalence inferred from a comparison.  All
    1830              :          uses of this ssa name are dominated by this assignment, so unwinding
    1831              :          just costs time and space.  */
    1832     16121356 :       if (may_optimize_p
    1833     16121356 :           && (TREE_CODE (rhs) == SSA_NAME
    1834     14028945 :               || is_gimple_min_invariant (rhs)))
    1835              :         {
    1836      2106399 :           rhs = dom_valueize (rhs);
    1837              : 
    1838      2106399 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1839              :             {
    1840           73 :               fprintf (dump_file, "==== ASGN ");
    1841           73 :               print_generic_expr (dump_file, lhs);
    1842           73 :               fprintf (dump_file, " = ");
    1843           73 :               print_generic_expr (dump_file, rhs);
    1844           73 :               fprintf (dump_file, "\n");
    1845              :             }
    1846              : 
    1847      2106399 :           set_ssa_name_value (lhs, rhs);
    1848              :         }
    1849              :     }
    1850              : 
    1851              :   /* Make sure we can propagate &x + CST.  */
    1852     49295261 :   if (lhs_code == SSA_NAME
    1853     33222349 :       && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR
    1854      1675396 :       && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR
    1855     49493321 :       && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST)
    1856              :     {
    1857         7254 :       tree op0 = gimple_assign_rhs1 (stmt);
    1858         7254 :       tree op1 = gimple_assign_rhs2 (stmt);
    1859         7254 :       tree new_rhs
    1860        14508 :         = build1 (ADDR_EXPR, TREE_TYPE (op0),
    1861         7254 :                   fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (op0)),
    1862              :                                unshare_expr (op0), fold_convert (ptr_type_node,
    1863              :                                                                  op1)));
    1864         7254 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1865              :         {
    1866            0 :           fprintf (dump_file, "==== ASGN ");
    1867            0 :           print_generic_expr (dump_file, lhs);
    1868            0 :           fprintf (dump_file, " = ");
    1869            0 :           print_generic_expr (dump_file, new_rhs);
    1870            0 :           fprintf (dump_file, "\n");
    1871              :         }
    1872              : 
    1873         7254 :       set_ssa_name_value (lhs, new_rhs);
    1874              :     }
    1875              : 
    1876              :   /* A memory store, even an aliased store, creates a useful
    1877              :      equivalence.  By exchanging the LHS and RHS, creating suitable
    1878              :      vops and recording the result in the available expression table,
    1879              :      we may be able to expose more redundant loads.  */
    1880     94775651 :   if (!gimple_has_volatile_ops (stmt)
    1881     73953900 :       && gimple_references_memory_p (stmt)
    1882     24658639 :       && gimple_assign_single_p (stmt)
    1883     24658639 :       && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
    1884     19269550 :           || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
    1885     61149188 :       && !is_gimple_reg (lhs))
    1886              :     {
    1887     11687122 :       tree rhs = gimple_assign_rhs1 (stmt);
    1888     11687122 :       gassign *new_stmt;
    1889              : 
    1890              :       /* Build a new statement with the RHS and LHS exchanged.  */
    1891     11687122 :       if (TREE_CODE (rhs) == SSA_NAME)
    1892              :         {
    1893              :           /* NOTE tuples.  The call to gimple_build_assign below replaced
    1894              :              a call to build_gimple_modify_stmt, which did not set the
    1895              :              SSA_NAME_DEF_STMT on the LHS of the assignment.  Doing so
    1896              :              may cause an SSA validation failure, as the LHS may be a
    1897              :              default-initialized name and should have no definition.  I'm
    1898              :              a bit dubious of this, as the artificial statement that we
    1899              :              generate here may in fact be ill-formed, but it is simply
    1900              :              used as an internal device in this pass, and never becomes
    1901              :              part of the CFG.  */
    1902      5253906 :           gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
    1903      5253906 :           new_stmt = gimple_build_assign (rhs, lhs);
    1904      5253906 :           SSA_NAME_DEF_STMT (rhs) = defstmt;
    1905              :         }
    1906              :       else
    1907      6433216 :         new_stmt = gimple_build_assign (rhs, lhs);
    1908              : 
    1909     23374244 :       gimple_set_vuse (new_stmt, gimple_vdef (stmt));
    1910              : 
    1911              :       /* Finally enter the statement into the available expression
    1912              :          table.  */
    1913     11687122 :       m_avail_exprs_stack->lookup_avail_expr (new_stmt, true, true);
    1914              :     }
    1915     49295261 : }
    1916              : 
    1917              : /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
    1918              :    CONST_AND_COPIES.  */
    1919              : 
    1920              : static void
    1921     82178888 : cprop_operand (gimple *stmt, use_operand_p op_p, range_query *query)
    1922              : {
    1923     82178888 :   tree val;
    1924     82178888 :   tree op = USE_FROM_PTR (op_p);
    1925              : 
    1926              :   /* If the operand has a known constant value or it is known to be a
    1927              :      copy of some other variable, use the value or copy stored in
    1928              :      CONST_AND_COPIES.  */
    1929     82178888 :   val = SSA_NAME_VALUE (op);
    1930     55638737 :   if (!val)
    1931              :     {
    1932     78088620 :       value_range r (TREE_TYPE (op));
    1933     78088620 :       tree single;
    1934    153721276 :       if (query->range_of_expr (r, op, stmt) && r.singleton_p (&single))
    1935        10576 :         val = single;
    1936     78088620 :     }
    1937              : 
    1938     82178888 :   if (val && val != op)
    1939              :     {
    1940              :       /* Certain operands are not allowed to be copy propagated due
    1941              :          to their interaction with exception handling and some GCC
    1942              :          extensions.  */
    1943      4099311 :       if (!may_propagate_copy (op, val))
    1944              :         return;
    1945              : 
    1946              :       /* Do not propagate copies into BIVs.
    1947              :          See PR23821 and PR62217 for how this can disturb IV and
    1948              :          number of iteration analysis.  */
    1949      4097676 :       if (TREE_CODE (val) != INTEGER_CST)
    1950              :         {
    1951      3307722 :           gimple *def = SSA_NAME_DEF_STMT (op);
    1952      3307722 :           if (gimple_code (def) == GIMPLE_PHI
    1953      3307722 :               && gimple_bb (def)->loop_father->header == gimple_bb (def))
    1954              :             return;
    1955              :         }
    1956              : 
    1957              :       /* Dump details.  */
    1958      4086339 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1959              :         {
    1960           76 :           fprintf (dump_file, "  Replaced '");
    1961           76 :           print_generic_expr (dump_file, op, dump_flags);
    1962           76 :           fprintf (dump_file, "' with %s '",
    1963           76 :                    (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
    1964           76 :           print_generic_expr (dump_file, val, dump_flags);
    1965           76 :           fprintf (dump_file, "'\n");
    1966              :         }
    1967              : 
    1968      4086339 :       if (TREE_CODE (val) != SSA_NAME)
    1969       968701 :         opt_stats.num_const_prop++;
    1970              :       else
    1971      3117638 :         opt_stats.num_copy_prop++;
    1972              : 
    1973      4086339 :       propagate_value (op_p, val);
    1974              : 
    1975              :       /* And note that we modified this statement.  This is now
    1976              :          safe, even if we changed virtual operands since we will
    1977              :          rescan the statement and rewrite its operands again.  */
    1978      4086339 :       gimple_set_modified (stmt, true);
    1979              :     }
    1980              : }
    1981              : 
    1982              : /* Fold the conditional STMT with range info.  */
    1983              : 
    1984              : void
    1985     55059208 : dom_opt_dom_walker::fold_cond (gimple *stmt)
    1986              : {
    1987     55059208 :   gcond *cond = dyn_cast <gcond *> (stmt);
    1988     55059208 :   if (!cond)
    1989     45896557 :     return;
    1990              : 
    1991      9162651 :   simplify_using_ranges simplify (m_ranger);
    1992      9162651 :   if (simplify.fold_cond (cond))
    1993        84371 :     gimple_set_modified (cond, true);
    1994      9162651 : }
    1995              : 
    1996              : /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
    1997              :    known value for that SSA_NAME (or NULL if no value is known).
    1998              : 
    1999              :    Propagate values from CONST_AND_COPIES into the uses, vuses and
    2000              :    vdef_ops of STMT.  */
    2001              : 
    2002              : static void
    2003    181444262 : cprop_into_stmt (gimple *stmt, range_query *query)
    2004              : {
    2005    181444262 :   use_operand_p op_p;
    2006    181444262 :   ssa_op_iter iter;
    2007    181444262 :   tree last_copy_propagated_op = NULL;
    2008              : 
    2009    263623822 :   FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE)
    2010              :     {
    2011     82179560 :       tree old_op = USE_FROM_PTR (op_p);
    2012              : 
    2013              :       /* If we have A = B and B = A in the copy propagation tables
    2014              :          (due to an equality comparison), avoid substituting B for A
    2015              :          then A for B in the trivially discovered cases.   This allows
    2016              :          optimization of statements were A and B appear as input
    2017              :          operands.  */
    2018     82179560 :       if (old_op != last_copy_propagated_op)
    2019              :         {
    2020     82178888 :           cprop_operand (stmt, op_p, query);
    2021              : 
    2022     82178888 :           tree new_op = USE_FROM_PTR (op_p);
    2023     82178888 :           if (new_op != old_op && TREE_CODE (new_op) == SSA_NAME)
    2024     82179560 :             last_copy_propagated_op = new_op;
    2025              :         }
    2026              :     }
    2027    181444262 : }
    2028              : 
    2029              : /* If STMT is a comparison of two uniform vectors reduce it to a comparison
    2030              :    of scalar objects, otherwise leave STMT unchanged.  */
    2031              : 
    2032              : static void
    2033    181444262 : reduce_vector_comparison_to_scalar_comparison (gimple *stmt)
    2034              : {
    2035    181444262 :   if (gimple_code (stmt) == GIMPLE_COND)
    2036              :     {
    2037      9214438 :       tree lhs = gimple_cond_lhs (stmt);
    2038      9214438 :       tree rhs = gimple_cond_rhs (stmt);
    2039              : 
    2040              :       /* We may have a vector comparison where both arms are uniform
    2041              :          vectors.  If so, we can simplify the vector comparison down
    2042              :          to a scalar comparison.  */
    2043      9214438 :       if (VECTOR_TYPE_P (TREE_TYPE (lhs))
    2044      9214438 :           && VECTOR_TYPE_P (TREE_TYPE (rhs)))
    2045              :         {
    2046              :           /* If either operand is an SSA_NAME, then look back to its
    2047              :              defining statement to try and get at a suitable source.  */
    2048         2566 :           if (TREE_CODE (rhs) == SSA_NAME)
    2049              :             {
    2050            0 :               gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
    2051            0 :               if (gimple_assign_single_p (def_stmt))
    2052            0 :                 rhs = gimple_assign_rhs1 (def_stmt);
    2053              :             }
    2054              : 
    2055         2566 :           if (TREE_CODE (lhs) == SSA_NAME)
    2056              :             {
    2057         2566 :               gimple *def_stmt = SSA_NAME_DEF_STMT (lhs);
    2058         2566 :               if (gimple_assign_single_p (def_stmt))
    2059            4 :                 lhs = gimple_assign_rhs1 (def_stmt);
    2060              :             }
    2061              : 
    2062              :           /* Now see if they are both uniform vectors and if so replace
    2063              :              the vector comparison with a scalar comparison.  */
    2064         2566 :           tree rhs_elem = rhs ? uniform_vector_p (rhs) : NULL_TREE;
    2065         2566 :           tree lhs_elem = lhs ? uniform_vector_p (lhs) : NULL_TREE;
    2066         2566 :           if (rhs_elem && lhs_elem)
    2067              :             {
    2068            3 :               if (dump_file && dump_flags & TDF_DETAILS)
    2069              :                 {
    2070            0 :                   fprintf (dump_file, "Reducing vector comparison: ");
    2071            0 :                   print_gimple_stmt (dump_file, stmt, 0);
    2072              :                 }
    2073              : 
    2074            3 :               gimple_cond_set_rhs (as_a <gcond *>(stmt), rhs_elem);
    2075            3 :               gimple_cond_set_lhs (as_a <gcond *>(stmt), lhs_elem);
    2076            3 :               gimple_set_modified (stmt, true);
    2077              : 
    2078            3 :               if (dump_file && dump_flags & TDF_DETAILS)
    2079              :                 {
    2080            0 :                   fprintf (dump_file, "To scalar equivalent: ");
    2081            0 :                   print_gimple_stmt (dump_file, stmt, 0);
    2082            0 :                   fprintf (dump_file, "\n");
    2083              :                 }
    2084              :             }
    2085              :         }
    2086              :     }
    2087    181444262 : }
    2088              : 
    2089              : /* Optimize the statement in block BB pointed to by iterator SI.
    2090              : 
    2091              :    We try to perform some simplistic global redundancy elimination and
    2092              :    constant propagation:
    2093              : 
    2094              :    1- To detect global redundancy, we keep track of expressions that have
    2095              :       been computed in this block and its dominators.  If we find that the
    2096              :       same expression is computed more than once, we eliminate repeated
    2097              :       computations by using the target of the first one.
    2098              : 
    2099              :    2- Constant values and copy assignments.  This is used to do very
    2100              :       simplistic constant and copy propagation.  When a constant or copy
    2101              :       assignment is found, we map the value on the RHS of the assignment to
    2102              :       the variable in the LHS in the CONST_AND_COPIES table.
    2103              : 
    2104              :    3- Very simple redundant store elimination is performed.
    2105              : 
    2106              :    4- We can simplify a condition to a constant or from a relational
    2107              :       condition to an equality condition.  */
    2108              : 
    2109              : edge
    2110    181444262 : dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator *si,
    2111              :                                    bool *removed_p)
    2112              : {
    2113    181444262 :   gimple *stmt, *old_stmt;
    2114    181444262 :   bool may_optimize_p;
    2115    181444262 :   bool modified_p = false;
    2116    181444262 :   bool was_noreturn;
    2117    181444262 :   edge retval = NULL;
    2118              : 
    2119    181444262 :   old_stmt = stmt = gsi_stmt (*si);
    2120    181444262 :   was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt);
    2121              : 
    2122    181444262 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2123              :     {
    2124         1623 :       fprintf (dump_file, "Optimizing statement ");
    2125         1623 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2126              :     }
    2127              : 
    2128              :   /* STMT may be a comparison of uniform vectors that we can simplify
    2129              :      down to a comparison of scalars.  Do that transformation first
    2130              :      so that all the scalar optimizations from here onward apply.  */
    2131    181444262 :   reduce_vector_comparison_to_scalar_comparison (stmt);
    2132              : 
    2133    181444262 :   update_stmt_if_modified (stmt);
    2134    181444262 :   opt_stats.num_stmts++;
    2135              : 
    2136              :   /* Const/copy propagate into USES, VUSES and the RHS of VDEFs.  */
    2137    181444262 :   cprop_into_stmt (stmt, m_ranger);
    2138              : 
    2139              :   /* If the statement has been modified with constant replacements,
    2140              :      fold its RHS before checking for redundant computations.  */
    2141    362561348 :   if (gimple_modified_p (stmt))
    2142              :     {
    2143      3918141 :       tree rhs = NULL;
    2144              : 
    2145              :       /* Try to fold the statement making sure that STMT is kept
    2146              :          up to date.  */
    2147      3918141 :       if (fold_stmt (si))
    2148              :         {
    2149       406884 :           stmt = gsi_stmt (*si);
    2150       406884 :           gimple_set_modified (stmt, true);
    2151              : 
    2152       406884 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2153              :             {
    2154           10 :               fprintf (dump_file, "  Folded to: ");
    2155           10 :               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2156              :             }
    2157              :         }
    2158              : 
    2159              :       /* We only need to consider cases that can yield a gimple operand.  */
    2160      3918141 :       if (gimple_assign_single_p (stmt))
    2161      1461242 :         rhs = gimple_assign_rhs1 (stmt);
    2162      2456899 :       else if (gimple_code (stmt) == GIMPLE_GOTO)
    2163            2 :         rhs = gimple_goto_dest (stmt);
    2164    181446204 :       else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
    2165              :         /* This should never be an ADDR_EXPR.  */
    2166         1942 :         rhs = gimple_switch_index (swtch_stmt);
    2167              : 
    2168      1463186 :       if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
    2169        82594 :         recompute_tree_invariant_for_addr_expr (rhs);
    2170              : 
    2171              :       /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
    2172              :          even if fold_stmt updated the stmt already and thus cleared
    2173              :          gimple_modified_p flag on it.  */
    2174              :       modified_p = true;
    2175              :     }
    2176              : 
    2177              :   /* Check for redundant computations.  Do this optimization only
    2178              :      for assignments that have no volatile ops and conditionals.  */
    2179    181444262 :   may_optimize_p = (!gimple_has_side_effects (stmt)
    2180    181444262 :                     && (is_gimple_assign (stmt)
    2181    122157035 :                         || (is_gimple_call (stmt)
    2182      1274119 :                             && gimple_call_lhs (stmt) != NULL_TREE)
    2183    120883280 :                         || gimple_code (stmt) == GIMPLE_COND
    2184    111668842 :                         || gimple_code (stmt) == GIMPLE_SWITCH));
    2185              : 
    2186              :   if (may_optimize_p)
    2187              :     {
    2188     56117378 :       if (gimple_code (stmt) == GIMPLE_CALL)
    2189              :         {
    2190              :           /* Resolve __builtin_constant_p.  If it hasn't been
    2191              :              folded to integer_one_node by now, it's fairly
    2192              :              certain that the value simply isn't constant.  */
    2193      1273755 :           tree callee = gimple_call_fndecl (stmt);
    2194      1273755 :           if (callee
    2195      1273755 :               && fndecl_built_in_p (callee, BUILT_IN_CONSTANT_P))
    2196              :             {
    2197         3994 :               propagate_tree_value_into_stmt (si, integer_zero_node);
    2198         3994 :               stmt = gsi_stmt (*si);
    2199              :             }
    2200              :         }
    2201              : 
    2202     56117378 :       update_stmt_if_modified (stmt);
    2203     56117378 :       eliminate_redundant_computations (si);
    2204     56117378 :       stmt = gsi_stmt (*si);
    2205              : 
    2206              :       /* Perform simple redundant store elimination.  */
    2207     56117378 :       if (gimple_assign_single_p (stmt)
    2208     28504145 :           && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME
    2209     69087719 :           && (TREE_CODE (gimple_assign_lhs (stmt)) != VAR_DECL
    2210      1059424 :               || !DECL_HARD_REGISTER (gimple_assign_lhs (stmt))))
    2211              :         {
    2212     12968273 :           tree lhs = gimple_assign_lhs (stmt);
    2213     12968273 :           tree rhs = gimple_assign_rhs1 (stmt);
    2214     12968273 :           tree cached_lhs;
    2215     12968273 :           gassign *new_stmt;
    2216     12968273 :           rhs = dom_valueize (rhs);
    2217              :           /* Build a new statement with the RHS and LHS exchanged.  */
    2218     12968273 :           if (TREE_CODE (rhs) == SSA_NAME)
    2219              :             {
    2220      5374631 :               gimple *defstmt = SSA_NAME_DEF_STMT (rhs);
    2221      5374631 :               new_stmt = gimple_build_assign (rhs, lhs);
    2222      5374631 :               SSA_NAME_DEF_STMT (rhs) = defstmt;
    2223              :             }
    2224              :           else
    2225      7593642 :             new_stmt = gimple_build_assign (rhs, lhs);
    2226     25936546 :           gimple_set_vuse (new_stmt, gimple_vuse (stmt));
    2227     12968273 :           expr_hash_elt *elt = NULL;
    2228     12968273 :           cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false,
    2229              :                                                                false, &elt);
    2230     12968273 :           if (cached_lhs
    2231       850907 :               && operand_equal_p (rhs, cached_lhs, 0)
    2232     13226823 :               && refs_same_for_tbaa_p (elt->expr ()->kind == EXPR_SINGLE
    2233       129275 :                                        ? elt->expr ()->ops.single.rhs
    2234              :                                        : NULL_TREE, lhs))
    2235              :             {
    2236       124748 :               basic_block bb = gimple_bb (stmt);
    2237       124748 :               unlink_stmt_vdef (stmt);
    2238       124748 :               if (gsi_remove (si, true))
    2239              :                 {
    2240            0 :                   bitmap_set_bit (need_eh_cleanup, bb->index);
    2241            0 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    2242            0 :                     fprintf (dump_file, "  Flagged to clear EH edges.\n");
    2243              :                 }
    2244       124748 :               release_defs (stmt);
    2245       124748 :               *removed_p = true;
    2246       124748 :               return retval;
    2247              :             }
    2248              :         }
    2249              : 
    2250              :       /* If this statement was not redundant, we may still be able to simplify
    2251              :          it, which may in turn allow other part of DOM or other passes to do
    2252              :          a better job.  */
    2253    111985260 :       if (!gimple_modified_p (stmt))
    2254     55059208 :         fold_cond (stmt);
    2255              :     }
    2256              : 
    2257              :   /* Record any additional equivalences created by this statement.  */
    2258    181319514 :   if (is_gimple_assign (stmt))
    2259     49295261 :     record_equivalences_from_stmt (stmt, may_optimize_p);
    2260              : 
    2261              :   /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may
    2262              :      know where it goes.  */
    2263    362639028 :   if (gimple_modified_p (stmt) || modified_p)
    2264              :     {
    2265      4532108 :       tree val = NULL;
    2266              : 
    2267      4532108 :       if (gimple_code (stmt) == GIMPLE_COND)
    2268       572698 :         val = fold_binary_loc (gimple_location (stmt),
    2269              :                                gimple_cond_code (stmt), boolean_type_node,
    2270              :                                gimple_cond_lhs (stmt),
    2271              :                                gimple_cond_rhs (stmt));
    2272      3959410 :       else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt))
    2273         1942 :         val = gimple_switch_index (swtch_stmt);
    2274              : 
    2275       574640 :       if (val && TREE_CODE (val) == INTEGER_CST)
    2276              :         {
    2277       181558 :           retval = find_taken_edge (bb, val);
    2278       181558 :           if (retval)
    2279              :             {
    2280              :               /* Fix the condition to be either true or false.  */
    2281       181558 :               if (gimple_code (stmt) == GIMPLE_COND)
    2282              :                 {
    2283       181543 :                   if (integer_zerop (val))
    2284       119839 :                     gimple_cond_make_false (as_a <gcond *> (stmt));
    2285        61704 :                   else if (integer_onep (val))
    2286        61704 :                     gimple_cond_make_true (as_a <gcond *> (stmt));
    2287              :                   else
    2288            0 :                     gcc_unreachable ();
    2289              : 
    2290       181543 :                   gimple_set_modified (stmt, true);
    2291              :                 }
    2292              : 
    2293              :               /* Further simplifications may be possible.  */
    2294       181558 :               cfg_altered = true;
    2295              :             }
    2296              :         }
    2297              : 
    2298      4532108 :       update_stmt_if_modified (stmt);
    2299              : 
    2300              :       /* If we simplified a statement in such a way as to be shown that it
    2301              :          cannot trap, update the eh information and the cfg to match.  */
    2302      4532108 :       if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
    2303              :         {
    2304         1411 :           bitmap_set_bit (need_eh_cleanup, bb->index);
    2305         1411 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2306            0 :             fprintf (dump_file, "  Flagged to clear EH edges.\n");
    2307              :         }
    2308              : 
    2309      4532108 :       if (!was_noreturn
    2310      4532108 :           && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
    2311            6 :         need_noreturn_fixup.safe_push (stmt);
    2312              :     }
    2313              :   return retval;
    2314              : }
        

Generated by: LCOV version 2.5.0-beta

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