Bug 30911 - VRP fails to eliminate range checks in Ada code
VRP fails to eliminate range checks in Ada code
Status: RESOLVED WONTFIX
Product: gcc
Classification: Unclassified
Component: tree-optimization
4.3.0
: P3 enhancement
: ---
Assigned To: Not yet assigned to anyone
:
Depends on: 26797 30317 31023
Blocks:
  Show dependency treegraph
 
Reported: 2007-02-21 13:56 UTC by Duncan Sands
Modified: 2009-11-17 19:00 UTC (History)
4 users (show)

See Also:
Host: i486-linux-gnu
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2007-02-22 18:00:53


Attachments
patch fixing the problem (4.11 KB, patch)
2007-02-23 11:37 UTC, Richard Biener
Details | Diff
patch (9.11 KB, patch)
2007-02-23 20:18 UTC, Richard Biener
Details | Diff
patch (9.11 KB, patch)
2007-02-23 22:40 UTC, Richard Biener
Details | Diff
patch for comment #47 (2.33 KB, text/plain)
2008-03-28 22:14 UTC, Richard Biener
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Duncan Sands 2007-02-21 13:56:54 UTC
All of the range checks can in theory be eliminated, except
for the first one (a call to __gnat_rcheck_04, unlike the
others which are calls to __gnat_rcheck_04), but they are
not:

$ gcc -c -O2 -fdump-tree-all j.ads
$ grep __gnat_rcheck_12 j.ads.118t.final_cleanup
  __gnat_rcheck_12 ("join_equal.adb", 14);
  __gnat_rcheck_12 ("join_equal.adb", 14);
  __gnat_rcheck_12 ("join_equal.adb", 29);
  __gnat_rcheck_12 ("join_equal.adb", 29);
  __gnat_rcheck_12 ("join_equal.adb", 39);
  __gnat_rcheck_12 ("join_equal.adb", 39);
Comment 1 Duncan Sands 2007-02-21 15:17:50 UTC
I've tried and failed to attach the source code (bugzilla problem), so here it
is inline (you can extract it using gnatchop):

with Join_Equal;
with JS;
procedure J is new Join_Equal (
  Source_Type => JS.S,
  Equal       => JS.E,
  Target_Type => JS.T,
  Move        => JS.M
);

package JS is
   type S is range 0 .. 100;
   type T is range 10 .. 20;
   function E (L, R : S) return Boolean;
   procedure M (
     First, Last : S;
     Destination : T
   );
end JS;

generic
   type Source_Type is (<>);
   with function Equal (Left, Right : Source_Type) return Boolean;
   type Target_Type is (<>);
   with procedure Move (
     First, Last : Source_Type;
     Destination : Target_Type
   );
procedure Join_Equal (
  Source_First : in     Source_Type;
  Source_Last  : in out Source_Type; -- returns last read
  Target_First : in     Target_Type;
  Target_Last  :    out Target_Type  -- returns last written
);
pragma Pure (Join_Equal);

procedure Join_Equal (
  Source_First : in     Source_Type;
  Source_Last  : in out Source_Type;
  Target_First : in     Target_Type;
  Target_Last  :    out Target_Type
) is
   Source : Source_Type := Source_First;
   Target : Target_Type := Target_First;
begin
   if Source_Last < Source_First then
      if Target_First = Target_Type'First then
         raise Constraint_Error;
      end if;
      Target_Last := Target_Type'Pred (Target_First);
      return;
   end if;
   loop
      declare
         Start : constant Source_Type := Source;
         Prev  : Source_Type := Source;
      begin
         loop
            if Source = Source_Last then
               Move (Start, Source, Target);
               Target_Last := Target;
               return;
            end if;
            Source := Source_Type'Succ (Source);
            exit when not Equal (Prev, Source);
            Prev := Source;
         end loop;
         Move (Start, Prev, Target);
         if Target = Target_Type'Last then
            Source_Last := Prev;
            Target_Last := Target;
            return;
         end if;
         Target := Target_Type'Succ (Target);
      end;
   end loop;
end Join_Equal;
Comment 2 Steven Bosscher 2007-02-21 17:55:42 UTC
Bonus points if you can reduce this to a C test case ;-)
Starting with the gimple dumps, this is usually not hard to do.
Comment 3 Eric Botcazou 2007-02-21 18:01:17 UTC
> Bonus points if you can reduce this to a C test case ;-)
> Starting with the gimple dumps, this is usually not hard to do.

Not everything is in the dumps, in particular you don't have subtypes in C.
Comment 4 Richard Biener 2007-02-22 17:04:33 UTC
Can you walk me through some of the checks and why they can be removed?  I see
(.004.gimple dump):

    source = source_first;
    target = target_first;
    source_last.0 = (js__TsB) source_last;
    source_first.1 = (js__TsB) source_first;
    if (source_last.0 < source_first.1)
      {
        if (target_first == 10)
          {
            __gnat_rcheck_04 ("join_equal.adb", 13);
          }
        else
          {

          }
        if (target_first == 128)
          {
            __gnat_rcheck_12 ("join_equal.adb", 15);
            iftmp.2 = target_first;
          }
        else
          {
            iftmp.2 = target_first;
          }
        iftmp.3 = iftmp.2;
        iftmp.4 = (js__TtB) iftmp.3;
        if (iftmp.4 <= 10)
          {
            goto <D1039>;
          }
        else
          {

          }
        iftmp.4 = (js__TtB) iftmp.3;
        if (iftmp.4 > 21)
          {
            goto <D1039>;
          }
        else
          {
            goto <D1040>;
          }
        <D1039>:;
        __gnat_rcheck_12 ("join_equal.adb", 15);
        <D1040>:;
        if (target_first == 128)
          {
            __gnat_rcheck_12 ("join_equal.adb", 15);
            iftmp.5 = target_first;
          }
        else
          {
            iftmp.5 = target_first;
          }
        iftmp.6 = iftmp.5;
        iftmp.7 = (js__TtB) iftmp.6;
        D.1047 = iftmp.7 + -1;
        target_last = (j__target_type___XDLU_10__20) D.1047;
        goto <D1016>;

I assume all of the above is gimplified from just

   if Source_Last < Source_First then
      if Target_First = Target_Type'First then
         raise Constraint_Error;
      end if;
      Target_Last := Target_Type'Pred (Target_First);
      return;

?  So in essence VRP should somehow be able to see that
Target_Type'Pred (Target_First) cannot be out of bounds because Target_First
is not Target_Type'First, correct?  But given the gimplified form above
we also need to prove Target_First is not 128 (where does that come from?
It looks like __gnat_rcheck_12 is not a noreturn function?).  We also
need to prove that (js__TtB) Target_First is > 10 (that looks doable from
the != 10 range we can extract from the first range check).  But where
does the check against 21 come from?  The 2nd check for 128 looks redundant
and indeed we remove it in VRP1.

I need to look closer at what js__TtB actually is looking like, but this
is at least a useful testcase.

Thanks.
Comment 5 Eric Botcazou 2007-02-22 17:33:29 UTC
Do not work too hard on this, there is code in the AdaCore tree to disable
VRP in more cases, lest language-mandated checks are erroneously removed.
Comment 6 Duncan Sands 2007-02-22 17:41:40 UTC
> Bonus points if you can reduce this to a C test case ;-)
> Starting with the gimple dumps, this is usually not hard to do.

