On Mon, May 12, 2014 at 5:42 AM, Patrick Palka <patr...@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 <patr...@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
>
