Re: FOR loops running backwards

From: Martin Harvey (Demon Account) (martin_at_pergolesi.demon.co.uk)
Date: 11/01/03 

Date: Fri, 31 Oct 2003 23:38:39 +0000

On Thu, 30 Oct 2003 12:42:04 +0000, Dr John Stockton
<spam@merlyn.demon.co.uk> wrote:

>Read the FAQ more carefully.

I have. It's not sufficiently clear on this point, and in fact, I
suspect the FAQ writer didn't appreciate the subtleties involved.

>In this case, if "whatever" refers only to the current element, the
>order of operation is unimportant.

Rubbish. Well mostly - your second caveat is not sufficiently general.

It's easy for you to say "only looking at the current element", but
the compiler doesn't work in those terms - it's looking to see where
the index is used as an lvalue or an rvalue, and the subsequent usage
of those values.

I initially thought that you could apply the optimisation when:

- No external code is called in the loop.
- The loop index is not used to generate an rvalue, directly or
indirectly in the loop.
- The loop index may be used to generate lvalues.

I assumed for those premises that the compiler does not keep track of
which operations are order invariant.

However, even that is broken. Consider this:

MyRec = record a,b:integer; end;

MyArray = array[LowLim..HighLim] of MyRec;

MyInt:integer;

var
  X:MyArray;

begin
    for MyInt := LowLim to HighLim do
      Inc(X[MyInt].a, X[MyInt].b);
end;

Looks safe as houses, right?

'fraid not! Think of it like this:

begin
  try
    for MyInt := LowLim to HighLim do
      Inc(X[MyInt].a, X[MyInt].b);
  except
    on EOverflow do //access the array?
  end;
end;

Oh dear!!!!

So we have a whole load of extra provisos:

- The loop may not generate an exception at any point.
- if the index is used as an rvalue, then all subsequent operations
using that rvalue must be commutative and associative.

Hmmm ... but at this point the plot thickens. You need to start doing
things like:

a) Have a set of rules (that follow the grammar and syntax of the
language) on what operations are order insensitive.

b) Have set of rules indicating what scope things can be modified
with.

c) If exceptions can be raised, have rules that none of the quantities
modified in the loop can be accessed from the exception handler
(otherwise disallow the optimisation)

d) as implied by c, this means that the loop omitisation can only be
applied if it only accesses local variables - who knows what
exceptions the caller might handle.

Oooh er ... gets rather tricky doesn't it?

I'm off to try and break my delphi compiler :-) If I succeed, then
it's a post to the Borland NG's. If I fail, then it's a post to
comp.compilers!

MH.

Relevant Pages

  • Re: long double versions of functions in gcc under Cygwin
    ... rather than the nearest enclosing one) and a decent exception ... them it doesn't seem like goto usage would be affected ... int typfun() ... Why use a for loop when it is just a while loop in disguise? ...
    (comp.lang.c)
  • Re: CInternetSession
    ... the presence of the Sleepindicates the serious design flaw. ... Sleep() calls around like pixie dust, your design is fundamentally broken and will need to ... If you use Sleepin a loop, your design is probably wrong and needs to be ... The "First Chance Exception" message usually indicates nothing harmful. ...
    (microsoft.public.vc.mfc)
  • Re: Get_Line problem (GNAT bug?)
    ... Now, if the program specs says: "read the lines from input until EOF", then this for me immediately translates into a loop with some exit condition. ... "Read until" - you have a regular end-of-sequence condition here. ... I'm not convinced that exception might be a correct design choice for breaking the loop that reads data from well formatted file. ...
    (comp.lang.ada)
  • Re: long double versions of functions in gcc under Cygwin
    ... missing feature in the language. ... named break (which could be used to break out of a specified loop ... rather than the nearest enclosing one) and a decent exception ... goto just operates on the control flow of your program. ...
    (comp.lang.c)
  • Re: Threading and Serial port issue
    ... "fails" is pretty useless information. ... If it generates an exception, ... I then sit in a loop waiting for data to arrive. ... private void SetupBoard_Click ...
    (microsoft.public.dotnet.framework.compactframework)
Loading