It can't be reduced because it relies on integer types with restricted ranges, i.e. TYPE_MIN_VALUE and/or TYPE_MAX_VALUE different from what you'd get from TYPE_PRECISION and the signedness.  Adding some kind of attribute to C so that you can create similar types there would be helpful.
Comment 7 Eric Botcazou 2007-02-22 18:00:53 UTC
> Do not work too hard on this, there is code in the AdaCore tree to disable
> VRP in more cases, lest language-mandated checks are erroneously removed.

For example PR ada/26797.
Comment 8 Duncan Sands 2007-02-22 18:14:39 UTC
> Can you walk me through some of the checks and why they can be removed?  I see
> (.004.gimple dump):
...
> I assume all of the above is gimplified from just
> 
>    if Source_Last < Source_First then
>       if Target_First = Target_Type'First then
>          raise Constraint_Error;
>       end if;
>       Target_Last := Target_Type'Pred (Target_First);
>       return;

Yes.  Amazing, isn't it ;)  The important thing to keep in mind is that
all "target" variables must be in the range 10..20, and all "source" variables in the range 0..100 (see the definitions
type S is range 0 .. 100; <-- S corresponds to Source_Type in Join_Equal
type T is range 10 .. 20; <-- T corresponds to Target_Type in Join_Equal
).
What does "must be in the range" mean?  Firstly, the program behaviour is undefined if a variable is outside its range.  This is the same as for signed overflow.  It's just that here overflow starts at 100 or at 20, not at INT_MAX!  Secondly, the language requires the compiler to check at the point of the call that the values passed to the Join_Equal subprogram are in the right ranges.  If not, an exception is raised.  Likewise, at points where you do arithmetic like adding or subtracting 1, the compiler inserts checks that the result will not go out of range.  If not, an exception is raised.  That's where all this code is coming from.

Anyway, the practical upshot is that VRP is allowed to assume that source_first and source_last have values in the range 0..100, and target_first and target_last have values in the range 10..20.  Using this, it should be able to eliminate all of the compiler inserted range checking.

> ?  So in essence VRP should somehow be able to see that
> Target_Type'Pred (Target_First) cannot be out of bounds because Target_First
> is not Target_Type'First, correct?

Exactly.

> But given the gimplified form above
> we also need to prove Target_First is not 128 (where does that come from?

It cannot be 128 because it is in the range 10..20.  As to why the compiler inserted 128, good question!  Probably it has placed target in an unsigned variable with 8-bit precision, and is checking that some computation it is about to do in that variable will not overflow.

> It looks like __gnat_rcheck_12 is not a noreturn function?).

It is a noreturn function.  It just raises a language defined exception.

> We also
> need to prove that (js__TtB) Target_First is > 10 (that looks doable from
> the != 10 range we can extract from the first range check).  But where
> does the check against 21 come from?

It seems to be another pointless check the compiler has inserted.  It can be removed because iftmp.4 is in the range 11..20.

> The 2nd check for 128 looks redundant
> and indeed we remove it in VRP1.

Yes.

> I need to look closer at what js__TtB actually is looking like, but this
> is at least a useful testcase.

