Created attachment 32888 [details]
reduced testcase

It also fails on trunk.

Hum, the testcase is a bit large. It should be possible to remove at least some struct members and enums which seem irrelevant. I removed quite a few lines but I'm sure with some patience the testcase could be reduced to 20 lines or so.

My guess is that what is uninitialized is "rw" and some optimization pass messed up the variable names when creating temporaries.

Created attachment 32889 [details]
even more reduced

This could be even further reduced

(In reply to Manuel López-Ibáñez from comment #1)
 
> My guess is that what is uninitialized is "rw" and some optimization pass
> messed up the variable names when creating temporaries.

I'm afraid it's more serious than that, because 'rw = XWINDOW (make_window ());' always initializes 'rw'.

Thanks for simplifying the test case.

(In reply to Paul Eggert from comment #3)
> (In reply to Manuel López-Ibáñez from comment #1)
>  
> > My guess is that what is uninitialized is "rw" and some optimization pass
> > messed up the variable names when creating temporaries.
> 
> I'm afraid it's more serious than that, because 'rw = XWINDOW (make_window
> ());' always initializes 'rw'.

Yes you're right. Simplifying further we get:


extern long int make_window (void);
struct vectorlike_header  {  long int size;  };

static  _Bool
PSEUDOVECTORP (long int a)
{
  if (! (((int) a & ~0) == 5))
    return 0;
  else
    {
      struct vectorlike_header *h = (void *) a - 5;
      return (h->size == 4611686018595160064);

    }
}
struct window
  {
    int line_height;
    int pixel_width;
    int pixel_height;
    int column_width;
    int text_cols;
    int internal_border_width;
    int left_fringe_width, right_fringe_width;
};


struct window *
make_frame (_Bool mini_p)
{
  struct window *rw, *mw;
  rw = (struct window *) make_window ();
  if (mini_p)
    {
      long int a = make_window ();
      if (!PSEUDOVECTORP (a)) return rw;
      mw  = (void*) a - 5;
    }
  rw->pixel_width = ((rw->text_cols * (rw->column_width))
                     + (rw->left_fringe_width + (rw->right_fringe_width)) + 2 * (rw->internal_border_width));
  rw->pixel_height = ((rw->text_cols * (rw->line_height)));
  if (mini_p)
    {
      mw->pixel_height = rw->pixel_height;
    }
  return rw;
}


For this, the uninit pass reports:
[WORKLIST]: add to initial list: mw_1 = PHI <mw_9(D)(9), mw_34(12)>
[CHECK]: examining phi: mw_1 = PHI <mw_9(D)(9), mw_34(12)>

[CHECK] Found def edge 1 in mw_1 = PHI <mw_9(D)(9), mw_34(12)>
[BEFORE SIMPLICATION -- [USE]:
mw_1->pixel_height = _28;
is guarded by :

mini_p_8(D) != 0


[BEFORE NORMALIZATION --[USE]:
mw_1->pixel_height = _28;
is guarded by :

mini_p_8(D) != 0


[AFTER NORMALIZATION -- [USE]:
mw_1->pixel_height = _28;
is guarded by :

mini_p_8(D) != 0


[BEFORE SIMPLICATION -- [DEF]:
mw_1 = PHI <mw_9(D)(9), mw_34(12)>
is guarded by :

mini_p_8(D) != 0 (.AND.)  (.NOT.) _31 != 5 (.AND.) _35 == 4611686018595160064


[BEFORE NORMALIZATION --[DEF]:
mw_1 = PHI <mw_9(D)(9), mw_34(12)>
is guarded by :

mini_p_8(D) != 0 (.AND.)  (.NOT.) _31 != 5 (.AND.) _35 == 4611686018595160064


[AFTER NORMALIZATION -- [DEF]:
mw_1 = PHI <mw_9(D)(9), mw_34(12)>
is guarded by :

_35 == 4611686018595160064 (.AND.)  (.NOT.) _31 != 5 (.AND.) mini_p_8(D) != 0


[CHECK]: Found unguarded use: mw_1->pixel_height = _28;

It seems the computation of the logical guards cannot figure out that if (_35 == 4611686018595160064 (.AND.)  (.NOT.) _31 != 5) is false then the function terminates and there cannot be uninitialized uses. From the GIMPLE output, it does not look as if it trivial to know this.

(In reply to Paul Eggert from comment #0)
> Also, mw was used in the
> previous line, with no warning.

I think uinit uses are computed walking the CFG backwards, and only one use is reported per variable.

On the reduced testcase this actually regressed already in November 2005 or so, so doesn't look anything close to a recent regression.

David, can you please have a look?

I think what is important that if the other conditions besides mini_p != 0 are not met, then control flow goes to basic blocks from which there is no path to the bb with the use (in this testcase just to the return bb or empty blocks that directly or indirectly fall thru into the return bb and the use is not in the return bb).

GCC 4.9.1 has been released.

GCC 4.9.2 has been released.

Of particular interest is this PHI node at the start of BB6:

  # mw_1 = PHI <mw_9(D)(2), h_33(5)>


I vaguely remember that we had code that would optimize this case, specifically we would ignore PHI alternatives associated with undefined uses.  If we did that, then we'd create an equivalence mw_1 = h33 which would then propagate to the use of mw_1 and replace it with h33 and avoid the false positive.  I thought that was in the vrp/ccp propagation engine.

Sigh.  We can't do the propagation, even if we recognize the mw_9 default definition represents an undefined value -- because doing so would result in a use that is not dominated by its def.

We could do duplication and essentially create

if (mini_p)
  {
    long int a = make_window ();
    if (!PSEUDOVECTORP (a)) return rw;
    mw  = (void*) a - 5;
    rw->pixel_width = ((rw->text_cols * (rw->column_width))
                     + (rw->left_fringe_width + (rw->right_fringe_width)) + 2 * (rw->internal_border_width));
    rw->pixel_height = ((rw->text_cols * (rw->line_height)));
    mw->pixel_height = rw->pixel_height;
  }
else
  {
    rw->pixel_width = ((rw->text_cols * (rw->column_width))
                     + (rw->left_fringe_width + (rw->right_fringe_width)) + 2 * (rw->internal_border_width));
    rw->pixel_height = ((rw->text_cols * (rw->line_height)));
  }


And in fact, that's precisely what the code to handle joiner blocks in the jump threader is supposed to do...   Hmmm, this might be mine...

*** Bug 64823 has been marked as a duplicate of this bug. ***

So we don't thread this case because of the limits we place on the number of statements in the duplicated block.

If --param max-jump-thread-duplication-stmts=16 is added to the command line, jump threading will kick in creating the pseudo-code I posted in c#11.  For reference, the default value of that param is 15.

What I don't understand from c#4 is uninit can't simplify this condition:

if (_35 == 4611686018595160064 (.AND.)  (.NOT.) _31 != 5) is false

While we may not know the full condition, does realizing that the (*.NOT.) _31 != 5 is totally pointless help?

And even simpler testcase:


void *init(void);

struct window
{
  int line_height;
  int pixel_width;
  int pixel_height;
  int column_width;
  int text_cols;
  int internal_border_width;
  int left_fringe_width, right_fringe_width;
} *rw;

void bar() __attribute__((noreturn));
void f(int i, int j) {
    void *ptr;
    if (i)
      {
        if (j)
          return; /* bar(); */
        ptr = init();
      }
    rw->pixel_width = ((rw->text_cols * (rw->column_width))
                       + (rw->left_fringe_width + (rw->right_fringe_width)) + 2 * (rw->internal_border_width));
  rw->pixel_height = ((rw->text_cols * (rw->line_height)));
  if (i)
    {
      rw=ptr;
    }
}


And the dump:

f (intD.6 iD.1843, intD.6 jD.1844)
{
  voidD.41 * ptrD.1847;
  struct window * rw.0_10;
  intD.6 _11;
  intD.6 _12;
  intD.6 _13;
  intD.6 _14;
  intD.6 _15;
  intD.6 _16;
  intD.6 _17;
  intD.6 _18;
  intD.6 _19;
  intD.6 _20;
  intD.6 _22;
  intD.6 _23;

;;   basic block 2, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 0, next block 9, flags: (NEW, REACHABLE)
;;    pred:       ENTRY [100.0%]  (FALLTHRU,EXECUTABLE)
;;   starting at line 17
  [test.c:17:8] if (i_4(D) != 0)
    goto <bb 3>;
  else
    goto <bb 9>;
;;    succ:       3 [50.0%]  (TRUE_VALUE,EXECUTABLE)
;;                9 [50.0%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 9, loop depth 0, count 0, freq 5000, maybe hot
;;    prev block 2, next block 3, flags: (NEW)
;;    pred:       2 [50.0%]  (FALSE_VALUE,EXECUTABLE)
;; 
  goto <bb 6>;
;;    succ:       6 [100.0%]  (FALLTHRU)

;;   basic block 3, loop depth 0, count 0, freq 5000, maybe hot
;;    prev block 9, next block 10, flags: (NEW, REACHABLE)
;;    pred:       2 [50.0%]  (TRUE_VALUE,EXECUTABLE)
;;   starting at line 19
  [test.c:19:5] if (j_7(D) != 0)
    goto <bb 10>;
  else
    goto <bb 5>;
;;    succ:       10 [61.0%]  (TRUE_VALUE,EXECUTABLE)
;;                5 [39.0%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 10, loop depth 0, count 0, freq 3051, maybe hot
;;    prev block 3, next block 4, flags: (NEW)
;;    pred:       3 [61.0%]  (TRUE_VALUE,EXECUTABLE)
;; 
;;    succ:       4 [100.0%]  (FALLTHRU)

;;   basic block 4, loop depth 0, count 0, freq 5761, maybe hot
;;    prev block 10, next block 5, flags: (NEW)
;;    pred:       10 [100.0%]  (FALLTHRU)
;;                11 [100.0%]  (FALLTHRU)
;; 
  # .MEM_47 = PHI <.MEM_6(D)(10), .MEM_24(11)>
  goto <bb 8>;
;;    succ:       8 [100.0%]  (FALLTHRU,EXECUTABLE)

;;   basic block 5, loop depth 0, count 0, freq 1949, maybe hot
;;    prev block 4, next block 6, flags: (NEW, REACHABLE)
;;    pred:       3 [39.0%]  (FALSE_VALUE,EXECUTABLE)
;;   starting at line 21
  [test.c:21:6] # .MEM_8 = VDEF <.MEM_6(D)>
  # PT = nonlocal escaped 
  # USE = nonlocal 
  # CLB = nonlocal 
  ptr_9 = initD.1831 ();
;;    succ:       6 [100.0%]  (FALLTHRU,EXECUTABLE)

;;   basic block 6, loop depth 0, count 0, freq 6949, maybe hot
;;    prev block 5, next block 11, flags: (NEW, REACHABLE)
;;    pred:       9 [100.0%]  (FALLTHRU)
;;                5 [100.0%]  (FALLTHRU,EXECUTABLE)
;;   starting at line 23
  # PT = nonlocal escaped 
  # ptr_1 = PHI <ptr_5(D)(9), [test.c:21:6] ptr_9(5)>
  # .MEM_2 = PHI <.MEM_6(D)(9), .MEM_8(5)>
  [test.c:23:27] # VUSE <.MEM_2>
  # PT = nonlocal escaped 
  rw.0_10 = rwD.1841;
  [test.c:23:27] # VUSE <.MEM_2>
  _11 = [test.c:23:27] rw.0_10->text_colsD.1837;
  [test.c:23:44] # VUSE <.MEM_2>
  _12 = [test.c:23:44] rw.0_10->column_widthD.1836;
  [test.c:23:39] _13 = _11 * _12;
  [test.c:24:15] # VUSE <.MEM_2>
  _14 = [test.c:24:15] rw.0_10->left_fringe_widthD.1839;
  [test.c:24:40] # VUSE <.MEM_2>
  _15 = [test.c:24:40] rw.0_10->right_fringe_widthD.1840;
  [test.c:24:35] _16 = _14 + _15;
  [test.c:24:10] _17 = _13 + _16;
  [test.c:24:72] # VUSE <.MEM_2>
  _18 = [test.c:24:72] rw.0_10->internal_border_widthD.1838;
  [test.c:24:67] # RANGE [-2147483648, 2147483647] NONZERO 4294967294
  _19 = _18 * 2;
  [test.c:24:63] _20 = _17 + _19;
  [test.c:23:21] # .MEM_21 = VDEF <.MEM_2>
  [test.c:23:7] rw.0_10->pixel_widthD.1834 = _20;
  [test.c:25:43] # VUSE <.MEM_21>
  _22 = [test.c:25:43] rw.0_10->line_heightD.1833;
  [test.c:25:38] _23 = _11 * _22;
  [test.c:25:20] # .MEM_24 = VDEF <.MEM_21>
  [test.c:25:5] rw.0_10->pixel_heightD.1835 = _23;
  [test.c:26:6] if (i_4(D) != 0)
    goto <bb 7>;
  else
    goto <bb 11>;
;;    succ:       7 [61.0%]  (TRUE_VALUE,EXECUTABLE)
;;                11 [39.0%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 11, loop depth 0, count 0, freq 2710, maybe hot
;;    prev block 6, next block 7, flags: (NEW)
;;    pred:       6 [39.0%]  (FALSE_VALUE,EXECUTABLE)
;; 
  goto <bb 4>;
;;    succ:       4 [100.0%]  (FALLTHRU)

;;   basic block 7, loop depth 0, count 0, freq 4239, maybe hot
;;    prev block 11, next block 8, flags: (NEW, REACHABLE)
;;    pred:       6 [61.0%]  (TRUE_VALUE,EXECUTABLE)
;;   starting at line 28
  [test.c:28:9] # .MEM_25 = VDEF <.MEM_24>
  rwD.1841 = ptr_1;
;;    succ:       8 [100.0%]  (FALLTHRU,EXECUTABLE)

;;   basic block 8, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 7, next block 1, flags: (NEW, REACHABLE)
;;    pred:       4 [100.0%]  (FALLTHRU,EXECUTABLE)
;;                7 [100.0%]  (FALLTHRU,EXECUTABLE)
;;   starting at line -1, discriminator 1
  # .MEM_3 = PHI <.MEM_47(4), .MEM_25(7)>
  # VUSE <.MEM_3>
  return;
;;    succ:       EXIT [100.0%] 

}

I don't really understand how the uninit pass computes the predicates, but when replacing the "return" with "bar()", it is able to see that "j != 0" is not part of the predicate guarding the def of ptr. Thus, somehow the analysis that works for a noreturn function fails for a normal return.

GCC 4.9.3 has been released.

AFAICT tree-ssa-uninit won't look at the predicate associated with an undefined PHI argument and test it against the predicate for the actual use.

ie, given this PHI from the testcase:

;;   basic block 6, loop depth 0
;;    pred:       9
;;                5
  # ptr_1 = PHI <ptr_5(D)(9), ptr_9(5)>

We want to look at the control dependent path that leads to the edge (9,5).  For this test, that edge is control dependent on bb2:

;;   basic block 2, loop depth 0
;;    pred:       ENTRY
  if (i_4(D) != 0)
    goto <bb 3>;
  else
    goto <bb 9>;


ie, we know that for ptr_1 to take the value ptr_5 that i_4 != 0 must be false.  So the guard for the edge (9,5) is NOT i_4 != 0.

And in this testcase, the actual use of ptr_1 is guarded by:

  if (i_4(D) != 0)
    goto <bb 7>;
  else
    goto <bb 11>;


When i_4 != 0 is true, then we'll get to the use. So the guard for the use is i_4 != 0

Those two guards can never both be true.  So there's no way at runtime for the value ptr_5 to flow into ptr_1 and then into the use of ptr_1 in bb7.

And AFAICT, tree-ssa-uninit.c doesn't have the code to do that kind of analysis.

GCC 4.9 branch is being closed

(In reply to Jeffrey A. Law from comment #16)
> AFAICT tree-ssa-uninit won't look at the predicate associated with an
> undefined PHI argument and test it against the predicate for the actual use.
> 
> ie, given this PHI from the testcase:
> 
> ;;   basic block 6, loop depth 0
> ;;    pred:       9
> ;;                5
>   # ptr_1 = PHI <ptr_5(D)(9), ptr_9(5)>
> 
> We want to look at the control dependent path that leads to the edge (9,5). 
> For this test, that edge is control dependent on bb2:

Jeff, do you mean edge(9,6) throughout?  Because I don't see any flow of control from 9->5.

Also, unless I'm missing something, in Jeff's analysis, I see no reference to j, which plays a pivotal role.

In the testcase in comment 14, we can see that the guard for ptr_14 is actually [i && j==0]:

    if (i)
      {
        if (j)
          return; /* bar(); */
        ptr = init();
      }

...because on j != 0, we exit, which is what the .uninit dump is suggesting with:

[AFTER NORMALIZATION -- [DEF]:
ptr_14 = PHI <ptr_18(D)(9), ptr_22(5)>
is guarded by :

 (.NOT.) j_20(D) != 0 (.AND.) i_17(D) != 0

Meanwhile, the use we are warning on is [i != 0]:

[AFTER NORMALIZATION -- [USE]:
rw = ptr_14;
is guarded by :

i_17(D) != 0

So the problem is that while the guard for the DEF is [i != 0 && j == 0], the guard for the USE is only [i != 0].  Uninit should somehow be aware that if PTR was set, then  j==0, because otherwise we would've exited the function.

You can see that .uninit is expecting the use to be guarded by [i != 0 && j == 0], by adding "&& !j" to the guard and silencing the warning:

   if (i && !j)
    {
      rw=ptr;
    }

If anyone is interested, here is an even smaller testcase:

int *rw;
int line_height;
int pixel_width;
int text_cols;
int width1, width2, width3;

void *pointer;

void f (int i, int j)
{
  void *ptr;
  if (i)
    {
      if (j)
	return;
      ptr = pointer;
    }
  pixel_width = 1234 + width1 + 2 * width2 + 2 * width3;
  *rw = text_cols + line_height;
  if (i)
    rw=ptr;
}

Created attachment 39487 [details]
even more^2 reduced testcase

Smaller testcase without any structure nonsense and even less variables.

Created attachment 39499 [details]
untested patch v1

I think I see what Jeff is getting at.

Here is an untested patch exploring the idea of ignoring unguarded uses if we can prove that the guards for such uses are invalidated by the uninitialized operand paths being executed.

Preliminary tests show that it fixes the testcase in the PR without introducing any regressions in the rest of the uninit tests:

     make check-gcc RUNTESTFLAGS=dg.exp=uninit*

As the "NOTE:" in the code states, we could be much smarter when invalidating predicates, but for now let's do straight negation which works for the simple case.

Does this seem like a reasonable approach?

Sorry, I can't remember if I meant 9->5 or 9->6 at this point :-)  I need to refamiliarize myself with this stuff again to make sure I've got the basic concepts before reviewing the patch.

But you can probably see now why I said there was some seriously powerful, but dense code in here that I'd like to be able to re-use elsewhere to prune other false positive may-be warnings.

OK.  It's coming back to me now.  And yes, Aldy, it was the edge 9->6 :-)

So we have a PHI argument that references an uninitialized variable.  There is a control predicate for that PHI argument, call it p.

The use of the result of the PHI is also guarded.  In this particular case the guard is !p.

Thus there is no path through the CFG which uses the uninitialized variable.  We ought to be able to look at the guard of the PHI argument as well as the guard for the use, at least that's the theory.  Now onward to look at your patch...

Author: aldyh
Date: Sun Nov 20 18:34:06 2016
New Revision: 242639

URL: https://gcc.gnu.org/viewcvs?rev=242639&root=gcc&view=rev
Log:
	PR middle-end/61409
	* tree-ssa-uninit.c: Define new global max_phi_args.
	(compute_uninit_opnds_pos): Use max_phi_args.
	(prune_uninit_phi_opnds): Same.
	(use_pred_not_overlap_with_undef_path_pred): Remove reference to
	missing NUM_PREDS in function comment.
	(can_one_predicate_be_invalidated_p): New.
	(can_chain_union_be_invalidated_p): New.
	(flatten_out_predicate_chains): New.
	(uninit_ops_invalidate_phi_use): New.
	(is_use_properly_guarded): Call uninit_ops_invalidate_phi_use.

Added:
    trunk/gcc/testsuite/gcc.dg/uninit-pr61409.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-uninit.c

Fixed in mainline.  Removing tag for GCC7.