gcc/tree-ssa-uninit.c

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