Probably this is the "base type" for the type js__T (aka JS.T) in the original source.  The idea of a base type is that that's the type that has the full range you would expect from the precision.  Most likely type T, with range 10..20, has been assigned 8 bit precision by the compiler, and has a base type js__TtB with range -128..127, i.e. a normal C signed byte.  The compiler systematically converts to the base type before doing arithmetic.  After the arithmetic, it checks whether the result is in the range of the original type (10..20).  If not, it raises an exception (__gnat_rcheck_12), and otherwise it it put the result back in the type T variable.
Comment 9 Duncan Sands 2007-02-22 18:18:05 UTC
(In reply to comment #7)
> > Do not work too hard on this, there is code in the AdaCore tree to disable
> > VRP in more cases, lest language-mandated checks are erroneously removed.
> 
> For example PR ada/26797.

That is quite a different issue.  Eliminating the checks in this example is perfectly valid and useful.  I certainly hope that you are not planning to turn off VRP permanently, since it is particularly important for Ada.  I can understand that you have to be careful with validity checks (which is what VIEW_CONVERT_EXPR is for) but that's orthogonal to this PR.
Comment 10 Eric Botcazou 2007-02-22 18:19:38 UTC
Please do not overwrite changes, thanks.
Comment 11 Duncan Sands 2007-02-22 22:54:27 UTC
> Please do not overwrite changes, thanks.

Sorry about that - it wasn't on purpose: your comment
and mine collided.  I actually checked the two bugs
after getting the message that I'd manage to wipe out
your change, and the relationship between 26797 and
30911 that you'd set up still seemed to be there.
So I guess bugzilla is too subtle for me...
Comment 12 Eric Botcazou 2007-02-23 05:50:47 UTC
> Sorry about that - it wasn't on purpose: your comment
> and mine collided.  I actually checked the two bugs
> after getting the message that I'd manage to wipe out
> your change, and the relationship between 26797 and
> 30911 that you'd set up still seemed to be there.

I added it again.  Note that you had received a warning before overwriting.
Comment 13 Richard Biener 2007-02-23 09:22:14 UTC
In reply to comment #8

To understand the issues a little bit more -- are there any requirements on
overflow behavior of the _base_ type?  Suppose a type T with range -100..120
has indeed be assigned a signed char with precision 8 (and so range -128..127).
If we now do arithmetic like (to add two Ts)

  T foo(T t1, T t2)
  {
    signed char t1_base = (signed char)t1;
    signed char t2_base = (signed char)t2;
    signed char res_base = t1_base + t2_base;
    if (res_base < 10 || res_base > 120)
      abort ();
    return (T)res_base;
  }

is it ok to not raise a constraint error if I happen to add 100 and 100 which
wraps on the machine in signed char precision back to a valid value inside
the range of T?
Comment 14 baldrick@free.fr 2007-02-23 09:39:30 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

On Friday 23 February 2007 06:50:48 ebotcazou at gcc dot gnu dot org wrote:
> 
> ------- Comment #12 from ebotcazou at gcc dot gnu dot org  2007-02-23 05:50 -------
> > Sorry about that - it wasn't on purpose: your comment
> > and mine collided.  I actually checked the two bugs
> > after getting the message that I'd manage to wipe out
> > your change, and the relationship between 26797 and
> > 30911 that you'd set up still seemed to be there.
> 
> I added it again.  Note that you had received a warning before overwriting.

Yes, but since I hadn't made any changes except adding a comment,
I didn't see why this should cause any problems.  The fact that
it did cause problems seems like a bugzilla bug to me.  Anyway,
now that I know how this works I will be more careful next time :-/

Ciao,

D.
Comment 15 baldrick@free.fr 2007-02-23 10:03:42 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

On Friday 23 February 2007 10:22:15 rguenth at gcc dot gnu dot org wrote:
> 
> ------- Comment #13 from rguenth at gcc dot gnu dot org  2007-02-23 09:22 -------
> In reply to comment #8
> 
> To understand the issues a little bit more -- are there any requirements on
> overflow behavior of the _base_ type?  Suppose a type T with range -100..120
> has indeed be assigned a signed char with precision 8 (and so range -128..127).
> If we now do arithmetic like (to add two Ts)
> 
>   T foo(T t1, T t2)
>   {
>     signed char t1_base = (signed char)t1;
>     signed char t2_base = (signed char)t2;
>     signed char res_base = t1_base + t2_base;
>     if (res_base < 10 || res_base > 120)
>       abort ();
>     return (T)res_base;
>   }
> 
> is it ok to not raise a constraint error if I happen to add 100 and 100 which
> wraps on the machine in signed char precision back to a valid value inside
> the range of T?

The Ada language requires the compiler to insert checks that arithmetic in
the base type does not overflow, and to raise an exception if it does.  To
be more precise, it is allowed either to raise an exception or return the
mathematically correct result (i.e. what you would get if the range of your
base type was infinite).  For example, calculating (x + INT_MAX) - INT_MAX
is allowed to return x or raise an exception.  The Ada f-e doesn't insert
the required checks by default - you have to give it the -gnato switch if
you want full language conformance (it doesn't do it by default because it
is too expensive; the Ada f-e really wants to use -ftrapv but doesn't because
-ftrapv doesn't work reliably enough, instead it inserts explicit checks).
Thus in standard conformant -gnato mode the problem you describe can never
happen.  What about the default mode, without -gnato?  The language provides
a way of suppressing checks, in this case the check is called Overflow_Check.
Not using -gnato is equivalent to suppressing Overflow_Check everywhere.  The
language standard says "If a given check has been suppressed, and the
corresponding error situation occurs, the execution of the program is erroneous."
Thus you may reasonably assume that the result of signed overflow is undefined.
So you can do what you like here, the same as in C.  I think, as a general rule,
that if you assume arithmetic on base types is the same as in C, then you won't
go wrong.

PS: For unsigned types the situation is different, as in C, namely addition has
wraparound semantics.
Comment 16 Richard Biener 2007-02-23 11:37:37 UTC
Created attachment 13096 [details]
patch fixing the problem

The attached patch removes all checks (from the first half of the testcase).  Not
yet bootstrapped or tested.

There is one appearant problem with the way the Ada frontend sets TYPE_MIN/MAX_VALUE on the integer subtypes -- I expected the min/max values
to be of the type of the subtype, not of the underlying base type.  This
unnecessarily complicates things.
Comment 17 Richard Biener 2007-02-23 11:42:25 UTC
This also depends on PR30317 as we have for example

<L9>:;
  source.4_29 = (js__TsB) source_4;
  R5b_30 = source.4_29 + 1;
  R5b.5_31 = (UNSIGNED_8) R5b_30;
  if (R5b.5_31 > 100) goto <L10>; else goto <L11>;
Comment 18 baldrick@free.fr 2007-02-23 12:36:28 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> The attached patch removes all checks (from the first half of the testcase). 

Thanks for the patch!

> +      Make sure to preserve ~[a, a] (FIXME: why?) and ~[-INF, +INF] though.

Some parts of VRP punt on anti-ranges unless it is of the form ~[a,a], however
turning this into [a+1,TYPE_MAX] should cause no problems, since this is a range
not an anti-range.

> +       && (tree_int_cst_equal (min,TYPE_MIN_VALUE (TREE_TYPE (min)))

Missing space after "min,".

> + 	  fprintf (dump_file, "Canonicalized anit-range to [");

anit-range! :)

Unfortunately bootstrap dies instantly with

In file included from ../../gcc.fsf.master/gcc/fold-const.c:56:
../../gcc.fsf.master/gcc/tree.h: In function ‘VEC_tree_base_length’:
../../gcc.fsf.master/gcc/tree.h:208: internal compiler error: tree check: expected integer_type or enumeral_type or boolean_type or real_type, have pointer_type in fold_comparison, at fold-const.c:8768

Most likely it was a pointer type.  By the way, I guess you're also doing
the folding for floating point types, is that wise?
Comment 19 Richard Biener 2007-02-23 12:41:47 UTC
Yeah, the fold-const.c chunk misses

+   /* We can compare x OP cst based on the value range of the type of
+      x.  */
+   if (TREE_CODE (arg1) == INTEGER_CST
+       && TREE_CODE (arg0) != INTEGER_CST
+       && !POINTER_TYPE_P (TREE_TYPE (arg0))
^^^^ this line

+       && TYPE_MIN_VALUE (TREE_TYPE (arg0))

I don't think I'm folding pointer types, if arg1 is an integer constant
arg0 is of integer type as well.
Comment 20 baldrick@free.fr 2007-02-23 13:04:54 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> !POINTER_TYPE_P 

I'm testing with INTEGRAL_TYPE_P.

By the way, I see a lot a anti-range canonicalization going
on in C code.  A lot of code where u is of an unsigned type
checks whether u!=0.  This now gets turned into the range
[1,INF] which I guess is a good thing.
Comment 21 Richard Biener 2007-02-23 14:05:25 UTC
Yep, INTEGRAL_TYPE_P is better.  the u!=0 case might be why I tried to preserve
~[0,0] for unsigneds... maybe we have some failing testcases with ranges for
range_is_nonnull, which only checks

static inline bool
range_is_nonnull (value_range_t *vr)
{
  return vr->type == VR_ANTI_RANGE
         && integer_zerop (vr->min)
         && integer_zerop (vr->max);
}

but doesn't see that for unsigned it's equivalent to [1, +INF].  I'll adjust
that, too.
Comment 22 Richard Biener 2007-02-23 15:15:34 UTC
Ok, I get lot's of acats failures with the patch, all of the form

RUN a22006d

raised CONSTRAINT_ERROR : a-textio.adb:1339 explicit raise
FAIL:   a22006d

which is from


   procedure Set_Col
     (File : File_Type;
      To   : Positive_Count)
   is
      ch : int;

   begin
      --  Raise Constraint_Error if out of range value. The reason for this
      --  explicit test is that we don't want junk values around, even if
      --  checks are off in the caller.

      if not To'Valid then
         raise Constraint_Error;
      end if;

(so it seems like we have a rts miscompilation or a rts error somewhere)
Comment 23 baldrick@free.fr 2007-02-23 15:40:22 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

>       if not To'Valid then

I'm pretty sure that this is an example of PR26797:
the front-end should generate 'Valid by doing a
VIEW_CONVERT_EXPR of To to its base type, and then
checking whether that is in the right range.  But
what it often does right now is simply check whether
To is in TYPE_MIN_VALUE .. TYPE_MAX_VALUE using an
"if" statement.  Of course VRP eliminates that.  This
is exactly PR26797, and needs to be fixed in the Ada
f-e.

That said, maybe I should explain about 'Valid.  How
can a variable have a value that is not in range?  One
answer is: because it is uninitialized.  Another way
is provided by the language: there is a technique for
assigning from one variable to another without a range
check, called "unchecked conversion".  If the result is
out of range, then the behaviour you get if you use it
is undefined.  Finally, there are some other funky
situations which can be thought of as equivalent to a
use of unchecked conversion.  Anyway, the language
provides exactly one way to check if a variable is in
range: using 'Valid.  So the 'Valid check must stop
the optimizers from optimizing away the check based
on the "known" range.  The technique that seems to
have been agreed on is to use VIEW_CONVERT_EXPR, but
unfortunately the front-end doesn't seem to always use
that right now.

So this is not a problem with your patch as such.
Comment 24 Richard Biener 2007-02-23 15:55:12 UTC
Of course in this case I would have expected VRP or whatever to optimize away

     if not To'Valid then
         raise Constraint_Error;
     end if;

but it looks it is now an unconditional

     raise Constraint_Error;

btw - I failed to manually re-build a file from the rts, what do I need to do this? (I tried with -gnatpg but that just complains in different ways than
without -gnatpg)
Comment 25 baldrick@free.fr 2007-02-23 15:59:28 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

There seems to be an additional C testsuite failure: loadpre1.c

Also, some of the acats failures look interesting, for example
the first one c34004a is showing a real problem.  I will try to
analyze it later.
Comment 26 baldrick@free.fr 2007-02-23 16:01:19 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> Of course in this case I would have expected VRP or whatever to optimize away
> 
>      if not To'Valid then
>          raise Constraint_Error;
>      end if;
> 
> but it looks it is now an unconditional
> 
>      raise Constraint_Error;

Some of the other tests are showing similar behaviour.

> btw - I failed to manually re-build a file from the rts, what do I need to do
> this? (I tried with -gnatpg but that just complains in different ways than
> without -gnatpg)

What does it complain about with -gnatpg?  Without it, it probably complains
that you are not allowed to compile children of package Ada, or something like
that.
Comment 27 Arnaud Charlet 2007-02-23 16:05:07 UTC
BTW, this is not a bug, but a possible enhancement, and a very tricky one at
that, since removing too many checks will hurt much more Ada programmers than
having too many, so let's please be extra careful here.

Arno
Comment 28 Richard Biener 2007-02-23 16:11:13 UTC
Got it compiling now with -gnatpg -- my tree was probably too old and messed up, rebuilding everything helped.  Now we indeed fold "not To'Valid" to 1 ;)  Unfolded 
it looks like


  if (to == 0 || (SIGNED_32) to < 0)
    {
      __gnat_rcheck_04 ("a-textio.adb", 1339);
    }

I'll try to get my hands on what goes wrong, but a small testcase resembling the
above part would be nice to have ;)
Comment 29 baldrick@free.fr 2007-02-23 17:09:35 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> BTW, this is not a bug, but a possible enhancement, and a very tricky one at
> that, since removing too many checks will hurt much more Ada programmers than
> having too many, so let's please be extra careful here.

Yes - vrp has potentially massive effects on Ada code.  These effects can
be good, even wonderful, if done right, but the slightest mistake could cause
bad bad trouble.
Comment 30 Richard Biener 2007-02-23 17:32:50 UTC
Ok, I have too little Ada skills ;)  What is missing in the following?


