This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix issue in uninit analysis (PR middle-end/61112)
- From: Xinliang David Li <davidxl at google dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: Patrick Palka <patrick at parcs dot ath dot cx>, GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 13 May 2014 16:12:58 -0700
- Subject: Re: [PATCH] Fix issue in uninit analysis (PR middle-end/61112)
- Authentication-results: sourceware.org; auth=none
- References: <1399866153-24670-1-git-send-email-patrick at parcs dot ath dot cx> <CAFiYyc3G_7=PLPVt1Y4t+ktL5sCjRQU8YE5bq50NCFd2a4Xp9A at mail dot gmail dot com> <CAAkRFZKVxJFQmLX+dQ=uT3dZ4En9HMtb0_EcdjPncuukjfunDA at mail dot gmail dot com>
>
> I think the right fix to the problem is to realize that BBs with the
> following conditions y_8 !=0, p.0_10 !=0, and x_5 !=0 are actually
> control equivalent. This fact allows simplifying the USE predicates
> from (y_8 !=0 OR p.0_10 !=0 OR x_5 !=0) into just p.0_10 !=0 which is
> the same as the condition for the definition.
Ignore above which is wrong.
For the fix, I wonder if we need to compute the cd_root for def PHI
from the use predicates (after simplication/normalization).
David
>
>
> On Tue, May 13, 2014 at 2:09 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, May 12, 2014 at 5:42 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>>> Hi,
>>>
>>> This patch fixes a bogus warning generated by -Wmaybe-uninitialized.
>>> The problem is that we sometimes fail to acknowledge a defining edge
>>> belonging to a control-dependence chain because we assume that each
>>> defining edge shares the same control-dependence root. But this may not
>>> be true if a defining edge flows into a PHI node that is different from
>>> the root PHI node. This faulty assumption may result in an incomplete
>>> control-dependency chain being computed, ultimately causing a
>>> false-positive warning like in the test case.
>>>
>>> To fix this, this patch computes the control-dependency root on a
>>> per-defining-edge basis, using the function nearest_common_dominator to
>>> find a common dominator (i.e. a BB before which control flow is
>>> irrelevant) between the control-dependency root of the root PHI node and
>>> that of the edge's dest PHI node.
>>>
>>> However, that change alone is not enough. We must also tweak the
>>> function collect_phi_def_edges to allow recursing on PHI nodes that are
>>> not dominated by the root PHI node's control dependency root as we can
>>> still figure out a control dependency chain in such cases as long the
>>> PHI node postdominates the PHI argument, i.e. as long as the control
>>> flow from the PHI argument edge down to the root PHI node is irrelevant.
>>>
>>> Both these changes are required to make the below test case compile
>>> without emitting a bogus warning.
>>>
>>> I bootstrapped and regtested this change on x86_64-unknown-linux-gnu.
>>> Is it OK for trunk?
>>
>> CCing the author of the code.
>>
>> Given the lengthy comment above I miss comments in the code
>> that reflect the complexity of this issue and explains the implementation.
>>
>> Other than that I defer to David, but any improvement to this pass
>> is welcome! Can you assess the effect on compile-time this patch has?
>> (from an algorithmic standpoint?)
>>
>> Thanks,
>> Richard.
>>
>>> 2014-05-10 Patrick Palka <patrick@parcs.ath.cx>
>>>
>>> * tree-ssa-uninit.c (collect_phi_def_edges): Remove cd_root
>>> parameter. Refactor to consolidate duplicate code. Tweak dump
>>> message.
>>> (find_def_preds): Add dump messages. Adjust call to
>>> collect_phi_def_edges. Adjust the control dependency root on
>>> a per-edge basis.
>>> ---
>>> gcc/testsuite/gcc.dg/uninit-pred-11.c | 20 ++++++++++
>>> gcc/tree-ssa-uninit.c | 75 +++++++++++++++++++----------------
>>> 2 files changed, 60 insertions(+), 35 deletions(-)
>>> create mode 100644 gcc/testsuite/gcc.dg/uninit-pred-11.c
>>>
>>> diff --git a/gcc/testsuite/gcc.dg/uninit-pred-11.c b/gcc/testsuite/gcc.dg/uninit-pred-11.c
>>> new file mode 100644
>>> index 0000000..493be68
>>> --- /dev/null
>>> +++ b/gcc/testsuite/gcc.dg/uninit-pred-11.c
>>> @@ -0,0 +1,20 @@
>>> +// PR middle-end/61112
>>> +// { dg-options "-Wuninitialized -O2" }
>>> +
>>> +int p;
>>> +
>>> +void
>>> +foo (int x, int y, int z)
>>> +{
>>> + int w;
>>> + if (x)
>>> + w = z;
>>> + if (y)
>>> + w = 10;
>>> + if (p)
>>> + w = 20;
>>> +
>>> + if (x || y || p)
>>> + p = w; // { dg-bogus "uninitialized" }
>>> +}
>>> +
>>> diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
>>> index 8b298fa..472b8e5 100644
>>> --- a/gcc/tree-ssa-uninit.c
>>> +++ b/gcc/tree-ssa-uninit.c
>>> @@ -641,13 +641,11 @@ find_predicates (pred_chain_union *preds,
>>>
>>> /* Computes the set of incoming edges of PHI that have non empty
>>> definitions of a phi chain. The collection will be done
>>> - recursively on operands that are defined by phis. CD_ROOT
>>> - is the control dependence root. *EDGES holds the result, and
>>> - VISITED_PHIS is a pointer set for detecting cycles. */
>>> + recursively on operands that are defined by phis. *EDGES holds
>>> + the result, and VISITED_PHIS is a pointer set for detecting cycles. */
>>>
>>> static void
>>> -collect_phi_def_edges (gimple phi, basic_block cd_root,
>>> - vec<edge> *edges,
>>> +collect_phi_def_edges (gimple phi, vec<edge> *edges,
>>> pointer_set_t *visited_phis)
>>> {
>>> size_t i, n;
>>> @@ -663,34 +661,23 @@ collect_phi_def_edges (gimple phi, basic_block cd_root,
>>> opnd_edge = gimple_phi_arg_edge (phi, i);
>>> opnd = gimple_phi_arg_def (phi, i);
>>>
>>> - if (TREE_CODE (opnd) != SSA_NAME)
>>> - {
>>> - if (dump_file && (dump_flags & TDF_DETAILS))
>>> - {
>>> - fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
>>> - print_gimple_stmt (dump_file, phi, 0, 0);
>>> - }
>>> - edges->safe_push (opnd_edge);
>>> - }
>>> - else
>>> - {
>>> - gimple def = SSA_NAME_DEF_STMT (opnd);
>>> -
>>> - if (gimple_code (def) == GIMPLE_PHI
>>> - && dominated_by_p (CDI_DOMINATORS,
>>> - gimple_bb (def), cd_root))
>>> - collect_phi_def_edges (def, cd_root, edges,
>>> - visited_phis);
>>> - else if (!uninit_undefined_value_p (opnd))
>>> - {
>>> - if (dump_file && (dump_flags & TDF_DETAILS))
>>> - {
>>> - fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
>>> - print_gimple_stmt (dump_file, phi, 0, 0);
>>> - }
>>> - edges->safe_push (opnd_edge);
>>> - }
>>> - }
>>> + if (TREE_CODE (opnd) == SSA_NAME
>>> + && gimple_code (SSA_NAME_DEF_STMT (opnd)) == GIMPLE_PHI
>>> + && dominated_by_p (CDI_POST_DOMINATORS,
>>> + gimple_bb (SSA_NAME_DEF_STMT (opnd)),
>>> + gimple_bb (phi)))
>>> + collect_phi_def_edges (SSA_NAME_DEF_STMT (opnd), edges, visited_phis);
>>> + else if (TREE_CODE (opnd) != SSA_NAME
>>> + || !uninit_undefined_value_p (opnd))
>>> + {
>>> + if (dump_file && (dump_flags & TDF_DETAILS))
>>> + {
>>> + fprintf (dump_file, "[CHECK] Found def edge %u in arg %d of ",
>>> + edges->length (), (int)i);
>>> + print_gimple_stmt (dump_file, phi, 0, 0);
>>> + }
>>> + edges->safe_push (opnd_edge);
>>> + }
>>> }
>>> }
>>>
>>> @@ -716,8 +703,12 @@ find_def_preds (pred_chain_union *preds, gimple phi)
>>> if (!cd_root)
>>> return false;
>>>
>>> + if (dump_file && (dump_flags & TDF_DETAILS))
>>> + fprintf (dump_file, "[CHECK] control dependence root is bb %d\n",
>>> + cd_root->index);
>>> +
>>> visited_phis = pointer_set_create ();
>>> - collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis);
>>> + collect_phi_def_edges (phi, &def_edges, visited_phis);
>>> pointer_set_destroy (visited_phis);
>>>
>>> n = def_edges.length ();
>>> @@ -728,11 +719,25 @@ find_def_preds (pred_chain_union *preds, gimple phi)
>>> {
>>> size_t prev_nc, j;
>>> int num_calls = 0;
>>> + basic_block adj_cd_root;
>>> edge opnd_edge;
>>>
>>> opnd_edge = def_edges[i];
>>> prev_nc = num_chains;
>>> - compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
>>> +
>>> + if (opnd_edge->dest == phi_bb)
>>> + adj_cd_root = cd_root;
>>> + else
>>> + adj_cd_root = nearest_common_dominator (CDI_DOMINATORS,
>>> + cd_root,
>>> + find_dom (opnd_edge->dest));
>>> +
>>> + if (dump_file && (dump_flags & TDF_DETAILS))
>>> + fprintf (dump_file,
>>> + "[CHECK] control dependence root of def edge %d is bb %d\n",
>>> + (int)i, adj_cd_root->index);
>>> +
>>> + compute_control_dep_chain (adj_cd_root, opnd_edge->src, dep_chains,
>>> &num_chains, &cur_chain, &num_calls);
>>>
>>> /* Now update the newly added chains with
>>> --
>>> 2.0.0.rc0
>>>