Bug 49498 - [5/6/7 Regression]: gcc.dg/uninit-pred-8_b.c bogus warning (predicate analysis bugs)
Summary: [5/6/7 Regression]: gcc.dg/uninit-pred-8_b.c bogus warning (predicate analysi...
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.7.0
: P4 enhancement
Target Milestone: 5.5
Assignee: Not yet assigned to anyone
URL:
Keywords: diagnostic
: 55424 (view as bug list)
Depends on:
Blocks:
 
Reported: 2011-06-22 00:02 UTC by Hans-Peter Nilsson
Modified: 2017-03-31 15:26 UTC (History)
9 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2011-06-22 17:27:37


Attachments
k.c (185 bytes, text/x-csrc)
2011-07-05 16:05 UTC, Jeffrey A. Law
Details
k.c.127t.uninit (877 bytes, text/plain)
2011-07-05 16:05 UTC, Jeffrey A. Law
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Hans-Peter Nilsson 2011-06-22 00:02:50 UTC
With revision 175107 this test passed.
From revision 175123 and on, this test has failed as follows:

Running /tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/dg.exp ...
...
FAIL: gcc.dg/uninit-pred-8_b.c bogus warning (test for bogus messages, line 20)

With the message in the gcc.log being:

Executing on host: /tmp/hpautotest-gcc1/cris-elf/gccobj/gcc/xgcc -B/tmp/hpautotest-gcc1/cris-elf/gccobj/gcc/ /tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c   -Wuninitialized -O2 -S   -isystem /tmp/hpautotest-gcc1/cris-elf/gccobj/cris-elf/./newlib/targ-include -isystem /tmp/hpautotest-gcc1/gcc/newlib/libc/include  -o uninit-pred-8_b.s    (timeout = 300)
/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c: In function 'foo':

/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c:20:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]

/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c: In function 'foo_2':

/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c:42:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]

output is:
/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c: In function 'foo':

/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c:20:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]

/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c: In function 'foo_2':

/tmp/hpautotest-gcc1/gcc/gcc/testsuite/gcc.dg/uninit-pred-8_b.c:42:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]


FAIL: gcc.dg/uninit-pred-8_b.c bogus warning (test for bogus messages, line 20)
PASS: gcc.dg/uninit-pred-8_b.c bogus warning (test for bogus messages, line 23)
PASS: gcc.dg/uninit-pred-8_b.c bogus warning (test for bogus messages, line 39)
PASS: gcc.dg/uninit-pred-8_b.c warning (test for warnings, line 42)
PASS: gcc.dg/uninit-pred-8_b.c (test for excess errors)

Authors of patches in suspect revision range CC:ed.

I see this for multiple targets on reports to gcc-testresults@ (mmix, mips, avr, m32c), but oddly not for some of the main targets (x86_64, i686, arm).

