Re: [PATCH] Fix issue in uninit analysis (PR middle-end/61112)

[Xinliang David Li <davidxl at google dot com>]

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
>>