[PATCH] Fix a missed case in predicate analysis of the late uninit pass

[PATCH] Fix a missed case in predicate analysis of the late uninit pass

[Vladislav Ivanishin]

[-- Attachment #1: Type: text/plain, Size: 1551 bytes --]

Hi!

This is a fairly trivial change fixing a false negative in
-Wmaybe-uninitialized.  I am pretty sure this is simply an overlooked
case (is_value_included_in() is not meant to deal with the case where
both compare codes are NE_EXPRs, neither does it need to, since their
handling is trivial).

In a nutshell, what happens is values of v restricted by (v != 2) are
incorrectly considered a subset of values of v restricted by (v != 1).
As if "v != 2, therefore v != 1".

This is by no means a gcc-9 regression; I'll ping the patch once stage4
is over, if needed.

This came up when I was experimenting with moving the uninit passes
around.  On mainline, the late uninit pass runs very late, so reliably
triggering the affected path is a bit tricky.  So I created a GIMPLE
test (it reproduces the behavior precisely, but might be fragile
w.r.t. future versions of the textual representation) and then with a
hint from Alexander managed to produce a simple C test.  [By the way,
the first take was to insert an asm with a lot of newlines to prevent
the dom pass from rewriting the CFG due to high cost of duplicating
instructions.  This didn't work out; I think the dom pass does not
respect sizes of inline asms.  I plan to create a testcase and file a
bug later.]

I ran regression testing on x86_64-pc-linux-gnu and saw no new
regressions modulo a handful of flaky UNRESOLVED tests under
gcc.dg/tree-prof.  `BOOT_CFLAGS="-O -Wno-error=maybe-uninitialized
-Wmaybe-uninitialized" bootstrap` also succeeded producing no new
warnings.

OK for stage1?


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-a-missed-case-in-predicate-analysis-of-the-late-.patch --]
[-- Type: text/x-patch, Size: 3351 bytes --]

gcc/ChangeLog:

        * tree-ssa-uninit.c (is_pred_expr_subset_of): Correctly handle a case
        where the operand of both simple predicates is the same, both compare
        codes are NE_EXPR, and the integer values are different (e.g. neither of
        the predicate expressions 'v != 1' and 'v != 2' should be considered a
        subset of the other).

gcc/testsuite/ChangeLog:

        * gcc.dg/uninit-25-gimple.c: New test.
        * gcc.dg/uninit-25.c: New test.
---
 gcc/testsuite/gcc.dg/uninit-25-gimple.c | 41 +++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/uninit-25.c        | 23 ++++++++++++++
 gcc/tree-ssa-uninit.c                   |  3 ++
 3 files changed, 67 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/uninit-25-gimple.c
 create mode 100644 gcc/testsuite/gcc.dg/uninit-25.c

diff --git a/gcc/testsuite/gcc.dg/uninit-25-gimple.c b/gcc/testsuite/gcc.dg/uninit-25-gimple.c
new file mode 100644
index 00000000000..0c0acd6b83e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-25-gimple.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O -Wmaybe-uninitialized" } */
+
+unsigned int __GIMPLE (ssa,startwith("uninit1"))
+foo (unsigned int v)
+{
+  unsigned int undef;        /* { dg-warning "may be used uninitialized" } */
+  unsigned int _2;
+  unsigned int _9;
+  unsigned int _10;
+
+  __BB(2):
+  if (v_4(D) != 1u)
+    goto __BB3;
+  else
+    goto __BB4;
+
+  __BB(3):
+  undef_8 = 8u; // 'undef' is defined conditionally (under 'v != 1' predicate)
+  goto __BB4;
+
+  __BB(4):
+  // An undef value flows into a phi.
+  undef_1 = __PHI (__BB2: undef_5(D), __BB3: undef_8);
+  if (v_4(D) != 2u) // This condition is neither a superset nor a subset of 'v != 1'.
+    goto __BB5;
+  else
+    goto __BB6;
+
+  __BB(5):
+  _9 = undef_1; // The phi value is used here (under 'v != 2' predicate).
+  goto __BB7;
+
+  __BB(6):
+  _10 = v_4(D);
+  goto __BB7;
+
+  __BB(7):
+  _2 = __PHI (__BB5: _9, __BB6: _10);
+  return _2;
+}
diff --git a/gcc/testsuite/gcc.dg/uninit-25.c b/gcc/testsuite/gcc.dg/uninit-25.c
new file mode 100644
index 00000000000..ffffce3f91c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-25.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O -Wmaybe-uninitialized" } */
+
+extern unsigned bar (void);
+extern void quux (void);
+
+unsigned foo (unsigned v)
+{
+  unsigned u;
+  if (v != 1)
+    u = bar ();
+
+  // Prevent the "dom" pass from changing the CFG layout based on the inference
+  // 'if (v != 1) is false then (v != 2) is true'.  (Now it would have to
+  // duplicate the loop in order to do so, which is deemed expensive.)
+  for (int i = 0; i < 10; i++)
+    quux ();
+
+  if (v != 2)
+    return u;       /* { dg-warning "may be used uninitialized" } */
+
+  return 0;
+}
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
index 55a55a05c96..1de7d21d2eb 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -1488,6 +1488,9 @@ is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
   if (expr2.invert)
     code2 = invert_tree_comparison (code2, false);
 
+  if (code1 == NE_EXPR && code2 == NE_EXPR)
+    return false;
+
   if ((code1 == EQ_EXPR || code1 == BIT_AND_EXPR) && code2 == BIT_AND_EXPR)
     return (wi::to_wide (expr1.pred_rhs)
 	    == (wi::to_wide (expr1.pred_rhs) & wi::to_wide (expr2.pred_rhs)));
-- 
2.20.1