I'm guessing that this isn't jamborm's commit r175111 but will triage and update.
Comment 1 Hans-Peter Nilsson 2011-06-22 03:08:41 UTC
(In reply to comment #0)
>  I'm guessing that this isn't jamborm's commit r175111 but will triage and
> update.

The test passed at r175113, hence removed from CC.
Comment 2 Jeffrey A. Law 2011-06-22 17:27:37 UTC
It looks like the uninit code is being confused by elimination of a test in one path. 

int foo (int n, int l, int m, int r)
{
  int v;

  if (n < 10 || m > 100 || r < 20 || l)
    v = r;

  if (m) g++;
  else   bar();

  if ( n < 10 ||  m > 100 || r < 20 )
      blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */

  return 0;
}


We end up copying the n < 10 test from the 3rd conditional into the m == 0 path of the second conditional and threading the false path from the copied conditional to the r < 20 test (ie, we bypass the m > 100 test as it always false on that path where m == 0.

This appears to confuse the predicate analysis in tree-ssa-uninit.c.  I'm still trying to wrap my head around its implementation to see if there's a reasonable way to solve this.
Comment 3 Jeffrey A. Law 2011-06-30 19:42:47 UTC
Frankly, I'm just not able to wrap my head around the tree-ssa-uninit implementation.  I understand the general concepts, but just can't seem to find where in that code we handle certain things.  Perhaps it simply doesn't handle them.

In this simpler sample code we have:

/* { dg-do compile } */
/* { dg-options "-Wuninitialized -O2" } */

int g;
void bar();
void blah(int);

int foo (int n, int l, int m, int r)
{
  int v;

  if (n < 10 || m > 100)
    v = r;

  if (m) g++;

  if ( n < 10 ||  m > 100)
      blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */

  return 0;
}

Compiling with -O2 -Wuninitialized on cris-elf.

Someone who knows the code in tree-ssa-uninit.c really needs to chime in... Reading that code just makes my head hurt.

From the standpoint of the resulting CFG, the path 2->8->4->5->6 can never be traversed, nor can 2->3->9->4->6.  2->3->9->4->5 is properly guarded as far as I can tell, though I'm not convinced tree-ssa-uninit.c is computing the guards correctly.
Comment 4 davidxl 2011-06-30 20:37:36 UTC
Created attachment 24692 [details]
k.c

I can to reproduce the problem on x86-64 linux. Can you help provide the following dump:

 -fdump-tree-uninit-blocks-details?

Thanks,

David



(In reply to comment #3)
> Frankly, I'm just not able to wrap my head around the tree-ssa-uninit
> implementation.  I understand the general concepts, but just can't seem to find
> where in that code we handle certain things.  Perhaps it simply doesn't handle
> them.
> 
> In this simpler sample code we have:
> 
> /* { dg-do compile } */
> /* { dg-options "-Wuninitialized -O2" } */
> 
> int g;
> void bar();
> void blah(int);
> 
> int foo (int n, int l, int m, int r)
> {
>   int v;
> 
>   if (n < 10 || m > 100)
>     v = r;
> 
>   if (m) g++;
> 
>   if ( n < 10 ||  m > 100)
>       blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
> 
>   return 0;
> }
> 
> Compiling with -O2 -Wuninitialized on cris-elf.
> 
> Someone who knows the code in tree-ssa-uninit.c really needs to chime in...
> Reading that code just makes my head hurt.
> 
> From the standpoint of the resulting CFG, the path 2->8->4->5->6 can never be
> traversed, nor can 2->3->9->4->6.  2->3->9->4->5 is properly guarded as far as
> I can tell, though I'm not convinced tree-ssa-uninit.c is computing the guards
> correctly.
Comment 5 Jeffrey A. Law 2011-07-05 16:05:21 UTC
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 06/30/11 14:37, xinliangli at gmail dot com wrote:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49498
> 
> --- Comment #4 from davidxl <xinliangli at gmail dot com> 2011-06-30 20:37:36 UTC ---
> I can to reproduce the problem on x86-64 linux. Can you help provide the
> following dump:
You need to configure for cris-elf.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOEzYmAAoJEBRtltQi2kC74P4H/RrrlfNZtk/e0W26Nr1U4K2G
xZM5Y513BPakr2DyRe4OOtpMquIbRxdOe0aJw0iuUfkDXTEKNaT1h/cePYAJGjYe
Wh8GJhHj7D+WC9OiobOoBiYUmCcF7vIclW0OdcNwPrIfQ328E6zFAr8wJeWvvbGb
gBvB0cu5jMYb7Ls+x7ox7PjdTfqHbrIFZCkMVpKBPe2OYuVtKcyoBErJD7QH1cWs
VeL+bk498CRSQNSHL3j9pr/sTKFp18+I+rrBh/+aKi0FnMfoRYgCpN3/AldQw8Ds
qtzTOCPdR7X5v1Wc19bxlPJvFmes5MQSjEvzMooDmA09JeiW963DA4n08w9NeLg=
=HmIU
-----END PGP SIGNATURE-----
Comment 6 Jeffrey A. Law 2011-07-05 16:05:22 UTC
Created attachment 24693 [details]
k.c.127t.uninit
Comment 7 davidxl 2011-07-05 22:51:49 UTC
(In reply to comment #6)
> Created attachment 24693 [details]
> k.c.127t.uninit


1) is the complicated control flow generated by if-merging + jump-threading?
2) On the targets that have the problem, is branch cost considered cheap?
3) Looks like there are more jump-threading opportunities that can clean up the control flow, namely,

(in the attached file):

BLOCK 4 should be split into 4_1 and 4_2. 4_1's predecessor is BLOCK 8, and it can be merged with with  BLOCK 10. The merged block (10 and 4_1) has single successor BLOCK 6. BLOCK 4_2 (predecessor is 9) is successors can be greatly simplified with a single successor BLOCK 7.

Why is that not happening?

With the complicated control flow, the uninit analysis is definitely confused -- requires powerful symbolic evaluation to simplify the predicates: the predicates guarding the use in BLOCK 6:

(n<=9 AND  m==0) OR (n <= 9 AND m != 0 AND (n <=9 OR m > 100)) OR (n > 9 AND m > 100) OR (n > 9 AND m <= 100 AND (n<=9 OR m > 100))

of course there might be other bugs in the analysis that prevent the above from formulated, but nonetheless, it is unlikely to be handled).

