LCOV - code coverage report
Current view: top level - gcc - gimple-predicate-analysis.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 86.2 % 947 816
Test Date: 2026-11-14 16:39:50 Functions: 94.2 % 52 49
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Support for simple predicate analysis.
       2              : 
       3              :    Copyright (C) 2001-2026 Free Software Foundation, Inc.
       4              :    Contributed by Xinliang David Li <davidxl@google.com>
       5              :    Generalized by Martin Sebor <msebor@redhat.com>
       6              : 
       7              :    This file is part of GCC.
       8              : 
       9              :    GCC is free software; you can redistribute it and/or modify
      10              :    it under the terms of the GNU General Public License as published by
      11              :    the Free Software Foundation; either version 3, or (at your option)
      12              :    any later version.
      13              : 
      14              :    GCC is distributed in the hope that it will be useful,
      15              :    but WITHOUT ANY WARRANTY; without even the implied warranty of
      16              :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      17              :    GNU General Public License for more details.
      18              : 
      19              :    You should have received a copy of the GNU General Public License
      20              :    along with GCC; see the file COPYING3.  If not see
      21              :    <http://www.gnu.org/licenses/>.  */
      22              : 
      23              : #define INCLUDE_STRING
      24              : #include "config.h"
      25              : #include "system.h"
      26              : #include "coretypes.h"
      27              : #include "backend.h"
      28              : #include "tree.h"
      29              : #include "gimple.h"
      30              : #include "tree-pass.h"
      31              : #include "ssa.h"
      32              : #include "gimple-pretty-print.h"
      33              : #include "diagnostic-core.h"
      34              : #include "fold-const.h"
      35              : #include "gimple-iterator.h"
      36              : #include "tree-ssa.h"
      37              : #include "tree-cfg.h"
      38              : #include "cfghooks.h"
      39              : #include "attribs.h"
      40              : #include "builtins.h"
      41              : #include "calls.h"
      42              : #include "value-query.h"
      43              : #include "cfganal.h"
      44              : #include "tree-eh.h"
      45              : #include "gimple-fold.h"
      46              : 
      47              : #include "gimple-predicate-analysis.h"
      48              : 
      49              : #define DEBUG_PREDICATE_ANALYZER 1
      50              : 
      51              : /* In our predicate normal form we have MAX_NUM_CHAINS or predicates
      52              :    and in those MAX_CHAIN_LEN (inverted) and predicates.  */
      53              : #define MAX_NUM_CHAINS (unsigned)param_uninit_max_num_chains
      54              : #define MAX_CHAIN_LEN (unsigned)param_uninit_max_chain_len
      55              : 
      56              : /* Return true if X1 is the negation of X2.  */
      57              : 
      58              : static inline bool
      59          550 : pred_neg_p (const pred_info &x1, const pred_info &x2)
      60              : {
      61          550 :   if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
      62          550 :       || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
      63              :     return false;
      64              : 
      65          100 :   tree_code c1 = x1.cond_code, c2;
      66          100 :   if (x1.invert == x2.invert)
      67            0 :     c2 = invert_tree_comparison (x2.cond_code, false);
      68              :   else
      69          100 :     c2 = x2.cond_code;
      70              : 
      71          100 :   return c1 == c2;
      72              : }
      73              : 
      74              : /* Return whether the condition (VAL CMPC BOUNDARY) is true.  */
      75              : 
      76              : static bool
      77          681 : is_value_included_in (tree val, tree boundary, tree_code cmpc)
      78              : {
      79              :   /* Only handle integer constant here.  */
      80          681 :   if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
      81              :     return true;
      82              : 
      83          681 :   bool inverted = false;
      84          681 :   if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
      85              :     {
      86          575 :       cmpc = invert_tree_comparison (cmpc, false);
      87          575 :       inverted = true;
      88              :     }
      89              : 
      90          681 :   bool result;
      91          681 :   if (cmpc == EQ_EXPR)
      92          652 :     result = tree_int_cst_equal (val, boundary);
      93           29 :   else if (cmpc == LT_EXPR)
      94           14 :     result = tree_int_cst_lt (val, boundary);
      95              :   else
      96              :     {
      97           15 :       gcc_assert (cmpc == LE_EXPR);
      98           15 :       result = tree_int_cst_le (val, boundary);
      99              :     }
     100              : 
     101          681 :   if (inverted)
     102          575 :     result ^= 1;
     103              : 
     104              :   return result;
     105              : }
     106              : 
     107              : /* Format the vector of edges EV as a string.  */
     108              : 
     109              : static std::string
     110           15 : format_edge_vec (const vec<edge> &ev)
     111              : {
     112           15 :   std::string str;
     113              : 
     114           15 :   unsigned n = ev.length ();
     115           32 :   for (unsigned i = 0; i < n; ++i)
     116              :     {
     117           17 :       char es[32];
     118           17 :       const_edge e = ev[i];
     119           17 :       sprintf (es, "%u -> %u", e->src->index, e->dest->index);
     120           17 :       str += es;
     121           17 :       if (i + 1 < n)
     122            6 :         str += ", ";
     123              :     }
     124           15 :   return str;
     125              : }
     126              : 
     127              : /* Format the first N elements of the array of vector of edges EVA as
     128              :    a string.  */
     129              : 
     130              : static std::string
     131            4 : format_edge_vecs (const vec<edge> eva[], unsigned n)
     132              : {
     133            4 :   std::string str;
     134              : 
     135            8 :   for (unsigned i = 0; i != n; ++i)
     136              :     {
     137            4 :       str += '{';
     138            8 :       str += format_edge_vec (eva[i]);
     139            4 :       str += '}';
     140            4 :       if (i + 1 < n)
     141            0 :         str += ", ";
     142              :     }
     143            4 :   return str;
     144              : }
     145              : 
     146              : /* Dump a single pred_info to F.  */
     147              : 
     148              : static void
     149           18 : dump_pred_info (FILE *f, const pred_info &pred)
     150              : {
     151           18 :   if (pred.invert)
     152            6 :     fprintf (f, "NOT (");
     153           18 :   print_generic_expr (f, pred.pred_lhs);
     154           18 :   fprintf (f, " %s ", op_symbol_code (pred.cond_code));
     155           18 :   print_generic_expr (f, pred.pred_rhs);
     156           18 :   if (pred.invert)
     157            6 :     fputc (')', f);
     158           18 : }
     159              : 
     160              : /* Dump a pred_chain to F.  */
     161              : 
     162              : static void
     163            8 : dump_pred_chain (FILE *f, const pred_chain &chain)
     164              : {
     165            8 :   unsigned np = chain.length ();
     166           20 :   for (unsigned j = 0; j < np; j++)
     167              :     {
     168           12 :       if (j > 0)
     169            4 :         fprintf (f, " AND (");
     170              :       else
     171            8 :         fputc ('(', f);
     172           12 :       dump_pred_info (f, chain[j]);
     173           12 :       fputc (')', f);
     174              :     }
     175            8 : }
     176              : 
     177              : /* Return the 'normalized' conditional code with operand swapping
     178              :    and condition inversion controlled by SWAP_COND and INVERT.  */
     179              : 
     180              : static tree_code
     181          965 : get_cmp_code (tree_code orig_cmp_code, bool swap_cond, bool invert)
     182              : {
     183          965 :   tree_code tc = orig_cmp_code;
     184              : 
     185          965 :   if (swap_cond)
     186           94 :     tc = swap_tree_comparison (orig_cmp_code);
     187          965 :   if (invert)
     188          346 :     tc = invert_tree_comparison (tc, false);
     189              : 
     190          965 :   switch (tc)
     191              :     {
     192          948 :     case LT_EXPR:
     193          948 :     case LE_EXPR:
     194          948 :     case GT_EXPR:
     195          948 :     case GE_EXPR:
     196          948 :     case EQ_EXPR:
     197          948 :     case NE_EXPR:
     198          948 :       break;
     199              :     default:
     200              :       return ERROR_MARK;
     201              :     }
     202          948 :   return tc;
     203              : }
     204              : 
     205              : /* Return true if PRED is common among all predicate chains in PREDS
     206              :    (and therefore can be factored out).  */
     207              : 
     208              : static bool
     209          162 : find_matching_predicate_in_rest_chains (const pred_info &pred,
     210              :                                         const pred_chain_union &preds)
     211              : {
     212              :   /* Trivial case.  */
     213          324 :   if (preds.length () == 1)
     214              :     return true;
     215              : 
     216            6 :   for (unsigned i = 1; i < preds.length (); i++)
     217              :     {
     218            3 :       bool found = false;
     219            3 :       const pred_chain &chain = preds[i];
     220            3 :       unsigned n = chain.length ();
     221            3 :       for (unsigned j = 0; j < n; j++)
     222              :         {
     223            3 :           const pred_info &pred2 = chain[j];
     224              :           /* Can relax the condition comparison to not use address
     225              :              comparison.  However, the most common case is that
     226              :              multiple control dependent paths share a common path
     227              :              prefix, so address comparison should be ok.  */
     228            3 :           if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
     229            3 :               && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
     230            6 :               && pred2.invert == pred.invert)
     231              :             {
     232              :               found = true;
     233              :               break;
     234              :             }
     235              :         }
     236            3 :       if (!found)
     237              :         return false;
     238              :     }
     239              :   return true;
     240              : }
     241              : 
     242              : /* Find a predicate to examine against paths of interest.  If there
     243              :    is no predicate of the "FLAG_VAR CMP CONST" form, try to find one
     244              :    of that's the form "FLAG_VAR CMP FLAG_VAR" with value range info.
     245              :    PHI is the phi node whose incoming (interesting) paths need to be
     246              :    examined.  On success, return the comparison code, set definition
     247              :    gimple of FLAG_DEF and BOUNDARY_CST.  Otherwise return ERROR_MARK.
     248              :    I is the running iterator so the function can be called repeatedly
     249              :    to gather all candidates.  */
     250              : 
     251              : static tree_code
     252          461 : find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def,
     253              :                     tree *boundary_cst, unsigned &i)
     254              : {
     255          461 :   gcc_assert (preds.length () > 0);
     256          461 :   pred_chain chain = preds[0];
     257         1170 :   for (; i < chain.length (); i++)
     258              :     {
     259          871 :       const pred_info &pred = chain[i];
     260          871 :       tree cond_lhs = pred.pred_lhs;
     261          871 :       tree cond_rhs = pred.pred_rhs;
     262          871 :       if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE)
     263          709 :         continue;
     264              : 
     265          871 :       tree_code code = get_cmp_code (pred.cond_code, false, pred.invert);
     266          871 :       if (code == ERROR_MARK)
     267           17 :         continue;
     268              : 
     269              :       /* Convert to the canonical form SSA_NAME CMP CONSTANT.  */
     270          854 :       if (TREE_CODE (cond_lhs) == SSA_NAME
     271          854 :           && is_gimple_constant (cond_rhs))
     272              :         ;
     273          101 :       else if (TREE_CODE (cond_rhs) == SSA_NAME
     274          101 :                && is_gimple_constant (cond_lhs))
     275              :         {
     276            0 :           std::swap (cond_lhs, cond_rhs);
     277            0 :           if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
     278            0 :             continue;
     279              :         }
     280              :       /* Check if we can take advantage of FLAG_VAR COMP FLAG_VAR predicate
     281              :          with value range info.  Note only first of such case is handled.  */
     282          101 :       else if (TREE_CODE (cond_lhs) == SSA_NAME
     283          101 :                && TREE_CODE (cond_rhs) == SSA_NAME)
     284              :         {
     285           98 :           gimple* lhs_def = SSA_NAME_DEF_STMT (cond_lhs);
     286           98 :           if (!lhs_def || gimple_code (lhs_def) != GIMPLE_PHI
     287          102 :               || gimple_bb (lhs_def) != gimple_bb (phi))
     288              :             {
     289           94 :               std::swap (cond_lhs, cond_rhs);
     290           94 :               if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
     291           86 :                 continue;
     292              :             }
     293              : 
     294              :           /* Check value range info of rhs, do following transforms:
     295              :                flag_var < [min, max]  ->  flag_var < max
     296              :                flag_var > [min, max]  ->  flag_var > min
     297              : 
     298              :              We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
     299              :                flag_var <= [min, max] ->  flag_var < [min, max+1]
     300              :                flag_var >= [min, max] ->  flag_var > [min-1, max]
     301              :              if no overflow/wrap.  */
     302           98 :           tree type = TREE_TYPE (cond_lhs);
     303           98 :           int_range_max r;
     304          180 :           if (!INTEGRAL_TYPE_P (type)
     305          188 :               || !get_range_query (cfun)->range_of_expr (r, cond_rhs)
     306           94 :               || r.undefined_p ()
     307          192 :               || r.varying_p ())
     308           82 :             continue;
     309              : 
     310           16 :           wide_int min = r.lower_bound ();
     311           16 :           wide_int max = r.upper_bound ();
     312           32 :           if (code == LE_EXPR
     313           16 :               && max != wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
     314              :             {
     315            0 :               code = LT_EXPR;
     316            0 :               max = max + 1;
     317              :             }
     318            0 :           if (code == GE_EXPR
     319           17 :               && min != wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
     320              :             {
     321            0 :               code = GT_EXPR;
     322            0 :               min = min - 1;
     323              :             }
     324           16 :           if (code == LT_EXPR)
     325           12 :             cond_rhs = wide_int_to_tree (type, max);
     326            4 :           else if (code == GT_EXPR)
     327            0 :             cond_rhs = wide_int_to_tree (type, min);
     328              :           else
     329            4 :             continue;
     330           98 :         }
     331              :       else
     332            3 :         continue;
     333              : 
     334          765 :       if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL)
     335            0 :         continue;
     336              : 
     337          765 :       if (gimple_code (*flag_def) != GIMPLE_PHI
     338          163 :           || gimple_bb (*flag_def) != gimple_bb (phi)
     339          927 :           || !find_matching_predicate_in_rest_chains (pred, preds))
     340          603 :         continue;
     341              : 
     342              :       /* Return predicate found.  */
     343          162 :       *boundary_cst = cond_rhs;
     344          162 :       ++i;
     345          162 :       return code;
     346              :     }
     347              : 
     348              :   return ERROR_MARK;
     349              : }
     350              : 
     351              : /* Return true if all interesting opnds are pruned, false otherwise.
     352              :    PHI is the phi node with interesting operands, OPNDS is the bitmap
     353              :    of the interesting operand positions, FLAG_DEF is the statement
     354              :    defining the flag guarding the use of the PHI output, BOUNDARY_CST
     355              :    is the const value used in the predicate associated with the flag,
     356              :    CMP_CODE is the comparison code used in the predicate, VISITED_PHIS
     357              :    is the pointer set of phis visited, and VISITED_FLAG_PHIS is
     358              :    the pointer to the pointer set of flag definitions that are also
     359              :    phis.
     360              : 
     361              :    Example scenario:
     362              : 
     363              :    BB1:
     364              :      flag_1 = phi <0, 1>                  // (1)
     365              :      var_1  = phi <undef, some_val>
     366              : 
     367              : 
     368              :    BB2:
     369              :      flag_2 = phi <0,   flag_1, flag_1>           // (2)
     370              :      var_2  = phi <undef, var_1, var_1>
     371              :      if (flag_2 == 1)
     372              :        goto BB3;
     373              : 
     374              :    BB3:
     375              :      use of var_2                               // (3)
     376              : 
     377              :    Because some flag arg in (1) is not constant, if we do not look into
     378              :    the flag phis recursively, it is conservatively treated as unknown and
     379              :    var_1 is thought to flow into use at (3).  Since var_1 is potentially
     380              :    uninitialized a false warning will be emitted.
     381              :    Checking recursively into (1), the compiler can find out that only
     382              :    some_val (which is defined) can flow into (3) which is OK.  */
     383              : 
     384              : bool
     385          392 : uninit_analysis::prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
     386              :                                   tree boundary_cst, tree_code cmp_code,
     387              :                                   hash_set<gphi *> *visited_phis,
     388              :                                   bitmap *visited_flag_phis,
     389              :                                   unsigned &max_attempts)
     390              : {
     391              :   /* The Boolean predicate guarding the PHI definition.  Initialized
     392              :      lazily from PHI in the first call to is_use_guarded() and cached
     393              :      for subsequent iterations.  */
     394          392 :   uninit_analysis def_preds (m_eval);
     395              : 
     396          392 :   unsigned n = MIN (m_eval.max_phi_args, gimple_phi_num_args (flag_def));
     397         1524 :   for (unsigned i = 0; i < n; i++)
     398              :     {
     399         1182 :       if (!MASK_TEST_BIT (opnds, i))
     400          292 :         continue;
     401              : 
     402          890 :       if (max_attempts == 0)
     403              :         return false;
     404          890 :       --max_attempts;
     405              : 
     406          890 :       tree flag_arg = gimple_phi_arg_def (flag_def, i);
     407          890 :       if (!is_gimple_constant (flag_arg))
     408              :         {
     409          265 :           if (TREE_CODE (flag_arg) != SSA_NAME)
     410              :             return false;
     411              : 
     412          265 :           gphi *flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
     413          230 :           if (!flag_arg_def)
     414              :             return false;
     415              : 
     416          230 :           tree phi_arg = gimple_phi_arg_def (phi, i);
     417          230 :           if (TREE_CODE (phi_arg) != SSA_NAME)
     418              :             return false;
     419              : 
     420          230 :           gphi *phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
     421          230 :           if (!phi_arg_def)
     422              :             return false;
     423              : 
     424          230 :           if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
     425              :             return false;
     426              : 
     427          230 :           if (!*visited_flag_phis)
     428           36 :             *visited_flag_phis = BITMAP_ALLOC (NULL);
     429              : 
     430          230 :           tree phi_result = gimple_phi_result (flag_arg_def);
     431          230 :           if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
     432              :             return false;
     433              : 
     434          230 :           bitmap_set_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
     435              : 
     436              :           /* Now recursively try to prune the interesting phi args.  */
     437          230 :           unsigned opnds_arg_phi = m_eval.phi_arg_set (phi_arg_def);
     438          230 :           if (!prune_phi_opnds (phi_arg_def, opnds_arg_phi, flag_arg_def,
     439              :                                 boundary_cst, cmp_code, visited_phis,
     440              :                                 visited_flag_phis, max_attempts))
     441              :             return false;
     442              : 
     443          229 :           bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
     444          229 :           continue;
     445          229 :         }
     446              : 
     447              :       /* Now check if the constant is in the guarded range.  */
     448          625 :       if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
     449              :         {
     450              :           /* Now that we know that this undefined edge is not pruned.
     451              :              If the operand is defined by another phi, we can further
     452              :              prune the incoming edges of that phi by checking
     453              :              the predicates of this operands.  */
     454              : 
     455           54 :           tree opnd = gimple_phi_arg_def (phi, i);
     456           54 :           gimple *opnd_def = SSA_NAME_DEF_STMT (opnd);
     457          432 :           if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
     458              :             {
     459           40 :               unsigned opnds2 = m_eval.phi_arg_set (opnd_def_phi);
     460           40 :               if (!MASK_EMPTY (opnds2))
     461              :                 {
     462           40 :                   edge opnd_edge = gimple_phi_arg_edge (phi, i);
     463           40 :                   if (def_preds.is_use_guarded (phi, opnd_edge->src,
     464              :                                                 opnd_def_phi, opnds2,
     465              :                                                 visited_phis))
     466              :                     return false;
     467              :                 }
     468              :             }
     469              :           else
     470              :             return false;
     471              :         }
     472              :     }
     473              : 
     474              :   return true;
     475          392 : }
     476              : 
     477              : /* Recursively compute the set PHI's incoming edges with "uninteresting"
     478              :    operands of a phi chain, i.e., those for which EVAL returns false.
     479              :    CD_ROOT is the control dependence root from which edges are collected
     480              :    up the CFG nodes that it's dominated by.  *EDGES holds the result, and
     481              :    VISITED is used for detecting cycles.  */
     482              : 
     483              : void
     484          290 : uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root,
     485              :                                         vec<edge> *edges,
     486              :                                         hash_set<gimple *> *visited)
     487              : {
     488          290 :   if (visited->elements () == 0
     489              :       && DEBUG_PREDICATE_ANALYZER
     490          290 :       && dump_file)
     491              :     {
     492            2 :       fprintf (dump_file, "%s for cd_root %u and ",
     493              :                __func__, cd_root->index);
     494            2 :       print_gimple_stmt (dump_file, phi, 0);
     495              : 
     496              :     }
     497              : 
     498          290 :   if (visited->add (phi))
     499              :     return;
     500              : 
     501          253 :   unsigned n = gimple_phi_num_args (phi);
     502          253 :   unsigned opnds_arg_phi = m_eval.phi_arg_set (phi);
     503         1144 :   for (unsigned i = 0; i < n; i++)
     504              :     {
     505          638 :       if (!MASK_TEST_BIT (opnds_arg_phi, i))
     506              :         {
     507              :           /* Add the edge for a not maybe-undefined edge value.  */
     508          258 :           edge opnd_edge = gimple_phi_arg_edge (phi, i);
     509          258 :           if (dump_file && (dump_flags & TDF_DETAILS))
     510              :             {
     511            0 :               fprintf (dump_file,
     512              :                        "\tFound def edge %i -> %i for cd_root %i "
     513              :                        "and operand %u of: ",
     514            0 :                        opnd_edge->src->index, opnd_edge->dest->index,
     515              :                        cd_root->index, i);
     516            0 :               print_gimple_stmt (dump_file, phi, 0);
     517              :             }
     518          258 :           edges->safe_push (opnd_edge);
     519          258 :           continue;
     520          258 :         }
     521              :       else
     522              :         {
     523          380 :           tree opnd = gimple_phi_arg_def (phi, i);
     524          380 :           if (TREE_CODE (opnd) == SSA_NAME)
     525              :             {
     526          380 :               gimple *def = SSA_NAME_DEF_STMT (opnd);
     527          380 :               if (gimple_code (def) == GIMPLE_PHI
     528          380 :                   && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
     529              :                 /* Process PHI defs of maybe-undefined edge values
     530              :                    recursively.  */
     531          100 :                 collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
     532              :                                        visited);
     533              :             }
     534              :         }
     535              :     }
     536              : }
     537              : 
     538              : /* Return a bitset of all PHI arguments or zero if there are too many.  */
     539              : 
     540              : unsigned
     541            0 : uninit_analysis::func_t::phi_arg_set (gphi *phi)
     542              : {
     543            0 :   unsigned n = gimple_phi_num_args (phi);
     544              : 
     545            0 :   if (max_phi_args < n)
     546              :     return 0;
     547              : 
     548              :   /* Set the least significant N bits.  */
     549            0 :   return (1U << n) - 1;
     550              : }
     551              : 
     552              : /* Determine if the predicate set of the use does not overlap with that
     553              :    of the interesting paths.  The most common scenario of guarded use is
     554              :    in Example 1:
     555              :      Example 1:
     556              :            if (some_cond)
     557              :            {
     558              :               x = ...;   // set x to valid
     559              :               flag = true;
     560              :            }
     561              : 
     562              :             ... some code ...
     563              : 
     564              :            if (flag)
     565              :               use (x);   // use when x is valid
     566              : 
     567              :      The real world examples are usually more complicated, but similar
     568              :      and usually result from inlining:
     569              : 
     570              :          bool init_func (int * x)
     571              :          {
     572              :              if (some_cond)
     573              :                 return false;
     574              :              *x  =  ...;   // set *x to valid
     575              :              return true;
     576              :          }
     577              : 
     578              :          void foo (..)
     579              :          {
     580              :              int x;
     581              : 
     582              :              if (!init_func (&x))
     583              :                 return;
     584              : 
     585              :              .. some_code ...
     586              :              use (x);      // use when x is valid
     587              :          }
     588              : 
     589              :      Another possible use scenario is in the following trivial example:
     590              : 
     591              :      Example 2:
     592              :           if (n > 0)
     593              :              x = 1;
     594              :           ...
     595              :           if (n > 0)
     596              :             {
     597              :               if (m < 2)
     598              :                  ... = x;
     599              :             }
     600              : 
     601              :      Predicate analysis needs to compute the composite predicate:
     602              : 
     603              :        1) 'x' use predicate: (n > 0) .AND. (m < 2)
     604              :        2) 'x' default value  (non-def) predicate: .NOT. (n > 0)
     605              :        (the predicate chain for phi operand defs can be computed
     606              :        starting from a bb that is control equivalent to the phi's
     607              :        bb and is dominating the operand def.)
     608              : 
     609              :        and check overlapping:
     610              :           (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
     611              :         <==> false
     612              : 
     613              :      This implementation provides a framework that can handle different
     614              :      scenarios.  (Note that many simple cases are handled properly without
     615              :      the predicate analysis if jump threading eliminates the merge point
     616              :      thus makes path-sensitive analysis unnecessary.)
     617              : 
     618              :      PHI is the phi node whose incoming (undefined) paths need to be
     619              :      pruned, and OPNDS is the bitmap holding interesting operand
     620              :      positions.  VISITED is the pointer set of phi stmts being
     621              :      checked.  */
     622              : 
     623              : bool
     624          412 : uninit_analysis::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited,
     625              :                           const predicate &use_preds)
     626              : {
     627          412 :   gimple *flag_def = NULL;
     628          412 :   tree boundary_cst = NULL_TREE;
     629              : 
     630              :   /* Find within the common prefix of multiple predicate chains
     631              :      a predicate that is a comparison of a flag variable against
     632              :      a constant.  */
     633          412 :   unsigned i = 0;
     634          412 :   tree_code cmp_code;
     635          461 :   while ((cmp_code = find_var_cmp_const (use_preds.chain (), phi, &flag_def,
     636          461 :                                          &boundary_cst, i)) != ERROR_MARK)
     637              :     {
     638              :       /* Now check all the uninit incoming edges have a constant flag
     639              :          value that is in conflict with the use guard/predicate.  */
     640          162 :       bitmap visited_flag_phis = NULL;
     641          162 :       gphi *phi_def = as_a<gphi *> (flag_def);
     642          162 :       unsigned max_attempts = param_uninit_max_prune_work;
     643          162 :       bool all_pruned = prune_phi_opnds (phi, opnds, phi_def, boundary_cst,
     644              :                                          cmp_code, visited,
     645              :                                          &visited_flag_phis, max_attempts);
     646          162 :       if (visited_flag_phis)
     647           36 :         BITMAP_FREE (visited_flag_phis);
     648          162 :       if (all_pruned)
     649          113 :         return false;
     650              :     }
     651              : 
     652              :   return true;
     653              : }
     654              : 
     655              : /* Return true if two predicates PRED1 and X2 are equivalent.  Assume
     656              :    the expressions have already properly re-associated.  */
     657              : 
     658              : static inline bool
     659         3174 : pred_equal_p (const pred_info &pred1, const pred_info &pred2)
     660              : {
     661         3174 :   if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0)
     662         3174 :       || !operand_equal_p (pred1.pred_rhs, pred2.pred_rhs, 0))
     663              :     return false;
     664              : 
     665          630 :   tree_code c1 = pred1.cond_code, c2;
     666          630 :   if (pred1.invert != pred2.invert
     667          222 :       && TREE_CODE_CLASS (pred2.cond_code) == tcc_comparison)
     668          221 :     c2 = invert_tree_comparison (pred2.cond_code, false);
     669              :   else
     670          409 :     c2 = pred2.cond_code;
     671              : 
     672          630 :   return c1 == c2;
     673              : }
     674              : 
     675              : /* Return true if PRED tests inequality (i.e., X != Y).  */
     676              : 
     677              : static inline bool
     678         5933 : is_neq_relop_p (const pred_info &pred)
     679              : {
     680              : 
     681         2355 :   return ((pred.cond_code == NE_EXPR && !pred.invert)
     682         4164 :           || (pred.cond_code == EQ_EXPR && pred.invert));
     683              : }
     684              : 
     685              : /* Returns true if PRED is of the form X != 0.  */
     686              : 
     687              : static inline bool
     688         5933 : is_neq_zero_form_p (const pred_info &pred)
     689              : {
     690         9245 :   if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
     691         5832 :       || TREE_CODE (pred.pred_lhs) != SSA_NAME)
     692         3275 :     return false;
     693              :   return true;
     694              : }
     695              : 
     696              : /* Return true if PRED is equivalent to X != 0.  */
     697              : 
     698              : static inline bool
     699           18 : pred_expr_equal_p (const pred_info &pred, tree expr)
     700              : {
     701           18 :   if (!is_neq_zero_form_p (pred))
     702              :     return false;
     703              : 
     704           18 :   return operand_equal_p (pred.pred_lhs, expr, 0);
     705              : }
     706              : 
     707              : /* Return true if VAL satisfies (x CMPC BOUNDARY) predicate.  CMPC can
     708              :    be either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and
     709              :    the like), or BIT_AND_EXPR.  EXACT_P is only meaningful for the latter.
     710              :    Modify the question from VAL & BOUNDARY != 0 to VAL & BOUNDARY == VAL.
     711              :    For other values of CMPC, EXACT_P is ignored.  */
     712              : 
     713              : static bool
     714           63 : value_sat_pred_p (tree val, tree boundary, tree_code cmpc,
     715              :                   bool exact_p = false)
     716              : {
     717           63 :   if (cmpc != BIT_AND_EXPR)
     718           56 :     return is_value_included_in (val, boundary, cmpc);
     719              : 
     720            7 :   widest_int andw = wi::to_widest (val) & wi::to_widest (boundary);
     721            7 :   if (exact_p)
     722            3 :     return andw == wi::to_widest (val);
     723              : 
     724            4 :   return wi::ne_p (andw, 0);
     725           63 : }
     726              : 
     727              : /* Return true if the domain of single predicate expression PRED1
     728              :    is a subset of that of PRED2, and false if it cannot be proved.  */
     729              : 
     730              : static bool
     731         2584 : subset_of (const pred_info &pred1, const pred_info &pred2)
     732              : {
     733         2584 :   if (pred_equal_p (pred1, pred2))
     734              :     return true;
     735              : 
     736         2529 :   if ((TREE_CODE (pred1.pred_rhs) != INTEGER_CST)
     737         2368 :       || (TREE_CODE (pred2.pred_rhs) != INTEGER_CST))
     738              :     return false;
     739              : 
     740         1988 :   if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0))
     741              :     return false;
     742              : 
     743          161 :   tree_code code1 = pred1.cond_code;
     744          161 :   if (pred1.invert)
     745          124 :     code1 = invert_tree_comparison (code1, false);
     746          161 :   tree_code code2 = pred2.cond_code;
     747          161 :   if (pred2.invert)
     748            6 :     code2 = invert_tree_comparison (code2, false);
     749              : 
     750          161 :   if (code2 == NE_EXPR && code1 == NE_EXPR)
     751              :     return false;
     752              : 
     753          158 :   if (code2 == NE_EXPR)
     754           48 :     return !value_sat_pred_p (pred2.pred_rhs, pred1.pred_rhs, code1);
     755              : 
     756          110 :   if (code1 == EQ_EXPR)
     757            2 :     return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2);
     758              : 
     759          108 :   if (code1 == code2)
     760           13 :     return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2,
     761           13 :                              code1 == BIT_AND_EXPR);
     762              : 
     763              :   return false;
     764              : }
     765              : 
     766              : /* Return true if the domain of CHAIN1 is a subset of that of CHAIN2.
     767              :    Return false if it cannot be proven so.  */
     768              : 
     769              : static bool
     770          466 : subset_of (const pred_chain &chain1, const pred_chain &chain2)
     771              : {
     772          466 :   unsigned np1 = chain1.length ();
     773          466 :   unsigned np2 = chain2.length ();
     774          531 :   for (unsigned i2 = 0; i2 < np2; i2++)
     775              :     {
     776          482 :       bool found = false;
     777          482 :       const pred_info &info2 = chain2[i2];
     778         1823 :       for (unsigned i1 = 0; i1 < np1; i1++)
     779              :         {
     780          924 :           const pred_info &info1 = chain1[i1];
     781          924 :           if (subset_of (info1, info2))
     782              :             {
     783              :               found = true;
     784              :               break;
     785              :             }
     786              :         }
     787          482 :       if (!found)
     788              :         return false;
     789              :     }
     790              :   return true;
     791              : }
     792              : 
     793              : /* Return true if the domain defined by the predicate chain PREDS is
     794              :    a subset of the domain of *THIS.  Return false if PREDS's domain
     795              :    is not a subset of any of the sub-domains of *THIS (corresponding
     796              :    to each individual chains in it), even though it may be still be
     797              :    a subset of whole domain of *THIS which is the union (ORed) of all
     798              :    its subdomains.  In other words, the result is conservative.  */
     799              : 
     800              : bool
     801          234 : predicate::includes (const pred_chain &chain) const
     802              : {
     803          651 :   for (unsigned i = 0; i < m_preds.length (); i++)
     804          466 :     if (subset_of (chain, m_preds[i]))
     805              :       return true;
     806              : 
     807              :   return false;
     808              : }
     809              : 
     810              : /* Return true if the domain defined by *THIS is a superset of PREDS's
     811              :    domain.
     812              :    Avoid building generic trees (and rely on the folding capability
     813              :    of the compiler), and instead perform brute force comparison of
     814              :    individual predicate chains (this won't be a computationally costly
     815              :    since the chains are pretty short).  Returning false does not
     816              :    necessarily mean *THIS is not a superset of *PREDS, only that
     817              :    it need not be since the analysis cannot prove it.  */
     818              : 
     819              : bool
     820          229 : predicate::superset_of (const predicate &preds) const
     821              : {
     822          278 :   for (unsigned i = 0; i < preds.m_preds.length (); i++)
     823          234 :     if (!includes (preds.m_preds[i]))
     824              :       return false;
     825              : 
     826              :   return true;
     827              : }
     828              : 
     829              : /* Remove from every chain in *THIS any (comparison) conjunct whose domain is
     830              :    a superset of every predicate in EDGE_CONDS, i.e. a conjunct implied by all
     831              :    of them.  Returns true if any conjunct was removed.  */
     832              : 
     833              : bool
     834          152 : predicate::drop_conjuncts_implied_by (const vec<pred_info> &edge_conds)
     835              : {
     836          152 :   if (edge_conds.is_empty ())
     837              :     return false;
     838              : 
     839              :   bool changed = false;
     840          462 :   for (unsigned i = 0; i < m_preds.length (); i++)
     841              :     {
     842          310 :       pred_chain &chain = m_preds[i];
     843         2284 :       for (unsigned j = 0; j < chain.length (); )
     844              :         {
     845              :           /* Only reason about comparison conjuncts: subset_of negates the
     846              :              code for inverted predicates, which is invalid for e.g. the
     847              :              BIT_AND_EXPR of an "x & mask" predicate.  */
     848         1664 :           bool implied = TREE_CODE_CLASS (chain[j].cond_code) == tcc_comparison;
     849         4988 :           for (unsigned k = 0; implied && k < edge_conds.length (); k++)
     850         1660 :             if (!subset_of (edge_conds[k], chain[j]))
     851              :               implied = false;
     852              : 
     853         1664 :           if (implied)
     854              :             {
     855            4 :               chain.ordered_remove (j);
     856            4 :               changed = true;
     857              :             }
     858              :           else
     859         1660 :             j++;
     860              :         }
     861              :     }
     862              :   return changed;
     863              : }
     864              : 
     865              : /* Create a predicate of the form OP != 0 and push it the work list CHAIN.  */
     866              : 
     867              : static void
     868           60 : push_to_worklist (tree op, pred_chain *chain, hash_set<tree> *mark_set)
     869              : {
     870           60 :   if (mark_set->contains (op))
     871              :     return;
     872           58 :   mark_set->add (op);
     873              : 
     874           58 :   pred_info arg_pred;
     875           58 :   arg_pred.pred_lhs = op;
     876           58 :   arg_pred.pred_rhs = integer_zero_node;
     877           58 :   arg_pred.cond_code = NE_EXPR;
     878           58 :   arg_pred.invert = false;
     879           58 :   chain->safe_push (arg_pred);
     880              : }
     881              : 
     882              : /* Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
     883              :    rhs.  */
     884              : 
     885              : static pred_info
     886           40 : get_pred_info_from_cmp (const gimple *cmp_assign)
     887              : {
     888           40 :   pred_info pred;
     889           40 :   pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
     890           40 :   pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
     891           40 :   pred.cond_code = gimple_assign_rhs_code (cmp_assign);
     892           40 :   pred.invert = false;
     893           40 :   return pred;
     894              : }
     895              : 
     896              : /* Return a pred_info for the GIMPLE_COND ending E's source block.  The true
     897              :    edge corresponds to the condition holding, so a false edge yields the
     898              :    inverted predicate.  */
     899              : 
     900              : static pred_info
     901         3426 : get_pred_info_from_cond_edge (edge e)
     902              : {
     903         6852 :   gcond *cond = as_a<gcond *> (*gsi_last_bb (e->src));
     904         3426 :   pred_info pred;
     905         3426 :   pred.pred_lhs = gimple_cond_lhs (cond);
     906         3426 :   pred.pred_rhs = gimple_cond_rhs (cond);
     907         3426 :   pred.cond_code = gimple_cond_code (cond);
     908         3426 :   pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
     909         3426 :   return pred;
     910              : }
     911              : 
     912              : /* If PHI is a degenerate phi with all operands having the same value (relop)
     913              :    update *PRED to that value and return true.  Otherwise return false.  */
     914              : 
     915              : static bool
     916           70 : is_degenerate_phi (gimple *phi, pred_info *pred)
     917              : {
     918           70 :   tree op0 = gimple_phi_arg_def (phi, 0);
     919              : 
     920           70 :   if (TREE_CODE (op0) != SSA_NAME)
     921              :     return false;
     922              : 
     923           34 :   gimple *def0 = SSA_NAME_DEF_STMT (op0);
     924           34 :   if (gimple_code (def0) != GIMPLE_ASSIGN)
     925              :     return false;
     926              : 
     927            1 :   if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
     928              :     return false;
     929              : 
     930            1 :   pred_info pred0 = get_pred_info_from_cmp (def0);
     931              : 
     932            1 :   unsigned n = gimple_phi_num_args (phi);
     933            1 :   for (unsigned i = 1; i < n; ++i)
     934              :     {
     935            1 :       tree op = gimple_phi_arg_def (phi, i);
     936            1 :       if (TREE_CODE (op) != SSA_NAME)
     937            1 :         return false;
     938              : 
     939            0 :       gimple *def = SSA_NAME_DEF_STMT (op);
     940            0 :       if (gimple_code (def) != GIMPLE_ASSIGN)
     941              :         return false;
     942              : 
     943            0 :       if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
     944              :         return false;
     945              : 
     946            0 :       pred_info pred = get_pred_info_from_cmp (def);
     947            0 :       if (!pred_equal_p (pred, pred0))
     948              :         return false;
     949              :     }
     950              : 
     951            0 :   *pred = pred0;
     952            0 :   return true;
     953              : }
     954              : 
     955              : /* If compute_control_dep_chain bailed out due to limits this routine
     956              :    tries to build a partial sparse path using dominators.  Returns
     957              :    path edges whose predicates are always true when reaching E.  */
     958              : 
     959              : static void
     960            0 : simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
     961              : {
     962            0 :   if (!dominated_by_p (CDI_DOMINATORS, to, from))
     963              :     return;
     964              : 
     965              :   basic_block src = to;
     966              :   while (src != from
     967            0 :          && chain.length () <= MAX_CHAIN_LEN)
     968              :     {
     969            0 :       basic_block dest = src;
     970            0 :       src = get_immediate_dominator (CDI_DOMINATORS, src);
     971            0 :       if (single_pred_p (dest))
     972              :         {
     973            0 :           edge pred_e = single_pred_edge (dest);
     974            0 :           gcc_assert (pred_e->src == src);
     975            0 :           if (!(pred_e->flags & ((EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK)))
     976            0 :               && !single_succ_p (src))
     977            0 :             chain.safe_push (pred_e);
     978              :         }
     979              :     }
     980              : }
     981              : 
     982              : /* Perform a DFS walk on predecessor edges to mark the region denoted
     983              :    by the EXIT_SRC block and DOM which dominates EXIT_SRC, including DOM.
     984              :    Blocks in the region are marked with FLAG and added to BBS.  BBS is
     985              :    filled up to its capacity only after which the walk is terminated
     986              :    and false is returned.  If the whole region was marked, true is returned.  */
     987              : 
     988              : static bool
     989          830 : dfs_mark_dominating_region (basic_block exit_src, basic_block dom, int flag,
     990              :                             vec<basic_block> &bbs)
     991              : {
     992          830 :   if (exit_src == dom || exit_src->flags & flag)
     993              :     return true;
     994          678 :   if (!bbs.space (1))
     995              :     return false;
     996          678 :   bbs.quick_push (exit_src);
     997          678 :   exit_src->flags |= flag;
     998          678 :   auto_vec<edge_iterator, 20> stack (bbs.allocated () - bbs.length () + 1);
     999          678 :   stack.quick_push (ei_start (exit_src->preds));
    1000        12884 :   while (!stack.is_empty ())
    1001              :     {
    1002              :       /* Look at the edge on the top of the stack.  */
    1003        12206 :       edge_iterator ei = stack.last ();
    1004        12206 :       basic_block src = ei_edge (ei)->src;
    1005              : 
    1006              :       /* Check if the edge source has been visited yet.  */
    1007        12206 :       if (!(src->flags & flag))
    1008              :         {
    1009              :           /* Mark the source if there's still space.  If not, return early.  */
    1010         5290 :           if (!bbs.space (1))
    1011            0 :             return false;
    1012         5290 :           src->flags |= flag;
    1013         5290 :           bbs.quick_push (src);
    1014              : 
    1015              :           /* Queue its predecessors if we didn't reach DOM.  */
    1016        16971 :           if (src != dom && EDGE_COUNT (src->preds) > 0)
    1017         4765 :             stack.quick_push (ei_start (src->preds));
    1018              :         }
    1019              :       else
    1020              :         {
    1021         6916 :           if (!ei_one_before_end_p (ei))
    1022         1473 :             ei_next (&stack.last ());
    1023              :           else
    1024         5443 :             stack.pop ();
    1025              :         }
    1026              :     }
    1027              :   return true;
    1028          678 : }
    1029              : 
    1030              : static bool
    1031              : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
    1032              :                            vec<edge> cd_chains[], unsigned *num_chains,
    1033              :                            vec<edge> &cur_cd_chain, unsigned *num_calls,
    1034              :                            unsigned in_region, unsigned depth,
    1035              :                            bool *complete_p);
    1036              : 
    1037              : /* Helper for compute_control_dep_chain that walks the post-dominator
    1038              :    chain from CD_BB up unto TARGET_BB looking for paths to DEP_BB.  */
    1039              : 
    1040              : static bool
    1041        10210 : compute_control_dep_chain_pdom (basic_block cd_bb, const_basic_block dep_bb,
    1042              :                                 basic_block target_bb,
    1043              :                                 vec<edge> cd_chains[], unsigned *num_chains,
    1044              :                                 vec<edge> &cur_cd_chain, unsigned *num_calls,
    1045              :                                 unsigned in_region, unsigned depth,
    1046              :                                 bool *complete_p)
    1047              : {
    1048        10210 :   bool found_cd_chain = false;
    1049        16872 :   while (cd_bb != target_bb)
    1050              :     {
    1051        13204 :       if (cd_bb == dep_bb)
    1052              :         {
    1053              :           /* Found a direct control dependence.  */
    1054         1117 :           if (*num_chains < MAX_NUM_CHAINS)
    1055              :             {
    1056          965 :               if (DEBUG_PREDICATE_ANALYZER && dump_file)
    1057            4 :                 fprintf (dump_file, "%*s pushing { %s }\n",
    1058            8 :                          depth, "", format_edge_vec (cur_cd_chain).c_str ());
    1059          965 :               cd_chains[*num_chains] = cur_cd_chain.copy ();
    1060          965 :               (*num_chains)++;
    1061              :             }
    1062              :           found_cd_chain = true;
    1063              :           /* Check path from next edge.  */
    1064              :           break;
    1065              :         }
    1066              : 
    1067              :       /* If the dominating region has been marked avoid walking outside.  */
    1068        12087 :       if (in_region != 0 && !(cd_bb->flags & in_region))
    1069              :         break;
    1070              : 
    1071              :       /* Count the number of steps we perform to limit compile-time.
    1072              :          This should cover both recursion and the post-dominator walk.  */
    1073         9749 :       if (*num_calls > (unsigned)param_uninit_control_dep_attempts)
    1074              :         {
    1075            0 :           if (dump_file)
    1076            0 :             fprintf (dump_file, "param_uninit_control_dep_attempts "
    1077              :                      "exceeded: %u\n", *num_calls);
    1078            0 :           *complete_p = false;
    1079            0 :           break;
    1080              :         }
    1081         9749 :       ++*num_calls;
    1082              : 
    1083              :       /* Check if DEP_BB is indirectly control-dependent on DOM_BB.  */
    1084         9749 :       if (!single_succ_p (cd_bb)
    1085         9749 :           && compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
    1086              :                                         num_chains, cur_cd_chain,
    1087              :                                         num_calls, in_region, depth + 1,
    1088              :                                         complete_p))
    1089              :         {
    1090              :           found_cd_chain = true;
    1091              :           break;
    1092              :         }
    1093              : 
    1094              :       /* The post-dominator walk will reach a backedge only
    1095              :          from a forwarder, otherwise it should choose to exit
    1096              :          the SCC.  */
    1097         7201 :       if (single_succ_p (cd_bb)
    1098         7201 :           && single_succ_edge (cd_bb)->flags & EDGE_DFS_BACK)
    1099              :         break;
    1100         6747 :       basic_block prev_cd_bb = cd_bb;
    1101         6747 :       cd_bb = get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb);
    1102         6747 :       if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1103              :         break;
    1104              :       /* Pick up conditions toward the post dominator such like
    1105              :          loop exit conditions.  See gcc.dg/uninit-pred-11.c and
    1106              :          gcc.dg/unninit-pred-12.c and PR106754.  */
    1107        13324 :       if (single_pred_p (cd_bb))
    1108              :         {
    1109           75 :           edge e2 = single_pred_edge (cd_bb);
    1110           75 :           gcc_assert (e2->src == prev_cd_bb);
    1111              :           /* But avoid adding fallthru or abnormal edges.  */
    1112           75 :           if (!(e2->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
    1113          150 :               && !single_succ_p (prev_cd_bb))
    1114           74 :             cur_cd_chain.safe_push (e2);
    1115              :         }
    1116              :     }
    1117        10210 :   return found_cd_chain;
    1118              : }
    1119              : 
    1120              : 
    1121              : /* Recursively compute the control dependence chains (paths of edges)
    1122              :    from the dependent basic block, DEP_BB, up to the dominating basic
    1123              :    block, DOM_BB (the head node of a chain should be dominated by it),
    1124              :    storing them in the CD_CHAINS array.
    1125              :    CUR_CD_CHAIN is the current chain being computed.
    1126              :    *NUM_CHAINS is total number of chains in the CD_CHAINS array.
    1127              :    *NUM_CALLS is the number of recursive calls to control unbounded
    1128              :    recursion.
    1129              :    Return true if the information is successfully computed, false if
    1130              :    there is no control dependence or not computed.
    1131              :    *COMPLETE_P is set to false if we stopped walking due to limits.
    1132              :    In this case there might be missing chains.  */
    1133              : 
    1134              : static bool
    1135         4794 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
    1136              :                            vec<edge> cd_chains[], unsigned *num_chains,
    1137              :                            vec<edge> &cur_cd_chain, unsigned *num_calls,
    1138              :                            unsigned in_region, unsigned depth,
    1139              :                            bool *complete_p)
    1140              : {
    1141              :   /* In our recursive calls this doesn't happen.  */
    1142         4794 :   if (single_succ_p (dom_bb))
    1143              :     return false;
    1144              : 
    1145              :   /* FIXME: Use a set instead.  */
    1146         4794 :   unsigned cur_chain_len = cur_cd_chain.length ();
    1147         4794 :   if (cur_chain_len > MAX_CHAIN_LEN)
    1148              :     {
    1149          219 :       if (dump_file)
    1150            0 :         fprintf (dump_file, "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len);
    1151              : 
    1152          219 :       *complete_p = false;
    1153          219 :       return false;
    1154              :     }
    1155              : 
    1156         4575 :   if (cur_chain_len > 5)
    1157              :     {
    1158         2412 :       if (dump_file)
    1159            0 :         fprintf (dump_file, "chain length exceeds 5: %u\n", cur_chain_len);
    1160              :     }
    1161              : 
    1162         4575 :   if (DEBUG_PREDICATE_ANALYZER && dump_file)
    1163            7 :     fprintf (dump_file,
    1164              :              "%*s%s (dom_bb = %u, dep_bb = %u, ..., "
    1165              :              "cur_cd_chain = { %s }, ...)\n",
    1166            7 :              depth, "", __func__, dom_bb->index, dep_bb->index,
    1167           14 :              format_edge_vec (cur_cd_chain).c_str ());
    1168              : 
    1169         4575 :   bool found_cd_chain = false;
    1170              : 
    1171              :   /* Iterate over DOM_BB's successors.  */
    1172         4575 :   edge e;
    1173         4575 :   edge_iterator ei;
    1174        13968 :   FOR_EACH_EDGE (e, ei, dom_bb->succs)
    1175              :     {
    1176         9393 :       if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
    1177           13 :         continue;
    1178              : 
    1179         9380 :       basic_block cd_bb = e->dest;
    1180         9380 :       unsigned pop_mark = cur_cd_chain.length ();
    1181         9380 :       cur_cd_chain.safe_push (e);
    1182         9380 :       basic_block target_bb
    1183         9380 :         = get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb);
    1184              :       /* Walk the post-dominator chain up to the CFG merge.  */
    1185         9380 :       found_cd_chain
    1186         9380 :           |= compute_control_dep_chain_pdom (cd_bb, dep_bb, target_bb,
    1187              :                                              cd_chains, num_chains,
    1188              :                                              cur_cd_chain, num_calls,
    1189              :                                              in_region, depth, complete_p);
    1190         9380 :       cur_cd_chain.truncate (pop_mark);
    1191        18760 :       gcc_assert (cur_cd_chain.length () == cur_chain_len);
    1192              :     }
    1193              : 
    1194         9150 :   gcc_assert (cur_cd_chain.length () == cur_chain_len);
    1195              :   return found_cd_chain;
    1196              : }
    1197              : 
    1198              : /* Wrapper around the compute_control_dep_chain worker above.  Returns
    1199              :    true when the collected set of chains in CD_CHAINS is complete.  */
    1200              : 
    1201              : static bool
    1202          830 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
    1203              :                            vec<edge> cd_chains[], unsigned *num_chains,
    1204              :                            unsigned in_region = 0)
    1205              : {
    1206          830 :   auto_vec<edge, 10> cur_cd_chain;
    1207          830 :   unsigned num_calls = 0;
    1208          830 :   unsigned depth = 0;
    1209          830 :   bool complete_p = true;
    1210              :   /* Walk the post-dominator chain.  */
    1211          830 :   cur_cd_chain.reserve (MAX_CHAIN_LEN + 1);
    1212          830 :   compute_control_dep_chain_pdom (dom_bb, dep_bb, NULL, cd_chains,
    1213              :                                   num_chains, cur_cd_chain, &num_calls,
    1214              :                                   in_region, depth, &complete_p);
    1215          830 :   return complete_p;
    1216          830 : }
    1217              : 
    1218              : /* Implemented simplifications:
    1219              : 
    1220              :    1a) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
    1221              :    1b) [!](X rel y) AND [!](X rel y') where y == y' or both constant
    1222              :        can possibly be simplified
    1223              :    2) (X AND Y) OR (!X AND Y) is equivalent to Y;
    1224              :    3) X OR (!X AND Y) is equivalent to (X OR Y);
    1225              :    4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
    1226              :       (x != 0 AND y != 0)
    1227              :    5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
    1228              :       (X AND Y) OR Z
    1229              : 
    1230              :    PREDS is the predicate chains, and N is the number of chains.  */
    1231              : 
    1232              : /* Implement rule 1a above.  PREDS is the AND predicate to simplify
    1233              :    in place.  */
    1234              : 
    1235              : static void
    1236          795 : simplify_1a (pred_chain &chain)
    1237              : {
    1238          795 :   bool simplified = false;
    1239          795 :   pred_chain s_chain = vNULL;
    1240              : 
    1241          795 :   unsigned n = chain.length ();
    1242         3892 :   for (unsigned i = 0; i < n; i++)
    1243              :     {
    1244         3097 :       pred_info &a_pred = chain[i];
    1245              : 
    1246         4839 :       if (!a_pred.pred_lhs
    1247         3097 :           || !is_neq_zero_form_p (a_pred))
    1248         1742 :         continue;
    1249              : 
    1250         1355 :       gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred.pred_lhs);
    1251         1355 :       if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
    1252          340 :         continue;
    1253              : 
    1254         1015 :       if (gimple_assign_rhs_code (def_stmt) != BIT_IOR_EXPR)
    1255         1008 :         continue;
    1256              : 
    1257           19 :       for (unsigned j = 0; j < n; j++)
    1258              :         {
    1259           12 :           const pred_info &b_pred = chain[j];
    1260              : 
    1261           15 :           if (!b_pred.pred_lhs
    1262           12 :               || !is_neq_zero_form_p (b_pred))
    1263            3 :             continue;
    1264              : 
    1265            9 :           if (pred_expr_equal_p (b_pred, gimple_assign_rhs1 (def_stmt))
    1266            9 :               || pred_expr_equal_p (b_pred, gimple_assign_rhs2 (def_stmt)))
    1267              :             {
    1268              :               /* Mark A_PRED for removal from PREDS.  */
    1269            0 :               a_pred.pred_lhs = NULL;
    1270            0 :               a_pred.pred_rhs = NULL;
    1271            0 :               simplified = true;
    1272            0 :               break;
    1273              :             }
    1274              :         }
    1275              :     }
    1276              : 
    1277          795 :   if (!simplified)
    1278          795 :     return;
    1279              : 
    1280              :   /* Remove predicates marked above.  */
    1281            0 :   for (unsigned i = 0; i < n; i++)
    1282              :     {
    1283            0 :       pred_info &a_pred = chain[i];
    1284            0 :       if (!a_pred.pred_lhs)
    1285            0 :         continue;
    1286            0 :       s_chain.safe_push (a_pred);
    1287              :     }
    1288              : 
    1289            0 :   chain.release ();
    1290            0 :   chain = s_chain;
    1291              : }
    1292              : 
    1293              : /* Implement rule 1b above.  PREDS is the AND predicate to simplify
    1294              :    in place.  Returns true if CHAIN simplifies to true or false.  */
    1295              : 
    1296              : static bool
    1297          795 : simplify_1b (pred_chain &chain)
    1298              : {
    1299         3681 :   for (unsigned i = 0; i < chain.length (); i++)
    1300              :     {
    1301         2893 :       pred_info &a_pred = chain[i];
    1302              : 
    1303        10753 :       for (unsigned j = i + 1; j < chain.length (); ++j)
    1304              :         {
    1305         7867 :           pred_info &b_pred = chain[j];
    1306              : 
    1307         7867 :           if (!operand_equal_p (a_pred.pred_lhs, b_pred.pred_lhs)
    1308         7867 :               || (!operand_equal_p (a_pred.pred_rhs, b_pred.pred_rhs)
    1309          219 :                   && !(CONSTANT_CLASS_P (a_pred.pred_rhs)
    1310          215 :                        && CONSTANT_CLASS_P (b_pred.pred_rhs))))
    1311         7654 :             continue;
    1312              : 
    1313          213 :           tree_code a_code = a_pred.cond_code;
    1314          213 :           if (a_pred.invert)
    1315          196 :             a_code = invert_tree_comparison (a_code, false);
    1316          213 :           tree_code b_code = b_pred.cond_code;
    1317          213 :           if (b_pred.invert)
    1318           30 :             b_code = invert_tree_comparison (b_code, false);
    1319              :           /* Try to combine X a_code Y && X b_code Y'.  */
    1320          213 :           tree comb = maybe_fold_and_comparisons (boolean_type_node,
    1321              :                                                   TRUTH_ANDIF_EXPR, a_code,
    1322              :                                                   a_pred.pred_lhs,
    1323              :                                                   a_pred.pred_rhs,
    1324              :                                                   b_code,
    1325              :                                                   b_pred.pred_lhs,
    1326              :                                                   b_pred.pred_rhs, NULL);
    1327          213 :           if (!comb)
    1328              :             ;
    1329          183 :           else if (integer_zerop (comb))
    1330              :             return true;
    1331          176 :           else if (integer_truep (comb))
    1332              :             {
    1333            0 :               chain.ordered_remove (j);
    1334            0 :               chain.ordered_remove (i);
    1335            0 :               if (chain.is_empty ())
    1336              :                 return true;
    1337            0 :               i--;
    1338            0 :               break;
    1339              :             }
    1340          176 :           else if (COMPARISON_CLASS_P (comb)
    1341          176 :                    && operand_equal_p (a_pred.pred_lhs, TREE_OPERAND (comb, 0)))
    1342              :             {
    1343          176 :               chain.ordered_remove (j);
    1344          176 :               a_pred.cond_code = TREE_CODE (comb);
    1345          176 :               a_pred.pred_rhs = TREE_OPERAND (comb, 1);
    1346          176 :               a_pred.invert = false;
    1347          176 :               j--;
    1348              :             }
    1349              :         }
    1350              :     }
    1351              : 
    1352              :   return false;
    1353              : }
    1354              : 
    1355              : /* Implements rule 2 for the OR predicate PREDS:
    1356              : 
    1357              :    2) (X AND Y) OR (!X AND Y) is equivalent to Y.  */
    1358              : 
    1359              : bool
    1360          120 : predicate::simplify_2 ()
    1361              : {
    1362          120 :   bool simplified = false;
    1363              : 
    1364              :   /* (X AND Y) OR (!X AND Y) is equivalent to Y.
    1365              :      (X AND Y) OR (X AND !Y) is equivalent to X.  */
    1366              : 
    1367          507 :   for (unsigned i = 0; i < m_preds.length (); i++)
    1368              :     {
    1369          387 :       pred_chain &a_chain = m_preds[i];
    1370              : 
    1371         1020 :       for (unsigned j = i + 1; j < m_preds.length (); j++)
    1372              :         {
    1373          663 :           pred_chain &b_chain = m_preds[j];
    1374         1989 :           if (b_chain.length () != a_chain.length ())
    1375          480 :             continue;
    1376              : 
    1377              :           unsigned neg_idx = -1U;
    1378          620 :           for (unsigned k = 0; k < a_chain.length (); ++k)
    1379              :             {
    1380          590 :               if (pred_equal_p (a_chain[k], b_chain[k]))
    1381          352 :                 continue;
    1382          238 :               if (neg_idx != -1U)
    1383              :                 {
    1384              :                   neg_idx = -1U;
    1385              :                   break;
    1386              :                 }
    1387          183 :               if (pred_neg_p (a_chain[k], b_chain[k]))
    1388              :                 neg_idx = k;
    1389              :               else
    1390              :                 break;
    1391              :             }
    1392              :           /* If we found equal chains with one negated predicate
    1393              :              simplify.  */
    1394          183 :           if (neg_idx != -1U)
    1395              :             {
    1396           30 :               a_chain.ordered_remove (neg_idx);
    1397           30 :               b_chain.release ();
    1398           30 :               m_preds.ordered_remove (j);
    1399           30 :               simplified = true;
    1400          417 :               if (a_chain.is_empty ())
    1401              :                 {
    1402              :                   /* A && !A simplifies to true, wipe the whole predicate.  */
    1403            2 :                   for (unsigned k = 0; k < m_preds.length (); ++k)
    1404            1 :                     m_preds[k].release ();
    1405            1 :                   m_preds.truncate (0);
    1406              :                 }
    1407              :               break;
    1408              :             }
    1409              :         }
    1410              :     }
    1411              : 
    1412          120 :   return simplified;
    1413              : }
    1414              : 
    1415              : /* Implement rule 3 for the OR predicate PREDS:
    1416              : 
    1417              :    3) x OR (!x AND y) is equivalent to x OR y.  */
    1418              : 
    1419              : bool
    1420          120 : predicate::simplify_3 ()
    1421              : {
    1422              :   /* Now iteratively simplify X OR (!X AND Z ..)
    1423              :        into X OR (Z ...).  */
    1424              : 
    1425          120 :   unsigned n = m_preds.length ();
    1426          120 :   if (n < 2)
    1427              :     return false;
    1428              : 
    1429              :   bool simplified = false;
    1430          492 :   for (unsigned i = 0; i < n; i++)
    1431              :     {
    1432          380 :       const pred_chain &a_chain = m_preds[i];
    1433              : 
    1434          380 :       if (a_chain.length () != 1)
    1435          319 :         continue;
    1436              : 
    1437           61 :       const pred_info &x = a_chain[0];
    1438          340 :       for (unsigned j = 0; j < n; j++)
    1439              :         {
    1440          218 :           if (j == i)
    1441           61 :             continue;
    1442              : 
    1443          157 :           pred_chain b_chain = m_preds[j];
    1444          157 :           if (b_chain.length () < 2)
    1445          102 :             continue;
    1446              : 
    1447          585 :           for (unsigned k = 0; k < b_chain.length (); k++)
    1448              :             {
    1449          367 :               const pred_info &x2 = b_chain[k];
    1450          367 :               if (pred_neg_p (x, x2))
    1451              :                 {
    1452           15 :                   b_chain.unordered_remove (k);
    1453           15 :                   simplified = true;
    1454           15 :                   break;
    1455              :                 }
    1456              :             }
    1457              :         }
    1458              :     }
    1459              :   return simplified;
    1460              : }
    1461              : 
    1462              : /* Implement rule 4 for the OR predicate PREDS:
    1463              : 
    1464              :    2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
    1465              :        (x != 0 AND y != 0).   */
    1466              : 
    1467              : bool
    1468          120 : predicate::simplify_4 ()
    1469              : {
    1470          120 :   bool simplified = false;
    1471          120 :   pred_chain_union s_preds = vNULL;
    1472              : 
    1473          120 :   unsigned n = m_preds.length ();
    1474          506 :   for (unsigned i = 0; i < n; i++)
    1475              :     {
    1476          386 :       pred_chain a_chain = m_preds[i];
    1477          386 :       if (a_chain.length () != 1)
    1478          386 :         continue;
    1479              : 
    1480           67 :       const pred_info &z = a_chain[0];
    1481           67 :       if (!is_neq_zero_form_p (z))
    1482           51 :         continue;
    1483              : 
    1484           16 :       gimple *def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
    1485           16 :       if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
    1486            3 :         continue;
    1487              : 
    1488           13 :       if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
    1489           13 :         continue;
    1490              : 
    1491            0 :       for (unsigned j = 0; j < n; j++)
    1492              :         {
    1493            0 :           if (j == i)
    1494            0 :             continue;
    1495              : 
    1496            0 :           pred_chain b_chain = m_preds[j];
    1497            0 :           if (b_chain.length () != 2)
    1498            0 :             continue;
    1499              : 
    1500            0 :           const pred_info &x2 = b_chain[0];
    1501            0 :           const pred_info &y2 = b_chain[1];
    1502            0 :           if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
    1503            0 :             continue;
    1504              : 
    1505            0 :           if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
    1506            0 :                && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
    1507            0 :               || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
    1508            0 :                   && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
    1509              :             {
    1510              :               /* Kill a_chain.  */
    1511            0 :               a_chain.release ();
    1512            0 :               simplified = true;
    1513            0 :               break;
    1514              :             }
    1515              :         }
    1516              :     }
    1517              :   /* Now clean up the chain.  */
    1518          120 :   if (simplified)
    1519              :     {
    1520            0 :       for (unsigned i = 0; i < n; i++)
    1521              :         {
    1522            0 :           if (m_preds[i].is_empty ())
    1523            0 :             continue;
    1524            0 :           s_preds.safe_push (m_preds[i]);
    1525              :         }
    1526              : 
    1527            0 :       m_preds.release ();
    1528            0 :       m_preds = s_preds;
    1529            0 :       s_preds = vNULL;
    1530              :     }
    1531              : 
    1532          120 :   return simplified;
    1533              : }
    1534              : 
    1535              : /* Simplify predicates in *THIS.  */
    1536              : 
    1537              : void
    1538          529 : predicate::simplify (gimple *use_or_def, bool is_use)
    1539              : {
    1540          529 :   if (dump_file && dump_flags & TDF_DETAILS)
    1541              :     {
    1542            0 :       fprintf (dump_file, "Before simplication ");
    1543            0 :       dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
    1544              :     }
    1545              : 
    1546         1324 :   for (unsigned i = 0; i < m_preds.length (); i++)
    1547              :     {
    1548          795 :       ::simplify_1a (m_preds[i]);
    1549          795 :       if (::simplify_1b (m_preds[i]))
    1550              :         {
    1551            7 :           m_preds[i].release ();
    1552            7 :           m_preds.ordered_remove (i);
    1553            7 :           i--;
    1554              :         }
    1555              :     }
    1556              : 
    1557          529 :   if (m_preds.length () < 2)
    1558              :     return;
    1559              : 
    1560          120 :   bool changed;
    1561          120 :   do
    1562              :     {
    1563          120 :       changed = false;
    1564          120 :       if (simplify_2 ())
    1565              :         changed = true;
    1566              : 
    1567          120 :       if (simplify_3 ())
    1568            9 :         changed = true;
    1569              : 
    1570          120 :       if (simplify_4 ())
    1571            0 :         changed = true;
    1572              :     }
    1573              :   while (changed);
    1574              : }
    1575              : 
    1576              : /* Attempt to normalize predicate chains by following UD chains by
    1577              :    building up a big tree of either IOR operations or AND operations,
    1578              :    and converting the IOR tree into a pred_chain_union or the BIT_AND
    1579              :    tree into a pred_chain.
    1580              :    Example:
    1581              : 
    1582              :   _3 = _2 RELOP1 _1;
    1583              :   _6 = _5 RELOP2 _4;
    1584              :   _9 = _8 RELOP3 _7;
    1585              :   _10 = _3 | _6;
    1586              :   _12 = _9 | _0;
    1587              :   _t = _10 | _12;
    1588              : 
    1589              :   then _t != 0 will be normalized into a pred_chain_union
    1590              : 
    1591              :    (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
    1592              : 
    1593              :    Similarly given:
    1594              : 
    1595              :   _3 = _2 RELOP1 _1;
    1596              :   _6 = _5 RELOP2 _4;
    1597              :   _9 = _8 RELOP3 _7;
    1598              :   _10 = _3 & _6;
    1599              :   _12 = _9 & _0;
    1600              : 
    1601              :   then _t != 0 will be normalized into a pred_chain:
    1602              :   (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
    1603              :   */
    1604              : 
    1605              : /* Normalize predicate PRED:
    1606              :    1) if PRED can no longer be normalized, append it to *THIS.
    1607              :    2) otherwise if PRED is of the form x != 0, follow x's definition
    1608              :       and put normalized predicates into WORK_LIST.  */
    1609              : 
    1610              : void
    1611         2464 : predicate::normalize (pred_chain *norm_chain,
    1612              :                       pred_info pred,
    1613              :                       tree_code and_or_code,
    1614              :                       pred_chain *work_list,
    1615              :                       hash_set<tree> *mark_set)
    1616              : {
    1617         2464 :   if (!is_neq_zero_form_p (pred))
    1618              :     {
    1619         1318 :       if (and_or_code == BIT_IOR_EXPR)
    1620            0 :         push_pred (pred);
    1621              :       else
    1622         1318 :         norm_chain->safe_push (pred);
    1623              :       return;
    1624              :     }
    1625              : 
    1626         1146 :   gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
    1627              : 
    1628         1146 :   if (gimple_code (def_stmt) == GIMPLE_PHI
    1629         1146 :       && is_degenerate_phi (def_stmt, &pred))
    1630              :     /* PRED has been modified above.  */
    1631            0 :     work_list->safe_push (pred);
    1632         1146 :   else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
    1633              :     {
    1634            3 :       unsigned n = gimple_phi_num_args (def_stmt);
    1635              : 
    1636              :       /* Punt for a nonzero constant.  The predicate should be one guarding
    1637              :          the phi edge.  */
    1638            9 :       for (unsigned i = 0; i < n; ++i)
    1639              :         {
    1640            6 :           tree op = gimple_phi_arg_def (def_stmt, i);
    1641            6 :           if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
    1642              :             {
    1643            0 :               push_pred (pred);
    1644            0 :               return;
    1645              :             }
    1646              :         }
    1647              : 
    1648            9 :       for (unsigned i = 0; i < n; ++i)
    1649              :         {
    1650            6 :           tree op = gimple_phi_arg_def (def_stmt, i);
    1651            6 :           if (integer_zerop (op))
    1652            0 :             continue;
    1653              : 
    1654            6 :           push_to_worklist (op, work_list, mark_set);
    1655              :         }
    1656              :     }
    1657         1143 :   else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
    1658              :     {
    1659          268 :       if (and_or_code == BIT_IOR_EXPR)
    1660            7 :         push_pred (pred);
    1661              :       else
    1662          261 :         norm_chain->safe_push (pred);
    1663              :     }
    1664          875 :   else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
    1665              :     {
    1666              :       /* Avoid splitting up bit manipulations like x & 3 or y | 1.  */
    1667           61 :       if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
    1668              :         {
    1669              :           /* But treat x & 3 as a condition.  */
    1670           34 :           if (and_or_code == BIT_AND_EXPR)
    1671              :             {
    1672           34 :               pred_info n_pred;
    1673           34 :               n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
    1674           34 :               n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
    1675           34 :               n_pred.cond_code = and_or_code;
    1676           34 :               n_pred.invert = false;
    1677           34 :               norm_chain->safe_push (n_pred);
    1678              :             }
    1679              :         }
    1680              :       else
    1681              :         {
    1682           27 :           push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
    1683           27 :           push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
    1684              :         }
    1685              :     }
    1686          814 :   else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
    1687              :            == tcc_comparison)
    1688              :     {
    1689           39 :       pred_info n_pred = get_pred_info_from_cmp (def_stmt);
    1690           39 :       if (and_or_code == BIT_IOR_EXPR)
    1691            0 :         push_pred (n_pred);
    1692              :       else
    1693           39 :         norm_chain->safe_push (n_pred);
    1694              :     }
    1695              :   else
    1696              :     {
    1697          775 :       if (and_or_code == BIT_IOR_EXPR)
    1698            0 :         push_pred (pred);
    1699              :       else
    1700          775 :         norm_chain->safe_push (pred);
    1701              :     }
    1702              : }
    1703              : 
    1704              : /* Normalize PRED and store the normalized predicates in THIS->M_PREDS.  */
    1705              : 
    1706              : void
    1707          275 : predicate::normalize (const pred_info &pred)
    1708              : {
    1709          275 :   if (!is_neq_zero_form_p (pred))
    1710              :     {
    1711          161 :       push_pred (pred);
    1712          408 :       return;
    1713              :     }
    1714              : 
    1715          114 :   tree_code and_or_code = ERROR_MARK;
    1716              : 
    1717          114 :   gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
    1718          114 :   if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
    1719           45 :     and_or_code = gimple_assign_rhs_code (def_stmt);
    1720          114 :   if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
    1721              :     {
    1722           86 :       if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
    1723              :         {
    1724            0 :           pred_info n_pred = get_pred_info_from_cmp (def_stmt);
    1725            0 :           push_pred (n_pred);
    1726              :         }
    1727              :       else
    1728           86 :         push_pred (pred);
    1729              :       return;
    1730              :     }
    1731              : 
    1732              : 
    1733           28 :   pred_chain norm_chain = vNULL;
    1734           28 :   pred_chain work_list = vNULL;
    1735           28 :   work_list.safe_push (pred);
    1736           28 :   hash_set<tree> mark_set;
    1737              : 
    1738          110 :   while (!work_list.is_empty ())
    1739              :     {
    1740           54 :       pred_info a_pred = work_list.pop ();
    1741           54 :       normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set);
    1742              :     }
    1743              : 
    1744           28 :   if (and_or_code == BIT_AND_EXPR)
    1745           25 :     m_preds.safe_push (norm_chain);
    1746              : 
    1747           28 :   work_list.release ();
    1748           28 : }
    1749              : 
    1750              : /* Normalize a single predicate PRED_CHAIN and append it to *THIS.  */
    1751              : 
    1752              : void
    1753          482 : predicate::normalize (const pred_chain &chain)
    1754              : {
    1755          482 :   pred_chain work_list = vNULL;
    1756          482 :   hash_set<tree> mark_set;
    1757         3342 :   for (unsigned i = 0; i < chain.length (); i++)
    1758              :     {
    1759         2378 :       work_list.safe_push (chain[i]);
    1760         2378 :       mark_set.add (chain[i].pred_lhs);
    1761              :     }
    1762              : 
    1763              :   /* Normalized chain of predicates built up below.  */
    1764          482 :   pred_chain norm_chain = vNULL;
    1765         2892 :   while (!work_list.is_empty ())
    1766              :     {
    1767         2410 :       pred_info pi = work_list.pop ();
    1768              :       /* The predicate object is not modified here, only NORM_CHAIN and
    1769              :          WORK_LIST are appended to.  */
    1770         4820 :       unsigned oldlen = m_preds.length ();
    1771         2410 :       normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set);
    1772         3828 :       gcc_assert (m_preds.length () == oldlen);
    1773              :     }
    1774              : 
    1775          482 :   m_preds.safe_push (norm_chain);
    1776          482 :   work_list.release ();
    1777          482 : }
    1778              : 
    1779              : /* Normalize predicate chains in THIS.  */
    1780              : 
    1781              : void
    1782          529 : predicate::normalize (gimple *use_or_def, bool is_use)
    1783              : {
    1784          529 :   if (dump_file && dump_flags & TDF_DETAILS)
    1785              :     {
    1786            0 :       fprintf (dump_file, "Before normalization ");
    1787            0 :       dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
    1788              :     }
    1789              : 
    1790          529 :   predicate norm_preds (empty_val ());
    1791         1286 :   for (unsigned i = 0; i < m_preds.length (); i++)
    1792              :     {
    1793          757 :       if (m_preds[i].length () != 1)
    1794          482 :         norm_preds.normalize (m_preds[i]);
    1795              :       else
    1796          275 :         norm_preds.normalize (m_preds[i][0]);
    1797              :     }
    1798              : 
    1799          529 :   *this = norm_preds;
    1800              : 
    1801          529 :   if (dump_file)
    1802              :     {
    1803            4 :       fprintf (dump_file, "After normalization ");
    1804            6 :       dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
    1805              :     }
    1806          529 : }
    1807              : 
    1808              : /* Convert the chains of control dependence edges into a set of predicates.
    1809              :    A control dependence chain is represented by a vector edges.  DEP_CHAINS
    1810              :    points to an array of NUM_CHAINS dependence chains. One edge in
    1811              :    a dependence chain is mapped to predicate expression represented by
    1812              :    pred_info type.  One dependence chain is converted to a composite
    1813              :    predicate that is the result of AND operation of pred_info mapped to
    1814              :    each edge.  A composite predicate is represented by a vector of
    1815              :    pred_info.  Sets M_PREDS to the resulting composite predicates.  */
    1816              : 
    1817              : void
    1818          762 : predicate::init_from_control_deps (const vec<edge> *dep_chains,
    1819              :                                    unsigned num_chains, bool is_use)
    1820              : {
    1821          762 :   gcc_assert (is_empty ());
    1822              : 
    1823          762 :   if (num_chains == 0)
    1824              :     return;
    1825              : 
    1826          691 :   if (DEBUG_PREDICATE_ANALYZER && dump_file)
    1827            6 :     fprintf (dump_file, "init_from_control_deps [%s] {%s}:\n",
    1828              :              is_use ? "USE" : "DEF",
    1829            8 :              format_edge_vecs (dep_chains, num_chains).c_str ());
    1830              : 
    1831              :   /* Convert the control dependency chain into a set of predicates.  */
    1832          691 :   m_preds.reserve (num_chains);
    1833              : 
    1834         2189 :   for (unsigned i = 0; i < num_chains; i++)
    1835              :     {
    1836              :       /* One path through the CFG represents a logical conjunction
    1837              :          of the predicates.  */
    1838          965 :       const vec<edge> &path = dep_chains[i];
    1839              : 
    1840          965 :       bool has_valid_pred = false;
    1841              :       /* The chain of predicates guarding the definition along this path.  */
    1842          965 :       pred_chain t_chain{ };
    1843         4110 :       for (unsigned j = 0; j < path.length (); j++)
    1844              :         {
    1845         3157 :           edge e = path[j];
    1846         3157 :           basic_block guard_bb = e->src;
    1847              : 
    1848         6314 :           gcc_assert (!empty_block_p (guard_bb) && !single_succ_p (guard_bb));
    1849              : 
    1850              :           /* Skip this edge if it is bypassing an abort - when the
    1851              :              condition is not satisfied we are neither reaching the
    1852              :              definition nor the use so it isn't meaningful.  Note if
    1853              :              we are processing the use predicate the condition is
    1854              :              meaningful.  See PR65244.  */
    1855         3157 :           if (!is_use && EDGE_COUNT (e->src->succs) == 2)
    1856              :             {
    1857         1170 :               edge e1;
    1858         1170 :               edge_iterator ei1;
    1859         1170 :               bool skip = false;
    1860              : 
    1861         3508 :               FOR_EACH_EDGE (e1, ei1, e->src->succs)
    1862              :                 {
    1863         2339 :                   if (EDGE_COUNT (e1->dest->succs) == 0)
    1864              :                     {
    1865              :                       skip = true;
    1866              :                       break;
    1867              :                     }
    1868              :                 }
    1869         1170 :               if (skip)
    1870              :                 {
    1871            1 :                   has_valid_pred = true;
    1872            1 :                   continue;
    1873              :                 }
    1874              :             }
    1875              :           /* Get the conditional controlling the bb exit edge.  */
    1876         3156 :           gimple *cond_stmt = *gsi_last_bb (guard_bb);
    1877         3156 :           if (gimple_code (cond_stmt) == GIMPLE_COND)
    1878              :             {
    1879              :               /* The true edge corresponds to the uninteresting condition.
    1880              :                  Add the negated predicate(s) for the edge to record
    1881              :                  the interesting condition.  */
    1882         3042 :               pred_info one_pred = get_pred_info_from_cond_edge (e);
    1883              : 
    1884         3042 :               t_chain.safe_push (one_pred);
    1885              : 
    1886         3042 :               if (DEBUG_PREDICATE_ANALYZER && dump_file)
    1887              :                 {
    1888            6 :                   fprintf (dump_file, "%d -> %d: one_pred = ",
    1889            6 :                            e->src->index, e->dest->index);
    1890            6 :                   dump_pred_info (dump_file, one_pred);
    1891            6 :                   fputc ('\n', dump_file);
    1892              :                 }
    1893              : 
    1894         3042 :               has_valid_pred = true;
    1895              :             }
    1896          114 :           else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
    1897              :             {
    1898              :               /* Find the case label, but avoid quadratic behavior.  */
    1899           97 :               tree l = get_cases_for_edge (e, gs);
    1900              :               /* If more than one label reaches this block or the case
    1901              :                  label doesn't have a contiguous range of values (like the
    1902              :                  default one) fail.  */
    1903          194 :               if (!l || CASE_CHAIN (l) || !CASE_LOW (l))
    1904              :                 has_valid_pred = false;
    1905           87 :               else if (!CASE_HIGH (l)
    1906           87 :                       || operand_equal_p (CASE_LOW (l), CASE_HIGH (l)))
    1907              :                 {
    1908           87 :                   pred_info one_pred;
    1909           87 :                   one_pred.pred_lhs = gimple_switch_index (gs);
    1910           87 :                   one_pred.pred_rhs
    1911           87 :                     = wide_int_to_tree (TREE_TYPE (one_pred.pred_lhs),
    1912           87 :                                         wi::to_widest (CASE_LOW (l)));
    1913           87 :                   one_pred.cond_code = EQ_EXPR;
    1914           87 :                   one_pred.invert = false;
    1915           87 :                   t_chain.safe_push (one_pred);
    1916           87 :                   has_valid_pred = true;
    1917              :                 }
    1918              :               else
    1919              :                 {
    1920              :                   /* Support a case label with a range with
    1921              :                      two predicates.  We're overcommitting on
    1922              :                      the MAX_CHAIN_LEN budget by at most a factor
    1923              :                      of two here.  */
    1924            0 :                   pred_info one_pred;
    1925            0 :                   one_pred.pred_lhs = gimple_switch_index (gs);
    1926            0 :                   one_pred.pred_rhs
    1927            0 :                     = wide_int_to_tree (TREE_TYPE (one_pred.pred_lhs),
    1928            0 :                                         wi::to_widest (CASE_LOW (l)));
    1929            0 :                   one_pred.cond_code = GE_EXPR;
    1930            0 :                   one_pred.invert = false;
    1931            0 :                   t_chain.safe_push (one_pred);
    1932            0 :                   one_pred.pred_rhs
    1933            0 :                     = wide_int_to_tree (TREE_TYPE (one_pred.pred_lhs),
    1934            0 :                                         wi::to_widest (CASE_HIGH (l)));
    1935            0 :                   one_pred.cond_code = LE_EXPR;
    1936            0 :                   t_chain.safe_push (one_pred);
    1937            0 :                   has_valid_pred = true;
    1938              :                 }
    1939              :             }
    1940           17 :           else if (stmt_can_throw_internal (cfun, cond_stmt)
    1941           17 :                    && !(e->flags & EDGE_EH))
    1942              :             /* Ignore the exceptional control flow and proceed as if
    1943              :                E were a fallthru without a controlling predicate for
    1944              :                both the USE (valid) and DEF (questionable) case.  */
    1945              :             has_valid_pred = true;
    1946              :           else
    1947              :             has_valid_pred = false;
    1948              : 
    1949              :           /* For USE predicates we can drop components of the
    1950              :              AND chain.  */
    1951         3153 :           if (!has_valid_pred && !is_use)
    1952              :             break;
    1953              :         }
    1954              : 
    1955              :       /* For DEF predicates we have to drop components of the OR chain
    1956              :          on failure.  */
    1957          965 :       if (!has_valid_pred && !is_use)
    1958              :         {
    1959           12 :           t_chain.release ();
    1960           12 :           continue;
    1961              :         }
    1962              : 
    1963              :       /* When we add || 1 simply prune the chain and return.  */
    1964          953 :       if (t_chain.is_empty ())
    1965              :         {
    1966          158 :           t_chain.release ();
    1967          474 :           for (auto chain : m_preds)
    1968            0 :             chain.release ();
    1969          158 :           m_preds.truncate (0);
    1970          158 :           break;
    1971              :         }
    1972              : 
    1973          795 :       m_preds.quick_push (t_chain);
    1974              :     }
    1975              : 
    1976          691 :   if (DEBUG_PREDICATE_ANALYZER && dump_file)
    1977            4 :     dump (dump_file);
    1978              : }
    1979              : 
    1980              : /* Store a PRED in *THIS.  */
    1981              : 
    1982              : void
    1983          254 : predicate::push_pred (const pred_info &pred)
    1984              : {
    1985          254 :   pred_chain chain = vNULL;
    1986          254 :   chain.safe_push (pred);
    1987          254 :   m_preds.safe_push (chain);
    1988          254 : }
    1989              : 
    1990              : /* Dump predicates in *THIS to F.  */
    1991              : 
    1992              : void
    1993            8 : predicate::dump (FILE *f) const
    1994              : {
    1995            8 :   unsigned np = m_preds.length ();
    1996            8 :   if (np == 0)
    1997              :     {
    1998            0 :       fprintf (f, "\tTRUE (empty)\n");
    1999            0 :       return;
    2000              :     }
    2001              : 
    2002           16 :   for (unsigned i = 0; i < np; i++)
    2003              :     {
    2004            8 :       if (i > 0)
    2005            0 :         fprintf (f, "\tOR (");
    2006              :       else
    2007            8 :         fprintf (f, "\t(");
    2008            8 :       dump_pred_chain (f, m_preds[i]);
    2009            8 :       fprintf (f, ")\n");
    2010              :     }
    2011              : }
    2012              : 
    2013              : /* Dump predicates in *THIS to stderr.  */
    2014              : 
    2015              : void
    2016            0 : predicate::debug () const
    2017              : {
    2018            0 :   dump (stderr);
    2019            0 : }
    2020              : 
    2021              : /* Dump predicates in *THIS for STMT prepended by MSG to F.  */
    2022              : 
    2023              : void
    2024            4 : predicate::dump (FILE *f, gimple *stmt, const char *msg) const
    2025              : {
    2026            4 :   fprintf (f, "%s", msg);
    2027            4 :   if (stmt)
    2028              :     {
    2029            4 :       fputc ('\t', f);
    2030            4 :       print_gimple_stmt (f, stmt, 0);
    2031            4 :       fprintf (f, "  is conditional on:\n");
    2032              :     }
    2033              : 
    2034            4 :   dump (f);
    2035            4 : }
    2036              : 
    2037              : /* Initialize USE_PREDS with the predicates of the control dependence chains
    2038              :    between the basic block DEF_BB that defines a variable of interest and
    2039              :    USE_BB that uses the variable, respectively.  */
    2040              : 
    2041              : bool
    2042          572 : uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
    2043              :                                  basic_block use_bb)
    2044              : {
    2045          572 :   if (DEBUG_PREDICATE_ANALYZER && dump_file)
    2046            2 :     fprintf (dump_file, "init_use_preds (def_bb = %u, use_bb = %u)\n",
    2047              :              def_bb->index, use_bb->index);
    2048              : 
    2049          572 :   gcc_assert (use_preds.is_empty ()
    2050              :               && dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
    2051              : 
    2052              :   /* Set CD_ROOT to the basic block closest to USE_BB that is the control
    2053              :      equivalent of (is guarded by the same predicate as) DEF_BB that also
    2054              :      dominates USE_BB.  This mimics the inner loop in
    2055              :      compute_control_dep_chain.  */
    2056              :   basic_block cd_root = def_bb;
    2057          754 :   do
    2058              :     {
    2059          754 :       basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, cd_root);
    2060              : 
    2061              :       /* Stop at a loop exit which is also postdominating cd_root.  */
    2062          923 :       if (single_pred_p (pdom) && !single_succ_p (cd_root))
    2063              :         break;
    2064              : 
    2065         1354 :       if (!dominated_by_p (CDI_DOMINATORS, pdom, cd_root)
    2066          677 :           || !dominated_by_p (CDI_DOMINATORS, use_bb, pdom))
    2067              :         break;
    2068              : 
    2069              :       cd_root = pdom;
    2070              :     }
    2071              :   while (1);
    2072              : 
    2073          572 :   auto_bb_flag in_region (cfun);
    2074          572 :   auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
    2075          572 :                                          param_uninit_control_dep_attempts));
    2076              : 
    2077              :   /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
    2078              :      Each DEP_CHAINS element is a series of edges whose conditions
    2079              :      are logical conjunctions.  Together, the DEP_CHAINS vector is
    2080              :      used below to initialize an OR expression of the conjunctions.  */
    2081          572 :   unsigned num_chains = 0;
    2082         5148 :   auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
    2083              : 
    2084          572 :   if (!dfs_mark_dominating_region (use_bb, cd_root, in_region, region)
    2085         1144 :       || !compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
    2086          572 :                                      in_region))
    2087              :     {
    2088              :       /* If the info in dep_chains is not complete we need to use a
    2089              :          conservative approximation for the use predicate.  */
    2090            0 :       if (DEBUG_PREDICATE_ANALYZER && dump_file)
    2091            0 :         fprintf (dump_file, "init_use_preds: dep_chain incomplete, using "
    2092              :                  "conservative approximation\n");
    2093            0 :       num_chains = 1;
    2094            0 :       dep_chains[0].truncate (0);
    2095            0 :       simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
    2096              :     }
    2097              : 
    2098              :   /* Unmark the region.  */
    2099         3706 :   for (auto bb : region)
    2100         1990 :     bb->flags &= ~in_region;
    2101              : 
    2102              :   /* From the set of edges computed above initialize *THIS as the OR
    2103              :      condition under which the definition in DEF_BB is used in USE_BB.
    2104              :      Each OR subexpression is represented by one element of DEP_CHAINS,
    2105              :      where each element consists of a series of AND subexpressions.  */
    2106          572 :   use_preds.init_from_control_deps (dep_chains, num_chains, true);
    2107         5720 :   delete[] dep_chains;
    2108         1144 :   return !use_preds.is_empty ();
    2109          572 : }
    2110              : 
    2111              : /* Release resources in *THIS.  */
    2112              : 
    2113         2010 : predicate::~predicate ()
    2114              : {
    2115         2010 :   unsigned n = m_preds.length ();
    2116         3842 :   for (unsigned i = 0; i != n; ++i)
    2117         1832 :     m_preds[i].release ();
    2118         2010 :   m_preds.release ();
    2119         2010 : }
    2120              : 
    2121              : /* Copy-assign RHS to *THIS.  */
    2122              : 
    2123              : predicate&
    2124          681 : predicate::operator= (const predicate &rhs)
    2125              : {
    2126          681 :   if (this == &rhs)
    2127              :     return *this;
    2128              : 
    2129          681 :   m_cval = rhs.m_cval;
    2130              : 
    2131          681 :   unsigned n = m_preds.length ();
    2132         1438 :   for (unsigned i = 0; i != n; ++i)
    2133          757 :     m_preds[i].release ();
    2134          681 :   m_preds.release ();
    2135              : 
    2136          681 :   n = rhs.m_preds.length ();
    2137         1752 :   for (unsigned i = 0; i != n; ++i)
    2138              :     {
    2139         1071 :       const pred_chain &chain = rhs.m_preds[i];
    2140         1071 :       m_preds.safe_push (chain.copy ());
    2141              :     }
    2142              : 
    2143              :   return *this;
    2144              : }
    2145              : 
    2146              : /* For each use edge of PHI, compute all control dependence chains
    2147              :    and convert those to the composite predicates in M_PREDS.
    2148              :    Return true if a nonempty predicate has been obtained.  */
    2149              : 
    2150              : bool
    2151          190 : uninit_analysis::init_from_phi_def (gphi *phi)
    2152              : {
    2153          190 :   gcc_assert (m_phi_def_preds.is_empty ());
    2154              : 
    2155          190 :   basic_block phi_bb = gimple_bb (phi);
    2156              :   /* Find the closest dominating bb to be the control dependence root.  */
    2157          190 :   basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
    2158          190 :   if (!cd_root)
    2159              :     return false;
    2160              : 
    2161              :   /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
    2162              :      definitions of each of the PHI operands for which M_EVAL is false.  */
    2163          190 :   auto_vec<edge> def_edges;
    2164          190 :   hash_set<gimple *> visited_phis;
    2165          190 :   collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
    2166              : 
    2167          380 :   unsigned nedges = def_edges.length ();
    2168          190 :   if (nedges == 0)
    2169              :     return false;
    2170              : 
    2171          190 :   auto_bb_flag in_region (cfun);
    2172          190 :   auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
    2173          190 :                                          param_uninit_control_dep_attempts));
    2174              :   /* Pre-mark the PHI incoming edges PHI block to make sure we only walk
    2175              :      interesting edges from there.  */
    2176          638 :   for (unsigned i = 0; i < nedges; i++)
    2177              :     {
    2178          258 :       if (!(def_edges[i]->dest->flags & in_region))
    2179              :         {
    2180          222 :           if (!region.space (1))
    2181              :             break;
    2182          222 :           def_edges[i]->dest->flags |= in_region;
    2183          222 :           region.quick_push (def_edges[i]->dest);
    2184              :         }
    2185              :     }
    2186          448 :   for (unsigned i = 0; i < nedges; i++)
    2187          258 :     if (!dfs_mark_dominating_region (def_edges[i]->src, cd_root,
    2188              :                                      in_region, region))
    2189              :       break;
    2190              : 
    2191          190 :   unsigned num_chains = 0;
    2192         1710 :   auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
    2193          448 :   for (unsigned i = 0; i < nedges; i++)
    2194              :     {
    2195          258 :       edge e = def_edges[i];
    2196          258 :       unsigned prev_nc = num_chains;
    2197          258 :       bool complete_p = compute_control_dep_chain (cd_root, e->src, dep_chains,
    2198          258 :                                                    &num_chains, in_region);
    2199              : 
    2200              :       /* Update the newly added chains with the phi operand edge.  */
    2201          258 :       if (EDGE_COUNT (e->src->succs) > 1)
    2202              :         {
    2203            0 :           if (complete_p
    2204            0 :               && prev_nc == num_chains
    2205            0 :               && num_chains < MAX_NUM_CHAINS)
    2206              :             /* We can only add a chain for the PHI operand edge when the
    2207              :                collected info was complete, otherwise the predicate may
    2208              :                not be conservative.  */
    2209            0 :             dep_chains[num_chains++] = vNULL;
    2210            0 :           for (unsigned j = prev_nc; j < num_chains; j++)
    2211            0 :             dep_chains[j].safe_push (e);
    2212              :         }
    2213              :     }
    2214              : 
    2215              :   /* Unmark the region.  */
    2216         4770 :   for (auto bb : region)
    2217         4200 :     bb->flags &= ~in_region;
    2218              : 
    2219              :   /* Convert control dependence chains to the predicate in *THIS under
    2220              :      which the PHI operands are defined to values for which M_EVAL is
    2221              :      false.  */
    2222          190 :   m_phi_def_preds.init_from_control_deps (dep_chains, num_chains, false);
    2223         1900 :   delete[] dep_chains;
    2224          380 :   return !m_phi_def_preds.is_empty ();
    2225          380 : }
    2226              : 
    2227              : /* Compute the predicates that guard the use USE_STMT and check if
    2228              :    the incoming paths that have an empty (or possibly empty) definition
    2229              :    can be pruned.  Return true if it can be determined that the use of
    2230              :    PHI's def in USE_STMT is guarded by a predicate set that does not
    2231              :    overlap with the predicate sets of all runtime paths that do not
    2232              :    have a definition.
    2233              : 
    2234              :    Return false if the use is not guarded or if it cannot be determined.
    2235              :    USE_BB is the bb of the use (for phi operand use, the bb is not the bb
    2236              :    of the phi stmt, but the source bb of the operand edge).
    2237              : 
    2238              :    OPNDS is a bitmap with a bit set for each PHI operand of interest.
    2239              : 
    2240              :    THIS->M_PREDS contains the (memoized) defining predicate chains of
    2241              :    a PHI.  If THIS->M_PREDS is empty, the PHI's defining predicate
    2242              :    chains are computed and stored into THIS->M_PREDS as needed.
    2243              : 
    2244              :    VISITED_PHIS is a pointer set of phis being visited.  */
    2245              : 
    2246              : bool
    2247          591 : uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb,
    2248              :                                  gphi *phi, unsigned opnds,
    2249              :                                  hash_set<gphi *> *visited)
    2250              : {
    2251          591 :   if (visited->add (phi))
    2252              :     return false;
    2253              : 
    2254              :   /* The basic block where the PHI is defined.  */
    2255          572 :   basic_block def_bb = gimple_bb (phi);
    2256              : 
    2257              :   /* Try to build the predicate expression under which the PHI flows
    2258              :      into its use.  This will be empty if the PHI is defined and used
    2259              :      in the same bb.  */
    2260          572 :   predicate use_preds (true);
    2261          572 :   if (!init_use_preds (use_preds, def_bb, use_bb))
    2262              :     return false;
    2263              : 
    2264          413 :   use_preds.simplify (use_stmt, /*is_use=*/true);
    2265          413 :   use_preds.normalize (use_stmt, /*is_use=*/true);
    2266          413 :   if (use_preds.is_false ())
    2267              :     return true;
    2268          413 :   if (use_preds.is_true ())
    2269              :     return false;
    2270              : 
    2271              :   /* Try to prune the dead incoming phi edges.  */
    2272          412 :   if (!overlap (phi, opnds, visited, use_preds))
    2273              :     {
    2274          113 :       if (DEBUG_PREDICATE_ANALYZER && dump_file)
    2275            0 :         fputs ("found predicate overlap\n", dump_file);
    2276              : 
    2277              :       return true;
    2278              :     }
    2279              : 
    2280          524 :   if (m_phi_def_preds.is_empty ())
    2281              :     {
    2282              :       /* Lazily initialize *THIS from PHI.  */
    2283          190 :       if (!init_from_phi_def (phi))
    2284              :         return false;
    2285              : 
    2286          116 :       m_phi_def_preds.simplify (phi);
    2287          116 :       m_phi_def_preds.normalize (phi);
    2288          116 :       if (m_phi_def_preds.is_false ())
    2289              :         return false;
    2290          116 :       if (m_phi_def_preds.is_true ())
    2291              :         return true;
    2292              :     }
    2293              : 
    2294              :   /* Return true if the predicate guarding the valid definition (i.e.,
    2295              :      *THIS) is a superset of the predicate guarding the use (i.e.,
    2296              :      USE_PREDS).  */
    2297          225 :   if (m_phi_def_preds.superset_of (use_preds))
    2298              :     return true;
    2299              : 
    2300              :   /* The superset test fails when a guard that distinguishes the defined from
    2301              :      the undefined value sits on the PHI's maybe-undef incoming edge rather
    2302              :      than on the use's control-dependence chain -- e.g. after ifcombine merges
    2303              :      the conditions guarding the definition.  A conjunct of the definition
    2304              :      predicate that is implied by the incoming-edge condition of every
    2305              :      maybe-undef operand cannot make the use unsafe: when that conjunct is
    2306              :      false the maybe-undef edge is not taken either, so no undefined value
    2307              :      reaches the PHI.  Drop such conjuncts from a copy of the definition
    2308              :      predicate and retry; bail unless every maybe-undef operand arrives on a
    2309              :      simple conditional edge.  */
    2310          183 :   auto_vec<pred_info, 4> edge_conds;
    2311          183 :   unsigned nargs = gimple_phi_num_args (phi);
    2312          682 :   for (unsigned i = 0; i < nargs && i < m_eval.max_phi_args; i++)
    2313              :     {
    2314          530 :       if (!MASK_TEST_BIT (opnds, i))
    2315          115 :         continue;
    2316          415 :       edge e = gimple_phi_arg_edge (phi, i);
    2317              :       /* Walk up through forwarder blocks to the controlling conditional; a
    2318              :          single-predecessor forwarder preserves the implication.  */
    2319          804 :       while (single_pred_p (e->src) && single_succ_p (e->src))
    2320          389 :         e = single_pred_edge (e->src);
    2321          415 :       if (EDGE_COUNT (e->src->succs) != 2
    2322          799 :           || !safe_dyn_cast <gcond *> (*gsi_last_bb (e->src)))
    2323              :         {
    2324           31 :           edge_conds.truncate (0);
    2325           31 :           break;
    2326              :         }
    2327          384 :       edge_conds.safe_push (get_pred_info_from_cond_edge (e));
    2328              :     }
    2329              : 
    2330          366 :   if (!edge_conds.is_empty ())
    2331              :     {
    2332          152 :       predicate relaxed (m_phi_def_preds);
    2333          152 :       if (relaxed.drop_conjuncts_implied_by (edge_conds)
    2334          152 :           && relaxed.superset_of (use_preds))
    2335            2 :         return true;
    2336          152 :     }
    2337              : 
    2338              :   return false;
    2339          572 : }
    2340              : 
    2341              : /* Public interface to the above. */
    2342              : 
    2343              : bool
    2344          551 : uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
    2345              :                                  unsigned opnds)
    2346              : {
    2347          551 :   hash_set<gphi *> visited;
    2348          551 :   return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
    2349          551 : }
    2350              : 
        

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.