Bootstrap failure on trunk: x86_64-linux-gnu

Bootstrap failure on trunk: x86_64-linux-gnu

[Andrew Haley]

When building a-textio in libada, today's gcc build fails when memory
is exhausted.

Seems like VRP is looping, consuming more and more memory.

Andrew.



make[7]: `a-teioed.o' is up to date.
/home/aph/gcc/build-x86_64-unknown-linux-gnu/./gcc/xgcc -B/home/aph/gcc/build-x86_64-unknown-linux-gnu/./gcc/ -B/home/aph/gcc/install/x86_64-unknown-linux-gnu/bin/ -B/home/aph/gcc/install/x86_64-unknown-linux-gnu/lib/ -isystem /home/aph/gcc/install/x86_64-unknown-linux-gnu/include -isystem /home/aph/gcc/install/x86_64-unknown-linux-gnu/sys-include -c -g -O2 -fPIC      -W -Wall -gnatpg  a-textio.adb -o a-textio.o
virtual memory exhausted: Cannot allocate memory
make[7]: *** [a-textio.o] Error 1
make[7]: Leaving directory `/homes/home/aph/gcc/build-x86_64-unknown-linux-gnu/gcc/ada/rts'
make[6]: *** [gnatlib] Error 2
make[6]: Leaving directory `/homes/home/aph/gcc/build-x86_64-unknown-linux-gnu/gcc/ada'
make[5]: *** [gnatlib-shared-default] Error 2
make[5]: Leaving directory `/homes/home/aph/gcc/build-x86_64-unknown-linux-gnu/gcc/ada'
make[4]: *** [gnatlib-shared-dual] Error 2
make[4]: Leaving directory `/homes/home/aph/gcc/build-x86_64-unknown-linux-gnu/gcc/ada'
make[3]: *** [gnatlib-shared] Error 2
make[3]: Leaving directory `/homes/home/aph/gcc/build-x86_64-unknown-linux-gnu/gcc/ada'
make[2]: *** [gnatlib-shared] Error 2
make[2]: Leaving directory `/homes/home/aph/gcc/build-x86_64-unknown-linux-gnu/x86_64-unknown-linux-gnu/libada'
make[1]: *** [all-target-libada] Error 2


Program received signal SIGINT, Interrupt.
0x00000000009260c9 in tree_int_cst_compare (t1=0x2b05a43cfe70, t2=0x2b05a55296c0)
    at /home/aph/gcc/trunk/gcc/tree.c:4390
(gdb) bt
#0  0x00000000009260c9 in tree_int_cst_compare (t1=0x2b05a43cfe70, t2=0x2b05a55296c0)
    at /home/aph/gcc/trunk/gcc/tree.c:4390
#1  0x000000000095ce9d in extract_range_from_expr (vr=0x7fffffd07e80, expr=0x2b05a540c9b0)
    at /home/aph/gcc/trunk/gcc/tree-vrp.c:614
#2  0x000000000095d752 in vrp_visit_assignment (stmt=0x2b05a540ca00, output_p=0x7fffffd07ef0)
    at /home/aph/gcc/trunk/gcc/tree-vrp.c:3366
#3  0x00000000006a2bf1 in simulate_stmt (stmt=0x2b05a540ca00)
    at /home/aph/gcc/trunk/gcc/tree-ssa-propagate.c:306
#4  0x00000000006a2e0f in process_ssa_edge_worklist (worklist=0x12417e8)
    at /home/aph/gcc/trunk/gcc/tree-ssa-propagate.c:380
#5  0x00000000006a3243 in ssa_propagate (visit_stmt=Variable "visit_stmt" is not available.
) at /home/aph/gcc/trunk/gcc/tree-ssa-propagate.c:683
#6  0x000000000095f2bf in execute_vrp () at /home/aph/gcc/trunk/gcc/tree-vrp.c:4569
#7  0x000000000094fd86 in execute_one_pass (pass=0x12f3550) at /home/aph/gcc/trunk/gcc/passes.c:854
#8  0x000000000094feec in execute_pass_list (pass=0x12f3550) at /home/aph/gcc/trunk/gcc/passes.c:898
#9  0x000000000094fefe in execute_pass_list (pass=0xdd6380) at /home/aph/gcc/trunk/gcc/passes.c:899
#10 0x000000000065853a in tree_rest_of_compilation (fndecl=0x2b05a5359500)
    at /home/aph/gcc/trunk/gcc/tree-optimize.c:412
#11 0x000000000041b715 in gnat_expand_body (gnu_decl=0x2b05a5359500) at /home/aph/gcc/trunk/gcc/ada/misc.c:653
#12 0x00000000009a3966 in cgraph_expand_function (node=0x2b05a539f6c0)
    at /home/aph/gcc/trunk/gcc/cgraphunit.c:1101
#13 0x00000000009a5f38 in cgraph_optimize () at /home/aph/gcc/trunk/gcc/cgraphunit.c:1166
#14 0x000000000041bf8a in gnat_parse_file (set_yydebug=Variable "set_yydebug" is not available.
) at /home/aph/gcc/trunk/gcc/ada/misc.c:245
#15 0x0000000000921378 in toplev_main (argc=Variable "argc" is not available.
) at /home/aph/gcc/trunk/gcc/toplev.c:999
#16 0x0000003d4071d024 in __libc_start_main () from /lib64/libc.so.6
#17 0x00000000004030b9 in _start ()
#18 0x00007fffffd081f8 in ?? ()
#19 0x0000000000000000 in ?? ()
(gdb) 

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Andrew Pinski]

On Feb 19, 2006, at 12:09 PM, Andrew Haley wrote:

> When building a-textio in libada, today's gcc build fails when memory
> is exhausted.

This has already been reported as PR 26348 and it looks like a bug
in the Ada front-end.

Thanks,
Andrew Pinski

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Arnaud Charlet]

> This has already been reported as PR 26348 and it looks like a bug
> in the Ada front-end.

Note that technically, its still a regression caused by a non Ada patch.

Anyway, hopefully Eric and Jeff can work together in identifying the
proper fix.

Arno

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Eric Botcazou]

> Anyway, hopefully Eric and Jeff can work together in identifying the
> proper fix.

Jeff already did a thorough analysis of the problem (thanks!) and came to the 
following double conclusion.  Quoting him:

"First, the inconsistency between the type's precision in its min/max
values needs to be fixed.  Most likely this is an Ada FE problem."

more precisely:

"Now for the first "oddity".  If we look at the underlying type
for last we have a type "natural___XDLU_0__2147483647".  What's
interesting about it is that it has a 32bit type precision, but
the min/max values only specify 31 bits.  ie, the min/max values
are 0, 0x7fffffff."

That's an old problem, which has already been discussed IIRC: should 
TYPE_MAX_VALUE/TYPE_MIN_VALUE be constrained by TYPE_PRECISION and 
TYPE_UNSIGNED?

Then:

"Second, for a given integer type (such as natural___XDLU_0_2147483647),
the type for the nodes in TYPE_MIN_VALUE and TYPE_MAX_VALUE really
should be a natural___XDLU_0_2147483647.  ie, the type of an integer
constant should be the same as the type of its min/max values."

I think that one is new and again pertains to TYPE_MAX_VALUE/TYPE_MIN_VALUE.


Clearly Ada stretches a lot more VRP than C-based languages because of its 
subtypes with non-canonical bounds.  However, there always should be the base 
type at hand when things go awry; for example in int_fits_type_p

  /* If we haven't been able to decide at this point, there nothing more we
     can check ourselves here.  Look at the base type if we have one and it
     has the same precision.  */
  if (TREE_CODE (type) == INTEGER_TYPE
      && TREE_TYPE (type) != 0
      && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
    return int_fits_type_p (c, TREE_TYPE (type));


Richard, what do you think?

-- 
Eric Botcazou

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Sun, 2006-02-19 at 20:15 +0100, Eric Botcazou wrote:

> >"Now for the first "oddity".  If we look at the underlying type
> > for last we have a type "natural___XDLU_0__2147483647".  What's
> >interesting about it is that it has a 32bit type precision, but
> > the min/max values only specify 31 bits.  ie, the min/max values
> > are 0, 0x7fffffff."
> 
> That's an old problem, which has already been discussed IIRC: should 
> TYPE_MAX_VALUE/TYPE_MIN_VALUE be constrained by TYPE_PRECISION and 
> TYPE_UNSIGNED?
My feeling?  Absolutely, TYPE_MIN_VALUE and TYPE_MAX_VALUE should
represent the set of values that an object of the type may hold.
Any other definition effectively renders those values useless.

ie, if an object can have the values 0..128 at runtime, then
TYPE_MIN_VALUE/TYPE_MAX_VALUE must cover that entire range.  
0..128.  If TYPE_MIN_VALUE/TYPE_MAX_VALUE only cover 0..127,
then that's a bug.

I suspect we get this behavior from the Ada front-end as a
side effect of the language and possibly the need to do 
runtime bounds checking on object values.   But that's no
excuse for a front-end to lie about the bounds of an object.

It'll be tedious, but I guess possible to have VRP look one
level deeper into the type to get a max/min value.  But that's
really a bandaid IMHO.



> 
> Then:
> 
> "Second, for a given integer type (such as natural___XDLU_0_2147483647),
> the type for the nodes in TYPE_MIN_VALUE and TYPE_MAX_VALUE really
> should be a natural___XDLU_0_2147483647.  ie, the type of an integer
> constant should be the same as the type of its min/max values."
> 
> I think that one is new and again pertains to TYPE_MAX_VALUE/TYPE_MIN_VALUE.
This is probably a secondary issue.  We end up ping-ponging both
on values for the range *and* on the type of the range.  I suspect
but can not verify yet that ping-ponging on the type of the range
will result in infinite iteration as well.    I'm willing to table
this until we get the TYPE_MIN/TYPE_MAX stuff resolved at which
point we can verify VRP's behavior when the types ping-pong.
jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Mark Mitchell]

Jeffrey A Law wrote:

> My feeling?  Absolutely, TYPE_MIN_VALUE and TYPE_MAX_VALUE should
> represent the set of values that an object of the type may hold.
> Any other definition effectively renders those values useless.

I agree -- with the obvious caveat that it need not be the case that the
object actually have that value if the program has invoked undefined
behavior.  So, if you have an 5-bit type, stored in a byte, and you
manage to get 255 in that byte, and you read the value, you might see
255 at runtime -- but only because your program was busted anyhow.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Guenther]

On 2/21/06, Mark Mitchell <mark@codesourcery.com> wrote:
> Jeffrey A Law wrote:
>
> > My feeling?  Absolutely, TYPE_MIN_VALUE and TYPE_MAX_VALUE should
> > represent the set of values that an object of the type may hold.
> > Any other definition effectively renders those values useless.
>
> I agree -- with the obvious caveat that it need not be the case that the
> object actually have that value if the program has invoked undefined
> behavior.  So, if you have an 5-bit type, stored in a byte, and you
> manage to get 255 in that byte, and you read the value, you might see
> 255 at runtime -- but only because your program was busted anyhow.

Right.  And if Ada wants to test for this condition using 'Valid, it should do
the range comparison in the base type and use a VIEW_CONVERT_EXPR
to get to the object of the base type from the 5-bit-type to avoid VRP
optimizing
away the comparison.

Richard.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Wed, 2006-02-22 at 11:51 +0100, Richard Guenther wrote:
> On 2/21/06, Mark Mitchell <mark@codesourcery.com> wrote:
> > Jeffrey A Law wrote:
> >
> > > My feeling?  Absolutely, TYPE_MIN_VALUE and TYPE_MAX_VALUE should
> > > represent the set of values that an object of the type may hold.
> > > Any other definition effectively renders those values useless.
> >
> > I agree -- with the obvious caveat that it need not be the case that the
> > object actually have that value if the program has invoked undefined
> > behavior.  So, if you have an 5-bit type, stored in a byte, and you
> > manage to get 255 in that byte, and you read the value, you might see
> > 255 at runtime -- but only because your program was busted anyhow.
> 
> Right.  And if Ada wants to test for this condition using 'Valid, it should do
> the range comparison in the base type and use a VIEW_CONVERT_EXPR
> to get to the object of the base type from the 5-bit-type to avoid VRP
> optimizing away the comparison.
Agreed wholeheartedly.


Jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Tue, 2006-02-21 at 14:56 -0800, Mark Mitchell wrote:
> Jeffrey A Law wrote:
> 
> > My feeling?  Absolutely, TYPE_MIN_VALUE and TYPE_MAX_VALUE should
> > represent the set of values that an object of the type may hold.
> > Any other definition effectively renders those values useless.
> 
> I agree -- with the obvious caveat that it need not be the case that the
> object actually have that value if the program has invoked undefined
> behavior.  So, if you have an 5-bit type, stored in a byte, and you
> manage to get 255 in that byte, and you read the value, you might see
> 255 at runtime -- but only because your program was busted anyhow.
Right.

This does highlight one of the issues that keeps nagging at me.
For an enumeration type, presumably we have TYPE_PRECISION set to
the minimum precision necessary to hold all the values in the enum.
What are TYPE_MIN_VAL/TYPE_MAX_VAL?    Does TYPE_MAX_VALUE include
values outside the enum, but which are included by the TYPE_PRECISION?

Consider

enum
{
  RED,
  GREEN,
  BLUE,
  BLACK,
  WHITE
}


for (color = RED; color <= WHITE; color++)

Now we might think that color is constrained to the values
RED .. WHITE.  However at runtime we can actually get
RED .. WHITE + 1.  Does TYPE_MAX_VALUE cover WHITE + 1?

If not, then we've got more latent bugs waiting to nail us.

It'll be simple enough to check, but if someone knows the
answer off the top of their head it would save me a few minutes
of investigative work.

jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Mark Mitchell]

Jeffrey A Law wrote:

> This does highlight one of the issues that keeps nagging at me.
> For an enumeration type, presumably we have TYPE_PRECISION set to
> the minimum precision necessary to hold all the values in the enum.
> What are TYPE_MIN_VAL/TYPE_MAX_VAL?    Does TYPE_MAX_VALUE include
> values outside the enum, but which are included by the TYPE_PRECISION?

In C++, there are no such values.  In C++, the range of the type gets
rounded up to a power of two, so for:

> Consider
> 
> enum
> {
>   RED,
>   GREEN,
>   BLUE,
>   BLACK,
>   WHITE
> }

you can happily assign "5" to this enum.  The C++ front end correctly
sets TYPE_MAX_VALUE in this case.

I'm not sure what the situation is in C.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Wed, 2006-02-22 at 09:00 -0800, Mark Mitchell wrote:
> Jeffrey A Law wrote:
> 
> > This does highlight one of the issues that keeps nagging at me.
> > For an enumeration type, presumably we have TYPE_PRECISION set to
> > the minimum precision necessary to hold all the values in the enum.
> > What are TYPE_MIN_VAL/TYPE_MAX_VAL?    Does TYPE_MAX_VALUE include
> > values outside the enum, but which are included by the TYPE_PRECISION?
> 
> In C++, there are no such values.  In C++, the range of the type gets
> rounded up to a power of two, so for:
Great.  That's what I expected to hear.  Hopefully the C 
front end does something similar.

Jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Henderson]

On Wed, Feb 22, 2006 at 10:06:25AM -0700, Jeffrey A Law wrote:
> > > This does highlight one of the issues that keeps nagging at me.
> > > For an enumeration type, presumably we have TYPE_PRECISION set to
> > > the minimum precision necessary to hold all the values in the enum.
> > > What are TYPE_MIN_VAL/TYPE_MAX_VAL?    Does TYPE_MAX_VALUE include
> > > values outside the enum, but which are included by the TYPE_PRECISION?
> > 
> > In C++, there are no such values.  In C++, the range of the type gets
> > rounded up to a power of two, so for:
> Great.  That's what I expected to hear.  Hopefully the C 
> front end does something similar.

The C front end correctly copies the min, max, and precision
from the base type.

The C90 language doesn't have the clauses that C++ does that
allows for the narrowed precision.  I think one can construe
that in C99, with extended integral types, but there's not so
much to be gained that it's worth being incompatible with C90.


r~

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Eric Botcazou]

[Sorry for the delay]

> > That's an old problem, which has already been discussed IIRC: should
> > TYPE_MAX_VALUE/TYPE_MIN_VALUE be constrained by TYPE_PRECISION and
> > TYPE_UNSIGNED?
>
> My feeling?  Absolutely, TYPE_MIN_VALUE and TYPE_MAX_VALUE should
> represent the set of values that an object of the type may hold.
> Any other definition effectively renders those values useless.
>
> ie, if an object can have the values 0..128 at runtime, then
> TYPE_MIN_VALUE/TYPE_MAX_VALUE must cover that entire range.
> 0..128.  If TYPE_MIN_VALUE/TYPE_MAX_VALUE only cover 0..127,
> then that's a bug.

I was actually referring to explicit constraints on TYPE_MAX_VALUE and 
TYPE_MIN_VALUE derived from TYPE_PRECISION and TYPE_UNSIGNED, for example 
that ceil(log2(TYPE_MAX_VALUE - TYPE_MIN_VALUE)) must be greater or equal to 
TYPE_PRECISION.

> I suspect we get this behavior from the Ada front-end as a
> side effect of the language and possibly the need to do
> runtime bounds checking on object values.   But that's no
> excuse for a front-end to lie about the bounds of an object.

I don't think the Ada front-end lies about the bounds of types, but it does 
virtually use the whole spectrum of TYPE_PRECISION, TYPE_MAX_VALUE and 
TYPE_MIN_VALUE settings, unlike the C-family of front-ends.

This problem was already raised when Diego contributed the VRP pass and Diego 
ajusted it to cope with Ada.  AFAIK Ada and VRP work fine on the 4.1 branch.

-- 
Eric Botcazou

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Tue, 2006-02-28 at 12:06 +0100, Eric Botcazou wrote:
> [Sorry for the delay]
No worries.

> I was actually referring to explicit constraints on TYPE_MAX_VALUE and 
> TYPE_MIN_VALUE derived from TYPE_PRECISION and TYPE_UNSIGNED, for example 
> that ceil(log2(TYPE_MAX_VALUE - TYPE_MIN_VALUE)) must be greater or equal to 
> TYPE_PRECISION.
OK.

> > I suspect we get this behavior from the Ada front-end as a
> > side effect of the language and possibly the need to do
> > runtime bounds checking on object values.   But that's no
> > excuse for a front-end to lie about the bounds of an object.
> 
> I don't think the Ada front-end lies about the bounds of types, but it does 
> virtually use the whole spectrum of TYPE_PRECISION, TYPE_MAX_VALUE and 
> TYPE_MIN_VALUE settings, unlike the C-family of front-ends.
> 
> This problem was already raised when Diego contributed the VRP pass and Diego 
> ajusted it to cope with Ada.  AFAIK Ada and VRP work fine on the 4.1 branch.
And IMHO the work-arond in VRP is a hack around this braindamage.  

Basically with the way Ada's setting of TYPE_MIN_VALUE/TYPE_MAX_VALUE
effectively makes them useless as we can not rely on them to 
actually reflect the set of values allowed in an object.

jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Eric Botcazou]

> Basically with the way Ada's setting of TYPE_MIN_VALUE/TYPE_MAX_VALUE
> effectively makes them useless as we can not rely on them to
> actually reflect the set of values allowed in an object.

Sorry, but why are you saying "we can not rely on them to actually reflect the 
set of values allowed in an object"?  I think we can.  My understanding is 
that the only subtlety with Ada is the TYPE_PRECISION thing, as you've 
written in your patch:

+   /* Ada creates sub-types where TYPE_MIN_VALUE/TYPE_MAX_VALUE do not
+      cover the entire range of values allowed by TYPE_PRECISION.
+ 
+      We do not want to optimize away conversions to such types.  Long
+      term I'd rather see the Ada front-end fixed.  */

The obvious question would then be, why bother with TYPE_MIN_VALUE and 
TYPE_MAX_VALUE if they can be directly deduced from TYPE_PRECISION and 
TYPE_UNSIGNED?  How do you represent subtypes with non-canonical bounds?

-- 
Eric Botcazou

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Tue, 2006-02-28 at 18:42 +0100, Eric Botcazou wrote:
> > Basically with the way Ada's setting of TYPE_MIN_VALUE/TYPE_MAX_VALUE
> > effectively makes them useless as we can not rely on them to
> > actually reflect the set of values allowed in an object.
> 
> Sorry, but why are you saying "we can not rely on them to actually reflect the 
> set of values allowed in an object"?  I think we can.  My understanding is 
> that the only subtlety with Ada is the TYPE_PRECISION thing, as you've 
> written in your patch:
Here's a great example from uintp.adb (which is the cause of the
testsuite hang FWIW)

We have a loop with the following termination code in uintp.num_bits

  # BLOCK 8
  # PRED: 5 [100.0%]  (fallthru,exec) 6 (fallthru,dfs_back,exec)
  # num_2 = PHI <num_49(5), num_10(6)>;
  # bits_1 = PHI <bits_50(5), bits_13(6)>;
<L7>:;
  num.265_5 = (types__TintB) num_2;
  if (num.265_5 <= 0) goto <L5>; else goto <L4>;
  # SUCC: 7 (true,exec) 6 (false,exec)

num_2 has the type:



 <integer_type 0x4006aa6c types__nat___XDLU_0__2147483647
    type <integer_type 0x4006a33c types__TintB sizes-gimplified
asm_written public visited SI
        size <integer_cst 0x400163d8 constant invariant 32>
        unit size <integer_cst 0x40016168 constant invariant 4>
        user align 32 symtab 1074169056 alias set 8 precision 32 min
<integer_cst 0x4006c810 -2147483648> max <integer_cst 0x4006c870
2147483647> RM size <integer_cst 0x400163d8 32>>
    sizes-gimplified asm_written public visited unsigned SI size
<integer_cst 0x400163d8 32> unit size <integer_cst 0x40016168 4>
    user align 32 symtab 1080625184 alias set 8 precision 32 min
<integer_cst 0x40075498 0> max <integer_cst 0x4006c870 2147483647>
    RM size <integer_cst 0x40016318 type <integer_type 0x4002505c
bit_size_type> constant invariant 31>>


Note carefully, it has a min/max value of 0, 21474833647.  So
not surprisingly we have a range of [0, INF] recorded for num_2.

So given the range [0, INF] and the test num_5 <= 0 we can
(and do) simplify the test to num_5 == 0.


Sooooo, why am I bringing this up?  Because num can actually have
the value 0x80000000 at runtime, which is out of its type's
MIN/MAX range.  And what do you think happens?  Well, given the
(valid) simplification of the loop test and the way "num" is
assigned within the loop (num = num / 2), the loop never terminates.

How do we get the value 0x80000000 into "num"?  Let's look at
the first two blocks in our function:



  # BLOCK 2
  # PRED: ENTRY (fallthru,exec)
  #   uintp__uints__table_41 = V_MAY_DEF <uintp__uints__table_14>;
  #   uintp__udigits__table_42 = V_MAY_DEF <uintp__udigits__table_23>;
  #   TMT.2002_43 = V_MAY_DEF <TMT.2002_39>;
  #   TMT.2003_44 = V_MAY_DEF <TMT.2003_40>;
  D.2350_4 = uintp__ui_is_in_int_range (input_3);
  if (D.2350_4 != 0) goto <L0>; else goto <L1>;
  # SUCC: 3 (true,exec) 4 (false,exec)

  # BLOCK 3
  # PRED: 2 (true,exec)
<L0>:;
  #   uintp__uints__table_45 = V_MAY_DEF <uintp__uints__table_41>;
  #   uintp__udigits__table_46 = V_MAY_DEF <uintp__udigits__table_42>;
  #   TMT.2002_47 = V_MAY_DEF <TMT.2002_43>;
  #   TMT.2003_48 = V_MAY_DEF <TMT.2003_44>;
  D.2351_34 = uintp__ui_to_int (input_3);
  D.2352_35 = (types__TintB) D.2351_34;
  D.2353_36 = ABS_EXPR <D.2352_35>;
  num_37 = (types__nat___XDLU_0__2147483647) D.2353_36;
  goto <bb 5> (<L2>);
  # SUCC: 5 (fallthru,exec)

Let's assume that uintp__ui_is_int_range returns true (as it does) 
for our input (2000000007).

uintp__ui_to_int returns 0x80000000  [For you non-Ada folks,
uintp__ui_to_int doesn't do what you might initially think].  And
ABS (0x80000000) is 0x80000000 which we then proceed to stuff
into num_37 after a couple typecasts.  Voila, we have a value
in a variable that is out of the MIN/MAX range associated with
the variable.


> +   /* Ada creates sub-types where TYPE_MIN_VALUE/TYPE_MAX_VALUE do not
> +      cover the entire range of values allowed by TYPE_PRECISION.
> + 
> +      We do not want to optimize away conversions to such types.  Long
> +      term I'd rather see the Ada front-end fixed.  */
> 
> The obvious question would then be, why bother with TYPE_MIN_VALUE and 
> TYPE_MAX_VALUE if they can be directly deduced from TYPE_PRECISION and 
> TYPE_UNSIGNED?  How do you represent subtypes with non-canonical bounds?
I wouldn't have a problem with non-canonical bounds if there were
no way to get a value into an object which is outside the 
bounds.  But if we can get values into the object which are outside
those bounds, then either the bounds are incorrect or the program
is invalid.  

Jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Daniel Jacobowitz]

On Tue, Feb 28, 2006 at 03:40:37PM -0700, Jeffrey A Law wrote:
> Here's a great example from uintp.adb (which is the cause of the
> testsuite hang FWIW)
> 
> We have a loop with the following termination code in uintp.num_bits
> 
>   # BLOCK 8
>   # PRED: 5 [100.0%]  (fallthru,exec) 6 (fallthru,dfs_back,exec)
>   # num_2 = PHI <num_49(5), num_10(6)>;
>   # bits_1 = PHI <bits_50(5), bits_13(6)>;
> <L7>:;
>   num.265_5 = (types__TintB) num_2;
>   if (num.265_5 <= 0) goto <L5>; else goto <L4>;
>   # SUCC: 7 (true,exec) 6 (false,exec)

...

> Sooooo, why am I bringing this up?  Because num can actually have
> the value 0x80000000 at runtime, which is out of its type's
> MIN/MAX range.  And what do you think happens?  Well, given the
> (valid) simplification of the loop test and the way "num" is
> assigned within the loop (num = num / 2), the loop never terminates.

I've been following this entire thread, and I think there's a serious
disconnect between the parties - it's unfortunate that none of the
tree-ssa folks involved know Ada as I suspect that would straighten
it out in a hurry.  This is a perfect example.  Now that we have some
concrete code that's causing a problem, let's take a look at it
(bear in mind, I don't know Ada either):

   function Num_Bits (Input : Uint) return Nat is
      Bits : Nat;
      Num  : Nat;

   begin
      if UI_Is_In_Int_Range (Input) then
         Num := abs (UI_To_Int (Input));
         Bits := 0;

      else
         Bits := Base_Bits * (Uints.Table (Input).Length - 1);
         Num  := abs (Udigits.Table (Uints.Table (Input).Loc));
      end if;

      while Types.">" (Num, 0) loop
         Num := Num / 2;
         Bits := Bits + 1;
      end loop;

      return Bits;
   end Num_Bits;

I'm going to assume that UI_Is_In_Int_Range isn't true for 0x80000000.
The other case is still assigning 0x80000000 to Nat somehow.  I'd be
amazed if that's really valid Ada!  Could someone who knows the
language comment, please?

> I wouldn't have a problem with non-canonical bounds if there were
> no way to get a value into an object which is outside the 
> bounds.  But if we can get values into the object which are outside
> those bounds, then either the bounds are incorrect or the program
> is invalid.  

Ignoring 'Valid, which folks agreed to do earlier, I think everyone
agrees with this statement - which is why I suspect that there's
something wrong with Num_Bits.

-- 
Daniel Jacobowitz
CodeSourcery

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Laurent GUERBY]

On Tue, 2006-02-28 at 18:59 -0500, Daniel Jacobowitz wrote:
> On Tue, Feb 28, 2006 at 03:40:37PM -0700, Jeffrey A Law wrote:
> > Here's a great example from uintp.adb (which is the cause of the
> > testsuite hang FWIW)
> > 
> > We have a loop with the following termination code in uintp.num_bits
> > 
> >   # BLOCK 8
> >   # PRED: 5 [100.0%]  (fallthru,exec) 6 (fallthru,dfs_back,exec)
> >   # num_2 = PHI <num_49(5), num_10(6)>;
> >   # bits_1 = PHI <bits_50(5), bits_13(6)>;
> > <L7>:;
> >   num.265_5 = (types__TintB) num_2;
> >   if (num.265_5 <= 0) goto <L5>; else goto <L4>;
> >   # SUCC: 7 (true,exec) 6 (false,exec)
> 
> ...
> 
> > Sooooo, why am I bringing this up?  Because num can actually have
> > the value 0x80000000 at runtime, which is out of its type's
> > MIN/MAX range.  And what do you think happens?  Well, given the
> > (valid) simplification of the loop test and the way "num" is
> > assigned within the loop (num = num / 2), the loop never terminates.
> 
> I've been following this entire thread, and I think there's a serious
> disconnect between the parties - it's unfortunate that none of the
> tree-ssa folks involved know Ada as I suspect that would straighten
> it out in a hurry.  This is a perfect example.  Now that we have some
> concrete code that's causing a problem, let's take a look at it
> (bear in mind, I don't know Ada either):
> 
>    function Num_Bits (Input : Uint) return Nat is
>       Bits : Nat;
>       Num  : Nat;
> 
>    begin
>       if UI_Is_In_Int_Range (Input) then
>          Num := abs (UI_To_Int (Input));
>          Bits := 0;
> 
>       else
>          Bits := Base_Bits * (Uints.Table (Input).Length - 1);
>          Num  := abs (Udigits.Table (Uints.Table (Input).Loc));
>       end if;
> 
>       while Types.">" (Num, 0) loop
>          Num := Num / 2;
>          Bits := Bits + 1;
>       end loop;
> 
>       return Bits;
>    end Num_Bits;

The specifications in uintp.ads says:

   function Num_Bits (Input : Uint) return Nat;
   --  Approximate number of binary bits in given universal integer.
   --  This function is used for capacity checks, and it can be one
   --  bit off without affecting its usage.

So this is a hint function, anything not hanging should do, like

if UI_Is_In_Int_Range (Input) then
   return Nat'Size;
else
...

> I'm going to assume that UI_Is_In_Int_Range isn't true for 0x80000000.
> The other case is still assigning 0x80000000 to Nat somehow.  I'd be
> amazed if that's really valid Ada!  Could someone who knows the
> language comment, please?

Ada checks are off when compiling the FE, in full Ada you
should get a Constraint_Error on the abs line on int'first.

You should get an exception it if you put a 

   pragma Unsuppress (All_Checks);

before begin.

So this is likely to be a FE Ada coding bug and not a FE/ME/BE interface
issue, thanks for spotting this!

Laurent

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

Here's the next segment in the ongoing saga of VRP vs Ada...
Not surprisingly we have another case where an object gets a
value outside of its TYPE_MIN_VALUE/TYPE_MAX_VALUE defined range.

Investigating the c460008 testsuite failure we have the following
code for Fixed_To_Short before VRP runs:




  # BLOCK 4
  # PRED: 3 (fallthru,exec)
  D.1294_13 = D.1294_12;
  D.1309_32 = for_the_value_31 /[rd] 1000000000;
  D.1310_33 = (UNSIGNED_64) D.1309_32;
  if (D.1310_33 > 255) goto <L0>; else goto <L1>;
  # SUCC: 5 (true,exec) 6 (false,exec)

  # BLOCK 5 
  # PRED: 4 (true,exec)
<L0>:;
  __gnat_rcheck_10 ("c460008.adb", 162);
  # SUCC: 13 (ab,eh,exec) 18 (ab,eh,exec) 29 (ab,eh,exec)
  
  # BLOCK 6
  # PRED: 4 (false,exec)
<L1>:;
  iftmp.78_63 = D.1309_32;
  iftmp.78_64 = D.1309_32;
  D.1316_65 = (c460008__unsigned_edge_8) D.1309_32;
  if (D.1316_65 == 255) goto <L3>; else goto <L4>;
  # SUCC: 7 (true,exec) 8 (false,exec)

D.1309_32's type has the range [0x8000000000000000,0x7fffffffffffffff]
with 64bit precision.

In block #6 we cast the value of D.1309_32 into a smaller type,
specifically c460008__unsigned_edge_8 and store the result into
D.1316_64 which has type c460008__unsigned_edge_8.

c460008__unsigned_edge_8's range is [ ,254] with 8 bit precision.

Note carefully that with the range [ ,254] (according to
TYPE_MIN_VALUE/TYPE_MAX_VALUE) that the test

if (D.1316_65 == 255)

Must always be false.  So VRP, as expected, wipes out test
completely.

The problem (of course) is D.1316_65 can and does actually hold
values outside the range [ ,254] at runtime.  For example, it could
hold the value 255 if D.1309_32 had the value 255, which would occur
if for_the_value_31 held the value 255000000000.

Someone with a better knowledge of Ada is going to need to step
in here, but based on the type information provided by the Ada
front-end, VRP is doing the right thing here.


Jeff

ACATS c460008 and VRP (was: Bootstrap failure on trunk: x86_64-linux-gnu)

[Laurent GUERBY]

Ok this test is checking a corner case of the language, namely
non power of two modular types.

It looks like this one needs overflow checking to pass (-gnato):

$ gnatmake -f -I../../../support/ c460008.adb
gcc -c -I../../../support/ c460008.adb
gcc -c -I./ -I../../../support/ -I- /home/guerby/work/gcc/build/build-head-20060301T130355/gcc/testsuite/ada/acats/support/report.adb
gnatbind -aO./ -I../../../support/ -I- -x c460008.ali
gnatlink c460008.ali
$ ./c460008

,.,. C460008 ACATS 2.5 06-03-02 00:28:43
---- C460008 Check that conversion to a modular type raises
                Constraint_Error when the operand value is outside the
                base range of the modular type.
   * C460008 Fix expected Constraint_Error D2S Dynamic, Negative.
   - C460008 Value of 251 not properly converted.
   * C460008 Fix expected Constraint_Error D2S Static,  Over_Mod.
   - C460008 Value of 204 not properly converted.
   * C460008 Fix expected Constraint_Error D28 Static, Negative.
   - C460008 Value of 255 not properly converted.
   * C460008 Fix expected Constraint_Error D28 Static,  At_Mod.
   - C460008 Value of 0 not properly converted.
   * C460008 Fix expected Constraint_Error D28 Dynamic, Over_Mod.
   - C460008 Value of 209 not properly converted.
**** C460008 FAILED ****************************.

$ gnatmake -f -gnato -I../../../support/ c460008.adb
gcc -c -gnato -I../../../support/ c460008.adb
gcc -c -I./ -gnato -I../../../support/ -I- /home/guerby/work/gcc/build/build-head-20060301T130355/gcc/testsuite/ada/acats/support/report.adb
gnatbind -aO./ -I../../../support/ -I- -x c460008.ali
gnatlink c460008.ali
$ ./c460008

,.,. C460008 ACATS 2.5 06-03-02 00:27:21
---- C460008 Check that conversion to a modular type raises
                Constraint_Error when the operand value is outside the
                base range of the modular type.
==== C460008 PASSED ============================.

I'm rerunning the whole testsuite on x86_64-linux with an edited
gcc/testsuite/ada/acats/run_all.sh that includes -gnato for all tests:

gnatflags="-gnatws -gnato"

We'll see what new ACATS FAIL go away.

Richard, Arnaud, could you check amongst GNAT experts if for such types
(non power of two modulus), it's not worth enabling overflow checks by
default now that we have VRP doing non trivial optimisations? People
using non power of two modulus are not caring for performance anyway, so
having a compliant implementation by default won't harm.

Laurent

On Wed, 2006-03-01 at 15:35 -0700, Jeffrey A Law wrote:
> Here's the next segment in the ongoing saga of VRP vs Ada...
> Not surprisingly we have another case where an object gets a
> value outside of its TYPE_MIN_VALUE/TYPE_MAX_VALUE defined range.
> 
> Investigating the c460008 testsuite failure we have the following
> code for Fixed_To_Short before VRP runs:
> 
> 
> 
> 
>   # BLOCK 4
>   # PRED: 3 (fallthru,exec)
>   D.1294_13 = D.1294_12;
>   D.1309_32 = for_the_value_31 /[rd] 1000000000;
>   D.1310_33 = (UNSIGNED_64) D.1309_32;
>   if (D.1310_33 > 255) goto <L0>; else goto <L1>;
>   # SUCC: 5 (true,exec) 6 (false,exec)
> 
>   # BLOCK 5 
>   # PRED: 4 (true,exec)
> <L0>:;
>   __gnat_rcheck_10 ("c460008.adb", 162);
>   # SUCC: 13 (ab,eh,exec) 18 (ab,eh,exec) 29 (ab,eh,exec)
>   
>   # BLOCK 6
>   # PRED: 4 (false,exec)
> <L1>:;
>   iftmp.78_63 = D.1309_32;
>   iftmp.78_64 = D.1309_32;
>   D.1316_65 = (c460008__unsigned_edge_8) D.1309_32;
>   if (D.1316_65 == 255) goto <L3>; else goto <L4>;
>   # SUCC: 7 (true,exec) 8 (false,exec)
> 
> D.1309_32's type has the range [0x8000000000000000,0x7fffffffffffffff]
> with 64bit precision.
> 
> In block #6 we cast the value of D.1309_32 into a smaller type,
> specifically c460008__unsigned_edge_8 and store the result into
> D.1316_64 which has type c460008__unsigned_edge_8.
> 
> c460008__unsigned_edge_8's range is [ ,254] with 8 bit precision.
> 
> Note carefully that with the range [ ,254] (according to
> TYPE_MIN_VALUE/TYPE_MAX_VALUE) that the test
> 
> if (D.1316_65 == 255)
> 
> Must always be false.  So VRP, as expected, wipes out test
> completely.
> 
> The problem (of course) is D.1316_65 can and does actually hold
> values outside the range [ ,254] at runtime.  For example, it could
> hold the value 255 if D.1309_32 had the value 255, which would occur
> if for_the_value_31 held the value 255000000000.
> 
> Someone with a better knowledge of Ada is going to need to step
> in here, but based on the type information provided by the Ada
> front-end, VRP is doing the right thing here.
> 
> 
> Jeff
> 
> 

Re: ACATS c460008 and VRP

[Robert Dewar]

Laurent GUERBY wrote:
> Ok this test is checking a corner case of the language, namely
> non power of two modular types.
> 
> It looks like this one needs overflow checking to pass (-gnato):

All ACATS tests should be run with -gnatE -gnato

Re: ACATS c460008 and VRP (was: Bootstrap failure on trunk: x86_64-linux-gnu)

[Eric Botcazou]

> Richard, Arnaud, could you check amongst GNAT experts if for such types
> (non power of two modulus), it's not worth enabling overflow checks by
> default now that we have VRP doing non trivial optimisations? People
> using non power of two modulus are not caring for performance anyway, so
> having a compliant implementation by default won't harm.

Changing compilation options to paper over potential bugs is IMHO not the best 
approach, especially if the new options are little used.  And the current 
implementation of -gnato makes it a "heavy" option, not a "light" one.

-- 
Eric Botcazou

Re: ACATS c460008 and VRP

[Robert Dewar]

Eric Botcazou wrote:
>> Richard, Arnaud, could you check amongst GNAT experts if for such types
>> (non power of two modulus), it's not worth enabling overflow checks by
>> default now that we have VRP doing non trivial optimisations? People
>> using non power of two modulus are not caring for performance anyway, so
>> having a compliant implementation by default won't harm.
> 
> Changing compilation options to paper over potential bugs is IMHO not the best 
> approach, especially if the new options are little used.  And the current 
> implementation of -gnato makes it a "heavy" option, not a "light" one.

it's not a bug, -gnato is clearly documented as required in this
case, what makes you think otherwise?

Non power of 2 modular is so rare that using -gnato in this
case seems just fine to me.
> 

Re: ACATS c460008 and VRP

[Eric Botcazou]

> it's not a bug, -gnato is clearly documented as required in this
> case, what makes you think otherwise?

Laurent's message.

Sorry about that, -gnato indeed has always been specified for this test.

-- 
Eric Botcazou

Re: ACATS c460008 and VRP

[Laurent GUERBY]

On Thu, 2006-03-02 at 14:04 +0100, Eric Botcazou wrote:
> > it's not a bug, -gnato is clearly documented as required in this
> > case, what makes you think otherwise?
> 
> Laurent's message.

I missed the fact that the test was already in overflow.lst :)

Laurent

Re: ACATS c460008 and VRP

[Eric Botcazou]

> I missed the fact that the test was already in overflow.lst :)

No worries, so did I. :-)

-- 
Eric Botcazou

Re: ACATS c460008 and VRP (was: Bootstrap failure on trunk: x86_64-linux-gnu)

[Laurent GUERBY]

The test still fails at -O2 -gnato... All the current FAIL
still fail with -gnato, and we even have two additional failures
(unexpected constraint_error):

c45532e 
c45532g

So we have to look carefully at what the front-end does with modular
types here.

Note that cxa4025, cxa4028, cxa4033 are likely to be due to coding
error in the RTS.

Laurent

On Thu, 2006-03-02 at 00:37 +0100, Laurent GUERBY wrote:
> Ok this test is checking a corner case of the language, namely
> non power of two modular types.
> 
> It looks like this one needs overflow checking to pass (-gnato):
> 
> $ gnatmake -f -I../../../support/ c460008.adb
> gcc -c -I../../../support/ c460008.adb
> gcc -c -I./ -I../../../support/ -I- /home/guerby/work/gcc/build/build-head-20060301T130355/gcc/testsuite/ada/acats/support/report.adb
> gnatbind -aO./ -I../../../support/ -I- -x c460008.ali
> gnatlink c460008.ali
> $ ./c460008
> 
> ,.,. C460008 ACATS 2.5 06-03-02 00:28:43
> ---- C460008 Check that conversion to a modular type raises
>                 Constraint_Error when the operand value is outside the
>                 base range of the modular type.
>    * C460008 Fix expected Constraint_Error D2S Dynamic, Negative.
>    - C460008 Value of 251 not properly converted.
>    * C460008 Fix expected Constraint_Error D2S Static,  Over_Mod.
>    - C460008 Value of 204 not properly converted.
>    * C460008 Fix expected Constraint_Error D28 Static, Negative.
>    - C460008 Value of 255 not properly converted.
>    * C460008 Fix expected Constraint_Error D28 Static,  At_Mod.
>    - C460008 Value of 0 not properly converted.
>    * C460008 Fix expected Constraint_Error D28 Dynamic, Over_Mod.
>    - C460008 Value of 209 not properly converted.
> **** C460008 FAILED ****************************.
> 
> $ gnatmake -f -gnato -I../../../support/ c460008.adb
> gcc -c -gnato -I../../../support/ c460008.adb
> gcc -c -I./ -gnato -I../../../support/ -I- /home/guerby/work/gcc/build/build-head-20060301T130355/gcc/testsuite/ada/acats/support/report.adb
> gnatbind -aO./ -I../../../support/ -I- -x c460008.ali
> gnatlink c460008.ali
> $ ./c460008
> 
> ,.,. C460008 ACATS 2.5 06-03-02 00:27:21
> ---- C460008 Check that conversion to a modular type raises
>                 Constraint_Error when the operand value is outside the
>                 base range of the modular type.
> ==== C460008 PASSED ============================.
> 
> I'm rerunning the whole testsuite on x86_64-linux with an edited
> gcc/testsuite/ada/acats/run_all.sh that includes -gnato for all tests:
> 
> gnatflags="-gnatws -gnato"
> 
> We'll see what new ACATS FAIL go away.
> 
> Richard, Arnaud, could you check amongst GNAT experts if for such types
> (non power of two modulus), it's not worth enabling overflow checks by
> default now that we have VRP doing non trivial optimisations? People
> using non power of two modulus are not caring for performance anyway, so
> having a compliant implementation by default won't harm.
> 
> Laurent
> 
> On Wed, 2006-03-01 at 15:35 -0700, Jeffrey A Law wrote:
> > Here's the next segment in the ongoing saga of VRP vs Ada...
> > Not surprisingly we have another case where an object gets a
> > value outside of its TYPE_MIN_VALUE/TYPE_MAX_VALUE defined range.
> > 
> > Investigating the c460008 testsuite failure we have the following
> > code for Fixed_To_Short before VRP runs:
> > 
> > 
> > 
> > 
> >   # BLOCK 4
> >   # PRED: 3 (fallthru,exec)
> >   D.1294_13 = D.1294_12;
> >   D.1309_32 = for_the_value_31 /[rd] 1000000000;
> >   D.1310_33 = (UNSIGNED_64) D.1309_32;
> >   if (D.1310_33 > 255) goto <L0>; else goto <L1>;
> >   # SUCC: 5 (true,exec) 6 (false,exec)
> > 
> >   # BLOCK 5 
> >   # PRED: 4 (true,exec)
> > <L0>:;
> >   __gnat_rcheck_10 ("c460008.adb", 162);
> >   # SUCC: 13 (ab,eh,exec) 18 (ab,eh,exec) 29 (ab,eh,exec)
> >   
> >   # BLOCK 6
> >   # PRED: 4 (false,exec)
> > <L1>:;
> >   iftmp.78_63 = D.1309_32;
> >   iftmp.78_64 = D.1309_32;
> >   D.1316_65 = (c460008__unsigned_edge_8) D.1309_32;
> >   if (D.1316_65 == 255) goto <L3>; else goto <L4>;
> >   # SUCC: 7 (true,exec) 8 (false,exec)
> > 
> > D.1309_32's type has the range [0x8000000000000000,0x7fffffffffffffff]
> > with 64bit precision.
> > 
> > In block #6 we cast the value of D.1309_32 into a smaller type,
> > specifically c460008__unsigned_edge_8 and store the result into
> > D.1316_64 which has type c460008__unsigned_edge_8.
> > 
> > c460008__unsigned_edge_8's range is [ ,254] with 8 bit precision.
> > 
> > Note carefully that with the range [ ,254] (according to
> > TYPE_MIN_VALUE/TYPE_MAX_VALUE) that the test
> > 
> > if (D.1316_65 == 255)
> > 
> > Must always be false.  So VRP, as expected, wipes out test
> > completely.
> > 
> > The problem (of course) is D.1316_65 can and does actually hold
> > values outside the range [ ,254] at runtime.  For example, it could
> > hold the value 255 if D.1309_32 had the value 255, which would occur
> > if for_the_value_31 held the value 255000000000.
> > 
> > Someone with a better knowledge of Ada is going to need to step
> > in here, but based on the type information provided by the Ada
> > front-end, VRP is doing the right thing here.
> > 
> > 
> > Jeff
> > 
> > 

Re: ACATS c460008 and VRP (was: Bootstrap failure on trunk: x86_64-linux-gnu)

[Richard Kenner]

> Richard, Arnaud, could you check amongst GNAT experts if for such types
> (non power of two modulus), it's not worth enabling overflow checks by
> default now that we have VRP doing non trivial optimisations? People
> using non power of two modulus are not caring for performance anyway, so
> having a compliant implementation by default won't harm.

I don't think that either of us are the best people to ask, but my sense
is that it's not a great idea to have the default overflow handling differ
between types.  For one thing, what option would then disable overflow
checking for those types?

-gnato is required for ACATS tests because you need -gnato for RM compliance.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Eric Botcazou]

>   # BLOCK 6
>   # PRED: 4 (false,exec)
> <L1>:;
>   iftmp.78_63 = D.1309_32;
>   iftmp.78_64 = D.1309_32;
>   D.1316_65 = (c460008__unsigned_edge_8) D.1309_32;
>   if (D.1316_65 == 255) goto <L3>; else goto <L4>;
>   # SUCC: 7 (true,exec) 8 (false,exec)
> [...]
> The problem (of course) is D.1316_65 can and does actually hold
> values outside the range [ ,254] at runtime.  For example, it could
> hold the value 255 if D.1309_32 had the value 255, which would occur
> if for_the_value_31 held the value 255000000000.
>
> Someone with a better knowledge of Ada is going to need to step
> in here, but based on the type information provided by the Ada
> front-end, VRP is doing the right thing here.

Yes, I think we have a problem in Gigi, namely convert_with_check:

Breakpoint 5, convert_with_check (gnat_type=2517, gnu_expr=0x5572c45c,
    overflowp=1 '\001', rangep=1 '\001', truncatep=0 '\0')
    at /home/eric/svn/gcc/gcc/ada/trans.c:5322
5322      tree gnu_type = get_unpadded_type (gnat_type);
5323      tree gnu_in_type = TREE_TYPE (gnu_expr);
5324      tree gnu_in_basetype = get_base_type (gnu_in_type);
5325      tree gnu_base_type = get_base_type (gnu_type);
5326      tree gnu_ada_base_type = get_ada_base_type (gnu_type);
5327      tree gnu_result = gnu_expr;

(gdb) p debug_tree(gnu_type)
 <integer_type 0x55723958 c460008__fixed_to_shortGP1192__target
    type <integer_type 0x55723678 c460008__unsigned_edge_8
        type <integer_type 0x5572361c c460008__unsigned_edge_8___UMT public 
unsigned type_1 QI

(gdb) p debug_tree(gnu_base_type)
 <integer_type 0x5572361c c460008__unsigned_edge_8___UMT public unsigned 
type_1QI

(gdb) p debug_tree(gnu_ada_base_type)
 <integer_type 0x55723678 c460008__unsigned_edge_8
    type <integer_type 0x5572361c c460008__unsigned_edge_8___UMT public 
unsigned type_1 QI

5482        gnu_result = convert (gnu_ada_base_type, gnu_result);
5488      if (rangep
5491        gnu_result = emit_range_check (gnu_result, gnat_type);
5493      return convert (gnu_type, gnu_result);

We convert to gnu_ada_base_type before emitting the check using gnu_base_type.

If you slightly thwart the constant folder, the t.gimple output looks like:

            D.756 = for_the_value /[rd] 1000000000;
            D.757 = (UNSIGNED_64) D.756;
            if (D.757 > 255)
              {
                __gnat_rcheck_10 ("c460008.adb", 35);
                iftmp.5 = for_the_value /[rd] 1000000000;
              }
            else
              {
                iftmp.5 = for_the_value /[rd] 1000000000;
              }
            iftmp.6 = iftmp.5;
            if (0)
              {
                goto <D760>;
              }
            else
              {
                
              }
            D.763 = (c460008__unsigned_edge_8) iftmp.6;
            D.764 = (c460008__unsigned_edge_8___UMT) D.763;
            if (D.764 > 254)
              {
                goto <D760>;
              }
            else
              {
                goto <D761>;
              }
            <D760>:;
            __gnat_rcheck_12 ("c460008.adb", 35);

The problematic line is

            D.763 = (c460008__unsigned_edge_8) iftmp.6;


Excerpt from utils2.c:

/* Likewise, but only return types known to the Ada source.  */
tree
get_ada_base_type (tree type)
{
  while (TREE_TYPE (type)
	 && (TREE_CODE (type) == INTEGER_TYPE
	     || TREE_CODE (type) == REAL_TYPE)
	 && !TYPE_EXTRA_SUBTYPE_P (type))
    type = TREE_TYPE (type);

  return type;
}

And ada-tree.h:

/* Nonzero in an arithmetic subtype if this is a subtype not known to the
   front-end.  */
#define TYPE_EXTRA_SUBTYPE_P(NODE) TYPE_LANG_FLAG_2 (NODE)

c460008__unsigned_edge_8 has the TYPE_EXTRA_SUBTYPE_P flag set.

-- 
Eric Botcazou

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Eric Botcazou]

> Excerpt from utils2.c:
>
> /* Likewise, but only return types known to the Ada source.  */
> tree
> get_ada_base_type (tree type)
> {
>   while (TREE_TYPE (type)
> 	 && (TREE_CODE (type) == INTEGER_TYPE
>
> 	     || TREE_CODE (type) == REAL_TYPE)
>
> 	 && !TYPE_EXTRA_SUBTYPE_P (type))
>     type = TREE_TYPE (type);
>
>   return type;
> }
>
> And ada-tree.h:
>
> /* Nonzero in an arithmetic subtype if this is a subtype not known to the
>    front-end.  */
> #define TYPE_EXTRA_SUBTYPE_P(NODE) TYPE_LANG_FLAG_2 (NODE)
>
> c460008__unsigned_edge_8 has the TYPE_EXTRA_SUBTYPE_P flag set.

Which is of course a bit confusing because get_ada_base_type precisely returns 
the first subtype "not known to the front-end"...

-- 
Eric Botcazou

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Thu, 2006-03-02 at 14:05 +0100, Eric Botcazou wrote:
> >   # BLOCK 6
> >   # PRED: 4 (false,exec)
> > <L1>:;
> >   iftmp.78_63 = D.1309_32;
> >   iftmp.78_64 = D.1309_32;
> >   D.1316_65 = (c460008__unsigned_edge_8) D.1309_32;
> >   if (D.1316_65 == 255) goto <L3>; else goto <L4>;
> >   # SUCC: 7 (true,exec) 8 (false,exec)
> > [...]
> > The problem (of course) is D.1316_65 can and does actually hold
> > values outside the range [ ,254] at runtime.  For example, it could
> > hold the value 255 if D.1309_32 had the value 255, which would occur
> > if for_the_value_31 held the value 255000000000.
> >
> > Someone with a better knowledge of Ada is going to need to step
> > in here, but based on the type information provided by the Ada
> > front-end, VRP is doing the right thing here.
> 
> Yes, I think we have a problem in Gigi, namely convert_with_check:
[ ... ]
Just to be 100% clear, I'm leaving this one in the hands of the
Ada maintainers.  I'm not qualified to fix it.  Once the Ada
maintainers have this issue fixed, I'll re-run the Ada testsuite
and attack the next regression introduced by the VRP changes
(if any are left). 

We're also still need the uintp fix installed.  I'm not qualified
to say if Kenner's fix is correct or not, thus I'm not comfortable
checking in that change.

jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Eric Botcazou]

> Just to be 100% clear, I'm leaving this one in the hands of the
> Ada maintainers.  I'm not qualified to fix it.  Once the Ada
> maintainers have this issue fixed, I'll re-run the Ada testsuite
> and attack the next regression introduced by the VRP changes
> (if any are left).

Sure.  My message was intended to confirm that the problem really is Ada FE's 
and expose the gory details.

> We're also still need the uintp fix installed.  I'm not qualified
> to say if Kenner's fix is correct or not, thus I'm not comfortable
> checking in that change.

Right, we need to fix it ASAP because a testsuite hang on x86 is pretty much a 
show stopper.  Richard, could you please install the change?

-- 
Eric Botcazou

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Sebastian Pop]

Jeffrey A Law wrote:
> I wouldn't have a problem with non-canonical bounds if there were
> no way to get a value into an object which is outside the 
> bounds.  But if we can get values into the object which are outside
> those bounds, then either the bounds are incorrect or the program
> is invalid.  
> 

I would classify this as a gimplification bug, as the starting program
is correct, but the GIMPLE form is not.  GIMPLE was introduced for
reducing the complexity of the specific of each language, so I think
that the types should also be translated to a canonical form.

Sebastian

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Diego Novillo]

Eric Botcazou wrote:

> This problem was already raised when Diego contributed the VRP pass and Diego 
> ajusted it to cope with Ada.  AFAIK Ada and VRP work fine on the 4.1 branch.
> 
Which doesn't mean that Ada is DTRT.  On the contrary, Ada ought to be
fixed.  It's an ugly hack in extract_range_from_assert:

  /* Special handling for integral types with super-types.  Some FEs
     construct integral types derived from other types and restrict
     the range of values these new types may take.

     It may happen that LIMIT is actually smaller than TYPE's minimum
     value.  For instance, the Ada FE is generating code like this
     during bootstrap:

            D.1480_32 = nam_30 - 300000361;
            if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
            <L112>:;
            D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;

    All the names are of type types__name_id___XDLU_300000000__399999999
     which has min == 300000000 and max == 399999999.  This means that
     the ASSERT_EXPR would try to create the range [3000000, 1] which
     is invalid.

     The fact that the type specifies MIN and MAX values does not
     automatically mean that every variable of that type will always
     be within that range, so the predicate may well be true at run
     time.  If we had symbolic -INF and +INF values, we could
     represent this range, but we currently represent -INF and +INF
     using the type's min and max values.

     So, the only sensible thing we can do for now is set the
     resulting range to VR_VARYING.  TODO, would having symbolic -INF
     and +INF values be worth the trouble?  */


BTW, the answer to that 'TODO' question is 'no'.  I briefly toyed with
that idea, but it is much more convenient to use TYPE_MAX_VALUE and
TYPE_MIN_VALUE.  Otherwise, arithmetic on +INF and -INF becomes unpleasant.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Guenther]

On 2/28/06, Diego Novillo <dnovillo@redhat.com> wrote:
> Eric Botcazou wrote:
>
> > This problem was already raised when Diego contributed the VRP pass and Diego
> > ajusted it to cope with Ada.  AFAIK Ada and VRP work fine on the 4.1 branch.
> >
> Which doesn't mean that Ada is DTRT.  On the contrary, Ada ought to be
> fixed.  It's an ugly hack in extract_range_from_assert:
>
>   /* Special handling for integral types with super-types.  Some FEs
>      construct integral types derived from other types and restrict
>      the range of values these new types may take.
>
>      It may happen that LIMIT is actually smaller than TYPE's minimum
>      value.  For instance, the Ada FE is generating code like this
>      during bootstrap:
>
>             D.1480_32 = nam_30 - 300000361;
>             if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
>             <L112>:;
>             D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
>
>     All the names are of type types__name_id___XDLU_300000000__399999999
>      which has min == 300000000 and max == 399999999.  This means that
>      the ASSERT_EXPR would try to create the range [3000000, 1] which
>      is invalid.

My understanding of Ada is that the above is not (or should not be) what
the frontend generates, but

   D.1480_32 = nam_30 - 300000361;

should be carried out in the base type, as should the comparison be.  It would
be interesting to have a testcase that exposes the above behavior and hunt for
the place where things start to go wrong.  So correct should be

  D.xxxx = (base_type)nam_30;
  D.1480_32 = D.xxxx - 300000361;

and D.1480 of type base_type.  Just papering over latent bugs isn't the way to
go here - rather break Ada, so it (or whatever gets it wrong) gets fixed.

Richard.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Eric Botcazou]

> It's an ugly hack in extract_range_from_assert:
>
>   /* Special handling for integral types with super-types.  Some FEs
>      construct integral types derived from other types and restrict
>      the range of values these new types may take.
>
>      It may happen that LIMIT is actually smaller than TYPE's minimum
>      value.  For instance, the Ada FE is generating code like this
>      during bootstrap:
>
>             D.1480_32 = nam_30 - 300000361;
>             if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
>             <L112>:;
>             D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
>
>     All the names are of type types__name_id___XDLU_300000000__399999999
>      which has min == 300000000 and max == 399999999.  This means that
>      the ASSERT_EXPR would try to create the range [3000000, 1] which
>      is invalid.
>
>      The fact that the type specifies MIN and MAX values does not
>      automatically mean that every variable of that type will always
>      be within that range, so the predicate may well be true at run
>      time.  If we had symbolic -INF and +INF values, we could
>      represent this range, but we currently represent -INF and +INF
>      using the type's min and max values.
>
>      So, the only sensible thing we can do for now is set the
>      resulting range to VR_VARYING.  TODO, would having symbolic -INF
>      and +INF values be worth the trouble?  */

I think we would need to clarify that, because I'm not sure the Ada front-end 
directly generates:

             D.1480_32 = nam_30 - 300000361;
             if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
             <L112>:;
             D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;

-- 
Eric Botcazou

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Tue, 2006-02-28 at 18:50 +0100, Eric Botcazou wrote:
> > It's an ugly hack in extract_range_from_assert:
> >
> >   /* Special handling for integral types with super-types.  Some FEs
> >      construct integral types derived from other types and restrict
> >      the range of values these new types may take.
> >
> >      It may happen that LIMIT is actually smaller than TYPE's minimum
> >      value.  For instance, the Ada FE is generating code like this
> >      during bootstrap:
> >
> >             D.1480_32 = nam_30 - 300000361;
> >             if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
> >             <L112>:;
> >             D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
> >
> >     All the names are of type types__name_id___XDLU_300000000__399999999
> >      which has min == 300000000 and max == 399999999.  This means that
> >      the ASSERT_EXPR would try to create the range [3000000, 1] which
> >      is invalid.
> >
> >      The fact that the type specifies MIN and MAX values does not
> >      automatically mean that every variable of that type will always
> >      be within that range, so the predicate may well be true at run
> >      time.  If we had symbolic -INF and +INF values, we could
> >      represent this range, but we currently represent -INF and +INF
> >      using the type's min and max values.
> >
> >      So, the only sensible thing we can do for now is set the
> >      resulting range to VR_VARYING.  TODO, would having symbolic -INF
> >      and +INF values be worth the trouble?  */
> 
> I think we would need to clarify that, because I'm not sure the Ada front-end 
> directly generates:
> 
>              D.1480_32 = nam_30 - 300000361;
>              if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
>              <L112>:;
>              D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
This one is probably worth tracking down -- if the Ada front-end
actually created this kind of code, then it would be a bug.  Similarly
if we originally had the proper typecasts and they were later
eliminated, then that would be a bug in the optimizers.

Diego -- do you recall what code actually triggered this problem?
jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Diego Novillo]

Jeffrey A Law wrote:

> Diego -- do you recall what code actually triggered this problem?
>
Not sure, exactly.

However, in figuring out what this code was working around, I remembered
this thread from Kenner where he fixed this particular FE bug:
http://gcc.gnu.org/ml/gcc-patches/2005-11/msg01347.html

In that same thread I found a follow up from me promising to remove this
code for 4.2.  I, of course, forgot.  *blush*.

So, it seems that we don't actually need this ugliness anymore.  I will
test a patch removing this code now.  Should I expect Ada to work with
mainline, atm?


Thanks.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Tue, 2006-02-28 at 17:51 -0500, Diego Novillo wrote:
> Jeffrey A Law wrote:
> 
> > Diego -- do you recall what code actually triggered this problem?
> >
> Not sure, exactly.
> 
> However, in figuring out what this code was working around, I remembered
> this thread from Kenner where he fixed this particular FE bug:
> http://gcc.gnu.org/ml/gcc-patches/2005-11/msg01347.html
> 
> In that same thread I found a follow up from me promising to remove this
> code for 4.2.  I, of course, forgot.  *blush*.
Opps :-)


> So, it seems that we don't actually need this ugliness anymore.  I will
> test a patch removing this code now.  Should I expect Ada to work with
> mainline, atm?
You'll get a hang in the Ada testsuite as well as a handful of 
failures.   But it should bootstrap and you can get meaningful
before/after testresults as long as you kill gnat1 when it hands
on the one test (don't remember its name offhand).

jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Andrew Haley]

Andrew Pinski writes:
 > 
 > On Feb 19, 2006, at 12:09 PM, Andrew Haley wrote:
 > 
 > > When building a-textio in libada, today's gcc build fails when memory
 > > is exhausted.
 > 
 > This has already been reported as PR 26348 and it looks like a bug
 > in the Ada front-end.

Oh right, thanks.  Was this mentioned on the list anywhere?

Andrew.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Andreas Schwab]

Andrew Haley <aph@redhat.com> writes:

> When building a-textio in libada, today's gcc build fails when memory
> is exhausted.

This is PR26348.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Kenner]

    "Second, for a given integer type (such as
    natural___XDLU_0_2147483647), the type for the nodes in TYPE_MIN_VALUE
    and TYPE_MAX_VALUE really should be a natural___XDLU_0_2147483647.
    ie, the type of an integer constant should be the same as the type of
    its min/max values."

No, the type of the bounds of a subtype should be the *base type*.  That's
how the tree has always looked, as far back as  I can remember.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Kenner]

    Basically with the way Ada's setting of TYPE_MIN_VALUE/TYPE_MAX_VALUE
    effectively makes them useless as we can not rely on them to 
    actually reflect the set of values allowed in an object.

As we've all told you numerous times before, TYPE_MIN_VALUE/TYPE_MAX_VALUE
are meant *precisely* to refect the set of valid values in an object.
("valid" is a technical term in Ada, while "allowed" is vague, so I'm
using the former term).

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Kenner]

    Which doesn't mean that Ada is DTRT.  On the contrary, Ada ought to be
    fixed.  It's an ugly hack in extract_range_from_assert:

It wasn't a bug in the Ada front end, but in fold, which was long-ago
fixed.  I thought this was removed a long time ago?

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Kenner]

    We have a loop with the following termination code in uintp.num_bits

This sure looks like a bug in Num_Bits to me, not in the compilation
of the front-end.

The relevant code is:

   function Num_Bits (Input : Uint) return Nat is
      Bits : Nat;
      Num  : Nat;

   begin
      if UI_Is_In_Int_Range (Input) then
         Num := abs (UI_To_Int (Input));
         Bits := 0;

This code only works for one-complement machines, since it assumes a
symmetric range for Int.  It breaks when UI_To_Int returns Integer'First, as
it did in this case.  When it does, the abs produces an erroneous result
(since checking is disabled).  So it almost doesn't matter what it puts into
Num (but it actually puts in an out-of-range value there too).

Robert, what's the proper fix here?

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Duncan Sands]

> This code only works for one-complement machines, since it assumes a
> symmetric range for Int.  It breaks when UI_To_Int returns Integer'First, as
> it did in this case.  When it does, the abs produces an erroneous result
> (since checking is disabled).  So it almost doesn't matter what it puts into
> Num (but it actually puts in an out-of-range value there too).

Is there a simple way to have the Ada runtime (+ compiler) be built with checking
enabled when bootstrapping?

Thanks a lot,

Duncan.

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Kenner]

    So this is likely to be a FE Ada coding bug and not a FE/ME/BE interface
    issue, thanks for spotting this!

Indeed, having looked a bit closer at Uintp, I think this is the right fix.
Robert, please confirm.

*** uintp.adb	12 Sep 2003 21:50:56 -0000	1.80
--- uintp.adb	1 Mar 2006 13:08:06 -0000
*************** package body Uintp is
*** 591,595 ****
  
     begin
!       if UI_Is_In_Int_Range (Input) then
           Num := abs (UI_To_Int (Input));
           Bits := 0;
--- 591,598 ----
  
     begin
!       if Input = Uint_Int_First then
!          Num := Int'Size;
! 
!       elsif UI_Is_In_Int_Range (Input) then
           Num := abs (UI_To_Int (Input));
           Bits := 0;

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Kenner]

    So this is likely to be a FE Ada coding bug and not a FE/ME/BE interface
    issue, thanks for spotting this!

Sorry, my last suggestion is clearly wrong.  I think is right.

*** uintp.adb	12 Sep 2003 21:50:56 -0000	1.80
--- uintp.adb	1 Mar 2006 13:16:21 -0000
*************** package body Uintp is
*** 591,595 ****
  
     begin
!       if UI_Is_In_Int_Range (Input) then
           Num := abs (UI_To_Int (Input));
           Bits := 0;
--- 591,598 ----
  
     begin
!       if Input = Uint_Int_First then
!          return Int'Size;
! 
!       elsif UI_Is_In_Int_Range (Input) then
           Num := abs (UI_To_Int (Input));
           Bits := 0;

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Jeffrey A Law]

On Wed, 2006-03-01 at 08:24 -0500, Richard Kenner wrote:
>     So this is likely to be a FE Ada coding bug and not a FE/ME/BE interface
>     issue, thanks for spotting this!
> 
> Sorry, my last suggestion is clearly wrong.  I think is right.
> 
> *** uintp.adb	12 Sep 2003 21:50:56 -0000	1.80
> --- uintp.adb	1 Mar 2006 13:16:21 -0000
> *************** package body Uintp is
> *** 591,595 ****
>   
>      begin
> !       if UI_Is_In_Int_Range (Input) then
>            Num := abs (UI_To_Int (Input));
>            Bits := 0;
> --- 591,598 ----
>   
>      begin
> !       if Input = Uint_Int_First then
> !          return Int'Size;
> ! 
> !       elsif UI_Is_In_Int_Range (Input) then
>            Num := abs (UI_To_Int (Input));
>            Bits := 0;
It certainly fixes the testsuite hang.  If it's the correct
fix, then can you please make sure it gets installed.

Thanks,
Jeff

Re: Bootstrap failure on trunk: x86_64-linux-gnu

[Richard Kenner]

    Just to be 100% clear, I'm leaving this one in the hands of the
    Ada maintainers.  I'm not qualified to fix it.  

Right.

    We're also still need the uintp fix installed.  I'm not qualified to
    say if Kenner's fix is correct or not, thus I'm not comfortable
    checking in that change.

Robert was out of the country for the last few days.  I expect him to get
back to me on it today.