* [PATCH] Fix issue in uninit analysis (PR middle-end/61112)
@ 2014-05-12 3:42 Patrick Palka
2014-05-13 9:09 ` Richard Biener
0 siblings, 1 reply; 4+ messages in thread
From: Patrick Palka @ 2014-05-12 3:42 UTC (permalink / raw)
To: gcc-patches; +Cc: Patrick Palka
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?
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Fix issue in uninit analysis (PR middle-end/61112)
2014-05-12 3:42 [PATCH] Fix issue in uninit analysis (PR middle-end/61112) Patrick Palka
@ 2014-05-13 9:09 ` Richard Biener
2014-05-13 22:20 ` Xinliang David Li
0 siblings, 1 reply; 4+ messages in thread
From: Richard Biener @ 2014-05-13 9:09 UTC (permalink / raw)
To: Patrick Palka; +Cc: GCC Patches, David Li
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
>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Fix issue in uninit analysis (PR middle-end/61112)
2014-05-13 9:09 ` Richard Biener
@ 2014-05-13 22:20 ` Xinliang David Li
2014-05-13 23:13 ` Xinliang David Li
0 siblings, 1 reply; 4+ messages in thread
From: Xinliang David Li @ 2014-05-13 22:20 UTC (permalink / raw)
To: Richard Biener; +Cc: Patrick Palka, GCC Patches
I have concerns with the proposed this patch:
1) not sharing cd_root may lead to difficulties in later predication
simplication
2) the change to check post-dom may also lead to incomplete predicate chain.
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.
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
>>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Fix issue in uninit analysis (PR middle-end/61112)
2014-05-13 22:20 ` Xinliang David Li
@ 2014-05-13 23:13 ` Xinliang David Li
0 siblings, 0 replies; 4+ messages in thread
From: Xinliang David Li @ 2014-05-13 23:13 UTC (permalink / raw)
To: Richard Biener; +Cc: Patrick Palka, GCC Patches
>
> 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
>>>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2014-05-13 23:13 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-12 3:42 [PATCH] Fix issue in uninit analysis (PR middle-end/61112) Patrick Palka
2014-05-13 9:09 ` Richard Biener
2014-05-13 22:20 ` Xinliang David Li
2014-05-13 23:13 ` Xinliang David Li
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).