predicate aware uninitialized variable analysis

[Xinliang David Li]

On Wed, Apr 14, 2010 at 3:44 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, Apr 13, 2010 at 9:23 PM, Xinliang David Li <davidxl@google.com> wrote:
>> The patch did not make into 4.5. Try it again for 4.6.
>>
>> There are new changes since the last attempt: The candidate list of
>> PHIs (which may produce undefined values) are not precomputed. In the
>> new patch, the predicate check will also be done on uses by phi
>> arguments. Only when the uses  in the phi arguments are not protected
>> properly by a predicate, the phi statement will then be added to the
>> worklist (and uses of its definitions will be checked later).
>>
>> Bootstrap and tested on x86_64/linux, and lots of apps.
>
> Can you instead of returning a sbitmap from compute_uninit_opnds_pos
> use an unsigned int mask (with proper checks for PHIs with too many
> operands which you don't want to handle because of complexity
> reasons anyway)?
>

Done. Did not bother to check when there are more operands that can be handled.


> +  bool is_postdom = false;
> +
> +  is_postdom = dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1);
> +
> +  if (!is_postdom)
> +    return false;
>
> save us code and simply write
>
>  if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
>   return false;
>

Done.

> You do compute control-dependences of some sort - can this
> code be shared with the control-dependence computation in
> tree-ssa-dce.c?  Thus, can you re-use that instead?  There's
> the same find_pdom stuff you have as well.

This is slightly different -- the one in this patch does control
dependence computation on demand for bb of interests, which is more
suitable.


>
> is_value_included_in looks like it should use code from tree-vrp.c.
>

Right, ideally the code should be shared. However there is no direct
code that can be shared in the current implementation -- the code in
value_inside_range is minimal, the majority of the code would be
converting the range in uninit check to value_range_t form which still
need to be written.

However, it may be worth to refactor vrp code to be some common
utility functions some day -- probably not in this patch.

> It's always a good opportunity to separate and abstract out code
> we can use from multiple places instead of re-inventing the
> wheel over and over.

Agree.


>
> find_matching_predicate_in_rest_chains also looks remotely
> similar to what tree-ssa-loop-niter.c:simplify_using_initial_conditions
> does.

Similar to the vrp case -- some refactoring is needed before sharing can happen.

>
> The pass is rather large, so I appreciate some review from other
> folks (I do believe it should try to use/enhance existing functionality).
>

Diego has done it internally.

> Btw, thanks for the large collection of testcases.  Can you check
> which uninitialized vars bugs this fixes and add them to the
> changelog entry?
>

Have checked some bug reports. Will update  the change log when submitting it.

Ok for check in?

Thanks,

David