[-- Attachment #3: Type: text/plain, Size: 10 bytes --]


-- 
Vlad

Re: [PATCH] Fix a missed case in predicate analysis of the late uninit pass

[Richard Biener]

On Mon, Apr 1, 2019 at 5:36 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>
> Hi!
>
> This is a fairly trivial change fixing a false negative in
> -Wmaybe-uninitialized.  I am pretty sure this is simply an overlooked
> case (is_value_included_in() is not meant to deal with the case where
> both compare codes are NE_EXPRs, neither does it need to, since their
> handling is trivial).
>
> In a nutshell, what happens is values of v restricted by (v != 2) are
> incorrectly considered a subset of values of v restricted by (v != 1).
> As if "v != 2, therefore v != 1".
>
> This is by no means a gcc-9 regression; I'll ping the patch once stage4
> is over, if needed.
>
> This came up when I was experimenting with moving the uninit passes
> around.  On mainline, the late uninit pass runs very late, so reliably
> triggering the affected path is a bit tricky.  So I created a GIMPLE
> test (it reproduces the behavior precisely, but might be fragile
> w.r.t. future versions of the textual representation) and then with a
> hint from Alexander managed to produce a simple C test.  [By the way,
> the first take was to insert an asm with a lot of newlines to prevent
> the dom pass from rewriting the CFG due to high cost of duplicating
> instructions.  This didn't work out; I think the dom pass does not
> respect sizes of inline asms.  I plan to create a testcase and file a
> bug later.]
>
> I ran regression testing on x86_64-pc-linux-gnu and saw no new
> regressions modulo a handful of flaky UNRESOLVED tests under
> gcc.dg/tree-prof.  `BOOT_CFLAGS="-O -Wno-error=maybe-uninitialized
> -Wmaybe-uninitialized" bootstrap` also succeeded producing no new
> warnings.
>
> OK for stage1?

Hum.  While definitely two NE_EXPR do not work correctly I'd like
to see a positive test since LT_EXPR doesn't work either?  Specifically
the code falls through to test is_value_included_in which seems to
assume code1 == code2.

To me it looks like is_value_includeds comment should be clarified to
say

/* Returns true if all values X satisfying X CMPC VAL satisfy
   X CMPC BOUNDARY.  */

That is, "all values in the range" in the current comment is under-specified
since VAL is just a single value.

So I wonder what testcases regress if we remove the && code2 != NE_EXPR
case?  That way we see what the intention was.  A patch should then
change that to

  if ((code1 != code2)
      || !(<condition on code1> && code2 == NE_EXPR))
   return false;

to explicitely spell out what case was meant here.

Richard.

>
> --
> Vlad

Re: [PATCH] Fix a missed case in predicate analysis of the late uninit pass

[Vladislav Ivanishin]

[-- Attachment #1: Type: text/plain, Size: 5657 bytes --]

Richard Biener <richard.guenther@gmail.com> writes:

> On Mon, Apr 1, 2019 at 5:36 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>>
>> Hi!
>>
>> This is a fairly trivial change fixing a false negative in
>> -Wmaybe-uninitialized.  I am pretty sure this is simply an overlooked
>> case (is_value_included_in() is not meant to deal with the case where
>> both compare codes are NE_EXPRs, neither does it need to, since their
>> handling is trivial).
>>
>> In a nutshell, what happens is values of v restricted by (v != 2) are
>> incorrectly considered a subset of values of v restricted by (v != 1).
>> As if "v != 2, therefore v != 1".
>>
>> This is by no means a gcc-9 regression; I'll ping the patch once stage4
>> is over, if needed.
>>
>> This came up when I was experimenting with moving the uninit passes
>> around.  On mainline, the late uninit pass runs very late, so reliably
>> triggering the affected path is a bit tricky.  So I created a GIMPLE
>> test (it reproduces the behavior precisely, but might be fragile
>> w.r.t. future versions of the textual representation) and then with a
>> hint from Alexander managed to produce a simple C test.  [By the way,
>> the first take was to insert an asm with a lot of newlines to prevent
>> the dom pass from rewriting the CFG due to high cost of duplicating
>> instructions.  This didn't work out; I think the dom pass does not
>> respect sizes of inline asms.  I plan to create a testcase and file a
>> bug later.]
>>
>> I ran regression testing on x86_64-pc-linux-gnu and saw no new
>> regressions modulo a handful of flaky UNRESOLVED tests under
>> gcc.dg/tree-prof.  `BOOT_CFLAGS="-O -Wno-error=maybe-uninitialized
>> -Wmaybe-uninitialized" bootstrap` also succeeded producing no new
>> warnings.
>>
>> OK for stage1?
>
> Hum.  While definitely two NE_EXPR do not work correctly I'd like
> to see a positive test since LT_EXPR doesn't work either?

Right, thanks.  The case that was not covered well is actually when
cond2 == NE_EXPR (arbitrary cond1).  I created 2 new tests: uninit-26.c
demonstrates a false negative, and uninit-27-gimple.c a false positive
with trunk.

> Specifically the code falls through to test is_value_included_in which
> seems to assume code1 == code2.

The function is_value_included_in itself only cares about one condition
code (I'll expound on this below).  I agree though that the second part
of the comment seems to assume that.

Please take a look at the updated patch.  The rationale is as follows.

When we have 2 potentially comparable predicates in
is_pred_expr_subset_of, there are basically two things we want to check.

1) Whether two ranges with identical condition codes are nested.  This
is done straightforwardly with is_value_included_in.

2) Whether X CMPC VAL1 is nested in X != VAL2.  Which is easy: this
happens iff the set (a.k.a "range") {X: X CMPC VAL1 is true} doesn't
contain ("cover") VAL2, in other words iff VAL2 CMPC VAL1 is false.

Only, the logic of 2) is faulty when X CMPC VAL1 is not a range bounded
on one end (this happens when, and only when CMPC is NE_EXPR; the range
is then unbounded on both ends and can only be nested in X != VAL2, if
VAL1 == VAL2).

3) Whether X != VAL1 is nested in X CMPC VAL2, but that is always false
unless CMPC is NE_EXPR, which is already considered.

> To me it looks like is_value_includeds comment should be clarified to
> say
>
> /* Returns true if all values X satisfying X CMPC VAL satisfy
>    X CMPC BOUNDARY.  */

This is indeed more clear than the current comment, and the meaning is
the same.  I suggest however to not discuss nestedness of ranges in this
comment at all.

> That is, "all values in the range" in the current comment is
> under-specified since VAL is just a single value.

The range is implied, since only one CMPC is passed.  (If CMPC is
NE_EXPR, however, then I guess the range would only be known in the
caller, but the function does not work correctly for this purpose --
hence the patch to not call it then.)  But is_value_included_in actually
only cares about one value and one set anyway, as the name suggests.

So I think the second part of the comment is supposed to help to think
about applying this function for its main use-case (this function is
used twice, actually: in the case we are discussing there is a range
whose nestedness the calling code is testing, in the other case there is
just a constant), whereas the first part simply states what the function
does.  I'd say, the second part of the comment should be rewritten or
discarded, while the first should be kept.  OTOH, it might have been
helpful to the person who wrote this code.

> So I wonder what testcases regress if we remove the && code2 != NE_EXPR
> case?  That way we see what the intention was.  A patch should then
> change that to
>
>   if ((code1 != code2)
>       || !(<condition on code1> && code2 == NE_EXPR))
>    return false;
>
> to explicitely spell out what case was meant here.

make check-gcc RUNTESTFLAGS='dg.exp=uninit*' gives one regression:

gcc.dg/uninit-pred-9_b.c bogus warning (test for bogus messages, line 24)

This test boils down to this:

     if (m != 100)
        v = sth;
    ...
     if (m < 99)
        use (v);

So with the code2 != NE_EXPR check in place, expr1 = {m, 98, LE_EXPR},
expr2 = {m, 100, NE_EXPR}, and code2 = NE_EXPR are passed to
is_value_included_in, which returns true: 98 is included in m != 100
and true means "no warning".  This does not clarify the intention for
me, since this only works by luck; the condition that needs to be tested
cannot be tested with passing NE_EXPR to is_value_included_in, as the
new uninit-26.c test shows.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-NE_EXPR-handling-in-predicate-analysis-of-the-la.patch --]
[-- Type: text/x-patch, Size: 6365 bytes --]

From 9f127898482a3830c55fbe9c33945182e0a975a6 Mon Sep 17 00:00:00 2001
From: Vladislav Ivanishin <vlad@ispras.ru>
Date: Wed, 27 Mar 2019 15:09:56 +0300
Subject: [PATCH] Fix NE_EXPR handling in predicate analysis of the late uninit
 pass

gcc/ChangeLog:

	* tree-ssa-uninit.c (is_pred_expr_subset_of): Correctly handle cases
	where cond2 is NE_EXPR.
	(is_value_included_in): Update comment.

gcc/testsuite/ChangeLog:

        * gcc.dg/uninit-25-gimple.c: New test.
        * gcc.dg/uninit-25.c: New test.
        * gcc.dg/uninit-26.c: New test.
        * gcc.dg/uninit-27-gimple.c: New test.
