Right of Optimize Eager Evaluation Away

Right of Optimize Eager Evaluation Away

[Laurent Guerby]

[I originally posted this in the 11.6 thread, but got no answer]

If we have the following function:
   
   function Cond_T (C : in Boolean; If_True, If_False : in T) return T;
   pragma Inline (Cond_T);

   function Cond_T (C : in Boolean; If_True, If_False : in T) return T is
   begin
      if C then
         return If_True;
      else
         return If_False;
      end if;
   end Cond_T;

And the following expression:

   C : constant Boolean := Some_Run_Time_Value_That_The_Compiler_Cannot_Guess;

   X : constant T := Cont_T (C, If_True => Super_Expensive_Function_Call_1, 
                                If_False => Super_Expensive_Function_Call_2);

The question is: is a smart Ada 95 compiler allowed to generate code
that looks like this:

   if C then
      X := Super_Expensive_Function_Call_1;
   else
      X := Super_Expensive_Function_Call_2;
   end if;

that is to say, be lazy about its argument, and so might
save execution time.

If one of the Super_Expensive function has side effects, or raises an
exception (so Pure won't help here), the code is not identical to the
original code:

   X1 := Super_Expensive_Function_Call_1;
   X2 := Super_Expensive_Function_Call_2;
   if C then
      return X1;
   else
      return X2;
   end if;

--LG

Re: Right of Optimize Eager Evaluation Away

[Robert A Duff]

Laurent Guerby <guerby@acm.org> writes:

> The question is: is a smart Ada 95 compiler allowed to generate code
> that looks like this:
> 
>    if C then
>       X := Super_Expensive_Function_Call_1;
>    else
>       X := Super_Expensive_Function_Call_2;
>    end if;
> 
> that is to say, be lazy about its argument, and so might
> save execution time.

No.  The function arguments may be evaluated in either order, so in case
of exception, the other one might not happen.  But without exceptions,
both arguments will be evaluated.

- Bob

Re: Right of Optimize Eager Evaluation Away

[Laurent Guerby]

Robert A Duff <bobduff@world.std.com> writes:
> Laurent Guerby <guerby@acm.org> writes:
> > The question is: is a smart Ada 95 compiler allowed to generate code
> > that looks like this:
> > 
> >    if C then
> >       X := Super_Expensive_Function_Call_1;
> >    else
> >       X := Super_Expensive_Function_Call_2;
> >    end if;
> > 
> > that is to say, be lazy about its argument, and so might
> > save execution time.
> No.  The function arguments may be evaluated in either order, so in case
> of exception, the other one might not happen.  But without exceptions,
> both arguments will be evaluated.

Is the potential raising of an exception the only language barrier
here (since as you mention the compiler is free to swap calls
defeating a class of side effects)? This seams easy to fix (via a
pragma), if one is interested in keeping the functional aspect of the
code instead of resorting to statements of course.

> - Bob

--LG

Re: Right of Optimize Eager Evaluation Away

[Nick Roberts]

Laurent Guerby wrote:
> 
> Robert A Duff <bobduff@world.std.com> writes:
> > Laurent Guerby <guerby@acm.org> writes:
> > > The question is: is a smart Ada 95 compiler allowed to generate code
> > > that looks like this:
> > >
> > >    if C then
> > >       X := Super_Expensive_Function_Call_1;
> > >    else
> > >       X := Super_Expensive_Function_Call_2;
> > >    end if;
> > >
> > > that is to say, be lazy about its argument, and so might
> > > save execution time.
> > No.  The function arguments may be evaluated in either order, so in case
> > of exception, the other one might not happen.  But without exceptions,
> > both arguments will be evaluated.
> 
> Is the potential raising of an exception the only language barrier
> here (since as you mention the compiler is free to swap calls
> defeating a class of side effects)? This seams easy to fix (via a
> pragma), if one is interested in keeping the functional aspect of the
> code instead of resorting to statements of course.

I didn't receive Laurent's original post (poor UK feed), so - forgive me
- I must guess at what he was originally suggesting, that a call such as

   P1(X,Y);

where P1 was declared by

   procedure P1 (A: Boolean; B: T) is
   begin
      if A then
         P2;
      else
         P3(B);
      end if;
   end;

would be optimised to evaluate X first, and omit the evaluation of Y if
X turned out to be True.

The RM95 says that a conforming implementation is allowed to execute an
Ada program in any way which produces the required external effects
[RM95 1.1.3(8-15)]. (Which is plain common sense, anyway, really.)

This means that a compiler can perform any optimisation that doesn't
change the external effects of a program. So the suggested optimisation
is perfectly acceptable, provided the compiler can _guarantee_ that it
will not change the external effects of the program.

I get the impression that, in practice, there are not many Ada compilers
which 'strongly' optimise (maybe there aren't any). However, I think a
strongly optimising compiler (by today's standards) would be very
likely, in effect, to produce the suggested optimisation, in the case of
the subprogram P1 being expanded inline, or local and independent, and
provided the compiler could be sure that the evaluation of Y could not
have raised an exception or caused any external effect.

-- 
Nick Roberts
http://www.adapower.com/lab/adaos
Always call for the professionals. (If they don't help, call for me ;-)

Re: Right of Optimize Eager Evaluation Away

[Robert A Duff]

Nick Roberts <nickroberts@callnetuk.com> writes:

> Laurent Guerby wrote:

> > Is the potential raising of an exception the only language barrier
> > here (since as you mention the compiler is free to swap calls
> > defeating a class of side effects)? This seams easy to fix (via a
> > pragma), if one is interested in keeping the functional aspect of the
> > code instead of resorting to statements of course.

I don't understand Laurent's question.

> I didn't receive Laurent's original post (poor UK feed), so - forgive me
> - I must guess at what he was originally suggesting, ...

Sorry, Nick -- you guessed wrong.  ;-)

The original question had to do with a function with two formal
parameters.  Does 11.6 authorize the compiler to omit the evaluation of
one of the *actual* parameters in a call, if it can prove that the value
of the formal will never be used.  The answer is no.  We are assuming
the evaluation of the actual parameters produces some externally-visible
side-effect.  (Yes, of course the compiler can optimize anything it
likes, if it can prove it doesn't affect the external effect.  But
that's not the point here.)

- Bob

Re: Right of Optimize Eager Evaluation Away

[Laurent Guerby]

Robert A Duff <bobduff@world.std.com> writes:
> > Laurent Guerby wrote:
> 
> > > Is the potential raising of an exception the only language barrier
> > > here (since as you mention the compiler is free to swap calls
> > > defeating a class of side effects)? This seams easy to fix (via a
> > > pragma), if one is interested in keeping the functional aspect of the
> > > code instead of resorting to statements of course.
> 
> I don't understand Laurent's question.

I should rephrase then ;-):

Is the potential raising of an exception the only language barrier
to allow lazy evaluation for an optimizing compiler?

It looks like to me that the Ada language more or less intend that
functions shouldn't have side effects, since by example it allows the
compiler to evaluate arguments and thus potentially calling functions
in any order, or allows only "in" parameters for the programmer.

The question is then, why stop at allowing any evaluation order and
not just allow lazy evaluation as well?

It allows some "nice" optimizations, like the one I mentionned, or
things like:

-- In some Debug package body:

   Enable_Trace : constant Boolean := True; 
   -- or set to False when compiled in "release" mode
   
   procedure Trace (M : in String) is
   begin
      if Enable_Trace then
          IO.Put (M);
      end if;
   end Trace;

-- Now you have your code full of Trace calls like:

   Trace ("index = " & Image (Index) & " value = " & Image (Value));

With the current RM, even if the compilers know that the Trace call
doesn't do anything (inlining is on, and proper unreached code
elimination has been done), it cannot suppress the calls to Image or
to "&" since they might potentially raise an exception. The only way
to do a "release"/"debug" switch that does not cause a performance
penalty for the "release" version is then to use vendor specific
pragmas like GNAT Assert or Debug, and thus is outside of the
language.

The "pragma" I was mentionning could look like:

pragma You_Can_Omit_Calls_To_This_If_The_Value_Is_Not_Needed (F);

(obviously a better name is needed ;-). If an expression involves only
calls to pragma'ed functions (the Standard and String stuff could be
in this category for example), then if the compiler finds out the
result isn't needed in some run-time paths, it can omit the evaluation
of the expression in those paths.

I don't know if I'm clearer here ;-).

