[Bug rtl-optimization/66790] New: Invalid uninitialized register handling in REE

[Bug rtl-optimization/66790] New: Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

            Bug ID: 66790
           Summary: Invalid uninitialized register handling in REE
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: derodat at adacore dot com
  Target Milestone: ---

The reproducer I'm about to attach[1] seems to trigger a code generation issue
at least on x86_64-linux:

    $ gnatmake -q p -O3 -gnatn
    $ ./p

    raised PROGRAM_ERROR : p.adb:9 explicit raise

The bottom line is that when Success is False in Q.Get (q.adb, around line 40)
its value is clobbered during return. If we build with -fno-ree, we can see in
the assembly code (near the return point for q__get) the following sequence:

    movzwl    (%rax), %epb
    ...
somelabel:
    ...
    movzwl    %bp, %ebp
    ...
    salq    $16, %rax
    orq    %rbp, %rax

However, without the -fno-ree switch the instruction:

    movzwl    %bp, %ebp

is merged with its definition (the first movzwl instruction) by the REE pass.
This is wrong since the definition does _not_ dominate this zero-extension: the
first movzwl instruction can be by-passed through "somelabel".

I started to investigate this issue: the REE pass is currently not aware of
this by-pass code path because it is reached by no proper definition (it brings
an uninitialized %rbp register to the zero-extension). This happens in
ree.c:get_defs; in our case (insn=second movzwl, reg=BP) DF_REF_CHAIN contains
only one definition: the movzwl instruction.

Given the "somelabel" code path, I would rather expect DF_REF_CHAIN to hold a
NULL reference to materialize the lack of initialization in one path. I found
the DF_LR_IN/DF_LR_OUT macros from df.h: they provide information about
uninitialized variables but the associated comment says they should not be used
("This intolerance should eventually be fixed."). Besides, they provide a
basic-block-level information whereas we are rather interested in
instruction-level information in REE.

I was thinking that REE may not be the only optimization pass needing this kind
of information but I found no other one, so I'm not sure how this ought to be
handled. Can anybody confirm my intuition about the NULL reference in
DF_REF_CHAIN? I'm willing to implement it but I prefer first to be sure this is
the right approach.

Thanks in advance!


[1] It's in Ada. I tried to translate it into C but any change in register
allocation makes the issue disappear...

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #2 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 35924
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35924&action=edit
Part of the reproducer

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #1 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 35923
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35923&action=edit
Part of the reproducer

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #3 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 35925
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35925&action=edit
Part of the reproducer

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2015-07-29
     Ever confirmed|0                           |1

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
So what is the issue with replacing zero-extending an uninitialized %ebp
with a random other value?  Both are essentially undefined when reached via
the somlabel bypass.

Is the real issue happening in a downstream pass?  I don't think REE does
anything wrong here.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #6 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Thanks for your answer, Richard!

(In reply to Richard Biener from comment #5)
> So what is the issue with replacing zero-extending an uninitialized %ebp
> with a random other value?  Both are essentially undefined when reached via
> the somlabel bypass.

Well, at least on x86, even when %ebp is uninitialized, “movzwl %bp, %ebp”
makes its upper half zero (and yes, the lower half is uninitialized). Hence a
following “shr $0x10, %ebp” is supposed to leave zero in %epb, for instance. If
we have a random value instead as shr’s input, this does not work anymore, so I
consider this transformation is an error.

> Is the real issue happening in a downstream pass?  I don't think REE does
> anything wrong here.

REE is the pass where I observed the change in behavior I described in my first
message, and I did not notice anything weird beyond this. If the above is wrong
(i.e. if we cannot assume (zext UNDEF from i16 to i32) >> 16 == 0), then I
guess I’ll have to look for something wrong up in the pipe. ;-)
>From gcc-bugs-return-493740-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Jul 30 10:16:30 2015
Return-Path: <gcc-bugs-return-493740-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 34638 invoked by alias); 30 Jul 2015 10:16:29 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 34606 invoked by uid 48); 30 Jul 2015 10:16:26 -0000
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
Date: Thu, 30 Jul 2015 10:16:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 6.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status
Message-ID: <bug-66790-4-BT37gQPLO1@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-66790-4@http.gcc.gnu.org/bugzilla/>
References: <bug-66790-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-07/txt/msg02630.txt.bz2
Content-length: 1760

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Pierre-Marie de Rodat from comment #6)
> Thanks for your answer, Richard!
> 
> (In reply to Richard Biener from comment #5)
> > So what is the issue with replacing zero-extending an uninitialized %ebp
> > with a random other value?  Both are essentially undefined when reached via
> > the somlabel bypass.
> 
> Well, at least on x86, even when %ebp is uninitialized, “movzwl %bp, %ebp”
> makes its upper half zero (and yes, the lower half is uninitialized). Hence
> a following “shr $0x10, %ebp” is supposed to leave zero in %epb, for
> instance. If we have a random value instead as shr’s input, this does not
> work anymore, so I consider this transformation is an error.
> 
> > Is the real issue happening in a downstream pass?  I don't think REE does
> > anything wrong here.
> 
> REE is the pass where I observed the change in behavior I described in my
> first message, and I did not notice anything weird beyond this. If the above
> is wrong (i.e. if we cannot assume (zext UNDEF from i16 to i32) >> 16 == 0),
> then I guess I’ll have to look for something wrong up in the pipe. ;-)

It would be certainly good to see why we have this UNDEF in the first place.

But yes, I have to agree that zext UNDEF >> 16 should be zero.  Unlike
sext UNDEF which is always undefined as the sign-bit is undefined.
>From gcc-bugs-return-493741-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Jul 30 10:46:07 2015
Return-Path: <gcc-bugs-return-493741-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 63997 invoked by alias); 30 Jul 2015 10:46:07 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 63970 invoked by uid 48); 30 Jul 2015 10:46:03 -0000
From: "anders.granlund.0 at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/67065] New: Missing diagnostics for ill-formed program with main variable instead of function
Date: Thu, 30 Jul 2015 10:46:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: anders.granlund.0 at gmail dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-67065-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-07/txt/msg02631.txt.bz2
Content-length: 1122