Solution
1) fix the test case by disabling jumpthreading and if-merging
2) or maybe move the uninit analysis earlier in the pipeline.

David
Comment 8 Jeffrey A. Law 2011-07-07 16:22:48 UTC
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 07/05/11 16:52, xinliangli at gmail dot com wrote:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49498
> 
> --- Comment #7 from davidxl <xinliangli at gmail dot com> 2011-07-05 22:51:49 UTC ---
> (In reply to comment #6)
>> Created attachment 24693 [details]
>> k.c.127t.uninit
> 
> 
> 1) is the complicated control flow generated by if-merging + jump-threading?
I think jump-threading is the primarly culprit.  At one time I tried to
track how things changed through the passes, but ultimately decided the
end result either had to be analyzable or not by the uninit code.

> 2) On the targets that have the problem, is branch cost considered cheap?
No idea.  I didn't bother to look at why cris-elf triggers the problem,
but x86 doesn't.  Presumably it's a branch-cost or similar issue.

> 3) Looks like there are more jump-threading opportunities that can clean up the
> control flow, namely,
Yes.  Jump threading is inherently an iterative process.  It was decided
some time ago to remove the iterative step as it doesn't buy a whole lot
in terms of code quality and it's a fairly significant compile-time cost.

During my investigations noticed the same thing and manually reran DOM
from within GDB and verified it further simplified the CFG, but
rerunning DOM isn't really going to be an option.


> 
> With the complicated control flow, the uninit analysis is definitely confused
> -- requires powerful symbolic evaluation to simplify the predicates: the
> predicates guarding the use in BLOCK 6:
> 
> (n<=9 AND  m==0) OR (n <= 9 AND m != 0 AND (n <=9 OR m > 100)) OR (n > 9 AND m
>> 100) OR (n > 9 AND m <= 100 AND (n<=9 OR m > 100))
> 
> of course there might be other bugs in the analysis that prevent the above from
> formulated, but nonetheless, it is unlikely to be handled).
OK.  That's kindof what I needed to know -- we're unlikely to handle
this particular case.

> 
> Solution
> 1) fix the test case by disabling jumpthreading and if-merging
Or xfailing it for the affected targets.

> 2) or maybe move the uninit analysis earlier in the pipeline.
As you know, that runs the risk of introducing other false positives.