> - Bob

--LG

Re: Right of Optimize Eager Evaluation Away

[Lutz Donnerhacke]

* Laurent Guerby wrote:
>It looks like to me that the Ada language more or less intend that
>functions shouldn't have side effects, since by example it allows the
>compiler to evaluate arguments and thus potentially calling functions
>in any order, or allows only "in" parameters for the programmer.
>
>The question is then, why stop at allowing any evaluation order and
>not just allow lazy evaluation as well?

You may provide a pragma to tell the compiler that this function is really a
pure functional function. Then it is allowed to optimize this way.

>The "pragma" I was mentionning could look like:
>pragma You_Can_Omit_Calls_To_This_If_The_Value_Is_Not_Needed (F);
>
>(obviously a better name is needed ;-). If an expression involves only

pragma Pure_Function ([Entity =>] function_LOCAL_NAME);
...

     Note: All functions in a Pure' package are automatically pure, and
     there is no need to use pragma Pure_Function' in this case.

     Note: If pragma Pure_Function' is applied to a renamed function,
     it applies to the underlying renamed function. This can be used to
     disambiguate cases of overloading where some but not all functions
     in a set of overloaded functions are to be designated as pure.
     

Re: Right of Optimize Eager Evaluation Away

[Robert A Duff]

Laurent Guerby <guerby@acm.org> writes:

> Is the potential raising of an exception the only language barrier
> to allow lazy evaluation for an optimizing compiler?

No.

> It looks like to me that the Ada language more or less intend that
> functions shouldn't have side effects, since by example it allows the
> compiler to evaluate arguments and thus potentially calling functions
> in any order, or allows only "in" parameters for the programmer.

Side effects are allowed in Ada.  It's true that functions can't have
'in' parameters, but they can modify globals and heap objects.  (As
Robert Dewar likes to point out, functions can have side effects, so
long as you don't document that fact in the parameter profile!)  The
rule is that the side effects must happen.

If you have two sub-expressions with side effects, they can happen in
either order.  That does make side effects less useful, but it is still
possible to write code so that the side effects are independent of each
other, so order doesn't matter.

In other words, the Ada rules encourage bugs in programs with side
effects, but they don't outlaw side effects.  Nor do they give the
optimizer permission to ignore side effects.

> The question is then, why stop at allowing any evaluation order and
> not just allow lazy evaluation as well?

Because Jean Ichbiah said so.  ;-)

It seems to me that if you're going to do lazy evaluation for all
function calls, then you really ought to be using a pure functional
language.

> It allows some "nice" optimizations, like the one I mentionned, or
> things like:
> 
> -- In some Debug package body:
> 
>    Enable_Trace : constant Boolean := True; 
>    -- or set to False when compiled in "release" mode
>    
>    procedure Trace (M : in String) is
>    begin
>       if Enable_Trace then
>           IO.Put (M);
>       end if;
>    end Trace;
> 
> -- Now you have your code full of Trace calls like:
> 
>    Trace ("index = " & Image (Index) & " value = " & Image (Value));

If you make put pragma Pure on Image, it can be optimized.
Unfortunately, you can't easily do that in all cases.

> With the current RM, even if the compilers know that the Trace call
> doesn't do anything (inlining is on, and proper unreached code
> elimination has been done), it cannot suppress the calls to Image or
> to "&" since they might potentially raise an exception. The only way
> to do a "release"/"debug" switch that does not cause a performance
> penalty for the "release" version is then to use vendor specific
> pragmas like GNAT Assert or Debug, and thus is outside of the
> language.
> 
> The "pragma" I was mentionning could look like:
> 
> pragma You_Can_Omit_Calls_To_This_If_The_Value_Is_Not_Needed (F);
> 
> (obviously a better name is needed ;-).

How about calling it Pure?  ;-)

>... If an expression involves only
> calls to pragma'ed functions (the Standard and String stuff could be
> in this category for example), then if the compiler finds out the
> result isn't needed in some run-time paths, it can omit the evaluation
> of the expression in those paths.
> 
> I don't know if I'm clearer here ;-).

Yes.

> > - Bob
> 
> --LG

Re: Right of Optimize Eager Evaluation Away

[Laurent Guerby]

Robert A Duff <bobduff@world.std.com> writes:
> If you have two sub-expressions with side effects, they can happen in
> either order.  That does make side effects less useful, but it is still
> possible to write code so that the side effects are independent of each
> other, so order doesn't matter.
> 
> In other words, the Ada rules encourage bugs in programs with side
> effects, but they don't outlaw side effects.  Nor do they give the
> optimizer permission to ignore side effects.

Well, that was my point, Ada makes the life of side-effect function
writers difficult in its current incarnation, in the sake of potential
optimization. Why not make another step, and allow lazy-style
optimization for Ada, at least under the control of a pragma?

> It seems to me that if you're going to do lazy evaluation for all
> function calls, then you really ought to be using a pure functional
> language.

I never said "all", that's the point of Ada, you can use the paradigm
you find adapted to your specific problem (simple private record, full
OO, functional with Pure, ...).

The state oriented part of the so-called pure functional languages I
know is just awful.  And I think most software will do state _and_
function, so I want to have a state oriented paradigm at hand when I'm
handling state so I can write code in a "natural" way, a functional
paradigm when I'm writing pure functions, and an high-level concurrent
paradigm when I'm writing the concurrent part, etc...

> > -- Now you have your code full of Trace calls like:
> >    Trace ("index = " & Image (Index) & " value = " & Image (Value));
> If you make put pragma Pure on Image, it can be optimized.