with test;

package test is
  type Count is range 0 .. Natural'Last;
  subtype Positive_Count is Count range 1 .. Count'Last;
  procedure Set_Col (To : Positive_Count);
end test;

procedure Set_Col
  (To  : Positive_Count)
is
begin
  if not To'Valid then
    raise Constraint_Error;
  end if;
end Set_Col;


$ gnatchop -w Set_Col.adb
splitting Set_Col.adb into:
   test.ads
   set_col.adb
$ gnatmake set_col.adb
gcc-4.1 -c set_col.adb
set_col.ads:2:25: "Positive_Count" is undefined (more references follow)
gnatmake: "set_col.adb" compilation error
Comment 31 Richard Biener 2007-02-23 20:18:48 UTC
Created attachment 13102 [details]
patch

updated patch
Comment 32 Richard Biener 2007-02-23 22:40:28 UTC
Created attachment 13103 [details]
patch

Bah - now with the errors fixed.  Bootstraps ok, some of acats regresses.

If you disable bootstrap and run the testsuite you get
FAIL:   c340001
FAIL:   c35507j
FAIL:   c390001
FAIL:   c390005
FAIL:   c390006
FAIL:   c390a01
FAIL:   c390a02
FAIL:   c390a03
FAIL:   c954012
FAIL:   c96005a
FAIL:   c96005d
FAIL:   c96005f
FAIL:   c96006a
FAIL:   c96007a
FAIL:   c96008a
FAIL:   c96008b
FAIL:   c974002
FAIL:   cc51007
FAIL:   cd92001
FAIL:   ce3305a
FAIL:   ce3402c
FAIL:   ce3405a
FAIL:   ce3405d
FAIL:   ce3409c
FAIL:   ce3410c
FAIL:   ce3602a
FAIL:   ce3605d
FAIL:   ce3605e
FAIL:   ce3606a
FAIL:   ce3606b
FAIL:   ce3706f
FAIL:   ce3806e
FAIL:   ce3806h
FAIL:   ce3906a
FAIL:   ce3906e
FAIL:   ce3906f
FAIL:   cxh1001
FAIL:   ee3203a
FAIL:   ee3402b

Most of the are either
raised CONSTRAINT_ERROR : a-calend.adb:440 explicit raise
or
raised CONSTRAINT_ERROR : a-textio.adb:1511 explicit raise

With bootstrapping the compiler and then checking you get

FAIL:   c35507j
FAIL:   cd92001
FAIL:   cxh1001

I guess that nearly all range checks are eliminated and without bootstrapping
we have a disconnect between the redundant checks in the rts and the
testcases.  If it happens that the non-bootstrapped rts is built by the
host compiler(?).
Comment 33 charlet@adacore.com 2007-02-24 10:12:18 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> I guess that nearly all range checks are eliminated and without bootstrapping
> we have a disconnect between the redundant checks in the rts and the
> testcases.  If it happens that the non-bootstrapped rts is built by the
> host compiler(?).

