Message ID | 8c90256b-a9a1-b849-08ce-9435fdb8c770@redhat.com |
---|---|

State | New |

Headers | show |

On 11/02/2016 11:16 AM, Aldy Hernandez wrote: > Hi Jeff. > > As discussed in the PR, here is a patch exploring your idea of ignoring > unguarded uses if we can prove that the guards for such uses are > invalidated by the uninitialized operand paths being executed. > > This is an updated patch from my suggestion in the PR. It bootstraps > with no regression on x86-64 Linux, and fixes the PR in question. > > As the "NOTE:" in the code states, we could be much smarter when > invalidating predicates, but for now let's do straight negation which > works for the simple case. We could expand on this in the future. > > OK for trunk? > > > curr > > > commit 8375d7e28c1a798dd0cc0f487d7fa1068d9eb124 > Author: Aldy Hernandez <aldyh@redhat.com> > Date: Thu Aug 25 10:44:29 2016 -0400 > > PR middle-end/61409 > * tree-ssa-uninit.c (use_pred_not_overlap_with_undef_path_pred): > Remove reference to missing NUM_PREDS in function comment. > (can_one_predicate_be_invalidated_p): New. > (can_chain_union_be_invalidated_p): New. > (flatten_out_predicate_chains): New. > (uninit_ops_invalidate_phi_use): New. > (is_use_properly_guarded): Call uninit_ops_invalidate_phi_use. [ snip ] > > +static bool > +can_one_predicate_be_invalidated_p (pred_info predicate, > + vec<pred_info *> worklist) > +{ > + for (size_t i = 0; i < worklist.length (); ++i) > + { > + pred_info *p = worklist[i]; > + > + /* NOTE: This is a very simple check, and only understands an > + exact opposite. So, [i == 0] is currently only invalidated > + by [.NOT. i == 0] or [i != 0]. Ideally we should also > + invalidate with say [i > 5] or [i == 8]. There is certainly > + room for improvement here. */ > + if (pred_neg_p (predicate, *p)) It's good enough for now. I saw some other routines that might allow us to handle more cases. I'm OK with faulting those in if/when we see such cases in real code. > + > +/* Return TRUE if executing the path to some uninitialized operands in > + a PHI will invalidate the use of the PHI result later on. > + > + UNINIT_OPNDS is a bit vector specifying which PHI arguments have > + arguments which are considered uninitialized. > + > + USE_PREDS is the pred_chain_union specifying the guard conditions > + for the use of the PHI result. > + > + What we want to do is disprove each of the guards in the factors of > + the USE_PREDS. So if we have: > + > + # USE_PREDS guards of: > + # 1. i > 5 && i < 100 > + # 2. j > 10 && j < 88 Are USE_PREDS joined by an AND or IOR? I guess based on their type it must be IOR. Thus to get to a use #1 or #2 must be true. So to prove we can't reach a use, we have to prove that #1 and #2 are both not true. Right? > + > +static bool > +uninit_ops_invalidate_phi_use (gphi *phi, unsigned uninit_opnds, > + pred_chain_union use_preds) > +{ > + /* Look for the control dependencies of all the uninitialized > + operands and build predicates describing them. */ > + unsigned i; > + pred_chain_union uninit_preds[32]; > + memset (uninit_preds, 0, sizeof (pred_chain_union) * 32); > + for (i = 0; i < MIN (32, gimple_phi_num_args (phi)); i++) Can you replace the magic "32" with a file scoped const or #define? I believe there's 2 existing uses of a magic "32" elsewhere in tree-ssa-uninit.c as well. > + > + /* Build the control dependency chain for `i'... */ > + if (compute_control_dep_chain (find_dom (e->src), > + e->src, > + dep_chains, > + &num_chains, > + &cur_chain, > + &num_calls)) Does this miss the control dependency carried by E itself. ie, if e->src ends in a conditional, shouldn't that conditional be reflected in the control dependency chain as well? I guess we'd have to have the notion of computing the control dependency for an edge rather than a block. It doesn't look like compute_control_dep_chain is ready for that. I'm willing to put that into a "future work" bucket. So I think just confirming my question about how USE_PREDS are joined at the call to uninit_opts_invalidate_phi_use and fixing the magic 32 to be a file scoped const or a #define and this is good to go on the trunk. jeff

