OSDN Git Service

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