---
 gcc/testsuite/gcc.dg/uninit-25-gimple.c | 41 +++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/uninit-25.c        | 23 ++++++++++++++
 gcc/testsuite/gcc.dg/uninit-26.c        | 23 ++++++++++++++
 gcc/testsuite/gcc.dg/uninit-27-gimple.c | 41 +++++++++++++++++++++++++
 gcc/tree-ssa-uninit.c                   | 11 +++++--
 5 files changed, 136 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/uninit-25-gimple.c
 create mode 100644 gcc/testsuite/gcc.dg/uninit-25.c
 create mode 100644 gcc/testsuite/gcc.dg/uninit-26.c
 create mode 100644 gcc/testsuite/gcc.dg/uninit-27-gimple.c

diff --git a/gcc/testsuite/gcc.dg/uninit-25-gimple.c b/gcc/testsuite/gcc.dg/uninit-25-gimple.c
new file mode 100644
index 00000000000..0c0acd6b83e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-25-gimple.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O -Wmaybe-uninitialized" } */
+
+unsigned int __GIMPLE (ssa,startwith("uninit1"))
+foo (unsigned int v)
+{
+  unsigned int undef;        /* { dg-warning "may be used uninitialized" } */
+  unsigned int _2;
+  unsigned int _9;
+  unsigned int _10;
+
+  __BB(2):
+  if (v_4(D) != 1u)
+    goto __BB3;
+  else
+    goto __BB4;
+
+  __BB(3):
+  undef_8 = 8u; // 'undef' is defined conditionally (under 'v != 1' predicate)
+  goto __BB4;
+
+  __BB(4):
+  // An undef value flows into a phi.
+  undef_1 = __PHI (__BB2: undef_5(D), __BB3: undef_8);
+  if (v_4(D) != 2u) // This condition is neither a superset nor a subset of 'v != 1'.
+    goto __BB5;
+  else
+    goto __BB6;
+
+  __BB(5):
+  _9 = undef_1; // The phi value is used here (under 'v != 2' predicate).
+  goto __BB7;
+
+  __BB(6):
+  _10 = v_4(D);
+  goto __BB7;
+
+  __BB(7):
+  _2 = __PHI (__BB5: _9, __BB6: _10);
+  return _2;
+}
diff --git a/gcc/testsuite/gcc.dg/uninit-25.c b/gcc/testsuite/gcc.dg/uninit-25.c
new file mode 100644
index 00000000000..ffffce3f91c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-25.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O -Wmaybe-uninitialized" } */
+
+extern unsigned bar (void);
+extern void quux (void);
+
+unsigned foo (unsigned v)
+{
+  unsigned u;
+  if (v != 1)
+    u = bar ();
+
+  // Prevent the "dom" pass from changing the CFG layout based on the inference
+  // 'if (v != 1) is false then (v != 2) is true'.  (Now it would have to
+  // duplicate the loop in order to do so, which is deemed expensive.)
+  for (int i = 0; i < 10; i++)
+    quux ();
+
+  if (v != 2)
+    return u;       /* { dg-warning "may be used uninitialized" } */
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/uninit-26.c b/gcc/testsuite/gcc.dg/uninit-26.c
new file mode 100644
index 00000000000..60ac48cdc50
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-26.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O -Wmaybe-uninitialized" } */
+
+extern unsigned bar (void);
+extern void quux (void);
+
+unsigned foo (unsigned v)
+{
+  unsigned u;
+  if (v != 100)
+    u = bar ();
+
+  // Prevent the "dom" pass from changing the CFG layout based on the inference
+  // 'if (v != 100) is false then (v < 105) is true'.  (Now it would have to
+  // duplicate the loop in order to do so, which is deemed expensive.)
+  for (int i = 0; i < 10; i++)
+    quux ();
+
+  if (v < 105) /* v == 100 falls into this range.  */
+    return u;       /* { dg-warning "may be used uninitialized" }  */
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/uninit-27-gimple.c b/gcc/testsuite/gcc.dg/uninit-27-gimple.c
new file mode 100644
index 00000000000..f75469d8ef8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-27-gimple.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O -Wmaybe-uninitialized" } */
+
+unsigned int __GIMPLE (ssa,startwith("uninit1"))
+foo (unsigned int v)
+{
+  unsigned int undef;        /* { dg-bogus "may be used uninitialized" } */
+  unsigned int _2;
+  unsigned int _9;
+  unsigned int _10;
+
+  __BB(2):
+  if (v_4(D) != 100u)
+    goto __BB3;
+  else
+    goto __BB4;
+
+  __BB(3):
+  undef_8 = 8u; // 'undef' is defined conditionally (under 'v != 100' predicate)
+  goto __BB4;
+
+  __BB(4):
+  // An undef value flows into a phi.
+  undef_1 = __PHI (__BB2: undef_5(D), __BB3: undef_8);
+  if (v_4(D) < 100u)
+    goto __BB5;
+  else
+    goto __BB6;
+
+  __BB(5):
+  _9 = undef_1; // The phi value is used here (under 'v < 100' predicate).
+  goto __BB7;
+
+  __BB(6):
+  _10 = v_4(D);
+  goto __BB7;
+
+  __BB(7):
+  _2 = __PHI (__BB5: _9, __BB6: _10);
+  return _2;
+}
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
index 55a55a05c96..7976072ca08 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -1011,8 +1011,7 @@ get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert)
   return tc;
 }
 
-/* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
-   all values in the range satisfies (x CMPC BOUNDARY) == true.  */
+/* Returns true if VAL falls in the domain defined by BOUNDARY and CMPC.  */
 
 static bool
 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
@@ -1488,11 +1487,17 @@ is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
   if (expr2.invert)
     code2 = invert_tree_comparison (code2, false);
 
+  if (code2 == NE_EXPR && code1 == NE_EXPR)
+    return false;
+
+  if (code2 == NE_EXPR)
+    return !is_value_included_in (expr2.pred_rhs, expr1.pred_rhs, code1);
+
   if ((code1 == EQ_EXPR || code1 == BIT_AND_EXPR) && code2 == BIT_AND_EXPR)
     return (wi::to_wide (expr1.pred_rhs)
 	    == (wi::to_wide (expr1.pred_rhs) & wi::to_wide (expr2.pred_rhs)));
 
-  if (code1 != code2 && code2 != NE_EXPR)
+  if (code1 != code2)
     return false;
 
   if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
-- 
2.20.1

Re: [PATCH] Fix a missed case in predicate analysis of the late uninit pass

[Richard Biener]

