gcc/tree-ssa-uninit.c

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