Re: Ada subtypes and base types

[Duncan Sands <baldrick at free dot fr>]

Hi Jeff,

On Monday 27 March 2006 21:00, Jeffrey A Law wrote:
> On Sat, 2006-03-25 at 10:35 -0500, Diego Novillo wrote:
> 
> > Start by looking at tree-vrp.c:infer_value_range.
> I'm not so sure this is the best place to start.

it seems a good place for adding ASSERT_EXPRs on function return
values though.

> It seems to me that the asserts could be registered at the
> start of insert_range_assertions.
> 
> Just walk the parameter list and extract the default definition
> for each parameter and register an appropriate assertion based
> on the parameter's type.

I agree, however I don't yet know how to walk the parameter list, so
any hints would be welcome :)

> Note that this basically avoids reaching any kind of conclusion
> about the best way to handle our representational issue with
> VR_VARYING vs just creating a range from TYPE_MIN_VALUE to
> TYPE_MAX_VALUE.  There's a part of me which would recommend
> reaching some conclusions on that issue before going down the
> path of special casing parameters.

I agree that this kind of special casing by the middle-end is all
wrong - the front-end should do it.

<RANT>
Personally I think the Ada frontend should never pass types with
a restricted range to the middle-end (in Ada terms, this means
that the middle-end would only ever see base types).  If the
front-end knows (or is prepared to have the optimisers assume)
that the value of a variable is in some restricted range, then
the front-end should itself insert an appropriate ASSERT_EXPR
in the tree that it is going to pass to the middle-end.

Of course this means reworking the middle-end a bit so it can
handle assertions right from the beginning.  Not to mention
reworking the Ada front-end.  But it gives more control to the
front-end, and it would likely be an overall code simplification
for the middle-end, and surely a conceptual simplification,
since no-one would have to worry about funny ranges any more,
and ASSERT_EXPRs are easy to understand.

After all, saying that a variable belongs to a type T with a
restricted range means: (A) it belongs to the base type (int,
for example), and (B) the value that it holds is within some
subrange.  (B) is essentially an assertion, exactly of the kind
ASSERT_EXPR was introduced to capture.  The problem with using
types like T is that sometimes (B) holds, sometimes it doesn't.
A variable declared to be of type T won't usually satisfy (B)
until it gets an initial value.  If the uninitialised variable
is passed to a procedure, now you have a procedure parameter
of type T which doesn't satisfy (B).  So when are the optimisers
allowed to assume (B)?  The Ada standard carefully defines the
possible outcomes of using an out-of-range variable; the middle-end
could try to implement these subtle semantics.  But surely it
shouldn't even try: it should leave Ada semantics to the Ada
front-end, and provide a means by which the front-end can tell
it what it may assume.  ASSERT_EXPRs seem like a decent way
of doing this, in any case a better way than the current type
based system.
</RANT>

That said, I'm still planning to implement the ASSERT_EXPR on
subroutine parameters scheme, to check that it really is feasible,
and to learn about the middle-end.

> Note that this basically avoids reaching any kind of conclusion
> about the best way to handle our representational issue with
> VR_VARYING vs just creating a range from TYPE_MIN_VALUE to
> TYPE_MAX_VALUE.  There's a part of me which would recommend
> reaching some conclusions on that issue before going down the
> path of special casing parameters.

If exotic TYPE_MIN, TYPE_MAX values did not exist, would you be
still feel there was an issue here?

Also, I now think it would be a mistake to initialise all
variable ranges to [TYPE_MIN, TYPE_MAX].  I implemented this,
and got great optimisation - a bit too much optimisation in fact!
For example, you can't test whether a variable is in range using
the obvious "if" statement anymore, since VRP will eliminate it
(after all, it "knows" the variable is in range already, because
it was told so).

Do the Ada people want this level of optimisation?  I'm pretty sure
they don't: I've heard Robert Dewar say that he considers exactly this
optimisation (eliminating an "if" on an uninitialised variable based
on the range given in the type definition) to be a bad idea.

So that means that initialising variables to [TYPE_MIN,TYPE_MAX]
is likely not acceptable in general.  Actually, it might be acceptable
if the Ada front-end was modified to only declare a variable to be of a
type with a restricted range when it is sure (or is willing to have
the optimisers assume) that the value is in that range.  For example,
uninitialised variables would have to be declared to be of the base type
(no funny range), and would be cast to the restricted range type when the
value is known to be in range, perhaps because Ada semantics ensure it is
in range, or because a range check was just performed.  [In the scheme I
suggested in my rant, the front-end would insert an ASSERT_EXPR here, rather
than a type cast].

Maybe the Ada people *are* happy if VRP assumes that uninitialised
variables are in range.  I'm really hoping that some Ada gurus will step
in here and enlighten us.  Or maybe a Pascal guru :)

A final remark: ASSERT_EXPRs and types with restricted ranges are
actually equivalent (at least if you are always allowed to assume
that a variable is in the range of its type).  Proof?  To get rid
of ASSERT_EXPRs and only use restricted ranges, proceed as follows:
every time you want to insert an ASSERT_EXPR in VRP, introduce a new
type instead, with [TYPE_MIN,TYPE_MAX] equal to the range that the
assertion would have defined, and cast the variable to that type; the
rest of VRP would then simply examine variable types and their ranges,
rather than ASSERT_EXPRs.  Conversely, to get rid of types with restricted
ranges, every time you see a variable of such a type, redeclare the
variable to be of the corresponding unrestricted "base" type, and insert
an ASSERT_EXPR that the variable is in the range [TYPE_MIN,TYPE_MAX].

The point of this remark is that there are two mechanisms for doing
the same thing: ASSERT_EXPRs and types with funny ranges.  Supporting
them both is simply a duplication of effort, and asking for trouble.
One of these mechanisms is redundant.  Since everyone understands
ASSERT_EXPRs, and almost no-one understands funny ranges, I think
funny ranges should be eliminated and ASSERT_EXPRs used more widely.

Sorry to have ranted so long.

All the best,

Duncan.