On Thu, Apr 4, 2019 at 4:05 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>
> Richard Biener <richard.guenther@gmail.com> writes:
>
> > On Mon, Apr 1, 2019 at 5:36 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
> >>
> >> Hi!
> >>
> >> This is a fairly trivial change fixing a false negative in
> >> -Wmaybe-uninitialized.  I am pretty sure this is simply an overlooked
> >> case (is_value_included_in() is not meant to deal with the case where
> >> both compare codes are NE_EXPRs, neither does it need to, since their
> >> handling is trivial).
> >>
> >> In a nutshell, what happens is values of v restricted by (v != 2) are
> >> incorrectly considered a subset of values of v restricted by (v != 1).
> >> As if "v != 2, therefore v != 1".
> >>
> >> This is by no means a gcc-9 regression; I'll ping the patch once stage4
> >> is over, if needed.
> >>
> >> This came up when I was experimenting with moving the uninit passes
> >> around.  On mainline, the late uninit pass runs very late, so reliably
> >> triggering the affected path is a bit tricky.  So I created a GIMPLE
> >> test (it reproduces the behavior precisely, but might be fragile
> >> w.r.t. future versions of the textual representation) and then with a
> >> hint from Alexander managed to produce a simple C test.  [By the way,
> >> the first take was to insert an asm with a lot of newlines to prevent
> >> the dom pass from rewriting the CFG due to high cost of duplicating
> >> instructions.  This didn't work out; I think the dom pass does not
> >> respect sizes of inline asms.  I plan to create a testcase and file a
> >> bug later.]
> >>
> >> I ran regression testing on x86_64-pc-linux-gnu and saw no new
> >> regressions modulo a handful of flaky UNRESOLVED tests under
> >> gcc.dg/tree-prof.  `BOOT_CFLAGS="-O -Wno-error=maybe-uninitialized
> >> -Wmaybe-uninitialized" bootstrap` also succeeded producing no new
> >> warnings.
> >>
> >> OK for stage1?
> >
> > Hum.  While definitely two NE_EXPR do not work correctly I'd like
> > to see a positive test since LT_EXPR doesn't work either?
>
> Right, thanks.  The case that was not covered well is actually when
> cond2 == NE_EXPR (arbitrary cond1).  I created 2 new tests: uninit-26.c
> demonstrates a false negative, and uninit-27-gimple.c a false positive
> with trunk.
>
> > Specifically the code falls through to test is_value_included_in which
> > seems to assume code1 == code2.
>
> The function is_value_included_in itself only cares about one condition
> code (I'll expound on this below).  I agree though that the second part
> of the comment seems to assume that.
>
> Please take a look at the updated patch.  The rationale is as follows.
>
> When we have 2 potentially comparable predicates in
> is_pred_expr_subset_of, there are basically two things we want to check.
>
> 1) Whether two ranges with identical condition codes are nested.  This
> is done straightforwardly with is_value_included_in.
>
> 2) Whether X CMPC VAL1 is nested in X != VAL2.  Which is easy: this
> happens iff the set (a.k.a "range") {X: X CMPC VAL1 is true} doesn't
> contain ("cover") VAL2, in other words iff VAL2 CMPC VAL1 is false.
>
> Only, the logic of 2) is faulty when X CMPC VAL1 is not a range bounded
> on one end (this happens when, and only when CMPC is NE_EXPR; the range
> is then unbounded on both ends and can only be nested in X != VAL2, if
> VAL1 == VAL2).
>
> 3) Whether X != VAL1 is nested in X CMPC VAL2, but that is always false
> unless CMPC is NE_EXPR, which is already considered.

OK.  Your patch does

+  if (code2 == NE_EXPR && code1 == NE_EXPR)
+    return false;

but it should instead return operand_equal_p (expr1.pred_rhs,
expr2.pred_rhs, 0)?

> > To me it looks like is_value_includeds comment should be clarified to
> > say
> >
> > /* Returns true if all values X satisfying X CMPC VAL satisfy
> >    X CMPC BOUNDARY.  */
>
> This is indeed more clear than the current comment, and the meaning is
> the same.  I suggest however to not discuss nestedness of ranges in this
> comment at all.
>
> > That is, "all values in the range" in the current comment is
> > under-specified since VAL is just a single value.
>
> The range is implied, since only one CMPC is passed.  (If CMPC is
> NE_EXPR, however, then I guess the range would only be known in the
> caller, but the function does not work correctly for this purpose --
> hence the patch to not call it then.)  But is_value_included_in actually
> only cares about one value and one set anyway, as the name suggests.
>
> So I think the second part of the comment is supposed to help to think
> about applying this function for its main use-case (this function is
> used twice, actually: in the case we are discussing there is a range
> whose nestedness the calling code is testing, in the other case there is
> just a constant), whereas the first part simply states what the function
> does.  I'd say, the second part of the comment should be rewritten or
> discarded, while the first should be kept.  OTOH, it might have been
> helpful to the person who wrote this code.
>
> > So I wonder what testcases regress if we remove the && code2 != NE_EXPR
> > case?  That way we see what the intention was.  A patch should then
> > change that to
> >
> >   if ((code1 != code2)
> >       || !(<condition on code1> && code2 == NE_EXPR))
> >    return false;
> >
> > to explicitely spell out what case was meant here.
>
> make check-gcc RUNTESTFLAGS='dg.exp=uninit*' gives one regression:
>
> gcc.dg/uninit-pred-9_b.c bogus warning (test for bogus messages, line 24)
>
> This test boils down to this:
>
>      if (m != 100)
>         v = sth;
>     ...
>      if (m < 99)
>         use (v);
>
> So with the code2 != NE_EXPR check in place, expr1 = {m, 98, LE_EXPR},
> expr2 = {m, 100, NE_EXPR}, and code2 = NE_EXPR are passed to
> is_value_included_in, which returns true: 98 is included in m != 100
> and true means "no warning".  This does not clarify the intention for
> me, since this only works by luck; the condition that needs to be tested
> cannot be tested with passing NE_EXPR to is_value_included_in, as the
> new uninit-26.c test shows.

The new patch is OK with the change suggested above and the new
comment for is_value_included_in spelling out how BOUNDARY and CMPC
form the domain, all x so that x CMPC BOUNDARY is true vs. the also
possible all x so that BOUNDARY CMPC x is true.

Thanks for explaining and the extra testcases.
Richard.

Re: [PATCH] Fix a missed case in predicate analysis of the late uninit pass

[Vladislav Ivanishin]