I can live with #1 or the target-specific xfailing approach.

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOFd1BAAoJEBRtltQi2kC7wpsIAJ1FStgYozE/6o8o5mZrj+5V
hWP7WmspSVFQMLTGDZw7hNeCEnE2rIl/8Tmin6/GDWM50oNGati2HqTRqTSZwU0y
YvMY8NlH1/YY4hJ94YPEpNrALAIwD8w3qdhiPVlS7eTWgOl8iTmXLJmJqk6OnT+Z
BeYPxpYDkQgYvicyjT4VVcWpwcmCbE/D9bKTNt68ABAH8RTmkba/VaK1wtGpt3qt
hy0qXCi59OUPh7TbcKvgrDLL3GDmy68C9afHUiEKyfDu3JxV9awl4y4Bfr1lOURF
bvTOuhKQo0MOlbtgJo24nGYK2TU/1Nv1DkcdhgvsCCBciO8LPoocnSZ176ohE5E=
=/ti9
-----END PGP SIGNATURE-----
Comment 9 davidxl 2011-07-07 19:31:53 UTC
On Thu, Jul 7, 2011 at 9:23 AM, law at redhat dot com <
gcc-bugzilla@gcc.gnu.org> wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49498
>
> --- Comment #8 from Jeffrey A. Law <law at redhat dot com> 2011-07-07
> 16:22:48 UTC ---
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 07/05/11 16:52, xinliangli at gmail dot com wrote:
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49498
> >
> > --- Comment #7 from davidxl <xinliangli at gmail dot com> 2011-07-05
> 22:51:49 UTC ---
> > (In reply to comment #6)
> >> Created attachment 24693 [details]
> >> k.c.127t.uninit
> >
> >
> > 1) is the complicated control flow generated by if-merging +
> jump-threading?
> I think jump-threading is the primarly culprit.  At one time I tried to
> track how things changed through the passes, but ultimately decided the
> end result either had to be analyzable or not by the uninit code.
>
> > 2) On the targets that have the problem, is branch cost considered cheap?
> No idea.  I didn't bother to look at why cris-elf triggers the problem,
> but x86 doesn't.  Presumably it's a branch-cost or similar issue.
>
> > 3) Looks like there are more jump-threading opportunities that can clean
> up the
> > control flow, namely,
> Yes.  Jump threading is inherently an iterative process.  It was decided
> some time ago to remove the iterative step as it doesn't buy a whole lot
> in terms of code quality and it's a fairly significant compile-time cost.
>

Does it need to be iterative? Any simple example to show dependency of
jump-threading analysis on actual transformation of some other
jump-threading instance (e.g, opportunity only gets exposed after
transformation)?


>
> During my investigations noticed the same thing and manually reran DOM
> from within GDB and verified it further simplified the CFG, but
> rerunning DOM isn't really going to be an option.
>

Is incremental DOM update a choice?

David


>
>
> >
> > With the complicated control flow, the uninit analysis is definitely
> confused
> > -- requires powerful symbolic evaluation to simplify the predicates: the
> > predicates guarding the use in BLOCK 6:
> >
> > (n<=9 AND  m==0) OR (n <= 9 AND m != 0 AND (n <=9 OR m > 100)) OR (n > 9
> AND m
> >> 100) OR (n > 9 AND m <= 100 AND (n<=9 OR m > 100))
> >
> > of course there might be other bugs in the analysis that prevent the
> above from
> > formulated, but nonetheless, it is unlikely to be handled).
> OK.  That's kindof what I needed to know -- we're unlikely to handle
> this particular case.
>
> >
> > Solution
> > 1) fix the test case by disabling jumpthreading and if-merging
> Or xfailing it for the affected targets.
>
> > 2) or maybe move the uninit analysis earlier in the pipeline.
> As you know, that runs the risk of introducing other false positives.
>
> I can live with #1 or the target-specific xfailing approach.
>
> jeff
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJOFd1BAAoJEBRtltQi2kC7wpsIAJ1FStgYozE/6o8o5mZrj+5V
> hWP7WmspSVFQMLTGDZw7hNeCEnE2rIl/8Tmin6/GDWM50oNGati2HqTRqTSZwU0y
> YvMY8NlH1/YY4hJ94YPEpNrALAIwD8w3qdhiPVlS7eTWgOl8iTmXLJmJqk6OnT+Z
> BeYPxpYDkQgYvicyjT4VVcWpwcmCbE/D9bKTNt68ABAH8RTmkba/VaK1wtGpt3qt
> hy0qXCi59OUPh7TbcKvgrDLL3GDmy68C9afHUiEKyfDu3JxV9awl4y4Bfr1lOURF
> bvTOuhKQo0MOlbtgJo24nGYK2TU/1Nv1DkcdhgvsCCBciO8LPoocnSZ176ohE5E=
> =/ti9
> -----END PGP SIGNATURE-----
>
> --
> Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug.
>
Comment 10 Jeffrey A. Law 2011-07-07 21:26:57 UTC
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 07/07/11 13:32, xinliangli at gmail dot com wrote:

