| Message ID | 1684bcc0-a007-b052-4162-8ce54ae78c27@redhat.com |
|---|---|
| State | New |
| Headers | show |
On 29 November 2016 at 17:33, Aldy Hernandez <aldyh@redhat.com> wrote: > This fixes the gcc.dg/uninit-pred-6* failures I seem to have caused on some > non x86 platforms. Sorry for the delay. > > The problem is that my fix for PR61409 had the logic backwards. I was > proving that all the uses of a PHI are invalidated by any one undefined PHI > path, whereas what we want is to prove that EVERY uninitialized path is > invalidated by some facor in the PHI use. > > The attached patch fixes this without causing any regressions on x86-64 > Linux. I also verified that at least on [arm-none-linux-gnueabihf > --with-cpu=cortex-a5 --with-fpu=vfpv3-d16-fp16], there are no > gcc.dg/*uninit* regressions. > > There is still one regression at large involving a double free in PR78548 > which I will look at next/independently. > Thanks for working on this. I've submitted a validation with your patch, I'll let you know if I find any regressions. Christophe > OK for trunk? > Aldy
On 29 November 2016 at 17:49, Christophe Lyon <christophe.lyon@linaro.org> wrote: > On 29 November 2016 at 17:33, Aldy Hernandez <aldyh@redhat.com> wrote: >> This fixes the gcc.dg/uninit-pred-6* failures I seem to have caused on some >> non x86 platforms. Sorry for the delay. >> >> The problem is that my fix for PR61409 had the logic backwards. I was >> proving that all the uses of a PHI are invalidated by any one undefined PHI >> path, whereas what we want is to prove that EVERY uninitialized path is >> invalidated by some facor in the PHI use. >> >> The attached patch fixes this without causing any regressions on x86-64 >> Linux. I also verified that at least on [arm-none-linux-gnueabihf >> --with-cpu=cortex-a5 --with-fpu=vfpv3-d16-fp16], there are no >> gcc.dg/*uninit* regressions. >> >> There is still one regression at large involving a double free in PR78548 >> which I will look at next/independently. >> > Thanks for working on this. > I've submitted a validation with your patch, I'll let you know if I find any > regressions. > > Christophe > The results are OK: gcc.dg/uninit-pred-6_[abc].c now pass on cortex-a5/cortex-m3. Thanks Christophe >> OK for trunk? >> Aldy
On 11/29/2016 09:33 AM, Aldy Hernandez wrote: > This fixes the gcc.dg/uninit-pred-6* failures I seem to have caused on > some non x86 platforms. Sorry for the delay. > > The problem is that my fix for PR61409 had the logic backwards. I was > proving that all the uses of a PHI are invalidated by any one undefined > PHI path, whereas what we want is to prove that EVERY uninitialized path > is invalidated by some facor in the PHI use. > > The attached patch fixes this without causing any regressions on x86-64 > Linux. I also verified that at least on [arm-none-linux-gnueabihf > --with-cpu=cortex-a5 --with-fpu=vfpv3-d16-fp16], there are no > gcc.dg/*uninit* regressions. > > There is still one regression at large involving a double free in > PR78548 which I will look at next/independently. > > OK for trunk? > Aldy > > curr > > > commit 469f4c38a48bc284c268b40f5d5511f015844ea2 > Author: Aldy Hernandez <aldyh@redhat.com> > Date: Tue Nov 29 05:59:53 2016 -0500 > > PR middle-end/78566 > * tree-ssa-uninit.c (can_one_predicate_be_invalidated_p): Change > argument type to a pred_chain. > (can_chain_union_be_invalidated_p): Use pred_chain instead of a > worklist. > (flatten_out_predicate_chains): Remove. > (uninit_uses_cannot_happen): Rename from > uninit_ops_invalidate_phi_use. > Change logic so that we are checking that the PHI use will > invalidate _ALL_ possibly uninitialized operands. > (is_use_properly_guarded): Rename call to > uninit_ops_invalidate_phi_use into uninit_uses_cannot_happen. This walk through is mostly for the historical record as I suspect we'll be in here again in the future... And it helps me organize my own thoughts as I walk through the code. I can't keep it all in my head :-) Anyway, so you have a set of PHI args that are potentially undefined. Those args (of course) are associated with control paths through the CFG. You also have a set of uses of the PHI which are themselves associated with control paths through the CFG. If none of the uninitialized PHI arguments can flow to the PHI uses, then no warning needs to be emitted as the path in question can not occur at runtime (and one might argue we want to mark that path for potential isolation/optimization or for other "may-be" analysis). find_uninit_use iterates over the uses of the PHI result and calls is_use_properly_guarded for each. is_use_properly_guarded will call uninit_uses_cannot_happen to see if the given use can or can not be reached by paths including the uninitialized PHI arguments. uninit_uses_cannot_happen builds the predicate for each uninitialized PHI argument then uses can_chain_union_be_invalidated to see if the argument's predicate ensures the use can not be reached. If that is true for all the PHI args, then we return true, false otherwise. can_chain_union_be_invalidated invalidates things one predicate at a time using can_one_predicate_be_invalidated. If all can be invalidated, then it returns true, false otherwise. OK. jeff
On 12/05/2016 11:07 PM, Jeff Law wrote: > On 11/29/2016 09:33 AM, Aldy Hernandez wrote: >> This fixes the gcc.dg/uninit-pred-6* failures I seem to have caused on >> some non x86 platforms. Sorry for the delay. >> >> The problem is that my fix for PR61409 had the logic backwards. I was >> proving that all the uses of a PHI are invalidated by any one undefined >> PHI path, whereas what we want is to prove that EVERY uninitialized path >> is invalidated by some facor in the PHI use. >> >> The attached patch fixes this without causing any regressions on x86-64 >> Linux. I also verified that at least on [arm-none-linux-gnueabihf >> --with-cpu=cortex-a5 --with-fpu=vfpv3-d16-fp16], there are no >> gcc.dg/*uninit* regressions. >> >> There is still one regression at large involving a double free in >> PR78548 which I will look at next/independently. >> >> OK for trunk? >> Aldy >> >> curr >> >> >> commit 469f4c38a48bc284c268b40f5d5511f015844ea2 >> Author: Aldy Hernandez <aldyh@redhat.com> >> Date: Tue Nov 29 05:59:53 2016 -0500 >> >> PR middle-end/78566 >> * tree-ssa-uninit.c (can_one_predicate_be_invalidated_p): >> Change >> argument type to a pred_chain. >> (can_chain_union_be_invalidated_p): Use pred_chain instead >> of a >> worklist. >> (flatten_out_predicate_chains): Remove. >> (uninit_uses_cannot_happen): Rename from >> uninit_ops_invalidate_phi_use. >> Change logic so that we are checking that the PHI use will >> invalidate _ALL_ possibly uninitialized operands. >> (is_use_properly_guarded): Rename call to >> uninit_ops_invalidate_phi_use into uninit_uses_cannot_happen. > This walk through is mostly for the historical record as I suspect we'll > be in here again in the future... And it helps me organize my own > thoughts as I walk through the code. I can't keep it all in my head :-) Woah, I should've hired you to write the comments, cause I had a horrible time documenting the code (as you can tell). > > > Anyway, so you have a set of PHI args that are potentially undefined. > Those args (of course) are associated with control paths through the CFG. > > You also have a set of uses of the PHI which are themselves associated > with control paths through the CFG. > > If none of the uninitialized PHI arguments can flow to the PHI uses, > then no warning needs to be emitted as the path in question can not > occur at runtime (and one might argue we want to mark that path for > potential isolation/optimization or for other "may-be" analysis). > > find_uninit_use iterates over the uses of the PHI result and calls > is_use_properly_guarded for each. > > is_use_properly_guarded will call uninit_uses_cannot_happen to see if > the given use can or can not be reached by paths including the > uninitialized PHI arguments. > > uninit_uses_cannot_happen builds the predicate for each uninitialized > PHI argument then uses can_chain_union_be_invalidated to see if the > argument's predicate ensures the use can not be reached. If that is > true for all the PHI args, then we return true, false otherwise. > > can_chain_union_be_invalidated invalidates things one predicate at a > time using can_one_predicate_be_invalidated. If all can be invalidated, > then it returns true, false otherwise. Yes to all the above. > > > > OK. I will close this PR and 78548 whose approved patch depends on this one. Thank you.
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c index 4557403..a648995 100644 --- a/gcc/tree-ssa-uninit.c +++ b/gcc/tree-ssa-uninit.c @@ -2155,115 +2155,66 @@ normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use) static bool can_one_predicate_be_invalidated_p (pred_info predicate, - vec<pred_info *> worklist) + pred_chain use_guard) { - for (size_t i = 0; i < worklist.length (); ++i) + for (size_t i = 0; i < use_guard.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)) + if (pred_neg_p (predicate, use_guard[i])) return true; } return false; } -/* Return TRUE if all USE_PREDS can be invalidated by some predicate - in WORKLIST. */ +/* Return TRUE if all predicates in UNINIT_PRED are invalidated by + USE_GUARD being true. */ static bool -can_chain_union_be_invalidated_p (pred_chain_union use_preds, - vec<pred_info *> worklist) +can_chain_union_be_invalidated_p (pred_chain_union uninit_pred, + pred_chain use_guard) { - /* 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) + if (uninit_pred.is_empty ()) + return false; + for (size_t i = 0; i < uninit_pred.length (); ++i) { - pred_chain c = use_preds[i]; - bool entire_pred_chain_invalidated = false; + pred_chain c = uninit_pred[i]; for (size_t j = 0; j < c.length (); ++j) - if (can_one_predicate_be_invalidated_p (c[j], worklist)) - { - entire_pred_chain_invalidated = true; - break; - } - if (!entire_pred_chain_invalidated) - return false; + if (!can_one_predicate_be_invalidated_p (c[j], use_guard)) + 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. +/* Return TRUE if none of the uninitialized operands in UNINT_OPNDS + can actually happen if we arrived at a use for PHI. - N is the number of pred_chain_union's in PREDS. + PHI_USE_GUARDS are the guard conditions for the use of the PHI. */ - 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) +static bool +uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds, + pred_chain_union phi_use_guards) { - 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] - # + unsigned phi_args = gimple_phi_num_args (phi); + if (phi_args > max_phi_args) + return false; - ...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. */ + /* PHI_USE_GUARDS are OR'ed together. If we have more than one + possible guard, there's no way of knowing which guard was true. + Since we need to be absolutely sure that the uninitialized + operands will be invalidated, bail. */ + if (phi_use_guards.length () != 1) + return false; -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. */ + operands and build guard predicates describing them. */ unsigned i; pred_chain_union uninit_preds[max_phi_args]; - memset (uninit_preds, 0, sizeof (pred_chain_union) * max_phi_args); - for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (phi)); i++) + memset (uninit_preds, 0, sizeof (pred_chain_union) * phi_args); + for (i = 0; i < phi_args; ++i) { if (!MASK_TEST_BIT (uninit_opnds, i)) continue; @@ -2274,32 +2225,27 @@ uninit_ops_invalidate_phi_use (gphi *phi, unsigned uninit_opnds, 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); - } + /* Build the control dependency chain for uninit operand `i'... */ + if (!compute_control_dep_chain (find_dom (e->src), + e->src, dep_chains, &num_chains, + &cur_chain, &num_calls)) + return false; + /* ...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); + + /* Can the guard for this uninitialized operand be invalidated + by the PHI use? */ + if (!can_chain_union_be_invalidated_p (uninit_preds[i], + phi_use_guards[0])) + return 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; + return true; } /* Computes the predicates that guard the use and checks @@ -2361,8 +2307,8 @@ is_use_properly_guarded (gimple *use_stmt, 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); + is_properly_guarded |= uninit_uses_cannot_happen (phi, uninit_opnds, + preds); if (is_properly_guarded) {
This fixes the gcc.dg/uninit-pred-6* failures I seem to have caused on some non x86 platforms. Sorry for the delay. The problem is that my fix for PR61409 had the logic backwards. I was proving that all the uses of a PHI are invalidated by any one undefined PHI path, whereas what we want is to prove that EVERY uninitialized path is invalidated by some facor in the PHI use. The attached patch fixes this without causing any regressions on x86-64 Linux. I also verified that at least on [arm-none-linux-gnueabihf --with-cpu=cortex-a5 --with-fpu=vfpv3-d16-fp16], there are no gcc.dg/*uninit* regressions. There is still one regression at large involving a double free in PR78548 which I will look at next/independently. OK for trunk? Aldy commit 469f4c38a48bc284c268b40f5d5511f015844ea2 Author: Aldy Hernandez <aldyh@redhat.com> Date: Tue Nov 29 05:59:53 2016 -0500 PR middle-end/78566 * tree-ssa-uninit.c (can_one_predicate_be_invalidated_p): Change argument type to a pred_chain. (can_chain_union_be_invalidated_p): Use pred_chain instead of a worklist. (flatten_out_predicate_chains): Remove. (uninit_uses_cannot_happen): Rename from uninit_ops_invalidate_phi_use. Change logic so that we are checking that the PHI use will invalidate _ALL_ possibly uninitialized operands. (is_use_properly_guarded): Rename call to uninit_ops_invalidate_phi_use into uninit_uses_cannot_happen.