[-- Attachment #1: Type: text/plain, Size: 7526 bytes --]

Richard Biener <richard.guenther@gmail.com> writes:

> On Thu, Apr 4, 2019 at 4:05 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>>
>> Richard Biener <richard.guenther@gmail.com> writes:
>>
>> > On Mon, Apr 1, 2019 at 5:36 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>> >>
>> >> Hi!
>> >>
>> >> This is a fairly trivial change fixing a false negative in
>> >> -Wmaybe-uninitialized.  I am pretty sure this is simply an overlooked
>> >> case (is_value_included_in() is not meant to deal with the case where
>> >> both compare codes are NE_EXPRs, neither does it need to, since their
>> >> handling is trivial).
>> >>
>> >> In a nutshell, what happens is values of v restricted by (v != 2) are
>> >> incorrectly considered a subset of values of v restricted by (v != 1).
>> >> As if "v != 2, therefore v != 1".
>> >>
>> >> This is by no means a gcc-9 regression; I'll ping the patch once stage4
>> >> is over, if needed.
>> >>
>> >> This came up when I was experimenting with moving the uninit passes
>> >> around.  On mainline, the late uninit pass runs very late, so reliably
>> >> triggering the affected path is a bit tricky.  So I created a GIMPLE
>> >> test (it reproduces the behavior precisely, but might be fragile
>> >> w.r.t. future versions of the textual representation) and then with a
>> >> hint from Alexander managed to produce a simple C test.  [By the way,
>> >> the first take was to insert an asm with a lot of newlines to prevent
>> >> the dom pass from rewriting the CFG due to high cost of duplicating
>> >> instructions.  This didn't work out; I think the dom pass does not
>> >> respect sizes of inline asms.  I plan to create a testcase and file a
>> >> bug later.]
>> >>
>> >> I ran regression testing on x86_64-pc-linux-gnu and saw no new
>> >> regressions modulo a handful of flaky UNRESOLVED tests under
>> >> gcc.dg/tree-prof.  `BOOT_CFLAGS="-O -Wno-error=maybe-uninitialized
>> >> -Wmaybe-uninitialized" bootstrap` also succeeded producing no new
>> >> warnings.
>> >>
>> >> OK for stage1?
>> >
>> > Hum.  While definitely two NE_EXPR do not work correctly I'd like
>> > to see a positive test since LT_EXPR doesn't work either?
>>
>> Right, thanks.  The case that was not covered well is actually when
>> cond2 == NE_EXPR (arbitrary cond1).  I created 2 new tests: uninit-26.c
>> demonstrates a false negative, and uninit-27-gimple.c a false positive
>> with trunk.
>>
>> > Specifically the code falls through to test is_value_included_in which
>> > seems to assume code1 == code2.
>>
>> The function is_value_included_in itself only cares about one condition
>> code (I'll expound on this below).  I agree though that the second part
>> of the comment seems to assume that.
>>
>> Please take a look at the updated patch.  The rationale is as follows.
>>
>> When we have 2 potentially comparable predicates in
>> is_pred_expr_subset_of, there are basically two things we want to check.
>>
>> 1) Whether two ranges with identical condition codes are nested.  This
>> is done straightforwardly with is_value_included_in.
>>
>> 2) Whether X CMPC VAL1 is nested in X != VAL2.  Which is easy: this
>> happens iff the set (a.k.a "range") {X: X CMPC VAL1 is true} doesn't
>> contain ("cover") VAL2, in other words iff VAL2 CMPC VAL1 is false.
>>
>> Only, the logic of 2) is faulty when X CMPC VAL1 is not a range bounded
>> on one end (this happens when, and only when CMPC is NE_EXPR; the range
>> is then unbounded on both ends and can only be nested in X != VAL2, if
>> VAL1 == VAL2).
>>
>> 3) Whether X != VAL1 is nested in X CMPC VAL2, but that is always false
>> unless CMPC is NE_EXPR, which is already considered.
>
> OK.  Your patch does
>
> +  if (code2 == NE_EXPR && code1 == NE_EXPR)
> +    return false;
>
> but it should instead return operand_equal_p (expr1.pred_rhs,
> expr2.pred_rhs, 0)?

This doesn't change the semantics, because the case with equal rhs's is
already considered at the beginning of this function:

static bool
is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
{
  enum tree_code code1, code2;

  if (pred_equal_p (expr1, expr2))
    return true;

So I think, leaving this part of the patch as is results in less
localized/explicit code, but better matches the overall style of this
function.  Or perhaps add a checking assert?

  if (code1 == code2)
    gcc_checking_assert (!operand_equal_p (expr1.pred_rhs,
                                           expr2.pred_rhs, 0))

>> > To me it looks like is_value_includeds comment should be clarified to
>> > say
>> >
>> > /* Returns true if all values X satisfying X CMPC VAL satisfy
>> >    X CMPC BOUNDARY.  */
>>
>> This is indeed more clear than the current comment, and the meaning is
>> the same.  I suggest however to not discuss nestedness of ranges in this
>> comment at all.
>>
>> > That is, "all values in the range" in the current comment is
>> > under-specified since VAL is just a single value.
>>
>> The range is implied, since only one CMPC is passed.  (If CMPC is
>> NE_EXPR, however, then I guess the range would only be known in the
>> caller, but the function does not work correctly for this purpose --
>> hence the patch to not call it then.)  But is_value_included_in actually
>> only cares about one value and one set anyway, as the name suggests.
>>
>> So I think the second part of the comment is supposed to help to think
>> about applying this function for its main use-case (this function is
>> used twice, actually: in the case we are discussing there is a range
>> whose nestedness the calling code is testing, in the other case there is
>> just a constant), whereas the first part simply states what the function
>> does.  I'd say, the second part of the comment should be rewritten or
>> discarded, while the first should be kept.  OTOH, it might have been
>> helpful to the person who wrote this code.
>>
>> > So I wonder what testcases regress if we remove the && code2 != NE_EXPR
>> > case?  That way we see what the intention was.  A patch should then
>> > change that to
>> >
>> >   if ((code1 != code2)
>> >       || !(<condition on code1> && code2 == NE_EXPR))
>> >    return false;
>> >
>> > to explicitely spell out what case was meant here.
>>
>> make check-gcc RUNTESTFLAGS='dg.exp=uninit*' gives one regression:
>>
>> gcc.dg/uninit-pred-9_b.c bogus warning (test for bogus messages, line 24)
>>
>> This test boils down to this:
>>
>>      if (m != 100)
>>         v = sth;
>>     ...
>>      if (m < 99)
>>         use (v);
>>
>> So with the code2 != NE_EXPR check in place, expr1 = {m, 98, LE_EXPR},
>> expr2 = {m, 100, NE_EXPR}, and code2 = NE_EXPR are passed to
>> is_value_included_in, which returns true: 98 is included in m != 100
>> and true means "no warning".  This does not clarify the intention for
>> me, since this only works by luck; the condition that needs to be tested
>> cannot be tested with passing NE_EXPR to is_value_included_in, as the
>> new uninit-26.c test shows.
>
> The new patch is OK with the change suggested above and the new
> comment for is_value_included_in spelling out how BOUNDARY and CMPC
> form the domain, all x so that x CMPC BOUNDARY is true vs. the also
> possible all x so that BOUNDARY CMPC x is true.

I updated this to say /* Returns whether VAL CMPC BOUNDARY is true.  */
As actually there is no need to define any "domain" entity here.

If this looks good, I'll ping the patch when stage1 opens, or ask
someone to apply.

> Thanks for explaining and the extra testcases.
> Richard.

Thank you for reviewing.
Vlad


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-NE_EXPR-handling-in-predicate-analysis-of-the-la.patch --]
[-- Type: text/x-patch, Size: 6100 bytes --]

gcc/ChangeLog:

	* tree-ssa-uninit.c (is_pred_expr_subset_of): Correctly handle cases
	where cond2 is NE_EXPR.
	(is_value_included_in): Update comment.

gcc/testsuite/ChangeLog:

        * gcc.dg/uninit-25-gimple.c: New test.
        * gcc.dg/uninit-25.c: New test.
        * gcc.dg/uninit-26.c: New test.
        * gcc.dg/uninit-27-gimple.c: New test.
---
 gcc/testsuite/gcc.dg/uninit-25-gimple.c | 41 +++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/uninit-25.c        | 23 ++++++++++++++
 gcc/testsuite/gcc.dg/uninit-26.c        | 23 ++++++++++++++
 gcc/testsuite/gcc.dg/uninit-27-gimple.c | 41 +++++++++++++++++++++++++
 gcc/tree-ssa-uninit.c                   | 11 +++++--
 5 files changed, 136 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/uninit-25-gimple.c
 create mode 100644 gcc/testsuite/gcc.dg/uninit-25.c
 create mode 100644 gcc/testsuite/gcc.dg/uninit-26.c
 create mode 100644 gcc/testsuite/gcc.dg/uninit-27-gimple.c

