LCOV - code coverage report
Current view: top level - gcc - tree-ssa-uninit.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 935 1088 85.9 %
Date: 2020-03-28 11:57:23 Functions: 53 58 91.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Predicate aware uninitialized variable warning.
       2                 :            :    Copyright (C) 2001-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Xinliang David Li <davidxl@google.com>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify
       8                 :            : it under the terms of the GNU General Public License as published by
       9                 :            : the Free Software Foundation; either version 3, or (at your option)
      10                 :            : any later version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful,
      13                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            : GNU General Public License for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "gimple.h"
      27                 :            : #include "tree-pass.h"
      28                 :            : #include "ssa.h"
      29                 :            : #include "gimple-pretty-print.h"
      30                 :            : #include "diagnostic-core.h"
      31                 :            : #include "fold-const.h"
      32                 :            : #include "gimple-iterator.h"
      33                 :            : #include "tree-ssa.h"
      34                 :            : #include "tree-cfg.h"
      35                 :            : #include "cfghooks.h"
      36                 :            : 
      37                 :            : /* This implements the pass that does predicate aware warning on uses of
      38                 :            :    possibly uninitialized variables.  The pass first collects the set of
      39                 :            :    possibly uninitialized SSA names.  For each such name, it walks through
      40                 :            :    all its immediate uses.  For each immediate use, it rebuilds the condition
      41                 :            :    expression (the predicate) that guards the use.  The predicate is then
      42                 :            :    examined to see if the variable is always defined under that same condition.
      43                 :            :    This is done either by pruning the unrealizable paths that lead to the
      44                 :            :    default definitions or by checking if the predicate set that guards the
      45                 :            :    defining paths is a superset of the use predicate.  */
      46                 :            : 
      47                 :            : /* Max PHI args we can handle in pass.  */
      48                 :            : const unsigned max_phi_args = 32;
      49                 :            : 
      50                 :            : /* Pointer set of potentially undefined ssa names, i.e.,
      51                 :            :    ssa names that are defined by phi with operands that
      52                 :            :    are not defined or potentially undefined.  */
      53                 :            : static hash_set<tree> *possibly_undefined_names = 0;
      54                 :            : 
      55                 :            : /* Bit mask handling macros.  */
      56                 :            : #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
      57                 :            : #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
      58                 :            : #define MASK_EMPTY(mask) (mask == 0)
      59                 :            : 
      60                 :            : /* Returns the first bit position (starting from LSB)
      61                 :            :    in mask that is non zero.  Returns -1 if the mask is empty.  */
      62                 :            : static int
      63                 :          0 : get_mask_first_set_bit (unsigned mask)
      64                 :            : {
      65                 :          0 :   int pos = 0;
      66                 :          0 :   if (mask == 0)
      67                 :            :     return -1;
      68                 :            : 
      69                 :          0 :   while ((mask & (1 << pos)) == 0)
      70                 :         59 :     pos++;
      71                 :            : 
      72                 :            :   return pos;
      73                 :            : }
      74                 :            : #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
      75                 :            : 
      76                 :            : /* Return true if T, an SSA_NAME, has an undefined value.  */
      77                 :            : static bool
      78                 :    4587780 : has_undefined_value_p (tree t)
      79                 :            : {
      80                 :    4587780 :   return (ssa_undefined_value_p (t)
      81                 :    4587780 :           || (possibly_undefined_names
      82                 :    4586380 :               && possibly_undefined_names->contains (t)));
      83                 :            : }
      84                 :            : 
      85                 :            : /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
      86                 :            :    is set on SSA_NAME_VAR.  */
      87                 :            : 
      88                 :            : static inline bool
      89                 :     545535 : uninit_undefined_value_p (tree t)
      90                 :            : {
      91                 :     545535 :   if (!has_undefined_value_p (t))
      92                 :            :     return false;
      93                 :        574 :   if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
      94                 :         21 :     return false;
      95                 :            :   return true;
      96                 :            : }
      97                 :            : 
      98                 :            : /* Emit warnings for uninitialized variables.  This is done in two passes.
      99                 :            : 
     100                 :            :    The first pass notices real uses of SSA names with undefined values.
     101                 :            :    Such uses are unconditionally uninitialized, and we can be certain that
     102                 :            :    such a use is a mistake.  This pass is run before most optimizations,
     103                 :            :    so that we catch as many as we can.
     104                 :            : 
     105                 :            :    The second pass follows PHI nodes to find uses that are potentially
     106                 :            :    uninitialized.  In this case we can't necessarily prove that the use
     107                 :            :    is really uninitialized.  This pass is run after most optimizations,
     108                 :            :    so that we thread as many jumps and possible, and delete as much dead
     109                 :            :    code as possible, in order to reduce false positives.  We also look
     110                 :            :    again for plain uninitialized variables, since optimization may have
     111                 :            :    changed conditionally uninitialized to unconditionally uninitialized.  */
     112                 :            : 
     113                 :            : /* Emit a warning for EXPR based on variable VAR at the point in the
     114                 :            :    program T, an SSA_NAME, is used being uninitialized.  The exact
     115                 :            :    warning text is in MSGID and DATA is the gimple stmt with info about
     116                 :            :    the location in source code.  When DATA is a GIMPLE_PHI, PHIARG_IDX
     117                 :            :    gives which argument of the phi node to take the location from.  WC
     118                 :            :    is the warning code.  */
     119                 :            : 
     120                 :            : static void
     121                 :    4043040 : warn_uninit (enum opt_code wc, tree t, tree expr, tree var,
     122                 :            :              const char *gmsgid, void *data, location_t phiarg_loc)
     123                 :            : {
     124                 :    4043040 :   gimple *context = (gimple *) data;
     125                 :    4043040 :   location_t location, cfun_loc;
     126                 :    4043040 :   expanded_location xloc, floc;
     127                 :            : 
     128                 :            :   /* Ignore COMPLEX_EXPR as initializing only a part of a complex
     129                 :            :      turns in a COMPLEX_EXPR with the not initialized part being
     130                 :            :      set to its previous (undefined) value.  */
     131                 :    4043040 :   if (is_gimple_assign (context)
     132                 :    4043040 :       && gimple_assign_rhs_code (context) == COMPLEX_EXPR)
     133                 :    4042750 :     return;
     134                 :    4042240 :   if (!has_undefined_value_p (t))
     135                 :            :     return;
     136                 :            : 
     137                 :            :   /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p
     138                 :            :      can return true if the def stmt of anonymous SSA_NAME is COMPLEX_EXPR
     139                 :            :      created for conversion from scalar to complex.  Use the underlying var of
     140                 :            :      the COMPLEX_EXPRs real part in that case.  See PR71581.  */
     141                 :        856 :   if (expr == NULL_TREE
     142                 :        856 :       && var == NULL_TREE
     143                 :          3 :       && SSA_NAME_VAR (t) == NULL_TREE
     144                 :          3 :       && is_gimple_assign (SSA_NAME_DEF_STMT (t))
     145                 :        859 :       && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (t)) == COMPLEX_EXPR)
     146                 :            :     {
     147                 :          3 :       tree v = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
     148                 :          3 :       if (TREE_CODE (v) == SSA_NAME
     149                 :          3 :           && has_undefined_value_p (v)
     150                 :          6 :           && zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t))))
     151                 :            :         {
     152                 :          3 :           expr = SSA_NAME_VAR (v);
     153                 :            :           var = expr;
     154                 :            :         }
     155                 :            :     }
     156                 :            : 
     157                 :        856 :   if (expr == NULL_TREE)
     158                 :            :     return;
     159                 :            : 
     160                 :            :   /* TREE_NO_WARNING either means we already warned, or the front end
     161                 :            :      wishes to suppress the warning.  */
     162                 :        856 :   if ((context
     163                 :        856 :        && (gimple_no_warning_p (context)
     164                 :        585 :            || (gimple_assign_single_p (context)
     165                 :        585 :                && TREE_NO_WARNING (gimple_assign_rhs1 (context)))))
     166                 :        792 :       || TREE_NO_WARNING (expr))
     167                 :            :     return;
     168                 :            : 
     169                 :        595 :   if (context != NULL && gimple_has_location (context))
     170                 :        283 :     location = gimple_location (context);
     171                 :         29 :   else if (phiarg_loc != UNKNOWN_LOCATION)
     172                 :            :     location = phiarg_loc;
     173                 :            :   else
     174                 :         26 :     location = DECL_SOURCE_LOCATION (var);
     175                 :        312 :   location = linemap_resolve_location (line_table, location,
     176                 :            :                                        LRK_SPELLING_LOCATION, NULL);
     177                 :        312 :   cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
     178                 :        312 :   xloc = expand_location (location);
     179                 :        312 :   floc = expand_location (cfun_loc);
     180                 :        602 :   auto_diagnostic_group d;
     181                 :        312 :   if (warning_at (location, wc, gmsgid, expr))
     182                 :            :     {
     183                 :        288 :       TREE_NO_WARNING (expr) = 1;
     184                 :            : 
     185                 :        288 :       if (location == DECL_SOURCE_LOCATION (var))
     186                 :         22 :         return;
     187                 :        266 :       if (xloc.file != floc.file
     188                 :        250 :           || linemap_location_before_p (line_table, location, cfun_loc)
     189                 :        479 :           || linemap_location_before_p (line_table, cfun->function_end_locus,
     190                 :            :                                         location))
     191                 :         60 :         inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
     192                 :            :     }
     193                 :            : }
     194                 :            : 
     195                 :            : struct check_defs_data
     196                 :            : {
     197                 :            :   /* If we found any may-defs besides must-def clobbers.  */
     198                 :            :   bool found_may_defs;
     199                 :            : };
     200                 :            : 
     201                 :            : /* Callback for walk_aliased_vdefs.  */
     202                 :            : 
     203                 :            : static bool
     204                 :    2344600 : check_defs (ao_ref *ref, tree vdef, void *data_)
     205                 :            : {
     206                 :    2344600 :   check_defs_data *data = (check_defs_data *)data_;
     207                 :    2344600 :   gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
     208                 :            :   /* If this is a clobber then if it is not a kill walk past it.  */
     209                 :    2344600 :   if (gimple_clobber_p (def_stmt))
     210                 :            :     {
     211                 :     103395 :       if (stmt_kills_ref_p (def_stmt, ref))
     212                 :            :         return true;
     213                 :     103387 :       return false;
     214                 :            :     }
     215                 :            :   /* Found a may-def on this path.  */
     216                 :    2241200 :   data->found_may_defs = true;
     217                 :    2241200 :   return true;
     218                 :            : }
     219                 :            : 
     220                 :            : static unsigned int
     221                 :     176089 : warn_uninitialized_vars (bool warn_possibly_uninitialized)
     222                 :            : {
     223                 :     176089 :   gimple_stmt_iterator gsi;
     224                 :     176089 :   basic_block bb;
     225                 :     176089 :   unsigned int vdef_cnt = 0;
     226                 :     176089 :   unsigned int oracle_cnt = 0;
     227                 :     176089 :   unsigned limit = 0;
     228                 :            : 
     229                 :    1971730 :   FOR_EACH_BB_FN (bb, cfun)
     230                 :            :     {
     231                 :    1795640 :       basic_block succ = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
     232                 :    1795640 :       bool always_executed = dominated_by_p (CDI_POST_DOMINATORS, succ, bb);
     233                 :   15483700 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     234                 :            :         {
     235                 :   11892400 :           gimple *stmt = gsi_stmt (gsi);
     236                 :   11892400 :           use_operand_p use_p;
     237                 :   11892400 :           ssa_op_iter op_iter;
     238                 :   11892400 :           tree use;
     239                 :            : 
     240                 :   11892400 :           if (is_gimple_debug (stmt))
     241                 :    6702510 :             continue;
     242                 :            : 
     243                 :            :           /* We only do data flow with SSA_NAMEs, so that's all we
     244                 :            :              can warn about.  */
     245                 :   12661400 :           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
     246                 :            :             {
     247                 :            :               /* BIT_INSERT_EXPR first operand should not be considered
     248                 :            :                  a use for the purpose of uninit warnings.  */
     249                 :    6527230 :               if (gassign *ass = dyn_cast <gassign *> (stmt))
     250                 :            :                 {
     251                 :    4390210 :                   if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
     252                 :    4390210 :                       && use_p->use == gimple_assign_rhs1_ptr (ass))
     253                 :          2 :                     continue;
     254                 :            :                 }
     255                 :    6527230 :               use = USE_FROM_PTR (use_p);
     256                 :    6527230 :               if (always_executed)
     257                 :    3196570 :                 warn_uninit (OPT_Wuninitialized, use, SSA_NAME_VAR (use),
     258                 :    1266000 :                              SSA_NAME_VAR (use),
     259                 :            :                              "%qD is used uninitialized in this function", stmt,
     260                 :            :                              UNKNOWN_LOCATION);
     261                 :    5261230 :               else if (warn_possibly_uninitialized)
     262                 :    6649930 :                 warn_uninit (OPT_Wmaybe_uninitialized, use, SSA_NAME_VAR (use),
     263                 :    2776950 :                              SSA_NAME_VAR (use),
     264                 :            :                              "%qD may be used uninitialized in this function",
     265                 :            :                              stmt, UNKNOWN_LOCATION);
     266                 :            :             }
     267                 :            : 
     268                 :            :           /* For limiting the alias walk below we count all
     269                 :            :              vdefs in the function.  */
     270                 :   11484700 :           if (gimple_vdef (stmt))
     271                 :    1559670 :             vdef_cnt++;
     272                 :            : 
     273                 :    6134220 :           if (gimple_assign_load_p (stmt)
     274                 :    7109010 :               && gimple_has_location (stmt))
     275                 :            :             {
     276                 :     944522 :               tree rhs = gimple_assign_rhs1 (stmt);
     277                 :     944522 :               tree lhs = gimple_assign_lhs (stmt);
     278                 :     944522 :               bool has_bit_insert = false;
     279                 :     944522 :               use_operand_p luse_p;
     280                 :     944522 :               imm_use_iterator liter;
     281                 :            : 
     282                 :     944522 :               if (TREE_NO_WARNING (rhs))
     283                 :     944313 :                 continue;
     284                 :            : 
     285                 :     942747 :               ao_ref ref;
     286                 :     942747 :               ao_ref_init (&ref, rhs);
     287                 :            : 
     288                 :            :               /* Do not warn if the base was marked so or this is a
     289                 :            :                  hard register var.  */
     290                 :     942747 :               tree base = ao_ref_base (&ref);
     291                 :     944807 :               if ((VAR_P (base)
     292                 :     424287 :                    && DECL_HARD_REGISTER (base))
     293                 :    1367020 :                   || TREE_NO_WARNING (base))
     294                 :       2060 :                 continue;
     295                 :            : 
     296                 :            :               /* Do not warn if the access is fully outside of the
     297                 :            :                  variable.  */
     298                 :     940687 :               poly_int64 decl_size;
     299                 :     940763 :               if (DECL_P (base)
     300                 :     436851 :                   && known_size_p (ref.size)
     301                 :    1377540 :                   && ((known_eq (ref.max_size, ref.size)
     302                 :     364606 :                        && known_le (ref.offset + ref.size, 0))
     303                 :     436843 :                       || (known_ge (ref.offset, 0)
     304                 :     436843 :                           && DECL_SIZE (base)
     305                 :     422011 :                           && poly_int_tree_p (DECL_SIZE (base), &decl_size)
     306                 :     422010 :                           && known_le (decl_size, ref.offset))))
     307                 :         76 :                 continue;
     308                 :            : 
     309                 :            :               /* Do not warn if the access is then used for a BIT_INSERT_EXPR. */
     310                 :     940611 :               if (TREE_CODE (lhs) == SSA_NAME)
     311                 :    2282610 :                 FOR_EACH_IMM_USE_FAST (luse_p, liter, lhs)
     312                 :            :                   {
     313                 :    1349920 :                     gimple *use_stmt = USE_STMT (luse_p);
     314                 :            :                     /* BIT_INSERT_EXPR first operand should not be considered
     315                 :            :                        a use for the purpose of uninit warnings.  */
     316                 :    2016010 :                     if (gassign *ass = dyn_cast <gassign *> (use_stmt))
     317                 :            :                       {
     318                 :     666089 :                         if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
     319                 :     666089 :                             && luse_p->use == gimple_assign_rhs1_ptr (ass))
     320                 :            :                           {
     321                 :            :                             has_bit_insert = true;
     322                 :            :                             break;
     323                 :            :                           }
     324                 :            :                       }
     325                 :            :                   }
     326                 :     932689 :               if (has_bit_insert)
     327                 :          0 :                 continue;
     328                 :            : 
     329                 :            :               /* Limit the walking to a constant number of stmts after
     330                 :            :                  we overcommit quadratic behavior for small functions
     331                 :            :                  and O(n) behavior.  */
     332                 :     940611 :               if (oracle_cnt > 128 * 128
     333                 :      26689 :                   && oracle_cnt > vdef_cnt * 2)
     334                 :      26689 :                 limit = 32;
     335                 :     940611 :               check_defs_data data;
     336                 :     940611 :               bool fentry_reached = false;
     337                 :     940611 :               data.found_may_defs = false;
     338                 :     940611 :               use = gimple_vuse (stmt);
     339                 :     940611 :               int res = walk_aliased_vdefs (&ref, use,
     340                 :            :                                             check_defs, &data, NULL,
     341                 :            :                                             &fentry_reached, limit);
     342                 :     940611 :               if (res == -1)
     343                 :            :                 {
     344                 :      24476 :                   oracle_cnt += limit;
     345                 :      24476 :                   continue;
     346                 :            :                 }
     347                 :     916135 :               oracle_cnt += res;
     348                 :     916135 :               if (data.found_may_defs)
     349                 :     662390 :                 continue;
     350                 :            :               /* Do not warn if it can be initialized outside this function.
     351                 :            :                  If we did not reach function entry then we found killing
     352                 :            :                  clobbers on all paths to entry.  */
     353                 :     507281 :               if (fentry_reached
     354                 :            :                   /* ???  We'd like to use ref_may_alias_global_p but that
     355                 :            :                      excludes global readonly memory and thus we get bougs
     356                 :            :                      warnings from p = cond ? "a" : "b" for example.  */
     357                 :     253745 :                   && (!VAR_P (base)
     358                 :      83321 :                       || is_global_var (base)))
     359                 :     253536 :                 continue;
     360                 :            : 
     361                 :            :               /* We didn't find any may-defs so on all paths either
     362                 :            :                  reached function entry or a killing clobber.  */
     363                 :        209 :               location_t location
     364                 :        209 :                 = linemap_resolve_location (line_table, gimple_location (stmt),
     365                 :            :                                             LRK_SPELLING_LOCATION, NULL);
     366                 :        209 :               if (always_executed)
     367                 :            :                 {
     368                 :         51 :                   if (warning_at (location, OPT_Wuninitialized,
     369                 :            :                                   "%qE is used uninitialized in this function",
     370                 :            :                                   rhs))
     371                 :            :                     /* ???  This is only effective for decls as in
     372                 :            :                        gcc.dg/uninit-B-O0.c.  Avoid doing this for
     373                 :            :                        maybe-uninit uses as it may hide important
     374                 :            :                        locations.  */
     375                 :         51 :                     TREE_NO_WARNING (rhs) = 1;
     376                 :            :                 }
     377                 :        158 :               else if (warn_possibly_uninitialized)
     378                 :        155 :                 warning_at (location, OPT_Wmaybe_uninitialized,
     379                 :            :                             "%qE may be used uninitialized in this function",
     380                 :            :                             rhs);
     381                 :            :             }
     382                 :            :         }
     383                 :            :     }
     384                 :            : 
     385                 :     176089 :   return 0;
     386                 :            : }
     387                 :            : 
     388                 :            : /* Checks if the operand OPND of PHI is defined by
     389                 :            :    another phi with one operand defined by this PHI,
     390                 :            :    but the rest operands are all defined.  If yes,
     391                 :            :    returns true to skip this operand as being
     392                 :            :    redundant.  Can be enhanced to be more general.  */
     393                 :            : 
     394                 :            : static bool
     395                 :        285 : can_skip_redundant_opnd (tree opnd, gimple *phi)
     396                 :            : {
     397                 :        285 :   gimple *op_def;
     398                 :        285 :   tree phi_def;
     399                 :        285 :   int i, n;
     400                 :            : 
     401                 :        285 :   phi_def = gimple_phi_result (phi);
     402                 :        285 :   op_def = SSA_NAME_DEF_STMT (opnd);
     403                 :        285 :   if (gimple_code (op_def) != GIMPLE_PHI)
     404                 :            :     return false;
     405                 :         19 :   n = gimple_phi_num_args (op_def);
     406                 :         29 :   for (i = 0; i < n; ++i)
     407                 :            :     {
     408                 :         29 :       tree op = gimple_phi_arg_def (op_def, i);
     409                 :         29 :       if (TREE_CODE (op) != SSA_NAME)
     410                 :          0 :         continue;
     411                 :         29 :       if (op != phi_def && uninit_undefined_value_p (op))
     412                 :            :         return false;
     413                 :            :     }
     414                 :            : 
     415                 :            :   return true;
     416                 :            : }
     417                 :            : 
     418                 :            : /* Returns a bit mask holding the positions of arguments in PHI
     419                 :            :    that have empty (or possibly empty) definitions.  */
     420                 :            : 
     421                 :            : static unsigned
     422                 :        205 : compute_uninit_opnds_pos (gphi *phi)
     423                 :            : {
     424                 :        205 :   size_t i, n;
     425                 :        205 :   unsigned uninit_opnds = 0;
     426                 :            : 
     427                 :        205 :   n = gimple_phi_num_args (phi);
     428                 :            :   /* Bail out for phi with too many args.  */
     429                 :        205 :   if (n > max_phi_args)
     430                 :            :     return 0;
     431                 :            : 
     432                 :        862 :   for (i = 0; i < n; ++i)
     433                 :            :     {
     434                 :        657 :       tree op = gimple_phi_arg_def (phi, i);
     435                 :        657 :       if (TREE_CODE (op) == SSA_NAME
     436                 :        597 :           && uninit_undefined_value_p (op)
     437                 :        942 :           && !can_skip_redundant_opnd (op, phi))
     438                 :            :         {
     439                 :        285 :           if (cfun->has_nonlocal_label || cfun->calls_setjmp)
     440                 :            :             {
     441                 :            :               /* Ignore SSA_NAMEs that appear on abnormal edges
     442                 :            :                  somewhere.  */
     443                 :         35 :               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
     444                 :         35 :                 continue;
     445                 :            :             }
     446                 :        250 :           MASK_SET_BIT (uninit_opnds, i);
     447                 :            :         }
     448                 :            :     }
     449                 :            :   return uninit_opnds;
     450                 :            : }
     451                 :            : 
     452                 :            : /* Find the immediate postdominator PDOM of the specified
     453                 :            :    basic block BLOCK.  */
     454                 :            : 
     455                 :            : static inline basic_block
     456                 :      32664 : find_pdom (basic_block block)
     457                 :            : {
     458                 :      32664 :   if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
     459                 :            :     return EXIT_BLOCK_PTR_FOR_FN (cfun);
     460                 :            :   else
     461                 :            :     {
     462                 :      32664 :       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
     463                 :      32664 :       if (!bb)
     464                 :          0 :         return EXIT_BLOCK_PTR_FOR_FN (cfun);
     465                 :            :       return bb;
     466                 :            :     }
     467                 :            : }
     468                 :            : 
     469                 :            : /* Find the immediate DOM of the specified basic block BLOCK.  */
     470                 :            : 
     471                 :            : static inline basic_block
     472                 :         64 : find_dom (basic_block block)
     473                 :            : {
     474                 :         64 :   if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     475                 :            :     return ENTRY_BLOCK_PTR_FOR_FN (cfun);
     476                 :            :   else
     477                 :            :     {
     478                 :         64 :       basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
     479                 :         64 :       if (!bb)
     480                 :          0 :         return ENTRY_BLOCK_PTR_FOR_FN (cfun);
     481                 :            :       return bb;
     482                 :            :     }
     483                 :            : }
     484                 :            : 
     485                 :            : /* Returns true if BB1 is postdominating BB2 and BB1 is
     486                 :            :    not a loop exit bb.  The loop exit bb check is simple and does
     487                 :            :    not cover all cases.  */
     488                 :            : 
     489                 :            : static bool
     490                 :      63051 : is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
     491                 :            : {
     492                 :      63051 :   if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
     493                 :            :     return false;
     494                 :            : 
     495                 :      31155 :   if (single_pred_p (bb1) && !single_succ_p (bb2))
     496                 :       1385 :     return false;
     497                 :            : 
     498                 :            :   return true;
     499                 :            : }
     500                 :            : 
     501                 :            : /* Find the closest postdominator of a specified BB, which is control
     502                 :            :    equivalent to BB.  */
     503                 :            : 
     504                 :            : static inline basic_block
     505                 :        223 : find_control_equiv_block (basic_block bb)
     506                 :            : {
     507                 :        223 :   basic_block pdom;
     508                 :            : 
     509                 :        223 :   pdom = find_pdom (bb);
     510                 :            : 
     511                 :            :   /* Skip the postdominating bb that is also loop exit.  */
     512                 :        223 :   if (!is_non_loop_exit_postdominating (pdom, bb))
     513                 :            :     return NULL;
     514                 :            : 
     515                 :        217 :   if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
     516                 :        158 :     return pdom;
     517                 :            : 
     518                 :            :   return NULL;
     519                 :            : }
     520                 :            : 
     521                 :            : #define MAX_NUM_CHAINS 8
     522                 :            : #define MAX_CHAIN_LEN 5
     523                 :            : #define MAX_POSTDOM_CHECK 8
     524                 :            : #define MAX_SWITCH_CASES 40
     525                 :            : 
     526                 :            : /* Computes the control dependence chains (paths of edges)
     527                 :            :    for DEP_BB up to the dominating basic block BB (the head node of a
     528                 :            :    chain should be dominated by it).  CD_CHAINS is pointer to an
     529                 :            :    array holding the result chains.  CUR_CD_CHAIN is the current
     530                 :            :    chain being computed.  *NUM_CHAINS is total number of chains.  The
     531                 :            :    function returns true if the information is successfully computed,
     532                 :            :    return false if there is no control dependence or not computed.  */
     533                 :            : 
     534                 :            : static bool
     535                 :      33147 : compute_control_dep_chain (basic_block bb, basic_block dep_bb,
     536                 :            :                            vec<edge> *cd_chains,
     537                 :            :                            size_t *num_chains,
     538                 :            :                            vec<edge> *cur_cd_chain,
     539                 :            :                            int *num_calls)
     540                 :            : {
     541                 :      33147 :   edge_iterator ei;
     542                 :      33147 :   edge e;
     543                 :      33147 :   size_t i;
     544                 :      33147 :   bool found_cd_chain = false;
     545                 :      33147 :   size_t cur_chain_len = 0;
     546                 :            : 
     547                 :      33147 :   if (*num_calls > param_uninit_control_dep_attempts)
     548                 :            :     return false;
     549                 :      33147 :   ++*num_calls;
     550                 :            : 
     551                 :            :   /* Could use a set instead.  */
     552                 :      33147 :   cur_chain_len = cur_cd_chain->length ();
     553                 :      33147 :   if (cur_chain_len > MAX_CHAIN_LEN)
     554                 :            :     return false;
     555                 :            : 
     556                 :     105063 :   for (i = 0; i < cur_chain_len; i++)
     557                 :            :     {
     558                 :      85276 :       edge e = (*cur_cd_chain)[i];
     559                 :            :       /* Cycle detected.  */
     560                 :      85276 :       if (e->src == bb)
     561                 :            :         return false;
     562                 :            :     }
     563                 :            : 
     564                 :      50246 :   FOR_EACH_EDGE (e, ei, bb->succs)
     565                 :            :     {
     566                 :      30459 :       basic_block cd_bb;
     567                 :      30459 :       int post_dom_check = 0;
     568                 :      30459 :       if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
     569                 :          0 :         continue;
     570                 :            : 
     571                 :      30459 :       cd_bb = e->dest;
     572                 :      30459 :       cur_cd_chain->safe_push (e);
     573                 :      62614 :       while (!is_non_loop_exit_postdominating (cd_bb, bb))
     574                 :            :         {
     575                 :      33124 :           if (cd_bb == dep_bb)
     576                 :            :             {
     577                 :            :               /* Found a direct control dependence.  */
     578                 :        305 :               if (*num_chains < MAX_NUM_CHAINS)
     579                 :            :                 {
     580                 :        305 :                   cd_chains[*num_chains] = cur_cd_chain->copy ();
     581                 :        305 :                   (*num_chains)++;
     582                 :            :                 }
     583                 :            :               found_cd_chain = true;
     584                 :            :               /* Check path from next edge.  */
     585                 :            :               break;
     586                 :            :             }
     587                 :            : 
     588                 :            :           /* Now check if DEP_BB is indirectly control dependent on BB.  */
     589                 :      32819 :           if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, num_chains,
     590                 :            :                                          cur_cd_chain, num_calls))
     591                 :            :             {
     592                 :            :               found_cd_chain = true;
     593                 :            :               break;
     594                 :            :             }
     595                 :            : 
     596                 :      32441 :           cd_bb = find_pdom (cd_bb);
     597                 :      32441 :           post_dom_check++;
     598                 :      32441 :           if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
     599                 :      32155 :               || post_dom_check > MAX_POSTDOM_CHECK)
     600                 :            :             break;
     601                 :            :         }
     602                 :      30459 :       cur_cd_chain->pop ();
     603                 :      30459 :       gcc_assert (cur_cd_chain->length () == cur_chain_len);
     604                 :            :     }
     605                 :      39574 :   gcc_assert (cur_cd_chain->length () == cur_chain_len);
     606                 :            : 
     607                 :            :   return found_cd_chain;
     608                 :            : }
     609                 :            : 
     610                 :            : /* The type to represent a simple predicate.  */
     611                 :            : 
     612                 :            : struct pred_info
     613                 :            : {
     614                 :            :   tree pred_lhs;
     615                 :            :   tree pred_rhs;
     616                 :            :   enum tree_code cond_code;
     617                 :            :   bool invert;
     618                 :            : };
     619                 :            : 
     620                 :            : /* The type to represent a sequence of predicates grouped
     621                 :            :   with .AND. operation.  */
     622                 :            : 
     623                 :            : typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
     624                 :            : 
     625                 :            : /* The type to represent a sequence of pred_chains grouped
     626                 :            :   with .OR. operation.  */
     627                 :            : 
     628                 :            : typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
     629                 :            : 
     630                 :            : /* Converts the chains of control dependence edges into a set of
     631                 :            :    predicates.  A control dependence chain is represented by a vector
     632                 :            :    edges.  DEP_CHAINS points to an array of dependence chains.
     633                 :            :    NUM_CHAINS is the size of the chain array.  One edge in a dependence
     634                 :            :    chain is mapped to predicate expression represented by pred_info
     635                 :            :    type.  One dependence chain is converted to a composite predicate that
     636                 :            :    is the result of AND operation of pred_info mapped to each edge.
     637                 :            :    A composite predicate is presented by a vector of pred_info.  On
     638                 :            :    return, *PREDS points to the resulting array of composite predicates.
     639                 :            :    *NUM_PREDS is the number of composite predictes.  */
     640                 :            : 
     641                 :            : static bool
     642                 :        301 : convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
     643                 :            :                                       size_t num_chains,
     644                 :            :                                       pred_chain_union *preds)
     645                 :            : {
     646                 :        301 :   bool has_valid_pred = false;
     647                 :        301 :   size_t i, j;
     648                 :        301 :   if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
     649                 :            :     return false;
     650                 :            : 
     651                 :            :   /* Now convert the control dep chain into a set
     652                 :            :      of predicates.  */
     653                 :        283 :   preds->reserve (num_chains);
     654                 :            : 
     655                 :        554 :   for (i = 0; i < num_chains; i++)
     656                 :            :     {
     657                 :        303 :       vec<edge> one_cd_chain = dep_chains[i];
     658                 :            : 
     659                 :        303 :       has_valid_pred = false;
     660                 :        303 :       pred_chain t_chain = vNULL;
     661                 :       1868 :       for (j = 0; j < one_cd_chain.length (); j++)
     662                 :            :         {
     663                 :        653 :           gimple *cond_stmt;
     664                 :        653 :           gimple_stmt_iterator gsi;
     665                 :        653 :           basic_block guard_bb;
     666                 :        653 :           pred_info one_pred;
     667                 :        653 :           edge e;
     668                 :            : 
     669                 :        653 :           e = one_cd_chain[j];
     670                 :        653 :           guard_bb = e->src;
     671                 :        653 :           gsi = gsi_last_bb (guard_bb);
     672                 :            :           /* Ignore empty forwarder blocks.  */
     673                 :        653 :           if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
     674                 :        124 :             continue;
     675                 :            :           /* An empty basic block here is likely a PHI, and is not one
     676                 :            :              of the cases we handle below.  */
     677                 :        561 :           if (gsi_end_p (gsi))
     678                 :            :             {
     679                 :            :               has_valid_pred = false;
     680                 :         22 :               break;
     681                 :            :             }
     682                 :        559 :           cond_stmt = gsi_stmt (gsi);
     683                 :        559 :           if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
     684                 :            :             /* Ignore EH edge.  Can add assertion on the other edge's flag.  */
     685                 :         28 :             continue;
     686                 :            :           /* Skip if there is essentially one succesor.  */
     687                 :        531 :           if (EDGE_COUNT (e->src->succs) == 2)
     688                 :            :             {
     689                 :        511 :               edge e1;
     690                 :        511 :               edge_iterator ei1;
     691                 :        511 :               bool skip = false;
     692                 :            : 
     693                 :       1525 :               FOR_EACH_EDGE (e1, ei1, e->src->succs)
     694                 :            :                 {
     695                 :       1018 :                   if (EDGE_COUNT (e1->dest->succs) == 0)
     696                 :            :                     {
     697                 :            :                       skip = true;
     698                 :            :                       break;
     699                 :            :                     }
     700                 :            :                 }
     701                 :        511 :               if (skip)
     702                 :          4 :                 continue;
     703                 :            :             }
     704                 :        527 :           if (gimple_code (cond_stmt) == GIMPLE_COND)
     705                 :            :             {
     706                 :        507 :               one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
     707                 :        507 :               one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
     708                 :        507 :               one_pred.cond_code = gimple_cond_code (cond_stmt);
     709                 :        507 :               one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
     710                 :        507 :               t_chain.safe_push (one_pred);
     711                 :        507 :               has_valid_pred = true;
     712                 :            :             }
     713                 :         20 :           else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
     714                 :            :             {
     715                 :            :               /* Avoid quadratic behavior.  */
     716                 :         20 :               if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES)
     717                 :            :                 {
     718                 :            :                   has_valid_pred = false;
     719                 :            :                   break;
     720                 :            :                 }
     721                 :            :               /* Find the case label.  */
     722                 :            :               tree l = NULL_TREE;
     723                 :            :               unsigned idx;
     724                 :          0 :               for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx)
     725                 :            :                 {
     726                 :          0 :                   tree tl = gimple_switch_label (gs, idx);
     727                 :          0 :                   if (e->dest == label_to_block (cfun, CASE_LABEL (tl)))
     728                 :            :                     {
     729                 :          0 :                       if (!l)
     730                 :            :                         l = tl;
     731                 :            :                       else
     732                 :            :                         {
     733                 :            :                           l = NULL_TREE;
     734                 :            :                           break;
     735                 :            :                         }
     736                 :            :                     }
     737                 :            :                 }
     738                 :            :               /* If more than one label reaches this block or the case
     739                 :            :                  label doesn't have a single value (like the default one)
     740                 :            :                  fail.  */
     741                 :          0 :               if (!l
     742                 :          0 :                   || !CASE_LOW (l)
     743                 :          0 :                   || (CASE_HIGH (l)
     744                 :          0 :                       && !operand_equal_p (CASE_LOW (l), CASE_HIGH (l), 0)))
     745                 :            :                 {
     746                 :            :                   has_valid_pred = false;
     747                 :            :                   break;
     748                 :            :                 }
     749                 :          0 :               one_pred.pred_lhs = gimple_switch_index (gs);
     750                 :          0 :               one_pred.pred_rhs = CASE_LOW (l);
     751                 :          0 :               one_pred.cond_code = EQ_EXPR;
     752                 :          0 :               one_pred.invert = false;
     753                 :          0 :               t_chain.safe_push (one_pred);
     754                 :          0 :               has_valid_pred = true;
     755                 :            :             }
     756                 :            :           else
     757                 :            :             {
     758                 :            :               has_valid_pred = false;
     759                 :            :               break;
     760                 :            :             }
     761                 :            :         }
     762                 :            : 
     763                 :        303 :       if (!has_valid_pred)
     764                 :            :         break;
     765                 :            :       else
     766                 :        271 :         preds->safe_push (t_chain);
     767                 :            :     }
     768                 :            :   return has_valid_pred;
     769                 :            : }
     770                 :            : 
     771                 :            : /* Computes all control dependence chains for USE_BB.  The control
     772                 :            :    dependence chains are then converted to an array of composite
     773                 :            :    predicates pointed to by PREDS.  PHI_BB is the basic block of
     774                 :            :    the phi whose result is used in USE_BB.  */
     775                 :            : 
     776                 :            : static bool
     777                 :        151 : find_predicates (pred_chain_union *preds,
     778                 :            :                  basic_block phi_bb,
     779                 :            :                  basic_block use_bb)
     780                 :            : {
     781                 :        151 :   size_t num_chains = 0, i;
     782                 :        151 :   int num_calls = 0;
     783                 :        151 :   vec<edge> dep_chains[MAX_NUM_CHAINS];
     784                 :        151 :   auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
     785                 :        151 :   bool has_valid_pred = false;
     786                 :        151 :   basic_block cd_root = 0;
     787                 :            : 
     788                 :            :   /* First find the closest bb that is control equivalent to PHI_BB
     789                 :            :      that also dominates USE_BB.  */
     790                 :        151 :   cd_root = phi_bb;
     791                 :        223 :   while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
     792                 :            :     {
     793                 :        223 :       basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
     794                 :        223 :       if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
     795                 :            :         cd_root = ctrl_eq_bb;
     796                 :            :       else
     797                 :            :         break;
     798                 :            :     }
     799                 :            : 
     800                 :        151 :   compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
     801                 :            :                              &cur_chain, &num_calls);
     802                 :            : 
     803                 :        151 :   has_valid_pred
     804                 :        151 :     = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
     805                 :        297 :   for (i = 0; i < num_chains; i++)
     806                 :        292 :     dep_chains[i].release ();
     807                 :        151 :   return has_valid_pred;
     808                 :            : }
     809                 :            : 
     810                 :            : /* Computes the set of incoming edges of PHI that have non empty
     811                 :            :    definitions of a phi chain.  The collection will be done
     812                 :            :    recursively on operands that are defined by phis.  CD_ROOT
     813                 :            :    is the control dependence root.  *EDGES holds the result, and
     814                 :            :    VISITED_PHIS is a pointer set for detecting cycles.  */
     815                 :            : 
     816                 :            : static void
     817                 :         91 : collect_phi_def_edges (gphi *phi, basic_block cd_root,
     818                 :            :                        auto_vec<edge> *edges,
     819                 :            :                        hash_set<gimple *> *visited_phis)
     820                 :            : {
     821                 :         91 :   size_t i, n;
     822                 :         91 :   edge opnd_edge;
     823                 :         91 :   tree opnd;
     824                 :            : 
     825                 :         91 :   if (visited_phis->add (phi))
     826                 :         10 :     return;
     827                 :            : 
     828                 :         81 :   n = gimple_phi_num_args (phi);
     829                 :        255 :   for (i = 0; i < n; i++)
     830                 :            :     {
     831                 :        174 :       opnd_edge = gimple_phi_arg_edge (phi, i);
     832                 :        174 :       opnd = gimple_phi_arg_def (phi, i);
     833                 :            : 
     834                 :        174 :       if (TREE_CODE (opnd) != SSA_NAME)
     835                 :            :         {
     836                 :          1 :           if (dump_file && (dump_flags & TDF_DETAILS))
     837                 :            :             {
     838                 :          0 :               fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int) i);
     839                 :          0 :               print_gimple_stmt (dump_file, phi, 0);
     840                 :            :             }
     841                 :          1 :           edges->safe_push (opnd_edge);
     842                 :            :         }
     843                 :            :       else
     844                 :            :         {
     845                 :        173 :           gimple *def = SSA_NAME_DEF_STMT (opnd);
     846                 :            : 
     847                 :        173 :           if (gimple_code (def) == GIMPLE_PHI
     848                 :        173 :               && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
     849                 :         27 :             collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
     850                 :            :                                    visited_phis);
     851                 :        146 :           else if (!uninit_undefined_value_p (opnd))
     852                 :            :             {
     853                 :         70 :               if (dump_file && (dump_flags & TDF_DETAILS))
     854                 :            :                 {
     855                 :          0 :                   fprintf (dump_file, "\n[CHECK] Found def edge %d in ",
     856                 :            :                            (int) i);
     857                 :          0 :                   print_gimple_stmt (dump_file, phi, 0);
     858                 :            :                 }
     859                 :         70 :               edges->safe_push (opnd_edge);
     860                 :            :             }
     861                 :            :         }
     862                 :            :     }
     863                 :            : }
     864                 :            : 
     865                 :            : /* For each use edge of PHI, computes all control dependence chains.
     866                 :            :    The control dependence chains are then converted to an array of
     867                 :            :    composite predicates pointed to by PREDS.  */
     868                 :            : 
     869                 :            : static bool
     870                 :         64 : find_def_preds (pred_chain_union *preds, gphi *phi)
     871                 :            : {
     872                 :         64 :   size_t num_chains = 0, i, n;
     873                 :         64 :   vec<edge> dep_chains[MAX_NUM_CHAINS];
     874                 :         64 :   auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
     875                 :        128 :   auto_vec<edge> def_edges;
     876                 :         64 :   bool has_valid_pred = false;
     877                 :         64 :   basic_block phi_bb, cd_root = 0;
     878                 :            : 
     879                 :         64 :   phi_bb = gimple_bb (phi);
     880                 :            :   /* First find the closest dominating bb to be
     881                 :            :      the control dependence root.  */
     882                 :         64 :   cd_root = find_dom (phi_bb);
     883                 :         64 :   if (!cd_root)
     884                 :            :     return false;
     885                 :            : 
     886                 :        128 :   hash_set<gimple *> visited_phis;
     887                 :         64 :   collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
     888                 :            : 
     889                 :         64 :   n = def_edges.length ();
     890                 :         64 :   if (n == 0)
     891                 :            :     return false;
     892                 :            : 
     893                 :        135 :   for (i = 0; i < n; i++)
     894                 :            :     {
     895                 :         71 :       size_t prev_nc, j;
     896                 :         71 :       int num_calls = 0;
     897                 :         71 :       edge opnd_edge;
     898                 :            : 
     899                 :         71 :       opnd_edge = def_edges[i];
     900                 :         71 :       prev_nc = num_chains;
     901                 :         71 :       compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
     902                 :            :                                  &num_chains, &cur_chain, &num_calls);
     903                 :            : 
     904                 :            :       /* Now update the newly added chains with
     905                 :            :          the phi operand edge:  */
     906                 :         71 :       if (EDGE_COUNT (opnd_edge->src->succs) > 1)
     907                 :            :         {
     908                 :          0 :           if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
     909                 :          0 :             dep_chains[num_chains++] = vNULL;
     910                 :          0 :           for (j = prev_nc; j < num_chains; j++)
     911                 :          0 :             dep_chains[j].safe_push (opnd_edge);
     912                 :            :         }
     913                 :            :     }
     914                 :            : 
     915                 :         64 :   has_valid_pred
     916                 :         64 :     = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
     917                 :        131 :   for (i = 0; i < num_chains; i++)
     918                 :        134 :     dep_chains[i].release ();
     919                 :            :   return has_valid_pred;
     920                 :            : }
     921                 :            : 
     922                 :            : /* Dump a pred_info.  */
     923                 :            : 
     924                 :            : static void
     925                 :          0 : dump_pred_info (pred_info one_pred)
     926                 :            : {
     927                 :          0 :   if (one_pred.invert)
     928                 :          0 :     fprintf (dump_file, " (.NOT.) ");
     929                 :          0 :   print_generic_expr (dump_file, one_pred.pred_lhs);
     930                 :          0 :   fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
     931                 :          0 :   print_generic_expr (dump_file, one_pred.pred_rhs);
     932                 :          0 : }
     933                 :            : 
     934                 :            : /* Dump a pred_chain.  */
     935                 :            : 
     936                 :            : static void
     937                 :          0 : dump_pred_chain (pred_chain one_pred_chain)
     938                 :            : {
     939                 :          0 :   size_t np = one_pred_chain.length ();
     940                 :          0 :   for (size_t j = 0; j < np; j++)
     941                 :            :     {
     942                 :          0 :       dump_pred_info (one_pred_chain[j]);
     943                 :          0 :       if (j < np - 1)
     944                 :          0 :         fprintf (dump_file, " (.AND.) ");
     945                 :            :       else
     946                 :          0 :         fprintf (dump_file, "\n");
     947                 :            :     }
     948                 :          0 : }
     949                 :            : 
     950                 :            : /* Dumps the predicates (PREDS) for USESTMT.  */
     951                 :            : 
     952                 :            : static void
     953                 :          0 : dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg)
     954                 :            : {
     955                 :          0 :   fprintf (dump_file, "%s", msg);
     956                 :          0 :   if (usestmt)
     957                 :            :     {
     958                 :          0 :       print_gimple_stmt (dump_file, usestmt, 0);
     959                 :          0 :       fprintf (dump_file, "is guarded by :\n\n");
     960                 :            :     }
     961                 :          0 :   size_t num_preds = preds.length ();
     962                 :          0 :   for (size_t i = 0; i < num_preds; i++)
     963                 :            :     {
     964                 :          0 :       dump_pred_chain (preds[i]);
     965                 :          0 :       if (i < num_preds - 1)
     966                 :          0 :         fprintf (dump_file, "(.OR.)\n");
     967                 :            :       else
     968                 :          0 :         fprintf (dump_file, "\n\n");
     969                 :            :     }
     970                 :          0 : }
     971                 :            : 
     972                 :            : /* Destroys the predicate set *PREDS.  */
     973                 :            : 
     974                 :            : static void
     975                 :        634 : destroy_predicate_vecs (pred_chain_union *preds)
     976                 :            : {
     977                 :        634 :   size_t i;
     978                 :            : 
     979                 :        634 :   size_t n = preds->length ();
     980                 :       1150 :   for (i = 0; i < n; i++)
     981                 :        873 :     (*preds)[i].release ();
     982                 :        634 :   preds->release ();
     983                 :        634 : }
     984                 :            : 
     985                 :            : /* Computes the 'normalized' conditional code with operand
     986                 :            :    swapping and condition inversion.  */
     987                 :            : 
     988                 :            : static enum tree_code
     989                 :         62 : get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert)
     990                 :            : {
     991                 :         62 :   enum tree_code tc = orig_cmp_code;
     992                 :            : 
     993                 :         62 :   if (swap_cond)
     994                 :          0 :     tc = swap_tree_comparison (orig_cmp_code);
     995                 :         62 :   if (invert)
     996                 :         28 :     tc = invert_tree_comparison (tc, false);
     997                 :            : 
     998                 :         62 :   switch (tc)
     999                 :            :     {
    1000                 :         62 :     case LT_EXPR:
    1001                 :         62 :     case LE_EXPR:
    1002                 :         62 :     case GT_EXPR:
    1003                 :         62 :     case GE_EXPR:
    1004                 :         62 :     case EQ_EXPR:
    1005                 :         62 :     case NE_EXPR:
    1006                 :         62 :       break;
    1007                 :            :     default:
    1008                 :            :       return ERROR_MARK;
    1009                 :            :     }
    1010                 :         62 :   return tc;
    1011                 :            : }
    1012                 :            : 
    1013                 :            : /* Returns whether VAL CMPC BOUNDARY is true.  */
    1014                 :            : 
    1015                 :            : static bool
    1016                 :         60 : is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
    1017                 :            : {
    1018                 :         60 :   bool inverted = false;
    1019                 :         60 :   bool result;
    1020                 :            : 
    1021                 :            :   /* Only handle integer constant here.  */
    1022                 :         60 :   if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
    1023                 :            :     return true;
    1024                 :            : 
    1025                 :         60 :   if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
    1026                 :            :     {
    1027                 :         26 :       cmpc = invert_tree_comparison (cmpc, false);
    1028                 :         26 :       inverted = true;
    1029                 :            :     }
    1030                 :            : 
    1031                 :         60 :   if (cmpc == EQ_EXPR)
    1032                 :         30 :     result = tree_int_cst_equal (val, boundary);
    1033                 :         30 :   else if (cmpc == LT_EXPR)
    1034                 :          2 :     result = tree_int_cst_lt (val, boundary);
    1035                 :            :   else
    1036                 :            :     {
    1037                 :         28 :       gcc_assert (cmpc == LE_EXPR);
    1038                 :         28 :       result = tree_int_cst_le (val, boundary);
    1039                 :            :     }
    1040                 :            : 
    1041                 :         60 :   if (inverted)
    1042                 :         26 :     result ^= 1;
    1043                 :            : 
    1044                 :            :   return result;
    1045                 :            : }
    1046                 :            : 
    1047                 :            : /* Returns whether VAL satisfies (x CMPC BOUNDARY) predicate.  CMPC can be
    1048                 :            :    either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and the like),
    1049                 :            :    or BIT_AND_EXPR.  EXACT_P is only meaningful for the latter.  It modifies the
    1050                 :            :    question from whether VAL & BOUNDARY != 0 to whether VAL & BOUNDARY == VAL.
    1051                 :            :    For other values of CMPC, EXACT_P is ignored.  */
    1052                 :            : 
    1053                 :            : static bool
    1054                 :         38 : value_sat_pred_p (tree val, tree boundary, enum tree_code cmpc,
    1055                 :            :                   bool exact_p = false)
    1056                 :            : {
    1057                 :         38 :   if (cmpc != BIT_AND_EXPR)
    1058                 :         29 :     return is_value_included_in (val, boundary, cmpc);
    1059                 :            : 
    1060                 :          9 :   wide_int andw = wi::to_wide (val) & wi::to_wide (boundary);
    1061                 :          9 :   if (exact_p)
    1062                 :          2 :     return andw == wi::to_wide (val);
    1063                 :            :   else
    1064                 :         14 :     return andw.to_uhwi ();
    1065                 :            : }
    1066                 :            : 
    1067                 :            : /* Returns true if PRED is common among all the predicate
    1068                 :            :    chains (PREDS) (and therefore can be factored out).
    1069                 :            :    NUM_PRED_CHAIN is the size of array PREDS.  */
    1070                 :            : 
    1071                 :            : static bool
    1072                 :         62 : find_matching_predicate_in_rest_chains (pred_info pred,
    1073                 :            :                                         pred_chain_union preds,
    1074                 :            :                                         size_t num_pred_chains)
    1075                 :            : {
    1076                 :         62 :   size_t i, j, n;
    1077                 :            : 
    1078                 :            :   /* Trival case.  */
    1079                 :         62 :   if (num_pred_chains == 1)
    1080                 :            :     return true;
    1081                 :            : 
    1082                 :          0 :   for (i = 1; i < num_pred_chains; i++)
    1083                 :            :     {
    1084                 :          0 :       bool found = false;
    1085                 :          0 :       pred_chain one_chain = preds[i];
    1086                 :          0 :       n = one_chain.length ();
    1087                 :          0 :       for (j = 0; j < n; j++)
    1088                 :            :         {
    1089                 :          0 :           pred_info pred2 = one_chain[j];
    1090                 :            :           /* Can relax the condition comparison to not
    1091                 :            :              use address comparison.  However, the most common
    1092                 :            :              case is that multiple control dependent paths share
    1093                 :            :              a common path prefix, so address comparison should
    1094                 :            :              be ok.  */
    1095                 :            : 
    1096                 :          0 :           if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
    1097                 :          0 :               && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
    1098                 :          0 :               && pred2.invert == pred.invert)
    1099                 :            :             {
    1100                 :          0 :               found = true;
    1101                 :          0 :               break;
    1102                 :            :             }
    1103                 :            :         }
    1104                 :          0 :       if (!found)
    1105                 :         62 :         return false;
    1106                 :            :     }
    1107                 :            :   return true;
    1108                 :            : }
    1109                 :            : 
    1110                 :            : /* Forward declaration.  */
    1111                 :            : static bool is_use_properly_guarded (gimple *use_stmt,
    1112                 :            :                                      basic_block use_bb,
    1113                 :            :                                      gphi *phi,
    1114                 :            :                                      unsigned uninit_opnds,
    1115                 :            :                                      pred_chain_union *def_preds,
    1116                 :            :                                      hash_set<gphi *> *visited_phis);
    1117                 :            : 
    1118                 :            : /* Returns true if all uninitialized opnds are pruned.  Returns false
    1119                 :            :    otherwise.  PHI is the phi node with uninitialized operands,
    1120                 :            :    UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
    1121                 :            :    FLAG_DEF is the statement defining the flag guarding the use of the
    1122                 :            :    PHI output, BOUNDARY_CST is the const value used in the predicate
    1123                 :            :    associated with the flag, CMP_CODE is the comparison code used in
    1124                 :            :    the predicate, VISITED_PHIS is the pointer set of phis visited, and
    1125                 :            :    VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
    1126                 :            :    that are also phis.
    1127                 :            : 
    1128                 :            :    Example scenario:
    1129                 :            : 
    1130                 :            :    BB1:
    1131                 :            :    flag_1 = phi <0, 1>                    // (1)
    1132                 :            :    var_1  = phi <undef, some_val>
    1133                 :            : 
    1134                 :            : 
    1135                 :            :    BB2:
    1136                 :            :    flag_2 = phi <0,   flag_1, flag_1>   // (2)
    1137                 :            :    var_2  = phi <undef, var_1, var_1>
    1138                 :            :    if (flag_2 == 1)
    1139                 :            :       goto BB3;
    1140                 :            : 
    1141                 :            :    BB3:
    1142                 :            :    use of var_2                         // (3)
    1143                 :            : 
    1144                 :            :    Because some flag arg in (1) is not constant, if we do not look into the
    1145                 :            :    flag phis recursively, it is conservatively treated as unknown and var_1
    1146                 :            :    is thought to be flowed into use at (3).  Since var_1 is potentially
    1147                 :            :    uninitialized a false warning will be emitted.
    1148                 :            :    Checking recursively into (1), the compiler can find out that only some_val
    1149                 :            :    (which is defined) can flow into (3) which is OK.  */
    1150                 :            : 
    1151                 :            : static bool
    1152                 :         74 : prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def,
    1153                 :            :                         tree boundary_cst, enum tree_code cmp_code,
    1154                 :            :                         hash_set<gphi *> *visited_phis,
    1155                 :            :                         bitmap *visited_flag_phis)
    1156                 :            : {
    1157                 :         74 :   unsigned i;
    1158                 :            : 
    1159                 :        148 :   for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++)
    1160                 :            :     {
    1161                 :        116 :       tree flag_arg;
    1162                 :            : 
    1163                 :        116 :       if (!MASK_TEST_BIT (uninit_opnds, i))
    1164                 :         42 :         continue;
    1165                 :            : 
    1166                 :         74 :       flag_arg = gimple_phi_arg_def (flag_def, i);
    1167                 :         74 :       if (!is_gimple_constant (flag_arg))
    1168                 :            :         {
    1169                 :         43 :           gphi *flag_arg_def, *phi_arg_def;
    1170                 :         43 :           tree phi_arg;
    1171                 :         43 :           unsigned uninit_opnds_arg_phi;
    1172                 :            : 
    1173                 :         43 :           if (TREE_CODE (flag_arg) != SSA_NAME)
    1174                 :            :             return false;
    1175                 :         43 :           flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
    1176                 :         12 :           if (!flag_arg_def)
    1177                 :            :             return false;
    1178                 :            : 
    1179                 :         12 :           phi_arg = gimple_phi_arg_def (phi, i);
    1180                 :         12 :           if (TREE_CODE (phi_arg) != SSA_NAME)
    1181                 :            :             return false;
    1182                 :            : 
    1183                 :         12 :           phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
    1184                 :         12 :           if (!phi_arg_def)
    1185                 :            :             return false;
    1186                 :            : 
    1187                 :         12 :           if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
    1188                 :            :             return false;
    1189                 :            : 
    1190                 :         12 :           if (!*visited_flag_phis)
    1191                 :         12 :             *visited_flag_phis = BITMAP_ALLOC (NULL);
    1192                 :            : 
    1193                 :         12 :           tree phi_result = gimple_phi_result (flag_arg_def);
    1194                 :         12 :           if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
    1195                 :            :             return false;
    1196                 :            : 
    1197                 :         24 :           bitmap_set_bit (*visited_flag_phis,
    1198                 :         12 :                           SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
    1199                 :            : 
    1200                 :            :           /* Now recursively prune the uninitialized phi args.  */
    1201                 :         12 :           uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
    1202                 :         12 :           if (!prune_uninit_phi_opnds
    1203                 :         12 :               (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def, boundary_cst,
    1204                 :            :                cmp_code, visited_phis, visited_flag_phis))
    1205                 :            :             return false;
    1206                 :            : 
    1207                 :          8 :           phi_result = gimple_phi_result (flag_arg_def);
    1208                 :          8 :           bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
    1209                 :          8 :           continue;
    1210                 :            :         }
    1211                 :            : 
    1212                 :            :       /* Now check if the constant is in the guarded range.  */
    1213                 :         31 :       if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
    1214                 :            :         {
    1215                 :          7 :           tree opnd;
    1216                 :          7 :           gimple *opnd_def;
    1217                 :            : 
    1218                 :            :           /* Now that we know that this undefined edge is not
    1219                 :            :              pruned.  If the operand is defined by another phi,
    1220                 :            :              we can further prune the incoming edges of that
    1221                 :            :              phi by checking the predicates of this operands.  */
    1222                 :            : 
    1223                 :          7 :           opnd = gimple_phi_arg_def (phi, i);
    1224                 :          7 :           opnd_def = SSA_NAME_DEF_STMT (opnd);
    1225                 :          7 :           if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
    1226                 :            :             {
    1227                 :          0 :               edge opnd_edge;
    1228                 :          0 :               unsigned uninit_opnds2 = compute_uninit_opnds_pos (opnd_def_phi);
    1229                 :          0 :               if (!MASK_EMPTY (uninit_opnds2))
    1230                 :            :                 {
    1231                 :          0 :                   pred_chain_union def_preds = vNULL;
    1232                 :          0 :                   bool ok;
    1233                 :          0 :                   opnd_edge = gimple_phi_arg_edge (phi, i);
    1234                 :          0 :                   ok = is_use_properly_guarded (phi,
    1235                 :            :                                                 opnd_edge->src,
    1236                 :            :                                                 opnd_def_phi,
    1237                 :            :                                                 uninit_opnds2,
    1238                 :            :                                                 &def_preds,
    1239                 :            :                                                 visited_phis);
    1240                 :          0 :                   destroy_predicate_vecs (&def_preds);
    1241                 :          0 :                   if (!ok)
    1242                 :          0 :                     return false;
    1243                 :            :                 }
    1244                 :            :             }
    1245                 :            :           else
    1246                 :            :             return false;
    1247                 :            :         }
    1248                 :            :     }
    1249                 :            : 
    1250                 :            :   return true;
    1251                 :            : }
    1252                 :            : 
    1253                 :            : /* A helper function that determines if the predicate set
    1254                 :            :    of the use is not overlapping with that of the uninit paths.
    1255                 :            :    The most common senario of guarded use is in Example 1:
    1256                 :            :      Example 1:
    1257                 :            :            if (some_cond)
    1258                 :            :            {
    1259                 :            :               x = ...;
    1260                 :            :               flag = true;
    1261                 :            :            }
    1262                 :            : 
    1263                 :            :             ... some code ...
    1264                 :            : 
    1265                 :            :            if (flag)
    1266                 :            :               use (x);
    1267                 :            : 
    1268                 :            :      The real world examples are usually more complicated, but similar
    1269                 :            :      and usually result from inlining:
    1270                 :            : 
    1271                 :            :          bool init_func (int * x)
    1272                 :            :          {
    1273                 :            :              if (some_cond)
    1274                 :            :                 return false;
    1275                 :            :              *x  =  ..
    1276                 :            :              return true;
    1277                 :            :          }
    1278                 :            : 
    1279                 :            :          void foo (..)
    1280                 :            :          {
    1281                 :            :              int x;
    1282                 :            : 
    1283                 :            :              if (!init_func (&x))
    1284                 :            :                 return;
    1285                 :            : 
    1286                 :            :              .. some_code ...
    1287                 :            :              use (x);
    1288                 :            :          }
    1289                 :            : 
    1290                 :            :      Another possible use scenario is in the following trivial example:
    1291                 :            : 
    1292                 :            :      Example 2:
    1293                 :            :           if (n > 0)
    1294                 :            :              x = 1;
    1295                 :            :           ...
    1296                 :            :           if (n > 0)
    1297                 :            :             {
    1298                 :            :               if (m < 2)
    1299                 :            :                  .. = x;
    1300                 :            :             }
    1301                 :            : 
    1302                 :            :      Predicate analysis needs to compute the composite predicate:
    1303                 :            : 
    1304                 :            :        1) 'x' use predicate: (n > 0) .AND. (m < 2)
    1305                 :            :        2) 'x' default value  (non-def) predicate: .NOT. (n > 0)
    1306                 :            :        (the predicate chain for phi operand defs can be computed
    1307                 :            :        starting from a bb that is control equivalent to the phi's
    1308                 :            :        bb and is dominating the operand def.)
    1309                 :            : 
    1310                 :            :        and check overlapping:
    1311                 :            :           (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
    1312                 :            :         <==> false
    1313                 :            : 
    1314                 :            :      This implementation provides framework that can handle
    1315                 :            :      scenarios.  (Note that many simple cases are handled properly
    1316                 :            :      without the predicate analysis -- this is due to jump threading
    1317                 :            :      transformation which eliminates the merge point thus makes
    1318                 :            :      path sensitive analysis unnecessary.)
    1319                 :            : 
    1320                 :            :      PHI is the phi node whose incoming (undefined) paths need to be
    1321                 :            :      pruned, and UNINIT_OPNDS is the bitmap holding uninit operand
    1322                 :            :      positions.  VISITED_PHIS is the pointer set of phi stmts being
    1323                 :            :      checked.  */
    1324                 :            : 
    1325                 :            : static bool
    1326                 :        135 : use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
    1327                 :            :                                            gphi *phi, unsigned uninit_opnds,
    1328                 :            :                                            hash_set<gphi *> *visited_phis)
    1329                 :            : {
    1330                 :        135 :   unsigned int i, n;
    1331                 :        135 :   gimple *flag_def = 0;
    1332                 :        135 :   tree boundary_cst = 0;
    1333                 :        135 :   enum tree_code cmp_code;
    1334                 :        135 :   bool swap_cond = false;
    1335                 :        135 :   bool invert = false;
    1336                 :        135 :   pred_chain the_pred_chain = vNULL;
    1337                 :        135 :   bitmap visited_flag_phis = NULL;
    1338                 :        135 :   bool all_pruned = false;
    1339                 :        135 :   size_t num_preds = preds.length ();
    1340                 :            : 
    1341                 :        135 :   gcc_assert (num_preds > 0);
    1342                 :            :   /* Find within the common prefix of multiple predicate chains
    1343                 :            :      a predicate that is a comparison of a flag variable against
    1344                 :            :      a constant.  */
    1345                 :        135 :   the_pred_chain = preds[0];
    1346                 :        135 :   n = the_pred_chain.length ();
    1347                 :        267 :   for (i = 0; i < n; i++)
    1348                 :            :     {
    1349                 :        194 :       tree cond_lhs, cond_rhs, flag = 0;
    1350                 :            : 
    1351                 :        194 :       pred_info the_pred = the_pred_chain[i];
    1352                 :            : 
    1353                 :        194 :       invert = the_pred.invert;
    1354                 :        194 :       cond_lhs = the_pred.pred_lhs;
    1355                 :        194 :       cond_rhs = the_pred.pred_rhs;
    1356                 :        194 :       cmp_code = the_pred.cond_code;
    1357                 :            : 
    1358                 :        194 :       if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
    1359                 :        388 :           && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
    1360                 :            :         {
    1361                 :            :           boundary_cst = cond_rhs;
    1362                 :            :           flag = cond_lhs;
    1363                 :            :         }
    1364                 :          0 :       else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
    1365                 :          0 :                && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
    1366                 :            :         {
    1367                 :            :           boundary_cst = cond_lhs;
    1368                 :            :           flag = cond_rhs;
    1369                 :            :           swap_cond = true;
    1370                 :            :         }
    1371                 :            : 
    1372                 :        194 :       if (!flag)
    1373                 :          0 :         continue;
    1374                 :            : 
    1375                 :        194 :       flag_def = SSA_NAME_DEF_STMT (flag);
    1376                 :            : 
    1377                 :        194 :       if (!flag_def)
    1378                 :          0 :         continue;
    1379                 :            : 
    1380                 :        194 :       if ((gimple_code (flag_def) == GIMPLE_PHI)
    1381                 :         62 :           && (gimple_bb (flag_def) == gimple_bb (phi))
    1382                 :        256 :           && find_matching_predicate_in_rest_chains (the_pred, preds,
    1383                 :            :                                                      num_preds))
    1384                 :            :         break;
    1385                 :            : 
    1386                 :        132 :       flag_def = 0;
    1387                 :            :     }
    1388                 :            : 
    1389                 :        135 :   if (!flag_def)
    1390                 :            :     return false;
    1391                 :            : 
    1392                 :            :   /* Now check all the uninit incoming edge has a constant flag value
    1393                 :            :      that is in conflict with the use guard/predicate.  */
    1394                 :         62 :   cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
    1395                 :            : 
    1396                 :         62 :   if (cmp_code == ERROR_MARK)
    1397                 :            :     return false;
    1398                 :            : 
    1399                 :         62 :   all_pruned = prune_uninit_phi_opnds
    1400                 :         62 :     (phi, uninit_opnds, as_a<gphi *> (flag_def), boundary_cst, cmp_code,
    1401                 :            :      visited_phis, &visited_flag_phis);
    1402                 :            : 
    1403                 :         62 :   if (visited_flag_phis)
    1404                 :         12 :     BITMAP_FREE (visited_flag_phis);
    1405                 :            : 
    1406                 :            :   return all_pruned;
    1407                 :            : }
    1408                 :            : 
    1409                 :            : /* The helper function returns true if two predicates X1 and X2
    1410                 :            :    are equivalent.  It assumes the expressions have already
    1411                 :            :    properly re-associated.  */
    1412                 :            : 
    1413                 :            : static inline bool
    1414                 :            : pred_equal_p (pred_info x1, pred_info x2)
    1415                 :            : {
    1416                 :            :   enum tree_code c1, c2;
    1417                 :            :   if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
    1418                 :            :       || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
    1419                 :            :     return false;
    1420                 :            : 
    1421                 :            :   c1 = x1.cond_code;
    1422                 :            :   if (x1.invert != x2.invert
    1423                 :            :       && TREE_CODE_CLASS (x2.cond_code) == tcc_comparison)
    1424                 :            :     c2 = invert_tree_comparison (x2.cond_code, false);
    1425                 :            :   else
    1426                 :            :     c2 = x2.cond_code;
    1427                 :            : 
    1428                 :            :   return c1 == c2;
    1429                 :            : }
    1430                 :            : 
    1431                 :            : /* Returns true if the predication is testing !=.  */
    1432                 :            : 
    1433                 :            : static inline bool
    1434                 :            : is_neq_relop_p (pred_info pred)
    1435                 :            : {
    1436                 :            : 
    1437                 :            :   return ((pred.cond_code == NE_EXPR && !pred.invert)
    1438                 :            :           || (pred.cond_code == EQ_EXPR && pred.invert));
    1439                 :            : }
    1440                 :            : 
    1441                 :            : /* Returns true if pred is of the form X != 0.  */
    1442                 :            : 
    1443                 :            : static inline bool
    1444                 :            : is_neq_zero_form_p (pred_info pred)
    1445                 :            : {
    1446                 :            :   if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
    1447                 :            :       || TREE_CODE (pred.pred_lhs) != SSA_NAME)
    1448                 :            :     return false;
    1449                 :            :   return true;
    1450                 :            : }
    1451                 :            : 
    1452                 :            : /* The helper function returns true if two predicates X1
    1453                 :            :    is equivalent to X2 != 0.  */
    1454                 :            : 
    1455                 :            : static inline bool
    1456                 :            : pred_expr_equal_p (pred_info x1, tree x2)
    1457                 :            : {
    1458                 :            :   if (!is_neq_zero_form_p (x1))
    1459                 :            :     return false;
    1460                 :            : 
    1461                 :            :   return operand_equal_p (x1.pred_lhs, x2, 0);
    1462                 :            : }
    1463                 :            : 
    1464                 :            : /* Returns true of the domain of single predicate expression
    1465                 :            :    EXPR1 is a subset of that of EXPR2.  Returns false if it
    1466                 :            :    cannot be proved.  */
    1467                 :            : 
    1468                 :            : static bool
    1469                 :        232 : is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
    1470                 :            : {
    1471                 :        232 :   enum tree_code code1, code2;
    1472                 :            : 
    1473                 :        232 :   if (pred_equal_p (expr1, expr2))
    1474                 :            :     return true;
    1475                 :            : 
    1476                 :        211 :   if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
    1477                 :        194 :       || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
    1478                 :            :     return false;
    1479                 :            : 
    1480                 :        192 :   if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
    1481                 :            :     return false;
    1482                 :            : 
    1483                 :         42 :   code1 = expr1.cond_code;
    1484                 :         42 :   if (expr1.invert)
    1485                 :          1 :     code1 = invert_tree_comparison (code1, false);
    1486                 :         42 :   code2 = expr2.cond_code;
    1487                 :         42 :   if (expr2.invert)
    1488                 :          0 :     code2 = invert_tree_comparison (code2, false);
    1489                 :            : 
    1490                 :         42 :   if (code2 == NE_EXPR && code1 == NE_EXPR)
    1491                 :            :     return false;
    1492                 :            : 
    1493                 :         40 :   if (code2 == NE_EXPR)
    1494                 :          9 :     return !value_sat_pred_p (expr2.pred_rhs, expr1.pred_rhs, code1);
    1495                 :            : 
    1496                 :         31 :   if (code1 == EQ_EXPR)
    1497                 :          6 :     return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2);
    1498                 :            : 
    1499                 :         25 :   if (code1 == code2)
    1500                 :         23 :     return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2,
    1501                 :         23 :                              code1 == BIT_AND_EXPR);
    1502                 :            : 
    1503                 :            :   return false;
    1504                 :            : }
    1505                 :            : 
    1506                 :            : /* Returns true if the domain of PRED1 is a subset
    1507                 :            :    of that of PRED2.  Returns false if it cannot be proved so.  */
    1508                 :            : 
    1509                 :            : static bool
    1510                 :        123 : is_pred_chain_subset_of (pred_chain pred1, pred_chain pred2)
    1511                 :            : {
    1512                 :        123 :   size_t np1, np2, i1, i2;
    1513                 :            : 
    1514                 :        123 :   np1 = pred1.length ();
    1515                 :        123 :   np2 = pred2.length ();
    1516                 :            : 
    1517                 :        174 :   for (i2 = 0; i2 < np2; i2++)
    1518                 :            :     {
    1519                 :        139 :       bool found = false;
    1520                 :        139 :       pred_info info2 = pred2[i2];
    1521                 :        320 :       for (i1 = 0; i1 < np1; i1++)
    1522                 :            :         {
    1523                 :        232 :           pred_info info1 = pred1[i1];
    1524                 :        232 :           if (is_pred_expr_subset_of (info1, info2))
    1525                 :            :             {
    1526                 :         51 :               found = true;
    1527                 :         51 :               break;
    1528                 :            :             }
    1529                 :            :         }
    1530                 :         51 :       if (!found)
    1531                 :         88 :         return false;
    1532                 :            :     }
    1533                 :            :   return true;
    1534                 :            : }
    1535                 :            : 
    1536                 :            : /* Returns true if the domain defined by
    1537                 :            :    one pred chain ONE_PRED is a subset of the domain
    1538                 :            :    of *PREDS.  It returns false if ONE_PRED's domain is
    1539                 :            :    not a subset of any of the sub-domains of PREDS
    1540                 :            :    (corresponding to each individual chains in it), even
    1541                 :            :    though it may be still be a subset of whole domain
    1542                 :            :    of PREDS which is the union (ORed) of all its subdomains.
    1543                 :            :    In other words, the result is conservative.  */
    1544                 :            : 
    1545                 :            : static bool
    1546                 :        105 : is_included_in (pred_chain one_pred, pred_chain_union preds)
    1547                 :            : {
    1548                 :        105 :   size_t i;
    1549                 :        105 :   size_t n = preds.length ();
    1550                 :            : 
    1551                 :        193 :   for (i = 0; i < n; i++)
    1552                 :            :     {
    1553                 :        123 :       if (is_pred_chain_subset_of (one_pred, preds[i]))
    1554                 :            :         return true;
    1555                 :            :     }
    1556                 :            : 
    1557                 :            :   return false;
    1558                 :            : }
    1559                 :            : 
    1560                 :            : /* Compares two predicate sets PREDS1 and PREDS2 and returns
    1561                 :            :    true if the domain defined by PREDS1 is a superset
    1562                 :            :    of PREDS2's domain.  N1 and N2 are array sizes of PREDS1 and
    1563                 :            :    PREDS2 respectively.  The implementation chooses not to build
    1564                 :            :    generic trees (and relying on the folding capability of the
    1565                 :            :    compiler), but instead performs brute force comparison of
    1566                 :            :    individual predicate chains (won't be a compile time problem
    1567                 :            :    as the chains are pretty short).  When the function returns
    1568                 :            :    false, it does not necessarily mean *PREDS1 is not a superset
    1569                 :            :    of *PREDS2, but mean it may not be so since the analysis cannot
    1570                 :            :    prove it.  In such cases, false warnings may still be
    1571                 :            :    emitted.  */
    1572                 :            : 
    1573                 :            : static bool
    1574                 :         95 : is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
    1575                 :            : {
    1576                 :         95 :   size_t i, n2;
    1577                 :         95 :   pred_chain one_pred_chain = vNULL;
    1578                 :            : 
    1579                 :         95 :   n2 = preds2.length ();
    1580                 :            : 
    1581                 :        130 :   for (i = 0; i < n2; i++)
    1582                 :            :     {
    1583                 :        105 :       one_pred_chain = preds2[i];
    1584                 :        105 :       if (!is_included_in (one_pred_chain, preds1))
    1585                 :            :         return false;
    1586                 :            :     }
    1587                 :            : 
    1588                 :            :   return true;
    1589                 :            : }
    1590                 :            : 
    1591                 :            : /* Returns true if X1 is the negate of X2.  */
    1592                 :            : 
    1593                 :            : static inline bool
    1594                 :            : pred_neg_p (pred_info x1, pred_info x2)
    1595                 :            : {
    1596                 :            :   enum tree_code c1, c2;
    1597                 :            :   if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
    1598                 :            :       || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
    1599                 :            :     return false;
    1600                 :            : 
    1601                 :            :   c1 = x1.cond_code;
    1602                 :            :   if (x1.invert == x2.invert)
    1603                 :            :     c2 = invert_tree_comparison (x2.cond_code, false);
    1604                 :            :   else
    1605                 :            :     c2 = x2.cond_code;
    1606                 :            : 
    1607                 :            :   return c1 == c2;
    1608                 :            : }
    1609                 :            : 
    1610                 :            : /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
    1611                 :            :    2) (X AND Y) OR (!X AND Y) is equivalent to Y;
    1612                 :            :    3) X OR (!X AND Y) is equivalent to (X OR Y);
    1613                 :            :    4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
    1614                 :            :       (x != 0 AND y != 0)
    1615                 :            :    5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
    1616                 :            :       (X AND Y) OR Z
    1617                 :            : 
    1618                 :            :    PREDS is the predicate chains, and N is the number of chains.  */
    1619                 :            : 
    1620                 :            : /* Helper function to implement rule 1 above.  ONE_CHAIN is
    1621                 :            :    the AND predication to be simplified.  */
    1622                 :            : 
    1623                 :            : static void
    1624                 :        231 : simplify_pred (pred_chain *one_chain)
    1625                 :            : {
    1626                 :        231 :   size_t i, j, n;
    1627                 :        231 :   bool simplified = false;
    1628                 :        231 :   pred_chain s_chain = vNULL;
    1629                 :            : 
    1630                 :        231 :   n = one_chain->length ();
    1631                 :            : 
    1632                 :        636 :   for (i = 0; i < n; i++)
    1633                 :            :     {
    1634                 :        405 :       pred_info *a_pred = &(*one_chain)[i];
    1635                 :            : 
    1636                 :        405 :       if (!a_pred->pred_lhs)
    1637                 :          0 :         continue;
    1638                 :        405 :       if (!is_neq_zero_form_p (*a_pred))
    1639                 :        276 :         continue;
    1640                 :            : 
    1641                 :        129 :       gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
    1642                 :        129 :       if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
    1643                 :         59 :         continue;
    1644                 :         70 :       if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
    1645                 :            :         {
    1646                 :         50 :           for (j = 0; j < n; j++)
    1647                 :            :             {
    1648                 :         33 :               pred_info *b_pred = &(*one_chain)[j];
    1649                 :            : 
    1650                 :         33 :               if (!b_pred->pred_lhs)
    1651                 :          2 :                 continue;
    1652                 :         31 :               if (!is_neq_zero_form_p (*b_pred))
    1653                 :          7 :                 continue;
    1654                 :            : 
    1655                 :         24 :               if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
    1656                 :         24 :                   || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
    1657                 :            :                 {
    1658                 :            :                   /* Mark a_pred for removal.  */
    1659                 :          3 :                   a_pred->pred_lhs = NULL;
    1660                 :          3 :                   a_pred->pred_rhs = NULL;
    1661                 :          3 :                   simplified = true;
    1662                 :          3 :                   break;
    1663                 :            :                 }
    1664                 :            :             }
    1665                 :            :         }
    1666                 :            :     }
    1667                 :            : 
    1668                 :        231 :   if (!simplified)
    1669                 :        228 :     return;
    1670                 :            : 
    1671                 :          9 :   for (i = 0; i < n; i++)
    1672                 :            :     {
    1673                 :          6 :       pred_info *a_pred = &(*one_chain)[i];
    1674                 :          6 :       if (!a_pred->pred_lhs)
    1675                 :          3 :         continue;
    1676                 :          3 :       s_chain.safe_push (*a_pred);
    1677                 :            :     }
    1678                 :            : 
    1679                 :          3 :   one_chain->release ();
    1680                 :          3 :   *one_chain = s_chain;
    1681                 :            : }
    1682                 :            : 
    1683                 :            : /* The helper function implements the rule 2 for the
    1684                 :            :    OR predicate PREDS.
    1685                 :            : 
    1686                 :            :    2) (X AND Y) OR (!X AND Y) is equivalent to Y.  */
    1687                 :            : 
    1688                 :            : static bool
    1689                 :         28 : simplify_preds_2 (pred_chain_union *preds)
    1690                 :            : {
    1691                 :         28 :   size_t i, j, n;
    1692                 :         28 :   bool simplified = false;
    1693                 :         28 :   pred_chain_union s_preds = vNULL;
    1694                 :            : 
    1695                 :            :   /* (X AND Y) OR (!X AND Y) is equivalent to Y.
    1696                 :            :      (X AND Y) OR (X AND !Y) is equivalent to X.  */
    1697                 :            : 
    1698                 :         28 :   n = preds->length ();
    1699                 :         88 :   for (i = 0; i < n; i++)
    1700                 :            :     {
    1701                 :         60 :       pred_info x, y;
    1702                 :         60 :       pred_chain *a_chain = &(*preds)[i];
    1703                 :            : 
    1704                 :         60 :       if (a_chain->length () != 2)
    1705                 :         46 :         continue;
    1706                 :            : 
    1707                 :         14 :       x = (*a_chain)[0];
    1708                 :         14 :       y = (*a_chain)[1];
    1709                 :            : 
    1710                 :         45 :       for (j = 0; j < n; j++)
    1711                 :            :         {
    1712                 :         32 :           pred_chain *b_chain;
    1713                 :         32 :           pred_info x2, y2;
    1714                 :            : 
    1715                 :         32 :           if (j == i)
    1716                 :         31 :             continue;
    1717                 :            : 
    1718                 :         18 :           b_chain = &(*preds)[j];
    1719                 :         18 :           if (b_chain->length () != 2)
    1720                 :         17 :             continue;
    1721                 :            : 
    1722                 :          1 :           x2 = (*b_chain)[0];
    1723                 :          1 :           y2 = (*b_chain)[1];
    1724                 :            : 
    1725                 :          1 :           if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
    1726                 :            :             {
    1727                 :            :               /* Kill a_chain.  */
    1728                 :          0 :               a_chain->release ();
    1729                 :          0 :               b_chain->release ();
    1730                 :          0 :               b_chain->safe_push (x);
    1731                 :          0 :               simplified = true;
    1732                 :          1 :               break;
    1733                 :            :             }
    1734                 :          1 :           if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
    1735                 :            :             {
    1736                 :            :               /* Kill a_chain.  */
    1737                 :          1 :               a_chain->release ();
    1738                 :          1 :               b_chain->release ();
    1739                 :          1 :               b_chain->safe_push (y);
    1740                 :          1 :               simplified = true;
    1741                 :          1 :               break;
    1742                 :            :             }
    1743                 :            :         }
    1744                 :            :     }
    1745                 :            :   /* Now clean up the chain.  */
    1746                 :         28 :   if (simplified)
    1747                 :            :     {
    1748                 :          4 :       for (i = 0; i < n; i++)
    1749                 :            :         {
    1750                 :          3 :           if ((*preds)[i].is_empty ())
    1751                 :          1 :             continue;
    1752                 :          2 :           s_preds.safe_push ((*preds)[i]);
    1753                 :            :         }
    1754                 :          1 :       preds->release ();
    1755                 :          1 :       (*preds) = s_preds;
    1756                 :          1 :       s_preds = vNULL;
    1757                 :            :     }
    1758                 :            : 
    1759                 :         28 :   return simplified;
    1760                 :            : }
    1761                 :            : 
    1762                 :            : /* The helper function implements the rule 2 for the
    1763                 :            :    OR predicate PREDS.
    1764                 :            : 
    1765                 :            :    3) x OR (!x AND y) is equivalent to x OR y.  */
    1766                 :            : 
    1767                 :            : static bool
    1768                 :         28 : simplify_preds_3 (pred_chain_union *preds)
    1769                 :            : {
    1770                 :         28 :   size_t i, j, n;
    1771                 :         28 :   bool simplified = false;
    1772                 :            : 
    1773                 :            :   /* Now iteratively simplify X OR (!X AND Z ..)
    1774                 :            :        into X OR (Z ...).  */
    1775                 :            : 
    1776                 :         28 :   n = preds->length ();
    1777                 :         28 :   if (n < 2)
    1778                 :            :     return false;
    1779                 :            : 
    1780                 :         87 :   for (i = 0; i < n; i++)
    1781                 :            :     {
    1782                 :         59 :       pred_info x;
    1783                 :         59 :       pred_chain *a_chain = &(*preds)[i];
    1784                 :            : 
    1785                 :         59 :       if (a_chain->length () != 1)
    1786                 :         25 :         continue;
    1787                 :            : 
    1788                 :         34 :       x = (*a_chain)[0];
    1789                 :            : 
    1790                 :        103 :       for (j = 0; j < n; j++)
    1791                 :            :         {
    1792                 :         69 :           pred_chain *b_chain;
    1793                 :         69 :           pred_info x2;
    1794                 :         69 :           size_t k;
    1795                 :            : 
    1796                 :         69 :           if (j == i)
    1797                 :         57 :             continue;
    1798                 :            : 
    1799                 :         35 :           b_chain = &(*preds)[j];
    1800                 :         35 :           if (b_chain->length () < 2)
    1801                 :         23 :             continue;
    1802                 :            : 
    1803                 :         36 :           for (k = 0; k < b_chain->length (); k++)
    1804                 :            :             {
    1805                 :         16 :               x2 = (*b_chain)[k];
    1806                 :         16 :               if (pred_neg_p (x, x2))
    1807                 :            :                 {
    1808                 :         10 :                   b_chain->unordered_remove (k);
    1809                 :         10 :                   simplified = true;
    1810                 :         10 :                   break;
    1811                 :            :                 }
    1812                 :            :             }
    1813                 :            :         }
    1814                 :            :     }
    1815                 :            :   return simplified;
    1816                 :            : }
    1817                 :            : 
    1818                 :            : /* The helper function implements the rule 4 for the
    1819                 :            :    OR predicate PREDS.
    1820                 :            : 
    1821                 :            :    2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
    1822                 :            :        (x != 0 ANd y != 0).   */
    1823                 :            : 
    1824                 :            : static bool
    1825                 :         28 : simplify_preds_4 (pred_chain_union *preds)
    1826                 :            : {
    1827                 :         28 :   size_t i, j, n;
    1828                 :         28 :   bool simplified = false;
    1829                 :         28 :   pred_chain_union s_preds = vNULL;
    1830                 :         28 :   gimple *def_stmt;
    1831                 :            : 
    1832                 :         28 :   n = preds->length ();
    1833                 :         87 :   for (i = 0; i < n; i++)
    1834                 :            :     {
    1835                 :         59 :       pred_info z;
    1836                 :         59 :       pred_chain *a_chain = &(*preds)[i];
    1837                 :            : 
    1838                 :         59 :       if (a_chain->length () != 1)
    1839                 :         57 :         continue;
    1840                 :            : 
    1841                 :         39 :       z = (*a_chain)[0];
    1842                 :            : 
    1843                 :         39 :       if (!is_neq_zero_form_p (z))
    1844                 :          4 :         continue;
    1845                 :            : 
    1846                 :         35 :       def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
    1847                 :         35 :       if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
    1848                 :         20 :         continue;
    1849                 :            : 
    1850                 :         15 :       if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
    1851                 :         13 :         continue;
    1852                 :            : 
    1853                 :          6 :       for (j = 0; j < n; j++)
    1854                 :            :         {
    1855                 :          4 :           pred_chain *b_chain;
    1856                 :          4 :           pred_info x2, y2;
    1857                 :            : 
    1858                 :          4 :           if (j == i)
    1859                 :          4 :             continue;
    1860                 :            : 
    1861                 :          2 :           b_chain = &(*preds)[j];
    1862                 :          2 :           if (b_chain->length () != 2)
    1863                 :          2 :             continue;
    1864                 :            : 
    1865                 :          0 :           x2 = (*b_chain)[0];
    1866                 :          0 :           y2 = (*b_chain)[1];
    1867                 :          0 :           if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
    1868                 :          0 :             continue;
    1869                 :            : 
    1870                 :          0 :           if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
    1871                 :          0 :                && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
    1872                 :          0 :               || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
    1873                 :          0 :                   && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
    1874                 :            :             {
    1875                 :            :               /* Kill a_chain.  */
    1876                 :          0 :               a_chain->release ();
    1877                 :          0 :               simplified = true;
    1878                 :          0 :               break;
    1879                 :            :             }
    1880                 :            :         }
    1881                 :            :     }
    1882                 :            :   /* Now clean up the chain.  */
    1883                 :         28 :   if (simplified)
    1884                 :            :     {
    1885                 :          0 :       for (i = 0; i < n; i++)
    1886                 :            :         {
    1887                 :          0 :           if ((*preds)[i].is_empty ())
    1888                 :          0 :             continue;
    1889                 :          0 :           s_preds.safe_push ((*preds)[i]);
    1890                 :            :         }
    1891                 :            : 
    1892                 :          0 :       preds->release ();
    1893                 :          0 :       (*preds) = s_preds;
    1894                 :          0 :       s_preds = vNULL;
    1895                 :            :     }
    1896                 :            : 
    1897                 :         28 :   return simplified;
    1898                 :            : }
    1899                 :            : 
    1900                 :            : /* This function simplifies predicates in PREDS.  */
    1901                 :            : 
    1902                 :            : static void
    1903                 :        211 : simplify_preds (pred_chain_union *preds, gimple *use_or_def, bool is_use)
    1904                 :            : {
    1905                 :        211 :   size_t i, n;
    1906                 :        211 :   bool changed = false;
    1907                 :            : 
    1908                 :        211 :   if (dump_file && dump_flags & TDF_DETAILS)
    1909                 :            :     {
    1910                 :          0 :       fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
    1911                 :          0 :       dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
    1912                 :            :     }
    1913                 :            : 
    1914                 :        884 :   for (i = 0; i < preds->length (); i++)
    1915                 :        231 :     simplify_pred (&(*preds)[i]);
    1916                 :            : 
    1917                 :        211 :   n = preds->length ();
    1918                 :        211 :   if (n < 2)
    1919                 :            :     return;
    1920                 :            : 
    1921                 :         28 :   do
    1922                 :            :     {
    1923                 :         28 :       changed = false;
    1924                 :         28 :       if (simplify_preds_2 (preds))
    1925                 :          1 :         changed = true;
    1926                 :            : 
    1927                 :            :       /* Now iteratively simplify X OR (!X AND Z ..)
    1928                 :            :        into X OR (Z ...).  */
    1929                 :         28 :       if (simplify_preds_3 (preds))
    1930                 :         10 :         changed = true;
    1931                 :            : 
    1932                 :         28 :       if (simplify_preds_4 (preds))
    1933                 :            :         changed = true;
    1934                 :            :     }
    1935                 :            :   while (changed);
    1936                 :            : 
    1937                 :            :   return;
    1938                 :            : }
    1939                 :            : 
    1940                 :            : /* This is a helper function which attempts to normalize predicate chains
    1941                 :            :   by following UD chains.  It basically builds up a big tree of either IOR
    1942                 :            :   operations or AND operations, and convert the IOR tree into a
    1943                 :            :   pred_chain_union or BIT_AND tree into a pred_chain.
    1944                 :            :   Example:
    1945                 :            : 
    1946                 :            :   _3 = _2 RELOP1 _1;
    1947                 :            :   _6 = _5 RELOP2 _4;
    1948                 :            :   _9 = _8 RELOP3 _7;
    1949                 :            :   _10 = _3 | _6;
    1950                 :            :   _12 = _9 | _0;
    1951                 :            :   _t = _10 | _12;
    1952                 :            : 
    1953                 :            :  then _t != 0 will be normalized into a pred_chain_union
    1954                 :            : 
    1955                 :            :    (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
    1956                 :            : 
    1957                 :            :  Similarly given,
    1958                 :            : 
    1959                 :            :   _3 = _2 RELOP1 _1;
    1960                 :            :   _6 = _5 RELOP2 _4;
    1961                 :            :   _9 = _8 RELOP3 _7;
    1962                 :            :   _10 = _3 & _6;
    1963                 :            :   _12 = _9 & _0;
    1964                 :            : 
    1965                 :            :  then _t != 0 will be normalized into a pred_chain:
    1966                 :            :    (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
    1967                 :            : 
    1968                 :            :   */
    1969                 :            : 
    1970                 :            : /* This is a helper function that stores a PRED into NORM_PREDS.  */
    1971                 :            : 
    1972                 :            : inline static void
    1973                 :        151 : push_pred (pred_chain_union *norm_preds, pred_info pred)
    1974                 :            : {
    1975                 :        151 :   pred_chain pred_chain = vNULL;
    1976                 :        151 :   pred_chain.safe_push (pred);
    1977                 :        151 :   norm_preds->safe_push (pred_chain);
    1978                 :            : }
    1979                 :            : 
    1980                 :            : /* A helper function that creates a predicate of the form
    1981                 :            :    OP != 0 and push it WORK_LIST.  */
    1982                 :            : 
    1983                 :            : inline static void
    1984                 :        102 : push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
    1985                 :            :                   hash_set<tree> *mark_set)
    1986                 :            : {
    1987                 :        102 :   if (mark_set->contains (op))
    1988                 :          2 :     return;
    1989                 :        100 :   mark_set->add (op);
    1990                 :            : 
    1991                 :        100 :   pred_info arg_pred;
    1992                 :        100 :   arg_pred.pred_lhs = op;
    1993                 :        100 :   arg_pred.pred_rhs = integer_zero_node;
    1994                 :        100 :   arg_pred.cond_code = NE_EXPR;
    1995                 :        100 :   arg_pred.invert = false;
    1996                 :        100 :   work_list->safe_push (arg_pred);
    1997                 :            : }
    1998                 :            : 
    1999                 :            : /* A helper that generates a pred_info from a gimple assignment
    2000                 :            :    CMP_ASSIGN with comparison rhs.  */
    2001                 :            : 
    2002                 :            : static pred_info
    2003                 :         74 : get_pred_info_from_cmp (gimple *cmp_assign)
    2004                 :            : {
    2005                 :         74 :   pred_info n_pred;
    2006                 :         74 :   n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
    2007                 :         74 :   n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
    2008                 :         74 :   n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
    2009                 :         74 :   n_pred.invert = false;
    2010                 :         74 :   return n_pred;
    2011                 :            : }
    2012                 :            : 
    2013                 :            : /* Returns true if the PHI is a degenerated phi with
    2014                 :            :    all args with the same value (relop).  In that case, *PRED
    2015                 :            :    will be updated to that value.  */
    2016                 :            : 
    2017                 :            : static bool
    2018                 :          7 : is_degenerated_phi (gimple *phi, pred_info *pred_p)
    2019                 :            : {
    2020                 :          7 :   int i, n;
    2021                 :          7 :   tree op0;
    2022                 :          7 :   gimple *def0;
    2023                 :          7 :   pred_info pred0;
    2024                 :            : 
    2025                 :          7 :   n = gimple_phi_num_args (phi);
    2026                 :          7 :   op0 = gimple_phi_arg_def (phi, 0);
    2027                 :            : 
    2028                 :          7 :   if (TREE_CODE (op0) != SSA_NAME)
    2029                 :            :     return false;
    2030                 :            : 
    2031                 :          7 :   def0 = SSA_NAME_DEF_STMT (op0);
    2032                 :          7 :   if (gimple_code (def0) != GIMPLE_ASSIGN)
    2033                 :            :     return false;
    2034                 :          4 :   if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
    2035                 :            :     return false;
    2036                 :          0 :   pred0 = get_pred_info_from_cmp (def0);
    2037                 :            : 
    2038                 :          0 :   for (i = 1; i < n; ++i)
    2039                 :            :     {
    2040                 :          0 :       gimple *def;
    2041                 :          0 :       pred_info pred;
    2042                 :          0 :       tree op = gimple_phi_arg_def (phi, i);
    2043                 :            : 
    2044                 :          0 :       if (TREE_CODE (op) != SSA_NAME)
    2045                 :          0 :         return false;
    2046                 :            : 
    2047                 :          0 :       def = SSA_NAME_DEF_STMT (op);
    2048                 :          0 :       if (gimple_code (def) != GIMPLE_ASSIGN)
    2049                 :            :         return false;
    2050                 :          0 :       if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
    2051                 :            :         return false;
    2052                 :          0 :       pred = get_pred_info_from_cmp (def);
    2053                 :          0 :       if (!pred_equal_p (pred, pred0))
    2054                 :            :         return false;
    2055                 :            :     }
    2056                 :            : 
    2057                 :          0 :   *pred_p = pred0;
    2058                 :          0 :   return true;
    2059                 :            : }
    2060                 :            : 
    2061                 :            : /* Normalize one predicate PRED
    2062                 :            :    1) if PRED can no longer be normlized, put it into NORM_PREDS.
    2063                 :            :    2) otherwise if PRED is of the form x != 0, follow x's definition
    2064                 :            :       and put normalized predicates into WORK_LIST.  */
    2065                 :            : 
    2066                 :            : static void
    2067                 :        368 : normalize_one_pred_1 (pred_chain_union *norm_preds,
    2068                 :            :                       pred_chain *norm_chain,
    2069                 :            :                       pred_info pred,
    2070                 :            :                       enum tree_code and_or_code,
    2071                 :            :                       vec<pred_info, va_heap, vl_ptr> *work_list,
    2072                 :            :                       hash_set<tree> *mark_set)
    2073                 :            : {
    2074                 :        368 :   if (!is_neq_zero_form_p (pred))
    2075                 :            :     {
    2076                 :        178 :       if (and_or_code == BIT_IOR_EXPR)
    2077                 :          0 :         push_pred (norm_preds, pred);
    2078                 :            :       else
    2079                 :        178 :         norm_chain->safe_push (pred);
    2080                 :        178 :       return;
    2081                 :            :     }
    2082                 :            : 
    2083                 :        190 :   gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
    2084                 :            : 
    2085                 :        190 :   if (gimple_code (def_stmt) == GIMPLE_PHI
    2086                 :        190 :       && is_degenerated_phi (def_stmt, &pred))
    2087                 :          0 :     work_list->safe_push (pred);
    2088                 :        190 :   else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
    2089                 :            :     {
    2090                 :          3 :       int i, n;
    2091                 :          3 :       n = gimple_phi_num_args (def_stmt);
    2092                 :            : 
    2093                 :            :       /* If we see non zero constant, we should punt.  The predicate
    2094                 :            :        * should be one guarding the phi edge.  */
    2095                 :          9 :       for (i = 0; i < n; ++i)
    2096                 :            :         {
    2097                 :          6 :           tree op = gimple_phi_arg_def (def_stmt, i);
    2098                 :          6 :           if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
    2099                 :            :             {
    2100                 :          0 :               push_pred (norm_preds, pred);
    2101                 :          0 :               return;
    2102                 :            :             }
    2103                 :            :         }
    2104                 :            : 
    2105                 :          9 :       for (i = 0; i < n; ++i)
    2106                 :            :         {
    2107                 :          6 :           tree op = gimple_phi_arg_def (def_stmt, i);
    2108                 :          6 :           if (integer_zerop (op))
    2109                 :          0 :             continue;
    2110                 :            : 
    2111                 :          6 :           push_to_worklist (op, work_list, mark_set);
    2112                 :            :         }
    2113                 :            :     }
    2114                 :        187 :   else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
    2115                 :            :     {
    2116                 :         39 :       if (and_or_code == BIT_IOR_EXPR)
    2117                 :         26 :         push_pred (norm_preds, pred);
    2118                 :            :       else
    2119                 :         26 :         norm_chain->safe_push (pred);
    2120                 :            :     }
    2121                 :        148 :   else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
    2122                 :            :     {
    2123                 :            :       /* Avoid splitting up bit manipulations like x & 3 or y | 1.  */
    2124                 :         57 :       if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
    2125                 :            :         {
    2126                 :            :           /* But treat x & 3 as condition.  */
    2127                 :          9 :           if (and_or_code == BIT_AND_EXPR)
    2128                 :            :             {
    2129                 :          9 :               pred_info n_pred;
    2130                 :          9 :               n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
    2131                 :          9 :               n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
    2132                 :          9 :               n_pred.cond_code = and_or_code;
    2133                 :          9 :               n_pred.invert = false;
    2134                 :          9 :               norm_chain->safe_push (n_pred);
    2135                 :            :             }
    2136                 :            :         }
    2137                 :            :       else
    2138                 :            :         {
    2139                 :         48 :           push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
    2140                 :         48 :           push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
    2141                 :            :         }
    2142                 :            :     }
    2143                 :         91 :   else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
    2144                 :            :            == tcc_comparison)
    2145                 :            :     {
    2146                 :         74 :       pred_info n_pred = get_pred_info_from_cmp (def_stmt);
    2147                 :         74 :       if (and_or_code == BIT_IOR_EXPR)
    2148                 :         34 :         push_pred (norm_preds, n_pred);
    2149                 :            :       else
    2150                 :         57 :         norm_chain->safe_push (n_pred);
    2151                 :            :     }
    2152                 :            :   else
    2153                 :            :     {
    2154                 :         17 :       if (and_or_code == BIT_IOR_EXPR)
    2155                 :          0 :         push_pred (norm_preds, pred);
    2156                 :            :       else
    2157                 :         17 :         norm_chain->safe_push (pred);
    2158                 :            :     }
    2159                 :            : }
    2160                 :            : 
    2161                 :            : /* Normalize PRED and store the normalized predicates into NORM_PREDS.  */
    2162                 :            : 
    2163                 :            : static void
    2164                 :        159 : normalize_one_pred (pred_chain_union *norm_preds, pred_info pred)
    2165                 :            : {
    2166                 :        159 :   vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
    2167                 :        159 :   enum tree_code and_or_code = ERROR_MARK;
    2168                 :        159 :   pred_chain norm_chain = vNULL;
    2169                 :            : 
    2170                 :        159 :   if (!is_neq_zero_form_p (pred))
    2171                 :            :     {
    2172                 :         87 :       push_pred (norm_preds, pred);
    2173                 :        121 :       return;
    2174                 :            :     }
    2175                 :            : 
    2176                 :         72 :   gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
    2177                 :         72 :   if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
    2178                 :         40 :     and_or_code = gimple_assign_rhs_code (def_stmt);
    2179                 :         72 :   if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
    2180                 :            :     {
    2181                 :         34 :       if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
    2182                 :            :         {
    2183                 :          0 :           pred_info n_pred = get_pred_info_from_cmp (def_stmt);
    2184                 :          0 :           push_pred (norm_preds, n_pred);
    2185                 :            :         }
    2186                 :            :       else
    2187                 :         68 :         push_pred (norm_preds, pred);
    2188                 :         34 :       return;
    2189                 :            :     }
    2190                 :            : 
    2191                 :         38 :   work_list.safe_push (pred);
    2192                 :         76 :   hash_set<tree> mark_set;
    2193                 :            : 
    2194                 :        152 :   while (!work_list.is_empty ())
    2195                 :            :     {
    2196                 :        114 :       pred_info a_pred = work_list.pop ();
    2197                 :        114 :       normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, and_or_code,
    2198                 :            :                             &work_list, &mark_set);
    2199                 :            :     }
    2200                 :         38 :   if (and_or_code == BIT_AND_EXPR)
    2201                 :         24 :     norm_preds->safe_push (norm_chain);
    2202                 :            : 
    2203                 :         76 :   work_list.release ();
    2204                 :            : }
    2205                 :            : 
    2206                 :            : static void
    2207                 :         71 : normalize_one_pred_chain (pred_chain_union *norm_preds, pred_chain one_chain)
    2208                 :            : {
    2209                 :         71 :   vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
    2210                 :         71 :   hash_set<tree> mark_set;
    2211                 :         71 :   pred_chain norm_chain = vNULL;
    2212                 :         71 :   size_t i;
    2213                 :            : 
    2214                 :        602 :   for (i = 0; i < one_chain.length (); i++)
    2215                 :            :     {
    2216                 :        230 :       work_list.safe_push (one_chain[i]);
    2217                 :        230 :       mark_set.add (one_chain[i].pred_lhs);
    2218                 :            :     }
    2219                 :            : 
    2220                 :        325 :   while (!work_list.is_empty ())
    2221                 :            :     {
    2222                 :        254 :       pred_info a_pred = work_list.pop ();
    2223                 :        254 :       normalize_one_pred_1 (0, &norm_chain, a_pred, BIT_AND_EXPR, &work_list,
    2224                 :            :                             &mark_set);
    2225                 :            :     }
    2226                 :            : 
    2227                 :         71 :   norm_preds->safe_push (norm_chain);
    2228                 :        142 :   work_list.release ();
    2229                 :         71 : }
    2230                 :            : 
    2231                 :            : /* Normalize predicate chains PREDS and returns the normalized one.  */
    2232                 :            : 
    2233                 :            : static pred_chain_union
    2234                 :        211 : normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
    2235                 :            : {
    2236                 :        211 :   pred_chain_union norm_preds = vNULL;
    2237                 :        211 :   size_t n = preds.length ();
    2238                 :        211 :   size_t i;
    2239                 :            : 
    2240                 :        211 :   if (dump_file && dump_flags & TDF_DETAILS)
    2241                 :            :     {
    2242                 :          0 :       fprintf (dump_file, "[BEFORE NORMALIZATION --");
    2243                 :          0 :       dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
    2244                 :            :     }
    2245                 :            : 
    2246                 :        441 :   for (i = 0; i < n; i++)
    2247                 :            :     {
    2248                 :        230 :       if (preds[i].length () != 1)
    2249                 :         71 :         normalize_one_pred_chain (&norm_preds, preds[i]);
    2250                 :            :       else
    2251                 :            :         {
    2252                 :        159 :           normalize_one_pred (&norm_preds, preds[i][0]);
    2253                 :        389 :           preds[i].release ();
    2254                 :            :         }
    2255                 :            :     }
    2256                 :            : 
    2257                 :        211 :   if (dump_file)
    2258                 :            :     {
    2259                 :          0 :       fprintf (dump_file, "[AFTER NORMALIZATION -- ");
    2260                 :          0 :       dump_predicates (use_or_def, norm_preds,
    2261                 :            :                        is_use ? "[USE]:\n" : "[DEF]:\n");
    2262                 :            :     }
    2263                 :            : 
    2264                 :        211 :   destroy_predicate_vecs (&preds);
    2265                 :        211 :   return norm_preds;
    2266                 :            : }
    2267                 :            : 
    2268                 :            : /* Return TRUE if PREDICATE can be invalidated by any individual
    2269                 :            :    predicate in USE_GUARD.  */
    2270                 :            : 
    2271                 :            : static bool
    2272                 :         73 : can_one_predicate_be_invalidated_p (pred_info predicate,
    2273                 :            :                                     pred_chain use_guard)
    2274                 :            : {
    2275                 :         73 :   if (dump_file && dump_flags & TDF_DETAILS)
    2276                 :            :     {
    2277                 :          0 :       fprintf (dump_file, "Testing if this predicate: ");
    2278                 :          0 :       dump_pred_info (predicate);
    2279                 :          0 :       fprintf (dump_file, "\n...can be invalidated by a USE guard of: ");
    2280                 :          0 :       dump_pred_chain (use_guard);
    2281                 :            :     }
    2282                 :        318 :   for (size_t i = 0; i < use_guard.length (); ++i)
    2283                 :            :     {
    2284                 :            :       /* NOTE: This is a very simple check, and only understands an
    2285                 :            :          exact opposite.  So, [i == 0] is currently only invalidated
    2286                 :            :          by [.NOT. i == 0] or [i != 0].  Ideally we should also
    2287                 :            :          invalidate with say [i > 5] or [i == 8].  There is certainly
    2288                 :            :          room for improvement here.  */
    2289                 :         98 :       if (pred_neg_p (predicate, use_guard[i]))
    2290                 :            :         {
    2291                 :         12 :           if (dump_file && dump_flags & TDF_DETAILS)
    2292                 :            :             {
    2293                 :          0 :               fprintf (dump_file, "  Predicate was invalidated by: ");
    2294                 :          0 :               dump_pred_info (use_guard[i]);
    2295                 :          0 :               fputc ('\n', dump_file);
    2296                 :            :             }
    2297                 :         12 :           return true;
    2298                 :            :         }
    2299                 :            :     }
    2300                 :            :   return false;
    2301                 :            : }
    2302                 :            : 
    2303                 :            : /* Return TRUE if all predicates in UNINIT_PRED are invalidated by
    2304                 :            :    USE_GUARD being true.  */
    2305                 :            : 
    2306                 :            : static bool
    2307                 :         60 : can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
    2308                 :            :                                   pred_chain use_guard)
    2309                 :            : {
    2310                 :         60 :   if (uninit_pred.is_empty ())
    2311                 :            :     return false;
    2312                 :         60 :   if (dump_file && dump_flags & TDF_DETAILS)
    2313                 :          0 :     dump_predicates (NULL, uninit_pred,
    2314                 :            :                      "Testing if anything here can be invalidated: ");
    2315                 :         72 :   for (size_t i = 0; i < uninit_pred.length (); ++i)
    2316                 :            :     {
    2317                 :         64 :       pred_chain c = uninit_pred[i];
    2318                 :         64 :       size_t j;
    2319                 :        250 :       for (j = 0; j < c.length (); ++j)
    2320                 :         73 :         if (can_one_predicate_be_invalidated_p (c[j], use_guard))
    2321                 :            :           break;
    2322                 :            : 
    2323                 :            :       /* If we were unable to invalidate any predicate in C, then there
    2324                 :            :          is a viable path from entry to the PHI where the PHI takes
    2325                 :            :          an uninitialized value and continues to a use of the PHI.  */
    2326                 :        128 :       if (j == c.length ())
    2327                 :         60 :         return false;
    2328                 :            :     }
    2329                 :            :   return true;
    2330                 :            : }
    2331                 :            : 
    2332                 :            : /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
    2333                 :            :    can actually happen if we arrived at a use for PHI.
    2334                 :            : 
    2335                 :            :    PHI_USE_GUARDS are the guard conditions for the use of the PHI.  */
    2336                 :            : 
    2337                 :            : static bool
    2338                 :        111 : uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
    2339                 :            :                            pred_chain_union phi_use_guards)
    2340                 :            : {
    2341                 :        111 :   unsigned phi_args = gimple_phi_num_args (phi);
    2342                 :        111 :   if (phi_args > max_phi_args)
    2343                 :            :     return false;
    2344                 :            : 
    2345                 :            :   /* PHI_USE_GUARDS are OR'ed together.  If we have more than one
    2346                 :            :      possible guard, there's no way of knowing which guard was true.
    2347                 :            :      Since we need to be absolutely sure that the uninitialized
    2348                 :            :      operands will be invalidated, bail.  */
    2349                 :        111 :   if (phi_use_guards.length () != 1)
    2350                 :            :     return false;
    2351                 :            : 
    2352                 :            :   /* Look for the control dependencies of all the uninitialized
    2353                 :            :      operands and build guard predicates describing them.  */
    2354                 :            :   pred_chain_union uninit_preds;
    2355                 :        159 :   bool ret = true;
    2356                 :        159 :   for (unsigned i = 0; i < phi_args; ++i)
    2357                 :            :     {
    2358                 :        151 :       if (!MASK_TEST_BIT (uninit_opnds, i))
    2359                 :         45 :         continue;
    2360                 :            : 
    2361                 :        106 :       edge e = gimple_phi_arg_edge (phi, i);
    2362                 :        106 :       vec<edge> dep_chains[MAX_NUM_CHAINS];
    2363                 :        114 :       auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
    2364                 :        106 :       size_t num_chains = 0;
    2365                 :        106 :       int num_calls = 0;
    2366                 :            : 
    2367                 :            :       /* Build the control dependency chain for uninit operand `i'...  */
    2368                 :        106 :       uninit_preds = vNULL;
    2369                 :        106 :       if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
    2370                 :            :                                       e->src, dep_chains, &num_chains,
    2371                 :            :                                       &cur_chain, &num_calls))
    2372                 :            :         {
    2373                 :            :           ret = false;
    2374                 :         98 :           break;
    2375                 :            :         }
    2376                 :            :       /* ...and convert it into a set of predicates.  */
    2377                 :         86 :       bool has_valid_preds
    2378                 :         86 :         = convert_control_dep_chain_into_preds (dep_chains, num_chains,
    2379                 :            :                                                 &uninit_preds);
    2380                 :        178 :       for (size_t j = 0; j < num_chains; ++j)
    2381                 :        184 :         dep_chains[j].release ();
    2382                 :         86 :       if (!has_valid_preds)
    2383                 :            :         {
    2384                 :            :           ret = false;
    2385                 :            :           break;
    2386                 :            :         }
    2387                 :         60 :       simplify_preds (&uninit_preds, NULL, false);
    2388                 :         60 :       uninit_preds = normalize_preds (uninit_preds, NULL, false);
    2389                 :            : 
    2390                 :            :       /* Can the guard for this uninitialized operand be invalidated
    2391                 :            :          by the PHI use?  */
    2392                 :         60 :       if (!can_chain_union_be_invalidated_p (uninit_preds, phi_use_guards[0]))
    2393                 :            :         {
    2394                 :            :           ret = false;
    2395                 :            :           break;
    2396                 :            :         }
    2397                 :            :     }
    2398                 :        106 :   destroy_predicate_vecs (&uninit_preds);
    2399                 :        106 :   return ret;
    2400                 :            : }
    2401                 :            : 
    2402                 :            : /* Computes the predicates that guard the use and checks
    2403                 :            :    if the incoming paths that have empty (or possibly
    2404                 :            :    empty) definition can be pruned/filtered.  The function returns
    2405                 :            :    true if it can be determined that the use of PHI's def in
    2406                 :            :    USE_STMT is guarded with a predicate set not overlapping with
    2407                 :            :    predicate sets of all runtime paths that do not have a definition.
    2408                 :            : 
    2409                 :            :    Returns false if it is not or it cannot be determined.  USE_BB is
    2410                 :            :    the bb of the use (for phi operand use, the bb is not the bb of
    2411                 :            :    the phi stmt, but the src bb of the operand edge).
    2412                 :            : 
    2413                 :            :    UNINIT_OPNDS is a bit vector.  If an operand of PHI is uninitialized, the
    2414                 :            :    corresponding bit in the vector is 1.  VISITED_PHIS is a pointer
    2415                 :            :    set of phis being visited.
    2416                 :            : 
    2417                 :            :    *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
    2418                 :            :    If *DEF_PREDS is the empty vector, the defining predicate chains of
    2419                 :            :    PHI will be computed and stored into *DEF_PREDS as needed.
    2420                 :            : 
    2421                 :            :    VISITED_PHIS is a pointer set of phis being visited.  */
    2422                 :            : 
    2423                 :            : static bool
    2424                 :        214 : is_use_properly_guarded (gimple *use_stmt,
    2425                 :            :                          basic_block use_bb,
    2426                 :            :                          gphi *phi,
    2427                 :            :                          unsigned uninit_opnds,
    2428                 :            :                          pred_chain_union *def_preds,
    2429                 :            :                          hash_set<gphi *> *visited_phis)
    2430                 :            : {
    2431                 :        214 :   basic_block phi_bb;
    2432                 :        214 :   pred_chain_union preds = vNULL;
    2433                 :        214 :   bool has_valid_preds = false;
    2434                 :        214 :   bool is_properly_guarded = false;
    2435                 :            : 
    2436                 :        214 :   if (visited_phis->add (phi))
    2437                 :            :     return false;
    2438                 :            : 
    2439                 :        214 :   phi_bb = gimple_bb (phi);
    2440                 :            : 
    2441                 :        214 :   if (is_non_loop_exit_postdominating (use_bb, phi_bb))
    2442                 :            :     return false;
    2443                 :            : 
    2444                 :        151 :   has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
    2445                 :            : 
    2446                 :        151 :   if (!has_valid_preds)
    2447                 :            :     {
    2448                 :         16 :       destroy_predicate_vecs (&preds);
    2449                 :         16 :       return false;
    2450                 :            :     }
    2451                 :            : 
    2452                 :            :   /* Try to prune the dead incoming phi edges.  */
    2453                 :        135 :   is_properly_guarded
    2454                 :        135 :     = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
    2455                 :            :                                                  visited_phis);
    2456                 :            : 
    2457                 :            :   /* We might be able to prove that if the control dependencies
    2458                 :            :      for UNINIT_OPNDS are true, that the control dependencies for
    2459                 :            :      USE_STMT can never be true.  */
    2460                 :        135 :   if (!is_properly_guarded)
    2461                 :        111 :     is_properly_guarded |= uninit_uses_cannot_happen (phi, uninit_opnds,
    2462                 :            :                                                       preds);
    2463                 :            : 
    2464                 :        135 :   if (is_properly_guarded)
    2465                 :            :     {
    2466                 :         32 :       destroy_predicate_vecs (&preds);
    2467                 :         32 :       return true;
    2468                 :            :     }
    2469                 :            : 
    2470                 :        103 :   if (def_preds->is_empty ())
    2471                 :            :     {
    2472                 :         64 :       has_valid_preds = find_def_preds (def_preds, phi);
    2473                 :            : 
    2474                 :         64 :       if (!has_valid_preds)
    2475                 :            :         {
    2476                 :          8 :           destroy_predicate_vecs (&preds);
    2477                 :          8 :           return false;
    2478                 :            :         }
    2479                 :            : 
    2480                 :         56 :       simplify_preds (def_preds, phi, false);
    2481                 :         56 :       *def_preds = normalize_preds (*def_preds, phi, false);
    2482                 :            :     }
    2483                 :            : 
    2484                 :         95 :   simplify_preds (&preds, use_stmt, true);
    2485                 :         95 :   preds = normalize_preds (preds, use_stmt, true);
    2486                 :            : 
    2487                 :         95 :   is_properly_guarded = is_superset_of (*def_preds, preds);
    2488                 :            : 
    2489                 :         95 :   destroy_predicate_vecs (&preds);
    2490                 :         95 :   return is_properly_guarded;
    2491                 :            : }
    2492                 :            : 
    2493                 :            : /* Searches through all uses of a potentially
    2494                 :            :    uninitialized variable defined by PHI and returns a use
    2495                 :            :    statement if the use is not properly guarded.  It returns
    2496                 :            :    NULL if all uses are guarded.  UNINIT_OPNDS is a bitvector
    2497                 :            :    holding the position(s) of uninit PHI operands.  WORKLIST
    2498                 :            :    is the vector of candidate phis that may be updated by this
    2499                 :            :    function.  ADDED_TO_WORKLIST is the pointer set tracking
    2500                 :            :    if the new phi is already in the worklist.  */
    2501                 :            : 
    2502                 :            : static gimple *
    2503                 :        166 : find_uninit_use (gphi *phi, unsigned uninit_opnds,
    2504                 :            :                  vec<gphi *> *worklist,
    2505                 :            :                  hash_set<gphi *> *added_to_worklist)
    2506                 :            : {
    2507                 :        166 :   tree phi_result;
    2508                 :        166 :   use_operand_p use_p;
    2509                 :        166 :   gimple *use_stmt;
    2510                 :        166 :   imm_use_iterator iter;
    2511                 :        166 :   pred_chain_union def_preds = vNULL;
    2512                 :        166 :   gimple *ret = NULL;
    2513                 :            : 
    2514                 :        166 :   phi_result = gimple_phi_result (phi);
    2515                 :            : 
    2516                 :        321 :   FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
    2517                 :            :     {
    2518                 :        250 :       basic_block use_bb;
    2519                 :            : 
    2520                 :        250 :       use_stmt = USE_STMT (use_p);
    2521                 :        250 :       if (is_gimple_debug (use_stmt))
    2522                 :         36 :         continue;
    2523                 :            : 
    2524                 :        214 :       if (gphi *use_phi = dyn_cast<gphi *> (use_stmt))
    2525                 :         70 :         use_bb = gimple_phi_arg_edge (use_phi,
    2526                 :         70 :                                       PHI_ARG_INDEX_FROM_USE (use_p))->src;
    2527                 :            :       else
    2528                 :        144 :         use_bb = gimple_bb (use_stmt);
    2529                 :            : 
    2530                 :        276 :       hash_set<gphi *> visited_phis;
    2531                 :        214 :       if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
    2532                 :            :                                    &def_preds, &visited_phis))
    2533                 :         93 :         continue;
    2534                 :            : 
    2535                 :        157 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2536                 :            :         {
    2537                 :          0 :           fprintf (dump_file, "[CHECK]: Found unguarded use: ");
    2538                 :          0 :           print_gimple_stmt (dump_file, use_stmt, 0);
    2539                 :            :         }
    2540                 :            :       /* Found one real use, return.  */
    2541                 :        157 :       if (gimple_code (use_stmt) != GIMPLE_PHI)
    2542                 :            :         {
    2543                 :         95 :           ret = use_stmt;
    2544                 :         95 :           break;
    2545                 :            :         }
    2546                 :            : 
    2547                 :            :       /* Found a phi use that is not guarded,
    2548                 :            :          add the phi to the worklist.  */
    2549                 :         62 :       if (!added_to_worklist->add (as_a<gphi *> (use_stmt)))
    2550                 :            :         {
    2551                 :         20 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2552                 :            :             {
    2553                 :          0 :               fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
    2554                 :          0 :               print_gimple_stmt (dump_file, use_stmt, 0);
    2555                 :            :             }
    2556                 :            : 
    2557                 :         20 :           worklist->safe_push (as_a<gphi *> (use_stmt));
    2558                 :         20 :           possibly_undefined_names->add (phi_result);
    2559                 :            :         }
    2560                 :            :     }
    2561                 :            : 
    2562                 :        166 :   destroy_predicate_vecs (&def_preds);
    2563                 :        166 :   return ret;
    2564                 :            : }
    2565                 :            : 
    2566                 :            : /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
    2567                 :            :    and gives warning if there exists a runtime path from the entry to a
    2568                 :            :    use of the PHI def that does not contain a definition.  In other words,
    2569                 :            :    the warning is on the real use.  The more dead paths that can be pruned
    2570                 :            :    by the compiler, the fewer false positives the warning is.  WORKLIST
    2571                 :            :    is a vector of candidate phis to be examined.  ADDED_TO_WORKLIST is
    2572                 :            :    a pointer set tracking if the new phi is added to the worklist or not.  */
    2573                 :            : 
    2574                 :            : static void
    2575                 :        193 : warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
    2576                 :            :                         hash_set<gphi *> *added_to_worklist)
    2577                 :            : {
    2578                 :        193 :   unsigned uninit_opnds;
    2579                 :        193 :   gimple *uninit_use_stmt = 0;
    2580                 :        193 :   tree uninit_op;
    2581                 :        193 :   int phiarg_index;
    2582                 :        193 :   location_t loc;
    2583                 :            : 
    2584                 :            :   /* Don't look at virtual operands.  */
    2585                 :        386 :   if (virtual_operand_p (gimple_phi_result (phi)))
    2586                 :            :     return;
    2587                 :            : 
    2588                 :        193 :   uninit_opnds = compute_uninit_opnds_pos (phi);
    2589                 :            : 
    2590                 :        193 :   if (MASK_EMPTY (uninit_opnds))
    2591                 :            :     return;
    2592                 :            : 
    2593                 :        166 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2594                 :            :     {
    2595                 :          0 :       fprintf (dump_file, "[CHECK]: examining phi: ");
    2596                 :          0 :       print_gimple_stmt (dump_file, phi, 0);
    2597                 :            :     }
    2598                 :            : 
    2599                 :            :   /* Now check if we have any use of the value without proper guard.  */
    2600                 :        166 :   uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
    2601                 :            :                                      worklist, added_to_worklist);
    2602                 :            : 
    2603                 :            :   /* All uses are properly guarded.  */
    2604                 :        166 :   if (!uninit_use_stmt)
    2605                 :            :     return;
    2606                 :            : 
    2607                 :        154 :   phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
    2608                 :         95 :   uninit_op = gimple_phi_arg_def (phi, phiarg_index);
    2609                 :         95 :   if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
    2610                 :            :     return;
    2611                 :         95 :   if (gimple_phi_arg_has_location (phi, phiarg_index))
    2612                 :            :     loc = gimple_phi_arg_location (phi, phiarg_index);
    2613                 :            :   else
    2614                 :            :     loc = UNKNOWN_LOCATION;
    2615                 :         95 :   warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
    2616                 :         95 :                SSA_NAME_VAR (uninit_op),
    2617                 :            :                "%qD may be used uninitialized in this function",
    2618                 :            :                uninit_use_stmt, loc);
    2619                 :            : }
    2620                 :            : 
    2621                 :            : static bool
    2622                 :    2528420 : gate_warn_uninitialized (void)
    2623                 :            : {
    2624                 :    2352490 :   return warn_uninitialized || warn_maybe_uninitialized;
    2625                 :            : }
    2626                 :            : 
    2627                 :            : namespace {
    2628                 :            : 
    2629                 :            : const pass_data pass_data_late_warn_uninitialized =
    2630                 :            : {
    2631                 :            :   GIMPLE_PASS, /* type */
    2632                 :            :   "uninit", /* name */
    2633                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    2634                 :            :   TV_NONE, /* tv_id */
    2635                 :            :   PROP_ssa, /* properties_required */
    2636                 :            :   0, /* properties_provided */
    2637                 :            :   0, /* properties_destroyed */
    2638                 :            :   0, /* todo_flags_start */
    2639                 :            :   0, /* todo_flags_finish */
    2640                 :            : };
    2641                 :            : 
    2642                 :            : class pass_late_warn_uninitialized : public gimple_opt_pass
    2643                 :            : {
    2644                 :            : public:
    2645                 :     401080 :   pass_late_warn_uninitialized (gcc::context *ctxt)
    2646                 :     802160 :     : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
    2647                 :            :   {}
    2648                 :            : 
    2649                 :            :   /* opt_pass methods: */
    2650                 :     200540 :   opt_pass *clone () { return new pass_late_warn_uninitialized (m_ctxt); }
    2651                 :     687615 :   virtual bool gate (function *) { return gate_warn_uninitialized (); }
    2652                 :            :   virtual unsigned int execute (function *);
    2653                 :            : 
    2654                 :            : }; // class pass_late_warn_uninitialized
    2655                 :            : 
    2656                 :            : unsigned int
    2657                 :      59737 : pass_late_warn_uninitialized::execute (function *fun)
    2658                 :            : {
    2659                 :      59737 :   basic_block bb;
    2660                 :      59737 :   gphi_iterator gsi;
    2661                 :      59737 :   vec<gphi *> worklist = vNULL;
    2662                 :            : 
    2663                 :      59737 :   calculate_dominance_info (CDI_DOMINATORS);
    2664                 :      59737 :   calculate_dominance_info (CDI_POST_DOMINATORS);
    2665                 :            :   /* Re-do the plain uninitialized variable check, as optimization may have
    2666                 :            :      straightened control flow.  Do this first so that we don't accidentally
    2667                 :            :      get a "may be" warning when we'd have seen an "is" warning later.  */
    2668                 :      59737 :   warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
    2669                 :            : 
    2670                 :      59737 :   timevar_push (TV_TREE_UNINIT);
    2671                 :            : 
    2672                 :      59737 :   possibly_undefined_names = new hash_set<tree>;
    2673                 :      59737 :   hash_set<gphi *> added_to_worklist;
    2674                 :            : 
    2675                 :            :   /* Initialize worklist  */
    2676                 :    1071600 :   FOR_EACH_BB_FN (bb, fun)
    2677                 :    1468630 :     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2678                 :            :       {
    2679                 :     456758 :         gphi *phi = gsi.phi ();
    2680                 :     456758 :         size_t n, i;
    2681                 :            : 
    2682                 :     456758 :         n = gimple_phi_num_args (phi);
    2683                 :            : 
    2684                 :            :         /* Don't look at virtual operands.  */
    2685                 :     913516 :         if (virtual_operand_p (gimple_phi_result (phi)))
    2686                 :     170690 :           continue;
    2687                 :            : 
    2688                 :     953136 :         for (i = 0; i < n; ++i)
    2689                 :            :           {
    2690                 :     667241 :             tree op = gimple_phi_arg_def (phi, i);
    2691                 :     667241 :             if (TREE_CODE (op) == SSA_NAME && uninit_undefined_value_p (op))
    2692                 :            :               {
    2693                 :        173 :                 worklist.safe_push (phi);
    2694                 :        173 :                 added_to_worklist.add (phi);
    2695                 :        173 :                 if (dump_file && (dump_flags & TDF_DETAILS))
    2696                 :            :                   {
    2697                 :          0 :                     fprintf (dump_file, "[WORKLIST]: add to initial list: ");
    2698                 :          0 :                     print_gimple_stmt (dump_file, phi, 0);
    2699                 :            :                   }
    2700                 :            :                 break;
    2701                 :            :               }
    2702                 :            :           }
    2703                 :            :       }
    2704                 :            : 
    2705                 :      59930 :   while (worklist.length () != 0)
    2706                 :            :     {
    2707                 :        193 :       gphi *cur_phi = 0;
    2708                 :        193 :       cur_phi = worklist.pop ();
    2709                 :        193 :       warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
    2710                 :            :     }
    2711                 :            : 
    2712                 :      59737 :   worklist.release ();
    2713                 :     119474 :   delete possibly_undefined_names;
    2714                 :      59737 :   possibly_undefined_names = NULL;
    2715                 :      59737 :   free_dominance_info (CDI_POST_DOMINATORS);
    2716                 :      59737 :   timevar_pop (TV_TREE_UNINIT);
    2717                 :      59737 :   return 0;
    2718                 :            : }
    2719                 :            : 
    2720                 :            : } // anon namespace
    2721                 :            : 
    2722                 :            : gimple_opt_pass *
    2723                 :     200540 : make_pass_late_warn_uninitialized (gcc::context *ctxt)
    2724                 :            : {
    2725                 :     200540 :   return new pass_late_warn_uninitialized (ctxt);
    2726                 :            : }
    2727                 :            : 
    2728                 :            : static unsigned int
    2729                 :     116352 : execute_early_warn_uninitialized (void)
    2730                 :            : {
    2731                 :            :   /* Currently, this pass runs always but
    2732                 :            :      execute_late_warn_uninitialized only runs with optimization.  With
    2733                 :            :      optimization we want to warn about possible uninitialized as late
    2734                 :            :      as possible, thus don't do it here.  However, without
    2735                 :            :      optimization we need to warn here about "may be uninitialized".  */
    2736                 :     116352 :   calculate_dominance_info (CDI_POST_DOMINATORS);
    2737                 :            : 
    2738                 :     116352 :   warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
    2739                 :            : 
    2740                 :            :   /* Post-dominator information cannot be reliably updated.  Free it
    2741                 :            :      after the use.  */
    2742                 :            : 
    2743                 :     116352 :   free_dominance_info (CDI_POST_DOMINATORS);
    2744                 :     116352 :   return 0;
    2745                 :            : }
    2746                 :            : 
    2747                 :            : namespace {
    2748                 :            : 
    2749                 :            : const pass_data pass_data_early_warn_uninitialized =
    2750                 :            : {
    2751                 :            :   GIMPLE_PASS, /* type */
    2752                 :            :   "*early_warn_uninitialized", /* name */
    2753                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    2754                 :            :   TV_TREE_UNINIT, /* tv_id */
    2755                 :            :   PROP_ssa, /* properties_required */
    2756                 :            :   0, /* properties_provided */
    2757                 :            :   0, /* properties_destroyed */
    2758                 :            :   0, /* todo_flags_start */
    2759                 :            :   0, /* todo_flags_finish */
    2760                 :            : };
    2761                 :            : 
    2762                 :            : class pass_early_warn_uninitialized : public gimple_opt_pass
    2763                 :            : {
    2764                 :            : public:
    2765                 :     200540 :   pass_early_warn_uninitialized (gcc::context *ctxt)
    2766                 :     401080 :     : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
    2767                 :            :   {}
    2768                 :            : 
    2769                 :            :   /* opt_pass methods: */
    2770                 :    1840810 :   virtual bool gate (function *) { return gate_warn_uninitialized (); }
    2771                 :     116352 :   virtual unsigned int execute (function *)
    2772                 :            :   {
    2773                 :     116352 :     return execute_early_warn_uninitialized ();
    2774                 :            :   }
    2775                 :            : 
    2776                 :            : }; // class pass_early_warn_uninitialized
    2777                 :            : 
    2778                 :            : } // anon namespace
    2779                 :            : 
    2780                 :            : gimple_opt_pass *
    2781                 :     200540 : make_pass_early_warn_uninitialized (gcc::context *ctxt)
    2782                 :            : {
    2783                 :     200540 :   return new pass_early_warn_uninitialized (ctxt);
    2784                 :            : }

Generated by: LCOV version 1.0

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