> Richard.
>
>
>> Ok for 4.6?
>>
>> David
>>
>>
>>
>> On Wed, Jul 22, 2009 at 2:19 PM, Xinliang David Li <davidxl@google.com> wrote:
>>> Hi, this was a unsubmitted patch from last year. The patch implements
>>> predicate aware uninitialized variable warning in GCC. The
>>> implementation changed the way potentially uninitialized variables are
>>> warned as of today. Before the change, GCC gave a warning when an
>>> empty def is used by an phi operand. This is not only noisy, but also
>>> does not have precise source information on where the uninit reference
>>> is. After the change, the warning is only given on actual uses of phi
>>> defs that are potentially undefined (with empty operands or possibly
>>> empty operands -- defined transitively). In the analysis, The
>>> predicate guarding the use of potentially uninitialized variable is
>>> compared against the predicate guarding the definition. The predicate
>>> expressions are formed using both control dependence and data
>>> dependence information.  Some notes:
>>>
>>> 1. In current GCC, many of the false positives can be eliminated if
>>> jump threading kicks in, but slightly more complicated cases (as in
>>> the examples and test cases attached) will defeat it.
>>> 2. The predicate expression comparison/evaluation in the
>>> implementation does/can not rely on expr tree simplification/folding
>>> to do the job, and is a little rusty -- but good enough for the
>>> applications tested (and test cases accumulated).
>>> 3. Diego has spent lot of time reviewing the code last year.
>>> 4. bootstrap and tested on i686/linux. SPEC06/SPEC2k/internal apps.
>>>
>>> Let me know if this ok enough for mainline. If not, I will create a
>>> public branch and whoever is interested in enhancing the analysis can
>>> start contributing.
>>>
>>> Thanks,
>>>
>>> David
>>>
>>> ==============================================================
>>>
>>> The following are some examples. For more, take a look at the test
>>> cases included in the patch file.
>>>
>>>
>>> Example 1:
>>> ======================
>>>
>>> int g;
>>> void bar (void);
>>> void blah (int);
>>>
>>> int foo (int n, int m, int r)
>>> {
>>>  int flag = 0;
>>>  int v;
>>>
>>>  if (n)
>>>    {
>>>      v = r;
>>>      flag = 1;
>>>    }
>>>
>>>  if (m)
>>>    g++;
>>>  else
>>>    bar();
>>>
>>>  if (flag)
>>>    blah(v); /* { dg-bogus "uninitialized" "bogus uninitialized var
>>> warning" } */
>>>
>>>  return 0;
>>> }
>>>
>>>
>>>
>>> // Example 2 (flag check after inlining -- very common scenario)
>>> ==================================================================
>>>
>>> typedef long long int64;
>>> void incr ();
>>> bool is_valid (int);
>>> int  get_time ();
>>>
>>> class A
>>> {
>>> public:
>>>  A ();
>>>  ~A () {
>>>    if (I) delete I;
>>>  }
>>>
>>> private:
>>>  int* I;
>>> };
>>>
>>> bool get_url (A *);
>>>
>>> class M {
>>>
>>>  public:
>>> __attribute__ ((always_inline))  int GetC (int *c)  {
>>>
>>>    A details_str;
>>>    if (!get_url (&details_str))
>>>      {
>>>        incr ();
>>>        return 1;
>>>      }
>>>
>>>    *c = get_time ();
>>>    return -1;
>>>  }
>>>
>>>  void do_sth();
>>>  void do_sth2();
>>>
>>>  void P (int64 t)
>>>    {
>>>      int cc; /* { dg-bogus "uninitialized" "uninitialized variable
>>> warning" }  */
>>>      if (GetC (&cc) >= 0 )
>>>        return;
>>>
>>>      if (t && cc <= 0 )  /* { dg-bogus "uninitialized" "uninitialized
>>> variable warning" } */
>>>        {
>>>          this->do_sth();
>>>          return;
>>>        }
>>>
>>>    do_sth2();
>>>  }
>>> };
>>>
>>> M* m;
>>> void foo(int x)
>>> {
>>>  m = new M;
>>>  m->P(x);
>>> }
>>>
>>> // Example 3
>>> ========================
>>> int g;
>>> void bar();
>>> void blah(int);
>>>
>>> int foo (int n, int l, int m, int r)
>>> {
>>>  int v;
>>>
>>>  if (n > 10)
>>>    v = r;
>>>
>>>  if (m) g++;
>>>  else   bar();
>>>
>>>  if ( (n > 10) && (l < 100))
>>>      blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
>>>
>>>  if ( n > 100 )
>>>      blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
>>>
>>>  return 0;
>>> }
>>>
>>> int foo_2 (int n, int l, int m, int r)
>>> {
>>>  int v;
>>>
>>>  if (n > 10)
>>>    v = r;
>>>
>>>  if (m) g++;
>>>  else   bar();
>>>
>>>  if ( n < 10)
>>>      blah (v); /* { dg-warning "uninitialized" "warning" } */
>>>
>>>
>>>  return 0;
>>> }
>>>
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pred_uninit_r3.p
Type: text/x-pascal
Size: 90444 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20100422/f784b827/attachment.bin>