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);
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;
Bonus points if you can reduce this to a C test case ;-) Starting with the gimple dumps, this is usually not hard to do.
> 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.
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.
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.
> 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.
> 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.
> 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.
(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.
Please do not overwrite changes, thanks.
> 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...
> 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.
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?
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.
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.
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.
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>;
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?
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.
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.
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.
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)
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.
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)
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.
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.
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
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 ;)
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.
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
Created attachment 13102 [details] patch updated patch
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(?).
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
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
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.
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
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!
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...
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.
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.
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.
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.
I agree. Let's create another bug for this issue. PR31023.
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
The recent VRP improvements made no difference to this bug.
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.
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);
Created attachment 15394 [details] patch for comment #47 This is what I was playing with.
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.
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.
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.
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?
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.
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;
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;
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
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.
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 ;)
> 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?
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.
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).
> 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.
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.
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.
> 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).
> 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. :-)
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;
I am no longer working on specifically this.
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 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.
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.
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
Can someone please close this bug as WONTFIX then (I don't know how to do this myself).
Marking as WONTFIX, as requested