> Yes.  Jump threading is inherently an iterative process.  It was decided
> some time ago to remove the iterative step as it doesn't buy a whole lot
> in terms of code quality and it's a fairly significant compile-time cost.
> 
> 
>> Does it need to be iterative? Any simple example to show dependency of
>> jump-threading analysis on actual transformation of some other
>> jump-threading instance (e.g, opportunity only gets exposed after
>> transformation)?
> 
> 
> 
> During my investigations noticed the same thing and manually reran DOM
> from within GDB and verified it further simplified the CFG, but
> rerunning DOM isn't really going to be an option.
> 
> 
>> Is incremental DOM update a choice?
I looked at it a few years ago.  I never came up with anything even
remotely close to working, even at a conceptual level.  While the PHI
nodes represent places where interesting things happen, I wasn't able to
make any leap that would allow me to use some kind of worklist algorithm
to pick up the secondary optimization opportunities.

During the course of those investigations I came across Bodik's work,
and only recently did the light come on with how Bodik's work might
translate well into how we handle jump threading.  I've been drawn off
that work temporarily, but expect to return to it shortly.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOFiSHAAoJEBRtltQi2kC7PhQH/A7NwXEghs+FUlszsb7rnB9p
lZkz1hrMSaVTPgMS2ewOwp6nedpK3pshOFVJHFcLxw1SjOjNePVYccH9XRXSwqSL
wiuiLYTv+SfObC7icvTkQuJ0N8eJ6apxo5hBvb3d599DifwAaZHaq/3RoUslcH2O
sNSfoQbJGiDSfw3HxAK36IgxRvx3Khe/1GoEMV1W40kiD9tB6wgH5YyAq1Iq6ZHR
Ckgqjy/fR8IZtTruSNNCA76erYXOSUc2etQoassYLGvvwsG/htqA1c3D86TQFIfP
0K55jDWMpdOmuxEp0JrUEE0g6jVuOXHY2DPIWAt/YDY2YJwTflYSEjd8wYYqYPM=
=/taX
-----END PGP SIGNATURE-----
Comment 11 Hans-Peter Nilsson 2011-07-07 21:51:54 UTC
(In reply to comment #8)
> > 2) On the targets that have the problem, is branch cost considered cheap?
> No idea.  I didn't bother to look at why cris-elf triggers the problem,
> but x86 doesn't.  Presumably it's a branch-cost or similar issue.

I forgot so I had to look myself...
At one time the default cost was measured as the best and that stuck; grep and behold the comment.  So, "only" ports using the default are affected.

> > Solution
> > 1) fix the test case by disabling jumpthreading and if-merging
> Or xfailing it for the affected targets.

FWIW, I don't mind.  Whatever solution you feel proud of. ;)
Comment 12 Jeffrey A. Law 2011-07-11 15:29:05 UTC
Testsuite adjusted.  Not closing as this does represent a regression and further improvements to jump threading and/or predicate aware uninit analysis may resolve this in the future.  However, I'm downgrading it to a P4 enhancement request.
Comment 13 Kai Tietz 2011-10-15 17:10:11 UTC
This bug seems to be caused by vrp's jump-threading and branching into different if-branch

For example this case gets expanded by vrp to:

int g;
void bar();
void blah(int);

int foo (int n, int l, int m, int r)
{
  int v;

  int v;

  if ((n != 0) & (l != 0))
    v = r;

  if (m) g++;
  else   bar();

  if ( n && l)
      blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */

  if (l ) if ( n)
      blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */

  return 0;
}

