| Message ID | 3a84e34a-f4ac-f4e5-e518-e25264560552@redhat.com |
|---|---|
| State | New |
| Headers | show |
On 11/20/2016 09:36 AM, Aldy Hernandez wrote: > On 11/16/2016 03:57 PM, Jeff Law wrote: >> 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. > > Ok. > >> >> >>> + >>> +/* 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? > > IOR, so yes. > >> >> >>> + >>> +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. > > Done. > >> >>> + >>> + /* 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. > > Hmmm, probably not. So yeah, let's put that in the 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. > > I've retested with no regressions on x86-64 Linux. > > OK for trunk? Yes. Thanks for taking my vague idea and making it real :-) I've got another if you're interested... jeff
Hi, On 20 November 2016 at 17:36, Aldy Hernandez <aldyh@redhat.com> wrote: > On 11/16/2016 03:57 PM, Jeff Law wrote: >> >> 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. > > > Ok. > >> >> >>> + >>> +/* 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? > > > IOR, so yes. > >> >> >>> + >>> +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. > > > Done. > >> >>> + >>> + /* 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. > > > Hmmm, probably not. So yeah, let's put that in the 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. > > > I've retested with no regressions on x86-64 Linux. > > OK for trunk? > > Since this commit (r242639), I've noticed regressions on arm targets: - PASS now FAIL [PASS => FAIL]: gcc.dg/uninit-pred-6_a.c warning (test for warnings, line 36) gcc.dg/uninit-pred-6_b.c warning (test for warnings, line 42) gcc.dg/uninit-pred-7_c.c (test for excess errors) gcc.dg/uninit-pred-7_c.c warning (test for warnings, line 29) - FAIL appears [ => FAIL]: gcc.dg/uninit-pred-7_c.c (internal compiler error) This ICE says: /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/testsuite/gcc.dg/uninit-pred-7_c.c: In function 'foo': /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/testsuite/gcc.dg/uninit-pred-7_c.c:9:5: internal compiler error: in operator[], at vec.h:732 0xd64099 vec<pred_info, va_heap, vl_embed>::operator[](unsigned int) /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.h:732 0xd64099 vec<pred_info, va_heap, vl_ptr>::operator[](unsigned int) /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.h:1216 0xd64099 can_chain_union_be_invalidated_p /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-uninit.c:2195 0xd64099 uninit_ops_invalidate_phi_use /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-uninit.c:2301 0xd649d0 is_use_properly_guarded /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-uninit.c:2365 0xd65b00 find_uninit_use /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-uninit.c:2434 0xd65b00 warn_uninitialized_phi /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-uninit.c:2504 0xd65b00 execute /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-uninit.c:2612 In this case, GCC was configured with: target arm-none-linux-gnueabihf --with-cpu=cortex-a5 --with-fpu=vfpv3-d16-fp16 The other CPUs I check work fine (a9/a15/a57). Christophe
On Nov 21 2016, Christophe Lyon <christophe.lyon@linaro.org> wrote: > Since this commit (r242639), I've noticed regressions on arm targets: > > - PASS now FAIL [PASS => FAIL]: > > gcc.dg/uninit-pred-6_a.c warning (test for warnings, line 36) > gcc.dg/uninit-pred-6_b.c warning (test for warnings, line 42) > gcc.dg/uninit-pred-7_c.c (test for excess errors) > gcc.dg/uninit-pred-7_c.c warning (test for warnings, line 29) > > - FAIL appears [ => FAIL]: > > gcc.dg/uninit-pred-7_c.c (internal compiler error) Same failures on m68k. Andreas.
> Since this commit (r242639), I've noticed regressions on arm targets: > > - PASS now FAIL [PASS => FAIL]: > > gcc.dg/uninit-pred-6_a.c warning (test for warnings, line 36) > gcc.dg/uninit-pred-6_b.c warning (test for warnings, line 42) > gcc.dg/uninit-pred-7_c.c (test for excess errors) > gcc.dg/uninit-pred-7_c.c warning (test for warnings, line 29) > > - FAIL appears [ => FAIL]: > > gcc.dg/uninit-pred-7_c.c (internal compiler error) > > This ICE says: > /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/testsuite/gcc.dg/uninit-pred-7_c.c: > In function 'foo': > /aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/testsuite/gcc.dg/uninit-pred-7_c.c:9:5: > internal compiler error: in operator[], at vec.h:732 I'll look into this.
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 dfee0ea..68dcf15 100644 --- a/gcc/tree-ssa-uninit.c +++ b/gcc/tree-ssa-uninit.c @@ -44,6 +44,9 @@ along with GCC; see the file COPYING3. If not see default definitions or by checking if the predicate set that guards the defining paths is a superset of the use predicate. */ +/* Max PHI args we can handle in pass. */ +const unsigned max_phi_args = 32; + /* Pointer set of potentially undefined ssa names, i.e., ssa names that are defined by phi with operands that are not defined or potentially undefined. */ @@ -314,7 +317,7 @@ compute_uninit_opnds_pos (gphi *phi) n = gimple_phi_num_args (phi); /* Bail out for phi with too many args. */ - if (n > 32) + if (n > max_phi_args) return 0; for (i = 0; i < n; ++i) @@ -1031,7 +1034,7 @@ prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def, { unsigned i; - for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++) + for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++) { tree flag_arg; @@ -1192,11 +1195,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, @@ -2148,6 +2150,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[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++) + { + 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 @@ -2203,6 +2357,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);