No, that never happens. The rts is always built with the latest (stage3)
compiler. Otherwise it would not even begin to work fro cross compilers.

Arno
Comment 34 charlet@adacore.com 2007-02-24 12:32:28 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> > we have a disconnect between the redundant checks in the rts and the
> > testcases.  If it happens that the non-bootstrapped rts is built by the
> > host compiler(?).
> 
> No, that never happens. The rts is always built with the latest (stage3)
> compiler. Otherwise it would not even begin to work fro cross compilers.

Note that I'm talking about ada/rts, which gets installed under adainclude
and adalib, and used by Ada apps. That's the target run-time.

Maybe you are talking about the part of the Ada run-time which is used by
the compiler itself, in which case, it's considered as a source of the
compiler, and treated as such (built successively by all compilers from
bootstrap compiler to stage2 compiler).

Arno
Comment 35 Richard Biener 2007-02-24 12:38:04 UTC
I was talking about the rts that get's used if I configure with --disable-bootstrap, do a make and then run make check-ada from within the
gcc/ subdirectory.  As far as I understand that rts seems to be built using
the bootstrap compiler.  At least this would explain the difference in the
number of acats failures I see comparing a bootstrapped tree vs. a non-bootstrapped tree.
Comment 36 charlet@adacore.com 2007-02-24 12:47:52 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> I was talking about the rts that get's used if I configure with
> --disable-bootstrap, do a make and then run make check-ada from within the
> gcc/ subdirectory.  As far as I understand that rts seems to be built using
> the bootstrap compiler.  At least this would explain the difference in the
> number of acats failures I see comparing a bootstrapped tree vs. a
> non-bootstrapped tree.

Sorry, I am not familiar with --disable-bootstrap, but if it builds
the Ada rts with the bootstrap compiler, then that's a clear bug in the
top level makefiles.

Ada makefiles are not designed to build the Ada rts with the host
compiler, so there must be some very strange makefile interaction going
on if true.

You can easily verify that of course by checking your build log.

Arno
Comment 37 baldrick@free.fr 2007-02-28 23:30:44 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> With bootstrapping the compiler and then checking you get
> 
> FAIL:   c35507j
> FAIL:   cd92001
> FAIL:   cxh1001

I get a slightly different set (i486-linux-gnu):

c35505f c35507j c35508g cxh1001

The intersection is c35507j cxh1001.

I worked on c35507j a bit.  Fold did it!  The problem
is that the value of arg1, a constant, is not in the
range of its own type!  It was fold itself that created
the (wrong) constant, in this case of constant of value 0
for a type with range 4..5 .  Fold needs to be consistent.
Either it decides that it is OK, for computational purposes,
to violate range restrictions - but in that case it can't
then simplify comparisons based on values being outside
the range of the type, which is what this patch does -
or it always respects range restrictions, which is not
currently the case and will take quite some work to ensure
(adding some assertions in the various routines that
construct constants would be helpful).

In fact, when you think about it this transformation
is quite dubious, at least if both arguments have the
same type.  If that case, if arg1 is outside the range
of arg0's type, then it is outside the range of its
own type!  i.e. it is a bogus constant and a sign of
a compiler bug rather than of a useful simplification!
Comment 38 baldrick@free.fr 2007-03-01 08:18:12 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> ... The problem
> is that the value of arg1, a constant, is not in the
> range of its own type! ...

It seemed clear to me last night why this is a problem,
but now I can't see why anymore...  Types don't seem
very useful for constants (why do they have a type at
all?), and if you take the viewpoint that you should
just ignore the constant's type, then being out of
range is not relevant.  So the question becomes: how
did this constant get created, and why does its type
seem to matter...
Comment 39 Richard Biener 2007-03-01 09:50:48 UTC
One key point to notice is that the transformation looks at ARG0 op CST where
arg0 and cst don't necessarily have to have the same type (arg0 is reduced from
op0 by STRIP_SIGN_NOPS), so effectively this folds

  (Base_Type)x > 10

(where 10 is supposed to be in Base_Type in the interesting case) based on the
value range of x!  Now, it also folds

  x > 10

with 10 in the derived type but out-of-range constant (created wrongly by
fold, as you noticed).  It should be possible to check whether 10 is in
of a derived type and in that case not doing the folding, which is probably
way easier than fixing all of fold not to generate those constants.
Comment 40 baldrick@free.fr 2007-03-01 23:07:06 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

The problem is in this transformation:

      /* Fold (X & C) op (Y & C) as (X ^ Y) & C op 0", and symmetries.  */

X^Y may not be in the range of the type.  In this case C=7 and op=NE_EXPR.
The type of X and Y has range 4..5.  Thus X^Y is either 0 or 2 (neither of
which is in the range 4..5).  Since the type of X^Y has range 4..5, the
new fold code deduces that X^Y NE 0 is always true.  I think the thing to
do, as Richard Kenner suggested, is to convert each type to its base type
right at the start of fold_comparison, at least if it has a base type
(the same goes for other routines in fold).  This unfortunately neutralizes
your patch, since as it is right now you will only ever see base types.
Thus this kind of check needs to happen at the start of fold_comparison,
before the conversion to the base type.

Ciao,

Duncan.
Comment 41 Richard Biener 2007-03-02 09:02:14 UTC
Thaks for the detective work!  I sort of expected the fold patch to be weird or
have no effect - but it was needed only (for the testcase) to get rid of the
target_first == 128 comparison, as that is confusing VRP.  Basically after this
comparison we conclude target_first != 128 and drop the earlier target_first != 10
assertion which is the one we can use to optimize the later comparisons.

So the other solution is to simply not record out-of-bounds assertions.
Comment 42 baldrick@free.fr 2007-03-02 09:16:30 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> Thaks for the detective work!  I sort of expected the fold patch to be weird or
> have no effect - but it was needed only (for the testcase) to get rid of the
> target_first == 128 comparison, as that is confusing VRP.  Basically after this
> comparison we conclude target_first != 128 and drop the earlier target_first !=
> 10
> assertion which is the one we can use to optimize the later comparisons.
> 
> So the other solution is to simply not record out-of-bounds assertions.

I think fold needs to be fixed, whether or not your fold patch goes in.
After all, fold is clearly willing to do create objects like X^Y which
take values outside of the range of the type.  Once such objects are
floating around, any serious use of TYPE_MAX_VALUE or TYPE_MIN_VALUE
(when they are non-trivial) will almost certainly give wrong results,
as shown by your fold patch.
Comment 43 Richard Biener 2007-03-02 09:53:10 UTC
I agree.  Let's create another bug for this issue.  PR31023.
Comment 44 Richard Biener 2008-03-28 12:21:01 UTC
Subject: Bug 30911

