OSDN Git Service

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