foo (int n, int l, int m, int r)
{
  int v;
  int g.3;
  int g.2;
  _Bool D.2766;
  _Bool D.2765;
  _Bool D.2764;

<bb 2>:
  D.2764_3 = n_2(D) != 0;
  D.2765_5 = l_4(D) != 0;
  D.2766_6 = D.2764_3 & D.2765_5;
  if (D.2766_6 != 0)
    goto <bb 4>;
  else
    goto <bb 3>;

<bb 3>:

<bb 4>:
  # v_1 = PHI <v_7(D)(3), r_8(D)(2)>
  if (m_10(D) != 0)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  g.2_11 = g;
  g.3_12 = g.2_11 + 1;
  g = g.3_12;
  goto <bb 7>;

<bb 6>:
  bar ();

<bb 7>:
  if (D.2766_6 != 0)
    goto <bb 8>;
  else
    goto <bb 9>;

<bb 8>:
  blah (v_1);
  goto <bb 13>;
<bb 9>:
  if (l_4(D) != 0)
    goto <bb 10>;
  else
    goto <bb 12>;

<bb 10>:
  if (n_2(D) != 0)
    goto <bb 11>;
  else
    goto <bb 12>;

<bb 11>:
  blah (v_1);

<bb 12>:
  return 0;

<bb 13>:
  goto <bb 10>;

}

Of interest is the insert goto at <bb 8> to <bb 10> via <bb 13>.
<bb 10> itself is the inner branch of the 'if (l ) if ( n)'.  So 'if ( n)' has two users, and so it gets warned, as it isn't clear to later check, that <bb 10>'s condition is for <bb 13> also true. IMHO vrp needs to learn that <bb 11> should be the target of <bb 13> instead.

That -mbranch-costs shows for such cases some effect, is caused by combining/not-combining if-conditions.

To solve this, we shouldn't make differences in AST about branching-costs high or low.  The tree-ssa-ifcombine pass should run before (and maybe after as now) first vrp pass, and should try to merge if-s together as well.  In one of the last gimple-passes then we should actually apply to conditions the branching rule and break-up conditions to their if-chains.
Comment 14 Richard Biener 2012-03-22 08:26:34 UTC
GCC 4.7.0 is being released, adjusting target milestone.
Comment 15 Richard Biener 2012-06-14 08:24:19 UTC
GCC 4.7.1 is being released, adjusting target milestone.
Comment 16 Jakub Jelinek 2012-09-20 10:17:10 UTC
GCC 4.7.2 has been released.
Comment 17 bin.cheng 2012-11-20 07:08:18 UTC
Hi,
I spent some time analyzing this bug and I think I understand the problem now.
For below dump file from trunk/cris-elf when compiling the attached k.c:
;; Function foo (foo, funcdef_no=0, decl_uid=1323, cgraph_uid=0)

;; 1 loops found
;;
;; Loop 0
;;  header 0, latch 1
;;  depth 0, outer -1
;;  nodes: 0 1 2 3 4 5 6 7 8 9 10 11
;; 2 succs { 10 3 }
;; 3 succs { 11 4 }
;; 4 succs { 11 }
;; 5 succs { 6 7 }
;; 6 succs { 9 }
;; 7 succs { 6 8 }
;; 8 succs { 9 }
;; 9 succs { 1 }
;; 10 succs { 5 6 }
;; 11 succs { 5 8 }
foo (int n, int l, int m, int r)
{
  int v;
  int g.1;
  int g.0;

  <bb 2>:
  if (n_4(D) <= 9)
    goto <bb 10>;
  else
    goto <bb 3>;

  <bb 3>:
  if (m_5(D) > 100)
    goto <bb 11>;
  else
    goto <bb 4>;

  <bb 4>:
  goto <bb 11>;

  <bb 5>:
  # v_14 = PHI <v_13(11), r_7(D)(10)>
  g.0_9 = g;
  g.1_10 = g.0_9 + 1;
  g = g.1_10;
  if (n_4(D) <= 9)
    goto <bb 6>;
  else
    goto <bb 7>;

  <bb 6>:
  # v_17 = PHI <v_14(5), v_14(7), r_7(D)(10)>
  blah (v_17);
  goto <bb 9>;

  <bb 7>:
  if (m_5(D) > 100)
    goto <bb 6>;
  else
    goto <bb 8>;

  <bb 8>:

  <bb 9>:
  return 0;

  <bb 10>:
  if (m_5(D) != 0)
    goto <bb 5>;
  else
    goto <bb 6>;

  <bb 11>:
  # v_13 = PHI <r_7(D)(3), v_6(D)(4)>
  if (m_5(D) != 0)
    goto <bb 5>;
  else
    goto <bb 8>;

}