Author: rguenth
Date: Fri Mar 28 12:20:09 2008
New Revision: 133680

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=133680
Log:
2008-03-28  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/30317
	PR tree-optimization/30911
	PR tree-optimization/34793
	* tree-vrp.c (set_and_canonicalize_value_range): New function.
	(struct assert_locus_d): New member EXPR.
	(register_new_assert_for): Add EXPR parameter to support
	ASSERT_EXPR <name, expr OP limit>.
	(register_edge_assert_for_1): Adjust callers.
	(find_assert_locations): Likewise.
	(process_assert_insertions_for): Build condition from
	expression.
	(extract_range_from_assert): Handle ASSERT_EXPRs
	of the form ASSERT_EXPR <name, expr OP limit>.
	(register_edge_assert_for_2): New helper registering
	asserts for comparisons.  Recognize range tests of the form
	(unsigned)i - CST1 OP CST2.
	(register_edge_assert_for_1): Use it.
	(register_edge_assert_for): Likewise.
	* tree.def (ASSERT_EXPR): Document extra allowed conditional
	expressions.
	(needs_overflow_infinity): Integer sub-types
	do not need overflow infinities.
	(vrp_val_is_max): The extreme values of integer sub-types
	are those of the base type.
	(vrp_val_is_min): Likewise.

	* gcc.dg/tree-ssa/vrp35.c: New testcase.
	* gcc.dg/tree-ssa/vrp36.c: Likewise.
	* gcc.dg/tree-ssa/vrp37.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp37.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c
    trunk/gcc/tree.def

Comment 45 Duncan Sands 2008-03-28 14:58:56 UTC
The recent VRP improvements made no difference to this bug.
Comment 46 Richard Biener 2008-03-28 19:18:55 UTC
Ok, I didn't really expect that ;)

