OSDN Git Service

* diagnostic.c: Don't include tm.h, tree.h, tm_p.h, langhooks.h or
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-uninit.c
1 /* Predicate aware uninitialized variable warning.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2010 Free Software
3    Foundation, Inc.
4    Contributed by Xinliang David Li <davidxl@google.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "flags.h"
28 #include "tm_p.h"
29 #include "langhooks.h"
30 #include "basic-block.h"
31 #include "output.h"
32 #include "expr.h"
33 #include "function.h"
34 #include "diagnostic.h"
35 #include "gimple-pretty-print.h"
36 #include "bitmap.h"
37 #include "pointer-set.h"
38 #include "tree-flow.h"
39 #include "gimple.h"
40 #include "tree-inline.h"
41 #include "timevar.h"
42 #include "hashtab.h"
43 #include "tree-dump.h"
44 #include "tree-pass.h"
45 #include "toplev.h"
46 #include "timevar.h"
47
48 /* This implements the pass that does predicate aware warning on uses of
49    possibly uninitialized variables. The pass first collects the set of
50    possibly uninitialized SSA names. For each such name, it walks through
51    all its immediate uses. For each immediate use, it rebuilds the condition
52    expression (the predicate) that guards the use. The predicate is then
53    examined to see if the variable is always defined under that same condition.
54    This is done either by pruning the unrealizable paths that lead to the
55    default definitions or by checking if the predicate set that guards the
56    defining paths is a superset of the use predicate.  */
57
58
59 /* Pointer set of potentially undefined ssa names, i.e.,
60    ssa names that are defined by phi with operands that
61    are not defined or potentially undefined.  */
62 static struct pointer_set_t *possibly_undefined_names = 0;
63
64 /* Bit mask handling macros.  */
65 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
66 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
67 #define MASK_EMPTY(mask) (mask == 0)
68
69 /* Returns the first bit position (starting from LSB)
70    in mask that is non zero. Returns -1 if the mask is empty.  */
71 static int
72 get_mask_first_set_bit (unsigned mask)
73 {
74   int pos = 0;
75   if (mask == 0)
76     return -1;
77
78   while ((mask & (1 << pos)) == 0)
79     pos++;
80
81   return pos;
82 }
83 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
84
85
86 /* Return true if T, an SSA_NAME, has an undefined value.  */
87
88 bool
89 ssa_undefined_value_p (tree t)
90 {
91   tree var = SSA_NAME_VAR (t);
92
93   /* Parameters get their initial value from the function entry.  */
94   if (TREE_CODE (var) == PARM_DECL)
95     return false;
96
97   /* Hard register variables get their initial value from the ether.  */
98   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
99     return false;
100
101   /* The value is undefined iff its definition statement is empty.  */
102   return (gimple_nop_p (SSA_NAME_DEF_STMT (t))
103           || (possibly_undefined_names
104               && pointer_set_contains (possibly_undefined_names, t)));
105 }
106
107 /* Checks if the operand OPND of PHI is defined by 
108    another phi with one operand defined by this PHI, 
109    but the rest operands are all defined. If yes, 
110    returns true to skip this this operand as being
111    redundant. Can be enhanced to be more general.  */
112
113 static bool
114 can_skip_redundant_opnd (tree opnd, gimple phi)
115 {
116   gimple op_def;
117   tree phi_def;
118   int i, n;
119
120   phi_def = gimple_phi_result (phi);
121   op_def = SSA_NAME_DEF_STMT (opnd);
122   if (gimple_code (op_def) != GIMPLE_PHI)
123     return false;
124   n = gimple_phi_num_args (op_def);
125   for (i = 0; i < n; ++i)
126     {
127       tree op = gimple_phi_arg_def (op_def, i);
128       if (TREE_CODE (op) != SSA_NAME)
129         continue;
130       if (op != phi_def && ssa_undefined_value_p (op))
131         return false;
132     }
133
134   return true;
135 }
136
137 /* Returns a bit mask holding the positions of arguments in PHI
138    that have empty (or possibly empty) definitions.  */
139
140 static unsigned
141 compute_uninit_opnds_pos (gimple phi)
142 {
143   size_t i, n;
144   unsigned uninit_opnds = 0;
145
146   n = gimple_phi_num_args (phi);
147
148   for (i = 0; i < n; ++i)
149     {
150       tree op = gimple_phi_arg_def (phi, i);
151       if (TREE_CODE (op) == SSA_NAME
152           && ssa_undefined_value_p (op)
153           && !can_skip_redundant_opnd (op, phi))
154         MASK_SET_BIT (uninit_opnds, i);
155     }
156   return uninit_opnds;
157 }
158
159 /* Find the immediate postdominator PDOM of the specified
160    basic block BLOCK.  */
161
162 static inline basic_block
163 find_pdom (basic_block block)
164 {
165    if (block == EXIT_BLOCK_PTR)
166      return EXIT_BLOCK_PTR;
167    else
168      {
169        basic_block bb
170            = get_immediate_dominator (CDI_POST_DOMINATORS, block);
171        if (! bb)
172          return EXIT_BLOCK_PTR;
173        return bb;
174      }
175 }
176
177 /* Find the immediate DOM of the specified
178    basic block BLOCK.  */
179
180 static inline basic_block
181 find_dom (basic_block block)
182 {
183    if (block == ENTRY_BLOCK_PTR)
184      return ENTRY_BLOCK_PTR;
185    else
186      {
187        basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
188        if (! bb)
189          return ENTRY_BLOCK_PTR;
190        return bb;
191      }
192 }
193
194 /* Returns true if BB1 is postdominating BB2 and BB1 is
195    not a loop exit bb. The loop exit bb check is simple and does
196    not cover all cases.  */
197
198 static bool
199 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
200 {
201   if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
202     return false;
203
204   if (single_pred_p (bb1) && !single_succ_p (bb2))
205     return false;
206
207   return true;
208 }
209
210 /* Find the closest postdominator of a specified BB, which is control
211    equivalent to BB.  */
212
213 static inline  basic_block
214 find_control_equiv_block (basic_block bb)
215 {
216   basic_block pdom;
217
218   pdom = find_pdom (bb);
219
220   /* Skip the postdominating bb that is also loop exit.  */
221   if (!is_non_loop_exit_postdominating (pdom, bb))
222     return NULL;
223
224   if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
225     return pdom;
226
227   return NULL;
228 }
229
230 #define MAX_NUM_CHAINS 8
231 #define MAX_CHAIN_LEN 5
232
233 /* Computes the control dependence chains (paths of edges)
234    for DEP_BB up to the dominating basic block BB (the head node of a
235    chain should be dominated by it).  CD_CHAINS is pointer to a
236    dynamic array holding the result chains. CUR_CD_CHAIN is the current
237    chain being computed.  *NUM_CHAINS is total number of chains.  The
238    function returns true if the information is successfully computed,
239    return false if there is no control dependence or not computed.  */
240
241 static bool
242 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
243                            VEC(edge, heap) **cd_chains,
244                            size_t *num_chains,
245                            VEC(edge, heap) **cur_cd_chain)
246 {
247   edge_iterator ei;
248   edge e;
249   size_t i;
250   bool found_cd_chain = false;
251   size_t cur_chain_len = 0;
252
253   if (EDGE_COUNT (bb->succs) < 2)
254     return false;
255
256   /* Could  use a set instead.  */
257   cur_chain_len = VEC_length (edge, *cur_cd_chain);
258   if (cur_chain_len > MAX_CHAIN_LEN)
259     return false;
260
261   for (i = 0; i < cur_chain_len; i++)
262     {
263       edge e = VEC_index (edge, *cur_cd_chain, i);
264       /* cycle detected. */
265       if (e->src == bb)
266         return false;
267     }
268
269   FOR_EACH_EDGE (e, ei, bb->succs)
270     {
271       basic_block cd_bb;
272       if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
273         continue;
274
275       cd_bb = e->dest;
276       VEC_safe_push (edge, heap, *cur_cd_chain, e);
277       while (!is_non_loop_exit_postdominating (cd_bb, bb))
278         {
279           if (cd_bb == dep_bb)
280             {
281               /* Found a direct control dependence.  */
282               if (*num_chains < MAX_NUM_CHAINS)
283                 {
284                   cd_chains[*num_chains]
285                       = VEC_copy (edge, heap, *cur_cd_chain);
286                   (*num_chains)++;
287                 }
288               found_cd_chain = true;
289               /* check path from next edge.  */
290               break;
291             }
292
293           /* Now check if DEP_BB is indirectly control dependent on BB.  */
294           if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
295                                          num_chains, cur_cd_chain))
296             {
297               found_cd_chain = true;
298               break;
299             }
300
301           cd_bb = find_pdom (cd_bb);
302           if (cd_bb == EXIT_BLOCK_PTR)
303             break;
304         }
305       VEC_pop (edge, *cur_cd_chain);
306       gcc_assert (VEC_length (edge, *cur_cd_chain) == cur_chain_len);
307     }
308   gcc_assert (VEC_length (edge, *cur_cd_chain) == cur_chain_len);
309
310   return found_cd_chain;
311 }
312
313 typedef struct use_pred_info
314 {
315   gimple cond;
316   bool invert;
317 } *use_pred_info_t;
318
319 DEF_VEC_P(use_pred_info_t);
320 DEF_VEC_ALLOC_P(use_pred_info_t, heap);
321
322
323 /* Converts the chains of control dependence edges into a set of
324    predicates. A control dependence chain is represented by a vector
325    edges. DEP_CHAINS points to an array of dependence chains.
326    NUM_CHAINS is the size of the chain array. One edge in a dependence
327    chain is mapped to predicate expression represented by use_pred_info_t
328    type. One dependence chain is converted to a composite predicate that
329    is the result of AND operation of use_pred_info_t mapped to each edge.
330    A composite predicate is presented by a vector of use_pred_info_t. On
331    return, *PREDS points to the resulting array of composite predicates.
332    *NUM_PREDS is the number of composite predictes.  */
333
334 static bool
335 convert_control_dep_chain_into_preds (VEC(edge, heap) **dep_chains,
336                                       size_t num_chains,
337                                       VEC(use_pred_info_t, heap) ***preds,
338                                       size_t *num_preds)
339 {
340   bool has_valid_pred = false;
341   size_t i, j;
342   if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
343     return false;
344
345   /* Now convert CD chains into predicates  */
346   has_valid_pred = true;
347
348   /* Now convert the control dep chain into a set
349      of predicates.  */
350   *preds = XCNEWVEC (VEC(use_pred_info_t, heap) *,
351                      num_chains);
352   *num_preds = num_chains;
353
354   for (i = 0; i < num_chains; i++)
355     {
356       VEC(edge, heap) *one_cd_chain = dep_chains[i];
357       for (j = 0; j < VEC_length (edge, one_cd_chain); j++)
358         {
359           gimple cond_stmt;
360           gimple_stmt_iterator gsi;
361           basic_block guard_bb;
362           use_pred_info_t one_pred;
363           edge e;
364
365           e = VEC_index (edge, one_cd_chain, j);
366           guard_bb = e->src;
367           gsi = gsi_last_bb (guard_bb);
368           if (gsi_end_p (gsi))
369             {
370               has_valid_pred = false;
371               break;
372             }
373           cond_stmt = gsi_stmt (gsi);
374           if (gimple_code (cond_stmt) == GIMPLE_CALL
375               && EDGE_COUNT (e->src->succs) >= 2)
376             {
377               /* Ignore EH edge. Can add assertion
378                  on the other edge's flag.  */
379               continue;
380             }
381           /* Skip if there is essentially one succesor.  */
382           if (EDGE_COUNT (e->src->succs) == 2)
383             {
384               edge e1;
385               edge_iterator ei1;
386               bool skip = false;
387
388               FOR_EACH_EDGE (e1, ei1, e->src->succs)
389                 {
390                   if (EDGE_COUNT (e1->dest->succs) == 0)
391                     {
392                       skip = true;
393                       break;
394                     }
395                 }
396               if (skip)
397                 continue;
398             }
399           if (gimple_code (cond_stmt) != GIMPLE_COND)
400             {
401               has_valid_pred = false;
402               break;
403             }
404           one_pred = XNEW (struct use_pred_info);
405           one_pred->cond = cond_stmt;
406           one_pred->invert = !!(e->flags & EDGE_FALSE_VALUE);
407           VEC_safe_push (use_pred_info_t, heap, (*preds)[i], one_pred);
408         }
409
410       if (!has_valid_pred)
411         break;
412     }
413   return has_valid_pred;
414 }
415
416 /* Computes all control dependence chains for USE_BB. The control
417    dependence chains are then converted to an array of composite
418    predicates pointed to by PREDS.  PHI_BB is the basic block of
419    the phi whose result is used in USE_BB.  */
420
421 static bool
422 find_predicates (VEC(use_pred_info_t, heap) ***preds,
423                  size_t *num_preds,
424                  basic_block phi_bb,
425                  basic_block use_bb)
426 {
427   size_t num_chains = 0, i;
428   VEC(edge, heap) **dep_chains = 0;
429   VEC(edge, heap) *cur_chain = 0;
430   bool has_valid_pred = false;
431   basic_block cd_root = 0;
432
433   dep_chains = XCNEWVEC (VEC(edge, heap) *, MAX_NUM_CHAINS);
434
435   /* First find the closest bb that is control equivalent to PHI_BB
436      that also dominates USE_BB.  */
437   cd_root = phi_bb;
438   while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
439     {
440       basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
441       if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
442         cd_root = ctrl_eq_bb;
443       else
444         break;
445     }
446
447   compute_control_dep_chain (cd_root, use_bb,
448                              dep_chains, &num_chains,
449                              &cur_chain);
450
451   has_valid_pred
452       = convert_control_dep_chain_into_preds (dep_chains,
453                                               num_chains,
454                                               preds,
455                                               num_preds);
456   /* Free individual chain  */
457   VEC_free (edge, heap, cur_chain);
458   for (i = 0; i < num_chains; i++)
459       VEC_free (edge, heap, dep_chains[i]);
460   free (dep_chains);
461   return has_valid_pred;
462 }
463
464 /* Computes the set of incoming edges of PHI that have non empty
465    definitions of a phi chain.  The collection will be done
466    recursively on operands that are defined by phis. CD_ROOT
467    is the control dependence root. *EDGES holds the result, and
468    VISITED_PHIS is a pointer set for detecting cycles.  */
469
470 static void
471 collect_phi_def_edges (gimple phi, basic_block cd_root,
472                        VEC(edge, heap) **edges,
473                        struct pointer_set_t *visited_phis)
474 {
475   size_t i, n;
476   edge opnd_edge;
477   tree opnd;
478
479   if (pointer_set_insert (visited_phis, phi))
480     return;
481
482   n = gimple_phi_num_args (phi);
483   for (i = 0; i < n; i++)
484     {
485       opnd_edge = gimple_phi_arg_edge (phi, i);
486       opnd = gimple_phi_arg_def (phi, i);
487
488       if (TREE_CODE (opnd) != SSA_NAME
489           || !ssa_undefined_value_p (opnd))
490         VEC_safe_push (edge, heap, *edges, opnd_edge);
491       else
492         {
493           gimple def = SSA_NAME_DEF_STMT (opnd);
494           if (gimple_code (def) == GIMPLE_PHI
495               && dominated_by_p (CDI_DOMINATORS,
496                                  gimple_bb (def), cd_root))
497             collect_phi_def_edges (def, cd_root, edges,
498                                    visited_phis);
499         }
500     }
501 }
502
503 /* For each use edge of PHI, computes all control dependence chains.
504    The control dependence chains are then converted to an array of
505    composite predicates pointed to by PREDS.  */
506
507 static bool
508 find_def_preds (VEC(use_pred_info_t, heap) ***preds,
509                 size_t *num_preds, gimple phi)
510 {
511   size_t num_chains = 0, i, n;
512   VEC(edge, heap) **dep_chains = 0;
513   VEC(edge, heap) *cur_chain = 0;
514   VEC(edge, heap) *def_edges = 0;
515   bool has_valid_pred = false;
516   basic_block phi_bb, cd_root = 0;
517   struct pointer_set_t *visited_phis;
518
519   dep_chains = XCNEWVEC (VEC(edge, heap) *, MAX_NUM_CHAINS);
520
521   phi_bb = gimple_bb (phi);
522   /* First find the closest dominating bb to be
523      the control dependence root  */
524   cd_root = find_dom (phi_bb);
525   if (!cd_root)
526     return false;
527
528   visited_phis = pointer_set_create ();
529   collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis);
530   pointer_set_destroy (visited_phis);
531
532   n = VEC_length (edge, def_edges);
533   if (n == 0)
534     return false;
535
536   for (i = 0; i < n; i++)
537     {
538       size_t prev_nc, j;
539       edge opnd_edge;
540
541       opnd_edge = VEC_index (edge, def_edges, i);
542       prev_nc = num_chains;
543       compute_control_dep_chain (cd_root, opnd_edge->src,
544                                  dep_chains, &num_chains,
545                                  &cur_chain);
546       /* Free individual chain  */
547       VEC_free (edge, heap, cur_chain);
548       cur_chain = 0;
549
550       /* Now update the newly added chains with
551          the phi operand edge:  */
552       if (EDGE_COUNT (opnd_edge->src->succs) > 1)
553         {
554           if (prev_nc == num_chains
555               && num_chains < MAX_NUM_CHAINS)
556             num_chains++;
557           for (j = prev_nc; j < num_chains; j++)
558             {
559               VEC_safe_push (edge, heap, dep_chains[j], opnd_edge);
560             }
561         }
562     }
563
564   has_valid_pred
565       = convert_control_dep_chain_into_preds (dep_chains,
566                                               num_chains,
567                                               preds,
568                                               num_preds);
569   for (i = 0; i < num_chains; i++)
570       VEC_free (edge, heap, dep_chains[i]);
571   free (dep_chains);
572   return has_valid_pred;
573 }
574
575 /* Dumps the predicates (PREDS) for USESTMT.  */
576
577 static void
578 dump_predicates (gimple usestmt, size_t num_preds,
579                  VEC(use_pred_info_t, heap) **preds,
580                  const char* msg)
581 {
582   size_t i, j;
583   VEC(use_pred_info_t, heap) *one_pred_chain;
584   fprintf (dump_file, msg);
585   print_gimple_stmt (dump_file, usestmt, 0, 0);
586   fprintf (dump_file, "is guarded by :\n");
587   /* do some dumping here:  */
588   for (i = 0; i < num_preds; i++)
589     {
590       size_t np;
591
592       one_pred_chain = preds[i];
593       np = VEC_length (use_pred_info_t, one_pred_chain);
594
595       for (j = 0; j < np; j++)
596         {
597           use_pred_info_t one_pred
598               = VEC_index (use_pred_info_t, one_pred_chain, j);
599           if (one_pred->invert)
600             fprintf (dump_file, " (.NOT.) ");
601           print_gimple_stmt (dump_file, one_pred->cond, 0, 0);
602           if (j < np - 1)
603             fprintf (dump_file, "(.AND.)\n");
604         }
605       if (i < num_preds - 1)
606         fprintf (dump_file, "(.OR.)\n");
607     }
608 }
609
610 /* Destroys the predicate set *PREDS.  */
611
612 static void
613 destroy_predicate_vecs (size_t n,
614                         VEC(use_pred_info_t, heap) ** preds)
615 {
616   size_t i, j;
617   for (i = 0; i < n; i++)
618     {
619       for (j = 0; j < VEC_length (use_pred_info_t, preds[i]); j++)
620         free (VEC_index (use_pred_info_t, preds[i], j));
621       VEC_free (use_pred_info_t, heap, preds[i]);
622     }
623   free (preds);
624 }
625
626
627 /* Computes the 'normalized' conditional code with operand 
628    swapping and condition inversion.  */
629
630 static enum tree_code
631 get_cmp_code (enum tree_code orig_cmp_code,
632               bool swap_cond, bool invert)
633 {
634   enum tree_code tc = orig_cmp_code;
635
636   if (swap_cond)
637     tc = swap_tree_comparison (orig_cmp_code);
638   if (invert)
639     tc = invert_tree_comparison (tc, false);
640
641   switch (tc)
642     {
643     case LT_EXPR:
644     case LE_EXPR:
645     case GT_EXPR:
646     case GE_EXPR:
647     case EQ_EXPR:
648     case NE_EXPR:
649       break;
650     default:
651       return ERROR_MARK;
652     }
653   return tc;
654 }
655
656 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
657    all values in the range satisfies (x CMPC BOUNDARY) == true.  */
658
659 static bool
660 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
661 {
662   bool inverted = false;
663   bool is_unsigned;
664   bool result;
665
666   /* Only handle integer constant here.  */
667   if (TREE_CODE (val) != INTEGER_CST
668       || TREE_CODE (boundary) != INTEGER_CST)
669     return true;
670
671   is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
672
673   if (cmpc == GE_EXPR || cmpc == GT_EXPR
674       || cmpc == NE_EXPR)
675     {
676       cmpc = invert_tree_comparison (cmpc, false);
677       inverted = true;
678     }
679
680   if (is_unsigned)
681     {
682       if (cmpc == EQ_EXPR)
683         result = tree_int_cst_equal (val, boundary);
684       else if (cmpc == LT_EXPR)
685         result = INT_CST_LT_UNSIGNED (val, boundary);
686       else
687         {
688           gcc_assert (cmpc == LE_EXPR);
689           result = (tree_int_cst_equal (val, boundary)
690                     || INT_CST_LT_UNSIGNED (val, boundary));
691         }
692     }
693   else
694     {
695       if (cmpc == EQ_EXPR)
696         result = tree_int_cst_equal (val, boundary);
697       else if (cmpc == LT_EXPR)
698         result = INT_CST_LT (val, boundary);
699       else
700         {
701           gcc_assert (cmpc == LE_EXPR);
702           result = (tree_int_cst_equal (val, boundary)
703                     || INT_CST_LT (val, boundary));
704         }
705     }
706
707   if (inverted)
708     result ^= 1;
709
710   return result;
711 }
712
713 /* Returns true if PRED is common among all the predicate
714    chains (PREDS) (and therefore can be factored out).
715    NUM_PRED_CHAIN is the size of array PREDS.  */
716
717 static bool
718 find_matching_predicate_in_rest_chains (use_pred_info_t pred,
719                                         VEC(use_pred_info_t, heap) **preds,
720                                         size_t num_pred_chains)
721 {
722   size_t i, j, n;
723
724   /* trival case  */
725   if (num_pred_chains == 1)
726     return true;
727
728   for (i = 1; i < num_pred_chains; i++)
729     {
730       bool found = false;
731       VEC(use_pred_info_t, heap) *one_chain = preds[i];
732       n = VEC_length (use_pred_info_t, one_chain);
733       for (j = 0; j < n; j++)
734         {
735           use_pred_info_t pred2
736               = VEC_index (use_pred_info_t, one_chain, j);
737           /* can relax the condition comparison to not
738              use address comparison. However, the most common
739              case is that multiple control dependent paths share
740              a common path prefix, so address comparison should
741              be ok.  */
742
743           if (pred2->cond == pred->cond
744               && pred2->invert == pred->invert)
745             {
746               found = true;
747               break;
748             }
749         }
750       if (!found)
751         return false;
752     }
753   return true;
754 }
755
756 /* Forward declaration.  */
757 static bool
758 is_use_properly_guarded (gimple use_stmt,
759                          basic_block use_bb,
760                          gimple phi,
761                          unsigned uninit_opnds,
762                          struct pointer_set_t *visited_phis);
763
764 /* A helper function that determines if the predicate set
765    of the use is not overlapping with that of the uninit paths.
766    The most common senario of guarded use is in Example 1:
767      Example 1:
768            if (some_cond)
769            {
770               x = ...;
771               flag = true;
772            }
773
774             ... some code ...
775
776            if (flag)
777               use (x);
778
779      The real world examples are usually more complicated, but similar
780      and usually result from inlining:
781
782          bool init_func (int * x)
783          {
784              if (some_cond)
785                 return false;
786              *x  =  ..
787              return true;
788          }
789
790          void foo(..)
791          {
792              int x;
793
794              if (!init_func(&x))
795                 return;
796
797              .. some_code ...
798              use (x);
799          }
800
801      Another possible use scenario is in the following trivial example:
802
803      Example 2:
804           if (n > 0)
805              x = 1;
806           ...
807           if (n > 0)
808             {
809               if (m < 2)
810                  .. = x;
811             }
812
813      Predicate analysis needs to compute the composite predicate:
814
815        1) 'x' use predicate: (n > 0) .AND. (m < 2)
816        2) 'x' default value  (non-def) predicate: .NOT. (n > 0)
817        (the predicate chain for phi operand defs can be computed
818        starting from a bb that is control equivalent to the phi's
819        bb and is dominating the operand def.)
820
821        and check overlapping:
822           (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
823         <==> false
824
825      This implementation provides framework that can handle
826      scenarios. (Note that many simple cases are handled properly
827      without the predicate analysis -- this is due to jump threading
828      transformation which eliminates the merge point thus makes
829      path sensitive analysis unnecessary.)
830
831      NUM_PREDS is the number is the number predicate chains, PREDS is
832      the array of chains, PHI is the phi node whose incoming (undefined)
833      paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
834      uninit operand positions. VISITED_PHIS is the pointer set of phi
835      stmts being checked.  */
836
837
838 static bool
839 use_pred_not_overlap_with_undef_path_pred (
840     size_t num_preds,
841     VEC(use_pred_info_t, heap) **preds,
842     gimple phi, unsigned uninit_opnds,
843     struct pointer_set_t *visited_phis)
844 {
845   unsigned int i, n;
846   gimple flag_def = 0;
847   tree  boundary_cst = 0;
848   enum tree_code cmp_code;
849   bool swap_cond = false;
850   bool invert = false;
851   VEC(use_pred_info_t, heap) *the_pred_chain;
852
853   gcc_assert (num_preds > 0);
854   /* Find within the common prefix of multiple predicate chains
855      a predicate that is a comparison of a flag variable against
856      a constant.  */
857   the_pred_chain = preds[0];
858   n = VEC_length (use_pred_info_t, the_pred_chain);
859   for (i = 0; i < n; i++)
860     {
861       gimple cond;
862       tree cond_lhs, cond_rhs, flag = 0;
863
864       use_pred_info_t the_pred
865           = VEC_index (use_pred_info_t, the_pred_chain, i);
866
867       cond = the_pred->cond;
868       invert = the_pred->invert;
869       cond_lhs = gimple_cond_lhs (cond);
870       cond_rhs = gimple_cond_rhs (cond);
871       cmp_code = gimple_cond_code (cond);
872
873       if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
874           && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
875         {
876           boundary_cst = cond_rhs;
877           flag = cond_lhs;
878         }
879       else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
880                && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
881         {
882           boundary_cst = cond_lhs;
883           flag = cond_rhs;
884           swap_cond = true;
885         }
886
887       if (!flag)
888         continue;
889
890       flag_def = SSA_NAME_DEF_STMT (flag);
891
892       if (!flag_def)
893         continue;
894
895       if ((gimple_code (flag_def) == GIMPLE_PHI)
896           && (gimple_bb (flag_def) == gimple_bb (phi))
897           && find_matching_predicate_in_rest_chains (
898               the_pred, preds, num_preds))
899         break;
900
901       flag_def = 0;
902     }
903
904   if (!flag_def)
905     return false;
906
907   /* Now check all the uninit incoming edge has a constant flag value
908      that is in conflict with the use guard/predicate.  */
909   cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
910
911   if (cmp_code == ERROR_MARK)
912     return false;
913
914   for (i = 0; i < sizeof (unsigned); i++)
915     {
916       tree flag_arg;
917
918       if (!MASK_TEST_BIT (uninit_opnds, i))
919         continue;
920
921       flag_arg = gimple_phi_arg_def (flag_def, i);
922       if (!is_gimple_constant (flag_arg))
923         return false;
924
925       /* Now check if the constant is in the guarded range.  */
926       if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
927         {
928           tree opnd;
929           gimple opnd_def;
930
931           /* Now that we know that this undefined edge is not
932              pruned. If the operand is defined by another phi,
933              we can further prune the incoming edges of that
934              phi by checking the predicates of this operands.  */
935
936           opnd = gimple_phi_arg_def (phi, i);
937           opnd_def = SSA_NAME_DEF_STMT (opnd);
938           if (gimple_code (opnd_def) == GIMPLE_PHI)
939             {
940               edge opnd_edge;
941               unsigned uninit_opnds2
942                   = compute_uninit_opnds_pos (opnd_def);
943               gcc_assert (!MASK_EMPTY (uninit_opnds2));
944               opnd_edge = gimple_phi_arg_edge (phi, i);
945               if (!is_use_properly_guarded (phi,
946                                             opnd_edge->src,
947                                             opnd_def,
948                                             uninit_opnds2,
949                                             visited_phis))
950                   return false;
951             }
952           else
953             return false;
954         }
955     }
956
957   return true;
958 }
959
960 /* Returns true if TC is AND or OR */
961
962 static inline bool
963 is_and_or_or (enum tree_code tc, tree typ)
964 {
965   return (tc == TRUTH_AND_EXPR
966           || tc == TRUTH_OR_EXPR
967           || tc == BIT_IOR_EXPR
968           || (tc == BIT_AND_EXPR
969               && (typ == 0 || TREE_CODE (typ) == BOOLEAN_TYPE)));
970 }
971
972 typedef struct norm_cond
973 {
974   VEC(gimple, heap) *conds;
975   enum tree_code cond_code;
976   bool invert;
977 } *norm_cond_t;
978
979
980 /* Normalizes gimple condition COND. The normalization follows
981    UD chains to form larger condition expression trees. NORM_COND
982    holds the normalized result. COND_CODE is the logical opcode
983    (AND or OR) of the normalized tree.  */
984
985 static void
986 normalize_cond_1 (gimple cond,
987                   norm_cond_t norm_cond,
988                   enum tree_code cond_code)
989 {
990   enum gimple_code gc;
991   enum tree_code cur_cond_code;
992   tree rhs1, rhs2;
993
994   gc = gimple_code (cond);
995   if (gc != GIMPLE_ASSIGN)
996     {
997       VEC_safe_push (gimple, heap, norm_cond->conds, cond);
998       return;
999     }
1000
1001   cur_cond_code = gimple_assign_rhs_code (cond);
1002   rhs1 = gimple_assign_rhs1 (cond);
1003   rhs2 = gimple_assign_rhs2 (cond);
1004   if (cur_cond_code == NE_EXPR)
1005     {
1006       if (integer_zerop (rhs2)
1007           && (TREE_CODE (rhs1) == SSA_NAME))
1008         normalize_cond_1 (
1009             SSA_NAME_DEF_STMT (rhs1),
1010             norm_cond, cond_code);
1011       else if (integer_zerop (rhs1)
1012                && (TREE_CODE (rhs2) == SSA_NAME))
1013         normalize_cond_1 (
1014             SSA_NAME_DEF_STMT (rhs2),
1015             norm_cond, cond_code);
1016       else
1017         VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1018
1019       return;
1020     }
1021
1022   if (is_and_or_or (cur_cond_code, TREE_TYPE (rhs1))
1023       && (cond_code == cur_cond_code || cond_code == ERROR_MARK)
1024       && (TREE_CODE (rhs1) == SSA_NAME && TREE_CODE (rhs2) == SSA_NAME))
1025     {
1026       normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1),
1027                         norm_cond, cur_cond_code);
1028       normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2),
1029                         norm_cond, cur_cond_code);
1030       norm_cond->cond_code = cur_cond_code;
1031     }
1032   else
1033     VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1034 }
1035
1036 /* See normalize_cond_1 for details. INVERT is a flag to indicate
1037    if COND needs to be inverted or not.  */
1038
1039 static void
1040 normalize_cond (gimple cond, norm_cond_t norm_cond, bool invert)
1041 {
1042   enum tree_code cond_code;
1043
1044   norm_cond->cond_code = ERROR_MARK;
1045   norm_cond->invert = false;
1046   norm_cond->conds = NULL;
1047   gcc_assert (gimple_code (cond) == GIMPLE_COND);
1048   cond_code = gimple_cond_code (cond);
1049   if (invert)
1050     cond_code = invert_tree_comparison (cond_code, false);
1051
1052   if (cond_code == NE_EXPR)
1053     {
1054       if (integer_zerop (gimple_cond_rhs (cond))
1055           && (TREE_CODE (gimple_cond_lhs (cond)) == SSA_NAME))
1056         normalize_cond_1 (
1057             SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)),
1058             norm_cond, ERROR_MARK);
1059       else if (integer_zerop (gimple_cond_lhs (cond))
1060                && (TREE_CODE (gimple_cond_rhs (cond)) == SSA_NAME))
1061         normalize_cond_1 (
1062             SSA_NAME_DEF_STMT (gimple_cond_rhs (cond)),
1063             norm_cond, ERROR_MARK);
1064       else
1065         {
1066           VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1067           norm_cond->invert = invert;
1068         }
1069     }
1070   else
1071     {
1072       VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1073       norm_cond->invert = invert;
1074     }
1075
1076   gcc_assert (VEC_length (gimple, norm_cond->conds) == 1
1077               || is_and_or_or (norm_cond->cond_code, NULL));
1078 }
1079
1080 /* Returns true if the domain for condition COND1 is a subset of
1081    COND2. REVERSE is a flag. when it is true the function checks
1082    if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
1083    to indicate if COND1 and COND2 need to be inverted or not.  */
1084
1085 static bool
1086 is_gcond_subset_of (gimple cond1, bool invert1,
1087                     gimple cond2, bool invert2,
1088                     bool reverse)
1089 {
1090   enum gimple_code gc1, gc2;
1091   enum tree_code cond1_code, cond2_code;
1092   gimple tmp;
1093   tree cond1_lhs, cond1_rhs, cond2_lhs, cond2_rhs;
1094
1095   /* Take the short cut.  */
1096   if (cond1 == cond2)
1097     return true;
1098
1099   if (reverse)
1100     {
1101       tmp = cond1;
1102       cond1 = cond2;
1103       cond2 = tmp;
1104     }
1105
1106   gc1 = gimple_code (cond1);
1107   gc2 = gimple_code (cond2);
1108
1109   if ((gc1 != GIMPLE_ASSIGN && gc1 != GIMPLE_COND)
1110       || (gc2 != GIMPLE_ASSIGN && gc2 != GIMPLE_COND))
1111     return cond1 == cond2;
1112
1113   cond1_code = ((gc1 == GIMPLE_ASSIGN)
1114                 ? gimple_assign_rhs_code (cond1)
1115                 : gimple_cond_code (cond1));
1116
1117   cond2_code = ((gc2 == GIMPLE_ASSIGN)
1118                 ? gimple_assign_rhs_code (cond2)
1119                 : gimple_cond_code (cond2));
1120
1121   if (TREE_CODE_CLASS (cond1_code) != tcc_comparison
1122       || TREE_CODE_CLASS (cond2_code) != tcc_comparison)
1123     return false;
1124
1125   if (invert1)
1126     cond1_code = invert_tree_comparison (cond1_code, false);
1127   if (invert2)
1128     cond2_code = invert_tree_comparison (cond2_code, false);
1129
1130   cond1_lhs = ((gc1 == GIMPLE_ASSIGN)
1131                ? gimple_assign_rhs1 (cond1)
1132                : gimple_cond_lhs (cond1));
1133   cond1_rhs = ((gc1 == GIMPLE_ASSIGN)
1134                ? gimple_assign_rhs2 (cond1)
1135                : gimple_cond_rhs (cond1));
1136   cond2_lhs = ((gc2 == GIMPLE_ASSIGN)
1137                ? gimple_assign_rhs1 (cond2)
1138                : gimple_cond_lhs (cond2));
1139   cond2_rhs = ((gc2 == GIMPLE_ASSIGN)
1140                ? gimple_assign_rhs2 (cond2)
1141                : gimple_cond_rhs (cond2));
1142
1143   /* Assuming const operands have been swapped to the
1144      rhs at this point of the analysis.  */
1145
1146   if (cond1_lhs != cond2_lhs)
1147     return false;
1148
1149   if (!is_gimple_constant (cond1_rhs)
1150       || TREE_CODE (cond1_rhs) != INTEGER_CST)
1151     return (cond1_rhs == cond2_rhs);
1152
1153   if (!is_gimple_constant (cond2_rhs)
1154       || TREE_CODE (cond2_rhs) != INTEGER_CST)
1155     return (cond1_rhs == cond2_rhs);
1156
1157   if (cond1_code == EQ_EXPR)
1158     return is_value_included_in (cond1_rhs,
1159                                  cond2_rhs, cond2_code);
1160   if (cond1_code == NE_EXPR || cond2_code == EQ_EXPR)
1161     return ((cond2_code == cond1_code)
1162             && tree_int_cst_equal (cond1_rhs, cond2_rhs));
1163
1164   if (((cond1_code == GE_EXPR || cond1_code == GT_EXPR)
1165        && (cond2_code == LE_EXPR || cond2_code == LT_EXPR))
1166       || ((cond1_code == LE_EXPR || cond1_code == LT_EXPR)
1167           && (cond2_code == GE_EXPR || cond2_code == GT_EXPR)))
1168     return false;
1169
1170   if (cond1_code != GE_EXPR && cond1_code != GT_EXPR
1171       && cond1_code != LE_EXPR && cond1_code != LT_EXPR)
1172     return false;
1173
1174   if (cond1_code == GT_EXPR)
1175     {
1176       cond1_code = GE_EXPR;
1177       cond1_rhs = fold_binary (PLUS_EXPR, TREE_TYPE (cond1_rhs),
1178                                cond1_rhs,
1179                                fold_convert (TREE_TYPE (cond1_rhs),
1180                                              integer_one_node));
1181     }
1182   else if (cond1_code == LT_EXPR)
1183     {
1184       cond1_code = LE_EXPR;
1185       cond1_rhs = fold_binary (MINUS_EXPR, TREE_TYPE (cond1_rhs),
1186                                cond1_rhs,
1187                                fold_convert (TREE_TYPE (cond1_rhs),
1188                                              integer_one_node));
1189     }
1190
1191   if (!cond1_rhs)
1192     return false;
1193
1194   gcc_assert (cond1_code == GE_EXPR || cond1_code == LE_EXPR);
1195
1196   if (cond2_code == GE_EXPR || cond2_code == GT_EXPR ||
1197       cond2_code == LE_EXPR || cond2_code == LT_EXPR)
1198     return is_value_included_in (cond1_rhs,
1199                                  cond2_rhs, cond2_code);
1200   else if (cond2_code == NE_EXPR)
1201     return
1202         (is_value_included_in (cond1_rhs,
1203                                cond2_rhs, cond2_code)
1204          && !is_value_included_in (cond2_rhs,
1205                                    cond1_rhs, cond1_code));
1206   return false;
1207 }
1208
1209 /* Returns true if the domain of the condition expression 
1210    in COND is a subset of any of the sub-conditions
1211    of the normalized condtion NORM_COND.  INVERT is a flag
1212    to indicate of the COND needs to be inverted.
1213    REVERSE is a flag. When it is true, the check is reversed --
1214    it returns true if COND is a superset of any of the subconditions
1215    of NORM_COND.  */
1216
1217 static bool
1218 is_subset_of_any (gimple cond, bool invert,
1219                   norm_cond_t norm_cond, bool reverse)
1220 {
1221   size_t i;
1222   size_t len = VEC_length (gimple, norm_cond->conds);
1223
1224   for (i = 0; i < len; i++)
1225     {
1226       if (is_gcond_subset_of (cond, invert,
1227                               VEC_index (gimple, norm_cond->conds, i),
1228                               false, reverse))
1229         return true;
1230     }
1231   return false;
1232 }
1233
1234 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
1235    expressions (formed by following UD chains not control
1236    dependence chains). The function returns true of domain
1237    of and expression NORM_COND1 is a subset of NORM_COND2's.
1238    The implementation is conservative, and it returns false if
1239    it the inclusion relationship may not hold.  */
1240
1241 static bool
1242 is_or_set_subset_of (norm_cond_t norm_cond1,
1243                      norm_cond_t norm_cond2)
1244 {
1245   size_t i;
1246   size_t len = VEC_length (gimple, norm_cond1->conds);
1247
1248   for (i = 0; i < len; i++)
1249     {
1250       if (!is_subset_of_any (VEC_index (gimple, norm_cond1->conds, i),
1251                              false, norm_cond2, false))
1252         return false;
1253     }
1254   return true;
1255 }
1256
1257 /* NORM_COND1 and NORM_COND2 are normalized logical AND
1258    expressions (formed by following UD chains not control
1259    dependence chains). The function returns true of domain
1260    of and expression NORM_COND1 is a subset of NORM_COND2's.  */
1261
1262 static bool
1263 is_and_set_subset_of (norm_cond_t norm_cond1,
1264                       norm_cond_t norm_cond2)
1265 {
1266   size_t i;
1267   size_t len = VEC_length (gimple, norm_cond2->conds);
1268
1269   for (i = 0; i < len; i++)
1270     {
1271       if (!is_subset_of_any (VEC_index (gimple, norm_cond2->conds, i),
1272                              false, norm_cond1, true))
1273         return false;
1274     }
1275   return true;
1276 }
1277
1278 /* Returns true of the domain if NORM_COND1 is a subset 
1279    of that of NORM_COND2. Returns false if it can not be 
1280    proved to be so.  */
1281
1282 static bool
1283 is_norm_cond_subset_of (norm_cond_t norm_cond1,
1284                         norm_cond_t norm_cond2)
1285 {
1286   size_t i;
1287   enum tree_code code1, code2;
1288
1289   code1 = norm_cond1->cond_code;
1290   code2 = norm_cond2->cond_code;
1291
1292   if (code1 == TRUTH_AND_EXPR || code1 == BIT_AND_EXPR)
1293     {
1294       /* Both conditions are AND expressions.  */
1295       if (code2 == TRUTH_AND_EXPR || code2 == BIT_AND_EXPR)
1296         return is_and_set_subset_of (norm_cond1, norm_cond2);
1297       /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
1298          expression. In this case, returns true if any subexpression
1299          of NORM_COND1 is a subset of any subexpression of NORM_COND2.  */
1300       else if (code2 == TRUTH_OR_EXPR || code2 == BIT_IOR_EXPR)
1301         {
1302           size_t len1;
1303           len1 = VEC_length (gimple, norm_cond1->conds);
1304           for (i = 0; i < len1; i++)
1305             {
1306               gimple cond1 = VEC_index (gimple, norm_cond1->conds, i);
1307               if (is_subset_of_any (cond1, false, norm_cond2, false))
1308                 return true;
1309             }
1310           return false;
1311         }
1312       else
1313         {
1314           gcc_assert (code2 == ERROR_MARK);
1315           gcc_assert (VEC_length (gimple, norm_cond2->conds) == 1);
1316           return is_subset_of_any (VEC_index (gimple, norm_cond2->conds, 0),
1317                                    norm_cond2->invert, norm_cond1, true);
1318         }
1319     }
1320   /* NORM_COND1 is an OR expression  */
1321   else if (code1 == TRUTH_OR_EXPR || code1 == BIT_IOR_EXPR)
1322     {
1323       if (code2 != code1)
1324         return false;
1325
1326       return is_or_set_subset_of (norm_cond1, norm_cond2);
1327     }
1328   else
1329     {
1330       gcc_assert (code1 == ERROR_MARK);
1331       gcc_assert (VEC_length (gimple, norm_cond1->conds) == 1);
1332       /* Conservatively returns false if NORM_COND1 is non-decomposible
1333          and NORM_COND2 is an AND expression.  */
1334       if (code2 == TRUTH_AND_EXPR || code2 == BIT_AND_EXPR)
1335         return false;
1336
1337       if (code2 == TRUTH_OR_EXPR || code2 == BIT_IOR_EXPR)
1338         return is_subset_of_any (VEC_index (gimple, norm_cond1->conds, 0),
1339                                  norm_cond1->invert, norm_cond2, false);
1340
1341       gcc_assert (code2 == ERROR_MARK);
1342       gcc_assert (VEC_length (gimple, norm_cond2->conds) == 1);
1343       return is_gcond_subset_of (VEC_index (gimple, norm_cond1->conds, 0),
1344                                  norm_cond1->invert,
1345                                  VEC_index (gimple, norm_cond2->conds, 0),
1346                                  norm_cond2->invert, false);
1347     }
1348 }
1349
1350 /* Returns true of the domain of single predicate expression
1351    EXPR1 is a subset of that of EXPR2. Returns false if it
1352    can not be proved.  */
1353
1354 static bool
1355 is_pred_expr_subset_of (use_pred_info_t expr1,
1356                         use_pred_info_t expr2)
1357 {
1358   gimple cond1, cond2;
1359   enum tree_code code1, code2;
1360   struct norm_cond norm_cond1, norm_cond2;
1361   bool is_subset = false;
1362
1363   cond1 = expr1->cond;
1364   cond2 = expr2->cond;
1365   code1 = gimple_cond_code (cond1);
1366   code2 = gimple_cond_code (cond2);
1367
1368   if (expr1->invert)
1369     code1 = invert_tree_comparison (code1, false);
1370   if (expr2->invert)
1371     code2 = invert_tree_comparison (code2, false);
1372
1373   /* Fast path -- match exactly  */
1374   if ((gimple_cond_lhs (cond1) == gimple_cond_lhs (cond2))
1375       && (gimple_cond_rhs (cond1) == gimple_cond_rhs (cond2))
1376       && (code1 == code2))
1377     return true;
1378
1379   /* Normalize conditions. To keep NE_EXPR, do not invert
1380      with both need inversion.  */
1381   normalize_cond (cond1, &norm_cond1, (expr1->invert));
1382   normalize_cond (cond2, &norm_cond2, (expr2->invert));
1383
1384   is_subset = is_norm_cond_subset_of (&norm_cond1, &norm_cond2);
1385
1386   /* Free memory  */
1387   VEC_free (gimple, heap, norm_cond1.conds);
1388   VEC_free (gimple, heap, norm_cond2.conds);
1389   return is_subset ;
1390 }
1391
1392 /* Returns true if the domain of PRED1 is a subset
1393    of that of PRED2. Returns false if it can not be proved so.  */
1394
1395 static bool
1396 is_pred_chain_subset_of (VEC(use_pred_info_t, heap) *pred1,
1397                          VEC(use_pred_info_t, heap) *pred2)
1398 {
1399   size_t np1, np2, i1, i2;
1400
1401   np1 = VEC_length (use_pred_info_t, pred1);
1402   np2 = VEC_length (use_pred_info_t, pred2);
1403
1404   for (i2 = 0; i2 < np2; i2++)
1405     {
1406       bool found = false;
1407       use_pred_info_t info2
1408           = VEC_index (use_pred_info_t, pred2, i2);
1409       for (i1 = 0; i1 < np1; i1++)
1410         {
1411           use_pred_info_t info1
1412               = VEC_index (use_pred_info_t, pred1, i1);
1413           if (is_pred_expr_subset_of (info1, info2))
1414             {
1415               found = true;
1416               break;
1417             }
1418         }
1419       if (!found)
1420         return false;
1421     }
1422   return true;
1423 }
1424
1425 /* Returns true if the domain defined by
1426    one pred chain ONE_PRED is a subset of the domain
1427    of *PREDS. It returns false if ONE_PRED's domain is
1428    not a subset of any of the sub-domains of PREDS (
1429    corresponding to each individual chains in it), even
1430    though it may be still be a subset of whole domain
1431    of PREDS which is the union (ORed) of all its subdomains.
1432    In other words, the result is conservative.  */
1433
1434 static bool
1435 is_included_in (VEC(use_pred_info_t, heap) *one_pred,
1436                 VEC(use_pred_info_t, heap) **preds,
1437                 size_t n)
1438 {
1439   size_t i;
1440
1441   for (i = 0; i < n; i++)
1442     {
1443       if (is_pred_chain_subset_of (one_pred, preds[i]))
1444         return true;
1445     }
1446
1447   return false;
1448 }
1449
1450 /* compares two predicate sets PREDS1 and PREDS2 and returns
1451    true if the domain defined by PREDS1 is a superset
1452    of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1453    PREDS2 respectively. The implementation chooses not to build
1454    generic trees (and relying on the folding capability of the
1455    compiler), but instead performs brute force comparison of
1456    individual predicate chains (won't be a compile time problem
1457    as the chains are pretty short). When the function returns
1458    false, it does not necessarily mean *PREDS1 is not a superset
1459    of *PREDS2, but mean it may not be so since the analysis can
1460    not prove it. In such cases, false warnings may still be
1461    emitted.  */
1462
1463 static bool
1464 is_superset_of (VEC(use_pred_info_t, heap) **preds1,
1465                 size_t n1,
1466                 VEC(use_pred_info_t, heap) **preds2,
1467                 size_t n2)
1468 {
1469   size_t i;
1470   VEC(use_pred_info_t, heap) *one_pred_chain;
1471
1472   for (i = 0; i < n2; i++)
1473     {
1474       one_pred_chain = preds2[i];
1475       if (!is_included_in (one_pred_chain, preds1, n1))
1476         return false;
1477     }
1478
1479   return true;
1480 }
1481
1482 /* Computes the predicates that guard the use and checks
1483    if the incoming paths that have empty (or possibly
1484    empty) defintion can be pruned/filtered. The function returns
1485    true if it can be determined that the use of PHI's def in
1486    USE_STMT is guarded with a predicate set not overlapping with
1487    predicate sets of all runtime paths that do not have a definition.
1488    Returns false if it is not or it can not be determined. USE_BB is
1489    the bb of the use (for phi operand use, the bb is not the bb of
1490    the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
1491    is a bit vector. If an operand of PHI is uninitialized, the
1492    correponding bit in the vector is 1.  VISIED_PHIS is a pointer
1493    set of phis being visted.  */
1494
1495 static bool
1496 is_use_properly_guarded (gimple use_stmt,
1497                          basic_block use_bb,
1498                          gimple phi,
1499                          unsigned uninit_opnds,
1500                          struct pointer_set_t *visited_phis)
1501 {
1502   basic_block phi_bb;
1503   VEC(use_pred_info_t, heap) **preds = 0;
1504   VEC(use_pred_info_t, heap) **def_preds = 0;
1505   size_t num_preds = 0, num_def_preds = 0;
1506   bool has_valid_preds = false;
1507   bool is_properly_guarded = false;
1508
1509   if (pointer_set_insert (visited_phis, phi))
1510     return false;
1511
1512   phi_bb = gimple_bb (phi);
1513
1514   if (is_non_loop_exit_postdominating (use_bb, phi_bb))
1515     return false;
1516
1517   has_valid_preds = find_predicates (&preds, &num_preds,
1518                                      phi_bb, use_bb);
1519
1520   if (!has_valid_preds)
1521     {
1522       destroy_predicate_vecs (num_preds, preds);
1523       return false;
1524     }
1525
1526   if (dump_file)
1527     dump_predicates (use_stmt, num_preds, preds,
1528                      "Use in stmt ");
1529
1530   has_valid_preds = find_def_preds (&def_preds,
1531                                     &num_def_preds, phi);
1532
1533   if (has_valid_preds)
1534     {
1535       if (dump_file)
1536         dump_predicates (phi, num_def_preds, def_preds,
1537                          "Operand defs of phi ");
1538       is_properly_guarded =
1539           is_superset_of (def_preds, num_def_preds,
1540                           preds, num_preds);
1541     }
1542
1543   /* further prune the dead incoming phi edges. */
1544   if (!is_properly_guarded)
1545     is_properly_guarded
1546         = use_pred_not_overlap_with_undef_path_pred (
1547             num_preds, preds, phi, uninit_opnds, visited_phis);
1548
1549   destroy_predicate_vecs (num_preds, preds);
1550   destroy_predicate_vecs (num_def_preds, def_preds);
1551   return is_properly_guarded;
1552 }
1553
1554 /* Searches through all uses of a potentially
1555    uninitialized variable defined by PHI and returns a use
1556    statement if the use is not properly guarded. It returns
1557    NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
1558    holding the position(s) of uninit PHI operands. WORKLIST
1559    is the vector of candidate phis that may be updated by this
1560    function. ADDED_TO_WORKLIST is the pointer set tracking
1561    if the new phi is already in the worklist.  */
1562
1563 static gimple
1564 find_uninit_use (gimple phi, unsigned uninit_opnds,
1565                  VEC(gimple, heap) **worklist,
1566                  struct pointer_set_t *added_to_worklist)
1567 {
1568   tree phi_result;
1569   use_operand_p use_p;
1570   gimple use_stmt;
1571   imm_use_iterator iter;
1572
1573   phi_result = gimple_phi_result (phi);
1574
1575   FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
1576     {
1577       struct pointer_set_t *visited_phis;
1578       basic_block use_bb;
1579
1580       use_stmt = use_p->loc.stmt;
1581
1582       visited_phis = pointer_set_create ();
1583
1584       use_bb = gimple_bb (use_stmt);
1585       if (gimple_code (use_stmt) == GIMPLE_PHI)
1586         {
1587           unsigned i, n;
1588           n = gimple_phi_num_args (use_stmt);
1589
1590           /* Find the matching phi argument of the use.  */
1591           for (i = 0; i < n; ++i)
1592             {
1593                if (gimple_phi_arg_def_ptr (use_stmt, i) == use_p->use)
1594                  {
1595                     edge e = gimple_phi_arg_edge (use_stmt, i);
1596                     use_bb = e->src;
1597                     break;
1598                  }
1599             }
1600         }
1601
1602       if (is_use_properly_guarded (use_stmt,
1603                                    use_bb, 
1604                                    phi,
1605                                    uninit_opnds,
1606                                    visited_phis))
1607         {
1608           pointer_set_destroy (visited_phis);
1609           continue;
1610         }
1611       pointer_set_destroy (visited_phis);
1612
1613       /* Found one real use, return.  */
1614       if (gimple_code (use_stmt) != GIMPLE_PHI)
1615          return use_stmt;
1616
1617       /* Found a phi use that is not guarded,
1618          add the phi to the worklist.  */
1619       if (!pointer_set_insert (added_to_worklist,
1620                                use_stmt))
1621         {
1622           VEC_safe_push (gimple, heap, *worklist, use_stmt);
1623           pointer_set_insert (possibly_undefined_names,
1624                               phi_result);
1625         }
1626     }
1627
1628   return NULL;
1629 }
1630
1631 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1632    and gives warning if there exists a runtime path from the entry to a
1633    use of the PHI def that does not contain a definition. In other words,
1634    the warning is on the real use. The more dead paths that can be pruned
1635    by the compiler, the fewer false positives the warning is. WORKLIST
1636    is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
1637    a pointer set tracking if the new phi is added to the worklist or not.  */
1638
1639 static void
1640 warn_uninitialized_phi (gimple phi, VEC(gimple, heap) **worklist,
1641                         struct pointer_set_t *added_to_worklist)
1642 {
1643   unsigned uninit_opnds;
1644   gimple uninit_use_stmt = 0;
1645   tree uninit_op;
1646
1647   /* Don't look at memory tags.  */
1648   if (!is_gimple_reg (gimple_phi_result (phi)))
1649     return;
1650
1651   uninit_opnds = compute_uninit_opnds_pos (phi);
1652
1653   if  (MASK_EMPTY (uninit_opnds))
1654     return;
1655
1656   /* Now check if we have any use of the value without proper guard.  */
1657   uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
1658                                      worklist, added_to_worklist);
1659
1660   /* All uses are properly guarded.  */
1661   if (!uninit_use_stmt)
1662     return;
1663
1664   uninit_op = gimple_phi_arg_def (phi, MASK_FIRST_SET_BIT (uninit_opnds));
1665   warn_uninit (uninit_op,
1666                "%qD may be used uninitialized in this function",
1667                uninit_use_stmt);
1668
1669 }
1670
1671
1672 /* Entry point to the late uninitialized warning pass.  */
1673
1674 static unsigned int
1675 execute_late_warn_uninitialized (void)
1676 {
1677   basic_block bb;
1678   gimple_stmt_iterator gsi;
1679   VEC(gimple, heap) *worklist = 0;
1680   struct pointer_set_t *added_to_worklist;
1681
1682   calculate_dominance_info (CDI_DOMINATORS);
1683   calculate_dominance_info (CDI_POST_DOMINATORS);
1684   /* Re-do the plain uninitialized variable check, as optimization may have
1685      straightened control flow.  Do this first so that we don't accidentally
1686      get a "may be" warning when we'd have seen an "is" warning later.  */
1687   warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1688
1689   timevar_push (TV_TREE_UNINIT);
1690
1691   possibly_undefined_names = pointer_set_create ();
1692   added_to_worklist = pointer_set_create ();
1693
1694   /* Initialize worklist  */
1695   FOR_EACH_BB (bb)
1696     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1697       {
1698         gimple phi = gsi_stmt (gsi);
1699         size_t n, i;
1700
1701         n = gimple_phi_num_args (phi);
1702
1703         /* Don't look at memory tags.  */
1704         if (!is_gimple_reg (gimple_phi_result (phi)))
1705           continue;
1706
1707         for (i = 0; i < n; ++i)
1708           {
1709             tree op = gimple_phi_arg_def (phi, i);
1710             if (TREE_CODE (op) == SSA_NAME
1711                 && ssa_undefined_value_p (op))
1712               {
1713                 VEC_safe_push (gimple, heap, worklist, phi);
1714                 pointer_set_insert (added_to_worklist, phi);
1715                 break;
1716               }
1717           }
1718       }
1719
1720   while (VEC_length (gimple, worklist) != 0)
1721     {
1722       gimple cur_phi = 0;
1723       cur_phi = VEC_pop (gimple, worklist);
1724       warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist);
1725     }
1726   
1727   VEC_free (gimple, heap, worklist);
1728   pointer_set_destroy (added_to_worklist);
1729   pointer_set_destroy (possibly_undefined_names);
1730   possibly_undefined_names = NULL;
1731   free_dominance_info (CDI_POST_DOMINATORS);
1732   timevar_pop (TV_TREE_UNINIT);
1733   return 0;
1734 }
1735
1736 static bool
1737 gate_warn_uninitialized (void)
1738 {
1739   return warn_uninitialized != 0;
1740 }
1741
1742 struct gimple_opt_pass pass_late_warn_uninitialized =
1743 {
1744  {
1745   GIMPLE_PASS,
1746   "uninit",                             /* name */
1747   gate_warn_uninitialized,              /* gate */
1748   execute_late_warn_uninitialized,      /* execute */
1749   NULL,                                 /* sub */
1750   NULL,                                 /* next */
1751   0,                                    /* static_pass_number */
1752   TV_NONE,                              /* tv_id */
1753   PROP_ssa,                             /* properties_required */
1754   0,                                    /* properties_provided */
1755   0,                                    /* properties_destroyed */
1756   0,                                    /* todo_flags_start */
1757   0                                     /* todo_flags_finish */
1758  }
1759 };