diff --git a/gcc/testsuite/gcc.dg/uninit-pr61409.c b/gcc/testsuite/gcc.dg/uninit-pr61409.c new file mode 100644 index 0000000..c27a67b --- /dev/null +++ b/gcc/testsuite/gcc.dg/uninit-pr61409.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -Wuninitialized" } */ + +int *rw; +int line_height; +int pixel_width; +int text_cols; +int width1, width2, width3; + +void *pointer; + +void f (int i, int j) +{ + void *ptr; + if (i) + { + if (j) + return; + ptr = pointer; + } + pixel_width = 1234 + width1 + 2 * width2 + 2 * width3; + *rw = text_cols + line_height; + if (i) + rw=ptr; /* { dg-bogus "uninitialized" "bogus warning" } */ +} diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c index 1344854..37c99a7 100644 --- a/gcc/tree-ssa-uninit.c +++ b/gcc/tree-ssa-uninit.c @@ -1184,11 +1184,10 @@ prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def, transformation which eliminates the merge point thus makes path sensitive analysis unnecessary.) - NUM_PREDS is the number is the number predicate chains, PREDS is - the array of chains, PHI is the phi node whose incoming (undefined) - paths need to be pruned, and UNINIT_OPNDS is the bitmap holding - uninit operand positions. VISITED_PHIS is the pointer set of phi - stmts being checked. */ + PHI is the phi node whose incoming (undefined) paths need to be + pruned, and UNINIT_OPNDS is the bitmap holding uninit operand + positions. VISITED_PHIS is the pointer set of phi stmts being + checked. */ static bool use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds, @@ -2140,6 +2139,158 @@ normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use) return norm_preds; } +/* Return TRUE if PREDICATE can be invalidated by any individual + predicate in WORKLIST. */ + +static bool +can_one_predicate_be_invalidated_p (pred_info predicate, + vec<pred_info *> worklist) +{ + for (size_t i = 0; i < worklist.length (); ++i) + { + pred_info *p = worklist[i]; + + /* NOTE: This is a very simple check, and only understands an + exact opposite. So, [i == 0] is currently only invalidated + by [.NOT. i == 0] or [i != 0]. Ideally we should also + invalidate with say [i > 5] or [i == 8]. There is certainly + room for improvement here. */ + if (pred_neg_p (predicate, *p)) + return true; + } + return false; +} + +/* Return TRUE if all USE_PREDS can be invalidated by some predicate + in WORKLIST. */ + +static bool +can_chain_union_be_invalidated_p (pred_chain_union use_preds, + vec<pred_info *> worklist) +{ + /* Remember: + PRED_CHAIN_UNION = PRED_CHAIN1 || PRED_CHAIN2 || PRED_CHAIN3 + PRED_CHAIN = PRED_INFO1 && PRED_INFO2 && PRED_INFO3, etc. + + We need to invalidate the entire PRED_CHAIN_UNION, which means, + invalidating every PRED_CHAIN in this union. But to invalidate + an individual PRED_CHAIN, all we need to invalidate is _any_ one + PRED_INFO, by boolean algebra !PRED_INFO1 || !PRED_INFO2... */ + for (size_t i = 0; i < use_preds.length (); ++i) + { + pred_chain c = use_preds[i]; + bool entire_pred_chain_invalidated = false; + for (size_t j = 0; j < c.length (); ++j) + if (can_one_predicate_be_invalidated_p (c[i], worklist)) + { + entire_pred_chain_invalidated = true; + break; + } + if (!entire_pred_chain_invalidated) + return false; + } + return true; +} + +/* Flatten out all the factors in all the pred_chain_union's in PREDS + into a WORKLIST of individual PRED_INFO's. + + N is the number of pred_chain_union's in PREDS. + + Since we are interested in the inverse of the PRED_CHAIN's, by + boolean algebra, an inverse turns those PRED_CHAINS into unions, + which means we can flatten all the factors out for easy access. */ + +static void +flatten_out_predicate_chains (pred_chain_union preds[], size_t n, + vec<pred_info *> *worklist) +{ + for (size_t i = 0; i < n; ++i) + { + pred_chain_union u = preds[i]; + for (size_t j = 0; j < u.length (); ++j) + { + pred_chain c = u[j]; + for (size_t k = 0; k < c.length (); ++k) + worklist->safe_push (&c[k]); + } + } +} + +/* Return TRUE if executing the path to some uninitialized operands in + a PHI will invalidate the use of the PHI result later on. + + UNINIT_OPNDS is a bit vector specifying which PHI arguments have + arguments which are considered uninitialized. + + USE_PREDS is the pred_chain_union specifying the guard conditions + for the use of the PHI result. + + What we want to do is disprove each of the guards in the factors of + the USE_PREDS. So if we have: + + # USE_PREDS guards of: + # 1. i > 5 && i < 100 + # 2. j > 10 && j < 88 + + Then proving that the control dependenies for the UNINIT_OPNDS are: + + # [i <= 5] + # .OR. [i >= 100] + # + + ...we can prove that the 1st guard above in USE_PREDS is invalid. + Similarly for the 2nd guard. We return TRUE if we can disprove + both of the guards in USE_PREDS above. */ + +static bool +uninit_ops_invalidate_phi_use (gphi *phi, unsigned uninit_opnds, + pred_chain_union use_preds) +{ + /* Look for the control dependencies of all the uninitialized + operands and build predicates describing them. */ + unsigned i; + pred_chain_union uninit_preds[32]; + memset (uninit_preds, 0, sizeof (pred_chain_union) * 32); + for (i = 0; i < MIN (32, gimple_phi_num_args (phi)); i++) + { + if (!MASK_TEST_BIT (uninit_opnds, i)) + continue; + + edge e = gimple_phi_arg_edge (phi, i); + vec<edge> dep_chains[MAX_NUM_CHAINS]; + auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain; + size_t num_chains = 0; + int num_calls = 0; + + /* Build the control dependency chain for `i'... */ + if (compute_control_dep_chain (find_dom (e->src), + e->src, + dep_chains, + &num_chains, + &cur_chain, + &num_calls)) + { + /* ...and convert it into a set of predicates. */ + convert_control_dep_chain_into_preds (dep_chains, num_chains, + &uninit_preds[i]); + for (size_t j = 0; j < num_chains; ++j) + dep_chains[j].release (); + simplify_preds (&uninit_preds[i], NULL, false); + uninit_preds[i] + = normalize_preds (uninit_preds[i], NULL, false); + } + } + + /* Munge all the predicates into one worklist, and see if we can + invalidate all the chains in USE_PREDs with the predicates in + WORKLIST. */ + auto_vec<pred_info *> worklist; + flatten_out_predicate_chains (uninit_preds, i, &worklist); + bool ret = can_chain_union_be_invalidated_p (use_preds, worklist); + return ret; +} + /* Computes the predicates that guard the use and checks if the incoming paths that have empty (or possibly empty) definition can be pruned/filtered. The function returns @@ -2195,6 +2346,13 @@ is_use_properly_guarded (gimple *use_stmt, = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds, visited_phis); + /* We might be able to prove that if the control dependencies + for UNINIT_OPNDS are true, that the control dependencies for + USE_STMT can never be true. */ + if (!is_properly_guarded) + is_properly_guarded |= uninit_ops_invalidate_phi_use (phi, uninit_opnds, + preds); + if (is_properly_guarded) { destroy_predicate_vecs (&preds);