Some new background information.  With the middle-end type-system work we now
omit conversions from sub-types T' to their base-types T.  Thus we have
the three cases

  T' sub;
  T  x;

  x = sub;      (1)
  sub = (T')x;  (2)
  x = VIEW_CONVERT_EXPR <T>(sub);  (3)

where VRP for the simple copy (1) does not restrict x value range based
on the T's TYPE_MIN/MAX_VALUE (but it should).  For (2) the same is
true (though the conversion is _not_ truncating for out of bound values,
so I am not sure if this doesn't break something).  But for both (1)
and (2) holds that a variable of type T' can be assumed to have a
value range restricted by its TYPE_MIN/MAX_VALUE.

Case (3) is special in that it is a propagation barrier, thus x will get
a varying value range.  We could do better here if we knew that subs
value range was not restricted by its TYPE_MIN/MAX_VALUE only.

I don't know if this is really the best setup to optimize Ada range checks,
or if we should always fall back to the base types TYPE_MIN/MAX_VALUE
range and use the type defined range of the sub-types T' only in special
places like for example for the initial value-range of T' variables
default definitions (thus uninitialized values and function parameters
where if I understand correctly in Ada the caller ensures that the
value is in range).  Of course this wouldn't work very well in
combination with inlining.
Comment 47 Richard Biener 2008-03-28 22:12:53 UTC
What is interesting is that j__target_type___XDLU_10__20 is a unsigned sub type
with range [10, 20] of a signed base type with range [-128, 127].  So, we
enter compare_values ((js__TtB)20, (j__target_type___XDLU_10__20)128)
(both types have a precision of 8 bits, but the out-of-range value 128 is
not representable in the base type, but is interpreted as -128).

So, why is this range check

  if (target_first_66 == 128)
    goto <bb 7>;
  else
    goto <bb 8>;

<bb 7>:
  __gnat_rcheck_12 ("join_equal.adb", 15);

using a value not representable in the base type?  The TYPE_MIN/MAX_VALUEs
are of the type of the base type, so target_first_66s value range is
[10, 20] at the point of this comparison.  Is this supposed to be
a comparison with -128 or with 128?  That is, is this

  target_first_66 == TYPE_MIN_VALUE (js__TtB)

?  I guess so.

The problem is that we try to compare different typed values here, the
10 and 20 of signed base type and the 128 of unsigned sub type.  If
we for the comparison canonicalize the 128 to the signed base type
(which is the only thing that makes sense) we get an overflow value
as it wraps to -128 and the comparison result will be ignored because
"it assumes that signed overflow is undefined".  Bah.

So let's try avoiding setting the overflow flag for conversions from
a sub type to its base type.  Then I have a patch that evaluates

      target_first_66 == 128

to false based on the initial value range idea for default SSA_NAMEs
and the only remaining range checks are

grep gnat_rcheck j.ads.127t.optimized 
  __gnat_rcheck_04 ("join_equal.adb", 13);
  __gnat_rcheck_12 ("join_equal.adb", 29);
  __gnat_rcheck_12 ("join_equal.adb", 39);
Comment 48 Richard Biener 2008-03-28 22:14:28 UTC
Created attachment 15394 [details]
patch for comment #47

This is what I was playing with.
Comment 49 Richard Biener 2008-03-28 22:35:35 UTC
As of

"The TYPE_MIN/MAX_VALUEs
are of the type of the base type, so target_first_66s value range is
[10, 20] at the point of this comparison.  Is this supposed to be
a comparison with -128 or with 128?  That is, is this

  target_first_66 == TYPE_MIN_VALUE (js__TtB)

?  I guess so."

This is fold simplifying (js__TtB) target_first == -128 to
target_first == 128 via fold_sign_changed_comparison.
And thus PR31023 which now also blocks this PR.
Comment 50 baldrick@free.fr 2008-03-28 22:42:20 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

>   T' sub;
>   T  x;
> 
>   x = sub;      (1)
>   sub = (T')x;  (2)
>   x = VIEW_CONVERT_EXPR <T>(sub);  (3)
> 
> where VRP for the simple copy (1) does not restrict x value range based
> on the T's TYPE_MIN/MAX_VALUE (but it should).  For (2) the same is
> true (though the conversion is _not_ truncating for out of bound values,
> so I am not sure if this doesn't break something).

Ada never does (2) unless the value of x is in the range of sub, so this
should be ok for assignments coming straight out of the Ada f-e.  It might
be that fold, for example, generates problematic versions of (2) however.
I have no idea if this can happen.

> I don't know if this is really the best setup to optimize Ada range checks,

It seems reasonable.  Only using range info for function arguments would
side-step the fold-doesn't-use-base-types problem though.
Comment 51 baldrick@free.fr 2008-03-28 22:48:21 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> This is fold simplifying (js__TtB) target_first == -128 to
> target_first == 128 via fold_sign_changed_comparison.

Right, that was my instant guess.  The Ada f-e is pretty
systematic about converting everything to the base type
before doing comparisons.  While fold happily creates the
kind of strangeness you observed.

> And thus PR31023 which now also blocks this PR.

In fact PR31023 was split out of this because of exactly
this kind of problem in the testcase!  I should have marked
it as blocking this one, sorry.
Comment 52 Richard Biener 2008-03-28 22:58:35 UTC
I'm now testing a variant of the patch that fixes fold_sign_changed_comparison
and just initializes incoming parameter value-ranges based on their types.
This seems to do the same range-check removals and looks like an overall
sane change.

I assume when inlining we will see the range check that assures the function
parameters are in-range, right?  So even for that case we should be able
to do the same simplifications.  Can you cook up a testcase that shows this
case?
Comment 53 Eric Botcazou 2008-03-30 09:15:03 UTC
I should have been more careful, there are wrong premises:

> Yes.  Amazing, isn't it ;)  The important thing to keep in mind is that
> all "target" variables must be in the range 10..20, and all "source"
> variables in the range 0..100 (see the definitions
> type S is range 0 .. 100; <-- S corresponds to Source_Type in Join_Equal
> type T is range 10 .. 20; <-- T corresponds to Target_Type in Join_Equal
> ).
> What does "must be in the range" mean?  Firstly, the program behaviour is
> undefined if a variable is outside its range.

That's not true.  The reference to an invalid value doesn't result in
undefined behavior, it is a bounded error, and the result must be some predictable non-erroneous implementation-defined behavior.

> Secondly, the language requires the compiler to check at the point of the
> call that the values passed to the Join_Equal subprogram are in the right
> ranges.

There is no such requirement and GNAT doesn't do that by default, you need to
pass -gnatVi on the command line to activate validity check for in arguments.

> Anyway, the practical upshot is that VRP is allowed to assume that
> source_first and source_last have values in the range 0..100, and
> target_first and target_last have values in the range 10..20.  Using
> this, it should be able to eliminate all of the compiler inserted range 
> checking.

Since the premises are wrong, the conclusion doesn't hold.
Comment 54 Duncan Sands 2008-03-30 14:14:44 UTC
Here's a test that VRP is not eliminating
validity checks.  "abort" should be called
if either X or Y is <= 0.  With Richard's
latest patch (from the gcc mailing list)
applied, everything is fine: the tests are
still done.

procedure Valid (X : Positive) is
   procedure Abrt;
   pragma Import(C, Abrt, "abort");

   Y : Positive;
begin
   if not X'Valid then
      Abrt;
   end if;
   if not Y'Valid then
      Abrt;
   end if;
end;
Comment 55 Duncan Sands 2008-03-30 14:18:33 UTC
And here's a testcase that was supposed to check that
VRP is not removing checks that array accesses are in
range.  Instead it shows that the Ada f-e is failing
to generate checks at all!

function Overflow (X : Positive) return Integer is
   Y : Positive;
   A : array (Positive) of Integer;
   pragma Import (Ada, A);
begin
   return A (X) + A (Y);
end;
Comment 56 baldrick@free.fr 2008-03-30 14:26:59 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> > What does "must be in the range" mean?  Firstly, the program behaviour is
> > undefined if a variable is outside its range.
> 
> That's not true.  The reference to an invalid value doesn't result in
> undefined behavior, it is a bounded error, and the result must be some
> predictable non-erroneous implementation-defined behavior.

This discussion continued on the gcc mailing list, starting here:
http://gcc.gnu.org/ml/gcc-patches/2008-03/msg01841.html
Comment 57 rguenther@suse.de 2008-03-30 14:52:19 UTC
Subject: Re:  VRP fails to eliminate range checks
 in Ada code

On Sun, 30 Mar 2008, baldrick at gcc dot gnu dot org wrote:

> ------- Comment #55 from baldrick at gcc dot gnu dot org  2008-03-30 14:18 -------
> And here's a testcase that was supposed to check that
> VRP is not removing checks that array accesses are in
> range.  Instead it shows that the Ada f-e is failing
> to generate checks at all!
> 
> function Overflow (X : Positive) return Integer is
>    Y : Positive;
>    A : array (Positive) of Integer;
>    pragma Import (Ada, A);
> begin
>    return A (X) + A (Y);
> end;

Or that fold is clever enough (again) to remove the check - I'm
sure it has special code dealing with >= 0 checks on unsigned
types ;)

Richard.
Comment 58 Richard Biener 2008-03-30 14:55:18 UTC
Btw, can we have those testcases in gnat.dg/ with a name I can remember
(bounds-N.adb or similar)?  Looking for testcases in acats is no fun ;)
Comment 59 Eric Botcazou 2008-03-30 15:03:00 UTC
> And here's a testcase that was supposed to check that
> VRP is not removing checks that array accesses are in
> range.  Instead it shows that the Ada f-e is failing
> to generate checks at all!

Even with -gnato?
Comment 60 Richard Biener 2008-03-30 15:09:06 UTC
function overflow (x : positive) return integer is
   y : positive;
   a : static array (1 .. 16#7FFF_FFFF#) of integer;
   pragma import (ada, a);
begin
   R4b : constant long_long_integer := long_long_integer?(a (x)) +
     long_long_integer?(a (y));
   [constraint_error when
     not (R4b in -16#8000_0000# .. 16#7FFF_FFFF#)
     "overflow check failed"]
   return integer(integer?(R4b));
end overflow;

so it checks the result of the addition, but not that x or y are within
bounds before accessing the array.
Comment 61 baldrick@free.fr 2008-03-30 15:16:44 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> > And here's a testcase that was supposed to check that
> > VRP is not removing checks that array accesses are in
> > range.  Instead it shows that the Ada f-e is failing
> > to generate checks at all!
> 
> Even with -gnato?

Yes, even with -gnato.  With -gnato it checks that the
addition doesn't overflow.  But there are no checks on
the array access.  It looks like the f-e doesn't generate
them in the first place (as opposed to fold or gigi making
a mistake).
Comment 62 Eric Botcazou 2008-03-30 15:45:21 UTC
> Yes, even with -gnato.  With -gnato it checks that the
> addition doesn't overflow.

Oh, sorry, I thought we were talking about the overflow check...

> But there are no checks on the array access.  It looks like the f-e
> doesn't generate them in the first place (as opposed to fold or gigi
> making a mistake).

This is as documented in the GNAT manual, section 3.2.4 Validity Checking.
You need to pass -gnatVs to have them.
Comment 63 rguenther@suse.de 2008-03-30 15:56:00 UTC
Subject: Re:  VRP fails to eliminate range checks
 in Ada code

On Sun, 30 Mar 2008, ebotcazou at gcc dot gnu dot org wrote:

> ------- Comment #62 from ebotcazou at gcc dot gnu dot org  2008-03-30 15:45 -------
> > Yes, even with -gnato.  With -gnato it checks that the
> > addition doesn't overflow.
> 
> Oh, sorry, I thought we were talking about the overflow check...
> 
> > But there are no checks on the array access.  It looks like the f-e
> > doesn't generate them in the first place (as opposed to fold or gigi
> > making a mistake).
> 
> This is as documented in the GNAT manual, section 3.2.4 Validity Checking.
> You need to pass -gnatVs to have them.

So even GNAT assumes parameter values are in-range?  Wouldn't that
cause an bounded error to become an unbounded error if it were
out-of-range?

I'm somewhat confused on what the Ada language specification is and
what is GNAT implementation freedom...

Richard.
Comment 64 baldrick@free.fr 2008-03-30 16:02:19 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> > But there are no checks on the array access.  It looks like the f-e
> > doesn't generate them in the first place (as opposed to fold or gigi
> > making a mistake).
> 
> This is as documented in the GNAT manual, section 3.2.4 Validity Checking.
> You need to pass -gnatVs to have them.

Consider the following test case:

procedure Overflow (X : Positive) return Integer is
   A : array (Positive) of Integer;
   pragma Import (Ada, A);
begin
   A (X) := X;
end;

(for which no checks are generated).  In the user guide

 GNAT GPL User's Guide 
 The GNAT Ada Compiler
 GNAT GPL Edition, Version 2007
 Document revision level 1.422
 Date: 2007/03/30 03:28:29

in section 3.2.4 it says:

 In GNAT, the result of such an evaluation in normal default mode is to
 either use the value unmodified, or to raise Constraint_Error in those
 cases where use of the unmodified value would cause erroneous execution.
 The cases where unmodified values might lead to erroneous execution are
 case statements (where a wild jump might result from an invalid value),
 and subscripts on the left hand side (where memory corruption could occur
 as a result of an invalid value).

This testcase is a clear example of erroneous execution, being of the type
explicitly mentioned.  So according to section 3.2.4 Constraint_Error should
be raised "in normal default mode".  Yet this is not the case.
Comment 65 Eric Botcazou 2008-03-30 16:15:27 UTC
> So even GNAT assumes parameter values are in-range?  Wouldn't that
> cause an bounded error to become an unbounded error if it were
> out-of-range?

GNAT considers that it's an unbounded error in a few specific cases by default,
for example subscripts on the LHS.  But not on the RHS (-gnatVs is needed).
Comment 66 Eric Botcazou 2008-03-30 16:18:45 UTC
> Consider the following test case:
> 
> procedure Overflow (X : Positive) return Integer is
>    A : array (Positive) of Integer;
>    pragma Import (Ada, A);
> begin
>    A (X) := X;
> end;
> 
> (for which no checks are generated).

Try first to compile it. :-)
Comment 67 baldrick@free.fr 2008-03-30 17:03:34 UTC
Subject: Re:  VRP fails to eliminate range checks in Ada code