https://gcc.gnu.org/bugzilla/show_bug.cgi?idg065

            Bug ID: 67065
           Summary: Missing diagnostics for ill-formed program with main
                    variable instead of function
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: anders.granlund.0 at gmail dot com
  Target Milestone: ---

The following program is ill-formed (proc.cc):

  int main;

Compile it with the following command line:

  clang++ prog.cc -std=c++14 -pedantic-errors

No error messages are given. Since the program is ill-formed I expected to get
at least one error message.

The program is ill-formed by following sentence in [basic.start.main]p3
(http://eel.is/c++draft/basic.start.main#3):

"A program that declares a variable main at global scope or that declares the
name main with C language linkage (in any namespace) is ill-formed."

I have tired this with gcc HEAD 6.0.0 20150729 here:

http://melpon.org/wandbox/permlink/uxZxjSFQqBPYXB8b

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #8 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
(In reply to Richard Biener from comment #7)
> It would be certainly good to see why we have this UNDEF in the first place.

Sure: here is a C translation of what happens in my Ada reproducer (only wrt.
UNDEF: this is not a reproducer for the original bug).

    #include <stdint.h>

    struct option_t {
      uint16_t is_present;
      uint16_t value;
    };

    struct option_t
    foo (uint16_t a, uint16_t b)
    {
      struct option_t result;

      result.is_present = b != 0;
      if (result.is_present)
        result.value = a / b;
      return result;
    }

On x86, foo's return value is the 32-bit value in $eax. If b == 0, its lower
half is undefined while its upper one is supposed to be 0. In other words, even
though the value field is uninitialized, the is_present one must be 0. Although
a trunk GCC produces no zero-extension at -O2 for this example, this simply
exposes the source use case for the "half-initialized" value business.

> But yes, I have to agree that zext UNDEF >> 16 should be zero.  Unlike
> sext UNDEF which is always undefined as the sign-bit is undefined.

Good point! The patch I submitted previously pessimized the sign-extension
case. The one I'm going to upload fixes this: bootstrapped and regtested
successfuly on x86_64-linux.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #9 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 36098
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36098&action=edit
Updated candidate patch

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu.org

--- Comment #10 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Just to mention that we have really thought hard about this bug at AdaCore and
the current patch seems (unfortunately) to be the only plausible way out, if we
don't want to pessimize the common case.  But suggestions are of course
welcome.

We have also discussed papering over it in the Ada front-end by initializing
the Out parameter to zero.  The problem is that you can write an equivalent Ada
testcase with an explicitly uninitialized variable and trigger the bug
(Pierre-Marie, could you attach it to the PR?  Concatenate the files though and
mention that it needs to be gnatchop'ed) so we cannot paper over it in all
cases.

But the fundamental thing to keep in mind here is that this is a valid Ada
program and that it could be translated into a valid C program: there is indeed
an uninitialized variable but the run-time behavior of the program doesn't
depend on its value.  The bug in REE effectively propagates the
uninitializedness of this variable to another, perfectly initialized variable,
because the latter initialization is done with a zero-extension that is
eliminated.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #11 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 36320
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36320&action=edit
Reproducer with an uninitialized variable (no OUT parameter)

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #12 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Thanks.  I misremembered, the testcase has a single variable with two fields,
one uninitialized and one initialized, instead of two variables, but it's
exactly the same reasoning (and it would be trivial to add the two variables
anyway).

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #13 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
(In reply to Eric Botcazou from comment #12)
> Thanks.  I misremembered, the testcase has a single variable with two
> fields, one uninitialized and one initialized, instead of two variables, but
> it's exactly the same reasoning (and it would be trivial to add the two
> variables anyway).

Thank you for your involvement into this! :-)

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bernds at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

Bernd Schmidt <bernds at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bernds at gcc dot gnu.org

--- Comment #14 from Bernd Schmidt <bernds at gcc dot gnu.org> ---
I've looked at this for a while now. I agree that this is a bug in REE that
needs to be fixed in a manner similar to this patch. However, there are some
oddities here.

As you say, the df-live problem claims to compute a must-initialized problem,
so it would be very odd to add another problem with the same name. I
experimented with changing df_live_confluence_n to use and instead of ior,
followed by actually taking the confluence_n from your mir problem. However,
this does not work: ior enlarges the set while and shrinks it, so the
initialization of the bitmaps would have to be different. It looks like your
"visited" bit tries to avoid that, but I don't think this works. One testcase I
looked at had this structure:

entry -> 2 -> 3 -> 3

i.e. a loop in  block 3. The confluence_n function takes the out bitmap from
block 3 (which is all zeros) and ands it with the in bitmap from the same
block, which has the incoming regs from block 2 at that point, but obviously
the bitmap turns into all zeros at this point (block 3 was already visited due
to the 2->3 edge). I don't see how your patch doesn't suffer from the same
problem.

I think ideally we would figure out whether df_live really does have a mistake
in it, and if so fix it rather than adding another problem.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #15 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> I've looked at this for a while now. I agree that this is a bug in REE that
> needs to be fixed in a manner similar to this patch.

Thanks for looking into it.

> I think ideally we would figure out whether df_live really does have a
> mistake in it, and if so fix it rather than adding another problem.

Its description is very confusing, to say the least.  Quoting df-problems.c:

   LIVE AND MUST-INITIALIZED REGISTERS.

   This problem first computes the IN and OUT bitvectors for the
   must-initialized registers problems, which is a forward problem.
   It gives the set of registers for which we MUST have an available
   definition on any path from the entry block to the entry/exit of
   a basic block.

I think that's incorrect, the correct description would be "it gives the set of
registers for which we MUST have an available definition on at least one path
from the entry block".  That's why it doesn't work for the problem at hand,
which requires the "available definition on any path" thing.

But I'm not sure we can change it because, for example, init-regs uses it to
detect must-uninitialized registers:

/* Check all of the uses of pseudo variables.  If any use that is MUST
   uninitialized, add a store of 0 immediately before it.

              /* A use is MUST uninitialized if it reaches the top of
                 the block from the inside of the block (the lr test)
                 and no def for it reaches the top of the block from
                 outside of the block (the ur test).  */
              if (bitmap_bit_p (lr, regno)
                  && (!bitmap_bit_p (ur, regno)))

that is to say, uses that don't have any available definition.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bernds at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #16 from Bernd Schmidt <bernds at gcc dot gnu.org> ---
So I think there's three things to solve
 - which problem should df_live be using, the one it says it's using or the one
it actually does
 - if it's the former, see if passes using the information need fixing
 - if it's the latter and we need the new problem from this patch, ensure that
it actually works correctly (initializing the out bitmaps to all ones,
probably).

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gnu dot org,
                   |                            |zadeck at naturalbridge dot com

--- Comment #17 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> So I think there's three things to solve
>  - which problem should df_live be using, the one it says it's using or the
> one it actually does
>  - if it's the former, see if passes using the information need fixing
>  - if it's the latter and we need the new problem from this patch, ensure
> that it actually works correctly (initializing the out bitmaps to all ones,
> probably).

That sounds like a good plan.  On second thoughts, for the first point, maybe a
native speaker understands "an available definition on any path" as "an
available definition on one path, whatever it is", in which case the
description would be correct, albeit very confusing for non-native speakers. 
It would be good to have some insight from the DF maintainers here (CCed).

In any case, what's needed to fix the bug is "an available definition on every
path" and that's what Pierre-Marie's patch implements.  We're going to review
it in light of your remarks.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bernds at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #18 from Bernd Schmidt <bernds at gcc dot gnu.org> ---
FWIW I did some googling to refresh my memory, and this may be helpful:

www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec02-Dataflow.pdf

It looks like you want exactly the available expressions problem from page 26.
Maybe that's better terminology than must-initialized? (I'm not sure, but I'd
never heard the latter term before.)

I think I'm coming to the conclusion that df_live really does want what it
currently uses, which is the guarantee that there is _any_ def that reaches a
use. The commentary could use updating though, I think it clearly isn't
computing a "must" problem.

When updating the patch please ensure that all new parameters are documented
before the function.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bonzini at gnu dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #19 from Paolo Bonzini <bonzini at gnu dot org> ---
LIVE provides live registers that MAY be initialized (are initialized on at
least one path).  The comments are all wrong!

There's no code in GCC for must-initialized.  Pierre's patch gets it right
(except that I'm not sure about the comment at line 2033).  The MIR name can
indeed add to the confusion about may/must.  Perhaps valid registers (VR)?

Note that this is not the available expressions problem.  The confluence
function is the same, but it operates on registers and not on expressions.  The
gen and kill sets are different, too.

I wouldn't be surprised if you don't find it in the literature, since it's a
relatively obvious extension of the usual dataflow problems.

I think this issue can also be fixed easily with an approximated solution,
which is already used for example by combine's
set_nonzero_bits_and_sign_copies.  If a register is undefined at the start of
the function, you punt because the register has uninitialized uses.  This is
suboptimal if you have cases like:

     int y, x;
     x = y;     /* uninitialized */
     ...
     y = 5;
     ...
     x = y;     /* initialized */

but they should be pretty rare.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[zadeck at naturalbridge dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #20 from Kenneth Zadeck <zadeck at naturalbridge dot com> ---
>> On second thoughts, for the first point, maybe a native speaker understands 
>> "an available definition on any path" as "an available definition on one path,
>> whatever it is", in which case the description would be correct, albeit very 
>> confusing for non-native speakers.  It would be good to have some insight from
>> the DF maintainers here (CCed).

A native English speaker would say that this could be written better.   I would
suggest the term "on at least one path" and this is what a MAY problem is
generally defined as.

I do have to say that I am still uncomfortable with changing RRE to use a MUST
problem rather than a MAY problem.   I see this as dumbing down the compiler to
provide the semantics of uninitialized variables and it is a path that we have
generally avoided in GCC. I do not have a better solution, but there is a
feeling that something is being missed here.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #21 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> LIVE provides live registers that MAY be initialized (are initialized on at
> least one path).  The comments are all wrong!
> 
> There's no code in GCC for must-initialized.  Pierre's patch gets it right
> (except that I'm not sure about the comment at line 2033).  The MIR name can
> indeed add to the confusion about may/must.  Perhaps valid registers (VR)?

Thanks for the comment.  Yes, I agree that the MIR name ought to be improved.

> I think this issue can also be fixed easily with an approximated solution,
> which is already used for example by combine's
> set_nonzero_bits_and_sign_copies.  If a register is undefined at the start
> of the function, you punt because the register has uninitialized uses.  This
> is suboptimal if you have cases like:
> 
>      int y, x;
>      x = y;     /* uninitialized */
>      ...
>      y = 5;
>      ...
>      x = y;     /* initialized */
> 
> but they should be pretty rare.

Right, we pondered about it.  The difference is that combine operates on pseudo
while REE operates on hard registers, so the suboptimality could be large.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[zadeck at naturalbridge dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #23 from Kenneth Zadeck <zadeck at naturalbridge dot com> ---
This change to the doc looks fine to me.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #25 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Author: ebotcazou
Date: Thu Sep 17 15:35:43 2015
New Revision: 227875

URL: https://gcc.gnu.org/viewcvs?rev=227875&root=gcc&view=rev
Log:
        PR rtl-optimization/66790
        * df-problems.c (LIVE): Amend documentation.

Modified:
    branches/gcc-5-branch/gcc/ChangeLog
    branches/gcc-5-branch/gcc/df-problems.c

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #24 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Author: ebotcazou
Date: Thu Sep 17 15:35:24 2015
New Revision: 227874

URL: https://gcc.gnu.org/viewcvs?rev=227874&root=gcc&view=rev
Log:
        PR rtl-optimization/66790
        * df-problems.c (LIVE): Amend documentation.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/df-problems.c

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #26 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Author: ebotcazou
Date: Thu Sep 17 15:35:58 2015
New Revision: 227876

URL: https://gcc.gnu.org/viewcvs?rev=227876&root=gcc&view=rev
Log:
        PR rtl-optimization/66790
        * df-problems.c (LIVE): Amend documentation.

Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/df-problems.c

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #27 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Firstly, thanks everyone for your help! I'll try to address points that
still are unresolved.



(In reply to Bernd Schmidt from comment #14)
> As you say, the df-live problem claims to compute a must-initialized
> problem, so it would be very odd to add another problem with the same name.
(In reply to Eric Botcazou from comment #21)
> (In reply to Paolo Bonzini from comment #19)
>> There's no code in GCC for must-initialized.  Pierre's patch gets it right
>> (except that I'm not sure about the comment at line 2033).  The MIR name can
>> indeed add to the confusion about may/must.  Perhaps valid registers (VR)?
> 
> Thanks for the comment.  Yes, I agree that the MIR name ought to be improved.
To me, "valid" register has the same meaning as "initialized" and thus
does not carry the information about whether we can assume it is either
always or sometimes valid/initialized. So what about "always initialized
registers"? The acronym would be AIR.



(In reply to Bernd Schmidt from comment #14)
> I experimented with changing df_live_confluence_n to use and instead of ior,
> followed by actually taking the confluence_n from your mir problem. However,
> this does not work: ior enlarges the set while and shrinks it, so the
> initialization of the bitmaps would have to be different.
Yes: they both compute different information as discussed later in this
thread.



(In reply to Bernd Schmidt from comment #14)
> It looks like your "visited" bit tries to avoid that, but I don't
> think this works.
(In reply to Paolo Bonzini from comment #19)
> There's no code in GCC for must-initialized.  Pierre's patch gets it right
> (except that I'm not sure about the comment at line 2033).
The "visited" bit I introduced is used to fake an "all bits set"
initialization. The confluence_n method is meant to do:

    IN(dest) = OUT(src_0) AND OUT(src_1) AND ...

... by small increments of:

    IN(dest) := IN(dest) AND OUT(src_i)

When it is executed for the first time, IN(dest) is all-zeros, so we do
a copy because "a AND all_ones = a". Then we can do regular AND later
on. In order to get rid of this "visited" bit, I guess we could instead
pretend that IN/OUT sets are set of never-or-may-initialized registers,
but this complicates other parts of the code, so...

Paolo, does this clarify the comment at line 2033? (I will update it if
you think this is enough :-))



(In reply to Bernd Schmidt from comment #14)
> One testcase I looked at had this structure:
> 
> entry -> 2 -> 3 -> 3
> 
> i.e. a loop in  block 3. The confluence_n function takes the out bitmap from
> block 3 (which is all zeros) and ands it with the in bitmap from the same
> block, which has the incoming regs from block 2 at that point, but obviously
> the bitmap turns into all zeros at this point (block 3 was already visited
> due to the 2->3 edge). I don't see how your patch doesn't suffer from the
> same problem.
I don't understand what the problem is: the confluence_n function is
used during forward propagation. So in your example:

 a. the confluence_n function will be called for the 3 -> edge only
    after...

 b. the transfer function is invoked for the basic block 3 (then OUT(3)
    is initialized and potentially not all-zeros); this will be invoked
    only after...

 c. the confluence_n function is invoked for the 2 -> 3 edge
    (then IN(3) is initialized and potentially not all-zeros).

If I understand correctly, the BB_LAST_CHANGE_AGE mechanism in df-core.h
makes sure computations comply with this dependency (c. before b., b.
before a.).  So at the point the confluence_n function for the 3 -> 3
edges is called for the first time, both IN(3) and OUT(3) can be not
all-zeros.



(In reply to Bernd Schmidt from comment #14)
> I do have to say that I am still uncomfortable with changing RRE to
> use a MUST problem rather than a MAY problem.   I see this as dumbing
> down the compiler to provide the semantics of uninitialized variables
> and it is a path that we have generally avoided in GCC. I do not have
> a better solution, but there is a feeling that something is being
> missed here.
Indeed, while trying to fix the bug, I noticed that no RTL pass needs
this "is initialized on all paths" information.

I'm not sure what "having no semantics for uninitialized variables"
really implies: does this mean that we have an undefined behavior as
soon as code uses the value of an uninitialized variable? If not, I
think what makes REE special regarding this is that zero-extension is
used to pack independent values into single storage units (registers).
Because of this, considering that the whole storage unit is
uninitialized because a single embedded value is uninitialized makes us
generate wrong code.



Now on a different topic, I forgot to mention with my first candidate
patch: LIVE and MIR are supposed to work on the same GEN/KILL sets.
These respectively represent the set of registers that are
initialized/clobbered in the basic block. As you might have noticed,
LIVE and MIR don't have the same bb_local_compute function, though.

While getting familiar with DF problems, I noticed that LIVE's ignores
the order of GENs and KILLs in basic blocks. In other words, the
transfer function for: GEN(r1); KILL(r1) is currently the same as for
KILL(r1); GEN(r1) whereas clearly the former leaves r1 unitialized
whereas the latter leaves it initialized.

In order to get this right for MIR, I stated that MIR's GEN set excludes
the registers left killed at the end of the basic block (and by the way,
the bb_local_compute should process artificial defs with DF_REF_AT_TOP
before anything else). It seems that RD's and MD's
local_compute_process_def do this properly by clearing GEN's bit when
setting the corresponding KILL's and reciprocally (and they handle
artificial defs properly too!).

I think we should do the same for LIVE but lacks confidence because I
have not heard of any bug due to this so far... What do you think?

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bernds at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #28 from Bernd Schmidt <bernds at gcc dot gnu.org> ---
(In reply to Pierre-Marie de Rodat from comment #27)
> (In reply to Bernd Schmidt from comment #14)
> > It looks like your "visited" bit tries to avoid that, but I don't
> > think this works.
> (In reply to Paolo Bonzini from comment #19)
> > There's no code in GCC for must-initialized.  Pierre's patch gets it right
> > (except that I'm not sure about the comment at line 2033).
> The "visited" bit I introduced is used to fake an "all bits set"
> initialization. The confluence_n method is meant to do:
> 
>     IN(dest) = OUT(src_0) AND OUT(src_1) AND ...
> 
> ... by small increments of:
> 
>     IN(dest) := IN(dest) AND OUT(src_i)
> 
> When it is executed for the first time, IN(dest) is all-zeros, so we do
> a copy because "a AND all_ones = a". Then we can do regular AND later
> on. In order to get rid of this "visited" bit, I guess we could instead
> pretend that IN/OUT sets are set of never-or-may-initialized registers,
> but this complicates other parts of the code, so...

I know this is what it's trying to do, but when I experimented with it that
wasn't working, due to the problem I described.

> If I understand correctly, the BB_LAST_CHANGE_AGE mechanism in df-core.h
> makes sure computations comply with this dependency (c. before b., b.
> before a.).  So at the point the confluence_n function for the 3 -> 3
> edges is called for the first time, both IN(3) and OUT(3) can be not
> all-zeros.

It is sufficient for OUT(3) to be all-zeros. And I don't think the
LAST_CHANGE_AGE mechanism does anything to prevent it. Please try it out. I
think you have to initialize your bitmaps correctly rather than rely on
"visited".

I applied your patch and compiled the following with a breakpoint on
df_mir_confluence_n:
int foo (int n)
{
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += i;
  return sum;
}

and when it reaches the loop:

Breakpoint 5, df_mir_confluence_n (e=<edge 0x7ffff07352d8 (4 -> 4)>) at
../../trunk/gcc/df-problems.c:2040
(gdb) p debug_bitmap (op1)

first = 0x24bf418 current = 0x24bf418 indx = 0
        0x24bf418 next = (nil) prev = (nil) indx = 0
                bits = { 0 1 2 4 5 7 17 21 22 23 24 25
                         26 27 28 37 38 }
$2 = void
(gdb) p debug_bitmap (op2)

first = (nil) current = (nil) indx = 0

and

(gdb) p bb_info->visited 
$5 = true

because the edge 3->4 was seen first.

> (In reply to Bernd Schmidt from comment #14)
> > I do have to say that I am still uncomfortable with changing RRE to

I did not write this.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bonzini at gnu dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #29 from Paolo Bonzini <bonzini at gnu dot org> ---
> While getting familiar with DF problems, I noticed that LIVE's ignores
> the order of GENs and KILLs in basic blocks. In other words, the
> transfer function for: GEN(r1); KILL(r1) is currently the same as for
> KILL(r1); GEN(r1) whereas clearly the former leaves r1 unitialized
> whereas the latter leaves it initialized.

GEN and KILL are not the same for LR and MIR.

1) Sets and clobbers are handled differently.  A set or clobber of r1 _kills_
liveness, while for MIR sets _generate_ "initialized-ness" and only clobbers
kill it.

2) A use of r1 _creates_ liveness (which extends up, until it reaches the sets
for all reaching definitions of that use), while uses of r1 are irrelevant for
MIR.

3) For LR, GEN must override KILL if an insn has both a set and a use of r1. 
For MIR, you cannot have a GEN (set) and a KILL (clobber) in the same insn.

BTW, are you sure that

+      if (DF_REF_FLAGS_IS_SET (def,
+                              DF_REF_PARTIAL | DF_REF_CONDITIONAL))
+       /* All partial or conditional def
+          seen are included in the gen set. */
+       bitmap_set_bit (gen, regno);

?  I would have thought they don't belong in any set, and on the contrary I
would have thought that may-clobber definitions count as kills.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #30 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> GEN and KILL are not the same for LR and MIR.
> 
> 1) Sets and clobbers are handled differently.  A set or clobber of r1
> _kills_ liveness, while for MIR sets _generate_ "initialized-ness" and only
> clobbers kill it.
> 
> 2) A use of r1 _creates_ liveness (which extends up, until it reaches the
> sets for all reaching definitions of that use), while uses of r1 are
> irrelevant for MIR.
> 
> 3) For LR, GEN must override KILL if an insn has both a set and a use of r1.
> For MIR, you cannot have a GEN (set) and a KILL (clobber) in the same insn.

The issue is not LR vs MIR, it's the may-initialized part of LIVE vs MIR.

It seem to me that the GEN and KILL of the may-initialized part of LIVE should
be the same as those of MIR, since the difference between the 2 problems is
only at the global level.  Pierre-Marie's patch duplicates them, but ideally
they should be factored and reused.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bonzini at gnu dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #31 from Paolo Bonzini <bonzini at gnu dot org> ---
Ah, I see now.  I think you're right that the DF_REF_MUST_CLOBBER case should
also clear GEN in df_live_bb_local_compute.

However, regarding the "BTW" I am fairly sure now that df_live_bb_local_compute
and the corresponding function for MIR should handle may-clobber and may-sets
differently.  If you think of may-clobber and may-set as a diamond-shaped CFG:

             .                .
            / \              / \
           /   \            /   \
      clobber   |          set   |
          \    /            \    /
           \  /              \  /
            \/                \/

Then at the join point you have an "OR" for LIVE (so the clobber's KILL
disappears and the set's GEN remains), and an "AND" for MIR.  For MIR the
clobber's KILL remains and the set's GEN disappears.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 5323 bytes --]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #32 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
(In reply to Bernd Schmidt from comment #28)
> It is sufficient for OUT(3) to be all-zeros. And I don't think the
> LAST_CHANGE_AGE mechanism does anything to prevent it. Please try it
> out. I think you have to initialize your bitmaps correctly rather than
> rely on "visited".
Thank you very much for the reproducer: I confirm that the
LAST_CHANGE_AGE mechanism does not have the effect I thought. I just
updated my patch locally to initialize bitmaps to 1 for all registers
and thus remove the visited field: this fixes the issue you found.

> > (In reply to Bernd Schmidt from comment #14)
> > > I do have to say that I am still uncomfortable with changing RRE to
> 
> I did not write this.
Indeed: Kenneth Zadeck said this in comment #20. I made a pasto, sorry
for that!



(In reply to Paolo Bonzini from comment #29)
> BTW, are you sure that
> 
> +      if (DF_REF_FLAGS_IS_SET (def,
> +                  DF_REF_PARTIAL | DF_REF_CONDITIONAL))
> +   /* All partial or conditional def
> +      seen are included in the gen set. */
> +   bitmap_set_bit (gen, regno);
> 
> ?  I would have thought they don't belong in any set, and on the
> contrary I would have thought that may-clobber definitions count as
> kills.
For partial and conditional defs in the context of MIR:

  * if the register was initialized, then it is still initialized
    afterwards, whatever happens;

  * if the register was uninitialized, then in the case of partial def
    there will still be bits uninitialized and in the case of
    conditional def it is possible that the instruction leaves the
    register uninitialized: in both case there is a possibility to leave
    part of the register uninitialized.

So I would agree with: they don't belong in any set.

While thinking about this, I also realized with REE in mind that since
we need a conservative computation for MIR, we must set KILL/clear GEN
for register refs with DF_REF_MAY_CLOBBER: it may leave the register
uninitialized.

(In reply to Paolo Bonzini from comment #31)
> Ah, I see now.  I think you're right that the DF_REF_MUST_CLOBBER case
> should also clear GEN in df_live_bb_local_compute.
> 
> However, regarding the "BTW" I am fairly sure now that
> df_live_bb_local_compute and the corresponding function for MIR should
> handle may-clobber and may-sets differently.  If you think of
> may-clobber and may-set as a diamond-shaped CFG:
> 
> […]
> 
> Then at the join point you have an "OR" for LIVE (so the clobber's
> KILL disappears and the set's GEN remains), and an "AND" for MIR.  For
> MIR the clobber's KILL remains and the set's GEN disappears.
Agreed, thank you! I have updated both MIR and LIVE in the light of
this. (bootstrapped and regtested on x86_64-linux)
>From gcc-bugs-return-497873-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Sep 23 10:05:00 2015
Return-Path: <gcc-bugs-return-497873-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 33820 invoked by alias); 23 Sep 2015 10:05:00 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 33761 invoked by uid 48); 23 Sep 2015 10:04:57 -0000
From: "derodat at adacore dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
Date: Wed, 23 Sep 2015 10:05:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 6.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: derodat at adacore dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: attachments.isobsolete attachments.created
Message-ID: <bug-66790-4-KXKkfkAmih@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-66790-4@http.gcc.gnu.org/bugzilla/>
References: <bug-66790-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-09/txt/msg01851.txt.bz2
Content-length: 544

https://gcc.gnu.org/bugzilla/show_bug.cgi?idf790

Pierre-Marie de Rodat <derodat at adacore dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #36098|0                           |1
        is obsolete|                            |

--- Comment #33 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 36377
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id6377&actioníit
Updated candidate patch

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #34 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 36378
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36378&action=edit
Fix for DF_LIVE local BB information

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bonzini at gnu dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #35 from Paolo Bonzini <bonzini at gnu dot org> ---
Comment on attachment 36377
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36377
Updated candidate patch

> +     This problem determines which registers may be uninitialized. It first
> +     assumes these are all initialized and then it eliminates the ones reached
> +     by paths without crossing a definition.  The IN bitmap is clear at first
> +     (i.e. all registers are assumed not to be initialized) so don't consider
> +     its value the first time.  */
> +  return bitmap_and_into (op1, op2);

Is this comment obsolete?  The IN bitmap is all set at first.  Otherwise looks
good.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bernds at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #36 from Bernd Schmidt <bernds at gcc dot gnu.org> ---
This looks better. I still don't quite understand why you're treating
MUST_CLOBBER and MAY_CLOBBER defs differently in simulate. It looks like a
MUST_CLOBBER produces a bit in gen which I think is not what is wanted.

Anything wrong with writing this simply as follows?

      if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
        {
          bitmap_set_bit (kill, regno);
          bitmap_clear_bit (gen, regno);
        }
      /* In the worst case, partial and conditional defs can leave bits
         uninitialized, so assume they do not change anything.  */
      else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
        {
          bitmap_set_bit (gen, regno);
          bitmap_clear_bit (kill, regno);
        }

And, not as a requirement for your patch, but as a point for discussion - do we
want a special all_ones_bitmap that doesn't take up memory for purposes like
this? It would add two additional tests to each bitmap_{and,ior} operation.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bonzini at gnu dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #37 from Paolo Bonzini <bonzini at gnu dot org> ---
Bernd is right that you have a missing 'else'.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 4338 bytes --]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #38 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
(In reply to Paolo Bonzini from comment #35)
> Is this comment obsolete?  The IN bitmap is all set at first.
Yes, indeed: I removed the part you quoted.

(In reply to Paolo Bonzini from comment #35)
> Otherwise looks good.
Thank you! Does this include the DF_LIVE fix?


(In reply to Bernd Schmidt from comment #36)
> This looks better. I still don't quite understand why you're treating
> MUST_CLOBBER and MAY_CLOBBER defs differently in simulate. It looks
> like a MUST_CLOBBER produces a bit in gen which I think is not what is
> wanted.
> 
> Anything wrong with writing this simply as follows?
(In reply to Paolo Bonzini from comment #37)
> Bernd is right that you have a missing 'else'.
Pastos strike back! I updated df_mir_simulate_one_insn according to your
suggestion: thank you.

Besides, Eric told me live that instead of artificially clearing the
entry basic block’s IN set, we could use the confluence_0 for that. I
did this and took this opportunity to minimize code duplication: the
df_mir_init function now just calls df_mir_reset.

> And, not as a requirement for your patch, but as a point for
> discussion - do we want a special all_ones_bitmap that doesn't take up
> memory for purposes like this? It would add two additional tests to
> each bitmap_{and,ior} operation.

Good point, although what would the following yield, then?

    bitmap_clear (res);
    bitmap_set_bit (res, 1);
    bitmap_and_into (res, all_ones_bitmap);

I mean: we would need to represent bitmaps will all bits set but one
(and by extension: all but several).

Anyway, here's the updated patch, bootstrapped and regtested again on
x86_64-linux (plus a new testcase in gnat.dg). By the way, there's still
the MIR name, as we did not reach a consensus about a better name.
>From gcc-bugs-return-497953-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Sep 24 07:43:20 2015
Return-Path: <gcc-bugs-return-497953-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 67305 invoked by alias); 24 Sep 2015 07:43:20 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 67070 invoked by uid 48); 24 Sep 2015 07:43:16 -0000
From: "derodat at adacore dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/66790] Invalid uninitialized register handling in REE
Date: Thu, 24 Sep 2015 07:43:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 6.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: derodat at adacore dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: attachments.isobsolete attachments.created
Message-ID: <bug-66790-4-tbZk24sK2t@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-66790-4@http.gcc.gnu.org/bugzilla/>
References: <bug-66790-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-09/txt/msg01931.txt.bz2
Content-length: 544

https://gcc.gnu.org/bugzilla/show_bug.cgi?idf790

Pierre-Marie de Rodat <derodat at adacore dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #36377|0                           |1
        is obsolete|                            |

--- Comment #39 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Created attachment 36384
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id6384&actioníit
Updated candidate patch

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #41 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Thank you again for spotting this! Yes, these artificial defs break the
consevativeness for the MIR analysis. I guess your proposal would work:
considering as uninintialized registers than aren’t is conservative
although it will prevent more optimizations that one could expect in
REE. I don’t know if it’s a problem in practice but your example shows
that we have a lot of registers in this situation.

At this point, though, I wonder why artificial defs do not describe what
actually happens for this function. Shouldn’t we instead fix DF to emit
artificial defs only for actual input registers? I’ll investigate this.

… and then I will followup on gcc-patches as you suggested. Once more,
thank you all for your help in this! :-)
>From gcc-bugs-return-498449-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Oct 01 06:42:01 2015
Return-Path: <gcc-bugs-return-498449-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 109305 invoked by alias); 1 Oct 2015 06:42:01 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 109231 invoked by uid 48); 1 Oct 2015 06:41:58 -0000
From: "trippels at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c/67793] Detect incorrect function arg sizes at compile time.
Date: Thu, 01 Oct 2015 06:42:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: trippels at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cf_reconfirmed_on cc everconfirmed
Message-ID: <bug-67793-4-epm7bz0KnS@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-67793-4@http.gcc.gnu.org/bugzilla/>
References: <bug-67793-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-10/txt/msg00004.txt.bz2
Content-length: 1075

https://gcc.gnu.org/bugzilla/show_bug.cgi?idg793

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-10-01
                 CC|                            |trippels at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
In C99 you can add "static" to the array function argument:

extern int func(char x[static 32]);

But unfortunately gcc doesn't warn for this case yet.
Clang already does:

markus@x4 /tmp % clang -c test.i
test.i:5:10: warning: array argument is too small; contains 8 elements, callee
requires at least 32 [-Warray-bounds]
  return func(p);
         ^    ~
test.i:1:22: note: callee declares array parameter as static here
extern int func(char x[static 32]);
                     ^~~~~~~~~~~~
1 warning generated.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[bernds at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #42 from Bernd Schmidt <bernds at gcc dot gnu.org> ---
I don't think that would actually help. Even if something is an actual incoming
argument register, it may still be uninitialized by the caller. That's true for
plain scalars, but even more likely for something like the partial struct
initialization in comment #8.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #43 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
(In reply to Bernd Schmidt from comment #42)
> I don't think that would actually help. Even if something is an actual
> incoming argument register, it may still be uninitialized by the caller.
Sure, but my understanding is that what matters in DF is what happens inside
the function, so we can assume arguments are always initialized.

Actually this makes sense in the context of REE as well: we have one
(artificial) def for arguments so since this def has no corresponding
instruction, REE will not be able to remove z-extensions reaching this def.

That being said, I failed to get the “is it really used for incoming arguments”
hard-reg predicate, so falling back to your proposal: I will followup on
gcc-patches@.

Thanks! :-)
>From gcc-bugs-return-499340-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Oct 12 14:56:06 2015
Return-Path: <gcc-bugs-return-499340-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 4449 invoked by alias); 12 Oct 2015 14:56:06 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 4396 invoked by uid 48); 12 Oct 2015 14:56:02 -0000
From: "trippels at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/67935] internal compiler error: Segmentation fault
Date: Mon, 12 Oct 2015 14:56:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: 5.2.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: critical
X-Bugzilla-Who: trippels at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cf_reconfirmed_on cc everconfirmed
Message-ID: <bug-67935-4-cKfVPZipPQ@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-67935-4@http.gcc.gnu.org/bugzilla/>
References: <bug-67935-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-10/txt/msg00895.txt.bz2
Content-length: 2583

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67935

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-10-12
                 CC|                            |trippels at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
markus@x4 test % cat main.ii
typedef struct { template <typename> void m_fn1(); } base_t;

markus@x4 test % g++ -c main.ii
main.ii:1:54: internal compiler error: tree check: expected tree that contains
‘decl with visibility’ structure, have ‘template_decl’ in determine_visibility,
at cp/decl2.c:2291
 typedef struct { template <typename> void m_fn1(); } base_t;
                                                      ^
0xef9b34 tree_contains_struct_check_failed(tree_node const*,
tree_node_structure_enum, char const*, int, char const*)
        ../../gcc/gcc/tree.c:9694
0x6b71db contains_struct_check(tree_node*, tree_node_structure_enum, char
const*, int, char const*)
        ../../gcc/gcc/tree.h:2978
0x6b71db determine_visibility(tree_node*)
        ../../gcc/gcc/cp/decl2.c:2291
0x6baa87 reset_decl_linkage
        ../../gcc/gcc/cp/decl2.c:2665
0x6bac74 reset_type_linkage_2
        ../../gcc/gcc/cp/decl2.c:2693
0x61447d grokdeclarator(cp_declarator const*, cp_decl_specifier_seq*,
decl_context, int, tree_node**)
        ../../gcc/gcc/cp/decl.c:10699
0x614fe6 start_decl(cp_declarator const*, cp_decl_specifier_seq*, int,
tree_node*, tree_node*, tree_node**)
        ../../gcc/gcc/cp/decl.c:4769
0x707390 cp_parser_init_declarator
        ../../gcc/gcc/cp/parser.c:18088
0x707f35 cp_parser_simple_declaration
        ../../gcc/gcc/cp/parser.c:12007
0x703403 cp_parser_block_declaration
        ../../gcc/gcc/cp/parser.c:11881
0x7118a7 cp_parser_declaration
        ../../gcc/gcc/cp/parser.c:11778
0x70fe2a cp_parser_declaration_seq_opt
        ../../gcc/gcc/cp/parser.c:11657
0x710149 cp_parser_translation_unit
        ../../gcc/gcc/cp/parser.c:4174
0x710149 c_parse_file()
        ../../gcc/gcc/cp/parser.c:34695
0x85b752 c_common_parse_file()
        ../../gcc/gcc/c-family/c-opts.c:1064
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.
>From gcc-bugs-return-499341-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Oct 12 15:07:27 2015
Return-Path: <gcc-bugs-return-499341-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 21753 invoked by alias); 12 Oct 2015 15:07:26 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 21697 invoked by uid 48); 12 Oct 2015 15:07:23 -0000
From: "hjl.tools at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug bootstrap/67931] [6 Regression] Gcc [trunk revision 228704] failed to profiledbootstrap on x86_64
Date: Mon, 12 Oct 2015 15:07:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: bootstrap
X-Bugzilla-Version: 6.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: hjl.tools at gmail dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 6.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cf_reconfirmed_on cc target_milestone everconfirmed
Message-ID: <bug-67931-4-2npE5mUGOZ@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-67931-4@http.gcc.gnu.org/bugzilla/>
References: <bug-67931-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-10/txt/msg00896.txt.bz2
Content-length: 608

https://gcc.gnu.org/bugzilla/show_bug.cgi?idg931

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-10-12
                 CC|                            |hubicka at ucw dot cz
   Target Milestone|---                         |6.0
     Ever confirmed|0                           |1

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> ---
It was caused by r228703.

[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[pmderodat at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #44 from pmderodat at gcc dot gnu.org ---
Author: pmderodat
Date: Mon Oct 19 23:47:35 2015
New Revision: 229008

URL: https://gcc.gnu.org/viewcvs?rev=229008&root=gcc&view=rev
Log:
REE: fix uninitialized registers handling

gcc/ChangeLog:

        PR rtl-optimization/66790
        * df.h (DF_MIR): New macro.
        (DF_LAST_PROBLEM_PLUS1): Update to be past DF_MIR
        (DF_MIR_INFO_BB): New macro.
        (DF_MIR_IN, DF_MIR_OUT): New macros.
        (struct df_mir_bb_info): New.
        (df_mir): New macro.
        (df_mir_add_problem, df_mir_simulate_one_insn): New forward
        declarations.
        (df_mir_get_bb_info): New.
        * df-problems.c (struct df_mir_problem_data): New.
        (df_mir_free_bb_info, df_mir_alloc, df_mir_reset,
        df_mir_bb_local_compute, df_mir_local_compute, df_mir_init,
        df_mir_confluence_0, df_mir_confluence_n,
        df_mir_transfer_function, df_mir_free, df_mir_top_dump,
        df_mir_bottom_dump, df_mir_verify_solution_start,
        df_mir_verify_solution_end): New.
        (problem_MIR): New.
        (df_mir_add_problem, df_mir_simulate_one_insn): New.
        * timevar.def (TV_DF_MIR): New.
        * ree.c: Include bitmap.h
        (add_removable_extension): Add an INIT_REGS parameter.  Use it
        to skip zero-extensions that may get an uninitialized register.
        (find_removable_extensions): Compute must-initialized registers
        using the MIR dataflow problem. Update the call to
        add_removable_extension.
        (find_and_remove_re): Call df_mir_add_problem.

gcc/testsuite/ChangeLog:

        * gnat.dg/opt50.adb: New test.
        * gnat.dg/opt50_pkg.adb: New helper.
        * gnat.dg/opt50_pkg.ads: New helper.

Added:
    trunk/gcc/testsuite/gnat.dg/opt50.adb
    trunk/gcc/testsuite/gnat.dg/opt50_pkg.adb
    trunk/gcc/testsuite/gnat.dg/opt50_pkg.ads
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/df-problems.c
    trunk/gcc/df.h
    trunk/gcc/ree.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/timevar.def