diff --git a/gcc/testsuite/gcc.dg/uninit-25-gimple.c b/gcc/testsuite/gcc.dg/uninit-25-gimple.c
new file mode 100644
index 00000000000..0c0acd6b83e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-25-gimple.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O -Wmaybe-uninitialized" } */
+
+unsigned int __GIMPLE (ssa,startwith("uninit1"))
+foo (unsigned int v)
+{
+  unsigned int undef;        /* { dg-warning "may be used uninitialized" } */
+  unsigned int _2;
+  unsigned int _9;
+  unsigned int _10;
+
+  __BB(2):
+  if (v_4(D) != 1u)
+    goto __BB3;
+  else
+    goto __BB4;
+
+  __BB(3):
+  undef_8 = 8u; // 'undef' is defined conditionally (under 'v != 1' predicate)
+  goto __BB4;
+
+  __BB(4):
+  // An undef value flows into a phi.
+  undef_1 = __PHI (__BB2: undef_5(D), __BB3: undef_8);
+  if (v_4(D) != 2u) // This condition is neither a superset nor a subset of 'v != 1'.
+    goto __BB5;
+  else
+    goto __BB6;
+
+  __BB(5):
+  _9 = undef_1; // The phi value is used here (under 'v != 2' predicate).
+  goto __BB7;
+
+  __BB(6):
+  _10 = v_4(D);
+  goto __BB7;
+
+  __BB(7):
+  _2 = __PHI (__BB5: _9, __BB6: _10);
+  return _2;
+}
diff --git a/gcc/testsuite/gcc.dg/uninit-25.c b/gcc/testsuite/gcc.dg/uninit-25.c
new file mode 100644
index 00000000000..ffffce3f91c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-25.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O -Wmaybe-uninitialized" } */
+
+extern unsigned bar (void);
+extern void quux (void);
+
+unsigned foo (unsigned v)
+{
+  unsigned u;
+  if (v != 1)
+    u = bar ();
+
+  // Prevent the "dom" pass from changing the CFG layout based on the inference
+  // 'if (v != 1) is false then (v != 2) is true'.  (Now it would have to
+  // duplicate the loop in order to do so, which is deemed expensive.)
+  for (int i = 0; i < 10; i++)
+    quux ();
+
+  if (v != 2)
+    return u;       /* { dg-warning "may be used uninitialized" } */
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/uninit-26.c b/gcc/testsuite/gcc.dg/uninit-26.c
new file mode 100644
index 00000000000..60ac48cdc50
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-26.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O -Wmaybe-uninitialized" } */
+
+extern unsigned bar (void);
+extern void quux (void);
+
+unsigned foo (unsigned v)
+{
+  unsigned u;
+  if (v != 100)
+    u = bar ();
+
+  // Prevent the "dom" pass from changing the CFG layout based on the inference
+  // 'if (v != 100) is false then (v < 105) is true'.  (Now it would have to
+  // duplicate the loop in order to do so, which is deemed expensive.)
+  for (int i = 0; i < 10; i++)
+    quux ();
+
+  if (v < 105) /* v == 100 falls into this range.  */
+    return u;       /* { dg-warning "may be used uninitialized" }  */
+
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/uninit-27-gimple.c b/gcc/testsuite/gcc.dg/uninit-27-gimple.c
new file mode 100644
index 00000000000..f75469d8ef8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/uninit-27-gimple.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-fgimple -O -Wmaybe-uninitialized" } */
+
+unsigned int __GIMPLE (ssa,startwith("uninit1"))
+foo (unsigned int v)
+{
+  unsigned int undef;        /* { dg-bogus "may be used uninitialized" } */
+  unsigned int _2;
+  unsigned int _9;
+  unsigned int _10;
+
+  __BB(2):
+  if (v_4(D) != 100u)
+    goto __BB3;
+  else
+    goto __BB4;
+
+  __BB(3):
+  undef_8 = 8u; // 'undef' is defined conditionally (under 'v != 100' predicate)
+  goto __BB4;
+
+  __BB(4):
+  // An undef value flows into a phi.
+  undef_1 = __PHI (__BB2: undef_5(D), __BB3: undef_8);
+  if (v_4(D) < 100u)
+    goto __BB5;
+  else
+    goto __BB6;
+
+  __BB(5):
+  _9 = undef_1; // The phi value is used here (under 'v < 100' predicate).
+  goto __BB7;
+
+  __BB(6):
+  _10 = v_4(D);
+  goto __BB7;
+
+  __BB(7):
+  _2 = __PHI (__BB5: _9, __BB6: _10);
+  return _2;
+}
diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
index b263d0a3fb9..b65189d64c6 100644
--- a/gcc/tree-ssa-uninit.c
+++ b/gcc/tree-ssa-uninit.c
@@ -1011,8 +1011,7 @@ get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert)
   return tc;
 }
 
-/* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
-   all values in the range satisfies (x CMPC BOUNDARY) == true.  */
+/* Returns whether VAL CMPC BOUNDARY is true.  */
 
 static bool
 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
@@ -1488,11 +1487,17 @@ is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
   if (expr2.invert)
     code2 = invert_tree_comparison (code2, false);
 
+  if (code2 == NE_EXPR && code1 == NE_EXPR)
+    return false;
+
+  if (code2 == NE_EXPR)
+    return !is_value_included_in (expr2.pred_rhs, expr1.pred_rhs, code1);
+
   if ((code1 == EQ_EXPR || code1 == BIT_AND_EXPR) && code2 == BIT_AND_EXPR)
     return (wi::to_wide (expr1.pred_rhs)
 	    == (wi::to_wide (expr1.pred_rhs) & wi::to_wide (expr2.pred_rhs)));
 
-  if (code1 != code2 && code2 != NE_EXPR)
+  if (code1 != code2)
     return false;
 
   if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
-- 
2.20.1

Re: [PATCH] Fix a missed case in predicate analysis of the late uninit pass

[Richard Biener]