> Try first to compile it. :-)

I did!  I didn't notice the compile error
after the -gnatG output.  Indeed, when fixed
thusly

procedure Overflow (X : Positive) is
   A : array (Positive) of Integer;
   pragma Import (Ada, A);
begin
   A (X) := X;
end;

then you do get a check:

with interfaces;

procedure overflow (x : positive) is
   a : array (1 .. 16#7FFF_FFFF#) of integer;
   pragma import (ada, a);
begin
   [constraint_error when not (interfaces__unsigned_32!(x) >= 1 and then
     interfaces__unsigned_32!(x) <= 16#7FFF_FFFF#) "invalid data"]
   a (x) := x;
   return;
end overflow;
Comment 68 Richard Biener 2008-04-03 19:52:40 UTC
I am no longer working on specifically this.
Comment 69 baldrick@free.fr 2009-11-17 11:04:32 UTC
It seems that variables produced by the Ada front-end no longer have any
non-trivial range information associated with them.  Without knowing the
range information
   type S is range 0 .. 100;
   type T is range 10 .. 20;
it is impossible for the optimizers to eliminate most of the range checks
in this testcase.  With the range information all of the checks can in theory
be removed.  This is an example of how range information is potentially very
helpful for optimizing Ada programs.

Is there anyway for the optimizers to get at this range information still?
Or was range information removed because it is essentially impossible to use
it correctly (if so this bug report should be closed as unfixable)?
Comment 70 Eric Botcazou 2009-11-17 11:19:21 UTC
> It seems that variables produced by the Ada front-end no longer have any
> non-trivial range information associated with them.  Without knowing the
> range information
>    type S is range 0 .. 100;
>    type T is range 10 .. 20;
> it is impossible for the optimizers to eliminate most of the range checks
> in this testcase.  With the range information all of the checks can in theory
> be removed.  This is an example of how range information is potentially very
> helpful for optimizing Ada programs.

Theoretically, but this never really worked in practice; and experiments showed that we get better code without it, especially in loops.

> Is there anyway for the optimizers to get at this range information still?
> Or was range information removed because it is essentially impossible to use
> it correctly (if so this bug report should be closed as unfixable)?

Yes, it's essentially impossible to use because of the need to support invalid values.  There might be means to get the info back, e.g. using ASSERT_EXPRs, but this hasn't been tried yet.
Comment 71 rguenther@suse.de 2009-11-17 15:07:51 UTC
Subject: Re:  VRP fails to eliminate range checks
 in Ada code

On Tue, 17 Nov 2009, baldrick at free dot fr wrote:

> ------- Comment #69 from baldrick at free dot fr  2009-11-17 11:04 -------
> It seems that variables produced by the Ada front-end no longer have any
> non-trivial range information associated with them.  Without knowing the
> range information
>    type S is range 0 .. 100;
>    type T is range 10 .. 20;
> it is impossible for the optimizers to eliminate most of the range checks
> in this testcase.  With the range information all of the checks can in theory
> be removed.  This is an example of how range information is potentially very
> helpful for optimizing Ada programs.
> 
> Is there anyway for the optimizers to get at this range information still?
> Or was range information removed because it is essentially impossible to use
> it correctly (if so this bug report should be closed as unfixable)?

It was removed because it was impossible to use it correctly.  The "fix"
is to derive range information from existing range checks, possibly
inter-procedurally.

Richard.
Comment 72 charlet@adacore.com 2009-11-17 15:50:31 UTC
Subject: Re:  VRP fails to eliminate range
	checks in Ada code

> > Is there anyway for the optimizers to get at this range information still?
> > Or was range information removed because it is essentially impossible to use
> > it correctly (if so this bug report should be closed as unfixable)?
> 
> It was removed because it was impossible to use it correctly.  The "fix"
> is to derive range information from existing range checks, possibly
> inter-procedurally.

Right, as soon as you have one range check, the compiler can make more
precise assumptions/conclusions about the actual range.

Arno
Comment 73 baldrick@free.fr 2009-11-17 16:56:45 UTC
Can someone please close this bug as WONTFIX then (I don't know how to do
this myself).
Comment 74 Arnaud Charlet 2009-11-17 17:03:35 UTC
Marking as WONTFIX, as requested