There are two flaws in tree-ssa-uninit.c revealing this bug.
1. GCC try to find def_chains from cd_root(which is the closest dominating bb  for phi_bb) to phi_bb, but only find use_predicates from phi_bb to use_bb. In general case with canonical CFG, this is fine, but in non-canonical CFG, it's possible to have ancestor basic block of phi_bb in def_chains which have branch that never reach to phi_bb, like basic block 10 reported in this PR. In this scenario the corresponding condition should not be counted in def_chains(edge<10, 5> in this case).
There are two methods to fix this:
   a) find use predicates from dom(phi_bb), rather than phi_bb in non-canonical CFGs.
   b) prune branch conditions that are irrelevant to this use/def in def_chains.
Method a is simpler, but the problem is it results in more dep_chains which might exceeds the limit MAX_NUM_CHAINS. As for method b), I haven't got any clue to implement it.

2. When calling is_use_properly_guarded in find_uninit_use, GCC finds predicates from source basic block if the use_stmt is a phi node. This results in missing condition at the end of each def_chain. Different from the first issue, this can be easily fixed.
Comment 18 Andrew Pinski 2012-11-21 13:07:00 UTC
*** Bug 55424 has been marked as a duplicate of this bug. ***
Comment 19 bin.cheng 2012-11-21 13:24:02 UTC
(In reply to comment #18)
> *** Bug 55424 has been marked as a duplicate of this bug. ***

Just for the record.
If the analysis I gave in Comment #17 is right, this PR reveals another bug in tree-ssa-uninit.c, apart from the limitation of MAX_NUM_CHAINS, while PR55424 is only about MAX_NUM_CHAINS.
Comment 20 Richard Biener 2013-04-11 07:59:15 UTC
GCC 4.7.3 is being released, adjusting target milestone.
Comment 21 Richard Biener 2014-06-12 13:45:53 UTC
The 4.7 branch is being closed, moving target milestone to 4.8.4.
Comment 22 Jakub Jelinek 2014-12-19 13:29:05 UTC
GCC 4.8.4 has been released.
Comment 23 Richard Biener 2015-06-23 08:18:20 UTC
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.
Comment 24 Jakub Jelinek 2015-06-26 19:54:25 UTC
GCC 4.9.3 has been released.
Comment 25 Richard Biener 2016-08-03 10:50:40 UTC
GCC 4.9 branch is being closed
Comment 26 Jeffrey A. Law 2017-03-30 19:49:10 UTC
So I had hoped this old BZ would be fixed by the changes for 71437.  Sadly, that is not the case.

*But* the WIP for for 78496 does happen to fix this BZ.  In fact, we only need the hunks from 78496 which are inexpensive.  So I may carve those out and push them forward as a fix for this BZ as well as an improvement for 78496.
Comment 27 Jeffrey A. Law 2017-03-31 06:05:52 UTC
Must. Read. dg-comments in testcase. More. Carefully.


This was actually fixed a couple years ago with some pass ordering changes.  The testsuite hack mentioned in c#12 is no longer needed.
Comment 28 Richard Biener 2017-03-31 07:40:45 UTC
(In reply to Jeffrey A. Law from comment #27)
> Must. Read. dg-comments in testcase. More. Carefully.
> 
> 
> This was actually fixed a couple years ago with some pass ordering changes. 
> The testsuite hack mentioned in c#12 is no longer needed.

Hmm, note the report states it worked on x86_64/i586/arm anyway and only
some other archs were broken.

Did you verify any of those?  Iff it's really fixed we should remove the
testcase workaround (enable DOM again).

A quick check on avr doesn't reproduce the issue when re-enabling DOM.
Comment 29 Jeffrey A. Law 2017-03-31 14:58:55 UTC
Yes, I checked cris-elf.  I've got the patch to reenable DOM for that test in my local tree.
Comment 30 Jeffrey A. Law 2017-03-31 15:26:50 UTC
Author: law
Date: Fri Mar 31 15:26:18 2017
New Revision: 246618

URL: https://gcc.gnu.org/viewcvs?rev=246618&root=gcc&view=rev
Log:
	PR tree-optimization/49498
	* gcc.dg/uninit-pred-8_b.c: Reenable DOM.

Modified:
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/uninit-pred-8_b.c