No, see below.

> > pragma You_Can_Omit_Calls_To_This_If_The_Value_Is_Not_Needed (F);
> > (obviously a better name is needed ;-).
> How about calling it Pure?  ;-)

Because, as I said, Pure doesn't allow the compiler to omit the call
(it can call the thing only once if the parameters don't change, or be
more aggressive and generate memo-izing code), just in case an
exception might happen. That's the point I made about the potential
exception raising being the only language barrier to the lazy
evaluation feature. You added independant side effects to the list,
but I would gladly drop or restrict this dubious feature in favour of
better potential optimization.

Or having the well-named pragma I proposed, since Pure doesn't do
the job I want to here ;-).

Also, Trace package and the like are unlikely to be Pure (but you can
use the Import trick to make them Pure as I mentioned it a few years
ago on this newsgroup ;-).

--LG

Re: Right of Optimize Eager Evaluation Away

[Niklas Holsti]

Laurent Guerby wrote:
  [ snip ]
> 
> Is the potential raising of an exception the only language barrier
> to allow lazy evaluation for an optimizing compiler?
> 
> It looks like to me that the Ada language more or less intend that
> functions shouldn't have side effects, since by example it allows the
> compiler to evaluate arguments and thus potentially calling functions
> in any order, or allows only "in" parameters for the programmer.
> 
> The question is then, why stop at allowing any evaluation order and
> not just allow lazy evaluation as well?

I think you could define a language like that. The question is
how it would be related to the (current) Ada language. It seems
sure to be incompatible with side-effecting functions, even if
differences in exception-raising are allowed.

RM 1.1.3(8) lists the external effects that should be preserved by
optimisation. There seem to be some that can be sensibly used by
programmers without knowing the evaluation order, but yet cannot
be omitted totally without harming the program's result:

   - setting the value of imported or exported objects (independent
     of order if the functions used in the parameter expressions set
     different objects)

   - reading or updating atomic or volatile objects (may be independent
     of order if the functions read/update different objects).

In other words, some programs could use side-effects of this type,
and still work whatever evaluation order is chosen. So to apply lazy
evaluation, the compiler should ensure that no such effects can
occur as side-effects of the lazily evaluated functions.

In practice, I would add any task interactions to this list. Given a
function that interacts with tasks, it seems quite unlikely that the
compiler could prove that omitting the task interactions would not
make any significant difference to the external effects, yet there
must be many cases in which the evaluation order of such functions
is not in fact significant for the correctness of the program.

> pragma You_Can_Omit_Calls_To_This_If_The_Value_Is_Not_Needed (F);
> 
> (obviously a better name is needed ;-). If an expression involves only
> calls to pragma'ed functions (the Standard and String stuff could be
> in this category for example), then if the compiler finds out the
> result isn't needed in some run-time paths, it can omit the evaluation
> of the expression in those paths.

Isn't pragma Pure (10.2.1(18)) something like this? Is it too
restrictive for you?

Regards,
Niklas

Working at but not speaking for Space Systems Finland Ltd.

Re: Right of Optimize Eager Evaluation Away

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1511 bytes --]


Laurent Guerby <guerby@acm.org> a �crit dans le message :
863dtqfo26.fsf@ppp-173-146.villette.club-internet.fr...
> [I originally posted this in the 11.6 thread, but got no answer]
>
> If we have the following function:
>
>    function Cond_T (C : in Boolean; If_True, If_False : in T) return T;
>    pragma Inline (Cond_T);
>
>    function Cond_T (C : in Boolean; If_True, If_False : in T) return T is
>    begin
>       if C then
>          return If_True;
>       else
>          return If_False;
>       end if;
>    end Cond_T;
>
> And the following expression:
>
>    C : constant Boolean :=
Some_Run_Time_Value_That_The_Compiler_Cannot_Guess;
>
>    X : constant T := Cont_T (C, If_True =>
Super_Expensive_Function_Call_1,
>                                 If_False =>
Super_Expensive_Function_Call_2);
>
> The question is: is a smart Ada 95 compiler allowed to generate code
> that looks like this:
>
>    if C then
>       X := Super_Expensive_Function_Call_1;
>    else
>       X := Super_Expensive_Function_Call_2;
>    end if;
>
> that is to say, be lazy about its argument, and so might
> save execution time.
>
The simplest solution in this case would be to pass pointers to the
Super_Expensive_Function_Calls;
This way, only the *pointers* are evaluated at the call, the functions are
actually called only as necessary...

--
---------------------------------------------------------
           J-P. Rosen (Rosen.Adalog@wanadoo.fr)
Visit Adalog's web site at http://pro.wanadoo.fr/adalog