On Fri, Apr 5, 2019 at 2:26 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>
> Richard Biener <richard.guenther@gmail.com> writes:
>
> > On Thu, Apr 4, 2019 at 4:05 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
> >>
> >> Richard Biener <richard.guenther@gmail.com> writes:
> >>
> >> > On Mon, Apr 1, 2019 at 5:36 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
> >> >>
> >> >> Hi!
> >> >>
> >> >> This is a fairly trivial change fixing a false negative in
> >> >> -Wmaybe-uninitialized.  I am pretty sure this is simply an overlooked
> >> >> case (is_value_included_in() is not meant to deal with the case where
> >> >> both compare codes are NE_EXPRs, neither does it need to, since their
> >> >> handling is trivial).
> >> >>
> >> >> In a nutshell, what happens is values of v restricted by (v != 2) are
> >> >> incorrectly considered a subset of values of v restricted by (v != 1).
> >> >> As if "v != 2, therefore v != 1".
> >> >>
> >> >> This is by no means a gcc-9 regression; I'll ping the patch once stage4
> >> >> is over, if needed.
> >> >>
> >> >> This came up when I was experimenting with moving the uninit passes
> >> >> around.  On mainline, the late uninit pass runs very late, so reliably
> >> >> triggering the affected path is a bit tricky.  So I created a GIMPLE
> >> >> test (it reproduces the behavior precisely, but might be fragile
> >> >> w.r.t. future versions of the textual representation) and then with a
> >> >> hint from Alexander managed to produce a simple C test.  [By the way,
> >> >> the first take was to insert an asm with a lot of newlines to prevent
> >> >> the dom pass from rewriting the CFG due to high cost of duplicating
> >> >> instructions.  This didn't work out; I think the dom pass does not
> >> >> respect sizes of inline asms.  I plan to create a testcase and file a
> >> >> bug later.]
> >> >>
> >> >> I ran regression testing on x86_64-pc-linux-gnu and saw no new
> >> >> regressions modulo a handful of flaky UNRESOLVED tests under
> >> >> gcc.dg/tree-prof.  `BOOT_CFLAGS="-O -Wno-error=maybe-uninitialized
> >> >> -Wmaybe-uninitialized" bootstrap` also succeeded producing no new
> >> >> warnings.
> >> >>
> >> >> OK for stage1?
> >> >
> >> > Hum.  While definitely two NE_EXPR do not work correctly I'd like
> >> > to see a positive test since LT_EXPR doesn't work either?
> >>
> >> Right, thanks.  The case that was not covered well is actually when
> >> cond2 == NE_EXPR (arbitrary cond1).  I created 2 new tests: uninit-26.c
> >> demonstrates a false negative, and uninit-27-gimple.c a false positive
> >> with trunk.
> >>
> >> > Specifically the code falls through to test is_value_included_in which
> >> > seems to assume code1 == code2.
> >>
> >> The function is_value_included_in itself only cares about one condition
> >> code (I'll expound on this below).  I agree though that the second part
> >> of the comment seems to assume that.
> >>
> >> Please take a look at the updated patch.  The rationale is as follows.
> >>
> >> When we have 2 potentially comparable predicates in
> >> is_pred_expr_subset_of, there are basically two things we want to check.
> >>
> >> 1) Whether two ranges with identical condition codes are nested.  This
> >> is done straightforwardly with is_value_included_in.
> >>
> >> 2) Whether X CMPC VAL1 is nested in X != VAL2.  Which is easy: this
> >> happens iff the set (a.k.a "range") {X: X CMPC VAL1 is true} doesn't
> >> contain ("cover") VAL2, in other words iff VAL2 CMPC VAL1 is false.
> >>
> >> Only, the logic of 2) is faulty when X CMPC VAL1 is not a range bounded
> >> on one end (this happens when, and only when CMPC is NE_EXPR; the range
> >> is then unbounded on both ends and can only be nested in X != VAL2, if
> >> VAL1 == VAL2).
> >>
> >> 3) Whether X != VAL1 is nested in X CMPC VAL2, but that is always false
> >> unless CMPC is NE_EXPR, which is already considered.
> >
> > OK.  Your patch does
> >
> > +  if (code2 == NE_EXPR && code1 == NE_EXPR)
> > +    return false;
> >
> > but it should instead return operand_equal_p (expr1.pred_rhs,
> > expr2.pred_rhs, 0)?
>
> This doesn't change the semantics, because the case with equal rhs's is
> already considered at the beginning of this function:
>
> static bool
> is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
> {
>   enum tree_code code1, code2;
>
>   if (pred_equal_p (expr1, expr2))
>     return true;
>
> So I think, leaving this part of the patch as is results in less
> localized/explicit code, but better matches the overall style of this
> function.  Or perhaps add a checking assert?

Ah, I looked for but missed this check...

>   if (code1 == code2)
>     gcc_checking_assert (!operand_equal_p (expr1.pred_rhs,
>                                            expr2.pred_rhs, 0))

No, I don't think that's needed.

> >> > To me it looks like is_value_includeds comment should be clarified to
> >> > say
> >> >
> >> > /* Returns true if all values X satisfying X CMPC VAL satisfy
> >> >    X CMPC BOUNDARY.  */
> >>
> >> This is indeed more clear than the current comment, and the meaning is
> >> the same.  I suggest however to not discuss nestedness of ranges in this
> >> comment at all.
> >>
> >> > That is, "all values in the range" in the current comment is
> >> > under-specified since VAL is just a single value.
> >>
> >> The range is implied, since only one CMPC is passed.  (If CMPC is
> >> NE_EXPR, however, then I guess the range would only be known in the
> >> caller, but the function does not work correctly for this purpose --
> >> hence the patch to not call it then.)  But is_value_included_in actually
> >> only cares about one value and one set anyway, as the name suggests.
> >>
> >> So I think the second part of the comment is supposed to help to think
> >> about applying this function for its main use-case (this function is
> >> used twice, actually: in the case we are discussing there is a range
> >> whose nestedness the calling code is testing, in the other case there is
> >> just a constant), whereas the first part simply states what the function
> >> does.  I'd say, the second part of the comment should be rewritten or
> >> discarded, while the first should be kept.  OTOH, it might have been
> >> helpful to the person who wrote this code.
> >>
> >> > So I wonder what testcases regress if we remove the && code2 != NE_EXPR
> >> > case?  That way we see what the intention was.  A patch should then
> >> > change that to
> >> >
> >> >   if ((code1 != code2)
> >> >       || !(<condition on code1> && code2 == NE_EXPR))
> >> >    return false;
> >> >
> >> > to explicitely spell out what case was meant here.
> >>
> >> make check-gcc RUNTESTFLAGS='dg.exp=uninit*' gives one regression:
> >>
> >> gcc.dg/uninit-pred-9_b.c bogus warning (test for bogus messages, line 24)
> >>
> >> This test boils down to this:
> >>
> >>      if (m != 100)
> >>         v = sth;
> >>     ...
> >>      if (m < 99)
> >>         use (v);
> >>
> >> So with the code2 != NE_EXPR check in place, expr1 = {m, 98, LE_EXPR},
> >> expr2 = {m, 100, NE_EXPR}, and code2 = NE_EXPR are passed to
> >> is_value_included_in, which returns true: 98 is included in m != 100
> >> and true means "no warning".  This does not clarify the intention for
> >> me, since this only works by luck; the condition that needs to be tested
> >> cannot be tested with passing NE_EXPR to is_value_included_in, as the
> >> new uninit-26.c test shows.
> >
> > The new patch is OK with the change suggested above and the new
> > comment for is_value_included_in spelling out how BOUNDARY and CMPC
> > form the domain, all x so that x CMPC BOUNDARY is true vs. the also
> > possible all x so that BOUNDARY CMPC x is true.
>
> I updated this to say /* Returns whether VAL CMPC BOUNDARY is true.  */
> As actually there is no need to define any "domain" entity here.
>
> If this looks good, I'll ping the patch when stage1 opens, or ask
> someone to apply.

Thanks.
Richard.

> > Thanks for explaining and the extra testcases.
> > Richard.
>
> Thank you for reviewing.
> Vlad
>

Re: [PATCH] Fix a missed case in predicate analysis of the late uninit pass

[Jeff Law]

On 4/8/19 3:00 AM, Richard Biener wrote:
> On Fri, Apr 5, 2019 at 2:26 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>>
>> Richard Biener <richard.guenther@gmail.com> writes:
>>
>>> On Thu, Apr 4, 2019 at 4:05 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>>>>
>>>> Richard Biener <richard.guenther@gmail.com> writes:
>>>>
>>>>> On Mon, Apr 1, 2019 at 5:36 PM Vladislav Ivanishin <vlad@ispras.ru> wrote:
>>>>>>
>>>>>> Hi!
>>>>>>
>>>>>> This is a fairly trivial change fixing a false negative in
>>>>>> -Wmaybe-uninitialized.  I am pretty sure this is simply an overlooked
>>>>>> case (is_value_included_in() is not meant to deal with the case where
>>>>>> both compare codes are NE_EXPRs, neither does it need to, since their
>>>>>> handling is trivial).
>>>>>>
>>>>>> In a nutshell, what happens is values of v restricted by (v != 2) are
>>>>>> incorrectly considered a subset of values of v restricted by (v != 1).
>>>>>> As if "v != 2, therefore v != 1".
>>>>>>
>>>>>> This is by no means a gcc-9 regression; I'll ping the patch once stage4
>>>>>> is over, if needed.
>>>>>>
>>>>>> This came up when I was experimenting with moving the uninit passes
>>>>>> around.  On mainline, the late uninit pass runs very late, so reliably
>>>>>> triggering the affected path is a bit tricky.  So I created a GIMPLE
>>>>>> test (it reproduces the behavior precisely, but might be fragile
>>>>>> w.r.t. future versions of the textual representation) and then with a
>>>>>> hint from Alexander managed to produce a simple C test.  [By the way,
>>>>>> the first take was to insert an asm with a lot of newlines to prevent
>>>>>> the dom pass from rewriting the CFG due to high cost of duplicating
>>>>>> instructions.  This didn't work out; I think the dom pass does not
>>>>>> respect sizes of inline asms.  I plan to create a testcase and file a
>>>>>> bug later.]
>>>>>>
>>>>>> I ran regression testing on x86_64-pc-linux-gnu and saw no new
>>>>>> regressions modulo a handful of flaky UNRESOLVED tests under
>>>>>> gcc.dg/tree-prof.  `BOOT_CFLAGS="-O -Wno-error=maybe-uninitialized
>>>>>> -Wmaybe-uninitialized" bootstrap` also succeeded producing no new
>>>>>> warnings.
>>>>>>
>>>>>> OK for stage1?
>>>>>
>>>>> Hum.  While definitely two NE_EXPR do not work correctly I'd like
>>>>> to see a positive test since LT_EXPR doesn't work either?
>>>>
>>>> Right, thanks.  The case that was not covered well is actually when
>>>> cond2 == NE_EXPR (arbitrary cond1).  I created 2 new tests: uninit-26.c
>>>> demonstrates a false negative, and uninit-27-gimple.c a false positive
>>>> with trunk.
>>>>
>>>>> Specifically the code falls through to test is_value_included_in which
>>>>> seems to assume code1 == code2.
>>>>
>>>> The function is_value_included_in itself only cares about one condition
>>>> code (I'll expound on this below).  I agree though that the second part
>>>> of the comment seems to assume that.
>>>>
>>>> Please take a look at the updated patch.  The rationale is as follows.
>>>>
>>>> When we have 2 potentially comparable predicates in
>>>> is_pred_expr_subset_of, there are basically two things we want to check.
>>>>
>>>> 1) Whether two ranges with identical condition codes are nested.  This
>>>> is done straightforwardly with is_value_included_in.
>>>>
>>>> 2) Whether X CMPC VAL1 is nested in X != VAL2.  Which is easy: this
>>>> happens iff the set (a.k.a "range") {X: X CMPC VAL1 is true} doesn't
>>>> contain ("cover") VAL2, in other words iff VAL2 CMPC VAL1 is false.
>>>>
>>>> Only, the logic of 2) is faulty when X CMPC VAL1 is not a range bounded
>>>> on one end (this happens when, and only when CMPC is NE_EXPR; the range
>>>> is then unbounded on both ends and can only be nested in X != VAL2, if
>>>> VAL1 == VAL2).
>>>>
>>>> 3) Whether X != VAL1 is nested in X CMPC VAL2, but that is always false
>>>> unless CMPC is NE_EXPR, which is already considered.
>>>
>>> OK.  Your patch does
>>>
>>> +  if (code2 == NE_EXPR && code1 == NE_EXPR)
>>> +    return false;
>>>
>>> but it should instead return operand_equal_p (expr1.pred_rhs,
>>> expr2.pred_rhs, 0)?
>>
>> This doesn't change the semantics, because the case with equal rhs's is
>> already considered at the beginning of this function:
>>
>> static bool
>> is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
>> {
>>   enum tree_code code1, code2;
>>
>>   if (pred_equal_p (expr1, expr2))
>>     return true;
>>
>> So I think, leaving this part of the patch as is results in less
>> localized/explicit code, but better matches the overall style of this
>> function.  Or perhaps add a checking assert?
> 
> Ah, I looked for but missed this check...
> 
>>   if (code1 == code2)
>>     gcc_checking_assert (!operand_equal_p (expr1.pred_rhs,
>>                                            expr2.pred_rhs, 0))
> 
> No, I don't think that's needed.
> 
>>>>> To me it looks like is_value_includeds comment should be clarified to
>>>>> say
>>>>>
>>>>> /* Returns true if all values X satisfying X CMPC VAL satisfy
>>>>>    X CMPC BOUNDARY.  */
>>>>
>>>> This is indeed more clear than the current comment, and the meaning is
>>>> the same.  I suggest however to not discuss nestedness of ranges in this
>>>> comment at all.
>>>>
>>>>> That is, "all values in the range" in the current comment is
>>>>> under-specified since VAL is just a single value.
>>>>
>>>> The range is implied, since only one CMPC is passed.  (If CMPC is
>>>> NE_EXPR, however, then I guess the range would only be known in the
>>>> caller, but the function does not work correctly for this purpose --
>>>> hence the patch to not call it then.)  But is_value_included_in actually
>>>> only cares about one value and one set anyway, as the name suggests.
>>>>
>>>> So I think the second part of the comment is supposed to help to think
>>>> about applying this function for its main use-case (this function is
>>>> used twice, actually: in the case we are discussing there is a range
>>>> whose nestedness the calling code is testing, in the other case there is
>>>> just a constant), whereas the first part simply states what the function
>>>> does.  I'd say, the second part of the comment should be rewritten or
>>>> discarded, while the first should be kept.  OTOH, it might have been
>>>> helpful to the person who wrote this code.
>>>>
>>>>> So I wonder what testcases regress if we remove the && code2 != NE_EXPR
>>>>> case?  That way we see what the intention was.  A patch should then
>>>>> change that to
>>>>>
>>>>>   if ((code1 != code2)
>>>>>       || !(<condition on code1> && code2 == NE_EXPR))
>>>>>    return false;
>>>>>
>>>>> to explicitely spell out what case was meant here.
>>>>
>>>> make check-gcc RUNTESTFLAGS='dg.exp=uninit*' gives one regression:
>>>>
>>>> gcc.dg/uninit-pred-9_b.c bogus warning (test for bogus messages, line 24)
>>>>
>>>> This test boils down to this:
>>>>
>>>>      if (m != 100)
>>>>         v = sth;
>>>>     ...
>>>>      if (m < 99)
>>>>         use (v);
>>>>
>>>> So with the code2 != NE_EXPR check in place, expr1 = {m, 98, LE_EXPR},
>>>> expr2 = {m, 100, NE_EXPR}, and code2 = NE_EXPR are passed to
>>>> is_value_included_in, which returns true: 98 is included in m != 100
>>>> and true means "no warning".  This does not clarify the intention for
>>>> me, since this only works by luck; the condition that needs to be tested
>>>> cannot be tested with passing NE_EXPR to is_value_included_in, as the
>>>> new uninit-26.c test shows.
>>>
>>> The new patch is OK with the change suggested above and the new
>>> comment for is_value_included_in spelling out how BOUNDARY and CMPC
>>> form the domain, all x so that x CMPC BOUNDARY is true vs. the also
>>> possible all x so that BOUNDARY CMPC x is true.
>>
>> I updated this to say /* Returns whether VAL CMPC BOUNDARY is true.  */
>> As actually there is no need to define any "domain" entity here.
>>
>> If this looks good, I'll ping the patch when stage1 opens, or ask
>> someone to apply.
Given your two comments earlier, I think this is ready to go onto the
trunk.  I'll install it momentarily.

jeff
>